Refining Concepts: Separate checking, part 1, relaxing constraints

September 18th, 2016

In Why Concepts didn’t make C++17 [Twitter] [Reddit], I summarized a number of technical concerns that were raised during the C++ standard committee meeting in Jacksonville in March, 2016. In this next series of posts, I’ll be discussing #6 on that list; separate checking of constrained template definitions.

I’ve been reviewing some of the original Concepts proposal papers [N1510] [N1522] [N1536] dating back to 2003 and have been struck by two observations.  1) How true the current Concepts proposal is to those original proposals, and 2) How much those original proposals emphasized the benefits of separate checking.  After re-reading these, it feels to me that gaining Concepts as currently proposed will have lost much of the promise of these initial papers if support for separate checking never arrives.

A quick refresher: separate checking refers to the ability of the compiler to concept check a constrained template definition, without concrete template arguments, to validate that the template definition does not make use of template parameters in a way that violates the declared constraints.  Ideally, a fully constrained template definition that the compiler has successfully concept checked would be guaranteed not to fail type checking when instantiated with any set of template arguments that satisfy the declared constraints.

The C++0x Concepts proposal included separate checking.  Ultimately, that proposal failed to reach consensus due to usability and implementability (primarily performance) concerns and, after enjoying a brief stint as an accepted feature of C++0x, was withdrawn before C++11 shipped.  A number of papers and articles have been written about the challenges with the C++0x proposal.  Of the ones I’ve read, I’ve found N2906 [N2906] and an article in Dr. Dobb’s by Bjarne Stroustrup [Dr.Dobb’s] to be the most informative.

One of the separate checking concerns that is often raised is how to grant implementation freedom to constrained template authors to allow for template argument dependent debugging, logging, tracing, telemetry, caching, etc… without having to pollute the constraint declarations of the template interface with requirements specific to the implementation of those facilities.  This issue was raised again in an email thread [SG8-Concepts] on the SG8 Concepts reflector just prior to the Jacksonville meeting in response to Matt Calabrese’s paper [P0240R0].  As an example, consider a hypothetical implementation of std::copy that supports a debug mode enabling validation that the input range provided is a valid range; that last is reachable from first:

    template<InputIterator II, OutputIterator OI>
    OI copy(II first, II last, OI result) {
    #if DEBUG_MODE_ENABLED
      validate_range(first, last);
    #endif
      ...
    }

The call to validate_range is not supported by the InputIterator requirements, so this implementation would presumably fail a concept check when compiled with debug mode enabled (depending on how strict definition checking is and how validate_range is defined).  The C++0x Concepts proposal [N2773] included support for suspending concept checking at the block level via the late_check statement in order to support cases like this.  I was not present for any of the C++0x Concepts discussions, but my understanding is that late_check was rather unloved given that it existed only to undermine the definition checking that C++0x Concepts was designed to do.  Nevertheless, it was accepted as a necessary evil.   Can we do better?  Could a different design fit more naturally into the current Concepts design?

The approach I favor is one inspired by the C++17 if constexpr feature and independently suggested by myself on the EWG reflector [isocpp-lib-ext] and by Nicol Bolas on the std-proposals list [std-proposals].  The idea is to introduce an if requires statement that enables a template author to relax constraints at a block level based on whether additional requirements are met.  When concept checking a block guarded by an if requires statement, the compiler would proceed as though the additional constraints were appended to the conjunction of associated constraints for the template declaration.  The example above might be adapted to use it as follows.

    template<typename I>
    concept bool SupportsRangeValidation =
      InputIterator<I> &&
      requires (I first, I last) {
        validate_range(first, last);
      };
    
    template<InputIterator II, OutputIterator<value_type_t<II>> OI>
    OI copy(II first, II last, OI result) {
    #if DEBUG_MODE_ENABLED
      if requires(SupportsRangeValidation<II>) {
        validate_range(first, last);
      }
    #endif
     ...
    }

The grammar for this statement would be an addition to selection-statement:

    selection-statement:
      if requires-clause statement
      if requires-clause statement else statement

The use of requires-clause is intended to maintain consistency with constraint declarations, but does mean that adding constraints via a requires expression will require the unfortunate “requires requires” syntax.  Presumably, any solution adopted to address the existing “requires requires” issue would be applicable here as well.

But wait, constrained function templates can be overloaded and partially ordered based on constraint refinement.  Does the following not address the use case above?  Why would we need if requires?

    template<InputIterator II, OutputIterator<value_type_t<II>> OI>
    OI copy(II first, II last, OI result) {
      ...
    }
    
    #if DEBUG_MODE_ENABLED
    template<InputIterator II, OutputIterator<value_type_t<II>> OI>
      requires SupportsRangeValidation<II>
    OI copy(II first, II last, OI result) {
      validate_range(first, last);
      ...
    }
    #endif

The above does work, but I find it deeply unsatisfying as it means the common parts of both implementations must either be duplicated or factored out. Additionally, as discussed in my prior post, the additional overload would contribute to longer error messages and, given that the overload only exists to satisfy implementation details, leaks concerns that users presumably would rather not be bothered with.  This has the feel to me of working around language limitations.  The if requires approach feels like a much more integrated, elegant, and simple solution.

