[antlr-interest] Stack overflow problem with C++

[Paul Johnson]

Ric Klaren wrote:
> Jorg Halker wrote:
> 
>>Okay, i tried it with linux (feodora core 2) and gcc (v3.2.2). It looks like
>>that the stack is larger there. So if i count until 150000 i have the same
>>problem with linux and gcc: segmentation fault/stack overflow. But if i set
>>up a parser which parses a file and creates an ast with the same amount of
>>ast nodes like the loop from the code snippet does, everything is fine and
>>the program exits well.
>>
>>Is it intended that the loop creates objects on the stack?? am i wrong if i
>>think that the stack should not overflow because the objects should be
>>created on the heap?? 
> 
> 
> Hmmm my guess is then that it's the reference counter that recurses too
> deep while destroying the tree structure. Note that the structure you
> made is very deep probably deeper than any 'real' AST would be.
> 
> Destroying the tree 'manually' with a stack you yourself maintain on the
> heap might be a solution. Actually I now recall a person running into
> this as well but that was a few years ago.

Just to clarify:

you create 'first' on the stack; you then add 150K siblings. When main 
terminates, the destructor for 'first' is called. This deletes the first 
AST node, but it first has to delete the 'right' field (ie. the 
sibling). Before deleting sibling, we have to delete the second sibling, 
and so on; the delete is therefore recursive. This is necessary because 
you have to decrement a reference count before deciding whether or not 
to delete a node; this means that the process has to be top-down, rather 
than bottom-up. The overflow you're seeing is simply the call stack for 
the recursive destruction. I checked this in valgrind, which shows that 
your test has a negligible stack until the end of the program, when it 
suddenly explodes to 20MB.

If you need to fix this, change your 'first' declaration to:

RefCommonAST *first = new RefCommonAST( new CommonAST());

so that the tree isn't deleted on program exit.

HTH

Paul