Fix hash function for Tuple

TeamTamoad · youknowone · commit c2955f8e7060 · 2023-02-22T21:56:28.000+09:00
diff --git a/Lib/test/test_tuple.py b/Lib/test/test_tuple.py
@@ -77,8 +77,6 @@ def f():
     # We expect tuples whose base components have deterministic hashes to
     # have deterministic hashes too - and, indeed, the same hashes across
     # platforms with hash codes of the same bit width.
-    # TODO: RUSTPYTHON
-    @unittest.expectedFailure
     def test_hash_exact(self):
         def check_one_exact(t, e32, e64):
             got = hash(t)
diff --git a/vm/src/builtins/range.rs b/vm/src/builtins/range.rs
@@ -1,9 +1,10 @@
-use super::{PyInt, PyIntRef, PySlice, PyTupleRef, PyType, PyTypeRef};
-use crate::atomic_func;
-use crate::common::hash::PyHash;
+use super::{
+    builtins_iter, tuple::tuple_hash, PyInt, PyIntRef, PySlice, PyTupleRef, PyType, PyTypeRef,
+};
 use crate::{
-    builtins::builtins_iter,
+    atomic_func,
     class::PyClassImpl,
+    common::hash::PyHash,
     function::{FuncArgs, OptionalArg, PyComparisonValue},
     protocol::{PyIterReturn, PyMappingMethods, PySequenceMethods},
     types::{
@@ -442,7 +443,7 @@ impl Hashable for PyRange {
                 zelf.step().into(),
             ]
         };
-        crate::utils::hash_iter(elements.iter(), vm)
+        tuple_hash(&elements, vm)
     }
 }
 
diff --git a/vm/src/builtins/tuple.rs b/vm/src/builtins/tuple.rs
@@ -1,9 +1,12 @@
 use once_cell::sync::Lazy;
 
 use super::{PositionIterInternal, PyGenericAlias, PyType, PyTypeRef};
-use crate::atomic_func;
-use crate::common::{hash::PyHash, lock::PyMutex};
+use crate::common::{
+    hash::{PyHash, PyUHash},
+    lock::PyMutex,
+};
 use crate::{
+    atomic_func,
     class::PyClassImpl,
     convert::{ToPyObject, TransmuteFromObject},
     function::{OptionalArg, PyArithmeticValue, PyComparisonValue},
@@ -372,7 +375,7 @@ impl AsSequence for PyTuple {
 impl Hashable for PyTuple {
     #[inline]
     fn hash(zelf: &crate::Py<Self>, vm: &VirtualMachine) -> PyResult<PyHash> {
-        crate::utils::hash_iter(zelf.elements.iter(), vm)
+        tuple_hash(zelf.as_slice(), vm)
     }
 }
 
@@ -523,3 +526,40 @@ impl<T: TransmuteFromObject> ToPyObject for PyTupleTyped<T> {
         self.tuple.into()
     }
 }
+
+pub fn tuple_hash(elements: &[PyObjectRef], vm: &VirtualMachine) -> PyResult<PyHash> {
+    #[cfg(target_pointer_width = "64")]
+    const PRIME1: PyUHash = 11400714785074694791;
+    #[cfg(target_pointer_width = "64")]
+    const PRIME2: PyUHash = 14029467366897019727;
+    #[cfg(target_pointer_width = "64")]
+    const PRIME5: PyUHash = 2870177450012600261;
+    #[cfg(target_pointer_width = "64")]
+    const ROTATE: u32 = 31;
+
+    #[cfg(target_pointer_width = "32")]
+    const PRIME1: PyUHash = 2654435761;
+    #[cfg(target_pointer_width = "32")]
+    const PRIME2: PyUHash = 2246822519;
+    #[cfg(target_pointer_width = "32")]
+    const PRIME5: PyUHash = 374761393;
+    #[cfg(target_pointer_width = "32")]
+    const ROTATE: u32 = 13;
+
+    let mut acc = PRIME5;
+    let len = elements.len() as PyUHash;
+
+    for val in elements {
+        let lane = val.hash(vm)? as PyUHash;
+        acc = acc.wrapping_add(lane.wrapping_mul(PRIME2));
+        acc = acc.rotate_left(ROTATE);
+        acc = acc.wrapping_mul(PRIME1);
+    }
+
+    acc = acc.wrapping_add(len ^ (PRIME5 ^ 3527539));
+
+    if acc as PyHash == -1 {
+        return Ok(1546275796);
+    }
+    Ok(acc as PyHash)
+}
