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

前回までのあらすじ

Rustの本家コンパイラをGuide to Rustc Developmentに沿って読んでいく。今回はRustの型システムに踏み込んでいくが、基礎が足りなすぎて泣きそうになった。あまり深い説明はできないと思うし、相変わらず網羅性はないです。

目次（初回）

Analysis

この章ではRustのコンパイラがもつ様々なチェック機構を見ていく。型推論や借用チェックなど、主にRustの型システムとして認識されているもので、これらはひとつの大きなパスで行われるのではなく、様々なパートに散りばめられている。

型チェック

型チェックではソースコード内の式に対する型を、場合によっては型推論も使いながら、決定していく。処理は主にrustc_typeckクレートで行われ、特にその中のcheckモジュールが型チェックの中心的な位置づけになる。

事前準備

漠然の処理を追っていくのはつらいので、ターゲットとなるソースコードをイメージしておく。ここでは最大限単純化して、このような関数を考えてみる。

fn main() {    
    let _a = 42_i32;    
}  

型推論も何もないような内容だが、これでも_aには型の指定が付いていないため、初期化する42_i32の型i32が型推論により決定されるはずだ。

また、内部的に上記のコードがどのように保持されているか確認しておくとソースも読みやすくなるかもしれない。型チェックはHIRの生成後に行われるため、以下のコマンド出力にあるbodiesを見るといいだろう。

$ rustc +nightly main.rs -Z unpretty=hir-tree

型チェックの入り口

型チェック処理はtypeck::check_crate()から始まる。この関数内には型チェックに関連する様々な処理が並んでいるが、ここでは関数内で使われる変数の型に対する処理を見ていくため、typeck_item_bodies()へと進んでいく。関数名からも分かるように、型チェックのメイン処理は関数の本体（Body）を一つの単位として実施される。

rustc_typeck/src/lib.rs

pub fn check_crate(tcx: TyCtxt<'_>) -> Result<(), ErrorReported> {
...
    tcx.sess.time("item_bodies_checking", || tcx.typeck_item_bodies(LOCAL_CRATE));
...
}

typeck_item_bodies()から、typeck()、typeck_with_fallback()と進んでいく。

rustc_typeck/src/check/mod.rs

fn typeck<'tcx>(tcx: TyCtxt<'tcx>, def_id: LocalDefId) -> &ty::TypeckResults<'tcx> {
    if let Some(param_did) = tcx.opt_const_param_of(def_id) {
        tcx.typeck_const_arg((def_id, param_did))
    } else {
        let fallback = move || tcx.type_of(def_id.to_def_id());
        typeck_with_fallback(tcx, def_id, fallback)
    }
}
...
fn typeck_item_bodies(tcx: TyCtxt<'_>, crate_num: CrateNum) {
    debug_assert!(crate_num == LOCAL_CRATE);
    tcx.par_body_owners(|body_owner_def_id| {
        tcx.ensure().typeck(body_owner_def_id);
    });
}

typeck_with_fallback()の中身はそれなりに大きいので記載は省略している部分も多いが、typeck_resultsを生成するのが中心的な処理になっている。中でもメイン処理と言えるのがcheck_fn()という関数だ。この関数内で型チェックを実施した後、resolve_type_vars_in_body()で最終的な結果を書き出し、上位に返すというのが大きな処理の流れと考えていいと思う。

rustc_typeck/src/check/mod.rs

fn typeck_with_fallback<'tcx>(
    tcx: TyCtxt<'tcx>,
    def_id: LocalDefId,
    fallback: impl Fn() -> Ty<'tcx> + 'tcx,
) -> &'tcx ty::TypeckResults<'tcx> {
...
    let typeck_results = Inherited::build(tcx, def_id).enter(|inh| {
        let param_env = tcx.param_env(def_id);
        let fcx = if let (Some(header), Some(decl)) = (fn_header, fn_decl) {
            let fn_sig = if crate::collect::get_infer_ret_ty(&decl.output).is_some() {
                let fcx = FnCtxt::new(&inh, param_env, body.value.hir_id);
                AstConv::ty_of_fn(
                    &fcx,
                    header.unsafety,
                    header.abi,
                    decl,
                    &hir::Generics::empty(),
                    None,
                )
            } else {
                tcx.fn_sig(def_id)
            };
...
            let fcx = check_fn(&inh, param_env, fn_sig, decl, id, body, None).0;
            fcx
        } else {
...
        };
...
        fcx.resolve_type_vars_in_body(body)
    });

    // Consistency check our TypeckResults instance can hold all ItemLocalIds
    // it will need to hold.
    assert_eq!(typeck_results.hir_owner, id.owner);

    typeck_results
}

