charCount(): number;

lineCount(): number;

isLeaf(): this is LineLeaf;

walk(rangeStart: number, rangeLength: number, walkFns: LineIndexWalker): void;

PreStart,

Start,

Entire,

Mid,

End,

PostEnd

goSubtree: boolean;

done: boolean;

leaf(relativeStart: number, relativeLength: number, lineCollection: LineLeaf): void;

pre?(relativeStart: number, relativeLength: number, lineCollection: LineCollection,

parent: LineNode, nodeType: CharRangeSection): void;

post?(relativeStart: number, relativeLength: number, lineCollection: LineCollection,

parent: LineNode, nodeType: CharRangeSection): void;

goSubtree = true;

get done() { return false; }

readonly lineIndex = new LineIndex();

// path to start of range

private readonly startPath: LineCollection[];

private readonly endBranch: LineCollection[] = [];

private branchNode: LineNode;

// path to current node

private readonly stack: LineNode[];

private state = CharRangeSection.Entire;

private lineCollectionAtBranch: LineCollection;

private initialText = "";

private trailingText = "";

constructor() {

this.lineIndex.root = new LineNode();

this.startPath = [this.lineIndex.root];

this.stack = [this.lineIndex.root];

}

insertLines(insertedText: string | undefined, suppressTrailingText: boolean) {

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) {

if (lines[lines.length - 1] === "") {

lines.pop();

}

}

let branchParent: LineNode | undefined;

let lastZeroCount: LineCollection | undefined;

for (let k = this.endBranch.length - 1; k >= 0; k--) {

(<LineNode>this.endBranch[k]).updateCounts();

if (this.endBranch[k].charCount() === 0) {

lastZeroCount = this.endBranch[k];

if (k > 0) {

branchParent = <LineNode>this.endBranch[k - 1];

}

else {

branchParent = this.branchNode;

}

}

}

if (lastZeroCount) {

branchParent!.remove(lastZeroCount);

}

// path at least length two (root and leaf)

const leafNode = <LineLeaf>this.startPath[this.startPath.length - 1];

if (lines.length > 0) {

leafNode.text = lines[0];

if (lines.length > 1) {

let insertedNodes = <LineCollection[]>new Array(lines.length - 1);

let startNode = <LineCollection>leafNode;

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 = <LineNode>this.startPath[pathIndex];

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--) {

(<LineNode>this.startPath[j]).updateCounts();

}

}

}

else {

const insertionNode = <LineNode>this.startPath[this.startPath.length - 2];

// no content for leaf node, so delete it

insertionNode.remove(leafNode);

for (let j = this.startPath.length - 2; j >= 0; j--) {

(<LineNode>this.startPath[j]).updateCounts();

}

}

return this.lineIndex;

}

post(_relativeStart: number, _relativeLength: number, lineCollection: LineCollection): void {

// have visited the path for start of range, now looking for end

// if range is on single line, we will never make this state transition

if (lineCollection === this.lineCollectionAtBranch) {

this.state = CharRangeSection.End;

}

// always pop stack because post only called when child has been visited

this.stack.pop();

}

pre(_relativeStart: number, _relativeLength: number, lineCollection: LineCollection, _parent: LineCollection, nodeType: CharRangeSection): void {

// currentNode corresponds to parent, but in the new tree

const currentNode = this.stack[this.stack.length - 1];

if ((this.state === CharRangeSection.Entire) && (nodeType === CharRangeSection.Start)) {

// if range is on single line, we will never make this state transition

this.state = CharRangeSection.Start;

this.branchNode = currentNode;

this.lineCollectionAtBranch = lineCollection;

}

let child: LineCollection | undefined;

function fresh(node: LineCollection): LineCollection {

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(<LineNode>child);

}

}

// just gather text from the leaves

leaf(relativeStart: number, relativeLength: number, ll: LineLeaf) {

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 {

// state is CharRangeSection.End

this.trailingText = ll.text.substring(relativeStart + relativeLength);

}

}

constructor(public pos: number, public deleteLen: number, public insertedText?: string) {

}

getTextChangeRange() {

return createTextChangeRange(createTextSpan(this.pos, this.deleteLen),

this.insertedText ? this.insertedText.length : 0);

}

private changes: TextChange[] = [];

private readonly versions: LineIndexSnapshot[] = new Array<LineIndexSnapshot>(ScriptVersionCache.maxVersions);

private minVersion = 0; // no versions earlier than min version will maintain change history

private currentVersion = 0;

private static readonly changeNumberThreshold = 8;

private static readonly changeLengthThreshold = 256;

