Using Std::Variant with Recursion, Without Using Boost::Recursive_Wrapper

Why is boost::recursive_wrapper not working in this case

Variants default-construct to their first element type.

This indeed directly leads to an infinite loop. (Demo)

The way to solve it is to make the default variant element not re-entrant or to make it lazily constructed. In this case, you can simply re-arrange to make int the first element.

Better yet, there doesn't seem to be a need to reflect the operator precedence hieararchy (as it is expressed in the rules) in the resultant tree, so why not simplify to:

struct unary_expression;
struct binary_expression;

enum operators { op_eq, op_ne };

using expression = boost::variant<
    int, 
    boost::recursive_wrapper<unary_expression>,
    boost::recursive_wrapper<binary_expression>
>;

struct unary_expression {
    expression expr;
};

struct binary_expression {
    expression                                    first;
    std::vector<std::pair<operators, expression>> other;
};

This no longer crashes and seems a bit simpler in adaptation and usage.

Simplified Full Demo

This full demo uses that AST, but adds a true unary expression. A few style things have been fixed:

• don't expose the skipper unless you intend for the caller to change it
• make the parser const
• show unparsed trailing data (or instead assert >> qi::eoi)

Note: I might have changed the precedence rules (specifically, associativity of binary operators). I'm not sure which version you require.

Live On Coliru

//#define BOOST_SPIRIT_DEBUG
#include <boost/spirit/include/qi.hpp>
#include <boost/fusion/include/adapt_struct.hpp>
#include <boost/fusion/include/std_pair.hpp>
#include <iostream>
#include <string>
#include <vector>

namespace ast {
    struct unary_expression;
    struct binary_expression;

    enum operators { op_eq, op_ne };

    using expression = boost::variant<
        int, 
        boost::recursive_wrapper<unary_expression>,
        boost::recursive_wrapper<binary_expression>
    >;

    struct unary_expression {
        bool negated = false;
        expression expr;
    };

    struct binary_expression {
        expression                                    first;
        std::vector<std::pair<operators, expression>> other;
    };

}

BOOST_FUSION_ADAPT_STRUCT(ast::unary_expression, negated, expr)
BOOST_FUSION_ADAPT_STRUCT(ast::binary_expression, first, other)

namespace ast {
    static inline std::ostream& operator<<(std::ostream& os, operators op) { return os << (op==op_eq?"==":"!="); }
    static inline std::ostream& operator<<(std::ostream& os, binary_expression const& e) { 
        os << e.first;
        for (auto& oe : e.other)
            os << " " << oe.first << " " << oe.second;
        return os;
    }
    static inline std::ostream& operator<<(std::ostream& os, unary_expression const& e) {
        return os << (e.negated?"!":"") << "(" << e.expr << ")";
    }
}

namespace client
{
    namespace qi = boost::spirit::qi;

    template <typename Iterator>
    class expression_grammar : public qi::grammar<Iterator, ast::expression()> {
      private:
        qi::symbols<char, ast::operators> operators;
        qi::rule<Iterator, ast::expression()> start;

        qi::rule<Iterator, ast::expression(),        qi::space_type> simple_expression;
        qi::rule<Iterator, ast::unary_expression(),  qi::space_type> unary_expression;
        qi::rule<Iterator, ast::binary_expression(), qi::space_type> binary_expression;
        qi::rule<Iterator, ast::expression(),        qi::space_type> expression;

      public:
        expression_grammar() : expression_grammar::base_type(start, "expression") {
            using namespace qi;

            operators.add
                ("==", ast::op_eq)
                ("!=", ast::op_ne)
                ;

            simple_expression =
                ( '(' > expression > ')' )
                | int_;

            unary_expression = 
                matches['!'] >> simple_expression;

            binary_expression =
                unary_expression >> *(operators > expression);

            expression = binary_expression;

            start = skip(space) [ expression ];

            BOOST_SPIRIT_DEBUG_NODES((expression)(binary_expression)(unary_expression)(simple_expression))
        }
    };

} // namespace client

int main() {
    using It = std::string::const_iterator;
    client::expression_grammar<It> const program;

    std::string const input{"1 == !(1 != 0)"};
    It iter = input.begin(), end = input.end();
    ast::expression out;

    if (parse(iter, end, program, out)) {
        std::cout << "Parsed: " << out << std::endl;
    } else {
        std::cerr << "Parsing failed." << std::endl;
        return 1;
    }

    if (iter != end) {
        std::cout << "Remaining unparsed input: '" << std::string(iter, end) << "'\n";
    }
}

