toylisp

前回 に引き続き、自作ゲーム用スクリプト言語と言語サーバを作っていきます。 rust-analyzer を参考に取り組んでいますが、かなり無謀な挑戦になりそうです。

全体的な進捗は tlp#1 に挙げています。

https://github.com/toyboot4e/tlp

前回までのあらすじ

フロントに専念しています。 hir_def の複雑さにやられて開発が止まっていました。

rust-analyzer から学んだこと

• rowan
  ソースを一旦 loss-less な具象構文木に変換します。無効な構文のソースも扱いやすくなります (例: 関数定義に引数が無い など) 。

• salsa
  インクリメンタルな計算のフレームワークです。ソースに変更があった時には、必要最小限の計算を実施します。

現在の toylisp

AST から hir_def への変換を試みています。 hir_def はソースコードの位置情報をより安定な index に変換し、出てくるアイテムを interning したデータです。名前解決を可能にするのが特徴で、可視アイテムのリスト (ItemScope) や式毎のスコープ情報 (ExprScope: Name → Patid) を作成します。

ra hir_def 調査 (1): 名前解決の気配

rust_analyzer の hir_def は、スコープを整理するパスと要約できそうです。

1. Item レベルのマクロ展開と名前解決を行います
2. ブロック毎にマクロ展開と名前解決をします。また式毎に ExprScope を割り当てることができます

後のパス hir_ty では、 hir_def 上のデータ ID から型データへのマッピングが生成されます。

Rust の文法について

文法が分かっていないとソースが読めませんね。

• Items: モジュール直下に置けるものが item です。ローカル変数 (正確には local bindings) は item ではありません。
• Patterns: 引数名や let の左辺、 for の左辺、match arm などは pattern です。 Pattern は再帰的で、変数名を追加するときは Identifier Pattern に行き着きます (binding pattern) 。 pattern @ subpattern の形でパタンに別名を付けることができます。これは identifier pattern にも有効です (let a@b = 10; などと書ける) 。
• Path: :: 区切りです。Field access などには個別の文法が用意されています。
• Namespaces: 型・変数・マクロで分かれています。モジュールは型の名前空間に、関数は変数の名前空間に属します。

Source map pattern でインクリメンタルな計算を活かす

ソース変更時の再計算を最小限に留めるために source map パタンを使います。 nameres/tests/incremental.rs に実例があります。利用方法は調査中です。

• AstIdMap (hir_expand) : SyntaxNodePtr の Arena です。 hir_def の lowering で利用します
• BodySourceMap (hir_def): SyntaxNodePtr と ItemTree 内 Arena への Idx 間の変換の記録。 hir_ty で利用されます

https://github.com/rust-lang/rust-analyzer/blob/master/docs/dev/guide.md#source-map-pattern

pub struct BodySourceMap {
    // SyntaxNodePtr → ExprId
    expr_map: FxHashMap<ExprSource, ExprId>,
    // ExprId → SyntaxNodePtr
    expr_map_back: ArenaMap<ExprId, Result<ExprSource, SyntheticSyntax>>,

    // SyntaxNodePtr → PatId
    pat_map: FxHashMap<PatSource, PatId>,
    // PatId → SyntaxNodePtr
    pat_map_back: ArenaMap<PatId, Result<PatSource, SyntheticSyntax>>,

    /* ~~~~ */
}

/// Maps items' `SyntaxNode`s to `ErasedFileAstId`s and back.
#[derive(Default)]
pub struct AstIdMap {
    /// Maps stable id to unstable ptr.
    arena: Arena<SyntaxNodePtr>,
    /// Reverse: map ptr to id.
    map: hashbrown::HashMap<Idx<SyntaxNodePtr>, (), ()>,
    _c: Count<Self>,
}

Item レベルの名前解決

• ファイル毎の ItemTree (ItemTree::file_item_tree_query)

  • A simplified AST that only contains items
  • Import などの？ desugar を行う
  • マクロ展開は行わない。 #[cfg( .. )] 属性も適用しない

• クレートの DefMap (DefMap::crate_def_map_query)
  ModuleData のツリー、ひいては ItemScope のツリー

  • ModuleData: モジュールの親子関係と ItemScope
    • ItemScope: あるスコープから見える item ID 一覧 (実体は ItemTree の中)

• モジュール内部の mod { .. } 宣言に対しては ModuleData が作られません。 ModuleData の中に Mod として保存されます。 ModuleData は FileData と言ってよいです。
• ItemTree 内の Function を FunctionData に写すと #[cfg( .. )] 属性が適用されます。

ブロックレベルの名前解決

• Body: 関数定義のコードブロックなど

  • ブロックの DefMap: ブロック内のアイテム ID 一覧
  • ブロック毎の ItemTree (ItemTree::lower_item_tree)

• ExprScopes
Body から計算できます。 Body 中の式毎に ScopeEntry { Name, Pat } の配列を割り当てます。

診断情報

名前解決に失敗したら診断情報に追加するようです。これはどう使うんでしょう……？

#[derive(Debug, PartialEq, Eq)]
pub struct DefDiagnostic {
    pub in_module: LocalModuleId,
    pub kind: DefDiagnosticKind,
}
#[derive(Debug, PartialEq, Eq)]
pub enum DefDiagnosticKind {
    UnresolvedModule { ast: AstId<ast::Module>, candidates: Box<[String]> },

    UnresolvedExternCrate { ast: AstId<ast::ExternCrate> },

    UnresolvedImport { id: ItemTreeId<item_tree::Import>, index: Idx<ast::UseTree> },

    UnconfiguredCode { ast: AstId<ast::Item>, cfg: CfgExpr, opts: CfgOptions },

    UnresolvedProcMacro { ast: MacroCallKind, krate: CrateId },

