1
#![cfg_attr(docsrs, feature(doc_auto_cfg, 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
#![warn(clippy::cognitive_complexity)]
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
#![deny(clippy::print_stderr)]
28
#![deny(clippy::print_stdout)]
29
#![warn(clippy::rc_buffer)]
30
#![deny(clippy::ref_option_ref)]
31
#![warn(clippy::semicolon_if_nothing_returned)]
32
#![warn(clippy::trait_duplication_in_bounds)]
33
#![deny(clippy::unchecked_duration_subtraction)]
34
#![deny(clippy::unnecessary_wraps)]
35
#![warn(clippy::unseparated_literal_suffix)]
36
#![deny(clippy::unwrap_used)]
37
#![deny(clippy::mod_module_files)]
38
#![allow(clippy::let_unit_value)] // This can reasonably be done for explicitness
39
#![allow(clippy::uninlined_format_args)]
40
#![allow(clippy::significant_drop_in_scrutinee)] // arti/-/merge_requests/588/#note_2812945
41
#![allow(clippy::result_large_err)] // temporary workaround for arti#587
42
#![allow(clippy::needless_raw_string_hashes)] // complained-about code is fine, often best
43
#![allow(clippy::needless_lifetimes)] // See arti#1765
44
//! <!-- @@ end lint list maintained by maint/add_warning @@ -->
45

            
46
mod key_data;
47

            
48
pub use slotmap::{
49
    new_key_type, secondary, DefaultKey, Key, KeyData, SecondaryMap, SparseSecondaryMap,
50
};
51

            
52
use key_data::key_version_serde as key_version;
53

            
54
//use key_version::key_version_serde;
55

            
56
/// A single entry in one of our careful slotmaps.
57
///
58
/// An entry can either be `Present` (in which case we treat it normally),
59
/// or `Unusable`, in which case we
60
#[cfg_attr(test, derive(serde::Serialize, serde::Deserialize))]
61
#[derive(Debug, Clone)]
62
enum Entry<V> {
63
    /// The entry is available.
64
    Present(V),
65
    /// The entry can no longer be used, removed, or set to anything else.
66
    ///
67
    /// It must not be removed from the slot map, since doing so would
68
    /// increase its slot's version number too high.
69
    Unusable,
70
}
71

            
72
impl<V> Entry<V> {
73
    /// Remove the value of `self` (if any), and make it unusable.
74
90
    fn take_and_mark_unusable(&mut self) -> Option<V> {
75
90
        match std::mem::replace(self, Entry::Unusable) {
76
36
            Entry::Present(v) => Some(v),
77
54
            Entry::Unusable => None,
78
        }
79
90
    }
80
    /// Return a reference to the value of `self`, if there is one.
81
21740
    fn value(&self) -> Option<&V> {
82
21740
        match self {
83
21692
            Entry::Present(val) => Some(val),
84
48
            Entry::Unusable => None,
85
        }
86
21740
    }
87
    /// Return a mutable reference to the value of `self``, if there is one.
88
6487726
    fn value_mut(&mut self) -> Option<&mut V> {
89
6487726
        match self {
90
6487720
            Entry::Present(val) => Some(val),
91
6
            Entry::Unusable => None,
92
        }
93
6487726
    }
94
    /// Consume this entry (which must be `Present`), and return its value.
95
    ///
96
    /// # Panics
97
    ///
98
    /// Panics if this entry is `Unusable`.
99
56692
    fn unwrap(self) -> V {
100
56692
        match self {
101
56692
            Entry::Present(val) => val,
102
            Entry::Unusable => panic!("Tried to unwrap an unusable slot."),
103
        }
104
56692
    }
105
}
106

            
107
/// Helper: Define a wrapper for a single SlotMap type.
108
///
109
/// This works for SlotMap, DenseSlotMap, and HopSlotMap.
110
///
111
/// (The alternative to using a macro here would be to define a new trait
112
/// implemented by all of the SlotMaps, and then to define our own SlotMap as a wrapper around an
113
/// instance of that trait.)
114
macro_rules! define_implementation {
115
        { $mapname:ident } => {paste::paste!{
116

            
117
        /// A variation of
118
        #[doc = concat!("[`slotmap::", stringify!($mapname), "`]")]
119
        /// that can never give the same key for multiple objects.
120
        ///
121
        /// Unlike a regular version of
122
        #[doc = concat!("`", stringify!($mapname), "`,")]
123
        /// this version will not allow a slot's version counter to roll over to
124
        /// 0 if it reaches 2^31.  Instead, it will mark the slot as unusable for future values.
125
        ///
126
        /// # Limitations
127
        ///
128
        /// The possibility of marking a slot as unusable
129
        /// makes it possible, given enough removals and re-insertions,
130
        /// for a slotmap to use an unbounded amount of memory, even if it is not storing much actual data.
131
        /// (From a DOS point of view: Given the ability to re-insert an entry ~2^31 times, an attacker can
132
        /// cause a slot-map to render approximately `4+sizeof(V)` bytes unusable.)
133
        ///
134
        /// This type does not include implementations for:
135
        ///   * `get_unchecked_mut()`
136
        ///   * `get_disjoint_unchecked_mut()`
137
        ///   * `IntoIterator`.
138
        ///   * `serde::{Serialize, Deserialize}`.
139
        ///
140
        /// # Risky business!
141
        ///
142
        /// This code relies upon stability of some undocumented properties of `slotmap` keys.
143
        /// In particular, it assumes:
144
        ///  * that the slotmap KeyData `serde` format is stable,
145
        ///  * that slot versions are represented as `u32`.
146
        ///  * that the least significant bit of a slot version is 1 if the slot is full,
147
        ///    and 0 if the slot is empty.
148
        ///  * that slot versions start at 0, and increase monotonically as the slot is
149
        ///    emptied and reused.
150
        ///
151
        /// Note that these assumptions are _probably_ okay: if `slotmap` were to change them,
152
        /// it would thereby create a breaking change in its serde version.
153
        //
154
        // Invariants:
155
        //
156
        // For every `(key,value)` that is present in `base`:
157
        //   - `key_okay(key)` is true.
158
        //   - if `value` is `Entry::Unusable`, then `key_version(key) == SATURATE_AT_VERSION`.
159
        //
160
        // `n_unusable` is the number of entries in `base` whose value is `Entry::Unusable`.
161
        //
162
        // To maintain these invariants:
163
        //   - Never remove a key with `key_version(key) == SATURATE_AT_VERSION`
164
        //   - Whenever setting a value to `Unusable`, increment `n_unusable`.
165
        #[derive(Clone, Debug)]
166
        pub struct $mapname<K: Key, V> {
167
            /// An underlying SlotMap, obeying the invariants above.
168
            base: slotmap::$mapname<K, Entry<V>>,
169
            /// The number of entries in this SlotMap that are filled with [`Entry::Unusable`] values.
170
            n_unusable: usize,
171
            /// A ZST, used to guarantee that we have spot-checked the behavior of the underlying
172
            /// SlotMap implementation.
173
            _valid: [<$mapname ValidationToken>],
174
        }
175

            
176
        impl<V> $mapname<DefaultKey, V> {
177
            /// Construct a new empty map, using a default key type.
178
            ///
179
            /// See
180
            #[doc = concat!("[`slotmap::", stringify!($mapname), "::new()`].")]
181
6
            pub fn new() -> Self {
182
6
                Self::with_key()
183
6
            }
184

            
185
            /// Construct a new empty map with a specified capacity, using a default key type.
186
            ///
187
            /// See
188
            #[doc = concat!("[`slotmap::", stringify!($mapname), "::with_capacity()`].")]
189
            /// ::with_capacity()`].
190
6
            pub fn with_capacity(capacity: usize) -> Self {
191
6
                Self::with_capacity_and_key(capacity)
192
6
            }
193
        }
194

            
195
        impl<K: Key, V> Default for $mapname<K, V> {
196
99872
            fn default() -> Self {
197
99872
                Self::with_key()
198
99872
            }
199
        }
200

            
201
        impl<K: Key, V> $mapname<K, V> {
202
            /// Construct a new empty map, using a specialized key type.
203
            ///
204
            /// See
205
            #[doc= concat!("[`slotmap::", stringify!($mapname), "::with_key()`].")]
206
100401
            pub fn with_key() -> Self {
207
100401
                Self::with_capacity_and_key(0)
208
100401
            }
209

            
210
            /// Construct a new empty map with a specified capacity, using a specialized key type.
211
            ///
212
            /// See
213
            #[doc= concat!("[`slotmap::", stringify!($mapname), "::with_capacity_and_key()`].")]
214
100407
            pub fn with_capacity_and_key(capacity: usize) -> Self {
215
100407
                Self {
216
100407
                    base: slotmap::$mapname::with_capacity_and_key(capacity),
217
100407
                    n_unusable: 0,
218
100407
                    _valid: [<validate_ $mapname:snake _behavior>](),
219
100407
                }
220
100407
            }
221

            
222
            /// Return the number of items in this map.
223
            ///
224
            /// See
225
            #[doc= concat!("[`slotmap::", stringify!($mapname), "::len()`].")]
226
2662
            pub fn len(&self) -> usize {
227
2662
                self.base
228
2662
                    .len()
229
2662
                    .checked_sub(self.n_unusable)
230
2662
                    .expect("logic error")
231
2662
            }
232

            
233
            /// Return true if this map has no items.
234
            ///
235
            /// See
236
            #[doc= concat!("[`slotmap::", stringify!($mapname), "::is_empty()`].")]
237
54
            pub fn is_empty(&self) -> bool {
238
54
                self.len() == 0
239
54
            }
240

            
241
            /// Return the total number of slots available for entries in this map.
242
            ///
243
            /// This number includes used slots, as well as empty slots that may become used.
244
            ///
245
            /// See
246
            #[doc= concat!("[`slotmap::", stringify!($mapname), "::capacity()`],")]
247
            /// but note that a `slotmap-careful` implementation may _lose_ capacity over time,
248
            /// as slots are marked unusable.
249
2296
            pub fn capacity(&self) -> usize {
250
2296
                self.base
251
2296
                    .capacity()
252
2296
                    .checked_sub(self.n_unusable)
253
2296
                    .expect("logic error")
254
2296
            }
255

            
256
            /// Reserve space as needed.
257
            ///
258
            /// Allocates if needed, so that this map can hold `additional` new entries
259
            /// without having to resize.
260
            ///
261
            /// See
262
            #[doc= concat!("[`slotmap::", stringify!($mapname), "::reserve()`].")]
263
18
            pub fn reserve(&mut self, additional: usize) {
264
18
                // Note that we don't need to check n_unusable here: the underlying
265
18
                // map type thinks that unusable entries are full, and so will allocate
266
18
                // correctly.
267
18
                self.base.reserve(additional);
268
18
            }
269

            
270
            /// Return true if the map contains an entry with a given key.
271
            ///
272
            /// See
273
            #[doc= concat!("[`slotmap::", stringify!($mapname), "::contains_key()`].")]
274
60
            pub fn contains_key(&self, key: K) -> bool {
275
60
                // Calling self.get, not self.base.get, so it will be None if the
276
60
                // slot is unusable.
277
60
                self.get(key).is_some()
278
60
            }
279

            
280
            /// Insert a new value into the map, and return the key used for it.
281
            ///
282
            /// See
283
            #[doc= concat!("[`slotmap::", stringify!($mapname), "::insert()`].")]
284
96174
            pub fn insert(&mut self, value: V) -> K {
285
96174
                let key = self.base.insert(Entry::Present(value));
286
96174
                debug_assert!(key_okay(key));
287
96174
                key
288
96174
            }
289

            
290
            /// Insert a new value into the map, constructing it using its own new key.
291
            ///
292
            /// This method is useful for the case where a value needs to refer to the
293
            /// key that will be assigned to it.
294
            ///
295
            /// See
296
            #[doc= concat!("[`slotmap::", stringify!($mapname), "::insert_with_key()`].")]
297
6
            pub fn insert_with_key<F>(&mut self, f: F) -> K
298
6
            where
299
6
                F: FnOnce(K) -> V,
300
6
            {
301
6
                let key = self.base.insert_with_key(|k| Entry::Present(f(k)));
302
6
                debug_assert!(key_okay(key));
303
6
                key
304
6
            }
305

            
306
            /// As [`Self::insert_with_key`], but may return an `Err`.
307
            ///
308
            /// See
309
            #[doc= concat!("[`slotmap::", stringify!($mapname), "::try_insert_with_key()`].")]
310
12
            pub fn try_insert_with_key<F, E>(&mut self, f: F) -> Result<K, E>
311
12
            where
312
12
                F: FnOnce(K) -> Result<V, E>,
313
12
            {
314
12
                let key = self
315
12
                    .base
316
12
                    .try_insert_with_key(|k| Ok(Entry::Present(f(k)?)))?;
317
6
                debug_assert!(key_okay(key));
318
6
                Ok(key)
319
12
            }
320

            
321
            /// Remove and return the element of this map with a given key.
322
            ///
323
            /// Return None if the key is not present in the map.
324
            ///
325
            /// See
326
            #[doc= concat!("[`slotmap::", stringify!($mapname), "::remove()`].")]
327
56800
            pub fn remove(&mut self, key: K) -> Option<V> {
328
56800
                if key_version_is_maximal(key) {
329
                    // The key is as large as it is allowed to get,
330
                    // so we should not actually remove this Entry.
331
96
                    match self.base.get_mut(key) {
332
90
                        Some(slot) => {
333
90
                            // The entry is Present: extract its value and mark it unusable.
334
90
                            let rv = slot.take_and_mark_unusable();
335
90
                            if rv.is_some() {
336
36
                                self.n_unusable += 1;
337
54
                            }
338
90
                            rv
339
                        }
340
                        // The entry is Unusable; treat it as if it weren't there.
341
6
                        None => None,
342
                    }
343
                } else {
344
                    // The Entry::unwrap function will panic if its argument is
345
                    // Entry::Unusable.  But that is impossible in this case,
346
                    // since we already checked key_version_is_maximal() for this key,
347
                    // and our invariant guarantees that, if the value is Entry::Unusable,
348
                    // then key_version(key) == SATURATE_AT_VERSION,
349
                    // so key_version_is_maximal is true.
350
56704
                    self.base.remove(key).map(Entry::unwrap)
351
                }
352
56800
            }
353

            
354
            /// Remove every element of this map that does not satisfy a given predicate.
355
            ///
356
            /// See
357
            #[doc= concat!("[`slotmap::", stringify!($mapname), "::retain()`].")]
358
280
            pub fn retain<F>(&mut self, mut f: F)
359
280
            where
360
280
                F: FnMut(K, &mut V) -> bool,
361
280
            {
362
3728
                self.base.retain(|k, v| {
363
3728
                    let Entry::Present(v_inner) = v else {
364
12
                        return true;
365
                    };
366

            
367
3716
                    if f(k, v_inner) {
368
1676
                        true
369
2040
                    } else if key_version_is_maximal(k) {
370
18
                        self.n_unusable += 1;
371
18
                        *v = Entry::Unusable;
372
18
                        true
373
                    } else {
374
2016
                        false
375
                    }
376
3722
                });
377
280
            }
378

            
379
            /// Remove every element of this map.
380
            ///
381
            /// See
382
            #[doc= concat!("[`slotmap::", stringify!($mapname), "::clear()`].")]
383
18
            pub fn clear(&mut self) {
384
18
                self.retain(|_, _| false);
385
18
            }
386

            
387
            /// Return a reference to the element of this map with a given key.
388
            ///
389
            /// Return None if there is no such element.
390
            ///
391
            /// See
392
            #[doc= concat!("[`slotmap::", stringify!($mapname), "::get()`].")]
393
23570
            pub fn get(&self, key: K) -> Option<&V> {
394
23570
                self.base.get(key).and_then(Entry::value)
395
23570
            }
396
            /// Return a mutable 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_mut()`].")]
402
6491191
            pub fn get_mut(&mut self, key: K) -> Option<&mut V> {
403
6491191
                self.base.get_mut(key).and_then(|ent| ent.value_mut())
404
6491191
            }
405

            
406
            /// Return an array of mutable references to the elements of this map with a given list
407
            /// of keys.
408
            ///
409
            /// Return None if any key is not present, or if the same key is given twice.
410
            ///
411
            /// See
412
            #[doc= concat!("[`slotmap::", stringify!($mapname), "::get_disjoint_mut()`].")]
413
18
            pub fn get_disjoint_mut<const N: usize>(&mut self, keys: [K; N]) -> Option<[&mut V; N]> {
414
18
                let vals = self.base.get_disjoint_mut(keys)?;
415
                // TODO array::try_map would be preferable, but it isn't stable.
416
18
                if vals.iter().all(|e| matches!(e, Entry::Present(_))) {
417
                    // Cannot panic, since we checked that every entry is present.
418
12
                    Some(vals.map(|v| match v {
419
12
                        Entry::Present(v) => v,
420
                        Entry::Unusable => panic!("Logic error"),
421
12
                    }))
422
                } else {
423
6
                    None
424
                }
425
18
            }
426

            
427
            /// Return an iterator over the elements of this map.
428
            ///
429
            /// See
430
            #[doc= concat!("[`slotmap::", stringify!($mapname), "::iter()`].")]
431
            ///
432
            /// # Current limitations
433
            ///
434
            /// Does not return a named type.
435
82224
            pub fn iter(&self) -> impl Iterator<Item = (K, &V)> + '_ {
436
104648
                self.base.iter().filter_map(|(k, v)| match v {
437
104630
                    Entry::Present(v) => Some((k, v)),
438
18
                    Entry::Unusable => None,
439
104648
                })
440
82224
            }
441

            
442
            /// Remove every element of this map.
443
            ///
444
            /// See
445
            #[doc= concat!("[`slotmap::", stringify!($mapname), "::drain()`].")]
446
502
            pub fn drain(&mut self) -> impl Iterator<Item = (K, V)> + '_ {
447
564
                self.base.drain().filter_map(|(k, v)| match v {
448
384
                    Entry::Present(v) => Some((k, v)),
449
                    Entry::Unusable => None,
450
564
                })
451
502
            }
452

            
453
            /// Return a mutable iterator over the elements of this map.
454
            ///
455
            /// See
456
            #[doc= concat!("[`slotmap::", stringify!($mapname), "::iter_mut()`].")]
457
            ///
458
            /// # Current limitations
459
            ///
460
            /// Does not return a named type.
461
38
            pub fn iter_mut(&mut self) -> impl Iterator<Item = (K, &mut V)> + '_ {
462
144
                self.base.iter_mut().filter_map(|(k, v)| match v {
463
138
                    Entry::Present(v) => Some((k, v)),
464
6
                    Entry::Unusable => None,
465
144
                })
466
38
            }
467

            
468
            /// Return an iterator over all the keys in this map.
469
            ///
470
            /// See
471
            #[doc= concat!("[`slotmap::", stringify!($mapname), "::keys()`].")]
472
            ///
473
            /// # Current limitations
474
            ///
475
            /// Does not return a named type.
476
20
            pub fn keys(&self) -> impl Iterator<Item = K> + '_ {
477
38
                self.iter().map(|(k, _)| k)
478
20
            }
