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