AST

다음 장에서 설명할 파서는 토큰을 추상 구문 트리 (AST)로 변환하는 책임을 맡습니다.
소스 텍스트보다 추상 구문 트리를 다루는 것이 훨씬 더 편리합니다.

모든 자바스크립트 도구는 추상 구문 트리 수준에서 작동합니다. 예를 들어:

린터 (예: ESLint)는 추상 구문 트리에서 오류를 검사합니다
포맷터 (예: prettier)는 추상 구문 트리를 다시 자바스크립트 텍스트로 출력합니다
미니파이어 (예: terser)는 추상 구문 트리를 변환합니다
번들러는 서로 다른 파일의 추상 구문 트리 간의 모든 가져오기 및 내보내기 문을 연결합니다

이 장에서는 루스트의 구조체와 열거형을 사용하여 자바스크립트 추상 구문 트리를 구성해 보겠습니다.

추상 구문 트리에 익숙해지기

추상 구문 트리에 익숙해지기 위해, ASTExplorer를 방문해 보세요. 상단 패널에서 자바스크립트를 선택하고 acorn을 선택한 후 var a를 입력하면 트리 보기와 JSON 보기에서 결과를 확인할 수 있습니다.

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는 자바스크립트에 대한 커뮤니티 표준 문법 사양이며,
다양한 도구가 서로 호환될 수 있도록 모든 추상 구문 트리 노드를 정의합니다.

어떤 추상 구문 트리 노드의 기본 구성 요소는 Node 타입입니다:

rust

#[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의 추상 구문 트리는 다음과 같이 정의됩니다.

rust

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

루스트는 상속을 지원하지 않으므로, Node는 각 구조체에 별도로 추가됩니다 (이는 "상속 대신 구성"이라고 불립니다).

Statement와 Expression는 다양한 노드 유형이 추가될 가능성이 크므로 열거형으로 정의됩니다. 예를 들어:

rust

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는 자기 참조 구조체가 루스트에서 허용되지 않기 때문에 필요합니다.

INFO

자바스크립트 문법에는 많은 세부적인 문제들이 있으므로, 즐거움을 위해 문법 튜토리얼을 읽어보세요.

루스트 최적화

메모리 할당

Vec 및 Box와 같은 힙에 할당된 구조체를 주의 깊게 살펴봐야 합니다. 힙 할당은 비용이 비싸기 때문입니다.

swc의 실제 구현을 보면, 추상 구문 트리에 많은 Box와 Vec가 포함되어 있으며, Statement와 Expression 열거형에는 십여 개의 열거형 변수가 있음을 알 수 있습니다.

메모리 아레나

추상 구문 트리에 전역 메모리 할당자를 사용하는 것은 실제로 효율적이지 않습니다.
각 Box와 Vec는 필요할 때마다 할당되고, 각각 별도로 해제됩니다.
우리가 원하는 것은 메모리를 미리 할당하고 일괄적으로 해제하는 것입니다.

INFO

추상 구문 트리를 메모리 아레나에 저장하는 배경 지식으로 루스트에서의 아레나 및 추상 구문 트리 평탄화를 참고하세요.

bumpalo는 문서에 따르면 우리의 용도에 매우 적합한 후보입니다:

버프 할당은 빠르지만 제한적인 할당 방식입니다.
우리는 메모리의 한 덩어리를 가지고 있으며, 그 안에서 포인터를 유지합니다. 객체를 할당할 때마다,
해당 덩어리에 충분한 용량이 남아 있는지 빠른 점검을 수행한 다음, 객체의 크기만큼 포인터를 업데이트합니다. 그것뿐입니다!
버프 할당의 단점은 개별 객체를 해제하거나 더 이상 사용하지 않는 객체의 메모리 영역을 회수하는 일반적인 방법이 없다는 것입니다.
이러한 성능과 안정성의 교환은 단계 중심 할당에 잘 맞습니다. 즉, 동일한 프로그램 단계 동안 모두 할당되고 사용되며, 이후 그룹으로 함께 해제될 수 있는 객체 그룹입니다.

bumpalo::collections::Vec와 bumpalo::boxed::Box를 사용함으로써, 우리 추상 구문 트리에는 라이프타임이 추가됩니다:

rust

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

현재 라이프타임을 다루는 것에 익숙하지 않다면 조심해야 합니다.
메모리 아레나 없이도 우리의 프로그램은 정상적으로 작동합니다.

다음 장의 코드는 단순성을 위해 메모리 아레나 사용을 보여주지 않습니다.

열거형 크기

우리가 첫 번째로 수행할 최적화는 열거형의 크기를 줄이는 것입니다.

루스트 열거형의 바이트 크기는 모든 변형의 합집합이라는 점을 알고 있습니다. 예를 들어, 아래의 열거형은 56바이트를 차지합니다 (태그용 1바이트, 본문용 48바이트, 정렬용 8바이트).

rust

enum Name {
    Anonymous, // 0바이트 본문
    Nickname(String), // 24바이트 본문
    FullName{ first: String, last: String }, // 48바이트 본문
}

INFO

이 예시는 이 블로그 포스트에서 인용되었습니다.

Expression과 Statement 열거형의 경우 현재 설정으로는 200바이트 이상을 차지할 수 있습니다.

이 200바이트는 매번 matches!(expr, Expression::AwaitExpression(_)) 검사를 수행할 때마다 전달되거나 접근되어야 하며, 이는 성능 측면에서 캐시 친화적이지 않습니다.

더 나은 접근법은 열거형 변형을 박싱하여 항상 16바이트만 전달하는 것입니다.

rust

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를 사용할 수 있습니다.

rust

#[test]
fn no_bloat_enum_sizes() {
    use std::mem::size_of;
    assert_eq!(size_of::<Statement>(), 16);
    assert_eq!(size_of::<Expression>(), 16);
}

"no bloat enum sizes" 테스트 케이스는 루스트 컴파일러 소스 코드에서도 흔히 볼 수 있으며, 작은 열거형 크기를 보장하기 위해 사용됩니다.

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

다른 큰 타입들을 찾기 위해 다음 명령을 실행할 수 있습니다.

bash

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를 사용하면 추상 구문 트리를 JSON으로 직렬화할 수 있습니다. 일부 기술을 사용하여 estree 호환성을 확보해야 합니다. 아래는 몇 가지 예시입니다:

rust

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 객체를 생성하지 않습니다.

AST ​

추상 구문 트리에 익숙해지기 ​

estree ​

루스트 최적화 ​

메모리 할당 ​

메모리 아레나 ​

열거형 크기 ​

JSON 직렬화 ​

AST

추상 구문 트리에 익숙해지기

estree

루스트 최적화

메모리 할당

메모리 아레나

열거형 크기

JSON 직렬화