Lifetime issue with peekable iterators

[smoky frigate]

I have a CombinedIterator struct which contains a vec of peekable iterators. I'm trying to implement Iterator on this struct such that the minimum next elements from the component iterators is returned.

Here's one impl attempt:

struct CombinedIterator<T> {
    iters: Vec<Peekable<Box<dyn Iterator<Item = T>>>>,
}

impl<T: Ord> Iterator for CombinedIterator<T> {
    type Item = T;

    fn next(&mut self) -> Option<Self::Item> {
        self.iters
            .iter_mut()
            .filter_map(|itr| itr.peek().map(|peeked| (peeked, itr)))
            .min_by(|x, y| x.0.cmp(y.0))
            .map(|(_, itr)| itr.next().unwrap())
    }
}

Which fails to compile:

error[E0505]: cannot move out of `itr` because it is borrowed
  --> examples/combined_iter.rs:13:46
   |
13 |             .filter_map(|itr| itr.peek().map(|peeked| (peeked, itr)))
   |                             - ---------------^^^^^^^^---------------
   |                             | |              |                 |
   |                             | |              |                 move occurs due to use in closure
   |                             | |              move out of `itr` occurs here
   |                             | borrow of `*itr` occurs here
   |                             | returning this value requires that `*itr` is borrowed for `'1`
   |                             return type of closure is Option<(&'1 T, &mut Peekable<Box<dyn Iterator<Item = T>>>)>

I know there are other (possibly superior) ways to implement next() to avoid this issue, but I'd like to understand why this impl fails.

The compiler error doesn't make sense to me. As input to the closure, itr is already borrowed as type &mut Peekable<_> so I don't understand why the compiler is saying further borrowing occurs. Why can't the same mutably borrowed itr reference be used for both itr.peek() and as the return value in the tuple?

[frozen meadow]

When you call Peekable::peek the returned reference's lifetime is tied to that of the &mut self in Peekable::peek - this means that the returned reference kinda "owns" the &mut Peekable for as long as it sticks around. It has to because Rust doesn't allow you to mutate something while you have any immutable references around

If it allowed that code, then you'd be making an iterator that produces shared references to the first element of the Peekable, along with a &mut to the Peekable and someone could do this

let (peeked, peekable) = your_filter_mapped_iterator.next().unwrap();
peekable.next().unwrap(); // moves the first item out of the iterator
dbg!(peeked); // the first element this was pointing to was moved! bad!

[smoky frigate]

Thanks much @frozen meadow , that makes sense.

However, it seems to me for peek() the returned reference lifetime should theoretically need only be tied to that of &self instead of &mut self.

E.g. peek() could be refactored as such:

impl<I: Iterator> Peekable<I> {
    pub fn peek(&mut self) -> Option<&I::Item> {
        let iter = &mut self.iter;
        self.peeked.get_or_insert_with(|| iter.next()).as_ref()
    }

    pub fn peek_refactored(&mut self) -> Option<&I::Item> {
        // Requires `&mut self`
        if self.peeked.is_some() {
            _ = self.peeked.insert(self.iter.next());
        }

        // Requires only `&self'
        let self_immutable: &Self = self;
        self_immutable.peeked.as_ref().unwrap().as_ref()
    }
}

Is there any way to express in Rust that the lifetime of the output reference is tied to the immutable variant of in input mutable reference?

[frozen meadow]

It doesn't seem so - I tried a few things but yeah, the compiler is keeping the &mut self alive for the duration of the data borrowed from it. Seems to be a limitation of the borrow checking system and actually has a section in the nomicon about this: https://doc.rust-lang.org/nomicon/lifetime-mismatch.html

One method of getting around it would be to pass the &self reference through as output from a function, and then use that for any further interactions

?play

#[derive(Debug, Default)]
struct Foo {
    i: u8
}

impl Foo {
    fn mutate_and_share(&mut self) -> (&u8, &Self) {
        self.i = 42;
        (&self.i, self)
    }

    fn share(&self) -> &u8 {
        &self.i
    }
}

fn main() {
    let mut foo = Foo::default();
    let (inner_borrow_1, pass_through) = foo.mutate_and_share();
    //let inner_borrow_2 = foo.share(); // this complains
    let inner_borrow_2 = pass_through.share();
    dbg!(inner_borrow_1);
    dbg!(inner_borrow_2);
}

[azure kernel]

[src/main.rs:22] inner_borrow_1 = 42
[src/main.rs:23] inner_borrow_2 = 42```

[frozen meadow]

But that relies on the function with the &mut Self passing the borrow through unfortunately

In your case though, as you mentioned that specific compiler error can most likely be fixed by implementing the next function in a different way