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