bug#55395: What does (1 2 3 . #2) mean?

["Mattias Engdegård" <mattiase@acm.org>]

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

14 maj 2022 kl. 15.45 skrev Stefan Monnier <monnier@iro.umontreal.ca>:

> I do have the impression that it used to be "correct", but I can't
> remember of a single time where I actually made use of that NNN.
> 
> And even if you know what it means and it works correctly, it's pretty
> hard for a normal human to correctly count the depth starting from
> the root.

It is. Counting upwards from a leaf seems slightly easier.

Perhaps these attempts to generate a meaningful circularity reference is a fool's errand and we should just go with #!circle! or something similar.

Anyway, I'm attaching a patch that tries to put some meaning back in the ` . #N` notation: it's an index into the same list, as it used to be, I think, prior to the switch from Floyd to Brent. This is done by keeping track of the index of the tortoise at all times, which isn't very expensive at all.

Without the patch: (rho 4 1) => (1 2 3 4 5 5 5 . #3)
With the patch:    (rho 4 1) => (1 2 3 4 5 5 5 . #6)

which should be a mild improvement.
It's still ambiguous:

 (1 1 . #1)

could mean either

 #1=(1 . #1#)

or

 #1=(1 1 . #1#)

and

 [(1 2 3 . #0)]

could mean either

 [#1=(1 2 3 . #1#)]

or
 #1=[(1 2 3 . #1#)]

but maybe it's less wrong, with room for future improvement?


[-- Attachment #2: circular-list-print-index.diff --]
[-- Type: application/octet-stream, Size: 2471 bytes --]

diff --git a/src/print.c b/src/print.c
index da4869e8fb..823bc07406 100644
--- a/src/print.c
+++ b/src/print.c
@@ -2028,12 +2028,12 @@ named_escape (int i)
   union {
     struct {
       Lisp_Object last;		/* cons whose car was just printed  */
-      ptrdiff_t idx;		/* index of next element */
-      intmax_t maxlen;		/* max length (from Vprint_length) */
+      intmax_t maxlen;		/* max number of elements left to print */
       /* state for Brent cycle detection */
       Lisp_Object tortoise;     /* slow pointer */
       ptrdiff_t n;		/* tortoise step countdown */
       ptrdiff_t m;		/* tortoise step period */
+      ptrdiff_t tortoise_idx;	/* index of tortoise */
     } list;
     struct {
       Lisp_Object obj;		/* object to print after " . " */
@@ -2408,10 +2408,10 @@ print_object (Lisp_Object obj, Lisp_Object printcharfun, bool escapeflag)
 		  .type = PE_list,
 		  .u.list.last = obj,
 		  .u.list.maxlen = print_length,
-		  .u.list.idx = 1,
 		  .u.list.tortoise = obj,
 		  .u.list.n = 2,
 		  .u.list.m = 2,
+		  .u.list.tortoise_idx = 0,
 		});
 	      /* print the car */
 	      obj = XCAR (obj);
@@ -2582,10 +2582,8 @@ print_object (Lisp_Object obj, Lisp_Object printcharfun, bool escapeflag)
 
 		printchar (' ', printcharfun);
 
-		/* FIXME: We wouldn't need to keep track of idx if we
-		   count down maxlen instead, and maintain a separate
-		   tortoise index if required.  */
-		if (e->u.list.idx >= e->u.list.maxlen)
+		--e->u.list.maxlen;
+		if (e->u.list.maxlen <= 0)
 		  {
 		    print_c_string ("...)", printcharfun);
 		    --prstack.sp;
@@ -2594,22 +2592,21 @@ print_object (Lisp_Object obj, Lisp_Object printcharfun, bool escapeflag)
 		  }
 
 		e->u.list.last = next;
-		e->u.list.idx++;
 		e->u.list.n--;
 		if (e->u.list.n == 0)
 		  {
 		    /* Double tortoise update period and teleport it.  */
+		    e->u.list.tortoise_idx += e->u.list.m;
 		    e->u.list.m <<= 1;
 		    e->u.list.n = e->u.list.m;
 		    e->u.list.tortoise = next;
 		  }
 		else if (BASE_EQ (next, e->u.list.tortoise))
 		  {
-		    /* FIXME: This #N tail index is bug-compatible with
-		       previous implementations but actually nonsense;
+		    /* FIXME: This #N tail index is somewhat ambiguous;
 		       see bug#55395.  */
 		    int len = sprintf (buf, ". #%" PRIdMAX ")",
-				       (e->u.list.idx >> 1) - 1);
+				       e->u.list.tortoise_idx);
 		    strout (buf, len, len, printcharfun);
 		    --prstack.sp;
 		    --print_depth;