LoginSignup
16
5

More than 3 years have passed since last update.

@0yoyoyo

本家Rustコンパイラのソースを読もうとしてみる（6）

Last updated at Posted at 2020-11-19

前回までのあらすじ

Rustの本家コンパイラをGuide to Rustc Developmentに沿って読んでいく。前回に引き続き難しい部分なので、あまり深追いせずに見ていく。理論的な知識をもっと補強しなければと痛感しました。

目次（初回）

Analysis

前回は型チェックの処理を見たので、今回はそれ以外の部分を見ていこう。

トレイト解決

概要

トレイト解決の目的は、ある型に求められている実装を見つけ出すことである。ガイドの例になるが、

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

このような関数が与えられ、

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

このように呼び出されていたとする。このとき、isizeにCloneが実装されているのか調べる作業になる。

トレイト解決においては、Obligationという用語が頻出する。これは、トレイト解決が必要であるとのマークのようなもので、このObligationを解決していくのが中心的な処理となっている。

Obligationの管理

ObligationForestというデータ構造がある。上述したObligationを管理するためのデータ構造と考えていいだろう。内部の詳細には立ち入らないが、以下の2つの操作を意識しておく。

  1. Add a new root obligations (register_obligation).
  2. Process the pending obligations (process_obligations).

つまりは、解決しなければならないObligationを集める操作と、解決されていないObligationを処理する操作だ。

Obligationの解決

Obligationを解決するための処理は、大きく3つのパートに分かれているようだ。

  • Selection: Obligationがどのように解決されるか決定する。
  • Fulfillment: 全てのObligationが解決されているか追跡する。
  • Coherence: 複数の実装が重複していないか検査する。

ただ、FulfillmentとCoherenceについてはガイドにも説明がほとんどなく、どこの処理を指しているのか確証が持てないというのが正直なところだ。あくまで参考情報だが、Coherenceはrustc_typeck::coherenceモジュールあたりで、FulfillmentはSelectionとの境界が曖昧な感じがしている。このような理由もあり、Selectionについてのみもう少し見ていこう。

Selection

Selectionの処理は、前回読んだ型チェック処理のtypeck_with_fallback()の途中で呼ばれるselect_obligations_where_possible()から始まっているようだ。

ちなみに、SelectionはObligationを解決する処理であるため、必然的にObligationを集める作業（ObligationForestの処理1）はその前に完了しているはずである。おそらくではあるが、型チェックの中で実施していると思う。

rustc_typeck/src/check/fn_ctxt/_impl.rs
impl<'a, 'tcx> FnCtxt<'a, 'tcx> {
...
    /// Select as many obligations as we can at present.
    pub(in super::super) fn select_obligations_where_possible(
        &self,
        fallback_has_occurred: bool,
        mutate_fullfillment_errors: impl Fn(&mut Vec<traits::FulfillmentError<'tcx>>),
    ) {
        let result = self.fulfillment_cx.borrow_mut().select_where_possible(self);
        if let Err(mut errors) = result {
            mutate_fullfillment_errors(&mut errors);
            self.report_fulfillment_errors(&errors, self.inh.body_id, fallback_has_occurred);
        }
    }
...
}

select_where_possible()からFulfillmentContextのselect()と続いていく。ここで、ObligationForestの処理2であるprocess_obligations()が呼ばれ、個々のObligationを確かめていく処理に進んでいく。

rustc_trait_selection/src/traits/fulfill.rs
impl<'a, 'tcx> FulfillmentContext<'tcx> {
...
    /// Attempts to select obligations using `selcx`.
    fn select(
        &mut self,
        selcx: &mut SelectionContext<'a, 'tcx>,
    ) -> Result<(), Vec<FulfillmentError<'tcx>>> {
...
        loop {
            debug!("select: starting another iteration");

            // Process pending obligations.
            let outcome: Outcome<_, _> =
                self.predicates.process_obligations(&mut FulfillProcessor {
                    selcx,
                    register_region_obligations: self.register_region_obligations,
                });
            debug!("select: outcome={:#?}", outcome);
...
            // If nothing new was added, no need to keep looping.
            if outcome.stalled {
                break;
            }
        }
...
    }
