AST

即將在下一章介紹的解析器負責將 Tokens 轉換為抽象語法樹 (AST)。與原始碼文本相比，在 AST 上工作要好得多。

所有 JavaScript 工具都以 AST 層級工作，例如

• 程式碼檢查器 (例如 ESLint) 會檢查 AST 中的錯誤
• 格式化工具 (例如 Prettier) 會將 AST 列印回 JavaScript 文本
• 壓縮器 (例如 Terser) 會轉換 AST
• 打包工具會連接不同檔案的 AST 之間的所有 import 和 export 語句

在本章中，我們將使用 Rust 結構體和枚舉來建構 JavaScript AST。

熟悉 AST

為了讓我們自己熟悉 AST，讓我們訪問 ASTExplorer 並查看它的樣子。在頂部面板上，選擇 JavaScript，然後選擇 acorn，輸入 var a，我們將看到一個樹狀檢視和 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 類型

#[derive(Debug, Default, Clone, Copy, Serialize, PartialEq, Eq)]
pub struct Node {
    /// Start offset in source
    pub start: usize,

    /// End offset in source
    pub end: usize,
}

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

var a 的 AST 定義為

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 是枚舉，因為它們將會擴展許多其他節點類型，例如

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 中不允許自我參照的結構體。

資訊

JavaScript 文法有很多細微之處，請閱讀文法教學來尋找樂趣。

Rust 優化

記憶體配置

我們需要注意堆積配置的結構體，例如 Vec 和 Box，因為堆積配置並不便宜。

看看來自 swc 的真實世界實作，我們可以看到 AST 可以有很多 Box 和 Vec，並且還要注意到 Statement 和 Expression 枚舉包含十幾個枚舉變體。

枚舉大小

我們要做的第一個優化是減少枚舉的大小。

眾所周知，Rust 枚舉的位元組大小是其所有變體的聯集。例如，以下枚舉將佔用 56 個位元組 (1 個位元組用於標籤、48 個位元組用於有效載荷，以及 8 個位元組用於對齊)。

enum Name {
    Anonymous, // 0 byte payload
    Nickname(String), // 24 byte payload
    FullName{ first: String, last: String }, // 48 byte payload
}

資訊

此範例取自這篇部落格文章

至於 Expression 和 Statement 枚舉，使用我們目前的設定，它們可以佔用 200 多個位元組。

每次我們執行 matches!(expr, Expression::AwaitExpression(_)) 檢查時，都需要傳遞或存取這 200 個位元組，這對於效能來說不是很適合快取。

更好的方法是框住枚舉變體，並僅攜帶 16 個位元組。

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。

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

「沒有膨脹的枚舉大小」的測試案例通常可以在 Rust 編譯器原始碼中看到，以確保小的枚舉大小。

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

// Some nodes are used a lot. Make sure they don't unintentionally get bigger.
#[cfg(all(target_arch = "x86_64", target_pointer_width = "64"))]
mod size_asserts {
    use super::*;
    use rustc_data_structures::static_assert_size;
    // These are in alphabetical order, which is easy to maintain.
    static_assert_size!(AssocItem, 160);
    static_assert_size!(AssocItemKind, 72);
    static_assert_size!(Attribute, 32);
    static_assert_size!(Block, 48);

若要尋找其他大型類型，我們可以執行

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

記憶體區域

為 AST 使用全域記憶體配置器實際上不是很有效率。每個 Box 和 Vec 都是按需配置，然後單獨釋放。我們想要做的是預先配置記憶體，然後批次釋放它。

資訊

這篇部落格文章更詳細地解釋了記憶體區域。

根據其文件，bumpalo 非常適合我們的使用案例

碰撞配置是一種快速但有限的配置方法。我們有一塊記憶體，並且我們在該記憶體中維護一個指標。每當我們配置物件時，我們會快速檢查我們的記憶體區塊中是否剩餘足夠的容量來配置物件，然後將指標更新物件的大小。就這樣！

碰撞配置的缺點是，沒有一般方法可以釋放個別物件或回收不再使用的物件的記憶體區域。

這些權衡使碰撞配置非常適合面向階段的配置。也就是說，一組物件將在相同的程式階段期間全部配置、使用，然後可以作為一組一起釋放。

透過使用 bumpalo::collections::Vec 和 bumpalo::boxed::Box，我們的 AST 將新增生命週期

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>,
}

資訊

如果我們在這個階段不習慣處理生命週期，請小心。我們的程式在沒有記憶體區域的情況下也能正常運作。

為了簡單起見，以下章節中的程式碼不會示範使用記憶體區域。

JSON 序列化

serde 可用於將 AST 序列化為 JSON。需要一些技術才能使其與 estree 相容。以下是一些範例

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 物件