void_t "can implement concepts"?

I was watching the second part of Walter Brown's CppCon2014 talk on template metaprogramming, during which he discussed the uses of his novel void_t<> construction. During his presentation Peter Sommerlad asked him a question that I didn't quite understand. (link goes directly to the question, the code under discussion took place directly before that)

Sommerlad asked > Walter, would that mean we actually can implement concepts lite right now?

to which Walter responded > Oh yeah! I've done it ... It doesn't have quite the same syntax.

I understood this exchange to be about Concepts Lite. Is this pattern really that versatile? For whatever reason, I am not seeing it. Can someone explain (or sketch) how something like this might look? Is this just about enable_if and defining traits, or what was the questioner referring to?

The void_t template is defined as follows:

template<class ...> using void_t = void;

He uses this then to detect if type statements are well formed, using this to implement the is_copy_assignable type trait:

//helper type
template<class T>
using copy_assignment_t
= decltype(declval<T&>() = declval<T const&>());

//base case template
template<class T, class=void>
struct is_copy_assignable : std::false_type {};

//SFINAE version only for types where copy_assignment_t<T> is well-formed.
template<class T>
struct is_copy_assignable<T, void_t<copy_assignment_t<T>>> 
: std::is_same<copy_assignment_t<T>,T&> {};

Because of the talk, I understand how this example works, but I don't see how we get from here to something like Concepts Lite.

Yes, concepts lite basically dresses up SFINAE. Plus it allows deeper introspection to allow for better overloading. However that only works if the concept predicates are defined as concept bool. The improved overloading does not work with the current concept predicates, but conditional overloading can be used. Lets look how we can define predicates, constrain templates, and overload functions in C++14. This is kind of long, but it goes over how to create all of the tools needed to accomplish this in C++14.

Defining Predicates

First, it is kind of ugly to read the predicate with all the std::declval and decltype everywhere. Instead, we can take advantage of the fact that we can constrain a function using a trailing decltype(from Eric Niebler’s blog post here), like this:

struct Incrementable
{
    template<class T>
    auto requires_(T&& x) -> decltype(++x);
};

So if ++x is not valid, then the requires_ member function is not callable. So we can create a models trait that just checks if requires_ is callable using void_t:

template<class Concept, class Enable=void>
struct models
: std::false_type
{};

template<class Concept, class... Ts>
struct models<Concept(Ts...), void_t< 
    decltype(std::declval<Concept>().requires_(std::declval<Ts>()...))
>>
: std::true_type
{};

Constraining Templates

So when we want to constrain the template based on the concept, we will still need to use enable_if, but we can use this macro to help make it cleaner:

#define REQUIRES(...) typename std::enable_if<(__VA_ARGS__), int>::type = 0

So we can define an increment function that is constrained based on Incrementable concept:

template<class T, REQUIRES(models<Incrementable(T)>())>
void increment(T& x)
{
    ++x;
}

So if we call increment with something that is not Incrementable, we will get an error like this:

test.cpp:23:5: error: no matching function for call to 'incrementable'
    incrementable(f);
    ^~~~~~~~~~~~~
test.cpp:11:19: note: candidate template ignored: disabled by 'enable_if' [with T = foo]
template<class T, REQUIRES(models<Incrementable(T)>())>
                  ^

Overloading Functions

Now if we want to do overloading, we want to use conditional overloading. Say we want to create an std::advance using concept predicates, we could define it like this(for now we will ignore the decrementable case):

struct Incrementable
{
    template<class T>
    auto requires_(T&& x) -> decltype(++x);
};

struct Advanceable
{
    template<class T, class I>
    auto requires_(T&& x, I&& i) -> decltype(x += i);
};

template<class Iterator, REQUIRES(models<Advanceable(Iterator, int)>())>
void advance(Iterator& it, int n)
{
    it += n;
}

template<class Iterator, REQUIRES(models<Incrementable(Iterator)>())>
void advance(Iterator& it, int n)
{
    while (n--) ++it;
}

However, this causes an ambiguous overload(In concepts lite this would still be an ambiguous overload unless we change our predicates to refer to the other predicates in a concept bool) when its used with std::vector iterator. What we want to do is order the calls, which we can do using conditional overloading. It can be thought of writing something like this(which is not valid C++):

template<class Iterator>
void advance(Iterator& it, int n) if (models<Advanceable(Iterator, int)>())
{
    it += n;
} 
else if (models<Incrementable(Iterator)>())
{
    while (n--) ++it;
}

So if the first function isn't called, it will call the next function. So lets start by implementing it for two functions. We will create a class called basic_conditional which accepts two function objects as template parameters:

struct Callable
{
    template<class F, class... Ts>
    auto requires_(F&& f, Ts&&... xs) -> decltype(
        f(std::forward<Ts>(xs)...)
    );
};

