[libc++][ranges] implement `std::ranges::set_intersection`

[huixie90]

Summary

implement std::ranges::set_intersection by reusing the classic std::set_intersection
added unit tests

[huixie90]

update review link

[huixie90]

added newline at the end of the file

[var-const]

libcxx/docs/Status/RangesAlgorithms.csv

57

Nit: s/set_intersenction/set_intersection/ in the patch description.

libcxx/include/__algorithm/set_intersection.h

32

I'd suggest defining a simple struct to hold the return values instead. It would be more readable than a tuple (the meaning of e.g. ret.first1 is a lot more obvious than std::get<0>(ret)) and would avoid the need for the conditional macros.

67

Instead of returning __first1 and __first2 and putting the responsibility to convert sentinels to iterators on the caller, I'd suggest calling next here and returning only __first1 (advanced to the last position), __first2 (same) and __result. I think iterator_operations.h would be a good place to hide the difference between std::next and std::ranges::next.

[var-const]

libcxx/test/std/algorithms/alg.sorting/alg.set.operations/set.intersection/ranges_set_intersection.pass.cpp

230

This class should probably also be moved to the utility header.

274

Unused?

586

You probably need to make this function return bool and add a static assertion here, similar to how test is invoked twice above. If there's a reason not to, please add it as a comment.

[huixie90]

libcxx/include/__algorithm/set_intersection.h

32

That was my first attempt. it turns out that in c++03 , initialising an aggregate is so hard. I can’t just return myStrucr{a,b}; I have to declare a variable and then return it. And by declaring a variable , it might be copied (NRVO is not guaranteed ). So I have to define a proper constructor for it to work for c++03

That is too much effort and I gave up and use tuple

But I still like the idea and struct with named members. what about only use struct for c++11 onward and for 03 just guard with macro

67

I did consider that. But for claasic algorithm, there is no need to call next since the iterators are discarded. std::next can be a linear complexity operation and it is wasteful to compute it when the result is not needed at all.

That is why I used this approach so that only ranges overload computes the next

What do you think?

[var-const]

libcxx/include/__algorithm/set_intersection.h

32

I'd prefer to have a three-element constructor -- it is a bit of boilerplate, but I think it's vastly preferable over the downsides of using a tuple.

67

I'd avoid using macros if at all possible. I think you could achieve a similar result by passing a template type as a tag to distinguish whether the function is invoked by the classic algorithm or the ranges algorithm (the return type would be decltype(auto) and the function could use if constexpr to return different types).

However, I think it's more trouble than it's worth. For the classic algorithm, the compiler should be able to optimize away the unused variables and their computation. In cases like this, IMO a simpler and more obviously correct implementation is higher priority than the minor performance difference (which should be optimized away in any optimized build).

[huixie90]

addressing feedback

libcxx/include/__algorithm/set_intersection.h

32

I used a slightly different approach now. It is combined with the other suggestion of using a "Tag" type. The "Tag" type specify what the return type should be.
So with that, I can avoid using tuple or any temporary struct at all. The "ClassicOperation" can specify the return type is just the iterator and the "RangeOperation" specifies that the return type is the set_intersection_result directly, without the need of creating any intermediate data type.

67

The macro is removed. and now the algorithm take the additional "tag" type. but with slightly different approach. the tag type dictates how to make the result. so the "classic tag" simply returns the output iterator and the "ranges tag" creates the set_intersection_result.

The benefit is to avoid writing intermediate struct (or avoid using tuple which isn't very readable). also it avoids writing the code that converts the intermediate result (temporary struct or tuple) to the final set_intersection_result

What do you think?

libcxx/test/std/algorithms/alg.sorting/alg.set.operations/set.intersection/ranges_set_intersection.pass.cpp

274

it is used. see the function body of runAllIteratorPermutationsTests contains static_assert

586

Unfortunately that does not work because it exceeds the constexpr execution step limit, due to the large number of combination of types of iterators (it is a 3-dimentional cartesian product)

The workaround here is instead of having one single static_assert that tests all the combinations, in the runAllIteratorPermutationsTests function, it has lots of smaller static_assert and each of them test 2-dimentional cartesian product which is less than the step limit.
And this explains the other comment you have, where I have return true in the second layer test function.

[huixie90]

rebase

[var-const]

libcxx/include/__algorithm/set_intersection.h

67

I definitely prefer this to the previous state, but I still think it's a minor optimization that isn't worth its cost in extra complexity. If these extra copies ever come up as a performance issue, we can always do the optimization later. I don't see a strong reason to avoid writing an intermediate struct -- it seems like it should be just ~6 lines of very straightforward boilerplate, mostly confined to a single internal header (but perhaps I'm missing something?).

libcxx/test/std/algorithms/alg.sorting/alg.set.operations/set.intersection/ranges_set_intersection.pass.cpp

586

Thanks for explaining! Please add this rationale as a comment here.

[huixie90]

address feedback

[var-const]

Thanks for addressing the feedback!

libcxx/include/__algorithm/set_intersection.h

80

Nit: move the iterators?

[huixie90]

fix CI

[gulfem]

We started seeing a test failure in libcxx/clang_tidy.sh.cpp after this patch:

FAIL: llvm-libc++-static.cfg.in :: libcxx/clang_tidy.sh.cpp (6983 of 12107)
******************** TEST 'llvm-libc++-static.cfg.in :: libcxx/clang_tidy.sh.cpp' FAILED ********************
Script:
--
: 'RUN: at line 12';   clang-tidy /b/s/w/ir/x/w/llvm-llvm-project/libcxx/test/libcxx/clang_tidy.sh.cpp --warnings-as-errors=* -header-filter=.* -- -Wweak-vtables -Wno-unknown-warning-option -nostdinc++ -I /b/s/w/ir/x/w/staging/llvm_build/include/c++/v1 -I /b/s/w/ir/x/w/staging/llvm_build/include/x86_64-unknown-linux-gnu/c++/v1 -I /b/s/w/ir/x/w/llvm-llvm-project/libcxx/test/support -std=c++2b -Werror -Wall -Wextra -Wshadow -Wundef -Wno-unused-command-line-argument -Wno-attributes -Wno-pessimizing-move -Wno-c++11-extensions -Wno-noexcept-type -Wno-atomic-alignment -Wno-user-defined-literals -Wno-tautological-compare -Wsign-compare -Wunused-variable -Wunused-parameter -Wunreachable-code -Wno-unused-local-typedef -D_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER -D_LIBCPP_ENABLE_EXPERIMENTAL -D_LIBCPP_DISABLE_AVAILABILITY -fcoroutines-ts -Werror=thread-safety -Wuser-defined-warnings  -fno-modules
--
Exit Code: 1

Command Output (stdout):
--
$ ":" "RUN: at line 12"
$ "clang-tidy" "/b/s/w/ir/x/w/llvm-llvm-project/libcxx/test/libcxx/clang_tidy.sh.cpp" "--warnings-as-errors=*" "-header-filter=.*" "--" "-Wweak-vtables" "-Wno-unknown-warning-option" "-nostdinc++" "-I" "/b/s/w/ir/x/w/staging/llvm_build/include/c++/v1" "-I" "/b/s/w/ir/x/w/staging/llvm_build/include/x86_64-unknown-linux-gnu/c++/v1" "-I" "/b/s/w/ir/x/w/llvm-llvm-project/libcxx/test/support" "-std=c++2b" "-Werror" "-Wall" "-Wextra" "-Wshadow" "-Wundef" "-Wno-unused-command-line-argument" "-Wno-attributes" "-Wno-pessimizing-move" "-Wno-c++11-extensions" "-Wno-noexcept-type" "-Wno-atomic-alignment" "-Wno-user-defined-literals" "-Wno-tautological-compare" "-Wsign-compare" "-Wunused-variable" "-Wunused-parameter" "-Wunreachable-code" "-Wno-unused-local-typedef" "-D_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER" "-D_LIBCPP_ENABLE_EXPERIMENTAL" "-D_LIBCPP_DISABLE_AVAILABILITY" "-fcoroutines-ts" "-Werror=thread-safety" "-Wuser-defined-warnings" "-fno-modules"
# command output:
/b/s/w/ir/x/w/staging/llvm_build/include/c++/v1/__algorithm/set_intersection.h:33:40: error: invalid case style for parameter '__inIter1' [readability-identifier-naming,-warnings-as-errors]
  __set_intersection_result(_InIter1&& __inIter1, _InIter2&& __inIter2, _OutIter&& __outIter)
                                       ^~~~~~~~~
                                       __in_iter1
