Valen's Memory Safety: A New Kind of Borrow Checking

struct World { vector<Entity> entities; }; void step(const World& world, Entity& entity) { entity.advance(); auto collision = world.getCollisionForEntity(entity); entity.resolve(collision); }

Of course, the above requires care to uphold memory safety, since C++ doesn't check for memory safety at compile time.

Let's see an equivalent in Rust, where we do get automatic memory safety: 26

struct World { entities: Vec<Entity>, } fn step(world: &mut World, entity_id: usize) { let entity_mut = &mut world.entities[entity_id]; // bounds check, possible panic entity_mut.advance(); let entity_read = &world.entities[entity_id]; // bounds check, possible panic let collision = world.get_collision_for_entity(entity_read); let entity_mut = &mut world.entities[entity_id]; // bounds check, possible panic entity_mut.resolve(collision); }

Rust is generally nice to work with, but in some cases (like this one), it isn't quite as fast or simple as the C++ case, because we need to re-fetch the reference every time someone needed a &mut to something else in the same hierarchy.

Another option is to refactor our program to be "flatter" (so to speak) which has its own tradeoffs. 27

If you want to get really fancy, you can use GhostCells and add brands to your data and access them with a GhostToken:

struct World<'brand> { entities: Vec<GhostCell<'brand, Entity>>, } fn step<'brand>( world: &World<'brand>, entity: &GhostCell<'brand, Entity>, token: &mut GhostToken<'brand>, ) { entity.borrow_mut(token).advance(); let collision = world.get_collision_for_entity(entity, token); entity.borrow_mut(token).resolve(collision); }

You can see the conundrum.

With Valen's approach, we get something fast, safe, and simple:

struct World { entities Vec<Entity>; } func step(world &World, entity in world.entities[] mut) { entity.advance(); let collision = world.get_collision_for_entity(entity); entity.resolve(collision); }

A pretty nice simplification!

Now, let's finally get to the explanation of how it works.

This is not like Rust's unique references (&mut). There can be other references to that same entity.

This function cannot modify the whole world, just the entities inside it (this is actually a huge superpower, and means the optimizer can better optimize this function and its callers, but I'll explain that more later).

Or more specifically, it knows roughly where it's pointing to; entity in world.entities[] points at somewhere in the group of objects that live in the entities array.

In Rust, we need a &mut Entity for entity_mut.advance(), and then have to throw it away to get the containing &World back to give to the get_collision_for_entity call. Then later, we need to re-fetch the &mut Entity for the resolve call.

Specifically, it becomes easier to work with the borrow checker (and faster if your game happens to do ECS-style iteration), but you lose some of the RAII benefits of single ownership.

For example, if you flatten a heterogeneous tree into multiple arrays, nodes aren't automatically deleted when their parents are.

Also, if you split into parallel collections too much, you might risk "ID chasing" cache-miss slowdowns.

In the end, I'm wary of any memory safety approach that influences us into one architecture over another, because it might not be the best.

Even group borrowing does this to some extent, which is why I'm excited to blend in reference counting or generational references.

Yes, I know how ironic it is to use "C++" and "simple" in the same sentence!

There's some nuance here. You can generally rearrange your Rust code to match group borrowing's speed, even without GhostCell.

TL;DR: The approach is made of five mechanisms:

That was pretty abstract, so I'll explain all of these more.

TL;DR: Valen's borrow checker is based on single ownership, like C++ and Rust. Every value is "owned" by a containing object, array, stack frame, or global. 31

If you know how C++ or Rust works already, skip ahead!

If you don't know (or just like reading!), I'll explain what single ownership is.

In single ownership, every piece of data has one "owner". For example...