29
\$\begingroup\$

I'm the current maintainer of Showdownjs, a markdown parser off which PageDown (stackexchange's markdown parser) is based on.

Showdown uses the following regex to parse horizontal rules:

/^( ?(-|\*|_) ?){3,}[ \t]*$/gm

This works fine for most cases. However, the following input:

- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - abc

makes the library painfully slow (takes about 10 seconds on nodeJS and longer in browsers). The more dashes you add, the slower it gets.

In fact, if you copy the input above and paste it here on stackexchange, the page will freeze. (stackexchange uses a similar regex to parse <hr>)

How can I make it faster?

\$\endgroup\$
  • 2
    \$\begingroup\$ Catastrophic Backtracking \$\endgroup\$ – Tushar Dec 19 '16 at 11:29
  • 9
    \$\begingroup\$ I misread the library name as Slowdownjs twice. I must have catastrophic backtracking, too. \$\endgroup\$ – ojdo Dec 19 '16 at 12:32
  • \$\begingroup\$ If you want to know why asking for explanation of code is off-topic, please read our off-topic page and let me know if it's still unclear. \$\endgroup\$ – janos Dec 19 '16 at 16:02
32
\$\begingroup\$

Congratulations, what you have here is a case of really really bad backtracking. Remember the StackOverflow outage in July 2016? Because it's explained quite nicely there.

regex101 is so kind as to tell us in the debugger view how many steps the regex takes until it matches. In case you were wondering, it's 111,803

We can drastically reduce the number of steps by removing alternative paths from the matcher graph . This can be done by eliminating optionals, dropping non-greedy quantification and some other hacks. In this case we can use a simple trick that's related to the fact that we should only allow a single space in between the asterisks,dashes and underscores:

/^( ?[-_*]){3,} ?[\t]*$/

Already cuts down the recognition of the pattern mismatch in your example to a measly 272 steps. Do note that I took the liberty of replacing your ORing capture group with a significantly "easier" character class. The functionality is basically equivalent, if we ignore the fact that the capture group you use results in mismatching and additional steps.
This change makes it easier for the regex-engine to determine a match.

The only significant difference between your pattern and mine is that mine doesn't recognize the "non-standard" (as far as that's defined in markdown):

-  -  -
- - - // as opposed to this with only one space between dashes

well and the fact that it doesn't exhibit catastrophic backtracking :) check it out on regex101

\$\endgroup\$
  • \$\begingroup\$ It's perhaps worth noting that some Markdown flavors, like CommonMark, do allow multiple spaces between the dashes / stars / underscores. On the other hand, CommonMark requires all the non-whitespace characters to be identical, which neither Tivie's regex nor yours does. \$\endgroup\$ – Ilmari Karonen Dec 19 '16 at 13:51
  • \$\begingroup\$ BTW, I believe you did introduce another minor difference: your regex won't match e.g. "--- \t \t". To fix that, you could change it back to /^( ?[-_*]){3,}[ \t]*$/; that shouldn't cause any extra backtracking, since ( ?[-_*]){3,} must end in a non-whitespace character anyway. Also, if allowing multiple spaces between the dashes is desired for backwards compatibility, I believe /^ ?([-_*] *){3,}(\t[ \t]*)?$/ or even /^ ?([-_*] {0,2}){3,}[ \t]*$/ (if you want to match exactly the same strings as the original regex) should do it without excessive backtracking. \$\endgroup\$ – Ilmari Karonen Dec 19 '16 at 14:03
7
\$\begingroup\$

I have just signed up, so I can only post answers and not comment on the otherwise nice answer of Vogel612.

I would like to add that it is also possible in PCRE to make {3,} not backtrack at all. You can do this by adding a + behind it. In this case, it is completely equivalent, because the part before and after the added + don't overlap (except for an optional space). The following regex only needs 196 steps to find that it does not match:

^( ?(-|\*|_) ?){3,}+[ \t]*$

If I combine this with Vogel612's trick of removing the multiple options to match the spaces, I can get it down to just 103:

^( ?[-_*]){3,}+ ?[\t]*$
\$\endgroup\$
  • 4
    \$\begingroup\$ While this is an awesome trick, unfortunately the standard javascript regex engine does not accept that as a regex :( \$\endgroup\$ – Vogel612 Dec 19 '16 at 16:03
  • \$\begingroup\$ Ah, I am sorry. I'm not too fluent in JavaScript, and tested it on the link you provided. I didn't notice it loaded PHP instead of JS by default. \$\endgroup\$ – TimVdE Dec 19 '16 at 16:06
3
\$\begingroup\$

Now I may be wrong, but I am able to match:

------- from 3 and up

- - - - - from 3 and up

While not matching the 'abc' example (or any line that throws a non-horizontal rule symbol into the mix anywhere in the line), with:

/^ *[\-\*_] *[\-\*_] *[\-\*_][\-\*_ \t]*$/ in 66 steps.

My one concern is that I'm not sure if you are wanting to allow multiple spaces between your horizontal-rule symbols. Because this definitely lets you add additional spaces between the symbols.

If the ability to add extra spaces is not a problem though, would this be a legitimate option for shortening the number of search steps required?

You can check out the pattern on regex101

\$\endgroup\$
  • \$\begingroup\$ 2 years ago I forgot to reply (and give you credit), but I ended up using a variant of your regex \$\endgroup\$ – Tivie Oct 8 '18 at 1:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.