    UnresolvedMacroCall { ast: MacroCallKind, path: ModPath },

    MacroError { ast: MacroCallKind, message: String },

    UnimplementedBuiltinMacro { ast: AstId<ast::Macro> },

    InvalidDeriveTarget { ast: AstId<ast::Item>, id: u32 },

    MalformedDerive { ast: AstId<ast::Adt>, id: u32 },
}

#[derive(Debug, Eq, PartialEq)]
pub enum BodyDiagnostic {
    InactiveCode { node: InFile<SyntaxNodePtr>, cfg: CfgExpr, opts: CfgOptions },
    MacroError { node: InFile<AstPtr<ast::MacroCall>>, message: String },
    UnresolvedProcMacro { node: InFile<AstPtr<ast::MacroCall>>, krate: CrateId },
    UnresolvedMacroCall { node: InFile<AstPtr<ast::MacroCall>>, path: ModPath },
}

構文の妄想 (1)

いつ動くようになるか分かりませんが、モダンな構文を持ち込みたいと思っています。それはもう Lisp ではないのかもしれませんが……

let

let はスコープを作らなくていいと思います。必要なら (do .. ) で囲みます。

;; 従来の Lisp
(let ((a 20)
      (b 30))
    ;; let は明示にスコープを作る
    (+ a b))

;; toylisp (予定)
(do (let a 20)
    (let b 30)
    (+ a b))

if (分岐)

If / then / else ではなく when / when / when にします。 Haskell の multi-way if ですね:

;; 従来の lisp
(defun main ()
    (let ((b t))
        (if b (progn
                  (print "true")
                  t)
            (print "false")
            nil)))

;; toylisp (予定)
(proc main ()
    (let b true)
    (if (b (print "true")
            b)
        (_ (print "false")
            false)))

というか cond か……

マクロ呼び出し

macro_name! の形で関数呼び出しと区別をつけようと思います。トークンレベルで区別が着くため、解析が楽になるはずです。

考え中……

この辺からよく考えないといけない気がします……

if (パタンマッチ)

• match 相当
• パターンガード
• if let 相当

関数定義

型を書ける特殊形式を builtin にします。

(proc fib (x:i32) -> i32
    (if ((= x 1) 1)
        ((= x 2) 1)
        (_ (fib (- x 1) (- x 2))))

構造体

(struct Vec2i
    x:i32
    y:i32
    (proc @.distance (other:&Self) -> f32
        (let dx (- x @.x))
        (let dy (- x @.y))
        (sqrt (+ (* dx dx) (* dy dy)))))

(let v1 (Vec2i 1 1))
(let v2 (Vec2i 2 1))
(assert_eq (v1.distance v2))

タグ付き共用体

• うーん

ジェネリクス

• Zig のように型を返す関数として書く？

型推論 (1) Unify の存在

型推論……何も分からない。単なる論理式の問題に持ち込めるらしいですが、今の視点では wizard's magic です。四段上の壁を覗いてみます。

tox

langs-in-rust に tox を見つけました。 Lox (Crafting Interpreters) がベースです。ランタイムこそ動的型付けですが、静的に型チェックを実施するようです。

たとえば以下のコードをコンパイルします:

fn main() {
    let a = true;
    a = "a";
}

Bool 型の変数 a に文字列 "a" を代入しようとしています。 Lox だと実行時エラーになるところですが、 tox では静的に弾かれます:

toylisp でもこれがやりたいですね。

Unify! なんだか見覚えのある言葉が出てきました。そう、それは……

速攻 MinCaml コンパイラ解説

コンパイル技法: パターンマッチ でも推されていた 速攻 MinCaml コンパイラ解説 です。 型推論の章 で出てきました。型推論のワンステップを unify と呼び、再帰的に unify すれば全部の型が分かるのでしょうか？

エアプにもまだ遠いです。ひとまず情報源は見つけました。

ra hir_def 調査 (2): スコープと Resolver

ローカル変数を作りたい！　フロントエンドにおける名前解決を見てみます。

Name → PatId

Resolver は Scope のスタックです:

#[derive(Debug, Clone)]
pub struct Resolver {
    scopes: Vec<Scope>,
}

ざっくり見て Stack = ModuleScope(DefMap) | ExprScope(ExprScope) です:

#[derive(Debug, Clone)]
enum Scope {
    /// All the items and imported names of a module
    ModuleScope(ModuleItemMap),
    /// Brings the generic parameters of an item into scope
    GenericParams { def: GenericDefId, params: Interned<GenericParams> },
    /// Brings `Self` in `impl` block into scope
    ImplDefScope(ImplId),
    /// Brings `Self` in enum, struct and union definitions into scope
    AdtScope(AdtId),
    /// Local bindings
    ExprScope(ExprScope),
}

// FIXME how to store these best
#[derive(Debug, Clone)]
struct ModuleItemMap {
    def_map: Arc<DefMap>,
    module_id: LocalModuleId,
}

#[derive(Debug, Clone)]
struct ExprScope {
    owner: DefWithBodyId,
    expr_scopes: Arc<ExprScopes>,
    scope_id: ScopeId, // Idx<ScopeDasta>
}

ExprScope は ExprScopes 内の ScopeData を参照します:

#[derive(Debug, PartialEq, Eq)]
pub struct ExprScopes {
    scopes: Arena<ScopeData>,
    scope_by_expr: FxHashMap<ExprId, ScopeId>,
}

#[derive(Debug, PartialEq, Eq)]
pub struct ScopeData {
    parent: Option<ScopeId>,
    block: Option<BlockId>,
    label: Option<(LabelId, Name)>,
    entries: Vec<ScopeEntry>,
}

#[derive(Debug, PartialEq, Eq)]
pub struct ScopeEntry {
    name: Name,
    pat: PatId,
}

ExprScopes の作成

ExprScopes は Body を解析して作ることができます:

impl ExprScopes {
    // ~~~~
    fn new(body: &Body) -> ExprScopes {
        // ~~~~
    }
    // ~~~~
}

この際全ての式を歩き、式に対応するスコープ (の連結リスト) を記録します。

Resolver の組み立て

Resolver 生成の trait があります:

pub trait HasResolver: Copy {
    /// Builds a resolver for type references inside this def.
    fn resolver(self, db: &dyn DefDatabase) -> Resolver;
}

定数や関数など、式を含む定義の ID に対して実装されています。 Resolver を組み立てて返します:

impl HasResolver for FunctionId {
    fn resolver(self, db: &dyn DefDatabase) -> Resolver {
        self.lookup(db).container.resolver(db).push_generic_params_scope(db, self.into())
    }
}

実装 1: ローカル変数の名前解決 (hir_def)

rust-analyzer を写経して大胆に hir_def を実装します。これまで苦戦して来ましたが、ついに壁を越えました。

Import, マクロ展開や desugar はおいておきます。

Lowering module items (→ ItemTree)

ast::Document を歩きます。過去に実装済みです。

• すべての ast::Form ast::Item に ID を与える (Arena に保存する)
• AST における Item / Expression を区別する (全部 Form なのは都合が悪い)
  なお lisp では式と文に構文上の違いは無い (; が無い) ため、 Stmt は作らないことにしました。

Module ItemScopeの収集

ItemTree を歩きます。過去に実装済みです。

• すべての item に関し Name → Id<ItemLocation<T>> のマッピングを作る
  Import 解決などは後のステップで

Lowering Body

関数定義の ast::Node を降りて行きます。

• すべての Expr に ID を与える (Arena に保存する)
• すべての Pat に ID を与える (Arena に保存する)
  • スコープに変数を追加する ast::Pat は、より明示的な expr::Pat::Bind に変換する。 hir_def で使い勝手の良い変換をしていい

式スコープの計算

Body のルート (expr::Block) を降りて行きます。

• すべての式に対してスコープを割り当てる

Source map pattern の実装

• AstIdMap: Item の source map です。

  • AstIdMap の作成 (AST を歩きます。このコードは丸コピしました)
  • Idx<SyntaxNodePtr> の newtype を作って N: AstNode の型を付ける
  • Item のフィールドに AST ID を追加、 ItemTree への lowering 時に記録

• BodySourceMap: Expr / Pat の source map です。
  Body の lowering の際に対応を記録します。

テスト (式スコープ)

(test) 時点のスコープを調べる方法でテストを作ってみました:

    do_check(
        r"(proc main ()
              (let x 0)
              (let y 1)
              (let z 2)
              (test))",
        &["z", "y", "x"],
    );

