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

["Mattias Engdegård" <mattiase@acm.org>]

[-- Attachment #1: Type: text/plain, Size: 1194 bytes --]

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?


[-- Attachment #2: 0001-Avoid-regexp-stack-overflow-in-GDB-string-matching-b.patch --]
[-- Type: application/octet-stream, Size: 1234 bytes --]

From 98db2fe313f869fcd146e4accc9e8cb2296468a2 Mon Sep 17 00:00:00 2001
From: =?UTF-8?q?Mattias=20Engdeg=C3=A5rd?= <mattiase@acm.org>
Date: Fri, 13 Mar 2020 19:51:02 +0100
Subject: [PATCH] Avoid regexp stack overflow in GDB string matching
 (bug#22149)

* lisp/progmodes/gdb-mi.el (gdb--string-regexp):
Swap the or-clauses so that the rarely matching one comes first.
This avoids a build-up of backtrack points on the regexp stack.
---
 lisp/progmodes/gdb-mi.el | 5 ++++-
 1 file changed, 4 insertions(+), 1 deletion(-)

diff --git a/lisp/progmodes/gdb-mi.el b/lisp/progmodes/gdb-mi.el
index e785acd284..5533aa000d 100644
--- a/lisp/progmodes/gdb-mi.el
+++ b/lisp/progmodes/gdb-mi.el
@@ -1035,7 +1035,10 @@ gdb-create-define-alist
 
 (declare-function tooltip-show "tooltip" (text &optional use-echo-area))
 
-(defconst gdb--string-regexp "\"\\(?:[^\\\"]\\|\\\\.\\)*\"")
+(defconst gdb--string-regexp (rx "\""
+                                 (* (or (seq "\\" nonl)
+                                        (not (any "\"\\"))))
+                                 "\""))
 
 (defun gdb-tooltip-print (expr)
   (with-current-buffer (gdb-get-buffer 'gdb-partial-output-buffer)
-- 
2.21.1 (Apple Git-122.3)