Regex to parse horizontal rules in Markdown

Question

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?

Answer 1

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

Answer 2

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]*$

Answer 3

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

Answer 4

The following is closer to the CommonMark Spec as "it is required that all of the characters other than spaces or tabs be the same" and only up to 3 spaces are permitted in front of the horizontal rule.

/^ {0,3}[\-][ \t]*[\-][ \t]*[\-][\- \t]*$|^ {0,3}[\*][ \t]*[\*][ \t]*[\*][\* \t]*$|^ {0,3}[_][ \t]*[_][ \t]*[_][_ \t]*$/

regex101 shows 75 steps