Yuku
Traverse
The traverser walks a tree depth-first and calls a visitor’s hooks at each node, in one of four modes. From JavaScript, see walk.
| Mode | Tracks | Returns | ctx.tree |
|---|---|---|---|
basic | the path from the root | nothing | *const ast.Tree |
scoped | the path and lexical scopes | a ScopeTree | *const ast.Tree |
semantic | scopes, symbols, and references | the Semantic model | *const ast.Tree |
transform | the path | nothing | *ast.Tree |
pub fn traverse(comptime V: type, tree: *ast.Tree, visitor: *V) std.mem.Allocator.Error!Result
basic.traverse takes a *const ast.Tree. Every mode can fail with error.OutOfMemory, since a subtree deeper than 256 levels walks iteratively.
Visitors
A visitor is a struct of pub hooks named after node tags. This one counts functions.
const std = @import("std");
const parser = @import("parser");
const ast = parser.ast;
const traverser = parser.traverser;
const basic = traverser.basic;
const Counter = struct {
functions: u32 = 0,
pub fn enter_function(self: *Counter, _: ast.Function, _: ast.NodeIndex, _: *basic.Ctx) traverser.Action {
self.functions += 1;
return .proceed;
}
};
var counter = Counter{};
try basic.traverse(Counter, &tree, &counter);
pub fn enter_<tag>(self: *V, payload: ast.<Payload>, index: ast.NodeIndex, ctx: *Ctx) Action
pub fn exit_<tag>(self: *V, payload: ast.<Payload>, index: ast.NodeIndex, ctx: *Ctx) void
pub fn enter_node(self: *V, data: ast.NodeData, index: ast.NodeIndex, ctx: *Ctx) Action
pub fn exit_node(self: *V, data: ast.NodeData, index: ast.NodeIndex, ctx: *Ctx) void
- An enter hook returns an
Action, orstd.mem.Allocator.Error!Actiontotryan allocation. - A misspelled hook or a wrong payload type is a compile error. A hook that is not
pubis never called. - At each node,
enter_noderuns, thenenter_<tag>unlessenter_nodereturned something other than.proceed, then the children in field order, thenexit_<tag>andexit_node.
Action | Effect |
|---|---|
.proceed | Walk into the children |
.skip | Pass over the children. The node’s exit hooks still run. |
.stop | End the walk. Exit hooks still run for the node and its ancestors. |
Every mode’s context has ctx.tree and ctx.path.
ctx.path.parent() // ?ast.NodeIndex
ctx.path.ancestor(n) // with the current node at 0
ctx.path.ancestors() // an iterator from the current node up
ctx.path.depth() // 1 at the root
Scoped
ctx.scope follows the walk into and out of every scope, and the walk returns every scope it saw as a ScopeTree. A node’s own scope is current in its enter hook. This lint counts each var that escapes its block.
const scoped = traverser.scoped;
const VarInBlock = struct {
found: u32 = 0,
pub fn enter_variable_declaration(self: *VarInBlock, decl: ast.VariableDeclaration, _: ast.NodeIndex, ctx: *scoped.Ctx) traverser.Action {
if (decl.kind == .@"var" and ctx.scope.get(ctx.scope.current).kind == .block) self.found += 1;
return .proceed;
}
};
var lint = VarInBlock{};
const scopes = try scoped.traverse(VarInBlock, &tree, &lint);
ctx.scope.current // the current ScopeId
ctx.scope.get(id) // its Scope, with kind, hoist_target, and flags.strict
ctx.scope.ancestors(id) // an iterator from a scope up
Semantic
The walk builds the Semantic model and returns it. A binding is declared after its node’s enter hook, and references resolve when the walk ends, so a visitor collects nodes and queries the model after. This one finds the types a file imports.
const sem = traverser.semantic;
const TypeNames = struct {
allocator: std.mem.Allocator,
nodes: std.ArrayList(ast.NodeIndex) = .empty,
pub fn enter_identifier_reference(self: *TypeNames, _: ast.IdentifierReference, index: ast.NodeIndex, ctx: *sem.Ctx) std.mem.Allocator.Error!traverser.Action {
if (ctx.inTypePosition()) try self.nodes.append(self.allocator, index);
return .proceed;
}
};
var names = TypeNames{ .allocator = tree.allocator() };
const semantic = try sem.traverse(TypeNames, &tree, &names);
for (names.nodes.items) |node| {
const id = semantic.symbolOf(node) orelse continue; // a global type
if (semantic.symbol(id).flags.intersects(parser.semantic.Symbol.any_import)) std.debug.print("imported\n", .{});
}
ctx.inTypePosition()
ctx.inTsNamespace()
ctx.scope // as in scoped
ctx.symbols.binding(scope, name) // ?SymbolId, a name declared so far
ctx.symbols.ownBinding(scope, name)
ctx.symbols.symbol(id)
The model covers the whole tree, so .skip and .stop only mute the visitor.
Transform
ctx.tree is mutable, and the walker reads a node again after its enter hook, so it walks a replacement. This one turns price + tax into price * tax.
const transform = traverser.transform;
const AddToMultiply = struct {
pub fn enter_binary_expression(_: *AddToMultiply, expr: ast.BinaryExpression, index: ast.NodeIndex, ctx: *transform.Ctx) traverser.Action {
if (expr.operator == .add) {
ctx.tree.setData(index, .{ .binary_expression = .{
.left = expr.left,
.right = expr.right,
.operator = .multiply,
} });
}
return .proceed;
}
};
var rewrite = AddToMultiply{};
try transform.traverse(AddToMultiply, &tree, &rewrite);
- The tree’s building and editing calls work during the walk.
- A node whose tag a hook changes is walked, and exited, as its new kind.
- After wrapping a node in a new parent, return
.skip, so the walk does not enter it again.
Modes compose as passes, such as a transform and then a semantic walk of its result.
Your own mode
A mode is a context type over one walker.
pub fn walk(comptime C: type, comptime V: type, visitor: *V, ctx: *C, comptime options: traverser.Options) std.mem.Allocator.Error!void
A context has a tree field, a *ast.Tree to edit or a *const ast.Tree to read, and an optional path: traverser.NodePath, which its enter and exit push and pop. The walk calls these optional methods around the visitor’s hooks, with the tag known at compile time.
pub fn enter(self: *C, comptime tag: ast.NodeTag, index: ast.NodeIndex, data: ast.NodeData) std.mem.Allocator.Error!void
pub fn post_enter(self: *C, comptime tag: ast.NodeTag, index: ast.NodeIndex, data: ast.NodeData) std.mem.Allocator.Error!void
pub fn exit(self: *C, comptime tag: ast.NodeTag, index: ast.NodeIndex, data: ast.NodeData) void
.whole_tree = true calls the context for every node, even under a .skip, so a context that builds a model of the whole tree sees all of it. basic.zig is the smallest mode.