style/
custom_properties_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//! The structure that contains the custom properties of a given element.
6
7use crate::custom_properties::Name;
8use crate::properties_and_values::value::ComputedValue as ComputedRegisteredValue;
9use crate::selector_map::PrecomputedHasher;
10use indexmap::IndexMap;
11use servo_arc::Arc;
12use std::hash::BuildHasherDefault;
13use std::sync::LazyLock;
14
15/// A map for a set of custom properties, which implements copy-on-write behavior on insertion with
16/// cheap copying.
17#[derive(Clone, Debug, PartialEq)]
18pub struct CustomPropertiesMap(Arc<Inner>);
19
20impl Default for CustomPropertiesMap {
21    fn default() -> Self {
22        Self(EMPTY.clone())
23    }
24}
25
26/// We use None in the value to represent a removed entry.
27pub type OwnMap =
28    IndexMap<Name, Option<ComputedRegisteredValue>, BuildHasherDefault<PrecomputedHasher>>;
29
30static EMPTY: LazyLock<Arc<Inner>> = LazyLock::new(|| {
31    Arc::new_leaked(Inner {
32        own_properties: Default::default(),
33        parent: None,
34        len: 0,
35        ancestor_count: 0,
36    })
37});
38
39#[derive(Debug, Clone)]
40struct Inner {
41    own_properties: OwnMap,
42    parent: Option<Arc<Inner>>,
43    /// The number of custom properties we store. Note that this is different from the sum of our
44    /// own and our parent's length, since we might store duplicate entries.
45    len: usize,
46    /// The number of ancestors we have.
47    ancestor_count: u8,
48}
49
50/// A not-too-large, not too small ancestor limit, to prevent creating too-big chains.
51const ANCESTOR_COUNT_LIMIT: usize = 4;
52
53/// An iterator over the custom properties.
54pub struct Iter<'a> {
55    current: &'a Inner,
56    current_iter: indexmap::map::Iter<'a, Name, Option<ComputedRegisteredValue>>,
57    descendants: smallvec::SmallVec<[&'a Inner; ANCESTOR_COUNT_LIMIT]>,
58}
59
60impl<'a> Iterator for Iter<'a> {
61    type Item = (&'a Name, &'a Option<ComputedRegisteredValue>);
62
63    fn next(&mut self) -> Option<Self::Item> {
64        loop {
65            let (name, value) = match self.current_iter.next() {
66                Some(v) => v,
67                None => {
68                    let parent = self.current.parent.as_deref()?;
69                    self.descendants.push(self.current);
70                    self.current = parent;
71                    self.current_iter = parent.own_properties.iter();
72                    continue;
73                },
74            };
75            // If the property is overridden by a descendant we've already visited it.
76            for descendant in &self.descendants {
77                if descendant.own_properties.contains_key(name) {
78                    continue;
79                }
80            }
81            return Some((name, value));
82        }
83    }
84}
85
86#[inline]
87fn can_deduplicate_values(
88    a: Option<&ComputedRegisteredValue>,
89    b: Option<&ComputedRegisteredValue>,
90) -> bool {
91    match (a, b) {
92        (Some(a), Some(b)) => {
93            // TODO(emilio): Seems we should compare `url_data` as well? It doesn't seem to matter
94            // much in practice since url values would be already-computed against the right base
95            // URI here, I think...
96            a == b && a.attr_tainted == b.attr_tainted
97        },
98        (None, None) => true,
99        _ => false,
100    }
101}
102
103impl PartialEq for Inner {
104    fn eq(&self, other: &Self) -> bool {
105        if self.len != other.len {
106            return false;
107        }
108        // NOTE(emilio): In order to speed up custom property comparison when tons of custom
109        // properties are involved, we return false in some cases where the ordering might be
110        // different, but the computed values end up being the same.
111        //
112        // This is a performance trade-off, on the assumption that if the ordering is different,
113        // there's likely a different value as well, but might over-invalidate.
114        //
115        // Doing the slow thing (checking all the keys) shows up a lot in profiles, see bug 1926423.
116        //
117        // Note that self.own_properties != other.own_properties is not the same, as by default
118        // IndexMap comparison is not order-aware.
119        //
120        // Note also that for this comparison we do care about e.g. attribute-tainting being
121        // different.
122        {
123            let own = self.own_properties.as_slice();
124            let other = other.own_properties.as_slice();
125            if own.len() != other.len() {
126                return false;
127            }
128            for ((own_k, own_v), (other_k, other_v)) in own.iter().zip(other.iter()) {
129                if own_k != other_k || !can_deduplicate_values(own_v.as_ref(), other_v.as_ref()) {
130                    return false;
131                }
132            }
133        }
134        self.parent == other.parent
135    }
136}
137
138impl Inner {
139    fn iter(&self) -> Iter<'_> {
140        Iter {
141            current: self,
142            current_iter: self.own_properties.iter(),
143            descendants: Default::default(),
144        }
145    }
146
147    fn is_empty(&self) -> bool {
148        self.len == 0
149    }
150
151    fn len(&self) -> usize {
152        self.len
153    }
154
155    fn get(&self, name: &Name) -> Option<&ComputedRegisteredValue> {
156        if let Some(p) = self.own_properties.get(name) {
157            return p.as_ref();
158        }
159        self.parent.as_ref()?.get(name)
160    }
161
162    fn insert(&mut self, name: &Name, value: Option<ComputedRegisteredValue>) {
163        let new = self.own_properties.insert(name.clone(), value).is_none();
164        if new && self.parent.as_ref().is_none_or(|p| p.get(name).is_none()) {
165            self.len += 1;
166        }
167    }
168
169    /// Whether we should expand the chain, or just copy-on-write.
170    fn should_expand_chain(&self) -> bool {
171        const SMALL_THRESHOLD: usize = 8;
172        if self.own_properties.len() <= SMALL_THRESHOLD {
173            return false; // Just copy, to avoid very long chains.
174        }
175        self.ancestor_count < ANCESTOR_COUNT_LIMIT as u8
176    }
177}
178
179impl CustomPropertiesMap {
180    /// Returns whether the map has no properties in it.
181    pub fn is_empty(&self) -> bool {
182        self.0.is_empty()
183    }
184
185    /// Returns the amount of different properties in the map.
186    pub fn len(&self) -> usize {
187        self.0.len()
188    }
189
190    /// Returns the property name and value at a given index.
191    pub fn get_index(&self, index: usize) -> Option<(&Name, &Option<ComputedRegisteredValue>)> {
192        if index >= self.len() {
193            return None;
194        }
195        // FIXME: This is O(n) which is a bit unfortunate.
196        self.0.iter().nth(index)
197    }
198
199    /// Returns a given property value by name.
200    pub fn get(&self, name: &Name) -> Option<&ComputedRegisteredValue> {
201        self.0.get(name)
202    }
203
204    fn do_insert(&mut self, name: &Name, value: Option<ComputedRegisteredValue>) {
205        if let Some(inner) = Arc::get_mut(&mut self.0) {
206            return inner.insert(name, value);
207        }
208        if self.get(name) == value.as_ref() {
209            return;
210        }
211        if !self.0.should_expand_chain() {
212            return Arc::make_mut(&mut self.0).insert(name, value);
213        }
214        let len = self.0.len;
215        let ancestor_count = self.0.ancestor_count + 1;
216        let mut new_inner = Inner {
217            own_properties: Default::default(),
218            // FIXME: Would be nice to avoid this clone.
219            parent: Some(self.0.clone()),
220            len,
221            ancestor_count,
222        };
223        new_inner.insert(name, value);
224        self.0 = Arc::new(new_inner);
225    }
226
227    /// Inserts an element in the map.
228    pub fn insert(&mut self, name: &Name, value: ComputedRegisteredValue) {
229        self.do_insert(name, Some(value))
230    }
231
232    /// Removes an element from the map.
233    pub fn remove(&mut self, name: &Name) {
234        self.do_insert(name, None)
235    }
236
237    /// Shrinks the map as much as possible.
238    pub fn shrink_to_fit(&mut self) {
239        if let Some(inner) = Arc::get_mut(&mut self.0) {
240            inner.own_properties.shrink_to_fit()
241        }
242    }
243
244    /// Return iterator to go through all properties.
245    pub fn iter(&self) -> Iter<'_> {
246        self.0.iter()
247    }
248}
style/custom_properties_map.rs

style/
custom_properties_map.rs
