[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

67

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

67

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

67

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

75

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

30

_AlgPolicy?

51

There shouldn't be any underscores here.

libcxx/include/__algorithm/set_intersection.h

37 ↗

(On Diff #443886)

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

[huixie90]

libcxx/include/__algorithm/iterator_operations.h

38

question. why double underscores here?

75

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

38

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

75

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

38

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

 //===----------------------------------------------------------------------===//
 //
 // 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
 //
 //===----------------------------------------------------------------------===//
 
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<_STLClassicAlgorithms>(__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>
 
 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
 #  pragma GCC system_header
 #endif
 
 _LIBCPP_BEGIN_NAMESPACE_STD
 
+template <class _Tag> struct _IterOps;
+
 #if _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES)
-struct _RangesIterOps {
+struct _RangesAlgorithms {};
+
+template <>
+struct _IterOps<_RangesAlgorithms> {
   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 _STLClassicAlgorithms {};
 
-  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);
+template <>
+struct _IterOps<_STLClassicAlgorithms> {
+
+  // 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<typename remove_reference<_Iter>::type>::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 _Iter>
+  _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX11
+  static _Iter next(const _Iter&, const _Iter& __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

 //===----------------------------------------------------------------------===//
 //
 // 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
 //
 //===----------------------------------------------------------------------===//
 

 #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 _AlgFamily, 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<_AlgFamily>::distance(__first, __last);
 
   while (__len != 0) {
     auto __l2 = std::__half_positive(__len);
     _Iter __m = __first;
-    _IterOps::advance(__m, __l2);
+    _IterOps<_AlgFamily>::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) {
+_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<_STLClassicAlgorithms>(__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,
+_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

 //===----------------------------------------------------------------------===//
 //
 // 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
 //
 //===----------------------------------------------------------------------===//
 

 
 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<_RangesAlgorithms>(__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<_RangesAlgorithms>(__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

 //===----------------------------------------------------------------------===//
 //
 // 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
 //
 //===----------------------------------------------------------------------===//
 

 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<_RangesAlgorithms>(__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<_RangesAlgorithms>(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_upper_bound.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
 //
 //===----------------------------------------------------------------------===//
 
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<_RangesAlgorithms>(__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<_RangesAlgorithms>(ranges::begin(__r),
                                                    ranges::end(__r),
                                                    __value,
                                                    __comp_lhs_rhs_swapped,
                                                    __proj);
   }
 };
 } // namespace __upper_bound