Can't understand this compiler error

help
1

Here's my code

struct Board {
	width: usize,
	height: usize,
	list: Vec<bool>
}

impl Board {
	fn new(width: usize, height: usize) -> Self {
		Self {
			width, height, list: vec![false; width * height]
		}
	}

	fn make_automata(self, rule: &dyn Rule) -> Automata {
		Automata {
			board: self,
			rule,
		}
	}
}

trait Rule {
	fn name(&self) -> String;
	fn modify(&self, board: &mut Board);
}

struct Automata<'a> {
	board: Board,
	rule: &'a dyn Rule,
}

impl<'a> Iterator for Automata<'a> {
	type Item = &'a Board;
	fn next(&mut self) -> Option<Self::Item> {
		self.rule.modify(&mut self.board);
		Some(&self.board)
	}
}

It gives me this error

error[E0495]: cannot infer an appropriate lifetime for borrow expression due to conflicting requirements
  --> src/main.rs:40:8
   |
40 |         Some(&self.board)
   |              ^^^^^^^^^^^
   |
note: first, the lifetime cannot outlive the anonymous lifetime #1 defined on the method body at 38:2...
  --> src/main.rs:38:2
   |
38 |     fn next(&mut self) -> Option<Self::Item> {
   |     ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
note: ...so that reference does not outlive borrowed content
  --> src/main.rs:40:8
   |
40 |         Some(&self.board)
   |              ^^^^^^^^^^^
note: but, the lifetime must be valid for the lifetime `'a` as defined on the impl at 36:6...
  --> src/main.rs:36:6
   |
36 | impl<'a> Iterator for Automata<'a> {
   |      ^^
note: ...so that the types are compatible
  --> src/main.rs:38:43
   |
38 |       fn next(&mut self) -> Option<Self::Item> {
   |  ______________________________________________^
39 | |         self.rule.modify(&mut self.board);
40 | |         Some(&self.board)
41 | |     }
   | |_____^
   = note: expected `Iterator`
              found `Iterator`

I'm not clear about the idea of lifetimes. My instuition is &self.board obviously should not 'outlive' the life of the automata object. that's why type Item = &'a Board where 'a is constrained to Automata<'a>(atleast that's what I thought would happen) but compiler still says it can't outlive.
And also I didn't understand this error "expected Iterator found Iterator" what does it actually mean?

2

There is a blog post on exactly this issue: Reference Iterators in Rust. One thing you’ve likely noticed when… | by Jordan MacDonald | Medium

The punchline is:

In simpler terms, the iterator shouldn’t own the data it’s yielding. It’s meant to be a transient type that sits outside of the collection, providing a convenient means of accessing the data.

Depending on the size of Board, you might want to just return a copy of the board every iteration. i.e. type Item = Board

Otherwise, it may not be a good conceptual fit to make your Automata an Iterator. Iterators are for iterating through a sequence, not necessarily representing a system as it evolves (and has only one state at a given instant)

1 Like
3

But, the thing is I like all the features and ergonomics and also some conveniences provided by the Iterator, that's why I chose Iterator trait to use it in the first place.
Also,

In order to do like this, I need to clone the Board. The problem is Vec used in the Board will contain 100 of millions of bools. So, basically cloning it takes a massive performance hit or even worse fail to allocate the memory.
I can use Arc<Board> instead of just Board but, I want to know is it the only way or is there any other way(i.e. without using Arc or Rc) to get around this limitation?

4

I finally understood why it should not it be possible.
If it was possible then:

fn main() {
	let mut automata = Board::new(10, 10).make_automata(&Dummy);
	let t = automata.next();
	let u = automata.next();
	//  t and u should not have same data
}

i.e. the data in the Board should not change until the variable t dies. If it changes that means there is a data race occuring which what happens in this line let u = automata.next();. The next method changes the data in Board while still var t is present and this will read-write race.

5

One option to explore might be to return a separate Iterator object, that returns references to Boards owned by the Automata. You could generate the boards as the iterator requested them, but you'll need to keep them around.

It might be a nightmare to clean up, but it is one option to explore depending on what you want to achieve.

Unfortunately there is no way around the fact that all of the Iterator results need to be accessible simultaneously, so one iteration can't overwrite the results of the previous iteration.

1 Like
6

Until Rust gets lending iterators, you can duck it without a trait:

impl<'a> Automata<'a> {
    // You could get rid of the `Option` in this case, but for illustration
	fn next(&mut self) -> Option<&Board> {
		self.rule.modify(&mut self.board);
		Some(&self.board)
	}
}

fn uses_automata(mut a: Automata<'_>) {
    // Use this form instead of `for`
    // (Or without `Option`... just `loop`)
    while let Some(thing) = a.next() {
        println!("{}", thing.width);
    }
}

Playground.

(But yeah, none of the convenience in other areas you may want too.)

1 Like
7

You're goddamn right. I also came to the conclusion which is almost the same :smile:

1 Like
9

I think all are in agreement, including the author... but for clarity, the example from the article:

struct TokenIterator {
    data: String,
    token_start: usize,
    token_end: usize,
}

... is flawed from the get-go.

Reason

data: String is the data. Essentially, a struct can’t both be the iterator and the data.

10

You can also use Rc or Arc to make a copy-on-write iterator:

struct Automata<'a> {
	board: Rc<Board>,
	rule: &'a dyn Rule,
}

impl<'a> Iterator for Automata<'a> {
	type Item = Rc<Board>;
	fn next(&mut self) -> Option<Self::Item> {
		self.rule.modify(Rc::make_mut(&mut self.board));
		Some(Rc::clone(&self.board))
	}
}

Playground

2 Likes
11

But, the problem with Rc::make_mut is (according to its docs) that is clones the data with a new heap allocation if there is a write. And the allocation can have a performance impact.
Also I think modelling this game of life as Iterator feels wrong.
Even this rustwasm tutorial uses tick method which is similar to this

instead of the Iterator.

12

This isn't quite right; it clones the data only if there are other outstanding references. If the consuming code drops the iterator result before calling next() again, there will be no copy made. A clone() will be required somewhere anyway if you want multiple board states to be accessible at the same time. The Rc code isn't free, though: There is a bit of overhead involved in the checks and a risk that your code will unintentionally clone by keeping results too long.

Those costs buy you the ability to use Iterator adapters and for loops; whether the tradeoff is appropriate will depend on the goals of your program.

The game of Life is a free-running automaton: It produces a sequence of values (a boolean matrix) without any external input, which seems perfectly suited to the Iterator abstraction to me.

1 Like
13

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.