From 12be8fe070d6c3b0ef04c744ba300063f30791cf Mon Sep 17 00:00:00 2001
From: Laurenz <laurmaedje@gmail.com>
Date: Tue, 11 Apr 2023 21:54:47 +0200
Subject: Let dictionaries respect insertion order

---
 src/eval/dict.rs  | 28 ++++++++++++++++++++--------
 src/eval/mod.rs   |  4 ++--
 src/eval/value.rs |  2 +-
 3 files changed, 23 insertions(+), 11 deletions(-)

(limited to 'src/eval')

diff --git a/src/eval/dict.rs b/src/eval/dict.rs
index 4333a55e..b137f03c 100644
--- a/src/eval/dict.rs
+++ b/src/eval/dict.rs
@@ -1,5 +1,5 @@
-use std::collections::BTreeMap;
 use std::fmt::{self, Debug, Formatter};
+use std::hash::{Hash, Hasher};
 use std::ops::{Add, AddAssign};
 use std::sync::Arc;
 
@@ -16,7 +16,7 @@ use crate::util::{pretty_array_like, separated_list, ArcExt};
 macro_rules! __dict {
     ($($key:expr => $value:expr),* $(,)?) => {{
         #[allow(unused_mut)]
-        let mut map = std::collections::BTreeMap::new();
+        let mut map = $crate::eval::IndexMap::new();
         $(map.insert($key.into(), $value.into());)*
         $crate::eval::Dict::from_map(map)
     }};
@@ -25,9 +25,12 @@ macro_rules! __dict {
 #[doc(inline)]
 pub use crate::__dict as dict;
 
+#[doc(inline)]
+pub use indexmap::IndexMap;
+
 /// A reference-counted dictionary with value semantics.
-#[derive(Default, Clone, PartialEq, Hash)]
-pub struct Dict(Arc<BTreeMap<Str, Value>>);
+#[derive(Default, Clone, PartialEq)]
+pub struct Dict(Arc<IndexMap<Str, Value>>);
 
 impl Dict {
     /// Create a new, empty dictionary.
@@ -36,7 +39,7 @@ impl Dict {
     }
 
     /// Create a new dictionary from a mapping of strings to values.
-    pub fn from_map(map: BTreeMap<Str, Value>) -> Self {
+    pub fn from_map(map: IndexMap<Str, Value>) -> Self {
         Self(Arc::new(map))
     }
 
@@ -116,7 +119,7 @@ impl Dict {
     }
 
     /// Iterate over pairs of references to the contained keys and values.
-    pub fn iter(&self) -> std::collections::btree_map::Iter<Str, Value> {
+    pub fn iter(&self) -> indexmap::map::Iter<Str, Value> {
         self.0.iter()
     }
 
@@ -171,6 +174,15 @@ impl AddAssign for Dict {
     }
 }
 
+impl Hash for Dict {
+    fn hash<H: Hasher>(&self, state: &mut H) {
+        state.write_usize(self.0.len());
+        for item in self {
+            item.hash(state);
+        }
+    }
+}
+
 impl Extend<(Str, Value)> for Dict {
     fn extend<T: IntoIterator<Item = (Str, Value)>>(&mut self, iter: T) {
         Arc::make_mut(&mut self.0).extend(iter);
@@ -185,7 +197,7 @@ impl FromIterator<(Str, Value)> for Dict {
 
 impl IntoIterator for Dict {
     type Item = (Str, Value);
-    type IntoIter = std::collections::btree_map::IntoIter<Str, Value>;
+    type IntoIter = indexmap::map::IntoIter<Str, Value>;
 
     fn into_iter(self) -> Self::IntoIter {
         Arc::take(self.0).into_iter()
@@ -194,7 +206,7 @@ impl IntoIterator for Dict {
 
 impl<'a> IntoIterator for &'a Dict {
     type Item = (&'a Str, &'a Value);
-    type IntoIter = std::collections::btree_map::Iter<'a, Str, Value>;
+    type IntoIter = indexmap::map::Iter<'a, Str, Value>;
 
     fn into_iter(self) -> Self::IntoIter {
         self.iter()
diff --git a/src/eval/mod.rs b/src/eval/mod.rs
index 55d2a734..5a450481 100644
--- a/src/eval/mod.rs
+++ b/src/eval/mod.rs
@@ -37,7 +37,7 @@ pub use self::value::*;
 
 pub(crate) use self::methods::methods_on;
 
-use std::collections::{BTreeMap, HashSet};
+use std::collections::HashSet;
 use std::mem;
 use std::path::{Path, PathBuf};
 
@@ -870,7 +870,7 @@ impl Eval for ast::Dict {
     type Output = Dict;
 
     fn eval(&self, vm: &mut Vm) -> SourceResult<Self::Output> {
-        let mut map = BTreeMap::new();
+        let mut map = indexmap::IndexMap::new();
 
         for item in self.items() {
             match item {
diff --git a/src/eval/value.rs b/src/eval/value.rs
index b8a51c70..3fd9ed42 100644
--- a/src/eval/value.rs
+++ b/src/eval/value.rs
@@ -444,6 +444,6 @@ mod tests {
         test(array![1, 2], "(1, 2)");
         test(dict![], "(:)");
         test(dict!["one" => 1], "(one: 1)");
-        test(dict!["two" => false, "one" => 1], "(one: 1, two: false)");
+        test(dict!["two" => false, "one" => 1], "(two: false, one: 1)");
     }
 }
-- 
cgit v1.2.3