C++ Mutually Recursive Variant Type (Again)

Question

I have a problem similar to that described here: C++ Mutually Recursive Variant Type

I am trying to create a JSON representation in C++. Many libraries already offer excellent JSON representations and parsers that are very fast, but I am not reinventing this wheel. I need to create a C++ JSON representation that supports certain space optimizations under specific conditions. In short, if and only if a JSON array contains homogenous data, rather than storing every element as bloated variant types, I need compact storage of native types. I also need to support heterogeneous arrays and standard nested JSON objects.

The following is the "if wishes were horses, beggars would ride" version of the code, which is meant to clearly illustrate intent, but is obviously broken because types are used before any declaration exists. I want to avoid specifying the same information multiple times in types (i.e. Array, Object, and Value should not require duplicated type specifications). I also want to avoid any unnecessarily high run-time costs.

#include <string>
#include <unordered_map>
#include <vector>
#include <boost/variant.hpp>
#include <boost/variant/variant.hpp>
#include <boost/variant/recursive_wrapper.hpp>

class JSONDocument {
    public:
        using String = std::string;
        using Integer = long;
        using Float = double;
        using Boolean = bool;
        using Null = void *;
        using Key = std::string;
        using Path = std::string;
        using Value = boost::variant<
                Null,
                String,
                Integer,
                Float,
                Boolean,
                Object,
                Array
                >;
        using Object = std::unordered_map<Key,Value>;
        using Array = boost::variant<
                std::vector<Null>,
                std::vector<String>,
                std::vector<Integer>,
                std::vector<Float>,
                std::vector<Boolean>,
                std::vector<Value> >;
    private:
        Value root;
        class value_traversal_visitor : public boost::static_visitor<Value> {
            public:
                value_traversal_visitor( Path path ) : path(path) {}
                Value operator()( Null x ) const {
                    if( path.empty() ) {
                        return x;
                    }
                    // otherwise throw ...
                }
                Value operator()( String x ) const {
                    if( path.empty() ) {
                        return x;
                    }
                }
                ...
                // special handling for Array and Object types
            private:
                Path path;
        };
    public:
        Value get( Path path ) {
            return boost::apply_visitor( value_traversal_visitor( path ), root );
        }
        ...
};

As you can see, I am including the recursive_wrapper header. I have tried various invocations of boost::make_recursive_variant and boost::recursive_wrapper, but I always get compiler errors. I do not see how the answer from C++ Mutually Recursive Variant Type solves this, because in every attempt, I get compiler errors (from both gcc++ 5.3 and LLVM/clang++ 3.8) that almost exclusively reference Boost that essentially boil down to types not being convertible or declarations either conflicting or not existing. I would put one of my attempts along with specific compiler error messages here, but I wouldn't know which of the many attempts to use.

I'm hoping somebody can set me on the right path...

Thanks in advance!

Edit

Just to build on the accepted answer below, here is an example of a working skeleton for the types and their usages.

#include <string>
#include <unordered_map>
#include <vector>
#include <boost/variant.hpp>
#include <boost/variant/variant.hpp>
#include <boost/variant/recursive_wrapper.hpp>

using String = std::string;
using Integer = long;
using Float = double;
using Boolean = bool;
using Key = std::string;

using Value = boost::make_recursive_variant<
        String,
        Integer,
        Float,
        Boolean,
        std::unordered_map<Key, boost::recursive_variant_>,
        boost::variant<std::vector<String>,std::vector<Integer>,std::vector<Float>,std::vector<Boolean>,std::vector<boost::recursive_variant_> >
        >::type;

using Object = std::unordered_map<Key, Value>;

using Array = boost::variant<std::vector<String>,std::vector<Integer>,std::vector<Float>,std::vector<Boolean>,std::vector<Value> >;

int main( int argc, char* argv[] ) {
    Value v;
    v = static_cast<Integer>( 7 );
    Object o;
    v = o;
    Array a = std::vector<Integer>( 3 );
    v = a;
    return 0;
}

