cairo_lang_utils/
ordered_hash_map.rs

1use core::hash::{BuildHasher, Hash};
2
3use indexmap::IndexMap;
4use itertools::zip_eq;
5
6// hashbrown's default hasher (foldhash) rather than std's SipHash. IndexMap/IndexSet iterate in
7// insertion order, so the iteration order -- and thus compilation determinism -- is independent of
8// the hasher.
9type BHImpl = hashbrown::DefaultHashBuilder;
10
11#[derive(Clone, Debug)]
12#[cfg_attr(
13    feature = "serde",
14    derive(serde::Deserialize, serde::Serialize),
15    serde(transparent),
16    serde(bound(
17        serialize = "Key: serde::Serialize, Value: serde::Serialize",
18        deserialize = "Key: serde::Deserialize<'de> + Hash + Eq, Value: serde::Deserialize<'de>, \
19                       BH: BuildHasher + Default"
20    ))
21)]
22pub struct OrderedHashMap<Key, Value, BH = BHImpl>(IndexMap<Key, Value, BH>);
23
24impl<Key, Value, BH> core::ops::Deref for OrderedHashMap<Key, Value, BH> {
25    type Target = IndexMap<Key, Value, BH>;
26
27    fn deref(&self) -> &Self::Target {
28        &self.0
29    }
30}
31
32impl<Key, Value, BH> core::ops::DerefMut for OrderedHashMap<Key, Value, BH> {
33    fn deref_mut(&mut self) -> &mut Self::Target {
34        &mut self.0
35    }
36}
37
38#[cfg(feature = "salsa")]
39unsafe impl<Key: salsa::SalsaValue + Eq + Hash, Value: salsa::SalsaValue, BH: BuildHasher>
40    salsa::SalsaValue for OrderedHashMap<Key, Value, BH>
41{
42}
43
44impl<Key, Value, BH: Default> Default for OrderedHashMap<Key, Value, BH> {
45    #[cfg(feature = "std")]
46    fn default() -> Self {
47        Self(Default::default())
48    }
49    #[cfg(not(feature = "std"))]
50    fn default() -> Self {
51        Self(IndexMap::with_hasher(Default::default()))
52    }
53}
54
55impl<Key, Value, BH> OrderedHashMap<Key, Value, BH> {
56    /// Returns true if the map contains no elements.
57    pub fn is_empty(&self) -> bool {
58        self.0.is_empty()
59    }
60}
61
62impl<Key, Value, BH: BuildHasher + Default> OrderedHashMap<Key, Value, BH> {
63    /// Creates an empty `OrderedHashMap` with the specified capacity.
64    pub fn with_capacity(capacity: usize) -> Self {
65        Self(IndexMap::with_capacity_and_hasher(capacity, Default::default()))
66    }
67}
68
69impl<Key: Eq + Hash, Value, BH: BuildHasher> OrderedHashMap<Key, Value, BH> {
70    /// Returns true if the maps are equal, ignoring the order of the entries.
71    pub fn eq_unordered(&self, other: &Self) -> bool
72    where
73        Value: Eq,
74    {
75        if self.len() != other.len() {
76            return false;
77        };
78        self.iter().all(|(k, v)| other.get(k) == Some(v))
79    }
80}
81
82/// Entry for an existing key-value pair or a vacant location to insert one.
83pub type Entry<'a, Key, Value> = indexmap::map::Entry<'a, Key, Value>;
84
85impl<Key, Value, BH> IntoIterator for OrderedHashMap<Key, Value, BH> {
86    type Item = (Key, Value);
87    type IntoIter = indexmap::map::IntoIter<Key, Value>;
88    fn into_iter(self) -> Self::IntoIter {
89        let OrderedHashMap(inner) = self;
90        inner.into_iter()
91    }
92}
93
94impl<Key: Eq, Value: Eq, BH> PartialEq for OrderedHashMap<Key, Value, BH> {
95    fn eq(&self, other: &Self) -> bool {
96        if self.len() != other.len() {
97            return false;
98        };
99
100        zip_eq(self.iter(), other.iter()).all(|(a, b)| a == b)
101    }
102}
103
104impl<Key: Hash + Eq, Value: Eq, BH: BuildHasher> Eq for OrderedHashMap<Key, Value, BH> {}
105
106impl<Key: Hash, Value: Hash, BH> Hash for OrderedHashMap<Key, Value, BH> {
107    fn hash<H: core::hash::Hasher>(&self, state: &mut H) {
108        self.len().hash(state);
109        for e in self.iter() {
110            e.hash(state);
111        }
112    }
113}
114
115impl<Key: Hash + Eq, Value, BH: BuildHasher + Default> FromIterator<(Key, Value)>
116    for OrderedHashMap<Key, Value, BH>
117{
118    fn from_iter<T: IntoIterator<Item = (Key, Value)>>(iter: T) -> Self {
119        Self(iter.into_iter().collect())
120    }
121}
122
123impl<Key: Hash + Eq, Value, BH: BuildHasher + Default, const N: usize> From<[(Key, Value); N]>
124    for OrderedHashMap<Key, Value, BH>
125{
126    fn from(init_map: [(Key, Value); N]) -> Self {
127        Self(IndexMap::from_iter(init_map))
128    }
129}
130
131#[cfg(feature = "serde")]
132mod impl_serde {
133    use indexmap::map::serde_seq;
134    use serde::{Deserialize, Deserializer, Serialize, Serializer};
135
136    use super::*;
137
138    pub fn serialize_ordered_hashmap_vec<K, V, BH, S>(
139        v: &OrderedHashMap<K, V, BH>,
140        serializer: S,
141    ) -> Result<S::Ok, S::Error>
142    where
143        S: Serializer,
144        K: Serialize + Hash + Eq,
145        V: Serialize,
146    {
147        serde_seq::serialize(&v.0, serializer)
148    }
149
150    pub fn deserialize_ordered_hashmap_vec<'de, K, V, BH: BuildHasher + Default, D>(
151        deserializer: D,
152    ) -> Result<OrderedHashMap<K, V, BH>, D::Error>
153    where
154        D: Deserializer<'de>,
155        K: Deserialize<'de> + Hash + Eq,
156        V: Deserialize<'de>,
157    {
158        Ok(OrderedHashMap(serde_seq::deserialize(deserializer)?))
159    }
160}
161#[cfg(feature = "serde")]
162pub use impl_serde::*;
cairo_lang_utils/ordered_hash_map.rs

cairo_lang_utils/
ordered_hash_map.rs
