How do I access the state of an iterator I'm iterating over without angering the borrow checker?

help
1

Earlier this week I was struggling with an advent of code solution that involved generating a long list of numbers, and then checking some additional conditions about it after a certain number of elements get generated (day 14 if you're playing).

I made a decent Iterator for my solution that kept things pretty clean in rust, but it performed orders of magnitude slower than a nearly identical python solution. Digging into why, I was using Vec.clone() to side-step some borrow checker issues, and it turns out copying the Vec out on every iteration was the culprit.

I was able to replicate the python solution's performance by throwing away my Iterator and instead have an infinite while-loop calling a mutating method on the struct and continually checking on the state of the list being generated. However, because I was no longer dealing with a clean Iterator implementation, I ended up introducing a few bugs that took me a while to track down. I was spoiled by keeping things in an Iterator.

How do I provide visibility of a piece of data from an Iterator without angering the borrow-checker?

I have a mini-replica of the issue in this playground link. The line that causes the performance hit is the last line in my fn next(&mut self) -> Option<Vec<i32>> implementation:

        Some(self.current.clone())

Removing the call to .clone() gives me the following compiler error:

   Compiling playground v0.0.1 (/playground)
error[E0507]: cannot move out of borrowed content
  --> src/main.rs:28:14
   |
28 |         Some(self.current)
   |              ^^^^^^^^^^^^ cannot move out of borrowed content

error: aborting due to previous error

For more information about this error, try `rustc --explain E0507`.
error: Could not compile `playground`.

To learn more, run the command again with --verbose.

How do I remove .clone() to improve my performance, without abandoning the easy-to-use Iterator solution?

2

Well, think about this case if we try to use references:
If we try to return a &Vec<i32>, then we will be breaking rust's ownership rules, here's why:

  • self will own a Vec<i32> with the contents [1, 1]
  • When we call next(), we end up with a modified self.current ([1, 1, 2])
  • next() will return &self.current
  • We will then try to call next() again, we attempt to modify self.current, but because we gave out a reference to self.current, we can't modify it, because owning a &T forces the underlying T to not be modified
  • Returning a &mut T won't work either, because we can't have multiple &mut T to the same object according to rust's rules as well

Therefore, references are off the table, or at least raw references
As a side note, I'd recommend either having next() just return the next value, or change it entirely and have the struct have a public Vec and impl a next() -> () function which will simply add to the internal Vec

Note that the idea I presented may look like the following:

//Untested
let mut fibs = ...;
for i in (0..n).iter().map(|_| {fibs.next(); fibs.current.last()}) {
    //
}
1 Like
3

If the upcoming GATs were implemented in the compiler, I believe this would work (though you would need another Iterator trait):

impl Iterator for FibVecGenerator {
    type Item<'a> = &'a [i32];
    
    fn next<'a>(&'a mut self) -> Option<&'a [i32]> {
        let a = self.current[self.current.len() - 1];
        let b = self.current[self.current.len() - 2];
        self.current.push(a + b);

        Some(&self.current)
    }
}

That way, each time we call next we would get a slice that would only live for the body of the loop.

However, you could bypass the problem by not implementing Iterator per se:

fn next(f: &mut FibVecGenerator) -> Option<&[i32]> {
    let a = f.current[f.current.len() - 1];
    let b = f.current[f.current.len() - 2];
    f.current.push(a + b);
    Some(&f.current)
}

fn main() {
    let mut fibs = FibVecGenerator::new();
    while let Some(f) = next(&mut fibs) {
        if f.len() % 3 == 0 {
            println!("skipping this iteration for the sake of example!");
            continue;
        } else {
            println!("{:?}", f);
        }
        if f.len() > 20 {
            break;
        }
    }
    println!("Hello, world!");
}
1 Like
4

I'm guessing that Fibonacci is not directly relevant to your AoC solution, but if you're still trying to return a fixed length of items (elf state?), I would suggest a different type than a vector. Either an array [T; 2] or a tuple (T, T) would be trivially copyable for T: Copy. (edit: scratch that -- I didn't notice you were producing the full growing fib sequence each time.)

For the general problem of wanting a GAT-like Iterator, there is StreamingIterator. It doesn't work with for loops, but you can get close with a while let Some loop, or it's fine to use in functional style.

5

I love how the linked RFC gives an example that's nearly identical to my problem:

A [...] use case for this trait would be an iterator over a vector which yields overlapping, mutable subslices with each iteration.

Thank you for this

6

Your while-loop is similar to the structure I ultimately had to refactor my puzzle solution to, but the let Some(f) == next(...) condition is much cleaner than the while true... break; nonsense I had written earlier. Very clean, love it!

1 Like