[antlr-interest] Cloning/dup* seriously broken for C++???

[Tiller, Michael (M.M.)]

Ric,

  Thanks for your suggestions, but perhaps I wasn't really clear about the issue (see my previous message titled "Cloning" for a few other details).

  I'm not having a problem with the tree construction per se.  I can build the tree exactly the way I want it.  The problem is in the reference counting data structures.  In my previous example, every time I would dup/clone the "pre" or "type" data structures, a copy would get made but the "RefAST" structure would always point back to the original?!?  This messed up the data structures.

  In looking through the list, I found an email that had a useful suggestion.  If you look at the definition of BaseAST's copy constructor in antlr-2.7.2, you find this:

BaseAST::BaseAST(const BaseAST& other)
: AST(other) // RK: don't copy links! , down(other.down), right(other.right)
{
}

  Note that you have correctly pointed out that when making a copy of a node, you do not want to copy its down and right links.  That wouldn't make sense since this a copy.  But, it appears that there was something forgotten here.  The "ref" member inherited from "AST" should also not be copied since "ref" points back to the ASTRef that is looking at the node.  The AST copy constructor preserves the value of "ref".  THIS IS A MISTAKE (as far as I can tell).

  Here is a typical scenario:

 
declaration
  : pre:prefix type:type list:component_list
    {
      for(antlr::RefAST cur=#list;
          cur!=antlr::nullAST;
          cur=cur->getNextSibling()) {
              cur->addChild(#([DECL_TYPE_INFO, "TypeInfo"],
                      astFactory->dupTree(#pre),
                      astFactory->dupTree(#type))));
     }
    }
  ;

The #pre tree does indeed get duplicated.  That isn't the problem (I can see this from the output of my clone() method).  The problem is that dup_pre has the same "ref" value that #pre.  When you try to wrap an ASTRef around dup_pre, the ASTRef tries to be clever and sees that "ref" for dup_pre is !=NULL (this is the mistake...it should be because nothing, up to this point, has actually referenced dup_pre).  Seeing that "ref" is non-NULL it says "Let me be clever and get rid of this unnecessary duplicate and go back and reference the value of "ptr" that this "ref" is using...clever, but wrong.

I think there is a simple fix for this.  Note that BaseAST cannot set the value of "ref" to be zero and in fact calls the AST copy constructor.  If you look at the AST copy constructor, you see this:

  AST(const AST& other) : ref(other.ref->increment()) {}

Yikes!!!  This is a copy!  It shouldn't use the value of ref from "other".  Instead, it should initialize ref as if this was a completely new AST, e.g.

  AST(const AST& other) : ref(0) {}

I didn't come up with all of this on my own.  I found most of this in a previous discussion in the newsgroup.

Looking at your development snapshot, I see this has been addressed.  I've patched 2.7.2 and so far (fingers crossed) I have been able to dup* things OK.  Of course, if I have any other problems I'll be sure to make everyone aware of them. :-)

--
Mike

> -----Original Message-----
> From: Ric Klaren [mailto:klaren at cs.utwente.nl]
> Sent: Thursday, June 19, 2003 6:19 AM
> To: antlr-interest at yahoogroups.com
> Subject: Re: [antlr-interest] Cloning/dup* seriously broken for C++???
> 
> 
> Hi,
> 
> On Wed, Jun 18, 2003 at 04:15:16PM -0400, Tiller, Michael 
> (M.M.) wrote:
> > I have spent my entire day trying to figure out how to do 
> something that
> > should be really simple.  I've got a declaration statement, 
> essentially it
> > looks like this:
> >
> > declaration
> >   : pre:prefix type:type list:component_list
> >   ;
> >
> > Now I need to iterate over component_list and add a *COPY* 
> of prefix and
> > type as children of each node in component_list.  I have 
> tried a dozen ways
> > of doing this and none of them have worked.  Here are a few 
> examples:
> >
> >      for(antlr::RefAST 
> cur=#list;cur!=antlr::nullAST;cur=cur->getNextSibling()) {
> >                 cur->addChild(#([DECL_TYPE_INFO, "TypeInfo"],
> >                         astFactory->dupTree(#pre),
> >                         astFactory->dupTree(#type))));
> >      }
> >
> >      for(antlr::RefAST 
> cur=#list;cur!=antlr::nullAST;cur=cur->getNextSibling()) {
> >                 cur->addChild(#pre->clone());
> >                 cur->addChild(#type->clone());
> >      }
> >
> >      for(antlr::RefAST 
> cur=#list;cur!=antlr::nullAST;cur=cur->getNextSibling()) {
> >                 cur->addChild(#pre);
> >                 cur->addChild(#type);
> >      }
> 
> It looks like you're modifying the tree while you're stepping 
> through it?
> I'm not sure if that will work... Try turning off AST 
> generation for the
> declaration rule. Then collect the trees generated by 
> prefix/type/comp_list
> (basically what you're already doing now). Then use a loop to 
> insert copies
> of all the parts you are glueing together. Something like 
> (abbreviated the
> duptrees):
> 
> RefAST nchild = #( duptree(cur), duptree(#pre), duptree(#type) );
> #declaration = #( nullAST, #declaration, nchild );
> 
> The above may need some tweaking. I'm not a big star in writing AST
> construction stuff. The nullAST thing adds them as siblings 
> to the returned
> tree if I recall right.
> 
> Also grab the print_tree template from
> 
> http://wwwhome.cs.utwente.nl/~klaren/antlr/print_tree.h
> 
> It prints out a more or less readable dump of an AST tree so 
> you can see
> what happens while copying, or between operations.
> 
> Other idea is to open up the component_list rule safes you the manual
> traversal of the list:
> 
> declaration!
>   : pre:prefix type:type ( comp:component
> 		{
> 			#declaration = #( nullAST, #declaration,
> 						#( 
> duptree(#pre), duptree(#type), duptree(#comp) ) );
> 		}
> 		)+
>   ;
> 
> > All these problems see to stem from the (sorry I have to 
> say it) extremely
> > complicated family of types including (but not limited to): ASTRef,
> > ASTRefCount, RefAST, RefMyCustomNodeAST, AST, BaseAST, 
> CommonAST, etc. :-)
> 
> I'm afraid we have to live with those in the 2.x.x series.
> 
> > I tried the recently announced development snapshot but I 
> couldn't get it
> > to run.  Does anybody have a fix for this issue?!?  I'm 
> completely stuck!!!
> > I cannot move forward on this project until I have some 
> kind of workaround.
> 
> The dev snapshot contains some fixes to the RefCounter. So 
> I'd definitely
> grab it (non serious though only memory leak if I recall 
> right). Might look
> at a diff between the release version you have now and the 
> support lib and
> manually port over.
> 
> Add default comment about bugreports. Compiler/system/error 
> output. This is
> not helping I'm afraid.
> 
> Cheers,
> 
> Ric
> --
> -----+++++****************************************************
*+++++++++-------
>     ---- Ric Klaren ----- j.klaren at utwente.nl ----- +31 53 
> 4893722  ----
> -----+++++****************************************************
*+++++++++-------
>   "You know how to use that thing?" [pointing to the sword]
>   "Sure.. The pointy end goes into the other guy."
>   --- The Mask of Zorro
> 
>  
> 
> Your use of Yahoo! Groups is subject to 
http://docs.yahoo.com/info/terms/ 


 

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