const init_loom = create_loom ( null , ( ) => { } ) ; init_loom . set ( '=[]' ) ; export function make ( id = Math . random ( ) . toString ( 36 ) . slice ( 2 ) ) { let loom = create_loom ( { id } , ( ) => { } ) ; loom = merge ( loom , init_loom ) ; return loom ; } export function merge ( loom1 , loom2 ) { var new_loom1 = create_loom ( JSON . parse ( JSON . stringify ( loom1 ) ) , ( peer , msg ) => { if ( peer !== 'hi' ) new_loom2 . receive ( msg ) ; } ) ; var new_loom2 = create_loom ( JSON . parse ( JSON . stringify ( loom2 ) ) , ( peer , msg ) => { if ( peer !== 'hi' ) new_loom1 . receive ( msg ) ; } ) ; new_loom1 . get ( 'a' ) ; return new_loom1 ; } export function get_content ( loom ) { return loom . read ( ) ; } export function insert ( loom , position , content ) { loom . set ( `[${ position }:${ position }]=[${ JSON . stringify ( content ) }]` ) ; } function create_loom ( L , send ) { L = L ?? { } ; if ( ! L . id ) L . id = Math . random ( ) . toString ( 36 ) . slice ( 2 ) ; if ( ! L . next_seq ) L . next_seq = 0 ; L . S = L . S ?? null ; L . T = L . T ?? { } ; L . current_version = L . current_version ?? { } ; L . peers = L . peers ?? { } ; L . version_cache = L . version_cache ?? { } ; L . fissures = L . fissures ?? { } ; L . acked_boundary = L . acked_boundary ?? { } ; L . unack_boundary = L . unack_boundary ?? { } ; L . acks_in_process = L . acks_in_process ?? { } ; var orig_send = send ; send = ( to , msg ) => { orig_send ( to , { peer : L . id , conn : L . peers [ to ] , ... msg } ) ; } ; L . get = peer => { send ( peer , { cmd : 'get' , conn : Math . random ( ) . toString ( 36 ) . slice ( 2 ) } ) ; } ; L . forget = peer => { send ( peer , { cmd : 'forget' } ) ; } ; L . disconnect = peer => { if ( ! L . peers [ peer ] ) return ; var conn = L . peers [ peer ] ; delete L . peers [ peer ] ; var versions = { } ; var ack_versions = ancestors ( L . acked_boundary ) ; Object . keys ( L . T ) . forEach ( v => { if ( ! ack_versions [ v ] || L . acked_boundary [ v ] ) versions [ v ] = true ; } ) ; L . receive ( { cmd : 'fissure' , fissure : { a : L . id , b : peer , conn , versions , time : Date . now ( ) } } ) ; } ; L . set = ( ... patches ) => { var version = `${ L . id }@${ L . next_seq ++ }` ; L . receive ( { cmd : 'set' , version , parents : { ... L . current_version } , patches } ) ; return version ; } ; L . read = ( is_anc ) => { if ( ! is_anc ) is_anc = ( ) => true ; else if ( typeof ( is_anc ) == 'string' ) { var ancs = loom1 . ancestors ( { [ is_anc ] : true } ) ; is_anc = v => ancs [ v ] ; } else if ( typeof ( is_anc ) == 'object' ) { var ancs = loom1 . ancestors ( is_anc ) ; is_anc = v => ancs [ v ] ; } return rec_read ( L . S ) ; function rec_read ( x ) { if ( x && typeof ( x ) == 'object' ) { if ( x . t == 'lit' ) return JSON . parse ( JSON . stringify ( x . S ) ) ; if ( x . t == 'val' ) return rec_read ( space_dag_get ( x . S , 0 , is_anc ) ) ; if ( x . t == 'obj' ) { var o = { } ; Object . entries ( x . S ) . forEach ( ( [ k , v ] ) => { var x = rec_read ( v ) ; if ( x != null ) o [ k ] = x ; } ) ; return o ; } if ( x . t == 'arr' ) { var a = [ ] ; traverse_space_dag ( x . S , is_anc , ( node , _ , __ , ___ , ____ , deleted ) => { if ( ! deleted ) node . elems . forEach ( ( e ) => a . push ( rec_read ( e ) ) ) ; } , true ) ; return a ; } if ( x . t == 'str' ) { var s = [ ] ; traverse_space_dag ( x . S , is_anc , ( node , _ , __ , ___ , ____ , deleted ) => { if ( ! deleted ) s . push ( node . elems ) ; } , true ) ; return s . join ( '' ) ; } throw Error ( 'bad' ) ; } return x ; } } ; L . receive = ( { cmd , version , parents , patches , fissure , versions , fissures , unack_boundary , min_leaves , peer , conn } ) => { if ( cmd == 'get' || cmd == 'get_back' ) { L . peers [ peer ] = conn ; if ( cmd == 'get' ) send ( peer , { cmd : 'get_back' } ) ; send ( peer , { cmd : 'welcome' , versions : generate_braid ( parents ) , fissures : Object . values ( L . fissures ) , parents : parents && Object . keys ( parents ) . length ? get_leaves ( ancestors ( parents , true ) ) : { } } ) ; } else if ( cmd == 'forget' ) { if ( ! L . peers [ peer ] ) throw Error ( 'bad' ) ; delete L . peers [ peer ] ; L . acks_in_process = { } ; } else if ( cmd == 'set' ) { for ( const p in parents ) if ( ! L . T [ p ] ) return send ( peer , { cmd : 'error' } ) ; if ( ! peer || ! L . T [ version ] ) { var rebased_patches = add_version ( version , parents , patches ) ; for ( let p of Object . keys ( L . peers ) ) if ( p != peer ) send ( p , { cmd : 'set' , version , parents , patches } ) ; L . acks_in_process [ version ] = { origin : peer , count : Object . keys ( L . peers ) . length } ; if ( peer ) L . acks_in_process [ version ] . count -- ; } else if ( L . acks_in_process [ version ] ) L . acks_in_process [ version ] . count -- ; check_ack_count ( version ) ; return rebased_patches ; } else if ( cmd == 'ack1' ) { if ( L . acks_in_process [ version ] ) { L . acks_in_process [ version ] . count -- ; check_ack_count ( version ) ; } } else if ( cmd == 'ack2' ) { if ( ! L . T [ version ] ) return ; if ( ancestors ( L . unack_boundary ) [ version ] ) return ; if ( ancestors ( L . acked_boundary ) [ version ] ) return ; add_full_ack_leaf ( version ) ; for ( let p of Object . keys ( L . peers ) ) if ( p != peer ) send ( p , { cmd : 'ack2' , version } ) ; } else if ( cmd == 'fissure' ) { var key = fissure . a + ':' + fissure . b + ':' + fissure . conn ; if ( ! L . fissures [ key ] ) { L . fissures [ key ] = fissure ; L . acks_in_process = { } ; for ( let p of Object . keys ( L . peers ) ) if ( p != peer ) send ( p , { cmd : 'fissure' , fissure } ) ; if ( fissure . b == L . id ) L . receive ( { cmd : 'fissure' , fissure : { ... fissure , a : L . id , b : fissure . a } } ) ; } } else if ( cmd == 'welcome' ) { var versions_to_add = { } ; versions . forEach ( v => versions_to_add [ v . version ] = v . parents ) ; versions . forEach ( v => { if ( L . T [ v . version ] ) { remove_ancestors ( v . version ) ; function remove_ancestors ( v ) { if ( versions_to_add [ v ] ) { Object . keys ( versions_to_add [ v ] ) . forEach ( remove_ancestors ) ; delete versions_to_add [ v ] ; } } } } ) ; var send_error = ( ) => send ( peer , { cmd : 'error' } ) ; var rebased_patches = [ ] ; var added_versions = [ ] ; for ( var v of versions ) { if ( versions_to_add [ v . version ] ) { if ( ! Object . keys ( v . parents ) . every ( p => L . T [ p ] ) ) return send_error ( ) ; rebased_patches = rebased_patches . concat ( add_version ( v . version , v . parents , v . patches , v . sort_keys ) ) ; added_versions . push ( v ) ; } } if ( ( ( min_leaves && Object . keys ( min_leaves ) . some ( k => ! L . T [ k ] ) ) || ( unack_boundary && Object . keys ( unack_boundary ) . some ( k => ! L . T [ k ] ) ) ) ) return send_error ( ) ; var new_fissures = [ ] ; var gen_fissures = [ ] ; fissures . forEach ( f => { var key = f . a + ':' + f . b + ':' + f . conn ; if ( ! L . fissures [ key ] ) { new_fissures . push ( f ) ; L . fissures [ key ] = f ; if ( f . b == L . id ) gen_fissures . push ( { ... f , a : L . id , b : f . a } ) ; } } ) ; if ( ! unack_boundary ) unack_boundary = { ... L . current_version } ; var our_conn_versions = ancestors ( L . T , L . unack_boundary ) ; var new_conn_versions = ancestors ( L . T , unack_boundary ) ; Object . keys ( L . unack_boundary ) . forEach ( x => { if ( new_conn_versions [ x ] && ! unack_boundary [ x ] ) delete L . unack_boundary [ x ] ; } ) ; Object . keys ( unack_boundary ) . forEach ( x => { if ( ! our_conn_versions [ x ] ) L . unack_boundary [ x ] = true ; } ) ; if ( ! min_leaves ) { if ( versions . length === 0 && ( ! parents || Object . keys ( parents ) . length === 0 ) ) min_leaves = { ... L . current_version } ; else { min_leaves = parents ? { ... parents } : { } ; versions . forEach ( v => { if ( ! versions_to_add [ v . version ] ) min_leaves [ v . version ] = true ; } ) ; min_leaves = get_leaves ( ancestors ( min_leaves , true ) ) ; } } var min_versions = ancestors ( min_leaves ) ; var ack_versions = ancestors ( L . acked_boundary ) ; Object . keys ( L . acked_boundary ) . forEach ( x => { if ( ! min_versions [ x ] ) delete L . acked_boundary [ x ] ; } ) ; Object . keys ( min_leaves ) . forEach ( x => { if ( ack_versions [ x ] ) L . acked_boundary [ x ] = true ; } ) ; L . acks_in_process = { } ; if ( added_versions . length > 0 || new_fissures . length > 0 ) { for ( let p of Object . keys ( L . peers ) ) if ( p != peer ) send ( p , { cmd : 'welcome' , key , versions : added_versions , unack_boundary , min_leaves , fissures : new_fissures } ) ; } gen_fissures . forEach ( f => L . receive ( { cmd : 'fissure' , fissure : f } ) ) ; return rebased_patches ; } } ; var is_lit = x => ! x || typeof ( x ) != 'object' || x . t == 'lit' ; var get_lit = x => ( x && typeof ( x ) == 'object' && x . t == 'lit' ) ? x . S : x ; let make_lit = x => ( x && typeof ( x ) == 'object' ) ? { t : 'lit' , S : x } : x ; function prune ( ) { return ; var unremovable = { } ; Object . entries ( L . fissures ) . forEach ( x => { var other_key = x [ 1 ] . b + ':' + x [ 1 ] . a + ':' + x [ 1 ] . conn ; var other = L . fissures [ other_key ] ; if ( other ) { delete L . fissures [ x [ 0 ] ] ; delete L . fissures [ other_key ] ; } } ) ; if ( L . fissure_lifetime != null ) { var now = Date . now ( ) ; Object . entries ( L . fissures ) . forEach ( ( [ k , f ] ) => { if ( f . time == null ) f . time = now ; if ( f . time <= now - L . fissure_lifetime ) { delete L . fissures [ k ] ; } } ) ; } var keep_us = { } ; Object . values ( L . fissures ) . forEach ( f => { Object . keys ( f . versions ) . forEach ( v => keep_us [ v ] = true ) ; } ) ; var acked = ancestors ( L . T , L . acked_boundary ) ; Object . keys ( L . T ) . forEach ( x => { if ( ! acked [ x ] || L . acked_boundary [ x ] ) keep_us [ x ] = true ; } ) ; var children = { } ; Object . entries ( L . T ) . forEach ( ( [ v , parents ] ) => { Object . keys ( parents ) . forEach ( parent => { if ( ! children [ parent ] ) children [ parent ] = { } ; children [ parent ] [ v ] = true ; } ) ; } ) ; var to_bubble = { } ; var bubble_tops = { } ; var bubble_bottoms = { } ; function mark_bubble ( bottom , top , tag ) { if ( ! to_bubble [ bottom ] ) { to_bubble [ bottom ] = tag ; if ( bottom !== top ) Object . keys ( L . T [ bottom ] ) . forEach ( p => mark_bubble ( p , top , tag ) ) ; } } var done = { } ; function f ( cur ) { if ( ! L . T [ cur ] ) return ; if ( done [ cur ] ) return ; done [ cur ] = true ; if ( ! to_bubble [ cur ] || bubble_tops [ cur ] ) { var bubble_top = find_one_bubble ( cur ) ; if ( bubble_top ) { delete to_bubble [ cur ] ; mark_bubble ( cur , bubble_top , bubble_tops [ cur ] || cur ) ; bubble_tops [ bubble_top ] = bubble_tops [ cur ] || cur ; bubble_bottoms [ bubble_tops [ cur ] || cur ] = bubble_top ; } } Object . keys ( L . T [ cur ] ) . forEach ( f ) ; } Object . keys ( L . current_version ) . forEach ( f ) ; function find_one_bubble ( cur ) { var seen = { [ cur ] : true } ; var q = Object . keys ( L . T [ cur ] ) ; var expecting = Object . fromEntries ( q . map ( x => [ x , true ] ) ) ; while ( q . length ) { cur = q . pop ( ) ; if ( ! L . T [ cur ] ) return null ; if ( keep_us [ cur ] ) return null ; if ( Object . keys ( children [ cur ] ) . every ( c => seen [ c ] ) ) { seen [ cur ] = true ; delete expecting [ cur ] ; if ( ! Object . keys ( expecting ) . length ) return cur ; Object . keys ( L . T [ cur ] ) . forEach ( p => { q . push ( p ) ; expecting [ p ] = true ; } ) ; } } return null ; } to_bubble = Object . fromEntries ( Object . entries ( to_bubble ) . map ( ( [ v , bub ] ) => [ v , [ bub , bubble_bottoms [ bub ] ] ] ) ) ; apply_bubbles ( to_bubble ) ; } function add_full_ack_leaf ( version ) { var marks = { } ; function f ( v ) { if ( ! marks [ v ] ) { marks [ v ] = true ; delete L . unack_boundary [ v ] ; delete L . acked_boundary [ v ] ; delete L . acks_in_process [ v ] ; Object . keys ( L . T [ v ] ) . forEach ( f ) ; } } f ( version ) ; L . acked_boundary [ version ] = true ; prune ( L ) ; } function check_ack_count ( version ) { if ( L . acks_in_process [ version ] && L . acks_in_process [ version ] . count == 0 ) { if ( L . acks_in_process [ version ] . origin ) { send ( L . acks_in_process [ version ] . origin , { cmd : 'ack1' , version } ) ; } else { add_full_ack_leaf ( version ) ; for ( let p of Object . keys ( L . peers ) ) send ( p , { cmd : 'ack2' , version } ) ; } } } function generate_braid ( versions ) { var anc = versions && Object . keys ( versions ) . length ? ancestors ( versions , true ) : { } ; var is_anc = x => anc [ x ] ; if ( Object . keys ( L . T ) . length === 0 ) return [ ] ; return Object . entries ( L . version_cache ) . filter ( x => ! is_anc ( x [ 0 ] ) ) . map ( ( [ version , set_message ] ) => { return L . version_cache [ version ] = set_message || generate_set_message ( version ) ; } ) ; function generate_set_message ( version ) { if ( ! Object . keys ( L . T [ version ] ) . length ) { return { version , parents : { } , patches : [ ` = ${ JSON . stringify ( L . read ( v => v == version ) ) }` ] } ; } var is_lit = x => ! x || typeof ( x ) !== 'object' || x . t === 'lit' ; var get_lit = x => ( x && typeof ( x ) === 'object' && x . t === 'lit' ) ? x . S : x ; var ancs = ancestors ( { [ version ] : true } ) ; delete ancs [ version ] ; var is_anc = x => ancs [ x ] ; var path = [ ] ; var patches = [ ] ; var sort_keys = { } ; recurse ( L . S ) ; function recurse ( x ) { if ( is_lit ( x ) ) { } else if ( x . t === 'val' ) { space_dag_generate_braid ( x . S , version , is_anc ) . forEach ( s => { if ( s [ 2 ] . length ) { patches . push ( `${ path . join ( '' ) } = ${ JSON . stringify ( s [ 2 ] [ 0 ] ) }` ) ; if ( s [ 3 ] ) sort_keys [ patches . length - 1 ] = s [ 3 ] ; } } ) ; traverse_space_dag ( x . S , is_anc , node => { node . elems . forEach ( recurse ) ; } ) ; } else if ( x . t === 'arr' ) { space_dag_generate_braid ( x . S , version , is_anc ) . forEach ( s => { patches . push ( `${ path . join ( '' ) }[${ s [ 0 ] }:${ s [ 0 ] + s [ 1 ] }] = ${ JSON . stringify ( s [ 2 ] ) }` ) ; if ( s [ 3 ] ) sort_keys [ patches . length - 1 ] = s [ 3 ] ; } ) ; var i = 0 ; traverse_space_dag ( x . S , is_anc , node => { node . elems . forEach ( e => { path . push ( `[${ i ++ }]` ) ; recurse ( e ) ; path . pop ( ) ; } ) ; } ) ; } else if ( x . t === 'obj' ) { Object . entries ( x . S ) . forEach ( e => { path . push ( '[' + JSON . stringify ( e [ 0 ] ) + ']' ) ; recurse ( e [ 1 ] ) ; path . pop ( ) ; } ) ; } else if ( x . t === 'str' ) { space_dag_generate_braid ( x . S , version , is_anc ) . forEach ( s => { patches . push ( `${ path . join ( '' ) }[${ s [ 0 ] }:${ s [ 0 ] + s [ 1 ] }] = ${ JSON . stringify ( s [ 2 ] ) }` ) ; if ( s [ 3 ] ) sort_keys [ patches . length - 1 ] = s [ 3 ] ; } ) ; } } return { version , parents : { ... L . T [ version ] } , patches , sort_keys } ; } } function apply_bubbles ( to_bubble ) { function recurse ( x ) { if ( is_lit ( x ) ) return x ; if ( x . t == 'val' ) { space_dag_apply_bubbles ( x . S , to_bubble ) ; traverse_space_dag ( x . S , ( ) => true , node => { node . elems = node . elems . slice ( 0 , 1 ) . map ( recurse ) ; } , true ) ; if ( x . S . nexts . length == 0 && ! x . S . next && x . S . elems . length == 1 && is_lit ( x . S . elems [ 0 ] ) ) return x . S . elems [ 0 ] ; return x ; } if ( x . t == 'arr' ) { space_dag_apply_bubbles ( x . S , to_bubble ) ; traverse_space_dag ( x . S , ( ) => true , node => { node . elems = node . elems . map ( recurse ) ; } , true ) ; if ( x . S . nexts . length == 0 && ! x . S . next && x . S . elems . every ( is_lit ) && ! Object . keys ( x . S . deleted_by ) . length ) return { t : 'lit' , S : x . S . elems . map ( get_lit ) } ; return x ; } if ( x . t == 'obj' ) { Object . entries ( x . S ) . forEach ( e => { var y = x . S [ e [ 0 ] ] = recurse ( e [ 1 ] ) ; if ( y == null ) delete x . S [ e [ 0 ] ] ; } ) ; if ( Object . values ( x . S ) . every ( is_lit ) ) { var o = { } ; Object . entries ( x . S ) . forEach ( e => o [ e [ 0 ] ] = get_lit ( e [ 1 ] ) ) ; return { t : 'lit' , S : o } ; } return x ; } if ( x . t == 'str' ) { space_dag_apply_bubbles ( x . S , to_bubble ) ; if ( x . S . nexts . length == 0 && ! x . S . next && ! Object . keys ( x . S . deleted_by ) . length ) return x . S . elems ; return x ; } } L . S = recurse ( L . S ) ; Object . entries ( to_bubble ) . forEach ( ( [ version , bubble ] ) => { if ( version === bubble [ 1 ] ) L . T [ bubble [ 0 ] ] = L . T [ bubble [ 1 ] ] ; if ( version !== bubble [ 0 ] ) { delete L . T [ version ] ; delete L . version_cache [ version ] ; } else L . version_cache [ version ] = null ; } ) ; var leaves = Object . keys ( L . current_version ) ; var acked_boundary = Object . keys ( L . acked_boundary ) ; var fiss = Object . keys ( L . fissures ) ; if ( leaves . length == 1 && acked_boundary . length == 1 && leaves [ 0 ] == acked_boundary [ 0 ] && fiss . length == 0 ) { L . T = { [ leaves [ 0 ] ] : { } } ; L . S = make_lit ( L . read ( ) ) ; } } function add_version ( version , parents , patches , sort_keys , is_anc ) { if ( L . T [ version ] ) return ; L . T [ version ] = { ... parents } ; L . version_cache [ version ] = JSON . parse ( JSON . stringify ( { version , parents , patches , sort_keys } ) ) ; Object . keys ( parents ) . forEach ( k => { if ( L . current_version [ k ] ) delete L . current_version [ k ] ; } ) ; L . current_version [ version ] = true ; if ( ! sort_keys ) sort_keys = { } ; if ( ! Object . keys ( parents ) . length ) { var parse = parse_patch ( patches [ 0 ] ) ; L . S = make_lit ( parse . value ) ; return patches ; } if ( ! is_anc ) { if ( parents == L . current_version ) { is_anc = _version => _version != version ; } else { var ancs = ancestors ( parents ) ; is_anc = _version => ancs [ _version ] ; } } var rebased_patches = [ ] ; patches . forEach ( ( patch , i ) => { var sort_key = sort_keys [ i ] ; var parse = parse_patch ( patch ) ; var cur = resolve_path ( parse ) ; if ( ! parse . slice ) { if ( cur . t != 'val' ) throw Error ( 'bad' ) ; var len = space_dag_length ( cur . S , is_anc ) ; space_dag_add_version ( cur . S , version , [ [ 0 , len , [ parse . delete ? null : make_lit ( parse . value ) ] ] ] , sort_key , is_anc ) ; rebased_patches . push ( patch ) ; } else { if ( typeof parse . value === 'string' && cur . t !== 'str' ) throw `Cannot splice string ${ JSON . stringify ( parse . value ) } into non-string` ; if ( parse . value instanceof Array && cur . t !== 'arr' ) throw `Cannot splice array ${ JSON . stringify ( parse . value ) } into non-array` ; if ( parse . value instanceof Array ) parse . value = parse . value . map ( x => make_lit ( x ) ) ; var r0 = parse . slice [ 0 ] ; var r1 = parse . slice [ 1 ] ; if ( r0 < 0 || Object . is ( r0 , - 0 ) || r1 < 0 || Object . is ( r1 , - 0 ) ) { let len = space_dag_length ( cur . S , is_anc ) ; if ( r0 < 0 || Object . is ( r0 , - 0 ) ) r0 = len + r0 ; if ( r1 < 0 || Object . is ( r1 , - 0 ) ) r1 = len + r1 ; } var rebased_splices = space_dag_add_version ( cur . S , version , [ [ r0 , r1 - r0 , parse . value ] ] , sort_key , is_anc ) ; for ( let rebased_splice of rebased_splices ) rebased_patches . push ( `${ parse . path . map ( x => `[${ JSON . stringify ( x ) }]` ) . join ( '' ) }[${ rebased_splice [ 0 ] }:${ rebased_splice [ 0 ] + rebased_splice [ 1 ] }] = ${ JSON . stringify ( rebased_splice [ 2 ] ) }` ) ; } } ) ; function resolve_path ( parse ) { var cur = L . S ; if ( ! cur || typeof ( cur ) != 'object' || cur . t == 'lit' ) cur = L . S = { t : 'val' , S : create_space_dag_node ( null , [ cur ] ) } ; var prev_S = null ; var prev_i = 0 ; for ( var i = 0 ; i < parse . path . length ; i ++ ) { var key = parse . path [ i ] ; if ( cur . t == 'val' ) cur = space_dag_get ( prev_S = cur . S , prev_i = 0 , is_anc ) ; if ( cur . t == 'lit' ) { var new_cur = { } ; if ( cur . S instanceof Array ) { new_cur . t = 'arr' ; new_cur . S = create_space_dag_node ( null , cur . S . map ( x => make_lit ( x ) ) ) ; } else { if ( typeof ( cur . S ) != 'object' ) throw Error ( 'bad' ) ; new_cur . t = 'obj' ; new_cur . S = { } ; Object . entries ( cur . S ) . forEach ( e => new_cur . S [ e [ 0 ] ] = make_lit ( e [ 1 ] ) ) ; } cur = new_cur ; space_dag_set ( prev_S , prev_i , cur , is_anc ) ; } if ( cur . t == 'obj' ) { let x = cur . S [ key ] ; if ( ! x || typeof ( x ) != 'object' || x . t == 'lit' ) x = cur . S [ key ] = { t : 'val' , S : create_space_dag_node ( null , [ x == null ? null : x ] ) } ; cur = x ; } else if ( i == parse . path . length - 1 && ! parse . slice ) { parse . slice = [ key , key + 1 ] ; parse . value = ( cur . t == 'str' ) ? parse . value : [ parse . value ] ; } else if ( cur . t == 'arr' ) { cur = space_dag_get ( prev_S = cur . S , prev_i = key , is_anc ) ; } else throw Error ( 'bad' ) ; } if ( parse . slice ) { if ( cur . t == 'val' ) cur = space_dag_get ( prev_S = cur . S , prev_i = 0 , is_anc ) ; if ( typeof ( cur ) == 'string' ) { cur = { t : 'str' , S : create_space_dag_node ( null , cur ) } ; space_dag_set ( prev_S , prev_i , cur , is_anc ) ; } else if ( cur . t == 'lit' ) { if ( ! ( cur . S instanceof Array ) ) throw Error ( 'bad' ) ; cur = { t : 'arr' , S : create_space_dag_node ( null , cur . S . map ( x => make_lit ( x ) ) ) } ; space_dag_set ( prev_S , prev_i , cur , is_anc ) ; } } return cur ; } return rebased_patches ; } function ancestors ( versions , ignore_nonexistent ) { var result = { } ; function recurse ( version ) { if ( result [ version ] ) return ; if ( ! L . T [ version ] ) { if ( ignore_nonexistent ) return ; throw `The version ${ version } no existo` ; } result [ version ] = true ; Object . keys ( L . T [ version ] ) . forEach ( recurse ) ; } Object . keys ( versions ) . forEach ( recurse ) ; return result ; } function get_leaves ( versions ) { var leaves = { ... versions } ; Object . keys ( versions ) . forEach ( v => { Object . keys ( L . T [ v ] ) . forEach ( p => delete leaves [ p ] ) ; } ) ; return leaves ; } return L ; } function create_space_dag_node ( version , elems , end_cap , sort_key ) { return { version : version , sort_key : sort_key , elems : elems , deleted_by : { } , end_cap : end_cap , nexts : [ ] , next : null } ; } function space_dag_generate_braid ( S , version , is_anc ) { var splices = [ ] ; function add_ins ( offset , ins , sort_key , end_cap ) { if ( typeof ( ins ) !== 'string' ) ins = ins . map ( x => read_raw ( x , ( ) => false ) ) ; if ( splices . length > 0 ) { var prev = splices [ splices . length - 1 ] ; if ( prev [ 0 ] + prev [ 1 ] === offset && ! end_cap && ( prev [ 4 ] === 'i' || ( prev [ 4 ] === 'r' && prev [ 1 ] === 0 ) ) ) { prev [ 2 ] = prev [ 2 ] . concat ( ins ) ; return ; } } splices . push ( [ offset , 0 , ins , sort_key , end_cap ? 'r' : 'i' ] ) ; } function add_del ( offset , del , ins ) { if ( splices . length > 0 ) { var prev = splices [ splices . length - 1 ] ; if ( prev [ 0 ] + prev [ 1 ] === offset && prev [ 4 ] !== 'i' ) { prev [ 1 ] += del ; return ; } } splices . push ( [ offset , del , ins , null , 'd' ] ) ; } var offset = 0 ; function helper ( node , _version , end_cap ) { if ( _version === version ) { add_ins ( offset , node . elems . slice ( 0 ) , node . sort_key , end_cap ) ; } else if ( node . deleted_by [ version ] && node . elems . length > 0 ) { add_del ( offset , node . elems . length , node . elems . slice ( 0 , 0 ) ) ; } if ( ( ! _version || is_anc ( _version ) ) && ! Object . keys ( node . deleted_by ) . some ( is_anc ) ) { offset += node . elems . length ; } node . nexts . forEach ( next => helper ( next , next . version , node . end_cap ) ) ; if ( node . next ) helper ( node . next , _version ) ; } helper ( S , null ) ; splices . forEach ( s => { if ( s [ 4 ] === 'r' && s [ 1 ] === 0 ) s [ 1 ] = 1 ; } ) ; return splices ; } function space_dag_apply_bubbles ( S , to_bubble ) { traverse_space_dag ( S , ( ) => true , node => { if ( to_bubble [ node . version ] && to_bubble [ node . version ] [ 0 ] != node . version ) { if ( ! node . sort_key ) node . sort_key = node . version ; node . version = to_bubble [ node . version ] [ 0 ] ; } for ( var x of Object . keys ( node . deleted_by ) ) { if ( to_bubble [ x ] ) { delete node . deleted_by [ x ] ; node . deleted_by [ to_bubble [ x ] [ 0 ] ] = true ; } } } , true ) ; function set_nnnext ( node , next ) { while ( node . next ) node = node . next ; node . next = next ; } do_line ( S , S . version ) ; function do_line ( node , version ) { var prev = null ; while ( node ) { if ( node . nexts [ 0 ] && node . nexts [ 0 ] . version == version ) { for ( let i = 0 ; i < node . nexts . length ; i ++ ) { delete node . nexts [ i ] . version ; delete node . nexts [ i ] . sort_key ; set_nnnext ( node . nexts [ i ] , i + 1 < node . nexts . length ? node . nexts [ i + 1 ] : node . next ) ; } node . next = node . nexts [ 0 ] ; node . nexts = [ ] ; } if ( node . deleted_by [ version ] ) { node . elems = node . elems . slice ( 0 , 0 ) ; node . deleted_by = { } ; if ( prev ) { node = prev ; continue ; } } var next = node . next ; if ( ! node . nexts . length && next && ( ! node . elems . length || ! next . elems . length || ( Object . keys ( node . deleted_by ) . every ( x => next . deleted_by [ x ] ) && Object . keys ( next . deleted_by ) . every ( x => node . deleted_by [ x ] ) ) ) ) { if ( ! node . elems . length ) node . deleted_by = next . deleted_by ; node . elems = node . elems . concat ( next . elems ) ; node . end_cap = next . end_cap ; node . nexts = next . nexts ; node . next = next . next ; continue ; } for ( let n of node . nexts ) do_line ( n , n . version ) ; prev = node ; node = next ; } } } function space_dag_get ( S , i , is_anc ) { var ret = null ; var offset = 0 ; traverse_space_dag ( S , is_anc ? is_anc : ( ) => true , ( node ) => { if ( i - offset < node . elems . length ) { ret = node . elems [ i - offset ] ; return false ; } offset += node . elems . length ; } ) ; return ret ; } function space_dag_set ( S , i , v , is_anc ) { var offset = 0 ; traverse_space_dag ( S , is_anc ? is_anc : ( ) => true , ( node ) => { if ( i - offset < node . elems . length ) { node . elems [ i - offset ] = v ; return false ; } offset += node . elems . length ; } ) ; } function space_dag_length ( S , is_anc ) { var count = 0 ; traverse_space_dag ( S , is_anc ? is_anc : ( ) => true , node => { count += node . elems . length ; } ) ; return count ; } function space_dag_break_node ( node , x , end_cap , new_next ) { var tail = create_space_dag_node ( null , node . elems . slice ( x ) , node . end_cap ) ; Object . assign ( tail . deleted_by , node . deleted_by ) ; tail . nexts = node . nexts ; tail . next = node . next ; node . elems = node . elems . slice ( 0 , x ) ; node . end_cap = end_cap ; node . nexts = new_next ? [ new_next ] : [ ] ; node . next = tail ; return tail ; } function space_dag_add_version ( S , version , splices , sort_key , is_anc ) { var rebased_splices = [ ] ; function add_to_nexts ( nexts , to ) { var i = binarySearch ( nexts , function ( x ) { if ( ( to . sort_key || to . version ) < ( x . sort_key || x . version ) ) return - 1 ; if ( ( to . sort_key || to . version ) > ( x . sort_key || x . version ) ) return 1 ; return 0 ; } ) ; nexts . splice ( i , 0 , to ) ; } var si = 0 ; var delete_up_to = 0 ; var process_patch = ( node , offset , has_nexts , prev , _version , deleted ) => { var s = splices [ si ] ; if ( ! s ) return false ; if ( deleted ) { if ( s [ 1 ] == 0 && s [ 0 ] == offset ) { if ( node . elems . length == 0 && ! node . end_cap && has_nexts ) return ; var new_node = create_space_dag_node ( version , s [ 2 ] , null , sort_key ) ; rebased_splices . push ( [ rebase_offset , 0 , s [ 2 ] ] ) ; if ( node . elems . length == 0 && ! node . end_cap ) add_to_nexts ( node . nexts , new_node ) ; else space_dag_break_node ( node , 0 , undefined , new_node ) ; si ++ ; } return ; } if ( s [ 1 ] == 0 ) { var d = s [ 0 ] - ( offset + node . elems . length ) ; if ( d > 0 ) return ; if ( d == 0 && ! node . end_cap && has_nexts ) return ; var new_node = create_space_dag_node ( version , s [ 2 ] , null , sort_key ) ; rebased_splices . push ( [ rebase_offset + s [ 0 ] - offset , 0 , s [ 2 ] ] ) ; if ( d == 0 && ! node . end_cap ) { add_to_nexts ( node . nexts , new_node ) ; } else { space_dag_break_node ( node , s [ 0 ] - offset , undefined , new_node ) ; } si ++ ; return ; } if ( delete_up_to <= offset ) { var d = s [ 0 ] - ( offset + node . elems . length ) ; if ( d >= 0 ) return ; delete_up_to = s [ 0 ] + s [ 1 ] ; if ( s [ 2 ] ) { var new_node = create_space_dag_node ( version , s [ 2 ] , null , sort_key ) ; rebased_splices . push ( [ rebase_offset + s [ 0 ] - offset , 0 , s [ 2 ] ] ) ; if ( s [ 0 ] == offset && prev && prev . end_cap ) { add_to_nexts ( prev . nexts , new_node ) ; } else { space_dag_break_node ( node , s [ 0 ] - offset , true , new_node ) ; return ; } } else { if ( s [ 0 ] == offset ) { } else { space_dag_break_node ( node , s [ 0 ] - offset ) ; return ; } } } if ( delete_up_to > offset ) { if ( delete_up_to <= offset + node . elems . length ) { if ( delete_up_to < offset + node . elems . length ) { space_dag_break_node ( node , delete_up_to - offset ) ; } si ++ ; } node . deleted_by [ version ] = true ; rebased_splices . push ( [ rebase_offset , node . elems . length , '' ] ) ; return ; } } ; var f = is_anc ; var exit_early = { } ; var offset = 0 ; var rebase_offset = 0 ; function traverse ( node , prev , version ) { var rebase_deleted = Object . keys ( node . deleted_by ) . length > 0 ; if ( ! version || f ( version ) ) { var has_nexts = node . nexts . find ( next => f ( next . version ) ) ; var deleted = Object . keys ( node . deleted_by ) . some ( version => f ( version ) ) ; if ( process_patch ( node , offset , has_nexts , prev , version , deleted ) == false ) throw exit_early ; if ( ! deleted ) offset += node . elems . length ; } if ( ! rebase_deleted ) rebase_offset += node . elems . length ; for ( var next of node . nexts ) traverse ( next , null , next . version ) ; if ( node . next ) traverse ( node . next , node , version ) ; } try { traverse ( S , null , S . version ) ; } catch ( e ) { if ( e != exit_early ) throw e ; } return rebased_splices ; } function traverse_space_dag ( S , f , cb , view_deleted , tail_cb ) { var exit_early = { } ; var offset = 0 ; function helper ( node , prev , version ) { var has_nexts = node . nexts . find ( next => f ( next . version ) ) ; var deleted = Object . keys ( node . deleted_by ) . some ( version => f ( version ) ) ; if ( view_deleted || ! deleted ) { if ( cb ( node , offset , has_nexts , prev , version , deleted ) == false ) throw exit_early ; offset += node . elems . length ; } for ( var next of node . nexts ) if ( f ( next . version ) ) helper ( next , null , next . version ) ; if ( node . next ) helper ( node . next , node , version ) ; else if ( tail_cb ) tail_cb ( node ) ; } try { helper ( S , null , S . version ) ; } catch ( e ) { if ( e != exit_early ) throw e ; } } function parse_patch ( patch ) { var ret = { path : [ ] } ; var re = /^(delete)\s+|\.?([^\.\[ =]+)|\[((\-?\d+)(:\-?\d+)?|'(\\'|[^'])*'|"(\\"|[^"])*")\]|\s*=\s*([\s\S]*)/g ; var m ; while ( m = re . exec ( patch ) ) { if ( m [ 1 ] ) ret . delete = true ; else if ( m [ 2 ] ) ret . path . push ( m [ 2 ] ) ; else if ( m [ 3 ] && m [ 5 ] ) ret . slice = [ JSON . parse ( m [ 4 ] ) , JSON . parse ( m [ 5 ] . substr ( 1 ) ) ] ; else if ( m [ 3 ] ) ret . path . push ( JSON . parse ( m [ 3 ] ) ) ; else if ( m [ 8 ] ) ret . value = JSON . parse ( m [ 8 ] ) ; } return ret ; } function binarySearch ( ar , compare_fn ) { var m = 0 ; var n = ar . length - 1 ; while ( m <= n ) { var k = ( n + m ) >> 1 ; var cmp = compare_fn ( ar [ k ] ) ; if ( cmp > 0 ) { m = k + 1 ; } else if ( cmp < 0 ) { n = k - 1 ; } else { return k ; } } return m ; }