Concept Traits Library

Contents

Introduction
Current Solutions
The Concept Traits Library
Synopsis
Directory Organisation
Overview
Dependencies

type_traits_ext
mpl_ext
Operator Traits
C++ Standard Concept Traits
Boost MPL Concept Traits

Performance
Compatibility
Tests
Possible Future Directions
Acknowledgements
Bibliography
Footnotes

Introduction 

As we know, there is no direct support for generic concepts in C++ (see e.g. [Austern99] for explanation of the generic programming terms concept, refinement and model). That is, we can't specify what type properties template parameters must have. For this reason, we can only hint at what properties the template parameters must have, to work with a class template or function template, using naming. For example:

template<class RandomAccessIterator>
void sort(RandomAccessIterator begin, RandomAccessIterator end)
{
  // ...
}

However, these names are of course not checked by the compiler at all; to the compiler, it's as we wrote it as:

template<class T>
void sort(T begin, T end)
{
  // ...
}

If we try to instantiate it with a type that doesn't model the RandomAccessIterator concept, we get an error, as the function attempts to use the type in a way that isn't supported by the type. However, such error messages tend to be very long and complex, pointing to an error deep in the implementation of the function, with typically no mentioning of the problem being the type of the values supplied, suggesting an error in sort(), rather than in the values.

Another problem is that we can't overload on concepts. Take the standard library function advance:

template<class InputIterator, class Distance>
void advance(InputIterator &i, Distance n)
{
  // ...
}

There are typically three implementations of this function in the standard library: one for where the iterator is InputIterator/OutputIterator/ForwardIterator, one for BidirectionalIterator, and one for RandomAccessIterator. However, these can not be written as three overloaded functions, so instead, advance() must use internal dispatching on tags (user-defined types must also supply that tag in some way, to tell what kind of iterator it is), to separate implementations of each iterator category. 

Current Solutions

One solution to the problem of unconstrained genericity (lack of support for concepts) is the Boost Concept Check Library (BCCL) [Siek00]. This library enables us to specify what concepts the template parameters have to model, or else you get an error message that is hopefully shorter and more comprehensible than without it.

Unfortunately, as the following example shows, you may still get very long error messages with BCCL (not all compilers stop after just a few instantiations, even if they give errors), and the quality of the error messages (and therefore decipherability) is also highly compiler-dependent. However, it's usually still much better than with no checking.

Example:

#include <boost/concept_check.hpp>

using namespace boost;

template<class Iterator>
void sort(Iterator begin,Iterator end)
{
  function_requires<RandomAccessIteratorConcept<Iterator> >();

  std::sort(begin,end);
}

int main()
{
  ::sort(1,1); // sort(int,int)
}

On Intel C++ 6.0 using STLPort, this gives 7-8 pages (about 300 lines) of error messages, with the first one giving no hint to the actual problem (unless you happen to know how std::iterator_traits is implemented). The situation is likely to be similar on other EDG-based compilers:

STLPORT-4.5.3\STLPORT\stl/_iterator_base.h(92): error: name followed by "::" must be a class or namespace name
    typedef typename _Iterator::iterator_category iterator_category;
                     ^

However, a few lines down, due to the use of BCCL, we get hints about the actual problem, with the mentioning of "RandomAccessIteratorConcept", "concept_check" and "function_requires":

          detected during:
            instantiation of class "_STL::iterator_traits<_Iterator> [with _Iterator=int]" at line 671 of "boost/concept_check.hpp"
            instantiation of class "boost::RandomAccessIteratorConcept<TT> [with TT=int]" at line 49 of "boost/concept_check.hpp"
            instantiation of "void boost::function_requires(boost::type<Concept> *) [with Concept=boost::RandomAccessIteratorConcept<int>]" at line 22 of "test.cpp"

Metaprogramming libraries, like MPL, due to their heavy use of templates, tend to give even longer and more cryptic error messages, often pointing deep into the instantiation stack and implementation.

Apart from this, BCCL doesn't support overloading of concepts (like the std::advance example): It's only an aid to better error messages.

The Concept Traits Library

