namespace ts {

// WARNING: The script `configureNightly.ts` uses a regexp to parse out these values.

// If changing the text in this section, be sure to test `configureNightly` too.

export const versionMajorMinor = "3.0";

/** The version of the TypeScript compiler release */

export const version = `${versionMajorMinor}.0-dev`;

}

namespace ts {

export function isExternalModuleNameRelative(moduleName: string): boolean {

// TypeScript 1.0 spec (April 2014): 11.2.1

// An external module name is "relative" if the first term is "." or "..".

// Update: We also consider a path like `C:\foo.ts` "relative" because we do not search for it in `node_modules` or treat it as an ambient module.

return pathIsRelative(moduleName) || isRootedDiskPath(moduleName);

}

export function sortAndDeduplicateDiagnostics<T extends Diagnostic>(diagnostics: ReadonlyArray<T>): T[] {

return sortAndDeduplicate<T>(diagnostics, compareDiagnostics);

}

}

/* @internal */

namespace ts {

export const emptyArray: never[] = [] as never[];

export function closeFileWatcher(watcher: FileWatcher) {

watcher.close();

}

/** Create a MapLike with good performance. */

function createDictionaryObject<T>(): MapLike<T> {

const map = Object.create(/*prototype*/ null); // tslint:disable-line:no-null-keyword

// Using 'delete' on an object causes V8 to put the object in dictionary mode.

// This disables creation of hidden classes, which are expensive when an object is

// constantly changing shape.

map.__ = undefined;

delete map.__;

return map;

}

/** Create a new map. If a template object is provided, the map will copy entries from it. */

export function createMap<T>(): Map<T> {

return new MapCtr<T>();

}

/** Create a new escaped identifier map. */

export function createUnderscoreEscapedMap<T>(): UnderscoreEscapedMap<T> {

return new MapCtr<T>() as UnderscoreEscapedMap<T>;

}

export function createSymbolTable(symbols?: ReadonlyArray<Symbol>): SymbolTable {

const result = createMap<Symbol>() as SymbolTable;

if (symbols) {

for (const symbol of symbols) {

result.set(symbol.escapedName, symbol);

}

}

return result;

}

export function createMapFromEntries<T>(entries: [string, T][]): Map<T> {

const map = createMap<T>();

for (const [key, value] of entries) {

map.set(key, value);

}

return map;

}

export function createMapFromTemplate<T>(template: MapLike<T>): Map<T> {

const map: Map<T> = new MapCtr<T>();

// Copies keys/values from template. Note that for..in will not throw if

// template is undefined, and instead will just exit the loop.

for (const key in template) {

if (hasOwnProperty.call(template, key)) {

map.set(key, template[key]);

}

}

return map;

}

// The global Map object. This may not be available, so we must test for it.

declare const Map: { new <T>(): Map<T> } | undefined;

// Internet Explorer's Map doesn't support iteration, so don't use it.

// tslint:disable-next-line no-in-operator variable-name

const MapCtr = typeof Map !== "undefined" && "entries" in Map.prototype ? Map : shimMap();

// Keep the class inside a function so it doesn't get compiled if it's not used.

function shimMap(): { new <T>(): Map<T> } {

class MapIterator<T, U extends (string | T | [string, T])> {

private data: MapLike<T>;

private keys: ReadonlyArray<string>;

private index = 0;

private selector: (data: MapLike<T>, key: string) => U;

constructor(data: MapLike<T>, selector: (data: MapLike<T>, key: string) => U) {

this.data = data;

this.selector = selector;

this.keys = Object.keys(data);

}

public next(): { value: U, done: false } | { value: never, done: true } {

const index = this.index;

if (index < this.keys.length) {

this.index++;

return { value: this.selector(this.data, this.keys[index]), done: false };

}

return { value: undefined as never, done: true };

}

}

return class <T> implements Map<T> {

private data = createDictionaryObject<T>();

public size = 0;

get(key: string): T | undefined {

return this.data[key];

}

set(key: string, value: T): this {

if (!this.has(key)) {

this.size++;

}

this.data[key] = value;

return this;

}

has(key: string): boolean {

// tslint:disable-next-line:no-in-operator

return key in this.data;

}

delete(key: string): boolean {

if (this.has(key)) {

this.size--;

delete this.data[key];

return true;

}

return false;

}

clear(): void {

this.data = createDictionaryObject<T>();

this.size = 0;

}

keys(): Iterator<string> {

return new MapIterator(this.data, (_data, key) => key);

}

values(): Iterator<T> {

return new MapIterator(this.data, (data, key) => data[key]);

}

entries(): Iterator<[string, T]> {

return new MapIterator(this.data, (data, key) => [key, data[key]] as [string, T]);

}

forEach(action: (value: T, key: string) => void): void {

for (const key in this.data) {

action(this.data[key], key);

}

}

};

}

export function toPath(fileName: string, basePath: string | undefined, getCanonicalFileName: (path: string) => string): Path {

const nonCanonicalizedPath = isRootedDiskPath(fileName)

? normalizePath(fileName)

: getNormalizedAbsolutePath(fileName, basePath);

return <Path>getCanonicalFileName(nonCanonicalizedPath);

}

export function length(array: ReadonlyArray<any> | undefined): number {

return array ? array.length : 0;

}

export function hasEntries(map: ReadonlyUnderscoreEscapedMap<any> | undefined): map is ReadonlyUnderscoreEscapedMap<any> {

return !!map && !!map.size;

}

/**

* Iterates through 'array' by index and performs the callback on each element of array until the callback

* returns a truthy value, then returns that value.

* If no such value is found, the callback is applied to each element of array and undefined is returned.

*/

export function forEach<T, U>(array: ReadonlyArray<T> | undefined, callback: (element: T, index: number) => U | undefined): U | undefined {

if (array) {

for (let i = 0; i < array.length; i++) {

const result = callback(array[i], i);

if (result) {

return result;

}

}

}

return undefined;

}

/** Like `forEach`, but suitable for use with numbers and strings (which may be falsy). */

export function firstDefined<T, U>(array: ReadonlyArray<T> | undefined, callback: (element: T, index: number) => U | undefined): U | undefined {

if (array === undefined) {

return undefined;

}

for (let i = 0; i < array.length; i++) {

const result = callback(array[i], i);

if (result !== undefined) {

return result;

}

}

return undefined;

}

export function firstDefinedIterator<T, U>(iter: Iterator<T>, callback: (element: T) => U | undefined): U | undefined {

while (true) {

const { value, done } = iter.next();

if (done) {

return undefined;

}

const result = callback(value);

if (result !== undefined) {

return result;

}

}

}

/**

* Iterates through the parent chain of a node and performs the callback on each parent until the callback

* returns a truthy value, then returns that value.

* If no such value is found, it applies the callback until the parent pointer is undefined or the callback returns "quit"

* At that point findAncestor returns undefined.

*/

export function findAncestor<T extends Node>(node: Node | undefined, callback: (element: Node) => element is T): T | undefined;

export function findAncestor(node: Node | undefined, callback: (element: Node) => boolean | "quit"): Node | undefined;

export function findAncestor(node: Node, callback: (element: Node) => boolean | "quit"): Node | undefined {

while (node) {

const result = callback(node);

if (result === "quit") {

return undefined;

}

else if (result) {

return node;

}

node = node.parent;

}

return undefined;

}

export function zipWith<T, U, V>(arrayA: ReadonlyArray<T>, arrayB: ReadonlyArray<U>, callback: (a: T, b: U, index: number) => V): V[] {

const result: V[] = [];

Debug.assertEqual(arrayA.length, arrayB.length);

for (let i = 0; i < arrayA.length; i++) {

result.push(callback(arrayA[i], arrayB[i], i));

}

return result;

}

export function zipToIterator<T, U>(arrayA: ReadonlyArray<T>, arrayB: ReadonlyArray<U>): Iterator<[T, U]> {

Debug.assertEqual(arrayA.length, arrayB.length);

let i = 0;

return {

next() {

if (i === arrayA.length) {

return { value: undefined as never, done: true };

}

i++;

return { value: [arrayA[i - 1], arrayB[i - 1]], done: false };

}

};

}

export function zipToMap<T>(keys: ReadonlyArray<string>, values: ReadonlyArray<T>): Map<T> {

Debug.assert(keys.length === values.length);

const map = createMap<T>();

for (let i = 0; i < keys.length; ++i) {

map.set(keys[i], values[i]);

}

return map;

}

/**

* Iterates through `array` by index and performs the callback on each element of array until the callback

* returns a falsey value, then returns false.

* If no such value is found, the callback is applied to each element of array and `true` is returned.

*/

export function every<T>(array: ReadonlyArray<T>, callback: (element: T, index: number) => boolean): boolean {

if (array) {

for (let i = 0; i < array.length; i++) {

if (!callback(array[i], i)) {

return false;

}

}

}

return true;

}

/** Works like Array.prototype.find, returning `undefined` if no element satisfying the predicate is found. */

export function find<T, U extends T>(array: ReadonlyArray<T>, predicate: (element: T, index: number) => element is U): U | undefined;

export function find<T>(array: ReadonlyArray<T>, predicate: (element: T, index: number) => boolean): T | undefined;

export function find<T>(array: ReadonlyArray<T>, predicate: (element: T, index: number) => boolean): T | undefined {

for (let i = 0; i < array.length; i++) {

const value = array[i];

if (predicate(value, i)) {

return value;

}

}

return undefined;

}

export function findLast<T, U extends T>(array: ReadonlyArray<T>, predicate: (element: T, index: number) => element is U): U | undefined;

export function findLast<T>(array: ReadonlyArray<T>, predicate: (element: T, index: number) => boolean): T | undefined;

export function findLast<T>(array: ReadonlyArray<T>, predicate: (element: T, index: number) => boolean): T | undefined {

for (let i = array.length - 1; i >= 0; i--) {

const value = array[i];

if (predicate(value, i)) {

return value;

}

}

return undefined;

}

/** Works like Array.prototype.findIndex, returning `-1` if no element satisfying the predicate is found. */

export function findIndex<T>(array: ReadonlyArray<T>, predicate: (element: T, index: number) => boolean, startIndex?: number): number {

for (let i = startIndex || 0; i < array.length; i++) {

if (predicate(array[i], i)) {

return i;

}

}

return -1;

}

export function findLastIndex<T>(array: ReadonlyArray<T>, predicate: (element: T, index: number) => boolean, startIndex?: number): number {

for (let i = startIndex === undefined ? array.length - 1 : startIndex; i >= 0; i--) {

if (predicate(array[i], i)) {

return i;

}

}

return -1;

}

/**

* Returns the first truthy result of `callback`, or else fails.

* This is like `forEach`, but never returns undefined.

*/

export function findMap<T, U>(array: ReadonlyArray<T>, callback: (element: T, index: number) => U | undefined): U {

for (let i = 0; i < array.length; i++) {

const result = callback(array[i], i);

if (result) {

return result;

}

}

return Debug.fail();

}

export function contains<T>(array: ReadonlyArray<T> | undefined, value: T, equalityComparer: EqualityComparer<T> = equateValues): boolean {

if (array) {

for (const v of array) {

if (equalityComparer(v, value)) {

return true;

}

}

}

return false;

}

export function arraysEqual<T>(a: ReadonlyArray<T>, b: ReadonlyArray<T>, equalityComparer: EqualityComparer<T> = equateValues): boolean {

return a.length === b.length && a.every((x, i) => equalityComparer(x, b[i]));

}

export function indexOfAnyCharCode(text: string, charCodes: ReadonlyArray<number>, start?: number): number {

for (let i = start || 0; i < text.length; i++) {

if (contains(charCodes, text.charCodeAt(i))) {

return i;

}

}

return -1;

}

export function countWhere<T>(array: ReadonlyArray<T>, predicate: (x: T, i: number) => boolean): number {

let count = 0;

if (array) {

for (let i = 0; i < array.length; i++) {

const v = array[i];

if (predicate(v, i)) {

count++;

}

}

}

return count;

}

/**

* Filters an array by a predicate function. Returns the same array instance if the predicate is

* true for all elements, otherwise returns a new array instance containing the filtered subset.

*/

export function filter<T, U extends T>(array: T[], f: (x: T) => x is U): U[];

export function filter<T>(array: T[], f: (x: T) => boolean): T[];

export function filter<T, U extends T>(array: ReadonlyArray<T>, f: (x: T) => x is U): ReadonlyArray<U>;

export function filter<T, U extends T>(array: ReadonlyArray<T>, f: (x: T) => boolean): ReadonlyArray<T>;

export function filter<T, U extends T>(array: T[] | undefined, f: (x: T) => x is U): U[] | undefined;

export function filter<T>(array: T[] | undefined, f: (x: T) => boolean): T[] | undefined;

export function filter<T, U extends T>(array: ReadonlyArray<T> | undefined, f: (x: T) => x is U): ReadonlyArray<U> | undefined;

export function filter<T, U extends T>(array: ReadonlyArray<T> | undefined, f: (x: T) => boolean): ReadonlyArray<T> | undefined;

export function filter<T>(array: ReadonlyArray<T> | undefined, f: (x: T) => boolean): ReadonlyArray<T> | undefined {

if (array) {

const len = array.length;

let i = 0;

while (i < len && f(array[i])) i++;

if (i < len) {

const result = array.slice(0, i);

i++;

while (i < len) {

const item = array[i];

if (f(item)) {

result.push(item);

}

i++;

}

return result;

}

}

return array;

}

export function filterMutate<T>(array: T[], f: (x: T, i: number, array: T[]) => boolean): void {

let outIndex = 0;

for (let i = 0; i < array.length; i++) {

if (f(array[i], i, array)) {

array[outIndex] = array[i];

outIndex++;

}

}

array.length = outIndex;

}

export function clear(array: {}[]): void {

array.length = 0;

}

export function map<T, U>(array: ReadonlyArray<T>, f: (x: T, i: number) => U): U[];

export function map<T, U>(array: ReadonlyArray<T> | undefined, f: (x: T, i: number) => U): U[] | undefined;

export function map<T, U>(array: ReadonlyArray<T> | undefined, f: (x: T, i: number) => U): U[] | undefined {

let result: U[] | undefined;

if (array) {

result = [];

for (let i = 0; i < array.length; i++) {

result.push(f(array[i], i));

}

}

return result;

}

export function mapIterator<T, U>(iter: Iterator<T>, mapFn: (x: T) => U): Iterator<U> {

return {

next() {

const iterRes = iter.next();

return iterRes.done ? iterRes : { value: mapFn(iterRes.value), done: false };

}

};

}

// Maps from T to T and avoids allocation if all elements map to themselves

export function sameMap<T>(array: T[], f: (x: T, i: number) => T): T[];

export function sameMap<T>(array: ReadonlyArray<T>, f: (x: T, i: number) => T): ReadonlyArray<T>;

export function sameMap<T>(array: T[] | undefined, f: (x: T, i: number) => T): T[] | undefined;

export function sameMap<T>(array: ReadonlyArray<T> | undefined, f: (x: T, i: number) => T): ReadonlyArray<T> | undefined;

export function sameMap<T>(array: ReadonlyArray<T> | undefined, f: (x: T, i: number) => T): ReadonlyArray<T> | undefined {

if (array) {

for (let i = 0; i < array.length; i++) {

const item = array[i];

const mapped = f(item, i);

if (item !== mapped) {

const result = array.slice(0, i);

result.push(mapped);

for (i++; i < array.length; i++) {

result.push(f(array[i], i));

}

return result;

}

}

}

return array;

}

/**

* Flattens an array containing a mix of array or non-array elements.

*

* @param array The array to flatten.

*/

export function flatten<T>(array: ReadonlyArray<T | ReadonlyArray<T> | undefined>): T[];

export function flatten<T>(array: ReadonlyArray<T | ReadonlyArray<T> | undefined> | undefined): T[] | undefined;

export function flatten<T>(array: ReadonlyArray<T | ReadonlyArray<T> | undefined> | undefined): T[] | undefined {

let result: T[] | undefined;

if (array) {

result = [];

for (const v of array) {

if (v) {

if (isArray(v)) {

addRange(result, v);

}

else {

result.push(v);

}

}

}

}

return result;

}

/**

* Maps an array. If the mapped value is an array, it is spread into the result.

*

* @param array The array to map.

* @param mapfn The callback used to map the result into one or more values.

*/

export function flatMap<T, U>(array: ReadonlyArray<T>, mapfn: (x: T, i: number) => U | ReadonlyArray<U> | undefined): U[];

export function flatMap<T, U>(array: ReadonlyArray<T> | undefined, mapfn: (x: T, i: number) => U | ReadonlyArray<U> | undefined): U[] | undefined;

export function flatMap<T, U>(array: ReadonlyArray<T> | undefined, mapfn: (x: T, i: number) => U | ReadonlyArray<U> | undefined): U[] | undefined {

let result: U[] | undefined;

if (array) {

result = [];

for (let i = 0; i < array.length; i++) {

const v = mapfn(array[i], i);

if (v) {

if (isArray(v)) {

addRange(result, v);

}

else {

result.push(v);

}

}

}

}

return result;

}

export function flatMapIterator<T, U>(iter: Iterator<T>, mapfn: (x: T) => U[] | Iterator<U> | undefined): Iterator<U> {

const first = iter.next();

if (first.done) {

return emptyIterator;

}

let currentIter = getIterator(first.value);

return {

next() {

while (true) {

const currentRes = currentIter.next();

if (!currentRes.done) {

return currentRes;

}

const iterRes = iter.next();

if (iterRes.done) {

return iterRes;

}

currentIter = getIterator(iterRes.value);

}

},

};

function getIterator(x: T): Iterator<U> {

const res = mapfn(x);

return res === undefined ? emptyIterator : isArray(res) ? arrayIterator(res) : res;

}

}

/**

* Maps an array. If the mapped value is an array, it is spread into the result.

* Avoids allocation if all elements map to themselves.

*

* @param array The array to map.

* @param mapfn The callback used to map the result into one or more values.

*/

export function sameFlatMap<T>(array: T[], mapfn: (x: T, i: number) => T | ReadonlyArray<T>): T[];

export function sameFlatMap<T>(array: ReadonlyArray<T>, mapfn: (x: T, i: number) => T | ReadonlyArray<T>): ReadonlyArray<T>;

export function sameFlatMap<T>(array: T[], mapfn: (x: T, i: number) => T | T[]): T[] {

let result: T[] | undefined;

if (array) {

for (let i = 0; i < array.length; i++) {

const item = array[i];

const mapped = mapfn(item, i);

if (result || item !== mapped || isArray(mapped)) {

if (!result) {

result = array.slice(0, i);

}

if (isArray(mapped)) {

addRange(result, mapped);

}

else {

result.push(mapped);

}

}

}

}

return result || array;

}

export function mapAllOrFail<T, U>(array: ReadonlyArray<T>, mapFn: (x: T, i: number) => U | undefined): U[] | undefined {

const result: U[] = [];

for (let i = 0; i < array.length; i++) {

const mapped = mapFn(array[i], i);

if (mapped === undefined) {

return undefined;

}

result.push(mapped);

}

return result;

}

export function mapDefined<T, U>(array: ReadonlyArray<T> | undefined, mapFn: (x: T, i: number) => U | undefined): U[] {

const result: U[] = [];

if (array) {

for (let i = 0; i < array.length; i++) {

const mapped = mapFn(array[i], i);

if (mapped !== undefined) {

result.push(mapped);

}

}

}

return result;

}

export function mapDefinedIterator<T, U>(iter: Iterator<T>, mapFn: (x: T) => U | undefined): Iterator<U> {

return {

next() {

while (true) {

const res = iter.next();

if (res.done) {

return res;

}

const value = mapFn(res.value);

if (value !== undefined) {

return { value, done: false };

}

}

}

};

}

export const emptyIterator: Iterator<never> = { next: () => ({ value: undefined as never, done: true }) };

export function singleIterator<T>(value: T): Iterator<T> {

let done = false;

return {

next() {

const wasDone = done;

done = true;

return wasDone ? { value: undefined as never, done: true } : { value, done: false };

}

};

}

/**

* Maps contiguous spans of values with the same key.

*

* @param array The array to map.

* @param keyfn A callback used to select the key for an element.

* @param mapfn A callback used to map a contiguous chunk of values to a single value.

*/

export function spanMap<T, K, U>(array: ReadonlyArray<T>, keyfn: (x: T, i: number) => K, mapfn: (chunk: T[], key: K, start: number, end: number) => U): U[];

export function spanMap<T, K, U>(array: ReadonlyArray<T> | undefined, keyfn: (x: T, i: number) => K, mapfn: (chunk: T[], key: K, start: number, end: number) => U): U[] | undefined;

export function spanMap<T, K, U>(array: ReadonlyArray<T> | undefined, keyfn: (x: T, i: number) => K, mapfn: (chunk: T[], key: K, start: number, end: number) => U): U[] | undefined {

let result: U[] | undefined;

if (array) {

result = [];

const len = array.length;

let previousKey: K | undefined;

let key: K | undefined;

let start = 0;

let pos = 0;

while (start < len) {

while (pos < len) {

const value = array[pos];

key = keyfn(value, pos);

if (pos === 0) {

previousKey = key;

}

else if (key !== previousKey) {

break;

}

pos++;

}

if (start < pos) {

const v = mapfn(array.slice(start, pos), previousKey!, start, pos);

if (v) {

result.push(v);

}

start = pos;

}

previousKey = key;

pos++;

}

}

return result;

}

export function mapEntries<T, U>(map: ReadonlyMap<T>, f: (key: string, value: T) => [string, U]): Map<U>;

export function mapEntries<T, U>(map: ReadonlyMap<T> | undefined, f: (key: string, value: T) => [string, U]): Map<U> | undefined;

export function mapEntries<T, U>(map: ReadonlyMap<T> | undefined, f: (key: string, value: T) => [string, U]): Map<U> | undefined {

if (!map) {

return undefined;

}

const result = createMap<U>();

map.forEach((value, key) => {

const [newKey, newValue] = f(key, value);

result.set(newKey, newValue);

});

return result;

}

export function some<T>(array: ReadonlyArray<T> | undefined): array is ReadonlyArray<T>;

export function some<T>(array: ReadonlyArray<T> | undefined, predicate: (value: T) => boolean): boolean;

export function some<T>(array: ReadonlyArray<T> | undefined, predicate?: (value: T) => boolean): boolean {

if (array) {

if (predicate) {

for (const v of array) {

if (predicate(v)) {

return true;

}

}

}

else {

return array.length > 0;

}

}

return false;

}

/** Calls the callback with (start, afterEnd) index pairs for each range where 'pred' is true. */

export function getRangesWhere<T>(arr: ReadonlyArray<T>, pred: (t: T) => boolean, cb: (start: number, afterEnd: number) => void): void {

let start: number | undefined;

for (let i = 0; i < arr.length; i++) {

if (pred(arr[i])) {

start = start === undefined ? i : start;

}

else {

if (start !== undefined) {

cb(start, i);

start = undefined;

}

}

}

if (start !== undefined) cb(start, arr.length);

}

export function concatenate<T>(array1: T[], array2: T[]): T[];

export function concatenate<T>(array1: ReadonlyArray<T>, array2: ReadonlyArray<T>): ReadonlyArray<T>;

export function concatenate<T>(array1: T[] | undefined, array2: T[] | undefined): T[];

export function concatenate<T>(array1: ReadonlyArray<T> | undefined, array2: ReadonlyArray<T> | undefined): ReadonlyArray<T>;

export function concatenate<T>(array1: T[], array2: T[]): T[] {

if (!some(array2)) return array1;

if (!some(array1)) return array2;

return [...array1, ...array2];

}

function deduplicateRelational<T>(array: ReadonlyArray<T>, equalityComparer: EqualityComparer<T>, comparer: Comparer<T>) {

// Perform a stable sort of the array. This ensures the first entry in a list of

// duplicates remains the first entry in the result.

const indices = array.map((_, i) => i);

stableSortIndices(array, indices, comparer);

let last = array[indices[0]];

const deduplicated: number[] = [indices[0]];

for (let i = 1; i < indices.length; i++) {

const index = indices[i];

const item = array[index];

if (!equalityComparer(last, item)) {

deduplicated.push(index);

last = item;

}

}

// restore original order

deduplicated.sort();

return deduplicated.map(i => array[i]);

}

function deduplicateEquality<T>(array: ReadonlyArray<T>, equalityComparer: EqualityComparer<T>) {

const result: T[] = [];

for (const item of array) {

pushIfUnique(result, item, equalityComparer);

}

return result;

}

/**

* Deduplicates an unsorted array.

* @param equalityComparer An optional `EqualityComparer` used to determine if two values are duplicates.

* @param comparer An optional `Comparer` used to sort entries before comparison, though the

* result will remain in the original order in `array`.

*/

export function deduplicate<T>(array: ReadonlyArray<T>, equalityComparer?: EqualityComparer<T>, comparer?: Comparer<T>): T[];

export function deduplicate<T>(array: ReadonlyArray<T> | undefined, equalityComparer?: EqualityComparer<T>, comparer?: Comparer<T>): T[] | undefined;

export function deduplicate<T>(array: ReadonlyArray<T> | undefined, equalityComparer: EqualityComparer<T>, comparer?: Comparer<T>): T[] | undefined {

return !array ? undefined :

array.length === 0 ? [] :

array.length === 1 ? array.slice() :

comparer ? deduplicateRelational(array, equalityComparer, comparer) :

deduplicateEquality(array, equalityComparer);

}

/**

* Deduplicates an array that has already been sorted.

*/

function deduplicateSorted<T>(array: ReadonlyArray<T>, comparer: EqualityComparer<T> | Comparer<T>): T[];

function deduplicateSorted<T>(array: ReadonlyArray<T> | undefined, comparer: EqualityComparer<T> | Comparer<T>): T[] | undefined;

function deduplicateSorted<T>(array: ReadonlyArray<T> | undefined, comparer: EqualityComparer<T> | Comparer<T>): T[] | undefined {

if (!array) return undefined;

if (array.length === 0) return [];

let last = array[0];

const deduplicated: T[] = [last];

for (let i = 1; i < array.length; i++) {

const next = array[i];

switch (comparer(next, last)) {

// equality comparison

case true:

// relational comparison

case Comparison.EqualTo:

continue;

case Comparison.LessThan:

// If `array` is sorted, `next` should **never** be less than `last`.

return Debug.fail("Array is unsorted.");

}

deduplicated.push(last = next);

}

return deduplicated;

}

export function insertSorted<T>(array: SortedArray<T>, insert: T, compare: Comparer<T>): void {

if (array.length === 0) {

array.push(insert);

return;

}

const insertIndex = binarySearch(array, insert, identity, compare);

if (insertIndex < 0) {

array.splice(~insertIndex, 0, insert);

}

}

export function sortAndDeduplicate<T>(array: ReadonlyArray<T>, comparer: Comparer<T>, equalityComparer?: EqualityComparer<T>) {

return deduplicateSorted(sort(array, comparer), equalityComparer || comparer);

}

export function arrayIsEqualTo<T>(array1: ReadonlyArray<T> | undefined, array2: ReadonlyArray<T> | undefined, equalityComparer: (a: T, b: T) => boolean = equateValues): boolean {

if (!array1 || !array2) {

return array1 === array2;

}

if (array1.length !== array2.length) {

return false;

}

for (let i = 0; i < array1.length; i++) {

if (!equalityComparer(array1[i], array2[i])) {

return false;

}

}

return true;

}

export function changesAffectModuleResolution(oldOptions: CompilerOptions, newOptions: CompilerOptions): boolean {

return !oldOptions ||

(oldOptions.module !== newOptions.module) ||

(oldOptions.moduleResolution !== newOptions.moduleResolution) ||

(oldOptions.noResolve !== newOptions.noResolve) ||

(oldOptions.target !== newOptions.target) ||

(oldOptions.noLib !== newOptions.noLib) ||

(oldOptions.jsx !== newOptions.jsx) ||

(oldOptions.allowJs !== newOptions.allowJs) ||

(oldOptions.rootDir !== newOptions.rootDir) ||

(oldOptions.configFilePath !== newOptions.configFilePath) ||

(oldOptions.baseUrl !== newOptions.baseUrl) ||

(oldOptions.maxNodeModuleJsDepth !== newOptions.maxNodeModuleJsDepth) ||

!arrayIsEqualTo(oldOptions.lib, newOptions.lib) ||

!arrayIsEqualTo(oldOptions.typeRoots, newOptions.typeRoots) ||

!arrayIsEqualTo(oldOptions.rootDirs, newOptions.rootDirs) ||

!equalOwnProperties(oldOptions.paths, newOptions.paths);

}

/**

* Compacts an array, removing any falsey elements.

*/

export function compact<T>(array: T[]): T[];

export function compact<T>(array: ReadonlyArray<T>): ReadonlyArray<T>;

export function compact<T>(array: T[]): T[] {

let result: T[] | undefined;

if (array) {

for (let i = 0; i < array.length; i++) {

const v = array[i];

if (result || !v) {

if (!result) {

result = array.slice(0, i);

}

if (v) {

result.push(v);

}

}

}

}

return result || array;

}

/**

* Gets the relative complement of `arrayA` with respect to `arrayB`, returning the elements that

* are not present in `arrayA` but are present in `arrayB`. Assumes both arrays are sorted

* based on the provided comparer.

*/

export function relativeComplement<T>(arrayA: T[] | undefined, arrayB: T[] | undefined, comparer: Comparer<T>): T[] | undefined {

if (!arrayB || !arrayA || arrayB.length === 0 || arrayA.length === 0) return arrayB;

const result: T[] = [];

loopB: for (let offsetA = 0, offsetB = 0; offsetB < arrayB.length; offsetB++) {

if (offsetB > 0) {

// Ensure `arrayB` is properly sorted.

Debug.assertGreaterThanOrEqual(comparer(arrayB[offsetB], arrayB[offsetB - 1]), Comparison.EqualTo);

}

loopA: for (const startA = offsetA; offsetA < arrayA.length; offsetA++) {

if (offsetA > startA) {

// Ensure `arrayA` is properly sorted. We only need to perform this check if

// `offsetA` has changed since we entered the loop.

Debug.assertGreaterThanOrEqual(comparer(arrayA[offsetA], arrayA[offsetA - 1]), Comparison.EqualTo);

}

switch (comparer(arrayB[offsetB], arrayA[offsetA])) {

case Comparison.LessThan:

// If B is less than A, B does not exist in arrayA. Add B to the result and

// move to the next element in arrayB without changing the current position

// in arrayA.

result.push(arrayB[offsetB]);

continue loopB;

case Comparison.EqualTo:

// If B is equal to A, B exists in arrayA. Move to the next element in

// arrayB without adding B to the result or changing the current position

// in arrayA.

continue loopB;

case Comparison.GreaterThan:

// If B is greater than A, we need to keep looking for B in arrayA. Move to

// the next element in arrayA and recheck.

continue loopA;

}

}

}

return result;

}

export function sum<T extends Record<K, number>, K extends string>(array: ReadonlyArray<T>, prop: K): number {

let result = 0;

for (const v of array) {

result += v[prop];

}

return result;

}

/**

* Appends a value to an array, returning the array.

*

* @param to The array to which `value` is to be appended. If `to` is `undefined`, a new array

* is created if `value` was appended.

* @param value The value to append to the array. If `value` is `undefined`, nothing is

* appended.

*/

export function append<T>(to: T[], value: T | undefined): T[];

export function append<T>(to: T[] | undefined, value: T): T[];

export function append<T>(to: T[] | undefined, value: T | undefined): T[] | undefined;

export function append<T>(to: Push<T>, value: T | undefined): void;

export function append<T>(to: T[], value: T | undefined): T[] | undefined {

if (value === undefined) return to;

if (to === undefined) return [value];

to.push(value);

return to;

}

/**

* Gets the actual offset into an array for a relative offset. Negative offsets indicate a

* position offset from the end of the array.

*/

function toOffset(array: ReadonlyArray<any>, offset: number) {

return offset < 0 ? array.length + offset : offset;

}

/**

* Appends a range of value to an array, returning the array.

*

* @param to The array to which `value` is to be appended. If `to` is `undefined`, a new array

* is created if `value` was appended.