From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.io!.POSTED.blaine.gmane.org!not-for-mail From: Mattias =?UTF-8?Q?Engdeg=C3=A5rd?= Newsgroups: gmane.emacs.bugs Subject: bug#55395: What does (1 2 3 . #2) mean? Date: Wed, 18 May 2022 16:29:51 +0200 Message-ID: <86345ABE-C19C-4096-8550-05E5B78D6C3A@acm.org> References: <4B70C9BE-B784-4B74-A081-7A8B3F8D5136@acm.org> <87ilq931ay.fsf@gnus.org> <715F3D50-7D11-47CF-A34B-6532F1F508D7@acm.org> Mime-Version: 1.0 (Mac OS X Mail 14.0 \(3654.120.0.1.13\)) Content-Type: multipart/mixed; boundary="Apple-Mail=_9C60AD69-423C-4E73-823B-DAA20C4ABAB0" Injection-Info: ciao.gmane.io; posting-host="blaine.gmane.org:116.202.254.214"; logging-data="16291"; mail-complaints-to="usenet@ciao.gmane.io" Cc: 55395@debbugs.gnu.org, Lars Ingebrigtsen To: Stefan Monnier Original-X-From: bug-gnu-emacs-bounces+geb-bug-gnu-emacs=m.gmane-mx.org@gnu.org Wed May 18 16:31:15 2022 Return-path: Envelope-to: geb-bug-gnu-emacs@m.gmane-mx.org Original-Received: from lists.gnu.org ([209.51.188.17]) by ciao.gmane.io with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.92) (envelope-from ) id 1nrKhn-0003zH-Bc for geb-bug-gnu-emacs@m.gmane-mx.org; Wed, 18 May 2022 16:31:15 +0200 Original-Received: from localhost ([::1]:48888 helo=lists1p.gnu.org) by lists.gnu.org with esmtp (Exim 4.90_1) (envelope-from ) id 1nrKhm-0006hO-2b for geb-bug-gnu-emacs@m.gmane-mx.org; Wed, 18 May 2022 10:31:14 -0400 Original-Received: from eggs.gnu.org ([2001:470:142:3::10]:52996) by lists.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1nrKha-0006hE-OQ for bug-gnu-emacs@gnu.org; Wed, 18 May 2022 10:31:03 -0400 Original-Received: from debbugs.gnu.org ([209.51.188.43]:39254) by eggs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_128_GCM_SHA256:128) (Exim 4.90_1) (envelope-from ) id 1nrKha-0004bN-G4 for bug-gnu-emacs@gnu.org; Wed, 18 May 2022 10:31:02 -0400 Original-Received: from Debian-debbugs by debbugs.gnu.org with local (Exim 4.84_2) (envelope-from ) id 1nrKha-0005Xg-DV for bug-gnu-emacs@gnu.org; Wed, 18 May 2022 10:31:02 -0400 X-Loop: help-debbugs@gnu.org Resent-From: Mattias =?UTF-8?Q?Engdeg=C3=A5rd?= Original-Sender: "Debbugs-submit" Resent-CC: bug-gnu-emacs@gnu.org Resent-Date: Wed, 18 May 2022 14:31:02 +0000 Resent-Message-ID: Resent-Sender: help-debbugs@gnu.org X-GNU-PR-Message: followup 55395 X-GNU-PR-Package: emacs Original-Received: via spool by 55395-submit@debbugs.gnu.org id=B55395.165288420617451 (code B ref 55395); Wed, 18 May 2022 14:31:02 +0000 Original-Received: (at 55395) by debbugs.gnu.org; 18 May 2022 14:30:06 +0000 Original-Received: from localhost ([127.0.0.1]:33149 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1nrKgf-0004Wz-OS for submit@debbugs.gnu.org; Wed, 18 May 2022 10:30:06 -0400 Original-Received: from mail1446c50.megamailservers.eu ([91.136.14.46]:44332 helo=mail265c50.megamailservers.eu) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1nrKgd-0004Ts-1C for 55395@debbugs.gnu.org; Wed, 18 May 2022 10:30:04 -0400 X-Authenticated-User: mattiase@bredband.net DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=megamailservers.eu; s=maildub; t=1652884196; bh=AkoR2KV03hTvXBXqJUSLGLi0/mBk6TCyBF4Pc/iYBRg=; h=From:Subject:Date:In-Reply-To:Cc:To:References:From; b=IiQhb9wOumxZVxRBDSnY4TBSYmvGXZ+Pke4alygp/MKkdw3+P/AjQ/iz8MxpclXWC 7fdd68lygqi5ZD8FSq0D2Vcoe4GHvv73F1SYAAq7v4RM0j/cTue9HketiSlk48Mxbn tGLMtIeHObLrZfOWJY/fgUFTqbSqFOVHeZnbtXIM= Feedback-ID: mattiase@acm.or Original-Received: from smtpclient.apple (c188-150-171-71.bredband.tele2.se [188.150.171.71]) (authenticated bits=0) by mail265c50.megamailservers.eu (8.14.9/8.13.1) with ESMTP id 24IETqMf005775; Wed, 18 May 2022 14:29:54 +0000 In-Reply-To: X-Mailer: Apple Mail (2.3654.120.0.1.13) X-CTCH-RefID: str=0001.0A742F1B.628502E4.000E, ss=1, re=0.000, recu=0.000, reip=0.000, cl=1, cld=1, fgs=0 X-CTCH-VOD: Unknown X-CTCH-Spam: Unknown X-CTCH-Score: 0.000 X-CTCH-Flags: 0 X-CTCH-ScoreCust: 0.000 X-Origin-Country: SE X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.18 Precedence: list X-BeenThere: bug-gnu-emacs@gnu.org List-Id: "Bug reports for GNU Emacs, the Swiss army knife of text editors" List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: bug-gnu-emacs-bounces+geb-bug-gnu-emacs=m.gmane-mx.org@gnu.org Original-Sender: "bug-gnu-emacs" Xref: news.gmane.io gmane.emacs.bugs:232577 Archived-At: --Apple-Mail=_9C60AD69-423C-4E73-823B-DAA20C4ABAB0 Content-Transfer-Encoding: quoted-printable Content-Type: text/plain; charset=us-ascii 14 maj 2022 kl. 15.45 skrev Stefan Monnier : > 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. >=20 > 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) =3D> (1 2 3 4 5 5 5 . #3) With the patch: (rho 4 1) =3D> (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=3D(1 . #1#) or #1=3D(1 1 . #1#) and [(1 2 3 . #0)] could mean either [#1=3D(1 2 3 . #1#)] or #1=3D[(1 2 3 . #1#)] but maybe it's less wrong, with room for future improvement? --Apple-Mail=_9C60AD69-423C-4E73-823B-DAA20C4ABAB0 Content-Disposition: attachment; filename=circular-list-print-index.diff Content-Type: application/octet-stream; x-unix-mode=0644; name="circular-list-print-index.diff" Content-Transfer-Encoding: 7bit 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; --Apple-Mail=_9C60AD69-423C-4E73-823B-DAA20C4ABAB0--