regular expression very slow on fail

Question

I've a regular expression that should validate if a string is composed by space-delimited strings. The regular expression works well (ok it allows a empty space in the end ... but that's not he problem) but takes too long when the validation fails.

The regular expression is the following:

/^(([\w\-]+)( )?){0,}$/

When trying to validate with the string

"'this-is_SAMPLE-scope-123,this-is_SAMPLE-scope-456'"

it takes 2 seconds.

The tests were performed in ruby 1.9.2-rc1 and 1.8.7. But this is probably a general problem.

Any idea?

Answer 1

Your pattern causes catastrophic backtracking. The catastrophic part can be summarized to this:

(.+)*

The + and the * interacts in catastrophic ways in some engines.

It's unclear what you're trying to match, exactly, but it may be something like this:

^[\w\-]+( [\w\-]+)*$

This matches (as seen on rubular.com):

hello world
99 bottles of beer on the wall
this_works_too

and rejects:

not like this, not like this
hey what the &#@!
too many    spaces

Another option would be to use possessive quantifiers and/or atomic groupings in parts of the original pattern.

References

• regular-expressions.info/Possessive quantifiers and Atomic grouping

---

Additional tips

The {0,} repetition is usually written simply as *. You can also use non-capturing groups to improve performance, i.e. (?:pattern).

References

• regular-expressions.info/Brackets for Capturing and Repetition with Star and Plus

Related questions

• Using explicitly numbered repetition instead of question mark, star and plus