1665154 - Lazy regex throws 'Uncaught InternalError: too much recursion' if not matched

Status: RESOLVED INCOMPLETE

(Core :: JavaScript Engine, defect, P3)

Description

[ratchkov]

User Agent: Mozilla/5.0 (Macintosh; Intel Mac OS X 10.14; rv:80.0) Gecko/20100101 Firefox/80.0

Steps to reproduce:

buf = Array(165537).join('x')
/.?module/s.exec(buf+'module') // works fine
/.?module/s.exec(buf) // Throws 'Uncaught InternalError: too much recursion'

Actual results:

The above code throws 'Uncaught InternalError: too much recursion'

Expected results:

Should return null.

Comment 1

[ratchkov]

The original submission ate some of the chars in the regex. Second attempt:

buf = Array(165537).join('x')
/.?module/s.exec(buf+'module') // works fine
/.?module/s.exec(buf) // Throws 'Uncaught InternalError: too much recursion'

Comment 2

[ratchkov]

Submission didn't work again. There is supposed to be a star '*' between the . and the ? in the regex.

Comment 3

[Tooru Fujisawa [:arai]]

You need to enclose code block with triple backquote.
https://guides.github.com/features/mastering-markdown/

buf = Array(165537).join('x')
/.*?module/s.exec(buf+'module') // works fine
/.*?module/s.exec(buf) // Throws 'Uncaught InternalError: too much recursion'

Comment 4

[Tooru Fujisawa [:arai]]

On nightly 82.0a1 (2020-09-15) (64-bit), this behaves differently, that Error: undefined is thrown.
from the following change:
https://hg.mozilla.org/integration/autoland/pushloghtml?fromchange=1fcabd8b2c9ec2ba55ce65124dc694758753efc3&tochange=6ac9edc64fe58b7de451c9a1bd82b673d66ca54d
so there seems to be another error around there.

also, strangely, the issue doesn't happen on JS shell.

Comment 5

[Tooru Fujisawa [:arai]]

looks like it's hitting this case:
https://searchfox.org/mozilla-central/rev/30e70f2fe80c97bfbfcd975e68538cefd7f58b2a/js/src/vm/RegExpObject.cpp#754

that explains why this doesn't happen on JS shell

Comment 6

[Tooru Fujisawa [:arai]]

basically, similar issue as bug 1391654.
once non-backtracking execution gets implemented, the pattern will run quickly.

Comment 7

[Jason Orendorff [:jorendorff]]

I pasted this code into the Chrome devtools, and this regexp makes Chrome unhappy too. With this exact number of characters, Chrome manages to get to the end (after 30 seconds or so) and return null. Then I tried it with buf.repeat(32) and it has gone unresponsive. Quitting Chrome doesn't even work.

Firefox uses V8's Regexp engine, so this requires work on the V8 side.

Comment 8

[Eyal Rozenberg]

I've just filed bug #1677315 today. Is that one a dupe of this one?

Comment 9

[Tooru Fujisawa [:arai]]

yes. but you can workaround this issue by fixing your pattern to correctly match what you want.

Comment 10

[g.vajda]

Hi, I've just run into the same issue with the following regular expression:

/^([a-z0-9]+-?)*[a-z0-9]+$/.test('one-two-three-four-five-six-seven-eight-nine-')

This fails with Uncaught InternalError: too much recursion on the console of Firefox Developer Edition (85.0b7 (64-bit) – Apple M1, MacOS 11.1)

Comment 11

[Iain Ireland [:iain]]

Your pattern results in exponential backtracking. See the "catastrophic backtracking" section of this V8 blog post for an explanation.

The problem is ([a-z0-9]+-?)*, which has an exponential number of potential matches. If you remove the ? in ([a-z0-9]+-?)*, your regexp will match the same inputs but execute much faster.

Comment 12

[g.vajda]

Thank you Iain, that helped a lot!