Adding upstream version 124.0.1.upstream/124.0.1

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

12 files changed, 5928 insertions, 0 deletions

diff --git a/servo/components/style/invalidation/element/document_state.rs b/servo/components/style/invalidation/element/document_state.rs
new file mode 100644
index 0000000000..0b846510d8
--- /dev/null
+++ b/servo/components/style/invalidation/element/document_state.rs
@@ -0,0 +1,154 @@
+/* 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/. */
+
+//! An invalidation processor for style changes due to document state changes.
+
+use crate::dom::TElement;
+use crate::invalidation::element::invalidation_map::Dependency;
+use crate::invalidation::element::invalidator::{
+    DescendantInvalidationLists, InvalidationVector, SiblingTraversalMap,
+};
+use crate::invalidation::element::invalidator::{Invalidation, InvalidationProcessor};
+use crate::invalidation::element::state_and_attributes;
+use crate::stylist::CascadeData;
+use dom::DocumentState;
+use selectors::matching::{
+    MatchingContext, MatchingForInvalidation, MatchingMode, NeedsSelectorFlags, QuirksMode,
+    SelectorCaches, VisitedHandlingMode,
+};
+
+/// A struct holding the members necessary to invalidate document state
+/// selectors.
+#[derive(Debug)]
+pub struct InvalidationMatchingData {
+    /// The document state that has changed, which makes it always match.
+    pub document_state: DocumentState,
+}
+
+impl Default for InvalidationMatchingData {
+    #[inline(always)]
+    fn default() -> Self {
+        Self {
+            document_state: DocumentState::empty(),
+        }
+    }
+}
+
+/// An invalidation processor for style changes due to state and attribute
+/// changes.
+pub struct DocumentStateInvalidationProcessor<'a, 'b, E: TElement, I> {
+    rules: I,
+    matching_context: MatchingContext<'a, E::Impl>,
+    traversal_map: SiblingTraversalMap<E>,
+    document_states_changed: DocumentState,
+    _marker: std::marker::PhantomData<&'b ()>,
+}
+
+impl<'a, 'b, E: TElement, I> DocumentStateInvalidationProcessor<'a, 'b, E, I> {
+    /// Creates a new DocumentStateInvalidationProcessor.
+    #[inline]
+    pub fn new(
+        rules: I,
+        document_states_changed: DocumentState,
+        selector_caches: &'a mut SelectorCaches,
+        quirks_mode: QuirksMode,
+    ) -> Self {
+        let mut matching_context = MatchingContext::<'a, E::Impl>::new_for_visited(
+            MatchingMode::Normal,
+            None,
+            selector_caches,
+            VisitedHandlingMode::AllLinksVisitedAndUnvisited,
+            quirks_mode,
+            NeedsSelectorFlags::No,
+            MatchingForInvalidation::No,
+        );
+
+        matching_context.extra_data.invalidation_data.document_state = document_states_changed;
+
+        Self {
+            rules,
+            document_states_changed,
+            matching_context,
+            traversal_map: SiblingTraversalMap::default(),
+            _marker: std::marker::PhantomData,
+        }
+    }
+}
+
+impl<'a, 'b, E, I> InvalidationProcessor<'b, 'a, E>
+    for DocumentStateInvalidationProcessor<'a, 'b, E, I>
+where
+    E: TElement,
+    I: Iterator<Item = &'b CascadeData>,
+{
+    fn check_outer_dependency(&mut self, _: &Dependency, _: E) -> bool {
+        debug_assert!(
+            false,
+            "how, we should only have parent-less dependencies here!"
+        );
+        true
+    }
+
+    fn collect_invalidations(
+        &mut self,
+        _element: E,
+        self_invalidations: &mut InvalidationVector<'b>,
+        _descendant_invalidations: &mut DescendantInvalidationLists<'b>,
+        _sibling_invalidations: &mut InvalidationVector<'b>,
+    ) -> bool {
+        for cascade_data in &mut self.rules {
+            let map = cascade_data.invalidation_map();
+            for dependency in &map.document_state_selectors {
+                if !dependency.state.intersects(self.document_states_changed) {
+                    continue;
+                }
+
+                // We pass `None` as a scope, as document state selectors aren't
+                // affected by the current scope.
+                //
+                // FIXME(emilio): We should really pass the relevant host for
+                // self.rules, so that we invalidate correctly if the selector
+                // happens to have something like :host(:-moz-window-inactive)
+                // for example.
+                self_invalidations.push(Invalidation::new(
+                    &dependency.dependency,
+                    /* scope = */ None,
+                ));
+            }
+        }
+
+        false
+    }
+
+    fn matching_context(&mut self) -> &mut MatchingContext<'a, E::Impl> {
+        &mut self.matching_context
+    }
+
+    fn sibling_traversal_map(&self) -> &SiblingTraversalMap<E> {
+        &self.traversal_map
+    }
+
+    fn recursion_limit_exceeded(&mut self, _: E) {
+        unreachable!("We don't run document state invalidation with stack limits")
+    }
+
+    fn should_process_descendants(&mut self, element: E) -> bool {
+        match element.borrow_data() {
+            Some(d) => state_and_attributes::should_process_descendants(&d),
+            None => false,
+        }
+    }
+
+    fn invalidated_descendants(&mut self, element: E, child: E) {
+        state_and_attributes::invalidated_descendants(element, child)
+    }
+
+    fn invalidated_self(&mut self, element: E) {
+        state_and_attributes::invalidated_self(element);
+    }
+
+    fn invalidated_sibling(&mut self, sibling: E, of: E) {
+        state_and_attributes::invalidated_sibling(sibling, of);
+    }
+}
diff --git a/servo/components/style/invalidation/element/element_wrapper.rs b/servo/components/style/invalidation/element/element_wrapper.rs
new file mode 100644
index 0000000000..e17afd7774
--- /dev/null
+++ b/servo/components/style/invalidation/element/element_wrapper.rs
@@ -0,0 +1,388 @@
+/* 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/. */
+
+//! A wrapper over an element and a snapshot, that allows us to selector-match
+//! against a past state of the element.
+
+use crate::dom::TElement;
+use crate::selector_parser::{AttrValue, NonTSPseudoClass, PseudoElement, SelectorImpl};
+use crate::selector_parser::{Snapshot, SnapshotMap};
+use crate::values::AtomIdent;
+use crate::{CaseSensitivityExt, LocalName, Namespace, WeakAtom};
+use dom::ElementState;
+use selectors::attr::{AttrSelectorOperation, CaseSensitivity, NamespaceConstraint};
+use selectors::bloom::BloomFilter;
+use selectors::matching::{ElementSelectorFlags, MatchingContext};
+use selectors::{Element, OpaqueElement};
+use std::cell::Cell;
+use std::fmt;
+
+/// In order to compute restyle hints, we perform a selector match against a
+/// list of partial selectors whose rightmost simple selector may be sensitive
+/// to the thing being changed. We do this matching twice, once for the element
+/// as it exists now and once for the element as it existed at the time of the
+/// last restyle. If the results of the selector match differ, that means that
+/// the given partial selector is sensitive to the change, and we compute a
+/// restyle hint based on its combinator.
+///
+/// In order to run selector matching against the old element state, we generate
+/// a wrapper for the element which claims to have the old state. This is the
+/// ElementWrapper logic below.
+///
+/// Gecko does this differently for element states, and passes a mask called
+/// mStateMask, which indicates the states that need to be ignored during
+/// selector matching. This saves an ElementWrapper allocation and an additional
+/// selector match call at the expense of additional complexity inside the
+/// selector matching logic. This only works for boolean states though, so we
+/// still need to take the ElementWrapper approach for attribute-dependent
+/// style. So we do it the same both ways for now to reduce complexity, but it's
+/// worth measuring the performance impact (if any) of the mStateMask approach.
+pub trait ElementSnapshot: Sized {
+    /// The state of the snapshot, if any.
+    fn state(&self) -> Option<ElementState>;
+
+    /// If this snapshot contains attribute information.
+    fn has_attrs(&self) -> bool;
+
+    /// Gets the attribute information of the snapshot as a string.
+    ///
+    /// Only for debugging purposes.
+    fn debug_list_attributes(&self) -> String {
+        String::new()
+    }
+
+    /// The ID attribute per this snapshot. Should only be called if
+    /// `has_attrs()` returns true.
+    fn id_attr(&self) -> Option<&WeakAtom>;
+
+    /// Whether this snapshot contains the class `name`. Should only be called
+    /// if `has_attrs()` returns true.
+    fn has_class(&self, name: &AtomIdent, case_sensitivity: CaseSensitivity) -> bool;
+
+    /// Whether this snapshot represents the part named `name`. Should only be
+    /// called if `has_attrs()` returns true.
+    fn is_part(&self, name: &AtomIdent) -> bool;
+
+    /// See Element::imported_part.
+    fn imported_part(&self, name: &AtomIdent) -> Option<AtomIdent>;
+
+    /// A callback that should be called for each class of the snapshot. Should
+    /// only be called if `has_attrs()` returns true.
+    fn each_class<F>(&self, _: F)
+    where
+        F: FnMut(&AtomIdent);
+
+    /// The `xml:lang=""` or `lang=""` attribute value per this snapshot.
+    fn lang_attr(&self) -> Option<AttrValue>;
+}
+
+/// A simple wrapper over an element and a snapshot, that allows us to
+/// selector-match against a past state of the element.
+#[derive(Clone)]
+pub struct ElementWrapper<'a, E>
+where
+    E: TElement,
+{
+    element: E,
+    cached_snapshot: Cell<Option<&'a Snapshot>>,
+    snapshot_map: &'a SnapshotMap,
+}
+
+impl<'a, E> ElementWrapper<'a, E>
+where
+    E: TElement,
+{
+    /// Trivially constructs an `ElementWrapper`.
+    pub fn new(el: E, snapshot_map: &'a SnapshotMap) -> Self {
+        ElementWrapper {
+            element: el,
+            cached_snapshot: Cell::new(None),
+            snapshot_map: snapshot_map,
+        }
+    }
+
+    /// Gets the snapshot associated with this element, if any.
+    pub fn snapshot(&self) -> Option<&'a Snapshot> {
+        if !self.element.has_snapshot() {
+            return None;
+        }
+
+        if let Some(s) = self.cached_snapshot.get() {
+            return Some(s);
+        }
+
+        let snapshot = self.snapshot_map.get(&self.element);
+        debug_assert!(snapshot.is_some(), "has_snapshot lied!");
+
+        self.cached_snapshot.set(snapshot);
+
+        snapshot
+    }
+
+    /// Returns the states that have changed since the element was snapshotted.
+    pub fn state_changes(&self) -> ElementState {
+        let snapshot = match self.snapshot() {
+            Some(s) => s,
+            None => return ElementState::empty(),
+        };
+
+        match snapshot.state() {
+            Some(state) => state ^ self.element.state(),
+            None => ElementState::empty(),
+        }
+    }
+
+    /// Returns the value of the `xml:lang=""` (or, if appropriate, `lang=""`)
+    /// attribute from this element's snapshot or the closest ancestor
+    /// element snapshot with the attribute specified.
+    fn get_lang(&self) -> Option<AttrValue> {
+        let mut current = self.clone();
+        loop {
+            let lang = match self.snapshot() {
+                Some(snapshot) if snapshot.has_attrs() => snapshot.lang_attr(),
+                _ => current.element.lang_attr(),
+            };
+            if lang.is_some() {
+                return lang;
+            }
+            current = current.parent_element()?;
+        }
+    }
+}
+
+impl<'a, E> fmt::Debug for ElementWrapper<'a, E>
+where
+    E: TElement,
+{
+    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
+        // Ignore other fields for now, can change later if needed.
+        self.element.fmt(f)
+    }
+}
+
+impl<'a, E> Element for ElementWrapper<'a, E>
+where
+    E: TElement,
+{
+    type Impl = SelectorImpl;
+
+    fn match_non_ts_pseudo_class(
+        &self,
+        pseudo_class: &NonTSPseudoClass,
+        context: &mut MatchingContext<Self::Impl>,
+    ) -> bool {
+        // Some pseudo-classes need special handling to evaluate them against
+        // the snapshot.
+        match *pseudo_class {
+            // For :link and :visited, we don't actually want to test the
+            // element state directly.
+            //
+            // Instead, we use the `visited_handling` to determine if they
+            // match.
+            NonTSPseudoClass::Link => {
+                return self.is_link() && context.visited_handling().matches_unvisited();
+            },
+            NonTSPseudoClass::Visited => {
+                return self.is_link() && context.visited_handling().matches_visited();
+            },
+
+            #[cfg(feature = "gecko")]
+            NonTSPseudoClass::MozTableBorderNonzero => {
+                if let Some(snapshot) = self.snapshot() {
+                    if snapshot.has_other_pseudo_class_state() {
+                        return snapshot.mIsTableBorderNonzero();
+                    }
+                }
+            },
+
+            #[cfg(feature = "gecko")]
+            NonTSPseudoClass::MozSelectListBox => {
+                if let Some(snapshot) = self.snapshot() {
+                    if snapshot.has_other_pseudo_class_state() {
+                        return snapshot.mIsSelectListBox();
+                    }
+                }
+            },
+
+            // :lang() needs to match using the closest ancestor xml:lang="" or
+            // lang="" attribtue from snapshots.
+            NonTSPseudoClass::Lang(ref lang_arg) => {
+                return self
+                    .element
+                    .match_element_lang(Some(self.get_lang()), lang_arg);
+            },
+
+            _ => {},
+        }
+
+        let flag = pseudo_class.state_flag();
+        if flag.is_empty() {
+            return self
+                .element
+                .match_non_ts_pseudo_class(pseudo_class, context);
+        }
+        match self.snapshot().and_then(|s| s.state()) {
+            Some(snapshot_state) => snapshot_state.intersects(flag),
+            None => self
+                .element
+                .match_non_ts_pseudo_class(pseudo_class, context),
+        }
+    }
+
+    fn apply_selector_flags(&self, _flags: ElementSelectorFlags) {
+        debug_assert!(false, "Shouldn't need selector flags for invalidation");
+    }
+
+    fn match_pseudo_element(
+        &self,
+        pseudo_element: &PseudoElement,
+        context: &mut MatchingContext<Self::Impl>,
+    ) -> bool {
+        self.element.match_pseudo_element(pseudo_element, context)
+    }
+
+    fn is_link(&self) -> bool {
+        match self.snapshot().and_then(|s| s.state()) {
+            Some(state) => state.intersects(ElementState::VISITED_OR_UNVISITED),
+            None => self.element.is_link(),
+        }
+    }
+
+    fn opaque(&self) -> OpaqueElement {
+        self.element.opaque()
+    }
+
+    fn parent_element(&self) -> Option<Self> {
+        let parent = self.element.parent_element()?;
+        Some(Self::new(parent, self.snapshot_map))
+    }
+
+    fn parent_node_is_shadow_root(&self) -> bool {
+        self.element.parent_node_is_shadow_root()
+    }
+
+    fn containing_shadow_host(&self) -> Option<Self> {
+        let host = self.element.containing_shadow_host()?;
+        Some(Self::new(host, self.snapshot_map))
+    }
+
+    fn prev_sibling_element(&self) -> Option<Self> {
+        let sibling = self.element.prev_sibling_element()?;
+        Some(Self::new(sibling, self.snapshot_map))
+    }
+
+    fn next_sibling_element(&self) -> Option<Self> {
+        let sibling = self.element.next_sibling_element()?;
+        Some(Self::new(sibling, self.snapshot_map))
+    }
+
+    fn first_element_child(&self) -> Option<Self> {
+        let child = self.element.first_element_child()?;
+        Some(Self::new(child, self.snapshot_map))
+    }
+
+    #[inline]
+    fn is_html_element_in_html_document(&self) -> bool {
+        self.element.is_html_element_in_html_document()
+    }
+
+    #[inline]
+    fn is_html_slot_element(&self) -> bool {
+        self.element.is_html_slot_element()
+    }
+
+    #[inline]
+    fn has_local_name(
+        &self,
+        local_name: &<Self::Impl as ::selectors::SelectorImpl>::BorrowedLocalName,
+    ) -> bool {
+        self.element.has_local_name(local_name)
+    }
+
+    #[inline]
+    fn has_namespace(
+        &self,
+        ns: &<Self::Impl as ::selectors::SelectorImpl>::BorrowedNamespaceUrl,
+    ) -> bool {
+        self.element.has_namespace(ns)
+    }
+
+    #[inline]
+    fn is_same_type(&self, other: &Self) -> bool {
+        self.element.is_same_type(&other.element)
+    }
+
+    fn attr_matches(
+        &self,
+        ns: &NamespaceConstraint<&Namespace>,
+        local_name: &LocalName,
+        operation: &AttrSelectorOperation<&AttrValue>,
+    ) -> bool {
+        match self.snapshot() {
+            Some(snapshot) if snapshot.has_attrs() => {
+                snapshot.attr_matches(ns, local_name, operation)
+            },
+            _ => self.element.attr_matches(ns, local_name, operation),
+        }
+    }
+
+    fn has_id(&self, id: &AtomIdent, case_sensitivity: CaseSensitivity) -> bool {
+        match self.snapshot() {
+            Some(snapshot) if snapshot.has_attrs() => snapshot
+                .id_attr()
+                .map_or(false, |atom| case_sensitivity.eq_atom(&atom, id)),
+            _ => self.element.has_id(id, case_sensitivity),
+        }
+    }
+
+    fn is_part(&self, name: &AtomIdent) -> bool {
+        match self.snapshot() {
+            Some(snapshot) if snapshot.has_attrs() => snapshot.is_part(name),
+            _ => self.element.is_part(name),
+        }
+    }
+
+    fn imported_part(&self, name: &AtomIdent) -> Option<AtomIdent> {
+        match self.snapshot() {
+            Some(snapshot) if snapshot.has_attrs() => snapshot.imported_part(name),
+            _ => self.element.imported_part(name),
+        }
+    }
+
+    fn has_class(&self, name: &AtomIdent, case_sensitivity: CaseSensitivity) -> bool {
+        match self.snapshot() {
+            Some(snapshot) if snapshot.has_attrs() => snapshot.has_class(name, case_sensitivity),
+            _ => self.element.has_class(name, case_sensitivity),
+        }
+    }
+
+    fn is_empty(&self) -> bool {
+        self.element.is_empty()
+    }
+
+    fn is_root(&self) -> bool {
+        self.element.is_root()
+    }
+
+    fn is_pseudo_element(&self) -> bool {
+        self.element.is_pseudo_element()
+    }
+
+    fn pseudo_element_originating_element(&self) -> Option<Self> {
+        self.element
+            .pseudo_element_originating_element()
+            .map(|e| ElementWrapper::new(e, self.snapshot_map))
+    }
+
+    fn assigned_slot(&self) -> Option<Self> {
+        self.element
+            .assigned_slot()
+            .map(|e| ElementWrapper::new(e, self.snapshot_map))
+    }
+
+    fn add_element_unique_hashes(&self, _filter: &mut BloomFilter) -> bool {
+        // Should not be relevant in the context of checking past elements in invalidation.
+        false
+    }
+}
diff --git a/servo/components/style/invalidation/element/invalidation_map.rs b/servo/components/style/invalidation/element/invalidation_map.rs
new file mode 100644
index 0000000000..cb03862740
--- /dev/null
+++ b/servo/components/style/invalidation/element/invalidation_map.rs
@@ -0,0 +1,1425 @@
+/* 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/. */
+
+//! Code for invalidations due to state or attribute changes.
+
+use crate::context::QuirksMode;
+use crate::selector_map::{
+    MaybeCaseInsensitiveHashMap, PrecomputedHashMap, SelectorMap, SelectorMapEntry,
+};
+use crate::selector_parser::{NonTSPseudoClass, SelectorImpl};
+use crate::AllocErr;
+use crate::{Atom, LocalName, Namespace, ShrinkIfNeeded};
+use dom::{DocumentState, ElementState};
+use selectors::attr::NamespaceConstraint;
+use selectors::parser::{
+    Combinator, Component, RelativeSelector, RelativeSelectorCombinatorCount,
+    RelativeSelectorMatchHint,
+};
+use selectors::parser::{Selector, SelectorIter};
+use selectors::visitor::{SelectorListKind, SelectorVisitor};
+use servo_arc::Arc;
+use smallvec::SmallVec;
+
+/// Mapping between (partial) CompoundSelectors (and the combinator to their
+/// right) and the states and attributes they depend on.
+///
+/// In general, for all selectors in all applicable stylesheets of the form:
+///
+/// |a _ b _ c _ d _ e|
+///
+/// Where:
+///   * |b| and |d| are simple selectors that depend on state (like :hover) or
+///     attributes (like [attr...], .foo, or #foo).
+///   * |a|, |c|, and |e| are arbitrary simple selectors that do not depend on
+///     state or attributes.
+///
+/// We generate a Dependency for both |a _ b:X _| and |a _ b:X _ c _ d:Y _|,
+/// even though those selectors may not appear on their own in any stylesheet.
+/// This allows us to quickly scan through the dependency sites of all style
+/// rules and determine the maximum effect that a given state or attribute
+/// change may have on the style of elements in the document.
+#[derive(Clone, Debug, MallocSizeOf)]
+pub struct Dependency {
+    /// The dependency selector.
+    #[ignore_malloc_size_of = "CssRules have primary refs, we measure there"]
+    pub selector: Selector<SelectorImpl>,
+
+    /// The offset into the selector that we should match on.
+    pub selector_offset: usize,
+
+    /// The parent dependency for an ancestor selector. For example, consider
+    /// the following:
+    ///
+    ///     .foo .bar:where(.baz span) .qux
+    ///         ^               ^     ^
+    ///         A               B     C
+    ///
+    ///  We'd generate:
+    ///
+    ///    * One dependency for .qux (offset: 0, parent: None)
+    ///    * One dependency for .baz pointing to B with parent being a
+    ///      dependency pointing to C.
+    ///    * One dependency from .bar pointing to C (parent: None)
+    ///    * One dependency from .foo pointing to A (parent: None)
+    ///
+    #[ignore_malloc_size_of = "Arc"]
+    pub parent: Option<Arc<Dependency>>,
+
+    /// What kind of relative selector invalidation this generates.
+    /// None if this dependency is not within a relative selector.
+    relative_kind: Option<RelativeDependencyInvalidationKind>,
+}
+
+impl SelectorMapEntry for Dependency {
+    fn selector(&self) -> SelectorIter<SelectorImpl> {
+        self.selector.iter_from(self.selector_offset)
+    }
+}
+
+/// The kind of elements down the tree this dependency may affect.
+#[derive(Clone, Copy, Debug, Eq, Hash, PartialEq, MallocSizeOf)]
+pub enum NormalDependencyInvalidationKind {
+    /// This dependency may affect the element that changed itself.
+    Element,
+    /// This dependency affects the style of the element itself, and also the
+    /// style of its descendants.
+    ///
+    /// TODO(emilio): Each time this feels more of a hack for eager pseudos...
+    ElementAndDescendants,
+    /// This dependency may affect descendants down the tree.
+    Descendants,
+    /// This dependency may affect siblings to the right of the element that
+    /// changed.
+    Siblings,
+    /// This dependency may affect slotted elements of the element that changed.
+    SlottedElements,
+    /// This dependency may affect parts of the element that changed.
+    Parts,
+}
+
+/// The kind of elements up the tree this relative selector dependency may
+/// affect. Because this travels upwards, it's not viable for parallel subtree
+/// traversal, and is handled separately.
+#[derive(Clone, Copy, Debug, Eq, Hash, PartialEq, MallocSizeOf)]
+pub enum RelativeDependencyInvalidationKind {
+    /// This dependency may affect relative selector anchors for ancestors.
+    Ancestors,
+    /// This dependency may affect a relative selector anchor for the parent.
+    Parent,
+    /// This dependency may affect a relative selector anchor for the previous sibling.
+    PrevSibling,
+    /// This dependency may affect relative selector anchors for ancestors' previous siblings.
+    AncestorPrevSibling,
+    /// This dependency may affect relative selector anchors for earlier siblings.
+    EarlierSibling,
+    /// This dependency may affect relative selector anchors for ancestors' earlier siblings.
+    AncestorEarlierSibling,
+}
+
+/// Invalidation kind merging normal and relative dependencies.
+#[derive(Clone, Copy, Debug, Eq, Hash, PartialEq, MallocSizeOf)]
+pub enum DependencyInvalidationKind {
+    /// This dependency is a normal dependency.
+    Normal(NormalDependencyInvalidationKind),
+    /// This dependency is a relative dependency.
+    Relative(RelativeDependencyInvalidationKind),
+}
+
+impl Dependency {
+    /// Creates a dummy dependency to invalidate the whole selector.
+    ///
+    /// This is necessary because document state invalidation wants to
+    /// invalidate all elements in the document.
+    ///
+    /// The offset is such as that Invalidation::new(self) returns a zero
+    /// offset. That is, it points to a virtual "combinator" outside of the
+    /// selector, so calling combinator() on such a dependency will panic.
+    pub fn for_full_selector_invalidation(selector: Selector<SelectorImpl>) -> Self {
+        Self {
+            selector_offset: selector.len() + 1,
+            selector,
+            parent: None,
+            relative_kind: None,
+        }
+    }
+
+    /// Returns the combinator to the right of the partial selector this
+    /// dependency represents.
+    ///
+    /// TODO(emilio): Consider storing inline if it helps cache locality?
+    fn combinator(&self) -> Option<Combinator> {
+        if self.selector_offset == 0 {
+            return None;
+        }
+
+        Some(
+            self.selector
+                .combinator_at_match_order(self.selector_offset - 1),
+        )
+    }
+
+    /// The kind of normal invalidation that this would generate. The dependency
+    /// in question must be a normal dependency.
+    pub fn normal_invalidation_kind(&self) -> NormalDependencyInvalidationKind {
+        debug_assert!(
+            self.relative_kind.is_none(),
+            "Querying normal invalidation kind on relative dependency."
+        );
+        match self.combinator() {
+            None => NormalDependencyInvalidationKind::Element,
+            Some(Combinator::Child) | Some(Combinator::Descendant) => {
+                NormalDependencyInvalidationKind::Descendants
+            },
+            Some(Combinator::LaterSibling) | Some(Combinator::NextSibling) => {
+                NormalDependencyInvalidationKind::Siblings
+            },
+            // TODO(emilio): We could look at the selector itself to see if it's
+            // an eager pseudo, and return only Descendants here if not.
+            Some(Combinator::PseudoElement) => {
+                NormalDependencyInvalidationKind::ElementAndDescendants
+            },
+            Some(Combinator::SlotAssignment) => NormalDependencyInvalidationKind::SlottedElements,
+            Some(Combinator::Part) => NormalDependencyInvalidationKind::Parts,
+        }
+    }
+
+    /// The kind of invalidation that this would generate.
+    pub fn invalidation_kind(&self) -> DependencyInvalidationKind {
+        if let Some(kind) = self.relative_kind {
+            return DependencyInvalidationKind::Relative(kind);
+        }
+        DependencyInvalidationKind::Normal(self.normal_invalidation_kind())
+    }
+
+    /// Is the combinator to the right of this dependency's compound selector
+    /// the next sibling combinator? This matters for insertion/removal in between
+    /// two elements connected through next sibling, e.g. `.foo:has(> .a + .b)`
+    /// where an element gets inserted between `.a` and `.b`.
+    pub fn right_combinator_is_next_sibling(&self) -> bool {
+        if self.selector_offset == 0 {
+            return false;
+        }
+        matches!(
+            self.selector
+                .combinator_at_match_order(self.selector_offset - 1),
+            Combinator::NextSibling
+        )
+    }
+
+    /// Is this dependency's compound selector a single compound in `:has`
+    /// with the next sibling relative combinator i.e. `:has(> .foo)`?
+    /// This matters for insertion between an anchor and an element
+    /// connected through next sibling, e.g. `.a:has(> .b)`.
+    pub fn dependency_is_relative_with_single_next_sibling(&self) -> bool {
+        match self.invalidation_kind() {
+            DependencyInvalidationKind::Normal(_) => false,
+            DependencyInvalidationKind::Relative(kind) => {
+                kind == RelativeDependencyInvalidationKind::PrevSibling
+            },
+        }
+    }
+}
+
+/// The same, but for state selectors, which can track more exactly what state
+/// do they track.
+#[derive(Clone, Debug, MallocSizeOf)]
+pub struct StateDependency {
+    /// The other dependency fields.
+    pub dep: Dependency,
+    /// The state this dependency is affected by.
+    pub state: ElementState,
+}
+
+impl SelectorMapEntry for StateDependency {
+    fn selector(&self) -> SelectorIter<SelectorImpl> {
+        self.dep.selector()
+    }
+}
+
+/// The same, but for document state selectors.
+#[derive(Clone, Debug, MallocSizeOf)]
+pub struct DocumentStateDependency {
+    /// We track `Dependency` even though we don't need to track an offset,
+    /// since when it changes it changes for the whole document anyway.
+    #[cfg_attr(
+        feature = "gecko",
+        ignore_malloc_size_of = "CssRules have primary refs, we measure there"
+    )]
+    #[cfg_attr(feature = "servo", ignore_malloc_size_of = "Arc")]
+    pub dependency: Dependency,
+    /// The state this dependency is affected by.
+    pub state: DocumentState,
+}
+
+/// Dependency mapping for classes or IDs.
+pub type IdOrClassDependencyMap = MaybeCaseInsensitiveHashMap<Atom, SmallVec<[Dependency; 1]>>;
+/// Dependency mapping for non-tree-strctural pseudo-class states.
+pub type StateDependencyMap = SelectorMap<StateDependency>;
+/// Dependency mapping for local names.
+pub type LocalNameDependencyMap = PrecomputedHashMap<LocalName, SmallVec<[Dependency; 1]>>;
+
+/// A map where we store invalidations.
+///
+/// This is slightly different to a SelectorMap, in the sense of that the same
+/// selector may appear multiple times.
+///
+/// In particular, we want to lookup as few things as possible to get the fewer
+/// selectors the better, so this looks up by id, class, or looks at the list of
+/// state/other attribute affecting selectors.
+#[derive(Clone, Debug, MallocSizeOf)]
+pub struct InvalidationMap {
+    /// A map from a given class name to all the selectors with that class
+    /// selector.
+    pub class_to_selector: IdOrClassDependencyMap,
+    /// A map from a given id to all the selectors with that ID in the
+    /// stylesheets currently applying to the document.
+    pub id_to_selector: IdOrClassDependencyMap,
+    /// A map of all the state dependencies.
+    pub state_affecting_selectors: StateDependencyMap,
+    /// A list of document state dependencies in the rules we represent.
+    pub document_state_selectors: Vec<DocumentStateDependency>,
+    /// A map of other attribute affecting selectors.
+    pub other_attribute_affecting_selectors: LocalNameDependencyMap,
+}
+
+/// Tree-structural pseudoclasses that we care about for (Relative selector) invalidation.
+/// Specifically, we need to store information on ones that don't generate the inner selector.
+#[derive(Clone, Copy, Debug, MallocSizeOf)]
+pub struct TSStateForInvalidation(u8);
+
+bitflags! {
+    impl TSStateForInvalidation : u8 {
+        /// :empty
+        const EMPTY = 1 << 0;
+        /// :nth etc, without of.
+        const NTH = 1 << 1;
+        /// "Simple" edge child selectors, like :first-child, :last-child, etc.
+        /// Excludes :*-of-type.
+        const NTH_EDGE = 1 << 2;
+    }
+}
+
+/// Dependency for tree-structural pseudo-classes.
+#[derive(Clone, Debug, MallocSizeOf)]
+pub struct TSStateDependency {
+    /// The other dependency fields.
+    pub dep: Dependency,
+    /// The state this dependency is affected by.
+    pub state: TSStateForInvalidation,
+}
+
+impl SelectorMapEntry for TSStateDependency {
+    fn selector(&self) -> SelectorIter<SelectorImpl> {
+        self.dep.selector()
+    }
+}
+
+/// Dependency mapping for tree-structural pseudo-class states.
+pub type TSStateDependencyMap = SelectorMap<TSStateDependency>;
+/// Dependency mapping for * selectors.
+pub type AnyDependencyMap = SmallVec<[Dependency; 1]>;
+
+/// A map to store all relative selector invalidations.
+/// This keeps a lot more data than the usual map, because any change can generate
+/// upward traversals that need to be handled separately.
+#[derive(Clone, Debug, MallocSizeOf)]
+pub struct RelativeSelectorInvalidationMap {
+    /// Portion common to the normal invalidation map, except that this is for relative selectors and their inner selectors.
+    pub map: InvalidationMap,
+    /// A map for a given tree-structural pseudo-class to all the relative selector dependencies with that type.
+    pub ts_state_to_selector: TSStateDependencyMap,
+    /// A map from a given type name to all the relative selector dependencies with that type.
+    pub type_to_selector: LocalNameDependencyMap,
+    /// All relative selector dependencies that specify `*`.
+    pub any_to_selector: AnyDependencyMap,
+    /// Flag indicating if any relative selector is used.
+    pub used: bool,
+    /// Flag indicating if invalidating a relative selector requires ancestor traversal.
+    pub needs_ancestors_traversal: bool,
+}
+
+impl RelativeSelectorInvalidationMap {
+    /// Creates an empty `InvalidationMap`.
+    pub fn new() -> Self {
+        Self {
+            map: InvalidationMap::new(),
+            ts_state_to_selector: TSStateDependencyMap::default(),
+            type_to_selector: LocalNameDependencyMap::default(),
+            any_to_selector: SmallVec::default(),
+            used: false,
+            needs_ancestors_traversal: false,
+        }
+    }
+
+    /// Returns the number of dependencies stored in the invalidation map.
+    pub fn len(&self) -> usize {
+        self.map.len()
+    }
+
+    /// Clears this map, leaving it empty.
+    pub fn clear(&mut self) {
+        self.map.clear();
+        self.ts_state_to_selector.clear();
+        self.type_to_selector.clear();
+        self.any_to_selector.clear();
+    }
+
+    /// Shrink the capacity of hash maps if needed.
+    pub fn shrink_if_needed(&mut self) {
+        self.map.shrink_if_needed();
+        self.ts_state_to_selector.shrink_if_needed();
+        self.type_to_selector.shrink_if_needed();
+    }
+}
+
+impl InvalidationMap {
+    /// Creates an empty `InvalidationMap`.
+    pub fn new() -> Self {
+        Self {
+            class_to_selector: IdOrClassDependencyMap::new(),
+            id_to_selector: IdOrClassDependencyMap::new(),
+            state_affecting_selectors: StateDependencyMap::new(),
+            document_state_selectors: Vec::new(),
+            other_attribute_affecting_selectors: LocalNameDependencyMap::default(),
+        }
+    }
+
+    /// Returns the number of dependencies stored in the invalidation map.
+    pub fn len(&self) -> usize {
+        self.state_affecting_selectors.len() +
+            self.document_state_selectors.len() +
+            self.other_attribute_affecting_selectors
+                .iter()
+                .fold(0, |accum, (_, ref v)| accum + v.len()) +
+            self.id_to_selector
+                .iter()
+                .fold(0, |accum, (_, ref v)| accum + v.len()) +
+            self.class_to_selector
+                .iter()
+                .fold(0, |accum, (_, ref v)| accum + v.len())
+    }
+
+    /// Clears this map, leaving it empty.
+    pub fn clear(&mut self) {
+        self.class_to_selector.clear();
+        self.id_to_selector.clear();
+        self.state_affecting_selectors.clear();
+        self.document_state_selectors.clear();
+        self.other_attribute_affecting_selectors.clear();
+    }
+
+    /// Shrink the capacity of hash maps if needed.
+    pub fn shrink_if_needed(&mut self) {
+        self.class_to_selector.shrink_if_needed();
+        self.id_to_selector.shrink_if_needed();
+        self.state_affecting_selectors.shrink_if_needed();
+        self.other_attribute_affecting_selectors.shrink_if_needed();
+    }
+}
+
+/// Adds a selector to the given `InvalidationMap`. Returns Err(..) to signify OOM.
+pub fn note_selector_for_invalidation(
+    selector: &Selector<SelectorImpl>,
+    quirks_mode: QuirksMode,
+    map: &mut InvalidationMap,
+    relative_selector_invalidation_map: &mut RelativeSelectorInvalidationMap,
+) -> Result<(), AllocErr> {
+    debug!("note_selector_for_invalidation({:?})", selector);
+
+    let mut document_state = DocumentState::empty();
+    {
+        let mut parent_stack = ParentSelectors::new();
+        let mut alloc_error = None;
+        let mut collector = SelectorDependencyCollector {
+            map,
+            relative_selector_invalidation_map,
+            document_state: &mut document_state,
+            selector,
+            parent_selectors: &mut parent_stack,
+            quirks_mode,
+            compound_state: PerCompoundState::new(0),
+            alloc_error: &mut alloc_error,
+        };
+
+        let visit_result = collector.visit_whole_selector();
+        debug_assert_eq!(!visit_result, alloc_error.is_some());
+        if let Some(alloc_error) = alloc_error {
+            return Err(alloc_error);
+        }
+    }
+
+    if !document_state.is_empty() {
+        let dep = DocumentStateDependency {
+            state: document_state,
+            dependency: Dependency::for_full_selector_invalidation(selector.clone()),
+        };
+        map.document_state_selectors.try_reserve(1)?;
+        map.document_state_selectors.push(dep);
+    }
+    Ok(())
+}
+struct PerCompoundState {
+    /// The offset at which our compound starts.
+    offset: usize,
+
+    /// The state this compound selector is affected by.
+    element_state: ElementState,
+}
+
+impl PerCompoundState {
+    fn new(offset: usize) -> Self {
+        Self {
+            offset,
+            element_state: ElementState::empty(),
+        }
+    }
+}
+
+struct ParentDependencyEntry {
+    selector: Selector<SelectorImpl>,
+    offset: usize,
+    cached_dependency: Option<Arc<Dependency>>,
+}
+
+trait Collector {
+    fn dependency(&mut self) -> Dependency;
+    fn id_map(&mut self) -> &mut IdOrClassDependencyMap;
+    fn class_map(&mut self) -> &mut IdOrClassDependencyMap;
+    fn state_map(&mut self) -> &mut StateDependencyMap;
+    fn attribute_map(&mut self) -> &mut LocalNameDependencyMap;
+    fn update_states(&mut self, element_state: ElementState, document_state: DocumentState);
+
+    // In normal invalidations, type-based dependencies don't need to be explicitly tracked;
+    // elements don't change their types, and mutations cause invalidations to go descendant
+    // (Where they are about to be styled anyway), and/or later-sibling direction (Where they
+    // siblings after inserted/removed elements get restyled anyway).
+    // However, for relative selectors, a DOM mutation can affect and arbitrary ancestor and/or
+    // earlier siblings, so we need to keep track of them.
+    fn type_map(&mut self) -> &mut LocalNameDependencyMap {
+        unreachable!();
+    }
+
+    // Tree-structural pseudo-selectors generally invalidates in a well-defined way, which are
+    // handled by RestyleManager. However, for relative selectors, as with type invalidations,
+    // the direction of invalidation becomes arbitrary, so we need to keep track of them.
+    fn ts_state_map(&mut self) -> &mut TSStateDependencyMap {
+        unreachable!();
+    }
+
+    // Same story as type invalidation maps.
+    fn any_vec(&mut self) -> &mut AnyDependencyMap {
+        unreachable!();
+    }
+}
+
+fn on_attribute<C: Collector>(
+    local_name: &LocalName,
+    local_name_lower: &LocalName,
+    collector: &mut C,
+) -> Result<(), AllocErr> {
+    add_attr_dependency(local_name.clone(), collector)?;
+
+    if local_name != local_name_lower {
+        add_attr_dependency(local_name_lower.clone(), collector)?;
+    }
+    Ok(())
+}
+
+fn on_id_or_class<C: Collector>(
+    s: &Component<SelectorImpl>,
+    quirks_mode: QuirksMode,
+    collector: &mut C,
+) -> Result<(), AllocErr> {
+    let dependency = collector.dependency();
+    let (atom, map) = match *s {
+        Component::ID(ref atom) => (atom, collector.id_map()),
+        Component::Class(ref atom) => (atom, collector.class_map()),
+        _ => unreachable!(),
+    };
+    let entry = map.try_entry(atom.0.clone(), quirks_mode)?;
+    let vec = entry.or_insert_with(SmallVec::new);
+    vec.try_reserve(1)?;
+    vec.push(dependency);
+    Ok(())
+}
+
+fn add_attr_dependency<C: Collector>(name: LocalName, collector: &mut C) -> Result<(), AllocErr> {
+    let dependency = collector.dependency();
+    let map = collector.attribute_map();
+    add_local_name(name, dependency, map)
+}
+
+fn add_local_name(
+    name: LocalName,
+    dependency: Dependency,
+    map: &mut LocalNameDependencyMap,
+) -> Result<(), AllocErr> {
+    map.try_reserve(1)?;
+    let vec = map.entry(name).or_default();
+    vec.try_reserve(1)?;
+    vec.push(dependency);
+    Ok(())
+}
+
+fn on_pseudo_class<C: Collector>(pc: &NonTSPseudoClass, collector: &mut C) -> Result<(), AllocErr> {
+    collector.update_states(pc.state_flag(), pc.document_state_flag());
+
+    let attr_name = match *pc {
+        #[cfg(feature = "gecko")]
+        NonTSPseudoClass::MozTableBorderNonzero => local_name!("border"),
+        #[cfg(feature = "gecko")]
+        NonTSPseudoClass::MozSelectListBox => {
+            // This depends on two attributes.
+            add_attr_dependency(local_name!("multiple"), collector)?;
+            return add_attr_dependency(local_name!("size"), collector);
+        },
+        NonTSPseudoClass::Lang(..) => local_name!("lang"),
+        _ => return Ok(()),
+    };
+
+    add_attr_dependency(attr_name, collector)
+}
+
+fn add_pseudo_class_dependency<C: Collector>(
+    element_state: ElementState,
+    quirks_mode: QuirksMode,
+    collector: &mut C,
+) -> Result<(), AllocErr> {
+    if element_state.is_empty() {
+        return Ok(());
+    }
+    let dependency = collector.dependency();
+    collector.state_map().insert(
+        StateDependency {
+            dep: dependency,
+            state: element_state,
+        },
+        quirks_mode,
+    )
+}
+
+type ParentSelectors = SmallVec<[ParentDependencyEntry; 5]>;
+
+/// A struct that collects invalidations for a given compound selector.
+struct SelectorDependencyCollector<'a> {
+    map: &'a mut InvalidationMap,
+    relative_selector_invalidation_map: &'a mut RelativeSelectorInvalidationMap,
+
+    /// The document this _complex_ selector is affected by.
+    ///
+    /// We don't need to track state per compound selector, since it's global
+    /// state and it changes for everything.
+    document_state: &'a mut DocumentState,
+
+    /// The current selector and offset we're iterating.
+    selector: &'a Selector<SelectorImpl>,
+
+    /// The stack of parent selectors that we have, and at which offset of the
+    /// sequence.
+    ///
+    /// This starts empty. It grows when we find nested :is and :where selector
+    /// lists. The dependency field is cached and reference counted.
+    parent_selectors: &'a mut ParentSelectors,
+
+    /// The quirks mode of the document where we're inserting dependencies.
+    quirks_mode: QuirksMode,
+
+    /// State relevant to a given compound selector.
+    compound_state: PerCompoundState,
+
+    /// The allocation error, if we OOM.
+    alloc_error: &'a mut Option<AllocErr>,
+}
+
+fn parent_dependency(
+    parent_selectors: &mut ParentSelectors,
+    outer_parent: Option<&Arc<Dependency>>,
+) -> Option<Arc<Dependency>> {
+    if parent_selectors.is_empty() {
+        return outer_parent.cloned();
+    }
+
+    fn dependencies_from(
+        entries: &mut [ParentDependencyEntry],
+        outer_parent: &Option<&Arc<Dependency>>,
+    ) -> Option<Arc<Dependency>> {
+        if entries.is_empty() {
+            return None;
+        }
+
+        let last_index = entries.len() - 1;
+        let (previous, last) = entries.split_at_mut(last_index);
+        let last = &mut last[0];
+        let selector = &last.selector;
+        let selector_offset = last.offset;
+        Some(
+            last.cached_dependency
+                .get_or_insert_with(|| {
+                    Arc::new(Dependency {
+                        selector: selector.clone(),
+                        selector_offset,
+                        parent: dependencies_from(previous, outer_parent),
+                        relative_kind: None,
+                    })
+                })
+                .clone(),
+        )
+    }
+
+    dependencies_from(parent_selectors, &outer_parent)
+}
+
+impl<'a> Collector for SelectorDependencyCollector<'a> {
+    fn dependency(&mut self) -> Dependency {
+        let parent = parent_dependency(self.parent_selectors, None);
+        Dependency {
+            selector: self.selector.clone(),
+            selector_offset: self.compound_state.offset,
+            parent,
+            relative_kind: None,
+        }
+    }
+
+    fn id_map(&mut self) -> &mut IdOrClassDependencyMap {
+        &mut self.map.id_to_selector
+    }
+
+    fn class_map(&mut self) -> &mut IdOrClassDependencyMap {
+        &mut self.map.class_to_selector
+    }
+
+    fn state_map(&mut self) -> &mut StateDependencyMap {
+        &mut self.map.state_affecting_selectors
+    }
+
+    fn attribute_map(&mut self) -> &mut LocalNameDependencyMap {
+        &mut self.map.other_attribute_affecting_selectors
+    }
+
+    fn update_states(&mut self, element_state: ElementState, document_state: DocumentState) {
+        self.compound_state.element_state |= element_state;
+        *self.document_state |= document_state;
+    }
+}
+
+impl<'a> SelectorDependencyCollector<'a> {
+    fn visit_whole_selector(&mut self) -> bool {
+        let iter = self.selector.iter();
+        self.visit_whole_selector_from(iter, 0)
+    }
+
+    fn visit_whole_selector_from(
+        &mut self,
+        mut iter: SelectorIter<SelectorImpl>,
+        mut index: usize,
+    ) -> bool {
+        loop {
+            // Reset the compound state.
+            self.compound_state = PerCompoundState::new(index);
+
+            // Visit all the simple selectors in this sequence.
+            for ss in &mut iter {
+                if !ss.visit(self) {
+                    return false;
+                }
+                index += 1; // Account for the simple selector.
+            }
+
+            if let Err(err) = add_pseudo_class_dependency(
+                self.compound_state.element_state,
+                self.quirks_mode,
+                self,
+            ) {
+                *self.alloc_error = Some(err);
+                return false;
+            }
+
+            let combinator = iter.next_sequence();
+            if combinator.is_none() {
+                return true;
+            }
+            index += 1; // account for the combinator
+        }
+    }
+}
+
+impl<'a> SelectorVisitor for SelectorDependencyCollector<'a> {
+    type Impl = SelectorImpl;
+
+    fn visit_selector_list(
+        &mut self,
+        _list_kind: SelectorListKind,
+        list: &[Selector<SelectorImpl>],
+    ) -> bool {
+        for selector in list {
+            // Here we cheat a bit: We can visit the rightmost compound with
+            // the "outer" visitor, and it'd be fine. This reduces the amount of
+            // state and attribute invalidations, and we need to check the outer
+            // selector to the left anyway to avoid over-invalidation, so it
+            // avoids matching it twice uselessly.
+            let mut iter = selector.iter();
+            let mut index = 0;
+
+            for ss in &mut iter {
+                if !ss.visit(self) {
+                    return false;
+                }
+                index += 1;
+            }
+
+            let combinator = iter.next_sequence();
+            if combinator.is_none() {
+                continue;
+            }
+
+            index += 1; // account for the combinator.
+
+            self.parent_selectors.push(ParentDependencyEntry {
+                selector: self.selector.clone(),
+                offset: self.compound_state.offset,
+                cached_dependency: None,
+            });
+            let mut nested = SelectorDependencyCollector {
+                map: &mut *self.map,
+                relative_selector_invalidation_map: &mut *self.relative_selector_invalidation_map,
+                document_state: &mut *self.document_state,
+                selector,
+                parent_selectors: &mut *self.parent_selectors,
+                quirks_mode: self.quirks_mode,
+                compound_state: PerCompoundState::new(index),
+                alloc_error: &mut *self.alloc_error,
+            };
+            if !nested.visit_whole_selector_from(iter, index) {
+                return false;
+            }
+            self.parent_selectors.pop();
+        }
+        true
+    }
+
+    fn visit_relative_selector_list(
+        &mut self,
+        list: &[selectors::parser::RelativeSelector<Self::Impl>],
+    ) -> bool {
+        self.relative_selector_invalidation_map.used = true;
+        for relative_selector in list {
+            // We can't cheat here like we do with other selector lists - the rightmost
+            // compound of a relative selector is not the subject of the invalidation.
+            self.parent_selectors.push(ParentDependencyEntry {
+                selector: self.selector.clone(),
+                offset: self.compound_state.offset,
+                cached_dependency: None,
+            });
+            let mut nested = RelativeSelectorDependencyCollector {
+                map: &mut *self.relative_selector_invalidation_map,
+                document_state: &mut *self.document_state,
+                selector: &relative_selector,
+                combinator_count: RelativeSelectorCombinatorCount::new(relative_selector),
+                parent_selectors: &mut *self.parent_selectors,
+                quirks_mode: self.quirks_mode,
+                compound_state: RelativeSelectorPerCompoundState::new(0),
+                alloc_error: &mut *self.alloc_error,
+            };
+            if !nested.visit_whole_selector() {
+                return false;
+            }
+            self.parent_selectors.pop();
+        }
+        true
+    }
+
+    fn visit_simple_selector(&mut self, s: &Component<SelectorImpl>) -> bool {
+        match *s {
+            Component::ID(..) | Component::Class(..) => {
+                if let Err(err) = on_id_or_class(s, self.quirks_mode, self) {
+                    *self.alloc_error = Some(err.into());
+                    return false;
+                }
+                true
+            },
+            Component::NonTSPseudoClass(ref pc) => {
+                if let Err(err) = on_pseudo_class(pc, self) {
+                    *self.alloc_error = Some(err.into());
+                    return false;
+                }
+                true
+            },
+            _ => true,
+        }
+    }
+
+    fn visit_attribute_selector(
+        &mut self,
+        _: &NamespaceConstraint<&Namespace>,
+        local_name: &LocalName,
+        local_name_lower: &LocalName,
+    ) -> bool {
+        if let Err(err) = on_attribute(local_name, local_name_lower, self) {
+            *self.alloc_error = Some(err);
+            return false;
+        }
+        true
+    }
+}
+
+struct RelativeSelectorPerCompoundState {
+    state: PerCompoundState,
+    ts_state: TSStateForInvalidation,
+    added_entry: bool,
+}
+
+impl RelativeSelectorPerCompoundState {
+    fn new(offset: usize) -> Self {
+        Self {
+            state: PerCompoundState::new(offset),
+            ts_state: TSStateForInvalidation::empty(),
+            added_entry: false,
+        }
+    }
+}
+
+/// A struct that collects invalidations for a given compound selector.
+struct RelativeSelectorDependencyCollector<'a> {
+    map: &'a mut RelativeSelectorInvalidationMap,
+
+    /// The document this _complex_ selector is affected by.
+    ///
+    /// We don't need to track state per compound selector, since it's global
+    /// state and it changes for everything.
+    document_state: &'a mut DocumentState,
+
+    /// The current inner relative selector and offset we're iterating.
+    selector: &'a RelativeSelector<SelectorImpl>,
+    /// Running combinator for this inner relative selector.
+    combinator_count: RelativeSelectorCombinatorCount,
+
+    /// The stack of parent selectors that we have, and at which offset of the
+    /// sequence.
+    ///
+    /// This starts empty. It grows when we find nested :is and :where selector
+    /// lists. The dependency field is cached and reference counted.
+    parent_selectors: &'a mut ParentSelectors,
+
+    /// The quirks mode of the document where we're inserting dependencies.
+    quirks_mode: QuirksMode,
+
+    /// State relevant to a given compound selector.
+    compound_state: RelativeSelectorPerCompoundState,
+
+    /// The allocation error, if we OOM.
+    alloc_error: &'a mut Option<AllocErr>,
+}
+
+fn add_non_unique_info<C: Collector>(
+    selector: &Selector<SelectorImpl>,
+    offset: usize,
+    collector: &mut C,
+) -> Result<(), AllocErr> {
+    // Go through this compound again.
+    for ss in selector.iter_from(offset) {
+        match ss {
+            Component::LocalName(ref name) => {
+                let dependency = collector.dependency();
+                add_local_name(name.name.clone(), dependency, &mut collector.type_map())?;
+                if name.name != name.lower_name {
+                    let dependency = collector.dependency();
+                    add_local_name(
+                        name.lower_name.clone(),
+                        dependency,
+                        &mut collector.type_map(),
+                    )?;
+                }
+                return Ok(());
+            },
+            _ => (),
+        };
+    }
+    // Ouch. Add one for *.
+    collector.any_vec().try_reserve(1)?;
+    let dependency = collector.dependency();
+    collector.any_vec().push(dependency);
+    Ok(())
+}
+
+fn add_ts_pseudo_class_dependency<C: Collector>(
+    state: TSStateForInvalidation,
+    quirks_mode: QuirksMode,
+    collector: &mut C,
+) -> Result<(), AllocErr> {
+    if state.is_empty() {
+        return Ok(());
+    }
+    let dependency = collector.dependency();
+    collector.ts_state_map().insert(
+        TSStateDependency {
+            dep: dependency,
+            state,
+        },
+        quirks_mode,
+    )
+}
+
+impl<'a> RelativeSelectorDependencyCollector<'a> {
+    fn visit_whole_selector(&mut self) -> bool {
+        let mut iter = self.selector.selector.iter_skip_relative_selector_anchor();
+        let mut index = 0;
+
+        self.map.needs_ancestors_traversal |= match self.selector.match_hint {
+            RelativeSelectorMatchHint::InNextSiblingSubtree |
+            RelativeSelectorMatchHint::InSiblingSubtree |
+            RelativeSelectorMatchHint::InSubtree => true,
+            _ => false,
+        };
+        loop {
+            // Reset the compound state.
+            self.compound_state = RelativeSelectorPerCompoundState::new(index);
+
+            // Visit all the simple selectors in this sequence.
+            for ss in &mut iter {
+                if !ss.visit(self) {
+                    return false;
+                }
+                index += 1; // Account for the simple selector.
+            }
+
+            if let Err(err) = add_pseudo_class_dependency(
+                self.compound_state.state.element_state,
+                self.quirks_mode,
+                self,
+            ) {
+                *self.alloc_error = Some(err);
+                return false;
+            }
+            if let Err(err) =
+                add_ts_pseudo_class_dependency(self.compound_state.ts_state, self.quirks_mode, self)
+            {
+                *self.alloc_error = Some(err);
+                return false;
+            }
+
+            if !self.compound_state.added_entry {
+                // Not great - we didn't add any uniquely identifiable information.
+                if let Err(err) = add_non_unique_info(
+                    &self.selector.selector,
+                    self.compound_state.state.offset,
+                    self,
+                ) {
+                    *self.alloc_error = Some(err);
+                    return false;
+                }
+            }
+
+            let combinator = iter.next_sequence();
+            if let Some(c) = combinator {
+                match c {
+                    Combinator::Child | Combinator::Descendant => {
+                        self.combinator_count.child_or_descendants -= 1
+                    },
+                    Combinator::NextSibling | Combinator::LaterSibling => {
+                        self.combinator_count.adjacent_or_next_siblings -= 1
+                    },
+                    Combinator::Part | Combinator::PseudoElement | Combinator::SlotAssignment => (),
+                }
+            } else {
+                return true;
+            }
+            index += 1; // account for the combinator
+        }
+    }
+}
+
+impl<'a> Collector for RelativeSelectorDependencyCollector<'a> {
+    fn dependency(&mut self) -> Dependency {
+        let parent = parent_dependency(self.parent_selectors, None);
+        Dependency {
+            selector: self.selector.selector.clone(),
+            selector_offset: self.compound_state.state.offset,
+            relative_kind: Some(match self.combinator_count.get_match_hint() {
+                RelativeSelectorMatchHint::InChild => RelativeDependencyInvalidationKind::Parent,
+                RelativeSelectorMatchHint::InSubtree => {
+                    RelativeDependencyInvalidationKind::Ancestors
+                },
+                RelativeSelectorMatchHint::InNextSibling => {
+                    RelativeDependencyInvalidationKind::PrevSibling
+                },
+                RelativeSelectorMatchHint::InSibling => {
+                    RelativeDependencyInvalidationKind::EarlierSibling
+                },
+                RelativeSelectorMatchHint::InNextSiblingSubtree => {
+                    RelativeDependencyInvalidationKind::AncestorPrevSibling
+                },
+                RelativeSelectorMatchHint::InSiblingSubtree => {
+                    RelativeDependencyInvalidationKind::AncestorEarlierSibling
+                },
+            }),
+            parent,
+        }
+    }
+
+    fn id_map(&mut self) -> &mut IdOrClassDependencyMap {
+        &mut self.map.map.id_to_selector
+    }
+
+    fn class_map(&mut self) -> &mut IdOrClassDependencyMap {
+        &mut self.map.map.class_to_selector
+    }
+
+    fn state_map(&mut self) -> &mut StateDependencyMap {
+        &mut self.map.map.state_affecting_selectors
+    }
+
+    fn attribute_map(&mut self) -> &mut LocalNameDependencyMap {
+        &mut self.map.map.other_attribute_affecting_selectors
+    }
+
+    fn update_states(&mut self, element_state: ElementState, document_state: DocumentState) {
+        self.compound_state.state.element_state |= element_state;
+        *self.document_state |= document_state;
+    }
+
+    fn type_map(&mut self) -> &mut LocalNameDependencyMap {
+        &mut self.map.type_to_selector
+    }
+
+    fn ts_state_map(&mut self) -> &mut TSStateDependencyMap {
+        &mut self.map.ts_state_to_selector
+    }
+
+    fn any_vec(&mut self) -> &mut AnyDependencyMap {
+        &mut self.map.any_to_selector
+    }
+}
+
+impl<'a> SelectorVisitor for RelativeSelectorDependencyCollector<'a> {
+    type Impl = SelectorImpl;
+
+    fn visit_selector_list(
+        &mut self,
+        _list_kind: SelectorListKind,
+        list: &[Selector<SelectorImpl>],
+    ) -> bool {
+        let mut parent_stack = ParentSelectors::new();
+        let parent_dependency = Arc::new(self.dependency());
+        for selector in list {
+            // Subjects inside relative selectors aren't really subjects.
+            // This simplifies compound state tracking as well (Additional
+            // states we track for relative selector's inner selectors should
+            // not leak out of the relevant selector).
+            let mut nested = RelativeSelectorInnerDependencyCollector {
+                map: &mut *self.map,
+                parent_dependency: &parent_dependency,
+                document_state: &mut *self.document_state,
+                selector,
+                parent_selectors: &mut parent_stack,
+                quirks_mode: self.quirks_mode,
+                compound_state: RelativeSelectorPerCompoundState::new(0),
+                alloc_error: &mut *self.alloc_error,
+            };
+            if !nested.visit_whole_selector() {
+                return false;
+            }
+        }
+        true
+    }
+
+    fn visit_relative_selector_list(
+        &mut self,
+        _list: &[selectors::parser::RelativeSelector<Self::Impl>],
+    ) -> bool {
+        // Ignore nested relative selectors. These can happen as a result of nesting.
+        true
+    }
+
+    fn visit_simple_selector(&mut self, s: &Component<SelectorImpl>) -> bool {
+        match *s {
+            Component::ID(..) | Component::Class(..) => {
+                self.compound_state.added_entry = true;
+                if let Err(err) = on_id_or_class(s, self.quirks_mode, self) {
+                    *self.alloc_error = Some(err.into());
+                    return false;
+                }
+                true
+            },
+            Component::NonTSPseudoClass(ref pc) => {
+                if !pc
+                    .state_flag()
+                    .intersects(ElementState::VISITED_OR_UNVISITED)
+                {
+                    // Visited/Unvisited styling doesn't take the usual state invalidation path.
+                    self.compound_state.added_entry = true;
+                }
+                if let Err(err) = on_pseudo_class(pc, self) {
+                    *self.alloc_error = Some(err.into());
+                    return false;
+                }
+                true
+            },
+            Component::Empty => {
+                self.compound_state
+                    .ts_state
+                    .insert(TSStateForInvalidation::EMPTY);
+                true
+            },
+            Component::Nth(data) => {
+                let kind = if data.is_simple_edge() {
+                    TSStateForInvalidation::NTH_EDGE
+                } else {
+                    TSStateForInvalidation::NTH
+                };
+                self.compound_state
+                    .ts_state
+                    .insert(kind);
+                true
+            },
+            Component::RelativeSelectorAnchor => unreachable!("Should not visit this far"),
+            _ => true,
+        }
+    }
+
+    fn visit_attribute_selector(
+        &mut self,
+        _: &NamespaceConstraint<&Namespace>,
+        local_name: &LocalName,
+        local_name_lower: &LocalName,
+    ) -> bool {
+        self.compound_state.added_entry = true;
+        if let Err(err) = on_attribute(local_name, local_name_lower, self) {
+            *self.alloc_error = Some(err);
+            return false;
+        }
+        true
+    }
+}
+
+/// A struct that collects invalidations from a complex selector inside a relative selector.
+/// TODO(dshin): All of this duplication is not great Perhaps should be merged to the normal
+/// one, if possible? See bug 1855690.
+struct RelativeSelectorInnerDependencyCollector<'a, 'b> {
+    map: &'a mut RelativeSelectorInvalidationMap,
+
+    /// The document this _complex_ selector is affected by.
+    ///
+    /// We don't need to track state per compound selector, since it's global
+    /// state and it changes for everything.
+    document_state: &'a mut DocumentState,
+
+    /// Parent relative selector dependency.
+    parent_dependency: &'b Arc<Dependency>,
+
+    /// The current inner relative selector and offset we're iterating.
+    selector: &'a Selector<SelectorImpl>,
+
+    /// The stack of parent selectors that we have, and at which offset of the
+    /// sequence.
+    ///
+    /// This starts empty. It grows when we find nested :is and :where selector
+    /// lists. The dependency field is cached and reference counted.
+    parent_selectors: &'a mut ParentSelectors,
+
+    /// The quirks mode of the document where we're inserting dependencies.
+    quirks_mode: QuirksMode,
+
+    /// State relevant to a given compound selector.
+    compound_state: RelativeSelectorPerCompoundState,
+
+    /// The allocation error, if we OOM.
+    alloc_error: &'a mut Option<AllocErr>,
+}
+
+impl<'a, 'b> Collector for RelativeSelectorInnerDependencyCollector<'a, 'b> {
+    fn dependency(&mut self) -> Dependency {
+        let parent = parent_dependency(self.parent_selectors, Some(self.parent_dependency));
+        Dependency {
+            selector: self.selector.clone(),
+            selector_offset: self.compound_state.state.offset,
+            parent,
+            relative_kind: None,
+        }
+    }
+
+    fn id_map(&mut self) -> &mut IdOrClassDependencyMap {
+        &mut self.map.map.id_to_selector
+    }
+
+    fn class_map(&mut self) -> &mut IdOrClassDependencyMap {
+        &mut self.map.map.class_to_selector
+    }
+
+    fn state_map(&mut self) -> &mut StateDependencyMap {
+        &mut self.map.map.state_affecting_selectors
+    }
+
+    fn attribute_map(&mut self) -> &mut LocalNameDependencyMap {
+        &mut self.map.map.other_attribute_affecting_selectors
+    }
+
+    fn update_states(&mut self, element_state: ElementState, document_state: DocumentState) {
+        self.compound_state.state.element_state |= element_state;
+        *self.document_state |= document_state;
+    }
+
+    fn type_map(&mut self) -> &mut LocalNameDependencyMap {
+        &mut self.map.type_to_selector
+    }
+
+    fn ts_state_map(&mut self) -> &mut TSStateDependencyMap {
+        &mut self.map.ts_state_to_selector
+    }
+
+    fn any_vec(&mut self) -> &mut AnyDependencyMap {
+        &mut self.map.any_to_selector
+    }
+}
+
+impl<'a, 'b> RelativeSelectorInnerDependencyCollector<'a, 'b> {
+    fn visit_whole_selector(&mut self) -> bool {
+        let mut iter = self.selector.iter();
+        let mut index = 0;
+        loop {
+            // Reset the compound state.
+            self.compound_state = RelativeSelectorPerCompoundState::new(index);
+
+            // Visit all the simple selectors in this sequence.
+            for ss in &mut iter {
+                if !ss.visit(self) {
+                    return false;
+                }
+                index += 1; // Account for the simple selector.
+            }
+
+            if let Err(err) = add_pseudo_class_dependency(
+                self.compound_state.state.element_state,
+                self.quirks_mode,
+                self,
+            ) {
+                *self.alloc_error = Some(err);
+                return false;
+            }
+
+            if let Err(err) =
+                add_ts_pseudo_class_dependency(self.compound_state.ts_state, self.quirks_mode, self)
+            {
+                *self.alloc_error = Some(err);
+                return false;
+            }
+
+            if !self.compound_state.added_entry {
+                // Not great - we didn't add any uniquely identifiable information.
+                if let Err(err) =
+                    add_non_unique_info(&self.selector, self.compound_state.state.offset, self)
+                {
+                    *self.alloc_error = Some(err);
+                    return false;
+                }
+            }
+
+            let combinator = iter.next_sequence();
+            if combinator.is_none() {
+                return true;
+            }
+            index += 1; // account for the combinator
+        }
+    }
+}
+
+impl<'a, 'b> SelectorVisitor for RelativeSelectorInnerDependencyCollector<'a, 'b> {
+    type Impl = SelectorImpl;
+
+    fn visit_selector_list(
+        &mut self,
+        _list_kind: SelectorListKind,
+        list: &[Selector<SelectorImpl>],
+    ) -> bool {
+        let parent_dependency = Arc::new(self.dependency());
+        for selector in list {
+            // Subjects inside relative selectors aren't really subjects.
+            // This simplifies compound state tracking as well (Additional
+            // states we track for relative selector's inner selectors should
+            // not leak out of the relevant selector).
+            let mut nested = RelativeSelectorInnerDependencyCollector {
+                map: &mut *self.map,
+                parent_dependency: &parent_dependency,
+                document_state: &mut *self.document_state,
+                selector,
+                parent_selectors: &mut *self.parent_selectors,
+                quirks_mode: self.quirks_mode,
+                compound_state: RelativeSelectorPerCompoundState::new(0),
+                alloc_error: &mut *self.alloc_error,
+            };
+            if !nested.visit_whole_selector() {
+                return false;
+            }
+        }
+        true
+    }
+
+    fn visit_relative_selector_list(
+        &mut self,
+        _list: &[selectors::parser::RelativeSelector<Self::Impl>],
+    ) -> bool {
+        // Ignore nested relative selectors. These can happen as a result of nesting.
+        true
+    }
+
+    fn visit_simple_selector(&mut self, s: &Component<SelectorImpl>) -> bool {
+        match *s {
+            Component::ID(..) | Component::Class(..) => {
+                self.compound_state.added_entry = true;
+                if let Err(err) = on_id_or_class(s, self.quirks_mode, self) {
+                    *self.alloc_error = Some(err.into());
+                    return false;
+                }
+                true
+            },
+            Component::NonTSPseudoClass(ref pc) => {
+                if !pc
+                    .state_flag()
+                    .intersects(ElementState::VISITED_OR_UNVISITED)
+                {
+                    // Visited/Unvisited styling doesn't take the usual state invalidation path.
+                    self.compound_state.added_entry = true;
+                }
+                if let Err(err) = on_pseudo_class(pc, self) {
+                    *self.alloc_error = Some(err.into());
+                    return false;
+                }
+                true
+            },
+            Component::Empty => {
+                self.compound_state
+                    .ts_state
+                    .insert(TSStateForInvalidation::EMPTY);
+                true
+            },
+            Component::Nth(data) => {
+                let kind = if data.is_simple_edge() {
+                    TSStateForInvalidation::NTH_EDGE
+                } else {
+                    TSStateForInvalidation::NTH
+                };
+                self.compound_state
+                    .ts_state
+                    .insert(kind);
+                true
+            },
+            Component::RelativeSelectorAnchor => unreachable!("Should not visit this far"),
+            _ => true,
+        }
+    }
+
+    fn visit_attribute_selector(
+        &mut self,
+        _: &NamespaceConstraint<&Namespace>,
+        local_name: &LocalName,
+        local_name_lower: &LocalName,
+    ) -> bool {
+        self.compound_state.added_entry = true;
+        if let Err(err) = on_attribute(local_name, local_name_lower, self) {
+            *self.alloc_error = Some(err);
+            return false;
+        }
+        true
+    }
+}
diff --git a/servo/components/style/invalidation/element/invalidator.rs b/servo/components/style/invalidation/element/invalidator.rs
new file mode 100644
index 0000000000..5dee1f5dcf
--- /dev/null
+++ b/servo/components/style/invalidation/element/invalidator.rs
@@ -0,0 +1,1130 @@
+/* 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/. */
+
+//! The struct that takes care of encapsulating all the logic on where and how
+//! element styles need to be invalidated.
+
+use crate::context::StackLimitChecker;
+use crate::dom::{TElement, TNode, TShadowRoot};
+use crate::invalidation::element::invalidation_map::{
+    Dependency, DependencyInvalidationKind, NormalDependencyInvalidationKind,
+    RelativeDependencyInvalidationKind,
+};
+use selectors::matching::matches_compound_selector_from;
+use selectors::matching::{CompoundSelectorMatchingResult, MatchingContext};
+use selectors::parser::{Combinator, Component};
+use selectors::OpaqueElement;
+use smallvec::SmallVec;
+use std::fmt;
+use std::fmt::Write;
+
+struct SiblingInfo<E>
+where
+    E: TElement,
+{
+    affected: E,
+    prev_sibling: Option<E>,
+    next_sibling: Option<E>,
+}
+
+/// Traversal mapping for elements under consideration. It acts like a snapshot map,
+/// though this only "maps" one element at most.
+/// For general invalidations, this has no effect, especially since when
+/// DOM mutates, the mutation's effect should not escape the subtree being mutated.
+/// This is not the case for relative selectors, unfortunately, so we may end up
+/// traversing a portion of the DOM tree that mutated. In case the mutation is removal,
+/// its sibling relation is severed by the time the invalidation happens. This structure
+/// recovers that relation. Note - it assumes that there is only one element under this
+/// effect.
+pub struct SiblingTraversalMap<E>
+where
+    E: TElement,
+{
+    info: Option<SiblingInfo<E>>,
+}
+
+impl<E> Default for SiblingTraversalMap<E>
+where
+    E: TElement,
+{
+    fn default() -> Self {
+        Self { info: None }
+    }
+}
+
+impl<E> SiblingTraversalMap<E>
+where
+    E: TElement,
+{
+    /// Create a new traversal map with the affected element.
+    pub fn new(affected: E, prev_sibling: Option<E>, next_sibling: Option<E>) -> Self {
+        Self {
+            info: Some(SiblingInfo {
+                affected,
+                prev_sibling,
+                next_sibling,
+            }),
+        }
+    }
+
+    /// Get the element's previous sibling element.
+    pub fn next_sibling_for(&self, element: &E) -> Option<E> {
+        if let Some(ref info) = self.info {
+            if *element == info.affected {
+                return info.next_sibling;
+            }
+        }
+        element.next_sibling_element()
+    }
+
+    /// Get the element's previous sibling element.
+    pub fn prev_sibling_for(&self, element: &E) -> Option<E> {
+        if let Some(ref info) = self.info {
+            if *element == info.affected {
+                return info.prev_sibling;
+            }
+        }
+        element.prev_sibling_element()
+    }
+}
+
+/// A trait to abstract the collection of invalidations for a given pass.
+pub trait InvalidationProcessor<'a, 'b, E>
+where
+    E: TElement,
+{
+    /// Whether an invalidation that contains only a pseudo-element selector
+    /// like ::before or ::after triggers invalidation of the element that would
+    /// originate it.
+    fn invalidates_on_pseudo_element(&self) -> bool {
+        false
+    }
+
+    /// Whether the invalidation processor only cares about light-tree
+    /// descendants of a given element, that is, doesn't invalidate
+    /// pseudo-elements, NAC, shadow dom...
+    fn light_tree_only(&self) -> bool {
+        false
+    }
+
+    /// When a dependency from a :where or :is selector matches, it may still be
+    /// the case that we don't need to invalidate the full style. Consider the
+    /// case of:
+    ///
+    ///   div .foo:where(.bar *, .baz) .qux
+    ///
+    /// We can get to the `*` part after a .bar class change, but you only need
+    /// to restyle the element if it also matches .foo.
+    ///
+    /// Similarly, you only need to restyle .baz if the whole result of matching
+    /// the selector changes.
+    ///
+    /// This function is called to check the result of matching the "outer"
+    /// dependency that we generate for the parent of the `:where` selector,
+    /// that is, in the case above it should match
+    /// `div .foo:where(.bar *, .baz)`.
+    ///
+    /// Returning true unconditionally here is over-optimistic and may
+    /// over-invalidate.
+    fn check_outer_dependency(&mut self, dependency: &Dependency, element: E) -> bool;
+
+    /// The matching context that should be used to process invalidations.
+    fn matching_context(&mut self) -> &mut MatchingContext<'b, E::Impl>;
+
+    /// The traversal map that should be used to process invalidations.
+    fn sibling_traversal_map(&self) -> &SiblingTraversalMap<E>;
+
+    /// Collect invalidations for a given element's descendants and siblings.
+    ///
+    /// Returns whether the element itself was invalidated.
+    fn collect_invalidations(
+        &mut self,
+        element: E,
+        self_invalidations: &mut InvalidationVector<'a>,
+        descendant_invalidations: &mut DescendantInvalidationLists<'a>,
+        sibling_invalidations: &mut InvalidationVector<'a>,
+    ) -> bool;
+
+    /// Returns whether the invalidation process should process the descendants
+    /// of the given element.
+    fn should_process_descendants(&mut self, element: E) -> bool;
+
+    /// Executes an arbitrary action when the recursion limit is exceded (if
+    /// any).
+    fn recursion_limit_exceeded(&mut self, element: E);
+
+    /// Executes an action when `Self` is invalidated.
+    fn invalidated_self(&mut self, element: E);
+
+    /// Executes an action when `sibling` is invalidated as a sibling of
+    /// `of`.
+    fn invalidated_sibling(&mut self, sibling: E, of: E);
+
+    /// Executes an action when any descendant of `Self` is invalidated.
+    fn invalidated_descendants(&mut self, element: E, child: E);
+
+    /// Executes an action when an element in a relative selector is reached.
+    /// Lets the dependency to be borrowed for further processing out of the
+    /// invalidation traversal.
+    fn found_relative_selector_invalidation(
+        &mut self,
+        _element: E,
+        _kind: RelativeDependencyInvalidationKind,
+        _relative_dependency: &'a Dependency,
+    ) {
+        debug_assert!(false, "Reached relative selector dependency");
+    }
+}
+
+/// Different invalidation lists for descendants.
+#[derive(Debug, Default)]
+pub struct DescendantInvalidationLists<'a> {
+    /// Invalidations for normal DOM children and pseudo-elements.
+    ///
+    /// TODO(emilio): Having a list of invalidations just for pseudo-elements
+    /// may save some work here and there.
+    pub dom_descendants: InvalidationVector<'a>,
+    /// Invalidations for slotted children of an element.
+    pub slotted_descendants: InvalidationVector<'a>,
+    /// Invalidations for ::part()s of an element.
+    pub parts: InvalidationVector<'a>,
+}
+
+impl<'a> DescendantInvalidationLists<'a> {
+    fn is_empty(&self) -> bool {
+        self.dom_descendants.is_empty() &&
+            self.slotted_descendants.is_empty() &&
+            self.parts.is_empty()
+    }
+}
+
+/// The struct that takes care of encapsulating all the logic on where and how
+/// element styles need to be invalidated.
+pub struct TreeStyleInvalidator<'a, 'b, 'c, E, P: 'a>
+where
+    'b: 'a,
+    E: TElement,
+    P: InvalidationProcessor<'b, 'c, E>,
+{
+    element: E,
+    stack_limit_checker: Option<&'a StackLimitChecker>,
+    processor: &'a mut P,
+    _marker: std::marker::PhantomData<(&'b (), &'c ())>,
+}
+
+/// A vector of invalidations, optimized for small invalidation sets.
+pub type InvalidationVector<'a> = SmallVec<[Invalidation<'a>; 10]>;
+
+/// The kind of descendant invalidation we're processing.
+#[derive(Clone, Copy, Debug, Eq, PartialEq)]
+enum DescendantInvalidationKind {
+    /// A DOM descendant invalidation.
+    Dom,
+    /// A ::slotted() descendant invalidation.
+    Slotted,
+    /// A ::part() descendant invalidation.
+    Part,
+}
+
+/// The kind of invalidation we're processing.
+///
+/// We can use this to avoid pushing invalidations of the same kind to our
+/// descendants or siblings.
+#[derive(Clone, Copy, Debug, Eq, PartialEq)]
+enum InvalidationKind {
+    Descendant(DescendantInvalidationKind),
+    Sibling,
+}
+
+/// An `Invalidation` is a complex selector that describes which elements,
+/// relative to a current element we are processing, must be restyled.
+#[derive(Clone)]
+pub struct Invalidation<'a> {
+    /// The dependency that generated this invalidation.
+    ///
+    /// Note that the offset inside the dependency is not really useful after
+    /// construction.
+    dependency: &'a Dependency,
+    /// The right shadow host from where the rule came from, if any.
+    ///
+    /// This is needed to ensure that we match the selector with the right
+    /// state, as whether some selectors like :host and ::part() match depends
+    /// on it.
+    scope: Option<OpaqueElement>,
+    /// The offset of the selector pointing to a compound selector.
+    ///
+    /// This order is a "parse order" offset, that is, zero is the leftmost part
+    /// of the selector written as parsed / serialized.
+    ///
+    /// It is initialized from the offset from `dependency`.
+    offset: usize,
+    /// Whether the invalidation was already matched by any previous sibling or
+    /// ancestor.
+    ///
+    /// If this is the case, we can avoid pushing invalidations generated by
+    /// this one if the generated invalidation is effective for all the siblings
+    /// or descendants after us.
+    matched_by_any_previous: bool,
+}
+
+impl<'a> Invalidation<'a> {
+    /// Create a new invalidation for matching a dependency.
+    pub fn new(dependency: &'a Dependency, scope: Option<OpaqueElement>) -> Self {
+        debug_assert!(
+            dependency.selector_offset == dependency.selector.len() + 1 ||
+                dependency.normal_invalidation_kind() !=
+                    NormalDependencyInvalidationKind::Element,
+            "No point to this, if the dependency matched the element we should just invalidate it"
+        );
+        Self {
+            dependency,
+            scope,
+            // + 1 to go past the combinator.
+            offset: dependency.selector.len() + 1 - dependency.selector_offset,
+            matched_by_any_previous: false,
+        }
+    }
+
+    /// Whether this invalidation is effective for the next sibling or
+    /// descendant after us.
+    fn effective_for_next(&self) -> bool {
+        if self.offset == 0 {
+            return true;
+        }
+
+        // TODO(emilio): For pseudo-elements this should be mostly false, except
+        // for the weird pseudos in <input type="number">.
+        //
+        // We should be able to do better here!
+        match self
+            .dependency
+            .selector
+            .combinator_at_parse_order(self.offset - 1)
+        {
+            Combinator::Descendant | Combinator::LaterSibling | Combinator::PseudoElement => true,
+            Combinator::Part |
+            Combinator::SlotAssignment |
+            Combinator::NextSibling |
+            Combinator::Child => false,
+        }
+    }
+
+    fn kind(&self) -> InvalidationKind {
+        if self.offset == 0 {
+            return InvalidationKind::Descendant(DescendantInvalidationKind::Dom);
+        }
+
+        match self
+            .dependency
+            .selector
+            .combinator_at_parse_order(self.offset - 1)
+        {
+            Combinator::Child | Combinator::Descendant | Combinator::PseudoElement => {
+                InvalidationKind::Descendant(DescendantInvalidationKind::Dom)
+            },
+            Combinator::Part => InvalidationKind::Descendant(DescendantInvalidationKind::Part),
+            Combinator::SlotAssignment => {
+                InvalidationKind::Descendant(DescendantInvalidationKind::Slotted)
+            },
+            Combinator::NextSibling | Combinator::LaterSibling => InvalidationKind::Sibling,
+        }
+    }
+}
+
+impl<'a> fmt::Debug for Invalidation<'a> {
+    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
+        use cssparser::ToCss;
+
+        f.write_str("Invalidation(")?;
+        for component in self
+            .dependency
+            .selector
+            .iter_raw_parse_order_from(self.offset)
+        {
+            if matches!(*component, Component::Combinator(..)) {
+                break;
+            }
+            component.to_css(f)?;
+        }
+        f.write_char(')')
+    }
+}
+
+/// The result of processing a single invalidation for a given element.
+struct SingleInvalidationResult {
+    /// Whether the element itself was invalidated.
+    invalidated_self: bool,
+    /// Whether the invalidation matched, either invalidating the element or
+    /// generating another invalidation.
+    matched: bool,
+}
+
+/// The result of a whole invalidation process for a given element.
+pub struct InvalidationResult {
+    /// Whether the element itself was invalidated.
+    invalidated_self: bool,
+    /// Whether the element's descendants were invalidated.
+    invalidated_descendants: bool,
+    /// Whether the element's siblings were invalidated.
+    invalidated_siblings: bool,
+}
+
+impl InvalidationResult {
+    /// Create an emtpy result.
+    pub fn empty() -> Self {
+        Self {
+            invalidated_self: false,
+            invalidated_descendants: false,
+            invalidated_siblings: false,
+        }
+    }
+
+    /// Whether the invalidation has invalidate the element itself.
+    pub fn has_invalidated_self(&self) -> bool {
+        self.invalidated_self
+    }
+
+    /// Whether the invalidation has invalidate desendants.
+    pub fn has_invalidated_descendants(&self) -> bool {
+        self.invalidated_descendants
+    }
+
+    /// Whether the invalidation has invalidate siblings.
+    pub fn has_invalidated_siblings(&self) -> bool {
+        self.invalidated_siblings
+    }
+}
+
+impl<'a, 'b, 'c, E, P: 'a> TreeStyleInvalidator<'a, 'b, 'c, E, P>
+where
+    'b: 'a,
+    E: TElement,
+    P: InvalidationProcessor<'b, 'c, E>,
+{
+    /// Trivially constructs a new `TreeStyleInvalidator`.
+    pub fn new(
+        element: E,
+        stack_limit_checker: Option<&'a StackLimitChecker>,
+        processor: &'a mut P,
+    ) -> Self {
+        Self {
+            element,
+            stack_limit_checker,
+            processor,
+            _marker: std::marker::PhantomData,
+        }
+    }
+
+    /// Perform the invalidation pass.
+    pub fn invalidate(mut self) -> InvalidationResult {
+        debug!("StyleTreeInvalidator::invalidate({:?})", self.element);
+
+        let mut self_invalidations = InvalidationVector::new();
+        let mut descendant_invalidations = DescendantInvalidationLists::default();
+        let mut sibling_invalidations = InvalidationVector::new();
+
+        let mut invalidated_self = self.processor.collect_invalidations(
+            self.element,
+            &mut self_invalidations,
+            &mut descendant_invalidations,
+            &mut sibling_invalidations,
+        );
+
+        debug!("Collected invalidations (self: {}): ", invalidated_self);
+        debug!(
+            " > self: {}, {:?}",
+            self_invalidations.len(),
+            self_invalidations
+        );
+        debug!(" > descendants: {:?}", descendant_invalidations);
+        debug!(
+            " > siblings: {}, {:?}",
+            sibling_invalidations.len(),
+            sibling_invalidations
+        );
+
+        let invalidated_self_from_collection = invalidated_self;
+
+        invalidated_self |= self.process_descendant_invalidations(
+            &self_invalidations,
+            &mut descendant_invalidations,
+            &mut sibling_invalidations,
+            DescendantInvalidationKind::Dom,
+        );
+
+        if invalidated_self && !invalidated_self_from_collection {
+            self.processor.invalidated_self(self.element);
+        }
+
+        let invalidated_descendants = self.invalidate_descendants(&descendant_invalidations);
+        let invalidated_siblings = self.invalidate_siblings(&mut sibling_invalidations);
+
+        InvalidationResult {
+            invalidated_self,
+            invalidated_descendants,
+            invalidated_siblings,
+        }
+    }
+
+    /// Go through later DOM siblings, invalidating style as needed using the
+    /// `sibling_invalidations` list.
+    ///
+    /// Returns whether any sibling's style or any sibling descendant's style
+    /// was invalidated.
+    fn invalidate_siblings(&mut self, sibling_invalidations: &mut InvalidationVector<'b>) -> bool {
+        if sibling_invalidations.is_empty() {
+            return false;
+        }
+
+        let mut current = self
+            .processor
+            .sibling_traversal_map()
+            .next_sibling_for(&self.element);
+        let mut any_invalidated = false;
+
+        while let Some(sibling) = current {
+            let mut sibling_invalidator =
+                TreeStyleInvalidator::new(sibling, self.stack_limit_checker, self.processor);
+
+            let mut invalidations_for_descendants = DescendantInvalidationLists::default();
+            let invalidated_sibling = sibling_invalidator.process_sibling_invalidations(
+                &mut invalidations_for_descendants,
+                sibling_invalidations,
+            );
+
+            if invalidated_sibling {
+                sibling_invalidator
+                    .processor
+                    .invalidated_sibling(sibling, self.element);
+            }
+
+            any_invalidated |= invalidated_sibling;
+
+            any_invalidated |=
+                sibling_invalidator.invalidate_descendants(&invalidations_for_descendants);
+
+            if sibling_invalidations.is_empty() {
+                break;
+            }
+
+            current = self
+                .processor
+                .sibling_traversal_map()
+                .next_sibling_for(&sibling);
+        }
+
+        any_invalidated
+    }
+
+    fn invalidate_pseudo_element_or_nac(
+        &mut self,
+        child: E,
+        invalidations: &[Invalidation<'b>],
+    ) -> bool {
+        let mut sibling_invalidations = InvalidationVector::new();
+
+        let result = self.invalidate_child(
+            child,
+            invalidations,
+            &mut sibling_invalidations,
+            DescendantInvalidationKind::Dom,
+        );
+
+        // Roots of NAC subtrees can indeed generate sibling invalidations, but
+        // they can be just ignored, since they have no siblings.
+        //
+        // Note that we can end up testing selectors that wouldn't end up
+        // matching due to this being NAC, like those coming from document
+        // rules, but we overinvalidate instead of checking this.
+
+        result
+    }
+
+    /// Invalidate a child and recurse down invalidating its descendants if
+    /// needed.
+    fn invalidate_child(
+        &mut self,
+        child: E,
+        invalidations: &[Invalidation<'b>],
+        sibling_invalidations: &mut InvalidationVector<'b>,
+        descendant_invalidation_kind: DescendantInvalidationKind,
+    ) -> bool {
+        let mut invalidations_for_descendants = DescendantInvalidationLists::default();
+
+        let mut invalidated_child = false;
+        let invalidated_descendants = {
+            let mut child_invalidator =
+                TreeStyleInvalidator::new(child, self.stack_limit_checker, self.processor);
+
+            invalidated_child |= child_invalidator.process_sibling_invalidations(
+                &mut invalidations_for_descendants,
+                sibling_invalidations,
+            );
+
+            invalidated_child |= child_invalidator.process_descendant_invalidations(
+                invalidations,
+                &mut invalidations_for_descendants,
+                sibling_invalidations,
+                descendant_invalidation_kind,
+            );
+
+            if invalidated_child {
+                child_invalidator.processor.invalidated_self(child);
+            }
+
+            child_invalidator.invalidate_descendants(&invalidations_for_descendants)
+        };
+
+        // The child may not be a flattened tree child of the current element,
+        // but may be arbitrarily deep.
+        //
+        // Since we keep the traversal flags in terms of the flattened tree,
+        // we need to propagate it as appropriate.
+        if invalidated_child || invalidated_descendants {
+            self.processor.invalidated_descendants(self.element, child);
+        }
+
+        invalidated_child || invalidated_descendants
+    }
+
+    fn invalidate_nac(&mut self, invalidations: &[Invalidation<'b>]) -> bool {
+        let mut any_nac_root = false;
+
+        let element = self.element;
+        element.each_anonymous_content_child(|nac| {
+            any_nac_root |= self.invalidate_pseudo_element_or_nac(nac, invalidations);
+        });
+
+        any_nac_root
+    }
+
+    // NB: It's important that this operates on DOM children, which is what
+    // selector-matching operates on.
+    fn invalidate_dom_descendants_of(
+        &mut self,
+        parent: E::ConcreteNode,
+        invalidations: &[Invalidation<'b>],
+    ) -> bool {
+        let mut any_descendant = false;
+
+        let mut sibling_invalidations = InvalidationVector::new();
+        for child in parent.dom_children() {
+            let child = match child.as_element() {
+                Some(e) => e,
+                None => continue,
+            };
+
+            any_descendant |= self.invalidate_child(
+                child,
+                invalidations,
+                &mut sibling_invalidations,
+                DescendantInvalidationKind::Dom,
+            );
+        }
+
+        any_descendant
+    }
+
+    fn invalidate_parts_in_shadow_tree(
+        &mut self,
+        shadow: <E::ConcreteNode as TNode>::ConcreteShadowRoot,
+        invalidations: &[Invalidation<'b>],
+    ) -> bool {
+        debug_assert!(!invalidations.is_empty());
+
+        let mut any = false;
+        let mut sibling_invalidations = InvalidationVector::new();
+
+        for node in shadow.as_node().dom_descendants() {
+            let element = match node.as_element() {
+                Some(e) => e,
+                None => continue,
+            };
+
+            if element.has_part_attr() {
+                any |= self.invalidate_child(
+                    element,
+                    invalidations,
+                    &mut sibling_invalidations,
+                    DescendantInvalidationKind::Part,
+                );
+                debug_assert!(
+                    sibling_invalidations.is_empty(),
+                    "::part() shouldn't have sibling combinators to the right, \
+                     this makes no sense! {:?}",
+                    sibling_invalidations
+                );
+            }
+
+            if let Some(shadow) = element.shadow_root() {
+                if element.exports_any_part() {
+                    any |= self.invalidate_parts_in_shadow_tree(shadow, invalidations)
+                }
+            }
+        }
+
+        any
+    }
+
+    fn invalidate_parts(&mut self, invalidations: &[Invalidation<'b>]) -> bool {
+        if invalidations.is_empty() {
+            return false;
+        }
+
+        let shadow = match self.element.shadow_root() {
+            Some(s) => s,
+            None => return false,
+        };
+
+        self.invalidate_parts_in_shadow_tree(shadow, invalidations)
+    }
+
+    fn invalidate_slotted_elements(&mut self, invalidations: &[Invalidation<'b>]) -> bool {
+        if invalidations.is_empty() {
+            return false;
+        }
+
+        let slot = self.element;
+        self.invalidate_slotted_elements_in_slot(slot, invalidations)
+    }
+
+    fn invalidate_slotted_elements_in_slot(
+        &mut self,
+        slot: E,
+        invalidations: &[Invalidation<'b>],
+    ) -> bool {
+        let mut any = false;
+
+        let mut sibling_invalidations = InvalidationVector::new();
+        for node in slot.slotted_nodes() {
+            let element = match node.as_element() {
+                Some(e) => e,
+                None => continue,
+            };
+
+            if element.is_html_slot_element() {
+                any |= self.invalidate_slotted_elements_in_slot(element, invalidations);
+            } else {
+                any |= self.invalidate_child(
+                    element,
+                    invalidations,
+                    &mut sibling_invalidations,
+                    DescendantInvalidationKind::Slotted,
+                );
+            }
+
+            debug_assert!(
+                sibling_invalidations.is_empty(),
+                "::slotted() shouldn't have sibling combinators to the right, \
+                 this makes no sense! {:?}",
+                sibling_invalidations
+            );
+        }
+
+        any
+    }
+
+    fn invalidate_non_slotted_descendants(&mut self, invalidations: &[Invalidation<'b>]) -> bool {
+        if invalidations.is_empty() {
+            return false;
+        }
+
+        if self.processor.light_tree_only() {
+            let node = self.element.as_node();
+            return self.invalidate_dom_descendants_of(node, invalidations);
+        }
+
+        let mut any_descendant = false;
+
+        // NOTE(emilio): This is only needed for Shadow DOM to invalidate
+        // correctly on :host(..) changes. Instead of doing this, we could add
+        // a third kind of invalidation list that walks shadow root children,
+        // but it's not clear it's worth it.
+        //
+        // Also, it's needed as of right now for document state invalidation,
+        // where we rely on iterating every element that ends up in the composed
+        // doc, but we could fix that invalidating per subtree.
+        if let Some(root) = self.element.shadow_root() {
+            any_descendant |= self.invalidate_dom_descendants_of(root.as_node(), invalidations);
+        }
+
+        if let Some(marker) = self.element.marker_pseudo_element() {
+            any_descendant |= self.invalidate_pseudo_element_or_nac(marker, invalidations);
+        }
+
+        if let Some(before) = self.element.before_pseudo_element() {
+            any_descendant |= self.invalidate_pseudo_element_or_nac(before, invalidations);
+        }
+
+        let node = self.element.as_node();
+        any_descendant |= self.invalidate_dom_descendants_of(node, invalidations);
+
+        if let Some(after) = self.element.after_pseudo_element() {
+            any_descendant |= self.invalidate_pseudo_element_or_nac(after, invalidations);
+        }
+
+        any_descendant |= self.invalidate_nac(invalidations);
+
+        any_descendant
+    }
+
+    /// Given the descendant invalidation lists, go through the current
+    /// element's descendants, and invalidate style on them.
+    fn invalidate_descendants(&mut self, invalidations: &DescendantInvalidationLists<'b>) -> bool {
+        if invalidations.is_empty() {
+            return false;
+        }
+
+        debug!(
+            "StyleTreeInvalidator::invalidate_descendants({:?})",
+            self.element
+        );
+        debug!(" > {:?}", invalidations);
+
+        let should_process = self.processor.should_process_descendants(self.element);
+
+        if !should_process {
+            return false;
+        }
+
+        if let Some(checker) = self.stack_limit_checker {
+            if checker.limit_exceeded() {
+                self.processor.recursion_limit_exceeded(self.element);
+                return true;
+            }
+        }
+
+        let mut any_descendant = false;
+
+        any_descendant |= self.invalidate_non_slotted_descendants(&invalidations.dom_descendants);
+        any_descendant |= self.invalidate_slotted_elements(&invalidations.slotted_descendants);
+        any_descendant |= self.invalidate_parts(&invalidations.parts);
+
+        any_descendant
+    }
+
+    /// Process the given sibling invalidations coming from our previous
+    /// sibling.
+    ///
+    /// The sibling invalidations are somewhat special because they can be
+    /// modified on the fly. New invalidations may be added and removed.
+    ///
+    /// In particular, all descendants get the same set of invalidations from
+    /// the parent, but the invalidations from a given sibling depend on the
+    /// ones we got from the previous one.
+    ///
+    /// Returns whether invalidated the current element's style.
+    fn process_sibling_invalidations(
+        &mut self,
+        descendant_invalidations: &mut DescendantInvalidationLists<'b>,
+        sibling_invalidations: &mut InvalidationVector<'b>,
+    ) -> bool {
+        let mut i = 0;
+        let mut new_sibling_invalidations = InvalidationVector::new();
+        let mut invalidated_self = false;
+
+        while i < sibling_invalidations.len() {
+            let result = self.process_invalidation(
+                &sibling_invalidations[i],
+                descendant_invalidations,
+                &mut new_sibling_invalidations,
+                InvalidationKind::Sibling,
+            );
+
+            invalidated_self |= result.invalidated_self;
+            sibling_invalidations[i].matched_by_any_previous |= result.matched;
+            if sibling_invalidations[i].effective_for_next() {
+                i += 1;
+            } else {
+                sibling_invalidations.remove(i);
+            }
+        }
+
+        sibling_invalidations.extend(new_sibling_invalidations.drain(..));
+        invalidated_self
+    }
+
+    /// Process a given invalidation list coming from our parent,
+    /// adding to `descendant_invalidations` and `sibling_invalidations` as
+    /// needed.
+    ///
+    /// Returns whether our style was invalidated as a result.
+    fn process_descendant_invalidations(
+        &mut self,
+        invalidations: &[Invalidation<'b>],
+        descendant_invalidations: &mut DescendantInvalidationLists<'b>,
+        sibling_invalidations: &mut InvalidationVector<'b>,
+        descendant_invalidation_kind: DescendantInvalidationKind,
+    ) -> bool {
+        let mut invalidated = false;
+
+        for invalidation in invalidations {
+            let result = self.process_invalidation(
+                invalidation,
+                descendant_invalidations,
+                sibling_invalidations,
+                InvalidationKind::Descendant(descendant_invalidation_kind),
+            );
+
+            invalidated |= result.invalidated_self;
+            if invalidation.effective_for_next() {
+                let mut invalidation = invalidation.clone();
+                invalidation.matched_by_any_previous |= result.matched;
+                debug_assert_eq!(
+                    descendant_invalidation_kind,
+                    DescendantInvalidationKind::Dom,
+                    "Slotted or part invalidations don't propagate."
+                );
+                descendant_invalidations.dom_descendants.push(invalidation);
+            }
+        }
+
+        invalidated
+    }
+
+    /// Processes a given invalidation, potentially invalidating the style of
+    /// the current element.
+    ///
+    /// Returns whether invalidated the style of the element, and whether the
+    /// invalidation should be effective to subsequent siblings or descendants
+    /// down in the tree.
+    fn process_invalidation(
+        &mut self,
+        invalidation: &Invalidation<'b>,
+        descendant_invalidations: &mut DescendantInvalidationLists<'b>,
+        sibling_invalidations: &mut InvalidationVector<'b>,
+        invalidation_kind: InvalidationKind,
+    ) -> SingleInvalidationResult {
+        debug!(
+            "TreeStyleInvalidator::process_invalidation({:?}, {:?}, {:?})",
+            self.element, invalidation, invalidation_kind
+        );
+
+        let matching_result = {
+            let context = self.processor.matching_context();
+            context.current_host = invalidation.scope;
+
+            matches_compound_selector_from(
+                &invalidation.dependency.selector,
+                invalidation.offset,
+                context,
+                &self.element,
+            )
+        };
+
+        let next_invalidation = match matching_result {
+            CompoundSelectorMatchingResult::NotMatched => {
+                return SingleInvalidationResult {
+                    invalidated_self: false,
+                    matched: false,
+                }
+            },
+            CompoundSelectorMatchingResult::FullyMatched => {
+                debug!(" > Invalidation matched completely");
+                // We matched completely. If we're an inner selector now we need
+                // to go outside our selector and carry on invalidating.
+                let mut cur_dependency = invalidation.dependency;
+                loop {
+                    cur_dependency = match cur_dependency.parent {
+                        None => {
+                            return SingleInvalidationResult {
+                                invalidated_self: true,
+                                matched: true,
+                            }
+                        },
+                        Some(ref p) => {
+                            let invalidation_kind = p.invalidation_kind();
+                            match invalidation_kind {
+                                DependencyInvalidationKind::Normal(_) => &**p,
+                                DependencyInvalidationKind::Relative(kind) => {
+                                    self.processor.found_relative_selector_invalidation(
+                                        self.element,
+                                        kind,
+                                        &**p,
+                                    );
+                                    return SingleInvalidationResult {
+                                        invalidated_self: false,
+                                        matched: true,
+                                    };
+                                },
+                            }
+                        },
+                    };
+
+                    debug!(" > Checking outer dependency {:?}", cur_dependency);
+
+                    // The inner selector changed, now check if the full
+                    // previous part of the selector did, before keeping
+                    // checking for descendants.
+                    if !self
+                        .processor
+                        .check_outer_dependency(cur_dependency, self.element)
+                    {
+                        return SingleInvalidationResult {
+                            invalidated_self: false,
+                            matched: false,
+                        };
+                    }
+
+                    if cur_dependency.normal_invalidation_kind() ==
+                        NormalDependencyInvalidationKind::Element
+                    {
+                        continue;
+                    }
+
+                    debug!(" > Generating invalidation");
+                    break Invalidation::new(cur_dependency, invalidation.scope);
+                }
+            },
+            CompoundSelectorMatchingResult::Matched {
+                next_combinator_offset,
+            } => Invalidation {
+                dependency: invalidation.dependency,
+                scope: invalidation.scope,
+                offset: next_combinator_offset + 1,
+                matched_by_any_previous: false,
+            },
+        };
+
+        debug_assert_ne!(
+            next_invalidation.offset, 0,
+            "Rightmost selectors shouldn't generate more invalidations",
+        );
+
+        let mut invalidated_self = false;
+        let next_combinator = next_invalidation
+            .dependency
+            .selector
+            .combinator_at_parse_order(next_invalidation.offset - 1);
+
+        if matches!(next_combinator, Combinator::PseudoElement) &&
+            self.processor.invalidates_on_pseudo_element()
+        {
+            // We need to invalidate the element whenever pseudos change, for
+            // two reasons:
+            //
+            //  * Eager pseudo styles are stored as part of the originating
+            //    element's computed style.
+            //
+            //  * Lazy pseudo-styles might be cached on the originating
+            //    element's pseudo-style cache.
+            //
+            // This could be more fine-grained (perhaps with a RESTYLE_PSEUDOS
+            // hint?).
+            //
+            // Note that we'll also restyle the pseudo-element because it would
+            // match this invalidation.
+            //
+            // FIXME: For non-element-backed pseudos this is still not quite
+            // correct. For example for ::selection even though we invalidate
+            // the style properly there's nothing that triggers a repaint
+            // necessarily. Though this matches old Gecko behavior, and the
+            // ::selection implementation needs to change significantly anyway
+            // to implement https://github.com/w3c/csswg-drafts/issues/2474 for
+            // example.
+            invalidated_self = true;
+        }
+
+        debug!(
+            " > Invalidation matched, next: {:?}, ({:?})",
+            next_invalidation, next_combinator
+        );
+
+        let next_invalidation_kind = next_invalidation.kind();
+
+        // We can skip pushing under some circumstances, and we should
+        // because otherwise the invalidation list could grow
+        // exponentially.
+        //
+        //  * First of all, both invalidations need to be of the same
+        //    kind. This is because of how we propagate them going to
+        //    the right of the tree for sibling invalidations and going
+        //    down the tree for children invalidations. A sibling
+        //    invalidation that ends up generating a children
+        //    invalidation ends up (correctly) in five different lists,
+        //    not in the same list five different times.
+        //
+        //  * Then, the invalidation needs to be matched by a previous
+        //    ancestor/sibling, in order to know that this invalidation
+        //    has been generated already.
+        //
+        //  * Finally, the new invalidation needs to be
+        //    `effective_for_next()`, in order for us to know that it is
+        //    still in the list, since we remove the dependencies that
+        //    aren't from the lists for our children / siblings.
+        //
+        // To go through an example, let's imagine we are processing a
+        // dom subtree like:
+        //
+        //   <div><address><div><div/></div></address></div>
+        //
+        // And an invalidation list with a single invalidation like:
+        //
+        //   [div div div]
+        //
+        // When we process the invalidation list for the outer div, we
+        // match it, and generate a `div div` invalidation, so for the
+        // <address> child we have:
+        //
+        //   [div div div, div div]
+        //
+        // With the first of them marked as `matched`.
+        //
+        // When we process the <address> child, we don't match any of
+        // them, so both invalidations go untouched to our children.
+        //
+        // When we process the second <div>, we match _both_
+        // invalidations.
+        //
+        // However, when matching the first, we can tell it's been
+        // matched, and not push the corresponding `div div`
+        // invalidation, since we know it's necessarily already on the
+        // list.
+        //
+        // Thus, without skipping the push, we'll arrive to the
+        // innermost <div> with:
+        //
+        //   [div div div, div div, div div, div]
+        //
+        // While skipping it, we won't arrive here with duplicating
+        // dependencies:
+        //
+        //   [div div div, div div, div]
+        //
+        let can_skip_pushing = next_invalidation_kind == invalidation_kind &&
+            invalidation.matched_by_any_previous &&
+            next_invalidation.effective_for_next();
+
+        if can_skip_pushing {
+            debug!(
+                " > Can avoid push, since the invalidation had \
+                 already been matched before"
+            );
+        } else {
+            match next_invalidation_kind {
+                InvalidationKind::Descendant(DescendantInvalidationKind::Dom) => {
+                    descendant_invalidations
+                        .dom_descendants
+                        .push(next_invalidation);
+                },
+                InvalidationKind::Descendant(DescendantInvalidationKind::Part) => {
+                    descendant_invalidations.parts.push(next_invalidation);
+                },
+                InvalidationKind::Descendant(DescendantInvalidationKind::Slotted) => {
+                    descendant_invalidations
+                        .slotted_descendants
+                        .push(next_invalidation);
+                },
+                InvalidationKind::Sibling => {
+                    sibling_invalidations.push(next_invalidation);
+                },
+            }
+        }
+
+        SingleInvalidationResult {
+            invalidated_self,
+            matched: true,
+        }
+    }
+}
diff --git a/servo/components/style/invalidation/element/mod.rs b/servo/components/style/invalidation/element/mod.rs
new file mode 100644
index 0000000000..0ddb9f1863
--- /dev/null
+++ b/servo/components/style/invalidation/element/mod.rs
@@ -0,0 +1,13 @@
+/* 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/. */
+
+//! Invalidation of element styles due to attribute or style changes.
+
+pub mod document_state;
+pub mod element_wrapper;
+pub mod invalidation_map;
+pub mod invalidator;
+pub mod relative_selector;
+pub mod restyle_hints;
+pub mod state_and_attributes;
diff --git a/servo/components/style/invalidation/element/relative_selector.rs b/servo/components/style/invalidation/element/relative_selector.rs
new file mode 100644
index 0000000000..ccb48e349f
--- /dev/null
+++ b/servo/components/style/invalidation/element/relative_selector.rs
@@ -0,0 +1,1164 @@
+/* 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/. */
+
+//! Invalidation of element styles relative selectors.
+
+use crate::data::ElementData;
+use crate::dom::{TElement, TNode};
+use crate::gecko_bindings::structs::ServoElementSnapshotTable;
+use crate::invalidation::element::element_wrapper::ElementWrapper;
+use crate::invalidation::element::invalidation_map::{
+    Dependency, DependencyInvalidationKind, NormalDependencyInvalidationKind,
+    RelativeDependencyInvalidationKind, RelativeSelectorInvalidationMap,
+};
+use crate::invalidation::element::invalidator::{
+    DescendantInvalidationLists, Invalidation, InvalidationProcessor, InvalidationResult,
+    InvalidationVector, SiblingTraversalMap, TreeStyleInvalidator,
+};
+use crate::invalidation::element::restyle_hints::RestyleHint;
+use crate::invalidation::element::state_and_attributes::{
+    check_dependency, dependency_may_be_relevant, invalidated_descendants, invalidated_self,
+    invalidated_sibling, push_invalidation, should_process_descendants,
+};
+use crate::stylist::{CascadeData, Stylist};
+use dom::ElementState;
+use fxhash::FxHashMap;
+use selectors::matching::{
+    matches_compound_selector_from, matches_selector, CompoundSelectorMatchingResult,
+    ElementSelectorFlags, MatchingContext, MatchingForInvalidation, MatchingMode,
+    NeedsSelectorFlags, QuirksMode, SelectorCaches, VisitedHandlingMode,
+};
+use selectors::parser::{Combinator, SelectorKey};
+use selectors::OpaqueElement;
+use smallvec::SmallVec;
+use std::ops::DerefMut;
+
+/// Kind of DOM mutation this relative selector invalidation is being carried out in.
+#[derive(Clone, Copy)]
+pub enum DomMutationOperation {
+    /// Insertion operation, can cause side effect, but presumed already happened.
+    Insert,
+    /// Append operation, cannot cause side effect.
+    Append,
+    /// Removal operation, can cause side effect, but presumed already happened. Sibling relationships are destroyed.
+    Remove,
+    /// Invalidating for side effect of a DOM operation, for the previous sibling.
+    SideEffectPrevSibling,
+    /// Invalidating for side effect of a DOM operation, for the next sibling.
+    SideEffectNextSibling,
+}
+
+impl DomMutationOperation {
+    fn accept<E: TElement>(&self, d: &Dependency, e: E) -> bool {
+        match self {
+            Self::Insert | Self::Append | Self::Remove => {
+                e.relative_selector_search_direction().is_some()
+            },
+            // `:has(+ .a + .b)` with `.anchor + .a + .remove + .b` - `.a` would be present
+            // in the search path.
+            Self::SideEffectPrevSibling => {
+                e.relative_selector_search_direction().is_some() &&
+                    d.right_combinator_is_next_sibling()
+            },
+            // If an element is being removed and would cause next-sibling match to happen,
+            // e.g. `:has(+ .a)` with `.anchor + .remove + .a`, `.a` isn't yet searched
+            // for relative selector matching.
+            Self::SideEffectNextSibling => d.dependency_is_relative_with_single_next_sibling(),
+        }
+    }
+
+    fn is_side_effect(&self) -> bool {
+        match self {
+            Self::Insert | Self::Append | Self::Remove => false,
+            Self::SideEffectPrevSibling | Self::SideEffectNextSibling => true,
+        }
+    }
+}
+
+/// Context required to try and optimize away relative dependencies.
+struct OptimizationContext<'a, E: TElement> {
+    sibling_traversal_map: &'a SiblingTraversalMap<E>,
+    quirks_mode: QuirksMode,
+    operation: DomMutationOperation,
+}
+
+impl<'a, E: TElement> OptimizationContext<'a, E> {
+    fn can_be_ignored(
+        &self,
+        is_subtree: bool,
+        element: E,
+        host: Option<OpaqueElement>,
+        dependency: &Dependency,
+    ) -> bool {
+        if is_subtree {
+            // Subtree elements don't have unaffected sibling to look at.
+            return false;
+        }
+        debug_assert!(
+            matches!(
+                dependency.invalidation_kind(),
+                DependencyInvalidationKind::Relative(..)
+            ),
+            "Non-relative selector being evaluated for optimization"
+        );
+        // This optimization predecates on the fact that there may be a sibling that can readily
+        // "take over" this element.
+        let sibling = match self.sibling_traversal_map.prev_sibling_for(&element) {
+            None => {
+                if matches!(self.operation, DomMutationOperation::Append) {
+                    return false;
+                }
+                match self.sibling_traversal_map.next_sibling_for(&element) {
+                    Some(s) => s,
+                    None => return false,
+                }
+            },
+            Some(s) => s,
+        };
+        {
+            // Run through the affected compund.
+            let mut iter = dependency.selector.iter_from(dependency.selector_offset);
+            while let Some(c) = iter.next() {
+                if c.has_indexed_selector_in_subject() {
+                    // We do not calculate indices during invalidation as they're wasteful - as a side effect,
+                    // such selectors always return true, breaking this optimization. Note that we only check
+                    // this compound only because the check to skip compares against this element's sibling.
+                    // i.e. Given `:has(:nth-child(2) .foo)`, we'd try to find `.foo`'s sibling, which
+                    // shares `:nth-child` up the selector.
+                    return false;
+                }
+            }
+        }
+        let is_rightmost = dependency.selector_offset == 0;
+        if !is_rightmost {
+            let combinator = dependency
+                .selector
+                .combinator_at_match_order(dependency.selector_offset - 1);
+            if combinator.is_ancestor() {
+                // We can safely ignore these, since we're about to traverse the
+                // rest of the affected tree anyway to find the rightmost invalidated element.
+                return true;
+            }
+            if combinator.is_sibling() && matches!(self.operation, DomMutationOperation::Append) {
+                // If we're in the subtree, same argument applies as ancestor combinator case.
+                // If we're at the top of the DOM tree being mutated, we can ignore it if the
+                // operation is append - we know we'll cover all the later siblings and their descendants.
+                return true;
+            }
+        }
+        let mut caches = SelectorCaches::default();
+        let mut matching_context = MatchingContext::new(
+            MatchingMode::Normal,
+            None,
+            &mut caches,
+            self.quirks_mode,
+            NeedsSelectorFlags::No,
+            MatchingForInvalidation::Yes,
+        );
+        matching_context.current_host = host;
+        let sibling_matches = matches_selector(
+            &dependency.selector,
+            dependency.selector_offset,
+            None,
+            &sibling,
+            &mut matching_context,
+        );
+        if sibling_matches {
+            // Remember that at this point, we know that the combinator to the right of this
+            // compound is a sibling combinator. Effectively, we've found a standin for the
+            // element we're mutating.
+            // e.g. Given `:has(... .a ~ .b ...)`, we're the mutating element matching `... .a`,
+            // if we find a sibling that matches the `... .a`, it can stand in for us.
+            debug_assert!(dependency.parent.is_some(), "No relative selector outer dependency?");
+            return dependency.parent.as_ref().map_or(false, |par| {
+                // ... However, if the standin sibling can be the anchor, we can't skip it, since
+                // that sibling should be invlidated to become the anchor.
+                !matches_selector(
+                    &par.selector,
+                    par.selector_offset,
+                    None,
+                    &sibling,
+                    &mut matching_context
+                )
+            });
+        }
+        // Ok, there's no standin element - but would this element have matched the upstream
+        // selector anyway? If we don't, either the match exists somewhere far from us
+        // (In which case our mutation doesn't really matter), or it doesn't exist at all,
+        // so we can just skip the invalidation.
+        let (combinator, prev_offset) = {
+            let mut iter = dependency.selector.iter_from(dependency.selector_offset);
+            let mut o = dependency.selector_offset;
+            while iter.next().is_some() {
+                o += 1;
+            }
+            let combinator = iter.next_sequence();
+            o += 1;
+            debug_assert!(
+                combinator.is_some(),
+                "Should at least see a relative combinator"
+            );
+            (combinator.unwrap(), o)
+        };
+        if combinator.is_sibling() {
+            if prev_offset >= dependency.selector.len() - 1 {
+                // Hit the relative combinator - we don't have enough information to
+                // see if there's going to be a downstream match.
+                return false;
+            }
+            if matches!(self.operation, DomMutationOperation::Remove) {
+                // This is sad :( The sibling relation of a removed element is lost, and we don't
+                // propagate sibling traversal map to selector matching context, so we need to do
+                // manual matching here. TODO(dshin): Worth changing selector matching for this?
+
+                // Try matching this compound, then...
+                // Note: We'll not hit the leftmost sequence (Since we would have returned early
+                // if we'd hit the relative selector anchor).
+                if matches!(
+                    matches_compound_selector_from(
+                        &dependency.selector,
+                        dependency.selector.len() - prev_offset + 1,
+                        &mut matching_context,
+                        &element
+                    ),
+                    CompoundSelectorMatchingResult::NotMatched
+                ) {
+                    return true;
+                }
+
+                // ... Match the rest of the selector, manually traversing.
+                let mut prev_sibling = self.sibling_traversal_map.prev_sibling_for(&element);
+                while let Some(sib) = prev_sibling {
+                    if matches_selector(
+                        &dependency.selector,
+                        prev_offset,
+                        None,
+                        &sib,
+                        &mut matching_context,
+                    ) {
+                        return false;
+                    }
+                    if matches!(combinator, Combinator::NextSibling) {
+                        break;
+                    }
+                    prev_sibling = self.sibling_traversal_map.prev_sibling_for(&sib);
+                }
+                return true;
+            }
+        }
+        !matches_selector(
+            &dependency.selector,
+            dependency.selector_offset,
+            None,
+            &element,
+            &mut matching_context,
+        )
+    }
+}
+
+/// Overall invalidator for handling relative selector invalidations.
+pub struct RelativeSelectorInvalidator<'a, 'b, E>
+where
+    E: TElement + 'a,
+{
+    /// Element triggering the invalidation.
+    pub element: E,
+    /// Quirks mode of the current invalidation.
+    pub quirks_mode: QuirksMode,
+    /// Snapshot containing changes to invalidate against.
+    /// Can be None if it's a DOM mutation.
+    pub snapshot_table: Option<&'b ServoElementSnapshotTable>,
+    /// Callback to trigger when the subject element is invalidated.
+    pub invalidated: fn(E, &InvalidationResult),
+    /// The traversal map that should be used to process invalidations.
+    pub sibling_traversal_map: SiblingTraversalMap<E>,
+    /// Marker for 'a lifetime.
+    pub _marker: ::std::marker::PhantomData<&'a ()>,
+}
+
+struct RelativeSelectorInvalidation<'a> {
+    host: Option<OpaqueElement>,
+    kind: RelativeDependencyInvalidationKind,
+    dependency: &'a Dependency,
+}
+
+type ElementDependencies<'a> = SmallVec<[(Option<OpaqueElement>, &'a Dependency); 1]>;
+type Dependencies<'a, E> = SmallVec<[(E, ElementDependencies<'a>); 1]>;
+type AlreadyInvalidated<'a, E> = SmallVec<[(E, Option<OpaqueElement>, &'a Dependency); 2]>;
+
+/// Interface for collecting relative selector dependencies.
+pub struct RelativeSelectorDependencyCollector<'a, E>
+where
+    E: TElement,
+{
+    /// Dependencies that need to run through the normal invalidation that may generate
+    /// a relative selector invalidation.
+    dependencies: FxHashMap<E, ElementDependencies<'a>>,
+    /// Dependencies that created an invalidation right away.
+    invalidations: AlreadyInvalidated<'a, E>,
+    /// The top element in the subtree being invalidated.
+    top: E,
+    /// Optional context that will be used to try and skip invalidations
+    /// by running selector matches.
+    optimization_context: Option<OptimizationContext<'a, E>>,
+}
+
+type Invalidations<'a> = SmallVec<[RelativeSelectorInvalidation<'a>; 1]>;
+type InnerInvalidations<'a, E> = SmallVec<[(E, RelativeSelectorInvalidation<'a>); 1]>;
+
+struct ToInvalidate<'a, E: TElement + 'a> {
+    /// Dependencies to run through normal invalidator.
+    dependencies: Dependencies<'a, E>,
+    /// Dependencies already invalidated.
+    invalidations: Invalidations<'a>,
+}
+
+impl<'a, E: TElement + 'a> Default for ToInvalidate<'a, E> {
+    fn default() -> Self {
+        Self {
+            dependencies: Dependencies::default(),
+            invalidations: Invalidations::default(),
+        }
+    }
+}
+
+fn dependency_selectors_match(a: &Dependency, b: &Dependency) -> bool {
+    if a.invalidation_kind() != b.invalidation_kind() {
+        return false;
+    }
+    if SelectorKey::new(&a.selector) != SelectorKey::new(&b.selector) {
+        return false;
+    }
+    let mut a_parent = a.parent.as_ref();
+    let mut b_parent = b.parent.as_ref();
+    while let (Some(a_p), Some(b_p)) = (a_parent, b_parent) {
+        if SelectorKey::new(&a_p.selector) != SelectorKey::new(&b_p.selector) {
+            return false;
+        }
+        a_parent = a_p.parent.as_ref();
+        b_parent = b_p.parent.as_ref();
+    }
+    a_parent.is_none() && b_parent.is_none()
+}
+
+impl<'a, E> RelativeSelectorDependencyCollector<'a, E>
+where
+    E: TElement,
+{
+    fn new(top: E, optimization_context: Option<OptimizationContext<'a, E>>) -> Self {
+        Self {
+            dependencies: FxHashMap::default(),
+            invalidations: AlreadyInvalidated::default(),
+            top,
+            optimization_context,
+        }
+    }
+
+    fn insert_invalidation(
+        &mut self,
+        element: E,
+        dependency: &'a Dependency,
+        host: Option<OpaqueElement>,
+    ) {
+        match self
+            .invalidations
+            .iter_mut()
+            .find(|(_, _, d)| dependency_selectors_match(dependency, d))
+        {
+            Some((e, h, d)) => {
+                // Just keep one.
+                if d.selector_offset > dependency.selector_offset {
+                    (*e, *h, *d) = (element, host, dependency);
+                }
+            },
+            None => {
+                self.invalidations.push((element, host, dependency));
+            },
+        }
+    }
+
+    /// Add this dependency, if it is unique (i.e. Different outer dependency or same outer dependency
+    /// but requires a different invalidation traversal).
+    pub fn add_dependency(
+        &mut self,
+        dependency: &'a Dependency,
+        element: E,
+        host: Option<OpaqueElement>,
+    ) {
+        match dependency.invalidation_kind() {
+            DependencyInvalidationKind::Normal(..) => {
+                self.dependencies
+                    .entry(element)
+                    .and_modify(|v| v.push((host, dependency)))
+                    .or_default()
+                    .push((host, dependency));
+            },
+            DependencyInvalidationKind::Relative(kind) => {
+                debug_assert!(
+                    dependency.parent.is_some(),
+                    "Orphaned inner relative selector?"
+                );
+                if element != self.top &&
+                    matches!(
+                        kind,
+                        RelativeDependencyInvalidationKind::Parent |
+                            RelativeDependencyInvalidationKind::PrevSibling |
+                            RelativeDependencyInvalidationKind::EarlierSibling
+                    )
+                {
+                    return;
+                }
+                self.insert_invalidation(element, dependency, host);
+            },
+        };
+    }
+
+    /// Get the dependencies in a list format.
+    fn get(self) -> ToInvalidate<'a, E> {
+        let mut result = ToInvalidate::default();
+        for (element, host, dependency) in self.invalidations {
+            match dependency.invalidation_kind() {
+                DependencyInvalidationKind::Normal(_) => {
+                    unreachable!("Inner selector in invalidation?")
+                },
+                DependencyInvalidationKind::Relative(kind) => {
+                    if let Some(context) = self.optimization_context.as_ref() {
+                        if context.can_be_ignored(element != self.top, element, host, dependency) {
+                            continue;
+                        }
+                    }
+                    let dependency = dependency.parent.as_ref().unwrap();
+                    result.invalidations.push(RelativeSelectorInvalidation {
+                        kind,
+                        host,
+                        dependency,
+                    });
+                    // We move the invalidation up to the top of the subtree to avoid unnecessary traveral, but
+                    // this means that we need to take ancestor-earlier sibling invalidations into account, as
+                    // they'd look into earlier siblings of the top of the subtree as well.
+                    if element != self.top &&
+                        matches!(
+                            kind,
+                            RelativeDependencyInvalidationKind::AncestorEarlierSibling |
+                                RelativeDependencyInvalidationKind::AncestorPrevSibling
+                        )
+                    {
+                        result.invalidations.push(RelativeSelectorInvalidation {
+                            kind: if matches!(
+                                kind,
+                                RelativeDependencyInvalidationKind::AncestorPrevSibling
+                            ) {
+                                RelativeDependencyInvalidationKind::PrevSibling
+                            } else {
+                                RelativeDependencyInvalidationKind::EarlierSibling
+                            },
+                            host,
+                            dependency,
+                        });
+                    }
+                },
+            };
+        }
+        for (key, element_dependencies) in self.dependencies {
+            // At least for now, we don't try to optimize away dependencies emitted from nested selectors.
+            result.dependencies.push((key, element_dependencies));
+        }
+        result
+    }
+
+    fn collect_all_dependencies_for_element(
+        &mut self,
+        element: E,
+        scope: Option<OpaqueElement>,
+        quirks_mode: QuirksMode,
+        map: &'a RelativeSelectorInvalidationMap,
+        operation: DomMutationOperation,
+    ) {
+        element
+            .id()
+            .map(|v| match map.map.id_to_selector.get(v, quirks_mode) {
+                Some(v) => {
+                    for dependency in v {
+                        if !operation.accept(dependency, element) {
+                            continue;
+                        }
+                        self.add_dependency(dependency, element, scope);
+                    }
+                },
+                None => (),
+            });
+        element.each_class(|v| match map.map.class_to_selector.get(v, quirks_mode) {
+            Some(v) => {
+                for dependency in v {
+                    if !operation.accept(dependency, element) {
+                        continue;
+                    }
+                    self.add_dependency(dependency, element, scope);
+                }
+            },
+            None => (),
+        });
+        element.each_attr_name(
+            |v| match map.map.other_attribute_affecting_selectors.get(v) {
+                Some(v) => {
+                    for dependency in v {
+                        if !operation.accept(dependency, element) {
+                            continue;
+                        }
+                        self.add_dependency(dependency, element, scope);
+                    }
+                },
+                None => (),
+            },
+        );
+        let state = element.state();
+        map.map.state_affecting_selectors.lookup_with_additional(
+            element,
+            quirks_mode,
+            None,
+            &[],
+            ElementState::empty(),
+            |dependency| {
+                if !dependency.state.intersects(state) {
+                    return true;
+                }
+                if !operation.accept(&dependency.dep, element) {
+                    return true;
+                }
+                self.add_dependency(&dependency.dep, element, scope);
+                true
+            },
+        );
+
+        if let Some(v) = map.type_to_selector.get(element.local_name()) {
+            for dependency in v {
+                if !operation.accept(dependency, element) {
+                    continue;
+                }
+                self.add_dependency(dependency, element, scope);
+            }
+        }
+
+        for dependency in &map.any_to_selector {
+            if !operation.accept(dependency, element) {
+                continue;
+            }
+            self.add_dependency(dependency, element, scope);
+        }
+    }
+
+    fn is_empty(&self) -> bool {
+        self.invalidations.is_empty() && self.dependencies.is_empty()
+    }
+}
+
+impl<'a, 'b, E> RelativeSelectorInvalidator<'a, 'b, E>
+where
+    E: TElement + 'a,
+{
+    /// Gather relative selector dependencies for the given element, and invalidate as necessary.
+    #[inline(never)]
+    pub fn invalidate_relative_selectors_for_this<F>(
+        self,
+        stylist: &'a Stylist,
+        mut gather_dependencies: F,
+    ) where
+        F: FnMut(
+            &E,
+            Option<OpaqueElement>,
+            &'a CascadeData,
+            QuirksMode,
+            &mut RelativeSelectorDependencyCollector<'a, E>,
+        ),
+    {
+        let mut collector = RelativeSelectorDependencyCollector::new(self.element, None);
+        stylist.for_each_cascade_data_with_scope(self.element, |data, scope| {
+            let map = data.relative_selector_invalidation_map();
+            if !map.used {
+                return;
+            }
+            gather_dependencies(
+                &self.element,
+                scope.map(|e| e.opaque()),
+                data,
+                self.quirks_mode,
+                &mut collector,
+            );
+        });
+        if collector.is_empty() {
+            return;
+        }
+        self.invalidate_from_dependencies(collector.get());
+    }
+
+    /// Gather relative selector dependencies for the given element (And its subtree) that mutated, and invalidate as necessary.
+    #[inline(never)]
+    pub fn invalidate_relative_selectors_for_dom_mutation(
+        self,
+        subtree: bool,
+        stylist: &'a Stylist,
+        inherited_search_path: ElementSelectorFlags,
+        operation: DomMutationOperation,
+    ) {
+        let mut collector = RelativeSelectorDependencyCollector::new(
+            self.element,
+            if operation.is_side_effect() {
+                None
+            } else {
+                Some(OptimizationContext {
+                    sibling_traversal_map: &self.sibling_traversal_map,
+                    quirks_mode: self.quirks_mode,
+                    operation,
+                })
+            },
+        );
+        let mut traverse_subtree = false;
+        self.element.apply_selector_flags(inherited_search_path);
+        stylist.for_each_cascade_data_with_scope(self.element, |data, scope| {
+            let map = data.relative_selector_invalidation_map();
+            if !map.used {
+                return;
+            }
+            traverse_subtree |= map.needs_ancestors_traversal;
+            collector.collect_all_dependencies_for_element(
+                self.element,
+                scope.map(|e| e.opaque()),
+                self.quirks_mode,
+                map,
+                operation,
+            );
+        });
+
+        if subtree && traverse_subtree {
+            for node in self.element.as_node().dom_descendants() {
+                let descendant = match node.as_element() {
+                    Some(e) => e,
+                    None => continue,
+                };
+                descendant.apply_selector_flags(inherited_search_path);
+                stylist.for_each_cascade_data_with_scope(descendant, |data, scope| {
+                    let map = data.relative_selector_invalidation_map();
+                    if !map.used {
+                        return;
+                    }
+                    collector.collect_all_dependencies_for_element(
+                        descendant,
+                        scope.map(|e| e.opaque()),
+                        self.quirks_mode,
+                        map,
+                        operation,
+                    );
+                });
+            }
+        }
+        if collector.is_empty() {
+            return;
+        }
+        self.invalidate_from_dependencies(collector.get());
+    }
+
+    /// Carry out complete invalidation triggered by a relative selector invalidation.
+    fn invalidate_from_dependencies(&self, to_invalidate: ToInvalidate<'a, E>) {
+        for (element, dependencies) in to_invalidate.dependencies {
+            let mut selector_caches = SelectorCaches::default();
+            let mut processor = RelativeSelectorInnerInvalidationProcessor::new(
+                self.quirks_mode,
+                self.snapshot_table,
+                &dependencies,
+                &mut selector_caches,
+                &self.sibling_traversal_map,
+            );
+            TreeStyleInvalidator::new(element, None, &mut processor).invalidate();
+            for (element, invalidation) in processor.take_invalidations() {
+                self.invalidate_upwards(element, &invalidation);
+            }
+        }
+        for invalidation in to_invalidate.invalidations {
+            self.invalidate_upwards(self.element, &invalidation);
+        }
+    }
+
+    fn invalidate_upwards(&self, element: E, invalidation: &RelativeSelectorInvalidation<'a>) {
+        // This contains the main reason for why relative selector invalidation is handled
+        // separately - It travels ancestor and/or earlier sibling direction.
+        match invalidation.kind {
+            RelativeDependencyInvalidationKind::Parent => {
+                element.parent_element().map(|e| {
+                    if !Self::in_search_direction(
+                        &e,
+                        ElementSelectorFlags::RELATIVE_SELECTOR_SEARCH_DIRECTION_ANCESTOR,
+                    ) {
+                        return;
+                    }
+                    self.handle_anchor(e, invalidation.dependency, invalidation.host);
+                });
+            },
+            RelativeDependencyInvalidationKind::Ancestors => {
+                let mut parent = element.parent_element();
+                while let Some(par) = parent {
+                    if !Self::in_search_direction(
+                        &par,
+                        ElementSelectorFlags::RELATIVE_SELECTOR_SEARCH_DIRECTION_ANCESTOR,
+                    ) {
+                        return;
+                    }
+                    self.handle_anchor(par, invalidation.dependency, invalidation.host);
+                    parent = par.parent_element();
+                }
+            },
+            RelativeDependencyInvalidationKind::PrevSibling => {
+                self.sibling_traversal_map
+                    .prev_sibling_for(&element)
+                    .map(|e| {
+                        if !Self::in_search_direction(
+                            &e,
+                            ElementSelectorFlags::RELATIVE_SELECTOR_SEARCH_DIRECTION_SIBLING,
+                        ) {
+                            return;
+                        }
+                        self.handle_anchor(e, invalidation.dependency, invalidation.host);
+                    });
+            },
+            RelativeDependencyInvalidationKind::AncestorPrevSibling => {
+                let mut parent = element.parent_element();
+                while let Some(par) = parent {
+                    if !Self::in_search_direction(
+                        &par,
+                        ElementSelectorFlags::RELATIVE_SELECTOR_SEARCH_DIRECTION_ANCESTOR,
+                    ) {
+                        return;
+                    }
+                    par.prev_sibling_element().map(|e| {
+                        if !Self::in_search_direction(
+                            &e,
+                            ElementSelectorFlags::RELATIVE_SELECTOR_SEARCH_DIRECTION_SIBLING,
+                        ) {
+                            return;
+                        }
+                        self.handle_anchor(e, invalidation.dependency, invalidation.host);
+                    });
+                    parent = par.parent_element();
+                }
+            },
+            RelativeDependencyInvalidationKind::EarlierSibling => {
+                let mut sibling = self.sibling_traversal_map.prev_sibling_for(&element);
+                while let Some(sib) = sibling {
+                    if !Self::in_search_direction(
+                        &sib,
+                        ElementSelectorFlags::RELATIVE_SELECTOR_SEARCH_DIRECTION_SIBLING,
+                    ) {
+                        return;
+                    }
+                    self.handle_anchor(sib, invalidation.dependency, invalidation.host);
+                    sibling = sib.prev_sibling_element();
+                }
+            },
+            RelativeDependencyInvalidationKind::AncestorEarlierSibling => {
+                let mut parent = element.parent_element();
+                while let Some(par) = parent {
+                    if !Self::in_search_direction(
+                        &par,
+                        ElementSelectorFlags::RELATIVE_SELECTOR_SEARCH_DIRECTION_ANCESTOR,
+                    ) {
+                        return;
+                    }
+                    let mut sibling = par.prev_sibling_element();
+                    while let Some(sib) = sibling {
+                        if !Self::in_search_direction(
+                            &sib,
+                            ElementSelectorFlags::RELATIVE_SELECTOR_SEARCH_DIRECTION_SIBLING,
+                        ) {
+                            return;
+                        }
+                        self.handle_anchor(sib, invalidation.dependency, invalidation.host);
+                        sibling = sib.prev_sibling_element();
+                    }
+                    parent = par.parent_element();
+                }
+            },
+        }
+    }
+
+    /// Is this element in the direction of the given relative selector search path?
+    fn in_search_direction(element: &E, desired: ElementSelectorFlags) -> bool {
+        if let Some(direction) = element.relative_selector_search_direction() {
+            direction.intersects(desired)
+        } else {
+            false
+        }
+    }
+
+    /// Handle a potential relative selector anchor.
+    fn handle_anchor(
+        &self,
+        element: E,
+        outer_dependency: &Dependency,
+        host: Option<OpaqueElement>,
+    ) {
+        let is_rightmost = Self::is_subject(outer_dependency);
+        if (is_rightmost &&
+            !element.has_selector_flags(ElementSelectorFlags::ANCHORS_RELATIVE_SELECTOR)) ||
+            (!is_rightmost &&
+                !element.has_selector_flags(
+                    ElementSelectorFlags::ANCHORS_RELATIVE_SELECTOR_NON_SUBJECT,
+                ))
+        {
+            // If it was never a relative selector anchor, don't bother.
+            return;
+        }
+        let mut selector_caches = SelectorCaches::default();
+        let matching_context = MatchingContext::<'_, E::Impl>::new_for_visited(
+            MatchingMode::Normal,
+            None,
+            &mut selector_caches,
+            VisitedHandlingMode::AllLinksVisitedAndUnvisited,
+            self.quirks_mode,
+            NeedsSelectorFlags::No,
+            MatchingForInvalidation::Yes,
+        );
+        let mut data = match element.mutate_data() {
+            Some(data) => data,
+            None => return,
+        };
+        let mut processor = RelativeSelectorOuterInvalidationProcessor {
+            element,
+            host,
+            data: data.deref_mut(),
+            dependency: &*outer_dependency,
+            matching_context,
+            traversal_map: &self.sibling_traversal_map,
+        };
+        let result = TreeStyleInvalidator::new(element, None, &mut processor).invalidate();
+        (self.invalidated)(element, &result);
+    }
+
+    /// Does this relative selector dependency have its relative selector in the subject position?
+    fn is_subject(outer_dependency: &Dependency) -> bool {
+        debug_assert!(
+            matches!(
+                outer_dependency.invalidation_kind(),
+                DependencyInvalidationKind::Normal(_)
+            ),
+            "Outer selector of relative selector is relative?"
+        );
+
+        if let Some(p) = outer_dependency.parent.as_ref() {
+            if !Self::is_subject(p.as_ref()) {
+                // Not subject in outer selector.
+                return false;
+            }
+        }
+        outer_dependency.selector.is_rightmost(outer_dependency.selector_offset)
+    }
+}
+
+/// Blindly invalidate everything outside of a relative selector.
+/// Consider `:is(.a :has(.b) .c ~ .d) ~ .e .f`, where .b gets deleted.
+/// Since the tree mutated, we cannot rely on snapshots.
+pub struct RelativeSelectorOuterInvalidationProcessor<'a, 'b, E: TElement> {
+    /// Element being invalidated.
+    pub element: E,
+    /// The current shadow host, if any.
+    pub host: Option<OpaqueElement>,
+    /// Data for the element being invalidated.
+    pub data: &'a mut ElementData,
+    /// Dependency to be processed.
+    pub dependency: &'b Dependency,
+    /// Matching context to use for invalidation.
+    pub matching_context: MatchingContext<'a, E::Impl>,
+    /// Traversal map for this invalidation.
+    pub traversal_map: &'a SiblingTraversalMap<E>,
+}
+
+impl<'a, 'b: 'a, E: 'a> InvalidationProcessor<'b, 'a, E>
+    for RelativeSelectorOuterInvalidationProcessor<'a, 'b, E>
+where
+    E: TElement,
+{
+    fn invalidates_on_pseudo_element(&self) -> bool {
+        true
+    }
+
+    fn check_outer_dependency(&mut self, _dependency: &Dependency, _element: E) -> bool {
+        // At this point, we know a relative selector invalidated, and are ignoring them.
+        true
+    }
+
+    fn matching_context(&mut self) -> &mut MatchingContext<'a, E::Impl> {
+        &mut self.matching_context
+    }
+
+    fn sibling_traversal_map(&self) -> &SiblingTraversalMap<E> {
+        self.traversal_map
+    }
+
+    fn collect_invalidations(
+        &mut self,
+        element: E,
+        _self_invalidations: &mut InvalidationVector<'b>,
+        descendant_invalidations: &mut DescendantInvalidationLists<'b>,
+        sibling_invalidations: &mut InvalidationVector<'b>,
+    ) -> bool {
+        debug_assert_eq!(element, self.element);
+        debug_assert!(
+            self.matching_context.matching_for_invalidation(),
+            "Not matching for invalidation?"
+        );
+
+        // Ok, this element can potentially an anchor to the given dependency.
+        // Before we do the potentially-costly ancestor/earlier sibling traversal,
+        // See if it can actuall be an anchor by trying to match the "rest" of the selector
+        // outside and to the left of `:has` in question.
+        // e.g. Element under consideration can only be the anchor to `:has` in
+        // `.foo .bar ~ .baz:has()`, iff it matches `.foo .bar ~ .baz`.
+        let invalidated_self = {
+            let mut d = self.dependency;
+            loop {
+                debug_assert!(
+                    matches!(
+                        d.invalidation_kind(),
+                        DependencyInvalidationKind::Normal(_)
+                    ),
+                    "Unexpected outer relative dependency"
+                );
+                if !dependency_may_be_relevant(d, &element, false) {
+                    break false;
+                }
+                if !matches_selector(
+                    &d.selector,
+                    d.selector_offset,
+                    None,
+                    &element,
+                    self.matching_context(),
+                ) {
+                    break false;
+                }
+                let invalidation_kind = d.normal_invalidation_kind();
+                if matches!(invalidation_kind, NormalDependencyInvalidationKind::Element) {
+                    if let Some(ref parent) = d.parent {
+                        d = parent;
+                        continue;
+                    }
+                    break true;
+                }
+                debug_assert_ne!(d.selector_offset, 0);
+                debug_assert_ne!(d.selector_offset, d.selector.len());
+                let invalidation = Invalidation::new(&d, self.host);
+                break push_invalidation(
+                    invalidation,
+                    invalidation_kind,
+                    descendant_invalidations,
+                    sibling_invalidations
+                );
+            }
+        };
+
+        if invalidated_self {
+            self.data.hint.insert(RestyleHint::RESTYLE_SELF);
+        }
+        invalidated_self
+    }
+
+    fn should_process_descendants(&mut self, element: E) -> bool {
+        if element == self.element {
+            return should_process_descendants(&self.data);
+        }
+
+        match element.borrow_data() {
+            Some(d) => should_process_descendants(&d),
+            None => return false,
+        }
+    }
+
+    fn recursion_limit_exceeded(&mut self, _element: E) {
+        unreachable!("Unexpected recursion limit");
+    }
+
+    fn invalidated_descendants(&mut self, element: E, child: E) {
+        invalidated_descendants(element, child)
+    }
+
+    fn invalidated_self(&mut self, element: E) {
+        debug_assert_ne!(element, self.element);
+        invalidated_self(element);
+    }
+
+    fn invalidated_sibling(&mut self, element: E, of: E) {
+        debug_assert_ne!(element, self.element);
+        invalidated_sibling(element, of);
+    }
+}
+
+/// Invalidation for the selector(s) inside a relative selector.
+pub struct RelativeSelectorInnerInvalidationProcessor<'a, 'b, 'c, E>
+where
+    E: TElement + 'a,
+{
+    /// Matching context to be used.
+    matching_context: MatchingContext<'b, E::Impl>,
+    /// Table of snapshots.
+    snapshot_table: Option<&'c ServoElementSnapshotTable>,
+    /// Incoming dependencies to be processed.
+    dependencies: &'c ElementDependencies<'a>,
+    /// Generated invalidations.
+    invalidations: InnerInvalidations<'a, E>,
+    /// Traversal map for this invalidation.
+    traversal_map: &'b SiblingTraversalMap<E>,
+}
+
+impl<'a, 'b, 'c, E> RelativeSelectorInnerInvalidationProcessor<'a, 'b, 'c, E>
+where
+    E: TElement + 'a,
+{
+    fn new(
+        quirks_mode: QuirksMode,
+        snapshot_table: Option<&'c ServoElementSnapshotTable>,
+        dependencies: &'c ElementDependencies<'a>,
+        selector_caches: &'b mut SelectorCaches,
+        traversal_map: &'b SiblingTraversalMap<E>,
+    ) -> Self {
+        let matching_context = MatchingContext::new_for_visited(
+            MatchingMode::Normal,
+            None,
+            selector_caches,
+            VisitedHandlingMode::AllLinksVisitedAndUnvisited,
+            quirks_mode,
+            NeedsSelectorFlags::No,
+            MatchingForInvalidation::Yes,
+        );
+        Self {
+            matching_context,
+            snapshot_table,
+            dependencies,
+            invalidations: InnerInvalidations::default(),
+            traversal_map,
+        }
+    }
+
+    fn note_dependency(
+        &mut self,
+        element: E,
+        scope: Option<OpaqueElement>,
+        dependency: &'a Dependency,
+        descendant_invalidations: &mut DescendantInvalidationLists<'a>,
+        sibling_invalidations: &mut InvalidationVector<'a>,
+    ) {
+        match dependency.invalidation_kind() {
+            DependencyInvalidationKind::Normal(_) => (),
+            DependencyInvalidationKind::Relative(kind) => {
+                self.found_relative_selector_invalidation(element, kind, dependency);
+                return;
+            },
+        }
+        if matches!(
+            dependency.normal_invalidation_kind(),
+            NormalDependencyInvalidationKind::Element
+        ) {
+            // Ok, keep heading outwards.
+            debug_assert!(
+                dependency.parent.is_some(),
+                "Orphaned inner selector dependency?"
+            );
+            if let Some(parent) = dependency.parent.as_ref() {
+                self.note_dependency(
+                    element,
+                    scope,
+                    parent,
+                    descendant_invalidations,
+                    sibling_invalidations,
+                );
+            }
+            return;
+        }
+        let invalidation = Invalidation::new(&dependency, scope);
+        match dependency.normal_invalidation_kind() {
+            NormalDependencyInvalidationKind::Descendants => {
+                // Descendant invalidations are simplified due to pseudo-elements not being available within the relative selector.
+                descendant_invalidations.dom_descendants.push(invalidation)
+            },
+            NormalDependencyInvalidationKind::Siblings => sibling_invalidations.push(invalidation),
+            _ => unreachable!(),
+        }
+    }
+
+    /// Take the generated invalidations.
+    fn take_invalidations(self) -> InnerInvalidations<'a, E> {
+        self.invalidations
+    }
+}
+
+impl<'a, 'b, 'c, E> InvalidationProcessor<'a, 'b, E>
+    for RelativeSelectorInnerInvalidationProcessor<'a, 'b, 'c, E>
+where
+    E: TElement + 'a,
+{
+    fn check_outer_dependency(&mut self, dependency: &Dependency, element: E) -> bool {
+        if let Some(snapshot_table) = self.snapshot_table {
+            let wrapper = ElementWrapper::new(element, snapshot_table);
+            return check_dependency(dependency, &element, &wrapper, &mut self.matching_context);
+        }
+        // Just invalidate if we don't have a snapshot.
+        true
+    }
+
+    fn matching_context(&mut self) -> &mut MatchingContext<'b, E::Impl> {
+        return &mut self.matching_context;
+    }
+
+    fn collect_invalidations(
+        &mut self,
+        element: E,
+        _self_invalidations: &mut InvalidationVector<'a>,
+        descendant_invalidations: &mut DescendantInvalidationLists<'a>,
+        sibling_invalidations: &mut InvalidationVector<'a>,
+    ) -> bool {
+        for (scope, dependency) in self.dependencies {
+            self.note_dependency(
+                element,
+                *scope,
+                dependency,
+                descendant_invalidations,
+                sibling_invalidations,
+            )
+        }
+        false
+    }
+
+    fn should_process_descendants(&mut self, _element: E) -> bool {
+        true
+    }
+
+    fn recursion_limit_exceeded(&mut self, _element: E) {
+        unreachable!("Unexpected recursion limit");
+    }
+
+    // Don't do anything for normal invalidations.
+    fn invalidated_self(&mut self, _element: E) {}
+    fn invalidated_sibling(&mut self, _sibling: E, _of: E) {}
+    fn invalidated_descendants(&mut self, _element: E, _child: E) {}
+
+    fn found_relative_selector_invalidation(
+        &mut self,
+        element: E,
+        kind: RelativeDependencyInvalidationKind,
+        dep: &'a Dependency,
+    ) {
+        debug_assert!(dep.parent.is_some(), "Orphaned inners selector?");
+        if element.relative_selector_search_direction().is_none() {
+            return;
+        }
+        self.invalidations.push((
+            element,
+            RelativeSelectorInvalidation {
+                host: self.matching_context.current_host,
+                kind,
+                dependency: dep.parent.as_ref().unwrap(),
+            },
+        ));
+    }
+
+    fn sibling_traversal_map(&self) -> &SiblingTraversalMap<E> {
+        &self.traversal_map
+    }
+}
diff --git a/servo/components/style/invalidation/element/restyle_hints.rs b/servo/components/style/invalidation/element/restyle_hints.rs
new file mode 100644
index 0000000000..fe89636e88
--- /dev/null
+++ b/servo/components/style/invalidation/element/restyle_hints.rs
@@ -0,0 +1,191 @@
+/* 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/. */
+
+//! Restyle hints: an optimization to avoid unnecessarily matching selectors.
+
+use crate::traversal_flags::TraversalFlags;
+
+bitflags! {
+    /// The kind of restyle we need to do for a given element.
+    #[repr(C)]
+    #[derive(Clone, Copy, Debug)]
+    pub struct RestyleHint: u16 {
+        /// Do a selector match of the element.
+        const RESTYLE_SELF = 1 << 0;
+
+        /// Do a selector match of the element's pseudo-elements. Always to be combined with
+        /// RESTYLE_SELF.
+        const RESTYLE_PSEUDOS = 1 << 1;
+
+        /// Do a selector match if the element is a pseudo-element.
+        const RESTYLE_SELF_IF_PSEUDO = 1 << 2;
+
+        /// Do a selector match of the element's descendants.
+        const RESTYLE_DESCENDANTS = 1 << 3;
+
+        /// Recascade the current element.
+        const RECASCADE_SELF = 1 << 4;
+
+        /// Recascade the current element if it inherits any reset style.
+        const RECASCADE_SELF_IF_INHERIT_RESET_STYLE = 1 << 5;
+
+        /// Recascade all descendant elements.
+        const RECASCADE_DESCENDANTS = 1 << 6;
+
+        /// Replace the style data coming from CSS transitions without updating
+        /// any other style data. This hint is only processed in animation-only
+        /// traversal which is prior to normal traversal.
+        const RESTYLE_CSS_TRANSITIONS = 1 << 7;
+
+        /// Replace the style data coming from CSS animations without updating
+        /// any other style data. This hint is only processed in animation-only
+        /// traversal which is prior to normal traversal.
+        const RESTYLE_CSS_ANIMATIONS = 1 << 8;
+
+        /// Don't re-run selector-matching on the element, only the style
+        /// attribute has changed, and this change didn't have any other
+        /// dependencies.
+        const RESTYLE_STYLE_ATTRIBUTE = 1 << 9;
+
+        /// Replace the style data coming from SMIL animations without updating
+        /// any other style data. This hint is only processed in animation-only
+        /// traversal which is prior to normal traversal.
+        const RESTYLE_SMIL = 1 << 10;
+    }
+}
+
+impl RestyleHint {
+    /// Creates a new `RestyleHint` indicating that the current element and all
+    /// its descendants must be fully restyled.
+    pub fn restyle_subtree() -> Self {
+        RestyleHint::RESTYLE_SELF | RestyleHint::RESTYLE_DESCENDANTS
+    }
+
+    /// Creates a new `RestyleHint` indicating that the current element and all
+    /// its descendants must be recascaded.
+    pub fn recascade_subtree() -> Self {
+        RestyleHint::RECASCADE_SELF | RestyleHint::RECASCADE_DESCENDANTS
+    }
+
+    /// Returns whether this hint invalidates the element and all its
+    /// descendants.
+    pub fn contains_subtree(&self) -> bool {
+        self.contains(Self::restyle_subtree())
+    }
+
+    /// Returns whether we'll recascade all of the descendants.
+    pub fn will_recascade_subtree(&self) -> bool {
+        self.contains_subtree() || self.contains(Self::recascade_subtree())
+    }
+
+    /// Returns whether we need to restyle this element.
+    pub fn has_non_animation_invalidations(&self) -> bool {
+        !(*self & !Self::for_animations()).is_empty()
+    }
+
+    /// Propagates this restyle hint to a child element.
+    pub fn propagate(&mut self, traversal_flags: &TraversalFlags) -> Self {
+        use std::mem;
+
+        // In the middle of an animation only restyle, we don't need to
+        // propagate any restyle hints, and we need to remove ourselves.
+        if traversal_flags.for_animation_only() {
+            self.remove_animation_hints();
+            return Self::empty();
+        }
+
+        debug_assert!(
+            !self.has_animation_hint(),
+            "There should not be any animation restyle hints \
+             during normal traversal"
+        );
+
+        // Else we should clear ourselves, and return the propagated hint.
+        mem::replace(self, Self::empty()).propagate_for_non_animation_restyle()
+    }
+
+    /// Returns a new `RestyleHint` appropriate for children of the current element.
+    fn propagate_for_non_animation_restyle(&self) -> Self {
+        if self.contains(RestyleHint::RESTYLE_DESCENDANTS) {
+            return Self::restyle_subtree();
+        }
+        let mut result = Self::empty();
+        if self.contains(RestyleHint::RESTYLE_PSEUDOS) {
+            result |= Self::RESTYLE_SELF_IF_PSEUDO;
+        }
+        if self.contains(RestyleHint::RECASCADE_DESCENDANTS) {
+            result |= Self::recascade_subtree();
+        }
+        result
+    }
+
+    /// Returns a hint that contains all the replacement hints.
+    pub fn replacements() -> Self {
+        RestyleHint::RESTYLE_STYLE_ATTRIBUTE | Self::for_animations()
+    }
+
+    /// The replacements for the animation cascade levels.
+    #[inline]
+    pub fn for_animations() -> Self {
+        RestyleHint::RESTYLE_SMIL |
+            RestyleHint::RESTYLE_CSS_ANIMATIONS |
+            RestyleHint::RESTYLE_CSS_TRANSITIONS
+    }
+
+    /// Returns whether the hint specifies that an animation cascade level must
+    /// be replaced.
+    #[inline]
+    pub fn has_animation_hint(&self) -> bool {
+        self.intersects(Self::for_animations())
+    }
+
+    /// Returns whether the hint specifies that an animation cascade level must
+    /// be replaced.
+    #[inline]
+    pub fn has_animation_hint_or_recascade(&self) -> bool {
+        self.intersects(
+            Self::for_animations() |
+                Self::RECASCADE_SELF |
+                Self::RECASCADE_SELF_IF_INHERIT_RESET_STYLE,
+        )
+    }
+
+    /// Returns whether the hint specifies some restyle work other than an
+    /// animation cascade level replacement.
+    #[inline]
+    pub fn has_non_animation_hint(&self) -> bool {
+        !(*self & !Self::for_animations()).is_empty()
+    }
+
+    /// Returns whether the hint specifies that some cascade levels must be
+    /// replaced.
+    #[inline]
+    pub fn has_replacements(&self) -> bool {
+        self.intersects(Self::replacements())
+    }
+
+    /// Removes all of the animation-related hints.
+    #[inline]
+    pub fn remove_animation_hints(&mut self) {
+        self.remove(Self::for_animations());
+
+        // While RECASCADE_SELF is not animation-specific, we only ever add and process it during
+        // traversal.  If we are here, removing animation hints, then we are in an animation-only
+        // traversal, and we know that any RECASCADE_SELF flag must have been set due to changes in
+        // inherited values after restyling for animations, and thus we want to remove it so that
+        // we don't later try to restyle the element during a normal restyle.
+        // (We could have separate RECASCADE_SELF_NORMAL and RECASCADE_SELF_ANIMATIONS flags to
+        // make it clear, but this isn't currently necessary.)
+        self.remove(Self::RECASCADE_SELF | Self::RECASCADE_SELF_IF_INHERIT_RESET_STYLE);
+    }
+}
+
+impl Default for RestyleHint {
+    fn default() -> Self {
+        Self::empty()
+    }
+}
+
+#[cfg(feature = "servo")]
+malloc_size_of_is_0!(RestyleHint);
diff --git a/servo/components/style/invalidation/element/state_and_attributes.rs b/servo/components/style/invalidation/element/state_and_attributes.rs
new file mode 100644
index 0000000000..1c58cddf1e
--- /dev/null
+++ b/servo/components/style/invalidation/element/state_and_attributes.rs
@@ -0,0 +1,601 @@
+/* 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/. */
+
+//! An invalidation processor for style changes due to state and attribute
+//! changes.
+
+use crate::context::SharedStyleContext;
+use crate::data::ElementData;
+use crate::dom::{TElement, TNode};
+use crate::invalidation::element::element_wrapper::{ElementSnapshot, ElementWrapper};
+use crate::invalidation::element::invalidation_map::*;
+use crate::invalidation::element::invalidator::{
+    DescendantInvalidationLists, InvalidationVector, SiblingTraversalMap,
+};
+use crate::invalidation::element::invalidator::{Invalidation, InvalidationProcessor};
+use crate::invalidation::element::restyle_hints::RestyleHint;
+use crate::selector_map::SelectorMap;
+use crate::selector_parser::Snapshot;
+use crate::stylesheets::origin::OriginSet;
+use crate::{Atom, WeakAtom};
+use dom::ElementState;
+use selectors::attr::CaseSensitivity;
+use selectors::matching::{
+    matches_selector, MatchingContext, MatchingForInvalidation, MatchingMode, NeedsSelectorFlags,
+    SelectorCaches, VisitedHandlingMode,
+};
+use smallvec::SmallVec;
+
+/// The collector implementation.
+struct Collector<'a, 'b: 'a, 'selectors: 'a, E>
+where
+    E: TElement,
+{
+    element: E,
+    wrapper: ElementWrapper<'b, E>,
+    snapshot: &'a Snapshot,
+    matching_context: &'a mut MatchingContext<'b, E::Impl>,
+    lookup_element: E,
+    removed_id: Option<&'a WeakAtom>,
+    added_id: Option<&'a WeakAtom>,
+    classes_removed: &'a SmallVec<[Atom; 8]>,
+    classes_added: &'a SmallVec<[Atom; 8]>,
+    state_changes: ElementState,
+    descendant_invalidations: &'a mut DescendantInvalidationLists<'selectors>,
+    sibling_invalidations: &'a mut InvalidationVector<'selectors>,
+    invalidates_self: bool,
+}
+
+/// An invalidation processor for style changes due to state and attribute
+/// changes.
+pub struct StateAndAttrInvalidationProcessor<'a, 'b: 'a, E: TElement> {
+    shared_context: &'a SharedStyleContext<'b>,
+    element: E,
+    data: &'a mut ElementData,
+    matching_context: MatchingContext<'a, E::Impl>,
+    traversal_map: SiblingTraversalMap<E>,
+}
+
+impl<'a, 'b: 'a, E: TElement + 'b> StateAndAttrInvalidationProcessor<'a, 'b, E> {
+    /// Creates a new StateAndAttrInvalidationProcessor.
+    pub fn new(
+        shared_context: &'a SharedStyleContext<'b>,
+        element: E,
+        data: &'a mut ElementData,
+        selector_caches: &'a mut SelectorCaches,
+    ) -> Self {
+        let matching_context = MatchingContext::new_for_visited(
+            MatchingMode::Normal,
+            None,
+            selector_caches,
+            VisitedHandlingMode::AllLinksVisitedAndUnvisited,
+            shared_context.quirks_mode(),
+            NeedsSelectorFlags::No,
+            MatchingForInvalidation::Yes,
+        );
+
+        Self {
+            shared_context,
+            element,
+            data,
+            matching_context,
+            traversal_map: SiblingTraversalMap::default(),
+        }
+    }
+}
+
+/// Checks a dependency against a given element and wrapper, to see if something
+/// changed.
+pub fn check_dependency<E, W>(
+    dependency: &Dependency,
+    element: &E,
+    wrapper: &W,
+    context: &mut MatchingContext<'_, E::Impl>,
+) -> bool
+where
+    E: TElement,
+    W: selectors::Element<Impl = E::Impl>,
+{
+    let matches_now = matches_selector(
+        &dependency.selector,
+        dependency.selector_offset,
+        None,
+        element,
+        context,
+    );
+
+    let matched_then = matches_selector(
+        &dependency.selector,
+        dependency.selector_offset,
+        None,
+        wrapper,
+        context,
+    );
+
+    matched_then != matches_now
+}
+
+/// Whether we should process the descendants of a given element for style
+/// invalidation.
+pub fn should_process_descendants(data: &ElementData) -> bool {
+    !data.styles.is_display_none() && !data.hint.contains(RestyleHint::RESTYLE_DESCENDANTS)
+}
+
+/// Propagates the bits after invalidating a descendant child.
+pub fn propagate_dirty_bit_up_to<E>(ancestor: E, child: E)
+where
+    E: TElement,
+{
+    // The child may not be a flattened tree child of the current element,
+    // but may be arbitrarily deep.
+    //
+    // Since we keep the traversal flags in terms of the flattened tree,
+    // we need to propagate it as appropriate.
+    let mut current = child.traversal_parent();
+    while let Some(parent) = current.take() {
+        unsafe { parent.set_dirty_descendants() };
+        current = parent.traversal_parent();
+
+        if parent == ancestor {
+            return;
+        }
+    }
+    debug_assert!(
+        false,
+        "Should've found {:?} as an ancestor of {:?}",
+        ancestor, child
+    );
+}
+
+/// Propagates the bits after invalidating a descendant child, if needed.
+pub fn invalidated_descendants<E>(element: E, child: E)
+where
+    E: TElement,
+{
+    if !child.has_data() {
+        return;
+    }
+    propagate_dirty_bit_up_to(element, child)
+}
+
+/// Sets the appropriate restyle hint after invalidating the style of a given
+/// element.
+pub fn invalidated_self<E>(element: E) -> bool
+where
+    E: TElement,
+{
+    let mut data = match element.mutate_data() {
+        Some(data) => data,
+        None => return false,
+    };
+    data.hint.insert(RestyleHint::RESTYLE_SELF);
+    true
+}
+
+/// Sets the appropriate hint after invalidating the style of a sibling.
+pub fn invalidated_sibling<E>(element: E, of: E)
+where
+    E: TElement,
+{
+    debug_assert_eq!(
+        element.as_node().parent_node(),
+        of.as_node().parent_node(),
+        "Should be siblings"
+    );
+    if !invalidated_self(element) {
+        return;
+    }
+    if element.traversal_parent() != of.traversal_parent() {
+        let parent = element.as_node().parent_element_or_host();
+        debug_assert!(
+            parent.is_some(),
+            "How can we have siblings without parent nodes?"
+        );
+        if let Some(e) = parent {
+            propagate_dirty_bit_up_to(e, element)
+        }
+    }
+}
+
+impl<'a, 'b: 'a, E: 'a> InvalidationProcessor<'a, 'a, E>
+    for StateAndAttrInvalidationProcessor<'a, 'b, E>
+where
+    E: TElement,
+{
+    /// We need to invalidate style on pseudo-elements, in order to process
+    /// changes that could otherwise end up in ::before or ::after content being
+    /// generated, and invalidate lazy pseudo caches.
+    fn invalidates_on_pseudo_element(&self) -> bool {
+        true
+    }
+
+    fn check_outer_dependency(&mut self, dependency: &Dependency, element: E) -> bool {
+        // We cannot assert about `element` having a snapshot here (in fact it
+        // most likely won't), because it may be an arbitrary descendant or
+        // later-sibling of the element we started invalidating with.
+        let wrapper = ElementWrapper::new(element, &*self.shared_context.snapshot_map);
+        check_dependency(dependency, &element, &wrapper, &mut self.matching_context)
+    }
+
+    fn matching_context(&mut self) -> &mut MatchingContext<'a, E::Impl> {
+        &mut self.matching_context
+    }
+
+    fn sibling_traversal_map(&self) -> &SiblingTraversalMap<E> {
+        &self.traversal_map
+    }
+
+    fn collect_invalidations(
+        &mut self,
+        element: E,
+        _self_invalidations: &mut InvalidationVector<'a>,
+        descendant_invalidations: &mut DescendantInvalidationLists<'a>,
+        sibling_invalidations: &mut InvalidationVector<'a>,
+    ) -> bool {
+        debug_assert_eq!(element, self.element);
+        debug_assert!(element.has_snapshot(), "Why bothering?");
+
+        let wrapper = ElementWrapper::new(element, &*self.shared_context.snapshot_map);
+
+        let state_changes = wrapper.state_changes();
+        let Some(snapshot) = wrapper.snapshot() else {
+            return false;
+        };
+
+        if !snapshot.has_attrs() && state_changes.is_empty() {
+            return false;
+        }
+
+        let mut classes_removed = SmallVec::<[Atom; 8]>::new();
+        let mut classes_added = SmallVec::<[Atom; 8]>::new();
+        if snapshot.class_changed() {
+            // TODO(emilio): Do this more efficiently!
+            snapshot.each_class(|c| {
+                if !element.has_class(c, CaseSensitivity::CaseSensitive) {
+                    classes_removed.push(c.0.clone())
+                }
+            });
+
+            element.each_class(|c| {
+                if !snapshot.has_class(c, CaseSensitivity::CaseSensitive) {
+                    classes_added.push(c.0.clone())
+                }
+            })
+        }
+
+        let mut id_removed = None;
+        let mut id_added = None;
+        if snapshot.id_changed() {
+            let old_id = snapshot.id_attr();
+            let current_id = element.id();
+
+            if old_id != current_id {
+                id_removed = old_id;
+                id_added = current_id;
+            }
+        }
+
+        if log_enabled!(::log::Level::Debug) {
+            debug!("Collecting changes for: {:?}", element);
+            if !state_changes.is_empty() {
+                debug!(" > state: {:?}", state_changes);
+            }
+            if snapshot.id_changed() {
+                debug!(" > id changed: +{:?} -{:?}", id_added, id_removed);
+            }
+            if snapshot.class_changed() {
+                debug!(
+                    " > class changed: +{:?} -{:?}",
+                    classes_added, classes_removed
+                );
+            }
+            let mut attributes_changed = false;
+            snapshot.each_attr_changed(|_| {
+                attributes_changed = true;
+            });
+            if attributes_changed {
+                debug!(
+                    " > attributes changed, old: {}",
+                    snapshot.debug_list_attributes()
+                )
+            }
+        }
+
+        let lookup_element = if element.implemented_pseudo_element().is_some() {
+            element.pseudo_element_originating_element().unwrap()
+        } else {
+            element
+        };
+
+        let mut shadow_rule_datas = SmallVec::<[_; 3]>::new();
+        let matches_document_author_rules =
+            element.each_applicable_non_document_style_rule_data(|data, host| {
+                shadow_rule_datas.push((data, host.opaque()))
+            });
+
+        let invalidated_self = {
+            let mut collector = Collector {
+                wrapper,
+                lookup_element,
+                state_changes,
+                element,
+                snapshot: &snapshot,
+                matching_context: &mut self.matching_context,
+                removed_id: id_removed,
+                added_id: id_added,
+                classes_removed: &classes_removed,
+                classes_added: &classes_added,
+                descendant_invalidations,
+                sibling_invalidations,
+                invalidates_self: false,
+            };
+
+            let document_origins = if !matches_document_author_rules {
+                OriginSet::ORIGIN_USER_AGENT | OriginSet::ORIGIN_USER
+            } else {
+                OriginSet::all()
+            };
+
+            for (cascade_data, origin) in self.shared_context.stylist.iter_origins() {
+                if document_origins.contains(origin.into()) {
+                    collector
+                        .collect_dependencies_in_invalidation_map(cascade_data.invalidation_map());
+                }
+            }
+
+            for &(ref data, ref host) in &shadow_rule_datas {
+                collector.matching_context.current_host = Some(host.clone());
+                collector.collect_dependencies_in_invalidation_map(data.invalidation_map());
+            }
+
+            collector.invalidates_self
+        };
+
+        // If we generated a ton of descendant invalidations, it's probably not
+        // worth to go ahead and try to process them.
+        //
+        // Just restyle the descendants directly.
+        //
+        // This number is completely made-up, but the page that made us add this
+        // code generated 1960+ invalidations (bug 1420741).
+        //
+        // We don't look at slotted_descendants because those don't propagate
+        // down more than one level anyway.
+        if descendant_invalidations.dom_descendants.len() > 150 {
+            self.data.hint.insert(RestyleHint::RESTYLE_DESCENDANTS);
+        }
+
+        if invalidated_self {
+            self.data.hint.insert(RestyleHint::RESTYLE_SELF);
+        }
+
+        invalidated_self
+    }
+
+    fn should_process_descendants(&mut self, element: E) -> bool {
+        if element == self.element {
+            return should_process_descendants(&self.data);
+        }
+
+        match element.borrow_data() {
+            Some(d) => should_process_descendants(&d),
+            None => return false,
+        }
+    }
+
+    fn recursion_limit_exceeded(&mut self, element: E) {
+        if element == self.element {
+            self.data.hint.insert(RestyleHint::RESTYLE_DESCENDANTS);
+            return;
+        }
+
+        if let Some(mut data) = element.mutate_data() {
+            data.hint.insert(RestyleHint::RESTYLE_DESCENDANTS);
+        }
+    }
+
+    fn invalidated_descendants(&mut self, element: E, child: E) {
+        invalidated_descendants(element, child)
+    }
+
+    fn invalidated_self(&mut self, element: E) {
+        debug_assert_ne!(element, self.element);
+        invalidated_self(element);
+    }
+
+    fn invalidated_sibling(&mut self, element: E, of: E) {
+        debug_assert_ne!(element, self.element);
+        invalidated_sibling(element, of);
+    }
+}
+
+impl<'a, 'b, 'selectors, E> Collector<'a, 'b, 'selectors, E>
+where
+    E: TElement,
+    'selectors: 'a,
+{
+    fn collect_dependencies_in_invalidation_map(&mut self, map: &'selectors InvalidationMap) {
+        let quirks_mode = self.matching_context.quirks_mode();
+        let removed_id = self.removed_id;
+        if let Some(ref id) = removed_id {
+            if let Some(deps) = map.id_to_selector.get(id, quirks_mode) {
+                for dep in deps {
+                    self.scan_dependency(dep);
+                }
+            }
+        }
+
+        let added_id = self.added_id;
+        if let Some(ref id) = added_id {
+            if let Some(deps) = map.id_to_selector.get(id, quirks_mode) {
+                for dep in deps {
+                    self.scan_dependency(dep);
+                }
+            }
+        }
+
+        for class in self.classes_added.iter().chain(self.classes_removed.iter()) {
+            if let Some(deps) = map.class_to_selector.get(class, quirks_mode) {
+                for dep in deps {
+                    self.scan_dependency(dep);
+                }
+            }
+        }
+
+        self.snapshot.each_attr_changed(|attribute| {
+            if let Some(deps) = map.other_attribute_affecting_selectors.get(attribute) {
+                for dep in deps {
+                    self.scan_dependency(dep);
+                }
+            }
+        });
+
+        self.collect_state_dependencies(&map.state_affecting_selectors)
+    }
+
+    fn collect_state_dependencies(&mut self, map: &'selectors SelectorMap<StateDependency>) {
+        if self.state_changes.is_empty() {
+            return;
+        }
+        map.lookup_with_additional(
+            self.lookup_element,
+            self.matching_context.quirks_mode(),
+            self.removed_id,
+            self.classes_removed,
+            self.state_changes,
+            |dependency| {
+                if !dependency.state.intersects(self.state_changes) {
+                    return true;
+                }
+                self.scan_dependency(&dependency.dep);
+                true
+            },
+        );
+    }
+
+    /// Check whether a dependency should be taken into account.
+    #[inline]
+    fn check_dependency(&mut self, dependency: &Dependency) -> bool {
+        check_dependency(
+            dependency,
+            &self.element,
+            &self.wrapper,
+            &mut self.matching_context,
+        )
+    }
+
+    fn scan_dependency(&mut self, dependency: &'selectors Dependency) {
+        debug_assert!(
+            matches!(
+                dependency.invalidation_kind(),
+                DependencyInvalidationKind::Normal(_)
+            ),
+            "Found relative selector dependency"
+        );
+        debug!(
+            "TreeStyleInvalidator::scan_dependency({:?}, {:?})",
+            self.element, dependency
+        );
+
+        if !self.dependency_may_be_relevant(dependency) {
+            return;
+        }
+
+        if self.check_dependency(dependency) {
+            return self.note_dependency(dependency);
+        }
+    }
+
+    fn note_dependency(&mut self, dependency: &'selectors Dependency) {
+        debug_assert!(self.dependency_may_be_relevant(dependency));
+
+        let invalidation_kind = dependency.normal_invalidation_kind();
+        if matches!(invalidation_kind, NormalDependencyInvalidationKind::Element) {
+            if let Some(ref parent) = dependency.parent {
+                // We know something changed in the inner selector, go outwards
+                // now.
+                self.scan_dependency(parent);
+            } else {
+                self.invalidates_self = true;
+            }
+            return;
+        }
+
+        debug_assert_ne!(dependency.selector_offset, 0);
+        debug_assert_ne!(dependency.selector_offset, dependency.selector.len());
+
+        let invalidation =
+            Invalidation::new(&dependency, self.matching_context.current_host.clone());
+
+        self.invalidates_self |= push_invalidation(
+            invalidation,
+            invalidation_kind,
+            self.descendant_invalidations,
+            self.sibling_invalidations,
+        );
+    }
+
+    /// Returns whether `dependency` may cause us to invalidate the style of
+    /// more elements than what we've already invalidated.
+    fn dependency_may_be_relevant(&self, dependency: &Dependency) -> bool {
+        match dependency.normal_invalidation_kind() {
+            NormalDependencyInvalidationKind::Element => !self.invalidates_self,
+            NormalDependencyInvalidationKind::SlottedElements => {
+                self.element.is_html_slot_element()
+            },
+            NormalDependencyInvalidationKind::Parts => self.element.shadow_root().is_some(),
+            NormalDependencyInvalidationKind::ElementAndDescendants |
+            NormalDependencyInvalidationKind::Siblings |
+            NormalDependencyInvalidationKind::Descendants => true,
+        }
+    }
+}
+
+pub(crate) fn push_invalidation<'a>(
+    invalidation: Invalidation<'a>,
+    invalidation_kind: NormalDependencyInvalidationKind,
+    descendant_invalidations: &mut DescendantInvalidationLists<'a>,
+    sibling_invalidations: &mut InvalidationVector<'a>,
+) -> bool {
+    match invalidation_kind {
+        NormalDependencyInvalidationKind::Element => unreachable!(),
+        NormalDependencyInvalidationKind::ElementAndDescendants => {
+            descendant_invalidations.dom_descendants.push(invalidation);
+            true
+        },
+        NormalDependencyInvalidationKind::Descendants => {
+            descendant_invalidations.dom_descendants.push(invalidation);
+            false
+        },
+        NormalDependencyInvalidationKind::Siblings => {
+            sibling_invalidations.push(invalidation);
+            false
+        },
+        NormalDependencyInvalidationKind::Parts => {
+            descendant_invalidations.parts.push(invalidation);
+            false
+        },
+        NormalDependencyInvalidationKind::SlottedElements => {
+            descendant_invalidations
+                .slotted_descendants
+                .push(invalidation);
+            false
+        },
+    }
+}
+
+pub(crate) fn dependency_may_be_relevant<E: TElement>(
+    dependency: &Dependency,
+    element: &E,
+    already_invalidated_self: bool,
+) -> bool {
+    match dependency.normal_invalidation_kind() {
+        NormalDependencyInvalidationKind::Element => !already_invalidated_self,
+        NormalDependencyInvalidationKind::SlottedElements => element.is_html_slot_element(),
+        NormalDependencyInvalidationKind::Parts => element.shadow_root().is_some(),
+        NormalDependencyInvalidationKind::ElementAndDescendants |
+        NormalDependencyInvalidationKind::Siblings |
+        NormalDependencyInvalidationKind::Descendants => true,
+    }
+}
diff --git a/servo/components/style/invalidation/media_queries.rs b/servo/components/style/invalidation/media_queries.rs
new file mode 100644
index 0000000000..6928b29d3d
--- /dev/null
+++ b/servo/components/style/invalidation/media_queries.rs
@@ -0,0 +1,130 @@
+/* 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/. */
+
+//! Code related to the invalidation of media-query-affected rules.
+
+use crate::context::QuirksMode;
+use crate::media_queries::Device;
+use crate::shared_lock::SharedRwLockReadGuard;
+use crate::stylesheets::{DocumentRule, ImportRule, MediaRule};
+use crate::stylesheets::{NestedRuleIterationCondition, StylesheetContents, SupportsRule};
+use fxhash::FxHashSet;
+
+/// A key for a given media query result.
+///
+/// NOTE: It happens to be the case that all the media lists we care about
+/// happen to have a stable address, so we can just use an opaque pointer to
+/// represent them.
+///
+/// Also, note that right now when a rule or stylesheet is removed, we do a full
+/// style flush, so there's no need to worry about other item created with the
+/// same pointer address.
+///
+/// If this changes, though, we may need to remove the item from the cache if
+/// present before it goes away.
+#[derive(Clone, Copy, Debug, Eq, Hash, MallocSizeOf, PartialEq)]
+pub struct MediaListKey(usize);
+
+impl MediaListKey {
+    /// Create a MediaListKey from a raw usize.
+    pub fn from_raw(k: usize) -> Self {
+        MediaListKey(k)
+    }
+}
+
+/// A trait to get a given `MediaListKey` for a given item that can hold a
+/// `MediaList`.
+pub trait ToMediaListKey: Sized {
+    /// Get a `MediaListKey` for this item. This key needs to uniquely identify
+    /// the item.
+    fn to_media_list_key(&self) -> MediaListKey {
+        MediaListKey(self as *const Self as usize)
+    }
+}
+
+impl ToMediaListKey for StylesheetContents {}
+impl ToMediaListKey for ImportRule {}
+impl ToMediaListKey for MediaRule {}
+
+/// A struct that holds the result of a media query evaluation pass for the
+/// media queries that evaluated successfully.
+#[derive(Clone, Debug, MallocSizeOf, PartialEq)]
+pub struct EffectiveMediaQueryResults {
+    /// The set of media lists that matched last time.
+    set: FxHashSet<MediaListKey>,
+}
+
+impl EffectiveMediaQueryResults {
+    /// Trivially constructs an empty `EffectiveMediaQueryResults`.
+    pub fn new() -> Self {
+        Self {
+            set: FxHashSet::default(),
+        }
+    }
+
+    /// Resets the results, using an empty key.
+    pub fn clear(&mut self) {
+        self.set.clear()
+    }
+
+    /// Returns whether a given item was known to be effective when the results
+    /// were cached.
+    pub fn was_effective<T>(&self, item: &T) -> bool
+    where
+        T: ToMediaListKey,
+    {
+        self.set.contains(&item.to_media_list_key())
+    }
+
+    /// Notices that an effective item has been seen, and caches it as matching.
+    pub fn saw_effective<T>(&mut self, item: &T)
+    where
+        T: ToMediaListKey,
+    {
+        // NOTE(emilio): We can't assert that we don't cache the same item twice
+        // because of stylesheet reusing... shrug.
+        self.set.insert(item.to_media_list_key());
+    }
+}
+
+/// A filter that filters over effective rules, but allowing all potentially
+/// effective `@media` rules.
+pub struct PotentiallyEffectiveMediaRules;
+
+impl NestedRuleIterationCondition for PotentiallyEffectiveMediaRules {
+    fn process_import(
+        _: &SharedRwLockReadGuard,
+        _: &Device,
+        _: QuirksMode,
+        _: &ImportRule,
+    ) -> bool {
+        true
+    }
+
+    fn process_media(_: &SharedRwLockReadGuard, _: &Device, _: QuirksMode, _: &MediaRule) -> bool {
+        true
+    }
+
+    /// Whether we should process the nested rules in a given `@-moz-document` rule.
+    fn process_document(
+        guard: &SharedRwLockReadGuard,
+        device: &Device,
+        quirks_mode: QuirksMode,
+        rule: &DocumentRule,
+    ) -> bool {
+        use crate::stylesheets::EffectiveRules;
+        EffectiveRules::process_document(guard, device, quirks_mode, rule)
+    }
+
+    /// Whether we should process the nested rules in a given `@supports` rule.
+    fn process_supports(
+        guard: &SharedRwLockReadGuard,
+        device: &Device,
+        quirks_mode: QuirksMode,
+        rule: &SupportsRule,
+    ) -> bool {
+        use crate::stylesheets::EffectiveRules;
+        EffectiveRules::process_supports(guard, device, quirks_mode, rule)
+    }
+}
diff --git a/servo/components/style/invalidation/mod.rs b/servo/components/style/invalidation/mod.rs
new file mode 100644
index 0000000000..12b0d06853
--- /dev/null
+++ b/servo/components/style/invalidation/mod.rs
@@ -0,0 +1,10 @@
+/* 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/. */
+
+//! Different bits of code related to invalidating style.
+
+pub mod element;
+pub mod media_queries;
+pub mod stylesheets;
+pub mod viewport_units;
diff --git a/servo/components/style/invalidation/stylesheets.rs b/servo/components/style/invalidation/stylesheets.rs
new file mode 100644
index 0000000000..d845897aa4
--- /dev/null
+++ b/servo/components/style/invalidation/stylesheets.rs
@@ -0,0 +1,651 @@
+/* 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/. */
+
+//! A collection of invalidations due to changes in which stylesheets affect a
+//! document.
+
+#![deny(unsafe_code)]
+
+use crate::context::QuirksMode;
+use crate::dom::{TDocument, TElement, TNode};
+use crate::invalidation::element::element_wrapper::{ElementSnapshot, ElementWrapper};
+use crate::invalidation::element::restyle_hints::RestyleHint;
+use crate::media_queries::Device;
+use crate::selector_map::{MaybeCaseInsensitiveHashMap, PrecomputedHashMap};
+use crate::selector_parser::{SelectorImpl, Snapshot, SnapshotMap};
+use crate::shared_lock::SharedRwLockReadGuard;
+use crate::stylesheets::{CssRule, StylesheetInDocument};
+use crate::stylesheets::{EffectiveRules, EffectiveRulesIterator};
+use crate::values::AtomIdent;
+use crate::LocalName as SelectorLocalName;
+use crate::{Atom, ShrinkIfNeeded};
+use selectors::parser::{Component, LocalName, Selector};
+
+/// The kind of change that happened for a given rule.
+#[repr(u32)]
+#[derive(Clone, Copy, Debug, Eq, Hash, MallocSizeOf, PartialEq)]
+pub enum RuleChangeKind {
+    /// The rule was inserted.
+    Insertion,
+    /// The rule was removed.
+    Removal,
+    /// Some change in the rule which we don't know about, and could have made
+    /// the rule change in any way.
+    Generic,
+    /// A change in the declarations of a style rule.
+    StyleRuleDeclarations,
+}
+
+/// A style sheet invalidation represents a kind of element or subtree that may
+/// need to be restyled. Whether it represents a whole subtree or just a single
+/// element is determined by the given InvalidationKind in
+/// StylesheetInvalidationSet's maps.
+#[derive(Debug, Eq, Hash, MallocSizeOf, PartialEq)]
+enum Invalidation {
+    /// An element with a given id.
+    ID(AtomIdent),
+    /// An element with a given class name.
+    Class(AtomIdent),
+    /// An element with a given local name.
+    LocalName {
+        name: SelectorLocalName,
+        lower_name: SelectorLocalName,
+    },
+}
+
+impl Invalidation {
+    fn is_id(&self) -> bool {
+        matches!(*self, Invalidation::ID(..))
+    }
+
+    fn is_id_or_class(&self) -> bool {
+        matches!(*self, Invalidation::ID(..) | Invalidation::Class(..))
+    }
+}
+
+/// Whether we should invalidate just the element, or the whole subtree within
+/// it.
+#[derive(Clone, Copy, Debug, Eq, MallocSizeOf, Ord, PartialEq, PartialOrd)]
+enum InvalidationKind {
+    None = 0,
+    Element,
+    Scope,
+}
+
+impl std::ops::BitOrAssign for InvalidationKind {
+    #[inline]
+    fn bitor_assign(&mut self, other: Self) {
+        *self = std::cmp::max(*self, other);
+    }
+}
+
+impl InvalidationKind {
+    #[inline]
+    fn is_scope(self) -> bool {
+        matches!(self, Self::Scope)
+    }
+
+    #[inline]
+    fn add(&mut self, other: Option<&InvalidationKind>) {
+        if let Some(other) = other {
+            *self |= *other;
+        }
+    }
+}
+
+/// A set of invalidations due to stylesheet additions.
+///
+/// TODO(emilio): We might be able to do the same analysis for media query
+/// changes too (or even selector changes?).
+#[derive(Debug, Default, MallocSizeOf)]
+pub struct StylesheetInvalidationSet {
+    classes: MaybeCaseInsensitiveHashMap<Atom, InvalidationKind>,
+    ids: MaybeCaseInsensitiveHashMap<Atom, InvalidationKind>,
+    local_names: PrecomputedHashMap<SelectorLocalName, InvalidationKind>,
+    fully_invalid: bool,
+}
+
+impl StylesheetInvalidationSet {
+    /// Create an empty `StylesheetInvalidationSet`.
+    pub fn new() -> Self {
+        Default::default()
+    }
+
+    /// Mark the DOM tree styles' as fully invalid.
+    pub fn invalidate_fully(&mut self) {
+        debug!("StylesheetInvalidationSet::invalidate_fully");
+        self.clear();
+        self.fully_invalid = true;
+    }
+
+    fn shrink_if_needed(&mut self) {
+        if self.fully_invalid {
+            return;
+        }
+        self.classes.shrink_if_needed();
+        self.ids.shrink_if_needed();
+        self.local_names.shrink_if_needed();
+    }
+
+    /// Analyze the given stylesheet, and collect invalidations from their
+    /// rules, in order to avoid doing a full restyle when we style the document
+    /// next time.
+    pub fn collect_invalidations_for<S>(
+        &mut self,
+        device: &Device,
+        stylesheet: &S,
+        guard: &SharedRwLockReadGuard,
+    ) where
+        S: StylesheetInDocument,
+    {
+        debug!("StylesheetInvalidationSet::collect_invalidations_for");
+        if self.fully_invalid {
+            debug!(" > Fully invalid already");
+            return;
+        }
+
+        if !stylesheet.enabled() || !stylesheet.is_effective_for_device(device, guard) {
+            debug!(" > Stylesheet was not effective");
+            return; // Nothing to do here.
+        }
+
+        let quirks_mode = device.quirks_mode();
+        for rule in stylesheet.effective_rules(device, guard) {
+            self.collect_invalidations_for_rule(
+                rule,
+                guard,
+                device,
+                quirks_mode,
+                /* is_generic_change = */ false,
+            );
+            if self.fully_invalid {
+                break;
+            }
+        }
+
+        self.shrink_if_needed();
+
+        debug!(" > resulting class invalidations: {:?}", self.classes);
+        debug!(" > resulting id invalidations: {:?}", self.ids);
+        debug!(
+            " > resulting local name invalidations: {:?}",
+            self.local_names
+        );
+        debug!(" > fully_invalid: {}", self.fully_invalid);
+    }
+
+    /// Clears the invalidation set, invalidating elements as needed if
+    /// `document_element` is provided.
+    ///
+    /// Returns true if any invalidations ocurred.
+    pub fn flush<E>(&mut self, document_element: Option<E>, snapshots: Option<&SnapshotMap>) -> bool
+    where
+        E: TElement,
+    {
+        debug!(
+            "Stylist::flush({:?}, snapshots: {})",
+            document_element,
+            snapshots.is_some()
+        );
+        let have_invalidations = match document_element {
+            Some(e) => self.process_invalidations(e, snapshots),
+            None => false,
+        };
+        self.clear();
+        have_invalidations
+    }
+
+    /// Returns whether there's no invalidation to process.
+    pub fn is_empty(&self) -> bool {
+        !self.fully_invalid &&
+            self.classes.is_empty() &&
+            self.ids.is_empty() &&
+            self.local_names.is_empty()
+    }
+
+    fn invalidation_kind_for<E>(
+        &self,
+        element: E,
+        snapshot: Option<&Snapshot>,
+        quirks_mode: QuirksMode,
+    ) -> InvalidationKind
+    where
+        E: TElement,
+    {
+        debug_assert!(!self.fully_invalid);
+
+        let mut kind = InvalidationKind::None;
+
+        if !self.classes.is_empty() {
+            element.each_class(|c| {
+                kind.add(self.classes.get(c, quirks_mode));
+            });
+
+            if kind.is_scope() {
+                return kind;
+            }
+
+            if let Some(snapshot) = snapshot {
+                snapshot.each_class(|c| {
+                    kind.add(self.classes.get(c, quirks_mode));
+                });
+
+                if kind.is_scope() {
+                    return kind;
+                }
+            }
+        }
+
+        if !self.ids.is_empty() {
+            if let Some(ref id) = element.id() {
+                kind.add(self.ids.get(id, quirks_mode));
+                if kind.is_scope() {
+                    return kind;
+                }
+            }
+
+            if let Some(ref old_id) = snapshot.and_then(|s| s.id_attr()) {
+                kind.add(self.ids.get(old_id, quirks_mode));
+                if kind.is_scope() {
+                    return kind;
+                }
+            }
+        }
+
+        if !self.local_names.is_empty() {
+            kind.add(self.local_names.get(element.local_name()));
+        }
+
+        kind
+    }
+
+    /// Clears the invalidation set without processing.
+    pub fn clear(&mut self) {
+        self.classes.clear();
+        self.ids.clear();
+        self.local_names.clear();
+        self.fully_invalid = false;
+        debug_assert!(self.is_empty());
+    }
+
+    fn process_invalidations<E>(&self, element: E, snapshots: Option<&SnapshotMap>) -> bool
+    where
+        E: TElement,
+    {
+        debug!("Stylist::process_invalidations({:?}, {:?})", element, self);
+
+        {
+            let mut data = match element.mutate_data() {
+                Some(data) => data,
+                None => return false,
+            };
+
+            if self.fully_invalid {
+                debug!("process_invalidations: fully_invalid({:?})", element);
+                data.hint.insert(RestyleHint::restyle_subtree());
+                return true;
+            }
+        }
+
+        if self.is_empty() {
+            debug!("process_invalidations: empty invalidation set");
+            return false;
+        }
+
+        let quirks_mode = element.as_node().owner_doc().quirks_mode();
+        self.process_invalidations_in_subtree(element, snapshots, quirks_mode)
+    }
+
+    /// Process style invalidations in a given subtree. This traverses the
+    /// subtree looking for elements that match the invalidations in our hash
+    /// map members.
+    ///
+    /// Returns whether it invalidated at least one element's style.
+    #[allow(unsafe_code)]
+    fn process_invalidations_in_subtree<E>(
+        &self,
+        element: E,
+        snapshots: Option<&SnapshotMap>,
+        quirks_mode: QuirksMode,
+    ) -> bool
+    where
+        E: TElement,
+    {
+        debug!("process_invalidations_in_subtree({:?})", element);
+        let mut data = match element.mutate_data() {
+            Some(data) => data,
+            None => return false,
+        };
+
+        if !data.has_styles() {
+            return false;
+        }
+
+        if data.hint.contains_subtree() {
+            debug!(
+                "process_invalidations_in_subtree: {:?} was already invalid",
+                element
+            );
+            return false;
+        }
+
+        let element_wrapper = snapshots.map(|s| ElementWrapper::new(element, s));
+        let snapshot = element_wrapper.as_ref().and_then(|e| e.snapshot());
+
+        match self.invalidation_kind_for(element, snapshot, quirks_mode) {
+            InvalidationKind::None => {},
+            InvalidationKind::Element => {
+                debug!(
+                    "process_invalidations_in_subtree: {:?} matched self",
+                    element
+                );
+                data.hint.insert(RestyleHint::RESTYLE_SELF);
+            },
+            InvalidationKind::Scope => {
+                debug!(
+                    "process_invalidations_in_subtree: {:?} matched subtree",
+                    element
+                );
+                data.hint.insert(RestyleHint::restyle_subtree());
+                return true;
+            },
+        }
+
+        let mut any_children_invalid = false;
+
+        for child in element.traversal_children() {
+            let child = match child.as_element() {
+                Some(e) => e,
+                None => continue,
+            };
+
+            any_children_invalid |=
+                self.process_invalidations_in_subtree(child, snapshots, quirks_mode);
+        }
+
+        if any_children_invalid {
+            debug!(
+                "Children of {:?} changed, setting dirty descendants",
+                element
+            );
+            unsafe { element.set_dirty_descendants() }
+        }
+
+        data.hint.contains(RestyleHint::RESTYLE_SELF) || any_children_invalid
+    }
+
+    /// TODO(emilio): Reuse the bucket stuff from selectormap? That handles
+    /// :is() / :where() etc.
+    fn scan_component(
+        component: &Component<SelectorImpl>,
+        invalidation: &mut Option<Invalidation>,
+    ) {
+        match *component {
+            Component::LocalName(LocalName {
+                ref name,
+                ref lower_name,
+            }) => {
+                if invalidation.is_none() {
+                    *invalidation = Some(Invalidation::LocalName {
+                        name: name.clone(),
+                        lower_name: lower_name.clone(),
+                    });
+                }
+            },
+            Component::Class(ref class) => {
+                if invalidation.as_ref().map_or(true, |s| !s.is_id_or_class()) {
+                    *invalidation = Some(Invalidation::Class(class.clone()));
+                }
+            },
+            Component::ID(ref id) => {
+                if invalidation.as_ref().map_or(true, |s| !s.is_id()) {
+                    *invalidation = Some(Invalidation::ID(id.clone()));
+                }
+            },
+            _ => {
+                // Ignore everything else, at least for now.
+            },
+        }
+    }
+
+    /// Collect invalidations for a given selector.
+    ///
+    /// We look at the outermost local name, class, or ID selector to the left
+    /// of an ancestor combinator, in order to restyle only a given subtree.
+    ///
+    /// If the selector has no ancestor combinator, then we do the same for
+    /// the only sequence it has, but record it as an element invalidation
+    /// instead of a subtree invalidation.
+    ///
+    /// We prefer IDs to classs, and classes to local names, on the basis
+    /// that the former should be more specific than the latter. We also
+    /// prefer to generate subtree invalidations for the outermost part
+    /// of the selector, to reduce the amount of traversal we need to do
+    /// when flushing invalidations.
+    fn collect_invalidations(
+        &mut self,
+        selector: &Selector<SelectorImpl>,
+        quirks_mode: QuirksMode,
+    ) {
+        debug!(
+            "StylesheetInvalidationSet::collect_invalidations({:?})",
+            selector
+        );
+
+        let mut element_invalidation: Option<Invalidation> = None;
+        let mut subtree_invalidation: Option<Invalidation> = None;
+
+        let mut scan_for_element_invalidation = true;
+        let mut scan_for_subtree_invalidation = false;
+
+        let mut iter = selector.iter();
+
+        loop {
+            for component in &mut iter {
+                if scan_for_element_invalidation {
+                    Self::scan_component(component, &mut element_invalidation);
+                } else if scan_for_subtree_invalidation {
+                    Self::scan_component(component, &mut subtree_invalidation);
+                }
+            }
+            match iter.next_sequence() {
+                None => break,
+                Some(combinator) => {
+                    scan_for_subtree_invalidation = combinator.is_ancestor();
+                },
+            }
+            scan_for_element_invalidation = false;
+        }
+
+        if let Some(s) = subtree_invalidation {
+            debug!(" > Found subtree invalidation: {:?}", s);
+            if self.insert_invalidation(s, InvalidationKind::Scope, quirks_mode) {
+                return;
+            }
+        }
+
+        if let Some(s) = element_invalidation {
+            debug!(" > Found element invalidation: {:?}", s);
+            if self.insert_invalidation(s, InvalidationKind::Element, quirks_mode) {
+                return;
+            }
+        }
+
+        // The selector was of a form that we can't handle. Any element could
+        // match it, so let's just bail out.
+        debug!(" > Can't handle selector or OOMd, marking fully invalid");
+        self.invalidate_fully()
+    }
+
+    fn insert_invalidation(
+        &mut self,
+        invalidation: Invalidation,
+        kind: InvalidationKind,
+        quirks_mode: QuirksMode,
+    ) -> bool {
+        match invalidation {
+            Invalidation::Class(c) => {
+                let entry = match self.classes.try_entry(c.0, quirks_mode) {
+                    Ok(e) => e,
+                    Err(..) => return false,
+                };
+                *entry.or_insert(InvalidationKind::None) |= kind;
+            },
+            Invalidation::ID(i) => {
+                let entry = match self.ids.try_entry(i.0, quirks_mode) {
+                    Ok(e) => e,
+                    Err(..) => return false,
+                };
+                *entry.or_insert(InvalidationKind::None) |= kind;
+            },
+            Invalidation::LocalName { name, lower_name } => {
+                let insert_lower = name != lower_name;
+                if self.local_names.try_reserve(1).is_err() {
+                    return false;
+                }
+                let entry = self.local_names.entry(name);
+                *entry.or_insert(InvalidationKind::None) |= kind;
+                if insert_lower {
+                    if self.local_names.try_reserve(1).is_err() {
+                        return false;
+                    }
+                    let entry = self.local_names.entry(lower_name);
+                    *entry.or_insert(InvalidationKind::None) |= kind;
+                }
+            },
+        }
+
+        true
+    }
+
+    /// Collects invalidations for a given CSS rule, if not fully invalid
+    /// already.
+    ///
+    /// TODO(emilio): we can't check whether the rule is inside a non-effective
+    /// subtree, we potentially could do that.
+    pub fn rule_changed<S>(
+        &mut self,
+        stylesheet: &S,
+        rule: &CssRule,
+        guard: &SharedRwLockReadGuard,
+        device: &Device,
+        quirks_mode: QuirksMode,
+        change_kind: RuleChangeKind,
+    ) where
+        S: StylesheetInDocument,
+    {
+        debug!("StylesheetInvalidationSet::rule_changed");
+        if self.fully_invalid {
+            return;
+        }
+
+        if !stylesheet.enabled() || !stylesheet.is_effective_for_device(device, guard) {
+            debug!(" > Stylesheet was not effective");
+            return; // Nothing to do here.
+        }
+
+        // If the change is generic, we don't have the old rule information to know e.g., the old
+        // media condition, or the old selector text, so we might need to invalidate more
+        // aggressively. That only applies to the changed rules, for other rules we can just
+        // collect invalidations as normal.
+        let is_generic_change = change_kind == RuleChangeKind::Generic;
+        self.collect_invalidations_for_rule(rule, guard, device, quirks_mode, is_generic_change);
+        if self.fully_invalid {
+            return;
+        }
+
+        if !is_generic_change && !EffectiveRules::is_effective(guard, device, quirks_mode, rule) {
+            return;
+        }
+
+        let rules = EffectiveRulesIterator::effective_children(device, quirks_mode, guard, rule);
+        for rule in rules {
+            self.collect_invalidations_for_rule(
+                rule,
+                guard,
+                device,
+                quirks_mode,
+                /* is_generic_change = */ false,
+            );
+            if self.fully_invalid {
+                break;
+            }
+        }
+    }
+
+    /// Collects invalidations for a given CSS rule.
+    fn collect_invalidations_for_rule(
+        &mut self,
+        rule: &CssRule,
+        guard: &SharedRwLockReadGuard,
+        device: &Device,
+        quirks_mode: QuirksMode,
+        is_generic_change: bool,
+    ) {
+        use crate::stylesheets::CssRule::*;
+        debug!("StylesheetInvalidationSet::collect_invalidations_for_rule");
+        debug_assert!(!self.fully_invalid, "Not worth being here!");
+
+        match *rule {
+            Style(ref lock) => {
+                if is_generic_change {
+                    // TODO(emilio): We need to do this for selector / keyframe
+                    // name / font-face changes, because we don't have the old
+                    // selector / name.  If we distinguish those changes
+                    // specially, then we can at least use this invalidation for
+                    // style declaration changes.
+                    return self.invalidate_fully();
+                }
+
+                let style_rule = lock.read_with(guard);
+                for selector in style_rule.selectors.slice() {
+                    self.collect_invalidations(selector, quirks_mode);
+                    if self.fully_invalid {
+                        return;
+                    }
+                }
+            },
+            Namespace(..) => {
+                // It's not clear what handling changes for this correctly would
+                // look like.
+            },
+            LayerStatement(..) => {
+                // Layer statement insertions might alter styling order, so we need to always
+                // invalidate fully.
+                return self.invalidate_fully();
+            },
+            Document(..) | Import(..) | Media(..) | Supports(..) | Container(..) |
+            LayerBlock(..) => {
+                // Do nothing, relevant nested rules are visited as part of rule iteration.
+            },
+            FontFace(..) => {
+                // Do nothing, @font-face doesn't affect computed style information on it's own.
+                // We'll restyle when the font face loads, if needed.
+            },
+            Page(..) | Margin(..) => {
+                // Do nothing, we don't support OM mutations on print documents, and page rules
+                // can't affect anything else.
+            },
+            Keyframes(ref lock) => {
+                if is_generic_change {
+                    return self.invalidate_fully();
+                }
+                let keyframes_rule = lock.read_with(guard);
+                if device.animation_name_may_be_referenced(&keyframes_rule.name) {
+                    debug!(
+                        " > Found @keyframes rule potentially referenced \
+                         from the page, marking the whole tree invalid."
+                    );
+                    self.invalidate_fully();
+                } else {
+                    // Do nothing, this animation can't affect the style of existing elements.
+                }
+            },
+            CounterStyle(..) | Property(..) | FontFeatureValues(..) | FontPaletteValues(..) => {
+                debug!(" > Found unsupported rule, marking the whole subtree invalid.");
+                self.invalidate_fully();
+            },
+        }
+    }
+}
diff --git a/servo/components/style/invalidation/viewport_units.rs b/servo/components/style/invalidation/viewport_units.rs
new file mode 100644
index 0000000000..06faeb14c4
--- /dev/null
+++ b/servo/components/style/invalidation/viewport_units.rs
@@ -0,0 +1,71 @@
+/* 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/. */
+
+//! Invalidates style of all elements that depend on viewport units.
+
+use crate::data::ViewportUnitUsage;
+use crate::dom::{TElement, TNode};
+use crate::invalidation::element::restyle_hints::RestyleHint;
+
+/// Invalidates style of all elements that depend on viewport units.
+///
+/// Returns whether any element was invalidated.
+pub fn invalidate<E>(root: E) -> bool
+where
+    E: TElement,
+{
+    debug!("invalidation::viewport_units::invalidate({:?})", root);
+    invalidate_recursively(root)
+}
+
+fn invalidate_recursively<E>(element: E) -> bool
+where
+    E: TElement,
+{
+    let mut data = match element.mutate_data() {
+        Some(data) => data,
+        None => return false,
+    };
+
+    if data.hint.will_recascade_subtree() {
+        debug!("invalidate_recursively: {:?} was already invalid", element);
+        return false;
+    }
+
+    let usage = data.styles.viewport_unit_usage();
+    let uses_viewport_units = usage != ViewportUnitUsage::None;
+    if uses_viewport_units {
+        debug!(
+            "invalidate_recursively: {:?} uses viewport units {:?}",
+            element, usage
+        );
+    }
+
+    match usage {
+        ViewportUnitUsage::None => {},
+        ViewportUnitUsage::FromQuery => {
+            data.hint.insert(RestyleHint::RESTYLE_SELF);
+        },
+        ViewportUnitUsage::FromDeclaration => {
+            data.hint.insert(RestyleHint::RECASCADE_SELF);
+        },
+    }
+
+    let mut any_children_invalid = false;
+    for child in element.traversal_children() {
+        if let Some(child) = child.as_element() {
+            any_children_invalid |= invalidate_recursively(child);
+        }
+    }
+
+    if any_children_invalid {
+        debug!(
+            "invalidate_recursively: Children of {:?} changed, setting dirty descendants",
+            element
+        );
+        unsafe { element.set_dirty_descendants() }
+    }
+
+    uses_viewport_units || any_children_invalid
+}