Does if requires suffice to address the needs for escaping constraints?  I don’t think so.  Authors of existing unconstrained templates, may wish to adopt interface constraints as an alternative to std::enable_if, or to improve error messages for users, without having to go through the trouble of defining concepts like SupportsRangeValidation above.  Presumably, their existing templates are working just fine for the types that they are actually instantiated with in practice, even if those templates use expressions that aren’t required by their interface guarantees.  I think it makes sense to support a mechanism to opt out of constraint checks completely in order to enable such adoption.  I favor a requires … statement for these cases as follows.  Note that this is just the C++0x Concepts late_check statement dressed in a different syntax, so all of the objections previously raised against late_check are relevant here as well.

    template<InputIterator II>
    void f(II i) {
      requires … {
        // unconstrained block...
      }
    }

Allowing a requires … statement to wrap a function body like a function-try-block would enable constructor templates to opt out of constraint checking for base class and data member initializers.

    template<InputIterator II>
    my_class(II i)
    requires …
      : i{i} // unconstrained initializers...
    {
      // unconstrained constructor body...
    }

I think if requires and requires … statements suffice to address relaxation of constraints within function templates.  If more fine-grained relaxation is found to be necessary, then the requires … syntax can be extended to enable relaxing constraints on expressions and initializers.  But, what about class, variable, and alias templates? Is there a need to relax constraints for base class specifiers or member function, data member, variable, or alias declarations?  The use cases I’ve come across so far I think can be adequately addressed through class inheritance and partial ordering of constrained explicit specializations, though I admit the refactoring required could be extensive.  The following prototype grammar includes support for fairly fine grained constraint relaxation.  (Note that I’m cheating here by applying opt to the combined requires … token sequence).

    primary-expression:
      requires… expression
    
    selection-statement:
      if requires-clause statement
      if requires-clause statement else statement
    
    compound-statement:
      requires…opt { statement-seqopt }
    
    function-try-block:
      requires…opt try ctor-initializeropt compound-statement handler-seq
    
    alias-declaration:
      using identifier attribute-specifier-seqopt = requires…opt defining-type-id ;
    
    braced-init-list:
      requires…opt { initializer-list ,opt }
      requires…opt { }
    
    class-specifier:
      class-head requires…opt { member-specificationopt } }
    
    base-clause:
      : requires…opt base-specifier-list

The concerns regarding separate checking expressed at the Jacksonville meeting had to do with the ability to provide separate checking as an incremental addition on top of the current Concepts proposal at some future date. With regard to the issues explored in this post, it looks to me like adequate solutions can be provided without requiring changes to the current proposal or compromising code written to it. However, I think there are other issues that are of greater concern. More on that next time.

References:

[N1510] Bjarne Stroustrup, “Concept checking – A more abstract complement to type checking”, N1510, 2003.
http://open-std.org/jtc1/sc22/wg21/docs/papers/2003/n1510.pdf
[N1522] Bjarne Stroustrup and Gabriel Dos Reis, “Concepts – Design choices for template argument checking”, N1522, 2003.
http://open-std.org/jtc1/sc22/wg21/docs/papers/2003/n1522.pdf
[N1536] Bjarne Stroustrup and Gabriel Dos Reis, “Concepts – syntax and composition”, N1536, 2003.
http://open-std.org/jtc1/sc22/wg21/docs/papers/2003/n1536.pdf
[N2773] Douglas Gregor et al., “Proposed Wording for Concepts (Revision 9)”, N2773, 2008.
http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2008/n2773.pdf
[N2906] Bjarne Stroustrup, “Simplifying the use of concepts”, N2906, 2009.
http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2009/n2906.pdf
[P0240R0] Matt Calabrese, “Why I want Concepts, but why they should come later rather than sooner”, P0240R0, 2016.
http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2016/p0240r0.html
[Dr.Dobb’s] Bjarne Stroustrup, “The C++0x “Remove Concepts” Decision”, 2009.
http://www.drdobbs.com/cpp/the-c0x-remove-concepts-decision/218600111
[SG8-Concepts] Faisal Vali et al., “Is there really no path forward for definition checking of templates?”, 2016.
https://groups.google.com/a/isocpp.org/forum/#!msg/concepts/CX3aUunonaI/D6-jtlkfFgAJ
[isocpp-lib-ext] Tom Honermann et al., “constexpr if and concept definition checking”, 2016.
EWG reflector, email thread titled “constexpr if and concept definition checking”, 2016-02-26
[std-proposals] Nicol Bolas, “if requires: the concepts-based if constexpr”, 2016.
https://groups.google.com/a/isocpp.org/forum/#!topic/std-proposals/8KgGLq50RLY

Refining Concepts: Improving error messages

July 18th, 2016

In Why Concepts didn’t make C++17 [Twitter] [Reddit], I summarized a number of technical concerns that were raised during the C++ standard committee meeting in Jacksonville in March, 2016. In this post, I’ll be discussing #5 on that list; error messages.

Producing good diagnostics is an art requiring considerable expertise and persistence.  In the examples that follow, we’ll see some cases where the diagnostics produced are lacking due to quality of implementation (QOI) issues rather than fundamental issues with the design of Concepts.  These QOI issues reflect the maturity of the current implementation, not what could be achieved with more effort.  At the Jacksonville meeting, these QOI issues were cited as evidence for lack of usage experience with Concepts outside of the committee.

