1use 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
25pub struct PrecomputedHasher {
28 hash: Option<u32>,
29}
30
31impl Default for PrecomputedHasher {
32 fn default() -> Self {
33 Self { hash: None }
34 }
35}
36
37pub type RelevantAttributes = thin_vec::ThinVec<LocalName>;
39
40const 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
58pub type PrecomputedHashMap<K, V> = HashMap<K, V, BuildHasherDefault<PrecomputedHasher>>;
60
61pub 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
85pub trait SelectorMapEntry: Sized + Clone {
87 fn selector(&self) -> SelectorIter<'_, SelectorImpl>;
89}
90
91#[derive(Clone, Debug, MallocSizeOf)]
119pub struct SelectorMap<T: 'static> {
120 pub root: SmallVec<[T; 1]>,
122 pub id_hash: MaybeCaseInsensitiveHashMap<Atom, SmallVec<[T; 1]>>,
124 pub class_hash: MaybeCaseInsensitiveHashMap<Atom, SmallVec<[T; 1]>>,
126 pub local_name_hash: PrecomputedHashMap<LocalName, SmallVec<[T; 1]>>,
128 pub attribute_hash: PrecomputedHashMap<LocalName, SmallVec<[T; 1]>>,
130 pub namespace_hash: PrecomputedHashMap<Namespace, SmallVec<[T; 1]>>,
132 pub rare_pseudo_classes: SmallVec<[T; 1]>,
134 pub other: SmallVec<[T; 1]>,
136 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 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 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 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 pub fn is_empty(&self) -> bool {
187 self.count == 0
188 }
189
190 pub fn len(&self) -> usize {
192 self.count
193 }
194}
195
196impl SelectorMap<Rule> {
197 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 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 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 pub fn insert(&mut self, entry: T, quirks_mode: QuirksMode) -> Result<(), AllocErr> {
396 self.count += 1;
397
398 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 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 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 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 #[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 if !self.lookup_with_state(
650 element,
651 element.state() | additional_states,
652 quirks_mode,
653 None,
654 |entry| f(entry),
655 ) {
656 return false;
657 }
658
659 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 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 #[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 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#[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 if new_bucket.more_or_equally_specific_than(¤t_bucket) {
821 current_bucket = new_bucket;
822 }
823 }
824
825 if iter.next_sequence() != Some(Combinator::PseudoElement) {
828 break;
829 }
830 }
831
832 current_bucket
833}
834
835#[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 pub fn new() -> Self {
849 Self::default()
850 }
851
852 pub fn shrink_if_needed(&mut self) {
854 self.0.shrink_if_needed()
855 }
856
857 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 #[inline]
872 pub fn is_empty(&self) -> bool {
873 self.0.is_empty()
874 }
875
876 pub fn iter(&self) -> hash_map::Iter<'_, Atom, V> {
878 self.0.iter()
879 }
880
881 pub fn clear(&mut self) {
883 self.0.clear()
884 }
885
886 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}