Adding upstream version 110.0.1.upstream/110.0.1upstream

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

11 files changed, 3700 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..13b53c27ba
--- /dev/null
+++ b/servo/components/style/invalidation/element/document_state.rs
@@ -0,0 +1,136 @@
+/* This Source Code Form is subject to the terms of the Mozilla Public
+ * License, v. 2.0. If a copy of the MPL was not distributed with this
+ * file, You can obtain one at https://mozilla.org/MPL/2.0/. */
+
+//! 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};
+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, MatchingMode, NeedsSelectorFlags, QuirksMode, 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, E: TElement, I> {
+    rules: I,
+    matching_context: MatchingContext<'a, E::Impl>,
+    document_states_changed: DocumentState,
+}
+
+impl<'a, E: TElement, I> DocumentStateInvalidationProcessor<'a, E, I> {
+    /// Creates a new DocumentStateInvalidationProcessor.
+    #[inline]
+    pub fn new(rules: I, document_states_changed: DocumentState, quirks_mode: QuirksMode) -> Self {
+        let mut matching_context = MatchingContext::<'a, E::Impl>::new_for_visited(
+            MatchingMode::Normal,
+            None,
+            None,
+            VisitedHandlingMode::AllLinksVisitedAndUnvisited,
+            quirks_mode,
+            NeedsSelectorFlags::No,
+        );
+
+        matching_context.extra_data.invalidation_data.document_state = document_states_changed;
+
+        Self {
+            rules,
+            document_states_changed,
+            matching_context,
+        }
+    }
+}
+
+impl<'a, E, I> InvalidationProcessor<'a, E> for DocumentStateInvalidationProcessor<'a, E, I>
+where
+    E: TElement,
+    I: Iterator<Item = &'a 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<'a>,
+        _descendant_invalidations: &mut DescendantInvalidationLists<'a>,
+        _sibling_invalidations: &mut InvalidationVector<'a>,
+    ) -> 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 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..d4ca7cbb3a
--- /dev/null
+++ b/servo/components/style/invalidation/element/element_wrapper.rs
@@ -0,0 +1,391 @@
+/* This Source Code Form is subject to the terms of the Mozilla Public
+ * License, v. 2.0. If a copy of the MPL was not distributed with this
+ * file, You can obtain one at https://mozilla.org/MPL/2.0/. */
+
+//! 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::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::MozBrowserFrame => {
+                if let Some(snapshot) = self.snapshot() {
+                    if snapshot.has_other_pseudo_class_state() {
+                        return snapshot.mIsMozBrowserFrame();
+                    }
+                }
+            },
+
+            #[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 set_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))
+    }
+}
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..3783f27880
--- /dev/null
+++ b/servo/components/style/invalidation/element/invalidation_map.rs
@@ -0,0 +1,541 @@
+/* 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::SelectorImpl;
+use crate::AllocErr;
+use crate::{Atom, LocalName, Namespace, ShrinkIfNeeded};
+use dom::{DocumentState, ElementState};
+use selectors::attr::NamespaceConstraint;
+use selectors::parser::{Combinator, Component};
+use selectors::parser::{Selector, SelectorIter};
+use selectors::visitor::SelectorVisitor;
+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.
+    #[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 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)
+    ///
+    pub parent: Option<Box<Dependency>>,
+}
+
+/// The kind of elements down the tree this dependency may affect.
+#[derive(Debug, Eq, PartialEq)]
+pub enum DependencyInvalidationKind {
+    /// 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,
+}
+
+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,
+        }
+    }
+
+    /// Returns the combinator to the right of the partial selector this
+    /// dependency represents.
+    ///
+    /// TODO(emilio): Consider storing inline if it helps cache locality?
+    pub 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 invalidation that this would generate.
+    pub fn invalidation_kind(&self) -> DependencyInvalidationKind {
+        match self.combinator() {
+            None => DependencyInvalidationKind::Element,
+            Some(Combinator::Child) | Some(Combinator::Descendant) => {
+                DependencyInvalidationKind::Descendants
+            },
+            Some(Combinator::LaterSibling) | Some(Combinator::NextSibling) => {
+                DependencyInvalidationKind::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) => DependencyInvalidationKind::ElementAndDescendants,
+            Some(Combinator::SlotAssignment) => DependencyInvalidationKind::SlottedElements,
+            Some(Combinator::Part) => DependencyInvalidationKind::Parts,
+        }
+    }
+}
+
+impl SelectorMapEntry for Dependency {
+    fn selector(&self) -> SelectorIter<SelectorImpl> {
+        self.selector.iter_from(self.selector_offset)
+    }
+}
+
+/// 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,
+}
+
+/// 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: MaybeCaseInsensitiveHashMap<Atom, SmallVec<[Dependency; 1]>>,
+    /// 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: MaybeCaseInsensitiveHashMap<Atom, SmallVec<[Dependency; 1]>>,
+    /// A map of all the state dependencies.
+    pub state_affecting_selectors: SelectorMap<StateDependency>,
+    /// 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:
+        PrecomputedHashMap<LocalName, SmallVec<[Dependency; 1]>>,
+}
+
+impl InvalidationMap {
+    /// Creates an empty `InvalidationMap`.
+    pub fn new() -> Self {
+        Self {
+            class_to_selector: MaybeCaseInsensitiveHashMap::new(),
+            id_to_selector: MaybeCaseInsensitiveHashMap::new(),
+            state_affecting_selectors: SelectorMap::new(),
+            document_state_selectors: Vec::new(),
+            other_attribute_affecting_selectors: PrecomputedHashMap::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 this `InvalidationMap`.  Returns Err(..) to
+    /// signify OOM.
+    pub fn note_selector(
+        &mut self,
+        selector: &Selector<SelectorImpl>,
+        quirks_mode: QuirksMode,
+    ) -> Result<(), AllocErr> {
+        debug!("InvalidationMap::note_selector({:?})", selector);
+
+        let mut document_state = DocumentState::empty();
+
+        {
+            let mut parent_stack = SmallVec::new();
+            let mut alloc_error = None;
+            let mut collector = SelectorDependencyCollector {
+                map: self,
+                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()),
+            };
+            self.document_state_selectors.try_reserve(1)?;
+            self.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(),
+        }
+    }
+}
+
+/// A struct that collects invalidations for a given compound selector.
+struct SelectorDependencyCollector<'a> {
+    map: &'a mut InvalidationMap,
+
+    /// 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.
+    parent_selectors: &'a mut SmallVec<[(Selector<SelectorImpl>, usize); 5]>,
+
+    /// 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>,
+}
+
+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 !self.compound_state.element_state.is_empty() {
+                let dependency = self.dependency();
+                let result = self.map.state_affecting_selectors.insert(
+                    StateDependency {
+                        dep: dependency,
+                        state: self.compound_state.element_state,
+                    },
+                    self.quirks_mode,
+                );
+                if let Err(alloc_error) = result {
+                    *self.alloc_error = Some(alloc_error.into());
+                    return false;
+                }
+            }
+
+            let combinator = iter.next_sequence();
+            if combinator.is_none() {
+                return true;
+            }
+            index += 1; // account for the combinator
+        }
+    }
+
+    fn add_attr_dependency(&mut self, name: LocalName) -> bool {
+        let dependency = self.dependency();
+
+        let map = &mut self.map.other_attribute_affecting_selectors;
+        if let Err(err) = map.try_reserve(1) {
+            *self.alloc_error = Some(err.into());
+            return false;
+        }
+        let vec = map.entry(name).or_default();
+        if let Err(err) = vec.try_reserve(1) {
+            *self.alloc_error = Some(err.into());
+            return false;
+        }
+        vec.push(dependency);
+        true
+    }
+
+    fn dependency(&self) -> Dependency {
+        let mut parent = None;
+
+        // TODO(emilio): Maybe we should refcount the parent dependencies, or
+        // cache them or something.
+        for &(ref selector, ref selector_offset) in self.parent_selectors.iter() {
+            debug_assert_ne!(
+                self.compound_state.offset, 0,
+                "Shouldn't bother creating nested dependencies for the rightmost compound",
+            );
+            let new_parent = Dependency {
+                selector: selector.clone(),
+                selector_offset: *selector_offset,
+                parent,
+            };
+            parent = Some(Box::new(new_parent));
+        }
+
+        Dependency {
+            selector: self.selector.clone(),
+            selector_offset: self.compound_state.offset,
+            parent,
+        }
+    }
+}
+
+impl<'a> SelectorVisitor for SelectorDependencyCollector<'a> {
+    type Impl = SelectorImpl;
+
+    fn visit_selector_list(&mut self, 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((self.selector.clone(), self.compound_state.offset));
+            let mut nested = SelectorDependencyCollector {
+                map: &mut *self.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_simple_selector(&mut self, s: &Component<SelectorImpl>) -> bool {
+        use crate::selector_parser::NonTSPseudoClass;
+
+        match *s {
+            Component::ID(ref atom) | Component::Class(ref atom) => {
+                let dependency = self.dependency();
+                let map = match *s {
+                    Component::ID(..) => &mut self.map.id_to_selector,
+                    Component::Class(..) => &mut self.map.class_to_selector,
+                    _ => unreachable!(),
+                };
+                let entry = match map.try_entry(atom.0.clone(), self.quirks_mode) {
+                    Ok(entry) => entry,
+                    Err(err) => {
+                        *self.alloc_error = Some(err.into());
+                        return false;
+                    },
+                };
+                let vec = entry.or_insert_with(SmallVec::new);
+                if let Err(err) = vec.try_reserve(1) {
+                    *self.alloc_error = Some(err.into());
+                    return false;
+                }
+                vec.push(dependency);
+                true
+            },
+            Component::NonTSPseudoClass(ref pc) => {
+                self.compound_state.element_state |= pc.state_flag();
+                *self.document_state |= pc.document_state_flag();
+
+                let attr_name = match *pc {
+                    #[cfg(feature = "gecko")]
+                    NonTSPseudoClass::MozTableBorderNonzero => local_name!("border"),
+                    #[cfg(feature = "gecko")]
+                    NonTSPseudoClass::MozBrowserFrame => local_name!("mozbrowser"),
+                    #[cfg(feature = "gecko")]
+                    NonTSPseudoClass::MozSelectListBox => {
+                        // This depends on two attributes.
+                        return self.add_attr_dependency(local_name!("multiple")) &&
+                            self.add_attr_dependency(local_name!("size"));
+                    },
+                    NonTSPseudoClass::Lang(..) => local_name!("lang"),
+                    _ => return true,
+                };
+
+                self.add_attr_dependency(attr_name)
+            },
+            _ => true,
+        }
+    }
+
+    fn visit_attribute_selector(
+        &mut self,
+        _: &NamespaceConstraint<&Namespace>,
+        local_name: &LocalName,
+        local_name_lower: &LocalName,
+    ) -> bool {
+        if !self.add_attr_dependency(local_name.clone()) {
+            return false;
+        }
+
+        if local_name != local_name_lower && !self.add_attr_dependency(local_name_lower.clone()) {
+            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..ac8f9ed5f8
--- /dev/null
+++ b/servo/components/style/invalidation/element/invalidator.rs
@@ -0,0 +1,1014 @@
+/* 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};
+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;
+
+/// A trait to abstract the collection of invalidations for a given pass.
+pub trait InvalidationProcessor<'a, 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<'a, E::Impl>;
+
+    /// 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);
+}
+
+/// 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, E, P: 'a>
+where
+    'b: 'a,
+    E: TElement,
+    P: InvalidationProcessor<'b, E>,
+{
+    element: E,
+    stack_limit_checker: Option<&'a StackLimitChecker>,
+    processor: &'a mut P,
+    _marker: ::std::marker::PhantomData<&'b ()>,
+}
+
+/// 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.invalidation_kind() != DependencyInvalidationKind::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_str(")")
+    }
+}
+
+/// 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, E, P: 'a> TreeStyleInvalidator<'a, 'b, E, P>
+where
+    'b: 'a,
+    E: TElement,
+    P: InvalidationProcessor<'b, 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.element.next_sibling_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 = sibling.next_sibling_element();
+        }
+
+        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) => &**p,
+                    };
+
+                    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.invalidation_kind() == DependencyInvalidationKind::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..1f19cc54f5
--- /dev/null
+++ b/servo/components/style/invalidation/element/mod.rs
@@ -0,0 +1,12 @@
+/* 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 restyle_hints;
+pub mod state_and_attributes;
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..c423d85390
--- /dev/null
+++ b/servo/components/style/invalidation/element/restyle_hints.rs
@@ -0,0 +1,192 @@
+/* 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)]
+    pub struct RestyleHint: u8 {
+        /// Do a selector match of the element.
+        const RESTYLE_SELF = 1 << 0;
+
+        /// Do a selector match of the element's descendants.
+        const RESTYLE_DESCENDANTS = 1 << 1;
+
+        /// Recascade the current element.
+        const RECASCADE_SELF = 1 << 2;
+
+        /// Recascade all descendant elements.
+        const RECASCADE_DESCENDANTS = 1 << 3;
+
+        /// 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 << 4;
+
+        /// 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 << 5;
+
+        /// 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 << 6;
+
+        /// 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 << 7;
+    }
+}
+
+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.intersects(
+            RestyleHint::RESTYLE_SELF |
+                RestyleHint::RECASCADE_SELF |
+                (Self::replacements() & !Self::for_animations()),
+        )
+    }
+
+    /// 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 `CascadeHint` 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();
+        }
+        if self.contains(RestyleHint::RECASCADE_DESCENDANTS) {
+            return Self::recascade_subtree();
+        }
+        Self::empty()
+    }
+
+    /// 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 the currently element must be
+    /// recascaded.
+    pub fn has_recascade_self(&self) -> bool {
+        self.contains(RestyleHint::RECASCADE_SELF)
+    }
+
+    /// 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() | RestyleHint::RECASCADE_SELF)
+    }
+
+    /// 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 selector matching must be re-run
+    /// for the element.
+    #[inline]
+    pub fn match_self(&self) -> bool {
+        self.intersects(RestyleHint::RESTYLE_SELF)
+    }
+
+    /// 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(RestyleHint::RECASCADE_SELF);
+    }
+}
+
+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..f88ebffe06
--- /dev/null
+++ b/servo/components/style/invalidation/element/state_and_attributes.rs
@@ -0,0 +1,555 @@
+/* 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};
+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, MatchingMode, NeedsSelectorFlags, VisitedHandlingMode,
+};
+use selectors::NthIndexCache;
+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>,
+}
+
+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,
+        nth_index_cache: &'a mut NthIndexCache,
+    ) -> Self {
+        let matching_context = MatchingContext::new_for_visited(
+            MatchingMode::Normal,
+            None,
+            Some(nth_index_cache),
+            VisitedHandlingMode::AllLinksVisitedAndUnvisited,
+            shared_context.quirks_mode(),
+            NeedsSelectorFlags::No,
+        );
+
+        Self {
+            shared_context,
+            element,
+            data,
+            matching_context,
+        }
+    }
+}
+
+/// 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, 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 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 snapshot = wrapper.snapshot().expect("has_snapshot lied");
+
+        if !snapshot.has_attrs() && state_changes.is_empty() {
+            return false;
+        }
+
+        // If we the visited state changed, we force a restyle here. Matching
+        // doesn't depend on the actual visited state at all, so we can't look
+        // at matching results to decide what to do for this case.
+        //
+        // TODO(emilio): This piece of code should be removed when
+        // layout.css.always-repaint-on-unvisited is true, since we cannot get
+        // into this situation in that case.
+        if state_changes.contains(ElementState::VISITED_OR_UNVISITED) {
+            trace!(" > visitedness change, force subtree restyle");
+            // We can't just return here because there may also be attribute
+            // changes as well that imply additional hints for siblings.
+            self.data.hint.insert(RestyleHint::restyle_subtree());
+        }
+
+        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!(
+            "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.invalidation_kind();
+        if matches!(invalidation_kind, DependencyInvalidationKind::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());
+
+        match invalidation_kind {
+            DependencyInvalidationKind::Element => unreachable!(),
+            DependencyInvalidationKind::ElementAndDescendants => {
+                self.invalidates_self = true;
+                self.descendant_invalidations
+                    .dom_descendants
+                    .push(invalidation);
+            },
+            DependencyInvalidationKind::Descendants => {
+                self.descendant_invalidations
+                    .dom_descendants
+                    .push(invalidation);
+            },
+            DependencyInvalidationKind::Siblings => {
+                self.sibling_invalidations.push(invalidation);
+            },
+            DependencyInvalidationKind::Parts => {
+                self.descendant_invalidations.parts.push(invalidation);
+            },
+            DependencyInvalidationKind::SlottedElements => {
+                self.descendant_invalidations
+                    .slotted_descendants
+                    .push(invalidation);
+            },
+        }
+    }
+
+    /// 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.invalidation_kind() {
+            DependencyInvalidationKind::Element => !self.invalidates_self,
+            DependencyInvalidationKind::SlottedElements => self.element.is_html_slot_element(),
+            DependencyInvalidationKind::Parts => self.element.shadow_root().is_some(),
+            DependencyInvalidationKind::ElementAndDescendants |
+            DependencyInvalidationKind::Siblings |
+            DependencyInvalidationKind::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..f18fe7942c
--- /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);
+            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,
+    {
+        use crate::stylesheets::CssRule::*;
+
+        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.
+        }
+
+        let is_generic_change = change_kind == RuleChangeKind::Generic;
+
+        match *rule {
+            Namespace(..) => {
+                // It's not clear what handling changes for this correctly would
+                // look like.
+            },
+            CounterStyle(..) |
+            Page(..) |
+            Viewport(..) |
+            FontFeatureValues(..) |
+            FontPaletteValues(..) |
+            LayerStatement(..) |
+            FontFace(..) |
+            Keyframes(..) |
+            Container(..) |
+            Style(..) => {
+                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();
+                }
+
+                self.collect_invalidations_for_rule(rule, guard, device, quirks_mode)
+            },
+            Document(..) | Import(..) | Media(..) | Supports(..) | LayerBlock(..) => {
+                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);
+                    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,
+    ) {
+        use crate::stylesheets::CssRule::*;
+        debug!("StylesheetInvalidationSet::collect_invalidations_for_rule");
+        debug_assert!(!self.fully_invalid, "Not worth to be here!");
+
+        match *rule {
+            Style(ref lock) => {
+                let style_rule = lock.read_with(guard);
+                for selector in &style_rule.selectors.0 {
+                    self.collect_invalidations(selector, quirks_mode);
+                    if self.fully_invalid {
+                        return;
+                    }
+                }
+            },
+            Document(..) | Namespace(..) | Import(..) | Media(..) | Supports(..) |
+            Container(..) | LayerStatement(..) | LayerBlock(..) => {
+                // Do nothing, relevant nested rules are visited as part of the
+                // iteration.
+            },
+            FontFace(..) => {
+                // Do nothing, @font-face doesn't affect computed style
+                // information. We'll restyle when the font face loads, if
+                // needed.
+            },
+            Keyframes(ref lock) => {
+                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.fully_invalid = true;
+                } else {
+                    // Do nothing, this animation can't affect the style of
+                    // existing elements.
+                }
+            },
+            CounterStyle(..) | Page(..) | Viewport(..) | FontFeatureValues(..) |
+            FontPaletteValues(..) => {
+                debug!(
+                    " > Found unsupported rule, marking the whole subtree \
+                     invalid."
+                );
+
+                // TODO(emilio): Can we do better here?
+                //
+                // At least in `@page`, we could check the relevant media, I
+                // guess.
+                self.fully_invalid = true;
+            },
+        }
+    }
+}
diff --git a/servo/components/style/invalidation/viewport_units.rs b/servo/components/style/invalidation/viewport_units.rs
new file mode 100644
index 0000000000..75a3aad24b
--- /dev/null
+++ b/servo/components/style/invalidation/viewport_units.rs
@@ -0,0 +1,68 @@
+/* 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
+}