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 templates 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 some given type. We also might want to know if the result of an expression converts 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, and that is how we detect whether an
expression is valid in an ADL context (such as std::swap). But we have
namespaces in C++, so we can easily solve this:
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 is not shown in the example below:
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 compiler builtins:
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 named
requirement. For a type to satisfy the Iterator requirement, it must satisfy
the following:
- CopyConstructible
- CopyAssignable
- Destructible
- Swappable
It also must support calling the prefix increment operator (++) which then
returns itself, as well as dereferencing an instance (unary operator *).
We’ve already made the concepts mentioned. Let’s 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, an
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 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.