AST

Парсер из следующих глав превращает токены в абстрактное синтаксическое дерево (AST). С AST работать проще и приятнее, чем с сырым текстом.

Весь JS-экосистемный инструментарий живёт на уровне AST, например:

• линтер (напр. ESLint) проверяет AST на ошибки
• форматтер (напр. Prettier) печатает AST обратно в текст JavaScript
• минификатор (напр. Terser) преобразует AST
• бандлер связывает import/export между AST разных файлов

В этой главе построим AST JavaScript на структурах и перечислениях Rust.

Знакомство с 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, чтобы инструменты были совместимы.

Базовый блок любого узла — тип 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 дерево задаётся так:

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 десятки вариантов.

Arena-память

Глобальный аллокатор для AST не особенно эффективен: каждый Box/Vec выделяется и освобождается по отдельности. Хотелось бы заранее выделить память и освободить всё одним действием.

INFO

Полезны также Arenas in Rust и Flattening ASTs про размещение AST в arena.

bumpalo подходит описанием:

Bump allocation is a fast, but limited approach to allocation. We have a chunk of memory, and we maintain a pointer within that memory. Whenever we allocate an object, we do a quick check that we have enough capacity left in our chunk to allocate the object and then update the pointer by the object’s size. That’s it!

The disadvantage of bump allocation is that there is no general way to deallocate individual objects or reclaim the memory region for a no-longer-in-use object.

These trade offs make bump allocation well-suited for phase-oriented allocations. That is, a group of objects that will all be allocated during the same program phase, used, and then can all be deallocated together as a group.

Через bumpalo::collections::Vec и bumpalo::boxed::Box появятся параметры времени жизни:

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

Если времена жизни пока некомфортны — можно обойтись без arena: программа будет работать. В следующих главах arena для простоты не показана.

Размер перечислений

Первая оптимизация — уменьшить размер enum’ов.

Размер Rust-enum — по сути сумма всех вариантов (пэйлоад самого большого). Например, такое перечисление займёт 56 байт (1 байт тега, 48 байт данных, выравнивание 8):

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

INFO

Пример взят из этого поста

У Expression и Statement при текущем подходе легко выйти на 200+ байт каждое.

Эти 200 байт таскаются постоянно и читаются при каждой проверке matches!(expr, Expression::AwaitExpression(_)), что плохо для кеша по производительности.

Лучше завернуть варианты в Box и носить 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-битных системах проверка размеров через 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);
}

Тесты «не раздувать enum» можно встретить и в коде самого компилятора 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) на enum — без лишнего вложенного JSON-объекта для самого перечисления