]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
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 | ||
b32b8144 | 75 | <li>A framework for specifying concept requirements through concept |
7c673cae FG |
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> > > >]’ | |
213 | bad_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.sgi.com/tech/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.sgi.com/tech/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> | |
250 | boost/concept_check.hpp: In destructor ‘boost::LessThanComparable<TT>::~ | |
251 | LessThanComparable() [with TT = std::complex<float>]’: | |
252 | boost/concept/detail/general.hpp:29: instantiated from ‘static void boost:: | |
253 | concepts::requirement<Model>::failed() [with Model = boost:: | |
254 | LessThanComparable<std::complex<float> >]’ | |
255 | boost/concept/requires.hpp:30: instantiated from ‘boost::_requires_<void | |
256 | (*)(boost::LessThanComparable<std::complex<float> >)>’ | |
257 | bad_error_eg.cpp:8: instantiated from here | |
258 | boost/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.sgi.com/tech/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> |