Quelle  parser.rs   Sprache: unbekannt

/* 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::{AttrSelectorOperator, AttrSelectorWithOptionalNamespace};
use crate::attr::{NamespaceConstraint, ParsedAttrSelectorOperation, ParsedCaseSensitivity};
use crate::bloom::BLOOM_HASH_MASK;
use crate::builder::{
    relative_selector_list_specificity_and_flags, selector_list_specificity_and_flags,
    SelectorBuilder, SelectorFlags, Specificity, SpecificityAndFlags,
};
use crate::context::QuirksMode;
use crate::sink::Push;
use crate::visitor::SelectorListKind;
pub use crate::visitor::SelectorVisitor;
use cssparser::parse_nth;
use cssparser::{BasicParseError, BasicParseErrorKind, ParseError, ParseErrorKind};
use cssparser::{CowRcStr, Delimiter, SourceLocation};
use cssparser::{Parser as CssParser, ToCss, Token};
use precomputed_hash::PrecomputedHash;
use servo_arc::{Arc, ArcUnionBorrow, ThinArc, ThinArcUnion, UniqueArc};
use smallvec::SmallVec;
use std::borrow::{Borrow, Cow};
use std::fmt::{self, Debug};
use std::iter::Rev;
use std::slice;
use bitflags::bitflags;
use cssparser::match_ignore_ascii_case;
use debug_unreachable::debug_unreachable;

#[cfg(feature = "to_shmem")]
use to_shmem_derive::ToShmem;

/// A trait that represents a pseudo-element.
pub trait PseudoElement: Sized + ToCss {
    /// The `SelectorImpl` this pseudo-element is used for.
    type Impl: SelectorImpl;

    /// Whether the pseudo-element supports a given state selector to the right
    /// of it.
    fn accepts_state_pseudo_classes(&self) -> bool {
        false
    }

    /// Whether this pseudo-element is valid after a ::slotted(..) pseudo.
    fn valid_after_slotted(&self) -> bool {
        false
    }

    /// The count we contribute to the specificity from this pseudo-element.
    fn specificity_count(&self) -> u32 {
        1
    }

    /// Whether this pseudo-element is in a pseudo-element tree (excluding the pseudo-element
    /// root).
    /// https://drafts.csswg.org/css-view-transitions-1/#pseudo-root
    fn is_in_pseudo_element_tree(&self) -> bool {
        false
    }
}

/// A trait that represents a pseudo-class.
pub trait NonTSPseudoClass: Sized + ToCss {
    /// The `SelectorImpl` this pseudo-element is used for.
    type Impl: SelectorImpl;

    /// Whether this pseudo-class is :active or :hover.
    fn is_active_or_hover(&self) -> bool;

    /// Whether this pseudo-class belongs to:
    ///
    /// https://drafts.csswg.org/selectors-4/#useraction-pseudos
    fn is_user_action_state(&self) -> bool;

    fn visit<V>(&self, _visitor: &mut V) -> bool
    where
        V: SelectorVisitor<Impl = Self::Impl>,
    {
        true
    }
}

/// Returns a Cow::Borrowed if `s` is already ASCII lowercase, and a
/// Cow::Owned if `s` had to be converted into ASCII lowercase.
fn to_ascii_lowercase(s: &str) -> Cow<str> {
    if let Some(first_uppercase) = s.bytes().position(|byte| byte >= b'A' && byte <= b'Z') {
        let mut string = s.to_owned();
        string[first_uppercase..].make_ascii_lowercase();
        string.into()
    } else {
        s.into()
    }
}

bitflags! {
    /// Flags that indicate at which point of parsing a selector are we.
    #[derive(Copy, Clone)]
    struct SelectorParsingState: u16 {
        /// Whether we should avoid adding default namespaces to selectors that
        /// aren't type or universal selectors.
        const SKIP_DEFAULT_NAMESPACE = 1 << 0;

        /// Whether we've parsed a ::slotted() pseudo-element already.
        ///
        /// If so, then we can only parse a subset of pseudo-elements, and
        /// whatever comes after them if so.
        const AFTER_SLOTTED = 1 << 1;
        /// Whether we've parsed a ::part() pseudo-element already.
        ///
        /// If so, then we can only parse a subset of pseudo-elements, and
        /// whatever comes after them if so.
        const AFTER_PART = 1 << 2;
        /// Whether we've parsed a pseudo-element (as in, an
        /// `Impl::PseudoElement` thus not accounting for `::slotted` or
        /// `::part`) already.
        ///
        /// If so, then other pseudo-elements and most other selectors are
        /// disallowed.
        const AFTER_PSEUDO_ELEMENT = 1 << 3;
        /// Whether we've parsed a non-stateful pseudo-element (again, as-in
        /// `Impl::PseudoElement`) already. If so, then other pseudo-classes are
        /// disallowed. If this flag is set, `AFTER_PSEUDO_ELEMENT` must be set
        /// as well.
        const AFTER_NON_STATEFUL_PSEUDO_ELEMENT = 1 << 4;

        /// Whether we are after any of the pseudo-like things.
        const AFTER_PSEUDO = Self::AFTER_PART.bits() | Self::AFTER_SLOTTED.bits() | Self::AFTER_PSEUDO_ELEMENT.bits();

        /// Whether we explicitly disallow combinators.
        const DISALLOW_COMBINATORS = 1 << 5;

        /// Whether we explicitly disallow pseudo-element-like things.
        const DISALLOW_PSEUDOS = 1 << 6;

        /// Whether we explicitly disallow relative selectors (i.e. `:has()`).
        const DISALLOW_RELATIVE_SELECTOR = 1 << 7;

        /// Whether we've parsed a pseudo-element which is in a pseudo-element tree (i.e. it is a
        /// descendant pseudo of a pseudo-element root).
        const IN_PSEUDO_ELEMENT_TREE = 1 << 8;
    }
}

impl SelectorParsingState {
    #[inline]
    fn allows_pseudos(self) -> bool {
        // NOTE(emilio): We allow pseudos after ::part and such.
        !self.intersects(Self::AFTER_PSEUDO_ELEMENT | Self::DISALLOW_PSEUDOS)
    }

    #[inline]
    fn allows_slotted(self) -> bool {
        !self.intersects(Self::AFTER_PSEUDO | Self::DISALLOW_PSEUDOS)
    }

    #[inline]
    fn allows_part(self) -> bool {
        !self.intersects(Self::AFTER_PSEUDO | Self::DISALLOW_PSEUDOS)
    }

    #[inline]
    fn allows_non_functional_pseudo_classes(self) -> bool {
        !self.intersects(Self::AFTER_SLOTTED | Self::AFTER_NON_STATEFUL_PSEUDO_ELEMENT)
    }

    #[inline]
    fn allows_tree_structural_pseudo_classes(self) -> bool {
        !self.intersects(Self::AFTER_PSEUDO) || self.intersects(Self::IN_PSEUDO_ELEMENT_TREE)
    }

    #[inline]
    fn allows_combinators(self) -> bool {
        !self.intersects(Self::DISALLOW_COMBINATORS)
    }

    #[inline]
    fn allows_only_child_pseudo_class_only(self) -> bool {
        self.intersects(Self::IN_PSEUDO_ELEMENT_TREE)
    }
}

pub type SelectorParseError<'i> = ParseError<'i, SelectorParseErrorKind<'i>>;

#[derive(Clone, Debug, PartialEq)]
pub enum SelectorParseErrorKind<'i> {
    NoQualifiedNameInAttributeSelector(Token<'i>),
    EmptySelector,
    DanglingCombinator,
    NonCompoundSelector,
    NonPseudoElementAfterSlotted,
    InvalidPseudoElementAfterSlotted,
    InvalidPseudoElementInsideWhere,
    InvalidState,
    UnexpectedTokenInAttributeSelector(Token<'i>),
    PseudoElementExpectedColon(Token<'i>),
    PseudoElementExpectedIdent(Token<'i>),
    NoIdentForPseudo(Token<'i>),
    UnsupportedPseudoClassOrElement(CowRcStr<'i>),
    UnexpectedIdent(CowRcStr<'i>),
    ExpectedNamespace(CowRcStr<'i>),
    ExpectedBarInAttr(Token<'i>),
    BadValueInAttr(Token<'i>),
    InvalidQualNameInAttr(Token<'i>),
    ExplicitNamespaceUnexpectedToken(Token<'i>),
    ClassNeedsIdent(Token<'i>),
}

macro_rules! with_all_bounds {
    (
        [ $( $InSelector: tt )* ]
        [ $( $CommonBounds: tt )* ]
        [ $( $FromStr: tt )* ]
    ) => {
        /// This trait allows to define the parser implementation in regards
        /// of pseudo-classes/elements
        ///
        /// NB: We need Clone so that we can derive(Clone) on struct with that
        /// are parameterized on SelectorImpl. See
        /// <https://github.com/rust-lang/rust/issues/26925>
        pub trait SelectorImpl: Clone + Debug + Sized + 'static {
            type ExtraMatchingData<'a>: Sized + Default;
            type AttrValue: $($InSelector)*;
            type Identifier: $($InSelector)* + PrecomputedHash;
            type LocalName: $($InSelector)* + Borrow<Self::BorrowedLocalName> + PrecomputedHash;
            type NamespaceUrl: $($CommonBounds)* + Default + Borrow<Self::BorrowedNamespaceUrl> + PrecomputedHash;
            type NamespacePrefix: $($InSelector)* + Default;
            type BorrowedNamespaceUrl: ?Sized + Eq;
            type BorrowedLocalName: ?Sized + Eq;

            /// non tree-structural pseudo-classes
            /// (see: https://drafts.csswg.org/selectors/#structural-pseudos)
            type NonTSPseudoClass: $($CommonBounds)* + NonTSPseudoClass<Impl = Self>;

            /// pseudo-elements
            type PseudoElement: $($CommonBounds)* + PseudoElement<Impl = Self>;

            /// Whether attribute hashes should be collected for filtering
            /// purposes.
            fn should_collect_attr_hash(_name: &Self::LocalName) -> bool {
                false
            }
        }
    }
}

macro_rules! with_bounds {
    ( [ $( $CommonBounds: tt )* ] [ $( $FromStr: tt )* ]) => {
        with_all_bounds! {
            [$($CommonBounds)* + $($FromStr)* + ToCss]
            [$($CommonBounds)*]
            [$($FromStr)*]
        }
    }
}

with_bounds! {
    [Clone + Eq]
    [for<'a> From<&'a str>]
}

pub trait Parser<'i> {
    type Impl: SelectorImpl;
    type Error: 'i + From<SelectorParseErrorKind<'i>>;

    /// Whether to parse the `::slotted()` pseudo-element.
    fn parse_slotted(&self) -> bool {
        false
    }

    /// Whether to parse the `::part()` pseudo-element.
    fn parse_part(&self) -> bool {
        false
    }

    /// Whether to parse the selector list of nth-child() or nth-last-child().
    fn parse_nth_child_of(&self) -> bool {
        false
    }

    /// Whether to parse `:is` and `:where` pseudo-classes.
    fn parse_is_and_where(&self) -> bool {
        false
    }

    /// Whether to parse the :has pseudo-class.
    fn parse_has(&self) -> bool {
        false
    }

    /// Whether to parse the '&' delimiter as a parent selector.
    fn parse_parent_selector(&self) -> bool {
        false
    }

    /// Whether the given function name is an alias for the `:is()` function.
    fn is_is_alias(&self, _name: &str) -> bool {
        false
    }

    /// Whether to parse the `:host` pseudo-class.
    fn parse_host(&self) -> bool {
        false
    }

    /// Whether to allow forgiving selector-list parsing.
    fn allow_forgiving_selectors(&self) -> bool {
        true
    }

    /// This function can return an "Err" pseudo-element in order to support CSS2.1
    /// pseudo-elements.
    fn parse_non_ts_pseudo_class(
        &self,
        location: SourceLocation,
        name: CowRcStr<'i>,
    ) -> Result<<Self::Impl as SelectorImpl>::NonTSPseudoClass, ParseError<'i, Self::Error>> {
        Err(
            location.new_custom_error(SelectorParseErrorKind::UnsupportedPseudoClassOrElement(
                name,
            )),
        )
    }

    fn parse_non_ts_functional_pseudo_class<'t>(
        &self,
        name: CowRcStr<'i>,
        parser: &mut CssParser<'i, 't>,
        _after_part: bool,
    ) -> Result<<Self::Impl as SelectorImpl>::NonTSPseudoClass, ParseError<'i, Self::Error>> {
        Err(
            parser.new_custom_error(SelectorParseErrorKind::UnsupportedPseudoClassOrElement(
                name,
            )),
        )
    }

    fn parse_pseudo_element(
        &self,
        location: SourceLocation,
        name: CowRcStr<'i>,
    ) -> Result<<Self::Impl as SelectorImpl>::PseudoElement, ParseError<'i, Self::Error>> {
        Err(
            location.new_custom_error(SelectorParseErrorKind::UnsupportedPseudoClassOrElement(
                name,
            )),
        )
    }

    fn parse_functional_pseudo_element<'t>(
        &self,
        name: CowRcStr<'i>,
        arguments: &mut CssParser<'i, 't>,
    ) -> Result<<Self::Impl as SelectorImpl>::PseudoElement, ParseError<'i, Self::Error>> {
        Err(
            arguments.new_custom_error(SelectorParseErrorKind::UnsupportedPseudoClassOrElement(
                name,
            )),
        )
    }

    fn default_namespace(&self) -> Option<<Self::Impl as SelectorImpl>::NamespaceUrl> {
        None
    }

    fn namespace_for_prefix(
        &self,
        _prefix: &<Self::Impl as SelectorImpl>::NamespacePrefix,
    ) -> Option<<Self::Impl as SelectorImpl>::NamespaceUrl> {
        None
    }
}

/// A selector list is a tagged pointer with either a single selector, or a ThinArc<()> of multiple
/// selectors.
#[derive(Clone, Eq, Debug, PartialEq)]
#[cfg_attr(feature = "to_shmem", derive(ToShmem))]
#[cfg_attr(feature = "to_shmem", shmem(no_bounds))]
pub struct SelectorList<Impl: SelectorImpl>(
    #[cfg_attr(feature = "to_shmem", shmem(field_bound))]
    ThinArcUnion<SpecificityAndFlags, Component<Impl>, (), Selector<Impl>>,
);

impl<Impl: SelectorImpl> SelectorList<Impl> {
    /// See Arc::mark_as_intentionally_leaked
    pub fn mark_as_intentionally_leaked(&self) {
        if let ArcUnionBorrow::Second(ref list) = self.0.borrow() {
            list.with_arc(|list| list.mark_as_intentionally_leaked())
        }
        self.slice().iter().for_each(|s| s.mark_as_intentionally_leaked())
    }

    pub fn from_one(selector: Selector<Impl>) -> Self {
        #[cfg(debug_assertions)]
        let selector_repr = unsafe { *(&selector as *const _ as *const usize) };
        let list = Self(ThinArcUnion::from_first(selector.into_data()));
        #[cfg(debug_assertions)]
        debug_assert_eq!(
            selector_repr,
            unsafe { *(&list as *const _ as *const usize) },
            "We rely on the same bit representation for the single selector variant"
        );
        list
    }

    pub fn from_iter(mut iter: impl ExactSizeIterator<Item = Selector<Impl>>) -> Self {
        if iter.len() == 1 {
            Self::from_one(iter.next().unwrap())
        } else {
            Self(ThinArcUnion::from_second(ThinArc::from_header_and_iter(
                (),
                iter,
            )))
        }
    }

    #[inline]
    pub fn slice(&self) -> &[Selector<Impl>] {
        match self.0.borrow() {
            ArcUnionBorrow::First(..) => {
                // SAFETY: see from_one.
                let selector: &Selector<Impl> = unsafe { std::mem::transmute(self) };
                std::slice::from_ref(selector)
            },
            ArcUnionBorrow::Second(list) => list.get().slice(),
        }
    }

    #[inline]
    pub fn len(&self) -> usize {
        match self.0.borrow() {
            ArcUnionBorrow::First(..) => 1,
            ArcUnionBorrow::Second(list) => list.len(),
        }
    }

    /// Returns the address on the heap of the ThinArc for memory reporting.
    pub fn thin_arc_heap_ptr(&self) -> *const ::std::os::raw::c_void {
        match self.0.borrow() {
            ArcUnionBorrow::First(s) => s.with_arc(|a| a.heap_ptr()),
            ArcUnionBorrow::Second(s) => s.with_arc(|a| a.heap_ptr()),
        }
    }
}

/// Uniquely identify a selector based on its components, which is behind ThinArc and
/// is therefore stable.
#[derive(Clone, Copy, Hash, Eq, PartialEq)]
pub struct SelectorKey(usize);

impl SelectorKey {
    /// Create a new key based on the given selector.
    pub fn new<Impl: SelectorImpl>(selector: &Selector<Impl>) -> Self {
        Self(selector.0.slice().as_ptr() as usize)
    }
}

/// Whether or not we're using forgiving parsing mode
#[derive(PartialEq)]
enum ForgivingParsing {
    /// Discard the entire selector list upon encountering any invalid selector.
    /// This is the default behavior for almost all of CSS.
    No,
    /// Ignore invalid selectors, potentially creating an empty selector list.
    ///
    /// This is the error recovery mode of :is() and :where()
    Yes,
}

/// Flag indicating if we're parsing relative selectors.
#[derive(Copy, Clone, PartialEq)]
pub enum ParseRelative {
    /// Expect selectors to start with a combinator, assuming descendant combinator if not present.
    ForHas,
    /// Allow selectors to start with a combinator, prepending a parent selector if so. Do nothing
    /// otherwise
    ForNesting,
    /// Allow selectors to start with a combinator, prepending a scope selector if so. Do nothing
    /// otherwise
    ForScope,
    /// Treat as parse error if any selector begins with a combinator.
    No,
}

impl<Impl: SelectorImpl> SelectorList<Impl> {
    /// Returns a selector list with a single `:scope` selector (with specificity)
    pub fn scope() -> Self {
        Self::from_one(Selector::scope())
    }
    /// Returns a selector list with a single implicit `:scope` selector (no specificity)
    pub fn implicit_scope() -> Self {
        Self::from_one(Selector::implicit_scope())
    }

    /// Parse a comma-separated list of Selectors.
    /// <https://drafts.csswg.org/selectors/#grouping>
    ///
    /// Return the Selectors or Err if there is an invalid selector.
    pub fn parse<'i, 't, P>(
        parser: &P,
        input: &mut CssParser<'i, 't>,
        parse_relative: ParseRelative,
    ) -> Result<Self, ParseError<'i, P::Error>>
    where
        P: Parser<'i, Impl = Impl>,
    {
        Self::parse_with_state(
            parser,
            input,
            SelectorParsingState::empty(),
            ForgivingParsing::No,
            parse_relative,
        )
    }

    /// Same as `parse`, but disallow parsing of pseudo-elements.
    pub fn parse_disallow_pseudo<'i, 't, P>(
        parser: &P,
        input: &mut CssParser<'i, 't>,
        parse_relative: ParseRelative,
    ) -> Result<Self, ParseError<'i, P::Error>>
    where
        P: Parser<'i, Impl = Impl>,
    {
        Self::parse_with_state(
            parser,
            input,
            SelectorParsingState::DISALLOW_PSEUDOS,
            ForgivingParsing::No,
            parse_relative,
        )
    }

    pub fn parse_forgiving<'i, 't, P>(
        parser: &P,
        input: &mut CssParser<'i, 't>,
        parse_relative: ParseRelative,
    ) -> Result<Self, ParseError<'i, P::Error>>
    where
        P: Parser<'i, Impl = Impl>,
    {
        Self::parse_with_state(
            parser,
            input,
            SelectorParsingState::empty(),
            ForgivingParsing::Yes,
            parse_relative,
        )
    }

    #[inline]
    fn parse_with_state<'i, 't, P>(
        parser: &P,
        input: &mut CssParser<'i, 't>,
        state: SelectorParsingState,
        recovery: ForgivingParsing,
        parse_relative: ParseRelative,
    ) -> Result<Self, ParseError<'i, P::Error>>
    where
        P: Parser<'i, Impl = Impl>,
    {
        let mut values = SmallVec::<[_; 4]>::new();
        let forgiving = recovery == ForgivingParsing::Yes && parser.allow_forgiving_selectors();
        loop {
            let selector = input.parse_until_before(Delimiter::Comma, |input| {
                let start = input.position();
                let mut selector = parse_selector(parser, input, state, parse_relative);
                if forgiving && (selector.is_err() || input.expect_exhausted().is_err()) {
                    input.expect_no_error_token()?;
                    selector = Ok(Selector::new_invalid(input.slice_from(start)));
                }
                selector
            })?;

            values.push(selector);

            match input.next() {
                Ok(&Token::Comma) => {},
                Ok(_) => unreachable!(),
                Err(_) => break,
            }
        }
        Ok(Self::from_iter(values.into_iter()))
    }

    /// Replaces the parent selector in all the items of the selector list.
    pub fn replace_parent_selector(&self, parent: &SelectorList<Impl>) -> Self {
        Self::from_iter(
            self.slice()
                .iter()
                .map(|selector| selector.replace_parent_selector(parent)),
        )
    }

    /// Creates a SelectorList from a Vec of selectors. Used in tests.
    #[allow(dead_code)]
    pub(crate) fn from_vec(v: Vec<Selector<Impl>>) -> Self {
        SelectorList::from_iter(v.into_iter())
    }
}

/// Parses one compound selector suitable for nested stuff like :-moz-any, etc.
fn parse_inner_compound_selector<'i, 't, P, Impl>(
    parser: &P,
    input: &mut CssParser<'i, 't>,
    state: SelectorParsingState,
) -> Result<Selector<Impl>, ParseError<'i, P::Error>>
where
    P: Parser<'i, Impl = Impl>,
    Impl: SelectorImpl,
{
    parse_selector(
        parser,
        input,
        state | SelectorParsingState::DISALLOW_PSEUDOS | SelectorParsingState::DISALLOW_COMBINATORS,
        ParseRelative::No,
    )
}

/// Ancestor hashes for the bloom filter. We precompute these and store them
/// inline with selectors to optimize cache performance during matching.
/// This matters a lot.
///
/// We use 4 hashes, which is copied from Gecko, who copied it from WebKit.
/// Note that increasing the number of hashes here will adversely affect the
/// cache hit when fast-rejecting long lists of Rules with inline hashes.
///
/// Because the bloom filter only uses the bottom 24 bits of the hash, we pack
/// the fourth hash into the upper bits of the first three hashes in order to
/// shrink Rule (whose size matters a lot). This scheme minimizes the runtime
/// overhead of the packing for the first three hashes (we just need to mask
/// off the upper bits) at the expense of making the fourth somewhat more
/// complicated to assemble, because we often bail out before checking all the
/// hashes.
#[derive(Clone, Debug, Eq, PartialEq)]
pub struct AncestorHashes {
    pub packed_hashes: [u32; 3],
}

pub(crate) fn collect_selector_hashes<'a, Impl: SelectorImpl, Iter>(
    iter: Iter,
    quirks_mode: QuirksMode,
    hashes: &mut [u32; 4],
    len: &mut usize,
    create_inner_iterator: fn(&'a Selector<Impl>) -> Iter,
) -> bool
where
    Iter: Iterator<Item = &'a Component<Impl>>,
{
    for component in iter {
        let hash = match *component {
            Component::LocalName(LocalName {
                ref name,
                ref lower_name,
            }) => {
                // Only insert the local-name into the filter if it's all
                // lowercase.  Otherwise we would need to test both hashes, and
                // our data structures aren't really set up for that.
                if name != lower_name {
                    continue;
                }
                name.precomputed_hash()
            },
            Component::DefaultNamespace(ref url) | Component::Namespace(_, ref url) => {
                url.precomputed_hash()
            },
            // In quirks mode, class and id selectors should match
            // case-insensitively, so just avoid inserting them into the filter.
            Component::ID(ref id) if quirks_mode != QuirksMode::Quirks => id.precomputed_hash(),
            Component::Class(ref class) if quirks_mode != QuirksMode::Quirks => {
                class.precomputed_hash()
            },
            Component::AttributeInNoNamespace { ref local_name, .. }
                if Impl::should_collect_attr_hash(local_name) =>
            {
                // AttributeInNoNamespace is only used when local_name ==
                // local_name_lower.
                local_name.precomputed_hash()
            },
            Component::AttributeInNoNamespaceExists {
                ref local_name,
                ref local_name_lower,
                ..
            } => {
                // Only insert the local-name into the filter if it's all
                // lowercase.  Otherwise we would need to test both hashes, and
                // our data structures aren't really set up for that.
                if local_name != local_name_lower || !Impl::should_collect_attr_hash(local_name) {
                    continue;
                }
                local_name.precomputed_hash()
            },
            Component::AttributeOther(ref selector) => {
                if selector.local_name != selector.local_name_lower ||
                    !Impl::should_collect_attr_hash(&selector.local_name)
                {
                    continue;
                }
                selector.local_name.precomputed_hash()
            },
            Component::Is(ref list) | Component::Where(ref list) => {
                // :where and :is OR their selectors, so we can't put any hash
                // in the filter if there's more than one selector, as that'd
                // exclude elements that may match one of the other selectors.
                let slice = list.slice();
                if slice.len() == 1 &&
                    !collect_selector_hashes(
                        create_inner_iterator(&slice[0]),
                        quirks_mode,
                        hashes,
                        len,
                        create_inner_iterator,
                    )
                {
                    return false;
                }
                continue;
            },
            _ => continue,
        };

        hashes[*len] = hash & BLOOM_HASH_MASK;
        *len += 1;
        if *len == hashes.len() {
            return false;
        }
    }
    true
}

fn collect_ancestor_hashes<Impl: SelectorImpl>(
    iter: SelectorIter<Impl>,
    quirks_mode: QuirksMode,
    hashes: &mut [u32; 4],
    len: &mut usize,
) {
    collect_selector_hashes(AncestorIter::new(iter), quirks_mode, hashes, len, |s| {
        AncestorIter(s.iter())
    });
}

impl AncestorHashes {
    pub fn new<Impl: SelectorImpl>(selector: &Selector<Impl>, quirks_mode: QuirksMode) -> Self {
        // Compute ancestor hashes for the bloom filter.
        let mut hashes = [0u32; 4];
        let mut len = 0;
        collect_ancestor_hashes(selector.iter(), quirks_mode, &mut hashes, &mut len);
        debug_assert!(len <= 4);

        // Now, pack the fourth hash (if it exists) into the upper byte of each of
        // the other three hashes.
        if len == 4 {
            let fourth = hashes[3];
            hashes[0] |= (fourth & 0x000000ff) << 24;
            hashes[1] |= (fourth & 0x0000ff00) << 16;
            hashes[2] |= (fourth & 0x00ff0000) << 8;
        }

        AncestorHashes {
            packed_hashes: [hashes[0], hashes[1], hashes[2]],
        }
    }

    /// Returns the fourth hash, reassembled from parts.
    pub fn fourth_hash(&self) -> u32 {
        ((self.packed_hashes[0] & 0xff000000) >> 24) |
            ((self.packed_hashes[1] & 0xff000000) >> 16) |
            ((self.packed_hashes[2] & 0xff000000) >> 8)
    }
}

#[inline]
pub fn namespace_empty_string<Impl: SelectorImpl>() -> Impl::NamespaceUrl {
    // Rust type’s default, not default namespace
    Impl::NamespaceUrl::default()
}

type SelectorData<Impl> = ThinArc<SpecificityAndFlags, Component<Impl>>;

bitflags! {
    /// What kind of selectors potentially matching featureless shawdow host are present.
    #[derive(Clone, Copy, Debug, Eq, PartialEq)]
    pub struct FeaturelessHostMatches: u8 {
        /// This selector matches featureless shadow host via `:host`.
        const FOR_HOST = 1 << 0;
        /// This selector matches featureless shadow host via `:scope`.
        /// Featureless match applies only if we're:
        /// 1) In a scoping context, AND
        /// 2) The scope is a shadow host.
        const FOR_SCOPE = 1 << 1;
    }
}

impl FeaturelessHostMatches {
    fn insert_not_empty(&mut self, other: Self) -> bool {
        if other.is_empty() {
            return false;
        }
        self.insert(other);
        true
    }
}

/// A Selector stores a sequence of simple selectors and combinators. The
/// iterator classes allow callers to iterate at either the raw sequence level or
/// at the level of sequences of simple selectors separated by combinators. Most
/// callers want the higher-level iterator.
///
/// We store compound selectors internally right-to-left (in matching order).
/// Additionally, we invert the order of top-level compound selectors so that
/// each one matches left-to-right. This is because matching namespace, local name,
/// id, and class are all relatively cheap, whereas matching pseudo-classes might
/// be expensive (depending on the pseudo-class). Since authors tend to put the
/// pseudo-classes on the right, it's faster to start matching on the left.
///
/// This reordering doesn't change the semantics of selector matching, and we
/// handle it in to_css to make it invisible to serialization.
#[derive(Clone, Eq, PartialEq)]
#[cfg_attr(feature = "to_shmem", derive(ToShmem))]
#[cfg_attr(feature = "to_shmem", shmem(no_bounds))]
#[repr(transparent)]
pub struct Selector<Impl: SelectorImpl>(
    #[cfg_attr(feature = "to_shmem", shmem(field_bound))] SelectorData<Impl>,
);

impl<Impl: SelectorImpl> Selector<Impl> {
    /// See Arc::mark_as_intentionally_leaked
    pub fn mark_as_intentionally_leaked(&self) {
        self.0.mark_as_intentionally_leaked()
    }

    fn scope() -> Self {
        Self(ThinArc::from_header_and_iter(
            SpecificityAndFlags {
                specificity: Specificity::single_class_like().into(),
                flags: SelectorFlags::HAS_SCOPE,
            },
            std::iter::once(Component::Scope),
        ))
    }

    /// An implicit scope selector, much like :where(:scope).
    fn implicit_scope() -> Self {
        Self(ThinArc::from_header_and_iter(
            SpecificityAndFlags {
                specificity: 0,
                flags: SelectorFlags::HAS_SCOPE,
            },
            std::iter::once(Component::ImplicitScope),
        ))
    }

    #[inline]
    pub fn specificity(&self) -> u32 {
        self.0.header.specificity
    }

    #[inline]
    pub(crate) fn flags(&self) -> SelectorFlags {
        self.0.header.flags
    }

    #[inline]
    pub fn has_pseudo_element(&self) -> bool {
        self.flags().intersects(SelectorFlags::HAS_PSEUDO)
    }

    #[inline]
    pub fn has_parent_selector(&self) -> bool {
        self.flags().intersects(SelectorFlags::HAS_PARENT)
    }

    #[inline]
    pub fn has_scope_selector(&self) -> bool {
        self.flags().intersects(SelectorFlags::HAS_SCOPE)
    }

    #[inline]
    pub fn is_slotted(&self) -> bool {
        self.flags().intersects(SelectorFlags::HAS_SLOTTED)
    }

    #[inline]
    pub fn is_part(&self) -> bool {
        self.flags().intersects(SelectorFlags::HAS_PART)
    }

    #[inline]
    pub fn parts(&self) -> Option<&[Impl::Identifier]> {
        if !self.is_part() {
            return None;
        }

        let mut iter = self.iter();
        if self.has_pseudo_element() {
            // Skip the pseudo-element.
            for _ in &mut iter {}

            let combinator = iter.next_sequence()?;
            debug_assert_eq!(combinator, Combinator::PseudoElement);
        }

        for component in iter {
            if let Component::Part(ref part) = *component {
                return Some(part);
            }
        }

        debug_assert!(false, "is_part() lied somehow?");
        None
    }

    #[inline]
    pub fn pseudo_element(&self) -> Option<&Impl::PseudoElement> {
        if !self.has_pseudo_element() {
            return None;
        }

        for component in self.iter() {
            if let Component::PseudoElement(ref pseudo) = *component {
                return Some(pseudo);
            }
        }

        debug_assert!(false, "has_pseudo_element lied!");
        None
    }

    /// Whether this selector (pseudo-element part excluded) matches every element.
    ///
    /// Used for "pre-computed" pseudo-elements in components/style/stylist.rs
    #[inline]
    pub fn is_universal(&self) -> bool {
        self.iter_raw_match_order().all(|c| {
            matches!(
                *c,
                Component::ExplicitUniversalType |
                    Component::ExplicitAnyNamespace |
                    Component::Combinator(Combinator::PseudoElement) |
                    Component::PseudoElement(..)
            )
        })
    }

    /// Returns an iterator over this selector in matching order (right-to-left).
    /// When a combinator is reached, the iterator will return None, and
    /// next_sequence() may be called to continue to the next sequence.
    #[inline]
    pub fn iter(&self) -> SelectorIter<Impl> {
        SelectorIter {
            iter: self.iter_raw_match_order(),
            next_combinator: None,
        }
    }

    /// Same as `iter()`, but skips `RelativeSelectorAnchor` and its associated combinator.
    #[inline]
    pub fn iter_skip_relative_selector_anchor(&self) -> SelectorIter<Impl> {
        if cfg!(debug_assertions) {
            let mut selector_iter = self.iter_raw_parse_order_from(0);
            assert!(
                matches!(
                    selector_iter.next().unwrap(),
                    Component::RelativeSelectorAnchor
                ),
                "Relative selector does not start with RelativeSelectorAnchor"
            );
            assert!(
                selector_iter.next().unwrap().is_combinator(),
                "Relative combinator does not exist"
            );
        }

        SelectorIter {
            iter: self.0.slice()[..self.len() - 2].iter(),
            next_combinator: None,
        }
    }

    /// Whether this selector matches a featureless shadow host, with no combinators to the left, and
    /// optionally has a pseudo-element to the right.
    #[inline]
    pub fn matches_featureless_host_selector_or_pseudo_element(&self) -> FeaturelessHostMatches {
        let flags = self.flags();

        let mut result = FeaturelessHostMatches::empty();
        if flags.intersects(SelectorFlags::HAS_NON_FEATURELESS_COMPONENT) {
            return result;
        }
        if flags.intersects(SelectorFlags::HAS_HOST) {
            result.insert(FeaturelessHostMatches::FOR_HOST);
        }
        if flags.intersects(SelectorFlags::HAS_SCOPE) {
            result.insert(FeaturelessHostMatches::FOR_SCOPE);
        }
        result
    }

    /// Returns an iterator over this selector in matching order (right-to-left),
    /// skipping the rightmost |offset| Components.
    #[inline]
    pub fn iter_from(&self, offset: usize) -> SelectorIter<Impl> {
        let iter = self.0.slice()[offset..].iter();
        SelectorIter {
            iter,
            next_combinator: None,
        }
    }

    /// Returns the combinator at index `index` (zero-indexed from the right),
    /// or panics if the component is not a combinator.
    #[inline]
    pub fn combinator_at_match_order(&self, index: usize) -> Combinator {
        match self.0.slice()[index] {
            Component::Combinator(c) => c,
            ref other => panic!(
                "Not a combinator: {:?}, {:?}, index: {}",
                other, self, index
            ),
        }
    }

    /// Returns an iterator over the entire sequence of simple selectors and
    /// combinators, in matching order (from right to left).
    #[inline]
    pub fn iter_raw_match_order(&self) -> slice::Iter<Component<Impl>> {
        self.0.slice().iter()
    }

    /// Returns the combinator at index `index` (zero-indexed from the left),
    /// or panics if the component is not a combinator.
    #[inline]
    pub fn combinator_at_parse_order(&self, index: usize) -> Combinator {
        match self.0.slice()[self.len() - index - 1] {
            Component::Combinator(c) => c,
            ref other => panic!(
                "Not a combinator: {:?}, {:?}, index: {}",
                other, self, index
            ),
        }
    }

    /// Returns an iterator over the sequence of simple selectors and
    /// combinators, in parse order (from left to right), starting from
    /// `offset`.
    #[inline]
    pub fn iter_raw_parse_order_from(&self, offset: usize) -> Rev<slice::Iter<Component<Impl>>> {
        self.0.slice()[..self.len() - offset].iter().rev()
    }

    /// Creates a Selector from a vec of Components, specified in parse order. Used in tests.
    #[allow(dead_code)]
    pub(crate) fn from_vec(
        vec: Vec<Component<Impl>>,
        specificity: u32,
        flags: SelectorFlags,
    ) -> Self {
        let mut builder = SelectorBuilder::default();
        for component in vec.into_iter() {
            if let Some(combinator) = component.as_combinator() {
                builder.push_combinator(combinator);
            } else {
                builder.push_simple_selector(component);
            }
        }
        let spec = SpecificityAndFlags { specificity, flags };
        Selector(builder.build_with_specificity_and_flags(spec, ParseRelative::No))
    }

    #[inline]
    fn into_data(self) -> SelectorData<Impl> {
        self.0
    }

    pub fn replace_parent_selector(&self, parent: &SelectorList<Impl>) -> Self {
        let parent_specificity_and_flags =
            selector_list_specificity_and_flags(parent.slice().iter(), /* for_nesting_parent = */ true);

        let mut specificity = Specificity::from(self.specificity());
        let mut flags = self.flags() - SelectorFlags::HAS_PARENT;
        let forbidden_flags = SelectorFlags::forbidden_for_nesting();

        fn replace_parent_on_selector_list<Impl: SelectorImpl>(
            orig: &[Selector<Impl>],
            parent: &SelectorList<Impl>,
            specificity: &mut Specificity,
            flags: &mut SelectorFlags,
            propagate_specificity: bool,
            forbidden_flags: SelectorFlags,
        ) -> Option<SelectorList<Impl>> {
            if !orig.iter().any(|s| s.has_parent_selector()) {
                return None;
            }

            let result = SelectorList::from_iter(orig.iter().map(|s| {
                s.replace_parent_selector(parent)
            }));

            let result_specificity_and_flags =
                selector_list_specificity_and_flags(result.slice().iter(), /* for_nesting_parent = */ false);
            if propagate_specificity {
                *specificity += Specificity::from(
                    result_specificity_and_flags.specificity -
                        selector_list_specificity_and_flags(orig.iter(), /* for_nesting_parent = */ false).specificity,
                );
            }
            flags.insert(result_specificity_and_flags.flags - forbidden_flags);
            Some(result)
        }

        fn replace_parent_on_relative_selector_list<Impl: SelectorImpl>(
            orig: &[RelativeSelector<Impl>],
            parent: &SelectorList<Impl>,
            specificity: &mut Specificity,
            flags: &mut SelectorFlags,
            forbidden_flags: SelectorFlags,
        ) -> Vec<RelativeSelector<Impl>> {
            let mut any = false;

            let result = orig
                .iter()
                .map(|s| {
                    if !s.selector.has_parent_selector() {
                        return s.clone();
                    }
                    any = true;
                    RelativeSelector {
                        match_hint: s.match_hint,
                        selector: s.selector.replace_parent_selector(parent),
                    }
                })
                .collect();

            if !any {
                return result;
            }

            let result_specificity_and_flags =
                relative_selector_list_specificity_and_flags(&result, /* for_nesting_parent = */ false);
            flags.insert(result_specificity_and_flags .flags - forbidden_flags);
            *specificity += Specificity::from(
                result_specificity_and_flags.specificity -
                    relative_selector_list_specificity_and_flags(orig, /* for_nesting_parent = */ false).specificity,
            );
            result
        }

        fn replace_parent_on_selector<Impl: SelectorImpl>(
            orig: &Selector<Impl>,
            parent: &SelectorList<Impl>,
            specificity: &mut Specificity,
            flags: &mut SelectorFlags,
            forbidden_flags: SelectorFlags,
        ) -> Selector<Impl> {
            let new_selector = orig.replace_parent_selector(parent);
            *specificity += Specificity::from(new_selector.specificity() - orig.specificity());
            flags.insert(new_selector.flags() - forbidden_flags);
            new_selector
        }

        if !self.has_parent_selector() {
            return self.clone();
        }

        let iter = self.iter_raw_match_order().map(|component| {
            use self::Component::*;
            match *component {
                LocalName(..) |
                ID(..) |
                Class(..) |
                AttributeInNoNamespaceExists { .. } |
                AttributeInNoNamespace { .. } |
                AttributeOther(..) |
                ExplicitUniversalType |
                ExplicitAnyNamespace |
                ExplicitNoNamespace |
                DefaultNamespace(..) |
                Namespace(..) |
                Root |
                Empty |
                Scope |
                ImplicitScope |
                Nth(..) |
                NonTSPseudoClass(..) |
                PseudoElement(..) |
                Combinator(..) |
                Host(None) |
                Part(..) |
                Invalid(..) |
                RelativeSelectorAnchor => component.clone(),
                ParentSelector => {
                    specificity += Specificity::from(parent_specificity_and_flags.specificity);
                    flags.insert(parent_specificity_and_flags.flags - forbidden_flags);
                    Is(parent.clone())
                },
                Negation(ref selectors) => {
                    Negation(
                        replace_parent_on_selector_list(
                            selectors.slice(),
                            parent,
                            &mut specificity,
                            &mut flags,
                            /* propagate_specificity = */ true,
                            forbidden_flags,
                        )
                        .unwrap_or_else(|| selectors.clone()),
                    )
                },
                Is(ref selectors) => {
                    Is(replace_parent_on_selector_list(
                        selectors.slice(),
                        parent,
                        &mut specificity,
                        &mut flags,
                        /* propagate_specificity = */ true,
                        forbidden_flags,
                    )
                    .unwrap_or_else(|| selectors.clone()))
                },
                Where(ref selectors) => {
                    Where(
                        replace_parent_on_selector_list(
                            selectors.slice(),
                            parent,
                            &mut specificity,
                            &mut flags,
                            /* propagate_specificity = */ false,
                            forbidden_flags,
                        )
                        .unwrap_or_else(|| selectors.clone()),
                    )
                },
                Has(ref selectors) => Has(replace_parent_on_relative_selector_list(
                    selectors,
                    parent,
                    &mut specificity,
                    &mut flags,
                    forbidden_flags,
                )
                .into_boxed_slice()),

                Host(Some(ref selector)) => Host(Some(replace_parent_on_selector(
                    selector,
                    parent,
                    &mut specificity,
                    &mut flags,
                    forbidden_flags | SelectorFlags::HAS_NON_FEATURELESS_COMPONENT,
                ))),
                NthOf(ref data) => {
                    let selectors = replace_parent_on_selector_list(
                        data.selectors(),
                        parent,
                        &mut specificity,
                        &mut flags,
                        /* propagate_specificity = */ true,
                        forbidden_flags,
                    );
                    NthOf(match selectors {
                        Some(s) => {
                            NthOfSelectorData::new(data.nth_data(), s.slice().iter().cloned())
                        },
                        None => data.clone(),
                    })
                },
                Slotted(ref selector) => Slotted(replace_parent_on_selector(
                    selector,
                    parent,
                    &mut specificity,
                    &mut flags,
                    forbidden_flags,
                )),
            }
        });
        let mut items = UniqueArc::from_header_and_iter(Default::default(), iter);
        *items.header_mut() = SpecificityAndFlags {
            specificity: specificity.into(),
            flags,
        };
        Selector(items.shareable())
    }

    /// Returns count of simple selectors and combinators in the Selector.
    #[inline]
    pub fn len(&self) -> usize {
        self.0.len()
    }

    /// Returns the address on the heap of the ThinArc for memory reporting.
    pub fn thin_arc_heap_ptr(&self) -> *const ::std::os::raw::c_void {
        self.0.heap_ptr()
    }

    /// Traverse selector components inside `self`.
    ///
    /// Implementations of this method should call `SelectorVisitor` methods
    /// or other impls of `Visit` as appropriate based on the fields of `Self`.
    ///
    /// A return value of `false` indicates terminating the traversal.
    /// It should be propagated with an early return.
    /// On the contrary, `true` indicates that all fields of `self` have been traversed:
    ///
    /// ```rust,ignore
    /// if !visitor.visit_simple_selector(&self.some_simple_selector) {
    ///     return false;
    /// }
    /// if !self.some_component.visit(visitor) {
    ///     return false;
    /// }
    /// true
    /// ```
    pub fn visit<V>(&self, visitor: &mut V) -> bool
    where
        V: SelectorVisitor<Impl = Impl>,
    {
        let mut current = self.iter();
        let mut combinator = None;
        loop {
            if !visitor.visit_complex_selector(combinator) {
                return false;
            }

            for selector in &mut current {
                if !selector.visit(visitor) {
                    return false;
                }
            }

            combinator = current.next_sequence();
            if combinator.is_none() {
                break;
            }
        }

        true
    }

    /// Parse a selector, without any pseudo-element.
    #[inline]
    pub fn parse<'i, 't, P>(
        parser: &P,
        input: &mut CssParser<'i, 't>,
    ) -> Result<Self, ParseError<'i, P::Error>>
    where
        P: Parser<'i, Impl = Impl>,
    {
        parse_selector(
            parser,
            input,
            SelectorParsingState::empty(),
            ParseRelative::No,
        )
    }

    pub fn new_invalid(s: &str) -> Self {
        fn check_for_parent(input: &mut CssParser, has_parent: &mut bool) {
            while let Ok(t) = input.next() {
                match *t {
                    Token::Function(_) |
                    Token::ParenthesisBlock |
                    Token::CurlyBracketBlock |
                    Token::SquareBracketBlock => {
                        let _ = input.parse_nested_block(
                            |i| -> Result<(), ParseError<'_, BasicParseError>> {
                                check_for_parent(i, has_parent);
                                Ok(())
                            },
                        );
                    },
                    Token::Delim('&') => {
                        *has_parent = true;
                    },
                    _ => {},
                }
                if *has_parent {
                    break;
                }
            }
        }
        let mut has_parent = false;
        {
            let mut parser = cssparser::ParserInput::new(s);
            let mut parser = CssParser::new(&mut parser);
            check_for_parent(&mut parser, &mut has_parent);
        }
        Self(ThinArc::from_header_and_iter(
            SpecificityAndFlags {
                specificity: 0,
                flags: if has_parent {
                    SelectorFlags::HAS_PARENT
                } else {
                    SelectorFlags::empty()
                },
            },
            std::iter::once(Component::Invalid(Arc::new(String::from(s.trim())))),
        ))
    }

    /// Is the compound starting at the offset the subject compound, or referring to its pseudo-element?
    pub fn is_rightmost(&self, offset: usize) -> bool {
        // There can really be only one pseudo-element, and it's not really valid for anything else to
        // follow it.
        offset == 0 || matches!(self.combinator_at_match_order(offset - 1), Combinator::PseudoElement)
    }
}