private static readonly maxVersions = 8;

private versionToIndex(version: number) {

if (version < this.minVersion || version > this.currentVersion) {

return undefined;

}

return version % ScriptVersionCache.maxVersions;

}

private currentVersionToIndex() {

return this.currentVersion % ScriptVersionCache.maxVersions;

}

// REVIEW: can optimize by coalescing simple edits

edit(pos: number, deleteLen: number, insertedText?: string) {

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(): IScriptSnapshot { return this._getSnapshot(); }

private _getSnapshot(): LineIndexSnapshot {

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(): number {

return this._getSnapshot().version;

}

getLineInfo(line: number): AbsolutePositionAndLineText {

return this._getSnapshot().index.lineNumberToInfo(line);

}

lineOffsetToPosition(line: number, column: number): number {

return this._getSnapshot().index.absolutePositionOfStartOfLine(line) + (column - 1);

}

positionToLineOffset(position: number): protocol.Location {

return this._getSnapshot().index.positionToLineOffset(position);

}

lineToTextSpan(line: number): TextSpan {

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: number, newVersion: number) {

if (oldVersion < newVersion) {

if (oldVersion >= this.minVersion) {

const textChangeRanges: TextChangeRange[] = [];

for (let i = oldVersion + 1; i <= newVersion; i++) {

const snap = this.versions[this.versionToIndex(i)!]; // TODO: GH#18217

for (const textChange of snap.changesSincePreviousVersion) {

textChangeRanges.push(textChange.getTextChangeRange());

}

}

return collapseTextChangeRangesAcrossMultipleVersions(textChangeRanges);

}

else {

return undefined;

}

}

else {

return unchangedTextChangeRange;

}

}

static fromString(script: string) {

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;

}

constructor(readonly version: number, readonly cache: ScriptVersionCache, readonly index: LineIndex, readonly changesSincePreviousVersion: ReadonlyArray<TextChange> = emptyArray) {

}

getText(rangeStart: number, rangeEnd: number) {

return this.index.getText(rangeStart, rangeEnd - rangeStart);

}

getLength() {

return this.index.getLength();

}

getChangeRange(oldSnapshot: IScriptSnapshot): TextChangeRange | undefined {

if (oldSnapshot instanceof LineIndexSnapshot && this.cache === oldSnapshot.cache) {

if (this.version <= oldSnapshot.version) {

return unchangedTextChangeRange;

}

else {

return this.cache.getTextChangesBetweenVersions(oldSnapshot.version, this.version);

}

}

}

root: LineNode;

// set this to true to check each edit for accuracy

checkEdits = false;

absolutePositionOfStartOfLine(oneBasedLine: number): number {

return this.lineNumberToInfo(oneBasedLine).absolutePosition;

}

positionToLineOffset(position: number): protocol.Location {

const { oneBasedLine, zeroBasedColumn } = this.root.charOffsetToLineInfo(1, position);

return { line: oneBasedLine, offset: zeroBasedColumn + 1 };

}

private positionToColumnAndLineText(position: number): { zeroBasedColumn: number, lineText: string | undefined } {

return this.root.charOffsetToLineInfo(1, position);

}

lineNumberToInfo(oneBasedLine: number): AbsolutePositionAndLineText {

const lineCount = this.root.lineCount();

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: string[]) {

if (lines.length > 0) {

const leaves: LineLeaf[] = [];

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: number, rangeLength: number, walkFns: LineIndexWalker) {

this.root.walk(rangeStart, rangeLength, walkFns);

}

getText(rangeStart: number, rangeLength: number) {

let accum = "";

if ((rangeLength > 0) && (rangeStart < this.root.charCount())) {

this.walk(rangeStart, rangeLength, {

goSubtree: true,

done: false,

leaf: (relativeStart: number, relativeLength: number, ll: LineLeaf) => {

accum = accum.concat(ll.text.substring(relativeStart, relativeStart + relativeLength));

}

});

}

return accum;

}

getLength(): number {

return this.root.charCount();

}

every(f: (ll: LineLeaf, s: number, len: number) => boolean, rangeStart: number, rangeEnd?: number) {

if (!rangeEnd) {

rangeEnd = this.root.charCount();

}

const walkFns = {

goSubtree: true,

done: false,

leaf(this: LineIndexWalker, relativeStart: number, relativeLength: number, ll: LineLeaf) {

if (!f(ll, relativeStart, relativeLength)) {

this.done = true;

}

}

};

this.walk(rangeStart, rangeEnd - rangeStart, walkFns);

return !walkFns.done;

}

edit(pos: number, deleteLength: number, newText?: string): LineIndex {

if (this.root.charCount() === 0) {

Debug.assert(deleteLength === 0); // Can't delete from empty document

if (newText !== undefined) {

this.load(LineIndex.linesFromText(newText).lines);

return this;

}

return undefined!; // TODO: GH#18217

}

else {

let checkText: string | undefined;

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()) {

// insert at end

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) {

// check whether last characters deleted are line break

const e = pos + deleteLength;

const { zeroBasedColumn, lineText } = this.positionToColumnAndLineText(e);

if (zeroBasedColumn === 0) {

// move range end just past line that will merge with previous line

deleteLength += lineText!.length; // TODO: GH#18217

// store text by appending to end of insertedText

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: LineCollection[]): LineNode {

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: string) {

const lineMap = computeLineStarts(text);

if (lineMap.length === 0) {

return { lines: <string[]>[], lineMap };

}

const lines = <string[]>new Array(lineMap.length);

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 };

}

totalChars = 0;

totalLines = 0;

constructor(private readonly children: LineCollection[] = []) {

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: number, rangeLength: number, walkFns: LineIndexWalker, childIndex: number, nodeType: CharRangeSection) {

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: number, relativeLength: number, childIndex: number, walkFns: LineIndexWalker, nodeType: CharRangeSection) {

if (walkFns.pre && (!walkFns.done)) {

walkFns.pre(relativeStart, relativeLength, this.children[childIndex], this, nodeType);

walkFns.goSubtree = true;

}

}

walk(rangeStart: number, rangeLength: number, walkFns: LineIndexWalker) {

// assume (rangeStart < this.totalChars) && (rangeLength <= this.totalChars)

let childIndex = 0;

let childCharCount = this.children[childIndex].charCount();

// find sub-tree containing start

let adjustedStart = rangeStart;

while (adjustedStart >= childCharCount) {

this.skipChild(adjustedStart, rangeLength, childIndex, walkFns, CharRangeSection.PreStart);

adjustedStart -= childCharCount;

childIndex++;

childCharCount = this.children[childIndex].charCount();

}

// Case I: both start and end of range in same subtree

if ((adjustedStart + rangeLength) <= childCharCount) {

if (this.execWalk(adjustedStart, rangeLength, walkFns, childIndex, CharRangeSection.Entire)) {

return;

}

}

else {

// Case II: start and end of range in different subtrees (possibly with subtrees in the middle)

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;

}

}

}

// Process any subtrees after the one containing range end

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);

}

}

}

}

