libs/concept_check/implementation.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) Jeremy Siek and Andrew Lumsdaine 2000, David Abrahams 2007 -->
   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   <link rel="stylesheet" href="../../rst.css" type="text/css" />
  15
  16   <title>Concept Checking Implementation</title>
  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   <h2><a name="warning" id="warning"><font color=
  25   "red">Warning</font></a></h2>
  26
  27   <p><font color="red">This documentation is out-of-date; similar but
  28   newer implementation techniques are now used.  This documentation
  29   also refers to components and protocols in the library's old
  30   interace such as <code>BOOST_CLASS_REQUIRES</code>
  31   and <code>constraints()</code> functions, which are still supported
  32   but deprecated.</font></p>
  33
  34   <h2><a name="implementation" id="implementation">Implementation</a></h2>
  35
  36   <p>Ideally we would like to catch, and indicate, the concept violation at
  37   the point of instantiation. As mentioned in D&amp;E[<a href=
  38   "bibliography.htm#stroustrup94:_design_evolution">2</a>], the error can be
  39   caught by exercising all of the requirements needed by the function
  40   template. Exactly how the requirements (the valid expressions in
  41   particular) are exercised is a tricky issue, since we want the code to be
  42   compiled—<i>but not executed</i>. Our approach is to exercise the
  43   requirements in a separate function that is assigned to a function pointer.
  44   In this case, the compiler will instantiate the function but will not
  45   actually invoke it. In addition, an optimizing compiler will remove the
  46   pointer assignment as ``dead code'' (though the run-time overhead added by
  47   the assignment would be trivial in any case). It might be conceivable for a
  48   compiler to skip the semantic analysis and compilation of the constraints
  49   function in the first place, which would make our function pointer
  50   technique ineffective. However, this is unlikely because removal of
  51   unnecessary code and functions is typically done in later stages of a
  52   compiler. We have successfully used the function pointer technique with GNU
  53   C++, Microsoft Visual C++, and several EDG-based compilers (KAI C++, SGI
  54   MIPSpro). The following code shows how this technique can be applied to the
  55   <tt>std::stable_sort()</tt> function:</p>
  56   <pre>
  57   template &lt;class RandomAccessIterator&gt;
  58   void stable_sort_constraints(RandomAccessIterator i)
  59   {
  60     typename std::iterator_traits&lt;RandomAccessIterator&gt;
  61       ::difference_type n;
  62     i += n;  // exercise the requirements for RandomAccessIterator
  63     ...
  64   }
  65   template &lt;class RandomAccessIterator&gt;
  66   void stable_sort(RandomAccessIterator first, RandomAccessIterator last)
  67   {
  68     typedef void (*fptr_type)(RandomAccessIterator);
  69     fptr_type x = &amp;stable_sort_constraints;
  70     ...
  71   }
  72 </pre>
  73
  74   <p>There is often a large set of requirements that need to be checked, and
  75   it would be cumbersome for the library implementor to write constraint
  76   functions like <tt>stable_sort_constraints()</tt> for every public
  77   function. Instead, we group sets of valid expressions together, according
  78   to the definitions of the corresponding concepts. For each concept we
  79   define a concept checking class template where the template parameter is
  80   for the type to be checked. The class contains a <tt>contraints()</tt>
  81   member function which exercises all of the valid expressions of the
  82   concept. The objects used in the constraints function, such as <tt>n</tt>
  83   and <tt>i</tt>, are declared as data members of the concept checking
  84   class.</p>
  85   <pre>
  86   template &lt;class Iter&gt;
  87   struct RandomAccessIteratorConcept
  88   {
  89     void constraints()
  90     {
  91       i += n;
  92       ...
  93     }
  94     typename std::iterator_traits&lt;RandomAccessIterator&gt;
  95       ::difference_type n;
  96     Iter i;
  97     ...
  98   };
  99 </pre>
 100
 101   <p>We can still use the function pointer mechanism to cause instantiation
 102   of the constraints function, however now it will be a member function
 103   pointer. To make it easy for the library implementor to invoke the concept
 104   checks, we wrap the member function pointer mechanism in a function named
 105   <tt>function_requires()</tt>. The following code snippet shows how to use
 106   <tt>function_requires()</tt> to make sure that the iterator is a <a href=
 107   "http://www.sgi.com/tech/stl/RandomAccessIterator.html">RandomAccessIterator</a>.</p>
 108   <pre>
 109   template &lt;class Iter&gt;
 110   void stable_sort(Iter first, Iter last)
 111   {
 112     function_requires&lt; RandomAccessIteratorConcept&lt;Iter&gt; &gt;();
 113     ...
 114   }
 115 </pre>
 116
 117   <p>The definition of the <tt>function_requires()</tt> is as follows. The
 118   <tt>Concept</tt> is the concept checking class that has been instantiated
 119   with the modeling type. We assign the address of the constraints member
 120   function to the function pointer <tt>x</tt>, which causes the instantiation
 121   of the constraints function and checking of the concept's valid
 122   expressions. We then assign <tt>x</tt> to <tt>x</tt> to avoid unused
 123   variable compiler warnings, and wrap everything in a do-while loop to
 124   prevent name collisions.</p>
 125   <pre>
 126   template &lt;class Concept&gt;
 127   void function_requires()
 128   {
 129     void (Concept::*x)() = BOOST_FPTR Concept::constraints;
 130     ignore_unused_variable_warning(x);
 131   }
 132 </pre>
 133
 134   <p>To check the type parameters of class templates, we provide the
 135   <tt>BOOST_CLASS_REQUIRE</tt> macro which can be used inside the body of a
 136   class definition (whereas <tt>function_requires()</tt> can only be used
 137   inside of a function body). This macro declares a nested class template,
 138   where the template parameter is a function pointer. We then use the nested
 139   class type in a typedef with the function pointer type of the constraint
 140   function as the template argument. We use the <tt>type_var</tt> and
 141   <tt>concept</tt> names in the nested class and typedef names to help
 142   prevent name collisions.</p>
 143   <pre>
 144 #define BOOST_CLASS_REQUIRE(type_var, ns, concept) \
 145   typedef void (ns::concept &lt;type_var&gt;::* func##type_var##concept)(); \
 146   template &lt;func##type_var##concept _Tp1&gt; \
 147   struct concept_checking_##type_var##concept { }; \
 148   typedef concept_checking_##type_var##concept&lt; \
 149     BOOST_FPTR ns::concept&lt;type_var&gt;::constraints&gt; \
 150     concept_checking_typedef_##type_var##concept
 151 </pre>
 152
 153   <p>In addition, there are versions of <tt>BOOST_CLASS_REQUIRE</tt> that
 154   take more arguments, to handle concepts that include interactions between
 155   two or more types. <tt>BOOST_CLASS_REQUIRE</tt> was not used in the
 156   implementation of the BCCL concept checks because some compilers do not
 157   implement template parameters of function pointer type.
 158   <!-- We decided not to go with this version since it is easier to misuse
 159
 160 To check the type parameters of class templates, we provide the
 161 <tt>class_requires</tt> class which can be used inside the body of a
 162 class definition (whereas <tt>function_requires()</tt> can only be
 163 used inside of a function body).  <tt>class_requires</tt> declares a
 164 nested class template, where the template parameter is a function
 165 pointer. We then use the nested class type in a typedef with the
 166 function pointer type of the constraint function as the template
 167 argument.
 168
 169 <pre>
 170   template &lt;class Concept&gt;
 171   class class_requires
 172   {
 173     typedef void (Concept::* function_pointer)();
 174
 175     template &lt;function_pointer Fptr&gt;
 176     struct dummy_struct { };
 177   public:
 178     typedef dummy_struct&lt; BOOST_FPTR Concept::constraints &gt; check;
 179   };
 180 </pre>
 181
 182 <tt>class_requires</tt> was not used in the implementation of the
 183 Boost Concept Checking Library concept checks because several
 184 compilers do not implement template parameters of function pointer
 185 type.
 186
 187 --></p>
 188
 189   <p><a href="./reference.htm">Next: Reference</a><br />
 190   <a href="prog_with_concepts.htm">Prev: Programming With
 191   Concepts</a><br /></p>
 192   <hr />
 193
 194   <table>
 195     <tr valign="top">
 196       <td nowrap="nowrap">Copyright &copy; 2000</td>
 197
 198       <td><a href="http://www.boost.org/people/jeremy_siek.htm">Jeremy Siek</a>(<a href=
 199       "mailto:jsiek@osl.iu.edu">jsiek@osl.iu.edu</a>) Andrew
 200       Lumsdaine(<a href="mailto:lums@osl.iu.edu">lums@osl.iu.edu</a>),
 201         2007 <a href="mailto:dave@boost-consulting.com">David Abrahams</a>.
 202     </tr>
 203   </table>
 204 </body>
 205 </html>