[Range] begin/end ADL issues in C++0x range-based for
[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
At Sat, 18 Dec 2010 07:20:56 +0900, Michel MORIN wrote:
#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?
First, Michel, thanks for addressing this important matter. 2nd, I'm a wee bit worried about ODR issues. At first it looks like you're saying to define has_begin in namespace boost. Then your code seems to imply it's in namespace range_detail. I think the latter is probably OK, but not the former. The key thing is that the definition of boost::begin should not itself alter the result of has_begin for any given type. -- Dave Abrahams BoostPro Computing http://www.boostpro.com
Dave Abrahams wrote:
First, Michel, thanks for addressing this important matter. 2nd, I'm a wee bit worried about ODR issues. At first it looks like you're saying to define has_begin in namespace boost. Then your code seems to imply it's in namespace range_detail. I think the latter is probably OK, but not the former. The key thing is that the definition of boost::begin should not itself alter the result of has_begin for any given type.
Ah! It's the latter. I should have written as #ifndef BOOST_NO_RANGE_BASED_FOR namespace boost { using std::begin; namespace range_detail { // 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... So don't worry :-) Here is a complete code I added to boost/range/begin.hpp: (And I attached header files (not the patches) in this mail, for convenience.) #ifndef BOOST_NO_RANGE_BASED_FOR #include <boost/mpl/bool.hpp> #include <boost/utility/enable_if.hpp> #include <boost/range/iterator.hpp> namespace boost { using std::begin; namespace range_detail { template <typename T> struct has_begin_impl { typedef char true_type; typedef char false_type[2]; template <typename S> static true_type& check(S* s_ptr, decltype(s_ptr->begin())* = 0); template <typename S> static false_type& check(...); static const bool value = sizeof(check<T>(0)) == sizeof(true_type); }; template <typename T> struct has_begin : boost::mpl::bool_<has_begin_impl<T>::value> {}; } 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); } template <typename Range> inline typename boost::range_iterator<Range const>::type begin(Range const& rng, typename disable_if<range_detail::has_begin<Range>>::type* = 0) { return range_begin(rng); } } #else // existing code... Regards, Michel
On 17.12.2010 23:20, Michel MORIN wrote:
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:
Hi, Again I assert that range-based for has nothing to do with this. It's std::begin() and std::end() that are the problem. I suggest you rename the feature macro to BOOST_NO_STD_BEGIN_END and put it in the standard library part of the configuration (boost/config/stdlib). Aside from that, very good and important work. Sebastian
Hi Sebastian, Thanks for your comment.
I suggest you rename the feature macro to BOOST_NO_STD_BEGIN_END and put it in the standard library part of the configuration (boost/config/stdlib).
I don't have strong opinion about renaming, but I'd like to hear other's opinions. BTW, I'm beginning to think that using ADL barrier technique to boost::begin/end is enough to solve ambiguity call problems. This might break existing codes that rely on ADL to find boost::begin/end, but this is so simple and does not need to define a new macro. Furthermore, this does not need #ifdef blocks. Regards, Michel
On 12/20/2010 11:06 PM, Michel MORIN wrote:
Hi Sebastian, Thanks for your comment.
I suggest you rename the feature macro to BOOST_NO_STD_BEGIN_END and put it in the standard library part of the configuration (boost/config/stdlib).
I don't have strong opinion about renaming, but I'd like to hear other's opinions.
BTW, I'm beginning to think that using ADL barrier technique to boost::begin/end is enough to solve ambiguity call problems. [...]
Just to be clear, as you seemed to indicate something slightly different in another post: Do you propose to prevent boost::begin/end from being picked up by ADL; to prevent boost::fusion::begin/end from being picked up by ADL; or both...? Do either of these begin/end combinations actually *need* to be found via ADL (i.e., is that a desirable feature, regardless of it possibly breaking existing code)? Ranges adapted to work with Boost.Range (by defining range_begin/range_end) will generally have to be re-adapted to work with the range-based for loops, so I wouldn't think relying on boost::begin/end to be found via ADL to be too useful... Also, again to be clear: What are the tradeoffs between defining Boost.Fusion's begin/end in another namespace and bringing them into the boost::fusion namespace with a using declaration; and defining the data structures in another namespace and bringing them into the boost::fusion namespace with a using declaration; or both? - Jeff
Hi Jeffrey, Jeffrey Lee Hellrung, Jr. wrote:
Just to be clear, as you seemed to indicate something slightly different in another post: Do you propose to prevent boost::begin/end from being picked up by ADL; to prevent boost::fusion::begin/end from being picked up by ADL; or both...?
For boost::begin/end, when I started this thread, I managed not to break existing codes and so boost::begin/end can be picked by ADL. But after I read your post in the Fusion thread, I was beginning to think that cooperation between boost::begin/end and ADL is not important and that solving the ambiguity call problem by ADL barrier is a very simple and acceptable way. For boost::fusion::begin/end, when I started the Fusion thread, I also managed not to break existing codes and so boost::fusion::begin/end can be picked by ADL. But after I read your post in the Fusion thread, I agreed with your solution.
Do either of these begin/end combinations actually *need* to be found via ADL (i.e., is that a desirable feature, regardless of it possibly breaking existing code)?
Now, my answer is no.
Ranges adapted to work with Boost.Range (by defining range_begin/range_end) will generally have to be re-adapted to work with the range-based for loops, so I wouldn't think relying on boost::begin/end to be found via ADL to be too useful...
Agreed.
Also, again to be clear: What are the tradeoffs between defining Boost.Fusion's begin/end in another namespace and bringing them into the boost::fusion namespace with a using declaration; and defining the data structures in another namespace and bringing them into the boost::fusion namespace with a using declaration; or both?
Oh, I remembered the ADL barrier idiom wrongly; I was thinking only the former is the idiom (and I didn't know that a using directive should be used in the former case). Thank you for pointing this out, Jeffrey. The correct idiom is: - Define Fusion's begin/end in another namespace and bringing them into the boost::fusion namespace with a using directive (not with a using declaration). or - Define the data type in another namespace and bringing them into the boost::fusion namespace with a using declaration/directive. The former prevents boost::fusion::begin/end from being picked up by ADL. The latter prevents any ADL for the data type, except ADL triggered by data type's template arguments and base classes. I cannot tell which is more suitable. Do you have any idea? Regards, Michel
Compiler errors (ambiguous calls to begin/end) are generated, when ADL finds both std::begin/end and boost::begin/end in range-based for
Fixed in trunk (r67541) by Neil using the ADL barrier technique. Now, the unqualified begin/end calls do not cause ambiguities between boost::begin/end and std::begin/end. Thanks Neil! Regards, Michel
participants (4)
-
Dave Abrahams -
Jeffrey Lee Hellrung, Jr. -
Michel MORIN -
Sebastian Redl