Zig Parser

2022-02-11

Zig パーサー

これはZig コンパイラ内部を扱うシリーズの一部です。

パースは、コンパイルパイプラインにおいてトークン化の次のステップです。パースの役割は、トークンのストリームから抽象構文木を構築することです。以前、Zig がバイト列（ソース）をどのようにトークン列へ変換するかについて書きました。

Zig のパーサーは、Zig のソースツリー内の lib/std/zig/parser.zig にあります。標準ライブラリの一部として std.zig.parse() 経由で利用できます。パーサーはソーステキスト全体を受け取り、std.zig.Ast（lib/std/zig/Ast.zig で定義）を返します。

MultiArrayList

パース以降、Zig コンパイラは MultiArrayList 構造を多用します。パーサーの仕組みや生成される AST の構造を理解するには、MultiArrayList を理解する必要があります。

MultiArrayList を説明する前に、通常の ArrayList（「Multi」の付かない方）について簡単に概観します。ArrayList は値の可変長配列です。配列がいっぱいになると、より大きな新しい配列が確保され、既存の要素が新しい配列にコピーされます。これは一般的な、動的に確保され伸縮する要素のリストです。

例として、次の Zig 構造体を考えてみましょう。

pub const Tree = struct {
    age: u32,       // trees can be very old, hence 32-bits
    alive: bool,    // is this tree still alive?
};

ArrayList では、多数の Tree 構造体は次のように格納されます。

       ┌──────────────┬──────────────┬──────────────┬──────────────┐
array: │     Tree     │     Tree     │     Tree     │     ...      │
       └──────────────┴──────────────┴──────────────┴──────────────┘

それぞれの Tree は 8 バイトのメモリを必要とします。4 つの Tree からなる配列は 32 バイトのメモリになります。

なぜ 8 バイト？ u32 は 4 バイトを必要とします。bool は本来 1 バイトで済みますが、u32 を含む構造体の中にあるため 4 バイトアラインメントが求められ、結果として 4 バイトを占有します（3 バイトが無駄になります）。合計で 8 バイトです。

MultiArrayList も同様に、要素を動的に確保するリストです。ただし、配列リストに格納される型の各フィールドが、それぞれ別の連続した配列に格納されます。これには主に 2 つの利点があります。(1) アラインメントによる無駄なバイトが減ること、(2) キャッシュ局所性が向上することです。これらの利点により、パフォーマンスが向上することがよくあります。

先ほどの Tree 構造体を例にすると、MultiArrayList(Tree) は次のように格納されます。

          ┌──────┬──────┬──────┬──────┐
   age:   │ age  │ age  │ age  │ ...  │
          └──────┴──────┴──────┴──────┘
          ┌┬┬┬┬┐
 alive:   ││││││
          └┴┴┴┴┘

構造体の各フィールドは、別々の連続した配列に格納されます。4 つの Tree からなる配列は 20 バイトを使用し、37.5% のメモリ削減になります。これは複数の配列ポインタのオーバーヘッドを無視した値ですが、そのオーバーヘッドは固定なので、リスト内の要素数が増えるにつれて償却され、この例では合計で 37.5% のメモリ削減になります。

なぜ 20 バイト？ 構造体が分解されるため、age フィールドは 4 バイトを必要とし、例では Tree が 4 つあるので 16 バイトになります。alive フィールドはもはや構造体の一部ではないため 4 バイトアラインメントが不要になり、1 バイトだけで済みます（無駄なバイトはなし）。例では Tree が 4 つあるので、alive は 4 バイトです。両方のフィールドを合計すると 20 バイトになります。

このページでは MultiArrayList がどのように実装されているかには立ち入りません。Zig コンパイラを理解するうえで重要なのは、ほぼすべての構造（トークン、AST ノード、今後の IR ノードなど）が MultiArrayList として格納されているという点だけです。実際のプログラムをコンパイルすると通常数万もの「ノード」が生成されるため、これにより大幅なメモリ節約とキャッシュ局所性の向上がもたらされます。

パーサーの構造

パーサーは Parser という構造体を使って、パース途中の状態を保持します。これは公開されている構造体ではなく、パース処理の内部状態を管理するためだけに使われます。呼び出し元にはパース処理の結果として Ast が返され、これについては後ほど詳しく見ていきます。

執筆時点でのパーサーの構造を以下に示します。状態を機能ごとに区切るため、改行を挿入しています。

