selectors/
matching.rs

1/* This Source Code Form is subject to the terms of the Mozilla Public
2 * License, v. 2.0. If a copy of the MPL was not distributed with this
3 * file, You can obtain one at https://mozilla.org/MPL/2.0/. */
4
5use crate::attr::{
6    AttrSelectorOperation, AttrSelectorWithOptionalNamespace, CaseSensitivity, NamespaceConstraint,
7    ParsedAttrSelectorOperation, ParsedCaseSensitivity,
8};
9use crate::bloom::{BloomFilter, BLOOM_HASH_MASK};
10use crate::kleene_value::KleeneValue;
11use crate::parser::{
12    AncestorHashes, Combinator, Component, LocalName, MatchesFeaturelessHost, NthSelectorData,
13    RelativeSelectorMatchHint,
14};
15use crate::parser::{
16    NonTSPseudoClass, RelativeSelector, Selector, SelectorImpl, SelectorIter, SelectorList,
17};
18use crate::relative_selector::cache::RelativeSelectorCachedMatch;
19use crate::tree::Element;
20use bitflags::bitflags;
21use debug_unreachable::debug_unreachable;
22use log::debug;
23use smallvec::SmallVec;
24use std::borrow::Borrow;
25
26pub use crate::context::*;
27
28// The bloom filter for descendant CSS selectors will have a <1% false
29// positive rate until it has this many selectors in it, then it will
30// rapidly increase.
31pub static RECOMMENDED_SELECTOR_BLOOM_FILTER_SIZE: usize = 4096;
32
33bitflags! {
34    /// Set of flags that are set on either the element or its parent (depending
35    /// on the flag) if the element could potentially match a selector.
36    #[derive(Clone, Copy)]
37    pub struct ElementSelectorFlags: usize {
38        /// When a child is added or removed from the parent, all the children
39        /// must be restyled, because they may match :nth-last-child,
40        /// :last-of-type, :nth-last-of-type, or :only-of-type.
41        const HAS_SLOW_SELECTOR = 1 << 0;
42
43        /// When a child is added or removed from the parent, any later
44        /// children must be restyled, because they may match :nth-child,
45        /// :first-of-type, or :nth-of-type.
46        const HAS_SLOW_SELECTOR_LATER_SIBLINGS = 1 << 1;
47
48        /// HAS_SLOW_SELECTOR* was set by the presence of :nth (But not of).
49        const HAS_SLOW_SELECTOR_NTH = 1 << 2;
50
51        /// When a DOM mutation occurs on a child that might be matched by
52        /// :nth-last-child(.. of <selector list>), earlier children must be
53        /// restyled, and HAS_SLOW_SELECTOR will be set (which normally
54        /// indicates that all children will be restyled).
55        ///
56        /// Similarly, when a DOM mutation occurs on a child that might be
57        /// matched by :nth-child(.. of <selector list>), later children must be
58        /// restyled, and HAS_SLOW_SELECTOR_LATER_SIBLINGS will be set.
59        const HAS_SLOW_SELECTOR_NTH_OF = 1 << 3;
60
61        /// When a child is added or removed from the parent, the first and
62        /// last children must be restyled, because they may match :first-child,
63        /// :last-child, or :only-child.
64        const HAS_EDGE_CHILD_SELECTOR = 1 << 4;
65
66        /// The element has an empty selector, so when a child is appended we
67        /// might need to restyle the parent completely.
68        const HAS_EMPTY_SELECTOR = 1 << 5;
69
70        /// The element may anchor a relative selector.
71        const ANCHORS_RELATIVE_SELECTOR = 1 << 6;
72
73        /// The element may anchor a relative selector that is not the subject
74        /// of the whole selector.
75        const ANCHORS_RELATIVE_SELECTOR_NON_SUBJECT = 1 << 7;
76
77        /// The element is reached by a relative selector search in the sibling direction.
78        const RELATIVE_SELECTOR_SEARCH_DIRECTION_SIBLING = 1 << 8;
79
80        /// The element is reached by a relative selector search in the ancestor direction.
81        const RELATIVE_SELECTOR_SEARCH_DIRECTION_ANCESTOR = 1 << 9;
82
83        // The element is reached by a relative selector search in both sibling and ancestor directions.
84        const RELATIVE_SELECTOR_SEARCH_DIRECTION_ANCESTOR_SIBLING =
85            Self::RELATIVE_SELECTOR_SEARCH_DIRECTION_SIBLING.bits() |
86            Self::RELATIVE_SELECTOR_SEARCH_DIRECTION_ANCESTOR.bits();
87    }
88}
89
90impl ElementSelectorFlags {
91    /// Returns the subset of flags that apply to the element.
92    pub fn for_self(self) -> ElementSelectorFlags {
93        self & (ElementSelectorFlags::HAS_EMPTY_SELECTOR
94            | ElementSelectorFlags::ANCHORS_RELATIVE_SELECTOR
95            | ElementSelectorFlags::ANCHORS_RELATIVE_SELECTOR_NON_SUBJECT
96            | ElementSelectorFlags::RELATIVE_SELECTOR_SEARCH_DIRECTION_SIBLING
97            | ElementSelectorFlags::RELATIVE_SELECTOR_SEARCH_DIRECTION_ANCESTOR)
98    }
99
100    /// Returns the subset of flags that apply to the parent.
101    pub fn for_parent(self) -> ElementSelectorFlags {
102        self & (ElementSelectorFlags::HAS_SLOW_SELECTOR
103            | ElementSelectorFlags::HAS_SLOW_SELECTOR_LATER_SIBLINGS
104            | ElementSelectorFlags::HAS_SLOW_SELECTOR_NTH
105            | ElementSelectorFlags::HAS_SLOW_SELECTOR_NTH_OF
106            | ElementSelectorFlags::HAS_EDGE_CHILD_SELECTOR)
107    }
108}
109
110/// Holds per-compound-selector data.
111struct LocalMatchingContext<'a, 'b: 'a, Impl: SelectorImpl> {
112    shared: &'a mut MatchingContext<'b, Impl>,
113    rightmost: SubjectOrPseudoElement,
114    quirks_data: Option<SelectorIter<'a, Impl>>,
115}
116
117#[inline(always)]
118pub fn matches_selector_list<E>(
119    selector_list: &SelectorList<E::Impl>,
120    element: &E,
121    context: &mut MatchingContext<E::Impl>,
122) -> bool
123where
124    E: Element,
125{
126    // This is pretty much any(..) but manually inlined because the compiler
127    // refuses to do so from querySelector / querySelectorAll.
128    for selector in selector_list.slice() {
129        let matches = matches_selector(selector, 0, None, element, context);
130        if matches {
131            return true;
132        }
133    }
134
135    false
136}
137
138/// Given the ancestor hashes from a selector, see if the current element,
139/// represented by the bloom filter, has a chance of matching at all.
140#[inline(always)]
141pub fn selector_may_match(hashes: &AncestorHashes, bf: &BloomFilter) -> bool {
142    // Check the first three hashes. Note that we can check for zero before
143    // masking off the high bits, since if any of the first three hashes is
144    // zero the fourth will be as well. We also take care to avoid the
145    // special-case complexity of the fourth hash until we actually reach it,
146    // because we usually don't.
147    //
148    // To be clear: this is all extremely hot.
149    for i in 0..3 {
150        let packed = hashes.packed_hashes[i];
151        if packed == 0 {
152            // No more hashes left - unable to fast-reject.
153            return true;
154        }
155
156        if !bf.might_contain_hash(packed & BLOOM_HASH_MASK) {
157            // Hooray! We fast-rejected on this hash.
158            return false;
159        }
160    }
161
162    // Now do the slighty-more-complex work of synthesizing the fourth hash,
163    // and check it against the filter if it exists.
164    let fourth = hashes.fourth_hash();
165    fourth == 0 || bf.might_contain_hash(fourth)
166}
167
168/// A result of selector matching, includes 3 failure types,
169///
170///   NotMatchedAndRestartFromClosestLaterSibling
171///   NotMatchedAndRestartFromClosestDescendant
172///   NotMatchedGlobally
173///
174/// When NotMatchedGlobally appears, stop selector matching completely since
175/// the succeeding selectors never matches.
176/// It is raised when
177///   Child combinator cannot find the candidate element.
178///   Descendant combinator cannot find the candidate element.
179///
180/// When NotMatchedAndRestartFromClosestDescendant appears, the selector
181/// matching does backtracking and restarts from the closest Descendant
182/// combinator.
183/// It is raised when
184///   NextSibling combinator cannot find the candidate element.
185///   LaterSibling combinator cannot find the candidate element.
186///   Child combinator doesn't match on the found element.
187///
188/// When NotMatchedAndRestartFromClosestLaterSibling appears, the selector
189/// matching does backtracking and restarts from the closest LaterSibling
190/// combinator.
191/// It is raised when
192///   NextSibling combinator doesn't match on the found element.
193///
194/// For example, when the selector "d1 d2 a" is provided and we cannot *find*
195/// an appropriate ancestor element for "d1", this selector matching raises
196/// NotMatchedGlobally since even if "d2" is moved to more upper element, the
197/// candidates for "d1" becomes less than before and d1 .
198///
199/// The next example is siblings. When the selector "b1 + b2 ~ d1 a" is
200/// provided and we cannot *find* an appropriate brother element for b1,
201/// the selector matching raises NotMatchedAndRestartFromClosestDescendant.
202/// The selectors ("b1 + b2 ~") doesn't match and matching restart from "d1".
203///
204/// The additional example is child and sibling. When the selector
205/// "b1 + c1 > b2 ~ d1 a" is provided and the selector "b1" doesn't match on
206/// the element, this "b1" raises NotMatchedAndRestartFromClosestLaterSibling.
207/// However since the selector "c1" raises
208/// NotMatchedAndRestartFromClosestDescendant. So the selector
209/// "b1 + c1 > b2 ~ " doesn't match and restart matching from "d1".
210///
211/// There is also the unknown result, which is used during invalidation when
212/// specific selector is being tested for before/after comparison. More specifically,
213/// selectors that are too expensive to correctly compute during invalidation may
214/// return unknown, as the computation will be thrown away and only to be recomputed
215/// during styling. For most cases, the unknown result can be treated as matching.
216/// This is because a compound of selectors acts like &&, and unknown && matched
217/// == matched and unknown && not-matched == not-matched. However, some selectors,
218/// like `:is()`, behave like || i.e. `:is(.a, .b)` == a || b. Treating unknown
219/// == matching then causes these selectors to always return matching, which undesired
220/// for before/after comparison. Coercing to not-matched doesn't work since each
221/// inner selector may have compounds: e.g. Toggling `.foo` in `:is(.foo:has(..))`
222/// with coersion to not-matched would result in an invalid before/after comparison
223/// of not-matched/not-matched.
224#[derive(Clone, Copy, Eq, PartialEq)]
225enum SelectorMatchingResult {
226    Matched,
227    NotMatchedAndRestartFromClosestLaterSibling,
228    NotMatchedAndRestartFromClosestDescendant,
229    NotMatchedGlobally,
230    Unknown,
231}
232
233impl From<SelectorMatchingResult> for KleeneValue {
234    #[inline]
235    fn from(value: SelectorMatchingResult) -> Self {
236        match value {
237            SelectorMatchingResult::Matched => KleeneValue::True,
238            SelectorMatchingResult::Unknown => KleeneValue::Unknown,
239            SelectorMatchingResult::NotMatchedAndRestartFromClosestLaterSibling
240            | SelectorMatchingResult::NotMatchedAndRestartFromClosestDescendant
241            | SelectorMatchingResult::NotMatchedGlobally => KleeneValue::False,
242        }
243    }
244}
245
246/// Matches a selector, fast-rejecting against a bloom filter.
247///
248/// We accept an offset to allow consumers to represent and match against
249/// partial selectors (indexed from the right). We use this API design, rather
250/// than having the callers pass a SelectorIter, because creating a SelectorIter
251/// requires dereferencing the selector to get the length, which adds an
252/// unnecessary cache miss for cases when we can fast-reject with AncestorHashes
253/// (which the caller can store inline with the selector pointer).
254#[inline(always)]
255pub fn matches_selector<E>(
256    selector: &Selector<E::Impl>,
257    offset: usize,
258    hashes: Option<&AncestorHashes>,
259    element: &E,
260    context: &mut MatchingContext<E::Impl>,
261) -> bool
262where
263    E: Element,
264{
265    let result = matches_selector_kleene(selector, offset, hashes, element, context);
266    if cfg!(debug_assertions) && result == KleeneValue::Unknown {
267        debug_assert!(
268            context
269                .matching_for_invalidation_comparison()
270                .unwrap_or(false),
271            "How did we return unknown?"
272        );
273    }
274    result.to_bool(true)
275}
276
277/// Same as matches_selector, but returns the Kleene value as-is.
278#[inline(always)]
279pub fn matches_selector_kleene<E>(
280    selector: &Selector<E::Impl>,
281    offset: usize,
282    hashes: Option<&AncestorHashes>,
283    element: &E,
284    context: &mut MatchingContext<E::Impl>,
285) -> KleeneValue
286where
287    E: Element,
288{
289    // Use the bloom filter to fast-reject.
290    if let Some(hashes) = hashes {
291        if let Some(filter) = context.bloom_filter {
292            if !selector_may_match(hashes, filter) {
293                return KleeneValue::False;
294            }
295        }
296    }
297    matches_complex_selector(
298        selector.iter_from(offset),
299        element,
300        context,
301        if selector.is_rightmost(offset) {
302            SubjectOrPseudoElement::Yes
303        } else {
304            SubjectOrPseudoElement::No
305        },
306    )
307}
308
309/// Whether a compound selector matched, and whether it was the rightmost
310/// selector inside the complex selector.
311pub enum CompoundSelectorMatchingResult {
312    /// The selector was fully matched.
313    FullyMatched,
314    /// The compound selector matched, and the next combinator offset is
315    /// `next_combinator_offset`.
316    Matched { next_combinator_offset: usize },
317    /// The selector didn't match.
318    NotMatched,
319}
320
321/// Matches a compound selector belonging to `selector`, starting at offset
322/// `from_offset`, matching left to right.
323///
324/// Requires that `from_offset` points to a `Combinator`.
325///
326/// NOTE(emilio): This doesn't allow to match in the leftmost sequence of the
327/// complex selector, but it happens to be the case we don't need it.
328pub fn matches_compound_selector_from<E>(
329    selector: &Selector<E::Impl>,
330    mut from_offset: usize,
331    context: &mut MatchingContext<E::Impl>,
332    element: &E,
333) -> CompoundSelectorMatchingResult
334where
335    E: Element,
336{
337    debug_assert!(
338        !context
339            .matching_for_invalidation_comparison()
340            .unwrap_or(false),
341        "CompoundSelectorMatchingResult doesn't support unknown"
342    );
343    if cfg!(debug_assertions) && from_offset != 0 {
344        selector.combinator_at_parse_order(from_offset - 1); // This asserts.
345    }
346
347    let mut local_context = LocalMatchingContext {
348        shared: context,
349        // We have no info if this is an outer selector. This function is called in
350        // an invalidation context, which only calls this for non-subject (i.e.
351        // Non-rightmost) positions.
352        rightmost: SubjectOrPseudoElement::No,
353        quirks_data: None,
354    };
355
356    // Find the end of the selector or the next combinator, then match
357    // backwards, so that we match in the same order as
358    // matches_complex_selector, which is usually faster.
359    let start_offset = from_offset;
360    for component in selector.iter_raw_parse_order_from(from_offset) {
361        if matches!(*component, Component::Combinator(..)) {
362            debug_assert_ne!(from_offset, 0, "Selector started with a combinator?");
363            break;
364        }
365
366        from_offset += 1;
367    }
368
369    debug_assert!(from_offset >= 1);
370    debug_assert!(from_offset <= selector.len());
371
372    let iter = selector.iter_from(selector.len() - from_offset);
373    debug_assert!(
374        iter.clone().next().is_some() || from_offset != selector.len(),
375        "Got the math wrong: {:?} | {:?} | {} {}",
376        selector,
377        selector.iter_raw_match_order().as_slice(),
378        from_offset,
379        start_offset
380    );
381
382    debug_assert!(
383        !local_context.shared.featureless(),
384        "Invalidating featureless element somehow?"
385    );
386
387    for component in iter {
388        let result = matches_simple_selector(component, element, &mut local_context);
389        debug_assert!(
390            result != KleeneValue::Unknown,
391            "Returned unknown in non invalidation context?"
392        );
393        if !result.to_bool(true) {
394            return CompoundSelectorMatchingResult::NotMatched;
395        }
396    }
397
398    if from_offset != selector.len() {
399        return CompoundSelectorMatchingResult::Matched {
400            next_combinator_offset: from_offset,
401        };
402    }
403
404    CompoundSelectorMatchingResult::FullyMatched
405}
406
407/// Matches a complex selector.
408#[inline(always)]
409fn matches_complex_selector<E>(
410    mut iter: SelectorIter<E::Impl>,
411    element: &E,
412    context: &mut MatchingContext<E::Impl>,
413    rightmost: SubjectOrPseudoElement,
414) -> KleeneValue
415where
416    E: Element,
417{
418    // If this is the special pseudo-element mode, consume the ::pseudo-element
419    // before proceeding, since the caller has already handled that part.
420    if context.matching_mode() == MatchingMode::ForStatelessPseudoElement && !context.is_nested() {
421        // Consume the pseudo.
422        match *iter.next().unwrap() {
423            Component::PseudoElement(ref pseudo) => {
424                if let Some(ref f) = context.pseudo_element_matching_fn {
425                    if !f(pseudo) {
426                        return KleeneValue::False;
427                    }
428                }
429            },
430            ref other => {
431                debug_assert!(
432                    false,
433                    "Used MatchingMode::ForStatelessPseudoElement \
434                     in a non-pseudo selector {:?}",
435                    other
436                );
437                return KleeneValue::False;
438            },
439        }
440
441        if !iter.matches_for_stateless_pseudo_element() {
442            return KleeneValue::False;
443        }
444
445        // Advance to the non-pseudo-element part of the selector.
446        let next_sequence = iter.next_sequence().unwrap();
447        debug_assert_eq!(next_sequence, Combinator::PseudoElement);
448    }
449
450    matches_complex_selector_internal(
451        iter,
452        element,
453        context,
454        rightmost,
455        SubjectOrPseudoElement::Yes,
456    )
457    .into()
458}
459
460/// Matches each selector of a list as a complex selector
461fn matches_complex_selector_list<E: Element>(
462    list: &[Selector<E::Impl>],
463    element: &E,
464    context: &mut MatchingContext<E::Impl>,
465    rightmost: SubjectOrPseudoElement,
466) -> KleeneValue {
467    KleeneValue::any(list.iter(), |selector| {
468        matches_complex_selector(selector.iter(), element, context, rightmost)
469    })
470}
471
472fn matches_relative_selector<E: Element>(
473    relative_selector: &RelativeSelector<E::Impl>,
474    element: &E,
475    context: &mut MatchingContext<E::Impl>,
476    rightmost: SubjectOrPseudoElement,
477) -> bool {
478    // Overall, we want to mark the path that we've traversed so that when an element
479    // is invalidated, we early-reject unnecessary relative selector invalidations.
480    if relative_selector.match_hint.is_descendant_direction() {
481        if context.needs_selector_flags() {
482            element.apply_selector_flags(
483                ElementSelectorFlags::RELATIVE_SELECTOR_SEARCH_DIRECTION_ANCESTOR,
484            );
485        }
486        let mut next_element = element.first_element_child();
487        while let Some(el) = next_element {
488            if context.needs_selector_flags() {
489                el.apply_selector_flags(
490                    ElementSelectorFlags::RELATIVE_SELECTOR_SEARCH_DIRECTION_ANCESTOR,
491                );
492            }
493            let mut matched = matches_complex_selector(
494                relative_selector.selector.iter(),
495                &el,
496                context,
497                rightmost,
498            )
499            .to_bool(true);
500            if !matched && relative_selector.match_hint.is_subtree() {
501                matched = matches_relative_selector_subtree(
502                    &relative_selector.selector,
503                    &el,
504                    context,
505                    rightmost,
506                );
507            }
508            if matched {
509                return true;
510            }
511            next_element = el.next_sibling_element();
512        }
513    } else {
514        debug_assert!(
515            matches!(
516                relative_selector.match_hint,
517                RelativeSelectorMatchHint::InNextSibling
518                    | RelativeSelectorMatchHint::InNextSiblingSubtree
519                    | RelativeSelectorMatchHint::InSibling
520                    | RelativeSelectorMatchHint::InSiblingSubtree
521            ),
522            "Not descendant direction, but also not sibling direction?"
523        );
524        if context.needs_selector_flags() {
525            element.apply_selector_flags(
526                ElementSelectorFlags::RELATIVE_SELECTOR_SEARCH_DIRECTION_SIBLING,
527            );
528        }
529        let sibling_flag = if relative_selector.match_hint.is_subtree() {
530            ElementSelectorFlags::RELATIVE_SELECTOR_SEARCH_DIRECTION_ANCESTOR_SIBLING
531        } else {
532            ElementSelectorFlags::RELATIVE_SELECTOR_SEARCH_DIRECTION_SIBLING
533        };
534        let mut next_element = element.next_sibling_element();
535        while let Some(el) = next_element {
536            if context.needs_selector_flags() {
537                el.apply_selector_flags(sibling_flag);
538            }
539            let matched = if relative_selector.match_hint.is_subtree() {
540                matches_relative_selector_subtree(
541                    &relative_selector.selector,
542                    &el,
543                    context,
544                    rightmost,
545                )
546            } else {
547                matches_complex_selector(relative_selector.selector.iter(), &el, context, rightmost)
548                    .to_bool(true)
549            };
550            if matched {
551                return true;
552            }
553            if relative_selector.match_hint.is_next_sibling() {
554                break;
555            }
556            next_element = el.next_sibling_element();
557        }
558    }
559    return false;
560}
561
562fn relative_selector_match_early<E: Element>(
563    selector: &RelativeSelector<E::Impl>,
564    element: &E,
565    context: &mut MatchingContext<E::Impl>,
566) -> Option<bool> {
567    // See if we can return a cached result.
568    if let Some(cached) = context
569        .selector_caches
570        .relative_selector
571        .lookup(element.opaque(), selector)
572    {
573        return Some(cached.matched());
574    }
575    // See if we can fast-reject.
576    if context
577        .selector_caches
578        .relative_selector_filter_map
579        .fast_reject(element, selector, context.quirks_mode())
580    {
581        // Alright, add as unmatched to cache.
582        context.selector_caches.relative_selector.add(
583            element.opaque(),
584            selector,
585            RelativeSelectorCachedMatch::NotMatched,
586        );
587        return Some(false);
588    }
589    None
590}
591
592fn match_relative_selectors<E: Element>(
593    selectors: &[RelativeSelector<E::Impl>],
594    element: &E,
595    context: &mut MatchingContext<E::Impl>,
596    rightmost: SubjectOrPseudoElement,
597) -> KleeneValue {
598    if context.relative_selector_anchor().is_some() {
599        // FIXME(emilio): This currently can happen with nesting, and it's not fully
600        // correct, arguably. But the ideal solution isn't super-clear either. For now,
601        // cope with it and explicitly reject it at match time. See [1] for discussion.
602        //
603        // [1]: https://github.com/w3c/csswg-drafts/issues/9600
604        return KleeneValue::False;
605    }
606    if let Some(may_return_unknown) = context.matching_for_invalidation_comparison() {
607        // In the context of invalidation, :has is expensive, especially because we
608        // can't use caching/filtering due to now/then matches. DOM structure also
609        // may have changed.
610        return if may_return_unknown {
611            KleeneValue::Unknown
612        } else {
613            KleeneValue::from(!context.in_negation())
614        };
615    }
616    context
617        .nest_for_relative_selector(element.opaque(), |context| {
618            do_match_relative_selectors(selectors, element, context, rightmost)
619        })
620        .into()
621}
622
623/// Matches a relative selector in a list of relative selectors.
624fn do_match_relative_selectors<E: Element>(
625    selectors: &[RelativeSelector<E::Impl>],
626    element: &E,
627    context: &mut MatchingContext<E::Impl>,
628    rightmost: SubjectOrPseudoElement,
629) -> bool {
630    // Due to style sharing implications (See style sharing code), we mark the current styling context
631    // to mark elements considered for :has matching. Additionally, we want to mark the elements themselves,
632    // since we don't want to indiscriminately invalidate every element as a potential anchor.
633    if rightmost == SubjectOrPseudoElement::Yes {
634        if context.needs_selector_flags() {
635            element.apply_selector_flags(ElementSelectorFlags::ANCHORS_RELATIVE_SELECTOR);
636        }
637    } else {
638        if context.needs_selector_flags() {
639            element
640                .apply_selector_flags(ElementSelectorFlags::ANCHORS_RELATIVE_SELECTOR_NON_SUBJECT);
641        }
642    }
643
644    for relative_selector in selectors.iter() {
645        if let Some(result) = relative_selector_match_early(relative_selector, element, context) {
646            if result {
647                return true;
648            }
649            // Early return indicates no match, continue to next selector.
650            continue;
651        }
652
653        let matched = matches_relative_selector(relative_selector, element, context, rightmost);
654        context.selector_caches.relative_selector.add(
655            element.opaque(),
656            relative_selector,
657            if matched {
658                RelativeSelectorCachedMatch::Matched
659            } else {
660                RelativeSelectorCachedMatch::NotMatched
661            },
662        );
663        if matched {
664            return true;
665        }
666    }
667
668    false
669}
670
671fn matches_relative_selector_subtree<E: Element>(
672    selector: &Selector<E::Impl>,
673    element: &E,
674    context: &mut MatchingContext<E::Impl>,
675    rightmost: SubjectOrPseudoElement,
676) -> bool {
677    let mut current = element.first_element_child();
678
679    while let Some(el) = current {
680        if context.needs_selector_flags() {
681            el.apply_selector_flags(
682                ElementSelectorFlags::RELATIVE_SELECTOR_SEARCH_DIRECTION_ANCESTOR,
683            );
684        }
685        if matches_complex_selector(selector.iter(), &el, context, rightmost).to_bool(true) {
686            return true;
687        }
688
689        if matches_relative_selector_subtree(selector, &el, context, rightmost) {
690            return true;
691        }
692
693        current = el.next_sibling_element();
694    }
695
696    false
697}
698
699/// Whether the :hover and :active quirk applies.
700///
701/// https://quirks.spec.whatwg.org/#the-active-and-hover-quirk
702fn hover_and_active_quirk_applies<Impl: SelectorImpl>(
703    selector_iter: &SelectorIter<Impl>,
704    context: &MatchingContext<Impl>,
705    rightmost: SubjectOrPseudoElement,
706) -> bool {
707    debug_assert_eq!(context.quirks_mode(), QuirksMode::Quirks);
708
709    if context.is_nested() {
710        return false;
711    }
712
713    // This compound selector had a pseudo-element to the right that we
714    // intentionally skipped.
715    if rightmost == SubjectOrPseudoElement::Yes
716        && context.matching_mode() == MatchingMode::ForStatelessPseudoElement
717    {
718        return false;
719    }
720
721    selector_iter.clone().all(|simple| match *simple {
722        Component::NonTSPseudoClass(ref pseudo_class) => pseudo_class.is_active_or_hover(),
723        _ => false,
724    })
725}
726
727#[derive(Clone, Copy, PartialEq)]
728enum SubjectOrPseudoElement {
729    Yes,
730    No,
731}
732
733fn host_for_part<E>(element: &E, context: &MatchingContext<E::Impl>) -> Option<E>
734where
735    E: Element,
736{
737    let scope = context.current_host;
738    let mut curr = element.containing_shadow_host()?;
739    if scope == Some(curr.opaque()) {
740        return Some(curr);
741    }
742    loop {
743        let parent = curr.containing_shadow_host();
744        if parent.as_ref().map(|h| h.opaque()) == scope {
745            return Some(curr);
746        }
747        curr = parent?;
748    }
749}
750
751fn assigned_slot<E>(element: &E, context: &MatchingContext<E::Impl>) -> Option<E>
752where
753    E: Element,
754{
755    debug_assert!(element
756        .assigned_slot()
757        .map_or(true, |s| s.is_html_slot_element()));
758    let scope = context.current_host?;
759    let mut current_slot = element.assigned_slot()?;
760    while current_slot.containing_shadow_host().unwrap().opaque() != scope {
761        current_slot = current_slot.assigned_slot()?;
762    }
763    Some(current_slot)
764}
765
766struct NextElement<E> {
767    next_element: Option<E>,
768    featureless: bool,
769}
770
771impl<E> NextElement<E> {
772    #[inline(always)]
773    fn new(next_element: Option<E>, featureless: bool) -> Self {
774        Self {
775            next_element,
776            featureless,
777        }
778    }
779}
780
781#[inline(always)]
782fn next_element_for_combinator<E>(
783    element: &E,
784    combinator: Combinator,
785    context: &MatchingContext<E::Impl>,
786) -> NextElement<E>
787where
788    E: Element,
789{
790    match combinator {
791        Combinator::NextSibling | Combinator::LaterSibling => {
792            NextElement::new(element.prev_sibling_element(), false)
793        },
794        Combinator::Child | Combinator::Descendant => {
795            if let Some(parent) = element.parent_element() {
796                return NextElement::new(Some(parent), false);
797            }
798
799            let element = if element.parent_node_is_shadow_root() {
800                element.containing_shadow_host()
801            } else {
802                None
803            };
804            NextElement::new(element, true)
805        },
806        Combinator::Part => NextElement::new(host_for_part(element, context), false),
807        Combinator::SlotAssignment => NextElement::new(assigned_slot(element, context), false),
808        Combinator::PseudoElement => {
809            NextElement::new(element.pseudo_element_originating_element(), false)
810        },
811    }
812}
813
814fn matches_complex_selector_internal<E>(
815    mut selector_iter: SelectorIter<E::Impl>,
816    element: &E,
817    context: &mut MatchingContext<E::Impl>,
818    mut rightmost: SubjectOrPseudoElement,
819    mut first_subject_compound: SubjectOrPseudoElement,
820) -> SelectorMatchingResult
821where
822    E: Element,
823{
824    debug!(
825        "Matching complex selector {:?} for {:?}",
826        selector_iter, element
827    );
828
829    let matches_compound_selector = {
830        let result = matches_compound_selector(&mut selector_iter, element, context, rightmost);
831        // We only care for unknown match in the first subject in compound - in the context of comparison
832        // invalidation, ancestors/previous sibling being an unknown match doesn't matter - we must
833        // invalidate to guarantee correctness.
834        if result == KleeneValue::Unknown && first_subject_compound == SubjectOrPseudoElement::No {
835            debug_assert!(
836                context
837                    .matching_for_invalidation_comparison()
838                    .unwrap_or(false),
839                "How did we return unknown?"
840            );
841            // Coerce the result to matched.
842            KleeneValue::from(!context.in_negation())
843        } else {
844            result
845        }
846    };
847
848    let Some(combinator) = selector_iter.next_sequence() else {
849        return match matches_compound_selector {
850            KleeneValue::True => SelectorMatchingResult::Matched,
851            KleeneValue::Unknown => SelectorMatchingResult::Unknown,
852            KleeneValue::False => {
853                SelectorMatchingResult::NotMatchedAndRestartFromClosestLaterSibling
854            },
855        };
856    };
857
858    let is_pseudo_combinator = combinator.is_pseudo_element();
859    if context.featureless() && !is_pseudo_combinator {
860        // A featureless element shouldn't match any further combinator.
861        // TODO(emilio): Maybe we could avoid the compound matching more eagerly.
862        return SelectorMatchingResult::NotMatchedGlobally;
863    }
864
865    let is_sibling_combinator = combinator.is_sibling();
866    if is_sibling_combinator && context.needs_selector_flags() {
867        // We need the flags even if we don't match.
868        element.apply_selector_flags(ElementSelectorFlags::HAS_SLOW_SELECTOR_LATER_SIBLINGS);
869    }
870
871    if matches_compound_selector == KleeneValue::False {
872        // We don't short circuit unknown here, since the rest of the selector
873        // to the left of this compound may still return false.
874        return SelectorMatchingResult::NotMatchedAndRestartFromClosestLaterSibling;
875    }
876
877    if !is_pseudo_combinator {
878        rightmost = SubjectOrPseudoElement::No;
879        first_subject_compound = SubjectOrPseudoElement::No;
880    }
881
882    // Stop matching :visited as soon as we find a link, or a combinator for
883    // something that isn't an ancestor.
884    let mut visited_handling = if is_sibling_combinator {
885        VisitedHandlingMode::AllLinksUnvisited
886    } else {
887        context.visited_handling()
888    };
889
890    let candidate_not_found = if is_sibling_combinator {
891        SelectorMatchingResult::NotMatchedAndRestartFromClosestDescendant
892    } else {
893        SelectorMatchingResult::NotMatchedGlobally
894    };
895
896    let mut element = element.clone();
897    loop {
898        if element.is_link() {
899            visited_handling = VisitedHandlingMode::AllLinksUnvisited;
900        }
901
902        let NextElement {
903            next_element,
904            featureless,
905        } = next_element_for_combinator(&element, combinator, &context);
906        element = match next_element {
907            None => return candidate_not_found,
908            Some(e) => e,
909        };
910
911        let result = context.with_visited_handling_mode(visited_handling, |context| {
912            context.with_featureless(featureless, |context| {
913                matches_complex_selector_internal(
914                    selector_iter.clone(),
915                    &element,
916                    context,
917                    rightmost,
918                    first_subject_compound,
919                )
920            })
921        });
922
923        // Return the status immediately if it is one of the global states.
924        match result {
925            SelectorMatchingResult::Matched => {
926                debug_assert!(
927                    matches_compound_selector.to_bool(true),
928                    "Compound didn't match?"
929                );
930                if !matches_compound_selector.to_bool(false) {
931                    return SelectorMatchingResult::Unknown;
932                }
933                return result;
934            },
935            SelectorMatchingResult::Unknown | SelectorMatchingResult::NotMatchedGlobally => {
936                return result
937            },
938            _ => {},
939        }
940
941        match combinator {
942            Combinator::Descendant => {
943                // The Descendant combinator and the status is
944                // NotMatchedAndRestartFromClosestLaterSibling or
945                // NotMatchedAndRestartFromClosestDescendant, or the LaterSibling combinator and
946                // the status is NotMatchedAndRestartFromClosestDescendant, we can continue to
947                // matching on the next candidate element.
948            },
949            Combinator::Child => {
950                // Upgrade the failure status to NotMatchedAndRestartFromClosestDescendant.
951                return SelectorMatchingResult::NotMatchedAndRestartFromClosestDescendant;
952            },
953            Combinator::LaterSibling => {
954                // If the failure status is NotMatchedAndRestartFromClosestDescendant and combinator is
955                // LaterSibling, give up this LaterSibling matching and restart from the closest
956                // descendant combinator.
957                if matches!(
958                    result,
959                    SelectorMatchingResult::NotMatchedAndRestartFromClosestDescendant
960                ) {
961                    return result;
962                }
963            },
964            Combinator::NextSibling
965            | Combinator::PseudoElement
966            | Combinator::Part
967            | Combinator::SlotAssignment => {
968                // NOTE(emilio): Conceptually, PseudoElement / Part / SlotAssignment should return
969                // `candidate_not_found`, but it doesn't matter in practice since they don't have
970                // sibling / descendant combinators to the right of them. This hopefully saves one
971                // branch.
972                return result;
973            },
974        }
975
976        if featureless {
977            // A featureless element didn't match the selector, we can stop matching now rather
978            // than looking at following elements for our combinator.
979            return candidate_not_found;
980        }
981    }
982}
983
984#[inline]
985fn matches_local_name<E>(element: &E, local_name: &LocalName<E::Impl>) -> bool
986where
987    E: Element,
988{
989    let name = select_name(element, &local_name.name, &local_name.lower_name).borrow();
990    element.has_local_name(name)
991}
992
993fn matches_part<E>(
994    element: &E,
995    parts: &[<E::Impl as SelectorImpl>::Identifier],
996    context: &mut MatchingContext<E::Impl>,
997) -> bool
998where
999    E: Element,
1000{
1001    let mut hosts = SmallVec::<[E; 4]>::new();
1002
1003    let mut host = match element.containing_shadow_host() {
1004        Some(h) => h,
1005        None => return false,
1006    };
1007
1008    let current_host = context.current_host;
1009    if current_host != Some(host.opaque()) {
1010        loop {
1011            let outer_host = host.containing_shadow_host();
1012            if outer_host.as_ref().map(|h| h.opaque()) == current_host {
1013                break;
1014            }
1015            let outer_host = match outer_host {
1016                Some(h) => h,
1017                None => return false,
1018            };
1019            // TODO(emilio): if worth it, we could early return if
1020            // host doesn't have the exportparts attribute.
1021            hosts.push(host);
1022            host = outer_host;
1023        }
1024    }
1025
1026    // Translate the part into the right scope.
1027    parts.iter().all(|part| {
1028        let mut part = part.clone();
1029        for host in hosts.iter().rev() {
1030            part = match host.imported_part(&part) {
1031                Some(p) => p,
1032                None => return false,
1033            };
1034        }
1035        element.is_part(&part)
1036    })
1037}
1038
1039fn matches_host<E>(
1040    element: &E,
1041    selector: Option<&Selector<E::Impl>>,
1042    context: &mut MatchingContext<E::Impl>,
1043    rightmost: SubjectOrPseudoElement,
1044) -> KleeneValue
1045where
1046    E: Element,
1047{
1048    let host = match context.shadow_host() {
1049        Some(h) => h,
1050        None => return KleeneValue::False,
1051    };
1052    if host != element.opaque() {
1053        return KleeneValue::False;
1054    }
1055    let Some(selector) = selector else {
1056        return KleeneValue::True;
1057    };
1058    context.nest(|context| {
1059        context.with_featureless(false, |context| {
1060            matches_complex_selector(selector.iter(), element, context, rightmost)
1061        })
1062    })
1063}
1064
1065fn matches_slotted<E>(
1066    element: &E,
1067    selector: &Selector<E::Impl>,
1068    context: &mut MatchingContext<E::Impl>,
1069    rightmost: SubjectOrPseudoElement,
1070) -> KleeneValue
1071where
1072    E: Element,
1073{
1074    // <slots> are never flattened tree slottables.
1075    if element.is_html_slot_element() {
1076        return KleeneValue::False;
1077    }
1078    context.nest(|context| matches_complex_selector(selector.iter(), element, context, rightmost))
1079}
1080
1081fn matches_rare_attribute_selector<E>(
1082    element: &E,
1083    attr_sel: &AttrSelectorWithOptionalNamespace<E::Impl>,
1084) -> bool
1085where
1086    E: Element,
1087{
1088    let empty_string;
1089    let namespace = match attr_sel.namespace() {
1090        Some(ns) => ns,
1091        None => {
1092            empty_string = crate::parser::namespace_empty_string::<E::Impl>();
1093            NamespaceConstraint::Specific(&empty_string)
1094        },
1095    };
1096    element.attr_matches(
1097        &namespace,
1098        select_name(element, &attr_sel.local_name, &attr_sel.local_name_lower),
1099        &match attr_sel.operation {
1100            ParsedAttrSelectorOperation::Exists => AttrSelectorOperation::Exists,
1101            ParsedAttrSelectorOperation::WithValue {
1102                operator,
1103                case_sensitivity,
1104                ref value,
1105            } => AttrSelectorOperation::WithValue {
1106                operator,
1107                case_sensitivity: to_unconditional_case_sensitivity(case_sensitivity, element),
1108                value,
1109            },
1110        },
1111    )
1112}
1113
1114/// There are relatively few selectors in a given compound that may match a featureless element.
1115/// Instead of adding a check to every selector that may not match, we handle it here in an out of
1116/// line path.
1117pub(crate) fn compound_matches_featureless_host<Impl: SelectorImpl>(
1118    iter: &mut SelectorIter<Impl>,
1119    scope_matches_featureless_host: bool,
1120) -> MatchesFeaturelessHost {
1121    let mut matches = MatchesFeaturelessHost::Only;
1122    for component in iter {
1123        match component {
1124            Component::Scope | Component::ImplicitScope if scope_matches_featureless_host => {},
1125            // :host only matches featureless elements.
1126            Component::Host(..) => {},
1127            // Pseudo-elements are allowed to match as well.
1128            Component::PseudoElement(..) => {},
1129            // We allow logical pseudo-classes, but we'll fail matching of the inner selectors if
1130            // necessary.
1131            Component::Is(ref l) | Component::Where(ref l) => {
1132                let mut any_yes = false;
1133                let mut any_no = false;
1134                for selector in l.slice() {
1135                    match selector.matches_featureless_host(scope_matches_featureless_host) {
1136                        MatchesFeaturelessHost::Never => {
1137                            any_no = true;
1138                        },
1139                        MatchesFeaturelessHost::Yes => {
1140                            any_yes = true;
1141                            any_no = true;
1142                        },
1143                        MatchesFeaturelessHost::Only => {
1144                            any_yes = true;
1145                        },
1146                    }
1147                }
1148                if !any_yes {
1149                    return MatchesFeaturelessHost::Never;
1150                }
1151                if any_no {
1152                    // Potentially downgrade since we might match non-featureless elements too.
1153                    matches = MatchesFeaturelessHost::Yes;
1154                }
1155            },
1156            Component::Negation(ref l) => {
1157                // For now preserving behavior, see
1158                // https://github.com/w3c/csswg-drafts/issues/10179 for existing resolutions that
1159                // tweak this behavior.
1160                for selector in l.slice() {
1161                    if selector.matches_featureless_host(scope_matches_featureless_host)
1162                        != MatchesFeaturelessHost::Only
1163                    {
1164                        return MatchesFeaturelessHost::Never;
1165                    }
1166                }
1167            },
1168            // Other components don't match the host scope.
1169            _ => return MatchesFeaturelessHost::Never,
1170        }
1171    }
1172    matches
1173}
1174
1175/// Determines whether the given element matches the given compound selector.
1176#[inline]
1177fn matches_compound_selector<E>(
1178    selector_iter: &mut SelectorIter<E::Impl>,
1179    element: &E,
1180    context: &mut MatchingContext<E::Impl>,
1181    rightmost: SubjectOrPseudoElement,
1182) -> KleeneValue
1183where
1184    E: Element,
1185{
1186    if context.featureless()
1187        && compound_matches_featureless_host(
1188            &mut selector_iter.clone(),
1189            /* scope_matches_featureless_host = */ true,
1190        ) == MatchesFeaturelessHost::Never
1191    {
1192        return KleeneValue::False;
1193    }
1194    let quirks_data = if context.quirks_mode() == QuirksMode::Quirks {
1195        Some(selector_iter.clone())
1196    } else {
1197        None
1198    };
1199    let mut local_context = LocalMatchingContext {
1200        shared: context,
1201        rightmost,
1202        quirks_data,
1203    };
1204    KleeneValue::any_false(selector_iter, |simple| {
1205        matches_simple_selector(simple, element, &mut local_context)
1206    })
1207}
1208
1209/// Determines whether the given element matches the given single selector.
1210fn matches_simple_selector<E>(
1211    selector: &Component<E::Impl>,
1212    element: &E,
1213    context: &mut LocalMatchingContext<E::Impl>,
1214) -> KleeneValue
1215where
1216    E: Element,
1217{
1218    debug_assert!(context.shared.is_nested() || !context.shared.in_negation());
1219    let rightmost = context.rightmost;
1220    KleeneValue::from(match *selector {
1221        Component::ID(ref id) => {
1222            element.has_id(id, context.shared.classes_and_ids_case_sensitivity())
1223        },
1224        Component::Class(ref class) => {
1225            element.has_class(class, context.shared.classes_and_ids_case_sensitivity())
1226        },
1227        Component::LocalName(ref local_name) => matches_local_name(element, local_name),
1228        Component::AttributeInNoNamespaceExists {
1229            ref local_name,
1230            ref local_name_lower,
1231        } => element.has_attr_in_no_namespace(select_name(element, local_name, local_name_lower)),
1232        Component::AttributeInNoNamespace {
1233            ref local_name,
1234            ref value,
1235            operator,
1236            case_sensitivity,
1237        } => element.attr_matches(
1238            &NamespaceConstraint::Specific(&crate::parser::namespace_empty_string::<E::Impl>()),
1239            local_name,
1240            &AttrSelectorOperation::WithValue {
1241                operator,
1242                case_sensitivity: to_unconditional_case_sensitivity(case_sensitivity, element),
1243                value,
1244            },
1245        ),
1246        Component::AttributeOther(ref attr_sel) => {
1247            matches_rare_attribute_selector(element, attr_sel)
1248        },
1249        Component::Part(ref parts) => matches_part(element, parts, &mut context.shared),
1250        Component::Slotted(ref selector) => {
1251            return matches_slotted(element, selector, &mut context.shared, rightmost);
1252        },
1253        Component::PseudoElement(ref pseudo) => {
1254            element.match_pseudo_element(pseudo, context.shared)
1255        },
1256        Component::ExplicitUniversalType | Component::ExplicitAnyNamespace => true,
1257        Component::Namespace(_, ref url) | Component::DefaultNamespace(ref url) => {
1258            element.has_namespace(&url.borrow())
1259        },
1260        Component::ExplicitNoNamespace => {
1261            let ns = crate::parser::namespace_empty_string::<E::Impl>();
1262            element.has_namespace(&ns.borrow())
1263        },
1264        Component::NonTSPseudoClass(ref pc) => {
1265            if let Some(ref iter) = context.quirks_data {
1266                if pc.is_active_or_hover()
1267                    && !element.is_link()
1268                    && hover_and_active_quirk_applies(iter, context.shared, context.rightmost)
1269                {
1270                    return KleeneValue::False;
1271                }
1272            }
1273            element.match_non_ts_pseudo_class(pc, &mut context.shared)
1274        },
1275        Component::Root => element.is_root(),
1276        Component::Empty => {
1277            if context.shared.needs_selector_flags() {
1278                element.apply_selector_flags(ElementSelectorFlags::HAS_EMPTY_SELECTOR);
1279            }
1280            element.is_empty()
1281        },
1282        Component::Host(ref selector) => {
1283            return matches_host(element, selector.as_ref(), &mut context.shared, rightmost);
1284        },
1285        Component::ParentSelector | Component::Scope | Component::ImplicitScope => {
1286            match context.shared.scope_element {
1287                Some(ref scope_element) => element.opaque() == *scope_element,
1288                None => element.is_root(),
1289            }
1290        },
1291        Component::Nth(ref nth_data) => {
1292            return matches_generic_nth_child(element, context.shared, nth_data, &[], rightmost);
1293        },
1294        Component::NthOf(ref nth_of_data) => {
1295            return context.shared.nest(|context| {
1296                matches_generic_nth_child(
1297                    element,
1298                    context,
1299                    nth_of_data.nth_data(),
1300                    nth_of_data.selectors(),
1301                    rightmost,
1302                )
1303            })
1304        },
1305        Component::Is(ref list) | Component::Where(ref list) => {
1306            return context.shared.nest(|context| {
1307                matches_complex_selector_list(list.slice(), element, context, rightmost)
1308            })
1309        },
1310        Component::Negation(ref list) => {
1311            return context.shared.nest_for_negation(|context| {
1312                !matches_complex_selector_list(list.slice(), element, context, rightmost)
1313            })
1314        },
1315        Component::Has(ref relative_selectors) => {
1316            return match_relative_selectors(
1317                relative_selectors,
1318                element,
1319                context.shared,
1320                rightmost,
1321            );
1322        },
1323        Component::Combinator(_) => unsafe {
1324            debug_unreachable!("Shouldn't try to selector-match combinators")
1325        },
1326        Component::RelativeSelectorAnchor => {
1327            let anchor = context.shared.relative_selector_anchor();
1328            // We may match inner relative selectors, in which case we want to always match.
1329            anchor.map_or(true, |a| a == element.opaque())
1330        },
1331        Component::Invalid(..) => false,
1332    })
1333}
1334
1335#[inline(always)]
1336pub fn select_name<'a, E: Element, T: PartialEq>(
1337    element: &E,
1338    local_name: &'a T,
1339    local_name_lower: &'a T,
1340) -> &'a T {
1341    if local_name == local_name_lower || element.is_html_element_in_html_document() {
1342        local_name_lower
1343    } else {
1344        local_name
1345    }
1346}
1347
1348#[inline(always)]
1349pub fn to_unconditional_case_sensitivity<'a, E: Element>(
1350    parsed: ParsedCaseSensitivity,
1351    element: &E,
1352) -> CaseSensitivity {
1353    match parsed {
1354        ParsedCaseSensitivity::CaseSensitive | ParsedCaseSensitivity::ExplicitCaseSensitive => {
1355            CaseSensitivity::CaseSensitive
1356        },
1357        ParsedCaseSensitivity::AsciiCaseInsensitive => CaseSensitivity::AsciiCaseInsensitive,
1358        ParsedCaseSensitivity::AsciiCaseInsensitiveIfInHtmlElementInHtmlDocument => {
1359            if element.is_html_element_in_html_document() {
1360                CaseSensitivity::AsciiCaseInsensitive
1361            } else {
1362                CaseSensitivity::CaseSensitive
1363            }
1364        },
1365    }
1366}
1367
1368fn matches_generic_nth_child<E>(
1369    element: &E,
1370    context: &mut MatchingContext<E::Impl>,
1371    nth_data: &NthSelectorData,
1372    selectors: &[Selector<E::Impl>],
1373    rightmost: SubjectOrPseudoElement,
1374) -> KleeneValue
1375where
1376    E: Element,
1377{
1378    if element.ignores_nth_child_selectors() {
1379        return KleeneValue::False;
1380    }
1381    let has_selectors = !selectors.is_empty();
1382    let selectors_match = !has_selectors
1383        || matches_complex_selector_list(selectors, element, context, rightmost).to_bool(true);
1384    if let Some(may_return_unknown) = context.matching_for_invalidation_comparison() {
1385        // Skip expensive indexing math in invalidation.
1386        return if selectors_match && may_return_unknown {
1387            KleeneValue::Unknown
1388        } else {
1389            KleeneValue::from(selectors_match && !context.in_negation())
1390        };
1391    }
1392
1393    let NthSelectorData { ty, an_plus_b, .. } = *nth_data;
1394    let is_of_type = ty.is_of_type();
1395    if ty.is_only() {
1396        debug_assert!(
1397            !has_selectors,
1398            ":only-child and :only-of-type cannot have a selector list!"
1399        );
1400        return KleeneValue::from(
1401            matches_generic_nth_child(
1402                element,
1403                context,
1404                &NthSelectorData::first(is_of_type),
1405                selectors,
1406                rightmost,
1407            )
1408            .to_bool(true)
1409                && matches_generic_nth_child(
1410                    element,
1411                    context,
1412                    &NthSelectorData::last(is_of_type),
1413                    selectors,
1414                    rightmost,
1415                )
1416                .to_bool(true),
1417        );
1418    }
1419
1420    let is_from_end = ty.is_from_end();
1421
1422    // It's useful to know whether this can only select the first/last element
1423    // child for optimization purposes, see the `HAS_EDGE_CHILD_SELECTOR` flag.
1424    let is_edge_child_selector = nth_data.is_simple_edge() && !has_selectors;
1425
1426    if context.needs_selector_flags() {
1427        let mut flags = if is_edge_child_selector {
1428            ElementSelectorFlags::HAS_EDGE_CHILD_SELECTOR
1429        } else if is_from_end {
1430            ElementSelectorFlags::HAS_SLOW_SELECTOR
1431        } else {
1432            ElementSelectorFlags::HAS_SLOW_SELECTOR_LATER_SIBLINGS
1433        };
1434        flags |= if has_selectors {
1435            ElementSelectorFlags::HAS_SLOW_SELECTOR_NTH_OF
1436        } else {
1437            ElementSelectorFlags::HAS_SLOW_SELECTOR_NTH
1438        };
1439        element.apply_selector_flags(flags);
1440    }
1441
1442    if !selectors_match {
1443        return KleeneValue::False;
1444    }
1445
1446    // :first/last-child are rather trivial to match, don't bother with the
1447    // cache.
1448    if is_edge_child_selector {
1449        return if is_from_end {
1450            element.next_sibling_element()
1451        } else {
1452            element.prev_sibling_element()
1453        }
1454        .is_none()
1455        .into();
1456    }
1457
1458    // Lookup or compute the index.
1459    let index = if let Some(i) = context
1460        .nth_index_cache(is_of_type, is_from_end, selectors)
1461        .lookup(element.opaque())
1462    {
1463        i
1464    } else {
1465        let i = nth_child_index(
1466            element,
1467            context,
1468            selectors,
1469            is_of_type,
1470            is_from_end,
1471            /* check_cache = */ true,
1472            rightmost,
1473        );
1474        context
1475            .nth_index_cache(is_of_type, is_from_end, selectors)
1476            .insert(element.opaque(), i);
1477        i
1478    };
1479    debug_assert_eq!(
1480        index,
1481        nth_child_index(
1482            element,
1483            context,
1484            selectors,
1485            is_of_type,
1486            is_from_end,
1487            /* check_cache = */ false,
1488            rightmost,
1489        ),
1490        "invalid cache"
1491    );
1492
1493    an_plus_b.matches_index(index).into()
1494}
1495
1496#[inline]
1497fn nth_child_index<E>(
1498    element: &E,
1499    context: &mut MatchingContext<E::Impl>,
1500    selectors: &[Selector<E::Impl>],
1501    is_of_type: bool,
1502    is_from_end: bool,
1503    check_cache: bool,
1504    rightmost: SubjectOrPseudoElement,
1505) -> i32
1506where
1507    E: Element,
1508{
1509    // The traversal mostly processes siblings left to right. So when we walk
1510    // siblings to the right when computing NthLast/NthLastOfType we're unlikely
1511    // to get cache hits along the way. As such, we take the hit of walking the
1512    // siblings to the left checking the cache in the is_from_end case (this
1513    // matches what Gecko does). The indices-from-the-left is handled during the
1514    // regular look further below.
1515    if check_cache
1516        && is_from_end
1517        && !context
1518            .nth_index_cache(is_of_type, is_from_end, selectors)
1519            .is_empty()
1520    {
1521        let mut index: i32 = 1;
1522        let mut curr = element.clone();
1523        while let Some(e) = curr.prev_sibling_element() {
1524            curr = e;
1525            let matches = if is_of_type {
1526                element.is_same_type(&curr)
1527            } else if !selectors.is_empty() {
1528                matches_complex_selector_list(selectors, &curr, context, rightmost).to_bool(true)
1529            } else {
1530                true
1531            };
1532            if !matches {
1533                continue;
1534            }
1535            if let Some(i) = context
1536                .nth_index_cache(is_of_type, is_from_end, selectors)
1537                .lookup(curr.opaque())
1538            {
1539                return i - index;
1540            }
1541            index += 1;
1542        }
1543    }
1544
1545    let mut index: i32 = 1;
1546    let mut curr = element.clone();
1547    let next = |e: E| {
1548        if is_from_end {
1549            e.next_sibling_element()
1550        } else {
1551            e.prev_sibling_element()
1552        }
1553    };
1554    while let Some(e) = next(curr) {
1555        curr = e;
1556        let matches = if is_of_type {
1557            element.is_same_type(&curr)
1558        } else if !selectors.is_empty() {
1559            matches_complex_selector_list(selectors, &curr, context, rightmost).to_bool(true)
1560        } else {
1561            true
1562        };
1563        if !matches {
1564            continue;
1565        }
1566        // If we're computing indices from the left, check each element in the
1567        // cache. We handle the indices-from-the-right case at the top of this
1568        // function.
1569        if !is_from_end && check_cache {
1570            if let Some(i) = context
1571                .nth_index_cache(is_of_type, is_from_end, selectors)
1572                .lookup(curr.opaque())
1573            {
1574                return i + index;
1575            }
1576        }
1577        index += 1;
1578    }
1579
1580    index
1581}