src/vs/editor/common/tokens/sparseMultilineTokens.ts
617 LOC · 549 covered · 68 uncovered · 135 ranges · 61 concepts · 33 introducers · 20 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.
/*---------------------------------------------------------------------------------------------
sparseMultilineTokens.ts ×33
* Copyright (c) Microsoft Corporation. All rights reserved.
* Licensed under the MIT License. See License.txt in the project root for license information.
*--------------------------------------------------------------------------------------------*/
import { CharCode } from '../../../base/common/charCode.js';
import { Position } from '../core/position.js';
import { IRange, Range } from '../core/range.js';
import { countEOL } from '../core/misc/eolCounter.js';
import { ITextModel } from '../model.js';
import { RateLimiter } from './common.js';
/**
* Represents sparse tokens over a contiguous range of lines.
*/
export class SparseMultilineTokens {
public static create(startLineNumber: number, tokens: Uint32Array): SparseMultilineTokens {
return new SparseMultilineTokens(startLineNumber, new SparseMultilineTokensStorage(tokens));
}
private _startLineNumber: number;
private _endLineNumber: number;
private readonly _tokens: SparseMultilineTokensStorage;
/**
* (Inclusive) start line number for these tokens.
*/
public get startLineNumber(): number {
}
/**
* (Inclusive) end line number for these tokens.
*/
public get endLineNumber(): number {
}
private constructor(startLineNumber: number, tokens: SparseMultilineTokensStorage) {
this._startLineNumber = startLineNumber;
this._tokens = tokens;
this._endLineNumber = this._startLineNumber + this._tokens.getMaxDeltaLine();
}
public toString(): string {
}
private _updateEndLineNumber(): void {
this._endLineNumber = this._startLineNumber + this._tokens.getMaxDeltaLine();
sparseMultilineTokens.ts ×3
}
public isEmpty(): boolean {
}
public getLineTokens(lineNumber: number): SparseLineTokens | null {
if (this._startLineNumber <= lineNumber && lineNumber <= this._endLineNumber) {
sparseTokensStore.ts ×10
return this._tokens.getLineTokens(lineNumber - this._startLineNumber);
}
return null;
public getRange(): Range | null {
if (!deltaRange) {
return deltaRange;
}
return new Range(this._startLineNumber + deltaRange.startLineNumber, deltaRange.startColumn, this._startLineNumber + deltaRange.endLineNumber, deltaRange.endColumn);
sparseMultilineTokens.ts ×4
}
public removeTokens(range: Range): void {
const endLineIndex = range.endLineNumber - this._startLineNumber;
this._startLineNumber += this._tokens.removeTokens(startLineIndex, range.startColumn - 1, endLineIndex, range.endColumn - 1);
this._updateEndLineNumber();
}
public split(range: Range): [SparseMultilineTokens, SparseMultilineTokens] {
// a) all the tokens before `range`
// b) all the tokens after `range`
const startLineIndex = range.startLineNumber - this._startLineNumber;
const endLineIndex = range.endLineNumber - this._startLineNumber;
const [a, b, bDeltaLine] = this._tokens.split(startLineIndex, range.startColumn - 1, endLineIndex, range.endColumn - 1);
return [new SparseMultilineTokens(this._startLineNumber, a), new SparseMultilineTokens(this._startLineNumber + bDeltaLine, b)];
}
public applyEdit(range: IRange, text: string): void {
const [eolCount, firstLineLength, lastLineLength] = countEOL(text);
this.acceptEdit(range, eolCount, firstLineLength, lastLineLength, text.length > 0 ? text.charCodeAt(0) : CharCode.Null);
}
public acceptEdit(range: IRange, eolCount: number, firstLineLength: number, lastLineLength: number, firstCharCode: number): void {
this._acceptInsertText(new Position(range.startLineNumber, range.startColumn), eolCount, firstLineLength, lastLineLength, firstCharCode);
this._updateEndLineNumber();
}
private _acceptDeleteRange(range: IRange): void {
if (range.startLineNumber === range.endLineNumber && range.startColumn === range.endColumn) {
sparseMultilineTokens.ts ×6
return;
}
const firstLineIndex = range.startLineNumber - this._startLineNumber;
const lastLineIndex = range.endLineNumber - this._startLineNumber;
if (lastLineIndex < 0) {
// this deletion occurs entirely before this block, so we only need to adjust line numbers
const deletedLinesCount = lastLineIndex - firstLineIndex;
this._startLineNumber -= deletedLinesCount;
return;
}
const tokenMaxDeltaLine = this._tokens.getMaxDeltaLine();
if (firstLineIndex >= tokenMaxDeltaLine + 1) {
// this deletion occurs entirely after this block, so there is nothing to do
return;
}
if (firstLineIndex < 0 && lastLineIndex >= tokenMaxDeltaLine + 1) {
sparseMultilineTokens.ts ×6
this._startLineNumber = 0;
this._tokens.clear();
return;
}
if (firstLineIndex < 0) {
this._startLineNumber -= deletedBefore;
this._tokens.acceptDeleteRange(range.startColumn - 1, 0, 0, lastLineIndex, range.endColumn - 1);
this._tokens.acceptDeleteRange(0, firstLineIndex, range.startColumn - 1, lastLineIndex, range.endColumn - 1);
sparseMultilineTokens.ts ×2
}
private _acceptInsertText(position: Position, eolCount: number, firstLineLength: number, lastLineLength: number, firstCharCode: number): void {
if (eolCount === 0 && firstLineLength === 0) {
return;
}
const lineIndex = position.lineNumber - this._startLineNumber;
if (lineIndex < 0) {
// this insertion occurs before this block, so we only need to adjust line numbers
this._startLineNumber += eolCount;
return;
}
const tokenMaxDeltaLine = this._tokens.getMaxDeltaLine();
if (lineIndex >= tokenMaxDeltaLine + 1) {
// this insertion occurs after this block, so there is nothing to do
return;
}
this._tokens.acceptInsertText(lineIndex, position.column - 1, eolCount, firstLineLength, lastLineLength, firstCharCode);
public reportIfInvalid(model: ITextModel): void {
}
class SparseMultilineTokensStorage {
/**
* The encoding of tokens is:
* 4*i deltaLine (from `startLineNumber`)
* 4*i+1 startCharacter (from the line start)
* 4*i+2 endCharacter (from the line start)
* 4*i+3 metadata
*/
private readonly _tokens: Uint32Array;
private _tokenCount: number;
constructor(tokens: Uint32Array) {
this._tokens = tokens;
this._tokenCount = tokens.length / 4;
}
public toString(startLineNumber: number): string {
for (let i = 0; i < this._tokenCount; i++) {
pieces.push(`(${this._getDeltaLine(i) + startLineNumber},${this._getStartCharacter(i)}-${this._getEndCharacter(i)})`);
}
return `[${pieces.join(',')}]`;
}
public getMaxDeltaLine(): number {
const tokenCount = this._getTokenCount();
if (tokenCount === 0) {
}
}
public getRange(): Range | null {
if (tokenCount === 0) {
return null;
}
const maxDeltaLine = this._getDeltaLine(tokenCount - 1);
const endChar = this._getEndCharacter(tokenCount - 1);
return new Range(0, startChar + 1, maxDeltaLine, endChar + 1);
}
private _getTokenCount(): number {
return this._tokenCount;
}
private _getDeltaLine(tokenIndex: number): number {
return this._tokens[4 * tokenIndex];
}
private _getStartCharacter(tokenIndex: number): number {
}
private _getEndCharacter(tokenIndex: number): number {
}
public isEmpty(): boolean {
}
public getLineTokens(deltaLine: number): SparseLineTokens | null {
let high = this._getTokenCount() - 1;
while (low < high) {
const midDeltaLine = this._getDeltaLine(mid);
if (midDeltaLine < deltaLine) {
while (min > low && this._getDeltaLine(min - 1) === deltaLine) {
}
while (max < high && this._getDeltaLine(max + 1) === deltaLine) {
}
return new SparseLineTokens(this._tokens.subarray(4 * min, 4 * max + 4));
sparseMultilineTokens.ts ×3
}
if (this._getDeltaLine(low) === deltaLine) {
return new SparseLineTokens(this._tokens.subarray(4 * low, 4 * low + 4));
sparseMultilineTokens.ts ×1
}
return null;
public clear(): void {
}
public removeTokens(startDeltaLine: number, startChar: number, endDeltaLine: number, endChar: number): number {
const tokenCount = this._tokenCount;
let newTokenCount = 0;
let hasDeletedTokens = false;
let firstDeltaLine = 0;
for (let i = 0; i < tokenCount; i++) {
const srcOffset = 4 * i;
const tokenDeltaLine = tokens[srcOffset];
const tokenStartCharacter = tokens[srcOffset + 1];
const tokenEndCharacter = tokens[srcOffset + 2];
const tokenMetadata = tokens[srcOffset + 3];
if (
(tokenDeltaLine > startDeltaLine || (tokenDeltaLine === startDeltaLine && tokenEndCharacter >= startChar))
&& (tokenDeltaLine < endDeltaLine || (tokenDeltaLine === endDeltaLine && tokenStartCharacter <= endChar))
) {
firstDeltaLine = tokenDeltaLine;
}
if (hasDeletedTokens) {
const destOffset = 4 * newTokenCount;
tokens[destOffset] = tokenDeltaLine - firstDeltaLine;
tokens[destOffset + 1] = tokenStartCharacter;
tokens[destOffset + 2] = tokenEndCharacter;
tokens[destOffset + 3] = tokenMetadata;
tokens[srcOffset] = tokenDeltaLine - firstDeltaLine;
}
}
this._tokenCount = newTokenCount;
return firstDeltaLine;
}
public split(startDeltaLine: number, startChar: number, endDeltaLine: number, endChar: number): [SparseMultilineTokensStorage, SparseMultilineTokensStorage, number] {
const tokenCount = this._tokenCount;
const aTokens: number[] = [];
const bTokens: number[] = [];
let destTokens: number[] = aTokens;
let destOffset = 0;
let destFirstDeltaLine: number = 0;
for (let i = 0; i < tokenCount; i++) {
const srcOffset = 4 * i;
const tokenDeltaLine = tokens[srcOffset];
const tokenStartCharacter = tokens[srcOffset + 1];
const tokenEndCharacter = tokens[srcOffset + 2];
const tokenMetadata = tokens[srcOffset + 3];
if ((tokenDeltaLine > startDeltaLine || (tokenDeltaLine === startDeltaLine && tokenEndCharacter >= startChar))) {
if ((tokenDeltaLine < endDeltaLine || (tokenDeltaLine === endDeltaLine && tokenStartCharacter <= endChar))) {
// this token is touching the range
continue;
// this token is after the range
if (destTokens !== bTokens) {
// this token is the first token after the range
destTokens = bTokens;
destOffset = 0;
destFirstDeltaLine = tokenDeltaLine;
}
}
}
destTokens[destOffset++] = tokenDeltaLine - destFirstDeltaLine;
destTokens[destOffset++] = tokenStartCharacter;
destTokens[destOffset++] = tokenEndCharacter;
destTokens[destOffset++] = tokenMetadata;
}
return [new SparseMultilineTokensStorage(new Uint32Array(aTokens)), new SparseMultilineTokensStorage(new Uint32Array(bTokens)), destFirstDeltaLine];
}
public acceptDeleteRange(horizontalShiftForFirstLineTokens: number, startDeltaLine: number, startCharacter: number, endDeltaLine: number, endCharacter: number): void {
// This is a bit complex, here are the cases I used to think about this:
sparseMultilineTokens.ts ×9
//
// 1. The token starts before the deletion range
// 1a. The token is completely before the deletion range
// -----------
// xxxxxxxxxxx
// 1b. The token starts before, the deletion range ends after the token
// -----------
// xxxxxxxxxxx
// 1c. The token starts before, the deletion range ends precisely with the token
// ---------------
// xxxxxxxx
// 1d. The token starts before, the deletion range is inside the token
// ---------------
// xxxxx
//
// 2. The token starts at the same position with the deletion range
// 2a. The token starts at the same position, and ends inside the deletion range
// -------
// xxxxxxxxxxx
// 2b. The token starts at the same position, and ends at the same position as the deletion range
// ----------
// xxxxxxxxxx
// 2c. The token starts at the same position, and ends after the deletion range
// -------------
// xxxxxxx
//
// 3. The token starts inside the deletion range
// 3a. The token is inside the deletion range
// -------
// xxxxxxxxxxxxx
// 3b. The token starts inside the deletion range, and ends at the same position as the deletion range
// ----------
// xxxxxxxxxxxxx
// 3c. The token starts inside the deletion range, and ends after the deletion range
// ------------
// xxxxxxxxxxx
//
// 4. The token starts after the deletion range
// -----------
// xxxxxxxx
//
const tokens = this._tokens;
const tokenCount = this._tokenCount;
const deletedLineCount = (endDeltaLine - startDeltaLine);
let newTokenCount = 0;
let hasDeletedTokens = false;
for (let i = 0; i < tokenCount; i++) {
const srcOffset = 4 * i;
let tokenDeltaLine = tokens[srcOffset];
let tokenStartCharacter = tokens[srcOffset + 1];
let tokenEndCharacter = tokens[srcOffset + 2];
const tokenMetadata = tokens[srcOffset + 3];
if (tokenDeltaLine < startDeltaLine || (tokenDeltaLine === startDeltaLine && tokenEndCharacter <= startCharacter)) {
// => nothing to do
newTokenCount++;
continue;
} else if (tokenDeltaLine === startDeltaLine && tokenStartCharacter < startCharacter) {
sparseMultilineTokens.ts ×9
// => the token survives, but it needs to shrink
if (tokenDeltaLine === endDeltaLine && tokenEndCharacter > endCharacter) {
// 1d. The token starts before, the deletion range is inside the token
// => the token shrinks by the deletion character count
tokenEndCharacter -= (endCharacter - startCharacter);
} else {
// 1b. The token starts before, the deletion range ends after the token
// 1c. The token starts before, the deletion range ends precisely with the token
// => the token shrinks its ending to the deletion start
tokenEndCharacter = startCharacter;
}
} else if (tokenDeltaLine === startDeltaLine && tokenStartCharacter === startCharacter) {
sparseMultilineTokens.ts ×9
// 2a, 2b, 2c
if (tokenDeltaLine === endDeltaLine && tokenEndCharacter > endCharacter) {
// 2c. The token starts at the same position, and ends after the deletion range
// => the token shrinks by the deletion character count
tokenEndCharacter -= (endCharacter - startCharacter);
} else {
// 2a. The token starts at the same position, and ends inside the deletion range
// 2b. The token starts at the same position, and ends at the same position as the deletion range
// => the token is deleted
hasDeletedTokens = true;
continue;
}
} else if (tokenDeltaLine < endDeltaLine || (tokenDeltaLine === endDeltaLine && tokenStartCharacter < endCharacter)) {
sparseMultilineTokens.ts ×9
if (tokenDeltaLine === endDeltaLine && tokenEndCharacter > endCharacter) {
// 3c. The token starts inside the deletion range, and ends after the deletion range
// => the token moves to continue right after the deletion
tokenDeltaLine = startDeltaLine;
tokenStartCharacter = startCharacter;
tokenEndCharacter = tokenStartCharacter + (tokenEndCharacter - endCharacter);
} else {
// 3a. The token is inside the deletion range
// 3b. The token starts inside the deletion range, and ends at the same position as the deletion range
// => the token is deleted
hasDeletedTokens = true;
continue;
}
// 4. (partial) The token starts after the deletion range, on a line below...
sparseMultilineTokens.ts ×10
if (deletedLineCount === 0 && !hasDeletedTokens) {
// early stop, there is no need to walk all the tokens and do nothing...
newTokenCount = tokenCount;
break;
}
} else if (tokenDeltaLine === endDeltaLine && tokenStartCharacter >= endCharacter) {
sparseMultilineTokens.ts ×9
// 4. (continued) The token starts after the deletion range, on the last line where a deletion occurs
sparseMultilineTokens.ts ×2
if (horizontalShiftForFirstLineTokens && tokenDeltaLine === 0) {
tokenEndCharacter += horizontalShiftForFirstLineTokens;
}
tokenStartCharacter -= (endCharacter - startCharacter);
tokenEndCharacter -= (endCharacter - startCharacter);
} else {
throw new Error(`Not possible!`);
}
const destOffset = 4 * newTokenCount;
tokens[destOffset] = tokenDeltaLine;
tokens[destOffset + 1] = tokenStartCharacter;
tokens[destOffset + 2] = tokenEndCharacter;
tokens[destOffset + 3] = tokenMetadata;
newTokenCount++;
}
this._tokenCount = newTokenCount;
}
public acceptInsertText(deltaLine: number, character: number, eolCount: number, firstLineLength: number, lastLineLength: number, firstCharCode: number): void {
//
// 1. The token is completely before the insertion point
// ----------- |
// 2. The token ends precisely at the insertion point
// -----------|
// 3. The token contains the insertion point
// -----|------
// 4. The token starts precisely at the insertion point
// |-----------
// 5. The token is completely after the insertion point
// | -----------
//
const isInsertingPreciselyOneWordCharacter = (
eolCount === 0
&& (
(firstCharCode >= CharCode.Digit0 && firstCharCode <= CharCode.Digit9)
|| (firstCharCode >= CharCode.A && firstCharCode <= CharCode.Z)
|| (firstCharCode >= CharCode.a && firstCharCode <= CharCode.z)
);
const tokens = this._tokens;
const tokenCount = this._tokenCount;
for (let i = 0; i < tokenCount; i++) {
const offset = 4 * i;
let tokenDeltaLine = tokens[offset];
let tokenStartCharacter = tokens[offset + 1];
let tokenEndCharacter = tokens[offset + 2];
if (tokenDeltaLine < deltaLine || (tokenDeltaLine === deltaLine && tokenEndCharacter < character)) {
// 1. The token is completely before the insertion point
// => nothing to do
continue;
} else if (tokenDeltaLine === deltaLine && tokenEndCharacter === character) {
// 2. The token ends precisely at the insertion point
// => expand the end character only if inserting precisely one character that is a word character
if (isInsertingPreciselyOneWordCharacter) {
tokenEndCharacter += 1;
} else {
continue;
}
} else if (tokenDeltaLine === deltaLine && tokenStartCharacter < character && character < tokenEndCharacter) {
sparseMultilineTokens.ts ×11
if (eolCount === 0) {
// => just expand the end character
tokenEndCharacter += firstLineLength;
} else {
// => cut off the token
tokenEndCharacter = character;
}
// 4. or 5.
if (tokenDeltaLine === deltaLine && tokenStartCharacter === character) {
// => grow the token (by keeping its start constant) only if inserting precisely one character that is a word character
// => otherwise behave as in case 5.
if (isInsertingPreciselyOneWordCharacter) {
continue;
}
if (tokenDeltaLine === deltaLine) {
tokenDeltaLine += eolCount;
// this token is on the line where the insertion is taking place
if (eolCount === 0) {
tokenStartCharacter += firstLineLength;
tokenEndCharacter += firstLineLength;
const tokenLength = tokenEndCharacter - tokenStartCharacter;
tokenStartCharacter = lastLineLength + (tokenStartCharacter - character);
tokenEndCharacter = tokenStartCharacter + tokenLength;
}
} else {
}
tokens[offset] = tokenDeltaLine;
tokens[offset + 1] = tokenStartCharacter;
tokens[offset + 2] = tokenEndCharacter;
}
}
private static _rateLimiter = new RateLimiter(10 / 60); // limit to 10 times per minute
public reportIfInvalid(model: ITextModel, startLineNumber: number): void {
const lineNumber = this._getDeltaLine(i) + startLineNumber;
if (lineNumber < 1) {
SparseMultilineTokensStorage._rateLimiter.runIfNotLimited(() => {
console.error('Invalid Semantic Tokens Data From Extension: lineNumber < 1');
});
SparseMultilineTokensStorage._rateLimiter.runIfNotLimited(() => {
console.error('Invalid Semantic Tokens Data From Extension: lineNumber > model.getLineCount()');
});
} else if (this._getEndCharacter(i) > model.getLineLength(lineNumber)) {
sparseMultilineTokens.ts ×5
SparseMultilineTokensStorage._rateLimiter.runIfNotLimited(() => {
console.error('Invalid Semantic Tokens Data From Extension: end character > model.getLineLength(lineNumber)');
});
}
}
export class SparseLineTokens {
private readonly _tokens: Uint32Array;
constructor(tokens: Uint32Array) {
}
public getCount(): number {
}
public getStartCharacter(tokenIndex: number): number {
}
public getEndCharacter(tokenIndex: number): number {
}
public getMetadata(tokenIndex: number): number {
}