Lifetime issue when wrapping a function returning an Iterator

Question

I am building a custom data structure which supposes to return an iterator for its elements. If simplified, it can look like this:

use std::iter::{Iterator, StepBy};

// My collection which returns iterator to it's elements
pub trait MyCollection<'a, T: 'a> {
  type I: Iterator<Item = &'a T>;
  fn find_something(&'a self) -> Self::I;
}

Now, in some cases, I would like to create a "wrapper" for this collection that transforms the elements returned by the iterator. For the sake of this example let's assume that this wrapper allows skipping over some elements of the original iterator:

// Wrapper for a collection that allows iterating over elements with a step
pub struct StepWrapper<'a, A>(&'a A, usize);

impl<'a, T: 'a, A: MyCollection<'a, T>> MyCollection<'a, T> for StepWrapper<'a, A> {
  type I = StepBy<A::I>;
  fn find_something(&'a self) -> Self::I {
    self.0.find_something().step_by(self.1)
  }
}

// Function which takes a collection and a step value and returns a wrapped collection
fn wrap<'a, T: 'a, A: MyCollection<'a, T>>(a: &'a A, step: usize) -> impl MyCollection<'a, T> {
  StepWrapper(a, step)
}

Unfortunately, I get a compilation error when trying to use this code:

// Example
impl<'a> MyCollection<'a, u64> for Vec<u64> {
  type I = std::slice::Iter<'a, u64>;
  fn find_something(&'a self) -> Self::I {
    return self.iter();
  }
}

fn main() {
  let collection = vec![12, 13, 14];
  let wrapped = wrap(&collection, 2);
  
  // Error now
  let result = wrapped.find_something().skip(1).next();
  //           ^^^^^^^ borrowed value does not live long enough

  println!("{}", result.unwrap());
}

I understand that StepWrapper<'a, A>::find_something requires self to be borrowed for the same lifetime as the original collection. But all my attempts to decouple lifetimes of a collection and a wrapper were unuseful. Essentially a find_something function in the wrapper needs to return a result which outlives itself. Is there a way to express it in Rust?

Fixed the code. When I remove lifetime 'a from the self I get an error in impl<'a> MyCollection<'a, u64> for Vec<u64>. — Peter Popov
In Rust it's easier to wrap not a reference, but the whole object (by value), thus eliminating all the pain of dealing with references. If you ever need to get to the inner value, you can implement such a method that unwraps it (by reference or by value). — Alexey Larionov

Cormac O'Brien Cormac O'Brien · Accepted Answer · 2021-01-15T19:18:00

The pattern you're using is called a streaming iterator, and unfortunately it's not possible with the Iterator trait.

This is a current weakness of Rust's type system: it lacks what are known as generic associated types, or GATs. There's an RFC for this language feature and a tracking issue.

In the meantime, the streaming_iterator crate is designed to provide the functionality you're looking for.

Lifetime issue when wrapping a function returning an Iterator

1 Answers