AST

下一章中的解析器负责将令牌转换为抽象语法树 (AST)。与原始文本相比，处理 AST 会好得多。

例如，所有 JavaScript 工具都工作在 AST 级别

• Linter（例如 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 被添加到每个结构中（这称为“在继承上进行组合”）。

语句和表达式是枚举，因为它们将扩展为大量其他节点类型，例如

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

需要 框是因为 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 多个字节。

这 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

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