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

This article is concerning Valen's new flexible get checker. Welcome!

You all cognize me, I love exploring new recollection safety approaches and blending them together in weird ways.

It's part of my eternal quest to discover the memory safety holy grail: item as mighty as Rust's get checking, yet item as uncomplicated and elastic as citation counting or refuse collection. 0 1

I've lengthy suspected that to discover the holy grail, we'd have to resolve three memory-safety challenges:

• Can we create a more relaxed get checker? 2
• Can we create a get checker peruse more complex data? 3 4
• Can we create those two systems activity together at the identical time?

Vague and arcane, I know! Further below I'll explain what that all means, and how Valen power have established a resolution for them. 5

This article chiefly focuses on the archetypal piece: Valen's more relaxed get checker.

So in this post, I'll conversation concerning what it is, what it can do, and how it works.

In this article, I obtain several liberties alongside syntactic sugar for clarity: auto-deref, immediately indexing a struct (my_vec[0]), and inferring types from groups (entity in world.entities[]) are coming in November. Aside from those syntactic adjustments, the get checker plant for everything we conversation about. 6

And, alongside the way, I'll explain several of the weirder tidbits, like:

• How a compiler can recall where a citation is pointing.
• How Valen has one benevolent of get reference, as opposed to the two that another get checkers have.
• How Valen's get checker is shaped to assistance it call into Rust code.

Also, this part is gloriously long and has a lot of context, so I'll let you cognize whenever to skip ahead.

Let's dive in!

Group borrowing: a near miss, and huge potential

(This is fair backstory that I affection telling, awareness liberated to skip this section!)

Valen's method is built on the "Group Borrowing" recommendation which was designed by my companion Nick Smith.

It's built about the center idea that the compiler remembers anywhere a citation points to, (I'll explain this later) and it uses that data to inspect that programs are memory-safe.

The design's existence had a coarse start; it was nearly buried in the flows of time. It was originally designed alongside Mojo in mind, but alas, notwithstanding my finest efforts I couldn't convince the higher-ups that we should use it. 7 Group borrowing was deceased before it had the chance to succeed.

But I knew it had massive potential, if it could fair make it into the earth somehow.

So we spent months sharpening the clarification and figuring out its benefits, and wrote a article 8 on it final year, expecting another languages would choice it up.

And they did! It dispersed far and wide. 9

• Google's Carbon tongue pivoted entirely to collection borrowing (and equal credited our article, which was nice of them!)
• Ante started operating it into their language, see Shared Mutability and Stability.
• Plecra's exclusion typing is redesigning the Rust get checker alongside concepts from collection borrowing and GhostCell. 10
• Zeta blended collection borrowing alongside disjointness 11 to aspect run-time facts into compile-time recollection safety.
• Fang is operating it into their designs, see Cyclic References in Fang.
• And now, my Valen combines collection borrowing alongside Vale's 12 approach, and makes it interop alongside Rust code too.

Most of these languages are circling the identical kind of challenge: how to create a additional elastic get checker.

For example, Valen wants to create a get checker that's elastic adequate to activity alongside citation counting and generational references, and Carbon wants to create a get checker elastic adequate to activity alongside C++ code.

This is difficult, since there's been a fundamental conflict between get checking and another approaches. It can be summed up akin this: 13

1. Borrow checking has the "shared-xor-mutable" restriction: if you clasp a citation to an object, nobody alternatively can alter the object.
2. Other approaches desire to authorize holding a citation to an entity during letting others alter it. 14 15

You're likely thinking, "There's certainly no way to determine this."

It does appear that way!

But collection borrowing really resolves the conflict, by relaxing "shared-xor-mutable" to "no use-after-free".

That was cryptic and won't create any sense, but it volition afterward whenever I explain how collection borrowing works.

So let's see what collection borrowing can do, and afterward I'll explain how it works.

What collection borrowing can do

Group borrowing gives a program recollection safety without run-time cost. 16

It catches use-after-free problems at compile time, and it does it in a way that has small restrictions than former approaches.

Here's an example anywhere a use-after-free error is caught at compile time:

