Implementing Concepts in C++14

I haven't posted in quite some time. For now, I want to show some cool stuff.

CppCon 2016 just ended. I had a wonderful time at the conference this year. There were some very interesting talks and panels (which I recommend you watch on YouTube, once they are uploaded). The ones that stood out to me were the coroutines talks. I also got to participate in SG14 and I started writing my first proposal for an intrusive smart pointer, which will hopefully be sent in before the Issaquah mailing deadline. There was quite a bit of interest from SG14, as well as Gor Nishanov from Microsoft. On Wednesday night, I decided to ask if there was a slot left for a thursday lightning talk and I was able to get myself squeezed in. The talk was originally titled No Concepts Beyond This Point, but I later wanted to call it Sic Semper SFINAE. Effectively, I showed a brief example on how to implement concepts (at least, the compile time interface constraints) in C++14. I ran out of time, however, so I decided to write this post to explain it a bit better and to show it off. It's not perfect; Extra work is required for placeholder types (assuming it is even possible). However, in today's post I'll be showing you how to implement them yourself. I'll be using the code I wrote before my lightning talk as a base. I only had 5 minutes to explain everything in my talk, so I'll be able to go into more depth and explain show it working.

The first thing I'll be showing is the detection idiom. The detection idiom is part of the C++ Library Fundamentals V2 Technical Specification. It's extremely powerful, building on top of void_t. If you don't know about void_t, I recommend you watch Walter E. Brown's talk on metaprogramming from C++14. Specifically, it allows one to detect if an expression is valid or not. There are some minute corner cases, but the breadth of features provided by these types cover almost all of them. Even better, they're extremely easy to implement. You one can even take the implementation found at the cppreference wiki and it will just work. The types we'll be using are:

  • is_detected<Op, Args...>
  • is_detected_convertible<To, Op, Args...>
  • is_detected_exact<Exact, Op, Args...>
  • detected_t<Op, Args...>

We'll also be using conjunction<Ts...>, disjunction<Ts...>, and bool_constant<B>. These are in C++17, but are easy for anyone to implement. We won't be using them directly however. It becomes a lot easier to use them when we wrap them into template variables:

template <bool... Bs>
constexpr bool require = conjunction<bool_constant<Bs>...>::value;

template <bool... Bs>
constexpr bool either = disjunction<bool_constant<Bs>...>::value;

template <bool... Bs>
constexpr bool disallow = not require<Bs...>;

It's extremely simple. Next we need to create some more explicit expressions. For example, we might want to know if the result of an expression is identical to to some given type. We also might want to know if the result of an expression converts to to some given type. We also just want to know if an expression is even valid. This is easy for us to implement, as we'll be wrapping the detection idiom types we previously mentioned:

template <template <class...> class Op, class... Args>
constexpr bool exists = is_detected<Op, Args...>::value;

template <class To, template <class...> class Op, class... Args>
constexpr bool converts_to = is_detected_convertible<To, Op, Args...>::value;

template <class Exact, template <class...> class Op, class... Args>
constexpr bool identical_to = is_detected_exact<Exact, Op, Args...>::value;

Neat! Now we can start writing what I call detection template metafunctions. There is one limitation with these detection metafunctions, and that is how we detect whether an expression is valid in an ADL context (such as swap). But we have namespaces, so this is easy to solve:

namespace adl {
  using std::swap;

  template <class T, class U=T>
  using swap_with = decltype(swap(declval<T>(), declval<U>()));
};

We can now technically make our first two concepts. Specifically, we'll be adding a SwappableWith<T, U> and Swappable<T> concept. We'll be placing them into a concepts namespace, but this will not be shown:

template <class T, class U>
constexpr bool SwappableWith = exists<adl::swap_with, T, U>;

template <class T>
constexpr bool Swappable = SwappableWith<T&, T&>;

You'll notice that our concepts are just constexpr bool. This is because there is almost no difference between a concept and a constexpr bool. Explaining why they are almost not different is for another post.

We can also make general C++ standard library type traits concepts as well:

template <class T>
constexpr bool CopyConstructible = is_copy_constructible<T>::value;

template <class T>
constexpr bool CopyAssignable = is_copy_assignable<T>::value;

template <class T>
constexpr bool Destructible = is_destructible<T>::value;

template <class T>
constexpr bool Pointer = is_pointer<T>::value;

Although we are using the standard library for these concepts, we can actually implement them without the standard libraries or the compiler:

template <class T>
using copy_assignable = decltype(declval<T&>() = declval<T const&>());

template <class T>
constexpr bool CopyAssignable = exists<copy_assignable, T>;

