AST

次の章で説明するパーサーは、トークンを抽象構文木（AST）に変換する責任を負います。ソーステキストよりも、このASTの上で作業するほうがずっと楽です。

すべてのJavaScriptツールは、このASTレベルで動作しています。たとえば：

ライナーツール（例：ESLint）は、このASTを検査してエラーをチェックします
フォーマッター（例：prettier）は、このASTを元に再びJavaScriptテキストとして出力します
ミニファイア（例：terser）は、このASTを変換します
バンドラは、異なるファイル間のすべてのインポート・エクスポートステートメントを、各ファイルのAST同士で接続します

この章では、Rustの構造体と列挙型を使って、実際にJavaScriptのASTを構築してみましょう。

ASTの基礎を学ぶ

まず、自分自身がこのASTに慣れられるように、ASTExplorer を訪れて、その外観を見てみましょう。上部パネルで「JavaScript」を選択し、「acorn」を選び、var a と入力すると、ツリー表示とJSON表示が確認できます。

json

{
  "type": "Program",
  "start": 0,
  "end": 5,
  "body": [
    {
      "type": "VariableDeclaration",
      "start": 0,
      "end": 5,
      "declarations": [
        {
          "type": "VariableDeclarator",
          "start": 4,
          "end": 5,
          "id": {
            "type": "Identifier",
            "start": 4,
            "end": 5,
            "name": "a"
          },
          "init": null
        }
      ],
      "kind": "var"
    }
  ],
  "sourceType": "script"
}

これは木構造なので、すべてのオブジェクトは Program や VariableDeclaration、VariableDeclarator、Identifier のような種類名を持つノードです。 start と end は、ソースからのオフセットを表しています。

estree

estree は、コミュニティ標準のJavaScript構文仕様であり、さまざまなツール間での互換性を確保するために、すべてのASTノードを定義しています。

どのASTノードにも共通する基本的な構成要素は Node 型です：

rust

#[derive(Debug, Default, Clone, Copy, Serialize, PartialEq, Eq)]
pub struct Node {
    /// ソース内の開始オフセット
    pub start: usize,

    /// ソース内の終了オフセット
    pub end: usize,
}

impl Node {
    pub fn new(start: usize, end: usize) -> Self {
        Self { start, end }
    }
}

var a に対するASTは次のように定義されます。

rust

pub struct Program {
    pub node: Node,
    pub body: Vec<Statement>,
}

pub enum Statement {
    VariableDeclarationStatement(VariableDeclaration),
}

pub struct VariableDeclaration {
    pub node: Node,
    pub declarations: Vec<VariableDeclarator>,
}

pub struct VariableDeclarator {
    pub node: Node,
    pub id: BindingIdentifier,
    pub init: Option<Expression>,
}

pub struct BindingIdentifier {
    pub node: Node,
    pub name: String,
}

pub enum Expression {
}

Rustには継承がないため、Node は各構造体に追加されています（これを「継承ではなく構成を使う」といいます）。

Statement と Expression は列挙型です。なぜなら、将来多くの他のノードタイプを追加する予定だからです。たとえば：

rust

pub enum Expression {
    AwaitExpression(AwaitExpression),
    YieldExpression(YieldExpression),
}

pub struct AwaitExpression {
    pub node: Node,
    pub expression: Box<Expression>,
}

pub struct YieldExpression {
    pub node: Node,
    pub expression: Box<Expression>,
}

Box が必要なのは、自己参照構造体はRustでは許可されていないからです。

INFO

JavaScriptの文法には多くの面倒な点があります。楽しみのために文法チュートリアルを読んでください。

Rustの最適化

メモリ割り当て

Vec や Box などのヒープ割り当て構造体には注意が必要です。ヒープ割り当ては高コストだからです。

swcからの実際の実装を見てみましょう。ここで、大量の Box と Vec が使われていることがわかります。また、Statement と Expression の列挙型には十数個の列挙バリアントが含まれていることも注目してください。

メモリアレイナ

グローバルメモリアロケータを使ってASTを作成するのは、実際には効率的ではありません。各 Box や Vec は必要に応じて割り当てられ、個別に解放されます。理想は、あらかじめメモリを割り当て、一括して解放することです。

INFO

ASTをメモリアレイナに格納する背景については、Rustにおけるアレイナと ASTのフラット化を参照してください。

bumpalo は、そのドキュメントによると、私たちの用途に非常に適した選択肢です：

バンプアロケーションは高速ですが、制限のあるアプローチです。メモリのチャンクを保持し、その中でポインタを管理しています。オブジェクトを割り当てる際には、チャンクに十分な容量があるかを簡単にチェックし、オブジェクトのサイズだけポインタを更新します。これだけで終わりです！
バンプアロケーションの欠点は、個々のオブジェクトを解放したり、使用していないオブジェクトのメモリ領域を再利用する一般的な方法がないことです。
このトレードオフにより、バンプアロケーションはフェーズ指向の割り当てに適しています。つまり、同じプログラムフェーズ内ですべて割り当てられ、使用され、その後まとめて解放されるオブジェクト群です。

bumpalo::collections::Vec と bumpalo::boxed::Box を使うことで、我々のASTにはライフタイムが追加されます：

rust

use bumpalo::collections::Vec;
use bumpalo::boxed::Box;

