[libc++][ranges] Make sure all range algorithms support differing projection types:

[var-const]

Summary

• for all algorithms taking more than one range, add a robust test to check the case where the ranges have different value types and the given projections are different, with each projection applying to a different value type;
• fix ranges::include to apply the correct projection to each range.

[var-const]

Make sure the classic include doesn't change behavior.

[huixie90]

The fix looks good to me and I think we should delete the overload __make_projected_comp(__comp, __proj1, __proj2) and replace all the usages with hand coded std::invoke

[var-const]

Fix the CI and rebase.

[huixie90]

This is a definitely needed fix. Whether or not to fix set_* algorithms in the same patch should not block this patch.

[var-const]

The CI failure is unrelated.

[var-const]

In D130515#3678127, @huixie90 wrote:

The fix looks good to me and I think we should delete the overload __make_projected_comp(__comp, __proj1, __proj2) and replace all the usages with hand coded std::invoke

Without this test, I'd agree. With the test, however, I think the benefits outweigh the drawbacks. If an algorithm switches the comparison order, this test will break. However, make_projected_comp not only reduces on boilerplate and keeps most internal algorithms unaware of projections, it also allows passing in the original comparator without modification and "eliding" identity when possible.

[huixie90]

In D130515#3681039, @var-const wrote:

In D130515#3678127, @huixie90 wrote:

The fix looks good to me and I think we should delete the overload __make_projected_comp(__comp, __proj1, __proj2) and replace all the usages with hand coded std::invoke

Without this test, I'd agree. With the test, however, I think the benefits outweigh the drawbacks. If an algorithm switches the comparison order, this test will break. However, make_projected_comp not only reduces on boilerplate and keeps most internal algorithms unaware of projections, it also allows passing in the original comparator without modification and "eliding" identity when possible.

Yes I do agree in general it keeps things tidy. I only have concerns with this particular overload that takes two projections. The problem is that the algorithm's concept constrained the __comp to be able to call __comp(*in1, *in1), __comp(*in1, *in2), __comp(*in2, *in1), __comp(*in2, *in2).
For example, https://en.cppreference.com/w/cpp/iterator/mergeable which calls https://en.cppreference.com/w/cpp/concepts/relation

But this particular overload assumes it always calls __comp(*in1, *in2). By having this overload available, in the future it could break things if we add new algorithms or even just use it internally

[var-const]

In D130515#3681057, @huixie90 wrote:

In D130515#3681039, @var-const wrote:

In D130515#3678127, @huixie90 wrote:

The fix looks good to me and I think we should delete the overload __make_projected_comp(__comp, __proj1, __proj2) and replace all the usages with hand coded std::invoke

Without this test, I'd agree. With the test, however, I think the benefits outweigh the drawbacks. If an algorithm switches the comparison order, this test will break. However, make_projected_comp not only reduces on boilerplate and keeps most internal algorithms unaware of projections, it also allows passing in the original comparator without modification and "eliding" identity when possible.

Yes I do agree in general it keeps things tidy. I only have concerns with this particular overload that takes two projections. The problem is that the algorithm's concept constrained the __comp to be able to call __comp(*in1, *in1), __comp(*in1, *in2), __comp(*in2, *in1), __comp(*in2, *in2).
For example, https://en.cppreference.com/w/cpp/iterator/mergeable which calls https://en.cppreference.com/w/cpp/concepts/relation

But this particular overload assumes it always calls __comp(*in1, *in2). By having this overload available, in the future it could break things if we add new algorithms or even just use it internally

Yes, but then the new test from this patch would break, right? I guess if we add a new algorithm, then we have to remember to update this test if appropriate, which is a downside. I still think that if we can verify that the projected comparator is only used with the non-reversed order of arguments, it's better to use it.

If you can think of a case where we could use the projected comparator incorrectly and this test would *not* break, let me know -- that would be pretty bad.

libcxx/include/__algorithm/includes.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___ALGORITHM_INCLUDES_H
 #define _LIBCPP___ALGORITHM_INCLUDES_H
 
 #include <__algorithm/comp.h>
 #include <__algorithm/comp_ref_type.h>
 #include <__config>
