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

style/
custom_properties_map.rs