The error messages that follow are courtesy of the in-development release of gcc 6.1.1, svn revision 238201.  As noted, below, some of these error messages were produced with a gcc patch applied to provide additional diagnostic information.

First, let’s start with a simple example that does not use concepts.

    template<typename T>
    auto f3(T t) {
        return t.i, t.i;
    }
    template<typename T>
    auto f2(T t) {
        return f3(t);
    }
    template<typename T>
    auto f1(T t) {
        return f2(t);
    }
    struct S {
    };
    auto x = f1(S{});

Compiling with g++ -c -std=c++1z t.cpp produces the following:

    t.cpp: In instantiation of ‘auto f3(T) [with T = S]’:
    t.cpp:7:14:   required from ‘auto f2(T) [with T = S]’
    t.cpp:11:14:   required from ‘auto f1(T) [with T = S]’
    t.cpp:15:16:   required from here
    t.cpp:3:14: error: ‘struct S’ has no member named ‘i’
         return t.i, t.i;
                ~~^
    t.cpp:3:14: error: ‘struct S’ has no member named ‘i’
         return t.i, t.i;
                     ~~^
    t.cpp:15:16: error: ‘void x’ has incomplete type
     auto x = f1(S{});
                    ^

Here we see a familiar template instantiation stack.  The diagnostics produced clearly indicate that instantiation failed because S lacks a data member named i and each expression requiring such a data member is clearly identified.  Now, let’s modify the example to specify constraints using concepts.  In order to keep this example simple, the template definitions are intentionally under constrained.  Kindly over look that detail.

    template<typename T>
    concept bool C = requires(T t) {
        t.i;
    };
    template<C T>
    auto f3(T t) {
        return t.i, t.i;
    }
    template<C T>
    auto f2(T t) {
        return f3(t);
    }
    template<C T>
    auto f1(T t) {
        return f2(t);
    }
    struct S {
    };
    auto x = f1(S{});

