Be consistent about explicitly requiring typename constraints

CaseyCarter commented 7 years ago

...in concept definitions. This came up in LWG Kona discussion of D0541R1's definition of Assignable:

template <class T, class U>
concept bool Assignable() {
  return is_lvalue_reference<T>::value && // see below
    CommonReference<
      const remove_reference_t<T>&,
      const remove_reference_t<U>&>() &&
    requires(T t, U&& u) {
      { t = std::forward<U>(u) } -> Same<T>&&;
    };
}

which forms const remove_reference_t<U>& without any assurance that type is valid (U could be void, for example). In many other places, e.g. Readable, we explicitly require the validity of types despite that substitution failure will handle an ill-formed type similarly. We need to consistently choose one or the other, or at least develop a guideline for when we use which approach.

Proposed Resolution

There are a great many issues in flight that alter the definitions of concepts in the TS, so it is not possible to list specific and detailed changes here without creating conflicts. We therefore propose application of the guideline developed later in this issue thread to the requires clauses - and particularly those that appear in concept definitions - in the TS. The application of that guideline can be summarized as:

Formation of types that can potentially fail shall occur only in a requires-expression; any requirements including a potentially failing type formation outside of a requires-expression should be transformed into nested requirements within a requires-expression.
the first potentially failing formation of a type shall be in a typename requirement for the type formed

This transformation should be sufficiently mechanical to be applied by the project editor without more detailed instruction. Note that the order of requirements in a requires clause is significant, so care should be taken not to reorder any requirements when applying this transformation.

CaseyCarter commented 7 years ago

Detailed Analysis

This program:

template<class T> using alias = typename T::type;

template<class> void foo() {}

template<class T>
concept bool C = requires {
    typename alias<T>;
    foo<alias<T>>();
};

void bar(C) {}

struct S { using type = int; };

int main() { bar(S{}); }

is well-formed c++ with Concepts. If we remove the declaration using type = int; from S the compiler diagnoses:

prog.cc: In function 'int main()':
prog.cc:15:21: error: cannot call function 'void bar(auto:1) [with auto:1 = S]'
 int main() { bar(S{}); }
                     ^
prog.cc:11:6: note:   constraints not satisfied
 void bar(C) {}
      ^~~
