Bug 1404789 - Stop reconstructing frames for the whole shadow root each time content is inserted in a shadow tree

* Cleanup a bit the ShadowRoot code
* Privatize ShadowRoot methods
* When the shadow tree distribution changes, post a restyle + reframe
* Simplify ShadowRoot::IsPooledNode
* Be a bit better at detecting distribution changes

Tag #1375

7 files changed, 243 insertions, 137 deletions

diff --git a/dom/base/ShadowRoot.cpp b/dom/base/ShadowRoot.cpp
index c9bd58d53a..f19cad6df9 100644
--- a/dom/base/ShadowRoot.cpp
+++ b/dom/base/ShadowRoot.cpp
@@ -79,10 +79,10 @@ ShadowRoot::ShadowRoot(Element* aElement,
 
 ShadowRoot::~ShadowRoot()
 {
-  if (GetHost()) {
-    // mPoolHost may have been unlinked or a new ShadowRoot may have been
-    // creating, making this one obsolete.
-    GetHost()->RemoveMutationObserver(this);
+  if (auto* host = GetHost()) {
+    // mHost may have been unlinked or a new ShadowRoot may have been
+    // created, making this one obsolete.
+    host->RemoveMutationObserver(this);
   }
 
   UnsetFlags(NODE_IS_IN_SHADOW_TREE);
@@ -114,8 +114,7 @@ ShadowRoot::StyleSheetChanged()
 {
   mProtoBinding->FlushSkinSheets();
 
-  nsIPresShell* shell = OwnerDoc()->GetShell();
-  if (shell) {
+  if (nsIPresShell* shell = OwnerDoc()->GetShell()) {
     OwnerDoc()->BeginUpdate(UPDATE_STYLE);
     shell->RecordShadowStyleChange(this);
     OwnerDoc()->EndUpdate(UPDATE_STYLE);
@@ -253,96 +252,106 @@ ShadowRoot::RemoveDestInsertionPoint(nsIContent* aInsertionPoint,
 }
 
 void
+ShadowRoot::DistributionChanged()
+{
+  // FIXME(emilio): We could be more granular in a bunch of cases.
+  auto* host = GetHost();
+  if (!host || !host->IsInComposedDoc()) {
+    return;
+  }
+
+  auto* shell = OwnerDoc()->GetShell();
+  if (!shell) {
+    return;
+  }
+
+  // FIXME(emilio): Rename this to DestroyFramesForAndRestyle?
+  shell->DestroyFramesFor(host);
+}
+
+const HTMLContentElement*
 ShadowRoot::DistributeSingleNode(nsIContent* aContent)
 {
   // Find the insertion point to which the content belongs.
-  HTMLContentElement* insertionPoint = nullptr;
-  for (uint32_t i = 0; i < mInsertionPoints.Length(); i++) {
-    if (mInsertionPoints[i]->Match(aContent)) {
-      if (mInsertionPoints[i]->MatchedNodes().Contains(aContent)) {
+  HTMLContentElement* foundInsertionPoint = nullptr;
+  for (HTMLContentElement* insertionPoint : mInsertionPoints) {
+    if (insertionPoint->Match(aContent)) {
+      if (insertionPoint->MatchedNodes().Contains(aContent)) {
         // Node is already matched into the insertion point. We are done.
-        return;
+        return insertionPoint;
       }
 
       // Matching may cause the insertion point to drop fallback content.
-      if (mInsertionPoints[i]->MatchedNodes().IsEmpty() &&
-          static_cast<nsINode*>(mInsertionPoints[i])->GetFirstChild()) {
+      if (insertionPoint->MatchedNodes().IsEmpty() &&
+          insertionPoint->HasChildren()) {
         // This match will cause the insertion point to drop all fallback
         // content and used matched nodes instead. Give up on the optimization
         // and just distribute all nodes.
         DistributeAllNodes();
-        return;
+        MOZ_ASSERT(insertionPoint->MatchedNodes().Contains(aContent));
+        return insertionPoint;
       }
-      insertionPoint = mInsertionPoints[i];
+      foundInsertionPoint = insertionPoint;
       break;
     }
   }
 
-  // Find the index into the insertion point.
-  if (insertionPoint) {
-    nsCOMArray<nsIContent>& matchedNodes = insertionPoint->MatchedNodes();
-    // Find the appropriate position in the matched node list for the
-    // newly distributed content.
-    bool isIndexFound = false;
-    ExplicitChildIterator childIterator(GetHost());
-    for (uint32_t i = 0; i < matchedNodes.Length(); i++) {
-      // Seek through the host's explicit children until the inserted content
-      // is found or when the current matched node is reached.
-      if (childIterator.Seek(aContent, matchedNodes[i])) {
-        // aContent was found before the current matched node.
-        insertionPoint->InsertMatchedNode(i, aContent);
-        isIndexFound = true;
-        break;
-      }
-    }
+  if (!foundInsertionPoint) {
+    return nullptr;
+  }
 
-    if (!isIndexFound) {
-      // We have still not found an index in the insertion point,
-      // thus it must be at the end.
-      MOZ_ASSERT(childIterator.Seek(aContent, nullptr),
-                 "Trying to match a node that is not a candidate to be matched");
-      insertionPoint->AppendMatchedNode(aContent);
+  // Find the index into the insertion point.
+  nsCOMArray<nsIContent>& matchedNodes = foundInsertionPoint->MatchedNodes();
+  // Find the appropriate position in the matched node list for the
+  // newly distributed content.
+  bool isIndexFound = false;
+  ExplicitChildIterator childIterator(GetHost());
+  for (uint32_t i = 0; i < matchedNodes.Length(); i++) {
+    // Seek through the host's explicit children until the inserted content
+    // is found or when the current matched node is reached.
+    if (childIterator.Seek(aContent, matchedNodes[i])) {
+      // aContent was found before the current matched node.
+      foundInsertionPoint->InsertMatchedNode(i, aContent);
+      isIndexFound = true;
+      break;
     }
+  }
 
-    // Handle the case where the parent of the insertion point has a ShadowRoot.
-    // The node distributed into the insertion point must be reprojected to the
-    // insertion points of the parent's ShadowRoot.
-    ShadowRoot* parentShadow = insertionPoint->GetParent()->GetShadowRoot();
-    if (parentShadow) {
-      parentShadow->DistributeSingleNode(aContent);
-    }
+  if (!isIndexFound) {
+    // We have still not found an index in the insertion point,
+    // thus it must be at the end.
+    MOZ_ASSERT(childIterator.Seek(aContent, nullptr),
+               "Trying to match a node that is not a candidate to be matched");
+    foundInsertionPoint->AppendMatchedNode(aContent);
   }
+
+  return foundInsertionPoint;
 }
 
-void
+const HTMLContentElement*
 ShadowRoot::RemoveDistributedNode(nsIContent* aContent)
 {
   // Find insertion point containing the content and remove the node.
-  for (uint32_t i = 0; i < mInsertionPoints.Length(); i++) {
-    if (mInsertionPoints[i]->MatchedNodes().Contains(aContent)) {
-      // Removing the matched node may cause the insertion point to use
-      // fallback content.
-      if (mInsertionPoints[i]->MatchedNodes().Length() == 1 &&
-          static_cast<nsINode*>(mInsertionPoints[i])->GetFirstChild()) {
-        // Removing the matched node will cause fallback content to be
-        // used instead. Give up optimization and distribute all nodes.
-        DistributeAllNodes();
-        return;
-      }
-
-      mInsertionPoints[i]->RemoveMatchedNode(aContent);
-
-      // Handle the case where the parent of the insertion point has a ShadowRoot.
-      // The removed node needs to be removed from the insertion points of the
-      // parent's ShadowRoot.
-      ShadowRoot* parentShadow = mInsertionPoints[i]->GetParent()->GetShadowRoot();
-      if (parentShadow) {
-        parentShadow->RemoveDistributedNode(aContent);
-      }
+  for (HTMLContentElement* insertionPoint : mInsertionPoints) {
+    if (!insertionPoint->MatchedNodes().Contains(aContent)) {
+      continue;
+    }
 
-      break;
+    // Removing the matched node may cause the insertion point to use
+    // fallback content.
+    if (insertionPoint->MatchedNodes().Length() == 1 &&
+        insertionPoint->HasChildren()) {
+      // Removing the matched node will cause fallback content to be
+      // used instead. Give up optimization and distribute all nodes.
+      DistributeAllNodes();
+      return insertionPoint;
     }
+
+    insertionPoint->RemoveMatchedNode(aContent);
+    return insertionPoint;
   }
+
+  return nullptr;
 }
 
 void
@@ -358,19 +367,19 @@ ShadowRoot::DistributeAllNodes()
 
   nsTArray<ShadowRoot*> shadowsToUpdate;
 
-  for (uint32_t i = 0; i < mInsertionPoints.Length(); i++) {
-    mInsertionPoints[i]->ClearMatchedNodes();
+  for (HTMLContentElement* insertionPoint : mInsertionPoints) {
+    insertionPoint->ClearMatchedNodes();
     // Assign matching nodes from node pool.
     for (uint32_t j = 0; j < nodePool.Length(); j++) {
-      if (mInsertionPoints[i]->Match(nodePool[j])) {
-        mInsertionPoints[i]->AppendMatchedNode(nodePool[j]);
+      if (insertionPoint->Match(nodePool[j])) {
+        insertionPoint->AppendMatchedNode(nodePool[j]);
         nodePool.RemoveElementAt(j--);
       }
     }
 
     // Keep track of instances where the content insertion point is distributed
     // (parent of insertion point has a ShadowRoot).
-    nsIContent* insertionParent = mInsertionPoints[i]->GetParent();
+    nsIContent* insertionParent = insertionPoint->GetParent();
     MOZ_ASSERT(insertionParent, "The only way for an insertion point to be in the"
                                 "mInsertionPoints array is to be a descendant of a"
                                 "ShadowRoot, in which case, it should have a parent");
@@ -384,9 +393,11 @@ ShadowRoot::DistributeAllNodes()
     }
   }
 
-  for (uint32_t i = 0; i < shadowsToUpdate.Length(); i++) {
-    shadowsToUpdate[i]->DistributeAllNodes();
+  for (ShadowRoot* shadow : shadowsToUpdate) {
+    shadow->DistributeAllNodes();
   }
+
+  DistributionChanged();
 }
 
 void
@@ -447,16 +458,16 @@ ShadowRoot::StyleSheets()
  * test nodes that have not yet been distributed.
  */
 bool
-ShadowRoot::IsPooledNode(nsIContent* aContent, nsIContent* aContainer,
-                         nsIContent* aHost)
+ShadowRoot::IsPooledNode(nsIContent* aContent) const
 {
   if (nsContentUtils::IsContentInsertionPoint(aContent)) {
     // Insertion points never end up in the pool.
     return false;
   }
 
-  if (aContainer == aHost &&
-      nsContentUtils::IsInSameAnonymousTree(aContainer, aContent)) {
+  auto* host = GetHost();
+  auto* container = aContent->GetParent();
+  if (container == host && !aContent->IsRootOfAnonymousSubtree()) {
     // Children of the host will end up in the pool. We check to ensure
     // that the content is in the same anonymous tree as the container
     // because anonymous content may report its container as the host
@@ -464,12 +475,11 @@ ShadowRoot::IsPooledNode(nsIContent* aContent, nsIContent* aContainer,
     return true;
   }
 
-  if (aContainer) {
+  if (auto* content = HTMLContentElement::FromContentOrNull(container)) {
     // Fallback content will end up in pool if its parent is a child of the host.
-    HTMLContentElement* content = HTMLContentElement::FromContent(aContainer);
-    return content && content->IsInsertionPoint() &&
+    return content->IsInsertionPoint() &&
            content->MatchedNodes().IsEmpty() &&
-           aContainer->GetParentNode() == aHost;
+           container->GetParentNode() == host;
   }
 
   return false;
@@ -483,44 +493,82 @@ ShadowRoot::AttributeChanged(nsIDocument* aDocument,
                              int32_t aModType,
                              const nsAttrValue* aOldValue)
 {
-  if (!IsPooledNode(aElement, aElement->GetParent(), GetHost())) {
+  if (!IsPooledNode(aElement)) {
     return;
   }
 
   // Attributes may change insertion point matching, find its new distribution.
-  RemoveDistributedNode(aElement);
-  DistributeSingleNode(aElement);
-}
+  //
+  // FIXME(emilio): What about state changes?
+  if (!RedistributeElement(aElement)) {
+    return;
+  }
 
-void
-ShadowRoot::ContentAppended(nsIDocument* aDocument,
-                            nsIContent* aContainer,
-                            nsIContent* aFirstNewContent,
-                            int32_t aNewIndexInContainer)
-{
-  if (mInsertionPointChanged) {
-    DistributeAllNodes();
-    mInsertionPointChanged = false;
+  if (!aElement->IsInComposedDoc()) {
     return;
   }
 
-  // Watch for new nodes added to the pool because the node
-  // may need to be added to an insertion point.
-  nsIContent* currentChild = aFirstNewContent;
-  while (currentChild) {
-    // Add insertion point to destination insertion points of fallback content.
-    if (nsContentUtils::IsContentInsertionPoint(aContainer)) {
-      HTMLContentElement* content = HTMLContentElement::FromContent(aContainer);
-      if (content->MatchedNodes().IsEmpty()) {
-        currentChild->DestInsertionPoints().AppendElement(aContainer);
+  auto* shell = OwnerDoc()->GetShell();
+  if (!shell) {
+    return;
+  }
+
+  shell->DestroyFramesFor(aElement);
+}
+
+bool
+ShadowRoot::RedistributeElement(Element* aElement)
+{
+  auto* oldInsertionPoint = RemoveDistributedNode(aElement);
+  auto* newInsertionPoint = DistributeSingleNode(aElement);
+
+  if (oldInsertionPoint == newInsertionPoint) {
+    if (oldInsertionPoint) {
+      if (auto* shadow = oldInsertionPoint->GetParent()->GetShadowRoot()) {
+        return shadow->RedistributeElement(aElement);
       }
     }
 
-    if (IsPooledNode(currentChild, aContainer, GetHost())) {
-      DistributeSingleNode(currentChild);
+    return false;
+  }
+
+  while (oldInsertionPoint) {
+    // Handle the case where the parent of the insertion point has a ShadowRoot.
+    // The node distributed into the insertion point must be reprojected to the
+    // insertion points of the parent's ShadowRoot.
+    auto* shadow = oldInsertionPoint->GetParent()->GetShadowRoot();
+    if (!shadow) {
+      break;
+    }
+
+    oldInsertionPoint = shadow->RemoveDistributedNode(aElement);
+  }
+
+  while (newInsertionPoint) {
+    // Handle the case where the parent of the insertion point has a ShadowRoot.
+    // The node distributed into the insertion point must be reprojected to the
+    // insertion points of the parent's ShadowRoot.
+    auto* shadow = newInsertionPoint->GetParent()->GetShadowRoot();
+    if (!shadow) {
+      break;
     }
 
-    currentChild = currentChild->GetNextSibling();
+    newInsertionPoint = shadow->DistributeSingleNode(aElement);
+  }
+
+  return true;
+}
+
+void
+ShadowRoot::ContentAppended(nsIDocument* aDocument,
+                            nsIContent* aContainer,
+                            nsIContent* aFirstNewContent,
+                            int32_t aNewIndexInContainer)
+{
+  for (nsIContent* content = aFirstNewContent;
+       content;
+       content = content->GetNextSibling()) {
+    ContentInserted(aDocument, aContainer, aFirstNewContent, aNewIndexInContainer);
   }
 }
 
@@ -536,18 +584,29 @@ ShadowRoot::ContentInserted(nsIDocument* aDocument,
     return;
   }
 
+  // Add insertion point to destination insertion points of fallback content.
+  if (nsContentUtils::IsContentInsertionPoint(aContainer)) {
+    HTMLContentElement* content = HTMLContentElement::FromContent(aContainer);
+    if (content && content->MatchedNodes().IsEmpty()) {
+      aChild->DestInsertionPoints().AppendElement(aContainer);
+    }
+  }
+
   // Watch for new nodes added to the pool because the node
   // may need to be added to an insertion point.
-  if (IsPooledNode(aChild, aContainer, GetHost())) {
-    // Add insertion point to destination insertion points of fallback content.
-    if (nsContentUtils::IsContentInsertionPoint(aContainer)) {
-      HTMLContentElement* content = HTMLContentElement::FromContent(aContainer);
-      if (content->MatchedNodes().IsEmpty()) {
-        aChild->DestInsertionPoints().AppendElement(aContainer);
+  if (IsPooledNode(aChild)) {
+    auto* insertionPoint = DistributeSingleNode(aChild);
+    while (insertionPoint) {
+      // Handle the case where the parent of the insertion point has a ShadowRoot.
+      // The node distributed into the insertion point must be reprojected to the
+      // insertion points of the parent's ShadowRoot.
+      auto* parentShadow = insertionPoint->GetParent()->GetShadowRoot();
+      if (!parentShadow) {
+        break;
       }
-    }
 
-    DistributeSingleNode(aChild);
+      insertionPoint = parentShadow->DistributeSingleNode(aChild);
+    }
   }
 }
 
@@ -575,8 +634,21 @@ ShadowRoot::ContentRemoved(nsIDocument* aDocument,
 
   // Watch for node that is removed from the pool because
   // it may need to be removed from an insertion point.
-  if (IsPooledNode(aChild, aContainer, GetHost())) {
-    RemoveDistributedNode(aChild);
+  if (IsPooledNode(aChild)) {
+    auto* insertionPoint = RemoveDistributedNode(aChild);
+    while (insertionPoint) {
+      // Handle the case where the parent of the insertion point has a
+      // ShadowRoot.
+      //
+      // The removed node needs to be removed from the insertion points of the
+      // parent's ShadowRoot.
+      auto* parentShadow = insertionPoint->GetParent()->GetShadowRoot();
+      if (!parentShadow) {
+        break;
+      }
+
+      insertionPoint = parentShadow->RemoveDistributedNode(aChild);
+    }
   }
 }
 
diff --git a/dom/base/ShadowRoot.h b/dom/base/ShadowRoot.h
index 04943752be..42423c92e3 100644
--- a/dom/base/ShadowRoot.h
+++ b/dom/base/ShadowRoot.h
@@ -54,23 +54,48 @@ public:
   StyleSheetList* StyleSheets();
 
   /**
+   * Distributes all the explicit children of the pool host to the content
+   * insertion points in this ShadowRoot.
+   */
+  void DistributeAllNodes();
+
+private:
+  /**
    * Distributes a single explicit child of the pool host to the content
    * insertion points in this ShadowRoot.
+   *
+   * Returns the insertion point the element is distributed to after this call.
+   *
+   * Note that this doesn't handle distributing the node in the insertion point
+   * parent's shadow root.
    */
-  void DistributeSingleNode(nsIContent* aContent);
+  const HTMLContentElement* DistributeSingleNode(nsIContent* aContent);
 
   /**
    * Removes a single explicit child of the pool host from the content
    * insertion points in this ShadowRoot.
+   *
+   * Returns the old insertion point, if any.
+   *
+   * Note that this doesn't handle removing the node in the returned insertion
+   * point parent's shadow root.
    */
-  void RemoveDistributedNode(nsIContent* aContent);
+  const HTMLContentElement* RemoveDistributedNode(nsIContent* aContent);
 
   /**
-   * Distributes all the explicit children of the pool host to the content
-   * insertion points in this ShadowRoot.
+   * Redistributes a node of the pool, and returns whether the distribution
+   * changed.
    */
-  void DistributeAllNodes();
+  bool RedistributeElement(Element*);
 
+  /**
+   * Called when we redistribute content after insertion points have changed.
+   */
+  void DistributionChanged();
+
+  bool IsPooledNode(nsIContent* aChild) const;
+
+public:
   void AddInsertionPoint(HTMLContentElement* aInsertionPoint);
   void RemoveInsertionPoint(HTMLContentElement* aInsertionPoint);
 
@@ -80,8 +105,6 @@ public:
 
   JSObject* WrapObject(JSContext* aCx, JS::Handle<JSObject*> aGivenProto) override;
 
-  static bool IsPooledNode(nsIContent* aChild, nsIContent* aContainer,
-                           nsIContent* aHost);
   static ShadowRoot* FromNode(nsINode* aNode);
 
   static void RemoveDestInsertionPoint(nsIContent* aInsertionPoint,
diff --git a/dom/html/HTMLContentElement.cpp b/dom/html/HTMLContentElement.cpp
index 158f8d0ce9..15d79c761a 100644
--- a/dom/html/HTMLContentElement.cpp
+++ b/dom/html/HTMLContentElement.cpp
@@ -248,8 +248,7 @@ HTMLContentElement::AfterSetAttr(int32_t aNamespaceID, nsIAtom* aName,
         }
       }
 
-      ShadowRoot* containingShadow = GetContainingShadow();
-      if (containingShadow) {
+      if (ShadowRoot* containingShadow = GetContainingShadow()) {
         containingShadow->DistributeAllNodes();
       }
     } else {
@@ -258,8 +257,7 @@ HTMLContentElement::AfterSetAttr(int32_t aNamespaceID, nsIAtom* aName,
       mValidSelector = true;
       mSelectorList = nullptr;
 
-      ShadowRoot* containingShadow = GetContainingShadow();
-      if (containingShadow) {
+      if (ShadowRoot* containingShadow = GetContainingShadow()) {
         containingShadow->DistributeAllNodes();
       }
     }
diff --git a/dom/html/HTMLContentElement.h b/dom/html/HTMLContentElement.h
index d2491a7928..630e26d17d 100644
--- a/dom/html/HTMLContentElement.h
+++ b/dom/html/HTMLContentElement.h
@@ -29,14 +29,7 @@ public:
   NS_DECL_CYCLE_COLLECTION_CLASS_INHERITED(HTMLContentElement,
                                            nsGenericHTMLElement)
 
-  static HTMLContentElement* FromContent(nsIContent* aContent)
-  {
-    if (aContent->IsHTMLContentElement()) {
-      return static_cast<HTMLContentElement*>(aContent);
-    }
-
-    return nullptr;
-  }
+  NS_IMPL_FROMCONTENT_HELPER(HTMLContentElement, IsHTMLContentElement())
 
   virtual bool IsHTMLContentElement() const override { return true; }
 
diff --git a/layout/base/crashtests/1404789-1.html b/layout/base/crashtests/1404789-1.html
new file mode 100644
index 0000000000..bd577ae24d
--- /dev/null
+++ b/layout/base/crashtests/1404789-1.html
@@ -0,0 +1,16 @@
+<!doctype html>
+<script>
+  // Test for content redistribution outside of the document.
+  // Passes if it doesn't assert.
+  let host = document.createElement('div');
+  host.innerHTML = "<div id='foo'></div>";
+
+  let shadowRoot = host.createShadowRoot();
+  shadowRoot.innerHTML = "<content select='#foo'></content>";
+
+  host.firstElementChild.removeAttribute('id');
+
+  // Move to the document, do the same.
+  document.documentElement.appendChild(host);
+  host.firstElementChild.setAttribute('id', 'foo');
+</script>
diff --git a/layout/base/crashtests/1404789-2.html b/layout/base/crashtests/1404789-2.html
new file mode 100644
index 0000000000..667618141b
--- /dev/null
+++ b/layout/base/crashtests/1404789-2.html
@@ -0,0 +1,2 @@
+<!doctype html>
+<iframe style="display: none" src="1404789-1.html"></iframe>
diff --git a/layout/base/crashtests/crashtests.list b/layout/base/crashtests/crashtests.list
index 6ded4ff3f2..66dc35ebcc 100644
--- a/layout/base/crashtests/crashtests.list
+++ b/layout/base/crashtests/crashtests.list
@@ -483,3 +483,5 @@ load 1308793.svg
 load 1308848-1.html
 load 1308848-2.html
 asserts(0-1) load 1343606.html # bug 1343948
+load 1404789-1.html
+load 1404789-2.html