Salsaを使ってインクリメンタルコンパイラを爆速で作る

言語実装 Advent Calendar 2022の8日目の記事です。

本記事ではRustのライブラリであるsalsaを使ってDesk言語のインクリメンタルコンパイラを作った話をします。

salsaは、rustcのアーキテクチャなどを参考にした、インクリメンタルかつオンデマンドな計算のためのcrateで、rust-analyzerで使われてるやつですね。

全体のコード

突然ですが、以下が開発したインクリメンタルコンパイラの実装になります。

#[salsa::query_group(CardStorage)]
pub trait CardQueries {
    #[salsa::input]
    fn code(&self, card_id: CardId) -> Code;
    fn ast(&self, id: CardId) -> QueryResult<WithSpan<ast::expr::Expr>>;
    fn hir(&self, id: CardId) -> QueryResult<HirResult>;
    fn typeinfer(&self, id: CardId) -> QueryResult<typeinfer::ctx::Ctx>;
    fn thir(&self, id: CardId) -> QueryResult<TypedHir>;
    fn mir(&self, id: CardId) -> QueryResult<Mir>;
}

#[salsa::database(CardStorage)]
#[derive(Default)]
pub struct CardsCompiler {
    storage: salsa::Storage<Self>,
}

impl salsa::Database for CardsCompiler {}

fn ast(db: &dyn CardQueries, id: CardId) -> QueryResult<WithSpan<ast::expr::Expr>> {
    let code = db.code(id);
    match code {
        Code::SourceCode { syntax, source } => {
            let ast = parse_source_code(&syntax, &source)?;
            Ok(Arc::new(ast))
        }
        Code::Ast(ast) => Ok(ast),
    }
}

fn hir(db: &dyn CardQueries, id: CardId) -> QueryResult<HirResult> {
    let ast = db.ast(id)?;
    let (genhir, hir) = hirgen::gen_hir(&ast)?;
    Ok(Arc::new(HirResult {
        hir,
        next_id: genhir.next_id(),
    }))
}

fn typeinfer(db: &dyn CardQueries, id: CardId) -> QueryResult<typeinfer::ctx::Ctx> {
    let hir_result = db.hir(id)?;
    let (ctx, _ty) = typeinfer::synth(hir_result.next_id, &hir_result.hir)?;
    Ok(Arc::new(ctx))
}

fn thir(db: &dyn CardQueries, id: CardId) -> QueryResult<TypedHir> {
    let hir_result = db.hir(id.clone())?;
    let ctx = db.typeinfer(id)?;
    let thir = thirgen::gen_typed_hir(ctx.next_id(), ctx.get_types(), &hir_result.hir);
    Ok(Arc::new(thir))
}

fn mir(db: &dyn CardQueries, id: CardId) -> QueryResult<Mir> {
    let thir = db.thir(id)?;
    let mir = mirgen::gen_mir(&thir)?;
    Ok(Arc::new(mir))
}

どうでしょうか？なんとなく読めたと思います。

正直、salsaを使ったコードは個人的には読みづらくて好きではありませんが、実は現在進行形でそれが修正されているようです。今年中に全てが良くなるみたいです。
しかし、今のままでもなんとか読めるものではあると思います。

コンパイラパスの列挙

#[salsa::query_group(CardStorage)]
pub trait CardQueries {
    #[salsa::input]
    fn code(&self, card_id: CardId) -> Code;
    fn ast(&self, id: CardId) -> QueryResult<WithSpan<ast::expr::Expr>>;
    fn hir(&self, id: CardId) -> QueryResult<HirResult>;
    fn typeinfer(&self, id: CardId) -> QueryResult<typeinfer::ctx::Ctx>;
    fn thir(&self, id: CardId) -> QueryResult<TypedHir>;
    fn mir(&self, id: CardId) -> QueryResult<Mir>;
}

ここでコンパイラのパスを列挙しています。

#[salsa::input]のついているcodeはコンパイラの入力です。

cards.set_code(card_id, code)でコンパイラに入力を与えることができます。 cardなのは、Desk言語では一つのまとまりをカードと呼ぶためです（他の言語だと関数に相当します）。

Codeは以下のように定義されています。

pub enum Code {
    SourceCode {
        syntax: SyntaxKind,
        source: Arc<String>,
    },
    Ast(Arc<WithSpan<Expr>>),
}

つまり、コンパイラの入力としてソースコードの場合とASTの場合があるわけです。ASTが入力？と思われるかも知れませんが、ビジュアルプログラミングエディタを使った場合はASTが入力になります。

QueryResultはanyhow::Resultのようなものですが、違いとして、Eqを実装しています。これはsalsaが変更の検出のために関数の出力にEqを求めるためです。また結果をArcで囲ってクローンを安価にしています。これはコンパイルが必要ない時に一度計算したコンパイル結果を何回も返すためです。

ast関数の実装

下半分のコードでは各コンパイラパスの実装がされています。

ast関数はパーサです。dbから入力のソースコードを受け取り、パースしています。その際、入力がASTの場合はパースをスキップしてそのまま返しています。

その他関数の実装

ast以下の関数では以下の実装を行なっています。

• hir: AST -> HIR (High-level IR) の変換
• typeinfer: HIRに対しての型推論
• thir: HIR -> THIR (Typed HIR)の変換
• mir: THIR -> MIR (Mid-level IR) の変換

MIRがコンパイラの最終出力になります。

実際の動作

まずcards.set_code(card_id, code)で入力を与えます。

そのあとcards.hir(card_id)やcards.mir(card_id)などと実行することで、その出力に必要なすべてのパスを計算して結果を返してくれます。

再度cards.mir(card_id)とすると入力が変わっていないので何もコンパイルが行われずに前回の結果がクローンされて返されます。

また、入力が変わっても必ず全てが再度コンパイルされるわけではなく、例えばフォーマッタをかけてソースコードを整形するだけではASTは変わらないはずなのでAST以降のコンパイルは行われません。

おわりに

いかがでしたか？

salsaを使えば簡単にインクリメンタルコンパイラを実装することができることがわかったと思います。