Zenn
Closed14

JavaScript Parser In Rust を読む

nissy-devnissy-dev

Lexer

identifier の先頭にくる文字と先頭以外の文字が決まっている

https://tc39.es/ecma262/#sec-names-and-keywords

最適化 tips

  • string の比較は普通だと O(n) かかるので string interning を使っている

String Interning solves these problems by storing only one copy of each distinct string value with a unique identifier in a cache. There will only be one heap allocation per distinct identifier or string, and string comparisons become O(1).

https://en.wikipedia.org/wiki/String_interning

nissy-devnissy-dev

AST

最適化 Tips

  • Enum の変数に Box を使うことで Enum の size を削減する

Rust の enum のサイズは、全ての変数の和になる。AST を定義するときは、非常に大きな enum を定義するので、効率が悪くなりがち。

// どんどんサイズは大きくなる
enum Name {
    Anonymous, // 0 byte payload
    Nickname(String), // 24 byte payload
    FullName{ first: String, last: String }, // 48 byte payload
　.... 
}

// enum を使うとポインタなのでサイズは増えていかない
pub enum Expression {
    AwaitExpression(Box<AwaitExpression>),
    YieldExpression(Box<YieldExpression>),
}
  • memory allocator として memory arena の１つ bump allocation を利用する

memory arena とは、メモリをチャンクで管理する方法のことを指す。

https://docs.rs/bumpalo/latest/bumpalo/#bump-allocation

bump allocation がどのようなメモリ管理方法なのかについては、次のコードを読むとわかりやすそう。ここでは、そこまで深く踏み込まない。

https://rust-hosted-langs.github.io/book/chapter-simple-bump.html

nissy-devnissy-dev

Parser

一般的な Recursive descent parser の紹介をしている。
パーサーなどは、次のリンクに以前まとめた
https://zenn.dev/link/comments/ecd33afa757894

Expression のパースは、再帰やネストが深くなるので、「Pratt Parsing」という tips を利用する。
Pratt Parsing は、ざっくり説明すると演算子に優先度をつけて効率的なパースを実現する手法である。
詳細は、Rust Analyzer の著者が書いたブログに書かれている。 Rome もこれを取り入れている。

https://matklad.github.io/2020/04/13/simple-but-powerful-pratt-parsing.html

JS では数個先の token をみても構文を決めることができない場合に、Cover Grammer というものを導入して回避している。

https://qiita.com/uhyo/items/c1574cdd11b1a28b85b7

Cover Grammer に関してパーサでは、expression で一旦解釈しつつ、その後に expression を別の node に変換することで対応している。(rome や oxc では IdentiferBinding に変換する)

nissy-devnissy-dev

AST のフラット化

Rust でパーサーを書くときに、Box を使ったASTノードの保持をよくやる

enum BinOp { Add, Sub, Mul, Div }
enum Expr {
    Binary(BinOp, Box<Expr>, Box<Expr>),
    Literal(i64),
}

参照が nest していくのが結構たいへんなので、次のように AST をノードを flat にもつ方法がいろんな観点からよいという話。

struct ExprPool(Vec<Expr>);

struct ExprRef(u32);

 enum Expr {
     Binary(BinOp, ExprRef, ExprRef),
     Literal(i64),
 }

記事で挙げられているメリットは次の通り。

  • 参照のサイズ削減
    • 従来：Box を使ったポインタは常に 64 bit
    • フラット：参照はただの id なので、ノード数に応じてより小さい値が利用できる (↑の例だと 32bit)
  • メモリの割りあて・解放などの効率化
    • 従来
      • Box は毎回動的にメモリ領域を探索して確保しにいく
      • 個々のExprを解放するためにすべてのポインタを走査する必要がある
    • フラット
      • Vec を使うと連続した領域で簡単にメモリを確保できる (キャッシュも効きやすい)
      • ASTの破棄は、単にExprPool全体を解放するだけで OK
  • ライフタイムの管理が楽になる
    • Box とライフタイムの管理が絡む実装は一般的には難しい
nissy-devnissy-dev

Identifier の定義

https://tc39.es/ecma262/#sec-names-and-keywords

のわからなかったところのメモ。

<ZWJ> :　https://ja.wikipedia.org/wiki/ゼロ幅接合子

<ZWNJ> :　https://ja.wikipedia.org/wiki/ゼロ幅非接合子

「any Unicode code point with the Unicode property “ID_Start”」がよくわからなかったんだけど、Unicode 側で ID_Start や ID_Continue が定義されているらしい。