#[derive(Clone)]
pub struct SelectorIter<'a, Impl: 'a + SelectorImpl> {
    iter: slice::Iter<'a, Component<Impl>>,
    next_combinator: Option<Combinator>,
}

impl<'a, Impl: 'a + SelectorImpl> SelectorIter<'a, Impl> {
    /// Prepares this iterator to point to the next sequence to the left,
    /// returning the combinator if the sequence was found.
    #[inline]
    pub fn next_sequence(&mut self) -> Option<Combinator> {
        self.next_combinator.take()
    }

    /// Whether this selector is a featureless selector matching the shadow host, with no
    /// combinators to the left.
    #[inline]
    pub(crate) fn is_featureless_host_selector(&mut self) -> FeaturelessHostMatches {
        if self.selector_length() == 0 {
            return FeaturelessHostMatches::empty();
        }
        let mut result = FeaturelessHostMatches::empty();
        while let Some(c) = self.next() {
            let component_matches = c.matches_featureless_host();
            if component_matches.is_empty() {
                return FeaturelessHostMatches::empty();
            }
            result.insert(component_matches);
        }
        if self.next_sequence().is_some() {
            FeaturelessHostMatches::empty()
        } else {
            result
        }
    }

    #[inline]
    pub(crate) fn matches_for_stateless_pseudo_element(&mut self) -> bool {
        let first = match self.next() {
            Some(c) => c,
            // Note that this is the common path that we keep inline: the
            // pseudo-element not having anything to its right.
            None => return true,
        };
        self.matches_for_stateless_pseudo_element_internal(first)
    }

    #[inline(never)]
    fn matches_for_stateless_pseudo_element_internal(&mut self, first: &Component<Impl>) -> bool {
        if !first.matches_for_stateless_pseudo_element() {
            return false;
        }
        for component in self {
            // The only other parser-allowed Components in this sequence are
            // state pseudo-classes, or one of the other things that can contain
            // them.
            if !component.matches_for_stateless_pseudo_element() {
                return false;
            }
        }
        true
    }

    /// Returns remaining count of the simple selectors and combinators in the Selector.
    #[inline]
    pub fn selector_length(&self) -> usize {
        self.iter.len()
    }
}

