Refining Concepts: Improving error messages

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
        && requires(T t) {
            { typename T::iterator_category{} } -> std::forward_iterator_tag;
        };
    template<typename T>
    concept bool BidirectionalIterator =
        ForwardIterator
        && requires(T t) {
            { typename T::iterator_category{} } -> std::bidirectional_iterator_tag;
        };
    template<typename T>
    concept bool RandomAccessIterator =
        BidirectionalIterator
        && 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’ was not satisfied
    t.cpp:10:14: note: within the concept template constexpr const bool ForwardIterator [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’ was not satisfied
    t.cpp:16:14: note: within the concept template constexpr const bool BidirectionalIterator [with T = I]
     concept bool BidirectionalIterator =
                  ^~~~~~~~~~~~~~~~~~~~~
    t.cpp:16:14: note: concept ‘ForwardIterator’ was not satisfied
    t.cpp:10:14: note: within the concept template constexpr const bool ForwardIterator [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’ was not satisfied
    t.cpp:22:14: note: within the concept template constexpr const bool RandomAccessIterator [with T = I]
     concept bool RandomAccessIterator =
                  ^~~~~~~~~~~~~~~~~~~~
    t.cpp:22:14: note: concept ‘BidirectionalIterator’ was not satisfied
    t.cpp:16:14: note: within the concept template constexpr const bool BidirectionalIterator [with T = I]
     concept bool BidirectionalIterator =
                  ^~~~~~~~~~~~~~~~~~~~~
    t.cpp:16:14: note: concept ‘ForwardIterator’ was not satisfied
    t.cpp:10:14: note: within the concept template constexpr const bool ForwardIterator [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’ was not satisfied
    t.cpp:10:14: note: within the concept template constexpr const bool ForwardIterator [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

Comments are closed.