Merging upstream version 1.67.1+dfsg1.

Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>

1 files changed, 240 insertions, 0 deletions

diff --git a/vendor/litemap/src/testing.rs b/vendor/litemap/src/testing.rs
new file mode 100644
index 000000000..827c8dd23
--- /dev/null
+++ b/vendor/litemap/src/testing.rs
@@ -0,0 +1,240 @@
+// This file is part of ICU4X. For terms of use, please see the file
+// called LICENSE at the top level of the ICU4X source tree
+// (online at: https://github.com/unicode-org/icu4x/blob/main/LICENSE ).
+
+//! Test utilities, primarily targeted to custom LiteMap stores.
+
+use crate::store::*;
+use crate::LiteMap;
+use alloc::vec::Vec;
+use core::fmt::Debug;
+
+// Test code
+#[allow(clippy::expect_used)]
+fn check_equivalence<'a, K, V, S0, S1>(mut a: S0, mut b: S1)
+where
+    K: Ord + Debug + PartialEq + 'a,
+    V: Debug + PartialEq + 'a,
+    S0: StoreMut<K, V> + StoreIterable<'a, K, V>,
+    S1: StoreMut<K, V> + StoreIterable<'a, K, V>,
+{
+    let len = a.lm_len();
+    assert_eq!(len, b.lm_len());
+    if len == 0 {
+        assert!(a.lm_is_empty());
+        assert!(b.lm_is_empty());
+    }
+    for i in 0..len {
+        let a_kv = a.lm_get(i);
+        let b_kv = b.lm_get(i);
+        assert!(a_kv.is_some());
+        assert_eq!(a_kv, b_kv);
+        let a_kv_mut = a.lm_get_mut(i);
+        let b_kv_mut = b.lm_get_mut(i);
+        assert!(a_kv_mut.is_some());
+        assert_eq!(a_kv_mut, b_kv_mut);
+    }
+    for j in 0..len {
+        let needle = a.lm_get(j).expect("j is in range").0;
+        let a_binary = a.lm_binary_search_by(|k| k.cmp(needle));
+        let b_binary = a.lm_binary_search_by(|k| k.cmp(needle));
+        assert_eq!(Ok(j), a_binary);
+        assert_eq!(Ok(j), b_binary);
+    }
+    assert!(a.lm_get(len).is_none());
+    assert!(b.lm_get(len).is_none());
+    assert_eq!(a.lm_last(), b.lm_last());
+}
+
+// Test code
+#[allow(clippy::expect_used)]
+fn check_into_iter_equivalence<'a, K, V, S0, S1>(a: S0, b: S1)
+where
+    K: Ord + Debug + PartialEq + 'a,
+    V: Debug + PartialEq + 'a,
+    S0: StoreIterableMut<'a, K, V>,
+    S1: StoreIterableMut<'a, K, V>,
+{
+    let a_vec = a.lm_into_iter().collect::<Vec<_>>();
+    let b_vec = b.lm_into_iter().collect::<Vec<_>>();
+    assert_eq!(a_vec, b_vec);
+}
+
+const SORTED_DATA: &[(u32, u64)] = &[
+    (106, 4816),
+    (147, 9864),
+    (188, 8588),
+    (252, 6031),
+    (434, 2518),
+    (574, 8500),
+    (607, 3756),
+    (619, 4965),
+    (663, 2669),
+    (724, 9211),
+];
+
+const RANDOM_DATA: &[(u32, u64)] = &[
+    (546, 7490),
+    (273, 4999),
+    (167, 8078),
+    (176, 2101),
+    (373, 1304),
+    (339, 9613),
+    (561, 3620),
+    (301, 1214),
+    (483, 4453),
+    (704, 5359),
+];
+
+// Test code
+#[allow(clippy::expect_used)]
+#[allow(clippy::panic)]
+fn populate_litemap<S>(map: &mut LiteMap<u32, u64, S>)
+where
+    S: StoreMut<u32, u64> + Debug,
+{
+    assert_eq!(0, map.len());
+    assert!(map.is_empty());
+    for (k, v) in SORTED_DATA.iter() {
+        #[allow(clippy::single_match)] // for clarity
+        match map.try_append(*k, *v) {
+            Some(_) => panic!("appending sorted data: {:?} to {:?}", k, map),
+            None => (), // OK
+        };
+    }
+    assert_eq!(10, map.len());
+    for (k, v) in RANDOM_DATA.iter() {
+        #[allow(clippy::single_match)] // for clarity
+        match map.try_append(*k, *v) {
+            Some(_) => (), // OK
+            None => panic!("cannot append random data: {:?} to{:?}", k, map),
+        };
+    }
+    assert_eq!(10, map.len());
+    for (k, v) in RANDOM_DATA.iter() {
+        map.insert(*k, *v);
+    }
+    assert_eq!(20, map.len());
+}
+
+/// Tests that a litemap that uses the given store as backend has behavior consistent with the
+/// reference impl.
+///
+/// Call this function in a test with the store impl to test as a valid backend for LiteMap.
+// Test code
+#[allow(clippy::expect_used)]
+pub fn check_store<'a, S>()
+where
+    S: StoreConstEmpty<u32, u64>
+        + StoreMut<u32, u64>
+        + StoreIterable<'a, u32, u64>
+        + StoreFromIterator<u32, u64>
+        + Clone
+        + Debug
+        + PartialEq
+        + 'a,
+{
+    let mut litemap_test: LiteMap<u32, u64, S> = LiteMap::new();
+    assert!(litemap_test.is_empty());
+    let mut litemap_std = LiteMap::<u32, u64>::new();
+    populate_litemap(&mut litemap_test);
+    populate_litemap(&mut litemap_std);
+    check_equivalence(litemap_test.clone().values, litemap_std.clone().values);
+
+    litemap_test.retain(|_, v| v % 2 == 0);
+    litemap_std.retain(|_, v| v % 2 == 0);
+    assert_eq!(11, litemap_test.len());
+    assert_eq!(11, litemap_std.len());
+    check_equivalence(litemap_test.clone().values, litemap_std.clone().values);
+
+    litemap_test
+        .remove(&175)
+        .ok_or(())
+        .expect_err("does not exist");
+    litemap_test.remove(&147).ok_or(()).expect("exists");
+    litemap_std
+        .remove(&175)
+        .ok_or(())
+        .expect_err("does not exist");
+    litemap_std.remove(&147).ok_or(()).expect("exists");
+
+    assert_eq!(10, litemap_test.len());
+    assert_eq!(10, litemap_std.len());
+    check_equivalence(litemap_test.clone().values, litemap_std.clone().values);
+
+    litemap_test.clear();
+    litemap_std.clear();
+    check_equivalence(litemap_test.values, litemap_std.values);
+}
+
+/// Similar to [`check_store`] function, but also checks the validitiy of [`StoreIterableMut`]
+/// trait.
+// Test code
+#[allow(clippy::expect_used)]
+pub fn check_store_full<'a, S>()
+where
+    S: StoreConstEmpty<u32, u64>
+        + StoreIterableMut<'a, u32, u64>
+        + StoreFromIterator<u32, u64>
+        + Clone
+        + Debug
+        + PartialEq
+        + 'a,
+{
+    let mut litemap_test: LiteMap<u32, u64, S> = LiteMap::new();
+    assert!(litemap_test.is_empty());
+    let mut litemap_std = LiteMap::<u32, u64>::new();
+    populate_litemap(&mut litemap_test);
+    populate_litemap(&mut litemap_std);
+    check_equivalence(litemap_test.clone().values, litemap_std.clone().values);
+    check_into_iter_equivalence(litemap_test.clone().values, litemap_std.clone().values);
+
+    let extras_test = litemap_test.clone();
+    let extras_test = litemap_test
+        .extend_from_litemap(extras_test)
+        .expect("duplicates");
+    assert_eq!(extras_test, litemap_test);
+    let extras_std = litemap_std.clone();
+    check_equivalence(litemap_test.clone().values, litemap_std.clone().values);
+    check_into_iter_equivalence(litemap_test.clone().values, litemap_std.clone().values);
+
+    litemap_test.retain(|_, v| v % 2 == 0);
+    litemap_std.retain(|_, v| v % 2 == 0);
+    assert_eq!(11, litemap_test.len());
+    assert_eq!(11, litemap_std.len());
+    check_equivalence(litemap_test.clone().values, litemap_std.clone().values);
+    check_into_iter_equivalence(litemap_test.clone().values, litemap_std.clone().values);
+
+    let extras_test = litemap_test
+        .extend_from_litemap(extras_test)
+        .expect("duplicates");
+    let extras_std = litemap_std
+        .extend_from_litemap(extras_std)
+        .expect("duplicates");
+    assert_eq!(11, extras_test.len());
+    assert_eq!(11, extras_std.len());
+    assert_eq!(20, litemap_test.len());
+    assert_eq!(20, litemap_std.len());
+    check_equivalence(litemap_test.clone().values, litemap_std.clone().values);
+    check_into_iter_equivalence(litemap_test.clone().values, litemap_std.clone().values);
+
+    litemap_test
+        .remove(&175)
+        .ok_or(())
+        .expect_err("does not exist");
+    litemap_test.remove(&176).ok_or(()).expect("exists");
+    litemap_std
+        .remove(&175)
+        .ok_or(())
+        .expect_err("does not exist");
+    litemap_std.remove(&176).ok_or(()).expect("exists");
+    assert_eq!(19, litemap_test.len());
+    assert_eq!(19, litemap_std.len());
+    check_equivalence(litemap_test.clone().values, litemap_std.clone().values);
+    check_into_iter_equivalence(litemap_test.clone().values, litemap_std.clone().values);
+
+    litemap_test.clear();
+    litemap_std.clear();
+    check_equivalence(litemap_test.clone().values, litemap_std.clone().values);
+    check_into_iter_equivalence(litemap_test.values, litemap_std.values);
+}