The mechanics of extension via free functions or member functions

Question

Loads of C++ libraries, the standard included, allow you to adapt your objects for use in the libraries. The choice is often between a member function or a free function in the same namespace.

I'd like to know mechanics and constructs the library code uses to dispatch a call which will call one of these "extension" functions, I know this decision has to take place during compile time and involves templates. The following runtime psuedocode is not possible/non-sense, the reasons are out of the scope of this question.

if Class A has member function with signature FunctionSignature
    choose &A.functionSignature(...)
else if NamespaceOfClassA has free function freeFunctionSignature
    choose freeFunctionSignature(...)
else
    throw "no valid extension function was provided"

The code above looks like runtime code :/. So, how does the library figure out the namespace a class is in, how does it detect the three conditions, what other pitfalls are there that need to be avoided.

The motivation for my question is for me to be able to find the dispatch blocks in libraries, and to be able to use the constructs in my own code. So, detailed answers will help.

!!TO WIN BOUNTY!!

Ok so according to the answer from Steve (and the comments) ADL and SFINAE are the key constructs for wiring up the dispatch at compile time. I've got my head arround ADL (primitively) and SFINAE (again rudementary). But I don't know how they orchistrate together in the way I think they should.

I want to see a illustrative example of how these two constructs can be put together so that a library can choose at compile time whether to call a user supplied member function in an object, or a user supplied free function supplied in the same object's namespace. This should only be done using the two constructs above, no runtime dispatch of any sort.

Lets say the object in question is called NS::Car, and this object needs to provide the behaviour of MoveForward(int units), as a member function ofc. If the behaviour is to be picked up from the object's namespace it will probably look like MoveForward(const Car & car_, int units). Lets define the function that wants to dispatch mover(NS::direction d, const NS::vehicle & v_) , where direction is an enum, and v_ is a base class of NS::car.

Answer 1

The library doesn't do any of this at runtime, dispatch is done by the compiler when the calling code is compiled. Free functions in the same namespace as one of the arguments are found according to the rules of a mechanism called "Argument-Dependent Lookup" (ADL), sometimes called "Koenig lookup".

In cases where you have the option either to implement a free function or a member function, it may be because the library provides a template for a free function that calls the member function. Then if your object provides a function of the same name by ADL, it will be a better match than instantiating the template, and hence will be chosen first. As Space_C0wb0y says, they might use SFINAE to detect the member function in the template, and do something different according to whether it exists or not.

You can't change the behaviour of std::cout << x; by adding a member function to x, so I'm not quite sure what you mean there.

Answer 2

Well, I can tell you how to detect the presence of member functions of a certain name (and signature) at compile time. A friend of mine describes it here:

Detecting the Existence of Member Functions at Compile-Time

However that won't get you where you want to go, because it only works for the static type. Since you want to pass a "reference-to-vehicle", there is no way to test if the the dynamic type (the type of the concrete object behind the reference) has such a member function.

If you settle for the static type though, there is another way to do a very similar thing. It implements "if the user provides an overloaded free function, call it, otherwise try to call the member function". And it goes like this:

namespace your_ns {

template <class T>
void your_function(T const& t)
{
    the_operation(t); // unqualified call to free function
}

// in the same namespace, you provide the "default"
// for the_operation as a template, and have it call the member function:

template <class T>
void the_operation(T const& t)
{
    t.the_operation();
}

} // namespace your_ns

That way the user can provide it's own overload of "the_operation", in the same namespace as his class, so it's found by ADL. Of course the user's "the_operation" must be "more specialized" than your default implementation - otherwise the call would be ambiguous. In practice that's not a problem though, since everything that restricts the type of the parameter more than it being a reference-to-const to anything will be "more specialized".

Example:

namespace users_ns {

class foo {};

void the_operation(foo const& f)
{
    std::cout << "foo\n";
}

template <class T>
class bar {};

template <class T>
void the_operation(bar<T> const& b)
{
    std::cout << "bar\n";
}

} // namespace users_ns

EDIT: after reading Steve Jessop's answer again, I realize that's basically what he wrote, only with more words :)

Answer 3

If you're just looking for a concrete example, consider the following:

#include <cassert>
#include <type_traits>
#include <iostream>

namespace NS
{
    enum direction { forward, backward, left, right };

    struct vehicle { virtual ~vehicle() { } };

    struct Car : vehicle
    {
        void MoveForward(int units) // (1)
        {
            std::cout << "in NS::Car::MoveForward(int)\n";
        }
    };

    void MoveForward(Car& car_, int units)
    {
        std::cout << "in NS::MoveForward(Car&, int)\n";
    }
}

template<typename V>
class HasMoveForwardMember // (2)
{
    template<typename U, void(U::*)(int) = &U::MoveForward>
    struct sfinae_impl { };

    typedef char true_t;
    struct false_t { true_t f[2]; };

    static V* make();

    template<typename U>
    static true_t check(U*, sfinae_impl<U>* = 0);
    static false_t check(...);

public:
    static bool const value = sizeof(check(make())) == sizeof(true_t);
};

template<typename V, bool HasMember = HasMoveForwardMember<V>::value>
struct MoveForwardDispatcher // (3)
{
    static void MoveForward(V& v_, int units) { v_.MoveForward(units); }
};

template<typename V>
struct MoveForwardDispatcher<V, false> // (3)
{
    static void MoveForward(V& v_, int units) { NS::MoveForward(v_, units); }
};

template<typename V>
typename std::enable_if<std::is_base_of<NS::vehicle, V>::value>::type // (4)
mover(NS::direction d, V& v_)
{
    switch (d)
    {
    case NS::forward:
        MoveForwardDispatcher<V>::MoveForward(v_, 1); // (5)
        break;
    case NS::backward:
        // ...
        break;
    case NS::left:
        // ...
        break;
    case NS::right:
        // ...
        break;
    default:
        assert(false);
    }
}

struct NonVehicleWithMoveForward { void MoveForward(int) { } }; // (6)

int main()
{
    NS::Car v; // (7)
    //NonVehicleWithMoveForward v;  // (8)
    mover(NS::forward, v);
}

HasMoveForwardMember (2) is a metafunction that checks for the existence of a member function of that name with the signature void(V::*)(int) in a given class V. MoveForwardDispatcher (3) uses this information to call the member function if it exists or falls back to calling a free function if it doesn't. mover simply delegates the invocation of MoveForward to MoveForwardDispatcher (5).

The code as-posted will invoke Car::MoveForward (1), but if this member function is removed, renamed, or has its signature changed, NS::MoveForward will be called instead.

Also note that because mover is a template, a SFINAE check must be put in place to retain the semantics of only allowing objects derived from NS::vehicle to be passed in for v_ (4). To demonstrate, if one comments out (7) and uncomments (8), mover will be called with an object of type NonVehicleWithMoveForward (6), which we want to disallow despite the fact that HasMoveForwardMember<NonVehicleWithMoveForward>::value == true.

(Note: If your standard library does not come with std::enable_if and std::is_base_of, use the std::tr1:: or boost:: variants instead as available.)

The way this sort of code is usually used is to always call the free function, and implement the free function in terms of something like MoveForwardDispatcher such that the free function simply calls the passed in object's member function if it exists, without having to write overloads of that free function for every possible type that may have an appropriate member function.