boost/range/concepts.hpp

0001 // Boost.Range library concept checks
0002 //
0003 //  Copyright Neil Groves 2009. Use, modification and distribution
0004 //  are subject to the Boost Software License, Version 1.0. (See
0005 //  accompanying file LICENSE_1_0.txt or copy at
0006 //  http://www.boost.org/LICENSE_1_0.txt)
0007 //
0008 //  Copyright Daniel Walker 2006. Use, modification and distribution
0009 //  are subject to the Boost Software License, Version 1.0. (See
0010 //  accompanying file LICENSE_1_0.txt or copy at
0011 //  http://www.boost.org/LICENSE_1_0.txt)
0012 //
0013 // For more information, see http://www.boost.org/libs/range/
0014 //
0015
0016 #ifndef BOOST_RANGE_CONCEPTS_HPP
0017 #define BOOST_RANGE_CONCEPTS_HPP
0018
0019 #include <boost/concept_check.hpp>
0020 #include <boost/iterator/iterator_concepts.hpp>
0021 #include <boost/range/begin.hpp>
0022 #include <boost/range/end.hpp>
0023 #include <boost/range/iterator.hpp>
0024 #include <boost/range/value_type.hpp>
0025 #include <boost/range/detail/misc_concept.hpp>
0026 #include <boost/type_traits/remove_reference.hpp>
0027
0028 #include <iterator>
0029
0030 /*!
0031  * \file
0032  * \brief Concept checks for the Boost Range library.
0033  *
0034  * The structures in this file may be used in conjunction with the
0035  * Boost Concept Check library to insure that the type of a function
0036  * parameter is compatible with a range concept. If not, a meaningful
0037  * compile time error is generated. Checks are provided for the range
0038  * concepts related to iterator traversal categories. For example, the
0039  * following line checks that the type T models the ForwardRange
0040  * concept.
0041  *
0042  * \code
0043  * BOOST_CONCEPT_ASSERT((ForwardRangeConcept<T>));
0044  * \endcode
0045  *
0046  * A different concept check is required to ensure writeable value
0047  * access. For example to check for a ForwardRange that can be written
0048  * to, the following code is required.
0049  *
0050  * \code
0051  * BOOST_CONCEPT_ASSERT((WriteableForwardRangeConcept<T>));
0052  * \endcode
0053  *
0054  * \see http://www.boost.org/libs/range/doc/range.html for details
0055  * about range concepts.
0056  * \see http://www.boost.org/libs/iterator/doc/iterator_concepts.html
0057  * for details about iterator concepts.
0058  * \see http://www.boost.org/libs/concept_check/concept_check.htm for
0059  * details about concept checks.
0060  */
0061
0062 namespace boost {
0063
0064     namespace range_detail {
0065
0066 #ifndef BOOST_RANGE_ENABLE_CONCEPT_ASSERT
0067
0068 // List broken compiler versions here:
0069 #ifndef __clang__
0070     #ifdef __GNUC__
0071         // GNUC 4.2 has strange issues correctly detecting compliance with the Concepts
0072         // hence the least disruptive approach is to turn-off the concept checking for
0073         // this version of the compiler.
0074         #if __GNUC__ == 4 && __GNUC_MINOR__ == 2
0075             #define BOOST_RANGE_ENABLE_CONCEPT_ASSERT 0
0076         #endif
0077     #endif
0078
0079     #ifdef __GCCXML__
0080         // GCC XML, unsurprisingly, has the same issues
0081         #if __GCCXML_GNUC__ == 4 && __GCCXML_GNUC_MINOR__ == 2
0082             #define BOOST_RANGE_ENABLE_CONCEPT_ASSERT 0
0083         #endif
0084     #endif
0085 #endif
0086
0087     #ifdef BOOST_BORLANDC
0088         #define BOOST_RANGE_ENABLE_CONCEPT_ASSERT 0
0089     #endif
0090
0091     #ifdef __PATHCC__
0092         #define BOOST_RANGE_ENABLE_CONCEPT_ASSERT 0
0093     #endif
0094
0095 // Default to using the concept asserts unless we have defined it off
0096 // during the search for black listed compilers.
0097     #ifndef BOOST_RANGE_ENABLE_CONCEPT_ASSERT
0098         #define BOOST_RANGE_ENABLE_CONCEPT_ASSERT 1
0099     #endif
0100
0101 #endif
0102
0103 #if BOOST_RANGE_ENABLE_CONCEPT_ASSERT
0104     #define BOOST_RANGE_CONCEPT_ASSERT( x ) BOOST_CONCEPT_ASSERT( x )
0105 #else
0106     #define BOOST_RANGE_CONCEPT_ASSERT( x )
0107 #endif
0108
0109         // Rationale for the inclusion of redefined iterator concept
0110         // classes:
0111         //
0112         // The Range algorithms often do not require that the iterators are
0113         // Assignable or default constructable, but the correct standard
0114         // conformant iterators do require the iterators to be a model of the
0115         // Assignable concept.
0116         // Iterators that contains a functor that is not assignable therefore
0117         // are not correct models of the standard iterator concepts,
0118         // despite being adequate for most algorithms. An example of this
0119         // use case is the combination of the boost::adaptors::filtered
0120         // class with a boost::lambda::bind generated functor.
0121         // Ultimately modeling the range concepts using composition
0122         // with the Boost.Iterator concepts would render the library
0123         // incompatible with many common Boost.Lambda expressions.
0124         template<class Iterator>
0125         struct IncrementableIteratorConcept : CopyConstructible<Iterator>
0126         {
0127 #if BOOST_RANGE_ENABLE_CONCEPT_ASSERT
0128             typedef BOOST_DEDUCED_TYPENAME iterator_traversal<Iterator>::type traversal_category;
0129
0130             BOOST_RANGE_CONCEPT_ASSERT((
0131                 Convertible<
0132                     traversal_category,
0133                     incrementable_traversal_tag
0134                 >));
0135
0136             BOOST_CONCEPT_USAGE(IncrementableIteratorConcept)
0137             {
0138                 ++i;
0139                 (void)i++;
0140             }
0141         private:
0142             Iterator i;
0143 #endif
0144         };
0145
0146         template<class Iterator>
0147         struct SinglePassIteratorConcept
0148             : IncrementableIteratorConcept<Iterator>
0149             , EqualityComparable<Iterator>
0150         {
0151 #if BOOST_RANGE_ENABLE_CONCEPT_ASSERT
0152             BOOST_RANGE_CONCEPT_ASSERT((
0153                 Convertible<
0154                     BOOST_DEDUCED_TYPENAME SinglePassIteratorConcept::traversal_category,
0155                     single_pass_traversal_tag
0156                 >));
0157
0158             BOOST_CONCEPT_USAGE(SinglePassIteratorConcept)
0159             {
0160                 Iterator i2(++i);
0161                 boost::ignore_unused_variable_warning(i2);
0162
0163                 // deliberately we are loose with the postfix version for the single pass
0164                 // iterator due to the commonly poor adherence to the specification means that
0165                 // many algorithms would be unusable, whereas actually without the check they
0166                 // work
0167                 (void)(i++);
0168
0169                 BOOST_DEDUCED_TYPENAME std::iterator_traits<Iterator>::reference r1(*i);
0170                 boost::ignore_unused_variable_warning(r1);
0171
0172                 BOOST_DEDUCED_TYPENAME std::iterator_traits<Iterator>::reference r2(*(++i));
0173                 boost::ignore_unused_variable_warning(r2);
0174             }
0175         private:
0176             Iterator i;
0177 #endif
0178         };
0179
0180         template<class Iterator>
0181         struct ForwardIteratorConcept
0182             : SinglePassIteratorConcept<Iterator>
0183             , DefaultConstructible<Iterator>
0184         {
0185 #if BOOST_RANGE_ENABLE_CONCEPT_ASSERT
0186             typedef BOOST_DEDUCED_TYPENAME std::iterator_traits<Iterator>::difference_type difference_type;
0187
0188             BOOST_MPL_ASSERT((is_integral<difference_type>));
0189             BOOST_MPL_ASSERT_RELATION(std::numeric_limits<difference_type>::is_signed, ==, true);
0190
0191             BOOST_RANGE_CONCEPT_ASSERT((
0192                 Convertible<
0193                     BOOST_DEDUCED_TYPENAME ForwardIteratorConcept::traversal_category,
0194                     forward_traversal_tag
0195                 >));
0196
0197             BOOST_CONCEPT_USAGE(ForwardIteratorConcept)
0198             {
0199                 // See the above note in the SinglePassIteratorConcept about the handling of the
0200                 // postfix increment. Since with forward and better iterators there is no need
0201                 // for a proxy, we can sensibly require that the dereference result
0202                 // is convertible to reference.
0203                 Iterator i2(i++);
0204                 boost::ignore_unused_variable_warning(i2);
0205                 BOOST_DEDUCED_TYPENAME std::iterator_traits<Iterator>::reference r(*(i++));
0206                 boost::ignore_unused_variable_warning(r);
0207             }
0208         private:
0209             Iterator i;
0210 #endif
0211          };
0212
0213          template<class Iterator>
0214          struct BidirectionalIteratorConcept
0215              : ForwardIteratorConcept<Iterator>
0216          {
0217  #if BOOST_RANGE_ENABLE_CONCEPT_ASSERT
0218              BOOST_RANGE_CONCEPT_ASSERT((
0219                  Convertible<
0220                      BOOST_DEDUCED_TYPENAME BidirectionalIteratorConcept::traversal_category,
0221                      bidirectional_traversal_tag
0222                  >));
0223
0224              BOOST_CONCEPT_USAGE(BidirectionalIteratorConcept)
0225              {
0226                  --i;
0227                  (void)i--;
0228              }
0229          private:
0230              Iterator i;
0231  #endif
0232          };
0233
0234          template<class Iterator>
0235          struct RandomAccessIteratorConcept
0236              : BidirectionalIteratorConcept<Iterator>
0237          {
0238  #if BOOST_RANGE_ENABLE_CONCEPT_ASSERT
0239              BOOST_RANGE_CONCEPT_ASSERT((
0240                  Convertible<
0241                      BOOST_DEDUCED_TYPENAME RandomAccessIteratorConcept::traversal_category,
0242                      random_access_traversal_tag
0243                  >));
0244
0245              BOOST_CONCEPT_USAGE(RandomAccessIteratorConcept)
0246              {
0247                  i += n;
0248                  i = i + n;
0249                  i = n + i;
0250                  i -= n;
0251                  i = i - n;
0252                  n = i - j;
0253              }
0254          private:
0255              BOOST_DEDUCED_TYPENAME BidirectionalIteratorConcept<Iterator>::difference_type n;
0256              Iterator i;
0257              Iterator j;
0258  #endif
0259          };
0260
0261     } // namespace range_detail
0262
0263     //! Check if a type T models the SinglePassRange range concept.
0264     template<class T>
0265     struct SinglePassRangeConcept
0266     {
0267 #if BOOST_RANGE_ENABLE_CONCEPT_ASSERT
0268         // A few compilers don't like the rvalue reference T types so just
0269         // remove it.
0270         typedef BOOST_DEDUCED_TYPENAME remove_reference<T>::type Rng;
0271
0272         typedef BOOST_DEDUCED_TYPENAME range_iterator<
0273             Rng const
0274         >::type const_iterator;
0275
0276         typedef BOOST_DEDUCED_TYPENAME range_iterator<Rng>::type iterator;
0277
0278         BOOST_RANGE_CONCEPT_ASSERT((
0279                 range_detail::SinglePassIteratorConcept<iterator>));
0280
0281         BOOST_RANGE_CONCEPT_ASSERT((
0282                 range_detail::SinglePassIteratorConcept<const_iterator>));
0283
0284         BOOST_CONCEPT_USAGE(SinglePassRangeConcept)
0285         {
0286             // This has been modified from assigning to this->i
0287             // (where i was a member variable) to improve
0288             // compatibility with Boost.Lambda
0289             iterator i1 = boost::begin(*m_range);
0290             iterator i2 = boost::end(*m_range);
0291
0292             boost::ignore_unused_variable_warning(i1);
0293             boost::ignore_unused_variable_warning(i2);
0294
0295             const_constraints(*m_range);
0296         }
0297
0298     private:
0299         void const_constraints(const Rng& const_range)
0300         {
0301             const_iterator ci1 = boost::begin(const_range);
0302             const_iterator ci2 = boost::end(const_range);
0303
0304             boost::ignore_unused_variable_warning(ci1);
0305             boost::ignore_unused_variable_warning(ci2);
0306         }
0307
0308        // Rationale:
0309        // The type of m_range is T* rather than T because it allows
0310        // T to be an abstract class. The other obvious alternative of
0311        // T& produces a warning on some compilers.
0312        Rng* m_range;
0313 #endif
0314     };
0315
0316     //! Check if a type T models the ForwardRange range concept.
0317     template<class T>
0318     struct ForwardRangeConcept : SinglePassRangeConcept<T>
0319     {
0320 #if BOOST_RANGE_ENABLE_CONCEPT_ASSERT
0321         BOOST_RANGE_CONCEPT_ASSERT((range_detail::ForwardIteratorConcept<BOOST_DEDUCED_TYPENAME ForwardRangeConcept::iterator>));
0322         BOOST_RANGE_CONCEPT_ASSERT((range_detail::ForwardIteratorConcept<BOOST_DEDUCED_TYPENAME ForwardRangeConcept::const_iterator>));
0323 #endif
0324     };
0325
0326     template<class T>
0327     struct WriteableRangeConcept
0328     {
0329 #if BOOST_RANGE_ENABLE_CONCEPT_ASSERT
0330         typedef BOOST_DEDUCED_TYPENAME range_iterator<T>::type iterator;
0331
0332         BOOST_CONCEPT_USAGE(WriteableRangeConcept)
0333         {
0334             *i = v;
0335         }
0336     private:
0337         iterator i;
0338         BOOST_DEDUCED_TYPENAME range_value<T>::type v;
0339 #endif
0340     };
0341
0342     //! Check if a type T models the WriteableForwardRange range concept.
0343     template<class T>
0344     struct WriteableForwardRangeConcept
0345         : ForwardRangeConcept<T>
0346         , WriteableRangeConcept<T>
0347     {
0348     };
0349
0350     //! Check if a type T models the BidirectionalRange range concept.
0351     template<class T>
0352     struct BidirectionalRangeConcept : ForwardRangeConcept<T>
0353     {
0354 #if BOOST_RANGE_ENABLE_CONCEPT_ASSERT
0355         BOOST_RANGE_CONCEPT_ASSERT((range_detail::BidirectionalIteratorConcept<BOOST_DEDUCED_TYPENAME BidirectionalRangeConcept::iterator>));
0356         BOOST_RANGE_CONCEPT_ASSERT((range_detail::BidirectionalIteratorConcept<BOOST_DEDUCED_TYPENAME BidirectionalRangeConcept::const_iterator>));
0357 #endif
0358     };
0359
0360     //! Check if a type T models the WriteableBidirectionalRange range concept.
0361     template<class T>
0362     struct WriteableBidirectionalRangeConcept
0363         : BidirectionalRangeConcept<T>
0364         , WriteableRangeConcept<T>
0365     {
0366     };
0367
0368     //! Check if a type T models the RandomAccessRange range concept.
0369     template<class T>
0370     struct RandomAccessRangeConcept : BidirectionalRangeConcept<T>
0371     {
0372 #if BOOST_RANGE_ENABLE_CONCEPT_ASSERT
0373         BOOST_RANGE_CONCEPT_ASSERT((range_detail::RandomAccessIteratorConcept<BOOST_DEDUCED_TYPENAME RandomAccessRangeConcept::iterator>));
0374         BOOST_RANGE_CONCEPT_ASSERT((range_detail::RandomAccessIteratorConcept<BOOST_DEDUCED_TYPENAME RandomAccessRangeConcept::const_iterator>));
0375 #endif
0376     };
0377
0378     //! Check if a type T models the WriteableRandomAccessRange range concept.
0379     template<class T>
0380     struct WriteableRandomAccessRangeConcept
0381         : RandomAccessRangeConcept<T>
0382         , WriteableRangeConcept<T>
0383     {
0384     };
0385
0386 } // namespace boost
0387
0388 #endif // BOOST_RANGE_CONCEPTS_HPP