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?

Chayim Friedman · Accepted Answer · 2023-10-27 10:03:17Z

2

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)
    }
}

answered Oct 27, 2023 at 10:03

Chayim Friedman

76.1k5 gold badges96 silver badges140 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

Eily Over a year ago

I do like that alternative version because of the explicit call to Copy when a reference is used. I can't use for an arbitrary ref depth though, it actually fails for &&u32. I think u32 and &u32 are going to cover most cases though, and although the error message isn't that helpful, it's actually pretty easy to fix the issue when using the trait by dereferencing the Iterator's Items

cdhowie · Accepted Answer · 2023-10-26 22:50:00Z

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.

Collectives™ on Stack Overflow

Implement a trait for Iterator over values or ref

Problem

Non working solutions

Working solution

2 Answers 2

1 Comment

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

Problem

Non working solutions

Working solution

2 Answers 2

1 Comment

Comments

Your Answer

Sign up or log in

Post as a guest

Related