Bug 1519269 - Remove OrderedMap in favor of IndexMap. r=emilio
authorShanavas M <shanavas.m2@gmail.com>
Fri, 11 Jan 2019 00:57:02 +0100
changeset 453288 0770b6410aea11196e85c01c7cbef19131c6369b
parent 453287 0801165e31759dfe84480650d254924336e4fe76
child 453289 a8ae7a84f300a5045b9516d5d426dd66614f7e21
push id111079
push useremilio@crisal.io
push dateFri, 11 Jan 2019 00:03:13 +0000
treeherdermozilla-inbound@a8ae7a84f300 [default view] [failures only]
perfherder[talos] [build metrics] [platform microbench] (compared to previous push)
reviewersemilio
bugs1519269, 22656
milestone66.0a1
first release with
nightly linux32
nightly linux64
nightly mac
nightly win32
nightly win64
last release without
nightly linux32
nightly linux64
nightly mac
nightly win32
nightly win64
Bug 1519269 - Remove OrderedMap in favor of IndexMap. r=emilio This cherry-picks https://github.com/servo/servo/pull/22656.
Cargo.lock
servo/components/style/Cargo.toml
servo/components/style/custom_properties.rs
servo/components/style/lib.rs
servo/ports/geckolib/glue.rs
--- a/Cargo.lock
+++ b/Cargo.lock
@@ -2420,16 +2420,17 @@ dependencies = [
  "bindgen 0.43.0 (registry+https://github.com/rust-lang/crates.io-index)",
  "bitflags 1.0.4 (registry+https://github.com/rust-lang/crates.io-index)",
  "byteorder 1.2.7 (registry+https://github.com/rust-lang/crates.io-index)",
  "cssparser 0.25.0 (registry+https://github.com/rust-lang/crates.io-index)",
  "euclid 0.19.4 (registry+https://github.com/rust-lang/crates.io-index)",
  "fallible 0.0.1",
  "fxhash 0.2.1 (registry+https://github.com/rust-lang/crates.io-index)",
  "hashglobe 0.1.0",
+ "indexmap 1.0.1 (registry+https://github.com/rust-lang/crates.io-index)",
  "itertools 0.7.6 (registry+https://github.com/rust-lang/crates.io-index)",
  "itoa 0.4.1 (registry+https://github.com/rust-lang/crates.io-index)",
  "lazy_static 1.0.1 (registry+https://github.com/rust-lang/crates.io-index)",
  "log 0.4.5 (registry+https://github.com/rust-lang/crates.io-index)",
  "malloc_size_of 0.0.1",
  "malloc_size_of_derive 0.0.1",
  "matches 0.1.6 (registry+https://github.com/rust-lang/crates.io-index)",
  "new_debug_unreachable 1.0.1 (registry+https://github.com/rust-lang/crates.io-index)",
--- a/servo/components/style/Cargo.toml
+++ b/servo/components/style/Cargo.toml
@@ -33,16 +33,17 @@ cssparser = "0.25"
 crossbeam-channel = { version = "0.3", optional = true }
 new_debug_unreachable = "1.0"
 encoding_rs = {version = "0.8", optional = true}
 euclid = "0.19"
 fallible = { path = "../fallible" }
 fxhash = "0.2"
 hashglobe = { path = "../hashglobe" }
 html5ever = {version = "0.22", optional = true}
+indexmap = "1.0"
 itertools = "0.7.6"
 itoa = "0.4"
 lazy_static = "1"
 log = "0.4"
 malloc_size_of = { path = "../malloc_size_of" }
 malloc_size_of_derive = { path = "../malloc_size_of_derive" }
 matches = "0.1"
 nsstring = {path = "../../../xpcom/rust/nsstring/", optional = true}
--- a/servo/components/style/custom_properties.rs
+++ b/servo/components/style/custom_properties.rs
@@ -3,27 +3,27 @@
  * file, You can obtain one at https://mozilla.org/MPL/2.0/. */
 
 //! Support for [custom properties for cascading variables][custom].
 //!
 //! [custom]: https://drafts.csswg.org/css-variables/
 
 use crate::hash::map::Entry;
 use crate::properties::{CSSWideKeyword, CustomDeclarationValue};
-use crate::selector_map::{PrecomputedHashMap, PrecomputedHashSet};
+use crate::selector_map::{PrecomputedHashMap, PrecomputedHashSet, PrecomputedHasher};
 use crate::Atom;
 use cssparser::{Delimiter, Parser, ParserInput, SourcePosition, Token, TokenSerializationType};
-use precomputed_hash::PrecomputedHash;
+use indexmap::IndexMap;
 use selectors::parser::SelectorParseErrorKind;
 use servo_arc::Arc;
 use smallvec::SmallVec;
-use std::borrow::{Borrow, Cow};
+use std::borrow::Cow;
 use std::cmp;
 use std::fmt::{self, Write};
-use std::hash::Hash;
+use std::hash::BuildHasherDefault;
 use style_traits::{CssWriter, ParseError, StyleParseErrorKind, ToCss};
 
 /// The environment from which to get `env` function values.
 ///
 /// TODO(emilio): If this becomes a bit more complex we should probably move it
 /// to the `media_queries` module, or something.
 #[derive(Debug, MallocSizeOf)]
 pub struct CssEnvironment;
@@ -126,149 +126,26 @@ impl ToCss for SpecifiedValue {
 ///
 /// A consistent ordering is required for CSSDeclaration objects in the
 /// DOM. CSSDeclarations expose property names as indexed properties, which
 /// need to be stable. So we keep an array of property names which order is
 /// determined on the order that they are added to the name-value map.
 ///
 /// The variable values are guaranteed to not have references to other
 /// properties.
-pub type CustomPropertiesMap = OrderedMap<Name, Arc<VariableValue>>;
+pub type CustomPropertiesMap =
+    IndexMap<Name, Arc<VariableValue>, BuildHasherDefault<PrecomputedHasher>>;
 
 /// Both specified and computed values are VariableValues, the difference is
 /// whether var() functions are expanded.
 pub type SpecifiedValue = VariableValue;
 /// Both specified and computed values are VariableValues, the difference is
 /// whether var() functions are expanded.
 pub type ComputedValue = VariableValue;
 
-/// A map that preserves order for the keys, and that is easily indexable.
-#[derive(Clone, Debug, Eq, PartialEq)]
-pub struct OrderedMap<K, V>
-where
-    K: PrecomputedHash + Hash + Eq + Clone,
-{
-    /// Key index.
-    index: Vec<K>,
-    /// Key-value map.
-    values: PrecomputedHashMap<K, V>,
-}
-
-impl<K, V> OrderedMap<K, V>
-where
-    K: Eq + PrecomputedHash + Hash + Clone,
-{
-    /// Creates a new ordered map.
-    pub fn new() -> Self {
-        OrderedMap {
-            index: Vec::new(),
-            values: PrecomputedHashMap::default(),
-        }
-    }
-
-    /// Insert a new key-value pair.
-    ///
-    /// TODO(emilio): Remove unused_mut when Gecko and Servo agree in whether
-    /// it's necessary.
-    #[allow(unused_mut)]
-    pub fn insert(&mut self, key: K, value: V) {
-        let OrderedMap {
-            ref mut index,
-            ref mut values,
-        } = *self;
-        match values.entry(key) {
-            Entry::Vacant(mut entry) => {
-                index.push(entry.key().clone());
-                entry.insert(value);
-            },
-            Entry::Occupied(mut entry) => {
-                entry.insert(value);
-            },
-        }
-    }
-
-    /// Get a value given its key.
-    pub fn get(&self, key: &K) -> Option<&V> {
-        let value = self.values.get(key);
-        debug_assert_eq!(value.is_some(), self.index.contains(key));
-        value
-    }
-
-    /// Get whether there's a value on the map for `key`.
-    pub fn contains_key(&self, key: &K) -> bool {
-        self.values.contains_key(key)
-    }
-
-    /// Get the key located at the given index.
-    pub fn get_key_at(&self, index: u32) -> Option<&K> {
-        self.index.get(index as usize)
-    }
-
-    /// Get an ordered map iterator.
-    pub fn iter<'a>(&'a self) -> OrderedMapIterator<'a, K, V> {
-        OrderedMapIterator {
-            inner: self,
-            pos: 0,
-        }
-    }
-
-    /// Get the count of items in the map.
-    pub fn len(&self) -> usize {
-        debug_assert_eq!(self.values.len(), self.index.len());
-        self.values.len()
-    }
-
-    /// Returns whether this map is empty.
-    pub fn is_empty(&self) -> bool {
-        self.len() == 0
-    }
-
-    /// Remove an item given its key.
-    fn remove<Q: ?Sized>(&mut self, key: &Q) -> Option<V>
-    where
-        K: Borrow<Q>,
-        Q: PrecomputedHash + Hash + Eq,
-    {
-        let index = self.index.iter().position(|k| k.borrow() == key)?;
-        self.index.remove(index);
-        self.values.remove(key)
-    }
-}
-
-/// An iterator for OrderedMap.
-///
-/// The iteration order is determined by the order that the values are
-/// added to the key-value map.
-pub struct OrderedMapIterator<'a, K, V>
-where
-    K: 'a + Eq + PrecomputedHash + Hash + Clone,
-    V: 'a,
-{
-    /// The OrderedMap itself.
-    inner: &'a OrderedMap<K, V>,
-    /// The position of the iterator.
-    pos: usize,
-}
-
-impl<'a, K, V> Iterator for OrderedMapIterator<'a, K, V>
-where
-    K: Eq + PrecomputedHash + Hash + Clone,
-{
-    type Item = (&'a K, &'a V);
-
-    fn next(&mut self) -> Option<Self::Item> {
-        let key = self.inner.index.get(self.pos)?;
-
-        self.pos += 1;
-        let value = &self.inner.values[key];
-
-        Some((key, value))
-    }
-}
-
 /// A struct holding information about the external references to that a custom
 /// property value may have.
 #[derive(Default)]
 struct VarOrEnvReferences {
     custom_property_references: PrecomputedHashSet<Name>,
     references_environment: bool,
 }
 
