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 | |
12 | use std::{ops::Range, sync::Arc}; |
13 | |
14 | use indexmap::IndexMap; |
15 | use proptest::prelude::*; |
16 | |
17 | use crate::{tid, Config, DefaultConfig, Slab}; |
18 | |
19 | const THREADS: Range<usize> = 1..4; |
20 | const ACTIONS: Range<usize> = 1..1000; |
21 | |
22 | #[derive(Debug, Clone)] |
23 | struct Action { |
24 | tid: usize, |
25 | kind: ActionKind, |
26 | } |
27 | |
28 | #[derive(Debug, Clone)] |
29 | enum 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 | |
40 | prop_compose! { |
41 | fn action_strategy()(tid in THREADS, kind in action_kind_strategy()) -> Action { |
42 | Action { tid, kind } |
43 | } |
44 | } |
45 | |
46 | fn 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)] |
62 | struct Active { |
63 | // Use `IndexMap` to preserve determinism. |
64 | map: IndexMap<usize, u32>, |
65 | prev_value: u32, |
66 | } |
67 | |
68 | impl 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 | |
113 | fn 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 | |
121 | fn 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 | |
184 | fn 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 | |
217 | proptest! { |
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 | |
229 | struct CustomConfig; |
230 | |
231 | #[cfg (target_pointer_width = "64" )] |
232 | impl 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" )] |
239 | impl 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 | |