1/* @internal */ 2namespace ts { 3 type GetIteratorCallback = <I extends readonly any[] | ReadonlySet<any> | ReadonlyESMap<any, any> | undefined>(iterable: I) => Iterator< 4 I extends ReadonlyESMap<infer K, infer V> ? [K, V] : 5 I extends ReadonlySet<infer T> ? T : 6 I extends readonly (infer T)[] ? T : 7 I extends undefined ? undefined : 8 never>; 9 10 function getCollectionImplementation< 11 K1 extends MatchingKeys<typeof NativeCollections, () => any>, 12 K2 extends MatchingKeys<typeof ShimCollections, (getIterator?: GetIteratorCallback) => ReturnType<(typeof NativeCollections)[K1]>> 13 >(name: string, nativeFactory: K1, shimFactory: K2): NonNullable<ReturnType<(typeof NativeCollections)[K1]>> { 14 // NOTE: ts.ShimCollections will be defined for typescriptServices.js but not for tsc.js, so we must test for it. 15 const constructor = NativeCollections[nativeFactory]() ?? ShimCollections?.[shimFactory](getIterator); 16 if (constructor) return constructor as NonNullable<ReturnType<(typeof NativeCollections)[K1]>>; 17 throw new Error(`TypeScript requires an environment that provides a compatible native ${name} implementation.`); 18 } 19 20 export const Map = getCollectionImplementation("Map", "tryGetNativeMap", "createMapShim"); 21 export const Set = getCollectionImplementation("Set", "tryGetNativeSet", "createSetShim"); 22 23 export function getIterator<I extends readonly any[] | ReadonlySet<any> | ReadonlyESMap<any, any> | undefined>(iterable: I): Iterator< 24 I extends ReadonlyESMap<infer K, infer V> ? [K, V] : 25 I extends ReadonlySet<infer T> ? T : 26 I extends readonly (infer T)[] ? T : 27 I extends undefined ? undefined : 28 never>; 29 export function getIterator<K, V>(iterable: ReadonlyESMap<K, V>): Iterator<[K, V]>; 30 export function getIterator<K, V>(iterable: ReadonlyESMap<K, V> | undefined): Iterator<[K, V]> | undefined; 31 export function getIterator<T>(iterable: readonly T[] | ReadonlySet<T>): Iterator<T>; 32 export function getIterator<T>(iterable: readonly T[] | ReadonlySet<T> | undefined): Iterator<T> | undefined; 33 export function getIterator(iterable: readonly any[] | ReadonlySet<any> | ReadonlyESMap<any, any> | undefined): Iterator<any> | undefined { 34 if (iterable) { 35 if (isArray(iterable)) return arrayIterator(iterable); 36 if (iterable instanceof Map) return iterable.entries(); 37 if (iterable instanceof Set) return iterable.values(); 38 throw new Error("Iteration not supported."); 39 } 40 } 41 42 export const emptyArray: never[] = [] as never[]; 43 export const emptyMap: ReadonlyESMap<never, never> = new Map<never, never>(); 44 export const emptySet: ReadonlySet<never> = new Set<never>(); 45 46 /** 47 * Create a new map. 48 * @deprecated Use `new Map()` instead. 49 */ 50 export function createMap<K, V>(): ESMap<K, V>; 51 export function createMap<T>(): ESMap<string, T>; 52 export function createMap<K, V>(): ESMap<K, V> { 53 return new Map<K, V>(); 54 } 55 56 /** 57 * Create a new map from a template object is provided, the map will copy entries from it. 58 * @deprecated Use `new Map(getEntries(template))` instead. 59 */ 60 export function createMapFromTemplate<T>(template: MapLike<T>): ESMap<string, T> { 61 const map: ESMap<string, T> = new Map<string, T>(); 62 63 // Copies keys/values from template. Note that for..in will not throw if 64 // template is undefined, and instead will just exit the loop. 65 for (const key in template) { 66 if (hasOwnProperty.call(template, key)) { 67 map.set(key, template[key]); 68 } 69 } 70 71 return map; 72 } 73 74 export function length(array: readonly any[] | undefined): number { 75 return array ? array.length : 0; 76 } 77 78 /** 79 * Iterates through 'array' by index and performs the callback on each element of array until the callback 80 * returns a truthy value, then returns that value. 81 * If no such value is found, the callback is applied to each element of array and undefined is returned. 82 */ 83 export function forEach<T, U>(array: readonly T[] | undefined, callback: (element: T, index: number) => U | undefined): U | undefined { 84 if (array) { 85 for (let i = 0; i < array.length; i++) { 86 const result = callback(array[i], i); 87 if (result) { 88 return result; 89 } 90 } 91 } 92 return undefined; 93 } 94 95 /** 96 * Like `forEach`, but iterates in reverse order. 97 */ 98 export function forEachRight<T, U>(array: readonly T[] | undefined, callback: (element: T, index: number) => U | undefined): U | undefined { 99 if (array) { 100 for (let i = array.length - 1; i >= 0; i--) { 101 const result = callback(array[i], i); 102 if (result) { 103 return result; 104 } 105 } 106 } 107 return undefined; 108 } 109 110 /** Like `forEach`, but suitable for use with numbers and strings (which may be falsy). */ 111 export function firstDefined<T, U>(array: readonly T[] | undefined, callback: (element: T, index: number) => U | undefined): U | undefined { 112 if (array === undefined) { 113 return undefined; 114 } 115 116 for (let i = 0; i < array.length; i++) { 117 const result = callback(array[i], i); 118 if (result !== undefined) { 119 return result; 120 } 121 } 122 return undefined; 123 } 124 125 export function firstDefinedIterator<T, U>(iter: Iterator<T>, callback: (element: T) => U | undefined): U | undefined { 126 while (true) { 127 const iterResult = iter.next(); 128 if (iterResult.done) { 129 return undefined; 130 } 131 const result = callback(iterResult.value); 132 if (result !== undefined) { 133 return result; 134 } 135 } 136 } 137 138 export function reduceLeftIterator<T, U>(iterator: Iterator<T> | undefined, f: (memo: U, value: T, i: number) => U, initial: U): U { 139 let result = initial; 140 if (iterator) { 141 for (let step = iterator.next(), pos = 0; !step.done; step = iterator.next(), pos++) { 142 result = f(result, step.value, pos); 143 } 144 } 145 return result; 146 } 147 148 export function zipWith<T, U, V>(arrayA: readonly T[], arrayB: readonly U[], callback: (a: T, b: U, index: number) => V): V[] { 149 const result: V[] = []; 150 Debug.assertEqual(arrayA.length, arrayB.length); 151 for (let i = 0; i < arrayA.length; i++) { 152 result.push(callback(arrayA[i], arrayB[i], i)); 153 } 154 return result; 155 } 156 157 export function zipToIterator<T, U>(arrayA: readonly T[], arrayB: readonly U[]): Iterator<[T, U]> { 158 Debug.assertEqual(arrayA.length, arrayB.length); 159 let i = 0; 160 return { 161 next() { 162 if (i === arrayA.length) { 163 return { value: undefined as never, done: true }; 164 } 165 i++; 166 return { value: [arrayA[i - 1], arrayB[i - 1]] as [T, U], done: false }; 167 } 168 }; 169 } 170 171 export function zipToMap<K, V>(keys: readonly K[], values: readonly V[]): ESMap<K, V> { 172 Debug.assert(keys.length === values.length); 173 const map = new Map<K, V>(); 174 for (let i = 0; i < keys.length; ++i) { 175 map.set(keys[i], values[i]); 176 } 177 return map; 178 } 179 180 /** 181 * Creates a new array with `element` interspersed in between each element of `input` 182 * if there is more than 1 value in `input`. Otherwise, returns the existing array. 183 */ 184 export function intersperse<T>(input: T[], element: T): T[] { 185 if (input.length <= 1) { 186 return input; 187 } 188 const result: T[] = []; 189 for (let i = 0, n = input.length; i < n; i++) { 190 if (i) result.push(element); 191 result.push(input[i]); 192 } 193 return result; 194 } 195 196 /** 197 * Iterates through `array` by index and performs the callback on each element of array until the callback 198 * returns a falsey value, then returns false. 199 * If no such value is found, the callback is applied to each element of array and `true` is returned. 200 */ 201 export function every<T>(array: readonly T[] | undefined, callback: (element: T, index: number) => boolean): boolean { 202 if (array) { 203 for (let i = 0; i < array.length; i++) { 204 if (!callback(array[i], i)) { 205 return false; 206 } 207 } 208 } 209 210 return true; 211 } 212 213 /** Works like Array.prototype.find, returning `undefined` if no element satisfying the predicate is found. */ 214 export function find<T, U extends T>(array: readonly T[], predicate: (element: T, index: number) => element is U): U | undefined; 215 export function find<T>(array: readonly T[], predicate: (element: T, index: number) => boolean): T | undefined; 216 export function find<T>(array: readonly T[], predicate: (element: T, index: number) => boolean): T | undefined { 217 for (let i = 0; i < array.length; i++) { 218 const value = array[i]; 219 if (predicate(value, i)) { 220 return value; 221 } 222 } 223 return undefined; 224 } 225 226 export function findLast<T, U extends T>(array: readonly T[], predicate: (element: T, index: number) => element is U): U | undefined; 227 export function findLast<T>(array: readonly T[], predicate: (element: T, index: number) => boolean): T | undefined; 228 export function findLast<T>(array: readonly T[], predicate: (element: T, index: number) => boolean): T | undefined { 229 for (let i = array.length - 1; i >= 0; i--) { 230 const value = array[i]; 231 if (predicate(value, i)) { 232 return value; 233 } 234 } 235 return undefined; 236 } 237 238 /** Works like Array.prototype.findIndex, returning `-1` if no element satisfying the predicate is found. */ 239 export function findIndex<T>(array: readonly T[], predicate: (element: T, index: number) => boolean, startIndex?: number): number { 240 for (let i = startIndex || 0; i < array.length; i++) { 241 if (predicate(array[i], i)) { 242 return i; 243 } 244 } 245 return -1; 246 } 247 248 export function findLastIndex<T>(array: readonly T[], predicate: (element: T, index: number) => boolean, startIndex?: number): number { 249 for (let i = startIndex === undefined ? array.length - 1 : startIndex; i >= 0; i--) { 250 if (predicate(array[i], i)) { 251 return i; 252 } 253 } 254 return -1; 255 } 256 257 /** 258 * Returns the first truthy result of `callback`, or else fails. 259 * This is like `forEach`, but never returns undefined. 260 */ 261 export function findMap<T, U>(array: readonly T[], callback: (element: T, index: number) => U | undefined): U { 262 for (let i = 0; i < array.length; i++) { 263 const result = callback(array[i], i); 264 if (result) { 265 return result; 266 } 267 } 268 return Debug.fail(); 269 } 270 271 export function contains<T>(array: readonly T[] | undefined, value: T, equalityComparer: EqualityComparer<T> = equateValues): boolean { 272 if (array) { 273 for (const v of array) { 274 if (equalityComparer(v, value)) { 275 return true; 276 } 277 } 278 } 279 return false; 280 } 281 282 export function arraysEqual<T>(a: readonly T[], b: readonly T[], equalityComparer: EqualityComparer<T> = equateValues): boolean { 283 return a.length === b.length && a.every((x, i) => equalityComparer(x, b[i])); 284 } 285 286 export function indexOfAnyCharCode(text: string, charCodes: readonly number[], start?: number): number { 287 for (let i = start || 0; i < text.length; i++) { 288 if (contains(charCodes, text.charCodeAt(i))) { 289 return i; 290 } 291 } 292 return -1; 293 } 294 295 export function countWhere<T>(array: readonly T[], predicate: (x: T, i: number) => boolean): number { 296 let count = 0; 297 if (array) { 298 for (let i = 0; i < array.length; i++) { 299 const v = array[i]; 300 if (predicate(v, i)) { 301 count++; 302 } 303 } 304 } 305 return count; 306 } 307 308 /** 309 * Filters an array by a predicate function. Returns the same array instance if the predicate is 310 * true for all elements, otherwise returns a new array instance containing the filtered subset. 311 */ 312 export function filter<T, U extends T>(array: T[], f: (x: T) => x is U): U[]; 313 export function filter<T>(array: T[], f: (x: T) => boolean): T[]; 314 export function filter<T, U extends T>(array: readonly T[], f: (x: T) => x is U): readonly U[]; 315 export function filter<T, U extends T>(array: readonly T[], f: (x: T) => boolean): readonly T[]; 316 export function filter<T, U extends T>(array: T[] | undefined, f: (x: T) => x is U): U[] | undefined; 317 export function filter<T>(array: T[] | undefined, f: (x: T) => boolean): T[] | undefined; 318 export function filter<T, U extends T>(array: readonly T[] | undefined, f: (x: T) => x is U): readonly U[] | undefined; 319 export function filter<T, U extends T>(array: readonly T[] | undefined, f: (x: T) => boolean): readonly T[] | undefined; 320 export function filter<T>(array: readonly T[] | undefined, f: (x: T) => boolean): readonly T[] | undefined { 321 if (array) { 322 const len = array.length; 323 let i = 0; 324 while (i < len && f(array[i])) i++; 325 if (i < len) { 326 const result = array.slice(0, i); 327 i++; 328 while (i < len) { 329 const item = array[i]; 330 if (f(item)) { 331 result.push(item); 332 } 333 i++; 334 } 335 return result; 336 } 337 } 338 return array; 339 } 340 341 export function filterMutate<T>(array: T[], f: (x: T, i: number, array: T[]) => boolean): void { 342 let outIndex = 0; 343 for (let i = 0; i < array.length; i++) { 344 if (f(array[i], i, array)) { 345 array[outIndex] = array[i]; 346 outIndex++; 347 } 348 } 349 array.length = outIndex; 350 } 351 352 export function clear(array: {}[]): void { 353 array.length = 0; 354 } 355 356 export function map<T, U>(array: readonly T[], f: (x: T, i: number) => U): U[]; 357 export function map<T, U>(array: readonly T[] | undefined, f: (x: T, i: number) => U): U[] | undefined; 358 export function map<T, U>(array: readonly T[] | undefined, f: (x: T, i: number) => U): U[] | undefined { 359 let result: U[] | undefined; 360 if (array) { 361 result = []; 362 for (let i = 0; i < array.length; i++) { 363 result.push(f(array[i], i)); 364 } 365 } 366 return result; 367 } 368 369 370 export function mapIterator<T, U>(iter: Iterator<T>, mapFn: (x: T) => U): Iterator<U> { 371 return { 372 next() { 373 const iterRes = iter.next(); 374 return iterRes.done ? iterRes as { done: true, value: never } : { value: mapFn(iterRes.value), done: false }; 375 } 376 }; 377 } 378 379 // Maps from T to T and avoids allocation if all elements map to themselves 380 export function sameMap<T>(array: T[], f: (x: T, i: number) => T): T[]; 381 export function sameMap<T>(array: readonly T[], f: (x: T, i: number) => T): readonly T[]; 382 export function sameMap<T>(array: T[] | undefined, f: (x: T, i: number) => T): T[] | undefined; 383 export function sameMap<T>(array: readonly T[] | undefined, f: (x: T, i: number) => T): readonly T[] | undefined; 384 export function sameMap<T>(array: readonly T[] | undefined, f: (x: T, i: number) => T): readonly T[] | undefined { 385 if (array) { 386 for (let i = 0; i < array.length; i++) { 387 const item = array[i]; 388 const mapped = f(item, i); 389 if (item !== mapped) { 390 const result = array.slice(0, i); 391 result.push(mapped); 392 for (i++; i < array.length; i++) { 393 result.push(f(array[i], i)); 394 } 395 return result; 396 } 397 } 398 } 399 return array; 400 } 401 402 /** 403 * Flattens an array containing a mix of array or non-array elements. 404 * 405 * @param array The array to flatten. 406 */ 407 export function flatten<T>(array: T[][] | readonly (T | readonly T[] | undefined)[]): T[] { 408 const result = []; 409 for (const v of array) { 410 if (v) { 411 if (isArray(v)) { 412 addRange(result, v); 413 } 414 else { 415 result.push(v); 416 } 417 } 418 } 419 return result; 420 } 421 422 /** 423 * Maps an array. If the mapped value is an array, it is spread into the result. 424 * 425 * @param array The array to map. 426 * @param mapfn The callback used to map the result into one or more values. 427 */ 428 export function flatMap<T, U>(array: readonly T[] | undefined, mapfn: (x: T, i: number) => U | readonly U[] | undefined): readonly U[] { 429 let result: U[] | undefined; 430 if (array) { 431 for (let i = 0; i < array.length; i++) { 432 const v = mapfn(array[i], i); 433 if (v) { 434 if (isArray(v)) { 435 result = addRange(result, v); 436 } 437 else { 438 result = append(result, v); 439 } 440 } 441 } 442 } 443 return result || emptyArray; 444 } 445 446 export function flatMapToMutable<T, U>(array: readonly T[] | undefined, mapfn: (x: T, i: number) => U | readonly U[] | undefined): U[] { 447 const result: U[] = []; 448 if (array) { 449 for (let i = 0; i < array.length; i++) { 450 const v = mapfn(array[i], i); 451 if (v) { 452 if (isArray(v)) { 453 addRange(result, v); 454 } 455 else { 456 result.push(v); 457 } 458 } 459 } 460 } 461 return result; 462 } 463 464 export function flatMapIterator<T, U>(iter: Iterator<T>, mapfn: (x: T) => readonly U[] | Iterator<U> | undefined): Iterator<U> { 465 const first = iter.next(); 466 if (first.done) { 467 return emptyIterator; 468 } 469 let currentIter = getIterator(first.value); 470 return { 471 next() { 472 while (true) { 473 const currentRes = currentIter.next(); 474 if (!currentRes.done) { 475 return currentRes; 476 } 477 const iterRes = iter.next(); 478 if (iterRes.done) { 479 return iterRes as { done: true, value: never }; 480 } 481 currentIter = getIterator(iterRes.value); 482 } 483 }, 484 }; 485 486 function getIterator(x: T): Iterator<U> { 487 const res = mapfn(x); 488 return res === undefined ? emptyIterator : isArray(res) ? arrayIterator(res) : res; 489 } 490 } 491 492 /** 493 * Maps an array. If the mapped value is an array, it is spread into the result. 494 * Avoids allocation if all elements map to themselves. 495 * 496 * @param array The array to map. 497 * @param mapfn The callback used to map the result into one or more values. 498 */ 499 export function sameFlatMap<T>(array: T[], mapfn: (x: T, i: number) => T | readonly T[]): T[]; 500 export function sameFlatMap<T>(array: readonly T[], mapfn: (x: T, i: number) => T | readonly T[]): readonly T[]; 501 export function sameFlatMap<T>(array: T[], mapfn: (x: T, i: number) => T | T[]): T[] { 502 let result: T[] | undefined; 503 if (array) { 504 for (let i = 0; i < array.length; i++) { 505 const item = array[i]; 506 const mapped = mapfn(item, i); 507 if (result || item !== mapped || isArray(mapped)) { 508 if (!result) { 509 result = array.slice(0, i); 510 } 511 if (isArray(mapped)) { 512 addRange(result, mapped); 513 } 514 else { 515 result.push(mapped); 516 } 517 } 518 } 519 } 520 return result || array; 521 } 522 523 export function mapAllOrFail<T, U>(array: readonly T[], mapFn: (x: T, i: number) => U | undefined): U[] | undefined { 524 const result: U[] = []; 525 for (let i = 0; i < array.length; i++) { 526 const mapped = mapFn(array[i], i); 527 if (mapped === undefined) { 528 return undefined; 529 } 530 result.push(mapped); 531 } 532 return result; 533 } 534 535 export function mapDefined<T, U>(array: readonly T[] | undefined, mapFn: (x: T, i: number) => U | undefined): U[] { 536 const result: U[] = []; 537 if (array) { 538 for (let i = 0; i < array.length; i++) { 539 const mapped = mapFn(array[i], i); 540 if (mapped !== undefined) { 541 result.push(mapped); 542 } 543 } 544 } 545 return result; 546 } 547 548 export function mapDefinedIterator<T, U>(iter: Iterator<T>, mapFn: (x: T) => U | undefined): Iterator<U> { 549 return { 550 next() { 551 while (true) { 552 const res = iter.next(); 553 if (res.done) { 554 return res as { done: true, value: never }; 555 } 556 const value = mapFn(res.value); 557 if (value !== undefined) { 558 return { value, done: false }; 559 } 560 } 561 } 562 }; 563 } 564 565 export function mapDefinedEntries<K1, V1, K2, V2>(map: ReadonlyESMap<K1, V1>, f: (key: K1, value: V1) => readonly [K2, V2] | undefined): ESMap<K2, V2>; 566 export function mapDefinedEntries<K1, V1, K2, V2>(map: ReadonlyESMap<K1, V1> | undefined, f: (key: K1, value: V1) => readonly [K2 | undefined, V2 | undefined] | undefined): ESMap<K2, V2> | undefined; 567 export function mapDefinedEntries<K1, V1, K2, V2>(map: ReadonlyESMap<K1, V1> | undefined, f: (key: K1, value: V1) => readonly [K2 | undefined, V2 | undefined] | undefined): ESMap<K2, V2> | undefined { 568 if (!map) { 569 return undefined; 570 } 571 572 const result = new Map<K2, V2>(); 573 map.forEach((value, key) => { 574 const entry = f(key, value); 575 if (entry !== undefined) { 576 const [newKey, newValue] = entry; 577 if (newKey !== undefined && newValue !== undefined) { 578 result.set(newKey, newValue); 579 } 580 } 581 }); 582 583 return result; 584 } 585 586 export function mapDefinedValues<V1, V2>(set: ReadonlySet<V1>, f: (value: V1) => V2 | undefined): Set<V2>; 587 export function mapDefinedValues<V1, V2>(set: ReadonlySet<V1> | undefined, f: (value: V1) => V2 | undefined): Set<V2> | undefined; 588 export function mapDefinedValues<V1, V2>(set: ReadonlySet<V1> | undefined, f: (value: V1) => V2 | undefined): Set<V2> | undefined { 589 if (set) { 590 const result = new Set<V2>(); 591 set.forEach(value => { 592 const newValue = f(value); 593 if (newValue !== undefined) { 594 result.add(newValue); 595 } 596 }); 597 return result; 598 } 599 } 600 601 export function getOrUpdate<K, V>(map: ESMap<K, V>, key: K, callback: () => V) { 602 if (map.has(key)) { 603 return map.get(key)!; 604 } 605 const value = callback(); 606 map.set(key, value); 607 return value; 608 } 609 610 export function tryAddToSet<T>(set: Set<T>, value: T) { 611 if (!set.has(value)) { 612 set.add(value); 613 return true; 614 } 615 return false; 616 } 617 618 export const emptyIterator: Iterator<never> = { next: () => ({ value: undefined as never, done: true }) }; 619 620 export function singleIterator<T>(value: T): Iterator<T> { 621 let done = false; 622 return { 623 next() { 624 const wasDone = done; 625 done = true; 626 return wasDone ? { value: undefined as never, done: true } : { value, done: false }; 627 } 628 }; 629 } 630 631 /** 632 * Maps contiguous spans of values with the same key. 633 * 634 * @param array The array to map. 635 * @param keyfn A callback used to select the key for an element. 636 * @param mapfn A callback used to map a contiguous chunk of values to a single value. 637 */ 638 export function spanMap<T, K, U>(array: readonly T[], keyfn: (x: T, i: number) => K, mapfn: (chunk: T[], key: K, start: number, end: number) => U): U[]; 639 export function spanMap<T, K, U>(array: readonly T[] | undefined, keyfn: (x: T, i: number) => K, mapfn: (chunk: T[], key: K, start: number, end: number) => U): U[] | undefined; 640 export function spanMap<T, K, U>(array: readonly T[] | undefined, keyfn: (x: T, i: number) => K, mapfn: (chunk: T[], key: K, start: number, end: number) => U): U[] | undefined { 641 let result: U[] | undefined; 642 if (array) { 643 result = []; 644 const len = array.length; 645 let previousKey: K | undefined; 646 let key: K | undefined; 647 let start = 0; 648 let pos = 0; 649 while (start < len) { 650 while (pos < len) { 651 const value = array[pos]; 652 key = keyfn(value, pos); 653 if (pos === 0) { 654 previousKey = key; 655 } 656 else if (key !== previousKey) { 657 break; 658 } 659 660 pos++; 661 } 662 663 if (start < pos) { 664 const v = mapfn(array.slice(start, pos), previousKey!, start, pos); 665 if (v) { 666 result.push(v); 667 } 668 669 start = pos; 670 } 671 672 previousKey = key; 673 pos++; 674 } 675 } 676 677 return result; 678 } 679 680 export function mapEntries<K1, V1, K2, V2>(map: ReadonlyESMap<K1, V1>, f: (key: K1, value: V1) => readonly [K2, V2]): ESMap<K2, V2>; 681 export function mapEntries<K1, V1, K2, V2>(map: ReadonlyESMap<K1, V1> | undefined, f: (key: K1, value: V1) => readonly [K2, V2]): ESMap<K2, V2> | undefined; 682 export function mapEntries<K1, V1, K2, V2>(map: ReadonlyESMap<K1, V1> | undefined, f: (key: K1, value: V1) => readonly [K2, V2]): ESMap<K2, V2> | undefined { 683 if (!map) { 684 return undefined; 685 } 686 687 const result = new Map<K2, V2>(); 688 map.forEach((value, key) => { 689 const [newKey, newValue] = f(key, value); 690 result.set(newKey, newValue); 691 }); 692 return result; 693 } 694 695 export function some<T>(array: readonly T[] | undefined): array is readonly T[]; 696 export function some<T>(array: readonly T[] | undefined, predicate: (value: T) => boolean): boolean; 697 export function some<T>(array: readonly T[] | undefined, predicate?: (value: T) => boolean): boolean { 698 if (array) { 699 if (predicate) { 700 for (const v of array) { 701 if (predicate(v)) { 702 return true; 703 } 704 } 705 } 706 else { 707 return array.length > 0; 708 } 709 } 710 return false; 711 } 712 713 /** Calls the callback with (start, afterEnd) index pairs for each range where 'pred' is true. */ 714 export function getRangesWhere<T>(arr: readonly T[], pred: (t: T) => boolean, cb: (start: number, afterEnd: number) => void): void { 715 let start: number | undefined; 716 for (let i = 0; i < arr.length; i++) { 717 if (pred(arr[i])) { 718 start = start === undefined ? i : start; 719 } 720 else { 721 if (start !== undefined) { 722 cb(start, i); 723 start = undefined; 724 } 725 } 726 } 727 if (start !== undefined) cb(start, arr.length); 728 } 729 730 export function concatenate<T>(array1: T[], array2: T[]): T[]; 731 export function concatenate<T>(array1: readonly T[], array2: readonly T[]): readonly T[]; 732 export function concatenate<T>(array1: T[] | undefined, array2: T[] | undefined): T[]; 733 export function concatenate<T>(array1: readonly T[] | undefined, array2: readonly T[] | undefined): readonly T[]; 734 export function concatenate<T>(array1: T[], array2: T[]): T[] { 735 if (!some(array2)) return array1; 736 if (!some(array1)) return array2; 737 return [...array1, ...array2]; 738 } 739 740 function selectIndex(_: unknown, i: number) { 741 return i; 742 } 743 744 export function indicesOf(array: readonly unknown[]): number[] { 745 return array.map(selectIndex); 746 } 747 748 function deduplicateRelational<T>(array: readonly T[], equalityComparer: EqualityComparer<T>, comparer: Comparer<T>) { 749 // Perform a stable sort of the array. This ensures the first entry in a list of 750 // duplicates remains the first entry in the result. 751 const indices = indicesOf(array); 752 stableSortIndices(array, indices, comparer); 753 754 let last = array[indices[0]]; 755 const deduplicated: number[] = [indices[0]]; 756 for (let i = 1; i < indices.length; i++) { 757 const index = indices[i]; 758 const item = array[index]; 759 if (!equalityComparer(last, item)) { 760 deduplicated.push(index); 761 last = item; 762 } 763 } 764 765 // restore original order 766 deduplicated.sort(); 767 return deduplicated.map(i => array[i]); 768 } 769 770 function deduplicateEquality<T>(array: readonly T[], equalityComparer: EqualityComparer<T>) { 771 const result: T[] = []; 772 for (const item of array) { 773 pushIfUnique(result, item, equalityComparer); 774 } 775 return result; 776 } 777 778 /** 779 * Deduplicates an unsorted array. 780 * @param equalityComparer An `EqualityComparer` used to determine if two values are duplicates. 781 * @param comparer An optional `Comparer` used to sort entries before comparison, though the 782 * result will remain in the original order in `array`. 783 */ 784 export function deduplicate<T>(array: readonly T[], equalityComparer: EqualityComparer<T>, comparer?: Comparer<T>): T[] { 785 return array.length === 0 ? [] : 786 array.length === 1 ? array.slice() : 787 comparer ? deduplicateRelational(array, equalityComparer, comparer) : 788 deduplicateEquality(array, equalityComparer); 789 } 790 791 /** 792 * Deduplicates an array that has already been sorted. 793 */ 794 function deduplicateSorted<T>(array: SortedReadonlyArray<T>, comparer: EqualityComparer<T> | Comparer<T>): SortedReadonlyArray<T> { 795 if (array.length === 0) return emptyArray as any as SortedReadonlyArray<T>; 796 797 let last = array[0]; 798 const deduplicated: T[] = [last]; 799 for (let i = 1; i < array.length; i++) { 800 const next = array[i]; 801 switch (comparer(next, last)) { 802 // equality comparison 803 case true: 804 805 // relational comparison 806 // falls through 807 case Comparison.EqualTo: 808 continue; 809 810 case Comparison.LessThan: 811 // If `array` is sorted, `next` should **never** be less than `last`. 812 return Debug.fail("Array is unsorted."); 813 } 814 815 deduplicated.push(last = next); 816 } 817 818 return deduplicated as any as SortedReadonlyArray<T>; 819 } 820 821 export function insertSorted<T>(array: SortedArray<T>, insert: T, compare: Comparer<T>): void { 822 if (array.length === 0) { 823 array.push(insert); 824 return; 825 } 826 827 const insertIndex = binarySearch(array, insert, identity, compare); 828 if (insertIndex < 0) { 829 array.splice(~insertIndex, 0, insert); 830 } 831 } 832 833 export function sortAndDeduplicate<T>(array: readonly string[]): SortedReadonlyArray<string>; 834 export function sortAndDeduplicate<T>(array: readonly T[], comparer: Comparer<T>, equalityComparer?: EqualityComparer<T>): SortedReadonlyArray<T>; 835 export function sortAndDeduplicate<T>(array: readonly T[], comparer?: Comparer<T>, equalityComparer?: EqualityComparer<T>): SortedReadonlyArray<T> { 836 return deduplicateSorted(sort(array, comparer), equalityComparer || comparer || compareStringsCaseSensitive as any as Comparer<T>); 837 } 838 839 export function arrayIsSorted<T>(array: readonly T[], comparer: Comparer<T>) { 840 if (array.length < 2) return true; 841 let prevElement = array[0]; 842 for (const element of array.slice(1)) { 843 if (comparer(prevElement, element) === Comparison.GreaterThan) { 844 return false; 845 } 846 prevElement = element; 847 } 848 return true; 849 } 850 851 export function arrayIsEqualTo<T>(array1: readonly T[] | undefined, array2: readonly T[] | undefined, equalityComparer: (a: T, b: T, index: number) => boolean = equateValues): boolean { 852 if (!array1 || !array2) { 853 return array1 === array2; 854 } 855 856 if (array1.length !== array2.length) { 857 return false; 858 } 859 860 for (let i = 0; i < array1.length; i++) { 861 if (!equalityComparer(array1[i], array2[i], i)) { 862 return false; 863 } 864 } 865 866 return true; 867 } 868 869 /** 870 * Compacts an array, removing any falsey elements. 871 */ 872 export function compact<T>(array: (T | undefined | null | false | 0 | "")[]): T[]; 873 export function compact<T>(array: readonly (T | undefined | null | false | 0 | "")[]): readonly T[]; 874 // ESLint thinks these can be combined with the above - they cannot; they'd produce higher-priority inferences and prevent the falsey types from being stripped 875 export function compact<T>(array: T[]): T[]; // eslint-disable-line @typescript-eslint/unified-signatures 876 export function compact<T>(array: readonly T[]): readonly T[]; // eslint-disable-line @typescript-eslint/unified-signatures 877 export function compact<T>(array: T[]): T[] { 878 let result: T[] | undefined; 879 if (array) { 880 for (let i = 0; i < array.length; i++) { 881 const v = array[i]; 882 if (result || !v) { 883 if (!result) { 884 result = array.slice(0, i); 885 } 886 if (v) { 887 result.push(v); 888 } 889 } 890 } 891 } 892 return result || array; 893 } 894 895 /** 896 * Gets the relative complement of `arrayA` with respect to `arrayB`, returning the elements that 897 * are not present in `arrayA` but are present in `arrayB`. Assumes both arrays are sorted 898 * based on the provided comparer. 899 */ 900 export function relativeComplement<T>(arrayA: T[] | undefined, arrayB: T[] | undefined, comparer: Comparer<T>): T[] | undefined { 901 if (!arrayB || !arrayA || arrayB.length === 0 || arrayA.length === 0) return arrayB; 902 const result: T[] = []; 903 loopB: for (let offsetA = 0, offsetB = 0; offsetB < arrayB.length; offsetB++) { 904 if (offsetB > 0) { 905 // Ensure `arrayB` is properly sorted. 906 Debug.assertGreaterThanOrEqual(comparer(arrayB[offsetB], arrayB[offsetB - 1]), Comparison.EqualTo); 907 } 908 909 loopA: for (const startA = offsetA; offsetA < arrayA.length; offsetA++) { 910 if (offsetA > startA) { 911 // Ensure `arrayA` is properly sorted. We only need to perform this check if 912 // `offsetA` has changed since we entered the loop. 913 Debug.assertGreaterThanOrEqual(comparer(arrayA[offsetA], arrayA[offsetA - 1]), Comparison.EqualTo); 914 } 915 916 switch (comparer(arrayB[offsetB], arrayA[offsetA])) { 917 case Comparison.LessThan: 918 // If B is less than A, B does not exist in arrayA. Add B to the result and 919 // move to the next element in arrayB without changing the current position 920 // in arrayA. 921 result.push(arrayB[offsetB]); 922 continue loopB; 923 case Comparison.EqualTo: 924 // If B is equal to A, B exists in arrayA. Move to the next element in 925 // arrayB without adding B to the result or changing the current position 926 // in arrayA. 927 continue loopB; 928 case Comparison.GreaterThan: 929 // If B is greater than A, we need to keep looking for B in arrayA. Move to 930 // the next element in arrayA and recheck. 931 continue loopA; 932 } 933 } 934 } 935 return result; 936 } 937 938 export function sum<T extends Record<K, number>, K extends string>(array: readonly T[], prop: K): number { 939 let result = 0; 940 for (const v of array) { 941 result += v[prop]; 942 } 943 return result; 944 } 945 946 /** 947 * Appends a value to an array, returning the array. 948 * 949 * @param to The array to which `value` is to be appended. If `to` is `undefined`, a new array 950 * is created if `value` was appended. 951 * @param value The value to append to the array. If `value` is `undefined`, nothing is 952 * appended. 953 */ 954 export function append<TArray extends any[] | undefined, TValue extends NonNullable<TArray>[number] | undefined>(to: TArray, value: TValue): [undefined, undefined] extends [TArray, TValue] ? TArray : NonNullable<TArray>[number][]; 955 export function append<T>(to: T[], value: T | undefined): T[]; 956 export function append<T>(to: T[] | undefined, value: T): T[]; 957 export function append<T>(to: T[] | undefined, value: T | undefined): T[] | undefined; 958 export function append<T>(to: Push<T>, value: T | undefined): void; 959 export function append<T>(to: T[], value: T | undefined): T[] | undefined { 960 if (value === undefined) return to; 961 if (to === undefined) return [value]; 962 to.push(value); 963 return to; 964 } 965 966 /** 967 * Combines two arrays, values, or undefineds into the smallest container that can accommodate the resulting set: 968 * 969 * ``` 970 * undefined -> undefined -> undefined 971 * T -> undefined -> T 972 * T -> T -> T[] 973 * T[] -> undefined -> T[] (no-op) 974 * T[] -> T -> T[] (append) 975 * T[] -> T[] -> T[] (concatenate) 976 * ``` 977 */ 978 export function combine<T>(xs: T | readonly T[] | undefined, ys: T | readonly T[] | undefined): T | readonly T[] | undefined; 979 export function combine<T>(xs: T | T[] | undefined, ys: T | T[] | undefined): T | T[] | undefined; 980 export function combine<T>(xs: T | T[] | undefined, ys: T | T[] | undefined) { 981 if (xs === undefined) return ys; 982 if (ys === undefined) return xs; 983 if (isArray(xs)) return isArray(ys) ? concatenate(xs, ys) : append(xs, ys); 984 if (isArray(ys)) return append(ys, xs); 985 return [xs, ys]; 986 } 987 988 /** 989 * Gets the actual offset into an array for a relative offset. Negative offsets indicate a 990 * position offset from the end of the array. 991 */ 992 function toOffset(array: readonly any[], offset: number) { 993 return offset < 0 ? array.length + offset : offset; 994 } 995 996 /** 997 * Appends a range of value to an array, returning the array. 998 * 999 * @param to The array to which `value` is to be appended. If `to` is `undefined`, a new array 1000 * is created if `value` was appended. 1001 * @param from The values to append to the array. If `from` is `undefined`, nothing is 1002 * appended. If an element of `from` is `undefined`, that element is not appended. 1003 * @param start The offset in `from` at which to start copying values. 1004 * @param end The offset in `from` at which to stop copying values (non-inclusive). 1005 */ 1006 export function addRange<T>(to: T[], from: readonly T[] | undefined, start?: number, end?: number): T[]; 1007 export function addRange<T>(to: T[] | undefined, from: readonly T[] | undefined, start?: number, end?: number): T[] | undefined; 1008 export function addRange<T>(to: T[] | undefined, from: readonly T[] | undefined, start?: number, end?: number): T[] | undefined { 1009 if (from === undefined || from.length === 0) return to; 1010 if (to === undefined) return from.slice(start, end); 1011 start = start === undefined ? 0 : toOffset(from, start); 1012 end = end === undefined ? from.length : toOffset(from, end); 1013 for (let i = start; i < end && i < from.length; i++) { 1014 if (from[i] !== undefined) { 1015 to.push(from[i]); 1016 } 1017 } 1018 return to; 1019 } 1020 1021 /** 1022 * @return Whether the value was added. 1023 */ 1024 export function pushIfUnique<T>(array: T[], toAdd: T, equalityComparer?: EqualityComparer<T>): boolean { 1025 if (contains(array, toAdd, equalityComparer)) { 1026 return false; 1027 } 1028 else { 1029 array.push(toAdd); 1030 return true; 1031 } 1032 } 1033 1034 /** 1035 * Unlike `pushIfUnique`, this can take `undefined` as an input, and returns a new array. 1036 */ 1037 export function appendIfUnique<T>(array: T[] | undefined, toAdd: T, equalityComparer?: EqualityComparer<T>): T[] { 1038 if (array) { 1039 pushIfUnique(array, toAdd, equalityComparer); 1040 return array; 1041 } 1042 else { 1043 return [toAdd]; 1044 } 1045 } 1046 1047 function stableSortIndices<T>(array: readonly T[], indices: number[], comparer: Comparer<T>) { 1048 // sort indices by value then position 1049 indices.sort((x, y) => comparer(array[x], array[y]) || compareValues(x, y)); 1050 } 1051 1052 /** 1053 * Returns a new sorted array. 1054 */ 1055 export function sort<T>(array: readonly T[], comparer?: Comparer<T>): SortedReadonlyArray<T> { 1056 return (array.length === 0 ? array : array.slice().sort(comparer)) as SortedReadonlyArray<T>; 1057 } 1058 1059 export function arrayIterator<T>(array: readonly T[]): Iterator<T> { 1060 let i = 0; 1061 return { next: () => { 1062 if (i === array.length) { 1063 return { value: undefined as never, done: true }; 1064 } 1065 else { 1066 i++; 1067 return { value: array[i - 1], done: false }; 1068 } 1069 }}; 1070 } 1071 1072 export function arrayReverseIterator<T>(array: readonly T[]): Iterator<T> { 1073 let i = array.length; 1074 return { 1075 next: () => { 1076 if (i === 0) { 1077 return { value: undefined as never, done: true }; 1078 } 1079 else { 1080 i--; 1081 return { value: array[i], done: false }; 1082 } 1083 } 1084 }; 1085 } 1086 1087 /** 1088 * Stable sort of an array. Elements equal to each other maintain their relative position in the array. 1089 */ 1090 export function stableSort<T>(array: readonly T[], comparer: Comparer<T>): SortedReadonlyArray<T> { 1091 const indices = indicesOf(array); 1092 stableSortIndices(array, indices, comparer); 1093 return indices.map(i => array[i]) as SortedArray<T> as SortedReadonlyArray<T>; 1094 } 1095 1096 export function rangeEquals<T>(array1: readonly T[], array2: readonly T[], pos: number, end: number) { 1097 while (pos < end) { 1098 if (array1[pos] !== array2[pos]) { 1099 return false; 1100 } 1101 pos++; 1102 } 1103 return true; 1104 } 1105 1106 /** 1107 * Returns the element at a specific offset in an array if non-empty, `undefined` otherwise. 1108 * A negative offset indicates the element should be retrieved from the end of the array. 1109 */ 1110 export function elementAt<T>(array: readonly T[] | undefined, offset: number): T | undefined { 1111 if (array) { 1112 offset = toOffset(array, offset); 1113 if (offset < array.length) { 1114 return array[offset]; 1115 } 1116 } 1117 return undefined; 1118 } 1119 1120 /** 1121 * Returns the first element of an array if non-empty, `undefined` otherwise. 1122 */ 1123 export function firstOrUndefined<T>(array: readonly T[]): T | undefined { 1124 return array.length === 0 ? undefined : array[0]; 1125 } 1126 1127 export function first<T>(array: readonly T[]): T { 1128 Debug.assert(array.length !== 0); 1129 return array[0]; 1130 } 1131 1132 /** 1133 * Returns the last element of an array if non-empty, `undefined` otherwise. 1134 */ 1135 export function lastOrUndefined<T>(array: readonly T[]): T | undefined { 1136 return array.length === 0 ? undefined : array[array.length - 1]; 1137 } 1138 1139 export function last<T>(array: readonly T[]): T { 1140 Debug.assert(array.length !== 0); 1141 return array[array.length - 1]; 1142 } 1143 1144 /** 1145 * Returns the only element of an array if it contains only one element, `undefined` otherwise. 1146 */ 1147 export function singleOrUndefined<T>(array: readonly T[] | undefined): T | undefined { 1148 return array && array.length === 1 1149 ? array[0] 1150 : undefined; 1151 } 1152 1153 /** 1154 * Returns the only element of an array if it contains only one element; otherwise, returns the 1155 * array. 1156 */ 1157 export function singleOrMany<T>(array: T[]): T | T[]; 1158 export function singleOrMany<T>(array: readonly T[]): T | readonly T[]; 1159 export function singleOrMany<T>(array: T[] | undefined): T | T[] | undefined; 1160 export function singleOrMany<T>(array: readonly T[] | undefined): T | readonly T[] | undefined; 1161 export function singleOrMany<T>(array: readonly T[] | undefined): T | readonly T[] | undefined { 1162 return array && array.length === 1 1163 ? array[0] 1164 : array; 1165 } 1166 1167 export function replaceElement<T>(array: readonly T[], index: number, value: T): T[] { 1168 const result = array.slice(0); 1169 result[index] = value; 1170 return result; 1171 } 1172 1173 /** 1174 * Performs a binary search, finding the index at which `value` occurs in `array`. 1175 * If no such index is found, returns the 2's-complement of first index at which 1176 * `array[index]` exceeds `value`. 1177 * @param array A sorted array whose first element must be no larger than number 1178 * @param value The value to be searched for in the array. 1179 * @param keySelector A callback used to select the search key from `value` and each element of 1180 * `array`. 1181 * @param keyComparer A callback used to compare two keys in a sorted array. 1182 * @param offset An offset into `array` at which to start the search. 1183 */ 1184 export function binarySearch<T, U>(array: readonly T[], value: T, keySelector: (v: T) => U, keyComparer: Comparer<U>, offset?: number): number { 1185 return binarySearchKey(array, keySelector(value), keySelector, keyComparer, offset); 1186 } 1187 1188 /** 1189 * Performs a binary search, finding the index at which an object with `key` occurs in `array`. 1190 * If no such index is found, returns the 2's-complement of first index at which 1191 * `array[index]` exceeds `key`. 1192 * @param array A sorted array whose first element must be no larger than number 1193 * @param key The key to be searched for in the array. 1194 * @param keySelector A callback used to select the search key from each element of `array`. 1195 * @param keyComparer A callback used to compare two keys in a sorted array. 1196 * @param offset An offset into `array` at which to start the search. 1197 */ 1198 export function binarySearchKey<T, U>(array: readonly T[], key: U, keySelector: (v: T, i: number) => U, keyComparer: Comparer<U>, offset?: number): number { 1199 if (!some(array)) { 1200 return -1; 1201 } 1202 1203 let low = offset || 0; 1204 let high = array.length - 1; 1205 while (low <= high) { 1206 const middle = low + ((high - low) >> 1); 1207 const midKey = keySelector(array[middle], middle); 1208 switch (keyComparer(midKey, key)) { 1209 case Comparison.LessThan: 1210 low = middle + 1; 1211 break; 1212 case Comparison.EqualTo: 1213 return middle; 1214 case Comparison.GreaterThan: 1215 high = middle - 1; 1216 break; 1217 } 1218 } 1219 1220 return ~low; 1221 } 1222 1223 export function reduceLeft<T, U>(array: readonly T[] | undefined, f: (memo: U, value: T, i: number) => U, initial: U, start?: number, count?: number): U; 1224 export function reduceLeft<T>(array: readonly T[], f: (memo: T, value: T, i: number) => T): T | undefined; 1225 export function reduceLeft<T>(array: T[], f: (memo: T, value: T, i: number) => T, initial?: T, start?: number, count?: number): T | undefined { 1226 if (array && array.length > 0) { 1227 const size = array.length; 1228 if (size > 0) { 1229 let pos = start === undefined || start < 0 ? 0 : start; 1230 const end = count === undefined || pos + count > size - 1 ? size - 1 : pos + count; 1231 let result: T; 1232 if (arguments.length <= 2) { 1233 result = array[pos]; 1234 pos++; 1235 } 1236 else { 1237 result = initial!; 1238 } 1239 while (pos <= end) { 1240 result = f(result, array[pos], pos); 1241 pos++; 1242 } 1243 return result; 1244 } 1245 } 1246 return initial; 1247 } 1248 1249 const hasOwnProperty = Object.prototype.hasOwnProperty; 1250 1251 /** 1252 * Indicates whether a map-like contains an own property with the specified key. 1253 * 1254 * @param map A map-like. 1255 * @param key A property key. 1256 */ 1257 export function hasProperty(map: MapLike<any>, key: string): boolean { 1258 return hasOwnProperty.call(map, key); 1259 } 1260 1261 /** 1262 * Gets the value of an owned property in a map-like. 1263 * 1264 * @param map A map-like. 1265 * @param key A property key. 1266 */ 1267 export function getProperty<T>(map: MapLike<T>, key: string): T | undefined { 1268 return hasOwnProperty.call(map, key) ? map[key] : undefined; 1269 } 1270 1271 /** 1272 * Gets the owned, enumerable property keys of a map-like. 1273 */ 1274 export function getOwnKeys<T>(map: MapLike<T>): string[] { 1275 const keys: string[] = []; 1276 for (const key in map) { 1277 if (hasOwnProperty.call(map, key)) { 1278 keys.push(key); 1279 } 1280 } 1281 1282 return keys; 1283 } 1284 1285 export function getAllKeys(obj: object): string[] { 1286 const result: string[] = []; 1287 do { 1288 const names = Object.getOwnPropertyNames(obj); 1289 for (const name of names) { 1290 pushIfUnique(result, name); 1291 } 1292 } while (obj = Object.getPrototypeOf(obj)); 1293 return result; 1294 } 1295 1296 export function getOwnValues<T>(sparseArray: T[]): T[] { 1297 const values: T[] = []; 1298 for (const key in sparseArray) { 1299 if (hasOwnProperty.call(sparseArray, key)) { 1300 values.push(sparseArray[key]); 1301 } 1302 } 1303 1304 return values; 1305 } 1306 1307 const _entries = Object.entries || (<T>(obj: MapLike<T>) => { 1308 const keys = getOwnKeys(obj); 1309 const result: [string, T][] = Array(keys.length); 1310 for (let i = 0; i < keys.length; i++) { 1311 result[i] = [keys[i], obj[keys[i]]]; 1312 } 1313 return result; 1314 }); 1315 1316 export function getEntries<T>(obj: MapLike<T>): [string, T][] { 1317 return obj ? _entries(obj) : []; 1318 } 1319 1320 export function arrayOf<T>(count: number, f: (index: number) => T): T[] { 1321 const result = new Array(count); 1322 for (let i = 0; i < count; i++) { 1323 result[i] = f(i); 1324 } 1325 return result; 1326 } 1327 1328 /** Shims `Array.from`. */ 1329 export function arrayFrom<T, U>(iterator: Iterator<T> | IterableIterator<T>, map: (t: T) => U): U[]; 1330 export function arrayFrom<T>(iterator: Iterator<T> | IterableIterator<T>): T[]; 1331 export function arrayFrom<T, U>(iterator: Iterator<T> | IterableIterator<T>, map?: (t: T) => U): (T | U)[] { 1332 const result: (T | U)[] = []; 1333 for (let iterResult = iterator.next(); !iterResult.done; iterResult = iterator.next()) { 1334 result.push(map ? map(iterResult.value) : iterResult.value); 1335 } 1336 return result; 1337 } 1338 1339 1340 export function assign<T extends object>(t: T, ...args: (T | undefined)[]) { 1341 for (const arg of args) { 1342 if (arg === undefined) continue; 1343 for (const p in arg) { 1344 if (hasProperty(arg, p)) { 1345 t[p] = arg[p]; 1346 } 1347 } 1348 } 1349 return t; 1350 } 1351 1352 /** 1353 * Performs a shallow equality comparison of the contents of two map-likes. 1354 * 1355 * @param left A map-like whose properties should be compared. 1356 * @param right A map-like whose properties should be compared. 1357 */ 1358 export function equalOwnProperties<T>(left: MapLike<T> | undefined, right: MapLike<T> | undefined, equalityComparer: EqualityComparer<T> = equateValues) { 1359 if (left === right) return true; 1360 if (!left || !right) return false; 1361 for (const key in left) { 1362 if (hasOwnProperty.call(left, key)) { 1363 if (!hasOwnProperty.call(right, key)) return false; 1364 if (!equalityComparer(left[key], right[key])) return false; 1365 } 1366 } 1367 1368 for (const key in right) { 1369 if (hasOwnProperty.call(right, key)) { 1370 if (!hasOwnProperty.call(left, key)) return false; 1371 } 1372 } 1373 1374 return true; 1375 } 1376 1377 /** 1378 * Creates a map from the elements of an array. 1379 * 1380 * @param array the array of input elements. 1381 * @param makeKey a function that produces a key for a given element. 1382 * 1383 * This function makes no effort to avoid collisions; if any two elements produce 1384 * the same key with the given 'makeKey' function, then the element with the higher 1385 * index in the array will be the one associated with the produced key. 1386 */ 1387 export function arrayToMap<K, V>(array: readonly V[], makeKey: (value: V) => K | undefined): ESMap<K, V>; 1388 export function arrayToMap<K, V1, V2>(array: readonly V1[], makeKey: (value: V1) => K | undefined, makeValue: (value: V1) => V2): ESMap<K, V2>; 1389 export function arrayToMap<T>(array: readonly T[], makeKey: (value: T) => string | undefined): ESMap<string, T>; 1390 export function arrayToMap<T, U>(array: readonly T[], makeKey: (value: T) => string | undefined, makeValue: (value: T) => U): ESMap<string, U>; 1391 export function arrayToMap<K, V1, V2>(array: readonly V1[], makeKey: (value: V1) => K | undefined, makeValue: (value: V1) => V1 | V2 = identity): ESMap<K, V1 | V2> { 1392 const result = new Map<K, V1 | V2>(); 1393 for (const value of array) { 1394 const key = makeKey(value); 1395 if (key !== undefined) result.set(key, makeValue(value)); 1396 } 1397 return result; 1398 } 1399 1400 export function arrayToNumericMap<T>(array: readonly T[], makeKey: (value: T) => number): T[]; 1401 export function arrayToNumericMap<T, U>(array: readonly T[], makeKey: (value: T) => number, makeValue: (value: T) => U): U[]; 1402 export function arrayToNumericMap<T, U>(array: readonly T[], makeKey: (value: T) => number, makeValue: (value: T) => T | U = identity): (T | U)[] { 1403 const result: (T | U)[] = []; 1404 for (const value of array) { 1405 result[makeKey(value)] = makeValue(value); 1406 } 1407 return result; 1408 } 1409 1410 export function arrayToMultiMap<K, V>(values: readonly V[], makeKey: (value: V) => K): MultiMap<K, V>; 1411 export function arrayToMultiMap<K, V, U>(values: readonly V[], makeKey: (value: V) => K, makeValue: (value: V) => U): MultiMap<K, U>; 1412 export function arrayToMultiMap<K, V, U>(values: readonly V[], makeKey: (value: V) => K, makeValue: (value: V) => V | U = identity): MultiMap<K, V | U> { 1413 const result = createMultiMap<K, V | U>(); 1414 for (const value of values) { 1415 result.add(makeKey(value), makeValue(value)); 1416 } 1417 return result; 1418 } 1419 1420 export function group<T, K>(values: readonly T[], getGroupId: (value: T) => K): readonly (readonly T[])[]; 1421 export function group<T, K, R>(values: readonly T[], getGroupId: (value: T) => K, resultSelector: (values: readonly T[]) => R): R[]; 1422 export function group<T>(values: readonly T[], getGroupId: (value: T) => string): readonly (readonly T[])[]; 1423 export function group<T, R>(values: readonly T[], getGroupId: (value: T) => string, resultSelector: (values: readonly T[]) => R): R[]; 1424 export function group<T, K>(values: readonly T[], getGroupId: (value: T) => K, resultSelector: (values: readonly T[]) => readonly T[] = identity): readonly (readonly T[])[] { 1425 return arrayFrom(arrayToMultiMap(values, getGroupId).values(), resultSelector); 1426 } 1427 1428 export function clone<T>(object: T): T { 1429 const result: any = {}; 1430 for (const id in object) { 1431 if (hasOwnProperty.call(object, id)) { 1432 result[id] = (<any>object)[id]; 1433 } 1434 } 1435 return result; 1436 } 1437 1438 /** 1439 * Creates a new object by adding the own properties of `second`, then the own properties of `first`. 1440 * 1441 * NOTE: This means that if a property exists in both `first` and `second`, the property in `first` will be chosen. 1442 */ 1443 export function extend<T1, T2>(first: T1, second: T2): T1 & T2 { 1444 const result: T1 & T2 = <any>{}; 1445 for (const id in second) { 1446 if (hasOwnProperty.call(second, id)) { 1447 (result as any)[id] = (second as any)[id]; 1448 } 1449 } 1450 1451 for (const id in first) { 1452 if (hasOwnProperty.call(first, id)) { 1453 (result as any)[id] = (first as any)[id]; 1454 } 1455 } 1456 1457 return result; 1458 } 1459 1460 export function copyProperties<T1 extends T2, T2>(first: T1, second: T2) { 1461 for (const id in second) { 1462 if (hasOwnProperty.call(second, id)) { 1463 (first as any)[id] = second[id]; 1464 } 1465 } 1466 } 1467 1468 export function maybeBind<T, A extends any[], R>(obj: T, fn: ((this: T, ...args: A) => R) | undefined): ((...args: A) => R) | undefined { 1469 return fn ? fn.bind(obj) : undefined; 1470 } 1471 1472 export interface MultiMap<K, V> extends ESMap<K, V[]> { 1473 /** 1474 * Adds the value to an array of values associated with the key, and returns the array. 1475 * Creates the array if it does not already exist. 1476 */ 1477 add(key: K, value: V): V[]; 1478 /** 1479 * Removes a value from an array of values associated with the key. 1480 * Does not preserve the order of those values. 1481 * Does nothing if `key` is not in `map`, or `value` is not in `map[key]`. 1482 */ 1483 remove(key: K, value: V): void; 1484 } 1485 1486 export function createMultiMap<K, V>(): MultiMap<K, V>; 1487 export function createMultiMap<V>(): MultiMap<string, V>; 1488 export function createMultiMap<K, V>(): MultiMap<K, V> { 1489 const map = new Map<K, V[]>() as MultiMap<K, V>; 1490 map.add = multiMapAdd; 1491 map.remove = multiMapRemove; 1492 return map; 1493 } 1494 function multiMapAdd<K, V>(this: MultiMap<K, V>, key: K, value: V) { 1495 let values = this.get(key); 1496 if (values) { 1497 values.push(value); 1498 } 1499 else { 1500 this.set(key, values = [value]); 1501 } 1502 return values; 1503 } 1504 function multiMapRemove<K, V>(this: MultiMap<K, V>, key: K, value: V) { 1505 const values = this.get(key); 1506 if (values) { 1507 unorderedRemoveItem(values, value); 1508 if (!values.length) { 1509 this.delete(key); 1510 } 1511 } 1512 } 1513 1514 export interface UnderscoreEscapedMultiMap<T> extends UnderscoreEscapedMap<T[]> { 1515 /** 1516 * Adds the value to an array of values associated with the key, and returns the array. 1517 * Creates the array if it does not already exist. 1518 */ 1519 add(key: __String, value: T): T[]; 1520 /** 1521 * Removes a value from an array of values associated with the key. 1522 * Does not preserve the order of those values. 1523 * Does nothing if `key` is not in `map`, or `value` is not in `map[key]`. 1524 */ 1525 remove(key: __String, value: T): void; 1526 } 1527 1528 export function createUnderscoreEscapedMultiMap<T>(): UnderscoreEscapedMultiMap<T> { 1529 return createMultiMap() as UnderscoreEscapedMultiMap<T>; 1530 } 1531 1532 /** 1533 * Tests whether a value is an array. 1534 */ 1535 export function isArray(value: any): value is readonly {}[] { 1536 return Array.isArray ? Array.isArray(value) : value instanceof Array; 1537 } 1538 1539 export function toArray<T>(value: T | T[]): T[]; 1540 export function toArray<T>(value: T | readonly T[]): readonly T[]; 1541 export function toArray<T>(value: T | T[]): T[] { 1542 return isArray(value) ? value : [value]; 1543 } 1544 1545 /** 1546 * Tests whether a value is string 1547 */ 1548 export function isString(text: unknown): text is string { 1549 return typeof text === "string"; 1550 } 1551 export function isNumber(x: unknown): x is number { 1552 return typeof x === "number"; 1553 } 1554 1555 export function tryCast<TOut extends TIn, TIn = any>(value: TIn | undefined, test: (value: TIn) => value is TOut): TOut | undefined; 1556 export function tryCast<T>(value: T, test: (value: T) => boolean): T | undefined; 1557 export function tryCast<T>(value: T, test: (value: T) => boolean): T | undefined { 1558 return value !== undefined && test(value) ? value : undefined; 1559 } 1560 1561 export function cast<TOut extends TIn, TIn = any>(value: TIn | undefined, test: (value: TIn) => value is TOut): TOut { 1562 if (value !== undefined && test(value)) return value; 1563 1564 return Debug.fail(`Invalid cast. The supplied value ${value} did not pass the test '${Debug.getFunctionName(test)}'.`); 1565 } 1566 1567 /** Does nothing. */ 1568 export function noop(_?: {} | null | undefined): void { } 1569 1570 /** Do nothing and return false */ 1571 export function returnFalse(): false { return false; } 1572 1573 /** Do nothing and return true */ 1574 export function returnTrue(): true { return true; } 1575 1576 /** Do nothing and return undefined */ 1577 export function returnUndefined(): undefined { return undefined; } 1578 1579 /** Returns its argument. */ 1580 export function identity<T>(x: T) { return x; } 1581 1582 /** Returns lower case string */ 1583 export function toLowerCase(x: string) { return x.toLowerCase(); } 1584 1585 // We convert the file names to lower case as key for file name on case insensitive file system 1586 // While doing so we need to handle special characters (eg \u0130) to ensure that we dont convert 1587 // it to lower case, fileName with its lowercase form can exist along side it. 1588 // Handle special characters and make those case sensitive instead 1589 // 1590 // |-#--|-Unicode--|-Char code-|-Desc-------------------------------------------------------------------| 1591 // | 1. | i | 105 | Ascii i | 1592 // | 2. | I | 73 | Ascii I | 1593 // |-------- Special characters ------------------------------------------------------------------------| 1594 // | 3. | \u0130 | 304 | Upper case I with dot above | 1595 // | 4. | i,\u0307 | 105,775 | i, followed by 775: Lower case of (3rd item) | 1596 // | 5. | I,\u0307 | 73,775 | I, followed by 775: Upper case of (4th item), lower case is (4th item) | 1597 // | 6. | \u0131 | 305 | Lower case i without dot, upper case is I (2nd item) | 1598 // | 7. | \u00DF | 223 | Lower case sharp s | 1599 // 1600 // Because item 3 is special where in its lowercase character has its own 1601 // upper case form we cant convert its case. 1602 // Rest special characters are either already in lower case format or 1603 // they have corresponding upper case character so they dont need special handling 1604 // 1605 // But to avoid having to do string building for most common cases, also ignore 1606 // a-z, 0-9, \u0131, \u00DF, \, /, ., : and space 1607 const fileNameLowerCaseRegExp = /[^\u0130\u0131\u00DFa-z0-9\\/:\-_\. ]+/g; 1608 /** 1609 * Case insensitive file systems have descripencies in how they handle some characters (eg. turkish Upper case I with dot on top - \u0130) 1610 * This function is used in places where we want to make file name as a key on these systems 1611 * It is possible on mac to be able to refer to file name with I with dot on top as a fileName with its lower case form 1612 * But on windows we cannot. Windows can have fileName with I with dot on top next to its lower case and they can not each be referred with the lowercase forms 1613 * Technically we would want this function to be platform sepcific as well but 1614 * our api has till now only taken caseSensitive as the only input and just for some characters we dont want to update API and ensure all customers use those api 1615 * We could use upper case and we would still need to deal with the descripencies but 1616 * we want to continue using lower case since in most cases filenames are lowercasewe and wont need any case changes and avoid having to store another string for the key 1617 * So for this function purpose, we go ahead and assume character I with dot on top it as case sensitive since its very unlikely to use lower case form of that special character 1618 */ 1619 export function toFileNameLowerCase(x: string) { 1620 return fileNameLowerCaseRegExp.test(x) ? 1621 x.replace(fileNameLowerCaseRegExp, toLowerCase) : 1622 x; 1623 } 1624 1625 /** Throws an error because a function is not implemented. */ 1626 export function notImplemented(): never { 1627 throw new Error("Not implemented"); 1628 } 1629 1630 export function memoize<T>(callback: () => T): () => T { 1631 let value: T; 1632 return () => { 1633 if (callback) { 1634 value = callback(); 1635 callback = undefined!; 1636 } 1637 return value; 1638 }; 1639 } 1640 1641 /** A version of `memoize` that supports a single primitive argument */ 1642 export function memoizeOne<A extends string | number | boolean | undefined, T>(callback: (arg: A) => T): (arg: A) => T { 1643 const map = new Map<string, T>(); 1644 return (arg: A) => { 1645 const key = `${typeof arg}:${arg}`; 1646 let value = map.get(key); 1647 if (value === undefined && !map.has(key)) { 1648 value = callback(arg); 1649 map.set(key, value); 1650 } 1651 return value!; 1652 }; 1653 } 1654 1655 /** 1656 * High-order function, composes functions. Note that functions are composed inside-out; 1657 * for example, `compose(a, b)` is the equivalent of `x => b(a(x))`. 1658 * 1659 * @param args The functions to compose. 1660 */ 1661 export function compose<T>(...args: ((t: T) => T)[]): (t: T) => T; 1662 export function compose<T>(a: (t: T) => T, b: (t: T) => T, c: (t: T) => T, d: (t: T) => T, e: (t: T) => T): (t: T) => T { 1663 if (!!e) { 1664 const args: ((t: T) => T)[] = []; 1665 for (let i = 0; i < arguments.length; i++) { 1666 args[i] = arguments[i]; 1667 } 1668 1669 return t => reduceLeft(args, (u, f) => f(u), t); 1670 } 1671 else if (d) { 1672 return t => d(c(b(a(t)))); 1673 } 1674 else if (c) { 1675 return t => c(b(a(t))); 1676 } 1677 else if (b) { 1678 return t => b(a(t)); 1679 } 1680 else if (a) { 1681 return t => a(t); 1682 } 1683 else { 1684 return t => t; 1685 } 1686 } 1687 1688 export const enum AssertionLevel { 1689 None = 0, 1690 Normal = 1, 1691 Aggressive = 2, 1692 VeryAggressive = 3, 1693 } 1694 1695 /** 1696 * Safer version of `Function` which should not be called. 1697 * Every function should be assignable to this, but this should not be assignable to every function. 1698 */ 1699 export type AnyFunction = (...args: never[]) => void; 1700 export type AnyConstructor = new (...args: unknown[]) => unknown; 1701 1702 export function equateValues<T>(a: T, b: T) { 1703 return a === b; 1704 } 1705 1706 /** 1707 * Compare the equality of two strings using a case-sensitive ordinal comparison. 1708 * 1709 * Case-sensitive comparisons compare both strings one code-point at a time using the integer 1710 * value of each code-point after applying `toUpperCase` to each string. We always map both 1711 * strings to their upper-case form as some unicode characters do not properly round-trip to 1712 * lowercase (such as `ẞ` (German sharp capital s)). 1713 */ 1714 export function equateStringsCaseInsensitive(a: string, b: string) { 1715 return a === b 1716 || a !== undefined 1717 && b !== undefined 1718 && a.toUpperCase() === b.toUpperCase(); 1719 } 1720 1721 /** 1722 * Compare the equality of two strings using a case-sensitive ordinal comparison. 1723 * 1724 * Case-sensitive comparisons compare both strings one code-point at a time using the 1725 * integer value of each code-point. 1726 */ 1727 export function equateStringsCaseSensitive(a: string, b: string) { 1728 return equateValues(a, b); 1729 } 1730 1731 function compareComparableValues(a: string | undefined, b: string | undefined): Comparison; 1732 function compareComparableValues(a: number | undefined, b: number | undefined): Comparison; 1733 function compareComparableValues(a: string | number | undefined, b: string | number | undefined) { 1734 return a === b ? Comparison.EqualTo : 1735 a === undefined ? Comparison.LessThan : 1736 b === undefined ? Comparison.GreaterThan : 1737 a < b ? Comparison.LessThan : 1738 Comparison.GreaterThan; 1739 } 1740 1741 /** 1742 * Compare two numeric values for their order relative to each other. 1743 * To compare strings, use any of the `compareStrings` functions. 1744 */ 1745 export function compareValues(a: number | undefined, b: number | undefined): Comparison { 1746 return compareComparableValues(a, b); 1747 } 1748 1749 /** 1750 * Compare two TextSpans, first by `start`, then by `length`. 1751 */ 1752 export function compareTextSpans(a: Partial<TextSpan> | undefined, b: Partial<TextSpan> | undefined): Comparison { 1753 return compareValues(a?.start, b?.start) || compareValues(a?.length, b?.length); 1754 } 1755 1756 export function min<T>(a: T, b: T, compare: Comparer<T>): T { 1757 return compare(a, b) === Comparison.LessThan ? a : b; 1758 } 1759 1760 /** 1761 * Compare two strings using a case-insensitive ordinal comparison. 1762 * 1763 * Ordinal comparisons are based on the difference between the unicode code points of both 1764 * strings. Characters with multiple unicode representations are considered unequal. Ordinal 1765 * comparisons provide predictable ordering, but place "a" after "B". 1766 * 1767 * Case-insensitive comparisons compare both strings one code-point at a time using the integer 1768 * value of each code-point after applying `toUpperCase` to each string. We always map both 1769 * strings to their upper-case form as some unicode characters do not properly round-trip to 1770 * lowercase (such as `ẞ` (German sharp capital s)). 1771 */ 1772 export function compareStringsCaseInsensitive(a: string, b: string) { 1773 if (a === b) return Comparison.EqualTo; 1774 if (a === undefined) return Comparison.LessThan; 1775 if (b === undefined) return Comparison.GreaterThan; 1776 a = a.toUpperCase(); 1777 b = b.toUpperCase(); 1778 return a < b ? Comparison.LessThan : a > b ? Comparison.GreaterThan : Comparison.EqualTo; 1779 } 1780 1781 /** 1782 * Compare two strings using a case-sensitive ordinal comparison. 1783 * 1784 * Ordinal comparisons are based on the difference between the unicode code points of both 1785 * strings. Characters with multiple unicode representations are considered unequal. Ordinal 1786 * comparisons provide predictable ordering, but place "a" after "B". 1787 * 1788 * Case-sensitive comparisons compare both strings one code-point at a time using the integer 1789 * value of each code-point. 1790 */ 1791 export function compareStringsCaseSensitive(a: string | undefined, b: string | undefined): Comparison { 1792 return compareComparableValues(a, b); 1793 } 1794 1795 export function getStringComparer(ignoreCase?: boolean) { 1796 return ignoreCase ? compareStringsCaseInsensitive : compareStringsCaseSensitive; 1797 } 1798 1799 /** 1800 * Creates a string comparer for use with string collation in the UI. 1801 */ 1802 const createUIStringComparer = (() => { 1803 let defaultComparer: Comparer<string> | undefined; 1804 let enUSComparer: Comparer<string> | undefined; 1805 1806 const stringComparerFactory = getStringComparerFactory(); 1807 return createStringComparer; 1808 1809 function compareWithCallback(a: string | undefined, b: string | undefined, comparer: (a: string, b: string) => number) { 1810 if (a === b) return Comparison.EqualTo; 1811 if (a === undefined) return Comparison.LessThan; 1812 if (b === undefined) return Comparison.GreaterThan; 1813 const value = comparer(a, b); 1814 return value < 0 ? Comparison.LessThan : value > 0 ? Comparison.GreaterThan : Comparison.EqualTo; 1815 } 1816 1817 function createIntlCollatorStringComparer(locale: string | undefined): Comparer<string> { 1818 // Intl.Collator.prototype.compare is bound to the collator. See NOTE in 1819 // http://www.ecma-international.org/ecma-402/2.0/#sec-Intl.Collator.prototype.compare 1820 const comparer = new Intl.Collator(locale, { usage: "sort", sensitivity: "variant" }).compare; 1821 return (a, b) => compareWithCallback(a, b, comparer); 1822 } 1823 1824 function createLocaleCompareStringComparer(locale: string | undefined): Comparer<string> { 1825 // if the locale is not the default locale (`undefined`), use the fallback comparer. 1826 if (locale !== undefined) return createFallbackStringComparer(); 1827 1828 return (a, b) => compareWithCallback(a, b, compareStrings); 1829 1830 function compareStrings(a: string, b: string) { 1831 return a.localeCompare(b); 1832 } 1833 } 1834 1835 function createFallbackStringComparer(): Comparer<string> { 1836 // An ordinal comparison puts "A" after "b", but for the UI we want "A" before "b". 1837 // We first sort case insensitively. So "Aaa" will come before "baa". 1838 // Then we sort case sensitively, so "aaa" will come before "Aaa". 1839 // 1840 // For case insensitive comparisons we always map both strings to their 1841 // upper-case form as some unicode characters do not properly round-trip to 1842 // lowercase (such as `ẞ` (German sharp capital s)). 1843 return (a, b) => compareWithCallback(a, b, compareDictionaryOrder); 1844 1845 function compareDictionaryOrder(a: string, b: string) { 1846 return compareStrings(a.toUpperCase(), b.toUpperCase()) || compareStrings(a, b); 1847 } 1848 1849 function compareStrings(a: string, b: string) { 1850 return a < b ? Comparison.LessThan : a > b ? Comparison.GreaterThan : Comparison.EqualTo; 1851 } 1852 } 1853 1854 function getStringComparerFactory() { 1855 // If the host supports Intl, we use it for comparisons using the default locale. 1856 if (typeof Intl === "object" && typeof Intl.Collator === "function") { 1857 return createIntlCollatorStringComparer; 1858 } 1859 1860 // If the host does not support Intl, we fall back to localeCompare. 1861 // localeCompare in Node v0.10 is just an ordinal comparison, so don't use it. 1862 if (typeof String.prototype.localeCompare === "function" && 1863 typeof String.prototype.toLocaleUpperCase === "function" && 1864 "a".localeCompare("B") < 0) { 1865 return createLocaleCompareStringComparer; 1866 } 1867 1868 // Otherwise, fall back to ordinal comparison: 1869 return createFallbackStringComparer; 1870 } 1871 1872 function createStringComparer(locale: string | undefined) { 1873 // Hold onto common string comparers. This avoids constantly reallocating comparers during 1874 // tests. 1875 if (locale === undefined) { 1876 return defaultComparer || (defaultComparer = stringComparerFactory(locale)); 1877 } 1878 else if (locale === "en-US") { 1879 return enUSComparer || (enUSComparer = stringComparerFactory(locale)); 1880 } 1881 else { 1882 return stringComparerFactory(locale); 1883 } 1884 } 1885 })(); 1886 1887 let uiComparerCaseSensitive: Comparer<string> | undefined; 1888 let uiLocale: string | undefined; 1889 1890 export function getUILocale() { 1891 return uiLocale; 1892 } 1893 1894 export function setUILocale(value: string | undefined) { 1895 if (uiLocale !== value) { 1896 uiLocale = value; 1897 uiComparerCaseSensitive = undefined; 1898 } 1899 } 1900 1901 /** 1902 * Compare two strings in a using the case-sensitive sort behavior of the UI locale. 1903 * 1904 * Ordering is not predictable between different host locales, but is best for displaying 1905 * ordered data for UI presentation. Characters with multiple unicode representations may 1906 * be considered equal. 1907 * 1908 * Case-sensitive comparisons compare strings that differ in base characters, or 1909 * accents/diacritic marks, or case as unequal. 1910 */ 1911 export function compareStringsCaseSensitiveUI(a: string, b: string) { 1912 const comparer = uiComparerCaseSensitive || (uiComparerCaseSensitive = createUIStringComparer(uiLocale)); 1913 return comparer(a, b); 1914 } 1915 1916 export function compareProperties<T, K extends keyof T>(a: T | undefined, b: T | undefined, key: K, comparer: Comparer<T[K]>): Comparison { 1917 return a === b ? Comparison.EqualTo : 1918 a === undefined ? Comparison.LessThan : 1919 b === undefined ? Comparison.GreaterThan : 1920 comparer(a[key], b[key]); 1921 } 1922 1923 /** True is greater than false. */ 1924 export function compareBooleans(a: boolean, b: boolean): Comparison { 1925 return compareValues(a ? 1 : 0, b ? 1 : 0); 1926 } 1927 1928 /** 1929 * Given a name and a list of names that are *not* equal to the name, return a spelling suggestion if there is one that is close enough. 1930 * Names less than length 3 only check for case-insensitive equality. 1931 * 1932 * find the candidate with the smallest Levenshtein distance, 1933 * except for candidates: 1934 * * With no name 1935 * * Whose length differs from the target name by more than 0.34 of the length of the name. 1936 * * Whose levenshtein distance is more than 0.4 of the length of the name 1937 * (0.4 allows 1 substitution/transposition for every 5 characters, 1938 * and 1 insertion/deletion at 3 characters) 1939 */ 1940 export function getSpellingSuggestion<T>(name: string, candidates: T[], getName: (candidate: T) => string | undefined): T | undefined { 1941 const maximumLengthDifference = Math.min(2, Math.floor(name.length * 0.34)); 1942 let bestDistance = Math.floor(name.length * 0.4) + 1; // If the best result is worse than this, don't bother. 1943 let bestCandidate: T | undefined; 1944 for (const candidate of candidates) { 1945 const candidateName = getName(candidate); 1946 if (candidateName !== undefined && Math.abs(candidateName.length - name.length) <= maximumLengthDifference) { 1947 if (candidateName === name) { 1948 continue; 1949 } 1950 // Only consider candidates less than 3 characters long when they differ by case. 1951 // Otherwise, don't bother, since a user would usually notice differences of a 2-character name. 1952 if (candidateName.length < 3 && candidateName.toLowerCase() !== name.toLowerCase()) { 1953 continue; 1954 } 1955 1956 const distance = levenshteinWithMax(name, candidateName, bestDistance - 0.1); 1957 if (distance === undefined) { 1958 continue; 1959 } 1960 1961 Debug.assert(distance < bestDistance); // Else `levenshteinWithMax` should return undefined 1962 bestDistance = distance; 1963 bestCandidate = candidate; 1964 } 1965 } 1966 return bestCandidate; 1967 } 1968 1969 function levenshteinWithMax(s1: string, s2: string, max: number): number | undefined { 1970 let previous = new Array(s2.length + 1); 1971 let current = new Array(s2.length + 1); 1972 /** Represents any value > max. We don't care about the particular value. */ 1973 const big = max + 0.01; 1974 1975 for (let i = 0; i <= s2.length; i++) { 1976 previous[i] = i; 1977 } 1978 1979 for (let i = 1; i <= s1.length; i++) { 1980 const c1 = s1.charCodeAt(i - 1); 1981 const minJ = Math.ceil(i > max ? i - max : 1); 1982 const maxJ = Math.floor(s2.length > max + i ? max + i : s2.length); 1983 current[0] = i; 1984 /** Smallest value of the matrix in the ith column. */ 1985 let colMin = i; 1986 for (let j = 1; j < minJ; j++) { 1987 current[j] = big; 1988 } 1989 for (let j = minJ; j <= maxJ; j++) { 1990 // case difference should be significantly cheaper than other differences 1991 const substitutionDistance = s1[i - 1].toLowerCase() === s2[j-1].toLowerCase() 1992 ? (previous[j - 1] + 0.1) 1993 : (previous[j - 1] + 2); 1994 const dist = c1 === s2.charCodeAt(j - 1) 1995 ? previous[j - 1] 1996 : Math.min(/*delete*/ previous[j] + 1, /*insert*/ current[j - 1] + 1, /*substitute*/ substitutionDistance); 1997 current[j] = dist; 1998 colMin = Math.min(colMin, dist); 1999 } 2000 for (let j = maxJ + 1; j <= s2.length; j++) { 2001 current[j] = big; 2002 } 2003 if (colMin > max) { 2004 // Give up -- everything in this column is > max and it can't get better in future columns. 2005 return undefined; 2006 } 2007 2008 const temp = previous; 2009 previous = current; 2010 current = temp; 2011 } 2012 2013 const res = previous[s2.length]; 2014 return res > max ? undefined : res; 2015 } 2016 2017 export function endsWith(str: string, suffix: string): boolean { 2018 const expectedPos = str.length - suffix.length; 2019 return expectedPos >= 0 && str.indexOf(suffix, expectedPos) === expectedPos; 2020 } 2021 2022 export function removeSuffix(str: string, suffix: string): string { 2023 return endsWith(str, suffix) ? str.slice(0, str.length - suffix.length) : str; 2024 } 2025 2026 export function tryRemoveSuffix(str: string, suffix: string): string | undefined { 2027 return endsWith(str, suffix) ? str.slice(0, str.length - suffix.length) : undefined; 2028 } 2029 2030 export function stringContains(str: string, substring: string): boolean { 2031 return str.indexOf(substring) !== -1; 2032 } 2033 2034 /** 2035 * Takes a string like "jquery-min.4.2.3" and returns "jquery" 2036 */ 2037 export function removeMinAndVersionNumbers(fileName: string) { 2038 // Match a "." or "-" followed by a version number or 'min' at the end of the name 2039 const trailingMinOrVersion = /[.-]((min)|(\d+(\.\d+)*))$/; 2040 2041 // The "min" or version may both be present, in either order, so try applying the above twice. 2042 return fileName.replace(trailingMinOrVersion, "").replace(trailingMinOrVersion, ""); 2043 } 2044 2045 /** Remove an item from an array, moving everything to its right one space left. */ 2046 export function orderedRemoveItem<T>(array: T[], item: T): boolean { 2047 for (let i = 0; i < array.length; i++) { 2048 if (array[i] === item) { 2049 orderedRemoveItemAt(array, i); 2050 return true; 2051 } 2052 } 2053 return false; 2054 } 2055 2056 /** Remove an item by index from an array, moving everything to its right one space left. */ 2057 export function orderedRemoveItemAt<T>(array: T[], index: number): void { 2058 // This seems to be faster than either `array.splice(i, 1)` or `array.copyWithin(i, i+ 1)`. 2059 for (let i = index; i < array.length - 1; i++) { 2060 array[i] = array[i + 1]; 2061 } 2062 array.pop(); 2063 } 2064 2065 export function unorderedRemoveItemAt<T>(array: T[], index: number): void { 2066 // Fill in the "hole" left at `index`. 2067 array[index] = array[array.length - 1]; 2068 array.pop(); 2069 } 2070 2071 /** Remove the *first* occurrence of `item` from the array. */ 2072 export function unorderedRemoveItem<T>(array: T[], item: T) { 2073 return unorderedRemoveFirstItemWhere(array, element => element === item); 2074 } 2075 2076 /** Remove the *first* element satisfying `predicate`. */ 2077 function unorderedRemoveFirstItemWhere<T>(array: T[], predicate: (element: T) => boolean) { 2078 for (let i = 0; i < array.length; i++) { 2079 if (predicate(array[i])) { 2080 unorderedRemoveItemAt(array, i); 2081 return true; 2082 } 2083 } 2084 return false; 2085 } 2086 2087 export type GetCanonicalFileName = (fileName: string) => string; 2088 export function createGetCanonicalFileName(useCaseSensitiveFileNames: boolean): GetCanonicalFileName { 2089 return useCaseSensitiveFileNames ? identity : toFileNameLowerCase; 2090 } 2091 2092 /** Represents a "prefix*suffix" pattern. */ 2093 export interface Pattern { 2094 prefix: string; 2095 suffix: string; 2096 } 2097 2098 export function patternText({ prefix, suffix }: Pattern): string { 2099 return `${prefix}*${suffix}`; 2100 } 2101 2102 /** 2103 * Given that candidate matches pattern, returns the text matching the '*'. 2104 * E.g.: matchedText(tryParsePattern("foo*baz"), "foobarbaz") === "bar" 2105 */ 2106 export function matchedText(pattern: Pattern, candidate: string): string { 2107 Debug.assert(isPatternMatch(pattern, candidate)); 2108 return candidate.substring(pattern.prefix.length, candidate.length - pattern.suffix.length); 2109 } 2110 2111 /** Return the object corresponding to the best pattern to match `candidate`. */ 2112 export function findBestPatternMatch<T>(values: readonly T[], getPattern: (value: T) => Pattern, candidate: string): T | undefined { 2113 let matchedValue: T | undefined; 2114 // use length of prefix as betterness criteria 2115 let longestMatchPrefixLength = -1; 2116 2117 for (const v of values) { 2118 const pattern = getPattern(v); 2119 if (isPatternMatch(pattern, candidate) && pattern.prefix.length > longestMatchPrefixLength) { 2120 longestMatchPrefixLength = pattern.prefix.length; 2121 matchedValue = v; 2122 } 2123 } 2124 2125 return matchedValue; 2126 } 2127 2128 export function startsWith(str: string, prefix: string): boolean { 2129 return str.lastIndexOf(prefix, 0) === 0; 2130 } 2131 2132 export function removePrefix(str: string, prefix: string): string { 2133 return startsWith(str, prefix) ? str.substr(prefix.length) : str; 2134 } 2135 2136 export function tryRemovePrefix(str: string, prefix: string, getCanonicalFileName: GetCanonicalFileName = identity): string | undefined { 2137 return startsWith(getCanonicalFileName(str), getCanonicalFileName(prefix)) ? str.substring(prefix.length) : undefined; 2138 } 2139 2140 function isPatternMatch({ prefix, suffix }: Pattern, candidate: string) { 2141 return candidate.length >= prefix.length + suffix.length && 2142 startsWith(candidate, prefix) && 2143 endsWith(candidate, suffix); 2144 } 2145 2146 export function and<T>(f: (arg: T) => boolean, g: (arg: T) => boolean) { 2147 return (arg: T) => f(arg) && g(arg); 2148 } 2149 2150 export function or<T extends unknown[]>(...fs: ((...args: T) => boolean)[]): (...args: T) => boolean { 2151 return (...args) => { 2152 for (const f of fs) { 2153 if (f(...args)) { 2154 return true; 2155 } 2156 } 2157 return false; 2158 }; 2159 } 2160 2161 export function not<T extends unknown[]>(fn: (...args: T) => boolean): (...args: T) => boolean { 2162 return (...args) => !fn(...args); 2163 } 2164 2165 export function assertType<T>(_: T): void { } 2166 2167 export function singleElementArray<T>(t: T | undefined): T[] | undefined { 2168 return t === undefined ? undefined : [t]; 2169 } 2170 2171 export function enumerateInsertsAndDeletes<T, U>(newItems: readonly T[], oldItems: readonly U[], comparer: (a: T, b: U) => Comparison, inserted: (newItem: T) => void, deleted: (oldItem: U) => void, unchanged?: (oldItem: U, newItem: T) => void) { 2172 unchanged = unchanged || noop; 2173 let newIndex = 0; 2174 let oldIndex = 0; 2175 const newLen = newItems.length; 2176 const oldLen = oldItems.length; 2177 let hasChanges = false; 2178 while (newIndex < newLen && oldIndex < oldLen) { 2179 const newItem = newItems[newIndex]; 2180 const oldItem = oldItems[oldIndex]; 2181 const compareResult = comparer(newItem, oldItem); 2182 if (compareResult === Comparison.LessThan) { 2183 inserted(newItem); 2184 newIndex++; 2185 hasChanges = true; 2186 } 2187 else if (compareResult === Comparison.GreaterThan) { 2188 deleted(oldItem); 2189 oldIndex++; 2190 hasChanges = true; 2191 } 2192 else { 2193 unchanged(oldItem, newItem); 2194 newIndex++; 2195 oldIndex++; 2196 } 2197 } 2198 while (newIndex < newLen) { 2199 inserted(newItems[newIndex++]); 2200 hasChanges = true; 2201 } 2202 while (oldIndex < oldLen) { 2203 deleted(oldItems[oldIndex++]); 2204 hasChanges = true; 2205 } 2206 return hasChanges; 2207 } 2208 2209 export function fill<T>(length: number, cb: (index: number) => T): T[] { 2210 const result = Array<T>(length); 2211 for (let i = 0; i < length; i++) { 2212 result[i] = cb(i); 2213 } 2214 return result; 2215 } 2216 2217 export function cartesianProduct<T>(arrays: readonly T[][]) { 2218 const result: T[][] = []; 2219 cartesianProductWorker(arrays, result, /*outer*/ undefined, 0); 2220 return result; 2221 } 2222 2223 function cartesianProductWorker<T>(arrays: readonly (readonly T[])[], result: (readonly T[])[], outer: readonly T[] | undefined, index: number) { 2224 for (const element of arrays[index]) { 2225 let inner: T[]; 2226 if (outer) { 2227 inner = outer.slice(); 2228 inner.push(element); 2229 } 2230 else { 2231 inner = [element]; 2232 } 2233 if (index === arrays.length - 1) { 2234 result.push(inner); 2235 } 2236 else { 2237 cartesianProductWorker(arrays, result, inner, index + 1); 2238 } 2239 } 2240 } 2241 2242 2243 /** 2244 * Returns string left-padded with spaces or zeros until it reaches the given length. 2245 * 2246 * @param s String to pad. 2247 * @param length Final padded length. If less than or equal to 's.length', returns 's' unchanged. 2248 * @param padString Character to use as padding (default " "). 2249 */ 2250 export function padLeft(s: string, length: number, padString: " " | "0" = " ") { 2251 return length <= s.length ? s : padString.repeat(length - s.length) + s; 2252 } 2253 2254 /** 2255 * Returns string right-padded with spaces until it reaches the given length. 2256 * 2257 * @param s String to pad. 2258 * @param length Final padded length. If less than or equal to 's.length', returns 's' unchanged. 2259 * @param padString Character to use as padding (default " "). 2260 */ 2261 export function padRight(s: string, length: number, padString: " " = " ") { 2262 return length <= s.length ? s : s + padString.repeat(length - s.length); 2263 } 2264 2265 export function takeWhile<T, U extends T>(array: readonly T[], predicate: (element: T) => element is U): U[]; 2266 export function takeWhile<T>(array: readonly T[], predicate: (element: T) => boolean): T[] { 2267 const len = array.length; 2268 let index = 0; 2269 while (index < len && predicate(array[index])) { 2270 index++; 2271 } 2272 return array.slice(0, index); 2273 } 2274} 2275