Issue #618 - Keep track of which modules in a graph have been fetched using a visited set

Ref: BZ 1365187

4 files changed, 92 insertions, 72 deletions

diff --git a/dom/script/ModuleLoadRequest.cpp b/dom/script/ModuleLoadRequest.cpp
index a12fcb162..a75a922e2 100644
--- a/dom/script/ModuleLoadRequest.cpp
+++ b/dom/script/ModuleLoadRequest.cpp
@@ -17,26 +17,48 @@ NS_INTERFACE_MAP_END_INHERITING(ScriptLoadRequest)
 NS_IMPL_CYCLE_COLLECTION_INHERITED(ModuleLoadRequest, ScriptLoadRequest,
                                    mBaseURL,
                                    mLoader,
-                                   mParent,
                                    mModuleScript,
                                    mImports)
 
 NS_IMPL_ADDREF_INHERITED(ModuleLoadRequest, ScriptLoadRequest)
 NS_IMPL_RELEASE_INHERITED(ModuleLoadRequest, ScriptLoadRequest)
 
-ModuleLoadRequest::ModuleLoadRequest(nsIScriptElement* aElement,
+ModuleLoadRequest::ModuleLoadRequest(nsIURI* aURI,
+                                     nsIScriptElement* aElement,
                                      uint32_t aVersion,
                                      CORSMode aCORSMode,
                                      const SRIMetadata &aIntegrity,
                                      ScriptLoader* aLoader)
   : ScriptLoadRequest(ScriptKind::Module,
+                      aURI,
                       aElement,
                       aVersion,
                       aCORSMode,
                       aIntegrity),
     mIsTopLevel(true),
-    mLoader(aLoader)
-{}
+    mLoader(aLoader),
+    mVisitedSet(new VisitedURLSet())
+{
+  mVisitedSet->PutEntry(aURI);
+}
+
+ModuleLoadRequest::ModuleLoadRequest(nsIURI* aURI,
+                                     ModuleLoadRequest* aParent)
+  : ScriptLoadRequest(ScriptKind::Module,
+                      aURI,
+                      aParent->mElement,
+                      aParent->mJSVersion,
+                      aParent->mCORSMode,
+                      aParent->mIntegrity),
+    mIsTopLevel(false),
+    mLoader(aParent->mLoader),
+    mVisitedSet(aParent->mVisitedSet)
+{
+  MOZ_ASSERT(mVisitedSet->Contains(aURI));
+
+  mIsInline = false;
+  mReferrerPolicy = aParent->mReferrerPolicy;
+}
 
 void ModuleLoadRequest::Cancel()
 {
@@ -132,8 +154,7 @@ ModuleLoadRequest::LoadFinished()
 {
   mLoader->ProcessLoadedModuleTree(this);
   mLoader = nullptr;
-  mParent = nullptr;
 }
 
 } // dom namespace
-} // mozilla namespace
\ No newline at end of file
+} // mozilla namespace
diff --git a/dom/script/ModuleLoadRequest.h b/dom/script/ModuleLoadRequest.h
index 7b06dd2cf..2e9652881 100644
--- a/dom/script/ModuleLoadRequest.h
+++ b/dom/script/ModuleLoadRequest.h
@@ -8,6 +8,7 @@
 #define mozilla_dom_ModuleLoadRequest_h
 
 #include "mozilla/dom/ScriptLoader.h"
