How to implement the next method on mutable Iterator if the Iterator has a lifetime?

Question

I want to implement a table type in Rust, so I have the code below:

use std::ops::{Index, IndexMut};

#[derive(Clone)]
pub struct Table<T>
where
    T: Clone,
{
    row: usize,
    col: usize,
    data: Vec<Vec<T>>,
}

impl<T> Table<T>
where
    T: Clone,
{
    pub fn new(row: usize, col: usize) -> Self {
        let mut t = Table {
            row,
            col,
            data: Vec::<Vec<T>>::with_capacity(row),
        };
        t.data.resize(row, Vec::<T>::with_capacity(col));
        t
    }

    pub fn size(&self) -> (usize, usize) {
        (self.row(), self.col())
    }

    pub fn col(&self) -> usize {
        self.col
    }

    pub fn row(&self) -> usize {
        self.row
    }

    pub fn cell_iter(&self) -> TableCellIter<T> {
        TableCellIter {
            table: self,
            row: 0,
            col: 0,
        }
    }

    pub fn cell_iter_mut(&mut self) -> TableCellIterMut<'_, T> {
        TableCellIterMut {
            table: self,
            row:0,
            col:0,
        }
    }
}

impl<T> Index<(usize, usize)> for Table<T>
where
    T: Clone,
{
    type Output = T;
    fn index(&self, (row, col): (usize, usize)) -> &Self::Output {
        if row >= self.row() {
            panic!("out of range")
        }
        &self.data[row][col]
    }
}

impl<T> IndexMut<(usize, usize)> for Table<T>
where
    T: Clone,
{
    fn index_mut(&mut self, (row, col): (usize, usize)) -> &mut Self::Output {
        while self.data.len() <= row {
            self.data.push(Vec::<T>::with_capacity(self.col()));
        }
        &mut self.data[row][col]
    }
}

pub struct TableCellIter<'a, T>
where
    T: Clone,
{
    table: &'a Table<T>,
    row: usize,
    col: usize,
}

impl<'a, T> Iterator for TableCellIter<'a, T>
where
    T: Clone,
{
    type Item = &'a T;

    fn next(&mut self) -> Option<Self::Item> {
        if self.col == self.table.col() {
            self.row += 1;
            self.col = 0;
        }
        if self.row >= self.table.row() {
            return None;
        }
        let ref cell = self.table[(self.row, self.col)];
        self.col += 1;
        Some(cell)
    }
}

pub struct TableCellIterMut<'a, T>
where
    T: Clone,
{
    table: &'a mut Table<T>,
    row: usize,
    col: usize,
}

impl<'a, T> Iterator for TableCellIterMut<'a, T>
where
    T: Clone,
{
    type Item = &'a mut T;

    fn next<'b: 'a>(&'b mut self) -> Option<Self::Item>
    {
        if self.col == self.table.col() {
            self.row += 1;
 self.col = 0;
        }
        if self.row >= self.table.row() {
            return None;
        }
        let ref mut cell = self.table[(self.row, self.col)];
        self.col += 1;
        Some(cell)
    }
}

Where the TableCellIter type works fine, the TableCellIterMut can not. The compiler warns me:

error[E0195]: lifetime parameters or bounds on method `next` do not match the trait declaration
   --> src/lib.rs:125:12
    |
125 |     fn next<'b: 'a>(&'b mut self) -> Option<Self::Item>
    |            ^^^^^^^^ lifetimes do not match method in trait

error: aborting due to previous error

For more information about this error, try `rustc --explain E0195`.
error: could not compile `sample`

But if I delete the lifetime bounds in the next of TableCellIterMut:

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

It seems the next's lifetime parameter can not be inffered:

error[E0495]: cannot infer an appropriate lifetime for lifetime parameter in function call due to conflicting requirements
   --> src/lib.rs:135:28
    |
135 |         let ref mut cell = self.table[(self.row, self.col)];
    |                            ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
    |
note: first, the lifetime cannot outlive the anonymous lifetime defined on the method body at 126:13...
   --> src/lib.rs:126:13
    |
126 |     fn next(&mut self) -> Option<Self::Item>
    |             ^^^^^^^^^
note: ...so that reference does not outlive borrowed content
   --> src/lib.rs:135:28
    |
135 |         let ref mut cell = self.table[(self.row, self.col)];
    |                            ^^^^^^^^^^
note: but, the lifetime must be valid for the lifetime `'a` as defined on the impl at 119:6...
   --> src/lib.rs:119:6
    |
119 | impl<'a, T> Iterator for TableCellIterMut<'a, T>
    |      ^^
note: ...so that the types are compatible
   --> src/lib.rs:127:5
    |
127 | /     {
128 | |         if self.col == self.table.col() {
129 | |             self.row += 1;
130 | |  self.col = 0;
...   |
137 | |         Some(cell)
138 | |     }
    | |_____^
    = note: expected `Iterator`
               found `Iterator`

error: aborting due to previous error

My question is, Why the next in the TableCellIter is right, while wrong in the TableCellIterMut?

How can I implement the next correctly?

Answer 1

The item references returned by iterators can have overlapping lifetimes, since, as your noticed, their lifetimes can't be tied to the lifetime of the self parameter to next(). If the next() method were to return the same mutable reference twice, you'd end up with multiple mutable references to the same object, which is not allowed. This means your code is only safe if all the references returned by it are disjoint, which is the case if the iterator is implemented correctly. However, this guarantee can only be derived by reasoning over the semantics of the code, and not by just looking at the prototypes of the involved function calls. This is something the borrow checker can't do (in fact, it can be proven to be impossible in the general case), so the compiler rejects the code.

For immutable references, this is not a problem, since having multiple immutable references to the same object is allowed.

There are several ways of solving this problem. My recommendation would be to change the data representation from Vec<Vec<T>> to a flat Vec<T>, and implement the indexing operations accordingly. This will make your code overall easier and at the same time far more efficient. The iterator could then be implemented by deferring to the existing iterators on Vec<>.

If you want to keep the Vec<Vec<T>> structure, you can still make use of the existing iterators on Vec:

pub fn cell_iter_mut(&mut self) -> impl Iterator<Item = &mut T> {
    self.data.iter_mut().flat_map(|row| row.iter_mut())
}

Note that you don't even need to explicitly define a custom iterator type. A similar implementation is possible for the iter() method.

If you want to create a completely custom container type from scratch, you usually need to use unsafe code for the mutable iterators, but in this case it's much better to rely on the iterator implementations for Vec (which use unsafe code internally).