Template Function Selection Based on Nested Type

Question

The following code works correctly on VS2015:

struct Foo
{
   using Bar = int;
   auto operator()() { return "Foo!";  }
};

template <typename Callable, typename CodeType> // <<< CodeType is a template param
void funky(CodeType code, Callable func)
{
   cout << "Generic: " << code << ", " << func() << endl;
}

template <typename HasBar>
void funky(typename HasBar::Bar code, HasBar func) // <<< The code type is a nested type
{
   cout << "Has Bar: " << code << ", " << func() << endl;
}

int main()
{
   Foo foo;
   funky(3, []() { return "Lambda!"; });
   funky(3, foo);
   return 0;
}

Printing:

Generic: 3, Lambda!
Has Bar: 3, Foo!

However, it does not compile on gcc/clang, complaining:

 In function 'int main()':
27:16: error: call of overloaded 'funky(int, Foo&)' is ambiguous
27:16: note: candidates are:
12:6: note: void funky(CodeType, Callable) [with Callable = Foo; CodeType = int]
18:6: note: void funky(typename HasBar::Bar, HasBar) [with HasBar = Foo; typename HasBar::Bar = int]

The ambiguity is resolved correctly by VS2015 (which does not mean it is the conforming thing to do).

How can I get this to compile and run correctly on Clang/gcc?
I thought of using std::enable_if but couldn't get it to do what I want (I most likely used it incorrectly). If this is the way to go, how should it be used to solve this ambiguity?

UPDATE:
Adding typename HasBar::Bar to the template params gets gcc/Clang to build and run the code correctly:

template <typename HasBar, typename HasBar::Bar>
void funky(typename HasBar::Bar code, HasBar func) // <<< The code type is a nested type
{
   cout << "Has Bar: " << code << ", " << func() << endl;
}

This seems to tell the compiler that there is a second, non-type template parameter value (unused in the function code) that is of type typename HasBar::Bar. If typename HasBar::Bar does not exist, SFINAE will remove this function from the overload set and the generic form will be chosen.

However, when it does exist, I do not know why this function will take precedence over the first. I guess because it is more specialized - although the specialization isn't used in the code itself. However, in this case, it was already more specialized even before the new param!

However, in this case VS2015 always chooses the generic form giving the wrong answer!

Is there some syntax (and/or workaround) that will work in all cases?

How did you use `enable_if`? Did you use it to enable the second overload, or *disable* the first overload? — Martin Bonner supports Monica, May 17 '16 at 12:48
Actually I tried various things but I am not sure they were correct. How *should* it be used here? — Adi Shavit, May 17 '16 at 12:50
I would have expected the second function to be more specialized and hence be the prefered overload when applicable (So VS would be right). Can someone comment on that? — MikeMB, May 17 '16 at 13:07

Adi Shavit · Answer 1 · 2016-05-17T17:05:27.403

4

13 minutes later... answering myself. [NOT] Solved!

Adding typename HasBar::Bar to the template params did the trick:

template <typename HasBar, typename HasBar::Bar>
void funky(typename HasBar::Bar code, HasBar func) // <<< The code type is a nested type
{
   cout << "Has Bar: " << code << ", " << func() << endl;
}

This seems to tell the compiler that there is a second, non-type template parameter value (unused in the function code) that is of type typename HasBar::Bar. If typename HasBar::Bar does not exist, SFINAE will remove this function from the overload set and the generic form will be chosen.

However, when it does exist, I do not know why this function will take precedence over the first. I guess because it is more specialized - although the specialization isn't used in the code itself.
However, in this case, it was already more specialized even before the new param!

edited May 17 '16 at 17:05

answered May 17 '16 at 12:56

Adi Shavit

16,743
5
67
137