ちなみに、型チェックの中でトレイト関連の処理もかなりのボリュームで絡み合っているが、ここでは触れない。

check_fn()についてもう少し深掘っておこう。FnCtxtを生成し、GatherLocalsVisitorのvisit_body()で関数内のローカル変数を収集し、check_return_expr()で関数内の型チェックを実施するという流れになっている。

rustc_typeck/src/check/check.rs

pub(super) fn check_fn<'a, 'tcx>(
    inherited: &'a Inherited<'a, 'tcx>,
    param_env: ty::ParamEnv<'tcx>,
    fn_sig: ty::FnSig<'tcx>,
    decl: &'tcx hir::FnDecl<'tcx>,
    fn_id: hir::HirId,
    body: &'tcx hir::Body<'tcx>,
    can_be_generator: Option<hir::Movability>,
) -> (FnCtxt<'a, 'tcx>, Option<GeneratorTypes<'tcx>>) {
    let mut fn_sig = fn_sig;

    debug!("check_fn(sig={:?}, fn_id={}, param_env={:?})", fn_sig, fn_id, param_env);

    // Create the function context. This is either derived from scratch or,
    // in the case of closures, based on the outer context.
    let mut fcx = FnCtxt::new(inherited, param_env, body.value.hir_id);
...
    GatherLocalsVisitor::new(&fcx, outer_hir_id).visit_body(body);
...
    if let ty::Dynamic(..) = declared_ret_ty.kind() {
...
    } else {
        fcx.require_type_is_sized(declared_ret_ty, decl.output.span(), traits::SizedReturnType);
        fcx.check_return_expr(&body.value);
    }
...
    (fcx, gen_ty)
}

ローカル変数の収集

まずはGatherLocalsVisitorに関する処理を見ていく。データ型を作った後、visit_body()というメソッドを呼んでいるが、これはHIRのところで説明したAST walkerと同じような、HIR walkerになっている。つまりは、HIRの木構造を下っていきながらVisitorに実装されているメソッドが呼ばれていくことになる。ローカル変数に対する処理visit_local()が実装されているので、それを見てみよう。

rustc_typeck/src/check/gather_locals.rs

impl<'a, 'tcx> Visitor<'tcx> for GatherLocalsVisitor<'a, 'tcx> {
...
    // Add explicitly-declared locals.
    fn visit_local(&mut self, local: &'tcx hir::Local<'tcx>) {
...
        let local_ty = match local.ty {
            Some(ref ty) => {
...
            }
            None => None,
        };
        self.assign(local.span, local.hir_id, local_ty);
...
    }
...
}

冒頭のイメージを考えると_aには型指定がないため、local_tyはNoneに設定された状態でassign()が呼ばれる。

rustc_typeck/src/check/gather_locals.rs

impl<'a, 'tcx> GatherLocalsVisitor<'a, 'tcx> {
...
    fn assign(&mut self, span: Span, nid: hir::HirId, ty_opt: Option<LocalTy<'tcx>>) -> Ty<'tcx> {
        match ty_opt {
            None => {
                // Infer the variable's type.
                let var_ty = self.fcx.next_ty_var(TypeVariableOrigin {
                    kind: TypeVariableOriginKind::TypeInference,
                    span,
                });
                self.fcx
                    .locals
                    .borrow_mut()
                    .insert(nid, LocalTy { decl_ty: var_ty, revealed_ty: var_ty });
                var_ty
            }
            Some(typ) => {
...
            }
        }
    }
}

next_ty_var()は、型推論関連の処理が実装されているrustc_inferクレートで提供される。next_ty_var()から、mk_ty_var()、mk_ty_infer()と続いており、途中にあるnext_ty_var_id()で推論のための型変数が生成され、それに紐づくTyVidが返されている。TyVidの生成にはnew_var()というメソッドが使われているが、これについては後ほどもう少し触れる。

rustc_infer/src/infer/mod.rs

impl<'a, 'tcx> InferCtxt<'a, 'tcx> {
...
    pub fn next_ty_var_id(&self, diverging: bool, origin: TypeVariableOrigin) -> TyVid {
        self.inner.borrow_mut().type_variables().new_var(self.universe(), diverging, origin)
    }

