GNU bug report logs - #22149
stack overflow in regexp matcher

Previous Next

Full log

Message #20 received at 22149 <at> debbugs.gnu.org (full text, mbox):

From: Mattias Engdegård <mattiase <at> acm.org>
To: Noam Postavsky <npostavs <at> gmail.com>
Cc: Andreas Schwab <schwab <at> suse.de>, Cheng-An Yang <rhymer123 <at> gmail.com>,
 22149 <at> debbugs.gnu.org
Subject: Re: bug#22149: 24.4; gdb stack overflow in regexp matcher
Date: Fri, 13 Mar 2020 19:58:23 +0100

[Message part 1 (text/plain, inline)]

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 (application/octet-stream, attachment)]

Previous Next

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