Lifetime mismatch in Iterator

help
1

I'm stuck with lifetime in iterator.

My code looks like this:

I'm getting following error:

error[E0308]: method not compatible with trait
   --> src/move.rs:371:5
    |
371 |     fn next(&'a mut self) -> Option<&'a Move> {
    |     ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ lifetime mismatch
    |
    = note: expected fn pointer `fn(&mut SortedMovesIter<'a>) -> Option<&Move>`
               found fn pointer `fn(&'a mut SortedMovesIter<'a>) -> Option<&'a Move>`
note: the anonymous lifetime as defined here...
   --> src/move.rs:371:5
    |
371 |     fn next(&'a mut self) -> Option<&'a Move> {
    |     ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
note: ...does not necessarily outlive the lifetime `'a` as defined here
   --> src/move.rs:366:6
    |
366 | impl<'a> Iterator for SortedMovesIter<'a> {
    |      ^^

Because of performance reasons I need to get the &Move reference.

From compiler errors I have an impression, that my problem might get solved with two explicit lifetimes, but I'm not able to get them right.

2

When you add an explicit lifetime to &self, and especially to &mut self, then you are almost certainly doing it wrong.

Just think about it: elements can exist without the iterator they come from. Surely you don't want the lifetime of elements to be tied to the lifetime of some arbitrarily short reference to the iterator?

For this exact reason, the signature of Iterator::next() is such that you can't even do this. The desugaring of

fn next(&mut self) -> Option<Item>

is

fn next<'iter>(&'iter mut self) -> Option<Item>

which shows that there is no relation whatsoever between the lifetime of self and any potential lifetime parameters.

I can't compile the given snippet in the Playground because it requires too much context, but I don't think any amount of lifetimes will solve your problem.

1 Like
3

Thanks for looking into my use case.

I've isolated the issue to Playground: Rust Playground

I know, that having move_list mutable is the source of the problem.

pub struct SortedMovesIter<'a> {
    move_list: &'a mut Vec<MyMove>,
    index: usize,
}

But, in my program, I need to do sorting "on the fly", iteration over the sorted vector breaks usually quite early.

Is there any way how to retain mutable collection in the iterator?

4

Do you really need a vector, or would a reference to a mutable suffice? There's a standard trick for iterating over a slice, which works by untying the lifetime of self and that of the slice, using mem::take(), which is possible because for<T> &mut [T; 0]: Default + 'static.

1 Like
5

Thank you. For me, "on the fly" ordering is crucial. I've ended up with cloning the move in the end. Once I will have the engine ported and covered with unit tests, I'm planning to review and reconsider tricky spots of the engine.

This is what's working for me:

pub struct SortedMovesIter<'a> {
    state: &'a BoardState,
    transposition_state: &'a TranspositionTable,
    move_list: MoveList,
    index: usize,
}

impl<'a> Iterator for SortedMovesIter<'a> {
    type Item = Move;
    fn next(&mut self) -> Option<Move> {
        if self.index == self.move_list.len() {
            return None;
        }

        self.move_list.pick_next_best_move(self.index);
        let moov: &Move = &self.move_list.moves[self.index];
        self.index += 1;
        Some(moov.clone())
    }
}
6

I don't think that's the reason, or else rust 1.65 announce wouldn't talk about bright future where iterators would do precisely that (the very first example for one of the very anticipated feature talks about such iterators).

But it's true that existing Iterator interface can not do that and, while announce presents such Lending Iterator as premier example it's not in the standard library yet (and it's hard to add it in third-party crate because this would make it impossible to use it in for).

P.S. Of course the mere existence of that blog post also proves your point about the fact that currently you can not express what @petr wanted to express: it wouldn't make sense to pitch a new feature capable of doing that if existing version would have been capable enough.

7

You can sort a slice, too.

8

OP is trying to implement the Iterator trait, which absolutely does not allow this. I was referring to this, and not some imaginary trait-to-be. "You may be able to do this a year later" is probably not the kind of advice they came here for.

1 Like
9

It's difference between what they wanted and what they needed. When I hit the same issues I was really glad to know that thing that I want is coming later.

Simply because then I can do what @petr actually did: cobble together some kind of inefficient workaround for now and replace it later when proper solution would become available.

Even if you can not wait and need to invent some kludge today it's still nice to know about that because of exceptio probat regulam in casibus non exceptis principle: if something is staged to arrive later then it means that it's not your understanding of the world is wrong, but that what you are dealing with is a deficiency (since other perceive it as deficiency), thus it's Ok to stop investigating and use of ugly kludge becomes justified.

You words here sounded as if current design of the iterator is the only sensible one which may exist which is most definitely not true.

10

This isn't a syntax problem, or even a GAT thing. This is, as far as borrow checking rules go, a logic error leading to potentially unsafe code.

The Iterator trait guarantees that uses like .collect() are always valid, by definition. Elements returned by the iterator must remain valid throughout the entire iteration and even outlive the iterator.

If you're mutating move_list, you're shuffling items around, which could affect the elements you've already returned that were supposed to be immutable. &mut allows doing anything with the list, including destroying all the elements in it, which would leave dangling pointers. That is a violation of the Iterator contract and the mutable != shared and safety guarantees of references.

You'd need to convince the borrow checker that the elements you've already returned are 100% guaranteed to stay immutable and unchanged no matter what. First, you'd definitely have to ensure that pick_next_best_move doesn't mutate any of the elements already returned.

You might convince the borrow checker with something like split_first_mut that the elmement you're returning and the rest of the list you'll keep are separate, but IIRC it requires some clever gymnastics to have borrow checker accept reassignment to self.move_list. You may need unsafe to force through the lifetimes here (this is standard practice for mutable iterators).

1 Like
11

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.