This Case of Template Function Overloading Eludes My Understanding

This case of template function overloading eludes my understanding

Once we get our candidate functions set (both bars), and then whittle it down to the viable functions (still both bars) we have to determine the best viable function. If there is more than one, we get an ambiguity error. The steps we take to determine the best one are laid out in [over.match.best]:

[A] viable function F1 is defined to be a better function than another viable function F2 if for all arguments i, ICS_i(F1) is not a worse conversion sequence than ICS_i(F2), and then

— for some argument j, ICS_j(F1) is a better conversion sequence than ICS_j(F2), or, if not that,

Both functions take an argument of type int, so both conversion sequences are identical. We continue.

— the context is an initialization by user-defined conversion [...]

Does not apply.

— the context is an initialization by conversion function for direct reference binding (13.3.1.6) of a reference to function type, [...]

Does not apply.

— F1 is not a function template specialization and F2 is a function template specialization, or, if not that,

Both bar<int>s are function template specializations. So we move onto the very last bullet point to to determine the best viable function.

— 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 partial ordering rules basically boil down to us synthesizing new unique types for the arguments of both bar overloads and performing template deduction on the other overload.

Consider the "b" overload first. Synthesize a type typename identity<Unique1>::type and attempt to perform template deduction against T. That succeeds. Simplest cast of template deduction there is.

Next, consider the "a" overload. Synthesize a type Unique2 and attempt to perform template deduction against typename identity<T>::type. This fails! This is a non-deduced context - no deduction can succeed.

Since template type deduction only succeeds in a single direction, the bar(typename identity<T>::type) overload is considered more specialized, and is chosen as the best viable candidate.

bogdan presents another interesting case for looking at partial ordering. Consider instead comparing:

template <typename T> void bar(T, T); // "c"
template <typename T> void bar(T, typename identity<T>::type ); // "d"

bar(5,5);
bar<int>(5, 5);

Again, both candidates are viable (this time even without explicitly specifying T) so we look at the partial ordering rule.

For the "c" overload, we synthesize arguments of type UniqueC, UniqueC and attempt to perform deduction against T, typename identity<T>::type. This succeeds (with T == UniqueC). So "c" is at least as specialized as "d".

For the "d" overload, we synthesize arguments of type UniqueD, typename identity<UniqueD>::type and attempt to perform deduction against T, T. This fails! The arguments are of different types! So "d" is not at least as specialized as "c".

Thus, the "c" overload is called.

Template partial ordering - why does partial deduction succeed here

As discussed in the comments, I believe there are several aspects of the function template partial ordering algorithm that are unclear or not specified at all in the standard, and this shows in your example.

To make things even more interesting, MSVC (I tested 12 and 14) rejects the call as ambiguous. I don't think there's anything in the standard to conclusively prove which compiler is right, but I think I might have a clue about where the difference comes from; there's a note about that below.

