I'm trying to use a URL matching regular expression that I got from

(?xi)
\b
(                       # Capture 1: entire matched URL
  (?:
    https?://               # http or https protocol
    |                       #   or
    www\d{0,3}[.]           # "www.", "www1.", "www2." … "www999."
    |                           #   or
    [a-z0-9.\-]+[.][a-z]{2,4}/  # looks like domain name followed by a slash
  )
  (?:                       # One or more:
    [^\s()<>]+                  # Run of non-space, non-()<>
    |                           #   or
    \(([^\s()<>]+|(\([^\s()<>]+\)))*\)  # balanced parens, up to 2 levels
  )+
  (?:                       # End with:
    \(([^\s()<>]+|(\([^\s()<>]+\)))*\)  # balanced parens, up to 2 levels
    |                               #   or
    [^\s`!()\[\]{};:'".,<>?«»“”‘’]        # not a space or one of these punct chars
  )
)

Based on the answers to another question, it appears that there are cases that cause this regex to backtrack catastrophically. For example:

var re = /\b((?:https?:\/\/|www\d{0,3}[.]|[a-z0-9.\-]+[.][a-z]{2,4}\/)(?:[^\s()<>]+|\(([^\s()<>]+|(\([^\s()<>]+\)))*\))+(?:\(([^\s()<>]+|(\([^\s()<>]+\)))*\)|[^\s`!()\[\]{};:'".,<>?«»“”‘’]))/i;
re.test("/?q=(AAAAAAAAAAAAAAAAAAAAAAAAAAAAA)")

... can take a really long time to execute (e.g. in Chrome)

It seems to me that the problem lies in this part of the code:

(?:                       # One or more:
    [^\s()<>]+                  # Run of non-space, non-()<>
    |                           #   or
    \(([^\s()<>]+|(\([^\s()<>]+\)))*\)  # balanced parens, up to 2 levels
  )+

... which seems to be roughly equivalent to (.+|\((.+|(\(.+\)))*\))+, which looks like it contains (.+)+

Is there a change I can make that will avoid that?

I'm trying to use a URL matching regular expression that I got from http://daringfireball/2010/07/improved_regex_for_matching_urls

(?xi)
\b
(                       # Capture 1: entire matched URL
  (?:
    https?://               # http or https protocol
    |                       #   or
    www\d{0,3}[.]           # "www.", "www1.", "www2." … "www999."
    |                           #   or
    [a-z0-9.\-]+[.][a-z]{2,4}/  # looks like domain name followed by a slash
  )
  (?:                       # One or more:
    [^\s()<>]+                  # Run of non-space, non-()<>
    |                           #   or
    \(([^\s()<>]+|(\([^\s()<>]+\)))*\)  # balanced parens, up to 2 levels
  )+
  (?:                       # End with:
    \(([^\s()<>]+|(\([^\s()<>]+\)))*\)  # balanced parens, up to 2 levels
    |                               #   or
    [^\s`!()\[\]{};:'".,<>?«»“”‘’]        # not a space or one of these punct chars
  )
)

Based on the answers to another question, it appears that there are cases that cause this regex to backtrack catastrophically. For example:

var re = /\b((?:https?:\/\/|www\d{0,3}[.]|[a-z0-9.\-]+[.][a-z]{2,4}\/)(?:[^\s()<>]+|\(([^\s()<>]+|(\([^\s()<>]+\)))*\))+(?:\(([^\s()<>]+|(\([^\s()<>]+\)))*\)|[^\s`!()\[\]{};:'".,<>?«»“”‘’]))/i;
re.test("http://google./?q=(AAAAAAAAAAAAAAAAAAAAAAAAAAAAA)")

... can take a really long time to execute (e.g. in Chrome)

It seems to me that the problem lies in this part of the code:

(?:                       # One or more:
    [^\s()<>]+                  # Run of non-space, non-()<>
    |                           #   or
    \(([^\s()<>]+|(\([^\s()<>]+\)))*\)  # balanced parens, up to 2 levels
  )+

... which seems to be roughly equivalent to (.+|\((.+|(\(.+\)))*\))+, which looks like it contains (.+)+

Is there a change I can make that will avoid that?

• javascript
• regex
• backtracking

Share Improve this question Follow edited May 23, 2017 at 12:16 CommunityBot 111 silver badge asked Apr 18, 2012 at 21:52 David IngersolDavid Ingersol 18566 bronze badges 2

• Really, you should throw this regex away and e up with one that does what you need. I haven't seen an application yet that is both fluffy enough to be using a regex for URL parsing (instead of a real parser) and serious enough that it needs to handle nested parentheses in a URL. Starting with "https?://" and ending at the first character that should be %-encoded in a proper URL but isn't will handle nearly everything, and doesn't cause the regex matcher to go exponential. – Kyle Jones Commented Apr 18, 2012 at 22:28
• Have you tried Rubular? It has a handy cheat sheet below it, and you can add all kinds of test expressions to make sure it works. (P.S. I'm aware this is for js, but this is still a handy resource nonetheless.) rubular. – Edwin Commented Apr 18, 2012 at 22:28

Add a ment  | 

1 Answer 1

Sorted by: Reset to default 10

Changing it to the following should prevent the catastrophic backtracking:

(?xi)
\b
(                       # Capture 1: entire matched URL
  (?:
    https?://               # http or https protocol
    |                       #   or
    www\d{0,3}[.]           # "www.", "www1.", "www2." … "www999."
    |                           #   or
    [a-z0-9.\-]+[.][a-z]{2,4}/  # looks like domain name followed by a slash
  )
  (?:                       # One or more:
    [^\s()<>]+                  # Run of non-space, non-()<>
    |                           #   or
    \(([^\s()<>]|(\([^\s()<>]+\)))*\)  # balanced parens, up to 2 levels
  )+
  (?:                       # End with:
    \(([^\s()<>]|(\([^\s()<>]+\)))*\)  # balanced parens, up to 2 levels
    |                               #   or
    [^\s`!()\[\]{};:'".,<>?«»“”‘’]        # not a space or one of these punct chars
  )
)

The only change that was made was to remove the + after the first [^\s()<>] in each of the "balanced parens" portions of the regex.

Here is the one-line version for testing with JS:

var re = /\b((?:https?:\/\/|www\d{0,3}[.]|[a-z0-9.\-]+[.][a-z]{2,4}\/)(?:[^\s()<>]+|\(([^\s()<>]|(\([^\s()<>]+\)))*\))+(?:\(([^\s()<>]|(\([^\s()<>]+\)))*\)|[^\s`!()\[\]{};:'".,<>?«»“”‘’]))/i;
re.test("http://google./?q=(AAAAAAAAAAAAAAAAAAAAAAAAAAAAA")

The problem portion of the original regex is the balanced parentheses section, to simplify the explanation of why the backtracking occurs I am going to pletely remove the nested parentheses portion of it because it isn't relevant here:

\(([^\s()<>]+|(\([^\s()<>]+\)))*\)    # original
\(([^\s()<>]+)*\)                     # expanded below

\(                # literal '('
(                 # start group, repeat zero or more times
    [^\s()<>]+        # one or more non-special characters
)*                # end group
\)                # literal ')'

Consider what happens here with the string '(AAAAA', the literal ( would match and then AAAAA would be consumed by the group, and the ) would fail to match. At this point the group would give up one A, leaving AAAA captured and attempting to continue the match at this point. Because the group has a * following it, the group can match multiple times so now you would have ([^\s()<>]+)* matching AAAA, and then A on the second pass. When this fails an additional A would be given up by the original capture and consumed by the second capture.

This would go on for a long while resulting in the following attempts to match, where each ma-separated group indicates a different time that the group is matched, and how many characters that instance matched:

AAAAA
AAAA, A
AAA, AA
AAA, A, A
AA, AAA
AA, AA, A
AA, A, AA
AA, A, A, A
....

I may have counted wrong, but I'm pretty sure it adds up to 16 steps before it is determined that the regex cannot match. As you continue to add additional characters to the string the number of steps to figure this out grows exponentially.

By removing the + and changing this to \(([^\s()<>])*\), you would avoid this backtracking scenario.

Adding the alternation back in to check for the nested parentheses doesn't cause any problems.

Note that you may want to add some sort of anchor to the end of the string, because currently "http://google./?q=(AAAAAAAAAAAAAAAAAAAAAAAAAAAAA" will match up to just before the (, so re.test(...) would return true because http://google./?q= matches.