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.