Implement concept of shadow including tree order

15 files changed, 69 insertions, 43 deletions

diff --git a/components/script/devtools.rs b/components/script/devtools.rs
index 7a24d959980..9494dbe41ac 100644
--- a/components/script/devtools.rs
+++ b/components/script/devtools.rs
@@ -103,7 +103,7 @@ fn find_node_by_unique_id(
     documents.find_document(pipeline).and_then(|document| {
         document
             .upcast::<Node>()
-            .traverse_preorder()
+            .traverse_preorder(/* shadow including */ false)
             .find(|candidate| candidate.unique_id() == node_id)
     })
 }
diff --git a/components/script/dom/customelementregistry.rs b/components/script/dom/customelementregistry.rs
index abefc4eca58..411d5c7fb7b 100644
--- a/components/script/dom/customelementregistry.rs
+++ b/components/script/dom/customelementregistry.rs
@@ -364,7 +364,7 @@ impl CustomElementRegistryMethods for CustomElementRegistry {
         // Steps 14-15
         for candidate in document
             .upcast::<Node>()
-            .traverse_preorder()
+            .traverse_preorder(/* shadow including */ true)
             .filter_map(DomRoot::downcast::<Element>)
         {
             let is = candidate.get_is();
diff --git a/components/script/dom/document.rs b/components/script/dom/document.rs
index 14dc0643925..3ed7082e4b5 100644
--- a/components/script/dom/document.rs
+++ b/components/script/dom/document.rs
@@ -631,7 +631,7 @@ impl Document {
     pub fn refresh_base_element(&self) {
         let base = self
             .upcast::<Node>()
-            .traverse_preorder()
+            .traverse_preorder(/* shadow including */ false)
             .filter_map(DomRoot::downcast::<HTMLBaseElement>)
             .find(|element| {
                 element
@@ -869,7 +869,7 @@ impl Document {
         };
         let doc_node = self.upcast::<Node>();
         doc_node
-            .traverse_preorder()
+            .traverse_preorder(/* shadow including */ false)
             .filter_map(DomRoot::downcast)
             .find(|node| check_anchor(&node))
             .map(DomRoot::upcast)
@@ -978,7 +978,7 @@ impl Document {
 
     pub fn dirty_all_nodes(&self) {
         let root = self.upcast::<Node>();
-        for node in root.traverse_preorder() {
+        for node in root.traverse_preorder(/* shadow including */ true) {
             node.dirty(NodeDamage::OtherNodeDamage)
         }
     }
@@ -2273,7 +2273,7 @@ impl Document {
     /// Iterate over all iframes in the document.
     pub fn iter_iframes(&self) -> impl Iterator<Item = DomRoot<HTMLIFrameElement>> {
         self.upcast::<Node>()
-            .traverse_preorder()
+            .traverse_preorder(/* shadow including */ true)
             .filter_map(DomRoot::downcast::<HTMLIFrameElement>)
     }
 
@@ -2837,7 +2837,7 @@ impl Document {
         let maybe_node = doc.deref().map(Castable::upcast::<Node>);
         let iter = maybe_node
             .iter()
-            .flat_map(|node| node.traverse_preorder())
+            .flat_map(|node| node.traverse_preorder(/* shadow including */ false))
             .filter(|node| callback(&node));
         NodeList::new_simple_list(&self.window, iter)
     }
@@ -3793,7 +3793,7 @@ impl DocumentMethods for Document {
             } else {
                 // Step 2.
                 root.upcast::<Node>()
-                    .traverse_preorder()
+                    .traverse_preorder(/* shadow including */ false)
                     .find(|node| node.is::<HTMLTitleElement>())
             }
         });
@@ -3840,7 +3840,7 @@ impl DocumentMethods for Document {
         } else if root.namespace() == &ns!(html) {
             let elem = root
                 .upcast::<Node>()
-                .traverse_preorder()
+                .traverse_preorder(/* shadow including */ false)
                 .find(|node| node.is::<HTMLTitleElement>());
             match elem {
                 Some(elem) => elem,
@@ -4207,7 +4207,7 @@ impl DocumentMethods for Document {
         {
             // Step 1.
             let mut elements = root
-                .traverse_preorder()
+                .traverse_preorder(/* shadow including */ false)
                 .filter(|node| filter_by_name(&name, &node))
                 .peekable();
             if let Some(first) = elements.next() {
@@ -4325,7 +4325,10 @@ impl DocumentMethods for Document {
         }
 
         // Step 8
-        for node in self.upcast::<Node>().traverse_preorder() {
+        for node in self
+            .upcast::<Node>()
+            .traverse_preorder(/* shadow including */ true)
+        {
             node.upcast::<EventTarget>().remove_all_listeners();
         }
 
diff --git a/components/script/dom/documentfragment.rs b/components/script/dom/documentfragment.rs
index 00718d0534d..ac9df62f59f 100644
--- a/components/script/dom/documentfragment.rs
+++ b/components/script/dom/documentfragment.rs
@@ -59,7 +59,7 @@ impl DocumentFragmentMethods for DocumentFragment {
     fn GetElementById(&self, id: DOMString) -> Option<DomRoot<Element>> {
         let node = self.upcast::<Node>();
         let id = Atom::from(id);
-        node.traverse_preorder()
+        node.traverse_preorder(/* shadow including */ false)
             .filter_map(DomRoot::downcast::<Element>)
             .find(
                 |descendant| match descendant.get_attribute(&ns!(), &local_name!("id")) {
diff --git a/components/script/dom/element.rs b/components/script/dom/element.rs
index bde1d46582f..5b5b93f78c1 100644
--- a/components/script/dom/element.rs
+++ b/components/script/dom/element.rs
@@ -443,7 +443,7 @@ impl Element {
         })
     }
 
-    fn is_shadow_host(&self) -> bool {
+    pub fn is_shadow_host(&self) -> bool {
         self.shadow_root.get().is_some()
     }
 
diff --git a/components/script/dom/htmlelement.rs b/components/script/dom/htmlelement.rs
index 52184326a62..a9e75c531df 100644
--- a/components/script/dom/htmlelement.rs
+++ b/components/script/dom/htmlelement.rs
@@ -707,7 +707,7 @@ impl HTMLElement {
         let root_element = element.root_element();
         let root_node = root_element.upcast::<Node>();
         let children = root_node
-            .traverse_preorder()
+            .traverse_preorder(/* shadow including */ false)
             .filter_map(DomRoot::downcast::<Element>)
             .filter(|elem| elem.is::<HTMLLabelElement>())
             .filter(|elem| elem.get_string_attribute(&local_name!("for")) == id)
diff --git a/components/script/dom/htmlfieldsetelement.rs b/components/script/dom/htmlfieldsetelement.rs
index d8e92180e56..d90555db9f1 100644
--- a/components/script/dom/htmlfieldsetelement.rs
+++ b/components/script/dom/htmlfieldsetelement.rs
@@ -128,7 +128,7 @@ impl VirtualMethods for HTMLFieldSetElement {
                 });
                 let fields = children.flat_map(|child| {
                     child
-                        .traverse_preorder()
+                        .traverse_preorder(/* shadow including */ false)
                         .filter(|descendant| match descendant.type_id() {
                             NodeTypeId::Element(ElementTypeId::HTMLElement(
                                 HTMLElementTypeId::HTMLButtonElement,
diff --git a/components/script/dom/htmlformelement.rs b/components/script/dom/htmlformelement.rs
index cd4bb442296..385389eb9d7 100755
--- a/components/script/dom/htmlformelement.rs
+++ b/components/script/dom/htmlformelement.rs
@@ -582,7 +582,7 @@ impl HTMLFormElement {
         //               form, refactor this when html5ever's form owner PR lands
         // Step 1-3
         let invalid_controls = node
-            .traverse_preorder()
+            .traverse_preorder(/* shadow including */ false)
             .filter_map(|field| {
                 if let Some(el) = field.downcast::<Element>() {
                     if el.disabled_state() {
diff --git a/components/script/dom/htmlheadelement.rs b/components/script/dom/htmlheadelement.rs
index ddb06f70932..3c356e279ed 100644
--- a/components/script/dom/htmlheadelement.rs
+++ b/components/script/dom/htmlheadelement.rs
@@ -55,7 +55,7 @@ impl HTMLHeadElement {
 
         let node = self.upcast::<Node>();
         let candidates = node
-            .traverse_preorder()
+            .traverse_preorder(/* shadow including */ false)
             .filter_map(DomRoot::downcast::<Element>)
             .filter(|elem| elem.is::<HTMLMetaElement>())
             .filter(|elem| elem.get_string_attribute(&local_name!("name")) == "referrer")
diff --git a/components/script/dom/htmlimageelement.rs b/components/script/dom/htmlimageelement.rs
index 7ad2aeac1e6..fd545b47016 100644
--- a/components/script/dom/htmlimageelement.rs
+++ b/components/script/dom/htmlimageelement.rs
@@ -1259,7 +1259,7 @@ impl HTMLImageElement {
 
         let useMapElements = document_from_node(self)
             .upcast::<Node>()
-            .traverse_preorder()
+            .traverse_preorder(/* shadow including */ false)
             .filter_map(DomRoot::downcast::<HTMLMapElement>)
             .find(|n| {
                 n.upcast::<Element>()
diff --git a/components/script/dom/htmllabelelement.rs b/components/script/dom/htmllabelelement.rs
index 3c9106a589a..6ed17609a03 100644
--- a/components/script/dom/htmllabelelement.rs
+++ b/components/script/dom/htmllabelelement.rs
@@ -162,7 +162,7 @@ impl VirtualMethods for HTMLLabelElement {
 impl HTMLLabelElement {
     pub fn first_labelable_descendant(&self) -> Option<DomRoot<HTMLElement>> {
         self.upcast::<Node>()
-            .traverse_preorder()
+            .traverse_preorder(/* shadow including */ false)
             .filter_map(DomRoot::downcast::<HTMLElement>)
             .filter(|elem| elem.is_labelable_element())
             .next()
diff --git a/components/script/dom/htmlmapelement.rs b/components/script/dom/htmlmapelement.rs
index 34b73e7e0b9..33a5e96aea7 100644
--- a/components/script/dom/htmlmapelement.rs
+++ b/components/script/dom/htmlmapelement.rs
@@ -43,7 +43,7 @@ impl HTMLMapElement {
 
     pub fn get_area_elements(&self) -> Vec<DomRoot<HTMLAreaElement>> {
         self.upcast::<Node>()
-            .traverse_preorder()
+            .traverse_preorder(/* shadow including */ false)
             .filter_map(DomRoot::downcast::<HTMLAreaElement>)
             .collect()
     }
diff --git a/components/script/dom/node.rs b/components/script/dom/node.rs
index cecad5d7b76..d8c1a2f4d5d 100644
--- a/components/script/dom/node.rs
+++ b/components/script/dom/node.rs
@@ -291,7 +291,7 @@ impl Node {
         let parent_in_doc = self.is_in_doc();
         let parent_in_shadow_tree = self.is_in_shadow_tree();
         let parent_is_connected = self.is_connected();
-        for node in new_child.traverse_preorder() {
+        for node in new_child.traverse_preorder(/* shadow including */ false) {
             if parent_in_shadow_tree {
                 if let Some(shadow_root) = self.downcast::<ShadowRoot>() {
                     node.set_owner_shadow_root(&*shadow_root);
@@ -355,7 +355,7 @@ impl Node {
         child.composed_parent_node.set(None);
         self.children_count.set(self.children_count.get() - 1);
 
-        for node in child.traverse_preorder() {
+        for node in child.traverse_preorder(/* shadow including */ true) {
             // Out-of-document elements never have the descendants flag set.
             node.set_flag(
                 NodeFlags::IS_IN_DOC |
@@ -365,7 +365,7 @@ impl Node {
                 false,
             );
         }
-        for node in child.traverse_preorder() {
+        for node in child.traverse_preorder(/* shadow including */ true) {
             // This needs to be in its own loop, because unbind_from_tree may
             // rely on the state of IS_IN_DOC of the context node's descendants,
             // e.g. when removing a <form>.
@@ -628,8 +628,8 @@ impl Node {
     }
 
     /// Iterates over this node and all its descendants, in preorder.
-    pub fn traverse_preorder(&self) -> TreeIterator {
-        TreeIterator::new(self)
+    pub fn traverse_preorder(&self, shadow_including: bool) -> TreeIterator {
+        TreeIterator::new(self, shadow_including)
     }
 
     pub fn inclusively_following_siblings(&self) -> impl Iterator<Item = DomRoot<Node>> {
@@ -876,7 +876,7 @@ impl Node {
                     self.owner_doc().quirks_mode(),
                 );
                 Ok(self
-                    .traverse_preorder()
+                    .traverse_preorder(/* shadow including */ false)
                     .filter_map(DomRoot::downcast)
                     .find(|element| matches_selector_list(&selectors, element, &mut ctx)))
             },
@@ -894,7 +894,7 @@ impl Node {
             Err(_) => Err(Error::Syntax),
             // Step 3.
             Ok(selectors) => {
-                let mut descendants = self.traverse_preorder();
+                let mut descendants = self.traverse_preorder(/* shadow including */ false);
                 // Skip the root of the tree.
                 assert!(&*descendants.next().unwrap() == self);
                 Ok(QuerySelectorIterator::new(descendants, selectors))
@@ -917,16 +917,16 @@ impl Node {
         }
     }
 
-    pub fn inclusive_ancestors(&self) -> impl Iterator<Item = DomRoot<Node>> {
-        SimpleNodeIterator {
+    pub fn inclusive_ancestors(&self) -> Box<Iterator<Item = DomRoot<Node>>> {
+        Box::new(SimpleNodeIterator {
             current: Some(DomRoot::from_ref(self)),
             next_node: |n| n.GetParentNode(),
-        }
+        })
     }
 
     /// https://dom.spec.whatwg.org/#concept-shadow-including-inclusive-ancestor
-    pub fn shadow_including_inclusive_ancestors(&self) -> impl Iterator<Item = DomRoot<Node>> {
-        SimpleNodeIterator {
+    pub fn shadow_including_inclusive_ancestors(&self) -> Box<Iterator<Item = DomRoot<Node>>> {
+        Box::new(SimpleNodeIterator {
             current: Some(DomRoot::from_ref(self)),
             next_node: |n| {
                 if let Some(shadow_root) = n.downcast::<ShadowRoot>() {
@@ -935,7 +935,7 @@ impl Node {
                     n.GetParentNode()
                 }
             },
-        }
+        })
     }
 
     pub fn owner_doc(&self) -> DomRoot<Document> {
@@ -1505,13 +1505,15 @@ where
 pub struct TreeIterator {
     current: Option<DomRoot<Node>>,
     depth: usize,
+    shadow_including: bool,
 }
 
 impl TreeIterator {
-    fn new(root: &Node) -> TreeIterator {
+    fn new(root: &Node, shadow_including: bool) -> TreeIterator {
         TreeIterator {
             current: Some(DomRoot::from_ref(root)),
             depth: 0,
+            shadow_including,
         }
     }
 
@@ -1522,7 +1524,13 @@ impl TreeIterator {
     }
 
     fn next_skipping_children_impl(&mut self, current: DomRoot<Node>) -> Option<DomRoot<Node>> {
-        for ancestor in current.inclusive_ancestors() {
+        let iter = if self.shadow_including {
+            current.shadow_including_inclusive_ancestors()
+        } else {
+            current.inclusive_ancestors()
+        };
+
+        for ancestor in iter {
             if self.depth == 0 {
                 break;
             }
@@ -1542,8 +1550,18 @@ impl Iterator for TreeIterator {
     type Item = DomRoot<Node>;
 
     // https://dom.spec.whatwg.org/#concept-tree-order
+    // https://dom.spec.whatwg.org/#concept-shadow-including-tree-order
     fn next(&mut self) -> Option<DomRoot<Node>> {
         let current = self.current.take()?;
+
+        if !self.shadow_including {
+            if let Some(element) = current.downcast::<Element>() {
+                if element.is_shadow_host() {
+                    return self.next_skipping_children_impl(current);
+                }
+            }
+        }
+
         if let Some(first_child) = current.GetFirstChild() {
             self.current = Some(first_child);
             self.depth += 1;
@@ -1626,11 +1644,11 @@ impl Node {
         // Step 3.
         if &*old_doc != document {
             // Step 3.1.
-            for descendant in node.traverse_preorder() {
+            for descendant in node.traverse_preorder(/* shadow including */ true) {
                 descendant.set_owner_doc(document);
             }
             for descendant in node
-                .traverse_preorder()
+                .traverse_preorder(/* shadow including */ true)
                 .filter_map(|d| d.as_custom_element())
             {
                 // Step 3.2.
@@ -1640,7 +1658,7 @@ impl Node {
                     None,
                 );
             }
-            for descendant in node.traverse_preorder() {
+            for descendant in node.traverse_preorder(/* shadow including */ true) {
                 // Step 3.3.
                 vtable_for(&descendant).adopting_steps(&old_doc);
             }
@@ -1861,7 +1879,7 @@ impl Node {
             parent.add_child(*kid, child);
             // Step 7.7.
             for descendant in kid
-                .traverse_preorder()
+                .traverse_preorder(/* shadow including */ true)
                 .filter_map(DomRoot::downcast::<Element>)
             {
                 // Step 7.7.2.
@@ -2306,7 +2324,9 @@ impl NodeMethods for Node {
     fn GetTextContent(&self) -> Option<DOMString> {
         match self.type_id() {
             NodeTypeId::DocumentFragment(_) | NodeTypeId::Element(..) => {
-                let content = Node::collect_text_contents(self.traverse_preorder());
+                let content = Node::collect_text_contents(
+                    self.traverse_preorder(/* shadow including */ false),
+                );
                 Some(content)
             },
             NodeTypeId::CharacterData(..) => {
@@ -3143,7 +3163,7 @@ where
 
         let elem_node = elem.upcast::<Node>();
         let mut head: usize = 0;
-        for node in tree_root.traverse_preorder() {
+        for node in tree_root.traverse_preorder(/* shadow including */ false) {
             let head_node = DomRoot::upcast::<Node>(DomRoot::from_ref(&*self[head]));
             if head_node == node {
                 head += 1;
diff --git a/components/script/dom/range.rs b/components/script/dom/range.rs
index afa759de52f..2f0b5422b1e 100644
--- a/components/script/dom/range.rs
+++ b/components/script/dom/range.rs
@@ -976,7 +976,10 @@ impl RangeMethods for Range {
         let fragment_node = element.parse_fragment(fragment)?;
 
         // Step 4.
-        for node in fragment_node.upcast::<Node>().traverse_preorder() {
+        for node in fragment_node
+            .upcast::<Node>()
+            .traverse_preorder(/* shadow incluing */ false)
+        {
             if let Some(script) = node.downcast::<HTMLScriptElement>() {
                 script.set_already_started(false);
                 script.set_parser_inserted(false);
diff --git a/components/script/webdriver_handlers.rs b/components/script/webdriver_handlers.rs
index a3c143a4faa..8bcb63a58f4 100644
--- a/components/script/webdriver_handlers.rs
+++ b/components/script/webdriver_handlers.rs
@@ -50,7 +50,7 @@ fn find_node_by_unique_id(
     documents.find_document(pipeline).and_then(|document| {
         document
             .upcast::<Node>()
-            .traverse_preorder()
+            .traverse_preorder(/* shadow including */ true)
             .find(|candidate| candidate.unique_id() == node_id)
     })
 }