src/vs/base/common/map.ts
1016 LOC · 873 covered · 143 uncovered · 293 ranges · 20961 concepts · 118 introducers · 12741 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
>
/*---------------------------------------------------------------------------------------------
map.ts ×97
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 { URI } from './uri.js';
7
>
8
>
export function getOrSet<K, V>(map: Map<K, V>, key: K, value: V): V {
10
>
if (result === undefined) {
11
>
result = value;
12
>
map.set(key, result);
13
>
}
14
>
15
>
return result;
16
>
}
18
>
export function mapToString<K, V>(map: Map<K, V>): string {
19
const entries: string[] = [];
20
map.forEach((value, key) => {
21
entries.push(`${key} => ${value}`);
22
});
23
24
return `Map(${map.size}) {${entries.join(', ')}}`;
25
}
27
>
export function setToString<K>(set: Set<K>): string {
28
const entries: K[] = [];
29
set.forEach(value => {
30
entries.push(value);
31
});
32
33
return `Set(${set.size}) {${entries.join(', ')}}`;
34
}
36
>
interface ResourceMapKeyFn {
37
>
(resource: URI): string;
38
>
}
39
>
40
>
class ResourceMapEntry<T> {
41
>
constructor(readonly uri: URI, readonly value: T) { }
42
>
}
43
>
44
>
function isEntries<T>(arg: ResourceMap<T> | ResourceMapKeyFn | readonly (readonly [URI, T])[] | undefined): arg is readonly (readonly [URI, T])[] {
map.ts ×4
45
>
return Array.isArray(arg);
46
>
}
48
>
export class ResourceMap<T> implements Map<URI, T> {
49
>
50
>
private static readonly defaultToKey = (resource: URI) => resource.toString();
51
>
52
>
readonly [Symbol.toStringTag] = 'ResourceMap';
53
>
54
>
private readonly map: Map<string, ResourceMapEntry<T>>;
55
>
private readonly toKey: ResourceMapKeyFn;
56
>
57
>
/**
58
>
*
59
>
* @param toKey Custom uri identity function, e.g use an existing `IExtUri#getComparison`-util
60
>
*/
61
>
constructor(toKey?: ResourceMapKeyFn);
62
>
63
>
/**
64
>
*
65
>
* @param other Another resource which this maps is created from
66
>
* @param toKey Custom uri identity function, e.g use an existing `IExtUri#getComparison`-util
67
>
*/
68
>
constructor(other?: ResourceMap<T>, toKey?: ResourceMapKeyFn);
69
>
70
>
/**
71
>
*
72
>
* @param other Another resource which this maps is created from
73
>
* @param toKey Custom uri identity function, e.g use an existing `IExtUri#getComparison`-util
74
>
*/
75
>
constructor(entries?: readonly (readonly [URI, T])[], toKey?: ResourceMapKeyFn);
76
>
77
>
constructor(arg?: ResourceMap<T> | ResourceMapKeyFn | readonly (readonly [URI, T])[], toKey?: ResourceMapKeyFn) {
79
this.map = new Map(arg.map);
80
this.toKey = toKey ?? ResourceMap.defaultToKey;
82
this.map = new Map();
83
this.toKey = toKey ?? ResourceMap.defaultToKey;
84
85
for (const [resource, value] of arg) {
86
this.set(resource, value);
87
}
89
>
this.map = new Map();
90
>
this.toKey = arg ?? ResourceMap.defaultToKey;
91
>
}
92
>
}
94
>
set(resource: URI, value: T): this {
96
>
return this;
97
>
}
99
>
get(resource: URI): T | undefined {
101
>
}
103
>
has(resource: URI): boolean {
105
>
}
107
>
get size(): number {
109
>
}
111
>
clear(): void {
113
>
}
115
>
delete(resource: URI): boolean {
117
>
}
119
>
forEach(clb: (value: T, key: URI, map: Map<URI, T>) => void, thisArg?: object): void {
121
clb = clb.bind(thisArg);
122
}
125
>
}
128
>
*values(): MapIterator<T> {
131
>
}
134
>
*keys(): MapIterator<URI> {
140
>
*entries(): MapIterator<[URI, T]> {
143
>
}
146
>
*[Symbol.iterator](): MapIterator<[URI, T]> {
149
>
}
152
>
153
>
export class ResourceSet implements Set<URI> {
154
>
155
>
readonly [Symbol.toStringTag]: string = 'ResourceSet';
156
>
157
>
private readonly _map: ResourceMap<URI>;
158
>
159
>
constructor(toKey?: ResourceMapKeyFn);
160
>
constructor(entries: readonly URI[], toKey?: ResourceMapKeyFn);
161
>
constructor(entriesOrKey?: readonly URI[] | ResourceMapKeyFn, toKey?: ResourceMapKeyFn) {
166
>
entriesOrKey.forEach(this.add, this);
167
>
}
170
>
171
>
get size(): number {
173
>
}
175
>
add(value: URI): this {
177
>
return this;
178
>
}
180
>
clear(): void {
182
>
}
184
>
delete(value: URI): boolean {
185
return this._map.delete(value);
186
}
188
>
forEach(callbackfn: (value: URI, value2: URI, set: Set<URI>) => void, thisArg?: unknown): void {
189
this._map.forEach((_value, key) => callbackfn.call(thisArg, key, key, this));
190
}
192
>
has(value: URI): boolean {
194
>
}
196
>
entries(): SetIterator<[URI, URI]> {
197
return this._map.entries() as unknown as SetIterator<[URI, URI]>;
198
}
200
>
keys(): SetIterator<URI> {
202
>
}
204
>
values(): SetIterator<URI> {
205
return this._map.keys() as unknown as SetIterator<URI>;
206
}
208
>
[Symbol.iterator](): SetIterator<URI> {
210
>
}
212
>
213
>
214
>
interface Item<K, V> {
215
>
previous: Item<K, V> | undefined;
216
>
next: Item<K, V> | undefined;
217
>
key: K;
218
>
value: V;
219
>
}
220
>
221
>
export const enum Touch {
222
>
None = 0,
223
>
AsOld = 1,
224
>
AsNew = 2
225
>
}
226
>
227
>
export class LinkedMap<K, V> implements Map<K, V> {
228
>
229
>
readonly [Symbol.toStringTag] = 'LinkedMap';
230
>
231
>
private _map: Map<K, Item<K, V>>;
232
>
private _head: Item<K, V> | undefined;
233
>
private _tail: Item<K, V> | undefined;
234
>
private _size: number;
235
>
236
>
private _state: number;
237
>
238
>
constructor() {
240
>
this._head = undefined;
241
>
this._tail = undefined;
242
>
this._size = 0;
243
>
this._state = 0;
244
>
}
246
>
clear(): void {
248
>
this._head = undefined;
249
>
this._tail = undefined;
250
>
this._size = 0;
251
>
this._state++;
252
>
}
254
>
isEmpty(): boolean {
255
return !this._head && !this._tail;
256
}
258
>
get size(): number {
260
>
}
262
>
get first(): V | undefined {
264
>
}
266
>
get last(): V | undefined {
268
>
}
270
>
has(key: K): boolean {
272
>
}
274
>
get(key: K, touch: Touch = Touch.None): V | undefined {
276
>
if (!item) {
278
>
}
281
>
}
285
>
set(key: K, value: V, touch: Touch = Touch.None): this {
287
>
if (item) {
289
>
if (touch !== Touch.None) {
290
>
this.touch(item, touch);
291
>
}
293
>
item = { key, value, next: undefined, previous: undefined };
294
>
switch (touch) {
295
>
case Touch.None:
297
>
break;
299
this.addItemFirst(item);
300
break;
303
>
break;
305
this.addItemLast(item);
306
break;
308
>
this._map.set(key, item);
309
>
this._size++;
310
>
}
311
>
return this;
312
>
}
314
>
delete(key: K): boolean {
316
>
}
318
>
remove(key: K): V | undefined {
320
>
if (!item) {
322
>
}
324
>
this.removeItem(item);
325
>
this._size--;
326
>
return item.value;
327
>
}
329
>
shift(): V | undefined {
330
if (!this._head && !this._tail) {
331
return undefined;
332
}
333
if (!this._head || !this._tail) {
334
throw new Error('Invalid list');
335
}
336
const item = this._head;
337
this._map.delete(item.key);
338
this.removeItem(item);
339
this._size--;
340
return item.value;
341
}
343
>
forEach(callbackfn: (value: V, key: K, map: Map<K, V>) => void, thisArg?: unknown): void {
345
>
let current = this._head;
346
>
while (current) {
347
>
if (thisArg) {
348
callbackfn.bind(thisArg)(current.value, current.key, this);
350
>
callbackfn(current.value, current.key, this);
351
>
}
352
>
if (this._state !== state) {
353
throw new Error(`LinkedMap got modified during iteration.`);
354
}
356
>
}
357
>
}
359
>
keys(): MapIterator<K> {
361
>
const state = this._state;
362
>
let current = this._head;
363
>
const iterator: MapIterator<K> = {
364
>
[Symbol.iterator]() {
365
>
return iterator;
366
>
},
367
>
[Symbol.dispose]() { /* no-op */ },
368
>
next(): IteratorResult<K> {
369
>
if (map._state !== state) {
371
>
}
374
>
current = current.next;
375
>
return result;
377
>
return { value: undefined, done: true };
378
>
}
379
>
}
380
>
};
381
>
return iterator;
382
>
}
384
>
values(): MapIterator<V> {
386
>
const state = this._state;
387
>
let current = this._head;
388
>
const iterator: MapIterator<V> = {
389
>
[Symbol.iterator]() {
390
>
return iterator;
391
>
},
392
>
[Symbol.dispose]() { /* no-op */ },
393
>
next(): IteratorResult<V> {
394
>
if (map._state !== state) {
396
>
}
398
>
const result = { value: current.value, done: false };
399
>
current = current.next;
400
>
return result;
401
>
} else {
402
>
return { value: undefined, done: true };
403
>
}
404
>
}
405
>
};
406
>
return iterator;
407
>
}
409
>
entries(): MapIterator<[K, V]> {
411
>
const state = this._state;
412
>
let current = this._head;
413
>
const iterator: MapIterator<[K, V]> = {
414
>
[Symbol.iterator]() {
415
>
return iterator;
416
>
},
417
>
[Symbol.dispose]() { /* no-op */ },
418
>
next(): IteratorResult<[K, V]> {
419
>
if (map._state !== state) {
421
>
}
423
>
const result: IteratorResult<[K, V]> = { value: [current.key, current.value], done: false };
424
>
current = current.next;
425
>
return result;
426
>
} else {
427
>
return { value: undefined, done: true };
428
>
}
429
>
}
430
>
};
431
>
return iterator;
432
>
}
434
>
[Symbol.iterator](): MapIterator<[K, V]> {
435
return this.entries();
436
}
438
>
protected trimOld(newSize: number) {
440
return;
441
}
443
this.clear();
444
return;
445
}
447
>
let currentSize = this.size;
448
>
while (current && currentSize > newSize) {
449
>
this._map.delete(current.key);
450
>
current = current.next;
451
>
currentSize--;
452
>
}
453
>
this._head = current;
454
>
this._size = currentSize;
455
>
if (current) {
456
>
current.previous = undefined;
457
>
}
458
>
this._state++;
459
>
}
461
>
protected trimNew(newSize: number) {
463
return;
464
}
466
this.clear();
467
return;
468
}
470
>
let currentSize = this.size;
471
>
while (current && currentSize > newSize) {
472
>
this._map.delete(current.key);
473
>
current = current.previous;
474
>
currentSize--;
475
>
}
476
>
this._tail = current;
477
>
this._size = currentSize;
478
>
if (current) {
479
>
current.next = undefined;
480
>
}
481
>
this._state++;
482
>
}
484
>
private addItemFirst(item: Item<K, V>): void {
485
// First time Insert
486
if (!this._head && !this._tail) {
487
this._tail = item;
488
} else if (!this._head) {
489
throw new Error('Invalid list');
490
} else {
491
item.next = this._head;
492
this._head.previous = item;
493
}
494
this._head = item;
495
this._state++;
496
}
498
>
private addItemLast(item: Item<K, V>): void {
500
>
if (!this._head && !this._tail) {
501
>
this._head = item;
502
>
} else if (!this._tail) {
503
throw new Error('Invalid list');
505
>
item.previous = this._tail;
506
>
this._tail.next = item;
507
>
}
509
>
this._state++;
510
>
}
512
>
private removeItem(item: Item<K, V>): void {
515
>
this._tail = undefined;
516
>
}
519
>
// by the case above.
520
>
if (!item.next) {
521
throw new Error('Invalid list');
522
}
524
>
this._head = item.next;
525
>
}
527
>
// This can only happen if size === 1 which is handled
528
>
// by the case above.
529
>
if (!item.previous) {
530
throw new Error('Invalid list');
531
}
533
>
this._tail = item.previous;
534
>
}
535
else {
536
const next = item.next;
537
const previous = item.previous;
538
if (!next || !previous) {
539
throw new Error('Invalid list');
540
}
541
next.previous = previous;
542
previous.next = next;
543
}
545
>
item.previous = undefined;
546
>
this._state++;
547
>
}
549
>
private touch(item: Item<K, V>, touch: Touch): void {
551
throw new Error('Invalid list');
552
}
554
return;
555
}
557
>
if (touch === Touch.AsOld) {
560
>
}
562
>
const next = item.next;
563
>
const previous = item.previous;
564
>
565
>
// Unlink the item
566
>
if (item === this._tail) {
568
>
// So there are more than on item in the map
569
>
previous!.next = undefined;
570
>
this._tail = previous;
571
>
}
573
>
// Both next and previous are not undefined since item was neither head nor tail.
574
>
next!.previous = previous;
575
>
previous!.next = next;
576
>
}
578
>
// Insert the node at head
579
>
item.previous = undefined;
580
>
item.next = this._head;
581
>
this._head.previous = item;
582
>
this._head = item;
583
>
this._state++;
587
>
}
589
>
const next = item.next;
590
>
const previous = item.previous;
591
>
592
>
// Unlink the item.
593
>
if (item === this._head) {
595
>
// So there are more than on item in the map
596
>
next!.previous = undefined;
597
>
this._head = next;
600
>
next!.previous = previous;
601
>
previous!.next = next;
602
>
}
604
>
item.previous = this._tail;
605
>
this._tail.next = item;
606
>
this._tail = item;
607
>
this._state++;
608
>
}
611
>
toJSON(): [K, V][] {
613
>
614
>
this.forEach((value, key) => {
615
>
data.push([key, value]);
616
>
});
617
>
618
>
return data;
619
>
}
621
>
fromJSON(data: [K, V][]): void {
623
>
624
>
for (const [key, value] of data) {
625
>
this.set(key, value);
626
>
}
627
>
}
629
>
630
>
abstract class Cache<K, V> extends LinkedMap<K, V> {
631
>
632
>
protected _limit: number;
633
>
protected _ratio: number;
634
>
635
>
constructor(limit: number, ratio: number = 1) {
637
>
this._limit = limit;
638
>
this._ratio = Math.min(Math.max(0, ratio), 1);
639
>
}
641
>
get limit(): number {
642
return this._limit;
643
}
645
>
set limit(limit: number) {
647
>
this.checkTrim();
648
>
}
650
>
get ratio(): number {
651
return this._ratio;
652
}
654
>
set ratio(ratio: number) {
655
this._ratio = Math.min(Math.max(0, ratio), 1);
656
this.checkTrim();
657
}
659
>
override get(key: K, touch: Touch = Touch.AsNew): V | undefined {
661
>
}
663
>
peek(key: K): V | undefined {
665
>
}
667
>
override set(key: K, value: V): this {
669
>
return this;
670
>
}
672
>
protected checkTrim() {
675
>
}
678
>
protected abstract trim(newSize: number): void;
679
>
}
680
>
681
>
export class LRUCache<K, V> extends Cache<K, V> {
682
>
683
>
constructor(limit: number, ratio: number = 1) {
685
>
}
687
>
protected override trim(newSize: number) {
689
>
}
691
>
override set(key: K, value: V): this {
693
>
this.checkTrim();
694
>
return this;
695
>
}
697
>
698
>
export class MRUCache<K, V> extends Cache<K, V> {
699
>
700
>
constructor(limit: number, ratio: number = 1) {
702
>
}
704
>
protected override trim(newSize: number) {
706
>
}
708
>
override set(key: K, value: V): this {
711
>
}
713
>
super.set(key, value);
714
>
return this;
715
>
}
717
>
718
>
export class CounterSet<T> {
719
720
private map = new Map<T, number>();
722
>
add(value: T): CounterSet<T> {
723
this.map.set(value, (this.map.get(value) || 0) + 1);
724
return this;
725
}
727
>
delete(value: T): boolean {
728
let counter = this.map.get(value) || 0;
729
730
if (counter === 0) {
731
return false;
732
}
733
734
counter--;
735
736
if (counter === 0) {
737
this.map.delete(value);
738
} else {
739
this.map.set(value, counter);
740
}
741
742
return true;
743
}
745
>
has(value: T): boolean {
746
return this.map.has(value);
747
}
749
>
750
>
/**
751
>
* A map that allows access both by keys and values.
752
>
* **NOTE**: values need to be unique.
753
>
*/
754
>
export class BidirectionalMap<K, V> {
755
>
756
>
private readonly _m1 = new Map<K, V>();
757
>
private readonly _m2 = new Map<V, K>();
758
>
759
>
constructor(entries?: readonly (readonly [K, V])[]) {
761
for (const [key, value] of entries) {
762
this.set(key, value);
763
}
764
}
767
>
clear(): void {
769
>
this._m2.clear();
770
>
}
772
>
set(key: K, value: V): void {
774
>
this._m2.set(value, key);
775
>
}
777
>
get(key: K): V | undefined {
779
>
}
781
>
getKey(value: V): K | undefined {
783
>
}
785
>
delete(key: K): boolean {
787
>
if (value === undefined) {
789
>
}
791
>
this._m2.delete(value);
792
>
return true;
795
>
forEach(callbackfn: (value: V, key: K, map: BidirectionalMap<K, V>) => void, thisArg?: unknown): void {
797
>
callbackfn.call(thisArg, value, key, this);
798
>
});
799
>
}
801
>
keys(): IterableIterator<K> {
802
return this._m1.keys();
803
}
805
>
values(): IterableIterator<V> {
806
return this._m1.values();
807
}
809
>
810
>
export class SetMap<K, V> {
812
>
private map = new Map<K, Set<V>>();
814
>
add(key: K, value: V): void {
816
>
817
>
if (!values) {
818
>
values = new Set<V>();
819
>
this.map.set(key, values);
820
>
}
821
>
822
>
values.add(value);
823
>
}
825
>
delete(key: K, value: V): void {
827
>
828
>
if (!values) {
829
return;
830
}
832
>
values.delete(value);
833
>
834
>
if (values.size === 0) {
835
>
this.map.delete(key);
836
>
}
837
>
}
839
>
forEach(key: K, fn: (value: V) => void): void {
841
>
842
>
if (!values) {
844
>
}
846
>
values.forEach(fn);
849
>
get(key: K): ReadonlySet<V> {
851
>
if (!values) {
853
>
}
857
>
858
>
export function mapsStrictEqualIgnoreOrder(a: Map<unknown, unknown>, b: Map<unknown, unknown>): boolean {
860
return true;
861
}
863
>
if (a.size !== b.size) {
864
>
return false;
865
>
}
866
>
867
>
for (const [key, value] of a) {
868
>
if (!b.has(key) || b.get(key) !== value) {
869
return false;
870
}
872
>
873
>
for (const [key] of b) {
874
>
if (!a.has(key)) {
875
return false;
876
}
878
>
879
>
return true;
880
>
}
882
>
/**
883
>
* A map that is addressable with an arbitrary number of keys. This is useful in high performance
884
>
* scenarios where creating a composite key whenever the data is accessed is too expensive. For
885
>
* example for a very hot function, constructing a string like `first-second-third` for every call
886
>
* will cause a significant hit to performance.
887
>
*/
888
>
export class NKeyMap<TValue, TKeys extends (string | boolean | number)[]> {
891
>
/**
892
>
* Sets a value on the map. Note that unlike a standard `Map`, the first argument is the value.
893
>
* This is because the spread operator is used for the keys and must be last..
894
>
* @param value The value to set.
895
>
* @param keys The keys for the value.
896
>
*/
897
>
public set(value: TValue, ...keys: [...TKeys]): void {
899
>
for (let i = 0; i < keys.length - 1; i++) {
900
>
let nextMap = currentMap.get(keys[i]);
901
>
if (nextMap === undefined) {
902
>
nextMap = new Map();
903
>
currentMap.set(keys[i], nextMap);
904
>
}
905
>
currentMap = nextMap;
906
>
}
907
>
currentMap.set(keys[keys.length - 1], value);
908
>
}
910
>
public get(...keys: [...TKeys]): TValue | undefined {
912
>
for (let i = 0; i < keys.length - 1; i++) {
913
>
const nextMap = currentMap.get(keys[i]);
914
>
if (nextMap === undefined) {
916
>
}
918
>
}
919
>
return currentMap.get(keys[keys.length - 1]);
922
>
public delete(...keys: [...TKeys]): boolean {
924
>
let currentMap = this._data;
925
>
for (let i = 0; i < keys.length - 1; i++) {
926
>
const nextMap = currentMap.get(keys[i]);
927
>
if (nextMap === undefined) {
929
>
}
931
>
maps.push(currentMap);
932
>
}
933
>
const deleted = currentMap.delete(keys[keys.length - 1]);
937
>
}
939
>
return deleted;
942
>
public deleteAll(...keys: Partial<TKeys>): boolean {
945
>
this._data.clear();
946
>
return hadData;
947
>
}
949
>
let currentMap = this._data;
950
>
for (let i = 0; i < keys.length - 1; i++) {
952
>
if (nextMap === undefined) {
953
return false;
954
}
956
>
maps.push(currentMap);
957
>
}
959
>
for (let i = keys.length - 2; deleted && i >= 0; i--) {
962
>
}
965
>
}
967
>
public clear(): void {
969
>
}
971
>
public *getAll(...keys: Partial<TKeys>): IterableIterator<TValue> {
973
>
for (const key of keys) {
974
>
const nextMap = currentMap.get(key);
975
>
if (nextMap === undefined) {
977
>
}
979
>
}
980
>
yield* this._values(currentMap);
983
>
public *values(): IterableIterator<TValue> {
985
>
}
987
>
private *_values(map: Map<any, any>): IterableIterator<TValue> {
992
>
yield value;
997
>
/**
998
>
* Get a textual representation of the map for debugging purposes.
999
>
*/
1000
>
public toString(): string {
1002
>
let result = '';
1003
>
for (const [key, value] of map) {
1004
>
result += `${' '.repeat(depth)}${key}: `;
1005
>
if (value instanceof Map) {
1006
>
result += '\n' + printMap(value, depth + 1);
1007
>
} else {
1008
>
result += `${value}\n`;
1009
>
}
1010
>
}
1011
>
return result;
1012
>
};
1013
>
1014
>
return printMap(this._data, 0);
1015
>
}