1/* @internal */ 2namespace ts { 3 type GetIteratorCallback = <I extends readonly any[] | ReadonlySetShim<any> | ReadonlyMapShim<any, any> | undefined>(iterable: I) => IteratorShim< 4 I extends ReadonlyMapShim<infer K, infer V> ? [K, V] : 5 I extends ReadonlySetShim<infer T> ? T : 6 I extends readonly (infer T)[] ? T : 7 I extends undefined ? undefined : 8 never>; 9 10 type IteratorResultShim<T> = 11 | { value: T, done?: false } 12 | { value: void, done: true }; 13 14 interface IteratorShim<T> { 15 next(): IteratorResultShim<T>; 16 } 17 18 interface ReadonlyMapShim<K, V> { 19 readonly size: number; 20 get(key: K): V | undefined; 21 has(key: K): boolean; 22 keys(): IteratorShim<K>; 23 values(): IteratorShim<V>; 24 entries(): IteratorShim<[K, V]>; 25 forEach(action: (value: V, key: K) => void): void; 26 } 27 28 interface MapShim<K, V> extends ReadonlyMapShim<K, V> { 29 set(key: K, value: V): this; 30 delete(key: K): boolean; 31 clear(): void; 32 } 33 34 type MapShimConstructor = new <K, V>(iterable?: readonly (readonly [K, V])[] | ReadonlyMapShim<K, V>) => MapShim<K, V>; 35 36 interface ReadonlySetShim<T> { 37 readonly size: number; 38 has(value: T): boolean; 39 keys(): IteratorShim<T>; 40 values(): IteratorShim<T>; 41 entries(): IteratorShim<[T, T]>; 42 forEach(action: (value: T, key: T) => void): void; 43 } 44 45 interface SetShim<T> extends ReadonlySetShim<T> { 46 add(value: T): this; 47 delete(value: T): boolean; 48 clear(): void; 49 } 50 51 type SetShimConstructor = new <T>(iterable?: readonly T[] | ReadonlySetShim<T>) => SetShim<T>; 52 53 interface MapData<K, V> { 54 size: number; 55 readonly head: MapEntry<K, V>; 56 tail: MapEntry<K, V>; 57 } 58 59 interface MapEntry<K, V> { 60 readonly key?: K; 61 value?: V; 62 /** 63 * Specifies the next entry in the linked list. 64 */ 65 next?: MapEntry<K, V>; 66 /** 67 * Specifies the previous entry in the linked list. 68 * Must be set when the entry is part of a Map/Set. 69 * When 'undefined', iterators should skip the next entry. 70 * This will be set to 'undefined' when an entry is deleted. 71 * See https://github.com/Microsoft/TypeScript/pull/27292 for more information. 72 */ 73 prev?: MapEntry<K, V>; 74 } 75 76 interface IteratorData<K, V, U extends (K | V | [K, V])> { 77 current?: MapEntry<K, V>; 78 selector: (key: K, value: V) => U; 79 } 80 81 function createMapData<K, V>(): MapData<K, V> { 82 const sentinel: MapEntry<K, V> = {}; 83 sentinel.prev = sentinel; 84 return { head: sentinel, tail: sentinel, size: 0 }; 85 } 86 87 function createMapEntry<K, V>(key: K, value: V): MapEntry<K, V> { 88 return { key, value, next: undefined, prev: undefined }; 89 } 90 91 function sameValueZero(x: unknown, y: unknown) { 92 // Treats -0 === 0 and NaN === NaN 93 return x === y || x !== x && y !== y; 94 } 95 96 function getPrev<K, V>(entry: MapEntry<K, V>) { 97 const prev = entry.prev; 98 // Entries without a 'prev' have been removed from the map. 99 // An entry whose 'prev' points to itself is the head of the list and is invalid here. 100 if (!prev || prev === entry) throw new Error("Illegal state"); 101 return prev; 102 } 103 104 function getNext<K, V>(entry: MapEntry<K, V> | undefined) { 105 while (entry) { 106 // Entries without a 'prev' have been removed from the map. Their 'next' 107 // pointer should point to the previous entry prior to deletion and 108 // that entry should be skipped to resume iteration. 109 const skipNext = !entry.prev; 110 entry = entry.next; 111 if (skipNext) { 112 continue; 113 } 114 return entry; 115 } 116 } 117 118 function getEntry<K, V>(data: MapData<K, V>, key: K): MapEntry<K, V> | undefined { 119 // We walk backwards from 'tail' to prioritize recently added entries. 120 // We skip 'head' because it is an empty entry used to track iteration start. 121 for (let entry = data.tail; entry !== data.head; entry = getPrev(entry)) { 122 if (sameValueZero(entry.key, key)) { 123 return entry; 124 } 125 } 126 } 127 128 function addOrUpdateEntry<K, V>(data: MapData<K, V>, key: K, value: V): MapEntry<K, V> | undefined { 129 const existing = getEntry(data, key); 130 if (existing) { 131 existing.value = value; 132 return; 133 } 134 135 const entry = createMapEntry(key, value); 136 entry.prev = data.tail; 137 data.tail.next = entry; 138 data.tail = entry; 139 data.size++; 140 return entry; 141 } 142 143 function deleteEntry<K, V>(data: MapData<K, V>, key: K): MapEntry<K, V> | undefined { 144 // We walk backwards from 'tail' to prioritize recently added entries. 145 // We skip 'head' because it is an empty entry used to track iteration start. 146 for (let entry = data.tail; entry !== data.head; entry = getPrev(entry)) { 147 // all entries in the map should have a 'prev' pointer. 148 if (entry.prev === undefined) throw new Error("Illegal state"); 149 if (sameValueZero(entry.key, key)) { 150 if (entry.next) { 151 entry.next.prev = entry.prev; 152 } 153 else { 154 // an entry in the map without a 'next' pointer must be the 'tail'. 155 if (data.tail !== entry) throw new Error("Illegal state"); 156 data.tail = entry.prev; 157 } 158 159 entry.prev.next = entry.next; 160 entry.next = entry.prev; 161 entry.prev = undefined; 162 data.size--; 163 return entry; 164 } 165 } 166 } 167 168 function clearEntries<K, V>(data: MapData<K, V>) { 169 let node = data.tail; 170 while (node !== data.head) { 171 const prev = getPrev(node); 172 node.next = data.head; 173 node.prev = undefined; 174 node = prev; 175 } 176 data.head.next = undefined; 177 data.tail = data.head; 178 data.size = 0; 179 } 180 181 function forEachEntry<K, V>(data: MapData<K, V>, action: (value: V, key: K) => void) { 182 let entry: MapEntry<K, V> | undefined = data.head; 183 while (entry) { 184 entry = getNext(entry); 185 if (entry) { 186 action(entry.value!, entry.key!); 187 } 188 } 189 } 190 191 function forEachIteration<T>(iterator: IteratorShim<T> | undefined, action: (value: any) => void) { 192 if (iterator) { 193 for (let step = iterator.next(); !step.done; step = iterator.next()) { 194 action(step.value); 195 } 196 } 197 } 198 199 function createIteratorData<K, V, U extends (K | V | [K, V])>(data: MapData<K, V>, selector: (key: K, value: V) => U): IteratorData<K, V, U> { 200 return { current: data.head, selector }; 201 } 202 203 function iteratorNext<K, V, U extends (K | V | [K, V])>(data: IteratorData<K, V, U>): IteratorResultShim<U> { 204 // Navigate to the next entry. 205 data.current = getNext(data.current); 206 if (data.current) { 207 return { value: data.selector(data.current.key!, data.current.value!), done: false }; 208 } 209 else { 210 return { value: undefined as never, done: true }; 211 } 212 } 213 214 /* @internal */ 215 export namespace ShimCollections { 216 export function createMapShim(getIterator: GetIteratorCallback): MapShimConstructor { 217 class MapIterator<K, V, U extends (K | V | [K, V])> { 218 private _data: IteratorData<K, V, U>; 219 constructor(data: MapData<K, V>, selector: (key: K, value: V) => U) { 220 this._data = createIteratorData(data, selector); 221 } 222 next() { return iteratorNext(this._data); } 223 } 224 return class Map<K, V> implements MapShim<K, V> { 225 private _mapData = createMapData<K, V>(); 226 constructor(iterable?: readonly (readonly [K, V])[] | ReadonlyMapShim<K, V>) { 227 forEachIteration(getIterator(iterable), ([key, value]) => this.set(key, value)); 228 } 229 get size() { return this._mapData.size; } 230 get(key: K): V | undefined { return getEntry(this._mapData, key)?.value; } 231 set(key: K, value: V): this { return addOrUpdateEntry(this._mapData, key, value), this; } 232 has(key: K): boolean { return !!getEntry(this._mapData, key); } 233 delete(key: K): boolean { return !!deleteEntry(this._mapData, key); } 234 clear(): void { clearEntries(this._mapData); } 235 keys(): IteratorShim<K> { return new MapIterator(this._mapData, (key, _value) => key); } 236 values(): IteratorShim<V> { return new MapIterator(this._mapData, (_key, value) => value); } 237 entries(): IteratorShim<[K, V]> { return new MapIterator(this._mapData, (key, value) => [key, value]); } 238 forEach(action: (value: V, key: K) => void): void { forEachEntry(this._mapData, action); } 239 }; 240 } 241 242 export function createSetShim(getIterator: GetIteratorCallback): SetShimConstructor { 243 class SetIterator<K, V, U extends (K | V | [K, V])> { 244 private _data: IteratorData<K, V, U>; 245 constructor(data: MapData<K, V>, selector: (key: K, value: V) => U) { 246 this._data = createIteratorData(data, selector); 247 } 248 next() { return iteratorNext(this._data); } 249 } 250 return class Set<T> implements SetShim<T> { 251 private _mapData = createMapData<T, T>(); 252 constructor(iterable?: readonly T[] | ReadonlySetShim<T>) { 253 forEachIteration(getIterator(iterable), value => this.add(value)); 254 } 255 get size() { return this._mapData.size; } 256 add(value: T): this { return addOrUpdateEntry(this._mapData, value, value), this; } 257 has(value: T): boolean { return !!getEntry(this._mapData, value); } 258 delete(value: T): boolean { return !!deleteEntry(this._mapData, value); } 259 clear(): void { clearEntries(this._mapData); } 260 keys(): IteratorShim<T> { return new SetIterator(this._mapData, (key, _value) => key); } 261 values(): IteratorShim<T> { return new SetIterator(this._mapData, (_key, value) => value); } 262 entries(): IteratorShim<[T, T]> { return new SetIterator(this._mapData, (key, value) => [key, value]); } 263 forEach(action: (value: T, key: T) => void): void { forEachEntry(this._mapData, action); } 264 }; 265 } 266 } 267} 268