Accept None as a key in pure python module (#42)

1 files changed, 511 insertions, 0 deletions

diff --git a/tests/test_none_keys.py b/tests/test_none_keys.py
new file mode 100644
index 0000000..3662e9c
--- /dev/null
+++ b/tests/test_none_keys.py
@@ -0,0 +1,511 @@
+import unittest
+
+from immutables.map import map_hash, map_mask, Map as PyMap
+from tests.test_map import HashKey
+
+
+none_hash = map_hash(None)
+assert(none_hash != 1)
+assert((none_hash >> 32) == 0)
+
+not_collision = 0xffffffff & (~none_hash)
+
+mask = 0x7ffffffff
+none_collisions = [none_hash & (mask >> shift)
+                   for shift in reversed(range(0, 32, 5))]
+assert(len(none_collisions) == 7)
+none_collisions = [h | (not_collision & (mask << shift))
+                   for shift, h in zip(range(5, 37, 5), none_collisions)]
+
+
+class NoneCollision(HashKey):
+    def __init__(self, name, level):
+        if name is None:
+            raise ValueError("Can't have a NoneCollision with a None value")
+        super().__init__(none_collisions[level], name)
+
+    def __eq__(self, other):
+        if other is None:
+            return False
+        return super().__eq__(other)
+
+    __hash__ = HashKey.__hash__
+
+
+class BaseNoneTest:
+    Map = None
+
+    def test_none_collisions(self):
+        collisions = [NoneCollision('a', level) for level in range(7)]
+        indices = [map_mask(none_hash, shift) for shift in range(0, 32, 5)]
+
+        for i, c in enumerate(collisions[:-1], 1):
+            self.assertNotEqual(c, None)
+            c_hash = map_hash(c)
+            self.assertNotEqual(c_hash, none_hash)
+            for j, idx in enumerate(indices[:i]):
+                self.assertEqual(map_mask(c_hash, j*5), idx)
+            for j, idx in enumerate(indices[i:], i):
+                self.assertNotEqual(map_mask(c_hash, j*5), idx)
+
+        c = collisions[-1]
+        self.assertNotEqual(c, None)
+        c_hash = map_hash(c)
+        self.assertEqual(c_hash, none_hash)
+        for i, idx in enumerate(indices):
+            self.assertEqual(map_mask(c_hash, i*5), idx)
+
+    def test_none_as_key(self):
+        m = self.Map({None: 1})
+
+        self.assertEqual(len(m), 1)
+        self.assertTrue(None in m)
+        self.assertEqual(m[None], 1)
+        self.assertTrue(repr(m).startswith('<immutables.Map({None: 1}) at 0x'))
+
+        for level in range(7):
+            key = NoneCollision('a', level)
+            self.assertFalse(key in m)
+            with self.assertRaises(KeyError):
+                m.delete(key)
+
+        m = m.delete(None)
+        self.assertEqual(len(m), 0)
+        self.assertFalse(None in m)
+        self.assertTrue(repr(m).startswith('<immutables.Map({}) at 0x'))
+
+        self.assertEqual(m, self.Map())
+
+        with self.assertRaises(KeyError):
+            m.delete(None)
+
+    def test_none_set(self):
+        m = self.Map().set(None, 2)
+
+        self.assertEqual(len(m), 1)
+        self.assertTrue(None in m)
+        self.assertEqual(m[None], 2)
+
+        m = m.set(None, 1)
+
+        self.assertEqual(len(m), 1)
+        self.assertTrue(None in m)
+        self.assertEqual(m[None], 1)
+
+        m = m.delete(None)
+
+        self.assertEqual(len(m), 0)
+        self.assertEqual(m, self.Map())
+        self.assertFalse(None in m)
+
+        with self.assertRaises(KeyError):
+            m.delete(None)
+
+    def test_none_collision_1(self):
+        for level in range(7):
+            key = NoneCollision('a', level)
+            m = self.Map({None: 1, key: 2})
+
+            self.assertEqual(len(m), 2)
+            self.assertTrue(None in m)
+            self.assertEqual(m[None], 1)
+            self.assertTrue(key in m)
+            self.assertEqual(m[key], 2)
+
+            m2 = m.delete(None)
+            self.assertEqual(len(m2), 1)
+            self.assertTrue(key in m2)
+            self.assertEqual(m2[key], 2)
+            self.assertFalse(None in m2)
+            with self.assertRaises(KeyError):
+                m2.delete(None)
+
+            m3 = m2.delete(key)
+            self.assertEqual(len(m3), 0)
+            self.assertFalse(None in m3)
+            self.assertFalse(key in m3)
+            self.assertEqual(m3, self.Map())
+            self.assertTrue(repr(m3).startswith('<immutables.Map({}) at 0x'))
+            with self.assertRaises(KeyError):
+                m3.delete(None)
+            with self.assertRaises(KeyError):
+                m3.delete(key)
+
+            m2 = m.delete(key)
+            self.assertEqual(len(m2), 1)
+            self.assertTrue(None in m2)
+            self.assertEqual(m2[None], 1)
+            self.assertFalse(key in m2)
+            with self.assertRaises(KeyError):
+                m2.delete(key)
+
+            m4 = m2.delete(None)
+            self.assertEqual(len(m4), 0)
+            self.assertFalse(None in m4)
+            self.assertFalse(key in m4)
+            self.assertEqual(m4, self.Map())
+            self.assertTrue(repr(m4).startswith('<immutables.Map({}) at 0x'))
+            with self.assertRaises(KeyError):
+                m4.delete(None)
+            with self.assertRaises(KeyError):
+                m4.delete(key)
+
+            self.assertEqual(m3, m4)
+
+    def test_none_collision_2(self):
+        key = HashKey(not_collision, 'a')
+        m = self.Map().set(None, 1).set(key, 2)
+
+        self.assertEqual(len(m), 2)
+        self.assertTrue(key in m)
+        self.assertTrue(None in m)
+        self.assertEqual(m[key], 2)
+        self.assertEqual
+
+        m = m.set(None, 0)
+        self.assertEqual(len(m), 2)
+        self.assertTrue(key in m)
+        self.assertTrue(None in m)
+
+        for level in range(7):
+            key2 = NoneCollision('b', level)
+            self.assertFalse(key2 in m)
+            m2 = m.set(key2, 1)
+
+            self.assertEqual(len(m2), 3)
+            self.assertTrue(key in m2)
+            self.assertTrue(None in m2)
+            self.assertTrue(key2 in m2)
+            self.assertEqual(m2[key], 2)
+            self.assertEqual(m2[None], 0)
+            self.assertEqual(m2[key2], 1)
+
+            m2 = m2.set(None, 1)
+            self.assertEqual(len(m2), 3)
+            self.assertTrue(key in m2)
+            self.assertTrue(None in m2)
+            self.assertTrue(key2 in m2)
+            self.assertEqual(m2[key], 2)
+            self.assertEqual(m2[None], 1)
+            self.assertEqual(m2[key2], 1)
+
+            m2 = m2.set(None, 2)
+            self.assertEqual(len(m2), 3)
+            self.assertTrue(key in m2)
+            self.assertTrue(None in m2)
+            self.assertTrue(key2 in m2)
+            self.assertEqual(m2[key], 2)
+            self.assertEqual(m2[None], 2)
+            self.assertEqual(m2[key2], 1)
+
+            m3 = m2.delete(key)
+            self.assertEqual(len(m3), 2)
+            self.assertTrue(None in m3)
+            self.assertTrue(key2 in m3)
+            self.assertFalse(key in m3)
+            self.assertEqual(m3[None], 2)
+            self.assertEqual(m3[key2], 1)
+            with self.assertRaises(KeyError):
+                m3.delete(key)
+
+            m3 = m2.delete(key2)
+            self.assertEqual(len(m3), 2)
+            self.assertTrue(None in m3)
+            self.assertTrue(key in m3)
+            self.assertFalse(key2 in m3)
+            self.assertEqual(m3[None], 2)
+            self.assertEqual(m3[key], 2)
+            with self.assertRaises(KeyError):
+                m3.delete(key2)
+
+            m3 = m2.delete(None)
+            self.assertEqual(len(m3), 2)
+            self.assertTrue(key in m3)
+            self.assertTrue(key2 in m3)
+            self.assertFalse(None in m3)
+            self.assertEqual(m3[key], 2)
+            self.assertEqual(m3[key2], 1)
+            with self.assertRaises(KeyError):
+                m3.delete(None)
+
+        m2 = m.delete(None)
+        self.assertEqual(len(m2), 1)
+        self.assertFalse(None in m2)
+        self.assertTrue(key in m2)
+        self.assertEqual(m2[key], 2)
+        with self.assertRaises(KeyError):
+            m2.delete(None)
+
+        m2 = m.delete(key)
+        self.assertEqual(len(m2), 1)
+        self.assertFalse(key in m2)
+        self.assertTrue(None in m2)
+        self.assertEqual(m2[None], 0)
+        with self.assertRaises(KeyError):
+            m2.delete(key)
+
+    def test_none_collision_3(self):
+        for level in range(7):
+            key = NoneCollision('a', level)
+            m = self.Map({key: 2})
+
+            self.assertEqual(len(m), 1)
+            self.assertFalse(None in m)
+            self.assertTrue(key in m)
+            self.assertEqual(m[key], 2)
+            with self.assertRaises(KeyError):
+                m.delete(None)
+
+            m = m.set(None, 1)
+            self.assertEqual(len(m), 2)
+            self.assertTrue(key in m)
+            self.assertEqual(m[key], 2)
+            self.assertTrue(None in m)
+            self.assertEqual(m[None], 1)
+
+            m = m.set(None, 0)
+            self.assertEqual(len(m), 2)
+            self.assertTrue(key in m)
+            self.assertEqual(m[key], 2)
+            self.assertTrue(None in m)
+            self.assertEqual(m[None], 0)
+
+            m2 = m.delete(key)
+            self.assertEqual(len(m2), 1)
+            self.assertTrue(None in m2)
+            self.assertEqual(m2[None], 0)
+            self.assertFalse(key in m2)
+            with self.assertRaises(KeyError):
+                m2.delete(key)
+
+            m2 = m.delete(None)
+            self.assertEqual(len(m2), 1)
+            self.assertTrue(key in m2)
+            self.assertEqual(m2[key], 2)
+            self.assertFalse(None in m2)
+            with self.assertRaises(KeyError):
+                m2.delete(None)
+
+    def test_collision_4(self):
+        key2 = NoneCollision('a', 2)
+        key4 = NoneCollision('b', 4)
+        m = self.Map({key2: 2, key4: 4})
+
+        self.assertEqual(len(m), 2)
+        self.assertTrue(key2 in m)
+        self.assertTrue(key4 in m)
+        self.assertEqual(m[key2], 2)
+        self.assertEqual(m[key4], 4)
+        self.assertFalse(None in m)
+
+        m2 = m.set(None, 9)
+
+        self.assertEqual(len(m2), 3)
+        self.assertTrue(key2 in m2)
+        self.assertTrue(key4 in m2)
+        self.assertTrue(None in m2)
+        self.assertEqual(m2[key2], 2)
+        self.assertEqual(m2[key4], 4)
+        self.assertEqual(m2[None], 9)
+
+        m3 = m2.set(None, 0)
+        self.assertEqual(len(m3), 3)
+        self.assertTrue(key2 in m3)
+        self.assertTrue(key4 in m3)
+        self.assertTrue(None in m3)
+        self.assertEqual(m3[key2], 2)
+        self.assertEqual(m3[key4], 4)
+        self.assertEqual(m3[None], 0)
+
+        m3 = m2.set(key2, 0)
+        self.assertEqual(len(m3), 3)
+        self.assertTrue(key2 in m3)
+        self.assertTrue(key4 in m3)
+        self.assertTrue(None in m3)
+        self.assertEqual(m3[key2], 0)
+        self.assertEqual(m3[key4], 4)
+        self.assertEqual(m3[None], 9)
+
+        m3 = m2.set(key4, 0)
+        self.assertEqual(len(m3), 3)
+        self.assertTrue(key2 in m3)
+        self.assertTrue(key4 in m3)
+        self.assertTrue(None in m3)
+        self.assertEqual(m3[key2], 2)
+        self.assertEqual(m3[key4], 0)
+        self.assertEqual(m3[None], 9)
+
+        m3 = m2.delete(None)
+        self.assertEqual(m3, m)
+        self.assertEqual(len(m3), 2)
+        self.assertTrue(key2 in m3)
+        self.assertTrue(key4 in m3)
+        self.assertEqual(m3[key2], 2)
+        self.assertEqual(m3[key4], 4)
+        self.assertFalse(None in  m3)
+        with self.assertRaises(KeyError):
+            m3.delete(None)
+
+        m3 = m2.delete(key2)
+        self.assertEqual(len(m3), 2)
+        self.assertTrue(None in m3)
+        self.assertTrue(key4 in m3)
+        self.assertEqual(m3[None], 9)
+        self.assertEqual(m3[key4], 4)
+        self.assertFalse(key2 in  m3)
+        with self.assertRaises(KeyError):
+            m3.delete(key2)
+
+        m3 = m2.delete(key4)
+        self.assertEqual(len(m3), 2)
+        self.assertTrue(None in m3)
+        self.assertTrue(key2 in m3)
+        self.assertEqual(m3[None], 9)
+        self.assertEqual(m3[key2], 2)
+        self.assertFalse(key4 in  m3)
+        with self.assertRaises(KeyError):
+            m3.delete(key4)
+
+    def test_none_mutation(self):
+        key2 = NoneCollision('a', 2)
+        key4 = NoneCollision('b', 4)
+        key = NoneCollision('c', -1)
+        m = self.Map({key: -1, key2: 2, key4: 4, None: 9})
+
+        with m.mutate() as mm:
+            self.assertEqual(len(mm), 4)
+            self.assertTrue(key in mm)
+            self.assertTrue(key2 in mm)
+            self.assertTrue(key4 in mm)
+            self.assertTrue(None in mm)
+            self.assertEqual(mm[key2], 2)
+            self.assertEqual(mm[key4], 4)
+            self.assertEqual(mm[key], -1)
+            self.assertEqual(mm[None], 9)
+
+            for k in m:
+                mm[k] = -mm[k]
+
+            self.assertEqual(len(mm), 4)
+            self.assertTrue(key in mm)
+            self.assertTrue(key2 in mm)
+            self.assertTrue(key4 in mm)
+            self.assertTrue(None in mm)
+            self.assertEqual(mm[key2], -2)
+            self.assertEqual(mm[key4], -4)
+            self.assertEqual(mm[key], 1)
+            self.assertEqual(mm[None], -9)
+
+            for k in m:
+                del mm[k]
+                self.assertEqual(len(mm), 3)
+                self.assertFalse(k in mm)
+                for n in m:
+                    if n != k:
+                        self.assertTrue(n in mm)
+                        self.assertEqual(mm[n], -m[n])
+                with self.assertRaises(KeyError):
+                    del mm[k]
+                mm[k] = -m[k]
+                self.assertEqual(len(mm), 4)
+                self.assertTrue(k in mm)
+                self.assertEqual(mm[k], -m[k])
+
+            for k in m:
+                mm[k] = -mm[k]
+
+            self.assertEqual(len(mm), 4)
+            self.assertTrue(key in mm)
+            self.assertTrue(key2 in mm)
+            self.assertTrue(key4 in mm)
+            self.assertTrue(None in mm)
+            self.assertEqual(mm[key2], 2)
+            self.assertEqual(mm[key4], 4)
+            self.assertEqual(mm[key], -1)
+            self.assertEqual(mm[None], 9)
+
+            for k in m:
+                mm[k] = -mm[k]
+
+            self.assertEqual(len(mm), 4)
+            self.assertTrue(key in mm)
+            self.assertTrue(key2 in mm)
+            self.assertTrue(key4 in mm)
+            self.assertTrue(None in mm)
+            self.assertEqual(mm[key2], -2)
+            self.assertEqual(mm[key4], -4)
+            self.assertEqual(mm[key], 1)
+            self.assertEqual(mm[None], -9)
+
+            m2 = mm.finish()
+
+        self.assertEqual(set(m), set(m2))
+        self.assertEqual(len(m2), 4)
+        self.assertTrue(key in m2)
+        self.assertTrue(key2 in m2)
+        self.assertTrue(key4 in m2)
+        self.assertTrue(None in m2)
+        self.assertEqual(m2[key2], -2)
+        self.assertEqual(m2[key4], -4)
+        self.assertEqual(m2[key], 1)
+        self.assertEqual(m2[None], -9)
+
+        for k, v in m.items():
+            self.assertTrue(k in m2)
+            self.assertEqual(m2[k], -v)
+
+    def test_iterators(self):
+        key2 = NoneCollision('a', 2)
+        key4 = NoneCollision('b', 4)
+        key = NoneCollision('c', -1)
+        m = self.Map({key: -1, key2: 2, key4: 4, None: 9})
+
+        self.assertEqual(len(m), 4)
+        self.assertTrue(key in m)
+        self.assertTrue(key2 in m)
+        self.assertTrue(key4 in m)
+        self.assertTrue(None in m)
+        self.assertEqual(m[key2], 2)
+        self.assertEqual(m[key4], 4)
+        self.assertEqual(m[key], -1)
+        self.assertEqual(m[None], 9)
+
+        s = set(m)
+        self.assertEqual(len(s), 4)
+        self.assertEqual(s, set([None, key, key2, key4]))
+
+        sk = set(m.keys())
+        self.assertEqual(s, sk)
+
+        sv = set(m.values())
+        self.assertEqual(len(sv), 4)
+        self.assertEqual(sv, set([-1, 2, 4, 9]))
+
+        si = set(m.items())
+        self.assertEqual(len(si), 4)
+        self.assertEqual(si,
+                         set([(key, -1), (key2, 2), (key4, 4), (None, 9)]))
+
+        d = {key: -1, key2: 2, key4: 4, None: 9}
+        self.assertEqual(dict(m.items()), d)
+
+
+class PyMapNoneTest(BaseNoneTest, unittest.TestCase):
+
+    Map = PyMap
+
+
+try:
+    from immutables._map import Map as CMap
+except ImportError:
+    CMap = None
+
+
+@unittest.skipIf(CMap is None, 'C Map is not available')
+class CMapNoneTest(BaseNoneTest, unittest.TestCase):
+
+    Map = CMap
+
+
+if __name__ == "__main__":
+    unittest.main()