Skip to content

Commit 555776e

Browse files
author
Andy
authored
Minor cleanups in builder (microsoft#17208)
* Minor cleanups in builder * Use enumerateInsertsAndDeletes
1 parent 240f1f1 commit 555776e

6 files changed

Lines changed: 85 additions & 102 deletions

File tree

‎src/compiler/core.ts‎

Lines changed: 4 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -780,7 +780,7 @@ namespace ts {
780780
/**
781781
* Stable sort of an array. Elements equal to each other maintain their relative position in the array.
782782
*/
783-
export function stableSort<T>(array: ReadonlyArray<T>, comparer: (x: T, y: T) => Comparison = compareValues) {
783+
export function stableSort<T>(array: ReadonlyArray<T>, comparer: Comparer<T> = compareValues) {
784784
return array
785785
.map((_, i) => i) // create array of indices
786786
.sort((x, y) => comparer(array[x], array[y]) || compareValues(x, y)) // sort indices by value then position
@@ -852,14 +852,16 @@ namespace ts {
852852
return result;
853853
}
854854

855+
export type Comparer<T> = (a: T, b: T) => Comparison;
856+
855857
/**
856858
* Performs a binary search, finding the index at which 'value' occurs in 'array'.
857859
* If no such index is found, returns the 2's-complement of first index at which
858860
* number[index] exceeds number.
859861
* @param array A sorted array whose first element must be no larger than number
860862
* @param number The value to be searched for in the array.
861863
*/
862-
export function binarySearch<T>(array: ReadonlyArray<T>, value: T, comparer?: (v1: T, v2: T) => number, offset?: number): number {
864+
export function binarySearch<T>(array: ReadonlyArray<T>, value: T, comparer?: Comparer<T>, offset?: number): number {
863865
if (!array || array.length === 0) {
864866
return -1;
865867
}

‎src/server/builder.ts‎

Lines changed: 15 additions & 72 deletions
Original file line numberDiff line numberDiff line change
@@ -203,57 +203,27 @@ namespace ts.server {
203203
}
204204

205205
class ModuleBuilderFileInfo extends BuilderFileInfo {
206-
references: ModuleBuilderFileInfo[] = [];
207-
referencedBy: ModuleBuilderFileInfo[] = [];
206+
references = createSortedArray<ModuleBuilderFileInfo>();
207+
readonly referencedBy = createSortedArray<ModuleBuilderFileInfo>();
208208
scriptVersionForReferences: string;
209209

210-
static compareFileInfos(lf: ModuleBuilderFileInfo, rf: ModuleBuilderFileInfo): number {
211-
const l = lf.scriptInfo.fileName;
212-
const r = rf.scriptInfo.fileName;
213-
return (l < r ? -1 : (l > r ? 1 : 0));
214-
}
215-
216-
static addToReferenceList(array: ModuleBuilderFileInfo[], fileInfo: ModuleBuilderFileInfo) {
217-
if (array.length === 0) {
218-
array.push(fileInfo);
219-
return;
220-
}
221-
222-
const insertIndex = binarySearch(array, fileInfo, ModuleBuilderFileInfo.compareFileInfos);
223-
if (insertIndex < 0) {
224-
array.splice(~insertIndex, 0, fileInfo);
225-
}
226-
}
227-
228-
static removeFromReferenceList(array: ModuleBuilderFileInfo[], fileInfo: ModuleBuilderFileInfo) {
229-
if (!array || array.length === 0) {
230-
return;
231-
}
232-
233-
if (array[0] === fileInfo) {
234-
array.splice(0, 1);
235-
return;
236-
}
237-
238-
const removeIndex = binarySearch(array, fileInfo, ModuleBuilderFileInfo.compareFileInfos);
239-
if (removeIndex >= 0) {
240-
array.splice(removeIndex, 1);
241-
}
210+
static compareFileInfos(lf: ModuleBuilderFileInfo, rf: ModuleBuilderFileInfo): Comparison {
211+
return compareStrings(lf.scriptInfo.fileName, rf.scriptInfo.fileName);
242212
}
243213

244214
addReferencedBy(fileInfo: ModuleBuilderFileInfo): void {
245-
ModuleBuilderFileInfo.addToReferenceList(this.referencedBy, fileInfo);
215+
insertSorted(this.referencedBy, fileInfo, ModuleBuilderFileInfo.compareFileInfos);
246216
}
247217

248218
removeReferencedBy(fileInfo: ModuleBuilderFileInfo): void {
249-
ModuleBuilderFileInfo.removeFromReferenceList(this.referencedBy, fileInfo);
219+
removeSorted(this.referencedBy, fileInfo, ModuleBuilderFileInfo.compareFileInfos);
250220
}
251221

252222
removeFileReferences() {
253223
for (const reference of this.references) {
254224
reference.removeReferencedBy(this);
255225
}
256-
this.references = [];
226+
this.references = createSortedArray<ModuleBuilderFileInfo>();
257227
}
258228
}
259229

@@ -270,16 +240,13 @@ namespace ts.server {
270240
super.clear();
271241
}
272242

273-
private getReferencedFileInfos(fileInfo: ModuleBuilderFileInfo): ModuleBuilderFileInfo[] {
243+
private getReferencedFileInfos(fileInfo: ModuleBuilderFileInfo): SortedArray<ModuleBuilderFileInfo> {
274244
if (!fileInfo.isExternalModuleOrHasOnlyAmbientExternalModules()) {
275-
return [];
245+
return createSortedArray();
276246
}
277247

278248
const referencedFilePaths = this.project.getReferencedFiles(fileInfo.scriptInfo.path);
279-
if (referencedFilePaths.length > 0) {
280-
return map<Path, ModuleBuilderFileInfo>(referencedFilePaths, f => this.getOrCreateFileInfo(f)).sort(ModuleBuilderFileInfo.compareFileInfos);
281-
}
282-
return [];
249+
return toSortedArray(referencedFilePaths.map(f => this.getOrCreateFileInfo(f)), ModuleBuilderFileInfo.compareFileInfos);
283250
}
284251

285252
protected ensureFileInfoIfInProject(_scriptInfo: ScriptInfo) {
@@ -319,39 +286,15 @@ namespace ts.server {
319286

320287
const newReferences = this.getReferencedFileInfos(fileInfo);
321288
const oldReferences = fileInfo.references;
322-
323-
let oldIndex = 0;
324-
let newIndex = 0;
325-
while (oldIndex < oldReferences.length && newIndex < newReferences.length) {
326-
const oldReference = oldReferences[oldIndex];
327-
const newReference = newReferences[newIndex];
328-
const compare = ModuleBuilderFileInfo.compareFileInfos(oldReference, newReference);
329-
if (compare < 0) {
289+
enumerateInsertsAndDeletes(newReferences, oldReferences,
290+
/*inserted*/ newReference => newReference.addReferencedBy(fileInfo),
291+
/*deleted*/ oldReference => {
330292
// New reference is greater then current reference. That means
331293
// the current reference doesn't exist anymore after parsing. So delete
332294
// references.
333295
oldReference.removeReferencedBy(fileInfo);
334-
oldIndex++;
335-
}
336-
else if (compare > 0) {
337-
// A new reference info. Add it.
338-
newReference.addReferencedBy(fileInfo);
339-
newIndex++;
340-
}
341-
else {
342-
// Equal. Go to next
343-
oldIndex++;
344-
newIndex++;
345-
}
346-
}
347-
// Clean old references
348-
for (let i = oldIndex; i < oldReferences.length; i++) {
349-
oldReferences[i].removeReferencedBy(fileInfo);
350-
}
351-
// Update new references
352-
for (let i = newIndex; i < newReferences.length; i++) {
353-
newReferences[i].addReferencedBy(fileInfo);
354-
}
296+
},
297+
/*compare*/ ModuleBuilderFileInfo.compareFileInfos);
355298

356299
fileInfo.references = newReferences;
357300
fileInfo.scriptVersionForReferences = fileInfo.scriptInfo.getLatestVersion();

‎src/server/project.ts‎

Lines changed: 3 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -554,7 +554,7 @@ namespace ts.server {
554554
for (const sourceFile of this.program.getSourceFiles()) {
555555
this.extractUnresolvedImportsFromSourceFile(sourceFile, result);
556556
}
557-
this.lastCachedUnresolvedImportsList = toSortedReadonlyArray(result);
557+
this.lastCachedUnresolvedImportsList = toSortedArray(result);
558558
}
559559
unresolvedImports = this.lastCachedUnresolvedImportsList;
560560

@@ -783,7 +783,7 @@ namespace ts.server {
783783
// We need to use a set here since the code can contain the same import twice,
784784
// but that will only be one dependency.
785785
// To avoid invernal conversion, the key of the referencedFiles map must be of type Path
786-
const referencedFiles = createMap<boolean>();
786+
const referencedFiles = createMap<true>();
787787
if (sourceFile.imports && sourceFile.imports.length > 0) {
788788
const checker: TypeChecker = this.program.getTypeChecker();
789789
for (const importName of sourceFile.imports) {
@@ -1057,7 +1057,7 @@ namespace ts.server {
10571057
}
10581058

10591059
getExternalFiles(): SortedReadonlyArray<string> {
1060-
return toSortedReadonlyArray(flatMap(this.plugins, plugin => {
1060+
return toSortedArray(flatMap(this.plugins, plugin => {
10611061
if (typeof plugin.getExternalFiles !== "function") return;
10621062
try {
10631063
return plugin.getExternalFiles(this);

‎src/server/types.ts‎

Lines changed: 5 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -20,8 +20,12 @@ declare namespace ts.server {
2020
require?(initialPath: string, moduleName: string): RequireResult;
2121
}
2222

23+
export interface SortedArray<T> extends Array<T> {
24+
" __sortedArrayBrand": any;
25+
}
26+
2327
export interface SortedReadonlyArray<T> extends ReadonlyArray<T> {
24-
" __sortedReadonlyArrayBrand": any;
28+
" __sortedArrayBrand": any;
2529
}
2630

2731
export interface TypingInstallerRequest {

‎src/server/typingsCache.ts‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -110,7 +110,7 @@ namespace ts.server {
110110
this.perProjectCache.set(projectName, {
111111
compilerOptions,
112112
typeAcquisition,
113-
typings: toSortedReadonlyArray(newTypings),
113+
typings: toSortedArray(newTypings),
114114
unresolvedImports,
115115
poisoned: false
116116
});

‎src/server/utilities.ts‎

Lines changed: 57 additions & 23 deletions
Original file line numberDiff line numberDiff line change
@@ -9,7 +9,7 @@ namespace ts.server {
99
verbose
1010
}
1111

12-
export const emptyArray: ReadonlyArray<any> = [];
12+
export const emptyArray: SortedReadonlyArray<never> = createSortedArray<never>();
1313

1414
export interface Logger {
1515
close(): void;
@@ -190,39 +190,45 @@ namespace ts.server {
190190
return `/dev/null/inferredProject${counter}*`;
191191
}
192192

193-
export function toSortedReadonlyArray(arr: string[]): SortedReadonlyArray<string> {
194-
arr.sort();
195-
return <any>arr;
193+
export function createSortedArray<T>(): SortedArray<T> {
194+
return [] as SortedArray<T>;
196195
}
197196

198-
export function enumerateInsertsAndDeletes<T>(a: SortedReadonlyArray<T>, b: SortedReadonlyArray<T>, inserted: (item: T) => void, deleted: (item: T) => void, compare?: (a: T, b: T) => Comparison) {
197+
export function toSortedArray(arr: string[]): SortedArray<string>;
198+
export function toSortedArray<T>(arr: T[], comparer: Comparer<T>): SortedArray<T>;
199+
export function toSortedArray<T>(arr: T[], comparer?: Comparer<T>): SortedArray<T> {
200+
arr.sort(comparer);
201+
return arr as SortedArray<T>;
202+
}
203+
204+
export function enumerateInsertsAndDeletes<T>(newItems: SortedReadonlyArray<T>, oldItems: SortedReadonlyArray<T>, inserted: (newItem: T) => void, deleted: (oldItem: T) => void, compare?: Comparer<T>) {
199205
compare = compare || compareValues;
200-
let aIndex = 0;
201-
let bIndex = 0;
202-
const aLen = a.length;
203-
const bLen = b.length;
204-
while (aIndex < aLen && bIndex < bLen) {
205-
const aItem = a[aIndex];
206-
const bItem = b[bIndex];
207-
const compareResult = compare(aItem, bItem);
206+
let newIndex = 0;
207+
let oldIndex = 0;
208+
const newLen = newItems.length;
209+
const oldLen = oldItems.length;
210+
while (newIndex < newLen && oldIndex < oldLen) {
211+
const newItem = newItems[newIndex];
212+
const oldItem = oldItems[oldIndex];
213+
const compareResult = compare(newItem, oldItem);
208214
if (compareResult === Comparison.LessThan) {
209-
inserted(aItem);
210-
aIndex++;
215+
inserted(newItem);
216+
newIndex++;
211217
}
212218
else if (compareResult === Comparison.GreaterThan) {
213-
deleted(bItem);
214-
bIndex++;
219+
deleted(oldItem);
220+
oldIndex++;
215221
}
216222
else {
217-
aIndex++;
218-
bIndex++;
223+
newIndex++;
224+
oldIndex++;
219225
}
220226
}
221-
while (aIndex < aLen) {
222-
inserted(a[aIndex++]);
227+
while (newIndex < newLen) {
228+
inserted(newItems[newIndex++]);
223229
}
224-
while (bIndex < bLen) {
225-
deleted(b[bIndex++]);
230+
while (oldIndex < oldLen) {
231+
deleted(oldItems[oldIndex++]);
226232
}
227233
}
228234

@@ -273,4 +279,32 @@ namespace ts.server {
273279
}
274280
}
275281
}
282+
283+
export function insertSorted<T>(array: SortedArray<T>, insert: T, compare: Comparer<T>): void {
284+
if (array.length === 0) {
285+
array.push(insert);
286+
return;
287+
}
288+
289+
const insertIndex = binarySearch(array, insert, compare);
290+
if (insertIndex < 0) {
291+
array.splice(~insertIndex, 0, insert);
292+
}
293+
}
294+
295+
export function removeSorted<T>(array: SortedArray<T>, remove: T, compare: Comparer<T>): void {
296+
if (!array || array.length === 0) {
297+
return;
298+
}
299+
300+
if (array[0] === remove) {
301+
array.splice(0, 1);
302+
return;
303+
}
304+
305+
const removeIndex = binarySearch(array, remove, compare);
306+
if (removeIndex >= 0) {
307+
array.splice(removeIndex, 1);
308+
}
309+
}
276310
}

0 commit comments

Comments
 (0)