概要: Rustの型推論の大枠を説明する。

なお、筆者もRustの型推論の動作を詳細に把握しているわけではない。

短くまとめると

Rustの型推論はHindley-Milner型推論ベースである。したがって後方の式や文の内容から手前の型が推論されることもある。しかし以下に挙げるようなRust独自の特徴をもつ。
型推論は原則として関数定義の中で閉じており、関数の引数型や戻り値型は推論されない。これは、関数を抽象化の境界とするための意図的なものである。この意味で「局所的」というのであれば間違いではない。
- ただし、let多相を含む型推論を避ける意図もあるかもしれない。
関数呼び出しや一部の演算子などは、その部分の制約を立てる段階で、型の一部分が判明している必要がある。この動作は推論順序の影響を受ける。
トレイトによりオーバーロード可能になっている関数や演算子は、射影型を使っている場合、ボトムアップにしか推論されない(式全体の型からオペランドが推論されない)。
型強制は、その時点で型のミスマッチが判明している場合にのみ発生するので、推論順序の影響を受ける。
その他、整数型と浮動小数点数型が特別扱いされていたり、生存期間に関して部分型付けをもつための特別処理があるなどの違いがある。

Phase3の大まかな流れ

型検査・型推論はPhase3の一環として行われる。Phase3の流れは以下の通りである。

言語アイテム (Sized などの処理系が特殊扱いするアイテム) の収集
生存期間の名前解決
ソースコード中のリージョンの列挙
break/continueとループの対応関係の検査
static の定義に再帰・相互再帰がないかの検査
不安定機能の検査
型推論・型検査
static/const の安全性検査
可視性検査
イントリンシックの事前条件検査
unsafe 検査
match 検査
生存検査
右辺値の Sized 検査
MIR検査
借用検査
到達可能性検査
デッドコード検査
未使用機能検査
リント検査

つまり、型推論の段階では、収集したリージョンをもとにリージョンの上界と下界の推定も行う。借用同士がコンフリクトしているかどうかは後の検査で行う。

Hindley-Milner型推論

Rustの型推論はHindley-Milner型推論である。このことはrustc::inferのREADMEで言及されている。

This is loosely based on standard HM-type inference, but …

このREADMEでは、部分型付けについて重点的に補足されている。本記事では部分型付けの詳細には立ち入らないことにする。なお、Rustの部分型付けはリージョンの大小によって発生するものである。

Hindley-Milner型推論についてはすでに多くの解説があるが、ここで大まかに説明する。この型推論は、「変数を立てる」「方程式を立てる」「方程式を解く」という流れで型を決定していくものである。例えば、

let x = Default::default();
let y = 1;
let mut z;
z = x;
z = y;

というコードを考える。大雑把に言うと、この場合は3つの変数が生成される。つまり、 x の型, y の型, z の型である。これを以下 ?X, ?Y, ?Z と呼ぶことにする。

この例では単純な代入しかないため、方程式は以下のように立つ。

?Y = i32
?Z = ?X
?Z = ?Y

一般には Vec<_> のように型コンストラクタが関わってくる場合もある。いずれにせよ、このような方程式は一般に最汎単一化子アルゴリズムと呼ばれる方法で解くことができる。

最汎単一化子アルゴリズムは次の3つのうちのいずれかの結果を出す。

唯一解がある場合: 型推論は成功となる。
変数が残ってしまった場合: 情報が足りず、型推論は失敗となる。ただし、言語によってはデフォルト値を適用する場合がある。
解なし: 型エラーにより型検査は失敗となる。

上の例では ?X = ?Y = ?Z = i32 が唯一解となる。

Hindley-Milner型推論は、体系によっては全く型注釈なして推論できるが、Rustの場合はこれはあまり当てはまらない。一方、Hindley-Milner型推論のもう一つの特徴として、式の出現順にかかわらず制約を収集して柔軟性の高い推論を行えることが挙げられるが、これはRustの場合はそれなりに当てはまる。

例えば以下のプログラムでは、タプル x の要素型は最初の文からはわからないが、後続の文から推論されている。

fn main() {
    let mut x : (_, _) = Default::default();
    x.0 = "foo".to_string();
    x.1 = vec![2, 2, 4];
    println!("{:?}", x);
}

インクリメンタルな型推論

Hindley-Milner型推論では、制約を集める途中でインクリメンタルにそれを解くこともできる。Rustの場合、Hindley-Milner型推論の通常の等式制約は、インクリメンタルに解くようになっている。

Rustの場合は部分型付けがあるため、等式ではなく不等号制約も扱いたい場合がある。また型だけではなく生存期間や型+ミュータビリティーなどにも不等号制約を解かせたいことから、これを rustc::ty::relate として一般化している。

最汎単一化子アルゴリズムは型の木構造にそって同値判定をする。この一般的なルーチンはsuper_relate_tys に実装されている。変数の処理は別の場所にあり、関係の種別(等号か不等号か)により実装が分けられている。例えば rustc::infer::equate の tys関数を見ると変数の処理がわかる。

制約の収集順序