const Parser = struct {
    gpa: Allocator,
    source: []const u8,

    token_tags: []const Token.Tag,
    token_starts: []const Ast.ByteOffset,
    tok_i: TokenIndex,

    errors: std.ArrayListUnmanaged(AstError),
    nodes: Ast.NodeList,
    extra_data: std.ArrayListUnmanaged(Node.Index),
    scratch: std.ArrayListUnmanaged(Node.Index),
};

最初のグループには gpa と source が含まれます。これは単一の Zig ファイルのアロケータと元のソースコード全体です。

2 番目のグループでは、token_tags と token_starts がトークン化の分解された結果です。前述のとおり、パーサーはメモリ使用量とキャッシュ局所性を高めるためにデータ指向設計を採用しています。そのため token_tags.len == token_starts.len となります。単に構造体のフィールドが別々の連続したメモリ領域に配置されているだけです。tok_i の値は、パーサーが現在見ているトークンのインデックス（0 から始まります）です。

3 番目のグループはパーサーの実際の作業状態です。ここに Ast の一部となる結果が蓄積されます。この 3 番目のグループはパーサーが構築しているものの中核であるため、非常に重要です。

errors は、パースが進むにつれて発生するエラーのリストです。多くの行儀の良いパーサーは、さまざまなエラー状況でもパースを継続しようとしますが、Zig のパーサーも同様です。Zig のパーサーはこのフィールドにエラーを蓄積し、パースを継続しようとします。
nodes は AST ノードのリストです。最初は空で、パースが進むにつれて徐々に構築されていきます。AST ノードの構造を理解することは極めて重要であり、次のセクションで扱います。
extra_data は、AST ノードが必要とする追加情報のリストです。例えば、構造体の場合、extra_data にはすべての構造体メンバーの完全なリストが含まれます。これもまたデータ指向設計の一例です。別のアプローチとして追加データを直接 Node に持たせる方法も考えられますが、そうすると各 Node がはるかに大きくなり、パーサー全体が遅くなります。
scratch はパーサーで共有される一時的な作業領域で、通常はノードや追加データのための情報を構築するために使われます。パーサーの処理が終わると解放されます。

AST ノードの構造

パースの結果は AST ノードのリストです。AST 自体は依然として木構造ですが、パーサーが返す結果は木を構成するノードのリストです。なぜなら、それがメモリ上での木の表現方法だからです。

AST ノードの構造は、データ自体が MultiArrayList に格納されているうえに、さらに多くの間接参照が重なるため、混乱しやすいかもしれません。このセクションを何度も読み返して、AST ノードの構造を確実に理解することをお勧めします。Zig コンパイラの内部を学ぶ中で、このデータパターンを完全に理解していなかったために多くの問題が生じました。というのも、このパターンはコンパイラの後続のすべての段階で再利用されているからです。

AST の構造は lib/std/zig/Ast.zig にあります。主要な構造体は Node です。

pub const Node = struct {
    tag: Tag,
    main_token: TokenIndex,
    data: Data,

    pub const Data = struct {
        lhs: Index,
        rhs: Index,
    };

    pub const Index = u32;
};

パーサー自体はノードを NodeList、すなわち MultiArrayList(Node) として格納していることに注意してください。つまり Node 構造体の各フィールドが、別々の連続したメモリブロックに分割されて格納されています。概念的にはノードを上記のような単一の構造体として考えることができますが、実際に使われる際にはフィールドは分割されています。

ノードの tag は、取りうる AST ノード種別の enum です。例えば、関数宣言を表す fn_decl、整数リテラルを表す integer_literal、@enumToInt のような組み込み呼び出しを表す builtin_call などがあります。

main_token フィールドは、現時点ではそれほど重要ではありません。これは AST ノードに関連付けられた主要なトークンです。例えば関数宣言であれば fn かもしれません。この値は、AST を構築するために使われたトークンのリストへのインデックスです。

data フィールドは極めて重要です。ここには AST ノードに関連付けられた情報が含まれます。例えば、関数宣言（.tag == .fn_decl）の場合、data には関数プロトタイプと関数本体が格納されます。data フィールドについては次のセクションで詳しく説明します。

AST ノードのデータ

AST ノードの重要な部分は、それに関連付けられたデータです。例えば、関数宣言は関数名、パラメータリスト、戻り値の型、本体などを持ちます。Node 構造体を見ても、この情報がどこにあるのかはすぐには分かりません。

