Infinite loop yet no loop

[ido50]

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);
}

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

Any help grately appreciated,
Ido Perelmutter.

[halley]

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;

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";
    }
}

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.)

[ido50]

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.

[gjb]

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-

[bart]

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.

[ido50]

Yes, the root is always created and is kind of a dummy entry.

[TomDLux]

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.

[graff]

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...

[Theo]

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.