bug#18577: Regexp I-search: [(error Stack overflow in regexp matcher)]

[Stefan Kangas <stefan@marxist.se>]

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

Eli Zaretskii <eliz@gnu.org> writes:

> Would it be possible to copy the relevant recommendations from that
> discussion to the PROBLEMS entry?  If shown in a cookbook manner, that
> could be very helpful in practice, I think.

How about this?

[-- Attachment #2: 0001-etc-PROBLEMS-Mention-problems-with-regexp-engine.-Bu.patch --]
[-- Type: text/x-diff, Size: 1300 bytes --]

From 91db453ff2236bae5c73c0f42b105737532206de Mon Sep 17 00:00:00 2001
From: Stefan Kangas <stefan@marxist.se>
Date: Sat, 23 Oct 2021 10:29:30 +0200
Subject: [PATCH] * etc/PROBLEMS: Mention problems with regexp engine. 
 (Bug#18577)

---
 etc/PROBLEMS | 12 ++++++++++++
 1 file changed, 12 insertions(+)

diff --git a/etc/PROBLEMS b/etc/PROBLEMS
index ede83a6e7c..daff102a0d 100644
--- a/etc/PROBLEMS
+++ b/etc/PROBLEMS
@@ -742,6 +742,18 @@ completed" message that tls.el relies upon, causing affected Emacs
 functions to hang.  To work around the problem, use older or newer
 versions of gnutls-cli, or use Emacs's built-in gnutls support.
 
+*** Stack overflow in regexp matcher.
+Due to fundamental limitations in the way Emacs' regular expression
+engine is designed, you might run into combinatorial explosions in
+backtracking with certain regexps.
+
+Avoid "\(...\(...\)*...\)*" and "\(...\)*\(...\)*".  Look for a way to
+anchor your regular expression, to avoid matching the null string in
+infinite ways.  The latter is what creates backtrack points, and
+eventual overflow in practice.
+
+(Also prefer "\(?:...\)" to "\(...\)" unless you need the latter.)
+
 * Runtime problems related to font handling
 
 ** Characters are displayed as empty boxes or with wrong font under X.
-- 
2.30.2