namespace ts . server { const lineCollectionCapacity = 4 ; interface LineCollection { charCount ( ) : number ; lineCount ( ) : number ; isLeaf ( ) : this is LineLeaf ; walk ( rangeStart , rangeLength , walkFns ) : void ; } export interface AbsolutePositionAndLineText { absolutePosition : number ; lineText : string | undefined ; } const enum CharRangeSection { PreStart , Start , Entire , Mid , End , PostEnd } interface LineIndexWalker { goSubtree : boolean ; done : boolean ; leaf ( relativeStart , relativeLength , lineCollection ) : void ; pre ? ( relativeStart , relativeLength , lineCollection , parent , nodeType ) : void ; post ? ( relativeStart , relativeLength , lineCollection , parent , nodeType ) : void ; } class EditWalker implements LineIndexWalker { goSubtree = true ; get done ( ) { return false ; } readonly lineIndex = new LineIndex ( ) ; private readonly startPath : LineCollection [ ] ; private readonly endBranch : LineCollection [ ] = [ ] ; private branchNode : LineNode | undefined ; private readonly stack : LineNode [ ] ; private state = CharRangeSection . Entire ; private lineCollectionAtBranch : LineCollection | undefined ; private initialText = "" ; private trailingText = "" ; constructor ( ) { this . lineIndex . root = new LineNode ( ) ; this . startPath = [ this . lineIndex . root ] ; this . stack = [ this . lineIndex . root ] ; } insertLines ( insertedText , suppressTrailingText ) { if ( suppressTrailingText ) { this . trailingText = "" ; } if ( insertedText ) { insertedText = this . initialText + insertedText + this . trailingText ; } else { insertedText = this . initialText + this . trailingText ; } const lm = LineIndex . linesFromText ( insertedText ) ; const lines = lm . lines ; if ( lines . length > 1 && lines [ lines . length - 1 ] === "" ) { lines . pop ( ) ; } let branchParent ; let lastZeroCount ; for ( let k = this . endBranch . length - 1 ; k >= 0 ; k -- ) { ( this . endBranch [ k ] as LineNode ) . updateCounts ( ) ; if ( this . endBranch [ k ] . charCount ( ) === 0 ) { lastZeroCount = this . endBranch [ k ] ; if ( k > 0 ) { branchParent = this . endBranch [ k - 1 ] as LineNode ; } else { branchParent = this . branchNode ; } } } if ( lastZeroCount ) { branchParent ! . remove ( lastZeroCount ) ; } const leafNode = this . startPath [ this . startPath . length - 1 ] as LineLeaf ; if ( lines . length > 0 ) { leafNode . text = lines [ 0 ] ; if ( lines . length > 1 ) { let insertedNodes = new Array ( lines . length - 1 ) as LineCollection [ ] ; let startNode = leafNode as LineCollection ; for ( let i = 1 ; i < lines . length ; i ++ ) { insertedNodes [ i - 1 ] = new LineLeaf ( lines [ i ] ) ; } let pathIndex = this . startPath . length - 2 ; while ( pathIndex >= 0 ) { const insertionNode = this . startPath [ pathIndex ] as LineNode ; insertedNodes = insertionNode . insertAt ( startNode , insertedNodes ) ; pathIndex -- ; startNode = insertionNode ; } let insertedNodesLen = insertedNodes . length ; while ( insertedNodesLen > 0 ) { const newRoot = new LineNode ( ) ; newRoot . add ( this . lineIndex . root ) ; insertedNodes = newRoot . insertAt ( this . lineIndex . root , insertedNodes ) ; insertedNodesLen = insertedNodes . length ; this . lineIndex . root = newRoot ; } this . lineIndex . root . updateCounts ( ) ; } else { for ( let j = this . startPath . length - 2 ; j >= 0 ; j -- ) { ( this . startPath [ j ] as LineNode ) . updateCounts ( ) ; } } } else { const insertionNode = this . startPath [ this . startPath . length - 2 ] as LineNode ; insertionNode . remove ( leafNode ) ; for ( let j = this . startPath . length - 2 ; j >= 0 ; j -- ) { ( this . startPath [ j ] as LineNode ) . updateCounts ( ) ; } } return this . lineIndex ; } post ( _relativeStart , _relativeLength , lineCollection ) { if ( lineCollection === this . lineCollectionAtBranch ) { this . state = CharRangeSection . End ; } this . stack . pop ( ) ; } pre ( _relativeStart , _relativeLength , lineCollection , _parent , nodeType ) { const currentNode = this . stack [ this . stack . length - 1 ] ; if ( ( this . state === CharRangeSection . Entire ) && ( nodeType === CharRangeSection . Start ) ) { this . state = CharRangeSection . Start ; this . branchNode = currentNode ; this . lineCollectionAtBranch = lineCollection ; } let child ; function fresh ( node ) { if ( node . isLeaf ( ) ) { return new LineLeaf ( "" ) ; } else return new LineNode ( ) ; } switch ( nodeType ) { case CharRangeSection . PreStart : this . goSubtree = false ; if ( this . state !== CharRangeSection . End ) { currentNode . add ( lineCollection ) ; } break ; case CharRangeSection . Start : if ( this . state === CharRangeSection . End ) { this . goSubtree = false ; } else { child = fresh ( lineCollection ) ; currentNode . add ( child ) ; this . startPath . push ( child ) ; } break ; case CharRangeSection . Entire : if ( this . state !== CharRangeSection . End ) { child = fresh ( lineCollection ) ; currentNode . add ( child ) ; this . startPath . push ( child ) ; } else { if ( ! lineCollection . isLeaf ( ) ) { child = fresh ( lineCollection ) ; currentNode . add ( child ) ; this . endBranch . push ( child ) ; } } break ; case CharRangeSection . Mid : this . goSubtree = false ; break ; case CharRangeSection . End : if ( this . state !== CharRangeSection . End ) { this . goSubtree = false ; } else { if ( ! lineCollection . isLeaf ( ) ) { child = fresh ( lineCollection ) ; currentNode . add ( child ) ; this . endBranch . push ( child ) ; } } break ; case CharRangeSection . PostEnd : this . goSubtree = false ; if ( this . state !== CharRangeSection . Start ) { currentNode . add ( lineCollection ) ; } break ; } if ( this . goSubtree ) { this . stack . push ( child as LineNode ) ; } } leaf ( relativeStart , relativeLength , ll ) { if ( this . state === CharRangeSection . Start ) { this . initialText = ll . text . substring ( 0 , relativeStart ) ; } else if ( this . state === CharRangeSection . Entire ) { this . initialText = ll . text . substring ( 0 , relativeStart ) ; this . trailingText = ll . text . substring ( relativeStart + relativeLength ) ; } else { this . trailingText = ll . text . substring ( relativeStart + relativeLength ) ; } } } class TextChange { constructor ( public pos , public deleteLen , public insertedText ? ) { } getTextChangeRange ( ) { return createTextChangeRange ( createTextSpan ( this . pos , this . deleteLen ) , this . insertedText ? this . insertedText . length : 0 ) ; } } export class ScriptVersionCache { private changes : TextChange [ ] = [ ] ; private readonly versions : LineIndexSnapshot [ ] = new Array < LineIndexSnapshot > ( ScriptVersionCache . maxVersions ) ; private minVersion = 0 ; private currentVersion = 0 ; private static readonly changeNumberThreshold = 8 ; private static readonly changeLengthThreshold = 256 ; private static readonly maxVersions = 8 ; private versionToIndex ( version ) { if ( version < this . minVersion || version > this . currentVersion ) { return undefined ; } return version % ScriptVersionCache . maxVersions ; } private currentVersionToIndex ( ) { return this . currentVersion % ScriptVersionCache . maxVersions ; } edit ( pos , deleteLen , insertedText ? ) { this . changes . push ( new TextChange ( pos , deleteLen , insertedText ) ) ; if ( this . changes . length > ScriptVersionCache . changeNumberThreshold || deleteLen > ScriptVersionCache . changeLengthThreshold || insertedText && insertedText . length > ScriptVersionCache . changeLengthThreshold ) { this . getSnapshot ( ) ; } } getSnapshot ( ) { return this . _getSnapshot ( ) ; } private _getSnapshot ( ) { let snap = this . versions [ this . currentVersionToIndex ( ) ] ; if ( this . changes . length > 0 ) { let snapIndex = snap . index ; for ( const change of this . changes ) { snapIndex = snapIndex . edit ( change . pos , change . deleteLen , change . insertedText ) ; } snap = new LineIndexSnapshot ( this . currentVersion + 1 , this , snapIndex , this . changes ) ; this . currentVersion = snap . version ; this . versions [ this . currentVersionToIndex ( ) ] = snap ; this . changes = [ ] ; if ( ( this . currentVersion - this . minVersion ) >= ScriptVersionCache . maxVersions ) { this . minVersion = ( this . currentVersion - ScriptVersionCache . maxVersions ) + 1 ; } } return snap ; } getSnapshotVersion ( ) { return this . _getSnapshot ( ) . version ; } getAbsolutePositionAndLineText ( oneBasedLine ) { return this . _getSnapshot ( ) . index . lineNumberToInfo ( oneBasedLine ) ; } lineOffsetToPosition ( line , column ) { return this . _getSnapshot ( ) . index . absolutePositionOfStartOfLine ( line ) + ( column - 1 ) ; } positionToLineOffset ( position ) { return this . _getSnapshot ( ) . index . positionToLineOffset ( position ) ; } lineToTextSpan ( line ) { const index = this . _getSnapshot ( ) . index ; const { lineText , absolutePosition } = index . lineNumberToInfo ( line + 1 ) ; const len = lineText !== undefined ? lineText . length : index . absolutePositionOfStartOfLine ( line + 2 ) - absolutePosition ; return createTextSpan ( absolutePosition , len ) ; } getTextChangesBetweenVersions ( oldVersion , newVersion ) { if ( oldVersion < newVersion ) { if ( oldVersion >= this . minVersion ) { const textChangeRanges = [ ] ; for ( let i = oldVersion + 1 ; i <= newVersion ; i ++ ) { const snap = this . versions [ this . versionToIndex ( i ) ! ] ; for ( const textChange of snap . changesSincePreviousVersion ) { textChangeRanges . push ( textChange . getTextChangeRange ( ) ) ; } } return collapseTextChangeRangesAcrossMultipleVersions ( textChangeRanges ) ; } else { return undefined ; } } else { return unchangedTextChangeRange ; } } getLineCount ( ) { return this . _getSnapshot ( ) . index . getLineCount ( ) ; } static fromString ( script ) { const svc = new ScriptVersionCache ( ) ; const snap = new LineIndexSnapshot ( 0 , svc , new LineIndex ( ) ) ; svc . versions [ svc . currentVersion ] = snap ; const lm = LineIndex . linesFromText ( script ) ; snap . index . load ( lm . lines ) ; return svc ; } } class LineIndexSnapshot implements IScriptSnapshot { constructor ( readonly version , readonly cache , readonly index , readonly changesSincePreviousVersion = emptyArray ) { } getText ( rangeStart , rangeEnd ) { return this . index . getText ( rangeStart , rangeEnd - rangeStart ) ; } getLength ( ) { return this . index . getLength ( ) ; } getChangeRange ( oldSnapshot ) { if ( oldSnapshot instanceof LineIndexSnapshot && this . cache === oldSnapshot . cache ) { if ( this . version <= oldSnapshot . version ) { return unchangedTextChangeRange ; } else { return this . cache . getTextChangesBetweenVersions ( oldSnapshot . version , this . version ) ; } } } } export class LineIndex { root ! : LineNode ; checkEdits = false ; absolutePositionOfStartOfLine ( oneBasedLine ) { return this . lineNumberToInfo ( oneBasedLine ) . absolutePosition ; } positionToLineOffset ( position ) { const { oneBasedLine , zeroBasedColumn } = this . root . charOffsetToLineInfo ( 1 , position ) ; return { line : oneBasedLine , offset : zeroBasedColumn + 1 } ; } private positionToColumnAndLineText ( position ) { return this . root . charOffsetToLineInfo ( 1 , position ) ; } getLineCount ( ) { return this . root . lineCount ( ) ; } lineNumberToInfo ( oneBasedLine ) { const lineCount = this . getLineCount ( ) ; if ( oneBasedLine <= lineCount ) { const { position , leaf } = this . root . lineNumberToInfo ( oneBasedLine , 0 ) ; return { absolutePosition : position , lineText : leaf && leaf . text } ; } else { return { absolutePosition : this . root . charCount ( ) , lineText : undefined } ; } } load ( lines ) { if ( lines . length > 0 ) { const leaves = [ ] ; for ( let i = 0 ; i < lines . length ; i ++ ) { leaves [ i ] = new LineLeaf ( lines [ i ] ) ; } this . root = LineIndex . buildTreeFromBottom ( leaves ) ; } else { this . root = new LineNode ( ) ; } } walk ( rangeStart , rangeLength , walkFns ) { this . root . walk ( rangeStart , rangeLength , walkFns ) ; } getText ( rangeStart , rangeLength ) { let accum = "" ; if ( ( rangeLength > 0 ) && ( rangeStart < this . root . charCount ( ) ) ) { this . walk ( rangeStart , rangeLength , { goSubtree : true , done : false , leaf : ( relativeStart , relativeLength , ll ) => { accum = accum . concat ( ll . text . substring ( relativeStart , relativeStart + relativeLength ) ) ; } } ) ; } return accum ; } getLength ( ) { return this . root . charCount ( ) ; } every ( f , rangeStart , rangeEnd ? ) { if ( ! rangeEnd ) { rangeEnd = this . root . charCount ( ) ; } const walkFns = { goSubtree : true , done : false , leaf ( this , relativeStart , relativeLength , ll ) { if ( ! f ( ll , relativeStart , relativeLength ) ) { this . done = true ; } } } ; this . walk ( rangeStart , rangeEnd - rangeStart , walkFns ) ; return ! walkFns . done ; } edit ( pos , deleteLength , newText ? ) { if ( this . root . charCount ( ) === 0 ) { Debug . assert ( deleteLength === 0 ) ; if ( newText !== undefined ) { this . load ( LineIndex . linesFromText ( newText ) . lines ) ; return this ; } return undefined ! ; } else { let checkText ; if ( this . checkEdits ) { const source = this . getText ( 0 , this . root . charCount ( ) ) ; checkText = source . slice ( 0 , pos ) + newText + source . slice ( pos + deleteLength ) ; } const walker = new EditWalker ( ) ; let suppressTrailingText = false ; if ( pos >= this . root . charCount ( ) ) { pos = this . root . charCount ( ) - 1 ; const endString = this . getText ( pos , 1 ) ; if ( newText ) { newText = endString + newText ; } else { newText = endString ; } deleteLength = 0 ; suppressTrailingText = true ; } else if ( deleteLength > 0 ) { const e = pos + deleteLength ; const { zeroBasedColumn , lineText } = this . positionToColumnAndLineText ( e ) ; if ( zeroBasedColumn === 0 ) { deleteLength += lineText ! . length ; newText = newText ? newText + lineText : lineText ; } } this . root . walk ( pos , deleteLength , walker ) ; walker . insertLines ( newText , suppressTrailingText ) ; if ( this . checkEdits ) { const updatedText = walker . lineIndex . getText ( 0 , walker . lineIndex . getLength ( ) ) ; Debug . assert ( checkText === updatedText , "buffer edit mismatch" ) ; } return walker . lineIndex ; } } private static buildTreeFromBottom ( nodes ) { if ( nodes . length < lineCollectionCapacity ) { return new LineNode ( nodes ) ; } const interiorNodes = new Array < LineNode > ( Math . ceil ( nodes . length / lineCollectionCapacity ) ) ; let nodeIndex = 0 ; for ( let i = 0 ; i < interiorNodes . length ; i ++ ) { const end = Math . min ( nodeIndex + lineCollectionCapacity , nodes . length ) ; interiorNodes [ i ] = new LineNode ( nodes . slice ( nodeIndex , end ) ) ; nodeIndex = end ; } return this . buildTreeFromBottom ( interiorNodes ) ; } static linesFromText ( text ) { const lineMap = computeLineStarts ( text ) ; if ( lineMap . length === 0 ) { return { lines : [ ] as string [ ] , lineMap } ; } const lines = new Array ( lineMap . length ) as string [ ] ; const lc = lineMap . length - 1 ; for ( let lmi = 0 ; lmi < lc ; lmi ++ ) { lines [ lmi ] = text . substring ( lineMap [ lmi ] , lineMap [ lmi + 1 ] ) ; } const endText = text . substring ( lineMap [ lc ] ) ; if ( endText . length > 0 ) { lines [ lc ] = endText ; } else { lines . pop ( ) ; } return { lines , lineMap } ; } } class LineNode implements LineCollection { totalChars = 0 ; totalLines = 0 ; constructor ( private readonly children = [ ] ) { if ( children . length ) this . updateCounts ( ) ; } isLeaf ( ) { return false ; } updateCounts ( ) { this . totalChars = 0 ; this . totalLines = 0 ; for ( const child of this . children ) { this . totalChars += child . charCount ( ) ; this . totalLines += child . lineCount ( ) ; } } private execWalk ( rangeStart , rangeLength , walkFns , childIndex , nodeType ) { if ( walkFns . pre ) { walkFns . pre ( rangeStart , rangeLength , this . children [ childIndex ] , this , nodeType ) ; } if ( walkFns . goSubtree ) { this . children [ childIndex ] . walk ( rangeStart , rangeLength , walkFns ) ; if ( walkFns . post ) { walkFns . post ( rangeStart , rangeLength , this . children [ childIndex ] , this , nodeType ) ; } } else { walkFns . goSubtree = true ; } return walkFns . done ; } private skipChild ( relativeStart , relativeLength , childIndex , walkFns , nodeType ) { if ( walkFns . pre && ( ! walkFns . done ) ) { walkFns . pre ( relativeStart , relativeLength , this . children [ childIndex ] , this , nodeType ) ; walkFns . goSubtree = true ; } } walk ( rangeStart , rangeLength , walkFns ) { let childIndex = 0 ; let childCharCount = this . children [ childIndex ] . charCount ( ) ; let adjustedStart = rangeStart ; while ( adjustedStart >= childCharCount ) { this . skipChild ( adjustedStart , rangeLength , childIndex , walkFns , CharRangeSection . PreStart ) ; adjustedStart -= childCharCount ; childIndex ++ ; childCharCount = this . children [ childIndex ] . charCount ( ) ; } if ( ( adjustedStart + rangeLength ) <= childCharCount ) { if ( this . execWalk ( adjustedStart , rangeLength , walkFns , childIndex , CharRangeSection . Entire ) ) { return ; } } else { if ( this . execWalk ( adjustedStart , childCharCount - adjustedStart , walkFns , childIndex , CharRangeSection . Start ) ) { return ; } let adjustedLength = rangeLength - ( childCharCount - adjustedStart ) ; childIndex ++ ; const child = this . children [ childIndex ] ; childCharCount = child . charCount ( ) ; while ( adjustedLength > childCharCount ) { if ( this . execWalk ( 0 , childCharCount , walkFns , childIndex , CharRangeSection . Mid ) ) { return ; } adjustedLength -= childCharCount ; childIndex ++ ; childCharCount = this . children [ childIndex ] . charCount ( ) ; } if ( adjustedLength > 0 ) { if ( this . execWalk ( 0 , adjustedLength , walkFns , childIndex , CharRangeSection . End ) ) { return ; } } } if ( walkFns . pre ) { const clen = this . children . length ; if ( childIndex < ( clen - 1 ) ) { for ( let ej = childIndex + 1 ; ej < clen ; ej ++ ) { this . skipChild ( 0 , 0 , ej , walkFns , CharRangeSection . PostEnd ) ; } } } } charOffsetToLineInfo ( lineNumberAccumulator , relativePosition ) { if ( this . children . length === 0 ) { return { oneBasedLine : lineNumberAccumulator , zeroBasedColumn : relativePosition , lineText : undefined } ; } for ( const child of this . children ) { if ( child . charCount ( ) > relativePosition ) { if ( child . isLeaf ( ) ) { return { oneBasedLine : lineNumberAccumulator , zeroBasedColumn : relativePosition , lineText : child . text } ; } else { return ( child as LineNode ) . charOffsetToLineInfo ( lineNumberAccumulator , relativePosition ) ; } } else { relativePosition -= child . charCount ( ) ; lineNumberAccumulator += child . lineCount ( ) ; } } const lineCount = this . lineCount ( ) ; if ( lineCount === 0 ) { return { oneBasedLine : 1 , zeroBasedColumn : 0 , lineText : undefined } ; } const leaf = Debug . checkDefined ( this . lineNumberToInfo ( lineCount , 0 ) . leaf ) ; return { oneBasedLine : lineCount , zeroBasedColumn : leaf . charCount ( ) , lineText : undefined } ; } /**
         * Input line number is relative to the start of this node.
         * Output line number is relative to the child.
         * positionAccumulator will be an absolute position once relativeLineNumber reaches 0.
         */ lineNumberToInfo ( relativeOneBasedLine , positionAccumulator ) { for ( const child of this . children ) { const childLineCount = child . lineCount ( ) ; if ( childLineCount >= relativeOneBasedLine ) { return child . isLeaf ( ) ? { position : positionAccumulator , leaf : child } : ( child as LineNode ) . lineNumberToInfo ( relativeOneBasedLine , positionAccumulator ) ; } else { relativeOneBasedLine -= childLineCount ; positionAccumulator += child . charCount ( ) ; } } return { position : positionAccumulator , leaf : undefined } ; } private splitAfter ( childIndex ) { let splitNode ; const clen = this . children . length ; childIndex ++ ; const endLength = childIndex ; if ( childIndex < clen ) { splitNode = new LineNode ( ) ; while ( childIndex < clen ) { splitNode . add ( this . children [ childIndex ] ) ; childIndex ++ ; } splitNode . updateCounts ( ) ; } this . children . length = endLength ; return splitNode ; } remove ( child ) { const childIndex = this . findChildIndex ( child ) ; const clen = this . children . length ; if ( childIndex < ( clen - 1 ) ) { for ( let i = childIndex ; i < ( clen - 1 ) ; i ++ ) { this . children [ i ] = this . children [ i + 1 ] ; } } this . children . pop ( ) ; } private findChildIndex ( child ) { const childIndex = this . children . indexOf ( child ) ; Debug . assert ( childIndex !== - 1 ) ; return childIndex ; } insertAt ( child , nodes ) { let childIndex = this . findChildIndex ( child ) ; const clen = this . children . length ; const nodeCount = nodes . length ; if ( ( clen < lineCollectionCapacity ) && ( childIndex === ( clen - 1 ) ) && ( nodeCount === 1 ) ) { this . add ( nodes [ 0 ] ) ; this . updateCounts ( ) ; return [ ] ; } else { const shiftNode = this . splitAfter ( childIndex ) ; let nodeIndex = 0 ; childIndex ++ ; while ( ( childIndex < lineCollectionCapacity ) && ( nodeIndex < nodeCount ) ) { this . children [ childIndex ] = nodes [ nodeIndex ] ; childIndex ++ ; nodeIndex ++ ; } let splitNodes = [ ] ; let splitNodeCount = 0 ; if ( nodeIndex < nodeCount ) { splitNodeCount = Math . ceil ( ( nodeCount - nodeIndex ) / lineCollectionCapacity ) ; splitNodes = new Array ( splitNodeCount ) as LineNode [ ] ; let splitNodeIndex = 0 ; for ( let i = 0 ; i < splitNodeCount ; i ++ ) { splitNodes [ i ] = new LineNode ( ) ; } let splitNode = splitNodes [ 0 ] ; while ( nodeIndex < nodeCount ) { splitNode . add ( nodes [ nodeIndex ] ) ; nodeIndex ++ ; if ( splitNode . children . length === lineCollectionCapacity ) { splitNodeIndex ++ ; splitNode = splitNodes [ splitNodeIndex ] ; } } for ( let i = splitNodes . length - 1 ; i >= 0 ; i -- ) { if ( splitNodes [ i ] . children . length === 0 ) { splitNodes . pop ( ) ; } } } if ( shiftNode ) { splitNodes . push ( shiftNode ) ; } this . updateCounts ( ) ; for ( let i = 0 ; i < splitNodeCount ; i ++ ) { splitNodes [ i ] . updateCounts ( ) ; } return splitNodes ; } } add ( collection ) { this . children . push ( collection ) ; Debug . assert ( this . children . length <= lineCollectionCapacity ) ; } charCount ( ) { return this . totalChars ; } lineCount ( ) { return this . totalLines ; } } class LineLeaf implements LineCollection { constructor ( public text ) { } isLeaf ( ) { return true ; } walk ( rangeStart , rangeLength , walkFns ) { walkFns . leaf ( rangeStart , rangeLength , this ) ; } charCount ( ) { return this . text . length ; } lineCount ( ) { return 1 ; } } }