"error: invalid application of ‘sizeof’ to incomplete type" fixed by reordering struct definitions

Question

For reference, I use the following type definitions:

typedef bool Bool;
typedef std::monostate Empty;

template <typename... Ts> using TupleT = std::tuple<Ts...>;

template <typename... Types> struct VariantT {
    static_assert(sizeof...(Types) > 0, "VariantT must have at least one type");

    std::uint8_t tag;
    std::aligned_union_t<0, Types...> value;
};

When I define the following recursive types:

struct ConsBool;
struct ConsListBool;
struct Nil;

typedef VariantT<ConsBool, Nil> ListBool;
typedef VariantT<ConsListBool, Nil> ListListBool;

struct ConsBool
{
    using type = TupleT<Bool, ListBool *>;
    type value;
};

struct ConsListBool
{
    using type = TupleT<ListBool, ListListBool *>;
    type value; // <- this line causes the error
};

struct Nil
{
    Empty value;
};

error: invalid application of ‘sizeof’ to incomplete type ‘Nil’

But, when I use an alternative order:

struct Nil;
struct ConsBool;
struct ConsListBool;

typedef VariantT<ConsBool, Nil> ListBool;
typedef VariantT<ConsListBool, Nil> ListListBool;

struct Nil
{
    Empty value;
};

struct ConsBool
{
    using type = TupleT<Bool, ListBool *>;
    type value;
};

struct ConsListBool
{
    using type = TupleT<ListBool, ListListBool *>;
    type value;
};

It compiles.

Why is this? And what's the logic behind the ordering?

I'm using gcc (Debian 12.2.0-14) 12.2.0

The full error message is included below:

/usr/include/c++/12/type_traits: In instantiation of ‘const std::size_t std::__strictest_alignment<Nil>::_S_size’:
/usr/include/c++/12/type_traits:2136:57:   required from ‘const std::size_t std::__strictest_alignment<ConsBool, Nil>::_S_size’
/usr/include/c++/12/type_traits:2157:56:   required from ‘const std::size_t std::aligned_union<0, ConsBool, Nil>::_S_len’
/usr/include/c++/12/type_traits:2163:71:   required from ‘struct std::aligned_union<0, ConsBool, Nil>’
/usr/include/c++/12/type_traits:2606:11:   required by substitution of ‘template<long unsigned int _Len, class ... _Types> using aligned_union_t = typename std::aligned_union::type [with long unsigned int _Len = 0; _Types = {ConsBool, Nil}]’
include/types/compound.hpp:19:39:   required from ‘struct VariantT<ConsBool, Nil>’
/usr/include/c++/12/tuple:69:23:   required from ‘struct std::_Tuple_impl<0, VariantT<ConsBool, Nil>, VariantT<ConsListBool, Nil>*>’
/usr/include/c++/12/tuple:981:11:   required from ‘class std::tuple<VariantT<ConsBool, Nil>, VariantT<ConsListBool, Nil>*>’
include/main/main.hpp:   required from here
/usr/include/c++/12/type_traits:2136:9: error: invalid application of ‘sizeof’ to incomplete type ‘Nil’
 2136 |         sizeof(_Tp) > __strictest_alignment<_Types...>::_S_size

Answer 1

Here are the important lines:

struct Nil;

struct ConsBool
{
    using type = TupleT<Bool, ListBool *>;
    type value;
};

struct ConsListBool
{
    using type = TupleT<ListBool, ListListBool *>;
    type value; // <- this line causes the error
};

In ConsBool, ListBool* is a pointer, but in ConsListBool, it is not. A pointer is a complete type, while ListBool is not due to Nil not being a complete type. When you reordered, you made Nil and ListBool complete types.