style/
stylist.rs

1/* This Source Code Form is subject to the terms of the Mozilla Public
2 * License, v. 2.0. If a copy of the MPL was not distributed with this
3 * file, You can obtain one at https://mozilla.org/MPL/2.0/. */
4
5//! Selector matching.
6
7use crate::applicable_declarations::{
8    ApplicableDeclarationBlock, ApplicableDeclarationList, CascadePriority, ScopeProximity,
9};
10use crate::computed_value_flags::ComputedValueFlags;
11use crate::context::{CascadeInputs, QuirksMode};
12use crate::custom_properties::ComputedCustomProperties;
13use crate::dom::TElement;
14#[cfg(feature = "gecko")]
15use crate::gecko_bindings::structs::{ServoStyleSetSizes, StyleRuleInclusion};
16use crate::invalidation::element::invalidation_map::{
17    note_selector_for_invalidation, AdditionalRelativeSelectorInvalidationMap, Dependency,
18    InvalidationMap,
19};
20use crate::invalidation::media_queries::{
21    EffectiveMediaQueryResults, MediaListKey, ToMediaListKey,
22};
23use crate::invalidation::stylesheets::RuleChangeKind;
24use crate::media_queries::Device;
25use crate::properties::{self, CascadeMode, ComputedValues, FirstLineReparenting};
26use crate::properties::{AnimationDeclarations, PropertyDeclarationBlock};
27use crate::properties_and_values::registry::{
28    PropertyRegistration, PropertyRegistrationData, ScriptRegistry as CustomPropertyScriptRegistry,
29};
30use crate::rule_cache::{RuleCache, RuleCacheConditions};
31use crate::rule_collector::RuleCollector;
32use crate::rule_tree::{CascadeLevel, RuleTree, StrongRuleNode, StyleSource};
33use crate::selector_map::{PrecomputedHashMap, PrecomputedHashSet, SelectorMap, SelectorMapEntry};
34use crate::selector_parser::{
35    NonTSPseudoClass, PerPseudoElementMap, PseudoElement, SelectorImpl, SnapshotMap,
36};
37use crate::shared_lock::{Locked, SharedRwLockReadGuard, StylesheetGuards};
38use crate::sharing::{RevalidationResult, ScopeRevalidationResult};
39use crate::stylesheet_set::{DataValidity, DocumentStylesheetSet, SheetRebuildKind};
40use crate::stylesheet_set::{DocumentStylesheetFlusher, SheetCollectionFlusher};
41use crate::stylesheets::container_rule::ContainerCondition;
42use crate::stylesheets::import_rule::ImportLayer;
43use crate::stylesheets::keyframes_rule::KeyframesAnimation;
44use crate::stylesheets::layer_rule::{LayerName, LayerOrder};
45use crate::stylesheets::scope_rule::{
46    collect_scope_roots, element_is_outside_of_scope, scope_selector_list_is_trivial,
47    ImplicitScopeRoot, ScopeRootCandidate, ScopeSubjectMap, ScopeTarget,
48};
49#[cfg(feature = "gecko")]
50use crate::stylesheets::{
51    CounterStyleRule, FontFaceRule, FontFeatureValuesRule, FontPaletteValuesRule,
52    PagePseudoClassFlags,
53};
54use crate::stylesheets::{
55    CssRule, EffectiveRulesIterator, Origin, OriginSet, PageRule, PerOrigin, PerOriginIter,
56    StylesheetContents, StylesheetInDocument,
57};
58use crate::values::{computed, AtomIdent};
59use crate::AllocErr;
60use crate::{Atom, LocalName, Namespace, ShrinkIfNeeded, WeakAtom};
61use dom::{DocumentState, ElementState};
62use fxhash::FxHashMap;
63#[cfg(feature = "gecko")]
64use malloc_size_of::MallocUnconditionalShallowSizeOf;
65use malloc_size_of::{MallocShallowSizeOf, MallocSizeOf, MallocSizeOfOps};
66use selectors::attr::{CaseSensitivity, NamespaceConstraint};
67use selectors::bloom::BloomFilter;
68use selectors::matching::{
69    matches_selector, selector_may_match, MatchingContext, MatchingMode, NeedsSelectorFlags,
70    SelectorCaches,
71};
72use selectors::matching::{MatchingForInvalidation, VisitedHandlingMode};
73use selectors::parser::{
74    AncestorHashes, Combinator, Component, MatchesFeaturelessHost, Selector, SelectorIter,
75    SelectorList,
76};
77use selectors::visitor::{SelectorListKind, SelectorVisitor};
78use servo_arc::{Arc, ArcBorrow, ThinArc};
79use smallvec::SmallVec;
80use std::cmp::Ordering;
81use std::hash::{Hash, Hasher};
82use std::sync::Mutex;
83use std::{mem, ops};
84
85/// The type of the stylesheets that the stylist contains.
86#[cfg(feature = "servo")]
87pub type StylistSheet = crate::stylesheets::DocumentStyleSheet;
88
89/// The type of the stylesheets that the stylist contains.
90#[cfg(feature = "gecko")]
91pub type StylistSheet = crate::gecko::data::GeckoStyleSheet;
92
93#[derive(Debug, Clone)]
94struct StylesheetContentsPtr(Arc<StylesheetContents>);
95
96impl PartialEq for StylesheetContentsPtr {
97    #[inline]
98    fn eq(&self, other: &Self) -> bool {
99        Arc::ptr_eq(&self.0, &other.0)
100    }
101}
102
103impl Eq for StylesheetContentsPtr {}
104
105impl Hash for StylesheetContentsPtr {
106    fn hash<H: Hasher>(&self, state: &mut H) {
107        let contents: &StylesheetContents = &*self.0;
108        (contents as *const StylesheetContents).hash(state)
109    }
110}
111
112type StyleSheetContentList = Vec<StylesheetContentsPtr>;
113
114/// A key in the cascade data cache.
115#[derive(Debug, Hash, Default, PartialEq, Eq)]
116struct CascadeDataCacheKey {
117    media_query_results: Vec<MediaListKey>,
118    contents: StyleSheetContentList,
119}
120
121unsafe impl Send for CascadeDataCacheKey {}
122unsafe impl Sync for CascadeDataCacheKey {}
123
124trait CascadeDataCacheEntry: Sized {
125    /// Rebuilds the cascade data for the new stylesheet collection. The
126    /// collection is guaranteed to be dirty.
127    fn rebuild<S>(
128        device: &Device,
129        quirks_mode: QuirksMode,
130        collection: SheetCollectionFlusher<S>,
131        guard: &SharedRwLockReadGuard,
132        old_entry: &Self,
133    ) -> Result<Arc<Self>, AllocErr>
134    where
135        S: StylesheetInDocument + PartialEq + 'static;
136    /// Measures heap memory usage.
137    #[cfg(feature = "gecko")]
138    fn add_size_of(&self, ops: &mut MallocSizeOfOps, sizes: &mut ServoStyleSetSizes);
139}
140
141struct CascadeDataCache<Entry> {
142    entries: FxHashMap<CascadeDataCacheKey, Arc<Entry>>,
143}
144
145impl<Entry> CascadeDataCache<Entry>
146where
147    Entry: CascadeDataCacheEntry,
148{
149    fn new() -> Self {
150        Self {
151            entries: Default::default(),
152        }
153    }
154
155    fn len(&self) -> usize {
156        self.entries.len()
157    }
158
159    // FIXME(emilio): This may need to be keyed on quirks-mode too, though for
160    // UA sheets there aren't class / id selectors on those sheets, usually, so
161    // it's probably ok... For the other cache the quirks mode shouldn't differ
162    // so also should be fine.
163    fn lookup<'a, S>(
164        &'a mut self,
165        device: &Device,
166        quirks_mode: QuirksMode,
167        collection: SheetCollectionFlusher<S>,
168        guard: &SharedRwLockReadGuard,
169        old_entry: &Entry,
170    ) -> Result<Option<Arc<Entry>>, AllocErr>
171    where
172        S: StylesheetInDocument + PartialEq + 'static,
173    {
174        use std::collections::hash_map::Entry as HashMapEntry;
175        debug!("StyleSheetCache::lookup({})", self.len());
176
177        if !collection.dirty() {
178            return Ok(None);
179        }
180
181        let mut key = CascadeDataCacheKey::default();
182        for sheet in collection.sheets() {
183            CascadeData::collect_applicable_media_query_results_into(
184                device,
185                sheet,
186                guard,
187                &mut key.media_query_results,
188                &mut key.contents,
189            )
190        }
191
192        let new_entry;
193        match self.entries.entry(key) {
194            HashMapEntry::Vacant(e) => {
195                debug!("> Picking the slow path (not in the cache)");
196                new_entry = Entry::rebuild(device, quirks_mode, collection, guard, old_entry)?;
197                e.insert(new_entry.clone());
198            },
199            HashMapEntry::Occupied(mut e) => {
200                // Avoid reusing our old entry (this can happen if we get
201                // invalidated due to CSSOM mutations and our old stylesheet
202                // contents were already unique, for example).
203                if !std::ptr::eq(&**e.get(), old_entry) {
204                    if log_enabled!(log::Level::Debug) {
205                        debug!("cache hit for:");
206                        for sheet in collection.sheets() {
207                            debug!(" > {:?}", sheet);
208                        }
209                    }
210                    // The line below ensures the "committed" bit is updated
211                    // properly.
212                    collection.each(|_, _, _| true);
213                    return Ok(Some(e.get().clone()));
214                }
215
216                debug!("> Picking the slow path due to same entry as old");
217                new_entry = Entry::rebuild(device, quirks_mode, collection, guard, old_entry)?;
218                e.insert(new_entry.clone());
219            },
220        }
221
222        Ok(Some(new_entry))
223    }
224
225    /// Returns all the cascade datas that are not being used (that is, that are
226    /// held alive just by this cache).
227    ///
228    /// We return them instead of dropping in place because some of them may
229    /// keep alive some other documents (like the SVG documents kept alive by
230    /// URL references), and thus we don't want to drop them while locking the
231    /// cache to not deadlock.
232    fn take_unused(&mut self) -> SmallVec<[Arc<Entry>; 3]> {
233        let mut unused = SmallVec::new();
234        self.entries.retain(|_key, value| {
235            // is_unique() returns false for static references, but we never
236            // have static references to UserAgentCascadeDatas.  If we did, it
237            // may not make sense to put them in the cache in the first place.
238            if !value.is_unique() {
239                return true;
240            }
241            unused.push(value.clone());
242            false
243        });
244        unused
245    }
246
247    fn take_all(&mut self) -> FxHashMap<CascadeDataCacheKey, Arc<Entry>> {
248        mem::take(&mut self.entries)
249    }
250
251    #[cfg(feature = "gecko")]
252    fn add_size_of(&self, ops: &mut MallocSizeOfOps, sizes: &mut ServoStyleSetSizes) {
253        sizes.mOther += self.entries.shallow_size_of(ops);
254        for (_key, arc) in self.entries.iter() {
255            // These are primary Arc references that can be measured
256            // unconditionally.
257            sizes.mOther += arc.unconditional_shallow_size_of(ops);
258            arc.add_size_of(ops, sizes);
259        }
260    }
261}
262
263/// Measure heap usage of UA_CASCADE_DATA_CACHE.
264#[cfg(feature = "gecko")]
265pub fn add_size_of_ua_cache(ops: &mut MallocSizeOfOps, sizes: &mut ServoStyleSetSizes) {
266    UA_CASCADE_DATA_CACHE
267        .lock()
268        .unwrap()
269        .add_size_of(ops, sizes);
270}
271
272lazy_static! {
273    /// A cache of computed user-agent data, to be shared across documents.
274    static ref UA_CASCADE_DATA_CACHE: Mutex<UserAgentCascadeDataCache> =
275        Mutex::new(UserAgentCascadeDataCache::new());
276}
277
278impl CascadeDataCacheEntry for UserAgentCascadeData {
279    fn rebuild<S>(
280        device: &Device,
281        quirks_mode: QuirksMode,
282        collection: SheetCollectionFlusher<S>,
283        guard: &SharedRwLockReadGuard,
284        _old: &Self,
285    ) -> Result<Arc<Self>, AllocErr>
286    where
287        S: StylesheetInDocument + PartialEq + 'static,
288    {
289        // TODO: Maybe we should support incremental rebuilds, though they seem
290        // uncommon and rebuild() doesn't deal with
291        // precomputed_pseudo_element_decls for now so...
292        let mut new_data = Self {
293            cascade_data: CascadeData::new(),
294            precomputed_pseudo_element_decls: PrecomputedPseudoElementDeclarations::default(),
295        };
296
297        for (index, sheet) in collection.sheets().enumerate() {
298            new_data.cascade_data.add_stylesheet(
299                device,
300                quirks_mode,
301                sheet,
302                index,
303                guard,
304                SheetRebuildKind::Full,
305                Some(&mut new_data.precomputed_pseudo_element_decls),
306            )?;
307        }
308
309        new_data.cascade_data.did_finish_rebuild();
310
311        Ok(Arc::new(new_data))
312    }
313
314    #[cfg(feature = "gecko")]
315    fn add_size_of(&self, ops: &mut MallocSizeOfOps, sizes: &mut ServoStyleSetSizes) {
316        self.cascade_data.add_size_of(ops, sizes);
317        sizes.mPrecomputedPseudos += self.precomputed_pseudo_element_decls.size_of(ops);
318    }
319}
320
321type UserAgentCascadeDataCache = CascadeDataCache<UserAgentCascadeData>;
322
323type PrecomputedPseudoElementDeclarations = PerPseudoElementMap<Vec<ApplicableDeclarationBlock>>;
324
325#[derive(Default)]
326struct UserAgentCascadeData {
327    cascade_data: CascadeData,
328
329    /// Applicable declarations for a given non-eagerly cascaded pseudo-element.
330    ///
331    /// These are eagerly computed once, and then used to resolve the new
332    /// computed values on the fly on layout.
333    ///
334    /// These are only filled from UA stylesheets.
335    precomputed_pseudo_element_decls: PrecomputedPseudoElementDeclarations,
336}
337
338lazy_static! {
339    /// The empty UA cascade data for un-filled stylists.
340    static ref EMPTY_UA_CASCADE_DATA: Arc<UserAgentCascadeData> = {
341        let arc = Arc::new(UserAgentCascadeData::default());
342        arc.mark_as_intentionally_leaked();
343        arc
344    };
345}
346
347/// All the computed information for all the stylesheets that apply to the
348/// document.
349#[derive(MallocSizeOf)]
350pub struct DocumentCascadeData {
351    #[ignore_malloc_size_of = "Arc, owned by UserAgentCascadeDataCache or empty"]
352    user_agent: Arc<UserAgentCascadeData>,
353    user: CascadeData,
354    author: CascadeData,
355    per_origin: PerOrigin<()>,
356}
357
358impl Default for DocumentCascadeData {
359    fn default() -> Self {
360        Self {
361            user_agent: EMPTY_UA_CASCADE_DATA.clone(),
362            user: Default::default(),
363            author: Default::default(),
364            per_origin: Default::default(),
365        }
366    }
367}
368
369/// An iterator over the cascade data of a given document.
370pub struct DocumentCascadeDataIter<'a> {
371    iter: PerOriginIter<'a, ()>,
372    cascade_data: &'a DocumentCascadeData,
373}
374
375impl<'a> Iterator for DocumentCascadeDataIter<'a> {
376    type Item = (&'a CascadeData, Origin);
377
378    fn next(&mut self) -> Option<Self::Item> {
379        let (_, origin) = self.iter.next()?;
380        Some((self.cascade_data.borrow_for_origin(origin), origin))
381    }
382}
383
384impl DocumentCascadeData {
385    /// Borrows the cascade data for a given origin.
386    #[inline]
387    pub fn borrow_for_origin(&self, origin: Origin) -> &CascadeData {
388        match origin {
389            Origin::UserAgent => &self.user_agent.cascade_data,
390            Origin::Author => &self.author,
391            Origin::User => &self.user,
392        }
393    }
394
395    fn iter_origins(&self) -> DocumentCascadeDataIter {
396        DocumentCascadeDataIter {
397            iter: self.per_origin.iter_origins(),
398            cascade_data: self,
399        }
400    }
401
402    fn iter_origins_rev(&self) -> DocumentCascadeDataIter {
403        DocumentCascadeDataIter {
404            iter: self.per_origin.iter_origins_rev(),
405            cascade_data: self,
406        }
407    }
408
409    /// Rebuild the cascade data for the given document stylesheets, and
410    /// optionally with a set of user agent stylesheets.  Returns Err(..)
411    /// to signify OOM.
412    fn rebuild<'a, S>(
413        &mut self,
414        device: &Device,
415        quirks_mode: QuirksMode,
416        mut flusher: DocumentStylesheetFlusher<'a, S>,
417        guards: &StylesheetGuards,
418    ) -> Result<(), AllocErr>
419    where
420        S: StylesheetInDocument + PartialEq + 'static,
421    {
422        // First do UA sheets.
423        {
424            let origin_flusher = flusher.flush_origin(Origin::UserAgent);
425            // Dirty check is just a minor optimization (no need to grab the
426            // lock if nothing has changed).
427            if origin_flusher.dirty() {
428                let mut ua_cache = UA_CASCADE_DATA_CACHE.lock().unwrap();
429                let new_data = ua_cache.lookup(
430                    device,
431                    quirks_mode,
432                    origin_flusher,
433                    guards.ua_or_user,
434                    &self.user_agent,
435                )?;
436                if let Some(new_data) = new_data {
437                    self.user_agent = new_data;
438                }
439                let _unused_entries = ua_cache.take_unused();
440                // See the comments in take_unused() as for why the following
441                // line.
442                std::mem::drop(ua_cache);
443            }
444        }
445
446        // Now do the user sheets.
447        self.user.rebuild(
448            device,
449            quirks_mode,
450            flusher.flush_origin(Origin::User),
451            guards.ua_or_user,
452        )?;
453
454        // And now the author sheets.
455        self.author.rebuild(
456            device,
457            quirks_mode,
458            flusher.flush_origin(Origin::Author),
459            guards.author,
460        )?;
461
462        Ok(())
463    }
464
465    /// Measures heap usage.
466    #[cfg(feature = "gecko")]
467    pub fn add_size_of(&self, ops: &mut MallocSizeOfOps, sizes: &mut ServoStyleSetSizes) {
468        self.user.add_size_of(ops, sizes);
469        self.author.add_size_of(ops, sizes);
470    }
471}
472
473/// Whether author styles are enabled.
474///
475/// This is used to support Gecko.
476#[allow(missing_docs)]
477#[derive(Clone, Copy, Debug, Eq, MallocSizeOf, PartialEq)]
478pub enum AuthorStylesEnabled {
479    Yes,
480    No,
481}
482
483/// A wrapper over a DocumentStylesheetSet that can be `Sync`, since it's only
484/// used and exposed via mutable methods in the `Stylist`.
485#[cfg_attr(feature = "servo", derive(MallocSizeOf))]
486struct StylistStylesheetSet(DocumentStylesheetSet<StylistSheet>);
487// Read above to see why this is fine.
488unsafe impl Sync for StylistStylesheetSet {}
489
490impl StylistStylesheetSet {
491    fn new() -> Self {
492        StylistStylesheetSet(DocumentStylesheetSet::new())
493    }
494}
495
496impl ops::Deref for StylistStylesheetSet {
497    type Target = DocumentStylesheetSet<StylistSheet>;
498
499    fn deref(&self) -> &Self::Target {
500        &self.0
501    }
502}
503
504impl ops::DerefMut for StylistStylesheetSet {
505    fn deref_mut(&mut self) -> &mut Self::Target {
506        &mut self.0
507    }
508}
509
510/// This structure holds all the selectors and device characteristics
511/// for a given document. The selectors are converted into `Rule`s
512/// and sorted into `SelectorMap`s keyed off stylesheet origin and
513/// pseudo-element (see `CascadeData`).
514///
515/// This structure is effectively created once per pipeline, in the
516/// LayoutThread corresponding to that pipeline.
517#[cfg_attr(feature = "servo", derive(MallocSizeOf))]
518pub struct Stylist {
519    /// Device that the stylist is currently evaluating against.
520    ///
521    /// This field deserves a bigger comment due to the different use that Gecko
522    /// and Servo give to it (that we should eventually unify).
523    ///
524    /// With Gecko, the device is never changed. Gecko manually tracks whether
525    /// the device data should be reconstructed, and "resets" the state of the
526    /// device.
527    ///
528    /// On Servo, on the other hand, the device is a really cheap representation
529    /// that is recreated each time some constraint changes and calling
530    /// `set_device`.
531    device: Device,
532
533    /// The list of stylesheets.
534    stylesheets: StylistStylesheetSet,
535
536    /// A cache of CascadeDatas for AuthorStylesheetSets (i.e., shadow DOM).
537    #[cfg_attr(feature = "servo", ignore_malloc_size_of = "XXX: how to handle this?")]
538    author_data_cache: CascadeDataCache<CascadeData>,
539
540    /// If true, the quirks-mode stylesheet is applied.
541    #[cfg_attr(feature = "servo", ignore_malloc_size_of = "defined in selectors")]
542    quirks_mode: QuirksMode,
543
544    /// Selector maps for all of the style sheets in the stylist, after
545    /// evalutaing media rules against the current device, split out per
546    /// cascade level.
547    cascade_data: DocumentCascadeData,
548
549    /// Whether author styles are enabled.
550    author_styles_enabled: AuthorStylesEnabled,
551
552    /// The rule tree, that stores the results of selector matching.
553    rule_tree: RuleTree,
554
555    /// The set of registered custom properties from script.
556    /// <https://drafts.css-houdini.org/css-properties-values-api-1/#dom-window-registeredpropertyset-slot>
557    script_custom_properties: CustomPropertyScriptRegistry,
558
559    /// Initial values for registered custom properties.
560    #[cfg_attr(feature = "servo", ignore_malloc_size_of = "Arc")]
561    initial_values_for_custom_properties: ComputedCustomProperties,
562
563    /// Flags set from computing registered custom property initial values.
564    initial_values_for_custom_properties_flags: ComputedValueFlags,
565
566    /// The total number of times the stylist has been rebuilt.
567    num_rebuilds: usize,
568}
569
570/// What cascade levels to include when styling elements.
571#[derive(Clone, Copy, PartialEq)]
572pub enum RuleInclusion {
573    /// Include rules for style sheets at all cascade levels.  This is the
574    /// normal rule inclusion mode.
575    All,
576    /// Only include rules from UA and user level sheets.  Used to implement
577    /// `getDefaultComputedStyle`.
578    DefaultOnly,
579}
580
581#[cfg(feature = "gecko")]
582impl From<StyleRuleInclusion> for RuleInclusion {
583    fn from(value: StyleRuleInclusion) -> Self {
584        match value {
585            StyleRuleInclusion::All => RuleInclusion::All,
586            StyleRuleInclusion::DefaultOnly => RuleInclusion::DefaultOnly,
587        }
588    }
589}
590
591/// `:scope` selector, depending on the use case, can match a shadow host.
592/// If used outside of `@scope`, it cannot possibly match the host.
593/// Even when inside of `@scope`, it's conditional if the selector will
594/// match the shadow host.
595#[derive(Clone, Copy, Eq, PartialEq)]
596enum ScopeMatchesShadowHost {
597    NotApplicable,
598    No,
599    Yes,
600}
601
602impl Default for ScopeMatchesShadowHost {
603    fn default() -> Self {
604        Self::NotApplicable
605    }
606}
607
608impl ScopeMatchesShadowHost {
609    fn nest_for_scope(&mut self, matches_shadow_host: bool) {
610        match *self {
611            Self::NotApplicable => {
612                // We're at the outermost `@scope`.
613                *self = if matches_shadow_host {
614                    Self::Yes
615                } else {
616                    Self::No
617                };
618            },
619            Self::Yes if !matches_shadow_host => {
620                // Inner `@scope` will not be able to match the shadow host.
621                *self = Self::No;
622            },
623            _ => (),
624        }
625    }
626}
627
628/// Nested declarations have effectively two behaviors:
629///  * Inside style rules (where they behave as the containing selector).
630///  * Inside @scope (where they behave as :where(:scope)).
631/// It is a bit unfortunate ideally we wouldn't need this, because scope also pushes to the
632/// ancestor_selector_lists, but the behavior isn't quite the same as wrapping in `&`, see
633/// https://github.com/w3c/csswg-drafts/issues/10431
634#[derive(Copy, Clone)]
635enum NestedDeclarationsContext {
636    Style,
637    Scope,
638}
639
640/// A struct containing state from ancestor rules like @layer / @import /
641/// @container / nesting / @scope.
642struct ContainingRuleState {
643    layer_name: LayerName,
644    layer_id: LayerId,
645    container_condition_id: ContainerConditionId,
646    in_starting_style: bool,
647    scope_condition_id: ScopeConditionId,
648    scope_matches_shadow_host: ScopeMatchesShadowHost,
649    ancestor_selector_lists: SmallVec<[SelectorList<SelectorImpl>; 2]>,
650    nested_declarations_context: NestedDeclarationsContext,
651}
652
653impl Default for ContainingRuleState {
654    fn default() -> Self {
655        Self {
656            layer_name: LayerName::new_empty(),
657            layer_id: LayerId::root(),
658            container_condition_id: ContainerConditionId::none(),
659            in_starting_style: false,
660            ancestor_selector_lists: Default::default(),
661            scope_condition_id: ScopeConditionId::none(),
662            scope_matches_shadow_host: Default::default(),
663            nested_declarations_context: NestedDeclarationsContext::Style,
664        }
665    }
666}
667
668struct SavedContainingRuleState {
669    ancestor_selector_lists_len: usize,
670    layer_name_len: usize,
671    layer_id: LayerId,
672    container_condition_id: ContainerConditionId,
673    in_starting_style: bool,
674    scope_condition_id: ScopeConditionId,
675    scope_matches_shadow_host: ScopeMatchesShadowHost,
676    nested_declarations_context: NestedDeclarationsContext,
677}
678
679impl ContainingRuleState {
680    fn save(&self) -> SavedContainingRuleState {
681        SavedContainingRuleState {
682            ancestor_selector_lists_len: self.ancestor_selector_lists.len(),
683            layer_name_len: self.layer_name.0.len(),
684            layer_id: self.layer_id,
685            container_condition_id: self.container_condition_id,
686            in_starting_style: self.in_starting_style,
687            scope_condition_id: self.scope_condition_id,
688            scope_matches_shadow_host: self.scope_matches_shadow_host,
689            nested_declarations_context: self.nested_declarations_context,
690        }
691    }
692
693    fn restore(&mut self, saved: &SavedContainingRuleState) {
694        debug_assert!(self.layer_name.0.len() >= saved.layer_name_len);
695        debug_assert!(self.ancestor_selector_lists.len() >= saved.ancestor_selector_lists_len);
696        self.ancestor_selector_lists
697            .truncate(saved.ancestor_selector_lists_len);
698        self.layer_name.0.truncate(saved.layer_name_len);
699        self.layer_id = saved.layer_id;
700        self.container_condition_id = saved.container_condition_id;
701        self.in_starting_style = saved.in_starting_style;
702        self.scope_condition_id = saved.scope_condition_id;
703        self.scope_matches_shadow_host = saved.scope_matches_shadow_host;
704        self.nested_declarations_context = saved.nested_declarations_context;
705    }
706}
707
708type ReplacedSelectors = SmallVec<[Selector<SelectorImpl>; 4]>;
709
710impl Stylist {
711    /// Construct a new `Stylist`, using given `Device` and `QuirksMode`.
712    /// If more members are added here, think about whether they should
713    /// be reset in clear().
714    #[inline]
715    pub fn new(device: Device, quirks_mode: QuirksMode) -> Self {
716        Self {
717            device,
718            quirks_mode,
719            stylesheets: StylistStylesheetSet::new(),
720            author_data_cache: CascadeDataCache::new(),
721            cascade_data: Default::default(),
722            author_styles_enabled: AuthorStylesEnabled::Yes,
723            rule_tree: RuleTree::new(),
724            script_custom_properties: Default::default(),
725            initial_values_for_custom_properties: Default::default(),
726            initial_values_for_custom_properties_flags: Default::default(),
727            num_rebuilds: 0,
728        }
729    }
730
731    /// Returns the document cascade data.
732    #[inline]
733    pub fn cascade_data(&self) -> &DocumentCascadeData {
734        &self.cascade_data
735    }
736
737    /// Returns whether author styles are enabled or not.
738    #[inline]
739    pub fn author_styles_enabled(&self) -> AuthorStylesEnabled {
740        self.author_styles_enabled
741    }
742
743    /// Iterate through all the cascade datas from the document.
744    #[inline]
745    pub fn iter_origins(&self) -> DocumentCascadeDataIter {
746        self.cascade_data.iter_origins()
747    }
748
749    /// Does what the name says, to prevent author_data_cache to grow without
750    /// bound.
751    pub fn remove_unique_author_data_cache_entries(&mut self) {
752        self.author_data_cache.take_unused();
753    }
754
755    /// Returns the custom property registration for this property's name.
756    /// https://drafts.css-houdini.org/css-properties-values-api-1/#determining-registration
757    pub fn get_custom_property_registration(&self, name: &Atom) -> &PropertyRegistrationData {
758        if let Some(registration) = self.custom_property_script_registry().get(name) {
759            return &registration.data;
760        }
761        for (data, _) in self.iter_origins() {
762            if let Some(registration) = data.custom_property_registrations.get(name) {
763                return &registration.data;
764            }
765        }
766        PropertyRegistrationData::unregistered()
767    }
768
769    /// Returns custom properties with their registered initial values.
770    pub fn get_custom_property_initial_values(&self) -> &ComputedCustomProperties {
771        &self.initial_values_for_custom_properties
772    }
773
774    /// Returns flags set from computing the registered custom property initial values.
775    pub fn get_custom_property_initial_values_flags(&self) -> ComputedValueFlags {
776        self.initial_values_for_custom_properties_flags
777    }
778
779    /// Rebuild custom properties with their registered initial values.
780    /// https://drafts.css-houdini.org/css-properties-values-api-1/#determining-registration
781    pub fn rebuild_initial_values_for_custom_properties(&mut self) {
782        let mut initial_values = ComputedCustomProperties::default();
783        let initial_values_flags;
784        {
785            let mut seen_names = PrecomputedHashSet::default();
786            let mut rule_cache_conditions = RuleCacheConditions::default();
787            let context = computed::Context::new_for_initial_at_property_value(
788                self,
789                &mut rule_cache_conditions,
790            );
791
792            for (k, v) in self.custom_property_script_registry().properties().iter() {
793                seen_names.insert(k.clone());
794                let Ok(value) = v.compute_initial_value(&context) else {
795                    continue;
796                };
797                let map = if v.inherits() {
798                    &mut initial_values.inherited
799                } else {
800                    &mut initial_values.non_inherited
801                };
802                map.insert(k, value);
803            }
804            for (data, _) in self.iter_origins() {
805                for (k, v) in data.custom_property_registrations.iter() {
806                    if seen_names.insert(k.clone()) {
807                        let last_value = &v.last().unwrap().0;
808                        let Ok(value) = last_value.compute_initial_value(&context) else {
809                            continue;
810                        };
811                        let map = if last_value.inherits() {
812                            &mut initial_values.inherited
813                        } else {
814                            &mut initial_values.non_inherited
815                        };
816                        map.insert(k, value);
817                    }
818                }
819            }
820            initial_values_flags = context.builder.flags();
821        }
822        self.initial_values_for_custom_properties_flags = initial_values_flags;
823        self.initial_values_for_custom_properties = initial_values;
824    }
825
826    /// Rebuilds (if needed) the CascadeData given a sheet collection.
827    pub fn rebuild_author_data<S>(
828        &mut self,
829        old_data: &CascadeData,
830        collection: SheetCollectionFlusher<S>,
831        guard: &SharedRwLockReadGuard,
832    ) -> Result<Option<Arc<CascadeData>>, AllocErr>
833    where
834        S: StylesheetInDocument + PartialEq + 'static,
835    {
836        self.author_data_cache
837            .lookup(&self.device, self.quirks_mode, collection, guard, old_data)
838    }
839
840    /// Iterate over the extra data in origin order.
841    #[inline]
842    pub fn iter_extra_data_origins(&self) -> ExtraStyleDataIterator {
843        ExtraStyleDataIterator(self.cascade_data.iter_origins())
844    }
845
846    /// Iterate over the extra data in reverse origin order.
847    #[inline]
848    pub fn iter_extra_data_origins_rev(&self) -> ExtraStyleDataIterator {
849        ExtraStyleDataIterator(self.cascade_data.iter_origins_rev())
850    }
851
852    /// Returns the number of selectors.
853    pub fn num_selectors(&self) -> usize {
854        self.cascade_data
855            .iter_origins()
856            .map(|(d, _)| d.num_selectors)
857            .sum()
858    }
859
860    /// Returns the number of declarations.
861    pub fn num_declarations(&self) -> usize {
862        self.cascade_data
863            .iter_origins()
864            .map(|(d, _)| d.num_declarations)
865            .sum()
866    }
867
868    /// Returns the number of times the stylist has been rebuilt.
869    pub fn num_rebuilds(&self) -> usize {
870        self.num_rebuilds
871    }
872
873    /// Returns the number of revalidation_selectors.
874    pub fn num_revalidation_selectors(&self) -> usize {
875        self.cascade_data
876            .iter_origins()
877            .map(|(data, _)| data.selectors_for_cache_revalidation.len())
878            .sum()
879    }
880
881    /// Returns the number of entries in invalidation maps.
882    pub fn num_invalidations(&self) -> usize {
883        self.cascade_data
884            .iter_origins()
885            .map(|(data, _)| {
886                data.invalidation_map.len() + data.relative_selector_invalidation_map.len()
887            })
888            .sum()
889    }
890
891    /// Returns whether the given DocumentState bit is relied upon by a selector
892    /// of some rule.
893    pub fn has_document_state_dependency(&self, state: DocumentState) -> bool {
894        self.cascade_data
895            .iter_origins()
896            .any(|(d, _)| d.document_state_dependencies.intersects(state))
897    }
898
899    /// Flush the list of stylesheets if they changed, ensuring the stylist is
900    /// up-to-date.
901    pub fn flush<E>(
902        &mut self,
903        guards: &StylesheetGuards,
904        document_element: Option<E>,
905        snapshots: Option<&SnapshotMap>,
906    ) -> bool
907    where
908        E: TElement,
909    {
910        if !self.stylesheets.has_changed() {
911            return false;
912        }
913
914        self.num_rebuilds += 1;
915
916        let flusher = self.stylesheets.flush(document_element, snapshots);
917
918        let had_invalidations = flusher.had_invalidations();
919
920        self.cascade_data
921            .rebuild(&self.device, self.quirks_mode, flusher, guards)
922            .unwrap_or_else(|_| warn!("OOM in Stylist::flush"));
923
924        self.rebuild_initial_values_for_custom_properties();
925
926        had_invalidations
927    }
928
929    /// Insert a given stylesheet before another stylesheet in the document.
930    pub fn insert_stylesheet_before(
931        &mut self,
932        sheet: StylistSheet,
933        before_sheet: StylistSheet,
934        guard: &SharedRwLockReadGuard,
935    ) {
936        self.stylesheets
937            .insert_stylesheet_before(Some(&self.device), sheet, before_sheet, guard)
938    }
939
940    /// Marks a given stylesheet origin as dirty, due to, for example, changes
941    /// in the declarations that affect a given rule.
942    ///
943    /// FIXME(emilio): Eventually it'd be nice for this to become more
944    /// fine-grained.
945    pub fn force_stylesheet_origins_dirty(&mut self, origins: OriginSet) {
946        self.stylesheets.force_dirty(origins)
947    }
948
949    /// Sets whether author style is enabled or not.
950    pub fn set_author_styles_enabled(&mut self, enabled: AuthorStylesEnabled) {
951        self.author_styles_enabled = enabled;
952    }
953
954    /// Returns whether we've recorded any stylesheet change so far.
955    pub fn stylesheets_have_changed(&self) -> bool {
956        self.stylesheets.has_changed()
957    }
958
959    /// Appends a new stylesheet to the current set.
960    pub fn append_stylesheet(&mut self, sheet: StylistSheet, guard: &SharedRwLockReadGuard) {
961        self.stylesheets
962            .append_stylesheet(Some(&self.device), sheet, guard)
963    }
964
965    /// Remove a given stylesheet to the current set.
966    pub fn remove_stylesheet(&mut self, sheet: StylistSheet, guard: &SharedRwLockReadGuard) {
967        self.stylesheets
968            .remove_stylesheet(Some(&self.device), sheet, guard)
969    }
970
971    /// Notify of a change of a given rule.
972    pub fn rule_changed(
973        &mut self,
974        sheet: &StylistSheet,
975        rule: &CssRule,
976        guard: &SharedRwLockReadGuard,
977        change_kind: RuleChangeKind,
978    ) {
979        self.stylesheets
980            .rule_changed(Some(&self.device), sheet, rule, guard, change_kind)
981    }
982
983    /// Appends a new stylesheet to the current set.
984    #[inline]
985    pub fn sheet_count(&self, origin: Origin) -> usize {
986        self.stylesheets.sheet_count(origin)
987    }
988
989    /// Appends a new stylesheet to the current set.
990    #[inline]
991    pub fn sheet_at(&self, origin: Origin, index: usize) -> Option<&StylistSheet> {
992        self.stylesheets.get(origin, index)
993    }
994
995    /// Returns whether for any of the applicable style rule data a given
996    /// condition is true.
997    pub fn any_applicable_rule_data<E, F>(&self, element: E, mut f: F) -> bool
998    where
999        E: TElement,
1000        F: FnMut(&CascadeData) -> bool,
1001    {
1002        if f(&self.cascade_data.user_agent.cascade_data) {
1003            return true;
1004        }
1005
1006        let mut maybe = false;
1007
1008        let doc_author_rules_apply =
1009            element.each_applicable_non_document_style_rule_data(|data, _| {
1010                maybe = maybe || f(&*data);
1011            });
1012
1013        if maybe || f(&self.cascade_data.user) {
1014            return true;
1015        }
1016
1017        doc_author_rules_apply && f(&self.cascade_data.author)
1018    }
1019
1020    /// Execute callback for all applicable style rule data.
1021    pub fn for_each_cascade_data_with_scope<'a, E, F>(&'a self, element: E, mut f: F)
1022    where
1023        E: TElement + 'a,
1024        F: FnMut(&'a CascadeData, Option<E>),
1025    {
1026        f(&self.cascade_data.user_agent.cascade_data, None);
1027        element.each_applicable_non_document_style_rule_data(|data, scope| {
1028            f(data, Some(scope));
1029        });
1030        f(&self.cascade_data.user, None);
1031        f(&self.cascade_data.author, None);
1032    }
1033
1034    /// Computes the style for a given "precomputed" pseudo-element, taking the
1035    /// universal rules and applying them.
1036    pub fn precomputed_values_for_pseudo<E>(
1037        &self,
1038        guards: &StylesheetGuards,
1039        pseudo: &PseudoElement,
1040        parent: Option<&ComputedValues>,
1041    ) -> Arc<ComputedValues>
1042    where
1043        E: TElement,
1044    {
1045        debug_assert!(pseudo.is_precomputed());
1046
1047        let rule_node = self.rule_node_for_precomputed_pseudo(guards, pseudo, vec![]);
1048
1049        self.precomputed_values_for_pseudo_with_rule_node::<E>(guards, pseudo, parent, rule_node)
1050    }
1051
1052    /// Computes the style for a given "precomputed" pseudo-element with
1053    /// given rule node.
1054    ///
1055    /// TODO(emilio): The type parameter could go away with a void type
1056    /// implementing TElement.
1057    pub fn precomputed_values_for_pseudo_with_rule_node<E>(
1058        &self,
1059        guards: &StylesheetGuards,
1060        pseudo: &PseudoElement,
1061        parent: Option<&ComputedValues>,
1062        rules: StrongRuleNode,
1063    ) -> Arc<ComputedValues>
1064    where
1065        E: TElement,
1066    {
1067        self.compute_pseudo_element_style_with_inputs::<E>(
1068            CascadeInputs {
1069                rules: Some(rules),
1070                visited_rules: None,
1071                flags: Default::default(),
1072            },
1073            pseudo,
1074            guards,
1075            parent,
1076            /* element */ None,
1077        )
1078    }
1079
1080    /// Returns the rule node for a given precomputed pseudo-element.
1081    ///
1082    /// If we want to include extra declarations to this precomputed
1083    /// pseudo-element, we can provide a vector of ApplicableDeclarationBlocks
1084    /// to extra_declarations. This is useful for @page rules.
1085    pub fn rule_node_for_precomputed_pseudo(
1086        &self,
1087        guards: &StylesheetGuards,
1088        pseudo: &PseudoElement,
1089        mut extra_declarations: Vec<ApplicableDeclarationBlock>,
1090    ) -> StrongRuleNode {
1091        let mut declarations_with_extra;
1092        let declarations = match self
1093            .cascade_data
1094            .user_agent
1095            .precomputed_pseudo_element_decls
1096            .get(pseudo)
1097        {
1098            Some(declarations) => {
1099                if !extra_declarations.is_empty() {
1100                    declarations_with_extra = declarations.clone();
1101                    declarations_with_extra.append(&mut extra_declarations);
1102                    &*declarations_with_extra
1103                } else {
1104                    &**declarations
1105                }
1106            },
1107            None => &[],
1108        };
1109
1110        self.rule_tree.insert_ordered_rules_with_important(
1111            declarations.into_iter().map(|a| a.clone().for_rule_tree()),
1112            guards,
1113        )
1114    }
1115
1116    /// Returns the style for an anonymous box of the given type.
1117    ///
1118    /// TODO(emilio): The type parameter could go away with a void type
1119    /// implementing TElement.
1120    #[cfg(feature = "servo")]
1121    pub fn style_for_anonymous<E>(
1122        &self,
1123        guards: &StylesheetGuards,
1124        pseudo: &PseudoElement,
1125        parent_style: &ComputedValues,
1126    ) -> Arc<ComputedValues>
1127    where
1128        E: TElement,
1129    {
1130        self.precomputed_values_for_pseudo::<E>(guards, &pseudo, Some(parent_style))
1131    }
1132
1133    /// Computes a pseudo-element style lazily during layout.
1134    ///
1135    /// This can only be done for a certain set of pseudo-elements, like
1136    /// :selection.
1137    ///
1138    /// Check the documentation on lazy pseudo-elements in
1139    /// docs/components/style.md
1140    pub fn lazily_compute_pseudo_element_style<E>(
1141        &self,
1142        guards: &StylesheetGuards,
1143        element: E,
1144        pseudo: &PseudoElement,
1145        rule_inclusion: RuleInclusion,
1146        originating_element_style: &ComputedValues,
1147        is_probe: bool,
1148        matching_fn: Option<&dyn Fn(&PseudoElement) -> bool>,
1149    ) -> Option<Arc<ComputedValues>>
1150    where
1151        E: TElement,
1152    {
1153        let cascade_inputs = self.lazy_pseudo_rules(
1154            guards,
1155            element,
1156            originating_element_style,
1157            pseudo,
1158            is_probe,
1159            rule_inclusion,
1160            matching_fn,
1161        )?;
1162
1163        Some(self.compute_pseudo_element_style_with_inputs(
1164            cascade_inputs,
1165            pseudo,
1166            guards,
1167            Some(originating_element_style),
1168            Some(element),
1169        ))
1170    }
1171
1172    /// Computes a pseudo-element style lazily using the given CascadeInputs.
1173    /// This can be used for truly lazy pseudo-elements or to avoid redoing
1174    /// selector matching for eager pseudo-elements when we need to recompute
1175    /// their style with a new parent style.
1176    pub fn compute_pseudo_element_style_with_inputs<E>(
1177        &self,
1178        inputs: CascadeInputs,
1179        pseudo: &PseudoElement,
1180        guards: &StylesheetGuards,
1181        parent_style: Option<&ComputedValues>,
1182        element: Option<E>,
1183    ) -> Arc<ComputedValues>
1184    where
1185        E: TElement,
1186    {
1187        // FIXME(emilio): The lack of layout_parent_style here could be
1188        // worrying, but we're probably dropping the display fixup for
1189        // pseudos other than before and after, so it's probably ok.
1190        //
1191        // (Though the flags don't indicate so!)
1192        //
1193        // It'd be fine to assert that this isn't called with a parent style
1194        // where display contents is in effect, but in practice this is hard to
1195        // do for stuff like :-moz-fieldset-content with a
1196        // <fieldset style="display: contents">. That is, the computed value of
1197        // display for the fieldset is "contents", even though it's not the used
1198        // value, so we don't need to adjust in a different way anyway.
1199        self.cascade_style_and_visited(
1200            element,
1201            Some(pseudo),
1202            inputs,
1203            guards,
1204            parent_style,
1205            parent_style,
1206            FirstLineReparenting::No,
1207            /* rule_cache = */ None,
1208            &mut RuleCacheConditions::default(),
1209        )
1210    }
1211
1212    /// Computes a style using the given CascadeInputs.  This can be used to
1213    /// compute a style any time we know what rules apply and just need to use
1214    /// the given parent styles.
1215    ///
1216    /// parent_style is the style to inherit from for properties affected by
1217    /// first-line ancestors.
1218    ///
1219    /// parent_style_ignoring_first_line is the style to inherit from for
1220    /// properties not affected by first-line ancestors.
1221    ///
1222    /// layout_parent_style is the style used for some property fixups.  It's
1223    /// the style of the nearest ancestor with a layout box.
1224    pub fn cascade_style_and_visited<E>(
1225        &self,
1226        element: Option<E>,
1227        pseudo: Option<&PseudoElement>,
1228        inputs: CascadeInputs,
1229        guards: &StylesheetGuards,
1230        parent_style: Option<&ComputedValues>,
1231        layout_parent_style: Option<&ComputedValues>,
1232        first_line_reparenting: FirstLineReparenting,
1233        rule_cache: Option<&RuleCache>,
1234        rule_cache_conditions: &mut RuleCacheConditions,
1235    ) -> Arc<ComputedValues>
1236    where
1237        E: TElement,
1238    {
1239        debug_assert!(pseudo.is_some() || element.is_some(), "Huh?");
1240
1241        // We need to compute visited values if we have visited rules or if our
1242        // parent has visited values.
1243        let visited_rules = match inputs.visited_rules.as_ref() {
1244            Some(rules) => Some(rules),
1245            None => {
1246                if parent_style.and_then(|s| s.visited_style()).is_some() {
1247                    Some(inputs.rules.as_ref().unwrap_or(self.rule_tree.root()))
1248                } else {
1249                    None
1250                }
1251            },
1252        };
1253
1254        let mut implemented_pseudo = None;
1255        // Read the comment on `precomputed_values_for_pseudo` to see why it's
1256        // difficult to assert that display: contents nodes never arrive here
1257        // (tl;dr: It doesn't apply for replaced elements and such, but the
1258        // computed value is still "contents").
1259        //
1260        // FIXME(emilio): We should assert that it holds if pseudo.is_none()!
1261        properties::cascade::<E>(
1262            &self,
1263            pseudo.or_else(|| {
1264                implemented_pseudo = element.unwrap().implemented_pseudo_element();
1265                implemented_pseudo.as_ref()
1266            }),
1267            inputs.rules.as_ref().unwrap_or(self.rule_tree.root()),
1268            guards,
1269            parent_style,
1270            layout_parent_style,
1271            first_line_reparenting,
1272            visited_rules,
1273            inputs.flags,
1274            rule_cache,
1275            rule_cache_conditions,
1276            element,
1277        )
1278    }
1279
1280    /// Computes the cascade inputs for a lazily-cascaded pseudo-element.
1281    ///
1282    /// See the documentation on lazy pseudo-elements in
1283    /// docs/components/style.md
1284    fn lazy_pseudo_rules<E>(
1285        &self,
1286        guards: &StylesheetGuards,
1287        element: E,
1288        originating_element_style: &ComputedValues,
1289        pseudo: &PseudoElement,
1290        is_probe: bool,
1291        rule_inclusion: RuleInclusion,
1292        matching_fn: Option<&dyn Fn(&PseudoElement) -> bool>,
1293    ) -> Option<CascadeInputs>
1294    where
1295        E: TElement,
1296    {
1297        debug_assert!(pseudo.is_lazy());
1298
1299        let mut selector_caches = SelectorCaches::default();
1300        // No need to bother setting the selector flags when we're computing
1301        // default styles.
1302        let needs_selector_flags = if rule_inclusion == RuleInclusion::DefaultOnly {
1303            NeedsSelectorFlags::No
1304        } else {
1305            NeedsSelectorFlags::Yes
1306        };
1307
1308        let mut declarations = ApplicableDeclarationList::new();
1309        let mut matching_context = MatchingContext::<'_, E::Impl>::new(
1310            MatchingMode::ForStatelessPseudoElement,
1311            None,
1312            &mut selector_caches,
1313            self.quirks_mode,
1314            needs_selector_flags,
1315            MatchingForInvalidation::No,
1316        );
1317
1318        matching_context.pseudo_element_matching_fn = matching_fn;
1319        matching_context.extra_data.originating_element_style = Some(originating_element_style);
1320
1321        self.push_applicable_declarations(
1322            element,
1323            Some(&pseudo),
1324            None,
1325            None,
1326            /* animation_declarations = */ Default::default(),
1327            rule_inclusion,
1328            &mut declarations,
1329            &mut matching_context,
1330        );
1331
1332        if declarations.is_empty() && is_probe {
1333            return None;
1334        }
1335
1336        let rules = self.rule_tree.compute_rule_node(&mut declarations, guards);
1337
1338        let mut visited_rules = None;
1339        if originating_element_style.visited_style().is_some() {
1340            let mut declarations = ApplicableDeclarationList::new();
1341            let mut selector_caches = SelectorCaches::default();
1342
1343            let mut matching_context = MatchingContext::<'_, E::Impl>::new_for_visited(
1344                MatchingMode::ForStatelessPseudoElement,
1345                None,
1346                &mut selector_caches,
1347                VisitedHandlingMode::RelevantLinkVisited,
1348                selectors::matching::IncludeStartingStyle::No,
1349                self.quirks_mode,
1350                needs_selector_flags,
1351                MatchingForInvalidation::No,
1352            );
1353            matching_context.pseudo_element_matching_fn = matching_fn;
1354            matching_context.extra_data.originating_element_style = Some(originating_element_style);
1355
1356            self.push_applicable_declarations(
1357                element,
1358                Some(&pseudo),
1359                None,
1360                None,
1361                /* animation_declarations = */ Default::default(),
1362                rule_inclusion,
1363                &mut declarations,
1364                &mut matching_context,
1365            );
1366            if !declarations.is_empty() {
1367                let rule_node = self.rule_tree.insert_ordered_rules_with_important(
1368                    declarations.drain(..).map(|a| a.for_rule_tree()),
1369                    guards,
1370                );
1371                if rule_node != *self.rule_tree.root() {
1372                    visited_rules = Some(rule_node);
1373                }
1374            }
1375        }
1376
1377        Some(CascadeInputs {
1378            rules: Some(rules),
1379            visited_rules,
1380            flags: matching_context.extra_data.cascade_input_flags,
1381        })
1382    }
1383
1384    /// Set a given device, which may change the styles that apply to the
1385    /// document.
1386    ///
1387    /// Returns the sheet origins that were actually affected.
1388    ///
1389    /// This means that we may need to rebuild style data even if the
1390    /// stylesheets haven't changed.
1391    ///
1392    /// Also, the device that arrives here may need to take the viewport rules
1393    /// into account.
1394    pub fn set_device(&mut self, device: Device, guards: &StylesheetGuards) -> OriginSet {
1395        self.device = device;
1396        self.media_features_change_changed_style(guards, &self.device)
1397    }
1398
1399    /// Returns whether, given a media feature change, any previously-applicable
1400    /// style has become non-applicable, or vice-versa for each origin, using
1401    /// `device`.
1402    pub fn media_features_change_changed_style(
1403        &self,
1404        guards: &StylesheetGuards,
1405        device: &Device,
1406    ) -> OriginSet {
1407        debug!("Stylist::media_features_change_changed_style {:?}", device);
1408
1409        let mut origins = OriginSet::empty();
1410        let stylesheets = self.stylesheets.iter();
1411
1412        for (stylesheet, origin) in stylesheets {
1413            if origins.contains(origin.into()) {
1414                continue;
1415            }
1416
1417            let guard = guards.for_origin(origin);
1418            let origin_cascade_data = self.cascade_data.borrow_for_origin(origin);
1419
1420            let affected_changed = !origin_cascade_data.media_feature_affected_matches(
1421                stylesheet,
1422                guard,
1423                device,
1424                self.quirks_mode,
1425            );
1426
1427            if affected_changed {
1428                origins |= origin;
1429            }
1430        }
1431
1432        origins
1433    }
1434
1435    /// Returns the Quirks Mode of the document.
1436    pub fn quirks_mode(&self) -> QuirksMode {
1437        self.quirks_mode
1438    }
1439
1440    /// Sets the quirks mode of the document.
1441    pub fn set_quirks_mode(&mut self, quirks_mode: QuirksMode) {
1442        if self.quirks_mode == quirks_mode {
1443            return;
1444        }
1445        self.quirks_mode = quirks_mode;
1446        self.force_stylesheet_origins_dirty(OriginSet::all());
1447    }
1448
1449    /// Returns the applicable CSS declarations for the given element.
1450    pub fn push_applicable_declarations<E>(
1451        &self,
1452        element: E,
1453        pseudo_element: Option<&PseudoElement>,
1454        style_attribute: Option<ArcBorrow<Locked<PropertyDeclarationBlock>>>,
1455        smil_override: Option<ArcBorrow<Locked<PropertyDeclarationBlock>>>,
1456        animation_declarations: AnimationDeclarations,
1457        rule_inclusion: RuleInclusion,
1458        applicable_declarations: &mut ApplicableDeclarationList,
1459        context: &mut MatchingContext<E::Impl>,
1460    ) where
1461        E: TElement,
1462    {
1463        let mut cur = element;
1464        let mut pseudos = SmallVec::new();
1465        if let Some(pseudo) = pseudo_element {
1466            pseudos.push(pseudo.clone());
1467        }
1468        while let Some(p) = cur.implemented_pseudo_element() {
1469            pseudos.push(p);
1470            let Some(parent_pseudo) = cur.pseudo_element_originating_element() else {
1471                break;
1472            };
1473            cur = parent_pseudo;
1474        }
1475        RuleCollector::new(
1476            self,
1477            element,
1478            pseudos,
1479            style_attribute,
1480            smil_override,
1481            animation_declarations,
1482            rule_inclusion,
1483            applicable_declarations,
1484            context,
1485        )
1486        .collect_all();
1487    }
1488
1489    /// Given an id, returns whether there might be any rules for that id in any
1490    /// of our rule maps.
1491    #[inline]
1492    pub fn may_have_rules_for_id<E>(&self, id: &WeakAtom, element: E) -> bool
1493    where
1494        E: TElement,
1495    {
1496        // If id needs to be compared case-insensitively, the logic below
1497        // wouldn't work. Just conservatively assume it may have such rules.
1498        match self.quirks_mode().classes_and_ids_case_sensitivity() {
1499            CaseSensitivity::AsciiCaseInsensitive => return true,
1500            CaseSensitivity::CaseSensitive => {},
1501        }
1502
1503        self.any_applicable_rule_data(element, |data| data.mapped_ids.contains(id))
1504    }
1505
1506    /// Returns the registered `@keyframes` animation for the specified name.
1507    #[inline]
1508    pub fn get_animation<'a, E>(&'a self, name: &Atom, element: E) -> Option<&'a KeyframesAnimation>
1509    where
1510        E: TElement + 'a,
1511    {
1512        macro_rules! try_find_in {
1513            ($data:expr) => {
1514                if let Some(animation) = $data.animations.get(name) {
1515                    return Some(animation);
1516                }
1517            };
1518        }
1519
1520        // NOTE(emilio): This is a best-effort thing, the right fix is a bit TBD because it
1521        // involves "recording" which tree the name came from, see [1][2].
1522        //
1523        // [1]: https://github.com/w3c/csswg-drafts/issues/1995
1524        // [2]: https://bugzil.la/1458189
1525        let mut animation = None;
1526        let doc_rules_apply =
1527            element.each_applicable_non_document_style_rule_data(|data, _host| {
1528                if animation.is_none() {
1529                    animation = data.animations.get(name);
1530                }
1531            });
1532
1533        if animation.is_some() {
1534            return animation;
1535        }
1536
1537        if doc_rules_apply {
1538            try_find_in!(self.cascade_data.author);
1539        }
1540        try_find_in!(self.cascade_data.user);
1541        try_find_in!(self.cascade_data.user_agent.cascade_data);
1542
1543        None
1544    }
1545
1546    /// Computes the match results of a given element against the set of
1547    /// revalidation selectors.
1548    pub fn match_revalidation_selectors<E>(
1549        &self,
1550        element: E,
1551        bloom: Option<&BloomFilter>,
1552        selector_caches: &mut SelectorCaches,
1553        needs_selector_flags: NeedsSelectorFlags,
1554    ) -> RevalidationResult
1555    where
1556        E: TElement,
1557    {
1558        // NB: `MatchingMode` doesn't really matter, given we don't share style
1559        // between pseudos.
1560        let mut matching_context = MatchingContext::new(
1561            MatchingMode::Normal,
1562            bloom,
1563            selector_caches,
1564            self.quirks_mode,
1565            needs_selector_flags,
1566            MatchingForInvalidation::No,
1567        );
1568
1569        // Note that, by the time we're revalidating, we're guaranteed that the
1570        // candidate and the entry have the same id, classes, and local name.
1571        // This means we're guaranteed to get the same rulehash buckets for all
1572        // the lookups, which means that the bitvecs are comparable. We verify
1573        // this in the caller by asserting that the bitvecs are same-length.
1574        let mut result = RevalidationResult::default();
1575        let mut relevant_attributes = &mut result.relevant_attributes;
1576        let selectors_matched = &mut result.selectors_matched;
1577
1578        let matches_document_rules =
1579            element.each_applicable_non_document_style_rule_data(|data, host| {
1580                matching_context.with_shadow_host(Some(host), |matching_context| {
1581                    data.selectors_for_cache_revalidation.lookup(
1582                        element,
1583                        self.quirks_mode,
1584                        Some(&mut relevant_attributes),
1585                        |selector_and_hashes| {
1586                            selectors_matched.push(matches_selector(
1587                                &selector_and_hashes.selector,
1588                                selector_and_hashes.selector_offset,
1589                                Some(&selector_and_hashes.hashes),
1590                                &element,
1591                                matching_context,
1592                            ));
1593                            true
1594                        },
1595                    );
1596                })
1597            });
1598
1599        for (data, origin) in self.cascade_data.iter_origins() {
1600            if origin == Origin::Author && !matches_document_rules {
1601                continue;
1602            }
1603
1604            data.selectors_for_cache_revalidation.lookup(
1605                element,
1606                self.quirks_mode,
1607                Some(&mut relevant_attributes),
1608                |selector_and_hashes| {
1609                    selectors_matched.push(matches_selector(
1610                        &selector_and_hashes.selector,
1611                        selector_and_hashes.selector_offset,
1612                        Some(&selector_and_hashes.hashes),
1613                        &element,
1614                        &mut matching_context,
1615                    ));
1616                    true
1617                },
1618            );
1619        }
1620
1621        result
1622    }
1623
1624    /// Computes currently active scopes for the given element for revalidation purposes.
1625    pub fn revalidate_scopes<E: TElement>(
1626        &self,
1627        element: &E,
1628        selector_caches: &mut SelectorCaches,
1629        needs_selector_flags: NeedsSelectorFlags,
1630    ) -> ScopeRevalidationResult {
1631        let mut matching_context = MatchingContext::new(
1632            MatchingMode::Normal,
1633            None,
1634            selector_caches,
1635            self.quirks_mode,
1636            needs_selector_flags,
1637            MatchingForInvalidation::No,
1638        );
1639
1640        let mut result = ScopeRevalidationResult::default();
1641        let matches_document_rules =
1642            element.each_applicable_non_document_style_rule_data(|data, host| {
1643                matching_context.with_shadow_host(Some(host), |matching_context| {
1644                    data.revalidate_scopes(self, element, matching_context, &mut result);
1645                })
1646            });
1647
1648        for (data, origin) in self.cascade_data.iter_origins() {
1649            if origin == Origin::Author && !matches_document_rules {
1650                continue;
1651            }
1652
1653            data.revalidate_scopes(self, element, &mut matching_context, &mut result);
1654        }
1655
1656        result
1657    }
1658
1659    /// Computes styles for a given declaration with parent_style.
1660    ///
1661    /// FIXME(emilio): the lack of pseudo / cascade flags look quite dubious,
1662    /// hopefully this is only used for some canvas font stuff.
1663    ///
1664    /// TODO(emilio): The type parameter can go away when
1665    /// https://github.com/rust-lang/rust/issues/35121 is fixed.
1666    pub fn compute_for_declarations<E>(
1667        &self,
1668        guards: &StylesheetGuards,
1669        parent_style: &ComputedValues,
1670        declarations: Arc<Locked<PropertyDeclarationBlock>>,
1671    ) -> Arc<ComputedValues>
1672    where
1673        E: TElement,
1674    {
1675        let block = declarations.read_with(guards.author);
1676
1677        // We don't bother inserting these declarations in the rule tree, since
1678        // it'd be quite useless and slow.
1679        //
1680        // TODO(emilio): Now that we fixed bug 1493420, we should consider
1681        // reversing this as it shouldn't be slow anymore, and should avoid
1682        // generating two instantiations of apply_declarations.
1683        properties::apply_declarations::<E, _>(
1684            &self,
1685            /* pseudo = */ None,
1686            self.rule_tree.root(),
1687            guards,
1688            block.declaration_importance_iter().map(|(declaration, _)| {
1689                (
1690                    declaration,
1691                    CascadePriority::new(
1692                        CascadeLevel::same_tree_author_normal(),
1693                        LayerOrder::root(),
1694                    ),
1695                )
1696            }),
1697            Some(parent_style),
1698            Some(parent_style),
1699            FirstLineReparenting::No,
1700            CascadeMode::Unvisited {
1701                visited_rules: None,
1702            },
1703            Default::default(),
1704            /* rule_cache = */ None,
1705            &mut Default::default(),
1706            /* element = */ None,
1707        )
1708    }
1709
1710    /// Accessor for a shared reference to the device.
1711    #[inline]
1712    pub fn device(&self) -> &Device {
1713        &self.device
1714    }
1715
1716    /// Accessor for a mutable reference to the device.
1717    #[inline]
1718    pub fn device_mut(&mut self) -> &mut Device {
1719        &mut self.device
1720    }
1721
1722    /// Accessor for a shared reference to the rule tree.
1723    #[inline]
1724    pub fn rule_tree(&self) -> &RuleTree {
1725        &self.rule_tree
1726    }
1727
1728    /// Returns the script-registered custom property registry.
1729    #[inline]
1730    pub fn custom_property_script_registry(&self) -> &CustomPropertyScriptRegistry {
1731        &self.script_custom_properties
1732    }
1733
1734    /// Returns the script-registered custom property registry, as a mutable ref.
1735    #[inline]
1736    pub fn custom_property_script_registry_mut(&mut self) -> &mut CustomPropertyScriptRegistry {
1737        &mut self.script_custom_properties
1738    }
1739
1740    /// Measures heap usage.
1741    #[cfg(feature = "gecko")]
1742    pub fn add_size_of(&self, ops: &mut MallocSizeOfOps, sizes: &mut ServoStyleSetSizes) {
1743        self.cascade_data.add_size_of(ops, sizes);
1744        self.author_data_cache.add_size_of(ops, sizes);
1745        sizes.mRuleTree += self.rule_tree.size_of(ops);
1746
1747        // We may measure other fields in the future if DMD says it's worth it.
1748    }
1749
1750    /// Shutdown the static data that this module stores.
1751    pub fn shutdown() {
1752        let _entries = UA_CASCADE_DATA_CACHE.lock().unwrap().take_all();
1753    }
1754}
1755
1756/// A vector that is sorted in layer order.
1757#[derive(Clone, Debug, Deref, MallocSizeOf)]
1758pub struct LayerOrderedVec<T>(Vec<(T, LayerId)>);
1759impl<T> Default for LayerOrderedVec<T> {
1760    fn default() -> Self {
1761        Self(Default::default())
1762    }
1763}
1764
1765/// A map that is sorted in layer order.
1766#[derive(Clone, Debug, Deref, MallocSizeOf)]
1767pub struct LayerOrderedMap<T>(PrecomputedHashMap<Atom, SmallVec<[(T, LayerId); 1]>>);
1768impl<T> Default for LayerOrderedMap<T> {
1769    fn default() -> Self {
1770        Self(Default::default())
1771    }
1772}
1773
1774#[cfg(feature = "gecko")]
1775impl<T: 'static> LayerOrderedVec<T> {
1776    fn clear(&mut self) {
1777        self.0.clear();
1778    }
1779    fn push(&mut self, v: T, id: LayerId) {
1780        self.0.push((v, id));
1781    }
1782    fn sort(&mut self, layers: &[CascadeLayer]) {
1783        self.0
1784            .sort_by_key(|&(_, ref id)| layers[id.0 as usize].order)
1785    }
1786}
1787
1788impl<T: 'static> LayerOrderedMap<T> {
1789    fn shrink_if_needed(&mut self) {
1790        self.0.shrink_if_needed();
1791    }
1792    fn clear(&mut self) {
1793        self.0.clear();
1794    }
1795    fn try_insert(&mut self, name: Atom, v: T, id: LayerId) -> Result<(), AllocErr> {
1796        self.try_insert_with(name, v, id, |_, _| Ordering::Equal)
1797    }
1798    fn try_insert_with(
1799        &mut self,
1800        name: Atom,
1801        v: T,
1802        id: LayerId,
1803        cmp: impl Fn(&T, &T) -> Ordering,
1804    ) -> Result<(), AllocErr> {
1805        self.0.try_reserve(1)?;
1806        let vec = self.0.entry(name).or_default();
1807        if let Some(&mut (ref mut val, ref last_id)) = vec.last_mut() {
1808            if *last_id == id {
1809                if cmp(&val, &v) != Ordering::Greater {
1810                    *val = v;
1811                }
1812                return Ok(());
1813            }
1814        }
1815        vec.push((v, id));
1816        Ok(())
1817    }
1818    fn sort(&mut self, layers: &[CascadeLayer]) {
1819        self.sort_with(layers, |_, _| Ordering::Equal)
1820    }
1821    fn sort_with(&mut self, layers: &[CascadeLayer], cmp: impl Fn(&T, &T) -> Ordering) {
1822        for (_, v) in self.0.iter_mut() {
1823            v.sort_by(|&(ref v1, ref id1), &(ref v2, ref id2)| {
1824                let order1 = layers[id1.0 as usize].order;
1825                let order2 = layers[id2.0 as usize].order;
1826                order1.cmp(&order2).then_with(|| cmp(v1, v2))
1827            })
1828        }
1829    }
1830    /// Get an entry on the LayerOrderedMap by name.
1831    pub fn get(&self, name: &Atom) -> Option<&T> {
1832        let vec = self.0.get(name)?;
1833        Some(&vec.last()?.0)
1834    }
1835}
1836
1837/// Wrapper to allow better tracking of memory usage by page rule lists.
1838///
1839/// This includes the layer ID for use with the named page table.
1840#[derive(Clone, Debug, MallocSizeOf)]
1841pub struct PageRuleData {
1842    /// Layer ID for sorting page rules after matching.
1843    pub layer: LayerId,
1844    /// Page rule
1845    #[ignore_malloc_size_of = "Arc, stylesheet measures as primary ref"]
1846    pub rule: Arc<Locked<PageRule>>,
1847}
1848
1849/// Stores page rules indexed by page names.
1850#[derive(Clone, Debug, Default, MallocSizeOf)]
1851pub struct PageRuleMap {
1852    /// Page rules, indexed by page name. An empty atom indicates no page name.
1853    pub rules: PrecomputedHashMap<Atom, SmallVec<[PageRuleData; 1]>>,
1854}
1855
1856#[cfg(feature = "gecko")]
1857impl PageRuleMap {
1858    #[inline]
1859    fn clear(&mut self) {
1860        self.rules.clear();
1861    }
1862
1863    /// Uses page-name and pseudo-classes to match all applicable
1864    /// page-rules and append them to the matched_rules vec.
1865    /// This will ensure correct rule order for cascading.
1866    pub fn match_and_append_rules(
1867        &self,
1868        matched_rules: &mut Vec<ApplicableDeclarationBlock>,
1869        origin: Origin,
1870        guards: &StylesheetGuards,
1871        cascade_data: &DocumentCascadeData,
1872        name: &Option<Atom>,
1873        pseudos: PagePseudoClassFlags,
1874    ) {
1875        let level = match origin {
1876            Origin::UserAgent => CascadeLevel::UANormal,
1877            Origin::User => CascadeLevel::UserNormal,
1878            Origin::Author => CascadeLevel::same_tree_author_normal(),
1879        };
1880        let cascade_data = cascade_data.borrow_for_origin(origin);
1881        let start = matched_rules.len();
1882
1883        self.match_and_add_rules(
1884            matched_rules,
1885            level,
1886            guards,
1887            cascade_data,
1888            &atom!(""),
1889            pseudos,
1890        );
1891        if let Some(name) = name {
1892            self.match_and_add_rules(matched_rules, level, guards, cascade_data, name, pseudos);
1893        }
1894
1895        // Because page-rules do not have source location information stored,
1896        // use stable sort to ensure source locations are preserved.
1897        matched_rules[start..].sort_by_key(|block| block.sort_key());
1898    }
1899
1900    fn match_and_add_rules(
1901        &self,
1902        extra_declarations: &mut Vec<ApplicableDeclarationBlock>,
1903        level: CascadeLevel,
1904        guards: &StylesheetGuards,
1905        cascade_data: &CascadeData,
1906        name: &Atom,
1907        pseudos: PagePseudoClassFlags,
1908    ) {
1909        let rules = match self.rules.get(name) {
1910            Some(rules) => rules,
1911            None => return,
1912        };
1913        for data in rules.iter() {
1914            let rule = data.rule.read_with(level.guard(&guards));
1915            let specificity = match rule.match_specificity(pseudos) {
1916                Some(specificity) => specificity,
1917                None => continue,
1918            };
1919            let block = rule.block.clone();
1920            extra_declarations.push(ApplicableDeclarationBlock::new(
1921                StyleSource::from_declarations(block),
1922                0,
1923                level,
1924                specificity,
1925                cascade_data.layer_order_for(data.layer),
1926                ScopeProximity::infinity(), // Page rule can't have nested rules anyway.
1927            ));
1928        }
1929    }
1930}
1931
1932impl MallocShallowSizeOf for PageRuleMap {
1933    fn shallow_size_of(&self, ops: &mut MallocSizeOfOps) -> usize {
1934        self.rules.shallow_size_of(ops)
1935    }
1936}
1937
1938/// This struct holds data which users of Stylist may want to extract
1939/// from stylesheets which can be done at the same time as updating.
1940#[derive(Clone, Debug, Default)]
1941#[cfg_attr(feature = "servo", derive(MallocSizeOf))]
1942pub struct ExtraStyleData {
1943    /// A list of effective font-face rules and their origin.
1944    #[cfg(feature = "gecko")]
1945    pub font_faces: LayerOrderedVec<Arc<Locked<FontFaceRule>>>,
1946
1947    /// A list of effective font-feature-values rules.
1948    #[cfg(feature = "gecko")]
1949    pub font_feature_values: LayerOrderedVec<Arc<FontFeatureValuesRule>>,
1950
1951    /// A list of effective font-palette-values rules.
1952    #[cfg(feature = "gecko")]
1953    pub font_palette_values: LayerOrderedVec<Arc<FontPaletteValuesRule>>,
1954
1955    /// A map of effective counter-style rules.
1956    #[cfg(feature = "gecko")]
1957    pub counter_styles: LayerOrderedMap<Arc<Locked<CounterStyleRule>>>,
1958
1959    /// A map of effective page rules.
1960    #[cfg(feature = "gecko")]
1961    pub pages: PageRuleMap,
1962}
1963
1964#[cfg(feature = "gecko")]
1965impl ExtraStyleData {
1966    /// Add the given @font-face rule.
1967    fn add_font_face(&mut self, rule: &Arc<Locked<FontFaceRule>>, layer: LayerId) {
1968        self.font_faces.push(rule.clone(), layer);
1969    }
1970
1971    /// Add the given @font-feature-values rule.
1972    fn add_font_feature_values(&mut self, rule: &Arc<FontFeatureValuesRule>, layer: LayerId) {
1973        self.font_feature_values.push(rule.clone(), layer);
1974    }
1975
1976    /// Add the given @font-palette-values rule.
1977    fn add_font_palette_values(&mut self, rule: &Arc<FontPaletteValuesRule>, layer: LayerId) {
1978        self.font_palette_values.push(rule.clone(), layer);
1979    }
1980
1981    /// Add the given @counter-style rule.
1982    fn add_counter_style(
1983        &mut self,
1984        guard: &SharedRwLockReadGuard,
1985        rule: &Arc<Locked<CounterStyleRule>>,
1986        layer: LayerId,
1987    ) -> Result<(), AllocErr> {
1988        let name = rule.read_with(guard).name().0.clone();
1989        self.counter_styles.try_insert(name, rule.clone(), layer)
1990    }
1991
1992    /// Add the given @page rule.
1993    fn add_page(
1994        &mut self,
1995        guard: &SharedRwLockReadGuard,
1996        rule: &Arc<Locked<PageRule>>,
1997        layer: LayerId,
1998    ) -> Result<(), AllocErr> {
1999        let page_rule = rule.read_with(guard);
2000        let mut add_rule = |name| {
2001            let vec = self.pages.rules.entry(name).or_default();
2002            vec.push(PageRuleData {
2003                layer,
2004                rule: rule.clone(),
2005            });
2006        };
2007        if page_rule.selectors.0.is_empty() {
2008            add_rule(atom!(""));
2009        } else {
2010            for selector in page_rule.selectors.as_slice() {
2011                add_rule(selector.name.0.clone());
2012            }
2013        }
2014        Ok(())
2015    }
2016
2017    fn sort_by_layer(&mut self, layers: &[CascadeLayer]) {
2018        self.font_faces.sort(layers);
2019        self.font_feature_values.sort(layers);
2020        self.font_palette_values.sort(layers);
2021        self.counter_styles.sort(layers);
2022    }
2023
2024    fn clear(&mut self) {
2025        #[cfg(feature = "gecko")]
2026        {
2027            self.font_faces.clear();
2028            self.font_feature_values.clear();
2029            self.font_palette_values.clear();
2030            self.counter_styles.clear();
2031            self.pages.clear();
2032        }
2033    }
2034}
2035
2036// Don't let a prefixed keyframes animation override
2037// a non-prefixed one.
2038fn compare_keyframes_in_same_layer(v1: &KeyframesAnimation, v2: &KeyframesAnimation) -> Ordering {
2039    if v1.vendor_prefix.is_some() == v2.vendor_prefix.is_some() {
2040        Ordering::Equal
2041    } else if v2.vendor_prefix.is_some() {
2042        Ordering::Greater
2043    } else {
2044        Ordering::Less
2045    }
2046}
2047
2048/// An iterator over the different ExtraStyleData.
2049pub struct ExtraStyleDataIterator<'a>(DocumentCascadeDataIter<'a>);
2050
2051impl<'a> Iterator for ExtraStyleDataIterator<'a> {
2052    type Item = (&'a ExtraStyleData, Origin);
2053
2054    fn next(&mut self) -> Option<Self::Item> {
2055        self.0.next().map(|d| (&d.0.extra_data, d.1))
2056    }
2057}
2058
2059#[cfg(feature = "gecko")]
2060impl MallocSizeOf for ExtraStyleData {
2061    /// Measure heap usage.
2062    fn size_of(&self, ops: &mut MallocSizeOfOps) -> usize {
2063        let mut n = 0;
2064        n += self.font_faces.shallow_size_of(ops);
2065        n += self.font_feature_values.shallow_size_of(ops);
2066        n += self.font_palette_values.shallow_size_of(ops);
2067        n += self.counter_styles.shallow_size_of(ops);
2068        n += self.pages.shallow_size_of(ops);
2069        n
2070    }
2071}
2072
2073/// SelectorMapEntry implementation for use in our revalidation selector map.
2074#[cfg_attr(feature = "gecko", derive(MallocSizeOf))]
2075#[derive(Clone, Debug)]
2076struct RevalidationSelectorAndHashes {
2077    #[cfg_attr(
2078        feature = "gecko",
2079        ignore_malloc_size_of = "CssRules have primary refs, we measure there"
2080    )]
2081    selector: Selector<SelectorImpl>,
2082    selector_offset: usize,
2083    hashes: AncestorHashes,
2084}
2085
2086impl RevalidationSelectorAndHashes {
2087    fn new(selector: Selector<SelectorImpl>, hashes: AncestorHashes) -> Self {
2088        let selector_offset = {
2089            // We basically want to check whether the first combinator is a
2090            // pseudo-element combinator.  If it is, we want to use the offset
2091            // one past it.  Otherwise, our offset is 0.
2092            let mut index = 0;
2093            let mut iter = selector.iter();
2094
2095            // First skip over the first ComplexSelector.
2096            //
2097            // We can't check what sort of what combinator we have until we do
2098            // that.
2099            for _ in &mut iter {
2100                index += 1; // Simple selector
2101            }
2102
2103            match iter.next_sequence() {
2104                Some(Combinator::PseudoElement) => index + 1, // +1 for the combinator
2105                _ => 0,
2106            }
2107        };
2108
2109        RevalidationSelectorAndHashes {
2110            selector,
2111            selector_offset,
2112            hashes,
2113        }
2114    }
2115}
2116
2117impl SelectorMapEntry for RevalidationSelectorAndHashes {
2118    fn selector(&self) -> SelectorIter<SelectorImpl> {
2119        self.selector.iter_from(self.selector_offset)
2120    }
2121}
2122
2123/// A selector visitor implementation that collects all the state the Stylist
2124/// cares about a selector.
2125struct StylistSelectorVisitor<'a> {
2126    /// Whether we've past the rightmost compound selector, not counting
2127    /// pseudo-elements.
2128    passed_rightmost_selector: bool,
2129
2130    /// Whether the selector needs revalidation for the style sharing cache.
2131    needs_revalidation: &'a mut bool,
2132
2133    /// Flags for which selector list-containing components the visitor is
2134    /// inside of, if any
2135    in_selector_list_of: SelectorListKind,
2136
2137    /// The filter with all the id's getting referenced from rightmost
2138    /// selectors.
2139    mapped_ids: &'a mut PrecomputedHashSet<Atom>,
2140
2141    /// The filter with the IDs getting referenced from the selector list of
2142    /// :nth-child(... of <selector list>) selectors.
2143    nth_of_mapped_ids: &'a mut PrecomputedHashSet<Atom>,
2144
2145    /// The filter with the local names of attributes there are selectors for.
2146    attribute_dependencies: &'a mut PrecomputedHashSet<LocalName>,
2147
2148    /// The filter with the classes getting referenced from the selector list of
2149    /// :nth-child(... of <selector list>) selectors.
2150    nth_of_class_dependencies: &'a mut PrecomputedHashSet<Atom>,
2151
2152    /// The filter with the local names of attributes there are selectors for
2153    /// within the selector list of :nth-child(... of <selector list>)
2154    /// selectors.
2155    nth_of_attribute_dependencies: &'a mut PrecomputedHashSet<LocalName>,
2156
2157    /// The filter with the local names of custom states in selectors for
2158    /// within the selector list of :nth-child(... of <selector list>)
2159    /// selectors.
2160    nth_of_custom_state_dependencies: &'a mut PrecomputedHashSet<AtomIdent>,
2161
2162    /// All the states selectors in the page reference.
2163    state_dependencies: &'a mut ElementState,
2164
2165    /// All the state selectors in the page reference within the selector list
2166    /// of :nth-child(... of <selector list>) selectors.
2167    nth_of_state_dependencies: &'a mut ElementState,
2168
2169    /// All the document states selectors in the page reference.
2170    document_state_dependencies: &'a mut DocumentState,
2171}
2172
2173fn component_needs_revalidation(
2174    c: &Component<SelectorImpl>,
2175    passed_rightmost_selector: bool,
2176) -> bool {
2177    match *c {
2178        Component::ID(_) => {
2179            // TODO(emilio): This could also check that the ID is not already in
2180            // the rule hash. In that case, we could avoid making this a
2181            // revalidation selector too.
2182            //
2183            // See https://bugzilla.mozilla.org/show_bug.cgi?id=1369611
2184            passed_rightmost_selector
2185        },
2186        Component::AttributeInNoNamespaceExists { .. }
2187        | Component::AttributeInNoNamespace { .. }
2188        | Component::AttributeOther(_)
2189        | Component::Empty
2190        | Component::Nth(_)
2191        | Component::NthOf(_)
2192        | Component::Has(_) => true,
2193        Component::NonTSPseudoClass(ref p) => p.needs_cache_revalidation(),
2194        _ => false,
2195    }
2196}
2197
2198impl<'a> StylistSelectorVisitor<'a> {
2199    fn visit_nested_selector(
2200        &mut self,
2201        in_selector_list_of: SelectorListKind,
2202        selector: &Selector<SelectorImpl>,
2203    ) {
2204        let old_passed_rightmost_selector = self.passed_rightmost_selector;
2205        let old_in_selector_list_of = self.in_selector_list_of;
2206
2207        self.passed_rightmost_selector = false;
2208        self.in_selector_list_of = in_selector_list_of;
2209        let _ret = selector.visit(self);
2210        debug_assert!(_ret, "We never return false");
2211
2212        self.passed_rightmost_selector = old_passed_rightmost_selector;
2213        self.in_selector_list_of = old_in_selector_list_of;
2214    }
2215}
2216
2217impl<'a> SelectorVisitor for StylistSelectorVisitor<'a> {
2218    type Impl = SelectorImpl;
2219
2220    fn visit_complex_selector(&mut self, combinator: Option<Combinator>) -> bool {
2221        *self.needs_revalidation =
2222            *self.needs_revalidation || combinator.map_or(false, |c| c.is_sibling());
2223
2224        // NOTE(emilio): this call happens before we visit any of the simple
2225        // selectors in the next ComplexSelector, so we can use this to skip
2226        // looking at them.
2227        self.passed_rightmost_selector = self.passed_rightmost_selector
2228            || !matches!(combinator, None | Some(Combinator::PseudoElement));
2229
2230        true
2231    }
2232
2233    fn visit_selector_list(
2234        &mut self,
2235        list_kind: SelectorListKind,
2236        list: &[Selector<Self::Impl>],
2237    ) -> bool {
2238        let in_selector_list_of = self.in_selector_list_of | list_kind;
2239        for selector in list {
2240            self.visit_nested_selector(in_selector_list_of, selector);
2241        }
2242        true
2243    }
2244
2245    fn visit_relative_selector_list(
2246        &mut self,
2247        list: &[selectors::parser::RelativeSelector<Self::Impl>],
2248    ) -> bool {
2249        let in_selector_list_of = self.in_selector_list_of | SelectorListKind::HAS;
2250        for selector in list {
2251            self.visit_nested_selector(in_selector_list_of, &selector.selector);
2252        }
2253        true
2254    }
2255
2256    fn visit_attribute_selector(
2257        &mut self,
2258        _ns: &NamespaceConstraint<&Namespace>,
2259        name: &LocalName,
2260        lower_name: &LocalName,
2261    ) -> bool {
2262        if self.in_selector_list_of.relevant_to_nth_of_dependencies() {
2263            self.nth_of_attribute_dependencies.insert(name.clone());
2264            if name != lower_name {
2265                self.nth_of_attribute_dependencies
2266                    .insert(lower_name.clone());
2267            }
2268        }
2269
2270        self.attribute_dependencies.insert(name.clone());
2271        if name != lower_name {
2272            self.attribute_dependencies.insert(lower_name.clone());
2273        }
2274
2275        true
2276    }
2277
2278    fn visit_simple_selector(&mut self, s: &Component<SelectorImpl>) -> bool {
2279        *self.needs_revalidation = *self.needs_revalidation
2280            || component_needs_revalidation(s, self.passed_rightmost_selector);
2281
2282        match *s {
2283            Component::NonTSPseudoClass(NonTSPseudoClass::CustomState(ref name)) => {
2284                // CustomStateSet is special cased as it is a functional pseudo
2285                // class with unbounded inner values. This is different to
2286                // other psuedo class like :emtpy or :dir() which can be packed
2287                // into the ElementState bitflags. For CustomState, however,
2288                // the state name should be checked for presence in the selector.
2289                if self.in_selector_list_of.relevant_to_nth_of_dependencies() {
2290                    self.nth_of_custom_state_dependencies.insert(name.0.clone());
2291                }
2292            },
2293            Component::NonTSPseudoClass(ref p) => {
2294                self.state_dependencies.insert(p.state_flag());
2295                self.document_state_dependencies
2296                    .insert(p.document_state_flag());
2297
2298                if self.in_selector_list_of.relevant_to_nth_of_dependencies() {
2299                    self.nth_of_state_dependencies.insert(p.state_flag());
2300                }
2301            },
2302            Component::ID(ref id) => {
2303                // We want to stop storing mapped ids as soon as we've moved off
2304                // the rightmost ComplexSelector that is not a pseudo-element.
2305                //
2306                // That can be detected by a visit_complex_selector call with a
2307                // combinator other than None and PseudoElement.
2308                //
2309                // Importantly, this call happens before we visit any of the
2310                // simple selectors in that ComplexSelector.
2311                //
2312                // NOTE(emilio): See the comment regarding on when this may
2313                // break in visit_complex_selector.
2314                if !self.passed_rightmost_selector {
2315                    self.mapped_ids.insert(id.0.clone());
2316                }
2317
2318                if self.in_selector_list_of.relevant_to_nth_of_dependencies() {
2319                    self.nth_of_mapped_ids.insert(id.0.clone());
2320                }
2321            },
2322            Component::Class(ref class)
2323                if self.in_selector_list_of.relevant_to_nth_of_dependencies() =>
2324            {
2325                self.nth_of_class_dependencies.insert(class.0.clone());
2326            },
2327            _ => {},
2328        }
2329
2330        true
2331    }
2332}
2333
2334/// A set of rules for element and pseudo-elements.
2335#[derive(Clone, Debug, Default, MallocSizeOf)]
2336struct GenericElementAndPseudoRules<Map> {
2337    /// Rules from stylesheets at this `CascadeData`'s origin.
2338    element_map: Map,
2339
2340    /// Rules from stylesheets at this `CascadeData`'s origin that correspond
2341    /// to a given pseudo-element.
2342    ///
2343    /// FIXME(emilio): There are a bunch of wasted entries here in practice.
2344    /// Figure out a good way to do a `PerNonAnonBox` and `PerAnonBox` (for
2345    /// `precomputed_values_for_pseudo`) without duplicating a lot of code.
2346    pseudos_map: PerPseudoElementMap<Box<Self>>,
2347}
2348
2349impl<Map: Default + MallocSizeOf> GenericElementAndPseudoRules<Map> {
2350    #[inline(always)]
2351    fn for_insertion<'a>(&mut self, pseudo_elements: &[&'a PseudoElement]) -> &mut Map {
2352        let mut current = self;
2353        for &pseudo_element in pseudo_elements {
2354            debug_assert!(
2355                !pseudo_element.is_precomputed()
2356                    && !pseudo_element.is_unknown_webkit_pseudo_element(),
2357                "Precomputed pseudos should end up in precomputed_pseudo_element_decls, \
2358                 and unknown webkit pseudos should be discarded before getting here"
2359            );
2360
2361            current = current
2362                .pseudos_map
2363                .get_or_insert_with(pseudo_element, Default::default);
2364        }
2365
2366        &mut current.element_map
2367    }
2368
2369    #[inline]
2370    fn rules(&self, pseudo_elements: &[PseudoElement]) -> Option<&Map> {
2371        let mut current = self;
2372        for pseudo in pseudo_elements {
2373            current = current.pseudos_map.get(&pseudo)?.as_ref();
2374        }
2375        Some(&current.element_map)
2376    }
2377
2378    /// Measures heap usage.
2379    #[cfg(feature = "gecko")]
2380    fn add_size_of(&self, ops: &mut MallocSizeOfOps, sizes: &mut ServoStyleSetSizes) {
2381        sizes.mElementAndPseudosMaps += self.element_map.size_of(ops);
2382
2383        for elem in self.pseudos_map.iter() {
2384            if let Some(ref elem) = *elem {
2385                sizes.mElementAndPseudosMaps += <Box<_> as MallocSizeOf>::size_of(elem, ops);
2386            }
2387        }
2388    }
2389}
2390
2391type ElementAndPseudoRules = GenericElementAndPseudoRules<SelectorMap<Rule>>;
2392type PartMap = PrecomputedHashMap<Atom, SmallVec<[Rule; 1]>>;
2393type PartElementAndPseudoRules = GenericElementAndPseudoRules<PartMap>;
2394
2395impl ElementAndPseudoRules {
2396    // TODO(emilio): Should we retain storage of these?
2397    fn clear(&mut self) {
2398        self.element_map.clear();
2399        self.pseudos_map.clear();
2400    }
2401
2402    fn shrink_if_needed(&mut self) {
2403        self.element_map.shrink_if_needed();
2404        for pseudo in self.pseudos_map.iter_mut() {
2405            if let Some(ref mut pseudo) = pseudo {
2406                pseudo.shrink_if_needed();
2407            }
2408        }
2409    }
2410}
2411
2412impl PartElementAndPseudoRules {
2413    // TODO(emilio): Should we retain storage of these?
2414    fn clear(&mut self) {
2415        self.element_map.clear();
2416        self.pseudos_map.clear();
2417    }
2418}
2419
2420/// The id of a given layer, a sequentially-increasing identifier.
2421#[derive(Clone, Copy, Debug, Eq, MallocSizeOf, PartialEq, PartialOrd, Ord)]
2422pub struct LayerId(u16);
2423
2424impl LayerId {
2425    /// The id of the root layer.
2426    pub const fn root() -> Self {
2427        Self(0)
2428    }
2429}
2430
2431#[derive(Clone, Debug, MallocSizeOf)]
2432struct CascadeLayer {
2433    id: LayerId,
2434    order: LayerOrder,
2435    children: Vec<LayerId>,
2436}
2437
2438impl CascadeLayer {
2439    const fn root() -> Self {
2440        Self {
2441            id: LayerId::root(),
2442            order: LayerOrder::root(),
2443            children: vec![],
2444        }
2445    }
2446}
2447
2448/// The id of a given container condition, a sequentially-increasing identifier
2449/// for a given style set.
2450#[derive(Clone, Copy, Debug, Eq, MallocSizeOf, PartialEq, PartialOrd, Ord)]
2451pub struct ContainerConditionId(u16);
2452
2453impl ContainerConditionId {
2454    /// A special id that represents no container rule.
2455    pub const fn none() -> Self {
2456        Self(0)
2457    }
2458}
2459
2460#[derive(Clone, Debug, MallocSizeOf)]
2461struct ContainerConditionReference {
2462    parent: ContainerConditionId,
2463    #[ignore_malloc_size_of = "Arc"]
2464    condition: Option<Arc<ContainerCondition>>,
2465}
2466
2467impl ContainerConditionReference {
2468    const fn none() -> Self {
2469        Self {
2470            parent: ContainerConditionId::none(),
2471            condition: None,
2472        }
2473    }
2474}
2475
2476/// The id of a given scope condition, a sequentially-increasing identifier
2477/// for a given style set.
2478#[derive(Clone, Copy, Debug, Eq, MallocSizeOf, PartialEq, PartialOrd, Ord)]
2479pub struct ScopeConditionId(u16);
2480
2481impl ScopeConditionId {
2482    /// A special id that represents no scope rule.
2483    pub const fn none() -> Self {
2484        Self(0)
2485    }
2486}
2487
2488#[derive(Clone, Debug, MallocSizeOf)]
2489struct ScopeConditionReference {
2490    parent: ScopeConditionId,
2491    condition: Option<ScopeBoundsWithHashes>,
2492    #[ignore_malloc_size_of = "Raw ptr behind the scenes"]
2493    implicit_scope_root: StylistImplicitScopeRoot,
2494    is_trivial: bool,
2495}
2496
2497impl ScopeConditionReference {
2498    const fn none() -> Self {
2499        Self {
2500            parent: ScopeConditionId::none(),
2501            condition: None,
2502            implicit_scope_root: StylistImplicitScopeRoot::default_const(),
2503            is_trivial: true,
2504        }
2505    }
2506}
2507
2508fn scope_bounds_is_trivial(bounds: &ScopeBoundsWithHashes) -> bool {
2509    fn scope_bound_is_trivial(bound: &Option<ScopeBoundWithHashes>, default: bool) -> bool {
2510        bound.as_ref().map_or(default, |bound| {
2511            scope_selector_list_is_trivial(&bound.selectors)
2512        })
2513    }
2514
2515    // Given an implicit scope, we are unable to tell if the cousins share the same implicit root.
2516    scope_bound_is_trivial(&bounds.start, false) && scope_bound_is_trivial(&bounds.end, true)
2517}
2518
2519struct ScopeRootCandidates {
2520    candidates: Vec<ScopeRootCandidate>,
2521    is_trivial: bool,
2522}
2523
2524impl Default for ScopeRootCandidates {
2525    fn default() -> Self {
2526        Self {
2527            candidates: vec![],
2528            is_trivial: true,
2529        }
2530    }
2531}
2532
2533impl ScopeRootCandidates {
2534    fn empty(is_trivial: bool) -> Self {
2535        Self {
2536            candidates: vec![],
2537            is_trivial,
2538        }
2539    }
2540}
2541
2542#[derive(Clone, Debug, MallocSizeOf)]
2543struct ScopeBoundWithHashes {
2544    // TODO(dshin): With replaced parent selectors, these may be unique...
2545    #[ignore_malloc_size_of = "Arc"]
2546    selectors: SelectorList<SelectorImpl>,
2547    hashes: SmallVec<[AncestorHashes; 1]>,
2548}
2549
2550impl ScopeBoundWithHashes {
2551    fn new(quirks_mode: QuirksMode, selectors: SelectorList<SelectorImpl>) -> Self {
2552        let mut hashes = SmallVec::with_capacity(selectors.len());
2553        for selector in selectors.slice() {
2554            hashes.push(AncestorHashes::new(selector, quirks_mode));
2555        }
2556        Self { selectors, hashes }
2557    }
2558}
2559
2560#[derive(Clone, Debug, MallocSizeOf)]
2561struct ScopeBoundsWithHashes {
2562    start: Option<ScopeBoundWithHashes>,
2563    end: Option<ScopeBoundWithHashes>,
2564}
2565
2566impl ScopeBoundsWithHashes {
2567    fn new(
2568        quirks_mode: QuirksMode,
2569        start: Option<SelectorList<SelectorImpl>>,
2570        end: Option<SelectorList<SelectorImpl>>,
2571    ) -> Self {
2572        Self {
2573            start: start.map(|selectors| ScopeBoundWithHashes::new(quirks_mode, selectors)),
2574            end: end.map(|selectors| ScopeBoundWithHashes::new(quirks_mode, selectors)),
2575        }
2576    }
2577
2578    fn selectors_for<'a>(
2579        bound_with_hashes: Option<&'a ScopeBoundWithHashes>,
2580    ) -> impl Iterator<Item = &'a Selector<SelectorImpl>> {
2581        bound_with_hashes
2582            .map(|b| b.selectors.slice().iter())
2583            .into_iter()
2584            .flatten()
2585    }
2586
2587    fn iter_selectors<'a>(&'a self) -> impl Iterator<Item = &'a Selector<SelectorImpl>> {
2588        let start_selectors = Self::selectors_for(self.start.as_ref());
2589        let end_selectors = Self::selectors_for(self.end.as_ref());
2590        start_selectors.chain(end_selectors)
2591    }
2592}
2593
2594/// Implicit scope root, which may or may not be cached (i.e. For shadow DOM author
2595/// styles that are cached and shared).
2596#[derive(Copy, Clone, Debug, MallocSizeOf)]
2597enum StylistImplicitScopeRoot {
2598    Normal(ImplicitScopeRoot),
2599    Cached(usize),
2600}
2601// Should be safe, only mutated through mutable methods in `Stylist`.
2602unsafe impl Sync for StylistImplicitScopeRoot {}
2603
2604impl StylistImplicitScopeRoot {
2605    const fn default_const() -> Self {
2606        // Use the "safest" fallback.
2607        Self::Normal(ImplicitScopeRoot::DocumentElement)
2608    }
2609}
2610
2611impl Default for StylistImplicitScopeRoot {
2612    fn default() -> Self {
2613        Self::default_const()
2614    }
2615}
2616
2617/// Data resulting from performing the CSS cascade that is specific to a given
2618/// origin.
2619///
2620/// FIXME(emilio): Consider renaming and splitting in `CascadeData` and
2621/// `InvalidationData`? That'd make `clear_cascade_data()` clearer.
2622#[derive(Debug, Clone, MallocSizeOf)]
2623pub struct CascadeData {
2624    /// The data coming from normal style rules that apply to elements at this
2625    /// cascade level.
2626    normal_rules: ElementAndPseudoRules,
2627
2628    /// The `:host` pseudo rules that are the rightmost selector (without
2629    /// accounting for pseudo-elements), or `:scope` rules that may match
2630    /// the featureless host.
2631    featureless_host_rules: Option<Box<ElementAndPseudoRules>>,
2632
2633    /// The data coming from ::slotted() pseudo-element rules.
2634    ///
2635    /// We need to store them separately because an element needs to match
2636    /// ::slotted() pseudo-element rules in different shadow roots.
2637    ///
2638    /// In particular, we need to go through all the style data in all the
2639    /// containing style scopes starting from the closest assigned slot.
2640    slotted_rules: Option<Box<ElementAndPseudoRules>>,
2641
2642    /// The data coming from ::part() pseudo-element rules.
2643    ///
2644    /// We need to store them separately because an element needs to match
2645    /// ::part() pseudo-element rules in different shadow roots.
2646    part_rules: Option<Box<PartElementAndPseudoRules>>,
2647
2648    /// The invalidation map for these rules.
2649    invalidation_map: InvalidationMap,
2650
2651    /// The relative selector equivalent of the invalidation map.
2652    relative_selector_invalidation_map: InvalidationMap,
2653
2654    additional_relative_selector_invalidation_map: AdditionalRelativeSelectorInvalidationMap,
2655
2656    /// The attribute local names that appear in attribute selectors.  Used
2657    /// to avoid taking element snapshots when an irrelevant attribute changes.
2658    /// (We don't bother storing the namespace, since namespaced attributes are
2659    /// rare.)
2660    attribute_dependencies: PrecomputedHashSet<LocalName>,
2661
2662    /// The classes that appear in the selector list of
2663    /// :nth-child(... of <selector list>). Used to avoid restyling siblings of
2664    /// an element when an irrelevant class changes.
2665    nth_of_class_dependencies: PrecomputedHashSet<Atom>,
2666
2667    /// The attributes that appear in the selector list of
2668    /// :nth-child(... of <selector list>). Used to avoid restyling siblings of
2669    /// an element when an irrelevant attribute changes.
2670    nth_of_attribute_dependencies: PrecomputedHashSet<LocalName>,
2671
2672    /// The custom states that appear in the selector list of
2673    /// :nth-child(... of <selector list>). Used to avoid restyling siblings of
2674    /// an element when an irrelevant custom state changes.
2675    nth_of_custom_state_dependencies: PrecomputedHashSet<AtomIdent>,
2676
2677    /// The element state bits that are relied on by selectors.  Like
2678    /// `attribute_dependencies`, this is used to avoid taking element snapshots
2679    /// when an irrelevant element state bit changes.
2680    state_dependencies: ElementState,
2681
2682    /// The element state bits that are relied on by selectors that appear in
2683    /// the selector list of :nth-child(... of <selector list>).
2684    nth_of_state_dependencies: ElementState,
2685
2686    /// The document state bits that are relied on by selectors.  This is used
2687    /// to tell whether we need to restyle the entire document when a document
2688    /// state bit changes.
2689    document_state_dependencies: DocumentState,
2690
2691    /// The ids that appear in the rightmost complex selector of selectors (and
2692    /// hence in our selector maps).  Used to determine when sharing styles is
2693    /// safe: we disallow style sharing for elements whose id matches this
2694    /// filter, and hence might be in one of our selector maps.
2695    mapped_ids: PrecomputedHashSet<Atom>,
2696
2697    /// The IDs that appear in the selector list of
2698    /// :nth-child(... of <selector list>). Used to avoid restyling siblings
2699    /// of an element when an irrelevant ID changes.
2700    nth_of_mapped_ids: PrecomputedHashSet<Atom>,
2701
2702    /// Selectors that require explicit cache revalidation (i.e. which depend
2703    /// on state that is not otherwise visible to the cache, like attributes or
2704    /// tree-structural state like child index and pseudos).
2705    #[ignore_malloc_size_of = "Arc"]
2706    selectors_for_cache_revalidation: SelectorMap<RevalidationSelectorAndHashes>,
2707
2708    /// A map with all the animations at this `CascadeData`'s origin, indexed
2709    /// by name.
2710    animations: LayerOrderedMap<KeyframesAnimation>,
2711
2712    /// A map with all the layer-ordered registrations from style at this `CascadeData`'s origin,
2713    /// indexed by name.
2714    #[ignore_malloc_size_of = "Arc"]
2715    custom_property_registrations: LayerOrderedMap<Arc<PropertyRegistration>>,
2716
2717    /// A map from cascade layer name to layer order.
2718    layer_id: FxHashMap<LayerName, LayerId>,
2719
2720    /// The list of cascade layers, indexed by their layer id.
2721    layers: SmallVec<[CascadeLayer; 1]>,
2722
2723    /// The list of container conditions, indexed by their id.
2724    container_conditions: SmallVec<[ContainerConditionReference; 1]>,
2725
2726    /// The list of scope conditions, indexed by their id.
2727    scope_conditions: SmallVec<[ScopeConditionReference; 1]>,
2728
2729    /// Map of unique selectors on scope start selectors' subjects.
2730    scope_subject_map: ScopeSubjectMap,
2731
2732    /// Effective media query results cached from the last rebuild.
2733    effective_media_query_results: EffectiveMediaQueryResults,
2734
2735    /// Extra data, like different kinds of rules, etc.
2736    extra_data: ExtraStyleData,
2737
2738    /// A monotonically increasing counter to represent the order on which a
2739    /// style rule appears in a stylesheet, needed to sort them by source order.
2740    rules_source_order: u32,
2741
2742    /// The total number of selectors.
2743    num_selectors: usize,
2744
2745    /// The total number of declarations.
2746    num_declarations: usize,
2747}
2748
2749lazy_static! {
2750    static ref IMPLICIT_SCOPE: SelectorList<SelectorImpl> = {
2751        // Implicit scope, as per https://github.com/w3c/csswg-drafts/issues/10196
2752        // Also, `&` is `:where(:scope)`, as per https://github.com/w3c/csswg-drafts/issues/9740
2753        // ``:where(:scope)` effectively behaves the same as the implicit scope.
2754        let list = SelectorList::implicit_scope();
2755        list.mark_as_intentionally_leaked();
2756        list
2757    };
2758}
2759
2760fn scope_start_matches_shadow_host(start: &SelectorList<SelectorImpl>) -> bool {
2761    // TODO(emilio): Should we carry a MatchesFeaturelessHost rather than a bool around?
2762    // Pre-existing behavior with multiple selectors matches this tho.
2763    start
2764        .slice()
2765        .iter()
2766        .any(|s| s.matches_featureless_host(true).may_match())
2767}
2768
2769impl CascadeData {
2770    /// Creates an empty `CascadeData`.
2771    pub fn new() -> Self {
2772        Self {
2773            normal_rules: ElementAndPseudoRules::default(),
2774            featureless_host_rules: None,
2775            slotted_rules: None,
2776            part_rules: None,
2777            invalidation_map: InvalidationMap::new(),
2778            relative_selector_invalidation_map: InvalidationMap::new(),
2779            additional_relative_selector_invalidation_map:
2780                AdditionalRelativeSelectorInvalidationMap::new(),
2781            nth_of_mapped_ids: PrecomputedHashSet::default(),
2782            nth_of_class_dependencies: PrecomputedHashSet::default(),
2783            nth_of_attribute_dependencies: PrecomputedHashSet::default(),
2784            nth_of_custom_state_dependencies: PrecomputedHashSet::default(),
2785            nth_of_state_dependencies: ElementState::empty(),
2786            attribute_dependencies: PrecomputedHashSet::default(),
2787            state_dependencies: ElementState::empty(),
2788            document_state_dependencies: DocumentState::empty(),
2789            mapped_ids: PrecomputedHashSet::default(),
2790            selectors_for_cache_revalidation: SelectorMap::new(),
2791            animations: Default::default(),
2792            custom_property_registrations: Default::default(),
2793            layer_id: Default::default(),
2794            layers: smallvec::smallvec![CascadeLayer::root()],
2795            container_conditions: smallvec::smallvec![ContainerConditionReference::none()],
2796            scope_conditions: smallvec::smallvec![ScopeConditionReference::none()],
2797            scope_subject_map: Default::default(),
2798            extra_data: ExtraStyleData::default(),
2799            effective_media_query_results: EffectiveMediaQueryResults::new(),
2800            rules_source_order: 0,
2801            num_selectors: 0,
2802            num_declarations: 0,
2803        }
2804    }
2805
2806    /// Rebuild the cascade data from a given SheetCollection, incrementally if
2807    /// possible.
2808    pub fn rebuild<'a, S>(
2809        &mut self,
2810        device: &Device,
2811        quirks_mode: QuirksMode,
2812        collection: SheetCollectionFlusher<S>,
2813        guard: &SharedRwLockReadGuard,
2814    ) -> Result<(), AllocErr>
2815    where
2816        S: StylesheetInDocument + PartialEq + 'static,
2817    {
2818        if !collection.dirty() {
2819            return Ok(());
2820        }
2821
2822        let validity = collection.data_validity();
2823
2824        match validity {
2825            DataValidity::Valid => {},
2826            DataValidity::CascadeInvalid => self.clear_cascade_data(),
2827            DataValidity::FullyInvalid => self.clear(),
2828        }
2829
2830        let mut result = Ok(());
2831
2832        collection.each(|index, stylesheet, rebuild_kind| {
2833            result = self.add_stylesheet(
2834                device,
2835                quirks_mode,
2836                stylesheet,
2837                index,
2838                guard,
2839                rebuild_kind,
2840                /* precomputed_pseudo_element_decls = */ None,
2841            );
2842            result.is_ok()
2843        });
2844
2845        self.did_finish_rebuild();
2846
2847        result
2848    }
2849
2850    /// Returns the invalidation map.
2851    pub fn invalidation_map(&self) -> &InvalidationMap {
2852        &self.invalidation_map
2853    }
2854
2855    /// Returns the relative selector invalidation map.
2856    pub fn relative_selector_invalidation_map(&self) -> &InvalidationMap {
2857        &self.relative_selector_invalidation_map
2858    }
2859
2860    /// Returns the relative selector invalidation map data.
2861    pub fn relative_invalidation_map_attributes(
2862        &self,
2863    ) -> &AdditionalRelativeSelectorInvalidationMap {
2864        &self.additional_relative_selector_invalidation_map
2865    }
2866
2867    /// Returns whether the given ElementState bit is relied upon by a selector
2868    /// of some rule.
2869    #[inline]
2870    pub fn has_state_dependency(&self, state: ElementState) -> bool {
2871        self.state_dependencies.intersects(state)
2872    }
2873
2874    /// Returns whether the given Custom State is relied upon by a selector
2875    /// of some rule in the selector list of :nth-child(... of <selector list>).
2876    #[inline]
2877    pub fn has_nth_of_custom_state_dependency(&self, state: &AtomIdent) -> bool {
2878        self.nth_of_custom_state_dependencies.contains(state)
2879    }
2880
2881    /// Returns whether the given ElementState bit is relied upon by a selector
2882    /// of some rule in the selector list of :nth-child(... of <selector list>).
2883    #[inline]
2884    pub fn has_nth_of_state_dependency(&self, state: ElementState) -> bool {
2885        self.nth_of_state_dependencies.intersects(state)
2886    }
2887
2888    /// Returns whether the given attribute might appear in an attribute
2889    /// selector of some rule.
2890    #[inline]
2891    pub fn might_have_attribute_dependency(&self, local_name: &LocalName) -> bool {
2892        self.attribute_dependencies.contains(local_name)
2893    }
2894
2895    /// Returns whether the given ID might appear in an ID selector in the
2896    /// selector list of :nth-child(... of <selector list>).
2897    #[inline]
2898    pub fn might_have_nth_of_id_dependency(&self, id: &Atom) -> bool {
2899        self.nth_of_mapped_ids.contains(id)
2900    }
2901
2902    /// Returns whether the given class might appear in a class selector in the
2903    /// selector list of :nth-child(... of <selector list>).
2904    #[inline]
2905    pub fn might_have_nth_of_class_dependency(&self, class: &Atom) -> bool {
2906        self.nth_of_class_dependencies.contains(class)
2907    }
2908
2909    /// Returns whether the given attribute might appear in an attribute
2910    /// selector in the selector list of :nth-child(... of <selector list>).
2911    #[inline]
2912    pub fn might_have_nth_of_attribute_dependency(&self, local_name: &LocalName) -> bool {
2913        self.nth_of_attribute_dependencies.contains(local_name)
2914    }
2915
2916    /// Returns the normal rule map for a given pseudo-element.
2917    #[inline]
2918    pub fn normal_rules(&self, pseudo_elements: &[PseudoElement]) -> Option<&SelectorMap<Rule>> {
2919        self.normal_rules.rules(pseudo_elements)
2920    }
2921
2922    /// Returns the featureless pseudo rule map for a given pseudo-element.
2923    #[inline]
2924    pub fn featureless_host_rules(
2925        &self,
2926        pseudo_elements: &[PseudoElement],
2927    ) -> Option<&SelectorMap<Rule>> {
2928        self.featureless_host_rules
2929            .as_ref()
2930            .and_then(|d| d.rules(pseudo_elements))
2931    }
2932
2933    /// Whether there's any featureless rule that could match in this scope.
2934    pub fn any_featureless_host_rules(&self) -> bool {
2935        self.featureless_host_rules.is_some()
2936    }
2937
2938    /// Returns the slotted rule map for a given pseudo-element.
2939    #[inline]
2940    pub fn slotted_rules(&self, pseudo_elements: &[PseudoElement]) -> Option<&SelectorMap<Rule>> {
2941        self.slotted_rules
2942            .as_ref()
2943            .and_then(|d| d.rules(pseudo_elements))
2944    }
2945
2946    /// Whether there's any ::slotted rule that could match in this scope.
2947    pub fn any_slotted_rule(&self) -> bool {
2948        self.slotted_rules.is_some()
2949    }
2950
2951    /// Returns the parts rule map for a given pseudo-element.
2952    #[inline]
2953    pub fn part_rules(&self, pseudo_elements: &[PseudoElement]) -> Option<&PartMap> {
2954        self.part_rules
2955            .as_ref()
2956            .and_then(|d| d.rules(pseudo_elements))
2957    }
2958
2959    /// Whether there's any ::part rule that could match in this scope.
2960    pub fn any_part_rule(&self) -> bool {
2961        self.part_rules.is_some()
2962    }
2963
2964    #[inline]
2965    fn layer_order_for(&self, id: LayerId) -> LayerOrder {
2966        self.layers[id.0 as usize].order
2967    }
2968
2969    pub(crate) fn container_condition_matches<E>(
2970        &self,
2971        mut id: ContainerConditionId,
2972        stylist: &Stylist,
2973        element: E,
2974        context: &mut MatchingContext<E::Impl>,
2975    ) -> bool
2976    where
2977        E: TElement,
2978    {
2979        loop {
2980            let condition_ref = &self.container_conditions[id.0 as usize];
2981            let condition = match condition_ref.condition {
2982                None => return true,
2983                Some(ref c) => c,
2984            };
2985            let matches = condition
2986                .matches(
2987                    stylist,
2988                    element,
2989                    context.extra_data.originating_element_style,
2990                    &mut context.extra_data.cascade_input_flags,
2991                )
2992                .to_bool(/* unknown = */ false);
2993            if !matches {
2994                return false;
2995            }
2996            id = condition_ref.parent;
2997        }
2998    }
2999
3000    pub(crate) fn find_scope_proximity_if_matching<E: TElement>(
3001        &self,
3002        rule: &Rule,
3003        stylist: &Stylist,
3004        element: E,
3005        context: &mut MatchingContext<E::Impl>,
3006    ) -> ScopeProximity {
3007        context
3008            .extra_data
3009            .cascade_input_flags
3010            .insert(ComputedValueFlags::CONSIDERED_NONTRIVIAL_SCOPED_STYLE);
3011
3012        // Whether the scope root matches a shadow host mostly olny depends on scope-intrinsic
3013        // parameters (i.e. bounds/implicit scope) - except for the use of `::parts`, where
3014        // matching crosses the shadow boundary.
3015        let result = self.scope_condition_matches(
3016            rule.scope_condition_id,
3017            stylist,
3018            element,
3019            rule.selector.is_part(),
3020            context,
3021        );
3022        for candidate in result.candidates {
3023            if context.nest_for_scope(Some(candidate.root), |context| {
3024                matches_selector(&rule.selector, 0, Some(&rule.hashes), &element, context)
3025            }) {
3026                return candidate.proximity;
3027            }
3028        }
3029        ScopeProximity::infinity()
3030    }
3031
3032    fn scope_condition_matches<E>(
3033        &self,
3034        id: ScopeConditionId,
3035        stylist: &Stylist,
3036        element: E,
3037        override_matches_shadow_host_for_part: bool,
3038        context: &mut MatchingContext<E::Impl>,
3039    ) -> ScopeRootCandidates
3040    where
3041        E: TElement,
3042    {
3043        let condition_ref = &self.scope_conditions[id.0 as usize];
3044        let bounds = match condition_ref.condition {
3045            None => return ScopeRootCandidates::default(),
3046            Some(ref c) => c,
3047        };
3048        // Make sure the parent scopes ara evaluated first. This runs a bit counter to normal
3049        // selector matching where rightmost selectors match first. However, this avoids having
3050        // to traverse through descendants (i.e. Avoids tree traversal vs linear traversal).
3051        let outer_result = self.scope_condition_matches(
3052            condition_ref.parent,
3053            stylist,
3054            element,
3055            override_matches_shadow_host_for_part,
3056            context,
3057        );
3058
3059        let is_trivial = condition_ref.is_trivial && outer_result.is_trivial;
3060        let is_outermost_scope = condition_ref.parent == ScopeConditionId::none();
3061        if !is_outermost_scope && outer_result.candidates.is_empty() {
3062            return ScopeRootCandidates::empty(is_trivial);
3063        }
3064
3065        let (root_target, matches_shadow_host) = if let Some(start) = bounds.start.as_ref() {
3066            if let Some(filter) = context.bloom_filter {
3067                // Use the bloom filter here. If our ancestors do not have the right hashes,
3068                // there's no point in traversing up. Besides, the filter is built for this depth,
3069                // so the filter contains more data than it should, the further we go up the ancestor
3070                // chain. It wouldn't generate wrong results, but makes the traversal even more pointless.
3071                if !start
3072                    .hashes
3073                    .iter()
3074                    .any(|entry| selector_may_match(entry, filter))
3075                {
3076                    return ScopeRootCandidates::empty(is_trivial);
3077                }
3078            }
3079            (
3080                ScopeTarget::Selector(&start.selectors),
3081                scope_start_matches_shadow_host(&start.selectors),
3082            )
3083        } else {
3084            let implicit_root = condition_ref.implicit_scope_root;
3085            match implicit_root {
3086                StylistImplicitScopeRoot::Normal(r) => (
3087                    ScopeTarget::Implicit(r.element(context.current_host.clone())),
3088                    r.matches_shadow_host(),
3089                ),
3090                StylistImplicitScopeRoot::Cached(index) => {
3091                    let host = context
3092                        .current_host
3093                        .expect("Cached implicit scope for light DOM implicit scope");
3094                    match E::implicit_scope_for_sheet_in_shadow_root(host, index) {
3095                        None => return ScopeRootCandidates::empty(is_trivial),
3096                        Some(root) => (
3097                            ScopeTarget::Implicit(root.element(context.current_host.clone())),
3098                            root.matches_shadow_host(),
3099                        ),
3100                    }
3101                },
3102            }
3103        };
3104        // For `::part`, we need to be able to reach the outer tree. Parts without the corresponding
3105        // `exportparts` attribute will be rejected at the selector matching time.
3106        let matches_shadow_host = override_matches_shadow_host_for_part || matches_shadow_host;
3107
3108        let potential_scope_roots = if is_outermost_scope {
3109            collect_scope_roots(
3110                element,
3111                None,
3112                context,
3113                &root_target,
3114                matches_shadow_host,
3115                &self.scope_subject_map,
3116            )
3117        } else {
3118            let mut result = vec![];
3119            for activation in outer_result.candidates {
3120                let mut this_result = collect_scope_roots(
3121                    element,
3122                    Some(activation.root),
3123                    context,
3124                    &root_target,
3125                    matches_shadow_host,
3126                    &self.scope_subject_map,
3127                );
3128                result.append(&mut this_result);
3129            }
3130            result
3131        };
3132
3133        if potential_scope_roots.is_empty() {
3134            return ScopeRootCandidates::empty(is_trivial);
3135        }
3136
3137        let candidates =
3138            if let Some(end) = bounds.end.as_ref() {
3139                let mut result = vec![];
3140                // If any scope-end selector matches, we're not in scope.
3141                for scope_root in potential_scope_roots {
3142                    if end.selectors.slice().iter().zip(end.hashes.iter()).all(
3143                        |(selector, hashes)| {
3144                            // Like checking for scope-start, use the bloom filter here.
3145                            if let Some(filter) = context.bloom_filter {
3146                                if !selector_may_match(hashes, filter) {
3147                                    // Selector this hash belongs to won't cause us to be out of this scope.
3148                                    return true;
3149                                }
3150                            }
3151
3152                            !element_is_outside_of_scope(
3153                                selector,
3154                                element,
3155                                scope_root.root,
3156                                context,
3157                                matches_shadow_host,
3158                            )
3159                        },
3160                    ) {
3161                        result.push(scope_root);
3162                    }
3163                }
3164                result
3165            } else {
3166                potential_scope_roots
3167            };
3168
3169        ScopeRootCandidates {
3170            candidates,
3171            is_trivial,
3172        }
3173    }
3174
3175    fn did_finish_rebuild(&mut self) {
3176        self.shrink_maps_if_needed();
3177        self.compute_layer_order();
3178    }
3179
3180    fn shrink_maps_if_needed(&mut self) {
3181        self.normal_rules.shrink_if_needed();
3182        if let Some(ref mut host_rules) = self.featureless_host_rules {
3183            host_rules.shrink_if_needed();
3184        }
3185        if let Some(ref mut slotted_rules) = self.slotted_rules {
3186            slotted_rules.shrink_if_needed();
3187        }
3188        self.animations.shrink_if_needed();
3189        self.custom_property_registrations.shrink_if_needed();
3190        self.invalidation_map.shrink_if_needed();
3191        self.relative_selector_invalidation_map.shrink_if_needed();
3192        self.additional_relative_selector_invalidation_map
3193            .shrink_if_needed();
3194        self.attribute_dependencies.shrink_if_needed();
3195        self.nth_of_attribute_dependencies.shrink_if_needed();
3196        self.nth_of_custom_state_dependencies.shrink_if_needed();
3197        self.nth_of_class_dependencies.shrink_if_needed();
3198        self.nth_of_mapped_ids.shrink_if_needed();
3199        self.mapped_ids.shrink_if_needed();
3200        self.layer_id.shrink_if_needed();
3201        self.selectors_for_cache_revalidation.shrink_if_needed();
3202        self.scope_subject_map.shrink_if_needed();
3203    }
3204
3205    fn compute_layer_order(&mut self) {
3206        debug_assert_ne!(
3207            self.layers.len(),
3208            0,
3209            "There should be at least the root layer!"
3210        );
3211        if self.layers.len() == 1 {
3212            return; // Nothing to do
3213        }
3214        let (first, remaining) = self.layers.split_at_mut(1);
3215        let root = &mut first[0];
3216        let mut order = LayerOrder::first();
3217        compute_layer_order_for_subtree(root, remaining, &mut order);
3218
3219        // NOTE(emilio): This is a bit trickier than it should to avoid having
3220        // to clone() around layer indices.
3221        fn compute_layer_order_for_subtree(
3222            parent: &mut CascadeLayer,
3223            remaining_layers: &mut [CascadeLayer],
3224            order: &mut LayerOrder,
3225        ) {
3226            for child in parent.children.iter() {
3227                debug_assert!(
3228                    parent.id < *child,
3229                    "Children are always registered after parents"
3230                );
3231                let child_index = (child.0 - parent.id.0 - 1) as usize;
3232                let (first, remaining) = remaining_layers.split_at_mut(child_index + 1);
3233                let child = &mut first[child_index];
3234                compute_layer_order_for_subtree(child, remaining, order);
3235            }
3236
3237            if parent.id != LayerId::root() {
3238                parent.order = *order;
3239                order.inc();
3240            }
3241        }
3242        #[cfg(feature = "gecko")]
3243        self.extra_data.sort_by_layer(&self.layers);
3244        self.animations
3245            .sort_with(&self.layers, compare_keyframes_in_same_layer);
3246        self.custom_property_registrations.sort(&self.layers)
3247    }
3248
3249    /// Collects all the applicable media query results into `results`.
3250    ///
3251    /// This duplicates part of the logic in `add_stylesheet`, which is
3252    /// a bit unfortunate.
3253    ///
3254    /// FIXME(emilio): With a bit of smartness in
3255    /// `media_feature_affected_matches`, we could convert
3256    /// `EffectiveMediaQueryResults` into a vector without too much effort.
3257    fn collect_applicable_media_query_results_into<S>(
3258        device: &Device,
3259        stylesheet: &S,
3260        guard: &SharedRwLockReadGuard,
3261        results: &mut Vec<MediaListKey>,
3262        contents_list: &mut StyleSheetContentList,
3263    ) where
3264        S: StylesheetInDocument + 'static,
3265    {
3266        if !stylesheet.enabled() || !stylesheet.is_effective_for_device(device, guard) {
3267            return;
3268        }
3269
3270        debug!(" + {:?}", stylesheet);
3271        let contents = stylesheet.contents();
3272        results.push(contents.to_media_list_key());
3273
3274        // Safety: StyleSheetContents are reference-counted with Arc.
3275        contents_list.push(StylesheetContentsPtr(unsafe {
3276            Arc::from_raw_addrefed(contents)
3277        }));
3278
3279        for rule in stylesheet.effective_rules(device, guard) {
3280            match *rule {
3281                CssRule::Import(ref lock) => {
3282                    let import_rule = lock.read_with(guard);
3283                    debug!(" + {:?}", import_rule.stylesheet.media(guard));
3284                    results.push(import_rule.to_media_list_key());
3285                },
3286                CssRule::Media(ref media_rule) => {
3287                    debug!(" + {:?}", media_rule.media_queries.read_with(guard));
3288                    results.push(media_rule.to_media_list_key());
3289                },
3290                _ => {},
3291            }
3292        }
3293    }
3294
3295    fn add_styles(
3296        &mut self,
3297        selectors: &SelectorList<SelectorImpl>,
3298        declarations: &Arc<Locked<PropertyDeclarationBlock>>,
3299        ancestor_selectors: Option<&SelectorList<SelectorImpl>>,
3300        containing_rule_state: &ContainingRuleState,
3301        mut replaced_selectors: Option<&mut ReplacedSelectors>,
3302        guard: &SharedRwLockReadGuard,
3303        rebuild_kind: SheetRebuildKind,
3304        mut precomputed_pseudo_element_decls: Option<&mut PrecomputedPseudoElementDeclarations>,
3305        quirks_mode: QuirksMode,
3306    ) -> Result<(), AllocErr> {
3307        self.num_declarations += declarations.read_with(guard).len();
3308        for selector in selectors.slice() {
3309            self.num_selectors += 1;
3310
3311            let pseudo_elements = selector.pseudo_elements();
3312            let inner_pseudo_element = pseudo_elements.get(0);
3313            if let Some(pseudo) = inner_pseudo_element {
3314                if pseudo.is_precomputed() {
3315                    debug_assert!(selector.is_universal());
3316                    debug_assert!(ancestor_selectors.is_none());
3317                    debug_assert_eq!(containing_rule_state.layer_id, LayerId::root());
3318                    // Because we precompute pseudos, we cannot possibly calculate scope proximity.
3319                    debug_assert_eq!(
3320                        containing_rule_state.scope_condition_id,
3321                        ScopeConditionId::none()
3322                    );
3323                    precomputed_pseudo_element_decls
3324                        .as_mut()
3325                        .expect("Expected precomputed declarations for the UA level")
3326                        .get_or_insert_with(pseudo, Vec::new)
3327                        .push(ApplicableDeclarationBlock::new(
3328                            StyleSource::from_declarations(declarations.clone()),
3329                            self.rules_source_order,
3330                            CascadeLevel::UANormal,
3331                            selector.specificity(),
3332                            LayerOrder::root(),
3333                            ScopeProximity::infinity(),
3334                        ));
3335                    continue;
3336                }
3337                if pseudo_elements
3338                    .iter()
3339                    .any(|p| p.is_unknown_webkit_pseudo_element())
3340                {
3341                    continue;
3342                }
3343            }
3344
3345            debug_assert!(!pseudo_elements
3346                .iter()
3347                .any(|p| p.is_precomputed() || p.is_unknown_webkit_pseudo_element()));
3348
3349            let selector = match ancestor_selectors {
3350                Some(ref s) => selector.replace_parent_selector(&s),
3351                None => selector.clone(),
3352            };
3353
3354            let hashes = AncestorHashes::new(&selector, quirks_mode);
3355
3356            let rule = Rule::new(
3357                selector,
3358                hashes,
3359                StyleSource::from_declarations(declarations.clone()),
3360                self.rules_source_order,
3361                containing_rule_state.layer_id,
3362                containing_rule_state.container_condition_id,
3363                containing_rule_state.in_starting_style,
3364                containing_rule_state.scope_condition_id,
3365            );
3366
3367            if let Some(ref mut replaced_selectors) = replaced_selectors {
3368                replaced_selectors.push(rule.selector.clone())
3369            }
3370
3371            if rebuild_kind.should_rebuild_invalidation() {
3372                let mut scope_idx = containing_rule_state.scope_condition_id;
3373                let mut inner_scope_dependencies: Option<ThinArc<(), Dependency>> = None;
3374                while scope_idx != ScopeConditionId::none() {
3375                    let cur_scope = &self.scope_conditions[scope_idx.0 as usize];
3376
3377                    if let Some(cond) = cur_scope.condition.as_ref() {
3378                        let mut dependency_vector: Vec<Dependency> = Vec::new();
3379
3380                        for s in cond.iter_selectors() {
3381                            let mut new_inner_dependencies = note_selector_for_invalidation(
3382                                &s.clone(),
3383                                quirks_mode,
3384                                &mut self.invalidation_map,
3385                                &mut self.relative_selector_invalidation_map,
3386                                &mut self.additional_relative_selector_invalidation_map,
3387                                inner_scope_dependencies.as_ref(),
3388                            )?;
3389
3390                            new_inner_dependencies.as_mut().map(|dep| {
3391                                dependency_vector.append(dep);
3392                            });
3393                        }
3394                        inner_scope_dependencies = Some(ThinArc::from_header_and_iter(
3395                            (),
3396                            dependency_vector.into_iter(),
3397                        ));
3398                    }
3399                    scope_idx = cur_scope.parent;
3400                }
3401
3402                note_selector_for_invalidation(
3403                    &rule.selector,
3404                    quirks_mode,
3405                    &mut self.invalidation_map,
3406                    &mut self.relative_selector_invalidation_map,
3407                    &mut self.additional_relative_selector_invalidation_map,
3408                    None,
3409                )?;
3410                let mut needs_revalidation = false;
3411                let mut visitor = StylistSelectorVisitor {
3412                    needs_revalidation: &mut needs_revalidation,
3413                    passed_rightmost_selector: false,
3414                    in_selector_list_of: SelectorListKind::default(),
3415                    mapped_ids: &mut self.mapped_ids,
3416                    nth_of_mapped_ids: &mut self.nth_of_mapped_ids,
3417                    attribute_dependencies: &mut self.attribute_dependencies,
3418                    nth_of_class_dependencies: &mut self.nth_of_class_dependencies,
3419                    nth_of_attribute_dependencies: &mut self.nth_of_attribute_dependencies,
3420                    nth_of_custom_state_dependencies: &mut self.nth_of_custom_state_dependencies,
3421                    state_dependencies: &mut self.state_dependencies,
3422                    nth_of_state_dependencies: &mut self.nth_of_state_dependencies,
3423                    document_state_dependencies: &mut self.document_state_dependencies,
3424                };
3425                rule.selector.visit(&mut visitor);
3426
3427                if needs_revalidation {
3428                    self.selectors_for_cache_revalidation.insert(
3429                        RevalidationSelectorAndHashes::new(
3430                            rule.selector.clone(),
3431                            rule.hashes.clone(),
3432                        ),
3433                        quirks_mode,
3434                    )?;
3435                }
3436            }
3437
3438            // Part is special, since given it doesn't have any
3439            // selectors inside, it's not worth using a whole
3440            // SelectorMap for it.
3441            if let Some(parts) = rule.selector.parts() {
3442                // ::part() has all semantics, so we just need to
3443                // put any of them in the selector map.
3444                //
3445                // We choose the last one quite arbitrarily,
3446                // expecting it's slightly more likely to be more
3447                // specific.
3448                let map = self
3449                    .part_rules
3450                    .get_or_insert_with(|| Box::new(Default::default()))
3451                    .for_insertion(&pseudo_elements);
3452                map.try_reserve(1)?;
3453                let vec = map.entry(parts.last().unwrap().clone().0).or_default();
3454                vec.try_reserve(1)?;
3455                vec.push(rule);
3456            } else {
3457                let scope_matches_shadow_host =
3458                    containing_rule_state.scope_matches_shadow_host == ScopeMatchesShadowHost::Yes;
3459                let matches_featureless_host_only = match rule
3460                    .selector
3461                    .matches_featureless_host(scope_matches_shadow_host)
3462                {
3463                    MatchesFeaturelessHost::Only => true,
3464                    MatchesFeaturelessHost::Yes => {
3465                        // We need to insert this in featureless_host_rules but also normal_rules.
3466                        self.featureless_host_rules
3467                            .get_or_insert_with(|| Box::new(Default::default()))
3468                            .for_insertion(&pseudo_elements)
3469                            .insert(rule.clone(), quirks_mode)?;
3470                        false
3471                    },
3472                    MatchesFeaturelessHost::Never => false,
3473                };
3474
3475                // NOTE(emilio): It's fine to look at :host and then at
3476                // ::slotted(..), since :host::slotted(..) could never
3477                // possibly match, as <slot> is not a valid shadow host.
3478                // :scope may match featureless shadow host if the scope
3479                // root is the shadow root.
3480                // See https://github.com/w3c/csswg-drafts/issues/9025
3481                let rules = if matches_featureless_host_only {
3482                    self.featureless_host_rules
3483                        .get_or_insert_with(|| Box::new(Default::default()))
3484                } else if rule.selector.is_slotted() {
3485                    self.slotted_rules
3486                        .get_or_insert_with(|| Box::new(Default::default()))
3487                } else {
3488                    &mut self.normal_rules
3489                }
3490                .for_insertion(&pseudo_elements);
3491                rules.insert(rule, quirks_mode)?;
3492            }
3493        }
3494        self.rules_source_order += 1;
3495        Ok(())
3496    }
3497
3498    fn add_rule_list<S>(
3499        &mut self,
3500        rules: std::slice::Iter<CssRule>,
3501        device: &Device,
3502        quirks_mode: QuirksMode,
3503        stylesheet: &S,
3504        sheet_index: usize,
3505        guard: &SharedRwLockReadGuard,
3506        rebuild_kind: SheetRebuildKind,
3507        containing_rule_state: &mut ContainingRuleState,
3508        mut precomputed_pseudo_element_decls: Option<&mut PrecomputedPseudoElementDeclarations>,
3509    ) -> Result<(), AllocErr>
3510    where
3511        S: StylesheetInDocument + 'static,
3512    {
3513        for rule in rules {
3514            // Handle leaf rules first, as those are by far the most common
3515            // ones, and are always effective, so we can skip some checks.
3516            let mut handled = true;
3517            let mut list_for_nested_rules = None;
3518            match *rule {
3519                CssRule::Style(ref locked) => {
3520                    let style_rule = locked.read_with(guard);
3521                    let has_nested_rules = style_rule.rules.is_some();
3522                    let mut replaced_selectors = ReplacedSelectors::new();
3523                    let ancestor_selectors = containing_rule_state.ancestor_selector_lists.last();
3524                    let collect_replaced_selectors =
3525                        has_nested_rules && ancestor_selectors.is_some();
3526                    self.add_styles(
3527                        &style_rule.selectors,
3528                        &style_rule.block,
3529                        ancestor_selectors,
3530                        &containing_rule_state,
3531                        if collect_replaced_selectors {
3532                            Some(&mut replaced_selectors)
3533                        } else {
3534                            None
3535                        },
3536                        guard,
3537                        rebuild_kind,
3538                        precomputed_pseudo_element_decls.as_deref_mut(),
3539                        quirks_mode,
3540                    )?;
3541                    if has_nested_rules {
3542                        handled = false;
3543                        list_for_nested_rules = Some(if collect_replaced_selectors {
3544                            SelectorList::from_iter(replaced_selectors.drain(..))
3545                        } else {
3546                            style_rule.selectors.clone()
3547                        });
3548                    }
3549                },
3550                CssRule::NestedDeclarations(ref rule) => {
3551                    if let Some(ref ancestor_selectors) =
3552                        containing_rule_state.ancestor_selector_lists.last()
3553                    {
3554                        let decls = &rule.read_with(guard).block;
3555                        let selectors = match containing_rule_state.nested_declarations_context {
3556                            NestedDeclarationsContext::Style => ancestor_selectors,
3557                            NestedDeclarationsContext::Scope => &*IMPLICIT_SCOPE,
3558                        };
3559                        self.add_styles(
3560                            selectors,
3561                            decls,
3562                            /* ancestor_selectors = */ None,
3563                            &containing_rule_state,
3564                            /* replaced_selectors = */ None,
3565                            guard,
3566                            // We don't need to rebuild invalidation data, since our ancestor style
3567                            // rule would've done this.
3568                            SheetRebuildKind::CascadeOnly,
3569                            precomputed_pseudo_element_decls.as_deref_mut(),
3570                            quirks_mode,
3571                        )?;
3572                    }
3573                },
3574                CssRule::Keyframes(ref keyframes_rule) => {
3575                    debug!("Found valid keyframes rule: {:?}", *keyframes_rule);
3576                    let keyframes_rule = keyframes_rule.read_with(guard);
3577                    let name = keyframes_rule.name.as_atom().clone();
3578                    let animation = KeyframesAnimation::from_keyframes(
3579                        &keyframes_rule.keyframes,
3580                        keyframes_rule.vendor_prefix.clone(),
3581                        guard,
3582                    );
3583                    self.animations.try_insert_with(
3584                        name,
3585                        animation,
3586                        containing_rule_state.layer_id,
3587                        compare_keyframes_in_same_layer,
3588                    )?;
3589                },
3590                CssRule::Property(ref registration) => {
3591                    self.custom_property_registrations.try_insert(
3592                        registration.name.0.clone(),
3593                        Arc::clone(registration),
3594                        containing_rule_state.layer_id,
3595                    )?;
3596                },
3597                #[cfg(feature = "gecko")]
3598                CssRule::FontFace(ref rule) => {
3599                    // NOTE(emilio): We don't care about container_condition_id
3600                    // because:
3601                    //
3602                    //     Global, name-defining at-rules such as @keyframes or
3603                    //     @font-face or @layer that are defined inside container
3604                    //     queries are not constrained by the container query
3605                    //     conditions.
3606                    //
3607                    // https://drafts.csswg.org/css-contain-3/#container-rule
3608                    // (Same elsewhere)
3609                    self.extra_data
3610                        .add_font_face(rule, containing_rule_state.layer_id);
3611                },
3612                #[cfg(feature = "gecko")]
3613                CssRule::FontFeatureValues(ref rule) => {
3614                    self.extra_data
3615                        .add_font_feature_values(rule, containing_rule_state.layer_id);
3616                },
3617                #[cfg(feature = "gecko")]
3618                CssRule::FontPaletteValues(ref rule) => {
3619                    self.extra_data
3620                        .add_font_palette_values(rule, containing_rule_state.layer_id);
3621                },
3622                #[cfg(feature = "gecko")]
3623                CssRule::CounterStyle(ref rule) => {
3624                    self.extra_data.add_counter_style(
3625                        guard,
3626                        rule,
3627                        containing_rule_state.layer_id,
3628                    )?;
3629                },
3630                #[cfg(feature = "gecko")]
3631                CssRule::Page(ref rule) => {
3632                    self.extra_data
3633                        .add_page(guard, rule, containing_rule_state.layer_id)?;
3634                    handled = false;
3635                },
3636                _ => {
3637                    handled = false;
3638                },
3639            }
3640
3641            if handled {
3642                // Assert that there are no children, and that the rule is
3643                // effective.
3644                if cfg!(debug_assertions) {
3645                    let mut effective = false;
3646                    let children = EffectiveRulesIterator::children(
3647                        rule,
3648                        device,
3649                        quirks_mode,
3650                        guard,
3651                        &mut effective,
3652                    );
3653                    debug_assert!(children.is_none());
3654                    debug_assert!(effective);
3655                }
3656                continue;
3657            }
3658
3659            let mut effective = false;
3660            let children =
3661                EffectiveRulesIterator::children(rule, device, quirks_mode, guard, &mut effective);
3662
3663            if !effective {
3664                continue;
3665            }
3666
3667            fn maybe_register_layer(data: &mut CascadeData, layer: &LayerName) -> LayerId {
3668                // TODO: Measure what's more common / expensive, if
3669                // layer.clone() or the double hash lookup in the insert
3670                // case.
3671                if let Some(id) = data.layer_id.get(layer) {
3672                    return *id;
3673                }
3674                let id = LayerId(data.layers.len() as u16);
3675
3676                let parent_layer_id = if layer.layer_names().len() > 1 {
3677                    let mut parent = layer.clone();
3678                    parent.0.pop();
3679
3680                    *data
3681                        .layer_id
3682                        .get_mut(&parent)
3683                        .expect("Parent layers should be registered before child layers")
3684                } else {
3685                    LayerId::root()
3686                };
3687
3688                data.layers[parent_layer_id.0 as usize].children.push(id);
3689                data.layers.push(CascadeLayer {
3690                    id,
3691                    // NOTE(emilio): Order is evaluated after rebuild in
3692                    // compute_layer_order.
3693                    order: LayerOrder::first(),
3694                    children: vec![],
3695                });
3696
3697                data.layer_id.insert(layer.clone(), id);
3698
3699                id
3700            }
3701
3702            fn maybe_register_layers(
3703                data: &mut CascadeData,
3704                name: Option<&LayerName>,
3705                containing_rule_state: &mut ContainingRuleState,
3706            ) {
3707                let anon_name;
3708                let name = match name {
3709                    Some(name) => name,
3710                    None => {
3711                        anon_name = LayerName::new_anonymous();
3712                        &anon_name
3713                    },
3714                };
3715                for name in name.layer_names() {
3716                    containing_rule_state.layer_name.0.push(name.clone());
3717                    containing_rule_state.layer_id =
3718                        maybe_register_layer(data, &containing_rule_state.layer_name);
3719                }
3720                debug_assert_ne!(containing_rule_state.layer_id, LayerId::root());
3721            }
3722
3723            let saved_containing_rule_state = containing_rule_state.save();
3724            match *rule {
3725                CssRule::Import(ref lock) => {
3726                    let import_rule = lock.read_with(guard);
3727                    if rebuild_kind.should_rebuild_invalidation() {
3728                        self.effective_media_query_results
3729                            .saw_effective(import_rule);
3730                    }
3731                    match import_rule.layer {
3732                        ImportLayer::Named(ref name) => {
3733                            maybe_register_layers(self, Some(name), containing_rule_state)
3734                        },
3735                        ImportLayer::Anonymous => {
3736                            maybe_register_layers(self, None, containing_rule_state)
3737                        },
3738                        ImportLayer::None => {},
3739                    }
3740                },
3741                CssRule::Media(ref media_rule) => {
3742                    if rebuild_kind.should_rebuild_invalidation() {
3743                        self.effective_media_query_results
3744                            .saw_effective(&**media_rule);
3745                    }
3746                },
3747                CssRule::LayerBlock(ref rule) => {
3748                    maybe_register_layers(self, rule.name.as_ref(), containing_rule_state);
3749                },
3750                CssRule::LayerStatement(ref rule) => {
3751                    for name in &*rule.names {
3752                        maybe_register_layers(self, Some(name), containing_rule_state);
3753                        // Register each layer individually.
3754                        containing_rule_state.restore(&saved_containing_rule_state);
3755                    }
3756                },
3757                CssRule::Style(..) => {
3758                    containing_rule_state.nested_declarations_context =
3759                        NestedDeclarationsContext::Style;
3760                    if let Some(s) = list_for_nested_rules {
3761                        containing_rule_state.ancestor_selector_lists.push(s);
3762                    }
3763                },
3764                CssRule::Container(ref rule) => {
3765                    let id = ContainerConditionId(self.container_conditions.len() as u16);
3766                    self.container_conditions.push(ContainerConditionReference {
3767                        parent: containing_rule_state.container_condition_id,
3768                        condition: Some(rule.condition.clone()),
3769                    });
3770                    containing_rule_state.container_condition_id = id;
3771                },
3772                CssRule::StartingStyle(..) => {
3773                    containing_rule_state.in_starting_style = true;
3774                },
3775                CssRule::Scope(ref rule) => {
3776                    containing_rule_state.nested_declarations_context =
3777                        NestedDeclarationsContext::Scope;
3778                    let id = ScopeConditionId(self.scope_conditions.len() as u16);
3779                    let mut matches_shadow_host = false;
3780                    let implicit_scope_root = if let Some(start) = rule.bounds.start.as_ref() {
3781                        matches_shadow_host = scope_start_matches_shadow_host(start);
3782                        // Would be unused, but use the default as fallback.
3783                        StylistImplicitScopeRoot::default()
3784                    } else {
3785                        // (Re)Moving stylesheets trigger a complete flush, so saving the implicit
3786                        // root here should be safe.
3787                        if let Some(root) = stylesheet.implicit_scope_root() {
3788                            matches_shadow_host = root.matches_shadow_host();
3789                            match root {
3790                                ImplicitScopeRoot::InLightTree(_)
3791                                | ImplicitScopeRoot::Constructed
3792                                | ImplicitScopeRoot::DocumentElement => {
3793                                    StylistImplicitScopeRoot::Normal(root)
3794                                },
3795                                ImplicitScopeRoot::ShadowHost(_)
3796                                | ImplicitScopeRoot::InShadowTree(_) => {
3797                                    // Style data can be shared between shadow trees, so we must
3798                                    // query the implicit root for that specific tree.
3799                                    // Shared stylesheet means shared sheet indices, so we can
3800                                    // use that to locate the implicit root.
3801                                    // Technically, this can also be applied to the light tree,
3802                                    // but that requires also knowing about what cascade level we're at.
3803                                    StylistImplicitScopeRoot::Cached(sheet_index)
3804                                },
3805                            }
3806                        } else {
3807                            // Could not find implicit scope root, but use the default as fallback.
3808                            StylistImplicitScopeRoot::default()
3809                        }
3810                    };
3811
3812                    let replaced =
3813                        {
3814                            let start = rule.bounds.start.as_ref().map(|selector| {
3815                                match containing_rule_state.ancestor_selector_lists.last() {
3816                                    Some(s) => selector.replace_parent_selector(s),
3817                                    None => selector.clone(),
3818                                }
3819                            });
3820                            let implicit_scope_selector = &*IMPLICIT_SCOPE;
3821                            let end = rule.bounds.end.as_ref().map(|selector| {
3822                                selector.replace_parent_selector(implicit_scope_selector)
3823                            });
3824                            containing_rule_state
3825                                .ancestor_selector_lists
3826                                .push(implicit_scope_selector.clone());
3827                            ScopeBoundsWithHashes::new(quirks_mode, start, end)
3828                        };
3829
3830                    if let Some(selectors) = replaced.start.as_ref() {
3831                        self.scope_subject_map
3832                            .add_bound_start(&selectors.selectors, quirks_mode);
3833                    }
3834
3835                    let is_trivial = scope_bounds_is_trivial(&replaced);
3836                    self.scope_conditions.push(ScopeConditionReference {
3837                        parent: containing_rule_state.scope_condition_id,
3838                        condition: Some(replaced),
3839                        implicit_scope_root,
3840                        is_trivial,
3841                    });
3842                    containing_rule_state
3843                        .scope_matches_shadow_host
3844                        .nest_for_scope(matches_shadow_host);
3845                    containing_rule_state.scope_condition_id = id;
3846                },
3847                // We don't care about any other rule.
3848                _ => {},
3849            }
3850
3851            if let Some(children) = children {
3852                self.add_rule_list(
3853                    children,
3854                    device,
3855                    quirks_mode,
3856                    stylesheet,
3857                    sheet_index,
3858                    guard,
3859                    rebuild_kind,
3860                    containing_rule_state,
3861                    precomputed_pseudo_element_decls.as_deref_mut(),
3862                )?;
3863            }
3864
3865            containing_rule_state.restore(&saved_containing_rule_state);
3866        }
3867
3868        Ok(())
3869    }
3870
3871    // Returns Err(..) to signify OOM
3872    fn add_stylesheet<S>(
3873        &mut self,
3874        device: &Device,
3875        quirks_mode: QuirksMode,
3876        stylesheet: &S,
3877        sheet_index: usize,
3878        guard: &SharedRwLockReadGuard,
3879        rebuild_kind: SheetRebuildKind,
3880        mut precomputed_pseudo_element_decls: Option<&mut PrecomputedPseudoElementDeclarations>,
3881    ) -> Result<(), AllocErr>
3882    where
3883        S: StylesheetInDocument + 'static,
3884    {
3885        if !stylesheet.enabled() || !stylesheet.is_effective_for_device(device, guard) {
3886            return Ok(());
3887        }
3888
3889        let contents = stylesheet.contents();
3890
3891        if rebuild_kind.should_rebuild_invalidation() {
3892            self.effective_media_query_results.saw_effective(contents);
3893        }
3894
3895        let mut state = ContainingRuleState::default();
3896        self.add_rule_list(
3897            contents.rules(guard).iter(),
3898            device,
3899            quirks_mode,
3900            stylesheet,
3901            sheet_index,
3902            guard,
3903            rebuild_kind,
3904            &mut state,
3905            precomputed_pseudo_element_decls.as_deref_mut(),
3906        )?;
3907
3908        Ok(())
3909    }
3910
3911    /// Returns whether all the media-feature affected values matched before and
3912    /// match now in the given stylesheet.
3913    pub fn media_feature_affected_matches<S>(
3914        &self,
3915        stylesheet: &S,
3916        guard: &SharedRwLockReadGuard,
3917        device: &Device,
3918        quirks_mode: QuirksMode,
3919    ) -> bool
3920    where
3921        S: StylesheetInDocument + 'static,
3922    {
3923        use crate::invalidation::media_queries::PotentiallyEffectiveMediaRules;
3924
3925        let effective_now = stylesheet.is_effective_for_device(device, guard);
3926
3927        let effective_then = self
3928            .effective_media_query_results
3929            .was_effective(stylesheet.contents());
3930
3931        if effective_now != effective_then {
3932            debug!(
3933                " > Stylesheet {:?} changed -> {}, {}",
3934                stylesheet.media(guard),
3935                effective_then,
3936                effective_now
3937            );
3938            return false;
3939        }
3940
3941        if !effective_now {
3942            return true;
3943        }
3944
3945        let mut iter = stylesheet.iter_rules::<PotentiallyEffectiveMediaRules>(device, guard);
3946
3947        while let Some(rule) = iter.next() {
3948            match *rule {
3949                CssRule::Style(..)
3950                | CssRule::NestedDeclarations(..)
3951                | CssRule::Namespace(..)
3952                | CssRule::FontFace(..)
3953                | CssRule::Container(..)
3954                | CssRule::CounterStyle(..)
3955                | CssRule::Supports(..)
3956                | CssRule::Keyframes(..)
3957                | CssRule::Margin(..)
3958                | CssRule::Page(..)
3959                | CssRule::Property(..)
3960                | CssRule::Document(..)
3961                | CssRule::LayerBlock(..)
3962                | CssRule::LayerStatement(..)
3963                | CssRule::FontPaletteValues(..)
3964                | CssRule::FontFeatureValues(..)
3965                | CssRule::Scope(..)
3966                | CssRule::StartingStyle(..)
3967                | CssRule::PositionTry(..) => {
3968                    // Not affected by device changes.
3969                    continue;
3970                },
3971                CssRule::Import(ref lock) => {
3972                    let import_rule = lock.read_with(guard);
3973                    let effective_now = match import_rule.stylesheet.media(guard) {
3974                        Some(m) => m.evaluate(device, quirks_mode),
3975                        None => true,
3976                    };
3977                    let effective_then = self
3978                        .effective_media_query_results
3979                        .was_effective(import_rule);
3980                    if effective_now != effective_then {
3981                        debug!(
3982                            " > @import rule {:?} changed {} -> {}",
3983                            import_rule.stylesheet.media(guard),
3984                            effective_then,
3985                            effective_now
3986                        );
3987                        return false;
3988                    }
3989
3990                    if !effective_now {
3991                        iter.skip_children();
3992                    }
3993                },
3994                CssRule::Media(ref media_rule) => {
3995                    let mq = media_rule.media_queries.read_with(guard);
3996                    let effective_now = mq.evaluate(device, quirks_mode);
3997                    let effective_then = self
3998                        .effective_media_query_results
3999                        .was_effective(&**media_rule);
4000
4001                    if effective_now != effective_then {
4002                        debug!(
4003                            " > @media rule {:?} changed {} -> {}",
4004                            mq, effective_then, effective_now
4005                        );
4006                        return false;
4007                    }
4008
4009                    if !effective_now {
4010                        iter.skip_children();
4011                    }
4012                },
4013            }
4014        }
4015
4016        true
4017    }
4018
4019    /// Returns the custom properties map.
4020    pub fn custom_property_registrations(&self) -> &LayerOrderedMap<Arc<PropertyRegistration>> {
4021        &self.custom_property_registrations
4022    }
4023
4024    fn revalidate_scopes<E: TElement>(
4025        &self,
4026        stylist: &Stylist,
4027        element: &E,
4028        matching_context: &mut MatchingContext<E::Impl>,
4029        result: &mut ScopeRevalidationResult,
4030    ) {
4031        // TODO(dshin): A scope block may not contain style rule for this element, but we don't keep
4032        // track of that, so we check _all_ scope conditions. It's possible for two comparable elements
4033        // to share scope & relevant styles rules, but also differ in scopes that do not contain style
4034        // rules relevant to them. So while we can be certain that an identical result share scoped styles
4035        // (Given that other sharing conditions are met), it is uncertain if elements with non-matching
4036        // results do not.
4037        for condition_id in 1..self.scope_conditions.len() {
4038            let condition = &self.scope_conditions[condition_id];
4039            let matches = if condition.is_trivial {
4040                // Just ignore this condition - for style sharing candidates, guaranteed
4041                // the same match result.
4042                continue;
4043            } else {
4044                let result = self.scope_condition_matches(
4045                    ScopeConditionId(condition_id as u16),
4046                    stylist,
4047                    *element,
4048                    // This should be ok since we aren't sharing styles across shadow boundaries.
4049                    false,
4050                    matching_context,
4051                );
4052                !result.candidates.is_empty()
4053            };
4054            result.scopes_matched.push(matches);
4055        }
4056    }
4057
4058    /// Clears the cascade data, but not the invalidation data.
4059    fn clear_cascade_data(&mut self) {
4060        self.normal_rules.clear();
4061        if let Some(ref mut slotted_rules) = self.slotted_rules {
4062            slotted_rules.clear();
4063        }
4064        if let Some(ref mut part_rules) = self.part_rules {
4065            part_rules.clear();
4066        }
4067        if let Some(ref mut host_rules) = self.featureless_host_rules {
4068            host_rules.clear();
4069        }
4070        self.animations.clear();
4071        self.custom_property_registrations.clear();
4072        self.layer_id.clear();
4073        self.layers.clear();
4074        self.layers.push(CascadeLayer::root());
4075        self.container_conditions.clear();
4076        self.container_conditions
4077            .push(ContainerConditionReference::none());
4078        self.scope_conditions.clear();
4079        self.scope_conditions.push(ScopeConditionReference::none());
4080        #[cfg(feature = "gecko")]
4081        self.extra_data.clear();
4082        self.rules_source_order = 0;
4083        self.num_selectors = 0;
4084        self.num_declarations = 0;
4085    }
4086
4087    fn clear(&mut self) {
4088        self.clear_cascade_data();
4089        self.invalidation_map.clear();
4090        self.relative_selector_invalidation_map.clear();
4091        self.additional_relative_selector_invalidation_map.clear();
4092        self.attribute_dependencies.clear();
4093        self.nth_of_attribute_dependencies.clear();
4094        self.nth_of_custom_state_dependencies.clear();
4095        self.nth_of_class_dependencies.clear();
4096        self.state_dependencies = ElementState::empty();
4097        self.nth_of_state_dependencies = ElementState::empty();
4098        self.document_state_dependencies = DocumentState::empty();
4099        self.mapped_ids.clear();
4100        self.nth_of_mapped_ids.clear();
4101        self.selectors_for_cache_revalidation.clear();
4102        self.effective_media_query_results.clear();
4103        self.scope_subject_map.clear();
4104    }
4105}
4106
4107impl CascadeDataCacheEntry for CascadeData {
4108    fn rebuild<S>(
4109        device: &Device,
4110        quirks_mode: QuirksMode,
4111        collection: SheetCollectionFlusher<S>,
4112        guard: &SharedRwLockReadGuard,
4113        old: &Self,
4114    ) -> Result<Arc<Self>, AllocErr>
4115    where
4116        S: StylesheetInDocument + PartialEq + 'static,
4117    {
4118        debug_assert!(collection.dirty(), "We surely need to do something?");
4119        // If we're doing a full rebuild anyways, don't bother cloning the data.
4120        let mut updatable_entry = match collection.data_validity() {
4121            DataValidity::Valid | DataValidity::CascadeInvalid => old.clone(),
4122            DataValidity::FullyInvalid => Self::new(),
4123        };
4124        updatable_entry.rebuild(device, quirks_mode, collection, guard)?;
4125        Ok(Arc::new(updatable_entry))
4126    }
4127
4128    #[cfg(feature = "gecko")]
4129    fn add_size_of(&self, ops: &mut MallocSizeOfOps, sizes: &mut ServoStyleSetSizes) {
4130        self.normal_rules.add_size_of(ops, sizes);
4131        if let Some(ref slotted_rules) = self.slotted_rules {
4132            slotted_rules.add_size_of(ops, sizes);
4133        }
4134        if let Some(ref part_rules) = self.part_rules {
4135            part_rules.add_size_of(ops, sizes);
4136        }
4137        if let Some(ref host_rules) = self.featureless_host_rules {
4138            host_rules.add_size_of(ops, sizes);
4139        }
4140        sizes.mInvalidationMap += self.invalidation_map.size_of(ops);
4141        sizes.mRevalidationSelectors += self.selectors_for_cache_revalidation.size_of(ops);
4142        sizes.mOther += self.animations.size_of(ops);
4143        sizes.mOther += self.effective_media_query_results.size_of(ops);
4144        sizes.mOther += self.extra_data.size_of(ops);
4145    }
4146}
4147
4148impl Default for CascadeData {
4149    fn default() -> Self {
4150        CascadeData::new()
4151    }
4152}
4153
4154/// A rule, that wraps a style rule, but represents a single selector of the
4155/// rule.
4156#[derive(Clone, Debug, MallocSizeOf)]
4157pub struct Rule {
4158    /// The selector this struct represents. We store this and the
4159    /// any_{important,normal} booleans inline in the Rule to avoid
4160    /// pointer-chasing when gathering applicable declarations, which
4161    /// can ruin performance when there are a lot of rules.
4162    #[ignore_malloc_size_of = "CssRules have primary refs, we measure there"]
4163    pub selector: Selector<SelectorImpl>,
4164
4165    /// The ancestor hashes associated with the selector.
4166    pub hashes: AncestorHashes,
4167
4168    /// The source order this style rule appears in. Note that we only use
4169    /// three bytes to store this value in ApplicableDeclarationsBlock, so
4170    /// we could repurpose that storage here if we needed to.
4171    pub source_order: u32,
4172
4173    /// The current layer id of this style rule.
4174    pub layer_id: LayerId,
4175
4176    /// The current @container rule id.
4177    pub container_condition_id: ContainerConditionId,
4178
4179    /// True if this rule is inside @starting-style.
4180    pub is_starting_style: bool,
4181
4182    /// The current @scope rule id.
4183    pub scope_condition_id: ScopeConditionId,
4184
4185    /// The actual style rule.
4186    #[ignore_malloc_size_of = "Secondary ref. Primary ref is in StyleRule under Stylesheet."]
4187    pub style_source: StyleSource,
4188}
4189
4190impl SelectorMapEntry for Rule {
4191    fn selector(&self) -> SelectorIter<SelectorImpl> {
4192        self.selector.iter()
4193    }
4194}
4195
4196impl Rule {
4197    /// Returns the specificity of the rule.
4198    pub fn specificity(&self) -> u32 {
4199        self.selector.specificity()
4200    }
4201
4202    /// Turns this rule into an `ApplicableDeclarationBlock` for the given
4203    /// cascade level.
4204    pub fn to_applicable_declaration_block(
4205        &self,
4206        level: CascadeLevel,
4207        cascade_data: &CascadeData,
4208        scope_proximity: ScopeProximity,
4209    ) -> ApplicableDeclarationBlock {
4210        ApplicableDeclarationBlock::new(
4211            self.style_source.clone(),
4212            self.source_order,
4213            level,
4214            self.specificity(),
4215            cascade_data.layer_order_for(self.layer_id),
4216            scope_proximity,
4217        )
4218    }
4219
4220    /// Creates a new Rule.
4221    pub fn new(
4222        selector: Selector<SelectorImpl>,
4223        hashes: AncestorHashes,
4224        style_source: StyleSource,
4225        source_order: u32,
4226        layer_id: LayerId,
4227        container_condition_id: ContainerConditionId,
4228        is_starting_style: bool,
4229        scope_condition_id: ScopeConditionId,
4230    ) -> Self {
4231        Self {
4232            selector,
4233            hashes,
4234            style_source,
4235            source_order,
4236            layer_id,
4237            container_condition_id,
4238            is_starting_style,
4239            scope_condition_id,
4240        }
4241    }
4242}
4243
4244// The size of this is critical to performance on the bloom-basic
4245// microbenchmark.
4246// When iterating over a large Rule array, we want to be able to fast-reject
4247// selectors (with the inline hashes) with as few cache misses as possible.
4248size_of_test!(Rule, 40);
4249
4250/// A function to be able to test the revalidation stuff.
4251pub fn needs_revalidation_for_testing(s: &Selector<SelectorImpl>) -> bool {
4252    let mut needs_revalidation = false;
4253    let mut mapped_ids = Default::default();
4254    let mut nth_of_mapped_ids = Default::default();
4255    let mut attribute_dependencies = Default::default();
4256    let mut nth_of_class_dependencies = Default::default();
4257    let mut nth_of_attribute_dependencies = Default::default();
4258    let mut nth_of_custom_state_dependencies = Default::default();
4259    let mut state_dependencies = ElementState::empty();
4260    let mut nth_of_state_dependencies = ElementState::empty();
4261    let mut document_state_dependencies = DocumentState::empty();
4262    let mut visitor = StylistSelectorVisitor {
4263        passed_rightmost_selector: false,
4264        needs_revalidation: &mut needs_revalidation,
4265        in_selector_list_of: SelectorListKind::default(),
4266        mapped_ids: &mut mapped_ids,
4267        nth_of_mapped_ids: &mut nth_of_mapped_ids,
4268        attribute_dependencies: &mut attribute_dependencies,
4269        nth_of_class_dependencies: &mut nth_of_class_dependencies,
4270        nth_of_attribute_dependencies: &mut nth_of_attribute_dependencies,
4271        nth_of_custom_state_dependencies: &mut nth_of_custom_state_dependencies,
4272        state_dependencies: &mut state_dependencies,
4273        nth_of_state_dependencies: &mut nth_of_state_dependencies,
4274        document_state_dependencies: &mut document_state_dependencies,
4275    };
4276    s.visit(&mut visitor);
4277    needs_revalidation
4278}