コンパイル

Body に保存された式は実行順になっていません。 Body をコンパイルする時は、 AST を使って Body 直下の式をイテレートする のが良さそうです (desugaring があると厄介ですが) 。名前解決などには HIR の機能を利用できます。

一旦 main 関数をローカル変数付きで実行できるようになりました。考えたことなどは『実装 3 』に書きます。

残り作業

RA におけるテスト (式スコープ)

マーカー ($0) 位置の式に割り当てられた式スコープを確認しています。 offset → ExprId の変換には BodySourceMap を使っています。

TODO? (やらなくてもよし)

Resolver

Item スコープと式スコープを合わせて、名前空間毎の名前解決 (Name → PerNs) を行います。

TODO: 必要になったら

インクリメンタルな計算のテスト

TODO

Rust の edition

2018 から 2021 に更新しました。 Or パタン (A | B | C) に $pat:pat でマッチできるようになりました。古いプロジェクトは更新しよう！

実装 2: シェル並みの言語

ただし外部コマンドは無いものとします。

むしろ VM の知識が足りなくなってきた

ra hir_def 調査 (2): チートシート

データ型

用語

• Arena: push-only な Vec
• Interning: データの実体を一箇所に集約すること。 Fly object パタン。 Arc ベースのものと ID ベースのものが混在しているが、いずれ salsa 提供の ID ベースの interning に統一されそう。
• Lowering: AST を HIR 型に変換して Arena に保存すること
• Source map: Arena に入れた HIR データの Idx と AST の SyntaxNodePtr 間の対応

ランタイムは小さい方が良い

VM はともかく、コンパイラも salsa や HIR に依存しない方が良い気はしてきた……

実装 3: 静的型付けの VM (スタックベース、バイトコード)

実装 1, 実装 2 と並行して VM について考えたいと思います。なんか…… 思っていたよりも全然手強い 気が……

スタックついて

• Rust の primitive とバイト列との相互変換
  Primitive 型の実装は Rust に任せたいと思います。バイト列への変換・バイト列からの復元においては、エンディアン (バイトの並び順) を考える必要がありそうです。 f32::to_ne_bytes, f32::from_ne_bytes のような関数があります。

  • スタック内の primitive について
    Native endian を使用する？
  • 定数について
    ある endian で保存し、実行時に native endian に書き換える？

• スタックの型は Vec<u8> と Vec<Word> のどちらにすべきか。たとえば bool 型のローカル変数に 8 バイト使って良いのか
  x86-64 (64 bit) のスタックは 8 バイトの word 列です。 Word の中にギチギチに変数を詰める気はしません？　スタックを節約する意味が無い、命令種別が増えすぎるなどの理由から Vec<Word> になる気がします。

コールフレームについて

• ローカル変数領域は動的に伸ばすべき？
  たとえば大量のローカル変数を持つ関数の冒頭で再帰呼び出しする場合、動的にローカル変数領域を拡大した方がスタックの使用量は減るはずです。でもスタックは十分に長いので気にする程ではない？

