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

# 前回までのあらすじ

[Rustの本家コンパイラ](https://github.com/rust-lang/rust)を[Guide to Rustc Development](https://rustc-dev-guide.rust-lang.org/about-this-guide.html)に沿って読んでいく。今回はRustの型システムに踏み込んでいくが、基礎が足りなすぎて泣きそうになった。あまり深い説明はできないと思うし、相変わらず網羅性はないです。

[目次（初回）](https://qiita.com/0yoyoyo/items/eba97a019d0e60324263)


# Analysis

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

### 型チェック

型チェックではソースコード内の式に対する型を、場合によっては型推論も使いながら、決定していく。処理は主に[rustc_typeck](https://doc.rust-lang.org/nightly/nightly-rustc/rustc_typeck/index.html)クレートで行われ、特にその中の[check](https://doc.rust-lang.org/nightly/nightly-rustc/rustc_typeck/check/index.html)モジュールが型チェックの中心的な位置づけになる。

##### 事前準備

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

```rust
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`）を一つの単位として実施される。

```rust: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()`と進んでいく。

```rust: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()`で最終的な結果を書き出し、上位に返すというのが大きな処理の流れと考えていいと思う。

```rust: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()`で関数内の型チェックを実施するという流れになっている。

```rust: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のところで説明した](https://qiita.com/0yoyoyo/items/7410b6897a4a202db67d#astからhir)AST walkerと同じような、**HIR walker**になっている。つまりは、HIRの木構造を下っていきながら`Visitor`に実装されているメソッドが呼ばれていくことになる。ローカル変数に対する処理`visit_local()`が実装されているので、それを見てみよう。

```rust: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()`が呼ばれる。

```rust: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()`というメソッドが使われているが、これについては後ほどもう少し触れる。

```rust: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))
    }
...
}
```

```rust: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`をもっている。これが内部で型の種別を表す表現となる。

```rust: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`と結論付けることができる。

```rust: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()`と続いていく。

```rust: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`へと進んでいくことになる。

```rust: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()`と進む。

```rust: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`となっている変数の型を渡していることを意識しよう。

```rust: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とコメントの付いたルートに進んでいく。

```rust: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`）で管理されるようだ。

```rust: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()`が呼ばれている。

```rust: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`型のデータを生成するだけである。

```rust: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にある。

```rust: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`の実装を見てみよう。

```rust: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()`というメソッドが呼ばれているようだ。

```rust: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()`となる。

```rust: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`として保存することで結び付けているようだ。

```rust: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](https://crates.io/crates/ena)というクレートで提供されている。enaはrustc用に作られた[Union–Find](https://ja.wikipedia.org/wiki/%E7%B4%A0%E9%9B%86%E5%90%88%E3%83%87%E3%83%BC%E3%82%BF%E6%A7%8B%E9%80%A0)を実装したクレートのようで、crates.ioにも公開されている。（enaの動作は細かい説明ができるほど理解していない、、）

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

```rust: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`となっていることを意識しておこう。

```rust: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()`というメソッドを呼んでいる。

```rust: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のドキュメント](https://doc.rust-lang.org/nightly/nightly-rustc/rustc_middle/ty/fold/index.html)を見るのが早いかもしれない。このような記述がある。

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

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

```rust: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()`に進んでいくことになる。

```rust: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()`に行き着く。

```rust: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のメソッドになっている。

```rust: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`と型情報を紐づけて、型チェックは完了となる。

```rust: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）](https://qiita.com/0yoyoyo/items/cdaa8a051abd0a62fffc)←次回