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.

ModeTracksReturnsctx.tree
basicthe path from the rootnothing*const ast.Tree
scopedthe path and lexical scopesa ScopeTree*const ast.Tree
semanticscopes, symbols, and referencesthe Semantic model*const ast.Tree
transformthe pathnothing*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, or std.mem.Allocator.Error!Action to try an allocation.
  • A misspelled hook or a wrong payload type is a compile error. A hook that is not pub is never called.
  • At each node, enter_node runs, then enter_<tag> unless enter_node returned something other than .proceed, then the children in field order, then exit_<tag> and exit_node.
ActionEffect
.proceedWalk into the children
.skipPass over the children. The node’s exit hooks still run.
.stopEnd 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.