1//! This module contains property-based tests against the public API:
2//! * API never panics.
3//! * Active entries cannot be overridden until removed.
4//! * The slab doesn't produce overlapping keys.
5//! * The slab doesn't leave "lost" keys.
6//! * `get()`, `get_owned`, and `contains()` are consistent.
7//! * `RESERVED_BITS` are actually not used.
8//!
9//! The test is supposed to be deterministic, so it doesn't spawn real threads
10//! and uses `tid::with()` to override the TID for the current thread.
11
12use std::{ops::Range, sync::Arc};
13
14use indexmap::IndexMap;
15use proptest::prelude::*;
16
17use crate::{tid, Config, DefaultConfig, Slab};
18
19const THREADS: Range<usize> = 1..4;
20const ACTIONS: Range<usize> = 1..1000;
21
22#[derive(Debug, Clone)]
23struct Action {
24 tid: usize,
25 kind: ActionKind,
26}
27
28#[derive(Debug, Clone)]
29enum ActionKind {
30 Insert,
31 VacantEntry,
32 RemoveRandom(usize), // key
33 RemoveExistent(usize), // seed
34 TakeRandom(usize), // key
35 TakeExistent(usize), // seed
36 GetRandom(usize), // key
37 GetExistent(usize), // seed
38}
39
40prop_compose! {
41 fn action_strategy()(tid in THREADS, kind in action_kind_strategy()) -> Action {
42 Action { tid, kind }
43 }
44}
45
46fn action_kind_strategy() -> impl Strategy<Value = ActionKind> {
47 prop_oneof![
48 1 => Just(ActionKind::Insert),
49 1 => Just(ActionKind::VacantEntry),
50 1 => prop::num::usize::ANY.prop_map(ActionKind::RemoveRandom),
51 1 => prop::num::usize::ANY.prop_map(ActionKind::RemoveExistent),
52 1 => prop::num::usize::ANY.prop_map(ActionKind::TakeRandom),
53 1 => prop::num::usize::ANY.prop_map(ActionKind::TakeExistent),
54 // Produce `GetRandom` and `GetExistent` more often.
55 5 => prop::num::usize::ANY.prop_map(ActionKind::GetRandom),
56 5 => prop::num::usize::ANY.prop_map(ActionKind::GetExistent),
57 ]
58}
59
60/// Stores active entries (added and not yet removed).
61#[derive(Default)]
62struct Active {
63 // Use `IndexMap` to preserve determinism.
64 map: IndexMap<usize, u32>,
65 prev_value: u32,
66}
67
68impl Active {
69 fn next_value(&mut self) -> u32 {
70 self.prev_value += 1;
71 self.prev_value
72 }
73
74 fn get(&self, key: usize) -> Option<u32> {
75 self.map.get(&key).copied()
76 }
77
78 fn get_any(&self, seed: usize) -> Option<(usize, u32)> {
79 if self.map.is_empty() {
80 return None;
81 }
82
83 let index = seed % self.map.len();
84 self.map.get_index(index).map(|(k, v)| (*k, *v))
85 }
86
87 fn insert(&mut self, key: usize, value: u32) {
88 assert_eq!(
89 self.map.insert(key, value),
90 None,
91 "keys of active entries must be unique"
92 );
93 }
94
95 fn remove(&mut self, key: usize) -> Option<u32> {
96 self.map.swap_remove(&key)
97 }
98
99 fn remove_any(&mut self, seed: usize) -> Option<(usize, u32)> {
100 if self.map.is_empty() {
101 return None;
102 }
103
104 let index = seed % self.map.len();
105 self.map.swap_remove_index(index)
106 }
107
108 fn drain(&mut self) -> impl Iterator<Item = (usize, u32)> + '_ {
109 self.map.drain(..)
110 }
111}
112
113fn used_bits<C: Config>(key: usize) -> usize {
114 assert_eq!(
115 C::RESERVED_BITS + Slab::<u32, C>::USED_BITS,
116 std::mem::size_of::<usize>() * 8
117 );
118 key & ((!0) >> C::RESERVED_BITS)
119}
120
121fn apply_action<C: Config>(
122 slab: &Arc<Slab<u32, C>>,
123 active: &mut Active,
124 action: ActionKind,
125) -> Result<(), TestCaseError> {
126 match action {
127 ActionKind::Insert => {
128 let value = active.next_value();
129 let key = slab.insert(value).expect("unexpectedly exhausted slab");
130 prop_assert_eq!(used_bits::<C>(key), key);
131 active.insert(key, value);
132 }
133 ActionKind::VacantEntry => {
134 let value = active.next_value();
135 let entry = slab.vacant_entry().expect("unexpectedly exhausted slab");
136 let key = entry.key();
137 prop_assert_eq!(used_bits::<C>(key), key);
138 entry.insert(value);
139 active.insert(key, value);
140 }
141 ActionKind::RemoveRandom(key) => {
142 let used_key = used_bits::<C>(key);
143 prop_assert_eq!(slab.get(key).map(|e| *e), slab.get(used_key).map(|e| *e));
144 prop_assert_eq!(slab.remove(key), active.remove(used_key).is_some());
145 }
146 ActionKind::RemoveExistent(seed) => {
147 if let Some((key, _value)) = active.remove_any(seed) {
148 prop_assert!(slab.contains(key));
149 prop_assert!(slab.remove(key));
150 }
151 }
152 ActionKind::TakeRandom(key) => {
153 let used_key = used_bits::<C>(key);
154 prop_assert_eq!(slab.get(key).map(|e| *e), slab.get(used_key).map(|e| *e));
155 prop_assert_eq!(slab.take(key), active.remove(used_key));
156 }
157 ActionKind::TakeExistent(seed) => {
158 if let Some((key, value)) = active.remove_any(seed) {
159 prop_assert!(slab.contains(key));
160 prop_assert_eq!(slab.take(key), Some(value));
161 }
162 }
163 ActionKind::GetRandom(key) => {
164 let used_key = used_bits::<C>(key);
165 prop_assert_eq!(slab.get(key).map(|e| *e), slab.get(used_key).map(|e| *e));
166 prop_assert_eq!(slab.get(key).map(|e| *e), active.get(used_key));
167 prop_assert_eq!(
168 slab.clone().get_owned(key).map(|e| *e),
169 active.get(used_key)
170 );
171 }
172 ActionKind::GetExistent(seed) => {
173 if let Some((key, value)) = active.get_any(seed) {
174 prop_assert!(slab.contains(key));
175 prop_assert_eq!(slab.get(key).map(|e| *e), Some(value));
176 prop_assert_eq!(slab.clone().get_owned(key).map(|e| *e), Some(value));
177 }
178 }
179 }
180
181 Ok(())
182}
183
184fn run<C: Config>(actions: Vec<Action>) -> Result<(), TestCaseError> {
185 let mut slab = Arc::new(Slab::new_with_config::<C>());
186 let mut active = Active::default();
187
188 // Apply all actions.
189 for action in actions {
190 // Override the TID for the current thread instead of using multiple real threads
191 // to preserve determinism. We're not checking concurrency issues here, they should be
192 // covered by loom tests anyway. Thus, it's fine to run all actions consequently.
193 tid::with(action.tid, || {
194 apply_action::<C>(&slab, &mut active, action.kind)
195 })?;
196 }
197
198 // Ensure the slab contains all remaining entries.
199 let mut expected_values = Vec::new();
200 for (key, value) in active.drain() {
201 prop_assert!(slab.contains(key));
202 prop_assert_eq!(slab.get(key).map(|e| *e), Some(value));
203 prop_assert_eq!(slab.clone().get_owned(key).map(|e| *e), Some(value));
204 expected_values.push(value);
205 }
206 expected_values.sort();
207
208 // Ensure `unique_iter()` returns all remaining entries.
209 let slab = Arc::get_mut(&mut slab).unwrap();
210 let mut actual_values = slab.unique_iter().copied().collect::<Vec<_>>();
211 actual_values.sort();
212 prop_assert_eq!(actual_values, expected_values);
213
214 Ok(())
215}
216
217proptest! {
218 #[test]
219 fn default_config(actions in prop::collection::vec(action_strategy(), ACTIONS)) {
220 run::<DefaultConfig>(actions)?;
221 }
222
223 #[test]
224 fn custom_config(actions in prop::collection::vec(action_strategy(), ACTIONS)) {
225 run::<CustomConfig>(actions)?;
226 }
227}
228
229struct CustomConfig;
230
231#[cfg(target_pointer_width = "64")]
232impl Config for CustomConfig {
233 const INITIAL_PAGE_SIZE: usize = 32;
234 const MAX_PAGES: usize = 15;
235 const MAX_THREADS: usize = 256;
236 const RESERVED_BITS: usize = 24;
237}
238#[cfg(target_pointer_width = "32")]
239impl Config for CustomConfig {
240 const INITIAL_PAGE_SIZE: usize = 16;
241 const MAX_PAGES: usize = 6;
242 const MAX_THREADS: usize = 128;
243 const RESERVED_BITS: usize = 12;
244}
245