How does C++ resolve specialized templates considering constness, templated-ness, and genericness?

Question

I have the following code, which may seem convoluted but comes from real code:

#include <iostream>
using namespace std;

template <class Hrm, class A>
void foo(Hrm& h, A& a)
{
  cout << "generic" << endl;
}

template <template <bool> class Hrg>
void foo(Hrg<false>& h, int& a)
{
  cout << "specialized int" << endl;
}

template <template <bool> class Hrg>
void foo(Hrg<true>& h, const int& a)
{
  cout << "specialized const-int" << endl;
}

template <bool W>
struct what;

template<> struct what<true> { };
template<> struct what<false> { };


int main() {
  what<true> wt;
  what<false> wf; 

  int i = 5;
  const int& ri = i;

  foo(wt, i);  // 1) generic
  foo(wf, i);  // 2) specialized int
  foo(wt, ri); // 5) specialized const-int
  foo(wf, ri); // 6) generic
  return 0;
}

Ideone link.

I understand 4: there is no specialization for a false Hrg with a const int, so the generic version is called.

My question is, why are the given functions called for the other cases? 3 seems to called the specialized const version because const int matches "more directly" than A. I'd like to know why that happens more specifically.

And, what about 1 and 2? Particularly, 1 very surprising to me: why is the generic version called instead of specialized const-int?

---

An additional note: if I change the two foo specializations to:

template <template <bool> class Hrg>
void _foo(Hrg<false>& h, int& a)
{
  cout << "specialized int" << endl;
}

template <template <bool> class Hrg>
void _foo(Hrg<true>& h, const int& a)
{
  cout << "specialized const-int" << endl;
}

template <class Hrg>
void foo(Hrg& h, int& a)
{
  return _foo(h, a);
}

template <class Hrg>
void foo(Hrg& h, const int& a)
{
  return _foo(h, a);
}

Then the output becomes:

foo(wt, i);     // a) specialized const-int
foo(wf, i);     // b) specialized int
foo(wt, ri);    // c) specialized const-int
//foo(wf, ri);  // d) compilation error

Which is a much more intuitive result for me.

Answer 1

Overload resolution occurs in the following steps:

1. A set of candidate functions is assembled. This set of candidates consists of both non-template functions and specializations of function templates. If template parameter deduction fails on a function template, it's silently removed from the set of candidates.
2. A subset of candidate functions are determined to be viable. That means the number of parameters it has is compatible with the number of arguments and that each argument can be implicitly converted to the corresponding parameter type. (Note that a function if viable even if a conversion is ambiguous; but in that case this function might still be chosen, and then you get a compilation error afterward).
3. Viable functions are compared. For a given pair of viable functions, the one that, in a sense, requires less implicit conversion in order to initialize the function's parameters from the given arguments, is considered "better" than the other function. Note that it's possible that given two functions, neither one is better than the other. Often, these rules are sufficient to establish that a single viable function is better than all the others. That function would then win overload resolution.
4. If there are two functions and neither is better than the other, then in some circumstances [1] a tie-breaker rule is applied that might still determine that one is better than the other. If rule 3 could not determine which one of two viable functions is better, but only one is a non-template, the non-template is better; if both are template specializations, but one is generated from a template that's more specialized than the other, that function is better. After the tie-breaker, if there's a single best viable function (better than all the others), that function wins overload resolution. If the ambiguity remains, overload resolution fails and the call is ambiguous.

It's important to remember that step 4 comes after step 3; the "genericness" or "templateness" is exclusively a tie-breaker rule.

Let's go over all your examples in your first code block.

(1) Deduction succeeds on the first and third overloads; Hrg cannot be deduced for the second. The candidates are therefore the first and third (rule 1). Both are viable (rule 2). The first overload would bind i to int& while the third would bind i to const int&. Binding to the less cv-qualified reference is preferred (rule 3). (Barry has the specific quote from the standard.) The first (generic) overload wins.

(2) Hrg cannot be deduced for the third overload, so it is not a candidate (rule 1). The first and second are candidates and are viable (rule 2). The first and second overloads both match exactly with no conversions required and are indistinguishable by rule 3. The second wins because it's more specialized (rule 4).

(5) Deduction of Hrg fails for the second overload, so it is not a candidate, while the first and third are (rule 1). Note that for the first overload, A is deduced as const int, producing an identical signature to the third overload. They are both viable (rule 2) and are indistinguishable by the end of rule 3. The third overload wins because it's more specialized (rule 4).

(6) Deduction of Hrg fails for the third overload, so it is not a candidate, while the first and second are (rule 1). The second overload is not viable (rule 2) since int& cannot bind to ri, which is const. The first overload, the generic one, is the only viable function, so it wins.

I leave the overload resolution in the second code block as an exercise for the reader.

[1] As T.C. points out in comments, there is a subtlety here. The tie-breaker rule only applies when, for a given pair of functions, the implicit conversion sequences required to initialize the parameters from the arguments are equally ranked for every pair of corresponding parameters. If the first function has a better implicit conversion sequence for one parameter and the second has a better implicit conversion sequence for a different parameter, the tie-breaker rule isn't applied, and the ambiguity remains. This case doesn't occur in the example in the question, though.

Answer 2

Going in order through the four distinct test cases. In all cases, the conversion sequences are all the same - there are no conversions required, so we would have to move on to the next stage of overload resolution.

foo(wt, i); // 1) generic

There are two potential overloads here. The everything and the Hrg<true>

template <class Hrm, class A> void foo(Hrm& h, A& a);
template <template <bool> class Hrg> void foo(Hrg<true>& h, const int& a);

In [over.ics.rank], we have (thanks @dyp):

Standard conversion sequence S1 is a better conversion sequence than standard conversion sequence S2 if...
— S1 and S2 are reference bindings (8.5.3), and the types to which the references refer are the same type except for top-level cv-qualifiers, and the type to which the reference initialized by S2 refers is more cv-qualified than the type to which the reference initialized by S1 refers..

const int is more cv-qualified than int, so the int overload is preferred - which would be the generic one.

foo(wf, i);  // 2) specialized int

Here the two overloads are

template <class Hrm, class A> void foo(Hrm& h, A& a)
template <template <bool> class Hrg> void foo(Hrg<false>& h, int& a)

Both conversion sequences are identical here, so nothing in that section can distinguish one from the other. So we move onto [over.match.best]:

Given these definitions, a viable function F1 is defined to be a better function than another viable function F2 if for all arguments i, ICSi(F1) is not a worse conversion sequence than ICSi(F2), and then
— ...
— F1 and F2 are function template specializations, and the function template for F1 is more specialized than the template for F2 according to the partial ordering rules described in 14.5.6.2.

The rules concerning "more specialized than" are complicated but basically mean that the second overload is viable for a strict subset of the types for which the first is viable for, hence it is preferred.

foo(wt, ri); // 5) specialized const-int

Here, we have the same two overloads as in the first case:

template <class Hrm, class A> void foo(Hrm& h, A& a);
template <template <bool> class Hrg> void foo(Hrg<true>& h, const int& a);

The conversion sequences are both identical, but the second overload is more specialized than the first, so the specialized overload is preferred for the same reasons as it was in (2).

foo(wf, ri); // 6) generic

Here the "generic" overload is the only viable overload.

UPDATE The new tests you added are more straightforward than the previous four. Given the two foo overloads:

template <class Hrg> void foo(Hrg& h, int& a);
template <class Hrg> void foo(Hrg& h, const int& a);

When called with ri, only the second overload is viable. But when called with i, the first overload is preferred for the same reasons as (1) above - int is less cv-qualified than const int.