    pub fn next_ty_var(&self, origin: TypeVariableOrigin) -> Ty<'tcx> {
        self.tcx.mk_ty_var(self.next_ty_var_id(false, origin))
    }
...
}

rustc_middle/src/ty/context.rs

impl<'tcx> TyCtxt<'tcx> {
...
    pub fn mk_ty_var(self, v: TyVid) -> Ty<'tcx> {
        self.mk_ty_infer(TyVar(v))
    }
...
    pub fn mk_ty_infer(self, it: InferTy) -> Ty<'tcx> {
        self.mk_ty(Infer(it))
    }
...
}

型の表現

ここで、先程の関数で設定しているデータ型について見てみよう。Tyの実体はTySとなっており、TySはTyKindをもっている。これが内部で型の種別を表す表現となる。

rustc_middle/src/ty/mod.rs

pub struct TyS<'tcx> {
    /// This field shouldn't be used directly and may be removed in the future.
    /// Use `TyS::kind()` instead.
    kind: TyKind<'tcx>,
...
}
...
pub type Ty<'tcx> = &'tcx TyS<'tcx>;

TyKindにはおなじみの型が並んでいるが、その中にInferというバリアントがあり、これが型推論が必要であることを示している。Inferの中にもInferTyとして3種類あり、それぞれ制限なし、整数、浮動小数を表しているようだ。これは、整数と浮動小数にはデフォルトの型があるためだろう。例えば、整数であることまで推論できれば、最終的にはデフォルトのi32と結論付けることができる。

rustc_middle/src/ty/sty.rs

pub enum TyKind<'tcx> {
...
    Bool,
...
    Char,
...
    Int(ast::IntTy),
...
    Uint(ast::UintTy),
...
    Float(ast::FloatTy),
...
    /// A type variable used during type checking.
    Infer(InferTy),
...
}
...
pub enum InferTy {
    TyVar(TyVid),
    IntVar(IntVid),
    FloatVar(FloatVid),
...
}

これで、関数の中で宣言された変数を洗い出し、それに型推論が必要であるというところまで認識することができた。

型の決定

さて、話をcheck_fn()まで戻し、今度はcheck_return_expr()を見ていこう。ここで少し注意（というか自分がハマったところ）だが、メソッドに渡しているbody.valueは関数の戻り値ではなく、関数の中身そのものとなっている。これは冒頭のコマンドの出力からも確認できる。

check_return_expr()は、関数の戻り値の型も引数に加えた上でcheck_expr_with_hint()と続いていく。

rustc_typeck/src/check/expr.rs

impl<'a, 'tcx> FnCtxt<'a, 'tcx> {
...
    pub(super) fn check_return_expr(&self, return_expr: &'tcx hir::Expr<'tcx>) {
        let ret_coercion = self.ret_coercion.as_ref().unwrap_or_else(|| {
            span_bug!(return_expr.span, "check_return_expr called outside fn body")
        });

        let ret_ty = ret_coercion.borrow().expected_ty();
        let return_expr_ty = self.check_expr_with_hint(return_expr, ret_ty.clone());
        ret_coercion.borrow_mut().coerce(
            self,
            &self.cause(return_expr.span, ObligationCauseCode::ReturnValue(return_expr.hir_id)),
            return_expr,
            return_expr_ty,
        );
    }
...
}

そこから途中は省略するがcheck_expr_with_hint()、check_expr_with_expectation()と続いていき、check_expr_kind()で式の種別ごとに処理が分岐する。関数の本体なので最初はBlockへと進んでいくことになる。

rustc_typeck/src/check/expr.rs

impl<'a, 'tcx> FnCtxt<'a, 'tcx> {
...
    fn check_expr_kind(
        &self,
        expr: &'tcx hir::Expr<'tcx>,
        expected: Expectation<'tcx>,
    ) -> Ty<'tcx> {
        debug!("check_expr_kind(expr={:?}, expected={:?})", expr, expected);

        let tcx = self.tcx;
        match expr.kind {
...
            ExprKind::Block(ref body, _) => self.check_block_with_expected(&body, expected),
...
        }
    }
...
}

check_block_with_expected()で関数内の文ごとにcheck_stmt()を呼び、さらにその中で文の種別ごとに処理が別れている。ここではローカル変数Localを見ていくのでcheck_decl_local()と進む。

