Two Ways to Walk: The Visit and Traverse Systems

Every tool in Oxc's pipeline needs to walk the AST. The linter examines each node for violations. The transformer rewrites nodes in place. The minifier repeatedly optimizes until nothing changes. But these tools have different requirements: the linter only reads the AST, while the transformer must mutate it. And the transformer needs to know about parent nodes, while the linter usually doesn't.

Oxc addresses these different needs with two distinct traversal systems: Visit (read-only, generated) and Traverse (mutable, with ancestry access). Both are generated by ast_tools — a build-time code generator that reads annotated AST definitions and emits thousands of lines of visitor code. Understanding these systems is essential for writing linter rules, transforms, or any code that processes Oxc's AST.

The Visit/VisitMut System

The Visit and VisitMut traits live in crates/oxc_ast_visit and are entirely generated. The crate's source is just a few lines at crates/oxc_ast_visit/src/lib.rs:

mod generated {
    pub mod visit;
    pub mod visit_mut;
}
pub use generated::{visit::*, visit_mut::*};

(The actual file also includes an optional utf8_to_utf16 module behind a feature flag, but the core is the two generated visitor modules.)

The generated Visit trait has one method per AST node type (e.g., visit_program, visit_expression, visit_binding_identifier). Each method has a default implementation that recursively walks into the node's children — the "walk" functions. Users override only the methods for node types they care about.

classDiagram
    class Visit {
        +visit_program(&Program)
        +visit_statement(&Statement)
        +visit_expression(&Expression)
        +visit_binding_identifier(&BindingIdentifier)
        +visit_identifier_reference(&IdentifierReference)
        ...hundreds more...
    }
    class SemanticBuilder {
        Implements Visit
        "Builds scope tree"
    }
    class LintRule {
        "Uses run() per node"
    }
    Visit <|.. SemanticBuilder
    note for LintRule "Lint rules use run(AstNode)\nnot Visit directly"

The SemanticBuilder (from Article 3) is the primary user of Visit. It implements dozens of visitor methods to construct scopes, bind symbols, and resolve references.

How Lint Rules Use the Visitor

Lint rules don't implement Visit directly — they receive individual AstNode values via their run() method (as we'll see in Article 5). But the linter infrastructure uses Visit internally to walk the AST and dispatch nodes to relevant rules.

VisitMut is the mutable counterpart, providing &mut references to each node. It's used in cases where you need to mutate the AST but don't need ancestry information.

The Traverse System: Mutable Walking with Ancestry

The Visit system has a fundamental limitation: when you're inside a visitor method, you can only see the current node and its children. You can't look up to see the parent or grandparent. For many transformations, you need that context. For example, converting arguments to a rest parameter requires knowing whether the current function is an arrow function.

The Traverse system in crates/oxc_traverse solves this. Its design is explained in the extensive module documentation at crates/oxc_traverse/src/lib.rs#L1-L61:

sequenceDiagram
    participant T as Traverse impl
    participant W as walk_* functions
    participant S as Ancestor Stack
    participant N as AST Node
    
    W->>S: push(ProgramWithoutBody)
    W->>N: raw pointer to body[0]
    W->>T: enter_statement(&mut stmt, ctx)
    Note right of T: ctx.parent() returns<br/>ProgramWithoutBody
    T->>T: transform statement
    W->>T: exit_statement(&mut stmt, ctx)
    W->>S: pop()

The Traverse trait provides enter_* and exit_* hooks for each node type. The enter hook fires before walking into children, and exit fires after. A TraverseCtx is passed to each hook, providing:

• Ancestry access: ctx.parent(), ctx.ancestor(n) — returns Ancestor enum variants
• Scoping data: ctx.scoping, ctx.current_scope_id()
• AST builder: ctx.ast — for allocating new AST nodes in the arena

The TraverseCtx is defined in crates/oxc_traverse/src/context/mod.rs#L33-L60 and provides both "direct" and "namespaced" APIs:

Direct	Namespaced
ctx.parent()	ctx.ancestry.parent()
ctx.current_scope_id()	ctx.scoping.current_scope_id()
ctx.alloc(thing)	ctx.ast.alloc(thing)

The namespaced APIs exist to solve a borrow checker problem: if you hold an &Ancestor from ctx.parent(), you can't also mutate the scope tree through ctx, because both borrow ctx. The namespaced form lets you borrow ctx.ancestry and ctx.scoping independently.

The Safety Model: Raw Pointers and Ancestor Exclusion

The Traverse system's safety model is the most intricate part of Oxc's codebase. The problem: Rust's aliasing rules say you can't hold a &mut reference to a child and a & reference to its parent simultaneously, because the parent owns the child. But that's exactly what a mutating traversal with ancestry access needs to do.

The solution uses two techniques:

1. Raw Pointers in Walk Functions

The generated walk_* functions don't create & or &mut references as they descend the tree. They use raw pointers, which bypass aliasing checks. References are only created at the boundary — when calling enter_* and exit_*:

// Conceptual simplified version of a walk function
unsafe fn walk_binary_expression(traverser, node_ptr, ctx) {
    // Push ancestor - NO reference created to parent
    ctx.push_stack(Ancestor::BinaryExpressionLeft(...));
    
    // Get raw pointer to left child - NO reference to parent
    let left_ptr = addr_of_mut!((*node_ptr).left);
    
    // NOW create &mut reference, only to the child
    walk_expression(traverser, left_ptr, ctx);
    
    ctx.pop_stack();
}

