C++11: Overload fails to resolve recursive decltype

Question

In the following piece of code, I'm trying to build a lattice of types. For instance, between float and int, promote the result to float:

float join(float f, int)   { return f; }
float join(float f, float) { return f; }

Then I introduce a wrapper type:

template <typename Inner>
struct wrapper
{
  using inner_t = Inner;
  inner_t value;
};

whose behavior with the join operation quite natural:

template <typename Inner1, typename Inner2>
auto
join(const wrapper<Inner1>& w1, const wrapper<Inner2>& w2)
  -> wrapper<decltype(join(w1.value, w2.value))>
{
  return {join(w1.value, w2.value)};
}

It can also be joined with a "scalar" type:

template <typename Inner1, typename T2>
auto
join(const wrapper<Inner1>& w1, const T2& value2)
  -> wrapper<decltype(join(w1.value, value2))>
{
  return {join(w1.value, value2)};
}

So far, so good, it works. But then, because in the real case I actually have many more such rules, I'd like to avoid duplicating the number of rules to express the commutativity of the join operation, and therefore, I express that join(scalar, wrapper) := join(wrapper, scalar) (In fact, I'd prefer something like join(v1, v2) := join(v2, v1), but let's start with something more specific.):

template <typename T1, typename Inner2>
auto
join(const T1& value1, const wrapper<Inner2>& w2)
  -> decltype(join(w2, value1))
{
  return join(w2, value1);
}

this works properly for join(scalar, scalar), join(wrapper, scalar) and join(scalar, wrapper). But then join(wrapper, wrapper) results in an infinite expansions of template functions with both G++ 4.9 and Clang++ 3.5, which I don't understand.

int main()
{
  int i;
  float f;
  wrapper<float> fr;
  join(f, i);
  join(fr, i);
  join(i, fr);
  join(fr, fr); // Loops.
}

Clang:

clang++-mp-3.5 -std=c++11 bar.cc
bar.cc:21:5: fatal error: recursive template instantiation exceeded maximum depth of
      256
    join(const wrapper<Inner1>& w1, const T2& value2)
    ^
bar.cc:29:5: note: while substituting deduced template arguments into function
      template 'join' [with T1 = wrapper<float>, Inner2 = float]
    join(const T1& value1, const wrapper<Inner2>& w2)
    ^

GCC:

g++-mp-4.9 -std=c++11 bar.cc
bar.cc:30:34: error: template instantiation depth exceeds maximum of 900 (use -ftemplate-depth= to increase the maximum) substituting 'template<class T1, class Inner2> decltype (join(w2, value1)) join(const T1&, const wrapper<Inner2>&) [with T1 = <missing>; Inner2 = <missing>]'
       -> decltype(join(w2, value1))
                                  ^
bar.cc:30:34:   recursively required by substitution of 'template<class T1, class Inner2> decltype (join(w2, value1)) join(const T1&, const wrapper<Inner2>&) [with T1 = wrapper<float>; Inner2 = float]'
bar.cc:30:34:   required by substitution of 'template<class T1, class Inner2> decltype (join(w2, value1)) join(const T1&, const wrapper<Inner2>&) [with T1 = wrapper<float>; Inner2 = float]'
bar.cc:43:18:   required from here

I do not understand why overloading does not cut the recursion. What is going on? There is probably a possible alternative implementation with (class) template specialization, but I'm not looking for alternative implementations: I'd like to understand what's wrong with this one. Thanks in advance.

Answer 1

There are several problems with this, and one of them leads to the error.

template <typename Inner1, typename T2>
auto
join(const wrapper<Inner1>& w1, const T2& value2)  // (A)
  -> wrapper<decltype(join(w1.value, value2))>;

The name lookup of join here will not find the same function template via unqualified lookup, as the trailing-return-type is part of the declaration, and names can only be found once they have been declared. But the syntax allows ADL to find the same function template. ADL for dependent names is performed later (from the point of instantiation).

As far as I understood the problem, the issue comes from overload resolution: Before decltype(join(w1.value, value2)) tries to resolve to an overload, all function templates with that name need to be instantiated. For each function template, one instantiation is added to the overload set (if instantiation succeeds).

Therefore, all joins need to be instantiated. Instantiation includes determining the return type. For every instantiation of this particular join function template (A), the same function template (A) with the same template arguments is a candidate for the overload resolution set. That is, to determine which return type (A) has, there needs to be an overload resolution, which requires to determine the return type of (A) and so on.

Deduction & substitution never fails in any single step of the recursion, the only reason not to choose this overload is partial ordering between the different function templates called join. And partial ordering is only checked as part of the overload resolution process -- which is too late to prevent further instantiations.

This error, as mentioned in the error message, occurs as an implementation limit. Therefore, it does not fall into the SFINAE category, see Solving the SFINAE problem for expressions. Therefore, even if this overload is not chosen, its mere existence makes the program ill-formed, just like

struct tag_for_ADL {};

template<class T>
auto foo(T p) -> decltype(foo(p));

foo(tag_for_ADL{}); // ill-formed, leads to infinite recursive instantiation