Regex to parse horizontal rules in Markdown 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 &lt;hr&gt;)

How can I make it faster?
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