命令について

• Add, Mul のような計算命令について
  i32, i64, f32, f64 など primitive 型毎に命令を用意する必要がありそうです？

ユーザ定義型について

• ユーザ定義型の命令について
  ユーザ定義型の計算は primitive 型の計算に帰結する気がします。 Push や Pop のような命令は常に 8 バイトのオペランドを取れば良い気がします。

• ユーザ定義型のローカル変数について

• ユーザ定義型の定数について
  ユーザ定義型は 1 word よりも長い可能性があります。一旦定数はリテラルのみとするのが簡単そうです。

• アラインメント？
  1 つの primitive が 2 word に跨ることがあり得ないようにする

• 他関数への値渡し
  1 word のコピーで終わらないため大変そう？

• #[repr(C)] のアラインメントとは
  構文の順にフィールドを走査する。それぞれのフィールドがその大きさでアラインメントされるようにパディングを入れる。最後に構造体全体が最大のフィールドのサイズでアラインメントされるようにパディングを入れる。

レジスタについて

• VM で関数の引数をレジスタ相当のフィールド (スタック領域) に置く意味はあるか

ra hir_ty 調査 1: WIP

ついに hir_def を突破したので hir_ty を調べていきます。 * などの builtin 演算子は引数の型によってオーバーロードしなければなりませんから、まずは型情報の持ち方を調べたいです。

hir_def の知識補完

• Resolver: Vec<Scope>
• Scope ~ ExprScope | ItemScope

infer

• 型変数: 現在不明な型。 ena の union-find で型変数を記録？

infer のアウトライン

• infer: Body → InferResult

• InferResult: Expr | Pat → Ty

// 大体こんな感じ
#[derive(Debug)]
pub struct InferenceResult {
    pub type_of_expr: ArenaMap<Idx<Expr>, Ty>,
    pub type_of_pat: ArenaMap<Idx<Pat>, Ty>,
}

• infer → infer_body → infer_expr_coerce → infer_expr_inner → 式にマッチして infer_* → write_expr_ty

    fn write_expr_ty(&mut self, expr: ExprId, ty: Ty) {
        self.result.type_of_expr.insert(expr, ty);
    }

• infer_block → infer_expr (再帰), infer_pat
• infer_pat → write_pat_ty

    fn write_pat_ty(&mut self, pat: PatId, ty: Ty) {
        self.result.type_of_pat.insert(pat, ty);
    }

infer の具体的な流れ

TODO

lower

salsa 2022 の調査

salsa (インクリメンタル計算のフレームワーク) のメジャーバージョンアップが近づいています。

変更は大きいです。早めに乗り換えたいと思います。

• ブログ記事 (ほぼ通知のみ)
• チュートリアル (unstable)
• Cargo.toml からの salsa-2022 検索結果
  dada が最も参考になるかも？　ただし rowan が使われていません。そこまで変わるのか……

データ指向の API に

これまでの API:

let data = db.create_data(args);

salsa 2022 の API:

let data = DataType::new(db, args);

• #[tracked] でフィールド毎に計算追跡
• #[specified] とは？
  メモ化される値を手動で登録できる (はず)

