Concept Checking in C++11

Posted on by — 34 Comments ↓

This post describes some utilities I’ve recently developed for doing concept checking in C++11. These utilities are part of an ongoing project to reimplement ranges, also for C++11, but I think the concept checking utilities are useful and interesting in their own right.

Concepts, the Saga So Far

(Feel free to skip this section if you already know what concepts are.)

The story of concept checking in C++ is long and quite dramatic. They were added to C++0x, they were hotly debated, they were ripped out (along with lots of greying hair), hands were wrung, chests beaten, sackcloth rent … Biblical stuff, truly. OK, maybe not, but it was dramatic. Anyway, there’s a new proposal to add them back, so it’s clear lots of people want concepts bad.

But let’s back up. What are concepts? In a sense, programmers have been using concepts since 1998 or even earlier, when the Standard Template Library first became a thing. You probably know what an iterator is, and you know there’s a difference between a random-access iterator, like std::vector‘s iterators, and bidirectional iterators, like std::list‘s. Things like “random-access iterator” and “bidirectional iterator” are concepts. Types don’t have to inherit from any special base class to be a random-access iterator. They just have to support a certain syntax and semantics. And the random-access iterator concept is a refinement of bidirectional iterator; the former supports all the syntax and semantics of the latter (e.g., increment and decrement), plus some additional stuff (e.g., being able to advance an iterator by n positions in O(1) time).

Concepts make it possible to define polymorphic algorithms: algorithms that work with objects of many different types. And they do it with very loose coupling and high performance. If your algorithm only relies on the syntax and semantics promised by the concept, then it should Just Work. And there’s the rub. Today, there’s no way to say in code that a certain algorithm requires random-access iterators, and if you pass it a bidirectional iterator, you’re sure to find out in the most unpleasant way. Hence the desire to add concept checking to the language proper.

Concepts, A New Hope?

Enough back-story. Show me the code, right? Here’s the full refinement hierarchy for the iterator concepts as defined with my utility.

struct Iterator
  : refines<CopyConstructible, CopyAssignable,
            Destructible>
{
    // Valid expressions
    template<typename T>
    auto requires(T && t) -> decltype(
        concepts::valid_expr(
            *t,
            concepts::has_type<T &>(++t)
        ));
};

struct OutputIterator
  : refines<Iterator(_1)> // OutputIterator<T,U> refines
{                         // Iterator<T>
    template<typename T, typename O>
    auto requires(T && t, O && o) -> decltype(
        concepts::valid_expr(
            t++,
            *t = o,
            *t++ = o
        ));
};

struct InputIterator
  : refines<Iterator, Comparable>
{
    template<typename T>
    auto requires(T && t) -> decltype(
        concepts::valid_expr(
            t++,
            concepts::convertible(*t, *t++)
        ));
};

struct ForwardIterator
  : refines<InputIterator>
{
    template<typename T>
    auto requires(T && t) -> decltype(
        concepts::valid_expr(
            concepts::same_type(*t, *t++)
        ));
};

struct BidirectionalIterator
  : refines<ForwardIterator>
{
    template<typename T>
    auto requires(T && t) -> decltype(
        concepts::valid_expr(
            concepts::has_type<T &>( --t ),
            concepts::same_type(*t, *t--)
        ));
};

struct RandomAccessIterator
  : refines<BidirectionalIterator>
{
    template<typename T>
    auto requires(T && t) -> decltype(
        concepts::valid_expr(
            concepts::model_of<SignedIntegral>(t-t),
            t = t + (t-t),
            t = (t-t) + t,
            t = t - (t-t),
            t += (t-t),
            t -= (t-t),
            concepts::same_type(*t, t[t-t]),
            concepts::model_of<Orderable>(t)
        ));
};

This might look a little strange at first glance, so let me step you through it. The first two lines…

struct Iterator
  : refines<CopyConstructible, CopyAssignable,
            Destructible>

… says that there is a concept called Iterator that refines the concepts CopyConstructible, CopyAssignable, and Destructible. Surely all iterators must support those basic operations. If the concept you want to define doesn’t refine any other concepts, you can leave that part off.

The next few lines describes the so-called valid expressions: valid syntax that all iterators must support:

template<typename T>
auto requires(T && t) -> decltype(
    concepts::valid_expr(
        *t,
        concepts::has_type<T &>(++t)
    ));

