src/vs/editor/common/model/pieceTreeTextBuffer/pieceTreeBase.ts
1882 LOC · 1736 covered · 146 uncovered · 500 ranges · 1708 concepts · 225 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 { CharCode } from '../../../../base/common/charCode.js';
7
>
import { Position } from '../../core/position.js';
8
>
import { Range } from '../../core/range.js';
9
>
import { FindMatch, ITextSnapshot, SearchData } from '../../model.js';
10
>
import { NodeColor, SENTINEL, TreeNode, fixInsert, leftest, rbDelete, righttest, updateTreeMetadata } from './rbTreeBase.js';
11
>
import { Searcher, createFindMatch, isValidMatch } from '../textModelSearch.js';
12
>
13
>
// const lfRegex = new RegExp(/\r\n|\r|\n/g);
14
>
const AverageBufferSize = 65535;
15
>
16
>
function createUintArray(arr: number[]): Uint32Array | Uint16Array {
pieceTreeTextBufferBuilder.ts ×19
17
>
let r;
18
>
if (arr[arr.length - 1] < 65536) {
22
>
}
24
>
return r;
25
>
}
27
>
class LineStarts {
28
>
constructor(
29
>
public readonly lineStarts: Uint32Array | Uint16Array | number[],
pieceTreeTextBufferBuilder.ts ×19
30
>
public readonly cr: number,
31
>
public readonly lf: number,
32
>
public readonly crlf: number,
33
>
public readonly isBasicASCII: boolean
34
>
) { }
36
>
37
>
export function createLineStartsFast(str: string, readonly: boolean = true): Uint32Array | Uint16Array | number[] {
39
>
let rLength = 1;
40
>
41
>
for (let i = 0, len = str.length; i < len; i++) {
42
>
const chr = str.charCodeAt(i);
43
>
44
>
if (chr === CharCode.CarriageReturn) {
47
>
r[rLength++] = i + 2;
48
>
i++; // skip \n
51
>
r[rLength++] = i + 1;
52
>
}
55
>
}
57
>
if (readonly) {
61
>
}
64
>
export function createLineStarts(r: number[], str: string): LineStarts {
66
>
r[0] = 0;
67
>
let rLength = 1;
68
>
let cr = 0, lf = 0, crlf = 0;
69
>
let isBasicASCII = true;
70
>
for (let i = 0, len = str.length; i < len; i++) {
72
>
73
>
if (chr === CharCode.CarriageReturn) {
76
>
crlf++;
77
>
r[rLength++] = i + 2;
78
>
i++; // skip \n
81
>
// \r... case
82
>
r[rLength++] = i + 1;
83
>
}
86
>
r[rLength++] = i + 1;
89
>
if (chr !== CharCode.Tab && (chr < 32 || chr > 126)) {
91
>
}
93
>
}
95
>
const result = new LineStarts(createUintArray(r), cr, lf, crlf, isBasicASCII);
pieceTreeTextBufferBuilder.ts ×19
96
>
r.length = 0;
97
>
98
>
return result;
99
>
}
101
>
interface NodePosition {
102
>
/**
103
>
* Piece Index
104
>
*/
105
>
node: TreeNode;
106
>
/**
107
>
* remainder in current piece.
108
>
*/
109
>
remainder: number;
110
>
/**
111
>
* node start offset in document.
112
>
*/
113
>
nodeStartOffset: number;
114
>
}
115
>
116
>
interface BufferCursor {
117
>
/**
118
>
* Line number in current buffer
119
>
*/
120
>
line: number;
121
>
/**
122
>
* Column number in current buffer
123
>
*/
124
>
column: number;
125
>
}
126
>
127
>
export class Piece {
128
>
readonly bufferIndex: number;
129
>
readonly start: BufferCursor;
130
>
readonly end: BufferCursor;
131
>
readonly length: number;
132
>
readonly lineFeedCnt: number;
133
>
134
>
constructor(bufferIndex: number, start: BufferCursor, end: BufferCursor, lineFeedCnt: number, length: number) {
136
>
this.start = start;
137
>
this.end = end;
138
>
this.lineFeedCnt = lineFeedCnt;
139
>
this.length = length;
140
>
}
142
>
143
>
export class StringBuffer {
144
>
buffer: string;
145
>
lineStarts: Uint32Array | Uint16Array | number[];
146
>
147
>
constructor(buffer: string, lineStarts: Uint32Array | Uint16Array | number[]) {
149
>
this.lineStarts = lineStarts;
150
>
}
152
>
153
>
/**
154
>
* Readonly snapshot for piece tree.
155
>
* In a real multiple thread environment, to make snapshot reading always work correctly, we need to
156
>
* 1. Make TreeNode.piece immutable, then reading and writing can run in parallel.
157
>
* 2. TreeNode/Buffers normalization should not happen during snapshot reading.
158
>
*/
159
>
class PieceTreeSnapshot implements ITextSnapshot {
160
>
private readonly _pieces: Piece[];
161
>
private _index: number;
162
>
private readonly _tree: PieceTreeBase;
163
>
private readonly _BOM: string;
164
>
165
>
constructor(tree: PieceTreeBase, BOM: string) {
167
>
this._tree = tree;
168
>
this._BOM = BOM;
169
>
this._index = 0;
170
>
if (tree.root !== SENTINEL) {
172
>
if (node !== SENTINEL) {
173
>
this._pieces.push(node.piece);
174
>
}
175
>
return true;
176
>
});
177
>
}
180
>
read(): string | null {
183
>
this._index++;
184
>
return this._BOM;
185
>
} else {
186
>
return null;
187
>
}
188
>
}
190
>
if (this._index > this._pieces.length - 1) {
191
>
return null;
192
>
}
193
>
194
>
if (this._index === 0) {
195
>
return this._BOM + this._tree.getPieceContent(this._pieces[this._index++]);
196
>
}
200
>
201
>
interface CacheEntry {
202
>
node: TreeNode;
203
>
nodeStartOffset: number;
204
>
nodeStartLineNumber?: number;
205
>
}
206
>
207
>
class PieceTreeSearchCache {
208
>
private readonly _limit: number;
209
>
private _cache: CacheEntry[];
210
>
211
>
constructor(limit: number) {
213
>
this._cache = [];
214
>
}
216
>
public get(offset: number): CacheEntry | null {
219
>
if (nodePos.nodeStartOffset <= offset && nodePos.nodeStartOffset + nodePos.node.piece.length >= offset) {
221
>
}
226
>
public get2(lineNumber: number): { node: TreeNode; nodeStartOffset: number; nodeStartLineNumber: number } | null {
229
>
if (nodePos.nodeStartLineNumber && nodePos.nodeStartLineNumber < lineNumber && nodePos.nodeStartLineNumber + nodePos.node.piece.lineFeedCnt >= lineNumber) {
230
>
return <{ node: TreeNode; nodeStartOffset: number; nodeStartLineNumber: number }>nodePos;
pieceTreeBase.ts ×3
231
>
}
234
>
}
236
>
public set(nodePosition: CacheEntry) {
239
>
}
241
>
}
243
>
public validate(offset: number) {
245
>
const tmp: Array<CacheEntry | null> = this._cache;
246
>
for (let i = 0; i < tmp.length; i++) {
248
>
if (nodePos.node.parent === null || nodePos.nodeStartOffset >= offset) {
250
>
hasInvalidVal = true;
251
>
continue;
252
>
}
255
>
if (hasInvalidVal) {
257
>
for (const entry of tmp) {
258
>
if (entry !== null) {
259
newArr.push(entry);
260
}
262
>
263
>
this._cache = newArr;
264
>
}
267
>
268
>
export class PieceTreeBase {
269
>
root!: TreeNode;
270
>
protected _buffers!: StringBuffer[]; // 0 is change buffer, others are readonly original buffer.
271
>
protected _lineCnt!: number;
272
>
protected _length!: number;
273
>
protected _EOL!: '\r\n' | '\n';
274
>
protected _EOLLength!: number;
275
>
protected _EOLNormalized!: boolean;
276
>
private _lastChangeBufferPos!: BufferCursor;
277
>
private _searchCache!: PieceTreeSearchCache;
278
>
private _lastVisitedLine!: { lineNumber: number; value: string };
279
>
280
>
constructor(chunks: StringBuffer[], eol: '\r\n' | '\n', eolNormalized: boolean) {
282
>
}
284
>
create(chunks: StringBuffer[], eol: '\r\n' | '\n', eolNormalized: boolean) {
286
>
new StringBuffer('', [0])
287
>
];
288
>
this._lastChangeBufferPos = { line: 0, column: 0 };
289
>
this.root = SENTINEL;
290
>
this._lineCnt = 1;
291
>
this._length = 0;
292
>
this._EOL = eol;
293
>
this._EOLLength = eol.length;
294
>
this._EOLNormalized = eolNormalized;
295
>
296
>
let lastNode: TreeNode | null = null;
297
>
for (let i = 0, len = chunks.length; i < len; i++) {
298
>
if (chunks[i].buffer.length > 0) {
300
chunks[i].lineStarts = createLineStartsFast(chunks[i].buffer);
301
}
303
>
const piece = new Piece(
304
>
i + 1,
305
>
{ line: 0, column: 0 },
306
>
{ line: chunks[i].lineStarts.length - 1, column: chunks[i].buffer.length - chunks[i].lineStarts[chunks[i].lineStarts.length - 1] },
307
>
chunks[i].lineStarts.length - 1,
308
>
chunks[i].buffer.length
309
>
);
310
>
this._buffers.push(chunks[i]);
311
>
lastNode = this.rbInsertRight(lastNode, piece);
312
>
}
314
>
315
>
this._searchCache = new PieceTreeSearchCache(1);
316
>
this._lastVisitedLine = { lineNumber: 0, value: '' };
317
>
this.computeBufferMetadata();
318
>
}
320
>
normalizeEOL(eol: '\r\n' | '\n') {
322
>
const min = averageBufferSize - Math.floor(averageBufferSize / 3);
323
>
const max = min * 2;
324
>
325
>
let tempChunk = '';
326
>
let tempChunkLen = 0;
327
>
const chunks: StringBuffer[] = [];
328
>
329
>
this.iterate(this.root, node => {
330
>
const str = this.getNodeContent(node);
331
>
const len = str.length;
332
>
if (tempChunkLen <= min || tempChunkLen + len < max) {
333
>
tempChunk += str;
334
>
tempChunkLen += len;
335
>
return true;
336
>
}
337
338
// flush anyways
339
const text = tempChunk.replace(/\r\n|\r|\n/g, eol);
340
chunks.push(new StringBuffer(text, createLineStartsFast(text)));
341
tempChunk = str;
342
tempChunkLen = len;
343
return true;
345
>
346
>
if (tempChunkLen > 0) {
347
>
const text = tempChunk.replace(/\r\n|\r|\n/g, eol);
348
>
chunks.push(new StringBuffer(text, createLineStartsFast(text)));
349
>
}
350
>
351
>
this.create(chunks, eol, true);
352
>
}
354
>
// #region Buffer API
355
>
public getEOL(): '\r\n' | '\n' {
357
>
}
359
>
public setEOL(newEOL: '\r\n' | '\n'): void {
361
>
this._EOLLength = this._EOL.length;
362
>
this.normalizeEOL(newEOL);
363
>
}
365
>
public createSnapshot(BOM: string): ITextSnapshot {
367
>
}
369
>
public equal(other: PieceTreeBase): boolean {
372
>
}
374
return false;
375
}
377
>
let offset = 0;
378
>
const ret = this.iterate(this.root, node => {
379
>
if (node === SENTINEL) {
380
>
return true;
381
>
}
383
>
const len = str.length;
384
>
const startPosition = other.nodeAt(offset);
385
>
const endPosition = other.nodeAt(offset + len);
386
>
const val = other.getValueInRange2(startPosition, endPosition);
387
>
388
>
offset += len;
389
>
return str === val;
391
>
392
>
return ret;
395
>
public getOffsetAt(lineNumber: number, column: number): number {
397
>
398
>
let x = this.root;
399
>
400
>
while (x !== SENTINEL) {
404
>
leftLen += x.size_left;
405
>
// lineNumber >= 2
406
>
const accumualtedValInCurrentIndex = this.getAccumulatedValue(x, lineNumber - x.lf_left - 2);
407
>
return leftLen += accumualtedValInCurrentIndex + column - 1;
408
>
} else {
410
>
leftLen += x.size_left + x.piece.length;
411
>
x = x.right;
412
>
}
415
>
return leftLen;
418
>
public getPositionAt(offset: number): Position {
420
>
offset = Math.max(0, offset);
421
>
422
>
let x = this.root;
423
>
let lfCnt = 0;
424
>
const originalOffset = offset;
425
>
426
>
while (x !== SENTINEL) {
427
>
if (x.size_left !== 0 && x.size_left >= offset) {
430
>
const out = this.getIndexOf(x, offset - x.size_left);
431
>
432
>
lfCnt += x.lf_left + out.index;
433
>
434
>
if (out.index === 0) {
436
>
const column = originalOffset - lineStartOffset;
437
>
return new Position(lfCnt + 1, column + 1);
438
>
}
440
>
return new Position(lfCnt + 1, out.remainder + 1);
443
>
lfCnt += x.lf_left + x.piece.lineFeedCnt;
444
>
445
>
if (x.right === SENTINEL) {
446
// last node
447
const lineStartOffset = this.getOffsetAt(lfCnt + 1, 1);
448
const column = originalOffset - offset - lineStartOffset;
449
return new Position(lfCnt + 1, column + 1);
451
>
x = x.right;
452
>
}
453
>
}
456
>
return new Position(1, 1);
459
>
public getValueInRange(range: Range, eol?: string): string {
460
>
if (range.startLineNumber === range.endLineNumber && range.startColumn === range.endColumn) {
pieceTreeBase.ts ×2
462
>
}
464
>
const startPosition = this.nodeAt2(range.startLineNumber, range.startColumn);
465
>
const endPosition = this.nodeAt2(range.endLineNumber, range.endColumn);
466
>
467
>
const value = this.getValueInRange2(startPosition, endPosition);
468
>
if (eol) {
471
>
}
476
>
}
478
>
}
479
return value.replace(/\r\n|\r|\n/g, eol);
480
}
484
>
public getValueInRange2(startPosition: NodePosition, endPosition: NodePosition): string {
487
>
const buffer = this._buffers[node.piece.bufferIndex].buffer;
488
>
const startOffset = this.offsetInBuffer(node.piece.bufferIndex, node.piece.start);
489
>
return buffer.substring(startOffset + startPosition.remainder, startOffset + endPosition.remainder);
490
>
}
492
>
let x = startPosition.node;
493
>
const buffer = this._buffers[x.piece.bufferIndex].buffer;
494
>
const startOffset = this.offsetInBuffer(x.piece.bufferIndex, x.piece.start);
495
>
let ret = buffer.substring(startOffset + startPosition.remainder, startOffset + x.piece.length);
496
>
497
>
x = x.next();
498
>
while (x !== SENTINEL) {
499
>
const buffer = this._buffers[x.piece.bufferIndex].buffer;
500
>
const startOffset = this.offsetInBuffer(x.piece.bufferIndex, x.piece.start);
501
>
502
>
if (x === endPosition.node) {
503
>
ret += buffer.substring(startOffset, startOffset + endPosition.remainder);
504
>
break;
505
>
} else {
507
>
}
508
>
509
>
x = x.next();
510
>
}
512
>
return ret;
515
>
public getLinesContent(): string[] {
517
>
let linesLength = 0;
518
>
let currentLine = '';
519
>
let danglingCR = false;
520
>
521
>
this.iterate(this.root, node => {
522
>
if (node === SENTINEL) {
523
>
return true;
524
>
}
525
>
526
>
const piece = node.piece;
527
>
let pieceLength = piece.length;
528
>
if (pieceLength === 0) {
529
return true;
530
}
532
>
const buffer = this._buffers[piece.bufferIndex].buffer;
533
>
const lineStarts = this._buffers[piece.bufferIndex].lineStarts;
534
>
535
>
const pieceStartLine = piece.start.line;
536
>
const pieceEndLine = piece.end.line;
537
>
let pieceStartOffset = lineStarts[pieceStartLine] + piece.start.column;
538
>
539
>
if (danglingCR) {
540
if (buffer.charCodeAt(pieceStartOffset) === CharCode.LineFeed) {
541
// pretend the \n was in the previous piece..
542
pieceStartOffset++;
543
pieceLength--;
544
}
545
lines[linesLength++] = currentLine;
546
currentLine = '';
547
danglingCR = false;
548
if (pieceLength === 0) {
549
return true;
550
}
551
}
553
>
if (pieceStartLine === pieceEndLine) {
555
>
if (!this._EOLNormalized && buffer.charCodeAt(pieceStartOffset + pieceLength - 1) === CharCode.CarriageReturn) {
556
danglingCR = true;
557
currentLine += buffer.substr(pieceStartOffset, pieceLength - 1);
559
>
currentLine += buffer.substr(pieceStartOffset, pieceLength);
560
>
}
561
>
return true;
562
>
}
564
>
// add the text before the first line start in this piece
565
>
currentLine += (
566
>
this._EOLNormalized
567
>
? buffer.substring(pieceStartOffset, Math.max(pieceStartOffset, lineStarts[pieceStartLine + 1] - this._EOLLength))
568
: buffer.substring(pieceStartOffset, lineStarts[pieceStartLine + 1]).replace(/(\r\n|\r|\n)$/, '')
570
>
lines[linesLength++] = currentLine;
571
>
572
>
for (let line = pieceStartLine + 1; line < pieceEndLine; line++) {
574
>
this._EOLNormalized
575
>
? buffer.substring(lineStarts[line], lineStarts[line + 1] - this._EOLLength)
576
: buffer.substring(lineStarts[line], lineStarts[line + 1]).replace(/(\r\n|\r|\n)$/, '')
578
>
lines[linesLength++] = currentLine;
579
>
}
581
>
if (!this._EOLNormalized && buffer.charCodeAt(lineStarts[pieceEndLine] + piece.end.column - 1) === CharCode.CarriageReturn) {
pieceTreeBase.ts ×7
582
danglingCR = true;
583
if (piece.end.column === 0) {
584
// The last line ended with a \r, let's undo the push, it will be pushed by next iteration
585
linesLength--;
586
} else {
587
currentLine = buffer.substr(lineStarts[pieceEndLine], piece.end.column - 1);
588
}
590
>
currentLine = buffer.substr(lineStarts[pieceEndLine], piece.end.column);
591
>
}
592
>
593
>
return true;
595
>
596
>
if (danglingCR) {
597
lines[linesLength++] = currentLine;
598
currentLine = '';
599
}
601
>
lines[linesLength++] = currentLine;
602
>
return lines;
603
>
}
605
>
public getLength(): number {
607
>
}
609
>
public getLineCount(): number {
611
>
}
613
>
public getLineContent(lineNumber: number): string {
616
>
}
618
>
this._lastVisitedLine.lineNumber = lineNumber;
619
>
620
>
if (lineNumber === this._lineCnt) {
623
>
this._lastVisitedLine.value = this.getLineRawContent(lineNumber, this._EOLLength);
pieceTreeBase.ts ×1
625
>
this._lastVisitedLine.value = this.getLineRawContent(lineNumber).replace(/(\r\n|\r|\n)$/, '');
pieceTreeBase.ts ×1
626
>
}
628
>
return this._lastVisitedLine.value;
629
>
}
631
>
private _getCharCode(nodePos: NodePosition): number {
634
>
const matchingNode = nodePos.node.next();
635
>
if (!matchingNode) {
636
return 0;
637
}
639
>
const buffer = this._buffers[matchingNode.piece.bufferIndex];
640
>
const startOffset = this.offsetInBuffer(matchingNode.piece.bufferIndex, matchingNode.piece.start);
641
>
return buffer.buffer.charCodeAt(startOffset);
644
>
const startOffset = this.offsetInBuffer(nodePos.node.piece.bufferIndex, nodePos.node.piece.start);
645
>
const targetOffset = startOffset + nodePos.remainder;
646
>
647
>
return buffer.buffer.charCodeAt(targetOffset);
648
>
}
651
>
public getLineCharCode(lineNumber: number, index: number): number {
653
>
return this._getCharCode(nodePos);
654
>
}
656
>
public getLineLength(lineNumber: number): number {
658
>
const startOffset = this.getOffsetAt(lineNumber, 1);
659
>
return this.getLength() - startOffset;
660
>
}
661
>
return this.getOffsetAt(lineNumber + 1, 1) - this.getOffsetAt(lineNumber, 1) - this._EOLLength;
pieceTreeBase.ts ×1
664
>
public getCharCode(offset: number): number {
665
const nodePos = this.nodeAt(offset);
666
return this._getCharCode(nodePos);
667
}
669
>
public getNearestChunk(offset: number): string {
671
>
if (nodePos.remainder === nodePos.node.piece.length) {
672
>
// the offset is at the head of next node.
673
>
const matchingNode = nodePos.node.next();
674
>
if (!matchingNode || matchingNode === SENTINEL) {
675
return '';
676
}
678
>
const buffer = this._buffers[matchingNode.piece.bufferIndex];
679
>
const startOffset = this.offsetInBuffer(matchingNode.piece.bufferIndex, matchingNode.piece.start);
680
>
return buffer.buffer.substring(startOffset, startOffset + matchingNode.piece.length);
681
>
} else {
682
>
const buffer = this._buffers[nodePos.node.piece.bufferIndex];
683
>
const startOffset = this.offsetInBuffer(nodePos.node.piece.bufferIndex, nodePos.node.piece.start);
684
>
const targetOffset = startOffset + nodePos.remainder;
685
>
const targetEnd = startOffset + nodePos.node.piece.length;
686
>
return buffer.buffer.substring(targetOffset, targetEnd);
687
>
}
688
>
}
690
>
public findMatchesInNode(node: TreeNode, searcher: Searcher, startLineNumber: number, startColumn: number, startCursor: BufferCursor, endCursor: BufferCursor, searchData: SearchData, captureMatches: boolean, limitResultCount: number, resultLen: number, result: FindMatch[]) {
692
>
const startOffsetInBuffer = this.offsetInBuffer(node.piece.bufferIndex, node.piece.start);
693
>
const start = this.offsetInBuffer(node.piece.bufferIndex, startCursor);
694
>
const end = this.offsetInBuffer(node.piece.bufferIndex, endCursor);
695
>
696
>
let m: RegExpExecArray | null;
697
>
// Reset regex to search from the beginning
698
>
const ret: BufferCursor = { line: 0, column: 0 };
699
>
let searchText: string;
700
>
let offsetInBuffer: (offset: number) => number;
701
>
702
>
if (searcher._wordSeparators) {
704
>
offsetInBuffer = (offset: number) => offset + start;
705
>
searcher.reset(0);
708
>
offsetInBuffer = (offset: number) => offset;
709
>
searcher.reset(start);
710
>
}
712
>
do {
713
>
m = searcher.next(searchText);
714
>
715
>
if (m) {
716
>
if (offsetInBuffer(m.index) >= end) {
717
return resultLen;
718
}
719
>
this.positionInBuffer(node, offsetInBuffer(m.index) - startOffsetInBuffer, ret);
pieceTreeBase.ts ×9
720
>
const lineFeedCnt = this.getLineFeedCnt(node.piece.bufferIndex, startCursor, ret);
721
>
const retStartColumn = ret.line === startCursor.line ? ret.column - startCursor.column + startColumn : ret.column + 1;
722
>
const retEndColumn = retStartColumn + m[0].length;
723
>
result[resultLen++] = createFindMatch(new Range(startLineNumber + lineFeedCnt, retStartColumn, startLineNumber + lineFeedCnt, retEndColumn), m, captureMatches);
724
>
725
>
if (offsetInBuffer(m.index) + m[0].length >= end) {
726
return resultLen;
727
}
729
return resultLen;
730
}
732
>
733
>
} while (m);
734
>
735
>
return resultLen;
736
>
}
738
>
public findMatchesLineByLine(searchRange: Range, searchData: SearchData, captureMatches: boolean, limitResultCount: number): FindMatch[] {
740
>
let resultLen = 0;
741
>
const searcher = new Searcher(searchData.wordSeparators, searchData.regex);
742
>
743
>
let startPosition = this.nodeAt2(searchRange.startLineNumber, searchRange.startColumn);
744
>
if (startPosition === null) {
746
>
}
747
>
const endPosition = this.nodeAt2(searchRange.endLineNumber, searchRange.endColumn);
pieceTreeBase.ts ×9
748
>
if (endPosition === null) {
749
return [];
750
}
751
>
let start = this.positionInBuffer(startPosition.node, startPosition.remainder);
pieceTreeBase.ts ×9
752
>
const end = this.positionInBuffer(endPosition.node, endPosition.remainder);
753
>
754
>
if (startPosition.node === endPosition.node) {
755
>
this.findMatchesInNode(startPosition.node, searcher, searchRange.startLineNumber, searchRange.startColumn, start, end, searchData, captureMatches, limitResultCount, resultLen, result);
pieceTreeBase.ts ×2
756
>
return result;
757
>
}
759
>
let startLineNumber = searchRange.startLineNumber;
760
>
761
>
let currentNode = startPosition.node;
762
>
while (currentNode !== endPosition.node) {
763
>
const lineBreakCnt = this.getLineFeedCnt(currentNode.piece.bufferIndex, start, currentNode.piece.end);
764
>
765
>
if (lineBreakCnt >= 1) {
766
>
// last line break position
767
>
const lineStarts = this._buffers[currentNode.piece.bufferIndex].lineStarts;
768
>
const startOffsetInBuffer = this.offsetInBuffer(currentNode.piece.bufferIndex, currentNode.piece.start);
769
>
const nextLineStartOffset = lineStarts[start.line + lineBreakCnt];
770
>
const startColumn = startLineNumber === searchRange.startLineNumber ? searchRange.startColumn : 1;
771
>
resultLen = this.findMatchesInNode(currentNode, searcher, startLineNumber, startColumn, start, this.positionInBuffer(currentNode, nextLineStartOffset - startOffsetInBuffer), searchData, captureMatches, limitResultCount, resultLen, result);
772
>
773
>
if (resultLen >= limitResultCount) {
774
return result;
775
}
777
>
startLineNumber += lineBreakCnt;
778
>
}
779
>
780
>
const startColumn = startLineNumber === searchRange.startLineNumber ? searchRange.startColumn - 1 : 0;
781
>
// search for the remaining content
782
>
if (startLineNumber === searchRange.endLineNumber) {
783
const text = this.getLineContent(startLineNumber).substring(startColumn, searchRange.endColumn - 1);
784
resultLen = this._findMatchesInLine(searchData, searcher, text, searchRange.endLineNumber, startColumn, resultLen, result, captureMatches, limitResultCount);
785
return result;
786
}
788
>
resultLen = this._findMatchesInLine(searchData, searcher, this.getLineContent(startLineNumber).substr(startColumn), startLineNumber, startColumn, resultLen, result, captureMatches, limitResultCount);
789
>
790
>
if (resultLen >= limitResultCount) {
791
return result;
792
}
794
>
startLineNumber++;
795
>
startPosition = this.nodeAt2(startLineNumber, 1);
796
>
currentNode = startPosition.node;
797
>
start = this.positionInBuffer(startPosition.node, startPosition.remainder);
798
>
}
799
>
800
>
if (startLineNumber === searchRange.endLineNumber) {
801
>
const startColumn = startLineNumber === searchRange.startLineNumber ? searchRange.startColumn - 1 : 0;
802
>
const text = this.getLineContent(startLineNumber).substring(startColumn, searchRange.endColumn - 1);
803
>
resultLen = this._findMatchesInLine(searchData, searcher, text, searchRange.endLineNumber, startColumn, resultLen, result, captureMatches, limitResultCount);
804
>
return result;
805
>
}
806
807
>
const startColumn = startLineNumber === searchRange.startLineNumber ? searchRange.startColumn : 1;
pieceTreeBase.ts ×2
808
>
resultLen = this.findMatchesInNode(endPosition.node, searcher, startLineNumber, startColumn, start, end, searchData, captureMatches, limitResultCount, resultLen, result);
809
>
return result;
810
>
}
812
>
private _findMatchesInLine(searchData: SearchData, searcher: Searcher, text: string, lineNumber: number, deltaOffset: number, resultLen: number, result: FindMatch[], captureMatches: boolean, limitResultCount: number): number {
814
>
if (!captureMatches && searchData.simpleSearch) {
815
const searchString = searchData.simpleSearch;
816
const searchStringLen = searchString.length;
817
const textLength = text.length;
818
819
let lastMatchIndex = -searchStringLen;
820
while ((lastMatchIndex = text.indexOf(searchString, lastMatchIndex + searchStringLen)) !== -1) {
821
if (!wordSeparators || isValidMatch(wordSeparators, text, textLength, lastMatchIndex, searchStringLen)) {
822
result[resultLen++] = new FindMatch(new Range(lineNumber, lastMatchIndex + 1 + deltaOffset, lineNumber, lastMatchIndex + 1 + searchStringLen + deltaOffset), null);
823
if (resultLen >= limitResultCount) {
824
return resultLen;
825
}
826
}
827
}
828
return resultLen;
829
}
831
>
let m: RegExpExecArray | null;
832
>
// Reset regex to search from the beginning
833
>
searcher.reset(0);
834
>
do {
835
>
m = searcher.next(text);
836
>
if (m) {
837
>
result[resultLen++] = createFindMatch(new Range(lineNumber, m.index + 1 + deltaOffset, lineNumber, m.index + 1 + m[0].length + deltaOffset), m, captureMatches);
838
>
if (resultLen >= limitResultCount) {
839
return resultLen;
840
}
842
>
} while (m);
843
>
return resultLen;
844
>
}
846
>
// #endregion
847
>
848
>
// #region Piece Table
849
>
public insert(offset: number, value: string, eolNormalized: boolean = false): void {
851
>
this._lastVisitedLine.lineNumber = 0;
852
>
this._lastVisitedLine.value = '';
853
>
854
>
if (this.root !== SENTINEL) {
856
>
const piece = node.piece;
857
>
const bufferIndex = piece.bufferIndex;
858
>
const insertPosInBuffer = this.positionInBuffer(node, remainder);
859
>
if (node.piece.bufferIndex === 0 &&
866
>
this.appendToNode(node, value);
867
>
this.computeBufferMetadata();
868
>
return;
869
>
}
871
>
if (nodeStartOffset === offset) {
873
>
this._searchCache.validate(offset);
876
>
const nodesToDel: TreeNode[] = [];
877
>
let newRightPiece = new Piece(
878
>
piece.bufferIndex,
879
>
insertPosInBuffer,
880
>
piece.end,
881
>
this.getLineFeedCnt(piece.bufferIndex, insertPosInBuffer, piece.end),
882
>
this.offsetInBuffer(bufferIndex, piece.end) - this.offsetInBuffer(bufferIndex, insertPosInBuffer)
883
>
);
884
>
885
>
if (this.shouldCheckCRLF() && this.endWithCR(value)) {
887
>
888
>
if (headOfRight === 10 /** \n */) {
889
>
const newStart: BufferCursor = { line: newRightPiece.start.line + 1, column: 0 };
pieceTreeBase.ts ×1
890
>
newRightPiece = new Piece(
891
>
newRightPiece.bufferIndex,
892
>
newStart,
893
>
newRightPiece.end,
894
>
this.getLineFeedCnt(newRightPiece.bufferIndex, newStart, newRightPiece.end),
895
>
newRightPiece.length - 1
896
>
);
897
>
898
>
value += '\n';
899
>
}
902
>
// reuse node for content before insertion point.
903
>
if (this.shouldCheckCRLF() && this.startWithLF(value)) {
905
>
if (tailOfLeft === 13 /** \r */) {
907
>
this.deleteNodeTail(node, previousPos);
908
>
value = '\r' + value;
909
>
910
>
if (node.piece.length === 0) {
912
>
}
915
>
}
918
>
}
920
>
const newPieces = this.createNewPieces(value);
921
>
if (newRightPiece.length > 0) {
922
>
this.rbInsertRight(node, newRightPiece);
923
>
}
924
>
925
>
let tmpNode = node;
926
>
for (let k = 0; k < newPieces.length; k++) {
927
>
tmpNode = this.rbInsertRight(tmpNode, newPieces[k]);
928
>
}
929
>
this.deleteNodes(nodesToDel);
932
>
}
935
>
const pieces = this.createNewPieces(value);
936
>
let node = this.rbInsertLeft(null, pieces[0]);
937
>
938
>
for (let k = 1; k < pieces.length; k++) {
939
node = this.rbInsertRight(node, pieces[k]);
940
}
943
>
// todo, this is too brutal. Total line feed count should be updated the same way as lf_left.
944
>
this.computeBufferMetadata();
945
>
}
947
>
public delete(offset: number, cnt: number): void {
949
>
this._lastVisitedLine.value = '';
950
>
951
>
if (cnt <= 0 || this.root === SENTINEL) {
953
>
}
955
>
const startPosition = this.nodeAt(offset);
956
>
const endPosition = this.nodeAt(offset + cnt);
957
>
const startNode = startPosition.node;
958
>
const endNode = endPosition.node;
959
>
960
>
if (startNode === endNode) {
961
>
const startSplitPosInBuffer = this.positionInBuffer(startNode, startPosition.remainder);
pieceTreeBase.ts ×1
962
>
const endSplitPosInBuffer = this.positionInBuffer(startNode, endPosition.remainder);
963
>
964
>
if (startPosition.nodeStartOffset === offset) {
967
>
rbDelete(this, startNode);
968
>
this.validateCRLFWithPrevNode(next);
969
>
this.computeBufferMetadata();
970
>
return;
971
>
}
973
>
this._searchCache.validate(offset);
974
>
this.validateCRLFWithPrevNode(startNode);
975
>
this.computeBufferMetadata();
976
>
return;
977
>
}
979
>
if (startPosition.nodeStartOffset + startNode.piece.length === offset + cnt) {
981
>
this.validateCRLFWithNextNode(startNode);
982
>
this.computeBufferMetadata();
983
>
return;
984
>
}
986
>
// delete content in the middle, this node will be splitted to nodes
987
>
this.shrinkNode(startNode, startSplitPosInBuffer, endSplitPosInBuffer);
988
>
this.computeBufferMetadata();
989
>
return;
990
>
}
992
>
const nodesToDel: TreeNode[] = [];
993
>
994
>
const startSplitPosInBuffer = this.positionInBuffer(startNode, startPosition.remainder);
995
>
this.deleteNodeTail(startNode, startSplitPosInBuffer);
996
>
this._searchCache.validate(offset);
997
>
if (startNode.piece.length === 0) {
999
>
}
1001
>
// update last touched node
1002
>
const endSplitPosInBuffer = this.positionInBuffer(endNode, endPosition.remainder);
1003
>
this.deleteNodeHead(endNode, endSplitPosInBuffer);
1004
>
if (endNode.piece.length === 0) {
1006
>
}
1008
>
// delete nodes in between
1009
>
const secondNode = startNode.next();
1010
>
for (let node = secondNode; node !== SENTINEL && node !== endNode; node = node.next()) {
pieceTreeBase.ts ×3
1012
>
}
1014
>
const prev = startNode.piece.length === 0 ? startNode.prev() : startNode;
pieceTreeBase.ts ×3
1015
>
this.deleteNodes(nodesToDel);
1016
>
this.validateCRLFWithNextNode(prev);
1017
>
this.computeBufferMetadata();
1018
>
}
1020
>
private insertContentToNodeLeft(value: string, node: TreeNode) {
1022
>
const nodesToDel: TreeNode[] = [];
1023
>
if (this.shouldCheckCRLF() && this.endWithCR(value) && this.startWithLF(node)) {
1025
>
1026
>
const piece = node.piece;
1027
>
const newStart: BufferCursor = { line: piece.start.line + 1, column: 0 };
1028
>
const nPiece = new Piece(
1029
>
piece.bufferIndex,
1030
>
newStart,
1031
>
piece.end,
1032
>
this.getLineFeedCnt(piece.bufferIndex, newStart, piece.end),
1033
>
piece.length - 1
1034
>
);
1035
>
1036
>
node.piece = nPiece;
1037
>
1038
>
value += '\n';
1039
>
updateTreeMetadata(this, node, -1, -1);
1040
>
1041
>
if (node.piece.length === 0) {
1042
nodesToDel.push(node);
1043
}
1046
>
const newPieces = this.createNewPieces(value);
1047
>
let newNode = this.rbInsertLeft(node, newPieces[newPieces.length - 1]);
1048
>
for (let k = newPieces.length - 2; k >= 0; k--) {
1049
newNode = this.rbInsertLeft(newNode, newPieces[k]);
1050
}
1052
>
this.deleteNodes(nodesToDel);
1053
>
}
1055
>
private insertContentToNodeRight(value: string, node: TreeNode) {
1057
>
if (this.adjustCarriageReturnFromNext(value, node)) {
1058
// move \n to the new node.
1059
value += '\n';
1060
}
1062
>
const newPieces = this.createNewPieces(value);
1063
>
const newNode = this.rbInsertRight(node, newPieces[0]);
1064
>
let tmpNode = newNode;
1065
>
1066
>
for (let k = 1; k < newPieces.length; k++) {
1067
tmpNode = this.rbInsertRight(tmpNode, newPieces[k]);
1068
}
1070
>
this.validateCRLFWithPrevNode(newNode);
1071
>
}
1073
>
private positionInBuffer(node: TreeNode, remainder: number): BufferCursor;
1074
>
private positionInBuffer(node: TreeNode, remainder: number, ret: BufferCursor): null;
1075
>
private positionInBuffer(node: TreeNode, remainder: number, ret?: BufferCursor): BufferCursor | null {
1077
>
const bufferIndex = node.piece.bufferIndex;
1078
>
const lineStarts = this._buffers[bufferIndex].lineStarts;
1079
>
1080
>
const startOffset = lineStarts[piece.start.line] + piece.start.column;
1081
>
1082
>
const offset = startOffset + remainder;
1083
>
1084
>
// binary search offset between startOffset and endOffset
1085
>
let low = piece.start.line;
1086
>
let high = piece.end.line;
1087
>
1088
>
let mid: number = 0;
1089
>
let midStop: number = 0;
1090
>
let midStart: number = 0;
1091
>
1092
>
while (low <= high) {
1093
>
mid = low + ((high - low) / 2) | 0;
1094
>
midStart = lineStarts[mid];
1095
>
1096
>
if (mid === high) {
1098
>
}
1100
>
midStop = lineStarts[mid + 1];
1101
>
1102
>
if (offset < midStart) {
1108
>
}
1110
>
1111
>
if (ret) {
1113
>
ret.column = offset - midStart;
1114
>
return null;
1115
>
}
1117
>
return {
1118
>
line: mid,
1119
>
column: offset - midStart
1120
>
};
1121
>
}
1123
>
private getLineFeedCnt(bufferIndex: number, start: BufferCursor, end: BufferCursor): number {
1124
>
// we don't need to worry about start: abc\r|\n, or abc|\r, or abc|\n, or abc|\r\n doesn't change the fact that, there is one line break after start.
pieceTreeBase.ts ×2
1125
>
// now let's take care of end: abc\r|\n, if end is in between \r and \n, we need to add line feed count by 1
1126
>
if (end.column === 0) {
1128
>
}
1130
>
const lineStarts = this._buffers[bufferIndex].lineStarts;
1131
>
if (end.line === lineStarts.length - 1) { // it means, there is no \n after end, otherwise, there will be one more lineStart.
1133
>
}
1135
>
const nextLineStartOffset = lineStarts[end.line + 1];
1136
>
const endOffset = lineStarts[end.line] + end.column;
1137
>
if (nextLineStartOffset > endOffset + 1) { // there are more than 1 character after end, which means it can't be \n
1139
>
}
1141
>
// character at endOffset is \n, so we check the character before first
1142
>
// if character at endOffset is \r, end.column is 0 and we can't get here.
1143
>
const previousCharOffset = endOffset - 1; // end.column > 0 so it's okay.
1144
>
const buffer = this._buffers[bufferIndex].buffer;
1145
>
1146
>
if (buffer.charCodeAt(previousCharOffset) === 13) {
1150
>
}
1153
>
private offsetInBuffer(bufferIndex: number, cursor: BufferCursor): number {
1155
>
return lineStarts[cursor.line] + cursor.column;
1156
>
}
1158
>
private deleteNodes(nodes: TreeNode[]): void {
1161
>
}
1164
>
private createNewPieces(text: string): Piece[] {
1166
// the content is large, operations like substring, charCode becomes slow
1167
// so here we split it into smaller chunks, just like what we did for CR/LF normalization
1168
const newPieces: Piece[] = [];
1169
while (text.length > AverageBufferSize) {
1170
const lastChar = text.charCodeAt(AverageBufferSize - 1);
1171
let splitText;
1172
if (lastChar === CharCode.CarriageReturn || (lastChar >= 0xD800 && lastChar <= 0xDBFF)) {
1173
// last character is \r or a high surrogate => keep it back
1174
splitText = text.substring(0, AverageBufferSize - 1);
1175
text = text.substring(AverageBufferSize - 1);
1176
} else {
1177
splitText = text.substring(0, AverageBufferSize);
1178
text = text.substring(AverageBufferSize);
1179
}
1180
1181
const lineStarts = createLineStartsFast(splitText);
1182
newPieces.push(new Piece(
1183
this._buffers.length, /* buffer index */
1184
{ line: 0, column: 0 },
1185
{ line: lineStarts.length - 1, column: splitText.length - lineStarts[lineStarts.length - 1] },
1186
lineStarts.length - 1,
1187
splitText.length
1188
));
1189
this._buffers.push(new StringBuffer(splitText, lineStarts));
1190
}
1191
1192
const lineStarts = createLineStartsFast(text);
1193
newPieces.push(new Piece(
1194
this._buffers.length, /* buffer index */
1195
{ line: 0, column: 0 },
1196
{ line: lineStarts.length - 1, column: text.length - lineStarts[lineStarts.length - 1] },
1197
lineStarts.length - 1,
1198
text.length
1199
));
1200
this._buffers.push(new StringBuffer(text, lineStarts));
1201
1202
return newPieces;
1203
}
1205
>
let startOffset = this._buffers[0].buffer.length;
1206
>
const lineStarts = createLineStartsFast(text, false);
1207
>
1208
>
let start = this._lastChangeBufferPos;
1209
>
if (this._buffers[0].lineStarts[this._buffers[0].lineStarts.length - 1] === startOffset
1210
>
&& startOffset !== 0
1212
>
&& this.endWithCR(this._buffers[0].buffer) // todo, we can check this._lastChangeBufferPos's column as it's the last one
pieceTreeBase.ts ×1
1214
>
this._lastChangeBufferPos = { line: this._lastChangeBufferPos.line, column: this._lastChangeBufferPos.column + 1 };
pieceTreeBase.ts ×1
1215
>
start = this._lastChangeBufferPos;
1216
>
1217
>
for (let i = 0; i < lineStarts.length; i++) {
1218
>
lineStarts[i] += startOffset + 1;
1219
>
}
1220
>
1221
>
this._buffers[0].lineStarts = (<number[]>this._buffers[0].lineStarts).concat(<number[]>lineStarts.slice(1));
1222
>
this._buffers[0].buffer += '_' + text;
1223
>
startOffset += 1;
1225
>
if (startOffset !== 0) {
1227
>
lineStarts[i] += startOffset;
1228
>
}
1229
>
}
1230
>
this._buffers[0].lineStarts = (<number[]>this._buffers[0].lineStarts).concat(<number[]>lineStarts.slice(1));
pieceTreeBase.ts ×9
1231
>
this._buffers[0].buffer += text;
1232
>
}
1233
>
1234
>
const endOffset = this._buffers[0].buffer.length;
1235
>
const endIndex = this._buffers[0].lineStarts.length - 1;
1236
>
const endColumn = endOffset - this._buffers[0].lineStarts[endIndex];
1237
>
const endPos = { line: endIndex, column: endColumn };
1238
>
const newPiece = new Piece(
1239
>
0, /** todo@peng */
1240
>
start,
1241
>
endPos,
1242
>
this.getLineFeedCnt(0, start, endPos),
1243
>
endOffset - startOffset
1244
>
);
1245
>
this._lastChangeBufferPos = endPos;
1246
>
return [newPiece];
1247
>
}
1249
>
public getLinesRawContent(): string {
1251
>
}
1253
>
public getLineRawContent(lineNumber: number, endOffset: number = 0): string {
1255
>
1256
>
let ret = '';
1257
>
const cache = this._searchCache.get2(lineNumber);
1258
>
if (cache) {
1260
>
const prevAccumulatedValue = this.getAccumulatedValue(x, lineNumber - cache.nodeStartLineNumber - 1);
1261
>
const buffer = this._buffers[x.piece.bufferIndex].buffer;
1262
>
const startOffset = this.offsetInBuffer(x.piece.bufferIndex, x.piece.start);
1263
>
if (cache.nodeStartLineNumber + x.piece.lineFeedCnt === lineNumber) {
1264
>
ret = buffer.substring(startOffset + prevAccumulatedValue, startOffset + x.piece.length);
pieceTreeBase.ts ×1
1266
>
const accumulatedValue = this.getAccumulatedValue(x, lineNumber - cache.nodeStartLineNumber);
pieceTreeBase.ts ×1
1267
>
return buffer.substring(startOffset + prevAccumulatedValue, startOffset + accumulatedValue - endOffset);
1268
>
}
1270
>
let nodeStartOffset = 0;
1271
>
const originalLineNumber = lineNumber;
1272
>
while (x !== SENTINEL) {
1276
>
const prevAccumulatedValue = this.getAccumulatedValue(x, lineNumber - x.lf_left - 2);
pieceTreeBase.ts ×1
1277
>
const accumulatedValue = this.getAccumulatedValue(x, lineNumber - x.lf_left - 1);
1278
>
const buffer = this._buffers[x.piece.bufferIndex].buffer;
1279
>
const startOffset = this.offsetInBuffer(x.piece.bufferIndex, x.piece.start);
1280
>
nodeStartOffset += x.size_left;
1281
>
this._searchCache.set({
1282
>
node: x,
1283
>
nodeStartOffset,
1284
>
nodeStartLineNumber: originalLineNumber - (lineNumber - 1 - x.lf_left)
1285
>
});
1286
>
1287
>
return buffer.substring(startOffset + prevAccumulatedValue, startOffset + accumulatedValue - endOffset);
1289
>
const prevAccumulatedValue = this.getAccumulatedValue(x, lineNumber - x.lf_left - 2);
pieceTreeBase.ts ×1
1290
>
const buffer = this._buffers[x.piece.bufferIndex].buffer;
1291
>
const startOffset = this.offsetInBuffer(x.piece.bufferIndex, x.piece.start);
1292
>
1293
>
ret = buffer.substring(startOffset + prevAccumulatedValue, startOffset + x.piece.length);
1294
>
break;
1297
>
nodeStartOffset += x.size_left + x.piece.length;
1298
>
x = x.right;
1299
>
}
1303
>
// search in order, to find the node contains end column
1304
>
x = x.next();
1305
>
while (x !== SENTINEL) {
1307
>
1308
>
if (x.piece.lineFeedCnt > 0) {
1310
>
const startOffset = this.offsetInBuffer(x.piece.bufferIndex, x.piece.start);
1311
>
1312
>
ret += buffer.substring(startOffset, startOffset + accumulatedValue - endOffset);
1313
>
return ret;
1315
>
const startOffset = this.offsetInBuffer(x.piece.bufferIndex, x.piece.start);
pieceTreeBase.ts ×1
1316
>
ret += buffer.substr(startOffset, x.piece.length);
1317
>
}
1318
>
1319
>
x = x.next();
1320
>
}
1322
>
return ret;
1325
>
private computeBufferMetadata() {
1327
>
1328
>
let lfCnt = 1;
1329
>
let len = 0;
1330
>
1331
>
while (x !== SENTINEL) {
1333
>
len += x.size_left + x.piece.length;
1334
>
x = x.right;
1335
>
}
1337
>
this._lineCnt = lfCnt;
1338
>
this._length = len;
1339
>
this._searchCache.validate(this._length);
1340
>
}
1342
>
// #region node operations
1343
>
private getIndexOf(node: TreeNode, accumulatedValue: number): { index: number; remainder: number } {
1345
>
const pos = this.positionInBuffer(node, accumulatedValue);
1346
>
const lineCnt = pos.line - piece.start.line;
1347
>
1348
>
if (this.offsetInBuffer(piece.bufferIndex, piece.end) - this.offsetInBuffer(piece.bufferIndex, piece.start) === accumulatedValue) {
1350
>
const realLineCnt = this.getLineFeedCnt(node.piece.bufferIndex, piece.start, pos);
1351
>
if (realLineCnt !== lineCnt) {
1353
>
return { index: realLineCnt, remainder: 0 };
1354
>
}
1357
>
return { index: lineCnt, remainder: pos.column };
1358
>
}
1360
>
private getAccumulatedValue(node: TreeNode, index: number) {
1363
>
}
1365
>
const lineStarts = this._buffers[piece.bufferIndex].lineStarts;
1366
>
const expectedLineStartIndex = piece.start.line + index + 1;
1367
>
if (expectedLineStartIndex > piece.end.line) {
1368
>
return lineStarts[piece.end.line] + piece.end.column - lineStarts[piece.start.line] - piece.start.column;
pieceTreeBase.ts ×1
1370
>
return lineStarts[expectedLineStartIndex] - lineStarts[piece.start.line] - piece.start.column;
1371
>
}
1374
>
private deleteNodeTail(node: TreeNode, pos: BufferCursor) {
1376
>
const originalLFCnt = piece.lineFeedCnt;
1377
>
const originalEndOffset = this.offsetInBuffer(piece.bufferIndex, piece.end);
1378
>
1379
>
const newEnd = pos;
1380
>
const newEndOffset = this.offsetInBuffer(piece.bufferIndex, newEnd);
1381
>
const newLineFeedCnt = this.getLineFeedCnt(piece.bufferIndex, piece.start, newEnd);
1382
>
1383
>
const lf_delta = newLineFeedCnt - originalLFCnt;
1384
>
const size_delta = newEndOffset - originalEndOffset;
1385
>
const newLength = piece.length + size_delta;
1386
>
1387
>
node.piece = new Piece(
1388
>
piece.bufferIndex,
1389
>
piece.start,
1390
>
newEnd,
1391
>
newLineFeedCnt,
1392
>
newLength
1393
>
);
1394
>
1395
>
updateTreeMetadata(this, node, size_delta, lf_delta);
1396
>
}
1398
>
private deleteNodeHead(node: TreeNode, pos: BufferCursor) {
1400
>
const originalLFCnt = piece.lineFeedCnt;
1401
>
const originalStartOffset = this.offsetInBuffer(piece.bufferIndex, piece.start);
1402
>
1403
>
const newStart = pos;
1404
>
const newLineFeedCnt = this.getLineFeedCnt(piece.bufferIndex, newStart, piece.end);
1405
>
const newStartOffset = this.offsetInBuffer(piece.bufferIndex, newStart);
1406
>
const lf_delta = newLineFeedCnt - originalLFCnt;
1407
>
const size_delta = originalStartOffset - newStartOffset;
1408
>
const newLength = piece.length + size_delta;
1409
>
node.piece = new Piece(
1410
>
piece.bufferIndex,
1411
>
newStart,
1412
>
piece.end,
1413
>
newLineFeedCnt,
1414
>
newLength
1415
>
);
1416
>
1417
>
updateTreeMetadata(this, node, size_delta, lf_delta);
1418
>
}
1420
>
private shrinkNode(node: TreeNode, start: BufferCursor, end: BufferCursor) {
1422
>
const originalStartPos = piece.start;
1423
>
const originalEndPos = piece.end;
1424
>
1425
>
// old piece, originalStartPos, start
1426
>
const oldLength = piece.length;
1427
>
const oldLFCnt = piece.lineFeedCnt;
1428
>
const newEnd = start;
1429
>
const newLineFeedCnt = this.getLineFeedCnt(piece.bufferIndex, piece.start, newEnd);
1430
>
const newLength = this.offsetInBuffer(piece.bufferIndex, start) - this.offsetInBuffer(piece.bufferIndex, originalStartPos);
1431
>
1432
>
node.piece = new Piece(
1433
>
piece.bufferIndex,
1434
>
piece.start,
1435
>
newEnd,
1436
>
newLineFeedCnt,
1437
>
newLength
1438
>
);
1439
>
1440
>
updateTreeMetadata(this, node, newLength - oldLength, newLineFeedCnt - oldLFCnt);
1441
>
1442
>
// new right piece, end, originalEndPos
1443
>
const newPiece = new Piece(
1444
>
piece.bufferIndex,
1445
>
end,
1446
>
originalEndPos,
1447
>
this.getLineFeedCnt(piece.bufferIndex, end, originalEndPos),
1448
>
this.offsetInBuffer(piece.bufferIndex, originalEndPos) - this.offsetInBuffer(piece.bufferIndex, end)
1449
>
);
1450
>
1451
>
const newNode = this.rbInsertRight(node, newPiece);
1452
>
this.validateCRLFWithPrevNode(newNode);
1453
>
}
1455
>
private appendToNode(node: TreeNode, value: string): void {
1458
>
}
1460
>
const hitCRLF = this.shouldCheckCRLF() && this.startWithLF(value) && this.endWithCR(node);
1461
>
const startOffset = this._buffers[0].buffer.length;
1462
>
this._buffers[0].buffer += value;
1463
>
const lineStarts = createLineStartsFast(value, false);
1464
>
for (let i = 0; i < lineStarts.length; i++) {
1465
>
lineStarts[i] += startOffset;
1466
>
}
1467
>
if (hitCRLF) {
1468
>
const prevStartOffset = this._buffers[0].lineStarts[this._buffers[0].lineStarts.length - 2];
pieceTreeBase.ts ×1
1469
>
(<number[]>this._buffers[0].lineStarts).pop();
1470
>
// _lastChangeBufferPos is already wrong
1471
>
this._lastChangeBufferPos = { line: this._lastChangeBufferPos.line - 1, column: startOffset - prevStartOffset };
1472
>
}
1474
>
this._buffers[0].lineStarts = (<number[]>this._buffers[0].lineStarts).concat(<number[]>lineStarts.slice(1));
1475
>
const endIndex = this._buffers[0].lineStarts.length - 1;
1476
>
const endColumn = this._buffers[0].buffer.length - this._buffers[0].lineStarts[endIndex];
1477
>
const newEnd = { line: endIndex, column: endColumn };
1478
>
const newLength = node.piece.length + value.length;
1479
>
const oldLineFeedCnt = node.piece.lineFeedCnt;
1480
>
const newLineFeedCnt = this.getLineFeedCnt(0, node.piece.start, newEnd);
1481
>
const lf_delta = newLineFeedCnt - oldLineFeedCnt;
1482
>
1483
>
node.piece = new Piece(
1484
>
node.piece.bufferIndex,
1485
>
node.piece.start,
1486
>
newEnd,
1487
>
newLineFeedCnt,
1488
>
newLength
1489
>
);
1490
>
1491
>
this._lastChangeBufferPos = newEnd;
1492
>
updateTreeMetadata(this, node, value.length, lf_delta);
1493
>
}
1495
>
private nodeAt(offset: number): NodePosition {
1497
>
const cache = this._searchCache.get(offset);
1498
>
if (cache) {
1500
>
node: cache.node,
1501
>
nodeStartOffset: cache.nodeStartOffset,
1502
>
remainder: offset - cache.nodeStartOffset
1503
>
};
1504
>
}
1506
>
let nodeStartOffset = 0;
1507
>
1508
>
while (x !== SENTINEL) {
1509
>
if (x.size_left > offset) {
1512
>
nodeStartOffset += x.size_left;
1513
>
const ret = {
1514
>
node: x,
1515
>
remainder: offset - x.size_left,
1516
>
nodeStartOffset
1517
>
};
1518
>
this._searchCache.set(ret);
1519
>
return ret;
1520
>
} else {
1522
>
nodeStartOffset += x.size_left + x.piece.length;
1523
>
x = x.right;
1524
>
}
1526
1527
return null!;
1530
>
private nodeAt2(lineNumber: number, column: number): NodePosition {
1532
>
let nodeStartOffset = 0;
1533
>
1534
>
while (x !== SENTINEL) {
1538
>
const prevAccumualtedValue = this.getAccumulatedValue(x, lineNumber - x.lf_left - 2);
pieceTreeBase.ts ×1
1539
>
const accumulatedValue = this.getAccumulatedValue(x, lineNumber - x.lf_left - 1);
1540
>
nodeStartOffset += x.size_left;
1541
>
1542
>
return {
1543
>
node: x,
1544
>
remainder: Math.min(prevAccumualtedValue + column - 1, accumulatedValue),
1545
>
nodeStartOffset
1546
>
};
1548
>
const prevAccumualtedValue = this.getAccumulatedValue(x, lineNumber - x.lf_left - 2);
pieceTreeBase.ts ×2
1549
>
if (prevAccumualtedValue + column - 1 <= x.piece.length) {
1551
>
node: x,
1552
>
remainder: prevAccumualtedValue + column - 1,
1553
>
nodeStartOffset
1554
>
};
1557
>
break;
1558
>
}
1561
>
nodeStartOffset += x.size_left + x.piece.length;
1562
>
x = x.right;
1563
>
}
1566
>
// search in order, to find the node contains position.column
1567
>
x = x.next();
1568
>
while (x !== SENTINEL) {
1570
>
if (x.piece.lineFeedCnt > 0) {
1572
>
const nodeStartOffset = this.offsetOfNode(x);
1573
>
return {
1574
>
node: x,
1575
>
remainder: Math.min(column - 1, accumulatedValue),
1576
>
nodeStartOffset
1577
>
};
1581
>
return {
1582
>
node: x,
1583
>
remainder: column - 1,
1584
>
nodeStartOffset
1585
>
};
1588
>
}
1591
>
x = x.next();
1592
>
}
1594
>
return null!;
1597
>
private nodeCharCodeAt(node: TreeNode, offset: number): number {
1600
>
}
1602
>
const newOffset = this.offsetInBuffer(node.piece.bufferIndex, node.piece.start) + offset;
1603
>
return buffer.buffer.charCodeAt(newOffset);
1604
>
}
1606
>
private offsetOfNode(node: TreeNode): number {
1608
return 0;
1609
}
1611
>
while (node !== this.root) {
1614
>
}
1616
>
node = node.parent;
1617
>
}
1619
>
return pos;
1620
>
}
1622
>
// #endregion
1623
>
1624
>
// #region CRLF
1625
>
private shouldCheckCRLF() {
1627
>
}
1629
>
private startWithLF(val: string | TreeNode): boolean {
1632
>
}
1636
>
}
1638
>
const piece = val.piece;
1639
>
const lineStarts = this._buffers[piece.bufferIndex].lineStarts;
1640
>
const line = piece.start.line;
1641
>
const startOffset = lineStarts[line] + piece.start.column;
1642
>
if (line === lineStarts.length - 1) {
1643
// last line, so there is no line feed at the end of this line
1644
return false;
1645
}
1647
>
if (nextLineOffset > startOffset + 1) {
1649
>
}
1650
>
return this._buffers[piece.bufferIndex].buffer.charCodeAt(startOffset) === 10;
pieceTreeBase.ts ×1
1653
>
private endWithCR(val: string | TreeNode): boolean {
1656
>
}
1660
>
}
1662
>
return this.nodeCharCodeAt(val, val.piece.length - 1) === 13;
1665
>
private validateCRLFWithPrevNode(nextNode: TreeNode) {
1668
>
if (this.endWithCR(node)) {
1670
>
}
1674
>
private validateCRLFWithNextNode(node: TreeNode) {
1677
>
if (this.startWithLF(nextNode)) {
1679
>
}
1683
>
private fixCRLF(prev: TreeNode, next: TreeNode) {
1685
>
// update node
1686
>
const lineStarts = this._buffers[prev.piece.bufferIndex].lineStarts;
1687
>
let newEnd: BufferCursor;
1688
>
if (prev.piece.end.column === 0) {
1690
>
newEnd = { line: prev.piece.end.line - 1, column: lineStarts[prev.piece.end.line] - lineStarts[prev.piece.end.line - 1] - 1 };
1693
>
newEnd = { line: prev.piece.end.line, column: prev.piece.end.column - 1 };
1694
>
}
1696
>
const prevNewLength = prev.piece.length - 1;
1697
>
const prevNewLFCnt = prev.piece.lineFeedCnt - 1;
1698
>
prev.piece = new Piece(
1699
>
prev.piece.bufferIndex,
1700
>
prev.piece.start,
1701
>
newEnd,
1702
>
prevNewLFCnt,
1703
>
prevNewLength
1704
>
);
1705
>
1706
>
updateTreeMetadata(this, prev, -1, -1);
1707
>
if (prev.piece.length === 0) {
1709
>
}
1711
>
// update nextNode
1712
>
const newStart: BufferCursor = { line: next.piece.start.line + 1, column: 0 };
1713
>
const newLength = next.piece.length - 1;
1714
>
const newLineFeedCnt = this.getLineFeedCnt(next.piece.bufferIndex, newStart, next.piece.end);
1715
>
next.piece = new Piece(
1716
>
next.piece.bufferIndex,
1717
>
newStart,
1718
>
next.piece.end,
1719
>
newLineFeedCnt,
1720
>
newLength
1721
>
);
1722
>
1723
>
updateTreeMetadata(this, next, -1, -1);
1724
>
if (next.piece.length === 0) {
1726
>
}
1728
>
// create new piece which contains \r\n
1729
>
const pieces = this.createNewPieces('\r\n');
1730
>
this.rbInsertRight(prev, pieces[0]);
1731
>
// delete empty nodes
1732
>
1733
>
for (let i = 0; i < nodesToDel.length; i++) {
1735
>
}
1738
>
private adjustCarriageReturnFromNext(value: string, node: TreeNode): boolean {
1741
>
if (this.startWithLF(nextNode)) {
1743
>
value += '\n';
1744
>
1745
>
if (nextNode.piece.length === 1) {
1749
>
const piece = nextNode.piece;
1750
>
const newStart: BufferCursor = { line: piece.start.line + 1, column: 0 };
1751
>
const newLength = piece.length - 1;
1752
>
const newLineFeedCnt = this.getLineFeedCnt(piece.bufferIndex, newStart, piece.end);
1753
>
nextNode.piece = new Piece(
1754
>
piece.bufferIndex,
1755
>
newStart,
1756
>
piece.end,
1757
>
newLineFeedCnt,
1758
>
newLength
1759
>
);
1760
>
1761
>
updateTreeMetadata(this, nextNode, -1, -1);
1762
>
}
1764
>
}
1767
>
return false;
1770
>
// #endregion
1771
>
1772
>
// #endregion
1773
>
1774
>
// #region Tree operations
1775
>
iterate(node: TreeNode, callback: (node: TreeNode) => boolean): boolean {
1777
>
return callback(SENTINEL);
1778
>
}
1780
>
const leftRet = this.iterate(node.left, callback);
1781
>
if (!leftRet) {
1782
return leftRet;
1783
}
1785
>
return callback(node) && this.iterate(node.right, callback);
1788
>
private getNodeContent(node: TreeNode) {
1791
>
}
1793
>
const piece = node.piece;
1794
>
const startOffset = this.offsetInBuffer(piece.bufferIndex, piece.start);
1795
>
const endOffset = this.offsetInBuffer(piece.bufferIndex, piece.end);
1796
>
const currentContent = buffer.buffer.substring(startOffset, endOffset);
1797
>
return currentContent;
1798
>
}
1800
>
getPieceContent(piece: Piece) {
1802
>
const startOffset = this.offsetInBuffer(piece.bufferIndex, piece.start);
1803
>
const endOffset = this.offsetInBuffer(piece.bufferIndex, piece.end);
1804
>
const currentContent = buffer.buffer.substring(startOffset, endOffset);
1805
>
return currentContent;
1806
>
}
1808
>
/**
1809
>
* node node
1810
>
* / \ / \
1811
>
* a b <---- a b
1812
>
* /
1813
>
* z
1814
>
*/
1815
>
private rbInsertRight(node: TreeNode | null, p: Piece): TreeNode {
1817
>
z.left = SENTINEL;
1818
>
z.right = SENTINEL;
1819
>
z.parent = SENTINEL;
1820
>
z.size_left = 0;
1821
>
z.lf_left = 0;
1822
>
1823
>
const x = this.root;
1824
>
if (x === SENTINEL) {
1826
>
z.color = NodeColor.Black;
1829
>
z.parent = node!;
1830
>
} else {
1832
>
nextNode.left = z;
1833
>
z.parent = nextNode;
1834
>
}
1836
>
fixInsert(this, z);
1837
>
return z;
1838
>
}
1840
>
/**
1841
>
* node node
1842
>
* / \ / \
1843
>
* a b ----> a b
1844
>
* \
1845
>
* z
1846
>
*/
1847
>
private rbInsertLeft(node: TreeNode | null, p: Piece): TreeNode {
1849
>
z.left = SENTINEL;
1850
>
z.right = SENTINEL;
1851
>
z.parent = SENTINEL;
1852
>
z.size_left = 0;
1853
>
z.lf_left = 0;
1854
>
1855
>
if (this.root === SENTINEL) {
1857
>
z.color = NodeColor.Black;
1860
>
z.parent = node!;
1863
>
prevNode.right = z;
1864
>
z.parent = prevNode;
1865
>
}
1867
>
fixInsert(this, z);
1868
>
return z;
1869
>
}
1871
>
private getContentOfSubTree(node: TreeNode): string {
1873
>
1874
>
this.iterate(node, node => {
1875
>
str += this.getNodeContent(node);
1876
>
return true;
1877
>
});
1878
>
1879
>
return str;
1880
>
}
1882
>
}