Vihren Atlas

intervalTree.ts ×7

Code frontier

unlabeled · c_f6c6baed5e08

340 tests · 41073 LOC · 238 files · introduces 0 tests · 186 LOC · 7 files

Introduces — evidence that enters the hierarchy at this concept

Code
26 ranges186 lines · 7 files
Tests
0 tests

Contains — complete concept membership

All code (extent)
5028 ranges41073 lines · 238 files · Browse complete extent
All tests (intent)
340 testsBrowse complete intent

Neighbourhood graph

The orange circle is the focus. Violet and green circles are every ancestor and descendant, broader and narrower, at any distance; blue squares and pink diamonds are the introduced files and exact introduced tests of every visible concept, not only the focus's. Arrows point from broader to narrower concepts and bridge only concepts omitted from this view. Undirected links show source or test introduction. Concept and file size follows LOC; exact test nodes use test-count units.

Introduced files, introduced tests, and structurally relevant concept specialization

In the embedded map, ordinary wheel input scrolls the page; use the visible controls to zoom and drag to pan. Open the full-screen map for canvas navigation: wheel pans, Ctrl/Command plus wheel zooms, and arrow keys pan when this region is focused. On touch screens, open the full-screen map to pan or pinch. If JavaScript or WebGL is unavailable, use the native relationship evidence on this page.

Graph controls are ready.

Interactive rendering requires JavaScript and WebGL. Use the native relationship evidence on this page while the interactive map is unavailable.

Native relationship evidence

Every exact file and test below is linked only from the concept that introduces it.

Introduced tests

Every collected test enters the hierarchy at exactly one concept.

No tests are introduced at this concept. Its intent tests are introduced by other concepts.

Introduced code

Every collected source range enters the hierarchy at exactly one concept.

7 files ranked by introduced lines: 186 introduced LOC across 26 ranges. Expand a file to inspect source; the > gutter marks introduced lines.

src/vs/editor/common/model/textModel.ts 84 introduced LOC · 7 ranges

Open complete file

1511
1512 if (contentChanges.length !== 0) {
1513 > // We do a first pass to update decorations textModel.ts
1514 > // because we want to read decorations in the second pass
1515 > // where we will emit content change events
1516 > // and we want to read the final decorations
1517 > for (let i = 0, len = contentChanges.length; i < len; i++) {
1518 > const change = contentChanges[i];
1519 > this._decorationsTree.acceptReplace(change.rangeOffset, change.rangeLength, change.text.length, change.forceMoveMarkers);
1520 > }
1521 >
1522 > const rawContentChanges: ModelRawChange[] = [];
1523 >
1524 > this._increaseVersionId();
1525 >
1526 > let lineCount = oldLineCount;
1527 > for (let i = 0, len = contentChanges.length; i < len; i++) {
1528 > const change = contentChanges[i];
1529 > const [eolCount] = countEOL(change.text);
1530 > this._onDidChangeDecorations.fire();
1531 >
1532 > const startLineNumber = change.range.startLineNumber;
1533 > const endLineNumber = change.range.endLineNumber;
1534 >
1535 > const deletingLinesCnt = endLineNumber - startLineNumber;
1536 > const insertingLinesCnt = eolCount;
1537 > const editingLinesCnt = Math.min(deletingLinesCnt, insertingLinesCnt);
1538 >
1539 > const changeLineCountDelta = (insertingLinesCnt - deletingLinesCnt);
1540 >
1541 > const currentEditStartLineNumber = newLineCount - lineCount - changeLineCountDelta + startLineNumber;
1542 >
1543 > for (let j = editingLinesCnt; j >= 0; j--) {
1544 > const editLineNumber = startLineNumber + j;
1545 > const currentEditLineNumber = currentEditStartLineNumber + j;
1546 >
1547 > rawContentChanges.push(
1548 > new ModelRawLineChanged(
1549 > editLineNumber,
1550 > currentEditLineNumber
1551 > ));
1552 > }
1553 >
1554 > if (editingLinesCnt < deletingLinesCnt) {
1555 // Must delete some lines
1556 const spliceStartLineNumber = startLineNumber + editingLinesCnt;
1559 rawContentChanges.push(new ModelRawLinesDeleted(spliceStartLineNumber + 1, endLineNumber, lastUntouchedLinePostEdit));
1560 }
1561 > textModel.ts
1562 > if (editingLinesCnt < insertingLinesCnt) {
1563 // Must insert some lines
1564 const spliceLineNumber = startLineNumber + editingLinesCnt;
1573 );
1574 }
1575 > textModel.ts
1576 > lineCount += changeLineCountDelta;
1577 > }
1578 >
1579 > this._emitContentChangedEvent(
1580 > new ModelRawContentChangedEvent(
1581 > rawContentChanges,
1582 > this.getVersionId(),
1583 > this._isUndoing,
1584 > this._isRedoing
1585 > ),
1586 > {
1587 > changes: contentChanges,
1588 > eol: this._buffer.getEOL(),
1589 > isEolChange: false,
1590 > versionId: this.getVersionId(),
1591 > isUndoing: this._isUndoing,
1592 > isRedoing: this._isRedoing,
1593 > isFlush: false,
1594 > detailedReasons: [reason],
1595 > detailedReasonsChangeLengths: [contentChanges.length],
1596 > },
1597 > resultingSelection
1598 > );
1599 > }
1600
1601 return (result.reverseEdits === null ? undefined : result.reverseEdits);
2347
2348 public acceptReplace(offset: number, length: number, textLength: number, forceMoveMarkers: boolean): void {
2349 > this._decorationsTree0.acceptReplace(offset, length, textLength, forceMoveMarkers); textModel.ts
2350 > this._decorationsTree1.acceptReplace(offset, length, textLength, forceMoveMarkers);
2351 > this._injectedTextDecorationsTree.acceptReplace(offset, length, textLength, forceMoveMarkers);
2352 > }
2353 }
2354
2722 if (this._deferredCnt === 0) {
2723 if (this._deferredEvent !== null) {
2724 > this._deferredEvent.rawContentChangedEvent.resultingSelection = resultingSelection; textModel.ts
2725 > const e = this._deferredEvent;
2726 > this._deferredEvent = null;
2727 > this._emitter.fire(e);
2728 > }
2729 }
2730 }
2732 public fire(e: InternalModelContentChangeEvent): void {
2733 if (this._deferredCnt > 0) {
2734 > if (this._deferredEvent) { textModel.ts
2735 this._deferredEvent = this._deferredEvent.merge(e);
2736 > } else { textModel.ts
2737 > this._deferredEvent = e;
2738 > }
2739 > return;
2740 > }
2741 this._emitter.fire(e);
2742 }
src/vs/editor/common/model/intervalTree.ts 53 introduced LOC · 7 ranges

