diff options
Diffstat (limited to 'servo/components/style/invalidation')
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 +} |