Implementation Challenge: Concepts in C++14

09 Sep 2016 by Jonathan

There is the concept TS, a technical specification for including concepts into C++17. Concepts have always been a … concept in C++. They are used to document constraints on template parameters. For example:

template <typename RandomAccessIterator, typename Comperator>
void sort(RandomAccessIterator begin, RandomAccessIterator end, Comperator comp);

This function has the requirement that begin and end are both random access iterators and comp is a comparison function. Right now, the concepts are only documented and ignoring them leads to great error messages. The concept TS provides ways to embed them in the language directly and make, for example, overloading based on the concept easier.

But it doesn’t really bring anything new to the language. Everything it does can be accomplished with C++11’s expression SFINAE today, it only brings an (arguably) cleaner syntax and more complexity to the language.

In this post I’ll show you how to do implement concepts using only C++14 language features. I’ll try to make it as easy as possible by introducing some library utilities you can use very easily.

The Challenge

In a nutshell, the concept TS provides two features:

The ability to define a concept by specifying the requirements.
The ability to require a certain concept for a template parameter. This also affects overloading, if a type does not fulfill the required concept, a different overload is selected.

It also contains more features, like an abbreviated template syntax, but let’s ignore those purely syntactic features.

As becomes clear in the post: everything in the concept TS is a purely syntactic feature.

A concept definition looks like this:

template <typename T>
concept bool my_concept = some-value;

It also has a function form. It’s messy.

Well, that’s easy to write in existing code:

template <typename T>
constexpr bool my_concept = some-value;

See, just use constepxr instead of concept, done.

The more useful part is the requires expression. The requires expression is used to basically check if an expression compiles. If it compiles, it returns true, otherwise false.

It can be used like this:

template <typename T>
concept bool has_foo = requires(T t) {t.foo()};

has_foo<T> will now be true, if - given some variable t of type T - the expression t.foo() will compile. You can also check the resulting type of the expression and if it throws:

requires(T t)
{
    { t.foo() };
    { t.bar() } noexcept -> int;
};

Now given some t t.bar() must compile as well, be noexcept and returns something convertible to int. You can of course add more parameters at the top, and of different types.

There is also the requires clause used for 2.: to require certain things from template parameters. You can use it like so:

template <std::size_t I>
void foo() requires I > 0;

Now foo() will only be instantiated if I is greater than 0. Otherwise overload resolution will continue looking (and failing, if there is nothing else).

The requires clause can also be used with predefined concepts, of course:

template <typename T>
void foo(T t) requires has_foo<T>;

This requires or concept above for T. It can be simplified:

template <has_foo T>
void foo(T t);

And further to:

void foo(has_foo t); // implictly a template

Because of that, concepts are usually named differently from types.

The requires expression and clause are the two main features of the concept TS, everything else is just syntax honey. So let’s look how we can implement them.

The `requires` expression

A first attempt that works

We need a way to check if an expression compiles. Thanks to expression SFINAE, this is surprisingly easy. For example, this is how you check for a member function foo():

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

template <typename T, typename AlwaysVoid = void_t<>>
struct has_foo : std::false_type {};

template <typename T>
struct has_foo<T, void_t<decltype(std::declval<T>().foo())>> : std::true_type {};

The key here is the very stupid looking alias template void_t. No matter the types, it is always void. But this little alias is incredibly powerful.

We have a class template has_foo that maps to either std::true_type or std::false_type, depending on whether the type T has a member function foo(). The generic template maps to std::false_type. Thanks to the ordering rules of specializations, the compiler will try to pick the most specialized version possible and use the generic template only as fallback if it cannot use the other one. Note that the generic template has a second argument that defaults to void_t<>, this is the key the controls the specialization selection.

The specialization applies if the second type is void_t<...>. Because the second type defaults to void, this is always the case! However, the argument to the void_t is a decltype() expression. The compiler has to evaluate the expression and pass it to void_t even if it will not be used. And in order to evaluate the expression, it has to figure out the return type of calling foo() on some T object.

The std::declval<T>() is just used to give us a T object, even if the type has no default constructors. The function isn’t defined because it is only used in “unevaluated contexts” like decltype() or sizeof(), but its return type type is the only thing that matters.

