Rustにおける再帰的/余再帰的なトレイト選択/トレイト履行

Rustでは以下のようなプログラムはコンパイルエラーになる。

struct List<X>(Option<Box<(X, List<X>)>>);

// 通常は X: Clone を仮定するが、あえて Option<Box<(X, List<X>)>>: Clone としてみる
impl<X> Clone for List<X> where Option<Box<(X, List<X>)>>: Clone {
    fn clone(&self) -> Self {
        List(self.0.clone())
    }
}

fn main() {
    let x = List::<i32>(None).clone();
}

このとき、 List<i32>: Clone をするために以下のような推論が行われる。

List<i32>: Clone は上で定義されている impl を使うことができる。
そのためには where 節にある Option<Box<(i32, List<i32>)>>: Clone を充足する必要がある。
これには impl<T: Clone> Clone for Option<T> を使うことができる。
そのためには where 節にある Box<(i32, List<i32>)>: Clone を充足する必要がある。
これには impl<T: Clone> Clone for Box<T> を使うことができる。
そのためには where 節にある (i32, List<i32>): Clone を充足する必要がある。
これには impl<T0: Clone, T1: Clone> Clone for (T0, T1) を使うことができる。
そのためには where 節にある i32: Clone と List<i32>: Clone を充足する必要がある。
i32: Clone は impl Clone for i32 を使うことができる。
List<i32>: Clone を解決する必要があるが、これは元の問題と全く同じであるため失敗とみなす。

むろんこれは、 Clone の実装の where 節に普通使わない書き方を採用したからであり、 X: Clone とすればこのような再帰的な解決は不要になる。

例外として、余帰納的なマッチング (coinductive matching)が許されるケースがある。それは以下のケースである。

検出されたサイクル上に登場する全てのトレイトが既定実装を持つとき。

例えば、先ほどの例で出てきた List<i32> が Send かどうかを調べようとすると、以下のような推論が行われる。

List<i32>: Send には他の候補はないため、既定実装候補が採用される。
List にはフィールドが一つあるため、 Option<Box<(i32, Lists<i32>)>>: Send を充足する必要がある。
Option<Box<(i32, Lists<i32>)>>: Send には他の候補はないため、既定実装候補が採用される。
Option にはフィールドが一つあるため、 Box<(i32, Lists<i32>)>: Send を充足する必要がある。
Box<(i32, Lists<i32>)>: Send には他の候補はないため、既定実装候補が採用される。
Box にはフィールドが一つあるため、 Unique<(i32, Lists<i32>)>: Send を充足する必要がある。
Unique<(i32, Lists<i32>)>: Send は impl<T: Send + ?Sized> Send for Unique<T> を使うことができる。
そのためには where 節にある (i32, Lists<i32>): Send を充足する必要がある。
(i32, Lists<i32>): Send には他の候補はないため、既定実装候補が採用される。
(_, _) にはフィールドが二つあるため、 i32: Send と Lists<i32>: Send を充足する必要がある。
i32: Send には他の候補はないため、既定実装候補が採用され、条件なしで充足される。
Lists<i32>: Send を解決する必要があるが、これは元の問題と全く同じである。通常ならばこれは失敗となるが、余帰納的なマッチングの条件を満たしているため、その場で成功とみなす。

なお、Rust 1.19.0時点では、この制約はトレイト履行(fulfillment)の場合にのみ適用され、トレイト選択(selection)時には余帰納的かどうかに関わらず再帰的なマッチングは認められていた。現時点での最新版では、#42840 の一部として、同じ制約がトレイト選択でも使われるようになっている。そのため、stableとnightlyでは以下のように表示されるエラーが異なっている。

stable

error[E0275]: overflow evaluating the requirement `List<i32>: std::clone::Clone`
  --> src/main.rs:11:31
   |
11 |     let x = List::<i32>(None).clone();
   |                               ^^^^^

nightly

error[E0599]: no method named `clone` found for type `List<i32>` in the current scope
  --> src/main.rs:11:31
   |
11 |     let x = List::<i32>(None).clone();
   |                               ^^^^^
   |
   = note: the method `clone` exists but the following trait bounds were not satisfied:
           `std::option::Option<std::boxed::Box<(i32, List<i32>)>> : std::clone::Clone`
   = help: items from traits can only be used if the trait is implemented and in scope
   = note: the following trait defines an item `clone`, perhaps you need to implement it:
           candidate #1: `std::clone::Clone`