You must be able to dereference an iterator and increment it, and the result of the increment operation must have type T &. This is true of all iterators. When you’re defining your concept’s valid expressions, you do so by following the above pattern: a requires member function that takes one or more objects by rvalue ref, and a trailing return type with decltype(concepts::valid_expr(/*...*/)) with your valid expressions. And that’s pretty much it for the concept definitions. There’s some utilities like has_type, same_type, and model_of for concept check-y sorts of things, but those are all details.

Concept Checking

We’ve seen what concept definitions look like, now let’s see how to use them. Imagine all the above definitions are in a concepts namespace. Let’s define some helpers for testing certain types against the concept definitions. They look like this:

template<typename T>
constexpr bool Iterator()
{
    return concepts::models<concepts::Iterator, T>();
}

template<typename T, typename O>
constexpr bool OutputIterator()
{
    return concepts::models<concepts::OutputIterator, T, O>();
}

template<typename T>
constexpr bool InputIterator()
{
    return concepts::models<concepts::InputIterator, T>();
}

template<typename T>
constexpr bool ForwardIterator()
{
    return concepts::models<concepts::ForwardIterator, T>();
}

template<typename T>
constexpr bool BidirectionalIterator()
{
    return concepts::models<concepts::BidirectionalIterator, T>();
}

template<typename T>
constexpr bool RandomAccessIterator()
{
    return concepts::models<concepts::RandomAccessIterator, T>();
}

Notice how these concept checkers are constexpr Boolean functions. The concepts::models function will return true if the given type(s) model the concept, and false otherwise. Easy. And note that so far, we haven’t used a single macro because I hate macros.

Now when you are wondering whether a certain type models a concept, you can get the answer as a compile-time Boolean. Say, for instance, that you are writing something like the std::advance algorithm. You want to make sure that the two arguments are an input iterator and a integral type, respectively:

template<typename InIt, typename Diff>
void advance(InIt & it, Diff d)
{
    static_assert(ranges::Integral<Diff>(),
                  "Diff isn't integral");
    static_assert(ranges::InputIterator<InIt>(),
                  "InIt isn't an input iterator");
    // ...
}

If you’re not allergic to macros, you can also do this:

template<typename InIt, typename Diff>
void advance(InIt & it, Diff d)
{
    CONCEPT_ASSERT(ranges::Integral<Diff>());
    CONCEPT_ASSERT(ranges::InputIterator<InIt>());
    // ...
}

(As you can see, in my code all the concept checking function are in the ranges namespace.) This is pretty nice. If someone calls advance with the wrong types, they’ll get a sensible error message. But maybe you want something else. Maybe there are lots of advance functions, and you want this overload to silently go away if the types don’t model the concepts. Then you can do this:

template<typename InIt, typename Diff,
         typename = concepts::requires_t<
                        ranges::Integral<Diff>() &&
                        ranges::InputIterator<InIt>()>>
void advance(InIt & it, Diff d)
{
    // ...
}

This uses SFINAE to make the advance function disappear when the concept requirements are not satisfied. That works, but it’s getting a bit ugly. Maybe it’s better to hold our noses and use a macro:

template<typename InIt, typename Diff,
         CONCEPT_REQUIRES(ranges::Integral<Diff>() &&
                          ranges::InputIterator<InIt>())>
void advance(InIt & it, Diff d)
{
    // ...
}

I hate macros, but I can live with that.

Concept-Based Overloading

If you know anything about std::advance, you might know why I picked it as an example. advance advances an iterator by a certain number of positions. Most iterators must be bumped forward n times, which is slow. But if an iterator is random-access, you can just add n to it and be done. How would you achieve that with my new concept-checking utilities?

In C++98, this is accomplished with iterator tag types and tag dispatching. Unfortunately, tag dispatching is still the best we can do in C++11, which is why we really need a language feature. But with my code, becomes quite a bit easier. The concept definitions can themselves be used as tags. Let’s see how.

The first question to answer is, given an iterator type, what is the most refined iterator concept that it models? For a type like int* it should be RandomAccessIterator, but for std::list::iterator it should be BidirectionalIterator. You can get that information with the help of a utility called most_refined_t. Here we use most_refined_t to implement an iterator_concept_t alias that tells you what concept an iterator type models:

template<typename T>
using iterator_concept_t =
    concepts::most_refined_t<
        concepts::RandomAccessIterator, T>;

most_refined_t does a breadth-first search of the refinement hierarchy rooted at concepts::RandomAccessIterator, looking for the most refined concept modeled by type T. Here’s how we can use it to optimally implement advance:

// Random-access iterators go here
template<typename RndIt, typename Diff>
void advance_impl(RndIt & it, Diff d,
                  ranges::concepts::RandomAccessIterator)
{
    it += d;
}

// All other iterator types go here
template<typename InIt, typename Diff>
void advance_impl(InIt & it, Diff d,
                  ranges::concepts::InputIterator)
{
    for(; d != 0; --d)
        ++it;
}

template<typename InIt, typename Diff,
         CONCEPT_REQUIRES(ranges::InputIterator<InIt>() &&
                          ranges::Integral<Diff>())>
void advance(InIt it, Diff d)
{
    advance_impl(it, d, ranges::iterator_concept_t<InIt>{});
}

As you can see, concept-based overloading is accomplished by dispatching to the proper implementation based on the concept that a particular type models. This all works just based on the concept definitions which, if you recall, only required you to specify the refinements and the valid expressions declaratively. You didn’t have to define any separate tags or any traits or metafunctions. Not shabby.

What’s Missing?

The big missing piece of this puzzle is the ability to automatically check an algorithm against the requires clauses. It’s all well and good that the advance algorithm says it needs only input iterators. But what if its implementation actually makes some other assumption? You wouldn’t know until you tried to call the algorithm with a type that doesn’t satisfy the assumption. That’s the state of the art, I’m afraid, and there’s nothing I can do about it. Sorry.

Making the Abstract Concrete

My concept-checking library isn’t perfect. It’s really a pale approximation of what true language support would be like. Heck, it isn’t even a library yet. But in my limited experience using this utility in my range code so far, it has real benefits. I can create rich overload sets and tune which overload gets selected by simply declaring what concepts the types must model. And defining the concepts is easy. Fun, even. It gives me more confidence when writing generic code that I’m actually going to get the behavior I expect.

So, if you like, leave me a comment with your thoughts. Would you find this useful? Is there a direction you’d like to see this go? Should I try (in my ample free time ) to turn this into a proper library, possibly as a modern replacement for Boost.Concept_check? Give me your thoughts.

For reference, you can find the (woefully under-commented and undocumented) code here.

x

34 Replies to “Concept Checking in C++11”

  1. Loved this. It is by far most interesting article I’ve read on this blog. I’ll definitely see the implementation, I may form my own thoughts thereafter.

    Reply ↓

  2. Pingback: Concept Checking in C++11 | Enjoying The Moment

    • (Repeating my response from reddit.) I think that’s more a proposal for compile-time reflection. It’s interesting. I’d like it better if it hid the clang AST API. That API is a moving target. I’d hate for all my code to break because someone in the clang team decided to tweak the AST.

      Reply ↓

  4. I like it. These days hard errors like those triggered by Boost.Concept_Check are not as convenient as the queryable nature of traits, or things that look like traits. On the other hand, littering detail namespaces with individual quasi-traits to check for every single aspect of a concept introduces a lot of noise. I know I’ve deliberately not been thorough when exploring some concepts, because I wasn’t sure if checking the validity of a convoluted expression would be of value when compared to the cost of writing the checks. Your solution is concise, readable and SFINAE-friendly — training wheels for concepts lite.

    On the other hand, there is a benefit to writing concepts as:

    template<typename T>
    struct BidirectionalIterator: And<
    ForwardIterator<T> // refines
    , detail::Decrement<T> // individually check new requirements
    /* rest omitted */
    > {};

    Namely that And can be a bit more than a logical conjunction, by providing e.g. a member to walk each clause, asserting on the first that fails.

    This is helpful when faced with an SFINAE failure, as a typical message is of the sort ‘no member named type in enable_if…’. In such situation I can add BidirectionalIterator<decltype(whichever argument expression)>::explain(), netting a new error message explaining e.g. ‘assertion failed in explain_failure() with T = detail::Decrement’.

    There is more than one way to skin that particular cat though. The essence of the challenge being whether it is possible to retain the compactness of -> decltype( concepts::valid_expr(foo, bar, baz) ) while still making an SFINAE failure understandable or explainable?

    Reply ↓

    • That’s a good question. You most definitely want to use SFINAE to prune overload sets. But inevitably you end up in situations where the function you want to call is SFINAE-ed away for some reason you don’t understand, and you want to investigate. A utility like explain_sfinae which walks the requires clauses or the refinement hierarchy or both and tells you where the failure is would be valuable.

      Reply ↓

  5. Should I try (in my ample free time ) to turn this into a
    proper library, possibly as a modern replacement for
    Boost.Concept_check?

    That would be awesome but a separated github repo that people can fork and start using (and maybe even contributing to it!) might also be a nice start that would require a bit less of your free time 🙂

    Reply ↓

  7. Looks good, but I just wonder about one thing: compile-time performance. How is it? Compile time performance keeps me away of some template uses sometimes.

    Reply ↓

  8. Erik, I would like to use CONCEPT_ REQUIRES in a specific use case.

    template <class… Args
    CONCEPT_ REQUIRES(std::is_constructible<value_type, Args&…>()) >
    explicit optional(in_place_t, Args&&… args);

    Would this work? If not, why? Is there an alternative approach ?

    Reply ↓

    • A type trait like std::is_constructible is not a concept, but I have provided the degenerate concepts True and False for this purpose. It would look like:

      template<typename...Args,
    CONCEPT_REQUIRES(True<std::is_constructible<value_type, Args&&...>>())>
