Cannot borrow as immutable because it is also borrowed as mutable when implementing an ECS

Question

I am trying to write a simple ECS:

struct Ecs {
    component_sets: HashMap<TypeId, Box<dyn Any>>,
}

impl Ecs {
    pub fn read_all<Component>(&self) -> &SparseSet<Component> {
        self.component_sets
            .get(&TypeId::of::<Component>())
            .unwrap()
            .downcast_ref::<SparseSet<Component>>()
            .unwrap()
    }

    pub fn write_all<Component>(&mut self) -> &mut SparseSet<Component> {
        self.component_sets
            .get_mut(&TypeId::of::<Component>())
            .unwrap()
            .downcast_mut::<SparseSet<Component>>()
            .unwrap()
    }
}

I am trying to get mutable access to a certain component while another is immutable. This testing code triggers the error:


fn testing() {
    let all_pos = { ecs.write_all::<Pos>() };
    let all_vel = { ecs.read_all::<Vel>() };

    for (p, v) in all_pos.iter_mut().zip(all_vel.iter()) {
        p.x += v.x;
        p.y += v.y;
    }
}

And the error

error[E0502]: cannot borrow `ecs` as immutable because it is also borrowed as mutable
   --> src\ecs.rs:191:25
    |
190 |         let all_pos = { ecs.write_all::<Pos>() };
    |                         --- mutable borrow occurs here
191 |         let all_vel = { ecs.read_all::<Vel>() };
    |                         ^^^ immutable borrow occurs here

My understanding of the borrow checker rules tells me that it's totally fine to get references to different component sets mutably or immutably (that is, &mut SparseSet<Pos> and &SparseSet<Vel>) since they are two different types. In order to get these references though, I need to go through the main ECS struct which owns the sets, which is where the compiler complains (i.e. first I use &mut Ecs when I call ecs.write_all and then &Ecs on ecs.read_all).

My first instinct was to enclose the statements in a scope, thinking it could just drop the &mut Ecs after I get the reference to the inner component set so as not to have both mutable and immutable Ecs references alive at the same time. This is probably very stupid, yet I don't fully understand how, so I wouldn't mind some more explaining there.

I suspect one additional level of indirection is needed (similar to RefCell's borrow and borrow_mut) but I am not sure what exactly I should wrap and how I should go about it.

Update

Solution 1: make the method signature of write_all take a &self despite returning a RefMut<'_, SparseSet<Component>> by wrapping the SparseSet in a RefCell (as illustrated in the answer below by Kevin Reid).

Solution 2: similar as above (method signature takes &self) but uses this piece of unsafe code:

fn write_all<Component>(&self) -> &mut SparseSet<Component> {
    let set = self.component_sets
        .get(&TypeId::of::<Component>())
        .unwrap()
        .downcast_ref::<SparseSet<Component>>()
        .unwrap();
        
    unsafe {
        let set_ptr = set as *const SparseSet<Component>;
        let set_ptr = set_ptr as *mut SparseSet<Component>;
        &mut *set_ptr
    }
}

What are benefits of using solution 1, is the implied runtime borrow-checking provided by RefCell an hindrance in this case or would it actually prove useful? Would the use of unsafe be tolerable in this case? Are there benefits? (e.g. performance)

If you choose to use RefCell, then its as simple as making write_all also take only &self and then referencing multiple parts of data at once will be a non-issue as you can borrow mutably from inside the structure while public interface only requires shared references. In general case for borrowchecker problems though, I'd recommend looking into projects like indexlist and generational-arena to see how we solve problems with circular references. — Kaihaku
Your "Solution 2" is unsound. It is never OK to transmute &T to &mut T (or convert via pointer casts) regardless of whether it is aliased or not. You can use unsafe to accomplish something similar to RefCell with no runtime overhead; the way to do that is using an UnsafeCell, which disables the optimizations that make &T->&mut T problematic. — trentcl
(By the way, please don't edit answers into the question -- it is confusing for people reading. If you think of something the existing answers don't cover, put it in an answer instead -- you can answer your own question.) — trentcl

Kevin Reid Kevin Reid · Accepted Answer · 2021-05-20T14:19:35

it's totally fine to get references to different component sets mutably or immutably

This is true: we can safely have multiple mutable, or mutable and immutable references, as long as no mutable reference points to the same data as any other reference.

However, not every means of obtaining those references will be accepted by the compiler's borrow checker. This doesn't mean they're unsound; just that we haven't convinced the compiler that they're safe. In particular, the only way the compiler understands to have simultaneous references is a struct's fields, because the compiler can know those are disjoint using a purely local analysis (looking only at the code of a single function):

struct Ecs {
    pub pos: SparseSet<Pos>,
    pub vel: SparseSet<Vel>,
}

for (p, v) in ecs.pos.iter_mut().zip(ecs.vel.iter()) {
    p.x += v.x;
    p.y += v.y;
}

This would compile, because the compiler can see that the references refer to different subsets of memory. It will not compile if you replace ecs.pos with a method ecs.pos() — let alone a HashMap. As soon as you get a function involved, information about field borrowing is hidden. Your function

pub fn write_all<Component>(&mut self) -> &mut SparseSet<Component>

has the elided lifetimes (lifetimes the compiler picks for you because every & must have a lifetime)

pub fn write_all<'a, Component>(&'a mut self) -> &'a mut SparseSet<Component>

which are the only information the compiler will use about what is borrowed. Hence, the 'a mutable reference to the SparseSet is borrowing all of the Ecs (as &'a mut self) and you can't have any other access to it.

The ways to arrange to be able to have multiple mutable references in a mostly-statically-checked way are discussed in the documentation page on Borrow Splitting. However, all of those are based on having some statically known property, which you don't. There's no way to express “this is okay as long as the Component type is not equal to another call's”. Therefore, to do this you do need RefCell, our general-purpose helper for runtime borrow checking.

Given what you've got already, the simplest thing to do is to replace SparseSet<Component> with RefCell<SparseSet<Component>>:

//                         no mut;    changed return type
pub fn write_all<Component>(&self) -> RefMut<'_, SparseSet<Component>> {
    self.component_sets
        .get(&TypeId::of::<Component>())
        .unwrap()
        .downcast::<RefCell<SparseSet<Component>>>()      // changed type
        .unwrap()
        .borrow_mut()                                     // added this line
}

Note the changed return type, because borrowing a RefCell must return an explicit handle in order to track the duration of the borrow. However, a Ref or RefMut acts mostly like an & or &mut thanks to deref coercion. (Your code that inserts items in the map, which you didn't show in the question, will also need a RefCell::new.)

Another option is to put the interior mutability — likely via RefCell, but not necessarily — inside the SparseSet type, or create a wrapper type that does that. This might or might not help the code be cleaner.

Cannot borrow as immutable because it is also borrowed as mutable when implementing an ECS

1 Answers