理想的な(例えばSTLCに対する)Hindley-Milner型推論では、制約の収集順序は型推論の動作に影響を与えない。というのも、制約の収集のために、その制約を解いた結果自体が必要となることがないからである。

しかし、Rustの場合はそうはいかない。型がある程度わかっていないと、次の制約集めがそもそもできない場面があるからである。

Rustコンパイラでいうと、 rustc_typeck::check などで structurally_resolved_type メソッドを呼んでいる部分がそれに当たる。例えば以下のような場面がそれに当たる。

f() の被呼び出し側 f
- 理由: クロージャ、クロージャトレイトを実装した型、関数定義、関数ポインタのいずれであるか判定する必要があるため
x.some_method(), x.some_field, x.0 におけるレシーバー x
- 理由: 名前解決に必要なため。また、自動参照外しのため。
*x, x[i] のオペランド x
- 理由: 自動参照外しのため。
!x, -x のオペランド x
- 理由: 基本型のヒューリスティックスのため。 (-x は整数型に対しては同じ整数型が推論される)

以下がその実例である。

fn main() {
    {
        let mut x = Default::default();
        // if let Some(x) = x { x(); } // Error
        x = Some(main);
        if let Some(x) = x { x(); }
    }
    {
        let mut x = Default::default();
        // x.clone(); // Error
        x = 1;
        x.clone();
    }
    {
        let mut x = Default::default();
        // x.0; // Error
        x = (1, 2);
        x.0;
    }
    {
        let mut x = Default::default();
        // *x; // Error
        x = Box::new(0);
        *x;
    }
    {
        let mut x = Default::default();
        // -x; // Error
        x = 0;
        -x;
    }
    {
        let mut x = Default::default();
        // x[1]; // Error
        x = [0, 1, 2];
        x[1];
    }
}

型強制

Rustの型強制は、式の型と必要な型が異なるときに、自動的に変換を挟むものである。そのため、その時点で型がどれくらい判明しているかに応じて、挙動が変わる可能性がある。

例えば、以下のように、推論順序によってコンパイルできたりできなかったりする可能性がある。

fn main() {
    {
        let mut y = Default::default();
        y = Box::new(Box::new([1, 2, 3]) as Box<[_]>);
        y = Box::new(Box::new([1, 2, 3]));
        let z : Box<Box<[_]>> = y;
    }
    // Error
    /*{
        let mut y = Default::default();
        y = Box::new(Box::new([1, 2, 3]));
        y = Box::new(Box::new([1, 2, 3]) as Box<[_]>);
        let z : Box<Box<[_]>> = y;
    }*/
}

型強制サイトは check_expr_coercable_to_type や demand_coerce を呼んでいる箇所であり、以下の位置にある。

static/constの右辺→左辺型
関数・クロージャの最後の式→戻り値型
return の式→戻り値型
let の右辺→左辺型 (左辺に ref がない場合のみ)
代入の右辺→左辺型
[x; n] の要素→期待されている要素型
タプルの要素→期待されている要素型
x || y, x && y の右辺→ bool
それ以外の二項演算の右辺→ 左辺のメソッド解決により期待される型
x[i] の i → Index::Output 型
関数・メソッド呼び出しの引数→仮引数型
構造体リテラルのフィールド値→フィールド型
ブロックの末尾→期待されているブロックの型

トレイト実装の選択

Rustの型推論を妨げるもう1つの壁が、トレイト実装の選択である。例えば以下の式を考える。

lhs + rhs

これはおおよそ ::std::ops::Add::add(lhs, rhs) の糖衣構文である(正確には型強制が含まれるので少し異なる)から、その戻り値は <Lhs as ::std::ops::Add<Rhs>>::Output である。

このような射影型は、他の型コンストラクタ (&X, Box<X>, [X; n] など) と異なり、単射でも排反的でもない。そのため、Hindley-Milner型推論の観点からは、これは型コンストラクタというよりも特殊な型変数のように見える(一般には単一化ができない)。

射影型を決定するには、このトレイト制約すなわち Lhs: ::std::ops::Add<Rhs> を解くしかない。これをRustでは選択と呼んでいる。このトレイト制約に対する実装を選ぶのが目的だからである。

上に挙げた、制約集めのために型が判明している必要がある場合(structurally_resolved_type)は、等式制約だけではなく、トレイト制約もできる限り選択される。

それ以外の場合は、トレイト制約の解決は後回しにされる。例えば以下の例では、 10.add(20) の型は 10: i32 が確定するまでわからないが問題ない。しかし、 10.add(20).add(30) の場合は 10.add(20) の型をその場で判定する必要があるからエラーになる。

use std::ops::Add;
fn main() {
    println!("{}", 10.add(20));
    // println!("{}", 10.add(20).add(30)); // Error
}

制約集めの順序と期待型の伝搬

制約集めは基本的に実行順 (上から下、左から右、中から外) に行われる。例えば、以下のような推論順序依存性がある。

fn main() {
    let mut x = Default::default();
    // (x.clone(), {x = 1}); // Error
    ({x = 1}, x.clone());
}

ただし、そのままではトップダウンな推論ができないために、主に型強制が思ったとおりに発生せず不便なことがある。例えば以下の例を考える。

