[antlr-interest] Problem with (C++) memory management

[Loring Craymer]

Eugen--

You will probably need Ric Klaren's help on this--I think that you need to modify the ~RefAST destructor.

--Loring


Eugen Cazacu <the_e57 at yahoo.com> wrote: Hi, I am new to this list, someone recommended me to
join it so that I can get my questions and problems
about antlr answered.
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. It happenes like this: you want to destroy the
root node, the root has many children, it calls the
destructor of the first child node, that one in order
to destroy calls the destructor on all of its members
and calls the destructor of the next sibling, the
destructor of the next sibling calls the destructor of
its next sibling and so on until the last sibling.
Since one node might have many children, 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
consider that the refCounter adds one more function
call for each node we would have from 40000 to 60000
recursive functions calls, which causes a stack
overflow and make the program to end with a
segmentation fault. 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 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 function moves the nodes in a vector type
structures and then deletes them, this way I avoid the
recursive call of the destructors)
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:

class MyAST : public AST {
  vector m_children;
  RefMyAST parent;
};

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.

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


 __________________________________________________
Do You Yahoo!?
Tired of spam?  Yahoo! Mail has the best spam protection around 
http://mail.yahoo.com 
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.antlr.org/pipermail/antlr-interest/attachments/20060721/93b7182d/attachment.html