/b/s/w/ir/x/w/staging/llvm_build/include/c++/v1/__algorithm/set_intersection.h:33:62: error: invalid case style for parameter '__inIter2' [readability-identifier-naming,-warnings-as-errors]
  __set_intersection_result(_InIter1&& __inIter1, _InIter2&& __inIter2, _OutIter&& __outIter)
                                                             ^~~~~~~~~
                                                             __in_iter2
/b/s/w/ir/x/w/staging/llvm_build/include/c++/v1/__algorithm/set_intersection.h:33:84: error: invalid case style for parameter '__outIter' [readability-identifier-naming,-warnings-as-errors]
  __set_intersection_result(_InIter1&& __inIter1, _InIter2&& __inIter2, _OutIter&& __outIter)
                                                                                   ^~~~~~~~~
                                                                                   __out_iter

https://luci-milo.appspot.com/ui/p/fuchsia/builders/toolchain.ci/clang-linux-x64/b8808958512552378161/overview

[Mordante]

Thanks for the report. D129503 is tested in the CI and should fix your build failure.

[gulfem]

In D129233#3643110, @Mordante wrote:

Thanks for the report. D129503 is tested in the CI and should fix your build failure.

Thanks @Mordante, D129503 fixed the build issue that we were seeing about variable names.

libcxx/docs/Status/RangesAlgorithms.csv

 Write,generate_n,Nikolas Klauser,n/a,Not started
 Write,remove_copy,Nikolas Klauser,n/a,Not started
 Write,remove_copy_if,Nikolas Klauser,n/a,Not started
 Write,replace,Nikolas Klauser,`D126283 <https://llvm.org/D126283>`_,✅
 Write,replace_if,Nikolas Klauser,`D126283 <https://llvm.org/D126283>`_,✅
 Write,replace_copy,Nikolas Klauser,n/a,Not started
 Write,replace_copy_if,Nikolas Klauser,n/a,Not started
 Write,swap_ranges,Nikolas Klauser,`D116303 <https://llvm.org/D116303>`_,✅
 Write,reverse_copy,Nikolas Klauser,`D127211 <https://llvm.org/D127211>`_,Under review
 Write,rotate_copy,Nikolas Klauser,`D127211 <https://llvm.org/D127211>`_,Under review
 Write,sample,Not assigned,n/a,Not started
 Write,unique_copy,Not assigned,n/a,Not started
 Write,partition_copy,Not assigned,n/a,Not started
 Write,partial_sort_copy,Not assigned,n/a,Not started
 Merge,merge,Hui Xie,`D128611 <https://llvm.org/D128611>`_,✅
 Merge,set_difference,Hui Xie,n/a,Not started
-Merge,set_intersection,Hui Xie,n/a,Not started
+Merge,set_intersection,Hui Xie,n/a,✅
 Merge,set_symmetric_difference,Hui Xie,n/a,Not started
 Merge,set_union,Not assigned,Hui Xie,Not started
 Permutation,remove,Not assigned,n/a,Not started
 Permutation,remove_if,Not assigned,n/a,Not started
 Permutation,reverse,Nikolas Klauser,`D125752 <https://llvm.org/D125752>`_,✅
 Permutation,rotate,Nikolas Klauser,`D124122 <https://llvm.org/D124122>`_,Under review
 Permutation,shuffle,Not assigned,n/a,Not started
 Permutation,unique,Not assigned,n/a,Not started

libcxx/include/CMakeLists.txt