これは、パーサーの仕組みに踏み込む前に理解しておくべき極めて重要な詳細です。そして、コンパイルパイプライン全体の仕組みを知りたい人にとっては、AST が後段の中間形式でも再利用されるパターンを使っているため、特に重要なポイントです。

次の Zig コードに対する関数宣言の AST がどのように構成されるかを見てみましょう。

fn add(a: u8, b: u8) callconv(.C) u8 {
    return a + b;
}

関数宣言

関数宣言のルートとなる AST ノードは fn_decl というタグを持ちます。

fn_decl の場合、data フィールドの lhs には関数プロトタイプ（名前、型情報など）へのインデックスが、rhs フィールドには関数本体へのインデックスが格納されます。これが分かるのは .fn_decl タグの上にあるコメントか、ソースを読むか、あるいはその両方だけです。

この場合の lhs と rhs のインデックス値は、NodeList 内の Node の配列インデックスです。つまり、関数プロトタイプは tree.nodes[lhs] にあります（擬似コードであり、厳密には正しくありません）。

つまりこの場合、data の両方のフィールドが NodeList のインデックスを格納するために使われています。これは data の一つの使い方であり、AST ノードに関する情報がどのように格納されるかを示しています。次に、関数プロトタイプを見て、パラメータリスト、戻り値の型、呼び出し規約をどのように特定するのかを見ていきます。

関数プロトタイプ

関数プロトタイプは tree.nodes[lhs] のノードを読むことで取得できます。このノードはこの場合 fn_proto というタグを持ちます。この種の AST ノードは、パラメータ、呼び出し規約、戻り値の型などに関する情報を格納します。

この特定の AST ノード種別では、lhs と rhs の使われ方が異なります。rhs フィールドは関数宣言と同じように使われ、戻り値の型の式（Zig では直接的な型識別子に加え、comptime に計算されるさまざまな戻り値型の式がサポートされています）の NodeList 内のインデックスを指します。

一方 lhs フィールドは AST ノードを指しません。代わりに、「パーサーの構造」で見た extra_data フィールドへのインデックスです。このインデックスは追加メタデータの開始インデックスです。追加メタデータの長さは AST ノードの種別に基づいて事前に決まっています。つまり、tree.nodes[lhs] ではなく、この場合は tree.extra_data[lhs] となります。重要なポイント：lhs/rhs はノードまたは追加データのいずれかを指す場合があります。

念のため、extra_data の型は []Index です。lhs が tree.extra_data[lhs] として使われているのを見ると、単に別のインデックスを指しているように見えるかもしれません。そうではありません。lhs（.fn_proto の場合）は extra_data 内の最初のインデックスを指しているだけです。続けて読むべきフィールド数はタグに依存します。fn_proto の場合は 6 フィールドです。なぜ 6 なのかは、ソース内のコメントか、エンコードされている構造体を読むことで分かります。

pub const FnProto = struct {
    params_start: Index,
    params_end: Index,
    align_expr: Index,
    addrspace_expr: Index,
    section_expr: Index,
    callconv_expr: Index,
};

つまり tree.extra_data[lhs] が params_start、tree.extra_data[lhs+1] が params_end、というように tree.extra_data[lhs+5] が callconv_expr になるまで続きます。

Ast 構造体は、これをデコードするためのヘルパー関数 extraData() を提供します。AST ツリー tree が与えられた場合、次のメソッドを使って簡単にアクセスできます。以下の例では、idx は .fn_proto ノードが存在するノードリスト内のインデックスです。

const fnData = tree.extraData(idx, FnProto)
fnData.params_start
fnData.callconv_expr
// etc...

では、FnProto 構造体上の param_start、param_end などは何でしょうか。これらは、最初のパラメータ、最後のパラメータなどを表す AST ノードの NodeList インデックスです。これが、関数プロトタイプに関する追加情報をすべて読み取る方法です。

先に警告したように、ここでは多くの間接参照が行われています。しかし、これは今理解しておくことが極めて重要です。そうしないと、パイプラインの後続の段階がさらに混乱を招くことになります。

関数識別子

main_token フィールドは、Node 上でまだ使っていない唯一のフィールドであり、AST ノードによってはデータをアクセスする最後の手段となります。関数プロトタイプの場合、識別子自体（関数名）がどこにも見当たらないことが分かるでしょう。

.fn_proto のような一部の AST ノードは、このために main_token フィールドを使います。fn_proto の main_token は、トークンストリーム内の「fn」キーワードへのインデックスです。Zig では関数識別子は常にこのキーワードの直後に来ます。そのため、main_token + 1 の位置にあるトークンを見ることで関数識別子を抽出できます。これは、コンパイラの後続の段階が識別子を読み取る方法とまったく同じです。

