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 60 namespace 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 BOOST_CONCEPT_USAGEboost::range_detail::IncrementableIteratorConcept134 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 BOOST_CONCEPT_USAGEboost::range_detail::SinglePassIteratorConcept156 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 BOOST_CONCEPT_USAGEboost::range_detail::ForwardIteratorConcept195 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 BOOST_CONCEPT_USAGEboost::range_detail::BidirectionalIteratorConcept222 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 BOOST_CONCEPT_USAGEboost::range_detail::RandomAccessIteratorConcept243 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 BOOST_CONCEPT_USAGEboost::SinglePassRangeConcept282 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: const_constraintsboost::SinglePassRangeConcept297 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 BOOST_CONCEPT_USAGEboost::WriteableRangeConcept330 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