import { List } from "immutable" ; import * as Char from "./char" ; import { Crdt , LocalChange } from "./crdt" ; export type t = List < List < Char . t > > ; function findNewline ( line ) { return line . findIndex ( char => char ! . value === "\n" ) ; } function updateCrdtRemove ( crdt , change ) { const lines = crdt . slice ( change . from . line , change . to . line + 1 ) ; const linesAndUpdates = lines . map ( ( line , index ) => { let startIndex ; let endIndex ; if ( index === 0 ) { startIndex = change . from . ch ; } else { startIndex = 0 ; } if ( index === lines . size - 1 ) { endIndex = change . to . ch ; } else { endIndex = line ! . size ; } const toRemove = line ! . slice ( startIndex , endIndex ) ; if ( toRemove . size !== endIndex - startIndex ) { throw new Error ( "size does not match" ) ; } const updatedLine = line ! . splice ( startIndex , endIndex - startIndex ) . toList ( ) ; return [ updatedLine , toRemove ] as [ List < Char . t > , List < Char . t > ] ; } ) ; const updatedLines = linesAndUpdates . map ( tuple => tuple ! [ 0 ] ) ; const toRemove = linesAndUpdates . flatMap ( tuple => tuple ! [ 1 ] ) ; let newCrdt ; if ( lines . size === 1 ) { newCrdt = crdt . set ( change . from . line , updatedLines . first ( ) ) ; } else { const remainingLine = updatedLines . first ( ) . concat ( updatedLines . last ( ) ) . toList ( ) ; newCrdt = crdt . splice ( change . from . line , lines . size , remainingLine ) . toList ( ) ; } return [ newCrdt , toRemove . toArray ( ) ] ; } function updateCrdtInsert ( crdt , lamport , site , change ) { const { line : lineIndex , ch } = change . from ; const line = crdt . get ( lineIndex ) ; const [ before , after ] = splitLineAt ( line , ch ) ; let previousChar = getPrecedingChar ( crdt , lineIndex , ch ) ; const nextChar = getCharAt ( crdt , lineIndex , ch ) ; let currentLine = before ; const lines = [ ] ; const addedChars = [ ] ; Array . from ( change . text ) . forEach ( addedChar => { const newPosition = Char . generatePositionBetween ( previousChar . position , nextChar . position , site ) ; const newChar = Char . create ( newPosition , lamport , addedChar ) ; currentLine = currentLine . push ( newChar ) ; if ( addedChar === "\n" ) { lines . push ( currentLine ) ; currentLine = List ( ) ; } addedChars . push ( newChar ) ; previousChar = newChar ; } ) ; currentLine = currentLine . concat ( after ) . toList ( ) ; lines . push ( currentLine ) ; const updatedCrdt = crdt . splice ( lineIndex , 1 , ... lines ) . toList ( ) ; return [ updatedCrdt , addedChars ] ; } function splitLineAt ( line , at ) { const before = line . slice ( 0 , at ) . toList ( ) ; const after = line . slice ( at , line . size ) . toList ( ) ; return [ before , after ] ; } function getPrecedingChar ( crdt , lineIndex , ch ) { if ( ch === 0 ) { if ( lineIndex === 0 ) { return Char . startOfFile ( ) ; } else { return crdt . get ( lineIndex - 1 ) . last ( ) ; } } else { return crdt . get ( lineIndex ) . get ( ch - 1 ) ; } } function getCharAt ( crdt , lineIndex , ch ) { const line = crdt . get ( lineIndex ) ; if ( ch >= line . size ) { if ( lineIndex === crdt . size - 1 && ch === line . size ) { return Char . endOfFile ( ) ; } else { throw Error ( "indexing out of bounds" ) ; } } else { return line . get ( ch ) ; } } function compareCharWithLine ( item , line ) { if ( line . size === 0 ) { return Char . compare ( item , Char . endOfFile ( ) ) ; } else { return Char . compare ( item , line . get ( 0 ) ) ; } } function findPosition ( crdt , char ) { const lineIndex = Math . max ( 0 , binarySearch ( crdt , char , compareCharWithLine , "before" ) ) ; const line = crdt . get ( lineIndex ) ; const charIndex = binarySearch ( line , char , Char . compare , "at" ) ; if ( charIndex < line . size ) { const found = Char . compare ( crdt . get ( lineIndex ) . get ( charIndex ) , char ) === 0 ; return [ lineIndex , charIndex , found ? "found" : "not_found" ] ; } else { const isAfterNewline = ( charIndex === line . size ) && ( lineIndex !== crdt . size - 1 ) ; if ( isAfterNewline ) { return [ lineIndex + 1 , 0 , "not_found" ] ; } else { return [ lineIndex , charIndex , "not_found" ] ; } } } export function binarySearch < U , V > ( list , item , comparator , notFoundBehavior ) { function _binarySearch < T > ( start , end ) { if ( start >= end ) { switch ( notFoundBehavior ) { case "at" : return start ; case "before" : return start - 1 ; default : throw new Error ( "Unknown behavior" ) ; } } else { const mid = Math . floor ( ( start + end ) / 2 ) ; const comp = comparator ( item , list . get ( mid ) ) ; if ( comp < 0 ) { return _binarySearch ( start , mid ) ; } else if ( comp > 0 ) { return _binarySearch ( mid + 1 , end ) ; } else { return mid ; } } } return _binarySearch ( 0 , list . size ) ; } export class LinearCrdt implements Crdt { private crdt : t ; public init ( init ) { let line = List ( ) ; let lines = List ( ) ; init . forEach ( serial => { const char = Char . ofArray ( serial ) ; if ( char . value === "\n" ) { line = line . push ( char ) ; lines = lines . push ( line ) ; line = List ( ) ; } else { line = line . push ( char ) ; } } ) ; this . crdt = lines . push ( line ) ; } public toString ( ) { return this . crdt . map ( line => line ! . map ( char => char ! . value ) . join ( "" ) ) . join ( "" ) ; } public remoteInsert ( char ) { const [ lineIndex , ch , found ] = findPosition ( this . crdt , char ) ; const line = this . crdt . get ( lineIndex ) ; if ( found === "not_found" ) { const change = LocalChange . create ( { line : lineIndex , ch } , { line : lineIndex , ch } , char . value ) ; if ( char . value === "\n" ) { const [ before , after ] = splitLineAt ( line , ch ) ; this . crdt = this . crdt . splice ( lineIndex , 1 , ... [ before . push ( char ) , after ] ) . toList ( ) ; return change ; } else { this . crdt = this . crdt . set ( lineIndex , line . insert ( ch , char ) ) ; return change ; } } else { return null ; } } public remoteDelete ( char ) { const [ lineIndex , ch , found ] = findPosition ( this . crdt , char ) ; const line = this . crdt . get ( lineIndex ) ; if ( found === "found" && Char . equals ( line . get ( ch ) , char ) ) { const newLine = line . remove ( ch ) ; const nextLine = this . crdt . get ( lineIndex + 1 ) ; if ( findNewline ( newLine ) < 0 && nextLine ) { const change = LocalChange . create ( { line : lineIndex , ch } , { line : lineIndex + 1 , ch : 0 } , "" ) ; this . crdt = this . crdt . splice ( lineIndex , 2 , newLine . concat ( nextLine ) ) . toList ( ) ; return change ; } else { const change = LocalChange . create ( { line : lineIndex , ch } , { line : lineIndex , ch : ch + 1 } , "" ) ; this . crdt = this . crdt . set ( lineIndex , newLine ) ; return change ; } } else { return null ; } } public localInsert ( lamport , site , change ) { const [ newCrdt , remoteChanges ] = updateCrdtInsert ( this . crdt , lamport , site , change ) ; this . crdt = newCrdt ; return remoteChanges ; } public localDelete ( change ) { const [ newCrdt , remoteChanges ] = updateCrdtRemove ( this . crdt , change ) ; this . crdt = newCrdt ; return remoteChanges ; } }