style/
selector_map.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//! A data structure to efficiently index structs containing selectors by local
6//! name, ids and hash.
7
8use crate::applicable_declarations::{ApplicableDeclarationList, ScopeProximity};
9use crate::context::QuirksMode;
10use crate::dom::TElement;
11use crate::rule_tree::CascadeLevel;
12use crate::selector_parser::SelectorImpl;
13use crate::stylist::{CascadeData, ContainerConditionId, Rule, ScopeConditionId, Stylist};
14use crate::AllocErr;
15use crate::{Atom, LocalName, Namespace, ShrinkIfNeeded, WeakAtom};
16use dom::ElementState;
17use precomputed_hash::PrecomputedHash;
18use selectors::matching::{matches_selector, MatchingContext};
19use selectors::parser::{Combinator, Component, SelectorIter};
20use smallvec::SmallVec;
21use std::collections::hash_map;
22use std::collections::{HashMap, HashSet};
23use std::hash::{BuildHasherDefault, Hash, Hasher};
24
25/// A hasher implementation that doesn't hash anything, because it expects its
26/// input to be a suitable u32 hash.
27pub struct PrecomputedHasher {
28    hash: Option<u32>,
29}
30
31impl Default for PrecomputedHasher {
32    fn default() -> Self {
33        Self { hash: None }
34    }
35}
36
37/// A vector of relevant attributes, that can be useful for revalidation.
38pub type RelevantAttributes = thin_vec::ThinVec<LocalName>;
39
40/// This is a set of pseudo-classes that are both relatively-rare (they don't
41/// affect most elements by default) and likely or known to have global rules
42/// (in e.g., the UA sheets).
43///
44/// We can avoid selector-matching those global rules for all elements without
45/// these pseudo-class states.
46const RARE_PSEUDO_CLASS_STATES: ElementState = ElementState::from_bits_retain(
47    ElementState::FULLSCREEN.bits()
48        | ElementState::VISITED_OR_UNVISITED.bits()
49        | ElementState::URLTARGET.bits()
50        | ElementState::INERT.bits()
51        | ElementState::FOCUS.bits()
52        | ElementState::FOCUSRING.bits()
53        | ElementState::TOPMOST_MODAL.bits()
54        | ElementState::SUPPRESS_FOR_PRINT_SELECTION.bits()
55        | ElementState::HEADING_LEVEL_BITS.bits(),
56);
57
58/// A simple alias for a hashmap using PrecomputedHasher.
59pub type PrecomputedHashMap<K, V> = HashMap<K, V, BuildHasherDefault<PrecomputedHasher>>;
60
61/// A simple alias for a hashset using PrecomputedHasher.
62pub type PrecomputedHashSet<K> = HashSet<K, BuildHasherDefault<PrecomputedHasher>>;
63
64impl Hasher for PrecomputedHasher {
65    #[inline]
66    fn write(&mut self, _: &[u8]) {
67        unreachable!(
68            "Called into PrecomputedHasher with something that isn't \
69             a u32"
70        )
71    }
72
73    #[inline]
74    fn write_u32(&mut self, i: u32) {
75        debug_assert!(self.hash.is_none());
76        self.hash = Some(i);
77    }
78
79    #[inline]
80    fn finish(&self) -> u64 {
81        self.hash.expect("PrecomputedHasher wasn't fed?") as u64
82    }
83}
84
85/// A trait to abstract over a given selector map entry.
86pub trait SelectorMapEntry: Sized + Clone {
87    /// Gets the selector we should use to index in the selector map.
88    fn selector(&self) -> SelectorIter<'_, SelectorImpl>;
89}
90
91/// Map element data to selector-providing objects for which the last simple
92/// selector starts with them.
93///
94/// e.g.,
95/// "p > img" would go into the set of selectors corresponding to the
96/// element "img"
97/// "a .foo .bar.baz" would go into the set of selectors corresponding to
98/// the class "bar"
99///
100/// Because we match selectors right-to-left (i.e., moving up the tree
101/// from an element), we need to compare the last simple selector in the
102/// selector with the element.
103///
104/// So, if an element has ID "id1" and classes "foo" and "bar", then all
105/// the rules it matches will have their last simple selector starting
106/// either with "#id1" or with ".foo" or with ".bar".
107///
108/// Hence, the union of the rules keyed on each of element's classes, ID,
109/// element name, etc. will contain the Selectors that actually match that
110/// element.
111///
112/// We use a 1-entry SmallVec to avoid a separate heap allocation in the case
113/// where we only have one entry, which is quite common. See measurements in:
114/// * https://bugzilla.mozilla.org/show_bug.cgi?id=1363789#c5
115/// * https://bugzilla.mozilla.org/show_bug.cgi?id=681755
116///
117/// TODO: Tune the initial capacity of the HashMap
118#[derive(Clone, Debug, MallocSizeOf)]
119pub struct SelectorMap<T: 'static> {
120    /// Rules that have `:root` selectors.
121    pub root: SmallVec<[T; 1]>,
122    /// A hash from an ID to rules which contain that ID selector.
123    pub id_hash: MaybeCaseInsensitiveHashMap<Atom, SmallVec<[T; 1]>>,
124    /// A hash from a class name to rules which contain that class selector.
125    pub class_hash: MaybeCaseInsensitiveHashMap<Atom, SmallVec<[T; 1]>>,
126    /// A hash from local name to rules which contain that local name selector.
127    pub local_name_hash: PrecomputedHashMap<LocalName, SmallVec<[T; 1]>>,
128    /// A hash from attributes to rules which contain that attribute selector.
129    pub attribute_hash: PrecomputedHashMap<LocalName, SmallVec<[T; 1]>>,
130    /// A hash from namespace to rules which contain that namespace selector.
131    pub namespace_hash: PrecomputedHashMap<Namespace, SmallVec<[T; 1]>>,
132    /// Rules for pseudo-states that are rare but have global selectors.
133    pub rare_pseudo_classes: SmallVec<[T; 1]>,
134    /// All other rules.
135    pub other: SmallVec<[T; 1]>,
136    /// The number of entries in this map.
137    pub count: usize,
138}
139
140impl<T: 'static> Default for SelectorMap<T> {
141    #[inline]
142    fn default() -> Self {
143        Self::new()
144    }
145}
146
147impl<T> SelectorMap<T> {
148    /// Trivially constructs an empty `SelectorMap`.
149    pub fn new() -> Self {
150        SelectorMap {
151            root: SmallVec::new(),
152            id_hash: MaybeCaseInsensitiveHashMap::new(),
153            class_hash: MaybeCaseInsensitiveHashMap::new(),
154            attribute_hash: HashMap::default(),
155            local_name_hash: HashMap::default(),
156            namespace_hash: HashMap::default(),
157            rare_pseudo_classes: SmallVec::new(),
158            other: SmallVec::new(),
159            count: 0,
160        }
161    }
162
163    /// Shrink the capacity of the map if needed.
164    pub fn shrink_if_needed(&mut self) {
165        self.id_hash.shrink_if_needed();
166        self.class_hash.shrink_if_needed();
167        self.attribute_hash.shrink_if_needed();
168        self.local_name_hash.shrink_if_needed();
169        self.namespace_hash.shrink_if_needed();
170    }
171
172    /// Clears the hashmap retaining storage.
173    pub fn clear(&mut self) {
174        self.root.clear();
175        self.id_hash.clear();
176        self.class_hash.clear();
177        self.attribute_hash.clear();
178        self.local_name_hash.clear();
179        self.namespace_hash.clear();
180        self.rare_pseudo_classes.clear();
181        self.other.clear();
182        self.count = 0;
183    }
184
185    /// Returns whether there are any entries in the map.
186    pub fn is_empty(&self) -> bool {
187        self.count == 0
188    }
189
190    /// Returns the number of entries.
191    pub fn len(&self) -> usize {
192        self.count
193    }
194}
195
196impl SelectorMap<Rule> {
197    /// Append to `rule_list` all Rules in `self` that match element.
198    ///
199    /// Extract matching rules as per element's ID, classes, tag name, etc..
200    /// Sort the Rules at the end to maintain cascading order.
201    pub fn get_all_matching_rules<E>(
202        &self,
203        element: E,
204        rule_hash_target: E,
205        matching_rules_list: &mut ApplicableDeclarationList,
206        matching_context: &mut MatchingContext<E::Impl>,
207        cascade_level: CascadeLevel,
208        cascade_data: &CascadeData,
209        stylist: &Stylist,
210    ) where
211        E: TElement,
212    {
213        if self.is_empty() {
214            return;
215        }
216
217        let quirks_mode = matching_context.quirks_mode();
218
219        if rule_hash_target.is_root() {
220            SelectorMap::get_matching_rules(
221                element,
222                &self.root,
223                matching_rules_list,
224                matching_context,
225                cascade_level,
226                cascade_data,
227                stylist,
228            );
229        }
230
231        if let Some(id) = rule_hash_target.id() {
232            if let Some(rules) = self.id_hash.get(id, quirks_mode) {
233                SelectorMap::get_matching_rules(
234                    element,
235                    rules,
236                    matching_rules_list,
237                    matching_context,
238                    cascade_level,
239                    cascade_data,
240                    stylist,
241                )
242            }
243        }
244
245        rule_hash_target.each_class(|class| {
246            if let Some(rules) = self.class_hash.get(&class, quirks_mode) {
247                SelectorMap::get_matching_rules(
248                    element,
249                    rules,
250                    matching_rules_list,
251                    matching_context,
252                    cascade_level,
253                    cascade_data,
254                    stylist,
255                )
256            }
257        });
258
259        rule_hash_target.each_attr_name(|name| {
260            if let Some(rules) = self.attribute_hash.get(name) {
261                SelectorMap::get_matching_rules(
262                    element,
263                    rules,
264                    matching_rules_list,
265                    matching_context,
266                    cascade_level,
267                    cascade_data,
268                    stylist,
269                )
270            }
271        });
272
273        if let Some(rules) = self.local_name_hash.get(rule_hash_target.local_name()) {
274            SelectorMap::get_matching_rules(
275                element,
276                rules,
277                matching_rules_list,
278                matching_context,
279                cascade_level,
280                cascade_data,
281                stylist,
282            )
283        }
284
285        if rule_hash_target
286            .state()
287            .intersects(RARE_PSEUDO_CLASS_STATES)
288        {
289            SelectorMap::get_matching_rules(
290                element,
291                &self.rare_pseudo_classes,
292                matching_rules_list,
293                matching_context,
294                cascade_level,
295                cascade_data,
296                stylist,
297            );
298        }
299
300        if let Some(rules) = self.namespace_hash.get(rule_hash_target.namespace()) {
301            SelectorMap::get_matching_rules(
302                element,
303                rules,
304                matching_rules_list,
305                matching_context,
306                cascade_level,
307                cascade_data,
308                stylist,
309            )
310        }
311
312        SelectorMap::get_matching_rules(
313            element,
314            &self.other,
315            matching_rules_list,
316            matching_context,
317            cascade_level,
318            cascade_data,
319            stylist,
320        );
321    }
322
323    /// Adds rules in `rules` that match `element` to the `matching_rules` list.
324    pub(crate) fn get_matching_rules<E>(
325        element: E,
326        rules: &[Rule],
327        matching_rules: &mut ApplicableDeclarationList,
328        matching_context: &mut MatchingContext<E::Impl>,
329        cascade_level: CascadeLevel,
330        cascade_data: &CascadeData,
331        stylist: &Stylist,
332    ) where
333        E: TElement,
334    {
335        use selectors::matching::IncludeStartingStyle;
336
337        let include_starting_style = matches!(
338            matching_context.include_starting_style,
339            IncludeStartingStyle::Yes
340        );
341        for rule in rules {
342            let scope_proximity = if rule.scope_condition_id == ScopeConditionId::none() {
343                if !matches_selector(
344                    &rule.selector,
345                    0,
346                    Some(&rule.hashes),
347                    &element,
348                    matching_context,
349                ) {
350                    continue;
351                }
352                ScopeProximity::infinity()
353            } else {
354                let result =
355                    cascade_data.find_scope_proximity_if_matching(rule, element, matching_context);
356                if result == ScopeProximity::infinity() {
357                    continue;
358                }
359                result
360            };
361
362            if rule.container_condition_id != ContainerConditionId::none() {
363                if !cascade_data.container_condition_matches(
364                    rule.container_condition_id,
365                    stylist,
366                    element,
367                    matching_context,
368                ) {
369                    continue;
370                }
371            }
372
373            if rule.is_starting_style {
374                // Set this flag if there are any rules inside @starting-style. This flag is for
375                // optimization to avoid any redundant resolution of starting style if the author
376                // doesn't specify for this element.
377                matching_context.has_starting_style = true;
378
379                if !include_starting_style {
380                    continue;
381                }
382            }
383
384            matching_rules.push(rule.to_applicable_declaration_block(
385                cascade_level,
386                cascade_data,
387                scope_proximity,
388            ));
389        }
390    }
391}
392
393impl<T: SelectorMapEntry> SelectorMap<T> {
394    /// Inserts an entry into the correct bucket(s).
395    pub fn insert(&mut self, entry: T, quirks_mode: QuirksMode) -> Result<(), AllocErr> {
396        self.count += 1;
397
398        // NOTE(emilio): It'd be nice for this to be a separate function, but
399        // then the compiler can't reason about the lifetime dependency between
400        // `entry` and `bucket`, and would force us to clone the rule in the
401        // common path.
402        macro_rules! insert_into_bucket {
403            ($entry:ident, $bucket:expr) => {{
404                let vec = match $bucket {
405                    Bucket::Root => &mut self.root,
406                    Bucket::ID(id) => self
407                        .id_hash
408                        .try_entry(id.clone(), quirks_mode)?
409                        .or_default(),
410                    Bucket::Class(class) => self
411                        .class_hash
412                        .try_entry(class.clone(), quirks_mode)?
413                        .or_default(),
414                    Bucket::Attribute { name, lower_name }
415                    | Bucket::LocalName { name, lower_name } => {
416                        // If the local name in the selector isn't lowercase,
417                        // insert it into the rule hash twice. This means that,
418                        // during lookup, we can always find the rules based on
419                        // the local name of the element, regardless of whether
420                        // it's an html element in an html document (in which
421                        // case we match against lower_name) or not (in which
422                        // case we match against name).
423                        //
424                        // In the case of a non-html-element-in-html-document
425                        // with a lowercase localname and a non-lowercase
426                        // selector, the rulehash lookup may produce superfluous
427                        // selectors, but the subsequent selector matching work
428                        // will filter them out.
429                        let is_attribute = matches!($bucket, Bucket::Attribute { .. });
430                        let hash = if is_attribute {
431                            &mut self.attribute_hash
432                        } else {
433                            &mut self.local_name_hash
434                        };
435                        if name != lower_name {
436                            hash.try_reserve(1)?;
437                            let vec = hash.entry(lower_name.clone()).or_default();
438                            vec.try_reserve(1)?;
439                            vec.push($entry.clone());
440                        }
441                        hash.try_reserve(1)?;
442                        hash.entry(name.clone()).or_default()
443                    },
444                    Bucket::Namespace(url) => {
445                        self.namespace_hash.try_reserve(1)?;
446                        self.namespace_hash.entry(url.clone()).or_default()
447                    },
448                    Bucket::RarePseudoClasses => &mut self.rare_pseudo_classes,
449                    Bucket::Universal => &mut self.other,
450                };
451                vec.try_reserve(1)?;
452                vec.push($entry);
453            }};
454        }
455
456        let bucket = {
457            let mut disjoint_buckets = SmallVec::new();
458            let bucket = find_bucket(entry.selector(), &mut disjoint_buckets);
459
460            // See if inserting this selector in multiple entries in the
461            // selector map would be worth it. Consider a case like:
462            //
463            //   .foo:where(div, #bar)
464            //
465            // There, `bucket` would be `Class(foo)`, and disjoint_buckets would
466            // be `[LocalName { div }, ID(bar)]`.
467            //
468            // Here we choose to insert the selector in the `.foo` bucket in
469            // such a case, as it's likely more worth it than inserting it in
470            // both `div` and `#bar`.
471            //
472            // This is specially true if there's any universal selector in the
473            // `disjoint_selectors` set, at which point we'd just be doing
474            // wasted work.
475            if !disjoint_buckets.is_empty()
476                && disjoint_buckets
477                    .iter()
478                    .all(|b| b.more_specific_than(&bucket))
479            {
480                for bucket in &disjoint_buckets {
481                    let entry = entry.clone();
482                    insert_into_bucket!(entry, *bucket);
483                }
484                return Ok(());
485            }
486            bucket
487        };
488
489        insert_into_bucket!(entry, bucket);
490        Ok(())
491    }
492
493    /// Looks up entries by id, class, local name, namespace, and other (in
494    /// order).
495    ///
496    /// Each entry is passed to the callback, which returns true to continue
497    /// iterating entries, or false to terminate the lookup.
498    ///
499    /// Returns false if the callback ever returns false.
500    ///
501    /// FIXME(bholley) This overlaps with SelectorMap<Rule>::get_all_matching_rules,
502    /// but that function is extremely hot and I'd rather not rearrange it.
503    pub fn lookup<'a, E, F>(
504        &'a self,
505        element: E,
506        quirks_mode: QuirksMode,
507        relevant_attributes: Option<&mut RelevantAttributes>,
508        f: F,
509    ) -> bool
510    where
511        E: TElement,
512        F: FnMut(&'a T) -> bool,
513    {
514        self.lookup_with_state(
515            element,
516            element.state(),
517            quirks_mode,
518            relevant_attributes,
519            f,
520        )
521    }
522
523    #[inline]
524    fn lookup_with_state<'a, E, F>(
525        &'a self,
526        element: E,
527        element_state: ElementState,
528        quirks_mode: QuirksMode,
529        mut relevant_attributes: Option<&mut RelevantAttributes>,
530        mut f: F,
531    ) -> bool
532    where
533        E: TElement,
534        F: FnMut(&'a T) -> bool,
535    {
536        if element.is_root() {
537            for entry in self.root.iter() {
538                if !f(&entry) {
539                    return false;
540                }
541            }
542        }
543
544        if let Some(id) = element.id() {
545            if let Some(v) = self.id_hash.get(id, quirks_mode) {
546                for entry in v.iter() {
547                    if !f(&entry) {
548                        return false;
549                    }
550                }
551            }
552        }
553
554        let mut done = false;
555        element.each_class(|class| {
556            if done {
557                return;
558            }
559            if let Some(v) = self.class_hash.get(class, quirks_mode) {
560                for entry in v.iter() {
561                    if !f(&entry) {
562                        done = true;
563                        return;
564                    }
565                }
566            }
567        });
568
569        if done {
570            return false;
571        }
572
573        element.each_attr_name(|name| {
574            if done {
575                return;
576            }
577            if let Some(v) = self.attribute_hash.get(name) {
578                if let Some(ref mut relevant_attributes) = relevant_attributes {
579                    relevant_attributes.push(name.clone());
580                }
581                for entry in v.iter() {
582                    if !f(&entry) {
583                        done = true;
584                        return;
585                    }
586                }
587            }
588        });
589
590        if done {
591            return false;
592        }
593
594        if let Some(v) = self.local_name_hash.get(element.local_name()) {
595            for entry in v.iter() {
596                if !f(&entry) {
597                    return false;
598                }
599            }
600        }
601
602        if let Some(v) = self.namespace_hash.get(element.namespace()) {
603            for entry in v.iter() {
604                if !f(&entry) {
605                    return false;
606                }
607            }
608        }
609
610        if element_state.intersects(RARE_PSEUDO_CLASS_STATES) {
611            for entry in self.rare_pseudo_classes.iter() {
612                if !f(&entry) {
613                    return false;
614                }
615            }
616        }
617
618        for entry in self.other.iter() {
619            if !f(&entry) {
620                return false;
621            }
622        }
623
624        true
625    }
626
627    /// Performs a normal lookup, and also looks up entries for the passed-in
628    /// id and classes.
629    ///
630    /// Each entry is passed to the callback, which returns true to continue
631    /// iterating entries, or false to terminate the lookup.
632    ///
633    /// Returns false if the callback ever returns false.
634    #[inline]
635    pub fn lookup_with_additional<'a, E, F>(
636        &'a self,
637        element: E,
638        quirks_mode: QuirksMode,
639        additional_id: Option<&WeakAtom>,
640        additional_classes: &[Atom],
641        additional_states: ElementState,
642        mut f: F,
643    ) -> bool
644    where
645        E: TElement,
646        F: FnMut(&'a T) -> bool,
647    {
648        // Do the normal lookup.
649        if !self.lookup_with_state(
650            element,
651            element.state() | additional_states,
652            quirks_mode,
653            /* relevant_attributes = */ None,
654            |entry| f(entry),
655        ) {
656            return false;
657        }
658
659        // Check the additional id.
660        if let Some(id) = additional_id {
661            if let Some(v) = self.id_hash.get(id, quirks_mode) {
662                for entry in v.iter() {
663                    if !f(&entry) {
664                        return false;
665                    }
666                }
667            }
668        }
669
670        // Check the additional classes.
671        for class in additional_classes {
672            if let Some(v) = self.class_hash.get(class, quirks_mode) {
673                for entry in v.iter() {
674                    if !f(&entry) {
675                        return false;
676                    }
677                }
678            }
679        }
680
681        true
682    }
683}
684
685enum Bucket<'a> {
686    Universal,
687    Namespace(&'a Namespace),
688    RarePseudoClasses,
689    LocalName {
690        name: &'a LocalName,
691        lower_name: &'a LocalName,
692    },
693    Attribute {
694        name: &'a LocalName,
695        lower_name: &'a LocalName,
696    },
697    Class(&'a Atom),
698    ID(&'a Atom),
699    Root,
700}
701
702impl<'a> Bucket<'a> {
703    /// root > id > class > local name > namespace > pseudo-classes > universal.
704    #[inline]
705    fn specificity(&self) -> usize {
706        match *self {
707            Bucket::Universal => 0,
708            Bucket::Namespace(..) => 1,
709            Bucket::RarePseudoClasses => 2,
710            Bucket::LocalName { .. } => 3,
711            Bucket::Attribute { .. } => 4,
712            Bucket::Class(..) => 5,
713            Bucket::ID(..) => 6,
714            Bucket::Root => 7,
715        }
716    }
717
718    #[inline]
719    fn more_or_equally_specific_than(&self, other: &Self) -> bool {
720        self.specificity() >= other.specificity()
721    }
722
723    #[inline]
724    fn more_specific_than(&self, other: &Self) -> bool {
725        self.specificity() > other.specificity()
726    }
727}
728
729type DisjointBuckets<'a> = SmallVec<[Bucket<'a>; 5]>;
730
731fn specific_bucket_for<'a>(
732    component: &'a Component<SelectorImpl>,
733    disjoint_buckets: &mut DisjointBuckets<'a>,
734) -> Bucket<'a> {
735    match *component {
736        Component::Root => Bucket::Root,
737        Component::ID(ref id) => Bucket::ID(id),
738        Component::Class(ref class) => Bucket::Class(class),
739        Component::AttributeInNoNamespace { ref local_name, .. } => Bucket::Attribute {
740            name: local_name,
741            lower_name: local_name,
742        },
743        Component::AttributeInNoNamespaceExists {
744            ref local_name,
745            ref local_name_lower,
746        } => Bucket::Attribute {
747            name: local_name,
748            lower_name: local_name_lower,
749        },
750        Component::AttributeOther(ref selector) => Bucket::Attribute {
751            name: &selector.local_name,
752            lower_name: &selector.local_name_lower,
753        },
754        Component::LocalName(ref selector) => Bucket::LocalName {
755            name: &selector.name,
756            lower_name: &selector.lower_name,
757        },
758        Component::Namespace(_, ref url) | Component::DefaultNamespace(ref url) => {
759            Bucket::Namespace(url)
760        },
761        // ::slotted(..) isn't a normal pseudo-element, so we can insert it on
762        // the rule hash normally without much problem. For example, in a
763        // selector like:
764        //
765        //   div::slotted(span)::before
766        //
767        // It looks like:
768        //
769        //  [
770        //    LocalName(div),
771        //    Combinator(SlotAssignment),
772        //    Slotted(span),
773        //    Combinator::PseudoElement,
774        //    PseudoElement(::before),
775        //  ]
776        //
777        // So inserting `span` in the rule hash makes sense since we want to
778        // match the slotted <span>.
779        Component::Slotted(ref selector) => find_bucket(selector.iter(), disjoint_buckets),
780        Component::Host(Some(ref selector)) => find_bucket(selector.iter(), disjoint_buckets),
781        Component::Is(ref list) | Component::Where(ref list) => {
782            if list.len() == 1 {
783                find_bucket(list.slice()[0].iter(), disjoint_buckets)
784            } else {
785                for selector in list.slice() {
786                    let bucket = find_bucket(selector.iter(), disjoint_buckets);
787                    disjoint_buckets.push(bucket);
788                }
789                Bucket::Universal
790            }
791        },
792        Component::NonTSPseudoClass(ref pseudo_class)
793            if pseudo_class
794                .state_flag()
795                .intersects(RARE_PSEUDO_CLASS_STATES) =>
796        {
797            Bucket::RarePseudoClasses
798        },
799        _ => Bucket::Universal,
800    }
801}
802
803/// Searches a compound selector from left to right, and returns the appropriate
804/// bucket for it.
805///
806/// It also populates disjoint_buckets with dependencies from nested selectors
807/// with any semantics like :is() and :where().
808#[inline(always)]
809fn find_bucket<'a>(
810    mut iter: SelectorIter<'a, SelectorImpl>,
811    disjoint_buckets: &mut DisjointBuckets<'a>,
812) -> Bucket<'a> {
813    let mut current_bucket = Bucket::Universal;
814
815    loop {
816        for ss in &mut iter {
817            let new_bucket = specific_bucket_for(ss, disjoint_buckets);
818            // NOTE: When presented with the choice of multiple specific selectors, use the
819            // rightmost, on the assumption that that's less common, see bug 1829540.
820            if new_bucket.more_or_equally_specific_than(&current_bucket) {
821                current_bucket = new_bucket;
822            }
823        }
824
825        // Effectively, pseudo-elements are ignored, given only state
826        // pseudo-classes may appear before them.
827        if iter.next_sequence() != Some(Combinator::PseudoElement) {
828            break;
829        }
830    }
831
832    current_bucket
833}
834
835/// Wrapper for PrecomputedHashMap that does ASCII-case-insensitive lookup in quirks mode.
836#[derive(Clone, Debug, MallocSizeOf)]
837pub struct MaybeCaseInsensitiveHashMap<K: PrecomputedHash + Hash + Eq, V>(PrecomputedHashMap<K, V>);
838
839impl<V> Default for MaybeCaseInsensitiveHashMap<Atom, V> {
840    #[inline]
841    fn default() -> Self {
842        MaybeCaseInsensitiveHashMap(PrecomputedHashMap::default())
843    }
844}
845
846impl<V> MaybeCaseInsensitiveHashMap<Atom, V> {
847    /// Empty map
848    pub fn new() -> Self {
849        Self::default()
850    }
851
852    /// Shrink the capacity of the map if needed.
853    pub fn shrink_if_needed(&mut self) {
854        self.0.shrink_if_needed()
855    }
856
857    /// HashMap::try_entry
858    pub fn try_entry(
859        &mut self,
860        mut key: Atom,
861        quirks_mode: QuirksMode,
862    ) -> Result<hash_map::Entry<'_, Atom, V>, AllocErr> {
863        if quirks_mode == QuirksMode::Quirks {
864            key = key.to_ascii_lowercase()
865        }
866        self.0.try_reserve(1)?;
867        Ok(self.0.entry(key))
868    }
869
870    /// HashMap::is_empty
871    #[inline]
872    pub fn is_empty(&self) -> bool {
873        self.0.is_empty()
874    }
875
876    /// HashMap::iter
877    pub fn iter(&self) -> hash_map::Iter<'_, Atom, V> {
878        self.0.iter()
879    }
880
881    /// HashMap::clear
882    pub fn clear(&mut self) {
883        self.0.clear()
884    }
885
886    /// HashMap::get
887    pub fn get(&self, key: &WeakAtom, quirks_mode: QuirksMode) -> Option<&V> {
888        if quirks_mode == QuirksMode::Quirks {
889            self.0.get(&key.to_ascii_lowercase())
890        } else {
891            self.0.get(key)
892        }
893    }
894}