It has been discovered relatively recently that you can overload on arbitrary properties of template parameter types, using enable_if (now part of Boost) [Hinnant03] [Järvi03]. This may be used both for function templates and class templates (with an added, default template parameter, for the latter).

This opened the door for better error messages and overloading on concepts. What remained was a way to create traits to detect concepts. With such traits, one could write:

template<class Iterator>
typename enable_if<is_random_access_iterator<Iterator> >::type
sort(Iterator begin, Iterator end)
{
  // ...
}

If used with a type not modelling RandomAccessIterator, the above example will give the following error message, on the same configuration as above (Intel C++ 6.0 and STLPort):

test.cpp(31): error: no instance of function template "sort" matches the argument list
            argument types are: (int, int)
    sort(1,1);
    ^

Rather a lot shorter and more precise. :)

This work completely analoguos to the way non-template overloading works:

class A {};
class B {};
class C {};

void sort(A,A);
void sort(B,B);

int main()
{
  C c1,c2;

  sort(c1,c2);
}

test.cpp(21): error: no instance of overloaded function "sort" matches the argument list
            argument types are: (C, C)
    sort(c1,c2);
    ^

Finally, function templates and non-template functions are treated the same way.

This would work without having to tell the compiler what concept Iterator conform to (such as with iterator_category_tag nested types): the concepts would be detected directly (!)

Likewise, the above mentioned std::advance() could now be written as three overloaded functions, in the same way, removing the need for internal dispatch on the same iterator_category_tag type.

Naturally, this extends to all kinds of concepts, not just iterators.

The operator traits/concept traits library makes the above possible, by containing type traits for detecting all the overloadable operators, all the C++ standard concepts, and all the documented Boost MPL concepts, as well as providing facilities for defining your own concept type traits.

Synopsis

The library contains:

• 46 operator type traits, covering all the overloadable (and therefore detectable) operators, as well as detection of default constructor, copy constructor and assignment operator.

• 37 C++ standard concepts type traits, covering all the concepts of the C++ standard.

• 19 Boost MPL concepts type traits, covering all the documented concepts of Boost MPL.

• Facilities for defining your own concept type traits.

• A complete set of unit tests.

• Example programs, demonstrating its use.

Directory Organisation

  boost
    |
concept_traits
    |_______________________________________________________
    |          |            |                |              |   
   std       boost       operator      type_traits_ext   mpl_ext   
    |          |            |
  detail      mpl         detail 
               |
             detail

(type_traits_ext and mpl_ext are needed to be part of the public interface, to enable people to define their own concept traits)

libs
  |
concept_traits                       
  |__________________
  |          |       |        
 test       doc   example
  |___________________________________
  |         |            |            |
 std      boost       operator      detail
            |
           mpl

Overview

The library consists of the following parts (some of it might be subsumed by existing Boost libraries, signalled by the "_ext" (extension) suffixes):

• concept_traits

• type_traits_ext

• mpl_ext

• operator 

The components in type_traits_ext and mpl_ext were originally made for the operator_traits and concept_traits, and were in the "detail" namespace. However, in order to ensure that users have access to the same facilities to create their own traits, and since they might be generally useful, these are now in the boost namespace (for type_traits_ext) and boost::mpl namespace (for mpl_ext) (the macros defines entities that may be put in any namespace, if desired, by invoking the macro in the desired namespace).

All components are in namespace boost, unless stated otherwise.

Dependencies

• type_traits_ext - MPL (just a few things, like void_<> and identity<>), mpl_ext

• mpl_ext - None

• operator - type traits, MPL, PP-lib (BOOST_PP_COMMA)

• concept_traits - type traits, MPL, PP-lib (BOOST_PP_COMMA), type_traits_ext, mpl_ext, operator_traits

These are described in the following:

type_traits_ext

This contains the following components. The reason for the macros is that the name of the entity to be detected needs to be passed in ("<string1>##<string2>" in the descriptions means concatenation of the strings <string1> and <string2>).

