Rustコアコミッターが解説する言語の最新情報 〜Rustの新しいTraitソルバをのぞいてみる〜

「効率的で信頼できるソフトウェアを誰もが作れる言語」を提唱するプログラミング言語 Rust。その優れたパフォーマンスやプログラムとしての信頼性・生産性の高さなどから、近年非常に人気を集めています。そんなRustでは、いったいどのような新機能が登場しているでしょうか。今回はコアコミッターである前田喬之さんに、最近Rustに実装された新しいTraitソルバについて寄稿していただきました。

はじめに

前田喬之といいます。SNSはTaKO8Kiというハンドルネームでやっていて、Rustのコミッターをしています。コンパイラのコントリビューターチームや、エラー周りの機構を実装するワーキンググループに所属しています。

Rustの新しいTraitソルバ

RustにはTraitがありますが、Trait解決をするために裏側ではTraitソルバが動いています。この記事では、Traitソルバがどういうものか簡単に説明し、新しいTraitソルバを見ていきたいと思います。

Traitソルバとは

まず、Traitソルバとは何かというと、Traitの解決を行うための機構です。Trait解決とは、例えば以下のようなコードがあったときに、どのTraitを使うかを決定することです。

Traitソルバは、Traitの解決を行うための機構で、Trait解決とは、Traitを使うためのimplを見つけることです。以下の例を見てみましょう。clone_sliceを下記のように実行しようとしているとします。

fn clone_slice<T: Clone>(x: &[T]) -> Vec<T> {

    let mut v = Vec::new();

    for e in &x {

        v.push((*e).clone()); // これはTがCloneを実装していないと動かない

    }

}

let v: Vec<isize> = clone_slice(&[1, 2, 3])

上記のコメントに書いている通りで、TはCloneを実装している必要があります。例えばこの呼び出し側の例では、isize : Cloneを満たすimplが実装されていなければならないということです。rustcでは、このようにあるimplを必要とするようなTraitの参照をobligation（日本語なら義務などが一番しっくりくる訳かなと思います）と呼び、Traitソルバはこれを解決し、適切なimplが存在することを証明します。

ここまでの説明でざっくりとTraitソルバが何かがつかめたのではないかなと思います。次にもう少しだけ掘り下げてみましょう。現行のTraitソルバはSelection, Fulfillment, Evaluationの主に3つの部分から構成されています。

Selectionがおそらく一番わかりやすくて、特定のobligationを解決する方法を決定することを指しています。

Fulfillmentは、obligationが完全に満たされたということをトラッキングするものです。例えばFulfillment用のContext structであるFulfillmentContextはこのリンクにあります。

Evaluationは、obligationが選択できるかもしくは特定の型に対してimplを適用することができるかを確認します。コードでいうと、InferCtxt::evaluate_obligation、SelectionContext::evaluate_root_obligationなどが該当します。

続いて本題の新しいTraitソルバについて見ていきましょう。新しいTraitソルバは、コードでいうとcompiler/rustc_trait_selection/src/solve.rsにあり、コアな実装は、rustc_next_trait_solverというcrateに含まれています。余談ですが、Traitソルバには今まで言及した古いソルバ、新しいソルバの他にもChalkソルバというものもあります。

まず気になるのはそもそもなぜ新しいTraitソルバが必要なのかということですが、これは新しいTraitソルバがよりシンプルで、よりパフォーマンスが良くて、より正確であるためです。

新しいTraitソルバは、文字通り別のcrateとして実装されており、使われている用語も古いものとはそれなりに異なっているため、まずはそれらを整理していきましょう。

例を挙げてみましょう。以下のような関数を定義したとします。先ほど挙げたコードとは異なり、引数としてVectorを受け取り、そのVectorをcloneして返す関数です。

fn clone_vec<T: Clone>(x: Vec<T>) -> Vec<T> {

    x.clone()

}

