atdcpp: recursive types render cpp code that fails to compile

[dlindsaye]

First of all .. thanks to everyone who contributes to these tools.

Unfortunately I have run into a problem with atdcpp when using recursive types. Given the following (recurisive.atd):

type expr = [
  | Int of int
  | Negate of expr
]

I can run atdcpp to produce recursive_atd.cpp and recursive_atd.hpp. Compiling with:

 g++ -c -I ~/Work/rapidjson/include -std=c++17 recusive_atd.cpp 

yields a ton of error messages including:

/usr/include/c++/8/type_traits:1222:12: error: invalid use of incomplete type ‘struct atd::Expr::Types::Negate’
     struct is_trivially_destructible
            ^~~~~~~~~~~~~~~~~~~~~~~~~
In file included from recusive_atd.cpp:12:
recusive_atd.hpp:46:16: note: forward declaration of ‘struct atd::Expr::Types::Negate’
         struct Negate
                ^~~~~~

which to me, as a newbie C++ developer, suggests trouble with the forward declarations.

[dlindsaye]

I misspoke. This is not a problem with forward declarations. std::variant doesn't work well for defining recursive types.

[Khady]

@elrandar FYI

[dlindsaye]

Some experimentation and borrowing from the last entry here. Given mutually recursive types:

type expr = [
  | Num of int
  | Add of (expr * expr)
  | Switch of bool_expr
]

type bool_expr = [
  | Eq of (expr * expr)
  | Not of bool_expr
]

then it seems it works to abstract the recursive type references as parameters, and use structs to tie the knot:

namespace atd {

namespace BoolExpr {
    namespace Types {
        // Original type: bool_expr = [ ... | Eq of ... | ... ]
        template <typename Expr> struct Eq
        {
            std::tuple<Expr, Expr> value;
            static void to_json(const Eq &e, rapidjson::Writer<rapidjson::StringBuffer> &writer);
        };
        // Original type: bool_expr = [ ... | Not of ... | ... ]
        template <typename BoolExpr> struct Not
        {
            BoolExpr value;
            static void to_json(const Not &e, rapidjson::Writer<rapidjson::StringBuffer> &writer);
        };
    }
}

namespace Expr {
    namespace Types {
        // Original type: expr = [ ... | Num of ... | ... ]
        struct Num
        {
            int value;
            static void to_json(const Num &e, rapidjson::Writer<rapidjson::StringBuffer> &writer);
        };
        // Original type: expr = [ ... | Add of ... | ... ]
        template <typename Expr> struct Add
        {
            std::tuple<Expr, Expr> value;
            static void to_json(const Add &e, rapidjson::Writer<rapidjson::StringBuffer> &writer);
        };
        // Original type: expr = [ ... | Switch of ... | ... ]
        template <typename BoolExpr> struct Switch
        {
            BoolExpr value;
            static void to_json(const Switch &e, rapidjson::Writer<rapidjson::StringBuffer> &writer);
        };
    }
}

namespace typedefs {
    template <typename Expr, typename BoolExpr>
    using BoolExpr_v = std::variant<
        atd::BoolExpr::Types::Eq<Expr>,
        atd::BoolExpr::Types::Not<BoolExpr>
    >;
    struct BoolExpr_s;
    struct Expr_s;

    struct BoolExpr_s {
        using t = BoolExpr_v<Expr_s, BoolExpr_s>;
    };
    using BoolExpr = BoolExpr_s::t;

    template <typename Expr, typename BoolExpr>
    using Expr_v = std::variant<
        atd::Expr::Types::Num,
        atd::Expr::Types::Add<Expr>,
        atd::Expr::Types::Switch<BoolExpr>
    >;
    struct Expr_s {
        using t = Expr_v<Expr_s, BoolExpr_s>;
    };
    using Expr = Expr_s::t;
} // namespace typedefs
} // namespace atd

A more experienced C++ dev may have a more elegant solution.

[dlindsaye]

My code above is bogus. It would seem that one can define recursive algebraic types with std::variant and without using pointers (more or less), but it would seem to be impossible to construct an object of that type. The most common solution would seem to require wrapping recursive references in std::shared_ptr. Again, a more skilled C++ developer might know better.

[elrandar]

Hi, thank you for opening that issue.
My apologies for the late reply.

It is a known problem and I spend some time trying to find the right way to tackle it when implementing the C++ backend.

The solution I've landed on, which is quite heavy, but has the benefit of being easy to understand is; as you described above; to wrap the recursive references in std::shared_ptr

For that matter I introduced the templatize keyword, which will wrap in C++ with std::shared_ptr templated on the correct type, (here std::optional).

It can be done as so, using the helper functions already included :

type recursive_record2 = {
  id: int;
  flag: bool;
  children: recursive_record2 nullable wrap <cpp templatize t="std::shared_ptr" wrap="_atd_wrap_shared_ptr" unwrap="_atd_unwrap_shared_ptr">;}

The output will be

struct RecursiveRecord2 {
    int id;
    bool flag;
    std::shared_ptr<std::optional<typedefs::RecursiveRecord2>> children;

    static RecursiveRecord2 from_json(const rapidjson::Value & doc);
    static RecursiveRecord2 from_json_string(const std::string &s);
    static void to_json(const RecursiveRecord2 &t, rapidjson::Writer<rapidjson::StringBuffer> &writer);
    static std::string to_json_string(const RecursiveRecord2 &t);
    std::string to_json_string();
};

You can find more examples in the tests.

Similarly for a variant:

type recursive_variant = [
  | Integer of int
  | Rec of recursive_variant wrap <cpp templatize t="std::shared_ptr" wrap="_atd_wrap_shared_ptr" unwrap="_atd_unwrap_shared_ptr">
]

I would direct you towards looking at the Cpp test for these kind of cases, although the backend obviously needs more documentation.