Subject: bug#36407: closed (Re: bug#36407: 27.0.50; `plist-get', `equal' etc. and circular "lists")

From: [email-masked] (GNU bug Tracking System)
Date: Fri, 28 Jun 2019 08:06:02 +0000

Your bug report

#36407: 27.0.50; `plist-get', `equal' etc. and circular "lists"

which was filed against the emacs package, has been closed.

The explanation is attached below, along with your original report.
If you require more details, please reply to [email-masked].

-- 
36407: http://debbugs.gnu.org/cgi/bugreport.cgi?bug=36407
GNU Bug Tracking System
Contact [email-masked] with problems

Subject: Re: bug#36407: 27.0.50; `plist-get', `equal' etc. and circular "lists"
From: Pip Cet <[email-masked]>
To: Paul Eggert <[email-masked]>
Cc: [email-masked]
Date: Fri, 28 Jun 2019 08:05:10 +0000
List-Id: <debbugs-submit.debbugs.gnu.org>

On Thu, Jun 27, 2019 at 10:52 PM Paul Eggert <[email-masked]> wrote:
> aren't needed. I installed that patch; thanks.

Thanks!

> > shouldn't `equal' be symmetric?
>
> Yes, on its domain. But circular lists are outside its domain, and the
> documentation doesn't promise any particular behavior on them. It's OK
> if (equal a b) signals an error and (equal b a) does not. It's even OK
> if (equal a b) signals an error and a later call (equal a b) with
> exactly the same (unchanged) arguments does not (because the stack
> happens to have more room the second time). We still have symmetry in
> the sense that (eq (equal a b) (equal b a)) always either returns t or
> signals an error; it never returns nil.

Thanks for your explanation, that makes perfect sense.

I was confused, in part, by the hash table code in internal_equal,
which appears to be designed to handle circular structures with some
generality.

On further thought, maybe that code is written for DAGs which contain
diamond-shaped subgraphs. However, those don't appear to be working
very well...

> I installed the attached doc patch to try to make this a bit clearer.

Thanks again! I'm closing this bug.

Subject: 27.0.50; `plist-get', `equal' etc. and circular "lists"
From: Pip Cet <[email-masked]>
To: [email-masked]
Date: Thu, 27 Jun 2019 21:43:32 +0000
List-Id: <debbugs-submit.debbugs.gnu.org>

plist-get currently contains this code:

  FOR_EACH_TAIL_SAFE (tail)
    {
      <check for success>
      tail = XCDR (tail);
      if (EQ (tail, li.tortoise))
        break;
    }

I don't understand why the last two lines are there. They're
unnecessary for proper plists; for circular plists, they result in
unintuitive behavior; and they depend on details of the
FOR_EACH_TAIL_SAFE implementation.

Can someone enlighten me?

As a tangential issue, shouldn't `equal' be symmetric?

