Planet
navi homePPSaboutscreenshotsdownloaddevelopmentforum

source: downloads/boost_1_34_1/libs/concept_check/implementation.htm @ 29

Last change on this file since 29 was 29, checked in by landauf, 16 years ago

updated boost from 1_33_1 to 1_34_1
File size: 7.8 KB
Line 
1<HTML>
2<!--
3  -- Copyright (c) Jeremy Siek and Andrew Lumsdaine 2000
4  --
5  -- Permission to use, copy, modify, distribute and sell this software
6  -- and its documentation for any purpose is hereby granted without fee,
7  -- provided that the above copyright notice appears in all copies and
8  -- that both that copyright notice and this permission notice appear
9  -- in supporting documentation.  We make no
10  -- representations about the suitability of this software for any
11  -- purpose.  It is provided "as is" without express or implied warranty.
12  -->
13<Head>
14<Title>Concept Checking Implementation</Title>
15<BODY BGCOLOR="#ffffff" LINK="#0000ee" TEXT="#000000" VLINK="#551a8b" 
16        ALINK="#ff0000"> 
17<IMG SRC="../../boost.png" 
18     ALT="C++ Boost" width="277" height="86"> 
19
20<BR Clear>
21
22
23<h2><a name="implementation">Implementation</a></h2>
24
25Ideally we would like to catch, and indicate, the concept violation at
26the point of instantiation.  As mentioned in D&amp;E[<a
27href="bibliography.htm#stroustrup94:_design_evolution">2</a>], the error
28can be caught by exercising all of the requirements needed by the
29function template.  Exactly how the requirements (the valid
30expressions in particular) are exercised is a tricky issue, since we
31want the code to be compiled --- <i>but not executed</i>.  Our
32approach is to exercise the requirements in a separate function that
33is assigned to a function pointer.  In this case, the compiler will
34instantiate the function but will not actually invoke it.  In
35addition, an optimizing compiler will remove the pointer assignment as
36``dead code'' (though the run-time overhead added by the assignment
37would be trivial in any case).  It might be conceivable for a compiler
38to skip the semantic analysis and compilation of the constraints
39function in the first place, which would make our function pointer
40technique ineffective. However, this is unlikely because removal of
41unnecessary code and functions is typically done in later stages of a
42compiler. We have successfully used the function pointer technique
43with GNU C++, Microsoft Visual C++, and several EDG-based compilers
44(KAI C++, SGI MIPSpro).  The following code shows how this technique
45can be applied to the <tt>std::stable_sort()</tt> function:
46
47<pre>
48  template &lt;class RandomAccessIterator&gt;
49  void stable_sort_constraints(RandomAccessIterator i)
50  {
51    typename std::iterator_traits&lt;RandomAccessIterator&gt;
52      ::difference_type n;
53    i += n;  // exercise the requirements for RandomAccessIterator
54    ...
55  }
56  template &lt;class RandomAccessIterator&gt;
57  void stable_sort(RandomAccessIterator first, RandomAccessIterator last)
58  {
59    typedef void (*fptr_type)(RandomAccessIterator);
60    fptr_type x = &stable_sort_constraints;
61    ...
62  }
63</pre>
64
65There is often a large set of requirements that need to be checked,
66and it would be cumbersome for the library implementor to write
67constraint functions like <tt>stable_sort_constraints()</tt> for every
68public function.  Instead, we group sets of valid expressions
69together, according to the definitions of the corresponding concepts.
70For each concept we define a concept checking class template where the
71template parameter is for the type to be checked.  The class contains
72a <tt>contraints()</tt> member function which exercises all of the
73valid expressions of the concept. The objects used in the constraints
74function, such as <tt>n</tt> and <tt>i</tt>, are declared as data
75members of the concept checking class.
76
77<pre>
78  template &lt;class Iter&gt;
79  struct RandomAccessIteratorConcept
80  {
81    void constraints()
82    {
83      i += n;
84      ...
85    }
86    typename std::iterator_traits&lt;RandomAccessIterator&gt;
87      ::difference_type n;
88    Iter i;
89    ...
90  };
91</pre>
92
93We can still use the function pointer mechanism to cause instantiation
94of the constraints function, however now it will be a member function
95pointer. To make it easy for the library implementor to invoke the
96concept checks, we wrap the member function pointer mechanism in a
97function named <tt>function_requires()</tt>. The following code
98snippet shows how to use <tt>function_requires()</tt> to make sure
99that the iterator is a
100<a
101href="http://www.sgi.com/tech/stl/RandomAccessIterator.html">
102RandomAccessIterator</a>.
103
104<pre>
105  template &lt;class Iter&gt;
106  void stable_sort(Iter first, Iter last)
107  {
108    function_requires&lt; RandomAccessIteratorConcept&lt;Iter&gt; &gt;();
109    ...
110  }
111</pre>
112
113The definition of the <tt>function_requires()</tt> is as follows. The
114<tt>Concept</tt> is the concept checking class that has been
115instantiated with the modeling type.  We assign the address of the
116constraints member function to the function pointer <tt>x</tt>, which
117causes the instantiation of the constraints function and checking of
118the concept's valid expressions. We then assign <tt>x</tt> to
119<tt>x</tt> to avoid unused variable compiler warnings, and wrap
120everything in a do-while loop to prevent name collisions.
121
122<pre>
123  template &lt;class Concept&gt;
124  void function_requires()
125  {
126    void (Concept::*x)() = BOOST_FPTR Concept::constraints;
127    ignore_unused_variable_warning(x);
128  }
129</pre>
130
131To check the type parameters of class templates, we provide the
132<tt>BOOST_CLASS_REQUIRE</tt> macro which can be used inside the body of a
133class definition (whereas <tt>function_requires()</tt> can only be used
134inside of a function body).  This macro declares a nested class
135template, where the template parameter is a function pointer. We then
136use the nested class type in a typedef with the function pointer type
137of the constraint function as the template argument. We use the
138<tt>type_var</tt> and <tt>concept</tt> names in the nested class and
139typedef names to help prevent name collisions.
140
141<pre>
142#define BOOST_CLASS_REQUIRE(type_var, ns, concept) \
143  typedef void (ns::concept &lt;type_var&gt;::* func##type_var##concept)(); \
144  template &lt;func##type_var##concept _Tp1&gt; \
145  struct concept_checking_##type_var##concept { }; \
146  typedef concept_checking_##type_var##concept&lt; \
147    BOOST_FPTR ns::concept&lt;type_var&gt;::constraints&gt; \
148    concept_checking_typedef_##type_var##concept
149</pre>
150
151In addition, there are versions of <tt>BOOST_CLASS_REQUIRE</tt> that
152take more arguments, to handle concepts that include interactions
153between two or more types. <tt>BOOST_CLASS_REQUIRE</tt> was not used
154in the implementation of the BCCL concept checks because some
155compilers do not implement template parameters of function pointer
156type.
157
158<!-- We decided not to go with this version since it is easier to misuse
159
160To 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
162class definition (whereas <tt>function_requires()</tt> can only be
163used inside of a function body).  <tt>class_requires</tt> declares a
164nested class template, where the template parameter is a function
165pointer. We then use the nested class type in a typedef with the
166function pointer type of the constraint function as the template
167argument.
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
183Boost Concept Checking Library concept checks because several
184compilers do not implement template parameters of function pointer
185type.
186
187-->
188
189<p>
190<a href="./reference.htm">Next: Reference</a><br>
191<a href="prog_with_concepts.htm">Prev: Programming With Concepts</a>
192
193<br>
194<HR>
195<TABLE>
196<TR valign=top>
197<TD nowrap>Copyright &copy 2000</TD><TD>
198<A HREF="../../people/jeremy_siek.htm">Jeremy Siek</A>(<A
199HREF="mailto:jsiek@osl.iu.edu">jsiek@osl.iu.edu</A>)
200Andrew Lumsdaine</A>(<A HREF="mailto:lums@osl.iu.edu">lums@osl.iu.edu</A>)
201</TD></TR></TABLE>
202
203</BODY>
204</HTML> 
Note: See TracBrowser for help on using the repository browser.