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