diff options
| author | Elvis Pranskevichus <elvis@edgedb.com> | 2021-08-04 19:25:44 -0700 |
|---|---|---|
| committer | GitHub <noreply@github.com> | 2021-08-04 19:25:44 -0700 |
| commit | fa355239e70411179c70b16ed4ff7113d8008dad (patch) | |
| tree | 776efefb6e20a2ef53a903172032250f86acb5d6 | |
| parent | 3f8cb24cf3da3af1b86ef61cefc091784d39ec08 (diff) | |
| download | immutables-fa355239e70411179c70b16ed4ff7113d8008dad.tar.gz immutables-fa355239e70411179c70b16ed4ff7113d8008dad.zip | |
Fix test_none_collisions on 32-bit systems (#69)
There are two issues at play here:
1. Python version of `map_hash` unnecessarily performs hash truncation
even if the hash is already 32-bit wide, which potentially converts
it from signed int to unsigned long.
2. The `test_none_collisions` test generates a collision node with
hash greater than 2^32.
Both of these are problematic on 32-bit systems, where `sizeof(Py_hash_t)`
is 4, and so anything that doesn't fit into `Py_hash_t` gets bit-mangled,
breaking the `hash(x) != x` invariance that the test relies upon.
Fixes: #53
Fixes: #50
| -rw-r--r-- | .github/workflows/tests.yml | 10 | ||||
| -rw-r--r-- | immutables/map.py | 5 | ||||
| -rw-r--r-- | tests/test_none_keys.py | 14 |
3 files changed, 22 insertions, 7 deletions
diff --git a/.github/workflows/tests.yml b/.github/workflows/tests.yml index 8613b21..90bffc3 100644 --- a/.github/workflows/tests.yml +++ b/.github/workflows/tests.yml @@ -16,6 +16,13 @@ jobs: matrix: python-version: [3.6, 3.7, 3.8, 3.9, 3.10.0-beta.4] os: [windows-latest, ubuntu-latest, macos-latest] + arch: [x64, x86] + exclude: + # 32-bit Python is only available on Windows + - os: ubuntu-latest + arch: x86 + - os: macos-latest + arch: x86 steps: - uses: actions/checkout@v2 @@ -38,11 +45,12 @@ jobs: if: steps.release.outputs.version == 0 with: python-version: ${{ matrix.python-version }} + architecture: ${{ matrix.arch }} - name: Test if: steps.release.outputs.version == 0 run: | - pip install -e .[test] + pip install --verbose -e .[test] flake8 immutables/ tests/ mypy immutables/ python -m pytest -v diff --git a/immutables/map.py b/immutables/map.py index 2c1ffa9..0ad2858 100644 --- a/immutables/map.py +++ b/immutables/map.py @@ -19,7 +19,10 @@ _mut_id = itertools.count(1).__next__ def map_hash(o): x = hash(o) - return (x & 0xffffffff) ^ ((x >> 32) & 0xffffffff) + if sys.hash_info.width > 32: + return (x & 0xffffffff) ^ ((x >> 32) & 0xffffffff) + else: + return x def map_mask(hash, shift): diff --git a/tests/test_none_keys.py b/tests/test_none_keys.py index 8c0bb37..26d4220 100644 --- a/tests/test_none_keys.py +++ b/tests/test_none_keys.py @@ -1,3 +1,4 @@ +import ctypes import unittest from immutables.map import map_hash, map_mask, Map as PyMap @@ -6,16 +7,19 @@ from immutables._testutils import HashKey none_hash = map_hash(None) assert(none_hash != 1) -assert((none_hash >> 32) == 0) +assert(none_hash.bit_length() <= 32) -not_collision = 0xffffffff & (~none_hash) +none_hash_u = ctypes.c_size_t(none_hash).value +not_collision = 0xffffffff & (~none_hash_u) mask = 0x7ffffffff -none_collisions = [none_hash & (mask >> shift) +none_collisions = [none_hash_u & (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)] +none_collisions = [ + ctypes.c_ssize_t(h | (not_collision & (mask << shift))).value + for shift, h in zip(range(5, 37, 5), none_collisions) +] class NoneCollision(HashKey): |