From 78efe6963f3514ead5af9559d3472547d5924570 Mon Sep 17 00:00:00 2001
From: Timo Tijhof <krinklemail@gmail.com>
Date: Mon, 8 Apr 2019 01:45:48 +0100
Subject: [PATCH] resourceloader: Optimise resolved-check in sortDependencies()

Remove the `resolved.indexOf` check from code outside the
for-loop because it's not needed for correctness. The function
is private, and its result is passed to enqueue() and work()
which already do their own de-duplication.

It was here as optimisation to keep the result fairly small
and avoid needless computation, but this isn't useful in practice
because the input never contains duplicates in production.
There are only two ways to call it:

1. From mw.loader.load(), which we never give duplicates.

2. Recursively from within sortDependencies() itself, which
   is already guarded by exactly the same check.

Move the handling of `baseModules` to the caller so that it
does not need to check it N times for every top-level module on
a page and N more times for every dependency of every dependency
of every such module etc. Instead, do it once before we start.

Also update error "Unknown dependency" to say "Unknown module",
because this function deals both with top-level modules and with
dependencies. In fact, most reports of this error in Phabricator
are for top-level modules, not dependencies.
This makes sense given dependency validation via PHPUnit,
which means such error would be unlikely in prod. An unknown
module, on the other hand, is quite normal (and caught) for
cases where a module or gadget is removed but still queued in
cached HTML.

Change-Id: I944593994a66f1c65c0732d7d1f2d60ed4226e79
---
 resources/src/startup/mediawiki.js            | 31 ++++++-------------
 .../mediawiki/mediawiki.loader.test.js        |  4 +--
 2 files changed, 12 insertions(+), 23 deletions(-)

diff --git a/resources/src/startup/mediawiki.js b/resources/src/startup/mediawiki.js
index 4c20e9dd06..fb4c6ed26f 100644
--- a/resources/src/startup/mediawiki.js
+++ b/resources/src/startup/mediawiki.js
@@ -917,15 +917,14 @@
 			 *  dependencies, such that later modules depend on earlier modules. The array
 			 *  contains the module names. If the array contains already some module names,
 			 *  this function appends its result to the pre-existing array.
-			 * @param {StringSet} [unresolved] Used to track the current dependency
-			 *  chain, and to report loops in the dependency graph.
-			 * @throws {Error} If any unregistered module or a dependency loop is encountered
+			 * @param {StringSet} [unresolved] Used to detect loops in the dependency graph.
+			 * @throws {Error} If an unknown module or a circular dependency is encountered
 			 */
 			function sortDependencies( module, resolved, unresolved ) {
-				var i, deps, skip;
+				var i, skip, deps;
 
 				if ( !( module in registry ) ) {
-					throw new Error( 'Unknown dependency: ' + module );
+					throw new Error( 'Unknown module: ' + module );
 				}
 
 				if ( typeof registry[ module ].skip === 'string' ) {
@@ -939,25 +938,12 @@
 					}
 				}
 
-				if ( resolved.indexOf( module ) !== -1 ) {
-					// Module already resolved; nothing to do
-					return;
-				}
 				// Create unresolved if not passed in
 				if ( !unresolved ) {
 					unresolved = new StringSet();
 				}
 
-				// Add base modules
-				if ( baseModules.indexOf( module ) === -1 ) {
-					for ( i = 0; i < baseModules.length; i++ ) {
-						if ( resolved.indexOf( baseModules[ i ] ) === -1 ) {
-							resolved.push( baseModules[ i ] );
-						}
-					}
-				}
-
-				// Tracks down dependencies
+				// Track down dependencies
 				deps = registry[ module ].dependencies;
 				unresolved.add( module );
 				for ( i = 0; i < deps.length; i++ ) {
@@ -971,6 +957,7 @@
 						sortDependencies( deps[ i ], resolved, unresolved );
 					}
 				}
+
 				resolved.push( module );
 			}
 
@@ -983,7 +970,8 @@
 			 * @throws {Error} If an unregistered module or a dependency loop is encountered
 			 */
 			function resolve( modules ) {
-				var resolved = [],
+				// Always load base modules
+				var resolved = baseModules.slice(),
 					i = 0;
 				for ( ; i < modules.length; i++ ) {
 					sortDependencies( modules[ i ], resolved );
@@ -1001,7 +989,8 @@
 			 */
 			function resolveStubbornly( modules ) {
 				var saved,
-					resolved = [],
+					// Always load base modules
+					resolved = baseModules.slice(),
 					i = 0;
 				for ( ; i < modules.length; i++ ) {
 					saved = resolved.slice();
diff --git a/tests/qunit/suites/resources/mediawiki/mediawiki.loader.test.js b/tests/qunit/suites/resources/mediawiki/mediawiki.loader.test.js
index e17c78d7af..8b3427f93f 100644
--- a/tests/qunit/suites/resources/mediawiki/mediawiki.loader.test.js
+++ b/tests/qunit/suites/resources/mediawiki/mediawiki.loader.test.js
@@ -255,7 +255,7 @@
 		assert.deepEqual(
 			[ {
 				topic: 'resourceloader.exception',
-				error: 'Unknown dependency: test.load.unreg',
+				error: 'Unknown module: test.load.unreg',
 				source: 'resolve'
 			} ],
 			capture
@@ -281,7 +281,7 @@
 		assert.deepEqual(
 			[ {
 				topic: 'resourceloader.exception',
-				error: 'Unknown dependency: test.load.missingdep2',
+				error: 'Unknown module: test.load.missingdep2',
 				source: 'resolve'
 			} ],
 			capture
-- 
2.20.1