Closed29

ToyLisp devlog 1 (hir-def の途中まで)

自作ゲーム用スクリプト言語 + 言語サーバを作ります。できれば静的型付けにしたいですが、妥協するかもしれません。 HIR は rust-analyzer から学んでいきます。

以下常態

CST/AST 生成

rowan の最適化と API が最高

rowan で CST を作成

CST = テキストのツリー。構文エラーがあっても強引に組み立てられる。

Red-green tree

rowan の内部実装についてのノート。 rowan を使うだけなら不要な知識。

Green tree

親から子へ降っていける最低限のデータ。相対位置しか持たないため、 token, subtree の deduplication に活用される。

  • GreenToken / GreenNode は GreenTokenData / GreenNodeData への thin ポインタ
  • GreenChild は GreenNode からの相対位置を持つ

Builder が便利

Red tree: view to green tree

Green node/token にソース位置や親子関係を関連づけて wrapping する。異なる red node/token が共通の green node/token を持つことで deduplication が行われている

User AST

AST node/token は CST token/node の wrapper で、単純なキャストで作る。 CST から動的に子要素を探すメソッドなどを持つ。

言語実装と言語サーバを並行して作って行きたい。 Client 側 (エディタ) は VSCode がデバッグに良いらしい。

まずは client/server を接続した。非同期プログラミングなどの技術が不要で助かった。しかし 1 つ 1 つ地道に調べていく必要があるのはいつもの通りで、今後も時間がかかりそう。

  • File type "toylisp" を package.json から設定
  • LSP client から LSP server に "toylisp" ファイルの変更を通知
  • LSP server が応答

言語サーバは構文ハイライトができない。 Semantic highlighting が可能らしいが、 client (エディタ) 側が正規表現で作ったトークンに、言語サーバからメタ情報を追加する機能に見える?

→ 追記: LSP の semantic tokens だけでハイライトできるみたい。でも動かせなかった?

それぞれのエディタは、独自の正規表現をパーサにしているらしい。習得が辛い。しかし今日では、 tree-sitter でパーサを書けば、任意のエディタでハイライトできるかもしれない。

tree-sitter (の CLI) に小さな PR を出した。 expand_path って言えばよかった。

ひとまず Emacs でハイライトを確認。 NeoVim (nightly) でも動きそう (素の Vim 用プラグインは無し) 。案外 VSCode で動かすのが一番手間になるかも

言語サーバでエラーを表示した。 span を line/column に復元するのが 1 手間かかった。 Column は UTF-16 で表すらしいが…… ascii 文字縛りでもいいかも:

追記: rust-analyzer の line_index.rs を借りて UTF-16 の (line, column) 位置を返すことにした

フロントエンド (AST, LS, ハイライト) の開発環境が整った。既にハードルを超えたかもしれない。
今後は前に進んで行ける。自分が toylisp のユーザになる日が楽しみでならない。

codespansource-span でターミナルの出力もリッチにしたい。まだ優先度は低い

追記: ariadne が出ていた。 flume の作者なので信頼感がある。名前も短いし、たぶんこれを使う。

簡易 validation を追加:

早くコードが動くようにしたい。

変数は動的型付け
関数は静的に解決
メソッド (予定) は動的に解決かな

ToyLisp が動的言語であったとしても、型を構文に入れて良さそう。

妄想:

(data (Vec3 T)
    x T y T z T
    :pub
    (met len () -> T
        (sqrt (+ (* self.x self.x) (* self.y self.y) (* self.z self.z))))
    :pub
    (met dot (other Self)
        (let a (* self.x other.x)
             b (* self.y other.y)
             c (* self.y other.y)
         in
            (+ a b c)))

むしろ:

(met dot (other Self)
    (var a (* self.x other.x)
        b (* self.y other.y)
        c (* self.z other.z))
    (+ a b c))

開発の順序としては、動的言語 → 型注釈 → 型推論 → 静的ダックタイピングで generics かな。
どこまで行けるか

Data flow (compilation passes)

rust-analyzer/guide/dev と rustc dev guide から方針を借りてくる。

Summary

AST → HIR/THIR で マクロ展開名前解決型推論 のパスを経る。また、名前解決付近で desugaring も行われる。

効率の観点では、 interning と incremental compilation が興味深い。また、アイテム宣言と定義が どこ に保存され、どのような ID で参照されるかも重要。

Wikipedia

伝統的には、 AST を中心にコンパイルしたらしい:

Source → Token 列 → AST → Modified AST → Executable program

  • lexical analysis: ソースからトークン列を生成
  • syntax analysis: トークン列を木 (AST) に起こす
  • semantic analysis: AST を解析する

しかし、このモデルは古そうだ。 AST の生成時にソースとの対応が失われたり、構文木以外の中間表現 (HIR) への言及が無い。忘れてしまおうと思う。

rustc

rustc dev guide によると、
ソースコード → AST → マクロ展開後 AST → HIR → THIR → MIR

  • HIR: 構文糖衣が展開された AST.
  • THIR: 型が付いた HIR
  • MIR: CFG (control-flow graph) でコードを表現

Interning については: Identifiers in the Compiler - Guide to Rustc Development. ID が多すぎる。 ToyLisp では ID を単純に表現したい

rust-analyzer

rust-analyzer における HIR は rustc における THIR に相当すると思う (型の確定もやっているはず) 。

ID について:

  • Source map pattern: AST ID → AST (HIR 側では AstId を使用)
  • interning: Positional ID → Numeric ID にマッピングするらしい

rust-analyzer の方針に乗っかるなら、 salsa を使い始めるのが良さそうだ。 rowan 同様に 4,000 行未満の小さなクレートで、洗練された API も期待できそう。

内容は、 Interning のサポートと、インクリメンタルな計算のキャッシュだろうか。

小さくて速くて綺麗なクレートに憧れる。これさえ読めば先に進める、そんなフレームワークが特にいい。

Youtube: Explainging Rust Analyzer (2021/07~)

誰かのメモ: rust-analyzer-notes

僕の (役に立たない) メモ:

rowan を使って Eldrio 言語を作っている人のブログ記事を見た。 CST, AST, HIR など、基本的な用語の理解に良さそう: Part Nineteen: Code Representations - arzg's website

発展的な内容には乏しい。やはり rust-analyzer HIR のソースを読んでいくしかないか。

Lowering が構文糖衣に限定されていた。 AST を別のデータに変換するだけでも lowering とは呼べないのだろうか。
HIR が rust-analyzer の HIR とはかなり違った (たとえば imports などの情報が無く、通常の AST と同様に見えた)

亀の歩み

RA 調査中 (hir_def)

Collections

  • ItemTree: 宣言の syntax node (ItemTreeNode) のツリー
    対象モジュール内の宣言のみを持ち、サブモジュールのデータを持たない。
  • Crate の DefMap: ItemScope のツリー
    クレート内の全モジュールに関するツリー。

ItemScope は、 import が解決された ItemTree みたいなもの。 Name → 宣言 のマップであり、また親子モジュールへの参照 (index) を持つ。

DefMapBody に関しても同じデータ型を使い回しているが、分けた方が明瞭なコードになる気がする。要調査

IDs

宣言のコレクションは ItemTree

  • Interning: 宣言 (in ItemTree) → 宣言位置 (ItemTreeId + Idx) → Salsa interned ID
  • Lookup: Salsa interned ID → 宣言位置 (ItemTreeId + Idx) → 宣言 (ItemTree)

Typo の PR が増えてしまった (rust-analyzer, rowan, mun) 。 mun の bread-first search はちょっと面白かった。

rust-analyzer hir の docstring が古い。

宣言を再帰的に集めるところまで書けた。まずは単ファイルのインタープリタを作るけれども、データの変換ステップ (pass) は RA を踏襲したい。

DefMap (クレート用)

nameres::collector::collect_defs: ItemTree → DefMap

ItemTreeData
    each Arena<Xxxtem>

DefMap
    Arena<ModuleData>
        ModuleData
            ItemScope
                each HashMap<Name, ModuleDefId>
                    ModuleDefId
  • ModItem: Import を取る ItemTree 側 item の upcast
  • ModuleDefId: Import を取らない解決済み item の upcast

DefMap (Body 用)

調査中

toylisp 関係なし

コンパイラ 構造と原理 の P48 まで来た。理論を理解すればもっと自由になれますよ、という本で、次々と形式的表現が現れる。確かに理工書だ! 解説は丁寧だし、読者を舐めていない……そんな電波を受信したので、この本が読めなかったら 100 % 自分のせいだと思う。逆に背伸びして読み切ったら自信がつきそう。なぜか興味よりもプライドのために読んでしまう。

書見台が良かった。文庫本よりも大きな本は、書見台に設置して読むものだったのだと思った。注文した翌日に届くものだから、毎日台が増え続け、いつの間にか 7 台の書見台が揃ってしまった。詰み本崩しは進みそうだけど……馬鹿だね、、

RA) FunctionData は ItemTree の Function から cfg フラグなどを取っ払った view みたいなものかな……?

tlp) HIR definition としての ProcData にテストコードから辿り着けるようになった。

