AST

下一章中的解析器负责将词法单元（Token）转换为抽象语法树（AST）。 相比于源文本，在 AST 上工作要更加舒适。

所有 JavaScript 工具都在 AST 层面工作，例如：

• Linter（如 ESLint）检查 AST 中的错误
• Formatter（如 prettier）将 AST 打印回 JavaScript 文本
• Minifier（如 terser）转换 AST
• Bundler 连接不同文件中 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 {
    /// 源代码中的起始偏移量
    pub start: usize,

    /// 源代码中的结束偏移量
    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 中不允许自引用结构体。

INFO

JavaScript 语法有很多令人烦恼的地方，阅读 语法教程 来获得一些乐趣。

Rust 优化

内存分配

我们需要注意堆分配的结构体，如 Vec 和 Box，因为堆分配并不便宜。

看看 swc 的真实实现， 我们可以看到 AST 可以有很多 Box 和 Vec，还要注意 Statement 和 Expression 枚举包含 十几个枚举变体。

内存竞技场

为 AST 使用全局内存分配器实际上并不是很高效。 每个 Box 和 Vec 都是按需分配然后单独释放的。 我们想要做的是预先分配内存，然后批量释放。

INFO

另见 Rust 中的 Arena 和 扁平化 AST 以获取更多关于在内存竞技场中存储 AST 的背景信息。

bumpalo 是我们使用场景的一个很好的候选者，根据其文档：

Bump 分配是一种快速但有限的分配方法。 我们有一块内存，并在该内存中维护一个指针。每当我们要分配一个对象时， 我们会快速检查块中是否有足够的容量来分配对象，然后按对象的大小更新指针。就是这样！

Bump 分配的缺点是没有通用的方法来释放单个对象或回收不再使用的对象的内存区域。

这些权衡使得 bump 分配非常适合阶段导向的分配。也就是说，一组对象将在同一程序阶段全部被分配、使用，然后可以作为一个组一起全部释放。

通过使用 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>,
}

INFO

如果我们在这个阶段对处理生命周期不太熟悉，请谨慎行事。 我们的程序在没有内存竞技场的情况下也能正常工作。

以下章节中的代码为了简单起见，不演示内存竞技场的使用。

枚举大小

我们要进行的第一个优化是减小枚举的大小。

众所周知，Rust 枚举的字节大小是其所有变体的联合体。 例如，以下枚举将占用 56 字节（1 字节用于标签，48 字节用于载荷，8 字节用于对齐）。

enum Name {
    Anonymous, // 0 字节载荷
    Nickname(String), // 24 字节载荷
    FullName{ first: String, last: String }, // 48 字节载荷
}

INFO

此示例取自 这篇博文

至于 Expression 和 Statement 枚举，在我们当前的设置下，它们可能占用超过 200 字节。

这 200 字节需要到处传递，或者每次我们进行 matches!(expr, Expression::AwaitExpression(_)) 检查时都要访问， 这对性能来说不是很缓存友好的。

更好的方法是将枚举变体装箱，只携带 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);
}

"no bloat enum sizes" 测试用例经常可以在 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

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 对象