Fix hash function for Tuple

TeamTamoad · youknowone · commit cc65be9f0cc9 · 2022-08-05T05:21:38.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,7 +1,8 @@
-use super::{PyInt, PyIntRef, PySlice, PyTupleRef, PyType, PyTypeRef};
+use super::{
+    builtins_iter, tuple::tuple_hash, PyInt, PyIntRef, PySlice, PyTupleRef, PyType, PyTypeRef,
+};
 use crate::common::hash::PyHash;
 use crate::{
-    builtins::builtins_iter,
     class::PyClassImpl,
     function::{FuncArgs, OptionalArg, PyComparisonValue},
     protocol::{PyIterReturn, PyMappingMethods, PySequenceMethods},
@@ -440,7 +441,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,5 +1,8 @@
 use super::{PositionIterInternal, PyGenericAlias, PyType, PyTypeRef};
-use crate::common::{hash::PyHash, lock::PyMutex};
+use crate::common::{
+    hash::{PyHash, PyUHash},
+    lock::PyMutex,
+};
 use crate::{
     class::PyClassImpl,
     convert::{ToPyObject, TransmuteFromObject},
@@ -371,7 +374,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)
     }
 }
 
@@ -522,3 +525,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)
+}

Original file line number	Diff line number	Diff line change
`@@ -1,7 +1,8 @@`
`1`		`-use super::{PyInt, PyIntRef, PySlice, PyTupleRef, PyType, PyTypeRef};`
	`1`	`+use super::{`
	`2`	`+ builtins_iter, tuple::tuple_hash, PyInt, PyIntRef, PySlice, PyTupleRef, PyType, PyTypeRef,`
	`3`	`+};`
`2`	`4`	`use crate::common::hash::PyHash;`
`3`	`5`	`use crate::{`
`4`		`- builtins::builtins_iter,`
`5`	`6`	`class::PyClassImpl,`
`6`	`7`	`function::{FuncArgs, OptionalArg, PyComparisonValue},`
`7`	`8`	`protocol::{PyIterReturn, PyMappingMethods, PySequenceMethods},`
`@@ -440,7 +441,7 @@ impl Hashable for PyRange {`
`440`	`441`	`zelf.step().into(),`
`441`	`442`	`]`
`442`	`443`	`};`
`443`		`- crate::utils::hash_iter(elements.iter(), vm)`
	`444`	`+ tuple_hash(&elements, vm)`
`444`	`445`	`}`
`445`	`446`	`}`
`446`	`447`