Infinite loop yet no loop

ido50 has asked for the wisdom of the Perl Monks concerning the following question:

Hi again!
Okay so I'm writing a CGI/Perl program (Object-Oriented Style) for some purpose. I use a tree-like structure in my program which, at certain situations, loads information from a database.
Foreach database entry, the program adds it to the tree, but only if its parent was already found (and added). If not, it pushes it into a buffer array.
In the end of the database reading, another method iterates over the buffer and adds the entries in it to the tree. Once again, this method also adds only if the parent was already added. So if an item from the buffer is added to the tree, it is also deleted from the buffer, and the method runs recursively with the changed buffer.

When calling the method, the program enters an infinite loop. I thought the recursion was the cause of it, so I deleted it to verify it, and it wasn't. It did the same thing again.
Anyway, the code looks like this (Recursion call commented out:

sub _addbuf {
   my ($class, $buffer) = @_;

   my $args = shift @$buffer;
   if (SOMECLASS->exists($args->{parent}) {
      my $new = SOMECLASS->new($args);
   } else {
    push(@$buffer, $args);
   }
   
   #SOMECLASS->_addbuf($buffer);
}
[download]

That's it. For some reason, the program enters an infinite loop, and I have no idea why.

Any help grately appreciated,
Ido Perelmutter.

-------------------------
Live fat, die young

Comment on Infinite loop yet no loop Download Code

Replies are listed 'Best First'.
Re: Infinite loop yet no loop by halley (Prior) on Mar 18, 2004 at 20:02 UTC
One, it's time to go back to basics: Comp Sci principles. Recursion needs a terminal case; some situation which you can PROVE will always happen eventually, that stops the recursion. In your case, all execution paths will reach the recursion call, even if `$buffer` is `undef`, or `@$buffer` is empty. `SOMECLASS->_addbuf($buffer) if $buffer && @$buffer;` [download] Two, it's time to go back to basics: Debug by observation. Rather than infer that the program is spinning uselessly, you should either (1) run a debugger and WATCH the program do the unexpected, or (2) add `print` statements or other tracery so you can know exactly what's getting called, with what arguments, in what order, and when. `sub _addbuf { print STDERR "_addbuf(", Dumper(\@_), ")\n"; ... if (...) { print STDERR "making a new item...\n"; } }` [download] Three, it's time to go back to basics. I don't know if you're just skipping parts of your example, but why are you creating a `$new` instance but never using it or attaching it anywhere? (Don't take my tone as being angry or anything; it's easy to stare at code and forget to think about the basics of what you're trying to accomplish. We all do it. Well, everyone except for tye.) -- `[ e d @ h a l l e y . c c ]`	[reply] [d/l] [select]
Re: Re: Infinite loop yet no loop by ido50 (Scribe) on Mar 21, 2004 at 15:44 UTC
One - there is a terminating condition, I just didn't copy it, it didn't really matter as the recursion is not the cause of it... Two, I have tried some `print` statements, but couldn't find the problem. I'll try the debugger... Three, once again, I didn't copy the entire subroutine. I am using a check of `$new` to see if the node was shoved into the tree or not... Thanks to you and anyone who replied, I'll try all your suggestions. ------------------------- Live fat, die young	[reply] [d/l] [select]
Re: Infinite loop yet no loop by gjb (Vicar) on Mar 18, 2004 at 19:07 UTC
Are you sure the root of the tree is added? If not, and you don't handle this, nothing will ever be added. Just my 2 cents, -gjb-	[reply]
Re: Re: Infinite loop yet no loop by bart (Canon) on Mar 18, 2004 at 20:22 UTC
Goog thinking. To the OP: keep track of whether anything changed in the loop, otherwise it's time to abort. For example keep track of the count of items in the buffer, and if it's the same before and after the iteration, nothing has changed, and it's useless to go on.	[reply]
Re: Re: Infinite loop yet no loop by ido50 (Scribe) on Mar 18, 2004 at 19:26 UTC
Yes, the root is always created and is kind of a dummy entry. ------------------------- Live fat, die young	[reply]
Re: Infinite loop yet no loop by TomDLux (Vicar) on Mar 19, 2004 at 02:44 UTC
While we're deealing with basics ... Without recursion, you enter the routine, get the first argument, and either create a SOMECLAS or else shove the argument back onto the argument list. Then you exit the routine. If the recursion line were not commented, I would worry that at least one of the arguments failed the exists() condition. In that case, you would have an infinite loop: after all matching arguments had been processed, the argument list would contain only defective arguments. But since there is not ( currently ) any recursion, and the routine is mostly linear, any looping must occur outside this routine. -- `TTTATCGGTCGTTATATAGATGTTTGCA`	[reply]
Re: Infinite loop yet no loop by graff (Chancellor) on Mar 19, 2004 at 02:58 UTC
I thought the recursion was the cause of it, so I deleted it to verify it, and it wasn't. It did the same thing again. This is embarrassing, so forgive me (and heaven help me), but this sort of statement reminds me of a mistake that I still make on occasion: I have the script in an editor window, where I see the code that I've just changed, and I run it in a separate shell window... forgetting to notice that I hadn't done the "save buffer" command in the editor, or forgetting that I saved the modified "test/debug" version under a different path/name -- hence I'm still running the prior version of the script in that shell window. But I'm sure I'm the only one who ever does this...	[reply]
Re: Re: Infinite loop yet no loop by Theo (Priest) on Mar 19, 2004 at 15:21 UTC
No, you're not alone. Another gotcha for me is modifying a file in directory A and running a copy of the file which lives in directory B. -Theo- (so many nodes and so little time ... )	[reply]