fn main() {
    let x : Box<[_]> = Box::new([1, 2, 3]);
    //                 ^^^^^^^^^^^^^^^^^^^ coercion site
    let y : Box<Box<[_]>> = Box::new(Box::new([1, 2, 3]));
    //                               ^^^^^^^^^^^^^^^^^^^ coercion site
}

この例はどちらも正しくコンパイルされる。

ここで、 x の型強制は let の制約集めのときに発生しているということで説明がつくが、 y の型強制は let ではなく、外側の Box::new の引数部分で発生している。

この型強制が発生するためには、 Box::new の制約集めの段階で、この部分に要求されている型が判明している必要がある。そのために、式の制約集めをするときは、どのような型が期待されているかという補助的な情報をトップダウンに伝搬するようになっている。この期待型の情報は以下の列挙型で表現されている。

pub enum Expectation<'tcx> {
    NoExpectation,
    ExpectHasType(Ty<'tcx>),
    ExpectCastableToType(Ty<'tcx>),
    ExpectRvalueLikeUnsized(Ty<'tcx>),
}

つまり、以下の4種類のいずれかの期待型情報が与えられる。

特に情報はない。
型 T か、その部分型が要求されている。 (例: &'a str に対して &'b str)
型 T に明示的にキャストできる型が要求されている。 (例: u8 に対して u32)
可変長型 T (スライスまたはトレイトオブジェクト)自身か、それに読み替えられる型(配列または、トレイトを実装した型)が要求されている。

例えば、上の y の例では、

Box::new(Box::new([1, 2, 3])) には Box<Box<[_]>> の ExpectHasType 期待型情報が与えられている。
関数呼び出しの処理により、 Box::new([1, 2, 3]) には、 Box<[_]> の ExpectHasType 期待型情報が与えられている。
関数呼び出しの処理により、 [1, 2, 3] には、 [_] の ExpectRvalueLikeUnsized 期待型情報が与えられている。
1, 2, 3 には _ の ExpectHasType 期待型情報が与えられている。
[1, 2, 3] の型は [{integer}; 3] で確定する。
[1, 2, 3] は [_] に強制できないため Box::new([1, 2, 3]) は Box<[{integer}; 3]> となる。
Box<[1, 2, 3]> は Box<[_]> に強制できるため Box::new(Box::new([1, 2, 3])) は Box<Box<[{integer}]>> となる。

という順番でトップダウン→ボトムアップに型が推論される。

整数・浮動小数点数型の推論

整数と浮動小数点数のリテラルは以下のように推論される。

接尾辞で型が明示されているときは、それが採用される。 (例: 100i8)
整数リテラルに整数型が期待されている場合、浮動小数点数リテラルに浮動小数点数型が期待されている場合は、それが採用される。
整数リテラルに以下のような型が期待されている場合は (例: 32 as char)
- char → u8
- 生ポインタ、関数ポインタ、関数定義 → usize
それ以外の場合は、整数/浮動小数点数限定の特殊な型変数が生成される。 ({integer}, {float} と表示される)

これらの型変数に代入されなかった場合は、 i32 と f64 が採用される。

(C言語とは異なり)リテラルの中身は型に影響を与えない。 1000000000000 と書いてもデフォルトでは i32 に推論される。オーバーフローするときは警告される。

抽象化境界としての関数定義

ここまで見てきたように、Rustの型推論はHindley-Milnerベースでありながら、いくつかの理由から推論順序の影響を受けたり、型注釈が必要なことがあった。

これとは別に、RustがHindley-Milnerベースであるという印象を受けない理由がもう1つある。それは、OCamlなどとは異なり、Rustが関数の引数・戻り値の推論をしないという点である。(なお、クロージャーの引数・戻り値の推論は行う。)

ただしこれは、Rustが関数を抽象化境界とみなしているという意図的な理由がある。(The BookのLifetime Elisionの項目を参照)

これは推測だが、これとは別に、多相な関数の垣根を越えた型推論を避けることで複雑性を低減する意図もあるかもしれない。なおRustのクロージャーは単相である。

まとめ

Rustの型推論はHindley-Milner型推論ベースである。したがって後方の式や文の内容から手前の型が推論されることもある。しかし以下に挙げるようなRust独自の特徴をもつ。
型推論は原則として関数定義の中で閉じており、関数の引数型や戻り値型は推論されない。これは、関数を抽象化の境界とするための意図的なものである。この意味で「局所的」というのであれば間違いではない。
- ただし、let多相を含む型推論を避ける意図もあるかもしれない。
関数呼び出しや一部の演算子などは、その部分の制約を立てる段階で、型の一部分が判明している必要がある。この動作は推論順序の影響を受ける。
トレイトによりオーバーロード可能になっている関数や演算子は、射影型を使っている場合、ボトムアップにしか推論されない(式全体の型からオペランドが推論されない)。
型強制は、その時点で型のミスマッチが判明している場合にのみ発生するので、推論順序の影響を受ける。
その他、整数型と浮動小数点数型が特別扱いされていたり、生存期間に関して部分型付けをもつための特別処理があるなどの違いがある。

簡潔なQ

Rustの型推論の概略