Concepts — case studies

This post has been inspired by the readers’ questions about using concepts to solve real problems. We will have a look at two such problems and see if, and how, concepts can help.

Case Study 1

My concept has two functions: one produces a value, and the other one later consumes this value:

template <typename T>
void test(T& encoder, span<byte> buffer)
{
  auto state = encoder.init();
  // do something with state
  encoder.encode(state, buffer);
}

How to reflect in a concept that the result of init() is a type that can be later passed to encode()?

A simple way to do it would be to put a combined expression as one of the concept requirements:

template <typename E>
concept Encoder = requires(E& e, span<byte> b)
{
  e.encode(e.init(), b);
};

But this has limitations. First, if our concept has two “init” functions init_1() and init_2() producing the value of the same type, and two “encode” functions encode_1() and encode_2() consuming the value of the same type, we will need a lot of combined expressions to reflect all the combinations.

Second, if function encode() modifies the state of the object in-place, and its argument type is an lvalue reference to non-const, such combined expression is actually ill-formed.

A solution to this problem employed in the STL is to additionally require in the concept that a constrained type provides a nested type alias that names the type in question: even if no algorithm actually uses this type.

template <typename E>
concept Encoder = requires(E& e, 
                           typename E::state_t& s,
                           span<byte> b)
{
  { e.init() } -> std::convertible_to<typename E::state_t>;
  e.encode(s, b);
};

Note that I have expressed the nested type requirement in an unusual way. It is not a separate declaration ending with a semicolon: it is in the “argument list” of the requires-expression. This makes the definition shorter, but this was not the reason. I needed to introduce the name s so that I can use it in the description of member function encode(). Otherwise, I would have to resort to solutions that look quite complicated:

template <typename E>
concept Encoder = requires(E& e)
{
  typename E::state_t;
  { e.init() } -> std::convertible_to<typename E::state_t>;
}
&& requires(E& e, 
            typename E::state_t& s,
            span<byte> b)
{
   e.encode(s, b);
};

This perfectly illustrates that requires-expression is just an expression, so you can combine it with other expressions. Token && is a conjunction operator — rather than a logical-or — and has the special compile-time short-circuiting properties. Another alternative:

template <typename E>
concept Encoder = requires(E& e)
{
  typename E::state_t;
  { e.init() } -> std::convertible_to<typename E::state_t>;

  requires requires(typename E::state_t& s,
                    span<byte> b)
  {
    e.encode(s, b);
  };
};

This is a nested requirement and uses the peculiar requires requires syntax. Another alternative uses std::declval:

template <typename E>
concept Encoder = requires(E& e, span<byte> b)
{
  typename E::state_t;
  { e.init() } -> std::convertible_to<typename E::state_t>;
  e.encode(std::declval<typename E::state_t&>(), b);
};

Which illustrates that arguments in requires-expression is just a syntactic sugar over what you can already do with std::declval. Similarly, we could substitute std::declval<E&>() for e in all the above examples, but using an argument name makes the declarations easier to read.

Anyway, in all these examples, including the first one, we have to repeat the typename E::state_t. This is a known inconvenience in C++20 concepts, and solutions are explored to resolve this problem in the future version of C++.

Case Study 2

In the above example, we were using a buffer of type std::span<std::byte>. Let’s change our concept a bit, and say that a type models concept Encoder if it has function encode that works with any type modelling concept Buffer. How do we do that? We could write something like this:

template <typename E, typename B>
concept Encoder = 
  Buffer<B> &&
  requires(E& e, typename E::state_t& s, B b)
{
  { e.init() } -> std::convertible_to<typename E::state_t>;
  e.encode(s, b);
};

This would compile, and could be used to check if a given encoder works with a given buffer, but this is not what we wanted. We want to check if an encoder can encode any type modelling concept Buffer.

Unfortunately, there is no way to do it. And this is not an omission in the concepts syntax. While this need occurs from time to time when we are doing template meta-programming, it is not in scope of what we call Generic Programming. In order to test if a given type (or set of types) satisfies a concept, we have to provide concrete types, and see if all the necessary declarations are present. Checking if a type satisfies a concept is similar to instantiating a template (although no template instantiation actually takes place).
If we have an encoder class:

struct MyEncoder
{
  using state_t = std::size_t;
  state_t init();
  void encode(state_t& s, span<byte> buf);
};

We can pass it to our concept, and it can test that all expressions are there, by substituting MyEncode for the template parameter E in concept Encoder:

static_assert(Encoder<MyEncoder>);

And once we do it, all types are known and concrete: there is no template anymore. We could test if our encoder works with one buffer type, or another buffer type, but there is no way a compiler can check — using template parameter substitution — if the encoder works with all possible types modelling concept Buffer that were ever defined or are yet to be defined. This would require an infinite number of tests. This is somewhat similar to virtual function templates: we do not have them, because it would require virtual tables of infinite sizes: one slot per any combination of function arguments’ types.

---

And that’s it for today. For the end, if you like to learn from videos, the organizers of C++Now offered me an opportunity to give a talk about practical aspects of concepts, based on the posts from this blog. You can watch it here.