Chris@16: // Boost.Range library concept checks
Chris@16: //
Chris@16: //  Copyright Neil Groves 2009. Use, modification and distribution
Chris@16: //  are subject to the Boost Software License, Version 1.0. (See
Chris@16: //  accompanying file LICENSE_1_0.txt or copy at
Chris@16: //  http://www.boost.org/LICENSE_1_0.txt)
Chris@16: //
Chris@16: //  Copyright Daniel Walker 2006. Use, modification and distribution
Chris@16: //  are subject to the Boost Software License, Version 1.0. (See
Chris@16: //  accompanying file LICENSE_1_0.txt or copy at
Chris@16: //  http://www.boost.org/LICENSE_1_0.txt)
Chris@16: //
Chris@16: // For more information, see http://www.boost.org/libs/range/
Chris@16: //
Chris@16: 
Chris@16: #ifndef BOOST_RANGE_CONCEPTS_HPP
Chris@16: #define BOOST_RANGE_CONCEPTS_HPP
Chris@16: 
Chris@16: #include <boost/concept_check.hpp>
Chris@16: #include <boost/iterator/iterator_concepts.hpp>
Chris@16: #include <boost/range/begin.hpp>
Chris@16: #include <boost/range/end.hpp>
Chris@16: #include <boost/range/iterator.hpp>
Chris@16: #include <boost/range/value_type.hpp>
Chris@16: #include <boost/range/detail/misc_concept.hpp>
Chris@101: #include <boost/type_traits/remove_reference.hpp>
Chris@16: 
Chris@16: /*!
Chris@16:  * \file
Chris@16:  * \brief Concept checks for the Boost Range library.
Chris@16:  *
Chris@16:  * The structures in this file may be used in conjunction with the
Chris@16:  * Boost Concept Check library to insure that the type of a function
Chris@16:  * parameter is compatible with a range concept. If not, a meaningful
Chris@16:  * compile time error is generated. Checks are provided for the range
Chris@16:  * concepts related to iterator traversal categories. For example, the
Chris@16:  * following line checks that the type T models the ForwardRange
Chris@16:  * concept.
Chris@16:  *
Chris@16:  * \code
Chris@16:  * BOOST_CONCEPT_ASSERT((ForwardRangeConcept<T>));
Chris@16:  * \endcode
Chris@16:  *
Chris@16:  * A different concept check is required to ensure writeable value
Chris@16:  * access. For example to check for a ForwardRange that can be written
Chris@16:  * to, the following code is required.
Chris@16:  *
Chris@16:  * \code
Chris@16:  * BOOST_CONCEPT_ASSERT((WriteableForwardRangeConcept<T>));
Chris@16:  * \endcode
Chris@16:  *
Chris@16:  * \see http://www.boost.org/libs/range/doc/range.html for details
Chris@16:  * about range concepts.
Chris@16:  * \see http://www.boost.org/libs/iterator/doc/iterator_concepts.html
Chris@16:  * for details about iterator concepts.
Chris@16:  * \see http://www.boost.org/libs/concept_check/concept_check.htm for
Chris@16:  * details about concept checks.
Chris@16:  */
Chris@16: 
Chris@16: namespace boost {
Chris@16: 
Chris@16:     namespace range_detail {
Chris@16: 
Chris@16: #ifndef BOOST_RANGE_ENABLE_CONCEPT_ASSERT
Chris@16: 
Chris@16: // List broken compiler versions here:
Chris@101: #ifndef __clang__
Chris@16:     #ifdef __GNUC__
Chris@16:         // GNUC 4.2 has strange issues correctly detecting compliance with the Concepts
Chris@16:         // hence the least disruptive approach is to turn-off the concept checking for
Chris@16:         // this version of the compiler.
Chris@16:         #if __GNUC__ == 4 && __GNUC_MINOR__ == 2
Chris@16:             #define BOOST_RANGE_ENABLE_CONCEPT_ASSERT 0
Chris@16:         #endif
Chris@16:     #endif
Chris@16: 
Chris@101:     #ifdef __GCCXML__
Chris@101:         // GCC XML, unsurprisingly, has the same issues
Chris@101:         #if __GCCXML_GNUC__ == 4 && __GCCXML_GNUC_MINOR__ == 2
Chris@101:             #define BOOST_RANGE_ENABLE_CONCEPT_ASSERT 0
Chris@101:         #endif
Chris@101:     #endif
Chris@101: #endif
Chris@101: 
Chris@16:     #ifdef __BORLANDC__
Chris@16:         #define BOOST_RANGE_ENABLE_CONCEPT_ASSERT 0
Chris@16:     #endif
Chris@16: 
Chris@16:     #ifdef __PATHCC__
Chris@16:         #define BOOST_RANGE_ENABLE_CONCEPT_ASSERT 0
Chris@16:     #endif
Chris@16: 
Chris@16: // Default to using the concept asserts unless we have defined it off
Chris@16: // during the search for black listed compilers.
Chris@16:     #ifndef BOOST_RANGE_ENABLE_CONCEPT_ASSERT
Chris@16:         #define BOOST_RANGE_ENABLE_CONCEPT_ASSERT 1
Chris@16:     #endif
Chris@16: 
Chris@16: #endif
Chris@16: 
Chris@16: #if BOOST_RANGE_ENABLE_CONCEPT_ASSERT
Chris@16:     #define BOOST_RANGE_CONCEPT_ASSERT( x ) BOOST_CONCEPT_ASSERT( x )
Chris@16: #else
Chris@16:     #define BOOST_RANGE_CONCEPT_ASSERT( x )
Chris@16: #endif
Chris@16: 
Chris@16:         // Rationale for the inclusion of redefined iterator concept
Chris@16:         // classes:
Chris@16:         //
Chris@16:         // The Range algorithms often do not require that the iterators are
Chris@16:         // Assignable or default constructable, but the correct standard
Chris@16:         // conformant iterators do require the iterators to be a model of the
Chris@16:         // Assignable concept.
Chris@16:         // Iterators that contains a functor that is not assignable therefore
Chris@16:         // are not correct models of the standard iterator concepts,
Chris@16:         // despite being adequate for most algorithms. An example of this
Chris@16:         // use case is the combination of the boost::adaptors::filtered
Chris@16:         // class with a boost::lambda::bind generated functor.
Chris@16:         // Ultimately modeling the range concepts using composition
Chris@16:         // with the Boost.Iterator concepts would render the library
Chris@16:         // incompatible with many common Boost.Lambda expressions.
Chris@16:         template<class Iterator>
Chris@16:         struct IncrementableIteratorConcept : CopyConstructible<Iterator>
Chris@16:         {
Chris@16: #if BOOST_RANGE_ENABLE_CONCEPT_ASSERT
Chris@16:             typedef BOOST_DEDUCED_TYPENAME iterator_traversal<Iterator>::type traversal_category;
Chris@16: 
Chris@16:             BOOST_RANGE_CONCEPT_ASSERT((
Chris@16:                 Convertible<
Chris@16:                     traversal_category,
Chris@16:                     incrementable_traversal_tag
Chris@16:                 >));
Chris@16: 
Chris@16:             BOOST_CONCEPT_USAGE(IncrementableIteratorConcept)
Chris@16:             {
Chris@16:                 ++i;
Chris@16:                 (void)i++;
Chris@16:             }
Chris@16:         private:
Chris@16:             Iterator i;
Chris@16: #endif
Chris@16:         };
Chris@16: 
Chris@16:         template<class Iterator>
Chris@16:         struct SinglePassIteratorConcept
Chris@16:             : IncrementableIteratorConcept<Iterator>
Chris@16:             , EqualityComparable<Iterator>
Chris@16:         {
Chris@16: #if BOOST_RANGE_ENABLE_CONCEPT_ASSERT
Chris@16:             BOOST_RANGE_CONCEPT_ASSERT((
Chris@16:                 Convertible<
Chris@16:                     BOOST_DEDUCED_TYPENAME SinglePassIteratorConcept::traversal_category,
Chris@16:                     single_pass_traversal_tag
Chris@16:                 >));
Chris@16: 
Chris@16:             BOOST_CONCEPT_USAGE(SinglePassIteratorConcept)
Chris@16:             {
Chris@16:                 Iterator i2(++i);
Chris@16:                 boost::ignore_unused_variable_warning(i2);
Chris@16: 
Chris@16:                 // deliberately we are loose with the postfix version for the single pass
Chris@16:                 // iterator due to the commonly poor adherence to the specification means that
Chris@16:                 // many algorithms would be unusable, whereas actually without the check they
Chris@16:                 // work
Chris@16:                 (void)(i++);
Chris@16: 
Chris@16:                 BOOST_DEDUCED_TYPENAME boost::detail::iterator_traits<Iterator>::reference r1(*i);
Chris@16:                 boost::ignore_unused_variable_warning(r1);
Chris@16: 
Chris@16:                 BOOST_DEDUCED_TYPENAME boost::detail::iterator_traits<Iterator>::reference r2(*(++i));
Chris@16:                 boost::ignore_unused_variable_warning(r2);
Chris@16:             }
Chris@16:         private:
Chris@16:             Iterator i;
Chris@16: #endif
Chris@16:         };
Chris@16: 
Chris@16:         template<class Iterator>
Chris@16:         struct ForwardIteratorConcept
Chris@16:             : SinglePassIteratorConcept<Iterator>
Chris@16:             , DefaultConstructible<Iterator>
Chris@16:         {
Chris@16: #if BOOST_RANGE_ENABLE_CONCEPT_ASSERT
Chris@16:             typedef BOOST_DEDUCED_TYPENAME boost::detail::iterator_traits<Iterator>::difference_type difference_type;
Chris@16: 
Chris@16:             BOOST_MPL_ASSERT((is_integral<difference_type>));
Chris@16:             BOOST_MPL_ASSERT_RELATION(std::numeric_limits<difference_type>::is_signed, ==, true);
Chris@16: 
Chris@16:             BOOST_RANGE_CONCEPT_ASSERT((
Chris@16:                 Convertible<
Chris@16:                     BOOST_DEDUCED_TYPENAME ForwardIteratorConcept::traversal_category,
Chris@16:                     forward_traversal_tag
Chris@16:                 >));
Chris@16: 
Chris@16:             BOOST_CONCEPT_USAGE(ForwardIteratorConcept)
Chris@16:             {
Chris@16:                 // See the above note in the SinglePassIteratorConcept about the handling of the
Chris@16:                 // postfix increment. Since with forward and better iterators there is no need
Chris@16:                 // for a proxy, we can sensibly require that the dereference result
Chris@16:                 // is convertible to reference.
Chris@16:                 Iterator i2(i++);
Chris@16:                 boost::ignore_unused_variable_warning(i2);
Chris@16:                 BOOST_DEDUCED_TYPENAME boost::detail::iterator_traits<Iterator>::reference r(*(i++));
Chris@16:                 boost::ignore_unused_variable_warning(r);
Chris@16:             }
Chris@16:         private:
Chris@16:             Iterator i;
Chris@16: #endif
Chris@16:          };
Chris@16: 
Chris@16:          template<class Iterator>
Chris@16:          struct BidirectionalIteratorConcept
Chris@16:              : ForwardIteratorConcept<Iterator>
Chris@16:          {
Chris@16:  #if BOOST_RANGE_ENABLE_CONCEPT_ASSERT
Chris@16:              BOOST_RANGE_CONCEPT_ASSERT((
Chris@16:                  Convertible<
Chris@16:                      BOOST_DEDUCED_TYPENAME BidirectionalIteratorConcept::traversal_category,
Chris@16:                      bidirectional_traversal_tag
Chris@16:                  >));
Chris@16: 
Chris@16:              BOOST_CONCEPT_USAGE(BidirectionalIteratorConcept)
Chris@16:              {
Chris@16:                  --i;
Chris@16:                  (void)i--;
Chris@16:              }
Chris@16:          private:
Chris@16:              Iterator i;
Chris@16:  #endif
Chris@16:          };
Chris@16: 
Chris@16:          template<class Iterator>
Chris@16:          struct RandomAccessIteratorConcept
Chris@16:              : BidirectionalIteratorConcept<Iterator>
Chris@16:          {
Chris@16:  #if BOOST_RANGE_ENABLE_CONCEPT_ASSERT
Chris@16:              BOOST_RANGE_CONCEPT_ASSERT((
Chris@16:                  Convertible<
Chris@16:                      BOOST_DEDUCED_TYPENAME RandomAccessIteratorConcept::traversal_category,
Chris@16:                      random_access_traversal_tag
Chris@16:                  >));
Chris@16: 
Chris@16:              BOOST_CONCEPT_USAGE(RandomAccessIteratorConcept)
Chris@16:              {
Chris@16:                  i += n;
Chris@16:                  i = i + n;
Chris@16:                  i = n + i;
Chris@16:                  i -= n;
Chris@16:                  i = i - n;
Chris@16:                  n = i - j;
Chris@16:              }
Chris@16:          private:
Chris@16:              BOOST_DEDUCED_TYPENAME RandomAccessIteratorConcept::difference_type n;
Chris@16:              Iterator i;
Chris@16:              Iterator j;
Chris@16:  #endif
Chris@16:          };
Chris@16: 
Chris@16:     } // namespace range_detail
Chris@16: 
Chris@16:     //! Check if a type T models the SinglePassRange range concept.
Chris@16:     template<class T>
Chris@16:     struct SinglePassRangeConcept
Chris@16:     {
Chris@16: #if BOOST_RANGE_ENABLE_CONCEPT_ASSERT
Chris@101:         // A few compilers don't like the rvalue reference T types so just
Chris@101:         // remove it.
Chris@101:         typedef BOOST_DEDUCED_TYPENAME remove_reference<T>::type Rng;
Chris@16: 
Chris@101:         typedef BOOST_DEDUCED_TYPENAME range_iterator<
Chris@101:             Rng const
Chris@101:         >::type const_iterator;
Chris@16: 
Chris@101:         typedef BOOST_DEDUCED_TYPENAME range_iterator<Rng>::type iterator;
Chris@101: 
Chris@101:         BOOST_RANGE_CONCEPT_ASSERT((
Chris@101:                 range_detail::SinglePassIteratorConcept<iterator>));
Chris@101: 
Chris@101:         BOOST_RANGE_CONCEPT_ASSERT((
Chris@101:                 range_detail::SinglePassIteratorConcept<const_iterator>));
Chris@101: 
Chris@101:         BOOST_CONCEPT_USAGE(SinglePassRangeConcept)
Chris@101:         {
Chris@16:             // This has been modified from assigning to this->i
Chris@16:             // (where i was a member variable) to improve
Chris@16:             // compatibility with Boost.Lambda
Chris@16:             iterator i1 = boost::begin(*m_range);
Chris@16:             iterator i2 = boost::end(*m_range);
Chris@16: 
Chris@101:             boost::ignore_unused_variable_warning(i1);
Chris@101:             boost::ignore_unused_variable_warning(i2);
Chris@16: 
Chris@16:             const_constraints(*m_range);
Chris@16:         }
Chris@16: 
Chris@16:     private:
Chris@101:         void const_constraints(const Rng& const_range)
Chris@16:         {
Chris@16:             const_iterator ci1 = boost::begin(const_range);
Chris@16:             const_iterator ci2 = boost::end(const_range);
Chris@16: 
Chris@101:             boost::ignore_unused_variable_warning(ci1);
Chris@101:             boost::ignore_unused_variable_warning(ci2);
Chris@16:         }
Chris@16: 
Chris@16:        // Rationale:
Chris@16:        // The type of m_range is T* rather than T because it allows
Chris@16:        // T to be an abstract class. The other obvious alternative of
Chris@16:        // T& produces a warning on some compilers.
Chris@101:        Rng* m_range;
Chris@16: #endif
Chris@16:     };
Chris@16: 
Chris@16:     //! Check if a type T models the ForwardRange range concept.
Chris@16:     template<class T>
Chris@16:     struct ForwardRangeConcept : SinglePassRangeConcept<T>
Chris@16:     {
Chris@16: #if BOOST_RANGE_ENABLE_CONCEPT_ASSERT
Chris@16:         BOOST_RANGE_CONCEPT_ASSERT((range_detail::ForwardIteratorConcept<BOOST_DEDUCED_TYPENAME ForwardRangeConcept::iterator>));
Chris@16:         BOOST_RANGE_CONCEPT_ASSERT((range_detail::ForwardIteratorConcept<BOOST_DEDUCED_TYPENAME ForwardRangeConcept::const_iterator>));
Chris@16: #endif
Chris@16:     };
Chris@16: 
Chris@101:     template<class T>
Chris@16:     struct WriteableRangeConcept
Chris@16:     {
Chris@16: #if BOOST_RANGE_ENABLE_CONCEPT_ASSERT
Chris@101:         typedef BOOST_DEDUCED_TYPENAME range_iterator<T>::type iterator;
Chris@16: 
Chris@16:         BOOST_CONCEPT_USAGE(WriteableRangeConcept)
Chris@16:         {
Chris@16:             *i = v;
Chris@16:         }
Chris@16:     private:
Chris@16:         iterator i;
Chris@101:         BOOST_DEDUCED_TYPENAME range_value<T>::type v;
Chris@16: #endif
Chris@16:     };
Chris@16: 
Chris@16:     //! Check if a type T models the WriteableForwardRange range concept.
Chris@16:     template<class T>
Chris@16:     struct WriteableForwardRangeConcept
Chris@16:         : ForwardRangeConcept<T>
Chris@16:         , WriteableRangeConcept<T>
Chris@16:     {
Chris@16:     };
Chris@16: 
Chris@16:     //! Check if a type T models the BidirectionalRange range concept.
Chris@16:     template<class T>
Chris@16:     struct BidirectionalRangeConcept : ForwardRangeConcept<T>
Chris@16:     {
Chris@16: #if BOOST_RANGE_ENABLE_CONCEPT_ASSERT
Chris@16:         BOOST_RANGE_CONCEPT_ASSERT((range_detail::BidirectionalIteratorConcept<BOOST_DEDUCED_TYPENAME BidirectionalRangeConcept::iterator>));
Chris@16:         BOOST_RANGE_CONCEPT_ASSERT((range_detail::BidirectionalIteratorConcept<BOOST_DEDUCED_TYPENAME BidirectionalRangeConcept::const_iterator>));
Chris@16: #endif
Chris@16:     };
Chris@16: 
Chris@16:     //! Check if a type T models the WriteableBidirectionalRange range concept.
Chris@16:     template<class T>
Chris@16:     struct WriteableBidirectionalRangeConcept
Chris@16:         : BidirectionalRangeConcept<T>
Chris@16:         , WriteableRangeConcept<T>
Chris@16:     {
Chris@16:     };
Chris@16: 
Chris@16:     //! Check if a type T models the RandomAccessRange range concept.
Chris@16:     template<class T>
Chris@16:     struct RandomAccessRangeConcept : BidirectionalRangeConcept<T>
Chris@16:     {
Chris@16: #if BOOST_RANGE_ENABLE_CONCEPT_ASSERT
Chris@16:         BOOST_RANGE_CONCEPT_ASSERT((range_detail::RandomAccessIteratorConcept<BOOST_DEDUCED_TYPENAME RandomAccessRangeConcept::iterator>));
Chris@16:         BOOST_RANGE_CONCEPT_ASSERT((range_detail::RandomAccessIteratorConcept<BOOST_DEDUCED_TYPENAME RandomAccessRangeConcept::const_iterator>));
Chris@16: #endif
Chris@16:     };
Chris@16: 
Chris@16:     //! Check if a type T models the WriteableRandomAccessRange range concept.
Chris@16:     template<class T>
Chris@16:     struct WriteableRandomAccessRangeConcept
Chris@16:         : RandomAccessRangeConcept<T>
Chris@16:         , WriteableRangeConcept<T>
Chris@16:     {
Chris@16:     };
Chris@16: 
Chris@16: } // namespace boost
Chris@16: 
Chris@16: #endif // BOOST_RANGE_CONCEPTS_HPP