Interning を積極的に (#[interned])

• 関数の返値は Arc<T> よりも ID を用いる
  • #[return_ref] で参照を返すと Arc<T> に等しい
  • 属性無しだと clone が返る

たとえば Name(SmolStr) より salsa の interned ID (World) を使う。

ランダム逆引き

• FileId 毎に入力テキストを設定するには？
  DB の外で FileId → SourceInput のマップを持てばいい

• rowan よりもインクリメンタルな計算に強くなる？
  そんなに変わらない気もする？　ただそもそも rowan のように self-contained なテキストツリーである必要は無く、また rowan 無しの方が Span の型変換が減るはず。 rowan 的な builder と traversible な API だけが残れば良い気がする。

• ItemTree は不要になる？　Source map パタンはどうなrU?

  • Item が Span を持つ
  • Expr 等は Span を持たない (サブテーブルに span を置く)
  • Expr → Span のマップ (body source map) は後のパスで利用されない。 Span のみが更新される場合は再計算が止まる
  • Span → Expr のマップは？
    たぶん動的に探す？

• 帰値の構造体を #[salsa::tracked] とマークすべきか？
  必要になったら (別の構造体にラップして) マークすれば良い。というのも tracked 関数の第二引数に利用できるのは salsa 構造体のみのため。また第三引数を取らない方が効率が良いらしい (Tracked functions are the unit of reuse)

• #[salsa::tracked] 関数へのアクセスポイントは？
  salsa 構造体のメソッドにするのが定石的みたい。たとえば Function に fn body(&self, db: &dyn IrDb) を生やす。

dada を読む (1): ソース〜 IR データ定義

発達したクレートの内、 salsa-2022 を使っているのはdada のみです。 salsa-2022 に乗り換えるということは 振り出しに戻る ということですが、一目見て価値はある……かを確かめる必要があります。なぜならハイナードを志しているから……

dada のソースカウントは約 16,000 行でした。読めないことはないですね。今週中にやっちゃいましょう。

dada-lsp

テキストの同期のみ。 LSP は確かソース位置を line, column (UTF-16) で話すので、オフセット表示 (UTF-8) との相互変換が必要なはずです。 trait DataLspMethods で変換しています。

trait DadaLspMethods {
    fn lsp_position(&self, input_file: InputFile, offset: Offset) -> Position;
    fn lsp_range(&self, span: dada_ir::span::FileSpan) -> Range;
    fn lsp_location(&self, span: dada_ir::span::FileSpan) -> Location;
    fn lsp_diagnostic(&self, dada_diagnostic: dada_ir::diagnostic::Diagnostic) -> Diagnostic;
}

impl DadaLspMethods for dada_db::Db {
    fn lsp_position(&self, input_file: InputFile, offset: Offset) -> Position {
        let line_column = dada_ir::lines::line_column(self, input_file, offset);
        Position {
            line: line_column.line1(),
            character: line_column.column1(),
        }
    }

    fn lsp_range(&self, span: dada_ir::span::FileSpan) -> Range {
        Range {
            start: self.lsp_position(span.input_file, span.start),
            end: self.lsp_position(span.input_file, span.end),
        }
    }

    fn lsp_location(&self, span: dada_ir::span::FileSpan) -> Location {
        Location {
            uri: Url::parse(span.input_file.name(self).string(self)).unwrap(),
            range: self.lsp_range(span),
        }
    }
    // ~~~
}

• 変換先では本当に UTF-16 を扱っている？
  見た目上の 1 文字を 1 column とカウントしている (rune? codepoint?)
• 変換先でのキャッシュの持ち方は？
  LineTable で行毎に区切って 2 分探索で column 特定

data-ir (1): ソース情報

まずは line / column 情報を見てます:

#[derive(Debug, PartialEq, Eq, Hash)]
pub struct LineTable {
    /// Always has at least one element for the first line
    lines: Vec<LineInfo>,
    end_offset: Offset,
}

#[derive(Debug, PartialEq, Eq, Hash)]
struct LineInfo {
    /// Offset of line start
    start: Offset,
    /// Spans of chars with utf8 length > 1
    wide_chars: Vec<Span>,
}

Column 位置が UTF-16 ではない……？

impl LineTable {
    // ~~~~
    fn line_column(&self, position: Offset) -> LineColumn {
        match self.lines.binary_search_by_key(&position, |l| l.start) {
            Ok(line0) => LineColumn::new0(line0, 0u32),
            Err(next_line0) => {
                let line0 = next_line0 - 1;
                let line = &self.lines[line0];
                // not quite column yet, because there may be wide characters between line start and position
                // at this point it's the byte offset from line start
                // we need to adjust for it
                let mut column0 = position - line.start;
                for wc in line.wide_chars.iter() {
                    if wc.start >= position {
                        break;
                    }
                    // e.g.: 🙂 will have len 4, but we count it as 1 character, so we subtract 3
                    column0 -= wc.len() - 1;
                }
                LineColumn::new0(line0, column0)
            }
        }
    }
}

UTF-16 ではない。 LSP ってそうだっけ……？

文字列の interning も (smol_str ではなく) salsa が提供します:

#[salsa::interned]
#[derive(Clone, Debug, PartialEq, Eq, Hash)]
pub struct Word {
    #[return_ref]
    pub string: String,
}

唯一の入力:

#[salsa::input]
pub struct InputFile {
    name: Word,
    #[return_ref]
    source_text: String,
    // ~~ブレイクポイントすら扱える！？~~ いやラインブレイクポイントじゃんね
    #[return_ref]
    breakpoint_locations: Vec<LineColumn>,
}

パース後の姿:

#[salsa::tracked]
pub struct SourceFile {
    #[id]
    input_file: InputFile,
    #[return_ref]
    items: Vec<Item>,
    main_fn: Option<Function>,
}

• TODO: なぜ Arena ではなく Vec<T> ?
  1 度 DB の中に入ったら参照しか触れないため実質 Arena 。
• Item を参照することは無い？
• Source map pattern は？
  AST を直接保持しているか、直前のパスに写し返すサブテーブルを持っている。 Span から対応のデータに写すマップは無いので動的に探すことになりそう。

dada-ids

InternTable は indexmap::IndexSet の wrapper で、 salsa::Id を経由して任意の newtype K をキーにしています。

#[derive(Clone, Debug, PartialEq, Eq)]
pub struct InternTable<K: salsa::AsId, V: Hash + Eq> {
    map: IndexSet<V>,
    phantom: PhantomData<K>,
}

AllocTable は arena です。こちらも salsa::Id を経由して任意の newtype K をキーにしています:

#[derive(Clone, Debug, PartialEq, Eq)]
pub struct AllocTable<K: salsa::AsId, V> {
    vec: IndexVec<salsa::Id, V>,
    phantom: PhantomData<K>,
}

AllocTable こと `arena を集めたテーブルがマクロで定義されます:

tables! {
    /// Tables that store the data for expr in the AST.
    /// You can use `tables[expr]` (etc) to access the data.
    #[derive(Clone, Debug, PartialEq, Eq)]
    pub struct Tables {
        local_variables: alloc LocalVariable => LocalVariableData,
        basic_blocks: alloc BasicBlock => BasicBlockData,
        statements: alloc Statement => StatementData,
        terminators: alloc Terminator => TerminatorData,
        exprs: alloc Expr => ExprData,
        places: alloc Place => PlaceData,
        target_places: alloc TargetPlace => TargetPlaceData,
    }
}

alloc の部分を intern に書き換えると、 InternTable にもできるようですが、実際に使っている例はコード中にありませんでした。

ID を定義するマクロもあります:

id!(pub struct LocalVariable);

テーブルは ID に対して Index, IndexMut を定義します。 ID は id.data(&table) の形でデータを取得できます。 ID は trait で抽象されています。 Newtype 万歳！

dada-ir (2): lex 用データ

dada-ir は lex, parse など後のステップで利用される salsa データ型を提供します。 rust-analyzer とは異なる構成ですね。『AST』という語も標準的な意味で使われていて、 salsa-2022 には新規参入者に易しくなるうとする意志を感じます。

dada::lex_file のエントリーポイントは lex_file です。 TokenTree を返します。 lex と言いつつ CST を作っている わけですね。そういうもんだっけ:

pub fn lex_file(db: &dyn crate::Db, input_file: InputFile) -> TokenTree {
    let source_text = input_file.source_text(db);
    lex_text(db, input_file, source_text, 0)
}

TokenTree 及び Token:

#[salsa::tracked]
pub struct TokenTree {
    input_file: InputFile,
    span: Span,
    #[return_ref]
    tokens: Vec<Token>,
}

#[derive(Copy, Clone, Debug, PartialEq, Eq, Hash)]
pub enum Token {
    /// "foo", could be keyword or an identifier
    Alphabetic(Word),

    /// 22_000
    Number(Word),

    /// A `,` -- this is lexed separately from an operator
    /// since it never combines with anything else.
    Comma,

    /// A single character from an operator like `+`
    Op(char),

    /// `(`, `)`, `[`, `]`, `{`, or `}`
    Delimiter(char),

    /// When we encounter an opening delimiter, all the contents up to (but not including)
    /// the closing delimiter are read into a Tree.
    Tree(token_tree::TokenTree),

    /// A alphabetic word that is "nuzzled" right up to a char/string
    /// literal, e.g. the `r` in `r"foo"`.
    Prefix(Word),

    /// A string literal like `"foo"` or `"foo {bar}"`
    FormatString(FormatString),

    /// Some whitespace (` `, `\n`, etc)
    Whitespace(char),

    /// Some unclassifiable, non-whitespace char
    Unknown(char),

    /// `# ...`, argument is the length (including `#`).
    /// Note that the newline that comes after a comment is
    /// considered a separate whitespace token.
    Comment(u32),
}

