This simply regular expression is really slow, why?

Question

I have written this really simple regular expression which checks if the whole string represents one or more hexadecimal numbers (optionally starting with "0x", separated by comma, minus sign or a whitespace character):

/^((0x)?[0-9A-F]+[,\-\s]*)+$/i

To me, this regex is very straightforward, but this simple test crashs Firefox and Edge at all, Chrome takes 100% CPU usage for about 15 seconds and then returns the expected result "false":

/^((0x)?[0-9A-F]+[,\-\s]*)+$/i.test("012345678901234567890123456789_0");

Has anyone an idea what's wrong here?

Possible duplicate of [Why does this take so long to match? Is it a bug?](http://stackoverflow.com/questions/25982466/why-does-this-take-so-long-to-match-is-it-a-bug) — Mazdak, Apr 01 '17 at 07:42

score 3 · Accepted Answer · answered Mar 31 '17 at 09:20

It is a usual case of a catastrophic backtracking (see your regex demo) when a group contains two subpatterns with one of them being optional.

You need to regroup the pattern as

/^(?:0x)?[0-9A-F]+(?:[,\s-]+(?:0x)?[0-9A-F]+)*$/i

Now, it will match:

^ - start of string
(?:0x)?[0-9A-F]+ - hex number
(?:[,\s-]+(?:0x)?[0-9A-F]+)* - zero or more sequences of
- [,\s-]+ - 1+ space, , or - symbols (remove + if only 1 must be matched)
- (?:0x)?[0-9A-F]+ - hex number
$ - end of string.

See the regex demo.

This simply regular expression is really slow, why?

1 Answers1