Replace hash() with hashlib.sha256() for robustness to collision

1 files 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