diff options
Diffstat (limited to 'servo/components/selectors/matching.rs')
| -rw-r--r-- | servo/components/selectors/matching.rs | 1370 |
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 +} |