先ほど説明した内容を前提にすると、この関数の呼び出し側では、Vec<T>: Cloneが満たされているかどうかをチェックする必要があります。このような、T: Cloneが満たされているという前提のもとで、Vec<T>: Cloneが満たされているかどうかをチェックするという概念をGoalと呼びます。そして、Vec<T>: CloneやT: CloneなどのTraitソルバが証明するものをPredicateと呼びます。新しいTraitソルバでは新たにGoalという用語を使っています。

では具体的に新しいTraitソルバは古いTraitソルバとどこが異なり、それによって何がうれしいのかについて見ていきましょう。次では興味深いものをいくつかピックアップして説明します。

新しいTraitソルバの特徴

Canonicalization

まず新しいTraitソルバでは、Canonicalizationが用いられています。これは、例えば、u32: Trait<?x>およびu32: Trait<?y>といったGoalがあり、ここで?xと?yは現在特に制約のない異なる推論変数であるとします。この場合は、両方のGoalは同じ結果にならなければなりません。こういった際に1つの正規化されたクエリを証明して、それを使って2つのGoalの結果を得られるというのが、Canonicalizationでできることです。

Canonicalizationを使うと、上記で述べたFulfillment, Evaluationの2ステップを1つのステップにまとめることができます。これによって、より実装をシンプルにしたり、キャッシュをより簡略化したりすることができ、意図せずトラッキングされていない情報を参照してしまうことがなくなります。

古いTraitソルバでは、Candidateの制約をstashするのにCanonicalizationを使っていないので、Selectionの際には制約を捨てなければならず、その後Candidateを再評価することで制約を適用する必要があります。実際にソースをのぞいてみると、下記のようにSelectionの後に再度評価しているのがわかります。

// Selection

 match self.candidate_from_obligation(stack) {

    // Reevaluation

    Ok(Some(c)) => self.evaluate_candidate(stack, &c),

    Ok(None) => Ok(EvaluatedToAmbig),

    Err(Overflow(OverflowError::Canonical)) => Err(OverflowError::Canonical),

    Err(..) => Ok(EvaluatedToErr),

}

また、Goalを評価して得られる推論制約をキャッシュすることもできず、EvaluationとFulfillmentという2つのステップを行うことを必要とするのはそれが原因です。

ただし、Canonicalizationを使う際は、fixed-point iteration（不動点反復）を用いる必要があります。古い実装でも同様のことはFulfillmentで行っていましたが、Evaluationでは行っていませんでした。常にそのようにすることでより推論が強化され、Traitソルバの順序依存性が軽減されます。

実装としては、設定したfixed-point iterationを実行するステップの限界値FIXPOINT_STEP_LIMITまでGoalの評価をくり返し、n+1回目の評価がn回目の評価と同じ結果になった場合に終了するようになっています。

具体的には、evaluate_added_goals_stepという関数の中でunchanged_certaintyという変数を用いて、Goalが証明可能かを管理しています。

 fn evaluate_added_goals_step(&mut self) -> Result<Option<Certainty>, NoSolution> {

        let cx = self.cx();

        let mut goals = core::mem::take(&mut self.nested_goals);

        // If this loop did not result in any progress, what's our final certainty.

        let mut unchanged_certainty = Some(Certainty::Yes);

        // ...

         Ok(unchanged_certainty)

 }

上記の関数は、以下のようにtry_evaluate_added_goalsという関数で呼び出されています。この関数は、FIXPOINT_STEP_LIMITまで評価をくり返すか、Goalを評価した結果がひとつ前のステップと同じ結果になった場合もしくは、評価に失敗した場合に終了します。

  pub(super) fn try_evaluate_added_goals(&mut self) -> Result<Certainty, NoSolution> {

    let mut response = Ok(Certainty::overflow(false));

    for _ in 0..FIXPOINT_STEP_LIMIT {

        match self.evaluate_added_goals_step() {

            Ok(Some(cert)) => {

                response = Ok(cert);

                break;

            }

            Ok(None) => {}

            Err(NoSolution) => {

                response = Err(NoSolution);

                break;

            }

        }

    }

    if response.is_err() {

        self.tainted = Err(NoSolution);

    }

    response

}

