Month: September 2017

Simon Brand from Simon Brand

Concepts is a proposed C++ feature which allows succinct, expressive, and powerful constraining of templates. They have been threatening to get in to C++ for a long time now, with the first proposal being rejected for C++11. They were finally merged in to C++20 a few months ago, which means we need to hold on for another few years before they’re in the official standard rather than a Technical Specification. In the mean time, there have been various attempts to implement parts of concepts as a library so that we can have access to some of the power of Concepts without waiting for the new standard. The detection idiom – designed by Walter Brown and part of the Library Fundamentals 2 Technical Specification – is one such solution. This post will outline the utility of it, and show the techniques which underlie its implementation.

A problem

We are developing a generic library. At some point on our library we need to calculate the foo factor for whatever types the user passes in.

template <class T>
int calculate_foo_factor (const T& t);

Some types will have specialized implementations of this function, but for types which don’t we’ll need some generic calculation.

struct has_special_support {
  int get_foo() const;
};

struct will_need_generic_calculation {
  // no get_foo member function
};

Using concepts we could write calculate_foo_factor like so:

template <class T>
concept bool SupportsFoo = requires (T t) {
  { t.get_foo() } -> int;
};

template <SupportsFoo T>
int calculate_foo_factor (const T& t) {
    return t.get_foo();
}

template <class T>
int calculate_foo_factor (const T& t) {
    // insert generic calculation here
    return 42;
}

This is quite succinct and clear: SupportsFoo is a concept which checks that we can call get_foo on t with no arguments, and that the type of that expression is int. The first calculate_foo_factor will be selected by overload resolution for types which satisfy the SupportsFoo concept, and the second will be chosen for those which don’t.

Unfortunately, our library has to support C++14. We’ll need to try something different. I’ll demonstrate a bunch of possible solutions to this problem in the next section. Some of them may seem complex if you aren’t familiar with the metaprogramming techniques used, but for now, just note the differences in complexity and abstraction between them. The metaprogramming tricks will all be explained in the following section.

Solutions

Here’s a possible solution using expression SFINAE:

namespace detail {
  template <class T>
  auto calculate_foo_factor (const T& t, int)
    -> decltype(t.get_foo()) {
    return t.get_foo();
  }

  template <class T>
  int calculate_foo_factor (const T& t, ...) {
    // insert generic calculation here
    return 42;
  }
}

template <class T>
int calculate_foo_factor (const T& t) {
  return detail::calculate_foo_factor(t, 0);
}

Well, it works, but it’s not exactly clear. What’s the int and ... there for? Why do we need an extra overload? The answers are not the important part here; what is important is that unless you’ve got a reasonable amount of metaprogramming experience, it’s unlikely you’ll be able to write this code offhand, or even copy-paste it without error.

The code could be improved by abstracting out the check for the presence of the member function into its own metafunction:

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

template <class T, class=void>
struct supports_foo : std::false_type{};

template <class T>
struct supports_foo<T, void_t<decltype(std::declval<T>().get_foo())>>
: std::true_type{};

Again, some more expert-only template trickery which I’ll explain later. Using this trait, we can use std::enable_if to enable and disable the overloads as required:

template <class T, std::enable_if_t<supports_foo<T>::value>* = nullptr>
auto calculate_foo_factor (const T& t) {
  return t.get_foo();
}

template <class T, std::enable_if_t<!supports_foo<T>::value>* = nullptr>
int calculate_foo_factor (const T& t) {
  // insert generic calculation here
  return 42;
}

This works, but you’d need to understand how to implement supports_foo, and you’d need to repeat all the boilerplate again if you needed to write a supports_bar trait. It would be better if we could completely abstract away the mechanism for detecting the member function and just focus on what we want to detect. This is what the detection idiom provides.

template <class T>
using foo_t = decltype(std::declval<T>().get_foo());

template <class T>
using supports_foo = is_detected<foo_t,T>;

is_detected here is part of the detection idiom. Read it as “is it valid to instantiate foo_t with T?” std::declval<T>() essentially means “pretend that I have a value of type T” (more on this later). This still requires some metaprogramming magic, but it’s a whole lot simpler than the previous examples. With this technique we can also easily check for the validity of arbitrary expressions:

template <class T, class U>
using equality_t = decltype(std::declval<T>() == std::declval<U>());

template <class T, class U>
using supports_equality = is_detected<equality_t, T, U>;

struct foo{};
struct bar{};
struct baz{};

bool operator== (foo, bar);

static_assert( supports_equality<foo,bar>::value, "wat");
static_assert(!supports_equality<foo,baz>::value, "wat");

We can also compose traits using std::conjunction:

template <class T>
using is_regular = std::conjunction<std::is_default_constructible<T>,
                                    std::is_copy_constructible<T>,
                                    supports_equality<T,T>,
                                    supports_inequality<T,T>, //assume impl
                                    supports_less_than<T,T>>; //ditto

