cairo_lang_utils/
ordered_hash_map.rs

1use core::hash::{BuildHasher, Hash};
2#[cfg(feature = "std")]
3use std::collections::hash_map::RandomState;
4
5use indexmap::IndexMap;
6use itertools::zip_eq;
7
8#[cfg(feature = "std")]
9type BHImpl = RandomState;
10#[cfg(not(feature = "std"))]
11type BHImpl = hashbrown::DefaultHashBuilder;
12
13#[derive(Clone, Debug)]
14pub struct OrderedHashMap<Key, Value, BH = BHImpl>(IndexMap<Key, Value, BH>);
15
16impl<Key, Value, BH> core::ops::Deref for OrderedHashMap<Key, Value, BH> {
17    type Target = IndexMap<Key, Value, BH>;
18
19    fn deref(&self) -> &Self::Target {
20        &self.0
21    }
22}
23
24impl<Key, Value, BH> core::ops::DerefMut for OrderedHashMap<Key, Value, BH> {
25    fn deref_mut(&mut self) -> &mut Self::Target {
26        &mut self.0
27    }
28}
29
30#[cfg(feature = "salsa")]
31unsafe impl<Key: salsa::Update + Eq + Hash, Value: salsa::Update> salsa::Update
32    for OrderedHashMap<Key, Value, BHImpl>
33{
34    // This code was taken from the salsa::Update trait implementation for IndexMap.
35    // It is defined privately in macro_rules! maybe_update_map in the db-ext-macro repo.
36    unsafe fn maybe_update(old_pointer: *mut Self, new_map: Self) -> bool {
37        let new_map = new_map;
38        let old_map: &mut Self = unsafe { &mut *old_pointer };
39
40        // To be considered "equal", the set of keys
41        // must be the same between the two maps.
42        let same_keys =
43            old_map.len() == new_map.len() && old_map.keys().all(|k| new_map.contains_key(k));
44
45        // If the set of keys has changed, then just pull in the new values
46        // from new_map and discard the old ones.
47        if !same_keys {
48            old_map.clear();
49            old_map.extend(new_map);
50            return true;
51        }
52
53        // Otherwise, recursively descend to the values.
54        // We do not invoke `K::update` because we assume
55        // that if the values are `Eq` they must not need
56        // updating (see the trait criteria).
57        let mut changed = false;
58        for (key, new_value) in new_map.into_iter() {
59            let old_value = old_map.get_mut(&key).unwrap();
60            changed |= unsafe { Value::maybe_update(old_value, new_value) };
61        }
62        changed
63    }
64}
65
66impl<Key, Value, BH: Default> Default for OrderedHashMap<Key, Value, BH> {
67    #[cfg(feature = "std")]
68    fn default() -> Self {
69        Self(Default::default())
70    }
71    #[cfg(not(feature = "std"))]
72    fn default() -> Self {
73        Self(IndexMap::with_hasher(Default::default()))
74    }
75}
76
77impl<Key, Value, BH> OrderedHashMap<Key, Value, BH> {
78    /// Returns true if the map contains no elements.
79    pub fn is_empty(&self) -> bool {
80        self.0.is_empty()
81    }
82}
83
84impl<Key: Eq + Hash, Value, BH: BuildHasher> OrderedHashMap<Key, Value, BH> {
85    /// Returns true if the maps are equal, ignoring the order of the entries.
86    pub fn eq_unordered(&self, other: &Self) -> bool
87    where
88        Value: Eq,
89    {
90        if self.len() != other.len() {
91            return false;
92        };
93        self.iter().all(|(k, v)| other.get(k) == Some(v))
94    }
95}
96
97/// Entry for an existing key-value pair or a vacant location to insert one.
98pub type Entry<'a, Key, Value> = indexmap::map::Entry<'a, Key, Value>;
99
100impl<Key, Value, BH> IntoIterator for OrderedHashMap<Key, Value, BH> {
101    type Item = (Key, Value);
102    type IntoIter = indexmap::map::IntoIter<Key, Value>;
103    fn into_iter(self) -> Self::IntoIter {
104        let OrderedHashMap(inner) = self;
105        inner.into_iter()
106    }
107}
108
109impl<Key: Eq, Value: Eq, BH> PartialEq for OrderedHashMap<Key, Value, BH> {
110    fn eq(&self, other: &Self) -> bool {
111        if self.len() != other.len() {
112            return false;
113        };
114
115        zip_eq(self.iter(), other.iter()).all(|(a, b)| a == b)
116    }
117}
118
119impl<Key: Hash + Eq, Value: Eq, BH: BuildHasher> Eq for OrderedHashMap<Key, Value, BH> {}
120
121impl<Key: Hash, Value: Hash, BH> Hash for OrderedHashMap<Key, Value, BH> {
122    fn hash<H: core::hash::Hasher>(&self, state: &mut H) {
123        self.len().hash(state);
124        for e in self.iter() {
125            e.hash(state);
126        }
127    }
128}
129
130impl<Key: Hash + Eq, Value, BH: BuildHasher + Default> FromIterator<(Key, Value)>
131    for OrderedHashMap<Key, Value, BH>
132{
133    fn from_iter<T: IntoIterator<Item = (Key, Value)>>(iter: T) -> Self {
134        Self(iter.into_iter().collect())
135    }
136}
137
138impl<Key: Hash + Eq, Value, BH: BuildHasher + Default, const N: usize> From<[(Key, Value); N]>
139    for OrderedHashMap<Key, Value, BH>
140{
141    fn from(init_map: [(Key, Value); N]) -> Self {
142        Self(IndexMap::from_iter(init_map))
143    }
144}
145
146#[cfg(feature = "serde")]
147mod impl_serde {
148    #[cfg(not(feature = "std"))]
149    use alloc::vec::Vec;
150
151    use itertools::Itertools;
152    use serde::{Deserialize, Deserializer, Serialize, Serializer};
153
154    use super::*;
155
156    impl<K: Hash + Eq + Serialize, V: Serialize, BH: BuildHasher> Serialize
157        for OrderedHashMap<K, V, BH>
158    {
159        fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error>
160        where
161            S: Serializer,
162        {
163            self.0.serialize(serializer)
164        }
165    }
166
167    impl<'de, K: Hash + Eq + Deserialize<'de>, V: Deserialize<'de>, BH: BuildHasher + Default>
168        Deserialize<'de> for OrderedHashMap<K, V, BH>
169    {
170        fn deserialize<D: Deserializer<'de>>(deserializer: D) -> Result<Self, D::Error> {
171            IndexMap::<K, V, BH>::deserialize(deserializer).map(|s| OrderedHashMap(s))
172        }
173    }
174
175    pub fn serialize_ordered_hashmap_vec<'de, K, V, BH, S>(
176        v: &OrderedHashMap<K, V, BH>,
177        serializer: S,
178    ) -> Result<S::Ok, S::Error>
179    where
180        S: Serializer,
181        K: Serialize + Deserialize<'de> + Hash + Eq,
182        V: Serialize + Deserialize<'de>,
183    {
184        v.iter().collect_vec().serialize(serializer)
185    }
186
187    pub fn deserialize_ordered_hashmap_vec<'de, K, V, BH: BuildHasher + Default, D>(
188        deserializer: D,
189    ) -> Result<OrderedHashMap<K, V, BH>, D::Error>
190    where
191        D: Deserializer<'de>,
192        K: Serialize + Deserialize<'de> + Hash + Eq,
193        V: Serialize + Deserialize<'de>,
194    {
195        Ok(Vec::<(K, V)>::deserialize(deserializer)?.into_iter().collect())
196    }
197}
198#[cfg(feature = "serde")]
199pub use impl_serde::*;
cairo_lang_utils/ordered_hash_map.rs

cairo_lang_utils/
ordered_hash_map.rs
