(Safe) rust is known for its rigorous enforcement of borrowing rules: Any piece of memory is always owned by exactly one scope (that is responsible for freeing its memory at some point) and can in addition be in use by either a single scope that is allowed to modify it (mutable borrow) OR by arbitrary many that have read-only access (immutable borrow). If this sounds weird to you I encourage you to pause at this point and read up on it for example in the Rust Book.

In this point I want to discuss a particular case where we have a piece of code that needs to both read from a data structure but also update it. We’ll first discuss the common and easy cases and later show a more complex example of how to implement a (sort of) transaction feature for your own data structures to alleviate borrow-checker pains for all its users.

Modify a vector while iterating

Lets say, we have a simple vector and want to modify its elements one by one. A simple way we can do this is like this:

let mut v = vec![1, 2, 3, 4];

for x in v.iter_mut() {
    *x = *x + 1;
}

This actually works like intended: The body of the for loop receives a mutable reference to one of the vectors elements in each iteration which it can both read and modify. Since each element is “part of” the vector, this also “locks” the whole vector, so we could not (easily) do anything else to the vector other than reading and/or modifying this single element.

No touching the vector!

For example what we can (and should) absolutely not do is pushing (i.e. appending) elements to v while iterating. And this is good! If you know a bit how vectors are implemented internally, you are probably aware that when you push elements to them they might end up moving all their data to some other place in memory. This would break any existing references and mess up the ongoing iteration, and its good that rust protects us from this.

But even on a more abstract level modifying v while iterating over it is ill-defined. For pushing we might agree on that we’d like iteration to continue and use the new elements right away, but what exactly do you even expect to happen if you delete an element while iterating? What should happen if you delete the element before the current one or the one that you are still on? There is no obvious answer to this and it depends on what you are doing. Even if you have a clear idea it would probably be hard to follow the code that does something like this.

What about other elements?

Lets say for modifying an element, we need to look at the element left of it also. The obvious approach does not work:

let mut v = vec![1, 2, 3, 4];

for (i, x) in v.iter_mut().enumerate() {
    if i > 0 {
         *x = *x + v[i - 1]; // cannot borrow `v` as immutable because its also borrowed as mutable
    }
}

This will not compile. As we established above, v is already borrowed, so we cannot have another immutable reference to it. Written in this way, Rust needs to assume that we are changing v in some way that might affect the reference v[i - 1], since by iterating we mutably borrow the whole vector (even if we do it in a way that can only affect an element at the same time and not, eg., push).

So what can be done about it? Well, there is a couple of options. For vectors specifically, we could just iterate over their indices only and then borrow individual elements as we please and if need be copy them around. A pragmatic solution would look like this:

let mut v = vec![1, 2, 3, 4];  
for i in 0..v.len() {
     if i > 0 {
         v[i] += v[i - 1];
     }
}

And there is nothing wrong with this from a memory safety perspective.

By the way have you guessed already how v looks after this operation? If you think its [1, 2+1, 3+2, 4+3] i.e. [1, 3, 5, 7], think again! As we are iterating in forwards order we are actually using the already changed elements in our updates, so what we compute is [1, 2+1, 3+2+1, 4+3+2+1] i.e. [1, 3, 6, 10]. If this is what you want, perfect! For a simple 1-d vector perhaps being helped out with a few lines of documentation the confusion about this might be considered not severe. If you do not want your updates to affect your output you may (in this specific case only!) just change the iteration order.

But what if for your operation this doesn’t work? What if what you are implementing uses neighbors in both directions (like a convolution)? What if v is not just a simple 1-d vector but something more complex? What if the iteration order is harder to reason about or out of your control? What if halfway through iterating you may need to abort the operation and don’t want to leave behind a half-updated vector?

Transactional Data Structures

Lets assume a somewhat more complex scenario: For a game, we have some tilemap data (think a 2d array of integers) with some internal storage that should stay encapsulated. In addition, we have some code that for some random positions in the map needs to do updates. The random positions come from some other place in our code and tell us where changes happened (eg the player built something there, etc..). The updates update one tile at a time based on its neighbors (we don’t care about the details but for illustration think of computing how some fluids distribute on the tilemap or similar).

