Bug 1464428: Optimize QuerySelector in shadow trees. r=xidorn
authorEmilio Cobos Álvarez <emilio@crisal.io>
Fri, 25 May 2018 16:56:41 +0200
changeset 800535 1d53c55e96dfbcd965b8a722539ea049bb45fffe
parent 800534 baf00899e3d139db5b316f6ec33129577cb72b86
child 800536 ed9287ebde83eca109b3c95bcb67a207769798cc
child 800576 f1af1b6d0b11c4e005e9260119d088095d886308
child 800580 78fb9da9d5217c5031968c858b811d609ad9ed76
child 800600 47f87e64a4c2bb7263eabcaebb207882debfd426
child 800602 28ccc519eacb3edbe0743dee09cd1e778fffaa13
child 800608 bc77410aee7efb332a115a624c879c303dc7a42d
child 800609 2919533323b3f78a79d06487c87042d107d25cea
child 800643 aefdccdb67f8b8fad80f80881082aa1d951c626d
child 801037 9a2dcb33e6d08e4a9bbe0f387bbc121286b41c33
child 801070 721c3c3f0ffd75be5c63ea25ca090ca78301b42b
push id111393
push userbmo:emilio@crisal.io
push dateMon, 28 May 2018 13:13:24 +0000
reviewersxidorn
bugs1464428
milestone62.0a1
Bug 1464428: Optimize QuerySelector in shadow trees. r=xidorn Pretty much the same setup we have for document. We have the awkwardness of having to check containing shadow manually for ShadowRoot because it's not available in TNode (and making it available added a bit more complexity that wasn't worth it IMO). MozReview-Commit-ID: CqOh0sLHf6o
layout/style/ServoBindings.cpp
layout/style/ServoBindings.h
layout/style/ServoBindings.toml
servo/components/style/dom.rs
servo/components/style/dom_apis.rs
servo/components/style/gecko/wrapper.rs
--- a/layout/style/ServoBindings.cpp
+++ b/layout/style/ServoBindings.cpp
@@ -2884,22 +2884,31 @@ Gecko_ContentList_AppendAll(
   aList->SetCapacity(aLength);
 
   for (size_t i = 0; i < aLength; ++i) {
     aList->AppendElement(const_cast<Element*>(aElements[i]));
   }
 }
 
 const nsTArray<Element*>*
-Gecko_GetElementsWithId(const nsIDocument* aDocument, nsAtom* aId)
+Gecko_Document_GetElementsWithId(const nsIDocument* aDoc, nsAtom* aId)
 {
-  MOZ_ASSERT(aDocument);
+  MOZ_ASSERT(aDoc);
   MOZ_ASSERT(aId);
 
-  return aDocument->GetAllElementsForId(nsDependentAtomString(aId));
+  return aDoc->GetAllElementsForId(nsDependentAtomString(aId));
+}
+
+const nsTArray<Element*>*
+Gecko_ShadowRoot_GetElementsWithId(const ShadowRoot* aShadowRoot, nsAtom* aId)
+{
+  MOZ_ASSERT(aShadowRoot);
+  MOZ_ASSERT(aId);
+
+  return aShadowRoot->GetAllElementsForId(nsDependentAtomString(aId));
 }
 
 bool
 Gecko_GetBoolPrefValue(const char* aPrefName)
 {
   MOZ_ASSERT(NS_IsMainThread());
   return Preferences::GetBool(aPrefName);
 }
--- a/layout/style/ServoBindings.h
+++ b/layout/style/ServoBindings.h
@@ -703,20 +703,27 @@ void Gecko_ReportUnexpectedCSSError(mozi
                                     uint32_t lineNumber,
                                     uint32_t colNumber);
 
 // DOM APIs.
 void Gecko_ContentList_AppendAll(nsSimpleContentList* aContentList,
                                  const RawGeckoElement** aElements,
                                  size_t aLength);
 
