[antlr-interest] Re: Should dup() and dupXXXX() have shallow or deep clone semantics?

[lgcraymer]

Ric--

My tree rewrite support does use the dup methods, and that will get 
folded in at some point.  They are needed--in some tree grammars, it 
is desirable to recognize anything (".") and then do a dupTree for the 
output copy--and they would otherwise need to be AST methods.

Micheal--

Backward links in a tree (or cross-links, for that matter) are 
incompatible with tree-rewriting and would be bad news for any 
tree-transformaing tree grammar.  Setting them would have to be 
deferred until the final syntax tree is constructed or the developer 
would have to add some significant machinery to deal with them, so 
this is probably a non-issue.

In a implicitly garbage-collected language, the "dup" methods only 
need to support deep cloning of the AST structure (right and down 
fields), I believe.  Any other pointers can probably be 
inherited--they are not part of the tree structure and would be passed 
unchanged through syntax tree transformation unless explicitly 
modified in actions.

I suspect that Ric's reason for cloning other fields in ASTs is 
because of the explicit garbage collection problem--adding smart 
pointers for strings takes up just as much space as does a copy of the 
string object and costs in terms of maintainability.

--Loring

--- In antlr-interest at y..., Ric Klaren <klaren at c...> wrote:
> Hi,
> 
> On Tue, Nov 12, 2002 at 04:12:05PM -0000, micheal_jor wrote:
> > OK. I'll have a quick look at how C++ does this. Was this feature
> > already present in 2.7.2a2 or should I be looking at 2.7.2a4 only?
> 
> 2.7.2a2 should have it.. Maybe a small bugfix here and there not 
sure.
> 
> > 1. the nodes have direct or indirect links (via object reference
> > chains) to really big object graphs such as the symbol table.
> 
> In that case the user would have to supply a good copy constructor 
that
> does the right thing. The dupXXX's in C++ just call the clone method 
of a
> AST and that one generally uses a copy constructor.
> 
> > 2. the nodes have bidirectional links - i.e. parent<->child and
> > sibling1<->sibling2..<->..siblingN - that will effectively turn 
every
> > dup()/dupXXX() into a full tree copy.
> 
> Hmmm standard antlr has no back links. And probably the dup 
algorithms
> can't handle those properly. And I don't know what the use is of 
dupping to
> a level higher than the node you are starting the duplicate with. 
Generally
> when you dup a bit I'd suspect you're only interested in the 
subtree.
> 
> Anyway on a different line of thought the dup methods IMHO don't 
belong in
> the factory anyway. No part of antlr's generated code uses them as 
well
> (AFAIK). It's a bunch of convenience functions. The combination of 
2.7.0/1,
> dupXXX and heterogeneous ASTs was even pretty much broken anyway 
(C++ maybe
> even other codegen).
> 
> > It's a worry that the use of these methods will incur a severe
> > memory/space cost essentially. A deep clone would always deep copy
> > all such linked objects too.

ANTLR always copies during tree transformation--the memory cost is 
there already.

> 
> That's one of the risks of duplicating stuff. Then again ANTLR 
generated
> code doesn't use the dup methods. And it's probably not a good idea 
to
> invest a lot of time in making them 100% idiot proof, they should be
> AST/BaseAST/CommonAST proof (well at least that's my view of them), 
then
> again it's not my time ;)
> 
> Cheers,
> 
> Ric
> --
> 
-----+++++*****************************************************+++++++
++-------
>     ---- Ric Klaren ----- klaren at c... ----- +31 53 4893722  ----
> 
-----+++++*****************************************************+++++++
++-------
>   Chaos often breeds life, when order breeds habit.
>   --- Henry B. Adams, The Education of Henry Adams


 

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