Late-Checked Templates, Revisited

One of the sticking points in the design of concepts has been the form of an “escape hatch”, where programmers that want some of the benefits of concepts (e.g., improved type-checking for users), but who want to use unsafe constructs within the bodies of their templates, such as extensive meta-programming. The “escape hatch” might also be useful for library developers that want to provide some support for concepts, but have not yet had the time to completely convert their libraries to use concepts.

The “escape hatch” has taken several forms, none of which I’ve liked. The most recent incarnation had “late-checked” expressions, types, and concept maps, which essentially allowed one to break type safety in a very localized manner. For example, one might write:

  typedef late_check typename some_metafunction<T>::type foo_t;

Now, we’re left with a choice: we know foo_t is unsafe, so either we need to make everything that uses “foo_t” also unsafe (because we know nothing about the type foo_t), or we have to say that the user can’t do anything with a “foo_t”. We chose the latter option, because it provides better type safety, then allowed the introduction of “where” clauses at block scope to say “assume this holds”, e.g.,

  where InputIterator<foo_t>; // we don't know what foo_t is, but we'll assume it's an InputIterator

Aside from being a real pain to implement, this approach means that one needs to do a lot of work to use the escape hatch. First one must use late_check, then (potentially) write concepts for whatever needs to be done with the result of the late_check (e.g., foo_t), then add where clauses in the body that say what foo_t really is… overall, it’s unlikely to save all that much effort.

So, in a discussion with Jaakko Jarvi, we decided that the right approach is to change the granularity of late_check. Instead of operating at the level of expressions or types, it acts at the level of entire templates. One can put the late_check keyword before the “template” keyword to indicate that, even though the template has constraints that the user of the template must meet, the body of the template will be parsed as if those constraints didn’t exist. Thus, late_check makes a constrained template act more like an unconstrained template. For example:

  late_check template<typename T>
  where Addable<T>
  T plus_equals(T& x, T y) {
    x = x + y;
  }

The Addable requirement allows one to add two T’s, but if this template where constrained, the assignment from the result of x+y to x would cause an error: T might not necessarily be Assignable. By adding the late_check keyword, we delay type-checking of plus_equals until instantiation time (just like with normal, unconstrained templates). However, one will not be able to call plus_equals with a type that is not Addable:

  struct X { };

  X x, y;
  plus_equals(x, y); // error: no matching function for call to plus_equals(X, X)

One caveat with late-checked templates is that they will not work well with concept maps that adapt syntax. For example, if we added the following concept map after the definition of the type X in the above program:

  concept_map Addable<X> {
    X operator+(X x, X y) { ... }
  }

Now, X is Addable, and the call to plus_equals will succeed. However, when we go to instantiate plus_equals<X>, no “+” will be found (because we never type-checked “x + y” to determine that + was part of the Addable concept), and we will get an instantiation-time failure. This is probably the right behavior, because the writer of plus_equals has decided for some reason that this template should be late-checked. Fortunately, since the compiler typically knows when a late-checked template is being given a concept map that rewrites syntax, so we could warn when such a thing happened, or give better guidance in the error message.

Range-based “for” Loop in ConceptGCC

Yesterday, I completed the initial implementation of the range-based for loop in ConceptGCC. This loop allows own to easily iterate over all of the values in a container, e.g.,

std::list<int> values;
// fill values...

int sum = 0;
for (int i : values)
  sum += i;

Here, we simply sum up the values in the list, but of course the body of the range-based “for” loop can be any statement.

As I mentioned before, this “for” loop can iterate over any of the standard containers. It can also iterate over statically-sized arrays, pairs of iterators, and even user-defined types. In fact, the range-based “for” loop can iterate over any type that meets the requirements of the For concept, which is defined in the (new) standard header <for>:

concept For<typename X> {
  InputIterator iterator;
  iterator begin(X&);
  iterator end(X&);
};

Of course, the standard library provides concept maps for the obvious cases. For example, the following concept map allows iteration over pairs of iterators:

template<InputIterator Iter>
concept_map For<pair<Iter, Iter> > {
  typedef Iter iterator;
  iterator begin(pair<Iter, Iter> p) { return p.first; }
  iterator end(pair<Iter, Iter> p) { return p.second; }
}

More information on the range-based “for” loop is available in Thorsten Ottosen’s original range-based “for” loop proposal and my concept-based version of his proposal. The latest version of ConceptGCC, available via Subversion, implements this feature as specified. Beware, however, that some bugs in the handling of constrained concept maps make it harder to do some of the really neat “for” loops that one would like to do. I hope to fix these in the coming weeks.

Google Hosting a Concepts Meeting

Matt Austern of Google will be hosting a meeting to discuss the concepts proposal for C++0x, February 22-23 at Google’s site in Mountain View, CA. We hope to finalize many of the details of concepts, so that we can begin drafting wording for the standard. The meeting is primarily intended for—but not restricted to—members of the ISO C++ committee.

Revisiting name lookup with the swap() example

Niels Dekker contributed an interesting bug report regarding the use of swap(). swap() is particularly interesting, because it is essentially the only algorithm in the C++ Standard Library that is really meant to be customized. The example is quite small:

  template <std::Swappable T>
  void SwapTheSwappable(T& lhs, T& rhs) {
    using std::swap;
    swap(lhs, rhs);  // ConceptGCC error: no matching function for call...
  }

This function (SwapTheSwappable) ConceptGCC rejects the call to swap() because the type ‘T’ does not meet the Assignable and CopyConstructible requirements. To see why, we first need to look at std::swap:

  template <typename T>
  where CopyConstructible<T> && Assignable<T>
  void swap(T& x, T& y) {
    T tmp(x);
    x = y;
    y = tmp;
  }

The Swappable concept then looks like this:

  auto concept Swappable<typename > {
    void swap(T&, T&)
  }

For any CopyConstructible and Assignable type, the Swappable requirements are automatically met by the std::swap template. Users can provide their own swap function in an associated namespace or write a concept map to provide a different implementation of swap.

So why does SwapTheSwappable fail? Name lookup for the call swap(lhs, rhs) finds the std::swap declared by the using declaration (“using std::swap”), and stops there. Since this function template requires Assignable and CopyConstructible, which aren’t requirements for SwapThisSwappable, the call fails. ConceptGCC never even looks at the swap() function in the Swappable concept, which would work.

If one removes the “using std::swap” line, ConceptGCC finds swap() in Swappable, and everything works. The problem is that “using std::swap” is the way that C++ programmers have been taught to write templates that use swap(), and it’s unfortunate that the only right way to handle swap in pre-concept code does not work with concepts.

This is a good reason to revisit the “lexical scoping” rule for name lookup into concepts. For instance, if having the using declaration meant only that std::swap would be overloaded with Swappable<T>::swap, the code would still work as intended.