Implement a trait for Iterator over values or ref

Question

I am trying to implement a trait that works for Iterator and Iterator<&u32> seamlessly, and while I did manage to find a solution I am not sure that is the best one, or even a good one. I have included my first two non working solutions for reference.

Problem

Implement the following trait for iterators over u32

trait First {
    fn first(self) -> Option<u32>;
}

Non working solutions

This first implementation :

impl<I> First for I
where I: Iterator<Item = u32> {
    fn first(mut self) -> Option<u32> {
        self.next()
    }
}

will work for vec![1, 2, 3].into_iter().first() (Iterator) but not for vec![1, 2, 3].iter().first() which will yield the following error:

error[E0599]: the method `first` exists for struct `Iter<'_, {integer}>`, but its trait bounds were not satisfied

using this second implementation:

impl<'a, I> First for I
where I: Iterator<Item = &'a u32> {
    fn first(mut self) -> Option<u32> {
        Some(*self.next()?)
    }
}

will fail this time on the into_iter() variant with the similar error:

error[E0599]: the method `first` exists for struct `IntoIter<{integer}>`, but its trait bounds were not satisfied

Note that in both cases the method is said to already exist, although the trait bounds are not satisfied. This means that it is note possible to use both definitions to have an overall working solution.

Working solution

This works:

impl<T, I> First for I
where
    I: Iterator<Item = T>,
    T: Borrow<u32>,
{
    fn first(mut self) -> Option<u32> {
        Some(*self.next()?.borrow())
    }
}

while this works, I'm not sure how (what I understand of) the semantics of the Borrow trait would justify using it for that usage. Also I'm not sure how this is actually compiled in the end, but it seems a little pointless in the case of into_iter() to take a reference to and owned integer, only to deference and copy it.

Am I missing something to make this work, or is it a mistake to even try something like that (it's not much of an issue for Copy, but for Clone types, having a trait calling .clone() even when the type is already owned is a waste or resources)? And is there any way to make the error message more explicit: to explicitly state that the iterator is expecting an owned value an not a reference, rather than the message about unsatisfied traits?

Answer 1

The implementations are not actually conflicting, since no type can implement Iterator with both Item = u32 and Item = &u32. The compiler is wrong here. This is issue #20400.

Using Borrow is one option. If you can't use it, for example because you need different behaviors for different Item types, or because you want to support any reference level (&&&&&u32), you can use a workaround that is not convenient but works. The idea is to pass the responsibility of the impl to the associated type. The compiler cannot confirm that impl Iterator<Item = u32> and impl Iterator<Item = &u32> are distinct types, but it can confirm that u32 and &u32 are:

trait First {
    fn first(self) -> Option<u32>;
}

trait IteratorItem {
    fn first(iter: impl Iterator<Item = Self>) -> Option<u32>;
}

impl IteratorItem for u32 {
    fn first(mut iter: impl Iterator<Item = Self>) -> Option<u32> {
        iter.next()
    }
}

impl IteratorItem for &'_ u32 {
    fn first(mut iter: impl Iterator<Item = Self>) -> Option<u32> {
        iter.next().copied()
    }
}

impl<I> First for I
where
    I: Iterator,
    I::Item: IteratorItem,
{
    fn first(self) -> Option<u32> {
        I::Item::first(self)
    }
}

Answer 2

The implementation constraining T: Borrow<u32> is probably what you want. This is one of the use cases that trait was designed for.

Also I'm not sure how this is actually compiled in the end, but it seems a little pointless in the case of into_iter() to take a reference to and owned integer, only to deference and copy it.

This will be handled during monomorphization. When the compiler instantiates the version for T=&u32 it will almost certainly inline the borrow() call and eliminate the indirection entirely.

Alternatively, maybe you don't actually need a u32, maybe you just need to be able to do something specific with the values. If you're doing addition, you could bound on T: std::ops::Add<U> for some U, for example. It's not clear if this would be a suitable solution since your question lacks the detail of your higher-level goal.