C++20 Concepts: Constraint Normalization

This is an example from the C++20 Standard (ISO/IEC 14882:2020), Section 13.5.4 ([temp.constr.normal]), Paragraph 1 (emphasis mine):

> The normal form of a concept-id C<A1 , A2 , ..., An> is the normal form of the constraint-expression of C, after substituting A1 , A2 , ..., An for C’s respective template parameters in the parameter mappings in each atomic constraint. If any such substitution results in an invalid type or expression, the program is ill-formed; no diagnostic is required.

template<typename T> concept A = T::value || true;
template<typename U> concept B = A<U*>;
template<typename V> concept C = B<V&>;

> Normalization of B’s constraint-expression is valid and results in T::value (with the mapping T -> U*) V true (with an empty mapping), despite the expression T::value being ill-formed for a pointer type T. Normalization of C’s constraint-expression results in the program being ill-formed, because it would form the invalid type V&* in the parameter mapping.

I understand that C makes a program ill-formed (and why). However, it is not clear to me if B would result in the program being ill-formed or not. The text states that B's normalization is valid, but at the same time it states that the expression T::value is ill-formed due to that pointer type (which I understand). Does it mean that only the normalization part of the process is valid but the program itself is ill-formed in a later stage when checking T::value? Or is the program valid in any case and the check of T::value is skipped/avoided somehow?

I checked with Godbolt's Compiler Explorer and both GCC and Clang seem to be fine with this. Nevertheless, since the Standard says "no diagnostic is required", this does not help much.

The concept B is valid, as you can pass a pointer to the concept A. Inside A itself the pointer cannot access ::value but this, according to the spec, [temp.constr.atomic], would not be considered as an error but rather as false, then the || true on concept A would make the entire expression true.

Note that if we pass int& to concept B then our code would be IFNDR, as B would try to pass to A an invalid type (int&*).

The concept C is IFNDR as is, since it passes a reference to B, that tries to pass a pointer to this reference to A, and again a V&* type is invalid.

Trying to evaluate an ill-formed-no-diagnostic-required expression using static_assert will not necessarily help in answering the question whether the expression is valid or not, as the compiler is not required to fail a static_assert on an ill-formed-no-diagnostic-required expression.

Note that each normalized constraint consists out of 2 parts:
The atomic constraint and an associated parameter mapping.

Let's separate each constraint into those two parts for your three example concepts:

In your example the normalized form of concept A would be the disjunction of these two constraints:

• Atomic expression: X::value
  Parameter Mapping: X ↦ T
• Atomic expression: true
  No Parameter Mapping

The normalized form of concept B would be the disjunction of these two constraints:

• Atomic expression: X::value
  Parameter Mapping: X ↦ U*
• Atomic expression: true
  No Parameter Mapping

And the normalized form of concept C would be the disjunction of these two constraints:

• Atomic expression: X::value
  Parameter Mapping: X ↦ V&*
• Atomic expression: true
  No Parameter Mapping

How the parameter mappings get formed

Forming the parameter mapping for an atomic expression is straightforward:

By default an atomic expression always starts out with an identity parameter mapping (i.e. no type modifications):
> 13.5.4 Constraint normalization [[temp.constr.normal]]
> ⁽¹⁾ The normal form of an expression E is a constraint that is defined as follows:
> [...]
> ^(1.5) The normal form of any other expression E is the atomic constraint whose expression is E and whose parameter mapping is the identity mapping.

and the only way to get a non-identity parameter mapping is to name another concept within the constraint:
> 13.5.4 Constraint normalization [[temp.constr.normal]]
> ^(1.4) The normal form of a concept-id C<A1, A2, ..., An> is the normal form of the constraint-expression of C, after substituting A1, A2, ..., An for C's respective template parameters in the parameter mappings in each atomic constraint. [...]

Here are a few examples:

template<class T> constexpr bool always_true = true;

// Atomic constraint: always_true<X>
// Parameter mapping: X ↦ T (identity)
template<class T> concept Base = always_true<T>;

