tor-browser

The Tor Browser
git clone https://git.dasho.dev/tor-browser.git
Log | Files | Refs | README | LICENSE

nth_index_cache.rs (3176B)

      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 use std::hash::Hash;
      6 
      7 use crate::{parser::Selector, tree::OpaqueElement, SelectorImpl};
      8 use rustc_hash::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)]
     16 pub 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 
     25 impl 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)]
     56 struct SelectorListCacheKey(usize);
     57 
     58 /// Use the selector list's pointer as the cache key
     59 impl 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)]
     68 pub 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
     72 impl 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)]
     85 pub struct NthIndexCacheInner(FxHashMap<OpaqueElement, i32>);
     86 
     87 impl 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 }