[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

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

From: Mattias Engdegård
Subject: bug#22149: 24.4; gdb stack overflow in regexp matcher
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 

(string-match (rx "t"
                  (* (or (not (any "bq"))
                         (: "b" nonl)))
              (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")))
              (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?

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

reply via email to

[Prev in Thread] Current Thread [Next in Thread]