This post is about Valen's new flexible borrow checker. Welcome!

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

It's part of my eternal quest to find the memory safety holy grail: something as powerful as Rust's borrow checking, yet something as simple and flexible as reference counting or garbage collection. 0 1

I've long suspected that to find the holy grail, we'd have to solve three memory-safety challenges:

• Can we make a more relaxed borrow checker? 2
• Can we make a borrow checker read more complex data? 3 4
• Can we make those two systems work together at the same time?

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

This post mainly focuses on the first piece: Valen's more relaxed borrow checker.

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

And, along the way, I'll explain some of the weirder tidbits, like:

• How a compiler can remember where a reference is pointing.
• How Valen has one kind of borrow reference, as opposed to the two that other borrow checkers have.
• How Valen's borrow checker is shaped to help it call into Rust code.

Also, this article is gloriously long and has a lot of context, so I'll let you know when to skip ahead.

Let's dive in!

Group borrowing: a near miss, and huge potential

(This is just backstory that I love telling, feel free to skip this section!)

Valen's approach is built on the "Group Borrowing" proposal which was designed by my friend Nick Smith.

It's built around the core concept that the compiler remembers where a reference points to, (I'll explain this later) and it uses that information to check that programs are memory-safe.

The design's life had a rough start; it was almost buried in the flows of time. It was originally designed with Mojo in mind, but alas, despite my best efforts I couldn't convince the higher-ups that we should use it. 7 Group borrowing was dead before it had the chance to succeed.

But I knew it had massive potential, if it could just make it into the world somehow.

So we spent months sharpening the explanation and figuring out its benefits, and wrote a post 8 on it last year, hoping other languages would pick it up.

And they did! It spread far and wide. 9

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

Most of these languages are circling the same sort of challenge: how to make a more flexible borrow checker.

For example, Valen wants to make a borrow checker that's flexible enough to work with reference counting and generational references, and Carbon wants to make a borrow checker flexible enough to work with C++ code.

This is difficult, because there's been a fundamental conflict between borrow checking and other approaches. It can be summed up like this: 13

1. Borrow checking has the "shared-xor-mutable" restriction: if you hold a reference to an object, nobody else can change the object.
2. Other approaches want to allow holding a reference to an object while letting others change it. 14 15

You're probably thinking, "There's definitely no way to resolve this."

It does seem that way!

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

That was cryptic and won't make any sense, but it will later when I explain how group borrowing works.

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

What group borrowing can do

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

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

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

struct Entity {
  hp int;
}
struct World {
  entities Vec<Entity>;
}
func main() int {
  let world = World(Vec<Entity>.new());

  world.entities.push(Entity(42));
  let first_ref = &world.entities[0];

  world.entities = Vec<Entity>.new();

  // Compile error: Used a borrow after invalidated
  return first_ref.hp;
}

It's an unusually flexible approach. Usually, compilers have trouble with the below program, but this approach understands that it's safe: 17

func main() int {
  let list = Vec<int>.new();

  // Make two refs to the list
  let ref_a = &list;
  let ref_b = &list;

  // Mutate the list through both refs
  ref_a.push(42);
  ref_b.push(73);

  return 42;
}

Group borrowing accepts a lot of patterns that are normally hard for borrow checkers, such as:

• Having multiple local variables that point to the same object, and write through any of them (like above).
• Take a parameter pointing at an object, and another parameter pointing somewhere inside that object, and write through only the latter (we'll see this in the next section).
• Having multiple function parameters that point to the same object, and write through any of them. 18
• Make a "rollback" struct, that will change an object when it goes out of scope, like the ScopeGuard pattern. 19 20
• Having multiple structs that have mutable references to a common subsystem. 21
• Plus a lot more that I'll explain further below. 22

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