Read OSS
ziglang/zig

ソースコードからZIRへ：Zigコンパイラのフロントエンド

•中級

前提知識

  • ›第1回：Zigコンパイラのアーキテクチャ
  • ›トークナイズと再帰降下構文解析の基本的な概念を理解していること

ソースコードからZIRへ：Zigコンパイラのフロントエンド

第1回で見たように、Zigコンパイラのフロントエンドは src/ ではなく lib/std/zig/ に置かれています。これは偶然の産物ではなく、意図的な設計判断です。zig fmt、Zig Language Server（ZLS）、その他のツールが、Sema やコード生成、リンカを持ち込むことなく、同一のトークナイザ・パーサ・AstGen コードを共有できるようにするためです。本記事では、生のソースバイト列が、セマンティック解析に送り込まれるフラットな命令ストリーム — ZIR (Zig Intermediate Representation) — へ変換されるまでの流れを追っていきます。

なぜフロントエンドは lib/std/zig/ に置かれているのか

コンパイラのフロントエンドは、トークンストリーム・AST・ZIR という3つの成果物を順に生成します。これら3つの表現はすべて、標準ライブラリ内で定義・生成されます。

flowchart LR
    subgraph "lib/std/zig/ (shared)"
        TOK["tokenizer.zig"] --> PARSE["Parse.zig"]
        PARSE --> AST["Ast.zig"]
        AST --> AG["AstGen.zig"]
        AG --> ZIR["Zir.zig"]
    end

    subgraph "Tools"
        FMT["zig fmt"]
        ZLS["ZLS"]
        AC["zig ast-check"]
    end

    subgraph "src/ (compiler only)"
        SEMA["Sema.zig"]
    end

    TOK -.->|"reuses"| FMT
    AST -.->|"reuses"| FMT
    AST -.->|"reuses"| ZLS
    ZIR -->|"feeds into"| SEMA

このアーキテクチャにより、zig fmt はコンパイラと同じパーサを使ってソースコードを解析・整形できるため、フォーマットの一貫性が保証されます。ZLS はコンパイラのオーバーヘッドを一切受けずに AST を構築し、IDE 機能を実現できます。そして zig ast-check は Sema を起動せずに AstGen を実行してエラーを検出できます。

ここで重要なのは、ZIR に至るまでのすべての処理が 型なし であるということです。セマンティック解析も、型の解決も、comptime の評価も一切行われません。これらのフェーズが純粋な構文レベルの変換であるからこそ、安全に共有できるのです。

トークナイズ：ソースバイト列からトークンストリームへ

lib/std/zig/tokenizer.zig のトークナイザは、生のUTF-8ソースバイト列を Token 値のストリームに変換します。各トークンは驚くほどコンパクトな構造を持っています。

pub const Token = struct {
    tag: Tag,
    loc: Loc,

    pub const Loc = struct {
        start: usize,
        end: usize,
    };
};

トークンが持つのは、トークンの種類を示すタグと、元のソース上のバイト範囲だけです。ファイル冒頭にある Tag 列挙型には、すべての Zig キーワード（12行目の StaticStringMap でマッピング）、演算子、リテラル、句読点が含まれています。

flowchart TD
    SRC["Source: 'const x = 5;'"] --> T1["const → keyword_const"]
    SRC --> T2["x → identifier"]
    SRC --> T3["= → equal"]
    SRC --> T4["5 → number_literal"]
    SRC --> T5["; → semicolon"]

トークナイザは 遅延評価 を念頭に設計されており、メモリの確保もリストの構築も行いません。パーサは next() メソッドを呼び出してソースを1トークンずつ読み進めます。ただし実際のコンパイルパスでは、ランダムアクセスのためにすべてのトークンを事前に MultiArrayList へトークナイズします。後続のフェーズ（AstGen やエラーレポート）が任意のトークン位置にジャンプする必要があるためです。

Tip: キーワードの検索には std.StaticStringMap が使われています。これはコンパイル時に生成されるパーフェクトハッシュマップであり、実行時のハッシュテーブルオーバーヘッドなしでキーワード検出を O(1) で行えます。

パース：トークンからASTへ