impl<'a, Impl: SelectorImpl> Iterator for SelectorIter<'a, Impl> {
    type Item = &'a Component<Impl>;

    #[inline]
    fn next(&mut self) -> Option<Self::Item> {
        debug_assert!(
            self.next_combinator.is_none(),
            "You should call next_sequence!"
        );
        match *self.iter.next()? {
            Component::Combinator(c) => {
                self.next_combinator = Some(c);
                None
            },
            ref x => Some(x),
        }
    }
}

impl<'a, Impl: SelectorImpl> fmt::Debug for SelectorIter<'a, Impl> {
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
        let iter = self.iter.clone().rev();
        for component in iter {
            component.to_css(f)?
        }
        Ok(())
    }
}

/// An iterator over all combinators in a selector. Does not traverse selectors within psuedoclasses.
struct CombinatorIter<'a, Impl: 'a + SelectorImpl>(SelectorIter<'a, Impl>);
impl<'a, Impl: 'a + SelectorImpl> CombinatorIter<'a, Impl> {
    fn new(inner: SelectorIter<'a, Impl>) -> Self {
        let mut result = CombinatorIter(inner);
        result.consume_non_combinators();
        result
    }

    fn consume_non_combinators(&mut self) {
        while self.0.next().is_some() {}
    }
}