+#include "nsURIHashKey.h"
 #include "mozilla/MozPromise.h"
 
 namespace mozilla {
@@ -16,6 +17,16 @@ namespace dom {
 class ModuleScript;
 class ScriptLoader;
 
+// A reference counted set of URLs we have visited in the process of loading a
+// module graph.
+class VisitedURLSet : public nsTHashtable<nsURIHashKey>
+{
+  NS_INLINE_DECL_REFCOUNTING(VisitedURLSet)
+
+private:
+  ~VisitedURLSet() = default;
+};
+
 // A load request for a module, created for every top level module script and
 // every module import. Load request can share a ModuleScript if there are
 // multiple imports of the same module.
@@ -31,12 +42,18 @@ public:
   NS_DECL_ISUPPORTS_INHERITED
   NS_DECL_CYCLE_COLLECTION_CLASS_INHERITED(ModuleLoadRequest, ScriptLoadRequest)
 
-  ModuleLoadRequest(nsIScriptElement* aElement,
+  // Create a top-level module load request.
+  ModuleLoadRequest(nsIURI* aURI,
+                    nsIScriptElement* aElement,
                     uint32_t aVersion,
                     CORSMode aCORSMode,
                     const SRIMetadata& aIntegrity,
                     ScriptLoader* aLoader);
 
+  // Create a module load request for an imported module.
+  ModuleLoadRequest(nsIURI* aURI,
+                    ModuleLoadRequest* aParent);
+
   bool IsTopLevel() const {
     return mIsTopLevel;
   }
@@ -55,7 +72,7 @@ private:
 
 public:
   // Is this a request for a top level module script or an import?
-  bool mIsTopLevel;
+  const bool mIsTopLevel;
 
   // The base URL used for resolving relative module imports.
   nsCOMPtr<nsIURI> mBaseURL;
@@ -64,10 +81,6 @@ public:
   // finishes.
   RefPtr<ScriptLoader> mLoader;
 
-  // The importing module, or nullptr for top level module scripts.  Used to
-  // implement the ancestor list checked when fetching module dependencies.
-  RefPtr<ModuleLoadRequest> mParent;
-
   // Set to a module script object after a successful load or nullptr on
   // failure.
   RefPtr<ModuleScript> mModuleScript;
@@ -79,9 +92,13 @@ public:
 
   // Array of imported modules.
   nsTArray<RefPtr<ModuleLoadRequest>> mImports;
+
+  // Set of module URLs visited while fetching the module graph this request is
+  // part of.
+  RefPtr<VisitedURLSet> mVisitedSet;
 };
 
 } // dom namespace
 } // mozilla namespace
 
-#endif // mozilla_dom_ModuleLoadRequest_h
\ No newline at end of file
+#endif // mozilla_dom_ModuleLoadRequest_h
diff --git a/dom/script/ScriptLoader.cpp b/dom/script/ScriptLoader.cpp
index 7d5a19faf..7a3cd8fe3 100644
--- a/dom/script/ScriptLoader.cpp
+++ b/dom/script/ScriptLoader.cpp
@@ -501,7 +501,7 @@ ScriptLoader::ProcessFetchedModuleSource(ModuleLoadRequest* aRequest)
 }
 
 static nsresult
-ResolveRequestedModules(ModuleLoadRequest* aRequest, nsCOMArray<nsIURI>& aUrls);
+ResolveRequestedModules(ModuleLoadRequest* aRequest, nsCOMArray<nsIURI>* aUrlsOut);
 
 nsresult
 ScriptLoader::CreateModuleScript(ModuleLoadRequest* aRequest)
@@ -577,8 +577,7 @@ ScriptLoader::CreateModuleScript(ModuleLoadRequest* aRequest)
 
     // Validate requested modules and treat failure to resolve module specifiers
     // the same as a parse error.