const SIZE: (i32, i32) = (1024, 1024);

struct Tilemap {
    data: Vec<u32> // this is considered private to update
}

impl Tilemap {
    fn get(&self, (x, y): (i32, i32)) -> u32 {
        todo!()
    }

    fn set(&mut self, (x, y): (i32, i32), v: u32) {
        todo!()
    }
}

fn main() {
    let mut map = Tilemap { data: vec![] };
    update(&mut map, [(3_i32, 4_i32), (832, 123)].iter().copied());
}

fn update(map: &mut Tilemap, positions: impl Iterator<Item=(i32, i32)>) {
  todo!()
}

Transaction Interface

What we would like to have is the concept of a Transaction, that is, a way to update our map with the following properties:

• Atomicity: A logical group of updates should be applied “all at once” or not at all, we don’t want our data structure to be half-updated ever.
• Consistency: The Tilemap implementation should have a way to run some assertions on the update, eg. whether the amount of liquid is conserved, etc…
• Freedom of Self-Interference: In lack of a better term, while preparing our transaction we want to be able to read from the original in its original (as opposed to partially updated) state to avoid confusion.
• Performance: We want to avoid copying the whole map if possible, updates will usually be sparse.

Note that this list is completely made up by things that I happen to find useful. You may after the first two points be reminded of ACID in database transactions, but here we do not care about isolation or durability, although I’m sure that could easily be added later.

Also for databases the definitions of eg. atomicity are usually much stricter due to the “durability” aspect: If there is a power outage during writing the data to disk, on next boot we want the whole transaction to be either completely there or not at all. Luckily we don’t have to worry about all that here. As such when we say “transaction” just be aware that we define the word somewhat arbitrarily.

Lets start from the interface and work our way “downwards”:

fn update(map: &mut Tilemap, positions: impl Iterator<Item=(i32, i32)>) {
    let mut tr = map.transaction();

    for (x, y) in positions {
        if x <= 0 || y <= 0 || x >= SIZE.0 || y >= SIZE.0 {
            // ignore border tiles for now
            continue;
        }

        // example: read some neighboring positions
        let a = map.get((x - 1, y + 1));

        // example: set value at position
        tr.set((x, y), a + 1);
    }

    tr.commit();
}

What do we expect to happen here? map.transaction() gives us a “transaction” (whose type we still need to define), which we later use to express our updates. The idea here is that tr.set does not update the map directly but collects a “TODO list” of updates for later. When we finally call tr.commit(), the map will be updated all in one go.

This gives us the atomicity and consistency and freedom of self-interference: Atomicity: In commit() the transaction is applied to the map “all at once” so if commit is implemented correctly, there can never be a half-updated state visible to any other code. Consistency: Having the commit() call also gives as a place to run some checks/assertions on the transaction, potentially discarding it (or taking other measures) if it violates a property the Tilemap cares about. Freedom of self-interference: map is not changed before .commit() so whatever commit does, it cannot possibly affect the map while we are building up the transaction.

Transaction Implementation

Ok so what is tr then? It needs some way of collecting changes for our map, for .set() to make any sense. Also, notice that in tr.commit() we did not need to pass in the map again so it needs to hold a mutable borrow to that:

use std::collections::HashMap;

// ...

struct Transaction<'a> {
    map: &'a mut Tilemap,
    changes: HashMap<(i32, i32), u32>
}

impl Transaction<'_> {
    fn set(&mut self, p: (i32, i32), v: u32) {
        self.changes.insert(p, v);
    }
}

But oh noes! This breaks our update function! Since tr now holds a mutable borrow of map, the call to map.get() can not obtain an immutable borrow.

        // example: read some neighboring positions
        let a = map.get((x - 1, y + 1)); // map is already borrowed by tr!

The solution to this is to pipe the read access to the map through the transaction which is currently the one with access to the map. Like this:

struct Transaction<'a> {
    map: &'a mut Tilemap,
    changes: HashMap<(i32, i32), u32>
}

impl Transaction<'_> {
    fn get(&self, p: (i32, i32)) -> u32 {
        self.map.get(p)
    }

    fn set(&mut self, p: (i32, i32), v: u32) {
        self.changes.insert(p, v);
    }
}

