Skip to content

Commit bfba32b

Browse files
rbucktonrbuckton
committed
Cleanup, merge microsoft#19475 
1 parent 2443777 commit bfba32b

8 files changed

Lines changed: 132 additions & 55 deletions

File tree

‎src/compiler/core.ts‎

Lines changed: 101 additions & 46 deletions
Original file line numberDiff line numberDiff line change
@@ -159,12 +159,6 @@ namespace ts {
159159
return <Path>getCanonicalFileName(nonCanonicalizedPath);
160160
}
161161

162-
export const enum Comparison {
163-
LessThan = -1,
164-
EqualTo = 0,
165-
GreaterThan = 1
166-
}
167-
168162
export function length(array: ReadonlyArray<any>) {
169163
return array ? array.length : 0;
170164
}
@@ -301,17 +295,33 @@ namespace ts {
301295
Debug.fail();
302296
}
303297

304-
export function contains<T>(array: ReadonlyArray<T>, value: T): boolean {
305-
if (array) {
306-
for (const v of array) {
307-
if (v === value) {
308-
return true;
309-
}
298+
function containsWithoutEqualityComparer<T>(array: ReadonlyArray<T>, value: T) {
299+
for (const v of array) {
300+
if (v === value) {
301+
return true;
310302
}
311303
}
312304
return false;
313305
}
314306

307+
function containsWithEqualityComparer<T>(array: ReadonlyArray<T>, value: T, equalityComparer: EqualityComparer<T>) {
308+
for (const v of array) {
309+
if (equalityComparer(v, value)) {
310+
return true;
311+
}
312+
}
313+
return false;
314+
}
315+
316+
export function contains<T>(array: ReadonlyArray<T>, value: T, equalityComparer?: EqualityComparer<T>): boolean {
317+
if (array) {
318+
return equalityComparer
319+
? containsWithEqualityComparer(array, value, equalityComparer)
320+
: containsWithoutEqualityComparer(array, value);
321+
}
322+
return false;
323+
}
324+
315325
export function indexOf<T>(array: ReadonlyArray<T>, value: T): number {
316326
if (array) {
317327
for (let i = 0; i < array.length; i++) {
@@ -649,21 +659,36 @@ namespace ts {
649659
return [...array1, ...array2];
650660
}
651661

652-
// TODO: fixme (N^2) - add optional comparer so collection can be sorted before deduplication.
653-
export function deduplicate<T>(array: ReadonlyArray<T>, equalityComparer: (a: T, b: T) => boolean = equateValues): T[] {
654-
let result: T[];
655-
if (array) {
656-
result = [];
657-
loop: for (const item of array) {
658-
for (const res of result) {
659-
if (equalityComparer(res, item)) {
660-
continue loop;
661-
}
662+
/**
663+
* Creates a new array with duplicate entries removed.
664+
* @param equalityComparer An optional `EqualityComparer` used to determine if two values are duplicates.
665+
* @param comparer An optional `Comparer` used to sort entries before comparison. If supplied,
666+
* results are returned in the original order found in `array`.
667+
*/
668+
export function deduplicate<T>(array: ReadonlyArray<T>, equalityComparer?: EqualityComparer<T>, comparer?: Comparer<T>): T[] {
669+
if (!array) return undefined;
670+
if (!comparer) return addRangeIfUnique([], array, equalityComparer);
671+
return deduplicateWorker(array, equalityComparer, comparer);
672+
}
673+
674+
function deduplicateWorker<T>(array: ReadonlyArray<T>, equalityComparer: EqualityComparer<T> = equateValues, comparer: Comparer<T>) {
675+
// Perform a stable sort of the array. This ensures the first entry in a list of
676+
// duplicates remains the first entry in the result.
677+
const indices = sequence(0, array.length);
678+
stableSortIndices(array, indices, comparer);
679+
680+
const deduplicated: number[] = [];
681+
loop: for (const sourceIndex of indices) {
682+
for (const targetIndex of deduplicated) {
683+
if (equalityComparer(array[sourceIndex], array[targetIndex])) {
684+
continue loop;
662685
}
663-
result.push(item);
664686
}
687+
deduplicated.push(sourceIndex);
665688
}
666-
return result;
689+
690+
// return deduplicated items in original order
691+
return deduplicated.sort().map(i => array[i]);
667692
}
668693

669694
export function arrayIsEqualTo<T>(array1: ReadonlyArray<T>, array2: ReadonlyArray<T>, equalityComparer: (a: T, b: T) => boolean = equateValues): boolean {
@@ -731,7 +756,7 @@ namespace ts {
731756
* are not present in `arrayA` but are present in `arrayB`. Assumes both arrays are sorted
732757
* based on the provided comparer.
733758
*/
734-
export function relativeComplement<T>(arrayA: T[] | undefined, arrayB: T[] | undefined, comparer: Comparer<T> = compareValues, offsetA = 0, offsetB = 0): T[] | undefined {
759+
export function relativeComplement<T>(arrayA: T[] | undefined, arrayB: T[] | undefined, comparer: Comparer<T>, offsetA = 0, offsetB = 0): T[] | undefined {
735760
if (!arrayB || !arrayA || arrayB.length === 0 || arrayA.length === 0) return arrayB;
736761
const result: T[] = [];
737762
outer: for (; offsetB < arrayB.length; offsetB++) {
@@ -795,19 +820,27 @@ namespace ts {
795820
start = start === undefined ? 0 : toOffset(from, start);
796821
end = end === undefined ? from.length : toOffset(from, end);
797822
for (let i = start; i < end && i < from.length; i++) {
798-
const v = from[i];
799-
if (v !== undefined) {
823+
if (from[i] !== undefined) {
800824
to.push(from[i]);
801825
}
802826
}
803827
return to;
804828
}
805829

830+
function addRangeIfUnique<T>(to: T[], from: ReadonlyArray<T>, equalityComparer?: EqualityComparer<T>): T[] | undefined {
831+
for (let i = 0; i < from.length; i++) {
832+
if (from[i] !== undefined) {
833+
pushIfUnique(to, from[i], equalityComparer);
834+
}
835+
}
836+
return to;
837+
}
838+
806839
/**
807840
* @return Whether the value was added.
808841
*/
809-
export function pushIfUnique<T>(array: T[], toAdd: T): boolean {
810-
if (contains(array, toAdd)) {
842+
export function pushIfUnique<T>(array: T[], toAdd: T, equalityComparer?: EqualityComparer<T>): boolean {
843+
if (contains(array, toAdd, equalityComparer)) {
811844
return false;
812845
}
813846
else {
@@ -819,24 +852,39 @@ namespace ts {
819852
/**
820853
* Unlike `pushIfUnique`, this can take `undefined` as an input, and returns a new array.
821854
*/
822-
export function appendIfUnique<T>(array: T[] | undefined, toAdd: T): T[] {
855+
export function appendIfUnique<T>(array: T[] | undefined, toAdd: T, equalityComparer?: EqualityComparer<T>): T[] {
823856
if (array) {
824-
pushIfUnique(array, toAdd);
857+
pushIfUnique(array, toAdd, equalityComparer);
825858
return array;
826859
}
827860
else {
828861
return [toAdd];
829862
}
830863
}
831864

865+
/**
866+
* Creates an array of integers starting at `from` (inclusive) and ending at `to` (exclusive).
867+
*/
868+
function sequence(from: number, to: number) {
869+
const numbers: number[] = [];
870+
for (let i = from; i < to; i++) {
871+
numbers.push(i);
872+
}
873+
return numbers;
874+
}
875+
876+
function stableSortIndices<T>(array: ReadonlyArray<T>, indices: number[], comparer: Comparer<T>) {
877+
// sort indices by value then position
878+
indices.sort((x, y) => comparer(array[x], array[y]) || compareValues(x, y));
879+
}
880+
832881
/**
833882
* Stable sort of an array. Elements equal to each other maintain their relative position in the array.
834883
*/
835-
export function stableSort<T>(array: ReadonlyArray<T>, comparer: Comparer<T> = compareValues) {
836-
return array
837-
.map((_, i) => i) // create array of indices
838-
.sort((x, y) => comparer(array[x], array[y]) || compareValues(x, y)) // sort indices by value then position
839-
.map(i => array[i]); // get sorted array
884+
export function stableSort<T>(array: ReadonlyArray<T>, comparer: Comparer<T>) {
885+
const indices = sequence(0, array.length);
886+
stableSortIndices(array, indices, comparer);
887+
return indices.map(i => array[i]);
840888
}
841889

842890
export function rangeEquals<T>(array1: ReadonlyArray<T>, array2: ReadonlyArray<T>, pos: number, end: number) {
@@ -914,9 +962,6 @@ namespace ts {
914962
return result;
915963
}
916964

917-
export type Comparer<T> = (a: T, b: T) => Comparison;
918-
export type EqualityComparer<T> = (a: T, b: T) => boolean;
919-
920965
/**
921966
* Performs a binary search, finding the index at which 'value' occurs in 'array'.
922967
* If no such index is found, returns the 2's-complement of first index at which
@@ -1483,7 +1528,7 @@ namespace ts {
14831528
return headChain;
14841529
}
14851530

1486-
function equateValues<T>(a: T, b: T) {
1531+
export function equateValues<T>(a: T, b: T) {
14871532
return a === b;
14881533
}
14891534

@@ -1512,17 +1557,23 @@ namespace ts {
15121557
return equateValues(a, b);
15131558
}
15141559

1515-
/**
1516-
* Compare two values for their order relative to each other.
1517-
*/
1518-
export function compareValues<T>(a: T, b: T) {
1560+
function compareComparableValues(a: string, b: string): Comparison;
1561+
function compareComparableValues(a: number, b: number): Comparison;
1562+
function compareComparableValues(a: string | number, b: string | number) {
15191563
return a === b ? Comparison.EqualTo :
15201564
a === undefined ? Comparison.LessThan :
15211565
b === undefined ? Comparison.GreaterThan :
15221566
a < b ? Comparison.LessThan :
15231567
Comparison.GreaterThan;
15241568
}
15251569

1570+
/**
1571+
* Compare two values for their order relative to each other.
1572+
*/
1573+
export function compareValues(a: number, b: number) {
1574+
return compareComparableValues(a, b);
1575+
}
1576+
15261577
/**
15271578
* Compare two strings using a case-insensitive ordinal comparison.
15281579
*
@@ -1555,7 +1606,7 @@ namespace ts {
15551606
* value of each code-point.
15561607
*/
15571608
export function compareStringsCaseSensitive(a: string, b: string) {
1558-
return compareValues(a, b);
1609+
return compareComparableValues(a, b);
15591610
}
15601611

15611612
/**
@@ -2488,7 +2539,11 @@ namespace ts {
24882539
if (!extraFileExtensions || extraFileExtensions.length === 0 || !needAllExtensions) {
24892540
return needAllExtensions ? allSupportedExtensions : supportedTypeScriptExtensions;
24902541
}
2491-
return deduplicate([...allSupportedExtensions, ...extraFileExtensions.map(e => e.extension)]);
2542+
return deduplicate(
2543+
[...allSupportedExtensions, ...extraFileExtensions.map(e => e.extension)],
2544+
equateStringsCaseSensitive,
2545+
compareStringsCaseSensitive
2546+
);
24922547
}
24932548

24942549
export function hasJavaScriptFileExtension(fileName: string) {

‎src/compiler/types.ts‎

Lines changed: 16 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -36,6 +36,22 @@ namespace ts {
3636
push(...values: T[]): void;
3737
}
3838

39+
/* @internal */
40+
export type EqualityComparer<T> = (a: T, b: T) => boolean;
41+
42+
/* @internal */
43+
export type Comparer<T> = (a: T, b: T) => Comparison;
44+
45+
/* @internal */
46+
export const enum Comparison {
47+
LessThan = -1,
48+
EqualTo = 0,
49+
GreaterThan = 1
50+
}
51+
52+
/* @internal */
53+
export type Selector<T, U> = (v: T) => U;
54+
3955
// branded string type used to store absolute, normalized and canonicalized paths
4056
// arbitrary file name can be converted to Path via toPath function
4157
export type Path = string & { __pathBrand: any };

‎src/server/project.ts‎

Lines changed: 2 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -860,7 +860,8 @@ namespace ts.server {
860860
const scriptInfo = this.projectService.getOrCreateScriptInfoNotOpenedByClient(inserted, this.directoryStructureHost);
861861
scriptInfo.attachToProject(this);
862862
},
863-
removed => this.detachScriptInfoFromProject(removed)
863+
removed => this.detachScriptInfoFromProject(removed),
864+
compareStringsCaseSensitive
864865
);
865866
const elapsed = timestamp() - start;
866867
this.writeLog(`Finishing updateGraphWorker: Project: ${this.getProjectName()} structureChanged: ${hasChanges} Elapsed: ${elapsed}ms`);

‎src/server/session.ts‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -958,7 +958,7 @@ namespace ts.server {
958958
projects,
959959
project => project.getLanguageService().findReferences(file, position),
960960
/*comparer*/ undefined,
961-
/*areEqual (TODO: fixme)*/ undefined
961+
equateValues
962962
);
963963
}
964964

‎src/server/utilities.ts‎

Lines changed: 2 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -288,16 +288,15 @@ namespace ts.server {
288288
return index === 0 || value !== array[index - 1];
289289
}
290290

291-
export function enumerateInsertsAndDeletes<T>(newItems: SortedReadonlyArray<T>, oldItems: SortedReadonlyArray<T>, inserted: (newItem: T) => void, deleted: (oldItem: T) => void, compare?: Comparer<T>) {
292-
compare = compare || compareValues;
291+
export function enumerateInsertsAndDeletes<T>(newItems: SortedReadonlyArray<T>, oldItems: SortedReadonlyArray<T>, inserted: (newItem: T) => void, deleted: (oldItem: T) => void, comparer: Comparer<T>) {
293292
let newIndex = 0;
294293
let oldIndex = 0;
295294
const newLen = newItems.length;
296295
const oldLen = oldItems.length;
297296
while (newIndex < newLen && oldIndex < oldLen) {
298297
const newItem = newItems[newIndex];
299298
const oldItem = oldItems[oldIndex];
300-
const compareResult = compare(newItem, oldItem);
299+
const compareResult = comparer(newItem, oldItem);
301300
if (compareResult === Comparison.LessThan) {
302301
inserted(newItem);
303302
newIndex++;

‎src/services/jsTyping.ts‎

Lines changed: 4 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -115,7 +115,10 @@ namespace ts.JsTyping {
115115

116116
// add typings for unresolved imports
117117
if (unresolvedImports) {
118-
const module = deduplicate(unresolvedImports.map(moduleId => nodeCoreModules.has(moduleId) ? "node" : moduleId));
118+
const module = deduplicate(
119+
unresolvedImports.map(moduleId => nodeCoreModules.has(moduleId) ? "node" : moduleId),
120+
equateStringsCaseSensitive,
121+
compareStringsCaseSensitive);
119122
addInferredTypings(module, "Inferred typings from unresolved imports");
120123
}
121124
// Add the cached typing locations for inferred typings that are already installed

‎src/services/pathCompletions.ts‎

Lines changed: 5 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -44,7 +44,10 @@ namespace ts.Completions.PathCompletions {
4444
containsPath(rootDirectory, scriptPath, basePath, ignoreCase) ? scriptPath.substr(rootDirectory.length) : undefined);
4545

4646
// Now find a path for each potential directory that is to be merged with the one containing the script
47-
return deduplicate(map(rootDirs, rootDirectory => combinePaths(rootDirectory, relativeDirectory)));
47+
return deduplicate(
48+
map(rootDirs, rootDirectory => combinePaths(rootDirectory, relativeDirectory)),
49+
equateStringsCaseSensitive,
50+
compareStringsCaseSensitive);
4851
}
4952

5053
function getCompletionEntriesForDirectoryFragmentWithRootDirs(rootDirs: string[], fragment: string, scriptPath: string, extensions: ReadonlyArray<string>, includeExtensions: boolean, span: TextSpan, compilerOptions: CompilerOptions, host: LanguageServiceHost, exclude?: string): CompletionEntry[] {
@@ -271,7 +274,7 @@ namespace ts.Completions.PathCompletions {
271274
}
272275
}
273276

274-
return deduplicate(nonRelativeModuleNames);
277+
return deduplicate(nonRelativeModuleNames, equateStringsCaseSensitive, compareStringsCaseSensitive);
275278
}
276279

277280
export function getTripleSlashReferenceCompletion(sourceFile: SourceFile, position: number, compilerOptions: CompilerOptions, host: LanguageServiceHost): CompletionInfo {

‎src/services/services.ts‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -1757,7 +1757,7 @@ namespace ts {
17571757
const newLineCharacter = getNewLineOrDefaultFromHost(host);
17581758
const rulesProvider = getRuleProvider(formatOptions);
17591759

1760-
return flatMap(deduplicate(errorCodes), errorCode => {
1760+
return flatMap(deduplicate(errorCodes, equateValues, compareValues), errorCode => {
17611761
cancellationToken.throwIfCancellationRequested();
17621762
return codefix.getFixes({ errorCode, sourceFile, span, program, newLineCharacter, host, cancellationToken, rulesProvider });
17631763
});

0 commit comments

Comments
 (0)