impl<'a, Impl: SelectorImpl> Iterator for CombinatorIter<'a, Impl> {
    type Item = Combinator;
    fn next(&mut self) -> Option<Self::Item> {
        let result = self.0.next_sequence();
        self.consume_non_combinators();
        result
    }
}

/// An iterator over all simple selectors belonging to ancestors.
struct AncestorIter<'a, Impl: 'a + SelectorImpl>(SelectorIter<'a, Impl>);
impl<'a, Impl: 'a + SelectorImpl> AncestorIter<'a, Impl> {
    /// Creates an AncestorIter. The passed-in iterator is assumed to point to
    /// the beginning of the child sequence, which will be skipped.
    fn new(inner: SelectorIter<'a, Impl>) -> Self {
        let mut result = AncestorIter(inner);
        result.skip_until_ancestor();
        result
    }

    /// Skips a sequence of simple selectors and all subsequent sequences until
    /// a non-pseudo-element ancestor combinator is reached.
    fn skip_until_ancestor(&mut self) {
        loop {
            while self.0.next().is_some() {}
            // If this is ever changed to stop at the "pseudo-element"
            // combinator, we will need to fix the way we compute hashes for
            // revalidation selectors.
            if self.0.next_sequence().map_or(true, |x| {
                matches!(x, Combinator::Child | Combinator::Descendant)
            }) {
                break;
            }
        }
    }
}

