AST

다음 장의 파서는 토큰을 추상 구문 트리(AST)로 바꿉니다. 소스 텍스트보다 AST 위에서 작업하는 편이 훨씬 낫습니다.

모든 JS 툴링은 AST 수준에서 돌아갑니다:

• 린터(예: ESLint)는 AST에서 오류 검사
• 포매터(예: prettier)는 AST를 다시 JS로 출력
• 축약기(예: terser)는 AST 변환
• 번들러는 파일마다 다른 AST의 import/export를 연결

이 장에서는 Rust의 struct와 enum으로 JavaScript 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 등)을 가진 노드입니다. start와 end는 소스 내 오프셋입니다.

estree

estree는 커뮤니티 표준 JS 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에는 상속이 없으므로 각 struct에 Node를 붙입니다(합성 우선).

Statement와 Expression은 enum으로 두면 나중에 변안이 많이 늘어납니다:

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

자기 참조 struct는 허용되지 않아 Box가 필요합니다.

INFO

JavaScript 문법은 성가신 부분이 많습니다. 문법 튜토리얼을 읽어 보세요.

Rust 최적화

메모리 할당

Vec, Box 같은 힙 할당 구조체는 값비싼 편이라 주의해야 합니다.

swc 실제 코드를 보면 AST에 Box와 Vec가 매우 많고, Statement·Expression enum에 변안이 수많습니다.

메모리 아레나

AST에 전역 할당자를 쓰는 것은 비효율적입니다. Box·Vec가 요청마다 따로 할당되고 따로 드롭되니, 미리 메모리를 잡았다 한꺼번에 버리고 싶습니다.

INFO

Arenas in Rust와 Flattening ASTs도 참고하세요.

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

INFO

수명이 부담된다면 아레나 없이도 프로그램은 잘 동작합니다. 다음 장 예제는 단순하게 아레나를 쓰지 않습니다.

Enum 크기

첫 번째 최적화는 enum 크기를 줄이는 것입니다.

Rust enum의 바이트 크기는 모든 변안의 합입니다. 예를 들어 다음 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 enum은 지금 구조만으로도 200바이트 넘게 커질 수 있습니다.

200바이트를 옮겨 다니거나 matches!(expr, Expression::AwaitExpression(_)) 할 때마다 접근해야 하면 성능과 캐시에 불리합니다.

변안을 박스하면 enum은 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비트에서 enum이 진짜 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 컴파일러 소스에도 종종 작은 enum 크기를 강제하는 테스트가 있습니다.

// 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
...

같은 출력을 볼 수 있습니다.

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")로 struct 이름이 "type" 필드가 됩니다.
• cfg_attr와 serde(rename)으로 이름이 다른 struct를 estree에서는 같은 이름으로 묶습니다(estree가 식별자를 구분하지 않으므로).
• enum에 serde(untagged)를 쓰면 enum용 추가 JSON 객체를 만들지 않습니다.