1 use indexmap::{IndexMap, IndexSet};
2 use itertools::Itertools;
3
4 use quickcheck::quickcheck;
5 use quickcheck::Arbitrary;
6 use quickcheck::Gen;
7 use quickcheck::TestResult;
8
9 use rand::Rng;
10
11 use fnv::FnvHasher;
12 use std::hash::{BuildHasher, BuildHasherDefault};
13 type FnvBuilder = BuildHasherDefault<FnvHasher>;
14 type IndexMapFnv<K, V> = IndexMap<K, V, FnvBuilder>;
15
16 use std::cmp::min;
17 use std::collections::HashMap;
18 use std::collections::HashSet;
19 use std::fmt::Debug;
20 use std::hash::Hash;
21 use std::iter::FromIterator;
22 use std::ops::Bound;
23 use std::ops::Deref;
24
25 use indexmap::map::Entry as OEntry;
26 use std::collections::hash_map::Entry as HEntry;
27
set<'a, T: 'a, I>(iter: I) -> HashSet<T> where I: IntoIterator<Item = &'a T>, T: Copy + Hash + Eq,28 fn set<'a, T: 'a, I>(iter: I) -> HashSet<T>
29 where
30 I: IntoIterator<Item = &'a T>,
31 T: Copy + Hash + Eq,
32 {
33 iter.into_iter().cloned().collect()
34 }
35
indexmap<'a, T: 'a, I>(iter: I) -> IndexMap<T, ()> where I: IntoIterator<Item = &'a T>, T: Copy + Hash + Eq,36 fn indexmap<'a, T: 'a, I>(iter: I) -> IndexMap<T, ()>
37 where
38 I: IntoIterator<Item = &'a T>,
39 T: Copy + Hash + Eq,
40 {
41 IndexMap::from_iter(iter.into_iter().cloned().map(|k| (k, ())))
42 }
43
44 quickcheck! {
45 fn contains(insert: Vec<u32>) -> bool {
46 let mut map = IndexMap::new();
47 for &key in &insert {
48 map.insert(key, ());
49 }
50 insert.iter().all(|&key| map.get(&key).is_some())
51 }
52
53 fn contains_not(insert: Vec<u8>, not: Vec<u8>) -> bool {
54 let mut map = IndexMap::new();
55 for &key in &insert {
56 map.insert(key, ());
57 }
58 let nots = &set(¬) - &set(&insert);
59 nots.iter().all(|&key| map.get(&key).is_none())
60 }
61
62 fn insert_remove(insert: Vec<u8>, remove: Vec<u8>) -> bool {
63 let mut map = IndexMap::new();
64 for &key in &insert {
65 map.insert(key, ());
66 }
67 for &key in &remove {
68 map.swap_remove(&key);
69 }
70 let elements = &set(&insert) - &set(&remove);
71 map.len() == elements.len() && map.iter().count() == elements.len() &&
72 elements.iter().all(|k| map.get(k).is_some())
73 }
74
75 fn insertion_order(insert: Vec<u32>) -> bool {
76 let mut map = IndexMap::new();
77 for &key in &insert {
78 map.insert(key, ());
79 }
80 itertools::assert_equal(insert.iter().unique(), map.keys());
81 true
82 }
83
84 fn pop(insert: Vec<u8>) -> bool {
85 let mut map = IndexMap::new();
86 for &key in &insert {
87 map.insert(key, ());
88 }
89 let mut pops = Vec::new();
90 while let Some((key, _v)) = map.pop() {
91 pops.push(key);
92 }
93 pops.reverse();
94
95 itertools::assert_equal(insert.iter().unique(), &pops);
96 true
97 }
98
99 fn with_cap(cap: usize) -> bool {
100 let map: IndexMap<u8, u8> = IndexMap::with_capacity(cap);
101 println!("wish: {}, got: {} (diff: {})", cap, map.capacity(), map.capacity() as isize - cap as isize);
102 map.capacity() >= cap
103 }
104
105 fn drain_full(insert: Vec<u8>) -> bool {
106 let mut map = IndexMap::new();
107 for &key in &insert {
108 map.insert(key, ());
109 }
110 let mut clone = map.clone();
111 let drained = clone.drain(..);
112 for (key, _) in drained {
113 map.swap_remove(&key);
114 }
115 map.is_empty()
116 }
117
118 fn drain_bounds(insert: Vec<u8>, range: (Bound<usize>, Bound<usize>)) -> TestResult {
119 let mut map = IndexMap::new();
120 for &key in &insert {
121 map.insert(key, ());
122 }
123
124 // First see if `Vec::drain` is happy with this range.
125 let result = std::panic::catch_unwind(|| {
126 let mut keys: Vec<u8> = map.keys().cloned().collect();
127 keys.drain(range);
128 keys
129 });
130
131 if let Ok(keys) = result {
132 map.drain(range);
133 // Check that our `drain` matches the same key order.
134 assert!(map.keys().eq(&keys));
135 // Check that hash lookups all work too.
136 assert!(keys.iter().all(|key| map.contains_key(key)));
137 TestResult::passed()
138 } else {
139 // If `Vec::drain` panicked, so should we.
140 TestResult::must_fail(move || { map.drain(range); })
141 }
142 }
143
144 fn shift_remove(insert: Vec<u8>, remove: Vec<u8>) -> bool {
145 let mut map = IndexMap::new();
146 for &key in &insert {
147 map.insert(key, ());
148 }
149 for &key in &remove {
150 map.shift_remove(&key);
151 }
152 let elements = &set(&insert) - &set(&remove);
153
154 // Check that order is preserved after removals
155 let mut iter = map.keys();
156 for &key in insert.iter().unique() {
157 if elements.contains(&key) {
158 assert_eq!(Some(key), iter.next().cloned());
159 }
160 }
161
162 map.len() == elements.len() && map.iter().count() == elements.len() &&
163 elements.iter().all(|k| map.get(k).is_some())
164 }
165
166 fn indexing(insert: Vec<u8>) -> bool {
167 let mut map: IndexMap<_, _> = insert.into_iter().map(|x| (x, x)).collect();
168 let set: IndexSet<_> = map.keys().cloned().collect();
169 assert_eq!(map.len(), set.len());
170
171 for (i, &key) in set.iter().enumerate() {
172 assert_eq!(map.get_index(i), Some((&key, &key)));
173 assert_eq!(set.get_index(i), Some(&key));
174 assert_eq!(map[i], key);
175 assert_eq!(set[i], key);
176
177 *map.get_index_mut(i).unwrap().1 >>= 1;
178 map[i] <<= 1;
179 }
180
181 set.iter().enumerate().all(|(i, &key)| {
182 let value = key & !1;
183 map[&key] == value && map[i] == value
184 })
185 }
186 }
187
188 use crate::Op::*;
189 #[derive(Copy, Clone, Debug)]
190 enum Op<K, V> {
191 Add(K, V),
192 Remove(K),
193 AddEntry(K, V),
194 RemoveEntry(K),
195 }
196
197 impl<K, V> Arbitrary for Op<K, V>
198 where
199 K: Arbitrary,
200 V: Arbitrary,
201 {
arbitrary<G: Gen>(g: &mut G) -> Self202 fn arbitrary<G: Gen>(g: &mut G) -> Self {
203 match g.gen::<u32>() % 4 {
204 0 => Add(K::arbitrary(g), V::arbitrary(g)),
205 1 => AddEntry(K::arbitrary(g), V::arbitrary(g)),
206 2 => Remove(K::arbitrary(g)),
207 _ => RemoveEntry(K::arbitrary(g)),
208 }
209 }
210 }
211
do_ops<K, V, S>(ops: &[Op<K, V>], a: &mut IndexMap<K, V, S>, b: &mut HashMap<K, V>) where K: Hash + Eq + Clone, V: Clone, S: BuildHasher,212 fn do_ops<K, V, S>(ops: &[Op<K, V>], a: &mut IndexMap<K, V, S>, b: &mut HashMap<K, V>)
213 where
214 K: Hash + Eq + Clone,
215 V: Clone,
216 S: BuildHasher,
217 {
218 for op in ops {
219 match *op {
220 Add(ref k, ref v) => {
221 a.insert(k.clone(), v.clone());
222 b.insert(k.clone(), v.clone());
223 }
224 AddEntry(ref k, ref v) => {
225 a.entry(k.clone()).or_insert_with(|| v.clone());
226 b.entry(k.clone()).or_insert_with(|| v.clone());
227 }
228 Remove(ref k) => {
229 a.swap_remove(k);
230 b.remove(k);
231 }
232 RemoveEntry(ref k) => {
233 if let OEntry::Occupied(ent) = a.entry(k.clone()) {
234 ent.swap_remove_entry();
235 }
236 if let HEntry::Occupied(ent) = b.entry(k.clone()) {
237 ent.remove_entry();
238 }
239 }
240 }
241 //println!("{:?}", a);
242 }
243 }
244
assert_maps_equivalent<K, V>(a: &IndexMap<K, V>, b: &HashMap<K, V>) -> bool where K: Hash + Eq + Debug, V: Eq + Debug,245 fn assert_maps_equivalent<K, V>(a: &IndexMap<K, V>, b: &HashMap<K, V>) -> bool
246 where
247 K: Hash + Eq + Debug,
248 V: Eq + Debug,
249 {
250 assert_eq!(a.len(), b.len());
251 assert_eq!(a.iter().next().is_some(), b.iter().next().is_some());
252 for key in a.keys() {
253 assert!(b.contains_key(key), "b does not contain {:?}", key);
254 }
255 for key in b.keys() {
256 assert!(a.get(key).is_some(), "a does not contain {:?}", key);
257 }
258 for key in a.keys() {
259 assert_eq!(a[key], b[key]);
260 }
261 true
262 }
263
264 quickcheck! {
265 fn operations_i8(ops: Large<Vec<Op<i8, i8>>>) -> bool {
266 let mut map = IndexMap::new();
267 let mut reference = HashMap::new();
268 do_ops(&ops, &mut map, &mut reference);
269 assert_maps_equivalent(&map, &reference)
270 }
271
272 fn operations_string(ops: Vec<Op<Alpha, i8>>) -> bool {
273 let mut map = IndexMap::new();
274 let mut reference = HashMap::new();
275 do_ops(&ops, &mut map, &mut reference);
276 assert_maps_equivalent(&map, &reference)
277 }
278
279 fn keys_values(ops: Large<Vec<Op<i8, i8>>>) -> bool {
280 let mut map = IndexMap::new();
281 let mut reference = HashMap::new();
282 do_ops(&ops, &mut map, &mut reference);
283 let mut visit = IndexMap::new();
284 for (k, v) in map.keys().zip(map.values()) {
285 assert_eq!(&map[k], v);
286 assert!(!visit.contains_key(k));
287 visit.insert(*k, *v);
288 }
289 assert_eq!(visit.len(), reference.len());
290 true
291 }
292
293 fn keys_values_mut(ops: Large<Vec<Op<i8, i8>>>) -> bool {
294 let mut map = IndexMap::new();
295 let mut reference = HashMap::new();
296 do_ops(&ops, &mut map, &mut reference);
297 let mut visit = IndexMap::new();
298 let keys = Vec::from_iter(map.keys().cloned());
299 for (k, v) in keys.iter().zip(map.values_mut()) {
300 assert_eq!(&reference[k], v);
301 assert!(!visit.contains_key(k));
302 visit.insert(*k, *v);
303 }
304 assert_eq!(visit.len(), reference.len());
305 true
306 }
307
308 fn equality(ops1: Vec<Op<i8, i8>>, removes: Vec<usize>) -> bool {
309 let mut map = IndexMap::new();
310 let mut reference = HashMap::new();
311 do_ops(&ops1, &mut map, &mut reference);
312 let mut ops2 = ops1.clone();
313 for &r in &removes {
314 if !ops2.is_empty() {
315 let i = r % ops2.len();
316 ops2.remove(i);
317 }
318 }
319 let mut map2 = IndexMapFnv::default();
320 let mut reference2 = HashMap::new();
321 do_ops(&ops2, &mut map2, &mut reference2);
322 assert_eq!(map == map2, reference == reference2);
323 true
324 }
325
326 fn retain_ordered(keys: Large<Vec<i8>>, remove: Large<Vec<i8>>) -> () {
327 let mut map = indexmap(keys.iter());
328 let initial_map = map.clone(); // deduplicated in-order input
329 let remove_map = indexmap(remove.iter());
330 let keys_s = set(keys.iter());
331 let remove_s = set(remove.iter());
332 let answer = &keys_s - &remove_s;
333 map.retain(|k, _| !remove_map.contains_key(k));
334
335 // check the values
336 assert_eq!(map.len(), answer.len());
337 for key in &answer {
338 assert!(map.contains_key(key));
339 }
340 // check the order
341 itertools::assert_equal(map.keys(), initial_map.keys().filter(|&k| !remove_map.contains_key(k)));
342 }
343
344 fn sort_1(keyvals: Large<Vec<(i8, i8)>>) -> () {
345 let mut map: IndexMap<_, _> = IndexMap::from_iter(keyvals.to_vec());
346 let mut answer = keyvals.0;
347 answer.sort_by_key(|t| t.0);
348
349 // reverse dedup: Because IndexMap::from_iter keeps the last value for
350 // identical keys
351 answer.reverse();
352 answer.dedup_by_key(|t| t.0);
353 answer.reverse();
354
355 map.sort_by(|k1, _, k2, _| Ord::cmp(k1, k2));
356
357 // check it contains all the values it should
358 for &(key, val) in &answer {
359 assert_eq!(map[&key], val);
360 }
361
362 // check the order
363
364 let mapv = Vec::from_iter(map);
365 assert_eq!(answer, mapv);
366
367 }
368
369 fn sort_2(keyvals: Large<Vec<(i8, i8)>>) -> () {
370 let mut map: IndexMap<_, _> = IndexMap::from_iter(keyvals.to_vec());
371 map.sort_by(|_, v1, _, v2| Ord::cmp(v1, v2));
372 assert_sorted_by_key(map, |t| t.1);
373 }
374
375 fn reverse(keyvals: Large<Vec<(i8, i8)>>) -> () {
376 let mut map: IndexMap<_, _> = IndexMap::from_iter(keyvals.to_vec());
377
378 fn generate_answer(input: &Vec<(i8, i8)>) -> Vec<(i8, i8)> {
379 // to mimic what `IndexMap::from_iter` does:
380 // need to get (A) the unique keys in forward order, and (B) the
381 // last value of each of those keys.
382
383 // create (A): an iterable that yields the unique keys in ltr order
384 let mut seen_keys = HashSet::new();
385 let unique_keys_forward = input.iter().filter_map(move |(k, _)| {
386 if seen_keys.contains(k) { None }
387 else { seen_keys.insert(*k); Some(*k) }
388 });
389
390 // create (B): a mapping of keys to the last value seen for that key
391 // this is the same as reversing the input and taking the first
392 // value seen for that key!
393 let mut last_val_per_key = HashMap::new();
394 for &(k, v) in input.iter().rev() {
395 if !last_val_per_key.contains_key(&k) {
396 last_val_per_key.insert(k, v);
397 }
398 }
399
400 // iterate over the keys in (A) in order, and match each one with
401 // the corresponding last value from (B)
402 let mut ans: Vec<_> = unique_keys_forward
403 .map(|k| (k, *last_val_per_key.get(&k).unwrap()))
404 .collect();
405
406 // finally, since this test is testing `.reverse()`, reverse the
407 // answer in-place
408 ans.reverse();
409
410 ans
411 }
412
413 let answer = generate_answer(&keyvals.0);
414
415 // perform the work
416 map.reverse();
417
418 // check it contains all the values it should
419 for &(key, val) in &answer {
420 assert_eq!(map[&key], val);
421 }
422
423 // check the order
424 let mapv = Vec::from_iter(map);
425 assert_eq!(answer, mapv);
426 }
427 }
428
assert_sorted_by_key<I, Key, X>(iterable: I, key: Key) where I: IntoIterator, I::Item: Ord + Clone + Debug, Key: Fn(&I::Item) -> X, X: Ord,429 fn assert_sorted_by_key<I, Key, X>(iterable: I, key: Key)
430 where
431 I: IntoIterator,
432 I::Item: Ord + Clone + Debug,
433 Key: Fn(&I::Item) -> X,
434 X: Ord,
435 {
436 let input = Vec::from_iter(iterable);
437 let mut sorted = input.clone();
438 sorted.sort_by_key(key);
439 assert_eq!(input, sorted);
440 }
441
442 #[derive(Clone, Debug, Hash, PartialEq, Eq)]
443 struct Alpha(String);
444
445 impl Deref for Alpha {
446 type Target = String;
deref(&self) -> &String447 fn deref(&self) -> &String {
448 &self.0
449 }
450 }
451
452 const ALPHABET: &[u8] = b"abcdefghijklmnopqrstuvwxyz";
453
454 impl Arbitrary for Alpha {
arbitrary<G: Gen>(g: &mut G) -> Self455 fn arbitrary<G: Gen>(g: &mut G) -> Self {
456 let len = g.next_u32() % g.size() as u32;
457 let len = min(len, 16);
458 Alpha(
459 (0..len)
460 .map(|_| ALPHABET[g.next_u32() as usize % ALPHABET.len()] as char)
461 .collect(),
462 )
463 }
464
shrink(&self) -> Box<dyn Iterator<Item = Self>>465 fn shrink(&self) -> Box<dyn Iterator<Item = Self>> {
466 Box::new((**self).shrink().map(Alpha))
467 }
468 }
469
470 /// quickcheck Arbitrary adaptor -- make a larger vec
471 #[derive(Clone, Debug)]
472 struct Large<T>(T);
473
474 impl<T> Deref for Large<T> {
475 type Target = T;
deref(&self) -> &T476 fn deref(&self) -> &T {
477 &self.0
478 }
479 }
480
481 impl<T> Arbitrary for Large<Vec<T>>
482 where
483 T: Arbitrary,
484 {
arbitrary<G: Gen>(g: &mut G) -> Self485 fn arbitrary<G: Gen>(g: &mut G) -> Self {
486 let len = g.next_u32() % (g.size() * 10) as u32;
487 Large((0..len).map(|_| T::arbitrary(g)).collect())
488 }
489
shrink(&self) -> Box<dyn Iterator<Item = Self>>490 fn shrink(&self) -> Box<dyn Iterator<Item = Self>> {
491 Box::new((**self).shrink().map(Large))
492 }
493 }
494