GNU bug report logs - #54501
Segfault on recursive structure

Previous Next

Full log

Message #22 received at 54501 <at> debbugs.gnu.org (full text, mbox):

From: Mattias Engdegård <mattiase <at> acm.org>
To: Andy Gaynor <goldipox <at> mail.com>
Cc: Lars Ingebrigtsen <larsi <at> gnus.org>, 54501 <at> debbugs.gnu.org,
 Andreas Schwab <schwab <at> linux-m68k.org>,
 Stefan Monnier <monnier <at> iro.umontreal.ca>
Subject: bug#54501: Segfault on recursive structure
Date: Sat, 26 Mar 2022 16:58:53 +0100

[Message part 1 (text/plain, inline)]

> #0=[#1=(#0# . #1#)]

When the reader encounters an expression in the form #N=X, the following steps take place:

1. Create a placeholder value P which is a fresh (nil . nil) cons pair.
2. Assign the number N to P in the read_objects_map.
3. Read X as the value V, where P is used for any occurrences of #N#.
4. Add V to the read_objects_completed set. This is used for future substitutions.
5. Traverse V to replace any occurrence of P with V itself, and return V so modified.

So far all good, but there is an optimisation: if X is a cons, then step 5 is skipped. Instead, since P is already a cons, its CAR and CDR slots are modified to those of V, and P is returned. That way no potentially expensive traversal of V is required.

The alert (human) reader has now spotted the error in the (lisp) reader: step 4 added the now defunct value V to read_objects_completed, not the actually returned value P. The traversal of the outer value, the vector #0 in the above example, will then enter infinite recursion because value #1 was never added to read_objects_completed.

The simplest solution is to remove the optimisation but I'd say it's algorithmically valuable and propose the attached patch.

The patch fixes the #0=#0# nonsense as well since it's a trivial check. Admittedly it doesn't handle #1=#2=#1# -- please keep this bug open if you think it's important.

[0001-Fix-reader-infinite-recursion-for-circular-mixed-typ.patch (application/octet-stream, attachment)]

Previous Next

GNU bug tracking system
Copyright (C) 1999 Darren O. Benham, 1997,2003 nCipher Corporation Ltd, 1994-97 Ian Jackson.