AST データレイアウトのまとめ

Zig コンパイラの残りの部分がどのように動くのかに興味があるなら、この情報格納パターンを深く理解することが極めて重要です。最初の読み取り（あるいは 2 回目や 3 回目の読み取り）では理解しにくいかもしれません。このセクションでは AST のデータがどのように配置されているかを振り返ります。

AST ノードのデータは 3 つの場所にあります。

トークンストリーム（識別子などの値）
ノードリスト（他の AST ノードを見つけるため）
追加データリスト（追加のデータ構造を見つけるため）

後続の AST ノードや追加データ構造は、通常、追加のノード、追加データ構造、またはトークンを指すさらなるインデックスを含んでいます。例えば、fn_decl は fn_proto を指し、fn_proto は追加データの FnProto 構造体を指し、そこからパラメータごとに 1 つの AST ノードを指します。

どのようなデータが利用可能で、どのようにアクセスするかは tag に依存します。lib/std/zig/Ast.zig 内のコメントを読むか、パーサーのソースコードを読んで、どのようなデータが設定されているかを正確に把握する必要があります。

パースの仕組み

内部のパーサー状態と結果として得られる AST の構造をしっかり理解したところで、パーサーが実際にトークンストリームをどのようにパースするのかを学んでいきましょう。

抽象的には、パーサーはトークンストリーム内の現在のトークンを調べて、それを文脈として次に来るべきトークンが何かを判断することで動作します。例えば fn foo というトークンストリームをパースする際、最初に見られるトークンは .keyword_fn で、次に期待されるトークンは識別子です。識別子でなければ、それは構文エラーです。

