In the realm of Regular Expressions, what is backtracking?

Question

The expression I have is

$(from \/projects(\/(\w|.)+)+):$(\d+$)

The strings I'm trying to match are:

(from /projects/idpro/branches/release_2018/test/test/test.1:13118)
(from /projects/idpro/trunk:13074)

the online regex testing utility I'm using blows up stating catastrophic backtracking. So here I am trying to learn what backtracking is, so I can avoid it and fix my code.

Of the 2 string examples I have provided, I would like to match both. In the first case, I'm trying to match (from /projects. After the word projects, I want to ignore a path of any dept, so long as the string ends with a :\d+\)

Similarly, for the second example, I want a match if (from /projects is followed by at least one folder, and ends with a :\d+\).

AdThanksVance

A great Google search expression is [regex backtracking explained](https://www.google.com/search?q=regex+backtracking+explained) — Ken White, Aug 24 '18 at 03:10
Your code will work just fine if you remove the `$` sign. https://regex101.com/r/PUv8Ma/1/ — Ibrahim, Aug 24 '18 at 03:12
@TimBiegeleisen It's ok, I was just trying to understand your point. — Ibrahim, Aug 24 '18 at 04:28
Possible duplicate of [How can I recognize an evil regex?](https://stackoverflow.com/questions/12841970/how-can-i-recognize-an-evil-regex) — tripleee, Aug 24 '18 at 04:37

Tim Biegeleisen · Answer 1 · 2018-08-24T04:21:31.097

0

I'm not sure exactly what is causing the catastrophic backtracking. But in any case, I would phrase your regex as this:

^\(from \/projects(?:\/[^\/]+)*:\d+$

As you can see in the demo below, there is no catastrophic backtracking happening.

Demo

Catastrophic backtracking is usually associated with poorly written regex patterns. So, just don't do that, and it probably won't happen.

edited Aug 24 '18 at 04:21

answered Aug 24 '18 at 03:07

Tim Biegeleisen

502,043
27
286
360

In the realm of Regular Expressions, what is backtracking?

1 Answers1

Demo