diff options
Diffstat (limited to 'servo/components/style/sharing')
| -rw-r--r-- | servo/components/style/sharing/checks.rs | 182 | ||||
| -rw-r--r-- | servo/components/style/sharing/mod.rs | 901 |
2 files changed, 1083 insertions, 0 deletions
diff --git a/servo/components/style/sharing/checks.rs b/servo/components/style/sharing/checks.rs new file mode 100644 index 0000000000..a691ac5c76 --- /dev/null +++ b/servo/components/style/sharing/checks.rs @@ -0,0 +1,182 @@ +/* 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 checks done during the style sharing process in order to determine +//! quickly whether it's worth to share style, and whether two different +//! elements can indeed share the same style. + +use crate::bloom::StyleBloom; +use crate::context::SharedStyleContext; +use crate::dom::TElement; +use crate::sharing::{StyleSharingCandidate, StyleSharingTarget}; +use selectors::NthIndexCache; + +/// Determines whether a target and a candidate have compatible parents for +/// sharing. +pub fn parents_allow_sharing<E>( + target: &mut StyleSharingTarget<E>, + candidate: &mut StyleSharingCandidate<E>, +) -> bool +where + E: TElement, +{ + // If the identity of the parent style isn't equal, we can't share. We check + // this first, because the result is cached. + if target.parent_style_identity() != candidate.parent_style_identity() { + return false; + } + + // Siblings can always share. + let parent = target.inheritance_parent().unwrap(); + let candidate_parent = candidate.element.inheritance_parent().unwrap(); + if parent == candidate_parent { + return true; + } + + // Cousins are a bit more complicated. + // + // The fact that the candidate is here means that its element does not anchor + // the relative selector. However, it may have considered relative selector(s) + // to compute its style, i.e. there's a rule `<..> :has(<..>) <..> candidate`. + // In this case, evaluating style sharing requires evaluating the relative + // selector for the target anyway. + if candidate.considered_relative_selector { + return false; + } + + // If a parent element was already styled and we traversed past it without + // restyling it, that may be because our clever invalidation logic was able + // to prove that the styles of that element would remain unchanged despite + // changes to the id or class attributes. However, style sharing relies in + // the strong guarantee that all the classes and ids up the respective parent + // chains are identical. As such, if we skipped styling for one (or both) of + // the parents on this traversal, we can't share styles across cousins. + // + // This is a somewhat conservative check. We could tighten it by having the + // invalidation logic explicitly flag elements for which it ellided styling. + let parent_data = parent.borrow_data().unwrap(); + let candidate_parent_data = candidate_parent.borrow_data().unwrap(); + if !parent_data.safe_for_cousin_sharing() || !candidate_parent_data.safe_for_cousin_sharing() { + return false; + } + + true +} + +/// Whether two elements have the same same style attribute (by pointer identity). +pub fn have_same_style_attribute<E>( + target: &mut StyleSharingTarget<E>, + candidate: &mut StyleSharingCandidate<E>, +) -> bool +where + E: TElement, +{ + match (target.style_attribute(), candidate.style_attribute()) { + (None, None) => true, + (Some(_), None) | (None, Some(_)) => false, + (Some(a), Some(b)) => &*a as *const _ == &*b as *const _, + } +} + +/// Whether two elements have the same same presentational attributes. +pub fn have_same_presentational_hints<E>( + target: &mut StyleSharingTarget<E>, + candidate: &mut StyleSharingCandidate<E>, +) -> bool +where + E: TElement, +{ + target.pres_hints() == candidate.pres_hints() +} + +/// Whether a given element has the same class attribute as a given candidate. +/// +/// We don't try to share style across elements with different class attributes. +pub fn have_same_class<E>( + target: &mut StyleSharingTarget<E>, + candidate: &mut StyleSharingCandidate<E>, +) -> bool +where + E: TElement, +{ + target.class_list() == candidate.class_list() +} + +/// Whether a given element has the same part attribute as a given candidate. +/// +/// We don't try to share style across elements with different part attributes. +pub fn have_same_parts<E>( + target: &mut StyleSharingTarget<E>, + candidate: &mut StyleSharingCandidate<E>, +) -> bool +where + E: TElement, +{ + target.part_list() == candidate.part_list() +} + +/// Whether a given element and a candidate match the same set of "revalidation" +/// selectors. +/// +/// Revalidation selectors are those that depend on the DOM structure, like +/// :first-child, etc, or on attributes that we don't check off-hand (pretty +/// much every attribute selector except `id` and `class`. +#[inline] +pub fn revalidate<E>( + target: &mut StyleSharingTarget<E>, + candidate: &mut StyleSharingCandidate<E>, + shared_context: &SharedStyleContext, + bloom: &StyleBloom<E>, + nth_index_cache: &mut NthIndexCache, +) -> bool +where + E: TElement, +{ + let stylist = &shared_context.stylist; + + let for_element = target.revalidation_match_results(stylist, bloom, nth_index_cache); + + let for_candidate = candidate.revalidation_match_results(stylist, bloom, nth_index_cache); + + // This assert "ensures", to some extent, that the two candidates have + // matched the same rulehash buckets, and as such, that the bits we're + // comparing represent the same set of selectors. + debug_assert_eq!(for_element.len(), for_candidate.len()); + + for_element == for_candidate +} + +/// Checks whether we might have rules for either of the two ids. +#[inline] +pub fn may_match_different_id_rules<E>( + shared_context: &SharedStyleContext, + element: E, + candidate: E, +) -> bool +where + E: TElement, +{ + let element_id = element.id(); + let candidate_id = candidate.id(); + + if element_id == candidate_id { + return false; + } + + let stylist = &shared_context.stylist; + + let may_have_rules_for_element = match element_id { + Some(id) => stylist.may_have_rules_for_id(id, element), + None => false, + }; + + if may_have_rules_for_element { + return true; + } + + match candidate_id { + Some(id) => stylist.may_have_rules_for_id(id, candidate), + None => false, + } +} diff --git a/servo/components/style/sharing/mod.rs b/servo/components/style/sharing/mod.rs new file mode 100644 index 0000000000..31a9587a85 --- /dev/null +++ b/servo/components/style/sharing/mod.rs @@ -0,0 +1,901 @@ +/* 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 style sharing cache, an optimization that allows similar +//! nodes to share style without having to run selector matching twice. +//! +//! The basic setup is as follows. We have an LRU cache of style sharing +//! candidates. When we try to style a target element, we first check whether +//! we can quickly determine that styles match something in this cache, and if +//! so we just use the cached style information. This check is done with a +//! StyleBloom filter set up for the target element, which may not be a correct +//! state for the cached candidate element if they're cousins instead of +//! siblings. +//! +//! The complicated part is determining that styles match. This is subject to +//! the following constraints: +//! +//! 1) The target and candidate must be inheriting the same styles. +//! 2) The target and candidate must have exactly the same rules matching them. +//! 3) The target and candidate must have exactly the same non-selector-based +//! style information (inline styles, presentation hints). +//! 4) The target and candidate must have exactly the same rules matching their +//! pseudo-elements, because an element's style data points to the style +//! data for its pseudo-elements. +//! +//! These constraints are satisfied in the following ways: +//! +//! * We check that the parents of the target and the candidate have the same +//! computed style. This addresses constraint 1. +//! +//! * We check that the target and candidate have the same inline style and +//! presentation hint declarations. This addresses constraint 3. +//! +//! * We ensure that a target matches a candidate only if they have the same +//! matching result for all selectors that target either elements or the +//! originating elements of pseudo-elements. This addresses constraint 4 +//! (because it prevents a target that has pseudo-element styles from matching +//! a candidate that has different pseudo-element styles) as well as +//! constraint 2. +//! +//! The actual checks that ensure that elements match the same rules are +//! conceptually split up into two pieces. First, we do various checks on +//! elements that make sure that the set of possible rules in all selector maps +//! in the stylist (for normal styling and for pseudo-elements) that might match +//! the two elements is the same. For example, we enforce that the target and +//! candidate must have the same localname and namespace. Second, we have a +//! selector map of "revalidation selectors" that the stylist maintains that we +//! actually match against the target and candidate and then check whether the +//! two sets of results were the same. Due to the up-front selector map checks, +//! we know that the target and candidate will be matched against the same exact +//! set of revalidation selectors, so the match result arrays can be compared +//! directly. +//! +//! It's very important that a selector be added to the set of revalidation +//! selectors any time there are two elements that could pass all the up-front +//! checks but match differently against some ComplexSelector in the selector. +//! If that happens, then they can have descendants that might themselves pass +//! the up-front checks but would have different matching results for the +//! selector in question. In this case, "descendants" includes pseudo-elements, +//! so there is a single selector map of revalidation selectors that includes +//! both selectors targeting elements and selectors targeting pseudo-element +//! originating elements. We ensure that the pseudo-element parts of all these +//! selectors are effectively stripped off, so that matching them all against +//! elements makes sense. + +use crate::applicable_declarations::ApplicableDeclarationBlock; +use crate::bloom::StyleBloom; +use crate::computed_value_flags::ComputedValueFlags; +use crate::context::{SharedStyleContext, StyleContext}; +use crate::dom::{SendElement, TElement}; +use crate::properties::ComputedValues; +use crate::rule_tree::StrongRuleNode; +use crate::style_resolver::{PrimaryStyle, ResolvedElementStyles}; +use crate::stylist::Stylist; +use crate::values::AtomIdent; +use atomic_refcell::{AtomicRefCell, AtomicRefMut}; +use owning_ref::OwningHandle; +use selectors::matching::{NeedsSelectorFlags, VisitedHandlingMode}; +use selectors::NthIndexCache; +use servo_arc::Arc; +use smallbitvec::SmallBitVec; +use smallvec::SmallVec; +use std::marker::PhantomData; +use std::mem::{self, ManuallyDrop}; +use std::ops::Deref; +use std::ptr::NonNull; +use uluru::LRUCache; + +mod checks; + +/// The amount of nodes that the style sharing candidate cache should hold at +/// most. +/// +/// The cache size was chosen by measuring style sharing and resulting +/// performance on a few pages; sizes up to about 32 were giving good sharing +/// improvements (e.g. 3x fewer styles having to be resolved than at size 8) and +/// slight performance improvements. Sizes larger than 32 haven't really been +/// tested. +pub const SHARING_CACHE_SIZE: usize = 32; + +/// Opaque pointer type to compare ComputedValues identities. +#[derive(Clone, Debug, Eq, PartialEq)] +pub struct OpaqueComputedValues(NonNull<()>); + +unsafe impl Send for OpaqueComputedValues {} +unsafe impl Sync for OpaqueComputedValues {} + +impl OpaqueComputedValues { + fn from(cv: &ComputedValues) -> Self { + let p = + unsafe { NonNull::new_unchecked(cv as *const ComputedValues as *const () as *mut ()) }; + OpaqueComputedValues(p) + } + + fn eq(&self, cv: &ComputedValues) -> bool { + Self::from(cv) == *self + } +} + +/// Some data we want to avoid recomputing all the time while trying to share +/// style. +#[derive(Debug, Default)] +pub struct ValidationData { + /// The class list of this element. + /// + /// TODO(emilio): Maybe check whether rules for these classes apply to the + /// element? + class_list: Option<SmallVec<[AtomIdent; 5]>>, + + /// The part list of this element. + /// + /// TODO(emilio): Maybe check whether rules with these part names apply to + /// the element? + part_list: Option<SmallVec<[AtomIdent; 5]>>, + + /// The list of presentational attributes of the element. + pres_hints: Option<SmallVec<[ApplicableDeclarationBlock; 5]>>, + + /// The pointer identity of the parent ComputedValues. + parent_style_identity: Option<OpaqueComputedValues>, + + /// The cached result of matching this entry against the revalidation + /// selectors. + revalidation_match_results: Option<SmallBitVec>, +} + +impl ValidationData { + /// Move the cached data to a new instance, and return it. + pub fn take(&mut self) -> Self { + mem::replace(self, Self::default()) + } + + /// Get or compute the list of presentational attributes associated with + /// this element. + pub fn pres_hints<E>(&mut self, element: E) -> &[ApplicableDeclarationBlock] + where + E: TElement, + { + self.pres_hints.get_or_insert_with(|| { + let mut pres_hints = SmallVec::new(); + element.synthesize_presentational_hints_for_legacy_attributes( + VisitedHandlingMode::AllLinksUnvisited, + &mut pres_hints, + ); + pres_hints + }) + } + + /// Get or compute the part-list associated with this element. + pub fn part_list<E>(&mut self, element: E) -> &[AtomIdent] + where + E: TElement, + { + if !element.has_part_attr() { + return &[]; + } + self.part_list.get_or_insert_with(|| { + let mut list = SmallVec::<[_; 5]>::new(); + element.each_part(|p| list.push(p.clone())); + // See below for the reasoning. + if !list.spilled() { + list.sort_unstable_by_key(|a| a.get_hash()); + } + list + }) + } + + /// Get or compute the class-list associated with this element. + pub fn class_list<E>(&mut self, element: E) -> &[AtomIdent] + where + E: TElement, + { + self.class_list.get_or_insert_with(|| { + let mut list = SmallVec::<[_; 5]>::new(); + element.each_class(|c| list.push(c.clone())); + // Assuming there are a reasonable number of classes (we use the + // inline capacity as "reasonable number"), sort them to so that + // we don't mistakenly reject sharing candidates when one element + // has "foo bar" and the other has "bar foo". + if !list.spilled() { + list.sort_unstable_by_key(|a| a.get_hash()); + } + list + }) + } + + /// Get or compute the parent style identity. + pub fn parent_style_identity<E>(&mut self, el: E) -> OpaqueComputedValues + where + E: TElement, + { + self.parent_style_identity + .get_or_insert_with(|| { + let parent = el.inheritance_parent().unwrap(); + let values = + OpaqueComputedValues::from(parent.borrow_data().unwrap().styles.primary()); + values + }) + .clone() + } + + /// Computes the revalidation results if needed, and returns it. + /// Inline so we know at compile time what bloom_known_valid is. + #[inline] + fn revalidation_match_results<E>( + &mut self, + element: E, + stylist: &Stylist, + bloom: &StyleBloom<E>, + nth_index_cache: &mut NthIndexCache, + bloom_known_valid: bool, + needs_selector_flags: NeedsSelectorFlags, + ) -> &SmallBitVec + where + E: TElement, + { + self.revalidation_match_results.get_or_insert_with(|| { + // The bloom filter may already be set up for our element. + // If it is, use it. If not, we must be in a candidate + // (i.e. something in the cache), and the element is one + // of our cousins, not a sibling. In that case, we'll + // just do revalidation selector matching without a bloom + // filter, to avoid thrashing the filter. + let bloom_to_use = if bloom_known_valid { + debug_assert_eq!(bloom.current_parent(), element.traversal_parent()); + Some(bloom.filter()) + } else { + if bloom.current_parent() == element.traversal_parent() { + Some(bloom.filter()) + } else { + None + } + }; + stylist.match_revalidation_selectors( + element, + bloom_to_use, + nth_index_cache, + needs_selector_flags, + ) + }) + } +} + +/// Information regarding a style sharing candidate, that is, an entry in the +/// style sharing cache. +/// +/// Note that this information is stored in TLS and cleared after the traversal, +/// and once here, the style information of the element is immutable, so it's +/// safe to access. +/// +/// Important: If you change the members/layout here, You need to do the same for +/// FakeCandidate below. +#[derive(Debug)] +pub struct StyleSharingCandidate<E: TElement> { + /// The element. + element: E, + validation_data: ValidationData, + considered_relative_selector: bool, +} + +struct FakeCandidate { + _element: usize, + _validation_data: ValidationData, + _considered_relative_selector: bool, +} + +impl<E: TElement> Deref for StyleSharingCandidate<E> { + type Target = E; + + fn deref(&self) -> &Self::Target { + &self.element + } +} + +impl<E: TElement> StyleSharingCandidate<E> { + /// Get the classlist of this candidate. + fn class_list(&mut self) -> &[AtomIdent] { + self.validation_data.class_list(self.element) + } + + /// Get the part list of this candidate. + fn part_list(&mut self) -> &[AtomIdent] { + self.validation_data.part_list(self.element) + } + + /// Get the pres hints of this candidate. + fn pres_hints(&mut self) -> &[ApplicableDeclarationBlock] { + self.validation_data.pres_hints(self.element) + } + + /// Get the parent style identity. + fn parent_style_identity(&mut self) -> OpaqueComputedValues { + self.validation_data.parent_style_identity(self.element) + } + + /// Compute the bit vector of revalidation selector match results + /// for this candidate. + fn revalidation_match_results( + &mut self, + stylist: &Stylist, + bloom: &StyleBloom<E>, + nth_index_cache: &mut NthIndexCache, + ) -> &SmallBitVec { + self.validation_data.revalidation_match_results( + self.element, + stylist, + bloom, + nth_index_cache, + /* bloom_known_valid = */ false, + // The candidate must already have the right bits already, if + // needed. + NeedsSelectorFlags::No, + ) + } +} + +impl<E: TElement> PartialEq<StyleSharingCandidate<E>> for StyleSharingCandidate<E> { + fn eq(&self, other: &Self) -> bool { + self.element == other.element + } +} + +/// An element we want to test against the style sharing cache. +pub struct StyleSharingTarget<E: TElement> { + element: E, + validation_data: ValidationData, +} + +impl<E: TElement> Deref for StyleSharingTarget<E> { + type Target = E; + + fn deref(&self) -> &Self::Target { + &self.element + } +} + +impl<E: TElement> StyleSharingTarget<E> { + /// Trivially construct a new StyleSharingTarget to test against the cache. + pub fn new(element: E) -> Self { + Self { + element: element, + validation_data: ValidationData::default(), + } + } + + fn class_list(&mut self) -> &[AtomIdent] { + self.validation_data.class_list(self.element) + } + + fn part_list(&mut self) -> &[AtomIdent] { + self.validation_data.part_list(self.element) + } + + /// Get the pres hints of this candidate. + fn pres_hints(&mut self) -> &[ApplicableDeclarationBlock] { + self.validation_data.pres_hints(self.element) + } + + /// Get the parent style identity. + fn parent_style_identity(&mut self) -> OpaqueComputedValues { + self.validation_data.parent_style_identity(self.element) + } + + fn revalidation_match_results( + &mut self, + stylist: &Stylist, + bloom: &StyleBloom<E>, + nth_index_cache: &mut NthIndexCache, + ) -> &SmallBitVec { + // It's important to set the selector flags. Otherwise, if we succeed in + // sharing the style, we may not set the slow selector flags for the + // right elements (which may not necessarily be |element|), causing + // missed restyles after future DOM mutations. + // + // Gecko's test_bug534804.html exercises this. A minimal testcase is: + // <style> #e:empty + span { ... } </style> + // <span id="e"> + // <span></span> + // </span> + // <span></span> + // + // The style sharing cache will get a hit for the second span. When the + // child span is subsequently removed from the DOM, missing selector + // flags would cause us to miss the restyle on the second span. + self.validation_data.revalidation_match_results( + self.element, + stylist, + bloom, + nth_index_cache, + /* bloom_known_valid = */ true, + NeedsSelectorFlags::Yes, + ) + } + + /// Attempts to share a style with another node. + pub fn share_style_if_possible( + &mut self, + context: &mut StyleContext<E>, + ) -> Option<ResolvedElementStyles> { + let cache = &mut context.thread_local.sharing_cache; + let shared_context = &context.shared; + let bloom_filter = &context.thread_local.bloom_filter; + let nth_index_cache = &mut context.thread_local.nth_index_cache; + + if cache.dom_depth != bloom_filter.matching_depth() { + debug!( + "Can't share style, because DOM depth changed from {:?} to {:?}, element: {:?}", + cache.dom_depth, + bloom_filter.matching_depth(), + self.element + ); + return None; + } + debug_assert_eq!( + bloom_filter.current_parent(), + self.element.traversal_parent() + ); + + cache.share_style_if_possible(shared_context, bloom_filter, nth_index_cache, self) + } + + /// Gets the validation data used to match against this target, if any. + pub fn take_validation_data(&mut self) -> ValidationData { + self.validation_data.take() + } +} + +struct SharingCacheBase<Candidate> { + entries: LRUCache<Candidate, SHARING_CACHE_SIZE>, +} + +impl<Candidate> Default for SharingCacheBase<Candidate> { + fn default() -> Self { + Self { + entries: LRUCache::default(), + } + } +} + +impl<Candidate> SharingCacheBase<Candidate> { + fn clear(&mut self) { + self.entries.clear(); + } + + fn is_empty(&self) -> bool { + self.entries.len() == 0 + } +} + +impl<E: TElement> SharingCache<E> { + fn insert( + &mut self, + element: E, + considered_relative_selector: bool, + validation_data_holder: Option<&mut StyleSharingTarget<E>>, + ) { + let validation_data = match validation_data_holder { + Some(v) => v.take_validation_data(), + None => ValidationData::default(), + }; + self.entries.insert(StyleSharingCandidate { + element, + considered_relative_selector, + validation_data, + }); + } +} + +/// Style sharing caches are are large allocations, so we store them in thread-local +/// storage such that they can be reused across style traversals. Ideally, we'd just +/// stack-allocate these buffers with uninitialized memory, but right now rustc can't +/// avoid memmoving the entire cache during setup, which gets very expensive. See +/// issues like [1] and [2]. +/// +/// Given that the cache stores entries of type TElement, we transmute to usize +/// before storing in TLS. This is safe as long as we make sure to empty the cache +/// before we let it go. +/// +/// [1] https://github.com/rust-lang/rust/issues/42763 +/// [2] https://github.com/rust-lang/rust/issues/13707 +type SharingCache<E> = SharingCacheBase<StyleSharingCandidate<E>>; +type TypelessSharingCache = SharingCacheBase<FakeCandidate>; +type StoredSharingCache = Arc<AtomicRefCell<TypelessSharingCache>>; + +thread_local! { + // See the comment on bloom.rs about why do we leak this. + static SHARING_CACHE_KEY: ManuallyDrop<StoredSharingCache> = + ManuallyDrop::new(Arc::new_leaked(Default::default())); +} + +/// An LRU cache of the last few nodes seen, so that we can aggressively try to +/// reuse their styles. +/// +/// Note that this cache is flushed every time we steal work from the queue, so +/// storing nodes here temporarily is safe. +pub struct StyleSharingCache<E: TElement> { + /// The LRU cache, with the type cast away to allow persisting the allocation. + cache_typeless: OwningHandle<StoredSharingCache, AtomicRefMut<'static, TypelessSharingCache>>, + /// Bind this structure to the lifetime of E, since that's what we effectively store. + marker: PhantomData<SendElement<E>>, + /// The DOM depth we're currently at. This is used as an optimization to + /// clear the cache when we change depths, since we know at that point + /// nothing in the cache will match. + dom_depth: usize, +} + +impl<E: TElement> Drop for StyleSharingCache<E> { + fn drop(&mut self) { + self.clear(); + } +} + +impl<E: TElement> StyleSharingCache<E> { + #[allow(dead_code)] + fn cache(&self) -> &SharingCache<E> { + let base: &TypelessSharingCache = &*self.cache_typeless; + unsafe { mem::transmute(base) } + } + + fn cache_mut(&mut self) -> &mut SharingCache<E> { + let base: &mut TypelessSharingCache = &mut *self.cache_typeless; + unsafe { mem::transmute(base) } + } + + /// Create a new style sharing candidate cache. + + // Forced out of line to limit stack frame sizes after extra inlining from + // https://github.com/rust-lang/rust/pull/43931 + // + // See https://github.com/servo/servo/pull/18420#issuecomment-328769322 + #[inline(never)] + pub fn new() -> Self { + assert_eq!( + mem::size_of::<SharingCache<E>>(), + mem::size_of::<TypelessSharingCache>() + ); + assert_eq!( + mem::align_of::<SharingCache<E>>(), + mem::align_of::<TypelessSharingCache>() + ); + let cache_arc = SHARING_CACHE_KEY.with(|c| Arc::clone(&*c)); + let cache = + OwningHandle::new_with_fn(cache_arc, |x| unsafe { x.as_ref() }.unwrap().borrow_mut()); + debug_assert!(cache.is_empty()); + + StyleSharingCache { + cache_typeless: cache, + marker: PhantomData, + dom_depth: 0, + } + } + + /// Tries to insert an element in the style sharing cache. + /// + /// Fails if we know it should never be in the cache. + /// + /// NB: We pass a source for the validation data, rather than the data itself, + /// to avoid memmoving at each function call. See rust issue #42763. + pub fn insert_if_possible( + &mut self, + element: &E, + style: &PrimaryStyle, + validation_data_holder: Option<&mut StyleSharingTarget<E>>, + dom_depth: usize, + shared_context: &SharedStyleContext, + ) { + let parent = match element.traversal_parent() { + Some(element) => element, + None => { + debug!("Failing to insert to the cache: no parent element"); + return; + }, + }; + + if !element.matches_user_and_content_rules() { + debug!("Failing to insert into the cache: no tree rules:"); + return; + } + + // We can't share style across shadow hosts right now, because they may + // match different :host rules. + // + // TODO(emilio): We could share across the ones that don't have :host + // rules or have the same. + if element.shadow_root().is_some() { + debug!("Failing to insert into the cache: Shadow Host"); + return; + } + + // If the element has running animations, we can't share style. + // + // This is distinct from the specifies_{animations,transitions} check below, + // because: + // * Animations can be triggered directly via the Web Animations API. + // * Our computed style can still be affected by animations after we no + // longer match any animation rules, since removing animations involves + // a sequential task and an additional traversal. + if element.has_animations(shared_context) { + debug!("Failing to insert to the cache: running animations"); + return; + } + + // If this element was considered for matching a relative selector, we can't + // share style, as that requires evaluating the relative selector in the + // first place. A couple notes: + // - This means that a document that contains a standalone `:has()` + // rule would basically turn style sharing off. + // - Since the flag is set on the element, we may be overly pessimistic: + // For example, given `<div class="foo"><div class="bar"></div></div>`, + // if we run into a `.foo:has(.bar) .baz` selector, we refuse any selector + // matching `.foo`, even if `:has()` may not even be used. Ideally we'd + // have something like `RelativeSelectorConsidered::RightMost`, but the + // element flag is required for invalidation, and this reduces more tracking. + if element.anchors_relative_selector() { + debug!("Failing to insert to the cache: may anchor relative selector"); + return; + } + + // In addition to the above running animations check, we also need to + // check CSS animation and transition styles since it's possible that + // we are about to create CSS animations/transitions. + // + // These are things we don't check in the candidate match because they + // are either uncommon or expensive. + let ui_style = style.style().get_ui(); + if ui_style.specifies_transitions() { + debug!("Failing to insert to the cache: transitions"); + return; + } + + if ui_style.specifies_animations() { + debug!("Failing to insert to the cache: animations"); + return; + } + + debug!( + "Inserting into cache: {:?} with parent {:?}", + element, parent + ); + + if self.dom_depth != dom_depth { + debug!( + "Clearing cache because depth changed from {:?} to {:?}, element: {:?}", + self.dom_depth, dom_depth, element + ); + self.clear(); + self.dom_depth = dom_depth; + } + self.cache_mut().insert( + *element, + style + .style + .0 + .flags + .intersects(ComputedValueFlags::CONSIDERED_RELATIVE_SELECTOR), + validation_data_holder, + ); + } + + /// Clear the style sharing candidate cache. + pub fn clear(&mut self) { + self.cache_mut().clear(); + } + + /// Attempts to share a style with another node. + fn share_style_if_possible( + &mut self, + shared_context: &SharedStyleContext, + bloom_filter: &StyleBloom<E>, + nth_index_cache: &mut NthIndexCache, + target: &mut StyleSharingTarget<E>, + ) -> Option<ResolvedElementStyles> { + if shared_context.options.disable_style_sharing_cache { + debug!( + "{:?} Cannot share style: style sharing cache disabled", + target.element + ); + return None; + } + + if target.inheritance_parent().is_none() { + debug!( + "{:?} Cannot share style: element has no parent", + target.element + ); + return None; + } + + if !target.matches_user_and_content_rules() { + debug!("{:?} Cannot share style: content rules", target.element); + return None; + } + + self.cache_mut().entries.lookup(|candidate| { + Self::test_candidate( + target, + candidate, + &shared_context, + bloom_filter, + nth_index_cache, + shared_context, + ) + }) + } + + fn test_candidate( + target: &mut StyleSharingTarget<E>, + candidate: &mut StyleSharingCandidate<E>, + shared: &SharedStyleContext, + bloom: &StyleBloom<E>, + nth_index_cache: &mut NthIndexCache, + shared_context: &SharedStyleContext, + ) -> Option<ResolvedElementStyles> { + debug_assert!(target.matches_user_and_content_rules()); + + // Check that we have the same parent, or at least that the parents + // share styles and permit sharing across their children. The latter + // check allows us to share style between cousins if the parents + // shared style. + if !checks::parents_allow_sharing(target, candidate) { + trace!("Miss: Parent"); + return None; + } + + if target.local_name() != candidate.element.local_name() { + trace!("Miss: Local Name"); + return None; + } + + if target.namespace() != candidate.element.namespace() { + trace!("Miss: Namespace"); + return None; + } + + // We do not ignore visited state here, because Gecko needs to store + // extra bits on visited styles, so these contexts cannot be shared. + if target.element.state() != candidate.state() { + trace!("Miss: User and Author State"); + return None; + } + + if target.is_link() != candidate.element.is_link() { + trace!("Miss: Link"); + return None; + } + + // If two elements belong to different shadow trees, different rules may + // apply to them, from the respective trees. + if target.element.containing_shadow() != candidate.element.containing_shadow() { + trace!("Miss: Different containing shadow roots"); + return None; + } + + // If the elements are not assigned to the same slot they could match + // different ::slotted() rules in the slot scope. + // + // If two elements are assigned to different slots, even within the same + // shadow root, they could match different rules, due to the slot being + // assigned to yet another slot in another shadow root. + if target.element.assigned_slot() != candidate.element.assigned_slot() { + // TODO(emilio): We could have a look at whether the shadow roots + // actually have slotted rules and such. + trace!("Miss: Different assigned slots"); + return None; + } + + if target.element.shadow_root().is_some() { + trace!("Miss: Shadow host"); + return None; + } + + if target.element.has_animations(shared_context) { + trace!("Miss: Has Animations"); + return None; + } + + if target.matches_user_and_content_rules() != + candidate.element.matches_user_and_content_rules() + { + trace!("Miss: User and Author Rules"); + return None; + } + + // It's possible that there are no styles for either id. + if checks::may_match_different_id_rules(shared, target.element, candidate.element) { + trace!("Miss: ID Attr"); + return None; + } + + if !checks::have_same_style_attribute(target, candidate) { + trace!("Miss: Style Attr"); + return None; + } + + if !checks::have_same_class(target, candidate) { + trace!("Miss: Class"); + return None; + } + + if !checks::have_same_presentational_hints(target, candidate) { + trace!("Miss: Pres Hints"); + return None; + } + + if !checks::have_same_parts(target, candidate) { + trace!("Miss: Shadow parts"); + return None; + } + + if !checks::revalidate(target, candidate, shared, bloom, nth_index_cache) { + trace!("Miss: Revalidation"); + return None; + } + + debug!( + "Sharing allowed between {:?} and {:?}", + target.element, candidate.element + ); + Some(candidate.element.borrow_data().unwrap().share_styles()) + } + + /// Attempts to find an element in the cache with the given primary rule + /// node and parent. + /// + /// FIXME(emilio): re-measure this optimization, and remove if it's not very + /// useful... It's probably not worth the complexity / obscure bugs. + pub fn lookup_by_rules( + &mut self, + shared_context: &SharedStyleContext, + inherited: &ComputedValues, + rules: &StrongRuleNode, + visited_rules: Option<&StrongRuleNode>, + target: E, + ) -> Option<PrimaryStyle> { + if shared_context.options.disable_style_sharing_cache { + return None; + } + + self.cache_mut().entries.lookup(|candidate| { + debug_assert_ne!(candidate.element, target); + if !candidate.parent_style_identity().eq(inherited) { + return None; + } + let data = candidate.element.borrow_data().unwrap(); + let style = data.styles.primary(); + if style.rules.as_ref() != Some(&rules) { + return None; + } + if style.visited_rules() != visited_rules { + return None; + } + // NOTE(emilio): We only need to check name / namespace because we + // do name-dependent style adjustments, like the display: contents + // to display: none adjustment. + if target.namespace() != candidate.element.namespace() { + return None; + } + if target.local_name() != candidate.element.local_name() { + return None; + } + // Rule nodes and styles are computed independent of the element's + // actual visitedness, but at the end of the cascade (in + // `adjust_for_visited`) we do store the visitedness as a flag in + // style. (This is a subtle change from initial visited work that + // landed when computed values were fused, see + // https://bugzilla.mozilla.org/show_bug.cgi?id=1381635.) + // So at the moment, we need to additionally compare visitedness, + // since that is not accounted for by rule nodes alone. + // FIXME(jryans): This seems like it breaks the constant time + // requirements of visited, assuming we get a cache hit on only one + // of unvisited vs. visited. + // TODO(emilio): We no longer have such a flag, remove this check. + if target.is_visited_link() != candidate.element.is_visited_link() { + return None; + } + + Some(data.share_primary_style()) + }) + } +} |