Breaks with "catastrophic backtracking" (caused by a poorly made regex that has a huge number of iterations)

[jmortiger]

When testing the regex /(^(?:\w+\s*)*)(?<=:)((?:\w+\s*)*)/gm with the following tester text file:

The Legend of Zelda: Ocarina of Time
Tony Hawk's Pro Skater 2
Grand Theft Auto IV
Disco Elysium: The Final Cut
The Legend of Zelda: Breath of the Wild
Perfect Dark
Red Dead Redemption 2
Grand Theft Auto V
Halo: Combat Evolved
NFL 2K1
Half-Life 2
The Legend of Zelda: Breath of the Wild
Uncharted 2: Among Thieves
Resident Evil 4
Batman: Arkham City
The House in Fata Morgana - Dreams of the Revenants Edition -
The Legend of Zelda: Twilight Princess
Elden Ring
The Elder Scrolls V: Skyrim
Persona 5 Royal
Half-Life
Metal Gear Solid 2: Sons of Liberty
Baldur's Gate II: Shadows of Amn
Grand Theft Auto: San Andreas

the extension became unresponsive. The "Not adding /gm" message on the bottom bar wasn't reacting when the shortcut was pressed nor when clicked directly (tooltip and hover animation worked, clicking did nothing) and the "Test Regex..." inline stopped responding (sometimes with no highlighting on mouseover and consistently no reaction when clicked). The preview stops updating with the regex, even if the regex is changed to a prior version that caused no problems (like (^(?:\w+\s*)*)), or even to a simple /\w/gm. Hovering over the preview displays a Loading... tooltip. If there were previous matches in the preview (from a successful prior version of my regex, which I'm editing while the preview is open), they remain, but don't respond to regex changes. While in this state, changing the contents of the preview behaves as follows:

• Deleting unmatched characters following the end of a match (in a way that would cause the remainder of the line to successfully match the regex whose results are still displayed) does not correctly add those pre-existing characters to the match.
• Adding text at the start, end, or inside a match will cause the inserted text to be highlighted as included in the match, regardless of whether or not it should match the regex (either as it was or as it is). For example, a : shouldn't match the successful prior regex (/\w/gm) nor the current buggy regex ((^(?:\w+\s*)*)(?<=:)((?:\w+\s*)*)/gm), but if added inside or at the ends of a cached successful match (i.e. The Legend of Zelda), it will be included.
• It behaves as though it's tracking the beginning and end of highlighted text, and any direct additions are included, and no regard to the regex is given.

It appears that, after waiting for an extremely long time, the extension stops hanging, and normal functionality is restored, but I'm not waiting again to verify this.

To Replicate:

1. Place a working regex in an editor window (I'd recommend (^(?:\w+\s*)*)).
2. Initiate the preview tester (Click "Test Regex", use the shortcut, don't think it matters how).
3. Replace the default preview text with the example above. (Maybe trim a few lines to see if you can reduce the hangtime while testing??? The unresponsive state should theoretically occur with just the first line in place.)
4. Modify the regex to one that has catastrophic backtracking, either by copy-pasting or manually typing it in. (Again, mine was (^(?:\w+\s*)*)(?<=:)((?:\w+\s*)*)/gm)

To (Temporarily) Resolve:

1. Modify the troublesome regex to a working one.
2. Either:
   A. Reload the window (Ctrl + R or Ctrl + Shift + P, "Reload Window"); or
   B. Wait an unknown yet significant amount of time for it to (presumably) work through its workload and then move on to the new version.

Please allow me to be a bit egotistical and offer some suggestions for fixes:

• Listen for specific events and use them to cancel the prior parse job and start the new one. This has the added bonus of allowing long files or poorly optimized regexs to try to complete, while allowing the operation to be cancelled at anytime if need be. I'd recommend:
  • When the bottom bar button is pressed
  • When the shortcut is toggled off
  • When the previewed regex is modified
• Cancel attempted parse after x iterations and display a notification alerting the user

[jmortiger]

This might be related to Extension causes high cpu load #36.