Cannot return Iterator with Return Position Impl in Trait

power-unsealed · April 18, 2025, 7:09am

At work, I stumbled across the following lifetime issue I just couldn't find a solution for. Maybe someone of you finds one, or can at least tell me that it is currently just not possible? Thank you in advance!

I was implementing some sort of BufRead trait that allows peeking all stored data. The challenge is, that I want to be generic over the different buffer types that might need to return a varying number of slices. To return all stored data, a Vec<u8> only ever needs to return one slice, a VecDeque<u8> sometimes two, and a buffer chain potentially multiple.

My first try was to define this part of the trait the following way:

trait BufRead {
    fn peek_all(&self) -> impl Iterator<Item = &[u8]>;
}

This worked, until I wanted to write a helper type that allows reading from a generic iterator over slices. A shortened version of this type might look like this:

struct SlicesReader<'b, I: Iterator<Item = &'b [u8]>> {
    iter: I,
}

Now, the issue is: No matter how I define the BufRead trait, some implementation breaks because of lifetime issues. Either I cannot implement BufRead for my SlicesReader, or I cannot implement it for another type like VecDeque<u8>. I have three different variants, and neither of them works:

Version A (Playground)

trait BufRead {
    fn peek_all(&self) -> impl Iterator<Item = &[u8]>;
}

impl BufRead for VecDeque<u8> {
    fn peek_all(&self) -> impl Iterator<Item = &[u8]> {
        let (front, back) = self.as_slices();
        [front, back].into_iter()
    }
}

impl<'b, I: Iterator<Item = &'b [u8]> + Clone> BufRead for SlicesReader<'b, I> {
    fn peek_all(&self) -> impl Iterator<Item = &[u8]> {
        self.iter.clone()
    }
}

This version fails with the following error:

error: lifetime may not live long enough
  --> src/lib.rs:20:9
   |
18 | impl<'b, I: Iterator<Item = &'b [u8]> + Clone> BufRead for SlicesReader<'b, I> {
   |      -- lifetime `'b` defined here
19 |     fn peek_all(&self) -> impl Iterator<Item = &[u8]> {
   |                 - let's call the lifetime of this reference `'1`
20 |         self.iter.clone()
   |         ^^^^^^^^^^^^^^^^^ method was supposed to return data with lifetime `'b` but it is returning data with lifetime `'1`

To be honest, I don't understand this error message. The method is indeed returning data with lifetime 'b, but the compiler seems to think that the lifetime of the returned iterator is bound to self.

Version B (Playground)

This time, I was trying it with a GAT whose lifetime is bound to self.

trait BufRead {
    type Peek<'a>: Iterator<Item = &'a [u8]> where Self: 'a;

    fn peek_all(&self) -> Self::Peek<'_>;
}

impl BufRead for VecDeque<u8> {
    type Peek<'a> = std::array::IntoIter<&'a [u8], 2> where Self: 'a;

    fn peek_all(&self) -> Self::Peek<'_> {
        let (front, back) = self.as_slices();
        [front, back].into_iter()
    }
}

impl<'b, I: Iterator<Item = &'b [u8]> + Clone> BufRead for SlicesReader<'b, I> {
    type Peek<'a> = I where Self: 'a;

    fn peek_all(&self) -> Self::Peek<'_> {
        self.iter.clone()
    }
}

This version fails with the following error:

error[E0308]: mismatched types
  --> src/lib.rs:23:21
   |
23 |     type Peek<'a> = I where Self: 'a;
   |                     ^ lifetime mismatch
   |
   = note: expected reference `&'b _`
              found reference `&'a _`
note: the lifetime `'a` as defined here...
  --> src/lib.rs:23:15
   |
23 |     type Peek<'a> = I where Self: 'a;
   |               ^^
note: ...does not necessarily outlive the lifetime `'b` as defined here
  --> src/lib.rs:22:6
   |
22 | impl<'b, I: Iterator<Item = &'b [u8]> + Clone> BufRead for SlicesReader<'b, I> {
   |      ^^

For more information about this error, try `rustc --explain E0308`.

I don't really blame the compiler for not being happy with this. I just couldn't find a way to connect I with the lifetime 'a of the GAT.

Version C (Playground)

In the last try, I introduced a buffer lifetime for the BufRead trait. This fixes the SlicesReader implementation, but breaks VecDeque.

trait BufRead<'b> {
    type Peek: Iterator<Item = &'b [u8]>;

    fn peek_all(&self) -> Self::Peek;
}

