Technique: Recursive variants and boxes

31 May 2022 by Jonathan

There are many data structures that can be elegantly expressed using sum types. In C++ a (somewhat clunky) implementation of sum types is std::variant. However, it can’t handle recursive data structures, where one alternative contains the entire sum type again.

Let’s see how we can fix that.

The problem

We’ll consider a simple calculator that supports addition and multiplication. We want to store and evaluate expressions like 11, 40 + 2, or 3 * 13 + 3. That is, an expression is either a literal number, an addition containing two subexpressions, or a multiplication containing two subexpressions. Using std::variant, it can look like this:

struct LiteralExpr
{
    int value;
};

struct AddExpr
{
    Expr lhs, rhs;
};

struct MulExpr
{
    Expr lhs, rhs;
};

using Expr = std::variant<LiteralExpr, AddExpr, MulExpr>;

But of course, this doesn’t compile: C++ requires a declaration before Expr can be used in AddExpr, but the declaration of Expr requires a declaration of AddExpr. Such circular dependencies can be solved by forward declaring AddExpr and MulExpr and moving the Expr declaration before their definition.

struct LiteralExpr
{
    int value;
};

// We forward declare the types while naming them here.
using Expr = std::variant<LiteralExpr,
                          struct AddExpr, struct MulExpr>;

struct AddExpr
{
    Expr lhs, rhs;
};

struct MulExpr
{
    Expr lhs, rhs;
};

Instead of writing struct foo; void f(const foo&); you can combine the forward declaration and function declaration into one entity: void f(const struct foo&). This is used in the declaration of Expr above.

Now, an expression like 1 + 2 * 3 would be stored as:

auto expr = Expr(AddExpr{LiteralExpr{1}, MulExpr{LiteralExpr{2}, LiteralExpr{3}}});

However, it still doesn’t compile: std::variant does not work with forward declarations – it needs to know the size of the type, which requires a definition. And even if C++ were a language where declaration order does not matter, the circular dependency is still there.

Consider: what is the size of Expr?

Well, Expr is a variant, so its size is the size of the biggest member plus a tag. The biggest member is AddExpr, whose size is 2 * sizeof(Expr), which in turn may contain an AddExpr, whose size is 2 * sizeof(Expr), and so on. The only solution of sizeof(Expr) = sizeof(tag) + 2 * sizeof(Expr) is sizeof(Expr) = ∞ (or sizeof(tag) = -sizeof(Expr))!

This is impossible.

Heap allocating nested expressions

One way to solve the infinite nesting is to only store e.g. an AddExpr if we actually need to store one, and leave it empty otherwise. This can be done by allocating an AddExpr on the heap whenever necessary. That way, the variant itself only stores a pointer, which has a fixed size.

Since we’re using modern C++, this means wrapping AddExpr and MulExpr inside std::unique_ptr:

using Expr = std::variant<LiteralExpr, std::unique_ptr<struct AddExpr>, std::unique_ptr<struct MulExpr>>;

std::unique_ptr has no problems with forward declared types and is itself a complete type, so std::variant is happy. Instead of providing storage for infinite nesting, only as much memory is allocated as actually needed for a particular expression.

Instead of changing Expr to be a variant of std::unique_ptr, we could also change AddExpr and MulExpr to store std::unique_ptr<Expr> instead of Expr. However, this has two problems:

It requires a forward declaration of the typedef Expr, which is not possible. We have to turn Expr into a struct that contains/inherits the variant.

Instead of one allocation for each AddExpr, we now have two allocations, one for each operand of AddExpr.

This solution works.

It’s also really ugly.

For starters, creating an expression requires std::make_unique calls:

Expr(std::make_unique<AddExpr>(LiteralExpr{1}, std::make_unique<MulExpr>(LiteralExpr{2}, LiteralExpr{3})));

And even that only works in C++20, where aggregates can be initialized with T(args...). Otherwise, we need to add a constructor to AddExpr and MulExpr.

More importantly, Expr no longer has value semantics. Previously, we could freely copy Exprs which results in two independent objects (so no, std::shared_ptr isn’t the answer). Now, thanks to std::unique_ptr, it is no longer copyable:

Expr square(Expr operand)
{
    // error: can't copy Expr
    return std::make_unique<MulExpr>(operand, operand);
}

Similarly, constness no longer propagates: when we have a const Expr& we could still modify lhs or rhs of an AddExpr as a const std::unique_ptr<Expr> still gives you an Expr&:

int evaluate(const Expr& expr)
{
    struct visitor
    {
        int operator()(const LiteralExpr& expr) { return expr.value; }

        int operator()(const std::unique_ptr<AddExpr>& expr)
        {
            expr->lhs = LiteralExpr{42}; // ups

            auto lhs = std::visit(*this, expr->lhs);
            auto rhs = std::visit(*this, expr->rhs);
            return lhs + rhs;
        }

        int operator()(const std::unique_ptr<MulExpr>& expr)
        {
            auto lhs = std::visit(*this, expr->lhs);
            auto rhs = std::visit(*this, expr->rhs);
            return lhs * rhs;
        }
    };

    return std::visit(visitor{}, expr);
}