TokenTree は Span を記憶しています。 Token は span 長のみを記憶しています:

impl Token {
    pub fn span_len(self, db: &dyn Db) -> u32 {
        match self {
            Token::Tree(tree) => tree.span(db).len(),
            Token::Alphabetic(word) | Token::Number(word) | Token::Prefix(word) => {
                word.as_str(db).len().try_into().unwrap()
            }
            Token::FormatString(f) => f.len(db),
            Token::Delimiter(ch) | Token::Op(ch) | Token::Whitespace(ch) | Token::Unknown(ch) => {
                ch.len_utf8().try_into().unwrap()
            }
            Token::Comma => 1,
            Token::Comment(l) => l,
        }
    }
    // ~~~~
}

そのため TokenTree を経由すれば Span つき Token に昇格できます:

impl TokenTree {
    pub fn spanned_tokens(self, db: &dyn crate::Db) -> impl Iterator<Item = (Span, Token)> + '_ {
        let mut start = self.span(db).start;
        self.tokens(db).iter().map(move |token| {
            let len = token.span_len(db);
            let span = Span::from(start, start + len);
            start = start + len;
            (span, *token)
        })
    }
}

origin_tables! マクロが出てきます。 AST ID を span に写し帰します:

origin_table! {
    #[derive(Clone, Debug, Default, PartialEq, Eq, Hash)]
    pub struct Spans {
        expr_spans: Expr => Span,
        named_expr_spans: NamedExpr => Span,
        local_variable_decl_spans: LocalVariableDecl => LocalVariableDeclSpan,
    }
}

• span から該当の AST ノードを得るには？
  たぶん AST から動的に探す？
• AstIdMap に相当するなら rust-analyzer のように bdfs (typo ではない) で AST ID を作るべきは？
  dada はコードブロック内に item を持てないっぽいので bfs で十分です。また名前が #[id] になっているので順不同かも？

TreeData と Spans は両方同時に計算されます:

#[salsa::tracked]
pub struct Tree {
    #[return_ref]
    data: TreeData,
    #[return_ref]
    spans: Spans,
}

#[salsa::tracked] のおかげで、フィールド毎にメモ化されます。 Spans のみが変化する場合、 TreeData に依存した salsa 関数は再計算されないはずです。

dada-ir (3): syntax 及び bir

code::syntax では式を定義しています。

code::bir は関数 Body に相当します。

// 関数の AST + メタ情報
#[salsa::tracked]
pub struct Bir {
    input_file: InputFile,
    function_name: Word,
    syntax_tree: syntax::Tree,
    #[return_ref]
    data: BirData,
    #[return_ref]
    origins: Origins,
}

// 関数の AST
#[derive(Clone, Debug, PartialEq, Eq)]
pub struct BirData {
    pub tables: Tables,
    pub num_parameters: usize,
    pub start_basic_block: BasicBlock,
}

Place は便利な概念ですね。

#[derive(PartialEq, Eq, Clone, Hash, Debug)]
pub enum PlaceData {
    LocalVariable(LocalVariable),
    Function(Function),
    Class(Class),
    Intrinsic(Intrinsic),
    Dot(Place, Word),
}

bir にも式があります。式を syntax::Expr に戻すマップもあります。

tables! {
    /// Tables that store the data for expr in the AST.
    /// You can use `tables[expr]` (etc) to access the data.
    #[derive(Clone, Debug, PartialEq, Eq)]
    pub struct Tables {
        local_variables: alloc LocalVariable => LocalVariableData,
        basic_blocks: alloc BasicBlock => BasicBlockData,
        statements: alloc Statement => StatementData,
        terminators: alloc Terminator => TerminatorData,
        exprs: alloc Expr => ExprData,
        places: alloc Place => PlaceData,
        target_places: alloc TargetPlace => TargetPlaceData,
    }
}

この上に item レベルのデータが定義されています。変換の流れは:

• dada-validate: syntax::Tree → validated::Tree
• dada-brew: validated::Tree → bir::Bir

Bir は base IR と言いながら後はコンパイルするだけなほど準備できています。

dada ベースの toylisp 再構築

