Adding upstream version 124.0.1.upstream/124.0.1

Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>

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
+}