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

[Scott Stanchfield]

> Hi Guys,
> 
> I like the flexibility of swing's tree interface, but I don't 
> like the need to pass in the parent to get the child.
> 
> Tree t = tree.getChild(parent, i);
> 
> just seems less pleasant than
> 
> Tree t = parent.getChild(i);

"Less pleasant"? Dude... (I find it more pleasant b/c I can turn anything
I'd like into a tree. Think of the <genie>PHENOMINAL COSMIC POWER... itty
bitty living space</genie>

Think about the flexibility. The code is generated, so it's no burden to the
grammar writers.

It still allows use of an AST node interface if you have the default
implementation just do things like:

  public Object getChild(Object parent, int num) {
    return ((AST)parent).getChild(num);
  }
  public Object getChildCount(Object parent) {
    return ((AST)parent).getChildCount();
  }
  public int getTokenType(Object parent) {
    return ((AST)parent).getToken().getType();
  }
  public int getTokenLine(Object parent) {
    return ((AST)parent).getToken().getLine();
  }  ...


So you get the best of both worlds. Anyone can still use AST as individual
nodes, but this approach opens it up the ability for any custom tree
implementation one may want w/o requiring node-level decorations (or
implementation of the AST interface)

> Also, you still need a tree node of some kind to actually 
> implement a tree.  Perhaps Tree and TreeNode?

Nope. All you need is Object. By referring to it indirectly through the
model, you have access to all of the same data you would as if it were a
specialized tree node.

For creation, the factory just returns Objects. So you make calls like

  Object node = factory.createNode(Token1);
  Object child = factory.createNode(Token2);
  factory.addChild(node, child);

The implementation of the factory decides how the data is stored, and gives
it back when asked through the model interface.

Pure, simple brilliance.

Can you imagine the types of tools people could create with this
<genie>PHENOMINAL COSMIC POWER... itty bitty living space</genie>

> I'm open to suggestions still because the payload model 
> requires an extra node just to wrap the pointer (as an 
> "adaptor") to another kind of tree node.  For example, if you 
> have a DOM tree or something that doesn't directly satisfy 
> the Tree interface, you must essentially make a duplicate, 
> parallel tree that points node-for-node from the ANTLR tree 
> into the DOM tree.
> 
> The main issue for me is: when do you really want to walk a "foreign" 
> (non-ANTLR constructor) tree?

When the tree already exists or is built by something else.

Prime example for me is the ASTs that eclipse generates. I'd love to use a
treewalker to work with them.

And you mentioned DOM... This would be so much nicer for DOM work... 

> It happens sometimes, but 
> usually because you're building your own trees with actions, 

I've only used trees once, and I doubt everyone uses them. Even those who
use them could benefit from the ability to have very flexible custom nodes.

> which you could make implement the Tree interface easily.  It 
> would be fairly rare don't you think to want to walk a 
> totally unrelated data structure?

Not at all. I've had at least three separate projects I've worked on this
year that I've tried to use the tree walker against existing data (Eclipse
ASTs, DOM parsing, and something else I cannot mention...)

You're thinking too close to your tool, with a single type of application in
mind. Head down to Haight-Ashbury and take a whiff into some mind expansion,
dude... ;)


> The payload thing works GREAT in most cases as it just points 
> at the associated token :)

Only if you use ANTLR ASTs, which I find lacking unfortunately. (I never
really liked the first/sib approach, and I'm not sure what's in 3.0). The
Swing folks hit the nail on the head with TreeModel. I've used it over and
over for doing some really cool things.

For example, I wrote a tool a while back that displays the components
comprise a GUI as a Jtree. See (http://javadude.com/misc/le1). Not released
yet b/c I was doing some things that the JRE license prohibits :( but I
recently figured out some alternatives and after the ANTLR plugin I'll try
to release it.

For this tool, I was able to just implement a single TreeModel, that
reinterpreted getChild, getChildCount, etc.  For example (from memory):

  private Object root;
  public Object getRoot() { return root; }
  Object getChild(Object node, int n) {
    if (node instanceof Container)
      return ((Container)node).getChildren()[n];
    return null;
  }

I could then set the root object in the tree model and the JTree walks the
tree model starting at the root and poof! Component list in a JTree. Very
easy.

If they hadn't implemented Swing this way, I would have had to have an
adapter for each component in the GUI, and each adapter would have to create
child adapters. Something like

  public class ComponentNode implements TreeNode {
    private Component comp;
    public ComponentNode(Component c) { comp = c; }
    public Object getChild(int n) {
      if (comp instanceof Container) {
        Component kid = ((Container)comp).getChildren().[n];
        return new ComponentNode(kid);
      }
      return null;
    }
    ...
  }


Much less elegant, and consumes a lot more RAM, requires extra garbage
collection.

Fortunately Swing lets us do this either way.

That's what I'm asking here.

1) Have an ASTModel interface that defines the node navigation and necessary
data access against Objects
2) Define an ASTFactory interface that creates and manipulates just Objects
3) Define AST interface that represents an ANTLR AST node
4) Define a default implementation of ASTModel that translates model calls
into AST node calls
5) Define default implementation(s) of AST as needed by ANTLR
6) Define default implementation(s) of ASTFactory as needed by ANTLR

After that, anyone can use any AST they would like, not just at the node
level.

Nifty, eh?

If you'd like me to take a pass at tweaking your existing AST setup into
this to give you a better idea of how well it works, let me know. It should
only take an hour methinks...

(I am the pattern master, after all ;) )

Later,
-- Scott