やるんだな……?!

base

dada から車輪を奪取します。とにかく今は道路に戻りたい。

base
├── jar.rs     # salsa 関数
├── lib.rs     # InputFile, Name, Jar, BaseDb
├── ln.rs      # LineTable
└── span.rs    # Span

syntax (lex, CST / AST)

rowan で作ったコードベースを流用しました。

• rowan を使っても良さそう？
  思えば rowan のような self-contained なテキストツリーを作る必要はありません。実際 dada では rowan が使われていません。しかし rowan と salsa-2022 の相性が悪いということもない気がしています。 rowan を使っても良さそうです。

• やはりrowan を ditch したい
  rowan を使うと Span や Name への変換が挟まるので、 dada 風のパーサを作りたいところです。

• 診断情報には salsa-2022 の accumulated を使うべき？
  一旦 Vec<T> で出力しました。積極的に使うメリットはあるのでしょうか。

ItemTree

ItemTree は廃止できそう です。

ra では ItemTree の生成時に Arena<T> で positional ID (idx<T>) を作ります。この ID は長く使用され、 i tem データの参照時には ID → Location → item_tree[loc] というような冗長なアクセスが必要でした。

しかし dada の Item は interning された名前を item の #[id] に しています。したがって tem データの参照は item.field(db) で済み、コンパクトな形に見えます。ソースとの対応データも保持しており、 AstIdMap も不要になりました。楽でいいな

• Interning された Word はリパース後どのように変化する？
  名前の hash 値のように扱えて item のリオーダーにも強い？　それとも実際は並び順の ID になっている？　ソースファイル毎に ID が変わる？
• Item, Proc

Body および BodySourceMap

dada_ir::code::syntax は ra と非常に似ています。 syntax::Tree { TreeData, Spans } の内、 Spans は後のパスで使用しませんから、大抵の変更では後のパスの再計算は不要です。しかし必要な時はレジーに span を返します。立派な source map pattern です。

TODO: dada は ra よりも body のパスが多く、通常のコンパイラに近い形になっています。

• Body, BodyData, BodyTables, BodySpans
• ExprScopeMap, ItemScope の移植
• Resolver の移植

9/6 時点で以降完了！

dada を読む (2): dada-parse

意外と rust-analyzer との差異点が好奇心に引っ掛かります。 lex は飛ばしましたが、 parse には立ち寄ってみます。

Jar

まずはアウトラインを確認します:

#[salsa::jar(db = Db)]
pub struct Jar(
    code_parser::parse_function_body,
    file_parser::parse_file,
    parameter_parser::parse_function_parameters,
    parameter_parser::parse_class_parameters,
);

• parse_file: ファイル → Item
• parse_function_body: Item → Body (もとい dada_ir::code::syntax::Tree)

file_parser

つまり item parse ですね。 parse_file は入力ファイルを Vec<Item> に変換します:

#[salsa::tracked(return_ref)]
#[allow(clippy::needless_lifetimes)]
pub fn parse_file(db: &dyn crate::Db, input_file: InputFile) -> SourceFile {
    let token_tree = dada_lex::lex_file(db, input_file);
    let mut parser = Parser::new(db, token_tree);
    parser.parse_source_file()
}

#[salsa::input]
pub struct InputFile {
    name: Word,
    #[return_ref]
    source_text: String,
    #[return_ref]
    breakpoint_locations: Vec<LineColumn>,
}

#[salsa::tracked]
pub struct SourceFile {
    #[id]
    input_file: InputFile,
    #[return_ref]
    items: Vec<Item>,
    main_fn: Option<Function>,
}

Item の中身を覗いてみると、 Body の中身まではパースしていないようです。 CST (TokenTree) で止まります:

#[derive(Copy, Clone, PartialEq, Eq, PartialOrd, Ord, Debug, Hash)]
pub enum Item {
    Function(Function),
    Class(Class),
}

#[salsa::tracked]
pub struct Class {
    #[id]
    name: SpannedWord,
    field_tokens: TokenTree,

    /// Overall span of the class (including any body)
    span: FileSpan,
}

#[salsa::tracked]
pub struct Function {
    #[id]
    name: SpannedWord,
    effect: Effect,
    effect_span: FileSpan,

    unparsed_code: Option<UnparsedCode>,

    span: FileSpan,
}

#[derive(Copy, Clone, PartialEq, Eq, Hash, Debug)]
pub struct UnparsedCode {
    pub parameter_tokens: TokenTree,
    pub body_tokens: TokenTree,
}

code_parser

つまり body parse ですね。 Item の body を掴んでパーサに渡します:

#[salsa::tracked(specify)]
pub fn parse_function_body(db: &dyn crate::Db, function: Function) -> Tree {
    if let Some(unparsed_code) = function.unparsed_code(db) {
        let body = unparsed_code.body_tokens;
        Parser::new(db, body).parse_code_body(function.parameters(db))
    } else {
        panic!(
            "cannot parse function `{:?}` which did not have unparsed code",
            function.debug(db)
        );
    }
}

• TODO: specified 関数は初見です。ドキュメントを見ても理解できないが……？
  普通に呼ぶこともできるし、手動でも生成できる #[salsa::tracked] 関数という意味のようです。そもそも tracked 関数を経由して値生成する意味があることを salsa の実装から理解する必要があるかもしれません。俺たちの戦いは (ry

dada を読む (3): dada-validate

syntax::Tree (Body) を validated::Tree に変換します。 validated::Tree って何だ？

Jar

まずはアウトラインを確認します:

#[salsa::jar(db = Db)]
pub struct Jar(validate::root_definitions, validate::validate_function);

僅か 2 関数！