Open complete file

305
306 public acceptReplace(offset: number, length: number, textLength: number, forceMoveMarkers: boolean): void {
307 > // Our strategy is to remove all directly impacted nodes, and then add them back to the tree. intervalTree.ts
308 >
309 > // (1) collect all nodes that are intersecting this edit as nodes of interest
310 > const nodesOfInterest = searchForEditing(this, offset, offset + length);
311 >
312 > // (2) remove all nodes that are intersecting this edit
313 > for (let i = 0, len = nodesOfInterest.length; i < len; i++) {
314 const node = nodesOfInterest[i];
315 rbTreeDelete(this, node);
316 }
317 > this._normalizeDeltaIfNecessary(); intervalTree.ts
318 >
319 > // (3) edit all tree nodes except the nodes of interest
320 > noOverlapReplace(this, offset, offset + length, textLength);
321 > this._normalizeDeltaIfNecessary();
322 >
323 > // (4) edit the nodes of interest and insert them back in the tree
324 > for (let i = 0, len = nodesOfInterest.length; i < len; i++) {
325 const node = nodesOfInterest[i];
326 node.start = node.cachedAbsoluteStart;
330 rbTreeInsert(this, node);
331 }
332 > this._normalizeDeltaIfNecessary(); intervalTree.ts
333 > }
334
335 public getAllInOrder(): IntervalNode[] {
490 }
491
492 > function searchForEditing(T: IntervalTree, start: number, end: number): IntervalNode[] { intervalTree.ts
493 > // https://en.wikipedia.org/wiki/Interval_tree#Augmented_tree
494 > // Now, it is known that two intervals A and B overlap only when both
495 > // A.low <= B.high and A.high >= B.low. When searching the trees for
496 > // nodes overlapping with a given interval, you can immediately skip:
497 > // a) all nodes to the right of nodes whose low value is past the end of the given interval.
498 > // b) all nodes that have their maximum 'high' value below the start of the given interval.
499 > let node = T.root;
500 > let delta = 0;
501 > let nodeMaxEnd = 0;
502 > let nodeStart = 0;
503 > let nodeEnd = 0;
504 > const result: IntervalNode[] = [];
505 > let resultLen = 0;
506 > while (node !== SENTINEL) {
507 if (getNodeIsVisited(node)) {
508 // going up from this node
556 }
557 }
558 > intervalTree.ts
559 > setNodeIsVisited(T.root, false);
560 >
561 > return result;
562 > }
563
564 > function noOverlapReplace(T: IntervalTree, start: number, end: number, textLength: number): void { intervalTree.ts
565 > // https://en.wikipedia.org/wiki/Interval_tree#Augmented_tree
566 > // Now, it is known that two intervals A and B overlap only when both
567 > // A.low <= B.high and A.high >= B.low. When searching the trees for
568 > // nodes overlapping with a given interval, you can immediately skip:
569 > // a) all nodes to the right of nodes whose low value is past the end of the given interval.
570 > // b) all nodes that have their maximum 'high' value below the start of the given interval.
571 > let node = T.root;
572 > let delta = 0;
573 > let nodeMaxEnd = 0;
574 > let nodeStart = 0;
575 > const editDelta = (textLength - (end - start));
576 > while (node !== SENTINEL) {
577 if (getNodeIsVisited(node)) {
578 // going up from this node
628 }
629 }
630 > intervalTree.ts
631 > setNodeIsVisited(T.root, false);
632 > }
633
634 //#endregion
src/vs/editor/common/model/pieceTreeTextBuffer/pieceTreeTextBuffer.ts 13 introduced LOC · 3 ranges