explicit optional(in_place_t, Args&&... args);

      But there should be a Constructible concept for this. It would be trivial to add.

      Reply ↓

  9. Wow! I would say that libary saves the day. From a user’s POV this looks elegant and concise. This gives extra time for the designers of the language feature, since we have something that works. Many thanks for sharing this.

    Could you please explain your recent change (
    concept checks are now Boolean metafunctions instead of constexpr Boo… )? As always, once you explain there is a tiny little chance to follow …

    Reply ↓

    • Thanks, Marcus. The recent change is to replace the constexpr bool functions described here with equivalent type traits. The usage is nearly the same. That is, you can still do:

      CONCEPT_ASSERT(InputIterator<It>());

      The only difference is that InputIterator<It>() now “constructs” an object of type InputIterator<It>, which has a constexpr conversion to bool. Likewise, you can also still do this:

      CONCEPT_ASSERT(InputIterator<It>() &&
               UnaryPredicate<Fun, iterator_value_t<It>>());

      The fact that they’re metafunctions (types) means you can pass them around. That is, they’re first-order compile-time objects. constexpr bool functions aren’t and so can’t be passed around easily.

      I’m still on the fence about this change. It can occasionally trigger the most-vexing parse. An example is:

      typename std::enable_if<Iterator<It>()>::type

      Here, Iterator<It>() parses as the type of a function taking no arguments and returning Iterator<It>. This has not conversion to bool, and so it causes a hard error. The solution is to do one of the following:

      typename std::enable_if<(Iterator<It>())>::type // OK
