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 62 namespace 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 BOOST_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 BOOST_CONCEPT_USAGEboost::range_detail::IncrementableIteratorConcept136 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 BOOST_CONCEPT_USAGEboost::range_detail::SinglePassIteratorConcept158 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 BOOST_CONCEPT_USAGEboost::range_detail::ForwardIteratorConcept197 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 BOOST_CONCEPT_USAGEboost::range_detail::BidirectionalIteratorConcept224 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 BOOST_CONCEPT_USAGEboost::range_detail::RandomAccessIteratorConcept245 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 BidirectionalIteratorConcept<Iterator>::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 BOOST_CONCEPT_USAGEboost::SinglePassRangeConcept284 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: const_constraintsboost::SinglePassRangeConcept299 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 BOOST_CONCEPT_USAGEboost::WriteableRangeConcept332 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