AST

下一章的解析器负责将标记（Tokens）转换为抽象语法树（AST）。相比于源代码文本，处理 AST 要更加方便。

所有 JavaScript 工具都基于 AST 层级工作，例如：

• 一个检查工具（如 ESLint）会在 AST 上查找错误
• 一个格式化工具（如 prettier）会将 AST 重新打印回 JavaScript 文本
• 一个压缩工具（如 terser）会转换 AST
• 一个打包工具会连接来自不同文件的 AST 中的导入和导出语句

在本章中，我们将使用 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

有关在内存池中存储 AST 的更多背景知识，请参阅 Rust 中的内存池 与 扁平化 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);
}

“无膨胀枚举大小”测试案例经常出现在 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);

要查找其他较大的类型，可以运行：

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