Concepts-Lite

This experimental branch of the GCC C++ compiler implements constraints for template arguments (a.k.a., concepts lite). A (very) brief overview of the language and associated library features is found below. A paper more fully describing the language and the compiler will be made available in the near future.

This is presentation I gave at ACCU'13 at Bristol.

I have been updating the implementation and library as bugs are found. Mostly, bugs have been in the library (explained below). Files are:

The implementation is built against GCC r191411 (Sep 18, 2012). The prerequisites and build instrunctions can be found here.

Note that this is a proof of concept, so it may be unstable. The implementation is currently being refined and integrated into an official GCC branch. The implementation will also be brought into line with a more recent version of GCC.

Some problems have been found building this version of GCC on Mac OS X. This appears to be a result strnlen not being provided with that version of Mac OS X. It can be worked around, but requires modifying the GCC source.

There are some known issues with the most recent version. In particular, any declaration relying on std::result_of may fail to compile. The current implementation may fail when argument types cannot be converted to parameter types. There have been some issues with variadic templates and template parameter packs (which have prevented me from fixing std::result_of).

Note that if your code includes data types that claim to be Equality_comparable or Totally_ordered but only provides == and/or <, then your types are not compatible with the constraints provided by the standard library.

Any questions regarding the compiler or constrained templates can be directed to Andrew Sutton.

Overview

This extension of the C++ programming language allows the specification and checking of constraints on template arguments. The language features are more fully described in this very preliminary report. This is a very preliminary version of a paper that will be submitted to the WG21 committee in April. We currently soliciting comments on the proposed features. A brief overview of the proposal is presented here.

Constraints are checked at the point of use, meaning that type errors in the use of templates are caught early. Gone should be the days of multi-page errors from the use of templates.

Constraints can be specified using a shorthand notation, writing requirements as part of a template parameter's type, or via a requires clause. For example, the Standard Library's find algorithm could be declared in any of the following ways:

template<typename I, typename T>
  requires Input_iterator<I>() 
        && Equality_comparable<Value_type<I>, T>()
    I find(I first, I last, const T& value);

template<Input_iterator I, typename T>
  requires Equality_comparable<Value_type<I>, T>()
    I find(I first, I last, const T& value);

template<Input_iterator I, Equality_comparable<Value_type<I>> T>
  I find(I first, I last, const T& value);

The declarations are equivalent; they all mean the same thing. The names Input_iterator and Equality_comparable are simply constexpr predicates that evaluate type traits. There is nothing particularly special about them. For example, Equality_comparable is defined like this:

template<typename T>
  constexpr bool Equality_comparable()
  {
    return has_eq<T>::value && is_convertible<eq_result<T>, bool>::value
        && has_neq<T>::value && is_convertible<neq_result<T>, bool>::value;
  }

Constraints are similar to enable_if in the sense that constant expressions are used to enable or disable declarations based on the properties of template arguments. However, this feature is far more powerful than what can be done using only enable_if. The compiler can overload based on requirements---without tag dispatch:

template<Input_iterator I>
  Difference_type<I> distance(I first, I last)
  {
    Difference_type<I> n = 0;
    while (first != last) {
      ++first;
      ++n;
    }
    return n;
  }

template<Random_access_iterator I>
  Difference_type<I> distance(I first, I last)
  {
    return last - first;
  }

The compiler will choose the correct overload based on the properties of each constraint.

Library

The standard library shipping with this compiler includes the constraints found in the paper "A Concept Design for the STL", which can be accessed by including the <type_traits> header file. Constraints are implemented as constexpr. We also provide constraints for each (or most) of the standard type traits. Iterator constraints are in the <iterator> header file.

Please note that the library components is a work in progress. Most componets in the STL remain unconstrained. A summary of changes follows.

Fundamental Concepts

Concepts describe properties of types in terms of their use.

Iterator Concepts

Iterator cocnepts define the different flavors of iterators in the STL. The first category describe reading from and writing to (through) iterators.

Traversal concepts describe how an iterator can be advanced.

And of course, the traditional iterator hierarchy.

Algorithm Constraints

We sometimes find it useful to create constraints for classes of related algorithms. The following concepts describe operations on pairs of iterator types.

These concepts describe common requirements for related algorithms:

Type Traits

Type traits describe sets of types in the C++ type system and are often used for lower-level metaprogramming. The following are the primary type categories in C++.

The composite type traits are groups of primary types. These include:

Traits can also be used to evaluate properties of types:

These constraints have been applied only to the <algorithm> header. We are in the process of deriving constraints for other parts of the Standard Library.


(c) 2013 Andrew Sutton