import assert from 'assert' ; import consoleLib from 'console' ; import chalk from 'chalk' ; globalThis . console = new consoleLib . Console ( { stdout : process . stdout , stderr : process . stderr , inspectOptions : { depth : null } } ) ; export type Id = [ agent : string , seq : number ] ; export type Version = Record < string , number > ; export type Algorithm = { localInsert : < T > ( this : Algorithm , doc : Doc < T > , agent : string , pos : number , content : T ) => void ; integrate : < T > ( doc : Doc < T > , newItem : Item < T > , idx_hint ? : number ) => void ; printDoc : < T > ( doc : Doc < T > ) => void ; ignoreTests ? : string [ ] ; } ; type YjsItem < T > = { content : T ; id : Id ; originLeft : Id | null ; originRight : Id | null ; isDeleted : boolean ; } ; type AMItem < T > = { content : T ; id : Id ; originLeft : Id | null ; seq : number ; isDeleted : boolean ; } ; type Sync9Item < T > = { content : T | null ; id : Id ; originLeft : Id | null ; insertAfter : boolean ; isDeleted : boolean ; } ; export type Item < T > = { content : T | null ; id : Id ; originLeft : Id | null ; originRight : Id | null ; seq : number ; insertAfter : boolean ; isDeleted : boolean ; } ; export interface Doc < T = string > { content : Item < T > [ ] ; version : Version ; length : number ; maxSeq : number ; } export const newDoc = < T > ( ) : Doc < T > => ( { content : [ ] , version : { } , length : 0 , maxSeq : 0 , } ) ; const idEq2 = ( a , agent , seq ) : boolean => ( a != null && ( a [ 0 ] === agent && a [ 1 ] === seq ) ) ; const idEq = ( a , b ) : boolean => ( a == b || ( a != null && b != null && a [ 0 ] === b [ 0 ] && a [ 1 ] === b [ 1 ] ) ) ; let hits = 0 ; let misses = 0 ; const findItem2 = < T > ( doc , needle , atEnd = false , idx_hint = - 1 ) : number => { if ( needle == null ) return - 1 ; else { const [ agent , seq ] = needle ; if ( idx_hint >= 0 && idx_hint < doc . content . length ) { const hint_item = doc . content [ idx_hint ] ; if ( ( ! atEnd && idEq2 ( hint_item . id , agent , seq ) ) || ( hint_item . content != null && atEnd && idEq2 ( hint_item . id , agent , seq ) ) ) { hits ++ ; return idx_hint ; } } misses ++ ; const idx = doc . content . findIndex ( ( { content , id } ) => ( ( ! atEnd && idEq2 ( id , agent , seq ) ) || ( content != null && atEnd && idEq2 ( id , agent , seq ) ) ) ) ; if ( idx < 0 ) throw Error ( 'Could not find item' ) ; return idx ; } } ; const findItem = < T > ( doc , needle , idx_hint = - 1 ) : number => ( findItem2 ( doc , needle , false , idx_hint ) ) ; const findItemAtPos = < T > ( doc , pos , stick_end = false ) : number => { let i = 0 ; for ( ; i < doc . content . length ; i ++ ) { const item = doc . content [ i ] ; if ( stick_end && pos === 0 ) return i ; else if ( item . isDeleted || item . content == null ) continue ; else if ( pos === 0 ) return i ; pos -- ; } if ( pos === 0 ) return i ; else throw Error ( 'past end of the document' ) ; } ; function localInsert < T > ( this , doc , agent , pos , content ) { let i = findItemAtPos ( doc , pos ) ; this . integrate ( doc , { content , id : [ agent , ( doc . version [ agent ] ?? - 1 ) + 1 ] , isDeleted : false , originLeft : doc . content [ i - 1 ] ?. id ?? null , originRight : doc . content [ i ] ?. id ?? null , insertAfter : true , seq : doc . maxSeq + 1 , } , i ) ; } function localInsertSync9 < T > ( this , doc , agent , pos , content ) { let i = findItemAtPos ( doc , pos , true ) ; let parentIdBase = doc . content [ i - 1 ] ?. id ?? null ; let originLeft = parentIdBase == null ? null : [ parentIdBase [ 0 ] , parentIdBase [ 1 ] ] ; let insertAfter = true ; for ( ; ; i ++ ) { let nextItem = doc . content [ i ] ; if ( nextItem == null || ! idEq ( nextItem . originLeft , parentIdBase ) ) break ; parentIdBase = nextItem . id ; originLeft = [ nextItem . id [ 0 ] , nextItem . id [ 1 ] ] ; insertAfter = false ; if ( nextItem . content != null ) break ; } this . integrate ( doc , { content , id : [ agent , ( doc . version [ agent ] ?? - 1 ) + 1 ] , isDeleted : false , originLeft , insertAfter , originRight : null , seq : 0 , } , i ) ; } export const localDelete = < T > ( doc , agent , pos ) : void => { const item = doc . content [ findItemAtPos ( doc , pos ) ] ; if ( ! item . isDeleted ) { item . isDeleted = true ; doc . length -= 1 ; } } ; export const getArray = < T > ( doc ) : T [ ] => ( doc . content . filter ( i => ! i . isDeleted && i . content != null ) . map ( i => i . content ! ) ) ; const printdoc = < T > ( doc , showSeq , showOR , showIsAfter ) => { const depth = { } ; const kForItem = ( id , isAfter ) => `${ id [ 0 ] } ${ id [ 1 ] } ${ isAfter }` ; for ( const i of doc . content ) { const d = i . originLeft == null ? 0 : depth [ kForItem ( i . originLeft , i . insertAfter ) ] + 1 ; depth [ kForItem ( i . id , i . content != null ) ] = d ; let content = `${ i . content == null ? '.' : i . isDeleted ? chalk . strikethrough ( i . content ) : chalk . yellow ( i . content ) } at [${ i . id }] (parent [${ i . originLeft }])` ; if ( showSeq ) content += ` seq ${ i . seq }` ; if ( showOR ) content += ` originRight [${ i . originRight }]` ; if ( showIsAfter ) content += ` ${ i . insertAfter ? 'after' : chalk . blue ( 'before' ) }` ; console . log ( `${ '| ' . repeat ( d ) }${ i . content == null ? chalk . grey ( content ) : content }` ) ; } } ; export const isInVersion = ( id , version ) => { if ( id == null ) return true ; const seq = version [ id [ 0 ] ] ; return seq != null && seq >= id [ 1 ] ; } ; export const canInsertNow = < T > ( op , doc ) : boolean => ( ! isInVersion ( op . id , doc . version ) && ( op . id [ 1 ] === 0 || isInVersion ( [ op . id [ 0 ] , op . id [ 1 ] - 1 ] , doc . version ) ) && isInVersion ( op . originLeft , doc . version ) && isInVersion ( op . originRight , doc . version ) ) ; export const mergeInto = < T > ( algorithm , dest , src ) => { const missing = src . content . filter ( op => op . content != null && ! isInVersion ( op . id , dest . version ) ) ; let remaining = missing . length ; while ( remaining > 0 ) { let mergedOnThisPass = 0 ; for ( let i = 0 ; i < missing . length ; i ++ ) { const op = missing [ i ] ; if ( op == null || ! canInsertNow ( op , dest ) ) continue ; algorithm . integrate ( dest , op ) ; missing [ i ] = null ; remaining -- ; mergedOnThisPass ++ ; } assert ( mergedOnThisPass ) ; } } ; const integrateYjsMod = < T > ( doc , newItem , idx_hint = - 1 ) => { const lastSeen = doc . version [ newItem . id [ 0 ] ] ?? - 1 ; if ( newItem . id [ 1 ] !== lastSeen + 1 ) throw Error ( 'Operations out of order' ) ; doc . version [ newItem . id [ 0 ] ] = newItem . id [ 1 ] ; let left = findItem ( doc , newItem . originLeft , idx_hint - 1 ) ; let destIdx = left + 1 ; let right = newItem . originRight == null ? doc . content . length : findItem ( doc , newItem . originRight , idx_hint ) ; let scanning = false ; for ( let i = destIdx ; ; i ++ ) { if ( ! scanning ) destIdx = i ; if ( i === doc . content . length ) break ; if ( i === right ) break ; let other = doc . content [ i ] ; let oleft = findItem ( doc , other . originLeft , idx_hint - 1 ) ; let oright = other . originRight == null ? doc . content . length : findItem ( doc , other . originRight , idx_hint ) ; if ( oleft < left ) { break ; } else if ( oleft === left ) { if ( oright < right ) { scanning = true ; continue ; } else if ( oright === right ) { if ( newItem . id [ 0 ] < other . id [ 0 ] ) break ; else { scanning = false ; continue ; } } else { scanning = false ; continue ; } } else { continue ; } } doc . content . splice ( destIdx , 0 , newItem ) ; if ( ! newItem . isDeleted ) doc . length += 1 ; } ; const integrateYjs = < T > ( doc , newItem , idx_hint = - 1 ) => { const lastSeen = doc . version [ newItem . id [ 0 ] ] ?? - 1 ; if ( newItem . id [ 1 ] !== lastSeen + 1 ) throw Error ( 'Operations out of order' ) ; doc . version [ newItem . id [ 0 ] ] = newItem . id [ 1 ] ; let left = findItem ( doc , newItem . originLeft , idx_hint - 1 ) ; let destIdx = left + 1 ; let right = newItem . originRight == null ? doc . content . length : findItem ( doc , newItem . originRight , idx_hint ) ; let scanning = false ; for ( let i = destIdx ; ; i ++ ) { if ( ! scanning ) destIdx = i ; if ( i === doc . content . length ) break ; if ( i === right ) break ; let other = doc . content [ i ] ; let oleft = findItem ( doc , other . originLeft , idx_hint - 1 ) ; let oright = other . originRight == null ? doc . content . length : findItem ( doc , other . originRight , idx_hint ) ; if ( oleft < left ) { break ; } else if ( oleft === left ) { if ( newItem . id [ 0 ] > other . id [ 0 ] ) { scanning = false ; continue ; } else if ( oright === right ) { break ; } else { scanning = true ; continue ; } } else { continue ; } } doc . content . splice ( destIdx , 0 , newItem ) ; if ( ! newItem . isDeleted ) doc . length += 1 ; } ; const integrateAutomerge = < T > ( doc , newItem , idx_hint = - 1 ) => { const { id } = newItem ; assert ( newItem . seq >= 0 ) ; const lastSeen = doc . version [ id [ 0 ] ] ?? - 1 ; if ( id [ 1 ] !== lastSeen + 1 ) throw Error ( 'Operations out of order' ) ; doc . version [ id [ 0 ] ] = id [ 1 ] ; let parent = findItem ( doc , newItem . originLeft , idx_hint - 1 ) ; let destIdx = parent + 1 ; for ( ; destIdx < doc . content . length ; destIdx ++ ) { let o = doc . content [ destIdx ] ; if ( newItem . seq > o . seq ) break ; let oparent = findItem ( doc , o . originLeft , idx_hint - 1 ) ; if ( oparent < parent ) { break ; } else if ( oparent === parent ) { if ( newItem . seq > o . seq ) { break ; } else if ( newItem . seq === o . seq ) { if ( id [ 0 ] < o . id [ 0 ] ) break ; else continue ; } else { continue ; } } else { continue ; } } if ( newItem . seq > doc . maxSeq ) doc . maxSeq = newItem . seq ; doc . content . splice ( destIdx , 0 , newItem ) ; if ( ! newItem . isDeleted ) doc . length += 1 ; } ; const integrateAutomergeSmol = < T > ( doc , newItem , idx_hint = - 1 ) => { const { id : [ agent , seq ] } = newItem ; const parent = findItem ( doc , newItem . originLeft , idx_hint - 1 ) ; let i ; for ( i = parent + 1 ; i < doc . content . length ; i ++ ) { let o = doc . content [ i ] ; if ( newItem . seq > o . seq ) break ; let oparent = findItem ( doc , o . originLeft , idx_hint - 1 ) ; if ( oparent < parent || ( oparent === parent && ( newItem . seq === o . seq ) && agent < o . id [ 0 ] ) ) break ; } doc . content . splice ( i , 0 , newItem ) ; doc . version [ agent ] = seq ; doc . maxSeq = Math . max ( doc . maxSeq , newItem . seq ) ; if ( ! newItem . isDeleted ) doc . length += 1 ; } ; const integrateSync9 = < T > ( doc , newItem , idx_hint = - 1 ) => { const { id : [ agent , seq ] } = newItem ; const lastSeen = doc . version [ agent ] ?? - 1 ; if ( seq !== lastSeen + 1 ) throw Error ( 'Operations out of order' ) ; doc . version [ agent ] = seq ; let parentIdx = findItem2 ( doc , newItem . originLeft , newItem . insertAfter , idx_hint - 1 ) ; let destIdx = parentIdx + 1 ; if ( parentIdx >= 0 && newItem . originLeft && ! newItem . insertAfter && doc . content [ parentIdx ] . content != null ) { doc . content . splice ( parentIdx , 0 , { ... doc . content [ parentIdx ] , content : null } ) ; } else { for ( ; destIdx < doc . content . length ; destIdx ++ ) { let other = doc . content [ destIdx ] ; let oparentIdx = findItem2 ( doc , other . originLeft , other . insertAfter , idx_hint - 1 ) ; if ( oparentIdx < parentIdx ) break ; else if ( oparentIdx === parentIdx ) { if ( newItem . id [ 0 ] < other . id [ 0 ] ) break ; else continue ; } else continue ; } } doc . content . splice ( destIdx , 0 , newItem ) ; if ( ! newItem . isDeleted && newItem . content != null ) doc . length += 1 ; } ; export const sync9 = { localInsert : localInsertSync9 , integrate : integrateSync9 , printDoc ( doc ) { printdoc ( doc , false , false , true ) ; } , } ; export const yjsMod = { localInsert , integrate : integrateYjsMod , printDoc ( doc ) { printdoc ( doc , false , true , false ) ; } , } ; export const yjs = { localInsert , integrate : integrateYjs , printDoc ( doc ) { printdoc ( doc , false , true , false ) ; } , ignoreTests : [ 'withTails2' ] } ; export const automerge = { localInsert , integrate : integrateAutomergeSmol , printDoc ( doc ) { printdoc ( doc , true , false , false ) ; } , ignoreTests : [ 'interleavingBackward' , 'interleavingBackward2' , 'withTails' , 'withTails2' ] } ; export const printDebugStats = ( ) => { console . log ( 'hits' , hits , 'misses' , misses ) ; } ;