struct Entity { hp int; } struct World { entities Vec<Entity>; } func main() int { let earth = World(Vec<Entity>.new()); world.entities.push(Entity(42)); let first_ref = &world.entities[0]; world.entities = Vec<Entity>.new(); return first_ref.hp; }

It's an unusually elastic approach. Usually, compilers have difficulty alongside the below program, but this method understands that it's safe: 17

func main() int { let catalog = Vec<int>.new(); let ref_a = &list; let ref_b = &list; ref_a.push(42); ref_b.push(73); return 42; }

Group borrowing accepts a lot of patterns that are normally difficult for get checkers, specified as:

• Having multiple local variables that item to the identical object, and compose through any of them (like above).
• Take a indicator pointing at an object, and another indicator pointing location inside that object, and compose through lone the second (we'll see this in the next section).
• Having multiple function parameters that item to the identical object, and compose through any of them. 18
• Make a "rollback" struct, that volition alter an entity whenever it goes out of scope, akin the ScopeGuard pattern. 19 20
• Having multiple structs that have mutable references to a average subsystem. 21
• Plus a lot additional that I'll explain additional below. 22

These are patterns we affection from C++, but no tongue has figured out how to do all of these in a memory-safe way at compile time.

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

A additional engaging example

(Or, jump to how it works)

For example, here's a step function that takes in a World reference, and a citation to among the entities inner it.

The crucial part is the entity in world.entities[] mut, which I'll explain below.

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); }

Note these parts:

• in method "a citation to one of".
• world.entities[] method "world's entities's elements"
• mut there method "we can modify it." 23 24

Put together: entity is a citation to one of world's entities's elements, and we can modify it.

This is the center idea of the approach: the compiler knows anywhere a citation points to, 25 since the person specifies (via in) anywhere it points to.

Now let's see how this looks in another languages, to see why this is so nice. (Or jump to how it works!)

First, the equal in C++:

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 complete requires attention to uphold recollection safety, since C++ doesn't inspect for recollection safety at compile time.

Let's see an equal in Rust, anywhere we do get automatic recollection safety: 26

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

Rust is mostly nice to activity with, but in several cases (like this one), it isn't fairly as accelerated or uncomplicated as the C++ case, since we need to re-fetch the citation all period person needed a &mut to item alternatively in the identical hierarchy.

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

If you desire to get really fancy, you can use GhostCells and add brands to your data and admission them alongside 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.

• The C++ example was simple, 28 but not memory-safe.
• Vanilla Rust was memory-safe, but a small slower, and a small additional complex. 29
• Adding GhostCell gave us the identical speed as C++, but it's motionless a bit complex.

With Valen's approach, we get item 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 beautiful nice simplification!

Now, let's eventually get to the clarification of how it works.

How Valen's get checker works

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

• Every entity is described by a path, according to single ownership.
• Every citation remembers the path of the entity it's pointing to. 30
• When we demolish an object, everything pointing at its way is no longer usable.
• A function signature describes the paths it modifies.
• When we call a function, everything pointing inner its modified paths are no longer usable.

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

Single Ownership

TL;DR: Valen's get checker is according to sole ownership, akin C++ and Rust. Every value is "owned" by a containing object, array, stack frame, or global. 31

If you cognize how C++ or Rust plant already, skip ahead!

If you don't cognize (or fair akin reading!), I'll explain what sole ownership is.

In sole ownership, all part of data has one "owner". For example...

#include <vector> struct Engine { int fuel; }; struct Ship { unique_ptr<Engine> engine; }; void foo(vector<Ship>* ships) { ... } void main() { vector<Ship> ships; ... foo(&ships); }

struct Engine { fuel int; }; struct Ship { engine Box<Engine>; } func foo(ships &Vec<Ship>) { } func main() { ships = Vec<Ship>.new(); foo(&ships); }

...we can say this: 32

• main's stack example "owns" vector<Ship> ships;
• The vector<Ship> ships; owns all Ship.
• Each Ship owns its Engine (via the unique_ptr).
• Each Engine owns its int fuel;
• foo does not own the vector, it fair has a raw pointer.
• main is the lone item without an owner.

If you've coded in C++ or Rust, you're likely acquainted alongside this mindset.

