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