go: go/ast: provide AST Rewrite functionality (ast.Walk is not good enough)
This has come up again and again. While it’s easy to traverse the AST (ast.Walk, ast.Inspect), it’s not easily possible to use those for general tree rewrites w/o significant amount of work.
For instance, if we wanted to rewrite all expressions (ast.Expr) of a certain kind into something else, ast.Walk and ast.Inspect would need to consider every node that contains ast.Expr fields separately, rather than just look at nodes that satisfy ast.Expr.
AST rewriters exist in other packages; most notably perhaps in gofmt (for gofmt -r); that one is reflection-based. Reflection-based approaches tend to be general, but also hard to understand, and slower than necessary.
API starting point:
// An ApplyFunc is invoked by Apply for each node, before and/or after
// the node's children. See Apply for the interpretation of the return
// value.
//
// The node is given by the node pointer's address addr which makes it
// possible for an ApplyFunc to rewrite the node. The node's parent is
// the node containing the *addr. If the node is part of a list, index
// identifies its position in that list. Index is < 0 otherwise.
type ApplyFunc func(parent Node, index int, addr interface{}) bool
// Apply traverses a syntax tree recursively, starting with the node
// identified by parent, index, and addr. See Apply for the meaning
// of these arguments.
//
// If pre is not nil, it is called for each node before its children
// are traversed (pre-order). If the result of calling pre is false,
// no children are traversed, and post is not called for the node.
//
// If post is not nil, it is called for each node after its children
// were traversed (post-order). If the result of calling post is false,
// traversal is terminated and Apply returns immediately.
func Apply(parent Node, index int, addr interface{}, pre, post ApplyFunc) {
About this issue
- Original URL
- State: closed
- Created 8 years ago
- Reactions: 33
- Comments: 41 (37 by maintainers)
Commits related to this issue
- go/ast: implement Apply for general tree traversal/rewriting See also https://github.com/golang/go/issues/17108. — committed to griesemer/dotGo2016 by griesemer 8 years ago
- go/ast: add Apply, for rewriting ASTs Based on work by Robert Griesemer. Fixes #17108 DO NOT REVIEW Work in progress. Notes: Needs more tests, particularly of interactions between modifications, ... — committed to josharian/go by josharian 7 years ago
- go/ast/astutil: add Apply, for rewriting Go ASTs This change implements an AST walker, Apply, with the capability to perform various actions (including rewrites) during the AST walk, in pre- and post... — committed to golang/tools by griesemer 7 years ago
@fatih Thanks for looking into this. A few observations:
Apply
, you don’t need to type-assert on the parent - you can simply use the newSetField
function (also documented in the API):ast.SetField(parent, name, index, <newnode>)
. With that, both versions will be approximately the same amount of code to write.astrewrite
is easier to use in simple cases, but it is almost always more costly: The implementation ofastrewrite
always needs to write back the result returned byrewriteFunc
, and because it’s always anast.Node
there’s always a type assertion needed for the assignment to work (in theastrewrite
implementation) - that’s relatively costly. You have to always do this for every single node even though most nodes are not rewritten. On the other hand, withast.Apply
, theast.SetField
operation is relatively expensive but you only pay when you actually rewrite something.ast.Apply
you have the choice to do the rewriting in pre- or post-order when traversing the tree, which is often important to be able to control - this is not possibly withastrewrite
.To summarize: If you only want to change the name of things, you may not need a rewrite at all. Secondly, while
astrewrite
may be fine for your (more general) use case, it’s probably not sufficiently powerful as a general rewrite mechanism, and likely quite a bit slower than the suggestedast.Apply
. Hope that helps.Anyway, thanks again for investigating!
@smasher164 Because ast.Apply may change the type of the node which cannot be done by modifying a node in place. For instance, an ast.Apply working on an constant expression tree may replace that tree with a single node which is the constant result.
I’m struggling with deleting elements of an AST.
Sample:
Task: eliminate all statements in
f
that are calls to functions starting witha
.I did the obvious thing and wrote a Delete helper, analogous to
SetField
(not thoroughly tested yet):But when you delete an element from a slice, it disrupts the walk that Apply does. In the sample above, the obvious implementation of
pre
deletesa1()
but missesa2()
, because after the deletion ofa1()
, Apply’s index into the BlockStmt is off by one.One option is give ApplyFunc access to Apply’s internal state, perhaps something like this:
@josharian Since it’s basically there (but for tests), I made this a 1.9 item. It should just be in the ast package. We can put it in once the tree opens (which is hopefully soon).