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