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

deser_value/
map.rs
