src/vs/editor/common/viewLayout/lineHeights.ts
493 LOC · 468 covered · 25 uncovered · 150 ranges · 118 concepts · 56 introducers · 50 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.
1
>
/*---------------------------------------------------------------------------------------------
lineHeights.ts ×24
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 { binarySearch2 } from '../../../base/common/arrays.js';
7
>
import { intersection } from '../../../base/common/collections.js';
8
>
import { IEditorConfiguration } from '../config/editorConfiguration.js';
9
>
import { EditorOption } from '../config/editorOptions.js';
10
>
import { ICoordinatesConverter } from '../coordinatesConverter.js';
11
>
import { IModelDecoration } from '../model.js';
12
>
13
>
const enum PendingChangeKind {
14
>
InsertOrChange,
15
>
Remove,
16
>
LinesDeleted,
17
>
LinesInserted,
18
>
}
19
>
20
>
type PendingChange =
21
>
| { readonly kind: PendingChangeKind.InsertOrChange; readonly decorationId: string; readonly startLineNumber: number; readonly endLineNumber: number; readonly lineHeight: number }
22
>
| { readonly kind: PendingChangeKind.Remove; readonly decorationId: string }
23
>
| { readonly kind: PendingChangeKind.LinesDeleted; readonly fromLineNumber: number; readonly toLineNumber: number }
24
>
| { readonly kind: PendingChangeKind.LinesInserted; readonly fromLineNumber: number; readonly toLineNumber: number };
25
>
26
>
export class CustomLine {
27
>
28
>
public index: number;
29
>
public lineNumber: number;
30
>
public specialHeight: number;
31
>
public prefixSum: number;
32
>
public maximumSpecialHeight: number;
33
>
public decorationId: string;
34
>
public deleted: boolean;
35
>
36
>
constructor(decorationId: string, index: number, lineNumber: number, specialHeight: number, prefixSum: number) {
38
>
this.index = index;
39
>
this.lineNumber = lineNumber;
40
>
this.specialHeight = specialHeight;
41
>
this.prefixSum = prefixSum;
42
>
this.maximumSpecialHeight = specialHeight;
43
>
this.deleted = false;
44
>
}
46
>
47
>
/**
48
>
* Manages line heights in the editor with support for custom line heights from decorations.
49
>
*
50
>
* This class maintains an ordered collection of line heights, where each line can have either
51
>
* the default height or a custom height specified by decorations. It supports efficient querying
52
>
* of individual line heights as well as accumulated heights up to a specific line.
53
>
*
54
>
* Line heights are stored in a sorted array for efficient binary search operations. Each line
55
>
* with custom height is represented by a {@link CustomLine} object which tracks its special height,
56
>
* accumulated height prefix sum, and associated decoration ID.
57
>
*
58
>
* The class optimizes performance by:
59
>
* - Using binary search to locate lines in the ordered array
60
>
* - Batching updates through a pending changes mechanism
61
>
* - Computing prefix sums for O(1) accumulated height lookup
62
>
* - Tracking maximum height for lines with multiple decorations
63
>
* - Efficiently handling document changes (line insertions and deletions)
64
>
*
65
>
* When lines are inserted or deleted, the manager updates line numbers and prefix sums
66
>
* for all affected lines. It also handles special cases like decorations that span
67
>
* the insertion/deletion points by re-applying those decorations appropriately.
68
>
*
69
>
* All query operations automatically commit pending changes to ensure consistent results.
70
>
* Clients can modify line heights by adding or removing custom line height decorations,
71
>
* which are tracked by their unique decoration IDs.
72
>
*/
73
>
export class LineHeightsManager {
74
>
75
>
private _decorationIDToCustomLine: ArrayMap<string, CustomLine> = new ArrayMap<string, CustomLine>();
76
>
private _orderedCustomLines: CustomLine[] = [];
77
>
private _pendingChanges: PendingChange[] = [];
78
>
private _invalidIndex: number = Infinity;
79
>
private _defaultLineHeight: number;
80
>
private _hasPending: boolean = false;
81
>
82
>
constructor(defaultLineHeight: number, customLineHeightData: CustomLineHeightData[]) {
84
>
for (const data of customLineHeightData) {
85
>
this.insertOrChangeCustomLineHeight(data.decorationId, data.startLineNumber, data.endLineNumber, data.lineHeight);
lineHeights.ts ×2
86
>
}
89
>
set defaultLineHeight(defaultLineHeight: number) {
91
>
}
93
>
get defaultLineHeight() {
95
>
}
97
>
public removeCustomLineHeight(decorationID: string): void {
98
>
this._pendingChanges.push({ kind: PendingChangeKind.Remove, decorationId: decorationID });
lineHeights.ts ×2
99
>
this._hasPending = true;
100
>
}
102
>
public insertOrChangeCustomLineHeight(decorationId: string, startLineNumber: number, endLineNumber: number, lineHeight: number): void {
103
>
this._pendingChanges.push({ kind: PendingChangeKind.InsertOrChange, decorationId, startLineNumber, endLineNumber, lineHeight });
lineHeights.ts ×13
104
>
this._hasPending = true;
105
>
}
107
>
public heightForLineNumber(lineNumber: number): number {
109
>
const searchIndex = this._binarySearchOverOrderedCustomLinesArray(lineNumber);
110
>
if (searchIndex >= 0) {
112
>
}
116
>
public getAccumulatedLineHeightsIncludingLineNumber(lineNumber: number): number {
118
>
const searchIndex = this._binarySearchOverOrderedCustomLinesArray(lineNumber);
119
>
if (searchIndex >= 0) {
120
>
return this._orderedCustomLines[searchIndex].prefixSum + this._orderedCustomLines[searchIndex].maximumSpecialHeight;
lineHeights.ts ×1
121
>
}
124
>
}
126
>
const previousSpecialLine = this._orderedCustomLines[modifiedIndex - 1];
127
>
return previousSpecialLine.prefixSum + previousSpecialLine.maximumSpecialHeight + this._defaultLineHeight * (lineNumber - previousSpecialLine.lineNumber);
130
>
public onLinesDeleted(fromLineNumber: number, toLineNumber: number): void {
131
>
this._pendingChanges.push({ kind: PendingChangeKind.LinesDeleted, fromLineNumber, toLineNumber });
lineHeights.ts ×1
132
>
this._hasPending = true;
133
>
}
135
>
public onLinesInserted(fromLineNumber: number, toLineNumber: number): void {
136
>
this._pendingChanges.push({ kind: PendingChangeKind.LinesInserted, fromLineNumber, toLineNumber });
lineHeights.ts ×1
137
>
this._hasPending = true;
138
>
}
140
>
private _commit(): void {
143
>
}
145
>
this._pendingChanges = [];
146
>
this._hasPending = false;
147
>
148
>
const stagedInserts: CustomLine[] = [];
149
>
const stagedIdMap = new ArrayMap<string, CustomLine>();
150
>
for (const change of changes) {
151
>
switch (change.kind) {
152
>
case PendingChangeKind.Remove:
154
>
break;
156
>
this._doInsertOrChangeCustomLineHeight(change.decorationId, change.startLineNumber, change.endLineNumber, change.lineHeight, stagedInserts, stagedIdMap);
lineHeights.ts ×13
157
>
break;
160
>
this._doLinesDeleted(change.fromLineNumber, change.toLineNumber);
161
>
break;
164
>
this._doLinesInserted(change.fromLineNumber, change.toLineNumber, stagedInserts, stagedIdMap);
165
>
break;
167
>
}
168
>
this._flushStagedDecorationChanges(stagedInserts, stagedIdMap);
171
>
private _doRemoveCustomLineHeight(decorationID: string, stagedIdMap: ArrayMap<string, CustomLine>): void {
173
>
if (customLines) {
175
>
for (const customLine of customLines) {
176
>
customLine.deleted = true;
177
>
this._invalidIndex = Math.min(this._invalidIndex, customLine.index);
178
>
}
179
>
}
181
>
if (stagedLines) {
183
>
for (const line of stagedLines) {
184
>
line.deleted = true;
185
>
}
186
>
}
189
>
private _doInsertOrChangeCustomLineHeight(decorationId: string, startLineNumber: number, endLineNumber: number, lineHeight: number, stagedInserts: CustomLine[], stagedIdMap: ArrayMap<string, CustomLine>): void {
191
>
for (let lineNumber = startLineNumber; lineNumber <= endLineNumber; lineNumber++) {
192
>
const customLine = new CustomLine(decorationId, -1, lineNumber, lineHeight, 0);
193
>
stagedInserts.push(customLine);
194
>
stagedIdMap.add(decorationId, customLine);
195
>
}
196
>
}
198
>
private _flushStagedDecorationChanges(stagedInserts: CustomLine[], stagedIdMap: ArrayMap<string, CustomLine>): void {
201
>
}
203
>
if (pendingChange.deleted) {
205
>
}
206
>
const candidateInsertionIndex = this._binarySearchOverOrderedCustomLinesArray(pendingChange.lineNumber);
lineHeights.ts ×11
207
>
const insertionIndex = candidateInsertionIndex >= 0 ? candidateInsertionIndex : -(candidateInsertionIndex + 1);
lineHeights.ts ×13
208
>
this._orderedCustomLines.splice(insertionIndex, 0, pendingChange);
209
>
this._invalidIndex = Math.min(this._invalidIndex, insertionIndex);
210
>
}
211
>
stagedInserts.length = 0;
212
>
stagedIdMap.clear();
213
>
if (this._invalidIndex === Infinity) {
215
>
}
217
>
const newOrderedSpecialLines: CustomLine[] = [];
218
>
219
>
for (let i = 0; i < this._invalidIndex; i++) {
221
>
newOrderedSpecialLines.push(customLine);
222
>
newDecorationIDToSpecialLine.add(customLine.decorationId, customLine);
223
>
}
225
>
let numberOfDeletions = 0;
226
>
let previousSpecialLine: CustomLine | undefined = (this._invalidIndex > 0) ? newOrderedSpecialLines[this._invalidIndex - 1] : undefined;
lineHeights.ts ×8
227
>
for (let i = this._invalidIndex; i < this._orderedCustomLines.length; i++) {
229
>
if (customLine.deleted) {
231
>
continue;
232
>
}
234
>
if (previousSpecialLine && previousSpecialLine.lineNumber === customLine.lineNumber) {
236
>
customLine.prefixSum = previousSpecialLine.prefixSum;
238
>
let maximumSpecialHeight = customLine.specialHeight;
239
>
for (let j = i; j < this._orderedCustomLines.length; j++) {
240
>
const nextSpecialLine = this._orderedCustomLines[j];
241
>
if (nextSpecialLine.deleted) {
243
>
}
246
>
}
247
>
maximumSpecialHeight = Math.max(maximumSpecialHeight, nextSpecialLine.specialHeight);
lineHeights.ts ×11
248
>
}
249
>
customLine.maximumSpecialHeight = maximumSpecialHeight;
250
>
251
>
let prefixSum: number;
252
>
if (previousSpecialLine) {
253
>
prefixSum = previousSpecialLine.prefixSum + previousSpecialLine.maximumSpecialHeight + this._defaultLineHeight * (customLine.lineNumber - previousSpecialLine.lineNumber - 1);
lineHeights.ts ×1
255
>
prefixSum = this._defaultLineHeight * (customLine.lineNumber - 1);
256
>
}
257
>
customLine.prefixSum = prefixSum;
258
>
}
259
>
previousSpecialLine = customLine;
260
>
newOrderedSpecialLines.push(customLine);
261
>
newDecorationIDToSpecialLine.add(customLine.decorationId, customLine);
262
>
}
263
>
this._orderedCustomLines = newOrderedSpecialLines;
264
>
this._decorationIDToCustomLine = newDecorationIDToSpecialLine;
265
>
this._invalidIndex = Infinity;
268
>
private _doLinesDeleted(fromLineNumber: number, toLineNumber: number): void {
270
>
const numberOfCustomLines = this._orderedCustomLines.length;
271
>
const candidateStartIndexOfDeletion = this._binarySearchOverOrderedCustomLinesArray(fromLineNumber);
272
>
let startIndexOfDeletion: number;
273
>
if (candidateStartIndexOfDeletion >= 0) {
275
>
for (let i = candidateStartIndexOfDeletion - 1; i >= 0; i--) {
277
startIndexOfDeletion--;
279
>
break;
280
>
}
281
>
}
283
>
startIndexOfDeletion = candidateStartIndexOfDeletion === -(numberOfCustomLines + 1) && candidateStartIndexOfDeletion !== -1 ? numberOfCustomLines - 1 : - (candidateStartIndexOfDeletion + 1);
lineHeights.ts ×1
284
>
}
285
>
const candidateEndIndexOfDeletion = this._binarySearchOverOrderedCustomLinesArray(toLineNumber);
lineHeights.ts ×9
286
>
let endIndexOfDeletion: number;
287
>
if (candidateEndIndexOfDeletion >= 0) {
289
>
for (let i = candidateEndIndexOfDeletion + 1; i < numberOfCustomLines; i++) {
290
if (this._orderedCustomLines[i].lineNumber === toLineNumber) {
291
endIndexOfDeletion++;
292
} else {
293
break;
294
}
295
}
297
>
endIndexOfDeletion = candidateEndIndexOfDeletion === -(numberOfCustomLines + 1) && candidateEndIndexOfDeletion !== -1 ? numberOfCustomLines - 1 : - (candidateEndIndexOfDeletion + 1);
lineHeights.ts ×1
298
>
}
299
>
const isEndIndexBiggerThanStartIndex = endIndexOfDeletion > startIndexOfDeletion;
lineHeights.ts ×9
300
>
const isEndIndexEqualToStartIndexAndCoversCustomLine = endIndexOfDeletion === startIndexOfDeletion
302
>
&& this._orderedCustomLines[startIndexOfDeletion].lineNumber >= fromLineNumber
lineHeights.ts ×1
303
>
&& this._orderedCustomLines[startIndexOfDeletion].lineNumber <= toLineNumber;
lineHeights.ts ×1
305
>
if (isEndIndexBiggerThanStartIndex || isEndIndexEqualToStartIndexAndCoversCustomLine) {
307
>
for (let i = startIndexOfDeletion; i <= endIndexOfDeletion; i++) {
308
>
maximumSpecialHeightOnDeletedInterval = Math.max(maximumSpecialHeightOnDeletedInterval, this._orderedCustomLines[i].maximumSpecialHeight);
309
>
}
310
>
let prefixSumOnDeletedInterval = 0;
311
>
if (startIndexOfDeletion > 0) {
312
>
const previousSpecialLine = this._orderedCustomLines[startIndexOfDeletion - 1];
lineHeights.ts ×4
313
>
prefixSumOnDeletedInterval = previousSpecialLine.prefixSum + previousSpecialLine.maximumSpecialHeight + this._defaultLineHeight * (fromLineNumber - previousSpecialLine.lineNumber - 1);
315
>
prefixSumOnDeletedInterval = fromLineNumber > 0 ? (fromLineNumber - 1) * this._defaultLineHeight : 0;
lineHeights.ts ×2
316
>
}
317
>
const firstSpecialLineDeleted = this._orderedCustomLines[startIndexOfDeletion];
lineHeights.ts ×7
318
>
const lastSpecialLineDeleted = this._orderedCustomLines[endIndexOfDeletion];
319
>
const firstSpecialLineAfterDeletion = this._orderedCustomLines[endIndexOfDeletion + 1];
320
>
const heightOfFirstLineAfterDeletion = firstSpecialLineAfterDeletion && firstSpecialLineAfterDeletion.lineNumber === toLineNumber + 1 ? firstSpecialLineAfterDeletion.maximumSpecialHeight : this._defaultLineHeight;
321
>
const totalHeightDeleted = lastSpecialLineDeleted.prefixSum
322
>
+ lastSpecialLineDeleted.maximumSpecialHeight
323
>
- firstSpecialLineDeleted.prefixSum
324
>
+ this._defaultLineHeight * (toLineNumber - lastSpecialLineDeleted.lineNumber)
325
>
+ this._defaultLineHeight * (firstSpecialLineDeleted.lineNumber - fromLineNumber)
326
>
+ heightOfFirstLineAfterDeletion - maximumSpecialHeightOnDeletedInterval;
327
>
328
>
const decorationIdsSeen = new Set<string>();
329
>
const newOrderedCustomLines: CustomLine[] = [];
330
>
const newDecorationIDToSpecialLine = new ArrayMap<string, CustomLine>();
331
>
let numberOfDeletions = 0;
332
>
for (let i = 0; i < this._orderedCustomLines.length; i++) {
333
>
const customLine = this._orderedCustomLines[i];
334
>
if (i < startIndexOfDeletion) {
336
>
newDecorationIDToSpecialLine.add(customLine.decorationId, customLine);
338
>
const decorationId = customLine.decorationId;
339
>
if (!decorationIdsSeen.has(decorationId)) {
341
>
customLine.lineNumber = fromLineNumber;
342
>
customLine.prefixSum = prefixSumOnDeletedInterval;
343
>
customLine.maximumSpecialHeight = maximumSpecialHeightOnDeletedInterval;
344
>
newOrderedCustomLines.push(customLine);
345
>
newDecorationIDToSpecialLine.add(customLine.decorationId, customLine);
348
>
}
350
customLine.index -= numberOfDeletions;
351
customLine.lineNumber -= deleteCount;
352
customLine.prefixSum -= totalHeightDeleted;
353
newOrderedCustomLines.push(customLine);
354
newDecorationIDToSpecialLine.add(customLine.decorationId, customLine);
355
}
357
>
}
358
>
this._orderedCustomLines = newOrderedCustomLines;
359
>
this._decorationIDToCustomLine = newDecorationIDToSpecialLine;
362
>
for (let i = endIndexOfDeletion; i < this._orderedCustomLines.length; i++) {
364
>
if (customLine.lineNumber > toLineNumber) {
366
>
customLine.prefixSum -= totalHeightDeleted;
367
>
}
372
>
private _doLinesInserted(fromLineNumber: number, toLineNumber: number, stagedInserts: CustomLine[], stagedIdMap: ArrayMap<string, CustomLine>): void {
374
>
const candidateStartIndexOfInsertion = this._binarySearchOverOrderedCustomLinesArray(fromLineNumber);
375
>
let startIndexOfInsertion: number;
376
>
if (candidateStartIndexOfInsertion >= 0) {
378
>
for (let i = candidateStartIndexOfInsertion - 1; i >= 0; i--) {
379
>
if (this._orderedCustomLines[i].lineNumber === fromLineNumber) {
380
startIndexOfInsertion--;
382
>
break;
383
>
}
384
>
}
387
>
}
389
>
const decorationsImmediatelyAfter = new Set<string>();
390
>
for (let i = startIndexOfInsertion; i < this._orderedCustomLines.length; i++) {
393
>
}
396
>
for (let i = startIndexOfInsertion - 1; i >= 0; i--) {
398
>
decorationsImmediatelyBefore.add(this._orderedCustomLines[i].decorationId);
399
>
}
400
>
}
401
>
const decorationsWithGaps = intersection(decorationsImmediatelyBefore, decorationsImmediatelyAfter);
lineHeights.ts ×8
402
>
const prefixSumToAdd = insertCount * this._defaultLineHeight;
403
>
for (let i = startIndexOfInsertion; i < this._orderedCustomLines.length; i++) {
405
>
this._orderedCustomLines[i].prefixSum += prefixSumToAdd;
406
>
}
408
>
if (decorationsWithGaps.size > 0) {
410
>
const decoration = this._decorationIDToCustomLine.get(decorationId);
411
>
if (decoration) {
412
>
const startLineNumber = decoration.reduce((min, l) => Math.min(min, l.lineNumber), fromLineNumber); // min
413
>
const endLineNumber = decoration.reduce((max, l) => Math.max(max, l.lineNumber), fromLineNumber); // max
414
>
const lineHeight = decoration.reduce((max, l) => Math.max(max, l.specialHeight), 0);
415
>
toReAdd.push({
416
>
decorationId,
417
>
startLineNumber,
418
>
endLineNumber,
419
>
lineHeight
420
>
});
421
>
}
422
>
}
423
>
424
>
for (const dec of toReAdd) {
425
>
this._doInsertOrChangeCustomLineHeight(dec.decorationId, dec.startLineNumber, dec.endLineNumber, dec.lineHeight, stagedInserts, stagedIdMap);
426
>
}
427
>
}
430
>
private _binarySearchOverOrderedCustomLinesArray(lineNumber: number): number {
433
>
if (line.lineNumber === lineNumber) {
439
>
}
441
>
}
443
>
444
>
export class CustomLineHeightData {
445
>
446
>
constructor(
448
>
readonly startLineNumber: number,
449
>
readonly endLineNumber: number,
450
>
readonly lineHeight: number
451
>
) { }
453
>
public static fromDecorations(decorations: IModelDecoration[], coordinatesConverter: ICoordinatesConverter, configuration: IEditorConfiguration): CustomLineHeightData[] {
454
const defaultLineHeight = configuration.options.get(EditorOption.lineHeight);
455
return decorations.map((d) => {
456
const viewRange = coordinatesConverter.convertModelRangeToViewRange(d.range);
457
return new CustomLineHeightData(
458
d.id,
459
viewRange.startLineNumber,
460
viewRange.endLineNumber,
461
d.options.lineHeight ? d.options.lineHeight * defaultLineHeight : 0
462
);
463
});
464
}
466
>
467
>
class ArrayMap<K, T> {
468
>
469
>
private _map: Map<K, T[]> = new Map<K, T[]>();
470
>
471
>
constructor() { }
472
>
473
>
add(key: K, value: T) {
475
>
if (!array) {
476
>
this._map.set(key, [value]);
477
>
} else {
479
>
}
482
>
get(key: K): T[] | undefined {
484
>
}
486
>
delete(key: K): void {
488
>
}
490
>
clear(): void {
492
>
}