Thus far we've been doing simple definitions. But let's get more complex. Let's try to check if a type meets the C++ standard library Iterator concept. For a type to satisfy the Iterator concept, it must satisfy the following concepts:

  • CopyConstructible
  • CopyAssignable
  • Destructible
  • Swappable

It also must support calling the prefix increment operator (++) which then returns itself, as well as dereferencing an instance. We've already made the concepts mentioned. Lets write some detectors for our eventual concept:

namespace ops {
  template <class T> using prefix_increment = decltype(++declval<T>());
  template <class T> using dereference = decltype(*declval<T>());
}

Excellent. Now we can finally get down to writing our Iterator concept:

template <class T>
constexpr bool Iterator = require<
  CopyConstructible<T>,
  CopyAssignable<T>,
  Destructible<T>,
  Swappable<T>,
  exists<ops::prefix_increment, T>,
  exists<ops::dereference, T>
>;

Let's give it a whirl! We're going to pass in a shared_ptr, an int, a int* and then a std::vector<int>::iterator:

static_assert(concepts::Iterator<std::vector<int>::iterator>, "");
static_assert(concepts::Iterator<int*>, "");

static_assert(not concepts::Iterator<std::shared_ptr<int>>, "");
static_assert(not concepts::Iterator<int>, "");

The above asserts compile! Radical! But we can go deeper. Let's make an InputIterator concept. In addition to modeling the Iterator, we also require the EqualityComparable concept. We also need to make sure there is a reference and value_type member type alias, as well as an iterator_category that is convertible to input_iterator_tag. Additionally, we need to check the return value of dereferencing the iterator, as well as check that it supports operator -> overload, as well as postfix increment. We're going to briefly make a shortcut, however, and skip all these checks if the given type is a code:Pointer. Now, we do know to rely on iterator_traits to receive the member type aliases, and we've also shown we can check for operator overloads. Let's write our detectors:

namespace iter {
  template <class T>
  using value_type = typename iterator_traits<T>::value_type;

  template <class T>
  using reference = typename iterator_traits<T>::reference;

  template <class T>
  using category = typename iterator_traits<T>::iterator_category;

  template <class T>
  using pointer = typename iterator_traits<T>::pointer;
}

namespace ops {
  template <class T> using postfix_increment = decltype(declval<T>()++);
  template <class T> using arrow = decltype(declval<T>().operator->());

}

Just like before, it's extremely simple. We now have everything we need to model the InputIterator concept. One thing to note in the code below is the use of detected_t for dependent lookups. This is just a consequence of parsing and detected_t lets us work around this:

template <class T>
constexpr bool InputIterator = either<
  Pointer<T>, // if this fails, we move to the require check
  require<
    EqualityComparable<T>,
    Iterator<T>,
    exists<iter::value_type, iter>,
    exists<iter::reference, iter>,
    either<
      identical_to<detected<iter::reference, T>, ops::dereference, T>,
      converts_to<detected<iter::value_type, T>, ops::dereference, T>
    >,
    identical_to<detected<iter::pointer, T>, ops::arrow, T>,
    converts_to<detected_t<iter::value_type, T>, ops::dereferece, T&>
    converts_to<input_iterator_tag, iter::category, T>
  >
>;

Not bad. A bit more verbose in the long run, but let's see this in action. We'll implement std::for_each, and use our new concept within a static_assert. We can use enable_if_t to let SFINAE take care of it for us (and we don't get a bunch of template error vomit), but a static_assert, lets us give a better error to the user:

template <class InputIt, class UnaryFunction>
auto each (InputIt first, InputIt last, UnaryFunction fun) {
  using concepts::InputIterator;
  static_assert(
    InputIterator<InputIt>
    "template argument 'InputIt' does not model InputIterator");
  return std::for_each(first, last, fun);
}

int main () {
  std::vector<int> values { 1, 2, 3, 4 };
  each(values.begin(), values.end(), [] (auto&& x) { std::printf("%d ", x); });
  each(1, 2, [] (auto&&) { });
  std::puts("");
}

If we compile this under clang, we get the error static_assert failed "template argument 'InputIt' does not model InputIterator". It's also at the top, and easier to find. If we comment out line 13, our code compiles without errors. I recommend you attempt to use the above each function with enable_if_t and see the difference in errors.

There we have it. We've created "concepts" out of type traits and detector metafunctions and we've also used them to compose more complex concepts and then used these concepts to constrain a generic function. And finally we get to see that our errors are not the usual amount of errors we might receive when doing this amount of template metaprogramming.

You can find the material I used in my CppCon 2016 lightning talk on my github.