Implement iterator trait for string generator

help
1

Implement iterator trait for string generator

I am writing a string generator (just as an example)

struct StringGenerator {
  value : String
}

impl StringGenerator {
  fn new() -> StringGenerator {
    StringGenerator { value : "naq".to_owned() }
  }

  fn generate(&mut self) -> &str {
    if self.value.len() > 15 {
      self.value.drain(0..4);
      self.value.truncate(10);
      self.value.push_str("abc");
    } else {
      self.value.drain(0..2);
      self.value.push_str("fuw");
    }
    self.value.as_str()
  }
}

Here, the field value is the internal state of the generator. I can use the struct StringGenerator to make new strings as

  let mut sgen = StringGenerator::new();
  for _ in 0..10 {
    print!("{} ", sgen.generate());
  }

I would like to implement the trait Iterator for StringGenerator, to be able to use the generator in a loop like

  for e in sgen {
    print!("{e} ");
  }

The crucial is I don't want to make a copy of the generator as well as cloning the resulting string. So, I expect the generator just passes the string reference.
At this point I have a trouble specifying the reference lifetime

impl Iterator for StringGenerator {
  type Item = &str; // error: associated type `Iterator::Item` is declared without lifetime parameters

  fn next(&mut self) -> Option<Self::Item> {
    Some(self.generate())
  }
}

I am trying to set the lifetime parameter, specifying that lifetime of Item is as long as self keeps unchanged, but I don't know how to make this correctly. Something like this...?

impl<'a> Iterator for StringGenerator {
  type Item = &'a str;

  fn next(&'a mut self) -> Option<Self::Item> {
    Some(self.generate())
  }
}
2

I believe this is one of the cases that the interface of Iterator doesn't allow. Instead a LendingIterator trait would be required. I've become used to the fact that Stream for example does not come with the syntactic sugar IntoIterator offers, so for me seeing

while let Some(e) = sgen.next() {
    print!("{e} ");
}

is a rather usual occurrence and only a bit less convenient than a for loop.

2 Likes
3

To extend @jofas's answer. The problem with the Iterator trait is that it has following definition:

trait Iterator {
    type Item;

    fn next(&mut self) -> Option<Self::Item>;
}

Note that returned type of Iterator::next does not capture any lifetimes. Because associated type Item is not generic over any lifetimes (which is defined by the trait itself, not its implementations), returned type must have a lifetime independent of the lifetime of the mutable borrow of self when calling next. Or in other words Iterator trait allows you to hold on to previously yielded items, while continuing to iterate over them.

This however is fundamentally impossible with how StringGenerator works. You want your generator to return references pointing into value buffer, but simultaneously you are mutating it. This could lead to reference invalidation, which is the entire point Rust prevents with its ownership rules.

To support this concept of iteration you could use a "LendingIterator", which usually has a following definition:

trait LendingIterator {
    type Item<'a> where Self: 'a;
    fn next(&mut self) -> Option<Self::Item<'_>>;
}

This definition however is not present in the standard library, so support for it from the ecosystem will be very limited. Apart from that, this has right semantics for you, since returned items will only be alive as long as the borrow of self for the next call (or in other words, you cannot call next again until you drop previously yielded item). This could be usable, but you won't be able to use any standard iterator combinators, as well as a for loop syntactic sugar. Instead you can use while let loop, which will continue as long, as given expression matches given pattern.

Finally if you don't want to expose this as a library, I wouldn't bother with implementing LendingIterator, and just would use a simple loop.

5 Likes