Gitiles
Code Review Sign In
realtimeroboticsgroup.org / RealtimeRoboticsGroup / test / bca6d25af494f6ecfb6ecab60094dae251570c14 / . / concept_check.htm
blob: 4a47fa808787c168e77bcc2217c11fb5b61ea7df [file] [log] [blame]
Brian Silvermanbca6d252018-08-04 23:36:16 -0700[diff] [blame^]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 &lt;vector&gt;
178<font color="gray">2</font color="gray"> #include &lt;complex&gt;
179<font color="gray">3</font color="gray"> #include &lt;algorithm&gt;
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&lt;std::complex&lt;float&gt; &gt; 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 &lt;class RandomAccessIterator&gt;
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&lt;std::complex&lt;float
201 &gt;*, std::vector&lt;std::complex&lt;float&gt;, std::allocator&lt;std::complex&lt;
202 float&gt; &gt; &gt; &gt;]’:
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&lt;std::complex&lt;float&gt;*, std::vector&lt;std::complex&lt;
207 float&gt;, std::allocator&lt;std::complex&lt;float&gt; &gt; &gt; &gt;]’
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&lt;std::complex&lt;float
211 &gt;*, std::vector&lt;std::complex&lt;float&gt;, std::allocator&lt;std::complex&lt;
212 float&gt; &gt; &gt; &gt;]’
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&lt;’ in ‘__val &lt; __first. __gnu_cxx::__normal_iterator&lt;
216 _Iterator, _Container&gt;::operator* [with _Iterator = std::complex&lt;float
217 &gt;*, _Container = std::vector&lt;std::complex&lt;float&gt;, std::allocator&lt;
218 std::complex&lt;float&gt; &gt; &gt;]()’
219</pre>
220
221 <p>In this case, the fundamental error is
222 that <tt>std:complex&lt;float&gt;</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>
250boost/concept_check.hpp: In destructor ‘boost::LessThanComparable&lt;TT&gt;::~
251 LessThanComparable() [with TT = std::complex&lt;float&gt;]’:
252boost/concept/detail/general.hpp:29: instantiated from ‘static void boost::
253 concepts::requirement&lt;Model&gt;::failed() [with Model = boost::
254 LessThanComparable&lt;std::complex&lt;float&gt; &gt;]’
255boost/concept/requires.hpp:30: instantiated from ‘boost::_requires_&lt;void
256 (*)(boost::LessThanComparable&lt;std::complex&lt;float&gt; &gt;)&gt;’
257bad_error_eg.cpp:8: instantiated from here
258boost/concept_check.hpp:236: error: no match for ‘operator&lt;’ in ‘((boost::
259 LessThanComparable&lt;std::complex&lt;float&gt; &gt;*)this)-&gt;boost::
260 LessThanComparable&lt;std::complex&lt;float&gt; &gt;::a &lt; ((boost::
261 LessThanComparable&lt;std::complex&lt;float&gt; &gt;*)this)-&gt;boost::
262 LessThanComparable&lt;std::complex&lt;float&gt; &gt;::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&amp;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 &copy; 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>