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