C++0x: No concepts no fun?

“Concepts” was a proposed C++0x feature that was supposed to make generic programming more enjoyable. The intention was to render many guru-level “template tricks” superfluous, produce much better compile-time error messages and provide “modular type checking” so errors can be caught early (even before a template is instantiated).

• Fact 1: Concepts have been removed from the C++0x standardization effort. See Doug Gregor’s blog post.
• Fact 2: C++0x still includes a whole lot of other core language and library features.

Fact 1 is as saddening as it is a relief, to be honest. Not all is lost, though. We don’t get modular type checking in C++0x. But we can restrict templates via SFINAE which just got more powerful with the addition of decltype and the extension of SFINAE to expressions. What follows is a reminder of how this used to look in good ol’ C++98. In this case it’s a simple pointer wrapper:

  template<typename T>
  class ptr
  {
    T* p;
    template<typename> friend class ptr;
  public:
    ptr(T* p) : p(p) {}

    template<typename U>
    ptr(ptr<U> const& x, typename enable_if<
        is_convertible<U*,T*>::value
    >::type* =0)
    : p(x.p) {}

    T& operator*() const {return *p;}
    T* operator->() const {return p;}
    T* get() const {return p;}
  };

“What’s with the enable_if?” you may ask. This is “SFINAE” in action. If the compiler considers instantiating the constructor for some types T and U where U* is not convertible to T* we’d like the compiler to ignore this function. We can do this by using enable_if for selecting the type of an additional default parameter. enable_if<...>::type is only a valid type if the condition — the first parameter to enable_if — holds. Otherwise, the class won’t contain a typedef and when there is no such typedef the compiler has a hard time figuring out the constructor’s prototype. Since it deduces U and enable_if<...>::type depends on U such an error qualifies as “deduction failure” and makes the compiler just ignore the constructor. Great! This is exactly what we want! This way we can constrain templates and kick them out of the overload set before it tries to instantiate them and even before the compiler applies overload resolution.

Without this SFINAE trick the compiler will still complain when someone tries to convert a ptr<int> to a ptr<double>, for example. But it complains rather late after trying to instantiate the conversion constructor. Since int* is not convertible to double* it will point us to the initializer list — specifically p(x.p) — instead of pointing us directly to the offending line that requrested a ptr<int> to ptr<double> conversion. This is not as nice because it exposes implementation details and usually leads to many more lines of error messages. But exposition of implementation details is not the only problem. If we can’t eliminate functions from the overload set we might get ambiguity errors. For example, the set might contain two function template specializations that are deemed equally good in terms of overload resolution. But only one function can be instantiated, the other one will trigger a compilation error because some template parameters don’t satisfy all constraints. Since overload resolution is applied before instantiation the function call is ambiguous even though there’s only one candidate whose body is well-formed.

So, at first glance, it looks like SFINAE is just as good as a concept-“requires clause” when it comes to constraining a function template. Unfortunately, there are only a few things we can check for in C++98. Luckily, this changes with C++0x.

  template<typename T> struct meta {
    static T&& src();
    static void sink(T);
  };

  template<typename T>
  class ptr
  {
    .....
    template<typename U, typename =
      decltype( meta<T*>::sink( meta<U*>::src() ) )>
    ptr(ptr<U> const& x) : p(x.p) {}
    .....
  };

This example shows a constructor with a default template argument which would have been illegal in C++03. This allows us to get rid of spurious default parameters. The expression inside decltype() tries to pass a pointer of type U* to a function that accepts a pointer of type T*. The implementation of the type trait class is_convertible is based on the same idea. If U* is implicitly convertible to T* the declared type of this expression will be void which is the sink function’s return value type. If U* is not convertible to T* we have a “deduction failure” and the compiler will just ignore the function. I also could have just reused the is_convertible type trait like this

  template<typename U, typename = typename
    enable_if<is_convertible<U*,T*>::value>::type >
  ptr(ptr<U> const& x) : p(x.p) {}

This version is probably more readable. But the point I was trying to make with the former example was that it’s basically possible to check for the “well-formedness” of arbitrary expressions via decltype.

With a bit of macro trickery I was able to write a little header file that contains type trait classes for many many expressions that emulate the concepts HasPlus, HasDereference, HasAssign, Convertible, HasConstructor, etc. I call these “basic expression concepts”. Anything else can be built on top of these via composition. With a couple of other helper templates I managed to make composition fairly easy. This is what my “ForwardIterator concept” looks like, for example:

  template<typename Iter> struct ForwardIterator
  : and_<
    SemiRegular<Iter>, // copiable, assignable
    EqualityComparable<Iter>,
    HasDereference<Iter>,
    SameType<typename HasPreincrement<Iter&>::result_type,Iter&>
    Convertible<typename HasPostincrement<Iter&>::result_type,Iter>
  > {
    typedef typename HasDereference<Iter>::result_type reference;
  };

Every “basic expression concept” exposes a static const bool named value which is true if the expression is well-formed and false otherwise. In addition, it contains a typedef for result_type that either matches the expressions type or is equivalent to invalid_type (an empty struct). The use of invalid_type instead of a missing typedef prevents compilation errors and eases composition. So far, this looks like a nice framework for constraining templates. If there is interest, I could show you the whole 300 line header file. It also includes a nice macro that lets you write code like this:

  template<typename Iter, REQUIRES(ForwardIterator<Iter>)>
  void foo(Iter a, Iter b) {
    // ...
  }

Conclusions: Extended SFINAE and decltype will make generic programming more enjoyable and possibibly more accessible to the masses. We can’t emulate modular type checking or concept-based overloading well, though. Constraints for class templates are even easier to check for with the help of static_assert and appropriate trait classes.

– P