Proposal: Improve ast.Walk and ast.Visitor

[diegommm]

Problem

There are a few minor extensibility issues with the current implementation:

• A visitor cannot stop ast.Walk: even if it finished its work it will still run for the reminder of the tree. If e.g. I want to make a silly visitor to answer the question "was this identifier used?" then it will keep running. It would be useful to be able to tell ast.Walk to stop earlier to be more efficient.
• A visitor cannot return an error: a common problem when customizing a language is that you may want to walk an AST and fail on some custom logic. For example, if you want regular expressions to be compiled and cached when the whole expression is compiled for performance, then you can make a visitor that returns an error if the matches operator was used and its RHS is not a constant string. In this case, it would be useful that a visitor can tell that.
• There is coupled, scattered and hidden code about visitors: for instance, the operator overloading patcher visitor implements additional methods (ShouldRepeat() bool and Reset()) that are checked in private code in checker, so checker is still coupled with patcher by the means of knowing this hidden methods.
• A visitor could make no changes but the AST is still re-checked: writing custom visitors can be more expensive than needed since each run will trigger the checker. For simple visitors that only want to check something instead of changing the tree, this can be excessive. It would be interesting to be able to avoid re-checking when not needed.

These items can make the language more difficult to maintain on the long run because if more features are needed, then more hidden methods are added, then more internal coupling, etc.

Proposed solution

There is no need to break the current API, many users may already rely on their visitors running correctly, and this proposal is rather light on outwards changes. With these changes, expr will be more extendable and new features will be easier to implement. Also, users will not need to hook into hidden logic. This will encourage users to implement their own logic instead of further expanding the current base language, which can make it more easily maintainable on the long run.

Changes to provide the ability to stop ast.Walk

package ast

type Visitor interface { // same as today
	Visit(node *Node)
}
type StoppableVisitor interface {
	Visit(node *Node) (stop bool)
}
type StoppableVisitorFunc func(node *Node) (stop bool) // trivial adapter

func (f StoppableVisitorFunc) Visit(node *Node) (stop bool) {
	return f(node)
}

func StoppableVisitorFromVisitor(v Visitor) StoppableVisitor {
	return StoppableVisitorFunc(func(node *Node) (stop bool) {
		v.Visit(node)
		return false // never stop, always keep going as it is today
	})
}

func Walk(node *Node, v Visitor) {
	vv, _ := v.(StoppableVisitor)
	if vv == nil {
		vv = StoppableVisitorFromVisitor(v)
	}
	StoppableWalk(vv)
}

func StoppableWalk(node *Node, v StoppableVisitor) {
	// this func doesn't need to return anything so just
	// wrap the actual recursive one
	walk(node, v)
}

func walk(node *Node, v StoppableVisitor) (stop bool) {
	// move the logic of the current Walk here, but check if the
	// bool was true then exit instead of continuing
}

Changes to provide additional state

The following changes would allow checker

package ast

type ResultsVisitor interface {
	StoppableVisitor
	// Results provides additional details about the outcome
	// that can be used in other packages of expr. We don't
	// need to add e.g. a "Reset" method because reset logic
	// could also be implemented in this same method, so
	// footprint is small.
	Results() (VisitorResults, error)
}

type VisitorResults struct {
	// ChangedState determines if the tree was changed, in
	// which case the checker will be ran afterwards.
	ChangedState bool
	// ShouldRepeat determines if the visitor should be run
	// again, similar to the current "ShouldRepeat" method
	ShouldRepeat bool
	// no other things for now, but being a struct makes it
	// easy to further expand it for new features without
	// requiring big changes
}

package checker

// Checker is now reusable.
type Checker struct {
	Config *conf.Config
	// internal stuff
}

func (c *Checker) CheckAndRunVisitors(tree *parser.Tree) error {
	// For every visitor run, see if it implements ResultsVisitor
	// to see if ChangedState requires re-checking of the tree.
	// Also see if ShouldRepeat is true, then do the appropriate.
	// Also, if it returns an error, then end and return it.
	// If the visitor does not implement ResultsVisitor, then assume
	// that we don't need to repeat BUT assume that state was changed
	// as ChangedState is just a particular optimization for the case
	// that we didn't change state.
}

[diegommm]

@antonmedv I'm willing to work on this if you agree on it. Please, let me know your comments and if you would like to change anything so we agree before I do any work.

[antonmedv]

Let me think about it. I understand the problem and I like that, but I think we need something simple and more intuitive.