// Input position is relative to the start of this node.

// Output line number is absolute.

charOffsetToLineInfo(lineNumberAccumulator: number, relativePosition: number): { oneBasedLine: number, zeroBasedColumn: number, lineText: string | undefined } {

if (this.children.length === 0) {

// Root node might have no children if this is an empty document.

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 (<LineNode>child).charOffsetToLineInfo(lineNumberAccumulator, relativePosition);

}

}

else {

relativePosition -= child.charCount();

lineNumberAccumulator += child.lineCount();

}

}

// Skipped all children

const { leaf } = this.lineNumberToInfo(this.lineCount(), 0);

return { oneBasedLine: this.lineCount(), zeroBasedColumn: leaf ? leaf.charCount() : 0, lineText: undefined };

}

/**

lineNumberToInfo(relativeOneBasedLine: number, positionAccumulator: number): { position: number, leaf: LineLeaf | undefined } {

for (const child of this.children) {

const childLineCount = child.lineCount();

if (childLineCount >= relativeOneBasedLine) {

return child.isLeaf() ? { position: positionAccumulator, leaf: child } : (<LineNode>child).lineNumberToInfo(relativeOneBasedLine, positionAccumulator);

}

else {

relativeOneBasedLine -= childLineCount;

positionAccumulator += child.charCount();

}

}

return { position: positionAccumulator, leaf: undefined };

}

private splitAfter(childIndex: number) {

let splitNode: LineNode | undefined;

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: LineCollection) {

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: LineCollection) {

const childIndex = this.children.indexOf(child);

Debug.assert(childIndex !== -1);

return childIndex;

}

insertAt(child: LineCollection, nodes: LineCollection[]) {

let childIndex = this.findChildIndex(child);

const clen = this.children.length;

const nodeCount = nodes.length;

// if child is last and there is more room and only one node to place, place it

if ((clen < lineCollectionCapacity) && (childIndex === (clen - 1)) && (nodeCount === 1)) {

this.add(nodes[0]);

this.updateCounts();

return [];

}

else {

const shiftNode = this.splitAfter(childIndex);