rustc_typeck/src/check/fn_ctxt.rs

impl<'a, 'tcx> FnCtxt<'a, 'tcx> {
...
    pub fn check_stmt(&self, stmt: &'tcx hir::Stmt<'tcx>) {
...
        match stmt.kind {
            hir::StmtKind::Local(ref l) => {
                self.check_decl_local(&l);
            }
...
        }
...
    }
...
    pub(super) fn check_block_with_expected(
        &self,
        blk: &'tcx hir::Block<'tcx>,
        expected: Expectation<'tcx>,
    ) -> Ty<'tcx> {
...
        let (ctxt, ()) = self.with_breakable_ctxt(blk.hir_id, ctxt, || {
            for s in blk.stmts {
                self.check_stmt(s);
            }
...
        });
...
    }
}

check_decl_local()ではlocal.initが存在する（イメージでは42_i32で変数の初期化している）ため、check_decl_initializer()が呼ばれる。そこからcheck_expr_coercable_to_type()が呼ばれ、型強制の処理に進んでいくことになる。check_expr_coercable_to_type()には、初期化に使われる式（42_i32）と、まだInferとなっている変数の型を渡していることを意識しよう。

rustc_typeck/src/check/fn_ctxt.rs

impl<'a, 'tcx> FnCtxt<'a, 'tcx> {
...
    pub fn check_decl_initializer(
        &self,
        local: &'tcx hir::Local<'tcx>,
        init: &'tcx hir::Expr<'tcx>,
    ) -> Ty<'tcx> {
...
        let local_ty = self.local_ty(init.span, local.hir_id).revealed_ty;
        if let Some(m) = ref_bindings {
...
        } else {
            self.check_expr_coercable_to_type(init, local_ty, None)
        }
    }

    /// Type check a `let` statement.
    pub fn check_decl_local(&self, local: &'tcx hir::Local<'tcx>) {
        // Determine and write the type which we'll check the pattern against.
        let ty = self.local_ty(local.span, local.hir_id).decl_ty;
        self.write_ty(local.hir_id, ty);

        // Type check the initializer.
        if let Some(ref init) = local.init {
            let init_ty = self.check_decl_initializer(local, &init);
            self.overwrite_local_ty_if_err(local, ty, init_ty);
        }
...
    }
...
}

ここも途中は省略するが、型強制の処理はcheck_expr_coercable_to_type()、demand_coerce()、demand_coerce_diag()、try_coerce()を経由してcoerce()と続いていく。先程渡した引数の型情報として、aには42_i32のi32、bには_aのInferが設定されているはずである。いくつか分岐ルートもあるが、今回は特に引っかからずにOtherwiseとコメントの付いたルートに進んでいく。

rustc_typeck/src/check/coerce.rs

impl<'f, 'tcx> Coerce<'f, 'tcx> {
...
    fn coerce(&self, a: Ty<'tcx>, b: Ty<'tcx>) -> CoerceResult<'tcx> {
...
        match *a.kind() {
...
            _ => {
                // Otherwise, just use unification rules.
                self.unify_and(a, b, identity)
            }
        }
    }
...
}

unify_and()の先ではunify()というメソッドが呼ばれ、InferResultという型を返している。名前からも分かるように、ここからは型推論の処理に入っていく。私には型強制と型推論の違いをはっきり説明することはできないのだが、型推論の一つの要素として型強制があるようなイメージだろうか。ここで、InferResultは処理の成否を返すのみで結果の内容は返さないことに注意しよう。型推論の結果はコンテキスト（InferCtxt）で管理されるようだ。

rustc_typeck/src/check/coerce.rs

impl<'f, 'tcx> Coerce<'f, 'tcx> {
...
    fn unify(&self, a: Ty<'tcx>, b: Ty<'tcx>) -> InferResult<'tcx, Ty<'tcx>> {
        debug!("unify(a: {:?}, b: {:?}, use_lub: {})", a, b, self.use_lub);
        self.commit_if_ok(|_| {
            if self.use_lub {
                self.at(&self.cause, self.fcx.param_env).lub(b, a)
            } else {
                self.at(&self.cause, self.fcx.param_env)
                    .sup(b, a)
                    .map(|InferOk { value: (), obligations }| InferOk { value: a, obligations })
            }
        })
    }

