[boost] [variant] awkward recursion

29 Oct 2012

      I've been playing around with variant a bit and decided to try to build
a data structure for storing json.  I came up with several different
approaches but none are super-satisfying.  I'd like some feedback.  (If
you need a refresher on what's in json, the front page of
http://json.org tells all).

In the abstract, json looks like:

  struct null {};
  typedef std::map<std::string, value> object;
  typedef std::vector<value> array;

  typedef variant<
     null, std::string, double, object, array, bool
...
value;
Naturally, this code isn't legal C++, so I set about making it be.

The first thing I tried was to use recursive_wrapper<>, as the
documentation implies it is the most flexible way to do this sort of
thing.  Unfortunately, there's no clean way to reformulate this type
in a way that allows recursive_wrapper work, because the type that needs
to be wrapped in recursive_wrapper includes "value" in its name, and I
can't forward-declare it.

The only way to forward-declare a type X, as far as I know, is:

    struct X; // or class X;

So to try to get recursive_wrapper to work, I tried a couple of
formulations that started with that, but it turns out that when you do
this, you end up not needing recursive_wrapper at all

  struct value;
  typedef std::map<std::string, value> object;
  typedef std::vector<value> array;

  typedef variant<
     null, std::string, double, object, array, bool
...
value_base;
struct value : value_base
  {
    value() {};

    template <class T>
    value(T const& x) : base(x) {} // no move; I'm in C++03-land
    value& operator=(value const& x) { base::operator=(x); return *this; }
    }
  };

I don't know if I've missed some things that should be in that "value"
class.  I know that a recursive variant, in principle, requires a
pointer indirection somewhere, so I was wondering if, had I wrapped
object and array in recursive_wrapper as below, I would have been adding
an unnecessary inefficiency.

  typedef variant<
     null, std::string, double, 
     reference_wrapper<object>, 
     reference_wrapper<array>, 
     bool
...
value_base;
I also wondered whether that would give me different results from 

  typedef std::map<std::string, value> object;
  typedef std::vector<value> array;

  typedef variant<
     null, std::string, double, 
     std::map<std::string, reference_wrapper<value> >, 
     std::vector<reference_wrapper<value> >, 
     bool
...
value_base;
and which one was better.  Does anyone know?  I think that should be in
the docs.  Using recursive_variant_ works out quite nicely, except that
it doesn't allow me to separately declare "object" and "array" and
re-use them in the definition of "value":

  typedef boost::make_recursive_variant<
      null
    , std::string
    , double
    , std::map<std::string, boost::recursive_variant_>
    , std::vector<boost::recursive_variant_>
    , bool
...
::type value;
I also wonder if I'm getting an unnecessary inefficiency in that case.

Lastly, what flexibility am I sacrificing by using this approach?

-- 
Dave Abrahams
BoostPro Computing                  Software Development        Training
http://www.boostpro.com             Clang/LLVM/EDG Compilers  C++  Boost