If you want to use is_detected today, then you can check if your standard library supports std::experimental::is_detected. If not, you can use the implementation from cppreference or the one which we will go on to write in the next section. If you aren’t interested in how this is written, then turn back, for here be metaprogramming dragons.

Metaprogramming demystified

I’ll now work backwards through the metaprogramming techniques used, leading up to implementing is_detected.

Type traits and _v and _t suffixes

A type trait is some template which can be used to get information about characteristics of a type. For example, you can find out if some type is an arithmetic type using std::is_arithmetic:

template <class T>
void foo(T t) {
     static_assert(std::is_arithmetic<T>::value, "Argument must be of an arithmetic type");
}

Type traits either “return” types with a ::type member alias, or values with a ::value alias. _t and _v suffixes are shorthand for these respectively. So std::is_arithmetic_v<T> is the same as std::is_arithmetic<T>::value, std::add_pointer_t<T> is the same as typename std::add_pointer<T>::type¹.

decltype specifiers

decltype gives you access to the type of an entity or expression. For example, with int i;, decltype(i) is int.

std::declval trickery

std::declval is a template function which helps create values inside decltype specifiers. std::declval<foo>() essentially means “pretend I have some value of type foo”. This is needed because the types you want to inspect inside decltype specifiers may not be default-constructible. For example:

struct foo {
    foo() = delete;
    foo(int);
    void do_something();
};

decltype(foo{}.do_something())               // invalid
decltype(std::declval<foo>().do_something()) // fine

SFINAE and std::enable_if

SFINAE stands for Substitution Failure Is Not An Error. Due to this rule, some constructs which are usually hard compiler errors just cause a function template to be ignored by overload resolution. std::enable_if is a way to gain easy access to this. It takes a boolean template argument and either contains or does not contain a ::type member alias depending on the value of that boolean. This allows you to do things like this:

template <class T>
std::enable_if_t<std::is_integral_v<T>> foo(T t);

template <class T>
std::enable_if_t<std::is_floating_point_v<T>> foo(T t);

If T is integral, then the second overload will be SFINAEd out, so the first is the only candidate. If T is floating point, then the reverse is true.

Expression SFINAE

Expression SFINAE is a special form of SFINAE which applies to arbitrary expressions. This is what allowed this example from above to work:

namespace detail {
  template <class T>
  auto calculate_foo_factor (const T& t, int)
    -> decltype(std::declval<T>().get_foo()) {
    return t.get_foo();
  }

  template <class T>
  int calculate_foo_factor (const T& t, ...) {
    // insert generic calculation here
    return 42;
  }
}

int calculate_foo_factor (const T& t) {
  return calculate_foo_factor(t, 0);
}

The first overload will be SFINAEd out if calling get_foo on an instance of T is invalid. The difficulty here is that both overloads will be valid if the get_foo call is valid. For this reason, we add some dummy parameters to the overloads (int and ...) to specify an order for overload resolution to follow².

void_t magic

void_t is a C++17 feature (although it’s implementable in C++11) which makes writing traits and using expression SFINAE a bit easier. The implementation is deceptively simple³:

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

You can see this used in this example which we used above:

template <class T, class=void>
struct supports_foo : std::false_type{};

template <class T>
struct supports_foo<T, void_t<decltype(std::declval<T>().get_foo())>>
: std::true_type{};

The relevant parts are the class=void and void_t<...>. If the expression inside void_t is invalid, then that specialization of supports_foo will be SFINAEd out, so the primary template will be used. Otherwise, the whole expression will be evaluated to void due to the void_t and this will match the =void default argument to the template. This gives a pretty succinct way to check arbitrary expressions.

That covers all of the ingredients we need to implement is_detected.

The implementation

For sake of simplicity I’ll just implement is_detected rather than all of the entities which the Lib Fundamentals 2 TS provides.

namespace detail {
  template <template <class...> class Trait, class Enabler, class... Args>
  struct is_detected : std::false_type{};

  template <template <class...> class Trait, class... Args>
  struct is_detected<Trait, void_t<Trait<Args...>>, Args...> : std::true_type{};
}

template <template <class...> class Trait, class... Args>
using is_detected = typename detail::is_detected<Trait, void, Args...>::type;

Let’s start with that last alias template. We take a variadic template template parameter (yes really) called Trait and any number of other type template arguments. We forward these to our detail::is_detected helper with an extra void argument which will act as the class=void construct from the previous section on void_t⁴. We then have a primary template which will “return” false as the result of the trait. The magic then happens in the following partial specialization. Trait<Args...>> is evaluated inside void_t. If instantiating Traits with Args... is invalid, then the partial specialization will be SFINAEd out, and if it’s valid, it’ll evaluate to void due to the void_t. This successfully abstracts away the implementation of the detection and allows us to focus on what we want to detect.

