Blanket impls for Iterable (GAT) covering owned collections and references

[MSR]

I was playing around with the Iterable trait using the newly stabilised GATs on nightly.

Here's the definition of the trait, from the GAT initiative:

trait Iterable {
    type Item<'collection>
    where
        Self: 'collection;

    type Iterator<'collection>: Iterator<Item = Self::Item<'collection>>
    where
        Self: 'collection;

    fn iter<'c>(&'c self) -> Self::Iterator<'c>;
}

I figured it should be possible to write a blanket impl for Iterable that covers I when for<'a> &'a I: IntoIterator. I can do that, and it works for owned collections like Vec or VecDeque:

impl<I> Iterable for I
where
    for<'a> &'a I: IntoIterator,
{
    type Item<'collection> = <&'collection I as IntoIterator>::Item
    where
        Self: 'collection;

    type Iterator<'collection> = <&'collection I as IntoIterator>::IntoIter
    where
        Self: 'collection;

    fn iter<'c>(&'c self) -> Self::Iterator<'c> {
        self.into_iter()
    }
}

But this doesn't work for &Vec<T> or &[T]. I can make a blanket impl for I when I: Copy + IntoIterator that will make those cases work, but doesn't cover the owned cases. Likewise, I can just concretely impl Iterable for &[T]. However, both of those solutions lead to conflicting implementations with the for<'a> &'a I: IntoIterator impl, where either upstream of downstream crates may cause breakage.

My question, therefore: Is there any way to implement the Iterable trait so that it will work for both owned collections (e.g. Vec, VecDeque, etc.) without manually implementing all of them, as well as for references to these and slices?

(Playground.)

[quinedot]

Here, I've applied some changes:

-impl<I> Iterable for I
+// Consider `I = [_]` -- `[_]` is not `Sized`
+impl<I: ?Sized> Iterable for I

-fn take_iterable<I>(_: I)
+// Similar -- note that this takes a reference now
+fn take_iterable<I: ?Sized>(_: &I)
 where
     I: Iterable

-    take_iterable(Vec::<i32>::default());
-    take_iterable(std::collections::VecDeque::<i32>::default());
+    // Have to pass in references
+    take_iterable(&Vec::<i32>::default());
+    take_iterable(&std::collections::VecDeque::<i32>::default());
+    // No change, you were already passing in a reference
     take_iterable(Vec::<i32>::default().as_slice());

I would argue that this is the correct pattern. The only thing you can do with an Iterable is call reference-taking methods -- if you wanted to consume something, you would have used IntoIterator. Howerver, it is true that the function signature is longer and that callers may have to add a reference.

What if you wanted to allow that? Callers probably don't want to give away ownership, but if they're okay with it, it would be less typing. ^[1] Let's try this one again:

fn foo<I: Iterable>(_: I) { /* ... */ }
// ...
    // No taking a &
    take_iterable(Vec::<i32>::default());
    take_iterable(std::collections::VecDeque::<i32>::default());
    // Still unchanged
    take_iterable(Vec::<i32>::default().as_slice());

It doesn't work. We've implemented Iterable for the unsized [_], which is correct. But we haven't implemented it for &[_].

• The generic approach conflicts again.
• Even if we restrict it to slices.
• And even non-generically, we would have to own the type.

So you can't get that ergonomics back, and function writers will need to use the ?Sized and take & pattern to properly support Iterable implementors.

Now, personally I think this is fine, because taking ownership is unnecessary on the receiving end (and ?Sized bounds don't bother me). Additionally, you usually don't want to give away ownership if you don't want to, and if you could, it might mean you clone unnecessarily due to a compiler hint or general lack of understanding. But it is less ergonomic if you don't care about your ownership, because we don't have autoref here; there's also a risk function writers will use the simpler, but incorrect, bounds.

---

As it happens, this has come up before. Consider the AsRef trait: the entire idea is conversion between reference types. The proper way (IMO) to use it would thus be like so:

fn open<P: AsRef<Path> + ?Sized>>(path: &P) { /* ... */ }

But because people find this unergonomic or are afraid people will be confused by ?Sized, we instead tend to see ^[2]:

fn open<P: AsRef<Path>>(path: P) { /* ... */ }

And unfortunately this opens up the speed-bump of accidentally passing in a String and giving away ownership of it (for example), or the performance hit of cloning unnecessarily, when open never needed the ownership in the first place. It couldn't need it -- there's nothing in the bounds that lets it do anything with path except convert a reference to it! (Granted, it is more ergonomic when you actually don't care if you give away your ownership or not.)

But wait, how does it work to pass in a &Path to open<P: AsRef<Path>>(path: P)? There must be a conversion from &&Path (two levels of reference) to &Path (one level). And there is:

impl<T, U> AsRef<U> for &T where
    T: AsRef<U> + ?Sized,
    U: ?Sized, 

You can pass in an arbitrarily nested &&&Thing and convert to &OtherThing ... provided there is a base AsRef<OtherThing> for Thing. This generic implementation plus impl AsRef<Path> for Path means that &Path implements AsRef<Path>, so we can convert the &&Path to a &Path. Whew!

However, with this generic "lifting", there cannot be a blanket AsRef<T> for T where T: ?Sized. So the trade-off is that types have to opt-in to being AsRef<Self>.

In your case, it's the opposite -- you want to opt all these types into being Iterable automatically, but that means you can't get the "lifting" over arbitrarily nested references.

And again, I think this is actually more correct, despite requiring more typing. It does put a burden on function writers to "get it right" (use ?Sized and take a reference). If they don't, it's a breaking change to fix it.

---

1. On the other hand, they might think they have to give up ownership, and clone something . ↩︎

2. including in the standard library! ↩︎

[MSR]

Very interesting, thank you very much for a great answer. Adding ?Sized and passing references makes a lot of sense. Nice connection with the AsRef<Path> bound also!