Staging
v0.8.1
v0.8.1
https://github.com/python/cpython
Tip revision: 74f4bd53e03ded8408bcc2de67cf0f5a4ac5b1a1 authored by Barry Warsaw on 23 February 2012, 15:59:38 UTC
Bump some more copyright years (as per PEP 101), since this is the first
Bump some more copyright years (as per PEP 101), since this is the first
Tip revision: 74f4bd5
test_hash.py
# test the invariant that
# iff a==b then hash(a)==hash(b)
#
# Also test that hash implementations are inherited as expected
import datetime
import os
import sys
import unittest
from test.support.script_helper import assert_python_ok
from collections.abc import Hashable
IS_64BIT = sys.maxsize > 2**32
def lcg(x, length=16):
"""Linear congruential generator"""
if x == 0:
return bytes(length)
out = bytearray(length)
for i in range(length):
x = (214013 * x + 2531011) & 0x7fffffff
out[i] = (x >> 16) & 0xff
return bytes(out)
def pysiphash(uint64):
"""Convert SipHash24 output to Py_hash_t
"""
assert 0 <= uint64 < (1 << 64)
# simple unsigned to signed int64
if uint64 > (1 << 63) - 1:
int64 = uint64 - (1 << 64)
else:
int64 = uint64
# mangle uint64 to uint32
uint32 = (uint64 ^ uint64 >> 32) & 0xffffffff
# simple unsigned to signed int32
if uint32 > (1 << 31) - 1:
int32 = uint32 - (1 << 32)
else:
int32 = uint32
return int32, int64
def skip_unless_internalhash(test):
"""Skip decorator for tests that depend on SipHash24 or FNV"""
ok = sys.hash_info.algorithm in {"fnv", "siphash24"}
msg = "Requires SipHash24 or FNV"
return test if ok else unittest.skip(msg)(test)
class HashEqualityTestCase(unittest.TestCase):
def same_hash(self, *objlist):
# Hash each object given and fail if
# the hash values are not all the same.
hashed = list(map(hash, objlist))
for h in hashed[1:]:
if h != hashed[0]:
self.fail("hashed values differ: %r" % (objlist,))
def test_numeric_literals(self):
self.same_hash(1, 1, 1.0, 1.0+0.0j)
self.same_hash(0, 0.0, 0.0+0.0j)
self.same_hash(-1, -1.0, -1.0+0.0j)
self.same_hash(-2, -2.0, -2.0+0.0j)
def test_coerced_integers(self):
self.same_hash(int(1), int(1), float(1), complex(1),
int('1'), float('1.0'))
self.same_hash(int(-2**31), float(-2**31))
self.same_hash(int(1-2**31), float(1-2**31))
self.same_hash(int(2**31-1), float(2**31-1))
# for 64-bit platforms
self.same_hash(int(2**31), float(2**31))
self.same_hash(int(-2**63), float(-2**63))
self.same_hash(int(2**63), float(2**63))
def test_coerced_floats(self):
self.same_hash(int(1.23e300), float(1.23e300))
self.same_hash(float(0.5), complex(0.5, 0.0))
def test_unaligned_buffers(self):
# The hash function for bytes-like objects shouldn't have
# alignment-dependent results (example in issue #16427).
b = b"123456789abcdefghijklmnopqrstuvwxyz" * 128
for i in range(16):
for j in range(16):
aligned = b[i:128+j]
unaligned = memoryview(b)[i:128+j]
self.assertEqual(hash(aligned), hash(unaligned))
_default_hash = object.__hash__
class DefaultHash(object): pass
_FIXED_HASH_VALUE = 42
class FixedHash(object):
def __hash__(self):
return _FIXED_HASH_VALUE
class OnlyEquality(object):
def __eq__(self, other):
return self is other
class OnlyInequality(object):
def __ne__(self, other):
return self is not other
class InheritedHashWithEquality(FixedHash, OnlyEquality): pass
class InheritedHashWithInequality(FixedHash, OnlyInequality): pass
class NoHash(object):
__hash__ = None
class HashInheritanceTestCase(unittest.TestCase):
default_expected = [object(),
DefaultHash(),
OnlyInequality(),
]
fixed_expected = [FixedHash(),
InheritedHashWithEquality(),
InheritedHashWithInequality(),
]
error_expected = [NoHash(),
OnlyEquality(),
]
def test_default_hash(self):
for obj in self.default_expected:
self.assertEqual(hash(obj), _default_hash(obj))
def test_fixed_hash(self):
for obj in self.fixed_expected:
self.assertEqual(hash(obj), _FIXED_HASH_VALUE)
def test_error_hash(self):
for obj in self.error_expected:
self.assertRaises(TypeError, hash, obj)
def test_hashable(self):
objects = (self.default_expected +
self.fixed_expected)
for obj in objects:
self.assertIsInstance(obj, Hashable)
def test_not_hashable(self):
for obj in self.error_expected:
self.assertNotIsInstance(obj, Hashable)
# Issue #4701: Check that some builtin types are correctly hashable
class DefaultIterSeq(object):
seq = range(10)
def __len__(self):
return len(self.seq)
def __getitem__(self, index):
return self.seq[index]
class HashBuiltinsTestCase(unittest.TestCase):
hashes_to_check = [enumerate(range(10)),
iter(DefaultIterSeq()),
iter(lambda: 0, 0),
]
def test_hashes(self):
_default_hash = object.__hash__
for obj in self.hashes_to_check:
self.assertEqual(hash(obj), _default_hash(obj))
class HashRandomizationTests:
# Each subclass should define a field "repr_", containing the repr() of
# an object to be tested
def get_hash_command(self, repr_):
return 'print(hash(eval(%a)))' % repr_
def get_hash(self, repr_, seed=None):
env = os.environ.copy()
env['__cleanenv'] = True # signal to assert_python not to do a copy
# of os.environ on its own
if seed is not None:
env['PYTHONHASHSEED'] = str(seed)
else:
env.pop('PYTHONHASHSEED', None)
out = assert_python_ok(
'-c', self.get_hash_command(repr_),
**env)
stdout = out[1].strip()
return int(stdout)
def test_randomized_hash(self):
# two runs should return different hashes
run1 = self.get_hash(self.repr_, seed='random')
run2 = self.get_hash(self.repr_, seed='random')
self.assertNotEqual(run1, run2)
class StringlikeHashRandomizationTests(HashRandomizationTests):
repr_ = None
repr_long = None
# 32bit little, 64bit little, 32bit big, 64bit big
known_hashes = {
'djba33x': [ # only used for small strings
# seed 0, 'abc'
[193485960, 193485960, 193485960, 193485960],
# seed 42, 'abc'
[-678966196, 573763426263223372, -820489388, -4282905804826039665],
],
'siphash24': [
# NOTE: PyUCS2 layout depends on endianness
# seed 0, 'abc'
[1198583518, 4596069200710135518, 1198583518, 4596069200710135518],
# seed 42, 'abc'
[273876886, -4501618152524544106, 273876886, -4501618152524544106],
# seed 42, 'abcdefghijk'
[-1745215313, 4436719588892876975, -1745215313, 4436719588892876975],
# seed 0, 'äú∑ℇ'
[493570806, 5749986484189612790, -1006381564, -5915111450199468540],
# seed 42, 'äú∑ℇ'
[-1677110816, -2947981342227738144, -1860207793, -4296699217652516017],
],
'fnv': [
# seed 0, 'abc'
[-1600925533, 1453079729188098211, -1600925533,
1453079729188098211],
# seed 42, 'abc'
[-206076799, -4410911502303878509, -1024014457,
-3570150969479994130],
# seed 42, 'abcdefghijk'
[811136751, -5046230049376118746, -77208053 ,
-4779029615281019666],
# seed 0, 'äú∑ℇ'
[44402817, 8998297579845987431, -1956240331,
-782697888614047887],
# seed 42, 'äú∑ℇ'
[-283066365, -4576729883824601543, -271871407,
-3927695501187247084],
]
}
def get_expected_hash(self, position, length):
if length < sys.hash_info.cutoff:
algorithm = "djba33x"
else:
algorithm = sys.hash_info.algorithm
if sys.byteorder == 'little':
platform = 1 if IS_64BIT else 0
else:
assert(sys.byteorder == 'big')
platform = 3 if IS_64BIT else 2
return self.known_hashes[algorithm][position][platform]
def test_null_hash(self):
# PYTHONHASHSEED=0 disables the randomized hash
known_hash_of_obj = self.get_expected_hash(0, 3)
# Randomization is enabled by default:
self.assertNotEqual(self.get_hash(self.repr_), known_hash_of_obj)
# It can also be disabled by setting the seed to 0:
self.assertEqual(self.get_hash(self.repr_, seed=0), known_hash_of_obj)
@skip_unless_internalhash
def test_fixed_hash(self):
# test a fixed seed for the randomized hash
# Note that all types share the same values:
h = self.get_expected_hash(1, 3)
self.assertEqual(self.get_hash(self.repr_, seed=42), h)
@skip_unless_internalhash
def test_long_fixed_hash(self):
if self.repr_long is None:
return
h = self.get_expected_hash(2, 11)
self.assertEqual(self.get_hash(self.repr_long, seed=42), h)
class StrHashRandomizationTests(StringlikeHashRandomizationTests,
unittest.TestCase):
repr_ = repr('abc')
repr_long = repr('abcdefghijk')
repr_ucs2 = repr('äú∑ℇ')
@skip_unless_internalhash
def test_empty_string(self):
self.assertEqual(hash(""), 0)
@skip_unless_internalhash
def test_ucs2_string(self):
h = self.get_expected_hash(3, 6)
self.assertEqual(self.get_hash(self.repr_ucs2, seed=0), h)
h = self.get_expected_hash(4, 6)
self.assertEqual(self.get_hash(self.repr_ucs2, seed=42), h)
class BytesHashRandomizationTests(StringlikeHashRandomizationTests,
unittest.TestCase):
repr_ = repr(b'abc')
repr_long = repr(b'abcdefghijk')
@skip_unless_internalhash
def test_empty_string(self):
self.assertEqual(hash(b""), 0)
class MemoryviewHashRandomizationTests(StringlikeHashRandomizationTests,
unittest.TestCase):
repr_ = "memoryview(b'abc')"
repr_long = "memoryview(b'abcdefghijk')"
@skip_unless_internalhash
def test_empty_string(self):
self.assertEqual(hash(memoryview(b"")), 0)
class DatetimeTests(HashRandomizationTests):
def get_hash_command(self, repr_):
return 'import datetime; print(hash(%s))' % repr_
class DatetimeDateTests(DatetimeTests, unittest.TestCase):
repr_ = repr(datetime.date(1066, 10, 14))
class DatetimeDatetimeTests(DatetimeTests, unittest.TestCase):
repr_ = repr(datetime.datetime(1, 2, 3, 4, 5, 6, 7))
class DatetimeTimeTests(DatetimeTests, unittest.TestCase):
repr_ = repr(datetime.time(0))
class HashDistributionTestCase(unittest.TestCase):
def test_hash_distribution(self):
# check for hash collision
base = "abcdefghabcdefg"
for i in range(1, len(base)):
prefix = base[:i]
with self.subTest(prefix=prefix):
s15 = set()
s255 = set()
for c in range(256):
h = hash(prefix + chr(c))
s15.add(h & 0xf)
s255.add(h & 0xff)
# SipHash24 distribution depends on key, usually > 60%
self.assertGreater(len(s15), 8, prefix)
self.assertGreater(len(s255), 128, prefix)
if __name__ == "__main__":
unittest.main()