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

  1. How to define a trait which requires Self to be iterable by ref? I figure there's two ways to do this, is there any difference between the two? I'm leaning towards the first version.
pub trait Trait1
where
    for<'a> &'a Self: IntoIterator,
{ ... }

pub trait Trait2<'a>
where
    &'a Self: IntoIterator,
{ ... }

The trait I am trying to define will really only describe something iterable (and optimally by ref only disallowing into_iter(self) that consumes self, disallow consuming the underlying collection or any elements within it). It will also declare a size() method to get the size of some underlying collection of unknown (to the trait) type. It may also require (Self: Index) immutable indexing. Finally is there a way to bind Self like (Self: !impl IntoIter) for the aforementioned reasons. I'd like to make it part of the trait contract that Self must not be able to consume/convert itself into an iterator as this would sort of be an anti-pattern for my use-case.

  1. When debugging my program (on lldb) after compiling it with the standard dev/debug profile, why is the source code for much of the rust std library missing (can only view the asm of Rust's std library functions)? I have the standard Rust toolchain (both stable and nightly installed the normal way).

One difference is that the former requires implementing IntoIterator for all lifetimes, while the latter permits only implementing for some lifetimes.

  • impl IntoIterator for &'static MyStruct
  • impl<'a> IntoIterator for &'a MyOtherStruct<'a>

The examples seem somewhat unlikely to encounter (and unlikely to be what you want to support), but the latter is more flexible. Additionally, there's another difference, which is that if you want to tie the associated types of IntoIterator into types of your own trait, you will need GATs (not yet stable) to do so:

pub trait Trait1
where
    for<'a> &'a Self: IntoIterator<Item = <Self as Trait1>::Item>,
{
    type Item;
}

impl Trait1 for Vec<i32> {
    type Item = &i32;
}

:arrow_right:


error[E0106]: missing lifetime specifier
 --> src/lib.rs:9:17
  |
9 |     type Item = &i32;
  |                 ^ expected named lifetime parameter
  |
help: consider introducing a named lifetime parameter
  |
9 |     type Item<'a> = &'a i32;
  |              ++++    ++

:arrow_right:

#![feature(generic_associated_types)]
pub trait Trait1
where
    for<'a> &'a Self: IntoIterator<Item = <Self as Trait1>::Item<'a>>,
{
    type Item<'a>;
}

impl Trait1 for Vec<i32> {
    type Item<'a> = &'a i32;
}

Playground (nightly).

If you can get away with not having the lifetime as a trait parameter, I recommend that (adding lifetimes to traits tends to add a lot of complication), but the above limitations are something to be aware of.


No. If you need to make that guarantee, wrap other things in a new type which you control.

Even if Rust gains the ability to do something like this (and it probably will eventually), it will be opt-in: a struct owner will have to explicitly implement !IntoIterator. If you could do what you suggest and it was not opt in, then users of your crate could be broken when some third party crate adds an implementation for IntoIterator, which is not considered a major breaking change today. (If it's opt-in, removing impl !IntoIterator would be the major breaking change.)

You might be interested in the ExactSizeIterator trait.


I suggest splitting your lldb question into a separate thread.

2 Likes

Thanks for the info. I still can't seem to wrap my head around everything. I went and read a couple blog posts on early and late bindings - I sort of understood it, but I'm not sure what applies here. Let's say I want a newtype which wraps a generic iterable. I want my new type to be iterable but only by reference. Its impl for IntoIterator will simply call self.inner.into_iter() where self: &Self (because I will only impl IntoIterator for MyIterableWrapper references - I don't want to allow consuming self nor the Item's).

pub struct MyIterableWrapper<T>
where
    &T: IntoIterator<Item = Card>,
    // ^ errors with: https://doc.rust-lang.org/error-index.html#E0637
{
    inner: T,
}

I'm overwhelmed by the options here. The compiler is suggesting adding a + 'static bound to T (and changing &T to &'static T). In addition to the compiler's suggestions, I feel like I could also try the for<'a> syntax before &T like before, or, just adding a lifetime param to the struct's params (This probably is the most correct and feels the most natural maybe, but it doesn't make much sense to me because my struct doesn't actually contain any &T references. I also don't want to have to specify a useless lifetime param every time I reference MyIterableWrapper?)

EDIT: I just realized that I could probably just require T to be IntoIterator and then only impl IntoIterator for &MyIterableWrapper on the wrapper. I believe this places a stricter requirement on T however, as T is a subtype of &T? So I think it's worth knowing how to accomplish this properly without making the bound stricter/less generic.

You want

pub struct MyIterableWrapper<T>
where
    for<'any> &'any T: IntoIterator<Item = Card>,
{
    inner: T,
}

Although it's more idiomatic to not put the bounds on the struct, and instead put them where it matters elsewhere (functions that need certain functionality, constructor function, wherever), as otherwise you'll write things like this by reflex:

fn foo<T>(_: MyIterableWrapper<T>) {}
And then the compiler will yell at you for not repeating the bound:
error[E0277]: `&'any T` is not an iterator
  --> src/lib.rs:10:14
   |
10 | fn foo<T>(_: MyIterableWrapper<T>) {}
   |              ^^^^^^^^^^^^^^^^^^^^ `&'any T` is not an iterator
   |
   = help: the trait `for<'any> Iterator` is not implemented for `&'any T`
   = help: the trait `Iterator` is implemented for `&mut I`
   = note: required because of the requirements on the impl of `for<'any> IntoIterator` for `&'any T`
note: required by a bound in `MyIterableWrapper`
  --> src/lib.rs:5:24
   |
3  | pub struct MyIterableWrapper<T>
   |            ----------------- required by a bound in this
4  | where
5  |     for<'any> &'any T: IntoIterator<Item = Card>,
   |                        ^^^^^^^^^^^^^^^^^^^^^^^^^ required by this bound in `MyIterableWrapper`

(The compiler does currently have a habit of suggesting &'static when it shouldn't.)


Anyway, next you probably want to implement IntoIterator on references to your wrapper, and probably the customary .iter method too:

// There's less downsides to using this form than there are downsides for
// having a `MyTrait<'a>`
impl<'a, T> IntoIterator for &'a MyIterableWrapper<T> 
where
    &'a T: IntoIterator<Item = Card>
{
    type IntoIter = <&'a T as IntoIterator>::IntoIter;
    type Item = Card;
    fn into_iter(self) -> Self::IntoIter {
        self.inner.into_iter()
    }
}

impl<T> MyIterableWrapper<T> {
    pub fn iter<'a>(&'a self) -> <&'a Self as IntoIterator>::IntoIter
    where
        &'a Self: IntoIterator
    {
        self.into_iter()
    }
}

You'll then be able to iterate directly given the appropriate bounds.

fn foo<T>(miw: MyIterableWrapper<T>) 
where
    for<'any> &'any MyIterableWrapper<T>: IntoIterator
{
    for _ in &miw {       
    }
}

Playground.

3 Likes

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

Nice work! Jeez. Who would of thought that it'd be so complicated to achieve this? You'd think that requiring &T or &Self to be IntoIterator would and should be similar in difficulty and complexity to how it is usually done for T or Self.

Do you know why/how _LifetimeHack = &'a Self transfers the lifetime 'a to Self in your example?

I also kinda wonder what a GAT solution would look like, although if it's easier than this then I could probably figure it out on my own. Honestly I didn't even know what a GAT was until you mentioned it.

After a little bit of research, it sounds like my issue is at least somewhat related to the StreamingIterator/LendingIterator problem in Rust (well I think anyway).

It is clear that lifetimes can very quickly and easily become very complex, complicating Rust's type system in no time.

By the way, you can get partially there to effectively requiring bounds on arbitrary types in a somewhat useful way, by using type equality. So for for<'a> &'a T: IntoIterator, you can write the traits like this

pub trait NonconsumingIter<'a, RefSelf = &'a Self> {
    type RefSelf: TypeIsEqual<To = RefSelf> + IntoIterator;
}

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

where type equality is defined by

pub trait TypeIsEqual {
    type To: ?Sized;
}
impl<T: ?Sized> TypeIsEqual for T {
    type To = Self;
}

(see here for a documented version of that trait).

Then T: Iterable does effectively prove that there is an actual for<'a> &'a T: IntoIterator implementation. Of course rustc doesn’t know that, but you can still use it with some workarounds/trickery:

impl<'a, T: Iterable> IntoIterator for &'a MyIterableWrapper<T> {
    type IntoIter = <<T as NonconsumingIter<'a>>::RefSelf as IntoIterator>::IntoIter;
    type Item = <Self::IntoIter as Iterator>::Item;
    fn into_iter(self) -> Self::IntoIter {
        fn helper<S: IntoIterator>(x: <S as TypeIsEqual>::To) -> S::IntoIter {
            x.into_iter()
        }
        helper::<<T as NonconsumingIter<'a>>::RefSelf>(&self.inner)
    }
}

(full playground)

There’s not really an advantage here necessarily over using a custom iter method instead, but it is IMO still technically interesting that you can exclusively work with helper-traits that don’t have any methods at all.

2 Likes

This is mostly explained in the collapsed "longer explanation". The lifetime is transferred by an implied bound: if the signature of a generic fn, type, trait, or impl directly includes a type &'a T, it automatically receives the implicit bound T: 'a. If this bound were not met, the type or trait wouldn't make any sense; it would be ill-formed. First, to illustrate well-formedness, a &'static &'a str cannot even be referred to:

pub fn example<'a>() {
    let _o: Option<&'static &'a str> = None;
}
error[E0491]: in type `&'static &'a str`, reference has a longer lifetime than the data it references
 --> src/lib.rs:2:13
  |
2 |     let _o: Option<&'static &'a str> = None;
  |             ^^^^^^^^^^^^^^^^^^^^^^^^
  |
  = note: the pointer is valid for the static lifetime
note: but the referenced data is only valid for the lifetime `'a` as defined here
 --> src/lib.rs:1:16
  |
1 | pub fn example<'a>() {
  |                ^^

For more information about this error, try `rustc --explain E0491`.
error: could not compile `wat` due to previous error

For the type system to be sound, it is important never to create ill-formed types through any means. The explanation for E0491 gives an example which illustrates this:

struct Foo<'a> {
    x: fn(&'a i32),
}

trait Trait<'a, 'b> {
    type Out;
}

impl<'a, 'b> Trait<'a, 'b> for usize {
    type Out = &'a Foo<'b>; // error!
}

If this were allowed, we could get around the well-formedness restrictions by writing <usize as Trait<'static, 'a>>::Out instead of &'static Foo<'a>. Instead, we must repeat the required bound on the impl, so that usize can no longer implement Trait<'static, 'a> (unless 'a: 'static):

-impl<'a, 'b> Trait<'a, 'b> for usize {
+impl<'a, 'b: 'a> Trait<'a, 'b> for usize {
     type Out = &'a Foo<'b>;
 }

However, writing these bounds explicitly everywhere would quickly become tedious. So when a type with well-formedness restrictions such as &'a Foo<'b> is referenced directly by a declaration, the compiler adds the implied bound 'b: 'a to prevent ill-formed usage.


In this particular scenario, the _LifetimeHack = &'a Self adds an implicit Self: 'a bound to NonconsumingIter<'a>. So when we write T: for<'any> NonconsumingIter<'any>, the compiler understands this to mean "T: NonconsumingIter<'any> for all lifetimes 'any such that NonconsumingIter<'any> is well-formed, i.e., all lifetimes 'any such that T: 'any". Without the implied bound, it would instead mean "T: NonconsumingIter<'any> for all lifetimes 'any, up to and including 'static", which can only hold when T: 'static.

1 Like

Like so. Mainly, the GAT-like trait gets combined into the main Iterable trait, where the GAT takes a parameter (whereas before we needed a separate trait to take the parameter). The where Self: 'a bounds on the GATs are taking the place of the _LifetimeHack.

Some of those bounds may some day be inferred, similar to @LegionMammal978's explanation of implied bounds [1].

The lack of GATs early on is probably why there is no Iterable trait; if there had been from the start, we could have instead had a blanket rule in the other direction:

impl<'a, I: Iterable> IntoIterator for &'a I {
    type IntoIter = <I as Iterable>::IntoIter<'a>;
    type Item = <I as Iterable>::Item<'a>;
    fn into_iter(self) -> Self::IntoIter {
        I::iter(self)
    }
}

// And also
impl<'a, I: Iterable> Iterable for &'a I {
    type IntoIter<'b> = <I as Iterable>::IntoIter<'a> where Self: 'b;
    type Item<'b> = <I as Iterable>::Item<'a> where Self: 'b;
    fn iter(&self) -> Self::IntoIter<'_> {
        <I as Iterable>::iter(*self)
    }
}

But now that would conflict with everyone's implementations on their own reference types. (Going the other direction should still be ok as inherent functions take precedence over trait method. Arbitrarily nested references are probably out for good though.)

LendingIterator tackles a different problem: When you want to return a piece of the iterator itself, like an internal buffer you lend out. That in turn means that users of the iterator have to drop each next() result before calling next() again, which is incompatible with the ability to .collect() a normal Iterator, say.


  1. but probably more fallibly as they will have to be inferred by the methods in the trait, versus actual well-formedness requirements of types ↩︎

2 Likes