impl<'a, Impl: SelectorImpl> Iterator for AncestorIter<'a, Impl> {
    type Item = &'a Component<Impl>;
    fn next(&mut self) -> Option<Self::Item> {
        // Grab the next simple selector in the sequence if available.
        let next = self.0.next();
        if next.is_some() {
            return next;
        }

        // See if there are more sequences. If so, skip any non-ancestor sequences.
        if let Some(combinator) = self.0.next_sequence() {
            if !matches!(combinator, Combinator::Child | Combinator::Descendant) {
                self.skip_until_ancestor();
            }
        }

        self.0.next()
    }
}

#[derive(Clone, Copy, Debug, Eq, PartialEq)]
#[cfg_attr(feature = "to_shmem", derive(ToShmem))]
pub enum Combinator {
    Child,        //  >
    Descendant,   // space
    NextSibling,  // +
    LaterSibling, // ~
    /// A dummy combinator we use to the left of pseudo-elements.
    ///
    /// It serializes as the empty string, and acts effectively as a child
    /// combinator in most cases.  If we ever actually start using a child
    /// combinator for this, we will need to fix up the way hashes are computed
    /// for revalidation selectors.
    PseudoElement,
    /// Another combinator used for ::slotted(), which represent the jump from
    /// a node to its assigned slot.
    SlotAssignment,
    /// Another combinator used for `::part()`, which represents the jump from
    /// the part to the containing shadow host.
    Part,
}