Why not use unique_ptr for the recursive types? That's essentially what the wrappers do. — Michaël Roy, Aug 21 '17 at 20:14
@MichaëlRoy One of my big issues with the whole project is even getting the declarations right. If I define Value in terms of unique_ptr — rg6, Aug 21 '17 at 20:39
If all fails, you can wrap the problematic types inside a struct. This you can forward-declare. I wrote an AST no long ago, and had to do that for some of my vectors, specifically. You end up with a unique_ptr. I know it's ugly, but it works. — Michaël Roy, Aug 21 '17 at 20:46
@MichaëlRoy That's ultimately the approach that they take in the link sehe provides below. I suppose that it's a fully flexible method and doesn't necessarily involve any extra run-time cost if done right, but I can't shake the feeling that there should be a way to do this just with variant facilities. For the sake of other people with a similar question, I'll look for an answer in that spirit. Maybe sehe can yet provide one. — rg6, Aug 22 '17 at 12:58

score 6 · Accepted Answer · answered Aug 21 '17 at 21:20

You could just use recursive_variant_ placeholder with make_recursive_variant.

Here's the gist:

using Value   = boost::make_recursive_variant<
    Null, 
    String, 
    Integer, 
    Float, 
    Boolean,
    std::unordered_map<Key, boost::recursive_variant_>, // Object
    std::vector<boost::recursive_variant_>              // Array
>::type;
using Object = std::unordered_map<Key, Value>;
using Array = boost::variant<Value>;

Live Demo

Live On Coliru

As you can see there's unimplemented bits in the code (never write functions missing return statements!). Also note the simplifications in control flow for get and the private visitor implementation.

#include <boost/variant.hpp>
#include <boost/variant/recursive_wrapper.hpp>
#include <boost/variant/variant.hpp>
#include <string>
#include <unordered_map>
#include <vector>

class JSONDocument {
  public:
    struct Null { constexpr bool operator==(Null) const { return true; } };
    using String  = std::string;
    using Integer = long;
    using Float   = double;
    using Boolean = bool;
    using Key     = std::string;
    using Path    = std::string;
    using Value   = boost::make_recursive_variant<
        Null, 
        String, 
        Integer, 
        Float, 
        Boolean,
        std::unordered_map<Key, boost::recursive_variant_>, // Object
        std::vector<boost::recursive_variant_>              // Array
    >::type;
    using Object = std::unordered_map<Key, Value>;
    using Array = boost::variant<Value>;

  private:
    Value root;

    struct value_traversal_visitor {
        Path path;
        using result_type = Value;

        result_type operator()(Value const &x) const {
            if (path.empty()) {
                return x;
            }
            return boost::apply_visitor(*this, x);
        }

        result_type operator()(Null)           const { throw std::invalid_argument("null not addressable"); }
        result_type operator()(String const &) const { throw std::invalid_argument("string not addressable"); }

        // special handling for Array and Object types TODO
        template <typename T> result_type operator()(T &&) const { return Null{}; }
    };

  public:
    Value get(Path path) { return value_traversal_visitor{path}(root); }
};

int main() {}

CAVEATS

Note that you should NOT use void* for Null because all manner of unwanted implicit conversions
Note that you should probably not use unordered_map because
- some JSON implementations allow duplicate property names
- some JSON applications depend on the ordering of the properties

See also https://github.com/sehe/spirit-v2-json/blob/master/json.hpp#L37

This is helpful indeed. I changed the Null representation from void*, and the extent to which the linked code is similar to what I'm aiming for in intent and detail is useful. The answer all sidesteps one core bit of complexity, however, which is the particular optimization that I *must* achieve. My Array type is not merely an encapsulation of the Value typedef, because that causes each element to be a variant, which I cannot afford. The Array must itself be a variant type of vectors among which the Value is only one while the Value type references this variant-typed array. — rg6, Aug 22 '17 at 04:33
Regarding my previous comment, it seems that this fundamentally makes my requirement different from the typical uses of the Boost recursive_variant facilities. The Value variant must have as a type member yet another variant type, the Array variant, which then must have as a type member the containing Value variant. Meanwhile, neither the Array variant nor the Value variant are yet defined, and both require the other. This is the element of complexity that causes my every attempt to fail with compiler spew. It doesn't seem to be a simple case of a variant recursively referencing itself. — rg6, Aug 23 '17 at 00:45
All right, this *does* generalize to what I needed. For all those who are interested in exactly how, check the edit above. It's naturally important that Array is defined *exactly* the same in both places, which is a fragility that I don't like, but it seems there is no way around it. — rg6, Aug 23 '17 at 20:12