@@ -643,17 +520,17 @@ impl<'a> CustomPropertiesBuilder<'a> {
 
         if !self.value_may_affect_style(name, specified_value) {
             return;
         }
 
         if self.custom_properties.is_none() {
             self.custom_properties = Some(match self.inherited {
                 Some(inherited) => (**inherited).clone(),
-                None => CustomPropertiesMap::new(),
+                None => CustomPropertiesMap::default(),
             });
         }
 
         let map = self.custom_properties.as_mut().unwrap();
         match *specified_value {
             CustomDeclarationValue::Value(ref unparsed_value) => {
                 let has_references = !unparsed_value.references.is_empty();
                 self.may_have_cycles |= has_references;
@@ -928,17 +805,17 @@ fn substitute_all(custom_properties_map:
         }
 
         // All resolved, so return the signal value.
         None
     }
 
     // We have to clone the names so that we can mutably borrow the map
     // in the context we create for traversal.
-    let names = custom_properties_map.index.clone();
+    let names: Vec<_> = custom_properties_map.keys().cloned().collect();
     for name in names.into_iter() {
         let mut context = Context {
             count: 0,
             index_map: PrecomputedHashMap::default(),
             stack: SmallVec::new(),
             var_info: SmallVec::new(),
             map: custom_properties_map,
             environment,
@@ -1107,17 +984,17 @@ pub fn substitute<'i>(
     first_token_type: TokenSerializationType,
     computed_values_map: Option<&Arc<CustomPropertiesMap>>,
     env: &CssEnvironment,
 ) -> Result<String, ParseError<'i>> {
     let mut substituted = ComputedValue::empty();
     let mut input = ParserInput::new(input);
     let mut input = Parser::new(&mut input);
     let mut position = (input.position(), first_token_type);
-    let empty_map = CustomPropertiesMap::new();
+    let empty_map = CustomPropertiesMap::default();
     let custom_properties = match computed_values_map {
         Some(m) => &**m,
         None => &empty_map,
     };
     let last_token_type = substitute_block(
         &mut input,
         &mut position,
         &mut substituted,
--- a/servo/components/style/lib.rs
+++ b/servo/components/style/lib.rs
@@ -43,16 +43,17 @@ extern crate fallible;
 extern crate fxhash;
 #[cfg(feature = "gecko")]
 #[macro_use]
 pub mod gecko_string_cache;
 extern crate hashglobe;
 #[cfg(feature = "servo")]
 #[macro_use]
 extern crate html5ever;
+extern crate indexmap;
 extern crate itertools;
 extern crate itoa;
 #[macro_use]
 extern crate lazy_static;
 #[macro_use]
 extern crate log;
 #[macro_use]
 extern crate malloc_size_of;
--- a/servo/ports/geckolib/glue.rs
+++ b/servo/ports/geckolib/glue.rs
@@ -5787,18 +5787,18 @@ pub extern "C" fn Servo_GetCustomPropert
     index: u32,
     name: *mut nsAString,
 ) -> bool {
     let custom_properties = match computed_values.custom_properties() {
         Some(p) => p,
         None => return false,
     };
 
-    let property_name = match custom_properties.get_key_at(index) {
-        Some(n) => n,
+    let property_name = match custom_properties.get_index(index as usize) {
+        Some((key, _value)) => key,
         None => return false,
     };
 
     let name = unsafe { name.as_mut().unwrap() };
     name.assign(&*property_name.as_slice());
 
     true
 }