[antlr-interest] Re: Should dup() and dupXXXX() have shallow or deep clone semantics?
lgcraymer
lgc at mail1.jpl.nasa.gov
Tue Nov 12 13:32:30 PST 2002
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/
More information about the antlr-interest
mailing list