in reply to Regex infinite loop?

If pattern contains nested quantifiers, it might take a very long time to match. Ages.

Consider this script:

#!/usr/bin/perl use strict; use warnings; use Benchmark qw(timethis); my $str = 'a' x shift; timethis(1, sub { $str =~ m/([abc]*[ab]*){2,12109}\d/; });

For a string with length 12 it takes 2.4 seconds to determine that there's no match, for 13 it's 8.3 seconds and for 14 it's 28 seconds.. And it grows exponentially.

Replies are listed 'Best First'.
Re^2: Regex infinite loop?
by Ninth Prince (Acolyte) on Oct 16, 2008 at 18:39 UTC

    I can't give you a technical answer to this, but I can tell you that I have been running this code for many weeks now. It runs once a day at the same time. When I run the program manually, it makes each match fairly quickly (a few seconds, at most).

    One thing, though. The code has been running fine for weeks, but whoever runs the website made some minor changes to the HTML. This forced me to have to go back and make a couple of (extremely) minor changes to the matching code. That said, I would note that the code does match, and match quickly, for probably 90% of the pages that I am pulling. It only hangs on a couple. The problem appears page-specific because when I change the order in which I pull the pages, it hangs on the same pages (regardless of where they are in my list of pages).

      Is both the regex and the html of the page that hangs your code a secret? I'm quite sure someone would already have found the solution if you posted the regex and the page code (or the url to that page).

      CountZero

      A program should be light and agile, its subroutines connected like a string of pearls. The spirit and intent of the program should be retained throughout. There should be neither too little or too much, neither needless loops nor useless variables, neither lack of structure nor overwhelming rigidity." - The Tao of Programming, 4.1 - Geoffrey James

        Okay, here is the relevant (I think) piece of the code

        if ($tempType eq "Bid") { while ($content =~m%<td class="marketWatch" style="width: 20p +x;"><p class="pngfix" id="market-watch-(.+?)">&#160;</p>.*?ugid=(.+?) +&marketId=(.+?)&action=add';};.+?<td style="width: 22\%;">\s+<a href= +"/marketplace/sports/nfl/super-bowl-xliii.*?>(.+?)</a>\s+</td>\s+<td +class="qty">.+?(?:"selected"\s+?>|<input type="hidden" id="qty_select +_\d+" value=")(.+?)(?:</option>|"/>).+?<span class="price">\$(.+?)</s +pan>%gs) { print(STDERR "[", pos($content), "]") ; $tempCount = $tempCount+1 ; print "\ntempCount = $tempCount\n" ; $tempMarketWatchID = $1 ; $tempugID = $2 ; $tempmarketID = $3 ; $tempLocation = $4 ; $tempBidQuantity = $5 ; $tempBid = $6 ; $tempLocation =~ s/^\s+// ; $tempLocation =~ s/\s+$// ; print "$date\t$time\t$tempType\t$teamName\t$tempMarketWatchID\t +$tempugID\t$tempmarketID\t$tempLocation\t$tempBidQuantity\t$tempBid\n +" ; } #end while print "Leaving the bid while\n" ; } #end if

        The pages that I am searching are:

        http://www.firstdibz.com/markets/sports/nfl/ravens/super-bowl-xliii/bi +d/show/buy http://www.firstdibz.com/markets/sports/nfl/bills/super-bowl-xliii/bid +/show/buy http://www.firstdibz.com/markets/sports/nfl/bengals/super-bowl-xliii/b +id/show/buy http://www.firstdibz.com/markets/sports/nfl/browns/super-bowl-xliii/bi +d/show/buy http://www.firstdibz.com/markets/sports/nfl/broncos/super-bowl-xliii/b +id/show/buy http://www.firstdibz.com/markets/sports/nfl/texans/super-bowl-xliii/bi +d/show/buy http://www.firstdibz.com/markets/sports/nfl/jaguars/super-bowl-xliii/b +id/show/buy http://www.firstdibz.com/markets/sports/nfl/chiefs/super-bowl-xliii/bi +d/show/buy http://www.firstdibz.com/markets/sports/nfl/dolphins/super-bowl-xliii/ +bid/show/buy http://www.firstdibz.com/markets/sports/nfl/patriots/super-bowl-xliii/ +bid/show/buy http://www.firstdibz.com/markets/sports/nfl/jets/super-bowl-xliii/bid/ +show/buy http://www.firstdibz.com/markets/sports/nfl/raiders/super-bowl-xliii/b +id/show/buy http://www.firstdibz.com/markets/sports/nfl/steelers/super-bowl-xliii/ +bid/show/buy http://www.firstdibz.com/markets/sports/nfl/chargers/super-bowl-xliii/ +bid/show/buy http://www.firstdibz.com/markets/sports/nfl/titans/super-bowl-xliii/bi +d/show/buy http://www.firstdibz.com/markets/sports/nfl/cardinals/super-bowl-xliii +/bid/show/buy http://www.firstdibz.com/markets/sports/nfl/falcons/super-bowl-xliii/b +id/show/buy http://www.firstdibz.com/markets/sports/nfl/panthers/super-bowl-xliii/ +bid/show/buy http://www.firstdibz.com/markets/sports/nfl/bears/super-bowl-xliii/bid +/show/buy http://www.firstdibz.com/markets/sports/nfl/cowboys/super-bowl-xliii/b +id/show/buy http://www.firstdibz.com/markets/sports/nfl/lions/super-bowl-xliii/bid +/show/buy http://www.firstdibz.com/markets/sports/nfl/packers/super-bowl-xliii/b +id/show/buy http://www.firstdibz.com/markets/sports/nfl/vikings/super-bowl-xliii/b +id/show/buy http://www.firstdibz.com/markets/sports/nfl/saints/super-bowl-xliii/bi +d/show/buy http://www.firstdibz.com/markets/sports/nfl/giants/super-bowl-xliii/bi +d/show/buy http://www.firstdibz.com/markets/sports/nfl/eagles/super-bowl-xliii/bi +d/show/buy http://www.firstdibz.com/markets/sports/nfl/49ers/super-bowl-xliii/bid +/show/buy http://www.firstdibz.com/markets/sports/nfl/seahawks/super-bowl-xliii/ +bid/show/buy http://www.firstdibz.com/markets/sports/nfl/rams/super-bowl-xliii/bid/ +show/buy http://www.firstdibz.com/markets/sports/nfl/buccaneers/super-bowl-xlii +i/bid/show/buy http://www.firstdibz.com/markets/sports/nfl/redskins/super-bowl-xliii/ +bid/show/buy http://www.firstdibz.com/markets/sports/nfl/colts/super-bowl-xliii/bid +/show/buy

        The pages that cause my code to hang are the colts and the jets. There maybe others, but I know that every page prior to the jets works fine. After the jets URL, I don't know as I have not tested. (The colts used to be earlier in my list, but I moved it when it started hanging.)