-const nsTArray<mozilla::dom::Element*>* Gecko_GetElementsWithId(
+// FIXME(emilio): These two below should be a single function that takes a
+// `const DocumentOrShadowRoot*`, but that doesn't make MSVC builds happy for a
+// reason I haven't really dug into.
+const nsTArray<mozilla::dom::Element*>* Gecko_Document_GetElementsWithId(
     const nsIDocument* aDocument,
     nsAtom* aId);
 
+const nsTArray<mozilla::dom::Element*>* Gecko_ShadowRoot_GetElementsWithId(
+    const mozilla::dom::ShadowRoot* aDocument,
+    nsAtom* aId);
+
 // Check the value of the given bool preference. The pref name needs to
 // be null-terminated.
 bool Gecko_GetBoolPrefValue(const char* pref_name);
 
 // Returns true if we're currently performing the servo traversal.
 bool Gecko_IsInServoTraversal();
 
 // Returns true if we're currently on the main thread.
--- a/layout/style/ServoBindings.toml
+++ b/layout/style/ServoBindings.toml
@@ -453,16 +453,17 @@ raw-lines = [
 whitelist-functions = ["Servo_.*", "Gecko_.*"]
 structs-types = [
     "mozilla::css::GridTemplateAreasValue",
     "mozilla::css::ErrorReporter",
     "mozilla::css::ImageValue",
     "mozilla::css::URLValue",
     "mozilla::css::URLValueData",
     "mozilla::dom::CallerType",
+    "mozilla::dom::ShadowRoot",
     "mozilla::AnonymousCounterStyle",
     "mozilla::AtomArray",
     "mozilla::FontStretch",
     "mozilla::FontSlantStyle",
     "mozilla::FontWeight",
     "mozilla::MallocSizeOf",
     "mozilla::OriginFlags",
     "mozilla::UniquePtr",
--- a/servo/components/style/dom.rs
+++ b/servo/components/style/dom.rs
@@ -130,24 +130,27 @@ pub trait TDocument: Sized + Copy + Clon
 
     /// Returns whether this document is an HTML document.
     fn is_html_document(&self) -> bool;
 
     /// Returns the quirks mode of this document.
     fn quirks_mode(&self) -> QuirksMode;
 
     /// Get a list of elements with a given ID in this document, sorted by
-    /// document position.
+    /// tree position.
     ///
     /// Can return an error to signal that this list is not available, or also
     /// return an empty slice.
-    fn elements_with_id(
+    fn elements_with_id<'a>(
         &self,
         _id: &Atom,
-    ) -> Result<&[<Self::ConcreteNode as TNode>::ConcreteElement], ()> {
+    ) -> Result<&'a [<Self::ConcreteNode as TNode>::ConcreteElement], ()>
+    where
+        Self: 'a,
+    {
         Err(())
     }
 }
 
 /// The `TNode` trait. This is the main generic trait over which the style
 /// system can be implemented.
 pub trait TNode: Sized + Copy + Clone + Debug + NodeInfo + PartialEq {
     /// The concrete `TElement` type.
@@ -337,16 +340,31 @@ pub trait TShadowRoot: Sized + Copy + Cl
 
     /// Get the shadow host that hosts this ShadowRoot.
     fn host(&self) -> <Self::ConcreteNode as TNode>::ConcreteElement;
 
     /// Get the style data for this ShadowRoot.
     fn style_data<'a>(&self) -> &'a CascadeData
     where
         Self: 'a;
+
+    /// Get a list of elements with a given ID in this shadow root, sorted by
+    /// tree position.
+    ///
+    /// Can return an error to signal that this list is not available, or also
+    /// return an empty slice.
+    fn elements_with_id<'a>(
+        &self,
+        _id: &Atom,
+    ) -> Result<&'a [<Self::ConcreteNode as TNode>::ConcreteElement], ()>
+    where
+        Self: 'a,
+    {
+        Err(())
+    }
 }
 
 /// The element trait, the main abstraction the style crate acts over.
 pub trait TElement:
     Eq + PartialEq + Debug + Hash + Sized + Copy + Clone + SelectorsElement<Impl = SelectorImpl>
 {
     /// The concrete node type.
     type ConcreteNode: TNode<ConcreteElement = Self>;
--- a/servo/components/style/dom_apis.rs
+++ b/servo/components/style/dom_apis.rs
@@ -216,93 +216,114 @@ where
 
         Q::append_element(results, element);
         if Q::should_stop_after_first_match() {
             return;
         }
     }
 }
 
