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