2. Ancestor Exclusion

Each Ancestor variant deliberately excludes the field that is currently being traversed. For BinaryExpression, there are separate variants:

• BinaryExpressionLeft — provides access to right and operator, but NOT left
• BinaryExpressionRight — provides access to left and operator, but NOT right

This is not just a naming convention — the types genuinely don't have methods to access the excluded field. If you try to access bin_expr_ref.right() when you entered through the right side, the code won't compile:

fn enter_numeric_literal(&mut self, node: &mut NumericLiteral<'a>, ctx: &mut TraverseCtx<'a>) {
    if let Ancestor::BinaryExpressionRight(bin_expr_ref) = ctx.parent() {
        // This compiles - left is a different branch
        let _ = bin_expr_ref.left();
        
        // This would NOT compile - right is where we came from
        // let _ = bin_expr_ref.right();
    }
}

flowchart TB
    subgraph "BinaryExpression (parent)"
        OP[operator: ==]
        LEFT[left: IdentifierReference]
        RIGHT[right: NumericLiteral]
    end
    
    subgraph "Ancestor::BinaryExpressionRight"
        A_OP[✅ operator]
        A_LEFT[✅ left]
        A_RIGHT[❌ right - excluded]
    end
    
    RIGHT -.->|"traversing into"| A_RIGHT
    style A_RIGHT fill:#f99
    style A_OP fill:#9f9
    style A_LEFT fill:#9f9

Tip: The Traverse system's safety depends entirely on the codegen being correct. The module docs explicitly warn against hand-editing generated files. Always use just ast to regenerate and never manually modify files in crates/oxc_traverse/src/generated/.

Code Generation with ast_tools

Both Visit and Traverse — along with CloneIn, TakeIn, Dummy, GetSpan, and layout assertions — are generated by the ast_tools pipeline. This is an ahead-of-time code generator (not a proc macro) defined in tasks/ast_tools/src/main.rs.

The pipeline proceeds in five phases:

flowchart LR
    L[Phase 1: Load] --> P[Phase 2: Parse]
    P --> R[Phase 3: Resolve]
    R --> G[Phase 4: Generate]
    G --> W[Phase 5: Write]
    
    L -.-|"Read .rs files,\nfind #[ast] types"| L
    P -.-|"Parse type defs,\nbuild TypeDefs"| P
    R -.-|"Link types via TypeId,\nresolve attributes"| R
    G -.-|"Run Generators\nand Derives"| G
    W -.-|"Write output\nto disk"| W

Phase 1 (Load): All .rs source files in crates depending on oxc_ast_macros are read and parsed with syn. Types with #[ast] are identified and assigned a TypeId.

Phase 2 (Parse): Each type's syn AST is parsed in full to produce StructDef or EnumDef, capturing all fields, variants, and their types.

Phase 3 (Resolve): Types are linked together — each field's type is resolved to a TypeId. Custom attributes like #[visit], #[scope], and #[generate_derive] are parsed.

Phase 4 (Generate): Generators and derives run, producing code for:

• Visit and VisitMut traits (in crates/oxc_ast_visit)
• Traverse trait, walk_* functions, and Ancestor types (in crates/oxc_traverse)
• CloneIn, TakeIn, Dummy, GetSpan, ContentEq implementations
• Layout assertions ensuring #[repr(C)] types have expected sizes
• SemanticBuilder scope creation hooks

Phase 5 (Write): Generated code is written to src/generated/ directories in the relevant crates and checked into git.

Why Ahead-of-Time Instead of Proc Macros?

The ast_tools documentation explains two advantages:

1. Compile time: Proc macros run on every cargo build. ast_tools runs only when you change AST types (just ast). For a project with hundreds of generated trait impls, this saves significant build time.

2. IDE navigability: Generated code is just .rs files checked into git. You can click through definitions in your IDE, read the generated code, and grep for implementations — none of which work well with proc macro output.

The #[ast] attribute macro at crates/oxc_ast_macros/src/lib.rs#L12-L47 itself does very little at compile time — it adds #[repr(C)] and a no-op #[derive(Ast)] that enables helper attributes. The real work happens at just ast time.

Traverse vs Visit: When to Use Which

Feature	Visit/VisitMut	Traverse
Direction	Top-down	Top-down (enter + exit)
Mutation	VisitMut: yes	Yes
Ancestry access	No	Yes (parent, grandparent, ...)
Scoping data	No	Yes (via TraverseCtx)
Primary users	SemanticBuilder, lint infrastructure	Transformer, Minifier
Safety model	Standard Rust references	Raw pointers + type-level exclusion

If you're analyzing the AST without modifying it, use Visit. If you're transforming the AST and need parent context, use Traverse. If you're modifying the AST but don't need ancestry, VisitMut is simpler than Traverse.

What's Next

With the traversal systems understood, Article 5 will put them to work in the linter — tracing how oxlint orchestrates parallel file processing, how lint rules use the Rule trait to hook into the visitor, and how LintContext provides rules with everything they need to detect and fix problems.