[boost] [Range] begin/end ADL issues in C++0x range-based for

17 Dec 2010

      [Range] begin/end ADL issues in C++0x range-based for

Hi,

I recently played around with C++0x range-based for (available on GCC
4.6 Pre-Release).
It turned out that some codes using Boost libraries do not compile.
Compiler errors (ambiguous calls to begin/end) are generated,
when ADL finds both std::begin/end and boost::begin/end in range-based for and
there is no single best match.
Remarkably, boost::iterator_range (and adapted ranges in Boost.Range) cannot be
used in range-based for.

First let us recall range-based for.
A range-based for
    for (auto x : range_expr) {
        // do something
    }
is equivalent to
    {
        // Special rule: namespace std is added to rng's associated namespaces
        auto&& rng = range_expr;

        for (
            auto it = begin(rng),
                 it_end = end(rng);
            it != it_end;
            ++it
        ) {
            auto x = *it;
            // do something
        }
    }
Note that rng has namespace std as its associated namespaces
and the unqualified begin/end function call triggers ADL.

In C++0x, there are std::begin functions (for simplicity, let's ignore end):
    template <typename Range> auto begin(Range&       r) -> decltype(r.begin());
    template <typename Range> auto begin(Range const& r) -> decltype(r.begin());
And Boost.Range has boost::begin functions:
    template <typename Range>
    inline typename boost::range_iterator<Range      >::type
begin(Range&       r);
    template <typename Range>
    inline typename boost::range_iterator<Range const>::type
begin(Range const& r);

So, if
 - rng has namespace boost as its associated namespaces,
 - the header file boost/range/begin.hpp is included, and
 - there is no single best match between std::begin and boost::begin,
then unqualified begin function call becomes ambiguous.
For example, all the following codes fail to be compiled:

// code 1
#include <boost/range/iterator_range.hpp>
for (auto x : boost::iterator_range<int*>(nullptr, nullptr)) {} // error

// code 2
#include <boost/ptr_container/ptr_vector.hpp>
for (auto x : boost::ptr_vector<int>()) {} // error

// code 3
#include <vector>
#include <boost/range/adaptor/reversed.hpp>
for (auto x : std::vector<int>() | boost::adaptors::reversed) {} // error

// code 4
#include <boost/algorithm/string.hpp>
#include <boost/array.hpp>
for (auto x : boost::array<int, 2>()) {} // error

// code 5
#include <vector>
#include <boost/shared_ptr.hpp>
#include <boost/range/algorithm.hpp>
for (auto x : std::vector<boost::shared_ptr<int> >()) {} // error

These errors can be resolved by fixing boost/range/begin.hpp.
The fix uses a using-declaration ("using std::begin;") and
SFINAE (disable_if with "has_begin" metafunction).
A summary of range-based-for-compatible <boost/range/begin.hpp> is the
following:

#ifndef BOOST_NO_RANGE_BASED_FOR
namespace boost {
    using std::begin;

    // has_begin metafunction...

    template <typename Range>
    inline typename boost::range_iterator<Range>::type
    begin(Range& rng, typename
disable_if<range_detail::has_begin<Range>>::type* = 0)
    {
        return range_begin(rng);
    }

	// const version ...
}
#else
// existing code...

For details, see the attached.
I also attach a patch for Boost.Config to add BOOST_NO_RANGE_BASED_FOR.
Any comments or thoughs?

Regards,
Michel

[boost] [Range] begin/end ADL issues in C++0x range-based for

Michel MORIN