[lib++][ranges][NFC] Refactor `iterator_operations.h` to use tags.

[var-const]

Summary

Change the mechanism in iterator_operations.h to pass around a generic
policy tag indicating whether an internal function is being invoked from
a "classic" STL algorithm or a ranges algorithm. IterOps is now
a template class specialized on the policy tag.

The advantage is that this mechanism is more generic and allows defining
arbitrary conditions in a clean manner.

Also add a few more iterator functions to IterOps.

[var-const]

Address feedback.

[huixie90]

libcxx/include/__algorithm/iterator_operations.h

68

I think you need to remove all the cv_ref instead of just the reference

68

I thought I've commented somewhere I don't seem to find it anymore. Just be aware that the type of std::move(*std::forward<_Iter>(__i)); does not always match
typename iterator_traits<typename remove_reference<_Iter>::type>::value_type&&. e.g. vector<bool>::itertor. But I think the code you've written is fine because most of the time the users do want the conversion (except for the new c++20 stuff which is not meant to be usable for classic algorithms)

[var-const]

libcxx/include/__algorithm/iterator_operations.h

68

Thanks, this is a very good point. I also think it should be okay given how it's used.

[var-const]

Rebase on main, address feedback.

[philnik]

LGTM % nits and with green CI.

libcxx/include/__algorithm/iterator_operations.h

76

Is there a reason you don't use the customization point? AFAIK iter_swap has to be implemented properly or not at all, just like swap.

libcxx/include/__algorithm/lower_bound.h

31

_AlgPolicy?

52

There shouldn't be any underscores here.

libcxx/include/__algorithm/set_intersection.h

37

I think _AlgPolicy would be a bit better and more consistent with _RangesAlgPolicy and _ClassicAlgPolicy.

[huixie90]

libcxx/include/__algorithm/iterator_operations.h

39

question. why double underscores here?

76

std::iter_swap is not a customization point, it simply does the two step swap (using std::swap then ADL swap).
On the other hand, std::ranges::iter_swap is a customization point where ADL iter_swap should be looked up.
(unrelated but FYI std::iter_swap is not constrained so to make std::ranges::iter_swap work probably, it needs the poison pill void iter_swap(a,b) = delete;)

Anyway I think this code is fine as std::iter_swap isn't a customization point.

[philnik]

libcxx/include/__algorithm/iterator_operations.h

39

iter_move is only used by the standard since C++20, so we can't use it in earlier versions.

76

I misread the cppreference entry as it being a customization point. Never mind then.

[var-const]

Address feedback, fix the CI.

libcxx/include/__algorithm/iterator_operations.h

39

Theoretically, a user could define a macro "overriding" the name unless it's a name reserved for the implementation (which iter_move isn't until C++20 like Nikolas mentioned).

[var-const]

Rename one remaining "tag" to "policy".

[var-const]

Fix the CI.

[var-const]

Rebase.

libcxx/include/__algorithm/equal_range.h

while (__len != 0)
             __len = __l2;
         }
         else
         {
             auto __proj = std::__identity();
             _ForwardIterator __mp1 = __m;
             return pair<_ForwardIterator, _ForwardIterator>
                    (
-                      _VSTD::__lower_bound_impl<_StdIterOps>(__first, __m, __value, __comp, __proj),
+                      _VSTD::__lower_bound_impl<_ClassicAlgPolicy>(__first, __m, __value, __comp, __proj),
                       _VSTD::__upper_bound<_Compare>(++__mp1, __last, __value, __comp)
                    );
         }
     }
     return pair<_ForwardIterator, _ForwardIterator>(__first, __first);
 }
 
 template <class _ForwardIterator, class _Tp, class _Compare>

libcxx/include/__algorithm/iterator_operations.h

 //===----------------------------------------------------------------------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 
-#ifndef _LIBCPP___ALGORIHTM_ITERATOR_OPERATIONS_H
-#define _LIBCPP___ALGORIHTM_ITERATOR_OPERATIONS_H
+#ifndef _LIBCPP___ALGORITHM_ITERATOR_OPERATIONS_H
+#define _LIBCPP___ALGORITHM_ITERATOR_OPERATIONS_H
 
+#include <__algorithm/iter_swap.h>
 #include <__config>
 #include <__iterator/advance.h>
 #include <__iterator/distance.h>