If you pass a type that has a member function foo(), the compiler will first try the specializations, evaluate all arguments - including the void_t<> and thus the decltype(), is able to detect the return type of T::foo() and uses the specialization.

If the type does not have the member function foo(), the compiler cannot determine the return type. This is a Substitution Failure, but thankfully it Is Not An Error.

SFINAE!

Instead, the compiler will look further and select the main template: This does exactly the same as the equivalent requires expression.

Making it more general

But it is soo verbose.

A much nicer way would be to create a generic compiles traits that you only need to put the expression in. So let’s do that:

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

template <typename T, template <typename> class Expression, typename AlwaysVoid = void_t<>>
struct compiles : std::false_type {};

template <typename T, template <typename> class Expression>
struct compiles<T, Expression, void_t<Expression<T>>> : std::true_type {};

Instead of hard coding the expression in the traits, we pass it as additional template template parameter. It must be a template itself, because we must not instantiate it if it is ill-formed. Otherwise it does exactly the same and evaluates the expression in the specialization to allow SFINAE.

Now our has_foo looks like this:

template <typename T>
using use_foo = decltype(std::declval<T>().foo());

template <typename T>
using has_foo = compiles<T, use_foo>;

Sadly we have to do a completely separate alias template to specify the expression and can’t do it inline.

A more complex example

This is a lot less verbose, especially because most of the time you do not have such a simple concept and the necessary boilerplate is less. For example, here is a description of my BlockAllocator concept:

template <class Allocator>
concept bool BlockAllocator = requires(Allocator a, const Allocator ca, memory::memory_block b)
{
    {a.allocate_block()} -> memory::memory_block;
    {a.deallocate_block(b)};
    {ca.next_block_size()} -> std::size_t;
};

And this is how it would look using the technique above:

template <typename T>
struct BlockAllocator_impl
{
    template <class Allocator>
    using allocate_block = decltype(std::declval<Allocator>().allocate_block());