...
}

処理を追っていくと、SelectionContextのselect()に行き着く。ガイドにも書いてある通り、このメソッドがSelectionのメインのインターフェースとなる。

rustc_trait_selection/src/traits/select/mod.rs
impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
...
    /// Attempts to satisfy the obligation. If successful, this will affect the surrounding
    /// type environment by performing unification.
    #[instrument(level = "debug", skip(self))]
    pub fn select(
        &mut self,
        obligation: &TraitObligation<'tcx>,
    ) -> SelectionResult<'tcx, Selection<'tcx>> {
        debug_assert!(!obligation.predicate.has_escaping_bound_vars());

        let pec = &ProvisionalEvaluationCache::default();
        let stack = self.push_stack(TraitObligationStackList::empty(pec), obligation);

        let candidate = match self.candidate_from_obligation(&stack) {
            Err(SelectionError::Overflow) => {
                // In standard mode, overflow must have been caught and reported
                // earlier.
                assert!(self.query_mode == TraitQueryMode::Canonical);
                return Err(SelectionError::Overflow);
            }
            Err(e) => {
                return Err(e);
            }
            Ok(None) => {
                return Ok(None);
            }
            Ok(Some(candidate)) => candidate,
        };

        match self.confirm_candidate(obligation, candidate) {
            Err(SelectionError::Overflow) => {
                assert!(self.query_mode == TraitQueryMode::Canonical);
                Err(SelectionError::Overflow)
            }
            Err(e) => Err(e),
            Ok(candidate) => {
                debug!(?candidate);
                Ok(Some(candidate))
            }
        }
    }

これ以降は深追いしないが、まずはcandidate_from_obligation()から始まる処理でObligationを解決する候補（candidate）を集めていく。ソースの転記はしていないがassemble_candidates()から分岐する処理において候補を集めているような処理が見られる。候補が複数見つかってしまった場合は絞り込みを行うなどする。候補が確定できたらconfirm_candidate()から始まる処理で見つかった実装がソース上の型を満たすのか確認を実施する。確認処理でも問題がなければ、無事にObligationが解決することとなる。

Chalk

トレイト解決の機構は今後刷新される予定となっている。新たな機構はChalkと呼ばれ、現在設計・実装中のようだ。ChalkはPrologという非手続き型で論理型なプログラミング言語の仕組みに基づいているとのこと。（うん、分からん。）

ChalkについてはChalk bookという結構たっぷりめの専用リファレンスもあるようなので、興味がある人は読んでみるのもいいかもしれない。

借用チェック

借用チェックはMIRに対して行われ、レキシカルなスコープに基づかないNLL（Non-Lexical Lifetimes）が使われる。処理の入り口はmir_borrowck()だ。

rustc_mir/src/borrow_check/mod.rs
fn mir_borrowck<'tcx>(
    tcx: TyCtxt<'tcx>,
    def: ty::WithOptConstParam<LocalDefId>,
) -> &'tcx BorrowCheckResult<'tcx> {
    let (input_body, promoted) = tcx.mir_promoted(def);
    debug!("run query mir_borrowck: {}", tcx.def_path_str(def.did.to_def_id()));

    let opt_closure_req = tcx.infer_ctxt().enter(|infcx| {
        let input_body: &Body<'_> = &input_body.borrow();
        let promoted: &IndexVec<_, _> = &promoted.borrow();
        do_mir_borrowck(&infcx, input_body, promoted)
    });
    debug!("mir_borrowck done");

    tcx.arena.alloc(opt_closure_req)
}

mir_borrowck()は本当に入り口のような感じで、そこから呼ばれるdo_mir_borrowck()に多くの処理が記述されている。

まず、replace_regions_in_mir()において、全てのリージョン（＝ライフタイム）に対してinference variableを与える。inference variableとは、型やライフタイムを推論する場合に与える変数であり、型推論では型変数と呼んでいたものだ。ライフタイムの推論に限定した呼び方はないようだが、少し無理やり呼ぶとしたらリージョン変数みたいな感じだろうか。一応ソース内のコメントではそのような呼び方も一部使われているようなので、この記事ではリージョン変数と呼ぶことにする。

