Adding upstream version 124.0.1.upstream/124.0.1

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

18 files changed, 8129 insertions, 0 deletions

diff --git a/servo/components/selectors/CHANGES.md b/servo/components/selectors/CHANGES.md
new file mode 100644
index 0000000000..b1e9511dca
--- /dev/null
+++ b/servo/components/selectors/CHANGES.md
@@ -0,0 +1 @@
+- `parser.rs` no longer wraps values in quotes (`"..."`) but expects their `to_css` impl to already wrap it ([Gecko Bug 1854809](https://bugzilla.mozilla.org/show_bug.cgi?id=1854809))
diff --git a/servo/components/selectors/Cargo.toml b/servo/components/selectors/Cargo.toml
new file mode 100644
index 0000000000..88360d7dd2
--- /dev/null
+++ b/servo/components/selectors/Cargo.toml
@@ -0,0 +1,35 @@
+[package]
+name = "selectors"
+version = "0.22.0"
+authors = ["The Servo Project Developers"]
+documentation = "https://docs.rs/selectors/"
+description = "CSS Selectors matching for Rust"
+repository = "https://github.com/servo/servo"
+readme = "README.md"
+keywords = ["css", "selectors"]
+license = "MPL-2.0"
+build = "build.rs"
+
+[lib]
+name = "selectors"
+path = "lib.rs"
+
+[features]
+bench = []
+
+[dependencies]
+bitflags = "2"
+cssparser = "0.33"
+derive_more = { version = "0.99", default-features = false, features = ["add", "add_assign"] }
+fxhash = "0.2"
+log = "0.4"
+phf = "0.11"
+precomputed-hash = "0.1"
+servo_arc = { version = "0.1", path = "../servo_arc" }
+smallvec = "1.0"
+to_shmem = { path = "../to_shmem" }
+to_shmem_derive = { path = "../to_shmem_derive" }
+new_debug_unreachable = "1"
+
+[build-dependencies]
+phf_codegen = "0.11"
diff --git a/servo/components/selectors/README.md b/servo/components/selectors/README.md
new file mode 100644
index 0000000000..dac4a7ff91
--- /dev/null
+++ b/servo/components/selectors/README.md
@@ -0,0 +1,25 @@
+rust-selectors
+==============
+
+* [![Build Status](https://travis-ci.com/servo/rust-selectors.svg?branch=master)](
+  https://travis-ci.com/servo/rust-selectors)
+* [Documentation](https://docs.rs/selectors/)
+* [crates.io](https://crates.io/crates/selectors)
+
+CSS Selectors library for Rust.
+Includes parsing and serilization of selectors,
+as well as matching against a generic tree of elements.
+Pseudo-elements and most pseudo-classes are generic as well.
+
+**Warning:** breaking changes are made to this library fairly frequently
+(13 times in 2016, for example).
+However you can use this crate without updating it that often,
+old versions stay available on crates.io and Cargo will only automatically update
+to versions that are numbered as compatible.
+
+To see how to use this library with your own tree representation,
+see [Kuchiki’s `src/select.rs`](https://github.com/kuchiki-rs/kuchiki/blob/master/src/select.rs).
+(Note however that Kuchiki is not always up to date with the latest rust-selectors version,
+so that code may need to be tweaked.)
+If you don’t already have a tree data structure,
+consider using [Kuchiki](https://github.com/kuchiki-rs/kuchiki) itself.
diff --git a/servo/components/selectors/attr.rs b/servo/components/selectors/attr.rs
new file mode 100644
index 0000000000..fee2962237
--- /dev/null
+++ b/servo/components/selectors/attr.rs
@@ -0,0 +1,183 @@
+/* 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::parser::SelectorImpl;
+use cssparser::ToCss;
+use std::fmt;
+
+#[derive(Clone, Eq, PartialEq, ToShmem)]
+#[shmem(no_bounds)]
+pub struct AttrSelectorWithOptionalNamespace<Impl: SelectorImpl> {
+    #[shmem(field_bound)]
+    pub namespace: Option<NamespaceConstraint<(Impl::NamespacePrefix, Impl::NamespaceUrl)>>,
+    #[shmem(field_bound)]
+    pub local_name: Impl::LocalName,
+    pub local_name_lower: Impl::LocalName,
+    #[shmem(field_bound)]
+    pub operation: ParsedAttrSelectorOperation<Impl::AttrValue>,
+}
+
+impl<Impl: SelectorImpl> AttrSelectorWithOptionalNamespace<Impl> {
+    pub fn namespace(&self) -> Option<NamespaceConstraint<&Impl::NamespaceUrl>> {
+        self.namespace.as_ref().map(|ns| match ns {
+            NamespaceConstraint::Any => NamespaceConstraint::Any,
+            NamespaceConstraint::Specific((_, ref url)) => NamespaceConstraint::Specific(url),
+        })
+    }
+}
+
+#[derive(Clone, Eq, PartialEq, ToShmem)]
+pub enum NamespaceConstraint<NamespaceUrl> {
+    Any,
+
+    /// Empty string for no namespace
+    Specific(NamespaceUrl),
+}
+
+#[derive(Clone, Eq, PartialEq, ToShmem)]
+pub enum ParsedAttrSelectorOperation<AttrValue> {
+    Exists,
+    WithValue {
+        operator: AttrSelectorOperator,
+        case_sensitivity: ParsedCaseSensitivity,
+        value: AttrValue,
+    },
+}
+
+#[derive(Clone, Eq, PartialEq)]
+pub enum AttrSelectorOperation<AttrValue> {
+    Exists,
+    WithValue {
+        operator: AttrSelectorOperator,
+        case_sensitivity: CaseSensitivity,
+        value: AttrValue,
+    },
+}
+
+impl<AttrValue> AttrSelectorOperation<AttrValue> {
+    pub fn eval_str(&self, element_attr_value: &str) -> bool
+    where
+        AttrValue: AsRef<str>,
+    {
+        match *self {
+            AttrSelectorOperation::Exists => true,
+            AttrSelectorOperation::WithValue {
+                operator,
+                case_sensitivity,
+                ref value,
+            } => operator.eval_str(element_attr_value, value.as_ref(), case_sensitivity),
+        }
+    }
+}
+
+#[derive(Clone, Copy, Eq, PartialEq, ToShmem)]
+pub enum AttrSelectorOperator {
+    Equal,
+    Includes,
+    DashMatch,
+    Prefix,
+    Substring,
+    Suffix,
+}
+
+impl ToCss for AttrSelectorOperator {
+    fn to_css<W>(&self, dest: &mut W) -> fmt::Result
+    where
+        W: fmt::Write,
+    {
+        // https://drafts.csswg.org/cssom/#serializing-selectors
+        // See "attribute selector".
+        dest.write_str(match *self {
+            AttrSelectorOperator::Equal => "=",
+            AttrSelectorOperator::Includes => "~=",
+            AttrSelectorOperator::DashMatch => "|=",
+            AttrSelectorOperator::Prefix => "^=",
+            AttrSelectorOperator::Substring => "*=",
+            AttrSelectorOperator::Suffix => "$=",
+        })
+    }
+}
+
+impl AttrSelectorOperator {
+    pub fn eval_str(
+        self,
+        element_attr_value: &str,
+        attr_selector_value: &str,
+        case_sensitivity: CaseSensitivity,
+    ) -> bool {
+        let e = element_attr_value.as_bytes();
+        let s = attr_selector_value.as_bytes();
+        let case = case_sensitivity;
+        match self {
+            AttrSelectorOperator::Equal => case.eq(e, s),
+            AttrSelectorOperator::Prefix => e.len() >= s.len() && case.eq(&e[..s.len()], s),
+            AttrSelectorOperator::Suffix => {
+                e.len() >= s.len() && case.eq(&e[(e.len() - s.len())..], s)
+            },
+            AttrSelectorOperator::Substring => {
+                case.contains(element_attr_value, attr_selector_value)
+            },
+            AttrSelectorOperator::Includes => element_attr_value
+                .split(SELECTOR_WHITESPACE)
+                .any(|part| case.eq(part.as_bytes(), s)),
+            AttrSelectorOperator::DashMatch => {
+                case.eq(e, s) || (e.get(s.len()) == Some(&b'-') && case.eq(&e[..s.len()], s))
+            },
+        }
+    }
+}
+
+/// The definition of whitespace per CSS Selectors Level 3 § 4.
+pub static SELECTOR_WHITESPACE: &[char] = &[' ', '\t', '\n', '\r', '\x0C'];
+
+#[derive(Clone, Copy, Debug, Eq, PartialEq, ToShmem)]
+pub enum ParsedCaseSensitivity {
+    /// 's' was specified.
+    ExplicitCaseSensitive,
+    /// 'i' was specified.
+    AsciiCaseInsensitive,
+    /// No flags were specified and HTML says this is a case-sensitive attribute.
+    CaseSensitive,
+    /// No flags were specified and HTML says this is a case-insensitive attribute.
+    AsciiCaseInsensitiveIfInHtmlElementInHtmlDocument,
+}
+
+#[derive(Clone, Copy, Debug, Eq, PartialEq)]
+pub enum CaseSensitivity {
+    CaseSensitive,
+    AsciiCaseInsensitive,
+}
+
+impl CaseSensitivity {
+    pub fn eq(self, a: &[u8], b: &[u8]) -> bool {
+        match self {
+            CaseSensitivity::CaseSensitive => a == b,
+            CaseSensitivity::AsciiCaseInsensitive => a.eq_ignore_ascii_case(b),
+        }
+    }
+
+    pub fn contains(self, haystack: &str, needle: &str) -> bool {
+        match self {
+            CaseSensitivity::CaseSensitive => haystack.contains(needle),
+            CaseSensitivity::AsciiCaseInsensitive => {
+                if let Some((&n_first_byte, n_rest)) = needle.as_bytes().split_first() {
+                    haystack.bytes().enumerate().any(|(i, byte)| {
+                        if !byte.eq_ignore_ascii_case(&n_first_byte) {
+                            return false;
+                        }
+                        let after_this_byte = &haystack.as_bytes()[i + 1..];
+                        match after_this_byte.get(..n_rest.len()) {
+                            None => false,
+                            Some(haystack_slice) => haystack_slice.eq_ignore_ascii_case(n_rest),
+                        }
+                    })
+                } else {
+                    // any_str.contains("") == true,
+                    // though these cases should be handled with *NeverMatches and never go here.
+                    true
+                }
+            },
+        }
+    }
+}
diff --git a/servo/components/selectors/bloom.rs b/servo/components/selectors/bloom.rs
new file mode 100644
index 0000000000..98461d1ba2
--- /dev/null
+++ b/servo/components/selectors/bloom.rs
@@ -0,0 +1,422 @@
+/* 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/. */
+
+//! Counting and non-counting Bloom filters tuned for use as ancestor filters
+//! for selector matching.
+
+use std::fmt::{self, Debug};
+
+// The top 8 bits of the 32-bit hash value are not used by the bloom filter.
+// Consumers may rely on this to pack hashes more efficiently.
+pub const BLOOM_HASH_MASK: u32 = 0x00ffffff;
+const KEY_SIZE: usize = 12;
+
+const ARRAY_SIZE: usize = 1 << KEY_SIZE;
+const KEY_MASK: u32 = (1 << KEY_SIZE) - 1;
+
+/// A counting Bloom filter with 8-bit counters.
+pub type BloomFilter = CountingBloomFilter<BloomStorageU8>;
+
+/// A counting Bloom filter with parameterized storage to handle
+/// counters of different sizes.  For now we assume that having two hash
+/// functions is enough, but we may revisit that decision later.
+///
+/// The filter uses an array with 2**KeySize entries.
+///
+/// Assuming a well-distributed hash function, a Bloom filter with
+/// array size M containing N elements and
+/// using k hash function has expected false positive rate exactly
+///
+/// $  (1 - (1 - 1/M)^{kN})^k  $
+///
+/// because each array slot has a
+///
+/// $  (1 - 1/M)^{kN}  $
+///
+/// chance of being 0, and the expected false positive rate is the
+/// probability that all of the k hash functions will hit a nonzero
+/// slot.
+///
+/// For reasonable assumptions (M large, kN large, which should both
+/// hold if we're worried about false positives) about M and kN this
+/// becomes approximately
+///
+/// $$  (1 - \exp(-kN/M))^k   $$
+///
+/// For our special case of k == 2, that's $(1 - \exp(-2N/M))^2$,
+/// or in other words
+///
+/// $$    N/M = -0.5 * \ln(1 - \sqrt(r))   $$
+///
+/// where r is the false positive rate.  This can be used to compute
+/// the desired KeySize for a given load N and false positive rate r.
+///
+/// If N/M is assumed small, then the false positive rate can
+/// further be approximated as 4*N^2/M^2.  So increasing KeySize by
+/// 1, which doubles M, reduces the false positive rate by about a
+/// factor of 4, and a false positive rate of 1% corresponds to
+/// about M/N == 20.
+///
+/// What this means in practice is that for a few hundred keys using a
+/// KeySize of 12 gives false positive rates on the order of 0.25-4%.
+///
+/// Similarly, using a KeySize of 10 would lead to a 4% false
+/// positive rate for N == 100 and to quite bad false positive
+/// rates for larger N.
+#[derive(Clone, Default)]
+pub struct CountingBloomFilter<S>
+where
+    S: BloomStorage,
+{
+    storage: S,
+}
+
+impl<S> CountingBloomFilter<S>
+where
+    S: BloomStorage,
+{
+    /// Creates a new bloom filter.
+    #[inline]
+    pub fn new() -> Self {
+        Default::default()
+    }
+
+    #[inline]
+    pub fn clear(&mut self) {
+        self.storage = Default::default();
+    }
+
+    // Slow linear accessor to make sure the bloom filter is zeroed. This should
+    // never be used in release builds.
+    #[cfg(debug_assertions)]
+    pub fn is_zeroed(&self) -> bool {
+        self.storage.is_zeroed()
+    }
+
+    #[cfg(not(debug_assertions))]
+    pub fn is_zeroed(&self) -> bool {
+        unreachable!()
+    }
+
+    /// Inserts an item with a particular hash into the bloom filter.
+    #[inline]
+    pub fn insert_hash(&mut self, hash: u32) {
+        self.storage.adjust_first_slot(hash, true);
+        self.storage.adjust_second_slot(hash, true);
+    }
+
+    /// Removes an item with a particular hash from the bloom filter.
+    #[inline]
+    pub fn remove_hash(&mut self, hash: u32) {
+        self.storage.adjust_first_slot(hash, false);
+        self.storage.adjust_second_slot(hash, false);
+    }
+
+    /// Check whether the filter might contain an item with the given hash.
+    /// This can sometimes return true even if the item is not in the filter,
+    /// but will never return false for items that are actually in the filter.
+    #[inline]
+    pub fn might_contain_hash(&self, hash: u32) -> bool {
+        !self.storage.first_slot_is_empty(hash) && !self.storage.second_slot_is_empty(hash)
+    }
+}
+
+impl<S> Debug for CountingBloomFilter<S>
+where
+    S: BloomStorage,
+{
+    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
+        let mut slots_used = 0;
+        for i in 0..ARRAY_SIZE {
+            if !self.storage.slot_is_empty(i) {
+                slots_used += 1;
+            }
+        }
+        write!(f, "BloomFilter({}/{})", slots_used, ARRAY_SIZE)
+    }
+}
+
+pub trait BloomStorage: Clone + Default {
+    fn slot_is_empty(&self, index: usize) -> bool;
+    fn adjust_slot(&mut self, index: usize, increment: bool);
+    fn is_zeroed(&self) -> bool;
+
+    #[inline]
+    fn first_slot_is_empty(&self, hash: u32) -> bool {
+        self.slot_is_empty(Self::first_slot_index(hash))
+    }
+
+    #[inline]
+    fn second_slot_is_empty(&self, hash: u32) -> bool {
+        self.slot_is_empty(Self::second_slot_index(hash))
+    }
+
+    #[inline]
+    fn adjust_first_slot(&mut self, hash: u32, increment: bool) {
+        self.adjust_slot(Self::first_slot_index(hash), increment)
+    }
+
+    #[inline]
+    fn adjust_second_slot(&mut self, hash: u32, increment: bool) {
+        self.adjust_slot(Self::second_slot_index(hash), increment)
+    }
+
+    #[inline]
+    fn first_slot_index(hash: u32) -> usize {
+        hash1(hash) as usize
+    }
+
+    #[inline]
+    fn second_slot_index(hash: u32) -> usize {
+        hash2(hash) as usize
+    }
+}
+
+/// Storage class for a CountingBloomFilter that has 8-bit counters.
+pub struct BloomStorageU8 {
+    counters: [u8; ARRAY_SIZE],
+}
+
+impl BloomStorage for BloomStorageU8 {
+    #[inline]
+    fn adjust_slot(&mut self, index: usize, increment: bool) {
+        let slot = &mut self.counters[index];
+        if *slot != 0xff {
+            // full
+            if increment {
+                *slot += 1;
+            } else {
+                *slot -= 1;
+            }
+        }
+    }
+
+    #[inline]
+    fn slot_is_empty(&self, index: usize) -> bool {
+        self.counters[index] == 0
+    }
+
+    #[inline]
+    fn is_zeroed(&self) -> bool {
+        self.counters.iter().all(|x| *x == 0)
+    }
+}
+
+impl Default for BloomStorageU8 {
+    fn default() -> Self {
+        BloomStorageU8 {
+            counters: [0; ARRAY_SIZE],
+        }
+    }
+}
+
+impl Clone for BloomStorageU8 {
+    fn clone(&self) -> Self {
+        BloomStorageU8 {
+            counters: self.counters,
+        }
+    }
+}
+
+/// Storage class for a CountingBloomFilter that has 1-bit counters.
+pub struct BloomStorageBool {
+    counters: [u8; ARRAY_SIZE / 8],
+}
+
+impl BloomStorage for BloomStorageBool {
+    #[inline]
+    fn adjust_slot(&mut self, index: usize, increment: bool) {
+        let bit = 1 << (index % 8);
+        let byte = &mut self.counters[index / 8];
+
+        // Since we have only one bit for storage, decrementing it
+        // should never do anything.  Assert against an accidental
+        // decrementing of a bit that was never set.
+        assert!(
+            increment || (*byte & bit) != 0,
+            "should not decrement if slot is already false"
+        );
+
+        if increment {
+            *byte |= bit;
+        }
+    }
+
+    #[inline]
+    fn slot_is_empty(&self, index: usize) -> bool {
+        let bit = 1 << (index % 8);
+        (self.counters[index / 8] & bit) == 0
+    }
+
+    #[inline]
+    fn is_zeroed(&self) -> bool {
+        self.counters.iter().all(|x| *x == 0)
+    }
+}
+
+impl Default for BloomStorageBool {
+    fn default() -> Self {
+        BloomStorageBool {
+            counters: [0; ARRAY_SIZE / 8],
+        }
+    }
+}
+
+impl Clone for BloomStorageBool {
+    fn clone(&self) -> Self {
+        BloomStorageBool {
+            counters: self.counters,
+        }
+    }
+}
+
+#[inline]
+fn hash1(hash: u32) -> u32 {
+    hash & KEY_MASK
+}
+
+#[inline]
+fn hash2(hash: u32) -> u32 {
+    (hash >> KEY_SIZE) & KEY_MASK
+}
+
+#[test]
+fn create_and_insert_some_stuff() {
+    use fxhash::FxHasher;
+    use std::hash::{Hash, Hasher};
+    use std::mem::transmute;
+
+    fn hash_as_str(i: usize) -> u32 {
+        let mut hasher = FxHasher::default();
+        let s = i.to_string();
+        s.hash(&mut hasher);
+        let hash: u64 = hasher.finish();
+        (hash >> 32) as u32 ^ (hash as u32)
+    }
+
+    let mut bf = BloomFilter::new();
+
+    // Statically assert that ARRAY_SIZE is a multiple of 8, which
+    // BloomStorageBool relies on.
+    unsafe {
+        transmute::<[u8; ARRAY_SIZE % 8], [u8; 0]>([]);
+    }
+
+    for i in 0_usize..1000 {
+        bf.insert_hash(hash_as_str(i));
+    }
+
+    for i in 0_usize..1000 {
+        assert!(bf.might_contain_hash(hash_as_str(i)));
+    }
+
+    let false_positives = (1001_usize..2000)
+        .filter(|i| bf.might_contain_hash(hash_as_str(*i)))
+        .count();
+
+    assert!(false_positives < 190, "{} is not < 190", false_positives); // 19%.
+
+    for i in 0_usize..100 {
+        bf.remove_hash(hash_as_str(i));
+    }
+
+    for i in 100_usize..1000 {
+        assert!(bf.might_contain_hash(hash_as_str(i)));
+    }
+
+    let false_positives = (0_usize..100)
+        .filter(|i| bf.might_contain_hash(hash_as_str(*i)))
+        .count();
+
+    assert!(false_positives < 20, "{} is not < 20", false_positives); // 20%.
+
+    bf.clear();
+
+    for i in 0_usize..2000 {
+        assert!(!bf.might_contain_hash(hash_as_str(i)));
+    }
+}
+
+#[cfg(feature = "bench")]
+#[cfg(test)]
+mod bench {
+    extern crate test;
+    use super::BloomFilter;
+
+    #[derive(Default)]
+    struct HashGenerator(u32);
+
+    impl HashGenerator {
+        fn next(&mut self) -> u32 {
+            // Each hash is split into two twelve-bit segments, which are used
+            // as an index into an array. We increment each by 64 so that we
+            // hit the next cache line, and then another 1 so that our wrapping
+            // behavior leads us to different entries each time.
+            //
+            // Trying to simulate cold caches is rather difficult with the cargo
+            // benchmarking setup, so it may all be moot depending on the number
+            // of iterations that end up being run. But we might as well.
+            self.0 += (65) + (65 << super::KEY_SIZE);
+            self.0
+        }
+    }
+
+    #[bench]
+    fn create_insert_1000_remove_100_lookup_100(b: &mut test::Bencher) {
+        b.iter(|| {
+            let mut gen1 = HashGenerator::default();
+            let mut gen2 = HashGenerator::default();
+            let mut bf = BloomFilter::new();
+            for _ in 0_usize..1000 {
+                bf.insert_hash(gen1.next());
+            }
+            for _ in 0_usize..100 {
+                bf.remove_hash(gen2.next());
+            }
+            for _ in 100_usize..200 {
+                test::black_box(bf.might_contain_hash(gen2.next()));
+            }
+        });
+    }
+
+    #[bench]
+    fn might_contain_10(b: &mut test::Bencher) {
+        let bf = BloomFilter::new();
+        let mut gen = HashGenerator::default();
+        b.iter(|| {
+            for _ in 0..10 {
+                test::black_box(bf.might_contain_hash(gen.next()));
+            }
+        });
+    }
+
+    #[bench]
+    fn clear(b: &mut test::Bencher) {
+        let mut bf = Box::new(BloomFilter::new());
+        b.iter(|| test::black_box(&mut bf).clear());
+    }
+
+    #[bench]
+    fn insert_10(b: &mut test::Bencher) {
+        let mut bf = BloomFilter::new();
+        let mut gen = HashGenerator::default();
+        b.iter(|| {
+            for _ in 0..10 {
+                test::black_box(bf.insert_hash(gen.next()));
+            }
+        });
+    }
+
+    #[bench]
+    fn remove_10(b: &mut test::Bencher) {
+        let mut bf = BloomFilter::new();
+        let mut gen = HashGenerator::default();
+        // Note: this will underflow, and that's ok.
+        b.iter(|| {
+            for _ in 0..10 {
+                bf.remove_hash(gen.next())
+            }
+        });
+    }
+}
diff --git a/servo/components/selectors/build.rs b/servo/components/selectors/build.rs
new file mode 100644
index 0000000000..c5c3803991
--- /dev/null
+++ b/servo/components/selectors/build.rs
@@ -0,0 +1,77 @@
+/* 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/. */
+
+extern crate phf_codegen;
+
+use std::env;
+use std::fs::File;
+use std::io::{BufWriter, Write};
+use std::path::Path;
+
+fn main() {
+    let path = Path::new(&env::var_os("OUT_DIR").unwrap())
+        .join("ascii_case_insensitive_html_attributes.rs");
+    let mut file = BufWriter::new(File::create(&path).unwrap());
+
+    let mut set = phf_codegen::Set::new();
+    for name in ASCII_CASE_INSENSITIVE_HTML_ATTRIBUTES.split_whitespace() {
+        set.entry(name);
+    }
+    write!(
+        &mut file,
+        "{{ static SET: ::phf::Set<&'static str> = {}; &SET }}",
+        set.build(),
+    )
+    .unwrap();
+}
+
+/// <https://html.spec.whatwg.org/multipage/#selectors>
+static ASCII_CASE_INSENSITIVE_HTML_ATTRIBUTES: &str = r#"
+    accept
+    accept-charset
+    align
+    alink
+    axis
+    bgcolor
+    charset
+    checked
+    clear
+    codetype
+    color
+    compact
+    declare
+    defer
+    dir
+    direction
+    disabled
+    enctype
+    face
+    frame
+    hreflang
+    http-equiv
+    lang
+    language
+    link
+    media
+    method
+    multiple
+    nohref
+    noresize
+    noshade
+    nowrap
+    readonly
+    rel
+    rev
+    rules
+    scope
+    scrolling
+    selected
+    shape
+    target
+    text
+    type
+    valign
+    valuetype
+    vlink
+"#;
diff --git a/servo/components/selectors/builder.rs b/servo/components/selectors/builder.rs
new file mode 100644
index 0000000000..2406cd84f6
--- /dev/null
+++ b/servo/components/selectors/builder.rs
@@ -0,0 +1,391 @@
+/* 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/. */
+
+//! Helper module to build up a selector safely and efficiently.
+//!
+//! Our selector representation is designed to optimize matching, and has
+//! several requirements:
+//! * All simple selectors and combinators are stored inline in the same buffer
+//!   as Component instances.
+//! * We store the top-level compound selectors from right to left, i.e. in
+//!   matching order.
+//! * We store the simple selectors for each combinator from left to right, so
+//!   that we match the cheaper simple selectors first.
+//!
+//! Meeting all these constraints without extra memmove traffic during parsing
+//! is non-trivial. This module encapsulates those details and presents an
+//! easy-to-use API for the parser.
+
+use crate::parser::{Combinator, Component, RelativeSelector, Selector, SelectorImpl};
+use crate::sink::Push;
+use servo_arc::{Arc, ThinArc};
+use smallvec::{self, SmallVec};
+use std::cmp;
+use std::iter;
+use std::ptr;
+use std::slice;
+
+/// Top-level SelectorBuilder struct. This should be stack-allocated by the
+/// consumer and never moved (because it contains a lot of inline data that
+/// would be slow to memmov).
+///
+/// After instantation, callers may call the push_simple_selector() and
+/// push_combinator() methods to append selector data as it is encountered
+/// (from left to right). Once the process is complete, callers should invoke
+/// build(), which transforms the contents of the SelectorBuilder into a heap-
+/// allocated Selector and leaves the builder in a drained state.
+#[derive(Debug)]
+pub struct SelectorBuilder<Impl: SelectorImpl> {
+    /// The entire sequence of simple selectors, from left to right, without combinators.
+    ///
+    /// We make this large because the result of parsing a selector is fed into a new
+    /// Arc-ed allocation, so any spilled vec would be a wasted allocation. Also,
+    /// Components are large enough that we don't have much cache locality benefit
+    /// from reserving stack space for fewer of them.
+    simple_selectors: SmallVec<[Component<Impl>; 32]>,
+    /// The combinators, and the length of the compound selector to their left.
+    combinators: SmallVec<[(Combinator, usize); 16]>,
+    /// The length of the current compount selector.
+    current_len: usize,
+}
+
+impl<Impl: SelectorImpl> Default for SelectorBuilder<Impl> {
+    #[inline(always)]
+    fn default() -> Self {
+        SelectorBuilder {
+            simple_selectors: SmallVec::new(),
+            combinators: SmallVec::new(),
+            current_len: 0,
+        }
+    }
+}
+
+impl<Impl: SelectorImpl> Push<Component<Impl>> for SelectorBuilder<Impl> {
+    fn push(&mut self, value: Component<Impl>) {
+        self.push_simple_selector(value);
+    }
+}
+
+impl<Impl: SelectorImpl> SelectorBuilder<Impl> {
+    /// Pushes a simple selector onto the current compound selector.
+    #[inline(always)]
+    pub fn push_simple_selector(&mut self, ss: Component<Impl>) {
+        assert!(!ss.is_combinator());
+        self.simple_selectors.push(ss);
+        self.current_len += 1;
+    }
+
+    /// Completes the current compound selector and starts a new one, delimited
+    /// by the given combinator.
+    #[inline(always)]
+    pub fn push_combinator(&mut self, c: Combinator) {
+        self.combinators.push((c, self.current_len));
+        self.current_len = 0;
+    }
+
+    /// Returns true if combinators have ever been pushed to this builder.
+    #[inline(always)]
+    pub fn has_combinators(&self) -> bool {
+        !self.combinators.is_empty()
+    }
+
+    /// Consumes the builder, producing a Selector.
+    #[inline(always)]
+    pub fn build(&mut self) -> ThinArc<SpecificityAndFlags, Component<Impl>> {
+        // Compute the specificity and flags.
+        let sf = specificity_and_flags(self.simple_selectors.iter());
+        self.build_with_specificity_and_flags(sf)
+    }
+
+    /// Builds with an explicit SpecificityAndFlags. This is separated from build() so
+    /// that unit tests can pass an explicit specificity.
+    #[inline(always)]
+    pub(crate) fn build_with_specificity_and_flags(
+        &mut self,
+        spec: SpecificityAndFlags,
+    ) -> ThinArc<SpecificityAndFlags, Component<Impl>> {
+        // Create the Arc using an iterator that drains our buffers.
+        // Panic-safety: if SelectorBuilderIter is not iterated to the end, some simple selectors
+        // will safely leak.
+        let raw_simple_selectors = unsafe {
+            let simple_selectors_len = self.simple_selectors.len();
+            self.simple_selectors.set_len(0);
+            std::slice::from_raw_parts(self.simple_selectors.as_ptr(), simple_selectors_len)
+        };
+        let (rest, current) = split_from_end(raw_simple_selectors, self.current_len);
+        let iter = SelectorBuilderIter {
+            current_simple_selectors: current.iter(),
+            rest_of_simple_selectors: rest,
+            combinators: self.combinators.drain(..).rev(),
+        };
+
+        Arc::from_header_and_iter(spec, iter)
+    }
+}
+
+struct SelectorBuilderIter<'a, Impl: SelectorImpl> {
+    current_simple_selectors: slice::Iter<'a, Component<Impl>>,
+    rest_of_simple_selectors: &'a [Component<Impl>],
+    combinators: iter::Rev<smallvec::Drain<'a, [(Combinator, usize); 16]>>,
+}
+
+impl<'a, Impl: SelectorImpl> ExactSizeIterator for SelectorBuilderIter<'a, Impl> {
+    fn len(&self) -> usize {
+        self.current_simple_selectors.len() +
+            self.rest_of_simple_selectors.len() +
+            self.combinators.len()
+    }
+}
+
+impl<'a, Impl: SelectorImpl> Iterator for SelectorBuilderIter<'a, Impl> {
+    type Item = Component<Impl>;
+    #[inline(always)]
+    fn next(&mut self) -> Option<Self::Item> {
+        if let Some(simple_selector_ref) = self.current_simple_selectors.next() {
+            // Move a simple selector out of this slice iterator.
+            // This is safe because we’ve called SmallVec::set_len(0) above,
+            // so SmallVec::drop won’t drop this simple selector.
+            unsafe { Some(ptr::read(simple_selector_ref)) }
+        } else {
+            self.combinators.next().map(|(combinator, len)| {
+                let (rest, current) = split_from_end(self.rest_of_simple_selectors, len);
+                self.rest_of_simple_selectors = rest;
+                self.current_simple_selectors = current.iter();
+                Component::Combinator(combinator)
+            })
+        }
+    }
+
+    fn size_hint(&self) -> (usize, Option<usize>) {
+        (self.len(), Some(self.len()))
+    }
+}
+
+fn split_from_end<T>(s: &[T], at: usize) -> (&[T], &[T]) {
+    s.split_at(s.len() - at)
+}
+
+/// Flags that indicate at which point of parsing a selector are we.
+#[derive(Clone, Copy, Default, Eq, PartialEq, ToShmem)]
+pub(crate) struct SelectorFlags(u8);
+
+bitflags! {
+    impl SelectorFlags: u8 {
+        const HAS_PSEUDO = 1 << 0;
+        const HAS_SLOTTED = 1 << 1;
+        const HAS_PART = 1 << 2;
+        const HAS_PARENT = 1 << 3;
+        const HAS_NON_FEATURELESS_COMPONENT = 1 << 4;
+        const HAS_HOST = 1 << 5;
+    }
+}
+
+impl core::fmt::Debug for SelectorFlags {
+    fn fmt(&self, f: &mut core::fmt::Formatter) -> core::fmt::Result {
+        if self.is_empty() {
+            write!(f, "{:#x}", Self::empty().bits())
+        } else {
+            bitflags::parser::to_writer(self, f)
+        }
+    }
+}
+
+impl SelectorFlags {
+    /// When you nest a pseudo-element with something like:
+    ///
+    ///   ::before { & { .. } }
+    ///
+    /// It is not supposed to work, because :is(::before) is invalid. We can't propagate the
+    /// pseudo-flags from inner to outer selectors, to avoid breaking our invariants.
+    pub(crate) fn for_nesting() -> Self {
+        Self::all() - (Self::HAS_PSEUDO | Self::HAS_SLOTTED | Self::HAS_PART)
+    }
+}
+
+#[derive(Clone, Copy, Debug, Default, Eq, PartialEq, ToShmem)]
+pub struct SpecificityAndFlags {
+    /// There are two free bits here, since we use ten bits for each specificity
+    /// kind (id, class, element).
+    pub(crate) specificity: u32,
+    /// There's padding after this field due to the size of the flags.
+    pub(crate) flags: SelectorFlags,
+}
+
+const MAX_10BIT: u32 = (1u32 << 10) - 1;
+
+#[derive(Add, AddAssign, Clone, Copy, Default, Eq, Ord, PartialEq, PartialOrd)]
+pub(crate) struct Specificity {
+    id_selectors: u32,
+    class_like_selectors: u32,
+    element_selectors: u32,
+}
+
+impl From<u32> for Specificity {
+    #[inline]
+    fn from(value: u32) -> Specificity {
+        assert!(value <= MAX_10BIT << 20 | MAX_10BIT << 10 | MAX_10BIT);
+        Specificity {
+            id_selectors: value >> 20,
+            class_like_selectors: (value >> 10) & MAX_10BIT,
+            element_selectors: value & MAX_10BIT,
+        }
+    }
+}
+
+impl From<Specificity> for u32 {
+    #[inline]
+    fn from(specificity: Specificity) -> u32 {
+        cmp::min(specificity.id_selectors, MAX_10BIT) << 20 |
+            cmp::min(specificity.class_like_selectors, MAX_10BIT) << 10 |
+            cmp::min(specificity.element_selectors, MAX_10BIT)
+    }
+}
+
+pub(crate) fn specificity_and_flags<Impl>(iter: slice::Iter<Component<Impl>>) -> SpecificityAndFlags
+where
+    Impl: SelectorImpl,
+{
+    complex_selector_specificity_and_flags(iter).into()
+}
+
+fn complex_selector_specificity_and_flags<Impl>(
+    iter: slice::Iter<Component<Impl>>,
+) -> SpecificityAndFlags
+where
+    Impl: SelectorImpl,
+{
+    fn component_specificity<Impl>(
+        simple_selector: &Component<Impl>,
+        specificity: &mut Specificity,
+        flags: &mut SelectorFlags,
+    ) where
+        Impl: SelectorImpl,
+    {
+        match *simple_selector {
+            Component::Combinator(..) => {},
+            Component::ParentSelector => flags.insert(SelectorFlags::HAS_PARENT),
+            Component::Part(..) => {
+                flags.insert(SelectorFlags::HAS_PART);
+                specificity.element_selectors += 1
+            },
+            Component::PseudoElement(..) => {
+                flags.insert(SelectorFlags::HAS_PSEUDO);
+                specificity.element_selectors += 1
+            },
+            Component::LocalName(..) => {
+                flags.insert(SelectorFlags::HAS_NON_FEATURELESS_COMPONENT);
+                specificity.element_selectors += 1
+            },
+            Component::Slotted(ref selector) => {
+                flags.insert(
+                    SelectorFlags::HAS_SLOTTED | SelectorFlags::HAS_NON_FEATURELESS_COMPONENT,
+                );
+                specificity.element_selectors += 1;
+                // Note that due to the way ::slotted works we only compete with
+                // other ::slotted rules, so the above rule doesn't really
+                // matter, but we do it still for consistency with other
+                // pseudo-elements.
+                //
+                // See: https://github.com/w3c/csswg-drafts/issues/1915
+                *specificity += Specificity::from(selector.specificity());
+                flags.insert(selector.flags());
+            },
+            Component::Host(ref selector) => {
+                flags.insert(SelectorFlags::HAS_HOST);
+                specificity.class_like_selectors += 1;
+                if let Some(ref selector) = *selector {
+                    // See: https://github.com/w3c/csswg-drafts/issues/1915
+                    *specificity += Specificity::from(selector.specificity());
+                    flags.insert(selector.flags() - SelectorFlags::HAS_NON_FEATURELESS_COMPONENT);
+                }
+            },
+            Component::ID(..) => {
+                flags.insert(SelectorFlags::HAS_NON_FEATURELESS_COMPONENT);
+                specificity.id_selectors += 1;
+            },
+            Component::Class(..) |
+            Component::AttributeInNoNamespace { .. } |
+            Component::AttributeInNoNamespaceExists { .. } |
+            Component::AttributeOther(..) |
+            Component::Root |
+            Component::Empty |
+            Component::Scope |
+            Component::Nth(..) |
+            Component::NonTSPseudoClass(..) => {
+                flags.insert(SelectorFlags::HAS_NON_FEATURELESS_COMPONENT);
+                specificity.class_like_selectors += 1;
+            },
+            Component::NthOf(ref nth_of_data) => {
+                // https://drafts.csswg.org/selectors/#specificity-rules:
+                //
+                //     The specificity of the :nth-last-child() pseudo-class,
+                //     like the :nth-child() pseudo-class, combines the
+                //     specificity of a regular pseudo-class with that of its
+                //     selector argument S.
+                specificity.class_like_selectors += 1;
+                let sf = selector_list_specificity_and_flags(nth_of_data.selectors().iter());
+                *specificity += Specificity::from(sf.specificity);
+                flags.insert(sf.flags | SelectorFlags::HAS_NON_FEATURELESS_COMPONENT);
+            },
+            // https://drafts.csswg.org/selectors/#specificity-rules:
+            //
+            //     The specificity of an :is(), :not(), or :has() pseudo-class
+            //     is replaced by the specificity of the most specific complex
+            //     selector in its selector list argument.
+            Component::Where(ref list) |
+            Component::Negation(ref list) |
+            Component::Is(ref list) => {
+                let sf = selector_list_specificity_and_flags(list.slice().iter());
+                if !matches!(*simple_selector, Component::Where(..)) {
+                    *specificity += Specificity::from(sf.specificity);
+                }
+                flags.insert(sf.flags);
+            },
+            Component::Has(ref relative_selectors) => {
+                let sf = relative_selector_list_specificity_and_flags(relative_selectors);
+                *specificity += Specificity::from(sf.specificity);
+                flags.insert(sf.flags | SelectorFlags::HAS_NON_FEATURELESS_COMPONENT);
+            },
+            Component::ExplicitUniversalType |
+            Component::ExplicitAnyNamespace |
+            Component::ExplicitNoNamespace |
+            Component::DefaultNamespace(..) |
+            Component::Namespace(..) |
+            Component::RelativeSelectorAnchor |
+            Component::Invalid(..) => {
+                // Does not affect specificity
+                flags.insert(SelectorFlags::HAS_NON_FEATURELESS_COMPONENT);
+            },
+        }
+    }
+
+    let mut specificity = Default::default();
+    let mut flags = Default::default();
+    for simple_selector in iter {
+        component_specificity(&simple_selector, &mut specificity, &mut flags);
+    }
+    SpecificityAndFlags {
+        specificity: specificity.into(),
+        flags,
+    }
+}
+
+/// Finds the maximum specificity of elements in the list and returns it.
+pub(crate) fn selector_list_specificity_and_flags<'a, Impl: SelectorImpl>(
+    itr: impl Iterator<Item = &'a Selector<Impl>>,
+) -> SpecificityAndFlags {
+    let mut specificity = 0;
+    let mut flags = SelectorFlags::empty();
+    for selector in itr {
+        specificity = std::cmp::max(specificity, selector.specificity());
+        flags.insert(selector.flags());
+    }
+    SpecificityAndFlags { specificity, flags }
+}
+
+pub(crate) fn relative_selector_list_specificity_and_flags<Impl: SelectorImpl>(
+    list: &[RelativeSelector<Impl>],
+) -> SpecificityAndFlags {
+    selector_list_specificity_and_flags(list.iter().map(|rel| &rel.selector))
+}
diff --git a/servo/components/selectors/context.rs b/servo/components/selectors/context.rs
new file mode 100644
index 0000000000..84ee262dfe
--- /dev/null
+++ b/servo/components/selectors/context.rs
@@ -0,0 +1,418 @@
+/* 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::CaseSensitivity;
+use crate::bloom::BloomFilter;
+use crate::nth_index_cache::{NthIndexCache, NthIndexCacheInner};
+use crate::parser::{Selector, SelectorImpl};
+use crate::relative_selector::cache::RelativeSelectorCache;
+use crate::relative_selector::filter::RelativeSelectorFilterMap;
+use crate::tree::{Element, OpaqueElement};
+
+/// What kind of selector matching mode we should use.
+///
+/// There are two modes of selector matching. The difference is only noticeable
+/// in presence of pseudo-elements.
+#[derive(Clone, Copy, Debug, PartialEq)]
+pub enum MatchingMode {
+    /// Don't ignore any pseudo-element selectors.
+    Normal,
+
+    /// Ignores any stateless pseudo-element selectors in the rightmost sequence
+    /// of simple selectors.
+    ///
+    /// This is useful, for example, to match against ::before when you aren't a
+    /// pseudo-element yourself.
+    ///
+    /// For example, in presence of `::before:hover`, it would never match, but
+    /// `::before` would be ignored as in "matching".
+    ///
+    /// It's required for all the selectors you match using this mode to have a
+    /// pseudo-element.
+    ForStatelessPseudoElement,
+}
+
+/// The mode to use when matching unvisited and visited links.
+#[derive(Clone, Copy, Debug, Eq, PartialEq)]
+pub enum VisitedHandlingMode {
+    /// All links are matched as if they are unvisted.
+    AllLinksUnvisited,
+    /// All links are matched as if they are visited and unvisited (both :link
+    /// and :visited match).
+    ///
+    /// This is intended to be used from invalidation code, to be conservative
+    /// about whether we need to restyle a link.
+    AllLinksVisitedAndUnvisited,
+    /// A element's "relevant link" is the element being matched if it is a link
+    /// or the nearest ancestor link. The relevant link is matched as though it
+    /// is visited, and all other links are matched as if they are unvisited.
+    RelevantLinkVisited,
+}
+
+impl VisitedHandlingMode {
+    #[inline]
+    pub fn matches_visited(&self) -> bool {
+        matches!(
+            *self,
+            VisitedHandlingMode::RelevantLinkVisited |
+                VisitedHandlingMode::AllLinksVisitedAndUnvisited
+        )
+    }
+
+    #[inline]
+    pub fn matches_unvisited(&self) -> bool {
+        matches!(
+            *self,
+            VisitedHandlingMode::AllLinksUnvisited |
+                VisitedHandlingMode::AllLinksVisitedAndUnvisited
+        )
+    }
+}
+
+/// Whether we need to set selector invalidation flags on elements for this
+/// match request.
+#[derive(Clone, Copy, Debug, PartialEq)]
+pub enum NeedsSelectorFlags {
+    No,
+    Yes,
+}
+
+/// Whether we're matching in the contect of invalidation.
+#[derive(PartialEq)]
+pub enum MatchingForInvalidation {
+    No,
+    Yes,
+}
+
+/// Which quirks mode is this document in.
+///
+/// See: https://quirks.spec.whatwg.org/
+#[derive(Clone, Copy, Debug, Eq, Hash, PartialEq)]
+pub enum QuirksMode {
+    /// Quirks mode.
+    Quirks,
+    /// Limited quirks mode.
+    LimitedQuirks,
+    /// No quirks mode.
+    NoQuirks,
+}
+
+impl QuirksMode {
+    #[inline]
+    pub fn classes_and_ids_case_sensitivity(self) -> CaseSensitivity {
+        match self {
+            QuirksMode::NoQuirks | QuirksMode::LimitedQuirks => CaseSensitivity::CaseSensitive,
+            QuirksMode::Quirks => CaseSensitivity::AsciiCaseInsensitive,
+        }
+    }
+}
+
+/// Whether or not this matching considered relative selector.
+#[derive(Clone, Copy, Debug, PartialEq)]
+pub enum RelativeSelectorMatchingState {
+    /// Was not considered for any relative selector.
+    None,
+    /// Relative selector was considered for a match, but the element to be
+    /// under matching would not anchor the relative selector. i.e. The
+    /// relative selector was not part of the first compound selector (in match
+    /// order).
+    Considered,
+    /// Same as above, but the relative selector was part of the first compound
+    /// selector (in match order).
+    ConsideredAnchor,
+}
+
+impl RelativeSelectorMatchingState {
+    /// Update the matching state to indicate that the relative selector matching
+    /// happened in the subject position.
+    pub fn considered_anchor(&mut self) {
+        *self = Self::ConsideredAnchor;
+    }
+
+    /// Update the matching state to indicate that the relative selector matching
+    /// happened in a non-subject position.
+    pub fn considered(&mut self) {
+        // Being considered an anchor is stronger (e.g. `:has(.a):is(:has(.b) .c)`).
+        if *self == Self::ConsideredAnchor {
+            *self = Self::ConsideredAnchor;
+        } else {
+            *self = Self::Considered;
+        }
+    }
+}
+
+/// Set of caches (And cache-likes) that speed up expensive selector matches.
+#[derive(Default)]
+pub struct SelectorCaches {
+    /// A cache to speed up nth-index-like selectors.
+    pub nth_index: NthIndexCache,
+    /// A cache to speed up relative selector matches. See module documentation.
+    pub relative_selector: RelativeSelectorCache,
+    /// A map of bloom filters to fast-reject relative selector matches.
+    pub relative_selector_filter_map: RelativeSelectorFilterMap,
+}
+
+/// Data associated with the matching process for a element.  This context is
+/// used across many selectors for an element, so it's not appropriate for
+/// transient data that applies to only a single selector.
+pub struct MatchingContext<'a, Impl>
+where
+    Impl: SelectorImpl,
+{
+    /// Input with the matching mode we should use when matching selectors.
+    matching_mode: MatchingMode,
+    /// Input with the bloom filter used to fast-reject selectors.
+    pub bloom_filter: Option<&'a BloomFilter>,
+    /// The element which is going to match :scope pseudo-class. It can be
+    /// either one :scope element, or the scoping element.
+    ///
+    /// Note that, although in theory there can be multiple :scope elements,
+    /// in current specs, at most one is specified, and when there is one,
+    /// scoping element is not relevant anymore, so we use a single field for
+    /// them.
+    ///
+    /// When this is None, :scope will match the root element.
+    ///
+    /// See https://drafts.csswg.org/selectors-4/#scope-pseudo
+    pub scope_element: Option<OpaqueElement>,
+
+    /// The current shadow host we're collecting :host rules for.
+    pub current_host: Option<OpaqueElement>,
+
+    /// Controls how matching for links is handled.
+    visited_handling: VisitedHandlingMode,
+
+    /// The current nesting level of selectors that we're matching.
+    nesting_level: usize,
+
+    /// Whether we're inside a negation or not.
+    in_negation: bool,
+
+    /// An optional hook function for checking whether a pseudo-element
+    /// should match when matching_mode is ForStatelessPseudoElement.
+    pub pseudo_element_matching_fn: Option<&'a dyn Fn(&Impl::PseudoElement) -> bool>,
+
+    /// Extra implementation-dependent matching data.
+    pub extra_data: Impl::ExtraMatchingData<'a>,
+
+    /// The current element we're anchoring on for evaluating the relative selector.
+    current_relative_selector_anchor: Option<OpaqueElement>,
+    pub considered_relative_selector: RelativeSelectorMatchingState,
+
+    quirks_mode: QuirksMode,
+    needs_selector_flags: NeedsSelectorFlags,
+
+    /// Whether we're matching in the contect of invalidation.
+    matching_for_invalidation: MatchingForInvalidation,
+
+    /// Caches to speed up expensive selector matches.
+    pub selector_caches: &'a mut SelectorCaches,
+
+    classes_and_ids_case_sensitivity: CaseSensitivity,
+    _impl: ::std::marker::PhantomData<Impl>,
+}
+
+impl<'a, Impl> MatchingContext<'a, Impl>
+where
+    Impl: SelectorImpl,
+{
+    /// Constructs a new `MatchingContext`.
+    pub fn new(
+        matching_mode: MatchingMode,
+        bloom_filter: Option<&'a BloomFilter>,
+        selector_caches: &'a mut SelectorCaches,
+        quirks_mode: QuirksMode,
+        needs_selector_flags: NeedsSelectorFlags,
+        matching_for_invalidation: MatchingForInvalidation,
+    ) -> Self {
+        Self::new_for_visited(
+            matching_mode,
+            bloom_filter,
+            selector_caches,
+            VisitedHandlingMode::AllLinksUnvisited,
+            quirks_mode,
+            needs_selector_flags,
+            matching_for_invalidation,
+        )
+    }
+
+    /// Constructs a new `MatchingContext` for use in visited matching.
+    pub fn new_for_visited(
+        matching_mode: MatchingMode,
+        bloom_filter: Option<&'a BloomFilter>,
+        selector_caches: &'a mut SelectorCaches,
+        visited_handling: VisitedHandlingMode,
+        quirks_mode: QuirksMode,
+        needs_selector_flags: NeedsSelectorFlags,
+        matching_for_invalidation: MatchingForInvalidation,
+    ) -> Self {
+        Self {
+            matching_mode,
+            bloom_filter,
+            visited_handling,
+            quirks_mode,
+            classes_and_ids_case_sensitivity: quirks_mode.classes_and_ids_case_sensitivity(),
+            needs_selector_flags,
+            matching_for_invalidation,
+            scope_element: None,
+            current_host: None,
+            nesting_level: 0,
+            in_negation: false,
+            pseudo_element_matching_fn: None,
+            extra_data: Default::default(),
+            current_relative_selector_anchor: None,
+            considered_relative_selector: RelativeSelectorMatchingState::None,
+            selector_caches,
+            _impl: ::std::marker::PhantomData,
+        }
+    }
+
+    // Grab a reference to the appropriate cache.
+    #[inline]
+    pub fn nth_index_cache(
+        &mut self,
+        is_of_type: bool,
+        is_from_end: bool,
+        selectors: &[Selector<Impl>],
+    ) -> &mut NthIndexCacheInner {
+        self.selector_caches
+            .nth_index
+            .get(is_of_type, is_from_end, selectors)
+    }
+
+    /// Whether we're matching a nested selector.
+    #[inline]
+    pub fn is_nested(&self) -> bool {
+        self.nesting_level != 0
+    }
+
+    /// Whether we're matching inside a :not(..) selector.
+    #[inline]
+    pub fn in_negation(&self) -> bool {
+        self.in_negation
+    }
+
+    /// The quirks mode of the document.
+    #[inline]
+    pub fn quirks_mode(&self) -> QuirksMode {
+        self.quirks_mode
+    }
+
+    /// The matching-mode for this selector-matching operation.
+    #[inline]
+    pub fn matching_mode(&self) -> MatchingMode {
+        self.matching_mode
+    }
+
+    /// Whether we need to set selector flags.
+    #[inline]
+    pub fn needs_selector_flags(&self) -> bool {
+        self.needs_selector_flags == NeedsSelectorFlags::Yes
+    }
+
+    /// Whether or not we're matching to invalidate.
+    #[inline]
+    pub fn matching_for_invalidation(&self) -> bool {
+        self.matching_for_invalidation == MatchingForInvalidation::Yes
+    }
+
+    /// The case-sensitivity for class and ID selectors
+    #[inline]
+    pub fn classes_and_ids_case_sensitivity(&self) -> CaseSensitivity {
+        self.classes_and_ids_case_sensitivity
+    }
+
+    /// Runs F with a deeper nesting level.
+    #[inline]
+    pub fn nest<F, R>(&mut self, f: F) -> R
+    where
+        F: FnOnce(&mut Self) -> R,
+    {
+        self.nesting_level += 1;
+        let result = f(self);
+        self.nesting_level -= 1;
+        result
+    }
+
+    /// Runs F with a deeper nesting level, and marking ourselves in a negation,
+    /// for a :not(..) selector, for example.
+    #[inline]
+    pub fn nest_for_negation<F, R>(&mut self, f: F) -> R
+    where
+        F: FnOnce(&mut Self) -> R,
+    {
+        let old_in_negation = self.in_negation;
+        self.in_negation = true;
+        let result = self.nest(f);
+        self.in_negation = old_in_negation;
+        result
+    }
+
+    #[inline]
+    pub fn visited_handling(&self) -> VisitedHandlingMode {
+        self.visited_handling
+    }
+
+    /// Runs F with a different VisitedHandlingMode.
+    #[inline]
+    pub fn with_visited_handling_mode<F, R>(
+        &mut self,
+        handling_mode: VisitedHandlingMode,
+        f: F,
+    ) -> R
+    where
+        F: FnOnce(&mut Self) -> R,
+    {
+        let original_handling_mode = self.visited_handling;
+        self.visited_handling = handling_mode;
+        let result = f(self);
+        self.visited_handling = original_handling_mode;
+        result
+    }
+
+    /// Runs F with a given shadow host which is the root of the tree whose
+    /// rules we're matching.
+    #[inline]
+    pub fn with_shadow_host<F, E, R>(&mut self, host: Option<E>, f: F) -> R
+    where
+        E: Element,
+        F: FnOnce(&mut Self) -> R,
+    {
+        let original_host = self.current_host.take();
+        self.current_host = host.map(|h| h.opaque());
+        let result = f(self);
+        self.current_host = original_host;
+        result
+    }
+
+    /// Returns the current shadow host whose shadow root we're matching rules
+    /// against.
+    #[inline]
+    pub fn shadow_host(&self) -> Option<OpaqueElement> {
+        self.current_host
+    }
+
+    /// Runs F with a deeper nesting level, with the given element as the anchor,
+    /// for a :has(...) selector, for example.
+    #[inline]
+    pub fn nest_for_relative_selector<F, R>(&mut self, anchor: OpaqueElement, f: F) -> R
+    where
+        F: FnOnce(&mut Self) -> R,
+    {
+        debug_assert!(
+            self.current_relative_selector_anchor.is_none(),
+            "Nesting should've been rejected at parse time"
+        );
+        self.current_relative_selector_anchor = Some(anchor);
+        let result = self.nest(f);
+        self.current_relative_selector_anchor = None;
+        result
+    }
+
+    /// Returns the current anchor element to evaluate the relative selector against.
+    #[inline]
+    pub fn relative_selector_anchor(&self) -> Option<OpaqueElement> {
+        self.current_relative_selector_anchor
+    }
+}
diff --git a/servo/components/selectors/lib.rs b/servo/components/selectors/lib.rs
new file mode 100644
index 0000000000..d909059ccf
--- /dev/null
+++ b/servo/components/selectors/lib.rs
@@ -0,0 +1,41 @@
+/* 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/. */
+
+// Make |cargo bench| work.
+#![cfg_attr(feature = "bench", feature(test))]
+
+#[macro_use]
+extern crate bitflags;
+#[macro_use]
+extern crate cssparser;
+#[macro_use]
+extern crate debug_unreachable;
+#[macro_use]
+extern crate derive_more;
+extern crate fxhash;
+#[macro_use]
+extern crate log;
+extern crate phf;
+extern crate precomputed_hash;
+extern crate servo_arc;
+extern crate smallvec;
+extern crate to_shmem;
+#[macro_use]
+extern crate to_shmem_derive;
+
+pub mod attr;
+pub mod bloom;
+mod builder;
+pub mod context;
+pub mod matching;
+mod nth_index_cache;
+pub mod parser;
+pub mod relative_selector;
+pub mod sink;
+mod tree;
+pub mod visitor;
+
+pub use crate::nth_index_cache::NthIndexCache;
+pub use crate::parser::{Parser, SelectorImpl, SelectorList};
+pub use crate::tree::{Element, OpaqueElement};
diff --git a/servo/components/selectors/matching.rs b/servo/components/selectors/matching.rs
new file mode 100644
index 0000000000..763f65d547
--- /dev/null
+++ b/servo/components/selectors/matching.rs
@@ -0,0 +1,1370 @@
+/* This Source Code Form is subject to the terms of the Mozilla Public
+ * License, v. 2.0. If a copy of the MPL was not distributed with this
+ * file, You can obtain one at https://mozilla.org/MPL/2.0/. */
+
+use crate::attr::{
+    AttrSelectorOperation, AttrSelectorWithOptionalNamespace, CaseSensitivity, NamespaceConstraint,
+    ParsedAttrSelectorOperation, ParsedCaseSensitivity,
+};
+use crate::bloom::{BloomFilter, BLOOM_HASH_MASK};
+use crate::parser::{
+    AncestorHashes, Combinator, Component, LocalName, NthSelectorData, RelativeSelectorMatchHint,
+};
+use crate::parser::{
+    NonTSPseudoClass, RelativeSelector, Selector, SelectorImpl, SelectorIter, SelectorList,
+};
+use crate::relative_selector::cache::RelativeSelectorCachedMatch;
+use crate::tree::Element;
+use smallvec::SmallVec;
+use std::borrow::Borrow;
+
+pub use crate::context::*;
+
+// The bloom filter for descendant CSS selectors will have a <1% false
+// positive rate until it has this many selectors in it, then it will
+// rapidly increase.
+pub static RECOMMENDED_SELECTOR_BLOOM_FILTER_SIZE: usize = 4096;
+
+bitflags! {
+    /// Set of flags that are set on either the element or its parent (depending
+    /// on the flag) if the element could potentially match a selector.
+    #[derive(Clone, Copy)]
+    pub struct ElementSelectorFlags: usize {
+        /// When a child is added or removed from the parent, all the children
+        /// must be restyled, because they may match :nth-last-child,
+        /// :last-of-type, :nth-last-of-type, or :only-of-type.
+        const HAS_SLOW_SELECTOR = 1 << 0;
+
+        /// When a child is added or removed from the parent, any later
+        /// children must be restyled, because they may match :nth-child,
+        /// :first-of-type, or :nth-of-type.
+        const HAS_SLOW_SELECTOR_LATER_SIBLINGS = 1 << 1;
+
+        /// HAS_SLOW_SELECTOR* was set by the presence of :nth (But not of).
+        const HAS_SLOW_SELECTOR_NTH = 1 << 2;
+
+        /// When a DOM mutation occurs on a child that might be matched by
+        /// :nth-last-child(.. of <selector list>), earlier children must be
+        /// restyled, and HAS_SLOW_SELECTOR will be set (which normally
+        /// indicates that all children will be restyled).
+        ///
+        /// Similarly, when a DOM mutation occurs on a child that might be
+        /// matched by :nth-child(.. of <selector list>), later children must be
+        /// restyled, and HAS_SLOW_SELECTOR_LATER_SIBLINGS will be set.
+        const HAS_SLOW_SELECTOR_NTH_OF = 1 << 3;
+
+        /// When a child is added or removed from the parent, the first and
+        /// last children must be restyled, because they may match :first-child,
+        /// :last-child, or :only-child.
+        const HAS_EDGE_CHILD_SELECTOR = 1 << 4;
+
+        /// The element has an empty selector, so when a child is appended we
+        /// might need to restyle the parent completely.
+        const HAS_EMPTY_SELECTOR = 1 << 5;
+
+        /// The element may anchor a relative selector.
+        const ANCHORS_RELATIVE_SELECTOR = 1 << 6;
+
+        /// The element may anchor a relative selector that is not the subject
+        /// of the whole selector.
+        const ANCHORS_RELATIVE_SELECTOR_NON_SUBJECT = 1 << 7;
+
+        /// The element is reached by a relative selector search in the sibling direction.
+        const RELATIVE_SELECTOR_SEARCH_DIRECTION_SIBLING = 1 << 8;
+
+        /// The element is reached by a relative selector search in the ancestor direction.
+        const RELATIVE_SELECTOR_SEARCH_DIRECTION_ANCESTOR = 1 << 9;
+
+        // The element is reached by a relative selector search in both sibling and ancestor directions.
+        const RELATIVE_SELECTOR_SEARCH_DIRECTION_ANCESTOR_SIBLING =
+            Self::RELATIVE_SELECTOR_SEARCH_DIRECTION_SIBLING.bits() |
+            Self::RELATIVE_SELECTOR_SEARCH_DIRECTION_ANCESTOR.bits();
+    }
+}
+
+impl ElementSelectorFlags {
+    /// Returns the subset of flags that apply to the element.
+    pub fn for_self(self) -> ElementSelectorFlags {
+        self & (ElementSelectorFlags::HAS_EMPTY_SELECTOR |
+            ElementSelectorFlags::ANCHORS_RELATIVE_SELECTOR |
+            ElementSelectorFlags::ANCHORS_RELATIVE_SELECTOR_NON_SUBJECT |
+            ElementSelectorFlags::RELATIVE_SELECTOR_SEARCH_DIRECTION_SIBLING |
+            ElementSelectorFlags::RELATIVE_SELECTOR_SEARCH_DIRECTION_ANCESTOR)
+    }
+
+    /// Returns the subset of flags that apply to the parent.
+    pub fn for_parent(self) -> ElementSelectorFlags {
+        self & (ElementSelectorFlags::HAS_SLOW_SELECTOR |
+            ElementSelectorFlags::HAS_SLOW_SELECTOR_LATER_SIBLINGS |
+            ElementSelectorFlags::HAS_SLOW_SELECTOR_NTH |
+            ElementSelectorFlags::HAS_SLOW_SELECTOR_NTH_OF |
+            ElementSelectorFlags::HAS_EDGE_CHILD_SELECTOR)
+    }
+}
+
+/// Holds per-compound-selector data.
+struct LocalMatchingContext<'a, 'b: 'a, Impl: SelectorImpl> {
+    shared: &'a mut MatchingContext<'b, Impl>,
+    rightmost: SubjectOrPseudoElement,
+    quirks_data: Option<SelectorIter<'a, Impl>>,
+}
+
+#[inline(always)]
+pub fn matches_selector_list<E>(
+    selector_list: &SelectorList<E::Impl>,
+    element: &E,
+    context: &mut MatchingContext<E::Impl>,
+) -> bool
+where
+    E: Element,
+{
+    // This is pretty much any(..) but manually inlined because the compiler
+    // refuses to do so from querySelector / querySelectorAll.
+    for selector in selector_list.slice() {
+        let matches = matches_selector(selector, 0, None, element, context);
+        if matches {
+            return true;
+        }
+    }
+
+    false
+}
+
+#[inline(always)]
+fn may_match(hashes: &AncestorHashes, bf: &BloomFilter) -> bool {
+    // Check the first three hashes. Note that we can check for zero before
+    // masking off the high bits, since if any of the first three hashes is
+    // zero the fourth will be as well. We also take care to avoid the
+    // special-case complexity of the fourth hash until we actually reach it,
+    // because we usually don't.
+    //
+    // To be clear: this is all extremely hot.
+    for i in 0..3 {
+        let packed = hashes.packed_hashes[i];
+        if packed == 0 {
+            // No more hashes left - unable to fast-reject.
+            return true;
+        }
+
+        if !bf.might_contain_hash(packed & BLOOM_HASH_MASK) {
+            // Hooray! We fast-rejected on this hash.
+            return false;
+        }
+    }
+
+    // Now do the slighty-more-complex work of synthesizing the fourth hash,
+    // and check it against the filter if it exists.
+    let fourth = hashes.fourth_hash();
+    fourth == 0 || bf.might_contain_hash(fourth)
+}
+
+/// A result of selector matching, includes 3 failure types,
+///
+///   NotMatchedAndRestartFromClosestLaterSibling
+///   NotMatchedAndRestartFromClosestDescendant
+///   NotMatchedGlobally
+///
+/// When NotMatchedGlobally appears, stop selector matching completely since
+/// the succeeding selectors never matches.
+/// It is raised when
+///   Child combinator cannot find the candidate element.
+///   Descendant combinator cannot find the candidate element.
+///
+/// When NotMatchedAndRestartFromClosestDescendant appears, the selector
+/// matching does backtracking and restarts from the closest Descendant
+/// combinator.
+/// It is raised when
+///   NextSibling combinator cannot find the candidate element.
+///   LaterSibling combinator cannot find the candidate element.
+///   Child combinator doesn't match on the found element.
+///
+/// When NotMatchedAndRestartFromClosestLaterSibling appears, the selector
+/// matching does backtracking and restarts from the closest LaterSibling
+/// combinator.
+/// It is raised when
+///   NextSibling combinator doesn't match on the found element.
+///
+/// For example, when the selector "d1 d2 a" is provided and we cannot *find*
+/// an appropriate ancestor element for "d1", this selector matching raises
+/// NotMatchedGlobally since even if "d2" is moved to more upper element, the
+/// candidates for "d1" becomes less than before and d1 .
+///
+/// The next example is siblings. When the selector "b1 + b2 ~ d1 a" is
+/// provided and we cannot *find* an appropriate brother element for b1,
+/// the selector matching raises NotMatchedAndRestartFromClosestDescendant.
+/// The selectors ("b1 + b2 ~") doesn't match and matching restart from "d1".
+///
+/// The additional example is child and sibling. When the selector
+/// "b1 + c1 > b2 ~ d1 a" is provided and the selector "b1" doesn't match on
+/// the element, this "b1" raises NotMatchedAndRestartFromClosestLaterSibling.
+/// However since the selector "c1" raises
+/// NotMatchedAndRestartFromClosestDescendant. So the selector
+/// "b1 + c1 > b2 ~ " doesn't match and restart matching from "d1".
+#[derive(Clone, Copy, Eq, PartialEq)]
+enum SelectorMatchingResult {
+    Matched,
+    NotMatchedAndRestartFromClosestLaterSibling,
+    NotMatchedAndRestartFromClosestDescendant,
+    NotMatchedGlobally,
+}
+
+/// Matches a selector, fast-rejecting against a bloom filter.
+///
+/// We accept an offset to allow consumers to represent and match against
+/// partial selectors (indexed from the right). We use this API design, rather
+/// than having the callers pass a SelectorIter, because creating a SelectorIter
+/// requires dereferencing the selector to get the length, which adds an
+/// unncessary cache miss for cases when we can fast-reject with AncestorHashes
+/// (which the caller can store inline with the selector pointer).
+#[inline(always)]
+pub fn matches_selector<E>(
+    selector: &Selector<E::Impl>,
+    offset: usize,
+    hashes: Option<&AncestorHashes>,
+    element: &E,
+    context: &mut MatchingContext<E::Impl>,
+) -> bool
+where
+    E: Element,
+{
+    // Use the bloom filter to fast-reject.
+    if let Some(hashes) = hashes {
+        if let Some(filter) = context.bloom_filter {
+            if !may_match(hashes, filter) {
+                return false;
+            }
+        }
+    }
+    matches_complex_selector(
+        selector.iter_from(offset),
+        element,
+        context,
+        if selector.is_rightmost(offset) {
+            SubjectOrPseudoElement::Yes
+        } else {
+            SubjectOrPseudoElement::No
+        },
+    )
+}
+
+/// Whether a compound selector matched, and whether it was the rightmost
+/// selector inside the complex selector.
+pub enum CompoundSelectorMatchingResult {
+    /// The selector was fully matched.
+    FullyMatched,
+    /// The compound selector matched, and the next combinator offset is
+    /// `next_combinator_offset`.
+    Matched { next_combinator_offset: usize },
+    /// The selector didn't match.
+    NotMatched,
+}
+
+/// Matches a compound selector belonging to `selector`, starting at offset
+/// `from_offset`, matching left to right.
+///
+/// Requires that `from_offset` points to a `Combinator`.
+///
+/// NOTE(emilio): This doesn't allow to match in the leftmost sequence of the
+/// complex selector, but it happens to be the case we don't need it.
+pub fn matches_compound_selector_from<E>(
+    selector: &Selector<E::Impl>,
+    mut from_offset: usize,
+    context: &mut MatchingContext<E::Impl>,
+    element: &E,
+) -> CompoundSelectorMatchingResult
+where
+    E: Element,
+{
+    if cfg!(debug_assertions) && from_offset != 0 {
+        selector.combinator_at_parse_order(from_offset - 1); // This asserts.
+    }
+
+    let mut local_context = LocalMatchingContext {
+        shared: context,
+        // We have no info if this is an outer selector. This function is called in
+        // an invalidation context, which only calls this for non-subject (i.e.
+        // Non-rightmost) positions.
+        rightmost: SubjectOrPseudoElement::No,
+        quirks_data: None,
+    };
+
+    // Find the end of the selector or the next combinator, then match
+    // backwards, so that we match in the same order as
+    // matches_complex_selector, which is usually faster.
+    let start_offset = from_offset;
+    for component in selector.iter_raw_parse_order_from(from_offset) {
+        if matches!(*component, Component::Combinator(..)) {
+            debug_assert_ne!(from_offset, 0, "Selector started with a combinator?");
+            break;
+        }
+
+        from_offset += 1;
+    }
+
+    debug_assert!(from_offset >= 1);
+    debug_assert!(from_offset <= selector.len());
+
+    let iter = selector.iter_from(selector.len() - from_offset);
+    debug_assert!(
+        iter.clone().next().is_some() ||
+            (from_offset != selector.len() &&
+                matches!(
+                    selector.combinator_at_parse_order(from_offset),
+                    Combinator::SlotAssignment | Combinator::PseudoElement
+                )),
+        "Got the math wrong: {:?} | {:?} | {} {}",
+        selector,
+        selector.iter_raw_match_order().as_slice(),
+        from_offset,
+        start_offset
+    );
+
+    for component in iter {
+        if !matches_simple_selector(component, element, &mut local_context) {
+            return CompoundSelectorMatchingResult::NotMatched;
+        }
+    }
+
+    if from_offset != selector.len() {
+        return CompoundSelectorMatchingResult::Matched {
+            next_combinator_offset: from_offset,
+        };
+    }
+
+    CompoundSelectorMatchingResult::FullyMatched
+}
+
+/// Matches a complex selector.
+#[inline(always)]
+fn matches_complex_selector<E>(
+    mut iter: SelectorIter<E::Impl>,
+    element: &E,
+    context: &mut MatchingContext<E::Impl>,
+    rightmost: SubjectOrPseudoElement,
+) -> bool
+where
+    E: Element,
+{
+    // If this is the special pseudo-element mode, consume the ::pseudo-element
+    // before proceeding, since the caller has already handled that part.
+    if context.matching_mode() == MatchingMode::ForStatelessPseudoElement && !context.is_nested() {
+        // Consume the pseudo.
+        match *iter.next().unwrap() {
+            Component::PseudoElement(ref pseudo) => {
+                if let Some(ref f) = context.pseudo_element_matching_fn {
+                    if !f(pseudo) {
+                        return false;
+                    }
+                }
+            },
+            ref other => {
+                debug_assert!(
+                    false,
+                    "Used MatchingMode::ForStatelessPseudoElement \
+                     in a non-pseudo selector {:?}",
+                    other
+                );
+                return false;
+            },
+        }
+
+        if !iter.matches_for_stateless_pseudo_element() {
+            return false;
+        }
+
+        // Advance to the non-pseudo-element part of the selector.
+        let next_sequence = iter.next_sequence().unwrap();
+        debug_assert_eq!(next_sequence, Combinator::PseudoElement);
+    }
+
+    let result = matches_complex_selector_internal(iter, element, context, rightmost);
+
+    matches!(result, SelectorMatchingResult::Matched)
+}
+
+/// Matches each selector of a list as a complex selector
+fn matches_complex_selector_list<E: Element>(
+    list: &[Selector<E::Impl>],
+    element: &E,
+    context: &mut MatchingContext<E::Impl>,
+    rightmost: SubjectOrPseudoElement,
+) -> bool {
+    for selector in list {
+        if matches_complex_selector(selector.iter(), element, context, rightmost) {
+            return true;
+        }
+    }
+    false
+}
+
+fn matches_relative_selector<E: Element>(
+    relative_selector: &RelativeSelector<E::Impl>,
+    element: &E,
+    context: &mut MatchingContext<E::Impl>,
+    rightmost: SubjectOrPseudoElement,
+) -> bool {
+    // Overall, we want to mark the path that we've traversed so that when an element
+    // is invalidated, we early-reject unnecessary relative selector invalidations.
+    if relative_selector.match_hint.is_descendant_direction() {
+        if context.needs_selector_flags() {
+            element.apply_selector_flags(
+                ElementSelectorFlags::RELATIVE_SELECTOR_SEARCH_DIRECTION_ANCESTOR,
+            );
+        }
+        let mut next_element = element.first_element_child();
+        while let Some(el) = next_element {
+            if context.needs_selector_flags() {
+                el.apply_selector_flags(
+                    ElementSelectorFlags::RELATIVE_SELECTOR_SEARCH_DIRECTION_ANCESTOR,
+                );
+            }
+            let mut matched = matches_complex_selector(
+                relative_selector.selector.iter(),
+                &el,
+                context,
+                rightmost,
+            );
+            if !matched && relative_selector.match_hint.is_subtree() {
+                matched = matches_relative_selector_subtree(
+                    &relative_selector.selector,
+                    &el,
+                    context,
+                    rightmost,
+                );
+            }
+            if matched {
+                return true;
+            }
+            next_element = el.next_sibling_element();
+        }
+    } else {
+        debug_assert!(
+            matches!(
+                relative_selector.match_hint,
+                RelativeSelectorMatchHint::InNextSibling |
+                    RelativeSelectorMatchHint::InNextSiblingSubtree |
+                    RelativeSelectorMatchHint::InSibling |
+                    RelativeSelectorMatchHint::InSiblingSubtree
+            ),
+            "Not descendant direction, but also not sibling direction?"
+        );
+        if context.needs_selector_flags() {
+            element.apply_selector_flags(
+                ElementSelectorFlags::RELATIVE_SELECTOR_SEARCH_DIRECTION_SIBLING,
+            );
+        }
+        let sibling_flag = if relative_selector.match_hint.is_subtree() {
+            ElementSelectorFlags::RELATIVE_SELECTOR_SEARCH_DIRECTION_ANCESTOR_SIBLING
+        } else {
+            ElementSelectorFlags::RELATIVE_SELECTOR_SEARCH_DIRECTION_SIBLING
+        };
+        let mut next_element = element.next_sibling_element();
+        while let Some(el) = next_element {
+            if context.needs_selector_flags() {
+                el.apply_selector_flags(sibling_flag);
+            }
+            let matched = if relative_selector.match_hint.is_subtree() {
+                matches_relative_selector_subtree(
+                    &relative_selector.selector,
+                    &el,
+                    context,
+                    rightmost,
+                )
+            } else {
+                matches_complex_selector(relative_selector.selector.iter(), &el, context, rightmost)
+            };
+            if matched {
+                return true;
+            }
+            if relative_selector.match_hint.is_next_sibling() {
+                break;
+            }
+            next_element = el.next_sibling_element();
+        }
+    }
+    return false;
+}
+
+fn relative_selector_match_early<E: Element>(
+    selector: &RelativeSelector<E::Impl>,
+    element: &E,
+    context: &mut MatchingContext<E::Impl>,
+) -> Option<bool> {
+    if context.matching_for_invalidation() {
+        // In the context of invalidation, we can't use caching/filtering due to
+        // now/then matches. DOM structure also may have changed, so just pretend
+        // that we always match.
+        return Some(!context.in_negation());
+    }
+    // See if we can return a cached result.
+    if let Some(cached) = context
+        .selector_caches
+        .relative_selector
+        .lookup(element.opaque(), selector)
+    {
+        return Some(cached.matched());
+    }
+    // See if we can fast-reject.
+    if context
+        .selector_caches
+        .relative_selector_filter_map
+        .fast_reject(element, selector, context.quirks_mode())
+    {
+        // Alright, add as unmatched to cache.
+        context.selector_caches.relative_selector.add(
+            element.opaque(),
+            selector,
+            RelativeSelectorCachedMatch::NotMatched,
+        );
+        return Some(false);
+    }
+    None
+}
+
+fn match_relative_selectors<E: Element>(
+    selectors: &[RelativeSelector<E::Impl>],
+    element: &E,
+    context: &mut MatchingContext<E::Impl>,
+    rightmost: SubjectOrPseudoElement,
+) -> bool {
+    if context.relative_selector_anchor().is_some() {
+        // FIXME(emilio): This currently can happen with nesting, and it's not fully
+        // correct, arguably. But the ideal solution isn't super-clear either. For now,
+        // cope with it and explicitly reject it at match time. See [1] for discussion.
+        //
+        // [1]: https://github.com/w3c/csswg-drafts/issues/9600
+        return false;
+    }
+    context.nest_for_relative_selector(element.opaque(), |context| {
+        do_match_relative_selectors(selectors, element, context, rightmost)
+    })
+}
+
+/// Matches a relative selector in a list of relative selectors.
+fn do_match_relative_selectors<E: Element>(
+    selectors: &[RelativeSelector<E::Impl>],
+    element: &E,
+    context: &mut MatchingContext<E::Impl>,
+    rightmost: SubjectOrPseudoElement,
+) -> bool {
+    // Due to style sharing implications (See style sharing code), we mark the current styling context
+    // to mark elements considered for :has matching. Additionally, we want to mark the elements themselves,
+    // since we don't want to indiscriminately invalidate every element as a potential anchor.
+    if rightmost == SubjectOrPseudoElement::Yes {
+        context.considered_relative_selector.considered_anchor();
+        if context.needs_selector_flags() {
+            element.apply_selector_flags(ElementSelectorFlags::ANCHORS_RELATIVE_SELECTOR);
+        }
+    } else {
+        context.considered_relative_selector.considered();
+        if context.needs_selector_flags() {
+            element
+                .apply_selector_flags(ElementSelectorFlags::ANCHORS_RELATIVE_SELECTOR_NON_SUBJECT);
+        }
+    }
+
+    for relative_selector in selectors.iter() {
+        if let Some(result) = relative_selector_match_early(relative_selector, element, context) {
+            if result {
+                return true;
+            }
+            // Early return indicates no match, continue to next selector.
+            continue;
+        }
+
+        let matched = matches_relative_selector(relative_selector, element, context, rightmost);
+        context.selector_caches.relative_selector.add(
+            element.opaque(),
+            relative_selector,
+            if matched {
+                RelativeSelectorCachedMatch::Matched
+            } else {
+                RelativeSelectorCachedMatch::NotMatched
+            },
+        );
+        if matched {
+            return true;
+        }
+    }
+
+    false
+}
+
+fn matches_relative_selector_subtree<E: Element>(
+    selector: &Selector<E::Impl>,
+    element: &E,
+    context: &mut MatchingContext<E::Impl>,
+    rightmost: SubjectOrPseudoElement,
+) -> bool {
+    let mut current = element.first_element_child();
+
+    while let Some(el) = current {
+        if context.needs_selector_flags() {
+            el.apply_selector_flags(
+                ElementSelectorFlags::RELATIVE_SELECTOR_SEARCH_DIRECTION_ANCESTOR,
+            );
+        }
+        if matches_complex_selector(selector.iter(), &el, context, rightmost) {
+            return true;
+        }
+
+        if matches_relative_selector_subtree(selector, &el, context, rightmost) {
+            return true;
+        }
+
+        current = el.next_sibling_element();
+    }
+
+    false
+}
+
+/// Whether the :hover and :active quirk applies.
+///
+/// https://quirks.spec.whatwg.org/#the-active-and-hover-quirk
+fn hover_and_active_quirk_applies<Impl: SelectorImpl>(
+    selector_iter: &SelectorIter<Impl>,
+    context: &MatchingContext<Impl>,
+    rightmost: SubjectOrPseudoElement,
+) -> bool {
+    if context.quirks_mode() != QuirksMode::Quirks {
+        return false;
+    }
+
+    if context.is_nested() {
+        return false;
+    }
+
+    // This compound selector had a pseudo-element to the right that we
+    // intentionally skipped.
+    if rightmost == SubjectOrPseudoElement::Yes &&
+        context.matching_mode() == MatchingMode::ForStatelessPseudoElement
+    {
+        return false;
+    }
+
+    selector_iter.clone().all(|simple| match *simple {
+        Component::LocalName(_) |
+        Component::AttributeInNoNamespaceExists { .. } |
+        Component::AttributeInNoNamespace { .. } |
+        Component::AttributeOther(_) |
+        Component::ID(_) |
+        Component::Class(_) |
+        Component::PseudoElement(_) |
+        Component::Negation(_) |
+        Component::Empty |
+        Component::Nth(_) |
+        Component::NthOf(_) => false,
+        Component::NonTSPseudoClass(ref pseudo_class) => pseudo_class.is_active_or_hover(),
+        _ => true,
+    })
+}
+
+#[derive(Clone, Copy, PartialEq)]
+enum SubjectOrPseudoElement {
+    Yes,
+    No,
+}
+
+fn host_for_part<E>(element: &E, context: &MatchingContext<E::Impl>) -> Option<E>
+where
+    E: Element,
+{
+    let scope = context.current_host;
+    let mut curr = element.containing_shadow_host()?;
+    if scope == Some(curr.opaque()) {
+        return Some(curr);
+    }
+    loop {
+        let parent = curr.containing_shadow_host();
+        if parent.as_ref().map(|h| h.opaque()) == scope {
+            return Some(curr);
+        }
+        curr = parent?;
+    }
+}
+
+fn assigned_slot<E>(element: &E, context: &MatchingContext<E::Impl>) -> Option<E>
+where
+    E: Element,
+{
+    debug_assert!(element
+        .assigned_slot()
+        .map_or(true, |s| s.is_html_slot_element()));
+    let scope = context.current_host?;
+    let mut current_slot = element.assigned_slot()?;
+    while current_slot.containing_shadow_host().unwrap().opaque() != scope {
+        current_slot = current_slot.assigned_slot()?;
+    }
+    Some(current_slot)
+}
+
+#[inline(always)]
+fn next_element_for_combinator<E>(
+    element: &E,
+    combinator: Combinator,
+    selector: &SelectorIter<E::Impl>,
+    context: &MatchingContext<E::Impl>,
+) -> Option<E>
+where
+    E: Element,
+{
+    match combinator {
+        Combinator::NextSibling | Combinator::LaterSibling => element.prev_sibling_element(),
+        Combinator::Child | Combinator::Descendant => {
+            match element.parent_element() {
+                Some(e) => return Some(e),
+                None => {},
+            }
+
+            if !element.parent_node_is_shadow_root() {
+                return None;
+            }
+
+            // https://drafts.csswg.org/css-scoping/#host-element-in-tree:
+            //
+            //   For the purpose of Selectors, a shadow host also appears in
+            //   its shadow tree, with the contents of the shadow tree treated
+            //   as its children. (In other words, the shadow host is treated as
+            //   replacing the shadow root node.)
+            //
+            // and also:
+            //
+            //   When considered within its own shadow trees, the shadow host is
+            //   featureless. Only the :host, :host(), and :host-context()
+            //   pseudo-classes are allowed to match it.
+            //
+            // Since we know that the parent is a shadow root, we necessarily
+            // are in a shadow tree of the host, and the next selector will only
+            // match if the selector is a featureless :host selector.
+            if !selector.clone().is_featureless_host_selector() {
+                return None;
+            }
+
+            element.containing_shadow_host()
+        },
+        Combinator::Part => host_for_part(element, context),
+        Combinator::SlotAssignment => assigned_slot(element, context),
+        Combinator::PseudoElement => element.pseudo_element_originating_element(),
+    }
+}
+
+fn matches_complex_selector_internal<E>(
+    mut selector_iter: SelectorIter<E::Impl>,
+    element: &E,
+    context: &mut MatchingContext<E::Impl>,
+    rightmost: SubjectOrPseudoElement,
+) -> SelectorMatchingResult
+where
+    E: Element,
+{
+    debug!(
+        "Matching complex selector {:?} for {:?}",
+        selector_iter, element
+    );
+
+    let matches_compound_selector =
+        matches_compound_selector(&mut selector_iter, element, context, rightmost);
+
+    let combinator = selector_iter.next_sequence();
+    if combinator.map_or(false, |c| c.is_sibling()) {
+        if context.needs_selector_flags() {
+            element.apply_selector_flags(ElementSelectorFlags::HAS_SLOW_SELECTOR_LATER_SIBLINGS);
+        }
+    }
+
+    if !matches_compound_selector {
+        return SelectorMatchingResult::NotMatchedAndRestartFromClosestLaterSibling;
+    }
+
+    let combinator = match combinator {
+        None => return SelectorMatchingResult::Matched,
+        Some(c) => c,
+    };
+
+    let (candidate_not_found, mut rightmost) = match combinator {
+        Combinator::NextSibling | Combinator::LaterSibling => {
+            (SelectorMatchingResult::NotMatchedAndRestartFromClosestDescendant, SubjectOrPseudoElement::No)
+        },
+        Combinator::Child |
+        Combinator::Descendant |
+        Combinator::SlotAssignment |
+        Combinator::Part => (SelectorMatchingResult::NotMatchedGlobally, SubjectOrPseudoElement::No),
+        Combinator::PseudoElement => (SelectorMatchingResult::NotMatchedGlobally, rightmost),
+    };
+
+    // Stop matching :visited as soon as we find a link, or a combinator for
+    // something that isn't an ancestor.
+    let mut visited_handling = if combinator.is_sibling() {
+        VisitedHandlingMode::AllLinksUnvisited
+    } else {
+        context.visited_handling()
+    };
+
+    let mut element = element.clone();
+    loop {
+        if element.is_link() {
+            visited_handling = VisitedHandlingMode::AllLinksUnvisited;
+        }
+
+        element = match next_element_for_combinator(&element, combinator, &selector_iter, &context)
+        {
+            None => return candidate_not_found,
+            Some(next_element) => next_element,
+        };
+
+        let result = context.with_visited_handling_mode(visited_handling, |context| {
+            matches_complex_selector_internal(
+                selector_iter.clone(),
+                &element,
+                context,
+                rightmost,
+            )
+        });
+
+        if !matches!(combinator, Combinator::PseudoElement) {
+            rightmost = SubjectOrPseudoElement::No;
+        }
+
+        match (result, combinator) {
+            // Return the status immediately.
+            (SelectorMatchingResult::Matched, _) |
+            (SelectorMatchingResult::NotMatchedGlobally, _) |
+            (_, Combinator::NextSibling) => {
+                return result;
+            },
+
+            // Upgrade the failure status to
+            // NotMatchedAndRestartFromClosestDescendant.
+            (_, Combinator::PseudoElement) | (_, Combinator::Child) => {
+                return SelectorMatchingResult::NotMatchedAndRestartFromClosestDescendant;
+            },
+
+            // If the failure status is
+            // NotMatchedAndRestartFromClosestDescendant and combinator is
+            // Combinator::LaterSibling, give up this Combinator::LaterSibling
+            // matching and restart from the closest descendant combinator.
+            (
+                SelectorMatchingResult::NotMatchedAndRestartFromClosestDescendant,
+                Combinator::LaterSibling,
+            ) => {
+                return result;
+            },
+
+            // The Combinator::Descendant combinator and the status is
+            // NotMatchedAndRestartFromClosestLaterSibling or
+            // NotMatchedAndRestartFromClosestDescendant, or the
+            // Combinator::LaterSibling combinator and the status is
+            // NotMatchedAndRestartFromClosestDescendant, we can continue to
+            // matching on the next candidate element.
+            _ => {},
+        }
+    }
+}
+
+#[inline]
+fn matches_local_name<E>(element: &E, local_name: &LocalName<E::Impl>) -> bool
+where
+    E: Element,
+{
+    let name = select_name(element, &local_name.name, &local_name.lower_name).borrow();
+    element.has_local_name(name)
+}
+
+fn matches_part<E>(
+    element: &E,
+    parts: &[<E::Impl as SelectorImpl>::Identifier],
+    context: &mut MatchingContext<E::Impl>,
+) -> bool
+where
+    E: Element,
+{
+    let mut hosts = SmallVec::<[E; 4]>::new();
+
+    let mut host = match element.containing_shadow_host() {
+        Some(h) => h,
+        None => return false,
+    };
+
+    let current_host = context.current_host;
+    if current_host != Some(host.opaque()) {
+        loop {
+            let outer_host = host.containing_shadow_host();
+            if outer_host.as_ref().map(|h| h.opaque()) == current_host {
+                break;
+            }
+            let outer_host = match outer_host {
+                Some(h) => h,
+                None => return false,
+            };
+            // TODO(emilio): if worth it, we could early return if
+            // host doesn't have the exportparts attribute.
+            hosts.push(host);
+            host = outer_host;
+        }
+    }
+
+    // Translate the part into the right scope.
+    parts.iter().all(|part| {
+        let mut part = part.clone();
+        for host in hosts.iter().rev() {
+            part = match host.imported_part(&part) {
+                Some(p) => p,
+                None => return false,
+            };
+        }
+        element.is_part(&part)
+    })
+}
+
+fn matches_host<E>(
+    element: &E,
+    selector: Option<&Selector<E::Impl>>,
+    context: &mut MatchingContext<E::Impl>,
+    rightmost: SubjectOrPseudoElement,
+) -> bool
+where
+    E: Element,
+{
+    let host = match context.shadow_host() {
+        Some(h) => h,
+        None => return false,
+    };
+    if host != element.opaque() {
+        return false;
+    }
+    selector.map_or(true, |selector| {
+        context
+            .nest(|context| matches_complex_selector(selector.iter(), element, context, rightmost))
+    })
+}
+
+fn matches_slotted<E>(
+    element: &E,
+    selector: &Selector<E::Impl>,
+    context: &mut MatchingContext<E::Impl>,
+    rightmost: SubjectOrPseudoElement,
+) -> bool
+where
+    E: Element,
+{
+    // <slots> are never flattened tree slottables.
+    if element.is_html_slot_element() {
+        return false;
+    }
+    context.nest(|context| matches_complex_selector(selector.iter(), element, context, rightmost))
+}
+
+fn matches_rare_attribute_selector<E>(
+    element: &E,
+    attr_sel: &AttrSelectorWithOptionalNamespace<E::Impl>,
+) -> bool
+where
+    E: Element,
+{
+    let empty_string;
+    let namespace = match attr_sel.namespace() {
+        Some(ns) => ns,
+        None => {
+            empty_string = crate::parser::namespace_empty_string::<E::Impl>();
+            NamespaceConstraint::Specific(&empty_string)
+        },
+    };
+    element.attr_matches(
+        &namespace,
+        select_name(element, &attr_sel.local_name, &attr_sel.local_name_lower),
+        &match attr_sel.operation {
+            ParsedAttrSelectorOperation::Exists => AttrSelectorOperation::Exists,
+            ParsedAttrSelectorOperation::WithValue {
+                operator,
+                case_sensitivity,
+                ref value,
+            } => AttrSelectorOperation::WithValue {
+                operator,
+                case_sensitivity: to_unconditional_case_sensitivity(case_sensitivity, element),
+                value,
+            },
+        },
+    )
+}
+
+/// Determines whether the given element matches the given compound selector.
+#[inline]
+fn matches_compound_selector<E>(
+    selector_iter: &mut SelectorIter<E::Impl>,
+    element: &E,
+    context: &mut MatchingContext<E::Impl>,
+    rightmost: SubjectOrPseudoElement,
+) -> bool
+where
+    E: Element,
+{
+    let quirks_data = if context.quirks_mode() == QuirksMode::Quirks {
+        Some(selector_iter.clone())
+    } else {
+        None
+    };
+    let mut local_context = LocalMatchingContext {
+        shared: context,
+        rightmost,
+        quirks_data,
+    };
+    selector_iter.all(|simple| matches_simple_selector(simple, element, &mut local_context))
+}
+
+/// Determines whether the given element matches the given single selector.
+fn matches_simple_selector<E>(
+    selector: &Component<E::Impl>,
+    element: &E,
+    context: &mut LocalMatchingContext<E::Impl>,
+) -> bool
+where
+    E: Element,
+{
+    debug_assert!(context.shared.is_nested() || !context.shared.in_negation());
+    let rightmost = context.rightmost;
+    match *selector {
+        Component::ID(ref id) => {
+            element.has_id(id, context.shared.classes_and_ids_case_sensitivity())
+        },
+        Component::Class(ref class) => {
+            element.has_class(class, context.shared.classes_and_ids_case_sensitivity())
+        },
+        Component::LocalName(ref local_name) => matches_local_name(element, local_name),
+        Component::AttributeInNoNamespaceExists {
+            ref local_name,
+            ref local_name_lower,
+        } => element.has_attr_in_no_namespace(select_name(element, local_name, local_name_lower)),
+        Component::AttributeInNoNamespace {
+            ref local_name,
+            ref value,
+            operator,
+            case_sensitivity,
+        } => element.attr_matches(
+            &NamespaceConstraint::Specific(&crate::parser::namespace_empty_string::<E::Impl>()),
+            local_name,
+            &AttrSelectorOperation::WithValue {
+                operator,
+                case_sensitivity: to_unconditional_case_sensitivity(case_sensitivity, element),
+                value,
+            },
+        ),
+        Component::AttributeOther(ref attr_sel) => {
+            matches_rare_attribute_selector(element, attr_sel)
+        },
+        Component::Part(ref parts) => matches_part(element, parts, &mut context.shared),
+        Component::Slotted(ref selector) => {
+            matches_slotted(element, selector, &mut context.shared, rightmost)
+        },
+        Component::PseudoElement(ref pseudo) => {
+            element.match_pseudo_element(pseudo, context.shared)
+        },
+        Component::ExplicitUniversalType | Component::ExplicitAnyNamespace => true,
+        Component::Namespace(_, ref url) | Component::DefaultNamespace(ref url) => {
+            element.has_namespace(&url.borrow())
+        },
+        Component::ExplicitNoNamespace => {
+            let ns = crate::parser::namespace_empty_string::<E::Impl>();
+            element.has_namespace(&ns.borrow())
+        },
+        Component::NonTSPseudoClass(ref pc) => {
+            if let Some(ref iter) = context.quirks_data {
+                if pc.is_active_or_hover() &&
+                    !element.is_link() &&
+                    hover_and_active_quirk_applies(iter, context.shared, context.rightmost)
+                {
+                    return false;
+                }
+            }
+            element.match_non_ts_pseudo_class(pc, &mut context.shared)
+        },
+        Component::Root => element.is_root(),
+        Component::Empty => {
+            if context.shared.needs_selector_flags() {
+                element.apply_selector_flags(ElementSelectorFlags::HAS_EMPTY_SELECTOR);
+            }
+            element.is_empty()
+        },
+        Component::Host(ref selector) => {
+            matches_host(element, selector.as_ref(), &mut context.shared, rightmost)
+        },
+        Component::ParentSelector | Component::Scope => match context.shared.scope_element {
+            Some(ref scope_element) => element.opaque() == *scope_element,
+            None => element.is_root(),
+        },
+        Component::Nth(ref nth_data) => {
+            matches_generic_nth_child(element, context.shared, nth_data, &[], rightmost)
+        },
+        Component::NthOf(ref nth_of_data) => context.shared.nest(|context| {
+            matches_generic_nth_child(
+                element,
+                context,
+                nth_of_data.nth_data(),
+                nth_of_data.selectors(),
+                rightmost,
+            )
+        }),
+        Component::Is(ref list) | Component::Where(ref list) => context.shared.nest(|context| {
+            matches_complex_selector_list(list.slice(), element, context, rightmost)
+        }),
+        Component::Negation(ref list) => context.shared.nest_for_negation(|context| {
+            !matches_complex_selector_list(list.slice(), element, context, rightmost)
+        }),
+        Component::Has(ref relative_selectors) => {
+            match_relative_selectors(relative_selectors, element, context.shared, rightmost)
+        },
+        Component::Combinator(_) => unsafe {
+            debug_unreachable!("Shouldn't try to selector-match combinators")
+        },
+        Component::RelativeSelectorAnchor => {
+            let anchor = context.shared.relative_selector_anchor();
+            // We may match inner relative selectors, in which case we want to always match.
+            anchor.map_or(true, |a| a == element.opaque())
+        },
+        Component::Invalid(..) => false,
+    }
+}
+
+#[inline(always)]
+pub fn select_name<'a, E: Element, T: PartialEq>(
+    element: &E,
+    local_name: &'a T,
+    local_name_lower: &'a T,
+) -> &'a T {
+    if local_name == local_name_lower || element.is_html_element_in_html_document() {
+        local_name_lower
+    } else {
+        local_name
+    }
+}
+
+#[inline(always)]
+pub fn to_unconditional_case_sensitivity<'a, E: Element>(
+    parsed: ParsedCaseSensitivity,
+    element: &E,
+) -> CaseSensitivity {
+    match parsed {
+        ParsedCaseSensitivity::CaseSensitive | ParsedCaseSensitivity::ExplicitCaseSensitive => {
+            CaseSensitivity::CaseSensitive
+        },
+        ParsedCaseSensitivity::AsciiCaseInsensitive => CaseSensitivity::AsciiCaseInsensitive,
+        ParsedCaseSensitivity::AsciiCaseInsensitiveIfInHtmlElementInHtmlDocument => {
+            if element.is_html_element_in_html_document() {
+                CaseSensitivity::AsciiCaseInsensitive
+            } else {
+                CaseSensitivity::CaseSensitive
+            }
+        },
+    }
+}
+
+fn matches_generic_nth_child<E>(
+    element: &E,
+    context: &mut MatchingContext<E::Impl>,
+    nth_data: &NthSelectorData,
+    selectors: &[Selector<E::Impl>],
+    rightmost: SubjectOrPseudoElement,
+) -> bool
+where
+    E: Element,
+{
+    if element.ignores_nth_child_selectors() {
+        return false;
+    }
+    let has_selectors = !selectors.is_empty();
+    let selectors_match =
+        !has_selectors || matches_complex_selector_list(selectors, element, context, rightmost);
+    if context.matching_for_invalidation() {
+        // Skip expensive indexing math in invalidation.
+        return selectors_match && !context.in_negation();
+    }
+
+    let NthSelectorData { ty, a, b, .. } = *nth_data;
+    let is_of_type = ty.is_of_type();
+    if ty.is_only() {
+        debug_assert!(
+            !has_selectors,
+            ":only-child and :only-of-type cannot have a selector list!"
+        );
+        return matches_generic_nth_child(
+            element,
+            context,
+            &NthSelectorData::first(is_of_type),
+            selectors,
+            rightmost,
+        ) && matches_generic_nth_child(
+            element,
+            context,
+            &NthSelectorData::last(is_of_type),
+            selectors,
+            rightmost,
+        );
+    }
+
+    let is_from_end = ty.is_from_end();
+
+    // It's useful to know whether this can only select the first/last element
+    // child for optimization purposes, see the `HAS_EDGE_CHILD_SELECTOR` flag.
+    let is_edge_child_selector = nth_data.is_simple_edge() && !has_selectors;
+
+    if context.needs_selector_flags() {
+        let mut flags = if is_edge_child_selector {
+            ElementSelectorFlags::HAS_EDGE_CHILD_SELECTOR
+        } else if is_from_end {
+            ElementSelectorFlags::HAS_SLOW_SELECTOR
+        } else {
+            ElementSelectorFlags::HAS_SLOW_SELECTOR_LATER_SIBLINGS
+        };
+        flags |= if has_selectors {
+            ElementSelectorFlags::HAS_SLOW_SELECTOR_NTH_OF
+        } else {
+            ElementSelectorFlags::HAS_SLOW_SELECTOR_NTH
+        };
+        element.apply_selector_flags(flags);
+    }
+
+    if !selectors_match {
+        return false;
+    }
+
+    // :first/last-child are rather trivial to match, don't bother with the
+    // cache.
+    if is_edge_child_selector {
+        return if is_from_end {
+            element.next_sibling_element()
+        } else {
+            element.prev_sibling_element()
+        }
+        .is_none();
+    }
+
+    // Lookup or compute the index.
+    let index = if let Some(i) = context
+        .nth_index_cache(is_of_type, is_from_end, selectors)
+        .lookup(element.opaque())
+    {
+        i
+    } else {
+        let i = nth_child_index(
+            element,
+            context,
+            selectors,
+            is_of_type,
+            is_from_end,
+            /* check_cache = */ true,
+            rightmost,
+        );
+        context
+            .nth_index_cache(is_of_type, is_from_end, selectors)
+            .insert(element.opaque(), i);
+        i
+    };
+    debug_assert_eq!(
+        index,
+        nth_child_index(
+            element,
+            context,
+            selectors,
+            is_of_type,
+            is_from_end,
+            /* check_cache = */ false,
+            rightmost,
+        ),
+        "invalid cache"
+    );
+
+    // Is there a non-negative integer n such that An+B=index?
+    match index.checked_sub(b) {
+        None => false,
+        Some(an) => match an.checked_div(a) {
+            Some(n) => n >= 0 && a * n == an,
+            None /* a == 0 */ => an == 0,
+        },
+    }
+}
+
+#[inline]
+fn nth_child_index<E>(
+    element: &E,
+    context: &mut MatchingContext<E::Impl>,
+    selectors: &[Selector<E::Impl>],
+    is_of_type: bool,
+    is_from_end: bool,
+    check_cache: bool,
+    rightmost: SubjectOrPseudoElement,
+) -> i32
+where
+    E: Element,
+{
+    // The traversal mostly processes siblings left to right. So when we walk
+    // siblings to the right when computing NthLast/NthLastOfType we're unlikely
+    // to get cache hits along the way. As such, we take the hit of walking the
+    // siblings to the left checking the cache in the is_from_end case (this
+    // matches what Gecko does). The indices-from-the-left is handled during the
+    // regular look further below.
+    if check_cache &&
+        is_from_end &&
+        !context
+            .nth_index_cache(is_of_type, is_from_end, selectors)
+            .is_empty()
+    {
+        let mut index: i32 = 1;
+        let mut curr = element.clone();
+        while let Some(e) = curr.prev_sibling_element() {
+            curr = e;
+            let matches = if is_of_type {
+                element.is_same_type(&curr)
+            } else if !selectors.is_empty() {
+                matches_complex_selector_list(selectors, &curr, context, rightmost)
+            } else {
+                true
+            };
+            if !matches {
+                continue;
+            }
+            if let Some(i) = context
+                .nth_index_cache(is_of_type, is_from_end, selectors)
+                .lookup(curr.opaque())
+            {
+                return i - index;
+            }
+            index += 1;
+        }
+    }
+
+    let mut index: i32 = 1;
+    let mut curr = element.clone();
+    let next = |e: E| {
+        if is_from_end {
+            e.next_sibling_element()
+        } else {
+            e.prev_sibling_element()
+        }
+    };
+    while let Some(e) = next(curr) {
+        curr = e;
+        let matches = if is_of_type {
+            element.is_same_type(&curr)
+        } else if !selectors.is_empty() {
+            matches_complex_selector_list(selectors, &curr, context, rightmost)
+        } else {
+            true
+        };
+        if !matches {
+            continue;
+        }
+        // If we're computing indices from the left, check each element in the
+        // cache. We handle the indices-from-the-right case at the top of this
+        // function.
+        if !is_from_end && check_cache {
+            if let Some(i) = context
+                .nth_index_cache(is_of_type, is_from_end, selectors)
+                .lookup(curr.opaque())
+            {
+                return i + index;
+            }
+        }
+        index += 1;
+    }
+
+    index
+}
diff --git a/servo/components/selectors/nth_index_cache.rs b/servo/components/selectors/nth_index_cache.rs
new file mode 100644
index 0000000000..b4b41578d0
--- /dev/null
+++ b/servo/components/selectors/nth_index_cache.rs
@@ -0,0 +1,102 @@
+/* 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 std::hash::Hash;
+
+use crate::{parser::Selector, tree::OpaqueElement, SelectorImpl};
+use fxhash::FxHashMap;
+
+/// A cache to speed up matching of nth-index-like selectors.
+///
+/// See [1] for some discussion around the design tradeoffs.
+///
+/// [1] https://bugzilla.mozilla.org/show_bug.cgi?id=1401855#c3
+#[derive(Default)]
+pub struct NthIndexCache {
+    nth: NthIndexCacheInner,
+    nth_of_selectors: NthIndexOfSelectorsCaches,
+    nth_last: NthIndexCacheInner,
+    nth_last_of_selectors: NthIndexOfSelectorsCaches,
+    nth_of_type: NthIndexCacheInner,
+    nth_last_of_type: NthIndexCacheInner,
+}
+
+impl NthIndexCache {
+    /// Gets the appropriate cache for the given parameters.
+    pub fn get<Impl: SelectorImpl>(
+        &mut self,
+        is_of_type: bool,
+        is_from_end: bool,
+        selectors: &[Selector<Impl>],
+    ) -> &mut NthIndexCacheInner {
+        if is_of_type {
+            return if is_from_end {
+                &mut self.nth_last_of_type
+            } else {
+                &mut self.nth_of_type
+            };
+        }
+        if !selectors.is_empty() {
+            return if is_from_end {
+                self.nth_last_of_selectors.lookup(selectors)
+            } else {
+                self.nth_of_selectors.lookup(selectors)
+            };
+        }
+        if is_from_end {
+            &mut self.nth_last
+        } else {
+            &mut self.nth
+        }
+    }
+}
+
+#[derive(Hash, Eq, PartialEq)]
+struct SelectorListCacheKey(usize);
+
+/// Use the selector list's pointer as the cache key
+impl SelectorListCacheKey {
+    // :nth-child of selectors are reference-counted with `ThinArc`, so we know their pointers are stable.
+    fn new<Impl: SelectorImpl>(selectors: &[Selector<Impl>]) -> Self {
+        Self(selectors.as_ptr() as usize)
+    }
+}
+
+/// Use a different map of cached indices per :nth-child's or :nth-last-child's selector list
+#[derive(Default)]
+pub struct NthIndexOfSelectorsCaches(FxHashMap<SelectorListCacheKey, NthIndexCacheInner>);
+
+/// Get or insert a map of cached incides for the selector list of this
+/// particular :nth-child or :nth-last-child pseudoclass
+impl NthIndexOfSelectorsCaches {
+    pub fn lookup<Impl: SelectorImpl>(
+        &mut self,
+        selectors: &[Selector<Impl>],
+    ) -> &mut NthIndexCacheInner {
+        self.0
+            .entry(SelectorListCacheKey::new(selectors))
+            .or_default()
+    }
+}
+
+/// The concrete per-pseudo-class cache.
+#[derive(Default)]
+pub struct NthIndexCacheInner(FxHashMap<OpaqueElement, i32>);
+
+impl NthIndexCacheInner {
+    /// Does a lookup for a given element in the cache.
+    pub fn lookup(&mut self, el: OpaqueElement) -> Option<i32> {
+        self.0.get(&el).copied()
+    }
+
+    /// Inserts an entry into the cache.
+    pub fn insert(&mut self, element: OpaqueElement, index: i32) {
+        self.0.insert(element, index);
+    }
+
+    /// Returns whether the cache is empty.
+    pub fn is_empty(&self) -> bool {
+        self.0.is_empty()
+    }
+}
diff --git a/servo/components/selectors/parser.rs b/servo/components/selectors/parser.rs
new file mode 100644
index 0000000000..792d4eb8bc
--- /dev/null
+++ b/servo/components/selectors/parser.rs
@@ -0,0 +1,4483 @@
+/* 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;
+
+/// 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
+    }
+}
+
+/// 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: u8 {
+        /// 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;
+    }
+}
+
+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)
+    }
+
+    #[inline]
+    fn allows_combinators(self) -> bool {
+        !self.intersects(Self::DISALLOW_COMBINATORS)
+    }
+}
+
+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 the `:where` pseudo-class.
+    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, ToShmem)]
+#[shmem(no_bounds)]
+pub struct SelectorList<Impl: SelectorImpl>(
+    #[shmem(field_bound)] ThinArcUnion<SpecificityAndFlags, Component<Impl>, (), Selector<Impl>>,
+);
+
+impl<Impl: SelectorImpl> SelectorList<Impl> {
+    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,
+    /// Treat as parse error if any selector begins with a combinator.
+    No,
+}
+
+impl<Impl: SelectorImpl> SelectorList<Impl> {
+    /// Returns a selector list with a single `&`
+    pub fn ampersand() -> Self {
+        Self::from_one(Selector::ampersand())
+    }
+
+    /// 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,
+        )
+    }
+
+    #[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>>;
+
+/// 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, ToShmem)]
+#[shmem(no_bounds)]
+#[repr(transparent)]
+pub struct Selector<Impl: SelectorImpl>(#[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 ampersand() -> Self {
+        Self(ThinArc::from_header_and_iter(
+            SpecificityAndFlags {
+                specificity: 0,
+                flags: SelectorFlags::HAS_PARENT,
+            },
+            std::iter::once(Component::ParentSelector),
+        ))
+    }
+
+    #[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 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 is a featureless :host selector, with no combinators to the left, and
+    /// optionally has a pseudo-element to the right.
+    #[inline]
+    pub fn is_featureless_host_selector_or_pseudo_element(&self) -> bool {
+        let flags = self.flags();
+        flags.intersects(SelectorFlags::HAS_HOST) &&
+            !flags.intersects(SelectorFlags::HAS_NON_FEATURELESS_COMPONENT)
+    }
+
+    /// 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))
+    }
+
+    #[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());
+
+        let mut specificity = Specificity::from(self.specificity());
+        let mut flags = self.flags() - SelectorFlags::HAS_PARENT;
+
+        fn replace_parent_on_selector_list<Impl: SelectorImpl>(
+            orig: &[Selector<Impl>],
+            parent: &SelectorList<Impl>,
+            specificity: &mut Specificity,
+            flags: &mut SelectorFlags,
+            propagate_specificity: bool,
+            flags_to_propagate: SelectorFlags,
+        ) -> Option<SelectorList<Impl>> {
+            if !orig.iter().any(|s| s.has_parent_selector()) {
+                return None;
+            }
+
+            let result = SelectorList::from_iter(orig.iter().map(|s| {
+                if !s.has_parent_selector() {
+                    return s.clone();
+                }
+                s.replace_parent_selector(parent)
+            }));
+
+            let result_specificity_and_flags =
+                selector_list_specificity_and_flags(result.slice().iter());
+            if propagate_specificity {
+                *specificity += Specificity::from(
+                    result_specificity_and_flags.specificity -
+                        selector_list_specificity_and_flags(orig.iter()).specificity,
+                );
+            }
+            flags.insert(
+                result_specificity_and_flags
+                    .flags
+                    .intersection(flags_to_propagate),
+            );
+            Some(result)
+        }
+
+        fn replace_parent_on_relative_selector_list<Impl: SelectorImpl>(
+            orig: &[RelativeSelector<Impl>],
+            parent: &SelectorList<Impl>,
+            specificity: &mut Specificity,
+            flags: &mut SelectorFlags,
+            flags_to_propagate: 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);
+            flags.insert(
+                result_specificity_and_flags
+                    .flags
+                    .intersection(flags_to_propagate),
+            );
+            *specificity += Specificity::from(
+                result_specificity_and_flags.specificity -
+                    relative_selector_list_specificity_and_flags(orig).specificity,
+            );
+            result
+        }
+
+        fn replace_parent_on_selector<Impl: SelectorImpl>(
+            orig: &Selector<Impl>,
+            parent: &SelectorList<Impl>,
+            specificity: &mut Specificity,
+            flags: &mut SelectorFlags,
+            flags_to_propagate: SelectorFlags,
+        ) -> Selector<Impl> {
+            if !orig.has_parent_selector() {
+                return orig.clone();
+            }
+            let new_selector = orig.replace_parent_selector(parent);
+            *specificity += Specificity::from(new_selector.specificity() - orig.specificity());
+            flags.insert(new_selector.flags().intersection(flags_to_propagate));
+            new_selector
+        }
+
+        let mut items = if !self.has_parent_selector() {
+            // Implicit `&` plus descendant combinator.
+            let iter = self.iter_raw_match_order();
+            let len = iter.len() + 2;
+            specificity += Specificity::from(parent_specificity_and_flags.specificity);
+            flags.insert(
+                parent_specificity_and_flags
+                    .flags
+                    .intersection(SelectorFlags::for_nesting()),
+            );
+            let iter = iter
+                .cloned()
+                .chain(std::iter::once(Component::Combinator(
+                    Combinator::Descendant,
+                )))
+                .chain(std::iter::once(Component::Is(parent.clone())));
+            UniqueArc::from_header_and_iter_with_size(Default::default(), iter, len)
+        } else {
+            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 |
+                    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
+                                .intersection(SelectorFlags::for_nesting()),
+                        );
+                        Is(parent.clone())
+                    },
+                    Negation(ref selectors) => {
+                        Negation(
+                            replace_parent_on_selector_list(
+                                selectors.slice(),
+                                parent,
+                                &mut specificity,
+                                &mut flags,
+                                /* propagate_specificity = */ true,
+                                SelectorFlags::for_nesting(),
+                            )
+                            .unwrap_or_else(|| selectors.clone()),
+                        )
+                    },
+                    Is(ref selectors) => {
+                        Is(replace_parent_on_selector_list(
+                            selectors.slice(),
+                            parent,
+                            &mut specificity,
+                            &mut flags,
+                            /* propagate_specificity = */ true,
+                            SelectorFlags::for_nesting(),
+                        )
+                        .unwrap_or_else(|| selectors.clone()))
+                    },
+                    Where(ref selectors) => {
+                        Where(
+                            replace_parent_on_selector_list(
+                                selectors.slice(),
+                                parent,
+                                &mut specificity,
+                                &mut flags,
+                                /* propagate_specificity = */ false,
+                                SelectorFlags::for_nesting(),
+                            )
+                            .unwrap_or_else(|| selectors.clone()),
+                        )
+                    },
+                    Has(ref selectors) => Has(replace_parent_on_relative_selector_list(
+                        selectors,
+                        parent,
+                        &mut specificity,
+                        &mut flags,
+                        SelectorFlags::for_nesting(),
+                    )
+                    .into_boxed_slice()),
+
+                    Host(Some(ref selector)) => Host(Some(replace_parent_on_selector(
+                        selector,
+                        parent,
+                        &mut specificity,
+                        &mut flags,
+                        SelectorFlags::for_nesting() - 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,
+                            SelectorFlags::for_nesting(),
+                        );
+                        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,
+                        SelectorFlags::for_nesting(),
+                    )),
+                }
+            });
+            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 host selector, with no
+    /// combinators to the left.
+    #[inline]
+    pub(crate) fn is_featureless_host_selector(&mut self) -> bool {
+        self.selector_length() > 0 &&
+            self.all(|component| component.matches_featureless_host()) &&
+            self.next_sequence().is_none()
+    }
+
+    #[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, 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, ToShmem)]
+#[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, ToShmem)]
+#[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()
+    }
+
+    /// 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, ToShmem)]
+#[shmem(no_bounds)]
+pub struct NthOfSelectorData<Impl: SelectorImpl>(
+    #[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, 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,
+        };
+
+        for combinator in CombinatorIter::new(
+            relative_selector
+                .selector
+                .iter_skip_relative_selector_anchor(),
+        ) {
+            match combinator {
+                Combinator::Descendant | Combinator::Child => {
+                    result.child_or_descendants += 1;
+                },
+                Combinator::NextSibling | Combinator::LaterSibling => {
+                    result.adjacent_or_next_siblings += 1;
+                },
+                Combinator::Part | Combinator::PseudoElement | Combinator::SlotAssignment => {
+                    continue
+                },
+            };
+        }
+        result
+    }
+
+    /// Get the match hint based on the current combinator count.
+    pub fn get_match_hint(&self) -> RelativeSelectorMatchHint {
+        RelativeSelectorMatchHint::new(
+            self.relative_combinator,
+            self.child_or_descendants != 0,
+            self.adjacent_or_next_siblings != 0,
+        )
+    }
+}
+
+/// Storage for a relative selector.
+#[derive(Clone, Eq, PartialEq, ToShmem)]
+#[shmem(no_bounds)]
+pub struct RelativeSelector<Impl: SelectorImpl> {
+    /// Match space constraining hint.
+    pub match_hint: RelativeSelectorMatchHint,
+    /// The selector. Guaranteed to contain `RelativeSelectorAnchor` and the relative combinator in parse order.
+    #[shmem(field_bound)]
+    pub selector: Selector<Impl>,
+}
+
+bitflags! {
+    /// Composition of combinators in a given selector, not traversing selectors of pseudoclasses.
+    #[derive(Clone, Debug, Eq, PartialEq)]
+    struct CombinatorComposition: u8 {
+        const DESCENDANTS = 1 << 0;
+        const SIBLINGS = 1 << 1;
+    }
+}
+
+impl CombinatorComposition {
+    fn for_relative_selector<Impl: SelectorImpl>(inner_selector: &Selector<Impl>) -> Self {
+        let mut result = CombinatorComposition::empty();
+        for combinator in CombinatorIter::new(inner_selector.iter_skip_relative_selector_anchor()) {
+            match combinator {
+                Combinator::Descendant | Combinator::Child => {
+                    result.insert(Self::DESCENDANTS);
+                },
+                Combinator::NextSibling | Combinator::LaterSibling => {
+                    result.insert(Self::SIBLINGS);
+                },
+                Combinator::Part | Combinator::PseudoElement | Combinator::SlotAssignment => {
+                    continue
+                },
+            };
+            if result.is_all() {
+                break;
+            }
+        }
+        return result;
+    }
+}
+
+impl<Impl: SelectorImpl> RelativeSelector<Impl> {
+    fn from_selector_list(selector_list: SelectorList<Impl>) -> Box<[Self]> {
+        let vec: Vec<Self> = selector_list
+            .slice()
+            .iter()
+            .map(|selector| {
+                // It's more efficient to keep track of all this during the parse time, but that seems like a lot of special
+                // case handling for what it's worth.
+                if cfg!(debug_assertions) {
+                    let relative_selector_anchor = selector.iter_raw_parse_order_from(0).next();
+                    debug_assert!(
+                        relative_selector_anchor.is_some(),
+                        "Relative selector is empty"
+                    );
+                    debug_assert!(
+                        matches!(
+                            relative_selector_anchor.unwrap(),
+                            Component::RelativeSelectorAnchor
+                        ),
+                        "Relative selector anchor is missing"
+                    );
+                }
+                // Leave a hint for narrowing down the search space when we're matching.
+                let composition = CombinatorComposition::for_relative_selector(&selector);
+                let match_hint = RelativeSelectorMatchHint::new(
+                    selector.combinator_at_parse_order(1),
+                    composition.intersects(CombinatorComposition::DESCENDANTS),
+                    composition.intersects(CombinatorComposition::SIBLINGS),
+                );
+                RelativeSelector {
+                    match_hint,
+                    selector: selector.clone(),
+                }
+            })
+            .collect();
+        vec.into_boxed_slice()
+    }
+}
+
+/// A CSS simple selector or combinator. We store both in the same enum for
+/// optimal packing and cache performance, see [1].
+///
+/// [1] https://bugzilla.mozilla.org/show_bug.cgi?id=1357973
+#[derive(Clone, Eq, PartialEq, ToShmem)]
+#[shmem(no_bounds)]
+pub enum Component<Impl: SelectorImpl> {
+    LocalName(LocalName<Impl>),
+
+    ID(#[shmem(field_bound)] Impl::Identifier),
+    Class(#[shmem(field_bound)] Impl::Identifier),
+
+    AttributeInNoNamespaceExists {
+        #[shmem(field_bound)]
+        local_name: Impl::LocalName,
+        local_name_lower: Impl::LocalName,
+    },
+    // Used only when local_name is already lowercase.
+    AttributeInNoNamespace {
+        local_name: Impl::LocalName,
+        operator: AttrSelectorOperator,
+        #[shmem(field_bound)]
+        value: Impl::AttrValue,
+        case_sensitivity: ParsedCaseSensitivity,
+    },
+    // Use a Box in the less common cases with more data to keep size_of::<Component>() small.
+    AttributeOther(Box<AttrSelectorWithOptionalNamespace<Impl>>),
+
+    ExplicitUniversalType,
+    ExplicitAnyNamespace,
+
+    ExplicitNoNamespace,
+    DefaultNamespace(#[shmem(field_bound)] Impl::NamespaceUrl),
+    Namespace(
+        #[shmem(field_bound)] Impl::NamespacePrefix,
+        #[shmem(field_bound)] Impl::NamespaceUrl,
+    ),
+
+    /// Pseudo-classes
+    Negation(SelectorList<Impl>),
+    Root,
+    Empty,
+    Scope,
+    ParentSelector,
+    Nth(NthSelectorData),
+    NthOf(NthOfSelectorData<Impl>),
+    NonTSPseudoClass(#[shmem(field_bound)] Impl::NonTSPseudoClass),
+    /// The ::slotted() pseudo-element:
+    ///
+    /// https://drafts.csswg.org/css-scoping/#slotted-pseudo
+    ///
+    /// The selector here is a compound selector, that is, no combinators.
+    ///
+    /// NOTE(emilio): This should support a list of selectors, but as of this
+    /// writing no other browser does, and that allows them to put ::slotted()
+    /// in the rule hash, so we do that too.
+    ///
+    /// See https://github.com/w3c/csswg-drafts/issues/2158
+    Slotted(Selector<Impl>),
+    /// The `::part` pseudo-element.
+    ///   https://drafts.csswg.org/css-shadow-parts/#part
+    Part(#[shmem(field_bound)] Box<[Impl::Identifier]>),
+    /// The `:host` pseudo-class:
+    ///
+    /// https://drafts.csswg.org/css-scoping/#host-selector
+    ///
+    /// NOTE(emilio): This should support a list of selectors, but as of this
+    /// writing no other browser does, and that allows them to put :host()
+    /// in the rule hash, so we do that too.
+    ///
+    /// See https://github.com/w3c/csswg-drafts/issues/2158
+    Host(Option<Selector<Impl>>),
+    /// The `:where` pseudo-class.
+    ///
+    /// https://drafts.csswg.org/selectors/#zero-matches
+    ///
+    /// The inner argument is conceptually a SelectorList, but we move the
+    /// selectors to the heap to keep Component small.
+    Where(SelectorList<Impl>),
+    /// The `:is` pseudo-class.
+    ///
+    /// https://drafts.csswg.org/selectors/#matches-pseudo
+    ///
+    /// Same comment as above re. the argument.
+    Is(SelectorList<Impl>),
+    /// The `:has` pseudo-class.
+    ///
+    /// https://drafts.csswg.org/selectors/#has-pseudo
+    ///
+    /// Same comment as above re. the argument.
+    Has(Box<[RelativeSelector<Impl>]>),
+    /// An invalid selector inside :is() / :where().
+    Invalid(Arc<String>),
+    /// An implementation-dependent pseudo-element selector.
+    PseudoElement(#[shmem(field_bound)] Impl::PseudoElement),
+
+    Combinator(Combinator),
+
+    /// Used only for relative selectors, which starts with a combinator
+    /// (With an implied descendant combinator if not specified).
+    ///
+    /// https://drafts.csswg.org/selectors-4/#typedef-relative-selector
+    RelativeSelectorAnchor,
+}
+
+impl<Impl: SelectorImpl> Component<Impl> {
+    /// Returns true if this is a combinator.
+    #[inline]
+    pub fn is_combinator(&self) -> bool {
+        matches!(*self, Component::Combinator(_))
+    }
+
+    /// Returns true if this is a :host() selector.
+    #[inline]
+    pub fn is_host(&self) -> bool {
+        matches!(*self, Component::Host(..))
+    }
+
+    /// Returns true if this is a :host() selector.
+    #[inline]
+    pub fn matches_featureless_host(&self) -> bool {
+        match *self {
+            Component::Host(..) => true,
+            Component::Where(ref l) | Component::Is(ref l) => {
+                // TODO(emilio): For now we use .all() rather than .any(), because not doing so
+                // brings up a fair amount of extra complexity (we can't make the decision on
+                // whether to walk out statically).
+                l.slice()
+                    .iter()
+                    .all(|i| i.is_featureless_host_selector_or_pseudo_element())
+            },
+            _ => false,
+        }
+    }
+
+    /// Returns the value as a combinator if applicable, None otherwise.
+    pub fn as_combinator(&self) -> Option<Combinator> {
+        match *self {
+            Component::Combinator(c) => Some(c),
+            _ => None,
+        }
+    }
+
+    /// Whether this component is valid after a pseudo-element. Only intended
+    /// for sanity-checking.
+    pub fn maybe_allowed_after_pseudo_element(&self) -> bool {
+        match *self {
+            Component::NonTSPseudoClass(..) => true,
+            Component::Negation(ref selectors) |
+            Component::Is(ref selectors) |
+            Component::Where(ref selectors) => selectors.slice().iter().all(|selector| {
+                selector
+                    .iter_raw_match_order()
+                    .all(|c| c.maybe_allowed_after_pseudo_element())
+            }),
+            _ => false,
+        }
+    }
+
+    /// Whether a given selector should match for stateless pseudo-elements.
+    ///
+    /// This is a bit subtle: Only selectors that return true in
+    /// `maybe_allowed_after_pseudo_element` should end up here, and
+    /// `NonTSPseudoClass` never matches (as it is a stateless pseudo after
+    /// all).
+    fn matches_for_stateless_pseudo_element(&self) -> bool {
+        debug_assert!(
+            self.maybe_allowed_after_pseudo_element(),
+            "Someone messed up pseudo-element parsing: {:?}",
+            *self
+        );
+        match *self {
+            Component::Negation(ref selectors) => !selectors.slice().iter().all(|selector| {
+                selector
+                    .iter_raw_match_order()
+                    .all(|c| c.matches_for_stateless_pseudo_element())
+            }),
+            Component::Is(ref selectors) | Component::Where(ref selectors) => {
+                selectors.slice().iter().any(|selector| {
+                    selector
+                        .iter_raw_match_order()
+                        .all(|c| c.matches_for_stateless_pseudo_element())
+                })
+            },
+            _ => false,
+        }
+    }
+
+    pub fn visit<V>(&self, visitor: &mut V) -> bool
+    where
+        V: SelectorVisitor<Impl = Impl>,
+    {
+        use self::Component::*;
+        if !visitor.visit_simple_selector(self) {
+            return false;
+        }
+
+        match *self {
+            Slotted(ref selector) => {
+                if !selector.visit(visitor) {
+                    return false;
+                }
+            },
+            Host(Some(ref selector)) => {
+                if !selector.visit(visitor) {
+                    return false;
+                }
+            },
+            AttributeInNoNamespaceExists {
+                ref local_name,
+                ref local_name_lower,
+            } => {
+                if !visitor.visit_attribute_selector(
+                    &NamespaceConstraint::Specific(&namespace_empty_string::<Impl>()),
+                    local_name,
+                    local_name_lower,
+                ) {
+                    return false;
+                }
+            },
+            AttributeInNoNamespace { ref local_name, .. } => {
+                if !visitor.visit_attribute_selector(
+                    &NamespaceConstraint::Specific(&namespace_empty_string::<Impl>()),
+                    local_name,
+                    local_name,
+                ) {
+                    return false;
+                }
+            },
+            AttributeOther(ref attr_selector) => {
+                let empty_string;
+                let namespace = match attr_selector.namespace() {
+                    Some(ns) => ns,
+                    None => {
+                        empty_string = crate::parser::namespace_empty_string::<Impl>();
+                        NamespaceConstraint::Specific(&empty_string)
+                    },
+                };
+                if !visitor.visit_attribute_selector(
+                    &namespace,
+                    &attr_selector.local_name,
+                    &attr_selector.local_name_lower,
+                ) {
+                    return false;
+                }
+            },
+
+            NonTSPseudoClass(ref pseudo_class) => {
+                if !pseudo_class.visit(visitor) {
+                    return false;
+                }
+            },
+            Negation(ref list) | Is(ref list) | Where(ref list) => {
+                let list_kind = SelectorListKind::from_component(self);
+                debug_assert!(!list_kind.is_empty());
+                if !visitor.visit_selector_list(list_kind, list.slice()) {
+                    return false;
+                }
+            },
+            NthOf(ref nth_of_data) => {
+                if !visitor.visit_selector_list(SelectorListKind::NTH_OF, nth_of_data.selectors()) {
+                    return false;
+                }
+            },
+            Has(ref list) => {
+                if !visitor.visit_relative_selector_list(list) {
+                    return false;
+                }
+            },
+            _ => {},
+        }
+
+        true
+    }
+
+    // Returns true if this has any selector that requires an index calculation. e.g.
+    // :nth-child, :first-child, etc. For nested selectors, return true only if the
+    // indexed selector is in its subject compound.
+    pub fn has_indexed_selector_in_subject(&self) -> bool {
+        match *self {
+            Component::NthOf(..) | Component::Nth(..) => return true,
+            Component::Is(ref selectors) |
+            Component::Where(ref selectors) |
+            Component::Negation(ref selectors) => {
+                // Check the subject compound.
+                for selector in selectors.slice() {
+                    let mut iter = selector.iter();
+                    while let Some(c) = iter.next() {
+                        if c.has_indexed_selector_in_subject() {
+                            return true;
+                        }
+                    }
+                }
+            },
+            _ => (),
+        };
+        false
+    }
+}
+
+#[derive(Clone, Eq, PartialEq, ToShmem)]
+#[shmem(no_bounds)]
+pub struct LocalName<Impl: SelectorImpl> {
+    #[shmem(field_bound)]
+    pub name: Impl::LocalName,
+    pub lower_name: Impl::LocalName,
+}
+
+impl<Impl: SelectorImpl> Debug for Selector<Impl> {
+    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
+        f.write_str("Selector(")?;
+        self.to_css(f)?;
+        write!(
+            f,
+            ", specificity = {:#x}, flags = {:?})",
+            self.specificity(),
+            self.flags()
+        )
+    }
+}
+
+impl<Impl: SelectorImpl> Debug for Component<Impl> {
+    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
+        self.to_css(f)
+    }
+}
+impl<Impl: SelectorImpl> Debug for AttrSelectorWithOptionalNamespace<Impl> {
+    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
+        self.to_css(f)
+    }
+}
+impl<Impl: SelectorImpl> Debug for LocalName<Impl> {
+    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
+        self.to_css(f)
+    }
+}
+
+fn serialize_selector_list<'a, Impl, I, W>(iter: I, dest: &mut W) -> fmt::Result
+where
+    Impl: SelectorImpl,
+    I: Iterator<Item = &'a Selector<Impl>>,
+    W: fmt::Write,
+{
+    let mut first = true;
+    for selector in iter {
+        if !first {
+            dest.write_str(", ")?;
+        }
+        first = false;
+        selector.to_css(dest)?;
+    }
+    Ok(())
+}
+
+impl<Impl: SelectorImpl> ToCss for SelectorList<Impl> {
+    fn to_css<W>(&self, dest: &mut W) -> fmt::Result
+    where
+        W: fmt::Write,
+    {
+        serialize_selector_list(self.slice().iter(), dest)
+    }
+}
+
+impl<Impl: SelectorImpl> ToCss for Selector<Impl> {
+    fn to_css<W>(&self, dest: &mut W) -> fmt::Result
+    where
+        W: fmt::Write,
+    {
+        // Compound selectors invert the order of their contents, so we need to
+        // undo that during serialization.
+        //
+        // This two-iterator strategy involves walking over the selector twice.
+        // We could do something more clever, but selector serialization probably
+        // isn't hot enough to justify it, and the stringification likely
+        // dominates anyway.
+        //
+        // NB: A parse-order iterator is a Rev<>, which doesn't expose as_slice(),
+        // which we need for |split|. So we split by combinators on a match-order
+        // sequence and then reverse.
+
+        let mut combinators = self
+            .iter_raw_match_order()
+            .rev()
+            .filter_map(|x| x.as_combinator());
+        let compound_selectors = self
+            .iter_raw_match_order()
+            .as_slice()
+            .split(|x| x.is_combinator())
+            .rev();
+
+        let mut combinators_exhausted = false;
+        for compound in compound_selectors {
+            debug_assert!(!combinators_exhausted);
+
+            // https://drafts.csswg.org/cssom/#serializing-selectors
+            if compound.is_empty() {
+                continue;
+            }
+            if let Component::RelativeSelectorAnchor = compound.first().unwrap() {
+                debug_assert!(
+                    compound.len() == 1,
+                    "RelativeLeft should only be a simple selector"
+                );
+                combinators.next().unwrap().to_css_relative(dest)?;
+                continue;
+            }
+
+            // 1. If there is only one simple selector in the compound selectors
+            //    which is a universal selector, append the result of
+            //    serializing the universal selector to s.
+            //
+            // Check if `!compound.empty()` first--this can happen if we have
+            // something like `... > ::before`, because we store `>` and `::`
+            // both as combinators internally.
+            //
+            // If we are in this case, after we have serialized the universal
+            // selector, we skip Step 2 and continue with the algorithm.
+            let (can_elide_namespace, first_non_namespace) = match compound[0] {
+                Component::ExplicitAnyNamespace |
+                Component::ExplicitNoNamespace |
+                Component::Namespace(..) => (false, 1),
+                Component::DefaultNamespace(..) => (true, 1),
+                _ => (true, 0),
+            };
+            let mut perform_step_2 = true;
+            let next_combinator = combinators.next();
+            if first_non_namespace == compound.len() - 1 {
+                match (next_combinator, &compound[first_non_namespace]) {
+                    // We have to be careful here, because if there is a
+                    // pseudo element "combinator" there isn't really just
+                    // the one simple selector. Technically this compound
+                    // selector contains the pseudo element selector as well
+                    // -- Combinator::PseudoElement, just like
+                    // Combinator::SlotAssignment, don't exist in the
+                    // spec.
+                    (Some(Combinator::PseudoElement), _) |
+                    (Some(Combinator::SlotAssignment), _) => (),
+                    (_, &Component::ExplicitUniversalType) => {
+                        // Iterate over everything so we serialize the namespace
+                        // too.
+                        for simple in compound.iter() {
+                            simple.to_css(dest)?;
+                        }
+                        // Skip step 2, which is an "otherwise".
+                        perform_step_2 = false;
+                    },
+                    _ => (),
+                }
+            }
+
+            // 2. Otherwise, for each simple selector in the compound selectors
+            //    that is not a universal selector of which the namespace prefix
+            //    maps to a namespace that is not the default namespace
+            //    serialize the simple selector and append the result to s.
+            //
+            // See https://github.com/w3c/csswg-drafts/issues/1606, which is
+            // proposing to change this to match up with the behavior asserted
+            // in cssom/serialize-namespaced-type-selectors.html, which the
+            // following code tries to match.
+            if perform_step_2 {
+                for simple in compound.iter() {
+                    if let Component::ExplicitUniversalType = *simple {
+                        // Can't have a namespace followed by a pseudo-element
+                        // selector followed by a universal selector in the same
+                        // compound selector, so we don't have to worry about the
+                        // real namespace being in a different `compound`.
+                        if can_elide_namespace {
+                            continue;
+                        }
+                    }
+                    simple.to_css(dest)?;
+                }
+            }
+
+            // 3. If this is not the last part of the chain of the selector
+            //    append a single SPACE (U+0020), followed by the combinator
+            //    ">", "+", "~", ">>", "||", as appropriate, followed by another
+            //    single SPACE (U+0020) if the combinator was not whitespace, to
+            //    s.
+            match next_combinator {
+                Some(c) => c.to_css(dest)?,
+                None => combinators_exhausted = true,
+            };
+
+            // 4. If this is the last part of the chain of the selector and
+            //    there is a pseudo-element, append "::" followed by the name of
+            //    the pseudo-element, to s.
+            //
+            // (we handle this above)
+        }
+
+        Ok(())
+    }
+}
+
+impl Combinator {
+    fn to_css_internal<W>(&self, dest: &mut W, prefix_space: bool) -> fmt::Result
+    where
+        W: fmt::Write,
+    {
+        if matches!(
+            *self,
+            Combinator::PseudoElement | Combinator::Part | Combinator::SlotAssignment
+        ) {
+            return Ok(());
+        }
+        if prefix_space {
+            dest.write_char(' ')?;
+        }
+        match *self {
+            Combinator::Child => dest.write_str("> "),
+            Combinator::Descendant => Ok(()),
+            Combinator::NextSibling => dest.write_str("+ "),
+            Combinator::LaterSibling => dest.write_str("~ "),
+            Combinator::PseudoElement | Combinator::Part | Combinator::SlotAssignment => unsafe {
+                debug_unreachable!("Already handled")
+            },
+        }
+    }
+
+    fn to_css_relative<W>(&self, dest: &mut W) -> fmt::Result
+    where
+        W: fmt::Write,
+    {
+        self.to_css_internal(dest, false)
+    }
+}
+
+impl ToCss for Combinator {
+    fn to_css<W>(&self, dest: &mut W) -> fmt::Result
+    where
+        W: fmt::Write,
+    {
+        self.to_css_internal(dest, true)
+    }
+}
+
+impl<Impl: SelectorImpl> ToCss for Component<Impl> {
+    fn to_css<W>(&self, dest: &mut W) -> fmt::Result
+    where
+        W: fmt::Write,
+    {
+        use self::Component::*;
+
+        match *self {
+            Combinator(ref c) => c.to_css(dest),
+            Slotted(ref selector) => {
+                dest.write_str("::slotted(")?;
+                selector.to_css(dest)?;
+                dest.write_char(')')
+            },
+            Part(ref part_names) => {
+                dest.write_str("::part(")?;
+                for (i, name) in part_names.iter().enumerate() {
+                    if i != 0 {
+                        dest.write_char(' ')?;
+                    }
+                    name.to_css(dest)?;
+                }
+                dest.write_char(')')
+            },
+            PseudoElement(ref p) => p.to_css(dest),
+            ID(ref s) => {
+                dest.write_char('#')?;
+                s.to_css(dest)
+            },
+            Class(ref s) => {
+                dest.write_char('.')?;
+                s.to_css(dest)
+            },
+            LocalName(ref s) => s.to_css(dest),
+            ExplicitUniversalType => dest.write_char('*'),
+
+            DefaultNamespace(_) => Ok(()),
+            ExplicitNoNamespace => dest.write_char('|'),
+            ExplicitAnyNamespace => dest.write_str("*|"),
+            Namespace(ref prefix, _) => {
+                prefix.to_css(dest)?;
+                dest.write_char('|')
+            },
+
+            AttributeInNoNamespaceExists { ref local_name, .. } => {
+                dest.write_char('[')?;
+                local_name.to_css(dest)?;
+                dest.write_char(']')
+            },
+            AttributeInNoNamespace {
+                ref local_name,
+                operator,
+                ref value,
+                case_sensitivity,
+                ..
+            } => {
+                dest.write_char('[')?;
+                local_name.to_css(dest)?;
+                operator.to_css(dest)?;
+                value.to_css(dest)?;
+                match case_sensitivity {
+                    ParsedCaseSensitivity::CaseSensitive |
+                    ParsedCaseSensitivity::AsciiCaseInsensitiveIfInHtmlElementInHtmlDocument => {},
+                    ParsedCaseSensitivity::AsciiCaseInsensitive => dest.write_str(" i")?,
+                    ParsedCaseSensitivity::ExplicitCaseSensitive => dest.write_str(" s")?,
+                }
+                dest.write_char(']')
+            },
+            AttributeOther(ref attr_selector) => attr_selector.to_css(dest),
+
+            // Pseudo-classes
+            Root => dest.write_str(":root"),
+            Empty => dest.write_str(":empty"),
+            Scope => dest.write_str(":scope"),
+            ParentSelector => dest.write_char('&'),
+            Host(ref selector) => {
+                dest.write_str(":host")?;
+                if let Some(ref selector) = *selector {
+                    dest.write_char('(')?;
+                    selector.to_css(dest)?;
+                    dest.write_char(')')?;
+                }
+                Ok(())
+            },
+            Nth(ref nth_data) => {
+                nth_data.write_start(dest)?;
+                if nth_data.is_function {
+                    nth_data.write_affine(dest)?;
+                    dest.write_char(')')?;
+                }
+                Ok(())
+            },
+            NthOf(ref nth_of_data) => {
+                let nth_data = nth_of_data.nth_data();
+                nth_data.write_start(dest)?;
+                debug_assert!(
+                    nth_data.is_function,
+                    "A selector must be a function to hold An+B notation"
+                );
+                nth_data.write_affine(dest)?;
+                debug_assert!(
+                    matches!(nth_data.ty, NthType::Child | NthType::LastChild),
+                    "Only :nth-child or :nth-last-child can be of a selector list"
+                );
+                debug_assert!(
+                    !nth_of_data.selectors().is_empty(),
+                    "The selector list should not be empty"
+                );
+                dest.write_str(" of ")?;
+                serialize_selector_list(nth_of_data.selectors().iter(), dest)?;
+                dest.write_char(')')
+            },
+            Is(ref list) | Where(ref list) | Negation(ref list) => {
+                match *self {
+                    Where(..) => dest.write_str(":where(")?,
+                    Is(..) => dest.write_str(":is(")?,
+                    Negation(..) => dest.write_str(":not(")?,
+                    _ => unreachable!(),
+                }
+                serialize_selector_list(list.slice().iter(), dest)?;
+                dest.write_str(")")
+            },
+            Has(ref list) => {
+                dest.write_str(":has(")?;
+                let mut first = true;
+                for RelativeSelector { ref selector, .. } in list.iter() {
+                    if !first {
+                        dest.write_str(", ")?;
+                    }
+                    first = false;
+                    selector.to_css(dest)?;
+                }
+                dest.write_str(")")
+            },
+            NonTSPseudoClass(ref pseudo) => pseudo.to_css(dest),
+            Invalid(ref css) => dest.write_str(css),
+            RelativeSelectorAnchor => Ok(()),
+        }
+    }
+}
+
+impl<Impl: SelectorImpl> ToCss for AttrSelectorWithOptionalNamespace<Impl> {
+    fn to_css<W>(&self, dest: &mut W) -> fmt::Result
+    where
+        W: fmt::Write,
+    {
+        dest.write_char('[')?;
+        match self.namespace {
+            Some(NamespaceConstraint::Specific((ref prefix, _))) => {
+                prefix.to_css(dest)?;
+                dest.write_char('|')?
+            },
+            Some(NamespaceConstraint::Any) => dest.write_str("*|")?,
+            None => {},
+        }
+        self.local_name.to_css(dest)?;
+        match self.operation {
+            ParsedAttrSelectorOperation::Exists => {},
+            ParsedAttrSelectorOperation::WithValue {
+                operator,
+                case_sensitivity,
+                ref value,
+            } => {
+                operator.to_css(dest)?;
+                value.to_css(dest)?;
+                match case_sensitivity {
+                    ParsedCaseSensitivity::CaseSensitive |
+                    ParsedCaseSensitivity::AsciiCaseInsensitiveIfInHtmlElementInHtmlDocument => {},
+                    ParsedCaseSensitivity::AsciiCaseInsensitive => dest.write_str(" i")?,
+                    ParsedCaseSensitivity::ExplicitCaseSensitive => dest.write_str(" s")?,
+                }
+            },
+        }
+        dest.write_char(']')
+    }
+}
+
+impl<Impl: SelectorImpl> ToCss for LocalName<Impl> {
+    fn to_css<W>(&self, dest: &mut W) -> fmt::Result
+    where
+        W: fmt::Write,
+    {
+        self.name.to_css(dest)
+    }
+}
+
+/// Build up a Selector.
+/// selector : simple_selector_sequence [ combinator simple_selector_sequence ]* ;
+///
+/// `Err` means invalid selector.
+fn parse_selector<'i, 't, P, Impl>(
+    parser: &P,
+    input: &mut CssParser<'i, 't>,
+    mut state: SelectorParsingState,
+    parse_relative: ParseRelative,
+) -> Result<Selector<Impl>, ParseError<'i, P::Error>>
+where
+    P: Parser<'i, Impl = Impl>,
+    Impl: SelectorImpl,
+{
+    let mut builder = SelectorBuilder::default();
+
+    // Helps rewind less, but also simplifies dealing with relative combinators below.
+    input.skip_whitespace();
+
+    if parse_relative != ParseRelative::No {
+        let combinator = try_parse_combinator::<P, Impl>(input);
+        match parse_relative {
+            ParseRelative::ForHas => {
+                builder.push_simple_selector(Component::RelativeSelectorAnchor);
+                // Do we see a combinator? If so, push that. Otherwise, push a descendant
+                // combinator.
+                builder.push_combinator(combinator.unwrap_or(Combinator::Descendant));
+            },
+            ParseRelative::ForNesting => {
+                if let Ok(combinator) = combinator {
+                    builder.push_simple_selector(Component::ParentSelector);
+                    builder.push_combinator(combinator);
+                }
+            },
+            ParseRelative::No => unreachable!(),
+        }
+    }
+    'outer_loop: loop {
+        // Parse a sequence of simple selectors.
+        let empty = parse_compound_selector(parser, &mut state, input, &mut builder)?;
+        if empty {
+            return Err(input.new_custom_error(if builder.has_combinators() {
+                SelectorParseErrorKind::DanglingCombinator
+            } else {
+                SelectorParseErrorKind::EmptySelector
+            }));
+        }
+
+        if state.intersects(SelectorParsingState::AFTER_PSEUDO) {
+            debug_assert!(state.intersects(
+                SelectorParsingState::AFTER_PSEUDO_ELEMENT |
+                    SelectorParsingState::AFTER_SLOTTED |
+                    SelectorParsingState::AFTER_PART
+            ));
+            break;
+        }
+
+        let combinator = if let Ok(c) = try_parse_combinator::<P, Impl>(input) {
+            c
+        } else {
+            break 'outer_loop;
+        };
+
+        if !state.allows_combinators() {
+            return Err(input.new_custom_error(SelectorParseErrorKind::InvalidState));
+        }
+
+        builder.push_combinator(combinator);
+    }
+    return Ok(Selector(builder.build()));
+}
+
+fn try_parse_combinator<'i, 't, P, Impl>(input: &mut CssParser<'i, 't>) -> Result<Combinator, ()> {
+    let mut any_whitespace = false;
+    loop {
+        let before_this_token = input.state();
+        match input.next_including_whitespace() {
+            Err(_e) => return Err(()),
+            Ok(&Token::WhiteSpace(_)) => any_whitespace = true,
+            Ok(&Token::Delim('>')) => {
+                return Ok(Combinator::Child);
+            },
+            Ok(&Token::Delim('+')) => {
+                return Ok(Combinator::NextSibling);
+            },
+            Ok(&Token::Delim('~')) => {
+                return Ok(Combinator::LaterSibling);
+            },
+            Ok(_) => {
+                input.reset(&before_this_token);
+                if any_whitespace {
+                    return Ok(Combinator::Descendant);
+                } else {
+                    return Err(());
+                }
+            },
+        }
+    }
+}
+
+/// * `Err(())`: Invalid selector, abort
+/// * `Ok(false)`: Not a type selector, could be something else. `input` was not consumed.
+/// * `Ok(true)`: Length 0 (`*|*`), 1 (`*|E` or `ns|*`) or 2 (`|E` or `ns|E`)
+fn parse_type_selector<'i, 't, P, Impl, S>(
+    parser: &P,
+    input: &mut CssParser<'i, 't>,
+    state: SelectorParsingState,
+    sink: &mut S,
+) -> Result<bool, ParseError<'i, P::Error>>
+where
+    P: Parser<'i, Impl = Impl>,
+    Impl: SelectorImpl,
+    S: Push<Component<Impl>>,
+{
+    match parse_qualified_name(parser, input, /* in_attr_selector = */ false) {
+        Err(ParseError {
+            kind: ParseErrorKind::Basic(BasicParseErrorKind::EndOfInput),
+            ..
+        }) |
+        Ok(OptionalQName::None(_)) => Ok(false),
+        Ok(OptionalQName::Some(namespace, local_name)) => {
+            if state.intersects(SelectorParsingState::AFTER_PSEUDO) {
+                return Err(input.new_custom_error(SelectorParseErrorKind::InvalidState));
+            }
+            match namespace {
+                QNamePrefix::ImplicitAnyNamespace => {},
+                QNamePrefix::ImplicitDefaultNamespace(url) => {
+                    sink.push(Component::DefaultNamespace(url))
+                },
+                QNamePrefix::ExplicitNamespace(prefix, url) => {
+                    sink.push(match parser.default_namespace() {
+                        Some(ref default_url) if url == *default_url => {
+                            Component::DefaultNamespace(url)
+                        },
+                        _ => Component::Namespace(prefix, url),
+                    })
+                },
+                QNamePrefix::ExplicitNoNamespace => sink.push(Component::ExplicitNoNamespace),
+                QNamePrefix::ExplicitAnyNamespace => {
+                    match parser.default_namespace() {
+                        // Element type selectors that have no namespace
+                        // component (no namespace separator) represent elements
+                        // without regard to the element's namespace (equivalent
+                        // to "*|") unless a default namespace has been declared
+                        // for namespaced selectors (e.g. in CSS, in the style
+                        // sheet). If a default namespace has been declared,
+                        // such selectors will represent only elements in the
+                        // default namespace.
+                        // -- Selectors § 6.1.1
+                        // So we'll have this act the same as the
+                        // QNamePrefix::ImplicitAnyNamespace case.
+                        None => {},
+                        Some(_) => sink.push(Component::ExplicitAnyNamespace),
+                    }
+                },
+                QNamePrefix::ImplicitNoNamespace => {
+                    unreachable!() // Not returned with in_attr_selector = false
+                },
+            }
+            match local_name {
+                Some(name) => sink.push(Component::LocalName(LocalName {
+                    lower_name: to_ascii_lowercase(&name).as_ref().into(),
+                    name: name.as_ref().into(),
+                })),
+                None => sink.push(Component::ExplicitUniversalType),
+            }
+            Ok(true)
+        },
+        Err(e) => Err(e),
+    }
+}
+
+#[derive(Debug)]
+enum SimpleSelectorParseResult<Impl: SelectorImpl> {
+    SimpleSelector(Component<Impl>),
+    PseudoElement(Impl::PseudoElement),
+    SlottedPseudo(Selector<Impl>),
+    PartPseudo(Box<[Impl::Identifier]>),
+}
+
+#[derive(Debug)]
+enum QNamePrefix<Impl: SelectorImpl> {
+    ImplicitNoNamespace,                          // `foo` in attr selectors
+    ImplicitAnyNamespace,                         // `foo` in type selectors, without a default ns
+    ImplicitDefaultNamespace(Impl::NamespaceUrl), // `foo` in type selectors, with a default ns
+    ExplicitNoNamespace,                          // `|foo`
+    ExplicitAnyNamespace,                         // `*|foo`
+    ExplicitNamespace(Impl::NamespacePrefix, Impl::NamespaceUrl), // `prefix|foo`
+}
+
+enum OptionalQName<'i, Impl: SelectorImpl> {
+    Some(QNamePrefix<Impl>, Option<CowRcStr<'i>>),
+    None(Token<'i>),
+}
+
+/// * `Err(())`: Invalid selector, abort
+/// * `Ok(None(token))`: Not a simple selector, could be something else. `input` was not consumed,
+///                      but the token is still returned.
+/// * `Ok(Some(namespace, local_name))`: `None` for the local name means a `*` universal selector
+fn parse_qualified_name<'i, 't, P, Impl>(
+    parser: &P,
+    input: &mut CssParser<'i, 't>,
+    in_attr_selector: bool,
+) -> Result<OptionalQName<'i, Impl>, ParseError<'i, P::Error>>
+where
+    P: Parser<'i, Impl = Impl>,
+    Impl: SelectorImpl,
+{
+    let default_namespace = |local_name| {
+        let namespace = match parser.default_namespace() {
+            Some(url) => QNamePrefix::ImplicitDefaultNamespace(url),
+            None => QNamePrefix::ImplicitAnyNamespace,
+        };
+        Ok(OptionalQName::Some(namespace, local_name))
+    };
+
+    let explicit_namespace = |input: &mut CssParser<'i, 't>, namespace| {
+        let location = input.current_source_location();
+        match input.next_including_whitespace() {
+            Ok(&Token::Delim('*')) if !in_attr_selector => Ok(OptionalQName::Some(namespace, None)),
+            Ok(&Token::Ident(ref local_name)) => {
+                Ok(OptionalQName::Some(namespace, Some(local_name.clone())))
+            },
+            Ok(t) if in_attr_selector => {
+                let e = SelectorParseErrorKind::InvalidQualNameInAttr(t.clone());
+                Err(location.new_custom_error(e))
+            },
+            Ok(t) => Err(location.new_custom_error(
+                SelectorParseErrorKind::ExplicitNamespaceUnexpectedToken(t.clone()),
+            )),
+            Err(e) => Err(e.into()),
+        }
+    };
+
+    let start = input.state();
+    match input.next_including_whitespace() {
+        Ok(Token::Ident(value)) => {
+            let value = value.clone();
+            let after_ident = input.state();
+            match input.next_including_whitespace() {
+                Ok(&Token::Delim('|')) => {
+                    let prefix = value.as_ref().into();
+                    let result = parser.namespace_for_prefix(&prefix);
+                    let url = result.ok_or(
+                        after_ident
+                            .source_location()
+                            .new_custom_error(SelectorParseErrorKind::ExpectedNamespace(value)),
+                    )?;
+                    explicit_namespace(input, QNamePrefix::ExplicitNamespace(prefix, url))
+                },
+                _ => {
+                    input.reset(&after_ident);
+                    if in_attr_selector {
+                        Ok(OptionalQName::Some(
+                            QNamePrefix::ImplicitNoNamespace,
+                            Some(value),
+                        ))
+                    } else {
+                        default_namespace(Some(value))
+                    }
+                },
+            }
+        },
+        Ok(Token::Delim('*')) => {
+            let after_star = input.state();
+            match input.next_including_whitespace() {
+                Ok(&Token::Delim('|')) => {
+                    explicit_namespace(input, QNamePrefix::ExplicitAnyNamespace)
+                },
+                _ if !in_attr_selector => {
+                    input.reset(&after_star);
+                    default_namespace(None)
+                },
+                result => {
+                    let t = result?;
+                    Err(after_star
+                        .source_location()
+                        .new_custom_error(SelectorParseErrorKind::ExpectedBarInAttr(t.clone())))
+                },
+            }
+        },
+        Ok(Token::Delim('|')) => explicit_namespace(input, QNamePrefix::ExplicitNoNamespace),
+        Ok(t) => {
+            let t = t.clone();
+            input.reset(&start);
+            Ok(OptionalQName::None(t))
+        },
+        Err(e) => {
+            input.reset(&start);
+            Err(e.into())
+        },
+    }
+}
+
+fn parse_attribute_selector<'i, 't, P, Impl>(
+    parser: &P,
+    input: &mut CssParser<'i, 't>,
+) -> Result<Component<Impl>, ParseError<'i, P::Error>>
+where
+    P: Parser<'i, Impl = Impl>,
+    Impl: SelectorImpl,
+{
+    let namespace;
+    let local_name;
+
+    input.skip_whitespace();
+
+    match parse_qualified_name(parser, input, /* in_attr_selector = */ true)? {
+        OptionalQName::None(t) => {
+            return Err(input.new_custom_error(
+                SelectorParseErrorKind::NoQualifiedNameInAttributeSelector(t),
+            ));
+        },
+        OptionalQName::Some(_, None) => unreachable!(),
+        OptionalQName::Some(ns, Some(ln)) => {
+            local_name = ln;
+            namespace = match ns {
+                QNamePrefix::ImplicitNoNamespace | QNamePrefix::ExplicitNoNamespace => None,
+                QNamePrefix::ExplicitNamespace(prefix, url) => {
+                    Some(NamespaceConstraint::Specific((prefix, url)))
+                },
+                QNamePrefix::ExplicitAnyNamespace => Some(NamespaceConstraint::Any),
+                QNamePrefix::ImplicitAnyNamespace | QNamePrefix::ImplicitDefaultNamespace(_) => {
+                    unreachable!() // Not returned with in_attr_selector = true
+                },
+            }
+        },
+    }
+
+    let location = input.current_source_location();
+    let operator = match input.next() {
+        // [foo]
+        Err(_) => {
+            let local_name_lower = to_ascii_lowercase(&local_name).as_ref().into();
+            let local_name = local_name.as_ref().into();
+            if let Some(namespace) = namespace {
+                return Ok(Component::AttributeOther(Box::new(
+                    AttrSelectorWithOptionalNamespace {
+                        namespace: Some(namespace),
+                        local_name,
+                        local_name_lower,
+                        operation: ParsedAttrSelectorOperation::Exists,
+                    },
+                )));
+            } else {
+                return Ok(Component::AttributeInNoNamespaceExists {
+                    local_name,
+                    local_name_lower,
+                });
+            }
+        },
+
+        // [foo=bar]
+        Ok(&Token::Delim('=')) => AttrSelectorOperator::Equal,
+        // [foo~=bar]
+        Ok(&Token::IncludeMatch) => AttrSelectorOperator::Includes,
+        // [foo|=bar]
+        Ok(&Token::DashMatch) => AttrSelectorOperator::DashMatch,
+        // [foo^=bar]
+        Ok(&Token::PrefixMatch) => AttrSelectorOperator::Prefix,
+        // [foo*=bar]
+        Ok(&Token::SubstringMatch) => AttrSelectorOperator::Substring,
+        // [foo$=bar]
+        Ok(&Token::SuffixMatch) => AttrSelectorOperator::Suffix,
+        Ok(t) => {
+            return Err(location.new_custom_error(
+                SelectorParseErrorKind::UnexpectedTokenInAttributeSelector(t.clone()),
+            ));
+        },
+    };
+
+    let value = match input.expect_ident_or_string() {
+        Ok(t) => t.clone(),
+        Err(BasicParseError {
+            kind: BasicParseErrorKind::UnexpectedToken(t),
+            location,
+        }) => return Err(location.new_custom_error(SelectorParseErrorKind::BadValueInAttr(t))),
+        Err(e) => return Err(e.into()),
+    };
+
+    let attribute_flags = parse_attribute_flags(input)?;
+    let value = value.as_ref().into();
+    let local_name_lower;
+    let local_name_is_ascii_lowercase;
+    let case_sensitivity;
+    {
+        let local_name_lower_cow = to_ascii_lowercase(&local_name);
+        case_sensitivity =
+            attribute_flags.to_case_sensitivity(local_name_lower_cow.as_ref(), namespace.is_some());
+        local_name_lower = local_name_lower_cow.as_ref().into();
+        local_name_is_ascii_lowercase = matches!(local_name_lower_cow, Cow::Borrowed(..));
+    }
+    let local_name = local_name.as_ref().into();
+    if namespace.is_some() || !local_name_is_ascii_lowercase {
+        Ok(Component::AttributeOther(Box::new(
+            AttrSelectorWithOptionalNamespace {
+                namespace,
+                local_name,
+                local_name_lower,
+                operation: ParsedAttrSelectorOperation::WithValue {
+                    operator,
+                    case_sensitivity,
+                    value,
+                },
+            },
+        )))
+    } else {
+        Ok(Component::AttributeInNoNamespace {
+            local_name,
+            operator,
+            value,
+            case_sensitivity,
+        })
+    }
+}
+
+/// An attribute selector can have 's' or 'i' as flags, or no flags at all.
+enum AttributeFlags {
+    // Matching should be case-sensitive ('s' flag).
+    CaseSensitive,
+    // Matching should be case-insensitive ('i' flag).
+    AsciiCaseInsensitive,
+    // No flags.  Matching behavior depends on the name of the attribute.
+    CaseSensitivityDependsOnName,
+}
+
+impl AttributeFlags {
+    fn to_case_sensitivity(self, local_name: &str, have_namespace: bool) -> ParsedCaseSensitivity {
+        match self {
+            AttributeFlags::CaseSensitive => ParsedCaseSensitivity::ExplicitCaseSensitive,
+            AttributeFlags::AsciiCaseInsensitive => ParsedCaseSensitivity::AsciiCaseInsensitive,
+            AttributeFlags::CaseSensitivityDependsOnName => {
+                if !have_namespace &&
+                    include!(concat!(
+                        env!("OUT_DIR"),
+                        "/ascii_case_insensitive_html_attributes.rs"
+                    ))
+                    .contains(local_name)
+                {
+                    ParsedCaseSensitivity::AsciiCaseInsensitiveIfInHtmlElementInHtmlDocument
+                } else {
+                    ParsedCaseSensitivity::CaseSensitive
+                }
+            },
+        }
+    }
+}
+
+fn parse_attribute_flags<'i, 't>(
+    input: &mut CssParser<'i, 't>,
+) -> Result<AttributeFlags, BasicParseError<'i>> {
+    let location = input.current_source_location();
+    let token = match input.next() {
+        Ok(t) => t,
+        Err(..) => {
+            // Selectors spec says language-defined; HTML says it depends on the
+            // exact attribute name.
+            return Ok(AttributeFlags::CaseSensitivityDependsOnName);
+        },
+    };
+
+    let ident = match *token {
+        Token::Ident(ref i) => i,
+        ref other => return Err(location.new_basic_unexpected_token_error(other.clone())),
+    };
+
+    Ok(match_ignore_ascii_case! {
+        ident,
+        "i" => AttributeFlags::AsciiCaseInsensitive,
+        "s" => AttributeFlags::CaseSensitive,
+        _ => return Err(location.new_basic_unexpected_token_error(token.clone())),
+    })
+}
+
+/// Level 3: Parse **one** simple_selector.  (Though we might insert a second
+/// implied "<defaultns>|*" type selector.)
+fn parse_negation<'i, 't, P, Impl>(
+    parser: &P,
+    input: &mut CssParser<'i, 't>,
+    state: SelectorParsingState,
+) -> Result<Component<Impl>, ParseError<'i, P::Error>>
+where
+    P: Parser<'i, Impl = Impl>,
+    Impl: SelectorImpl,
+{
+    let list = SelectorList::parse_with_state(
+        parser,
+        input,
+        state |
+            SelectorParsingState::SKIP_DEFAULT_NAMESPACE |
+            SelectorParsingState::DISALLOW_PSEUDOS,
+        ForgivingParsing::No,
+        ParseRelative::No,
+    )?;
+
+    Ok(Component::Negation(list))
+}
+
+/// simple_selector_sequence
+/// : [ type_selector | universal ] [ HASH | class | attrib | pseudo | negation ]*
+/// | [ HASH | class | attrib | pseudo | negation ]+
+///
+/// `Err(())` means invalid selector.
+/// `Ok(true)` is an empty selector
+fn parse_compound_selector<'i, 't, P, Impl>(
+    parser: &P,
+    state: &mut SelectorParsingState,
+    input: &mut CssParser<'i, 't>,
+    builder: &mut SelectorBuilder<Impl>,
+) -> Result<bool, ParseError<'i, P::Error>>
+where
+    P: Parser<'i, Impl = Impl>,
+    Impl: SelectorImpl,
+{
+    input.skip_whitespace();
+
+    let mut empty = true;
+    if parse_type_selector(parser, input, *state, builder)? {
+        empty = false;
+    }
+
+    loop {
+        let result = match parse_one_simple_selector(parser, input, *state)? {
+            None => break,
+            Some(result) => result,
+        };
+
+        if empty {
+            if let Some(url) = parser.default_namespace() {
+                // If there was no explicit type selector, but there is a
+                // default namespace, there is an implicit "<defaultns>|*" type
+                // selector. Except for :host() or :not() / :is() / :where(),
+                // where we ignore it.
+                //
+                // https://drafts.csswg.org/css-scoping/#host-element-in-tree:
+                //
+                //     When considered within its own shadow trees, the shadow
+                //     host is featureless. Only the :host, :host(), and
+                //     :host-context() pseudo-classes are allowed to match it.
+                //
+                // https://drafts.csswg.org/selectors-4/#featureless:
+                //
+                //     A featureless element does not match any selector at all,
+                //     except those it is explicitly defined to match. If a
+                //     given selector is allowed to match a featureless element,
+                //     it must do so while ignoring the default namespace.
+                //
+                // https://drafts.csswg.org/selectors-4/#matches
+                //
+                //     Default namespace declarations do not affect the compound
+                //     selector representing the subject of any selector within
+                //     a :is() pseudo-class, unless that compound selector
+                //     contains an explicit universal selector or type selector.
+                //
+                //     (Similar quotes for :where() / :not())
+                //
+                let ignore_default_ns = state
+                    .intersects(SelectorParsingState::SKIP_DEFAULT_NAMESPACE) ||
+                    matches!(
+                        result,
+                        SimpleSelectorParseResult::SimpleSelector(Component::Host(..))
+                    );
+                if !ignore_default_ns {
+                    builder.push_simple_selector(Component::DefaultNamespace(url));
+                }
+            }
+        }
+
+        empty = false;
+
+        match result {
+            SimpleSelectorParseResult::SimpleSelector(s) => {
+                builder.push_simple_selector(s);
+            },
+            SimpleSelectorParseResult::PartPseudo(part_names) => {
+                state.insert(SelectorParsingState::AFTER_PART);
+                builder.push_combinator(Combinator::Part);
+                builder.push_simple_selector(Component::Part(part_names));
+            },
+            SimpleSelectorParseResult::SlottedPseudo(selector) => {
+                state.insert(SelectorParsingState::AFTER_SLOTTED);
+                builder.push_combinator(Combinator::SlotAssignment);
+                builder.push_simple_selector(Component::Slotted(selector));
+            },
+            SimpleSelectorParseResult::PseudoElement(p) => {
+                state.insert(SelectorParsingState::AFTER_PSEUDO_ELEMENT);
+                if !p.accepts_state_pseudo_classes() {
+                    state.insert(SelectorParsingState::AFTER_NON_STATEFUL_PSEUDO_ELEMENT);
+                }
+                builder.push_combinator(Combinator::PseudoElement);
+                builder.push_simple_selector(Component::PseudoElement(p));
+            },
+        }
+    }
+    Ok(empty)
+}
+
+fn parse_is_where<'i, 't, P, Impl>(
+    parser: &P,
+    input: &mut CssParser<'i, 't>,
+    state: SelectorParsingState,
+    component: impl FnOnce(SelectorList<Impl>) -> Component<Impl>,
+) -> Result<Component<Impl>, ParseError<'i, P::Error>>
+where
+    P: Parser<'i, Impl = Impl>,
+    Impl: SelectorImpl,
+{
+    debug_assert!(parser.parse_is_and_where());
+    // https://drafts.csswg.org/selectors/#matches-pseudo:
+    //
+    //     Pseudo-elements cannot be represented by the matches-any
+    //     pseudo-class; they are not valid within :is().
+    //
+    let inner = SelectorList::parse_with_state(
+        parser,
+        input,
+        state |
+            SelectorParsingState::SKIP_DEFAULT_NAMESPACE |
+            SelectorParsingState::DISALLOW_PSEUDOS,
+        ForgivingParsing::Yes,
+        ParseRelative::No,
+    )?;
+    Ok(component(inner))
+}
+
+fn parse_has<'i, 't, P, Impl>(
+    parser: &P,
+    input: &mut CssParser<'i, 't>,
+    state: SelectorParsingState,
+) -> Result<Component<Impl>, ParseError<'i, P::Error>>
+where
+    P: Parser<'i, Impl = Impl>,
+    Impl: SelectorImpl,
+{
+    debug_assert!(parser.parse_has());
+    if state.intersects(SelectorParsingState::DISALLOW_RELATIVE_SELECTOR) {
+        return Err(input.new_custom_error(SelectorParseErrorKind::InvalidState));
+    }
+    // Nested `:has()` is disallowed, mark it as such.
+    // Note: The spec defines ":has-allowed pseudo-element," but there's no
+    // pseudo-element defined as such at the moment.
+    // https://w3c.github.io/csswg-drafts/selectors-4/#has-allowed-pseudo-element
+    let inner = SelectorList::parse_with_state(
+        parser,
+        input,
+        state |
+            SelectorParsingState::SKIP_DEFAULT_NAMESPACE |
+            SelectorParsingState::DISALLOW_PSEUDOS |
+            SelectorParsingState::DISALLOW_RELATIVE_SELECTOR,
+        ForgivingParsing::No,
+        ParseRelative::ForHas,
+    )?;
+    Ok(Component::Has(RelativeSelector::from_selector_list(inner)))
+}
+
+fn parse_functional_pseudo_class<'i, 't, P, Impl>(
+    parser: &P,
+    input: &mut CssParser<'i, 't>,
+    name: CowRcStr<'i>,
+    state: SelectorParsingState,
+) -> Result<Component<Impl>, ParseError<'i, P::Error>>
+where
+    P: Parser<'i, Impl = Impl>,
+    Impl: SelectorImpl,
+{
+    match_ignore_ascii_case! { &name,
+        "nth-child" => return parse_nth_pseudo_class(parser, input, state, NthType::Child),
+        "nth-of-type" => return parse_nth_pseudo_class(parser, input, state, NthType::OfType),
+        "nth-last-child" => return parse_nth_pseudo_class(parser, input, state, NthType::LastChild),
+        "nth-last-of-type" => return parse_nth_pseudo_class(parser, input, state, NthType::LastOfType),
+        "is" if parser.parse_is_and_where() => return parse_is_where(parser, input, state, Component::Is),
+        "where" if parser.parse_is_and_where() => return parse_is_where(parser, input, state, Component::Where),
+        "has" if parser.parse_has() => return parse_has(parser, input, state),
+        "host" => {
+            if !state.allows_tree_structural_pseudo_classes() {
+                return Err(input.new_custom_error(SelectorParseErrorKind::InvalidState));
+            }
+            return Ok(Component::Host(Some(parse_inner_compound_selector(parser, input, state)?)));
+        },
+        "not" => {
+            return parse_negation(parser, input, state)
+        },
+        _ => {}
+    }
+
+    if parser.parse_is_and_where() && parser.is_is_alias(&name) {
+        return parse_is_where(parser, input, state, Component::Is);
+    }
+
+    if state.intersects(SelectorParsingState::AFTER_PSEUDO_ELEMENT | SelectorParsingState::AFTER_SLOTTED) {
+        return Err(input.new_custom_error(SelectorParseErrorKind::InvalidState));
+    }
+
+    let after_part = state.intersects(SelectorParsingState::AFTER_PART);
+    P::parse_non_ts_functional_pseudo_class(parser, name, input, after_part).map(Component::NonTSPseudoClass)
+}
+
+fn parse_nth_pseudo_class<'i, 't, P, Impl>(
+    parser: &P,
+    input: &mut CssParser<'i, 't>,
+    state: SelectorParsingState,
+    ty: NthType,
+) -> Result<Component<Impl>, ParseError<'i, P::Error>>
+where
+    P: Parser<'i, Impl = Impl>,
+    Impl: SelectorImpl,
+{
+    if !state.allows_tree_structural_pseudo_classes() {
+        return Err(input.new_custom_error(SelectorParseErrorKind::InvalidState));
+    }
+    let (a, b) = parse_nth(input)?;
+    let nth_data = NthSelectorData {
+        ty,
+        is_function: true,
+        a,
+        b,
+    };
+    if !parser.parse_nth_child_of() || ty.is_of_type() {
+        return Ok(Component::Nth(nth_data));
+    }
+
+    // Try to parse "of <selector-list>".
+    if input.try_parse(|i| i.expect_ident_matching("of")).is_err() {
+        return Ok(Component::Nth(nth_data));
+    }
+    // Whitespace between "of" and the selector list is optional
+    // https://github.com/w3c/csswg-drafts/issues/8285
+    let selectors = SelectorList::parse_with_state(
+        parser,
+        input,
+        state |
+            SelectorParsingState::SKIP_DEFAULT_NAMESPACE |
+            SelectorParsingState::DISALLOW_PSEUDOS,
+        ForgivingParsing::No,
+        ParseRelative::No,
+    )?;
+    Ok(Component::NthOf(NthOfSelectorData::new(
+        &nth_data,
+        selectors.slice().iter().cloned(),
+    )))
+}
+
+/// Returns whether the name corresponds to a CSS2 pseudo-element that
+/// can be specified with the single colon syntax (in addition to the
+/// double-colon syntax, which can be used for all pseudo-elements).
+fn is_css2_pseudo_element(name: &str) -> bool {
+    // ** Do not add to this list! **
+    match_ignore_ascii_case! { name,
+        "before" | "after" | "first-line" | "first-letter" => true,
+        _ => false,
+    }
+}
+
+/// Parse a simple selector other than a type selector.
+///
+/// * `Err(())`: Invalid selector, abort
+/// * `Ok(None)`: Not a simple selector, could be something else. `input` was not consumed.
+/// * `Ok(Some(_))`: Parsed a simple selector or pseudo-element
+fn parse_one_simple_selector<'i, 't, P, Impl>(
+    parser: &P,
+    input: &mut CssParser<'i, 't>,
+    state: SelectorParsingState,
+) -> Result<Option<SimpleSelectorParseResult<Impl>>, ParseError<'i, P::Error>>
+where
+    P: Parser<'i, Impl = Impl>,
+    Impl: SelectorImpl,
+{
+    let start = input.state();
+    let token = match input.next_including_whitespace().map(|t| t.clone()) {
+        Ok(t) => t,
+        Err(..) => {
+            input.reset(&start);
+            return Ok(None);
+        },
+    };
+
+    Ok(Some(match token {
+        Token::IDHash(id) => {
+            if state.intersects(SelectorParsingState::AFTER_PSEUDO) {
+                return Err(input.new_custom_error(SelectorParseErrorKind::InvalidState));
+            }
+            let id = Component::ID(id.as_ref().into());
+            SimpleSelectorParseResult::SimpleSelector(id)
+        },
+        Token::Delim(delim) if delim == '.' || (delim == '&' && parser.parse_parent_selector()) => {
+            if state.intersects(SelectorParsingState::AFTER_PSEUDO) {
+                return Err(input.new_custom_error(SelectorParseErrorKind::InvalidState));
+            }
+            let location = input.current_source_location();
+            SimpleSelectorParseResult::SimpleSelector(if delim == '&' {
+                Component::ParentSelector
+            } else {
+                let class = match *input.next_including_whitespace()? {
+                    Token::Ident(ref class) => class,
+                    ref t => {
+                        let e = SelectorParseErrorKind::ClassNeedsIdent(t.clone());
+                        return Err(location.new_custom_error(e));
+                    },
+                };
+                Component::Class(class.as_ref().into())
+            })
+        },
+        Token::SquareBracketBlock => {
+            if state.intersects(SelectorParsingState::AFTER_PSEUDO) {
+                return Err(input.new_custom_error(SelectorParseErrorKind::InvalidState));
+            }
+            let attr = input.parse_nested_block(|input| parse_attribute_selector(parser, input))?;
+            SimpleSelectorParseResult::SimpleSelector(attr)
+        },
+        Token::Colon => {
+            let location = input.current_source_location();
+            let (is_single_colon, next_token) = match input.next_including_whitespace()?.clone() {
+                Token::Colon => (false, input.next_including_whitespace()?.clone()),
+                t => (true, t),
+            };
+            let (name, is_functional) = match next_token {
+                Token::Ident(name) => (name, false),
+                Token::Function(name) => (name, true),
+                t => {
+                    let e = SelectorParseErrorKind::PseudoElementExpectedIdent(t);
+                    return Err(input.new_custom_error(e));
+                },
+            };
+            let is_pseudo_element = !is_single_colon || is_css2_pseudo_element(&name);
+            if is_pseudo_element {
+                if !state.allows_pseudos() {
+                    return Err(input.new_custom_error(SelectorParseErrorKind::InvalidState));
+                }
+                let pseudo_element = if is_functional {
+                    if P::parse_part(parser) && name.eq_ignore_ascii_case("part") {
+                        if !state.allows_part() {
+                            return Err(
+                                input.new_custom_error(SelectorParseErrorKind::InvalidState)
+                            );
+                        }
+                        let names = input.parse_nested_block(|input| {
+                            let mut result = Vec::with_capacity(1);
+                            result.push(input.expect_ident()?.as_ref().into());
+                            while !input.is_exhausted() {
+                                result.push(input.expect_ident()?.as_ref().into());
+                            }
+                            Ok(result.into_boxed_slice())
+                        })?;
+                        return Ok(Some(SimpleSelectorParseResult::PartPseudo(names)));
+                    }
+                    if P::parse_slotted(parser) && name.eq_ignore_ascii_case("slotted") {
+                        if !state.allows_slotted() {
+                            return Err(
+                                input.new_custom_error(SelectorParseErrorKind::InvalidState)
+                            );
+                        }
+                        let selector = input.parse_nested_block(|input| {
+                            parse_inner_compound_selector(parser, input, state)
+                        })?;
+                        return Ok(Some(SimpleSelectorParseResult::SlottedPseudo(selector)));
+                    }
+                    input.parse_nested_block(|input| {
+                        P::parse_functional_pseudo_element(parser, name, input)
+                    })?
+                } else {
+                    P::parse_pseudo_element(parser, location, name)?
+                };
+
+                if state.intersects(SelectorParsingState::AFTER_SLOTTED) &&
+                    !pseudo_element.valid_after_slotted()
+                {
+                    return Err(input.new_custom_error(SelectorParseErrorKind::InvalidState));
+                }
+                SimpleSelectorParseResult::PseudoElement(pseudo_element)
+            } else {
+                let pseudo_class = if is_functional {
+                    input.parse_nested_block(|input| {
+                        parse_functional_pseudo_class(parser, input, name, state)
+                    })?
+                } else {
+                    parse_simple_pseudo_class(parser, location, name, state)?
+                };
+                SimpleSelectorParseResult::SimpleSelector(pseudo_class)
+            }
+        },
+        _ => {
+            input.reset(&start);
+            return Ok(None);
+        },
+    }))
+}
+
+fn parse_simple_pseudo_class<'i, P, Impl>(
+    parser: &P,
+    location: SourceLocation,
+    name: CowRcStr<'i>,
+    state: SelectorParsingState,
+) -> Result<Component<Impl>, ParseError<'i, P::Error>>
+where
+    P: Parser<'i, Impl = Impl>,
+    Impl: SelectorImpl,
+{
+    if !state.allows_non_functional_pseudo_classes() {
+        return Err(location.new_custom_error(SelectorParseErrorKind::InvalidState));
+    }
+
+    if state.allows_tree_structural_pseudo_classes() {
+        match_ignore_ascii_case! { &name,
+            "first-child" => return Ok(Component::Nth(NthSelectorData::first(/* of_type = */ false))),
+            "last-child" => return Ok(Component::Nth(NthSelectorData::last(/* of_type = */ false))),
+            "only-child" => return Ok(Component::Nth(NthSelectorData::only(/* of_type = */ false))),
+            "root" => return Ok(Component::Root),
+            "empty" => return Ok(Component::Empty),
+            "scope" => return Ok(Component::Scope),
+            "host" if P::parse_host(parser) => return Ok(Component::Host(None)),
+            "first-of-type" => return Ok(Component::Nth(NthSelectorData::first(/* of_type = */ true))),
+            "last-of-type" => return Ok(Component::Nth(NthSelectorData::last(/* of_type = */ true))),
+            "only-of-type" => return Ok(Component::Nth(NthSelectorData::only(/* of_type = */ true))),
+            _ => {},
+        }
+    }
+
+    let pseudo_class = P::parse_non_ts_pseudo_class(parser, location, name)?;
+    if state.intersects(SelectorParsingState::AFTER_PSEUDO_ELEMENT) &&
+        !pseudo_class.is_user_action_state()
+    {
+        return Err(location.new_custom_error(SelectorParseErrorKind::InvalidState));
+    }
+    Ok(Component::NonTSPseudoClass(pseudo_class))
+}
+
+// NB: pub module in order to access the DummyParser
+#[cfg(test)]
+pub mod tests {
+    use super::*;
+    use crate::builder::SelectorFlags;
+    use crate::parser;
+    use cssparser::{serialize_identifier, Parser as CssParser, ParserInput, ToCss};
+    use std::collections::HashMap;
+    use std::fmt;
+
+    #[derive(Clone, Debug, Eq, PartialEq)]
+    pub enum PseudoClass {
+        Hover,
+        Active,
+        Lang(String),
+    }
+
+    #[derive(Clone, Debug, Eq, PartialEq)]
+    pub enum PseudoElement {
+        Before,
+        After,
+        Highlight(String),
+    }
+
+    impl parser::PseudoElement for PseudoElement {
+        type Impl = DummySelectorImpl;
+
+        fn accepts_state_pseudo_classes(&self) -> bool {
+            true
+        }
+
+        fn valid_after_slotted(&self) -> bool {
+            true
+        }
+    }
+
+    impl parser::NonTSPseudoClass for PseudoClass {
+        type Impl = DummySelectorImpl;
+
+        #[inline]
+        fn is_active_or_hover(&self) -> bool {
+            matches!(*self, PseudoClass::Active | PseudoClass::Hover)
+        }
+
+        #[inline]
+        fn is_user_action_state(&self) -> bool {
+            self.is_active_or_hover()
+        }
+    }
+
+    impl ToCss for PseudoClass {
+        fn to_css<W>(&self, dest: &mut W) -> fmt::Result
+        where
+            W: fmt::Write,
+        {
+            match *self {
+                PseudoClass::Hover => dest.write_str(":hover"),
+                PseudoClass::Active => dest.write_str(":active"),
+                PseudoClass::Lang(ref lang) => {
+                    dest.write_str(":lang(")?;
+                    serialize_identifier(lang, dest)?;
+                    dest.write_char(')')
+                },
+            }
+        }
+    }
+
+    impl ToCss for PseudoElement {
+        fn to_css<W>(&self, dest: &mut W) -> fmt::Result
+        where
+            W: fmt::Write,
+        {
+            match *self {
+                PseudoElement::Before => dest.write_str("::before"),
+                PseudoElement::After => dest.write_str("::after"),
+                PseudoElement::Highlight(ref name) => {
+                    dest.write_str("::highlight(")?;
+                    serialize_identifier(&name, dest)?;
+                    dest.write_char(')')
+                },
+            }
+        }
+    }
+
+    #[derive(Clone, Debug, PartialEq)]
+    pub struct DummySelectorImpl;
+
+    #[derive(Default)]
+    pub struct DummyParser {
+        default_ns: Option<DummyAtom>,
+        ns_prefixes: HashMap<DummyAtom, DummyAtom>,
+    }
+
+    impl DummyParser {
+        fn default_with_namespace(default_ns: DummyAtom) -> DummyParser {
+            DummyParser {
+                default_ns: Some(default_ns),
+                ns_prefixes: Default::default(),
+            }
+        }
+    }
+
+    impl SelectorImpl for DummySelectorImpl {
+        type ExtraMatchingData<'a> = std::marker::PhantomData<&'a ()>;
+        type AttrValue = DummyAttrValue;
+        type Identifier = DummyAtom;
+        type LocalName = DummyAtom;
+        type NamespaceUrl = DummyAtom;
+        type NamespacePrefix = DummyAtom;
+        type BorrowedLocalName = DummyAtom;
+        type BorrowedNamespaceUrl = DummyAtom;
+        type NonTSPseudoClass = PseudoClass;
+        type PseudoElement = PseudoElement;
+    }
+
+    #[derive(Clone, Debug, Default, Eq, Hash, PartialEq)]
+    pub struct DummyAttrValue(String);
+
+    impl ToCss for DummyAttrValue {
+        fn to_css<W>(&self, dest: &mut W) -> fmt::Result
+        where
+            W: fmt::Write,
+        {
+            use std::fmt::Write;
+
+            dest.write_char('"')?;
+            write!(cssparser::CssStringWriter::new(dest), "{}", &self.0)?;
+            dest.write_char('"')
+        }
+    }
+
+    impl<'a> From<&'a str> for DummyAttrValue {
+        fn from(string: &'a str) -> Self {
+            Self(string.into())
+        }
+    }
+
+    #[derive(Clone, Debug, Default, Eq, Hash, PartialEq)]
+    pub struct DummyAtom(String);
+
+    impl ToCss for DummyAtom {
+        fn to_css<W>(&self, dest: &mut W) -> fmt::Result
+        where
+            W: fmt::Write,
+        {
+            serialize_identifier(&self.0, dest)
+        }
+    }
+
+    impl From<String> for DummyAtom {
+        fn from(string: String) -> Self {
+            DummyAtom(string)
+        }
+    }
+
+    impl<'a> From<&'a str> for DummyAtom {
+        fn from(string: &'a str) -> Self {
+            DummyAtom(string.into())
+        }
+    }
+
+    impl PrecomputedHash for DummyAtom {
+        fn precomputed_hash(&self) -> u32 {
+            self.0.as_ptr() as u32
+        }
+    }
+
+    impl<'i> Parser<'i> for DummyParser {
+        type Impl = DummySelectorImpl;
+        type Error = SelectorParseErrorKind<'i>;
+
+        fn parse_slotted(&self) -> bool {
+            true
+        }
+
+        fn parse_nth_child_of(&self) -> bool {
+            true
+        }
+
+        fn parse_is_and_where(&self) -> bool {
+            true
+        }
+
+        fn parse_has(&self) -> bool {
+            true
+        }
+
+        fn parse_parent_selector(&self) -> bool {
+            true
+        }
+
+        fn parse_part(&self) -> bool {
+            true
+        }
+
+        fn parse_non_ts_pseudo_class(
+            &self,
+            location: SourceLocation,
+            name: CowRcStr<'i>,
+        ) -> Result<PseudoClass, SelectorParseError<'i>> {
+            match_ignore_ascii_case! { &name,
+                "hover" => return Ok(PseudoClass::Hover),
+                "active" => return Ok(PseudoClass::Active),
+                _ => {}
+            }
+            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<PseudoClass, SelectorParseError<'i>> {
+            match_ignore_ascii_case! { &name,
+                "lang" if !after_part => {
+                    let lang = parser.expect_ident_or_string()?.as_ref().to_owned();
+                    return Ok(PseudoClass::Lang(lang));
+                },
+                _ => {}
+            }
+            Err(
+                parser.new_custom_error(SelectorParseErrorKind::UnsupportedPseudoClassOrElement(
+                    name,
+                )),
+            )
+        }
+
+        fn parse_pseudo_element(
+            &self,
+            location: SourceLocation,
+            name: CowRcStr<'i>,
+        ) -> Result<PseudoElement, SelectorParseError<'i>> {
+            match_ignore_ascii_case! { &name,
+                "before" => return Ok(PseudoElement::Before),
+                "after" => return Ok(PseudoElement::After),
+                _ => {}
+            }
+            Err(
+                location.new_custom_error(SelectorParseErrorKind::UnsupportedPseudoClassOrElement(
+                    name,
+                )),
+            )
+        }
+
+        fn parse_functional_pseudo_element<'t>(
+            &self,
+            name: CowRcStr<'i>,
+            parser: &mut CssParser<'i, 't>,
+        ) -> Result<PseudoElement, SelectorParseError<'i>> {
+            match_ignore_ascii_case! {&name,
+                "highlight" => return Ok(PseudoElement::Highlight(parser.expect_ident()?.as_ref().to_owned())),
+                _ => {}
+            }
+            Err(
+                parser.new_custom_error(SelectorParseErrorKind::UnsupportedPseudoClassOrElement(
+                    name,
+                )),
+            )
+        }
+
+        fn default_namespace(&self) -> Option<DummyAtom> {
+            self.default_ns.clone()
+        }
+
+        fn namespace_for_prefix(&self, prefix: &DummyAtom) -> Option<DummyAtom> {
+            self.ns_prefixes.get(prefix).cloned()
+        }
+    }
+
+    fn parse<'i>(
+        input: &'i str,
+    ) -> Result<SelectorList<DummySelectorImpl>, SelectorParseError<'i>> {
+        parse_relative(input, ParseRelative::No)
+    }
+
+    fn parse_relative<'i>(
+        input: &'i str,
+        parse_relative: ParseRelative,
+    ) -> Result<SelectorList<DummySelectorImpl>, SelectorParseError<'i>> {
+        parse_ns_relative(input, &DummyParser::default(), parse_relative)
+    }
+
+    fn parse_expected<'i, 'a>(
+        input: &'i str,
+        expected: Option<&'a str>,
+    ) -> Result<SelectorList<DummySelectorImpl>, SelectorParseError<'i>> {
+        parse_ns_expected(input, &DummyParser::default(), expected)
+    }
+
+    fn parse_relative_expected<'i, 'a>(
+        input: &'i str,
+        parse_relative: ParseRelative,
+        expected: Option<&'a str>,
+    ) -> Result<SelectorList<DummySelectorImpl>, SelectorParseError<'i>> {
+        parse_ns_relative_expected(input, &DummyParser::default(), parse_relative, expected)
+    }
+
+    fn parse_ns<'i>(
+        input: &'i str,
+        parser: &DummyParser,
+    ) -> Result<SelectorList<DummySelectorImpl>, SelectorParseError<'i>> {
+        parse_ns_relative(input, parser, ParseRelative::No)
+    }
+
+    fn parse_ns_relative<'i>(
+        input: &'i str,
+        parser: &DummyParser,
+        parse_relative: ParseRelative,
+    ) -> Result<SelectorList<DummySelectorImpl>, SelectorParseError<'i>> {
+        parse_ns_relative_expected(input, parser, parse_relative, None)
+    }
+
+    fn parse_ns_expected<'i, 'a>(
+        input: &'i str,
+        parser: &DummyParser,
+        expected: Option<&'a str>,
+    ) -> Result<SelectorList<DummySelectorImpl>, SelectorParseError<'i>> {
+        parse_ns_relative_expected(input, parser, ParseRelative::No, expected)
+    }
+
+    fn parse_ns_relative_expected<'i, 'a>(
+        input: &'i str,
+        parser: &DummyParser,
+        parse_relative: ParseRelative,
+        expected: Option<&'a str>,
+    ) -> Result<SelectorList<DummySelectorImpl>, SelectorParseError<'i>> {
+        let mut parser_input = ParserInput::new(input);
+        let result = SelectorList::parse(
+            parser,
+            &mut CssParser::new(&mut parser_input),
+            parse_relative,
+        );
+        if let Ok(ref selectors) = result {
+            // We can't assume that the serialized parsed selector will equal
+            // the input; for example, if there is no default namespace, '*|foo'
+            // should serialize to 'foo'.
+            assert_eq!(
+                selectors.to_css_string(),
+                match expected {
+                    Some(x) => x,
+                    None => input,
+                }
+            );
+        }
+        result
+    }
+
+    fn specificity(a: u32, b: u32, c: u32) -> u32 {
+        a << 20 | b << 10 | c
+    }
+
+    #[test]
+    fn test_empty() {
+        let mut input = ParserInput::new(":empty");
+        let list = SelectorList::parse(
+            &DummyParser::default(),
+            &mut CssParser::new(&mut input),
+            ParseRelative::No,
+        );
+        assert!(list.is_ok());
+    }
+
+    const MATHML: &str = "http://www.w3.org/1998/Math/MathML";
+    const SVG: &str = "http://www.w3.org/2000/svg";
+
+    #[test]
+    fn test_parsing() {
+        assert!(parse("").is_err());
+        assert!(parse(":lang(4)").is_err());
+        assert!(parse(":lang(en US)").is_err());
+        assert_eq!(
+            parse("EeÉ"),
+            Ok(SelectorList::from_vec(vec![Selector::from_vec(
+                vec![Component::LocalName(LocalName {
+                    name: DummyAtom::from("EeÉ"),
+                    lower_name: DummyAtom::from("eeÉ"),
+                })],
+                specificity(0, 0, 1),
+                SelectorFlags::HAS_NON_FEATURELESS_COMPONENT,
+            )]))
+        );
+        assert_eq!(
+            parse("|e"),
+            Ok(SelectorList::from_vec(vec![Selector::from_vec(
+                vec![
+                    Component::ExplicitNoNamespace,
+                    Component::LocalName(LocalName {
+                        name: DummyAtom::from("e"),
+                        lower_name: DummyAtom::from("e"),
+                    }),
+                ],
+                specificity(0, 0, 1),
+                SelectorFlags::HAS_NON_FEATURELESS_COMPONENT,
+            )]))
+        );
+        // When the default namespace is not set, *| should be elided.
+        // https://github.com/servo/servo/pull/17537
+        assert_eq!(
+            parse_expected("*|e", Some("e")),
+            Ok(SelectorList::from_vec(vec![Selector::from_vec(
+                vec![Component::LocalName(LocalName {
+                    name: DummyAtom::from("e"),
+                    lower_name: DummyAtom::from("e"),
+                })],
+                specificity(0, 0, 1),
+                SelectorFlags::HAS_NON_FEATURELESS_COMPONENT,
+            )]))
+        );
+        // When the default namespace is set, *| should _not_ be elided (as foo
+        // is no longer equivalent to *|foo--the former is only for foo in the
+        // default namespace).
+        // https://github.com/servo/servo/issues/16020
+        assert_eq!(
+            parse_ns(
+                "*|e",
+                &DummyParser::default_with_namespace(DummyAtom::from("https://mozilla.org"))
+            ),
+            Ok(SelectorList::from_vec(vec![Selector::from_vec(
+                vec![
+                    Component::ExplicitAnyNamespace,
+                    Component::LocalName(LocalName {
+                        name: DummyAtom::from("e"),
+                        lower_name: DummyAtom::from("e"),
+                    }),
+                ],
+                specificity(0, 0, 1),
+                SelectorFlags::HAS_NON_FEATURELESS_COMPONENT,
+            )]))
+        );
+        assert_eq!(
+            parse("*"),
+            Ok(SelectorList::from_vec(vec![Selector::from_vec(
+                vec![Component::ExplicitUniversalType],
+                specificity(0, 0, 0),
+                SelectorFlags::HAS_NON_FEATURELESS_COMPONENT,
+            )]))
+        );
+        assert_eq!(
+            parse("|*"),
+            Ok(SelectorList::from_vec(vec![Selector::from_vec(
+                vec![
+                    Component::ExplicitNoNamespace,
+                    Component::ExplicitUniversalType,
+                ],
+                specificity(0, 0, 0),
+                SelectorFlags::HAS_NON_FEATURELESS_COMPONENT,
+            )]))
+        );
+        assert_eq!(
+            parse_expected("*|*", Some("*")),
+            Ok(SelectorList::from_vec(vec![Selector::from_vec(
+                vec![Component::ExplicitUniversalType],
+                specificity(0, 0, 0),
+                SelectorFlags::HAS_NON_FEATURELESS_COMPONENT,
+            )]))
+        );
+        assert_eq!(
+            parse_ns(
+                "*|*",
+                &DummyParser::default_with_namespace(DummyAtom::from("https://mozilla.org"))
+            ),
+            Ok(SelectorList::from_vec(vec![Selector::from_vec(
+                vec![
+                    Component::ExplicitAnyNamespace,
+                    Component::ExplicitUniversalType,
+                ],
+                specificity(0, 0, 0),
+                SelectorFlags::HAS_NON_FEATURELESS_COMPONENT,
+            )]))
+        );
+        assert_eq!(
+            parse(".foo:lang(en-US)"),
+            Ok(SelectorList::from_vec(vec![Selector::from_vec(
+                vec![
+                    Component::Class(DummyAtom::from("foo")),
+                    Component::NonTSPseudoClass(PseudoClass::Lang("en-US".to_owned())),
+                ],
+                specificity(0, 2, 0),
+                SelectorFlags::HAS_NON_FEATURELESS_COMPONENT,
+            )]))
+        );
+        assert_eq!(
+            parse("#bar"),
+            Ok(SelectorList::from_vec(vec![Selector::from_vec(
+                vec![Component::ID(DummyAtom::from("bar"))],
+                specificity(1, 0, 0),
+                SelectorFlags::HAS_NON_FEATURELESS_COMPONENT,
+            )]))
+        );
+        assert_eq!(
+            parse("e.foo#bar"),
+            Ok(SelectorList::from_vec(vec![Selector::from_vec(
+                vec![
+                    Component::LocalName(LocalName {
+                        name: DummyAtom::from("e"),
+                        lower_name: DummyAtom::from("e"),
+                    }),
+                    Component::Class(DummyAtom::from("foo")),
+                    Component::ID(DummyAtom::from("bar")),
+                ],
+                specificity(1, 1, 1),
+                SelectorFlags::HAS_NON_FEATURELESS_COMPONENT,
+            )]))
+        );
+        assert_eq!(
+            parse("e.foo #bar"),
+            Ok(SelectorList::from_vec(vec![Selector::from_vec(
+                vec![
+                    Component::LocalName(LocalName {
+                        name: DummyAtom::from("e"),
+                        lower_name: DummyAtom::from("e"),
+                    }),
+                    Component::Class(DummyAtom::from("foo")),
+                    Component::Combinator(Combinator::Descendant),
+                    Component::ID(DummyAtom::from("bar")),
+                ],
+                specificity(1, 1, 1),
+                SelectorFlags::HAS_NON_FEATURELESS_COMPONENT,
+            )]))
+        );
+        // Default namespace does not apply to attribute selectors
+        // https://github.com/mozilla/servo/pull/1652
+        let mut parser = DummyParser::default();
+        assert_eq!(
+            parse_ns("[Foo]", &parser),
+            Ok(SelectorList::from_vec(vec![Selector::from_vec(
+                vec![Component::AttributeInNoNamespaceExists {
+                    local_name: DummyAtom::from("Foo"),
+                    local_name_lower: DummyAtom::from("foo"),
+                }],
+                specificity(0, 1, 0),
+                SelectorFlags::HAS_NON_FEATURELESS_COMPONENT,
+            )]))
+        );
+        assert!(parse_ns("svg|circle", &parser).is_err());
+        parser
+            .ns_prefixes
+            .insert(DummyAtom("svg".into()), DummyAtom(SVG.into()));
+        assert_eq!(
+            parse_ns("svg|circle", &parser),
+            Ok(SelectorList::from_vec(vec![Selector::from_vec(
+                vec![
+                    Component::Namespace(DummyAtom("svg".into()), SVG.into()),
+                    Component::LocalName(LocalName {
+                        name: DummyAtom::from("circle"),
+                        lower_name: DummyAtom::from("circle"),
+                    }),
+                ],
+                specificity(0, 0, 1),
+                SelectorFlags::HAS_NON_FEATURELESS_COMPONENT,
+            )]))
+        );
+        assert_eq!(
+            parse_ns("svg|*", &parser),
+            Ok(SelectorList::from_vec(vec![Selector::from_vec(
+                vec![
+                    Component::Namespace(DummyAtom("svg".into()), SVG.into()),
+                    Component::ExplicitUniversalType,
+                ],
+                specificity(0, 0, 0),
+                SelectorFlags::HAS_NON_FEATURELESS_COMPONENT,
+            )]))
+        );
+        // Default namespace does not apply to attribute selectors
+        // https://github.com/mozilla/servo/pull/1652
+        // but it does apply to implicit type selectors
+        // https://github.com/servo/rust-selectors/pull/82
+        parser.default_ns = Some(MATHML.into());
+        assert_eq!(
+            parse_ns("[Foo]", &parser),
+            Ok(SelectorList::from_vec(vec![Selector::from_vec(
+                vec![
+                    Component::DefaultNamespace(MATHML.into()),
+                    Component::AttributeInNoNamespaceExists {
+                        local_name: DummyAtom::from("Foo"),
+                        local_name_lower: DummyAtom::from("foo"),
+                    },
+                ],
+                specificity(0, 1, 0),
+                SelectorFlags::HAS_NON_FEATURELESS_COMPONENT,
+            )]))
+        );
+        // Default namespace does apply to type selectors
+        assert_eq!(
+            parse_ns("e", &parser),
+            Ok(SelectorList::from_vec(vec![Selector::from_vec(
+                vec![
+                    Component::DefaultNamespace(MATHML.into()),
+                    Component::LocalName(LocalName {
+                        name: DummyAtom::from("e"),
+                        lower_name: DummyAtom::from("e"),
+                    }),
+                ],
+                specificity(0, 0, 1),
+                SelectorFlags::HAS_NON_FEATURELESS_COMPONENT,
+            )]))
+        );
+        assert_eq!(
+            parse_ns("*", &parser),
+            Ok(SelectorList::from_vec(vec![Selector::from_vec(
+                vec![
+                    Component::DefaultNamespace(MATHML.into()),
+                    Component::ExplicitUniversalType,
+                ],
+                specificity(0, 0, 0),
+                SelectorFlags::HAS_NON_FEATURELESS_COMPONENT,
+            )]))
+        );
+        assert_eq!(
+            parse_ns("*|*", &parser),
+            Ok(SelectorList::from_vec(vec![Selector::from_vec(
+                vec![
+                    Component::ExplicitAnyNamespace,
+                    Component::ExplicitUniversalType,
+                ],
+                specificity(0, 0, 0),
+                SelectorFlags::HAS_NON_FEATURELESS_COMPONENT,
+            )]))
+        );
+        // Default namespace applies to universal and type selectors inside :not and :matches,
+        // but not otherwise.
+        assert_eq!(
+            parse_ns(":not(.cl)", &parser),
+            Ok(SelectorList::from_vec(vec![Selector::from_vec(
+                vec![
+                    Component::DefaultNamespace(MATHML.into()),
+                    Component::Negation(SelectorList::from_vec(vec![Selector::from_vec(
+                        vec![Component::Class(DummyAtom::from("cl"))],
+                        specificity(0, 1, 0),
+                        SelectorFlags::HAS_NON_FEATURELESS_COMPONENT,
+                    )])),
+                ],
+                specificity(0, 1, 0),
+                SelectorFlags::HAS_NON_FEATURELESS_COMPONENT,
+            )]))
+        );
+        assert_eq!(
+            parse_ns(":not(*)", &parser),
+            Ok(SelectorList::from_vec(vec![Selector::from_vec(
+                vec![
+                    Component::DefaultNamespace(MATHML.into()),
+                    Component::Negation(SelectorList::from_vec(vec![Selector::from_vec(
+                        vec![
+                            Component::DefaultNamespace(MATHML.into()),
+                            Component::ExplicitUniversalType,
+                        ],
+                        specificity(0, 0, 0),
+                        SelectorFlags::HAS_NON_FEATURELESS_COMPONENT,
+                    )]),),
+                ],
+                specificity(0, 0, 0),
+                SelectorFlags::HAS_NON_FEATURELESS_COMPONENT,
+            )]))
+        );
+        assert_eq!(
+            parse_ns(":not(e)", &parser),
+            Ok(SelectorList::from_vec(vec![Selector::from_vec(
+                vec![
+                    Component::DefaultNamespace(MATHML.into()),
+                    Component::Negation(SelectorList::from_vec(vec![Selector::from_vec(
+                        vec![
+                            Component::DefaultNamespace(MATHML.into()),
+                            Component::LocalName(LocalName {
+                                name: DummyAtom::from("e"),
+                                lower_name: DummyAtom::from("e"),
+                            }),
+                        ],
+                        specificity(0, 0, 1),
+                        SelectorFlags::HAS_NON_FEATURELESS_COMPONENT,
+                    )])),
+                ],
+                specificity(0, 0, 1),
+                SelectorFlags::HAS_NON_FEATURELESS_COMPONENT,
+            )]))
+        );
+        assert_eq!(
+            parse("[attr|=\"foo\"]"),
+            Ok(SelectorList::from_vec(vec![Selector::from_vec(
+                vec![Component::AttributeInNoNamespace {
+                    local_name: DummyAtom::from("attr"),
+                    operator: AttrSelectorOperator::DashMatch,
+                    value: DummyAttrValue::from("foo"),
+                    case_sensitivity: ParsedCaseSensitivity::CaseSensitive,
+                }],
+                specificity(0, 1, 0),
+                SelectorFlags::HAS_NON_FEATURELESS_COMPONENT,
+            )]))
+        );
+        // https://github.com/mozilla/servo/issues/1723
+        assert_eq!(
+            parse("::before"),
+            Ok(SelectorList::from_vec(vec![Selector::from_vec(
+                vec![
+                    Component::Combinator(Combinator::PseudoElement),
+                    Component::PseudoElement(PseudoElement::Before),
+                ],
+                specificity(0, 0, 1),
+                SelectorFlags::HAS_PSEUDO,
+            )]))
+        );
+        assert_eq!(
+            parse("::before:hover"),
+            Ok(SelectorList::from_vec(vec![Selector::from_vec(
+                vec![
+                    Component::Combinator(Combinator::PseudoElement),
+                    Component::PseudoElement(PseudoElement::Before),
+                    Component::NonTSPseudoClass(PseudoClass::Hover),
+                ],
+                specificity(0, 1, 1),
+                SelectorFlags::HAS_NON_FEATURELESS_COMPONENT | SelectorFlags::HAS_PSEUDO,
+            )]))
+        );
+        assert_eq!(
+            parse("::before:hover:hover"),
+            Ok(SelectorList::from_vec(vec![Selector::from_vec(
+                vec![
+                    Component::Combinator(Combinator::PseudoElement),
+                    Component::PseudoElement(PseudoElement::Before),
+                    Component::NonTSPseudoClass(PseudoClass::Hover),
+                    Component::NonTSPseudoClass(PseudoClass::Hover),
+                ],
+                specificity(0, 2, 1),
+                SelectorFlags::HAS_NON_FEATURELESS_COMPONENT | SelectorFlags::HAS_PSEUDO,
+            )]))
+        );
+        assert!(parse("::before:hover:lang(foo)").is_err());
+        assert!(parse("::before:hover .foo").is_err());
+        assert!(parse("::before .foo").is_err());
+        assert!(parse("::before ~ bar").is_err());
+        assert!(parse("::before:active").is_ok());
+
+        // https://github.com/servo/servo/issues/15335
+        assert!(parse(":: before").is_err());
+        assert_eq!(
+            parse("div ::after"),
+            Ok(SelectorList::from_vec(vec![Selector::from_vec(
+                vec![
+                    Component::LocalName(LocalName {
+                        name: DummyAtom::from("div"),
+                        lower_name: DummyAtom::from("div"),
+                    }),
+                    Component::Combinator(Combinator::Descendant),
+                    Component::Combinator(Combinator::PseudoElement),
+                    Component::PseudoElement(PseudoElement::After),
+                ],
+                specificity(0, 0, 2),
+                SelectorFlags::HAS_NON_FEATURELESS_COMPONENT | SelectorFlags::HAS_PSEUDO,
+            )]))
+        );
+        assert_eq!(
+            parse("#d1 > .ok"),
+            Ok(SelectorList::from_vec(vec![Selector::from_vec(
+                vec![
+                    Component::ID(DummyAtom::from("d1")),
+                    Component::Combinator(Combinator::Child),
+                    Component::Class(DummyAtom::from("ok")),
+                ],
+                (1 << 20) + (1 << 10) + (0 << 0),
+                SelectorFlags::HAS_NON_FEATURELESS_COMPONENT,
+            )]))
+        );
+        parser.default_ns = None;
+        assert!(parse(":not(#provel.old)").is_ok());
+        assert!(parse(":not(#provel > old)").is_ok());
+        assert!(parse("table[rules]:not([rules=\"none\"]):not([rules=\"\"])").is_ok());
+        // https://github.com/servo/servo/issues/16017
+        assert_eq!(
+            parse_ns(":not(*)", &parser),
+            Ok(SelectorList::from_vec(vec![Selector::from_vec(
+                vec![Component::Negation(SelectorList::from_vec(vec![
+                    Selector::from_vec(
+                        vec![Component::ExplicitUniversalType],
+                        specificity(0, 0, 0),
+                        SelectorFlags::HAS_NON_FEATURELESS_COMPONENT,
+                    )
+                ]))],
+                specificity(0, 0, 0),
+                SelectorFlags::HAS_NON_FEATURELESS_COMPONENT,
+            )]))
+        );
+        assert_eq!(
+            parse_ns(":not(|*)", &parser),
+            Ok(SelectorList::from_vec(vec![Selector::from_vec(
+                vec![Component::Negation(SelectorList::from_vec(vec![
+                    Selector::from_vec(
+                        vec![
+                            Component::ExplicitNoNamespace,
+                            Component::ExplicitUniversalType,
+                        ],
+                        specificity(0, 0, 0),
+                        SelectorFlags::HAS_NON_FEATURELESS_COMPONENT,
+                    )
+                ]))],
+                specificity(0, 0, 0),
+                SelectorFlags::HAS_NON_FEATURELESS_COMPONENT,
+            )]))
+        );
+        // *| should be elided if there is no default namespace.
+        // https://github.com/servo/servo/pull/17537
+        assert_eq!(
+            parse_ns_expected(":not(*|*)", &parser, Some(":not(*)")),
+            Ok(SelectorList::from_vec(vec![Selector::from_vec(
+                vec![Component::Negation(SelectorList::from_vec(vec![
+                    Selector::from_vec(
+                        vec![Component::ExplicitUniversalType],
+                        specificity(0, 0, 0),
+                        SelectorFlags::HAS_NON_FEATURELESS_COMPONENT,
+                    )
+                ]))],
+                specificity(0, 0, 0),
+                SelectorFlags::HAS_NON_FEATURELESS_COMPONENT,
+            )]))
+        );
+
+        assert!(parse("::highlight(foo)").is_ok());
+
+        assert!(parse("::slotted()").is_err());
+        assert!(parse("::slotted(div)").is_ok());
+        assert!(parse("::slotted(div).foo").is_err());
+        assert!(parse("::slotted(div + bar)").is_err());
+        assert!(parse("::slotted(div) + foo").is_err());
+
+        assert!(parse("::part()").is_err());
+        assert!(parse("::part(42)").is_err());
+        assert!(parse("::part(foo bar)").is_ok());
+        assert!(parse("::part(foo):hover").is_ok());
+        assert!(parse("::part(foo) + bar").is_err());
+
+        assert!(parse("div ::slotted(div)").is_ok());
+        assert!(parse("div + slot::slotted(div)").is_ok());
+        assert!(parse("div + slot::slotted(div.foo)").is_ok());
+        assert!(parse("slot::slotted(div,foo)::first-line").is_err());
+        assert!(parse("::slotted(div)::before").is_ok());
+        assert!(parse("slot::slotted(div,foo)").is_err());
+
+        assert!(parse("foo:where()").is_ok());
+        assert!(parse("foo:where(div, foo, .bar baz)").is_ok());
+        assert!(parse("foo:where(::before)").is_ok());
+    }
+
+    #[test]
+    fn parent_selector() {
+        assert!(parse("foo &").is_ok());
+        assert_eq!(
+            parse("#foo &.bar"),
+            Ok(SelectorList::from_vec(vec![Selector::from_vec(
+                vec![
+                    Component::ID(DummyAtom::from("foo")),
+                    Component::Combinator(Combinator::Descendant),
+                    Component::ParentSelector,
+                    Component::Class(DummyAtom::from("bar")),
+                ],
+                (1 << 20) + (1 << 10) + (0 << 0),
+                SelectorFlags::HAS_PARENT | SelectorFlags::HAS_NON_FEATURELESS_COMPONENT
+            )]))
+        );
+
+        let parent = parse(".bar, div .baz").unwrap();
+        let child = parse("#foo &.bar").unwrap();
+        assert_eq!(
+            child.replace_parent_selector(&parent),
+            parse("#foo :is(.bar, div .baz).bar").unwrap()
+        );
+
+        let has_child = parse("#foo:has(&.bar)").unwrap();
+        assert_eq!(
+            has_child.replace_parent_selector(&parent),
+            parse("#foo:has(:is(.bar, div .baz).bar)").unwrap()
+        );
+
+        let child = parse("#foo").unwrap();
+        assert_eq!(
+            child.replace_parent_selector(&parent),
+            parse(":is(.bar, div .baz) #foo").unwrap()
+        );
+
+        let child =
+            parse_relative_expected("+ #foo", ParseRelative::ForNesting, Some("& + #foo")).unwrap();
+        assert_eq!(child, parse("& + #foo").unwrap());
+    }
+
+    #[test]
+    fn test_pseudo_iter() {
+        let list = parse("q::before").unwrap();
+        let selector = &list.slice()[0];
+        assert!(!selector.is_universal());
+        let mut iter = selector.iter();
+        assert_eq!(
+            iter.next(),
+            Some(&Component::PseudoElement(PseudoElement::Before))
+        );
+        assert_eq!(iter.next(), None);
+        let combinator = iter.next_sequence();
+        assert_eq!(combinator, Some(Combinator::PseudoElement));
+        assert!(matches!(iter.next(), Some(&Component::LocalName(..))));
+        assert_eq!(iter.next(), None);
+        assert_eq!(iter.next_sequence(), None);
+    }
+
+    #[test]
+    fn test_universal() {
+        let list = parse_ns(
+            "*|*::before",
+            &DummyParser::default_with_namespace(DummyAtom::from("https://mozilla.org")),
+        )
+        .unwrap();
+        let selector = &list.slice()[0];
+        assert!(selector.is_universal());
+    }
+
+    #[test]
+    fn test_empty_pseudo_iter() {
+        let list = parse("::before").unwrap();
+        let selector = &list.slice()[0];
+        assert!(selector.is_universal());
+        let mut iter = selector.iter();
+        assert_eq!(
+            iter.next(),
+            Some(&Component::PseudoElement(PseudoElement::Before))
+        );
+        assert_eq!(iter.next(), None);
+        assert_eq!(iter.next_sequence(), Some(Combinator::PseudoElement));
+        assert_eq!(iter.next(), None);
+        assert_eq!(iter.next_sequence(), None);
+    }
+
+    struct TestVisitor {
+        seen: Vec<String>,
+    }
+
+    impl SelectorVisitor for TestVisitor {
+        type Impl = DummySelectorImpl;
+
+        fn visit_simple_selector(&mut self, s: &Component<DummySelectorImpl>) -> bool {
+            let mut dest = String::new();
+            s.to_css(&mut dest).unwrap();
+            self.seen.push(dest);
+            true
+        }
+    }
+
+    #[test]
+    fn visitor() {
+        let mut test_visitor = TestVisitor { seen: vec![] };
+        parse(":not(:hover) ~ label").unwrap().slice()[0].visit(&mut test_visitor);
+        assert!(test_visitor.seen.contains(&":hover".into()));
+
+        let mut test_visitor = TestVisitor { seen: vec![] };
+        parse("::before:hover").unwrap().slice()[0].visit(&mut test_visitor);
+        assert!(test_visitor.seen.contains(&":hover".into()));
+    }
+}
diff --git a/servo/components/selectors/relative_selector/cache.rs b/servo/components/selectors/relative_selector/cache.rs
new file mode 100644
index 0000000000..d7681aa3a4
--- /dev/null
+++ b/servo/components/selectors/relative_selector/cache.rs
@@ -0,0 +1,81 @@
+/* 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 fxhash::FxHashMap;
+/// Relative selector cache. This is useful for following cases.
+/// First case is non-subject relative selector: Imagine `.anchor:has(<..>) ~ .foo`, with DOM
+/// `.anchor + .foo + .. + .foo`. Each match on `.foo` triggers `:has()` traversal that
+/// yields the same result. This is simple enough, since we just need to store
+/// the exact match on that anchor pass/fail.
+/// Second case is `querySelectorAll`: Imagine `querySelectorAll(':has(.a)')`, with DOM
+/// `div > .. > div > .a`. When the we perform the traversal at the top div,
+/// we basically end up evaluating `:has(.a)` for all anchors, which could be reused.
+/// Also consider the sibling version: `querySelectorAll(':has(~ .a)')` with DOM
+/// `div + .. + div + .a`.
+/// TODO(dshin): Second case is not yet handled. That is tracked in Bug 1845291.
+use std::hash::Hash;
+
+use crate::parser::{RelativeSelector, SelectorKey};
+use crate::{tree::OpaqueElement, SelectorImpl};
+
+/// Match data for a given element and a selector.
+#[derive(Clone, Copy)]
+pub enum RelativeSelectorCachedMatch {
+    /// This selector matches this element.
+    Matched,
+    /// This selector does not match this element.
+    NotMatched,
+}
+
+impl RelativeSelectorCachedMatch {
+    /// Is the cached result a match?
+    pub fn matched(&self) -> bool {
+        matches!(*self, Self::Matched)
+    }
+}
+
+#[derive(Clone, Copy, Hash, Eq, PartialEq)]
+struct Key {
+    element: OpaqueElement,
+    selector: SelectorKey,
+}
+
+impl Key {
+    pub fn new<Impl: SelectorImpl>(
+        element: OpaqueElement,
+        selector: &RelativeSelector<Impl>,
+    ) -> Self {
+        Key {
+            element,
+            selector: SelectorKey::new(&selector.selector),
+        }
+    }
+}
+
+/// Cache to speed up matching of relative selectors.
+#[derive(Default)]
+pub struct RelativeSelectorCache {
+    cache: FxHashMap<Key, RelativeSelectorCachedMatch>,
+}
+
+impl RelativeSelectorCache {
+    /// Add a relative selector match into the cache.
+    pub fn add<Impl: SelectorImpl>(
+        &mut self,
+        anchor: OpaqueElement,
+        selector: &RelativeSelector<Impl>,
+        matched: RelativeSelectorCachedMatch,
+    ) {
+        self.cache.insert(Key::new(anchor, selector), matched);
+    }
+
+    /// Check if we have a cache entry for the element.
+    pub fn lookup<Impl: SelectorImpl>(
+        &mut self,
+        element: OpaqueElement,
+        selector: &RelativeSelector<Impl>,
+    ) -> Option<RelativeSelectorCachedMatch> {
+        self.cache.get(&Key::new(element, selector)).copied()
+    }
+}
diff --git a/servo/components/selectors/relative_selector/filter.rs b/servo/components/selectors/relative_selector/filter.rs
new file mode 100644
index 0000000000..3c3eb7d2fa
--- /dev/null
+++ b/servo/components/selectors/relative_selector/filter.rs
@@ -0,0 +1,159 @@
+/* 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/. */
+
+/// Bloom filter for relative selectors.
+use fxhash::FxHashMap;
+
+use crate::bloom::BloomFilter;
+use crate::context::QuirksMode;
+use crate::parser::{collect_selector_hashes, RelativeSelector, RelativeSelectorMatchHint};
+use crate::tree::{Element, OpaqueElement};
+use crate::SelectorImpl;
+
+enum Entry {
+    /// Filter lookup happened once. Construction of the filter is expensive,
+    /// so this is set when the element for subtree traversal is encountered.
+    Lookup,
+    /// Filter lookup happened more than once, and the filter for this element's
+    /// subtree traversal is constructed. Could use special handlings for pseudo-classes
+    /// such as `:hover` and `:focus`, see Bug 1845503.
+    HasFilter(Box<BloomFilter>),
+}
+
+#[derive(Clone, Copy, Hash, Eq, PartialEq)]
+enum TraversalKind {
+    Children,
+    Descendants,
+}
+
+fn add_to_filter<E: Element>(element: &E, filter: &mut BloomFilter, kind: TraversalKind) -> bool {
+    let mut child = element.first_element_child();
+    while let Some(e) = child {
+        if !e.add_element_unique_hashes(filter) {
+            return false;
+        }
+        if kind == TraversalKind::Descendants {
+            if !add_to_filter(&e, filter, kind) {
+                return false;
+            }
+        }
+        child = e.next_sibling_element();
+    }
+    true
+}
+
+#[derive(Clone, Copy, Hash, Eq, PartialEq)]
+struct Key(OpaqueElement, TraversalKind);
+
+/// Map of bloom filters for fast-rejecting relative selectors.
+#[derive(Default)]
+pub struct RelativeSelectorFilterMap {
+    map: FxHashMap<Key, Entry>,
+}
+
+fn fast_reject<Impl: SelectorImpl>(
+    selector: &RelativeSelector<Impl>,
+    quirks_mode: QuirksMode,
+    filter: &BloomFilter,
+) -> bool {
+    let mut hashes = [0u32; 4];
+    let mut len = 0;
+    // For inner selectors, we only collect from the single rightmost compound.
+    // This is because inner selectors can cause breakouts: e.g. `.anchor:has(:is(.a .b) .c)`
+    // can match when `.a` is the ancestor of `.anchor`. Including `.a` would possibly fast
+    // reject the subtree for not having `.a`, even if the selector would match.
+    // Technically, if the selector's traversal is non-sibling subtree, we can traverse
+    // inner selectors up to the point where a descendant/child combinator is encountered
+    // (e.g. In `.anchor:has(:is(.a ~ .b) .c)`, `.a` is guaranteed to be the a descendant
+    // of `.anchor`). While that can be separately handled, well, this is simpler.
+    collect_selector_hashes(
+        selector.selector.iter(),
+        quirks_mode,
+        &mut hashes,
+        &mut len,
+        |s| s.iter(),
+    );
+    for i in 0..len {
+        if !filter.might_contain_hash(hashes[i]) {
+            // Definitely rejected.
+            return true;
+        }
+    }
+    false
+}
+
+impl RelativeSelectorFilterMap {
+    fn get_filter<E: Element>(&mut self, element: &E, kind: TraversalKind) -> Option<&BloomFilter> {
+        // Insert flag to indicate that we looked up the filter once, and
+        // create the filter if and only if that flag is there.
+        let key = Key(element.opaque(), kind);
+        let entry = self
+            .map
+            .entry(key)
+            .and_modify(|entry| {
+                if !matches!(entry, Entry::Lookup) {
+                    return;
+                }
+                let mut filter = BloomFilter::new();
+                // Go through all children/descendants of this element and add their hashes.
+                if add_to_filter(element, &mut filter, kind) {
+                    *entry = Entry::HasFilter(Box::new(filter));
+                }
+            })
+            .or_insert(Entry::Lookup);
+        match entry {
+            Entry::Lookup => None,
+            Entry::HasFilter(ref filter) => Some(filter.as_ref()),
+        }
+    }
+
+    /// Potentially reject the given selector for this element.
+    /// This may seem redundant in presence of the cache, but the cache keys into the
+    /// selector-element pair specifically, while this filter keys to the element
+    /// and the traversal kind, so it is useful for handling multiple selectors
+    /// that effectively end up looking at the same(-ish, for siblings) subtree.
+    pub fn fast_reject<Impl: SelectorImpl, E: Element>(
+        &mut self,
+        element: &E,
+        selector: &RelativeSelector<Impl>,
+        quirks_mode: QuirksMode,
+    ) -> bool {
+        if matches!(
+            selector.match_hint,
+            RelativeSelectorMatchHint::InNextSibling
+        ) {
+            // Don't bother.
+            return false;
+        }
+        let is_sibling = matches!(
+            selector.match_hint,
+            RelativeSelectorMatchHint::InSibling |
+                RelativeSelectorMatchHint::InNextSiblingSubtree |
+                RelativeSelectorMatchHint::InSiblingSubtree
+        );
+        let is_subtree = matches!(
+            selector.match_hint,
+            RelativeSelectorMatchHint::InSubtree |
+                RelativeSelectorMatchHint::InNextSiblingSubtree |
+                RelativeSelectorMatchHint::InSiblingSubtree
+        );
+        let kind = if is_subtree {
+            TraversalKind::Descendants
+        } else {
+            TraversalKind::Children
+        };
+        if is_sibling {
+            // Contain the entirety of the parent's children/subtree in the filter, and use that.
+            // This is less likely to reject, especially for sibling subtree matches; however, it's less
+            // expensive memory-wise, compared to storing filters for each sibling.
+            element.parent_element().map_or(false, |parent| {
+                self.get_filter(&parent, kind)
+                    .map_or(false, |filter| fast_reject(selector, quirks_mode, filter))
+            })
+        } else {
+            self.get_filter(element, kind)
+                .map_or(false, |filter| fast_reject(selector, quirks_mode, filter))
+        }
+    }
+}
diff --git a/servo/components/selectors/relative_selector/mod.rs b/servo/components/selectors/relative_selector/mod.rs
new file mode 100644
index 0000000000..6dd39f7327
--- /dev/null
+++ b/servo/components/selectors/relative_selector/mod.rs
@@ -0,0 +1,6 @@
+/* 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/. */
+
+pub mod cache;
+pub mod filter;
diff --git a/servo/components/selectors/sink.rs b/servo/components/selectors/sink.rs
new file mode 100644
index 0000000000..dcdd7ff259
--- /dev/null
+++ b/servo/components/selectors/sink.rs
@@ -0,0 +1,31 @@
+/* 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/. */
+
+//! Small helpers to abstract over different containers.
+#![deny(missing_docs)]
+
+use smallvec::{Array, SmallVec};
+
+/// A trait to abstract over a `push` method that may be implemented for
+/// different kind of types.
+///
+/// Used to abstract over `Array`, `SmallVec` and `Vec`, and also to implement a
+/// type which `push` method does only tweak a byte when we only need to check
+/// for the presence of something.
+pub trait Push<T> {
+    /// Push a value into self.
+    fn push(&mut self, value: T);
+}
+
+impl<T> Push<T> for Vec<T> {
+    fn push(&mut self, value: T) {
+        Vec::push(self, value);
+    }
+}
+
+impl<A: Array> Push<A::Item> for SmallVec<A> {
+    fn push(&mut self, value: A::Item) {
+        SmallVec::push(self, value);
+    }
+}
diff --git a/servo/components/selectors/tree.rs b/servo/components/selectors/tree.rs
new file mode 100644
index 0000000000..c1ea8ff5ae
--- /dev/null
+++ b/servo/components/selectors/tree.rs
@@ -0,0 +1,168 @@
+/* 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/. */
+
+//! Traits that nodes must implement. Breaks the otherwise-cyclic dependency
+//! between layout and style.
+
+use crate::attr::{AttrSelectorOperation, CaseSensitivity, NamespaceConstraint};
+use crate::bloom::BloomFilter;
+use crate::matching::{ElementSelectorFlags, MatchingContext};
+use crate::parser::SelectorImpl;
+use std::fmt::Debug;
+use std::ptr::NonNull;
+
+/// Opaque representation of an Element, for identity comparisons.
+#[derive(Clone, Copy, Debug, Eq, Hash, PartialEq)]
+pub struct OpaqueElement(NonNull<()>);
+
+unsafe impl Send for OpaqueElement {}
+
+impl OpaqueElement {
+    /// Creates a new OpaqueElement from an arbitrarily-typed pointer.
+    pub fn new<T>(ptr: &T) -> Self {
+        unsafe {
+            OpaqueElement(NonNull::new_unchecked(
+                ptr as *const T as *const () as *mut (),
+            ))
+        }
+    }
+}
+
+pub trait Element: Sized + Clone + Debug {
+    type Impl: SelectorImpl;
+
+    /// Converts self into an opaque representation.
+    fn opaque(&self) -> OpaqueElement;
+
+    fn parent_element(&self) -> Option<Self>;
+
+    /// Whether the parent node of this element is a shadow root.
+    fn parent_node_is_shadow_root(&self) -> bool;
+
+    /// The host of the containing shadow root, if any.
+    fn containing_shadow_host(&self) -> Option<Self>;
+
+    /// The parent of a given pseudo-element, after matching a pseudo-element
+    /// selector.
+    ///
+    /// This is guaranteed to be called in a pseudo-element.
+    fn pseudo_element_originating_element(&self) -> Option<Self> {
+        debug_assert!(self.is_pseudo_element());
+        self.parent_element()
+    }
+
+    /// Whether we're matching on a pseudo-element.
+    fn is_pseudo_element(&self) -> bool;
+
+    /// Skips non-element nodes
+    fn prev_sibling_element(&self) -> Option<Self>;
+
+    /// Skips non-element nodes
+    fn next_sibling_element(&self) -> Option<Self>;
+
+    /// Skips non-element nodes
+    fn first_element_child(&self) -> Option<Self>;
+
+    fn is_html_element_in_html_document(&self) -> bool;
+
+    fn has_local_name(&self, local_name: &<Self::Impl as SelectorImpl>::BorrowedLocalName) -> bool;
+
+    /// Empty string for no namespace
+    fn has_namespace(&self, ns: &<Self::Impl as SelectorImpl>::BorrowedNamespaceUrl) -> bool;
+
+    /// Whether this element and the `other` element have the same local name and namespace.
+    fn is_same_type(&self, other: &Self) -> bool;
+
+    fn attr_matches(
+        &self,
+        ns: &NamespaceConstraint<&<Self::Impl as SelectorImpl>::NamespaceUrl>,
+        local_name: &<Self::Impl as SelectorImpl>::LocalName,
+        operation: &AttrSelectorOperation<&<Self::Impl as SelectorImpl>::AttrValue>,
+    ) -> bool;
+
+    fn has_attr_in_no_namespace(
+        &self,
+        local_name: &<Self::Impl as SelectorImpl>::LocalName,
+    ) -> bool {
+        self.attr_matches(
+            &NamespaceConstraint::Specific(&crate::parser::namespace_empty_string::<Self::Impl>()),
+            local_name,
+            &AttrSelectorOperation::Exists,
+        )
+    }
+
+    fn match_non_ts_pseudo_class(
+        &self,
+        pc: &<Self::Impl as SelectorImpl>::NonTSPseudoClass,
+        context: &mut MatchingContext<Self::Impl>,
+    ) -> bool;
+
+    fn match_pseudo_element(
+        &self,
+        pe: &<Self::Impl as SelectorImpl>::PseudoElement,
+        context: &mut MatchingContext<Self::Impl>,
+    ) -> bool;
+
+    /// Sets selector flags on the elemnt itself or the parent, depending on the
+    /// flags, which indicate what kind of work may need to be performed when
+    /// DOM state changes.
+    fn apply_selector_flags(&self, flags: ElementSelectorFlags);
+
+    /// Whether this element is a `link`.
+    fn is_link(&self) -> bool;
+
+    /// Returns whether the element is an HTML <slot> element.
+    fn is_html_slot_element(&self) -> bool;
+
+    /// Returns the assigned <slot> element this element is assigned to.
+    ///
+    /// Necessary for the `::slotted` pseudo-class.
+    fn assigned_slot(&self) -> Option<Self> {
+        None
+    }
+
+    fn has_id(
+        &self,
+        id: &<Self::Impl as SelectorImpl>::Identifier,
+        case_sensitivity: CaseSensitivity,
+    ) -> bool;
+
+    fn has_class(
+        &self,
+        name: &<Self::Impl as SelectorImpl>::Identifier,
+        case_sensitivity: CaseSensitivity,
+    ) -> bool;
+
+    /// Returns the mapping from the `exportparts` attribute in the reverse
+    /// direction, that is, in an outer-tree -> inner-tree direction.
+    fn imported_part(
+        &self,
+        name: &<Self::Impl as SelectorImpl>::Identifier,
+    ) -> Option<<Self::Impl as SelectorImpl>::Identifier>;
+
+    fn is_part(&self, name: &<Self::Impl as SelectorImpl>::Identifier) -> bool;
+
+    /// Returns whether this element matches `:empty`.
+    ///
+    /// That is, whether it does not contain any child element or any non-zero-length text node.
+    /// See http://dev.w3.org/csswg/selectors-3/#empty-pseudo
+    fn is_empty(&self) -> bool;
+
+    /// Returns whether this element matches `:root`,
+    /// i.e. whether it is the root element of a document.
+    ///
+    /// Note: this can be false even if `.parent_element()` is `None`
+    /// if the parent node is a `DocumentFragment`.
+    fn is_root(&self) -> bool;
+
+    /// Returns whether this element should ignore matching nth child
+    /// selector.
+    fn ignores_nth_child_selectors(&self) -> bool {
+        false
+    }
+
+    /// Add hashes unique to this element to the given filter, returning true
+    /// if any got added.
+    fn add_element_unique_hashes(&self, filter: &mut BloomFilter) -> bool;
+}
diff --git a/servo/components/selectors/visitor.rs b/servo/components/selectors/visitor.rs
new file mode 100644
index 0000000000..d5befbc68b
--- /dev/null
+++ b/servo/components/selectors/visitor.rs
@@ -0,0 +1,136 @@
+/* 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/. */
+
+//! Visitor traits for selectors.
+
+#![deny(missing_docs)]
+
+use crate::attr::NamespaceConstraint;
+use crate::parser::{Combinator, Component, RelativeSelector, Selector, SelectorImpl};
+
+/// A trait to visit selector properties.
+///
+/// All the `visit_foo` methods return a boolean indicating whether the
+/// traversal should continue or not.
+pub trait SelectorVisitor: Sized {
+    /// The selector implementation this visitor wants to visit.
+    type Impl: SelectorImpl;
+
+    /// Visit an attribute selector that may match (there are other selectors
+    /// that may never match, like those containing whitespace or the empty
+    /// string).
+    fn visit_attribute_selector(
+        &mut self,
+        _namespace: &NamespaceConstraint<&<Self::Impl as SelectorImpl>::NamespaceUrl>,
+        _local_name: &<Self::Impl as SelectorImpl>::LocalName,
+        _local_name_lower: &<Self::Impl as SelectorImpl>::LocalName,
+    ) -> bool {
+        true
+    }
+
+    /// Visit a simple selector.
+    fn visit_simple_selector(&mut self, _: &Component<Self::Impl>) -> bool {
+        true
+    }
+
+    /// Visit a nested relative selector list. The caller is responsible to call visit
+    /// into the internal selectors if / as needed.
+    ///
+    /// The default implementation skips it altogether.
+    fn visit_relative_selector_list(&mut self, _list: &[RelativeSelector<Self::Impl>]) -> bool {
+        true
+    }
+
+    /// Visit a nested selector list. The caller is responsible to call visit
+    /// into the internal selectors if / as needed.
+    ///
+    /// The default implementation does this.
+    fn visit_selector_list(
+        &mut self,
+        _list_kind: SelectorListKind,
+        list: &[Selector<Self::Impl>],
+    ) -> bool {
+        for nested in list {
+            if !nested.visit(self) {
+                return false;
+            }
+        }
+        true
+    }
+
+    /// Visits a complex selector.
+    ///
+    /// Gets the combinator to the right of the selector, or `None` if the
+    /// selector is the rightmost one.
+    fn visit_complex_selector(&mut self, _combinator_to_right: Option<Combinator>) -> bool {
+        true
+    }
+}
+
+bitflags! {
+    /// The kinds of components the visitor is visiting the selector list of, if any
+    #[derive(Clone, Copy, Default)]
+    pub struct SelectorListKind: u8 {
+        /// The visitor is inside :not(..)
+        const NEGATION = 1 << 0;
+        /// The visitor is inside :is(..)
+        const IS = 1 << 1;
+        /// The visitor is inside :where(..)
+        const WHERE = 1 << 2;
+        /// The visitor is inside :nth-child(.. of <selector list>) or
+        /// :nth-last-child(.. of <selector list>)
+        const NTH_OF = 1 << 3;
+        /// The visitor is inside :has(..)
+        const HAS = 1 << 4;
+    }
+}
+
+impl SelectorListKind {
+    /// Construct a SelectorListKind for the corresponding component.
+    pub fn from_component<Impl: SelectorImpl>(component: &Component<Impl>) -> Self {
+        match component {
+            Component::Negation(_) => SelectorListKind::NEGATION,
+            Component::Is(_) => SelectorListKind::IS,
+            Component::Where(_) => SelectorListKind::WHERE,
+            Component::NthOf(_) => SelectorListKind::NTH_OF,
+            _ => SelectorListKind::empty(),
+        }
+    }
+
+    /// Whether the visitor is inside :not(..)
+    pub fn in_negation(&self) -> bool {
+        self.intersects(SelectorListKind::NEGATION)
+    }
+
+    /// Whether the visitor is inside :is(..)
+    pub fn in_is(&self) -> bool {
+        self.intersects(SelectorListKind::IS)
+    }
+
+    /// Whether the visitor is inside :where(..)
+    pub fn in_where(&self) -> bool {
+        self.intersects(SelectorListKind::WHERE)
+    }
+
+    /// Whether the visitor is inside :nth-child(.. of <selector list>) or
+    /// :nth-last-child(.. of <selector list>)
+    pub fn in_nth_of(&self) -> bool {
+        self.intersects(SelectorListKind::NTH_OF)
+    }
+
+    /// Whether the visitor is inside :has(..)
+    pub fn in_has(&self) -> bool {
+        self.intersects(SelectorListKind::HAS)
+    }
+
+    /// Whether this nested selector is relevant for nth-of dependencies.
+    pub fn relevant_to_nth_of_dependencies(&self) -> bool {
+        // Order of nesting for `:has` and `:nth-child(.. of ..)` doesn't matter, because:
+        // * `:has(:nth-child(.. of ..))`: The location of the anchoring element is
+        //   independent from where `:nth-child(.. of ..)` is applied.
+        // * `:nth-child(.. of :has(..))`: Invalidations inside `:has` must first use the
+        //   `:has` machinary to find the anchor, then carry out the remaining invalidation.
+        self.in_nth_of() && !self.in_has()
+    }
+}