impl<'b> BufRead<'b> for VecDeque<u8> where Self: 'b {
    type Peek = std::array::IntoIter<&'b [u8], 2>;

    fn peek_all(&self) -> Self::Peek {
        let (front, back) = self.as_slices();
        [front, back].into_iter()
    }
}

impl<'b, I: Iterator<Item = &'b [u8]> + Clone> BufRead<'b> for SlicesReader<'b, I> {
    type Peek = I;

    fn peek_all(&self) -> Self::Peek {
        self.iter.clone()
    }
}

This version fails with the following error:

error: lifetime may not live long enough
  --> src/lib.rs:14:9
   |
9  | impl<'b> BufRead<'b> for VecDeque<u8> where Self: 'b {
   |      -- lifetime `'b` defined here
...
12 |     fn peek_all(&self) -> Self::Peek {
   |                 - let's call the lifetime of this reference `'1`
13 |         let (front, back) = self.as_slices();
14 |         [front, back].into_iter()
   |         ^^^^^^^^^^^^^^^^^^^^^^^^^ method was supposed to return data with lifetime `'b` but it is returning data with lifetime `'1`

Again, I cannot really blame the compiler for this, except that it seems to ignore the Self: 'b lifetime bound (?)

Do you have an idea on how to fix this? I don't want to resort to returning something like Vec<&[u8]>. This seems just wasteful, especially since this code needs to run on an embedded microcontroller. Thank you for your time!

nerditation · April 18, 2025, 7:46am

this is in the signature of the trait method, if you write the elided lifetimes explicitly:

trait BufRead {
    fn peek_all<'a>(&'a self) -> impl Iterator<Item = &'a [u8]>;
}

for version A, it is fixable. the problem is the opaque type impl Iterator<Item = &[u8]> doesn't have a way to specify the variance, but you know the hidden type is covariant, so you can ~~explicitly~~ manually reborrow it to satisfy the signature:

impl<'b, I: Iterator<Item = &'b [u8]> + Clone> BufRead for SlicesReader<'b, I> {
    fn peek_all(&self) -> impl Iterator<Item = &[u8]> {
        self.iter.clone().map(|item| item)
    }
}

however, I don't know how to make version B work. the problem is, the GAT Peek<'a> is higher ordered, but the impl block gives it a single type I, but there's no way to tell the compiler that I: 'a for all 'a (where Self: 'a).

for version C, the bound Self: 'b is useless, because the method has an elided lifetime, let's call it &'a self, where 'a is the lifetime of the return value of self.into_iter(), i.e. array::IntoIter<&'a ...>, not array::IntoIter<&'b ...>.

version C can be "fixed" by implementing BufRead<'b> on reference type, i.e. &'b VecDeque instead of VecDeque itself, but it has other drawbacks, namely, auto referencing of self is not performed when you call the method with a VecDeque, :

impl<'b> BufRead<'b> for &'b VecDeque<u8> {
    type Peek = std::array::IntoIter<&'b [u8], 2>;

    fn peek_all(&self) -> Self::Peek {
        let (front, back) = self.as_slices();
        [front, back].into_iter()
    }
}

fn main() {
    let v = VecDeque::new();
    v.peek_all(); //<---- error: cannot find method `peek_all()`
    (&v).peek_all(); // ok
    let v = &v;
    v.peek_all(); // ok
    let v = &&&&&&v;
    v.peek_all(); // ok, auto deref still works
}

power-unsealed · April 18, 2025, 8:18am

Okay, that makes sense. But then I don't understand, why the compiler is saying that the method was supposed to return data with lifetime 'b.

nerditation:

for version A, it is fixable. the problem is the opaque type impl Iterator<Item = &[u8]> doesn't have a way to specify the variance, but you know the hidden type is covariant, so you can ~~explicitly~~ manually reborrow it to satisfy the signature:
impl<'b, I: Iterator<Item = &'b [u8]> + Clone> BufRead for SlicesReader<'b, I> {
    fn peek_all(&self) -> impl Iterator<Item = &[u8]> {
        self.iter.clone().map(|item| item)
    }
}

Nice, that works indeed. I was aware that sometimes a reborrow can help. But I didn't think of this solution. It would be really nice if the compiler could tell this, or even do it automatically. But at least there is a way to get it to work.

But doesn't tell the Self: 'b bound the compiler that 'b is more or less equivalent to the elided lifetime 'a? Because 'a would also be defined as &'a self, or isn't that the same?

Thanks a lot for your time and help!

power-unsealed · April 18, 2025, 8:39am

I think I can answer that question myself. The lifetime of the value is not necessarily the same as that of one of its references in a method call. Therefore, 'a is not a subtype of 'b.

quinedot · April 18, 2025, 8:55pm

(Tangential note)

Interestingly enough, this stops working if you idiomatically drop the bounds (and thus the lifetime) from SlicesReader. Presumably there's some opaque GAT and HRTB interaction that relies on &'a Thing<'b> being present in the signature, and not just Self: 'b in the impl bounds.

I agree that is a broken diagnostic.

You can make it work if you make something nameable to perform, effectively, .map(|item| item). Having to name things is the primary difference from version A.^[1]

No, it desugars to

where VecDeque<u8>: 'b

which is trivially true for all lifetimes. For example, it's true for 'b = 'static. But this can't work:

impl BufRead<'static> for VecDeque<u8> {
    type Peek = std::array::IntoIter<&'static [u8], 2>;

    fn peek_all(&self) -> Self::Peek {
        let (front, back) = self.as_slices();
        [front, back].into_iter()
    }
}

In more detail: Lifetime bounds like Self: 'b are type-level constraints, and syntactically defined. Foo: 'x if and only if, for every generic type or lifetime X in Foo, X: 'x. In the case of Foo = VecDeque<u8>, there are no generics type or lifetimes, so it satifies : 'x for any lifetime.

Rust lifetimes ('_ things) operate at the type level and don't correspond to the liveness scope of values. (Usually a lifetime corresponds to the duration of a borrow, and going out of scope or being destructed can conflict with being borrowed, but the liveness scope itself is not a Rust lifetime, despite the confusing overlap in terminology.)

In the body of peek_all, you have a borrow of the VecDeque<u8> based on the &'this self parameter (i.e. for duration 'this), and nothing longer. There's no way to tie that lifetime to the parameter on BufRead with the way the trait is defined.

You could change the definition of the trait to tie the lifetimes together...

trait BufRead<'b> {
    type Peek: Iterator<Item = &'b [u8]>;
    //           vv
    fn peek_all(&'b self) -> Self::Peek;
}

...but now you're basically back at Version B, only you've moved the lifetime from the associated type to the trait. So the SlicesReader implementation needs the same workaround as Version B.

I'd say "only difference", but things like my tangential note above make me wary of blanket statements ↩︎

undefined.behavior · April 18, 2025, 11:20pm

What's the disadvantage of expressing the lifetimes directly on traits?

Modified Version A (Playground)

trait BufRead<'b> {
    fn peek_all<'s: 'b>(&'s self) -> impl Iterator<Item = &'b [u8]>;
}

impl<'b> BufRead<'b> for VecDeque<u8> {
    fn peek_all<'s: 'b>(&'s self) -> impl Iterator<Item = &'b [u8]> {
        let (front, back) = self.as_slices();
        [front, back].into_iter()
    }
}

struct SlicesReader<'b, I: Iterator<Item = &'b [u8]> + ?Sized> {
    iter: I,
}

impl<'b, I: Iterator<Item = &'b [u8]> + Clone> BufRead<'b> for SlicesReader<'b, I> {
    fn peek_all<'s: 'b>(&'s self) -> impl Iterator<Item = &'b [u8]> {
        self.iter.clone()
    }
}

quinedot · April 19, 2025, 12:15am

Verbosity and making the lifetime invariant, though that may not matter for this particular use case. Part of the verbosity is needing to use higher-ranked bounds elsewhere, so you can call the method on a local variable. Getting those right is pretty finicky. (Sometimes extremely finicky.)

It works out in this case, but here are a few notes.

You don't need the distinct lifetime 's with 's: 'b in your playground, you can just use &'b self. The extra lifetime just allows someone to forcefully pass in a longer borrow of *self than is required. In practice no one will, because no one wants to borrow anything longer than necessary (and because you have to force it with turbofish, which probably no one will think to do).
You don't need to require that the borrow of *self be at least as long as the item lifetimes of I for SlicesReader<I>, and probably don't want to:
- it will interfere with the higher-ranked bounds needed to call the method on local variables^[1]
- calling the implementation may require borrowing forever (albeit in shared manner) if I is invariant in the lifetime
Allowing shorter borrows of *self reintroduces the OP's problem, but the map(|item| item) workaround still works.

Here's how things look after those adjustments:

turns out this my Version C had problems in this area as well; I didn't bother to try to fix them and stuck with your playground ↩︎

power-unsealed · April 20, 2025, 6:13am

Interesting observation
Somehow, I didn't think of eliding the lifetime in the struct definition, probably because in the real version of SlicesReader I am additionally caching the last slice from the iterator and therefore need the lifetime.

That's a really interesting solution! Making the lifetime conversion explicit seems to help here. Thank's for the suggestion!

quinedot:

In more detail: Lifetime bounds like Self: 'b are type-level constraints, and syntactically defined. Foo: 'x if and only if, for every generic type or lifetime X in Foo, X: 'x. In the case of Foo = VecDeque<u8>, there are no generics type or lifetimes, so it satifies : 'x for any lifetime.

Rust lifetimes ('_ things) operate at the type level and don't correspond to the liveness scope of values. (Usually a lifetime corresponds to the duration of a borrow, and going out of scope or being destructed can conflict with being borrowed, but the liveness scope itself is not a Rust lifetime, despite the confusing overlap in terminology.)

In the body of peek_all, you have a borrow of the VecDeque<u8> based on the &'this self parameter (i.e. for duration 'this), and nothing longer. There's no way to tie that lifetime to the parameter on BufRead with the way the trait is defined.

I don't want to claim having fully understood your explanation, but I think I kinda get the broad point. I wasn't aware that there is a distinction between type-level lifetimes and value-level lifetimes. The where Self: 'lifetime bound just describes a limitation on what types this trait is implemented for. In case of the VecDeque, it's for all because that type doesn't include a non-static lifetime. Such a type-level bound doesn't automatically impose a restriction on the value-level lifetime of the &self parameter in contained methods.

Topic		Replies	Views
Returning Iterators in Traits help	3	429	March 18, 2022
[solved] Wrapping an iterator around a trait help	4	1157	January 12, 2023
Iterator returning slice: how? help	3	1912	January 12, 2023
Lifetimeception - Trait usage with lifetime in trait and impl help	6	653	January 28, 2021
Lifetime issue in iterator help	12	1073	May 1, 2024

Cannot return Iterator with Return Position Impl in Trait

Version A (Playground)

Version B (Playground)

Version C (Playground)

Related topics