impl Combinator {
    /// Returns true if this combinator is a child or descendant combinator.
    #[inline]
    pub fn is_ancestor(&self) -> bool {
        matches!(
            *self,
            Combinator::Child |
                Combinator::Descendant |
                Combinator::PseudoElement |
                Combinator::SlotAssignment
        )
    }

    /// Returns true if this combinator is a pseudo-element combinator.
    #[inline]
    pub fn is_pseudo_element(&self) -> bool {
        matches!(*self, Combinator::PseudoElement)
    }

    /// Returns true if this combinator is a next- or later-sibling combinator.
    #[inline]
    pub fn is_sibling(&self) -> bool {
        matches!(*self, Combinator::NextSibling | Combinator::LaterSibling)
    }
}

/// An enum for the different types of :nth- pseudoclasses
#[derive(Copy, Clone, Eq, PartialEq)]
#[cfg_attr(feature = "to_shmem", derive(ToShmem))]
#[cfg_attr(feature = "to_shmem", shmem(no_bounds))]
pub enum NthType {
    Child,
    LastChild,
    OnlyChild,
    OfType,
    LastOfType,
    OnlyOfType,
}

impl NthType {
    pub fn is_only(self) -> bool {
        self == Self::OnlyChild || self == Self::OnlyOfType
    }

