Gitiles
Code Review Sign In
realtimeroboticsgroup.org / RealtimeRoboticsGroup / test / bca6d25af494f6ecfb6ecab60094dae251570c14 / . / implementation.htm
blob: 008fbeda1e91cd463f521aab71e0eb2e4336e7a1 [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) 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
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--></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>