python re problem

Question

i test re on some pythonwebshelll, all of them are encounter issue

if i use

a=re.findall(r"""<ul>[\s\S]*?<li><a href="(?P<link>[\s\S]*?)"[\s\S]*?<img src="(?P<img>[\s\S]*?)"[\s\S]*?<br/>[\s\S]*?</li>[\s\S]*?</li>[\s\S]*?</li>[\s\S]*?</ul>""",html)
print a

it's ok

but if i use

a=re.findall(r"""<ul>[\s\S]*?<li><a href="(?P<link>[\s\S]*?)"[\s\S]*?<img src="(?P<img>[\s\S]*?)"[\s\S]*?<br/>[\s\S]*?</li>[\s\S]*?</li>[\s\S]*?</li>[\s\S]*?</ul>d""",html)
print a

it will block the server and wait always like the server is dead,also i have tested on regexbuddy

the only difference betwwen the two snippet code is at the end of the second snippet code's regur expression,i add a character 'd'

any one can explain why occures this

Answer 1

The expression [\s\S]*? can match any amount of anything. This can potentially cause an enormous amount of backtracking in the case that the match fails. If you are more specific about what you can and can't match then it will allow the match to fail faster.

Also, I'd advise you to use an HTML parser instead of regular expressions for this. Beautiful Soup is an excellent library that is easy to use.

Answer 2

Your regex is suffering from catastrophic backtracking. If it can find a match it's fine, but if it can't, it has to try a virtually infinite number of possibilities before it gives up. Every one of those [\s\S]*? constructs ends up trying to match all the way to the end of the document, and the interaction between them creates a staggering amount of useless work.

Python doesn't support atomic groups, but here's a little trick you can use to imitate them:

a=re.findall(r"""(?=(<ul>[\s\S]*?<li><a href="(?P<link>[\s\S]*?)"[\s\S]*?<img src="(?P<img>[\s\S]*?)"[\s\S]*?<br/>[\s\S]*?</li>[\s\S]*?</li>[\s\S]*?</li>[\s\S]*?</ul>))\1d""",html)
print a

If the lookahead succeeds, the whole <UL> element is captured in group #1, the match position resets to the beginning of the element, then the \1 backreference consumes the element. But if the next character is not d, it does not go back and muck about with all those [\s\S]*? constructs again, like your regex does.

Instead, the regex engine goes straight back to the beginning of the <UL> element, then bumps ahead one position (so it's between the < and the u) and tries the lookahead again from the beginning. It keeps doing that until it finds another match for the lookahead, or it reaches the end of the document. In this way, it will fail (the expected result) in about the same time your first regex took to succeed.

Note that I'm not presenting this trick as a solution, just trying to answer your question as to why your regex seems to hang. If I were offering a solution, I would say to stop using [\s\S]*? (or [\s\S]*, or .*, or .*?); you're relying on that too much. Try to be as specific as you reasonably can--for example, instead of:

<a href="(?P<link>[\s\S]*?)"[\s\S]*?<img src="(?P<img>[\s\S]*?)"[\s\S]*?

...use:

<a href="(?P<link>[^"]*)"[^>]*><img src="(?P<img>[^"]*)"[^>]*>

But even that has serious problems. You should seriously consider using an HTML parser for this job. I love regexes too, but you're asking too much from them.