Unicodeの ID_Start 属性を満たす文字 (ASCIIの [a-zA-Z] に相当)

らしい

https://unicode.org/reports/tr31/

次の記事が助けになった

https://zenn.dev/awyaki/articles/ae4fb630350d2a

https://zenn.dev/qnighy/articles/8ee48a7077d19f#モジュールで使える識別子

nissy-devnissy-dev

Rome の CST について

そもそもなんで AST じゃなくて CST を使っているかというと....

https://rome.tools/blog/2021/09/21/rome-will-be-rewritten-in-rust/

AST では次のような問題がある

AST のサンプル

# `let value = 42;`
Node(VariableDeclaration, 
    kind: "let", 
    declarations: [
        Node(VariableDeclarator,
            id: Node(BindingIdentifier, name: "value")
            initializer: Node(NumericLiteral, value: 42)
        )
    ]
)
  • プログラムとして完全に正しいツリーを表現する必要がある
  • コードを変更したらツリー全体を構築し直す必要がある (なんとなくわかる？)
  • コメントなどの一部情報が失われている
    • フォーマットとかで必要になる

情報が失われているからといって、そのまま token 情報を扱うのは難しい。そこで CST を使うことを試みる。CST では、空白などを trivia というフィールドで保存する。

# `let value = 42;`
Node(VariableDeclaration,
    kind: Token(LetKeyword, trailing_trivia: Token(Whitespace, " "))
    declarations: [
        Node(VariableDeclarator,
            id: Node(BindingIdentifier,
                name: "value",
                trailing_trivia: Token(Whitespace, " ")
            )
            equals: Token(Equals, trailing_trivia: Token(Whitespace, " "))
            initializer: Node(NumericLiteral, value: 42)
        )
    ]
    semicolon: Token(Semicolon)
)

しかし、そのままの CST だとやはり有効な抽象構文であることは求められる。そこで CST を次のように拡張する。

  • ツリーのノードは構文構造を表すことができる
  • ソースコードを表現する token も ツリーに含むことができる
  • 抽象的な構文構造とトークンを保持しつつ、不完全なツリーも表現できる

これを満たす構造が次のようなものになる。トークンと抽象構文情報が同じツリーに存在しているのが特徴になる。

type Error(String)
type Token(SyntaxKind, source_text: String)
type Node(SyntaxKind, children: List<Node | Token | Error>)

# `let value =`
Node(VariableDeclaration, children: [
    Token(LetKeyword, "let")
    Token(Whitespace, " ")
    Node(VariableDeclarator, children: [
        Node(BindingIdentifier, children: [
            Token(Identifier, "value")
            Token(Whitespace, " ")
        ])
        Token(Equals, "=")
        Error("Unexpected EOF") # << our program ends too early
    ])
])

これは Red-Green Tree と呼ばれていて、C#、Swift、Rust Analyzer、RSLint で使われている。
Rust Analyzer が作った構文木は Rowan と呼ばれている。RSLint も これを使っている。

まとめると、、、、

「抽象構文を表しつつ、ソースコードの全てを表すに必要なデータをノードに保持できるツリーがほしい。」ということな気がする

ソースコードの全てを表すに必要なノード = 抽象構文を表すノード以外に構文エラーや Token など

=> 構文エラーは、不完全な構文木を扱えるようにするため。不完全な構文木を扱えることで、コードを書き途中でも lint の結果を得ることができる。
=> Token は、空白やコメントなども扱えるようにするため。フォーマットや autofix する時の実装が楽になる。

AST の課題を理解するために読む

https://rdambrosio016.github.io/rust/2020/09/18/pure-ast-based-linting-sucks.html

この記事にはもっと問題が羅列されていた。主に Rust のような静的型付けの言語の話な感じがある。

  • AST の複製コストが大きい
    • スコープ解析にわたしたいなどの一般的なユースケースがある
    • AST をそのまま clone するとコストがおおきくなってしまう
  • 静的型言語だとランタイムなしで親や子ノードの型を決定することができない
    • AST を top-down で travese するしかない、bottom-up で解析したい lint ルールもある
  • 子ノードや token に簡単にアクセスする方法がない
    • 良いエラーを報告したい時に token の情報などが必要になる
    • ESLint は token をAST と別のデータとして保持しているがいくつかの問題がある
      • トークンと AST の紐づけができてない (この token の親 AST を知りたいなどが難しい)
      • 新たなデータ構造の実装とそのメンテナンス
  • AST は非可逆 = lossy (AST から token に戻せない)
    • 空白などに関するなスタイル周りのルールは記述できない
  • AST の可変性
    • autofix などはあるけど、lint するだけなら不変でよい
    • 不変のほうが、ノードを共有したい時に clone や参照を奪ったりしなくて良くて簡単
  • エラーから回復する方法がない
    • 間違った文法に会うと、そこで終了しエラーを返してしまう
    • IDE などでコードを書きながら lint の体験を得るためには重要

