GNU bug report logs - #65726
29.1.50; Crash in regexp engine

Previous Next

Full log

View this message in rfc822 format

From: Stefan Monnier <monnier <at> iro.umontreal.ca>
To: Mattias Engdegård <mattias.engdegard <at> gmail.com>
Cc: martin rudalics <rudalics <at> gmx.at>, Eli Zaretskii <eliz <at> gnu.org>, 65726 <at> debbugs.gnu.org
Subject: bug#65726: 29.1.50; Crash in regexp engine
Date: Fri, 15 Sep 2023 23:45:33 -0400

>> so yes, we may need to remember where we've been. (At this point
>> someone will inevitably point out a helpful invariant that is obvious
>> in hindsight. This is just my cunning attempt at making that happen.)

I think I have a "helpful invariant", finally:

Because of how we build our code, when we're at an `on_failure_jump` the
two branches can either both go forward (typically for a "|" or a "?"),
or *one* of them goes backward the other forward (for loops), where the
one that goes backward (i.e. `p2 <= p2_orig`) is the edge (call it
`p2_loop`) that goes back to the beginning of the loop and the other
(call it `p2_exit`) is the one that exits the loop.

Now, because our loops are nested with proper "structured programming",
there can't be any jump from within the loop to outside the loop except
for the current jump.  And there can't be any jump from outside the loop
to inside the loop except by entering via `p2_loop`.

Since we have two recursive calls to `mutually_exclusive_p` (one for
`p2_exit` and one for `p2_loop`) and each one only needs to check those
positions not checked by the other, we can say that `p2_loop` only needs
to check the positions within the loop (i.e. between `p2_loop` and
`p2_exit`) and can presume that *all* other positions are checked by the
other recursive call (the one that starts at `p2_exit`).

So I think a single arg `done_end` (set, like the current `done_end`, to
`p2_loop` when recursing into `p2_loop`) is indeed sufficient: there's
no way to go from `p2_loop` to before `p2_loop` without first going to
`p2_exit` (which is already checked by the other call).


        Stefan

Previous Next

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