<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN"
"http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
<html xmlns="http://www.w3.org/1999/xhtml">
<!-- Copyright (c) 2000 Jeremy Siek and Andrew Lumsdaine, 2007 David Abrahams -->
<!-- Distributed under 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) -->
<head>
<meta name="generator" content=
"HTML Tidy for Linux/x86 (vers 1 September 2005), see www.w3.org" />
<meta http-equiv="Content-Type" content="text/html; charset=utf-8" />
<title>Concept Check Library</title>
<link rel="stylesheet" href="../../rst.css" type="text/css" />
</head>
<body bgcolor="#FFFFFF" link="#0000EE" text="#000000" vlink="#551A8B" alink=
"#FF0000">
<img src="../../boost.png" alt="C++ Boost" width="277" height=
"86" /><br clear="none" />
<h1>The Boost Concept Check Library (BCCL)</h1>
<blockquote>
The Concept Check library allows one to add explicit statement and
checking of <a href=
"http://www.boost.org/more/generic_programming.html#concept">concepts</a> in the style
of the <a href=
"http://www.generic-programming.org/languages/conceptcpp/specification/">proposed
C++ language extension</a>.
</blockquote>
<h2><a name="sec:concept-checking" id="sec:concept-checking"></a>Synopsis</a></h2>
<p>Generic programming in C++ is characterized by the use of template
parameters to represent abstract data types (or “<a href=
"http://www.boost.org/more/generic_programming.html#concept">concepts</a>”). However, the
C++ language itself does not provide a mechanism for the writer of a class
or function template to explicitly state the concept that the user-supplied
template argument should model (or conform to). Template parameters are
commonly named after the concept they're required to model as a hint to the
user, and to make the concept requirements explicit in code. However, the
compiler doesn't treat these special names specially: a parameter named
<code>RandomAccessIterator</code> is no different to the compiler than one
named <code>T</code>. Furthermore,</p>
<ul>
<li>Compiler error messages resulting from incorrect template arguments
can be particularly difficult to decipher. Often times the error does not
point to the location of the template call-site, but instead exposes the
internals of the template, which the user should never have to see.</li>
<li>Without checking from the compiler, the documented requirements are
oftentimes vague, incorrect, or nonexistent, so a user cannot know
exactly what kind of arguments are expected.</li>
<li>The documented concept requirements may not fully <i>cover</i> the
needs of the actual template, meaning the user could get a compiler error
even though the supplied template arguments meet the documented
requirements.</li>
<li>The documented concept requirements may be too stringent, requiring
more than is really needed by the template.</li>
<li>Concept names in code may drift out-of-sync with the documented
requirements.</li>
</ul><p>The Boost Concept Checking Library provides:
<ul>
<li>A mechanism for inserting compile-time checks on template parameters
at their point of use.</li>
<li>A framework for specifying concept requirements through concept
checking classes.</li>
<li>A mechanism for verifying that concept requirements cover the
template.</li>
<li>A suite of concept checking classes and archetype classes that match
the concept requirements in the C++ Standard Library.</li>
<li>An alternative to the use of traits classes for accessing associated
types that mirrors the syntax proposed for the next C++ standard.</li>
</ul><p>The mechanisms use standard C++ and introduce no run-time overhead.
The main cost of using the mechanism is in compile-time.</p>
<p><strong>Every programmer writing class or function templates ought to
make concept checking a normal part of their code writing routine.</strong>
A concept check should be inserted for each template parameter in a
component's public interface. If the concept is one of the ones from the
Standard Library, then simply use the matching concept checking class in
the BCCL. If not, then write a new concept checking class - after all, they
are typically only a few lines long. For new concepts, a matching archetype
class should also be created, which is a minimal skeleton-implementation of
the concept</p>
<p>The documentation is organized into the following sections.</p>
<ol>
<li><a href="#introduction">Introduction</a></li>
<li><a href="#motivating-example">Motivating Example</a></li>
<li><a href="#history">History</a></li>
<li><a href="#publications">Publications</a></li>
<li><a href="#acknowledgements">Acknowledgements</a></li>
<li><a href="./using_concept_check.htm">Using Concept Checks</a></li>
<li><a href="creating_concepts.htm">Creating Concept Checking
Classes</a></li>
<li><a href="./concept_covering.htm">Concept Covering and
Archetypes</a></li>
<li><a href="./prog_with_concepts.htm">Programming With Concepts</a></li>
<li><a href="./implementation.htm">Implementation</a></li>
<li><a href="./reference.htm">Reference</a></li>
</ol>
<p><a href="http://www.boost.org/people/jeremy_siek.htm">Jeremy Siek</a> contributed this
library. <a href="http://www.boost.org/people/beman_dawes.html">Beman Dawes</a> managed
the formal review. <a href="http://www.boost.org/people/dave_abrahams.htm">Dave
Abrahams</a> contributed a rewrite that updated syntax to be more
compatible with proposed syntax for concept support the C++ core
language.</p>
<h2><a name="introduction" id="introduction">Introduction</a></h2><p>A
<i>concept</i> is a set of requirements (valid expressions, associated
types, semantic invariants, complexity guarantees, etc.) that a type must
fulfill to be correctly used as arguments in a call to a generic algorithm.
In C++, concepts are represented by formal template parameters to function
templates (generic algorithms). However, C++ has no explicit mechanism for
representing concepts—template parameters are merely placeholders. By
convention, these parameters are given names corresponding to the concept
that is required, but a C++ compiler does not enforce compliance to the
concept when the template parameter is bound to an actual type.
<p>Naturally, if a generic algorithm is invoked with a type that does not
fulfill at least the syntactic requirements of the concept, a compile-time
error will occur. However, this error will not <i>per se</i> reflect the
fact that the type did not meet all of the requirements of the concept.
Rather, the error may occur deep inside the instantiation hierarchy at the
point where an expression is not valid for the type, or where a presumed
associated type is not available. The resulting error messages are largely
uninformative and basically impenetrable.</p>
<p>What is required is a mechanism for enforcing
“concept safety” at (or close to) the point
of instantiation. The Boost Concept Checking Library uses some standard C++
constructs to enforce early concept compliance and that provides more
informative error messages upon non-compliance.</p>
<p>Note that this technique only addresses the syntactic requirements of
concepts (the valid expressions and associated types). We do not address
the semantic invariants or complexity guarantees, which are also part of
concept requirements..</p>
<h2><a name="motivating-example" id="motivating-example">Motivating
Example</a></h2>
<p>We present a simple example to illustrate incorrect usage of a template
library and the resulting error messages. In the code below, the generic
<tt>std::stable_sort()</tt> algorithm from the Standard Template Library
(STL)[<a href="bibliography.htm#austern99:_gener_progr_stl">3</a>, <a href=
"bibliography.htm#IB-H965502">4</a>,<a href=
"bibliography.htm#stepa.lee-1994:the.s:TR">5</a>] is applied to a linked
list.</p>
<pre>
<a href="./bad_error_eg.cpp">bad_error_eg.cpp</a>:
<font color="gray">1</font> #include <vector>
<font color="gray">2</font color="gray"> #include <complex>
<font color="gray">3</font color="gray"> #include <algorithm>
<font color="gray">4</font color="gray">
<font color="gray">5</font color="gray"> int main()
<font color="gray">6</font color="gray"> {
<font color="gray">7</font color="gray"> std::vector<std::complex<float> > v;
<font color="gray">8</font color="gray"> std::stable_sort(v.begin(), v.end());
<font color="gray">9</font color="gray"> }
</pre>
<p>Here, the <tt>std::stable_sort()</tt> algorithm is prototyped as
follows:</p>
<pre>
template <class RandomAccessIterator>
void stable_sort(RandomAccessIterator first, RandomAccessIterator last);
</pre>
<p>Attempting to compile this code with Gnu C++ produces the following
compiler error:</p>
<pre>
/usr/include/c++/4.1.2/bits/stl_algo.h: In function ‘void std::
__insertion_sort(_RandomAccessIterator, _RandomAccessIterator) [with
_RandomAccessIterator = __gnu_cxx::__normal_iterator<std::complex<float
>*, std::vector<std::complex<float>, std::allocator<std::complex<
float> > > >]’:
/usr/include/c++/4.1.2/bits/stl_algo.h:3066: instantiated from ‘void
std::__inplace_stable_sort(_RandomAccessIterator,
_RandomAccessIterator) [with _RandomAccessIterator = __gnu_cxx::
__normal_iterator<std::complex<float>*, std::vector<std::complex<
float>, std::allocator<std::complex<float> > > >]’
/usr/include/c++/4.1.2/bits/stl_algo.h:3776: instantiated from ‘void
std::stable_sort(_RandomAccessIterator, _RandomAccessIterator) [with
_RandomAccessIterator = __gnu_cxx::__normal_iterator<std::complex<float
>*, std::vector<std::complex<float>, std::allocator<std::complex<
float> > > >]’
bad_error_eg.cpp:8: instantiated from here
/usr/include/c++/4.1.2/bits/stl_algo.h:2277: error: no match for
‘operator<’ in ‘__val < __first. __gnu_cxx::__normal_iterator<
_Iterator, _Container>::operator* [with _Iterator = std::complex<float
>*, _Container = std::vector<std::complex<float>, std::allocator<
std::complex<float> > >]()’
</pre>
<p>In this case, the fundamental error is
that <tt>std:complex<float></tt> does not model the <a href=
"http://www.sgi.com/tech/stl/LessThanComparable.html">LessThanComparable</a>
concept. Unfortunately, there is nothing in the error message to
indicate that to the user.</p>
<p>The error may be obvious to a C++ programmer having enough
experience with template libraries, but there are several reasons
why this message could be hard for the uninitiated to
understand:</p>
<ol>
<li>There is no textual correlation between the error message and the
documented requirements for <tt>std::stable_sort()</tt> and for <a href=
"http://www.sgi.com/tech/stl/LessThanComparable.html">LessThanComparable</a>.</li>
<li>The error message is overly long, listing functions internal
to the STL (e.g. <code>__insertion_sort</code>) that the user
does not (and should not!) know or care about.</li>
<li>With so many internal library functions listed in the error message,
the programmer could easily infer that the problem is in the library,
rather than in his or her own code.</li>
</ol>
<p>The following is an example of what we might expect from a more
informative message (and is in fact what the Boost Concept Checking Library
produces):</p>
<pre>
boost/concept_check.hpp: In destructor ‘boost::LessThanComparable<TT>::~
LessThanComparable() [with TT = std::complex<float>]’:
boost/concept/detail/general.hpp:29: instantiated from ‘static void boost::
concepts::requirement<Model>::failed() [with Model = boost::
LessThanComparable<std::complex<float> >]’
boost/concept/requires.hpp:30: instantiated from ‘boost::_requires_<void
(*)(boost::LessThanComparable<std::complex<float> >)>’
bad_error_eg.cpp:8: instantiated from here
boost/concept_check.hpp:236: error: no match for ‘operator<’ in ‘((boost::
LessThanComparable<std::complex<float> >*)this)->boost::
LessThanComparable<std::complex<float> >::a < ((boost::
LessThanComparable<std::complex<float> >*)this)->boost::
LessThanComparable<std::complex<float> >::b’
</pre>
<p>This message rectifies several of the shortcomings of the standard error
messages.</p>
<ul>
<li>The message refers explicitly to concepts that the user can look up
in the STL documentation (<a href=
"http://www.sgi.com/tech/stl/LessThanComparable.html">LessThanComparable</a>).</li>
<li>The error message is now much shorter and does not reveal
internal STL functions, nor indeed does it even point
to <code>std::stable_sort</code>.</li>
<li>The presence of <tt>concept_check.hpp</tt> in the error message
alerts the user to the fact that the error lies in the user code and not
in the library implementation.</li>
</ul>
<h2><a name="history" id="history">History</a></h2>
<p>The first version of this concept checking system was developed
by Jeremy Siek while working at SGI in their C++ compiler and
library group. That version is now part of the SGI STL
distribution. The system originally introduced as the boost concept
checking library differs from concept checking in the SGI STL in
that the definition of concept checking classes was greatly
simplified, at the price of less helpful verbiage in the error
messages. In 2006 the system was rewritten (preserving backward
compatibility) by Dave Abrahams to be easier to use, more similar to
the proposed concept support the C++ core language, and to give
better error messages.
</p>
<h2><a name="publications" id="publications">Publications</a></h2>
<ul>
<li><a href="http://www.oonumerics.org/tmpw00/">C++ Template Workshop
2000</a>, Concept Checking</li>
</ul>
<h2><a name="acknowledgements" id=
"acknowledgements">Acknowledgements</a></h2><p>The idea to use function
pointers to cause instantiation is due to Alexander Stepanov. We are not sure
of the origin of the idea to use expressions to do up-front checking of
templates, but it did appear in D&E[ <a href=
"bibliography.htm#stroustrup94:_design_evolution">2</a>]. Thanks to Matt
Austern for his excellent documentation and organization of the STL
concepts, upon which these concept checks are based. Thanks to Boost
members for helpful comments and reviews.
<p><a href="./using_concept_check.htm">Next: Using Concept
Checks</a><br /></p>
<hr />
<table>
<tr valign="top">
<td nowrap="nowrap">Copyright © 2000</td>
<td><a href="http://www.boost.org/people/jeremy_siek.htm">Jeremy Siek</a>(<a href=
"mailto:jsiek@osl.iu.edu">jsiek@osl.iu.edu</a>) Andrew
Lumsdaine(<a href="mailto:lums@osl.iu.edu">lums@osl.iu.edu</a>),
2007 <a href="mailto:dave@boost-consulting.com">David Abrahams</a>.
</td>
</tr>
</table>
</body>
</html>