+#include <__iterator/iter_move.h>
+#include <__iterator/iter_swap.h>
 #include <__iterator/iterator_traits.h>
 #include <__iterator/next.h>
+#include <__utility/forward.h>
+#include <__utility/move.h>
+#include <type_traits>
 
 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
 #  pragma GCC system_header
 #endif
 
 _LIBCPP_BEGIN_NAMESPACE_STD
 
+template <class _AlgPolicy> struct _IterOps;
+
 #if _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES)
-struct _RangesIterOps {
+struct _RangeAlgPolicy {};
+
+template <>
+struct _IterOps<_RangeAlgPolicy> {
   static constexpr auto advance = ranges::advance;
   static constexpr auto distance = ranges::distance;
+  static constexpr auto __iter_move = ranges::iter_move;
+  static constexpr auto iter_swap = ranges::iter_swap;
   static constexpr auto next = ranges::next;
 };
 #endif
 
-struct _StdIterOps {
+struct _ClassicAlgPolicy {};
+
+template <>
+struct _IterOps<_ClassicAlgPolicy> {
 
-  template <class _Iterator, class _Distance>
-  _LIBCPP_HIDE_FROM_ABI static _LIBCPP_CONSTEXPR_AFTER_CXX11 void advance(_Iterator& __iter, _Distance __count) {
-    return std::advance(__iter, __count);
+  // advance
+  template <class _Iter, class _Distance>
+  _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX11
+  static void advance(_Iter& __iter, _Distance __count) {
+    std::advance(__iter, __count);
   }
 
-  template <class _Iterator>
-  _LIBCPP_HIDE_FROM_ABI static _LIBCPP_CONSTEXPR_AFTER_CXX11
-  typename iterator_traits<_Iterator>::difference_type distance(_Iterator __first, _Iterator __last) {
+  // distance
+  template <class _Iter>
+  _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX11
+  static typename iterator_traits<_Iter>::difference_type distance(_Iter __first, _Iter __last) {
     return std::distance(__first, __last);
   }
 
+  // iter_move
+  template <class _Iter>
+  _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX11
+  // Declaring the return type is necessary for the C++03 mode (which doesn't support placeholder return types).
+  static typename iterator_traits<__uncvref_t<_Iter> >::value_type&& __iter_move(_Iter&& __i) {
+    return std::move(*std::forward<_Iter>(__i));
+  }
+
+  // iter_swap
+  template <class _Iter1, class _Iter2>
+  _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX11
+  static void iter_swap(_Iter1&& __a, _Iter2&& __b) {
+    std::iter_swap(std::forward<_Iter1>(__a), std::forward<_Iter2>(__b));
+  }
+
+  // next
   template <class _Iterator>
   _LIBCPP_HIDE_FROM_ABI static _LIBCPP_CONSTEXPR_AFTER_CXX11
   _Iterator next(_Iterator, _Iterator __last) {
     return __last;
   }
-
 };
 
 _LIBCPP_END_NAMESPACE_STD
 
-#endif // _LIBCPP___ALGORIHTM_ITERATOR_OPERATIONS_H
+#endif // _LIBCPP___ALGORITHM_ITERATOR_OPERATIONS_H

libcxx/include/__algorithm/lower_bound.h

 #include <__algorithm/iterator_operations.h>
 #include <__config>
 #include <__functional/identity.h>
 #include <__functional/invoke.h>
 #include <__iterator/advance.h>
 #include <__iterator/distance.h>
 #include <__iterator/iterator_traits.h>
 #include <__type_traits/is_callable.h>
+#include <__type_traits/remove_reference.h>
 #include <type_traits>
 
 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
 #  pragma GCC system_header
 #endif
 
 _LIBCPP_BEGIN_NAMESPACE_STD
 
-template <class _IterOps, class _Iter, class _Sent, class _Type, class _Proj, class _Comp>
+template <class _AlgPolicy, class _Iter, class _Sent, class _Type, class _Proj, class _Comp>
 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX17
 _Iter __lower_bound_impl(_Iter __first, _Sent __last, const _Type& __value, _Comp& __comp, _Proj& __proj) {
-  auto __len = _IterOps::distance(__first, __last);
+  auto __len = _IterOps<_AlgPolicy>::distance(__first, __last);
 
   while (__len != 0) {
     auto __l2 = std::__half_positive(__len);
     _Iter __m = __first;
-    _IterOps::advance(__m, __l2);
+    _IterOps<_AlgPolicy>::advance(__m, __l2);
     if (std::__invoke(__comp, std::__invoke(__proj, *__m), __value)) {
       __first = ++__m;
       __len -= __l2 + 1;
     } else {
       __len = __l2;
     }
   }
   return __first;
 }
 
 template <class _ForwardIterator, class _Tp, class _Compare>
 _LIBCPP_NODISCARD_EXT inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX17
 _ForwardIterator lower_bound(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value, _Compare __comp) {
   static_assert(__is_callable<_Compare, decltype(*__first), const _Tp&>::value,
                 "The comparator has to be callable");
   auto __proj = std::__identity();
-  return std::__lower_bound_impl<_StdIterOps>(__first, __last, __value, __comp, __proj);
+  return std::__lower_bound_impl<_ClassicAlgPolicy>(__first, __last, __value, __comp, __proj);
 }
 
 template <class _ForwardIterator, class _Tp>
 _LIBCPP_NODISCARD_EXT inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX17
 _ForwardIterator lower_bound(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value) {
   return std::lower_bound(__first, __last, __value,
                           __less<typename iterator_traits<_ForwardIterator>::value_type, _Tp>());
 }
 
 _LIBCPP_END_NAMESPACE_STD
 
 #endif // _LIBCPP___ALGORITHM_LOWER_BOUND_H

libcxx/include/__algorithm/ranges_binary_search.h

 
 namespace ranges {
 namespace __binary_search {
 struct __fn {
   template <forward_iterator _Iter, sentinel_for<_Iter> _Sent, class _Type, class _Proj = identity,
             indirect_strict_weak_order<const _Type*, projected<_Iter, _Proj>> _Comp = ranges::less>
   _LIBCPP_HIDE_FROM_ABI constexpr
   bool operator()(_Iter __first, _Sent __last, const _Type& __value, _Comp __comp = {}, _Proj __proj = {}) const {
-    auto __ret = std::__lower_bound_impl<_RangesIterOps>(__first, __last, __value, __comp, __proj);
+    auto __ret = std::__lower_bound_impl<_RangeAlgPolicy>(__first, __last, __value, __comp, __proj);
     return __ret != __last && !std::invoke(__comp, __value, std::invoke(__proj, *__first));
   }
 
   template <forward_range _Range, class _Type, class _Proj = identity,
             indirect_strict_weak_order<const _Type*, projected<iterator_t<_Range>, _Proj>> _Comp = ranges::less>
   _LIBCPP_HIDE_FROM_ABI constexpr
   bool operator()(_Range&& __r, const _Type& __value, _Comp __comp = {}, _Proj __proj = {}) const {
     auto __first = ranges::begin(__r);
     auto __last = ranges::end(__r);
-    auto __ret = std::__lower_bound_impl<_RangesIterOps>(__first, __last, __value, __comp, __proj);
+    auto __ret = std::__lower_bound_impl<_RangeAlgPolicy>(__first, __last, __value, __comp, __proj);
     return __ret != __last && !std::invoke(__comp, __value, std::invoke(__proj, *__first));
   }
 };
 } // namespace __binary_search
 
 inline namespace __cpo {
   inline constexpr auto binary_search = __binary_search::__fn{};
 } // namespace __cpo
 } // namespace ranges
 
 _LIBCPP_END_NAMESPACE_STD
 
 #endif // _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES)
 
 #endif // _LIBCPP___ALGORITHM_RANGES_BINARY_SEARCH_H

libcxx/include/__algorithm/ranges_lower_bound.h

 namespace ranges {
 
 namespace __lower_bound {
 struct __fn {
   template <forward_iterator _Iter, sentinel_for<_Iter> _Sent, class _Type, class _Proj = identity,
             indirect_strict_weak_order<const _Type*, projected<_Iter, _Proj>> _Comp = ranges::less>
   _LIBCPP_HIDE_FROM_ABI constexpr
   _Iter operator()(_Iter __first, _Sent __last, const _Type& __value, _Comp __comp = {}, _Proj __proj = {}) const {
-    return std::__lower_bound_impl<_RangesIterOps>(__first, __last, __value, __comp, __proj);
+    return std::__lower_bound_impl<_RangeAlgPolicy>(__first, __last, __value, __comp, __proj);
   }
 
   template <forward_range _Range, class _Type, class _Proj = identity,
             indirect_strict_weak_order<const _Type*, projected<iterator_t<_Range>, _Proj>> _Comp = ranges::less>
   _LIBCPP_HIDE_FROM_ABI constexpr
   borrowed_iterator_t<_Range> operator()(_Range&& __r,
                                          const _Type& __value,
                                          _Comp __comp = {},
                                          _Proj __proj = {}) const {
-    return std::__lower_bound_impl<_RangesIterOps>(ranges::begin(__r), ranges::end(__r), __value, __comp, __proj);
+    return std::__lower_bound_impl<_RangeAlgPolicy>(ranges::begin(__r), ranges::end(__r), __value, __comp, __proj);
   }
 };
 } // namespace __lower_bound
 
 inline namespace __cpo {
   inline constexpr auto lower_bound = __lower_bound::__fn{};
 } // namespace __cpo
 } // namespace ranges
 
 _LIBCPP_END_NAMESPACE_STD
 
 #endif // _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES)
 
 #endif // _LIBCPP___ALGORITHM_RANGES_LOWER_BOUND_H

libcxx/include/__algorithm/ranges_set_intersection.h

_LIBCPP_HIDE_FROM_ABI constexpr set_intersection_result<_InIter1, _InIter2, _OutIter> operator()(
       _InIter1 __first1,
       _Sent1 __last1,
       _InIter2 __first2,
       _Sent2 __last2,
       _OutIter __result,
       _Comp __comp   = {},
       _Proj1 __proj1 = {},
       _Proj2 __proj2 = {}) const {
-    auto __ret = std::__set_intersection<_RangesIterOps>(
+    auto __ret = std::__set_intersection<_RangeAlgPolicy>(
         std::move(__first1),
         std::move(__last1),
         std::move(__first2),
         std::move(__last2),
         std::move(__result),
         ranges::__make_projected_comp(__comp, __proj1, __proj2));
     return {std::move(__ret.in1), std::move(__ret.in2), std::move(__ret.out)};
   }
_LIBCPP_HIDE_FROM_ABI constexpr set_intersection_result<borrowed_iterator_t<_Range1>,
                                                             _OutIter>
     operator()(
         _Range1&& __range1,
         _Range2&& __range2,
         _OutIter __result,
         _Comp __comp   = {},
         _Proj1 __proj1 = {},
         _Proj2 __proj2 = {}) const {
-    auto __ret = std::__set_intersection<_RangesIterOps>(
+    auto __ret = std::__set_intersection<_RangeAlgPolicy>(
         ranges::begin(__range1),
         ranges::end(__range1),
         ranges::begin(__range2),
         ranges::end(__range2),
         std::move(__result),
         ranges::__make_projected_comp(__comp, __proj1, __proj2));
     return {std::move(__ret.in1), std::move(__ret.in2), std::move(__ret.out)};
   }

libcxx/include/__algorithm/ranges_upper_bound.h

struct __fn {
   template <forward_iterator _Iter, sentinel_for<_Iter> _Sent, class _Type, class _Proj = identity,
             indirect_strict_weak_order<const _Type*, projected<_Iter, _Proj>> _Comp = ranges::less>
   _LIBCPP_HIDE_FROM_ABI constexpr
   _Iter operator()(_Iter __first, _Sent __last, const _Type& __value, _Comp __comp = {}, _Proj __proj = {}) const {
     auto __comp_lhs_rhs_swapped = [&](const auto& __lhs, const auto& __rhs) {
       return !std::invoke(__comp, __rhs, __lhs);
     };
 
-    return std::__lower_bound_impl<_RangesIterOps>(__first, __last, __value, __comp_lhs_rhs_swapped, __proj);
+    return std::__lower_bound_impl<_RangeAlgPolicy>(__first, __last, __value, __comp_lhs_rhs_swapped, __proj);
   }
 
   template <forward_range _Range, class _Type, class _Proj = identity,
             indirect_strict_weak_order<const _Type*, projected<iterator_t<_Range>, _Proj>> _Comp = ranges::less>
   _LIBCPP_HIDE_FROM_ABI constexpr
   borrowed_iterator_t<_Range> operator()(_Range&& __r,
                                          const _Type& __value,
                                          _Comp __comp = {},
                                          _Proj __proj = {}) const {
     auto __comp_lhs_rhs_swapped = [&](const auto& __lhs, const auto& __rhs) {
       return !std::invoke(__comp, __rhs, __lhs);
     };
 
-    return std::__lower_bound_impl<_RangesIterOps>(ranges::begin(__r),
+    return std::__lower_bound_impl<_RangeAlgPolicy>(ranges::begin(__r),
                                                    ranges::end(__r),
                                                    __value,
                                                    __comp_lhs_rhs_swapped,
                                                    __proj);
   }
 };
 } // namespace __upper_bound
 

libcxx/include/__algorithm/set_intersection.h

struct __set_intersection_result {
   _OutIter out;
 
   // need a constructor as C++03 aggregate init is hard
   _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX17
   __set_intersection_result(_InIter1&& __in_iter1, _InIter2&& __in_iter2, _OutIter&& __out_iter)
       : in1(std::move(__in_iter1)), in2(std::move(__in_iter2)), out(std::move(__out_iter)) {}
 };
 
-template < class _IterOper, class _Compare, class _InIter1, class _Sent1, class _InIter2, class _Sent2, class _OutIter>
+template <class _AlgPolicy, class _Compare, class _InIter1, class _Sent1, class _InIter2, class _Sent2, class _OutIter>
 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX17 __set_intersection_result<_InIter1, _InIter2, _OutIter>
 __set_intersection(
     _InIter1 __first1, _Sent1 __last1, _InIter2 __first2, _Sent2 __last2, _OutIter __result, _Compare&& __comp) {
   while (__first1 != __last1 && __first2 != __last2) {
     if (__comp(*__first1, *__first2))
       ++__first1;
     else {
       if (!__comp(*__first2, *__first1)) {
         *__result = *__first1;
         ++__result;
         ++__first1;
       }
       ++__first2;
     }
   }
 
   return __set_intersection_result<_InIter1, _InIter2, _OutIter>(
-      _IterOper::next(std::move(__first1), std::move(__last1)),
-      _IterOper::next(std::move(__first2), std::move(__last2)),
+      _IterOps<_AlgPolicy>::next(std::move(__first1), std::move(__last1)),
+      _IterOps<_AlgPolicy>::next(std::move(__first2), std::move(__last2)),
       std::move(__result));
 }
 
 template <class _InputIterator1, class _InputIterator2, class _OutputIterator, class _Compare>
 inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX17 _OutputIterator set_intersection(
     _InputIterator1 __first1,
     _InputIterator1 __last1,
     _InputIterator2 __first2,
     _InputIterator2 __last2,
     _OutputIterator __result,
     _Compare __comp) {
   typedef typename __comp_ref_type<_Compare>::type _Comp_ref;
-  return std::__set_intersection<_StdIterOps, _Comp_ref>(
+  return std::__set_intersection<_ClassicAlgPolicy, _Comp_ref>(
              std::move(__first1),
              std::move(__last1),
              std::move(__first2),
              std::move(__last2),
              std::move(__result),
              __comp)
       .out;
 }
 
 template <class _InputIterator1, class _InputIterator2, class _OutputIterator>
 inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX17 _OutputIterator set_intersection(
     _InputIterator1 __first1,
     _InputIterator1 __last1,
     _InputIterator2 __first2,
     _InputIterator2 __last2,
     _OutputIterator __result) {
-  return std::__set_intersection<_StdIterOps>(
+  return std::__set_intersection<_ClassicAlgPolicy>(
              std::move(__first1),
              std::move(__last1),
              std::move(__first2),
              std::move(__last2),
              std::move(__result),
              __less<typename iterator_traits<_InputIterator1>::value_type,
                     typename iterator_traits<_InputIterator2>::value_type>())
       .out;
 }
 
 _LIBCPP_END_NAMESPACE_STD
 
 #endif // _LIBCPP___ALGORITHM_SET_INTERSECTION_H