From 26a029d407be480d791972afb5975cf62c9360a6 Mon Sep 17 00:00:00 2001 From: Daniel Baumann Date: Fri, 19 Apr 2024 02:47:55 +0200 Subject: Adding upstream version 124.0.1. Signed-off-by: Daniel Baumann --- .../rust/indexmap/tests/equivalent_trait.rs | 53 ++ .../rust/indexmap/tests/macros_full_path.rs | 19 + third_party/rust/indexmap/tests/quick.rs | 573 +++++++++++++++++++++ third_party/rust/indexmap/tests/tests.rs | 28 + 4 files changed, 673 insertions(+) create mode 100644 third_party/rust/indexmap/tests/equivalent_trait.rs create mode 100644 third_party/rust/indexmap/tests/macros_full_path.rs create mode 100644 third_party/rust/indexmap/tests/quick.rs create mode 100644 third_party/rust/indexmap/tests/tests.rs (limited to 'third_party/rust/indexmap/tests') diff --git a/third_party/rust/indexmap/tests/equivalent_trait.rs b/third_party/rust/indexmap/tests/equivalent_trait.rs new file mode 100644 index 0000000000..ff5943a3ed --- /dev/null +++ b/third_party/rust/indexmap/tests/equivalent_trait.rs @@ -0,0 +1,53 @@ +use indexmap::indexmap; +use indexmap::Equivalent; + +use std::hash::Hash; + +#[derive(Debug, Hash)] +pub struct Pair(pub A, pub B); + +impl PartialEq<(A, B)> for Pair +where + C: PartialEq, + D: PartialEq, +{ + fn eq(&self, rhs: &(A, B)) -> bool { + self.0 == rhs.0 && self.1 == rhs.1 + } +} + +impl Equivalent for Pair +where + Pair: PartialEq, + A: Hash + Eq, + B: Hash + Eq, +{ + fn equivalent(&self, other: &X) -> bool { + *self == *other + } +} + +#[test] +fn test_lookup() { + let s = String::from; + let map = indexmap! { + (s("a"), s("b")) => 1, + (s("a"), s("x")) => 2, + }; + + assert!(map.contains_key(&Pair("a", "b"))); + assert!(!map.contains_key(&Pair("b", "a"))); +} + +#[test] +fn test_string_str() { + let s = String::from; + let mut map = indexmap! { + s("a") => 1, s("b") => 2, + s("x") => 3, s("y") => 4, + }; + + assert!(map.contains_key("a")); + assert!(!map.contains_key("z")); + assert_eq!(map.swap_remove("b"), Some(2)); +} diff --git a/third_party/rust/indexmap/tests/macros_full_path.rs b/third_party/rust/indexmap/tests/macros_full_path.rs new file mode 100644 index 0000000000..2467d9b4f5 --- /dev/null +++ b/third_party/rust/indexmap/tests/macros_full_path.rs @@ -0,0 +1,19 @@ +#[test] +fn test_create_map() { + let _m = indexmap::indexmap! { + 1 => 2, + 7 => 1, + 2 => 2, + 3 => 3, + }; +} + +#[test] +fn test_create_set() { + let _s = indexmap::indexset! { + 1, + 7, + 2, + 3, + }; +} diff --git a/third_party/rust/indexmap/tests/quick.rs b/third_party/rust/indexmap/tests/quick.rs new file mode 100644 index 0000000000..e9d96acccb --- /dev/null +++ b/third_party/rust/indexmap/tests/quick.rs @@ -0,0 +1,573 @@ +use indexmap::{IndexMap, IndexSet}; +use itertools::Itertools; + +use quickcheck::Arbitrary; +use quickcheck::Gen; +use quickcheck::QuickCheck; +use quickcheck::TestResult; + +use fnv::FnvHasher; +use std::hash::{BuildHasher, BuildHasherDefault}; +type FnvBuilder = BuildHasherDefault; +type IndexMapFnv = IndexMap; + +use std::cmp::min; +use std::collections::HashMap; +use std::collections::HashSet; +use std::fmt::Debug; +use std::hash::Hash; +use std::ops::Bound; +use std::ops::Deref; + +use indexmap::map::Entry as OEntry; +use std::collections::hash_map::Entry as HEntry; + +fn set<'a, T: 'a, I>(iter: I) -> HashSet +where + I: IntoIterator, + T: Copy + Hash + Eq, +{ + iter.into_iter().copied().collect() +} + +fn indexmap<'a, T: 'a, I>(iter: I) -> IndexMap +where + I: IntoIterator, + T: Copy + Hash + Eq, +{ + IndexMap::from_iter(iter.into_iter().copied().map(|k| (k, ()))) +} + +// Helper macro to allow us to use smaller quickcheck limits under miri. +macro_rules! quickcheck_limit { + (@as_items $($i:item)*) => ($($i)*); + { + $( + $(#[$m:meta])* + fn $fn_name:ident($($arg_name:ident : $arg_ty:ty),*) -> $ret:ty { + $($code:tt)* + } + )* + } => ( + quickcheck::quickcheck! { + @as_items + $( + #[test] + $(#[$m])* + fn $fn_name() { + fn prop($($arg_name: $arg_ty),*) -> $ret { + $($code)* + } + let mut quickcheck = QuickCheck::new(); + if cfg!(miri) { + quickcheck = quickcheck + .gen(Gen::new(10)) + .tests(10) + .max_tests(100); + } + + quickcheck.quickcheck(prop as fn($($arg_ty),*) -> $ret); + } + )* + } + ) +} + +quickcheck_limit! { + fn contains(insert: Vec) -> bool { + let mut map = IndexMap::new(); + for &key in &insert { + map.insert(key, ()); + } + insert.iter().all(|&key| map.get(&key).is_some()) + } + + fn contains_not(insert: Vec, not: Vec) -> bool { + let mut map = IndexMap::new(); + for &key in &insert { + map.insert(key, ()); + } + let nots = &set(¬) - &set(&insert); + nots.iter().all(|&key| map.get(&key).is_none()) + } + + fn insert_remove(insert: Vec, remove: Vec) -> bool { + let mut map = IndexMap::new(); + for &key in &insert { + map.insert(key, ()); + } + for &key in &remove { + map.swap_remove(&key); + } + let elements = &set(&insert) - &set(&remove); + map.len() == elements.len() && map.iter().count() == elements.len() && + elements.iter().all(|k| map.get(k).is_some()) + } + + fn insertion_order(insert: Vec) -> bool { + let mut map = IndexMap::new(); + for &key in &insert { + map.insert(key, ()); + } + itertools::assert_equal(insert.iter().unique(), map.keys()); + true + } + + fn pop(insert: Vec) -> bool { + let mut map = IndexMap::new(); + for &key in &insert { + map.insert(key, ()); + } + let mut pops = Vec::new(); + while let Some((key, _v)) = map.pop() { + pops.push(key); + } + pops.reverse(); + + itertools::assert_equal(insert.iter().unique(), &pops); + true + } + + fn with_cap(template: Vec<()>) -> bool { + let cap = template.len(); + let map: IndexMap = IndexMap::with_capacity(cap); + println!("wish: {}, got: {} (diff: {})", cap, map.capacity(), map.capacity() as isize - cap as isize); + map.capacity() >= cap + } + + fn drain_full(insert: Vec) -> bool { + let mut map = IndexMap::new(); + for &key in &insert { + map.insert(key, ()); + } + let mut clone = map.clone(); + let drained = clone.drain(..); + for (key, _) in drained { + map.swap_remove(&key); + } + map.is_empty() + } + + fn drain_bounds(insert: Vec, range: (Bound, Bound)) -> TestResult { + let mut map = IndexMap::new(); + for &key in &insert { + map.insert(key, ()); + } + + // First see if `Vec::drain` is happy with this range. + let result = std::panic::catch_unwind(|| { + let mut keys: Vec = map.keys().copied().collect(); + keys.drain(range); + keys + }); + + if let Ok(keys) = result { + map.drain(range); + // Check that our `drain` matches the same key order. + assert!(map.keys().eq(&keys)); + // Check that hash lookups all work too. + assert!(keys.iter().all(|key| map.contains_key(key))); + TestResult::passed() + } else { + // If `Vec::drain` panicked, so should we. + TestResult::must_fail(move || { map.drain(range); }) + } + } + + fn shift_remove(insert: Vec, remove: Vec) -> bool { + let mut map = IndexMap::new(); + for &key in &insert { + map.insert(key, ()); + } + for &key in &remove { + map.shift_remove(&key); + } + let elements = &set(&insert) - &set(&remove); + + // Check that order is preserved after removals + let mut iter = map.keys(); + for &key in insert.iter().unique() { + if elements.contains(&key) { + assert_eq!(Some(&key), iter.next()); + } + } + + map.len() == elements.len() && map.iter().count() == elements.len() && + elements.iter().all(|k| map.get(k).is_some()) + } + + fn indexing(insert: Vec) -> bool { + let mut map: IndexMap<_, _> = insert.into_iter().map(|x| (x, x)).collect(); + let set: IndexSet<_> = map.keys().copied().collect(); + assert_eq!(map.len(), set.len()); + + for (i, &key) in set.iter().enumerate() { + assert_eq!(map.get_index(i), Some((&key, &key))); + assert_eq!(set.get_index(i), Some(&key)); + assert_eq!(map[i], key); + assert_eq!(set[i], key); + + *map.get_index_mut(i).unwrap().1 >>= 1; + map[i] <<= 1; + } + + set.iter().enumerate().all(|(i, &key)| { + let value = key & !1; + map[&key] == value && map[i] == value + }) + } + + // Use `u8` test indices so quickcheck is less likely to go out of bounds. + fn swap_indices(vec: Vec, a: u8, b: u8) -> TestResult { + let mut set = IndexSet::::from_iter(vec); + let a = usize::from(a); + let b = usize::from(b); + + if a >= set.len() || b >= set.len() { + return TestResult::discard(); + } + + let mut vec = Vec::from_iter(set.iter().cloned()); + vec.swap(a, b); + + set.swap_indices(a, b); + + // Check both iteration order and hash lookups + assert!(set.iter().eq(vec.iter())); + assert!(vec.iter().enumerate().all(|(i, x)| { + set.get_index_of(x) == Some(i) + })); + TestResult::passed() + } + + // Use `u8` test indices so quickcheck is less likely to go out of bounds. + fn move_index(vec: Vec, from: u8, to: u8) -> TestResult { + let mut set = IndexSet::::from_iter(vec); + let from = usize::from(from); + let to = usize::from(to); + + if from >= set.len() || to >= set.len() { + return TestResult::discard(); + } + + let mut vec = Vec::from_iter(set.iter().cloned()); + let x = vec.remove(from); + vec.insert(to, x); + + set.move_index(from, to); + + // Check both iteration order and hash lookups + assert!(set.iter().eq(vec.iter())); + assert!(vec.iter().enumerate().all(|(i, x)| { + set.get_index_of(x) == Some(i) + })); + TestResult::passed() + } +} + +use crate::Op::*; +#[derive(Copy, Clone, Debug)] +enum Op { + Add(K, V), + Remove(K), + AddEntry(K, V), + RemoveEntry(K), +} + +impl Arbitrary for Op +where + K: Arbitrary, + V: Arbitrary, +{ + fn arbitrary(g: &mut Gen) -> Self { + match u32::arbitrary(g) % 4 { + 0 => Add(K::arbitrary(g), V::arbitrary(g)), + 1 => AddEntry(K::arbitrary(g), V::arbitrary(g)), + 2 => Remove(K::arbitrary(g)), + _ => RemoveEntry(K::arbitrary(g)), + } + } +} + +fn do_ops(ops: &[Op], a: &mut IndexMap, b: &mut HashMap) +where + K: Hash + Eq + Clone, + V: Clone, + S: BuildHasher, +{ + for op in ops { + match *op { + Add(ref k, ref v) => { + a.insert(k.clone(), v.clone()); + b.insert(k.clone(), v.clone()); + } + AddEntry(ref k, ref v) => { + a.entry(k.clone()).or_insert_with(|| v.clone()); + b.entry(k.clone()).or_insert_with(|| v.clone()); + } + Remove(ref k) => { + a.swap_remove(k); + b.remove(k); + } + RemoveEntry(ref k) => { + if let OEntry::Occupied(ent) = a.entry(k.clone()) { + ent.swap_remove_entry(); + } + if let HEntry::Occupied(ent) = b.entry(k.clone()) { + ent.remove_entry(); + } + } + } + //println!("{:?}", a); + } +} + +fn assert_maps_equivalent(a: &IndexMap, b: &HashMap) -> bool +where + K: Hash + Eq + Debug, + V: Eq + Debug, +{ + assert_eq!(a.len(), b.len()); + assert_eq!(a.iter().next().is_some(), b.iter().next().is_some()); + for key in a.keys() { + assert!(b.contains_key(key), "b does not contain {:?}", key); + } + for key in b.keys() { + assert!(a.get(key).is_some(), "a does not contain {:?}", key); + } + for key in a.keys() { + assert_eq!(a[key], b[key]); + } + true +} + +quickcheck_limit! { + fn operations_i8(ops: Large>>) -> bool { + let mut map = IndexMap::new(); + let mut reference = HashMap::new(); + do_ops(&ops, &mut map, &mut reference); + assert_maps_equivalent(&map, &reference) + } + + fn operations_string(ops: Vec>) -> bool { + let mut map = IndexMap::new(); + let mut reference = HashMap::new(); + do_ops(&ops, &mut map, &mut reference); + assert_maps_equivalent(&map, &reference) + } + + fn keys_values(ops: Large>>) -> bool { + let mut map = IndexMap::new(); + let mut reference = HashMap::new(); + do_ops(&ops, &mut map, &mut reference); + let mut visit = IndexMap::new(); + for (k, v) in map.keys().zip(map.values()) { + assert_eq!(&map[k], v); + assert!(!visit.contains_key(k)); + visit.insert(*k, *v); + } + assert_eq!(visit.len(), reference.len()); + true + } + + fn keys_values_mut(ops: Large>>) -> bool { + let mut map = IndexMap::new(); + let mut reference = HashMap::new(); + do_ops(&ops, &mut map, &mut reference); + let mut visit = IndexMap::new(); + let keys = Vec::from_iter(map.keys().copied()); + for (k, v) in keys.iter().zip(map.values_mut()) { + assert_eq!(&reference[k], v); + assert!(!visit.contains_key(k)); + visit.insert(*k, *v); + } + assert_eq!(visit.len(), reference.len()); + true + } + + fn equality(ops1: Vec>, removes: Vec) -> bool { + let mut map = IndexMap::new(); + let mut reference = HashMap::new(); + do_ops(&ops1, &mut map, &mut reference); + let mut ops2 = ops1.clone(); + for &r in &removes { + if !ops2.is_empty() { + let i = r % ops2.len(); + ops2.remove(i); + } + } + let mut map2 = IndexMapFnv::default(); + let mut reference2 = HashMap::new(); + do_ops(&ops2, &mut map2, &mut reference2); + assert_eq!(map == map2, reference == reference2); + true + } + + fn retain_ordered(keys: Large>, remove: Large>) -> () { + let mut map = indexmap(keys.iter()); + let initial_map = map.clone(); // deduplicated in-order input + let remove_map = indexmap(remove.iter()); + let keys_s = set(keys.iter()); + let remove_s = set(remove.iter()); + let answer = &keys_s - &remove_s; + map.retain(|k, _| !remove_map.contains_key(k)); + + // check the values + assert_eq!(map.len(), answer.len()); + for key in &answer { + assert!(map.contains_key(key)); + } + // check the order + itertools::assert_equal(map.keys(), initial_map.keys().filter(|&k| !remove_map.contains_key(k))); + } + + fn sort_1(keyvals: Large>) -> () { + let mut map: IndexMap<_, _> = IndexMap::from_iter(keyvals.to_vec()); + let mut answer = keyvals.0; + answer.sort_by_key(|t| t.0); + + // reverse dedup: Because IndexMap::from_iter keeps the last value for + // identical keys + answer.reverse(); + answer.dedup_by_key(|t| t.0); + answer.reverse(); + + map.sort_by(|k1, _, k2, _| Ord::cmp(k1, k2)); + + // check it contains all the values it should + for &(key, val) in &answer { + assert_eq!(map[&key], val); + } + + // check the order + + let mapv = Vec::from_iter(map); + assert_eq!(answer, mapv); + + } + + fn sort_2(keyvals: Large>) -> () { + let mut map: IndexMap<_, _> = IndexMap::from_iter(keyvals.to_vec()); + map.sort_by(|_, v1, _, v2| Ord::cmp(v1, v2)); + assert_sorted_by_key(map, |t| t.1); + } + + fn reverse(keyvals: Large>) -> () { + let mut map: IndexMap<_, _> = IndexMap::from_iter(keyvals.to_vec()); + + fn generate_answer(input: &Vec<(i8, i8)>) -> Vec<(i8, i8)> { + // to mimic what `IndexMap::from_iter` does: + // need to get (A) the unique keys in forward order, and (B) the + // last value of each of those keys. + + // create (A): an iterable that yields the unique keys in ltr order + let mut seen_keys = HashSet::new(); + let unique_keys_forward = input.iter().filter_map(move |(k, _)| { + if seen_keys.contains(k) { None } + else { seen_keys.insert(*k); Some(*k) } + }); + + // create (B): a mapping of keys to the last value seen for that key + // this is the same as reversing the input and taking the first + // value seen for that key! + let mut last_val_per_key = HashMap::new(); + for &(k, v) in input.iter().rev() { + if !last_val_per_key.contains_key(&k) { + last_val_per_key.insert(k, v); + } + } + + // iterate over the keys in (A) in order, and match each one with + // the corresponding last value from (B) + let mut ans: Vec<_> = unique_keys_forward + .map(|k| (k, *last_val_per_key.get(&k).unwrap())) + .collect(); + + // finally, since this test is testing `.reverse()`, reverse the + // answer in-place + ans.reverse(); + + ans + } + + let answer = generate_answer(&keyvals.0); + + // perform the work + map.reverse(); + + // check it contains all the values it should + for &(key, val) in &answer { + assert_eq!(map[&key], val); + } + + // check the order + let mapv = Vec::from_iter(map); + assert_eq!(answer, mapv); + } +} + +fn assert_sorted_by_key(iterable: I, key: Key) +where + I: IntoIterator, + I::Item: Ord + Clone + Debug, + Key: Fn(&I::Item) -> X, + X: Ord, +{ + let input = Vec::from_iter(iterable); + let mut sorted = input.clone(); + sorted.sort_by_key(key); + assert_eq!(input, sorted); +} + +#[derive(Clone, Debug, Hash, PartialEq, Eq)] +struct Alpha(String); + +impl Deref for Alpha { + type Target = String; + fn deref(&self) -> &String { + &self.0 + } +} + +const ALPHABET: &[u8] = b"abcdefghijklmnopqrstuvwxyz"; + +impl Arbitrary for Alpha { + fn arbitrary(g: &mut Gen) -> Self { + let len = usize::arbitrary(g) % g.size(); + let len = min(len, 16); + Alpha( + (0..len) + .map(|_| ALPHABET[usize::arbitrary(g) % ALPHABET.len()] as char) + .collect(), + ) + } + + fn shrink(&self) -> Box> { + Box::new((**self).shrink().map(Alpha)) + } +} + +/// quickcheck Arbitrary adaptor -- make a larger vec +#[derive(Clone, Debug)] +struct Large(T); + +impl Deref for Large { + type Target = T; + fn deref(&self) -> &T { + &self.0 + } +} + +impl Arbitrary for Large> +where + T: Arbitrary, +{ + fn arbitrary(g: &mut Gen) -> Self { + let len = usize::arbitrary(g) % (g.size() * 10); + Large((0..len).map(|_| T::arbitrary(g)).collect()) + } + + fn shrink(&self) -> Box> { + Box::new((**self).shrink().map(Large)) + } +} diff --git a/third_party/rust/indexmap/tests/tests.rs b/third_party/rust/indexmap/tests/tests.rs new file mode 100644 index 0000000000..7d522f1c97 --- /dev/null +++ b/third_party/rust/indexmap/tests/tests.rs @@ -0,0 +1,28 @@ +use indexmap::{indexmap, indexset}; + +#[test] +fn test_sort() { + let m = indexmap! { + 1 => 2, + 7 => 1, + 2 => 2, + 3 => 3, + }; + + itertools::assert_equal( + m.sorted_by(|_k1, v1, _k2, v2| v1.cmp(v2)), + vec![(7, 1), (1, 2), (2, 2), (3, 3)], + ); +} + +#[test] +fn test_sort_set() { + let s = indexset! { + 1, + 7, + 2, + 3, + }; + + itertools::assert_equal(s.sorted_by(|v1, v2| v1.cmp(v2)), vec![1, 2, 3, 7]); +} -- cgit v1.2.3