AST

No capítulo seguinte o parser converte tokens em AST (abstract syntax tree). Trabalhar em cima da AST é bem mais confortável que no texto-fonte.

Ferramentas JavaScript todas operam no nível da AST:

• linter (por ex. ESLint) examina erros na AST;
• formatter (por ex. Prettier) imprime a AST de volta em texto;
• minificador (por ex. terser) transforma a AST;
• bundler une import/export entre ASTs de vários arquivos.

Vamos montar uma AST JS com structs e enums Rust.

Conhecendo a AST

Para se ambientar, abra ASTExplorer: JavaScript → acorn, digite var a e observe a árvore e o 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"
}

Cada objeto é um nó com type (Program, VariableDeclaration, etc.). start e end são offsets no fonte.

estree

estree padroniza a gramática AST da comunidade e lista todos os nós para diferentes ferramentas conversarem entre si.

O bloco base de qualquer nó é o tipo 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 }
    }
}

A AST para var a fica assim:

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 não tem herança: cada struct carrega seu Node (composition over inheritance).

Statement e Expression são enums porque crescerão com muitos tipos:

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

Precisamos de Box porque structs autorreferenciais não são permitidas.

INFO

A gramática JS tem várias esquisitices — divirta-se com o tutorial de gramática.

Rust Optimizations

Memory Allocations

Cuidado com Vec e Box na heap — alocação não é de graça.

Na AST real do swc há montes de Box/Vec, e os enums Statement/Expression têm dezenas de variantes.

Memory Arena

Alocar AST com o alocador global nem sempre é eficiente. Cada Box/Vec nasce e morre separadamente. O ideal é reservar blocos e descartar tudo de uma vez.

INFO

Veja Arenas in Rust e Flattening ASTs.

bumpalo encaixa bem:

Bump allocation é rápida, porém limitada. Temos um bloco de memória e um ponteiro interno. Ao alocar, checamos capacidade e avançamos o ponteiro pelo tamanho do objeto. Pronto!

A desvantagem é não haver liberação fina: não dá para liberar um objeto isolado.

Ideal para fases: alocar um grupo, usar tudo e soltar junto.

Com bumpalo::collections::Vec e bumpalo::boxed::Box, a AST ganha tempos de vida:

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

Se lifetimes ainda assustam, ok deixar sem arena — o código dos capítulos seguintes omite arena por simplicidade.

Enum Size

Primeira otimização: encolher enums.

O tamanho em bytes de um enum Rust é a união das variantes. Exemplo de ~56 bytes (tag + carga + alinhamento):

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

INFO

Exemplo deste post.

Expression/Statement podem passar de 200 bytes do jeito “ingênuo”. Esses 200 bytes viajam a cada matches!(expr, Expression::AwaitExpression(_)) — péssimo para cache.

Melhor: boxar variantes e carregar só ~16 bytes.

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

Confirme com 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);
}

Testes “no bloat enum sizes” aparecem no próprio rustc para garantir enums pequenos.

// 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);

Para achar tipos grandes:

RUSTFLAGS=-Zprint-type-sizes cargo +nightly build -p name_of_the_crate --release

Saída típica:

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 Serialization

serde serializa a AST em JSON; alguns truques ajudam a ficar compatível com 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") cria campo "type".
• cfg_attr + serde(rename) unifica nomes quando estree não distingue structs diferentes.
• serde(untagged) evita objeto extra enrolando o enum.