[antlr-interest] Problem with memory management

[Eugen Cazacu]

--- Ric Klaren <ric.klaren at gmail.com> wrote:

> Hi,
> 
> On 7/21/06, Eugen Cazacu <the_e57 at yahoo.com> wrote:
> > I am writing a verilog parser in antl, actually it
> is
> > finished, now we are running tests on it, one type
> of
> > test revealed a pretty big problem with antlr
> design.
> > I must mention that the generated code is C++.
> > The problem is in the way the AST is built. This
> > nextSibling/firstChild tree design has a problem
> when
> > one node has many children, because they are all
> > stored in a unidirectional list if I use CommonAST
> > class. The problem occures on the destruction of
> the
> > tree. ...  this causes a
> > recursive call if all of the destructors in depth.
> IF
> > a node has as many as 20000-30000 children there
> are
> > at least 20000-30000 recursive calls, if we would
> 
> Yup this is a known problem. Occasionally there's
> someone that runs into it.
> 
> > ...
> > To avoid this probelem I wrote a
> > special destroy function to delete the AST after I
> > don't need it any more, that looks like this:
> >
> > void destroy(RefAST &ast) {
> >   if(!ast.get())
> >     return;
> >   std::cerr << "before destroy" << endl;
> >   std::queue<RefAST> destroyQueue;
> >   destroyQueue.push(ast);
> >   ast = 0;
> >   RefAST temp1, temp2;
> >   while(!destroyQueue.empty()) {
> >     temp1 = destroyQueue.front();
> >     destroyQueue.pop();
> >     temp2 = temp1->getFirstChild();
> >     temp1->setFirstChild(RefAST(0));
> >     if(temp2.get())
> >       destroyQueue.push(temp2);
> >     temp2 = temp1->getNextSibling();
> >     temp1->setNextSibling(RefAST(0));
> >     if(temp2.get())
> >       destroyQueue.push(temp2);
> >     temp1 = 0;
> >     temp2 = 0;
> >   }
> 
> This is indeed a good work around.
> 
> > This make the program terminate correctly. But
> only in
> > the case when the parser doesn't throw any
> exceptions
> > (MismatchedTokenException for example). When the
> > parser does this, it destroyes whatever tree was
> built
> > by itself and if the tree is similar to what I
> > described before, a stack overflow occures and the
> > program end without printing the exception message
> in
> > a segmentation fault, because I can only catch the
> > exceptions after antlr tryes to delete the tree.
> >
> > To avoid this problem I am attempting now to write
> my
> > own AST Node class derived from AST that would
> > simulate the behaviour of it, but would use a more
> > linear structure, small example:
> 
> It's probably easier to override the destructor of
> the parser (e.g.
> add a custom destructor in the .g file) and include
> the previous fix
> to that? Or maybe I'm missing something (don't have
> access to the code
> atm so can't check)
> 
> > But here I got another problem. The reference
> counting
> > antlr nechanism doesn't have a weak reference
> class (I
> > can't use strong references, RefCount, because it
> > would cause a the object to have a counted
> reference
> > to itself and it will never be destroyed, since
> antlr
> > RefCount doesn't check for loop references) , that
> I
> > could use in place of "this" pointer, I need it
> > because all the antlr interface uses Refs. This
> would
> > make me to rewrite antlr code, which I don't want
> to
> > do because when a new version of antlr will appear
> I
> > will have to rewrite some code again. I hope that
> > someone could help with this here.
> 
> The reference counter is something I'd rather not
> touch. It's very
> much tailored to the antlr runtime. Trying to use a
> smarter reference
> counter and inject it into the antlr runtime will
> probably get you
> some gray hairs. Got some work in progress code for
> it but that broke
> around heterogeneous AST's.
> 
> Expect something better in antlr3. I will (re)start
> on the C++ codegen
> for ANTLR 3 in one/two weeks.
> 
> Cheers,
> 
> Ric
> 
In order to avoid this problem I with exceptions, I
made the destructor of a AST node to destroy the whole
tree that is below it by invoking my destroy funstions
for nextSibling and firsChild, I know it might skrew
the tree if in one moment one node might be removed
and the subtree used in another place. In my tests
antlr didn't do stuff like that, I hope this will work
fine
Have a nice day,
--------
Eugen Cazacu

__________________________________________________
Do You Yahoo!?
Tired of spam?  Yahoo! Mail has the best spam protection around 
http://mail.yahoo.com