    template <class Allocator>
    using deallocate_block = decltype(std::declval<Allocator>().deallocate_block(std::declval<memory::memory_block>());

    template <class Allocator>
    using next_block_size = decltype(std::declval<const Allocator>().next_block_size());

    using result = std::conjunction<
        compiles_convertible_type<T, memory::memory_block, allocate_block>,
        compiles<T, deallocate_block>,
        compiles_same_type<T, std::size_t, next_block_size>
        >;
};

template <typename T>
using BlockAllocator = typename BlockAllocator_impl<T>::result;

std::conjunction is a C++17 addition that is std::true_type if all arguments are std::true_type, otherwise std::false_type. It is very easy to implement, I was just too lazy.

The two compiles_convertible_type and compiles_same_type are simple extensions of the compiles trait that assert std::is_convertible type or std::is_same type of the expression. Implementing those is left as an exercise of the reader.

With those, it is straightforward to actually define the concept: Just list of all the required expressions and require that they compile. I have used an extra struct so that the expression do not leak into the outer scope.

Making it even less verbose?

Granted, this is still more verbose than the requires version, but it doesn’t look so bad. Especially given because most of the time you are using concepts instead of writing them, so only rarely do you have to write it.

The only thing that really bothers me is the constant use of std::declval<T>(). It would be a lot nicer if something like this would work:

template <class Allocator>
using deallocate_block = decltype([](Allocator& a, memory::memory_block b)
                    {
                        return a.deallocate_block(b);
                    } (std::declval<Allocator&>(), std::declval<memory::memory_block>()));

We decltype() the result of calling a lambda.

But a lambda must not appear in an unevaluated context and even if it were, I’m not quite sure if it would work as intended.

Anyways, we can now define concepts and emulate the requires expression, on to the requires clause.

The `requires` clause

The requires clause is just a std::enable_if:

template <typename ResultType, typename CheckType, template <typename> class ... Values>
using requires = std::enable_if_t<std::conjunction<Values<CheckType>...>::value, ResultType>;

I use an alias template to make it more powerful and enable using an arbitrary number of concepts to check for at once:

template <typename T>
auto foo(const T& t) -> requires<void, T, ConceptA, ConceptB>;

Check out my SFINAE post for information about std::enable_if. In a nutshell, if all the concepts are fulfilled, the return type will be void. Otherwise it is ill-formed and overload resolution continues.

If you’ve used std::enable_if before, you know that you have to put it on all overloads if you want to select a fallback. For that reason, let’s define another helper alias:

template <typename ResultType, typename CheckType, template <typename> class ... Values>
using fallback = std::enable_if_t<std::conjunction<std::negation<Values<Check>>...>::value, ResultType>;

Again, std::negation is a C++17 helper that negates a std::integral_const<bool, X>.

The fallback is only valid if all the conditions are false. With it you can easily dispatch on multiple concepts:

template <typename T>
auto func(const T& t) -> requires<void, T, ConceptA>;

template <typename T>
auto func(const T& t) -> requires<void, T, ConceptB>;

template <typename T>
auto func(const T& t) -> fallback<void, T, ConceptA, ConceptB>;

Note that you have to put all the other conditions in the fallback function.

Inline concept definitions

If you don’t need to define your concepts before and only need to use them at one place, you can also use void_t<> directly:

template <typename T>
auto func(const T& t) -> void_t<decltype(t.foo())>;

This function is only selected if T has a member function foo(). Most of the time, this is sufficient.

Conclusion

Emulation of the requires clause is possible using almost the same syntax with std::enable_if. There is no need to make a “cuter” syntax that doesn’t really show the template:

void func(const ConceptA& a); // template if `ConceptA` is a real concept

And the long form is almost identical to the solution shown above:

template <typename T>
void func(const T& t) requires ConceptA<T>;

DISCLAIMER: The following paragraphs can be seen as rant.

I thought the standard committee preferred library solutions over language solutions? Why make it part of the language then?

The requires expression however, can only be emulated with a more verbose syntax and the help of library additions, you would have to write every time you want to use it.

Except that it is already in the library fundamentals v2 TS. The idiom I’ve shown is the detection idiom and likewise they propose std::is_detected.

But even with the help of it, the syntax isn’t quite as nice as the requires expression, so it could simplify it. But is the additional complexity worth it?

I mean, it makes the syntax nicer, but let’s face it: who writes concept?

Template heavy libraries. And they already need to use TMP for other things, is the simplification of one part worth it?

Every new feature, especially language features, comes with additional complexity, implementation difficulties, learning difficulties. C++ is already a bloated language, do we really need more new syntax sugar? Couldn’t we achieve the same thing by weakening the rules for other things like the lambda example I’ve shown?

After all, C is simple, because it has so few features.

Luckily, I do not have to make the decision but can just rant about it. If one day concepts will make it into C++, I’ll probably use them in projects where I do not have to support older compilers. But this is not a language feature I’m looking forward to.

Appendix A: But concepts improve error messages!

For starters: as far as I know, they don’t. This could be changed by now.

But I’ve already written about improving error messages. The literal same technique can be applied here:

template <typename T>
auto func(const T& t) -> requires<void, T, ConceptA>;

template <typename T>
auto func(const T& t) -> fallback<void, T, ConceptA>
{
    static_assert(always_false<T>::value, "T does not model ConceptA");
}

always_false<T> is always std::false_type. Used to trick smart compilers.

So if T does not model ConceptA, the fallback is selected, the static assertion fails and a user defined error message is shown.

Appendix B: What about `constexpr if`?

It is sometimes said that instead of concepts, the language should focus on constexpr if.

Instead of selecting overloads, one can also select function implementations using C++17’s constexpr if. This removes the need for concepts as dispatching mechanism if you have a valid implementation for each case, but still requires traits to detect the expression.

But if you don’t have a valid implementation for each case, you might want to SFINAE detect that further and have to use different overloads.

[meta] Appendix C: There are ads!

Yes, there are now ads on this site.

I applied to Google Adsense, not really expecting to be accepted. Well, now I am.

These ads are mainly used as motivation for me to write more posts, I don’t expect to earn much money with it - most of you are using an ad blocker anyway. But I’ll tree to keep them not much intrusive and ensure matching content as much as I can.

This blog post was written for my old blog design and ported over. If there are any issues, please let me know.