AST を歩く2つの方法: Visit と Traverse システム

Oxc のパイプラインに含まれるツールはすべて、AST を走査する必要があります。リンターは各ノードを検査して違反を見つけ、トランスフォーマーはノードをその場で書き換え、ミニファイアーは変化がなくなるまで繰り返し最適化します。しかし、これらのツールが求めるものはそれぞれ異なります。リンターは AST を読むだけで十分ですが、トランスフォーマーは AST を変更しなければなりません。また、トランスフォーマーが親ノードの情報を必要とするのに対し、リンターでは通常不要です。

こうした異なるニーズに応えるため、Oxc は2つの走査システムを提供しています。Visit（読み取り専用・生成コード）と Traverse（mutable・祖先アクセス付き）です。どちらも ast_tools によって生成されます。ast_tools はビルド時に動作するコードジェネレータで、アノテーション付きの AST 定義を読み込んで数千行のビジターコードを出力します。リンタールールやトランスフォームを書く場合、あるいは Oxc の AST を処理するコードを書く場合には、これらのシステムを理解しておくことが不可欠です。

Visit/VisitMut システム

Visit トレイトと VisitMut トレイトは crates/oxc_ast_visit に定義されており、すべてコード生成によって作られます。クレートのソースは crates/oxc_ast_visit/src/lib.rs のわずか数行だけです。

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

（実際のファイルにはフィーチャーフラグで制御される utf8_to_utf16 モジュールも含まれていますが、核心は生成された二つのビジターモジュールです。）

生成された Visit トレイトには、AST ノード型ごとに 1 つのメソッドがあります（例: visit_program、visit_expression、visit_binding_identifier）。各メソッドにはデフォルト実装があり、子ノードを再帰的に走査する「walk 関数」を呼び出します。利用者は関心のあるノード型のメソッドだけをオーバーライドすればよいのです。

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"

第 3 回で解説した SemanticBuilder が Visit の主な利用者です。スコープの構築・シンボルのバインド・参照の解決のために、数十のビジターメソッドを実装しています。

リンタールールがビジターを使う方法

リンタールールは Visit を直接実装しません。代わりに、run() メソッドを通じて個別の AstNode を受け取ります（詳細は第 5 回で説明します）。ただし、リンターのインフラ側は内部的に Visit を使って AST を走査し、関連するルールにノードをディスパッチしています。

VisitMut は Visit の mutable 版で、各ノードへの &mut 参照を提供します。祖先情報は不要だが AST を変更したい場合に使われます。

Traverse システム: 祖先アクセス付きの mutable 走査

Visit システムには根本的な制約があります。ビジターメソッドの中で見えるのは、現在のノードとその子孫だけです。親や祖父母を上方に参照することはできません。しかし多くの変換では、そのコンテキストが必要になります。たとえば arguments を rest パラメータに変換するには、現在の関数がアロー関数かどうかを知る必要があります。

crates/oxc_traverse の Traverse システムはこの問題を解決します。その設計は 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()

Traverse トレイトは各ノード型に対して enter_* と exit_* のフックを提供します。enter フックは子ノードへの走査が始まる前に、exit フックは走査が終わった後に呼び出されます。各フックには TraverseCtx が渡され、以下の情報にアクセスできます。

• 祖先アクセス: ctx.parent()、ctx.ancestor(n) — Ancestor enum のバリアントを返す
• スコープデータ: ctx.scoping、ctx.current_scope_id()
• AST ビルダー: ctx.ast — アリーナに新しい AST ノードを確保する

TraverseCtx は crates/oxc_traverse/src/context/mod.rs#L33-L60 で定義されており、「ダイレクト」と「名前空間付き」の 2 種類の API を提供しています。

ダイレクト	名前空間付き
ctx.parent()	ctx.ancestry.parent()
ctx.current_scope_id()	ctx.scoping.current_scope_id()
ctx.alloc(thing)	ctx.ast.alloc(thing)

名前空間付き API が存在する理由は、借用チェッカーの問題を回避するためです。ctx.parent() から &Ancestor を受け取っている間は、ctx 全体を借用しているため、ctx 経由でスコープツリーを変更することができません。名前空間付き形式を使えば ctx.ancestry と ctx.scoping を独立して借用できるので、この問題を解決できます。

安全性モデル: 生ポインタと Ancestor の除外

Traverse システムの安全性モデルは、Oxc のコードベースの中で最も複雑な部分です。問題の核心は、Rust のエイリアシングルールにあります。ある子ノードへの &mut 参照と、その親ノードへの & 参照を同時に保持することはできません。なぜなら、親が子を所有しているからです。しかし、祖先アクセス付きの mutable 走査には、まさにそれが必要です。

この問題を解決するために、二つの手法を組み合わせています。

1. walk 関数における生ポインタの使用

