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
--- a/layout/style/ServoBindings.cpp
+++ b/layout/style/ServoBindings.cpp
@@ -2887,22 +2887,22 @@ 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_GetElementsWithId(const DocumentOrShadowRoot* aDocOrShadowRoot, nsAtom* aId)
{
- MOZ_ASSERT(aDocument);
+ MOZ_ASSERT(aDocOrShadowRoot);
MOZ_ASSERT(aId);
- return aDocument->GetAllElementsForId(nsDependentAtomString(aId));
+ return aDocOrShadowRoot->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
@@ -704,17 +704,17 @@ void Gecko_ReportUnexpectedCSSError(mozi
uint32_t colNumber);
// DOM APIs.
void Gecko_ContentList_AppendAll(nsSimpleContentList* aContentList,
const RawGeckoElement** aElements,
size_t aLength);
const nsTArray<mozilla::dom::Element*>* Gecko_GetElementsWithId(
- const nsIDocument* aDocument,
+ const mozilla::dom::DocumentOrShadowRoot* aDocOrShadowRoot,
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();
--- 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::DocumentOrShadowRoot",
"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,
+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,40 @@ 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;
+
+fn elements_with_id<'a, 'le>(
+ root: &'a structs::DocumentOrShadowRoot,
+ id: &Atom,
+) -> &'a [GeckoElement<'le>] {
+ unsafe {
+ let array = bindings::Gecko_GetElementsWithId(root, id.as_ptr());
+ 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 +128,22 @@ 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(&self.0._base_1, id))
}
}
/// A simple wrapper over `ShadowRoot`.
#[derive(Clone, Copy)]
pub struct GeckoShadowRoot<'lr>(pub &'lr structs::ShadowRoot);
impl<'lr> PartialEq for GeckoShadowRoot<'lr> {
@@ -171,16 +183,24 @@ 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(&self.0._base_1, id))
+ }
}
/// 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.
///