Skip to main content

slotmap_careful/
lib.rs

1#![cfg_attr(docsrs, feature(doc_cfg))]
2#![doc = include_str!("../README.md")]
3// @@ begin lint list maintained by maint/add_warning @@
4#![allow(renamed_and_removed_lints)] // @@REMOVE_WHEN(ci_arti_stable)
5#![allow(unknown_lints)] // @@REMOVE_WHEN(ci_arti_nightly)
6#![warn(missing_docs)]
7#![warn(noop_method_call)]
8#![warn(unreachable_pub)]
9#![warn(clippy::all)]
10#![deny(clippy::await_holding_lock)]
11#![deny(clippy::cargo_common_metadata)]
12#![deny(clippy::cast_lossless)]
13#![deny(clippy::checked_conversions)]
14#![allow(clippy::cognitive_complexity)] // See arti#2556
15#![deny(clippy::debug_assert_with_mut_call)]
16#![deny(clippy::exhaustive_enums)]
17#![deny(clippy::exhaustive_structs)]
18#![deny(clippy::expl_impl_clone_on_copy)]
19#![deny(clippy::fallible_impl_from)]
20#![deny(clippy::implicit_clone)]
21#![deny(clippy::large_stack_arrays)]
22#![warn(clippy::manual_ok_or)]
23#![deny(clippy::missing_docs_in_private_items)]
24#![warn(clippy::needless_borrow)]
25#![warn(clippy::needless_pass_by_value)]
26#![warn(clippy::option_option)]
27#![warn(clippy::or_fun_call)]
28#![deny(clippy::print_stderr)]
29#![deny(clippy::print_stdout)]
30#![warn(clippy::rc_buffer)]
31#![deny(clippy::ref_option_ref)]
32#![warn(clippy::semicolon_if_nothing_returned)]
33#![warn(clippy::trait_duplication_in_bounds)]
34#![deny(clippy::unchecked_time_subtraction)]
35#![deny(clippy::unnecessary_wraps)]
36#![warn(clippy::unseparated_literal_suffix)]
37#![deny(clippy::unwrap_used)]
38#![deny(clippy::mod_module_files)]
39#![allow(clippy::let_unit_value)] // This can reasonably be done for explicitness
40#![allow(clippy::uninlined_format_args)]
41#![allow(clippy::significant_drop_in_scrutinee)] // arti/-/merge_requests/588/#note_2812945
42#![allow(clippy::result_large_err)] // temporary workaround for arti#587
43#![allow(clippy::needless_raw_string_hashes)] // complained-about code is fine, often best
44#![allow(clippy::needless_lifetimes)] // See arti#1765
45#![allow(mismatched_lifetime_syntaxes)] // temporary workaround for arti#2060
46#![allow(clippy::collapsible_if)] // See arti#2342
47#![deny(clippy::unused_async)]
48#![deny(clippy::string_slice)] // See arti#2571
49#![allow(recursion_depth_exceeding_limit)] // arti#2715, rust/issues/159228
50//! <!-- @@ end lint list maintained by maint/add_warning @@ -->
51
52// TODO: add to the list maintained by maint/add_warning once it's available on all crates
53#![warn(unnameable_types)]
54
55mod key_data;
56
57pub use slotmap::{
58    DefaultKey, Key, KeyData, SecondaryMap, SparseSecondaryMap, new_key_type, secondary,
59};
60
61use key_data::key_version_serde as key_version;
62
63//use key_version::key_version_serde;
64
65/// A single entry in one of our careful slotmaps.
66///
67/// An entry can either be `Present` (in which case we treat it normally),
68/// or `Unusable`, in which case we
69#[cfg_attr(test, derive(serde::Serialize, serde::Deserialize))]
70#[derive(Debug, Clone)]
71enum Entry<V> {
72    /// The entry is available.
73    Present(V),
74    /// The entry can no longer be used, removed, or set to anything else.
75    ///
76    /// It must not be removed from the slot map, since doing so would
77    /// increase its slot's version number too high.
78    Unusable,
79}
80
81impl<V> Entry<V> {
82    /// Remove the value of `self` (if any), and make it unusable.
83    fn take_and_mark_unusable(&mut self) -> Option<V> {
84        match std::mem::replace(self, Entry::Unusable) {
85            Entry::Present(v) => Some(v),
86            Entry::Unusable => None,
87        }
88    }
89    /// Return a reference to the value of `self`, if there is one.
90    fn value(&self) -> Option<&V> {
91        match self {
92            Entry::Present(val) => Some(val),
93            Entry::Unusable => None,
94        }
95    }
96    /// Return a mutable reference to the value of `self``, if there is one.
97    fn value_mut(&mut self) -> Option<&mut V> {
98        match self {
99            Entry::Present(val) => Some(val),
100            Entry::Unusable => None,
101        }
102    }
103    /// Consume this entry (which must be `Present`), and return its value.
104    ///
105    /// # Panics
106    ///
107    /// Panics if this entry is `Unusable`.
108    fn unwrap(self) -> V {
109        match self {
110            Entry::Present(val) => val,
111            Entry::Unusable => panic!("Tried to unwrap an unusable slot."),
112        }
113    }
114}
115
116/// Helper: Define a wrapper for a single SlotMap type.
117///
118/// This works for SlotMap, and DenseSlotMap.
119///
120/// (The alternative to using a macro here would be to define a new trait
121/// implemented by all of the SlotMaps, and then to define our own SlotMap as a wrapper around an
122/// instance of that trait.)
123macro_rules! define_implementation {
124        { $mapname:ident } => {paste::paste!{
125
126        /// A variation of
127        #[doc = concat!("[`slotmap::", stringify!($mapname), "`]")]
128        /// that can never give the same key for multiple objects.
129        ///
130        /// Unlike a regular version of
131        #[doc = concat!("`", stringify!($mapname), "`,")]
132        /// this version will not allow a slot's version counter to roll over to
133        /// 0 if it reaches 2^31.  Instead, it will mark the slot as unusable for future values.
134        ///
135        /// # Limitations
136        ///
137        /// The possibility of marking a slot as unusable
138        /// makes it possible, given enough removals and re-insertions,
139        /// for a slotmap to use an unbounded amount of memory, even if it is not storing much actual data.
140        /// (From a DOS point of view: Given the ability to re-insert an entry ~2^31 times, an attacker can
141        /// cause a slot-map to render approximately `4+sizeof(V)` bytes unusable.)
142        ///
143        /// This type does not include implementations for:
144        ///   * `get_unchecked_mut()`
145        ///   * `get_disjoint_unchecked_mut()`
146        ///   * `IntoIterator`.
147        ///   * `serde::{Serialize, Deserialize}`.
148        ///
149        /// # Risky business!
150        ///
151        /// This code relies upon stability of some undocumented properties of `slotmap` keys.
152        /// In particular, it assumes:
153        ///  * that the slotmap KeyData `serde` format is stable,
154        ///  * that slot versions are represented as `u32`.
155        ///  * that the least significant bit of a slot version is 1 if the slot is full,
156        ///    and 0 if the slot is empty.
157        ///  * that slot versions start at 0, and increase monotonically as the slot is
158        ///    emptied and reused.
159        ///
160        /// Note that these assumptions are _probably_ okay: if `slotmap` were to change them,
161        /// it would thereby create a breaking change in its serde version.
162        //
163        // Invariants:
164        //
165        // For every `(key,value)` that is present in `base`:
166        //   - `key_okay(key)` is true.
167        //   - if `value` is `Entry::Unusable`, then `key_version(key) == SATURATE_AT_VERSION`.
168        //
169        // `n_unusable` is the number of entries in `base` whose value is `Entry::Unusable`.
170        //
171        // To maintain these invariants:
172        //   - Never remove a key with `key_version(key) == SATURATE_AT_VERSION`
173        //   - Whenever setting a value to `Unusable`, increment `n_unusable`.
174        #[derive(Clone, Debug)]
175        pub struct $mapname<K: Key, V> {
176            /// An underlying SlotMap, obeying the invariants above.
177            base: slotmap::$mapname<K, Entry<V>>,
178            /// The number of entries in this SlotMap that are filled with [`Entry::Unusable`] values.
179            n_unusable: usize,
180            /// A ZST, used to guarantee that we have spot-checked the behavior of the underlying
181            /// SlotMap implementation.
182            _valid: [<$mapname ValidationToken>],
183        }
184
185        impl<V> $mapname<DefaultKey, V> {
186            /// Construct a new empty map, using a default key type.
187            ///
188            /// See
189            #[doc = concat!("[`slotmap::", stringify!($mapname), "::new()`].")]
190            pub fn new() -> Self {
191                Self::with_key()
192            }
193
194            /// Construct a new empty map with a specified capacity, using a default key type.
195            ///
196            /// See
197            #[doc = concat!("[`slotmap::", stringify!($mapname), "::with_capacity()`].")]
198            /// ::with_capacity()`].
199            pub fn with_capacity(capacity: usize) -> Self {
200                Self::with_capacity_and_key(capacity)
201            }
202        }
203
204        impl<K: Key, V> Default for $mapname<K, V> {
205            fn default() -> Self {
206                Self::with_key()
207            }
208        }
209
210        impl<K: Key, V> $mapname<K, V> {
211            /// Construct a new empty map, using a specialized key type.
212            ///
213            /// See
214            #[doc= concat!("[`slotmap::", stringify!($mapname), "::with_key()`].")]
215            pub fn with_key() -> Self {
216                Self::with_capacity_and_key(0)
217            }
218
219            /// Construct a new empty map with a specified capacity, using a specialized key type.
220            ///
221            /// See
222            #[doc= concat!("[`slotmap::", stringify!($mapname), "::with_capacity_and_key()`].")]
223            pub fn with_capacity_and_key(capacity: usize) -> Self {
224                Self {
225                    base: slotmap::$mapname::with_capacity_and_key(capacity),
226                    n_unusable: 0,
227                    _valid: [<validate_ $mapname:snake _behavior>](),
228                }
229            }
230
231            /// Return the number of items in this map.
232            ///
233            /// See
234            #[doc= concat!("[`slotmap::", stringify!($mapname), "::len()`].")]
235            pub fn len(&self) -> usize {
236                self.base
237                    .len()
238                    .checked_sub(self.n_unusable)
239                    .expect("logic error")
240            }
241
242            /// Return true if this map has no items.
243            ///
244            /// See
245            #[doc= concat!("[`slotmap::", stringify!($mapname), "::is_empty()`].")]
246            pub fn is_empty(&self) -> bool {
247                self.len() == 0
248            }
249
250            /// Return the total number of slots available for entries in this map.
251            ///
252            /// This number includes used slots, as well as empty slots that may become used.
253            ///
254            /// See
255            #[doc= concat!("[`slotmap::", stringify!($mapname), "::capacity()`],")]
256            /// but note that a `slotmap-careful` implementation may _lose_ capacity over time,
257            /// as slots are marked unusable.
258            pub fn capacity(&self) -> usize {
259                self.base
260                    .capacity()
261                    .checked_sub(self.n_unusable)
262                    .expect("logic error")
263            }
264
265            /// Reserve space as needed.
266            ///
267            /// Allocates if needed, so that this map can hold `additional` new entries
268            /// without having to resize.
269            ///
270            /// See
271            #[doc= concat!("[`slotmap::", stringify!($mapname), "::reserve()`].")]
272            pub fn reserve(&mut self, additional: usize) {
273                // Note that we don't need to check n_unusable here: the underlying
274                // map type thinks that unusable entries are full, and so will allocate
275                // correctly.
276                self.base.reserve(additional);
277            }
278
279            /// Return true if the map contains an entry with a given key.
280            ///
281            /// See
282            #[doc= concat!("[`slotmap::", stringify!($mapname), "::contains_key()`].")]
283            pub fn contains_key(&self, key: K) -> bool {
284                // Calling self.get, not self.base.get, so it will be None if the
285                // slot is unusable.
286                self.get(key).is_some()
287            }
288
289            /// Insert a new value into the map, and return the key used for it.
290            ///
291            /// See
292            #[doc= concat!("[`slotmap::", stringify!($mapname), "::insert()`].")]
293            pub fn insert(&mut self, value: V) -> K {
294                let key = self.base.insert(Entry::Present(value));
295                debug_assert!(key_okay(key));
296                key
297            }
298
299            /// Insert a new value into the map, constructing it using its own new key.
300            ///
301            /// This method is useful for the case where a value needs to refer to the
302            /// key that will be assigned to it.
303            ///
304            /// See
305            #[doc= concat!("[`slotmap::", stringify!($mapname), "::insert_with_key()`].")]
306            pub fn insert_with_key<F>(&mut self, f: F) -> K
307            where
308                F: FnOnce(K) -> V,
309            {
310                let key = self.base.insert_with_key(|k| Entry::Present(f(k)));
311                debug_assert!(key_okay(key));
312                key
313            }
314
315            /// As [`Self::insert_with_key`], but may return an `Err`.
316            ///
317            /// See
318            #[doc= concat!("[`slotmap::", stringify!($mapname), "::try_insert_with_key()`].")]
319            pub fn try_insert_with_key<F, E>(&mut self, f: F) -> Result<K, E>
320            where
321                F: FnOnce(K) -> Result<V, E>,
322            {
323                let key = self
324                    .base
325                    .try_insert_with_key(|k| Ok(Entry::Present(f(k)?)))?;
326                debug_assert!(key_okay(key));
327                Ok(key)
328            }
329
330            /// Remove and return the element of this map with a given key.
331            ///
332            /// Return None if the key is not present in the map.
333            ///
334            /// See
335            #[doc= concat!("[`slotmap::", stringify!($mapname), "::remove()`].")]
336            pub fn remove(&mut self, key: K) -> Option<V> {
337                if key_version_is_maximal(key) {
338                    // The key is as large as it is allowed to get,
339                    // so we should not actually remove this Entry.
340                    match self.base.get_mut(key) {
341                        Some(slot) => {
342                            // The entry is Present: extract its value and mark it unusable.
343                            let rv = slot.take_and_mark_unusable();
344                            if rv.is_some() {
345                                self.n_unusable += 1;
346                            }
347                            rv
348                        }
349                        // The entry is Unusable; treat it as if it weren't there.
350                        None => None,
351                    }
352                } else {
353                    // The Entry::unwrap function will panic if its argument is
354                    // Entry::Unusable.  But that is impossible in this case,
355                    // since we already checked key_version_is_maximal() for this key,
356                    // and our invariant guarantees that, if the value is Entry::Unusable,
357                    // then key_version(key) == SATURATE_AT_VERSION,
358                    // so key_version_is_maximal is true.
359                    self.base.remove(key).map(Entry::unwrap)
360                }
361            }
362
363            /// Remove every element of this map that does not satisfy a given predicate.
364            ///
365            /// See
366            #[doc= concat!("[`slotmap::", stringify!($mapname), "::retain()`].")]
367            pub fn retain<F>(&mut self, mut f: F)
368            where
369                F: FnMut(K, &mut V) -> bool,
370            {
371                self.base.retain(|k, v| {
372                    let Entry::Present(v_inner) = v else {
373                        return true;
374                    };
375
376                    if f(k, v_inner) {
377                        true
378                    } else if key_version_is_maximal(k) {
379                        self.n_unusable += 1;
380                        *v = Entry::Unusable;
381                        true
382                    } else {
383                        false
384                    }
385                });
386            }
387
388            /// Remove every element of this map.
389            ///
390            /// See
391            #[doc= concat!("[`slotmap::", stringify!($mapname), "::clear()`].")]
392            pub fn clear(&mut self) {
393                self.retain(|_, _| false);
394            }
395
396            /// Return a reference to the element of this map with a given key.
397            ///
398            /// Return None if there is no such element.
399            ///
400            /// See
401            #[doc= concat!("[`slotmap::", stringify!($mapname), "::get()`].")]
402            pub fn get(&self, key: K) -> Option<&V> {
403                self.base.get(key).and_then(Entry::value)
404            }
405            /// Return a mutable reference to the element of this map with a given key.
406            ///
407            /// Return None if there is no such element.
408            ///
409            /// See
410            #[doc= concat!("[`slotmap::", stringify!($mapname), "::get_mut()`].")]
411            pub fn get_mut(&mut self, key: K) -> Option<&mut V> {
412                self.base.get_mut(key).and_then(|ent| ent.value_mut())
413            }
414
415            /// Return an array of mutable references to the elements of this map with a given list
416            /// of keys.
417            ///
418            /// Return None if any key is not present, or if the same key is given twice.
419            ///
420            /// See
421            #[doc= concat!("[`slotmap::", stringify!($mapname), "::get_disjoint_mut()`].")]
422            pub fn get_disjoint_mut<const N: usize>(&mut self, keys: [K; N]) -> Option<[&mut V; N]> {
423                let vals = self.base.get_disjoint_mut(keys)?;
424                // TODO array::try_map would be preferable, but it isn't stable.
425                if vals.iter().all(|e| matches!(e, Entry::Present(_))) {
426                    // Cannot panic, since we checked that every entry is present.
427                    Some(vals.map(|v| match v {
428                        Entry::Present(v) => v,
429                        Entry::Unusable => panic!("Logic error"),
430                    }))
431                } else {
432                    None
433                }
434            }
435
436            /// Return an iterator over the elements of this map.
437            ///
438            /// See
439            #[doc= concat!("[`slotmap::", stringify!($mapname), "::iter()`].")]
440            ///
441            /// # Current limitations
442            ///
443            /// Does not return a named type.
444            pub fn iter(&self) -> impl Iterator<Item = (K, &V)> + '_ {
445                self.base.iter().filter_map(|(k, v)| match v {
446                    Entry::Present(v) => Some((k, v)),
447                    Entry::Unusable => None,
448                })
449            }
450
451            /// Remove every element of this map.
452            ///
453            /// See
454            #[doc= concat!("[`slotmap::", stringify!($mapname), "::drain()`].")]
455            pub fn drain(&mut self) -> impl Iterator<Item = (K, V)> + '_ {
456                self.base.drain().filter_map(|(k, v)| match v {
457                    Entry::Present(v) => Some((k, v)),
458                    Entry::Unusable => None,
459                })
460            }
461
462            /// Return a mutable iterator over the elements of this map.
463            ///
464            /// See
465            #[doc= concat!("[`slotmap::", stringify!($mapname), "::iter_mut()`].")]
466            ///
467            /// # Current limitations
468            ///
469            /// Does not return a named type.
470            pub fn iter_mut(&mut self) -> impl Iterator<Item = (K, &mut V)> + '_ {
471                self.base.iter_mut().filter_map(|(k, v)| match v {
472                    Entry::Present(v) => Some((k, v)),
473                    Entry::Unusable => None,
474                })
475            }
476
477            /// Return an iterator over all the keys in this map.
478            ///
479            /// See
480            #[doc= concat!("[`slotmap::", stringify!($mapname), "::keys()`].")]
481            ///
482            /// # Current limitations
483            ///
484            /// Does not return a named type.
485            pub fn keys(&self) -> impl Iterator<Item = K> + '_ {
486                self.iter().map(|(k, _)| k)
487            }
488
489            /// Return an iterator over the values in this map.
490            ///
491            /// See
492            #[doc= concat!("[`slotmap::", stringify!($mapname), "::values()`].")]
493            ///
494            /// # Current limitations
495            ///
496            /// Does not return a named type.
497            pub fn values(&self) -> impl Iterator<Item = &V> + '_ {
498                self.base.values().filter_map(Entry::value)
499            }
500
501            /// Return a mutable iterator over the values in this map.
502            ///
503            /// See
504            #[doc= concat!("[`slotmap::", stringify!($mapname), "::values_mut()`].")]
505            ///
506            /// # Current limitations
507            ///
508            /// Does not return a named type.
509            pub fn values_mut(&mut self) -> impl Iterator<Item = &mut V> + '_ {
510                self.base.values_mut().filter_map(Entry::value_mut)
511            }
512
513            /// Testing helper: Assert that every invariant holds for this map.
514            ///
515            /// # Panics
516            ///
517            /// Panics if any invariant does not hold.
518            #[cfg(test)]
519            fn assert_rep_ok(&self) {
520                let mut n_unusable_found = 0;
521                for (k, v) in self.base.iter() {
522                    assert!(key_okay(k), "Key {:?} was invalid", k.data());
523                    if matches!(v, Entry::Unusable) {
524                        n_unusable_found += 1;
525                        assert_eq!(key_version(k), SATURATE_AT_VERSION);
526                    }
527                }
528                assert_eq!(n_unusable_found, self.n_unusable);
529            }
530        }
531
532        /// Helper: a token constructed if the slotmap behavior matches our expectations.
533        ///
534        /// See `validate_*_behavior()`
535        #[derive(Clone, Debug)]
536        struct [<$mapname ValidationToken>];
537
538        /// Spot-check whether `SlotMap` has changed its key encoding behavior; panic if so.
539        ///
540        /// (Our implementation relies on our ability to check whether a version number is about to
541        /// overflow. But the only efficient way to access a version number is via `KeyData::as_ffi`,
542        /// which does not guarantee anything about the actual encoding of the versions.)
543        ///
544        /// This function returns a ZST ValidationToken; nothing else must return one.
545        /// Being able to construct a ValidationToken implies
546        /// that `slotmap` has probably not changed its behavior in a way that will break us.
547        ///
548        /// # Panics
549        ///
550        /// May panic if slotmap does not encode its keys in the expected manner.
551        fn [<validate_ $mapname:snake _behavior>]() -> [<$mapname ValidationToken>] {
552            use std::sync::atomic::{AtomicBool, Ordering::Relaxed};
553            /// Helper:
554            static VALIDATED: AtomicBool = AtomicBool::new(false);
555            if VALIDATED.load(Relaxed) {
556                // We have already validated it at least once.
557                return [<$mapname ValidationToken>];
558            }
559            /// Helper: assert that key has bit 32 set.
560            fn ver_lsb_check<K: Key>(key: K) {
561                let (ver, _) = key_data::key_data_parts(key.data()).expect("slotmap has changed its serde representation");
562                assert_eq!(ver & 1, 1,
563                    "Key version LSB not set as expected"
564                );
565            }
566
567            let mut map = slotmap::$mapname::new();
568            let k1 = map.insert("a");
569            assert_eq!(key_version(k1), 0, "Keys do not begin with version 0.");
570            assert_eq!(key_slot(k1), 1, "Keys do not begin with index 1.");
571            ver_lsb_check(k1);
572
573            // This is a basic correctness check.
574            map.remove(k1).expect("insert+remove failed");
575            let k2 = map.insert("b");
576            assert_eq!(key_slot(k1), key_slot(k2), "Slot not re-used as expected.");
577            assert_eq!(
578                key_version(k1) + 1,
579                key_version(k2),
580                "Key version did not increment by 1 after slot reuse"
581            );
582            ver_lsb_check(k2);
583
584            let k3 = map.insert("c");
585            assert_eq!(
586                key_version(k3),
587                0,
588                "A different slot did not begin with version 0.",
589            );
590            assert_eq!(
591                key_slot(k3),
592                key_slot(k1) + 1,
593                "Slots not allocated in expected order."
594            );
595            ver_lsb_check(k3);
596
597            // Remember that we've validated SlotMap.
598            VALIDATED.store(true, Relaxed);
599            [<$mapname ValidationToken>]
600        }
601    }
602
603    impl<K:Key, V> std::ops::Index<K> for $mapname<K,V> {
604        type Output = V;
605        fn index(&self, key: K) -> &V {
606            self.get(key).expect("key invalid")
607        }
608    }
609    impl<K:Key, V> std::ops::IndexMut<K> for $mapname<K,V> {
610        fn index_mut(&mut self, key: K) -> &mut V {
611            self.get_mut(key).expect("key invalid")
612        }
613    }
614}} // END OF MACRO.
615
616define_implementation! { SlotMap }
617
618define_implementation! { DenseSlotMap }
619
620/// Return true if this key is apparently valid.
621///
622/// We should use debug_assert! to test this on every new key, every time an entry is inserted.
623///
624/// If inserting an entry results in a _not_ valid key,
625/// we have messed up, and allowed a version counter to grow too high.
626fn key_okay<K: Key>(key: K) -> bool {
627    key_version(key) <= SATURATE_AT_VERSION
628}
629
630/// Return true if the version number for this key should not be allowed to grow any larger.
631///
632/// We should call this whenever we are about to remove an entry with a given key.
633/// If it returns true, we should instead replace the entry with [`Entry::Unusable`]
634fn key_version_is_maximal<K: Key>(key: K) -> bool {
635    key_version(key) == SATURATE_AT_VERSION
636}
637/// The maximal version that we allow a key to reach.
638///
639/// When it reaches this version, we do not remove the entry with the key any longer;
640/// instead, when we would remove the entry, we instead set its value to [`Entry::Unusable`]
641///
642/// This value is deliberately chosen to be less than the largest possible value (`0x7fff_ffff`),
643/// so that we can detect any bugs that would risk overflowing the version.
644const SATURATE_AT_VERSION: u32 = 0x7fff_fffe;
645
646/// Helper: return the slot of a key, assuming that the representation is as we expect.
647///
648/// Used for testing and verify functions.
649fn key_slot<K: Key>(key: K) -> u32 {
650    let (_, idx) =
651        key_data::key_data_parts(key.data()).expect("slotmap has changed its serde representation");
652    idx
653}
654
655#[cfg(test)]
656mod test {
657    // @@ begin test lint list maintained by maint/add_warning @@
658    #![allow(clippy::bool_assert_comparison)]
659    #![allow(clippy::clone_on_copy)]
660    #![allow(clippy::dbg_macro)]
661    #![allow(clippy::mixed_attributes_style)]
662    #![allow(clippy::print_stderr)]
663    #![allow(clippy::print_stdout)]
664    #![allow(clippy::single_char_pattern)]
665    #![allow(clippy::unwrap_used)]
666    #![allow(clippy::unchecked_time_subtraction)]
667    #![allow(clippy::useless_vec)]
668    #![allow(clippy::needless_pass_by_value)]
669    #![allow(clippy::string_slice)] // See arti#2571
670    //! <!-- @@ end test lint list maintained by maint/add_warning @@ -->
671
672    /// Create a new key, using `ver` as its version field (includes trailing 1)
673    /// and `idx` as its index field.
674    fn construct_key(ver: u32, idx: u32) -> slotmap::DefaultKey {
675        let j = serde_json::json! {
676            {
677                "version": ver,
678                "idx": idx,
679            }
680        };
681        serde_json::from_value(j).expect("invalid representation")
682    }
683
684    /// Define a set of tests for one of the map variants, in a module named after that variant.
685    macro_rules! tests_for {
686            { $mapname:ident } => {paste::paste!{
687
688            mod [<$mapname:snake>] {
689
690                use slotmap::DefaultKey;
691                use crate::*;
692
693            #[test]
694            fn validate() {
695                let _tok = [<validate_ $mapname:snake _behavior>]();
696            }
697
698            #[test]
699            fn empty() {
700                let mut m: $mapname<DefaultKey, ()> = $mapname::default();
701
702                for _ in 1..=3 {
703                    assert_eq!(m.len(), 0);
704                    assert!(m.is_empty());
705                    m.assert_rep_ok();
706
707                    let k1 = m.insert(());
708                    let k2 = m.insert(());
709                    let k3 = m.insert(());
710                    m.remove(k1);
711                    m.remove(k2);
712                    m.remove(k3);
713                }
714            }
715
716            fn construct_near_saturated_slotmap() -> ($mapname<DefaultKey, String>, DefaultKey, DefaultKey) {
717                fn encode_ver(v: u32) -> u32 {
718                    (v << 1) | 1
719                }
720
721                let json = serde_json::json! {
722                    [
723                        // sentinel entry.
724                        { "value": null, "version": 0},
725                        { "value": {"Present": "hello"}, "version": encode_ver(SATURATE_AT_VERSION) },
726                        { "value": {"Present": "world"}, "version": encode_ver(SATURATE_AT_VERSION - 2) }
727                    ]
728                };
729
730                let m = $mapname {
731                    base: serde_json::from_value(json).expect("invalid json"),
732                    n_unusable: 0,
733                    _valid: [<validate_ $mapname:snake _behavior>](),
734                };
735                let mut k1 = None;
736                let mut k2 = None;
737
738                for (k, v) in m.iter() {
739                    if v == "hello" {
740                        k1 = Some(k);
741                    }
742                    if v == "world" {
743                        k2 = Some(k);
744                    }
745                }
746                let (k1, k2) = (k1.unwrap(), k2.unwrap());
747                (m, k1, k2)
748            }
749
750            #[test]
751            fn saturating() {
752                let (mut m, k1, k2) = construct_near_saturated_slotmap();
753
754                assert_eq!(key_version(k1), SATURATE_AT_VERSION);
755                assert_eq!(key_version(k2), SATURATE_AT_VERSION - 2);
756
757                // Replace k1, and make sure that the index is _not_ reused.
758                let v = m.remove(k1);
759                assert_eq!(v.unwrap(), "hello");
760                assert!(matches!(m.base.get(k1), Some(Entry::Unusable)));
761                let k1_new = m.insert("HELLO".into());
762                assert_ne!(key_slot(k1), key_slot(k1_new));
763                assert_eq!(key_version(k1_new), 0);
764                assert!(matches!(m.base.get(k1), Some(Entry::Unusable)));
765                assert_eq!(m.get(k1_new).unwrap(), "HELLO");
766                assert!(m.get(k1).is_none());
767                m.assert_rep_ok();
768
769                // Replace k2 and make sure that that the index gets reused twice.
770                let v = m.remove(k2);
771                assert_eq!(v.unwrap(), "world");
772                let k2_2 = m.insert("WoRlD".into());
773                assert_eq!(key_version(k2_2), SATURATE_AT_VERSION - 1);
774                m.remove(k2_2);
775                m.assert_rep_ok();
776                assert!(m.base.get(k2_2).is_none());
777                let k2_3 = m.insert("WORLD".into());
778                assert_eq!(key_slot(k2), key_slot(k2_2));
779                assert_eq!(key_slot(k2), key_slot(k2_3));
780                assert_eq!(key_version(k2_3), SATURATE_AT_VERSION);
781                m.remove(k2_3);
782                assert!(m.base.get(k2_2).is_none());
783                m.assert_rep_ok();
784
785                let k2_4 = m.insert("World!".into());
786                assert!(matches!(m.base.get(k2_3), Some(Entry::Unusable)));
787                assert_eq!(m.get(k2_4).unwrap(), "World!");
788                assert_ne!(key_slot(k2_4), key_slot(k2));
789                assert!(m.contains_key(k2_4));
790                assert!(!m.contains_key(k2_3));
791                m.assert_rep_ok();
792            }
793
794            #[test]
795            fn insert_variations() {
796                let mut m = $mapname::new();
797                let k1 = m.insert("hello".to_string());
798                let k2 = m.insert_with_key(|k| format!("{:?}", k));
799                let k3 = m
800                    .try_insert_with_key(|k| Result::<_, ()>::Ok(format!("{:?}", k)))
801                    .unwrap();
802                let () = m.try_insert_with_key(|_k| Err(())).unwrap_err();
803
804                assert!(m.contains_key(k1));
805                assert!(m.contains_key(k2));
806                assert!(m.contains_key(k3));
807                assert_eq!(m.len(), 3);
808            }
809
810            #[test]
811            fn remove_large_but_bogus() {
812                let mut m: $mapname<DefaultKey, String> = $mapname::with_capacity(0);
813                let _k1 = m.insert("hello".to_string());
814                // Construct a key with maximal version (so we would expect to freeze it),
815                // but which won't actually be present.
816                let k_fake = super::construct_key((SATURATE_AT_VERSION << 1) | 1, 1);
817
818                let v = m.remove(k_fake);
819                assert!(v.is_none());
820                m.assert_rep_ok();
821            }
822
823            #[test]
824            fn remove_many_times() {
825                let (mut m, k1, _k2) = construct_near_saturated_slotmap();
826
827                let mut n_removed = 0;
828                for _ in 0..10 {
829                    if m.remove(k1).is_some() {
830                        n_removed += 1;
831                    }
832                    m.assert_rep_ok();
833                    assert_eq!(m.n_unusable, 1);
834                    assert_eq!(m.len(), 1);
835                }
836                assert_eq!(n_removed, 1);
837            }
838
839            #[test]
840            fn clear() {
841                let (mut m, k1, k2) = construct_near_saturated_slotmap();
842                assert_eq!(m.len(), 2);
843                assert_eq!(m.is_empty(), false);
844                assert_eq!(m.n_unusable, 0);
845
846                for _ in 0..=2 {
847                    m.clear();
848                    m.assert_rep_ok();
849
850                    assert_eq!(m.len(), 0);
851                    assert_eq!(m.is_empty(), true);
852                    assert!(m.get(k1).is_none());
853                    assert!(m.get(k2).is_none());
854                    assert!(matches!(m.base.get(k1), Some(Entry::Unusable)));
855                    assert_eq!(m.n_unusable, 1);
856                }
857
858                let k_next = m.insert("probe".into());
859                assert_eq!(key_slot(k_next), key_slot(k2));
860                assert_eq!(key_version(k_next), SATURATE_AT_VERSION - 1);
861            }
862
863            #[test]
864            fn retain() {
865                let (mut m, k1, k2) = construct_near_saturated_slotmap();
866
867                // drop all but the nearly-saturated (but not saturated) "world" item.
868                m.retain(|_k, v| v == "world");
869                m.assert_rep_ok();
870                assert_eq!(m.len(), 1);
871                assert!(!m.is_empty());
872                assert_eq!(m.n_unusable, 1);
873                assert_eq!(m.contains_key(k1), false);
874                assert_eq!(m.contains_key(k2), true);
875                assert_eq!(m.base.contains_key(k1), true); // key still internally present as Unusable.
876
877                let (mut m, k1, k2) = construct_near_saturated_slotmap();
878
879                // drop all but the saturated (but not saturated) "hello" item.
880                m.retain(|_k, v| v == "hello");
881                m.assert_rep_ok();
882                assert_eq!(m.len(), 1);
883                assert!(!m.is_empty());
884                assert_eq!(m.n_unusable, 0);
885                assert_eq!(m.contains_key(k1), true);
886                assert_eq!(m.contains_key(k2), false);
887                assert_eq!(m.base.contains_key(k2), false); // key not present.
888            }
889
890            #[test]
891            fn retain_and_panic() {
892                use std::panic::AssertUnwindSafe;
893                let (mut m, k1, _k2) = construct_near_saturated_slotmap();
894
895                let _ = std::panic::catch_unwind(AssertUnwindSafe(|| {
896                    m.retain(|k,_| if k == k1 { false } else { panic!() })
897                })).unwrap_err();
898                m.assert_rep_ok();
899            }
900
901            #[test]
902            fn modify() {
903                let (mut m, k1, k2) = construct_near_saturated_slotmap();
904
905                *m.get_mut(k1).unwrap() = "HELLO".to_string();
906                *m.get_mut(k2).unwrap() = "WORLD".to_string();
907
908                let v: Vec<_> = m.values().collect();
909                assert_eq!(v, vec![&"HELLO".to_string(), &"WORLD".to_string()]);
910            }
911
912            #[test]
913            fn iterators() {
914                let (mut m, k1, k2) = construct_near_saturated_slotmap();
915
916                m.remove(k1);
917                assert_eq!(m.n_unusable, 1);
918
919                for v in m.values_mut() {
920                    *v = "WORLD".to_string();
921                }
922
923                let v: Vec<_> = m.values().collect();
924                assert_eq!(v, vec![&"WORLD".to_string()]);
925
926                let v: Vec<_> = m.iter().collect();
927                assert_eq!(v, vec![(k2, &"WORLD".to_string())]);
928
929                for (k, v) in m.iter_mut() {
930                    assert_eq!(k, k2);
931                    *v = "World".to_string();
932                }
933
934                let v: Vec<_> = m.iter().collect();
935                assert_eq!(v, vec![(k2, &"World".to_string())]);
936
937                let v: Vec<_> = m.keys().collect();
938                assert_eq!(v, vec![k2]);
939
940                m.assert_rep_ok();
941            }
942
943            #[test]
944            fn get_mut_multiple() {
945                let (mut m, k1, k2) = construct_near_saturated_slotmap();
946
947                assert!(m.get_disjoint_mut([k1,k1]).is_none());
948
949                if let Some([v1, v2]) = m.get_disjoint_mut([k1, k2]) {
950                    assert_eq!(v1, "hello");
951                    assert_eq!(v2, "world");
952                    *v1 = "HELLO".into();
953                    *v2 = "WORLD".into();
954                } else {
955                    panic!("get_disjoint_mut failed.");
956                };
957
958                m.remove(k1);
959                assert_eq!(m.contains_key(k1), false);
960                assert_eq!(m.base.contains_key(k1), true);
961                m.assert_rep_ok();
962
963                if let Some([_v1, _v2]) = m.get_disjoint_mut([k1, k2]) {
964                    panic!("get_disjoint_mut succeeded unexpectedly.")
965                }
966            }
967
968            #[test]
969            fn get_capacity() {
970                let (mut m, k1, _) = construct_near_saturated_slotmap();
971
972                let cap_orig = dbg!(m.capacity());
973                m.remove(k1);
974                m.assert_rep_ok();
975
976                assert_eq!(m.n_unusable, 1);
977                assert_eq!(m.capacity(), cap_orig - 1); // capacity decreased, since there is an unusable slot.
978
979                m.reserve(5);
980                assert!(m.capacity() >= 5);
981            }
982
983            #[test]
984            fn index() {
985                let (mut m, k1, k2) = construct_near_saturated_slotmap();
986
987                assert_eq!(m[k1], "hello");
988                assert_eq!(*(&mut m[k2]), "world");
989            }
990        } // end module.
991        }}} // End macro rules
992
993    tests_for! {SlotMap}
994    tests_for! {DenseSlotMap}
995}