c++ - Name resolution for recursive trailing return type

Question

I found a weird difference between explicit and automatic trailing return types.

In the following code, we define a struct templated on an integer and an iter function, which take one object of this type as argument. The return type depends on the result of calling itself after decrementing the template value.

To break the instantiation loop (or so I thought), I provide a specialization which returns a non-dependent type.

We have a toy main to instantiate the templates.

Here is a bit of code:

template<int i> struct Int {};

constexpr auto iter(Int<0>) -> Int<0>;

template<int i> constexpr auto iter(Int<i>) -> decltype(iter(Int<i-1>{}));

int main(){
  decltype(iter(Int<10>{})) a;
}

This code does not work in both gcc 4.9 and clang 3.5. Both trigger infinite instantiation (they don't match the specialized base case).

rec.cpp:11:62: fatal error: recursive template instantiation exceeded maximum depth of 256
template<int i> constexpr auto iter(Int<i>) -> decltype(iter(Int<i-1>{}));

Now, if we use C++14 decltype(auto) and we provide a body for the template which returns the exact same thing:

template<int i> struct Int {};

constexpr auto iter(Int<0>) -> Int<0>;

template<int i>
constexpr auto iter(Int<i>) -> decltype(auto) {
  return iter(Int<i-1>{});
}

int main(){
  decltype(iter(Int<10>{})) a;
}

This now works for both compilers and behave as expected.

I tried different ways to express the specialization and moved it around a bit (to be careful about its location), but that didn't prevent its self-immolation ;(

I also tried to sprinkle the code with more decltype and declval, but I can't seem to get the C++11 syntax working.

Could someone explain the difference between the two syntaxes for the name lookup?

Answer 1

It's because of the relative ordering of overload resolution, template overload resolution, template declaration instantiation, and template definition instantiation.

Let's look at the C++11 case first. When the compiler needs to evaluate decltype(iter(Int<0>{})), it performs overload resolution on the name iter called with arguments prvalue Int<0>. Since a template is in the overload set, we apply 14.8.3 [temp.over]:

1 - A function template can be overloaded either by (non-template) functions of its name or by (other) function templates of the same name. When a call to that name is written (explicitly, or implicitly using the operator notation), template argument deduction (14.8.2) and checking of any explicit template arguments (14.3) are performed for each function template to find the template argument values (if any) that can be used with that function template to instantiate a function template specialization that can be invoked with the call arguments. [...]

As a result, the declaration template<int i> constexpr auto iter(...) -> ... is instantiated (14.7.1p10 [temp.inst]) with i = 0, which forces the evaluation of decltype(iter(Int<-1>{})) and off down the rabbit hole of negative integers we go.

It doesn't matter that constexpr auto iter(Int<0>) -> Int<0> would be a better overload (by 13.3.3p1 [over.match.best]), because we never get that far; the compiler is away marching merrily towards negative infinity.

By contrast, with C++14 deduced return types 7.1.6.4p12 [dcl.spec.auto] applies:

12 - Return type deduction for a function template with a placeholder in its declared type occurs when the definition is instantiated [...]

Since definition instantiation occurs after template overload resolution (14.7.1p3), the bad template iter<0> is never instantiated; 14.8.3p5:

5 - Only the signature of a function template specialization is needed to enter the specialization in a set of candidate functions. Therefore only the function template declaration is needed to resolve a call for which a template specialization is a candidate.

The "signature" of iter<0> here is (Int<0>) -> decltype(auto), a signature containing a placeholder type (7.1.6.4).

---

Suggested workaround: use SFINAE to prevent any attempted call to iter(Int<-1>{}):

template<int i> constexpr auto iter(Int<i>)
  -> decltype(iter(typename std::enable_if<i != 0, Int<i-1>>::type{}));
                   ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^        ^^^^^^^

Note that the SFINAE has to go inside the decltype, and indeed inside the call to iter.