For all traits that detect members, these will fail with a compilation error (rather than give false) if the member is inaccessible (private or protected, unless the traits are declared as friends), as the traits use overload resolution, which occurs before access check. They have this in common with similar facilities in Boost, such as MPL's has_xxx.hpp (detecting a member type), with the rare exception of type traits' is_base_and_derived, which can detect inaccessible (and ambiguous) base classes.

Macros

BOOST_TT_EXT_DEFINE_HAS_MEMBER_TYPE(name)
BOOST_TT_EXT_DEFINE_HAS_MEMBER_CLASS_TEMPLATE(name)
BOOST_TT_EXT_DEFINE_HAS_MEMBER(name)
BOOST_TT_EXT_DEFINE_HAS_STATIC_MEMBER(name)
BOOST_TT_EXT_MEMBER_TYPE(name)
BOOST_TT_EXT_MEMBER_TYPE_CONST(name)
BOOST_TT_EXT_MEMBER_TYPE_CONST_REF(name)

Templates

has_member_function<T, MemberFunction, R [, P1, ...] >
pointer_to_member_function<F, R [, P1, ...] >

These are described in detail in the following:

BOOST_TT_EXT_DEFINE_HAS_MEMBER_TYPE(name) [1]

This defines a type trait of the form:

has_member_type_##name<T>

This gives true if T has a member type named <name>. Note, however, that this won't detect reference type members.

Example:

BOOST_TT_EXT_DEFINE_HAS_MEMBER_TYPE(type)

has_member_type_type<A> // Will detect if the class A has a (non-reference) member type called "type".

BOOST_TT_EXT_DEFINE_HAS_MEMBER_CLASS_TEMPLATE(name)

This defines a type trait of the form:

has_member_class_template_##name<T [, P1, ...] >

This gives true if T has a member class template named <name>. Any parameters for the member class template follows T in the parameter list.

Examples:

BOOST_TT_EXT_DEFINE_HAS_MEMBER_CLASS_TEMPLATE(apply)

// The following detect if the class A has a member class template named "apply", taking one type parameter.
// The parameter "int" is used to signal the number of parameters for the member class template,
// and it's also used in the test.

has_member_class_template_apply<A, int>

// The following detect if the class A has a member class template named "apply", taking three type parameters.
// The "int" arguments are used as above.

has_member_class_template_apply<A, int, int, int>

BOOST_TT_EXT_DEFINE_HAS_MEMBER(name)

This defines a type trait of the form:

has_member_##name<T>

This gives true if there exists a (non-static) class member with the signature given in T. This trait may be used with other traits, such as has_member_function<>, which detects a (non-static) member function, given a has_member_##name<> template as a parameter, and any member function parameters.

Examples:

BOOST_TT_EXT_DEFINE_HAS_MEMBER(value)

has_member_value<bool A::*> // Will detect if the class A has a (non-static) bool member variable named "value".

BOOST_TT_EXT_DEFINE_HAS_MEMBER(swap)

has_member_swap<void (A::*)(A &)> // Will detect if the class A has a (non-static) member function named "swap" with the given signature.

BOOST_TT_EXT_DEFINE_HAS_STATIC_MEMBER(name)

This defines a type trait of the form:

has_static_member_##name<T, Type>

This gives true if T has a static member (variable or function). with the type Type.

Examples:

BOOST_TT_EXT_DEFINE_HAS_STATIC_MEMBER(value)

has_static_member_value<A, const bool> // Will detect if the class A has a static const bool member variable named "value".

BOOST_TT_EXT_DEFINE_HAS_STATIC_MEMBER(create)

has_static_member_create<A, A ()> // Will detect if the class A has a static member function named "create" taking no parameters and returning A.

BOOST_TT_EXT_MEMBER_TYPE(name)

This defines a type trait of the form:

member_type_##name<T>

This returns the member type of T named <name> as "type" (essentially changing the name of the member type). This is useful in combination with other traits, expecting the standard "type" member.

Example (has_member_function is described further down):

BOOST_TT_EXT_DEFINE_HAS_MEMBER(size)
BOOST_TT_EXT_MEMBER_TYPE(size_type)

has_member_function<
  const T,
  has_member_size,
  member_type_size_type<T>