479

            
480
            /// Return an iterator over the values in this map.
481
            ///
482
            /// See
483
            #[doc= concat!("[`slotmap::", stringify!($mapname), "::values()`].")]
484
            ///
485
            /// # Current limitations
486
            ///
487
            /// Does not return a named type.
488
24
            pub fn values(&self) -> impl Iterator<Item = &V> + '_ {
489
24
                self.base.values().filter_map(Entry::value)
490
24
            }
491

            
492
            /// Return a mutable iterator over the values in this map.
493
            ///
494
            /// See
495
            #[doc= concat!("[`slotmap::", stringify!($mapname), "::values_mut()`].")]
496
            ///
497
            /// # Current limitations
498
            ///
499
            /// Does not return a named type.
500
14
            pub fn values_mut(&mut self) -> impl Iterator<Item = &mut V> + '_ {
501
14
                self.base.values_mut().filter_map(Entry::value_mut)
502
14
            }
503

            
504
            /// Testing helper: Assert that every invariant holds for this map.
505
            ///
506
            /// # Panics
507
            ///
508
            /// Panics if any invariant does not hold.
509
            #[cfg(test)]
510
162
            fn assert_rep_ok(&self) {
511
162
                let mut n_unusable_found = 0;
512
282
                for (k, v) in self.base.iter() {
513
282
                    assert!(key_okay(k), "Key {:?} was invalid", k.data());
514
282
                    if matches!(v, Entry::Unusable) {
515
144
                        n_unusable_found += 1;
516
144
                        assert_eq!(key_version(k), SATURATE_AT_VERSION);
517
138
                    }
518
                }
519
162
                assert_eq!(n_unusable_found, self.n_unusable);
520
162
            }
