Access immutable methods while iterating over a mutable member

Question

While learning about iterators in Rust, I created the following struct to hide the implementation of a two-dimensional collection:

use std::slice::{Items, MutItems};
use std::vec::{Vec};

pub struct Table<T> {
    pub width: uint,
    pub height: uint,
    data: Vec<T>
}

impl<T: Clone> Table<T> {
    pub fn from_elem(width: uint, height: uint, value: T) -> Table<T> {
        Table {
            width: width,
            height: height,
            data: Vec::from_elem(width * height, value)
        }
    }
}

impl<T> Table<T> {
    pub fn get_row_column(&self, index: uint) -> (uint, uint) {
        (index / self.width, index % self.width)
    }

    pub fn iter<'a>(&'a self) -> Items<'a, T> {
        self.data.iter()
    }

    pub fn iter_mut<'a>(&'a mut self) -> MutItems<'a, T> {
        self.data.iter_mut()
    }
}

The goal of the iter and iter_mut methods was that the user of this struct wouldn't need to worry about whether the data was stored in a row-major or column-major format; the iterator would simply provide the elements in the most efficient order.

However, in using this data structure, I often needed to know the particular row and column in order to get some external data:

fn get_input(row: uint, column: uint) -> uint {
    row * 10 + column / 2
}

fn main() {
    let mut table = Table::from_elem(640, 480, 0u);

    for (index, value) in table.iter_mut().enumerate() {
        let (row, column) = table.get_row_column(index);
        *value = get_input(row, column);
    }
}

But as soon as I try to call the get_row_column method, I get the following compiler error:

main.rs:56:33: 56:38 error: cannot borrow `table` as immutable because it is also borrowed as mutable
main.rs:56             let (row, column) = table.get_row_column(index);
                                           ^~~~~
main.rs:55:31: 55:36 note: previous borrow of `table` occurs here; the mutable borrow prevents subsequent moves, borrows, or modification of `table` until the borrow ends
main.rs:55         for (index, value) in table.iter_mut().enumerate() {
                                         ^~~~~
main.rs:59:6: 59:6 note: previous borrow ends here
main.rs:55         for (index, value) in table.iter_mut().enumerate() {
main.rs:56             let (row, column) = table.get_row_column(index);
main.rs:57             *value = get_input(row, column);
main.rs:58         }
main.rs:59     }
               ^

What's the right way to accomplish what I'm trying to do here? I can add a set method that takes the row and column numbers and explicitly loop over row and column indices, but then the user has to worry about row-major vs. column-major ordering:

impl<T> Table<T> {        
    fn get_index(&self, row: uint, column: uint) -> uint {
        row * self.width + column
    }

    pub fn set(&mut self, row: uint, column: uint, value: T) {
        let index = self.get_index(row, column);
        self.data[index] = value;
    }
}

fn main() {
    let mut table = Table::from_elem(640, 480, 0u);

    for row in range(0, table.height) {
        for column in range(0, table.width) {
            table.set(row, column, get_input(row, column));
        }
    }
}

Is there a convention or best-practice for mutating internal members of a struct while still allowing access to the immutable members and methods? Or does that completely violate the safety guarantees?

Answer 1

Matthieu M. has the right idea: use the iterator to return the row and column, rather than directly expose index. Unfortunately, it appears that closures in Rust are currently stack allocated and cannot extend beyond the stack frame in which they were created, so his proposed solution doesn't compile.

While using the iterator adapters is extremely convenient and succinct, we can still do it the long way by creating new iterators objects.

The key is to create an iterator that keeps track of the context we need, which in this case is the dimensions of the table:

pub struct TableItems<'a, T: 'a> {
    iter: Items<'a, T>,
    width: uint,
    height: uint
}

impl<'a, T> Iterator<&'a T> for TableItems<'a, T> {
    #[inline]
    fn next(&mut self) -> Option<&'a T> {
        self.iter.next()
    }
}

This struct contains the Items iterator provided by the slice module, along with the width and height from the table. Implementing the Iterator trait is as easy as passing along the call to next to the internal iterator.

The TableItems struct only returns immutable references, but we can create a similar one for mutable references:

pub struct MutTableItems<'a, T: 'a> {
    iter: MutItems<'a, T>,
    width: uint,
    height: uint
}

