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

[Jörg Hälker]

Hi,

thank you for clarification... i didnt thought that the reference check
during deallocation is the problem. But sure, if a recursive algorithm walks
all the siblings to check whether the objects can be deallocated... But
there are solutions now as i know the problem!

Thank you!
Jörg

> -----Original Message-----
> From: antlr-interest-bounces at antlr.org 
> [mailto:antlr-interest-bounces at antlr.org] On Behalf Of Paul Johnson
> Sent: Tuesday, July 19, 2005 10:11 PM
> To: antlr-interest at antlr.org
> Subject: Re: [antlr-interest] Stack overflow problem with C++
> 
> 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
>