typename std::enable_if<Iterator<It>{}>::type   // OK
CONCEPT_REQUIRES(Iterator<It>()) // Also OK

      Thoughts? I’m not sure I like setting users up for a mysterious failure like this.

      Reply ↓

      • Well this is really ony a failure when used inside a template parameter. It will work where a boolen is expected such as static_assert(and in the requires clauses I presume as well).

        I honestly think this is a better direction for these so called ‘concepts’ to go. Especially when combined with generic lambdas(which could possibly lead to a simplified way of defining functions). For example, using these utilities:

        template<bool B>
        using requires = typename std::enable_if<B, int>::type;

        template<template<class...> class Trait, class... Ts>
        constexpr bool ax(Ts&&...)
        {
        return Trait<typename std::remove_reference<Ts>::type...>::value;
        }

        I can then define a transform function with a requires clause like this:

        auto transform = [](auto range, auto predicate,
        requires
        <
        ax<Range>(range) and
        ax<UnaryPredicate>(predicate, range_value(range))
        >_=0)
        {
        ...
        }

        It uses what I call an ax operator. (Its called that to be short, perhaps there is a better name for it.) Utimately this is a much cleaner way of defining generic functions, it requires no template paramters(althought they are used implicitly), and no need to use decltype. Plus, it doesn’t succumb to the problems of the most vexing parse.

        Ideally, it would be much nicer if C++ supported this operator natively along with a trailing requires clause, perhaps like this:

        auto transform = [](auto range, auto predicate)
        requires
        @Range(range) and
        @UnaryPredicate(predicate, range_value(range))
        {
        ...
        }

        Just some thoughts on this subject.

        Reply ↓

  13. Eric,

    thanks for writing this out. I implemented this myself, and am now trying to convert my code to using it. However, I ran into a problem.

    I have a concept Real — for real numbers. Each type to model this concept must have a free function bool isInfinity(Type) to tell whether an object represents infinity or not.

    Everything went fine in Visual C++ 2015 RC. But, of course, that was only because VC++ is relaxed with respect to two-phase name-lookup.

    With Clang and gcc I ran into problems. The problem seems to be that in the concept-requirement-decltype, the function template isInfinity is not a dependent name — even if the concept-requirement is written in the form isInfinity<Type>(t). So, as I understand it, I would need to make isInfinity a dependent name, so that it will be looked up at only when the concept-requirement function-template is instantiated.

    One possibility is to create a global isInfinity template, which is looked up at the first phase, which redirects to a template-class, which is looked up at the second phase.

    Would you know of a neater way to solve this?

    Reply ↓

    • The call must be unqualified, and it must depend on a function parameter. It’s exactly how the Range concept in my range-v3 library is implemented in terms of a call to begin and end. You can see how it works there.

      Reply ↓

      • Hmm.. I looked at range-v3 and tried to replicate the essential, with no luck. Here is a live code sample (Clang 3.7):

        http://goo.gl/19dFCv

        This is the error I interpreted becoming from two-phase name lookup. Is the code in range-v3 different to this example?

        Reply ↓

          • Here’ s an attempt at explanation for anyone going through the same problems. I hope it is at least to the right direction:p

            The problem is not two-phase name lookup. Since isInfinity(t) depends on argument t, which has a dependent type, the function call will be resolved in the dependent-phase (as desired). In the dependent-phase, the call is resolved using argument-dependent lookup (ADL). Since a native type is not associated with any namespace, the lookup fails. In contrast, ADL works as usual for a user-defined struct. The solution is to define the function isInfinity for native types before the concept is defined.

            A harder problem is to extend the concept with a function infinity<Type>(), which returns an object of type ‘Type’ representing infinity. Here the function template gets resolved in the non-dependent phase, which requires the function to already be defined for all models. This is not possible for user-defined models, since they are not known beforehand. I wonder if there is some reasonable workaround.

  14. This page is bloody awful if you want to print it. The background black is not ignored as is the normal case with web pages. I think what you say is important enough to want to print it. You fail to appreciate that there is more than one way to view a web page and waste VAST quantities of my toner.

    Reply ↓

  15. Dear Eric Niebler,

    I found an interesting (and maybe unintended) use case of your concepts. (Maybe you are already familiar with this use case, but I’d like to share it anyway).

    In my scenario, I want to pass my own templated type into a function. But for simplicity, let’s just take std::vector<T> as example instead. Because the function actually the unary operator operator+(.), it is important that it only binds to my own type, hence, my function is templated on typename T and takes std::vector<T>.

    template<typename T>
operator+ (std::vector<T>& v)

    Now, I actually want to improve my function, by making it accept both rvalues and lvalues, so I want to take a universal reference to std::vector<T>.
    However, the standard (see for instance the blogpost of Scott Meyers [1] on this topic), will treat std::vector<T>&& as an rvalue.
    On the other hand, just accepting T instead of vector<T> would bind to anything, so the following will not be desirable:

    template<typename T>
operator+ (T&& v)

    I solved this as follows

    template<typename S, CONCEPT_REQUIRES_(matchVec<S>())>
void operator+(S&& sh)
{
  //body....
}

    where matchVec is defined as follows: (inspired by Milewski [2])

    template<class T> struct matchVec_imp
{ static const bool apply = false; };

template<class... T> struct matchVec_imp<std::vector<T...>> 
{ static const bool apply = true; };

template<typename S> constexpr bool matchVec()
{ return matchVec_imp<std::decay_t<S>>::apply; }

    Now my question to you, can matchVec be implemented using your constructs?
    (In particular, could we make it generic, so that I can not only match against std::vector (which is now hardcoded in matchVec_imp), but an arbitrary templated class?)

    Kind regards,
    and last but not least: thank you for sharing this post and your C++ work in general,
    Niek

    [1] https://isocpp.org/blog/2012/11/universal-references-in-c11-scott-meyers
    [2] https://bartoszmilewski.com/2009/09/08/template-metaprogramming-made-easy-huh/

    Reply ↓

    • My meta library has a trait for telling whether a type is an instantiation of a particular template. That is handy here:

      template<typename S,
    CONCEPT_REQUIRES_(meta::is<S, std::vector>::value)>
void operator+(S&& sh)
{
  //body....
}
      Reply ↓

Leave a Reply to Germán Diago Cancel reply

Your email address will not be published. Required fields are marked *

*

This site uses Akismet to reduce spam. Learn how your comment data is processed.