optional<T> in a possible C++20 future
C++17 gave us std::optional which is, in the words of a friend of mine, one of those really simple, ultra complex types — in the sense that it’s very easy to understand and use properly, even for relatively inexperienced programmers… but extremely difficult to implement correctly, even for experts (another such is std::pair). Today, it’s well over a thousand lines of code, most of which is critical to support even its most basic functionality. optional<T> is the simplest sum type, and it appears in lots of different languages (and even has special syntax in Swift) under various related names — Maybe, Option, etc. — but in the languages I’m even nominally familiar with, it’s about as simple to implement as it is to use.
But that’s the state of affairs today. What does tomorrow bring?
C++20 is at least 30 months away from being published. In that time frame, some proposals that were accepted might get tweaked, heavily modified, or even removed. Some new language features might get added, or rejected for now or for ever. It’s way, way too early to say what this future might hold.
But since it’s fun to do, I’m going to do it anyway.
There are five language features that make optional easier and more concise to implement, without any change in functionality, two of which have already been added to the working draft and three that I am a coauthor of and hope to present at the next committee meeting in Jacksonville next month. I will go through each in turn and present the diffs of their impact on the implementation, using libstdc++’s as a starting point — though I’m not just taking <optional>, I’m also including an auxiliary header for reasons that will become clear shortly and I’m also snipping some of the declarations of auxiliary types. Altogether, implementing std::optional today using this hopefully-reasonable approach to counting takes 1137 sloc. Note that since many of these language features are too new to be implemented in compilers (or, again, may never be part of the language), the diffs I’m presenting here may very well be wrong or at least typo-ridden.
The first language feature I will talk about is the biggest, the most contentious, the one that has spent the longest time coming: Concepts. Concepts isn’t just a really nice, first class language feature solution to SFINAE, it’s not just a nicer enable_if. It also gives us the ability to constrain functions that we previously were not able to constrain at all. Most relevantly in this case, like the special member functions. We need optional<int> to be copyable, but optional<unique_ptr<int>> needs to be non-copyable, only movable, and optional<mutex> needs to be neither copyable nor movable. Today, the way to implement that kind of functionality is through indirection: we inherit from a type that has each special member defaulted or deleted based on the characteristics desired. Since there are four special member functions, that means we have sixteen specializations of a class template — even if not every combination is meaningful — and today we do:
template<typename _Tp>
class optional
: private _Optional_base<_Tp>,
private _Enable_copy_move<
// Copy constructor.
is_copy_constructible<_Tp>::value,
// Copy assignment.
__and_<is_copy_constructible<_Tp>, is_copy_assignable<_Tp>>::value,
// Move constructor.
is_move_constructible<_Tp>::value,
// Move assignment.
__and_<is_move_constructible<_Tp>, is_move_assignable<_Tp>>::value,
// Unique tag type.
optional<_Tp>>
{
/* ... */
};That’s… hardly expressing programmer intent. Enter, Concepts. Now, we can constrain special members! And it’s enough to simply declare a constrained special member as defaulted — that would inhibit the implicit generation of the member by the compiler. No base class necessary, and everything can be inline:
That brings us down to just 974 sloc, a drop of 163 lines. It’s likely that other parts of this implementation could benefit from Concepts as well, so this is certainly a lower bar estimate — but it’s a pretty large improvement already.
The next language feature already in the working draft is one that I’ve already written about, in this very context even: operator<=>. Outside of not being in a header named =, this language feature is amazing, providing the ability to write just one function instead of six. And in this case, it’s just three functions instead of thirty. Less code that’s only a little bit more complicated, but a whole lot easier to write:
After another 156 line deduction, we’re down to 818 sloc. And we’re just getting started.
One of the major sources of complexity, and line count, in the implementation of std::optional is the conditional triviality requirement. optional<int> needs to be trivially copyable and trivially destructible, optional<string> can’t be either. You can’t just if constexpr away a destructor body, and Concepts can’t quite solve this problem by itself. But it almost can, just with a little extra push. So Casey Carter and I co-wrote P0848 (in the post-ABQ mailing) to allow constrained special member functions to still be trivial if other special members are declared. In other words, given this code:
template <typename T>
class optional {
struct empty { };
union {
empty _;
T val_;
};
bool engaged_;public:
optional(optional const& ) requires is_trivially_copy_constructible_v<T> && is_copy_constructible_v<T> = default; optional(optional const& rhs) requires is_copy_constructible_v<T>
: engaged_(rhs.engaged_)
{
if (engaged_) {
new (val_) T(rhs.val_);
}
}
};
With Concepts, this compiles, and the expected copy constructor is invoked based on T's supported operations. But optional<int> still isn’t trivially copyable, simply because that second copy constructor exists. Our proposal seeks to fix that.
This fix seems fairly minor, but the implications can be large. Today, in order to achieve conditional triviality, we need to conditionally inherit from two different base classes — one trivial and one not — that are otherwise identical. That’s quite a bit of code duplication, and more importantly means that our logic must be split into multiple classes instead of being able to be in just the one.
With P0848, we just need the one type, which means all of the member functions can just directly access members instead of going through private bases. Suddenly, this implementation has become pretty comprehensible. So much delete:
We’re down another 347 lines, to just 471 sloc! Perhaps unsurprisingly, optional is the motivating example in that paper.
One of the still remaining sources of code duplication are the pairs of constructors that exist to meet the requirement of a conditionally explicit constructor. This conditionality is achieved today by making two constructors that are mutually disjoint with SFINAE. This gets a bit better with Concepts (though I did not make this change in the Concepts diff), but we still need two constructors. STL and I cowrote P0892 (in the pre-JAX mailing) to add the ability to make one single constructor conditionally explicit, using similar syntax to the way we make functions conditionally noexcept. This is a fairly small change, that has fairly small impact, but we think it’s definitely a positive change:
Instead of three pairs of otherwise duplicate constructors, now we just have three constructors. And we’re down 35 lines to 436 sloc.
The last remaining source of code duplication comes from the the necessity of manually writing all the overloads for member functions to handle const and non-const, lvalue and rvalue. optional has four of these member functions leading to fourteen overloads. Gašper Ažman, Simon Brand, Ben Deane, and I cowrote P0847 (in the pre-JAX mailing) to make it possible to deduce the qualifiers and value category of the object parameter instead of having to manually overload. It’s not the only problem that this proposal hopes to solve, but it is the first motivating example.
That dips us below 400 for the first time, now we need only 390 sloc!
All said and done, these language changes would give reduce the required implementation of optional from 1137 sloc all the way down to 390. We haven’t lost any functionality, but we have made the implementation much, much easier to understand, much closer to expressing programmer intent, and I would claim that we significantly widened the field of C++ developers would be able to implement std::optional.
I don’t know what C++20 will actually have in it, or whether any of the proposals I’ve worked on will make the cut. I don’t know what to expect in Jacksonville. But I’m excited to find out.
