From: Stefan Monnier via "Bug reports for GNU Emacs, the Swiss army knife of text editors" <bug-gnu-emacs@gnu.org>
To: "Mattias Engdegård" <mattias.engdegard@gmail.com>
Cc: martin rudalics <rudalics@gmx.at>, Eli Zaretskii <eliz@gnu.org>,
65726@debbugs.gnu.org
Subject: bug#65726: 29.1.50; Crash in regexp engine
Date: Mon, 18 Sep 2023 08:32:40 -0400 [thread overview]
Message-ID: <jwvpm2foe9f.fsf-monnier+emacs@gnu.org> (raw)
In-Reply-To: <jwvcyygp526.fsf-monnier+emacs@gnu.org> (Stefan Monnier's message of "Sun, 17 Sep 2023 23:59:32 -0400")
[-- Attachment #1: Type: text/plain, Size: 432 bytes --]
> BTW maybe we should replace
>
> 31: /on_failure_jump_loop to 37
> 34: /jump to 9
>
> with
>
> 31: /on_failure_dont_jump_loop to 9
In the mean time the patch below recognizes the above pattern, which
gives me code which is safe (it should both always terminate and should
never apply the optimization if it's not valid) yet does find the
optimization in all the cases where I expected it.
Stefan
[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #2: regexp.c.patch --]
[-- Type: text/x-diff, Size: 8140 bytes --]
diff --git a/src/regex-emacs.c b/src/regex-emacs.c
index 55d0a6e8df8..e45d0f19dbf 100644
--- a/src/regex-emacs.c
+++ b/src/regex-emacs.c
@@ -1923,12 +1923,22 @@ regex_compile (re_char *pattern, ptrdiff_t size,
if (!zero_times_ok && simple)
{ /* Since simple * loops can be made faster by using
- on_failure_keep_string_jump, we turn simple P+
- into PP* if P is simple. */
+ on_failure_keep_string_jump, we turn P+ into PP*
+ if P is simple.
+ We can't use `top: <BODY>; OFJS exit; J top; exit:`
+ Because the OFJS needs to be at the beginning
+ since we want to be able to replace
+ `top: OFJS exit; <BODY>; J top; exit`
+ with
+ `top: OFKSJ exit; loop: <BODY>; J loop; exit`,
+ i.e. a single OFJ at the beginning of the loop
+ rather than once per iteration. */
unsigned char *p1, *p2;
startoffset = b - laststart;
GET_BUFFER_SPACE (startoffset);
p1 = b; p2 = laststart;
+ /* This presumes that the code skipped
+ by `skip_one_char` is position-independent. */
while (p2 < p1)
*b++ = *p2++;
zero_times_ok = 1;
@@ -3068,8 +3078,10 @@ analyze_first (re_char *p, re_char *pend, char *fastmap, bool multibyte)
continue;
case succeed_n:
- /* If N == 0, it should be an on_failure_jump_loop instead. */
- DEBUG_STATEMENT (EXTRACT_NUMBER (j, p + 2); eassert (j > 0));
+ /* If N == 0, it should be an on_failure_jump_loop instead.
+ `j` can be negative because `EXTRACT_NUMBER` extracts a
+ signed number whereas `succeed_n` treats it as unsigned. */
+ DEBUG_STATEMENT (EXTRACT_NUMBER (j, p + 2); eassert (j != 0));
p += 4;
/* We only care about one iteration of the loop, so we don't
need to consider the case where this behaves like an
@@ -3743,20 +3755,20 @@ mutually_exclusive_charset (struct re_pattern_buffer *bufp, re_char *p1,
}
/* True if "p1 matches something" implies "p2 fails". */
-/* Avoiding inf-loops:
- We're trying to follow all paths reachable from `p2`, but since some
+/* We're trying to follow all paths reachable from `p2`, but since some
loops can match the empty string, this can loop back to `p2`.
- To avoid inf-looping, we keep track of points that have been considered
- "already". Instead of keeping a list of such points, `done_beg` and
- `done_end` delimit a chunk of bytecode we already considered.
- To guarantee termination, a lexical ordering between `done_*` and `p2`
- should be obeyed:
- At each recursion, either `done_beg` gets smaller,
- or `done_beg` is unchanged and `done_end` gets larger
- or they're both unchanged and `p2` gets larger. */
+ To avoid inf-looping, we take advantage of the fact that
+ the bytecode we generate is made of syntactically nested loops, more
+ specifically, every loop has a single entry point and single exit point.
+ The function takes 2 more arguments (`loop_entry` and `loop_exit`).
+ `loop_entry` points to the sole entry point of the current loop and
+ `loop_exit` points to its sole exit point (when non-NULL).
+ The function can assume that `loop_exit` is "mutually exclusive".
+ Termination of recursive calls is ensured because either `loop_entry`
+ is larger, or it's equal but `p2` is larger. */
static bool
mutually_exclusive_aux (struct re_pattern_buffer *bufp, re_char *p1,
- re_char *p2, re_char *done_beg, re_char *done_end)
+ re_char *p2, re_char *loop_entry, re_char *loop_exit)
{
re_opcode_t op2;
unsigned char *pend = bufp->buffer + bufp->used;
@@ -3765,8 +3777,23 @@ mutually_exclusive_aux (struct re_pattern_buffer *bufp, re_char *p1,
eassert (p1 >= bufp->buffer && p1 < pend
&& p2 >= bufp->buffer && p2 <= pend);
- eassert (done_beg <= done_end);
- eassert (done_end <= p2);
+ if (p2 == loop_exit)
+ /* Presumably already checked elsewhere. */
+ return true;
+ eassert (loop_entry && p2 >= loop_entry);
+ /* eassert (!loop_exit || p2 < loop_exit); */
+ if (p2 < loop_entry)
+ return false;
+ if (loop_exit && p2 > loop_exit)
+ {
+ void print_compiled_pattern (struct re_pattern_buffer *bufp);
+ print_compiled_pattern (bufp);
+ fprintf (stderr, "p1==%d, p2==%d, loop-entry==%d, loop-exit==%d\n",
+ p1 - bufp->buffer, p2 - bufp->buffer,
+ loop_entry - bufp->buffer, loop_exit - bufp->buffer);
+ error ("WOW1!");
+ }
+ /* return false; */
/* Skip over open/close-group commands.
If what follows this loop is a ...+ construct,
@@ -3859,28 +3886,40 @@ mutually_exclusive_aux (struct re_pattern_buffer *bufp, re_char *p1,
p2++;
EXTRACT_NUMBER_AND_INCR (mcnt, p2);
re_char *p2_other = p2 + mcnt;
+ /* For `+` loops, we often have an `on_failure_jump` that skips forward
+ over a subsequent `jump` for lack of an `on_failure_dont_jump`
+ kind of thing. Recognize this pattern since that subsequent
+ `jump` is the one that jumps to the loop-entry. */
+ if ((re_opcode_t) p2[0] == jump && mcnt == 3)
+ {
+ EXTRACT_NUMBER (mcnt, p2 + 1);
+ p2 += mcnt + 3;
+ }
- /* When we jump backward we bump `done_end` up to `p3` under
- the assumption that any other position between `done_end`
- and `p3` is either:
- - checked by the other call to RECURSE.
- - not reachable from here (e.g. for positions before the
- `on_failure_jump`), or at least not without first
- jumping before `done_beg`.
- This should hold because our state machines are not arbitrary:
- they consists of syntaxically nested loops with limited
- control flow.
- FIXME: This can fail (i.e. return true when it shouldn't)
- if we start generating bytecode with a different shape,
- so maybe we should bite the bullet and replace done_beg/end
- with an actual list of positions we've already processed. */
-#define RECURSE(p3) \
- ((p3) < done_beg ? mutually_exclusive_aux (bufp, p1, p3, p3, p3) \
- : (p3) <= done_end ? true \
- : mutually_exclusive_aux (bufp, p1, p3, done_beg, \
- (p3) > p2_orig ? done_end : (p3)))
-
- return RECURSE (p2) && RECURSE (p2_other);
+ /* If we jump backward to the entry point of the current loop
+ it means it's a zero-length cycle through that loop, so
+ this cycle itself does not break mutual-exclusion.
+ If we jump backward to a new loop nested within the current one
+ then the `p2_other` points to the exit of that inner loop
+ and the other RECURSE will check what happens when we leave
+ the loop so we can focus on checking just the loop body,
+ so we pass new values for `loop-entry` and `loop_exit`.
+ In all other cases, we just recurse "normally": if it's before
+ `loop_entry` it's a bug that will be caught by checks at
+ the entrace of the function and otherwise it's a forward jump
+ which doesn't need any special treatment.
+ FIXME: This is failsafe (can't return true when it shouldn't)
+ but it could be too conservative if we start generating bytecode
+ with a different shape, so maybe we should bite the bullet and
+ replace done_beg/end with an actual list of positions we've
+ already processed. */
+#define RECURSE(p3, p3_other) \
+ ((p3) == loop_entry ? true \
+ : loop_entry < (p3) && (p3) < p2_orig && (p3_other) > p2_orig ? \
+ mutually_exclusive_aux (bufp, p1, p3, p3, p3_other) \
+ : mutually_exclusive_aux (bufp, p1, p3, loop_entry, loop_exit))
+
+ return RECURSE (p2, p2_other) && RECURSE (p2_other, p2);
}
default:
@@ -3895,7 +3934,7 @@ #define RECURSE(p3) \
mutually_exclusive_p (struct re_pattern_buffer *bufp, re_char *p1,
re_char *p2)
{
- return mutually_exclusive_aux (bufp, p1, p2, p2, p2);
+ return mutually_exclusive_aux (bufp, p1, p2, bufp->buffer, NULL);
}
\f
/* Matching routines. */
next prev parent reply other threads:[~2023-09-18 12:32 UTC|newest]
Thread overview: 36+ messages / expand[flat|nested] mbox.gz Atom feed top
2023-09-04 7:46 bug#65726: 29.1.50; Crash in regexp engine martin rudalics
2023-09-04 8:44 ` Mattias Engdegård
2023-09-04 12:12 ` Eli Zaretskii
2023-09-04 13:18 ` Mattias Engdegård
2023-09-04 13:26 ` Mattias Engdegård
2023-09-04 13:28 ` Eli Zaretskii
2023-09-04 15:47 ` Mattias Engdegård
2023-09-05 12:23 ` Mattias Engdegård
2023-09-05 13:08 ` Stefan Monnier via Bug reports for GNU Emacs, the Swiss army knife of text editors
2023-09-05 13:50 ` Mattias Engdegård
2023-09-05 15:33 ` Stefan Monnier via Bug reports for GNU Emacs, the Swiss army knife of text editors
2023-09-06 12:03 ` Mattias Engdegård
2023-09-09 15:55 ` Stefan Monnier via Bug reports for GNU Emacs, the Swiss army knife of text editors
2023-09-09 16:34 ` Mattias Engdegård
2023-09-14 14:41 ` Stefan Monnier via Bug reports for GNU Emacs, the Swiss army knife of text editors
2023-09-15 20:03 ` Mattias Engdegård
2023-09-15 22:20 ` Stefan Monnier via Bug reports for GNU Emacs, the Swiss army knife of text editors
2023-09-16 3:45 ` Stefan Monnier via Bug reports for GNU Emacs, the Swiss army knife of text editors
2023-09-16 10:49 ` Mattias Engdegård
2023-09-16 15:48 ` Stefan Monnier via Bug reports for GNU Emacs, the Swiss army knife of text editors
2023-09-18 2:14 ` Stefan Monnier via Bug reports for GNU Emacs, the Swiss army knife of text editors
2023-09-18 3:59 ` Stefan Monnier via Bug reports for GNU Emacs, the Swiss army knife of text editors
2023-09-18 12:32 ` Stefan Monnier via Bug reports for GNU Emacs, the Swiss army knife of text editors [this message]
2023-09-21 17:23 ` Mattias Engdegård
2023-09-21 18:08 ` Stefan Monnier via Bug reports for GNU Emacs, the Swiss army knife of text editors
2023-09-23 11:56 ` Mattias Engdegård
2023-09-04 14:32 ` Stefan Monnier via Bug reports for GNU Emacs, the Swiss army knife of text editors
2023-09-04 15:57 ` Eli Zaretskii
2023-09-04 17:12 ` Stefan Monnier via Bug reports for GNU Emacs, the Swiss army knife of text editors
2023-09-10 7:50 ` Stefan Kangas
2023-09-10 7:55 ` Eli Zaretskii
2023-09-10 23:09 ` Stefan Monnier via Bug reports for GNU Emacs, the Swiss army knife of text editors
2023-09-11 14:46 ` Stefan Kangas
2023-09-05 7:14 ` martin rudalics
2023-09-11 8:10 ` Mattias Engdegård
2023-09-11 13:41 ` Stefan Monnier via Bug reports for GNU Emacs, the Swiss army knife of text editors
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
List information: https://www.gnu.org/software/emacs/
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=jwvpm2foe9f.fsf-monnier+emacs@gnu.org \
--to=bug-gnu-emacs@gnu.org \
--cc=65726@debbugs.gnu.org \
--cc=eliz@gnu.org \
--cc=mattias.engdegard@gmail.com \
--cc=monnier@iro.umontreal.ca \
--cc=rudalics@gmx.at \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
Code repositories for project(s) associated with this public inbox
https://git.savannah.gnu.org/cgit/emacs.git
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).