prog.cc:6:14: note: within 'template<class T> concept const bool C<T> [with T = S]'
 concept bool C = requires {
              ^
prog.cc:6:14: note: the required type 'alias<T>' would be ill-formed
prog.cc:6:14: note: the required expression 'foo<alias<T> >()' would be ill-formed

If we further remove typename alias<T>; from the definition of concept C:

prog.cc: In function 'int main()':
prog.cc:14:21: error: cannot call function 'void bar(auto:1) [with auto:1 = S]'
 int main() { bar(S{}); }
                     ^
prog.cc:10:6: note:   constraints not satisfied
 void bar(C) {}
      ^~~
prog.cc:6:14: note: within 'template<class T> concept const bool C<T> [with T = S]'
 concept bool C = requires {
              ^
prog.cc:6:14: note: the required expression 'foo<alias<T> >()' would be ill-formed

Note that the only difference in the sets of diagnostics is that the first includes the line:

prog.cc:6:14: note: the required type 'alias<T>' would be ill-formed

and the second does not. Although the standard does not constrain the form of diagnostics issued by implementations, it seems likely that other implementations of Concepts will handle these examples similarly: if the first unsatisfied requirement listed in a concept definition is a typename requirement, an indication of that dissatisfaction will appear early in the diagnostic. Calling the user's attention to the fact that formation of a typename is ill-formed is a much more specific diagnostic than "this enormous expression which includes the typename (and likely several others) is ill-formed" and hence likely to help the user solve the problem more quickly.

template<class T>
using alias = typename T::type;

template<class>
concept bool C1 = true;

template<class T>
concept bool C2 = C1<alias<T>>;

void bar(C2) {}

struct S { using type = int; };

int main() { bar(S{}); }

If we again remove using type = int; from the body of S:

prog.cc: In function 'int main()':
prog.cc:14:21: error: cannot call function 'void bar(auto:1) [with auto:1 = S]'
 int main() { bar(S{}); }
                     ^
prog.cc:10:6: note:   constraints not satisfied
 void bar(C2) {}
      ^~~
prog.cc:10:6: note: in the expansion of concept 'C2<auto:1>' template<class T> concept const bool C2<T> [with T = S]

(Yes, that is the entire diagnostic.) The diagnostic - which is so poor as to deserve a bug report - doesn't mention alias<T> at all. Maybe we can fix the problem by changing the body of C2 to requires { typename alias<T>; } && C1<alias<T>>:

prog.cc: In function 'int main()':
prog.cc:14:21: error: cannot call function 'void bar(auto:1) [with auto:1 = S]'
 int main() { bar(S{}); }
                     ^
prog.cc:10:6: note:   constraints not satisfied
 void bar(C2) {}
      ^~~
prog.cc:10:6: note: in the expansion of concept 'C2<auto:1>' template<class T> concept const bool C2<T> [with T = S]

Nope - exactly the same partial diagnostic. How about nesting the C1 requirement inside the requires expression a la requires { typename alias<T>; requires C1<alias<T>>; }:

prog.cc: In function 'int main()':
prog.cc:14:21: error: cannot call function 'void bar(auto:1) [with auto:1 = S]'
 int main() { bar(S{}); }
                     ^
prog.cc:10:6: note:   constraints not satisfied
 void bar(C2) {}
      ^~~
prog.cc:8:14: note: within 'template<class T> concept const bool C2<T> [with T = S]'
 concept bool C2 = requires { typename alias<T>; requires C1<alias<T>>; };
              ^~
prog.cc:8:14: note: the required type 'alias<T>' would be ill-formed
prog.cc:14:21: note: ill-formed constraint
 int main() { bar(S{}); }
                     ^

This finally achieves a helpful (complete) diagnostic. It would appear that if we want to define concepts that provide useful error messages to users we must pay careful attention to how we go about the formation of new types.

We can use the lessons learned here to establish a guideline: when formation of a type in a requires clause or requires expression can potentially fail, the first formation of that type should be in a typename requirement and other references to that type should appear within the same requires-expression as that typename requirement. Consequently, occurrences that appear directly in a requires clause as concept parameters, as in the earlier example:

template<class T>
concept bool C2 = C1<alias<T>>;

will need to reformulate that occurrence as a nested requirement within the requires expression where the newly introduced typename requirement appears:

template<class T>
concept bool C2 = requires {
  typename alias<T>;
  requires C1<alias<T>>;
};

The reasoning we used to devise this guideline relies partly on the behavior of a specific implementation - granted it is currently the only implementation - so it may need to be reconsidered in the future as new implementations appear or as the GCC implementation is revised. For now, this approach provides the highest quality error messages.

As an example, we can apply this guideline to the reformulation of the Ranges TS CommonReference concept presented in the proposed resolution of issue #311:

template <class T, class U>
concept bool CommonReference() {
  return
    Same<common_reference_t<T, U>, common_reference_t<U, T>>() &&
    ConvertibleTo<T, common_reference_t<T, U>>() &&
    ConvertibleTo<U, common_reference_t<T, U>>();
}

Note that the types common_reference_t<T, U> and common_reference_t<U, T> are first formed as parameters for the Same requirement outside of any requires-expression. As expected, diagnostics are poor if the formation of those types fails:

CommonReference{T, U}
void f(T, U) {}

int main() {
    struct S {};
    f(42, S{});
}

produces diagnostics:

prog.cc: In function 'int main()':
prog.cc:28:14: error: cannot call function 'void f(T, U) [with T = int; U = main()::S]'
     f(42, S{});
              ^
prog.cc:24:6: note:   constraints not satisfied
 void f(T, U) {}
      ^
prog.cc:24:6: note: in the expansion of concept '(CommonReference<T, U>)()' template<class T, class U> concept bool CommonReference() [with T = int; U = main()::S]

Application of the guideline above results in the concept definition:

template <class T, class U>
concept bool CommonReference() {
  return requires {
    typename common_reference_t<T, U>;
    typename common_reference_t<U, T>;
    requires Same<common_reference_t<T, U>, common_reference_t<U, T>>() &&
      ConvertibleTo<T, common_reference_t<T, U>>() &&
      ConvertibleTo<U, common_reference_t<T, U>>();
  };
}

which produces high quality diagnostics as expected:

prog.cc: In function 'int main()':
prog.cc:31:12: error: cannot call function 'void f(T, U) [with T = int; U = main()::S]'
   f(42, S{});
            ^
prog.cc:27:6: note:   constraints not satisfied
 void f(T, U) {}
      ^
prog.cc:16:14: note: within 'template<class T, class U> concept bool CommonReference() [with T = int; U = main()::S]'
 concept bool CommonReference() {
              ^~~~~~~~~~~~~~~
prog.cc:16:14: note: the required type 'common_reference_t<T, U>' would be ill-formed
prog.cc:16:14: note: the required type 'common_reference_t<U, T>' would be ill-formed
prog.cc:31:12: note: ill-formed constraint
   f(42, S{});
            ^

Note that one could equivalently break apart the conjunction in the newly introduced nested requirement into multiple nested requirements:

template <class T, class U>
concept bool CommonReference() {
  return requires {
    typename common_reference_t<T, U>;
    typename common_reference_t<U, T>;
    requires Same<common_reference_t<T, U>, common_reference_t<U, T>>();
    requires ConvertibleTo<T, common_reference_t<T, U>>();
    requires ConvertibleTo<U, common_reference_t<T, U>>();
  };
}

This causes GCC to emit an additional "note: ill-formed constraint" diagnostic for each failing nested requirement when the typename formation fails:

prog.cc: In function 'int main()':
prog.cc:34:12: error: cannot call function 'void f(T, U) [with T = int; U = main()::S]'
   f(42, S{});
            ^
prog.cc:30:6: note:   constraints not satisfied
 void f(T, U) {}
      ^
prog.cc:19:14: note: within 'template<class T, class U> concept bool CommonReference() [with T = int; U = main()::S]'
 concept bool CommonReference() {
              ^~~~~~~~~~~~~~~
prog.cc:19:14: note: the required type 'common_reference_t<T, U>' would be ill-formed
prog.cc:19:14: note: the required type 'common_reference_t<U, T>' would be ill-formed
prog.cc:34:12: note: ill-formed constraint
   f(42, S{});
            ^
prog.cc:34:12: note: ill-formed constraint
prog.cc:34:12: note: ill-formed constraint

So we do not recommend this transformation at this time.

For users of the Ranges TS to get the highest quality compiler diagnostics from constraint violations in the current implementation environment, we should apply the guideline developed herein to all of the requires-clauses in the TS.

CaseyCarter commented 7 years ago

@ericniebler Any thoughts on the guideline / proposed resolution? I intend to review the requires-clauses - along with my review for #230 - to ensure that application of the proposed guideline is in fact straight-forward.

ericniebler commented 7 years ago

Very nice work, thanks. When applying this guideline, you should take care not to reorder any existing constraints. As we've learned, that can be a breaking change.

CaseyCarter commented 7 years ago

When applying this guideline, you should take care not to reorder any existing constraints. As we've learned, that can be a breaking change.

I've added a note to this effect to the PR.

EDIT: For posterity, there are currently a bit more than 500 occurrences of the word "requires" in the TS.

ericniebler commented 5 years ago

It doesn't look like this was ever done, and we're running out of time to respecify the concepts. @CaseyCarter, is this still worth doing?

ericniebler / stl2

Be consistent about explicitly requiring typename constraints #388

Proposed Resolution

Detailed Analysis