Why are implementations of Iterator and Iterator conflicting?

Question

This code fails to compile:

pub trait ToVec<T> {
    fn to_vec(self) -> Vec<T>;
}

impl<I, T> ToVec<T> for I
where
    I: Iterator<Item = T>,
{
    fn to_vec(self) -> Vec<T> {
        self.collect()
    }
}

impl<'a, I, T> ToVec<T> for I
where
    I: Iterator<Item = &'a T>,
    T: Clone,
{
    fn to_vec(self) -> Vec<T> {
        self.cloned().collect()
    }
}

Error:

error[E0119]: conflicting implementations of trait `ToVec<_>`:
  --> src/lib.rs:14:1
   |
5  | / impl<I, T> ToVec<T> for I
6  | | where
7  | |     I: Iterator<Item = T>,
8  | | {
...  |
11 | |     }
12 | | }
   | |_- first implementation here
13 | 
14 | / impl<'a, I, T> ToVec<T> for I
15 | | where
16 | |     I: Iterator<Item = &'a T>,
17 | |     T: Clone,
...  |
21 | |     }
22 | | }
   | |_^ conflicting implementation

From what I understand, when a given type I implements Iterator, I::Item can only have one specific type, so it cannot satisfy both implementations.

Is this a limitation of the compiler or is my reasoning incorrect? If so, please provide an example which satisfies both impls.

Answer 1

I believe this is issue #20400, Can't write non-overlapping blanket impls that involve associated type bindings. To summarize, the impls are in fact non-overlapping, but teaching the compiler to recognize that would introduce a form of negative reasoning, which is a major departure from how the trait solver currently works. An RFC was written to fix the issue, but postponed partly due to ambiguity about what it means for two types to overlap.

It seems likely this issue will be revisited and fixed eventually, but it may take some time.

In the mean time, you might write a workaround based on adding a type parameter to Trait, as in my answer to Can I avoid eager ambiguity resolution for trait implementations with generics? (Although in your case, since your impls never actually overlap, you never have to use the turbofish to pick an impl; the compiler should always just figure it out.)

Answer 2

Roughly speaking, an iterator with Item = &X would satisfy both:

• The first one with T == &X => could result in a Vec<&X>
• The second one with T == X => could result in a Vec<X>

Maybe specialization (nightly) could help, but I am not sure.

Answer 3

The set of types represented by the generic type parameter T is a superset of the set of types represented by the generic type parameter &T. They are not disjoint. Everything in &T is also in T hence the conflicting implementations message.

Minimal example:

trait Trait {}

impl<T> Trait for T {}

impl<T> Trait for &T {} // compile error

Throws:

error[E0119]: conflicting implementations of trait `Trait` for type `&_`:
 --> src/lib.rs:5:1
  |
3 | impl<T> Trait for T {}
  | ------------------- first implementation here
4 | 
5 | impl<T> Trait for &T {} // compile error
  | ^^^^^^^^^^^^^^^^^^^^ conflicting implementation for `&_`