GAT Iterable lifetime annotation

help
1

I tried to write the Iterable trait by using GAT as follows:

#![feature(generic_associated_types)]

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

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

but got the error from compiler:

error[E0261]: use of undeclared lifetime name `'a`
 --> src/main.rs:7:14
  |
7 |     fn iter(&'a self) -> Self::Iter<'a>;
  |              ^^ undeclared lifetime
  |
help: consider introducing lifetime `'a` here
  |
7 |     fn iter<'a>(&'a self) -> Self::Iter<'a>;
  |            ++++
help: consider introducing lifetime `'a` here
  |
3 | trait Iterable<'a> {
  |               ++++

I change the code to:

#![feature(generic_associated_types)]

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

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

and it works.

My question is why I need to add the constraint Self: 'a?

To my understanding, Self: 'a means that the lifetime of Self is longer than 'a. But actually what the trait requires is that the lifetime of Self is equal to 'a.

2

'a is the lifetime of borrowing created by iter(), it doesn't have to live as long as Self.

1 Like
3

First of all, this is not true. (Why would the collection need to live exactly as long as the iterator? Not having that requirement is the very point of a borrowing iterator.)

But more importantly, the error has nothing to do with the lifetime of Self; it is almost barely of a syntactic nature. In your first, non-compiling solution, the lifetime 'a on the function is not declared anywhere. It's declared on the associated types, but those are separate and independent declarations; you might as well have called them by completely different names, because generic parameters introduced inside them are independent.

If you write the following, it eliminates the particular "undeclared lifetime" error:

trait Iterable {
    type Item<'b>;
    type Iter<'c>: Iterator<Item = Self::Item<'c>>;

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

(and you then get back to the lifetime annotation error about Self, which appears to be an artificial constraint for now.)

4

Careful, we have a &self, i.e., a self: &'_ Self receiver, so there are two lifetimes/regions/durations to consider:

  • the lifetime/duration of the borrow of *self held in self, here '_ (or 'a in @H2CO3's snippet);

  • the lifetime/region of "owned usability" of Self: indeed, the Self type, itself, may have nested borrows inside it. For instance, consider Self = (&'x [u8], Cow<'s, str>)). In that case if we go beyond 'x that first borrow will dangle, and if we go beyond 's the Cow may dangle. So we must stay within both 'x and 's. That is, we must stay within the intersection ("minimum") lifetime of these.

    By saying Self : 'a, we are thus rather expressing a 'x : 'a && 's : 'a constraint, for each and every lifetime parameter appearing in Self.

    Usually, there are no inner lifetimes in Self (e.g., Self = Vec<u8> or Self = String), in which case there are no limitations / the "lifetime of owned-usability of Self is 'static". Then, Self : 'a is expressing no constraints.

An interesting relationship between these two things is that given &'a Self, for the borrow to be well-formed, Self : 'a needs to hold. Indeed, if nobody can own Self beyond its "lifetime of owned usability" (by definition), then a fortiori you cannot borrow it for that long either.

As to why it is required, the fact is you're not gonna be instantiating a Self::Iter<'a> other than by calling .iter::<'a>() on that self: &'a Self. This means that the moment we are calling .iter(), we have a self: &'a Self appearing in the signature, and thus, a Self : 'a constraint.

So, if we are gonna have that constraint any time we instantiate Self::Iter<'a>, we may as well offer it as a guarantee when providing that GAT, to keep things flexible. That is, this bound is a blessing / a good thing and not a bad thing, it's actually saying "don't bother providing Self::Iter<'a> when Self : 'a does not hold".

For instance, if Rust did not "firmly" remind you to add that loosening Self : 'a clause on that GAT, that is, if you had:

trait Iterable {
    type Item<'iter>;
    type Iter<'iter> : Iterator<Item = Item<'iter>>;
    /* removed the `fn` to prevent Rust from firmly suggesting a `where Self : 'iter` bound */
}

then the following type would be unable to impl Iterable:

struct Foo<'s>(&'s str); // some non-'static type

impl Iterator for &'_ Foo<'_> { /* … */ } // &Foo : Iterator

impl<'s> Iterable for Foo<'s> {
/*
    fn iter<'iter> (self: &'iter Foo<'s>)
      -> &'iter Foo<'s>
    {
        self // thanks to `&Self : Iterator`
    }
*/
    // thus:
    type Iter<'iter> = &'iter Foo<'s>; // ERROR: `'s` does not live long enough, add a `'s : 'static` yadda yadda
}

Since in order for &'iter Foo<'s> to be well-formed, we need Foo<'s> : 'iter to hold, i.e., 's : 'iter. And yet nothing gives us that property (only that where … at the definition of the GAT could!), so we have to fall back to that annoying 's : 'static restriction.

So not only is it good that the clause be added, you should also add it to that type Item<'iter>; ! (e.g., imagine if
<&'iter Foo<'s> as Iterator>::Item = &'iter &'s str : you'd need 's : 'iter as well).

  • There is only one annoyance, however, which is that Rust does not let an implementor "refuse the gift", and try to provide an associated type for any lifetime:

    impl<'xs> Iterable for &'xs [u8] {
    type Iter<'iter> = slice::Iter<'iter, u8>; // no `'xs` whatsoever
                                               // thus no `'xs : 'iter`
                                               // should be needed

    but, alas, when the trait definition has a where Self : 'iter clause attached to it, you do have to (needlessly) repeat it here.

5 Likes
5

This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.