    /// Unify two types (using sub or lub) and produce a specific coercion.
    fn unify_and<F>(&self, a: Ty<'tcx>, b: Ty<'tcx>, f: F) -> CoerceResult<'tcx>
    where
        F: FnOnce(Ty<'tcx>) -> Vec<Adjustment<'tcx>>,
    {
        self.unify(&a, &b)
            .and_then(|InferOk { value: ty, obligations }| success(f(ty), ty, obligations))
    }
...
}

型推論

unify()で呼ばれているsup()というメソッドに注目する。ここからはrustc_inferクレートに視点が移る。結構ややこしかったので、丁寧に見ていこうと思う。同名のメソッドが型ごとに定義されていたりするので、今自分が見ている型を見失わないようにしよう。

まずは単純に追っていく。sup()の先ではTraceに実装されているsub()が呼ばれている。

rustc_infer/src/infer/at.rs

impl<'a, 'tcx> At<'a, 'tcx> {
...
    /// Makes `a <: b`, where `a` may or may not be expected.
    pub fn sub_exp<T>(self, a_is_expected: bool, a: T, b: T) -> InferResult<'tcx, ()>
    where
        T: ToTrace<'tcx>,
    {
        self.trace_exp(a_is_expected, a, b).sub(a, b)
    }

    /// Makes `actual <: expected`. For example, if type-checking a
    /// call like `foo(x)`, where `foo: fn(i32)`, you might have
    /// `sup(i32, x)`, since the "expected" type is the type that
    /// appears in the signature.
    pub fn sup<T>(self, expected: T, actual: T) -> InferResult<'tcx, ()>
    where
        T: ToTrace<'tcx>,
    {
        self.sub_exp(false, actual, expected)
    }
...
}
...
impl<'a, 'tcx> Trace<'a, 'tcx> {
    /// Makes `a <: b` where `a` may or may not be expected (if
    /// `a_is_expected` is true, then `a` is expected).
    pub fn sub<T>(self, a: T, b: T) -> InferResult<'tcx, ()>
    where
        T: Relate<'tcx>,
    {
        debug!("sub({:?} <: {:?})", a, b);
        let Trace { at, trace, a_is_expected } = self;
        at.infcx.commit_if_ok(|_| {
            let mut fields = at.infcx.combine_fields(trace, at.param_env);
            fields
                .sub(a_is_expected)
                .relate(a, b)
                .map(move |_| InferOk { value: (), obligations: fields.obligations })
        })
    }
...
}

Traceのsub()の中で、さらにsub()が呼ばれる。これはSub型のデータを生成するだけである。

rustc_infer/src/infer/combine.rs

impl<'infcx, 'tcx> CombineFields<'infcx, 'tcx> {
...
    pub fn sub<'a>(&'a mut self, a_is_expected: bool) -> Sub<'a, 'infcx, 'tcx> {
        Sub::new(self, a_is_expected)
    }
...
}

そしてSubのメソッドであるrelate()を呼んでいる。しかしこのrelate()は結構複雑だ。

SubはTypeRelationというトレイトを実装している。TypeRelationの定義はrustc_middle/src/ty/relate.rsにある。

rustc_middle/src/ty/relate.rs

pub trait TypeRelation<'tcx>: Sized {
...
    /// Generic relation routine suitable for most anything.
    fn relate<T: Relate<'tcx>>(&mut self, a: T, b: T) -> RelateResult<'tcx, T> {
        Relate::relate(self, a, b)
    }
...
}

TypeRelationのrelate()は、Relateのrelate()を呼び出す。同ファイルには様々な型に対するRelateが実装されているが、どのrelate()が呼ばれるかは型パラメータであるTに依存することになる。つまりはaとbの型であり、ここではTyとなるはずだ。Tyに対するRelateの実装を見てみよう。

rustc_middle/src/ty/relate.rs

impl<'tcx> Relate<'tcx> for Ty<'tcx> {
    #[inline]
    fn relate<R: TypeRelation<'tcx>>(
        relation: &mut R,
        a: Ty<'tcx>,
        b: Ty<'tcx>,
    ) -> RelateResult<'tcx, Ty<'tcx>> {
        relation.tys(a, b)
    }
}

引数relationに実装されているtys()のメソッドが呼ばれている。relationの型もジェネリクスとなっており、今見ている状況下ではSubとなっているはずだ。結果として、Traceのsub()の中で呼ばれているrelata()は、Subに実装されているtys()が呼ばれることになる。