これらの代替となるのが Rowan という CST の拡張らしい。

nissy-devnissy-dev

Rowan について

https://github.com/rust-analyzer/rowan

https://github.com/rust-lang/rust-analyzer/blob/master/docs/dev/syntax.md

Rowan is a library for lossless syntax trees, inspired in part by Swift's libsyntax.

Rust Analyzer の overview を理解する。syntax tree は次のデザインゴールを掲げている。

  • 構文木は情報の損失がなく、完全な忠実性がある = すべてのコメントや空白は保持する
  • 構文木はセマンティクスを持たない
  • 構文木は単純な値の型になる (外部の文脈なしで構文を持つ木を作成することが可能にする)
  • 構文木には直感的なトラバーサルAPI（親、子、兄弟など）がある
  • パースで情報の損失はないようにする
    • 入力が無効であっても、生成される木はそれを正確に表す
  • 不完全な構文に対してもできる限りパースを試みる
    • 入力が無効であっても、できる限り多くの構文木の断片を入力から抽出する
  • パフォーマンスは重要
  • パーサと構文木を互いに分離して、独立性を保つ

synatx tree は次の３つレイヤーからなる。

  • GreenNodes → Rowan が定義
  • SyntaxNodes (aka RedNode) → Rowan が定義
  • AST → rust-analyzer が定義

GreenNodesとは

任意の個数の要素を持つ関数型のツリー。構造体の定義がわかりやすい。

#[derive(PartialEq, Eq, Clone, Copy)]
struct SyntaxKind(u16);

#[derive(PartialEq, Eq, Clone)]
struct Node {
    kind: SyntaxKind,
    text_len: usize,
    children: Vec<Arc<Either<Node, Token>>>,
}

#[derive(PartialEq, Eq, Clone)]
struct Token {
    kind: SyntaxKind,
    text: String,
}

ポイントは...

  • 木構造に型がついてない
    • Node に type タグがあって、それによって区別する
    • trivia と non-trivia も型レベルで区別しない
  • トークンは、ソースコードを完全に保持する
    • トークンをすべて結合するとソースコードを再現できる
  • 特定のタイプの子要素にアクセスする際にには、子ノードを線形に走査する
  • 構文木の変更はおおよそ O(深さ) で行われる
    • 構文木は枝分かれして浅い傾向がある
  • 余分な誤った入力が存在する場合、ERROR というノードで保持する
    • 基本的には他のノードと同様に扱われる

最適化

  • 全てのトークンを heap に積むと効率が悪いので、interning している
    • https://en.wikipedia.org/wiki/String_interning
      • 異なる文字列を pool しておき、値を使いたいときはその参照を利用する
    • string interning は immutable なデータを要求するので、Green Nodes の木構造は不変である
  • トークンは小さな文字列に最適化された構造である SmolStr を使用する
  • TextSize も usize ではなく u32 を利用する
    • 4GB 以上のファイルはサポートできないなどの制約は受け入れている

Alternative なデザインについて

  • trivia の扱い方
    • ノードのフィールドに含む (swift and roslyn)
    • TOKEN のみの双方向の linked list を作る (dart)
    • intellij は rowan と同じ
  • 子ノードへのアクセス
    • あらかじめ明示的な領域を割り当てることで O(1) でのアクセスも実現できる (swift and roslyn)
    • これも intellij は rowan と同じ
  • 木構造の可変性
    • intellij は木構造を可変にしているが、実装が複雑になる (らしい)

SyntaxNodes (aka RedNode) とは

SyntaxNodes は、GreenNode に親ノードのポインタとノードを識別するためのセマンティクス (ここでは offset？) を追加したもの。GreenNode は interning されるので、token の値だけでは識別の方法がなくなってしまう...

type SyntaxNode = Arc<SyntaxData>;

struct SyntaxData {
    offset: usize,
    parent: Option<SyntaxNode>,
    green: Arc<GreenNode>,
}

