C++ Concepts: Subsumption Rules Explained

In C++20, constraints and concepts allow developers to restrict template arguments and overload templates based on type capabilities. When multiple constrained templates match a set of template arguments, the compiler relies on subsumption rules to evaluate which constraint is more specialized. This article explains how constraint normalization works, how subsumption determines when one constraint implies another, and how overload resolution uses these relationships to select the most specific template.

Constraint Normalization

Before the compiler can compare two constraints, it transforms them through a process called normalization. Normalization decomposes complex requirement expressions into logical combinations of atomic constraints.

The normalization process performs the following steps:

  1. Concept Expansion: References to concepts are recursively expanded until only expressions joined by the logical operators && and || remain.
  2. Atomic Constraint Identification: An atomic constraint is an expression evaluated as a boolean value that cannot be further broken down into && or || operations. For example, in requires (sizeof(T) > 4 && std::is_integral_v<T>), the normalization yields two separate atomic constraints: sizeof(T) > 4 and std::is_integral_v<T>.
  3. Form Conversion: Constraints are logically represented as sets of clauses (Conjunctive Normal Form or Disjunctive Normal Form) composed of these atomic constraints.

The Definition of Subsumption

Subsumption is the formal compile-time mechanism used to determine logical implication between normalized constraints. A constraint \(P\) subsumes a constraint \(Q\) if and only if it can be proven that \(P \implies Q\) (P implies Q) under the rules of propositional logic.

The basic rules for subsumption are:

  • A conjunction A && B subsumes A, as well as B. If both A and B are true, A must inherently be true.
  • An atomic constraint A subsumes a disjunction A || B. If A is true, the compound expression A || B is satisfied.
  • Two identical atomic constraints subsume each other.

For a compound constraint \(P\) to subsume \(Q\), every clause in the normalized form of \(Q\) must be satisfied by the conditions provided by \(P\).

The Identity of Atomic Constraints

A critical aspect of subsumption is atomic constraint identity. Two atomic constraints are considered identical if and only if they originate from the exact same syntactic expression in the source code and have identical template parameter mappings.

Consider the following example:

template <typename T>
concept Signed = std::is_signed_v<T>;

template <typename T>
concept SignedInt = std::is_signed_v<T> && std::is_integral_v<T>;

In this case, SignedInt<T> subsumes Signed<T> because both reference the exact same underlying concept expression, allowing the compiler to recognize std::is_signed_v<T> as the same atomic constraint.

Conversely, if constraints use raw expressions rather than shared concepts:

template <typename T> requires (sizeof(T) > 4)
void process(T);

template <typename T> requires (sizeof(T) > 4 && std::is_integral_v<T>)
void process(T);

Even though sizeof(T) > 4 appears in both declarations, they are separate syntactic entities. Because they are not defined within the same concept, the compiler treats them as distinct atomic constraints. As a result, the second overload does not subsume the first, causing an ambiguous call error during compilation.

Overload Resolution and Specificity

During overload resolution, candidate function templates are ranked based on viability. When multiple templates with different constraints are viable for a given set of arguments:

  1. The compiler checks if constraint \(P\) of the first candidate subsumes constraint \(Q\) of the second candidate.
  2. The compiler checks if constraint \(Q\) subsumes constraint \(P\).
  3. If \(P\) subsumes \(Q\), but \(Q\) does not subsume \(P\), then \(P\) is deemed more constrained (more specific) than \(Q\).

The candidate with the more constrained requirement is chosen as the best match. If neither constraint subsumes the other, or if both subsume each other without other tie-breaking factors (such as non-template functions or standard conversion sequences), the call is flagged as ambiguous.