Adding memory safety to C++ is a very difficult problem, to say the least.

I’ve spent most of the last decade exploring this area (mainly to design Vale‘s memory safety) and I’ve discovered some surprising things.

The world largely believes that the only ways to make code memory safe are through reference counting, tracing garbage collection, or borrow checking.

It turns out, there’s at least eleven more methods 0 1 with more being discovered all the time if you know where to look. 2

Someone asked me recently, can we use these techniques to add memory safety to C++?

We can! It’s something I’ve been thinking about for a while, and it’s about time I write it all down.

The Challenges

Our ultimate goal is to find simple ways to make C++ memory-safe, simple enough that they can be checked via static analysis tooling or linters, without extending the language.

We’re going to do this without reference counting, or tracing garbage collection, or Rust-style borrow checking.

Not because they’re bad, of course. They have some great benefits:

• Tracing GC is the simplest model for the user, and helps with time management and development velocity, two very important aspects of software engineering.
• Reference counting is simple, allows for more predictable destruction of objects, and doesn’t require a VM like tracing GC does.
• Borrow checking is very fast, and helps avoid data races.

However, they each have their drawbacks too:

• Tracing GC can have some unpredictable pauses sometimes, while it stops the world to figure out which objects are still alive.
• Reference counting is often the slowest approach (though I think that will change in the next decade 3).
• Borrow checking is incompatible with some useful patterns and optimizations (described later on), and its infectious constraints can have trouble coexisting with non-borrow-checked code.

They also have their pragmatic limitations:

• Making tracing GC work well with C++ would be tricky, since the GC would need to find everywhere the normal C++ objects have references to garbage-collection-managed objects. 4
• Reference counting is pretty doable actually, as shown by shared_ptr.
• Borrow checking has a high complexity cost in the type system, such as its annotations. It would be difficult to add that to C++ which is a very complex language already.

I’m about to describe some different approaches, each with their own tradeoffs. None are silver bullets, and I wouldn’t claim that they’re the best way to do things. They’re merely interesting possibilities.

The techniques

We’re going to blend four main ingredients to achieve our memory safety:

• “Borrowless affine style”, via unique_ptr and owned values (from Vale, Val, and Austral)
• Constraint references (from Gel, Inko, and Vale)
• Generational references and random generational references (from Vale)
• Simplified borrowing (from Val)

These techniques are all possible, as far as I know. Between Vale, Val, Austral, Rust, Inko, and a few others, these techniques have all been implemented one place or another. There are a few other blends which use completely different techniques 5, but let’s start with this one. It starts off a bit rocky, but has that nice “zero-cost abstraction” feel to it, and generational references let us code with a familiar C++-like spirit.

These techniques provide the tools we need, and then a separate static analysis tool could ensure that we use them for the entire program, or in certain scopes, or for certain types. 6 7

Some caveats up-front:

• There is no such thing as zero-overhead memory safety for any language; some of these techniques could incur extra cloning, bounds checking, hashing, etc.
• Using these techniques will feel awkward or restrictive at first, almost Rust-esque at times. Further below, we blend in some other techniques to relax these restrictions and make it easier.
• These techniques will have varying levels of composability with existing unsafe C++ code.

With that, let’s dive in!

Borrowless Affine Style

This technique blew my mind pretty spectacularly, especially when I realized that it was already hidden beneath the surface in languages like Vale, Austral, Val, and Rust.

This technique shows that we don’t need tracing GC, reference counting, borrow checking, or anything for memory safety. We just need to change the way we move data around.

We’re going to start by identifying some memory-safe patterns that are already in C++, and then we’ll slowly expand it until we have a minimum viable memory-safe subset of C++. After that, we’ll add some mechanisms to make it more usable.

unique_ptr

C++11’s unique_ptr is a class that tracks who has sole responsibility for destroying an object.

This one little class singlehandedly brought the concepts of single ownership and move semantics into the mainstream, and it will serve as the starting point for our memory safety.

Our first principle is that dereferencing a unique_ptr is safe, as long as we follow these two rules:

Rule 1: Always initialize a unique_ptr to contain something. 8

Rule 2: Don’t use a unique_ptr local variable after moving from it. 9

It wouldn’t be hard to make some static analysis or a linter for these, plenty enforce that second one already.

So far, this is pretty obvious. A lot of us follow these rules already in our codebases.

The next part will be obvious too, and after that things get more interesting.

Stack objects are safe too

struct Ship { int fuel; };
int main() {
  Ship ship{ 42 };
  // Safe to access ship's fields.
  cout << ship.fuel << endl;
}

Now that the more obvious principles are out of the way, let's get to the interesting stuff!

Avoid raw pointers and references 11

I know, that sounds impossible and ridiculous.

"How in the world would we get anything done without raw pointers and references?" I can hear you say.

But I assure you, it is possible. And don't worry, we'll be adding pointers back in later.

