GNU bug report logs - #61514
30.0.50; sadistically long xml line hangs emacs

Previous Next

Full log

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

From: Stefan Monnier <monnier <at> iro.umontreal.ca>
To: Gregory Heytings <gregory <at> heytings.org>
Cc: Eli Zaretskii <eliz <at> gnu.org>, 61514 <at> debbugs.gnu.org, mah <at> everybody.org
Subject: Re: bug#61514: 30.0.50; sadistically long xml line hangs emacs
Date: Mon, 20 Feb 2023 13:49:49 -0500

> where I can even reduce the regexp down to "[-._[:alnum:]]*\t*=".
> Looks like we're missing a case in our backtracking-elimination code.

The patch below fixes the stack overflow.
[ And thanks Gregory for the yet simpler test cases.  ]

I don't think we want that for `emacs-29`, but unless there's some
objection I'll push this to `master`,


        Stefan


diff --git a/src/regex-emacs.c b/src/regex-emacs.c
index 2dca0d16ad9..2571812cb39 100644
--- a/src/regex-emacs.c
+++ b/src/regex-emacs.c
@@ -3653,6 +3653,7 @@ mutually_exclusive_p (struct re_pattern_buffer *bufp, re_char *p1,
   re_opcode_t op2;
   bool multibyte = RE_MULTIBYTE_P (bufp);
   unsigned char *pend = bufp->buffer + bufp->used;
+  re_char *p2_orig = p2;
 
   eassert (p1 >= bufp->buffer && p1 < pend
 	   && p2 >= bufp->buffer && p2 <= pend);
@@ -3822,6 +3823,23 @@ mutually_exclusive_p (struct re_pattern_buffer *bufp, re_char *p1,
     case notcategoryspec:
       return ((re_opcode_t) *p1 == categoryspec && p1[1] == p2[1]);
 
+    case on_failure_jump_nastyloop:
+    case on_failure_jump_smart:
+    case on_failure_jump_loop:
+    case on_failure_keep_string_jump:
+    case on_failure_jump:
+      {
+        int mcnt;
+	p2++;
+	EXTRACT_NUMBER_AND_INCR (mcnt, p2);
+	/* Don't just test `mcnt > 0` because non-greedy loops have
+	   their test at the end with an unconditional jump at the start.  */
+	if (p2 + mcnt > p2_orig) /* Ensure forward progress.  */
+	  return (mutually_exclusive_p (bufp, p1, p2)
+		  && mutually_exclusive_p (bufp, p1, p2 + mcnt));
+	break;
+      }
+
     default:
       ;
     }
diff --git a/test/src/regex-emacs-tests.el b/test/src/regex-emacs-tests.el
index 34fa35e32ff..52d43775b8e 100644
--- a/test/src/regex-emacs-tests.el
+++ b/test/src/regex-emacs-tests.el
@@ -872,4 +872,15 @@ regexp-atomic-failure
   (should (equal (string-match "\\`\\(?:ab\\)*\\'" "a") nil))
   (should (equal (string-match "\\`a\\{2\\}*\\'" "a") nil)))
 
+(ert-deftest regexp-tests-backtrack-optimization () ;bug#61514
+  ;; Make sure we don't use up the regexp stack needlessly.
+  (with-current-buffer (get-buffer-create "*bug*")
+    (erase-buffer)
+    (insert (make-string 1000000 ?x) "=")
+    (goto-char (point-min))
+    (should (looking-at "x*=*"))
+    (should (looking-at "x*\\(=\\|:\\)"))
+    (should (looking-at "x*\\(=\\|:\\)*"))
+    (should (looking-at "x*=*?"))))
+
 ;;; regex-emacs-tests.el ends here

Previous Next

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