Resolving Catastrophic Backtracking issue in RegEx
<p>I am using RegEx for finding URL substrings in strings.
The RegEx I am using has been taken from tohster's answer on - 
<a href="http://stackoverflow.com/questions/520031/whats-the-cleanest-way-to-extract-urls-from-a-string-using-python/30408189#30408189">What&#39;s the cleanest way to extract URLs from a string using Python?</a></p>

<p>The RE is -</p>

<pre><code>r'^(?:(?:https?|ftp)://)(?:\S+(?::\S*)?@)?(?:(?:[1-9]\d?|1\d\d|2[01]\d|22[0-3])(?:\.(?:1?\d{1,2}|2[0-4]\d|25[0-5])){2}(?:\.(?:[1-9]\d?|1\d\d|2[0-4]\d|25[0-4]))|(?:(?:[a-z\u00a1-\uffff0-9]+-?)*[a-z\u00a1-\uffff0-9]+)(?:\.(?:[a-z\u00a1-\uffff0-9]+-?)*[a-z\u00a1-\uffff0-9]+)*(?:\.(?:[a-z\u00a1-\uffff]{2,})))(?::\d{2,5})?(?:/[^\s]*)?$'
</code></pre>

<p>I have done some changes to it - </p>

<blockquote>
  <ol>
  <li>In the IPv4 detection part, I changed the order of the IP range to be found. > Precisely, changed <code>[1-9]\d?|1\d\d|2[01]\d|22[0-3]</code> to <code>25[0-5]|2[0-4][0-9]|1[0-&gt; 9]{2}|[1-9][0-9]|[0-9]</code> at 2 instances.</li>
  <li>Made the https group - <code>(?:https?|ftp):\/\/)?(?:\S+(?::\S*)?@)</code> optional.</li>
  </ol>
</blockquote>

<p>The final version is -</p>

<pre><code>(?:(?:https?|ftp):\/\/)?(?:\S+(?::\S*)?@)?(?:((25[0-5]|2[0-4][0-9]|1[0-9]{2}|[1-9][0-9]|[0-9])\.){3}(25[0-5]|2[0-4][0-9]|1[0-9]{2}|[1-9][0-9]|[0-9])|(?:(?:[a-z\u00a1-\uffff0-9]+-?)*[a-z\u00a1-\uffff0-9]+)(?:\.(?:[a-z\u00a1-\uffff0-9]+-?)*[a-z\u00a1-\uffff0-9]+)*(?:\.(?:[a-z\u00a1-\uffff]{2,})))(?::\d{2,5})?(?:\/[^\s]*)?
</code></pre>

<p>The final RE I am using seems to be very promising and has improved significantly as per my requirements(as compared to the original one) and works in Python as well as Java Script, except for the fact that due to the changes I have done have caused the following examples to give <code>"catastrophic backtracking"</code> error -</p>

<blockquote>
  <p>asasasasasac31.23.53.122asasassasd</p>
  
  <p>12312312312321.32.34.2312312312321</p>
  
  <p>12.3423423432.234123123.123</p>
  
  <p>31.134232131.231.34</p>
</blockquote>

<p>Can be tested at - <a href="https://regex101.com/r/i6jDei/1" rel="nofollow">https://regex101.com/r/i6jDei/1</a></p>

<p>My contention is that the first example - <code>asasasasasac31.23.53.122asasassasd</code> should have some slick way to pass as the IP is surrounded by non-numeric chars.</p>

<p>Also, is there a way to pass the first two of the above examples as valid IPv4 addresses?</p>

<p>To resolve ambiguity, I would opt for the largest possible Address, i.e.,</p>

<blockquote>
  <p>31.23.53.122</p>
  
  <p>21.32.34.231</p>
</blockquote>

<p>The issue of the catastrophic backtracking is caused by the pattern <code>(?:(?:[a-z\u00a1-\uffff0-9]+-?)*[a-z\u00a1-\uffff0-9]+)(?:\.(?:[a-z\u00a1-\uffff0-9]+-?)*[a-z\u00a1-\uffff0-9]+)*(?:\.(?:[a-z\u00a1-\uffff]{2,}))</code> where <code>(?:[a-z\u00a1-\uffff0-9]+-?)*[a-z\u00a1-\uffff0-9]+)</code> will jump through a lot of combinations, if the overall pattern can not be matched. As you can see the character classes are basically the same, so e.g. for <code>asasasasasac31</code> it can match like:</p>

<pre><code>(asasasasasac31)
(a)(sasasasasac31)
(a)(s)(asasasasac31)
(as)(asasasasac31)
</code></pre>

<p>This is not really the way it actually takes, just to show how many combinations exist.</p>

<p>The mistake here seems to be the <code>-</code> being optional which I see no reason for. If we remove the -, we get it working for your samples (and reduce the number of steps for the already working samples). </p>

<p>See the updated <a href="https://regex101.com/r/i6jDei/3" rel="nofollow">regex101-demo</a>, where I also added your samples that caused the catastrophic backtracking.</p>

<p>The final pattern then is:</p>

<pre><code>(?:(?:https?|ftp):\/\/)?(?:\S+(?::\S*)?@)?(?:((25[0-5]|2[0-4][0-9]|1[0-9]{2}|[1-9][0-9]|[0-9])\.){3}(25[0-5]|2[0-4][0-9]|1[0-9]{2}|[1-9][0-9]|[0-9])|(?:(?:[a-z\u00a1-\uffff0-9]+-)*[a-z\u00a1-\uffff0-9]+)(?:\.(?:[a-z\u00a1-\uffff0-9]+-)*[a-z\u00a1-\uffff0-9]+)*(?:\.(?:[a-z\u00a1-\uffff]{2,})))(?::\d{2,5})?(?:\/[^\s]*)?
</code></pre>

python regex url ip-address ipv4