    pub fn is_of_type(self) -> bool {
        self == Self::OfType || self == Self::LastOfType || self == Self::OnlyOfType
    }

    pub fn is_from_end(self) -> bool {
        self == Self::LastChild || self == Self::LastOfType
    }
}

/// The properties that comprise an :nth- pseudoclass as of Selectors 3 (e.g.,
/// nth-child(An+B)).
/// https://www.w3.org/TR/selectors-3/#nth-child-pseudo
#[derive(Copy, Clone, Eq, PartialEq)]
#[cfg_attr(feature = "to_shmem", derive(ToShmem))]
#[cfg_attr(feature = "to_shmem", shmem(no_bounds))]
pub struct NthSelectorData {
    pub ty: NthType,
    pub is_function: bool,
    pub a: i32,
    pub b: i32,
}

impl NthSelectorData {
    /// Returns selector data for :only-{child,of-type}
    #[inline]
    pub const fn only(of_type: bool) -> Self {
        Self {
            ty: if of_type {
                NthType::OnlyOfType
            } else {
                NthType::OnlyChild
            },
            is_function: false,
            a: 0,
            b: 1,
        }
    }

    /// Returns selector data for :first-{child,of-type}
    #[inline]
    pub const fn first(of_type: bool) -> Self {
        Self {
            ty: if of_type {
                NthType::OfType
            } else {
                NthType::Child
            },
            is_function: false,
            a: 0,
            b: 1,
        }
    }

