My question, Is there no catastrophic backtracking in Go regex?, was closed as "not reproducible or was caused by typos" and I'm afraid I don't understand why. I don't believe there is a typo and the problem is certainly reproducible.
I had drafted an answer, based on comments and further reading, before I spotted that the question was closed and it seems a pity not to be able to post the answer.
I could add the answer as an addendum to the question or maybe in a comment, though I believe comments are transient.
Here is the draft answer in case there will be an objection to it.
Answer
Yes, the catastrophic backtracking warning can be safely ignored when using the regex in Go.
Go uses the RE2 algorithm for regex, and RE2 does not use backtracking so the problem does not arise in Go. https://en.wikipedia.org/wiki/Regular_expression#Implementations_and_running_times has more information about alternative implementations for regex matching. Go (RE2) has linear performance against input string length and regex string length: O(mn).
However other languages / libs that do use backtracking can have exponential running time, depending on the regex and the input string. regex101.com shows the number of steps to run a regex against an input string and you can see the number of steps increase exponentially as you increase the string length for a regex like
(a*)*$
with a string likeaaaaaaaaaaaaaaaaX
. And the debugger on regex101.com can show the pattern match execution one step at a time, so you can see how backtracking has to handle an exponentially increasing number of alternatives.@sln provided an alternative to my original regex that removed the exponential backtracking. Simplifying the before/after regex to
a
andX
, for input stringaaaaaaaaaaaaaaaaZ
^(a+X*)*a$
takes about 300,000 steps (doubling for each additionala
) but^(aX*)*a$
takes about 100 stepsI don't know any general way to map a vulnerable regex to a safe regex
- unless @sln cares to provide a service ;-)
The purpose of the original regex was to check that an input string contains only [a-z0-9] and
-
while starting and ending with [a-z0-9].a
,a-b
,ab--c
,a-b--aa---bbb
, ...