521
        }
522

            
523
        /// Helper: a token constructed if the slotmap behavior matches our expectations.
524
        ///
525
        /// See `validate_*_behavior()`
526
        #[derive(Clone, Debug)]
527
        struct [<$mapname ValidationToken>];
528

            
529
        /// Spot-check whether `SlotMap` has changed its key encoding behavior; panic if so.
530
        ///
531
        /// (Our implementation relies on our ability to check whether a version number is about to
532
        /// overflow. But the only efficient way to access a version number is via `KeyData::as_ffi`,
533
        /// which does not guarantee anything about the actual encoding of the versions.)
534
        ///
535
        /// This function returns a ZST ValidationToken; nothing else must return one.
536
        /// Being able to construct a ValidationToken implies
537
        /// that `slotmap` has probably not changed its behavior in a way that will break us.
538
        ///
539
        /// # Panics
540
        ///
541
        /// May panic if slotmap does not encode its keys in the expected manner.
542
177820
        fn [<validate_ $mapname:snake _behavior>]() -> [<$mapname ValidationToken>] {
543
            use std::sync::atomic::{AtomicBool, Ordering::Relaxed};
544
            /// Helper:
545
            static VALIDATED: AtomicBool = AtomicBool::new(false);
546
177820
            if VALIDATED.load(Relaxed) {
547
                // We have already validated it at least once.
548
176414
                return [<$mapname ValidationToken>];
549
1406
            }
550
            /// Helper: assert that key has bit 32 set.
551
4218
            fn ver_lsb_check<K: Key>(key: K) {
552
4218
                let (ver, _) = key_data::key_data_parts(key.data()).expect("slotmap has changed its serde representation");
553
4218
                assert_eq!(ver & 1, 1,
554
                    "Key version LSB not set as expected"
555
                );
556
4218
            }
557

            
558
1406
            let mut map = slotmap::$mapname::new();
559
1406
            let k1 = map.insert("a");
560
1406
            assert_eq!(key_version(k1), 0, "Keys do not begin with version 0.");
561
1406
            assert_eq!(key_slot(k1), 1, "Keys do not begin with index 1.");
562
1406
            ver_lsb_check(k1);
563
1406

            
564
1406
            // This is a basic correctness check.
565
1406
            map.remove(k1).expect("insert+remove failed");
566
1406
            let k2 = map.insert("b");
567
1406
            assert_eq!(key_slot(k1), key_slot(k2), "Slot not re-used as expected.");
568
1406
            assert_eq!(
569
1406
                key_version(k1) + 1,
570
1406
                key_version(k2),
571
                "Key version did not increment by 1 after slot reuse"
572
            );
573
1406
            ver_lsb_check(k2);
574
1406

            
575
1406
            let k3 = map.insert("c");
576
1406
            assert_eq!(
577
1406
                key_version(k3),
578
                0,
579
                "A different slot did not begin with version 0.",
580
            );
581
1406
            assert_eq!(
582
1406
                key_slot(k3),
583
1406
                key_slot(k1) + 1,
584
                "Slots not allocated in expected order."
585
            );
586
1406
            ver_lsb_check(k3);
587
1406

            
588
1406
            // Remember that we've validated SlotMap.
589
1406
            VALIDATED.store(true, Relaxed);
590
1406
            [<$mapname ValidationToken>]
591
177820
        }