トークナイザとは異なり、パーサーはトークンの順序が意味をなすかどうかを気にかけます。トークナイザは盲目的にトークンを生成するだけなので、fn pub var foo i32 } { のような不正な構文でも有効なトークンストリームが生成されます。しかしパーサーはそのトークンストリームを見て、それが無意味であるためエラーを生成します。

次に、以下に示す単純な Zig ファイルをパーサーが具体的にどのようにパースするのかを見てみましょう。

var x = 7;

pub fn inc() callconv(.C) void {
  x += 1;
}

Zig ファイルのパース

主要なエントリーポイントは、Zig ファイルの完全なソースコードを受け取る parse() 関数です。これはパーサーの状態を初期化し、Zig ファイルのメンバーをパースするために parseContainerMembers() を呼び出します。Zig ファイルは暗黙的に struct であるため、パーサーは実質的に struct をパースしていることになります。

これにより、現在のトークンを見て次に何を期待すべきかを判断する while ループに入ります。おおよそ次のような構造です。

while (true) {
    switch (p.token_tags[p.tok_i]) {
        .keyword_var => ...
    }
}

現在のトークンに応じて、次に何を期待するかが決まります。最初のトークンは .keyword_var です。なぜなら、サンプルファイルは変数を定義しているからです。これは最終的に変数宣言をパースするための parseVarDecl につながります。もちろん、この時点では comptime、fn、pub など、他にも多くの有効なトークンがあり得ます。

変数宣言のパース

Zig ファイル内で最初に見つかるメンバーは変数宣言です。呼び出しチェーンは最終的に parseVarDecl につながり、そこで初めて AST ノードが作成されるのを見ます。簡略化したバージョンを以下に示します。

fn parseVarDecl(p: *Parser) !Node.Index {
    const mut_token = p.eatToken(.keyword_const) orelse
        p.eatToken(.keyword_var) orelse
        return null_node;

    _ = try p.expectToken(.identifier);
    const type_node: Node.Index = if (p.eatToken(.colon) == null) 0 else try p.expectTypeExpr();
    const init_node: Node.Index = if (p.eatToken(.equal) == null) 0 else try p.expectExpr();

    return p.addNode(.{
        .tag = .simple_var_decl,
        .main_token = mut_token,
        .data = .{
            .lhs = type_node,
            .rhs = init_node,
        },
   });
}

これは最初のトークンを「食べます」：const か var のいずれかです（このパース関数は両方で使われます）。トークンを「食べる」とは、現在のトークンが返され、パーサー状態の tok_i インデックスがインクリメントされることを意味します。const でも var でもなければ、null_node 値が返され、呼び出しチェーンの上位でエラーが生成されます（変数宣言は const または var で始まらなければなりません）。

次に、変数名として identifier を期待します。expectToken 関数は、トークンが identifier でない場合にエラーを返します。例えば var 32 とした場合、パーサーが identifier を期待したが整数リテラルを得たというエラーを作成し格納するのはここです。

次に、いくつかの可能性が考えられます。eatToken を条件分岐で使うことで、次に何をすべきかを判断できます。次のトークンがコロンであれば、型式を期待します。例えば var x: u32 のような場合です。しかし型式は省略可能で、今回の実際の例にはないため、type_node はゼロに設定されます。

次に、次のトークンがイコールかどうかをチェックします。そうであれば、変数初期化式を期待します。今回の変数宣言にはこれがあるため、AST ノードが作成され、ノードリストへのインデックスが返されます。expectExpr の中身はここでは見ません。

これにより、var x、var x: i32、var x: i32 = 42 など、複数の有効な変数宣言構文が生成されることに注目してください。一方で、何が無効なのかにも注目してください。例えば var : i32 x や var = 32 などです。

最後に、addNode を呼び出して Node を作成します。これはノードリストへのインデックスを返します。この場合、.simple_var_decl を作成します。.simple_var_decl のコメントを見ると、lhs が型式の AST ノードのインデックス（型式がなければゼロ）を、rhs が初期化式の AST ノードのインデックス（初期化がなければゼロ）を指すことが分かります。

parseVarDecl 関数は .simple_var_decl AST ノードへのインデックスを返します。これは最終的に最初にいた parseContainerMembers 関数まで返され、scratch 状態に格納されます。この scratch 状態がどのように使われるかは後で説明します。ひとまず while ループはパースを続行し、関数定義の始まりである .keyword_pub という次のトークンを探します。

関数定義のパース

.keyword_pub が見つかると、呼び出しチェーンは最終的に parseFnProto と parseBlock につながり、それぞれ関数のプロトタイプと本体をパースします。まだ見ていない動作をする parseFnProto に焦点を当ててみましょう。

parseFnProto の簡略化され不完全なバージョンを以下に示します。

fn parseFnProto(p: *Parser) !Node.Index {
    const fn_token = p.eatToken(.keyword_fn) orelse return null_node;

    // We want the fn proto node to be before its children in the array.
    const fn_proto_index = try p.reserveNode();

    _ = p.eatToken(.identifier);
    const params = try p.parseParamDeclList();
    const callconv_expr = try p.parseCallconv();
    _ = p.eatToken(.bang);

    const return_type_expr = try p.parseTypeExpr();
    if (return_type_expr == 0) {
        try p.warn(.expected_return_type);
    }

    return p.setNode(fn_proto_index, .{
        .tag = .fn_proto_one,
        .main_token = fn_token,
        .data = .{
            .lhs = try p.addExtra(Node.FnProtoOne{
                .param = params.zero_or_one,
                .callconv_expr = callconv_expr,
            }),
            .rhs = return_type_expr,
         },
    })
}

これは変数宣言のパースと似ています。いくつか新しいパターンが現れます。まず、戻り値の型が設定されていない場合、パース全体を停止するのではなく警告が格納されることが分かります。パーサーはエラーに直面してもパースを継続しようとすることが多く、これはその一例です。

次に、fn_proto_one タグの lhs 値は extra_data へのインデックスです。これは追加データがどのように書き込まれるかを示しています。addExtra 関数はすべての値を持つ構造体を受け取り、型安全な方法で extra_data にエンコードしてから、追加データ内の開始インデックスを返します。先ほど示したように、この AST ノードの利用者は fn_proto_one タグに対して何フィールドを期待すべきかを正確に把握しており、この情報を読み取ることができます。

AST の確定

パースはプログラム全体に対して再帰的に継続し、AST ノードを構築します。パースの最後に、パーサーは Ast 構造体を返します。その構造を以下に示します。

pub const Ast = struct {
    source: [:0]const u8,
    tokens: TokenList.Slice,
    nodes: NodeList.Slice,
    extra_data: []Node.Index,
    errors: []const Error,
};

この時点で、トークン化のページを読み、パーサーと AST ノードの構造を完全に理解していれば、これらの各フィールドの意味が分かるはずです。AST は、完全なソースを source として（識別子文字列やエラーメッセージの特定などに使用）、トークンのリストを tokens として、AST ノードのリストを nodes として、AST ノード用の追加データを extra_data として、そして蓄積されたエラーのリストを errors として持っています。

次はAstGen プロセスです。