Why does the following code compile using clang but not gcc

Question

#include <iostream>
#include <unordered_map>
#include <string>

struct tree_node {
  // tree_node() : attrib_val{"null"} {}
  std::unordered_map<std::string, tree_node> child;
};
int main(int argc, char const *argv[])
{
  return 0;
}

This code compiles just fine on my mac with clang:

$ g++ --version
Configured with: --prefix=/Library/Developer/CommandLineTools/usr --with-gxx-include-dir=/Library/Developer/CommandLineTools/SDKs/MacOSX10.14.sdk/usr/include/c++/4.2.1
Apple LLVM version 10.0.1 (clang-1001.0.46.4)
Target: x86_64-apple-darwin18.7.0
Thread model: posix
InstalledDir: /Library/Developer/CommandLineTools/usr/bin

$ g++ -std=c++11 test.cpp
$ 

On my linux machine, with gcc 9.1.0, I get the following error:

In file included from /usr/um/gcc-9.1.0/include/c++/9.1.0/bits/stl_algobase.h:64,
                 from /usr/um/gcc-9.1.0/include/c++/9.1.0/bits/char_traits.h:39,
                 from /usr/um/gcc-9.1.0/include/c++/9.1.0/ios:40,
                 from /usr/um/gcc-9.1.0/include/c++/9.1.0/ostream:38,
                 from /usr/um/gcc-9.1.0/include/c++/9.1.0/iostream:39,
                 from test.cpp:1:
/usr/um/gcc-9.1.0/include/c++/9.1.0/bits/stl_pair.h: In instantiation of ‘struct std::pair<const std::__cxx11::basic_string<char>, tree_node>’:
/usr/um/gcc-9.1.0/include/c++/9.1.0/ext/aligned_buffer.h:91:28:   required from ‘struct __gnu_cxx::__aligned_buffer<std::pair<const std::__cxx11::basic_string<char>, tree_node> >’
/usr/um/gcc-9.1.0/include/c++/9.1.0/bits/hashtable_policy.h:233:43:   required from ‘struct std::__detail::_Hash_node_value_base<std::pair<const std::__cxx11::basic_string<char>, tree_node> >’
/usr/um/gcc-9.1.0/include/c++/9.1.0/bits/hashtable_policy.h:264:12:   required from ‘struct std::__detail::_Hash_node<std::pair<const std::__cxx11::basic_string<char>, tree_node>, true>’
/usr/um/gcc-9.1.0/include/c++/9.1.0/bits/hashtable_policy.h:2016:13:   required from ‘struct std::__detail::_Hashtable_alloc<std::allocator<std::__detail::_Hash_node<std::pair<const std::__cxx11::basic_string<char>, tree_node>, true> > >’
/usr/um/gcc-9.1.0/include/c++/9.1.0/bits/hashtable.h:173:11:   required from ‘class std::_Hashtable<std::__cxx11::basic_string<char>, std::pair<const std::__cxx11::basic_string<char>, tree_node>, std::allocator<std::pair<const std::__cxx11::basic_string<char>, tree_node> >, std::__detail::_Select1st, std::equal_to<std::__cxx11::basic_string<char> >, std::hash<std::__cxx11::basic_string<char> >, std::__detail::_Mod_range_hashing, std::__detail::_Default_ranged_hash, std::__detail::_Prime_rehash_policy, std::__detail::_Hashtable_traits<true, false, true> >’
/usr/um/gcc-9.1.0/include/c++/9.1.0/bits/unordered_map.h:105:18:   required from ‘class std::unordered_map<std::__cxx11::basic_string<char>, tree_node>’
test.cpp:7:46:   required from here
/usr/um/gcc-9.1.0/include/c++/9.1.0/bits/stl_pair.h:215:11: error: ‘std::pair<_T1, _T2>::second’ has incomplete type
  215 |       _T2 second;                /// @c second is a copy of the second object
      |           ^~~~~~
test.cpp:5:8: note: forward declaration of ‘struct tree_node’
    5 | struct tree_node {

It doesn't like the tree_node as a value in unordered_map for some reason.

Answer 1

This is undefined behavior, by [res.on.functions]/2.5:

[The effects are undefined if] an incomplete type ([basic.types]) is used as a template argument when instantiating a template component or evaluating a concept, unless specifically allowed for that component.

This is an annoying case where I basically have to prove a negative for this answer to be valid, but I find no place in the standard that mentions an exception that allows you to use an incomplete type in a std::map. Therefore, this program can do anything. In particular, though Clang compiles it now, it may stop working at any point in the future, and there's also a chance that the compiled code map specialization doesn't work properly. Certain containers, especially std::vector, have a clause that allows them to be instantiated at incomplete types under the right conditions. But this case is undefined behavior, and so compilers have no obligation to warn you or error. Change your program somehow to avoid this. I believe the following would be legal, without forcing you to store too many extra pointers.

struct tree_node {
  std::unique_ptr<std::unordered_map<std::string, tree_node>> child;
};

std::unique_ptr is an exception to the general no-go rule—it's OK to instantiate it at an incomplete type (but some of its members aren't as lax). I believe that this means that std::unordered_map<std::string, tree_node> is not required to be complete at the point in the definition of tree_node where the specialization of std::unique_ptr is required to be complete, and so the std::unordered_map specialization is not triggered and UB is avoided since tree_node is not required to be complete. Note that you can still write constructors, functions, a destructor, etc. without worry, since all of those definitions are implicitly moved out of and after the class definition, and tree_node becomes complete after the class definition ends.

Answer 2

Changing:

struct tree_node {
  // tree_node() : attrib_val{"null"} {}
  std::unordered_map<std::string, tree_node> child;
};

To:

struct tree_node {
  // tree_node() : attrib_val{"null"} {}
  std::unordered_map<std::string, tree_node *> child;
};

Makes the compilation problem go away. Whether it has any reflection on what you wanted?