deser_value/
map.rs

1use std::cmp::Ordering;
2use std::collections::hash_map::{DefaultHasher, RandomState};
3use std::fmt;
4use std::hash::{BuildHasher, Hash, Hasher};
5use std::iter::FusedIterator;
6use std::sync::OnceLock;
7
8use deser_core::Order;
9use indexmap::{Equivalent, IndexMap};
10
11use crate::tree;
12use crate::value::{Kind, Value};
13
14/// Hashes the keys of maps.
15///
16/// The keys are random per process which protects against collisions
17/// provoked by untrusted input.  Unlike [`RandomState`] this has no size
18/// which keeps maps small.
19#[derive(Clone, Copy, Default)]
20pub(crate) struct MapHasher;
21
22impl BuildHasher for MapHasher {
23    type Hasher = DefaultHasher;
24
25    #[inline]
26    fn build_hasher(&self) -> DefaultHasher {
27        static KEYS: OnceLock<RandomState> = OnceLock::new();
28        KEYS.get_or_init(RandomState::new).build_hasher()
29    }
30}
31
32pub(crate) type Entries = IndexMap<Value, Value, MapHasher>;
33
34pub(crate) struct MapInner {
35    pub(crate) entries: Entries,
36    pub(crate) order: Order,
37    pub(crate) multimap: bool,
38}
39
40/// A map of values.
41///
42/// Maps retain the order in which the entries were inserted and every key
43/// is unique.  Keys can be any value, not just strings.  Additionally a
44/// map holds the [`Order`] of its entries and if it's a multimap (see
45/// [`is_multimap`](Self::is_multimap)) which are passed on to formats when
46/// the map is serialized.  Neither is considered when maps are compared:
47/// maps are equal if they contain the same entries.  The
48/// exception are entries with maps or sequences as keys, which are compared
49/// in order (this allows comparing maps without recursion).
50///
51/// ```
52/// use deser_value::{Map, Value};
53///
54/// let mut map = Map::new();
55/// map.insert("name", "Jane");
56/// map.insert(42, true);
57/// assert_eq!(map.get("name"), Some(&Value::from("Jane")));
58/// assert_eq!(map.get(&42), Some(&Value::from(true)));
59/// assert_eq!(
60///     map.keys().collect::<Vec<_>>(),
61///     [&Value::from("name"), &Value::from(42)]
62/// );
63/// ```
64///
65/// Keys can be looked up by anything that implements [`MapKey`], which
66/// includes strings, integers and values.
67pub struct Map {
68    pub(crate) inner: Box<MapInner>,
69}
70
71impl Map {
72    /// Creates an empty map.
73    pub fn new() -> Map {
74        Map::with_capacity(0)
75    }
76
77    /// Creates an empty map with a capacity.
78    pub fn with_capacity(capacity: usize) -> Map {
79        Map {
80            inner: Box::new(MapInner {
81                entries: IndexMap::with_capacity_and_hasher(capacity, MapHasher),
82                order: Order::Natural,
83                multimap: false,
84            }),
85        }
86    }
87
88    /// Returns the order of the entries.
89    pub fn order(&self) -> Order {
90        self.inner.order
91    }
92
93    /// Sets the order of the entries.
94    pub fn set_order(&mut self, order: Order) {
95        self.inner.order = order;
96    }
97
98    /// Sets the order of the entries and returns the map.
99    pub fn with_order(mut self, order: Order) -> Map {
100        self.inner.order = order;
101        self
102    }
103
104    /// Returns `true` if the map is a multimap.
105    ///
106    /// Maps that are deserialized from multimaps (like query strings, see
107    /// [`ContainerShape::with_multimap`](deser_core::ContainerShape::with_multimap))
108    /// are multimaps.  The values of a key that was given more than once
109    /// are a [`Seq`](crate::Seq) marked as
110    /// [repeated](crate::Seq::is_repeated).  When the map is deserialized
111    /// into another type, it's a multimap again and the values of repeated
112    /// keys are passed on as the values of repeated keys.  A key that was
113    /// given once is a single value, so types that collect the values of
114    /// keys (like `Vec<T>`) receive the same values as from the original
115    /// input.
116    ///
117    /// ```
118    /// use deser_value::{Map, Seq, Value};
119    ///
120    /// #[derive(deser::Deserialize, Debug, PartialEq)]
121    /// struct Query {
122    ///     tag: Vec<String>,
123    ///     page: Vec<u32>,
124    /// }
125    ///
126    /// let mut map = Map::new().with_multimap(true);
127    /// map.insert(
128    ///     "tag",
129    ///     Seq::from(vec![Value::from("a"), Value::from("b")])
130    ///         .with_repeated(true),
131    /// );
132    /// map.insert("page", 1);
133    /// let query: Query = deser_value::from_value(&Value::from(map)).unwrap();
134    /// assert_eq!(
135    ///     query,
136    ///     Query { tag: vec!["a".into(), "b".into()], page: vec![1] }
137    /// );
138    /// ```
139    pub fn is_multimap(&self) -> bool {
140        self.inner.multimap
141    }
142
143    /// Sets if the map is a multimap.
144    pub fn set_multimap(&mut self, yes: bool) {
145        self.inner.multimap = yes;
146    }
147
148    /// Sets if the map is a multimap and returns the map.
149    pub fn with_multimap(mut self, yes: bool) -> Map {
150        self.inner.multimap = yes;
151        self
152    }
153
154    /// Returns the number of entries.
155    pub fn len(&self) -> usize {
156        self.inner.entries.len()
157    }
158
159    /// Returns `true` if the map has no entries.
160    pub fn is_empty(&self) -> bool {
161        self.inner.entries.is_empty()
162    }
163
164    /// Returns the value of a key.
165    pub fn get<K: MapKey + ?Sized>(&self, key: &K) -> Option<&Value> {
166        self.inner.entries.get(&key.__key_ref())
167    }
168
169    /// Returns the value of a key mutably.
170    pub fn get_mut<K: MapKey + ?Sized>(&mut self, key: &K) -> Option<&mut Value> {
171        self.inner.entries.get_mut(&key.__key_ref())
172    }
173
174    /// Returns the key and value of a key.
175    ///
176    /// This is useful to get to the meta data of the key.
177    pub fn get_key_value<K: MapKey + ?Sized>(&self, key: &K) -> Option<(&Value, &Value)> {
178        self.inner.entries.get_key_value(&key.__key_ref())
179    }
180
181    /// Returns the index of a key.
182    pub fn get_index_of<K: MapKey + ?Sized>(&self, key: &K) -> Option<usize> {
183        self.inner.entries.get_index_of(&key.__key_ref())
184    }
185
186    /// Returns the key and value at an index.
187    pub fn get_index(&self, index: usize) -> Option<(&Value, &Value)> {
188        self.inner.entries.get_index(index)
189    }
190
191    /// Returns the key and the mutable value at an index.
192    pub fn get_index_mut(&mut self, index: usize) -> Option<(&Value, &mut Value)> {
193        self.inner.entries.get_index_mut(index)
194    }
195
196    /// Returns `true` if the map contains a key.
197    pub fn contains_key<K: MapKey + ?Sized>(&self, key: &K) -> bool {
198        self.inner.entries.contains_key(&key.__key_ref())
199    }
200
201    /// Inserts a value for a key.
202    ///
203    /// If the key already exists, its value is replaced (the entry keeps its
204    /// position and key) and the old value is returned.  Otherwise the entry
205    /// is added at the end.
206    pub fn insert<K: Into<Value>, V: Into<Value>>(&mut self, key: K, value: V) -> Option<Value> {
207        self.inner.entries.insert(key.into(), value.into())
208    }
209
210    /// Returns the value of a key, inserting the result of `f` if the key
211    /// does not exist.
212    pub fn get_or_insert_with<K: Into<Value>, F: FnOnce() -> Value>(
213        &mut self,
214        key: K,
215        f: F,
216    ) -> &mut Value {
217        self.inner.entries.entry(key.into()).or_insert_with(f)
218    }
219
220    /// Removes a key and returns its value.
221    ///
222    /// The order of the remaining entries is retained.
223    pub fn remove<K: MapKey + ?Sized>(&mut self, key: &K) -> Option<Value> {
224        self.inner.entries.shift_remove(&key.__key_ref())
225    }
226
227    /// Removes a key and returns it together with its value.
228    ///
229    /// The order of the remaining entries is retained.
230    pub fn remove_entry<K: MapKey + ?Sized>(&mut self, key: &K) -> Option<(Value, Value)> {
231        self.inner.entries.shift_remove_entry(&key.__key_ref())
232    }
233
234    /// Retains the entries for which the predicate returns `true`.
235    pub fn retain<F: FnMut(&Value, &mut Value) -> bool>(&mut self, f: F) {
236        self.inner.entries.retain(f);
237    }
238
239    /// Sorts the entries with a comparison function.
240    pub fn sort_by<F>(&mut self, mut f: F)
241    where
242        F: FnMut(&Value, &Value, &Value, &Value) -> Ordering,
243    {
244        self.inner
245            .entries
246            .sort_by(|k1, v1, k2, v2| f(k1, v1, k2, v2));
247    }
248
249    /// Removes all entries.
250    pub fn clear(&mut self) {
251        if self
252            .inner
253            .entries
254            .iter()
255            .any(|(k, v)| k.has_children() || v.has_children())
256        {
257            let entries = std::mem::take(&mut self.inner.entries);
258            tree::drop_entries(entries);
259        } else {
260            self.inner.entries.clear();
261        }
262    }
263
264    /// Returns an iterator over the entries.
265    pub fn iter(&self) -> Iter<'_> {
266        Iter(self.inner.entries.iter())
267    }
268
269    /// Returns an iterator over the entries with mutable values.
270    pub fn iter_mut(&mut self) -> IterMut<'_> {
271        IterMut(self.inner.entries.iter_mut())
272    }
273
274    /// Returns an iterator over the keys.
275    pub fn keys(&self) -> Keys<'_> {
276        Keys(self.inner.entries.keys())
277    }
278
279    /// Returns an iterator over the values.
280    pub fn values(&self) -> Values<'_> {
281        Values(self.inner.entries.values())
282    }
283
284    /// Returns an iterator over the mutable values.
285    pub fn values_mut(&mut self) -> ValuesMut<'_> {
286        ValuesMut(self.inner.entries.values_mut())
287    }
288}
289
290impl Default for Map {
291    fn default() -> Map {
292        Map::new()
293    }
294}
295
296impl Drop for Map {
297    fn drop(&mut self) {
298        if self
299            .inner
300            .entries
301            .iter()
302            .any(|(k, v)| k.has_children() || v.has_children())
303        {
304            tree::drop_entries(std::mem::take(&mut self.inner.entries));
305        }
306    }
307}
308
309impl Clone for Map {
310    fn clone(&self) -> Map {
311        match tree::clone_map(self) {
312            Kind::Map(map) => map,
313            _ => unreachable!(),
314        }
315    }
316}
317
318impl PartialEq for Map {
319    fn eq(&self, other: &Map) -> bool {
320        tree::eq_map(self, other)
321    }
322}
323
324impl Eq for Map {}
325
326impl Hash for Map {
327    fn hash<H: Hasher>(&self, state: &mut H) {
328        tree::hash_map(self, state);
329    }
330}
331
332impl fmt::Debug for Map {
333    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
334        tree::fmt_map(self, f)
335    }
336}
337
338impl<K: Into<Value>, V: Into<Value>> FromIterator<(K, V)> for Map {
339    fn from_iter<I: IntoIterator<Item = (K, V)>>(iter: I) -> Map {
340        let iter = iter.into_iter();
341        let mut map = Map::with_capacity(iter.size_hint().0);
342        map.extend(iter);
343        map
344    }
345}
346
347impl<K: Into<Value>, V: Into<Value>> Extend<(K, V)> for Map {
348    fn extend<I: IntoIterator<Item = (K, V)>>(&mut self, iter: I) {
349        for (key, value) in iter {
350            self.insert(key, value);
351        }
352    }
353}
354
355macro_rules! iterator {
356    ($(#[$attr:meta])* $name:ident<$lt:lifetime>, $inner:ty, $item:ty) => {
357        $(#[$attr])*
358        pub struct $name<$lt>($inner);
359
360        impl<$lt> Iterator for $name<$lt> {
361            type Item = $item;
362
363            #[inline]
364            fn next(&mut self) -> Option<$item> {
365                self.0.next()
366            }
367
368            #[inline]
369            fn size_hint(&self) -> (usize, Option<usize>) {
370                self.0.size_hint()
371            }
372        }
373
374        impl<$lt> DoubleEndedIterator for $name<$lt> {
375            #[inline]
376            fn next_back(&mut self) -> Option<$item> {
377                self.0.next_back()
378            }
379        }
380
381        impl<$lt> ExactSizeIterator for $name<$lt> {}
382
383        impl<$lt> FusedIterator for $name<$lt> {}
384    };
385}
386
387iterator!(
388    /// An iterator over the entries of a [`Map`].
389    Iter<'a>, indexmap::map::Iter<'a, Value, Value>, (&'a Value, &'a Value)
390);
391iterator!(
392    /// An iterator over the entries of a [`Map`] with mutable values.
393    IterMut<'a>, indexmap::map::IterMut<'a, Value, Value>, (&'a Value, &'a mut Value)
394);
395iterator!(
396    /// An iterator over the keys of a [`Map`].
397    Keys<'a>, indexmap::map::Keys<'a, Value, Value>, &'a Value
398);
399iterator!(
400    /// An iterator over the values of a [`Map`].
401    Values<'a>, indexmap::map::Values<'a, Value, Value>, &'a Value
402);
403iterator!(
404    /// An iterator over the mutable values of a [`Map`].
405    ValuesMut<'a>, indexmap::map::ValuesMut<'a, Value, Value>, &'a mut Value
406);
407
408/// An owning iterator over the entries of a [`Map`].
409pub struct IntoIter(indexmap::map::IntoIter<Value, Value>);
410
411impl Iterator for IntoIter {
412    type Item = (Value, Value);
413
414    #[inline]
415    fn next(&mut self) -> Option<(Value, Value)> {
416        self.0.next()
417    }
418
419    #[inline]
420    fn size_hint(&self) -> (usize, Option<usize>) {
421        self.0.size_hint()
422    }
423}
424
425impl DoubleEndedIterator for IntoIter {
426    #[inline]
427    fn next_back(&mut self) -> Option<(Value, Value)> {
428        self.0.next_back()
429    }
430}
431
432impl ExactSizeIterator for IntoIter {}
433
434impl FusedIterator for IntoIter {}
435
436impl IntoIterator for Map {
437    type Item = (Value, Value);
438    type IntoIter = IntoIter;
439
440    fn into_iter(mut self) -> IntoIter {
441        IntoIter(std::mem::take(&mut self.inner.entries).into_iter())
442    }
443}
444
445impl<'a> IntoIterator for &'a Map {
446    type Item = (&'a Value, &'a Value);
447    type IntoIter = Iter<'a>;
448
449    fn into_iter(self) -> Iter<'a> {
450        self.iter()
451    }
452}
453
454impl<'a> IntoIterator for &'a mut Map {
455    type Item = (&'a Value, &'a mut Value);
456    type IntoIter = IterMut<'a>;
457
458    fn into_iter(self) -> IterMut<'a> {
459        self.iter_mut()
460    }
461}
462
463mod sealed {
464    pub trait Sealed {}
465}
466
467/// A type that map keys can be looked up with.
468///
469/// This is implemented for strings, integers, bools, chars and
470/// [`Value`]s.  Looking up keys with it does not require the key to be
471/// converted into a value first.
472pub trait MapKey: sealed::Sealed {
473    #[doc(hidden)]
474    fn __key_ref(&self) -> KeyRef<'_>;
475}
476
477/// A borrowed map key.
478#[doc(hidden)]
479pub enum KeyRef<'a> {
480    Str(&'a str),
481    Int(i128),
482    Bool(bool),
483    Char(char),
484    Value(&'a Value),
485}
486
487impl Hash for KeyRef<'_> {
488    fn hash<H: Hasher>(&self, state: &mut H) {
489        match *self {
490            KeyRef::Str(value) => tree::hash_str(value, state),
491            KeyRef::Int(value) => tree::hash_int(value, state),
492            KeyRef::Bool(value) => tree::hash_bool(value, state),
493            KeyRef::Char(value) => tree::hash_char(value, state),
494            KeyRef::Value(value) => value.hash(state),
495        }
496    }
497}
498
499impl Equivalent<Value> for KeyRef<'_> {
500    fn equivalent(&self, key: &Value) -> bool {
501        match (self, &key.kind) {
502            // implicit values are looked up like their value
503            (_, Kind::Implicit(value)) => {
504                self.equivalent(&Value::new(Kind::from_implicit(value.value())))
505            }
506            (KeyRef::Str(a), Kind::Str(b) | Kind::Lexical(b)) => *a == b,
507            (KeyRef::Int(a), Kind::U64(b)) => *a == i128::from(*b),
508            (KeyRef::Int(a), Kind::I64(b)) => *a == i128::from(*b),
509            (KeyRef::Bool(a), Kind::Bool(b)) => a == b,
510            (KeyRef::Char(a), Kind::Char(b)) => a == b,
511            (KeyRef::Value(a), _) => *a == key,
512            _ => false,
513        }
514    }
515}
516
517impl sealed::Sealed for str {}
518
519impl MapKey for str {
520    fn __key_ref(&self) -> KeyRef<'_> {
521        KeyRef::Str(self)
522    }
523}
524
525impl sealed::Sealed for String {}
526
527impl MapKey for String {
528    fn __key_ref(&self) -> KeyRef<'_> {
529        KeyRef::Str(self)
530    }
531}
532
533impl sealed::Sealed for bool {}
534
535impl MapKey for bool {
536    fn __key_ref(&self) -> KeyRef<'_> {
537        KeyRef::Bool(*self)
538    }
539}
540
541impl sealed::Sealed for char {}
542
543impl MapKey for char {
544    fn __key_ref(&self) -> KeyRef<'_> {
545        KeyRef::Char(*self)
546    }
547}
548
549impl sealed::Sealed for Value {}
550
551impl MapKey for Value {
552    fn __key_ref(&self) -> KeyRef<'_> {
553        KeyRef::Value(self)
554    }
555}
556
557impl<T: MapKey + ?Sized> sealed::Sealed for &T {}
558
559impl<T: MapKey + ?Sized> MapKey for &T {
560    fn __key_ref(&self) -> KeyRef<'_> {
561        (**self).__key_ref()
562    }
563}
564
565macro_rules! int_key {
566    ($($ty:ty),*) => {
567        $(
568            impl sealed::Sealed for $ty {}
569
570            impl MapKey for $ty {
571                fn __key_ref(&self) -> KeyRef<'_> {
572                    KeyRef::Int(*self as i128)
573                }
574            }
575        )*
576    };
577}
578
579int_key!(u8, u16, u32, u64, usize, i8, i16, i32, i64, isize);
deser_value/map.rs

deser_value/
map.rs
