[antlr-interest] Problem with memory management

Ric Klaren ric.klaren at gmail.com
Mon Jul 24 04:09:05 PDT 2006


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


More information about the antlr-interest mailing list