vendor/indexmap/tests/quick.rs

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