style: Add a query-selector fast path for #id foo. draft
authorEmilio Cobos Álvarez <emilio@crisal.io>
Fri, 27 Oct 2017 14:00:53 +0200
changeset 687756 c9cb85e4e9186044ca58494423dd7a157ef030de
parent 687720 ea8c1db64f7e1de71238bea4f044ae70e487065c
child 687757 02719baa0563f01ab4539c7d8f7265043dd6038e
push id86596
push userbmo:emilio@crisal.io
push dateFri, 27 Oct 2017 18:18:19 +0000
milestone58.0a1
style: Add a query-selector fast path for #id foo. MozReview-Commit-ID: DkrLcfQLPga
servo/components/style/dom_apis.rs
--- a/servo/components/style/dom_apis.rs
+++ b/servo/components/style/dom_apis.rs
@@ -224,106 +224,99 @@ where
 
 /// Returns whether a given element is descendant of a given `root` node.
 ///
 /// NOTE(emilio): if root == element, this returns false.
 fn element_is_descendant_of<E>(element: E, root: E::ConcreteNode) -> bool
 where
     E: TElement,
 {
+    if element.as_node().is_in_document() && root == root.owner_doc().as_node() {
+        return true;
+    }
+
     let mut current = element.as_node().parent_node();
     while let Some(n) = current.take() {
         if n == root {
             return true;
         }
 
         current = n.parent_node();
     }
     false
 }
 
-/// Execute `callback` on each element with a given `id` under `root`.
-///
-/// If `callback` returns false, iteration will stop immediately.
-fn each_element_with_id_under<E, F>(
-    root: E::ConcreteNode,
+/// Fast path for iterating over every element with a given id in the document.
+fn fast_elements_with_id<'a, D>(
+    doc: &'a D,
+    root: D::ConcreteNode,
     id: &Atom,
     quirks_mode: QuirksMode,
-    mut callback: F,
-)
+) -> Result<&'a [<D::ConcreteNode as TNode>::ConcreteElement], ()>
 where
-    E: TElement,
-    F: FnMut(E) -> bool,
+    D: TDocument,
 {
+    debug_assert_eq!(root.owner_doc().as_node(), doc.as_node());
+
     let case_sensitivity = quirks_mode.classes_and_ids_case_sensitivity();
-    if case_sensitivity == CaseSensitivity::CaseSensitive &&
-       root.is_in_document()
-    {
-        let doc = root.owner_doc();
-        if let Ok(elements) = doc.elements_with_id(id) {
-            if root == doc.as_node() {
-                for element in elements {
-                    if !callback(*element) {
-                        return;
-                    }
-                }
-            } else {
-                for element in elements {
-                    if !element_is_descendant_of(*element, root) {
-                        continue;
-                    }
-
-                    if !callback(*element) {
-                        return;
-                    }
-                }
-            }
-        }
-        return;
+    if case_sensitivity != CaseSensitivity::CaseSensitive {
+        return Err(());
     }
 
-    for node in root.dom_descendants() {
-        let element = match node.as_element() {
-            Some(e) => e,
-            None => continue,
-        };
+    if !root.is_in_document() {
+        return Err(());
+    }
 
-        if !element.has_id(id, case_sensitivity) {
-            continue;
-        }
-
-        if !callback(element) {
-            return;
-        }
-    }
+    doc.elements_with_id(id)
 }
 
+/// Collects elements with a given id under `root`, that pass `filter`.
 fn collect_elements_with_id<E, Q, F>(
     root: E::ConcreteNode,
     id: &Atom,
     results: &mut Q::Output,
     quirks_mode: QuirksMode,
     mut filter: F,
 )
 where
     E: TElement,
     Q: SelectorQuery<E>,
     F: FnMut(E) -> bool,
 {
-    each_element_with_id_under::<E, _>(root, id, quirks_mode, |element| {
-        if !filter(element) {
-            return true;
+    let doc = root.owner_doc();
+    let elements = match fast_elements_with_id(&doc, root, id, quirks_mode) {
+        Ok(elements) => elements,
+        Err(()) => {
+            let case_sensitivity =
+                quirks_mode.classes_and_ids_case_sensitivity();
+
+            collect_all_elements::<E, Q, _>(root, results, |e| {
+                e.has_id(id, case_sensitivity) && filter(e)
+            });
+
+            return;
+        }
+    };
+
+    for element in elements {
+        if !element_is_descendant_of(*element, root) {
+            continue;
         }
 
-        Q::append_element(results, element);
-        return !Q::should_stop_after_first_match()
-    })
+        if !filter(*element) {
+            continue;
+        }
+
+        Q::append_element(results, *element);
+        if Q::should_stop_after_first_match() {
+            break;
+        }
+    }
 }
 
-
 /// Fast paths for querySelector with a single simple selector.
 fn query_selector_single_query<E, Q>(
     root: E::ConcreteNode,
     component: &Component<E::Impl>,
     results: &mut Q::Output,
     quirks_mode: QuirksMode,
 ) -> Result<(), ()>
 where
@@ -336,17 +329,17 @@ where
         }
         Component::ID(ref id) => {
             collect_elements_with_id::<E, Q, _>(
                 root,
                 id,
                 results,
                 quirks_mode,
                 |_| true,
-            )
+            );
         }
         Component::Class(ref class) => {
             let case_sensitivity = quirks_mode.classes_and_ids_case_sensitivity();
             collect_all_elements::<E, Q, _>(root, results, |element| {
                 element.has_class(class, case_sensitivity)
             })
         }
         Component::LocalName(LocalName { ref name, ref lower_name }) => {
@@ -424,18 +417,41 @@ where
                                     matching_context,
                                 )
                             }
                         );
 
                         return Ok(());
                     }
 
-                    // TODO(emilio): Find descendants of `root` that are
-                    // descendants of an element with a given `id`.
+                    let doc = root.owner_doc();
+                    let elements =
+                        fast_elements_with_id(&doc, root, id, quirks_mode)?;
+
+                    if elements.is_empty() {
+                        return Ok(());
+                    }
+
+                    if elements.len() > 1 {
+                        continue;
+                    }
+
+                    let element = elements[0];
+                    if !element_is_descendant_of(element, root) {
+                        continue;
+                    }
+
+                    query_selector_slow::<E, Q>(
+                        element.as_node(),
+                        selector_list,
+                        results,
+                        matching_context,
+                    );
+
+                    return Ok(());
                 }
                 _ => {},
             }
         }
 
         loop {
             let next_combinator = match iter.next_sequence() {
                 None => return Err(()),