Michaël Roy · Answer 2 · 2017-08-22T22:46:55.767

1

Not a solution per se, but Here's a way to achieve variant recursivity using std::variant. I thought this might be of interest, since the stl doesn't provide any api for recursive, nor forward-declared types. Compiles using gcc 7.2 -std=c++17

#include <variant>
#include <vector>
#include <iostream>
#include <algorithm>

using namespace std;

struct Nil {};

struct vector1;

using var_t1 = variant<Nil, int, vector1>;
using var_t2 = variant<Nil, double, float, int, var_t1>;

struct vector1 { 
    vector<var_t2> v_; 
};

struct print_var_t2;

struct print_var_t1 {
    void operator()(const vector1& v);
    void operator()(int) { cout << "int\n"; }
    void operator()(const Nil&) { cout  << "nil\n"; }
};

struct print_var_t2 {
    void operator()(const Nil&) { cout << "Nil\n"; } 
    void operator()(int)  { cout << "int\n"; }
    void operator()(double) { cout << "double\n"; }
    void operator()(float)  { cout << "float\n"; }
    void operator()(const var_t1& v);
};

void print_var_t1::operator()(const vector1& v) {
    for_each(v.v_.begin(), v.v_.end(), [](const var_t2& x)
    {
        visit(print_var_t2{}, x);
    });
}

void print_var_t2::operator()(const var_t1& v) {
    visit(print_var_t1{}, v);    
}

int main()
{
    vector1 v1;
    v1.v_.push_back(.1);
    v1.v_.push_back(2.f);
    v1.v_.push_back(3);
    v1.v_.push_back(var_t2{3});

    var_t1 var1 = v1;

    std::visit(print_var_t1{}, var1);
    return 0;
}

edited Aug 22 '17 at 22:46

answered Aug 22 '17 at 15:17

Michaël Roy

6,338
1
15
19

Those variants are not recursive. You define a `recursive_variant` that looks like it should be named `recursive_wrapper`. But it isn't used. If you had used it, it would have the exact same problem because it requires the template argument `T` defined to be a complete type as well, AFAICT. – sehe Aug 22 '17 at 22:44
1. Thanks for the correction. 2. But not if T is a forward declared struct. – Michaël Roy Aug 22 '17 at 22:48
forward declared is the definition of "incomplete type". You cannot do some things with those (like, any operation that requires `sizeof(T)` to be known, like, you know, declaring a member variable of type `T`) – sehe Aug 22 '17 at 22:56
Nobody disputes that. – sehe Aug 22 '17 at 22:59
After removing the bad bits, your answer shows that you can write the same with `std::variant<>` instead of `boost::variant<>`. It's because `std::vector<>` is effectively a multi-valued recursive_wrapper. – sehe Aug 22 '17 at 23:00
Yup. This was the point of my post. boost variant offers a wrapper but not the stl. spirit and spirit::x3 also offer their own wrapper, but in the end any kind of wrapper will do. including a smart pointer. I posted this in case someone using std::variant, and who had the same issue, stumbles upon this question in the future. Your answer is perfect for boost::variant users. – Michaël Roy Aug 22 '17 at 23:08
The original question doesn't require recursive_wrapper. I contended that the wrapper you posted couldn't work (I'll check tomorrow). Now that it's removed I wonder what this answer adds. – sehe Aug 22 '17 at 23:12
As it says, not a solution per se, but a technique. You have to remember that any small error in variant declarations may generate hundreds of lines of error listing, – Michaël Roy Aug 22 '17 at 23:40
@MichaëlRoy As soon as I try to do a recursive variant nested in a variant itself within the recursive variant type, I run into problems. At the very least the struct-based technique as you exhibit nicely here with std::variant and as is shown in the link in sehe's answer works. I'll see what materializes in the next couple days here, but I'm starting to think that a purely variant-based design (i.e. without wrappers) isn't worth it. – rg6 Aug 23 '17 at 13:23

C++ Mutually Recursive Variant Type (Again)

Edit

2 Answers2

Live Demo

CAVEATS

Linked