How to implement a simple 2D array using a closure?

I need a 2D array, but I don’t want to introduce external dependencies like ndarray, so I want to write one myself.

I could write something like this (playground link):

struct Array<T> {
    data: Vec<T>,
    columns: usize,
}

impl<T> Array<T> {
    fn get_mut(&mut self, i: usize, j: usize) -> &mut T {
        &mut self.data[self.columns * i + j]
    }
}

fn main() {
    let rows = 5;
    let columns = 7;

    let mut array = Array {
        data: vec![0; rows * columns],
        columns,
    };

    assert_eq!(*array.get_mut(3, 4), 0);
}

This one works, but I think this is too complicated, I want something quick and simple, like this (playground link):

fn main() {
    let rows = 5;
    let columns = 7;

    let mut data = vec![0; rows * columns];
    let mut array = move |i: usize, j: usize| &mut data[columns * i + j];

    assert_eq!(*array(3, 4), 0);
}

But this one does not compile due to lifetime error:

   Compiling playground v0.0.1 (/playground)
error[E0495]: cannot infer an appropriate lifetime for lifetime parameter in function call due to conflicting requirements
 --> src/main.rs:6:52
  |
6 |     let mut array = move |i: usize, j: usize| &mut data[columns * i + j];
  |                                                    ^^^^^^^^^^^^^^^^^^^^^
  |
note: first, the lifetime cannot outlive the lifetime '_ as defined on the body at 6:21...
 --> src/main.rs:6:21
  |
6 |     let mut array = move |i: usize, j: usize| &mut data[columns * i + j];
  |                     ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
note: ...so that closure can access `data`
 --> src/main.rs:6:52
  |
6 |     let mut array = move |i: usize, j: usize| &mut data[columns * i + j];
  |                                                    ^^^^
note: but, the lifetime must be valid for the expression at 8:16...
 --> src/main.rs:8:16
  |
8 |     assert_eq!(*array(3, 4), 0);
  |                ^^^^^^^^^^^^
note: ...so that pointer is not dereferenced outside its lifetime
 --> src/main.rs:8:16
  |
8 |     assert_eq!(*array(3, 4), 0);
  |                ^^^^^^^^^^^^

I don’t understand why this happens. I thought a closure is just an instance of some anonymous data structure with captured variables as its members. Why can’t the compiler compile the closure to something like the the Array structure in my first example?

You are trying to return a reference to something stored in that anonymous struct, which is something you can't do.

Remove the move keyword and it should work.

Even after removing the move keyword, the code still does not compile.

You can't do this. Link since the closurr can't share references to its captured things, and since it owning the vec and having a mutable reference to it are both exclusive access in this case, it doesn't matter whether you do it either way.

This would be the code I'd use:

fn main() {
    let rows = 7;
    let columns = 8;
    
    let data = vec![0; rows * columns];
    let array = |i: usize, j: usize| -> usize {
        data[i + j * columns]
    };
}

It doesn't compile, because it's not safe per Rust's definition of safety, and enables Undefined Behavior.

let a = array(0,0);
let b = array(0,0);

This code would create two exclusive references to the same location in memory, and violate fundamental no-mutable-aliasing guarantee of Rust.

You can have such closure with shared references only. For exclusive+mutable access you have to create an interface that will have a guarantee that it can never give the same array element twice. split_at_mut() and iter_mut() work like that.

1 Like

It still does not compile even if I change the code to use non-mutable references.

Non-move works:

fn main() {
    let rows = 5;
    let columns = 7;

    let mut data = vec![0; rows * columns];
    let mut array = |i: usize, j: usize| &data[columns * i + j];

    assert_eq!(*array(3, 4), 0);
}

because the closure is then equivalent of fn<'a>(/* from scope &'a Vec*/) -> &'a usize.

or by value works:

    let array = move |i: usize, j: usize| data[columns * i + j];

    assert_eq!(array(3, 4), 0);

because closure is then equivalent of fn() -> usize.

The move + reference combo doesn't work, because with data owned by the closure there's no way to ensure the reference will be valid. Non-borrowing closure is movable and can be moved/destroyed. After it returns a reference, it could be moved to another thread, or it could modify the data in a way that invalidates the previous reference. Having closure borrow the data freezes it as read-only and attaches a lifetime to it that can be reused for returned references.

fn main() {
    let rows = 5;
    let columns = 7;

    let mut data = vec![0; rows * columns];
    let array = move |i: usize, j: usize| data[columns * i + j];

    let tmp = array(3,4);
    drop(array); // if array owns the data, this destroys the data
    assert_eq!(tmp, 0); // if this was a reference, it'd be use-after-free
}

Is it possible for the compiler to mark the returned reference to the captured variable as a borrowed reference from the closure so that the returned reference cannot out live the closure? In this way, we can eliminate the undefined behavior with the borrow checker.

Here are some examples to show what I mean.

Dropping the closure while being borrowed is an error:

fn main() {
    let rows = 5;
    let columns = 7;

    let mut data = vec![0; rows * columns];
    let mut array = move |i: usize, j: usize| &mut data[columns * i + j];

    let tmp = array(3, 4); // `tmp` is a reference borrowed from the closure `array` and cannot out live `array`.
    drop(array); // Error because `array` is being dropped while being borrowed.
    assert_eq(tmp, 0);
}

Mutably borrow the closure multiple times at the same time is a error:

fn main() {
    let rows = 5;
    let columns = 7;

    let mut data = vec![0; rows * columns];
    let mut array = move |i: usize, j: usize| &mut data[columns * i + j];

    let tmp_1 = array(3, 4); // OK.
    let tmp_2 = array(2, 3); // Error since `array` is already being mutably borrowed.
    assert_eq(tmp_1, 0);
}

Immutably borrow the closure multiple times is fine:

fn main() {
    let rows = 5;
    let columns = 7;

    let data = vec![0; rows * columns];
    let array = move |i: usize, j: usize| &data[columns * i + j];

    let tmp_1 = array(3, 4); // OK.
    let tmp_2 = array(2, 3); // OK since we only have immutable borrows from the closure.
    assert_eq(tmp_1, 0);
    assert_eq(tmp_2, 0);
}

If the previous mutable borrow ends, you can mutably borrow the closure again:

fn main() {
    let rows = 5;
    let columns = 7;

    let mut data = vec![0; rows * columns];
    let mut array = move |i: usize, j: usize| &mut data[columns * i + j];

    assert_eq(*array(3, 4), 0); // OK. This line borrows the closure and then the borrow ends.
    *array(3, 4) = 5; // OK.
    assert_eq(*array(3, 4), 5); // OK.
}

This requires GATs, generic associated types.