Vihren Atlas

src/vs/editor/common/model/pieceTreeTextBuffer/rbTreeBase.ts

425 LOC · 425 covered · 0 uncovered · 159 ranges · 1708 concepts · 81 introducers · 861 tests

File neighbourhood

The centred file is linked to every concept that introduces one of its ranges, every test that runs code from the file, and the gray connector concepts standing between those tests and the file's own introducer concepts. Undirected links join concepts to every file where they introduce source and concepts to the tests they introduce; arrows show specialization between the displayed concepts and bridge only concepts omitted from this view. Concept colors match the source ranges below; connector concepts have no source color and are shown in gray.

Focused file, its introducer and connector concepts, their introduced files, and tests that run code from the file

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 related-file, concept, and source links on this page.

Graph controls are ready.

Interactive rendering requires JavaScript and WebGL. Use the related-file, concept, and source links on this page while the interactive map is unavailable.

Files sharing a concept 34

A concept that introduces code in this file also introduces code in these files.

Files with a broader (ancestor) concept 26

These files introduce code for a direct ancestor — a broader, larger-extent concept — of a concept that introduces code here.

Files with a narrower (descendant) concept 42

These files introduce code for a direct descendant — a narrower, larger-intent concept — of a concept that introduces code here.

1 > /*--------------------------------------------------------------------------------------------- textModel.ts ×190
2 > * Copyright (c) Microsoft Corporation. All rights reserved.
3 > * Licensed under the MIT License. See License.txt in the project root for license information.
4 > *--------------------------------------------------------------------------------------------*/
5 >
6 > import { Piece, PieceTreeBase } from './pieceTreeBase.js';
7 >
8 > export class TreeNode {
9 > parent: TreeNode;
10 > left: TreeNode;
11 > right: TreeNode;
12 > color: NodeColor;
13 >
14 > // Piece
15 > piece: Piece;
16 > size_left: number; // size of the left subtree (not inorder)
17 > lf_left: number; // line feeds cnt in the left subtree (not in order)
18 >
19 > constructor(piece: Piece, color: NodeColor) {
20 > this.piece = piece;
21 > this.color = color;
22 > this.size_left = 0;
23 > this.lf_left = 0;
24 > this.parent = this;
25 > this.left = this;
26 > this.right = this;
27 > }
28 >
29 > public next(): TreeNode {
30 > if (this.right !== SENTINEL) { rbTreeBase.ts ×2
31 > return leftest(this.right); rbTreeBase.ts ×1
32 > }
33 > rbTreeBase.ts ×3
34 > let node: TreeNode = this;
35 >
36 > while (node.parent !== SENTINEL) {
37 > if (node.parent.left === node) { rbTreeBase.ts ×1
38 > break; rbTreeBase.ts ×2
39 > }
40 > rbTreeBase.ts ×1
41 > node = node.parent;
42 > }
43 > rbTreeBase.ts ×3
44 > if (node.parent === SENTINEL) {
45 > return SENTINEL; rbTreeBase.ts ×1
46 > } else { rbTreeBase.ts ×3
47 > return node.parent; rbTreeBase.ts ×2
48 > }
49 > } rbTreeBase.ts ×2
50 > textModel.ts ×190
51 > public prev(): TreeNode {
52 > if (this.left !== SENTINEL) { rbTreeBase.ts ×2
53 > return righttest(this.left); rbTreeBase.ts ×1
54 > }
55 > rbTreeBase.ts ×3
56 > let node: TreeNode = this;
57 >
58 > while (node.parent !== SENTINEL) {
59 > if (node.parent.right === node) { rbTreeBase.ts ×1
60 > break; rbTreeBase.ts ×2
61 > }
62 > rbTreeBase.ts ×1
63 > node = node.parent;
64 > }
65 > rbTreeBase.ts ×3
66 > if (node.parent === SENTINEL) {
67 > return SENTINEL; rbTreeBase.ts ×1
68 > } else { rbTreeBase.ts ×3
69 > return node.parent; rbTreeBase.ts ×2
70 > }
71 > } rbTreeBase.ts ×2
72 > textModel.ts ×190
73 > public detach(): void {
74 > this.parent = null!; rbTreeBase.ts ×6
75 > this.left = null!;
76 > this.right = null!;
77 > }
78 > } textModel.ts ×190
79 >
80 > export const enum NodeColor {
81 > Black = 0,
82 > Red = 1,
83 > }
84 >
85 > export const SENTINEL: TreeNode = new TreeNode(null!, NodeColor.Black);
86 > SENTINEL.parent = SENTINEL;
87 > SENTINEL.left = SENTINEL;
88 > SENTINEL.right = SENTINEL;
89 > SENTINEL.color = NodeColor.Black;
90 >
91 > export function leftest(node: TreeNode): TreeNode {
92 > while (node.left !== SENTINEL) { rbTreeBase.ts ×2
93 > node = node.left; rbTreeBase.ts ×1
94 > }
95 > return node; rbTreeBase.ts ×2
96 > }
97 > textModel.ts ×190
98 > export function righttest(node: TreeNode): TreeNode {
99 > while (node.right !== SENTINEL) { rbTreeBase.ts ×2
100 > node = node.right; rbTreeBase.ts ×1
101 > }
102 > return node; rbTreeBase.ts ×2
103 > }
104 > textModel.ts ×190
105 > function calculateSize(node: TreeNode): number { rbTreeBase.ts ×2
106 > if (node === SENTINEL) {
107 > return 0;
108 > }
109 > rbTreeBase.ts ×3
110 > return node.size_left + node.piece.length + calculateSize(node.right);
111 > }
112 > textModel.ts ×190
113 > function calculateLF(node: TreeNode): number { rbTreeBase.ts ×2
114 > if (node === SENTINEL) {
115 > return 0;
116 > }
117 > rbTreeBase.ts ×3
118 > return node.lf_left + node.piece.lineFeedCnt + calculateLF(node.right);
119 > }
120 > textModel.ts ×190
121 > function resetSentinel(): void { rbTreeBase.ts ×6
122 > SENTINEL.parent = SENTINEL;
123 > }
124 > textModel.ts ×190
125 > export function leftRotate(tree: PieceTreeBase, x: TreeNode) {
126 > const y = x.right; rbTreeBase.ts ×4
127 >
128 > // fix size_left
129 > y.size_left += x.size_left + (x.piece ? x.piece.length : 0);
130 > y.lf_left += x.lf_left + (x.piece ? x.piece.lineFeedCnt : 0);
131 > x.right = y.left;
132 >
133 > if (y.left !== SENTINEL) {
134 > y.left.parent = x; rbTreeBase.ts ×1
135 > }
136 > y.parent = x.parent; rbTreeBase.ts ×4
137 > if (x.parent === SENTINEL) {
138 > tree.root = y; rbTreeBase.ts ×1
139 > } else if (x.parent.left === x) { rbTreeBase.ts ×4
140 > x.parent.left = y; rbTreeBase.ts ×1
141 > } else { rbTreeBase.ts ×1
142 > x.parent.right = y; rbTreeBase.ts ×1
143 > }
144 > y.left = x; rbTreeBase.ts ×4
145 > x.parent = y;
146 > }
147 > textModel.ts ×190
148 > export function rightRotate(tree: PieceTreeBase, y: TreeNode) {
149 > const x = y.left; rbTreeBase.ts ×4
150 > y.left = x.right;
151 > if (x.right !== SENTINEL) {
152 > x.right.parent = y; rbTreeBase.ts ×1
153 > }
154 > x.parent = y.parent; rbTreeBase.ts ×4
155 >
156 > // fix size_left
157 > y.size_left -= x.size_left + (x.piece ? x.piece.length : 0);
158 > y.lf_left -= x.lf_left + (x.piece ? x.piece.lineFeedCnt : 0);
159 >
160 > if (y.parent === SENTINEL) {
161 > tree.root = x; rbTreeBase.ts ×1
162 > } else if (y === y.parent.right) { rbTreeBase.ts ×4
163 > y.parent.right = x; rbTreeBase.ts ×1
164 > } else {
165 > y.parent.left = x; rbTreeBase.ts ×1
166 > }
167 > rbTreeBase.ts ×4
168 > x.right = y;
169 > y.parent = x;
170 > }
171 > textModel.ts ×190
172 > export function rbDelete(tree: PieceTreeBase, z: TreeNode) {
173 > let x: TreeNode; rbTreeBase.ts ×6
174 > let y: TreeNode;
175 >
176 > if (z.left === SENTINEL) {
177 > y = z; rbTreeBase.ts ×1
178 > x = y.right;
179 > } else if (z.right === SENTINEL) { rbTreeBase.ts ×6
180 > y = z; rbTreeBase.ts ×1
181 > x = y.left;
182 > } else { rbTreeBase.ts ×1
183 > y = leftest(z.right); rbTreeBase.ts ×7
184 > x = y.right;
185 > }
186 > rbTreeBase.ts ×6
187 > if (y === tree.root) {
188 > tree.root = x; rbTreeBase.ts ×1
189 >
190 > // if x is null, we are removing the only node
191 > x.color = NodeColor.Black;
192 > z.detach();
193 > resetSentinel();
194 > tree.root.parent = SENTINEL;
195 >
196 > return;
197 > }
198 > rbTreeBase.ts ×6
199 > const yWasRed = (y.color === NodeColor.Red);
200 >
201 > if (y === y.parent.left) {
202 > y.parent.left = x; rbTreeBase.ts ×1
203 > } else { rbTreeBase.ts ×6
204 > y.parent.right = x; rbTreeBase.ts ×1
205 > }
206 > rbTreeBase.ts ×6
207 > if (y === z) {
208 > x.parent = y.parent; rbTreeBase.ts ×1
209 > recomputeTreeMetadata(tree, x);
210 > } else { rbTreeBase.ts ×6
211 > if (y.parent === z) { rbTreeBase.ts ×7
212 > x.parent = y; rbTreeBase.ts ×1
213 > } else { rbTreeBase.ts ×7
214 > x.parent = y.parent; rbTreeBase.ts ×2
215 > }
216 > rbTreeBase.ts ×7
217 > // as we make changes to x's hierarchy, update size_left of subtree first
218 > recomputeTreeMetadata(tree, x);
219 >
220 > y.left = z.left;
221 > y.right = z.right;
222 > y.parent = z.parent;
223 > y.color = z.color;
224 >
225 > if (z === tree.root) {
226 > tree.root = y; rbTreeBase.ts ×1
227 > } else { rbTreeBase.ts ×7
228 > if (z === z.parent.left) { rbTreeBase.ts ×3
229 > z.parent.left = y; rbTreeBase.ts ×1
230 > } else { rbTreeBase.ts ×3
231 > z.parent.right = y; rbTreeBase.ts ×1
232 > }
233 > } rbTreeBase.ts ×3
234 > rbTreeBase.ts ×7
235 > if (y.left !== SENTINEL) {
236 > y.left.parent = y;
237 > }
238 > if (y.right !== SENTINEL) {
239 > y.right.parent = y; rbTreeBase.ts ×2
240 > }
241 > // update metadata rbTreeBase.ts ×7
242 > // we replace z with y, so in this sub tree, the length change is z.item.length
243 > y.size_left = z.size_left;
244 > y.lf_left = z.lf_left;
245 > recomputeTreeMetadata(tree, y);
246 > }
247 > rbTreeBase.ts ×6
248 > z.detach();
249 >
250 > if (x.parent.left === x) {
251 > const newSizeLeft = calculateSize(x); rbTreeBase.ts ×2
252 > const newLFLeft = calculateLF(x);
253 > if (newSizeLeft !== x.parent.size_left || newLFLeft !== x.parent.lf_left) {
254 > const delta = newSizeLeft - x.parent.size_left; rbTreeBase.ts ×1
255 > const lf_delta = newLFLeft - x.parent.lf_left;
256 > x.parent.size_left = newSizeLeft;
257 > x.parent.lf_left = newLFLeft;
258 > updateTreeMetadata(tree, x.parent, delta, lf_delta);
259 > }
260 > } rbTreeBase.ts ×2
261 > rbTreeBase.ts ×6
262 > recomputeTreeMetadata(tree, x.parent);
263 >
264 > if (yWasRed) {
265 > resetSentinel(); rbTreeBase.ts ×1
266 > return;
267 > }
268 > rbTreeBase.ts ×2
269 > // RB-DELETE-FIXUP
270 > let w: TreeNode;
271 > while (x !== tree.root && x.color === NodeColor.Black) { rbTreeBase.ts ×6
272 > if (x === x.parent.left) { rbTreeBase.ts ×3
273 > w = x.parent.right; rbTreeBase.ts ×3
274 >
275 > if (w.color === NodeColor.Red) {
276 > w.color = NodeColor.Black; rbTreeBase.ts ×1
277 > x.parent.color = NodeColor.Red;
278 > leftRotate(tree, x.parent);
279 > w = x.parent.right;
280 > }
281 > rbTreeBase.ts ×3
282 > if (w.left.color === NodeColor.Black && w.right.color === NodeColor.Black) {
283 > w.color = NodeColor.Red; rbTreeBase.ts ×1
284 > x = x.parent;
285 > } else { rbTreeBase.ts ×3
286 > if (w.right.color === NodeColor.Black) { rbTreeBase.ts ×2
287 > w.left.color = NodeColor.Black; rbTreeBase.ts ×1
288 > w.color = NodeColor.Red;
289 > rightRotate(tree, w);
290 > w = x.parent.right;
291 > }
292 > rbTreeBase.ts ×2
293 > w.color = x.parent.color;
294 > x.parent.color = NodeColor.Black;
295 > w.right.color = NodeColor.Black;
296 > leftRotate(tree, x.parent);
297 > x = tree.root;
298 > }
299 > } else { rbTreeBase.ts ×3
300 > w = x.parent.left; rbTreeBase.ts ×4
301 >
302 > if (w.color === NodeColor.Red) {
303 > w.color = NodeColor.Black; rbTreeBase.ts ×1
304 > x.parent.color = NodeColor.Red;
305 > rightRotate(tree, x.parent);
306 > w = x.parent.left;
307 > }
308 > rbTreeBase.ts ×4
309 > if (w.left.color === NodeColor.Black && w.right.color === NodeColor.Black) {
310 > w.color = NodeColor.Red; rbTreeBase.ts ×1
311 > x = x.parent;
312 >
313 > } else { rbTreeBase.ts ×4
314 > if (w.left.color === NodeColor.Black) { rbTreeBase.ts ×2
315 > w.right.color = NodeColor.Black; rbTreeBase.ts ×1
316 > w.color = NodeColor.Red;
317 > leftRotate(tree, w);
318 > w = x.parent.left;
319 > }
320 > rbTreeBase.ts ×2
321 > w.color = x.parent.color;
322 > x.parent.color = NodeColor.Black;
323 > w.left.color = NodeColor.Black;
324 > rightRotate(tree, x.parent);
325 > x = tree.root;
326 > }
327 > } rbTreeBase.ts ×4
328 > } rbTreeBase.ts ×3
329 > x.color = NodeColor.Black; rbTreeBase.ts ×2
330 > resetSentinel();
331 > }
332 > textModel.ts ×190
333 > export function fixInsert(tree: PieceTreeBase, x: TreeNode) {
334 > recomputeTreeMetadata(tree, x); rbTreeBase.ts ×6
335 >
336 > while (x !== tree.root && x.parent.color === NodeColor.Red) {
337 > if (x.parent === x.parent.parent.left) { rbTreeBase.ts ×3
338 > const y = x.parent.parent.right; rbTreeBase.ts ×2
339 >
340 > if (y.color === NodeColor.Red) {
341 > x.parent.color = NodeColor.Black; rbTreeBase.ts ×1
342 > y.color = NodeColor.Black;
343 > x.parent.parent.color = NodeColor.Red;
344 > x = x.parent.parent;
345 > } else { rbTreeBase.ts ×2
346 > if (x === x.parent.right) { rbTreeBase.ts ×2
347 > x = x.parent; rbTreeBase.ts ×1
348 > leftRotate(tree, x);
349 > }
350 > rbTreeBase.ts ×2
351 > x.parent.color = NodeColor.Black;
352 > x.parent.parent.color = NodeColor.Red;
353 > rightRotate(tree, x.parent.parent);
354 > }
355 > } else { rbTreeBase.ts ×3
356 > const y = x.parent.parent.left; rbTreeBase.ts ×3
357 >
358 > if (y.color === NodeColor.Red) {
359 > x.parent.color = NodeColor.Black; rbTreeBase.ts ×1
360 > y.color = NodeColor.Black;
361 > x.parent.parent.color = NodeColor.Red;
362 > x = x.parent.parent;
363 > } else { rbTreeBase.ts ×3
364 > if (x === x.parent.left) { rbTreeBase.ts ×2
365 > x = x.parent; rbTreeBase.ts ×1
366 > rightRotate(tree, x);
367 > }
368 > x.parent.color = NodeColor.Black; rbTreeBase.ts ×2
369 > x.parent.parent.color = NodeColor.Red;
370 > leftRotate(tree, x.parent.parent);
371 > }
372 > } rbTreeBase.ts ×3
373 > } rbTreeBase.ts ×3
374 > rbTreeBase.ts ×6
375 > tree.root.color = NodeColor.Black;
376 > }
377 > textModel.ts ×190
378 > export function updateTreeMetadata(tree: PieceTreeBase, x: TreeNode, delta: number, lineFeedCntDelta: number): void {
379 > // node length change or line feed count change rbTreeBase.ts ×2
380 > while (x !== tree.root && x !== SENTINEL) {
381 > if (x.parent.left === x) { rbTreeBase.ts ×2
382 > x.parent.size_left += delta; rbTreeBase.ts ×1
383 > x.parent.lf_left += lineFeedCntDelta;
384 > }
385 > rbTreeBase.ts ×2
386 > x = x.parent;
387 > }
388 > } rbTreeBase.ts ×2
389 > textModel.ts ×190
390 > export function recomputeTreeMetadata(tree: PieceTreeBase, x: TreeNode) {
391 > let delta = 0; rbTreeBase.ts ×6
392 > let lf_delta = 0;
393 > if (x === tree.root) {
394 > return;
395 > }
396 > rbTreeBase.ts ×2
397 > // go upwards till the node whose left subtree is changed.
398 > while (x !== tree.root && x === x.parent.right) { rbTreeBase.ts ×6
399 > x = x.parent; rbTreeBase.ts ×1
400 > }
401 > rbTreeBase.ts ×2
402 > if (x === tree.root) {
403 > // well, it means we add a node to the end (inorder) rbTreeBase.ts ×1
404 > return;
405 > }
406 > rbTreeBase.ts ×3
407 > // x is the node whose right subtree is changed.
408 > x = x.parent;
409 >
410 > delta = calculateSize(x.left) - x.size_left;
411 > lf_delta = calculateLF(x.left) - x.lf_left;
412 > x.size_left += delta;
413 > x.lf_left += lf_delta;
414 >
415 >
416 > // go upwards till root. O(logN)
417 > while (x !== tree.root && (delta !== 0 || lf_delta !== 0)) { rbTreeBase.ts ×6
418 > if (x.parent.left === x) { rbTreeBase.ts ×2
419 > x.parent.size_left += delta; rbTreeBase.ts ×1
420 > x.parent.lf_left += lf_delta;
421 > }
422 > rbTreeBase.ts ×2
423 > x = x.parent;
424 > }
425 > } rbTreeBase.ts ×6