Use unordered removal where possible

Andy Hanson · Andy Hanson · commit d6aa65daf10c · 2016-08-22T06:18:31.000-07:00
diff --git a/src/compiler/checker.ts b/src/compiler/checker.ts
@@ -5336,7 +5336,7 @@ namespace ts {
             while (i > 0) {
                 i--;
                 if (isSubtypeOfAny(types[i], types)) {
-                    removeItemAt(types, i);
+                    removeItemAtPreservingOrder(types, i);
                 }
             }
         }
diff --git a/src/compiler/core.ts b/src/compiler/core.ts
@@ -1395,31 +1395,37 @@ namespace ts {
     }
 
     /** Remove an item from an array, moving everything to its right one space left. */
-    export function removeItemAt<T>(array: T[], index: number): void {
+    export function removeItemAtPreservingOrder<T>(array: T[], index: number): void {
         // This seems to be faster than either `array.splice(i, 1)` or `array.copyWithin(i, i+ 1)`.
         for (let i = index; i < array.length - 1; i++) {
             array[i] = array[i + 1];
         }
         array.pop();
     }
 
+    export function unorderedRemoveItemAt<T>(array: T[], index: number): void {
+        // Fill in the "hole" left at `index`.
+        array[index] = array[array.length - 1];
+        array.pop();
+    }
+
     /** Remove the *first* occurrence of `item` from the array. */
-    export function removeItem<T>(item: T, array: T[]): void {
-        removeFirstItemWhere(array, element => element === item);
+    export function unorderedRemoveItem<T>(item: T, array: T[]): void {
+        unorderedRemoveFirstItemWhere(array, element => element === item);
     }
 
     /** Remove the *first* element satisfying `predicate`. */
-    export function removeFirstItemWhere<T>(array: T[], predicate: (element: T) => boolean): void {
+    export function unorderedRemoveFirstItemWhere<T>(array: T[], predicate: (element: T) => boolean): void {
         for (let i = 0; i < array.length; i++) {
             if (predicate(array[i])) {
-                removeItemAt(array, i);
+                unorderedRemoveItemAt(array, i);
                 break;
             }
         }
     }
 
-    export function createGetCanonicalFileName(useCaseSensitivefileNames: boolean): (fileName: string) => string {
-        return useCaseSensitivefileNames
+    export function createGetCanonicalFileName(useCaseSensitiveFileNames: boolean): (fileName: string) => string {
+        return useCaseSensitiveFileNames
             ? ((fileName) => fileName)
             : ((fileName) => fileName.toLowerCase());
     }
diff --git a/src/compiler/sys.ts b/src/compiler/sys.ts
@@ -285,7 +285,7 @@ namespace ts {
                 function removeFileWatcherCallback(filePath: string, callback: FileWatcherCallback) {
                     const callbacks = fileWatcherCallbacks[filePath];
                     if (callbacks) {
-                        removeItem(callback, callbacks);
+                        unorderedRemoveItem(callback, callbacks);
                         if (callbacks.length === 0) {
                             delete fileWatcherCallbacks[filePath];
                         }
diff --git a/src/compiler/tsc.ts b/src/compiler/tsc.ts
@@ -490,7 +490,7 @@ namespace ts {
             sourceFile.fileWatcher.close();
             sourceFile.fileWatcher = undefined;
             if (removed) {
-                removeItem(sourceFile.fileName, rootFileNames);
+                unorderedRemoveItem(sourceFile.fileName, rootFileNames);
             }
             startTimerForRecompilation();
         }
diff --git a/src/harness/harness.ts b/src/harness/harness.ts
@@ -1558,7 +1558,7 @@ namespace Harness {
                     tsConfig.options.configFilePath = data.name;
 
                     // delete entry from the list
-                    ts.removeItemAt(testUnitData, i);
+                    ts.removeItemAtPreservingOrder(testUnitData, i);
 
                     break;
                 }
diff --git a/src/harness/unittests/tsserverProjectSystem.ts b/src/harness/unittests/tsserverProjectSystem.ts
@@ -214,7 +214,7 @@ namespace ts {
                 referenceCount: 0,
                 directoryName,
                 close: () => {
-                    removeFirstItemWhere(callbacks, cb => cb.cb === callback);
+                    unorderedRemoveFirstItemWhere(callbacks, cb => cb.cb === callback);
                     if (!callbacks.length) {
                         delete this.watchedDirectories[path];
                     }
@@ -248,7 +248,7 @@ namespace ts {
             callbacks.push(callback);
             return {
                 close: () => {
-                    removeItem(callback, callbacks);
+                    unorderedRemoveItem(callback, callbacks);
                     if (!callbacks.length) {
                         delete this.watchedFiles[path];
                     }
@@ -263,7 +263,7 @@ namespace ts {
         };
         readonly clearTimeout = (timeoutId: any): void => {
             if (typeof timeoutId === "number") {
-                removeItemAt(this.callbackQueue, timeoutId);
+                unorderedRemoveItemAt(this.callbackQueue, timeoutId);
             }
         };
 
diff --git a/src/server/editorServices.ts b/src/server/editorServices.ts
@@ -275,7 +275,7 @@ namespace ts.server {
         removeRoot(info: ScriptInfo) {
             if (this.filenameToScript.contains(info.path)) {
                 this.filenameToScript.remove(info.path);
-                removeItem(info, this.roots);
+                unorderedRemoveItem(info, this.roots);
                 this.resolvedModuleNames.remove(info.path);
                 this.resolvedTypeReferenceDirectives.remove(info.path);
             }
@@ -849,7 +849,7 @@ namespace ts.server {
                 project.directoryWatcher.close();
                 forEachValue(project.directoriesWatchedForWildcards, watcher => { watcher.close(); });
                 delete project.directoriesWatchedForWildcards;
-                removeItem(project, this.configuredProjects);
+                unorderedRemoveItem(project, this.configuredProjects);
             }
             else {
                 for (const directory of project.directoriesWatchedForTsconfig) {
@@ -861,7 +861,7 @@ namespace ts.server {
                         delete project.projectService.directoryWatchersForTsconfig[directory];
                     }
                 }
-                removeItem(project, this.inferredProjects);
+                unorderedRemoveItem(project, this.inferredProjects);
             }
 
             const fileNames = project.getFileNames();
@@ -986,7 +986,7 @@ namespace ts.server {
                 }
             }
             else {
-                removeItem(info, this.openFilesReferenced);
+                unorderedRemoveItem(info, this.openFilesReferenced);
             }
             info.close();
         }
@@ -1496,13 +1496,13 @@ namespace ts.server {
                             // openFileRoots or openFileReferenced.
                             if (info.isOpen) {
                                 if (this.openFileRoots.indexOf(info) >= 0) {
-                                    removeItem(info, this.openFileRoots);
+                                    unorderedRemoveItem(info, this.openFileRoots);
                                     if (info.defaultProject && !info.defaultProject.isConfiguredProject()) {
                                         this.removeProject(info.defaultProject);
                                     }
                                 }
                                 if (this.openFilesReferenced.indexOf(info) >= 0) {
-                                    removeItem(info, this.openFilesReferenced);
+                                    unorderedRemoveItem(info, this.openFilesReferenced);
                                 }
                                 this.openFileRootsConfigured.push(info);
                                 info.defaultProject = project;

Original file line number	Diff line number	Diff line change
`@@ -5336,7 +5336,7 @@ namespace ts {`
`5336`	`5336`	`while (i > 0) {`
`5337`	`5337`	`i--;`
`5338`	`5338`	`if (isSubtypeOfAny(types[i], types)) {`
`5339`		`- removeItemAt(types, i);`
	`5339`	`+ removeItemAtPreservingOrder(types, i);`
`5340`	`5340`	`}`
`5341`	`5341`	`}`
`5342`	`5342`	`}`
Original file line number	Diff line number	Diff line change
`@@ -1395,31 +1395,37 @@ namespace ts {`
`1395`	`1395`	`}`
`1396`	`1396`
`1397`	`1397`	`/** Remove an item from an array, moving everything to its right one space left. */`
`1398`		`- export function removeItemAt<T>(array: T[], index: number): void {`
	`1398`	`+ export function removeItemAtPreservingOrder<T>(array: T[], index: number): void {`
`1399`	`1399`	// This seems to be faster than either `array.splice(i, 1)` or `array.copyWithin(i, i+ 1)`.
`1400`	`1400`	`for (let i = index; i < array.length - 1; i++) {`
`1401`	`1401`	`array[i] = array[i + 1];`
`1402`	`1402`	`}`
`1403`	`1403`	`array.pop();`
`1404`	`1404`	`}`
`1405`	`1405`
	`1406`	`+ export function unorderedRemoveItemAt<T>(array: T[], index: number): void {`
	`1407`	+ // Fill in the "hole" left at `index`.
	`1408`	`+ array[index] = array[array.length - 1];`
	`1409`	`+ array.pop();`
	`1410`	`+ }`
	`1411`	`+`
`1406`	`1412`	/** Remove the first occurrence of `item` from the array. */
`1407`		`- export function removeItem<T>(item: T, array: T[]): void {`
`1408`		`- removeFirstItemWhere(array, element => element === item);`
	`1413`	`+ export function unorderedRemoveItem<T>(item: T, array: T[]): void {`
	`1414`	`+ unorderedRemoveFirstItemWhere(array, element => element === item);`
`1409`	`1415`	`}`
`1410`	`1416`
`1411`	`1417`	/** Remove the first element satisfying `predicate`. */
`1412`		`- export function removeFirstItemWhere<T>(array: T[], predicate: (element: T) => boolean): void {`
	`1418`	`+ export function unorderedRemoveFirstItemWhere<T>(array: T[], predicate: (element: T) => boolean): void {`
`1413`	`1419`	`for (let i = 0; i < array.length; i++) {`
`1414`	`1420`	`if (predicate(array[i])) {`
`1415`		`- removeItemAt(array, i);`
	`1421`	`+ unorderedRemoveItemAt(array, i);`
`1416`	`1422`	`break;`
`1417`	`1423`	`}`
`1418`	`1424`	`}`
`1419`	`1425`	`}`
`1420`	`1426`
`1421`		`- export function createGetCanonicalFileName(useCaseSensitivefileNames: boolean): (fileName: string) => string {`
`1422`		`- return useCaseSensitivefileNames`
	`1427`	`+ export function createGetCanonicalFileName(useCaseSensitiveFileNames: boolean): (fileName: string) => string {`
	`1428`	`+ return useCaseSensitiveFileNames`
`1423`	`1429`	`? ((fileName) => fileName)`
`1424`	`1430`	`: ((fileName) => fileName.toLowerCase());`
`1425`	`1431`	`}`
Original file line number	Diff line number	Diff line change
`@@ -285,7 +285,7 @@ namespace ts {`
`285`	`285`	`function removeFileWatcherCallback(filePath: string, callback: FileWatcherCallback) {`
`286`	`286`	`const callbacks = fileWatcherCallbacks[filePath];`
`287`	`287`	`if (callbacks) {`
`288`		`- removeItem(callback, callbacks);`
	`288`	`+ unorderedRemoveItem(callback, callbacks);`
`289`	`289`	`if (callbacks.length === 0) {`
`290`	`290`	`delete fileWatcherCallbacks[filePath];`
`291`	`291`	`}`
Original file line number	Diff line number	Diff line change
`@@ -490,7 +490,7 @@ namespace ts {`
`490`	`490`	`sourceFile.fileWatcher.close();`
`491`	`491`	`sourceFile.fileWatcher = undefined;`
`492`	`492`	`if (removed) {`
`493`		`- removeItem(sourceFile.fileName, rootFileNames);`
	`493`	`+ unorderedRemoveItem(sourceFile.fileName, rootFileNames);`
`494`	`494`	`}`
`495`	`495`	`startTimerForRecompilation();`
`496`	`496`	`}`
Original file line number	Diff line number	Diff line change
`@@ -1558,7 +1558,7 @@ namespace Harness {`
`1558`	`1558`	`tsConfig.options.configFilePath = data.name;`
`1559`	`1559`
`1560`	`1560`	`// delete entry from the list`
`1561`		`- ts.removeItemAt(testUnitData, i);`
	`1561`	`+ ts.removeItemAtPreservingOrder(testUnitData, i);`
`1562`	`1562`
`1563`	`1563`	`break;`
`1564`	`1564`	`}`
Original file line number	Diff line number	Diff line change
`@@ -275,7 +275,7 @@ namespace ts.server {`
`275`	`275`	`removeRoot(info: ScriptInfo) {`
`276`	`276`	`if (this.filenameToScript.contains(info.path)) {`
`277`	`277`	`this.filenameToScript.remove(info.path);`
`278`		`- removeItem(info, this.roots);`
	`278`	`+ unorderedRemoveItem(info, this.roots);`
`279`	`279`	`this.resolvedModuleNames.remove(info.path);`
`280`	`280`	`this.resolvedTypeReferenceDirectives.remove(info.path);`
`281`	`281`	`}`
`@@ -849,7 +849,7 @@ namespace ts.server {`
`849`	`849`	`project.directoryWatcher.close();`
`850`	`850`	`forEachValue(project.directoriesWatchedForWildcards, watcher => { watcher.close(); });`
`851`	`851`	`delete project.directoriesWatchedForWildcards;`
`852`		`- removeItem(project, this.configuredProjects);`
	`852`	`+ unorderedRemoveItem(project, this.configuredProjects);`
`853`	`853`	`}`
`854`	`854`	`else {`
`855`	`855`	`for (const directory of project.directoriesWatchedForTsconfig) {`
`@@ -861,7 +861,7 @@ namespace ts.server {`
`861`	`861`	`delete project.projectService.directoryWatchersForTsconfig[directory];`
`862`	`862`	`}`
`863`	`863`	`}`
`864`		`- removeItem(project, this.inferredProjects);`
	`864`	`+ unorderedRemoveItem(project, this.inferredProjects);`
`865`	`865`	`}`
`866`	`866`
`867`	`867`	`const fileNames = project.getFileNames();`
`@@ -986,7 +986,7 @@ namespace ts.server {`
`986`	`986`	`}`
`987`	`987`	`}`
`988`	`988`	`else {`
`989`		`- removeItem(info, this.openFilesReferenced);`
	`989`	`+ unorderedRemoveItem(info, this.openFilesReferenced);`
`990`	`990`	`}`
`991`	`991`	`info.close();`
`992`	`992`	`}`
`@@ -1496,13 +1496,13 @@ namespace ts.server {`
`1496`	`1496`	`// openFileRoots or openFileReferenced.`
`1497`	`1497`	`if (info.isOpen) {`
`1498`	`1498`	`if (this.openFileRoots.indexOf(info) >= 0) {`
`1499`		`- removeItem(info, this.openFileRoots);`
	`1499`	`+ unorderedRemoveItem(info, this.openFileRoots);`
`1500`	`1500`	`if (info.defaultProject && !info.defaultProject.isConfiguredProject()) {`
`1501`	`1501`	`this.removeProject(info.defaultProject);`
`1502`	`1502`	`}`
`1503`	`1503`	`}`
`1504`	`1504`	`if (this.openFilesReferenced.indexOf(info) >= 0) {`
`1505`		`- removeItem(info, this.openFilesReferenced);`
	`1505`	`+ unorderedRemoveItem(info, this.openFilesReferenced);`
`1506`	`1506`	`}`
`1507`	`1507`	`this.openFileRootsConfigured.push(info);`
`1508`	`1508`	`info.defaultProject = project;`