1<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" 2 "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd"> 3 4<html xmlns="http://www.w3.org/1999/xhtml"> 5<!-- Copyright (c) 2000 Jeremy Siek and Andrew Lumsdaine, 2007 David Abrahams --> 6<!-- Distributed under the Boost --> 7<!-- Software License, Version 1.0. (See accompanying --> 8<!-- file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt) --> 9 10<head> 11 <meta name="generator" content= 12 "HTML Tidy for Linux/x86 (vers 1 September 2005), see www.w3.org" /> 13 <meta http-equiv="Content-Type" content="text/html; charset=utf-8" /> 14 15 <title>Concept Check Library</title> 16 <link rel="stylesheet" href="../../rst.css" type="text/css" /> 17</head> 18 19<body bgcolor="#FFFFFF" link="#0000EE" text="#000000" vlink="#551A8B" alink= 20"#FF0000"> 21 <img src="../../boost.png" alt="C++ Boost" width="277" height= 22 "86" /><br clear="none" /> 23 24 <h1>The Boost Concept Check Library (BCCL)</h1> 25 26 <blockquote> 27 The Concept Check library allows one to add explicit statement and 28 checking of <a href= 29 "http://www.boost.org/more/generic_programming.html#concept">concepts</a> in the style 30 of the <a href= 31 "http://www.generic-programming.org/languages/conceptcpp/specification/">proposed 32 C++ language extension</a>. 33 </blockquote> 34 35 <h2><a name="sec:concept-checking" id="sec:concept-checking"></a>Synopsis</a></h2> 36 37 <p>Generic programming in C++ is characterized by the use of template 38 parameters to represent abstract data types (or “<a href= 39 "http://www.boost.org/more/generic_programming.html#concept">concepts</a>”). However, the 40 C++ language itself does not provide a mechanism for the writer of a class 41 or function template to explicitly state the concept that the user-supplied 42 template argument should model (or conform to). Template parameters are 43 commonly named after the concept they're required to model as a hint to the 44 user, and to make the concept requirements explicit in code. However, the 45 compiler doesn't treat these special names specially: a parameter named 46 <code>RandomAccessIterator</code> is no different to the compiler than one 47 named <code>T</code>. Furthermore,</p> 48 49 <ul> 50 <li>Compiler error messages resulting from incorrect template arguments 51 can be particularly difficult to decipher. Often times the error does not 52 point to the location of the template call-site, but instead exposes the 53 internals of the template, which the user should never have to see.</li> 54 55 <li>Without checking from the compiler, the documented requirements are 56 oftentimes vague, incorrect, or nonexistent, so a user cannot know 57 exactly what kind of arguments are expected.</li> 58 59 <li>The documented concept requirements may not fully <i>cover</i> the 60 needs of the actual template, meaning the user could get a compiler error 61 even though the supplied template arguments meet the documented 62 requirements.</li> 63 64 <li>The documented concept requirements may be too stringent, requiring 65 more than is really needed by the template.</li> 66 67 <li>Concept names in code may drift out-of-sync with the documented 68 requirements.</li> 69 </ul><p>The Boost Concept Checking Library provides: 70 71 <ul> 72 <li>A mechanism for inserting compile-time checks on template parameters 73 at their point of use.</li> 74 75 <li>A framework for specifying concept requirements through concept 76 checking classes.</li> 77 78 <li>A mechanism for verifying that concept requirements cover the 79 template.</li> 80 81 <li>A suite of concept checking classes and archetype classes that match 82 the concept requirements in the C++ Standard Library.</li> 83 84 <li>An alternative to the use of traits classes for accessing associated 85 types that mirrors the syntax proposed for the next C++ standard.</li> 86 </ul><p>The mechanisms use standard C++ and introduce no run-time overhead. 87 The main cost of using the mechanism is in compile-time.</p> 88 89 <p><strong>Every programmer writing class or function templates ought to 90 make concept checking a normal part of their code writing routine.</strong> 91 A concept check should be inserted for each template parameter in a 92 component's public interface. If the concept is one of the ones from the 93 Standard Library, then simply use the matching concept checking class in 94 the BCCL. If not, then write a new concept checking class - after all, they 95 are typically only a few lines long. For new concepts, a matching archetype 96 class should also be created, which is a minimal skeleton-implementation of 97 the concept</p> 98 99 <p>The documentation is organized into the following sections.</p> 100 101 <ol> 102 <li><a href="#introduction">Introduction</a></li> 103 104 <li><a href="#motivating-example">Motivating Example</a></li> 105 106 <li><a href="#history">History</a></li> 107 108 <li><a href="#publications">Publications</a></li> 109 110 <li><a href="#acknowledgements">Acknowledgements</a></li> 111 112 <li><a href="./using_concept_check.htm">Using Concept Checks</a></li> 113 114 <li><a href="creating_concepts.htm">Creating Concept Checking 115 Classes</a></li> 116 117 <li><a href="./concept_covering.htm">Concept Covering and 118 Archetypes</a></li> 119 120 <li><a href="./prog_with_concepts.htm">Programming With Concepts</a></li> 121 122 <li><a href="./implementation.htm">Implementation</a></li> 123 124 <li><a href="./reference.htm">Reference</a></li> 125 </ol> 126 127 <p><a href="http://www.boost.org/people/jeremy_siek.htm">Jeremy Siek</a> contributed this 128 library. <a href="http://www.boost.org/people/beman_dawes.html">Beman Dawes</a> managed 129 the formal review. <a href="http://www.boost.org/people/dave_abrahams.htm">Dave 130 Abrahams</a> contributed a rewrite that updated syntax to be more 131 compatible with proposed syntax for concept support the C++ core 132 language.</p> 133 134 <h2><a name="introduction" id="introduction">Introduction</a></h2><p>A 135 <i>concept</i> is a set of requirements (valid expressions, associated 136 types, semantic invariants, complexity guarantees, etc.) that a type must 137 fulfill to be correctly used as arguments in a call to a generic algorithm. 138 In C++, concepts are represented by formal template parameters to function 139 templates (generic algorithms). However, C++ has no explicit mechanism for 140 representing concepts—template parameters are merely placeholders. By 141 convention, these parameters are given names corresponding to the concept 142 that is required, but a C++ compiler does not enforce compliance to the 143 concept when the template parameter is bound to an actual type. 144 145 <p>Naturally, if a generic algorithm is invoked with a type that does not 146 fulfill at least the syntactic requirements of the concept, a compile-time 147 error will occur. However, this error will not <i>per se</i> reflect the 148 fact that the type did not meet all of the requirements of the concept. 149 Rather, the error may occur deep inside the instantiation hierarchy at the 150 point where an expression is not valid for the type, or where a presumed 151 associated type is not available. The resulting error messages are largely 152 uninformative and basically impenetrable.</p> 153 154 <p>What is required is a mechanism for enforcing 155 “concept safety” at (or close to) the point 156 of instantiation. The Boost Concept Checking Library uses some standard C++ 157 constructs to enforce early concept compliance and that provides more 158 informative error messages upon non-compliance.</p> 159 160 <p>Note that this technique only addresses the syntactic requirements of 161 concepts (the valid expressions and associated types). We do not address 162 the semantic invariants or complexity guarantees, which are also part of 163 concept requirements..</p> 164 165 <h2><a name="motivating-example" id="motivating-example">Motivating 166 Example</a></h2> 167 168 <p>We present a simple example to illustrate incorrect usage of a template 169 library and the resulting error messages. In the code below, the generic 170 <tt>std::stable_sort()</tt> algorithm from the Standard Template Library 171 (STL)[<a href="bibliography.htm#austern99:_gener_progr_stl">3</a>, <a href= 172 "bibliography.htm#IB-H965502">4</a>,<a href= 173 "bibliography.htm#stepa.lee-1994:the.s:TR">5</a>] is applied to a linked 174 list.</p> 175 <pre> 176 <a href="./bad_error_eg.cpp">bad_error_eg.cpp</a>: 177<font color="gray">1</font> #include <vector> 178<font color="gray">2</font color="gray"> #include <complex> 179<font color="gray">3</font color="gray"> #include <algorithm> 180<font color="gray">4</font color="gray"> 181<font color="gray">5</font color="gray"> int main() 182<font color="gray">6</font color="gray"> { 183<font color="gray">7</font color="gray"> std::vector<std::complex<float> > v; 184<font color="gray">8</font color="gray"> std::stable_sort(v.begin(), v.end()); 185<font color="gray">9</font color="gray"> } 186</pre> 187 188 <p>Here, the <tt>std::stable_sort()</tt> algorithm is prototyped as 189 follows:</p> 190 <pre> 191 template <class RandomAccessIterator> 192 void stable_sort(RandomAccessIterator first, RandomAccessIterator last); 193</pre> 194 195 <p>Attempting to compile this code with Gnu C++ produces the following 196 compiler error:</p> 197 <pre> 198/usr/include/c++/4.1.2/bits/stl_algo.h: In function ‘void std:: 199 __insertion_sort(_RandomAccessIterator, _RandomAccessIterator) [with 200 _RandomAccessIterator = __gnu_cxx::__normal_iterator<std::complex<float 201 >*, std::vector<std::complex<float>, std::allocator<std::complex< 202 float> > > >]’: 203/usr/include/c++/4.1.2/bits/stl_algo.h:3066: instantiated from ‘void 204 std::__inplace_stable_sort(_RandomAccessIterator, 205 _RandomAccessIterator) [with _RandomAccessIterator = __gnu_cxx:: 206 __normal_iterator<std::complex<float>*, std::vector<std::complex< 207 float>, std::allocator<std::complex<float> > > >]’ 208/usr/include/c++/4.1.2/bits/stl_algo.h:3776: instantiated from ‘void 209 std::stable_sort(_RandomAccessIterator, _RandomAccessIterator) [with 210 _RandomAccessIterator = __gnu_cxx::__normal_iterator<std::complex<float 211 >*, std::vector<std::complex<float>, std::allocator<std::complex< 212 float> > > >]’ 213bad_error_eg.cpp:8: instantiated from here 214/usr/include/c++/4.1.2/bits/stl_algo.h:2277: error: no match for 215 ‘operator<’ in ‘__val < __first. __gnu_cxx::__normal_iterator< 216 _Iterator, _Container>::operator* [with _Iterator = std::complex<float 217 >*, _Container = std::vector<std::complex<float>, std::allocator< 218 std::complex<float> > >]()’ 219</pre> 220 221 <p>In this case, the fundamental error is 222 that <tt>std:complex<float></tt> does not model the <a href= 223 "http://www.boost.org/sgi/stl/LessThanComparable.html">LessThanComparable</a> 224 concept. Unfortunately, there is nothing in the error message to 225 indicate that to the user.</p> 226 227 <p>The error may be obvious to a C++ programmer having enough 228 experience with template libraries, but there are several reasons 229 why this message could be hard for the uninitiated to 230 understand:</p> 231 232 <ol> 233 <li>There is no textual correlation between the error message and the 234 documented requirements for <tt>std::stable_sort()</tt> and for <a href= 235 "http://www.boost.org/sgi/stl/LessThanComparable.html">LessThanComparable</a>.</li> 236 237 <li>The error message is overly long, listing functions internal 238 to the STL (e.g. <code>__insertion_sort</code>) that the user 239 does not (and should not!) know or care about.</li> 240 241 <li>With so many internal library functions listed in the error message, 242 the programmer could easily infer that the problem is in the library, 243 rather than in his or her own code.</li> 244 </ol> 245 246 <p>The following is an example of what we might expect from a more 247 informative message (and is in fact what the Boost Concept Checking Library 248 produces):</p> 249 <pre> 250boost/concept_check.hpp: In destructor ‘boost::LessThanComparable<TT>::~ 251 LessThanComparable() [with TT = std::complex<float>]’: 252boost/concept/detail/general.hpp:29: instantiated from ‘static void boost:: 253 concepts::requirement<Model>::failed() [with Model = boost:: 254 LessThanComparable<std::complex<float> >]’ 255boost/concept/requires.hpp:30: instantiated from ‘boost::_requires_<void 256 (*)(boost::LessThanComparable<std::complex<float> >)>’ 257bad_error_eg.cpp:8: instantiated from here 258boost/concept_check.hpp:236: error: no match for ‘operator<’ in ‘((boost:: 259 LessThanComparable<std::complex<float> >*)this)->boost:: 260 LessThanComparable<std::complex<float> >::a < ((boost:: 261 LessThanComparable<std::complex<float> >*)this)->boost:: 262 LessThanComparable<std::complex<float> >::b’ 263</pre> 264 265 <p>This message rectifies several of the shortcomings of the standard error 266 messages.</p> 267 268 <ul> 269 <li>The message refers explicitly to concepts that the user can look up 270 in the STL documentation (<a href= 271 "http://www.boost.org/sgi/stl/LessThanComparable.html">LessThanComparable</a>).</li> 272 273 <li>The error message is now much shorter and does not reveal 274 internal STL functions, nor indeed does it even point 275 to <code>std::stable_sort</code>.</li> 276 277 <li>The presence of <tt>concept_check.hpp</tt> in the error message 278 alerts the user to the fact that the error lies in the user code and not 279 in the library implementation.</li> 280 </ul> 281 282 <h2><a name="history" id="history">History</a></h2> 283 284 <p>The first version of this concept checking system was developed 285 by Jeremy Siek while working at SGI in their C++ compiler and 286 library group. That version is now part of the SGI STL 287 distribution. The system originally introduced as the boost concept 288 checking library differs from concept checking in the SGI STL in 289 that the definition of concept checking classes was greatly 290 simplified, at the price of less helpful verbiage in the error 291 messages. In 2006 the system was rewritten (preserving backward 292 compatibility) by Dave Abrahams to be easier to use, more similar to 293 the proposed concept support the C++ core language, and to give 294 better error messages. 295</p> 296 297 <h2><a name="publications" id="publications">Publications</a></h2> 298 299 <ul> 300 <li><a href="http://www.oonumerics.org/tmpw00/">C++ Template Workshop 301 2000</a>, Concept Checking</li> 302 </ul> 303 304 <h2><a name="acknowledgements" id= 305 "acknowledgements">Acknowledgements</a></h2><p>The idea to use function 306 pointers to cause instantiation is due to Alexander Stepanov. We are not sure 307 of the origin of the idea to use expressions to do up-front checking of 308 templates, but it did appear in D&E[ <a href= 309 "bibliography.htm#stroustrup94:_design_evolution">2</a>]. Thanks to Matt 310 Austern for his excellent documentation and organization of the STL 311 concepts, upon which these concept checks are based. Thanks to Boost 312 members for helpful comments and reviews. 313 314 <p><a href="./using_concept_check.htm">Next: Using Concept 315 Checks</a><br /></p> 316 <hr /> 317 318 <table> 319 <tr valign="top"> 320 <td nowrap="nowrap">Copyright © 2000</td> 321 322 <td><a href="http://www.boost.org/people/jeremy_siek.htm">Jeremy Siek</a>(<a href= 323 "mailto:jsiek@osl.iu.edu">jsiek@osl.iu.edu</a>) Andrew 324 Lumsdaine(<a href="mailto:lums@osl.iu.edu">lums@osl.iu.edu</a>), 325 2007 <a href="mailto:dave@boost-consulting.com">David Abrahams</a>. 326</td> 327 </tr> 328 </table> 329</body> 330</html> 331