-/// Returns whether a given element is descendant of a given `root` node.
+/// Returns whether a given element connected to `root` is descendant of `root`.
 ///
 /// NOTE(emilio): if root == element, this returns false.
-fn element_is_descendant_of<E>(element: E, root: E::ConcreteNode) -> bool
+fn connected_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() {
+    // Optimize for when the root is a document or a shadow root and the element
+    // is connected to that root.
+    if root.as_document().is_some() {
+        debug_assert!(element.as_node().is_in_document(), "Not connected?");
+        debug_assert_eq!(
+            root,
+            root.owner_doc().as_node(),
+            "Where did this element come from?",
+        );
+        return true;
+    }
+
+    if root.as_shadow_root().is_some() {
+        debug_assert_eq!(
+            element.containing_shadow().unwrap().as_node(),
+            root,
+            "Not connected?"
+        );
         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
 }
 
 /// Fast path for iterating over every element with a given id in the document
-/// that `root` is connected to.
-fn fast_connected_elements_with_id<'a, D>(
-    doc: &'a D,
-    root: D::ConcreteNode,
+/// or shadow root that `root` is connected to.
+fn fast_connected_elements_with_id<'a, N>(
+    root: N,
     id: &Atom,
     quirks_mode: QuirksMode,
-) -> Result<&'a [<D::ConcreteNode as TNode>::ConcreteElement], ()>
+) -> Result<&'a [N::ConcreteElement], ()>
 where