Compiling with g++ -c -std=c++1z -fconcepts t.cpp produces the following:

    t.cpp:19:16: error: cannot call function ‘auto f1(T) [with T = S]’
     auto x = f1(S{});
                    ^
    t.cpp:14:6: note: constraints not satisfied
     auto f1(T t) {
          ^~
    t.cpp:14:6: note: concept ‘C<S>’ was not satisfied

The compiler has helpfully informed us that the call to f1 failed because S doesn’t satisfy the constraints required of concept C, but has not provided any information explaining why satisfaction failed.  The lack of such details can make it challenging to determine why a type fails to satisfy a concept.  The problem is somewhat more pronounced if one attempts to validate that a type satisfies a concept via static_assert.

    template<typename T>
    concept bool C = requires(T t) {
        t.i;
    };
    struct S {
    };
    static_assert(C<s>);

Compiling with g++ -c -std=c++1z -fconcepts t.cpp produces the following:

    t.cpp:7:1: error: static assertion failed
     static_assert(C<S>);
     ^~~~~~~~~~~~~

The lack of details in the above error messages are purely due to QOI issues and are tracked by a gcc bug report [GCC bug 71843].  When I raised these issues to Andrew Sutton at the Jacksonville meeting, he provided a gcc patch that he already had available and that can be found attached to that bug report.  With that patch applied, error messages are significantly improved for the example above (not for the static_assert example however).  All of the error messages that follow were produced with that patch applied.

    t.cpp:19:16: error: cannot call function ‘auto f1(T) [with T = S]’
     auto x = f1(S{});
                    ^
    t.cpp:14:6: note: constraints not satisfied
     auto f1(T t) {
          ^~
    t.cpp:14:6: note: concept ‘C<S>’ was not satisfied
    t.cpp:2:14: note: within the concept template<class T> constexpr const bool C<T> [with T = S]
     concept bool C = requires(T t) {
                  ^
    t.cpp:2:14: note: the required expression ‘t.i’ would be ill-formed

Here we see the promise of better error messages as foretold in the first paragraph of the first Concepts paper [N1510] starting to be realized.  There is no template instantiation stack, the error message clearly describes why type s fails to satisfy the constraints of concept C required by f1(), and only one error is emitted instead of one error for each use of the required expression.  Concepts delivers!

Let’s consider what happens in a more complicated scenario.  Partial ordering of constrained function declarations enables an alternative to tag dispatching and std::enable_if tricks that allows writing constrained overloaded functions more naturally than is done today.  The following code presents a simplified example of how std::next() might be declared in a concept enabled standard library.  Note that I’m intentionally omitting real iterator details and, in reality, an implementation would likely only have a single declaration with a definition that dispatches to std::advance(), but bare with me.

    #include <iterator>
    
    // Iterator concepts:
    template<typename T>
    concept bool InputIterator =
        requires(T t) {
            { typename T::iterator_category{} } -> std::input_iterator_tag;
        };
    template<typename T>
    concept bool ForwardIterator =
        InputIterator<T>
        && requires(T t) {
            { typename T::iterator_category{} } -> std::forward_iterator_tag;
        };
    template<typename T>
    concept bool BidirectionalIterator =
        ForwardIterator<T>
        && requires(T t) {
            { typename T::iterator_category{} } -> std::bidirectional_iterator_tag;
        };
    template<typename T>
    concept bool RandomAccessIterator =
        BidirectionalIterator<T>
        && requires(T t) {
            { typename T::iterator_category{} } -> std::random_access_iterator_tag;
        };
    
    // next() declarations:
    template<ForwardIterator T>
    T next(T, typename T::difference_type = 1); // Uses operator++().
    template<BidirectionalIterator T>
    T next(T, typename T::difference_type = 1); // Uses operator++() and operator--().
    template<RandomAccessIterator T>
    T next(T, typename T::difference_type = 1); // Uses operator+=().

Now, let’s look at the errors emitted when next() is called with an input iterator (which should be permitted [LWG 2353], but currently isn’t).

    // An input iterator:
    struct I {
        using iterator_category = std::input_iterator_tag;
        using difference_type = int;
    };
    
    // Oops, can't call next() with an input iterator:
    void f(I i) {
        next(i);
    }

Compiling with g++ -c -std=c++1z -fconcepts t.cpp produces the following:

    t.cpp: In function ‘void f(I)’:
    t.cpp:44:11: error: no matching function for call to ‘next(I&)’
         next(i);
               ^
    t.cpp:30:3: note: candidate: T next(T, typename T::difference_type) [with T = I; typename T::difference_type = int]
     T next(T, typename T::difference_type = 1);
       ^~~~
    t.cpp:30:3: note: constraints not satisfied
    t.cpp:30:3: note: concept ‘ForwardIterator<I>’ was not satisfied
    t.cpp:10:14: note: within the concept template<class T> constexpr const bool ForwardIterator<T> [with T = I]
     concept bool ForwardIterator =
                  ^~~~~~~~~~~~~~~
    t.cpp:10:14: note: ‘I::iterator_category{}’ is not implicitly convertible to ‘std::forward_iterator_tag’
    t.cpp:32:3: note: candidate: T next(T, typename T::difference_type) [with T = I; typename T::difference_type = int]
     T next(T, typename T::difference_type = 1);
       ^~~~
    t.cpp:32:3: note: constraints not satisfied
    t.cpp:32:3: note: concept ‘BidirectionalIterator<I>’ was not satisfied
    t.cpp:16:14: note: within the concept template<class T> constexpr const bool BidirectionalIterator<T> [with T = I]
     concept bool BidirectionalIterator =
                  ^~~~~~~~~~~~~~~~~~~~~
    t.cpp:16:14: note: concept ‘ForwardIterator<I>’ was not satisfied
    t.cpp:10:14: note: within the concept template<class T> constexpr const bool ForwardIterator<T> [with T = I]
     concept bool ForwardIterator =
                  ^~~~~~~~~~~~~~~
    t.cpp:10:14: note: ‘I::iterator_category{}’ is not implicitly convertible to ‘std::forward_iterator_tag’
    t.cpp:16:14: note: ‘I::iterator_category{}’ is not implicitly convertible to ‘std::bidirectional_iterator_tag’
     concept bool BidirectionalIterator =
                  ^~~~~~~~~~~~~~~~~~~~~
    t.cpp:34:3: note: candidate: T next(T, typename T::difference_type) [with T = I; typename T::difference_type = int]
     T next(T, typename T::difference_type = 1);
       ^~~~
    t.cpp:34:3: note: constraints not satisfied
    t.cpp:34:3: note: concept ‘RandomAccessIterator<I>’ was not satisfied
    t.cpp:22:14: note: within the concept template<class T> constexpr const bool RandomAccessIterator<T> [with T = I]
     concept bool RandomAccessIterator =
                  ^~~~~~~~~~~~~~~~~~~~
    t.cpp:22:14: note: concept ‘BidirectionalIterator<I>’ was not satisfied
    t.cpp:16:14: note: within the concept template<class T> constexpr const bool BidirectionalIterator<T> [with T = I]
     concept bool BidirectionalIterator =
                  ^~~~~~~~~~~~~~~~~~~~~
    t.cpp:16:14: note: concept ‘ForwardIterator<I>’ was not satisfied
    t.cpp:10:14: note: within the concept template<class T> constexpr const bool ForwardIterator<T> [with T = I]
     concept bool ForwardIterator =
                  ^~~~~~~~~~~~~~~
    t.cpp:10:14: note: ‘I::iterator_category{}’ is not implicitly convertible to ‘std::forward_iterator_tag’
    t.cpp:16:14: note: ‘I::iterator_category{}’ is not implicitly convertible to ‘std::bidirectional_iterator_tag’
     concept bool BidirectionalIterator =
                  ^~~~~~~~~~~~~~~~~~~~~
    t.cpp:22:14: note: ‘I::iterator_category{}’ is not implicitly convertible to ‘std::random_access_iterator_tag’
     concept bool RandomAccessIterator =
                  ^~~~~~~~~~~~~~~~~~~~

Gcc reports all three overloads and dutifully describes, in 52 lines of detail, why each one is not a valid candidate for the call.  Since the error is not due to a template instantiation failure, there  is no template instantiation stack.  But, if you look at the notes emitted for each candidate, you’ll see something that could be termed a concept refinement stack.  Have we just exchanged one prolix set of diagnostics for another?  And this time, instead of just one template instantiation stack, portions of the concept refinement stack are replicated for each non-viable overload!

Fortunately, the partial ordering of constrained declarations that enables this problem also serves as its solution.  The RandomAccessIterator concept subsumes the BidirectionalIterator concept which subsumes the ForwardIterator concept.  The compiler is already required to be able to compute the partial ordering of the overload candidates.  Why not apply that knowledge to diagnostics generation and either omit subsuming overloads entirely, or replace detailed reporting of such overloads with a note on the subsumed candidate(s)?  The error message below is a mock up of what this might look like.  The emphasized lines reflect the imagined new diagnostic capabilities instilled in the compiler.

    t.cpp: In function ‘void f(I)’:
    t.cpp:44:11: error: no matching function for call to ‘next(I&)’
         next(i);
               ^
    t.cpp:30:3: note: candidate: T next(T, typename T::difference_type) [with T = I; typename T::difference_type = int]
     T next(T, typename T::difference_type = 1);
       ^~~~
    t.cpp:30:3: note: constraints not satisfied
    t.cpp:30:3: note: concept ‘ForwardIterator<I>’ was not satisfied
    t.cpp:10:14: note: within the concept template<class T> constexpr const bool ForwardIterator<T> [with T = I]
     concept bool ForwardIterator =
                  ^~~~~~~~~~~~~~~
    t.cpp:10:14: note: ‘I::iterator_category{}’ is not implicitly convertible to ‘std::forward_iterator_tag’
    t.cpp:32:3: note: candidate subsumed by: T next(T, typename T::difference_type) [with T = I; typename T::difference_type = int]
     T next(T, typename T::difference_type = 1);
       ^~~~
    t.cpp:34:3: note: candidate subsumed by: T next(T, typename T::difference_type) [with T = I; typename T::difference_type = int]
     T next(T, typename T::difference_type = 1);
       ^~~~

Now we’re getting somewhere.  With all due respect to Andrei Alexandrescu [ACCU 2016], Concepts is a great idea!  Anyone have the time to implement this in gcc?

Producing good diagnostics when overload resolution fails is not a new challenge.  Compilers already prune candidates when there are obvious closer matches, so the suggestion above fits nicely into existing practice.  But problems still remain when the best candidates are all non-viable due to SFINAE or constraint failures as the list of candidates can get quite long and it isn’t clear how compilers can best cope with that.  Consider a worst case scenario like a large set of operator==() overloads (all in the same namespace so the compiler can’t favor associated namespaces, and all unrelated by partial ordering).  In one example, gcc dutifully reports all 54 candidates in 539 lines of glorious detail while Clang takes a slightly different approach and reports none of them.  I’m not sure which approach is better, but neither feels particularly satisfactory.  While this problem is not specific to concepts, I fear it may be exacerbated by use of them since they make declaring constrained overloads so much more natural and convenient.  For the foreseeable future, following the existing guidance to write overloads as in-class defined friend functions only resolved by ADL, when possible, remains prudent.

Use of Concepts, as currently proposed, will not eliminate the verbose error messages we’re used to seeing when template instantiation fails.  Such diagnostics will continue to be emitted for unconstrained and under constrained template definitions.  However, wide use of concepts by template authors will reduce the frequency of exposure to such diagnostics by users of constrained templates and I think that is a big win.  Going forward, If we want to improve error messages for template authors as well, then we need to move beyond the current proposal and provide separate checking for template definitions.

[Edit: Corrected references and links to the actual first paper describing concepts.]

[Edit: Considerable concepts related compile-time performance and diagnostic improvements were checked in for gcc 6.2 and 7.0 on 2016-07-21 via gcc bugs 67565 [GCC bug 67565], 67579 [GCC bug 67579], and 71843 [GCC bug 71843]]

References:

[N1510] Bjarne Stroustrup, “Concept checking – A more abstract complement to type checking”, N1510, 2003.
http://open-std.org/jtc1/sc22/wg21/docs/papers/2003/n1510.pdf
[LWG 2353] “C++ Standard Library Defect Report List (Revision R99)”, 2016.
“2353. std::next is over-constrained”
http://www.open-std.org/jtc1/sc22/wg21/docs/lwg-defects.html#2353
[GCC bug 67565] [concepts] Very slow compile time and high memory usage with complex concept definitions, even if unused
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=67565
[GCC bug 67579] [concepts] Memoization for constraint expressions
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=67579
[GCC bug 71843] [concepts] Diagnostics issued for constraint satisfaction failure fail to elucidate unsatisfied constraints
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=71843
[ACCU 2016] “‘Fastware’ - Andrei Alexandrescu [ ACCU 2016 ]”
https://youtu.be/AxnotgLql0k?t=515

Refining Concepts: The quiddity of concept definitions

March 24th, 2016

In Why Concepts didn’t make C++17 [Twitter] [Reddit], I summarized a number of technical concerns that were raised during the C++ standard committee meeting in Jacksonville.  In this post, I’ll be discussing #3 on that list; the forms of concept definitions.

A quick review; the Concepts TS [Concepts] specifies two forms of concept definitions.

Function concept:
    template<typename T>
    concept bool FC() {
      return constraint-expression;
    }

Variable concept:
    template<typename T>
    concept bool VC = constraint-expression;

Function concepts are function template definitions declared with a concept specifier and variable concepts are variable template definitions declared with a concept specifier.  The form that is used to define a concept dictates usage syntax in some contexts.  For example, the above concepts can be referenced with the same syntax in the following constrained function template declaration:
    template<FC T1, VC T2>
    void f();

However, in the following equivalent declaration, the form in which the concept definition is declared determines the syntax used to evaluate each concept.  (Note the added () following FC<T1>)
    template<typename T1, typename T2>
      requires FC<T1>() && VC<T2>
    void f();

The requirement for distinct syntax imposes both usability and maintenance concerns:

  • Library specifications must dictate the form in which a concept definition is provided and implementers must adhere to the specified form.
  • Users of a library that provides concept definitions must be aware of the form in which the concepts are defined when referencing them other than as a constrained-type-specifier.  (Note: constrained-type-specifier should be renamed [Issue#31])
  • Changing a concept definition from one form to the other breaks source compatibility.  Overloading is not supported for variable concepts, so a desire to provide an overloaded concept definition might motivate such a change.

The function form has a distinct advantage over the variable form due to its support for overloading based on template parameter kind and arity.  The variable form offers a slightly more terse syntax for defining and using concepts, but I’m not aware of any other benefits (the ability to prohibit overloading can sometimes be useful, but those uses don’t seem applicable to concept definitions).  All concepts that can be defined using the variable form can be defined using the function form.

So, would dropping the variable form resolve the above concerns?  I think it would.  But, before we kick variable concepts out of the specification, lets look at the current forms a bit more closely.

Function concepts are defined as function templates.  However, adding the concept specifier brings along a host of restrictions:

  • The template parameters must not be constrained.
  • The return type must be declared as bool; return type deduction is not allowed (deduction requires instantiation and function concepts are not instantiated).
  • The parameter list must be empty (or void).
  • An exception specification must not be specified.
  • The body must be a single return statement that returns a constraint-expression.
  • The function must not be declared in conjunction with the thread_local, inline, friend, or constexpr specifiers (though the function will be implicitly defined as constexpr).
  • The function cannot be forward declared.
  • The function must be declared at namespace scope (class member declarations are not permitted).
  • The function cannot be explicitly instantiated or implicitly or explicitly specialized.
  • The function address cannot be taken (kind of.  gcc currently permits it, but since the function is not actually instantiated, unresolved symbol errors occur at link time).

Likewise, the variable form has its own set of similar restrictions:

  • The template parameters must not be constrained.
  • The variable type must be declared as bool; type deduction is not allowed.
  • The variable Initializer must be a constraint-expression.
  • The variable cannot be forward declared (though the specification is currently a little unclear regarding this; see concepts TS issue 16 [Issue#16]).
  • The variable must be declared at namespace scope (class member declarations are not permitted).
  • The variable cannot be explicitly instantiated or implicitly or explicitly specialized.
  • The variable address cannot be taken; concept variable references are prvalues.

Those restrictions lead me to wonder if functions and variables are a good match for expressing concept definitions.  In one sense, they nicely reflect the predicate based boolean algebra of the algorithms that determine constraint satisfaction and partial ordering.  However, I expect most users won’t think about concepts in terms of those algorithms, so the expression of concepts as boolean variables and functions seems a bit of a leaky abstraction.  But, if not a function or a variable, then what should concept definitions be?  What is their quiddity?

Concept definitions serve exactly one purpose; they associate a name with a parameterized constraint-expression and make that name available for use as a constrained-type-specifier as an alternative for use of a requires-clause or in contexts where a requires-clause is not permitted, such as for placeholders in deduced variable and return types.  All other uses of concept definitions can be accommodated with constexpr functions or variables.

[Edit: Concept definitions do serve an additional purpose as described by Botond in the comments]

Concepts do not just constrain types (again, constrained-type-specifier is a misnomer); they may constrain non-type and template template parameters as well.  The idea of a named constraint that is applicable to types, non-types, and templates strikes me as quite novel and leads me to conclude that concepts are a new kind of entity and therefore deserving of a distinct syntax for definition.

I’m not alone in this opinion; concepts TS issue 6 [Issue#6] was opened following a paper [N4434] submitted for the 2015 meeting in Lenexa and proposes adopting the variable form, sans the currently required bool variable type, as a declaration of a first class concept entity.  Let’s take a look at a moderately complicated example concept defined in that form.
    template<typename T>
    concept C =
      Regular<T> &&                 // requires-clause
      requires (T t)                // requires-expression
      {
        typename T::type;           // type-requirement
        requires X<decltype(t.dm)>; // nested-requirement
      };

I like this form.  It now looks like an entity of a unique kind is being declared, the syntax is concise, the association of a name and a constraint-expression is clear, and the existing requires-clause and requires-expression productions are unchanged in both their definition and usage.  What’s not to like?

The challenge is, how do we specify it?  Overloading based on template kind and arity is desirable as demonstrated by the EqualityComparable, Swappable, and other concepts defined in the Ranges TS [Ranges].  But at present, overloading is only defined for functions.  What would it mean to add an additional overloadable entity?  Would it be permissible to declare functions and concepts with the same name, but with distinct template parameter lists?

The current concepts design allows overloading of concept and non-concept functions as a consequence of each being functions, but is this useful?  Or perhaps a recipe for confusion?  Concepts TS issue 20 [Issue#20] touches on this question.  Consider the following code.  The concept overload is usable as a constrained-type-specifier, but the other overload is not.  Both may be used to define constraints however.
    template<typename T>
    concept bool C() { return true; }
     
    template<typename T, typename U>
    constexpr bool C() { return true; }
     
    template<C T>          // Ok.
    void f1() {}
     
    template<C<int> T>     // Ill-formed, C<T,int> is not a concept.
    void f2() {}
     
    template<typename T>
      requires C<T>()      // Ok.
    void f3() {}
     
    template<typename T>
      requires C<T, int>() // Ok.
    void f4() {}

Without a strong incentive for supporting mixed concept and function overloading, my inclination is to prohibit it to avoid having to specify behavior for code like that above.

So, back to the question of how we specify concepts as a first class entity.  I don’t have a full answer for that question.  The following is a rough sketch of the kinds of changes I think would be required.

  1. Remove concept as a declaration specifier.
  2. Add a new concept-definition production to the grammar:
    concept-definition:
        template < template-parameter-list > concept concept-name = constraint-expression ;
  3. Add concept-definition as an additional alternative for template-declaration.
  4. Audit all references to template-declaration and update as needed for the concept-definition alternative.
  5. Audit all references to template-id and update as needed for references to concept definitions.
  6. Update id-expression to define the semantics for reference to a template-id that specifies a concept-name.
  7. Update clause 13 to define concept overloading and to prohibit declarations of functions and concepts with the same name in the same scope.

That last one is the big one.  It might be eased by defining concept overloading in terms of a function template with an empty or void parameter list.  If may also be possible to specify it such that an implementation is permitted to lower concept definitions to function templates in such a way that the current gcc implementation would be conforming with relatively minor changes.

Drafting the changes that would be required to the standard to specify an additional overloadable entity entails significant effort.  Would it be worth it?  I think so.  I expect concepts will be quite popular and defining them as a first class entity will enable their evolution without compromise.  Would interesting use cases be enabled by allowing them to be passed as template parameters like class and alias templates?  What else might we do with concepts if they are freed from the bounds of variables and functions?

References:

[Concepts] “C++ Extensions for concepts”, ISO/IEC technical specification 19217:2015.
http://www.iso.org/iso/home/store/catalogue_tc/catalogue_detail.htm?csnumber=64031
[Issue#6] “C++ Concepts Active Issues List (Revision 3)”, Issue 6: “Simplify concept definitions”, 2016.
http://cplusplus.github.io/concepts-ts/ts-active.html#6
[Issue#16] “C++ Concepts Active Issues List (Revision 3)”, Issue 16: “Concept and non-concept declarations of the same variable template”, 2016.
http://cplusplus.github.io/concepts-ts/ts-active.html#16
[Issue#20] “C++ Concepts Active Issues List (Revision 3)”, Issue 20: “Concept-names and overload sets with non-concept functions”, 2016.
http://cplusplus.github.io/concepts-ts/ts-active.html#20
[Issue#31] “C++ Concepts Active Issues List (Revision 3)”, Issue 31: “Constrained-type-specifiers introduce non-type placeholders”, 2016.
http://cplusplus.github.io/concepts-ts/ts-active.html#31
[N4434] Walter E. Brown, “Tweaks to Streamline Concepts Lite Syntax”, N4434, 2015.
http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2015/n4434.pdf
[Ranges] Eric Niebler and Casey Carter, “Working Draft, C++ Extensions for Ranges”, N4560, 2015.
http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2015/n4560.pdf

Why Concepts didn’t make C++17

March 6th, 2016

I returned home yesterday from attending the ISO C++ 2016 standard committee meeting held in Jacksonville, Florida 02/29-03/05 and decided to share my observations regarding why the Concepts TS wasn’t adopted for C++17.  This decision by the committee may come as a surprise to many who are eager for Concepts and have been expecting it to be included in C++17.

The short explanation is: the committee failed to achieve consensus that Concepts, as specified in the TS, has attained sufficient implementation and usage experience to be confident in the current design.  Basically, the committee did not say “no” to concepts, it said “not yet.”

The long explanation is, well, longer…

The most significant opposition was not due to technical concerns.  The primary concerns raised included:

  1. The Concepts TS [Concepts] was published 2015-11-15 following approval by the committee in between the Lenexa and Kona meetings.  The TS has therefore only existed in a published form for less than four months.
  2. The only known publicly available implementation is in an unreleased version of the gcc compiler.
  3. The implementation in the gcc compiler was developed by the same (very talented) individual that wrote the specification.  An implementation is therefore available for testing, but no known attempt has been made to produce an implementation based on the specification and the specification is therefore untested.  Several core working group (CWG) members indicated that having an implementation produced from specification is critical for identifying specification issues.
  4. The most significant known usage of Concepts is in the Ranges TS [Ranges] and in its only known implementation in Casey Carter and Eric Niebler’s cmcstl2 [cmcstl2].  There are a few other projects experimenting with Concepts (including my own text_view [Text_view] library), but none that approach the scale that would be expected when developers really start making use of the feature.  Performance and error handling issues with the current gcc implementation provide further evidence that no such large scale attempts at using Concepts exists.
  5. The Concepts TS does not specify any concept definitions.  Some committee members question the usefulness of concepts without the availability of a concept definition library such as that in the Ranges TS.  Adopting the Concepts TS into C++17 without a corresponding concept definition library risks locking down the language without proof that it provides the features needed to implement a library as might be designed to conceptify the standard library.

If more implementation and usage experience had been available, would it have affected the decision to adopt Concepts into C++17?  I’m not sure.  A number of technical concerns were raised and I suspect that at least one nation body was prepared to vote no on a final C++17 publication if it included Concepts in its current form.  Technical concerns raised throughout the week included:

  1. The Concepts TS includes new syntax to define function templates.  An abbreviated function template declaration looks similar to a non-template function declaration except that at least one of its parameters is declared with a placeholder type specifier; either ‘auto’ or the name of a concept.  The concern is that a declaration like this:
        void f(X x) {}
    defines a non-template function if ‘X’ is a type, but defines a function template if ‘X’ is a concept.  This has subtle ramifications for whether the function can be defined in a header file, whether the typename keyword is needed to reference member types of ‘X’, whether parameters declared with rvalue reference qualifiers are forwarding references or parameters that only bind to rvalue arguments, whether there is exactly one variable or potentially none or many for each declared static local variable, etc…
  2. The Concepts TS also includes a template-introduction syntax that allows omitting the verbose template declaration syntax that we’re all used to while simultaneously stating type constraints.  For example, the following declares function template ‘f’ taking two parameters ‘A’ and ‘B’ that satisfy concept C<A, B>:
        C{A,B} void f(A a, B b);
    This syntax is not loved by all.  It was mentioned that a version of the Ranges TS used it at one point and the library evolution working group (LEWG) requested that it be changed and never used again.
  3. There are two forms of concept definitions; function and variable.  The function form exists to support overloading of concept definitions based on template parameter arity.  The variable form exists to support slightly shorter definitions.
        // function form:
        template<typename T>
        concept bool C() {
            return ...;
        }
        
        // variable form:
        template<typename T>
        concept bool C = ...;
    All concepts that can be defined using the variable form can be defined using the function form.  The form that is used impacts the syntax required to evaluate a concept, thus usage of a concept requires knowing the form used to define the concept.  An early version of the Ranges TS used both the variable and function forms to define concepts and the inconsistency produced many errors in specification.  The current Ranges TS uses only the function form to define specified concepts.  Some committee members feel that a single concept definition form would simplify the language and avoid usage and teaching difficulties.  Providing a distinct syntax for defining concepts rather than defining them in terms of functions or variables would also avoid the awkward ‘concept bool’ syntax.
  4. A revision of P0127R0 [P0127R0] was approved by the evolution working group (EWG) in Jacksonville for C++17.  This proposal adds the ability to use ‘auto’ as a type specifier for a non-type template parameter:
        template<auto V>
        constexpr auto v = V*2;
    With Concepts, one might want to constrain the above template such that the type of ‘V’ must satisfy the Integral concept:
        template<Integral V>
        constexpr auto v = V*2;
    However, this is the same syntax currently used by the Concepts TS to declare a constrained template type parameter.  If the Concepts TS were to be adopted, then some other syntax would be needed to declare a constrained non-type template parameter.  Arguably, the syntax used by the Concepts TS would be more suitable for declaring template non-type parameters as shown above since this matches the syntax used for other variable declarations.  This implies that a new syntax for declaring constrained type parameters would be desirable for language consistency reasons.
  5. Concepts have been widely expected to produce better error messages than are currently produced when template instantiation fails.  The theory goes, since Concepts enables rejecting code based on a constraint at the point of usage of a template, the compiler can simply report the constraint failure rather than an error in some expression in a potentially deeply nested template instantiation stack.  Unfortunately, it turns out not to be so simple and use of concepts sometimes results in worse error messages.  Constraint failures frequently manifest as overload resolution failures resulting in a potentially long list of candidates, each with its own list of reasons for rejection.  Identifying the candidate that was intended for a given use and then figuring out why the constraint failure occurred, can be a worse experience than navigating a template instantiation stack.
  6. A number of committee members are concerned about whether the current Concepts design suffices as a foundation on which full template definition checking can be implemented in the future.  Though assertions were made by Concepts advocates that such checking will be possible, many questions remain unanswered, and these committee members remain unconvinced.  It seems unlikely that these concerns will be addressed other than through an implementation of definition checking.

I’m confident that Concepts, in some form, will be added to C++19/20.  I expect all of gcc, Clang, and Visual C++ to be shipping implementations well before the next standard is complete, hopefully within the next year.  While we await the growth of confidence in the Concepts design, I hope to see changes made to address at least some of the technical concerns listed above as I think addressing these will help to build consensus and avoid surprises when we next consider adopting Concepts into the C++ standard.

In the next few posts, I’ll explore the technical design concerns above in more depth and discuss possible solutions.

References:

[Concepts] “C++ Extensions for concepts”, ISO/IEC technical specification 19217:2015.
http://www.iso.org/iso/home/store/catalogue_tc/catalogue_detail.htm?csnumber=64031
[Ranges] Eric Niebler and Casey Carter, “Working Draft, C++ Extensions for Ranges”, N4560, 2015.
http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2015/n4560.pdf
[cmcstl2] Casey Carter and Eric Niebler, An implementation of C++ Extensions for Ranges.
https://github.com/CaseyCarter/cmcstl2
[Text_view] Tom Honermann, Text_view library.
https://github.com/tahonermann/text_view
[P0127R0] James Touton, “Declaring non-type template arguments with auto”, P0127R0, 2015.
http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2015/p0127r0.html