ceph/src/boost/libs/concept_check/concept_check.htm

   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 though 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;]’
 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&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>
 250 boost/concept_check.hpp: In destructor ‘boost::LessThanComparable&lt;TT&gt;::~
 251   LessThanComparable() [with TT = std::complex&lt;float&gt;]’:
 252 boost/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;]’
 255 boost/concept/requires.hpp:30:   instantiated from ‘boost::_requires_&lt;void
 256   (*)(boost::LessThanComparable&lt;std::complex&lt;float&gt; &gt;)&gt;’
 257 bad_error_eg.cpp:8:   instantiated from here
 258 boost/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>