IntoIterator/Iterate by ref (non-consuming) trait bound

help
5

Bonus round!

After I posted that last comment [1], I thought "ugh, well, carrying that for<> bound around is still annoying. Let's get rid of that too."

But as it turns out, doing so is pretty involved, and explaining it all ends up getting rather into the weeds of Rust. So this is going to get into techniques that I wouldn't expect beginners (or intermediates?) to think of. Since I bothered to write it up though, I'm still going to post it :slightly_smiling_face: You might want to skip it altogether, or just skip to the end result and see if you want to use it. But you can also save the rest to revisit later.

Anyway, looking at the foo example, that bound is still sort of annoying, isn't it? Let's try to improve that.

The challenge is that only supertrait bounds get carried around implicitly. That is, if you write this:

trait Trait where Self: OtherTrait {}
// aka: trait Trait: OtherTrait {}

Then when you have a where T: Trait bound, you get T: OtherTrait as well, implicitly. However, this doesn't work for "where clauses" generally, only bounds on Self directly (supertraits). So when you have

trait MyAwesomeIteratorStuff where for<'any> &'any Self: OtherTrait {}

The for<'any> bound has to be repeated, like when the compiler yelled at you for not carrying the struct bound around. (The term for both of these things are "implied bounds", and Rust may get more implied bounds in the future, but we don't have them now.)

OK, so that's the context. If we're going to improve this so we don't have to write out the for<'any> bound, we need to have the bound on Self. We want something like this:[2]

pub trait Iterable: for<'any> MyRefsIntoIteratorImpl<'any> {
    fn iter(&self) -> <Self as MyRefsIntoIteratorImpl<'_>>::IntoIter;
}

That is, we need a trait that we implement for T, that ties it to &T's implementation of IntoIter. Let's call it NonconsumingIter instead, and make it look like IntoIterator otherwise. I don't think you really need the Item here though, so I've left it out. [3]

pub trait NonconsumingIter<'a> {
    type IntoIter: Iterator;
}

We want to implement this for T when &'a T can be turned into an iterator. This will allow us to "find" a reference's iterator type from T itself. (T still doesn't have a lifetime, but the implementation of NonconsumingIter<'_> for T does -- this is how we're able to define an iterator-per-lifetime for T.)

impl<'a, T: ?Sized> NonconsumingIter<'a> for T
where
    &'a T: IntoIterator
{
    type IntoIter = <&'a T as IntoIterator>::IntoIter;
}

Uh oh, the compiler is mad. Hmmm... oh, it doesn't like our bound on &'a T, because maybe we're dealing with impl NonconsumingIter<'static> for &'short T or something. Let's just make it happy for now [4].

-impl<'a, T: ?Sized> NonconsumingIter<'a> for T
+impl<'a, T: ?Sized + 'a> NonconsumingIter<'a> for T

And then we implement the Iterable trait for everything that meets the bounds...

impl<T: ?Sized> Iterable for T
where
    for<'any> &'any T: IntoIterator
{
    fn iter(&self) -> <Self as NonconsumingIter<'_>>::IntoIter {
        self.into_iter()
    }
}

Dang, it's mad again. Also, the help doesn't make any sense, there's nowhere to add a 'a here. Turns out, it's confused in a similar way to when it suggested 'static, but in the other direction. Since we want the supertrait implemented for all lifetimes, T needs to be valid for all lifetimes... ah ha!

-impl<T: ?Sized> Iterable for T
+impl<T: ?Sized + 'static> Iterable for T

Alright, that worked... but time for another aside. There's actually a hackier, but better, way to go. It may not matter for this use case, but sometimes it does. We're going to do this instead:

-pub trait NonconsumingIter<'a> {
+pub trait NonconsumingIter<'a, _LifetimeHack = &'a Self> {
[...]
-impl<'a, T: ?Sized + 'a> NonconsumingIter<'a> for T
+impl<'a, T: ?Sized> NonconsumingIter<'a> for T
[...]
-impl<T: ?Sized + 'static> Iterable for T
+impl<T: ?Sized> Iterable for T

Why? The main reason is to get rid of that 'static bound. Probably it doesn't matter for your particular use-case anyway, so

let's hide the longer explanation by default.

It's possible to have an unbounded implementation on a non-'static type:

pub struct AnotherAside<'a> {
    inner: &'a Option<u32>
}

impl<'a> IntoIterator for &AnotherAside<'a> {
//...
}

This could work with our implementations, but doesn't due to the 'static bound. But if you change to the commented versions, you'll see it then compiles. How does it work?

