diff options
Diffstat (limited to 'servo/components/style/dom_apis.rs')
| -rw-r--r-- | servo/components/style/dom_apis.rs | 814 |
1 files changed, 814 insertions, 0 deletions
diff --git a/servo/components/style/dom_apis.rs b/servo/components/style/dom_apis.rs new file mode 100644 index 0000000000..cdc106e1ad --- /dev/null +++ b/servo/components/style/dom_apis.rs @@ -0,0 +1,814 @@ +/* This Source Code Form is subject to the terms of the Mozilla Public + * License, v. 2.0. If a copy of the MPL was not distributed with this + * file, You can obtain one at https://mozilla.org/MPL/2.0/. */ + +//! Generic implementations of some DOM APIs so they can be shared between Servo +//! and Gecko. + +use crate::context::QuirksMode; +use crate::dom::{TDocument, TElement, TNode, TShadowRoot}; +use crate::invalidation::element::invalidation_map::Dependency; +use crate::invalidation::element::invalidator::{ + DescendantInvalidationLists, Invalidation, SiblingTraversalMap, +}; +use crate::invalidation::element::invalidator::{InvalidationProcessor, InvalidationVector}; +use crate::selector_parser::SelectorImpl; +use crate::values::AtomIdent; +use selectors::attr::CaseSensitivity; +use selectors::attr::{AttrSelectorOperation, NamespaceConstraint}; +use selectors::matching::{ + self, MatchingContext, MatchingForInvalidation, MatchingMode, NeedsSelectorFlags, + SelectorCaches, +}; +use selectors::parser::{Combinator, Component, LocalName}; +use selectors::{Element, SelectorList}; +use smallvec::SmallVec; + +/// <https://dom.spec.whatwg.org/#dom-element-matches> +pub fn element_matches<E>( + element: &E, + selector_list: &SelectorList<E::Impl>, + quirks_mode: QuirksMode, +) -> bool +where + E: Element, +{ + let mut selector_caches = SelectorCaches::default(); + + let mut context = MatchingContext::new( + MatchingMode::Normal, + None, + &mut selector_caches, + quirks_mode, + NeedsSelectorFlags::No, + MatchingForInvalidation::No, + ); + context.scope_element = Some(element.opaque()); + context.current_host = element.containing_shadow_host().map(|e| e.opaque()); + matching::matches_selector_list(selector_list, element, &mut context) +} + +/// <https://dom.spec.whatwg.org/#dom-element-closest> +pub fn element_closest<E>( + element: E, + selector_list: &SelectorList<E::Impl>, + quirks_mode: QuirksMode, +) -> Option<E> +where + E: Element, +{ + let mut selector_caches = SelectorCaches::default(); + + let mut context = MatchingContext::new( + MatchingMode::Normal, + None, + &mut selector_caches, + quirks_mode, + NeedsSelectorFlags::No, + MatchingForInvalidation::No, + ); + context.scope_element = Some(element.opaque()); + context.current_host = element.containing_shadow_host().map(|e| e.opaque()); + + let mut current = Some(element); + while let Some(element) = current.take() { + if matching::matches_selector_list(selector_list, &element, &mut context) { + return Some(element); + } + current = element.parent_element(); + } + + return None; +} + +/// A selector query abstraction, in order to be generic over QuerySelector and +/// QuerySelectorAll. +pub trait SelectorQuery<E: TElement> { + /// The output of the query. + type Output; + + /// Whether the query should stop after the first element has been matched. + fn should_stop_after_first_match() -> bool; + + /// Append an element matching after the first query. + fn append_element(output: &mut Self::Output, element: E); + + /// Returns true if the output is empty. + fn is_empty(output: &Self::Output) -> bool; +} + +/// The result of a querySelectorAll call. +pub type QuerySelectorAllResult<E> = SmallVec<[E; 128]>; + +/// A query for all the elements in a subtree. +pub struct QueryAll; + +impl<E: TElement> SelectorQuery<E> for QueryAll { + type Output = QuerySelectorAllResult<E>; + + fn should_stop_after_first_match() -> bool { + false + } + + fn append_element(output: &mut Self::Output, element: E) { + output.push(element); + } + + fn is_empty(output: &Self::Output) -> bool { + output.is_empty() + } +} + +/// A query for the first in-tree match of all the elements in a subtree. +pub struct QueryFirst; + +impl<E: TElement> SelectorQuery<E> for QueryFirst { + type Output = Option<E>; + + fn should_stop_after_first_match() -> bool { + true + } + + fn append_element(output: &mut Self::Output, element: E) { + if output.is_none() { + *output = Some(element) + } + } + + fn is_empty(output: &Self::Output) -> bool { + output.is_none() + } +} + +struct QuerySelectorProcessor<'a, 'b, E, Q> +where + E: TElement + 'a, + Q: SelectorQuery<E>, + Q::Output: 'a, +{ + results: &'a mut Q::Output, + matching_context: MatchingContext<'b, E::Impl>, + traversal_map: SiblingTraversalMap<E>, + dependencies: &'a [Dependency], +} + +impl<'a, 'b, E, Q> InvalidationProcessor<'a, 'b, E> for QuerySelectorProcessor<'a, 'b, E, Q> +where + E: TElement + 'a, + Q: SelectorQuery<E>, + Q::Output: 'a, +{ + fn light_tree_only(&self) -> bool { + true + } + + fn check_outer_dependency(&mut self, _: &Dependency, _: E) -> bool { + debug_assert!( + false, + "How? We should only have parent-less dependencies here!" + ); + true + } + + fn collect_invalidations( + &mut self, + element: E, + self_invalidations: &mut InvalidationVector<'a>, + descendant_invalidations: &mut DescendantInvalidationLists<'a>, + _sibling_invalidations: &mut InvalidationVector<'a>, + ) -> bool { + // TODO(emilio): If the element is not a root element, and + // selector_list has any descendant combinator, we need to do extra work + // in order to handle properly things like: + // + // <div id="a"> + // <div id="b"> + // <div id="c"></div> + // </div> + // </div> + // + // b.querySelector('#a div'); // Should return "c". + // + // For now, assert it's a root element. + debug_assert!(element.parent_element().is_none()); + + let target_vector = if self.matching_context.scope_element.is_some() { + &mut descendant_invalidations.dom_descendants + } else { + self_invalidations + }; + + for dependency in self.dependencies.iter() { + target_vector.push(Invalidation::new( + dependency, + self.matching_context.current_host.clone(), + )) + } + + false + } + + fn matching_context(&mut self) -> &mut MatchingContext<'b, E::Impl> { + &mut self.matching_context + } + + fn sibling_traversal_map(&self) -> &SiblingTraversalMap<E> { + &self.traversal_map + } + + fn should_process_descendants(&mut self, _: E) -> bool { + if Q::should_stop_after_first_match() { + return Q::is_empty(&self.results); + } + + true + } + + fn invalidated_self(&mut self, e: E) { + Q::append_element(self.results, e); + } + + fn invalidated_sibling(&mut self, e: E, _of: E) { + Q::append_element(self.results, e); + } + + fn recursion_limit_exceeded(&mut self, _e: E) {} + fn invalidated_descendants(&mut self, _e: E, _child: E) {} +} + +fn collect_all_elements<E, Q, F>(root: E::ConcreteNode, results: &mut Q::Output, mut filter: F) +where + E: TElement, + Q: SelectorQuery<E>, + F: FnMut(E) -> bool, +{ + for node in root.dom_descendants() { + let element = match node.as_element() { + Some(e) => e, + None => continue, + }; + + if !filter(element) { + continue; + } + + Q::append_element(results, element); + if Q::should_stop_after_first_match() { + return; + } + } +} + +/// Returns whether a given element connected to `root` is descendant of `root`. +/// +/// NOTE(emilio): if root == element, this returns false. +fn connected_element_is_descendant_of<E>(element: E, root: E::ConcreteNode) -> bool +where + E: TElement, +{ + // 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 +/// or shadow root that `root` is connected to. +fn fast_connected_elements_with_id<'a, N>( + root: N, + id: &AtomIdent, + case_sensitivity: CaseSensitivity, +) -> Result<&'a [N::ConcreteElement], ()> +where + N: TNode + 'a, +{ + if case_sensitivity != CaseSensitivity::CaseSensitive { + return Err(()); + } + + if root.is_in_document() { + return root.owner_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: &AtomIdent, + results: &mut Q::Output, + class_and_id_case_sensitivity: CaseSensitivity, + mut filter: F, +) where + E: TElement, + Q: SelectorQuery<E>, + F: FnMut(E) -> bool, +{ + let elements = match fast_connected_elements_with_id(root, id, class_and_id_case_sensitivity) { + Ok(elements) => elements, + Err(()) => { + collect_all_elements::<E, Q, _>(root, results, |e| { + e.has_id(id, class_and_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 !connected_element_is_descendant_of(*element, root) { + continue; + } + + if !filter(*element) { + continue; + } + + Q::append_element(results, *element); + if Q::should_stop_after_first_match() { + break; + } + } +} + +fn has_attr<E>(element: E, local_name: &AtomIdent) -> bool +where + E: TElement, +{ + let mut found = false; + element.each_attr_name(|name| found |= name == local_name); + found +} + +#[inline(always)] +fn local_name_matches<E>(element: E, local_name: &LocalName<E::Impl>) -> bool +where + E: TElement, +{ + let LocalName { + ref name, + ref lower_name, + } = *local_name; + + let chosen_name = if name == lower_name || element.is_html_element_in_html_document() { + lower_name + } else { + name + }; + + element.local_name() == &**chosen_name +} + +fn get_attr_name(component: &Component<SelectorImpl>) -> Option<&AtomIdent> { + let (name, name_lower) = match component { + Component::AttributeInNoNamespace { ref local_name, .. } => return Some(local_name), + Component::AttributeInNoNamespaceExists { + ref local_name, + ref local_name_lower, + .. + } => (local_name, local_name_lower), + Component::AttributeOther(ref attr) => (&attr.local_name, &attr.local_name_lower), + _ => return None, + }; + if name != name_lower { + return None; // TODO: Maybe optimize this? + } + Some(name) +} + +fn get_id(component: &Component<SelectorImpl>) -> Option<&AtomIdent> { + use selectors::attr::AttrSelectorOperator; + Some(match component { + Component::ID(ref id) => id, + Component::AttributeInNoNamespace { + ref operator, + ref local_name, + ref value, + .. + } => { + if *local_name != local_name!("id") { + return None; + } + if *operator != AttrSelectorOperator::Equal { + return None; + } + AtomIdent::cast(&value.0) + }, + _ => return None, + }) +} + +/// 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, + class_and_id_case_sensitivity: CaseSensitivity, +) -> Result<(), ()> +where + E: TElement, + Q: SelectorQuery<E>, +{ + match *component { + Component::ExplicitUniversalType => { + collect_all_elements::<E, Q, _>(root, results, |_| true) + }, + Component::Class(ref class) => collect_all_elements::<E, Q, _>(root, results, |element| { + element.has_class(class, class_and_id_case_sensitivity) + }), + Component::LocalName(ref local_name) => { + collect_all_elements::<E, Q, _>(root, results, |element| { + local_name_matches(element, local_name) + }) + }, + Component::AttributeInNoNamespaceExists { + ref local_name, + ref local_name_lower, + } => collect_all_elements::<E, Q, _>(root, results, |element| { + element.has_attr_in_no_namespace(matching::select_name( + &element, + local_name, + local_name_lower, + )) + }), + Component::AttributeInNoNamespace { + ref local_name, + ref value, + operator, + case_sensitivity, + } => { + let empty_namespace = selectors::parser::namespace_empty_string::<E::Impl>(); + let namespace_constraint = NamespaceConstraint::Specific(&empty_namespace); + collect_all_elements::<E, Q, _>(root, results, |element| { + element.attr_matches( + &namespace_constraint, + local_name, + &AttrSelectorOperation::WithValue { + operator, + case_sensitivity: matching::to_unconditional_case_sensitivity( + case_sensitivity, + &element, + ), + value, + }, + ) + }) + }, + ref other => { + let id = match get_id(other) { + Some(id) => id, + // TODO(emilio): More fast paths? + None => return Err(()), + }; + collect_elements_with_id::<E, Q, _>( + root, + id, + results, + class_and_id_case_sensitivity, + |_| true, + ); + }, + } + + Ok(()) +} + +enum SimpleFilter<'a> { + Class(&'a AtomIdent), + Attr(&'a AtomIdent), + LocalName(&'a LocalName<SelectorImpl>), +} + +/// Fast paths for a given selector query. +/// +/// When there's only one component, we go directly to +/// `query_selector_single_query`, otherwise, we try to optimize by looking just +/// at the subtrees rooted at ids in the selector, and otherwise we try to look +/// up by class name or local name in the rightmost compound. +/// +/// FIXME(emilio, nbp): This may very well be a good candidate for code to be +/// replaced by HolyJit :) +fn query_selector_fast<E, Q>( + root: E::ConcreteNode, + selector_list: &SelectorList<E::Impl>, + results: &mut Q::Output, + matching_context: &mut MatchingContext<E::Impl>, +) -> Result<(), ()> +where + E: TElement, + Q: SelectorQuery<E>, +{ + // We need to return elements in document order, and reordering them + // afterwards is kinda silly. + if selector_list.len() > 1 { + return Err(()); + } + + let selector = &selector_list.slice()[0]; + let class_and_id_case_sensitivity = matching_context.classes_and_ids_case_sensitivity(); + // Let's just care about the easy cases for now. + if selector.len() == 1 { + if query_selector_single_query::<E, Q>( + root, + selector.iter().next().unwrap(), + results, + class_and_id_case_sensitivity, + ) + .is_ok() + { + return Ok(()); + } + } + + let mut iter = selector.iter(); + let mut combinator: Option<Combinator> = None; + + // We want to optimize some cases where there's no id involved whatsoever, + // like `.foo .bar`, but we don't want to make `#foo .bar` slower because of + // that. + let mut simple_filter = None; + + 'selector_loop: loop { + debug_assert!(combinator.map_or(true, |c| !c.is_sibling())); + + 'component_loop: for component in &mut iter { + match *component { + Component::Class(ref class) => { + if combinator.is_none() { + simple_filter = Some(SimpleFilter::Class(class)); + } + }, + Component::LocalName(ref local_name) => { + if combinator.is_none() { + // Prefer to look at class rather than local-name if + // both are present. + if let Some(SimpleFilter::Class(..)) = simple_filter { + continue; + } + simple_filter = Some(SimpleFilter::LocalName(local_name)); + } + }, + ref other => { + if let Some(id) = get_id(other) { + if combinator.is_none() { + // In the rightmost compound, just find descendants of root that match + // the selector list with that id. + collect_elements_with_id::<E, Q, _>( + root, + id, + results, + class_and_id_case_sensitivity, + |e| { + matching::matches_selector_list( + selector_list, + &e, + matching_context, + ) + }, + ); + return Ok(()); + } + + let elements = fast_connected_elements_with_id( + root, + id, + class_and_id_case_sensitivity, + )?; + 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. + if !Q::should_stop_after_first_match() && elements.len() > 1 { + continue; + } + + for element in elements { + // If the element is not a descendant of the root, then + // it may have descendants that match our selector that + // _are_ descendants of the root, and other descendants + // 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 !connected_element_is_descendant_of(*element, root) { + continue 'component_loop; + } + + query_selector_slow::<E, Q>( + element.as_node(), + selector_list, + results, + matching_context, + ); + + if Q::should_stop_after_first_match() && !Q::is_empty(&results) { + break; + } + } + + return Ok(()); + } + if combinator.is_none() && simple_filter.is_none() { + if let Some(attr_name) = get_attr_name(other) { + simple_filter = Some(SimpleFilter::Attr(attr_name)); + } + } + }, + } + } + + loop { + let next_combinator = match iter.next_sequence() { + None => break 'selector_loop, + Some(c) => c, + }; + + // We don't want to scan stuff affected by sibling combinators, + // given we scan the subtree of elements with a given id (and we + // don't want to care about scanning the siblings' subtrees). + if next_combinator.is_sibling() { + // Advance to the next combinator. + for _ in &mut iter {} + continue; + } + + combinator = Some(next_combinator); + break; + } + } + + // We got here without finding any ID or such that we could handle. Try to + // use one of the simple filters. + let simple_filter = match simple_filter { + Some(f) => f, + None => return Err(()), + }; + + match simple_filter { + SimpleFilter::Class(ref class) => { + collect_all_elements::<E, Q, _>(root, results, |element| { + element.has_class(class, class_and_id_case_sensitivity) && + matching::matches_selector_list(selector_list, &element, matching_context) + }); + }, + SimpleFilter::LocalName(ref local_name) => { + collect_all_elements::<E, Q, _>(root, results, |element| { + local_name_matches(element, local_name) && + matching::matches_selector_list(selector_list, &element, matching_context) + }); + }, + SimpleFilter::Attr(ref local_name) => { + collect_all_elements::<E, Q, _>(root, results, |element| { + has_attr(element, local_name) && + matching::matches_selector_list(selector_list, &element, matching_context) + }); + }, + } + + Ok(()) +} + +// Slow path for a given selector query. +fn query_selector_slow<E, Q>( + root: E::ConcreteNode, + selector_list: &SelectorList<E::Impl>, + results: &mut Q::Output, + matching_context: &mut MatchingContext<E::Impl>, +) where + E: TElement, + Q: SelectorQuery<E>, +{ + collect_all_elements::<E, Q, _>(root, results, |element| { + matching::matches_selector_list(selector_list, &element, matching_context) + }); +} + +/// Whether the invalidation machinery should be used for this query. +#[derive(PartialEq)] +pub enum MayUseInvalidation { + /// We may use it if we deem it useful. + Yes, + /// Don't use it. + No, +} + +/// <https://dom.spec.whatwg.org/#dom-parentnode-queryselector> +pub fn query_selector<E, Q>( + root: E::ConcreteNode, + selector_list: &SelectorList<E::Impl>, + results: &mut Q::Output, + may_use_invalidation: MayUseInvalidation, +) where + E: TElement, + Q: SelectorQuery<E>, +{ + use crate::invalidation::element::invalidator::TreeStyleInvalidator; + + let mut selector_caches = SelectorCaches::default(); + let quirks_mode = root.owner_doc().quirks_mode(); + + let mut matching_context = MatchingContext::new( + MatchingMode::Normal, + None, + &mut selector_caches, + quirks_mode, + NeedsSelectorFlags::No, + MatchingForInvalidation::No, + ); + let root_element = root.as_element(); + matching_context.scope_element = root_element.map(|e| e.opaque()); + matching_context.current_host = match root_element { + Some(root) => root.containing_shadow_host().map(|host| host.opaque()), + None => root.as_shadow_root().map(|root| root.host().opaque()), + }; + + let fast_result = + query_selector_fast::<E, Q>(root, selector_list, results, &mut matching_context); + + if fast_result.is_ok() { + return; + } + + // Slow path: Use the invalidation machinery if we're a root, and tree + // traversal otherwise. + // + // See the comment in collect_invalidations to see why only if we're a root. + // + // The invalidation mechanism is only useful in presence of combinators. + // + // We could do that check properly here, though checking the length of the + // selectors is a good heuristic. + // + // A selector with a combinator needs to have a length of at least 3: A + // simple selector, a combinator, and another simple selector. + let invalidation_may_be_useful = may_use_invalidation == MayUseInvalidation::Yes && + selector_list.slice().iter().any(|s| s.len() > 2); + + if root_element.is_some() || !invalidation_may_be_useful { + query_selector_slow::<E, Q>(root, selector_list, results, &mut matching_context); + } else { + let dependencies = selector_list + .slice() + .iter() + .map(|selector| Dependency::for_full_selector_invalidation(selector.clone())) + .collect::<SmallVec<[_; 5]>>(); + let mut processor = QuerySelectorProcessor::<E, Q> { + results, + matching_context, + traversal_map: SiblingTraversalMap::default(), + dependencies: &dependencies, + }; + + for node in root.dom_children() { + if let Some(e) = node.as_element() { + TreeStyleInvalidator::new(e, /* stack_limit_checker = */ None, &mut processor) + .invalidate(); + } + } + } +} |