From 26a029d407be480d791972afb5975cf62c9360a6 Mon Sep 17 00:00:00 2001 From: Daniel Baumann Date: Fri, 19 Apr 2024 02:47:55 +0200 Subject: Adding upstream version 124.0.1. Signed-off-by: Daniel Baumann --- servo/components/style/custom_properties_map.rs | 237 ++++++++++++++++++++++++ 1 file changed, 237 insertions(+) create mode 100644 servo/components/style/custom_properties_map.rs (limited to 'servo/components/style/custom_properties_map.rs') diff --git a/servo/components/style/custom_properties_map.rs b/servo/components/style/custom_properties_map.rs new file mode 100644 index 0000000000..04ca8e1b3d --- /dev/null +++ b/servo/components/style/custom_properties_map.rs @@ -0,0 +1,237 @@ +/* This Source Code Form is subject to the terms of the Mozilla Public + * License, v. 2.0. If a copy of the MPL was not distributed with this + * file, You can obtain one at https://mozilla.org/MPL/2.0/. */ + +//! The structure that contains the custom properties of a given element. + +use crate::custom_properties::{Name, VariableValue}; +use crate::selector_map::PrecomputedHasher; +use indexmap::IndexMap; +use servo_arc::Arc; +use std::hash::BuildHasherDefault; + +/// A map for a set of custom properties, which implements copy-on-write behavior on insertion with +/// cheap copying. +#[derive(Clone, Debug, PartialEq)] +pub struct CustomPropertiesMap(Arc); + +impl Default for CustomPropertiesMap { + fn default() -> Self { + Self(EMPTY.clone()) + } +} + +/// We use None in the value to represent a removed entry. +type OwnMap = IndexMap>, BuildHasherDefault>; + +// IndexMap equality doesn't consider ordering, which we want to account for. Also, for the same +// reason, IndexMap equality comparisons are slower than needed. +// +// See https://github.com/bluss/indexmap/issues/153. +// TODO: use as_slice when updating to indexmap 2.0. +fn maps_equal(l: &OwnMap, r: &OwnMap) -> bool { + if std::ptr::eq(l, r) { + return true; + } + if l.len() != r.len() { + return false; + } + l.iter() + .zip(r.iter()) + .all(|((k1, v1), (k2, v2))| k1 == k2 && v1 == v2) +} + +lazy_static! { + static ref EMPTY: Arc = { + Arc::new_leaked(Inner { + own_properties: Default::default(), + parent: None, + len: 0, + ancestor_count: 0, + }) + }; +} + +#[derive(Debug, Clone)] +struct Inner { + own_properties: OwnMap, + parent: Option>, + /// The number of custom properties we store. Note that this is different from the sum of our + /// own and our parent's length, since we might store duplicate entries. + len: usize, + /// The number of ancestors we have. + ancestor_count: u8, +} + +/// A not-too-large, not too small ancestor limit, to prevent creating too-big chains. +const ANCESTOR_COUNT_LIMIT: usize = 4; + +/// An iterator over the custom properties. +pub struct Iter<'a> { + current: &'a Inner, + current_iter: indexmap::map::Iter<'a, Name, Option>>, + descendants: smallvec::SmallVec<[&'a Inner; ANCESTOR_COUNT_LIMIT]>, +} + +impl<'a> Iterator for Iter<'a> { + type Item = (&'a Name, &'a Option>); + + fn next(&mut self) -> Option { + loop { + let (name, value) = match self.current_iter.next() { + Some(v) => v, + None => { + let parent = self.current.parent.as_deref()?; + self.descendants.push(self.current); + self.current = parent; + self.current_iter = parent.own_properties.iter(); + continue; + }, + }; + // If the property is overridden by a descendant we've already visited it. + for descendant in &self.descendants { + if descendant.own_properties.contains_key(name) { + continue; + } + } + return Some((name, value)); + } + } +} + +impl PartialEq for Inner { + fn eq(&self, other: &Self) -> bool { + if self.len != other.len { + return false; + } + if self.parent_ptr_eq(other) { + return maps_equal(&self.own_properties, &other.own_properties); + } + for (name, value) in self.iter() { + if other.get(name) != value.as_ref() { + return false; + } + } + return true; + } +} + +impl Inner { + fn parent_ptr_eq(&self, other: &Self) -> bool { + match (&self.parent, &other.parent) { + (Some(p1), Some(p2)) => Arc::ptr_eq(p1, p2), + (None, None) => true, + _ => false, + } + } + + fn iter(&self) -> Iter { + Iter { + current: self, + current_iter: self.own_properties.iter(), + descendants: Default::default(), + } + } + + fn is_empty(&self) -> bool { + self.len == 0 + } + + fn len(&self) -> usize { + self.len + } + + fn get(&self, name: &Name) -> Option<&Arc> { + if let Some(p) = self.own_properties.get(name) { + return p.as_ref(); + } + self.parent.as_ref()?.get(name) + } + + fn insert(&mut self, name: &Name, value: Option>) { + let new = self.own_properties.insert(name.clone(), value).is_none(); + if new && self.parent.as_ref().map_or(true, |p| p.get(name).is_none()) { + self.len += 1; + } + } + + /// Whether we should expand the chain, or just copy-on-write. + fn should_expand_chain(&self) -> bool { + const SMALL_THRESHOLD: usize = 8; + if self.own_properties.len() <= SMALL_THRESHOLD { + return false; // Just copy, to avoid very long chains. + } + self.ancestor_count < ANCESTOR_COUNT_LIMIT as u8 + } +} + +impl CustomPropertiesMap { + /// Returns whether the map has no properties in it. + pub fn is_empty(&self) -> bool { + self.0.is_empty() + } + + /// Returns the amount of different properties in the map. + pub fn len(&self) -> usize { + self.0.len() + } + + /// Returns the property name and value at a given index. + pub fn get_index(&self, index: usize) -> Option<(&Name, &Option>)> { + if index >= self.len() { + return None; + } + // FIXME: This is O(n) which is a bit unfortunate. + self.0.iter().nth(index) + } + + /// Returns a given property value by name. + pub fn get(&self, name: &Name) -> Option<&Arc> { + self.0.get(name) + } + + fn do_insert(&mut self, name: &Name, value: Option>) { + if let Some(inner) = Arc::get_mut(&mut self.0) { + return inner.insert(name, value); + } + if self.get(name) == value.as_ref() { + return; + } + if !self.0.should_expand_chain() { + return Arc::make_mut(&mut self.0).insert(name, value); + } + let len = self.0.len; + let ancestor_count = self.0.ancestor_count + 1; + let mut new_inner = Inner { + own_properties: Default::default(), + // FIXME: Would be nice to avoid this clone. + parent: Some(self.0.clone()), + len, + ancestor_count, + }; + new_inner.insert(name, value); + self.0 = Arc::new(new_inner); + } + + /// Inserts an element in the map. + pub fn insert(&mut self, name: &Name, value: Arc) { + self.do_insert(name, Some(value)) + } + + /// Removes an element from the map. + pub fn remove(&mut self, name: &Name) { + self.do_insert(name, None) + } + + /// Shrinks the map as much as possible. + pub fn shrink_to_fit(&mut self) { + if let Some(inner) = Arc::get_mut(&mut self.0) { + inner.own_properties.shrink_to_fit() + } + } + + /// Return iterator to go through all properties. + pub fn iter(&self) -> Iter { + self.0.iter() + } +} -- cgit v1.2.3