生成された walk_* 関数は、ツリーを降りていく過程で & や &mut 参照を作りません。代わりにエイリアシングチェックを回避できる生ポインタを使います。参照が作られるのは境界部分だけ — つまり enter_* と 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 の除外

各 Ancestor バリアントは、現在走査中のフィールドを意図的に除外した構造になっています。BinaryExpression には次の二つのバリアントが用意されています。

• BinaryExpressionLeft — right と operator にはアクセスできるが、left にはアクセスできない
• BinaryExpressionRight — left と operator にはアクセスできるが、right にはアクセスできない

これは単なる命名規則ではありません。型として除外されたフィールドにアクセスするメソッドが存在しないため、コンパイラがそれを強制します。たとえば右辺側から入ってきているときに bin_expr_ref.right() を呼び出そうとすると、コンパイルエラーになります。

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

ヒント: Traverse システムの安全性は、codegen が正しく動作していることに完全に依存しています。モジュールドキュメントでも、生成ファイルを手動で編集しないよう明示的に警告しています。crates/oxc_traverse/src/generated/ 内のファイルは絶対に手動で変更せず、必ず just ast で再生成してください。

ast_tools によるコード生成

Visit と Traverse — さらに CloneIn、TakeIn、Dummy、GetSpan、レイアウトアサーションも含めて — はすべて ast_tools パイプラインによって生成されます。これはプロシージャルマクロではなく、tasks/ast_tools/src/main.rs で定義されたアヘッドオブタイム (ahead-of-time) のコードジェネレータです。

パイプラインは 5 つのフェーズで構成されています。

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

フェーズ 1 (Load): oxc_ast_macros に依存するクレートの .rs ソースファイルをすべて読み込み、syn でパースします。#[ast] が付いた型を識別し、TypeId を割り当てます。

フェーズ 2 (Parse): 各型の syn AST を完全にパースし、すべてのフィールド・バリアント・型を含む StructDef または EnumDef を生成します。

フェーズ 3 (Resolve): 型同士を結びつけます。各フィールドの型を TypeId に解決し、#[visit]、#[scope]、#[generate_derive] といったカスタムアトリビュートをパースします。

フェーズ 4 (Generate): ジェネレータとderiveが実行され、以下のコードが生成されます。

• Visit と VisitMut トレイト（crates/oxc_ast_visit 内）
• Traverse トレイト、walk_* 関数、Ancestor 型（crates/oxc_traverse 内）
• CloneIn、TakeIn、Dummy、GetSpan、ContentEq の実装
• #[repr(C)] 型が期待するサイズを持つことを確認するレイアウトアサーション
• SemanticBuilder のスコープ生成フック

フェーズ 5 (Write): 生成されたコードを各クレートの src/generated/ ディレクトリに書き出し、git にコミットします。

なぜプロシージャルマクロではなくアヘッドオブタイムなのか

ast_tools のドキュメントでは、この選択の利点として二点が挙げられています。

1. コンパイル時間: プロシージャルマクロは cargo build のたびに実行されます。ast_tools は AST の型を変更したとき（just ast）にしか実行されません。数百もの生成トレイト実装を持つプロジェクトでは、これによってビルド時間を大幅に削減できます。

2. IDE での探索性: 生成されたコードは git にコミットされた通常の .rs ファイルです。IDE で定義にジャンプしたり、生成コードを直接読んだり、実装を grep で検索したりできます。これらはプロシージャルマクロの出力ではなかなか実現できないことです。

crates/oxc_ast_macros/src/lib.rs#L12-L47 の #[ast] アトリビュートマクロ自体はコンパイル時にほとんど何もしません。#[repr(C)] を付加し、ヘルパーアトリビュートを有効にするだけの #[derive(Ast)] を追加するのみです。実際の処理はすべて just ast 実行時に行われます。

Traverse vs Visit: どちらを使うべきか

機能	Visit/VisitMut	Traverse
方向	トップダウン	トップダウン（enter + exit）
変更	VisitMut: 可	可
祖先アクセス	不可	可（親・祖父母など）
スコープデータ	不可	可（TraverseCtx 経由）
主な利用者	SemanticBuilder、リントインフラ	Transformer、Minifier
安全性モデル	標準的な Rust 参照	生ポインタ + 型レベルの除外

AST を変更せずに解析するだけなら Visit を使いましょう。AST を変換しつつ親コンテキストも必要なら Traverse が適しています。変更は必要だが祖先情報は不要な場合は、Traverse より VisitMut のほうがシンプルです。

次回予告

走査システムの全体像を理解したところで、第 5 回ではこれらを実際にリンターの中で活用する場面を追っていきます。oxlint がどのようにファイルの並列処理を制御しているか、リンタールールが Rule トレイトを使ってビジターにどうフックするか、そして LintContext がルールに必要なすべての情報をどのように提供するかを解説します。