Salsa の仕組み

この章は、Niko Matsakis による Salsa についてのこの動画での説明に基づいています。さらに詳しく知りたい場合は、同じく Niko Matsakis による Salsa In More Depth を見るとよいでしょう。

2022 年 11 月時点では、Salsa は rustc のクエリシステムに
（他のものとともに）触発されていますが、rustc で直接使われているわけではありません。 Rust のトレイトシステムの実装である chalk や、 Rust 向け Language Server Protocol の公式実装である rust-analyzer では広く使われていますが、コンパイラに統合するための中期的または長期的な具体的な計画はありません。

Salsa とは何か？

Salsa はインクリメンタルな再計算のためのライブラリです。これは、過去にすでに行われた計算を再利用することで、将来の計算の効率を高められることを意味します。

Salsa の目的は次のとおりです。

その機能を自動的な形で提供し、古い計算の再利用をライブラリによって自動的に行うこと。
それを「健全」または「正しい」方法で行い、その結果として最初から行った場合と同じ結果を導くこと。

Salsa の実際のモデルははるかに豊かで、多くの種類の入力と多くの異なる出力を扱えます。たとえば、Salsa を IDE と統合する場合、入力はマニフェスト（Cargo.toml、rust-toolchain.toml）、ソースファイル全体（foo.rs）、スニペットなどになり得ます。そのような統合の出力は、バイナリ実行可能ファイルから、lint、型（たとえば、ユーザーが特定の変数を選択してその型を見たい場合）、補完などまでさまざまです。

どのように機能するのか？

Salsa が最初に行う必要があるのは、計算されたものではなく入力として与えられる「基底入力」を識別することです。

次に Salsa は、中間的な「派生」値も識別する必要があります。これはライブラリが生成するものですが、各派生値について、その派生値を計算する「純粋」関数が存在します。

たとえば、ast(x: Path) -> AST という関数があるかもしれません。生成される抽象構文木（AST）は最終的な値ではなく、ライブラリが計算に使用する中間値です。

これは、ライブラリで計算しようとすると、Salsa がさまざまな派生値を計算し、最終的に入力を読み取り、求められた計算の結果を生成することを意味します。

計算の過程で、Salsa はどの入力がアクセスされ、どの値が派生されたかを追跡します。この情報は、入力が変更されたときに何が起こるか、つまり派生値がまだ有効かどうかを判断するために使われます。

これは必ずしも、入力の下流にある各計算がチェックされることを意味しません。それは高コストになり得ます。Salsa は、変更されていないものを見つけるまで、各下流の計算をチェックするだけで済みます。その時点で、他の派生計算は変更する必要がないため、チェックされません。

これは、ノードを持つグラフとして考えるとわかりやすいです。各派生値は他の値に依存しており、それらは基底値または派生値のいずれかです。基底値には依存関係がありません。

I <- A <- C ...
          |
J <- B <--+

入力 I が変化すると、派生値 A は変化する可能性があります。派生値 B は I、A、または A や I から派生したどの値にも依存していないため、変更の対象ではありません。したがって、Salsa は B について過去に行った計算を、再計算することなく再利用できます。

計算は早期に終了することもあります。前と同じグラフのまま、入力 I が何らかの形で変化した（そして入力 J は変化していない）とします。しかし、A を再度計算したところ、A が前回の計算から変化していないことが判明したとします。これは「早期終了」につながります。なぜなら、C の直接の入力である A と B の両方が変化していないため、C が変更される必要があるかどうかをチェックする必要がないからです。

Salsa の主要な概念

クエリ

クエリとは、Salsa が計算の過程でアクセスできる何らかの値です。各クエリは（0 個から多数までの）キーをいくつか持つことができ、すべてのクエリは関数と同様に結果を持ちます。0-key クエリは「入力」クエリと呼ばれます。

データベース

データベースは基本的に計算全体のコンテキストであり、Salsa の内部状態、各クエリのすべての中間値、そして計算に必要となるその他すべてのものを保存するためのものです。データベースは、構築される前にライブラリが行うすべてのクエリを知っている必要がありますが、それらを同じ場所で指定する必要はありません。

データベースが形成されると、関数によく似たクエリでアクセスできます。各クエリの結果はデータベースに保存されているため、クエリが N 回呼び出されると、（入力が再計算を正当化するような形で変更されていない限り）クエリを再計算することなく、 N 個の clone された 結果を返します。

