Subject: bug#22149: 24.4; gdb stack overflow in regexp matcher

From: Mattias Engdegård <[email-masked]>
Date: Fri, 13 Mar 2020 19:58:23 +0100

This was a while ago, but the effect can still be observed in current master (28.0.50). The exact reproduction no longer works but it's probably just a quantitive change; perhaps the regexp stack has become bigger.

Simplified, and with some character renaming for clarity, the test case is essentially

(string-match (rx "t"
                  (* (or (not (any "bq"))
                         (: "b" nonl)))
                  "q")
              (concat "t" (make-string 160000 ?a)))

where the number 160000 can be lowered a bit to avoid the stack overflow.

One way of dodging the error regardless of string size is to swap the two 'or' operands, so that the (: "b" nonl) part, which usually fails, is attempted first. This is because the NFA matcher implements a kind of TCO: no backtrack point on the stack is needed for the last or-clause.

In fact, Noam's proposed workaround, equivalent to

(string-match (rx "t"
                  (* (or "bq" (not "b")))
                  "q")
              (concat "t" (make-string 160000 ?a)))

works precisely for this reason -- swapping the or-clauses here gives a stack overflow again.

What about this patch for Emacs 27?