Adding upstream version 86.0.1.upstream/86.0.1upstream

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

1 files changed, 1015 insertions, 0 deletions

diff --git a/servo/components/selectors/matching.rs b/servo/components/selectors/matching.rs
new file mode 100644
index 0000000000..244572b53b
--- /dev/null
+++ b/servo/components/selectors/matching.rs
@@ -0,0 +1,1015 @@
+/* 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, NamespaceConstraint, ParsedAttrSelectorOperation};
+use crate::bloom::{BloomFilter, BLOOM_HASH_MASK};
+use crate::nth_index_cache::NthIndexCacheInner;
+use crate::parser::{AncestorHashes, Combinator, Component, LocalName};
+use crate::parser::{NonTSPseudoClass, Selector, SelectorImpl, SelectorIter, SelectorList};
+use crate::tree::Element;
+use smallvec::SmallVec;
+use std::borrow::Borrow;
+use std::iter;
+
+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.
+    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;
+
+        /// 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 << 2;
+
+        /// 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 << 3;
+    }
+}
+
+impl ElementSelectorFlags {
+    /// Returns the subset of flags that apply to the element.
+    pub fn for_self(self) -> ElementSelectorFlags {
+        self & (ElementSelectorFlags::HAS_EMPTY_SELECTOR)
+    }
+
+    /// 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_EDGE_CHILD_SELECTOR)
+    }
+}
+
+/// Holds per-compound-selector data.
+struct LocalMatchingContext<'a, 'b: 'a, Impl: SelectorImpl> {
+    shared: &'a mut MatchingContext<'b, Impl>,
+    matches_hover_and_active_quirk: MatchesHoverAndActiveQuirk,
+}
+
+#[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.0 {
+        let matches = matches_selector(selector, 0, None, element, context, &mut |_, _| {});
+
+        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,
+}
+
+/// Whether the :hover and :active quirk applies.
+///
+/// https://quirks.spec.whatwg.org/#the-active-and-hover-quirk
+#[derive(Clone, Copy, Debug, PartialEq)]
+enum MatchesHoverAndActiveQuirk {
+    Yes,
+    No,
+}
+
+/// 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, F>(
+    selector: &Selector<E::Impl>,
+    offset: usize,
+    hashes: Option<&AncestorHashes>,
+    element: &E,
+    context: &mut MatchingContext<E::Impl>,
+    flags_setter: &mut F,
+) -> bool
+where
+    E: Element,
+    F: FnMut(&E, ElementSelectorFlags),
+{
+    // 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, flags_setter)
+}
+
+/// 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,
+        matches_hover_and_active_quirk: MatchesHoverAndActiveQuirk::No,
+    };
+
+    // 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, &mut |_, _| {}) {
+            return CompoundSelectorMatchingResult::NotMatched;
+        }
+    }
+
+    if from_offset != selector.len() {
+        return CompoundSelectorMatchingResult::Matched {
+            next_combinator_offset: from_offset,
+        };
+    }
+
+    CompoundSelectorMatchingResult::FullyMatched
+}
+
+/// Matches a complex selector.
+#[inline(always)]
+pub fn matches_complex_selector<E, F>(
+    mut iter: SelectorIter<E::Impl>,
+    element: &E,
+    context: &mut MatchingContext<E::Impl>,
+    flags_setter: &mut F,
+) -> bool
+where
+    E: Element,
+    F: FnMut(&E, ElementSelectorFlags),
+{
+    // 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;
+                    }
+                }
+            },
+            _ => {
+                debug_assert!(
+                    false,
+                    "Used MatchingMode::ForStatelessPseudoElement \
+                     in a non-pseudo selector"
+                );
+            },
+        }
+
+        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, flags_setter, Rightmost::Yes);
+
+    matches!(result, SelectorMatchingResult::Matched)
+}
+
+#[inline]
+fn matches_hover_and_active_quirk<Impl: SelectorImpl>(
+    selector_iter: &SelectorIter<Impl>,
+    context: &MatchingContext<Impl>,
+    rightmost: Rightmost,
+) -> MatchesHoverAndActiveQuirk {
+    if context.quirks_mode() != QuirksMode::Quirks {
+        return MatchesHoverAndActiveQuirk::No;
+    }
+
+    if context.is_nested() {
+        return MatchesHoverAndActiveQuirk::No;
+    }
+
+    // This compound selector had a pseudo-element to the right that we
+    // intentionally skipped.
+    if rightmost == Rightmost::Yes &&
+        context.matching_mode() == MatchingMode::ForStatelessPseudoElement
+    {
+        return MatchesHoverAndActiveQuirk::No;
+    }
+
+    let all_match = selector_iter.clone().all(|simple| match *simple {
+        Component::LocalName(_) |
+        Component::AttributeInNoNamespaceExists { .. } |
+        Component::AttributeInNoNamespace { .. } |
+        Component::AttributeOther(_) |
+        Component::ID(_) |
+        Component::Class(_) |
+        Component::PseudoElement(_) |
+        Component::Negation(_) |
+        Component::FirstChild |
+        Component::LastChild |
+        Component::OnlyChild |
+        Component::Empty |
+        Component::NthChild(_, _) |
+        Component::NthLastChild(_, _) |
+        Component::NthOfType(_, _) |
+        Component::NthLastOfType(_, _) |
+        Component::FirstOfType |
+        Component::LastOfType |
+        Component::OnlyOfType => false,
+        Component::NonTSPseudoClass(ref pseudo_class) => pseudo_class.is_active_or_hover(),
+        _ => true,
+    });
+
+    if all_match {
+        MatchesHoverAndActiveQuirk::Yes
+    } else {
+        MatchesHoverAndActiveQuirk::No
+    }
+}
+
+#[derive(Clone, Copy, PartialEq)]
+enum Rightmost {
+    Yes,
+    No,
+}
+
+#[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 => element.containing_shadow_host(),
+        Combinator::SlotAssignment => {
+            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)
+        },
+        Combinator::PseudoElement => element.pseudo_element_originating_element(),
+    }
+}
+
+fn matches_complex_selector_internal<E, F>(
+    mut selector_iter: SelectorIter<E::Impl>,
+    element: &E,
+    context: &mut MatchingContext<E::Impl>,
+    flags_setter: &mut F,
+    rightmost: Rightmost,
+) -> SelectorMatchingResult
+where
+    E: Element,
+    F: FnMut(&E, ElementSelectorFlags),
+{
+    debug!(
+        "Matching complex selector {:?} for {:?}",
+        selector_iter, element
+    );
+
+    let matches_compound_selector = matches_compound_selector(
+        &mut selector_iter,
+        element,
+        context,
+        flags_setter,
+        rightmost,
+    );
+
+    let combinator = selector_iter.next_sequence();
+    if combinator.map_or(false, |c| c.is_sibling()) {
+        flags_setter(
+            element,
+            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 = match combinator {
+        Combinator::NextSibling | Combinator::LaterSibling => {
+            SelectorMatchingResult::NotMatchedAndRestartFromClosestDescendant
+        },
+        Combinator::Child |
+        Combinator::Descendant |
+        Combinator::SlotAssignment |
+        Combinator::Part |
+        Combinator::PseudoElement => SelectorMatchingResult::NotMatchedGlobally,
+    };
+
+    let mut next_element =
+        next_element_for_combinator(element, combinator, &selector_iter, &context);
+
+    // 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 element.is_link() || combinator.is_sibling() {
+        VisitedHandlingMode::AllLinksUnvisited
+    } else {
+        context.visited_handling()
+    };
+
+    loop {
+        let element = match next_element {
+            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,
+                flags_setter,
+                Rightmost::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.
+            _ => {},
+        }
+
+        if element.is_link() {
+            visited_handling = VisitedHandlingMode::AllLinksUnvisited;
+        }
+
+        next_element = next_element_for_combinator(&element, combinator, &selector_iter, &context);
+    }
+}
+
+#[inline]
+fn matches_local_name<E>(element: &E, local_name: &LocalName<E::Impl>) -> bool
+where
+    E: Element,
+{
+    let name = select_name(
+        element.is_html_element_in_html_document(),
+        &local_name.name,
+        &local_name.lower_name,
+    )
+    .borrow();
+    element.has_local_name(name)
+}
+
+/// Determines whether the given element matches the given compound selector.
+#[inline]
+fn matches_compound_selector<E, F>(
+    selector_iter: &mut SelectorIter<E::Impl>,
+    element: &E,
+    context: &mut MatchingContext<E::Impl>,
+    flags_setter: &mut F,
+    rightmost: Rightmost,
+) -> bool
+where
+    E: Element,
+    F: FnMut(&E, ElementSelectorFlags),
+{
+    let matches_hover_and_active_quirk =
+        matches_hover_and_active_quirk(&selector_iter, context, rightmost);
+
+    // Handle some common cases first.
+    // We may want to get rid of this at some point if we can make the
+    // generic case fast enough.
+    let mut selector = selector_iter.next();
+    if let Some(&Component::LocalName(ref local_name)) = selector {
+        if !matches_local_name(element, local_name) {
+            return false;
+        }
+        selector = selector_iter.next();
+    }
+    let class_and_id_case_sensitivity = context.classes_and_ids_case_sensitivity();
+    if let Some(&Component::ID(ref id)) = selector {
+        if !element.has_id(id, class_and_id_case_sensitivity) {
+            return false;
+        }
+        selector = selector_iter.next();
+    }
+    while let Some(&Component::Class(ref class)) = selector {
+        if !element.has_class(class, class_and_id_case_sensitivity) {
+            return false;
+        }
+        selector = selector_iter.next();
+    }
+    let selector = match selector {
+        Some(s) => s,
+        None => return true,
+    };
+
+    let mut local_context = LocalMatchingContext {
+        shared: context,
+        matches_hover_and_active_quirk,
+    };
+    iter::once(selector)
+        .chain(selector_iter)
+        .all(|simple| matches_simple_selector(simple, element, &mut local_context, flags_setter))
+}
+
+/// Determines whether the given element matches the given single selector.
+fn matches_simple_selector<E, F>(
+    selector: &Component<E::Impl>,
+    element: &E,
+    context: &mut LocalMatchingContext<E::Impl>,
+    flags_setter: &mut F,
+) -> bool
+where
+    E: Element,
+    F: FnMut(&E, ElementSelectorFlags),
+{
+    debug_assert!(context.shared.is_nested() || !context.shared.in_negation());
+
+    match *selector {
+        Component::Combinator(_) => unreachable!(),
+        Component::Part(ref parts) => {
+            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.shared.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)
+            })
+        },
+        Component::Slotted(ref selector) => {
+            // <slots> are never flattened tree slottables.
+            !element.is_html_slot_element() &&
+                context.shared.nest(|context| {
+                    matches_complex_selector(selector.iter(), element, context, flags_setter)
+                })
+        },
+        Component::PseudoElement(ref pseudo) => {
+            element.match_pseudo_element(pseudo, context.shared)
+        },
+        Component::LocalName(ref local_name) => matches_local_name(element, local_name),
+        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::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::AttributeInNoNamespaceExists {
+            ref local_name,
+            ref local_name_lower,
+        } => {
+            let is_html = element.is_html_element_in_html_document();
+            element.attr_matches(
+                &NamespaceConstraint::Specific(&crate::parser::namespace_empty_string::<E::Impl>()),
+                select_name(is_html, local_name, local_name_lower),
+                &AttrSelectorOperation::Exists,
+            )
+        },
+        Component::AttributeInNoNamespace {
+            ref local_name,
+            ref value,
+            operator,
+            case_sensitivity,
+            never_matches,
+        } => {
+            if never_matches {
+                return false;
+            }
+            let is_html = element.is_html_element_in_html_document();
+            element.attr_matches(
+                &NamespaceConstraint::Specific(&crate::parser::namespace_empty_string::<E::Impl>()),
+                local_name,
+                &AttrSelectorOperation::WithValue {
+                    operator,
+                    case_sensitivity: case_sensitivity.to_unconditional(is_html),
+                    expected_value: value,
+                },
+            )
+        },
+        Component::AttributeOther(ref attr_sel) => {
+            if attr_sel.never_matches {
+                return false;
+            }
+            let is_html = element.is_html_element_in_html_document();
+            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(is_html, &attr_sel.local_name, &attr_sel.local_name_lower),
+                &match attr_sel.operation {
+                    ParsedAttrSelectorOperation::Exists => AttrSelectorOperation::Exists,
+                    ParsedAttrSelectorOperation::WithValue {
+                        operator,
+                        case_sensitivity,
+                        ref expected_value,
+                    } => AttrSelectorOperation::WithValue {
+                        operator,
+                        case_sensitivity: case_sensitivity.to_unconditional(is_html),
+                        expected_value,
+                    },
+                },
+            )
+        },
+        Component::NonTSPseudoClass(ref pc) => {
+            if context.matches_hover_and_active_quirk == MatchesHoverAndActiveQuirk::Yes &&
+                !context.shared.is_nested() &&
+                pc.is_active_or_hover() &&
+                !element.is_link()
+            {
+                return false;
+            }
+
+            element.match_non_ts_pseudo_class(pc, &mut context.shared, flags_setter)
+        },
+        Component::FirstChild => matches_first_child(element, flags_setter),
+        Component::LastChild => matches_last_child(element, flags_setter),
+        Component::OnlyChild => {
+            matches_first_child(element, flags_setter) && matches_last_child(element, flags_setter)
+        },
+        Component::Root => element.is_root(),
+        Component::Empty => {
+            flags_setter(element, ElementSelectorFlags::HAS_EMPTY_SELECTOR);
+            element.is_empty()
+        },
+        Component::Host(ref selector) => {
+            context
+                .shared
+                .shadow_host()
+                .map_or(false, |host| host == element.opaque()) &&
+                selector.as_ref().map_or(true, |selector| {
+                    context.shared.nest(|context| {
+                        matches_complex_selector(selector.iter(), element, context, flags_setter)
+                    })
+                })
+        },
+        Component::Scope => match context.shared.scope_element {
+            Some(ref scope_element) => element.opaque() == *scope_element,
+            None => element.is_root(),
+        },
+        Component::NthChild(a, b) => {
+            matches_generic_nth_child(element, context, a, b, false, false, flags_setter)
+        },
+        Component::NthLastChild(a, b) => {
+            matches_generic_nth_child(element, context, a, b, false, true, flags_setter)
+        },
+        Component::NthOfType(a, b) => {
+            matches_generic_nth_child(element, context, a, b, true, false, flags_setter)
+        },
+        Component::NthLastOfType(a, b) => {
+            matches_generic_nth_child(element, context, a, b, true, true, flags_setter)
+        },
+        Component::FirstOfType => {
+            matches_generic_nth_child(element, context, 0, 1, true, false, flags_setter)
+        },
+        Component::LastOfType => {
+            matches_generic_nth_child(element, context, 0, 1, true, true, flags_setter)
+        },
+        Component::OnlyOfType => {
+            matches_generic_nth_child(element, context, 0, 1, true, false, flags_setter) &&
+                matches_generic_nth_child(element, context, 0, 1, true, true, flags_setter)
+        },
+        Component::Is(ref list) | Component::Where(ref list) => context.shared.nest(|context| {
+            for selector in &**list {
+                if matches_complex_selector(selector.iter(), element, context, flags_setter) {
+                    return true;
+                }
+            }
+            false
+        }),
+        Component::Negation(ref list) => context.shared.nest_for_negation(|context| {
+            for selector in &**list {
+                if matches_complex_selector(selector.iter(), element, context, flags_setter) {
+                    return false;
+                }
+            }
+            true
+        }),
+    }
+}
+
+#[inline(always)]
+fn select_name<'a, T>(is_html: bool, local_name: &'a T, local_name_lower: &'a T) -> &'a T {
+    if is_html {
+        local_name_lower
+    } else {
+        local_name
+    }
+}
+
+#[inline]
+fn matches_generic_nth_child<E, F>(
+    element: &E,
+    context: &mut LocalMatchingContext<E::Impl>,
+    a: i32,
+    b: i32,
+    is_of_type: bool,
+    is_from_end: bool,
+    flags_setter: &mut F,
+) -> bool
+where
+    E: Element,
+    F: FnMut(&E, ElementSelectorFlags),
+{
+    if element.ignores_nth_child_selectors() {
+        return false;
+    }
+
+    flags_setter(
+        element,
+        if is_from_end {
+            ElementSelectorFlags::HAS_SLOW_SELECTOR
+        } else {
+            ElementSelectorFlags::HAS_SLOW_SELECTOR_LATER_SIBLINGS
+        },
+    );
+
+    // Grab a reference to the appropriate cache.
+    let mut cache = context
+        .shared
+        .nth_index_cache
+        .as_mut()
+        .map(|c| c.get(is_of_type, is_from_end));
+
+    // Lookup or compute the index.
+    let index = if let Some(i) = cache.as_mut().and_then(|c| c.lookup(element.opaque())) {
+        i
+    } else {
+        let i = nth_child_index(
+            element,
+            is_of_type,
+            is_from_end,
+            cache.as_deref_mut(),
+        );
+        if let Some(c) = cache.as_mut() {
+            c.insert(element.opaque(), i)
+        }
+        i
+    };
+    debug_assert_eq!(
+        index,
+        nth_child_index(element, is_of_type, is_from_end, None),
+        "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,
+    is_of_type: bool,
+    is_from_end: bool,
+    mut cache: Option<&mut NthIndexCacheInner>,
+) -> 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 let Some(ref mut c) = cache {
+        if is_from_end && !c.is_empty() {
+            let mut index: i32 = 1;
+            let mut curr = element.clone();
+            while let Some(e) = curr.prev_sibling_element() {
+                curr = e;
+                if !is_of_type || element.is_same_type(&curr) {
+                    if let Some(i) = c.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;
+        if !is_of_type || element.is_same_type(&curr) {
+            // 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 {
+                if let Some(i) = cache.as_mut().and_then(|c| c.lookup(curr.opaque())) {
+                    return i + index;
+                }
+            }
+            index += 1;
+        }
+    }
+
+    index
+}
+
+#[inline]
+fn matches_first_child<E, F>(element: &E, flags_setter: &mut F) -> bool
+where
+    E: Element,
+    F: FnMut(&E, ElementSelectorFlags),
+{
+    flags_setter(element, ElementSelectorFlags::HAS_EDGE_CHILD_SELECTOR);
+    element.prev_sibling_element().is_none()
+}
+
+#[inline]
+fn matches_last_child<E, F>(element: &E, flags_setter: &mut F) -> bool
+where
+    E: Element,
+    F: FnMut(&E, ElementSelectorFlags),
+{
+    flags_setter(element, ElementSelectorFlags::HAS_EDGE_CHILD_SELECTOR);
+    element.next_sibling_element().is_none()
+}