1// Boost.Range library concept checks
2//
3// Copyright Neil Groves 2009. Use, modification and distribution
4// are subject to the Boost Software License, Version 1.0. (See
5// accompanying file LICENSE_1_0.txt or copy at
6// http://www.boost.org/LICENSE_1_0.txt)
7//
8// Copyright Daniel Walker 2006. Use, modification and distribution
9// are subject to the Boost Software License, Version 1.0. (See
10// accompanying file LICENSE_1_0.txt or copy at
11// http://www.boost.org/LICENSE_1_0.txt)
12//
13// For more information, see http://www.boost.org/libs/range/
14//
15
16#ifndef BOOST_RANGE_CONCEPTS_HPP
17#define BOOST_RANGE_CONCEPTS_HPP
18
19#include <boost/concept_check.hpp>
20#include <boost/iterator/iterator_concepts.hpp>
21#include <boost/range/begin.hpp>
22#include <boost/range/end.hpp>
23#include <boost/range/iterator.hpp>
24#include <boost/range/value_type.hpp>
25#include <boost/range/detail/misc_concept.hpp>
26#include <boost/type_traits/remove_reference.hpp>
27
28/*!
29 * \file
30 * \brief Concept checks for the Boost Range library.
31 *
32 * The structures in this file may be used in conjunction with the
33 * Boost Concept Check library to insure that the type of a function
34 * parameter is compatible with a range concept. If not, a meaningful
35 * compile time error is generated. Checks are provided for the range
36 * concepts related to iterator traversal categories. For example, the
37 * following line checks that the type T models the ForwardRange
38 * concept.
39 *
40 * \code
41 * BOOST_CONCEPT_ASSERT((ForwardRangeConcept<T>));
42 * \endcode
43 *
44 * A different concept check is required to ensure writeable value
45 * access. For example to check for a ForwardRange that can be written
46 * to, the following code is required.
47 *
48 * \code
49 * BOOST_CONCEPT_ASSERT((WriteableForwardRangeConcept<T>));
50 * \endcode
51 *
52 * \see http://www.boost.org/libs/range/doc/range.html for details
53 * about range concepts.
54 * \see http://www.boost.org/libs/iterator/doc/iterator_concepts.html
55 * for details about iterator concepts.
56 * \see http://www.boost.org/libs/concept_check/concept_check.htm for
57 * details about concept checks.
58 */
59
60namespace boost {
61
62 namespace range_detail {
63
64#ifndef BOOST_RANGE_ENABLE_CONCEPT_ASSERT
65
66// List broken compiler versions here:
67#ifndef __clang__
68 #ifdef __GNUC__
69 // GNUC 4.2 has strange issues correctly detecting compliance with the Concepts
70 // hence the least disruptive approach is to turn-off the concept checking for
71 // this version of the compiler.
72 #if __GNUC__ == 4 && __GNUC_MINOR__ == 2
73 #define BOOST_RANGE_ENABLE_CONCEPT_ASSERT 0
74 #endif
75 #endif
76
77 #ifdef __GCCXML__
78 // GCC XML, unsurprisingly, has the same issues
79 #if __GCCXML_GNUC__ == 4 && __GCCXML_GNUC_MINOR__ == 2
80 #define BOOST_RANGE_ENABLE_CONCEPT_ASSERT 0
81 #endif
82 #endif
83#endif
84
85 #ifdef __BORLANDC__
86 #define BOOST_RANGE_ENABLE_CONCEPT_ASSERT 0
87 #endif
88
89 #ifdef __PATHCC__
90 #define BOOST_RANGE_ENABLE_CONCEPT_ASSERT 0
91 #endif
92
93// Default to using the concept asserts unless we have defined it off
94// during the search for black listed compilers.
95 #ifndef BOOST_RANGE_ENABLE_CONCEPT_ASSERT
96 #define BOOST_RANGE_ENABLE_CONCEPT_ASSERT 1
97 #endif
98
99#endif
100
101#if BOOST_RANGE_ENABLE_CONCEPT_ASSERT
102 #define BOOST_RANGE_CONCEPT_ASSERT( x ) BOOST_CONCEPT_ASSERT( x )
103#else
104 #define BOOST_RANGE_CONCEPT_ASSERT( x )
105#endif
106
107 // Rationale for the inclusion of redefined iterator concept
108 // classes:
109 //
110 // The Range algorithms often do not require that the iterators are
111 // Assignable or default constructable, but the correct standard
112 // conformant iterators do require the iterators to be a model of the
113 // Assignable concept.
114 // Iterators that contains a functor that is not assignable therefore
115 // are not correct models of the standard iterator concepts,
116 // despite being adequate for most algorithms. An example of this
117 // use case is the combination of the boost::adaptors::filtered
118 // class with a boost::lambda::bind generated functor.
119 // Ultimately modeling the range concepts using composition
120 // with the Boost.Iterator concepts would render the library
121 // incompatible with many common Boost.Lambda expressions.
122 template<class Iterator>
123 struct IncrementableIteratorConcept : CopyConstructible<Iterator>
124 {
125#if BOOST_RANGE_ENABLE_CONCEPT_ASSERT
126 typedef BOOST_DEDUCED_TYPENAME iterator_traversal<Iterator>::type traversal_category;
127
128 BOOST_RANGE_CONCEPT_ASSERT((
129 Convertible<
130 traversal_category,
131 incrementable_traversal_tag
132 >));
133
134 BOOST_CONCEPT_USAGE(IncrementableIteratorConcept)
135 {
136 ++i;
137 (void)i++;
138 }
139 private:
140 Iterator i;
141#endif
142 };
143
144 template<class Iterator>
145 struct SinglePassIteratorConcept
146 : IncrementableIteratorConcept<Iterator>
147 , EqualityComparable<Iterator>
148 {
149#if BOOST_RANGE_ENABLE_CONCEPT_ASSERT
150 BOOST_RANGE_CONCEPT_ASSERT((
151 Convertible<
152 BOOST_DEDUCED_TYPENAME SinglePassIteratorConcept::traversal_category,
153 single_pass_traversal_tag
154 >));
155
156 BOOST_CONCEPT_USAGE(SinglePassIteratorConcept)
157 {
158 Iterator i2(++i);
159 boost::ignore_unused_variable_warning(i2);
160
161 // deliberately we are loose with the postfix version for the single pass
162 // iterator due to the commonly poor adherence to the specification means that
163 // many algorithms would be unusable, whereas actually without the check they
164 // work
165 (void)(i++);
166
167 BOOST_DEDUCED_TYPENAME boost::detail::iterator_traits<Iterator>::reference r1(*i);
168 boost::ignore_unused_variable_warning(r1);
169
170 BOOST_DEDUCED_TYPENAME boost::detail::iterator_traits<Iterator>::reference r2(*(++i));
171 boost::ignore_unused_variable_warning(r2);
172 }
173 private:
174 Iterator i;
175#endif
176 };
177
178 template<class Iterator>
179 struct ForwardIteratorConcept
180 : SinglePassIteratorConcept<Iterator>
181 , DefaultConstructible<Iterator>
182 {
183#if BOOST_RANGE_ENABLE_CONCEPT_ASSERT
184 typedef BOOST_DEDUCED_TYPENAME boost::detail::iterator_traits<Iterator>::difference_type difference_type;
185
186 BOOST_MPL_ASSERT((is_integral<difference_type>));
187 BOOST_MPL_ASSERT_RELATION(std::numeric_limits<difference_type>::is_signed, ==, true);
188
189 BOOST_RANGE_CONCEPT_ASSERT((
190 Convertible<
191 BOOST_DEDUCED_TYPENAME ForwardIteratorConcept::traversal_category,
192 forward_traversal_tag
193 >));
194
195 BOOST_CONCEPT_USAGE(ForwardIteratorConcept)
196 {
197 // See the above note in the SinglePassIteratorConcept about the handling of the
198 // postfix increment. Since with forward and better iterators there is no need
199 // for a proxy, we can sensibly require that the dereference result
200 // is convertible to reference.
201 Iterator i2(i++);
202 boost::ignore_unused_variable_warning(i2);
203 BOOST_DEDUCED_TYPENAME boost::detail::iterator_traits<Iterator>::reference r(*(i++));
204 boost::ignore_unused_variable_warning(r);
205 }
206 private:
207 Iterator i;
208#endif
209 };
210
211 template<class Iterator>
212 struct BidirectionalIteratorConcept
213 : ForwardIteratorConcept<Iterator>
214 {
215 #if BOOST_RANGE_ENABLE_CONCEPT_ASSERT
216 BOOST_RANGE_CONCEPT_ASSERT((
217 Convertible<
218 BOOST_DEDUCED_TYPENAME BidirectionalIteratorConcept::traversal_category,
219 bidirectional_traversal_tag
220 >));
221
222 BOOST_CONCEPT_USAGE(BidirectionalIteratorConcept)
223 {
224 --i;
225 (void)i--;
226 }
227 private:
228 Iterator i;
229 #endif
230 };
231
232 template<class Iterator>
233 struct RandomAccessIteratorConcept
234 : BidirectionalIteratorConcept<Iterator>
235 {
236 #if BOOST_RANGE_ENABLE_CONCEPT_ASSERT
237 BOOST_RANGE_CONCEPT_ASSERT((
238 Convertible<
239 BOOST_DEDUCED_TYPENAME RandomAccessIteratorConcept::traversal_category,
240 random_access_traversal_tag
241 >));
242
243 BOOST_CONCEPT_USAGE(RandomAccessIteratorConcept)
244 {
245 i += n;
246 i = i + n;
247 i = n + i;
248 i -= n;
249 i = i - n;
250 n = i - j;
251 }
252 private:
253 BOOST_DEDUCED_TYPENAME RandomAccessIteratorConcept::difference_type n;
254 Iterator i;
255 Iterator j;
256 #endif
257 };
258
259 } // namespace range_detail
260
261 //! Check if a type T models the SinglePassRange range concept.
262 template<class T>
263 struct SinglePassRangeConcept
264 {
265#if BOOST_RANGE_ENABLE_CONCEPT_ASSERT
266 // A few compilers don't like the rvalue reference T types so just
267 // remove it.
268 typedef BOOST_DEDUCED_TYPENAME remove_reference<T>::type Rng;
269
270 typedef BOOST_DEDUCED_TYPENAME range_iterator<
271 Rng const
272 >::type const_iterator;
273
274 typedef BOOST_DEDUCED_TYPENAME range_iterator<Rng>::type iterator;
275
276 BOOST_RANGE_CONCEPT_ASSERT((
277 range_detail::SinglePassIteratorConcept<iterator>));
278
279 BOOST_RANGE_CONCEPT_ASSERT((
280 range_detail::SinglePassIteratorConcept<const_iterator>));
281
282 BOOST_CONCEPT_USAGE(SinglePassRangeConcept)
283 {
284 // This has been modified from assigning to this->i
285 // (where i was a member variable) to improve
286 // compatibility with Boost.Lambda
287 iterator i1 = boost::begin(*m_range);
288 iterator i2 = boost::end(*m_range);
289
290 boost::ignore_unused_variable_warning(i1);
291 boost::ignore_unused_variable_warning(i2);
292
293 const_constraints(*m_range);
294 }
295
296 private:
297 void const_constraints(const Rng& const_range)
298 {
299 const_iterator ci1 = boost::begin(const_range);
300 const_iterator ci2 = boost::end(const_range);
301
302 boost::ignore_unused_variable_warning(ci1);
303 boost::ignore_unused_variable_warning(ci2);
304 }
305
306 // Rationale:
307 // The type of m_range is T* rather than T because it allows
308 // T to be an abstract class. The other obvious alternative of
309 // T& produces a warning on some compilers.
310 Rng* m_range;
311#endif
312 };
313
314 //! Check if a type T models the ForwardRange range concept.
315 template<class T>
316 struct ForwardRangeConcept : SinglePassRangeConcept<T>
317 {
318#if BOOST_RANGE_ENABLE_CONCEPT_ASSERT
319 BOOST_RANGE_CONCEPT_ASSERT((range_detail::ForwardIteratorConcept<BOOST_DEDUCED_TYPENAME ForwardRangeConcept::iterator>));
320 BOOST_RANGE_CONCEPT_ASSERT((range_detail::ForwardIteratorConcept<BOOST_DEDUCED_TYPENAME ForwardRangeConcept::const_iterator>));
321#endif
322 };
323
324 template<class T>
325 struct WriteableRangeConcept
326 {
327#if BOOST_RANGE_ENABLE_CONCEPT_ASSERT
328 typedef BOOST_DEDUCED_TYPENAME range_iterator<T>::type iterator;
329
330 BOOST_CONCEPT_USAGE(WriteableRangeConcept)
331 {
332 *i = v;
333 }
334 private:
335 iterator i;
336 BOOST_DEDUCED_TYPENAME range_value<T>::type v;
337#endif
338 };
339
340 //! Check if a type T models the WriteableForwardRange range concept.
341 template<class T>
342 struct WriteableForwardRangeConcept
343 : ForwardRangeConcept<T>
344 , WriteableRangeConcept<T>
345 {
346 };
347
348 //! Check if a type T models the BidirectionalRange range concept.
349 template<class T>
350 struct BidirectionalRangeConcept : ForwardRangeConcept<T>
351 {
352#if BOOST_RANGE_ENABLE_CONCEPT_ASSERT
353 BOOST_RANGE_CONCEPT_ASSERT((range_detail::BidirectionalIteratorConcept<BOOST_DEDUCED_TYPENAME BidirectionalRangeConcept::iterator>));
354 BOOST_RANGE_CONCEPT_ASSERT((range_detail::BidirectionalIteratorConcept<BOOST_DEDUCED_TYPENAME BidirectionalRangeConcept::const_iterator>));
355#endif
356 };
357
358 //! Check if a type T models the WriteableBidirectionalRange range concept.
359 template<class T>
360 struct WriteableBidirectionalRangeConcept
361 : BidirectionalRangeConcept<T>
362 , WriteableRangeConcept<T>
363 {
364 };
365
366 //! Check if a type T models the RandomAccessRange range concept.
367 template<class T>
368 struct RandomAccessRangeConcept : BidirectionalRangeConcept<T>
369 {
370#if BOOST_RANGE_ENABLE_CONCEPT_ASSERT
371 BOOST_RANGE_CONCEPT_ASSERT((range_detail::RandomAccessIteratorConcept<BOOST_DEDUCED_TYPENAME RandomAccessRangeConcept::iterator>));
372 BOOST_RANGE_CONCEPT_ASSERT((range_detail::RandomAccessIteratorConcept<BOOST_DEDUCED_TYPENAME RandomAccessRangeConcept::const_iterator>));
373#endif
374 };
375
376 //! Check if a type T models the WriteableRandomAccessRange range concept.
377 template<class T>
378 struct WriteableRandomAccessRangeConcept
379 : RandomAccessRangeConcept<T>
380 , WriteableRangeConcept<T>
381 {
382 };
383
384} // namespace boost
385
386#endif // BOOST_RANGE_CONCEPTS_HPP
387