Trouble with lifetimes on iterator that mutates iterable

Question

I'm making a "sorted iterator" which takes a slice of unsorted items and outputs them in sorted order and sorts the underlying slice as you go using heap sort. The trouble is there is a conflicting lifetime in the iterator implementation.

Here is the relevant code:

struct SortedIterator<'a, T:'a+Ord> {
    heap: &'a mut [T],
    iteration: usize
}

fn getChildren(pos: usize, total_size: usize) -> (usize, usize) {
    let diff = 2*(total_size - pos);
    (total_size - diff - 1, total_size - diff - 2)
}

impl<'a, T:'a+Ord> Iterator for SortedIterator<'a, T> {
    type Item = &'a T;
    fn next(&mut self) -> Option<Self::Item> {
        if self.iteration < self.heap.len() {
            self.heap.swap(self.iteration, self.heap.len());
            self.iteration += 1;

            // restore heap here
            let mut swapped = true;
            let mut current_pos = self.heap.len() -1;
            while swapped {
                swapped = false;
                let (left, right) = getChildren(current_pos, self.heap.len() - 1);
                if self.iteration > left { 
                    // it's children have entered into the sorted part of the array
                    // so we're actually at a leaf
                    continue;
                } else if self.iteration > right {
                    // left is the last child, potentially swap it with parent and then
                    // we are done iterating
                    if self.heap[right] < self.heap[current_pos] {
                        self.heap.swap(right, current_pos);
                    }
                } else if self.heap[left] < self.heap[current_pos] || self.heap[right] < self.heap[current_pos] {
                    swapped = true;
                    // swap parent with lower item of the two children, update position in the slice
                    // then iterate again
                    if self.heap[left] < self.heap[right] {
                        self.heap.swap(left, current_pos);
                        current_pos = left;
                    } else {
                        self.heap.swap(right, current_pos);
                        current_pos = right;
                    }
                }
            }
            // the trouble occurs here, it says it 
            // expects <SortedIterator<'a, T> as std::iter::Iterator>
            // found <SortedIterator<'_, T> as std::iter::Iterator>
            Some(&self.heap[self.iteration - 1])
        } else {
            None
        }
    }
}

I'm just not sure where I might need an extra annotation to solve the lifetime confusion for Rust.

Here is the error from cargo check

error[E0495]: cannot infer an appropriate lifetime for lifetime parameter in function call due to conflicting requirements
  --> src\lib.rs:73:19
   |
73 |             Some(&self.heap[self.iteration - 1])
   |                   ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
   |
note: first, the lifetime cannot outlive the anonymous lifetime defined here...
  --> src\lib.rs:36:13
   |
36 |     fn next(&mut self) -> Option<Self::Item> {
   |             ^^^^^^^^^
note: ...so that reference does not outlive borrowed content
  --> src\lib.rs:73:19
   |
73 |             Some(&self.heap[self.iteration - 1])
   |                   ^^^^^^^^^
note: but, the lifetime must be valid for the lifetime `'a` as defined here...
  --> src\lib.rs:34:6
   |
34 | impl<'a, T:'a+Ord> Iterator for SortedIterator<'a, T> {
   |      ^^
note: ...so that the types are compatible
  --> src\lib.rs:36:46
   |
36 |       fn next(&mut self) -> Option<Self::Item> {
   |  ______________________________________________^
37 | |         if self.iteration < self.heap.len() {
38 | |             self.heap.swap(self.iteration, self.heap.len());
39 | |             self.iteration += 1;
...  |
76 | |         }
77 | |     }
   | |_____^
   = note: expected `<SortedIterator<'a, T> as Iterator>`
              found `<SortedIterator<'_, T> as Iterator>`

Answer 1

The reason for the error is as in How can I create my own data structure with an iterator that returns mutable references?. Read there for an expansive explanation, but in short, this code:

impl<'a, T: 'a + Ord> Iterator for SortedIterator<'a, T> {
    type Item = &'a T;
    fn next(&mut self) -> Option<Self::Item> {
        Some(&self.heap[self.iteration - 1])
    }
}

Has the same form as the following code (and gives similar error):

struct S<'a>(&'a mut i32);
impl<'a> S<'a> {
    fn f<'b>(&'b mut self) -> &'a i32 { &*self.0 }
}

I explicitly annotated 'b because it makes it easy to see what went wrong: you cannot take a reference to self with lifetime 'b, which may be shorter than 'a, but return a reference that can live for the whole 'a. This will allow callers to hold the resulting reference longer than they should be able to, and violating the "aliasable xor mutable" rule by creating an overlapping mutable reference:

// (Pseudo-Rust)

'a: {
    let mut i: i32 = 123;
    let mut s: S<'a> = S(&'a mut i);
    let r1: &'a i32 = 'b: {
        let s_r: &'b mut S = &'b mut S;
        S::<'a>::f::<'b>(s_r)
        // Reference `s_r` is destroyed here, but the returned value is still alive!
    };
    let r2: &'a mut i32 = &'a mut s;
    // Now we got `r1` and `r2` both pointing to `i` while `r2` is mutable, boom!
}

The solution is to split the slice, and work only with the remaining part while releasing the sorted part, element by element, to the wild. Because we don't hold it, nothing can go wrong. The compiler cannot track that automatically, and so we use std::mem::take(). I will not post the full code here, but the general idea is like:

fn next(&mut self) -> Option<Self::Item> {
    // This allow us to get rid of the length check (but you still can check then `unwrap()`).
    let (first, heap) = std::mem::take(&mut self.heap).split_first_mut()?;
    self.heap = heap;
    // Calculations and sorting...
    Some(first)
}