Traverse

Visitors

A visitor is a struct with enter_<tag> and exit_<tag> methods, named after node tags. Each hook receives its node’s payload already unpacked. This one counts functions in basic mode.

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);
std.debug.print("{d} functions\n", .{counter.functions});

A misspelled hook or a wrong payload type is a compile error. enter_node and exit_node fire for every node, with the ast.NodeData payload. The walk is depth-first with siblings in source order. An enter hook returns a traverser.Action, .proceed to walk into the children, .skip to pass over them, or .stop to end the walk, and may return it in an error union to try an allocation. An exit hook returns nothing.

Every mode’s context has ctx.tree and ctx.path. The path knows the current node’s parent(), its ancestor(n) with the current node at 0, its ancestors() from the current node up, and its depth().

Scoped

ctx.scope follows the walk into and out of every scope, with currentScope(), hoistTarget(), and isStrict(). This lint finds each var that escapes the block it is written in.

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.currentScope().kind == .block) self.found += 1;
        return .proceed;
    }
};

var lint = VarInBlock{};
const scopes = try scoped.traverse(VarInBlock, &tree, &lint);

On { var b; } for (var i = 0;;) {} it finds b and i. The walk also returns every scope it saw as a ScopeTree, and an empty visitor returns just that.

Semantic

The walk builds the Semantic model as it goes and returns it. During the walk, ctx.inTypePosition() and ctx.inTsNamespace() tell where it is, ctx.parentOf(node) climbs from any node already entered, and ctx.symbols.binding(scope, name) finds a name declared so far. References resolve when the walk ends, so a visitor collects nodes and asks 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
    const symbol = semantic.symbol(id);
    if (symbol.flags.intersects(sem.Symbol.any_import)) {
        std.debug.print("imported type {s}\n", .{tree.string(symbol.name)});
    }
}

On import type { User } from "./user"; type Id = string; let user: User, id: Id; it prints User. semantic.analyze is this mode with a visitor that reports the early errors.

Transform

A transform hook rewrites the tree in place. The walker re-reads a node after its enter hook, so it walks the replacement. This one turns total = price + tax into total = 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, such as addNode, addString, and setIdentifierName, work during the walk. After wrapping a node in a new parent, return .skip, so the walker does not enter the moved node again. Codegen prints the result.

ast.Tree.initEmpty starts a tree from nothing, so a transpiler can walk an input tree with full semantics while building a separate output tree. Modes compose as passes, such as a transform followed by a semantic walk over its result.

Your own mode

The four modes are four context types over one walker. A context of your own has a tree field and enter(index, data) and exit(index, data) methods, and traverser.Layer runs them around your visitor’s hooks.

var layer = traverser.Layer(MyCtx, V){ .inner = &visitor };
try traverser.walk(MyCtx, traverser.Layer(MyCtx, V), &layer, &ctx);

basic.zig is the smallest mode, a context that tracks the path.