Subject: bug#65726: 29.1.50; Crash in regexp engine

From: Stefan Monnier <[email-masked]>
Date: Mon, 04 Sep 2023 10:32:38 -0400

> Python Exception <class 'gdb.MemoryError'> Cannot access memory at address 0x7fffff66fff8:
> #0  0x000000000068810a in skip_noops (p=#1  0x0000000000688823 in mutually_exclusive_p (bufp=0xec9c30 <searchbufs+752>, p1=0x1fcee74 "\004\005", p2=0x1fcee81 "\016\063") at ../../src/regex-emacs.c:3665
> #2  0x0000000000688e19 in mutually_exclusive_p (bufp=0xec9c30 <searchbufs+752>, p1=0x1fcee74 "\004\005", p2=0x1fcee81 "\016\063") at ../../src/regex-emacs.c:3838
> #3  0x0000000000688e3c in mutually_exclusive_p (bufp=0xec9c30 <searchbufs+752>, p1=0x1fcee74 "\004\005", p2=0x1fceeba "\004\020") at ../../src/regex-emacs.c:3839
> #4  0x0000000000688e3c in mutually_exclusive_p (bufp=0xec9c30 <searchbufs+752>, p1=0x1fcee74 "\004\005", p2=0x1fcee84 "\002\001@\004\020") at ../../src/regex-emacs.c:3839
> #5  0x0000000000688e19 in mutually_exclusive_p (bufp=0xec9c30 <searchbufs+752>, p1=0x1fcee74 "\004\005", p2=0x1fcee81 "\016\063") at ../../src/regex-emacs.c:3838
> ...

Hmm... the line numbers strongly suggests the inf-recursion happens via
the calls:

    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;
      }

Re-reading the code I see that `skip_noops` can return a position
smaller than its argument, which makes it possible for `p2` to
be smaller (or equal) to `p2_orig` and hence explain that inf-loop
(that's the only path I can see that explains the inf-loop you're
seeing).

So, the patch below should hopefully fix your problem.

        Stefan

diff --git a/src/regex-emacs.c b/src/regex-emacs.c
index 7e75f0ac597..3a14c10771d 100644
--- a/src/regex-emacs.c
+++ b/src/regex-emacs.c
@@ -3832,7 +3832,8 @@ mutually_exclusive_p (struct re_pattern_buffer *bufp, re_char *p1,
 	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.  */
+	if (p2 + mcnt > p2_orig /* Ensure forward progress.  */
+	    && p2 > p2_orig)    /* Bug#65726  */
 	  return (mutually_exclusive_p (bufp, p1, p2)
 		  && mutually_exclusive_p (bufp, p1, p2 + mcnt));
 	break;