[antlr-interest] On trees and JavaBeans, part 2: tree creation

[Loring Craymer]

> -----Original Message-----
> From: Scott Stanchfield [mailto:scott at javadude.com]
> Sent: Wednesday, April 20, 2005 4:24 AM
> To: 'Loring Craymer'; antlr-interest at antlr.org
> Subject: RE: [antlr-interest] On trees and JavaBeans, part 2: tree
> creation
> 
> To avoid folks whining about the length of digest posts, I'm going to
> generically address your misunderstandings...
> 
> 1) You need to examine the code I posted last night.
> 
> 2) TreeNode and TreeModel SHOULD NOT be the *actual* data. The should just
> be used to ADAPT existing data (again, see the example code -- the GUI I
> create and whose components I display in the Jtree *Do not* implement
> TreeNode...)
> 
> 3) ANTLR ISN'T THE ONLY WAY TO CREATE TREES.

Of course not.  For arbitrary trees, such as we are discussing, there are
two logical models:
	1.)  Every node is a (possibly empty) vector of children.  This is
the logical model that Swing uses.
	2.)  Every node has siblings and children. This is the model that
ANTLR uses.

Each of these models has advantages and disadvantages.  Model 1 is optimized
for random access to children and static construction (have all children
known; then allocate the vector); model 2 is optimized for sequential access
of children, and freeform construction of trees (add a node whenever it
makes sense).  Imposing a model 1 view on ANTLR would impose a performance
penalty.   Adaptors can coerce either model into the other model view.

ANTLR sequentially accesses the children of a node and does freeform
construction.  Ter made the right design decision in the first place;
switching to a model which would force suboptimal implementation without
compelling justification is wrong.

> 
> I don't want to have to force my data to "be" antlr objects, NOR do I want
> to create an adapter PER NODE. Using my proposal, we would be able to
> process ANY existing tree (without cycles)
> 
> 4) You're thinking of a single-pass *program*, which seems to be the same
> box Ter is thinking in.
> (This is for all of your "the garbage collector is reasonably optimized"
> lines. I'm talking about scenarios where the garbage collector will run
> hundreds or more times while the program is running)

Sorry, I thought you were considering real world applications.  A Java-based
enterprise server will run thousands of transactions per second and hundreds
to thousands of object create/deletes per transaction.  Garbage collection
algorithms and implementations have gotten quite robust over the years.
J2EE works only because garbage collectors can handle an indefinite number
of create/deletes over the lifetime of a single application.

The GC is a critical part of any Java implementation; I would be surprised
if any vendor did not do exhaustive stress testing of the GC--at least
enough to reassure any big customers.

> To make the problem clear:
> 
> I want to use this for processing an eclipse AST, as do many of the folks
> I've chatted with on the eclipse mailing lists. ASTs will be generated
> hundreds or thousands of times during an eclipse session.
> 
> Every time you pause during typing, an AST is created for syntax
> highlighting and error analysis. I want to create ONE additional object to
> interpret that AST with an antlr tree parser for some additional anaysis.
> I've brought up on the eclipse mailing lists using ANTLR which was met
> with
> great enthusiasm, but it's WAY too much overhead with the ANTLR 2.0 AST
> node
> req or 3.0 carrier/payload design. It would require an adapter PER eclipse
> AST node.
> 
> There's no way I'd propose making eclipse ASTs implement ANTLR's AST
> interface. I'd be laughed out of the mailing list, because everyone there
> knows adapters are the right approach, and that this is only feasible if
> ANTLR trees work the same way Swing trees do.

As I pointed out above, Swing assumes a logical tree structure that differs
from ANTLR's.  Changing ANTLR's logical model to a structure that is less
optimal for tree walking does not make sense.  Incorporating an unneeded
adaptor into ANTLR makes even less sense.  It adds no new
functionality--since you can get adaptor functionality through an
implementation of the Carrier interface--and adds an extra object reference
and method call to getNextSibling() or getFirstChild().  Good design
practice is to optimize for the common cases first and to provide support
for the abnormal cases second.

Oddly enough, if you are going to be able to use ANTLR 3 for walking a
foreign tree, you should be able to write an AST class as an adaptor (per
node) for that foreign tree in ANTLR 2.  The only thing stopping you is fear
of the garbage collector.

> 5) As for Swing You TRULY do not get Swing's tree.
> 
> TreeNodes are **optional**. YOU DON'T NEED THEM TO DO JTREE. See the
> example
> code I posted for how you SHOULD do adaptation of an existing structure.
> (See the GoodExample.java)

You mean the line that reads
		f.getContentPane().add(new JScrollPane(new JTree(new
DefaultTreeModel(new ComponentTreeNode(ftp)))));

coupled with the definition of ComponentTreeNode which begins

public class ComponentTreeNode implements TreeNode {

or is there some other code that I should be looking for TreeNodes in?


> You have a CHOICE in swing:
> 
> a) Use the existing DefaultTreeModel and adapt existing data using
> TreeNodes
>    Cost: an extra tree node adapter PER real node
> 
> b) Use the existing DefaultTreeModel and change your existing data to
> implement TreeNode
>    Cost: modification of real data nodes, injecting a Swing dependency
> into
> them
>          * you may not have access to modify them
>          * I think it's bad design to integrate the presentation model
>            (TreeModel/TreeNode) with the real model
> 
> c) Use your own TreeModel (without TreeNodes) to adapt the entire tree
>   Cost: ONE new object. The data doesn't change
> 
> > > Jtree  --> TreeModel --> Your Real Data
> > Which implements the TreeNode interface ...
> 
> NO!!!!! The data DOES NOT NEED TO. You obviously didn't look at my example
> code.
> 

One of us didn't.

> 
> Ter -- please look at the example I posted. I hope you "get it" and
> implement this for 3.0. Otherwise I'll need to maintain a mod to ANTLR
> that
> I'd really rather not.
> 
> This is no extra cost to ANTLR or use of ANTLR ASTs, but it opens up ANTLR
> a
> whole new realm of application.

No it doesn't.  Arbitrary trees can be handled with ANTLR 2.  All you need
to do is to write an ASTWrapper class which implements the AST interface and
wraps nodes returned by getFirstChild() or getNextSibling(), wrap the tree
root with an ASTWrapper, and then invoke a method on the wrapper.  [Well,
you do have to set the default AST type in the tree walker also.]

--Loring

> 
> Frustrated,
> -- Scott
> 
> 
>