From fea3466093936116d57606b0e5083f5d1121f146 Mon Sep 17 00:00:00 2001
From: Yury Selivanov <yury@magic.io>
Date: Sun, 1 Apr 2018 18:01:18 -0400
Subject: Implement Map.__hash__

---
 Makefile          |  2 ++
 immutables/_map.c | 65 ++++++++++++++++++++++++++++++++++++++++++++++++++++---
 immutables/_map.h |  1 +
 tests/test_map.py | 27 +++++++++++++++++++++++
 4 files changed, 92 insertions(+), 3 deletions(-)

diff --git a/Makefile b/Makefile
index 68f4b1e..f698d35 100644
--- a/Makefile
+++ b/Makefile
@@ -8,5 +8,7 @@ test:
 	python setup.py test -v
 
 rtest:
+	~/dev/venvs/36-debug/bin/python setup.py build_ext --inplace
+
 	env PYTHONPATH=. \
 		~/dev/venvs/36-debug/bin/python -m test.regrtest -R3:3 --testdir tests/
diff --git a/immutables/_map.c b/immutables/_map.c
index 6f76318..445b713 100644
--- a/immutables/_map.c
+++ b/immutables/_map.c
@@ -2453,6 +2453,8 @@ map_alloc(void)
         return NULL;
     }
     o->h_weakreflist = NULL;
+    o->h_hash = -1;
+    o->h_count = 0;
     PyObject_GC_Track(o);
     return o;
 }
@@ -2478,8 +2480,6 @@ map_new(void)
         return NULL;
     }
 
-    o->h_count = 0;
-
     if (_empty_map == NULL) {
         Py_INCREF(o);
         _empty_map = o;
@@ -2942,6 +2942,65 @@ error:
 }
 
 
+static Py_uhash_t
+_shuffle_bits(Py_uhash_t h)
+{
+    return ((h ^ 89869747UL) ^ (h << 16)) * 3644798167UL;
+}
+
+
+static Py_hash_t
+map_py_hash(MapObject *self)
+{
+    /* Adapted version of frozenset.__hash__: it's important
+       that Map.__hash__ is independant of key/values order.
+
+       Optimization idea: compute and memoize intermediate
+       hash values for HAMT nodes.
+    */
+
+    if (self->h_hash != -1) {
+        return self->h_hash;
+    }
+
+    Py_uhash_t hash = 0;
+
+    MapIteratorState iter;
+    map_iter_t iter_res;
+    map_iterator_init(&iter, self->h_root);
+    do {
+        PyObject *v_key;
+        PyObject *v_val;
+
+        iter_res = map_iterator_next(&iter, &v_key, &v_val);
+        if (iter_res == I_ITEM) {
+            Py_hash_t vh = PyObject_Hash(v_key);
+            if (vh == -1) {
+                return -1;
+            }
+            hash ^= _shuffle_bits((Py_uhash_t)vh);
+
+            vh = PyObject_Hash(v_val);
+            if (vh == -1) {
+                return -1;
+            }
+            hash ^= _shuffle_bits((Py_uhash_t)vh);
+        }
+    } while (iter_res != I_END);
+
+    hash ^= ((Py_uhash_t)self->h_count * 2 + 1) * 1927868237UL;
+
+    hash ^= (hash >> 11) ^ (hash >> 25);
+    hash = hash * 69069U + 907133923UL;
+
+    self->h_hash = (Py_hash_t)hash;
+    if (self->h_hash == -1) {
+        self->h_hash = 1;
+    }
+    return self->h_hash;
+}
+
+
 static PyMethodDef Map_methods[] = {
     {"set", (PyCFunction)map_py_set, METH_VARARGS, NULL},
     {"get", (PyCFunction)map_py_get, METH_VARARGS, NULL},
@@ -2987,7 +3046,7 @@ PyTypeObject _Map_Type = {
     .tp_clear = (inquiry)map_tp_clear,
     .tp_new = map_tp_new,
     .tp_weaklistoffset = offsetof(MapObject, h_weakreflist),
-    .tp_hash = PyObject_HashNotImplemented,
+    .tp_hash = (hashfunc)map_py_hash,
     .tp_repr = (reprfunc)map_py_repr,
 };
 
diff --git a/immutables/_map.h b/immutables/_map.h
index 41cfa13..6e87c4b 100644
--- a/immutables/_map.h
+++ b/immutables/_map.h
@@ -22,6 +22,7 @@ typedef struct {
     MapNode *h_root;
     PyObject *h_weakreflist;
     Py_ssize_t h_count;
+    Py_hash_t h_hash;
 } MapObject;
 
 
diff --git a/tests/test_map.py b/tests/test_map.py
index 06c82b9..91050a2 100644
--- a/tests/test_map.py
+++ b/tests/test_map.py
@@ -757,6 +757,33 @@ class MapTest(unittest.TestCase):
         self.assertTrue(repr(h).startswith(
             '<immutables.Map({{...}: 1}) at 0x'))
 
+    def test_hash_1(self):
+        h = Map()
+        self.assertNotEqual(hash(h), -1)
+        self.assertEqual(hash(h), hash(h))
+
+        h = h.set(1, 2).set('a', 'b')
+        self.assertNotEqual(hash(h), -1)
+        self.assertEqual(hash(h), hash(h))
+
+        self.assertEqual(
+            hash(h.set(1, 2).set('a', 'b')),
+            hash(h.set('a', 'b').set(1, 2)))
+
+    def test_hash_2(self):
+        h = Map()
+        A = HashKey(100, 'A')
+
+        m = h.set(1, 2).set(A, 3).set(3, 4)
+        with self.assertRaises(HashingError):
+            with HaskKeyCrasher(error_on_hash=True):
+                hash(m)
+
+        m = h.set(1, 2).set(2, A).set(3, 4)
+        with self.assertRaises(HashingError):
+            with HaskKeyCrasher(error_on_hash=True):
+                hash(m)
+
 
 if __name__ == "__main__":
     unittest.main()
-- 
cgit v1.2.3