pub trait NonconsumingIter<'a, _LifetimeHack = &'a Self> {
//                            ^^^^^^^^^^^^^^^^^^^^^^^^^

That's a default type parameter. Because it's a default, if you don't mention that parameter anywhere, it will default to being &'a Self; that's the first part of the trick. The second part is that the presence of &'a Self in the trait signature itself makes it implicit that Self: 'a. This means that even here:

pub trait Iterable: for<'any> NonconsumingIter<'any> {

Self doesn't have to be 'static, because this is really short for

pub trait Iterable: for<'any> NonconsumingIter<'any, &'any Self> {

And so the for<> bound is really something like the (otherwise inexpressible)

for<'any where Self: 'any> NonconsumingIter<'any> {

And thus the for<> bound can hold, even when Self is not 'static.

Whew! Well, I did say this would get into the weeds.

Alright, where were we. It looks like we've managed to define Iterable alright, let's see if we can use it. Let's throw out the iter method we wrote before -- we'll get it from being Iterable instead. For the implementations to apply, we need to implement IntoIterator for &MyIterableWrapper like before -- we want that functionality anyway. Let's just throw in that code from before then, and see how things have improved.

fn foo<T>(miw: MyIterableWrapper<T>)
where
    MyIterableWrapper<T>: Iterable
{
    for _ in miw.iter() {       
    }
}

Hey, it works! But uh, that bound doesn't really look all that much improved. What we really want is something like

-fn foo<T>(miw: MyIterableWrapper<T>)
-where
-    MyIterableWrapper<T>: Iterable
-{
+fn foo<T: Iterable>(miw: MyIterableWrapper<T>) {

Which should follow from the blanket implementations anyway right? And as we see...

error[E0599]: the method `iter` exists for struct `MyIterableWrapper<T>`, but its trait bounds were not satisfied

Um, wait, why not? Weird, our implementation of IntoIterator for references to our struct should make the implementations apply. Well look, we really care more about those than the iter method anyway, right?

fn foo<T: Iterable>(miw: MyIterableWrapper<T>) {
    for _ in &miw {       
    }
}

:arrow_right:

error[E0275]: overflow evaluating the requirement `&_: IntoIterator`
   |
   = help: consider increasing the recursion limit by adding a `#![recursion_limit = "256"]` attribute to your crate (`playground`)
note: required because of the requirements on the impl of `IntoIterator` for `&MyIterableWrapper<_>`
  --> src/main.rs:43:13
   |
43 | impl<'a, T> IntoIterator for &'a MyIterableWrapper<T> 
   |             ^^^^^^^^^^^^     ^^^^^^^^^^^^^^^^^^^^^^^^
   = note: 127 redundant requirements hidden
   = note: required because of the requirements on the impl of `IntoIterator` for 
`&MyIterableWrapper<MyIterableWrapper<...and on and on...`

Uh... uh oh. We've sent the compiler into a recursive loop. This must be why it couldn't find the Iterable implementation either. We need to break the recursion somehow...

OK, how about this. We rely on T itself being Iterable; maybe that will be enough. It directly reflects the bounds we want to use on our functions, anyway.

impl<'a, T: Iterable> IntoIterator for &'a MyIterableWrapper<T> {
    type IntoIter = <T as NonconsumingIter<'a>>::IntoIter;
    type Item = <Self::IntoIter as Iterator>::Item;
    // ^^ Aha!  It doesn't look so bad in this form.
    fn into_iter(self) -> Self::IntoIter {
        self.inner.iter()
    }
}

Aaaaaaand.... oh hey it works.[5]

Final version all in one place 
// A GAT-like substitute to transfer the lifetime from `&T` to `T`
pub trait NonconsumingIter<'a, _LifetimeHack = &'a Self> {
    type IntoIter: Iterator;
}

// Our main trait which relies on it
pub trait Iterable: for<'any> NonconsumingIter<'any> {
    fn iter(&self) -> <Self as NonconsumingIter<'_>>::IntoIter;
}

// Blanket implement for everything that matches our use case
impl<'a, T: ?Sized> NonconsumingIter<'a> for T
where
    &'a T: IntoIterator
{
    type IntoIter = <&'a T as IntoIterator>::IntoIter;
}

// Blanket implement for everything that meets the bounds period
impl<T: ?Sized> Iterable for T
where
    for<'any> &'any T: IntoIterator
{
    fn iter(&self) -> <Self as NonconsumingIter<'_>>::IntoIter {
        self.into_iter()
    }
}

// Implement `IntoIterator` for references to our self
impl<'a, T: Iterable> IntoIterator for &'a MyIterableWrapper<T> {
    type IntoIter = <T as NonconsumingIter<'a>>::IntoIter;
    type Item = <Self::IntoIter as Iterator>::Item;
    fn into_iter(self) -> Self::IntoIter {
        self.inner.iter()
    }
}

// And now we can have nice bounds
fn foo<T: Iterable>(miw: MyIterableWrapper<T>) {
    for _ in &miw {       
    }
    for _ in miw.iter() {
    }
}

Worth it? I'll let you decide.

  1. actually before I hit submit, but eventually I realized what a detour this was ↩︎

  2. well, what we really want is GATs (generic associated types), so that we could put this all in one trait. But we don't have those yet, so... ↩︎

  3. If you need it, due to the bound, you can use <<T as NonconsumingIter>::IntoIter as Iterator>::Item. Simple! ↩︎

  4. guess that phrasing is a spoiler... ↩︎

  5. And doesn't require 'static. ↩︎

3 Likes