Subject: bug#73883: [PATCH] Fix 'equal' freezing on large cyclic objects

From: Ethan Kong <[email-masked]>
Date: Sat, 9 Nov 2024 11:36:56 +0800

On 24/11/09 02:57, Stefan Monnier wrote:
> While the new title is arguably better for a bug report, the old one was
> better at describing your patch.  🙂

I see. Here is the patch with the old summary line.
From 425270179bb22630b7ad5871fcfcee84737b55fb Mon Sep 17 00:00:00 2001
From: Ethan Kong <[email-masked]>
Date: Sat, 19 Oct 2024 12:43:27 +0800
Subject: [PATCH] Fix internal_equal so that it uses at most one hash table

* src/fns.c (internal_equal): Delegate to internal_equal_1.
(internal_equal_1): New function. Pass the hash table argument by
pointer instead of by value.
---
 src/fns.c | 23 +++++++++++++++--------
 1 file changed, 15 insertions(+), 8 deletions(-)

diff --git a/src/fns.c b/src/fns.c
index 2de04d06519..ef6922c137b 100644
--- a/src/fns.c
+++ b/src/fns.c
@@ -2823,8 +2823,8 @@ equal_no_quit (Lisp_Object o1, Lisp_Object o2)
    if EQUAL_KIND == EQUAL_NO_QUIT.  */
 
 static bool
-internal_equal (Lisp_Object o1, Lisp_Object o2, enum equal_kind equal_kind,
-		int depth, Lisp_Object ht)
+internal_equal_1 (Lisp_Object o1, Lisp_Object o2, enum equal_kind equal_kind,
+		  int depth, Lisp_Object *ht)
 {
  tail_recurse:
   if (depth > 10)
@@ -2832,13 +2832,13 @@ internal_equal (Lisp_Object o1, Lisp_Object o2, enum equal_kind equal_kind,
       eassert (equal_kind != EQUAL_NO_QUIT);
       if (depth > 200)
 	error ("Stack overflow in equal");
-      if (NILP (ht))
-	ht = CALLN (Fmake_hash_table, QCtest, Qeq);
+      if (NILP (*ht))
+	*ht = CALLN (Fmake_hash_table, QCtest, Qeq);
       switch (XTYPE (o1))
 	{
 	case Lisp_Cons: case Lisp_Vectorlike:
 	  {
-	    struct Lisp_Hash_Table *h = XHASH_TABLE (ht);
+	    struct Lisp_Hash_Table *h = XHASH_TABLE (*ht);
 	    hash_hash_t hash = hash_from_key (h, o1);
 	    ptrdiff_t i = hash_lookup_with_hash (h, o1, hash);
 	    if (i >= 0)
@@ -2888,8 +2888,8 @@ internal_equal (Lisp_Object o1, Lisp_Object o2, enum equal_kind equal_kind,
 	  {
 	    if (! CONSP (o2))
 	      return false;
-	    if (! internal_equal (XCAR (o1), XCAR (o2),
-				  equal_kind, depth + 1, ht))
+	    if (! internal_equal_1 (XCAR (o1), XCAR (o2),
+				    equal_kind, depth + 1, ht))
 	      return false;
 	    o2 = XCDR (o2);
 	    if (EQ (XCDR (o1), o2))
@@ -2964,7 +2964,7 @@ internal_equal (Lisp_Object o1, Lisp_Object o2, enum equal_kind equal_kind,
 	    Lisp_Object v1, v2;
 	    v1 = AREF (o1, i);
 	    v2 = AREF (o2, i);
-	    if (!internal_equal (v1, v2, equal_kind, depth + 1, ht))
+	    if (!internal_equal_1 (v1, v2, equal_kind, depth + 1, ht))
 	      return false;
 	  }
 	return true;
@@ -2985,6 +2985,13 @@ internal_equal (Lisp_Object o1, Lisp_Object o2, enum equal_kind equal_kind,
   return false;
 }
 
+static bool
+internal_equal (Lisp_Object o1, Lisp_Object o2, enum equal_kind equal_kind,
+		int depth, Lisp_Object ht)
+{
+  return internal_equal_1 (o1, o2, equal_kind, depth, &ht);
+}
+
 /* Return -1/0/1 for the </=/> lexicographic relation between bool-vectors.  */
 static int
 bool_vector_cmp (Lisp_Object a, Lisp_Object b)
-- 
2.43.0.windows.1