re.search() in python goes into an infinite loop

Question

I'm trying to extract file paths (Windows/Ubuntu, relative/absolute) from a text document.

The regular expression code below is used check if a word is a file path or not.

It works for most of the cases but fails for one case, where it goes into an infinite loop. Any explanation for this?

import re
path_regex = re.compile(r'^([\.]*)([/]+)(((?![<>:"/\\|?*]).)+((?<![ .])(\\|/))?)*$' , re.I)
text = '/var/lib/jenkins/jobs/abcd-deploy-test-environment-oneccc/workspace/../workspace/abcd-deploy-test-environment.sh'
path_regex.search(text)

Answer 1

Indeed there is a problem.
You have overlayed subexpressions mixed with spurious quantifiers.

modified for required parts between slashes
It is easily fixed using this ^([\.]*)([/]+)((?:[^<>:"/\\|?*.\r\n]|\.(?![\\/]))[\\/]?)*$

The idea is to see just what your guarding against.
The guard is that you'd allow forward or back slash if not preceeded by a dot.

So, you have to include the dot in the exclusion class with the \ and /
then qualify them in a separate alternation.

If you do it this way, it will always pass.

 ^ 
 ( [\.]* )                     # (1)
 ( [/]+ )                      # (2)
 (                             # (3 start)
      (?:                           # Group start (required between slashes)
           [^<>:"/\\|?*.\r\n]            # Any character, but exclude these
        |                              # or,
           \.                            # The dot, if not followed by forward or back slash
           (?! [\\/] )
      )                             # Group end
      [\\/]?                        # Optional forward or back shash
 )*                            # (3 end)
 $

Answer 2

sln gave a good solution to your problem, so I'll try to explain what the problem is.

Welcome to the joys of catastrophic backtracking. The core of your problem is in (((?![<>:"/\\|?*]).)+((?<![ .])(\\|/))?)*. (Now that I've said that, all your problems are solved, right? Easy peasy.)

Assuming you're a bit like me and blinked blankly a couple of times the first time someone said "regex backtracking", we can work through your regex with the shorter input /path./. This is an invalid path according to your regex, but lets us (somewhat) easily walk through the problem.

^([\.]*)([/]+) matches the leading /. This works fine.

For the sake of readability here, I'm going to call the first half of the problematic capture group, ((?![<>:"/\\|?*]).)+, x+, and the second half, ((?<![ .])(\\|/))?, y?. The whole group is (x+y?).

How is (x+y?)*$ backtracking when matching path./?

1. x+ matches path.
2. y? matches (it matches 0 times, which is fine because of the ?)
3. (x+y?) has now matched once
4. (x+y?) repeats, and fails, since it does not match /. Thus, (x+y?)* has matched path.
5. $ fails, since it does not match /.
6. The regex engine backtracks:
   • (x+y?)* can only backtrack into its first iteration, since it only had one iteration.
   • Within that iteration, y? can't backtrack, since it matched 0 times.
   • x+ backtracks, to match only path instead of path.
7. x+ matches path
8. y? matches
9. (x+y?) has now matched once (path)
10. (x+y?) repeats and matches again:
    • x+ matches .
    • y? matches
11. (x+y?) repeats, and fails since it does not match /. Thus, (x+y?)* has matched path.
12. $ fails, since it does not match /.
13. The regex engine backtracks:
    • (x+y?)* can only backtrack into its first iteration, since in its second iteration x+ matched only once and y? matched 0 times.
    • y? in the first iteration matched 0 times, so it can't backtrack
    • x+ can backtrack to only matching pat
14. Hopefully you get the idea, but (x+y?) matches twice: pat, h.; then on the next backtrack we have pat h ., and then pa th., and so on.

It takes 478 steps for the engine to determine that /path./ is not matched by your regex. Every additional character in that problematic capture group increases the number of backtracks by a lot, and after a certain point your regex implementation is just going to throw up its hands and give up. sln's solution takes only 49 steps.

The behaviour of a regex engine when backtracking is difficult both to explain and to grasp, especially when limited to Markdown, so I would recommend running your regex through a debugger to visualize what's going on.