Python regex freezes with small input string
<p>I am using regular expressions on a bunch of wikipedia pages. Actually working really good for the first like 20 pages, but then it suddenly freezes without me seeing a reason. Interrupting the script delivers this:</p>

<pre><code>File "imageListFiller.py", line 30, in getImage
foundImage = re.search(urlRegex, str(decodedLine))
File "/Library/Frameworks/Python.framework/Versions/3.5/lib/python3.5/re.py",line 173, in search
return _compile(pattern, flags).search(string)
</code></pre>

<p>this is my code:</p>

<pre><code>def getImage(wikiHtml):  
    urlRegex = """File:((?:[a-zA-Z]|[0-9]|[$-_@.&amp;+]|[!*\(\),]|(?:[0-9a-fA-F][0-9a-fA-F]))*?\.(png|jpg|svg|JPG))"""
uselessPictures = ("Wiktionary-logo-v2.svg", "Disambig_gray.svg",
                   "Question_book-new.svg", "Commons-logo.png")    

for line in wikiHtml:
    decodedLine = line.decode('utf-8')
    foundImage = re.search(urlRegex, str(decodedLine))
    if foundImage:
        if not foundImage.group(1) in uselessPictures:
            return foundImage.group(1)
</code></pre>

<p>and this is the input string that causes it to freeze:</p>

<blockquote>
  href="/wiki/File:EARTH_-_WIKIPEDIA_SPOKEN_ARTICLE_(Part_01).ogg" title="Listen to this article"> src="//upload.wikimedia.org/wikipedia/commons/thumb/4/47/Sound-icon.svg/20px-Sound-icon.svg.png" width="20" height="15" srcset="//upload.wikimedia.org/wikipedia/commons/thumb/4/47/Sound-icon.svg/30px-Sound-icon.svg.png 1.5x, //upload.wikimedia.org/wikipedia/commons/thumb/4/47/Sound-icon.svg/40px-Sound-icon.svg.png 2x" data-file-width="128" data-file-height="96" > />
</blockquote>

<p>The regex is not actually supposed to match here, it just needs to skip this line.
Thanks!</p>

<p>The <code>$-_</code> part in your pattern created a range matching uppercase letters and digits, and even more chars. Since other alternative branches in the group could match at the same location (like <code>[a-zA-Z]</code>) that led to a time out / catastrophic backtracking issue.</p>

<p>You need to just concat all the character classes that only match 1 char in the 1st group, and either escape the <code>-</code> inside the character class or put it at the start/end of the character class (I'd still escape it if the pattern is going to be updated in the future):</p>

<pre><code>r"""File:((?:[0-9a-fA-F]{2}|[a-zA-Z0-9\-$_@.&amp;+!*(),])*?\.(png|jpg|svg|JPG))"""
</code></pre>

<p>See the <a href="https://regex101.com/r/sF2vH8/3" rel="nofollow">regex demo</a>.</p>

<p>Also, the longer alternative should precede the shorter one, so the <code>[0-9a-fA-F]{2}</code> should go first.</p>

<p>Also, <code>\w</code> can be used to shorten the pattern a bit (to replace <code>[a-zA-Z0-9_]</code>):</p>

<pre><code>r"""File:((?:[0-9a-fA-F]{2}|[\w\-$@.&amp;+!*(),])*?\.(png|jpg|svg|JPG))"""
                             ^^^  
</code></pre>

python regex freeze