allenai / allenai/tango

`det_hash` is not consistent with `__eq__`

Aperta
#602 0 commenti 0 reazioni 0 assegnatari Vedi su GitHub
bug
Lingua principale
Python
Stelle
572
Fork
55
Metriche di merge delle PR
Nessuna PR unita negli ultimi 30g

Descrizione

### 🐛 Describe the bug

## Problem

I found that `det_hash` can sometimes hash equal objects differently. This was causing me a lot of grief when trying to manually initializing a step and retrieve its cached results. I feel that the default hashing in Tango should (at least) respect `__eq__` for [built-in types](https://docs.python.org/3.9/library/stdtypes.html) and fallback to Pickle serialization for more complex and custom data structures.

### Examples

```python
from tango.common.det_hash import det_hash

x = ["bert", "bert"]
y = ["bert", "bert "[:-1]]
assert x == y
assert det_hash(x) == det_hash(y) # AssertionError

# Also, suppose you invoke this script as `python script.py bert bert`
assert x == sys.argv[1:]
assert det_hash(x) == det_hash(sys.argv[1:]) # AssertionError

# I understand that this is because the object hierarchies may be different for `x` and `y`.

x_addr = [id(i) for i in x]
y_addr = [id(i) for i in y]
assert x_addr[0] == x_addr[1]
assert y_addr[0] == y_addr[1] # AssertionError

# Therefore, `x` and `y` pickle differently.

import dill
assert dill.dumps(x) == dill.dumps(y) # AssertionError
```

## Solutions

In Python, object hashes ([`hash`](https://docs.python.org/3/library/functions.html#hash) or [`__hash__`](https://docs.python.org/3/reference/datamodel.html#object.__hash__)) are indeed expected to respect equality: i.e.

> `x == y` implies both that `x is y` and `hash(x) == hash(y)`

However, there are a few problems with using `__hash__`:

1. mutable data types are not supposed to implement `__hash__`

2. not all classes will implement `__hash__`

3. determinism can only be toggled when initializing the interpreter

I propose the following implementation:

1. At hash time in Tango, we just want the object's instantaneous hash and do not actually care whether objects are immutable. So we can manually hash the mutable built-in types. Also, since mutable types may be nested, we can hash recursively.

2. We can simply fall back to `pickle` serialization for objects that are not hashable. I am assuming that hash collisions between `__hash__` and `pickle` are negligible.

3. Two suggestions:

3.1. We could write a simple C extension to temporarily [disable hash determinism](https://github.com/python/cpython/blob/43a6e4fa4934fcc0cbd83f7f3dc1b23a5f79f24b/Include/cpython/initconfig.h#L143-L144) during Tango's hashing function. (Note: I'm not personally familiar with cpython, am just assuming that this variable can be changed.) Then, we will have deterministic hashing for all types that implement `__hash__`.
3.2. Alternatively, we could write a custom function with deterministic hashing logic for all built-in Python types. This would be recursive (like `rec_hash` above) to handle nested data structures. But custom classes that do implement `__hash__` will not be supported.

Together (with 3.1) that's:

```python
def rec_hash(o: Any) -> str:
if isinstance(o, collections.abc.Sequence): # tuples, lists, ranges
return hash((rec_hash(x) for x in o))
elif isinstance(o, set):
# set elements are guaranteed to be hashable
return hash(frozenset(o))
elif isinstance(o, dict):
# dict keys are guaranteed to be hashable
return hash(sorted(hash((k, rec_hash(v)) for k,v in o.items())))
elif isinstance(o, collections.abc.Hashable):
# nested types may be un-hashable, could raise TypeError
return hash(o)
raise TypeError(f"unhashable type: '{type(o).__name__}'")

def det_hash(o: Any) -> str:
try:
with hash_seed(0): # TODO: need to implement this
h = rec_hash(o)
return base58.b58encode_int(h)
except TypeError:
pass

# Fallback to pickling
m = hashlib.blake2b()
with io.BytesIO() as buffer:
pickler = _DetHashPickler(buffer)
pickler.dump(o)
m.update(buffer.getbuffer())
return base58.b58encode(m.digest()).decode()
```

### Please let me know what you think, thanks!

### Versions

Python 3.9.16
ai2-tango==1.2.1
base58==2.1.1
black==23.7.0
boto3==1.28.54
botocore==1.31.54
cached-path==1.4.0
cachetools==5.3.1
certifi==2023.7.22
charset-normalizer==3.2.0
click==8.1.7
click-help-colors==0.9.2
dill==0.3.7
filelock==3.12.4
fsspec==2023.9.2
gitdb==4.0.10
GitPython==3.1.37
glob2==0.7
google-api-core==2.12.0
google-auth==2.23.0
google-cloud-core==2.3.3
google-cloud-storage==2.11.0
google-crc32c==1.5.0
google-resumable-media==2.6.0
googleapis-common-protos==1.60.0
huggingface-hub==0.16.4
idna==3.4
jmespath==1.0.1
markdown-it-py==3.0.0
mdurl==0.1.2
more-itertools==9.1.0
packaging==23.1
petname==2.6
protobuf==4.24.3
pyasn1==0.5.0
pyasn1-modules==0.3.0
Pygments==2.16.1
python-dateutil==2.8.2
pytz==2023.3.post1
PyYAML==6.0.1
requests==2.31.0
rich==13.5.3
rjsonnet==0.5.3
rsa==4.9
s3transfer==0.6.2
six==1.16.0
smmap==5.0.1
sqlitedict==2.1.0
tqdm==4.66.1
typing_extensions==4.8.0
urllib3==1.26.16
xxhash==3.3.0

Guida per i contributori

Apri la guida per i contributori

Valutazione

Questa issue non è ancora stata valutata.

Ricevi le nuove issue nella tua casella

Un breve riepilogo di issue GitHub adatte ai principianti.