Overload Resolution with Std::Function

std::function fails to distinguish overloaded functions

It's obvious to us which function you intend to be chosen, but the compiler has to follow the rules of C++ not use clever leaps of logic (or even not so clever ones, as in simple cases like this!)

The relevant constructor of std::function is:

template<class F> function(F f);

which is a template that accepts any type.

The C++14 standard does constrain the template (since LWG DR 2132) so that it:

shall not participate in overload resolution unless f is Callable (20.9.12.2) for argument types ArgTypes... and return type R.

which means that the compiler will only allow the constructor to be called when Functor is compatible with the call signature of the std::function (which is void(int, int) in your example). In theory that should mean that void add(A, A) is not a viable argument and so "obviously" you intended to use void add(int, int).

However, the compiler can't test the "f is Callable for argument types ..." constraint until it knows the type of f, which means it needs to have already disambiguated between void add(int, int) and void add(A, A) before it can apply the constraint that would allow it to reject one of those functions!

So there's a chicken and egg situation, which unfortunately means that you need to help the compiler out by specifying exactly which overload of add you want to use, and then the compiler can apply the constraint and (rather redundantly) decide that it is an acceptable argument for the constructor.

It is conceivable that we could change C++ so that in cases like this all the overloaded functions are tested against the constraint (so we don't need to know which one to test before testing it) and if only one is viable then use that one, but that's not how C++ works.

Why doesn't std::function participate in overload resolution?

This doesn't really have anything to do with "phases of translation". It's purely about the constructors of std::function.

See, std::function<R(Args)> doesn't require that the given function is exactly of the type R(Args). In particular, it doesn't require that it is given a function pointer. It can take any callable type (member function pointer, some object that has an overload of operator()) so long as it is invokable as if it took Args parameters and returns something convertible to R (or if R is void, it can return anything).

To do that, the appropriate constructor of std::function must be a template: template<typename F> function(F f);. That is, it can take any function type (subject to the above restrictions).

The expression baz represents an overload set. If you use that expression to call the overload set, that's fine. If you use that expression as a parameter to a function that takes a specific function pointer, C++ can whittle down the overload set to a single call, thus making it fine.

However, once a function is a template, and you're using template argument deduction to figure out what that parameter is, C++ no longer has the ability to determine what the correct overload in the overload set is. So you must specify it directly.

Overload resolution with std::function

In C++11...

Let's take a look at the specification of the constructor template of std::function (which takes any Callable): [func.wrap.func.con]/7-10

template<class F> function(F f);
template <class F, class A> function(allocator_arg_t, const A& a, F f);
7 Requires: F shall be CopyConstructible. f shall be Callable (20.10.11.2) for argument types ArgTypes and return type
R. The copy constructor and destructor of A shall not throw
exceptions.

8 Postconditions: !*this if any of the following hold:

f is a NULL function pointer.

f is a NULL pointer to member.

F is an instance of the function class template, and !f

9 Otherwise, *this targets a copy of f initialized with std::move(f). [left out a note here]

10 Throws: shall not throw exceptions when f is a function pointer or a reference_wrapper<T> for some T. Otherwise, may throw
bad_alloc or any exception thrown by F’s copy or move constructor.

Now, constructing, or attempting to construct (for overload resolution) a std::function<void(int)> from a [](){} (i.e. with signature void(void)) violates the requirements of std::function<void(int)>'s constructor.

[res.on.required]/1

Violation of the preconditions specified in a function’s Requires: paragraph results in undefined behavior unless the function’s Throws: paragraph specifies throwing an exception when the precondition is violated.

So, AFAIK, even the result of the overload resolution is undefined. Therefore, both versions of g++/libstdc++ are complying in this aspect.

In C++14, this has been changed, see LWG 2132. Now, the converting constructor template of std::function is required to SFINAE-reject incompatible Callables (more about SFINAE in the next chapter):

template<class F> function(F f);
template <class F, class A> function(allocator_arg_t, const A& a, F f);
7 Requires: F shall be CopyConstructible.

8 Remarks: These constructors shall not participate in overload
resolution unless f is Callable (20.9.11.2) for argument types
ArgTypes... and return type R.

[...]

The "shall not participate in overload resolution" corresponds to rejection via SFINAE. The net effect is that if you have an overload set of functions foo,

void foo(std::function<void(double)>);
void foo(std::function<void(char const*)>);

and a call-expression such as

foo([](std::string){}) // (C)

then the second overload of foo is chosen unambiguously: Since std::function<F> defines F as its interface to the outside, the F defines which argument types are passed into std::function. Then, the wrapped function object has to be called with those arguments (argument types). If a double is passed into std::function, it cannot be passed on to a function taking a std::string, because there's no conversion double -> std::string.
For the first overload of foo, the argument [](std::string){} is therefore not considered Callable for std::function<void(double)>. The constructor template is deactivated, hence there's no viable conversion from [](std::string){} to std::function<void(double)>. This first overload is removed from the overload set for resolving the call (C), leaving only the second overload.

Note that there's been a slight change to the wording above, due to LWG 2420: There's an exception that if the return type R of a std::function<R(ArgTypes...)> is void, then any return type is accepted (and discarded) for the Callable in the constructor template mentioned above. For example, both []() -> void {} and []() -> bool {} are Callable for std::function<void()>. The following situation therefore produces an ambiguity:

void foo(std::function<void()>);
void foo(std::function<bool()>);

foo([]() -> bool {}); // ambiguous

The overload resolution rules don't try to rank among different user-defined conversions, and hence both overloads of foo are viable (first of all) and neither is better.

How can SFINAE help here?

Note when a SFINAE-check fails, the program isn't ill-formed, but the function isn't viable for overload resolution. For example:

#include <type_traits>
#include <iostream>

template<class T>
auto foo(T) -> typename std::enable_if< std::is_integral<T>::value >::type
{  std::cout << "foo 1\n";  }

template<class T>
auto foo(T) -> typename std::enable_if< not std::is_integral<T>::value >::type
{  std::cout << "foo 2\n";  }

int main()
{
    foo(42);
    foo(42.);
}

Similarly, a conversion can be made non-viable by using SFINAE on the converting constructor:

#include <type_traits>
#include <iostream>

struct foo
{
    template<class T, class =
             typename std::enable_if< std::is_integral<T>::value >::type >
    foo(T)
    {  std::cout << "foo(T)\n";  }
};

struct bar
{
    template<class T, class =
             typename std::enable_if< not std::is_integral<T>::value >::type >
    bar(T)
    {  std::cout << "bar(T)\n";  }
};

struct kitty
{
    kitty(foo) {}
    kitty(bar) {}
};

int main()
{
    kitty cat(42);
    kitty tac(42.);
}

Overloading on std::function...

Is this supposed to happen or just a deficiency in the compilers?

This is supposed to happen. std::function has a constructor template that can take an argument of any type. The compiler can't know until after a constructor template is selected and instantiated that it's going to run into errors, and it has to be able to select an overload of your function before it can do that.

The most straightforward fix is to use a cast or to explicitly construct a std::function object of the correct type:

func(std::function<void()>([](){}));
func(std::function<void(int)>([](int){}));

If you have a compiler that supports the captureless-lambda-to-function-pointer conversion and your lambda doesn't capture anything, you can use raw function pointers:

void func(void (*param)()) { }
void func(void (*param)(int)) { }

(It looks like you are using Visual C++ 2010, which does not support this conversion. The conversion was not added to the specification until just before Visual Studio 2010 shipped, too late to add it in.)

To explain the problem in a bit more detail, consider the following:

template <typename T>
struct function {

    template <typename U>
    function(U f) { }
};

This is basically what the std::function constructor in question looks like: You can call it with any argument, even if the argument doesn't make sense and would cause an error somewhere else. For example, function<int()> f(42); would invoke this constructor template with U = int.

In your specific example, the compiler finds two candidate functions during overload resolution:

void func(std::function<void(void)>)
void func(std::function<void(int)>)

The argument type, some unutterable lambda type name that we will refer to as F, doesn't match either of these exactly, so the compiler starts looking at what conversions it can do to F to try and make it match one of these candidate functions. When looking for conversions, it finds the aforementioned constructor template.

All the compiler sees at this point is that it can call either function because

it can convert F to std::function<void(void)> using its converting constructor with U = F and
it can convert F to std::function<void(int)> using its converting constructor with U = F.

In your example it is obvious that only one of these will succeed without error, but in the general case that isn't true. The compiler can't do anything further. It has to report the ambiguity and fail. It can't pick one because both conversions are equally good and neither overload is better than the other.

Using concepts for function overload resolution (instead of SFINAE)

Yes concepts are designed for this purpose. If a sent parameter doesn't meet the required concept argument the function would not be considered in the overload resolution list, thus avoiding ambiguity.

Moreover, if a sent parameter meets several functions, the more specific one would be selected.

Simple example:

void print(auto t) {
    std::cout << t << std::endl;
}

void print(std::integral auto i) {
    std::cout << "integral: " << i << std::endl;
}

Above print functions are a valid overloading that can live together.

If we send a non integral type it will pick the first
If we send an integral type it will prefer the second

e.g., calling the functions:

print("hello"); // calls print(auto)
print(7);       // calls print(std::integral auto)

No ambiguity -- the two functions can perfectly live together, side-by-side.

No need for any SFINAE code, such as enable_if -- it is applied already (hidden very nicely).

Picking between two concepts

The example above presents how the compiler prefers constrained type (std::integral auto) over an unconstrained type (just auto). But the rules also apply to two competing concepts. The compiler should pick the more specific one, if one is more specific. Of course if both concepts are met and none of them is more specific this will result with ambiguity.

Well, what makes a concept be more specific? if it is based on the other one¹.

The generic concept - GenericTwople:

template<class P>
concept GenericTwople = requires(P p) {
    requires std::tuple_size<P>::value == 2;
    std::get<0>(p);
    std::get<1>(p);
};

The more specific concept - Twople:

class Any;

template<class Me, class TestAgainst>
concept type_matches =
    std::same_as<TestAgainst, Any> ||
    std::same_as<Me, TestAgainst>  ||
    std::derived_from<Me, TestAgainst>;

template<class P, class First, class Second>
concept Twople =
    GenericTwople<P> && // <= note this line
    type_matches<std::tuple_element_t<0, P>, First> &&
    type_matches<std::tuple_element_t<1, P>, Second>;

Note that Twople is required to meet GenericTwople requirements, thus it is more specific.

If you replace in our Twople the line:

    GenericTwople<P> && // <= note this line

with the actual requirements that this line brings, Twople would still have the same requirements but it will no longer be more specific than GenericTwople. This, along with code reuse of course, is why we prefer to define Twople based on GenericTwople.

Now we can play with all sort of overloads:

void print(auto t) {
    cout << t << endl;
}

void print(const GenericTwople auto& p) {
    cout << "GenericTwople: " << std::get<0>(p) << ", " << std::get<1>(p) << endl;
}

void print(const Twople<int, int> auto& p) {
    cout << "{int, int}: " << std::get<0>(p) << ", " << std::get<1>(p) << endl;
}

And call it with:

print(std::tuple{1, 2});        // goes to print(Twople<int, int>)
print(std::tuple{1, "two"});    // goes to print(GenericTwople)
print(std::pair{"three", 4});   // goes to print(GenericTwople)
print(std::array{5, 6});        // goes to print(Twople<int, int>)
print("hello");                 // goes to print(auto)

We can go further, as the Twople concept presented above works also with polymorphism:

struct A{
    virtual ~A() = default;
    virtual std::ostream& print(std::ostream& out = std::cout) const {
        return out << "A";
    }
    friend std::ostream& operator<<(std::ostream& out, const A& a) {
        return a.print(out);
    }
};

struct B: A{
    std::ostream& print(std::ostream& out = std::cout) const override {
        return out << "B";
    }
};

add the following overload:

void print(const Twople<A, A> auto& p) {
    cout << "{A, A}: " << std::get<0>(p) << ", " << std::get<1>(p) << endl;
}

and call it (while all the other overloads are still present) with:

    print(std::pair{B{}, A{}}); // calls the specific print(Twople<A, A>)

Code: https://godbolt.org/z/3-O1Gz

Unfortunately C++20 doesn't allow concept specialization, otherwise we would go even further, with:

template<class P>
concept Twople<P, Any, Any> = GenericTwople<P>;

Which could add a nice possible answer to this SO question, however concept specialization is not allowed.

_{¹ The actual rules for Partial Ordering of Constraints are more complicated, see: cppreference / C++20 spec.}

How does overload resolution work when an argument is an overloaded function?

Let's take the most interesting case,

bar("abc", foo);

The primary question to figure out is, which overload of bar to use. As always, we first get a set of overloads by name lookup, then do template type deduction for each function template in the overload set, then do overload resolution.

The really interesting part here is the template type deduction for the declaration

template<class T> void bar(T* x, void (*f)(T*)) {}

The Standard has this to say in 14.8.2.1/6:

When P is a function type, pointer to function type, or pointer to member function type:
If the argument is an overload set containing one or more function templates, the parameter is treated as a non-deduced context.
If the argument is an overload set (not containing function templates), trial argument deduction is attempted using each of the members of the set. If deduction succeeds for only one of the overload set members, that member is used as the argument value for the deduction. If deduction succeeds for more than one member of the overload set the parameter is treated as a non-deduced context.

(P has already been defined as the function template's function parameter type including template parameters, so here P is void (*)(T*).)

So since foo is an overload set containing a function template, foo and void (*f)(T*) don't play a role in template type deduction. That leaves parameter T* x and argument "abc" with type const char[4]. T* not being a reference, the array type decays to a pointer type const char* and we find that T is const char.

Now we have overload resolution with these candidates:

void bar(int x, void (*f)(int)) {}                             // (1)
void bar(double x, void (*f)(double)) {}                       // (2)
void bar(std::string x, void (*f)(std::string)) {}             // (3)
void bar<const char>(const char* x, void (*f)(const char*)) {} // (4)
void bar(A x, void (*f2)(double)) {}                           // (5)

Time to find out which of these are viable functions. (1), (2), and (5) are not viable because there is no conversion from const char[4] to int, double, or A. For (3) and (4) we need to figure out if foo is a valid second argument. In Standard section 13.4/1-6:

A use of an overloaded function name without arguments is resolved in certain contexts to a function, a pointer to function or a pointer to member function for a specific function from the overload set. A function template name is considered to name a set of overloaded functions in such contexts. The function selected is the one whose type is identical to the function type of the target type required in the context. The target can be
...
a parameter of a function (5.2.2),
...
... If the name is a function template, template argument deduction is done (14.8.2.2), and if the argument deduction succeeds, the resulting template argument list is used to generate a single function template specialization, which is added to the set of overloaded functions considered. ...
[Note: If f() and g() are both overloaded functions, the cross product of possibilities must be considered to resolve f(&g), or the equivalent expression f(g). - end note]

For overload (3) of bar, we first attempt type deduction for

template<class T> void foo(T* ) {}

with target type void (*)(std::string). This fails since std::string cannot match T*. But we find one overload of foo which has the exact type void (std::string), so it wins for the overload (3) case, and overload (3) is viable.

For overload (4) of bar, we first attempt type deduction for the same function template foo, this time with target type void (*)(const char*) This time type deduction succeeds, with T = const char. None of the other overloads of foo have the exact type void (const char*), so the function template specialization is used, and overload (4) is viable.

Finally, we compare overloads (3) and (4) by ordinary overload resolution. In both cases, the conversion of argument foo to a pointer to function is an Exact Match, so neither implicit conversion sequence is better than the other. But the standard conversion from const char[4] to const char* is better than the user-defined conversion sequence from const char[4] to std::string. So overload (4) of bar is the best viable function (and it uses void foo<const char>(const char*) as its argument).