lib/std/zig/Parse.zig のパーサは、典型的な再帰降下パーサです。トークンストリームを消費し、lib/std/zig/Ast.zig で定義された AST を生成します。

AST の表現方法は一般的なものとは異なります。ポインタを使ったヒープアロケートのツリーノードではなく、Zig は フラットな multi-array-list を採用しています。

pub const NodeList = std.MultiArrayList(Node);

// Each node has:
//   tag: Node.Tag    — what kind of syntax node
//   main_token: u32  — index into the token list
//   data: Data       — two u32 fields (lhs/rhs or extra indices)

この構造では、すべてのノードが連続した配列に格納され、tag・main_token・data が並列配列（MultiArrayList レイアウト）を形成します。子ノードへの参照はポインタではなく整数インデックスで行われます。子ノードが3つ以上あるノードの場合、data フィールドには別の extra_data: []u32 配列へのインデックスが格納されます。

flowchart TD
    subgraph "Flat AST Layout"
        TAGS["tags:    [fn_decl, block, return, ...]"]
        TOKENS["tokens:  [0, 5, 8, ...]"]
        DATA["data:    [{lhs:1, rhs:2}, ...]"]
        EXTRA["extra_data: [3, 7, 9, ...]"]
    end
    DATA -->|"overflow"| EXTRA

パーサ自体が保持する状態はごくわずかです — gpa アロケータ、ソースバイト列、tokens スライス、そして現在のトークンインデックス tok_i だけです。parseContainerDeclaration・parseExpr・parseStatement などの関数は、文法規則に直接従う形で実装されています。

パーサはエラー回復に対応しています。最初の構文エラーで中断するのではなく、errors: std.ArrayList(AstError) にエラーを記録しながら解析を継続しようとします。不完全・不正なファイルが当たり前の IDE サポートにとって、これは不可欠な特性です。

AstGen：ASTからZIRへ

AstGen は、ツリー構造の AST をフラットな命令ストリームである ZIR へ変換するフェーズです。lib/std/zig/AstGen.zig に実装されており、フロントエンドの中で最も複雑な部分に当たります。

AstGen 構造体は、lowering 処理の間に多くの状態を保持します。

gpa: Allocator,
tree: *const Ast,
nodes_need_rl: *const AstRlAnnotate.RlNeededSet,
instructions: std.MultiArrayList(Zir.Inst) = .{},
extra: ArrayList(u32) = .empty,
string_bytes: ArrayList(u8) = .empty,
source_offset: u32 = 0,
source_line: u32 = 0,
source_column: u32 = 0,

source_offset・source_line・source_column の各フィールドは、ソースファイル内の位置を追跡するカーソルを形成します。このカーソルは O(N²) の行スキャンを避けるために lowering 処理全体を通じて 維持され続けます — 大きなファイルに対して効果を発揮する巧妙な最適化です。

AstGen は、AST レベルには存在しないいくつかの重要な概念を導入します。

  1. 結果ロケーション: 式が「自分の結果をどこに書き込むか」を知っているという Zig の result location セマンティクスが、nodes_need_rl アノテーションセットを通じて ZIR にエンコードされます。

  2. スコープ追跡: AstGen はレキシカルスコープを管理し、どの名前がスコープ内にあるか、break/continue/return のターゲットがどのように解決されるかを追跡します。

  3. Comptime アノテーション: comptime ブロックや式に ZIR 内でマークが付けられ、Sema がそれらをコンパイル時に評価すべきであると認識できるようになります。

  4. ソースハッシュの計算: AstGen は宣言本体のインクリメンタルハッシュを計算し、ZIR に格納します。このハッシュは後でインクリメンタルコンパイルシステムによって利用されます。

flowchart TD
    AST["AST Node: fn_decl"] --> SCOPE["Push function scope"]
    SCOPE --> PARAMS["Generate ZIR for parameters"]
    PARAMS --> BODY["Generate ZIR for body"]
    BODY --> RET["Handle return type / result location"]
    RET --> POP["Pop function scope"]
    POP --> ZIR["ZIR instructions appended"]

ZIRのデータ構造：Instructions・Extra・String Bytes