+#include <__functional/identity.h>
+#include <__functional/invoke.h>
 #include <__iterator/iterator_traits.h>
+#include <__type_traits/is_callable.h>
 #include <__utility/move.h>
 
 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
 #  pragma GCC system_header
 #endif
 
 _LIBCPP_BEGIN_NAMESPACE_STD
 
-template <class _Iter1, class _Sent1, class _Iter2, class _Sent2, class _Comp>
+template <class _Iter1, class _Sent1, class _Iter2, class _Sent2, class _Comp, class _Proj1, class _Proj2>
 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX17 bool
-__includes(_Iter1 __first1, _Sent1 __last1, _Iter2 __first2, _Sent2 __last2, _Comp&& __comp) {
+__includes(_Iter1 __first1, _Sent1 __last1, _Iter2 __first2, _Sent2 __last2,
+           _Comp&& __comp, _Proj1&& __proj1, _Proj2&& __proj2) {
   for (; __first2 != __last2; ++__first1) {
-    if (__first1 == __last1 || __comp(*__first2, *__first1))
+    if (__first1 == __last1 || std::__invoke(
+          __comp, std::__invoke(__proj2, *__first2), std::__invoke(__proj1, *__first1)))
       return false;
-    if (!__comp(*__first1, *__first2))
+    if (!std::__invoke(__comp, std::__invoke(__proj1, *__first1), std::__invoke(__proj2, *__first2)))
       ++__first2;
   }
   return true;
 }
 
 template <class _InputIterator1, class _InputIterator2, class _Compare>
 _LIBCPP_NODISCARD_EXT inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX17 bool includes(
     _InputIterator1 __first1,
     _InputIterator1 __last1,
     _InputIterator2 __first2,
     _InputIterator2 __last2,
     _Compare __comp) {
+  static_assert(__is_callable<_Compare, decltype(*__first1), decltype(*__first2)>::value,
+      "Comparator has to be callable");
+
   typedef typename __comp_ref_type<_Compare>::type _Comp_ref;
   return std::__includes(
-      std::move(__first1), std::move(__last1), std::move(__first2), std::move(__last2), static_cast<_Comp_ref>(__comp));
+      std::move(__first1), std::move(__last1), std::move(__first2), std::move(__last2),
+      static_cast<_Comp_ref>(__comp), __identity(), __identity());
 }
 
 template <class _InputIterator1, class _InputIterator2>
 _LIBCPP_NODISCARD_EXT inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX17 bool
 includes(_InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2, _InputIterator2 __last2) {
   return std::includes(
       std::move(__first1),
       std::move(__last1),

libcxx/include/__algorithm/ranges_includes.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
 //
 //===----------------------------------------------------------------------===//
 
_LIBCPP_HIDE_FROM_ABI constexpr bool operator()(
       _Comp __comp   = {},
       _Proj1 __proj1 = {},
       _Proj2 __proj2 = {}) const {
     return std::__includes(
         std::move(__first1),
         std::move(__last1),
         std::move(__first2),
         std::move(__last2),
-        ranges::__make_projected_comp(__comp, __proj1, __proj2));
+        std::move(__comp),
+        std::move(__proj1),
+        std::move(__proj2));
   }
 
   template <
       input_range _Range1,
       input_range _Range2,
       class _Proj1 = identity,
       class _Proj2 = identity,
       indirect_strict_weak_order<projected<iterator_t<_Range1>, _Proj1>, projected<iterator_t<_Range2>, _Proj2>>
           _Comp = ranges::less>
   _LIBCPP_HIDE_FROM_ABI constexpr bool operator()(
       _Range1&& __range1, _Range2&& __range2, _Comp __comp = {}, _Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const {
     return std::__includes(
         ranges::begin(__range1),
         ranges::end(__range1),
         ranges::begin(__range2),
         ranges::end(__range2),
-        ranges::__make_projected_comp(__comp, __proj1, __proj2));
+        std::move(__comp),
+        std::move(__proj1),
+        std::move(__proj2));
   }
 };
 
 } // namespace __includes
 
 inline namespace __cpo {
   inline constexpr auto includes = __includes::__fn{};
 } // namespace __cpo
 } // namespace ranges
 
 _LIBCPP_END_NAMESPACE_STD
 
 #endif // _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES)
 
 #endif // _LIBCPP___ALGORITHM_RANGES_INCLUDES_H

