bug#63671: Add function to test equality of hash tables

bug#63671: Add function to test equality of hash tables

[Joseph Turner via Bug reports for GNU Emacs, the Swiss army knife of text editors]

Hello!

Would y'all be open to adding something like this?

(defun hash-equal (hash1 hash2)
  "Return non-nil when the contents of HASH1 and HASH2 are equal.
Table values are compared using `equal' unless they are both hash
tables themselves, in which case `hash-equal' is used.
Does not compare equality predicates."
  (and (= (hash-table-count hash1)
          (hash-table-count hash2))
       (catch 'flag (maphash (lambda (key hash1-value)
                               (let ((hash2-value (gethash key hash2)))
                                 (or (if (and (hash-table-p hash1-value)
                                              (hash-table-p hash2-value))
                                         (hash-equal hash1-value hash2-value)
                                       (equal hash1-value hash2-value))
                                     (throw 'flag nil))))
                             hash1)
              t)))

Rudimentary test:

(let ((hash1 (make-hash-table))
      (hash2 (make-hash-table))
      (hash3 (make-hash-table))
      (hash4 (make-hash-table)))
  (puthash 'foo "foo" hash1)
  (puthash 'foo "foo" hash2)
  (puthash 'bar "foo" hash3)
  (puthash 'bar "foo" hash4)
  (puthash 'baz hash3 hash1)
  (puthash 'baz hash4 hash2)
  (hash-equal hash1 hash2))

We could use hash-table-test to compare predicates, perhaps
dependent on the presence of a 'compare-tests flag?

Best,

Joseph

bug#63671: Add function to test equality of hash tables

[Mattias Engdegård]

Thank you, but this seems a bit too specific to your own requirements -- maybe you can keep that procedure locally where you need it? The standard library must be generally useful with clear semantics.

bug#63671: Add function to test equality of hash tables

[Joseph Turner via Bug reports for GNU Emacs, the Swiss army knife of text editors]

Mattias Engdegård <mattias.engdegard@gmail.com> writes:

> Thank you, but this seems a bit too specific to your own requirements
> -- maybe you can keep that procedure locally where you need it?

It's no problem to keep the procedure local.

> The standard library must be generally useful with clear semantics.

Would extending `equal' to handle hash tables be generally useful?

Joseph

bug#63671: Add function to test equality of hash tables

[Ihor Radchenko]

Joseph Turner via "Bug reports for GNU Emacs, the Swiss army knife of
text editors" <bug-gnu-emacs@gnu.org> writes:

>> The standard library must be generally useful with clear semantics.
>
> Would extending `equal' to handle hash tables be generally useful?

See https://yhetil.org/emacs-devel/871qvz4kdw.fsf@localhost/

-- 
Ihor Radchenko // yantar92,
Org mode contributor,
Learn more about Org mode at <https://orgmode.org/>.
Support Org development at <https://liberapay.com/org-mode>,
or support my work at <https://liberapay.com/yantar92>

bug#63671: Add function to test equality of hash tables

[Mattias Engdegård]

[-- Attachment #1: Type: text/plain, Size: 553 bytes --]

24 maj 2023 kl. 19.27 skrev Joseph Turner <joseph@breatheoutbreathe.in>:

> Would extending `equal' to handle hash tables be generally useful?

It would, but doing so would be very risky at this point since it would change long-standing semantics.

We could make an augmented version of `equal` but what we really want is one that works for user-defined types (see Ihor's reference to a previous discussion).

Anyway, here's an old patch I had lying around, in case we decide that we do need a shoddy equality predicate for hash tables only.


[-- Attachment #2: hash-table-equal-p.diff --]
[-- Type: application/octet-stream, Size: 3636 bytes --]

diff --git a/lisp/emacs-lisp/subr-x.el b/lisp/emacs-lisp/subr-x.el
index 9cd793d05c..17ca80a297 100644
--- a/lisp/emacs-lisp/subr-x.el
+++ b/lisp/emacs-lisp/subr-x.el
@@ -93,6 +93,28 @@ hash-table-values
   "Return a list of values in HASH-TABLE."
   (cl-loop for v being the hash-values of hash-table collect v))
 
+(defun hash-table-equal-p (h1 h2 &optional value-eq)
+  "Whether the hash tables H1 and H2 are equal with respect to VALUE-EQ.
+Equality means that the tables have the same equality predicate
+and the same set of key-value pairs where keys are compared by
+that predicate and values by VALUE-EQ, which defaults to `eq'."
+  (or (eq h1 h2)
+      (and (= (hash-table-count h1) (hash-table-count h2))
+           (eq (hash-table-test h1) (hash-table-test h2))
+           (progn
+             (unless value-eq
+               (setq value-eq #'eq))
+             ;; Loop over the physically smaller table.
+             (when (> (hash-table-size h1) (hash-table-size h2))
+               (cl-rotatef h1 h2))
+             (catch 'done
+               (maphash
+                (lambda (k v)
+                  (unless (funcall value-eq v (gethash k h2 (not v)))
+                    (throw 'done nil)))
+                h1)
+               t)))))
+
 (defsubst string-empty-p (string)
   "Check whether STRING is empty."
   (string= string ""))
diff --git a/test/lisp/emacs-lisp/subr-x-tests.el b/test/lisp/emacs-lisp/subr-x-tests.el
index 7f3916c2c0..923155eedb 100644
--- a/test/lisp/emacs-lisp/subr-x-tests.el
+++ b/test/lisp/emacs-lisp/subr-x-tests.el
@@ -743,6 +743,55 @@ test-with-buffer-unmodified-if-unchanged
           (with-current-buffer inner
             (should-not (buffer-modified-p))))))))
 
+(ert-deftest subr-x--hash-table-equal-p ()
+  (cl-flet ((hashtab (test &rest elts)
+              (let ((h (make-hash-table :test test)))
+                (while elts
+                  (let* ((key (pop elts))
+                         (val (pop elts)))
+                    (puthash key val h)))
+                h)))
+
+    (let ((h1 (hashtab #'eq 'a (list 1) 'b (list 2))
+          (h2 (hashtab #'eq 'a (list 1) 'b (list 2)))))
+      (should (hash-table-equal-p h1 h2 #'equal))
+      (should (hash-table-equal-p h2 h1 #'equal))
+      (should (not (hash-table-equal-p h1 h2 #'eq)))
+      (should (not (hash-table-equal-p h2 h1 #'eq)))
+      (should (hash-table-equal-p h1 h1 #'eq)))
+
+    (let ((h1 (hashtab #'eql 1 'a 2 'b)
+          (h2 (hashtab #'equal 1 'a 2 'b))))
+      (should (not (hash-table-equal-p h1 h2)))
+      (should (not (hash-table-equal-p h2 h1))))
+
+    (let ((h1 (hashtab #'eql 1 'a 2 'a)
+          (h2 (hashtab #'eql 1 'a))))
+      (should (not (hash-table-equal-p h1 h2)))
+      (should (not (hash-table-equal-p h2 h1))))
+
+    (let ((h1 (hashtab #'eql 1 'a 2 'a)
+          (h2 (hashtab #'eql 1 'a 2 'b))))
+      (should (not (hash-table-equal-p h1 h2)))
+      (should (not (hash-table-equal-p h2 h1))))
+
+    (let ((h1 (hashtab #'eql 1 'a 2 'a)
+          (h2 (hashtab #'eql 1 'a 3 'a))))
+      (should (not (hash-table-equal-p h1 h2)))
+      (should (not (hash-table-equal-p h2 h1))))
+
+    (let ((h1 (hashtab #'eql)
+          (h2 (hashtab #'eql))))
+      (should (hash-table-equal-p h1 h2))
+      (should (hash-table-equal-p h2 h1)))
+
+    (let ((h1 (make-hash-table :test #'eql :size 1000 :rehash-size 3.5))
+          (h2 (hashtab #'eql 10 'a 20 'b)))
+      (puthash 10 'a h1)
+      (puthash 20 'b h1)
+      (should (hash-table-equal-p h1 h2))
+      (should (hash-table-equal-p h2 h1)))
+    ))
 
 (provide 'subr-x-tests)
 ;;; subr-x-tests.el ends here

bug#63671: Add function to test equality of hash tables

[Joseph Turner via Bug reports for GNU Emacs, the Swiss army knife of text editors]

Mattias Engdegård <mattias.engdegard@gmail.com> writes:

> 24 maj 2023 kl. 19.27 skrev Joseph Turner <joseph@breatheoutbreathe.in>:
>
>> Would extending `equal' to handle hash tables be generally useful?
>
> It would, but doing so would be very risky at this point since it would change long-standing semantics.
>
> We could make an augmented version of `equal` but what we really want is one that works for user-defined types (see Ihor's reference to a previous discussion).
>
> Anyway, here's an old patch I had lying around, in case we decide that we do need a shoddy equality predicate for hash tables only.

Thank you for the references, Ihor and Mattias! Since this is a
duplicate of Ihor's thread, my report should probably be closed.

How do I close this report?

Joseph

bug#63671: Add function to test equality of hash tables

[Ihor Radchenko]

Joseph Turner <joseph@breatheoutbreathe.in> writes:

> Thank you for the references, Ihor and Mattias! Since this is a
> duplicate of Ihor's thread, my report should probably be closed.

If we are serious about adding this feature, lets not close this report.
My email was on emacs-devel, and it is thus less visible compared to
something being tracked on debbugs.

-- 
Ihor Radchenko // yantar92,
Org mode contributor,
Learn more about Org mode at <https://orgmode.org/>.
Support Org development at <https://liberapay.com/org-mode>,
or support my work at <https://liberapay.com/yantar92>

bug#63671: Add function to test equality of hash tables

[Joseph Turner via Bug reports for GNU Emacs, the Swiss army knife of text editors]

Ihor Radchenko <yantar92@posteo.net> writes:

> If we are serious about adding this feature, lets not close this report.
> My email was on emacs-devel, and it is thus less visible compared to
> something being tracked on debbugs.

I would be happy to see this feature added to Emacs! Unfortunately, I
won't be of much help right now since I have no C experience.

bug#63671: Add function to test equality of hash tables

[Joseph Turner via Bug reports for GNU Emacs, the Swiss army knife of text editors]

Ihor Radchenko <yantar92@posteo.net> writes:

> If we are serious about adding this feature, lets not close this report.
> My email was on emacs-devel, and it is thus less visible compared to
> something being tracked on debbugs.

I would be happy to see this feature added to Emacs! Unfortunately, I
won't be of much help right now since I have no C experience.

bug#63671: Add function to test equality of hash tables

[Mattias Engdegård]

25 maj 2023 kl. 08.31 skrev Ihor Radchenko <yantar92@posteo.net>:

> If we are serious about adding this feature, lets not close this report.

I for one am not, at least not now.

bug#63671: Add function to test equality of hash tables

[Stefan Kangas]

Mattias Engdegård <mattias.engdegard@gmail.com> writes:

> 25 maj 2023 kl. 08.31 skrev Ihor Radchenko <yantar92@posteo.net>:
>
>> If we are serious about adding this feature, lets not close this report.
>
> I for one am not, at least not now.

Let's close this for now then.