Breaking Circular Dependencies in Recursive Union Types With C++17
The Curious Case of std::variant‘s Missing Recursive Wrapper
One of the many great features in C++17 is std::variant – a class template implementing a type-safe union. Unexpected to some, it lacks a recursive wrapper that lets programmers easily define recursive union types, for example JSON-like structures that include other JSON-like sub structures. Building a recursive wrapper is easy. All it takes are literally five lines of code.
Recursive union types are used virtually everywhere. The most notable and very widely used example is JSON: a light-weight format to describe (and exchange) data. It‘s easy to read and write for humans and computers alike and it‘s defined by a small recursive grammar. For the sake of this post JSON will serve as guinea pig as every programmer should be familiar with it.
C++ has no builtin JSON data type in its standard library and some people have gone so far that building one yourself is awfully hard, or that it’s impossible without using inheritance, or that it required rather arcane features like void pointers, or that it requires third-party dependencies. We‘ll see that building a simple JSON type isn’t all that hard, doesn't require obscure language feature, no pointer structures and only a couple lines of code.
Simply put, JSON works like this: Data is stored either as a value, an ordered array of values or as an object which is an unordered set of name/value pairs. A value itself is either a string, a number, true, false, null, or again an array or an object. Note the recursive structure of arrays and objects which themselves can contain one (or more) further values. As some say, circular depencencies are meant to be broken.
It’s easy to see that first and foremost JSON as a generic structure reflects some kind of union type. An instance could be either of the above and still be valid JSON. But how can we implement it? The standards committee didn’t give us a recursive wrapper. Did they overlook it? Maybe even on purpose in their infinite wisdom? Did they know something we don’t?
As savvy C++ aficionados we are certain that it should be more than possible to build it using type-safe unions in standard C++17 by leveraging the languages sane type system in addition to using the standard template library (STL) where possible. But how? Implementing string, number, object, true, false, null types is straightforward. They are not recursive at all and require only a few lines of code. Just putting them as class template parameters into a std::variant instantiation gives us a decent but not yet awefully useful type-safe union:
We’d need arrays and objects to give any JSON-based data format a non-trivial structure. They are just a bit tricky to implement, though, because how would we declare a union type that holds another type depending again on itself? We’ll need a way to describe the recursive nature of JSON to the type system just to define the type in a complete. And by the time we have to do it the type will be incomplete. First, we’ll use simple forward declarations to tell the compiler about JSON object and array types.
Note the TODO marker in the middle of the code snipped. Because of the recursive nature of JSON, we use the forward declaration to make the compiler aware that a full type is coming later, but that it should note its name. Then we need to put the recursive definition of the JSON type between the forward declarations and the actual type declarations by using a light-weight wrapper type. Before implementing anything, though, let’s spend a minute thinking about the requirements of a recursive wrapper. The most important and somewhat obvious things are
- A wrapper needs to wrap a JSON object by storing, and
- it needs to return the wrapped object when asked for it, while
- contents of the wrapper shall be allocated dynamically.
Ok, that’s not too much to ask for and it should allow us to break the circular dependency. A simple vector to store the object and a cast operator to the wrapped object shall suffice:
It’s as simple as that. If you think about it, the above is essentially just a vector with two lines of boiler plate to construct and retrieve a wrapped object. Note std::vector serves as a poor mans optional type, here. You can experiment with other types from the STL, of course, if you care about the overhead.
Now, we can declare and define everything we need for a simple, yet functional JSON data structure in one header file using just a little more than 40 LOCs:
Sure, it’s a little clunky and could use some nip-tuck work to make it look more fashionable if used in any production system. Arguably, printing a JSON to standard output is important, so let’s give it a visitor implementation in another header file to just do that:
Again, not much magic happening here. An overload of the operator for every JSON type and structure suffices. We don’t even need to specify overloads for recursive_wrapper objects as the cast operator will automatically unwrap those which is a really nice feature of our 5LOCs implementation. And the following simple example that shows how everything works together:
Not too bad, eh? Now, it doesn’t matter too much if the committee forgot to include it on purpose or not. Next time someone says that standard C++ as a language sucks because it doesn’t have a recursive wrapper for its std::variant union type, you know it’s just two lines of boiler plate around a simple vector.
The above can be done in a simpler way? Let me know!
No void pointers were harmed during the making of this post.