impl<'a, T> Iterator<&'a mut T> for MutTableItems<'a, T> {
    #[inline]
    fn next(&mut self) -> Option<&'a mut T> {
        self.iter.next()
    }
}

Then we just need to add a way to pass the dimensions from the Table object into the iterators:

impl<T> Table<T> {
    pub fn iter<'a>(&'a self) -> TableItems<'a, T> {
        TableItems {
            iter: self.data.iter(),
            width: self.width,
            height: self.height
        }
    }

    pub fn iter_mut<'a>(&'a mut self) -> MutTableItems<'a, T> {
        MutTableItems {
            iter: self.data.iter_mut(),
            width: self.width,
            height: self.height
        }
    }
}

Now, these iterators by themselves don't really gain us anything; they return the values of the Table, but we still don't have the row and column. To accomplish that, we can add our own iterator adapter that mimics the Enumerate trait from the iter module by incrementing separate counts for the current row and column:

impl<'a, A, T: Iterator<A>> Iterator<((uint, uint), A)> for TableEnumerate<T> {
    fn next(&mut self) -> Option<((uint, uint), A)> {
        match self.iter.next() {
            Some(value) => {
                let ret = Some(((self.row_count, self.column_count), value));

                self.column_count += 1;
                if self.column_count == self.width {
                    self.row_count += 1;
                    self.column_count = 0;
                }
                ret
            },
            None => None
        }
    }

    #[inline]
    fn size_hint(&self) -> (uint, Option<uint>) {
        self.iter.size_hint()
    }
}

This adapter is generic, so it can be used for either TableItems or MutTableItems (or anything else we choose to come up with in the future).

The last step is to create methods that return an instance of TableEnumerate:

impl<'a, T> TableItems<'a, T> {
    pub fn enumerate_2d(self) -> TableEnumerate<TableItems<'a, T>> {
        let width = self.width;
        let height = self.height;

        TableEnumerate {
            iter: self,
            width: width,
            height: height,
            row_count: 0,
            column_count: 0
        }
    }
}

impl<'a, T> MutTableItems<'a, T> {
    pub fn enumerate_2d(self) -> TableEnumerate<MutTableItems<'a, T>> {
        let width = self.width;
        let height = self.height;

        TableEnumerate {
            iter: self,
            width: width,
            height: height,
            row_count: 0,
            column_count: 0
        }
    }
}

I would have loved to have named these enumerate, but it appears that the compiler finds the Iterator implementation of enumerate before this one.

With this complete solution, the table can be acessed like so:

fn get_input(row: uint, column: uint) -> uint {
    row * 10 + column / 2
}

fn main() {
    let mut table = Table::from_elem(640, 480, 0u);

    for ((row, column), value) in table.iter_mut().enumerate_2d() {
        *value = get_input(row, column);
    }
}

Answer 2

I would argue that the issue here is one of leaky abstraction: index should never be exposed to the user to start with.

Therefore, you would need to change the interface to directly provide (row, column) instead of index when iterating, and then usage would be straightforward.

Something like:

use std::iter::{Enumerate, Map}

impl<T> Table<T> {
    // Additions
    pub fn iter_enum<'a>(&'a self) -> Map<'a, (uint, &'a T), ((uint, uint), &'a T), Enumerate<Items<'a, T>>> {
        self.iter().enumerate().map(|(i, v)| ((i / self.width, i % self.width), v)
    }

    pub fn iter_mut_enum<'a>(&'a mut self) -> Map<'a, (uint, &'a mut T), ((uint, uint), &'a mut T), Enumerate<MutItems<'a, T>>> {
        self.iter_mut().enumerate().map(|(i, v)| ((i / self.width, i % self.width), v)
    }
}

Note: I wish for C++ template aliases feature a lot, here.

Answer 3

This isn't a mutable-immutable issue, it's just a double-borrow. If the inner method call was an &mut self method you would have the same issues. You haven't lost access to the immutable methods, you have lost access to all methods as long as value is in scope, since value is a borrow into the table.

While it's not happening in this particular case, having multiple aliases to the piece being iterated over can lead to iterator invalidation.

In this case, use map to do the calculations:

fn main() {
    let mut table = Table::from_elem(640, 480, 0u);
    let width = table.width;

    for (value, row, column) in table.iter_mut().enumerate().map(|(i,v)| (v, i / width, i % width) ) {
        *value = get_input(row, column);
    }
}

playpen

Making get_row_column a separate function would help, too.