// Atomic constraint: always_true<X>
// Parameter mapping: X ↦ U (identity) 
template<class U> concept Foo = Base<U>;

// Atomic constraint: always_true<X>
// Parameter mapping: X ↦ V::type
template<class V> concept Bar = Base<typename V::type>;

// Atomic constraint: always_true<X>
// Parameter mapping: X ↦ W&&
template<class W> concept Baz = Base<W&&>;

Your quoted section

Which brings us back to your original quoted section:
> 13.5.4 Constraint normalization [[temp.constr.normal]]
> ^(1.4) The normal form of a concept-id C<A1, A2, ..., An> is the normal form of the constraint-expression of C, after substituting A1, A2, ..., An for C's respective template parameters in the parameter mappings in each atomic constraint. If any such substitution results in an invalid type or expression, the program is ill-formed; no diagnostic is required.

Note that the highlighted statement only applies to the parameter mapping - not to the atomic expression itself.

This is why concept C in your example is ill-formed, NDR - because the parameter mapping for its atomic expressions forms an invalid type (pointer to reference): X ↦ V&*

Note that the actual type that gets substituted for V does not matter at the normalization stage; the only thing that matters is if the mapping itself forms an invalid type or expression.

Here are a few more examples:

template<class T> constexpr bool always_true = true;

// well-formed
// Atomic constraint: always_true<X>
// Parameter mapping: X ↦ T (identity)
template<class T> concept Base = always_true<T>;

// well-formed
// Atomic constraint: always_true<X>
// Parameter mapping: X ↦ U::type
template<class U> concept Foo = Base<typename U::type>;

// ill-formed, ndr (invalid parameter mapping)
// Atomic constraint: always_true<X>
// Parameter mapping: X ↦ V*::type
template<class V> concept Bar = Foo<V*>;

// ill-formed, ndr (invalid parameter mapping)
// Atomic constraint: always_true<X>
// Parameter mapping: X ↦ W&*
template<class W> concept Baz = Foo<W&>;

Rough Timeline of events during compilation

To answer the question of when your program gets ill-formed ndr, we need to establish the order in which events take place during compilation.

• When the constraints of an associated declaration are determined OR the value of a concept is evaluated then constraint normalization will take place.
  This is given by:
  > 13.5.4 Constraint normalization [[temp.constr.normal]]
  > ^{[Note 1]} Normalization of constraint-expressions is performed when determining the associated constraints of a declaration and when evaluating the value of an id-expression that names a concept specialization.

  This is where your program would become ill-formed, ndr if the parameter mapping forms an invalid type or expression.

• After the constraints have been normalized the actual type will be substituted into the constraints:
  > 13.5.2.3 Atomic constraints [[temp.constr.atomic]]
  > ⁽³⁾ To determine if an atomic constraint is satisfied, the parameter mapping and template arguments are first substituted into its expression. If substitution results in an invalid type or expression, the constraint is not satisfied.

  Note that at this point it is allowed for invalid types or expression to be formed - if that's the case then the result of the constraint will simply be false.

Conclusion

So to answer your questions:

• > Does it mean that only the normalization part of the process is valid but the program itself is ill-formed in a later stage when checking T::value?

  Concepts A and B are well-formed.
  Concept C is ill-formed, ndr during the normalization process.
  The actual atomic constraint T::value does not matter in this case; it could as well simply be always_true<T>.

• > Or is the program valid in any case and the check of T::value is skipped/avoided somehow?

  The program is valid as long as concept C never gets normalized.
  i.e. explicitly evaluating it or using it as a constraint would make your program ill-formed, ndr.

  Example:

  // evaluates concept C
  //   -> results in normalization of C
  //   -> ill-formed, ndr
  static_assert(C</* something */>); 
  
  template<C T>
  void foo() {}
  
  // constraints of foo will be determined
  //   -> results in normalization of C
  //   -> ill-formed, ndr
  foo</* something */>();