Let’s fix those problems.

Adding value semantics

In C++, we no longer use malloc‘ed const char* pointers for string, where copying the pointer does not copy the string, we use std::string: it is the same internally, but adds value semantics on top. For the same reason, we should not use std::unique_ptr: it is only marginally better than raw pointers in that it provides and communicates ownership, but is fundamentally still a type with reference semantics. The only acceptable use of std::unique_ptr is as an implementation detail; it shouldn’t appear in interfaces.

What we really want is a type that can store a heap allocated T but otherwise behaves like T. In particular, it should propagate const, and has a copy constructor that does a deep copy. Taking inspiration from Rust, let’s call it box<T>:

template <typename T>
class box
{
    // Wrapper over unique_ptr.
    std::unique_ptr<T> _impl;

public:
    // Automatic construction from a `T`, not a `T*`.
    box(T &&obj) : _impl(new T(std::move(obj))) {}
    box(const T &obj) : _impl(new T(obj)) {}

    // Copy constructor copies `T`.
    box(const box &other) : box(*other._impl) {}
    box &operator=(const box &other)
    {
        *_impl = *other._impl;
        return *this;
    }

    // unique_ptr destroys `T` for us.
    ~box() = default;

    // Access propagates constness.
    T &operator*() { return *_impl; }
    const T &operator*() const { return *_impl; }

    T *operator->() { return _impl.get(); }
    const T *operator->() const { return _impl.get(); }
};

A couple things of note:

It is a wrapper over std::unique_ptr. That way, we don’t need to worry about the destructor.
It can be implicitly constructed from T, which involves a heap allocation. This is similar to std::string, which can be implicitly constructed from const char*. For efficiency reason, the constructor can be made explicit, but this makes our intended usage with std::variant a bit more awkward.
The copy constructor goes ahead and copies the T object, which requires allocating a new one. This is required for value semantics.
Access to the underlying T object is possible using operator* and operator->. They propagate const: a const box<T> does only hand out const T&, unlike std::unique_ptr. In an ideal world, we had some sort of automatic dereferencing here to allow access with ., like Rust does.

Now we simply replace std::unique_ptr with box in the variant declaration. This makes construction nice again, we can freely copy expressions, and constness propagates.

using Expr = std::variant<LiteralExpr,
                          box<struct AddExpr>, box<struct MulExpr>>;

…

auto expr = Expr(AddExpr{LiteralExpr{1}, MulExpr{LiteralExpr{2}, LiteralExpr{3}}});

Expr square(Expr operand)
{
    return MulExpr{operand, operand}; // ok
}

int evaluate(const Expr& expr)
{
    struct visitor
    {
        int operator()(const LiteralExpr& expr) { return expr.value; }

        int operator()(const box<AddExpr>& expr)
        {
            // expr->lhs = LiteralExpr{42}; -- won't compile

            auto lhs = std::visit(*this, expr->lhs);
            auto rhs = std::visit(*this, expr->rhs);
            return lhs + rhs;
        }

        int operator()(const box<MulExpr>& expr)
        {
            auto lhs = std::visit(*this, expr->lhs);
            auto rhs = std::visit(*this, expr->rhs);
            return lhs * rhs;
        }
    };

    return std::visit(visitor{}, expr);
}

Aside: Moving boxes

Notice how I haven’t given box<T> a move constructor. This is intentional, as there are two options and thus warrants more discussion.

The first is to have a move constructor that behaves like the copy constructor and moves the underlying T object. This requires heap allocating a new object, and makes it not noexcept:

box(box &&other) : box(std::move(*other._impl)) {}
box &operator=(box &&other)
{
    *_impl = std::move(*other._impl);
    return *this;
}

The second option is to delegate to std::unique_ptr’s move constructor, which transfers ownership. This does not require heap allocation and makes it noexcept.

box(box&& other) noexcept = default;
box& operator(box&& other) noexcept = default;

However, going with the second option introduces the possibility for a box<T> to be empty – the moved-from state. There, it is no longer allowed to access the underlying T object, as there is none.

As I’ve repeatedly argued in the past, adding such a moved-from state is problematic, as the C++ compiler does not help you to catch it. If you go down that route, you should fully embrace the empty state – adding a default constructor, a query for it, etc. – turning the box into an optional_box<T>. Again, Rust doesn’t have that problem as the compiler prevents access to moved objects.

Conclusion

Recursive variants require heap allocation; there is no way around that.

The simple approach to heap allocation is std::unique_ptr. However, it is a type with reference semantics, which are vastly inferior to value types. A better alternative is to write a simple wrapper over it that adds correct value semantics, box<T>.

In general, I don’t really like std::unique_ptr for that reason. It has no place in interfaces and should only be an implementation detail. Unfortunately, the C++ standard library does not provide the nicer types, such as box<T> or the proposed std::polymorphic_value<T>, which is a replacement for polymorphic types. This lead to a proliferation of reference semantics in interfaces, which is a shame.