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}