summaryrefslogtreecommitdiffstats
path: root/servo/components/selectors/matching.rs
diff options
context:
space:
mode:
authorDaniel Baumann <daniel.baumann@progress-linux.org>2024-04-19 00:47:55 +0000
committerDaniel Baumann <daniel.baumann@progress-linux.org>2024-04-19 00:47:55 +0000
commit26a029d407be480d791972afb5975cf62c9360a6 (patch)
treef435a8308119effd964b339f76abb83a57c29483 /servo/components/selectors/matching.rs
parentInitial commit. (diff)
downloadfirefox-26a029d407be480d791972afb5975cf62c9360a6.tar.xz
firefox-26a029d407be480d791972afb5975cf62c9360a6.zip
Adding upstream version 124.0.1.upstream/124.0.1
Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>
Diffstat (limited to 'servo/components/selectors/matching.rs')
-rw-r--r--servo/components/selectors/matching.rs1370
1 files changed, 1370 insertions, 0 deletions
diff --git a/servo/components/selectors/matching.rs b/servo/components/selectors/matching.rs
new file mode 100644
index 0000000000..763f65d547
--- /dev/null
+++ b/servo/components/selectors/matching.rs
@@ -0,0 +1,1370 @@
+/* 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/. */
+
+use crate::attr::{
+ AttrSelectorOperation, AttrSelectorWithOptionalNamespace, CaseSensitivity, NamespaceConstraint,
+ ParsedAttrSelectorOperation, ParsedCaseSensitivity,
+};
+use crate::bloom::{BloomFilter, BLOOM_HASH_MASK};
+use crate::parser::{
+ AncestorHashes, Combinator, Component, LocalName, NthSelectorData, RelativeSelectorMatchHint,
+};
+use crate::parser::{
+ NonTSPseudoClass, RelativeSelector, Selector, SelectorImpl, SelectorIter, SelectorList,
+};
+use crate::relative_selector::cache::RelativeSelectorCachedMatch;
+use crate::tree::Element;
+use smallvec::SmallVec;
+use std::borrow::Borrow;
+
+pub use crate::context::*;
+
+// The bloom filter for descendant CSS selectors will have a <1% false
+// positive rate until it has this many selectors in it, then it will
+// rapidly increase.
+pub static RECOMMENDED_SELECTOR_BLOOM_FILTER_SIZE: usize = 4096;
+
+bitflags! {
+ /// Set of flags that are set on either the element or its parent (depending
+ /// on the flag) if the element could potentially match a selector.
+ #[derive(Clone, Copy)]
+ pub struct ElementSelectorFlags: usize {
+ /// When a child is added or removed from the parent, all the children
+ /// must be restyled, because they may match :nth-last-child,
+ /// :last-of-type, :nth-last-of-type, or :only-of-type.
+ const HAS_SLOW_SELECTOR = 1 << 0;
+
+ /// When a child is added or removed from the parent, any later
+ /// children must be restyled, because they may match :nth-child,
+ /// :first-of-type, or :nth-of-type.
+ const HAS_SLOW_SELECTOR_LATER_SIBLINGS = 1 << 1;
+
+ /// HAS_SLOW_SELECTOR* was set by the presence of :nth (But not of).
+ const HAS_SLOW_SELECTOR_NTH = 1 << 2;
+
+ /// When a DOM mutation occurs on a child that might be matched by
+ /// :nth-last-child(.. of <selector list>), earlier children must be
+ /// restyled, and HAS_SLOW_SELECTOR will be set (which normally
+ /// indicates that all children will be restyled).
+ ///
+ /// Similarly, when a DOM mutation occurs on a child that might be
+ /// matched by :nth-child(.. of <selector list>), later children must be
+ /// restyled, and HAS_SLOW_SELECTOR_LATER_SIBLINGS will be set.
+ const HAS_SLOW_SELECTOR_NTH_OF = 1 << 3;
+
+ /// When a child is added or removed from the parent, the first and
+ /// last children must be restyled, because they may match :first-child,
+ /// :last-child, or :only-child.
+ const HAS_EDGE_CHILD_SELECTOR = 1 << 4;
+
+ /// The element has an empty selector, so when a child is appended we
+ /// might need to restyle the parent completely.
+ const HAS_EMPTY_SELECTOR = 1 << 5;
+
+ /// The element may anchor a relative selector.
+ const ANCHORS_RELATIVE_SELECTOR = 1 << 6;
+
+ /// The element may anchor a relative selector that is not the subject
+ /// of the whole selector.
+ const ANCHORS_RELATIVE_SELECTOR_NON_SUBJECT = 1 << 7;
+
+ /// The element is reached by a relative selector search in the sibling direction.
+ const RELATIVE_SELECTOR_SEARCH_DIRECTION_SIBLING = 1 << 8;
+
+ /// The element is reached by a relative selector search in the ancestor direction.
+ const RELATIVE_SELECTOR_SEARCH_DIRECTION_ANCESTOR = 1 << 9;
+
+ // The element is reached by a relative selector search in both sibling and ancestor directions.
+ const RELATIVE_SELECTOR_SEARCH_DIRECTION_ANCESTOR_SIBLING =
+ Self::RELATIVE_SELECTOR_SEARCH_DIRECTION_SIBLING.bits() |
+ Self::RELATIVE_SELECTOR_SEARCH_DIRECTION_ANCESTOR.bits();
+ }
+}
+
+impl ElementSelectorFlags {
+ /// Returns the subset of flags that apply to the element.
+ pub fn for_self(self) -> ElementSelectorFlags {
+ self & (ElementSelectorFlags::HAS_EMPTY_SELECTOR |
+ ElementSelectorFlags::ANCHORS_RELATIVE_SELECTOR |
+ ElementSelectorFlags::ANCHORS_RELATIVE_SELECTOR_NON_SUBJECT |
+ ElementSelectorFlags::RELATIVE_SELECTOR_SEARCH_DIRECTION_SIBLING |
+ ElementSelectorFlags::RELATIVE_SELECTOR_SEARCH_DIRECTION_ANCESTOR)
+ }
+
+ /// Returns the subset of flags that apply to the parent.
+ pub fn for_parent(self) -> ElementSelectorFlags {
+ self & (ElementSelectorFlags::HAS_SLOW_SELECTOR |
+ ElementSelectorFlags::HAS_SLOW_SELECTOR_LATER_SIBLINGS |
+ ElementSelectorFlags::HAS_SLOW_SELECTOR_NTH |
+ ElementSelectorFlags::HAS_SLOW_SELECTOR_NTH_OF |
+ ElementSelectorFlags::HAS_EDGE_CHILD_SELECTOR)
+ }
+}
+
+/// Holds per-compound-selector data.
+struct LocalMatchingContext<'a, 'b: 'a, Impl: SelectorImpl> {
+ shared: &'a mut MatchingContext<'b, Impl>,
+ rightmost: SubjectOrPseudoElement,
+ quirks_data: Option<SelectorIter<'a, Impl>>,
+}
+
+#[inline(always)]
+pub fn matches_selector_list<E>(
+ selector_list: &SelectorList<E::Impl>,
+ element: &E,
+ context: &mut MatchingContext<E::Impl>,
+) -> bool
+where
+ E: Element,
+{
+ // This is pretty much any(..) but manually inlined because the compiler
+ // refuses to do so from querySelector / querySelectorAll.
+ for selector in selector_list.slice() {
+ let matches = matches_selector(selector, 0, None, element, context);
+ if matches {
+ return true;
+ }
+ }
+
+ false
+}
+
+#[inline(always)]
+fn may_match(hashes: &AncestorHashes, bf: &BloomFilter) -> bool {
+ // Check the first three hashes. Note that we can check for zero before
+ // masking off the high bits, since if any of the first three hashes is
+ // zero the fourth will be as well. We also take care to avoid the
+ // special-case complexity of the fourth hash until we actually reach it,
+ // because we usually don't.
+ //
+ // To be clear: this is all extremely hot.
+ for i in 0..3 {
+ let packed = hashes.packed_hashes[i];
+ if packed == 0 {
+ // No more hashes left - unable to fast-reject.
+ return true;
+ }
+
+ if !bf.might_contain_hash(packed & BLOOM_HASH_MASK) {
+ // Hooray! We fast-rejected on this hash.
+ return false;
+ }
+ }
+
+ // Now do the slighty-more-complex work of synthesizing the fourth hash,
+ // and check it against the filter if it exists.
+ let fourth = hashes.fourth_hash();
+ fourth == 0 || bf.might_contain_hash(fourth)
+}
+
+/// A result of selector matching, includes 3 failure types,
+///
+/// NotMatchedAndRestartFromClosestLaterSibling
+/// NotMatchedAndRestartFromClosestDescendant
+/// NotMatchedGlobally
+///
+/// When NotMatchedGlobally appears, stop selector matching completely since
+/// the succeeding selectors never matches.
+/// It is raised when
+/// Child combinator cannot find the candidate element.
+/// Descendant combinator cannot find the candidate element.
+///
+/// When NotMatchedAndRestartFromClosestDescendant appears, the selector
+/// matching does backtracking and restarts from the closest Descendant
+/// combinator.
+/// It is raised when
+/// NextSibling combinator cannot find the candidate element.
+/// LaterSibling combinator cannot find the candidate element.
+/// Child combinator doesn't match on the found element.
+///
+/// When NotMatchedAndRestartFromClosestLaterSibling appears, the selector
+/// matching does backtracking and restarts from the closest LaterSibling
+/// combinator.
+/// It is raised when
+/// NextSibling combinator doesn't match on the found element.
+///
+/// For example, when the selector "d1 d2 a" is provided and we cannot *find*
+/// an appropriate ancestor element for "d1", this selector matching raises
+/// NotMatchedGlobally since even if "d2" is moved to more upper element, the
+/// candidates for "d1" becomes less than before and d1 .
+///
+/// The next example is siblings. When the selector "b1 + b2 ~ d1 a" is
+/// provided and we cannot *find* an appropriate brother element for b1,
+/// the selector matching raises NotMatchedAndRestartFromClosestDescendant.
+/// The selectors ("b1 + b2 ~") doesn't match and matching restart from "d1".
+///
+/// The additional example is child and sibling. When the selector
+/// "b1 + c1 > b2 ~ d1 a" is provided and the selector "b1" doesn't match on
+/// the element, this "b1" raises NotMatchedAndRestartFromClosestLaterSibling.
+/// However since the selector "c1" raises
+/// NotMatchedAndRestartFromClosestDescendant. So the selector
+/// "b1 + c1 > b2 ~ " doesn't match and restart matching from "d1".
+#[derive(Clone, Copy, Eq, PartialEq)]
+enum SelectorMatchingResult {
+ Matched,
+ NotMatchedAndRestartFromClosestLaterSibling,
+ NotMatchedAndRestartFromClosestDescendant,
+ NotMatchedGlobally,
+}
+
+/// Matches a selector, fast-rejecting against a bloom filter.
+///
+/// We accept an offset to allow consumers to represent and match against
+/// partial selectors (indexed from the right). We use this API design, rather
+/// than having the callers pass a SelectorIter, because creating a SelectorIter
+/// requires dereferencing the selector to get the length, which adds an
+/// unncessary cache miss for cases when we can fast-reject with AncestorHashes
+/// (which the caller can store inline with the selector pointer).
+#[inline(always)]
+pub fn matches_selector<E>(
+ selector: &Selector<E::Impl>,
+ offset: usize,
+ hashes: Option<&AncestorHashes>,
+ element: &E,
+ context: &mut MatchingContext<E::Impl>,
+) -> bool
+where
+ E: Element,
+{
+ // Use the bloom filter to fast-reject.
+ if let Some(hashes) = hashes {
+ if let Some(filter) = context.bloom_filter {
+ if !may_match(hashes, filter) {
+ return false;
+ }
+ }
+ }
+ matches_complex_selector(
+ selector.iter_from(offset),
+ element,
+ context,
+ if selector.is_rightmost(offset) {
+ SubjectOrPseudoElement::Yes
+ } else {
+ SubjectOrPseudoElement::No
+ },
+ )
+}
+
+/// Whether a compound selector matched, and whether it was the rightmost
+/// selector inside the complex selector.
+pub enum CompoundSelectorMatchingResult {
+ /// The selector was fully matched.
+ FullyMatched,
+ /// The compound selector matched, and the next combinator offset is
+ /// `next_combinator_offset`.
+ Matched { next_combinator_offset: usize },
+ /// The selector didn't match.
+ NotMatched,
+}
+
+/// Matches a compound selector belonging to `selector`, starting at offset
+/// `from_offset`, matching left to right.
+///
+/// Requires that `from_offset` points to a `Combinator`.
+///
+/// NOTE(emilio): This doesn't allow to match in the leftmost sequence of the
+/// complex selector, but it happens to be the case we don't need it.
+pub fn matches_compound_selector_from<E>(
+ selector: &Selector<E::Impl>,
+ mut from_offset: usize,
+ context: &mut MatchingContext<E::Impl>,
+ element: &E,
+) -> CompoundSelectorMatchingResult
+where
+ E: Element,
+{
+ if cfg!(debug_assertions) && from_offset != 0 {
+ selector.combinator_at_parse_order(from_offset - 1); // This asserts.
+ }
+
+ let mut local_context = LocalMatchingContext {
+ shared: context,
+ // We have no info if this is an outer selector. This function is called in
+ // an invalidation context, which only calls this for non-subject (i.e.
+ // Non-rightmost) positions.
+ rightmost: SubjectOrPseudoElement::No,
+ quirks_data: None,
+ };
+
+ // Find the end of the selector or the next combinator, then match
+ // backwards, so that we match in the same order as
+ // matches_complex_selector, which is usually faster.
+ let start_offset = from_offset;
+ for component in selector.iter_raw_parse_order_from(from_offset) {
+ if matches!(*component, Component::Combinator(..)) {
+ debug_assert_ne!(from_offset, 0, "Selector started with a combinator?");
+ break;
+ }
+
+ from_offset += 1;
+ }
+
+ debug_assert!(from_offset >= 1);
+ debug_assert!(from_offset <= selector.len());
+
+ let iter = selector.iter_from(selector.len() - from_offset);
+ debug_assert!(
+ iter.clone().next().is_some() ||
+ (from_offset != selector.len() &&
+ matches!(
+ selector.combinator_at_parse_order(from_offset),
+ Combinator::SlotAssignment | Combinator::PseudoElement
+ )),
+ "Got the math wrong: {:?} | {:?} | {} {}",
+ selector,
+ selector.iter_raw_match_order().as_slice(),
+ from_offset,
+ start_offset
+ );
+
+ for component in iter {
+ if !matches_simple_selector(component, element, &mut local_context) {
+ return CompoundSelectorMatchingResult::NotMatched;
+ }
+ }
+
+ if from_offset != selector.len() {
+ return CompoundSelectorMatchingResult::Matched {
+ next_combinator_offset: from_offset,
+ };
+ }
+
+ CompoundSelectorMatchingResult::FullyMatched
+}
+
+/// Matches a complex selector.
+#[inline(always)]
+fn matches_complex_selector<E>(
+ mut iter: SelectorIter<E::Impl>,
+ element: &E,
+ context: &mut MatchingContext<E::Impl>,
+ rightmost: SubjectOrPseudoElement,
+) -> bool
+where
+ E: Element,
+{
+ // If this is the special pseudo-element mode, consume the ::pseudo-element
+ // before proceeding, since the caller has already handled that part.
+ if context.matching_mode() == MatchingMode::ForStatelessPseudoElement && !context.is_nested() {
+ // Consume the pseudo.
+ match *iter.next().unwrap() {
+ Component::PseudoElement(ref pseudo) => {
+ if let Some(ref f) = context.pseudo_element_matching_fn {
+ if !f(pseudo) {
+ return false;
+ }
+ }
+ },
+ ref other => {
+ debug_assert!(
+ false,
+ "Used MatchingMode::ForStatelessPseudoElement \
+ in a non-pseudo selector {:?}",
+ other
+ );
+ return false;
+ },
+ }
+
+ if !iter.matches_for_stateless_pseudo_element() {
+ return false;
+ }
+
+ // Advance to the non-pseudo-element part of the selector.
+ let next_sequence = iter.next_sequence().unwrap();
+ debug_assert_eq!(next_sequence, Combinator::PseudoElement);
+ }
+
+ let result = matches_complex_selector_internal(iter, element, context, rightmost);
+
+ matches!(result, SelectorMatchingResult::Matched)
+}
+
+/// Matches each selector of a list as a complex selector
+fn matches_complex_selector_list<E: Element>(
+ list: &[Selector<E::Impl>],
+ element: &E,
+ context: &mut MatchingContext<E::Impl>,
+ rightmost: SubjectOrPseudoElement,
+) -> bool {
+ for selector in list {
+ if matches_complex_selector(selector.iter(), element, context, rightmost) {
+ return true;
+ }
+ }
+ false
+}
+
+fn matches_relative_selector<E: Element>(
+ relative_selector: &RelativeSelector<E::Impl>,
+ element: &E,
+ context: &mut MatchingContext<E::Impl>,
+ rightmost: SubjectOrPseudoElement,
+) -> bool {
+ // Overall, we want to mark the path that we've traversed so that when an element
+ // is invalidated, we early-reject unnecessary relative selector invalidations.
+ if relative_selector.match_hint.is_descendant_direction() {
+ if context.needs_selector_flags() {
+ element.apply_selector_flags(
+ ElementSelectorFlags::RELATIVE_SELECTOR_SEARCH_DIRECTION_ANCESTOR,
+ );
+ }
+ let mut next_element = element.first_element_child();
+ while let Some(el) = next_element {
+ if context.needs_selector_flags() {
+ el.apply_selector_flags(
+ ElementSelectorFlags::RELATIVE_SELECTOR_SEARCH_DIRECTION_ANCESTOR,
+ );
+ }
+ let mut matched = matches_complex_selector(
+ relative_selector.selector.iter(),
+ &el,
+ context,
+ rightmost,
+ );
+ if !matched && relative_selector.match_hint.is_subtree() {
+ matched = matches_relative_selector_subtree(
+ &relative_selector.selector,
+ &el,
+ context,
+ rightmost,
+ );
+ }
+ if matched {
+ return true;
+ }
+ next_element = el.next_sibling_element();
+ }
+ } else {
+ debug_assert!(
+ matches!(
+ relative_selector.match_hint,
+ RelativeSelectorMatchHint::InNextSibling |
+ RelativeSelectorMatchHint::InNextSiblingSubtree |
+ RelativeSelectorMatchHint::InSibling |
+ RelativeSelectorMatchHint::InSiblingSubtree
+ ),
+ "Not descendant direction, but also not sibling direction?"
+ );
+ if context.needs_selector_flags() {
+ element.apply_selector_flags(
+ ElementSelectorFlags::RELATIVE_SELECTOR_SEARCH_DIRECTION_SIBLING,
+ );
+ }
+ let sibling_flag = if relative_selector.match_hint.is_subtree() {
+ ElementSelectorFlags::RELATIVE_SELECTOR_SEARCH_DIRECTION_ANCESTOR_SIBLING
+ } else {
+ ElementSelectorFlags::RELATIVE_SELECTOR_SEARCH_DIRECTION_SIBLING
+ };
+ let mut next_element = element.next_sibling_element();
+ while let Some(el) = next_element {
+ if context.needs_selector_flags() {
+ el.apply_selector_flags(sibling_flag);
+ }
+ let matched = if relative_selector.match_hint.is_subtree() {
+ matches_relative_selector_subtree(
+ &relative_selector.selector,
+ &el,
+ context,
+ rightmost,
+ )
+ } else {
+ matches_complex_selector(relative_selector.selector.iter(), &el, context, rightmost)
+ };
+ if matched {
+ return true;
+ }
+ if relative_selector.match_hint.is_next_sibling() {
+ break;
+ }
+ next_element = el.next_sibling_element();
+ }
+ }
+ return false;
+}
+
+fn relative_selector_match_early<E: Element>(
+ selector: &RelativeSelector<E::Impl>,
+ element: &E,
+ context: &mut MatchingContext<E::Impl>,
+) -> Option<bool> {
+ if context.matching_for_invalidation() {
+ // In the context of invalidation, we can't use caching/filtering due to
+ // now/then matches. DOM structure also may have changed, so just pretend
+ // that we always match.
+ return Some(!context.in_negation());
+ }
+ // See if we can return a cached result.
+ if let Some(cached) = context
+ .selector_caches
+ .relative_selector
+ .lookup(element.opaque(), selector)
+ {
+ return Some(cached.matched());
+ }
+ // See if we can fast-reject.
+ if context
+ .selector_caches
+ .relative_selector_filter_map
+ .fast_reject(element, selector, context.quirks_mode())
+ {
+ // Alright, add as unmatched to cache.
+ context.selector_caches.relative_selector.add(
+ element.opaque(),
+ selector,
+ RelativeSelectorCachedMatch::NotMatched,
+ );
+ return Some(false);
+ }
+ None
+}
+
+fn match_relative_selectors<E: Element>(
+ selectors: &[RelativeSelector<E::Impl>],
+ element: &E,
+ context: &mut MatchingContext<E::Impl>,
+ rightmost: SubjectOrPseudoElement,
+) -> bool {
+ if context.relative_selector_anchor().is_some() {
+ // FIXME(emilio): This currently can happen with nesting, and it's not fully
+ // correct, arguably. But the ideal solution isn't super-clear either. For now,
+ // cope with it and explicitly reject it at match time. See [1] for discussion.
+ //
+ // [1]: https://github.com/w3c/csswg-drafts/issues/9600
+ return false;
+ }
+ context.nest_for_relative_selector(element.opaque(), |context| {
+ do_match_relative_selectors(selectors, element, context, rightmost)
+ })
+}
+
+/// Matches a relative selector in a list of relative selectors.
+fn do_match_relative_selectors<E: Element>(
+ selectors: &[RelativeSelector<E::Impl>],
+ element: &E,
+ context: &mut MatchingContext<E::Impl>,
+ rightmost: SubjectOrPseudoElement,
+) -> bool {
+ // Due to style sharing implications (See style sharing code), we mark the current styling context
+ // to mark elements considered for :has matching. Additionally, we want to mark the elements themselves,
+ // since we don't want to indiscriminately invalidate every element as a potential anchor.
+ if rightmost == SubjectOrPseudoElement::Yes {
+ context.considered_relative_selector.considered_anchor();
+ if context.needs_selector_flags() {
+ element.apply_selector_flags(ElementSelectorFlags::ANCHORS_RELATIVE_SELECTOR);
+ }
+ } else {
+ context.considered_relative_selector.considered();
+ if context.needs_selector_flags() {
+ element
+ .apply_selector_flags(ElementSelectorFlags::ANCHORS_RELATIVE_SELECTOR_NON_SUBJECT);
+ }
+ }
+
+ for relative_selector in selectors.iter() {
+ if let Some(result) = relative_selector_match_early(relative_selector, element, context) {
+ if result {
+ return true;
+ }
+ // Early return indicates no match, continue to next selector.
+ continue;
+ }
+
+ let matched = matches_relative_selector(relative_selector, element, context, rightmost);
+ context.selector_caches.relative_selector.add(
+ element.opaque(),
+ relative_selector,
+ if matched {
+ RelativeSelectorCachedMatch::Matched
+ } else {
+ RelativeSelectorCachedMatch::NotMatched
+ },
+ );
+ if matched {
+ return true;
+ }
+ }
+
+ false
+}
+
+fn matches_relative_selector_subtree<E: Element>(
+ selector: &Selector<E::Impl>,
+ element: &E,
+ context: &mut MatchingContext<E::Impl>,
+ rightmost: SubjectOrPseudoElement,
+) -> bool {
+ let mut current = element.first_element_child();
+
+ while let Some(el) = current {
+ if context.needs_selector_flags() {
+ el.apply_selector_flags(
+ ElementSelectorFlags::RELATIVE_SELECTOR_SEARCH_DIRECTION_ANCESTOR,
+ );
+ }
+ if matches_complex_selector(selector.iter(), &el, context, rightmost) {
+ return true;
+ }
+
+ if matches_relative_selector_subtree(selector, &el, context, rightmost) {
+ return true;
+ }
+
+ current = el.next_sibling_element();
+ }
+
+ false
+}
+
+/// Whether the :hover and :active quirk applies.
+///
+/// https://quirks.spec.whatwg.org/#the-active-and-hover-quirk
+fn hover_and_active_quirk_applies<Impl: SelectorImpl>(
+ selector_iter: &SelectorIter<Impl>,
+ context: &MatchingContext<Impl>,
+ rightmost: SubjectOrPseudoElement,
+) -> bool {
+ if context.quirks_mode() != QuirksMode::Quirks {
+ return false;
+ }
+
+ if context.is_nested() {
+ return false;
+ }
+
+ // This compound selector had a pseudo-element to the right that we
+ // intentionally skipped.
+ if rightmost == SubjectOrPseudoElement::Yes &&
+ context.matching_mode() == MatchingMode::ForStatelessPseudoElement
+ {
+ return false;
+ }
+
+ selector_iter.clone().all(|simple| match *simple {
+ Component::LocalName(_) |
+ Component::AttributeInNoNamespaceExists { .. } |
+ Component::AttributeInNoNamespace { .. } |
+ Component::AttributeOther(_) |
+ Component::ID(_) |
+ Component::Class(_) |
+ Component::PseudoElement(_) |
+ Component::Negation(_) |
+ Component::Empty |
+ Component::Nth(_) |
+ Component::NthOf(_) => false,
+ Component::NonTSPseudoClass(ref pseudo_class) => pseudo_class.is_active_or_hover(),
+ _ => true,
+ })
+}
+
+#[derive(Clone, Copy, PartialEq)]
+enum SubjectOrPseudoElement {
+ Yes,
+ No,
+}
+
+fn host_for_part<E>(element: &E, context: &MatchingContext<E::Impl>) -> Option<E>
+where
+ E: Element,
+{
+ let scope = context.current_host;
+ let mut curr = element.containing_shadow_host()?;
+ if scope == Some(curr.opaque()) {
+ return Some(curr);
+ }
+ loop {
+ let parent = curr.containing_shadow_host();
+ if parent.as_ref().map(|h| h.opaque()) == scope {
+ return Some(curr);
+ }
+ curr = parent?;
+ }
+}
+
+fn assigned_slot<E>(element: &E, context: &MatchingContext<E::Impl>) -> Option<E>
+where
+ E: Element,
+{
+ debug_assert!(element
+ .assigned_slot()
+ .map_or(true, |s| s.is_html_slot_element()));
+ let scope = context.current_host?;
+ let mut current_slot = element.assigned_slot()?;
+ while current_slot.containing_shadow_host().unwrap().opaque() != scope {
+ current_slot = current_slot.assigned_slot()?;
+ }
+ Some(current_slot)
+}
+
+#[inline(always)]
+fn next_element_for_combinator<E>(
+ element: &E,
+ combinator: Combinator,
+ selector: &SelectorIter<E::Impl>,
+ context: &MatchingContext<E::Impl>,
+) -> Option<E>
+where
+ E: Element,
+{
+ match combinator {
+ Combinator::NextSibling | Combinator::LaterSibling => element.prev_sibling_element(),
+ Combinator::Child | Combinator::Descendant => {
+ match element.parent_element() {
+ Some(e) => return Some(e),
+ None => {},
+ }
+
+ if !element.parent_node_is_shadow_root() {
+ return None;
+ }
+
+ // https://drafts.csswg.org/css-scoping/#host-element-in-tree:
+ //
+ // For the purpose of Selectors, a shadow host also appears in
+ // its shadow tree, with the contents of the shadow tree treated
+ // as its children. (In other words, the shadow host is treated as
+ // replacing the shadow root node.)
+ //
+ // and also:
+ //
+ // When considered within its own shadow trees, the shadow host is
+ // featureless. Only the :host, :host(), and :host-context()
+ // pseudo-classes are allowed to match it.
+ //
+ // Since we know that the parent is a shadow root, we necessarily
+ // are in a shadow tree of the host, and the next selector will only
+ // match if the selector is a featureless :host selector.
+ if !selector.clone().is_featureless_host_selector() {
+ return None;
+ }
+
+ element.containing_shadow_host()
+ },
+ Combinator::Part => host_for_part(element, context),
+ Combinator::SlotAssignment => assigned_slot(element, context),
+ Combinator::PseudoElement => element.pseudo_element_originating_element(),
+ }
+}
+
+fn matches_complex_selector_internal<E>(
+ mut selector_iter: SelectorIter<E::Impl>,
+ element: &E,
+ context: &mut MatchingContext<E::Impl>,
+ rightmost: SubjectOrPseudoElement,
+) -> SelectorMatchingResult
+where
+ E: Element,
+{
+ debug!(
+ "Matching complex selector {:?} for {:?}",
+ selector_iter, element
+ );
+
+ let matches_compound_selector =
+ matches_compound_selector(&mut selector_iter, element, context, rightmost);
+
+ let combinator = selector_iter.next_sequence();
+ if combinator.map_or(false, |c| c.is_sibling()) {
+ if context.needs_selector_flags() {
+ element.apply_selector_flags(ElementSelectorFlags::HAS_SLOW_SELECTOR_LATER_SIBLINGS);
+ }
+ }
+
+ if !matches_compound_selector {
+ return SelectorMatchingResult::NotMatchedAndRestartFromClosestLaterSibling;
+ }
+
+ let combinator = match combinator {
+ None => return SelectorMatchingResult::Matched,
+ Some(c) => c,
+ };
+
+ let (candidate_not_found, mut rightmost) = match combinator {
+ Combinator::NextSibling | Combinator::LaterSibling => {
+ (SelectorMatchingResult::NotMatchedAndRestartFromClosestDescendant, SubjectOrPseudoElement::No)
+ },
+ Combinator::Child |
+ Combinator::Descendant |
+ Combinator::SlotAssignment |
+ Combinator::Part => (SelectorMatchingResult::NotMatchedGlobally, SubjectOrPseudoElement::No),
+ Combinator::PseudoElement => (SelectorMatchingResult::NotMatchedGlobally, rightmost),
+ };
+
+ // Stop matching :visited as soon as we find a link, or a combinator for
+ // something that isn't an ancestor.
+ let mut visited_handling = if combinator.is_sibling() {
+ VisitedHandlingMode::AllLinksUnvisited
+ } else {
+ context.visited_handling()
+ };
+
+ let mut element = element.clone();
+ loop {
+ if element.is_link() {
+ visited_handling = VisitedHandlingMode::AllLinksUnvisited;
+ }
+
+ element = match next_element_for_combinator(&element, combinator, &selector_iter, &context)
+ {
+ None => return candidate_not_found,
+ Some(next_element) => next_element,
+ };
+
+ let result = context.with_visited_handling_mode(visited_handling, |context| {
+ matches_complex_selector_internal(
+ selector_iter.clone(),
+ &element,
+ context,
+ rightmost,
+ )
+ });
+
+ if !matches!(combinator, Combinator::PseudoElement) {
+ rightmost = SubjectOrPseudoElement::No;
+ }
+
+ match (result, combinator) {
+ // Return the status immediately.
+ (SelectorMatchingResult::Matched, _) |
+ (SelectorMatchingResult::NotMatchedGlobally, _) |
+ (_, Combinator::NextSibling) => {
+ return result;
+ },
+
+ // Upgrade the failure status to
+ // NotMatchedAndRestartFromClosestDescendant.
+ (_, Combinator::PseudoElement) | (_, Combinator::Child) => {
+ return SelectorMatchingResult::NotMatchedAndRestartFromClosestDescendant;
+ },
+
+ // If the failure status is
+ // NotMatchedAndRestartFromClosestDescendant and combinator is
+ // Combinator::LaterSibling, give up this Combinator::LaterSibling
+ // matching and restart from the closest descendant combinator.
+ (
+ SelectorMatchingResult::NotMatchedAndRestartFromClosestDescendant,
+ Combinator::LaterSibling,
+ ) => {
+ return result;
+ },
+
+ // The Combinator::Descendant combinator and the status is
+ // NotMatchedAndRestartFromClosestLaterSibling or
+ // NotMatchedAndRestartFromClosestDescendant, or the
+ // Combinator::LaterSibling combinator and the status is
+ // NotMatchedAndRestartFromClosestDescendant, we can continue to
+ // matching on the next candidate element.
+ _ => {},
+ }
+ }
+}
+
+#[inline]
+fn matches_local_name<E>(element: &E, local_name: &LocalName<E::Impl>) -> bool
+where
+ E: Element,
+{
+ let name = select_name(element, &local_name.name, &local_name.lower_name).borrow();
+ element.has_local_name(name)
+}
+
+fn matches_part<E>(
+ element: &E,
+ parts: &[<E::Impl as SelectorImpl>::Identifier],
+ context: &mut MatchingContext<E::Impl>,
+) -> bool
+where
+ E: Element,
+{
+ let mut hosts = SmallVec::<[E; 4]>::new();
+
+ let mut host = match element.containing_shadow_host() {
+ Some(h) => h,
+ None => return false,
+ };
+
+ let current_host = context.current_host;
+ if current_host != Some(host.opaque()) {
+ loop {
+ let outer_host = host.containing_shadow_host();
+ if outer_host.as_ref().map(|h| h.opaque()) == current_host {
+ break;
+ }
+ let outer_host = match outer_host {
+ Some(h) => h,
+ None => return false,
+ };
+ // TODO(emilio): if worth it, we could early return if
+ // host doesn't have the exportparts attribute.
+ hosts.push(host);
+ host = outer_host;
+ }
+ }
+
+ // Translate the part into the right scope.
+ parts.iter().all(|part| {
+ let mut part = part.clone();
+ for host in hosts.iter().rev() {
+ part = match host.imported_part(&part) {
+ Some(p) => p,
+ None => return false,
+ };
+ }
+ element.is_part(&part)
+ })
+}
+
+fn matches_host<E>(
+ element: &E,
+ selector: Option<&Selector<E::Impl>>,
+ context: &mut MatchingContext<E::Impl>,
+ rightmost: SubjectOrPseudoElement,
+) -> bool
+where
+ E: Element,
+{
+ let host = match context.shadow_host() {
+ Some(h) => h,
+ None => return false,
+ };
+ if host != element.opaque() {
+ return false;
+ }
+ selector.map_or(true, |selector| {
+ context
+ .nest(|context| matches_complex_selector(selector.iter(), element, context, rightmost))
+ })
+}
+
+fn matches_slotted<E>(
+ element: &E,
+ selector: &Selector<E::Impl>,
+ context: &mut MatchingContext<E::Impl>,
+ rightmost: SubjectOrPseudoElement,
+) -> bool
+where
+ E: Element,
+{
+ // <slots> are never flattened tree slottables.
+ if element.is_html_slot_element() {
+ return false;
+ }
+ context.nest(|context| matches_complex_selector(selector.iter(), element, context, rightmost))
+}
+
+fn matches_rare_attribute_selector<E>(
+ element: &E,
+ attr_sel: &AttrSelectorWithOptionalNamespace<E::Impl>,
+) -> bool
+where
+ E: Element,
+{
+ let empty_string;
+ let namespace = match attr_sel.namespace() {
+ Some(ns) => ns,
+ None => {
+ empty_string = crate::parser::namespace_empty_string::<E::Impl>();
+ NamespaceConstraint::Specific(&empty_string)
+ },
+ };
+ element.attr_matches(
+ &namespace,
+ select_name(element, &attr_sel.local_name, &attr_sel.local_name_lower),
+ &match attr_sel.operation {
+ ParsedAttrSelectorOperation::Exists => AttrSelectorOperation::Exists,
+ ParsedAttrSelectorOperation::WithValue {
+ operator,
+ case_sensitivity,
+ ref value,
+ } => AttrSelectorOperation::WithValue {
+ operator,
+ case_sensitivity: to_unconditional_case_sensitivity(case_sensitivity, element),
+ value,
+ },
+ },
+ )
+}
+
+/// Determines whether the given element matches the given compound selector.
+#[inline]
+fn matches_compound_selector<E>(
+ selector_iter: &mut SelectorIter<E::Impl>,
+ element: &E,
+ context: &mut MatchingContext<E::Impl>,
+ rightmost: SubjectOrPseudoElement,
+) -> bool
+where
+ E: Element,
+{
+ let quirks_data = if context.quirks_mode() == QuirksMode::Quirks {
+ Some(selector_iter.clone())
+ } else {
+ None
+ };
+ let mut local_context = LocalMatchingContext {
+ shared: context,
+ rightmost,
+ quirks_data,
+ };
+ selector_iter.all(|simple| matches_simple_selector(simple, element, &mut local_context))
+}
+
+/// Determines whether the given element matches the given single selector.
+fn matches_simple_selector<E>(
+ selector: &Component<E::Impl>,
+ element: &E,
+ context: &mut LocalMatchingContext<E::Impl>,
+) -> bool
+where
+ E: Element,
+{
+ debug_assert!(context.shared.is_nested() || !context.shared.in_negation());
+ let rightmost = context.rightmost;
+ match *selector {
+ Component::ID(ref id) => {
+ element.has_id(id, context.shared.classes_and_ids_case_sensitivity())
+ },
+ Component::Class(ref class) => {
+ element.has_class(class, context.shared.classes_and_ids_case_sensitivity())
+ },
+ Component::LocalName(ref local_name) => matches_local_name(element, local_name),
+ Component::AttributeInNoNamespaceExists {
+ ref local_name,
+ ref local_name_lower,
+ } => element.has_attr_in_no_namespace(select_name(element, local_name, local_name_lower)),
+ Component::AttributeInNoNamespace {
+ ref local_name,
+ ref value,
+ operator,
+ case_sensitivity,
+ } => element.attr_matches(
+ &NamespaceConstraint::Specific(&crate::parser::namespace_empty_string::<E::Impl>()),
+ local_name,
+ &AttrSelectorOperation::WithValue {
+ operator,
+ case_sensitivity: to_unconditional_case_sensitivity(case_sensitivity, element),
+ value,
+ },
+ ),
+ Component::AttributeOther(ref attr_sel) => {
+ matches_rare_attribute_selector(element, attr_sel)
+ },
+ Component::Part(ref parts) => matches_part(element, parts, &mut context.shared),
+ Component::Slotted(ref selector) => {
+ matches_slotted(element, selector, &mut context.shared, rightmost)
+ },
+ Component::PseudoElement(ref pseudo) => {
+ element.match_pseudo_element(pseudo, context.shared)
+ },
+ Component::ExplicitUniversalType | Component::ExplicitAnyNamespace => true,
+ Component::Namespace(_, ref url) | Component::DefaultNamespace(ref url) => {
+ element.has_namespace(&url.borrow())
+ },
+ Component::ExplicitNoNamespace => {
+ let ns = crate::parser::namespace_empty_string::<E::Impl>();
+ element.has_namespace(&ns.borrow())
+ },
+ Component::NonTSPseudoClass(ref pc) => {
+ if let Some(ref iter) = context.quirks_data {
+ if pc.is_active_or_hover() &&
+ !element.is_link() &&
+ hover_and_active_quirk_applies(iter, context.shared, context.rightmost)
+ {
+ return false;
+ }
+ }
+ element.match_non_ts_pseudo_class(pc, &mut context.shared)
+ },
+ Component::Root => element.is_root(),
+ Component::Empty => {
+ if context.shared.needs_selector_flags() {
+ element.apply_selector_flags(ElementSelectorFlags::HAS_EMPTY_SELECTOR);
+ }
+ element.is_empty()
+ },
+ Component::Host(ref selector) => {
+ matches_host(element, selector.as_ref(), &mut context.shared, rightmost)
+ },
+ Component::ParentSelector | Component::Scope => match context.shared.scope_element {
+ Some(ref scope_element) => element.opaque() == *scope_element,
+ None => element.is_root(),
+ },
+ Component::Nth(ref nth_data) => {
+ matches_generic_nth_child(element, context.shared, nth_data, &[], rightmost)
+ },
+ Component::NthOf(ref nth_of_data) => context.shared.nest(|context| {
+ matches_generic_nth_child(
+ element,
+ context,
+ nth_of_data.nth_data(),
+ nth_of_data.selectors(),
+ rightmost,
+ )
+ }),
+ Component::Is(ref list) | Component::Where(ref list) => context.shared.nest(|context| {
+ matches_complex_selector_list(list.slice(), element, context, rightmost)
+ }),
+ Component::Negation(ref list) => context.shared.nest_for_negation(|context| {
+ !matches_complex_selector_list(list.slice(), element, context, rightmost)
+ }),
+ Component::Has(ref relative_selectors) => {
+ match_relative_selectors(relative_selectors, element, context.shared, rightmost)
+ },
+ Component::Combinator(_) => unsafe {
+ debug_unreachable!("Shouldn't try to selector-match combinators")
+ },
+ Component::RelativeSelectorAnchor => {
+ let anchor = context.shared.relative_selector_anchor();
+ // We may match inner relative selectors, in which case we want to always match.
+ anchor.map_or(true, |a| a == element.opaque())
+ },
+ Component::Invalid(..) => false,
+ }
+}
+
+#[inline(always)]
+pub fn select_name<'a, E: Element, T: PartialEq>(
+ element: &E,
+ local_name: &'a T,
+ local_name_lower: &'a T,
+) -> &'a T {
+ if local_name == local_name_lower || element.is_html_element_in_html_document() {
+ local_name_lower
+ } else {
+ local_name
+ }
+}
+
+#[inline(always)]
+pub fn to_unconditional_case_sensitivity<'a, E: Element>(
+ parsed: ParsedCaseSensitivity,
+ element: &E,
+) -> CaseSensitivity {
+ match parsed {
+ ParsedCaseSensitivity::CaseSensitive | ParsedCaseSensitivity::ExplicitCaseSensitive => {
+ CaseSensitivity::CaseSensitive
+ },
+ ParsedCaseSensitivity::AsciiCaseInsensitive => CaseSensitivity::AsciiCaseInsensitive,
+ ParsedCaseSensitivity::AsciiCaseInsensitiveIfInHtmlElementInHtmlDocument => {
+ if element.is_html_element_in_html_document() {
+ CaseSensitivity::AsciiCaseInsensitive
+ } else {
+ CaseSensitivity::CaseSensitive
+ }
+ },
+ }
+}
+
+fn matches_generic_nth_child<E>(
+ element: &E,
+ context: &mut MatchingContext<E::Impl>,
+ nth_data: &NthSelectorData,
+ selectors: &[Selector<E::Impl>],
+ rightmost: SubjectOrPseudoElement,
+) -> bool
+where
+ E: Element,
+{
+ if element.ignores_nth_child_selectors() {
+ return false;
+ }
+ let has_selectors = !selectors.is_empty();
+ let selectors_match =
+ !has_selectors || matches_complex_selector_list(selectors, element, context, rightmost);
+ if context.matching_for_invalidation() {
+ // Skip expensive indexing math in invalidation.
+ return selectors_match && !context.in_negation();
+ }
+
+ let NthSelectorData { ty, a, b, .. } = *nth_data;
+ let is_of_type = ty.is_of_type();
+ if ty.is_only() {
+ debug_assert!(
+ !has_selectors,
+ ":only-child and :only-of-type cannot have a selector list!"
+ );
+ return matches_generic_nth_child(
+ element,
+ context,
+ &NthSelectorData::first(is_of_type),
+ selectors,
+ rightmost,
+ ) && matches_generic_nth_child(
+ element,
+ context,
+ &NthSelectorData::last(is_of_type),
+ selectors,
+ rightmost,
+ );
+ }
+
+ let is_from_end = ty.is_from_end();
+
+ // It's useful to know whether this can only select the first/last element
+ // child for optimization purposes, see the `HAS_EDGE_CHILD_SELECTOR` flag.
+ let is_edge_child_selector = nth_data.is_simple_edge() && !has_selectors;
+
+ if context.needs_selector_flags() {
+ let mut flags = if is_edge_child_selector {
+ ElementSelectorFlags::HAS_EDGE_CHILD_SELECTOR
+ } else if is_from_end {
+ ElementSelectorFlags::HAS_SLOW_SELECTOR
+ } else {
+ ElementSelectorFlags::HAS_SLOW_SELECTOR_LATER_SIBLINGS
+ };
+ flags |= if has_selectors {
+ ElementSelectorFlags::HAS_SLOW_SELECTOR_NTH_OF
+ } else {
+ ElementSelectorFlags::HAS_SLOW_SELECTOR_NTH
+ };
+ element.apply_selector_flags(flags);
+ }
+
+ if !selectors_match {
+ return false;
+ }
+
+ // :first/last-child are rather trivial to match, don't bother with the
+ // cache.
+ if is_edge_child_selector {
+ return if is_from_end {
+ element.next_sibling_element()
+ } else {
+ element.prev_sibling_element()
+ }
+ .is_none();
+ }
+
+ // Lookup or compute the index.
+ let index = if let Some(i) = context
+ .nth_index_cache(is_of_type, is_from_end, selectors)
+ .lookup(element.opaque())
+ {
+ i
+ } else {
+ let i = nth_child_index(
+ element,
+ context,
+ selectors,
+ is_of_type,
+ is_from_end,
+ /* check_cache = */ true,
+ rightmost,
+ );
+ context
+ .nth_index_cache(is_of_type, is_from_end, selectors)
+ .insert(element.opaque(), i);
+ i
+ };
+ debug_assert_eq!(
+ index,
+ nth_child_index(
+ element,
+ context,
+ selectors,
+ is_of_type,
+ is_from_end,
+ /* check_cache = */ false,
+ rightmost,
+ ),
+ "invalid cache"
+ );
+
+ // Is there a non-negative integer n such that An+B=index?
+ match index.checked_sub(b) {
+ None => false,
+ Some(an) => match an.checked_div(a) {
+ Some(n) => n >= 0 && a * n == an,
+ None /* a == 0 */ => an == 0,
+ },
+ }
+}
+
+#[inline]
+fn nth_child_index<E>(
+ element: &E,
+ context: &mut MatchingContext<E::Impl>,
+ selectors: &[Selector<E::Impl>],
+ is_of_type: bool,
+ is_from_end: bool,
+ check_cache: bool,
+ rightmost: SubjectOrPseudoElement,
+) -> i32
+where
+ E: Element,
+{
+ // The traversal mostly processes siblings left to right. So when we walk
+ // siblings to the right when computing NthLast/NthLastOfType we're unlikely
+ // to get cache hits along the way. As such, we take the hit of walking the
+ // siblings to the left checking the cache in the is_from_end case (this
+ // matches what Gecko does). The indices-from-the-left is handled during the
+ // regular look further below.
+ if check_cache &&
+ is_from_end &&
+ !context
+ .nth_index_cache(is_of_type, is_from_end, selectors)
+ .is_empty()
+ {
+ let mut index: i32 = 1;
+ let mut curr = element.clone();
+ while let Some(e) = curr.prev_sibling_element() {
+ curr = e;
+ let matches = if is_of_type {
+ element.is_same_type(&curr)
+ } else if !selectors.is_empty() {
+ matches_complex_selector_list(selectors, &curr, context, rightmost)
+ } else {
+ true
+ };
+ if !matches {
+ continue;
+ }
+ if let Some(i) = context
+ .nth_index_cache(is_of_type, is_from_end, selectors)
+ .lookup(curr.opaque())
+ {
+ return i - index;
+ }
+ index += 1;
+ }
+ }
+
+ let mut index: i32 = 1;
+ let mut curr = element.clone();
+ let next = |e: E| {
+ if is_from_end {
+ e.next_sibling_element()
+ } else {
+ e.prev_sibling_element()
+ }
+ };
+ while let Some(e) = next(curr) {
+ curr = e;
+ let matches = if is_of_type {
+ element.is_same_type(&curr)
+ } else if !selectors.is_empty() {
+ matches_complex_selector_list(selectors, &curr, context, rightmost)
+ } else {
+ true
+ };
+ if !matches {
+ continue;
+ }
+ // If we're computing indices from the left, check each element in the
+ // cache. We handle the indices-from-the-right case at the top of this
+ // function.
+ if !is_from_end && check_cache {
+ if let Some(i) = context
+ .nth_index_cache(is_of_type, is_from_end, selectors)
+ .lookup(curr.opaque())
+ {
+ return i + index;
+ }
+ }
+ index += 1;
+ }
+
+ index
+}