Authors: [email protected], [email protected], [email protected]
Publication Date: 10th September 2021
A common question raised when comparing C++ and Rust is whether the Rust borrow checker is really unique to Rust, or if it can be implemented in C++ too. C++ is a very flexible language, so it seems like it should be possible. In this article we’ll explore if it is possible to do borrow checking at compile time in C++.
Many folks are working on improving C++, including improving its memory safety. Clang has experimental -Wlifetime warnings to help catch a class of use-after-free bugs. The cases it catches are typically dangling references to temporaries, which makes them a valuable set of warnings to enable when it is available. But the cases it would solve do not seem to intersect with the set of cases MiraclePtr is attempting to protect against, which is an effort to frustrate exploits we’ve observed in Chrome. MiraclePtr would be used to rewrite and verify pointer dereferences of fields in heap-allocated objects at runtime. This article asks if we could do the same sort of verification at compile time, similar to Rust.
One tool the Rust compiler uses to ensure the memory safety of a program is its borrow checker. The borrow checker ensures that an object is always in one of 3 states:
The type system and borrow checker also ensure that correct lifetimes are maintained.
The existence of references are known to the compiler, and they must be consumed to bring the original object back to its “Uniquely Owned” state. So we have a state machine that can be described as follows.
Define UNIQ<T> as an object of type T that is uniquely owned, no outstanding references.
Define HASMUT<T> as an object of type T that has a single exclusive (mutable) reference to the object.
Define MUT<T> as an exclusive (mutable) reference to T.
Define HASREF<T, N> as an object of type T that has N (for N >= 1) shared references to the object.
Define REF<T> as a shared reference to T.
Then the valid state transitions looks like:
UNIQ<T>
-> HASMUT<T> + MUT<T>
HASMUT<T> + MUT<T>
-> UNIQ<T>
UNIQ<T>
-> HASREF<T, 1> + REF<T>
HASREF<T, N>
-> HASREF<T, N+1> + REF<T>
HASREF<T, N> + REF<T>
-> HASREF<T, N-1>
HASREF<T, 1> + REF<T>
-> UNIQ<T>
Credit: [email protected]
The above states are all known to the Rust compiler in order for it to enforce the borrow checker’s rules. We would like to implement this safety feature in C++, which means we need to introduce these states to the compiler. In C++ the tool we have to control the compiler is types. In order to have the compiler enforce the above rules — short of changing the compiler and creating a new, derived and ABI-incompatible (with a changed representation of references) language — we must represent them in the C++ type system.
The above has some unfortunate implications for writing C++ against the borrow-checking type system, which we will explore.
In order to express the above in the C++ type system, we can simply define each state as a type:
class Uniq<T> {};
class HasMut<T> {};
class HasRef<T, unsigned> {};
As well, references require an explicit lifetime, so they also are defined as types.
class MutRef<T> {};
class Ref<T> {};
We can define the state transitions with some free functions that perform the necessary type conversions. These start from a uniquely owned state and bring a reference into existence.
std::pair<HasMut<T>, MutRef<T>> mut(Uniq<T>);
std::pair<HasRef<T, 1>, Ref<T>> ref(Uniq<T>);
We will ignore adding more than one shared reference for now, as just tracking a single reference becomes difficult enough at compile time. (More on that later.) Now we need to define the transitions back to unique ownership.
Uniq<T> consume(HasMut<T>, MutRef<T>);
Uniq<T> consume(HasRef<T, 1>, Ref<T>);
These functions consume the reference to ensure that it is returned to the object.
It would seem at first glance that we have successfully written C++ borrow checking, with the types defined above. Unfortunately, we have not.
Our goal is to have the compiler enforce the above state transitions, and prevent any other (invalid) state transition.
Since the Uniq<T> object is the only state where there are no outstanding references, we should expect that the object must always be returned to the Uniq<T> state/type before it is destroyed. To do otherwise violates the guarantees of the borrow checker. To do that, HasMut<T> and HasRef<T> can not be (publicly) destructible.
By ensuring the types HasMut<T> and HasRef<T> are not (publicly) destructible, we would ensure that they are converted back to Uniq<T> eventually, or their usage would fail to compile.
C++ passes ownership though moves, however C++ requires that the destructor of the moved-from object is still run when the object leaves scope. Commonly that destructor does nothing after a move, but the compiler will generate code to run it regardless, and then may optimize it out. There is no way to avoid this contract.
By comparison, Rust moves objects destructively. When ownership (always of a uniquely owned object) is transferred, the destructor on the moved-from object would not run, the contents of the object are mem-copied into the destination object and the moved-from object is considered to no longer exist to the compiler.
What this means for our borrow checker implementation is that each state transition leaves behind a moved-from object representing the old state, which must be destroyed. Because the moved-from object lives outside of the state transition functions, it requires a public destructor. This contradicts our borrow checker’s desired guarantees.
We must note that clang provides a [[clang:trivial_abi]] attribute which changes the C++ ABI contract above. It allows the compiler to move an object with a destructor as a function parameter in registers, effectively performing a memcpy. This can move the responsibility for calling the destructor into the callee, but does not remove the requirement for having a destructor that is visible and can run on a moved-from object.
Let us assume that we find a way to keep the destructors ~HasMut<T>() and ~HasRef<T>() private (we’re not concerned with the visibility of the ~T() destructor), with access limited to within our consume() state transition. This requires modifying the C++ language, but we can generously assume we have done so.
In order to obtain the guarantees of the borrow checker, we must ensure also that Uniq<T> only undergoes the correct transitions. It can transition to a HasMut<T> or a HasRef<T> but it can not transition to both, nor to either one more than once. Note that it’s possible to move back from HasRef<T> to Uniq<T>, however it creates a new/different Uniq<T> object owning the same original object. Using the original Uniq<T> instead would require runtime behaviour to validate and deal with the state inside the assigned-to Uniq<T>. This means that the transition from Uniq to HasMut or HasRef must destroy the Uniq type, in order to prevent it from later being used to perform another transition.
If we allow Uniq to be assignable after destruction, in order to reuse an lvalue variable, then we create another scenario to invalidate the borrow checker. Since the type Uniq<T> is tied to the type T but not to any particular object, and because the borrow-checker primitives need be exposed to the code author in this proposal, it would become possible to consume() a HasMut<T> and a MutRef<T> from different objects of type T, putting the borrow checker into an incorrect state in which its guarantees are not possible to enforce.
What this means is that moving from Uniq<T> to HasMut<T> and back to Uniq<T> requires a different instance of a Uniq<T> between the first and second state, meaning they require different variables.
Uniq<T> owner = …;
… mut(std::move(owner)) …
// Note this calls Uniq<T>(Uniq<T>&&) constructor, it’s
// not assignment.
Uniq<T> owner2 = consume(std::move(hasmut), std::move(mutref));
In order to ensure that the first owner does not get used after being moved, we require language changes to
We note that the first is possible to do in clang against the final AST, in a clang plugin or as changes to the compiler, since clang-tidy can warn on the same.
Given the above, we would then require an explicit destroy() state transition to destroy the object owned by a Uniq<T>.
Uniq<T> owner = make<T>();
// Generate a mutable ref, and use it. The usage is elided here.
… mut(std::move(owner)) …
// Consume the mutable ref.
Uniq<T> owner2 = consume(std::move(hasmut), std::move(mutref));
destroy(std::move(owner2));
Of course this no longer looks recognizable as C++.
The above glossed over the required code to hold and use a mutable reference. The actual code to do so is incredibly unwieldy.
Since the transition from uniquely-owned to having a mutable ref requires a new type, that type must be expressed and be given a lifetime.
Uniq<T> owner = make<T>();
// Generate a mutable ref.
std::pair<HasMut<T>, MutRef<T>> mutable = mut(std::move(owner));
// Use the mutable ref. Anything receiving the mutable ref must also
// return it.
MutRef<T> mutref = Borrows(std::move(mutable.second));
// Consume the mutable ref.
Uniq<T> owner2 = consume(std::move(mutable.first), std::move(mutref));
destroy(std::move(owner2));
There’s at least two very difficult-to-express-well problems here.
MutRef<T> Borrows(MutRef<T> t, int& outval);
int Borrows(MutRef<T> t, MutRef<T>& outref);
This explicit reference-returning is very verbose and makes the C++ difficult to write and, more importantly, to read.
MutRef<T> mutref = Borrows(mut(std::move(owner)).second);
Here the HasMut type is not stored, but is destroyed at the end of the statement’s execution, violating our borrow checker, and thus disallowed by the non-public destructor of HasMut<T>.
To avoid these problems would (handwavingly) require changing the C++ language such that the type of Uniq<T> owner is able to change dynamically, while being known to the compiler.
In the state description, we pointed out that in order for the compiler to verify all const references are returned/consumed, the reference count must be part of the type. We then made no mention of that again, because just working with a single (mutable or const) reference is hard enough.
A Ref<T> should be copyable so that it can be further shared. But in order to achieve that, the HasRef<T> would need to be present at each site that a Ref<T> is copied or destroyed, and the number of outstanding references would need to be baked into function signatures. That would make it impossible to call a method like
void ConsiderFoo(const Foo&);
which would need to be written as
Ref<Foo, 1> ConsiderFoo(Ref<Foo, 1>);
in different parts of the program, where one location has 1 reference and another has 2 where it exists. Every such function would require the refcount to be templated, forcing the code to be written in the header file. This is a pretty gross abuse of the C++ type system and would be an unreasonable compile-time burden for a large C++ codebase.
Instead, the only reasonable solution here is to fall back to runtime reference counting and to panic when a HasRef<T> is collapsed back to a Uniq<T> with an outstanding reference. This does provide some runtime safety but it does not satisfy the requirements of a compile-time C++ borrow checker. Note that if any Ref<T> is lost (destroyed) without collapsing it back into the HasRef type, the underlying object would end up being leaked. This is a worse situation than a ref-counted system that doesn’t require type-shifting back to a uniquely-owned state (e.g. std::shared_ptr).
If we accept that we can modify the language to make HasMut<T> and HasRef<T> non-destructible, and to enforce they are not used after a move, then we might consider to go a step further and do away with these troublesome types.
We might try to instead make the reference types MutRef<T> and Ref<T> not-publicly-destructible but also movable with a destructive move. Then we can eliminate the HasMut and HasRef types, and encode those states by the existence of the reference types.
However, that allows a method to steal ownership from a reference. By constructing a Uniq<T> from a MutRef<T>, ownership is taken without being passed a Uniq<T> explicitly. Thus we actually need the states representing HasMut and HasRef to remain in the original scope of the Uniq<T> they are transitioned from in order to return ownership back to the same scope (though not the same variable).
We attempted to represent ownership and borrowing through the C++ type system, however the language does not lend itself to this. Thus memory safety in C++ would need to be achieved through runtime checks.
#include <type_traits>
#include <utility>
#include <assert.h>
#include <stddef.h>
enum NoRefs {};
enum HasMutRef {};
enum HasRefs {};
template <class T, typename Mode>
class Own;
template <class T>
class MutRef;
template <class T>
class Ref;
template <class T, typename... Args>
inline Own<T, NoRefs> make(Args... args) {
return Own<T, NoRefs>(std::forward<Args>(args)...);
}
template <class T>
inline Own<T, NoRefs> consume(Own<T, HasMutRef> own, MutRef<T> ref) {
return Own<T, NoRefs>(std::move(own));
}
template <class T>
inline Own<T, NoRefs> consume(Own<T, HasRefs> own) {
return Own<T, NoRefs>(std::move(own));
}
template <class T>
std::pair<Own<T, HasMutRef>, MutRef<T>> mut(Own<T, NoRefs> own) {
T* t = own.t_;
own.t_ = nullptr;
return std::make_pair(Own<T, HasMutRef>(t), MutRef<T>(t));
}
template <class T>
std::pair<Own<T, HasRefs>, MutRef<T>> ref(Own<T, NoRefs> own) {
T* t = own.t_;
own.t_ = nullptr;
return std::make_pair(Own<T, HasRefs>(t), Ref<T>(t));
}
// No refs exist.
template <class T>
class [[clang::trivial_abi]] Own<T, NoRefs> {
public:
template <typename... Args>
Own(Args... args) : t_(new T(std::forward<Args>(args)...)) {}
~Own() { delete t_; }
Own(Own<T, NoRefs>&& other) : t_(other.t_) { other.t_ = nullptr; }
T& operator*() const noexcept { return *t_; }
T* operator->() const noexcept { return t_; }
private:
friend Own<T, NoRefs> consume<T>(Own<T, HasMutRef> own, MutRef<T> ref);
friend Own<T, NoRefs> consume<T>(Own<T, HasRefs> own);
friend std::pair<Own<T, HasMutRef>, MutRef<T>> mut(Own<T, NoRefs> own);
friend std::pair<Own<T, HasRefs>, Ref<T>> ref(Own<T, NoRefs> own);
Own(Own<T, HasMutRef>&& own) : t_(own.t_) {}
Own(Own<T, HasRefs>&& own) : t_(own.t_) {}
T* t_;
};
// A mut ref exists.
template <class T>
class [[clang::trivial_abi]] Own<T, HasMutRef> {
public:
T& operator*() const noexcept { return *t_; }
T* operator->() const noexcept { return t_; }
private:
friend class Own<T, NoRefs>;
Own(T* t) : t_(t) {}
~Own() {}
T* t_;
};
// Non-mut refs exist.
template <class T>
class [[clang::trivial_abi]] Own<T, HasRefs> {
public:
T& operator*() const noexcept { return *t_; }
T* operator->() const noexcept { return t_; }
Ref<T> ref() { return Ref<T>(t_, &count_); }
private:
friend std::pair<Own<T, HasRefs>, Ref<T>> ref(Own<T, NoRefs> own);
explicit Own(T* t) : t_(t) {}
~Own() { assert(count_ == 0u); }
T* t_;
uint32_t count_;
};
template <class T>
class MutRef {
public:
T& operator*() const noexcept { return *t_; }
T* operator->() const noexcept { return t_; }
~MutRef() = default;
MutRef(MutRef&& other) : t_(other.t_) {}
private:
friend std::pair<Own<T, HasMutRef>, MutRef<T>> mut(Own<T, NoRefs> own);
MutRef(T* t) : t_(t) {}
T* t_;
};
template <class T>
class Ref {
public:
T& operator*() const noexcept { return *t_; }
T* operator->() const noexcept { return t_; }
~Ref() { --(*count_); }
Ref(const Ref& other) : t_(other.t_), count_(other.count_) { ++(*count_); }
Ref(Ref&& other) : t_(other.t_), count_(other.count_) {}
private:
friend std::pair<Own<T, HasRefs>, Ref<T>> ref(Own<T, NoRefs> own);
Ref(T* t, uint32_t* count) : t_(t), count_(count) { ++(*count); }
T* t_;
uint32_t* count_;
};
MutRef<int> Borrows(MutRef<int> i) {
(*i)++;
return i;
}
TEST(Borrow, HelloWorld) {
// Can't do this. The HasMutRefs type is not destructible outside of
// consume()in order to have compiler check it is re-owned, but it won't
// compile. To pass the HasMutRefs to consume() it has to be destroyed both
// inside and outside of consume(). This is true even if trivial_abi is
// used and only one destructor would actually run.
Own<int, NoRefs> i = make<int>(5);
auto& hasmut = mut(std::move(i));
MutRef<int> ref = Borrows(std::move(hasmut.second));
Own<int, NoRefs> i2 = consume(std::move(hasmut.first), std::move(ref));
}
