1
>
/*---------------------------------------------------------------------------------------------
intervalTree.ts
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 { Range } from '../core/range.js';
7
>
import { TrackedRangeStickiness, TrackedRangeStickiness as ActualTrackedRangeStickiness } from '../model.js';
8
>
import { ModelDecorationOptions } from './textModel.js';
9
>
10
>
//
11
>
// The red-black tree is based on the "Introduction to Algorithms" by Cormen, Leiserson and Rivest.
12
>
//
13
>
14
>
export const enum ClassName {
15
>
EditorHintDecoration = 'squiggly-hint',
16
>
EditorInfoDecoration = 'squiggly-info',
17
>
EditorWarningDecoration = 'squiggly-warning',
18
>
EditorErrorDecoration = 'squiggly-error',
19
>
EditorUnnecessaryDecoration = 'squiggly-unnecessary',
20
>
EditorUnnecessaryInlineDecoration = 'squiggly-inline-unnecessary',
21
>
EditorDeprecatedInlineDecoration = 'squiggly-inline-deprecated'
22
>
}
23
>
24
>
export const enum NodeColor {
25
>
Black = 0,
26
>
Red = 1,
27
>
}
28
>
29
>
const enum Constants {
30
>
ColorMask = 0b00000001,
31
>
ColorMaskInverse = 0b11111110,
32
>
ColorOffset = 0,
33
>
34
>
IsVisitedMask = 0b00000010,
35
>
IsVisitedMaskInverse = 0b11111101,
36
>
IsVisitedOffset = 1,
37
>
38
>
IsForValidationMask = 0b00000100,
39
>
IsForValidationMaskInverse = 0b11111011,
40
>
IsForValidationOffset = 2,
41
>
42
>
StickinessMask = 0b00011000,
43
>
StickinessMaskInverse = 0b11100111,
44
>
StickinessOffset = 3,
45
>
46
>
CollapseOnReplaceEditMask = 0b00100000,
47
>
CollapseOnReplaceEditMaskInverse = 0b11011111,
48
>
CollapseOnReplaceEditOffset = 5,
49
>
50
>
IsMarginMask = 0b01000000,
51
>
IsMarginMaskInverse = 0b10111111,
52
>
IsMarginOffset = 6,
53
>
54
>
AffectsFontMask = 0b10000000,
55
>
AffectsFontMaskInverse = 0b01111111,
56
>
AffectsFontOffset = 7,
57
>
58
>
/**
59
>
* Due to how deletion works (in order to avoid always walking the right subtree of the deleted node),
60
>
* the deltas for nodes can grow and shrink dramatically. It has been observed, in practice, that unless
61
>
* the deltas are corrected, integer overflow will occur.
62
>
*
63
>
* The integer overflow occurs when 53 bits are used in the numbers, but we will try to avoid it as
64
>
* a node's delta gets below a negative 30 bits number.
65
>
*
66
>
* MIN SMI (SMall Integer) as defined in v8.
67
>
* one bit is lost for boxing/unboxing flag.
68
>
* one bit is lost for sign flag.
69
>
* See https://thibaultlaurens.github.io/javascript/2013/04/29/how-the-v8-engine-works/#tagged-values
70
>
*/
71
>
MIN_SAFE_DELTA = -(1 << 30),
72
>
/**
73
>
* MAX SMI (SMall Integer) as defined in v8.
74
>
* one bit is lost for boxing/unboxing flag.
75
>
* one bit is lost for sign flag.
76
>
* See https://thibaultlaurens.github.io/javascript/2013/04/29/how-the-v8-engine-works/#tagged-values
77
>
*/
78
>
MAX_SAFE_DELTA = 1 << 30,
79
>
}
80
>
81
>
export function getNodeColor(node: IntervalNode): NodeColor {
82
return ((node.metadata & Constants.ColorMask) >>> Constants.ColorOffset);
83
}
85
>
node.metadata = (
86
>
(node.metadata & Constants.ColorMaskInverse) | (color << Constants.ColorOffset)
87
>
);
88
>
}
89
function getNodeIsVisited(node: IntervalNode): boolean {
90
return ((node.metadata & Constants.IsVisitedMask) >>> Constants.IsVisitedOffset) === 1;
91
}
93
>
node.metadata = (
94
>
(node.metadata & Constants.IsVisitedMaskInverse) | ((value ? 1 : 0) << Constants.IsVisitedOffset)
95
>
);
96
>
}
97
function getNodeIsForValidation(node: IntervalNode): boolean {
98
return ((node.metadata & Constants.IsForValidationMask) >>> Constants.IsForValidationOffset) === 1;
99
}
101
>
node.metadata = (
102
>
(node.metadata & Constants.IsForValidationMaskInverse) | ((value ? 1 : 0) << Constants.IsForValidationOffset)
103
>
);
104
>
}
105
function getNodeIsInGlyphMargin(node: IntervalNode): boolean {
106
return ((node.metadata & Constants.IsMarginMask) >>> Constants.IsMarginOffset) === 1;
107
}
109
>
node.metadata = (
110
>
(node.metadata & Constants.IsMarginMaskInverse) | ((value ? 1 : 0) << Constants.IsMarginOffset)
111
>
);
112
>
}
113
function getNodeAffectsFont(node: IntervalNode): boolean {
114
return ((node.metadata & Constants.AffectsFontMask) >>> Constants.AffectsFontOffset) === 1;
115
}
117
>
node.metadata = (
118
>
(node.metadata & Constants.AffectsFontMaskInverse) | ((value ? 1 : 0) << Constants.AffectsFontOffset)
119
>
);
120
>
}
121
function getNodeStickiness(node: IntervalNode): TrackedRangeStickiness {
122
return ((node.metadata & Constants.StickinessMask) >>> Constants.StickinessOffset);
123
}
124
>
function _setNodeStickiness(node: IntervalNode, stickiness: TrackedRangeStickiness): void {
intervalTree.ts
125
>
node.metadata = (
126
>
(node.metadata & Constants.StickinessMaskInverse) | (stickiness << Constants.StickinessOffset)
127
>
);
128
>
}
129
function getCollapseOnReplaceEdit(node: IntervalNode): boolean {
130
return ((node.metadata & Constants.CollapseOnReplaceEditMask) >>> Constants.CollapseOnReplaceEditOffset) === 1;
131
}
133
>
node.metadata = (
134
>
(node.metadata & Constants.CollapseOnReplaceEditMaskInverse) | ((value ? 1 : 0) << Constants.CollapseOnReplaceEditOffset)
135
>
);
136
>
}
137
>
export function setNodeStickiness(node: IntervalNode, stickiness: ActualTrackedRangeStickiness): void {
138
_setNodeStickiness(node, <number>stickiness);
139
}
141
>
export class IntervalNode {
142
>
143
>
/**
144
>
* contains binary encoded information for color, visited, isForValidation and stickiness.
145
>
*/
146
>
public metadata: number;
147
>
148
>
public parent: IntervalNode;
149
>
public left: IntervalNode;
150
>
public right: IntervalNode;
151
>
152
>
public start: number;
153
>
public end: number;
154
>
public delta: number;
155
>
public maxEnd: number;
156
>
157
>
public id: string;
158
>
public ownerId: number;
159
>
public options: ModelDecorationOptions;
160
>
161
>
public cachedVersionId: number;
162
>
public cachedAbsoluteStart: number;
163
>
public cachedAbsoluteEnd: number;
164
>
public range: Range | null;
165
>
166
>
constructor(id: string, start: number, end: number) {
167
>
this.metadata = 0;
168
>
169
>
this.parent = this;
170
>
this.left = this;
171
>
this.right = this;
172
>
setNodeColor(this, NodeColor.Red);
173
>
174
>
this.start = start;
175
>
this.end = end;
176
>
// FORCE_OVERFLOWING_TEST: this.delta = start;
177
>
this.delta = 0;
178
>
this.maxEnd = end;
179
>
180
>
this.id = id;
181
>
this.ownerId = 0;
182
>
this.options = null!;
183
>
setNodeIsForValidation(this, false);
184
>
setNodeIsInGlyphMargin(this, false);
185
>
_setNodeStickiness(this, TrackedRangeStickiness.NeverGrowsWhenTypingAtEdges);
186
>
setCollapseOnReplaceEdit(this, false);
187
>
setNodeAffectsFont(this, false);
188
>
189
>
this.cachedVersionId = 0;
190
>
this.cachedAbsoluteStart = start;
191
>
this.cachedAbsoluteEnd = end;
192
>
this.range = null;
193
>
194
>
setNodeIsVisited(this, false);
195
>
}
196
>
197
>
public reset(versionId: number, start: number, end: number, range: Range): void {
198
this.start = start;
199
this.end = end;