Skip to main content

buffa/sensitive/
map.rs

1// Modified by ReallyMe Technologies Limited.
2use super::{Zeroize, ZeroizeOnDrop, Zeroizing};
3use alloc::{boxed::Box, collections::BTreeMap};
4use core::{borrow::Borrow, fmt};
5
6/// A stable wipe-owned map key, exposed for borrowed-lookup bounds.
7/// Its contents are available through the map's borrowed entry API.
8#[doc(hidden)]
9pub struct MapKey<K: Zeroize>(Box<Zeroizing<K>>);
10impl<K: Zeroize> core::ops::Deref for MapKey<K> {
11    type Target = K;
12    fn deref(&self) -> &K {
13        &self.0
14    }
15}
16impl<K: Zeroize + PartialEq> PartialEq for MapKey<K> {
17    fn eq(&self, other: &Self) -> bool {
18        **self == **other
19    }
20}
21impl<K: Zeroize + Eq> Eq for MapKey<K> {}
22impl<K: Zeroize + PartialOrd> PartialOrd for MapKey<K> {
23    fn partial_cmp(&self, other: &Self) -> Option<core::cmp::Ordering> {
24        (**self).partial_cmp(&**other)
25    }
26}
27impl<K: Zeroize + Ord> Ord for MapKey<K> {
28    fn cmp(&self, other: &Self) -> core::cmp::Ordering {
29        (**self).cmp(&**other)
30    }
31}
32impl<K: Zeroize> Borrow<K> for MapKey<K> {
33    fn borrow(&self) -> &K {
34        self
35    }
36}
37impl<K: Zeroize + Borrow<str>> Borrow<str> for MapKey<K> {
38    fn borrow(&self) -> &str {
39        K::borrow(self)
40    }
41}
42impl<K: Zeroize + Borrow<[u8]>> Borrow<[u8]> for MapKey<K> {
43    fn borrow(&self) -> &[u8] {
44        K::borrow(self)
45    }
46}
47
48/// An ordered map with keys and values in stable wipe-owned allocations.
49///
50/// Tree balancing only moves pointers. Key order is deterministic and lookup
51/// has logarithmic worst-case cost, including in no_std without random seeds.
52pub struct Map<K: Zeroize, V: Zeroize>(BTreeMap<MapKey<K>, Box<Zeroizing<V>>>);
53impl<K: Zeroize, V: Zeroize> Default for Map<K, V> {
54    fn default() -> Self {
55        Self(BTreeMap::new())
56    }
57}
58impl<K: Zeroize, V: Zeroize> Map<K, V> {
59    /// Number of entries.
60    pub fn len(&self) -> usize {
61        self.0.len()
62    }
63    /// Whether the map is empty.
64    pub fn is_empty(&self) -> bool {
65        self.0.is_empty()
66    }
67    /// Borrow entries in ascending key order.
68    pub fn iter(&self) -> Iter<'_, K, V> {
69        Iter {
70            inner: self.0.iter(),
71        }
72    }
73    /// Borrow keys in ascending order.
74    pub fn keys(&self) -> impl DoubleEndedIterator<Item = &K> + ExactSizeIterator {
75        self.0.keys().map(|key| &**key)
76    }
77    /// Borrow values in ascending key order.
78    pub fn values(&self) -> impl DoubleEndedIterator<Item = &V> + ExactSizeIterator {
79        self.0.values().map(|value| &***value)
80    }
81    /// Mutably borrow values in place, without moving their stable slots.
82    pub fn values_mut(&mut self) -> impl DoubleEndedIterator<Item = &mut V> + ExactSizeIterator {
83        self.0.values_mut().map(|value| &mut ***value)
84    }
85    /// Wipe and remove every entry.
86    pub fn clear(&mut self) {
87        self.0.clear();
88    }
89}
90impl<K: Zeroize + Ord, V: Zeroize> Map<K, V> {
91    /// Insert a value, wiping a replaced value and any redundant key before release.
92    pub fn insert(&mut self, key: K, value: V) {
93        self.0.insert(
94            MapKey(Box::new(Zeroizing::new(key))),
95            Box::new(Zeroizing::new(value)),
96        );
97    }
98    /// Find a value by its key, a borrowed string, or borrowed bytes.
99    pub fn get<Q: Ord + ?Sized>(&self, key: &Q) -> Option<&V>
100    where
101        MapKey<K>: Borrow<Q>,
102    {
103        self.0.get(key).map(|value| &***value)
104    }
105    /// Mutably borrow an existing value without moving its storage.
106    pub fn get_mut<Q: Ord + ?Sized>(&mut self, key: &Q) -> Option<&mut V>
107    where
108        MapKey<K>: Borrow<Q>,
109    {
110        self.0.get_mut(key).map(|value| &mut ***value)
111    }
112}
113impl<K: Zeroize, V: Zeroize> Zeroize for Map<K, V> {
114    fn zeroize(&mut self) {
115        self.clear();
116    }
117}
118impl<K: Zeroize, V: Zeroize> Drop for Map<K, V> {
119    fn drop(&mut self) {
120        self.zeroize();
121    }
122}
123impl<K: Zeroize, V: Zeroize> ZeroizeOnDrop for Map<K, V> {}
124impl<K: Zeroize + Ord + Clone, V: Zeroize + Clone> Clone for Map<K, V> {
125    fn clone(&self) -> Self {
126        self.iter().map(|(k, v)| (k.clone(), v.clone())).collect()
127    }
128}
129impl<K: Zeroize + Ord, V: Zeroize + PartialEq> PartialEq for Map<K, V> {
130    fn eq(&self, other: &Self) -> bool {
131        self.len() == other.len()
132            && self
133                .iter()
134                .all(|(key, value)| other.get(key) == Some(value))
135    }
136}
137impl<K: Zeroize + Ord, V: Zeroize + Eq> Eq for Map<K, V> {}
138impl<K: Zeroize, V: Zeroize> fmt::Debug for Map<K, V> {
139    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
140        f.write_str("Map([REDACTED])")
141    }
142}
143impl<K: Zeroize + Ord, V: Zeroize> FromIterator<(K, V)> for Map<K, V> {
144    fn from_iter<I: IntoIterator<Item = (K, V)>>(iter: I) -> Self {
145        let mut map = Self::default();
146        for (k, v) in iter {
147            map.insert(k, v);
148        }
149        map
150    }
151}
152impl<K: Zeroize + Ord, V: Zeroize> crate::map_codec::MapStorage for Map<K, V> {
153    type Key = K;
154    type Value = V;
155    fn storage_len(&self) -> usize {
156        self.len()
157    }
158    fn storage_insert(&mut self, key: K, value: V) {
159        self.insert(key, value);
160    }
161    fn storage_clear(&mut self) {
162        self.clear();
163    }
164    fn storage_erase_key(key: &mut K) {
165        key.zeroize();
166    }
167    fn storage_erase_value(value: &mut V) {
168        value.zeroize();
169    }
170    fn storage_iter<'a>(&'a self) -> impl Iterator<Item = (&'a K, &'a V)>
171    where
172        K: 'a,
173        V: 'a,
174    {
175        self.iter()
176    }
177}
178/// Borrowed entries in ascending key order.
179pub struct Iter<'a, K: Zeroize, V: Zeroize> {
180    inner: alloc::collections::btree_map::Iter<'a, MapKey<K>, Box<Zeroizing<V>>>,
181}
182impl<'a, K: Zeroize, V: Zeroize> Iterator for Iter<'a, K, V> {
183    type Item = (&'a K, &'a V);
184    fn next(&mut self) -> Option<Self::Item> {
185        self.inner.next().map(|(key, value)| (&**key, &***value))
186    }
187    fn size_hint(&self) -> (usize, Option<usize>) {
188        self.inner.size_hint()
189    }
190}
191impl<K: Zeroize, V: Zeroize> DoubleEndedIterator for Iter<'_, K, V> {
192    fn next_back(&mut self) -> Option<Self::Item> {
193        self.inner
194            .next_back()
195            .map(|(key, value)| (&**key, &***value))
196    }
197}
198impl<K: Zeroize, V: Zeroize> ExactSizeIterator for Iter<'_, K, V> {}
199impl<K: Zeroize, V: Zeroize> core::iter::FusedIterator for Iter<'_, K, V> {}
200impl<'a, K: Zeroize, V: Zeroize> IntoIterator for &'a Map<K, V> {
201    type Item = (&'a K, &'a V);
202    type IntoIter = Iter<'a, K, V>;
203    fn into_iter(self) -> Self::IntoIter {
204        self.iter()
205    }
206}
207#[cfg(feature = "json")]
208impl<K: Zeroize + serde::Serialize, V: Zeroize + serde::Serialize> serde::Serialize for Map<K, V> {
209    fn serialize<S: serde::Serializer>(&self, serializer: S) -> Result<S::Ok, S::Error> {
210        use serde::ser::SerializeMap;
211        let mut map = serializer.serialize_map(Some(self.len()))?;
212        for (k, v) in self.iter() {
213            map.serialize_entry(k, v)?;
214        }
215        map.end()
216    }
217}
218#[cfg(feature = "json")]
219impl<'de, K: Zeroize + Ord + serde::Deserialize<'de>, V: Zeroize + serde::Deserialize<'de>>
220    serde::Deserialize<'de> for Map<K, V>
221{
222    fn deserialize<D: serde::Deserializer<'de>>(deserializer: D) -> Result<Self, D::Error> {
223        struct Visitor<K, V>(core::marker::PhantomData<(K, V)>);
224        impl<
225                'de,
226                K: Zeroize + Ord + serde::Deserialize<'de>,
227                V: Zeroize + serde::Deserialize<'de>,
228            > serde::de::Visitor<'de> for Visitor<K, V>
229        {
230            type Value = Map<K, V>;
231            fn expecting(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
232                f.write_str("an object")
233            }
234            fn visit_map<A: serde::de::MapAccess<'de>>(
235                self,
236                mut access: A,
237            ) -> Result<Self::Value, A::Error> {
238                let mut map = Map::default();
239                while let Some(key) = access.next_key::<K>()? {
240                    let key = Zeroizing::new(key);
241                    let value = access.next_value()?;
242                    map.0
243                        .insert(MapKey(Box::new(key)), Box::new(Zeroizing::new(value)));
244                }
245                Ok(map)
246            }
247        }
248        deserializer.deserialize_map(Visitor(core::marker::PhantomData))
249    }
250}
251
252#[cfg(test)]
253mod tests {
254    use super::*;
255    use alloc::string::String;
256    use core::sync::atomic::{AtomicUsize, Ordering};
257    static ERASED: AtomicUsize = AtomicUsize::new(0);
258    #[derive(Clone)]
259    struct Counted(u64);
260    impl Zeroize for Counted {
261        fn zeroize(&mut self) {
262            self.0.zeroize();
263            ERASED.fetch_add(1, Ordering::SeqCst);
264        }
265    }
266    #[test]
267    fn stable_values_are_wiped_on_replacement_clear_and_drop() {
268        ERASED.store(0, Ordering::SeqCst);
269        let mut map = Map::<String, Counted>::default();
270        map.insert("key".into(), Counted(42));
271        let address = map.get("key").unwrap() as *const Counted;
272        for n in 0..100 {
273            map.insert(alloc::format!("other-{n}"), Counted(n));
274        }
275        assert_eq!(address, map.get("key").unwrap() as *const Counted);
276        map.insert("key".into(), Counted(43));
277        assert_eq!(ERASED.load(Ordering::SeqCst), 1);
278        map.get_mut("key").unwrap().0 = 44;
279        map.clear();
280        assert!(map.is_empty());
281        assert_eq!(ERASED.load(Ordering::SeqCst), 102);
282        map.insert("key".into(), Counted(45));
283        drop(map);
284        assert_eq!(ERASED.load(Ordering::SeqCst), 103);
285    }
286    #[cfg(feature = "json")]
287    #[test]
288    fn native_serde_handles_duplicates_and_invalid_values() {
289        let map: Map<String, u64> = serde_json::from_str(r#"{"key":1,"key":2}"#).unwrap();
290        assert_eq!(map.get("key"), Some(&2));
291        assert_eq!(serde_json::to_string(&map).unwrap(), r#"{"key":2}"#);
292        assert!(serde_json::from_str::<Map<String, u64>>(r#"{"key":1,"bad":[]}"#).is_err());
293    }
294}