fn update(...) {
  // ...
        // example: read some neighboring positions
        // let a = map.get((x - 1, y + 1)); // this wouldn't work: map is already borrowed by tr!
        let a = tr.get((x - 1, y + 1)); // this does!
 // ...
}

Lastly, we need to implement Tilemap.transaction() and Transaction.commit(), both a relatively straight forward:

impl Tilemap {
    // ...

    fn transaction(&'_ mut self) -> Transaction<'_> {
        Transaction {
            map: self,
            changes: HashMap::new()
        }
    }
}

impl Transaction<'_> {
    // ...

    fn commit(self) {
        for (p, v) in self.changes.iter() {
            self.map.set(*p, *v);
        }
    }
}

Note that in commit we chose to accept a self rather than a &mut self. This ensures that after commit no method can be called anymore on tr.

And voila! There you have a transaction for your custom type that collects changes and applies them. Your changes can be commited or discarded (simply by not calling commit), there is zero confusion about how much of a change is currently applied (either all of it or nothing) and reading and writing are decoupled, i.e. there is no self-interference. Furthermore we did this without the need to create a complete copy of the data, but of course performance depends heavily on how your data looks and what your most frequent update patterns are (eg. a copy might actually be better if you are updating most tiles anyway).

As a bonus you have a record of exactly where your data structure was changed which in the game example could inform the positions argument to update in the next frame.

Here is the complete code:

use std::collections::HashMap;


const SIZE: (i32, i32) = (1024, 1024);

struct Tilemap {
    data: Vec<u32>
}

impl Tilemap {
    fn get(&self, (x, y): (i32, i32)) -> u32 {
        todo!()
    }

    fn set(&mut self, (x, y): (i32, i32), v: u32) {
        todo!()
    }

    fn transaction(&'_ mut self) -> Transaction<'_> {
        Transaction {
            map: self,
            changes: HashMap::new()
        }
    }
}

struct Transaction<'a> {
    map: &'a mut Tilemap,
    changes: HashMap<(i32, i32), u32>
}

impl Transaction<'_> {
    fn get(&self, p: (i32, i32)) -> u32 {
        self.map.get(p)
    }

    fn set(&mut self, p: (i32, i32), v: u32) {
        self.changes.insert(p, v);
    }

    fn commit(self) {
        for (p, v) in self.changes.iter() {
            self.map.set(*p, *v);
        }
    }
}

fn main() {
    let mut map = Tilemap { data: vec![] };
    update(&mut map, [(3_i32, 4_i32), (832, 123)].iter().copied());
}

fn update(map: &mut Tilemap, positions: impl Iterator<Item=(i32, i32)>) {
    let mut tr = map.transaction();

    for (x, y) in positions {
        if x <= 0 || y <= 0 || x >= SIZE.0 || y >= SIZE.0 {
            // ignore border tiles for now
            continue;
        }

        // example: read some neighboring positions
        let a = tr.get((x - 1, y + 1));

        // example: set value at position
        tr.set((x, y), a + 1);
    }

    tr.commit();
}

Where to go from here?

From here on there is several improvements we can make:

• If you find yourself forwarding a lot of calls from the transaction to the map, check out the delegate crate to safe yourself some typing
• In my case I rarely needed to discard and would rather .commit() by default. You can do this easily by implementing Drop for Transaction to call self.commit(). You have to change commit to accept a &mut self though as technically it still needs to give self back to drop (even if that is just dropping it afterwards).
• Implement discard(self) { } (this is already the whole function, discard doesn’t need to do anything other than consuming the transaction)
• Transaction is also a nice place for several convenience methods such as a function that maps a tile to a different one depending on its neighbors (convolution style) etc..
• In commit you can implement arbitrary consistency checks of the transaction itself or the resulting updated map
• If you want to get really fancy you could allow multiple parallel transactions in flight (and reference the map via eg a Mutex or dont reference the map at all but have commit be a method of Tilemap. This does not mix well with the auto-commit feature though). This requires that you have a clear idea on how to resolve conflicts (does the order transactions are applied in matter? Can we confine each transaction to a limited exclusive region of the map?)

Have fun!