///
///
///
namespace ts.server {
const lineCollectionCapacity = 4;
interface LineCollection {
charCount(): number;
lineCount(): number;
isLeaf(): this is LineLeaf;
walk(rangeStart: number, rangeLength: number, walkFns: ILineIndexWalker): void;
}
export interface AbsolutePositionAndLineText {
absolutePosition: number;
lineText: string | undefined;
}
const enum CharRangeSection {
PreStart,
Start,
Entire,
Mid,
End,
PostEnd
}
interface ILineIndexWalker {
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;
}
class EditWalker implements ILineIndexWalker {
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, 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;
let lastZeroCount: LineCollection;
for (let k = this.endBranch.length - 1; k >= 0; k--) {
(this.endBranch[k]).updateCounts();
if (this.endBranch[k].charCount() === 0) {
lastZeroCount = this.endBranch[k];
if (k > 0) {
branchParent = this.endBranch[k - 1];
}
else {
branchParent = this.branchNode;
}
}
}
if (lastZeroCount) {
branchParent.remove(lastZeroCount);
}
// path at least length two (root and leaf)
const leafNode = this.startPath[this.startPath.length - 1];
if (lines.length > 0) {
leafNode.text = lines[0];
if (lines.length > 1) {
let insertedNodes = new Array(lines.length - 1);
let startNode = leafNode;
for (let i = 1; i = 0) {
const insertionNode = 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--) {
(this.startPath[j]).updateCounts();
}
}
}
else {
const insertionNode = 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--) {
(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;
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(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);
}
}
}
// text change information
class TextChange {
constructor(public pos: number, public deleteLen: number, public insertedText?: string) {
}
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(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.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();
}
}
// reload whole script, leaving no change history behind reload
reload(script: string) {
this.currentVersion++;
this.changes = []; // history wiped out by reload
const snap = new LineIndexSnapshot(this.currentVersion, this, new LineIndex());
// delete all versions
for (let i = 0; i 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 = this.minVersion) {
const textChangeRanges: TextChangeRange[] = [];
for (let i = oldVersion + 1; i = emptyArray) {
}
getText(rangeStart: number, rangeEnd: number) {
return this.index.getText(rangeStart, rangeEnd - rangeStart);
}
getLength() {
return this.index.root.charCount();
}
getChangeRange(oldSnapshot: IScriptSnapshot): TextChangeRange {
if (oldSnapshot instanceof LineIndexSnapshot && this.cache === oldSnapshot.cache) {
if (this.version 0) {
const leaves: LineLeaf[] = [];
for (let i = 0; i 0) && (rangeStart {
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: ILineIndexWalker, 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;
}
}
else {
let checkText: string;
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;
// 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 (Math.ceil(nodes.length / lineCollectionCapacity));
let nodeIndex = 0;
for (let i = 0; i [], lineMap };
}
const lines = new Array(lineMap.length);
const lc = lineMap.length - 1;
for (let lmi = 0; lmi 0) {
lines[lc] = endText;
}
else {
lines.pop();
}
return { lines, lineMap };
}
}
class LineNode implements LineCollection {
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: ILineIndexWalker, 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: ILineIndexWalker, 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: ILineIndexWalker) {
// assume (rangeStart = 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(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 relativePosition) {
if (child.isLeaf()) {
return { oneBasedLine: lineNumberAccumulator, zeroBasedColumn: relativePosition, lineText: child.text };
}
else {
return (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.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: 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 } : (child).lineNumberToInfo(relativeOneBasedLine, positionAccumulator);
}
else {
relativeOneBasedLine -= childLineCount;
positionAccumulator += child.charCount();
}
}
return { position: positionAccumulator, leaf: undefined };
}
private splitAfter(childIndex: number) {
let splitNode: LineNode;
const clen = this.children.length;
childIndex++;
const endLength = childIndex;
if (childIndex new Array(splitNodeCount);
let splitNodeIndex = 0;
for (let i = 0; i splitNodes[0];
while (nodeIndex 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 splitNodes[i]).updateCounts();
}
return splitNodes;
}
}
// assume there is room for the item; return true if more room
add(collection: LineCollection): void {
this.children.push(collection);
Debug.assert(this.children.length