Re: Circular records: how do I best handle them? (The new correct warning position branch now bootstraps in native compilation!)

[Alan Mackenzie <acm@muc.de>]

Hello, Stefan.

On Fri, Dec 24, 2021 at 08:56:56 -0500, Stefan Monnier wrote:
> > The recursion was in the (new) function `byte-compile-strip-s-p-1'
> > (where "strip-s-p" stands for "strip-symbol-positions").  This function
> > recursively descends list and vector structures, stripping positions
> > from symbols-with-position it finds.

> > However, I seem to have circularity in a record structure, where two
> > records seem to point to eachother.  I suspect that it is the zeroth
> > elements of these records (which are meant to be symbols) that are
> > pointing at eachother.

> Hmm... circularity is quite normal in data structures, yes.
> But presumably this is only applied to source code where circularity is
> very rare.  Could it be that you end up recursing in elements which
> actually aren't part of the source code (and hence can't have
> symbols-with-positions)?

I honestly don't know at the moment.

> Also, I see in `byte-compile-strip-s-p-1` that you only look inside conses
> and vectors.  So I'm not sure what makes you say the recursion was in
> records since records are similar to vectors but aren't `vectorp` so
> AFAICT your code won't recurse into them.

byte-compile-strip-s-p-1 has been enhanced to handle records, too,
though I haven't committed that bit yet (along with quite a lot of other
amendments, too).

> Also that means your code won't handle the case where the source code
> includes literal hash-tables, literal records, literal char-tables,
> literal strings-with-properties, ...

The positions get stripped off hash-table keys in puthash.  I'm unsure
about the others, just offhand.

Put it this way, make bootstrap is currently working, although a bit
delicate.  My preliminary timings on a benchmark are as fast as
expected, so it's looking good.

> These are quite rare and maybe it's OK to disallow them in source code,
> but maybe a more robust approach would be to make sure your lread.c code
> doesn't generate symbols-with-positions within anything else than conses
> and vectors?
> [ Tho it wouldn't prevent a macro from expanding into a literal hash-table
>   from source that only has conses&vectors :-(  ]

> > Would somebody (?Stefan M, perhaps) please suggest to me how I might
> > efficiently cope with these circular structures.  Do I need to maintain
> > a list of already encountered Lisp Objects, somehow, and check this list
> > before recursing into the function?

> That's what we do elsewhere, yes, except that history taught us that
> a hash-table is a better choice to avoid scalability problems.
> Tho in your case you'd only need to keep the stack of objects inside of
> which you're currently recursing, so maybe a list is good enough.

I've tried the list approach (using memq to check for an already
processed cons/vector/record.  It fell flat on its face with
lisp/leim/ja-dic/ja-dec.el, which has a list with over 60,000 strings in
it.  I Ctrl-C'd out of this after five minutes, and it took me a while
to establish I didn't have an infinite loop; not quite.

So I disabled the checking for circularity in conses, leaving it in for
vectors and records.  That's what I meant when I said "a bit delicate"
above.  There's nothing to stop somebody building a circular list in a
source file.  Maybe the way to handle this would be to allow it to hit
max-lisp-eval-depth, catch the error, then turn on the circularity
detector and try again.  Circular lists in source code are surely rare.
Large circular lists must be rarer still.

> BTW, instead of doing it by hand, you can call `print--preprocess` which
> will do the recurse-and-fill-hash-table for you.  You can see how it's
> used in `cl-print.el`.

Thanks, I'll have a closer look at this, probably in a few days time.

Have a good tomorrow!

>         Stefan

-- 
Alan Mackenzie (Nuremberg, Germany).