-    nsCOMArray<nsIURI> urls;
-    rv = ResolveRequestedModules(aRequest, urls);
+    rv = ResolveRequestedModules(aRequest, nullptr);
     if (NS_FAILED(rv)) {
       aRequest->ModuleErrored();
       return NS_OK;
@@ -665,33 +664,7 @@ ResolveModuleSpecifier(ModuleScript* aScript,
 }
 
 static nsresult
-RequestedModuleIsInAncestorList(ModuleLoadRequest* aRequest, nsIURI* aURL, bool* aResult)
-{
-  const size_t ImportDepthLimit = 100;
-
-  *aResult = false;
-  size_t depth = 0;
-  while (aRequest) {
-    if (depth++ == ImportDepthLimit) {
-      return NS_ERROR_FAILURE;
-    }
-
-    bool equal;
-    nsresult rv = aURL->Equals(aRequest->mURI, &equal);
-    NS_ENSURE_SUCCESS(rv, rv);
-    if (equal) {
-      *aResult = true;
-      return NS_OK;
-    }
-
-    aRequest = aRequest->mParent;
-  }
-
-  return NS_OK;
-}
-
-static nsresult
-ResolveRequestedModules(ModuleLoadRequest* aRequest, nsCOMArray<nsIURI> &aUrls)
+ResolveRequestedModules(ModuleLoadRequest* aRequest, nsCOMArray<nsIURI>* aUrlsOut)
 {
   ModuleScript* ms = aRequest->mModuleScript;
 
@@ -728,11 +701,8 @@ ResolveRequestedModules(ModuleLoadRequest* aRequest, nsCOMArray<nsIURI> &aUrls)
       return NS_ERROR_FAILURE;
     }
 
-    bool isAncestor;
-    nsresult rv = RequestedModuleIsInAncestorList(aRequest, uri, &isAncestor);
-    NS_ENSURE_SUCCESS(rv, rv);
-    if (!isAncestor) {
-      aUrls.AppendElement(uri.forget());
+    if (aUrlsOut) {
+      aUrlsOut->AppendElement(uri.forget());
     }
   }
 
@@ -746,17 +716,33 @@ ScriptLoader::StartFetchingModuleDependencies(ModuleLoadRequest* aRequest)
   MOZ_ASSERT(!aRequest->mModuleScript->HasParseError());
   MOZ_ASSERT(!aRequest->IsReadyToRun());
 
+  auto visitedSet = aRequest->mVisitedSet;
+  MOZ_ASSERT(visitedSet->Contains(aRequest->mURI));
+
   aRequest->mProgress = ModuleLoadRequest::Progress::FetchingImports;
 
   nsCOMArray<nsIURI> urls;
-  nsresult rv = ResolveRequestedModules(aRequest, urls);
+  nsresult rv = ResolveRequestedModules(aRequest, &urls);
   if (NS_FAILED(rv)) {
     aRequest->ModuleErrored();
     return;
   }
 
-  if (urls.Length() == 0) {
-    // There are no descendents to load so this request is ready.
+  // Remove already visited URLs from the list. Put unvisited URLs into the
+  // visited set.
+  int32_t i = 0;
+  while (i < urls.Count()) {
+    nsIURI* url = urls[i];
+    if (visitedSet->Contains(url)) {
+      urls.RemoveObjectAt(i);
+    } else {
+      visitedSet->PutEntry(url);
+      i++;
+    }
+  }
+
+  if (urls.Count() == 0) {
+    // There are no descendants to load so this request is ready.
     aRequest->DependenciesLoaded();
     return;
   }
@@ -779,21 +765,14 @@ ScriptLoader::StartFetchingModuleDependencies(ModuleLoadRequest* aRequest)
 }
 
 RefPtr<GenericPromise>
-ScriptLoader::StartFetchingModuleAndDependencies(ModuleLoadRequest* aRequest,
+ScriptLoader::StartFetchingModuleAndDependencies(ModuleLoadRequest* aParent,
                                                  nsIURI* aURI)
 {
   MOZ_ASSERT(aURI);
 
-  RefPtr<ModuleLoadRequest> childRequest =
-    new ModuleLoadRequest(aRequest->mElement, aRequest->mJSVersion,
-                          aRequest->mCORSMode, aRequest->mIntegrity, this);
+  RefPtr<ModuleLoadRequest> childRequest = new ModuleLoadRequest(aURI, aParent);
 
-  childRequest->mIsTopLevel = false;
-  childRequest->mURI = aURI;
-  childRequest->mIsInline = false;
-  childRequest->mReferrerPolicy = aRequest->mReferrerPolicy;
-  childRequest->mParent = aRequest;
-  aRequest->mImports.AppendElement(childRequest);
+  aParent->mImports.AppendElement(childRequest);
 
   RefPtr<GenericPromise> ready = childRequest->mReady.Ensure(__func__);
 
@@ -1201,17 +1180,19 @@ CSPAllowsInlineScript(nsIScriptElement *aElement, nsIDocument *aDocument)
 
 ScriptLoadRequest*
 ScriptLoader::CreateLoadRequest(ScriptKind aKind,
+                                nsIURI* aURI,
                                 nsIScriptElement* aElement,
                                 uint32_t aVersion, CORSMode aCORSMode,
                                 const SRIMetadata &aIntegrity)
 {
   if (aKind == ScriptKind::Classic) {
-    return new ScriptLoadRequest(aKind, aElement, aVersion, aCORSMode,
+    return new ScriptLoadRequest(aKind, aURI, aElement,
+                                 aVersion,aCORSMode,
                                  aIntegrity);
   }
 
   MOZ_ASSERT(aKind == ScriptKind::Module);
-  return new ModuleLoadRequest(aElement, aVersion, aCORSMode, aIntegrity, this);
+  return new ModuleLoadRequest(aURI, aElement, aVersion, aCORSMode, aIntegrity, this);
 }
 
 bool
@@ -1343,9 +1324,8 @@ ScriptLoader::ProcessScriptElement(nsIScriptElement *aElement)
         }
       }
 
-      request = CreateLoadRequest(scriptKind, aElement, version, ourCORSMode,
-                                  sriMetadata);
-      request->mURI = scriptURI;
+      request = CreateLoadRequest(scriptKind, scriptURI, aElement,
+                                  version, ourCORSMode, sriMetadata);
       request->mIsInline = false;
       request->mReferrerPolicy = ourRefPolicy;
 
@@ -1466,11 +1446,11 @@ ScriptLoader::ProcessScriptElement(nsIScriptElement *aElement)
   }
 
   // Inline scripts ignore ther CORS mode and are always CORS_NONE
-  request = CreateLoadRequest(scriptKind, aElement, version, CORS_NONE,
+  request = CreateLoadRequest(scriptKind, mDocument->GetDocumentURI(), aElement,
+                              version, CORS_NONE,
                               SRIMetadata()); // SRI doesn't apply
   request->mJSVersion = version;
   request->mIsInline = true;
-  request->mURI = mDocument->GetDocumentURI();
   request->mLineNo = aElement->GetScriptLineNumber();
 
   if (request->IsModuleRequest()) {
@@ -2603,9 +2583,8 @@ ScriptLoader::PreloadURI(nsIURI *aURI, const nsAString &aCharset,
   }
 
   RefPtr<ScriptLoadRequest> request =
-    CreateLoadRequest(ScriptKind::Classic, nullptr, 0,
+    CreateLoadRequest(ScriptKind::Classic, aURI, nullptr, 0,
                       Element::StringToCORSMode(aCrossOrigin), sriMetadata);
-  request->mURI = aURI;
   request->mIsInline = false;
   request->mReferrerPolicy = aReferrerPolicy;
 
diff --git a/dom/script/ScriptLoader.h b/dom/script/ScriptLoader.h
index 955ac2cb7..3cbecbf03 100644
--- a/dom/script/ScriptLoader.h
+++ b/dom/script/ScriptLoader.h
@@ -62,6 +62,7 @@ protected:
 
 public:
   ScriptLoadRequest(ScriptKind aKind,
+                    nsIURI* aURI,
                     nsIScriptElement* aElement,
                     uint32_t aVersion,
                     mozilla::CORSMode aCORSMode,
@@ -81,6 +82,7 @@ public:
       mScriptTextBuf(nullptr),
       mScriptTextLength(0),
       mJSVersion(aVersion),
+      mURI(aURI),
       mLineNo(1),
       mCORSMode(aCORSMode),
       mIntegrity(aIntegrity),
@@ -165,7 +167,7 @@ public:
   char16_t* mScriptTextBuf; // Holds script text for non-inline scripts. Don't
   size_t mScriptTextLength; // use nsString so we can give ownership to jsapi.
   uint32_t mJSVersion;
-  nsCOMPtr<nsIURI> mURI;
+  const nsCOMPtr<nsIURI> mURI;
   nsCOMPtr<nsIPrincipal> mOriginPrincipal;
   nsAutoCString mURL;     // Keep the URI's filename alive during off thread parsing.
   int32_t mLineNo;
@@ -470,6 +472,7 @@ private:
 
   ScriptLoadRequest* CreateLoadRequest(
     ScriptKind aKind,
+    nsIURI* aURI,
     nsIScriptElement* aElement,
     uint32_t aVersion,
     mozilla::CORSMode aCORSMode,
@@ -588,7 +591,7 @@ private:
   void StartFetchingModuleDependencies(ModuleLoadRequest* aRequest);
 
   RefPtr<mozilla::GenericPromise>
-  StartFetchingModuleAndDependencies(ModuleLoadRequest* aRequest, nsIURI* aURI);
+  StartFetchingModuleAndDependencies(ModuleLoadRequest* aParent, nsIURI* aURI);
 
   nsIDocument* mDocument;                   // [WEAK]
   nsCOMArray<nsIScriptLoaderObserver> mObservers;