What C++20 change to reverse_iterator is breaking this code?

Question

The following code compiles in C++11, C++14, and C++17, but does not compile in C++20. What change to the standard broke this code?

#include <vector>
#include <utility>

template<typename T>
struct bar
{
    typename T::reverse_iterator x;
};

struct foo
{
    bar<std::vector<std::pair<foo, foo>*>> x;
};

int main()
{
    foo f;
}

The error is quite long, but can be summarized as:

template argument must be a complete class

Answer 1

This was always undefined. [res.on.functions]/2.5 says:

In particular, the effects are undefined in the following cases:

• [...]
• 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.

std::pair does not (and cannot) support incomplete types. You were just relying on order of instantiation to kind of get around that. Something changed in the library that slightly changed the evaluation order, leading to the error. But undefined behavior is undefined - it happened to work before and it happens to not work now.

---

As to why it's specifically C++20 that is causing this to fail. In C++20, iterators changed to have this new iterator_concept idea. In order to instantiate that, reverse_iterator needs to determine what the concept should be. That looks like this:

#if __cplusplus > 201703L && __cpp_lib_concepts
      using iterator_concept
    = conditional_t<random_access_iterator<_Iterator>,
            random_access_iterator_tag,
            bidirectional_iterator_tag>;
      using iterator_category
    = __detail::__clamp_iter_cat<typename __traits_type::iterator_category,
                     random_access_iterator_tag>;
#endif

Now, in the process of checking random_access_iterator, the root of iterator concept hierarchy is wonderfully named input_or_output_iterator, specified in [iterator.concept.iterator]:

template<class I>
  concept input_or_output_iterator =
    requires(I i) {
      { *i } -> can-reference;
    } &&
    weakly_incrementable<I>;

So, we have to do *i on our iterator type. That's __gnu_cxx::__normal_iterator<std::pair<foo, foo>**, std::vector<std::pair<foo, foo>*> > , in this case. Now, *i triggers ADL - because of course it does. And ADL requires instantiation of all the associated types - because those associated types might have injected friends that could be candidates!

This, in turn, requires instantiating pair<foo, foo> - because, we have to check. And then that ultimately fails in this specific case because instantiating a type requires instantiating all of the type's special member functions, and the way that libstdc++ implements conditional assignment for std::pair is using Eric Fisellier's trick:

      _GLIBCXX20_CONSTEXPR pair&
      operator=(typename conditional<
        __and_<is_copy_assignable<_T1>,
               is_copy_assignable<_T2>>::value,
        const pair&, const __nonesuch&>::type __p)
      {
    first = __p.first;
    second = __p.second;
    return *this;
      }

And is_copy_assignable requires complete types and we don't have one.

But really even if pair used concepts to check in this case, that would still involve instantiating the same type traits, so we'd ultimately end up in the same position.

Moral of the story is, undefined behavior is undefined.