tys()の引数は、上述したようにaがi32、bがInferとなっているので、そのルートを追ってみよう。instantiate()というメソッドが呼ばれているようだ。

rustc_infer/src/infer/at.rs

impl TypeRelation<'tcx> for Sub<'combine, 'infcx, 'tcx> {
...
    fn tys(&mut self, a: Ty<'tcx>, b: Ty<'tcx>) -> RelateResult<'tcx, Ty<'tcx>> {
        debug!("{}.tys({:?}, {:?})", self.tag(), a, b);

        if a == b {
            return Ok(a);
        }

        let infcx = self.fields.infcx;
        let a = infcx.inner.borrow_mut().type_variables().replace_if_possible(a);
        let b = infcx.inner.borrow_mut().type_variables().replace_if_possible(b);
        match (a.kind(), b.kind()) {
...
            (_, &ty::Infer(TyVar(b_id))) => {
                self.fields.instantiate(a, RelationDir::SubtypeOf, b_id, self.a_is_expected)?;
                Ok(a)
            }
...
            }
        }
    }
...
}

instantiate()では、まずgeneralize()にaの型情報a_tyが渡され、ここからbの型であるb_tyが決定される。今の例ではaの型は明らかなので特に問題なくi32が返るはずだ。ここで初めて、不明だったbの型がaの型と同じであるというつながりができたことになる。

bの型が分かったので、それを記録しておこう。続けてinstantiate()が呼ばれるが、こちらはTypeVariableTableに実装されているinstantiate()となる。

rustc_infer/src/infer/combine.rs

impl<'infcx, 'tcx> CombineFields<'infcx, 'tcx> {
...
    pub fn instantiate(
        &mut self,
        a_ty: Ty<'tcx>,
        dir: RelationDir,
        b_vid: ty::TyVid,
        a_is_expected: bool,
    ) -> RelateResult<'tcx, ()> {
        use self::RelationDir::*;
...
        let Generalization { ty: b_ty, needs_wf } = self.generalize(a_ty, b_vid, dir)?;
        debug!(
            "instantiate(a_ty={:?}, dir={:?}, b_vid={:?}, generalized b_ty={:?})",
            a_ty, dir, b_vid, b_ty
        );
        self.infcx.inner.borrow_mut().type_variables().instantiate(b_vid, b_ty);
...
        match dir {
            EqTo => self.equate(a_is_expected).relate(a_ty, b_ty),
            SubtypeOf => self.sub(a_is_expected).relate(a_ty, b_ty),
            SupertypeOf => {
                self.sub(a_is_expected).relate_with_variance(ty::Contravariant, a_ty, b_ty)
            }
        }?;

        Ok(())
    }
...
}

ローカル変数を収集するときに、型変数とそれに紐づくTyVidを生成していたことを思い出そう。TypeVariableTableのinstantiate()では、そのとき生成したTyVidと具体的な型をKnownとして保存することで結び付けているようだ。

rustc_infer/src/infer/type_variable.rs

impl<'tcx> TypeVariableTable<'_, 'tcx> {
...
    /// Instantiates `vid` with the type `ty`.
...
    pub fn instantiate(&mut self, vid: ty::TyVid, ty: Ty<'tcx>) {
        let vid = self.root_var(vid);
        debug_assert!(self.probe(vid).is_unknown());
        debug_assert!(
            self.eq_relations().probe_value(vid).is_unknown(),
            "instantiating type variable `{:?}` twice: new-value = {:?}, old-value={:?}",
            vid,
            ty,
            self.eq_relations().probe_value(vid)
        );
        self.eq_relations().union_value(vid, TypeVariableValue::Known { value: ty });

        // Hack: we only need this so that `types_escaping_snapshot`
        // can see what has been unified; see the Delegate impl for
        // more details.
        self.undo_log.push(Instantiate { vid });
    }
...
}

ここでunion_value()というメソッドが呼ばれているが、これは外部のenaというクレートで提供されている。enaはrustc用に作られたUnion–Findを実装したクレートのようで、crates.ioにも公開されている。（enaの動作は細かい説明ができるほど理解していない、、）