(let* ((l1 '#1=(0 1 2 . #1#))
       (l2 '(0 1 2 0 1 2 . #1#)))
  (equal l2 l1) => t
  (equal l1 l2) => "List contains a loop" error.
  (plist-get l2 1) => 2
  (plist-get l1 1) => nil

Patches attached.
From 722b621835b1470f420ad9610f80f50f4b31a5c6 Mon Sep 17 00:00:00 2001
From: Pip Cet <[email-masked]>
Date: Thu, 27 Jun 2019 20:11:52 +0000
Subject: [PATCH] Remove unnecessary tortoise checks.

* src/fns.c (Fplist_get, Fplist_put, Flax_plist_get)
(Flax_plist_put, Fplist_member): Remove unnecessary check.
* src/json.c (lisp_to_json_toplevel_1): Remove unnecessary check.
---
 src/fns.c  | 10 ----------
 src/json.c |  1 -
 2 files changed, 11 deletions(-)

diff --git a/src/fns.c b/src/fns.c
index fd0c7fc71a..2fc000a7f4 100644
--- a/src/fns.c
+++ b/src/fns.c
@@ -2164,8 +2164,6 @@ DEFUN ("plist-get", Fplist_get, Splist_get, 2, 2, 0,
       if (EQ (prop, XCAR (tail)))
 	return XCAR (XCDR (tail));
       tail = XCDR (tail);
-      if (EQ (tail, li.tortoise))
-	break;
     }
 
   return Qnil;
@@ -2208,8 +2206,6 @@ DEFUN ("plist-put", Fplist_put, Splist_put, 3, 3, 0,
 
       prev = tail;
       tail = XCDR (tail);
-      if (EQ (tail, li.tortoise))
-	circular_list (plist);
     }
   CHECK_TYPE (NILP (tail), Qplistp, plist);
   Lisp_Object newcell
@@ -2247,8 +2243,6 @@ DEFUN ("lax-plist-get", Flax_plist_get, Slax_plist_get, 2, 2, 0,
       if (! NILP (Fequal (prop, XCAR (tail))))
 	return XCAR (XCDR (tail));
       tail = XCDR (tail);
-      if (EQ (tail, li.tortoise))
-	circular_list (plist);
     }
 
   CHECK_TYPE (NILP (tail), Qplistp, plist);
@@ -2280,8 +2274,6 @@ DEFUN ("lax-plist-put", Flax_plist_put, Slax_plist_put, 3, 3, 0,
 
       prev = tail;
       tail = XCDR (tail);
-      if (EQ (tail, li.tortoise))
-	circular_list (plist);
     }
   CHECK_TYPE (NILP (tail), Qplistp, plist);
   Lisp_Object newcell = list2 (prop, val);
@@ -3045,8 +3037,6 @@ DEFUN ("plist-member", Fplist_member, Splist_member, 2, 2, 0,
       tail = XCDR (tail);
       if (! CONSP (tail))
 	break;
-      if (EQ (tail, li.tortoise))
-	circular_list (tail);
     }
   CHECK_TYPE (NILP (tail), Qplistp, plist);
   return Qnil;
diff --git a/src/json.c b/src/json.c
index 23234c767d..48820a1cb0 100644
--- a/src/json.c
+++ b/src/json.c
@@ -404,7 +404,6 @@ lisp_to_json_toplevel_1 (Lisp_Object lisp,
               tail = XCDR (tail);
               CHECK_CONS (tail);
               value = XCAR (tail);
-              if (EQ (tail, li.tortoise)) circular_list (lisp);
             }
           else
             {
-- 
2.20.1

From 57c8e010cea8dfb8d0e6d54992a7543c640c4f9f Mon Sep 17 00:00:00 2001
From: Pip Cet <[email-masked]>
Date: Thu, 27 Jun 2019 21:04:18 +0000
Subject: [PATCH] Make `equal' symmetric.

* src/fns.c (internal_equal): Make symmetric. Copy tortoise-hare
  algorithm from lisp.h
---
 src/fns.c | 23 +++++++++++++++++------
 1 file changed, 17 insertions(+), 6 deletions(-)

diff --git a/src/fns.c b/src/fns.c
index 2fc000a7f4..623435445a 100644
--- a/src/fns.c
+++ b/src/fns.c
@@ -2401,16 +2401,27 @@ internal_equal (Lisp_Object o1, Lisp_Object o2, enum equal_kind equal_kind,
 	      return true;
 	  }
       else
-	FOR_EACH_TAIL (o1)
+	for (struct for_each_tail_internal li1 = { o1, 2, 0, 2 },
+	       li2 = { o2, 2, 0, 2 };
+	     CONSP (o1) && CONSP (o2);
+	     (o1 = XCDR (o1),
+	      o2 = XCDR (o2),
+	      ((--li1.q != 0
+		|| (maybe_quit (), 0 < --li1.n)
+		|| (li1.q = li1.n = li1.max <<= 1, li1.n >>= USHRT_WIDTH,
+		    li1.tortoise = (o1), false))
+	       && EQ (o1, li1.tortoise)) ? circular_list (o1) : (void) 0,
+	      ((--li2.q != 0
+		|| (maybe_quit (), 0 < --li2.n)
+		|| (li2.q = li2.n = li2.max <<= 1, li2.n >>= USHRT_WIDTH,
+		    li2.tortoise = (o2), false))
+	       && EQ (o2, li2.tortoise)) ? circular_list (o2) : (void) 0))
 	  {
-	    if (! CONSP (o2))
-	      return false;
+	    if (EQ (o1, o2))
+	      return true;
 	    if (! internal_equal (XCAR (o1), XCAR (o2),
 				  equal_kind, depth + 1, ht))
 	      return false;
-	    o2 = XCDR (o2);
-	    if (EQ (XCDR (o1), o2))
-	      return true;
 	  }
       depth++;
       goto tail_recurse;
-- 
2.20.1