1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
|
<HTML>
<!--
-- Copyright (c) Jeremy Siek and Andrew Lumsdaine 2000
--
-- Permission to use, copy, modify, distribute and sell this software
-- and its documentation for any purpose is hereby granted without fee,
-- provided that the above copyright notice appears in all copies and
-- that both that copyright notice and this permission notice appear
-- in supporting documentation. We make no
-- representations about the suitability of this software for any
-- purpose. It is provided "as is" without express or implied warranty.
-->
<Head>
<Title>Concept Check Library</Title>
</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>
<H1>The Boost Concept Check Library (BCCL)</H1>
<h2>
<A NAME="sec:concept-checking"></A>
header <a href="../../boost/concept_check.hpp">
<tt>boost/concept_check.hpp</tt></a>
<br>and <a href="../../boost/concept_archetype.hpp">
<tt>boost/concept_archetype.hpp</tt></a>
</h2>
<p>
Generic programming in C++ is characterized by the use of template
parameters to represent abstract data types (or ``concepts'').
However, the C++ language itself does not provide a mechanism for the
writer of a class or function template to explicitly state what
concept the user-supplied template argument should model (or conform
to). The common practice is to name the template parameter after the
required concept as a hint to the user and to state the concept
requirements in the documentation. However, often times the
requirements are vague, incorrect, or nonexistent, which is quite a
problem for the user, since he or she will not know exactly what kind
of input is expected by the template. Furthermore, the following
problems occur:
<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>The documented concept requirements may not fully <i>cover</i>
the 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>The requirements are not explicitly stated in the code, which
makes the code harder to understand. Also, the code may
get out-of-sync with the documented requirements.</li>
</ul>
The Boost Concept Checking Library provides:
<ul>
<li>A mechanism for inserting compile-time checks of template
parameters.</li>
<li>A framework for specifying concept requirements though 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>
</ul>
The mechanisms use standard C++ and introduce no run-time
overhead. The main cost of using the mechanism is in compile-time.
<p>
Any programmer writing class or function templates ought to make
concept checking a normal part of their code writing routine. 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>
The documentation is organized into the following sections.
<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="../../people/jeremy_siek.htm">Jeremy Siek</a> contributed
this library. <a href="../../people/beman_dawes.html">Beman Dawes</a>
managed the formal review.
<h2><a name="introduction">Introduction</a></h2>
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>
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>
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..
<h2><a name="motivating-example">Motivating Example</a></h2>
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.
<pre>
<a href="./bad_error_eg.cpp">bad_error_eg.cpp</a>:
1 #include <list>
2 #include <algorithm>
3
4 int main(int, char*[]) {
5 std::list<int> v;
6 std::stable_sort(v.begin(), v.end());
7 return 0;
8 }
</pre>
Here, the
<tt>std::stable_sort()</tt> algorithm is prototyped as follows:
<pre>
template <class RandomAccessIterator>
void stable_sort(RandomAccessIterator first, RandomAccessIterator last);
</pre>
Attempting to compile this code with Gnu C++ produces the following
compiler error. The output from other compilers is listed in the
Appendix.
<pre>
stl_algo.h: In function `void __merge_sort_loop<_List_iterator
<int,int &,int *>, int *, int>(_List_iterator<int,int &,int *>,
_List_iterator<int,int &,int *>, int *, int)':
stl_algo.h:1448: instantiated from `__merge_sort_with_buffer
<_List_iterator<int,int &,int *>, int *, int>(
_List_iterator<int,int &,int *>, _List_iterator<int,int &,int *>,
int *, int *)'
stl_algo.h:1485: instantiated from `__stable_sort_adaptive<
_List_iterator<int,int &,int *>, int *, int>(_List_iterator
<int,int &,int *>, _List_iterator<int,int &,int *>, int *, int)'
stl_algo.h:1524: instantiated from here
stl_algo.h:1377: no match for `_List_iterator<int,int &,int *> & -
_List_iterator<int,int &,int *> &'
</pre>
In this case, the fundamental error is that
<tt>std:list::iterator</tt> does not model the concept of <a
href="http://www.sgi.com/tech/stl/RandomAccessIterator.html">
RandomAccessIterator</a>. The list iterator is only bidirectional, not
fully random access (as would be a vector iterator). Unfortunately,
there is nothing in the error message to indicate this to the user.
<p>
To a C++ programmer having enough experience with template libraries
the error may be obvious. However, for the uninitiated, there are several
reasons why this message would be hard to understand.
<OL>
<LI> The location of the error, line 6 of <tt>bad_error_eg.cpp</tt>
is not pointed to by the error message, despite the fact that Gnu C++
prints up to 4 levels deep in the instantiation stack.
<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/RandomAccessIterator.html">
RandomAccessIterator</a>.
<LI> The error message is overly long, listing functions internal
to the STL that the user does not (and should not!) know or care
about.
<LI> With so many internal library functions listed in the error
message, the programmer could easily infer that the error is due
to the library, rather than to his or her own code.
</OL>
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):
<pre>
boost/concept_check.hpp: In method `void LessThanComparableConcept
<_List_iterator<int,int &,int *> >::constraints()':
boost/concept_check.hpp:334: instantiated from `RandomAccessIteratorConcept
<_List_iterator<int,int &,int *> >::constraints()'
bad_error_eg.cpp:6: instantiated from `stable_sort<_List_iterator
<int,int &,int *> >(_List_iterator<int,int &,int *>,
_List_iterator<int,int &,int *>)'
boost/concept_check.hpp:209: no match for `_List_iterator<int,int &,int *> &
< _List_iterator<int,int &,int *> &'
</pre>
This message rectifies several of the shortcomings of the standard
error messages.
<UL>
<LI> The location of the error, <tt>bad_error_eg.cpp:6</tt> is
specified in the error message.
<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/RandomAccessIterator.html">
RandomAccessIterator</a>).
<LI> The error message is now much shorter and does not reveal
internal STL functions.
<LI> The presence of <tt>concept_check.hpp</tt> and
<tt>constraints()</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.
</UL>
<h2><a name="history">History</a></h2>
An earlier version of this concept checking system was developed by
the author while working at SGI in their C++ compiler and library
group. The earlier version is now part of the SGI STL distribution. The
boost concept checking library differs from the concept checking in
the SGI STL in that the definition of concept checking classes has
been greatly simplified, at the price of less helpful verbiage in the
error messages.
<h2><a name="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">Acknowledgements</a></h2>
The idea to use function pointers to cause instantiation is due to
Alexander Stepanov. I am 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>
<HR>
<TABLE>
<TR valign=top>
<TD nowrap>Copyright © 2000</TD><TD>
<A HREF="../../people/jeremy_siek.htm">Jeremy Siek</A>(<A
HREF="mailto:jsiek@osl.iu.edu">jsiek@osl.iu.edu</A>)
Andrew Lumsdaine</A>(<A HREF="mailto:lums@osl.iu.edu">lums@osl.iu.edu</A>)
</TD></TR></TABLE>
</BODY>
</HTML>
|