impl SyntaxNode {
    fn new_root(root: Arc<GreenNode>) -> SyntaxNode {
        Arc::new(SyntaxData {
            offset: 0,
            parent: None,
            green: root,
        })
    }
    fn parent(&self) -> Option<SyntaxNode> {
        self.parent.clone()
    }
    fn children(&self) -> impl Iterator<Item = SyntaxNode> {
        let mut offset = self.offset;
        self.green.children().map(|green_child| {
            let child_offset = offset;
            offset += green_child.text_len;
            Arc::new(SyntaxData {
                offset: child_offset,
                parent: Some(Arc::clone(self)),
                green: Arc::clone(green_child),
            })
        })
    }
}

impl PartialEq for SyntaxNode {
    fn eq(&self, other: &SyntaxNode) -> bool {
        self.offset == other.offset
            && Arc::ptr_eq(&self.green, &other.green)
    }
}

ポイントは...

  • SyntaxNodeは親ノードを記憶する (これをカーソルとかジッパーと呼ぶ)
  • SyntaxNode は、ファイル全体における絶対的なオフセットを保持する
  • 等価性は同一性に基づく

最適化

  • Rowan ではスレッドセーフでない Rc を使っている
    • 木のトラバーサルはほとんどの場合で単一のスレッドで実行されるため問題ない
  • SyntaxNode ノードの root でしか GreenNode を保持する時に Arc を使わない
    • 他の SyntaxNode は Rc 経由でポインターを保持する
  • Rowan はスレッドローカルな SyntaxNode ノードのリストを保持するようにしている
    • トラバーサルなども安価に実行できる

!Sync の意味

It's a negative trait implementation for the Send trait as described in RFC 19.

Send は auto-trait なので、明示的に省きたい時がある。

https://stackoverflow.com/questions/30291217/what-does-the-exclamation-point-mean-in-a-trait-implementation

Alternative なデザインについて

  • once cell などを使った RedNode のメモ化
    • 構文木のメモリ要件を2倍以上に増やしてしまう
    • rowan では、自分のカーソル (親ノード) へのパスのみを保持する
    • C#は弱い参照を使用することで増加したメモリ使用量の削減を試みている
type SyntaxNode = Arc<SyntaxData>;

struct SyntaxData {
    offset: usize,
    parent: Option<SyntaxNode>,
    green: Arc<GreenNode>,
    children: Vec<OnceCell<SyntaxNode>>,
}

AST

Green Nodes によるツリーは片付けされてないので、片付けするのが AST のレイヤーのやることになる。

ASTNode は SyntaxNode を受けとって cast する。

pub trait AstNode {
    fn cast(syntax: SyntaxNode) -> Option<Self>
    where
        Self: Sized;

    fn syntax(&self) -> &SyntaxNode;
}

ポイントは....

  • SyntaxNodesをベースとした ASTノードなので、クローンするためオーバーヘッドが引き続き小さい
    • SyntaxNodes に含まれる Green Nodes の値はポインターがベース
  • 不完全なコードをサポートするためフィールドはすべてオプションになる
  • ASTノードを型のない SyntaxNode に変換することは常に可能
  • rust-analyzer の処理のほとんどは AST に対して行われる
    • 例外としては、マクロ展開や一部のIDE固有の機能 (構文の強調表示など) などがある
      • AST より生のトークンやSyntaxNodesに対して実装するほうが有利

Alternative なデザインについて

  • Intellij のAST では意味的な情報を紐づけてたりもしている

Parsing

Green tree は、所望のツリー構造の dfs によって構築される (ここで言う所望の tree 構造とはなんだろうか...?)

パーサーの interface は次のようになっていて、入力トークンと出力ツリーのための引数を受け取る。

pub trait TokenSource {
    fn current(&self) -> Token;
    fn lookahead_nth(&self, n: usize) -> Token;
    fn is_keyword(&self, kw: &str) -> bool;

    fn bump(&mut self);
}

pub trait TreeSink {
    fn token(&mut self, kind: SyntaxKind, n_tokens: u8);

    fn start_node(&mut self, kind: SyntaxKind);
    fn finish_node(&mut self);

    fn error(&mut self, error: ParseError);
}

pub fn parse(
    token_source: &mut dyn TokenSource,
    tree_sink: &mut dyn TreeSink,
) { ... }

ポイント

  • パーサーと構文木は独立しており、互いに依存していない
  • パーサーはトークンのテキスト内容については基本的には何も知る必要がない
  • トークンを連結して扱うために、TreeSink::token は1つ前だけではなく、さらに先の token に進むことがある
  • 構文エラーの報告やコメントは TreeSink レイヤーによって処理される
橙异橙异

I'm interested in how to use Rust to write an interpreter too. And I found we collect some same blogs，It's so funny.

このスクラップは2023/09/17にクローズされました