-    D: TDocument,
+    N: TNode + 'a,
 {
-    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 {
         return Err(());
     }
 
-    if !root.is_in_document() {
-        return Err(());
+    if root.is_in_document() {
+        return root.owner_doc().elements_with_id(id);
     }
 
-    doc.elements_with_id(id)
+    if let Some(shadow) = root.as_shadow_root() {
+        return shadow.elements_with_id(id);
+    }
+
+    if let Some(shadow) = root.as_element().and_then(|e| e.containing_shadow()) {
+        return shadow.elements_with_id(id);
+    }
+
+    Err(())
 }
 
 /// 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,
 {
-    let doc = root.owner_doc();
-    let elements = match fast_connected_elements_with_id(&doc, root, id, quirks_mode) {
+    let elements = match fast_connected_elements_with_id(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 the element is not an actual descendant of the root, even though
         // it's connected, we don't really care about it.
-        if !element_is_descendant_of(*element, root) {
+        if !connected_element_is_descendant_of(*element, root) {
             continue;
         }
 
         if !filter(*element) {
             continue;
         }
 
         Q::append_element(results, *element);
@@ -400,19 +421,18 @@ where
                         // root that match the selector list with that id.
                         collect_elements_with_id::<E, Q, _>(root, id, results, quirks_mode, |e| {
                             matching::matches_selector_list(selector_list, &e, matching_context)
                         });
 
                         return Ok(());
                     }
 
-                    let doc = root.owner_doc();
-                    let elements = fast_connected_elements_with_id(&doc, root, id, quirks_mode)?;
-
+                    let elements =
+                        fast_connected_elements_with_id(root, id, quirks_mode)?;
                     if elements.is_empty() {
                         return Ok(());
                     }
 
                     // Results need to be in document order. Let's not bother
                     // reordering or deduplicating nodes, which we would need to
                     // do if one element with the given id were a descendant of
                     // another element with that given id.
@@ -427,17 +447,17 @@ where
                         // that match our selector that are _not_.
                         //
                         // So we can't just walk over the element's descendants
                         // and match the selector against all of them, nor can
                         // we skip looking at this element's descendants.
                         //
                         // Give up on trying to optimize based on this id and
                         // keep walking our selector.
-                        if !element_is_descendant_of(*element, root) {
+                        if !connected_element_is_descendant_of(*element, root) {
                             continue 'component_loop;
                         }
 
                         query_selector_slow::<E, Q>(
                             element.as_node(),
                             selector_list,
                             results,
                             matching_context,
--- a/servo/components/style/gecko/wrapper.rs
+++ b/servo/components/style/gecko/wrapper.rs
@@ -82,16 +82,39 @@ use shared_lock::Locked;
 use std::cell::RefCell;
 use std::fmt;
 use std::hash::{Hash, Hasher};
 use std::mem;
 use std::ptr;
 use string_cache::{Atom, Namespace, WeakAtom, WeakNamespace};
 use stylist::CascadeData;
 
+
+#[inline]
+fn elements_with_id<'a, 'le>(
+    array: *const structs::nsTArray<*mut RawGeckoElement>,
+) -> &'a [GeckoElement<'le>] {
+    unsafe {
+        if array.is_null() {
+            return &[];
+        }
+
+        let elements: &[*mut RawGeckoElement] = &**array;
+
+        // NOTE(emilio): We rely on the in-memory representation of
+        // GeckoElement<'ld> and *mut RawGeckoElement being the same.
+        #[allow(dead_code)]
+        unsafe fn static_assert() {
+            mem::transmute::<*mut RawGeckoElement, GeckoElement<'static>>(0xbadc0de as *mut _);
+        }
+
+        mem::transmute(elements)
+    }
+}
+
 /// A simple wrapper over `nsIDocument`.
 #[derive(Clone, Copy)]
 pub struct GeckoDocument<'ld>(pub &'ld structs::nsIDocument);
 
 impl<'ld> TDocument for GeckoDocument<'ld> {
     type ConcreteNode = GeckoNode<'ld>;
 
     #[inline]
@@ -104,34 +127,24 @@ impl<'ld> TDocument for GeckoDocument<'l
         self.0.mType == structs::root::nsIDocument_Type::eHTML
     }
 
     #[inline]
     fn quirks_mode(&self) -> QuirksMode {
         self.0.mCompatMode.into()
     }
 
-    fn elements_with_id(&self, id: &Atom) -> Result<&[GeckoElement<'ld>], ()> {
-        unsafe {
-            let array = bindings::Gecko_GetElementsWithId(self.0, id.as_ptr());
-            if array.is_null() {
-                return Ok(&[]);
-            }
-
-            let elements: &[*mut RawGeckoElement] = &**array;
-
-            // NOTE(emilio): We rely on the in-memory representation of
-            // GeckoElement<'ld> and *mut RawGeckoElement being the same.
-            #[allow(dead_code)]
-            unsafe fn static_assert() {
-                mem::transmute::<*mut RawGeckoElement, GeckoElement<'static>>(0xbadc0de as *mut _);
-            }
-
-            Ok(mem::transmute(elements))
-        }
+    #[inline]
+    fn elements_with_id<'a>(&self, id: &Atom) -> Result<&'a [GeckoElement<'ld>], ()>
+    where
+        Self: 'a,
+    {
+        Ok(elements_with_id(unsafe {
+            bindings::Gecko_Document_GetElementsWithId(self.0, id.as_ptr())
+        }))
     }
 }
 
 /// A simple wrapper over `ShadowRoot`.
 #[derive(Clone, Copy)]
 pub struct GeckoShadowRoot<'lr>(pub &'lr structs::ShadowRoot);
 
 impl<'lr> PartialEq for GeckoShadowRoot<'lr> {
@@ -171,16 +184,26 @@ impl<'lr> TShadowRoot for GeckoShadowRoo
         debug_assert!(!author_styles.stylesheets.dirty());
         debug_assert!(
             author_styles.quirks_mode == self.as_node().owner_doc().quirks_mode() ||
                 author_styles.stylesheets.is_empty()
         );
 
         &author_styles.data
     }
+
+    #[inline]
+    fn elements_with_id<'a>(&self, id: &Atom) -> Result<&'a [GeckoElement<'lr>], ()>
+    where
+        Self: 'a,
+    {
+        Ok(elements_with_id(unsafe {
+            bindings::Gecko_ShadowRoot_GetElementsWithId(self.0, id.as_ptr())
+        }))
+    }
 }
 
 /// A simple wrapper over a non-null Gecko node (`nsINode`) pointer.
 ///
 /// Important: We don't currently refcount the DOM, because the wrapper lifetime
 /// magic guarantees that our LayoutFoo references won't outlive the root, and
 /// we don't mutate any of the references on the Gecko side during restyle.
 ///