selectors/
nth_index_cache.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
5use std::hash::Hash;
6
7use crate::{parser::Selector, tree::OpaqueElement, SelectorImpl};
8use fxhash::FxHashMap;
9
10/// A cache to speed up matching of nth-index-like selectors.
11///
12/// See [1] for some discussion around the design tradeoffs.
13///
14/// [1] https://bugzilla.mozilla.org/show_bug.cgi?id=1401855#c3
15#[derive(Default)]
16pub struct NthIndexCache {
17    nth: NthIndexCacheInner,
18    nth_of_selectors: NthIndexOfSelectorsCaches,
19    nth_last: NthIndexCacheInner,
20    nth_last_of_selectors: NthIndexOfSelectorsCaches,
21    nth_of_type: NthIndexCacheInner,
22    nth_last_of_type: NthIndexCacheInner,
23}
24
25impl NthIndexCache {
26    /// Gets the appropriate cache for the given parameters.
27    pub fn get<Impl: SelectorImpl>(
28        &mut self,
29        is_of_type: bool,
30        is_from_end: bool,
31        selectors: &[Selector<Impl>],
32    ) -> &mut NthIndexCacheInner {
33        if is_of_type {
34            return if is_from_end {
35                &mut self.nth_last_of_type
36            } else {
37                &mut self.nth_of_type
38            };
39        }
40        if !selectors.is_empty() {
41            return if is_from_end {
42                self.nth_last_of_selectors.lookup(selectors)
43            } else {
44                self.nth_of_selectors.lookup(selectors)
45            };
46        }
47        if is_from_end {
48            &mut self.nth_last
49        } else {
50            &mut self.nth
51        }
52    }
53}
54
55#[derive(Hash, Eq, PartialEq)]
56struct SelectorListCacheKey(usize);
57
58/// Use the selector list's pointer as the cache key
59impl SelectorListCacheKey {
60    // :nth-child of selectors are reference-counted with `ThinArc`, so we know their pointers are stable.
61    fn new<Impl: SelectorImpl>(selectors: &[Selector<Impl>]) -> Self {
62        Self(selectors.as_ptr() as usize)
63    }
64}
65
66/// Use a different map of cached indices per :nth-child's or :nth-last-child's selector list
67#[derive(Default)]
68pub struct NthIndexOfSelectorsCaches(FxHashMap<SelectorListCacheKey, NthIndexCacheInner>);
69
70/// Get or insert a map of cached incides for the selector list of this
71/// particular :nth-child or :nth-last-child pseudoclass
72impl NthIndexOfSelectorsCaches {
73    pub fn lookup<Impl: SelectorImpl>(
74        &mut self,
75        selectors: &[Selector<Impl>],
76    ) -> &mut NthIndexCacheInner {
77        self.0
78            .entry(SelectorListCacheKey::new(selectors))
79            .or_default()
80    }
81}
82
83/// The concrete per-pseudo-class cache.
84#[derive(Default)]
85pub struct NthIndexCacheInner(FxHashMap<OpaqueElement, i32>);
86
87impl NthIndexCacheInner {
88    /// Does a lookup for a given element in the cache.
89    pub fn lookup(&mut self, el: OpaqueElement) -> Option<i32> {
90        self.0.get(&el).copied()
91    }
92
93    /// Inserts an entry into the cache.
94    pub fn insert(&mut self, element: OpaqueElement, index: i32) {
95        self.0.insert(element, index);
96    }
97
98    /// Returns whether the cache is empty.
99    pub fn is_empty(&self) -> bool {
100        self.0.is_empty()
101    }
102}
selectors/nth_index_cache.rs

selectors/
nth_index_cache.rs