libcxx/test/std/algorithms/ranges_robust_against_differing_projections.pass.cpp

+//===----------------------------------------------------------------------===//
+//
+// 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
+//
+//===----------------------------------------------------------------------===//
+
+// UNSUPPORTED: c++03, c++11, c++14, c++17
+// UNSUPPORTED: libcpp-has-no-incomplete-ranges
+
+// <algorithm>
+//
+// Range algorithms should support the case where the ranges they operate on have different value types and the given
+// projection functors are different (each projection applies to a different value type).
+
+#include <algorithm>
+
+#include <array>
+#include <functional>
+#include <iterator>
+#include <ranges>
+#include <utility>
+
+// (in1, in2, ...)
+template <class Func, std::ranges::range Input1, std::ranges::range Input2, class ...Args>
+constexpr void test(Func&& func, Input1& in1, Input2& in2, Args&& ...args) {
+  func(in1.begin(), in1.end(), in2.begin(), in2.end(), std::forward<Args>(args)...);
+  func(in1, in2, std::forward<Args>(args)...);
+}
+
+constexpr bool test_all() {
+  struct A {
+    int x = 0;
+
+    constexpr A() = default;
+    constexpr A(int value) : x(value) {}
+    constexpr operator int() const { return x; }
+
+    constexpr auto operator<=>(const A&) const = default;
+  };
+
+  std::array in = {1, 2, 3};
+  std::array in2 = {A{4}, A{5}, A{6}};
+
+  std::array output = {7, 8, 9, 10, 11, 12};
+  auto out = output.begin();
+  std::array output2 = {A{7}, A{8}, A{9}, A{10}, A{11}, A{12}};
+  auto out2 = output2.begin();
+
+  std::ranges::equal_to eq;
+  std::ranges::less less;
+  auto sum = [](int lhs, A rhs) { return lhs + rhs.x; };
+  auto proj1 = [](int x) { return x * -1; };
+  auto proj2 = [](A a) { return a.x * -1; };
+
+  test(std::ranges::equal, in, in2, eq, proj1, proj2);
+  test(std::ranges::lexicographical_compare, in, in2, eq, proj1, proj2);
+  //test(std::ranges::is_permutation, in, in2, eq, proj1, proj2);
+  test(std::ranges::includes, in, in2, less, proj1, proj2);
+  test(std::ranges::find_first_of, in, in2, eq, proj1, proj2);
+  test(std::ranges::mismatch, in, in2, eq, proj1, proj2);
+  test(std::ranges::search, in, in2, eq, proj1, proj2);
+  test(std::ranges::find_end, in, in2, eq, proj1, proj2);
+  test(std::ranges::transform, in, in2, out, sum, proj1, proj2);
+  test(std::ranges::transform, in, in2, out2, sum, proj1, proj2);
+  //test(std::ranges::partial_sort_copy, in, in2, output2.begin(), output2.end(), less, proj1, proj2);
+  test(std::ranges::merge, in, in2, out, less, proj1, proj2);
+  test(std::ranges::merge, in, in2, out2, less, proj1, proj2);
+  test(std::ranges::set_intersection, in, in2, out, less, proj1, proj2);
+  test(std::ranges::set_intersection, in, in2, out2, less, proj1, proj2);
+  test(std::ranges::set_difference, in, in2, out, less, proj1, proj2);
+  test(std::ranges::set_difference, in, in2, out2, less, proj1, proj2);
+  test(std::ranges::set_symmetric_difference, in, in2, out, less, proj1, proj2);
+  test(std::ranges::set_symmetric_difference, in, in2, out2, less, proj1, proj2);
+  test(std::ranges::set_union, in, in2, out, less, proj1, proj2);
+  test(std::ranges::set_union, in, in2, out2, less, proj1, proj2);
+
+  return true;
+}
+
+int main(int, char**) {
+  test_all();
+  static_assert(test_all());
+
+  return 0;
+}