>

This trait detects if the type T has a (non-static) const member function named "size", returning a value of type T::size_type. I.e. the signature of the member function is "T::size_type size() const"

An alternative way of detecting this is to use:

has_member_size<T::size_type size() const>

At first, this may seem like a simpler solution, but alas, it can't be used as a general trait, as the "T::size_type" part will give an error if instantiated with a type not having this member type (rather than false). The has_member_function form does not suffer from this problem, due to its lazy evaluation. As the example shows, the has_member_function instantiation actually uses the has_member_size template.

BOOST_TT_EXT_MEMBER_TYPE_CONST(name)

This defines a type trait of the form:

member_type_const_##name<T>

This works like member_type_##name<T>, except that it returns "const T::name" as "type". This may be done with the following, but is provided for convenience when used with lazy evaluation:

add_const<member_type_##name<T>::type>

BOOST_TT_EXT_MEMBER_TYPE_CONST_REF(name)

This defines a type trait of the form:

member_type_const_ref_##name<T>

This works like member_type_##name<T>, except that it returns "const T::name &" as "type", for the same reason as given for member_type_const_##name<T>

has_member_function<T, MemberFunction, R [, P1, ...] >

This gives true if T has a (non-static) member function MemberFunction (which is a class template given by has_member_##name), with any parameters given as P1, P2, P3 etc.

An example is given for BOOST_TT_EXT_MEMBER_TYPE.

pointer_to_member_function<F, R [, P1, ...] >

This returns the type R (T::*)([P1, ...]) [const] as "type". If T is const qualified, the member function is, as well. It is used in the implementation of has_member_function, and might be better to have in the "detail" namespace, but might also be useful on its own.

mpl_ext

This contains the following components, which are useful for lazy evaluation (all being in the boost::mpl namespace):

eval<T>

This takes a class template-id and "evaluates" its arguments, and the template-id, returning the result as the nested type "type".

Example:

typedef eval<A<X> >::type type;

"type" will here be A<X::type>::type.

eval_args<T>

This is similar to eval<>, but does not evaluate the result of the template-id, returning instead the template-id as the nested type "type".

Example:

typedef eval_args<A<X> >::type type;

"type" will here be A<X::type>

Operator Traits

The default constructor and copy constructor are not operators, but since they are unnamed, special member functions, they are still included in this library, not at least because they are needed to implement the corresponding concept traits (is_default_constructible and is_copy_constructible).

Note: The operator traits will fail with a compiler error for user-defined operators returning void.

For type traits taking two template parameters, the second parameter is optional, and if omitted, equals the first parameter. In the following table, a is an instance of T (or T1), b is an instance of T2, and p1 is an instance of P1.

C++ Standard Concept Traits

For type traits taking two template parameters, the second parameter is optional, and if omitted, equals the first parameter. In the following table, a is an instance of T (or T1) and b is an instance of T2.

Boost MPL Concept Traits

For type traits taking two template parameters, the second parameter is optional, and if omitted, equals the first parameter. In the following table, a is an instance of T (or T1) and b is an instance of T2.

These type traits are put in the boost::mpl namespace, both because they concern MPL, and also to prevent clashes with C++ standard concepts of the same name (e.g. TrivialIterator).

References

[1] [Austern99]

[2] Boost MPL reference

Performance

As the operator traits and concept traits involve potentially rather long instantiation sequences, there might be performance issues with compilation time, but this has not yet been investigated to any extent, as the traits have mostly been tested with small examples (except the unit tests, which take a long time to compile, but which contain thousands of tests and so hardly represent "typical code").

Compatibility

The library has been tested on Intel C++ 7.1, MSVC 7.1 and g++ 3.2.

All tests pass on Intel C++ 7.1 and MSVC 7.1. For g++ 3.2, the operator traits tests pass, but most of the concept traits fails (either at compile time, or give wrong result). I intend to work to make the library work on g++ 3.2, as well.

When running the unit tests, g++ 3.2 gives warnings about passing non-POD through a ...-function (which doesn't happen; it's only used for overload resolution - the call is never made), and some other warnings from Boost type traits, which you may want to turn off (using the "-w" option - turn off all warnings, or something less drastic). If you don't, then running the unit tests for the operator traits gives so many warnings that it stops compiling, and outputs:

"[General Error] Too many messages; abort.
There must be something terribly wrong with your code. Please fix it."

:P

For g++ you may also need to set the -ftemplate-depth-<n> option.

Tests

The library comes with a complete set of unit tests (meaning that all parts are tested). The type_traits_ext and mpl_ext components, due to their origin as implementation details, do not yet have separate tests, but are tested as part of the operator_traits and concept_traits unit tests.

As noted above, the unit tests takes a very long time to compile (but runs in a fraction of a second), as each test (operator traits, standard C++ concepts traits, and Boost.MPL concepts traits) uses MPL to construct a test matrix on the fly, testing each trait in a list against a list of types to test for. The total number of tests generated is several thousand.

To provide faster compilation, this might be done differently, but the advantage of it is no requirement of external preprocessing, and avoiding code duplication.

Possible Future Directions

• Make the traits MPL lambda compatible.

• Implement concept traits for the standards proposal new iterator concepts, N1640.

• Use Boost.PP-lib to remove some of the repetitive code some places in the implementation, as well as removing some arbitrary limitation on the number of arguments of templates and functions to be detected (pointer_to_member_function.hpp, has_member_class_template.hpp, eval.hpp and eval_args.hpp comes to mind).

• Split the three unit test files (for operator traits, concept traits for C++ standard, and concept traits for MPL) into one per trait (like Boost type traits). This makes of course each test run much faster, and also uses a lot less memory to run the tests (g++ 3.2 uses more than 250 MB to compile the full operator traits unit test). This splitting wasn't done in order to keep the number of files for the library down, but may be done if considered useful.

Acknowledgements

A lot of people contributed to this library (directly or indirectly). More to come here, but in addition to the people behind enable_if (Howard Hinnant, Jaakko Järvi, Jeremiah Willcock, Andrew Lumsdaine, and possibly more) and isAddable (Dietmar Kuehl, Jaakko Jarvi, Jeremy Siek, Mat Marcus and Dave Abrahams), they include Aleksey Gurtovoy for MPL, and Paul Mensonides, for advanced C++ type introspection, and Richard Crossley for eval<>. These people's - as well as other Boost authors's and participants's - "diagonal"/"out of the box" thinking have given us things we haven't even dreamt about earlier.

Bibliography

• [Austern99] Matthew H. Austern, Generic Programming and the STL: Using and Extending the Standard Template Library, 1999

• [Hinnant03] Howard Hinnant, Jaakko Järvi and Jeremiah Willcock, Function Overloading Based on Arbitrary Properties of Types, 2003

• [Järvi03]  Jaakko Järvi, Jeremiah Willcock, Andrew Lumsdaine, boost::enable_if, 2003

• [Siek00] Jeremy Siek, The Boost Concept Check Library, 2000

• [Stroustrup03_1] Bjarne Stroustrup, N1510: Concept checking - A more abstract complement to type checking, 2003

• [Stroustrup03_2] B. Stroustrup, G. Dos Reis, N1522: Concepts - Design choices for template argument checking, 2003

• [Stroustrup03_3] B. Stroustrup, G. Dos Reis, N1536: Concepts - syntax and composition, 2003 

Footnotes

[1] MPL now has a has_xxx.hpp header, which appears to do the same as type_traits_ext/has_member_type.hpp. However, at the time of the start of this library, the MPL version was neither in the public interface (it was in the "detail" namespace), nor documented, so I couldn't rely on it. has_member_type.hpp is included in type_traits_ext for completeness, as it may be more of a type trait, than a type computation. It might be replaced by the MPL version, especially as it seems the MPL version handles reference types, as well.

12 September 2004

Documentation © Copyright Terje Slettebø and Tobias Schwinger 2004. Use, modification and distribution are subject to the Boost Software License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt).

Maintained by Terje Slettebø and Tobias Schwinger, the latest version of the library can be found at http://www.neoscientists.org.