diff options
Diffstat (limited to 'servo/components/style/invalidation/element')
7 files changed, 2850 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..5900549c79 --- /dev/null +++ b/servo/components/style/invalidation/element/document_state.rs @@ -0,0 +1,142 @@ +/* This Source Code Form is subject to the terms of the Mozilla Public + * License, v. 2.0. If a copy of the MPL was not distributed with this + * file, You can obtain one at https://mozilla.org/MPL/2.0/. */ + +//! An invalidation processor for style changes due to document state changes. + +use crate::dom::TElement; +use crate::invalidation::element::invalidation_map::Dependency; +use crate::invalidation::element::invalidator::{DescendantInvalidationLists, InvalidationVector}; +use crate::invalidation::element::invalidator::{Invalidation, InvalidationProcessor}; +use crate::invalidation::element::state_and_attributes; +use crate::stylist::CascadeData; +use dom::DocumentState; +use selectors::matching::{ + MatchingContext, MatchingMode, NeedsSelectorFlags, QuirksMode, VisitedHandlingMode, +}; +use selectors::NthIndexCache; + +/// A struct holding the members necessary to invalidate document state +/// selectors. +#[derive(Debug)] +pub struct InvalidationMatchingData { + /// The document state that has changed, which makes it always match. + pub document_state: DocumentState, +} + +impl Default for InvalidationMatchingData { + #[inline(always)] + fn default() -> Self { + Self { + document_state: DocumentState::empty(), + } + } +} + +/// An invalidation processor for style changes due to state and attribute +/// changes. +pub struct DocumentStateInvalidationProcessor<'a, E: TElement, I> { + rules: I, + matching_context: MatchingContext<'a, E::Impl>, + document_states_changed: DocumentState, +} + +impl<'a, E: TElement, I> DocumentStateInvalidationProcessor<'a, E, I> { + /// Creates a new DocumentStateInvalidationProcessor. + #[inline] + pub fn new( + rules: I, + document_states_changed: DocumentState, + nth_index_cache: &'a mut NthIndexCache, + quirks_mode: QuirksMode, + ) -> Self { + let mut matching_context = MatchingContext::<'a, E::Impl>::new_for_visited( + MatchingMode::Normal, + None, + nth_index_cache, + VisitedHandlingMode::AllLinksVisitedAndUnvisited, + quirks_mode, + NeedsSelectorFlags::No, + ); + + matching_context.extra_data.invalidation_data.document_state = document_states_changed; + + Self { + rules, + document_states_changed, + matching_context, + } + } +} + +impl<'a, E, I> InvalidationProcessor<'a, E> for DocumentStateInvalidationProcessor<'a, E, I> +where + E: TElement, + I: Iterator<Item = &'a CascadeData>, +{ + fn check_outer_dependency(&mut self, _: &Dependency, _: E) -> bool { + debug_assert!( + false, + "how, we should only have parent-less dependencies here!" + ); + true + } + + fn collect_invalidations( + &mut self, + _element: E, + self_invalidations: &mut InvalidationVector<'a>, + _descendant_invalidations: &mut DescendantInvalidationLists<'a>, + _sibling_invalidations: &mut InvalidationVector<'a>, + ) -> bool { + for cascade_data in &mut self.rules { + let map = cascade_data.invalidation_map(); + for dependency in &map.document_state_selectors { + if !dependency.state.intersects(self.document_states_changed) { + continue; + } + + // We pass `None` as a scope, as document state selectors aren't + // affected by the current scope. + // + // FIXME(emilio): We should really pass the relevant host for + // self.rules, so that we invalidate correctly if the selector + // happens to have something like :host(:-moz-window-inactive) + // for example. + self_invalidations.push(Invalidation::new( + &dependency.dependency, + /* scope = */ None, + )); + } + } + + false + } + + fn matching_context(&mut self) -> &mut MatchingContext<'a, E::Impl> { + &mut self.matching_context + } + + fn recursion_limit_exceeded(&mut self, _: E) { + unreachable!("We don't run document state invalidation with stack limits") + } + + fn should_process_descendants(&mut self, element: E) -> bool { + match element.borrow_data() { + Some(d) => state_and_attributes::should_process_descendants(&d), + None => false, + } + } + + fn invalidated_descendants(&mut self, element: E, child: E) { + state_and_attributes::invalidated_descendants(element, child) + } + + fn invalidated_self(&mut self, element: E) { + state_and_attributes::invalidated_self(element); + } + + fn invalidated_sibling(&mut self, sibling: E, of: E) { + state_and_attributes::invalidated_sibling(sibling, of); + } +} diff --git a/servo/components/style/invalidation/element/element_wrapper.rs b/servo/components/style/invalidation/element/element_wrapper.rs new file mode 100644 index 0000000000..71c3c94daf --- /dev/null +++ b/servo/components/style/invalidation/element/element_wrapper.rs @@ -0,0 +1,391 @@ +/* This Source Code Form is subject to the terms of the Mozilla Public + * License, v. 2.0. If a copy of the MPL was not distributed with this + * file, You can obtain one at https://mozilla.org/MPL/2.0/. */ + +//! A wrapper over an element and a snapshot, that allows us to selector-match +//! against a past state of the element. + +use crate::dom::TElement; +use crate::selector_parser::{AttrValue, NonTSPseudoClass, PseudoElement, SelectorImpl}; +use crate::selector_parser::{Snapshot, SnapshotMap}; +use crate::values::AtomIdent; +use crate::{CaseSensitivityExt, LocalName, Namespace, WeakAtom}; +use dom::ElementState; +use selectors::attr::{AttrSelectorOperation, CaseSensitivity, NamespaceConstraint}; +use selectors::matching::{ElementSelectorFlags, MatchingContext}; +use selectors::{Element, OpaqueElement}; +use std::cell::Cell; +use std::fmt; + +/// In order to compute restyle hints, we perform a selector match against a +/// list of partial selectors whose rightmost simple selector may be sensitive +/// to the thing being changed. We do this matching twice, once for the element +/// as it exists now and once for the element as it existed at the time of the +/// last restyle. If the results of the selector match differ, that means that +/// the given partial selector is sensitive to the change, and we compute a +/// restyle hint based on its combinator. +/// +/// In order to run selector matching against the old element state, we generate +/// a wrapper for the element which claims to have the old state. This is the +/// ElementWrapper logic below. +/// +/// Gecko does this differently for element states, and passes a mask called +/// mStateMask, which indicates the states that need to be ignored during +/// selector matching. This saves an ElementWrapper allocation and an additional +/// selector match call at the expense of additional complexity inside the +/// selector matching logic. This only works for boolean states though, so we +/// still need to take the ElementWrapper approach for attribute-dependent +/// style. So we do it the same both ways for now to reduce complexity, but it's +/// worth measuring the performance impact (if any) of the mStateMask approach. +pub trait ElementSnapshot: Sized { + /// The state of the snapshot, if any. + fn state(&self) -> Option<ElementState>; + + /// If this snapshot contains attribute information. + fn has_attrs(&self) -> bool; + + /// Gets the attribute information of the snapshot as a string. + /// + /// Only for debugging purposes. + fn debug_list_attributes(&self) -> String { + String::new() + } + + /// The ID attribute per this snapshot. Should only be called if + /// `has_attrs()` returns true. + fn id_attr(&self) -> Option<&WeakAtom>; + + /// Whether this snapshot contains the class `name`. Should only be called + /// if `has_attrs()` returns true. + fn has_class(&self, name: &AtomIdent, case_sensitivity: CaseSensitivity) -> bool; + + /// Whether this snapshot represents the part named `name`. Should only be + /// called if `has_attrs()` returns true. + fn is_part(&self, name: &AtomIdent) -> bool; + + /// See Element::imported_part. + fn imported_part(&self, name: &AtomIdent) -> Option<AtomIdent>; + + /// A callback that should be called for each class of the snapshot. Should + /// only be called if `has_attrs()` returns true. + fn each_class<F>(&self, _: F) + where + F: FnMut(&AtomIdent); + + /// The `xml:lang=""` or `lang=""` attribute value per this snapshot. + fn lang_attr(&self) -> Option<AttrValue>; +} + +/// A simple wrapper over an element and a snapshot, that allows us to +/// selector-match against a past state of the element. +#[derive(Clone)] +pub struct ElementWrapper<'a, E> +where + E: TElement, +{ + element: E, + cached_snapshot: Cell<Option<&'a Snapshot>>, + snapshot_map: &'a SnapshotMap, +} + +impl<'a, E> ElementWrapper<'a, E> +where + E: TElement, +{ + /// Trivially constructs an `ElementWrapper`. + pub fn new(el: E, snapshot_map: &'a SnapshotMap) -> Self { + ElementWrapper { + element: el, + cached_snapshot: Cell::new(None), + snapshot_map: snapshot_map, + } + } + + /// Gets the snapshot associated with this element, if any. + pub fn snapshot(&self) -> Option<&'a Snapshot> { + if !self.element.has_snapshot() { + return None; + } + + if let Some(s) = self.cached_snapshot.get() { + return Some(s); + } + + let snapshot = self.snapshot_map.get(&self.element); + debug_assert!(snapshot.is_some(), "has_snapshot lied!"); + + self.cached_snapshot.set(snapshot); + + snapshot + } + + /// Returns the states that have changed since the element was snapshotted. + pub fn state_changes(&self) -> ElementState { + let snapshot = match self.snapshot() { + Some(s) => s, + None => return ElementState::empty(), + }; + + match snapshot.state() { + Some(state) => state ^ self.element.state(), + None => ElementState::empty(), + } + } + + /// Returns the value of the `xml:lang=""` (or, if appropriate, `lang=""`) + /// attribute from this element's snapshot or the closest ancestor + /// element snapshot with the attribute specified. + fn get_lang(&self) -> Option<AttrValue> { + let mut current = self.clone(); + loop { + let lang = match self.snapshot() { + Some(snapshot) if snapshot.has_attrs() => snapshot.lang_attr(), + _ => current.element.lang_attr(), + }; + if lang.is_some() { + return lang; + } + current = current.parent_element()?; + } + } +} + +impl<'a, E> fmt::Debug for ElementWrapper<'a, E> +where + E: TElement, +{ + fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { + // Ignore other fields for now, can change later if needed. + self.element.fmt(f) + } +} + +impl<'a, E> Element for ElementWrapper<'a, E> +where + E: TElement, +{ + type Impl = SelectorImpl; + + fn match_non_ts_pseudo_class( + &self, + pseudo_class: &NonTSPseudoClass, + context: &mut MatchingContext<Self::Impl>, + ) -> bool { + // Some pseudo-classes need special handling to evaluate them against + // the snapshot. + match *pseudo_class { + // For :link and :visited, we don't actually want to test the + // element state directly. + // + // Instead, we use the `visited_handling` to determine if they + // match. + NonTSPseudoClass::Link => { + return self.is_link() && context.visited_handling().matches_unvisited(); + }, + NonTSPseudoClass::Visited => { + return self.is_link() && context.visited_handling().matches_visited(); + }, + + #[cfg(feature = "gecko")] + NonTSPseudoClass::MozTableBorderNonzero => { + if let Some(snapshot) = self.snapshot() { + if snapshot.has_other_pseudo_class_state() { + return snapshot.mIsTableBorderNonzero(); + } + } + }, + + #[cfg(feature = "gecko")] + NonTSPseudoClass::MozBrowserFrame => { + if let Some(snapshot) = self.snapshot() { + if snapshot.has_other_pseudo_class_state() { + return snapshot.mIsMozBrowserFrame(); + } + } + }, + + #[cfg(feature = "gecko")] + NonTSPseudoClass::MozSelectListBox => { + if let Some(snapshot) = self.snapshot() { + if snapshot.has_other_pseudo_class_state() { + return snapshot.mIsSelectListBox(); + } + } + }, + + // :lang() needs to match using the closest ancestor xml:lang="" or + // lang="" attribtue from snapshots. + NonTSPseudoClass::Lang(ref lang_arg) => { + return self + .element + .match_element_lang(Some(self.get_lang()), lang_arg); + }, + + _ => {}, + } + + let flag = pseudo_class.state_flag(); + if flag.is_empty() { + return self + .element + .match_non_ts_pseudo_class(pseudo_class, context); + } + match self.snapshot().and_then(|s| s.state()) { + Some(snapshot_state) => snapshot_state.intersects(flag), + None => self + .element + .match_non_ts_pseudo_class(pseudo_class, context), + } + } + + fn 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)) + } +} 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..7fa552e458 --- /dev/null +++ b/servo/components/style/invalidation/element/invalidation_map.rs @@ -0,0 +1,545 @@ +/* This Source Code Form is subject to the terms of the Mozilla Public + * License, v. 2.0. If a copy of the MPL was not distributed with this + * file, You can obtain one at https://mozilla.org/MPL/2.0/. */ + +//! Code for invalidations due to state or attribute changes. + +use crate::context::QuirksMode; +use crate::selector_map::{ + MaybeCaseInsensitiveHashMap, PrecomputedHashMap, SelectorMap, SelectorMapEntry, +}; +use crate::selector_parser::SelectorImpl; +use crate::AllocErr; +use crate::{Atom, LocalName, Namespace, ShrinkIfNeeded}; +use dom::{DocumentState, ElementState}; +use selectors::attr::NamespaceConstraint; +use selectors::parser::{Combinator, Component}; +use selectors::parser::{Selector, SelectorIter}; +use selectors::visitor::{SelectorListKind, SelectorVisitor}; +use smallvec::SmallVec; + +/// Mapping between (partial) CompoundSelectors (and the combinator to their +/// right) and the states and attributes they depend on. +/// +/// In general, for all selectors in all applicable stylesheets of the form: +/// +/// |a _ b _ c _ d _ e| +/// +/// Where: +/// * |b| and |d| are simple selectors that depend on state (like :hover) or +/// attributes (like [attr...], .foo, or #foo). +/// * |a|, |c|, and |e| are arbitrary simple selectors that do not depend on +/// state or attributes. +/// +/// We generate a Dependency for both |a _ b:X _| and |a _ b:X _ c _ d:Y _|, +/// even though those selectors may not appear on their own in any stylesheet. +/// This allows us to quickly scan through the dependency sites of all style +/// rules and determine the maximum effect that a given state or attribute +/// change may have on the style of elements in the document. +#[derive(Clone, Debug, MallocSizeOf)] +pub struct Dependency { + /// The dependency selector. + #[cfg_attr( + feature = "gecko", + ignore_malloc_size_of = "CssRules have primary refs, we measure there" + )] + #[cfg_attr(feature = "servo", ignore_malloc_size_of = "Arc")] + pub selector: Selector<SelectorImpl>, + + /// The offset into the selector that we should match on. + pub selector_offset: usize, + + /// The parent dependency for an ancestor selector. For example, consider + /// the following: + /// + /// .foo .bar:where(.baz span) .qux + /// ^ ^ ^ + /// A B C + /// + /// We'd generate: + /// + /// * One dependency for .qux (offset: 0, parent: None) + /// * One dependency for .baz pointing to B with parent being a + /// dependency pointing to C. + /// * One dependency from .bar pointing to C (parent: None) + /// * One dependency from .foo pointing to A (parent: None) + /// + pub parent: Option<Box<Dependency>>, +} + +/// The kind of elements down the tree this dependency may affect. +#[derive(Debug, Eq, PartialEq)] +pub enum DependencyInvalidationKind { + /// This dependency may affect the element that changed itself. + Element, + /// This dependency affects the style of the element itself, and also the + /// style of its descendants. + /// + /// TODO(emilio): Each time this feels more of a hack for eager pseudos... + ElementAndDescendants, + /// This dependency may affect descendants down the tree. + Descendants, + /// This dependency may affect siblings to the right of the element that + /// changed. + Siblings, + /// This dependency may affect slotted elements of the element that changed. + SlottedElements, + /// This dependency may affect parts of the element that changed. + Parts, +} + +impl Dependency { + /// Creates a dummy dependency to invalidate the whole selector. + /// + /// This is necessary because document state invalidation wants to + /// invalidate all elements in the document. + /// + /// The offset is such as that Invalidation::new(self) returns a zero + /// offset. That is, it points to a virtual "combinator" outside of the + /// selector, so calling combinator() on such a dependency will panic. + pub fn for_full_selector_invalidation(selector: Selector<SelectorImpl>) -> Self { + Self { + selector_offset: selector.len() + 1, + selector, + parent: None, + } + } + + /// Returns the combinator to the right of the partial selector this + /// dependency represents. + /// + /// TODO(emilio): Consider storing inline if it helps cache locality? + pub fn combinator(&self) -> Option<Combinator> { + if self.selector_offset == 0 { + return None; + } + + Some( + self.selector + .combinator_at_match_order(self.selector_offset - 1), + ) + } + + /// The kind of invalidation that this would generate. + pub fn invalidation_kind(&self) -> DependencyInvalidationKind { + match self.combinator() { + None => DependencyInvalidationKind::Element, + Some(Combinator::Child) | Some(Combinator::Descendant) => { + DependencyInvalidationKind::Descendants + }, + Some(Combinator::LaterSibling) | Some(Combinator::NextSibling) => { + DependencyInvalidationKind::Siblings + }, + // TODO(emilio): We could look at the selector itself to see if it's + // an eager pseudo, and return only Descendants here if not. + Some(Combinator::PseudoElement) => DependencyInvalidationKind::ElementAndDescendants, + Some(Combinator::SlotAssignment) => DependencyInvalidationKind::SlottedElements, + Some(Combinator::Part) => DependencyInvalidationKind::Parts, + } + } +} + +impl SelectorMapEntry for Dependency { + fn selector(&self) -> SelectorIter<SelectorImpl> { + self.selector.iter_from(self.selector_offset) + } +} + +/// The same, but for state selectors, which can track more exactly what state +/// do they track. +#[derive(Clone, Debug, MallocSizeOf)] +pub struct StateDependency { + /// The other dependency fields. + pub dep: Dependency, + /// The state this dependency is affected by. + pub state: ElementState, +} + +impl SelectorMapEntry for StateDependency { + fn selector(&self) -> SelectorIter<SelectorImpl> { + self.dep.selector() + } +} + +/// The same, but for document state selectors. +#[derive(Clone, Debug, MallocSizeOf)] +pub struct DocumentStateDependency { + /// We track `Dependency` even though we don't need to track an offset, + /// since when it changes it changes for the whole document anyway. + #[cfg_attr( + feature = "gecko", + ignore_malloc_size_of = "CssRules have primary refs, we measure there" + )] + #[cfg_attr(feature = "servo", ignore_malloc_size_of = "Arc")] + pub dependency: Dependency, + /// The state this dependency is affected by. + pub state: DocumentState, +} + +/// A map where we store invalidations. +/// +/// This is slightly different to a SelectorMap, in the sense of that the same +/// selector may appear multiple times. +/// +/// In particular, we want to lookup as few things as possible to get the fewer +/// selectors the better, so this looks up by id, class, or looks at the list of +/// state/other attribute affecting selectors. +#[derive(Clone, Debug, MallocSizeOf)] +pub struct InvalidationMap { + /// A map from a given class name to all the selectors with that class + /// selector. + pub class_to_selector: MaybeCaseInsensitiveHashMap<Atom, SmallVec<[Dependency; 1]>>, + /// A map from a given id to all the selectors with that ID in the + /// stylesheets currently applying to the document. + pub id_to_selector: MaybeCaseInsensitiveHashMap<Atom, SmallVec<[Dependency; 1]>>, + /// A map of all the state dependencies. + pub state_affecting_selectors: SelectorMap<StateDependency>, + /// A list of document state dependencies in the rules we represent. + pub document_state_selectors: Vec<DocumentStateDependency>, + /// A map of other attribute affecting selectors. + pub other_attribute_affecting_selectors: + PrecomputedHashMap<LocalName, SmallVec<[Dependency; 1]>>, +} + +impl InvalidationMap { + /// Creates an empty `InvalidationMap`. + pub fn new() -> Self { + Self { + class_to_selector: MaybeCaseInsensitiveHashMap::new(), + id_to_selector: MaybeCaseInsensitiveHashMap::new(), + state_affecting_selectors: SelectorMap::new(), + document_state_selectors: Vec::new(), + other_attribute_affecting_selectors: PrecomputedHashMap::default(), + } + } + + /// Returns the number of dependencies stored in the invalidation map. + pub fn len(&self) -> usize { + self.state_affecting_selectors.len() + + self.document_state_selectors.len() + + self.other_attribute_affecting_selectors + .iter() + .fold(0, |accum, (_, ref v)| accum + v.len()) + + self.id_to_selector + .iter() + .fold(0, |accum, (_, ref v)| accum + v.len()) + + self.class_to_selector + .iter() + .fold(0, |accum, (_, ref v)| accum + v.len()) + } + + /// Clears this map, leaving it empty. + pub fn clear(&mut self) { + self.class_to_selector.clear(); + self.id_to_selector.clear(); + self.state_affecting_selectors.clear(); + self.document_state_selectors.clear(); + self.other_attribute_affecting_selectors.clear(); + } + + /// Shrink the capacity of hash maps if needed. + pub fn shrink_if_needed(&mut self) { + self.class_to_selector.shrink_if_needed(); + self.id_to_selector.shrink_if_needed(); + self.state_affecting_selectors.shrink_if_needed(); + self.other_attribute_affecting_selectors.shrink_if_needed(); + } + + /// Adds a selector to this `InvalidationMap`. Returns Err(..) to + /// signify OOM. + pub fn note_selector( + &mut self, + selector: &Selector<SelectorImpl>, + quirks_mode: QuirksMode, + ) -> Result<(), AllocErr> { + debug!("InvalidationMap::note_selector({:?})", selector); + + let mut document_state = DocumentState::empty(); + + { + let mut parent_stack = SmallVec::new(); + let mut alloc_error = None; + let mut collector = SelectorDependencyCollector { + map: self, + document_state: &mut document_state, + selector, + parent_selectors: &mut parent_stack, + quirks_mode, + compound_state: PerCompoundState::new(0), + alloc_error: &mut alloc_error, + }; + + let visit_result = collector.visit_whole_selector(); + debug_assert_eq!(!visit_result, alloc_error.is_some()); + if let Some(alloc_error) = alloc_error { + return Err(alloc_error); + } + } + + if !document_state.is_empty() { + let dep = DocumentStateDependency { + state: document_state, + dependency: Dependency::for_full_selector_invalidation(selector.clone()), + }; + self.document_state_selectors.try_reserve(1)?; + self.document_state_selectors.push(dep); + } + + Ok(()) + } +} + +struct PerCompoundState { + /// The offset at which our compound starts. + offset: usize, + + /// The state this compound selector is affected by. + element_state: ElementState, +} + +impl PerCompoundState { + fn new(offset: usize) -> Self { + Self { + offset, + element_state: ElementState::empty(), + } + } +} + +/// A struct that collects invalidations for a given compound selector. +struct SelectorDependencyCollector<'a> { + map: &'a mut InvalidationMap, + + /// The document this _complex_ selector is affected by. + /// + /// We don't need to track state per compound selector, since it's global + /// state and it changes for everything. + document_state: &'a mut DocumentState, + + /// The current selector and offset we're iterating. + selector: &'a Selector<SelectorImpl>, + + /// The stack of parent selectors that we have, and at which offset of the + /// sequence. + /// + /// This starts empty. It grows when we find nested :is and :where selector + /// lists. + parent_selectors: &'a mut SmallVec<[(Selector<SelectorImpl>, usize); 5]>, + + /// The quirks mode of the document where we're inserting dependencies. + quirks_mode: QuirksMode, + + /// State relevant to a given compound selector. + compound_state: PerCompoundState, + + /// The allocation error, if we OOM. + alloc_error: &'a mut Option<AllocErr>, +} + +impl<'a> SelectorDependencyCollector<'a> { + fn visit_whole_selector(&mut self) -> bool { + let iter = self.selector.iter(); + self.visit_whole_selector_from(iter, 0) + } + + fn visit_whole_selector_from( + &mut self, + mut iter: SelectorIter<SelectorImpl>, + mut index: usize, + ) -> bool { + loop { + // Reset the compound state. + self.compound_state = PerCompoundState::new(index); + + // Visit all the simple selectors in this sequence. + for ss in &mut iter { + if !ss.visit(self) { + return false; + } + index += 1; // Account for the simple selector. + } + + if !self.compound_state.element_state.is_empty() { + let dependency = self.dependency(); + let result = self.map.state_affecting_selectors.insert( + StateDependency { + dep: dependency, + state: self.compound_state.element_state, + }, + self.quirks_mode, + ); + if let Err(alloc_error) = result { + *self.alloc_error = Some(alloc_error.into()); + return false; + } + } + + let combinator = iter.next_sequence(); + if combinator.is_none() { + return true; + } + index += 1; // account for the combinator + } + } + + fn add_attr_dependency(&mut self, name: LocalName) -> bool { + let dependency = self.dependency(); + + let map = &mut self.map.other_attribute_affecting_selectors; + if let Err(err) = map.try_reserve(1) { + *self.alloc_error = Some(err.into()); + return false; + } + let vec = map.entry(name).or_default(); + if let Err(err) = vec.try_reserve(1) { + *self.alloc_error = Some(err.into()); + return false; + } + vec.push(dependency); + true + } + + fn dependency(&self) -> Dependency { + let mut parent = None; + + // TODO(emilio): Maybe we should refcount the parent dependencies, or + // cache them or something. + for &(ref selector, ref selector_offset) in self.parent_selectors.iter() { + debug_assert_ne!( + self.compound_state.offset, 0, + "Shouldn't bother creating nested dependencies for the rightmost compound", + ); + let new_parent = Dependency { + selector: selector.clone(), + selector_offset: *selector_offset, + parent, + }; + parent = Some(Box::new(new_parent)); + } + + Dependency { + selector: self.selector.clone(), + selector_offset: self.compound_state.offset, + parent, + } + } +} + +impl<'a> SelectorVisitor for SelectorDependencyCollector<'a> { + type Impl = SelectorImpl; + + fn visit_selector_list( + &mut self, + _list_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((self.selector.clone(), self.compound_state.offset)); + let mut nested = SelectorDependencyCollector { + map: &mut *self.map, + document_state: &mut *self.document_state, + selector, + parent_selectors: &mut *self.parent_selectors, + quirks_mode: self.quirks_mode, + compound_state: PerCompoundState::new(index), + alloc_error: &mut *self.alloc_error, + }; + if !nested.visit_whole_selector_from(iter, index) { + return false; + } + self.parent_selectors.pop(); + } + true + } + + fn visit_simple_selector(&mut self, s: &Component<SelectorImpl>) -> bool { + use crate::selector_parser::NonTSPseudoClass; + + match *s { + Component::ID(ref atom) | Component::Class(ref atom) => { + let dependency = self.dependency(); + let map = match *s { + Component::ID(..) => &mut self.map.id_to_selector, + Component::Class(..) => &mut self.map.class_to_selector, + _ => unreachable!(), + }; + let entry = match map.try_entry(atom.0.clone(), self.quirks_mode) { + Ok(entry) => entry, + Err(err) => { + *self.alloc_error = Some(err.into()); + return false; + }, + }; + let vec = entry.or_insert_with(SmallVec::new); + if let Err(err) = vec.try_reserve(1) { + *self.alloc_error = Some(err.into()); + return false; + } + vec.push(dependency); + true + }, + Component::NonTSPseudoClass(ref pc) => { + self.compound_state.element_state |= pc.state_flag(); + *self.document_state |= pc.document_state_flag(); + + let attr_name = match *pc { + #[cfg(feature = "gecko")] + NonTSPseudoClass::MozTableBorderNonzero => local_name!("border"), + #[cfg(feature = "gecko")] + NonTSPseudoClass::MozBrowserFrame => local_name!("mozbrowser"), + #[cfg(feature = "gecko")] + NonTSPseudoClass::MozSelectListBox => { + // This depends on two attributes. + return self.add_attr_dependency(local_name!("multiple")) && + self.add_attr_dependency(local_name!("size")); + }, + NonTSPseudoClass::Lang(..) => local_name!("lang"), + _ => return true, + }; + + self.add_attr_dependency(attr_name) + }, + _ => true, + } + } + + fn visit_attribute_selector( + &mut self, + _: &NamespaceConstraint<&Namespace>, + local_name: &LocalName, + local_name_lower: &LocalName, + ) -> bool { + if !self.add_attr_dependency(local_name.clone()) { + return false; + } + + if local_name != local_name_lower && !self.add_attr_dependency(local_name_lower.clone()) { + return false; + } + + true + } +} diff --git a/servo/components/style/invalidation/element/invalidator.rs b/servo/components/style/invalidation/element/invalidator.rs new file mode 100644 index 0000000000..00f714c5b1 --- /dev/null +++ b/servo/components/style/invalidation/element/invalidator.rs @@ -0,0 +1,1017 @@ +/* This Source Code Form is subject to the terms of the Mozilla Public + * License, v. 2.0. If a copy of the MPL was not distributed with this + * file, You can obtain one at https://mozilla.org/MPL/2.0/. */ + +//! The struct that takes care of encapsulating all the logic on where and how +//! element styles need to be invalidated. + +use crate::context::StackLimitChecker; +use crate::dom::{TElement, TNode, TShadowRoot}; +use crate::invalidation::element::invalidation_map::{Dependency, DependencyInvalidationKind}; +use selectors::matching::matches_compound_selector_from; +use selectors::matching::{CompoundSelectorMatchingResult, MatchingContext}; +use selectors::parser::{Combinator, Component}; +use selectors::OpaqueElement; +use smallvec::SmallVec; +use std::fmt; +use std::fmt::Write; + +/// A trait to abstract the collection of invalidations for a given pass. +pub trait InvalidationProcessor<'a, E> +where + E: TElement, +{ + /// Whether an invalidation that contains only a pseudo-element selector + /// like ::before or ::after triggers invalidation of the element that would + /// originate it. + fn invalidates_on_pseudo_element(&self) -> bool { + false + } + + /// Whether the invalidation processor only cares about light-tree + /// descendants of a given element, that is, doesn't invalidate + /// pseudo-elements, NAC, shadow dom... + fn light_tree_only(&self) -> bool { + false + } + + /// When a dependency from a :where or :is selector matches, it may still be + /// the case that we don't need to invalidate the full style. Consider the + /// case of: + /// + /// div .foo:where(.bar *, .baz) .qux + /// + /// We can get to the `*` part after a .bar class change, but you only need + /// to restyle the element if it also matches .foo. + /// + /// Similarly, you only need to restyle .baz if the whole result of matching + /// the selector changes. + /// + /// This function is called to check the result of matching the "outer" + /// dependency that we generate for the parent of the `:where` selector, + /// that is, in the case above it should match + /// `div .foo:where(.bar *, .baz)`. + /// + /// Returning true unconditionally here is over-optimistic and may + /// over-invalidate. + fn check_outer_dependency(&mut self, dependency: &Dependency, element: E) -> bool; + + /// The matching context that should be used to process invalidations. + fn matching_context(&mut self) -> &mut MatchingContext<'a, E::Impl>; + + /// Collect invalidations for a given element's descendants and siblings. + /// + /// Returns whether the element itself was invalidated. + fn collect_invalidations( + &mut self, + element: E, + self_invalidations: &mut InvalidationVector<'a>, + descendant_invalidations: &mut DescendantInvalidationLists<'a>, + sibling_invalidations: &mut InvalidationVector<'a>, + ) -> bool; + + /// Returns whether the invalidation process should process the descendants + /// of the given element. + fn should_process_descendants(&mut self, element: E) -> bool; + + /// Executes an arbitrary action when the recursion limit is exceded (if + /// any). + fn recursion_limit_exceeded(&mut self, element: E); + + /// Executes an action when `Self` is invalidated. + fn invalidated_self(&mut self, element: E); + + /// Executes an action when `sibling` is invalidated as a sibling of + /// `of`. + fn invalidated_sibling(&mut self, sibling: E, of: E); + + /// Executes an action when any descendant of `Self` is invalidated. + fn invalidated_descendants(&mut self, element: E, child: E); +} + +/// Different invalidation lists for descendants. +#[derive(Debug, Default)] +pub struct DescendantInvalidationLists<'a> { + /// Invalidations for normal DOM children and pseudo-elements. + /// + /// TODO(emilio): Having a list of invalidations just for pseudo-elements + /// may save some work here and there. + pub dom_descendants: InvalidationVector<'a>, + /// Invalidations for slotted children of an element. + pub slotted_descendants: InvalidationVector<'a>, + /// Invalidations for ::part()s of an element. + pub parts: InvalidationVector<'a>, +} + +impl<'a> DescendantInvalidationLists<'a> { + fn is_empty(&self) -> bool { + self.dom_descendants.is_empty() && + self.slotted_descendants.is_empty() && + self.parts.is_empty() + } +} + +/// The struct that takes care of encapsulating all the logic on where and how +/// element styles need to be invalidated. +pub struct TreeStyleInvalidator<'a, 'b, E, P: 'a> +where + 'b: 'a, + E: TElement, + P: InvalidationProcessor<'b, E>, +{ + element: E, + stack_limit_checker: Option<&'a StackLimitChecker>, + processor: &'a mut P, + _marker: ::std::marker::PhantomData<&'b ()>, +} + +/// A vector of invalidations, optimized for small invalidation sets. +pub type InvalidationVector<'a> = SmallVec<[Invalidation<'a>; 10]>; + +/// The kind of descendant invalidation we're processing. +#[derive(Clone, Copy, Debug, Eq, PartialEq)] +enum DescendantInvalidationKind { + /// A DOM descendant invalidation. + Dom, + /// A ::slotted() descendant invalidation. + Slotted, + /// A ::part() descendant invalidation. + Part, +} + +/// The kind of invalidation we're processing. +/// +/// We can use this to avoid pushing invalidations of the same kind to our +/// descendants or siblings. +#[derive(Clone, Copy, Debug, Eq, PartialEq)] +enum InvalidationKind { + Descendant(DescendantInvalidationKind), + Sibling, +} + +/// An `Invalidation` is a complex selector that describes which elements, +/// relative to a current element we are processing, must be restyled. +#[derive(Clone)] +pub struct Invalidation<'a> { + /// The dependency that generated this invalidation. + /// + /// Note that the offset inside the dependency is not really useful after + /// construction. + dependency: &'a Dependency, + /// The right shadow host from where the rule came from, if any. + /// + /// This is needed to ensure that we match the selector with the right + /// state, as whether some selectors like :host and ::part() match depends + /// on it. + scope: Option<OpaqueElement>, + /// The offset of the selector pointing to a compound selector. + /// + /// This order is a "parse order" offset, that is, zero is the leftmost part + /// of the selector written as parsed / serialized. + /// + /// It is initialized from the offset from `dependency`. + offset: usize, + /// Whether the invalidation was already matched by any previous sibling or + /// ancestor. + /// + /// If this is the case, we can avoid pushing invalidations generated by + /// this one if the generated invalidation is effective for all the siblings + /// or descendants after us. + matched_by_any_previous: bool, +} + +impl<'a> Invalidation<'a> { + /// Create a new invalidation for matching a dependency. + pub fn new(dependency: &'a Dependency, scope: Option<OpaqueElement>) -> Self { + debug_assert!( + dependency.selector_offset == dependency.selector.len() + 1 || + dependency.invalidation_kind() != DependencyInvalidationKind::Element, + "No point to this, if the dependency matched the element we should just invalidate it" + ); + Self { + dependency, + scope, + // + 1 to go past the combinator. + offset: dependency.selector.len() + 1 - dependency.selector_offset, + matched_by_any_previous: false, + } + } + + /// Whether this invalidation is effective for the next sibling or + /// descendant after us. + fn effective_for_next(&self) -> bool { + if self.offset == 0 { + return true; + } + + // TODO(emilio): For pseudo-elements this should be mostly false, except + // for the weird pseudos in <input type="number">. + // + // We should be able to do better here! + match self + .dependency + .selector + .combinator_at_parse_order(self.offset - 1) + { + Combinator::Descendant | Combinator::LaterSibling | Combinator::PseudoElement => true, + Combinator::Part | + Combinator::SlotAssignment | + Combinator::NextSibling | + Combinator::Child => false, + } + } + + fn kind(&self) -> InvalidationKind { + if self.offset == 0 { + return InvalidationKind::Descendant(DescendantInvalidationKind::Dom); + } + + match self + .dependency + .selector + .combinator_at_parse_order(self.offset - 1) + { + Combinator::Child | Combinator::Descendant | Combinator::PseudoElement => { + InvalidationKind::Descendant(DescendantInvalidationKind::Dom) + }, + Combinator::Part => InvalidationKind::Descendant(DescendantInvalidationKind::Part), + Combinator::SlotAssignment => { + InvalidationKind::Descendant(DescendantInvalidationKind::Slotted) + }, + Combinator::NextSibling | Combinator::LaterSibling => InvalidationKind::Sibling, + } + } +} + +impl<'a> fmt::Debug for Invalidation<'a> { + fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { + use cssparser::ToCss; + + f.write_str("Invalidation(")?; + for component in self + .dependency + .selector + .iter_raw_parse_order_from(self.offset) + { + if matches!(*component, Component::Combinator(..)) { + break; + } + component.to_css(f)?; + } + f.write_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, E, P: 'a> TreeStyleInvalidator<'a, 'b, E, P> +where + 'b: 'a, + E: TElement, + P: InvalidationProcessor<'b, E>, +{ + /// Trivially constructs a new `TreeStyleInvalidator`. + pub fn new( + element: E, + stack_limit_checker: Option<&'a StackLimitChecker>, + processor: &'a mut P, + ) -> Self { + Self { + element, + stack_limit_checker, + processor, + _marker: ::std::marker::PhantomData, + } + } + + /// Perform the invalidation pass. + pub fn invalidate(mut self) -> InvalidationResult { + debug!("StyleTreeInvalidator::invalidate({:?})", self.element); + + let mut self_invalidations = InvalidationVector::new(); + let mut descendant_invalidations = DescendantInvalidationLists::default(); + let mut sibling_invalidations = InvalidationVector::new(); + + let mut invalidated_self = self.processor.collect_invalidations( + self.element, + &mut self_invalidations, + &mut descendant_invalidations, + &mut sibling_invalidations, + ); + + debug!("Collected invalidations (self: {}): ", invalidated_self); + debug!( + " > self: {}, {:?}", + self_invalidations.len(), + self_invalidations + ); + debug!(" > descendants: {:?}", descendant_invalidations); + debug!( + " > siblings: {}, {:?}", + sibling_invalidations.len(), + sibling_invalidations + ); + + let invalidated_self_from_collection = invalidated_self; + + invalidated_self |= self.process_descendant_invalidations( + &self_invalidations, + &mut descendant_invalidations, + &mut sibling_invalidations, + DescendantInvalidationKind::Dom, + ); + + if invalidated_self && !invalidated_self_from_collection { + self.processor.invalidated_self(self.element); + } + + let invalidated_descendants = self.invalidate_descendants(&descendant_invalidations); + let invalidated_siblings = self.invalidate_siblings(&mut sibling_invalidations); + + InvalidationResult { + invalidated_self, + invalidated_descendants, + invalidated_siblings, + } + } + + /// Go through later DOM siblings, invalidating style as needed using the + /// `sibling_invalidations` list. + /// + /// Returns whether any sibling's style or any sibling descendant's style + /// was invalidated. + fn invalidate_siblings(&mut self, sibling_invalidations: &mut InvalidationVector<'b>) -> bool { + if sibling_invalidations.is_empty() { + return false; + } + + let mut current = self.element.next_sibling_element(); + let mut any_invalidated = false; + + while let Some(sibling) = current { + let mut sibling_invalidator = + TreeStyleInvalidator::new(sibling, self.stack_limit_checker, self.processor); + + let mut invalidations_for_descendants = DescendantInvalidationLists::default(); + let invalidated_sibling = sibling_invalidator.process_sibling_invalidations( + &mut invalidations_for_descendants, + sibling_invalidations, + ); + + if invalidated_sibling { + sibling_invalidator + .processor + .invalidated_sibling(sibling, self.element); + } + + any_invalidated |= invalidated_sibling; + + any_invalidated |= + sibling_invalidator.invalidate_descendants(&invalidations_for_descendants); + + if sibling_invalidations.is_empty() { + break; + } + + current = sibling.next_sibling_element(); + } + + any_invalidated + } + + fn invalidate_pseudo_element_or_nac( + &mut self, + child: E, + invalidations: &[Invalidation<'b>], + ) -> bool { + let mut sibling_invalidations = InvalidationVector::new(); + + let result = self.invalidate_child( + child, + invalidations, + &mut sibling_invalidations, + DescendantInvalidationKind::Dom, + ); + + // Roots of NAC subtrees can indeed generate sibling invalidations, but + // they can be just ignored, since they have no siblings. + // + // Note that we can end up testing selectors that wouldn't end up + // matching due to this being NAC, like those coming from document + // rules, but we overinvalidate instead of checking this. + + result + } + + /// Invalidate a child and recurse down invalidating its descendants if + /// needed. + fn invalidate_child( + &mut self, + child: E, + invalidations: &[Invalidation<'b>], + sibling_invalidations: &mut InvalidationVector<'b>, + descendant_invalidation_kind: DescendantInvalidationKind, + ) -> bool { + let mut invalidations_for_descendants = DescendantInvalidationLists::default(); + + let mut invalidated_child = false; + let invalidated_descendants = { + let mut child_invalidator = + TreeStyleInvalidator::new(child, self.stack_limit_checker, self.processor); + + invalidated_child |= child_invalidator.process_sibling_invalidations( + &mut invalidations_for_descendants, + sibling_invalidations, + ); + + invalidated_child |= child_invalidator.process_descendant_invalidations( + invalidations, + &mut invalidations_for_descendants, + sibling_invalidations, + descendant_invalidation_kind, + ); + + if invalidated_child { + child_invalidator.processor.invalidated_self(child); + } + + child_invalidator.invalidate_descendants(&invalidations_for_descendants) + }; + + // The child may not be a flattened tree child of the current element, + // but may be arbitrarily deep. + // + // Since we keep the traversal flags in terms of the flattened tree, + // we need to propagate it as appropriate. + if invalidated_child || invalidated_descendants { + self.processor.invalidated_descendants(self.element, child); + } + + invalidated_child || invalidated_descendants + } + + fn invalidate_nac(&mut self, invalidations: &[Invalidation<'b>]) -> bool { + let mut any_nac_root = false; + + let element = self.element; + element.each_anonymous_content_child(|nac| { + any_nac_root |= self.invalidate_pseudo_element_or_nac(nac, invalidations); + }); + + any_nac_root + } + + // NB: It's important that this operates on DOM children, which is what + // selector-matching operates on. + fn invalidate_dom_descendants_of( + &mut self, + parent: E::ConcreteNode, + invalidations: &[Invalidation<'b>], + ) -> bool { + let mut any_descendant = false; + + let mut sibling_invalidations = InvalidationVector::new(); + for child in parent.dom_children() { + let child = match child.as_element() { + Some(e) => e, + None => continue, + }; + + any_descendant |= self.invalidate_child( + child, + invalidations, + &mut sibling_invalidations, + DescendantInvalidationKind::Dom, + ); + } + + any_descendant + } + + fn invalidate_parts_in_shadow_tree( + &mut self, + shadow: <E::ConcreteNode as TNode>::ConcreteShadowRoot, + invalidations: &[Invalidation<'b>], + ) -> bool { + debug_assert!(!invalidations.is_empty()); + + let mut any = false; + let mut sibling_invalidations = InvalidationVector::new(); + + for node in shadow.as_node().dom_descendants() { + let element = match node.as_element() { + Some(e) => e, + None => continue, + }; + + if element.has_part_attr() { + any |= self.invalidate_child( + element, + invalidations, + &mut sibling_invalidations, + DescendantInvalidationKind::Part, + ); + debug_assert!( + sibling_invalidations.is_empty(), + "::part() shouldn't have sibling combinators to the right, \ + this makes no sense! {:?}", + sibling_invalidations + ); + } + + if let Some(shadow) = element.shadow_root() { + if element.exports_any_part() { + any |= self.invalidate_parts_in_shadow_tree(shadow, invalidations) + } + } + } + + any + } + + fn invalidate_parts(&mut self, invalidations: &[Invalidation<'b>]) -> bool { + if invalidations.is_empty() { + return false; + } + + let shadow = match self.element.shadow_root() { + Some(s) => s, + None => return false, + }; + + self.invalidate_parts_in_shadow_tree(shadow, invalidations) + } + + fn invalidate_slotted_elements(&mut self, invalidations: &[Invalidation<'b>]) -> bool { + if invalidations.is_empty() { + return false; + } + + let slot = self.element; + self.invalidate_slotted_elements_in_slot(slot, invalidations) + } + + fn invalidate_slotted_elements_in_slot( + &mut self, + slot: E, + invalidations: &[Invalidation<'b>], + ) -> bool { + let mut any = false; + + let mut sibling_invalidations = InvalidationVector::new(); + for node in slot.slotted_nodes() { + let element = match node.as_element() { + Some(e) => e, + None => continue, + }; + + if element.is_html_slot_element() { + any |= self.invalidate_slotted_elements_in_slot(element, invalidations); + } else { + any |= self.invalidate_child( + element, + invalidations, + &mut sibling_invalidations, + DescendantInvalidationKind::Slotted, + ); + } + + debug_assert!( + sibling_invalidations.is_empty(), + "::slotted() shouldn't have sibling combinators to the right, \ + this makes no sense! {:?}", + sibling_invalidations + ); + } + + any + } + + fn invalidate_non_slotted_descendants(&mut self, invalidations: &[Invalidation<'b>]) -> bool { + if invalidations.is_empty() { + return false; + } + + if self.processor.light_tree_only() { + let node = self.element.as_node(); + return self.invalidate_dom_descendants_of(node, invalidations); + } + + let mut any_descendant = false; + + // NOTE(emilio): This is only needed for Shadow DOM to invalidate + // correctly on :host(..) changes. Instead of doing this, we could add + // a third kind of invalidation list that walks shadow root children, + // but it's not clear it's worth it. + // + // Also, it's needed as of right now for document state invalidation, + // where we rely on iterating every element that ends up in the composed + // doc, but we could fix that invalidating per subtree. + if let Some(root) = self.element.shadow_root() { + any_descendant |= self.invalidate_dom_descendants_of(root.as_node(), invalidations); + } + + if let Some(marker) = self.element.marker_pseudo_element() { + any_descendant |= self.invalidate_pseudo_element_or_nac(marker, invalidations); + } + + if let Some(before) = self.element.before_pseudo_element() { + any_descendant |= self.invalidate_pseudo_element_or_nac(before, invalidations); + } + + let node = self.element.as_node(); + any_descendant |= self.invalidate_dom_descendants_of(node, invalidations); + + if let Some(after) = self.element.after_pseudo_element() { + any_descendant |= self.invalidate_pseudo_element_or_nac(after, invalidations); + } + + any_descendant |= self.invalidate_nac(invalidations); + + any_descendant + } + + /// Given the descendant invalidation lists, go through the current + /// element's descendants, and invalidate style on them. + fn invalidate_descendants(&mut self, invalidations: &DescendantInvalidationLists<'b>) -> bool { + if invalidations.is_empty() { + return false; + } + + debug!( + "StyleTreeInvalidator::invalidate_descendants({:?})", + self.element + ); + debug!(" > {:?}", invalidations); + + let should_process = self.processor.should_process_descendants(self.element); + + if !should_process { + return false; + } + + if let Some(checker) = self.stack_limit_checker { + if checker.limit_exceeded() { + self.processor.recursion_limit_exceeded(self.element); + return true; + } + } + + let mut any_descendant = false; + + any_descendant |= self.invalidate_non_slotted_descendants(&invalidations.dom_descendants); + any_descendant |= self.invalidate_slotted_elements(&invalidations.slotted_descendants); + any_descendant |= self.invalidate_parts(&invalidations.parts); + + any_descendant + } + + /// Process the given sibling invalidations coming from our previous + /// sibling. + /// + /// The sibling invalidations are somewhat special because they can be + /// modified on the fly. New invalidations may be added and removed. + /// + /// In particular, all descendants get the same set of invalidations from + /// the parent, but the invalidations from a given sibling depend on the + /// ones we got from the previous one. + /// + /// Returns whether invalidated the current element's style. + fn process_sibling_invalidations( + &mut self, + descendant_invalidations: &mut DescendantInvalidationLists<'b>, + sibling_invalidations: &mut InvalidationVector<'b>, + ) -> bool { + let mut i = 0; + let mut new_sibling_invalidations = InvalidationVector::new(); + let mut invalidated_self = false; + + while i < sibling_invalidations.len() { + let result = self.process_invalidation( + &sibling_invalidations[i], + descendant_invalidations, + &mut new_sibling_invalidations, + InvalidationKind::Sibling, + ); + + invalidated_self |= result.invalidated_self; + sibling_invalidations[i].matched_by_any_previous |= result.matched; + if sibling_invalidations[i].effective_for_next() { + i += 1; + } else { + sibling_invalidations.remove(i); + } + } + + sibling_invalidations.extend(new_sibling_invalidations.drain(..)); + invalidated_self + } + + /// Process a given invalidation list coming from our parent, + /// adding to `descendant_invalidations` and `sibling_invalidations` as + /// needed. + /// + /// Returns whether our style was invalidated as a result. + fn process_descendant_invalidations( + &mut self, + invalidations: &[Invalidation<'b>], + descendant_invalidations: &mut DescendantInvalidationLists<'b>, + sibling_invalidations: &mut InvalidationVector<'b>, + descendant_invalidation_kind: DescendantInvalidationKind, + ) -> bool { + let mut invalidated = false; + + for invalidation in invalidations { + let result = self.process_invalidation( + invalidation, + descendant_invalidations, + sibling_invalidations, + InvalidationKind::Descendant(descendant_invalidation_kind), + ); + + invalidated |= result.invalidated_self; + if invalidation.effective_for_next() { + let mut invalidation = invalidation.clone(); + invalidation.matched_by_any_previous |= result.matched; + debug_assert_eq!( + descendant_invalidation_kind, + DescendantInvalidationKind::Dom, + "Slotted or part invalidations don't propagate." + ); + descendant_invalidations.dom_descendants.push(invalidation); + } + } + + invalidated + } + + /// Processes a given invalidation, potentially invalidating the style of + /// the current element. + /// + /// Returns whether invalidated the style of the element, and whether the + /// invalidation should be effective to subsequent siblings or descendants + /// down in the tree. + fn process_invalidation( + &mut self, + invalidation: &Invalidation<'b>, + descendant_invalidations: &mut DescendantInvalidationLists<'b>, + sibling_invalidations: &mut InvalidationVector<'b>, + invalidation_kind: InvalidationKind, + ) -> SingleInvalidationResult { + debug!( + "TreeStyleInvalidator::process_invalidation({:?}, {:?}, {:?})", + self.element, invalidation, invalidation_kind + ); + + let matching_result = { + let context = self.processor.matching_context(); + context.current_host = invalidation.scope; + + matches_compound_selector_from( + &invalidation.dependency.selector, + invalidation.offset, + context, + &self.element, + ) + }; + + let next_invalidation = match matching_result { + CompoundSelectorMatchingResult::NotMatched => { + return SingleInvalidationResult { + invalidated_self: false, + matched: false, + } + }, + CompoundSelectorMatchingResult::FullyMatched => { + debug!(" > Invalidation matched completely"); + // We matched completely. If we're an inner selector now we need + // to go outside our selector and carry on invalidating. + let mut cur_dependency = invalidation.dependency; + loop { + cur_dependency = match cur_dependency.parent { + None => { + return SingleInvalidationResult { + invalidated_self: true, + matched: true, + } + }, + Some(ref p) => &**p, + }; + + debug!(" > Checking outer dependency {:?}", cur_dependency); + + // The inner selector changed, now check if the full + // previous part of the selector did, before keeping + // checking for descendants. + if !self + .processor + .check_outer_dependency(cur_dependency, self.element) + { + return SingleInvalidationResult { + invalidated_self: false, + matched: false, + }; + } + + if cur_dependency.invalidation_kind() == DependencyInvalidationKind::Element { + continue; + } + + debug!(" > Generating invalidation"); + break Invalidation::new(cur_dependency, invalidation.scope); + } + }, + CompoundSelectorMatchingResult::Matched { + next_combinator_offset, + } => Invalidation { + dependency: invalidation.dependency, + scope: invalidation.scope, + offset: next_combinator_offset + 1, + matched_by_any_previous: false, + }, + }; + + debug_assert_ne!( + next_invalidation.offset, 0, + "Rightmost selectors shouldn't generate more invalidations", + ); + + let mut invalidated_self = false; + let next_combinator = next_invalidation + .dependency + .selector + .combinator_at_parse_order(next_invalidation.offset - 1); + + if matches!(next_combinator, Combinator::PseudoElement) && + self.processor.invalidates_on_pseudo_element() + { + // We need to invalidate the element whenever pseudos change, for + // two reasons: + // + // * Eager pseudo styles are stored as part of the originating + // element's computed style. + // + // * Lazy pseudo-styles might be cached on the originating + // element's pseudo-style cache. + // + // This could be more fine-grained (perhaps with a RESTYLE_PSEUDOS + // hint?). + // + // Note that we'll also restyle the pseudo-element because it would + // match this invalidation. + // + // FIXME: For non-element-backed pseudos this is still not quite + // correct. For example for ::selection even though we invalidate + // the style properly there's nothing that triggers a repaint + // necessarily. Though this matches old Gecko behavior, and the + // ::selection implementation needs to change significantly anyway + // to implement https://github.com/w3c/csswg-drafts/issues/2474 for + // example. + invalidated_self = true; + } + + debug!( + " > Invalidation matched, next: {:?}, ({:?})", + next_invalidation, next_combinator + ); + + let next_invalidation_kind = next_invalidation.kind(); + + // We can skip pushing under some circumstances, and we should + // because otherwise the invalidation list could grow + // exponentially. + // + // * First of all, both invalidations need to be of the same + // kind. This is because of how we propagate them going to + // the right of the tree for sibling invalidations and going + // down the tree for children invalidations. A sibling + // invalidation that ends up generating a children + // invalidation ends up (correctly) in five different lists, + // not in the same list five different times. + // + // * Then, the invalidation needs to be matched by a previous + // ancestor/sibling, in order to know that this invalidation + // has been generated already. + // + // * Finally, the new invalidation needs to be + // `effective_for_next()`, in order for us to know that it is + // still in the list, since we remove the dependencies that + // aren't from the lists for our children / siblings. + // + // To go through an example, let's imagine we are processing a + // dom subtree like: + // + // <div><address><div><div/></div></address></div> + // + // And an invalidation list with a single invalidation like: + // + // [div div div] + // + // When we process the invalidation list for the outer div, we + // match it, and generate a `div div` invalidation, so for the + // <address> child we have: + // + // [div div div, div div] + // + // With the first of them marked as `matched`. + // + // When we process the <address> child, we don't match any of + // them, so both invalidations go untouched to our children. + // + // When we process the second <div>, we match _both_ + // invalidations. + // + // However, when matching the first, we can tell it's been + // matched, and not push the corresponding `div div` + // invalidation, since we know it's necessarily already on the + // list. + // + // Thus, without skipping the push, we'll arrive to the + // innermost <div> with: + // + // [div div div, div div, div div, div] + // + // While skipping it, we won't arrive here with duplicating + // dependencies: + // + // [div div div, div div, div] + // + let can_skip_pushing = next_invalidation_kind == invalidation_kind && + invalidation.matched_by_any_previous && + next_invalidation.effective_for_next(); + + if can_skip_pushing { + debug!( + " > Can avoid push, since the invalidation had \ + already been matched before" + ); + } else { + match next_invalidation_kind { + InvalidationKind::Descendant(DescendantInvalidationKind::Dom) => { + descendant_invalidations + .dom_descendants + .push(next_invalidation); + }, + InvalidationKind::Descendant(DescendantInvalidationKind::Part) => { + descendant_invalidations.parts.push(next_invalidation); + }, + InvalidationKind::Descendant(DescendantInvalidationKind::Slotted) => { + descendant_invalidations + .slotted_descendants + .push(next_invalidation); + }, + InvalidationKind::Sibling => { + sibling_invalidations.push(next_invalidation); + }, + } + } + + SingleInvalidationResult { + invalidated_self, + matched: true, + } + } +} diff --git a/servo/components/style/invalidation/element/mod.rs b/servo/components/style/invalidation/element/mod.rs new file mode 100644 index 0000000000..1f19cc54f5 --- /dev/null +++ b/servo/components/style/invalidation/element/mod.rs @@ -0,0 +1,12 @@ +/* This Source Code Form is subject to the terms of the Mozilla Public + * License, v. 2.0. If a copy of the MPL was not distributed with this + * file, You can obtain one at https://mozilla.org/MPL/2.0/. */ + +//! Invalidation of element styles due to attribute or style changes. + +pub mod document_state; +pub mod element_wrapper; +pub mod invalidation_map; +pub mod invalidator; +pub mod restyle_hints; +pub mod state_and_attributes; diff --git a/servo/components/style/invalidation/element/restyle_hints.rs b/servo/components/style/invalidation/element/restyle_hints.rs new file mode 100644 index 0000000000..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..1ead300a87 --- /dev/null +++ b/servo/components/style/invalidation/element/state_and_attributes.rs @@ -0,0 +1,552 @@ +/* This Source Code Form is subject to the terms of the Mozilla Public + * License, v. 2.0. If a copy of the MPL was not distributed with this + * file, You can obtain one at https://mozilla.org/MPL/2.0/. */ + +//! An invalidation processor for style changes due to state and attribute +//! changes. + +use crate::context::SharedStyleContext; +use crate::data::ElementData; +use crate::dom::{TElement, TNode}; +use crate::invalidation::element::element_wrapper::{ElementSnapshot, ElementWrapper}; +use crate::invalidation::element::invalidation_map::*; +use crate::invalidation::element::invalidator::{DescendantInvalidationLists, InvalidationVector}; +use crate::invalidation::element::invalidator::{Invalidation, InvalidationProcessor}; +use crate::invalidation::element::restyle_hints::RestyleHint; +use crate::selector_map::SelectorMap; +use crate::selector_parser::Snapshot; +use crate::stylesheets::origin::OriginSet; +use crate::{Atom, WeakAtom}; +use dom::ElementState; +use selectors::attr::CaseSensitivity; +use selectors::matching::{ + matches_selector, MatchingContext, MatchingMode, NeedsSelectorFlags, VisitedHandlingMode, +}; +use selectors::NthIndexCache; +use smallvec::SmallVec; + +/// The collector implementation. +struct Collector<'a, 'b: 'a, 'selectors: 'a, E> +where + E: TElement, +{ + element: E, + wrapper: ElementWrapper<'b, E>, + snapshot: &'a Snapshot, + matching_context: &'a mut MatchingContext<'b, E::Impl>, + lookup_element: E, + removed_id: Option<&'a WeakAtom>, + added_id: Option<&'a WeakAtom>, + classes_removed: &'a SmallVec<[Atom; 8]>, + classes_added: &'a SmallVec<[Atom; 8]>, + state_changes: ElementState, + descendant_invalidations: &'a mut DescendantInvalidationLists<'selectors>, + sibling_invalidations: &'a mut InvalidationVector<'selectors>, + invalidates_self: bool, +} + +/// An invalidation processor for style changes due to state and attribute +/// changes. +pub struct StateAndAttrInvalidationProcessor<'a, 'b: 'a, E: TElement> { + shared_context: &'a SharedStyleContext<'b>, + element: E, + data: &'a mut ElementData, + matching_context: MatchingContext<'a, E::Impl>, +} + +impl<'a, 'b: 'a, E: TElement + 'b> StateAndAttrInvalidationProcessor<'a, 'b, E> { + /// Creates a new StateAndAttrInvalidationProcessor. + pub fn new( + shared_context: &'a SharedStyleContext<'b>, + element: E, + data: &'a mut ElementData, + nth_index_cache: &'a mut NthIndexCache, + ) -> Self { + let matching_context = MatchingContext::new_for_visited( + MatchingMode::Normal, + None, + nth_index_cache, + VisitedHandlingMode::AllLinksVisitedAndUnvisited, + shared_context.quirks_mode(), + NeedsSelectorFlags::No, + ); + + Self { + shared_context, + element, + data, + matching_context, + } + } +} + +/// Checks a dependency against a given element and wrapper, to see if something +/// changed. +pub fn check_dependency<E, W>( + dependency: &Dependency, + element: &E, + wrapper: &W, + context: &mut MatchingContext<'_, E::Impl>, +) -> bool +where + E: TElement, + W: selectors::Element<Impl = E::Impl>, +{ + let matches_now = matches_selector( + &dependency.selector, + dependency.selector_offset, + None, + element, + context, + ); + + let matched_then = matches_selector( + &dependency.selector, + dependency.selector_offset, + None, + wrapper, + context, + ); + + matched_then != matches_now +} + +/// Whether we should process the descendants of a given element for style +/// invalidation. +pub fn should_process_descendants(data: &ElementData) -> bool { + !data.styles.is_display_none() && !data.hint.contains(RestyleHint::RESTYLE_DESCENDANTS) +} + +/// Propagates the bits after invalidating a descendant child. +pub fn propagate_dirty_bit_up_to<E>(ancestor: E, child: E) +where + E: TElement, +{ + // The child may not be a flattened tree child of the current element, + // but may be arbitrarily deep. + // + // Since we keep the traversal flags in terms of the flattened tree, + // we need to propagate it as appropriate. + let mut current = child.traversal_parent(); + while let Some(parent) = current.take() { + unsafe { parent.set_dirty_descendants() }; + current = parent.traversal_parent(); + + if parent == ancestor { + return; + } + } + debug_assert!( + false, + "Should've found {:?} as an ancestor of {:?}", + ancestor, child + ); +} + +/// Propagates the bits after invalidating a descendant child, if needed. +pub fn invalidated_descendants<E>(element: E, child: E) +where + E: TElement, +{ + if !child.has_data() { + return; + } + propagate_dirty_bit_up_to(element, child) +} + +/// Sets the appropriate restyle hint after invalidating the style of a given +/// element. +pub fn invalidated_self<E>(element: E) -> bool +where + E: TElement, +{ + let mut data = match element.mutate_data() { + Some(data) => data, + None => return false, + }; + data.hint.insert(RestyleHint::RESTYLE_SELF); + true +} + +/// Sets the appropriate hint after invalidating the style of a sibling. +pub fn invalidated_sibling<E>(element: E, of: E) +where + E: TElement, +{ + debug_assert_eq!( + element.as_node().parent_node(), + of.as_node().parent_node(), + "Should be siblings" + ); + if !invalidated_self(element) { + return; + } + if element.traversal_parent() != of.traversal_parent() { + let parent = element.as_node().parent_element_or_host(); + debug_assert!( + parent.is_some(), + "How can we have siblings without parent nodes?" + ); + if let Some(e) = parent { + propagate_dirty_bit_up_to(e, element) + } + } +} + +impl<'a, 'b: 'a, E: 'a> InvalidationProcessor<'a, E> + for StateAndAttrInvalidationProcessor<'a, 'b, E> +where + E: TElement, +{ + /// We need to invalidate style on pseudo-elements, in order to process + /// changes that could otherwise end up in ::before or ::after content being + /// generated, and invalidate lazy pseudo caches. + fn invalidates_on_pseudo_element(&self) -> bool { + true + } + + fn check_outer_dependency(&mut self, dependency: &Dependency, element: E) -> bool { + // We cannot assert about `element` having a snapshot here (in fact it + // most likely won't), because it may be an arbitrary descendant or + // later-sibling of the element we started invalidating with. + let wrapper = ElementWrapper::new(element, &*self.shared_context.snapshot_map); + check_dependency(dependency, &element, &wrapper, &mut self.matching_context) + } + + fn matching_context(&mut self) -> &mut MatchingContext<'a, E::Impl> { + &mut self.matching_context + } + + fn collect_invalidations( + &mut self, + element: E, + _self_invalidations: &mut InvalidationVector<'a>, + descendant_invalidations: &mut DescendantInvalidationLists<'a>, + sibling_invalidations: &mut InvalidationVector<'a>, + ) -> bool { + debug_assert_eq!(element, self.element); + debug_assert!(element.has_snapshot(), "Why bothering?"); + + let wrapper = ElementWrapper::new(element, &*self.shared_context.snapshot_map); + + let state_changes = wrapper.state_changes(); + let snapshot = wrapper.snapshot().expect("has_snapshot lied"); + + if !snapshot.has_attrs() && state_changes.is_empty() { + return false; + } + + let mut classes_removed = SmallVec::<[Atom; 8]>::new(); + let mut classes_added = SmallVec::<[Atom; 8]>::new(); + if snapshot.class_changed() { + // TODO(emilio): Do this more efficiently! + snapshot.each_class(|c| { + if !element.has_class(c, CaseSensitivity::CaseSensitive) { + classes_removed.push(c.0.clone()) + } + }); + + element.each_class(|c| { + if !snapshot.has_class(c, CaseSensitivity::CaseSensitive) { + classes_added.push(c.0.clone()) + } + }) + } + + let mut id_removed = None; + let mut id_added = None; + if snapshot.id_changed() { + let old_id = snapshot.id_attr(); + let current_id = element.id(); + + if old_id != current_id { + id_removed = old_id; + id_added = current_id; + } + } + + if log_enabled!(::log::Level::Debug) { + debug!("Collecting changes for: {:?}", element); + if !state_changes.is_empty() { + debug!(" > state: {:?}", state_changes); + } + if snapshot.id_changed() { + debug!(" > id changed: +{:?} -{:?}", id_added, id_removed); + } + if snapshot.class_changed() { + debug!( + " > class changed: +{:?} -{:?}", + classes_added, classes_removed + ); + } + let mut attributes_changed = false; + snapshot.each_attr_changed(|_| { + attributes_changed = true; + }); + if attributes_changed { + debug!( + " > attributes changed, old: {}", + snapshot.debug_list_attributes() + ) + } + } + + let lookup_element = if element.implemented_pseudo_element().is_some() { + element.pseudo_element_originating_element().unwrap() + } else { + element + }; + + let mut shadow_rule_datas = SmallVec::<[_; 3]>::new(); + let matches_document_author_rules = + element.each_applicable_non_document_style_rule_data(|data, host| { + shadow_rule_datas.push((data, host.opaque())) + }); + + let invalidated_self = { + let mut collector = Collector { + wrapper, + lookup_element, + state_changes, + element, + snapshot: &snapshot, + matching_context: &mut self.matching_context, + removed_id: id_removed, + added_id: id_added, + classes_removed: &classes_removed, + classes_added: &classes_added, + descendant_invalidations, + sibling_invalidations, + invalidates_self: false, + }; + + let document_origins = if !matches_document_author_rules { + OriginSet::ORIGIN_USER_AGENT | OriginSet::ORIGIN_USER + } else { + OriginSet::all() + }; + + for (cascade_data, origin) in self.shared_context.stylist.iter_origins() { + if document_origins.contains(origin.into()) { + collector + .collect_dependencies_in_invalidation_map(cascade_data.invalidation_map()); + } + } + + for &(ref data, ref host) in &shadow_rule_datas { + collector.matching_context.current_host = Some(host.clone()); + collector.collect_dependencies_in_invalidation_map(data.invalidation_map()); + } + + collector.invalidates_self + }; + + // If we generated a ton of descendant invalidations, it's probably not + // worth to go ahead and try to process them. + // + // Just restyle the descendants directly. + // + // This number is completely made-up, but the page that made us add this + // code generated 1960+ invalidations (bug 1420741). + // + // We don't look at slotted_descendants because those don't propagate + // down more than one level anyway. + if descendant_invalidations.dom_descendants.len() > 150 { + self.data.hint.insert(RestyleHint::RESTYLE_DESCENDANTS); + } + + if invalidated_self { + self.data.hint.insert(RestyleHint::RESTYLE_SELF); + } + + invalidated_self + } + + fn should_process_descendants(&mut self, element: E) -> bool { + if element == self.element { + return should_process_descendants(&self.data); + } + + match element.borrow_data() { + Some(d) => should_process_descendants(&d), + None => return false, + } + } + + fn recursion_limit_exceeded(&mut self, element: E) { + if element == self.element { + self.data.hint.insert(RestyleHint::RESTYLE_DESCENDANTS); + return; + } + + if let Some(mut data) = element.mutate_data() { + data.hint.insert(RestyleHint::RESTYLE_DESCENDANTS); + } + } + + fn invalidated_descendants(&mut self, element: E, child: E) { + invalidated_descendants(element, child) + } + + fn invalidated_self(&mut self, element: E) { + debug_assert_ne!(element, self.element); + invalidated_self(element); + } + + fn invalidated_sibling(&mut self, element: E, of: E) { + debug_assert_ne!(element, self.element); + invalidated_sibling(element, of); + } +} + +impl<'a, 'b, 'selectors, E> Collector<'a, 'b, 'selectors, E> +where + E: TElement, + 'selectors: 'a, +{ + fn collect_dependencies_in_invalidation_map(&mut self, map: &'selectors InvalidationMap) { + let quirks_mode = self.matching_context.quirks_mode(); + let removed_id = self.removed_id; + if let Some(ref id) = removed_id { + if let Some(deps) = map.id_to_selector.get(id, quirks_mode) { + for dep in deps { + self.scan_dependency(dep); + } + } + } + + let added_id = self.added_id; + if let Some(ref id) = added_id { + if let Some(deps) = map.id_to_selector.get(id, quirks_mode) { + for dep in deps { + self.scan_dependency(dep); + } + } + } + + for class in self.classes_added.iter().chain(self.classes_removed.iter()) { + if let Some(deps) = map.class_to_selector.get(class, quirks_mode) { + for dep in deps { + self.scan_dependency(dep); + } + } + } + + self.snapshot.each_attr_changed(|attribute| { + if let Some(deps) = map.other_attribute_affecting_selectors.get(attribute) { + for dep in deps { + self.scan_dependency(dep); + } + } + }); + + self.collect_state_dependencies(&map.state_affecting_selectors) + } + + fn collect_state_dependencies(&mut self, map: &'selectors SelectorMap<StateDependency>) { + if self.state_changes.is_empty() { + return; + } + map.lookup_with_additional( + self.lookup_element, + self.matching_context.quirks_mode(), + self.removed_id, + self.classes_removed, + self.state_changes, + |dependency| { + if !dependency.state.intersects(self.state_changes) { + return true; + } + self.scan_dependency(&dependency.dep); + true + }, + ); + } + + /// Check whether a dependency should be taken into account. + #[inline] + fn check_dependency(&mut self, dependency: &Dependency) -> bool { + check_dependency( + dependency, + &self.element, + &self.wrapper, + &mut self.matching_context, + ) + } + + fn scan_dependency(&mut self, dependency: &'selectors Dependency) { + debug!( + "TreeStyleInvalidator::scan_dependency({:?}, {:?})", + self.element, dependency + ); + + if !self.dependency_may_be_relevant(dependency) { + return; + } + + if self.check_dependency(dependency) { + return self.note_dependency(dependency); + } + } + + fn note_dependency(&mut self, dependency: &'selectors Dependency) { + debug_assert!(self.dependency_may_be_relevant(dependency)); + + let invalidation_kind = dependency.invalidation_kind(); + if matches!(invalidation_kind, DependencyInvalidationKind::Element) { + if let Some(ref parent) = dependency.parent { + // We know something changed in the inner selector, go outwards + // now. + self.scan_dependency(parent); + } else { + self.invalidates_self = true; + } + return; + } + + debug_assert_ne!(dependency.selector_offset, 0); + debug_assert_ne!(dependency.selector_offset, dependency.selector.len()); + + let invalidation = + Invalidation::new(&dependency, self.matching_context.current_host.clone()); + + match invalidation_kind { + DependencyInvalidationKind::Element => unreachable!(), + DependencyInvalidationKind::ElementAndDescendants => { + self.invalidates_self = true; + self.descendant_invalidations + .dom_descendants + .push(invalidation); + }, + DependencyInvalidationKind::Descendants => { + self.descendant_invalidations + .dom_descendants + .push(invalidation); + }, + DependencyInvalidationKind::Siblings => { + self.sibling_invalidations.push(invalidation); + }, + DependencyInvalidationKind::Parts => { + self.descendant_invalidations.parts.push(invalidation); + }, + DependencyInvalidationKind::SlottedElements => { + self.descendant_invalidations + .slotted_descendants + .push(invalidation); + }, + } + } + + /// Returns whether `dependency` may cause us to invalidate the style of + /// more elements than what we've already invalidated. + fn dependency_may_be_relevant(&self, dependency: &Dependency) -> bool { + match dependency.invalidation_kind() { + DependencyInvalidationKind::Element => !self.invalidates_self, + DependencyInvalidationKind::SlottedElements => self.element.is_html_slot_element(), + DependencyInvalidationKind::Parts => self.element.shadow_root().is_some(), + DependencyInvalidationKind::ElementAndDescendants | + DependencyInvalidationKind::Siblings | + DependencyInvalidationKind::Descendants => true, + } + } +} |