Prints

Parsed: (1) == !((1) != (0))

C++ Mutually Recursive Variant Type (Again)

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

Composing boost::variant visitors for recursive variants

Firstly, I'd suggest the variant to include all possible node types, not distinguishing between mult and expression. This distinction makes no sense at the AST level, only at a parser stage (if you implement operator precedence in recursive/PEG fashion).

Other than that, here's a few observations:

• if you encapsulate the apply_visitor dispatch into your evaluation functor you can reduce the code duplication by a big factor

• your real question seems not to be about composing variants, but composing visitors, more specifically, by inheritance.

  You can use using to pull inherited overloads into scope for overload resolution, so this might be the most direct answer:

  Live On Coliru

   struct better_mult_calculator : calculator {
       using calculator::operator();
  
       auto operator()(const binop<mult>& binary) const
       {
           return boost::apply_visitor(*this, binary.left) *
               boost::apply_visitor(*this, binary.right);
       }
   };
  

IMPROVING!

Starting from that listing let's shave off some noise!

1. remove unncessary AST distinction (-40 lines, down to 55 lines of code)

2. generalize the operations; the <functional> header comes standard with these:

   namespace AST {
       template <typename> struct binop;
       using add  = binop<std::plus<>>;
       using sub  = binop<std::minus<>>;
       using mult = binop<std::multiplies<>>;
       using expr = boost::variant<int,
           recursive_wrapper<add>,
           recursive_wrapper<sub>,
           recursive_wrapper<mult>>;
   
       template <typename> struct binop { expr left, right; };
   } // namespace AST
   

   Now the entire calculator can be:

   struct calculator : boost::static_visitor<int> {
       int operator()(int value) const { return value; }
   
       template <typename Op> 
       int operator()(AST::binop<Op> const& binary) const {
           return Op{}(boost::apply_visitor(*this, binary.left),
                       boost::apply_visitor(*this, binary.right));
       }
   };
   

   Here your variant can add arbitrary operations without even needing to touch the calculator.

   Live Demo, 43 Lines Of Code

3. Like I mentioned starting off, encapsulate visitation!

   struct Calculator {
       template <typename... T> int operator()(boost::variant<T...> const& v) const {
           return boost::apply_visitor(*this, v);
       }
   
       template <typename T> 
       int operator()(T const& lit) const { return lit; }
   
       template <typename Op> 
       int operator()(AST::binop<Op> const& bin) const {
           return Op{}(operator()(bin.left), operator()(bin.right));
       }
   };
   

   Now you can just call your calculator, like intended:

   Calculator calc;
   auto result1 = calc(e1);
   

   It will work when you extend the variant with operatios or even other literal types (like e.g. double). It will even work, regardless of whether you pass it an incompatible variant type that holds a subset of the node types.

4. To finish that off for maintainability/readability, I'd suggest making operator() only a dispatch function:

Full Demo

Live On Coliru

#include <boost/variant.hpp>
#include <iostream>

namespace AST {
    using boost::recursive_wrapper;

    template <typename> struct binop;
    using add  = binop<std::plus<>>;
    using sub  = binop<std::minus<>>;
    using mult = binop<std::multiplies<>>;
    using expr = boost::variant<int,
        recursive_wrapper<add>,
        recursive_wrapper<sub>,
        recursive_wrapper<mult>>;

    template <typename> struct binop { expr left, right; };
} // namespace AST

struct Calculator {
    auto operator()(auto const& v) const { return call(v); }

  private:
    template <typename... T> int call(boost::variant<T...> const& v) const {
        return boost::apply_visitor(*this, v);
    }

    template <typename T> 
    int call(T const& lit) const { return lit; }

    template <typename Op> 
    int call(AST::binop<Op> const& bin) const {
        return Op{}(call(bin.left), call(bin.right));
    }
};

int main()
{
    using namespace AST;
    std::cout << std::boolalpha;
    auto sub_expr = add{sub{7, 3}, 8};
    expr e1       = sub_expr;
    expr e2       = mult{sub_expr, 2};

    Calculator calc;

    auto result1 = calc(e1);
    std::cout << "result1:  " << result1 << " Success? " << (12 == result1) << "\n";

    // result2 = ((7-3)+8)*2 = 12
    auto result2 = calc(e2);
    std::cout << "result2:  " << result2 << " Success? " << (24 == result2) << "\n";
}