借用チェックの主な仕事は、このリージョン変数に対して具体的な値を決定すること（リージョンの推論）と言えるだろう。それを行うのがcompute_regions()だ。

rustc_mir/src/borrow_check/mod.rs
fn do_mir_borrowck<'a, 'tcx>(
    infcx: &InferCtxt<'a, 'tcx>,
    input_body: &Body<'tcx>,
    input_promoted: &IndexVec<Promoted, Body<'tcx>>,
) -> BorrowCheckResult<'tcx> {
...
    // Replace all regions with fresh inference variables. This
    // requires first making our own copy of the MIR. This copy will
    // be modified (in place) to contain non-lexical lifetimes. It
    // will have a lifetime tied to the inference context.
    let mut body = input_body.clone();
    let mut promoted = input_promoted.clone();
    let free_regions = nll::replace_regions_in_mir(infcx, param_env, &mut body, &mut promoted);
    let body = &body; // no further changes
...
    // Compute non-lexical lifetimes.
    let nll::NllOutput {
        regioncx,
        opaque_type_values,
        polonius_output,
        opt_closure_req,
        nll_errors,
    } = nll::compute_regions(
        infcx,
        free_regions,
        body,
        &promoted,
        location_table,
        param_env,
        &mut flow_inits,
        &mdpe.move_data,
        &borrow_set,
        &upvars,
    );
...
}

リージョンの推論にはまず、推論のための材料となる制約（Constraint）を収集する。compute_regions()で呼ばれるtype_check()やgenerate_constraints()などがその役割を持つ。ここでのtype_check()は、型の整合性を検査するための処理ではなく、あくまで制約を集めるために行われる。（型の整合性は前回見たようにHIRに対する検査で確認される。）

制約とは例えば、ライフタイム'aはライフタイム'bより長生きするとか、ある時点でどの変数が生存しているか、などの情報である。こういった制約を洗い出し、それらを材料にsolve()で解決を行う。

/// Computes the (non-lexical) regions from the input MIR.
///
/// This may result in errors being reported.
pub(in crate::borrow_check) fn compute_regions<'cx, 'tcx>(
    infcx: &InferCtxt<'cx, 'tcx>,
    universal_regions: UniversalRegions<'tcx>,
    body: &Body<'tcx>,
    promoted: &IndexVec<Promoted, Body<'tcx>>,
    location_table: &LocationTable,
    param_env: ty::ParamEnv<'tcx>,
    flow_inits: &mut ResultsCursor<'cx, 'tcx, MaybeInitializedPlaces<'cx, 'tcx>>,
    move_data: &MoveData<'tcx>,
    borrow_set: &BorrowSet<'tcx>,
    upvars: &[Upvar],
) -> NllOutput<'tcx> {
...
    // Run the MIR type-checker.
    let MirTypeckResults { constraints, universal_region_relations, opaque_type_values } =
        type_check::type_check(
            infcx,
            param_env,
            body,
            promoted,
            &universal_regions,
            location_table,
            borrow_set,
            &mut all_facts,
            flow_inits,
            move_data,
            elements,
            upvars,
        );
...
    constraint_generation::generate_constraints(
        infcx,
        &mut liveness_constraints,
        &mut all_facts,
        location_table,
        &body,
        borrow_set,
    );
...
    // Solve the region constraints.
    let (closure_region_requirements, nll_errors) =
        regioncx.solve(infcx, &body, polonius_output.clone());
...
    NllOutput {
        regioncx,
        opaque_type_values: remapped_opaque_tys,
        polonius_output,
        opt_closure_req: closure_region_requirements,
        nll_errors,
    }
}

推論により全てのリージョン変数を解決し、もし不整合があればエラーを出力する。エラーがなければ借用チェックは無事完了となる。

つづく

ここまででRustの型システムに関する章は終わりとなる。型システムは調べれば調べるだけ深くキリがないため（だからこそ面白いのだが）、今回は表面をなでるだけになってしまったかもしれない。次回は最後の章である、MIRから実行バイナリを生成するところを見ていく。

16
5
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
16
5