Re^5: Regex infinite loop?

Yikes ! This gave me an opportunity to learn a bit about debuggering regex.

The pragma use re 'debug' will tell you more than you ever thought you might have wanted to know about the regex being processed.

The problem I found was that the 'colts' html contains:

  <td class="qty" style="width: 7%;">

where your regex was looking for:

  <td class="qty">

Because the regex is littered with .*?, there is lots of scope for backtracking. As far as I can see:

first it backtracks to (.+?)</a> and goes screaming forward trying to find another </a>;...
...which it finds, but the next <td class="qty" style...> also fails...
...so, when there are no more </a>; to try, it backtracks to .*?>(.+?)</a>...
...I started to lose the will to live at this point, but observe that there are five earlier .*? available to backtrack to...

I doubt that this is an infinite loop. But I haven't the patience to establish one way or the other.

Not sure what to suggest here... Where possible I would replace .*? by, for example, [^<]*? -- which limits the scope for backtracking. There is other regex magic to limit backtracking, but I'm not familiar with it.

However, the big problem I see is that you can never be sure whether your regex has failed because there is no more data of interest, or because it's not recognising a small variation in format. Do you have a drawing board ?

Comment on Re^5: Regex infinite loop? Select or Download Code

Replies are listed 'Best First'.
Re^6: Regex infinite loop? by Ninth Prince (Acolyte) on Oct 17, 2008 at 14:32 UTC
Thank you very much. I'm going to do a mea culpa here. The code is not, in fact, hanging -- it's just taking a very long time to execute. The thing that confuses me, though, is that for most pages, it does all of the matching in a matter of a few seconds. For the colts and the jets however, it takes something like 2 HOURS. Intuitively, it seems like there must be something that is different about their pages, but I'm not sure what it is. I think that I need to learn more about how the regex engine works. I clearly don't have a good understanding of backtracking. Maybe it's time for me to get myself a copy of "Mastering Regular Expressions!" I will give what you have suggested a try. Thank you very much for your efforts on my behalf.	[reply]

Replies are listed 'Best First'.

Re^6: Regex infinite loop?
by Ninth Prince (Acolyte) on Oct 17, 2008 at 14:32 UTC

Thank you very much. I'm going to do a mea culpa here. The code is not, in fact, hanging -- it's just taking a very long time to execute. The thing that confuses me, though, is that for most pages, it does all of the matching in a matter of a few seconds. For the colts and the jets however, it takes something like 2 HOURS. Intuitively, it seems like there must be something that is different about their pages, but I'm not sure what it is. I think that I need to learn more about how the regex engine works. I clearly don't have a good understanding of backtracking. Maybe it's time for me to get myself a copy of "Mastering Regular Expressions!"

I will give what you have suggested a try.

Thank you very much for your efforts on my behalf.

[reply]