少し話は戻るが、型変数を生成するときにnew_var()というメソッドを使っていた。これも内部ではnew_key()というenaのメソッドを使用し、初期状態としてUnknownを設定していたことが分かる。型推論によって、Unknownに設定されていたTyVidに紐づく型変数がKnownに更新されたことになる。

rustc_infer/src/infer/type_variable.rs

impl<'tcx> TypeVariableTable<'_, 'tcx> {
...
    /// Creates a new type variable.
...
    pub fn new_var(
        &mut self,
        universe: ty::UniverseIndex,
        diverging: bool,
        origin: TypeVariableOrigin,
    ) -> ty::TyVid {
        let eq_key = self.eq_relations().new_key(TypeVariableValue::Unknown { universe });
...
        eq_key.vid
    }
...
}

推論結果の保存

型推論によって変数の型を決定できたので、冒頭のtypeck_with_fallback()まで戻ってresolve_type_vars_in_body()を深掘りしてみよう。

内部ではWritebackCxというデータを生成し、visit_xxx()をひたすら呼んでいるようだ。つまりはここでもVisitorが定義され、HIR walkerが使われている。ローカル変数を処理するvisit_local()があるので、その中のresolve()に注目する。型推論は完了しているが、ここでresolve()に渡しているvar_tyは、まだInferとなっていることを意識しておこう。

rustc_typeck/src/check/writeback.rs

impl<'a, 'tcx> FnCtxt<'a, 'tcx> {
    pub fn resolve_type_vars_in_body(
        &self,
        body: &'tcx hir::Body<'tcx>,
    ) -> &'tcx ty::TypeckResults<'tcx> {
...
        let mut wbcx = WritebackCx::new(self, body, rustc_dump_user_substs);
...
        wbcx.visit_body(body);
        wbcx.visit_upvar_capture_map();
        wbcx.visit_closures();
        wbcx.visit_liberated_fn_sigs();
        wbcx.visit_fru_field_types();
        wbcx.visit_opaque_types(body.value.span);
        wbcx.visit_coercion_casts();
        wbcx.visit_user_provided_tys();
        wbcx.visit_user_provided_sigs();
        wbcx.visit_generator_interior_types();
...
        self.tcx.arena.alloc(wbcx.typeck_results)
    }
}
...
impl<'cx, 'tcx> Visitor<'tcx> for WritebackCx<'cx, 'tcx> {
...
    fn visit_local(&mut self, l: &'tcx hir::Local<'tcx>) {
        intravisit::walk_local(self, l);
        let var_ty = self.fcx.local_ty(l.span, l.hir_id).decl_ty;
        let var_ty = self.resolve(&var_ty, &l.span);
        self.write_ty_to_typeck_results(l.hir_id, var_ty);
    }
...
}

resolve()は内部でResolverを生成し、それを引数としてfold_with()というメソッドを呼んでいる。

rustc_typeck/src/check/writeback.rs

impl<'cx, 'tcx> WritebackCx<'cx, 'tcx> {
...
    fn resolve<T>(&mut self, x: &T, span: &dyn Locatable) -> T
    where
        T: TypeFoldable<'tcx>,
    {
        let mut resolver = Resolver::new(self.fcx, span, self.body);
        let x = x.fold_with(&mut resolver);
...
        x
    }
}

このfold_with()も初見ではなかなかの曲者だ。イメージを掴むにはfoldのドキュメントを見るのが早いかもしれない。このような記述がある。

T.fold_with(F) --calls--> F.fold_T(T) --calls--> T.super_fold_with(F)

今の場合TはTy、FはResolverであるため、関数名は小文字でることも考慮に入れると、Resolverのfold_ty()というメソッドが呼ばれることになりそうだ。実際に同ファイル内を検索すると、まさにそのようなメソッドが定義されていることが分かる。

rustc_typeck/src/check/writeback.rs

impl<'cx, 'tcx> TypeFolder<'tcx> for Resolver<'cx, 'tcx> {
...
    fn fold_ty(&mut self, t: Ty<'tcx>) -> Ty<'tcx> {
        match self.infcx.fully_resolve(&t) {
            Ok(t) => self.infcx.tcx.erase_regions(&t),
            Err(_) => {
                debug!("Resolver::fold_ty: input type `{:?}` not fully resolvable", t);
                self.report_type_error(t);
                self.replaced_with_error = true;
                self.tcx().ty_error()
            }
        }
    }
...
}