If you've coded in C, you power think akin this too, equal although C doesn't explicitly track sole ownership. If you trace an object's journey all the way from its malloc() call to its free() call, all of the variables/fields that the pointer passes through are dealing alongside the "owning pointer", so to speak. It's nearly akin how detectives track the "chain of custody" for evidence. In another words, who is "responsible" for it at any stated moment. 33

Heck, equal Java and C# programmers sometimes think in conditions of sole ownership. If you're expected to call an object's "dispose"/"cleanup"/"destroy"/"unregister"/etc. method at several point, you can trace that object's journey all the way from new to that (conceptually destructive) method call, and those are the variables/fields that are handling its "owning reference", so to speak.

Single ownership, as explained so far, is the basis for a lot of languages:

• If you add regular (unrestricted) pointers and references, you get C++.
• If you add generational references and area borrowing, you get Vale.
• If you add exclusivity-checked references, you get Rust.
• If you add collection borrowing and a few another mechanisms, you get Valen.

With sole ownership, all entity can be described by a "path", which I'll explain next.

Paths

Every entity can be described by a path.

For this example:

struct Entity { hp int; } struct World { diameter int; entities Vec<Entity>; } func main() int { let x = 42; let earth = World(73, Vec<Entity>.new()); }

Here are all the paths in this program:

• x
• world
• world.diameter
• world.entities
• world.entities[]
• world.entities[].hp

A way continually starts alongside one of these:

• Local changeable (like world).
• A function parameter.
• A function's "group parameter" (we'll see this later).

After that start, it volition have things like:

• .diameter to name a associate (like above).
• [] to name the elements of a gathering (like above).
• .SomeType to name a union's variant. 34
• plus a few another options that I'll enter later. 35

Every part of data has lone one owner (because sole ownership), so all entity has one path. 36

So what are paths used for?

References!

The compiler knows what way all citation points to, and that helps uphold recollection safety.

Every citation knows what way it points to

For example, in this program:

struct Entity { hp int; } struct World { entities Vec<Entity>; } func main() int { let earth = World(Vec<Entity>.new()); world.entities.push(Entity(42)); let entity_ref = &world.entities[0]; }

entity_ref's category is &Entity in world.entities[].

That method it's a citation to one of world's entities's elements.

And in the example we saw before:

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); }

You can see the entity in world.entities[], specifying an entity indicator that points at one of world's entities's elements.

If you cognize Rust: a way isn't really akin a lifetime. It's easier to grok whenever you think concerning them as distinct things. 37

Now let's discover out why we're doing all of this. Let's see how we use paths for recollection safety!

Using paths for recollection safety

The compiler uses paths to detect use-after-free; it detects whenever we're dereferencing a citation that is pointing at data that has already been destroyed.

It does this alongside these two rules:

• When we modify an object, we grade any citation pointing inside that entity as "invalidated".
• When we try to use an "invalidated" reference, the compiler shows an error.

struct Entity { hp int; } struct World { entities Vec<Entity>; } func main() int { let earth = World(Vec<Entity>.new()); world.entities.push(Entity(42)); let first_ref = &world.entities[0]; world.entities = Vec<Entity>.new(); return first_ref.hp; }

Note how I said:

When we modify an object, we grade any citation pointing inside that entity as "invalidated".

We don't invalidate references pointing to an object. We invalidate references pointing inside the object.

struct Ship { fuel int; } func main() int { let vec = Vec<Ship>.new(); vec.push(Ship(42)); let vec_ref = &vec; let elem_ref = &vec[0]; vec.push(Ship(73)); vec_ref.push(Ship(81)); return elem_ref.fuel; }

Notice how this is all happening without describing whether a citation is mutable or not.

Valen, however, has lone one benevolent of get reference.

This can be confusing if you're coming from C++ and Rust, which the two have multiple kinds of references (C++ has const and non-const, Rust has & and &mut).

In Valen, the mutability of item isn't part of its type, the surrounding function determines it.

Valen does put mut on function parameters, but that's syntactic sugar. mut is not part of the parameter's type. 38

Function signatures communicate invalidations

So how did the compiler cognize that push modified the vec?

push has to say so, in its signature, alongside the mut keyword.

Here's push's signature:

func push<T>(self &Vec<T> mut) { }

...which is syntactic sugar for this:

func push<T>(self &Vec<T>) mut(self) { }

Notice how mut(self) isn't part of self's type. It's additional part of the function.

So whenever main called vec.push(...), main was passing vec in for self.

The compiler afterward sees the mut(self), knows self is really vec, so knows vec was mutated.

That's how it knew to invalidate item pointing inside vec.

Here's another example:

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

We're not mutating the entire world; we're lone mutating item in world.entities[].

This is fine since this won't invalidate callers' references to entities.

For example, this step_and_read is calling the complete step function which doesn't invalidate the entity.

func step_and_read(world &World, entity in world.entities[] mut) { step(world, entity); entity.read_book(); }

And if we accomplishment the Valen compiler correct (and place LLVM), this might let us harness the optimizer in a way that no tongue always has before. 39

A twist on collection borrowing

The first collection borrowing designs included a lot of the complete (and more!). Here's the things that Valen volition be adding on top of it, to create it sing.

Mutable-in-Immutable

Recall this program, anywhere we took in a world that was immutable except for its entities elements:

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); }

We're receiving two indicator references, anywhere we can mutate through the additional particular one, and we can't mutate item exterior of it.

Valen adds this so that we don't have to do the traditional borrow-checking form of taking in the complete earth mutably.

This volition have a brace benefits.

First, it could assistance alongside a program's architecture, since it helps us create stronger APIs.

We can enforce that nothing in this complete function can alter any part of the world that we don't expect.

I ideate that volition be particularly helpful whenever operating in a squad alongside enterprising newhires (or alongside merchandise managers who affection to throw vibe code at you).

Second, I doubtful this characteristic could create Valen code optimize better.

I won't go too deeply into it here, 40 but basically, whenever you provision the optimizer additional fine-grained data concerning what power alter and what won't change, it can improved acknowledge places anywhere it can rearrange code to be faster. 41 42

Temporary Uniqueness

One of Valen's goals is to be capable to seamlessly call into Rust code, as effortlessly as Kotlin calls into Java, or C++ into C.

Of course, this volition be tricky, since collection borrowing and Rust have distinct kinds of references:

• Group borrowing allows others to alter the data that your citation is pointing at.
• In Rust, all citation is either shared (&) or distinctive (&mut). When you clasp a reference, nobody alternatively can alter what your citation is pointing at.

So the inquiry that arose was: Can we rotate a collection borrowing citation into a Rust reference, temporarily?

It turns out, yes!

The scheme is beautiful simple. When Valen is calling Rust:

• We can hand a Valen citation into a Rust &mut if it's the only citation that can attain that data during that call.
• If we have multiple Valen references that can item to the identical object, they can lone be handed into Rust & references.

I conversation a small bit concerning this in Memory Safety Across the Valen/Rust Boundary, inspect it out!

This impermanent conversion could develop into a broader characteristic one day. We desire Valen to assistance item akin Rust's Vec<&mut Ship>, anywhere all component is a distinctive reference, and collection borrowing doesn't have that.

I doubtful Valen can have item akin a "unique group", e.g. a unique(world.ships[]) note on a function, which would forestall making new references pointing at that part of the hierarchy.

This aspect needs additional idea though. One of Valen's top strengths is that it lone has one benevolent of get reference... so introducing a second "unique" citation requires several careful consideration.

Wildcard Descendant Paths

This is another characteristic that helps Valen call into Rust code.

While trying to get the Golden Spike to work, I ran into a conundrum.

When Valen calls a Rust function that returns a citation (like -> &Gem below), how does it cognize where that citation points?

For example:

impl Chest { pub fn gem(&self) -> &Gem { &self.gem } }

Valen was confused by this, since Valen likes to cognize the way for all reference.

In Valen's ideal world, it would see the complete akin this:

func gem(self &Chest) -> &Gem in self.gem { &self.gem }

But alas! Valen can't infer the in self.gem from the Rust code.

But if you zoom out a bit, the Rust code is trying to province that it's returning item to "somewhere inside" self.

So, let's add that idea to Valen!

Valen now interprets the complete Rust function as if it were this:

