Rust 関数呼び出しの期待型の伝搬

以前の記事で説明したように、Rustでは型強制や整数リテラルなどの特殊な型推論をシームレスに行うために期待型という概念を導入している。

この期待型はトップダウンに伝搬されるが、先ほどの記事で挙げた例

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
}

では Box::new 関数の外側から内側に向けて期待型の伝搬が行われている。

これは Box::new に限ったことではなく、一般にどのような関数でもこのような伝搬が行われる。この計算をしているのが expected_inputs_for_expected_outputs メソッドである。

これは大まかに言うと次のようなことをしている。

関数の引数型と戻り値型を生成する。ジェネリクスにより未確定の部分には型推論変数を入れる。例えば、 Box::new の場合、引数型は ?T で戻り値型は Box<?T> である。
型推論環境のスナップショットを生成する。
関数の戻り値型と、関数呼び出しの期待型で、単一化を行う。例えば期待型が Box<Box<[?X]>> なら、単一化により ?T := Box<[?X]> が生成される。
引数型の型推論変数を展開する。今回は ?T := Box<[?X]> が判明しているため、引数型は ?T から Box<[?X]> にリファインされる。
展開結果を、引数の期待型として覚えておく。
型推論環境のスナップショットをロールバックする。

期待型はあくまでヒントであるため、期待型とは異なる型が推論されることはある。例えば、上の例ではまず Box::new([1, 2, 3]) に Box<[?X]> が期待されているという情報から [1, 2, 3] に [?X] が期待されているという情報が生成される。このような型強制はできないため失敗し、 Box::new([1, 2, 3]) の型は Box<[{integer}; 3]> になる。そこで翻ってこの期待型 Box<[?X]> と比較すると、この時点で型強制が可能であるため、強制後の型は Box<[{integer}]> となる。

このとき、期待型の伝搬のためにまず ?T := [?X] がユニフィケーションで生成されるが、これはロールバックにより消滅する。中の型が確定してからあらためてユニフィケーションが行われ、このときは ?T := [{integer}; 3] となる。

このように期待型の伝搬の過程では誤った単一化子が生成されることがあるが、期待型の処理ごとにロールバックすることで競合を回避している。