fold_with()の具体的な実装が知りたい場合は、rustc_middle/src/ty/fold.rs、rustc_middle/src/ty/structural_impls.rsあたりを見ればfold_ty()が呼ばれるまでの流れが分かる。

さて、fold_ty()ではfully_resolve()というメソッドをが呼ばれているので見ていこう。fully_resolve()でも同じようにfold_with()が使用され、今度はFullTypeResolverのfold_ty()に進んでいくことになる。

rustc_infer/src/infer/resolve.rs

pub fn fully_resolve<'a, 'tcx, T>(infcx: &InferCtxt<'a, 'tcx>, value: &T) -> FixupResult<'tcx, T>
where
    T: TypeFoldable<'tcx>,
{
    let mut full_resolver = FullTypeResolver { infcx, err: None };
    let result = value.fold_with(&mut full_resolver);
    match full_resolver.err {
        None => Ok(result),
        Some(e) => Err(e),
    }
}
...
impl<'a, 'tcx> TypeFolder<'tcx> for FullTypeResolver<'a, 'tcx> {
...
    fn fold_ty(&mut self, t: Ty<'tcx>) -> Ty<'tcx> {
        if !t.needs_infer() {
            t // micro-optimize -- if there is nothing in this type that this fold affects...
        } else {
            let t = self.infcx.shallow_resolve(t);
            match *t.kind() {
...
                _ => t.super_fold_with(self),
            }
        }
    }
...
}

さらにこのFullTypeResolverのfold_ty()でも、fold_with()を介してShallowResolverのfold_ty()が呼ばれ、最終的にshallow_resolve_ty()に行き着く。

rustc_infer/src/infer/mod.rs

impl<'a, 'tcx> InferCtxt<'a, 'tcx> {
...
    fn shallow_resolve_ty(&self, typ: Ty<'tcx>) -> Ty<'tcx> {
        match *typ.kind() {
            ty::Infer(ty::TyVar(v)) => {
...
                let known = self.inner.borrow_mut().type_variables().probe(v).known();
                known.map(|t| self.shallow_resolve_ty(t)).unwrap_or(typ)
            }
...
            _ => typ,
        }
    }
...
}

ここでTyVidに対してprobe()でアクセスし、known()で型変数の中身の型を取り出している。この中身は型推論により決定された型情報になっているはずだ。ちなみに、probe()で使われるinlined_probe_value()もenaのメソッドになっている。

rustc_infer/src/infer/type_variable.rs

impl<'tcx> TypeVariableValue<'tcx> {
    /// If this value is known, returns the type it is known to be.
    /// Otherwise, `None`.
    pub fn known(&self) -> Option<Ty<'tcx>> {
        match *self {
            TypeVariableValue::Unknown { .. } => None,
            TypeVariableValue::Known { value } => Some(value),
        }
    }
...
}
...
impl<'tcx> TypeVariableTable<'_, 'tcx> {
...
    /// Retrieves the type to which `vid` has been instantiated, if
    /// any.
    pub fn probe(&mut self, vid: ty::TyVid) -> TypeVariableValue<'tcx> {
        self.inlined_probe(vid)
    }

    /// An always-inlined variant of `probe`, for very hot call sites.
    #[inline(always)]
    pub fn inlined_probe(&mut self, vid: ty::TyVid) -> TypeVariableValue<'tcx> {
        self.eq_relations().inlined_probe_value(vid)
    }
...
}

これで無事に、型推論が必要なローカル変数の型情報を得ることができた。あとはwrite_ty_to_typeck_results()でHirIdと型情報を紐づけて、型チェックは完了となる。

rustc_typeck/src/check/writeback.rs

impl<'cx, 'tcx> WritebackCx<'cx, 'tcx> {
...
    fn write_ty_to_typeck_results(&mut self, hir_id: hir::HirId, ty: Ty<'tcx>) {
        debug!("write_ty_to_typeck_results({:?}, {:?})", hir_id, ty);
        assert!(!ty.needs_infer() && !ty.has_placeholders() && !ty.has_free_regions());
        self.typeck_results.node_types_mut().insert(hir_id, ty);
    }
...
}

つづく

型システムの基礎が足りないこともあり、結構苦戦してしまった。ボリュームもそれなりになってしまったので今回はこのあたりで切り上げて、次回Analysisの残りを見ていきたいと思う。ソースコードにはあまり深入りしすぎないようにしたいが、借用チェッカーとか気になるな～。

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