Adding upstream version 127.0.upstream/127.0

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

3 files changed, 258 insertions, 97 deletions

diff --git a/third_party/rust/ahash/tests/bench.rs b/third_party/rust/ahash/tests/bench.rs
index 9e6dccc481..2d000c0a6a 100644
--- a/third_party/rust/ahash/tests/bench.rs
+++ b/third_party/rust/ahash/tests/bench.rs
@@ -1,39 +1,35 @@
-use ahash::{CallHasher, RandomState};
+#![cfg_attr(feature = "specialize", feature(build_hasher_simple_hash_one))]
+
+use ahash::{AHasher, RandomState};
 use criterion::*;
 use fxhash::FxHasher;
+use rand::Rng;
 use std::collections::hash_map::DefaultHasher;
-use std::hash::{Hash, Hasher};
-
-#[cfg(any(
-    all(any(target_arch = "x86", target_arch = "x86_64"), target_feature = "aes", not(miri)),
-    all(any(target_arch = "arm", target_arch = "aarch64"), target_feature = "crypto", not(miri), feature = "stdsimd")
-))]
-fn aeshash<H: Hash>(b: &H) -> u64 {
+use std::hash::{BuildHasherDefault, Hash, Hasher};
+
+// Needs to be in sync with `src/lib.rs`
+const AHASH_IMPL: &str = if cfg!(any(
+    all(
+        any(target_arch = "x86", target_arch = "x86_64"),
+        target_feature = "aes",
+        not(miri),
+    ),
+    all(feature = "nightly-arm-aes", target_arch = "aarch64", target_feature = "aes", not(miri)),
+    all(
+        feature = "nightly-arm-aes",
+        target_arch = "arm",
+        target_feature = "aes",
+        not(miri)
+    ),
+)) {
+    "aeshash"
+} else {
+    "fallbackhash"
+};
+
+fn ahash<H: Hash>(b: &H) -> u64 {
     let build_hasher = RandomState::with_seeds(1, 2, 3, 4);
-    H::get_hash(b, &build_hasher)
-}
-#[cfg(not(any(
-    all(any(target_arch = "x86", target_arch = "x86_64"), target_feature = "aes", not(miri)),
-    all(any(target_arch = "arm", target_arch = "aarch64"), target_feature = "crypto", not(miri), feature = "stdsimd")
-)))]
-fn aeshash<H: Hash>(_b: &H) -> u64 {
-    panic!("aes must be enabled")
-}
-
-#[cfg(not(any(
-    all(any(target_arch = "x86", target_arch = "x86_64"), target_feature = "aes", not(miri)),
-    all(any(target_arch = "arm", target_arch = "aarch64"), target_feature = "crypto", not(miri), feature = "stdsimd")
-)))]
-fn fallbackhash<H: Hash>(b: &H) -> u64 {
-    let build_hasher = RandomState::with_seeds(1, 2, 3, 4);
-    H::get_hash(b, &build_hasher)
-}
-#[cfg(any(
-    all(any(target_arch = "x86", target_arch = "x86_64"), target_feature = "aes", not(miri)),
-    all(any(target_arch = "arm", target_arch = "aarch64"), target_feature = "crypto", not(miri), feature = "stdsimd")
-))]
-fn fallbackhash<H: Hash>(_b: &H) -> u64 {
-    panic!("aes must be disabled")
+    build_hasher.hash_one(b)
 }
 
 fn fnvhash<H: Hash>(b: &H) -> u64 {
@@ -76,79 +72,128 @@ fn gen_strings() -> Vec<String> {
         .collect()
 }
 
-const U8_VALUE: u8 = 123;
-const U16_VALUE: u16 = 1234;
-const U32_VALUE: u32 = 12345678;
-const U64_VALUE: u64 = 1234567890123456;
-const U128_VALUE: u128 = 12345678901234567890123456789012;
-
-fn bench_ahash(c: &mut Criterion) {
-    let mut group = c.benchmark_group("aeshash");
-    group.bench_with_input("u8", &U8_VALUE, |b, s| b.iter(|| black_box(aeshash(s))));
-    group.bench_with_input("u16", &U16_VALUE, |b, s| b.iter(|| black_box(aeshash(s))));
-    group.bench_with_input("u32", &U32_VALUE, |b, s| b.iter(|| black_box(aeshash(s))));
-    group.bench_with_input("u64", &U64_VALUE, |b, s| b.iter(|| black_box(aeshash(s))));
-    group.bench_with_input("u128", &U128_VALUE, |b, s| b.iter(|| black_box(aeshash(s))));
-    group.bench_with_input("string", &gen_strings(), |b, s| b.iter(|| black_box(aeshash(s))));
+macro_rules! bench_inputs {
+    ($group:ident, $hash:ident) => {
+        // Number of iterations per batch should be high enough to hide timing overhead.
+        let size = BatchSize::NumIterations(50_000);
+
+        let mut rng = rand::thread_rng();
+        $group.bench_function("u8", |b| b.iter_batched(|| rng.gen::<u8>(), |v| $hash(&v), size));
+        $group.bench_function("u16", |b| b.iter_batched(|| rng.gen::<u16>(), |v| $hash(&v), size));
+        $group.bench_function("u32", |b| b.iter_batched(|| rng.gen::<u32>(), |v| $hash(&v), size));
+        $group.bench_function("u64", |b| b.iter_batched(|| rng.gen::<u64>(), |v| $hash(&v), size));
+        $group.bench_function("u128", |b| b.iter_batched(|| rng.gen::<u128>(), |v| $hash(&v), size));
+        $group.bench_with_input("strings", &gen_strings(), |b, s| b.iter(|| $hash(black_box(s))));
+    };
 }
 
-fn bench_fallback(c: &mut Criterion) {
-    let mut group = c.benchmark_group("fallback");
-    group.bench_with_input("u8", &U8_VALUE, |b, s| b.iter(|| black_box(fallbackhash(s))));
-    group.bench_with_input("u16", &U16_VALUE, |b, s| b.iter(|| black_box(fallbackhash(s))));
-    group.bench_with_input("u32", &U32_VALUE, |b, s| b.iter(|| black_box(fallbackhash(s))));
-    group.bench_with_input("u64", &U64_VALUE, |b, s| b.iter(|| black_box(fallbackhash(s))));
-    group.bench_with_input("u128", &U128_VALUE, |b, s| b.iter(|| black_box(fallbackhash(s))));
-    group.bench_with_input("string", &gen_strings(), |b, s| b.iter(|| black_box(fallbackhash(s))));
+fn bench_ahash(c: &mut Criterion) {
+    let mut group = c.benchmark_group(AHASH_IMPL);
+    bench_inputs!(group, ahash);
 }
 
 fn bench_fx(c: &mut Criterion) {
     let mut group = c.benchmark_group("fx");
-    group.bench_with_input("u8", &U8_VALUE, |b, s| b.iter(|| black_box(fxhash(s))));
-    group.bench_with_input("u16", &U16_VALUE, |b, s| b.iter(|| black_box(fxhash(s))));
-    group.bench_with_input("u32", &U32_VALUE, |b, s| b.iter(|| black_box(fxhash(s))));
-    group.bench_with_input("u64", &U64_VALUE, |b, s| b.iter(|| black_box(fxhash(s))));
-    group.bench_with_input("u128", &U128_VALUE, |b, s| b.iter(|| black_box(fxhash(s))));
-    group.bench_with_input("string", &gen_strings(), |b, s| b.iter(|| black_box(fxhash(s))));
+    bench_inputs!(group, fxhash);
 }
 
 fn bench_fnv(c: &mut Criterion) {
     let mut group = c.benchmark_group("fnv");
-    group.bench_with_input("u8", &U8_VALUE, |b, s| b.iter(|| black_box(fnvhash(s))));
-    group.bench_with_input("u16", &U16_VALUE, |b, s| b.iter(|| black_box(fnvhash(s))));
-    group.bench_with_input("u32", &U32_VALUE, |b, s| b.iter(|| black_box(fnvhash(s))));
-    group.bench_with_input("u64", &U64_VALUE, |b, s| b.iter(|| black_box(fnvhash(s))));
-    group.bench_with_input("u128", &U128_VALUE, |b, s| b.iter(|| black_box(fnvhash(s))));
-    group.bench_with_input("string", &gen_strings(), |b, s| b.iter(|| black_box(fnvhash(s))));
+    bench_inputs!(group, fnvhash);
 }
 
 fn bench_sea(c: &mut Criterion) {
     let mut group = c.benchmark_group("sea");
-    group.bench_with_input("u8", &U8_VALUE, |b, s| b.iter(|| black_box(seahash(s))));
-    group.bench_with_input("u16", &U16_VALUE, |b, s| b.iter(|| black_box(seahash(s))));
-    group.bench_with_input("u32", &U32_VALUE, |b, s| b.iter(|| black_box(seahash(s))));
-    group.bench_with_input("u64", &U64_VALUE, |b, s| b.iter(|| black_box(seahash(s))));
-    group.bench_with_input("u128", &U128_VALUE, |b, s| b.iter(|| black_box(seahash(s))));
-    group.bench_with_input("string", &gen_strings(), |b, s| b.iter(|| black_box(seahash(s))));
+    bench_inputs!(group, seahash);
 }
 
 fn bench_sip(c: &mut Criterion) {
     let mut group = c.benchmark_group("sip");
-    group.bench_with_input("u8", &U8_VALUE, |b, s| b.iter(|| black_box(siphash(s))));
-    group.bench_with_input("u16", &U16_VALUE, |b, s| b.iter(|| black_box(siphash(s))));
-    group.bench_with_input("u32", &U32_VALUE, |b, s| b.iter(|| black_box(siphash(s))));
-    group.bench_with_input("u64", &U64_VALUE, |b, s| b.iter(|| black_box(siphash(s))));
-    group.bench_with_input("u128", &U128_VALUE, |b, s| b.iter(|| black_box(siphash(s))));
-    group.bench_with_input("string", &gen_strings(), |b, s| b.iter(|| black_box(siphash(s))));
+    bench_inputs!(group, siphash);
+}
+
+fn bench_map(c: &mut Criterion) {
+    #[cfg(feature = "std")]
+    {
+        let mut group = c.benchmark_group("map");
+        group.bench_function("aHash-alias", |b| {
+            b.iter(|| {
+                let hm: ahash::HashMap<i32, i32> = (0..1_000_000).map(|i| (i, i)).collect();
+                let mut sum = 0;
+                for i in 0..1_000_000 {
+                    if let Some(x) = hm.get(&i) {
+                        sum += x;
+                    }
+                }
+            })
+        });
+        group.bench_function("aHash-hashBrown", |b| {
+            b.iter(|| {
+                let hm: hashbrown::HashMap<i32, i32> = (0..1_000_000).map(|i| (i, i)).collect();
+                let mut sum = 0;
+                for i in 0..1_000_000 {
+                    if let Some(x) = hm.get(&i) {
+                        sum += x;
+                    }
+                }
+            })
+        });
+        group.bench_function("aHash-hashBrown-explicit", |b| {
+            b.iter(|| {
+                let hm: hashbrown::HashMap<i32, i32, RandomState> = (0..1_000_000).map(|i| (i, i)).collect();
+                let mut sum = 0;
+                for i in 0..1_000_000 {
+                    if let Some(x) = hm.get(&i) {
+                        sum += x;
+                    }
+                }
+            })
+        });
+        group.bench_function("aHash-wrapper", |b| {
+            b.iter(|| {
+                let hm: ahash::AHashMap<i32, i32> = (0..1_000_000).map(|i| (i, i)).collect();
+                let mut sum = 0;
+                for i in 0..1_000_000 {
+                    if let Some(x) = hm.get(&i) {
+                        sum += x;
+                    }
+                }
+            })
+        });
+        group.bench_function("aHash-rand", |b| {
+            b.iter(|| {
+                let hm: std::collections::HashMap<i32, i32, RandomState> = (0..1_000_000).map(|i| (i, i)).collect();
+                let mut sum = 0;
+                for i in 0..1_000_000 {
+                    if let Some(x) = hm.get(&i) {
+                        sum += x;
+                    }
+                }
+            })
+        });
+        group.bench_function("aHash-default", |b| {
+            b.iter(|| {
+                let hm: std::collections::HashMap<i32, i32, BuildHasherDefault<AHasher>> =
+                    (0..1_000_000).map(|i| (i, i)).collect();
+                let mut sum = 0;
+                for i in 0..1_000_000 {
+                    if let Some(x) = hm.get(&i) {
+                        sum += x;
+                    }
+                }
+            })
+        });
+    }
 }
 
 criterion_main!(benches);
+
 criterion_group!(
     benches,
     bench_ahash,
-    bench_fallback,
     bench_fx,
     bench_fnv,
     bench_sea,
-    bench_sip
+    bench_sip,
+    bench_map
 );
diff --git a/third_party/rust/ahash/tests/map_tests.rs b/third_party/rust/ahash/tests/map_tests.rs
index be617a2e72..97fdbee0f9 100644
--- a/third_party/rust/ahash/tests/map_tests.rs
+++ b/third_party/rust/ahash/tests/map_tests.rs
@@ -1,10 +1,11 @@
+#![cfg_attr(feature = "specialize", feature(build_hasher_simple_hash_one))]
+
 use std::hash::{BuildHasher, Hash, Hasher};
 
+use ahash::RandomState;
 use criterion::*;
 use fxhash::FxHasher;
 
-use ahash::{AHasher, CallHasher, RandomState};
-
 fn gen_word_pairs() -> Vec<String> {
     let words: Vec<_> = r#"
 a, ability, able, about, above, accept, according, account, across, act, action,
@@ -150,9 +151,18 @@ fn check_for_collisions<H: Hash, B: BuildHasher>(build_hasher: &B, items: &[H],
     );
 }
 
+#[cfg(feature = "specialize")]
+#[allow(unused)] // False positive
+fn hash<H: Hash, B: BuildHasher>(b: &H, build_hasher: &B) -> u64 {
+    build_hasher.hash_one(b)
+}
+
+#[cfg(not(feature = "specialize"))]
 #[allow(unused)] // False positive
 fn hash<H: Hash, B: BuildHasher>(b: &H, build_hasher: &B) -> u64 {
-    H::get_hash(b, build_hasher)
+    let mut hasher = build_hasher.build_hasher();
+    b.hash(&mut hasher);
+    hasher.finish()
 }
 
 #[test]
@@ -169,10 +179,107 @@ fn test_bucket_distribution() {
     check_for_collisions(&build_hasher, &sequence, 256);
 }
 
+#[cfg(feature = "std")]
+#[test]
+fn test_ahash_alias_map_construction() {
+    let mut map = ahash::HashMap::default();
+    map.insert(1, "test");
+    use ahash::HashMapExt;
+    let mut map = ahash::HashMap::with_capacity(1234);
+    map.insert(1, "test");
+}
+
+#[cfg(feature = "std")]
+#[test]
+fn test_ahash_alias_set_construction() {
+    let mut set = ahash::HashSet::default();
+    set.insert(1);
+
+    use ahash::HashSetExt;
+    let mut set = ahash::HashSet::with_capacity(1235);
+    set.insert(1);
+}
+
+
+#[cfg(feature = "std")]
+#[test]
+fn test_key_ref() {
+    let mut map = ahash::HashMap::default();
+    map.insert(1, "test");
+    assert_eq!(Some((1, "test")), map.remove_entry(&1));
+
+    let mut map = ahash::HashMap::default();
+    map.insert(&1, "test");
+    assert_eq!(Some((&1, "test")), map.remove_entry(&&1));
+
+    let mut m = ahash::HashSet::<Box<String>>::default();
+    m.insert(Box::from("hello".to_string()));
+    assert!(m.contains(&"hello".to_string()));
+
+    let mut m = ahash::HashSet::<String>::default();
+    m.insert("hello".to_string());
+    assert!(m.contains("hello"));
+
+    let mut m = ahash::HashSet::<Box<[u8]>>::default();
+    m.insert(Box::from(&b"hello"[..]));
+    assert!(m.contains(&b"hello"[..]));
+}
+
+#[cfg(feature = "std")]
+#[test]
+fn test_byte_dist() {
+    use rand::{SeedableRng, Rng, RngCore};
+    use pcg_mwc::Mwc256XXA64;
+
+    let mut r = Mwc256XXA64::seed_from_u64(0xe786_c22b_119c_1479);
+    let mut lowest = 2.541;
+    let mut highest = 2.541;
+    for _round in 0..100 {
+        let mut table: [bool; 256 * 8] = [false; 256 * 8];
+        let hasher = RandomState::with_seeds(r.gen(), r.gen(), r.gen(), r.gen());
+        for i in 0..128 {
+            let mut keys: [u8; 8] = hasher.hash_one((i as u64) << 30).to_ne_bytes();
+            //let mut keys = r.next_u64().to_ne_bytes(); //This is a control to test assert sensitivity.
+            for idx in 0..8 {
+                while table[idx * 256 + keys[idx] as usize] {
+                    keys[idx] = keys[idx].wrapping_add(1);
+                }
+                table[idx * 256 + keys[idx] as usize] = true;
+            }
+        }
+
+        for idx in 0..8 {
+            let mut len = 0;
+            let mut total_len = 0;
+            let mut num_seq = 0;
+            for i in 0..256 {
+                if table[idx * 256 + i] {
+                    len += 1;
+                } else if len != 0 {
+                    num_seq += 1;
+                    total_len += len;
+                    len = 0;
+                }
+            }
+            let mean = total_len as f32 / num_seq as f32;
+            println!("Mean sequence length = {}", mean);
+            if mean > highest {
+                highest = mean;
+            }
+            if mean < lowest {
+                lowest = mean;
+            }
+        }
+    }
+    assert!(lowest > 1.9, "Lowest = {}", lowest);
+    assert!(highest < 3.9, "Highest = {}", highest);
+}
+
+
 fn ahash_vec<H: Hash>(b: &Vec<H>) -> u64 {
     let mut total: u64 = 0;
     for item in b {
-        let mut hasher = AHasher::new_with_keys(1234, 5678);
+        let mut hasher = RandomState::with_seeds(12, 34, 56, 78).build_hasher();
         item.hash(&mut hasher);
         total = total.wrapping_add(hasher.finish());
     }
diff --git a/third_party/rust/ahash/tests/nopanic.rs b/third_party/rust/ahash/tests/nopanic.rs
index d48ff559d2..56f754cbee 100644
--- a/third_party/rust/ahash/tests/nopanic.rs
+++ b/third_party/rust/ahash/tests/nopanic.rs
@@ -1,5 +1,5 @@
-use ahash::{AHasher, CallHasher, RandomState};
-use std::hash::BuildHasher;
+use ahash::{AHasher, RandomState};
+use std::hash::{BuildHasher, Hash, Hasher};
 
 #[macro_use]
 extern crate no_panic;
@@ -8,8 +8,8 @@ extern crate no_panic;
 #[no_panic]
 fn hash_test_final(num: i32, string: &str) -> (u64, u64) {
     use core::hash::Hasher;
-    let mut hasher1 = AHasher::new_with_keys(1, 2);
-    let mut hasher2 = AHasher::new_with_keys(3, 4);
+    let mut hasher1 = RandomState::with_seeds(1, 2, 3, 4).build_hasher();
+    let mut hasher2 = RandomState::with_seeds(3, 4, 5, 6).build_hasher();
     hasher1.write_i32(num);
     hasher2.write(string.as_bytes());
     (hasher1.finish(), hasher2.finish())
@@ -24,6 +24,17 @@ struct SimpleBuildHasher {
     hasher: AHasher,
 }
 
+impl SimpleBuildHasher {
+    fn hash_one<T: Hash>(&self, x: T) -> u64
+    where
+        Self: Sized,
+    {
+        let mut hasher = self.build_hasher();
+        x.hash(&mut hasher);
+        hasher.finish()
+    }
+}
+
 impl BuildHasher for SimpleBuildHasher {
     type Hasher = AHasher;
 
@@ -35,11 +46,11 @@ impl BuildHasher for SimpleBuildHasher {
 #[inline(never)]
 #[no_panic]
 fn hash_test_specialize(num: i32, string: &str) -> (u64, u64) {
-    let hasher1 = AHasher::new_with_keys(1, 2);
-    let hasher2 = AHasher::new_with_keys(1, 2);
+    let hasher1 = RandomState::with_seeds(1, 2, 3, 4).build_hasher();
+    let hasher2 = RandomState::with_seeds(1, 2, 3, 4).build_hasher();
     (
-        i32::get_hash(&num, &SimpleBuildHasher { hasher: hasher1 }),
-        <[u8]>::get_hash(string.as_bytes(), &SimpleBuildHasher { hasher: hasher2 }),
+        SimpleBuildHasher { hasher: hasher1 }.hash_one(num),
+        SimpleBuildHasher { hasher: hasher2 }.hash_one(string.as_bytes()),
     )
 }
 
@@ -53,10 +64,7 @@ fn hash_test_random_wrapper(num: i32, string: &str) {
 fn hash_test_random(num: i32, string: &str) -> (u64, u64) {
     let build_hasher1 = RandomState::with_seeds(1, 2, 3, 4);
     let build_hasher2 = RandomState::with_seeds(1, 2, 3, 4);
-    (
-        i32::get_hash(&num, &build_hasher1),
-        <[u8]>::get_hash(string.as_bytes(), &build_hasher2),
-    )
+    (build_hasher1.hash_one(&num), build_hasher2.hash_one(string.as_bytes()))
 }
 
 #[inline(never)]
@@ -68,5 +76,6 @@ fn hash_test_specialize_wrapper(num: i32, string: &str) {
 fn test_no_panic() {
     hash_test_final_wrapper(2, "Foo");
     hash_test_specialize_wrapper(2, "Bar");
-    hash_test_random_wrapper(2, "Baz");
+    hash_test_random(2, "Baz");
+    hash_test_random_wrapper(2, "Bat");
 }