Your question (and this one) challenged me to do some more investigation into how things work. I decided to write this answer not because I consider it authoritative, but rather to organize the information I have found in one place (it wouldn't fit in comments). I hope it will be useful.

First, the proposed resolution for issue 1391. We discussed it extensively in comments and chat. I think that, while it does provide some clarification, it also introduces some issues. It changes [14.8.2.4p4] to (new text in bold):

Each type nominated above from the parameter template and the
corresponding type from the argument template are used as the types of
P and A. If a particular P contains no template-parameters that
participate in template argument deduction, that P is not used to
determine the ordering.

Not a good idea in my opinion, for several reasons:

If P is non-dependent, it doesn't contain any template parameters at all, so it doesn't contain any that participate in argument deduction either, which would make the bold statement apply to it. However, that would make template<class T> f(T, int) and template<class T, class U> f(T, U) unordered, which doesn't make sense. This is arguably a matter of interpretation of the wording, but it could cause confusion.
It messes with the notion of used to determine the ordering, which affects [14.8.2.4p11]. This makes template<class T> void f(T) and template<class T> void f(typename A<T>::a) unordered (deduction succeeds from first to second, because T is not used in a type used for partial ordering according to the new rule, so it can remain without a value). Currently, all compilers I've tested report the second as more specialized.

It would make #2 more specialized than #1 in the following example:

#include <iostream>

template<class T> struct A { using a = T; };

struct D { };
template<class T> struct B { B() = default; B(D) { } };
template<class T> struct C { C() = default; C(D) { } };

template<class T> void f(T, B<T>) { std::cout << "#1\n"; } // #1
template<class T> void f(T, C<typename A<T>::a>) { std::cout << "#2\n"; } // #2

int main()
{
   f<int>(1, D());
}

(#2's second parameter is not used for partial ordering, so deduction succeeds from #1 to #2 but not the other way around). Currently, the call is ambiguous, and should arguably remain so.

After looking at Clang's implementation of the partial ordering algorithm, here's how I think the standard text could be changed to reflect what actually happens.

Leave [p4] as it is and add the following between [p8] and [p9]:

For a P / A pair:

If P is non-dependent, deduction is considered successful if and only if P and A are the same type.

Substitution of deduced template parameters into the non-deduced contexts appearing in P is not performed and does not affect the outcome of the deduction process.

If template argument values are successfully deduced for all template parameters of P except the ones that appear only in non-deduced contexts, then deduction is considered successful (even if some parameters used in P remain without a value at the end of the deduction process for that particular P / A pair).

Notes:

About the second bullet point: [14.8.2.5p1] talks about finding template argument values that will make P, after substitution of the deduced values (call it the deduced A), compatible with A. This could cause confusion about what actually happens during partial ordering; there's no substitution going on.
MSVC doesn't seem to implement the third bullet point in some cases. See the next section for details.
The second and third bullet points are intented to also cover cases where P has forms like A<T, typename U::b>, which aren't covered by the wording in issue 1391.

Change the current [p10] to:

Function template F is at least as specialized as function template
G if and only if:

for each pair of types used to determine the ordering, the type from F is at least as specialized as the type from G, and,

when performing deduction using the transformed F as the argument template and G as the parameter template, after deduction is done
for all pairs of types, all template parameters used in the types from
G that are used to determine the ordering have values, and those
values are consistent across all pairs of types.

F is more specialized than G if F is at least as specialized
as G and G is not at least as specialized as F.

Make the entire current [p11] a note.

(The note added by the resolution of 1391 to [14.8.2.5p4] needs to be adjusted as well - it's fine for [14.8.2.1], but not for [14.8.2.4].)

For MSVC, in some cases, it looks like all template parameters in P need to receive values during deduction for that specific P / A pair in order for deduction to succeed from A to P. I think this could be what causes implementation divergence in your example and others, but I've seen at least one case where the above doesn't seem to apply, so I'm not sure what to believe.

Another example where the statement above does seem to apply: changing template<typename T> void bar(T, T) to template<typename T, typename U> void bar(T, U) in your example swaps results around: the call is ambiguous in Clang and GCC, but resolves to b in MSVC.

One example where it doesn't:

#include <iostream>

template<class T> struct A { using a = T; };
template<class, class> struct B { };

template<class T, class U> void f(B<U, T>) { std::cout << "#1\n"; }
template<class T, class U> void f(B<U, typename A<T>::a>) { std::cout << "#2\n"; }

int main()
{
   f<int>(B<int, int>());
}

This selects #2 in Clang and GCC, as expected, but MSVC rejects the call as ambiguous; no idea why.

The partial ordering algorithm as described in the standard speaks of synthesizing a unique type, value, or class template in order to generate the arguments. Clang manages that by... not synthesizing anything. It just uses the original forms of the dependent types (as declared) and matches them both ways. This makes sense, as substituting the synthesized types doesn't add any new information. It can't change the forms of the A types, since there's generally no way to tell what concrete types the substituted forms could resolve to. The synthesized types are unknown, which makes them pretty similar to template parameters.

When encountering a P that is a non-deduced context, Clang's template argument deduction algorithm simply skips it, by returning "success" for that particular step. This happens not only during partial ordering, but for all types of deductions, and not just at the top level in a function parameter list, but recursively whenever a non-deduced context is encountered in the form of a compound type. For some reason, I found that surprising the first time I saw it. Thinking about it, it does, of course, make sense, and is according to the standard ([...] does not participate in type deduction [...] in [14.8.2.5p4]).

This is consistent with Richard Corden's comments to his answer, but I had to actually see the compiler code to understand all the implications (not a fault of his answer, but rather of my own - programmer thinking in code and all that).

I've included some more information about Clang's implementation in this answer.

What else do I need to use variadic template inheritance to create lambda overloads?

You didn't actually recurse.

// primary template; not defined.
template <class... F> struct overload;

// recursive case; inherit from the first and overload<rest...>
template<class F1, class... F>
struct overload<F1, F...> : F1, overload<F...> {
    overload(F1 f1, F... f) : F1(f1), overload<F...>(f...) {}

    // bring all operator()s from the bases into the derived class
    using F1::operator();
    using overload<F...>::operator();
};      

// Base case of recursion
template <class F>
struct overload<F> : F {
    overload(F f) : F(f) {}
    using F::operator();
};

Template operator overloading implementation outside class header

The answer to your actual question is no for reasons explained in @AndyProwl link, and even if you would have included the operator definitions inside the header util.h the answer would still be no.

The reason is that these operators are actually non-template functions that are injected into the enclosing scope of the class they are defined in as a side-effect of the class template instantiation. In other words, this class template

template<class T>
struct Rect {
  T x, y, w, h;

  friend bool operator ==(const Rect<T> &a, const Rect<T> &b);
  friend bool operator !=(const Rect<T> &a, const Rect<T> &b);
};

generates the following two non-template functions for every type T

bool operator ==(const Rect<T> &a, const Rect<T> &b);
bool operator !=(const Rect<T> &a, const Rect<T> &b);

If you then also define function templates

template<class T>
bool operator ==(const Rect<T> &a, const Rect<T> &b)
{
    return (a.x == b.x && a.y == b.y && a.w == b.w && a.h == b.h);
}

template<class T>
bool operator !=(const Rect<T> &a, const Rect<T> &b)
{
    return !(a == b);
}

and call them in your code, then name lookup and argument deduction proceed without difficulty, but function overload resolution will end in a tie which is broken by the non-template in-class friend functions. But when these are not defined, your program will fail to link.

There are two escapes: define the operators in-class (as you already provided) or (again as alluded to by @AndyProwl) to befriend the general operator templates inside the class with this peculair syntax

// forward declarations
template<typename T> struct Rect;
template<typename T> bool operator==(const Rect<T>&, const Rect<T>&);
template<typename T> bool operator!=(const Rect<T>&, const Rect<T>&);

template<class T>
struct Rect {
  T x, y, w, h;

  // friend of operator templates
  friend bool operator == <>(const Rect<T> &a, const Rect<T> &b);
  friend bool operator != <>(const Rect<T> &a, const Rect<T> &b);
};

// definitions of operator templates follow

Note that befriending templates is a tricky business, as explained in this old column by Herb Sutter.

This Case of Template Function Overloading Eludes My Understanding