Mutliple mutable references to items in a larger structure - the best way

Hi

Assume I have a graph structure

struct Node;
struct Graph {
    nodes: Vec<RefCell<Node>>,
}

With this it is possible to get multiple mutable references to nodes as long as there are no references to the same node.

impl Graph {
    fn get_mut(&self, index: usize) -> RefMut<'_, Node> {
        self.nodes[index].borrow_mut()
    }
}

This is all well and good, however it is a bit more free than I would like.

You see this allows one to get mutable references to nodes even when holding only a non-mutable reference to the graph. It is safe of course since the RefCell guarantees this, but it makes for a more confusing code base when one cannot trust that methods taking a non-mut reference do in fact not mutate it.

I have been trying to fix this by using the signature below (i.e. just taking &mut self instead of &self)

impl Graph {
    fn get_mut(&mut self, index: usize) -> RefMut<'_, Node> {
        self.nodes[index].borrow_mut()
    }
}

However this makes it impossible to borrow multiple (different) nodes at the same time

let mut graph = Graph {
    nodes: vec![RefCell::new(Node{}), RefCell::new(Node{})]
};
let mut a = graph.get_mut(0);
let mut b = graph.get_mut(1);
a.mutate();
b.mutate();
error[E0499]: cannot borrow `graph` as mutable more than once at a time
   --> src/something.rs:933:17
    |
932 |     let mut a = graph.get_mut(0);
    |                 ----- first mutable borrow occurs here
933 |     let mut b = graph.get_mut(0);
    |                 ^^^^^ second mutable borrow occurs here
934 |     a.mutate();
    |     - first borrow later used here

Is there a way to convince the borrow checker fulfill the requirements below?

  1. Only allow the method to be used if you have a mutable reference
  2. Allow multiple mutable references to different nodes (dynamically checked by RefCell or some similar unsafe code).

My best attempt has involved using a trait that I only implement for &mut Graph. And while this does work, it cannot be used if you have a mutable value and not a reference, and it gives very uninformative error message if you try to use it on a &Graph (not mutable).

Don't think of it as mutable and immutable references. Their primary aspect is exclusive vs shared borrows.

There can only exist one exclusive-mutable reference at a time, so the compiler is absolutely right — you can't ask for two separate exclusive locks on the same object ( &mut self tells to put the exclusive lock on the entire self).

You can allow multiple exclusive borrows of different elements of the graph, but it's not possible to guarantee at compile time that get_mut will only give out non-overlapping borrows. This is usually worked around with things like mutable iterators, and they need unsafe internally.

2 Likes

Indeed. However ideally I would be able to convince the compiler that I only need that exclusive borrow for the duration of the get_mut call. The RefCell will guarantee that all other guarantees are met.

You can't. Lifetime of the returned object is tied to the lifetime it came from, so it "inherits" the exclusivity. I don't remember exactly the details why (something with variance?), but it's not a bug, it's necessary to prevent loopholes in safety guarantees.

That '_ is derived from &mut self lifetime. You can't make lifetimes out of thin air.

1 Like

I see :frowning:
Is there no way of doing this even with unsafe code?

In unsafe you can always transmute the borrow checker away.

Well, yes. But in this case the returned object (RefCell<'a,Node>) still needs a lifetime. And as you say I cannot create lifetimes out of thin air. The lifetime is tied to the graph, however the borrow checker should still allow other mutable references to other nodes.
So I'm not sure how transmute helps with this?

Thank you for your quick responses! :slight_smile:

If you are able to determine the indices you want mutable access to up front, you could do something like this: https://play.rust-lang.org/?version=stable&mode=debug&edition=2018&gist=d2760941dacdeb8c055275c8abdf1aeb

There's perhaps a more generic way to do this with Iterators, but I got buried in lifetime issues.

1 Like

This topic was automatically closed 90 days after the last reply. New replies are no longer allowed.