592
    }
593

            
594
    impl<K:Key, V> std::ops::Index<K> for $mapname<K,V> {
595
        type Output = V;
596
102
        fn index(&self, key: K) -> &V {
597
102
            self.get(key).expect("key invalid")
598
102
        }
599
    }
600
    impl<K:Key, V> std::ops::IndexMut<K> for $mapname<K,V> {
601
6
        fn index_mut(&mut self, key: K) -> &mut V {
602
6
            self.get_mut(key).expect("key invalid")
603
6
        }
604
    }
605
}} // END OF MACRO.
606

            
607
define_implementation! { SlotMap }
608

            
609
define_implementation! { DenseSlotMap }
610

            
611
define_implementation! { HopSlotMap }
612

            
613
/// Return true if this key is apparently valid.
614
///
615
/// We should use debug_assert! to test this on every new key, every time an entry is inserted.
616
///
617
/// If inserting an entry results in a _not_ valid key,
618
/// we have messed up, and allowed a version counter to grow too high.
619
96468
fn key_okay<K: Key>(key: K) -> bool {
620
96468
    key_version(key) <= SATURATE_AT_VERSION
621
96468
}
622

            
623
/// Return true if the version number for this key should not be allowed to grow any larger.
624
///
625
/// We should call this whenever we are about to remove an entry with a given key.
626
/// If it returns true, we should instead replace the entry with [`Entry::Unusable`]
627
58834
fn key_version_is_maximal<K: Key>(key: K) -> bool {
628
58834
    key_version(key) == SATURATE_AT_VERSION
629
58834
}
630
/// The maximal version that we allow a key to reach.
631
///
632
/// When it reaches this version, we do not remove the entry with the key any longer;
633
/// instead, when we would remove the entry, we instead set its value to [`Entry::Unusable`]
634
///
635
/// This value is deliberately chosen to be less than the largest possible value (`0x7fff_ffff`),
636
/// so that we can detect any bugs that would risk overflowing the version.
637
const SATURATE_AT_VERSION: u32 = 0x7fff_fffe;
638

            
639
/// Helper: return the slot of a key, assuming that the representation is as we expect.
640
///
641
/// Used for testing and verify functions.
642
7090
fn key_slot<K: Key>(key: K) -> u32 {
643
7090
    let (_, idx) =
644
7090
        key_data::key_data_parts(key.data()).expect("slotmap has changed its serde representation");
645
7090
    idx
646
7090
}
647

            
648
#[cfg(test)]
649
mod test {
650
    // @@ begin test lint list maintained by maint/add_warning @@
651
    #![allow(clippy::bool_assert_comparison)]
652
    #![allow(clippy::clone_on_copy)]
653
    #![allow(clippy::dbg_macro)]
654
    #![allow(clippy::mixed_attributes_style)]
655
    #![allow(clippy::print_stderr)]
656
    #![allow(clippy::print_stdout)]
657
    #![allow(clippy::single_char_pattern)]
658
    #![allow(clippy::unwrap_used)]
659
    #![allow(clippy::unchecked_duration_subtraction)]
660
    #![allow(clippy::useless_vec)]
661
    #![allow(clippy::needless_pass_by_value)]
662
    //! <!-- @@ end test lint list maintained by maint/add_warning @@ -->
663

            
664
    /// Create a new key, using `ver` as its version field (includes trailing 1)
665
    /// and `idx` as its index field.
666
    fn construct_key(ver: u32, idx: u32) -> slotmap::DefaultKey {
667
        let j = serde_json::json! {
668
            {
669
                "version": ver,
670
                "idx": idx,
671
            }
672
        };
673
        serde_json::from_value(j).expect("invalid representation")
674
    }
675

            
676
    /// Define a set of tests for one of the map variants, in a module named after that variant.
677
    macro_rules! tests_for {
678
            { $mapname:ident } => {paste::paste!{
679

            
680
            mod [<$mapname:snake>] {
681

            
682
                use slotmap::DefaultKey;
683
                use crate::*;
684

            
685
            #[test]
686
            fn validate() {
687
                let _tok = [<validate_ $mapname:snake _behavior>]();
688
            }
689

            
690
            #[test]
691
            fn empty() {
692
                let mut m: $mapname<DefaultKey, ()> = $mapname::default();
693

            
694
                for _ in 1..=3 {
695
                    assert_eq!(m.len(), 0);
696
                    assert!(m.is_empty());
697
                    m.assert_rep_ok();
698

            
699
                    let k1 = m.insert(());
700
                    let k2 = m.insert(());
701
                    let k3 = m.insert(());
702
                    m.remove(k1);
703
                    m.remove(k2);
704
                    m.remove(k3);
705
                }
706
            }
707

            
708
            fn construct_near_saturated_slotmap() -> ($mapname<DefaultKey, String>, DefaultKey, DefaultKey) {
709
                fn encode_ver(v: u32) -> u32 {
710
                    (v << 1) | 1
711
                }
712

            
713
                let json = serde_json::json! {
714
                    [
715
                        // sentinel entry.
716
                        { "value": null, "version": 0},
717
                        { "value": {"Present": "hello"}, "version": encode_ver(SATURATE_AT_VERSION) },
718
                        { "value": {"Present": "world"}, "version": encode_ver(SATURATE_AT_VERSION - 2) }
719
                    ]
720
                };
721

            
722
                let m = $mapname {
723
                    base: serde_json::from_value(json).expect("invalid json"),
724
                    n_unusable: 0,
725
                    _valid: [<validate_ $mapname:snake _behavior>](),
726
                };
727
                let mut k1 = None;
728
                let mut k2 = None;
729

            
730
                for (k, v) in m.iter() {
731
                    if v == "hello" {
732
                        k1 = Some(k);
733
                    }
734
                    if v == "world" {
735
                        k2 = Some(k);
736
                    }
737
                }
738
                let (k1, k2) = (k1.unwrap(), k2.unwrap());
739
                (m, k1, k2)
740
            }
741

            
742
            #[test]
743
            #[allow(clippy::cognitive_complexity)]
744
            fn saturating() {
745
                let (mut m, k1, k2) = construct_near_saturated_slotmap();
746

            
747
                assert_eq!(key_version(k1), SATURATE_AT_VERSION);
748
                assert_eq!(key_version(k2), SATURATE_AT_VERSION - 2);
749

            
750
                // Replace k1, and make sure that the index is _not_ reused.
751
                let v = m.remove(k1);
752
                assert_eq!(v.unwrap(), "hello");
753
                assert!(matches!(m.base.get(k1), Some(Entry::Unusable)));
754
                let k1_new = m.insert("HELLO".into());
755
                assert_ne!(key_slot(k1), key_slot(k1_new));
756
                assert_eq!(key_version(k1_new), 0);
757
                assert!(matches!(m.base.get(k1), Some(Entry::Unusable)));
758
                assert_eq!(m.get(k1_new).unwrap(), "HELLO");
759
                assert!(m.get(k1).is_none());
760
                m.assert_rep_ok();
761

            
762
                // Replace k2 and make sure that that the index gets reused twice.
763
                let v = m.remove(k2);
764
                assert_eq!(v.unwrap(), "world");
765
                let k2_2 = m.insert("WoRlD".into());
766
                assert_eq!(key_version(k2_2), SATURATE_AT_VERSION - 1);
767
                m.remove(k2_2);
768
                m.assert_rep_ok();
769
                assert!(m.base.get(k2_2).is_none());
770
                let k2_3 = m.insert("WORLD".into());
771
                assert_eq!(key_slot(k2), key_slot(k2_2));
772
                assert_eq!(key_slot(k2), key_slot(k2_3));
773
                assert_eq!(key_version(k2_3), SATURATE_AT_VERSION);
774
                m.remove(k2_3);
775
                assert!(m.base.get(k2_2).is_none());
776
                m.assert_rep_ok();
777

            
778
                let k2_4 = m.insert("World!".into());
779
                assert!(matches!(m.base.get(k2_3), Some(Entry::Unusable)));
780
                assert_eq!(m.get(k2_4).unwrap(), "World!");
781
                assert_ne!(key_slot(k2_4), key_slot(k2));
782
                assert!(m.contains_key(k2_4));
783
                assert!(!m.contains_key(k2_3));
784
                m.assert_rep_ok();
785
            }
786

            
787
            #[test]
788
            fn insert_variations() {
789
                let mut m = $mapname::new();
790
                let k1 = m.insert("hello".to_string());
791
                let k2 = m.insert_with_key(|k| format!("{:?}", k));
792
                let k3 = m
793
                    .try_insert_with_key(|k| Result::<_, ()>::Ok(format!("{:?}", k)))
794
                    .unwrap();
795
                let () = m.try_insert_with_key(|_k| Err(())).unwrap_err();
796

            
797
                assert!(m.contains_key(k1));
798
                assert!(m.contains_key(k2));
799
                assert!(m.contains_key(k3));
800
                assert_eq!(m.len(), 3);
801
            }
802

            
803
            #[test]
804
            fn remove_large_but_bogus() {
805
                let mut m: $mapname<DefaultKey, String> = $mapname::with_capacity(0);
806
                let _k1 = m.insert("hello".to_string());
807
                // Construct a key with maximal version (so we would expect to freeze it),
808
                // but which won't actually be present.
809
                let k_fake = super::construct_key((SATURATE_AT_VERSION << 1) | 1, 1);
810

            
811
                let v = m.remove(k_fake);
812
                assert!(v.is_none());
813
                m.assert_rep_ok();
814
            }
815

            
816
            #[test]
817
            fn remove_many_times() {
818
                let (mut m, k1, _k2) = construct_near_saturated_slotmap();
819

            
820
                let mut n_removed = 0;
821
                for _ in 0..10 {
822
                    if m.remove(k1).is_some() {
823
                        n_removed += 1;
824
                    }
825
                    m.assert_rep_ok();
826
                    assert_eq!(m.n_unusable, 1);
827
                    assert_eq!(m.len(), 1);
828
                }
829
                assert_eq!(n_removed, 1);
830
            }
831

            
832
            #[test]
833
            fn clear() {
834
                let (mut m, k1, k2) = construct_near_saturated_slotmap();
835
                assert_eq!(m.len(), 2);
836
                assert_eq!(m.is_empty(), false);
837
                assert_eq!(m.n_unusable, 0);
838

            
839
                for _ in 0..=2 {
840
                    m.clear();
841
                    m.assert_rep_ok();
842

            
843
                    assert_eq!(m.len(), 0);
844
                    assert_eq!(m.is_empty(), true);
845
                    assert!(m.get(k1).is_none());
846
                    assert!(m.get(k2).is_none());
847
                    assert!(matches!(m.base.get(k1), Some(Entry::Unusable)));
848
                    assert_eq!(m.n_unusable, 1);
849
                }
850

            
851
                let k_next = m.insert("probe".into());
852
                assert_eq!(key_slot(k_next), key_slot(k2));
853
                assert_eq!(key_version(k_next), SATURATE_AT_VERSION - 1);
854
            }
855

            
856
            #[test]
857
            fn retain() {
858
                let (mut m, k1, k2) = construct_near_saturated_slotmap();
859

            
860
                // drop all but the nearly-saturated (but not saturated) "world" item.
861
                m.retain(|_k, v| v == "world");
862
                m.assert_rep_ok();
863
                assert_eq!(m.len(), 1);
864
                assert!(!m.is_empty());
865
                assert_eq!(m.n_unusable, 1);
866
                assert_eq!(m.contains_key(k1), false);
867
                assert_eq!(m.contains_key(k2), true);
868
                assert_eq!(m.base.contains_key(k1), true); // key still internally present as Unusable.
869

            
870
                let (mut m, k1, k2) = construct_near_saturated_slotmap();
871

            
872
                // drop all but the saturated (but not saturated) "hello" item.
873
                m.retain(|_k, v| v == "hello");
874
                m.assert_rep_ok();
875
                assert_eq!(m.len(), 1);
876
                assert!(!m.is_empty());
877
                assert_eq!(m.n_unusable, 0);
878
                assert_eq!(m.contains_key(k1), true);
879
                assert_eq!(m.contains_key(k2), false);
880
                assert_eq!(m.base.contains_key(k2), false); // key not present.
881
            }
882

            
883
            #[test]
884
            fn retain_and_panic() {
885
                use std::panic::AssertUnwindSafe;
886
                let (mut m, k1, _k2) = construct_near_saturated_slotmap();
887

            
888
                let _ = std::panic::catch_unwind(AssertUnwindSafe(|| {
889
                    m.retain(|k,_| if k == k1 { false } else { panic!() })
890
                })).unwrap_err();
891
                m.assert_rep_ok();
892
            }
893

            
894
            #[test]
895
            fn modify() {
896
                let (mut m, k1, k2) = construct_near_saturated_slotmap();
897

            
898
                *m.get_mut(k1).unwrap() = "HELLO".to_string();
899
                *m.get_mut(k2).unwrap() = "WORLD".to_string();
900

            
901
                let v: Vec<_> = m.values().collect();
902
                assert_eq!(v, vec![&"HELLO".to_string(), &"WORLD".to_string()]);
903
            }
904

            
905
            #[test]
906
            fn iterators() {
907
                let (mut m, k1, k2) = construct_near_saturated_slotmap();
908

            
909
                m.remove(k1);
910
                assert_eq!(m.n_unusable, 1);
911

            
912
                for v in m.values_mut() {
913
                    *v = "WORLD".to_string();
914
                }
915

            
916
                let v: Vec<_> = m.values().collect();
917
                assert_eq!(v, vec![&"WORLD".to_string()]);
918

            
919
                let v: Vec<_> = m.iter().collect();
920
                assert_eq!(v, vec![(k2, &"WORLD".to_string())]);
921

            
922
                for (k, v) in m.iter_mut() {
923
                    assert_eq!(k, k2);
924
                    *v = "World".to_string();
925
                }
926

            
927
                let v: Vec<_> = m.iter().collect();
928
                assert_eq!(v, vec![(k2, &"World".to_string())]);
929

            
930
                let v: Vec<_> = m.keys().collect();
931
                assert_eq!(v, vec![k2]);
932

            
933
                m.assert_rep_ok();
934
            }
935

            
936
            #[test]
937
            fn get_mut_multiple() {
938
                let (mut m, k1, k2) = construct_near_saturated_slotmap();
939

            
940
                assert!(m.get_disjoint_mut([k1,k1]).is_none());
941

            
942
                if let Some([v1, v2]) = m.get_disjoint_mut([k1, k2]) {
943
                    assert_eq!(v1, "hello");
944
                    assert_eq!(v2, "world");
945
                    *v1 = "HELLO".into();
946
                    *v2 = "WORLD".into();
947
                } else {
948
                    panic!("get_disjoint_mut failed.");
949
                };
950

            
951
                m.remove(k1);
952
                assert_eq!(m.contains_key(k1), false);
953
                assert_eq!(m.base.contains_key(k1), true);
954
                m.assert_rep_ok();
955

            
956
                if let Some([_v1, _v2]) = m.get_disjoint_mut([k1, k2]) {
957
                    panic!("get_disjoint_mut succeeded unexpectedly.")
958
                }
959
            }
960

            
961
            #[test]
962
            fn get_capacity() {
963
                let (mut m, k1, _) = construct_near_saturated_slotmap();
964

            
965
                let cap_orig = dbg!(m.capacity());
966
                m.remove(k1);
967
                m.assert_rep_ok();
968

            
969
                assert_eq!(m.n_unusable, 1);
970
                assert_eq!(m.capacity(), cap_orig - 1); // capacity decreased, since there is an unusable slot.
971

            
972
                m.reserve(5);
973
                assert!(m.capacity() >= 5);
974
            }
975

            
976
            #[test]
977
            fn index() {
978
                let (mut m, k1, k2) = construct_near_saturated_slotmap();
979

            
980
                assert_eq!(m[k1], "hello");
981
                assert_eq!(*(&mut m[k2]), "world");
982
            }
983
        } // end module.
984
        }}} // End macro rules
985

            
986
    tests_for! {SlotMap}
987
    tests_for! {DenseSlotMap}
988
    tests_for! {HopSlotMap}
989
}