rustで型推論できる場合とできない場合の違いが知りたい

前提・実現したいこと

rustで次のプログラムをコンパイルしたところ、型推論エラーが発生しました

let mut a = None;
let mut b = vec![vec![None; 10]; 10];

if let Some(i) = a {
    b[i][0] = Some(0);
}
a = Some(0);

error[E0282]: type annotations needed
 --> src/main.rs:8:9
  |
8 |         b[i][0] = Some(0);
  |         ^^^^ cannot infer type
  |
  = note: type must be known at this point

一方、こちらのコードでは型推論エラーは発生しませんでした

let mut a = None;
let mut b = vec![None; 10];

if let Some(i) = a {
    b[i] = Some(0);
}
a = Some(0);

また、1つ目のコードでbにある程度ヒントを与えた状態でも同じエラーが出ました

let mut b: Vec<Vec<Option<_>>> = vec![vec![None; 10]; 10];

2つのコードでなぜ違いが出るのかを知りたいです

補足情報（FW/ツールのバージョンなど）

Rust Playground (1.43.1) で確認してます

行動規範の内容に同意します

回答1件

ベストアンサー

端的に言うと、

b はVecであることがわかっているので b[i] までは推論できる
b[i] はVecかどうか確定していないので b[i][0] の解決で失敗する (この時点では i がスカラーインデックスとは限らず b[0..1] のような表記である可能性が残されている)

ということになります。以下詳しい説明です。

RustはHindley-Milnerベースの型推論を採用しているので原則としてコードの順番に逆行する型推論が可能です。しかし純粋なHindley-Milner型推論とは異なり、「型による条件分岐」によって型を決定しなければいけない箇所があり、そこで推論に失敗することがあります。わかりやすいのがメソッド構文を使った場合です。

rust
1fn main() {
2    let mut x = Default::default();
3    // x.abs() を解決するにはxの型がある程度わかっている必要がある
4    // しかしこの時点でxの型は未定なので、コンパイルエラーになる
5    dbg!(x.abs());
6    x = 0_i32;
7}

メソッド構文ではautodereferenceとオーバーロードの解決のためにレシーバの型を解決する必要があります。たとえばここでは x の型として i32, i64, &i32, &&i32, &&&i32 などが考えられるため、この可能性を絞るために型がある程度わかっている必要があります。

ここで「ある程度」と言っているのは、ジェネリクス引数までは解決しなくてもよいことが多いからです。たとえば、以下のコードはコンパイルが通ります。

rust
1fn main() {
2    let mut vec = vec![];
3    // この時点でvecの型は Vec<_> までしか確定していないが、pushの解決をする上ではそれで十分
4    vec.push(Default::default());
5    vec.push(1);
6}

push メソッドのレシーバとして Vec<_>, &mut Vec<_>, OsString, &mut OsString などが考えられますが、この分岐を決定するには Vec<_> までわかっていればよく Vec の要素型まで確定する必要はありません。

さて、問題の

rust
1b[i][0] = Some(0);

では、 b は Vec<Vec<Option<_>>> であることまでわかっていて、 a は Option<_> までわかっています。以下わかりやすくするために型変数名を割り当てて Vec<Vec<Option<?B>>>, Option<?A> と呼ぶことにします。

Rustの配列インデックス構文は「レシーバをautodereferenceし、Index/IndexMutを適用」したものとして扱われます。今回はレシーバ型のVecがIndexを直接実装しているので、autodereferenceは行われず

b[i]: <Vec<Vec<Option<?B>>> as Index<?A>>::Output

であることがこの時点で確定できます。この <Vec<Vec<Option<?B>>> as Index<?A>>::Output (射影型) も単純型システムには出てこない特殊な概念で、Rustではトレイト実装が一意に決まった時点で展開することになっています。ではこの場合はどうでしょうか。VecのIndex実装には以下のひとつしかありません。

rust
1impl<T, I> Index<I> for Vec<T>
2where
3    I: SliceIndex<[T]>
4{
5    type Output = <I as SliceIndex<[T]>>::Output;
6}

つまり、先ほどの射影型はその場で展開して

b[i]: <?A as SliceIndex<[Vec<Option<?B>>]>>::Output

に変形することが可能です。しかしまた射影型になってしまいました。これはどうでしょうか。SliceIndexの関連する実装には以下があります。

rust
1impl<T> SliceIndex<[T]> for usize {
2    type Output = T;
3}
4impl<T> SliceIndex<[T]> for Range<usize> {
5    type Output = [T];
6}
7impl<T> SliceIndex<[T]> for RangeFrom<usize> {
8    type Output = [T];
9}
10impl<T> SliceIndex<[T]> for RangeFull {
11    type Output = [T];
12}
13impl<T> SliceIndex<[T]> for RangeInclusive<usize> {
14    type Output = [T];
15}
16impl<T> SliceIndex<[T]> for RangeTo<usize> {
17    type Output = [T];
18}
19impl<T> SliceIndex<[T]> for RangeToInclusive<usize> {
20    type Output = [T];
21}

?A が確定していないので、これらのうちどの実装を採用するべきかわかりません。この場合 <?A as SliceIndex<[Vec<Option<?B>>]>>::Output はこのままで推論を進めることになります。

さて、 b[i] を解決したら、次は b[i][0] を解決する必要があります。ここでは b[i] のdereferenceを解決する必要があります。

ところが、b[i] の型である <?A as SliceIndex<[Vec<Option<?B>>]>>::Output が実際はどういう型になるのか、この時点ではわかりません。 (ちゃんと条件を見れば Vec<Option<?B>> と [Vec<Option<?B>>] のどちらかということはわかるわけですが、Rustのルールではこういう状態はなく、「～まで確定している」か「確定していない」の2択として扱われます) そのため何回dereferenceすればいいかもわからないということになり、ここで推論が失敗してしまいます。

さて、もう1つの問題のないソースコード

rust
1b[i] = Some(0);

ではどうでしょうか。今回は b の型が Vec<Option<?B>> ということにすると、 b[i] の型は <?A as SliceIndex<[Option<?B>]>>::Output までわかることになります。代入構文ではautodereferenceは関係してこないので、単に <?A as SliceIndex<[Option<?B>]>>::Output と Option<{integer}> を単一化すればいいわけです。ただ射影型の単一化は射影型が解決されるまでは進められないので、この制約はそのまま覚えておくことになります。すると次に

rust
1a = Some(0);

があるので、ここで ?A が {integer} であることが確定します。すると b[i] の型であった

<?A as SliceIndex<[Option<?B>]>>::Output

は展開して

<{integer} as SliceIndex<[Option<?B>]>>::Output

とすることができます。改めてSliceIndexの関連する実装を見ると、 usize に対する実装しかありえないことがわかります。 (この部分の 0 がusize型であることも同時に決まります)

<usize as SliceIndex<[Option<?B>]>>::Output

これは展開可能で

Option<?B>

になります。先ほど覚えておいた単一化の制約は Option<?B> = Option<{integer}> なので、 ?B は {integer} だということがわかりました。 (この {integer} は他に制約がないので、型推論の最終段階でデフォルトである i32 になります)

投稿2020/05/30 02:02