Subject: bug#54501: Segfault on recursive structure

From: Mattias Engdegård <[email-masked]>
Date: Sat, 26 Mar 2022 16:58:53 +0100

> #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.