Subject: bug#56255: 28.1.50; sxhash-equal does not change when object is modified

From: Ihor Radchenko <[email-masked]>
Date: Wed, 29 Jun 2022 20:56:31 +0800

Lars Ingebrigtsen <[email-masked]> writes:

> Ihor Radchenko <[email-masked]> writes:
>
>> The original idea was to detect changed objects in most generic way, as
>> a part of persistent storage library. Oh well.
>
> We could make SXHASH_MAX_DEPTH into a defvar -- or pass the depth in to
> `sxhash-equal'.  However, the hash it's computing is geared towards hash
> tables, so collisions are OK -- it's not a cryptographic hash, so I'm
> not sure it would fit your use case anyway.  I.e., our sxhash_combine is
> very simple.

Well. In my scenario, the object structure creates so bad case that
_all_ the hashes for _all possible_ avl-tree structures collide
(actually, I use plists containing avl-tree structures).

As for the hash tables and collisions. Are you sure that collisions are
OK? Consider the following example:

(setq a (avl-tree--create #'org-element--cache-compare))
(avl-tree-enter a '(headline (:begin 2)))
(setq tbl (make-hash-table :test #'equal))
(puthash a 'value tbl)
(gethash a tbl)
(plist-put (nth 1 (avl-tree-first a)) :begin 10)
(gethash a tbl) ;; the value does not change!

Best,
Ihor