func gem(self &Chest) -> &Gem in self.gem... { &self.gem }

The in self.gem... method "points somewhere inside self.gem".

This is called a wildcard descendant path, and it certainly needs a improved name.

I depict this a small additional in Memory Safety Across the Valen/Rust Boundary.

I doubtful this volition be helpful for additional than fair Rust interop. It could erase inner particulars from signatures, and create archive APIs a small additional elastic and forward-compatible. However, we should observe out current too, since that identical intent can be served by another features in theory. 43

How this all fits in

Above, I mentioned the "memory safety holy grail", and the three challenges that we need to resolve to discover it:

• Can we create a more relaxed get checker?
• Can we create a get checker peruse more complex data?
• Can we create those two systems activity together at the identical time?

Valen's get checker is the key to #1: it lets us have multiple references to any object, and lets us peruse and compose through any of them.

#2 and #3 volition be in another article (since this article is getting massive!) but I can't oppose giving a quick preview of what it's all about.

These are my hasty scribbles to try and explain it in fractional a page. Nobody should try to comprehend it. Quick, jump ahead!

Recall this example from above:

struct World { entities Vec<Entity>; } func step(world &World, entity in world.entities[] mut) { }

I desire users to have the choice of using citation counted classes whenever they don't desire to define the paths. Like this:

class World { entities Vec<Entity>; } func step(world World, entity Entity) mut { }

It would be amazing to provision the users the liberty to simplify akin that. 44

Of course, blending citation counting and borrowing is infamously difficult. 45

The answer lies in a idea test from 2023 I called Arrrlang. Its name was a joke, but it had an engaging premise: portray the heap as N earth arrays, anywhere N is the figure of types in your program. 46

It occurred to me: collection borrowing understands arrays. And citation counting can be idea of as N arrays, all having references to all other.

If we put those two facts together, afterward the key understanding emerges: if we describe reference-counted classes to a get checker as if it's a bunch of arrays, afterward we power be capable to have get references into them in a memory-safe way.

A compiler doesn't need to actually compile citation counted objects to an array, of course. But it can depict it that way to the get checker, using group-borrowing terms.

If you do it that way, abruptly a lot of problems disappear, and it clarifies exactly what construction blocks we need to add to collection borrowing:

• A "multi-typed group", akin to a Vale region, as opposed to vanilla collection borrowing anywhere all collection needs a type. 47 48
• A "run-time" group. References into the run-time collection don't get invalidated.

Like I said, none of this volition create sense. Keep an eye out for the next article that talks concerning all this!

That's all for now

Thanks for reading!

In the next few articles, I'll explain additional concerning how we'll blend in citation counting and generational references, and how Valen's collection get checker is implemented.

This is fair the tip of the iceberg, so remain tuned by subscribing to my RSS feed, r/valen, or joining the Valen discord. And prosecute me on Bluesky and Mastodon!

Cheers,

- Evan Ovadia

Appendix: The type-stability exception

This part isn't implemented in Valen yet. Stay tuned!

Group borrowing can additionally be astute adequate to cognize that if you say my_vec.push(42), afterward equal although push says mut(self), it won't invalidate pointers to my_vec.size.

This makes awareness since no matter how anyone modifies a my_vec (which is a Vec), the item at my_vec.size volition motionless be there. Nobody can modify a Vec's size to be item another than an integer. In another words, it's "type-stable".

Generalizing a bit, collection borrowing volition never invalidate any type-stable data.

It won't invalidate pointers to any contained type-stable things (primitives, structs, or fixed-size arrays), or any type-stable things inner them. It lone invalidates pointers pointing inner any type-unstable things (enums' contents, pointer's pointee).

For example, in this program, nobody modifying the contents of Level can invalidate your citation to its Terrain.

struct Level { terrain Terrain; entities HashMap<EntityId, Entity>; location_to_entity HashMap<Location, EntityId>; } func add_entity(level &Level mut, entity Entity) { level.location_to_entity.insert(entity.loc, entity.id); level.entities.insert(entity.id, entity); } func main() { let flat = ; let terrain_ref = &level.terrain; level.add_entity(Entity(1, Loc(4, 5), 42)); print(terrain_ref.tiles.len()); }