[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
emacs-29 5a864f23eb8: regex-emacs.c: Reduce the use of backtracking a bi
From: |
Stefan Monnier |
Subject: |
emacs-29 5a864f23eb8: regex-emacs.c: Reduce the use of backtracking a bit further |
Date: |
Mon, 20 Feb 2023 21:22:50 -0500 (EST) |
branch: emacs-29
commit 5a864f23eb8a36ef435136c5b41cb01b875df399
Author: Stefan Monnier <monnier@iro.umontreal.ca>
Commit: Stefan Monnier <monnier@iro.umontreal.ca>
regex-emacs.c: Reduce the use of backtracking a bit further
bug#61514 exhibited some undesirable backtracking in a case where
it's easy to avoid it by making `mutually_exclusive_p` just a bit
more careful.
* src/regex-emacs.c (mutually_exclusive_p): Handle `on_failure_jump`s.
* test/src/regex-emacs-tests.el (regexp-tests-backtrack-optimization):
Add a few tests.
---
src/regex-emacs.c | 18 ++++++++++++++++++
test/src/regex-emacs-tests.el | 11 +++++++++++
2 files changed, 29 insertions(+)
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 cd4924f9785..c8f161c9b24 100644
--- a/test/src/regex-emacs-tests.el
+++ b/test/src/regex-emacs-tests.el
@@ -872,4 +872,15 @@ This evaluates the TESTS test cases from glibc."
(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
[Prev in Thread] |
Current Thread |
[Next in Thread] |
- emacs-29 5a864f23eb8: regex-emacs.c: Reduce the use of backtracking a bit further,
Stefan Monnier <=