自作ゲーム用スクリプト言語 + 言語サーバを作ります。できれば静的型付けにしたいですが、妥協するかもしれません。 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 から動的に子要素を探すメソッドなどを持つ。

そういえば repo: tlp (ToyLisp)

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

• tower-lsp
• Extension API | Visual Studio Code Extension API

まずは 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 のユーザになる日が楽しみでならない。

codespan か source-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 のサポートと、インクリメンタルな計算のキャッシュだろうか。

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

rowan/salsa の使用例

• sky-sl
• mun

Youtube: Explainging Rust Analyzer (2021/07~)

誰かのメモ: rust-analyzer-notes

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

• ra の 機能紹介 からソースファイルに飛べる
• ra は UTF-8 対応 の LSP 拡張を実装している
• VSCode: Open symbol by name でプロジェクト中の全アイテムを検索できる。
  • 最近の Emacs なら consult-lsp に対応するコマンドがある。 consult については: Emacsの次世代ミニバッファ補完UI
  • なおファイル中のアイテムを検索するなら、 Emacs には lsp-ui-imenu や consult-imenu がある。

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) を持つ。

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

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 の Literal が SyntaxNode なのは source map patter のためかな (AstNodePtr で指せる) 。やっと token/node の意図 (使い分け) を把握できた気がする。なぜ AstTokenPtr や AstTokenElement が無いのか、という本質情報のためには、 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 を再開します〜