Author: Carl Friedrich Bolz-Tereick <cfb...@gmx.de> Branch: py3.7 Changeset: r98359:4f0d7c92cfdd Date: 2019-12-23 16:14 +0100 http://bitbucket.org/pypy/pypy/changeset/4f0d7c92cfdd/
Log: pure python HAMT immutable dict implementation from the immutables package taken from rev 11863b29e3fbcd7d25335befce706e21a785f5e0 from https://github.com/MagicStack/immutables/ discussed on Twitter here: https://twitter.com/1st1/status/1208819455507218437 tests converted to pytest using unittest2pytest diff too long, truncating to 2000 out of 2125 lines diff --git a/extra_tests/test_immutables_map.py b/extra_tests/test_immutables_map.py new file mode 100644 --- /dev/null +++ b/extra_tests/test_immutables_map.py @@ -0,0 +1,1298 @@ +import collections.abc +import gc +import pickle +import random +import sys +import weakref +import pytest + +from _immutables_map import Map + + +class HashKey: + _crasher = None + + def __init__(self, hash, name, *, error_on_eq_to=None): + assert hash != -1 + self.name = name + self.hash = hash + self.error_on_eq_to = error_on_eq_to + + def __repr__(self): + if self._crasher is not None and self._crasher.error_on_repr: + raise ReprError + return '<Key name:{} hash:{}>'.format(self.name, self.hash) + + def __hash__(self): + if self._crasher is not None and self._crasher.error_on_hash: + raise HashingError + + return self.hash + + def __eq__(self, other): + if not isinstance(other, HashKey): + return NotImplemented + + if self._crasher is not None and self._crasher.error_on_eq: + raise EqError + + if self.error_on_eq_to is not None and self.error_on_eq_to is other: + raise ValueError('cannot compare {!r} to {!r}'.format(self, other)) + if other.error_on_eq_to is not None and other.error_on_eq_to is self: + raise ValueError('cannot compare {!r} to {!r}'.format(other, self)) + + return (self.name, self.hash) == (other.name, other.hash) + + +class KeyStr(str): + + def __hash__(self): + if HashKey._crasher is not None and HashKey._crasher.error_on_hash: + raise HashingError + return super().__hash__() + + def __eq__(self, other): + if HashKey._crasher is not None and HashKey._crasher.error_on_eq: + raise EqError + return super().__eq__(other) + + def __repr__(self, other): + if HashKey._crasher is not None and HashKey._crasher.error_on_repr: + raise ReprError + return super().__eq__(other) + + +class HashKeyCrasher: + + def __init__(self, *, error_on_hash=False, error_on_eq=False, + error_on_repr=False): + self.error_on_hash = error_on_hash + self.error_on_eq = error_on_eq + self.error_on_repr = error_on_repr + + def __enter__(self): + if HashKey._crasher is not None: + raise RuntimeError('cannot nest crashers') + HashKey._crasher = self + + def __exit__(self, *exc): + HashKey._crasher = None + + +class HashingError(Exception): + pass + + +class EqError(Exception): + pass + + +class ReprError(Exception): + pass + + +class BaseMapTest: + + def test_hashkey_helper_1(self): + k1 = HashKey(10, 'aaa') + k2 = HashKey(10, 'bbb') + + assert k1 != k2 + assert hash(k1) == hash(k2) + + d = dict() + d[k1] = 'a' + d[k2] = 'b' + + assert d[k1] == 'a' + assert d[k2] == 'b' + + def test_map_basics_1(self): + h = self.Map() + h = None # NoQA + + def test_map_basics_2(self): + h = self.Map() + assert len(h) == 0 + + h2 = h.set('a', 'b') + assert h is not h2 + assert len(h) == 0 + assert len(h2) == 1 + + assert h.get('a') is None + assert h.get('a', 42) == 42 + + assert h2.get('a') == 'b' + + h3 = h2.set('b', 10) + assert h2 is not h3 + assert len(h) == 0 + assert len(h2) == 1 + assert len(h3) == 2 + assert h3.get('a') == 'b' + assert h3.get('b') == 10 + + assert h.get('b') is None + assert h2.get('b') is None + + assert h.get('a') is None + assert h2.get('a') == 'b' + + h = h2 = h3 = None + + def test_map_basics_3(self): + h = self.Map() + o = object() + h1 = h.set('1', o) + h2 = h1.set('1', o) + assert h1 is h2 + + def test_map_basics_4(self): + h = self.Map() + h1 = h.set('key', []) + h2 = h1.set('key', []) + assert h1 is not h2 + assert len(h1) == 1 + assert len(h2) == 1 + assert h1.get('key') is not h2.get('key') + + def test_map_collision_1(self): + k1 = HashKey(10, 'aaa') + k2 = HashKey(10, 'bbb') + k3 = HashKey(10, 'ccc') + + h = self.Map() + h2 = h.set(k1, 'a') + h3 = h2.set(k2, 'b') + + assert h.get(k1) == None + assert h.get(k2) == None + + assert h2.get(k1) == 'a' + assert h2.get(k2) == None + + assert h3.get(k1) == 'a' + assert h3.get(k2) == 'b' + + h4 = h3.set(k2, 'cc') + h5 = h4.set(k3, 'aa') + + assert h3.get(k1) == 'a' + assert h3.get(k2) == 'b' + assert h4.get(k1) == 'a' + assert h4.get(k2) == 'cc' + assert h4.get(k3) == None + assert h5.get(k1) == 'a' + assert h5.get(k2) == 'cc' + assert h5.get(k2) == 'cc' + assert h5.get(k3) == 'aa' + + assert len(h) == 0 + assert len(h2) == 1 + assert len(h3) == 2 + assert len(h4) == 2 + assert len(h5) == 3 + + def test_map_collision_2(self): + A = HashKey(100, 'A') + B = HashKey(101, 'B') + C = HashKey(0b011000011100000100, 'C') + D = HashKey(0b011000011100000100, 'D') + E = HashKey(0b1011000011100000100, 'E') + + h = self.Map() + h = h.set(A, 'a') + h = h.set(B, 'b') + h = h.set(C, 'c') + h = h.set(D, 'd') + + # BitmapNode(size=6 bitmap=0b100110000): + # NULL: + # BitmapNode(size=4 bitmap=0b1000000000000000000001000): + # <Key name:A hash:100>: 'a' + # NULL: + # CollisionNode(size=4 id=0x108572410): + # <Key name:C hash:100100>: 'c' + # <Key name:D hash:100100>: 'd' + # <Key name:B hash:101>: 'b' + + h = h.set(E, 'e') + + # BitmapNode(size=4 count=2.0 bitmap=0b110000 id=10b8ea5c0): + # None: + # BitmapNode(size=4 count=2.0 + # bitmap=0b1000000000000000000001000 id=10b8ea518): + # <Key name:A hash:100>: 'a' + # None: + # BitmapNode(size=2 count=1.0 bitmap=0b10 + # id=10b8ea4a8): + # None: + # BitmapNode(size=4 count=2.0 + # bitmap=0b100000001000 + # id=10b8ea4e0): + # None: + # CollisionNode(size=4 id=10b8ea470): + # <Key name:C hash:100100>: 'c' + # <Key name:D hash:100100>: 'd' + # <Key name:E hash:362244>: 'e' + # <Key name:B hash:101>: 'b' + + def test_map_stress(self): + COLLECTION_SIZE = 7000 + TEST_ITERS_EVERY = 647 + CRASH_HASH_EVERY = 97 + CRASH_EQ_EVERY = 11 + RUN_XTIMES = 3 + + for _ in range(RUN_XTIMES): + h = self.Map() + d = dict() + + for i in range(COLLECTION_SIZE): + key = KeyStr(i) + + if not (i % CRASH_HASH_EVERY): + with HashKeyCrasher(error_on_hash=True): + with pytest.raises(HashingError): + h.set(key, i) + + h = h.set(key, i) + + if not (i % CRASH_EQ_EVERY): + with HashKeyCrasher(error_on_eq=True): + with pytest.raises(EqError): + h.get(KeyStr(i)) # really trigger __eq__ + + d[key] = i + assert len(d) == len(h) + + if not (i % TEST_ITERS_EVERY): + assert set(h.items()) == set(d.items()) + assert len(h.items()) == len(d.items()) + + assert len(h) == COLLECTION_SIZE + + for key in range(COLLECTION_SIZE): + assert h.get(KeyStr(key), 'not found') == key + + keys_to_delete = list(range(COLLECTION_SIZE)) + random.shuffle(keys_to_delete) + for iter_i, i in enumerate(keys_to_delete): + key = KeyStr(i) + + if not (iter_i % CRASH_HASH_EVERY): + with HashKeyCrasher(error_on_hash=True): + with pytest.raises(HashingError): + h.delete(key) + + if not (iter_i % CRASH_EQ_EVERY): + with HashKeyCrasher(error_on_eq=True): + with pytest.raises(EqError): + h.delete(KeyStr(i)) + + h = h.delete(key) + assert h.get(key, 'not found') == 'not found' + del d[key] + assert len(d) == len(h) + + if iter_i == COLLECTION_SIZE // 2: + hm = h + dm = d.copy() + + if not (iter_i % TEST_ITERS_EVERY): + assert set(h.keys()) == set(d.keys()) + assert len(h.keys()) == len(d.keys()) + + assert len(d) == 0 + assert len(h) == 0 + + # ============ + + for key in dm: + assert hm.get(str(key)) == dm[key] + assert len(dm) == len(hm) + + for i, key in enumerate(keys_to_delete): + if str(key) in dm: + hm = hm.delete(str(key)) + dm.pop(str(key)) + assert hm.get(str(key), 'not found') == 'not found' + assert len(d) == len(h) + + if not (i % TEST_ITERS_EVERY): + assert set(h.values()) == set(d.values()) + assert len(h.values()) == len(d.values()) + + assert len(d) == 0 + assert len(h) == 0 + assert list(h.items()) == [] + + def test_map_delete_1(self): + A = HashKey(100, 'A') + B = HashKey(101, 'B') + C = HashKey(102, 'C') + D = HashKey(103, 'D') + E = HashKey(104, 'E') + Z = HashKey(-100, 'Z') + + Er = HashKey(103, 'Er', error_on_eq_to=D) + + h = self.Map() + h = h.set(A, 'a') + h = h.set(A, 'a') + h = h.set(B, 'b') + h = h.set(C, 'c') + h = h.set(D, 'd') + h = h.set(E, 'e') + + orig_len = len(h) + + # BitmapNode(size=10 bitmap=0b111110000 id=0x10eadc618): + # <Key name:A hash:100>: 'a' + # <Key name:B hash:101>: 'b' + # <Key name:C hash:102>: 'c' + # <Key name:D hash:103>: 'd' + # <Key name:E hash:104>: 'e' + + h = h.delete(C) + assert len(h) == orig_len - 1 + + with pytest.raises(ValueError, match='cannot compare'): + h.delete(Er) + + h = h.delete(D) + assert len(h) == orig_len - 2 + + with pytest.raises(KeyError) as ex: + h.delete(Z) + assert ex.value.args[0] is Z + + h = h.delete(A) + assert len(h) == orig_len - 3 + + assert h.get(A, 42) == 42 + assert h.get(B) == 'b' + assert h.get(E) == 'e' + + def test_map_delete_2(self): + A = HashKey(100, 'A') + B = HashKey(201001, 'B') + C = HashKey(101001, 'C') + BLike = HashKey(201001, 'B-like') + D = HashKey(103, 'D') + E = HashKey(104, 'E') + Z = HashKey(-100, 'Z') + + Er = HashKey(201001, 'Er', error_on_eq_to=B) + + h = self.Map() + h = h.set(A, 'a') + h = h.set(B, 'b') + h = h.set(C, 'c') + h = h.set(D, 'd') + h = h.set(E, 'e') + + h = h.set(B, 'b') # trigger branch in BitmapNode.assoc + + with pytest.raises(KeyError): + h.delete(BLike) # trigger branch in BitmapNode.without + + orig_len = len(h) + + # BitmapNode(size=8 bitmap=0b1110010000): + # <Key name:A hash:100>: 'a' + # <Key name:D hash:103>: 'd' + # <Key name:E hash:104>: 'e' + # NULL: + # BitmapNode(size=4 bitmap=0b100000000001000000000): + # <Key name:B hash:201001>: 'b' + # <Key name:C hash:101001>: 'c' + + with pytest.raises(ValueError, match='cannot compare'): + h.delete(Er) + + with pytest.raises(KeyError) as ex: + h.delete(Z) + assert ex.value.args[0] is Z + assert len(h) == orig_len + + h = h.delete(C) + assert len(h) == orig_len - 1 + + h = h.delete(B) + assert len(h) == orig_len - 2 + + h = h.delete(A) + assert len(h) == orig_len - 3 + + assert h.get(D) == 'd' + assert h.get(E) == 'e' + + with pytest.raises(KeyError): + h = h.delete(A) + with pytest.raises(KeyError): + h = h.delete(B) + h = h.delete(D) + h = h.delete(E) + assert len(h) == 0 + + def test_map_delete_3(self): + A = HashKey(0b00000000001100100, 'A') + B = HashKey(0b00000000001100101, 'B') + + C = HashKey(0b11000011100000100, 'C') + D = HashKey(0b11000011100000100, 'D') + X = HashKey(0b01000011100000100, 'Z') + Y = HashKey(0b11000011100000100, 'Y') + + E = HashKey(0b00000000001101000, 'E') + + h = self.Map() + h = h.set(A, 'a') + h = h.set(B, 'b') + h = h.set(C, 'c') + h = h.set(D, 'd') + h = h.set(E, 'e') + + assert len(h) == 5 + h = h.set(C, 'c') # trigger branch in CollisionNode.assoc + assert len(h) == 5 + + orig_len = len(h) + + with pytest.raises(KeyError): + h.delete(X) + with pytest.raises(KeyError): + h.delete(Y) + + # BitmapNode(size=6 bitmap=0b100110000): + # NULL: + # BitmapNode(size=4 bitmap=0b1000000000000000000001000): + # <Key name:A hash:100>: 'a' + # NULL: + # CollisionNode(size=4 id=0x108572410): + # <Key name:C hash:100100>: 'c' + # <Key name:D hash:100100>: 'd' + # <Key name:B hash:101>: 'b' + # <Key name:E hash:104>: 'e' + + h = h.delete(A) + assert len(h) == orig_len - 1 + + h = h.delete(E) + assert len(h) == orig_len - 2 + + assert h.get(C) == 'c' + assert h.get(B) == 'b' + + h2 = h.delete(C) + assert len(h2) == orig_len - 3 + + h2 = h.delete(D) + assert len(h2) == orig_len - 3 + + assert len(h) == orig_len - 2 + + def test_map_delete_4(self): + A = HashKey(100, 'A') + B = HashKey(101, 'B') + C = HashKey(100100, 'C') + D = HashKey(100100, 'D') + E = HashKey(100100, 'E') + + h = self.Map() + h = h.set(A, 'a') + h = h.set(B, 'b') + h = h.set(C, 'c') + h = h.set(D, 'd') + h = h.set(E, 'e') + + orig_len = len(h) + + # BitmapNode(size=4 bitmap=0b110000): + # NULL: + # BitmapNode(size=4 bitmap=0b1000000000000000000001000): + # <Key name:A hash:100>: 'a' + # NULL: + # CollisionNode(size=6 id=0x10515ef30): + # <Key name:C hash:100100>: 'c' + # <Key name:D hash:100100>: 'd' + # <Key name:E hash:100100>: 'e' + # <Key name:B hash:101>: 'b' + + h = h.delete(D) + assert len(h) == orig_len - 1 + + h = h.delete(E) + assert len(h) == orig_len - 2 + + h = h.delete(C) + assert len(h) == orig_len - 3 + + h = h.delete(A) + assert len(h) == orig_len - 4 + + h = h.delete(B) + assert len(h) == 0 + + def test_map_delete_5(self): + h = self.Map() + + keys = [] + for i in range(17): + key = HashKey(i, str(i)) + keys.append(key) + h = h.set(key, 'val-{}'.format(i)) + + collision_key16 = HashKey(16, '18') + h = h.set(collision_key16, 'collision') + + # ArrayNode(id=0x10f8b9318): + # 0:: + # BitmapNode(size=2 count=1 bitmap=0b1): + # <Key name:0 hash:0>: 'val-0' + # + # ... 14 more BitmapNodes ... + # + # 15:: + # BitmapNode(size=2 count=1 bitmap=0b1): + # <Key name:15 hash:15>: 'val-15' + # + # 16:: + # BitmapNode(size=2 count=1 bitmap=0b1): + # NULL: + # CollisionNode(size=4 id=0x10f2f5af8): + # <Key name:16 hash:16>: 'val-16' + # <Key name:18 hash:16>: 'collision' + + assert len(h) == 18 + + h = h.delete(keys[2]) + assert len(h) == 17 + + h = h.delete(collision_key16) + assert len(h) == 16 + h = h.delete(keys[16]) + assert len(h) == 15 + + h = h.delete(keys[1]) + assert len(h) == 14 + with pytest.raises(KeyError) as ex: + h.delete(keys[1]) + assert ex.value.args[0] is keys[1] + assert len(h) == 14 + + for key in keys: + if key in h: + h = h.delete(key) + assert len(h) == 0 + + def test_map_delete_6(self): + h = self.Map() + h = h.set(1, 1) + h = h.delete(1) + assert len(h) == 0 + assert h == self.Map() + + def test_map_items_1(self): + A = HashKey(100, 'A') + B = HashKey(201001, 'B') + C = HashKey(101001, 'C') + D = HashKey(103, 'D') + E = HashKey(104, 'E') + F = HashKey(110, 'F') + + h = self.Map() + h = h.set(A, 'a') + h = h.set(B, 'b') + h = h.set(C, 'c') + h = h.set(D, 'd') + h = h.set(E, 'e') + h = h.set(F, 'f') + + it = h.items() + assert set(list(it)) == \ + {(A, 'a'), (B, 'b'), (C, 'c'), (D, 'd'), (E, 'e'), (F, 'f')} + + def test_map_items_2(self): + A = HashKey(100, 'A') + B = HashKey(101, 'B') + C = HashKey(100100, 'C') + D = HashKey(100100, 'D') + E = HashKey(100100, 'E') + F = HashKey(110, 'F') + + h = self.Map() + h = h.set(A, 'a') + h = h.set(B, 'b') + h = h.set(C, 'c') + h = h.set(D, 'd') + h = h.set(E, 'e') + h = h.set(F, 'f') + + it = h.items() + assert set(list(it)) == \ + {(A, 'a'), (B, 'b'), (C, 'c'), (D, 'd'), (E, 'e'), (F, 'f')} + + def test_map_items_3(self): + h = self.Map() + assert len(h.items()) == 0 + assert list(h.items()) == [] + + def test_map_items_4(self): + h = self.Map(a=1, b=2, c=3) + k = h.items() + assert set(k) == {('a', 1), ('b', 2), ('c', 3)} + assert set(k) == {('a', 1), ('b', 2), ('c', 3)} + + def test_map_keys_1(self): + A = HashKey(100, 'A') + B = HashKey(101, 'B') + C = HashKey(100100, 'C') + D = HashKey(100100, 'D') + E = HashKey(100100, 'E') + F = HashKey(110, 'F') + + h = self.Map() + h = h.set(A, 'a') + h = h.set(B, 'b') + h = h.set(C, 'c') + h = h.set(D, 'd') + h = h.set(E, 'e') + h = h.set(F, 'f') + + assert set(list(h.keys())) == {A, B, C, D, E, F} + assert set(list(h)) == {A, B, C, D, E, F} + + def test_map_keys_2(self): + h = self.Map(a=1, b=2, c=3) + k = h.keys() + assert set(k) == {'a', 'b', 'c'} + assert set(k) == {'a', 'b', 'c'} + + def test_map_values_1(self): + A = HashKey(100, 'A') + B = HashKey(101, 'B') + C = HashKey(100100, 'C') + D = HashKey(100100, 'D') + E = HashKey(100100, 'E') + F = HashKey(110, 'F') + + h = self.Map() + h = h.set(A, 'a') + h = h.set(B, 'b') + h = h.set(C, 'c') + h = h.set(D, 'd') + h = h.set(E, 'e') + h = h.set(F, 'f') + + assert set(list(h.values())) == {'a', 'b', 'c', 'd', 'e', 'f'} + + def test_map_values_2(self): + h = self.Map(a=1, b=2, c=3) + k = h.values() + assert set(k) == {1, 2, 3} + assert set(k) == {1, 2, 3} + + def test_map_eq_1(self): + A = HashKey(100, 'A') + B = HashKey(101, 'B') + C = HashKey(100100, 'C') + D = HashKey(100100, 'D') + E = HashKey(120, 'E') + + h1 = self.Map() + h1 = h1.set(A, 'a') + h1 = h1.set(B, 'b') + h1 = h1.set(C, 'c') + h1 = h1.set(D, 'd') + + h2 = self.Map() + h2 = h2.set(A, 'a') + + assert not (h1 == h2) + assert h1 != h2 + + h2 = h2.set(B, 'b') + assert not (h1 == h2) + assert h1 != h2 + + h2 = h2.set(C, 'c') + assert not (h1 == h2) + assert h1 != h2 + + h2 = h2.set(D, 'd2') + assert not (h1 == h2) + assert h1 != h2 + + h2 = h2.set(D, 'd') + assert h1 == h2 + assert not (h1 != h2) + + h2 = h2.set(E, 'e') + assert not (h1 == h2) + assert h1 != h2 + + h2 = h2.delete(D) + assert not (h1 == h2) + assert h1 != h2 + + h2 = h2.set(E, 'd') + assert not (h1 == h2) + assert h1 != h2 + + def test_map_eq_2(self): + A = HashKey(100, 'A') + Er = HashKey(100, 'Er', error_on_eq_to=A) + + h1 = self.Map() + h1 = h1.set(A, 'a') + + h2 = self.Map() + h2 = h2.set(Er, 'a') + + with pytest.raises(ValueError, match='cannot compare'): + h1 == h2 + + with pytest.raises(ValueError, match='cannot compare'): + h1 != h2 + + def test_map_eq_3(self): + assert self.Map() != 1 + + def test_map_gc_1(self): + A = HashKey(100, 'A') + + h = self.Map() + h = h.set(0, 0) # empty Map node is memoized in _map.c + ref = weakref.ref(h) + + a = [] + a.append(a) + a.append(h) + b = [] + a.append(b) + b.append(a) + h = h.set(A, b) + + del h, a, b + + gc.collect() + gc.collect() + gc.collect() + + assert ref() is None + + def test_map_gc_2(self): + A = HashKey(100, 'A') + + h = self.Map() + h = h.set(A, 'a') + h = h.set(A, h) + + ref = weakref.ref(h) + hi = iter(h.items()) + next(hi) + + del h, hi + + gc.collect() + gc.collect() + gc.collect() + + assert ref() is None + + def test_map_in_1(self): + A = HashKey(100, 'A') + AA = HashKey(100, 'A') + + B = HashKey(101, 'B') + + h = self.Map() + h = h.set(A, 1) + + assert A in h + assert not (B in h) + + with pytest.raises(EqError): + with HashKeyCrasher(error_on_eq=True): + AA in h + + with pytest.raises(HashingError): + with HashKeyCrasher(error_on_hash=True): + AA in h + + def test_map_getitem_1(self): + A = HashKey(100, 'A') + AA = HashKey(100, 'A') + + B = HashKey(101, 'B') + + h = self.Map() + h = h.set(A, 1) + + assert h[A] == 1 + assert h[AA] == 1 + + with pytest.raises(KeyError): + h[B] + + with pytest.raises(EqError): + with HashKeyCrasher(error_on_eq=True): + h[AA] + + with pytest.raises(HashingError): + with HashKeyCrasher(error_on_hash=True): + h[AA] + + def test_repr_1(self): + h = self.Map() + assert repr(h).startswith('<immutables.Map({}) at 0x') + + h = h.set(1, 2).set(2, 3).set(3, 4) + assert repr(h).startswith( + '<immutables.Map({1: 2, 2: 3, 3: 4}) at 0x') + + def test_repr_2(self): + h = self.Map() + A = HashKey(100, 'A') + + with pytest.raises(ReprError): + with HashKeyCrasher(error_on_repr=True): + repr(h.set(1, 2).set(A, 3).set(3, 4)) + + with pytest.raises(ReprError): + with HashKeyCrasher(error_on_repr=True): + repr(h.set(1, 2).set(2, A).set(3, 4)) + + def test_repr_3(self): + class Key: + def __init__(self): + self.val = None + + def __hash__(self): + return 123 + + def __repr__(self): + return repr(self.val) + + h = self.Map() + k = Key() + h = h.set(k, 1) + k.val = h + + assert repr(h).startswith( + '<immutables.Map({{...}: 1}) at 0x') + + def test_hash_1(self): + h = self.Map() + assert hash(h) != -1 + assert hash(h) == hash(h) + + h = h.set(1, 2).set('a', 'b') + assert hash(h) != -1 + assert hash(h) == hash(h) + + assert hash(h.set(1, 2).set('a', 'b')) == \ + hash(h.set('a', 'b').set(1, 2)) + + def test_hash_2(self): + h = self.Map() + A = HashKey(100, 'A') + + m = h.set(1, 2).set(A, 3).set(3, 4) + with pytest.raises(HashingError): + with HashKeyCrasher(error_on_hash=True): + hash(m) + + m = h.set(1, 2).set(2, A).set(3, 4) + with pytest.raises(HashingError): + with HashKeyCrasher(error_on_hash=True): + hash(m) + + def test_abc_1(self): + assert issubclass(self.Map, collections.abc.Mapping) + + def test_map_mut_1(self): + h = self.Map() + h = h.set('a', 1) + + hm1 = h.mutate() + hm2 = h.mutate() + + assert not isinstance(hm1, self.Map) + + assert hm1 is not hm2 + assert hm1['a'] == 1 + assert hm2['a'] == 1 + + hm1.set('b', 2) + hm1.set('c', 3) + + hm2.set('x', 100) + hm2.set('a', 1000) + + assert hm1['a'] == 1 + assert hm1.get('x', -1) == -1 + + assert hm2['a'] == 1000 + assert 'x' in hm2 + + h1 = hm1.finish() + h2 = hm2.finish() + + assert isinstance(h1, self.Map) + + assert dict(h.items()) == {'a': 1} + assert dict(h1.items()) == {'a': 1, 'b': 2, 'c': 3} + assert dict(h2.items()) == {'a': 1000, 'x': 100} + + def test_map_mut_2(self): + h = self.Map() + h = h.set('a', 1) + + hm1 = h.mutate() + hm1.set('a', 2) + hm1.set('a', 3) + hm1.set('a', 4) + h2 = hm1.finish() + + assert dict(h.items()) == {'a': 1} + assert dict(h2.items()) == {'a': 4} + + def test_map_mut_3(self): + h = self.Map() + h = h.set('a', 1) + hm1 = h.mutate() + + assert repr(hm1).startswith( + "<immutables.MapMutation({'a': 1})") + + with pytest.raises(TypeError, match='unhashable type'): + hash(hm1) + + def test_map_mut_4(self): + h = self.Map() + h = h.set('a', 1) + h = h.set('b', 2) + + hm1 = h.mutate() + hm2 = h.mutate() + + assert hm1 == hm2 + + hm1.set('a', 10) + assert hm1 != hm2 + + hm2.set('a', 10) + assert hm1 == hm2 + + assert hm2.pop('a') == 10 + assert hm1 != hm2 + + def test_map_mut_5(self): + h = self.Map({'a': 1, 'b': 2}, z=100) + assert isinstance(h, self.Map) + assert dict(h.items()) == {'a': 1, 'b': 2, 'z': 100} + + h2 = h.update(z=200, y=-1) + assert dict(h.items()) == {'a': 1, 'b': 2, 'z': 100} + assert dict(h2.items()) == {'a': 1, 'b': 2, 'z': 200, 'y': -1} + + h3 = h2.update([(1, 2), (3, 4)]) + assert dict(h.items()) == {'a': 1, 'b': 2, 'z': 100} + assert dict(h2.items()) == {'a': 1, 'b': 2, 'z': 200, 'y': -1} + assert dict(h3.items()) == \ + {'a': 1, 'b': 2, 'z': 200, 'y': -1, 1: 2, 3: 4} + + h4 = h3.update() + assert h4 is h3 + + h5 = h4.update(self.Map({'zzz': 'yyz'})) + + assert dict(h5.items()) == \ + {'a': 1, 'b': 2, 'z': 200, 'y': -1, 1: 2, 3: 4, + 'zzz': 'yyz'} + + def test_map_mut_6(self): + h = self.Map({'a': 1, 'b': 2}, z=100) + assert dict(h.items()) == {'a': 1, 'b': 2, 'z': 100} + + with pytest.raises(TypeError, match='not iterable'): + h.update(1) + + with pytest.raises(ValueError, match='map update sequence element'): + h.update([(1, 2), (3, 4, 5)]) + + with pytest.raises(TypeError, match='cannot convert map update'): + h.update([(1, 2), 1]) + + assert dict(h.items()) == {'a': 1, 'b': 2, 'z': 100} + + def test_map_mut_7(self): + key = HashKey(123, 'aaa') + + h = self.Map({'a': 1, 'b': 2}, z=100) + assert dict(h.items()) == {'a': 1, 'b': 2, 'z': 100} + + upd = {key: 1} + with HashKeyCrasher(error_on_hash=True): + with pytest.raises(HashingError): + h.update(upd) + + upd = self.Map({key: 'zzz'}) + with HashKeyCrasher(error_on_hash=True): + with pytest.raises(HashingError): + h.update(upd) + + upd = [(1, 2), (key, 'zzz')] + with HashKeyCrasher(error_on_hash=True): + with pytest.raises(HashingError): + h.update(upd) + + assert dict(h.items()) == {'a': 1, 'b': 2, 'z': 100} + + def test_map_mut_8(self): + key1 = HashKey(123, 'aaa') + key2 = HashKey(123, 'bbb') + + h = self.Map({key1: 123}) + assert dict(h.items()) == {key1: 123} + + upd = {key2: 1} + with HashKeyCrasher(error_on_eq=True): + with pytest.raises(EqError): + h.update(upd) + + upd = self.Map({key2: 'zzz'}) + with HashKeyCrasher(error_on_eq=True): + with pytest.raises(EqError): + h.update(upd) + + upd = [(1, 2), (key2, 'zzz')] + with HashKeyCrasher(error_on_eq=True): + with pytest.raises(EqError): + h.update(upd) + + assert dict(h.items()) == {key1: 123} + + def test_map_mut_9(self): + key1 = HashKey(123, 'aaa') + + src = {key1: 123} + with HashKeyCrasher(error_on_hash=True): + with pytest.raises(HashingError): + self.Map(src) + + src = [(1, 2), (key1, 123)] + with HashKeyCrasher(error_on_hash=True): + with pytest.raises(HashingError): + self.Map(src) + + def test_map_mut_10(self): + key1 = HashKey(123, 'aaa') + + m = self.Map({key1: 123}) + + mm = m.mutate() + with HashKeyCrasher(error_on_hash=True): + with pytest.raises(HashingError): + del mm[key1] + + mm = m.mutate() + with HashKeyCrasher(error_on_hash=True): + with pytest.raises(HashingError): + mm.pop(key1, None) + + mm = m.mutate() + with HashKeyCrasher(error_on_hash=True): + with pytest.raises(HashingError): + mm.set(key1, 123) + + def test_map_mut_11(self): + m = self.Map({'a': 1, 'b': 2}) + + mm = m.mutate() + assert mm.pop('a', 1) == 1 + assert mm.finish() == self.Map({'b': 2}) + + mm = m.mutate() + assert mm.pop('b', 1) == 2 + assert mm.finish() == self.Map({'a': 1}) + + mm = m.mutate() + assert mm.pop('b', 1) == 2 + del mm['a'] + assert mm.finish() == self.Map() + + def test_map_mut_12(self): + m = self.Map({'a': 1, 'b': 2}) + + mm = m.mutate() + mm.finish() + + with pytest.raises(ValueError, match='has been finished'): + mm.pop('a') + + with pytest.raises(ValueError, match='has been finished'): + del mm['a'] + + with pytest.raises(ValueError, match='has been finished'): + mm.set('a', 'b') + + with pytest.raises(ValueError, match='has been finished'): + mm['a'] = 'b' + + with pytest.raises(ValueError, match='has been finished'): + mm.update(a='b') + + def test_map_mut_13(self): + key1 = HashKey(123, 'aaa') + key2 = HashKey(123, 'aaa') + + m = self.Map({key1: 123}) + + mm = m.mutate() + with HashKeyCrasher(error_on_eq=True): + with pytest.raises(EqError): + del mm[key2] + + mm = m.mutate() + with HashKeyCrasher(error_on_eq=True): + with pytest.raises(EqError): + mm.pop(key2, None) + + mm = m.mutate() + with HashKeyCrasher(error_on_eq=True): + with pytest.raises(EqError): + mm.set(key2, 123) + + def test_map_mut_14(self): + m = self.Map(a=1, b=2) + + with m.mutate() as mm: + mm['z'] = 100 + del mm['a'] + + assert mm.finish() == self.Map(z=100, b=2) + + def test_map_mut_15(self): + m = self.Map(a=1, b=2) + + with pytest.raises(ZeroDivisionError): + with m.mutate() as mm: + mm['z'] = 100 + del mm['a'] + 1 / 0 + + assert mm.finish() == self.Map(z=100, b=2) + assert m == self.Map(a=1, b=2) + + def test_map_mut_16(self): + m = self.Map(a=1, b=2) + hash(m) + + m2 = self.Map(m) + m3 = self.Map(m, c=3) + + assert m == m2 + assert len(m) == len(m2) + assert hash(m) == hash(m2) + + assert m is not m2 + assert m3 == self.Map(a=1, b=2, c=3) + + def test_map_mut_17(self): + m = self.Map(a=1) + with m.mutate() as mm: + with pytest.raises(TypeError, match='cannot create Maps from MapMutations'): + self.Map(mm) + + def test_map_mut_18(self): + m = self.Map(a=1, b=2) + with m.mutate() as mm: + mm.update(self.Map(x=1), z=2) + mm.update(c=3) + mm.update({'n': 100, 'a': 20}) + m2 = mm.finish() + + expected = self.Map( + {'b': 2, 'c': 3, 'n': 100, 'z': 2, 'x': 1, 'a': 20}) + + assert len(m2) == 6 + assert m2 == expected + assert m == self.Map(a=1, b=2) + + def test_map_mut_19(self): + m = self.Map(a=1, b=2) + m2 = m.update({'a': 20}) + assert len(m2) == 2 + + def test_map_mut_stress(self): + COLLECTION_SIZE = 7000 + TEST_ITERS_EVERY = 647 + RUN_XTIMES = 3 + + for _ in range(RUN_XTIMES): + h = self.Map() + d = dict() + + for i in range(COLLECTION_SIZE // TEST_ITERS_EVERY): + + hm = h.mutate() + for j in range(TEST_ITERS_EVERY): + key = random.randint(1, 100000) + key = HashKey(key % 271, str(key)) + + hm.set(key, key) + d[key] = key + + assert len(hm) == len(d) + + h2 = hm.finish() + assert dict(h2.items()) == d + h = h2 + + assert dict(h.items()) == d + assert len(h) == len(d) + + it = iter(tuple(d.keys())) + for i in range(COLLECTION_SIZE // TEST_ITERS_EVERY): + + hm = h.mutate() + for j in range(TEST_ITERS_EVERY): + try: + key = next(it) + except StopIteration: + break + + del d[key] + del hm[key] + + assert len(hm) == len(d) + + h2 = hm.finish() + assert dict(h2.items()) == d + h = h2 + + assert dict(h.items()) == d + assert len(h) == len(d) + + def test_map_pickle(self): + h = self.Map(a=1, b=2) + for proto in range(pickle.HIGHEST_PROTOCOL): + p = pickle.dumps(h, proto) + uh = pickle.loads(p) + + assert isinstance(uh, self.Map) + assert h == uh + + with pytest.raises(TypeError, match="can('t|not) pickle"): + pickle.dumps(h.mutate()) + + def test_map_is_subscriptable(self): + assert self.Map[int, str] is self.Map + +class TestPyMap(BaseMapTest): + Map = Map diff --git a/lib_pypy/_immutables_map.py b/lib_pypy/_immutables_map.py new file mode 100644 --- /dev/null +++ b/lib_pypy/_immutables_map.py @@ -0,0 +1,817 @@ +import collections.abc +import itertools +import reprlib +import sys + + +__all__ = ('Map',) + + +# Thread-safe counter. +_mut_id = itertools.count(1).__next__ + + +# Python version of _map.c. The topmost comment there explains +# all datastructures and algorithms. +# The code here follows C code closely on purpose to make +# debugging and testing easier. + + +def map_hash(o): + x = hash(o) + return (x & 0xffffffff) ^ ((x >> 32) & 0xffffffff) + + +def map_mask(hash, shift): + return (hash >> shift) & 0x01f + + +def map_bitpos(hash, shift): + return 1 << map_mask(hash, shift) + + +def map_bitcount(v): + v = v - ((v >> 1) & 0x55555555) + v = (v & 0x33333333) + ((v >> 2) & 0x33333333) + v = (v & 0x0F0F0F0F) + ((v >> 4) & 0x0F0F0F0F) + v = v + (v >> 8) + v = (v + (v >> 16)) & 0x3F + return v + + +def map_bitindex(bitmap, bit): + return map_bitcount(bitmap & (bit - 1)) + + +W_EMPTY, W_NEWNODE, W_NOT_FOUND = range(3) +void = object() + + +class BitmapNode: + + def __init__(self, size, bitmap, array, mutid): + self.size = size + self.bitmap = bitmap + assert isinstance(array, list) and len(array) == size + self.array = array + self.mutid = mutid + + def clone(self, mutid): + return BitmapNode(self.size, self.bitmap, self.array.copy(), mutid) + + def assoc(self, shift, hash, key, val, mutid): + bit = map_bitpos(hash, shift) + idx = map_bitindex(self.bitmap, bit) + + if self.bitmap & bit: + key_idx = 2 * idx + val_idx = key_idx + 1 + + key_or_null = self.array[key_idx] + val_or_node = self.array[val_idx] + + if key_or_null is None: + sub_node, added = val_or_node.assoc( + shift + 5, hash, key, val, mutid) + if val_or_node is sub_node: + return self, added + + if mutid and mutid == self.mutid: + self.array[val_idx] = sub_node + return self, added + else: + ret = self.clone(mutid) + ret.array[val_idx] = sub_node + return ret, added + + if key == key_or_null: + if val is val_or_node: + return self, False + + if mutid and mutid == self.mutid: + self.array[val_idx] = val + return self, False + else: + ret = self.clone(mutid) + ret.array[val_idx] = val + return ret, False + + existing_key_hash = map_hash(key_or_null) + if existing_key_hash == hash: + sub_node = CollisionNode( + 4, hash, [key_or_null, val_or_node, key, val], mutid) + else: + sub_node = BitmapNode(0, 0, [], mutid) + sub_node, _ = sub_node.assoc( + shift + 5, existing_key_hash, + key_or_null, val_or_node, + mutid) + sub_node, _ = sub_node.assoc( + shift + 5, hash, key, val, + mutid) + + if mutid and mutid == self.mutid: + self.array[key_idx] = None + self.array[val_idx] = sub_node + return self, True + else: + ret = self.clone(mutid) + ret.array[key_idx] = None + ret.array[val_idx] = sub_node + return ret, True + + else: + key_idx = 2 * idx + val_idx = key_idx + 1 + + n = map_bitcount(self.bitmap) + + new_array = self.array[:key_idx] + new_array.append(key) + new_array.append(val) + new_array.extend(self.array[key_idx:]) + + if mutid and mutid == self.mutid: + self.size = 2 * (n + 1) + self.bitmap |= bit + self.array = new_array + return self, True + else: + return BitmapNode( + 2 * (n + 1), self.bitmap | bit, new_array, mutid), True + + def find(self, shift, hash, key): + bit = map_bitpos(hash, shift) + + if not (self.bitmap & bit): + raise KeyError + + idx = map_bitindex(self.bitmap, bit) + key_idx = idx * 2 + val_idx = key_idx + 1 + + key_or_null = self.array[key_idx] + val_or_node = self.array[val_idx] + + if key_or_null is None: + return val_or_node.find(shift + 5, hash, key) + + if key == key_or_null: + return val_or_node + + raise KeyError(key) + + def without(self, shift, hash, key, mutid): + bit = map_bitpos(hash, shift) + if not (self.bitmap & bit): + return W_NOT_FOUND, None + + idx = map_bitindex(self.bitmap, bit) + key_idx = 2 * idx + val_idx = key_idx + 1 + + key_or_null = self.array[key_idx] + val_or_node = self.array[val_idx] + + if key_or_null is None: + res, sub_node = val_or_node.without(shift + 5, hash, key, mutid) + + if res is W_EMPTY: + raise RuntimeError('unreachable code') # pragma: no cover + + elif res is W_NEWNODE: + if (type(sub_node) is BitmapNode and + sub_node.size == 2 and + sub_node.array[0] is not None): + + if mutid and mutid == self.mutid: + self.array[key_idx] = sub_node.array[0] + self.array[val_idx] = sub_node.array[1] + return W_NEWNODE, self + else: + clone = self.clone(mutid) + clone.array[key_idx] = sub_node.array[0] + clone.array[val_idx] = sub_node.array[1] + return W_NEWNODE, clone + + if mutid and mutid == self.mutid: + self.array[val_idx] = sub_node + return W_NEWNODE, self + else: + clone = self.clone(mutid) + clone.array[val_idx] = sub_node + return W_NEWNODE, clone + + else: + assert sub_node is None + return res, None + + else: + if key == key_or_null: + if self.size == 2: + return W_EMPTY, None + + new_array = self.array[:key_idx] + new_array.extend(self.array[val_idx + 1:]) + + if mutid and mutid == self.mutid: + self.size -= 2 + self.bitmap &= ~bit + self.array = new_array + return W_NEWNODE, self + else: + new_node = BitmapNode( + self.size - 2, self.bitmap & ~bit, new_array, mutid) + return W_NEWNODE, new_node + + else: + return W_NOT_FOUND, None + + def keys(self): + for i in range(0, self.size, 2): + key_or_null = self.array[i] + + if key_or_null is None: + val_or_node = self.array[i + 1] + yield from val_or_node.keys() + else: + yield key_or_null + + def values(self): + for i in range(0, self.size, 2): + key_or_null = self.array[i] + val_or_node = self.array[i + 1] + + if key_or_null is None: + yield from val_or_node.values() + else: + yield val_or_node + + def items(self): + for i in range(0, self.size, 2): + key_or_null = self.array[i] + val_or_node = self.array[i + 1] + + if key_or_null is None: + yield from val_or_node.items() + else: + yield key_or_null, val_or_node + + def dump(self, buf, level): # pragma: no cover + buf.append( + ' ' * (level + 1) + + 'BitmapNode(size={} count={} bitmap={} id={:0x}):'.format( + self.size, self.size / 2, bin(self.bitmap), id(self))) + + for i in range(0, self.size, 2): + key_or_null = self.array[i] + val_or_node = self.array[i + 1] + + pad = ' ' * (level + 2) + + if key_or_null is None: + buf.append(pad + 'None:') + val_or_node.dump(buf, level + 2) + else: + buf.append(pad + '{!r}: {!r}'.format(key_or_null, val_or_node)) + + +class CollisionNode: + + def __init__(self, size, hash, array, mutid): + self.size = size + self.hash = hash + self.array = array + self.mutid = mutid + + def find_index(self, key): + for i in range(0, self.size, 2): + if self.array[i] == key: + return i + return -1 + + def find(self, shift, hash, key): + for i in range(0, self.size, 2): + if self.array[i] == key: + return self.array[i + 1] + raise KeyError(key) + + def assoc(self, shift, hash, key, val, mutid): + if hash == self.hash: + key_idx = self.find_index(key) + + if key_idx == -1: + new_array = self.array.copy() + new_array.append(key) + new_array.append(val) + + if mutid and mutid == self.mutid: + self.size += 2 + self.array = new_array + return self, True + else: + new_node = CollisionNode( + self.size + 2, hash, new_array, mutid) + return new_node, True + + val_idx = key_idx + 1 + if self.array[val_idx] is val: + return self, False + + if mutid and mutid == self.mutid: + self.array[val_idx] = val + return self, False + else: + new_array = self.array.copy() + new_array[val_idx] = val + return CollisionNode(self.size, hash, new_array, mutid), False + + else: + new_node = BitmapNode( + 2, map_bitpos(self.hash, shift), [None, self], mutid) + return new_node.assoc(shift, hash, key, val, mutid) + + def without(self, shift, hash, key, mutid): + if hash != self.hash: + return W_NOT_FOUND, None + + key_idx = self.find_index(key) + if key_idx == -1: + return W_NOT_FOUND, None + + new_size = self.size - 2 + if new_size == 0: + # Shouldn't be ever reachable + return W_EMPTY, None # pragma: no cover + + if new_size == 2: + if key_idx == 0: + new_array = [self.array[2], self.array[3]] + else: + assert key_idx == 2 + new_array = [self.array[0], self.array[1]] + + new_node = BitmapNode( + 2, map_bitpos(hash, shift), new_array, mutid) + return W_NEWNODE, new_node + + new_array = self.array[:key_idx] + new_array.extend(self.array[key_idx + 2:]) + if mutid and mutid == self.mutid: + self.array = new_array + self.size -= 2 + return W_NEWNODE, self + else: + new_node = CollisionNode( + self.size - 2, self.hash, new_array, mutid) + return W_NEWNODE, new_node + + def keys(self): + for i in range(0, self.size, 2): + yield self.array[i] + + def values(self): + for i in range(1, self.size, 2): + yield self.array[i] + + def items(self): + for i in range(0, self.size, 2): + yield self.array[i], self.array[i + 1] + + def dump(self, buf, level): # pragma: no cover + pad = ' ' * (level + 1) + buf.append( + pad + 'CollisionNode(size={} id={:0x}):'.format( + self.size, id(self))) + + pad = ' ' * (level + 2) + for i in range(0, self.size, 2): + key = self.array[i] + val = self.array[i + 1] + + buf.append('{}{!r}: {!r}'.format(pad, key, val)) + + +class MapKeys: + + def __init__(self, c, m): + self.__count = c + self.__root = m + + def __len__(self): + return self.__count + + def __iter__(self): + return iter(self.__root.keys()) + + +class MapValues: + + def __init__(self, c, m): + self.__count = c + self.__root = m + + def __len__(self): + return self.__count + + def __iter__(self): + return iter(self.__root.values()) + + +class MapItems: + + def __init__(self, c, m): + self.__count = c + self.__root = m + + def __len__(self): + return self.__count + + def __iter__(self): + return iter(self.__root.items()) + + +class Map: + + def __init__(self, col=None, **kw): + self.__count = 0 + self.__root = BitmapNode(0, 0, [], 0) + self.__hash = -1 + + if isinstance(col, Map): + self.__count = col.__count + self.__root = col.__root + self.__hash = col.__hash + col = None + elif isinstance(col, MapMutation): + raise TypeError('cannot create Maps from MapMutations') + + if col or kw: + init = self.update(col, **kw) + self.__count = init.__count + self.__root = init.__root + + @classmethod + def _new(cls, count, root): + m = Map.__new__(Map) + m.__count = count + m.__root = root + m.__hash = -1 + return m + + def __reduce__(self): + return (type(self), (dict(self.items()),)) + + def __len__(self): + return self.__count + + def __eq__(self, other): + if not isinstance(other, Map): + return NotImplemented + + if len(self) != len(other): + return False + + for key, val in self.__root.items(): + try: + oval = other.__root.find(0, map_hash(key), key) + except KeyError: + return False + else: + if oval != val: + return False + + return True + + def update(self, col=None, **kw): + it = None + if col is not None: + if hasattr(col, 'items'): + it = iter(col.items()) + else: + it = iter(col) + + if it is not None: + if kw: + it = iter(itertools.chain(it, kw.items())) + else: + if kw: + it = iter(kw.items()) + + if it is None: + + return self + + mutid = _mut_id() + root = self.__root + count = self.__count + + i = 0 + while True: + try: + tup = next(it) + except StopIteration: + break + + try: + tup = tuple(tup) + except TypeError: + raise TypeError( + 'cannot convert map update ' + 'sequence element #{} to a sequence'.format(i)) from None + key, val, *r = tup + if r: + raise ValueError( + 'map update sequence element #{} has length ' + '{}; 2 is required'.format(i, len(r) + 2)) + + root, added = root.assoc(0, map_hash(key), key, val, mutid) + if added: + count += 1 + + i += 1 + + return Map._new(count, root) + + def mutate(self): + return MapMutation(self.__count, self.__root) + + def set(self, key, val): + new_count = self.__count + new_root, added = self.__root.assoc(0, map_hash(key), key, val, 0) + + if new_root is self.__root: + assert not added + return self + + if added: + new_count += 1 + + return Map._new(new_count, new_root) + + def delete(self, key): + res, node = self.__root.without(0, map_hash(key), key, 0) + if res is W_EMPTY: + return Map() + elif res is W_NOT_FOUND: + raise KeyError(key) + else: + return Map._new(self.__count - 1, node) + + def get(self, key, default=None): + try: + return self.__root.find(0, map_hash(key), key) + except KeyError: + return default + + def __getitem__(self, key): + return self.__root.find(0, map_hash(key), key) + + def __contains__(self, key): + try: + self.__root.find(0, map_hash(key), key) + except KeyError: + return False + else: + return True + + def __iter__(self): + yield from self.__root.keys() + + def keys(self): + return MapKeys(self.__count, self.__root) + + def values(self): + return MapValues(self.__count, self.__root) + + def items(self): + return MapItems(self.__count, self.__root) + + def __hash__(self): + if self.__hash != -1: + return self.__hash + + MAX = sys.maxsize + MASK = 2 * MAX + 1 + + h = 1927868237 * (self.__count * 2 + 1) + h &= MASK + + for key, value in self.__root.items(): + hx = hash(key) + h ^= (hx ^ (hx << 16) ^ 89869747) * 3644798167 + h &= MASK + + hx = hash(value) + h ^= (hx ^ (hx << 16) ^ 89869747) * 3644798167 + h &= MASK + + h = h * 69069 + 907133923 + h &= MASK + + if h > MAX: + h -= MASK + 1 # pragma: no cover + if h == -1: + h = 590923713 # pragma: no cover + + self.__hash = h + return h + + @reprlib.recursive_repr("{...}") + def __repr__(self): + items = [] + for key, val in self.items(): + items.append("{!r}: {!r}".format(key, val)) + return '<immutables.Map({{{}}}) at 0x{:0x}>'.format( + ', '.join(items), id(self)) + + def __dump__(self): # pragma: no cover + buf = [] + self.__root.dump(buf, 0) + return '\n'.join(buf) + + def __class_getitem__(cls, item): + return cls + + +class MapMutation: + + def __init__(self, count, root): + self.__count = count + self.__root = root + self.__mutid = _mut_id() + + def set(self, key, val): + self[key] = val + + def __enter__(self): + return self + + def __exit__(self, *exc): + self.finish() + return False + + def __iter__(self): + raise TypeError('{} is not iterable'.format(type(self))) + + def __delitem__(self, key): + if self.__mutid == 0: + raise ValueError('mutation {!r} has been finished'.format(self)) + + res, new_root = self.__root.without( + 0, map_hash(key), key, self.__mutid) + if res is W_EMPTY: + self.__count = 0 + self.__root = BitmapNode(0, 0, [], self.__mutid) + elif res is W_NOT_FOUND: + raise KeyError(key) + else: + self.__root = new_root + self.__count -= 1 + + def __setitem__(self, key, val): + if self.__mutid == 0: + raise ValueError('mutation {!r} has been finished'.format(self)) + + self.__root, added = self.__root.assoc( + 0, map_hash(key), key, val, self.__mutid) + + if added: + self.__count += 1 + + def pop(self, key, *args): + if self.__mutid == 0: + raise ValueError('mutation {!r} has been finished'.format(self)) + + if len(args) > 1: + raise TypeError( + 'pop() accepts 1 to 2 positional arguments, ' + 'got {}'.format(len(args) + 1)) + elif len(args) == 1: + default = args[0] + else: _______________________________________________ pypy-commit mailing list pypy-commit@python.org https://mail.python.org/mailman/listinfo/pypy-commit