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

From: Mattias Engdegård <[email-masked]>
Date: Mon, 4 Sep 2023 17:47:04 +0200

Minimised reproduction recipe:

  (string-match (rx (* "a") (* (* "b"))) "a")

(Don't worry about the nested stars; the original was more like (* (| A (* B))).)

The generated bytecode is:

    0  on-failure-jump-smart to 9
    3  exact "a"
    6  jump to 0
    9  on-failure-jump-loop to 24
   12  on-failure-jump-smart to 21
   15  exact "b"
   18  jump to 12
   21  jump to 9
   24  succeed

which suggests a mutual_exclusive_p recursion loop:

  mep(3,9)
  -> mep(3,12)
     -> mep(3,21) = {skip_noop} = mep(3,9)
        -> mep(3,12)
           ...

Maybe there is something clever we could do here but it's possible that we just can't avoid keeping track of visited nodes.