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

[Mattias Engdegård]

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?

0001-Avoid-regexp-stack-overflow-in-GDB-string-matching-b.patch
Description: Binary data