ZIR のメモリレイアウトは、フロントエンドパイプラインの集大成です。lib/std/zig/Zir.zig で定義されており、3つの並列データストアで構成されています。

instructions: std.MultiArrayList(Inst).Slice,
string_bytes: []u8,
extra: []u32,

instructions はコアとなる配列です。各 Inst は、命令の種類を識別する tag（enum(u8)）と data: u32 ペイロードを持ちます。タグによってデータの解釈方法が決まります — 直接のオペランドであることも、extra へのインデックスであることも、別の命令への参照であることもあります。

extra は可変長のサイドカーです。1つの u32 に収まらないデータを持つ命令は、追加フィールドを保持する extra へのインデックスを格納します。たとえば、関数呼び出し命令は呼び出し先を data フィールドに格納しますが、引数リストは extra に格納されます。

string_bytes は、識別子・文字列リテラル・エラーメッセージなど、すべての文字列データをプールします。命令はこの配列へのインデックスで文字列を参照します。

flowchart LR
    subgraph "ZIR Memory Layout"
        direction TB
        I["instructions\ntag: [alloc, load, call, ...]\ndata: [0, 3, 42, ...]"]
        E["extra\n[arg0_ref, arg1_ref, ret_type, ...]"]
        S["string_bytes\n['m','a','i','n',0,'x',0,...]"]
    end
    I -->|"data index"| E
    I -->|"string index"| S
    E -->|"string index"| S

ZIR をディスクにキャッシュする際には、3つの配列の長さと、キャッシュ無効化のためのファイルメタデータ（inode、サイズ、mtime）を記録する Header がプレフィックスとして付加されます。

このフラットな表現は、重要なパフォーマンス特性を持っています。ツリーとは異なり、ZIR は Sema が順次処理でき、キャッシュローカリティも優れています。ポインタを辿る必要がなく、すべての参照は u32 インデックスです。また、ファイル全体の ZIR を連続したブロブとしてディスクへ書き込み・読み出しできます。

Tip: ZIR は自己完結型です。一度生成されれば、Sema が必要とするすべてを内包し、AST・トークンリスト・ソースバイト列への参照は一切持ちません。これはファイルのヘッダコメントに明記されています："machine code, without any memory access into the AST tree token list, node list, or source bytes."

AstGenの起動：ファイル更新からZIR生成まで

フロントエンドとコンパイラをつなぐのが src/Zcu/PerThread.zig です。updateFile() 関数は、単一のソースファイルに対するフロントエンドパイプライン全体を調整します。

sequenceDiagram
    participant Comp as Compilation
    participant PT as PerThread
    participant FS as FileSystem
    participant FE as Frontend (lib/std/zig/)

    Comp->>PT: updateFile(file_index, file)
    PT->>FS: stat + open source file
    PT->>FE: tokenize (source → tokens)
    FE-->>PT: Token list
    PT->>FE: parse (tokens → AST)
    FE-->>PT: Ast
    PT->>FE: AstGen (AST → ZIR)
    FE-->>PT: Zir
    PT->>PT: Cache ZIR to disk

updateFile 関数はまずファイルの stat を確認し、前回のコンパイル以降にソースが変更されたかどうかを調べます。ファイルが変更されておらず、キャッシュされた ZIR が存在する場合は、フロントエンドパイプライン全体をスキップできます。これがインクリメンタルコンパイルの第一層です — Sema が介入する前の段階で、変更のないファイルはキャッシュされた ZIR を再利用します。

AstGen が実行されると、生成された ZIR は Zcu 上の global_zir_cache と local_zir_cache の両ディレクトリにキャッシュされます。次回以降のコンパイルでは、キャッシュのチェックがトークナイズよりも前に行われるため、変更のないファイルにはフロントエンドのコストがまったく発生しません。

次回予告

ここまで、ソースバイト列がトークナイズ・パース・AstGen を経て ZIR へと変換される流れを追ってきました。第3回では、lib/std/zig/ から src/ へと境界を越え、型なし ZIR を完全に型付けされた AIR へ変換するコンパイラの心臓部 — 37,000行を超える Sema — を探っていきます。また、コンパイル全体のすべての型と値が u32 インデックスとして存在する汎用ストア、InternPool についても深く掘り下げていく予定です。