But for now, here are some rules to understand how to make programs without aliasing.

Rule 3: When you want to take a pointer or a reference as a parameter, instead take (and return) a unique_ptr or a stack object.

Rule 4: When you want a raw pointer as a field, use an index or an ID instead.

Instead of a Ship having a Port* like this...

struct Port { string name; };
struct Ship { Port* port; };

Ship print(Ship ship) {
  cout << ship.port->name << endl;
  return ship;
}

...we would do something conceptually similar to this, where print uses the portId to read the Port from a map.

struct Port { string name; };
struct Ship { int portId; };

Ship print(unordered_map* ports, Ship ship) {
  cout << ports[ship.portId].name << endl;
  return ship;
}

Of course, we'll need to change that pointer parameter according to rule 3. We'll instead take and return the vector directly:

struct Port { string name; };
struct Ship { int portId; };

tuple, Ship> print(
    unordered_map ports,
    Ship ship) {
  cout << ports[ship.portId].name << endl;
  return make_tuple(ports, ship);
}

That's pretty verbose! We'll see some ways to make it less verbose further below.

These two rules may seem familiar to those who have used Rust; taking and returning a Ship is semantically equivalent to taking an &mut Ship, and the borrow checker often makes reference struct fields into indices/IDs as well.

However, we'll be deviating from Rust's direction pretty sharply.

Reading fields: swapping, move-destructuring

Later, we can access fields pretty easily using "simplified borrowing" like in Val. Until we get to those, I'll show how we can access fields using only this "borrowless affine style", for completeness.

Rule 5: We can only read a field by taking ownership of it, by either swapping something into its place or destroying the containing struct.

"Wait, can't we skip all this swapping and just read it, if we know nobody else accesses it?"

We can! But we'll get to that later on, when we talk about simplified borrowing and how we might use it for C++.

The rule mentioned that we can also destroy the containing struct to read its members, let's see an example of that.

The above example is fairly simple, but it could get a bit more difficult if we don't have ownership of the containing struct conveniently nearby.

We may need to refactor and pipe ownership of the containing struct all the way to here. Further below, we'll talk about this drawback and ways to address it.

Resizable Collections

Rule 6: Only use std::array and resizable collections, don't use raw arrays directly.

This is because raw arrays temporarily risk some unsafety when we first make them and when we're destroying them.

There are a lot of ways we can later relax these restrictions.

For example, we could have a runtime-sized array where we construct it with a size N and a closure, and the library (or language) will invoke that closure N times, filling the array's elements with the closure calls' results.

Or we can make something halfway between std::array and std::vector, which doesn't resize past its initial capacity, but still has size and capacity fields and methods like push, pop etc.

Vale's arrays are like that, and they're used to implement the standard library's array list, hash map, etc.

Bounds-checked array slices could also make life easier, so that functions could take in an arbitrary range of elements.

Reading from Collections

Rule 7: To access an element of an array, we need to take ownership of it by removing it.

This is pretty easy for a collection like a hash map. Simply remove the element, and put it back when we're done.

Nobody should access the hash map in the meantime. It wouldn't cause any unsafety, but could be a logic error.

Arrays are a bit trickier. When we temporarily remove an element, we have to either:

• Shift all the later elements down by one slot, and once we're done, unshift them all and put the element back in.
• Temporarily swap the last element into its place, and when we're done, do the reverse.

Another way to get an element out of the array is to destroy the entire thing, thus taking ownership of all its elements. Sometimes this can be pretty useful.

Branching

A few last rules to make this work:

• We must move (or destroy) the same variables from both branches of an if-statement.
• If we move (or destroy) something from inside a loop, we need to reinitialize it in that same iteration.

These might sound irksome, but we can always wrap a local in an optional to work around it.

The approach so far

So far, we've talked about:

• How unique_ptr and owned values are safe to access.
• How we can write a program using just those, without non-owning pointers/references.
• How we can use structs (including swapping and destructuring).
• How we can use collections.
• How we can safely use if-statements and loops.

The foundational rules above form "borrowless affine style", and they've achieved their goal: we now have a memory-safe subset of C++.

But let's take a step back and recognize its drawbacks, and see how we might address them by blending in some other techniques.

Besides being verbose, there are also some architectural consequences:

Drawback 1: Since Rule 3 requires us to change our function signature (by borrowing the vector), and all of our callers' callers' callers, this technique has become a viral leaky abstraction.

Drawback 2: Rule 4 puts a lot of our objects into collections, making our program almost similar to a relational database.

Drawback 3: Since we can't use raw pointers and references, we effectively cut ourselves off from mutable aliasing. This means we can't use fast approaches like intrusive data structures and graphs, and we can't use useful patterns like observers, back-references, dependency references, callbacks, delegates and many forms of RAII.

These are familiar to Rust users; &mut is semantically equ