Bug 877072 - Script execution order for imports. r=mrbkap
authorGabor Krizsanits <gkrizsanits@mozilla.com>
Wed, 01 Oct 2014 14:13:53 +0200
changeset 208194 89716e3f169df2469a1f82da92ce95163a8ff8bc
parent 208193 df8c49b33b2219add48ed17521fc35fc77757f87
child 208195 e6e7586b3e02cdd59e978f306b8f1c2d1ef71c4c
push id1
push userroot
push dateMon, 20 Oct 2014 17:29:22 +0000
reviewersmrbkap
bugs877072
milestone35.0a1
Bug 877072 - Script execution order for imports. r=mrbkap
content/base/public/nsIDocument.h
content/base/src/ImportManager.cpp
content/base/src/ImportManager.h
content/base/src/nsDocument.cpp
content/base/src/nsDocument.h
content/base/src/nsScriptLoader.cpp
content/base/src/nsScriptLoader.h
content/html/content/moz.build
content/html/content/src/HTMLLinkElement.cpp
content/html/content/test/imports/file_importA1.html
content/html/content/test/imports/file_importA2.html
content/html/content/test/imports/file_importB1.html
content/html/content/test/imports/file_importB2.html
content/html/content/test/imports/file_importC1.html
content/html/content/test/imports/file_importC10.html
content/html/content/test/imports/file_importC2.html
content/html/content/test/imports/file_importC3.html
content/html/content/test/imports/file_importC4.html
content/html/content/test/imports/file_importC5.html
content/html/content/test/imports/file_importC6.html
content/html/content/test/imports/file_importC7.html
content/html/content/test/imports/file_importC8.html
content/html/content/test/imports/file_importC9.html
content/html/content/test/imports/file_importD.html
content/html/content/test/imports/file_importE.html
content/html/content/test/imports/mochitest.ini
content/html/content/test/mochitest.ini
content/html/content/test/test_imports_nested.html
content/html/content/test/test_imports_nested_2.html
testing/web-platform/meta/html-imports/fetching/already-in-import-map.html.ini
--- a/content/base/public/nsIDocument.h
+++ b/content/base/public/nsIDocument.h
@@ -129,18 +129,18 @@ template<typename> class OwningNonNull;
 template<typename> class Sequence;
 
 template<typename, typename> class CallbackObjectHolder;
 typedef CallbackObjectHolder<NodeFilter, nsIDOMNodeFilter> NodeFilterHolder;
 } // namespace dom
 } // namespace mozilla
 
 #define NS_IDOCUMENT_IID \
-{ 0x613ea294, 0x0288, 0x48b4, \
-  { 0x9e, 0x7b, 0x0f, 0xe9, 0x3f, 0x8c, 0xf8, 0x95 } }
+{ 0x42a263db, 0x6ac6, 0x40ff, \
+  { 0x89, 0xe2, 0x25, 0x12, 0xe4, 0xbc, 0x2d, 0x2d } }
 
 // Enum for requesting a particular type of document when creating a doc
 enum DocumentFlavor {
   DocumentFlavorLegacyGuess, // compat with old code until made HTML5-compliant
   DocumentFlavorHTML, // HTMLDocument with HTMLness bit set to true
   DocumentFlavorSVG, // SVGDocument
   DocumentFlavorPlain, // Just a Document
 };
@@ -2357,20 +2357,25 @@ public:
   nsIHTMLCollection* Children();
   uint32_t ChildElementCount();
 
   virtual nsHTMLDocument* AsHTMLDocument() { return nullptr; }
   virtual mozilla::dom::SVGDocument* AsSVGDocument() { return nullptr; }
 
   // Each import tree has exactly one master document which is
   // the root of the tree, and owns the browser context.
-  virtual already_AddRefed<nsIDocument> MasterDocument() = 0;
+  virtual nsIDocument* MasterDocument() = 0;
   virtual void SetMasterDocument(nsIDocument* master) = 0;
   virtual bool IsMasterDocument() = 0;