set(files
   __algorithm/ranges_minmax_element.h
   __algorithm/ranges_mismatch.h
   __algorithm/ranges_move.h
   __algorithm/ranges_move_backward.h
   __algorithm/ranges_none_of.h
   __algorithm/ranges_replace.h
   __algorithm/ranges_replace_if.h
   __algorithm/ranges_reverse.h
+  __algorithm/ranges_set_intersection.h
   __algorithm/ranges_sort.h
   __algorithm/ranges_stable_sort.h
   __algorithm/ranges_swap_ranges.h
   __algorithm/ranges_transform.h
   __algorithm/ranges_upper_bound.h
   __algorithm/remove.h
   __algorithm/remove_copy.h
   __algorithm/remove_copy_if.h

libcxx/include/__algorithm/make_projected.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_MAKE_PROJECTED_H
 #define _LIBCPP___ALGORITHM_MAKE_PROJECTED_H
 
 #include <__concepts/same_as.h>
 #include <__config>
 #include <__functional/identity.h>
 #include <__functional/invoke.h>
+#include <__type_traits/decay.h>
+#include <__type_traits/is_member_pointer.h>
 #include <__utility/forward.h>
 
 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
 #  pragma GCC system_header
 #endif
 
 #if _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES)
 
 _LIBCPP_BEGIN_NAMESPACE_STD
 
 namespace ranges {
 
 template <class _Comp, class _Proj>
 _LIBCPP_HIDE_FROM_ABI constexpr static
 decltype(auto) __make_projected_comp(_Comp& __comp, _Proj& __proj) {
-  if constexpr (same_as<_Proj, identity>) {
+  if constexpr (same_as<decay_t<_Proj>, identity> && !is_member_pointer_v<decay_t<_Comp>>) {
     // Avoid creating the lambda and just use the pristine comparator -- for certain algorithms, this would enable
     // optimizations that rely on the type of the comparator.
     return __comp;
 
   } else {
     return [&](auto&& __lhs, auto&& __rhs) {
       return std::invoke(__comp,
                         std::invoke(__proj, std::forward<decltype(__lhs)>(__lhs)),
                         std::invoke(__proj, std::forward<decltype(__rhs)>(__rhs)));
     };
   }
 }
 
+template <class _Comp, class _Proj1, class _Proj2>
+_LIBCPP_HIDE_FROM_ABI constexpr static
+decltype(auto) __make_projected_comp(_Comp& __comp, _Proj1& __proj1, _Proj2& __proj2) {
+  if constexpr (same_as<decay_t<_Proj1>, identity> && same_as<decay_t<_Proj2>, identity> &&
+                !is_member_pointer_v<decay_t<_Comp>>) {
+    // Avoid creating the lambda and just use the pristine comparator -- for certain algorithms, this would enable
+    // optimizations that rely on the type of the comparator.
+    return __comp;
+
+  } else {
+    return [&](auto&& __lhs, auto&& __rhs) {
+      return std::invoke(__comp,
+                        std::invoke(__proj1, std::forward<decltype(__lhs)>(__lhs)),
+                        std::invoke(__proj2, std::forward<decltype(__rhs)>(__rhs)));
+    };
+  }
+}
+
 } // namespace ranges
 
 _LIBCPP_END_NAMESPACE_STD
 
 #endif // _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES)
 
 #endif // _LIBCPP___ALGORITHM_MAKE_PROJECTED_H

libcxx/include/__algorithm/ranges_set_intersection.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_RANGES_SET_INTERSECTION_H
+#define _LIBCPP___ALGORITHM_RANGES_SET_INTERSECTION_H
+
+#include <__algorithm/in_in_out_result.h>
+#include <__algorithm/make_projected.h>
+#include <__algorithm/set_intersection.h>
+#include <__config>
+#include <__functional/identity.h>
+#include <__functional/invoke.h>
+#include <__functional/ranges_operations.h>
+#include <__iterator/concepts.h>
+#include <__iterator/mergeable.h>
+#include <__iterator/next.h>
+#include <__ranges/access.h>
+#include <__ranges/concepts.h>
+#include <__ranges/dangling.h>
+#include <__type_traits/decay.h>
+#include <__utility/move.h>
+#include <tuple>
+
+#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
+#  pragma GCC system_header
+#endif
+
+#if _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES)
+
+_LIBCPP_BEGIN_NAMESPACE_STD
+
+namespace ranges {
+
+template <class _InIter1, class _InIter2, class _OutIter>
+using set_intersection_result = in_in_out_result<_InIter1, _InIter2, _OutIter>;
+
+namespace __set_intersection {
+
+struct __fn {
+  template <
+      input_iterator _InIter1,
+      sentinel_for<_InIter1> _Sent1,
+      input_iterator _InIter2,
+      sentinel_for<_InIter2> _Sent2,
+      weakly_incrementable _OutIter,
+      class _Comp  = less,
+      class _Proj1 = identity,
+      class _Proj2 = identity>
+    requires mergeable<_InIter1, _InIter2, _OutIter, _Comp, _Proj1, _Proj2>
+  _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(
+        __first1, __last1, __first2, __last2, __result, ranges::__make_projected_comp(__comp, __proj1, __proj2));
+    return {
+        ranges::next(std::move(std::get<0>(__ret)), std::move(std::get<1>(__ret))),
+        ranges::next(std::move(std::get<2>(__ret)), std::move(std::get<3>(__ret))),
+        std::move(std::get<4>(__ret))};
+  }
+
+  template <
+      input_range _Range1,
+      input_range _Range2,
+      weakly_incrementable _OutIter,
+      class _Comp  = less,
+      class _Proj1 = identity,
+      class _Proj2 = identity>
+    requires mergeable<
+        iterator_t<_Range1>,
+        iterator_t<_Range2>,
+        _OutIter,
+        _Comp,
+        _Proj1,
+        _Proj2> 
+  _LIBCPP_HIDE_FROM_ABI constexpr set_intersection_result<borrowed_iterator_t<_Range1>,
+                                                          borrowed_iterator_t<_Range2>,
+                                                          _OutIter>
+    operator()(
+        _Range1&& __range1,
+        _Range2&& __range2,
+        _OutIter __result,
+        _Comp __comp   = {},
+        _Proj1 __proj1 = {},
+        _Proj2 __proj2 = {}) const {
+    auto __ret = std::__set_intersection(
+        ranges::begin(__range1),
+        ranges::end(__range1),
+        ranges::begin(__range2),
+        ranges::end(__range2),
+        __result,
+        ranges::__make_projected_comp(__comp, __proj1, __proj2));
+    return {
+        ranges::next(std::move(std::get<0>(__ret)), std::move(std::get<1>(__ret))),
+        ranges::next(std::move(std::get<2>(__ret)), std::move(std::get<3>(__ret))),
+        std::move(std::get<4>(__ret))};
+  }
+};
+
+} // namespace __set_intersection
+
+inline namespace __cpo {
+  inline constexpr auto set_intersection = __set_intersection::__fn{};
+} // namespace __cpo
+} // namespace ranges
+
+_LIBCPP_END_NAMESPACE_STD
+
+#endif // _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES)
+#endif // _LIBCPP___ALGORITHM_RANGES_SET_INTERSECTION_H

libcxx/include/__algorithm/set_intersection.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_SET_INTERSECTION_H
 #define _LIBCPP___ALGORITHM_SET_INTERSECTION_H
 
 #include <__algorithm/comp.h>
 #include <__algorithm/comp_ref_type.h>
 #include <__config>
 #include <__iterator/iterator_traits.h>
+#include <__utility/move.h>
+#include <tuple>
+#include <type_traits>
 
 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
 #  pragma GCC system_header
 #endif
 
 _LIBCPP_BEGIN_NAMESPACE_STD
 
-template <class _Compare, class _InputIterator1, class _InputIterator2, class _OutputIterator>
-_LIBCPP_CONSTEXPR_AFTER_CXX17 _OutputIterator
-__set_intersection(_InputIterator1 __first1, _InputIterator1 __last1,
-                   _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result, _Compare __comp)
-{
-    while (__first1 != __last1 && __first2 != __last2)
-    {
-        if (__comp(*__first1, *__first2))
-            ++__first1;
-        else
-        {
-            if (!__comp(*__first2, *__first1))
-            {
-                *__result = *__first1;
-                ++__result;
-                ++__first1;
-            }
-            ++__first2;
-        }
-    }
-    return __result;
+template <class _Compare, class _InIter1, class _Sent1, class _InIter2, class _Sent2, class _OutIter>
+_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX17
+// tuple isn't available in C++03
+#if defined(_LIBCPP_CXX03_LANG)
+    _OutIter
+#else
+    tuple< __uncvref_t<_InIter1>,
+           __uncvref_t<_Sent1>,
+           __uncvref_t<_InIter2>,
+           __uncvref_t<_Sent2>,
+           __uncvref_t<_OutIter> >
+#endif
+    __set_intersection(
+        _InIter1&& __first1,
+        _Sent1&& __last1,
+        _InIter2&& __first2,
+        _Sent2&& __last2,
+        _OutIter&& __result,
+        _Compare&& __comp) {
+  while (__first1 != __last1 && __first2 != __last2) {
+    else {
+      if (!__comp(*__first2, *__first1)) {
+
+#if defined(_LIBCPP_CXX03_LANG)
+#else
+  return tuple<
+      __uncvref_t<_InIter1>,
+      __uncvref_t<_Sent1>,
+      __uncvref_t<_InIter2>,
+      __uncvref_t<_Sent2>,
+      __uncvref_t<_OutIter>>{
+      std::move(__first1), std::move(__last1), std::move(__first2), std::move(__last2), std::move(__result)};
+#endif
 }
 
 template <class _InputIterator1, class _InputIterator2, class _OutputIterator, class _Compare>
-inline _LIBCPP_INLINE_VISIBILITY _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 _VSTD::__set_intersection<_Comp_ref>(__first1, __last1, __first2, __last2, __result, __comp);
+inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX17 _OutputIterator set_intersection(
+    _InputIterator1 __first1,
+    _InputIterator1 __last1,
+    _InputIterator2 __first2,
+    _InputIterator2 __last2,
+    _OutputIterator __result,
+    _Compare __comp) {
+  auto __ret = std::__set_intersection<_Comp_ref>(__first1, __last1, __first2, __last2, __result, __comp);
+
+#if defined(_LIBCPP_CXX03_LANG)
+  return __ret;
+#else
+  return std::move(std::get<4>(__ret));
+#endif
 }
 
 template <class _InputIterator1, class _InputIterator2, class _OutputIterator>
-inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
-_OutputIterator
-set_intersection(_InputIterator1 __first1, _InputIterator1 __last1,
-                 _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result)
-{
-    return _VSTD::set_intersection(__first1, __last1, __first2, __last2, __result,
-                                  __less<typename iterator_traits<_InputIterator1>::value_type,
-                                         typename iterator_traits<_InputIterator2>::value_type>());
+inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX17 _OutputIterator set_intersection(
+    _InputIterator1 __first1,
+    _InputIterator1 __last1,
+    _InputIterator2 __first2,
+    _InputIterator2 __last2,
+    _OutputIterator __result) {
+  auto __ret = std::__set_intersection(
+      __first1,
+      __last1,
+      __first2,
+      __last2,
+      __result,
+
+#if defined(_LIBCPP_CXX03_LANG)
+  return __ret;
+#else
+  return std::move(std::get<4>(__ret));
+#endif
 }
 
 _LIBCPP_END_NAMESPACE_STD
 
 #endif // _LIBCPP___ALGORITHM_SET_INTERSECTION_H

libcxx/include/algorithm

template<input_range R1, input_range R2, class Pred = ranges::equal_to,
 
   template<input_range R1, input_range R2, weakly_incrementable O, class Comp = ranges::less,
            class Proj1 = identity, class Proj2 = identity>
     requires mergeable<iterator_t<R1>, iterator_t<R2>, O, Comp, Proj1, Proj2>
     constexpr merge_result<borrowed_iterator_t<R1>, borrowed_iterator_t<R2>, O>
       merge(R1&& r1, R2&& r2, O result,
             Comp comp = {}, Proj1 proj1 = {}, Proj2 proj2 = {});                                    // since C++20
 
+  template<class I1, class I2, class O>
+    using set_intersection_result = in_in_out_result<I1, I2, O>;                                    // since C++20
+
+  template<input_iterator I1, sentinel_for<I1> S1, input_iterator I2, sentinel_for<I2> S2,
+           weakly_incrementable O, class Comp = ranges::less,
+           class Proj1 = identity, class Proj2 = identity>
+    requires mergeable<I1, I2, O, Comp, Proj1, Proj2>
+    constexpr set_intersection_result<I1, I2, O>
+      set_intersection(I1 first1, S1 last1, I2 first2, S2 last2, O result,
+                       Comp comp = {}, Proj1 proj1 = {}, Proj2 proj2 = {});                         // since C++20
+
+  template<input_range R1, input_range R2, weakly_incrementable O,
+           class Comp = ranges::less, class Proj1 = identity, class Proj2 = identity>
+    requires mergeable<iterator_t<R1>, iterator_t<R2>, O, Comp, Proj1, Proj2>
+    constexpr set_intersection_result<borrowed_iterator_t<R1>, borrowed_iterator_t<R2>, O>
+      set_intersection(R1&& r1, R2&& r2, O result,
+                       Comp comp = {}, Proj1 proj1 = {}, Proj2 proj2 = {});                         // since C++20
+
 }
 
     constexpr bool     // constexpr in C++20
     all_of(InputIterator first, InputIterator last, Predicate pred);
 
 template <class InputIterator, class Predicate>
     constexpr bool     // constexpr in C++20
     any_of(InputIterator first, InputIterator last, Predicate pred);

 #include <__algorithm/ranges_minmax_element.h>
 #include <__algorithm/ranges_mismatch.h>
 #include <__algorithm/ranges_move.h>
 #include <__algorithm/ranges_move_backward.h>
 #include <__algorithm/ranges_none_of.h>
 #include <__algorithm/ranges_replace.h>
 #include <__algorithm/ranges_replace_if.h>
 #include <__algorithm/ranges_reverse.h>
+#include <__algorithm/ranges_set_intersection.h>
 #include <__algorithm/ranges_sort.h>
 #include <__algorithm/ranges_stable_sort.h>
 #include <__algorithm/ranges_swap_ranges.h>
 #include <__algorithm/ranges_transform.h>
 #include <__algorithm/ranges_upper_bound.h>
 #include <__algorithm/remove.h>
 #include <__algorithm/remove_copy.h>
 #include <__algorithm/remove_copy_if.h>

libcxx/include/module.modulemap.in

module __algorithm {
       module ranges_minmax_element           { private header "__algorithm/ranges_minmax_element.h" }
       module ranges_mismatch                 { private header "__algorithm/ranges_mismatch.h" }
       module ranges_move                     { private header "__algorithm/ranges_move.h" }
       module ranges_move_backward            { private header "__algorithm/ranges_move_backward.h" }
       module ranges_none_of                  { private header "__algorithm/ranges_none_of.h" }
       module ranges_replace                  { private header "__algorithm/ranges_replace.h" }
       module ranges_replace_if               { private header "__algorithm/ranges_replace_if.h" }
       module ranges_reverse                  { private header "__algorithm/ranges_reverse.h" }
+      module ranges_set_intersection         { private header "__algorithm/ranges_set_intersection.h" }
       module ranges_sort                     { private header "__algorithm/ranges_sort.h" }
       module ranges_stable_sort              { private header "__algorithm/ranges_stable_sort.h" }
       module ranges_swap_ranges              { private header "__algorithm/ranges_swap_ranges.h" }
       module ranges_transform                { private header "__algorithm/ranges_transform.h" }
       module ranges_upper_bound              { private header "__algorithm/ranges_upper_bound.h" }
       module remove                          { private header "__algorithm/remove.h" }
       module remove_copy                     { private header "__algorithm/remove_copy.h" }
       module remove_copy_if                  { private header "__algorithm/remove_copy_if.h" }

libcxx/test/libcxx/algorithms/ranges_robust_against_copying_comparators.pass.cpp

#endif
     (void)std::ranges::replace_if(first, last, UnaryTrue(&copies), value); assert(copies == 0);
     (void)std::ranges::replace_if(a, UnaryTrue(&copies), value); assert(copies == 0);
     //(void)std::ranges::search(first, last, first2, mid2, Equal(&copies)); assert(copies == 0);
     //(void)std::ranges::search(a, b, Equal(&copies)); assert(copies == 0);
     //(void)std::ranges::search_n(first, last, count, value, Equal(&copies)); assert(copies == 0);
     //(void)std::ranges::search_n(a, count, value, Equal(&copies)); assert(copies == 0);
     //(void)std::ranges::set_difference(first, mid, mid, last, first2, Less(&copies)); assert(copies == 0);
     //(void)std::ranges::set_difference(a, b, first2, Less(&copies)); assert(copies == 0);
-    //(void)std::ranges::set_intersection(first, mid, mid, last, first2, Less(&copies)); assert(copies == 0);
-    //(void)std::ranges::set_intersection(a, b, first2, Less(&copies)); assert(copies == 0);
+    (void)std::ranges::set_intersection(first, mid, mid, last, first2, Less(&copies)); assert(copies == 0);
+    (void)std::ranges::set_intersection(a, b, first2, Less(&copies)); assert(copies == 0);
     //(void)std::ranges::set_symmetric_difference(first, mid, mid, last, first2, Less(&copies)); assert(copies == 0);
     //(void)std::ranges::set_symmetric_difference(a, b, first2, Less(&copies)); assert(copies == 0);
     //(void)std::ranges::set_union(first, mid, mid, last, first2, Less(&copies)); assert(copies == 0);
     //(void)std::ranges::set_union(a, b, first2, Less(&copies)); assert(copies == 0);
     (void)std::ranges::sort(first, last, Less(&copies)); assert(copies == 0);
     (void)std::ranges::sort(a, Less(&copies)); assert(copies == 0);
     //(void)std::ranges::sort_heap(first, last, Less(&copies)); assert(copies == 0);
     //(void)std::ranges::sort_heap(a, Less(&copies)); assert(copies == 0);

libcxx/test/libcxx/algorithms/ranges_robust_against_copying_projections.pass.cpp

#endif
     (void)std::ranges::replace_if(first, last, UnaryTrue(), T(), Proj(&copies)); assert(copies == 0);
     (void)std::ranges::replace_if(a, UnaryTrue(), T(), Proj(&copies)); assert(copies == 0);
     //(void)std::ranges::search(first, last, first2, mid2, Equal(), Proj(&copies), Proj(&copies)); assert(copies == 0);
     //(void)std::ranges::search(a, b, Equal(), Proj(&copies), Proj(&copies)); assert(copies == 0);
     //(void)std::ranges::search_n(first, last, count, value, Equal(), Proj(&copies)); assert(copies == 0);
     //(void)std::ranges::search_n(a, count, value, Equal(), Proj(&copies)); assert(copies == 0);
     //(void)std::ranges::set_difference(first, mid, mid, last, first2, Less(), Proj(&copies), Proj(&copies)); assert(copies == 0);
     //(void)std::ranges::set_difference(a, b, first2, Less(), Proj(&copies), Proj(&copies)); assert(copies == 0);
-    //(void)std::ranges::set_intersection(first, mid, mid, last, first2, Less(), Proj(&copies), Proj(&copies)); assert(copies == 0);
-    //(void)std::ranges::set_intersection(a, b, first2, Less(), Proj(&copies), Proj(&copies)); assert(copies == 0);
+    (void)std::ranges::set_intersection(first, mid, mid, last, first2, Less(), Proj(&copies), Proj(&copies)); assert(copies == 0);
+    (void)std::ranges::set_intersection(a, b, first2, Less(), Proj(&copies), Proj(&copies)); assert(copies == 0);
     //(void)std::ranges::set_symmetric_difference(first, mid, mid, last, first2, Less(), Proj(&copies), Proj(&copies)); assert(copies == 0);
     //(void)std::ranges::set_symmetric_difference(a, b, first2, Less(), Proj(&copies), Proj(&copies)); assert(copies == 0);
     //(void)std::ranges::set_union(first, mid, mid, last, first2, Less(), Proj(&copies), Proj(&copies)); assert(copies == 0);
     //(void)std::ranges::set_union(a, b, first2, Less(), Proj(&copies), Proj(&copies)); assert(copies == 0);
     (void)std::ranges::sort(first, last, Less(), Proj(&copies)); assert(copies == 0);
     (void)std::ranges::sort(a, Less(), Proj(&copies)); assert(copies == 0);
     //(void)std::ranges::sort_heap(first, last, Less(), Proj(&copies)); assert(copies == 0);
     //(void)std::ranges::sort_heap(a, Less(), Proj(&copies)); assert(copies == 0);

libcxx/test/libcxx/private_headers.verify.cpp

 #include <__algorithm/ranges_minmax_element.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_minmax_element.h'}}
 #include <__algorithm/ranges_mismatch.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_mismatch.h'}}
 #include <__algorithm/ranges_move.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_move.h'}}
 #include <__algorithm/ranges_move_backward.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_move_backward.h'}}
 #include <__algorithm/ranges_none_of.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_none_of.h'}}
 #include <__algorithm/ranges_replace.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_replace.h'}}
 #include <__algorithm/ranges_replace_if.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_replace_if.h'}}
 #include <__algorithm/ranges_reverse.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_reverse.h'}}
+#include <__algorithm/ranges_set_intersection.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_set_intersection.h'}}
 #include <__algorithm/ranges_sort.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_sort.h'}}
 #include <__algorithm/ranges_stable_sort.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_stable_sort.h'}}
 #include <__algorithm/ranges_swap_ranges.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_swap_ranges.h'}}
 #include <__algorithm/ranges_transform.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_transform.h'}}
 #include <__algorithm/ranges_upper_bound.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_upper_bound.h'}}
 #include <__algorithm/remove.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/remove.h'}}
 #include <__algorithm/remove_copy.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/remove_copy.h'}}
 #include <__algorithm/remove_copy_if.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/remove_copy_if.h'}}

libcxx/test/std/algorithms/alg.sorting/alg.set.operations/set.intersection/ranges_set_intersection.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
+//
+//===----------------------------------------------------------------------===//
+
+// <algorithm>
+
+// UNSUPPORTED: c++03, c++11, c++14, c++17
+// UNSUPPORTED: libcpp-has-no-incomplete-ranges
+
+// template<input_iterator I1, sentinel_for<I1> S1, input_iterator I2, sentinel_for<I2> S2,
+//          weakly_incrementable O, class Comp = ranges::less,
+//          class Proj1 = identity, class Proj2 = identity>
+//   requires mergeable<I1, I2, O, Comp, Proj1, Proj2>
+//   constexpr set_intersection_result<I1, I2, O>
+//     set_intersection(I1 first1, S1 last1, I2 first2, S2 last2, O result,
+//                      Comp comp = {}, Proj1 proj1 = {}, Proj2 proj2 = {});                         // since C++20
+//
+// template<input_range R1, input_range R2, weakly_incrementable O,
+//          class Comp = ranges::less, class Proj1 = identity, class Proj2 = identity>
+//   requires mergeable<iterator_t<R1>, iterator_t<R2>, O, Comp, Proj1, Proj2>
+//   constexpr set_intersection_result<borrowed_iterator_t<R1>, borrowed_iterator_t<R2>, O>
+//     set_intersection(R1&& r1, R2&& r2, O result,
+//                      Comp comp = {}, Proj1 proj1 = {}, Proj2 proj2 = {});                         // since C++20
+
+#include <algorithm>
+#include <array>
+#include <concepts>
+
+#include "almost_satisfies_types.h"
+#include "MoveOnly.h"
+#include "test_iterators.h"
+#include "../../sortable_helpers.h"
+
+// Test iterator overload's constraints:
+// =====================================
+template <class InIter1 = int*, class Sent1 = int*, class InIter2 = int*, class Sent2 = int*, class OutIter = int*>
+concept HasSetIntersectionIter =
+    requires(InIter1&& inIter1, InIter2&& inIter2, OutIter&& outIter, Sent1&& sent1, Sent2&& sent2) {
+      std::ranges::set_intersection(
+          std::forward<InIter1>(inIter1),
+          std::forward<Sent1>(sent1),
+          std::forward<InIter2>(inIter2),
+          std::forward<Sent2>(sent2),
+          std::forward<OutIter>(outIter));
+    };
+
+static_assert(HasSetIntersectionIter<int*, int*, int*, int*, int*>);
+
+// !std::input_iterator<I1>
+static_assert(!HasSetIntersectionIter<InputIteratorNotDerivedFrom>);
+
+// !std::sentinel_for<S1, I1>
+static_assert(!HasSetIntersectionIter<int*, SentinelForNotSemiregular>);
+
+// !std::input_iterator<I2>
+static_assert(!HasSetIntersectionIter<int*, int*, InputIteratorNotDerivedFrom>);
+
+// !std::sentinel_for<S2, I2>
+static_assert(!HasSetIntersectionIter<int*, int*, int*, SentinelForNotSemiregular>);
+
+// !std::weakly_incrementable<O>
+static_assert(!HasSetIntersectionIter<int*, int*, int*, int*, WeaklyIncrementableNotMovable>);
+
+// !std::mergeable<I1, I2, O, Comp, Proj1, Proj2>
+static_assert(!HasSetIntersectionIter<MoveOnly*, MoveOnly*, MoveOnly*, MoveOnly*, MoveOnly*>);
+
+// Test range overload's constraints:
+// =====================================
+
+template <class Range1, class Range2, class OutIter>
+concept HasSetIntersectionRange =
+    requires(Range1&& range1, Range2&& range2, OutIter&& outIter) {
+      std::ranges::set_intersection(
+          std::forward<Range1>(range1), std::forward<Range2>(range2), std::forward<OutIter>(outIter));
+    };
+
+static_assert(HasSetIntersectionRange<UncheckedRange<int*>, UncheckedRange<int*>, int*>);
+
+// !std::input_range<R2>
+static_assert(!HasSetIntersectionRange<UncheckedRange<InputIteratorNotDerivedFrom>, UncheckedRange<int*>, int*>);
+
+// !std::input_range<R2>
+static_assert(!HasSetIntersectionRange<UncheckedRange<int*>, UncheckedRange<InputIteratorNotDerivedFrom>, int*>);
+
+// !std::weakly_incrementable<O>
+static_assert(!HasSetIntersectionRange<UncheckedRange<int*>, UncheckedRange<int*>, WeaklyIncrementableNotMovable >);
+
+// !std::mergeable<iterator_t<R1>, iterator_t<R2>, O, Comp, Proj1, Proj2>
+static_assert(!HasSetIntersectionRange<UncheckedRange<MoveOnly*>, UncheckedRange<MoveOnly*>, MoveOnly*>);
+
+using std::ranges::set_intersection_result;
+
+template <class In1, class In2, class Out, std::size_t N1, std::size_t N2, std::size_t N3>
+constexpr void testSetIntersectionImpl(std::array<int, N1> in1, std::array<int, N2> in2, std::array<int, N3> expected) {
+  // TODO: std::ranges::set_intersection calls std::ranges::copy
+  // std::ranges::copy(contiguous_iterator<int*>, sentinel_wrapper<contiguous_iterator<int*>>, contiguous_iterator<int*>) doesn't seem to work.
+  // It seems that std::ranges::copy calls std::copy, which unwraps contiguous_iterator<int*> into int*,
+  // and then it failed because there is no == between int* and sentinel_wrapper<contiguous_iterator<int*>>
+  using Sent1 = std::conditional_t<std::contiguous_iterator<In1>, In1, sentinel_wrapper<In1>>;
+  using Sent2 = std::conditional_t<std::contiguous_iterator<In2>, In2, sentinel_wrapper<In2>>;
+
+  // iterator overload
+  {
+    std::array<int, N3> out;
+    std::same_as<set_intersection_result<In1, In2, Out>> decltype(auto) result = std::ranges::set_intersection(
+        In1{in1.data()},
+        Sent1{In1{in1.data() + in1.size()}},
+        In2{in2.data()},
+        Sent2{In2{in2.data() + in2.size()}},
+        Out{out.data()});
+    assert(std::ranges::equal(out, expected));
+
+    assert(base(result.in1) == in1.data() + in1.size());
+    assert(base(result.in2) == in2.data() + in2.size());
+    assert(base(result.out) == out.data() + out.size());
+  }
+
+  // range overload
+  {
+    std::array<int, N3> out;
+    std::ranges::subrange r1{In1{in1.data()}, Sent1{In1{in1.data() + in1.size()}}};
+    std::ranges::subrange r2{In2{in2.data()}, Sent2{In2{in2.data() + in2.size()}}};
+    std::same_as<set_intersection_result<In1, In2, Out>> decltype(auto) result =
+        std::ranges::set_intersection(r1, r2, Out{out.data()});
+    assert(std::ranges::equal(out, expected));
+
+    assert(base(result.in1) == in1.data() + in1.size());
+    assert(base(result.in2) == in2.data() + in2.size());
+    assert(base(result.out) == out.data() + out.size());
+  }
+}
+
+template <class In1, class In2, class Out>
+constexpr void testImpl() {
+  // range 1 shorter than range2
+  {
+    std::array in1{0, 1, 5, 6, 9, 10};
+    std::array in2{3, 6, 7, 9, 13, 15, 100};
+    std::array expected{6, 9};
+    testSetIntersectionImpl<In1, In2, Out>(in1, in2, expected);
+  }
+
+  // range 2 shorter than range 1
+  {
+    std::array in1{2, 6, 8, 12, 15, 16};
+    std::array in2{0, 2, 8};
+    std::array expected{2, 8};
+    testSetIntersectionImpl<In1, In2, Out>(in1, in2, expected);
+  }
+
+  // range 1 and range 2 has the same length but different elements
+  {
+    std::array in1{2, 6, 8, 12, 15, 16};
+    std::array in2{0, 2, 8, 15, 17, 19};
+    std::array expected{2, 8, 15};
+    testSetIntersectionImpl<In1, In2, Out>(in1, in2, expected);
+  }
+
+  // range 1 == range 2
+  {
+    std::array in1{0, 1, 2};
+    std::array in2{0, 1, 2};
+    std::array expected{0, 1, 2};
+    testSetIntersectionImpl<In1, In2, Out>(in1, in2, expected);
+  }
+
+  // range 1 is super set of range 2
+  {
+    std::array in1{8, 8, 10, 12, 13};
+    std::array in2{8, 10};
+    std::array expected{8, 10};
+    testSetIntersectionImpl<In1, In2, Out>(in1, in2, expected);
+  }
+
+  // range 2 is super set of range 1
+  {
+    std::array in1{0, 1, 1};
+    std::array in2{0, 1, 1, 2, 5};
+    std::array expected{0, 1, 1};
+    testSetIntersectionImpl<In1, In2, Out>(in1, in2, expected);
+  }
+
+  // range 1 and range 2 have no elements in common
+  {
+    std::array in1{7, 7, 9, 12};
+    std::array in2{1, 5, 5, 8, 10};
+    std::array<int, 0> expected{};
+    testSetIntersectionImpl<In1, In2, Out>(in1, in2, expected);
+  }
+
+  // range 1 and range 2 have duplicated equal elements
+  {
+    std::array in1{7, 7, 9, 12};
+    std::array in2{7, 7, 7, 13};
+    std::array expected{7, 7};
+    testSetIntersectionImpl<In1, In2, Out>(in1, in2, expected);
+  }
+
+  // range 1 is empty
+  {
+    std::array<int, 0> in1{};
+    std::array in2{3, 4, 5};
+    std::array<int, 0> expected{};
+    testSetIntersectionImpl<In1, In2, Out>(in1, in2, expected);
+  }
+
+  // range 2 is empty
+  {
+    std::array in1{3, 4, 5};
+    std::array<int, 0> in2{};
+    std::array<int, 0> expected{};
+    testSetIntersectionImpl<In1, In2, Out>(in1, in2, expected);
+  }
+
+  // both ranges are empty
+  {
+    std::array<int, 0> in1{};
+    std::array<int, 0> in2{};
+    std::array<int, 0> expected{};
+    testSetIntersectionImpl<In1, In2, Out>(in1, in2, expected);
+  }
+
+  // check that ranges::dangling is returned for non-borrowed_range
+  {
+    struct NonBorrowedRange {
+      int* data_;
+      size_t size_;
+
+      // TODO: std::ranges::set_intersection calls std::__copy
+      // std::ranges::copy(contiguous_iterator<int*>, sentinel_wrapper<contiguous_iterator<int*>>, contiguous_iterator<int*>) doesn't seem to work.
+      // It seems that std::ranges::copy calls std::copy, which unwraps contiguous_iterator<int*> into int*,
+      // and then it failed because there is no == between int* and sentinel_wrapper<contiguous_iterator<int*>>
+      using Sent = std::conditional_t<std::contiguous_iterator<In2>, In2, sentinel_wrapper<In2>>;
+
+      constexpr NonBorrowedRange(int* d, size_t s) : data_{d}, size_{s} {}
+
+      constexpr In2 begin() const { return In2{data_}; };
+      constexpr Sent end() const { return Sent{In2{data_ + size_}}; };
+    };
+
+    std::array r1{3, 6, 7, 9};
+    int r2[] = {2, 3, 4, 5, 6};
+    std::array<int, 2> out;
+    std::same_as<set_intersection_result<std::ranges::dangling, int*, int*>> decltype(auto) result =
+        std::ranges::set_intersection(NonBorrowedRange{r1.data(), r1.size()}, r2, out.data());
+    assert(base(result.in2) == r2 + 5);
+    assert(base(result.out) == out.data() + out.size());
+    assert(std::ranges::equal(out, std::array{3, 6}));
+  }
+}
+
+template <class InIter2, class OutIter>
+constexpr void withAllPermutationsOfInIter1() {
+  // C++17 InputIterator may or may not satisfy std::input_iterator
+  testImpl<cpp20_input_iterator<int*>, InIter2, OutIter>();
+  testImpl<forward_iterator<int*>, InIter2, OutIter>();
+  testImpl<bidirectional_iterator<int*>, InIter2, OutIter>();
+  testImpl<random_access_iterator<int*>, InIter2, OutIter>();
+  testImpl<contiguous_iterator<int*>, InIter2, OutIter>();
+}
+
+template <class OutIter>
+constexpr bool withAllPermutationsOfInIter1AndInIter2() {
+  withAllPermutationsOfInIter1<cpp20_input_iterator<int*>, OutIter>();
+  withAllPermutationsOfInIter1<forward_iterator<int*>, OutIter>();
+  withAllPermutationsOfInIter1<bidirectional_iterator<int*>, OutIter>();
+  withAllPermutationsOfInIter1<random_access_iterator<int*>, OutIter>();
+  withAllPermutationsOfInIter1<contiguous_iterator<int*>, OutIter>();
+  return true;
+}
+
+constexpr void runAllIteratorPermutationsTests() {
+  withAllPermutationsOfInIter1AndInIter2<cpp20_output_iterator<int*>>();
+  withAllPermutationsOfInIter1AndInIter2<cpp20_input_iterator<int*>>();
+  withAllPermutationsOfInIter1AndInIter2<forward_iterator<int*>>();
+  withAllPermutationsOfInIter1AndInIter2<bidirectional_iterator<int*>>();
+  withAllPermutationsOfInIter1AndInIter2<random_access_iterator<int*>>();
+  withAllPermutationsOfInIter1AndInIter2<contiguous_iterator<int*>>();
+
+  static_assert(withAllPermutationsOfInIter1AndInIter2<cpp20_output_iterator<int*>>());
+  static_assert(withAllPermutationsOfInIter1AndInIter2<cpp20_input_iterator<int*>>());
+  static_assert(withAllPermutationsOfInIter1AndInIter2<forward_iterator<int*>>());
+  static_assert(withAllPermutationsOfInIter1AndInIter2<bidirectional_iterator<int*>>());
+  static_assert(withAllPermutationsOfInIter1AndInIter2<random_access_iterator<int*>>());
+  static_assert(withAllPermutationsOfInIter1AndInIter2<contiguous_iterator<int*>>());
+}
+
+constexpr bool test() {
+  // check that every element is copied exactly once
+  {
+    std::array<TracedCopy, 5> r1{3, 5, 8, 15, 16};
+    std::array<TracedCopy, 3> r2{1, 3, 8};
+
+    // iterator overload
+    {
+      std::array<TracedCopy, 2> out;
+      auto result = std::ranges::set_intersection(r1.begin(), r1.end(), r2.begin(), r2.end(), out.data());
+
+      assert(result.in1 == r1.end());
+      assert(result.in2 == r2.end());
+      assert(result.out == out.end());
+      assert(std::ranges::equal(out, std::array<TracedCopy, 2>{3, 8}));
+
+      assert(std::ranges::all_of(out, &TracedCopy::copiedOnce));
+    }
+
+    // range overload
+    {
+      std::array<TracedCopy, 2> out;
+      auto result = std::ranges::set_intersection(r1, r2, out.data());
+
+      assert(result.in1 == r1.end());
+      assert(result.in2 == r2.end());
+      assert(result.out == out.end());
+      assert(std::ranges::equal(out, std::array<TracedCopy, 2>{3, 8}));
+
+      assert(std::ranges::all_of(out, &TracedCopy::copiedOnce));
+    }
+  }
+
+  struct IntAndOrder {
+    int data;
+    int order;
+
+    constexpr auto operator==(const IntAndOrder& o) const { return data == o.data; }
+    constexpr auto operator<=>(const IntAndOrder& o) const { return data <=> o.data; }
+  };
+
+  // Stable. If [first1, last1) contains m elements that are equivalent to each other and [first2, last2)
+  // contains n elements that are equivalent to them, the first min(m, n) elements are copied from the first
+  // range to the output range, in order.
+  {
+    std::array<IntAndOrder, 5> r1{{{0, 0}, {0, 1}, {0, 2}, {0, 3}, {0, 4}}};
+    std::array<IntAndOrder, 3> r2{{{0, 5}, {0, 6}, {0, 7}}};
+
+    // iterator overload
+    {
+      std::array<IntAndOrder, 3> out;
+      std::ranges::set_intersection(r1.begin(), r1.end(), r2.begin(), r2.end(), out.data());
+
+      assert(std::ranges::equal(out, std::array{0, 0, 0}, {}, &IntAndOrder::data));
+      assert(std::ranges::equal(out, std::array{0, 1, 2}, {}, &IntAndOrder::order));
+    }
+
+    // range overload
+    {
+      std::array<IntAndOrder, 3> out;
+      std::ranges::set_intersection(r1, r2, out.data());
+
+      assert(std::ranges::equal(out, std::array{0, 0, 0}, {}, &IntAndOrder::data));
+      assert(std::ranges::equal(out, std::array{0, 1, 2}, {}, &IntAndOrder::order));
+    }
+  }
+
+  struct Data {
+    int data;
+
+    constexpr bool smallerThan(const Data& o) const { return data < o.data; }
+  };
+
+  // Test custom comparator
+  {
+    std::array r1{Data{4}, Data{8}, Data{12}};
+    std::array r2{Data{8}, Data{9}};
+
+    // iterator overload
+    {
+      std::array<Data, 1> out;
+      auto result = std::ranges::set_intersection(
+          r1.begin(), r1.end(), r2.begin(), r2.end(), out.data(), [](const Data& x, const Data& y) {
+            return x.data < y.data;
+          });
+
+      assert(std::ranges::equal(out, std::array{8}, {}, &Data::data));
+
+      assert(result.in1 == r1.end());
+      assert(result.in2 == r2.end());
+      assert(result.out == out.end());
+    }
+
+    // range overload
+    {
+      std::array<Data, 1> out;
+      auto result = std::ranges::set_intersection(r1, r2, out.data(), [](const Data& x, const Data& y) {
+        return x.data < y.data;
+      });
+
+      assert(std::ranges::equal(out, std::array{8}, {}, &Data::data));
+
+      assert(result.in1 == r1.end());
+      assert(result.in2 == r2.end());
+      assert(result.out == out.end());
+    }
+
+    // member pointer Comparator iterator overload
+    {
+      std::array<Data, 1> out;
+      auto result =
+          std::ranges::set_intersection(r1.begin(), r1.end(), r2.begin(), r2.end(), out.data(), &Data::smallerThan);
+
+      assert(std::ranges::equal(out, std::array{8}, {}, &Data::data));
+
+      assert(result.in1 == r1.end());
+      assert(result.in2 == r2.end());
+      assert(result.out == out.end());
+    }
+
+    // member pointer Comparator range overload
+    {
+      std::array<Data, 1> out;
+      auto result = std::ranges::set_intersection(r1, r2, out.data(), &Data::smallerThan);
+
+      assert(std::ranges::equal(out, std::array{8}, {}, &Data::data));
+
+      assert(result.in1 == r1.end());
+      assert(result.in2 == r2.end());
+      assert(result.out == out.end());
+    }
+  }
+
+  // Test Projection
+  {
+    std::array r1{Data{1}, Data{3}, Data{5}};
+    std::array r2{Data{2}, Data{3}, Data{5}};
+
+    const auto proj = [](const Data& d) { return d.data; };
+
+    // iterator overload
+    {
+      std::array<Data, 2> out;
+      auto result = std::ranges::set_intersection(
+          r1.begin(), r1.end(), r2.begin(), r2.end(), out.data(), std::ranges::less{}, proj, proj);
+
+      assert(std::ranges::equal(out, std::array{3, 5}, {}, &Data::data));
+
+      assert(result.in1 == r1.end());
+      assert(result.in2 == r2.end());
+      assert(result.out == out.end());
+    }
+
+    // range overload
+    {
+      std::array<Data, 2> out;
+      auto result = std::ranges::set_intersection(r1, r2, out.data(), std::ranges::less{}, proj, proj);
+
+      assert(std::ranges::equal(out, std::array{3, 5}, {}, &Data::data));
+
+      assert(result.in1 == r1.end());
+      assert(result.in2 == r2.end());
+      assert(result.out == out.end());
+    }
+
+    // member pointer Projection iterator overload
+    {
+      std::array<Data, 2> out;
+      auto result = std::ranges::set_intersection(
+          r1.begin(), r1.end(), r2.begin(), r2.end(), out.data(), {}, &Data::data, &Data::data);
+
+      assert(std::ranges::equal(out, std::array{3, 5}, {}, &Data::data));
+
+      assert(result.in1 == r1.end());
+      assert(result.in2 == r2.end());
+      assert(result.out == out.end());
+    }
+
+    // member pointer Projection range overload
+    {
+      std::array<Data, 2> out;
+      auto result = std::ranges::set_intersection(r1, r2, out.data(), std::ranges::less{}, &Data::data, &Data::data);
+
+      assert(std::ranges::equal(out, std::array{3, 5}, {}, &Data::data));
+
+      assert(result.in1 == r1.end());
+      assert(result.in2 == r2.end());
+      assert(result.out == out.end());
+    }
+  }
+
+  // Complexity: At most 2 * ((last1 - first1) + (last2 - first2)) - 1 comparisons and applications of each projection.
+  {
+    std::array<Data, 5> r1{{{1}, {3}, {5}, {7}, {9}}};
+    std::array<Data, 5> r2{{{2}, {4}, {6}, {8}, {10}}};
+    std::array<int, 0> expected{};
+
+    const std::size_t maxOperation = 2 * (r1.size() + r2.size()) - 1;
+
+    // iterator overload
+    {
+      std::array<Data, 0> out{};
+      std::size_t numberOfComp  = 0;
+      std::size_t numberOfProj1 = 0;
+      std::size_t numberOfProj2 = 0;
+
+      const auto comp = [&numberOfComp](int x, int y) {
+        ++numberOfComp;
+        return x < y;
+      };
+
+      const auto proj1 = [&numberOfProj1](const Data& d) {
+        ++numberOfProj1;
+        return d.data;
+      };
+
+      const auto proj2 = [&numberOfProj2](const Data& d) {
+        ++numberOfProj2;
+        return d.data;
+      };
+
+      std::ranges::set_intersection(r1.begin(), r1.end(), r2.begin(), r2.end(), out.data(), comp, proj1, proj2);
+
+      assert(std::ranges::equal(out, expected, {}, &Data::data));
+      assert(numberOfComp < maxOperation);
+      assert(numberOfProj1 < maxOperation);
+      assert(numberOfProj2 < maxOperation);
+    }
+
+    // range overload
+    {
+      std::array<Data, 0> out{};
+      std::size_t numberOfComp  = 0;
+      std::size_t numberOfProj1 = 0;
+      std::size_t numberOfProj2 = 0;
+
+      const auto comp = [&numberOfComp](int x, int y) {
+        ++numberOfComp;
+        return x < y;
+      };
+
+      const auto proj1 = [&numberOfProj1](const Data& d) {
+        ++numberOfProj1;
+        return d.data;
+      };
+
+      const auto proj2 = [&numberOfProj2](const Data& d) {
+        ++numberOfProj2;
+        return d.data;
+      };
+
+      std::ranges::set_intersection(r1, r2, out.data(), comp, proj1, proj2);
+
+      assert(std::ranges::equal(out, expected, {}, &Data::data));
+      assert(numberOfComp < maxOperation);
+      assert(numberOfProj1 < maxOperation);
+      assert(numberOfProj2 < maxOperation);
+    }
+  }
+
+  // Comparator convertible to bool
+  {
+    struct ConvertibleToBool {
+      bool b;
+      constexpr operator bool() const { return b; }
+    };
+    Data r1[] = {{3}, {4}};
+    Data r2[] = {{3}, {4}, {5}};
+
+    const auto comp = [](const Data& x, const Data& y) { return ConvertibleToBool{x.data < y.data}; };
+
+    // iterator overload
+    {
+      std::array<Data, 2> out;
+      std::ranges::set_intersection(r1, r1 + 2, r2, r2 + 3, out.data(), comp);
+      assert(std::ranges::equal(out, std::array{3, 4}, {}, &Data::data));
+    }
+
+    // range overload
+    {
+      std::array<Data, 2> out;
+      std::ranges::set_intersection(r1, r2, out.data(), comp);
+      assert(std::ranges::equal(out, std::array{3, 4}, {}, &Data::data));
+    }
+  }
+
+  return true;
+}
+
+int main(int, char**) {
+  test();
+  static_assert(test());
+
+  runAllIteratorPermutationsTests();
+
+  return 0;
+}
 No newline at end of file

libcxx/test/std/algorithms/alg.sorting/sortable_helpers.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 SORTABLE_HELPERS_H
 #define SORTABLE_HELPERS_H
 
 #include <type_traits>
 
 #include "test_macros.h"
 
+#if TEST_STD_VER > 17
+#include <compare>
+#endif 
+
 struct TrivialSortable {
     int value;
     TEST_CONSTEXPR TrivialSortable() : value(0) {}
     TEST_CONSTEXPR TrivialSortable(int v) : value(v) {}
     friend TEST_CONSTEXPR bool operator<(const TrivialSortable& a, const TrivialSortable& b) {
         return a.value / 10 < b.value / 10;
     }
     static TEST_CONSTEXPR bool less(const TrivialSortable& a, const TrivialSortable& b) {
struct NonTrivialSortableWithComp {
     }
 };
 
 static_assert(std::is_trivially_copyable<TrivialSortable>::value, "");
 static_assert(std::is_trivially_copyable<TrivialSortableWithComp>::value, "");
 static_assert(!std::is_trivially_copyable<NonTrivialSortable>::value, "");
 static_assert(!std::is_trivially_copyable<NonTrivialSortableWithComp>::value, "");
 
+#if TEST_STD_VER > 17
+struct TracedCopy {
+  int copied = 0;
+  int data   = 0;
+
+  constexpr TracedCopy() = default;
+  constexpr TracedCopy(int i) : data(i) {}
+  constexpr TracedCopy(const TracedCopy& other) : copied(other.copied + 1), data(other.data) {}
+
+  constexpr TracedCopy(TracedCopy&& other)            = delete;
+  constexpr TracedCopy& operator=(TracedCopy&& other) = delete;
+
+  constexpr TracedCopy& operator=(const TracedCopy& other) {
+    copied = other.copied + 1;
+    data   = other.data;
+    return *this;
+  }
+
+  constexpr bool copiedOnce() const { return copied == 1; }
+
+  constexpr bool operator==(const TracedCopy& o) const { return data == o.data; }
+  constexpr auto operator<=>(const TracedCopy& o) const { return data <=> o.data; }
+};
+#endif // TEST_STD_VER > 17
+
 #endif // SORTABLE_HELPERS_H

libcxx/test/std/library/description/conventions/customization.point.object/niebloid.compile.pass.cpp

 static_assert(test(std::ranges::reverse, a));
 //static_assert(test(std::ranges::reverse_copy, a, a));
 //static_assert(test(std::ranges::rotate, a, a+5));
 //static_assert(test(std::ranges::rotate_copy, a, a+5, a));
 //static_assert(test(std::ranges::sample, a, a, 5));
 //static_assert(test(std::ranges::search, a, a));
 //static_assert(test(std::ranges::search_n, a, 10, 42));
 //static_assert(test(std::ranges::set_difference, a, a, a));
-//static_assert(test(std::ranges::set_intersection, a, a, a));
+static_assert(test(std::ranges::set_intersection, a, a, a));
 //static_assert(test(std::ranges::set_symmetric_difference, a, a, a));
 //static_assert(test(std::ranges::set_union, a, a, a));
 //static_assert(test(std::ranges::shuffle, a, g));
 static_assert(test(std::ranges::sort, a));
 //static_assert(test(std::ranges::sort_heap, a));
 //static_assert(test(std::ranges::stable_partition, a, odd));
 static_assert(test(std::ranges::stable_sort, a));
 //static_assert(test(std::ranges::starts_with, a, a));