Can I implement a trait for both [T] and Vec<T> at the same time?

I have the following code (playground):

trait Trait {
    fn do_stuff(&self) -> bool;
}

impl<T: AsRef<str>> Trait for [T] {
    fn do_stuff(&self) -> bool {
        helper(self)
    }
}

impl<T: AsRef<str>> Trait for Vec<T> {
    fn do_stuff(&self) -> bool {
        helper(self)
    }
}

fn helper<T: AsRef<str>>(array: &[T]) -> bool {
    // Create an iterator and do useful things with it,
    // eventually returning a boolean value.
    // I don't think details matter here.
    true
}

It works fine, but the two implementations are exactly identical and the only reason for helper's existence is to avoid the code duplication. I would like to know if there is a nice way to fold them into a single implementation.

My first attempt was the following (playground):

impl<T: AsRef<str>, U: AsRef<T>> Trait for U {
    fn do_stuff(&self) -> bool {
        helper(self.as_ref())
    }
}

But the compiler complains about an unconstrained type T. Question 1: why is it considered unconstrained, given that T is still used as a bound to U? And why could it be a problem in this case?

Since helper() only works on an iterator, I thought about implementing the trait for IntoIterator instead:

impl<T: AsRef<str>, I: IntoIterator<Item=T>> Trait for I {
    fn do_stuff(&self) -> bool {
        helper(self.into_iter())
    }
}

fn helper<T: AsRef<str>>(mut iter: impl Iterator<Item=T>) -> bool {
    // Use the iterator and do useful things with it,
    // eventually returning a boolean value.
    true
}

But this doesn't compile, because I would need a non-consuming version of IntoIterator, which doesn't seem to exist. Question 2: why isn't iter() a trait implementation, like into_iter()?

Finally, another option would be to implement the trait for Iterator and make the trait consume its self parameter, but this changes the usage pattern: callers first have to call .iter() (for example), which is less discoverable.

Question 3: is there another way to achieve this? I don't really mind keeping the original code, but it's a nice learning exercise for me :slight_smile:

The issue is that this may specify multiple behaviors for a single object, and the compiler can’t tell which should be used. For example:

struct A { /* ... */ };
struct B { /* ... */ };
struct Both { a: A, b: B };

impl AsRef<str> for A { /* ... */ }
impl AsRef<str> for B { /* ... */ }
impl AsRef<A> for Both { /* ... */ }
impl AsRef<B> for Both { /* ... */ }

Should both.do_stuff() use A or B?

By convention, the T.iter() method is equivalent to calling (&T).into_iter. If your trait consumes a Copyable IntoIterator, then it the compiler shoulde able to call it with auto-referencing:

impl<'a, T: AsRef<str>, I: IntoIterator<Item=&'a T> + Copy> Trait for I {
    fn do_stuff(self) -> bool {
        helper(self.into_iter())
    }
}

This implements the trait on the reference type instead of the collection itself, which may be undesirable. Alternatively, you can use higher-rank trait bounds (HRTBs) to require that the reference implements IntoIterator:

impl<T: AsRef<str>, I> Trait for I
where for<'a> &’a I: IntoIterator<&'a T> {
    fn do_stuff(&self) -> bool {
        helper(self.into_iter())
    }
}

Another choice to avoid the unconstrained type parameter issue is Deref<Target=[T]>. Because no object can have more than one Deref implementation, there’s no possibility of the conflicting case I showed above.

5 Likes

Thank you! The HTRB solution is beautiful.

Just a follow up on question 2: is there is a technical reason not to have a trait for iter()? If not, does that mean that future Rust versions might eventually add this as syntactic sugar?

Moving existing method to the trait will AFAIK be always a breaking change. The reason is simple: for no_std cases, there's no implicit std prelude, and this trait must be explicitly pulled in, so every code using iter will instantly stop to compile.

2 Likes

In addition to what @Cerberuser said, it's not currently possible/desirable to make a trait that provides iter. To do it properly, you need GATs:

trait Iterable {
    type Iter<'a>;
    fn iter(&'a self) -> Iter<'a>;
}

This is not valid Rust today. Iter needs to be generic because it can borrow from self (after all, that's the whole point). When we get GATs it will be possible to generalize iter.

You don't need GATs if you put a lifetime in the trait. Rayon has IntoParallelRefIterator and IntoParallelRefMutIterator, and you can do the same for Iterator (playground):

trait IntoRefIterator<'a> {
    type Iter: Iterator<Item = Self::Item>;
    type Item: 'a;

    fn iter(&'a self) -> Self::Iter;
}

impl<'a, I: 'a + ?Sized> IntoRefIterator<'a> for I
where
    &'a I: IntoIterator,
{
    type Iter = <&'a I as IntoIterator>::IntoIter;
    type Item = <&'a I as IntoIterator>::Item;

    fn iter(&'a self) -> Self::Iter {
        self.into_iter()
    }
}

Then I: for<'a> IntoRefIterator<'a> is nearly the same as for<'a> &'a I: IntoIterator, but rust#20671 makes the latter awkward to propagate.

There is an implicit core prelude too, but #![no_implicit_prelude] disables all preludes.

I wouldn't move the existing inherent methods anyway, just shadow them in the new trait for generic use. When there's ambiguity between trait and inherent methods, the latter is used.

This is technically true, but it's not as general as it could be with GATs, and the compiler's ability to reason about universal predicates isn't quite what it should be. @LukasKalbertodt's article Solving the Generalized Streaming Iterator Problem without GATs calls this "Workaround A". It works, but it's not great.

Yeah, the lifetime in the trait is a trade-off, not ideal. We decided it was important enough to do this in Rayon though, because we don't have the option of adding inherent par_iter() methods to external types, especially the standard collections. I think it's rare to actually use IntoParallelRefIterator in a generic way -- it's more often just used like an extension trait.