[Internals] Make it easier to walk the AST

[ffrank]

Versions:

• mgmt version (eg: mgmt --version): 0.0.26

• operating system/distribution (eg: uname -a): any

• golang version (eg: go version): any

Description:

It is currently hard to work with the AST on a data structure level. For example, running a search to present the node path to a specific node is Very Hard. It is Very Hard to generate a nice topological representation of the tree, etcpp.

The only useful means we have is the interfaces.Node.Apply() method, but it is very basic, does not give any context information to the func/lambda it accepts, limits us to depth first traversal, and may have other important limitations.

The tree currently is very heterogenous, with each tree node having a rather distinct type, with very little abstraction. This is not a bad design per se, but poses some challenges.

I would like to have some discussion of which code additions or changes could make sense in order to help with this.

[ffrank]

One approach that I could see is to have an additional data structure that just represents the tree, e.g.

type TreeNode struct {
    Content Node
    Children []TreeNode
}

So all or Stmt and Expr nodes end up dangling on such TreeNodes, rather than forming the proper tree. It is not clear to me whether we still have pointers to semantical children, i.e.

type StmtIf struct {
	Condition    interfaces.Expr
	conditionPtr interfaces.Func // ptr for table lookup
	ThenBranch   interfaces.Stmt // optional, but usually present
	ElseBranch   interfaces.Stmt // optional

or rather replace all of this with a pointer to the TreeNode, and then access the children through that.

type StmtIf struct {
    tree *TreeNode
}

This probably does not work for node types that have more chaotic types of children, but I don't have enough of an overview that I could tell from here.

The nice thing about such a structure is that we can implement many recursive functions like findSpecificASTNode with very little effort.

[ffrank]

A different approach could be to apply the visitor pattern to AST nodes.

I.e., we create visitor interface for AST nodes, extend all Stmt and Expr types with methods for accepting visitors, and then build visitors that work on the tree.

In my mind, that should make it easier to do more powerful things with the existing Apply method, because we can apply a visitor to each node in turn.

This might still make it difficult to implement common tree algorithms, and lend itself more to other problem areas. I'm not sure, would probably have to build a PoC and play with it to get a feel. Just throwing it out there for now.

[ffrank]

FWIW this can be closed rather soon if it feels like a burden. I mainly want these thoughts to be out there and written down.

[purpleidea]

We already have an Apply() function on the AST which I thought was enough. If you have a patch needing something else, please send the patch and the patch using that patch. I'm not against this but I don't see it (likely my bad here) at the moment. I'm going to close for now, we can re-open if there's a patch.