以上のようにして新しいTraitソルバでは、ネストしたGoalの評価の際に不動点反復が用いられています。

ref:

• https://github.com/rust-lang/rust/blob/c926476d013fbb2ca43bd5259d0a7228009a9cb2/compiler/rustc_next_trait_solver/src/solve/eval_ctxt/mod.rs#L502
• https://github.com/rust-lang/rust/blob/c926476d013fbb2ca43bd5259d0a7228009a9cb2/compiler/rustc_type_ir/src/search_graph/mod.rs#L925
• https://github.com/rust-lang/rust/blob/c926476d013fbb2ca43bd5259d0a7228009a9cb2/compiler/rustc_next_trait_solver/src/solve/eval_ctxt/mod.rs#L533
• https://github.com/rust-lang/rust/blob/c926476d013fbb2ca43bd5259d0a7228009a9cb2/compiler/rustc_type_ir/src/solve/mod.rs#L283

エラー機構のパフォーマンス改善

Rustコンパイラは、より良いエラーメッセージを出力するように開発されています。Traitソルバとして、これを実現するために古い実装では、エラーのもとになる情報を直接トラッキングしていました。新しい実装ではその代わりに、ProofTreeを使うことで、関連する情報を遅延計算できるようになっています。これはまだ実装中ですが、完成すると、パフォーマンスの改善や意図せずエラー元の情報に依存した実装になってしまうことを防げるようになります。

具体的にはProofTreeを使う際は、ProofTreeVisitorというTraitを実装する必要があります。

pub trait ProofTreeVisitor<'tcx> {

    type Result: VisitorResult = ();

    fn span(&self) -> Span;

    fn config(&self) -> InspectConfig {

        InspectConfig { max_depth: 10 }

    }

    fn visit_goal(&mut self, goal: &InspectGoal<'_, 'tcx>) -> Self::Result;

}

例えば、AmbiguityCausesVisitorやBestObligationはProofTreeVisitorを実装しているStructの例です。

visit_goalで具体的にある特定のGoalを証明する際の情報を得ることができます。以下のように、Goalを起点にそのCandidateやそのGoalが証明できたかどうかなど取得することができます。

impl<'a, 'tcx> ProofTreeVisitor<'tcx> for AmbiguityCausesVisitor<'a, 'tcx> {

    fn span(&self) -> Span {

        DUMMY_SP

    }

    fn visit_goal(&mut self, goal: &InspectGoal<'_, 'tcx>) {

        let infcx = goal.infcx();

        for cand in goal.candidates() {

            cand.visit_nested_in_probe(self);

        }

        // When searching for intercrate ambiguity causes, we only need to look

        // at ambiguous goals, as for others the coherence unknowable candidate

        // was irrelevant.

        match goal.result() {

            Ok(Certainty::Maybe(_)) => {}

            Ok(Certainty::Yes) | Err(NoSolution) => return,

        }

        // 省略

    }

}

まとめ

新しいTraitソルバは、基本的には複雑になり過ぎていた古い実装のキャッシュやエラー情報の保持の仕方を簡略化したり、新しいプロセスを導入することで既存のTrait解決のステップをまとめたりすることを目的として開発されているようです。

ソースを見るとCanonicalizationは一通り実装が出来上がっていそうですが、例えば、上記で挙げたエラー情報の保持の仕方を改善することに関してはまだhackyな実装になってしまっている部分があるため、今後の動向に注目です。

そういった動向は、基本的にhttps://github.com/rust-lang/trait-system-refactor-initiativeというリポジトリでinitiative-trait-system-refactorというチームによって管理されています。少しのぞいてみると先ほど述べたfixpointに関連するissue #102が立っているので、興味がある方は見てみるのもよいかもしれません。