From c3dff14c6906ad48b39c16e749301e409f83c717 Mon Sep 17 00:00:00 2001 From: Nao Pross Date: Fri, 8 Mar 2024 01:55:19 +0100 Subject: Replace hash() with hashlib.sha256() for robustness to collision --- mdpoly/abc.py | 25 +++++++++++++++++-------- 1 file changed, 17 insertions(+), 8 deletions(-) diff --git a/mdpoly/abc.py b/mdpoly/abc.py index 87a6c13..36cb1c3 100644 --- a/mdpoly/abc.py +++ b/mdpoly/abc.py @@ -15,6 +15,7 @@ from enum import Enum, auto from copy import copy from abc import ABC, abstractmethod from dataclassabc import dataclassabc +from hashlib import sha256 # ┏━╸╻ ╻┏━┓┏━┓┏━╸┏━┓┏━┓╻┏━┓┏┓╻┏━┓ @@ -93,12 +94,9 @@ class Expr(ABC): def __iter__(self) -> Iterable[Expr]: yield from self.children() - def __hash__(self) -> int: - return hash(self.left) + hash(self.right) - def __eq__(self, other: object) -> bool: if isinstance(other, Expr): - return hash(self) == hash(other) + return self.subtree_hash() == other.subtree_hash() return False # --- Methods for polynomial expression --- @@ -114,6 +112,12 @@ class Expr(ABC): # --- Methods for tree data structure --- + def subtree_hash(self) -> bytes: + h = sha256() + h.update(self.left.subtree_hash()) + h.update(self.right.subtree_hash()) + return h.digest() + def children(self) -> Sequence[Expr]: """ Iterate over the two nodes """ return self.left, self.right @@ -252,9 +256,6 @@ class Leaf(Expr): def __repr__(self) -> str: return self.name - def __hash__(self) -> int: - return hash((self.__class__.__qualname__, self.algebra, self.name, self.shape)) - # -- Overloads --- @property @@ -282,6 +283,14 @@ class Leaf(Expr): """ Overloads right child setter with function that does nothing. (Leaves do not have children). """ + def subtree_hash(self) -> bytes: + h = sha256() + h.update(self.__class__.__qualname__.encode("utf-8")) + h.update(bytes(self.algebra.value)) + h.update(self.name.encode("utf-8")) # type: ignore + h.update(bytes(self.shape)) + return h.digest() + T = TypeVar("T") @@ -314,7 +323,7 @@ class Nothing(Leaf): """ A leaf that is nothing. This is a placeholder (eg. for unary operators). """ - name: str = "" + name: str = "." shape: Shape = Shape(0, 0) algebra: Algebra = Algebra.none -- cgit v1.2.1