template<class F1, class F2>
struct basic_conditional
{
    // We don't need to use a requires clause here because the trailing
    // `decltype` will constrain the template for us.
    template<class... Ts>
    auto operator()(Ts&&... xs) -> decltype(F1()(std::forward<Ts>(xs)...))
    {
        return F1()(std::forward<Ts>(xs)...);
    }
    // Here we add a requires clause to make this function callable only if
    // `F1` is not callable.
    template<class... Ts, REQUIRES(!models<Callable(F1, Ts&&...)>())>
    auto operator()(Ts&&... xs) -> decltype(F2()(std::forward<Ts>(xs)...))
    {
        return F2()(std::forward<Ts>(xs)...);
    }
};

So now that means we need to define our functions as functions objects instead:

struct advance_advanceable
{
    template<class Iterator, REQUIRES(models<Advanceable(Iterator, int)>())>
    void operator()(Iterator& it, int n) const
    {
        it += n;
    }
};

struct advance_incrementable
{
    template<class Iterator, REQUIRES(models<Incrementable(Iterator)>())>
    void operator()(Iterator& it, int n) const
    {
        while (n--) ++it;
    }
};

static conditional<advance_advanceable, advance_incrementable> advance = {};

So now if we try to use it with an std::vector:

std::vector<int> v = { 1, 2, 3, 4, 5, 6 };
auto iterator = v.begin();
advance(iterator, 4);
std::cout << *iterator << std::endl;

It will compile and print out 5.

However, std::advance actually has three overloads, so we can use the basic_conditional to implement conditional that works for any number of functions using recursion:

template<class F, class... Fs>
struct conditional : basic_conditional<F, conditional<Fs...>>
{};

template<class F>
struct conditional<F> : F
{};

So, now we can write the full std::advance like this:

struct Incrementable
{
    template<class T>
    auto requires_(T&& x) -> decltype(++x);
};

struct Decrementable
{
    template<class T>
    auto requires_(T&& x) -> decltype(--x);
};

struct Advanceable
{
    template<class T, class I>
    auto requires_(T&& x, I&& i) -> decltype(x += i);
};

struct advance_advanceable
{
    template<class Iterator, REQUIRES(models<Advanceable(Iterator, int)>())>
    void operator()(Iterator& it, int n) const
    {
        it += n;
    }
};

struct advance_decrementable
{
    template<class Iterator, REQUIRES(models<Decrementable(Iterator)>())>
    void operator()(Iterator& it, int n) const
    {
        if (n > 0) while (n--) ++it;
        else 
        {
            n *= -1;
            while (n--) --it;
        }
    }
};

struct advance_incrementable
{
    template<class Iterator, REQUIRES(models<Incrementable(Iterator)>())>
    void operator()(Iterator& it, int n) const
    {
        while (n--) ++it;
    }
};

static conditional<advance_advanceable, advance_decrementable, advance_incrementable> advance = {};

Overloading With Lambdas

However, additionally, we could use lambdas to write it instead of function objects which can help make it cleaner to write. So we use this STATIC_LAMBDA macro to construct lambdas at compile time:

struct wrapper_factor
{
    template<class F>
    constexpr wrapper<F> operator += (F*)
    {
        return {};
    }
};

struct addr_add
{
    template<class T>
    friend typename std::remove_reference<T>::type *operator+(addr_add, T &&t) 
    {
        return &t;
    }
};

#define STATIC_LAMBDA wrapper_factor() += true ? nullptr : addr_add() + []

And add a make_conditional function that is constexpr:

template<class... Fs>
constexpr conditional<Fs...> make_conditional(Fs...)
{
    return {};
}

Then we can now write the advance function like this:

constexpr const advance = make_conditional(
    STATIC_LAMBDA(auto& it, int n, REQUIRES(models<Advanceable(decltype(it), int)>()))
    {
        it += n;
    },
    STATIC_LAMBDA(auto& it, int n, REQUIRES(models<Decrementable(decltype(it))>()))
    {
        if (n > 0) while (n--) ++it;
        else 
        {
            n *= -1;
            while (n--) --it;
        }
    },
    STATIC_LAMBDA(auto& it, int n, REQUIRES(models<Incrementable(decltype(it))>()))
    {
        while (n--) ++it;
    }
);

Which is little more compact and readable than using the function object versions.

Additionally, we could define a modeled function to reduce down the decltype ugliness:

template<class Concept, class... Ts>
constexpr auto modeled(Ts&&...)
{
    return models<Concept(Ts...)>();
}

constexpr const advance = make_conditional(
    STATIC_LAMBDA(auto& it, int n, REQUIRES(modeled<Advanceable>(it, n)))
    {
        it += n;
    },
    STATIC_LAMBDA(auto& it, int n, REQUIRES(modeled<Decrementable>(it)))
    {
        if (n > 0) while (n--) ++it;
        else 
        {
            n *= -1;
            while (n--) --it;
        }
    },
    STATIC_LAMBDA(auto& it, int n, REQUIRES(modeled<Incrementable>(it)))
    {
        while (n--) ++it;
    }
);

Finally, if you are interested in using existing library solutions(rather than rolling your own like I've shown). There is the Tick library that provides a framework for defining concepts and constraining templates. And the Fit library can handle the functions and overloading.