1 files changed, 243 insertions, 40 deletions

diff --git a/dom/base/ContentIterator.cpp b/dom/base/ContentIterator.cpp
index 6819353520..0b405f0348 100644
--- a/dom/base/ContentIterator.cpp
+++ b/dom/base/ContentIterator.cpp
@@ -7,6 +7,7 @@
 #include "ContentIterator.h"
 
 #include "mozilla/Assertions.h"
+#include "mozilla/dom/ShadowRoot.h"
 #include "mozilla/DebugOnly.h"
 #include "mozilla/RangeBoundary.h"
 #include "mozilla/RangeUtils.h"
@@ -26,6 +27,69 @@ using namespace dom;
       __VA_ARGS__);                                                            \
   template aResultType ContentIteratorBase<nsINode*>::aMethodName(__VA_ARGS__)
 
+/**
+ * IteratorHelpers contains the static methods to help extra values
+ * based on whether or not the iterator allows to iterate nodes cross the shadow
+ * boundary.
+ */
+struct IteratorHelpers {
+  IteratorHelpers() = delete;
+
+  static nsINode* GetStartContainer(AbstractRange* aRange,
+                                    bool aAllowCrossShadowBoundary) {
+    MOZ_ASSERT(aRange);
+    return (StaticPrefs::dom_shadowdom_selection_across_boundary_enabled() &&
+            aAllowCrossShadowBoundary)
+               ? aRange->GetMayCrossShadowBoundaryStartContainer()
+               : aRange->GetStartContainer();
+  }
+
+  static int32_t StartOffset(AbstractRange* aRange,
+                             bool aAllowCrossShadowBoundary) {
+    MOZ_ASSERT(aRange);
+    return (StaticPrefs::dom_shadowdom_selection_across_boundary_enabled() &&
+            aAllowCrossShadowBoundary)
+               ? aRange->MayCrossShadowBoundaryStartOffset()
+               : aRange->StartOffset();
+  }
+
+  static nsINode* GetEndContainer(AbstractRange* aRange,
+                                  bool aAllowCrossShadowBoundary) {
+    MOZ_ASSERT(aRange);
+    return (StaticPrefs::dom_shadowdom_selection_across_boundary_enabled() &&
+            aAllowCrossShadowBoundary)
+               ? aRange->GetMayCrossShadowBoundaryEndContainer()
+               : aRange->GetEndContainer();
+  }
+
+  static int32_t EndOffset(AbstractRange* aRange,
+                           bool aAllowCrossShadowBoundary) {
+    MOZ_ASSERT(aRange);
+    return (StaticPrefs::dom_shadowdom_selection_across_boundary_enabled() &&
+            aAllowCrossShadowBoundary)
+               ? aRange->MayCrossShadowBoundaryEndOffset()
+               : aRange->EndOffset();
+  }
+
+  // FIXME(sefeng): This doesn't work with slots / flattened tree.
+  static nsINode* GetParentNode(nsINode& aNode,
+                                bool aAllowCrossShadowBoundary) {
+    return (StaticPrefs::dom_shadowdom_selection_across_boundary_enabled() &&
+            aAllowCrossShadowBoundary)
+               ? aNode.GetParentOrShadowHostNode()
+               : aNode.GetParentNode();
+  }
+
+  static ShadowRoot* GetShadowRoot(const nsINode* aNode,
+                                   bool aAllowCrossShadowBoundary) {
+    MOZ_ASSERT(aNode);
+    return (StaticPrefs::dom_shadowdom_selection_across_boundary_enabled() &&
+            aAllowCrossShadowBoundary)
+               ? aNode->GetShadowRootForSelection()
+               : nullptr;
+  }
+};
+
 static bool ComparePostMode(const RawRangeBoundary& aStart,
                             const RawRangeBoundary& aEnd, nsINode& aNode) {
   nsINode* parent = aNode.GetParentNode();
@@ -541,17 +605,45 @@ nsINode* ContentIteratorBase<NodeType>::GetDeepFirstChild(nsINode* aRoot) {
 // static
 template <typename NodeType>
 nsIContent* ContentIteratorBase<NodeType>::GetDeepFirstChild(
-    nsIContent* aRoot) {
+    nsIContent* aRoot, bool aAllowCrossShadowBoundary) {
   if (NS_WARN_IF(!aRoot)) {
     return nullptr;
   }
 
   nsIContent* node = aRoot;
-  nsIContent* child = node->GetFirstChild();
+  nsIContent* child = nullptr;
+
+  if (ShadowRoot* shadowRoot =
+          IteratorHelpers::GetShadowRoot(node, aAllowCrossShadowBoundary)) {
+    // When finding the deepest child of node, if this node has a
+    // web exposed shadow root, we use this shadow root to find the deepest
+    // child.
+    // If the first candidate should be a slotted content,
+    // shadowRoot->GetFirstChild() should be able to return the <slot> element.
+    // It's probably correct I think. Then it's up to the caller of this
+    // iterator to decide whether to use the slot's assigned nodes or not.
+    MOZ_ASSERT(aAllowCrossShadowBoundary);
+    child = shadowRoot->GetFirstChild();
+  } else {
+    child = node->GetFirstChild();
+  }
 
   while (child) {
     node = child;
-    child = node->GetFirstChild();
+    if (ShadowRoot* shadowRoot =
+            IteratorHelpers::GetShadowRoot(node, aAllowCrossShadowBoundary)) {
+      // When finding the deepest child of node, if this node has a
+      // web exposed shadow root, we use this shadow root to find the deepest
+      // child.
+      // If the first candidate should be a slotted content,
+      // shadowRoot->GetFirstChild() should be able to return the <slot>
+      // element. It's probably correct I think. Then it's up to the caller of
+      // this iterator to decide whether to use the slot's assigned nodes or
+      // not.
+      child = shadowRoot->GetFirstChild();
+    } else {
+      child = node->GetFirstChild();
+    }
   }
 
   return node;
@@ -569,23 +661,41 @@ nsINode* ContentIteratorBase<NodeType>::GetDeepLastChild(nsINode* aRoot) {
 
 // static
 template <typename NodeType>
-nsIContent* ContentIteratorBase<NodeType>::GetDeepLastChild(nsIContent* aRoot) {
+nsIContent* ContentIteratorBase<NodeType>::GetDeepLastChild(
+    nsIContent* aRoot, bool aAllowCrossShadowBoundary) {
   if (NS_WARN_IF(!aRoot)) {
     return nullptr;
   }
 
   nsIContent* node = aRoot;
-  while (node->HasChildren()) {
-    nsIContent* child = node->GetLastChild();
-    node = child;
+
+  ShadowRoot* shadowRoot =
+      IteratorHelpers::GetShadowRoot(node, aAllowCrossShadowBoundary);
+  // FIXME(sefeng): This doesn't work with slots / flattened tree.
+  while (node->HasChildren() || (shadowRoot && shadowRoot->HasChildren())) {
+    if (node->HasChildren()) {
+      node = node->GetLastChild();
+    } else {
+      MOZ_ASSERT(shadowRoot);
+      // If this node doesn't have a child, but it's also a shadow host
+      // that can be selected, we go into this shadow tree.
+      node = shadowRoot->GetLastChild();
+    }
+    shadowRoot =
+        IteratorHelpers::GetShadowRoot(node, aAllowCrossShadowBoundary);
   }
   return node;
 }
 
-// Get the next sibling, or parent's next sibling, or grandpa's next sibling...
+// Get the next sibling, or parent's next sibling, or shadow host's next
+// sibling (when aAllowCrossShadowBoundary is true), or grandpa's next
+// sibling...
+//
 // static
+//
 template <typename NodeType>
-nsIContent* ContentIteratorBase<NodeType>::GetNextSibling(nsINode* aNode) {
+nsIContent* ContentIteratorBase<NodeType>::GetNextSibling(
+    nsINode* aNode, bool aAllowCrossShadowBoundary) {
   if (NS_WARN_IF(!aNode)) {
     return nullptr;
   }
@@ -594,18 +704,32 @@ nsIContent* ContentIteratorBase<NodeType>::GetNextSibling(nsINode* aNode) {
     return next;
   }
 
-  nsINode* parent = aNode->GetParentNode();
+  nsINode* parent =
+      IteratorHelpers::GetParentNode(*aNode, aAllowCrossShadowBoundary);
   if (NS_WARN_IF(!parent)) {
     return nullptr;
   }
 
-  return ContentIteratorBase::GetNextSibling(parent);
+  if (aAllowCrossShadowBoundary) {
+    // This is temporary solution.
+    // For shadow root, instead of getting to the sibling of the parent
+    // directly, we need to get into the light tree of the parent to handle
+    // slotted contents.
+    if (ShadowRoot* shadowRoot = ShadowRoot::FromNode(aNode)) {
+      if (nsIContent* child = parent->GetFirstChild()) {
+        return child;
+      }
+    }
+  }
+
+  return ContentIteratorBase::GetNextSibling(parent, aAllowCrossShadowBoundary);
 }
 
-// Get the prev sibling, or parent's prev sibling, or grandpa's prev sibling...
-// static
+// Get the prev sibling, or parent's prev sibling, or shadow host's prev sibling
+// (when aAllowCrossShadowBoundary is true), or grandpa's prev sibling... static
 template <typename NodeType>
-nsIContent* ContentIteratorBase<NodeType>::GetPrevSibling(nsINode* aNode) {
+nsIContent* ContentIteratorBase<NodeType>::GetPrevSibling(
+    nsINode* aNode, bool aAllowCrossShadowBoundary) {
   if (NS_WARN_IF(!aNode)) {
     return nullptr;
   }
@@ -614,12 +738,13 @@ nsIContent* ContentIteratorBase<NodeType>::GetPrevSibling(nsINode* aNode) {
     return prev;
   }
 
-  nsINode* parent = aNode->GetParentNode();
+  nsINode* parent =
+      IteratorHelpers::GetParentNode(*aNode, aAllowCrossShadowBoundary);
   if (NS_WARN_IF(!parent)) {
     return nullptr;
   }
 
-  return ContentIteratorBase::GetPrevSibling(parent);
+  return ContentIteratorBase::GetPrevSibling(parent, aAllowCrossShadowBoundary);
 }
 
 template <typename NodeType>
@@ -860,19 +985,41 @@ nsresult ContentSubtreeIterator::Init(const RawRangeBoundary& aStartBoundary,
   return InitWithRange();
 }
 
+nsresult ContentSubtreeIterator::InitWithAllowCrossShadowBoundary(
+    AbstractRange* aRange) {
+  MOZ_ASSERT(aRange);
+
+  if (NS_WARN_IF(!aRange->IsPositioned())) {
+    return NS_ERROR_INVALID_ARG;
+  }
+
+  mRange = aRange;
+
+  mAllowCrossShadowBoundary = AllowRangeCrossShadowBoundary::Yes;
+  return InitWithRange();
+}
+
 void ContentSubtreeIterator::CacheInclusiveAncestorsOfEndContainer() {
   mInclusiveAncestorsOfEndContainer.Clear();
-  nsINode* const endContainer = mRange->GetEndContainer();
+  nsINode* const endContainer =
+      IteratorHelpers::GetEndContainer(mRange, IterAllowCrossShadowBoundary());
   nsIContent* endNode =
       endContainer->IsContent() ? endContainer->AsContent() : nullptr;
   while (endNode) {
     mInclusiveAncestorsOfEndContainer.AppendElement(endNode);
-    endNode = endNode->GetParent();
+    // Cross the boundary for contents in shadow tree.
+    nsINode* parent = IteratorHelpers::GetParentNode(
+        *endNode, IterAllowCrossShadowBoundary());
+    if (!parent || !parent->IsContent()) {
+      break;
+    }
+    endNode = parent->AsContent();
   }
 }
 
 nsIContent* ContentSubtreeIterator::DetermineCandidateForFirstContent() const {
-  nsINode* startContainer = mRange->GetStartContainer();
+  nsINode* startContainer = IteratorHelpers::GetStartContainer(
+      mRange, IterAllowCrossShadowBoundary());
   nsIContent* firstCandidate = nullptr;
   // find first node in range
   nsINode* node = nullptr;
@@ -880,9 +1027,14 @@ nsIContent* ContentSubtreeIterator::DetermineCandidateForFirstContent() const {
     // no children, start at the node itself
     node = startContainer;
   } else {
-    nsIContent* child = mRange->GetChildAtStartOffset();
-    MOZ_ASSERT(child ==
-               startContainer->GetChildAt_Deprecated(mRange->StartOffset()));
+    nsIContent* child =
+        IterAllowCrossShadowBoundary()
+            ? mRange->GetMayCrossShadowBoundaryChildAtStartOffset()
+            : mRange->GetChildAtStartOffset();
+
+    MOZ_ASSERT(child == startContainer->GetChildAt_Deprecated(
+                            IteratorHelpers::StartOffset(
+                                mRange, IterAllowCrossShadowBoundary())));
     if (!child) {
       // offset after last child
       node = startContainer;
@@ -893,11 +1045,13 @@ nsIContent* ContentSubtreeIterator::DetermineCandidateForFirstContent() const {
 
   if (!firstCandidate) {
     // then firstCandidate is next node after node
-    firstCandidate = ContentIteratorBase::GetNextSibling(node);
+    firstCandidate = ContentIteratorBase::GetNextSibling(
+        node, IterAllowCrossShadowBoundary());
   }
 
   if (firstCandidate) {
-    firstCandidate = ContentIteratorBase::GetDeepFirstChild(firstCandidate);
+    firstCandidate = ContentIteratorBase::GetDeepFirstChild(
+        firstCandidate, IterAllowCrossShadowBoundary());
   }
 
   return firstCandidate;
@@ -926,9 +1080,12 @@ nsIContent* ContentSubtreeIterator::DetermineFirstContent() const {
 
 nsIContent* ContentSubtreeIterator::DetermineCandidateForLastContent() const {
   nsIContent* lastCandidate{nullptr};
-  nsINode* endContainer = mRange->GetEndContainer();
+  nsINode* endContainer =
+      IteratorHelpers::GetEndContainer(mRange, IterAllowCrossShadowBoundary());
   // now to find the last node
-  int32_t offset = mRange->EndOffset();
+  int32_t offset =
+      IteratorHelpers::EndOffset(mRange, IterAllowCrossShadowBoundary());
+
   int32_t numChildren = endContainer->GetChildCount();
 
   nsINode* node = nullptr;
@@ -939,7 +1096,9 @@ nsIContent* ContentSubtreeIterator::DetermineCandidateForLastContent() const {
   if (!offset || !numChildren) {
     node = endContainer;
   } else {
-    lastCandidate = mRange->EndRef().Ref();
+    lastCandidate = IterAllowCrossShadowBoundary()
+                        ? mRange->MayCrossShadowBoundaryEndRef().Ref()
+                        : mRange->EndRef().Ref();
     MOZ_ASSERT(lastCandidate == endContainer->GetChildAt_Deprecated(--offset));
     NS_ASSERTION(lastCandidate,
                  "tree traversal trouble in ContentSubtreeIterator::Init");
@@ -947,11 +1106,13 @@ nsIContent* ContentSubtreeIterator::DetermineCandidateForLastContent() const {
 
   if (!lastCandidate) {
     // then lastCandidate is prev node before node
-    lastCandidate = ContentIteratorBase::GetPrevSibling(node);
+    lastCandidate = ContentIteratorBase::GetPrevSibling(
+        node, IterAllowCrossShadowBoundary());
   }
 
   if (lastCandidate) {
-    lastCandidate = ContentIteratorBase::GetDeepLastChild(lastCandidate);
+    lastCandidate = ContentIteratorBase::GetDeepLastChild(
+        lastCandidate, IterAllowCrossShadowBoundary());
   }
 
   return lastCandidate;
@@ -962,11 +1123,17 @@ nsresult ContentSubtreeIterator::InitWithRange() {
   MOZ_ASSERT(mRange->IsPositioned());
 
   // get the start node and offset, convert to nsINode
-  mClosestCommonInclusiveAncestor = mRange->GetClosestCommonInclusiveAncestor();
-  nsINode* startContainer = mRange->GetStartContainer();
-  const int32_t startOffset = mRange->StartOffset();
-  nsINode* endContainer = mRange->GetEndContainer();
-  const int32_t endOffset = mRange->EndOffset();
+  mClosestCommonInclusiveAncestor =
+      mRange->GetClosestCommonInclusiveAncestor(mAllowCrossShadowBoundary);
+
+  nsINode* startContainer = IteratorHelpers::GetStartContainer(
+      mRange, IterAllowCrossShadowBoundary());
+  const int32_t startOffset =
+      IteratorHelpers::StartOffset(mRange, IterAllowCrossShadowBoundary());
+  nsINode* endContainer =
+      IteratorHelpers::GetEndContainer(mRange, IterAllowCrossShadowBoundary());
+  const int32_t endOffset =
+      IteratorHelpers::EndOffset(mRange, IterAllowCrossShadowBoundary());
   MOZ_ASSERT(mClosestCommonInclusiveAncestor && startContainer && endContainer);
   // Bug 767169
   MOZ_ASSERT(uint32_t(startOffset) <= startContainer->Length() &&
@@ -1044,14 +1211,23 @@ void ContentSubtreeIterator::Next() {
     return;
   }
 
-  nsINode* nextNode = ContentIteratorBase::GetNextSibling(mCurNode);
+  nsINode* nextNode = ContentIteratorBase::GetNextSibling(
+      mCurNode, IterAllowCrossShadowBoundary());
+
   NS_ASSERTION(nextNode, "No next sibling!?! This could mean deadlock!");
 
   int32_t i = mInclusiveAncestorsOfEndContainer.IndexOf(nextNode);
   while (i != -1) {
     // as long as we are finding ancestors of the endpoint of the range,
     // dive down into their children
-    nextNode = nextNode->GetFirstChild();
+    ShadowRoot* root = IteratorHelpers::GetShadowRoot(
+        Element::FromNode(nextNode), IterAllowCrossShadowBoundary());
+    if (!root) {
+      nextNode = nextNode->GetFirstChild();
+    } else {
+      nextNode = mRange->MayCrossShadowBoundary() ? root->GetFirstChild()
+                                                  : nextNode->GetFirstChild();
+    }
     NS_ASSERTION(nextNode, "Iterator error, expected a child node!");
 
     // should be impossible to get a null pointer.  If we went all the way
@@ -1098,7 +1274,8 @@ nsresult ContentSubtreeIterator::PositionAt(nsINode* aCurNode) {
 
 nsIContent* ContentSubtreeIterator::GetTopAncestorInRange(
     nsINode* aNode) const {
-  if (!aNode || !aNode->GetParentNode()) {
+  if (!aNode ||
+      !IteratorHelpers::GetParentNode(*aNode, IterAllowCrossShadowBoundary())) {
     return nullptr;
   }
 
@@ -1114,15 +1291,23 @@ nsIContent* ContentSubtreeIterator::GetTopAncestorInRange(
     return nullptr;
   }
 
+  nsIContent* lastContentInShadowTree = nullptr;
   while (content) {
-    nsIContent* parent = content->GetParent();
+    nsINode* parent = IteratorHelpers::GetParentNode(
+        *content, IterAllowCrossShadowBoundary());
+
     // content always has a parent.  If its parent is the root, however --
     // i.e., either it's not content, or it is content but its own parent is
     // null -- then we're finished, since we don't go up to the root.
     //
+    // Caveat: If iteration crossing shadow boundary is allowed
+    // and the root is a shadow root, we keep going up to the
+    // shadow host and continue.
+    //
     // We have to special-case this because CompareNodeToRange treats the root
     // node differently -- see bug 765205.
-    if (!parent || !parent->GetParentNode()) {
+    if (!parent || !IteratorHelpers::GetParentNode(
+                       *parent, IterAllowCrossShadowBoundary())) {
       return content;
     }
 
@@ -1130,10 +1315,28 @@ nsIContent* ContentSubtreeIterator::GetTopAncestorInRange(
         RangeUtils::IsNodeContainedInRange(*parent, mRange);
     MOZ_ALWAYS_TRUE(isNodeContainedInRange);
     if (!isNodeContainedInRange.value()) {
+      if (IterAllowCrossShadowBoundary() && content->IsShadowRoot()) {
+        MOZ_ASSERT(parent->GetShadowRoot() == content);
+        // host element is not in range, the last content in tree
+        // should be the ancestor.
+        MOZ_ASSERT(lastContentInShadowTree);
+        return lastContentInShadowTree;
+      }
       return content;
     }
 
-    content = parent;
+    // When we cross the boundary, we keep a reference to the
+    // last content that is in tree, because if we later
+    // find the shadow host element is not in the range, that means
+    // the last content in the tree should be top ancestor in range.
+    //
+    // Using shadow root doesn't make sense here because it doesn't
+    // represent a actual content.
+    if (IterAllowCrossShadowBoundary() && parent->IsShadowRoot()) {
+      lastContentInShadowTree = content;
+    }
+
+    content = parent->AsContent();
   }
 
   MOZ_CRASH("This should only be possible if aNode was null");