Bug 1464428: Optimize QuerySelector in shadow trees. r=xidorn
authorEmilio Cobos Álvarez <emilio@crisal.io>
Fri, 25 May 2018 16:56:41 +0200
changeset 420147 1d53c55e96dfbcd965b8a722539ea049bb45fffe
parent 420146 baf00899e3d139db5b316f6ec33129577cb72b86
child 420148 f1af1b6d0b11c4e005e9260119d088095d886308
push id34065
push useraciure@mozilla.com
push dateMon, 28 May 2018 21:54:18 +0000
treeherdermozilla-central@35aa0dde259f [default view] [failures only]
perfherder[talos] [build metrics] [platform microbench] (compared to previous push)
reviewersxidorn
bugs1464428
milestone62.0a1
first release with
nightly linux32
nightly linux64
nightly mac
nightly win32
nightly win64
last release without
nightly linux32
nightly linux64
nightly mac
nightly win32
nightly win64
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.
 ///