Simple recursive box without container

[ajihyf]

Thanks for authoring this library.

I'm trying to implement a simple recursive data structure.

struct Expr;

struct BinaryExpr {
  immer::box<Expr> left;
  immer::box<Expr> right;
};

The compiler throws an error below

In file included from /Applications/Xcode.app/Contents/Developer/Toolchains/XcodeDefault.xctoolchain/usr/bin/../include/c++/v1/cstddef:110:
/Applications/Xcode.app/Contents/Developer/Toolchains/XcodeDefault.xctoolchain/usr/bin/../include/c++/v1/type_traits:2803:38: error: incomplete type 'Expr' used in type trait expression
    : public integral_constant<bool, __is_constructible(_Tp, _Args...)>
                                     ^
bazel-out/darwin-opt/bin/external/immer/_virtual_includes/immer/immer/box.hpp:76:24: note: in instantiation of template class 'std::__1::is_constructible<Expr, immer::box<Expr, immer::memory_policy<immer::free_list_heap_policy<immer::cpp_heap, 1024>, immer::refcount_policy, immer::spinlock_policy, immer::no_transience_policy, false, true> > >' requested here
                  std::is_constructible<T, Arg>::value>>
                       ^
bazel-out/darwin-opt/bin/external/immer/_virtual_includes/immer/immer/box.hpp:77:5: note: in instantiation of default argument for 'box<immer::box<Expr, immer::memory_policy<immer::free_list_heap_policy<immer::cpp_heap, 1024>, immer::refcount_policy, immer::spinlock_policy, immer::no_transience_policy, false, true> > >' required here
    box(Arg&& arg)

[arximboldi]

That depends on the definition of Expr. I think this is not the whole picture. I suspect its definition is:

struct Expr {
   std::variant<BinaryExpr, UnaryExpr, ...> expr;
};

Right? And maybe that std::variant is forcing checking is_constructible before the full definition of Expr is available for it to succeed on BinaryExpr... You can play with things a little bit, it's hard to tell without a concrete example. Maybe you can simplify things by explicitly defining constructors for Expr or something.

[ajihyf]

Thanks for your instant reply. Using std::variant may complicate this issue, the simple code below is also reproducible.

  struct a_type;

  struct b_type {
    b_type(int a, immer::box<a_type> val) : a(a), val(val) {}
    int a;
    immer::box<a_type> val;
  };

  struct a_type {
    a_type() : b{} {}
    std::optional<immer::box<b_type>> b;
  };

  b_type b(233, immer::box<a_type>());

In file included from test/test.cc:4:
In file included from external/gtest/googletest/include/gtest/gtest.h:55:
In file included from /Applications/Xcode.app/Contents/Developer/Toolchains/XcodeDefault.xctoolchain/usr/bin/../include/c++/v1/cstddef:110:
/Applications/Xcode.app/Contents/Developer/Toolchains/XcodeDefault.xctoolchain/usr/bin/../include/c++/v1/type_traits:2803:38: error: incomplete type 'a_type' used in type trait expression
    : public integral_constant<bool, __is_constructible(_Tp, _Args...)>
                                     ^
bazel-out/darwin-opt/bin/external/immer/_virtual_includes/immer/immer/box.hpp:76:24: note: in instantiation of template class 'std::__1::is_constructible<a_type, const immer::box<a_type, immer::memory_policy<immer::free_list_heap_policy<immer::cpp_heap, 1024>, immer::refcount_policy, immer::spinlock_policy, immer::no_transience_policy, false, true> > &>' requested here
                  std::is_constructible<T, Arg>::value>>
                       ^
bazel-out/darwin-opt/bin/external/immer/_virtual_includes/immer/immer/box.hpp:77:5: note: in instantiation of default argument for 'box<const immer::box<a_type, immer::memory_policy<immer::free_list_heap_policy<immer::cpp_heap, 1024>, immer::refcount_policy, immer::spinlock_policy, immer::no_transience_policy, false, true> > &>' required here
    box(Arg&& arg)
    ^~~~~~~~~~~~~~
bazel-out/darwin-opt/bin/external/immer/_virtual_includes/immer/immer/box.hpp:36:7: note: while substituting deduced template arguments into function template 'box' [with Arg = const immer::box<a_type, immer::memory_policy<immer::free_list_heap_policy<immer::cpp_heap, 1024>, immer::refcount_policy, immer::spinlock_policy, immer::no_transience_policy, false, true> > &, Enable = (no value)]

It seems that the problem comes from this constructor of box

    /*!
     * Constructs a box holding `T{arg}`
     */
    template <typename Arg,
              typename Enable = std::enable_if_t<
                  !std::is_same<box, std::decay_t<Arg>>::value &&
                  std::is_constructible<T, Arg>::value>>
    box(Arg&& arg)
        : impl_{detail::make<heap, holder>(std::forward<Arg>(arg))}
    {}

[arximboldi]

Hmmm, what if you move the definition of the constructor b_type::b_type(int a, immer::box<a_type> val) after the definition of a_type?

[ajihyf]

Still the same after I move constructors

struct a_type;

struct b_type {
  b_type(int a, immer::box<a_type> val);
  int a;
  immer::box<a_type> val;
};

struct a_type {
  a_type();
  std::optional<immer::box<b_type>> b;
};

b_type::b_type(int a, immer::box<a_type> val) : a(a), val(val) {}

a_type::a_type() : b{} {}

[arximboldi]

Interesting. To be fair I'm not so sure now what's going on, the rules about partial types and when they are allowed are quite subtle, I'd need a bit more investigation into the issue. Thanks for the report and elaborating a test case!

[arximboldi]

Hi @ajihyf! Sorry for the very late reply on this. I have done some small experiment here: 6770f16. I think the issue is with std::optional and not with immer. The synthesized example you showed works properly with boost::optional. Cheers!