boost/range/concepts.hpp

   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
 124             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
 146             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
 185             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
 212              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
 233              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
 262          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:
 277         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
 310         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((range_detail::BidirectionalIteratorConcept<BOOST_DEDUCED_TYPENAME BidirectionalRangeConcept::iterator>));
 334         BOOST_RANGE_CONCEPT_ASSERT((range_detail::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((range_detail::RandomAccessIteratorConcept<BOOST_DEDUCED_TYPENAME RandomAccessRangeConcept::iterator>));
 352         BOOST_RANGE_CONCEPT_ASSERT((range_detail::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