That covers it for the detection idiom. This is a handy utility for clearing up some hairy metaprogramming, and is even more useful since it can be implemented in old versions of the standard. Let me know if there are any other parts of the code you’d like explained down in the comments or on Twitter. If you want some more resources on the detection idiom, you might want to watch the conference talks given by Walter Brown^{5 6}, Marshall Clow^{7 8}, and Isabella Muerte⁹.

Simon Brand from Simon Brand

C++ is one of the most powerful programming languages in the world. However, it can also be one of the most daunting for beginners. There is so much to learn, so many corner cases, so many little languages within the language itself, that mastering it can seem an insurmountable task. Fortunately, it’s not quite as impossible as it looks. This post outlines some resources and advice for learning C++ today. Some of these also will be useful for those who have used C++ in the past and want to get familiar with modern C++, which is like an entirely different language.

If you want to learn C++ from scratch, don’t rely on random online tutorials. Get a good book. One of these. I read the entirety of Accelerated C++ the day before the interview for my current job, and it was enough to get stuck in to real C++ development. It’s a bit outdated now, (i.e. it doesn’t cover C++11/14/17) but is easily the most important book in my career development. The Effective C++ series by Scott Meyers should be mandatory reading for C++ developers, particularly Effective Modern C++, which is the go-to introduction to C++11 and 14. If you prefer online resources, use reputable ones like Kate Gregory’s Pluralsight courses rather than whatever Google throws out. There are a lot of terrible C++ tutorials out there which will only harm you. A good rule of thumb: if you see #include <iostream.h>, run¹.

However, no matter how much you read, you need to practice in order to improve. I find it helpful to have a mix of small, self-contained problems to try out new techniques, and larger applications to make sure you can use those ideas in a real-world context. Kind of like unit tests and integration tests for your programming skills; can you use these ideas in isolation, and can you fit them together into something comprehensible and maintainable.

Stack Overflow is a great source of skill unit tests. I learned most of my initial metaprogramming knowledge by answering Stack Overflow questions incorrectly and having people tell me why I was wrong. Unfortunately it can be an unforgiving community, and isn’t friendly to very simple questions. Be sure to read through the rules thoroughly before contributing, and feel free to send me an answer you were going to post to get feedback on it if you’re worried!

For skill integration tests, I’d recommend coming up with an application in a domain you’re interested in and trying to develop it from start to finish. If you haven’t done much of this kind of thing before, it can be a daunting task. The main piece of advice I have on this is to ensure your application has a strict scope so that you always know what you’re aiming towards and when you’re finished. Set a number of checkpoints or milestones so that you have explicit tasks to work on and don’t get lost. Some ideas for fun projects:

• A compiler for a simple C subset
• A mini text editor
• Implement some simplified standard library classes, like std::vector
• A clone of a simple video game like Snake
• An ELF file manipulation tool

One of the most valuable knowledge sources is a good C++ community to be part of. Find out if your city or a nearby one has a User Group and go along to meet other developers. They might even have a mentorship program or advice channels for people learning the language. Definitely get on to the C++ Slack Channel and lurk, ask questions, join in discussions. Many of the foremost C++ experts in the world hang out there, and it’s also a very friendly and welcoming environment to those learning. There are even dedicated subchannels for those learning or having problems debugging C++.

Don’t be discouraged when you find things difficult, and, trust me, you will. C++ is hard, and even the experts get things wrong, or can’t even agree on what’s right.

C++ was invented primarily to teach humility to humans. https://t.co/ejZKeu32O3

— Andy Balaam (@andybalaam) July 28, 2017

If you do get good, pass on the knowledge. Start a blog, give advice, mentor those who need it, talk at conferences. You do not need to be an expert to do these things, and we need more speakers and writers from a diverse set of experience levels, as well as in background, race, gender, sexuality. The major C++ conferences all have codes of conduct and organisers who care about these issues. Many of them also have student or accessibility tickets available for those who need further assistance to attend. If in doubt, just ask the organisers, or drop me a message and I can get in touch with the relevant people.

Finally, find some good, regular blogs to learn from. Here are some I would recommend:

• Eli Bendersky — The Green Place
• Jonathan Boccara — Fluent C++
• Bartlomiej Filipek — Bartek’s coding blog
• Stephanie Hurlburt — Blog
• KrzaQ — /dev/krzaq
• Arne Mertz — Simplify C++
• Jonathan Müller — foonathan::blog()
• Vittorio Romeo — Personal website
• Filip Roséen — b.atch.se
• Adi Shavit — Video Cortex
• Jason Turner — C++ Weekly

I hope that this post helps you in your journey to learn C++. It’s a long, but very rewarding path, with a lot of wonderful people to meet, work with, and debate metaprogramming techniques with along the way.