[antlr-interest] Re: Limits of tree generation (C++)

Ric Klaren klaren at cs.utwente.nl
Fri Oct 10 02:23:41 PDT 2003


On Thu, Oct 09, 2003 at 10:09:14AM -0400, Tiller, Michael (M.M.) wrote:
> > On Thu, Oct 09, 2003 at 09:58:08AM -0000, marcschellens wrote:
> > > The next stage of processing that tree knows only to read
> > > the first node.
> > > As I understood, the nodes are reference counted.
> > > Isn't it therefore more effective to keep it like it is,
> > > or is there a caveeat?
> >
> > You'll have the same node in the tree in multiple places, usually this will
> > give problems. E.g. at a later stage you will forget about it maybe switch
> > to some custom AST with extra info and get bitten by it, or you add a child
> > to it at a later stage and see it appear in two places. The sky's the limit
> > as Murphy said...
> So then can someone remind me why reference counting is even used?

This is not a reference counting problem. You could create the same problem
with plain pointers. You'll still have two 'pointing entities' pointing to
the same thing in two places in the tree, e.g. are open to all things like
loops in the tree (e.g. exit tree), neverending algorithms on the tree etc.
Operating on one of the nodes will change the tree in two places maybe even
making loops or destroying the tree in two parts. In this particular case
the risk might not be there as is but as the code evolves this may happen.

> Wouldn't it be better to make each node solely responsible for its children
> (i.e. the children are deleted either when they are removed or when the
> parent is destroyed).

Would require rewriting the whole support lib is my guess. Or at least
reevaluating every line that works with nodes. Rewriting is something I
want to do but will not be this year I guess.

> It just seems that a different memory manage/garbage
> collection scheme would map much better given that nodes cannot be shared.

Nodes can be shared they just can't be shared among tree nodes because the
risk is high that you make a more general graph than a tree with as result
that the support code and treewalkers aren't guaranteed to work anymore.

> > dupTree is the right thing here I guess (look for it in ASTFactory.hpp) if
> > you know for sure that there's only one node a simple clone might do the
> > trick as well.
> I would point out that I created my own stand-alone implementation.  I
> found no reason for ASTFactory to be involved in this process.

It depends a bit on what you're doing I guess. If you want to be able to
read/write trees from/to disk then you'll need something that knows all the
nodes and their factories, hence the superfactory.

> This is much more convenient because, as I recall, dupTree is a non-static
> method of ASTFactory.  Having to instantiate an ASTFactory just to call
> dupTree is just too inconvenient (and totally unnecessary).

I agree dupTree and a lot of its friends should not be in the factory. This
is carry over from the java support lib and I didn't want to break the
interface yet. In the future this might all be implemented as templates.


    ---- Ric Klaren ----- j.klaren at utwente.nl ----- +31 53 4893722  ----
     Innovation makes enemies of all those who prospered under the old
   regime, and only lukewarm support is forthcoming from those who would
               prosper under the new. --- Niccolò Machiavelli


Your use of Yahoo! Groups is subject to http://docs.yahoo.com/info/terms/ 

More information about the antlr-interest mailing list