Jar (瓶) というのは結構好みです。主要な API を明示的にまとめることで、『これさえ見れば良い』という安心感が生まれます。 Bevy の Plugin を思い出すモジュール感です。

root_definitions

#[salsa::tracked(return_ref)]
#[allow(clippy::needless_lifetimes)]
pub fn root_definitions(db: &dyn crate::Db, input_file: InputFile) -> name_lookup::RootDefinitions {
    name_lookup::RootDefinitions::new(db, input_file)
}

dada_validate::validate::name_lookup をみると……構造体は #[salsa::tracked] ではないようです。ただしこれを返す関数は #[salsa::tracked] です。フィールド毎に追跡する必要が無ければ構造体へのマークは不要ということかもしれません:

#[derive(Clone, Debug, PartialEq, Eq)]
pub struct RootDefinitions {
    names: Map<Word, Definition>,
}

RootDefinition は Definition の集まりです。ただし LocalVariable はありません (item + intinsic です) 。つまり ItemScope です。

Definition というのは Item の拡張ですね。まだ本領発揮していません:

#[derive(Clone, Copy, PartialEq, Eq, Hash, Debug)]
pub(crate) enum Definition {
    // Body の中では変数定義もできる
    LocalVariable(validated::LocalVariable),
    // Body は item を持てる
    Function(Function),
    Class(Class),
    // builtin ってこと
    Intrinsic(Intrinsic),
}

#[derive(Copy, Clone, PartialEq, Eq, Debug, Hash)]
pub enum Intrinsic {
    Print,
}

validate_function

パース済みの関数 Body こと syntax::Tree を謎のデータ型 validated::Tree に写します:

#[salsa::tracked]
#[tracing::instrument(level = "debug", skip(db))]
pub(crate) fn validate_function(db: &dyn crate::Db, function: Function) -> validated::Tree {
    let syntax_tree = function.syntax_tree(db);

外から見るとパーサの割り当てを吹っ飛ばして見えます。過程を吹き飛ばし、結果だけが残る……まさか、ボス？ rust-anaylzer もこういう API で良かったのかもしれない。

dada_ir の validated::Tree と syntax::Tree を比較すると、 syntax::ExprData の方にのみ Option<T> が使用されています。 validated::Tree を作るときには Option 型はエラー蓄積に写されます:

                    dada_ir::error!(
                        self.function.return_type(self.db).span(self.db),
                        "function body cannot be empty",
                    )
                    .primary_label("because function is supposed to return something")
                    .emit(self.db);

error! マクロはフォーマット文字列を作って DiagnosticsBuilder を返します。なるほどね。 DB にエラーを蓄積するのは Writer モナド感があります。

dada を読む (4): dada-brew

アウトライン

定番の Jar:

#[salsa::jar(db = Db)]
pub struct Jar(brew::brew);

関数 1 本です ！　validated::Tree を bir::Bir に写します:

#[salsa::tracked]
pub fn brew(db: &dyn crate::Db, validated_tree: validated::Tree) -> bir::Bir {

Base IR って何だ……

tables! {
    #[derive(Clone, Debug, PartialEq, Eq)]
    pub struct Tables {
        exprs: alloc Expr => ExprData,
        named_exprs: alloc NamedExpr => NamedExprData,
        local_variable_decls: alloc LocalVariableDecl => LocalVariableDeclData,
    }
}

tables! {
    #[derive(Clone, Debug, PartialEq, Eq)]
    pub struct Tables {
        exprs: alloc Expr => ExprData,
        named_exprs: alloc NamedExpr => NamedExprData,
        local_variables: alloc LocalVariable => LocalVariableData,
+        places: alloc Place => PlaceData,
+        target_places: alloc TargetPlace => TargetPlaceData,
    }
}

tables! {
    #[derive(Clone, Debug, PartialEq, Eq)]
    pub struct Tables {
        exprs: alloc Expr => ExprData,
-        named_exprs: alloc NamedExpr => NamedExprData,
        local_variables: alloc LocalVariable => LocalVariableData,
        places: alloc Place => PlaceData,
        target_places: alloc TargetPlace => TargetPlaceData,
+        basic_blocks: alloc BasicBlock => BasicBlockData,
+        statements: alloc Statement => StatementData,
+        terminators: alloc Terminator => TerminatorData,
    }
}

• 型情報は syntax 以降失われています (本当は解析すべきだけれど dada が未実装のため？)
• syntax, validated では ExprData の中に Return や Seq (コードブロック) が入っています。 bir ではそれらが BasicBlockData (コードブロック), StatementData (ブレイクポイントを含む), TerminatorData (Goto, If, Result など) に分かれています。

Lowering (?)

TODO

salsa の目立った更新をメモ

早速影響があったので、ここからはウォッチして行きたいと思います。

https://github.com/salsa-rs/salsa/issues/305

• Automatically derive DebugInDb for salsa structs
  Boilerplate 解消！

• add synthetic_write
  よく分からないけれど trait Database が変わりました。

• Make getters and setters have the visibility of their field
  #[salsa::tracked] フィールドへのアクセサに visibility を設定！

ra ブログ記事を読む

IDE 一般の話が載っており、筆者の経験 (JetBrains) が活きています。

https://rust-analyzer.github.io/blog

Find References (item)

予想

対象 item のを定義を見つけ、 item を import したファイルを列挙します。それらのファイルのすべての Body を計算し、対象 item を指す ExprId の span を返します。

ra 記事

grep で候補を得てから解析で絞り込みます。最適化としては trigram の index を保持する案が一般的なようです (2019 年当時の ra は未実装) 。

ra には SSR (structural search and replace) というクレートがあるのですが、単なる隠し機能ではなく、大いに活躍していることが窺えました。

Rename symbol

TODO

salsa-2022 に移行しました

スクラップも 3 本目に移行します。