todo)

  • Body (式) の interning を調べて実装する
  • Source map pattern を把握する
  • MIR を作るべきか検討する
  • 四則演算が書ける main 関数を書けるようにする

数値は token にした方が、テキストに触れやすくて (&str) 良さそう。

文字も数値も token になったけれど、 lexer は streaming に (Iterator) にしていない。空白などの trivia を一気に跨ぎたくなる場合を考えてのことだけれど、 Lisp なら streaming にしてもいいかも。

ariadne は僅か 1,000 行! と思ってソースを見たものの、これは実用的ではないな……。 LSP の severity を考えていないし、『クソース書き換えます』が残っている。 codespan を見た方がいいかな。

久しぶりに rust-analyzer の解説動画を観た。構文の話が終わり、ヤッター HIR が始まる! ための導入だった。
Explaining Rust Analyzer 18: Token Trees as Macro Expansion Interface

  • VSCode でコードを折り畳んでいるのがいい。うちの Emacs も対応させよう。
  • FileAstId は『2 番目の構造体』のような positional な ID 。名前の変更には強い。 AstIdMap は ID を名前の構文にマッピングする。構文をいじっても ID が変わらない場合は、再計算を省略できる。
  • HirFileId = FileId | MacroFile. 再帰的なマクロ呼び出しは (MacroFile, Parent) の形で表現できる。
  • マクロ呼び出しには名前解決も必要。ですよね

次回からいよいよ解析に入っていくそう。キタキタキタ!

RA から rowan への移植 PR が来ていた。ユーザの迷いが減って良さそう。 examples 追加も欲しいかな

hir_def における式の lowering は AST との 1:1 で、 desugaring は無い……っぽい。 hir_def はほぼ AST だった、が結論になりそう……?

  • Source map pattern
  • cfg フラッグの適用 (ItemTree item → definition data)
  • データはなるべく Vec に入れる
  • マクロ展開

まだ source map pattern を吸収していないけれど、 rowan の PR が来るまで次のクレートを読もうかな。


この構成は理想的では無い、とあらゆる場所に書いてある。

SSR (structural search and replace) が面白そうだったけれど、 Emacs クライアントからは利用できないみたい。応用すればコード編集用の小さな DSL が作れそう……


RA の LiteralSyntaxNode なのは source map patter のためかな (AstNodePtr で指せる) 。やっと token/node の意図 (使い分け) を把握できた気がする。なぜ AstTokenPtrAstTokenElement が無いのか、という本質情報のためには、 rowan の GC を把握しないと……

→ 違った。 #[attr] 込みで Node にしているのか。 #[allow(unused)] 0.0 みたいなコード書くかなぁ……? ToyLisp では絶対に書かない。

やはり AstElement を使っていく方向性もアリかな


hir_def の次にどのコードを読むべきだろうか。解析部分も読みたいけれど、 今は RA のエラー表示が知りたい。

たまに偽陽性のエラーが出ることから、独自のエラー解析を rustc のエラー型経由で文字列化している気がする。 LSP の publish_diagnostics 的なコードから探していこう。

rowan の PR が 1 分まえに merge された。 trait を乗り換えよう

ECS をやり過ぎて言語開発への情熱が蘇ってきた。

  • Explaining Rust Analyzer 20: assigning IDs, HirFileId and AstIdMap
    もう観ている人数が 100 人以下だ。 rustc を読むオンラインミートアップに吸われたかな?
    hir_def では AST から ItemTree (主にファイル内 item の Vec) を作ってパスなどを ID で呼ぶ。このような、より構造的なデータへの変換を RA では lowering と呼んでいる。 ItemTree には top-level module item のみが入っており、 AST に関しては ID しか持たない (そして確か ID は階層順かつ item 種別毎に振られていたはず) 。したがってソースが書き変わっても ItemTree はあまり変化せず、 ItemTree に依存した計算は再計算せずに済む。

  • Explaining Rust Analyzer 21: live coding faster AstIdMap
    視聴中……

ECS 記事も (WIP だけど) 出したし toylisp に戻ろう。

確か hir_def を読んで式の interning まで行った。

  • 識別子やパスも全部パタン扱いなのか?
  • マクロ以外の名前解決も hir_def でしてる? それとももう一度データを変換してから実行している?
  • Source map パタンも真似ておこう

目標: 名前解決してシンボルをリネームする。ひとまず ssr (semantic search & replace) や hir_ty を読んで見通しを立ててからコードを書こう。実はコードは書くよりも読む方が速かったりする……

4 ヶ月も放置してしまったので、一旦締めます。また ToyLisp devlog 2 を再開します〜

このスクラップは4ヶ月前にクローズされました
ログインするとコメントできます