Can you (or someone else) please also explain why it works like this? Standard citations would be welcome. – Tamás Szelei May 17 '16 at 13:05
@TamásSzelei: It uses SFINAE to remove the posted function from the overload set, if HasBar::Bar isn't valid.(as in "if `HasBar` doesn't have a nested type `Bar") – MikeMB May 17 '16 at 13:13
Turns out this, indeed, fixes gcc/clang but breaks VS2015 - causing it to give a wrong answer :-( – Adi Shavit May 17 '16 at 14:04

Richard Hodges · Answer 2 · 2016-05-17T14:03:57.870

Answering the question as to why...

An easy way to understand this is to manually do what the compiler would do.

Given:

// first form
template <typename Callable, typename CodeType>
void funky(CodeType code, Callable func);

// second form
template <typename HasBar, typename HasBar::Bar>
void funky(typename HasBar::Bar code, HasBar func);

substituting lambda, int:

first form: template<lambda, int> void funky(int, lambda) - fine, required two substitutions

second form: template<lambda, lambda::Bar> <-- SFNAE error here because lambda does not have a Bar subordinate type.

Therefore the first form is chosen (being the only legal one)

substituting HasBar, HasBar::Bar :

first form: template<HasBar, HasBar::Bar> void funky(HasBar::Bar, HasBar) - fine, required two substitutions

second form: template<HasBar, HasBar::Bar> <-- Fine, required zero substitutions.

Both are valid, but the second form requires fewer template substitutions. It's therefore more specialised and a better match.

in response to questions:

ok... lets think about one way we could implement the template match algorithm in a compiler...

At the point of this call funky(3, []() { return "Lambda!"; });:

compute the "ambiguity" of each template...
let's measure ambiguity as the total number of combinations of 
known types that would make a match.
This would be a set of possible substitutions. The set is limited
to the product of the total number of types known for each template
argument... for now let's just consider the ones mentioned in the program and ignore all others (like float, ostream etc.)

for the first form: template<Callable, CodeType>
Callable can be: Foo, int, some_lambda
When Callable is Foo, CodeType can be: Foo, int, some_lambda
When Callable is int, CodeType can be: Foo, int, some_lambda
... etc
for a total ambiguity score of 3 * 3 = 9

now the second form: template<HasBar, HasBar::Bar>
HasBar can be: Foo, int, some_lambda
When HasBar is Foo, HasBar::Bar can only be: Foo::Bar, because Foo::int and Foo::some_lambda are not legal syntax = 1
When HasBar is int, HasBar::Bar can't be anything because int::something is illegal, so score = 0
When HasBar is some_lambda, HasBar::Bar can't be anything because lambda::something is illegal, so score = 0
... for a total ambiguity score of 1 + 0 + 0 = 1

... ok, now we know how ambiguous each template is, let's see if the arguments can be substituted into one of the options for each...
... if the arguments can't be legally substituted, dump the template as an option ...
... if we have any templates left in our 'legal' set, choose the one with the least 'ambiguity'
... if there is more than one legal templates with the minimum ambiguity, error (as you saw in the beginning)
... otherwise, we have a match - use this template function.

Two things: (1) Does this mean that the selection doesn't actually take into account the actual params for the overload set, because that already contained `typename HasBar::Bar`? (2) Can you detail more about what you mean by substitution? Why is the second form in the second case 0 substitutions? Can you explicitely specify the substitutions in the answer? — Adi Shavit, May 17 '16 at 13:34
@AdiShavit the types tested against the template arguments are deduced from the types of the arguments at the call site. In the second form, HasBar is a template argument (i.e must be matched) but once that has done, `HasBar::Bar` is no longer just a template type, it's a special template type because it's dependent upon `HasBar` (which has already been deduced). It's therefore 'not as generic' as simply `CodeType`, which could be anything. Confused? I'm probably making it worse... — Richard Hodges, May 17 '16 at 13:43
@AdiShavit the simplistic method I use is to imagine how much "work" the compiler must do to work out whether the arguments match the template types. If there's "doubt/ambiguity" about a match, it's going to require more "work" to figure out the type... More "work" means less specialised. — Richard Hodges, May 17 '16 at 13:46
I guess that does make sense. Could I ask that you extend your answer to specify the substitutions? It would certainly improve the answer and help see what actually gets substituted with what. Also, I am not clear why the original version was not considered more specialized to begin with. — Adi Shavit, May 17 '16 at 13:48
@AdiShavit added a narrative which (more or less) models the process your compiler goes through. — Richard Hodges, May 17 '16 at 14:04

score 2 · Accepted Answer · edited May 23 '17 at 12:07

I would do it with SFINAE(https://en.wikipedia.org/wiki/Substitution_failure_is_not_an_error) trick in a way like this:

#include <iostream>
#include <type_traits>

using namespace std;

struct Foo
{
   using Bar = int;
   auto operator()() { return "Foo!";  }
};

template< typename ... Ts >
using void_t = void;

template< typename T, typename = void >
struct has_type_Bar : false_type{};

template< typename T >
struct has_type_Bar< T, void_t<typename T::Bar> > : true_type {};

template <typename Callable, typename CodeType>
void funky_impl(CodeType code, Callable func, false_type)
{
   cout << "Generic: " << code << ", " << func() << endl;
}

template <typename Callable, typename CodeType>
void funky_impl(CodeType code, Callable func, true_type)
{
   cout << "Has Bar: " << code << ", " << func() << endl;
}

template <typename Callable, typename CodeType>
void funky(CodeType code, Callable func)
{
    return funky_impl( code, func, has_type_Bar<CodeType>{} );
}

int main()
{
   Foo foo;
   funky(3, []() { return "Lambda!"; });
   funky(3, foo);
   return 0;
}

For VS2015, I guess it has a bug with two-phase name lookup(What exactly is "broken" with Microsoft Visual C++'s two-phase template instantiation?).

This works, but is there a less verbose, more generic way to do it? Perhaps with more `std` utils? — Adi Shavit, May 17 '16 at 14:17
I ended up using this since it is the only thing that worked consistently, including on VS2015. — Adi Shavit, May 18 '16 at 11:46

Template Function Selection Based on Nested Type

3 Answers3