-  virtual already_AddRefed<mozilla::dom::ImportManager> ImportManager() = 0;
+  virtual mozilla::dom::ImportManager* ImportManager() = 0;
+  // We keep track of the order of sub imports were added to the document.
+  virtual bool HasSubImportLink(nsINode* aLink) = 0;
+  virtual uint32_t IndexOfSubImportLink(nsINode* aLink) = 0;
+  virtual void AddSubImportLink(nsINode* aLink) = 0;
+  virtual nsINode* GetSubImportLink(uint32_t aIdx) = 0;
 
   /*
    * Given a node, get a weak reference to it and append that reference to
    * mBlockedTrackingNodes. Can be used later on to look up a node in it.
    * (e.g., by the UI)
    */
   void AddBlockedTrackingNode(nsINode *node)
   {
--- a/content/base/src/ImportManager.cpp
+++ b/content/base/src/ImportManager.cpp
@@ -18,16 +18,20 @@
 #include "nsIDocument.h"
 #include "nsIDOMDocument.h"
 #include "nsIDOMEvent.h"
 #include "nsIPrincipal.h"
 #include "nsIScriptObjectPrincipal.h"
 #include "nsScriptLoader.h"
 #include "nsNetUtil.h"
 
+//-----------------------------------------------------------------------------
+// AutoError
+//-----------------------------------------------------------------------------
+
 class AutoError {
 public:
   explicit AutoError(mozilla::dom::ImportLoader* loader, bool scriptsBlocked = true)
     : mLoader(loader)
     , mPassed(false)
     , mScriptsBlocked(scriptsBlocked)
   {}
 
@@ -44,16 +48,230 @@ private:
   mozilla::dom::ImportLoader* mLoader;
   bool mPassed;
   bool mScriptsBlocked;
 };
 
 namespace mozilla {
 namespace dom {
 
+//-----------------------------------------------------------------------------
+// ImportLoader::Updater
+//-----------------------------------------------------------------------------
+
+void
+ImportLoader::Updater::GetReferrerChain(nsINode* aNode,
+                                        nsTArray<nsINode*>& aResult)
+{
+  // We fill up the array backward. First the last link: aNode.
+  MOZ_ASSERT(mLoader->mLinks.Contains(aNode));
+
+  aResult.AppendElement(aNode);
+  nsINode* node = aNode;
+  nsRefPtr<ImportManager> manager = mLoader->Manager();
+  for (ImportLoader* referrersLoader = manager->Find(node->OwnerDoc());
+       referrersLoader;
+       referrersLoader = manager->Find(node->OwnerDoc()))
+  {
+    // Then walking up the main referrer chain and append each link
+    // to the array.
+    node = referrersLoader->GetMainReferrer();
+    MOZ_ASSERT(node);
+    aResult.AppendElement(node);
+  }
+
+  // The reversed order is more useful for consumers.
+  // XXX: This should probably go to nsTArray or some generic utility
+  // lib for our containers that we don't have... I would really like to
+  // get rid of this part...
+  uint32_t l = aResult.Length();
+  for (uint32_t i = 0; i < l / 2; i++) {
+    Swap(aResult[i], aResult[l - i - 1]);
+  }
+}
+
+bool
+ImportLoader::Updater::ShouldUpdate(nsTArray<nsINode*>& aNewPath)
+{
+  // Let's walk down on the main referrer chains of both the current main and
+  // the new link, and find the last pair of links that are from the same
+  // document. This is the junction point between the two referrer chain. Their
+  // order in the subimport list of that document will determine if we have to
+  // update the spanning tree or this new edge changes nothing in the script
+  // execution order.
+  nsTArray<nsINode*> oldPath;
+  GetReferrerChain(mLoader->mLinks[mLoader->mMainReferrer], oldPath);
+  uint32_t max = std::min(oldPath.Length(), aNewPath.Length());
+  MOZ_ASSERT(max > 0);
+  uint32_t lastCommonImportAncestor = 0;
+
+  for (uint32_t i = 0;
+       i < max && oldPath[i]->OwnerDoc() == aNewPath[i]->OwnerDoc();
+       i++)
+  {
+    lastCommonImportAncestor = i;
+  }
+
+  MOZ_ASSERT(lastCommonImportAncestor < max);
+  nsINode* oldLink = oldPath[lastCommonImportAncestor];
+  nsINode* newLink = aNewPath[lastCommonImportAncestor];
+
+  if ((lastCommonImportAncestor == max - 1) &&
+      newLink == oldLink ) {
+    // If one chain contains the other entirely, then this is a simple cycle,
+    // nothing to be done here.
+    MOZ_ASSERT(oldPath.Length() != aNewPath.Length(),
+               "This would mean that new link == main referrer link");
+    return false;
+  }
+
+  MOZ_ASSERT(aNewPath != oldPath,
+             "How could this happen?");
+  nsIDocument* doc = oldLink->OwnerDoc();
+  MOZ_ASSERT(doc->HasSubImportLink(newLink));
+  MOZ_ASSERT(doc->HasSubImportLink(oldLink));
+
+  return doc->IndexOfSubImportLink(newLink) < doc->IndexOfSubImportLink(oldLink);
+}
+
+void
+ImportLoader::Updater::UpdateMainReferrer(uint32_t aNewIdx)
+{
+  MOZ_ASSERT(aNewIdx < mLoader->mLinks.Length());
+  nsINode* newMainReferrer = mLoader->mLinks[aNewIdx];
+
+  // This new link means we have to execute our scripts sooner...
+  // Let's make sure that unblocking a loader does not trigger a script execution.
+  // So we start with placing the new blockers and only then will we remove any
+  // blockers.
+  if (mLoader->IsBlocking()) {
+    // Our import parent is changed, let's block the new one and later unblock
+    // the old one.
+    newMainReferrer->OwnerDoc()->ScriptLoader()->AddExecuteBlocker();
+  }
+
+  if (mLoader->mDocument) {
+    // Our nearest predecessor has changed. So let's add the ScriptLoader to the
+    // new one if there is any. And remove it from the old one.
+    nsRefPtr<ImportManager> manager = mLoader->Manager();
+    nsScriptLoader* loader = mLoader->mDocument->ScriptLoader();
+    ImportLoader*& pred = mLoader->mBlockingPredecessor;
+    ImportLoader* newPred = manager->GetNearestPredecessor(newMainReferrer);
+    if (pred) {
+      if (newPred) {
+        newPred->AddBlockedScriptLoader(loader);
+      }
+      pred->RemoveBlockedScriptLoader(loader);
+    }
+  }
+
+  if (mLoader->IsBlocking()) {
+    mLoader->mImportParent->ScriptLoader()->RemoveExecuteBlocker();
+  }
+
+  // Finally update mMainReferrer to point to the newly added link.
+  mLoader->mMainReferrer = aNewIdx;
+  mLoader->mImportParent = newMainReferrer->OwnerDoc();
+}
+
+nsINode*
+ImportLoader::Updater::NextDependant(nsINode* aCurrentLink,
+                                     nsTArray<nsINode*>& aPath,
+                                     NodeTable& aVisitedNodes, bool aSkipChildren)
+{
+  // Depth first graph traversal.
+  if (!aSkipChildren) {
+    // "first child"
+    ImportLoader* loader = mLoader->Manager()->Find(aCurrentLink);
+    if (loader && loader->GetDocument()) {
+      nsINode* firstSubImport = loader->GetDocument()->GetSubImportLink(0);
+      if (firstSubImport && !aVisitedNodes.Contains(firstSubImport)) {
+        aPath.AppendElement(aCurrentLink);
+        aVisitedNodes.PutEntry(firstSubImport);
+        return firstSubImport;
+      }
+    }
+  }
+
+  aPath.AppendElement(aCurrentLink);
+  // "(parent's) next sibling"
+  while(aPath.Length() > 1) {
+    aCurrentLink = aPath[aPath.Length() - 1];
+    aPath.RemoveElementAt(aPath.Length() - 1);
+
+    // Let's find the next "sibling"
+    ImportLoader* loader =  mLoader->Manager()->Find(aCurrentLink->OwnerDoc());
+    MOZ_ASSERT(loader && loader->GetDocument(), "How can this happend?");
+    nsIDocument* doc = loader->GetDocument();
+    MOZ_ASSERT(doc->HasSubImportLink(aCurrentLink));
+    uint32_t idx = doc->IndexOfSubImportLink(aCurrentLink);
+    nsINode* next = doc->GetSubImportLink(idx + 1);
+    if (next) {
+      // Note: If we found an already visited link that means the parent links has
+      // closed the circle it's always the "first child" section that should find
+      // the first already visited node. Let's just assert that.
+      MOZ_ASSERT(!aVisitedNodes.Contains(next));
+      aVisitedNodes.PutEntry(next);
+      return next;
+    }
+  }
+
+  return nullptr;
+}
+
+void
+ImportLoader::Updater::UpdateDependants(nsINode* aNode,
+                                        nsTArray<nsINode*>& aPath)
+{
+  NodeTable visitedNodes;
+  nsINode* current = aNode;
+  uint32_t initialLength = aPath.Length();
+  bool neededUpdate = true;
+  while ((current = NextDependant(current, aPath, visitedNodes, !neededUpdate))) {
+    if (!current || aPath.Length() <= initialLength) {
+      break;
+    }
+    ImportLoader* loader = mLoader->Manager()->Find(current);
+    if (!loader) {
+      continue;
+    }
+    Updater& updater = loader->mUpdater;
+    neededUpdate = updater.ShouldUpdate(aPath);
+    if (neededUpdate) {
+      updater.UpdateMainReferrer(loader->mLinks.IndexOf(current));
+    }
+  }
+}
+
+void
+ImportLoader::Updater::UpdateSpanningTree(nsINode* aNode)
+{
+  if (mLoader->mReady || mLoader->mStopped) {
+    // Scripts already executed, nothing to be done here.
+    return;
+  }
+
+  if (mLoader->mLinks.Length() == 1) {
+    // If this is the first referrer, let's mark it.
+    mLoader->mMainReferrer = 0;
+    return;
+  }
+
+  nsTArray<nsINode*> newReferrerChain;
+  GetReferrerChain(aNode, newReferrerChain);
+  if (ShouldUpdate(newReferrerChain)) {
+    UpdateMainReferrer(mLoader->mLinks.Length() - 1);
+    UpdateDependants(aNode, newReferrerChain);
+  }
+}
+
+//-----------------------------------------------------------------------------
+// ImportLoader
+//-----------------------------------------------------------------------------
+
 NS_INTERFACE_MAP_BEGIN(ImportLoader)
   NS_INTERFACE_MAP_ENTRY(nsIStreamListener)
   NS_INTERFACE_MAP_ENTRY(nsIRequestObserver)
   NS_INTERFACE_MAP_ENTRIES_CYCLE_COLLECTION(ImportLoader)
 NS_INTERFACE_MAP_END
 
 NS_IMPL_CYCLE_COLLECTING_ADDREF(ImportLoader)
 NS_IMPL_CYCLE_COLLECTING_RELEASE(ImportLoader)
@@ -61,64 +279,98 @@ NS_IMPL_CYCLE_COLLECTING_RELEASE(ImportL
 NS_IMPL_CYCLE_COLLECTION(ImportLoader,
                          mDocument,
                          mImportParent,
                          mLinks)
 
 ImportLoader::ImportLoader(nsIURI* aURI, nsIDocument* aImportParent)
   : mURI(aURI)
   , mImportParent(aImportParent)
+  , mBlockingPredecessor(nullptr)
   , mReady(false)
   , mStopped(false)
   , mBlockingScripts(false)
-{}
+  , mUpdater(MOZ_THIS_IN_INITIALIZER_LIST())
+{
+}
 
 void
 ImportLoader::BlockScripts()
 {
   MOZ_ASSERT(!mBlockingScripts);
   mImportParent->ScriptLoader()->AddExecuteBlocker();
   mBlockingScripts = true;
 }
 
 void
 ImportLoader::UnblockScripts()
 {
   MOZ_ASSERT(mBlockingScripts);
   mImportParent->ScriptLoader()->RemoveExecuteBlocker();
+  for (uint32_t i = 0; i < mBlockedScriptLoaders.Length(); i++) {
+    mBlockedScriptLoaders[i]->RemoveExecuteBlocker();
+  }
+  mBlockedScriptLoaders.Clear();
   mBlockingScripts = false;
 }
 
 void
+ImportLoader::SetBlockingPredecessor(ImportLoader* aLoader)
+{
+  mBlockingPredecessor = aLoader;
+}
+
+void
 ImportLoader::DispatchEventIfFinished(nsINode* aNode)
 {
   MOZ_ASSERT(!(mReady && mStopped));
   if (mReady) {
     DispatchLoadEvent(aNode);
   }
   if (mStopped) {
     DispatchErrorEvent(aNode);
   }
 }
 
 void
+ImportLoader::AddBlockedScriptLoader(nsScriptLoader* aScriptLoader)
+{
+  if (mBlockedScriptLoaders.Contains(aScriptLoader)) {
+    return;
+  }
+
+  aScriptLoader->AddExecuteBlocker();
+
+  // Let's keep track of the pending script loaders.
+  mBlockedScriptLoaders.AppendElement(aScriptLoader);
+}
+
+bool
+ImportLoader::RemoveBlockedScriptLoader(nsScriptLoader* aScriptLoader)
+{
+  aScriptLoader->RemoveExecuteBlocker();
+  return mBlockedScriptLoaders.RemoveElement(aScriptLoader);
+}
+
+void
 ImportLoader::AddLinkElement(nsINode* aNode)
 {
   // If a new link element is added to the import tree that
   // refers to an import that is already finished loading or
   // stopped trying, we need to fire the corresponding event
   // on it.
-  mLinks.AppendObject(aNode);
+  mLinks.AppendElement(aNode);
+  mUpdater.UpdateSpanningTree(aNode);
   DispatchEventIfFinished(aNode);
 }
 
 void
 ImportLoader::RemoveLinkElement(nsINode* aNode)
 {
-  mLinks.RemoveObject(aNode);
+  mLinks.RemoveElement(aNode);
 }
 
 // Events has to be fired with a script runner, so mImport can
 // be set on the link element before the load event is fired even
 // if ImportLoader::Get returns an already loaded import and we
 // fire the load event immediately on the new referring link element.
 class AsyncEvent : public nsRunnable {
 public:
@@ -154,31 +406,31 @@ ImportLoader::DispatchLoadEvent(nsINode*
 {
   nsContentUtils::AddScriptRunner(new AsyncEvent(aNode, /* aSuccess = */ true));
 }
 
 void
 ImportLoader::Done()
 {
   mReady = true;
-  uint32_t count = mLinks.Count();
-  for (uint32_t i = 0; i < count; i++) {
+  uint32_t l = mLinks.Length();
+  for (uint32_t i = 0; i < l; i++) {
     DispatchLoadEvent(mLinks[i]);
   }
   UnblockScripts();
   ReleaseResources();
 }
 
 void
 ImportLoader::Error(bool aUnblockScripts)
 {
   mDocument = nullptr;
   mStopped = true;
-  uint32_t count = mLinks.Count();
-  for (uint32_t i = 0; i < count; i++) {
+  uint32_t l = mLinks.Length();
+  for (uint32_t i = 0; i < l; i++) {
     DispatchErrorEvent(mLinks[i]);
   }
   if (aUnblockScripts) {
     UnblockScripts();
   }
   ReleaseResources();
 }
 
@@ -386,25 +638,47 @@ ImportLoader::OnStartRequest(nsIRequest*
   nsCOMPtr<nsILoadGroup> newLoadGroup = do_CreateInstance(NS_LOADGROUP_CONTRACTID);
   NS_ENSURE_TRUE(newLoadGroup, NS_ERROR_OUT_OF_MEMORY);
   newLoadGroup->SetLoadGroup(loadGroup);
   rv = mDocument->StartDocumentLoad("import", channel, newLoadGroup,
                                     nullptr, getter_AddRefs(listener),
                                     true);
   NS_ENSURE_SUCCESS(rv, NS_ERROR_DOM_ABORT_ERR);
 
-  // Let's start parser.
+  nsCOMPtr<nsIURI> originalURI;
+  rv = channel->GetOriginalURI(getter_AddRefs(originalURI));
+  NS_ENSURE_SUCCESS(rv, NS_ERROR_DOM_ABORT_ERR);
+
+  nsCOMPtr<nsIURI> URI;
+  rv = channel->GetURI(getter_AddRefs(URI));
+  NS_ENSURE_SUCCESS(rv, NS_ERROR_DOM_ABORT_ERR);
+  MOZ_ASSERT(URI, "URI of a channel should never be null");
+
+  bool equals;
+  rv = URI->Equals(originalURI, &equals);
+  NS_ENSURE_SUCCESS(rv, NS_ERROR_DOM_ABORT_ERR);
+
+  if (!equals) {
+    // In case of a redirection we must add the new URI to the import map.
+    Manager()->AddLoaderWithNewURI(this, URI);
+  }
+
+  // Let's start the parser.
   mParserStreamListener = listener;
   rv = listener->OnStartRequest(aRequest, aContext);
   NS_ENSURE_SUCCESS(rv, NS_ERROR_DOM_ABORT_ERR);
 
   ae.Pass();
   return NS_OK;
 }
 
+//-----------------------------------------------------------------------------
+// ImportManager
+//-----------------------------------------------------------------------------
+
 NS_IMPL_CYCLE_COLLECTION(ImportManager,
                          mImports)
 
 NS_INTERFACE_MAP_BEGIN(ImportManager)
   NS_INTERFACE_MAP_ENTRIES_CYCLE_COLLECTION(ImportManager)
 NS_INTERFACE_MAP_END
 
 NS_IMPL_CYCLE_COLLECTING_ADDREF(ImportManager)
@@ -412,21 +686,83 @@ NS_IMPL_CYCLE_COLLECTING_RELEASE(ImportM
 
 already_AddRefed<ImportLoader>
 ImportManager::Get(nsIURI* aURI, nsINode* aNode, nsIDocument* aOrigDocument)
 {
   // Check if we have a loader for that URI, if not create one,
   // and start it up.
   nsRefPtr<ImportLoader> loader;
   mImports.Get(aURI, getter_AddRefs(loader));
-
+  bool needToStart = false;
   if (!loader) {
     loader = new ImportLoader(aURI, aOrigDocument);
     mImports.Put(aURI, loader);
+    needToStart = true;
+  }
+
+  MOZ_ASSERT(loader);
+  // Let's keep track of the sub imports links in each document. It will
+  // be used later for scrip execution order calculation. (see UpdateSpanningTree)
+  // NOTE: removing and adding back the link to the tree somewhere else will
+  // NOT have an effect on script execution order.
+  if (!aOrigDocument->HasSubImportLink(aNode)) {
+    aOrigDocument->AddSubImportLink(aNode);
+  }
+
+  loader->AddLinkElement(aNode);
+
+  if (needToStart) {
     loader->Open();
   }
-  loader->AddLinkElement(aNode);
-  MOZ_ASSERT(loader);
+
   return loader.forget();
 }
 
+ImportLoader*
+ImportManager::Find(nsIDocument* aImport)
+{
+  return mImports.GetWeak(aImport->GetDocumentURIObject());
+}
+
+ImportLoader*
+ImportManager::Find(nsINode* aLink)
+{
+  HTMLLinkElement* linkElement = static_cast<HTMLLinkElement*>(aLink);
+  nsCOMPtr<nsIURI> uri = linkElement->GetHrefURI();
+  return mImports.GetWeak(uri);
+}
+
+void
+ImportManager::AddLoaderWithNewURI(ImportLoader* aLoader, nsIURI* aNewURI)
+{
+  mImports.Put(aNewURI, aLoader);
+}
+
+nsRefPtr<ImportLoader> ImportManager::GetNearestPredecessor(nsINode* aNode)
+{
+  // Return the previous link if there is any in the same document.
+  nsIDocument* doc = aNode->OwnerDoc();
+  int32_t idx = doc->IndexOfSubImportLink(aNode);
+  MOZ_ASSERT(idx != -1, "aNode must be a sub import link of its owner document");
+  if (idx == 0) {
+    if (doc->IsMasterDocument()) {
+      // If there is no previous one, and it was the master document, then
+      // there is no predecessor.
+      return nullptr;
+    }
+    // Else we find the main referrer of the import parent of the link's document.
+    // And do a recursion.
+    ImportLoader* owner = Find(doc);
+    MOZ_ASSERT(owner);
+    nsCOMPtr<nsINode> mainReferrer = owner->GetMainReferrer();
+    return GetNearestPredecessor(mainReferrer);
+  }
+  MOZ_ASSERT(idx > 0);
+  HTMLLinkElement* link =
+    static_cast<HTMLLinkElement*>(doc->GetSubImportLink(idx - 1));
+  nsCOMPtr<nsIURI> uri = link->GetHrefURI();
+  nsRefPtr<ImportLoader> ret;
+  mImports.Get(uri, getter_AddRefs(ret));
+  return ret;
+}
+
 } // namespace dom
 } // namespace mozilla
--- a/content/base/src/ImportManager.h
+++ b/content/base/src/ImportManager.h
@@ -34,40 +34,100 @@
  *  |                                        |
  *  LinkElement <-----------------------------
  *
  */
 
 #ifndef mozilla_dom_ImportManager_h__
 #define mozilla_dom_ImportManager_h__
 
-#include "nsCOMArray.h"
+#include "nsTArray.h"
 #include "nsCycleCollectionParticipant.h"
 #include "nsIDOMEventListener.h"
 #include "nsIStreamListener.h"
 #include "nsIWeakReferenceUtils.h"
 #include "nsRefPtrHashtable.h"
+#include "nsScriptLoader.h"
 #include "nsURIHashKey.h"
 
 class nsIDocument;
 class nsIChannel;
 class nsIPrincipal;
 class nsINode;
 class AutoError;
 
 namespace mozilla {
 namespace dom {
 
 class ImportManager;
 
+typedef nsTHashtable<nsPtrHashKey<nsINode>> NodeTable;
+
 class ImportLoader MOZ_FINAL : public nsIStreamListener
                              , public nsIDOMEventListener
 {
+
+  // A helper inner class to decouple the logic of updating the import graph
+  // after a new import link has been found by one of the parsers.
+  class Updater {
+
+  public:
+    Updater(ImportLoader* aLoader) : mLoader(aLoader)
+    {}
+
+    // After a new link is added that refers to this import, we
+    // have to update the spanning tree, since given this new link the
+    // priority of this import might be higher in the scripts
+    // execution order than before. It updates mMainReferrer, mImportParent,
+    // the corresponding pending ScriptRunners, etc.
+    // It also handles updating additional dependant loaders via the
+    // UpdateDependants calls.
+    // (NOTE: See GetMainReferrer about spanning tree.)
+    void UpdateSpanningTree(nsINode* aNode);
+
+  private:
+    // Returns an array of links that forms a referring chain from
+    // the master document to this import. Each link in the array
+    // is marked as main referrer in the list.
+    void GetReferrerChain(nsINode* aNode, nsTArray<nsINode*>& aResult);
+
+    // Once we find a new referrer path to our import, we have to see if
+    // it changes the load order hence we have to do an update on the graph.
+    bool ShouldUpdate(nsTArray<nsINode*>& aNewPath);
+    void UpdateMainReferrer(uint32_t newIdx);
+
+    // It's a depth first graph traversal algorithm, for UpdateDependants. The
+    // nodes in the graph are the import link elements, and there is a directed
+    // edge from link1 to link2 if link2 is a subimport in the import document
+    // of link1.
+    // If the ImportLoader that aCurrentLink points to didn't need to be updated
+    // the algorithm skips its "children" (subimports). Note, that this graph can
+    // also contain cycles, aVisistedLinks is used to track the already visited
+    // links to avoid an infinite loop.
+    // aPath - (in/out) the referrer link chain of aCurrentLink when called, and
+    //                  of the next link when the function returns
+    // aVisitedLinks - (in/out) list of links that the traversal already visited
+    //                          (to handle cycles in the graph)
+    // aSkipChildren - when aCurrentLink points to an import that did not need
+    //                 to be updated, we can skip its sub-imports ('children')
+    nsINode* NextDependant(nsINode* aCurrentLink,
+                           nsTArray<nsINode*>& aPath,
+                           NodeTable& aVisitedLinks, bool aSkipChildren);
+
+    // When we find a new link that changes the load order of the known imports,
+    // we also have to check all the subimports of it, to see if they need an
+    // update too. (see test_imports_nested_2.html)
+    void UpdateDependants(nsINode* aNode, nsTArray<nsINode*>& aPath);
+
+    ImportLoader* mLoader;
+  };
+
   friend class ::AutoError;
   friend class ImportManager;
+  friend class Updater;
 
 public:
   ImportLoader(nsIURI* aURI, nsIDocument* aOriginDocument);
 
   NS_DECL_CYCLE_COLLECTING_ISUPPORTS
   NS_DECL_CYCLE_COLLECTION_CLASS_AMBIGUOUS(ImportLoader, nsIStreamListener)
   NS_DECL_NSISTREAMLISTENER
   NS_DECL_NSIREQUESTOBSERVER
@@ -78,21 +138,56 @@ public:
 
   // Validation then opening and starting up the channel.
   void Open();
   void AddLinkElement(nsINode* aNode);
   void RemoveLinkElement(nsINode* aNode);
   bool IsReady() { return mReady; }
   bool IsStopped() { return mStopped; }
   bool IsBlocking() { return mBlockingScripts; }
-  already_AddRefed<nsIDocument> GetImport()
+
+  ImportManager* Manager() {
+    MOZ_ASSERT(mDocument || mImportParent, "One of them should be always set");
+    return (mDocument ? mDocument : mImportParent)->ImportManager();
+  }
+
+  // Simply getter for the import document. Can return a partially parsed
+  // document if called too early.
+  nsIDocument* GetDocument()
+  {
+    return mDocument;
+  }
+
+  // Getter for the import document that is used in the spec. Returns
+  // nullptr if the import is not yet ready.
+  nsIDocument* GetImport()
   {
-    return mReady ? nsCOMPtr<nsIDocument>(mDocument).forget() : nullptr;
+    return mReady ? mDocument : nullptr;
   }
 
+  // There is only one referring link that is marked as primary link per
+  // imports. This is the one that has to be taken into account when
+  // scrip execution order is determined. Links marked as primary link form
+  // a spanning tree in the import graph. (Eliminating the cycles and
+  // multiple parents.) This spanning tree is recalculated every time
+  // a new import link is added to the manager.
+  nsINode* GetMainReferrer()
+  {
+    return mLinks.IsEmpty() ? nullptr : mLinks[mMainReferrer];
+  }
+
+  // An import is not only blocked by its import children, but also
+  // by its predecessors. It's enough to find the closest predecessor
+  // and wait for that to run its scripts. We keep track of all the
+  // ScriptRunners that are waiting for this import. NOTE: updating
+  // the main referrer might change this list.
+  void AddBlockedScriptLoader(nsScriptLoader* aScriptLoader);
+  bool RemoveBlockedScriptLoader(nsScriptLoader* aScriptLoader);
+  void SetBlockingPredecessor(ImportLoader* aLoader);
+
 private:
   ~ImportLoader() {}
 
   // If a new referrer LinkElement was added, let's
   // see if we are already finished and if so fire
   // the right event.
   void DispatchEventIfFinished(nsINode* aNode);
 
@@ -117,39 +212,67 @@ private:
   void UnblockScripts();
 
   nsIPrincipal* Principal();
 
   nsCOMPtr<nsIDocument> mDocument;
   nsCOMPtr<nsIURI> mURI;
   nsCOMPtr<nsIStreamListener> mParserStreamListener;
   nsCOMPtr<nsIDocument> mImportParent;
+  ImportLoader* mBlockingPredecessor;
+
   // List of the LinkElements that are referring to this import
   // we need to keep track of them so we can fire event on them.
-  nsCOMArray<nsINode> mLinks;
+  nsTArray<nsCOMPtr<nsINode>> mLinks;
+
+  // List of pending ScriptLoaders that are waiting for this import
+  // to finish.
+  nsTArray<nsRefPtr<nsScriptLoader>> mBlockedScriptLoaders;
+
+  // There is always exactly one referrer link that is flagged as
+  // the main referrer the primary link. This is the one that is
+  // used in the script execution order calculation.
+  // ("Branch" according to the spec.)
+  uint32_t mMainReferrer;
   bool mReady;
   bool mStopped;
   bool mBlockingScripts;
+  Updater mUpdater;
 };
 
 class ImportManager MOZ_FINAL : public nsISupports
 {
   typedef nsRefPtrHashtable<nsURIHashKey, ImportLoader> ImportMap;
 
   ~ImportManager() {}
 
 public:
   ImportManager() {}
 
   NS_DECL_CYCLE_COLLECTING_ISUPPORTS
   NS_DECL_CYCLE_COLLECTION_CLASS(ImportManager)
 
+  // Finds the ImportLoader that belongs to aImport in the map.
+  ImportLoader* Find(nsIDocument* aImport);
+
+  // Find the ImportLoader aLink refers to.
+  ImportLoader* Find(nsINode* aLink);
+
+  void AddLoaderWithNewURI(ImportLoader* aLoader, nsIURI* aNewURI);
+
+  // When a new import link is added, this getter either creates
+  // a new ImportLoader for it, or returns an existing one if
+  // it was already created and in the import map.
   already_AddRefed<ImportLoader> Get(nsIURI* aURI, nsINode* aNode,
                                      nsIDocument* aOriginDocument);
 
+  // It finds the predecessor for an import link node that runs its
+  // scripts the latest among its predecessors.
+  nsRefPtr<ImportLoader> GetNearestPredecessor(nsINode* aNode);
+
 private:
   ImportMap mImports;
 };
 
 } // namespace dom
 } // namespace mozilla
 
 #endif // mozilla_dom_ImportManager_h__
--- a/content/base/src/nsDocument.cpp
+++ b/content/base/src/nsDocument.cpp
@@ -1992,16 +1992,18 @@ NS_IMPL_CYCLE_COLLECTION_TRAVERSE_BEGIN_
   NS_IMPL_CYCLE_COLLECTION_TRAVERSE(mChildrenCollection)
   NS_IMPL_CYCLE_COLLECTION_TRAVERSE(mRegistry)
 
   // Traverse all our nsCOMArrays.
   NS_IMPL_CYCLE_COLLECTION_TRAVERSE(mStyleSheets)
   NS_IMPL_CYCLE_COLLECTION_TRAVERSE(mOnDemandBuiltInUASheets)
   NS_IMPL_CYCLE_COLLECTION_TRAVERSE(mPreloadingImages)
 
+  NS_IMPL_CYCLE_COLLECTION_TRAVERSE(mSubImportLinks)
+
   for (uint32_t i = 0; i < tmp->mFrameRequestCallbacks.Length(); ++i) {
     NS_CYCLE_COLLECTION_NOTE_EDGE_NAME(cb, "mFrameRequestCallbacks[i]");
     cb.NoteXPCOMChild(tmp->mFrameRequestCallbacks[i].mCallback.GetISupports());
   }
 
   // Traverse animation components
   if (tmp->mAnimationController) {
     tmp->mAnimationController->Traverse(&cb);
@@ -2056,16 +2058,17 @@ NS_IMPL_CYCLE_COLLECTION_UNLINK_BEGIN(ns
   NS_IMPL_CYCLE_COLLECTION_UNLINK(mCachedEncoder)
   NS_IMPL_CYCLE_COLLECTION_UNLINK(mUndoManager)
   NS_IMPL_CYCLE_COLLECTION_UNLINK(mAnimationTimeline)
   NS_IMPL_CYCLE_COLLECTION_UNLINK(mTemplateContentsOwner)
   NS_IMPL_CYCLE_COLLECTION_UNLINK(mChildrenCollection)
   NS_IMPL_CYCLE_COLLECTION_UNLINK(mRegistry)
   NS_IMPL_CYCLE_COLLECTION_UNLINK(mMasterDocument)
   NS_IMPL_CYCLE_COLLECTION_UNLINK(mImportManager)
+  NS_IMPL_CYCLE_COLLECTION_UNLINK(mSubImportLinks)
 
   tmp->mParentDocument = nullptr;
 
   NS_IMPL_CYCLE_COLLECTION_UNLINK(mPreloadingImages)
 
 
   if (tmp->mBoxObjectTable) {
    tmp->mBoxObjectTable->EnumerateRead(ClearAllBoxObjects, nullptr);
--- a/content/base/src/nsDocument.h
+++ b/content/base/src/nsDocument.h
@@ -1285,49 +1285,70 @@ public:
                                                   const nsAString& aTypeExtension,
                                                   mozilla::ErrorResult& rv) MOZ_OVERRIDE;
   virtual already_AddRefed<Element> CreateElementNS(const nsAString& aNamespaceURI,
                                                     const nsAString& aQualifiedName,
                                                     const nsAString& aTypeExtension,
                                                     mozilla::ErrorResult& rv) MOZ_OVERRIDE;
   virtual void UseRegistryFromDocument(nsIDocument* aDocument) MOZ_OVERRIDE;
 
-  virtual already_AddRefed<nsIDocument> MasterDocument()
+  virtual nsIDocument* MasterDocument()
   {
-    return mMasterDocument ? (nsCOMPtr<nsIDocument>(mMasterDocument)).forget()
-                           : (nsCOMPtr<nsIDocument>(this)).forget();
+    return mMasterDocument ? mMasterDocument.get()
+                           : this;
   }
 
   virtual void SetMasterDocument(nsIDocument* master)
   {
     mMasterDocument = master;
   }
 
   virtual bool IsMasterDocument()
   {
     return !mMasterDocument;
   }
 
-  virtual already_AddRefed<mozilla::dom::ImportManager> ImportManager()
+  virtual mozilla::dom::ImportManager* ImportManager()
   {
     if (mImportManager) {
       MOZ_ASSERT(!mMasterDocument, "Only the master document has ImportManager set");
-      return nsRefPtr<mozilla::dom::ImportManager>(mImportManager).forget();
+      return mImportManager.get();
     }
 
     if (mMasterDocument) {
       return mMasterDocument->ImportManager();
     }
 
     // ImportManager is created lazily.
     // If the manager is not yet set it has to be the
     // master document and this is the first import in it.
     // Let's create a new manager.
     mImportManager = new mozilla::dom::ImportManager();
-    return nsRefPtr<mozilla::dom::ImportManager>(mImportManager).forget();
+    return mImportManager.get();
+  }
+
+  virtual bool HasSubImportLink(nsINode* aLink)
+  {
+    return mSubImportLinks.Contains(aLink);
+  }
+
+  virtual uint32_t IndexOfSubImportLink(nsINode* aLink)
+  {
+    return mSubImportLinks.IndexOf(aLink);
+  }
+
+  virtual void AddSubImportLink(nsINode* aLink)
+  {
+    mSubImportLinks.AppendElement(aLink);
+  }
+
+  virtual nsINode* GetSubImportLink(uint32_t aIdx)
+  {
+    return aIdx < mSubImportLinks.Length() ? mSubImportLinks[aIdx].get()
+                                           : nullptr;
   }
 
   virtual void UnblockDOMContentLoaded() MOZ_OVERRIDE;
 
 protected:
   friend class nsNodeUtils;
   friend class nsDocumentOnStack;
 
@@ -1749,16 +1770,17 @@ private:
 
   nsrefcnt mStackRefCnt;
   bool mNeedsReleaseAfterStackRefCntRelease;
 
   CSPErrorQueue mCSPWebConsoleErrorQueue;
 
   nsCOMPtr<nsIDocument> mMasterDocument;
   nsRefPtr<mozilla::dom::ImportManager> mImportManager;
+  nsTArray<nsCOMPtr<nsINode> > mSubImportLinks;
 
   // Set to true when the document is possibly controlled by the ServiceWorker.
   // Used to prevent multiple requests to ServiceWorkerManager.
   bool mMaybeServiceWorkerControlled;
 
 #ifdef DEBUG
 public:
   bool mWillReparent;
--- a/content/base/src/nsScriptLoader.cpp
+++ b/content/base/src/nsScriptLoader.cpp
@@ -44,16 +44,17 @@
 #include "nsIChannelPolicy.h"
 #include "nsChannelPolicy.h"
 #include "nsCRT.h"
 #include "nsContentCreatorFunctions.h"
 #include "nsCrossSiteListenerProxy.h"
 #include "nsSandboxFlags.h"
 #include "nsContentTypeParser.h"
 #include "nsINetworkPredictor.h"
+#include "ImportManager.h"
 #include "mozilla/dom/EncodingUtils.h"
 
 #include "mozilla/CORSMode.h"
 #include "mozilla/Attributes.h"
 #include "mozilla/unused.h"
 
 #ifdef PR_LOGGING
 static PRLogModuleInfo* gCspPRLog;
@@ -1231,30 +1232,64 @@ nsScriptLoader::ProcessPendingRequests()
 bool
 nsScriptLoader::ReadyToExecuteScripts()
 {
   // Make sure the SelfReadyToExecuteScripts check is first, so that
   // we don't block twice on an ancestor.
   if (!SelfReadyToExecuteScripts()) {
     return false;
   }
-  
+
   for (nsIDocument* doc = mDocument; doc; doc = doc->GetParentDocument()) {
     nsScriptLoader* ancestor = doc->ScriptLoader();
     if (!ancestor->SelfReadyToExecuteScripts() &&
         ancestor->AddPendingChildLoader(this)) {
       AddExecuteBlocker();
       return false;
     }
   }
 
+  if (!mDocument->IsMasterDocument()) {
+    nsRefPtr<ImportManager> im = mDocument->ImportManager();
+    nsRefPtr<ImportLoader> loader = im->Find(mDocument);
+    MOZ_ASSERT(loader, "How can we have an import document without a loader?");
+
+    // The referring link that counts in the execution order calculation
+    // (in spec: flagged as branch)
+    nsCOMPtr<nsINode> referrer = loader->GetMainReferrer();
+    MOZ_ASSERT(referrer, "There has to be a main referring link for each imports");
+
+    // Import documents are blocked by their import predecessors. We need to
+    // wait with script execution until all the predecessors are done.
+    // Technically it means we have to wait for the last one to finish,
+    // which is the neares one to us in the order.
+    nsRefPtr<ImportLoader> lastPred = im->GetNearestPredecessor(referrer);
+    if (!lastPred) {
+      // If there is no predecessor we can run.
+      return true;
+    }
+
+    nsCOMPtr<nsIDocument> doc = lastPred->GetDocument();
+    if (lastPred->IsBlocking() || !doc || (doc && !doc->ScriptLoader()->SelfReadyToExecuteScripts())) {
+      // Document has not been created yet or it was created but not ready.
+      // Either case we are blocked by it. The ImportLoader will take care
+      // of blocking us, and adding the pending child loader to the blocking
+      // ScriptLoader when it's possible (at this point the blocking loader
+      // might not have created the document/ScriptLoader)
+      lastPred->AddBlockedScriptLoader(this);
+      // As more imports are parsed, this can change, let's cache what we
+      // blocked, so it can be later updated if needed (see: ImportLoader::Updater).
+      loader->SetBlockingPredecessor(lastPred);
+      return false;
+    }
+  }
+
   return true;
 }
 
-
 // This function was copied from nsParser.cpp. It was simplified a bit.
 static bool
 DetectByteOrderMark(const unsigned char* aBytes, int32_t aLen, nsCString& oCharset)
 {
   if (aLen < 2)
     return false;
 
   switch(aBytes[0]) {
--- a/content/base/src/nsScriptLoader.h
+++ b/content/base/src/nsScriptLoader.h
@@ -244,16 +244,20 @@ public:
 
   /**
    * Process a request that was deferred so that the script could be compiled
    * off thread.
    */
   nsresult ProcessOffThreadRequest(nsScriptLoadRequest *aRequest,
                                    void **aOffThreadToken);
 
+  bool AddPendingChildLoader(nsScriptLoader* aChild) {
+    return mPendingChildLoaders.AppendElement(aChild) != nullptr;
+  }
+
 private:
   virtual ~nsScriptLoader();
 
   /**
    * Unblocks the creator parser of the parser-blocking scripts.
    */
   void UnblockParser(nsScriptLoadRequest* aParserBlockingRequest);
 
@@ -297,20 +301,16 @@ private:
   /**
    * Return whether just this loader is ready to execute scripts.
    */
   bool SelfReadyToExecuteScripts()
   {
     return mEnabled && !mBlockerCount;
   }
 
-  bool AddPendingChildLoader(nsScriptLoader* aChild) {
-    return mPendingChildLoaders.AppendElement(aChild) != nullptr;
-  }
-
   nsresult AttemptAsyncScriptParse(nsScriptLoadRequest* aRequest);
   nsresult ProcessRequest(nsScriptLoadRequest* aRequest,
                           void **aOffThreadToken = nullptr);
   void FireScriptAvailable(nsresult aResult,
                            nsScriptLoadRequest* aRequest);
   void FireScriptEvaluated(nsresult aResult,
                            nsScriptLoadRequest* aRequest);
   nsresult EvaluateScript(nsScriptLoadRequest* aRequest,
--- a/content/html/content/moz.build
+++ b/content/html/content/moz.build
@@ -3,16 +3,17 @@
 # This Source Code Form is subject to the terms of the Mozilla Public
 # License, v. 2.0. If a copy of the MPL was not distributed with this
 # file, You can obtain one at http://mozilla.org/MPL/2.0/.
 
 DIRS += ['public', 'src']
 
 MOCHITEST_MANIFESTS += [
     'test/forms/mochitest.ini',
+    'test/imports/mochitest.ini',
     'test/mochitest.ini',
 ]
 
 MOCHITEST_CHROME_MANIFESTS += [
     'test/chrome.ini',
     'test/forms/chrome.ini',
 ]
 
--- a/content/html/content/src/HTMLLinkElement.cpp
+++ b/content/html/content/src/HTMLLinkElement.cpp
@@ -258,25 +258,16 @@ HTMLLinkElement::UpdateImport()
     // the import and reset mImportLoader.
     if (mImportLoader) {
       mImportLoader->RemoveLinkElement(this);
       mImportLoader = nullptr;
     }
     return;
   }
 
-  // Until the script execution order is not sorted out for nested cases
-  // let's not allow them.
-  if (!doc->IsMasterDocument()) {
-    nsContentUtils::LogSimpleConsoleError(
-      NS_LITERAL_STRING("Nested imports are not supported yet"),
-      "Imports");
-    return;
-  }
-
   // 2. rel type should be import.
   nsAutoString rel;
   GetAttr(kNameSpaceID_None, nsGkAtoms::rel, rel);
   uint32_t linkTypes = nsStyleLinkElement::ParseLinkTypes(rel, NodePrincipal());
   if (!(linkTypes & eHTMLIMPORT)) {
     mImportLoader = nullptr;
     return;
   }
@@ -521,13 +512,13 @@ JSObject*
 HTMLLinkElement::WrapNode(JSContext* aCx)
 {
   return HTMLLinkElementBinding::Wrap(aCx, this);
 }
 
 already_AddRefed<nsIDocument>
 HTMLLinkElement::GetImport()
 {
-  return mImportLoader ? mImportLoader->GetImport() : nullptr;
+  return mImportLoader ? nsRefPtr<nsIDocument>(mImportLoader->GetImport()).forget() : nullptr;
 }
 
 } // namespace dom
 } // namespace mozilla
new file mode 100644
--- /dev/null
+++ b/content/html/content/test/imports/file_importA1.html
@@ -0,0 +1,11 @@
+<!DOCTYPE html>
+<html lang="en-US">
+  <head>
+    <link rel="import" href="file_importA2.html" id="A2" onload="loaded()" onerror="failed()"></link>
+  </head>
+  <body>
+    <script>
+      order.push("A1");
+    </script>
+  </body>
+</html>
\ No newline at end of file
new file mode 100644
--- /dev/null
+++ b/content/html/content/test/imports/file_importA2.html
@@ -0,0 +1,10 @@
+<!DOCTYPE html>
+<html lang="en-US">
+  <head>
+  </head>
+  <body>
+    <script>
+      order.push("A2");
+    </script>
+  </body>
+</html>
\ No newline at end of file
new file mode 100644
--- /dev/null
+++ b/content/html/content/test/imports/file_importB1.html
@@ -0,0 +1,11 @@
+<!DOCTYPE html>
+<html lang="en-US">
+  <head>
+    <link rel="import" href="file_importB2.html" id="B2" onload="loaded()" onerror="failed()"></link>
+  </head>
+  <body>
+    <script>
+      order.push("B1");
+    </script>
+  </body>
+</html>
\ No newline at end of file
new file mode 100644
--- /dev/null
+++ b/content/html/content/test/imports/file_importB2.html
@@ -0,0 +1,10 @@
+<!DOCTYPE html>
+<html lang="en-US">
+  <head>
+  </head>
+  <body>
+    <script>
+      order.push("B2");
+    </script>
+  </body>
+</html>
\ No newline at end of file
new file mode 100644
--- /dev/null
+++ b/content/html/content/test/imports/file_importC1.html
@@ -0,0 +1,11 @@
+<!DOCTYPE html>
+<html lang="en-US">
+  <head>
+    <link rel="import" href="file_importC2.html" onload="loaded()" onerror="failed()"></link>
+  </head>
+  <body>
+    <script>
+      order.push("C1");
+    </script>
+  </body>
+</html>
\ No newline at end of file
new file mode 100644
--- /dev/null
+++ b/content/html/content/test/imports/file_importC10.html
@@ -0,0 +1,11 @@
+<!DOCTYPE html>
+<html lang="en-US">
+  <head>
+    <link rel="import" href="file_importE.html" onload="loaded()" onerror="failed()"></link>
+  </head>
+  <body>
+    <script>
+      order.push("C10");
+    </script>
+  </body>
+</html>
\ No newline at end of file
new file mode 100644
--- /dev/null
+++ b/content/html/content/test/imports/file_importC2.html
@@ -0,0 +1,11 @@
+<!DOCTYPE html>
+<html lang="en-US">
+  <head>
+    <link rel="import" href="file_importC3.html" onload="loaded()" onerror="failed()"></link>
+  </head>
+  <body>
+    <script>
+      order.push("C2");
+    </script>
+  </body>
+</html>
\ No newline at end of file
new file mode 100644
--- /dev/null
+++ b/content/html/content/test/imports/file_importC3.html
@@ -0,0 +1,11 @@
+<!DOCTYPE html>
+<html lang="en-US">
+  <head>
+    <link rel="import" href="file_importC4.html" onload="loaded()" onerror="failed()"></link>
+  </head>
+  <body>
+    <script>
+      order.push("C3");
+    </script>
+  </body>
+</html>
\ No newline at end of file
new file mode 100644
--- /dev/null
+++ b/content/html/content/test/imports/file_importC4.html
@@ -0,0 +1,11 @@
+<!DOCTYPE html>
+<html lang="en-US">
+  <head>
+    <link rel="import" href="file_importC5.html" onload="loaded()" onerror="failed()"></link>
+  </head>
+  <body>
+    <script>
+      order.push("C4");
+    </script>
+  </body>
+</html>
\ No newline at end of file
new file mode 100644
--- /dev/null
+++ b/content/html/content/test/imports/file_importC5.html
@@ -0,0 +1,11 @@
+<!DOCTYPE html>
+<html lang="en-US">
+  <head>
+    <link rel="import" href="file_importC6.html" onload="loaded()" onerror="failed()"></link>
+  </head>
+  <body>
+    <script>
+      order.push("C5");
+    </script>
+  </body>
+</html>
\ No newline at end of file
new file mode 100644
--- /dev/null
+++ b/content/html/content/test/imports/file_importC6.html
@@ -0,0 +1,11 @@
+<!DOCTYPE html>
+<html lang="en-US">
+  <head>
+    <link rel="import" href="file_importC7.html" onload="loaded()" onerror="failed()"></link>
+  </head>
+  <body>
+    <script>
+      order.push("C6");
+    </script>
+  </body>
+</html>
\ No newline at end of file
new file mode 100644
--- /dev/null
+++ b/content/html/content/test/imports/file_importC7.html
@@ -0,0 +1,11 @@
+<!DOCTYPE html>
+<html lang="en-US">
+  <head>
+    <link rel="import" href="file_importC8.html" onload="loaded()" onerror="failed()"></link>
+  </head>
+  <body>
+    <script>
+      order.push("C7");
+    </script>
+  </body>
+</html>
\ No newline at end of file
new file mode 100644
--- /dev/null
+++ b/content/html/content/test/imports/file_importC8.html
@@ -0,0 +1,11 @@
+<!DOCTYPE html>
+<html lang="en-US">
+  <head>
+    <link rel="import" href="file_importC9.html" onload="loaded()" onerror="failed()"></link>
+  </head>
+  <body>
+    <script>
+      order.push("C8");
+    </script>
+  </body>
+</html>
\ No newline at end of file
new file mode 100644
--- /dev/null
+++ b/content/html/content/test/imports/file_importC9.html
@@ -0,0 +1,11 @@
+<!DOCTYPE html>
+<html lang="en-US">
+  <head>
+    <link rel="import" href="file_importC10.html" onload="loaded()" onerror="failed()"></link>
+  </head>
+  <body>
+    <script>
+      order.push("C9");
+    </script>
+  </body>
+</html>
\ No newline at end of file
new file mode 100644
--- /dev/null
+++ b/content/html/content/test/imports/file_importD.html
@@ -0,0 +1,8 @@
+<!DOCTYPE html>
+<html lang="en-US">
+  <body>
+    <script>
+      order.push("D");
+    </script>
+  </body>
+</html>
\ No newline at end of file
new file mode 100644
--- /dev/null
+++ b/content/html/content/test/imports/file_importE.html
@@ -0,0 +1,11 @@
+<!DOCTYPE html>
+<html lang="en-US">
+  <head>
+    <link rel="import" href="file_importD.html" onload="loaded()" onerror="failed()"></link>
+  </head>
+  <body>
+    <script>
+      order.push("E");
+    </script>
+  </body>
+</html>
\ No newline at end of file
new file mode 100644
--- /dev/null
+++ b/content/html/content/test/imports/mochitest.ini
@@ -0,0 +1,20 @@
+[DEFAULT]
+support-files =
+  file_importA1.html
+  file_importA2.html
+  file_importB1.html
+  file_importB2.html
+  file_importC1.html
+  file_importC2.html
+  file_importC3.html
+  file_importC4.html
+  file_importC5.html
+  file_importC6.html
+  file_importC7.html
+  file_importC8.html
+  file_importC9.html
+  file_importC10.html
+  file_importD.html
+  file_importE.html
+
+
--- a/content/html/content/test/mochitest.ini
+++ b/content/html/content/test/mochitest.ini
@@ -458,16 +458,20 @@ skip-if = buildapp == 'b2g' || e10s # b2
 [test_iframe_sandbox_redirect.html]
 [test_iframe_sandbox_same_origin.html]
 [test_iframe_sandbox_workers.html]
 [test_img_attributes_reflection.html]
 [test_imageSrcSet.html]
 [test_imports_basics.html]
 [test_imports_redirect.html]
 [test_imports_nonhttp.html]
+[test_imports_nested.html]
+skip-if = toolkit == 'gonk' # nested imports fail on b2g emulator
+[test_imports_nested_2.html]
+skip-if = toolkit == 'gonk' # nested imports fail on b2g emulator
 [test_li_attributes_reflection.html]
 [test_link_attributes_reflection.html]
 [test_link_sizes.html]
 [test_map_attributes_reflection.html]
 [test_meta_attributes_reflection.html]
 [test_mod_attributes_reflection.html]
 [test_mozaudiochannel.html]
 skip-if = buildapp == 'mulet' || (buildapp == 'b2g' && (toolkit != 'gonk' || debug)) # b2g-debug(Perma-orange on debug emulator) b2g-desktop(Bug 931116, b2g desktop specific, initial triage)
new file mode 100644
--- /dev/null
+++ b/content/html/content/test/test_imports_nested.html
@@ -0,0 +1,41 @@
+<!DOCTYPE HTML>
+<html>
+<!--
+https://bugzilla.mozilla.org/show_bug.cgi?id=877072
+-->
+<head>
+  <title>Test for Bug 877072</title>
+  <script type="text/javascript" src="/tests/SimpleTest/SimpleTest.js"></script>
+  <link rel="stylesheet" type="text/css" href="/tests/SimpleTest/test.css" />
+  <meta http-equiv="Content-Type" content="text/html;charset=utf-8">
+</head>
+<body>
+  <a target="_blank" href="https://bugzilla.mozilla.org/show_bug.cgi?id=877072">Mozilla Bug 877072</a>
+
+  <script type="text/javascript">
+    SimpleTest.waitForExplicitFinish();
+    var counter = 0;
+    var fcounter = 0;
+    var order = [];
+    function loaded() {
+      counter++;
+    }
+    function failed() {
+      fcounter++;
+    }
+  </script>
+
+  <link rel="import" href="imports/file_importA1.html" id="A1" onload="loaded()" onerror="failed()"></link>
+  <link rel="import" href="imports/file_importB1.html" id="B1" onload="loaded()" onerror="failed()"></link>
+  <link rel="import" href="imports/file_importB2.html" id="B2_2" onload="loaded()" onerror="failed()"></link>
+
+  <script type="text/javascript">
+    is(counter, 5, "Imports are loaded");
+    is(fcounter, 0, "No error in imports");
+    var expected = ["A2", "A1", "B2", "B1"];
+    for (i in expected)
+      is(order[i], expected[i], "import " + i + " should be " + expected[i]);
+    SimpleTest.finish();
+  </script>
+</body>
+</html>
new file mode 100644
--- /dev/null
+++ b/content/html/content/test/test_imports_nested_2.html
@@ -0,0 +1,56 @@
+<!DOCTYPE HTML>
+<html>
+<!--
+https://bugzilla.mozilla.org/show_bug.cgi?id=877072
+-->
+<head>
+  <title>Test for Bug 877072</title>
+  <script type="text/javascript" src="/tests/SimpleTest/SimpleTest.js"></script>
+  <link rel="stylesheet" type="text/css" href="/tests/SimpleTest/test.css" />
+  <meta http-equiv="Content-Type" content="text/html;charset=utf-8">
+</head>
+<body>
+  <a target="_blank" href="https://bugzilla.mozilla.org/show_bug.cgi?id=877072">Mozilla Bug 877072</a>
+
+  <script type="text/javascript">
+    SimpleTest.waitForExplicitFinish();
+    var counter = 0;
+    var fcounter = 0;
+    var order = [];
+    function loaded() {
+      counter++;
+    }
+    function failed() {
+      fcounter++;
+    }
+  </script>
+
+<!--
+
+Master -> c1 -> ... -> C10
+|  |                    |
+|  - - -> D             |
+|         ^             |
+|         |             |
+ - - - -> E < - - - - - -
+
+This test is for testing ImportLoader::UpdateDependants.Because of the long
+chain to C10, it's very likely that C10->E will be the last edge the ImportLoaders
+find. At that point it won't only have to update E but also its subimport D.
+
+-->
+
+  <link rel="import" href="imports/file_importC1.html" onload="loaded()" onerror="failed()"></link>
+  <link rel="import" href="imports/file_importD.html" onload="loaded()" onerror="failed()"></link>
+  <link rel="import" href="imports/file_importE.html" onload="loaded()" onerror="failed()"></link>
+
+  <script type="text/javascript">
+    is(counter, 14, "Imports are loaded"); // 12 imports but 14 link imports...
+    is(fcounter, 0, "No error in imports");
+    var expected = ["D", "E", "C10", "C9", "C8", "C7", "C6", "C5", "C4", "C3", "C2", "C1"];
+    for (i in expected)
+      is(order[i], expected[i], "import " + i + " should be " + expected[i]);
+    SimpleTest.finish();
+  </script>
+</body>
+</html>
deleted file mode 100644
--- a/testing/web-platform/meta/html-imports/fetching/already-in-import-map.html.ini
+++ /dev/null
@@ -1,5 +0,0 @@
-[already-in-import-map.html]
-  type: testharness
-  [If LOCATION is already in the import map, let IMPORT be the imported document for LOCATION and stop. (2)]
-    expected: FAIL
-