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.

Posted in programming | Tagged , , | Leave a comment

Decent concepts

Last year I published two posts on writing concepts:

  1. Concept Archetypes,
  2. Semantic requirements in concepts.

Having had some time to reflect upon these posts, I now realize that the model presented in them is not complete. In this post I want to give a more coherent view of concepts.

In this post we will see that:

  1. Duck-typing property cannot be relied upon for the majority of concepts;
  2. “Additional requirements” when specializing algorithms have to be reflected through concept refinement;

Continue reading

Posted in programming | Tagged , , , | 1 Comment

Contracts, Preconditions & Invariants

In this post we will see what a contract is, how preconditions and invariants can be derived from the contract, and how this process can help detect bugs. Two points that I will be stressing in this post are: (1) preconditions and invariants are not “contracts” and (2) only a subset of contract-related bugs can be detected through preconditions and invariants. Continue reading

Posted in programming | Tagged , , | Leave a comment

Semantic requirements in concepts

The word ‘concept’ in the context of C++ generic programming has two meanings. The first is more abstract: it is the notion from the domain of Generic Programming (GP) in general. GP is not tied to any specific language: it is an approach to writing programs, and concepts are part of this approach. In this sense concepts have been with us since the inception of the STL. The second meaning is the keyword concept in C++20 with its associated semantics: its goal is to approximate the more abstract notion of a concept from GP, and this works only to some extent. One notable difference is that concepts in GP specify semantic requirements on types they constrain, and C++ concepts cannot express them directly.

In this post we will see how semantic requirements in concepts can break your program if you don’t pay attention to them, and what can be done in C++20 concepts to account for semantic requirements. Continue reading

Posted in programming | Tagged , , , | 8 Comments

Reflection for aggregates

An aggregate is an array or a class with

  • no user-declared or inherited constructors,
  • no private or protected direct non-static data members,
  • no virtual functions, and
  • no virtual, private, or protected base classes.

Aggregates can be initialized in aggregate initialization, and, for most cases, decomposed in a structured binding:

struct Point { int x, y; }; // aggregate

Point pt = {1, 2};          // aggregate init
auto const& [x, y] = pt;    // decomposition

Aggregate classes (that is, not arrays) in some aspects are close to tuples, except that their members have meaningful names. However, unlike tuples, you cannot access their members by index.

In this post we will see how to provide an index-based access to aggregate members and write a “for-each” loop that iterates over all members of a given aggregate type. We will also have a look at PFR (Precise and Flat Reflection) library which implements this already. Continue reading

Posted in programming | Tagged , , | 1 Comment

Concept archetypes — update

An observant reader indicated that in the previous post where I was trying to implement a concept archetype — a type with minimal interface that models a given concept — I actually failed. This deserves a closer examination. Continue reading

Posted in programming | Tagged , , | 7 Comments

Concept archetypes

Concepts in the form added in C++20 used to be called lite. This is because they do not provide one quite important functionality: having the compiler check if the author of a constrained template is only using operations and types allowed by the constraining concept. In other words, we can say that our template only requires operations A and B to be valid, but we can still use some other operations inside and this is fine with the compiler. In this post we will show how this is problematic, even for programmers aware of the issue, and how to address it with concept archetypes. Continue reading

Posted in programming | Tagged , , | 13 Comments

Ordering by constraints

In the previous post we have seen how constraint conjunction and disjunction works, and how a function template with constraints is a better match than a function template without constraints (provided that the constraints are satisfied) when determining the best overload. We have also mentioned that selecting a better match from two constrained templates is possible, but not obvious. In this post we will expand on this, and show how constraint conjunction and disjunction as well as concepts play an important role in ordering function overloads and class template specializations based solely on constraints. This is one of the situations where language concepts show their special properties. Continue reading

Posted in programming | Tagged , , , | 8 Comments

Requires-clause — updated

The previous post, “Requires-clause”, contained incorrect information about parentheses inside a requires-clause. Token || inside parentheses is still interpretted as a disjunction of two constraints. I apologize for misleading the readers. I also want to thank James Pfeffer for bringing this error to my attention. The post has now been corrected. You might wish to re-read section Conjunction and Disjunction.

Posted in programming | Tagged , , , | 2 Comments