src/vs/editor/common/model/pieceTreeTextBuffer/pieceTreeTextBuffer.ts
629 LOC · 509 covered · 120 uncovered · 145 ranges · 1708 concepts · 63 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.
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 { Emitter, Event } from '../../../../base/common/event.js';
7
>
import * as strings from '../../../../base/common/strings.js';
8
>
import { Position } from '../../core/position.js';
9
>
import { Range } from '../../core/range.js';
10
>
import { ApplyEditsResult, EndOfLinePreference, FindMatch, IInternalModelContentChange, ISingleEditOperationIdentifier, ITextBuffer, ITextSnapshot, ValidAnnotatedEditOperation, IValidEditOperation, SearchData } from '../../model.js';
11
>
import { PieceTreeBase, StringBuffer } from './pieceTreeBase.js';
12
>
import { countEOL, StringEOL } from '../../core/misc/eolCounter.js';
13
>
import { TextChange } from '../../core/textChange.js';
14
>
import { Disposable } from '../../../../base/common/lifecycle.js';
15
>
16
>
export interface IValidatedEditOperation {
17
>
sortIndex: number;
18
>
identifier: ISingleEditOperationIdentifier | null;
19
>
range: Range;
20
>
rangeOffset: number;
21
>
rangeLength: number;
22
>
text: string;
23
>
eolCount: number;
24
>
firstLineLength: number;
25
>
lastLineLength: number;
26
>
forceMoveMarkers: boolean;
27
>
isAutoWhitespaceEdit: boolean;
28
>
}
29
>
30
>
interface IReverseSingleEditOperation extends IValidEditOperation {
31
>
sortIndex: number;
32
>
}
33
>
34
>
export class PieceTreeTextBuffer extends Disposable implements ITextBuffer {
35
>
private _pieceTree: PieceTreeBase;
36
>
private readonly _BOM: string;
37
>
private _mightContainRTL: boolean;
38
>
private _mightContainUnusualLineTerminators: boolean;
39
>
private _mightContainNonBasicASCII: boolean;
40
>
41
>
private readonly _onDidChangeContent: Emitter<void> = this._register(new Emitter<void>());
42
>
public get onDidChangeContent(): Event<void> { return this._onDidChangeContent.event; }
43
>
44
>
constructor(chunks: StringBuffer[], BOM: string, eol: '\r\n' | '\n', containsRTL: boolean, containsUnusualLineTerminators: boolean, isBasicASCII: boolean, eolNormalized: boolean) {
46
>
this._BOM = BOM;
47
>
this._mightContainNonBasicASCII = !isBasicASCII;
48
>
this._mightContainRTL = containsRTL;
49
>
this._mightContainUnusualLineTerminators = containsUnusualLineTerminators;
50
>
this._pieceTree = new PieceTreeBase(chunks, eol, eolNormalized);
51
>
}
53
>
// #region TextBuffer
54
>
public equals(other: ITextBuffer): boolean {
55
if (!(other instanceof PieceTreeTextBuffer)) {
56
return false;
57
}
58
if (this._BOM !== other._BOM) {
59
return false;
60
}
61
if (this.getEOL() !== other.getEOL()) {
62
return false;
63
}
64
return this._pieceTree.equal(other._pieceTree);
65
}
68
>
}
70
return this._mightContainUnusualLineTerminators;
71
}
73
this._mightContainUnusualLineTerminators = false;
74
}
77
>
}
79
return this._BOM;
80
}
83
>
}
85
>
public createSnapshot(preserveBOM: boolean): ITextSnapshot {
87
>
}
89
>
public getOffsetAt(lineNumber: number, column: number): number {
91
>
}
93
>
public getPositionAt(offset: number): Position {
95
>
}
97
>
public getRangeAt(start: number, length: number): Range {
99
>
const startPosition = this.getPositionAt(start);
100
>
const endPosition = this.getPositionAt(end);
101
>
return new Range(startPosition.lineNumber, startPosition.column, endPosition.lineNumber, endPosition.column);
102
>
}
104
>
public getValueInRange(range: Range, eol: EndOfLinePreference = EndOfLinePreference.TextDefined): string {
107
>
}
109
>
const lineEnding = this._getEndOfLine(eol);
110
>
return this._pieceTree.getValueInRange(range, lineEnding);
113
>
public getValueLengthInRange(range: Range, eol: EndOfLinePreference = EndOfLinePreference.TextDefined): number {
116
>
}
118
>
if (range.startLineNumber === range.endLineNumber) {
120
>
}
122
>
const startOffset = this.getOffsetAt(range.startLineNumber, range.startColumn);
123
>
const endOffset = this.getOffsetAt(range.endLineNumber, range.endColumn);
124
>
125
>
// offsets use the text EOL, so we need to compensate for length differences
126
>
// if the requested EOL doesn't match the text EOL
127
>
let eolOffsetCompensation = 0;
128
>
const desiredEOL = this._getEndOfLine(eol);
129
>
const actualEOL = this.getEOL();
130
>
if (desiredEOL.length !== actualEOL.length) {
132
>
const eolCount = range.endLineNumber - range.startLineNumber;
133
>
eolOffsetCompensation = delta * eolCount;
134
>
}
136
>
return endOffset - startOffset + eolOffsetCompensation;
139
>
public getCharacterCountInRange(range: Range, eol: EndOfLinePreference = EndOfLinePreference.TextDefined): number {
140
if (this._mightContainNonBasicASCII) {
141
// we must count by iterating
142
143
let result = 0;
144
145
const fromLineNumber = range.startLineNumber;
146
const toLineNumber = range.endLineNumber;
147
for (let lineNumber = fromLineNumber; lineNumber <= toLineNumber; lineNumber++) {
148
const lineContent = this.getLineContent(lineNumber);
149
const fromOffset = (lineNumber === fromLineNumber ? range.startColumn - 1 : 0);
150
const toOffset = (lineNumber === toLineNumber ? range.endColumn - 1 : lineContent.length);
151
152
for (let offset = fromOffset; offset < toOffset; offset++) {
153
if (strings.isHighSurrogate(lineContent.charCodeAt(offset))) {
154
result = result + 1;
155
offset = offset + 1;
156
} else {
157
result = result + 1;
158
}
159
}
160
}
161
162
result += this._getEndOfLine(eol).length * (toLineNumber - fromLineNumber);
163
164
return result;
165
}
166
167
return this.getValueLengthInRange(range, eol);
168
}
170
>
public getNearestChunk(offset: number): string {
171
return this._pieceTree.getNearestChunk(offset);
172
}
174
>
public getLength(): number {
176
>
}
178
>
public getLineCount(): number {
180
>
}
182
>
public getLinesContent(): string[] {
184
>
}
186
>
public getLineContent(lineNumber: number): string {
188
>
}
190
>
public getLineCharCode(lineNumber: number, index: number): number {
192
>
}
194
>
public getCharCode(offset: number): number {
195
return this._pieceTree.getCharCode(offset);
196
}
198
>
public getLineLength(lineNumber: number): number {
200
>
}
202
>
public getLineMinColumn(lineNumber: number): number {
203
return 1;
204
}
206
>
public getLineMaxColumn(lineNumber: number): number {
207
return this.getLineLength(lineNumber) + 1;
208
}
210
>
public getLineFirstNonWhitespaceColumn(lineNumber: number): number {
211
>
const result = strings.firstNonWhitespaceIndex(this.getLineContent(lineNumber));
textModel.ts ×2
212
>
if (result === -1) {
213
>
return 0;
214
>
}
215
>
return result + 1;
216
>
}
218
>
public getLineLastNonWhitespaceColumn(lineNumber: number): number {
219
>
const result = strings.lastNonWhitespaceIndex(this.getLineContent(lineNumber));
textModel.ts ×2
220
>
if (result === -1) {
221
>
return 0;
222
>
}
223
>
return result + 2;
224
>
}
226
>
private _getEndOfLine(eol: EndOfLinePreference): string {
228
>
case EndOfLinePreference.LF:
235
throw new Error('Unknown EOL preference');
237
>
}
239
>
public setEOL(newEOL: '\r\n' | '\n'): void {
241
>
}
243
>
public applyEdits(rawOperations: ValidAnnotatedEditOperation[], recordTrimAutoWhitespace: boolean, computeUndoEdits: boolean): ApplyEditsResult {
245
>
let mightContainUnusualLineTerminators = this._mightContainUnusualLineTerminators;
246
>
let mightContainNonBasicASCII = this._mightContainNonBasicASCII;
247
>
let canReduceOperations = true;
248
>
249
>
let operations: IValidatedEditOperation[] = [];
250
>
for (let i = 0; i < rawOperations.length; i++) {
251
>
const op = rawOperations[i];
252
>
if (canReduceOperations && op._isTracked) {
253
canReduceOperations = false;
254
}
256
>
if (op.text) {
258
>
if (!mightContainNonBasicASCII) {
260
>
mightContainNonBasicASCII = textMightContainNonBasicASCII;
261
>
}
264
>
mightContainRTL = strings.containsRTL(op.text);
265
>
}
266
>
if (!mightContainUnusualLineTerminators && textMightContainNonBasicASCII) {
pieceTreeTextBuffer.ts ×7
268
>
mightContainUnusualLineTerminators = strings.containsUnusualLineTerminators(op.text);
269
>
}
272
>
let validText = '';
273
>
let eolCount = 0;
274
>
let firstLineLength = 0;
275
>
let lastLineLength = 0;
276
>
if (op.text) {
278
>
[eolCount, firstLineLength, lastLineLength, strEOL] = countEOL(op.text);
279
>
280
>
const bufferEOL = this.getEOL();
281
>
const expectedStrEOL = (bufferEOL === '\r\n' ? StringEOL.CRLF : StringEOL.LF);
282
>
if (strEOL === StringEOL.Unknown || strEOL === expectedStrEOL) {
286
>
}
289
>
operations[i] = {
290
>
sortIndex: i,
291
>
identifier: op.identifier || null,
292
>
range: validatedRange,
293
>
rangeOffset: this.getOffsetAt(validatedRange.startLineNumber, validatedRange.startColumn),
294
>
rangeLength: this.getValueLengthInRange(validatedRange),
295
>
text: validText,
296
>
eolCount: eolCount,
297
>
firstLineLength: firstLineLength,
298
>
lastLineLength: lastLineLength,
299
>
forceMoveMarkers: Boolean(op.forceMoveMarkers),
300
>
isAutoWhitespaceEdit: op.isAutoWhitespaceEdit || false
301
>
};
302
>
}
303
>
304
>
// Sort operations ascending
305
>
operations.sort(PieceTreeTextBuffer._sortOpsAscending);
306
>
307
>
let hasTouchingRanges = false;
308
>
for (let i = 0, count = operations.length - 1; i < count; i++) {
310
>
const nextRangeStart = operations[i + 1].range.getStartPosition();
311
>
312
>
if (nextRangeStart.isBeforeOrEqual(rangeEnd)) {
315
>
throw new Error('Overlapping ranges are not allowed!');
316
>
}
318
>
}
321
>
if (canReduceOperations) {
322
>
operations = this._reduceOperations(operations);
323
>
}
324
>
325
>
// Delta encode operations
326
>
const reverseRanges = (computeUndoEdits || recordTrimAutoWhitespace ? PieceTreeTextBuffer._getInverseEditRanges(operations) : []);
textModel.ts ×10
327
>
const newTrimAutoWhitespaceCandidates: { lineNumber: number; oldContent: string }[] = [];
328
>
if (recordTrimAutoWhitespace) {
330
>
const op = operations[i];
331
>
const reverseRange = reverseRanges[i];
332
>
333
>
if (op.isAutoWhitespaceEdit && op.range.isEmpty()) {
334
// Record already the future line numbers that might be auto whitespace removal candidates on next edit
335
for (let lineNumber = reverseRange.startLineNumber; lineNumber <= reverseRange.endLineNumber; lineNumber++) {
336
let currentLineContent = '';
337
if (lineNumber === reverseRange.startLineNumber) {
338
currentLineContent = this.getLineContent(op.range.startLineNumber);
339
if (strings.firstNonWhitespaceIndex(currentLineContent) !== -1) {
340
continue;
341
}
342
}
343
newTrimAutoWhitespaceCandidates.push({ lineNumber: lineNumber, oldContent: currentLineContent });
344
}
345
}
347
>
}
348
>
349
>
let reverseOperations: IReverseSingleEditOperation[] | null = null;
350
>
if (computeUndoEdits) {
352
>
let reverseRangeDeltaOffset = 0;
353
>
reverseOperations = [];
354
>
for (let i = 0; i < operations.length; i++) {
355
>
const op = operations[i];
356
>
const reverseRange = reverseRanges[i];
357
>
const bufferText = this.getValueInRange(op.range);
358
>
const reverseRangeOffset = op.rangeOffset + reverseRangeDeltaOffset;
359
>
reverseRangeDeltaOffset += (op.text.length - bufferText.length);
360
>
361
>
reverseOperations[i] = {
362
>
sortIndex: op.sortIndex,
363
>
identifier: op.identifier,
364
>
range: reverseRange,
365
>
text: bufferText,
366
>
textChange: new TextChange(op.rangeOffset, bufferText, reverseRangeOffset, op.text)
367
>
};
368
>
}
369
>
370
>
// Can only sort reverse operations when the order is not significant
371
>
if (!hasTouchingRanges) {
373
>
}
376
>
377
>
this._mightContainRTL = mightContainRTL;
378
>
this._mightContainUnusualLineTerminators = mightContainUnusualLineTerminators;
379
>
this._mightContainNonBasicASCII = mightContainNonBasicASCII;
380
>
381
>
const contentChanges = this._doApplyEdits(operations);
382
>
383
>
let trimAutoWhitespaceLineNumbers: number[] | null = null;
384
>
if (recordTrimAutoWhitespace && newTrimAutoWhitespaceCandidates.length > 0) {
textModel.ts ×10
385
// sort line numbers auto whitespace removal candidates for next edit descending
386
newTrimAutoWhitespaceCandidates.sort((a, b) => b.lineNumber - a.lineNumber);
387
388
trimAutoWhitespaceLineNumbers = [];
389
for (let i = 0, len = newTrimAutoWhitespaceCandidates.length; i < len; i++) {
390
const lineNumber = newTrimAutoWhitespaceCandidates[i].lineNumber;
391
if (i > 0 && newTrimAutoWhitespaceCandidates[i - 1].lineNumber === lineNumber) {
392
// Do not have the same line number twice
393
continue;
394
}
395
396
const prevContent = newTrimAutoWhitespaceCandidates[i].oldContent;
397
const lineContent = this.getLineContent(lineNumber);
398
399
if (lineContent.length === 0 || lineContent === prevContent || strings.firstNonWhitespaceIndex(lineContent) !== -1) {
400
continue;
401
}
402
403
trimAutoWhitespaceLineNumbers.push(lineNumber);
404
}
405
}
407
>
this._onDidChangeContent.fire();
408
>
409
>
return new ApplyEditsResult(
410
>
reverseOperations,
411
>
contentChanges,
412
>
trimAutoWhitespaceLineNumbers
413
>
);
416
>
/**
417
>
* Transform operations such that they represent the same logic edit,
418
>
* but that they also do not cause OOM crashes.
419
>
*/
420
>
private _reduceOperations(operations: IValidatedEditOperation[]): IValidatedEditOperation[] {
422
>
// We know from empirical testing that a thousand edits work fine regardless of their shape.
423
>
return operations;
424
>
}
425
426
// At one point, due to how events are emitted and how each operation is handled,
427
// some operations can trigger a high amount of temporary string allocations,
428
// that will immediately get edited again.
429
// e.g. a formatter inserting ridiculous ammounts of \n on a model with a single line
430
// Therefore, the strategy is to collapse all the operations into a huge single edit operation
431
return [this._toSingleEditOperation(operations)];
434
>
_toSingleEditOperation(operations: IValidatedEditOperation[]): IValidatedEditOperation {
436
>
const firstEditRange = operations[0].range;
437
>
const lastEditRange = operations[operations.length - 1].range;
438
>
const entireEditRange = new Range(firstEditRange.startLineNumber, firstEditRange.startColumn, lastEditRange.endLineNumber, lastEditRange.endColumn);
439
>
let lastEndLineNumber = firstEditRange.startLineNumber;
440
>
let lastEndColumn = firstEditRange.startColumn;
441
>
const result: string[] = [];
442
>
443
>
for (let i = 0, len = operations.length; i < len; i++) {
444
>
const operation = operations[i];
445
>
const range = operation.range;
446
>
447
>
forceMoveMarkers = forceMoveMarkers || operation.forceMoveMarkers;
448
>
449
>
// (1) -- Push old text
450
>
result.push(this.getValueInRange(new Range(lastEndLineNumber, lastEndColumn, range.startLineNumber, range.startColumn)));
451
>
452
>
// (2) -- Push new text
453
>
if (operation.text.length > 0) {
455
>
}
457
>
lastEndLineNumber = range.endLineNumber;
458
>
lastEndColumn = range.endColumn;
459
>
}
460
>
461
>
const text = result.join('');
462
>
const [eolCount, firstLineLength, lastLineLength] = countEOL(text);
463
>
464
>
return {
465
>
sortIndex: 0,
466
>
identifier: operations[0].identifier,
467
>
range: entireEditRange,
468
>
rangeOffset: this.getOffsetAt(entireEditRange.startLineNumber, entireEditRange.startColumn),
469
>
rangeLength: this.getValueLengthInRange(entireEditRange, EndOfLinePreference.TextDefined),
470
>
text: text,
471
>
eolCount: eolCount,
472
>
firstLineLength: firstLineLength,
473
>
lastLineLength: lastLineLength,
474
>
forceMoveMarkers: forceMoveMarkers,
475
>
isAutoWhitespaceEdit: false
476
>
};
477
>
}
479
>
private _doApplyEdits(operations: IValidatedEditOperation[]): IInternalModelContentChange[] {
481
>
482
>
const contentChanges: IInternalModelContentChange[] = [];
483
>
484
>
// operations are from bottom to top
485
>
for (let i = 0; i < operations.length; i++) {
486
>
const op = operations[i];
487
>
488
>
const startLineNumber = op.range.startLineNumber;
489
>
const startColumn = op.range.startColumn;
490
>
const endLineNumber = op.range.endLineNumber;
491
>
const endColumn = op.range.endColumn;
492
>
493
>
if (startLineNumber === endLineNumber && startColumn === endColumn && op.text.length === 0) {
495
>
continue;
496
>
}
498
>
if (op.text) {
500
>
this._pieceTree.delete(op.rangeOffset, op.rangeLength);
501
>
this._pieceTree.insert(op.rangeOffset, op.text, true);
502
>
505
>
this._pieceTree.delete(op.rangeOffset, op.rangeLength);
506
>
}
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
>
}
518
>
}
520
>
findMatchesLineByLine(searchRange: Range, searchData: SearchData, captureMatches: boolean, limitResultCount: number): FindMatch[] {
521
>
return this._pieceTree.findMatchesLineByLine(searchRange, searchData, captureMatches, limitResultCount);
pieceTreeBase.ts ×2
522
>
}
524
>
// #endregion
525
>
526
>
// #region helper
527
>
// testing purpose.
528
>
public getPieceTree(): PieceTreeBase {
530
>
}
532
>
public static _getInverseEditRange(range: Range, text: string) {
533
const startLineNumber = range.startLineNumber;
534
const startColumn = range.startColumn;
535
const [eolCount, firstLineLength, lastLineLength] = countEOL(text);
536
let resultRange: Range;
537
538
if (text.length > 0) {
539
// the operation inserts something
540
const lineCount = eolCount + 1;
541
542
if (lineCount === 1) {
543
// single line insert
544
resultRange = new Range(startLineNumber, startColumn, startLineNumber, startColumn + firstLineLength);
545
} else {
546
// multi line insert
547
resultRange = new Range(startLineNumber, startColumn, startLineNumber + lineCount - 1, lastLineLength + 1);
548
}
549
} else {
550
// There is nothing to insert
551
resultRange = new Range(startLineNumber, startColumn, startLineNumber, startColumn);
552
}
553
554
return resultRange;
555
}
557
>
/**
558
>
* Assumes `operations` are validated and sorted ascending
559
>
*/
560
>
public static _getInverseEditRanges(operations: IValidatedEditOperation[]): Range[] {
562
>
563
>
let prevOpEndLineNumber: number = 0;
564
>
let prevOpEndColumn: number = 0;
565
>
let prevOp: IValidatedEditOperation | null = null;
566
>
for (let i = 0, len = operations.length; i < len; i++) {
567
>
const op = operations[i];
568
>
569
>
let startLineNumber: number;
570
>
let startColumn: number;
571
>
572
>
if (prevOp) {
575
>
startColumn = prevOpEndColumn + (op.range.startColumn - prevOp.range.endColumn);
577
>
startLineNumber = prevOpEndLineNumber + (op.range.startLineNumber - prevOp.range.endLineNumber);
pieceTreeTextBuffer.ts ×1
578
>
startColumn = op.range.startColumn;
579
>
}
581
>
startLineNumber = op.range.startLineNumber;
582
>
startColumn = op.range.startColumn;
583
>
}
584
>
585
>
let resultRange: Range;
586
>
587
>
if (op.text.length > 0) {
589
>
const lineCount = op.eolCount + 1;
590
>
591
>
if (lineCount === 1) {
593
>
resultRange = new Range(startLineNumber, startColumn, startLineNumber, startColumn + op.firstLineLength);
596
>
resultRange = new Range(startLineNumber, startColumn, startLineNumber + lineCount - 1, op.lastLineLength + 1);
597
>
}
600
>
resultRange = new Range(startLineNumber, startColumn, startLineNumber, startColumn);
601
>
}
603
>
prevOpEndLineNumber = resultRange.endLineNumber;
604
>
prevOpEndColumn = resultRange.endColumn;
605
>
606
>
result.push(resultRange);
607
>
prevOp = op;
608
>
}
609
>
610
>
return result;
611
>
}
613
>
private static _sortOpsAscending(a: IValidatedEditOperation, b: IValidatedEditOperation): number {
615
>
if (r === 0) {
617
>
}
621
>
private static _sortOpsDescending(a: IValidatedEditOperation, b: IValidatedEditOperation): number {
623
>
if (r === 0) {
625
>
}
629
>
}