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.
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:
However, they each have their drawbacks too:
They also have their pragmatic limitations:
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.
For a sneak peek, here they are: constraint references, generational references, random generational references, regions, arenas, mutable value semantics, interaction nets, basil memory stacks, CHERI capabilities, neverfree, MMM++, SPARK, and linear types. More than eleven really, but there is some overlap.
One day, I want to write about all these methods, and call the book the "Memory Safety Grimoire". That'd be pretty sweet!
Mostly r/programminglanguages.
I think a language will come along that blends reference counting with regions and linear or unique types. That would eliminate the vast majority of reference counting operations, which might make RC competitive again.
This is why Rust has Rc and RefCell, and also why we're about to introduce generational references and constraint references.
This has been done though, see the Boehm-Demers-Weiser garbage collector.
We're going to blend four main ingredients to achieve our memory safety:
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 6, 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. 7 8
Some caveats up-front:
With that, let's dive in!
Some other blends:
If you want to hear more about these, let me know!
Or maybe even just a well-crafted linter.
If anyone wants to actually attempt this, let me know!
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, so it's not so restrictive.
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. 9
Rule 2: Don't use a unique_ptr local variable after moving from it. 10
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.
If you want a nullable unique_ptr, consider wrapping it in an optional.
Linters enforce this for local variables, but not for fields. We'll have another rule to address that below.
Our next principle is that, of course, accessing the fields of an object on the stack is safe too.
That doesn't include making a pointer to a stack-allocated object and then dereferencing. 11 Only accessing a field directly is safe, at least so far.
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!
Technically, the compiler might produce a temporary reference when we say the name of a variable. That's fine, as long as we don't make references or pointers directly.
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.
Instead of taking a Ship pointer like this:
struct Ship { int fuel; };
void print(Ship* ship) {
cout << ship->fuel << endl;
}
...print would take (and return) it:
struct Ship { int fuel; };
Ship print(Ship ship) {
cout << ship.fuel << endl;
return ship;
}
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<int, Port>* 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<unordered_map<int, Port>, Ship> print(
unordered_map<int, Port> ports,
Ship ship) {
cout << ports[ship.portId].name << endl;
return make_tuple(move(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.
We'll still be using them indirectly of course; dereferencing a unique_ptr produces a temporary reference. But we won't be using raw pointers or references directly.
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.
In this example, a Ship contains a unique_ptr<Engine>.
We'll use std::exchange 13 to swap the unique_ptr<Engine> out to read it.
struct Engine {
int fuel;
Engine(int fuel_) : fuel(fuel_) {}
};
struct Ship {
unique_ptr<Engine> engine;
Ship(unique_ptr<Engine> engine_) :
engine(move(engine_)) {}
};
int main() {
auto ship =
make_unique<Ship>(
make_unique<Engine>(42));
// Swap it out
auto engine =
exchange(
ship->engine,
make_unique<Engine>(0);
// Read engine
cout << engine.fuel << endl;
// Move it back
ship->engine = move(engine);
...
}
Note how we're doing a make_unique<Engine>(0), making a temporary engine to swap into its place. This ensures that if someone else references the engine, they'll get something of the expected shape.
Alternatively, Ship could have a optional<unique_ptr<Engine>>, so we can just swap a nullopt into its place. 14
"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.
This example is similar, a Ship contains a unique_ptr<Engine>.
We remove the unique_ptr<Engine> from the containing Ship, and then destroy the Ship.
struct Engine {
int fuel;
Engine(int fuel_) : fuel(fuel_) {}
};
struct Ship {
unique_ptr<Engine> engine;
Ship(unique_ptr<Engine> engine_) :
engine(move(engine_)) {}
};
int main() {
auto ship =
make_unique<Ship>(
make_unique<Engine>(42));
auto engine = move(ship->engine);
ship = nullptr; // Deallocates ship
// Can't use ship again, per rule 2
cout << engine.fuel << endl;
}
This is such a common operation that other single-ownership based languages have syntax for destroying a struct and extracting its members.
Vale's move-destructuring does this, e.g. [engine] = ship; but the static analysis tool could enforce we do it manually for C++.
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.
Thanks to u/wearingdepends for the suggestion to use std::exchange here!
Or we can put nullptr into that unique_ptr instead of having an optional, though that would require some adjustments to our scheme elsewhere.
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.
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:
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.
A few last rules to make this work:
These might sound irksome, but we can always wrap a local in an optional to work around it.
So far, we've talked about:
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<Ship>), 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 equivalent to everything we're doing here and has the same drawbacks. This is the downside of eliminating mutable aliasing. Luckily, Rust partially resolves them with Rc and RefCell, for those willing to use them.
So should we do something like shared_ptr<optional<T>> then, or are there any other options?
There are indeed other options! Let's talk about generational references, random generational references, and constraint references.
A generational reference is where each object has a current "generation number".
It's equivalent to the generational indices method, but applied to an entire heap.
To learn more, check out this article which talks about how we added them to Vale (though, the next section talks about an improved version).
Vale has some additional mechanisms that help generational references, but we'll need to add something extra for C++.
Above, when I mentioned we can "get access to an object", I didn't actually mean dereferencing. We'll need an extra step of "checking out" the contents to take ownership of it from the original owner. Before the end of the scope, we're required to put something back into that spot. 15 16
Using a generational reference would look something like this snippet. 17
An object lives inside a gowned wrapper.
We use its ref() method to make a gref to it. 18
We can open a gref, which does a generation check and gives us something we can dereference.
// Makes an object
gowned<Ship> ship =
make_gowned<Ship>(42);
// Makes a generational reference to it
gref<Ship> shipRef = ship.ref();
// Does a generation check
auto shipHandle = shipRef.open();
// Prints 42
cout << shipHandle->fuel << endl;
There's a couple downsides so far:
We can address both by keeping the generations in a separate thread-local table. 19
There's also an alternative technique that's about 3x faster than that though: random generational references!
This is basically the same thing as Rust's RefCell.
We might also need enable_genref_from_this, for the same reasons enable_shared_from_this exists.
Let me know if you want some example code for this and I can dig it up from the Vale histories.
We can also just copy an existing gref.
Vale used to do this, but switched to random generational references which are about 3x faster. Someone also made a Rust crate for this table-based approach!
A random generational reference is a generational reference with one adjustment: it uses a pseudo-random generation number for every object, or even a thread-local ever-increasing integer. 20 21
Usage would be the same as the above generational references, and I include a sample implementation further below.
If you've ever heard of Arm's memory tagging, this is like that but with a wider tag.
While this approach is promising, it's still ultimately unknown. I'd recommend waiting until it's studied more before using it.
This approach has a lot of benefits:
This is a very strong stochastic approach, similar to how passwords work.
It does have a theoretical downside. For example, if we have an invalid access in our server code that's causing (worst case) six million loud errors a second and we decide to ignore it, then after 73,250 years 23 on average it could reuse the same generation as something that was there before, in which case the invalid access bug could cause some unsafety.
Those well-versed in statistics will recognize that this isn't really a problem, but let's explore it a little.
The odds of an invalid access happening undetected is always 1/2^64 for a 64-bit generation.
It also helps to keep in mind that these probabilities only apply to the error detection mechanism, not to the program itself.
One of my beta readers asked:
That would be true, except that most Rust programs use unsafe or have it in their dependencies, even when you don't count the standard library.
When someone uses unsafe to get around the borrow checker's restrictions, even if they think really hard about unsafe's more arcane interactions, bugs can remain hidden for a long time, stealthily causing undefined behavior in the unsafe block and in the safe code around it.
We'd similarly use random generational references to get around the restrictions of affine style, and fortunately, any invalid accesses are detected very loudly as a check failure brings down the entire program. Bugs are discovered very quickly, instead of causing mysterious behavior for years.
So it's better in some ways, worse in others. It's just a different approach.
Vale actually went one step further and replaced unsafe with a "skip-check dereference" operator to skip a generation check in release mode. The major benefit is that a compiler flag can ignore these in dependencies, so we no longer have to trust that our dependencies used unsafety well.
Even without that, when we're interoperating with a large amount of existing unsafe C++ code, this seems like an improvement over the pre-existing code.
There are a couple complications for adding this to C++:
Usage would be the same as the above normal generational references, and a simple C++ implementation would look roughly like the below code (also available here).
extern size_t vrefNextKey;
template<typename T>
class vref {
public:
vref(vowned<T>* own_) :
own(own_),
rememberedKey(own_->currentKey) {}
~vref() {}
vref_guard<T> open() {
return vref_guard<T>(own, rememberedKey);
}
private:
size_t rememberedKey;
vowned<T>* own;
};
template<typename T>
class vref_guard {
public:
vref_guard(vowned<T>* own_, size_t rememberedKey) :
own(own_) {
assert(rememberedKey == own->currentKey);
assert(own->present);
own->present = false;
}
~vref_guard() {
own->present = true;
}
T* operator->() { return &own->contents; }
const T* operator->() const { return &own->contents; }
private:
vowned<T>* own;
};
template<typename T>
class vowned {
public:
vowned(T contents_) :
present(true),
currentKey(vrefNextKey++),
contents(std::move(contents_)) {}
~vowned() {
assert(present);
}
vref<T> ref() {
return vref<T>(this);
}
private:
friend class vref<T>;
friend class vref_guard<T>;
bool present : 1;
size_t currentKey : 63;
T contents;
};
template<typename T, typename... P>
vowned<T> make_vowned(P&&... params) {
return vowned<T>(T(std::forward<P>(params)...));
}This simple implementation uses:
This approach has one additional benefit. For domains where its appropriate, it can be turned completely off for production code, and it would be as efficient as normal C++. This can be a pretty stellar tradeoff for single player games, compilers, or sandboxed situations like webassembly modules or apps.
Increasing it monotonically could have some security implications though, so perhaps use some randomness.
It could also be global. Vale does neither, and has an implicit restrict uint64_t* parameter to every function, which optimizes very nicely.
This relies on the OS detecting accesses to released memory and raising segmentation faults.
Given a 64 bit generation, it will take an average of 13 quintillion tries to trigger a false negative.
If there's only one failure per second, it's 439 billion years on average to cause unsafety.
If there's only one failure per week, it would take 266 quadrillion years on average to cause unsafety.
If there's six million check failures per second (the largest DDoS in history), it's 73,250 years on average to cause any unsafety.
Comfortable odds, I'd say!
Still, I'd recommend waiting on this approach until it's explored a bit more by the broader security community.
Normally the optimizer won't realize it's undefined behavior, but we can contrive some cases, such as if we return a reference to some stack-allocated memory.
Or, if we're willing to modify the language or compiler, then we could either:
Another option is to use something called a constraint reference, which allows for memory-safe mutable aliasing, while allowing objects to live on the stack or directly inside another object.
Basically, we:
A simplified implementation would look something like this (also available here):
template<typename T>
class cref {
public:
cref(cowned<T>* own_) : own(own_) { own->refCount++; }
~cref() { own->refCount--; }
cref_guard<T> open() { return cref_guard<T>(own); }
private:
cowned<T>* own;
};
template<typename T>
class cref_guard {
public:
cref_guard(cowned<T>* own_) :
own(own_) {
assert(own->present);
own->present = false;
}
~cref_guard() {
own->present = true;
}
T* operator->() { return &own->contents; }
const T* operator->() const { return &own->contents; }
private:
cowned<T>* own;
};
template<typename T>
class cowned {
public:
cowned(T contents_) :
present(true),
refCount(0),
contents(move(contents_)) {}
~cowned() {
assert(present);
assert(refCount == 0);
}
cref<T> ref() {
return cref<T>(this);
}
private:
friend class cref<T>;
friend class cref_guard<T>;
bool present : 1;
size_t refCount : 63;
T contents;
};It works similarly to a foreign key constraint in SQL, hence the name constraint reference. 26
This was also explored by Adam Dingle and David Bacon in their paper Ownership You Can Count On: A Hybrid Approach to Safe Explicit Memory Management, who made an entire C# variant using this, named Gel. This is also one of the mechanisms behind the language Inko, as described in the article Friendship ended with the garbage collector.
To get the object from the constraint_ref, we "check out" the contents and take ownership of it from the original owner. Before the end of the scope, we're required to put something back into that spot, via a constraint_guard object. 27 28
The obvious downside, of course, is that if you violate the constraint, your entire program halts. Still, this can be useful in development mode, and then we can compile these to raw pointers or generational references in release mode. 29
If you want to read more about constraint references, check out The Next Steps for Single Ownership and RAII. The ones described in there are slightly different in that they don't require "checking out" the object.
This is basically the same thing as Rust's RefCell.
We might also need enable_constraint_from_this, for the same reasons enable_shared_from_this exists.
Older versions of Vale used these for development mode, and would compile them into generational references for release mode. Later on, we managed to make generational references so efficient in Vale (by combining them with regions and something like the aforementioned affine style) that we defaulted everything to generational references in both modes.
So far, we've talked about this "borrowless affine style", where we only access things through unique_ptrs and owned values.
Then, we added some mutable aliasing goodness, via constraint references and generational references. Now it's a little more ergonomic.
But let's see what else we could do!
Let's talk about adding some limited aliasing via simplified borrowing. It doesn't require a full Rust-style borrow checker, lifetimes, or annotations, so it should be possible to implement it in a basic static analysis tool.
Above, when we were swapping out a Ships Engine so we could read it, we asked:
"Wait, can't we skip all this swapping and just read it, if we know nobody else accesses it?"
One might think that we would need a full borrow checker for this. But is there a simpler way?
There is! We can use a technique from Val, a sort of simplified borrowing. 30
Rust's Graydon Hoare talked about this kind of system in his article The Rust I Wanted Had No Future:
and then:
Austral's Fernando Boretti wrote a really good article on this. He mentions that it's even more restrictive than Rust's borrow checker, but that's why we're pairing it with mutable aliasing via generational references and constraint references. 31
Let's make it a little more concrete!
We'll add mutable non-owning pointers back in, with these rules:
With these rules, we don't need a full borrow checker 32 or any annotations.
We could call this a unique borrow.
This snippet is similar to the example from before, where a Ship contains an Engine.
Except now, we're just reading the engine directly with a unique borrow.
struct Engine {
int fuel;
Engine(int fuel_) : fuel(fuel_) {}
};
struct Ship {
unique_ptr<Engine> engine;
Ship(unique_ptr<Engine> engine_) :
engine(move(engine_)) {}
};
int main() {
auto ship =
make_unique<Ship>(
make_unique<Engine>(42));
Engine& engine_borrow = *ship.engine;
// Can't use ship while engine_borrow exists
cout << engine.fuel << endl;
}
Let's talk about that second rule, "don't return them". This seems like it would make getters complicated.
For example, this shipAt method wouldn't compile.
struct Ship {
int fuel;
};
struct Shipyard {
vector<Engine> ships;
};
Ship& shipAt(
Shipyard& shipyard,
int index) {
// Error, can't return this.
return shipyard.ships[index];
}
int main() {
Shipyard shipyard = ...;
shipAt(shipyard, 3).fuel = 42;
}
That's because shipAt returns a unique borrow, which isn't allowed in our rules.
There is a workaround, however. We can make shipAt take a function as an argument, like this.
struct Ship {
int fuel;
};
struct Shipyard {
vector<Engine> ships;
};
Ship& shipAt(
Shipyard& shipyard,
int index,
std::function<void(Ship&)> func) {
func(shipyard.ships[index]);
}
int main() {
Shipyard shipyard = ...;
shipAt(shipyard, 3, [](Ship& ship){
ship.fuel = 42;
});
}
Here, shipAt takes a function that it will then give a Ship&.
Now, we aren't violating the "don't return them" rule. Instead of returning it, shipAt is just passing it to another function which was supplied by the caller.
This function returns void but we can make one that returns a T that the function returns. We can also take an arbitrary callable, instead of the (sometimes slower) std::function.
Adding syntactic sugar is out of scope for our hypothetical static analysis tool, but I'm a language nerd, so I'll mention Swift's trailing closure syntax, or Kotlin's inline function syntax.
The previous callsite:
shipAt(shipyard, 3, [](Ship& ship){
ship.fuel = 42;
});
...could look like this instead:
shipAt(shipyard, 3) [](Ship& ship){
ship.fuel = 42;
};
Or, if we want to go overboard and use generic lambdas under the hood, we could even make it look like this. 33
shipAt(shipyard, 3) (ship){
ship.fuel = 42;
}
But alas, we're explicitly not modifying the C++ language or compiler in this article; this syntactic sugar is just an interesting thought experiment.
We're blending Val and Vale! If only we had something from Vala too, we'd have the whole set!
By the way, if you haven't checked out Austral, give it a look! It uses one of my favorite features, linear types.
It could be said that this is a borrow checker, which would make the title of this article a bit awkward. However, most people are coming into this article thinking that "borrow checker" means something like Rust's borrow checker, so the title is trying to work within that pre-existing connotation.
In other words, it would expand that (ship){ to something like [](auto& ship){ under the hood. I also removed a semicolon here, because this is all theoretical and nobody can stop me in my madness.
We could get away with just having this "affine style" and the unique borrows described above, but we can also add a simplified immutable borrowing as well.
We can add it to our little theoretical C++ static analysis tool, since it still doesn't require a full borrow checker with annotations.
We would add immutable non-owning pointers back in, and we'd follow these rules:
It's pretty similar to the previous simplified unique borrowing, except we can alias them, and can't modify things through them.
Fun fact: This enables seamless fearless structured concurrency, as long as we don't choose to introduce data coloring (such as Rust's Sync/Send). 34 We'll talk more about concurrency further below.
So far, we've talked about this "borrowless affine style", where we only access things through unique_ptrs and owned values.
We also just added simplified borrowing, which is a little restrictive but resolves some of the awkwardness of borrowless affine style.
That combination alone is still quite difficult. Just like with Rust, we'll find ourselves doing a lot of cloning, bounds checking, and hashing to work around its restrictions, and we can't do patterns like observers, back-references, dependency references, callbacks, delegates and many forms of RAII.
Luckily, we also have mutable aliasing via constraint references and generational references, to handle all those and make things feel a little more like the C++ spirit we're used to.
A pretty good combination so far!
More specifically, as long as we don't choose to add escape hatches for immutable references, such as how Rust's RefCell acts as an escape hatch for their shared references.
We'll of course be adding something like shared_ptr.
The reason we haven't yet is because I wanted to show you that we don't need reference counting to add memory safety to C++. 35
So just for fun, let's ask the question: how much do we really need reference counting?
This is a familiar question to anyone who has used Rust. One of my favorite things to do in Rust is to see how far we can get by just using the borrow checker, and not using Rc<RefCell<T>>. However, that Rust usage had the same three drawbacks we mentioned above for affine style:
In my opinion, this shows the wisdom of the Rust language designers in adding Rc and RefCell to their standard library.
So does all this mean we should add something like Rc<RefCell<T>>?
Perhaps.
We already have gref, vref, and cref above, which all add mutable aliasing, so it's unclear if we need reference counting.
We also have some techniques available to us that Rust doesn't. For example, in cases where there would only be two people with references to an object, we could make a bidirectional optional reference, where if we destroy one side we null out the other. 37
In fact, Vale doesn't have any sort of shared ownership quite yet, so that we can explore these techniques for a while longer. However, we'll likely add it before 1.0, because we can contrive a few situations where it's unavoidable. For example, we might want a FileCache object that counted how many classes had a file open for reading. If anyone knows of an alternative to that, let me know!
So, all that said, let's talk about how we might add shared ownership in!
Besides, the title kind of promises no reference counting, and I stretched the title's veracity enough by adding simplified borrowing!
RAII is about automatically affecting the world outside our object. To affect the outside world, the borrow checker often requires us to take a &mut parameter or return a value, but we can't change drop's signature. To see this in action, try to make a handle that automatically removes something from a central collection. Under the hood we usually use unsafe mechanisms, including FFI.
I even made a thread-safe version of these with two mutexes, when I was working on Earth.
It would likely take the form of a shared_ptr<optional<T>>.
We would "check out" the value by using the .value() method and then swapping something into its place.
After we're done using it, we would put the object back into the shared_ptr's optional.
// Makes an object
auto original_ship =
make_shared<optional<Ship>>(
make_optional<Ship>(42));
// Makes another reference to it
auto shipRef = original_ship;
// Check it out.
// This value() asserts it's present
auto ship = shipRef->value()
// Prints 42
cout << ship.fuel << endl;
// Put it back
*shipRef = make_optional<Ship>(ship);
We could also make a "handle" object that uses RAII to ensure we put that ship back into the shared_ptr, similar to what we did with vref/cref.
So far we have:
Between all these, we might be able to add some memory safety to C++!
This isn't the only blend, of course. There are more!
...but this article is already 20+ pages! So let's stay with this blend for now.
Let me know if you want to hear about those, and I'll be happy to make this into a series.
I like this general approach of finding a memory-safe subset of C++, because we can gradually migrate existing C++ to it.
For this particular blend, we would migrate on a type-by-type basis. We'd have a whitelist file where we list all the classes that should follow these rules. Alternately, we can have a tooling-recognizable comment above any classes that follow these rules, or have them inherit a certain marker class.
I think this is a better starting point than the usual approach of having "safe functions", because for a function to be safe, all arguments handed in have to be safe, which quickly becomes a viral leaky abstraction. Same thing goes for scopes and files.
We should have both. Safe functions/scopes/files will be useful in the late stages of migrations after we've migrated over most types.
As an extra benefit, generational references and constraint references can be turned off with #defines, making them exactly equivalent to bare C++. This means we can gradually migrate our programs to use them turned off, and then try flipping them on all at once.
All these techniques are either concurrency-safe already or can be made concurrency-safe fairly easily. By "concurrency-safe", I mean safe from risk of data races.
Borrowless affine style is already safe, since only one thread has access to an object at any given time. Though, it could be awkward to use in practice, because other threads with IDs can't actually read the object they're referring to. Luckily, we're blending other mechanisms in.
Simplified unique/immutable borrowing is already thread safe.
One might think that shared_ptr<optional<T>> can't be made thread-safe, because Rust's Rc<RefCell<T>> isn't thread-safe. However, that's because of a (mis)feature in RefCell's design. Instead, let's make it so that accessing a shared_ptr via an immutable borrow will always produce another immutable borrow. With that, it's safe to concurrently read a shared_ptr from multiple threads. We wouldn't even need any data coloring like Sync/Send, which is nice.
Alternately, we can add something like Rust's Mutex<T>, perhaps called std::mutexed. We would then be able to use it like shared_ptr<mutexed<T>>, and it would be thread-safe.
Random generational references can be made safe if we "scramble" the generations that cross thread boundaries. Like in Vale's design, we could add the same random number to the object's generation, all indirectly owned objects' generations, and any generational references inside them 38, recursively.
Regular generational references can also be made safe, though the thread-crossing "scramble" would require a two-pass recursion: the first pass would gather a hash map of all objects in the hierarchy and their new generations, and the second pass would update any contained references to each other.
Constraint references would do something similar, with some recursions and a hash map. It would note all the objects in the hierarchy, and then assert that there are no references outside to anything inside the hierarchy.
Alternately, something like Vale's region borrowing could avoid any of the scrambling or assertions for generational references or constraint references. Basically, we'd make it so pure functions or "pure blocks" could immutably access everything outside their scope. I talk about this more in Seamless, Fearless, and Structured Concurrency.
This is so that references to another object inside the same hierarchy are also updated.
The nice thing about all of this is that it wouldn't require any big language changes or committees or standards. It could be implemented with some static analysis, since these are all pretty simple locally-verifiable rules. Perhaps it would only be enabled for certain types, or any types with a certain suffix.
If someone wants to investigate this, let me know and I'd be happy to pool knowledge!
I can even imagine a future where there's some sort of "C++ safe mode" where this static analysis is enabled by default, and then we break out of it with unsafe blocks.
Or perhaps a project like Carbon or CppFront could support something like these approaches. 39
A lot of people are working on adding memory safety to C++, from a lot of really promising angles! Here are just a few:
Herb/Chandler, let me know you ever want to talk memory safety over some cider!
Thats it! I hope you enjoyed this whirlwind tour of the various ways we can add memory safety to C++.
If you have any questions, feel free to message me on twitter, the discord server, or subreddit.
Until next time!
- Evan Ovadia