Still prints

result1:  12 Success? true
result2:  24 Success? true

Recursive pair via boost.Variant broken since boost 1.62

I think you're actually running into a similar change to std::pair<> seen here: does boost-1.55 boost::property_tree::ptree compile with c++11?

There are fewer implicit conversions for std::pair since c++11. It is true that your code did compile boost < 1.62 but, in essence it looks like that was a mistake, at least in c++11 mode.

In C++11, you are doing this:

std::make_pair(s, i); // s is std::string, i is int

which results in std::pair<std::string, int>. Next you're not only asking an implicit conversion of std::pair<std::string, int> to std::pair<std::string, IntPairVariant>, but you're expecting to use the result of that conversion as the initializer for the variant you're assigning.

In all parts of C++, that's asking for two implicit conversions and the compiler would never resolve an overload using that.

So, in effect your code was bit sloppy in that it used "leeway" that Boost Variant should likely not not have had. It is a breaking change, but the new behaviour seems to make more sense.

Another note

You're making a recursive variant with a single element. That's... a bit weird.

This "strains" the type system a bit more than necessary by hiding the std::pair<> structural property under the first layer of variant.

Using A std::pair directly

Live On Coliru

The most boring thing I can imagine:

#include <boost/variant.hpp>
#include <string>

using namespace std;

typedef std::pair<std::string,
    boost::make_recursive_variant<int, std::pair<std::string, boost::recursive_variant_> >::type >
    recursivePair;

typedef boost::variant<int, recursivePair> intPairVariant;

int main() {
    recursivePair xxx(std::string("s"), intPairVariant());
    recursivePair yyy(string("s"), 5);
    recursivePair zzz("s", 5);
}

Note this already allows the exact spellings in your question:

recursivePair xxx(std::make_pair(std::string("s"), intPairVariant()));
recursivePair yyy(std::make_pair(string("s"), 5));
recursivePair zzz(std::make_pair("s", 5));

But make_pair is redundant in all three cases.

Interesting Variations

Perhaps you can do something more like

struct V;
using Pair = std::pair<std::string, V>;

struct V : boost::variant<int, boost::recursive_wrapper<Pair> > {
    using base = boost::variant<int, boost::recursive_wrapper<Pair> >;
    using base::base;
    using base::operator=;
};

Now you can safely say

Live On Coliru

Pair xxx("s", V{});
Pair yyy("s", 5);
Pair zzz{};

Helping The Constructor

The upside of having the derived struct instead of a plain variant is that you can actually disambiguate constructors:

Live On Coliru

#include <boost/variant.hpp>
#include <string>
#include <iostream>

namespace mylib {

    struct V;
    using Pair = std::pair<std::string, V>;

    struct V : boost::variant<int, boost::recursive_wrapper<Pair> > {
        using base = boost::variant<int, boost::recursive_wrapper<Pair> >;

        V() = default;
        V(V&&) = default;
        V(V const&) = default;
        V& operator=(V&&) = default;
        V& operator=(V const&) = default;

        V(int i) : base(i) {}
        V(std::string const& key, V value);
    };

    V::V(std::string const& key, V value) : base{Pair{std::move(key), std::move(value)}} {}

    static inline std::ostream& operator<<(std::ostream& os, Pair const& p) {
        return os << "{" << p.first << "," << p.second << "}";
    }
}

int main() {
    using mylib::V;
    V xxx("s", mylib::V{});
    V yyy("s", 5);
    V zzz{};
    V huh("s", {"more", {"intricate", {"nested", { "truths", 42} } } });

    V simple = 5;
    simple = {"simple", 5};
    simple = {"not_so_simple", simple};

    std::cout << "xxx:" << xxx << "\n";
    std::cout << "yyy:" << yyy << "\n";
    std::cout << "zzz:" << zzz << "\n";
    std::cout << "huh:" << huh << "\n";
    std::cout << "simple:" << simple << "\n";
}

Prints

xxx:{s,0}
yyy:{s,5}
zzz:0
huh:{s,{more,{intricate,{nested,{truths,42}}}}}
simple:{not_so_simple,{simple,5}}

---

Related Topics