pub enum Expression<'a> {
    AwaitExpression(Box<'a, AwaitExpression>),
    YieldExpression(Box<'a, YieldExpression>),
}

pub struct AwaitExpression<'a> {
    pub node: Node,
    pub expression: Expression<'a>,
}

pub struct YieldExpression<'a> {
    pub node: Node,
    pub expression: Expression<'a>,
}

INFO

今この段階でライフタイムに慣れていない場合は注意が必要です。メモリアレイナを使わなくても、プログラムは問題なく動作します。

以降の章では、シンプルにするためにメモリアレイナの使用は示しません。

列挙型のサイズ

最初に行う最適化は、列挙型のサイズを減らすことです。

Rustの列挙型のバイトサイズは、すべてのバリアントの和であることはよく知られています。たとえば、以下の列挙型は56バイト（タグ用1バイト、ペイロード用48バイト、アラインメント用8バイト）になります。

rust

enum Name {
    Anonymous, // ペイロード0バイト
    Nickname(String), // ペイロード24バイト
    FullName{ first: String, last: String }, // ペイロード48バイト
}

INFO

この例はこのブログ記事から引用しています

Expression および Statement の列挙型の場合、現状の設定では200バイト以上になる可能性があります。

これらの200バイトは、matches!(expr, Expression::AwaitExpression(_)) のようなチェックを行うたびに、移動やアクセスされる必要があります。これはパフォーマンス的にキャッシュに優しくありません。

より良いアプローチは、列挙バリアントをボックス化し、常に16バイトしか持ち運ばないことです。

rust

pub enum Expression {
    AwaitExpression(Box<AwaitExpression>),
    YieldExpression(Box<YieldExpression>),
}

pub struct AwaitExpression {
    pub node: Node,
    pub expression: Expression,
}

pub struct YieldExpression {
    pub node: Node,
    pub expression: Expression,
}

列挙型が64ビットシステムで実際に16バイトになっていることを確認するには、std::mem::size_of を使います。

rust

#[test]
fn no_bloat_enum_sizes() {
    use std::mem::size_of;
    assert_eq!(size_of::<Statement>(), 16);
    assert_eq!(size_of::<Expression>(), 16);
}

「no bloat enum sizes」テストケースは、小さい列挙型サイズを保証するために、しばしばRustコンパイラのソースコードで見られます。

rust

// https://github.com/rust-lang/rust/blob/9c20b2a8cc7588decb6de25ac6a7912dcef24d65/compiler/rustc_ast/src/ast.rs#L3033-L3042

// 一部のノードは頻繁に使用されます。意図しない大きさにならないか確認しましょう。
#[cfg(all(target_arch = "x86_64", target_pointer_width = "64"))]
mod size_asserts {
    use super::*;
    use rustc_data_structures::static_assert_size;
    // アルファベット順に並べて、維持が簡単です。
    static_assert_size!(AssocItem, 160);
    static_assert_size!(AssocItemKind, 72);
    static_assert_size!(Attribute, 32);
    static_assert_size!(Block, 48);

他の大きな型を探すには、次のように実行できます。

bash

RUSTFLAGS=-Zprint-type-sizes cargo +nightly build -p name_of_the_crate --release

以下のような出力が得られます。

print-type-size type: `ast::js::Statement`: 16 bytes, alignment: 8 bytes
print-type-size     discriminant: 8 bytes
print-type-size     variant `BlockStatement`: 8 bytes
print-type-size         field `.0`: 8 bytes
print-type-size     variant `BreakStatement`: 8 bytes
print-type-size         field `.0`: 8 bytes
print-type-size     variant `ContinueStatement`: 8 bytes
print-type-size         field `.0`: 8 bytes
print-type-size     variant `DebuggerStatement`: 8 bytes
print-type-size         field `.0`: 8 bytes

JSONシリアル化

serde を使って、ASTをJSONにシリアライズできます。estree 互換にするためにいくつかのテクニックが必要です。以下に例を示します：

rust

use serde::Serialize;

#[derive(Debug, Clone, Serialize, PartialEq)]
#[serde(tag = "type")]
#[cfg_attr(feature = "estree", serde(rename = "Identifier"))]
pub struct IdentifierReference {
    #[serde(flatten)]
    pub node: Node,
    pub name: Atom,
}

#[derive(Debug, Clone, Serialize, PartialEq, Hash)]
#[serde(tag = "type")]
#[cfg_attr(feature = "estree", serde(rename = "Identifier"))]
pub struct BindingIdentifier {
    #[serde(flatten)]
    pub node: Node,
    pub name: Atom,
}

#[derive(Debug, Serialize, PartialEq)]
#[serde(untagged)]
pub enum Expression<'a> {
    ...
}

serde(tag = "type") は、構造体名を "type" フィールドにすることで、{ "type" : "..." } の形式にします
cfg_attr + serde(rename) は、異なる構造体名を同じ名前にリネームするために使います。estree は異なる識別子を区別しないためです
列挙型に serde(untagged) が指定されているのは、列挙型のために余計なJSONオブジェクトを作らないようにするためです

AST ​

ASTの基礎を学ぶ ​

estree ​

Rustの最適化 ​

メモリ割り当て ​

メモリアレイナ ​

列挙型のサイズ ​

JSONシリアル化 ​

AST

ASTの基礎を学ぶ

estree

Rustの最適化

メモリ割り当て

メモリアレイナ

列挙型のサイズ

JSONシリアル化