Open complete file

495 continue;
496 }
497 > pieceTreeTextBuffer.ts
498 > if (op.text) {
499 // replacement
500 this._pieceTree.delete(op.rangeOffset, op.rangeLength);
501 this._pieceTree.insert(op.rangeOffset, op.text, true);
502
503 > } else { pieceTreeTextBuffer.ts
504 // deletion
505 this._pieceTree.delete(op.rangeOffset, op.rangeLength);
506 }
507 > pieceTreeTextBuffer.ts
508 > const contentChangeRange = new Range(startLineNumber, startColumn, endLineNumber, endColumn);
509 > contentChanges.push({
510 > range: contentChangeRange,
511 > rangeLength: op.rangeLength,
512 > text: op.text,
513 > rangeOffset: op.rangeOffset,
514 > forceMoveMarkers: op.forceMoveMarkers
515 > });
516 > }
517 return contentChanges;
518 }
src/vs/editor/common/model/tokens/tokenizationTextModelPart.ts 12 introduced LOC · 1 range

Open complete file

135 this._semanticTokens.flush();
136 } else if (!e.isEolChange) { // We don't have to do anything on an EOL change
137 > for (const c of e.changes) { tokenizationTextModelPart.ts
138 > const [eolCount, firstLineLength, lastLineLength] = countEOL(c.text);
139 >
140 > this._semanticTokens.acceptEdit(
141 > c.range,
142 > eolCount,
143 > firstLineLength,
144 > lastLineLength,
145 > c.text.length > 0 ? c.text.charCodeAt(0) : CharCode.Null
146 > );
147 > }
148 > }
149
150 this.tokens.get().handleDidChangeContent(e);
src/vs/editor/common/model/tokens/tokenizerSyntaxTokenBackend.ts 11 introduced LOC · 2 ranges

Open complete file

192 this.todo_resetTokenization(false);
193 } else if (!e.isEolChange) { // We don't have to do anything on an EOL change
194 > for (const c of e.changes) { tokenizerSyntaxTokenBackend.ts
195 > const [eolCount, firstLineLength] = countEOL(c.text);
196 >
197 > this._tokens.acceptEdit(c.range, eolCount, firstLineLength);
198 > this._debugBackgroundTokens?.acceptEdit(c.range, eolCount, firstLineLength);
199 > }
200 > this._debugBackgroundStates?.acceptChanges(e.changes);
201 >
202 > if (this._tokenizer) {
203 this._tokenizer.store.acceptChanges(e.changes);
204 }
205 > this._defaultBackgroundTokenizer?.handleChanges(); tokenizerSyntaxTokenBackend.ts
206 > }
207 }
208
src/vs/editor/common/tokens/contiguousTokensStore.ts 10 introduced LOC · 5 ranges

Open complete file

149
150 public acceptEdit(range: IRange, eolCount: number, firstLineLength: number): void {
151 > this._acceptDeleteRange(range); contiguousTokensStore.ts
152 > this._acceptInsertText(new Position(range.startLineNumber, range.startColumn), eolCount, firstLineLength);
153 > }
154
155 private _acceptDeleteRange(range: IRange): void {
156 > contiguousTokensStore.ts
157 > const firstLineIndex = range.startLineNumber - 1;
158 > if (firstLineIndex >= this._len) {
159 return;
160 }
183 // Delete middle lines
184 this._deleteLines(range.startLineNumber, range.endLineNumber - range.startLineNumber);
185 > } contiguousTokensStore.ts
186
187 private _acceptInsertText(position: Position, eolCount: number, firstLineLength: number): void {
188 > contiguousTokensStore.ts
189 > if (eolCount === 0 && firstLineLength === 0) {
190 // Nothing to insert
191 return;
src/vs/editor/common/textModelEvents.ts 3 introduced LOC · 1 range

Open complete file

318
319 constructor(lineNumber: number, lineNumberPostEdit: number) {
320 > this.lineNumber = lineNumber; textModelEvents.ts
321 > this.lineNumberPostEdit = lineNumberPostEdit;
322 > }
323 }
324

Direct hierarchy

Parents

Children