各入力クエリ（0-key）については、「set」メソッドが生成され、ユーザーはそのようなクエリの出力を変更し、以前にメモ化された値が無効化される可能性を引き起こすことができます。

クエリグループ

クエリグループとは、1 つの単位としてまとめて定義されたクエリの集合です。データベースはクエリグループを組み合わせることで形成されます。クエリグループは「Salsa モジュール」に似ています。

クエリグループ内のクエリの集合は、トレイト内のメソッドの集合にすぎません。

クエリグループを作成するには、特定の属性（#[salsa::query_group(...)]）で注釈付けされたトレイトを作成する必要があります。

その属性には引数も指定しなければなりません。これは、後でデータベースが作成されるときに使用される struct を Salsa が作成するために使われます。

入力クエリグループの例:

/// この属性はこのツリーを処理し、このツリーを出力として生成し、Salsa も使用する
/// 中間的なものを大量に生成します。これらのうちの 1 つは
/// "StorageStruct" であり、その名前は属性で指定しています。
///
/// このクエリグループは、いかなる派生入力にも依存しない **入力** クエリの集まりです。
#[salsa::query_group(InputsStorage)]
pub trait Inputs {
    /// この属性（`#[salsa::input]`）は、このクエリが基底
    /// 入力であることを示すため、`set_manifest` が自動生成されます
    #[salsa::input]
    fn manifest(&self) -> Manifest;

    #[salsa::input]
    fn source_text(&self, name: String) -> String;
}

派生クエリグループを作成するには、次の例に示すように、このクエリグループがどの他のクエリグループに依存するかを、それらをスーパートレイトとして指定することで指定しなければなりません。

/// このクエリグループには、派生値に依存するクエリが含まれます。
/// クエリグループは、依存関係をスーパートレイトとして指定することで、別の
/// クエリグループのクエリにアクセスできます。クエリグループは、このパターンを使って
/// 必要なだけ積み重ねることができます。
#[salsa::query_group(ParserStorage)]
pub trait Parser: Inputs {
    /// このクエリ `ast` は入力クエリではなく、派生クエリです。これは
    /// 定義が必要であることを意味します。
    fn ast(&self, name: String) -> String;
}

派生クエリを作成する場合、そのクエリの実装は trait の外部で定義する必要があります。定義は、その他のキーに加えて、定義が属するクエリグループである trait を impl Trait（または dyn Trait）としてデータベースパラメーターに取る必要があります。

/// これは `Parser` trait における `ast` クエリの定義になります。
/// そのため、クエリ `ast` が呼び出され、再計算が必要になった場合、Salsa は
/// この関数を呼び出し、データベースを `impl Parser` として渡します。
/// この関数は、すべてのクエリグループのすべてのクエリを認識する必要はありません
fn ast(db: &impl Parser, name: String) -> String {
    //! なお、ここでは `impl Parser` が使用されていますが、`dyn Parser` でも同様に動作します
    /* code */
    ///`impl Parser` を渡すことで、これは許可されます
    let source_text = db.input_file(name);
    /* 実際のパースを行う */
    return ast;
}

最終的に、すべてのクエリグループが定義された後、struct を宣言することでデータベースを作成できます。

どのクエリグループをデータベースの一部にするかを指定するには、attribute （#[salsa::database(...)]）を追加する必要があります。その attribute の引数は、クエリグループの storages を指定する identifiers のリストです。

///この属性は、どのクエリグループをデータベースに含めるかを指定します
#[salsa::database(InputsStorage, ParserStorage)]
#[derive(Default)] //任意！
struct MyDatabase {
    ///このフィールドも 1 つ必要です
    runtime : salsa::Runtime<MyDatabase>,
}
///そして、この trait を実装する必要があります
impl salsa::Database for MyDatabase {
    fn salsa_runtime(&self) -> &salsa::Runtime<MyDatabase> {
        &self.runtime
    }
}

使用例:

fn main() {
    let db = MyDatabase::default();
    db.set_manifest(...);
    db.set_source_text(...);
    loop {
        db.ast(...); //結果を再利用します
        db.set_source_text(...);
    }
}

Keyboard shortcuts