    /// Returns selector data for :last-{child,of-type}
    #[inline]
    pub const fn last(of_type: bool) -> Self {
        Self {
            ty: if of_type {
                NthType::LastOfType
            } else {
                NthType::LastChild
            },
            is_function: false,
            a: 0,
            b: 1,
        }
    }

    /// Returns true if this is an edge selector that is not `:*-of-type``
    #[inline]
    pub fn is_simple_edge(&self) -> bool {
        self.a == 0 && self.b == 1 && !self.ty.is_of_type() && !self.ty.is_only()
    }

    /// Writes the beginning of the selector.
    #[inline]
    fn write_start<W: fmt::Write>(&self, dest: &mut W) -> fmt::Result {
        dest.write_str(match self.ty {
            NthType::Child if self.is_function => ":nth-child(",
            NthType::Child => ":first-child",
            NthType::LastChild if self.is_function => ":nth-last-child(",
            NthType::LastChild => ":last-child",
            NthType::OfType if self.is_function => ":nth-of-type(",
            NthType::OfType => ":first-of-type",
            NthType::LastOfType if self.is_function => ":nth-last-of-type(",
            NthType::LastOfType => ":last-of-type",
            NthType::OnlyChild => ":only-child",
            NthType::OnlyOfType => ":only-of-type",
        })
    }

    /// Serialize <an+b> (part of the CSS Syntax spec, but currently only used here).
    /// <https://drafts.csswg.org/css-syntax-3/#serialize-an-anb-value>
    #[inline]
    fn write_affine<W: fmt::Write>(&self, dest: &mut W) -> fmt::Result {
        match (self.a, self.b) {
            (0, 0) => dest.write_char('0'),

            (1, 0) => dest.write_char('n'),
            (-1, 0) => dest.write_str("-n"),
            (_, 0) => write!(dest, "{}n", self.a),

            (0, _) => write!(dest, "{}", self.b),
            (1, _) => write!(dest, "n{:+}", self.b),
            (-1, _) => write!(dest, "-n{:+}", self.b),
            (_, _) => write!(dest, "{}n{:+}", self.a, self.b),
        }
    }
}

/// The properties that comprise an :nth- pseudoclass as of Selectors 4 (e.g.,
/// nth-child(An+B [of S]?)).
/// https://www.w3.org/TR/selectors-4/#nth-child-pseudo
#[derive(Clone, Eq, PartialEq)]
#[cfg_attr(feature = "to_shmem", derive(ToShmem))]
#[cfg_attr(feature = "to_shmem", shmem(no_bounds))]
pub struct NthOfSelectorData<Impl: SelectorImpl>(
    #[cfg_attr(feature = "to_shmem", shmem(field_bound))] ThinArc<NthSelectorData, Selector<Impl>>,
);

impl<Impl: SelectorImpl> NthOfSelectorData<Impl> {
    /// Returns selector data for :nth-{,last-}{child,of-type}(An+B [of S])
    #[inline]
    pub fn new<I>(nth_data: &NthSelectorData, selectors: I) -> Self
    where
        I: Iterator<Item = Selector<Impl>> + ExactSizeIterator,
    {
        Self(ThinArc::from_header_and_iter(*nth_data, selectors))
    }

    /// Returns the An+B part of the selector
    #[inline]
    pub fn nth_data(&self) -> &NthSelectorData {
        &self.0.header
    }

    /// Returns the selector list part of the selector
    #[inline]
    pub fn selectors(&self) -> &[Selector<Impl>] {
        self.0.slice()
    }
}

/// Flag indicating where a given relative selector's match would be contained.
#[derive(Clone, Copy, Eq, PartialEq)]
#[cfg_attr(feature = "to_shmem", derive(ToShmem))]
pub enum RelativeSelectorMatchHint {
    /// Within this element's subtree.
    InSubtree,
    /// Within this element's direct children.
    InChild,
    /// This element's next sibling.
    InNextSibling,
    /// Within this element's next sibling's subtree.
    InNextSiblingSubtree,
    /// Within this element's subsequent siblings.
    InSibling,
    /// Across this element's subsequent siblings and their subtrees.
    InSiblingSubtree,
}

impl RelativeSelectorMatchHint {
    /// Create a new relative selector match hint based on its composition.
    pub fn new(
        relative_combinator: Combinator,
        has_child_or_descendants: bool,
        has_adjacent_or_next_siblings: bool,
    ) -> Self {
        match relative_combinator {
            Combinator::Descendant => RelativeSelectorMatchHint::InSubtree,
            Combinator::Child => {
                if !has_child_or_descendants {
                    RelativeSelectorMatchHint::InChild
                } else {
                    // Technically, for any composition that consists of child combinators only,
                    // the search space is depth-constrained, but it's probably not worth optimizing for.
                    RelativeSelectorMatchHint::InSubtree
                }
            },
            Combinator::NextSibling => {
                if !has_child_or_descendants && !has_adjacent_or_next_siblings {
                    RelativeSelectorMatchHint::InNextSibling
                } else if !has_child_or_descendants && has_adjacent_or_next_siblings {
                    RelativeSelectorMatchHint::InSibling
                } else if has_child_or_descendants && !has_adjacent_or_next_siblings {
                    // Match won't cross multiple siblings.
                    RelativeSelectorMatchHint::InNextSiblingSubtree
                } else {
                    RelativeSelectorMatchHint::InSiblingSubtree
                }
            },
            Combinator::LaterSibling => {
                if !has_child_or_descendants {
                    RelativeSelectorMatchHint::InSibling
                } else {
                    // Even if the match may not cross multiple siblings, we have to look until
                    // we find a match anyway.
                    RelativeSelectorMatchHint::InSiblingSubtree
                }
            },
            Combinator::Part | Combinator::PseudoElement | Combinator::SlotAssignment => {
                debug_assert!(false, "Unexpected relative combinator");
                RelativeSelectorMatchHint::InSubtree
            },
        }
    }

    /// Is the match traversal direction towards the descendant of this element (As opposed to siblings)?
    pub fn is_descendant_direction(&self) -> bool {
        matches!(*self, Self::InChild | Self::InSubtree)
    }

    /// Is the match traversal terminated at the next sibling?
    pub fn is_next_sibling(&self) -> bool {
        matches!(*self, Self::InNextSibling | Self::InNextSiblingSubtree)
    }

    /// Does the match involve matching the subtree?
    pub fn is_subtree(&self) -> bool {
        matches!(
            *self,
            Self::InSubtree | Self::InSiblingSubtree | Self::InNextSiblingSubtree
        )
    }
}

/// Count of combinators in a given relative selector, not traversing selectors of pseudoclasses.
#[derive(Clone, Copy)]
pub struct RelativeSelectorCombinatorCount {
    relative_combinator: Combinator,
    pub child_or_descendants: usize,
    pub adjacent_or_next_siblings: usize,
}

impl RelativeSelectorCombinatorCount {
    /// Create a new relative selector combinator count from a given relative selector.
    pub fn new<Impl: SelectorImpl>(relative_selector: &RelativeSelector<Impl>) -> Self {
        let mut result = RelativeSelectorCombinatorCount {
            relative_combinator: relative_selector.selector.combinator_at_parse_order(1),
            child_or_descendants: 0,
            adjacent_or_next_siblings: 0,
        };

--> --------------------

--> maximum size reached

--> --------------------