[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

31

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.

63

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

229

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

273

Unused?

585

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

31

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

63

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

31

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.

63

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

31

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.

63

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

273

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

585

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

63

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

585

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

69

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,`D128983 <https://llvm.org/D128983>`,✅
-Merge,set_intersection,Hui Xie,n/a,Not started
+Merge,set_intersection,Hui Xie,`D129233 <https://llvm.org/D129233>`,✅
 Merge,set_symmetric_difference,Hui Xie,n/a,Not started
 Merge,set_union,Hui Xie,n/a,Not started
 Permutation,remove,Nikolas Klauser,`D128618 <https://llvm.org/D128618>`_,✅
 Permutation,remove_if,Nikolas Klauser,`D128618 <https://llvm.org/D128618>`_,✅
 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_move_backward.h
   __algorithm/ranges_none_of.h
   __algorithm/ranges_remove.h
   __algorithm/ranges_remove_if.h
   __algorithm/ranges_replace.h
   __algorithm/ranges_replace_if.h
   __algorithm/ranges_reverse.h
   __algorithm/ranges_set_difference.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/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
 
 #include <__config>
 #include <__iterator/advance.h>
 #include <__iterator/distance.h>
 #include <__iterator/iterator_traits.h>
+#include <__iterator/next.h>
 
 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
 #  pragma GCC system_header
 #endif
 
 _LIBCPP_BEGIN_NAMESPACE_STD
 
 #if _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES)
 struct _RangesIterOps {
   static constexpr auto advance = ranges::advance;
   static constexpr auto distance = ranges::distance;
+  static constexpr auto next = ranges::next;
 };
 #endif
 
 struct _StdIterOps {
 
   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 <class _Iterator>
   _LIBCPP_HIDE_FROM_ABI static _LIBCPP_CONSTEXPR_AFTER_CXX11
   typename iterator_traits<_Iterator>::difference_type distance(_Iterator __first, _Iterator __last) {
     return std::distance(__first, __last);
   }
 
+  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

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/iterator_operations.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 <__ranges/access.h>
+#include <__ranges/concepts.h>
+#include <__ranges/dangling.h>
+#include <__utility/move.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 _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<_RangesIterOps>(
+        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)};
+  }
+
+  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<_RangesIterOps>(
+        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)};
+  }
+};
+
+} // 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 <__algorithm/iterator_operations.h>
 #include <__config>
 #include <__iterator/iterator_traits.h>
+#include <__utility/move.h>
 
 #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 _InIter1, class _InIter2, class _OutIter>
+struct __set_intersection_result {
+  _InIter1 in1;
+  _InIter2 in2;
+  _OutIter out;
+
+  // need a constructor as C++03 aggregate init is hard
+  _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX17
+  __set_intersection_result(_InIter1&& __inIter1, _InIter2&& __inIter2, _OutIter&& __outIter)
+      : in1(std::move(__inIter1)), in2(std::move(__inIter2)), out(std::move(__outIter)) {}
+};
+
+template < class _IterOper, 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) {
+    else {
+      if (!__comp(*__first2, *__first1)) {
+
+  return __set_intersection_result<_InIter1, _InIter2, _OutIter>(
+      _IterOper::next(std::move(__first1), std::move(__last1)),
+      _IterOper::next(std::move(__first2), std::move(__last2)),
+      std::move(__result));
 }
 
 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) {
+  return std::__set_intersection<_StdIterOps, _Comp_ref>(__first1, __last1, __first2, __last2, __result, __comp).out;
 }
 
 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) {
+  return std::__set_intersection<_StdIterOps>(
+             __first1,
+             __last1,
+             __first2,
+             __last2,
+             __result,
+                    typename iterator_traits<_InputIterator2>::value_type>())
+      .out;
 }
 
 _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 set_difference_result<borrowed_iterator_t<R1>, O>
       set_difference(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_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<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_move_backward.h>
 #include <__algorithm/ranges_none_of.h>
 #include <__algorithm/ranges_remove.h>
 #include <__algorithm/ranges_remove_if.h>
 #include <__algorithm/ranges_replace.h>
 #include <__algorithm/ranges_replace_if.h>
 #include <__algorithm/ranges_reverse.h>
 #include <__algorithm/ranges_set_difference.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_move_backward            { private header "__algorithm/ranges_move_backward.h" }
       module ranges_none_of                  { private header "__algorithm/ranges_none_of.h" }
       module ranges_remove                   { private header "__algorithm/ranges_remove.h" }
       module ranges_remove_if                { private header "__algorithm/ranges_remove_if.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_difference           { private header "__algorithm/ranges_set_difference.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_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_remove.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_remove.h'}}
 #include <__algorithm/ranges_remove_if.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_remove_if.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_difference.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_set_difference.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.merge/ranges_merge.pass.cpp

// both ranges are empty
     std::array<int, 0> in1{};
     std::array<int, 0> in2{};
     std::array<int, 0> expected{};
     testMergeImpl<In1, In2, Out>(in1, in2, expected);
   }
 
   // check that ranges::dangling is returned for non-borrowed_range and iterator_t is returned for borrowed_range
   {
-    struct NonBorrowedRange {
-      int* data_;
-      size_t size_;
-
-      // TODO: std::ranges::merge 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 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};
     std::array r2{2, 3, 4};
     std::array<int, 7> out;
     std::same_as<merge_result<std::array<int, 4>::iterator, std::ranges::dangling, int*>> decltype(auto) result =
-        std::ranges::merge(r1, NonBorrowedRange{r2.data(), r2.size()}, out.data());
+        std::ranges::merge(r1, NonBorrowedRange<In2>{r2.data(), r2.size()}, out.data());
     assert(base(result.in1) == r1.end());
     assert(base(result.out) == out.data() + out.size());
     assert(std::ranges::equal(out, std::array{2, 3, 3, 4, 6, 7, 9}));
   }
 }
 
 template <class InIter2, class OutIter>
 constexpr void withAllPermutationsOfInIter1() {

libcxx/test/std/algorithms/alg.sorting/alg.set.operations/set.difference/ranges_set_difference.pass.cpp

// both ranges are empty
     std::array<int, 0> in1{};
     std::array<int, 0> in2{};
     std::array<int, 0> expected{};
     testSetDifferenceImpl<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_difference 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};
     std::array r2{2, 3, 4, 5, 6};
     std::array<int, 2> out;
     std::same_as<set_difference_result<std::ranges::dangling, int*>> decltype(auto) result =
-        std::ranges::set_difference(NonBorrowedRange{r1.data(), r1.size()}, r2, out.data());
+        std::ranges::set_difference(NonBorrowedRange<In1>{r1.data(), r1.size()}, r2, out.data());
     assert(base(result.out) == out.data() + out.size());
     assert(std::ranges::equal(out, std::array{7, 9}));
   }
 }
 
 template <class InIter2, class OutIter>
 constexpr void withAllPermutationsOfInIter1() {
   // C++17 InputIterator may or may not satisfy std::input_iterator

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_difference_result<I1, O>
-//     set_difference(I1 first1, S1 last1, I2 first2, S2 last2, O result,
-//                    Comp comp = {}, Proj1 proj1 = {}, Proj2 proj2 = {});                           // since C++20
-
+//   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_difference_result<borrowed_iterator_t<R1>, O>
-//     set_difference(R1&& r1, R2&& r2, O result,
-//                    Comp comp = {}, Proj1 proj1 = {}, Proj2 proj2 = {});                           // since C++20
+//   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,
-    class InIter2,
-    class OutIter,
-    class Sent1 = sentinel_wrapper<InIter1>,
-    class Sent2 = sentinel_wrapper<InIter2>>
-concept HasSetDifferenceIter =
+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_difference(
+      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(HasSetDifferenceIter<int*, int*, int*, int*, int*>);
+static_assert(HasSetIntersectionIter<int*, int*, int*, int*, int*>);
 
 // !std::input_iterator<I1>
-static_assert(!HasSetDifferenceIter<InputIteratorNotDerivedFrom, int*, int*>);
+static_assert(!HasSetIntersectionIter<InputIteratorNotDerivedFrom>);
 
 // !std::sentinel_for<S1, I1>
-static_assert(!HasSetDifferenceIter<int*, int*, int*, SentinelForNotSemiregular>);
+static_assert(!HasSetIntersectionIter<int*, SentinelForNotSemiregular>);
 
 // !std::input_iterator<I2>
-static_assert(!HasSetDifferenceIter<int*, InputIteratorNotDerivedFrom, int*>);
+static_assert(!HasSetIntersectionIter<int*, int*, InputIteratorNotDerivedFrom>);
 
 // !std::sentinel_for<S2, I2>
-static_assert(!HasSetDifferenceIter<int*, int*, int*, int*, SentinelForNotSemiregular>);
+static_assert(!HasSetIntersectionIter<int*, int*, int*, SentinelForNotSemiregular>);
 
 // !std::weakly_incrementable<O>
-static_assert(!HasSetDifferenceIter<int*, int*, WeaklyIncrementableNotMovable>);
+static_assert(!HasSetIntersectionIter<int*, int*, int*, int*, WeaklyIncrementableNotMovable>);
 
 // !std::mergeable<I1, I2, O, Comp, Proj1, Proj2>
-static_assert(!HasSetDifferenceIter<MoveOnly*, MoveOnly*, MoveOnly*, MoveOnly*, MoveOnly*>);
+static_assert(!HasSetIntersectionIter<MoveOnly*, MoveOnly*, MoveOnly*, MoveOnly*, MoveOnly*>);
 
 // Test range overload's constraints:
 // =====================================
 
 template <class Range1, class Range2, class OutIter>
-concept HasSetDifferenceRange =
+concept HasSetIntersectionRange =
     requires(Range1&& range1, Range2&& range2, OutIter&& outIter) {
-      std::ranges::set_difference(
+      std::ranges::set_intersection(
           std::forward<Range1>(range1), std::forward<Range2>(range2), std::forward<OutIter>(outIter));
     };
 
-static_assert(HasSetDifferenceRange<UncheckedRange<int*>, UncheckedRange<int*>, int*>);
+static_assert(HasSetIntersectionRange<UncheckedRange<int*>, UncheckedRange<int*>, int*>);
 
 // !std::input_range<R2>
-static_assert(!HasSetDifferenceRange<UncheckedRange<InputIteratorNotDerivedFrom>, UncheckedRange<int*>, int*>);
+static_assert(!HasSetIntersectionRange<UncheckedRange<InputIteratorNotDerivedFrom>, UncheckedRange<int*>, int*>);
 
 // !std::input_range<R2>
-static_assert(!HasSetDifferenceRange<UncheckedRange<int*>, UncheckedRange<InputIteratorNotDerivedFrom>, int*>);
+static_assert(!HasSetIntersectionRange<UncheckedRange<int*>, UncheckedRange<InputIteratorNotDerivedFrom>, int*>);
 
 // !std::weakly_incrementable<O>
-static_assert(!HasSetDifferenceRange<UncheckedRange<int*>, UncheckedRange<int*>, WeaklyIncrementableNotMovable >);
+static_assert(!HasSetIntersectionRange<UncheckedRange<int*>, UncheckedRange<int*>, WeaklyIncrementableNotMovable >);
 
 // !std::mergeable<iterator_t<R1>, iterator_t<R2>, O, Comp, Proj1, Proj2>
-static_assert(!HasSetDifferenceRange< UncheckedRange<MoveOnly*>, UncheckedRange<MoveOnly*>, MoveOnly*>);
+static_assert(!HasSetIntersectionRange<UncheckedRange<MoveOnly*>, UncheckedRange<MoveOnly*>, MoveOnly*>);
 
-using std::ranges::set_difference_result;
+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 testSetDifferenceImpl(std::array<int, N1> in1, std::array<int, N2> in2, std::array<int, N3> expected) {
-  // TODO: std::ranges::set_difference calls std::ranges::copy
+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_difference_result<In1, Out>> decltype(auto) result = std::ranges::set_difference(
+    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.in) == in1.data() + in1.size());
+    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_difference_result<In1, Out>> decltype(auto) result =
-        std::ranges::set_difference(r1, r2, Out{out.data()});
+    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.in) == in1.data() + in1.size());
+    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{0, 1, 5, 10};
-    testSetDifferenceImpl<In1, In2, Out>(in1, in2, expected);
+    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{6, 12, 15, 16};
-    testSetDifferenceImpl<In1, In2, Out>(in1, in2, expected);
+    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{6, 12, 16};
-    testSetDifferenceImpl<In1, In2, Out>(in1, in2, expected);
+    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<int, 0> expected{};
-    testSetDifferenceImpl<In1, In2, Out>(in1, in2, expected);
+    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, 12, 13};
-    testSetDifferenceImpl<In1, In2, Out>(in1, in2, expected);
+    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{};
-    testSetDifferenceImpl<In1, In2, Out>(in1, in2, 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{};
-    testSetDifferenceImpl<In1, In2, Out>(in1, in2, 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 expected{3, 4, 5};
-    testSetDifferenceImpl<In1, In2, Out>(in1, in2, expected);
+    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{};
-    testSetDifferenceImpl<In1, In2, Out>(in1, in2, 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_difference 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};
-    std::array r2{2, 3, 4, 5, 6};
+    int r2[] = {2, 3, 4, 5, 6};
     std::array<int, 2> out;
-    std::same_as<set_difference_result<std::ranges::dangling, int*>> decltype(auto) result =
-        std::ranges::set_difference(NonBorrowedRange{r1.data(), r1.size()}, r2, out.data());
+    std::same_as<set_intersection_result<std::ranges::dangling, int*, int*>> decltype(auto) result =
+        std::ranges::set_intersection(NonBorrowedRange<In1>{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{7, 9}));
+    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>();
constexpr void runAllIteratorPermutationsTests() {
   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, 3> out;
-      auto result = std::ranges::set_difference(r1.begin(), r1.end(), r2.begin(), r2.end(), out.data());
+      std::array<TracedCopy, 2> out;
+      auto result = std::ranges::set_intersection(r1.begin(), r1.end(), r2.begin(), r2.end(), out.data());
 
-      assert(result.in == r1.end());
+      assert(result.in1 == r1.end());
+      assert(result.in2 == r2.end());
       assert(result.out == out.end());
-      assert(std::ranges::equal(out, std::array<TracedCopy, 3>{5, 15, 16}));
+      assert(std::ranges::equal(out, std::array<TracedCopy, 2>{3, 8}));
 
       assert(std::ranges::all_of(out, &TracedCopy::copiedOnce));
     }
 
     // range overload
     {
-      std::array<TracedCopy, 3> out;
-      auto result = std::ranges::set_difference(r1, r2, out.data());
+      std::array<TracedCopy, 2> out;
+      auto result = std::ranges::set_intersection(r1, r2, out.data());
 
-      assert(result.in == r1.end());
+      assert(result.in1 == r1.end());
+      assert(result.in2 == r2.end());
       assert(result.out == out.end());
-      assert(std::ranges::equal(out, std::array<TracedCopy, 3>{5, 15, 16}));
+      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; }
   };
 
-  // equal elements should be copied in the original order and only m-n elements are copied
+  // 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, 1}, {0, 2}, {0, 3}}};
+    std::array<IntAndOrder, 3> r2{{{0, 5}, {0, 6}, {0, 7}}};
 
     // iterator overload
     {
-      std::array<IntAndOrder, 2> out;
-      std::ranges::set_difference(r1.begin(), r1.end(), r2.begin(), r2.end(), out.data());
+      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}, {}, &IntAndOrder::data));
-      // m-n elements are copied in order
-      assert(std::ranges::equal(out, std::array{3, 4}, {}, &IntAndOrder::order));
+      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, 2> out;
-      std::ranges::set_difference(r1, r2, out.data());
+      std::array<IntAndOrder, 3> out;
+      std::ranges::set_intersection(r1, r2, out.data());
 
-      assert(std::ranges::equal(out, std::array{0, 0}, {}, &IntAndOrder::data));
-      // ID should be in their original order
-      assert(std::ranges::equal(out, std::array{3, 4}, {}, &IntAndOrder::order));
+      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}};
-    using Iter1 = std::array<Data, 3>::iterator;
 
     // iterator overload
     {
-      std::array<Data, 2> out;
-      std::same_as<set_difference_result<Iter1, Data*>> decltype(auto) result = std::ranges::set_difference(
+      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{4, 12}, {}, &Data::data));
+      assert(std::ranges::equal(out, std::array{8}, {}, &Data::data));
 
-      assert(result.in == r1.end());
+      assert(result.in1 == r1.end());
+      assert(result.in2 == r2.end());
       assert(result.out == out.end());
     }
 
     // range overload
     {
-      std::array<Data, 2> out;
-      std::same_as<set_difference_result<Iter1, Data*>> decltype(auto) result =
-          std::ranges::set_difference(r1, r2, out.data(), [](const Data& x, const Data& y) { return x.data < y.data; });
+      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{4, 12}, {}, &Data::data));
+      assert(std::ranges::equal(out, std::array{8}, {}, &Data::data));
 
-      assert(result.in == r1.end());
+      assert(result.in1 == r1.end());
+      assert(result.in2 == r2.end());
       assert(result.out == out.end());
     }
 
     // member pointer Comparator iterator overload
     {
-      std::array<Data, 2> out;
-      std::same_as<set_difference_result<Iter1, Data*>> decltype(auto) result =
-          std::ranges::set_difference(r1.begin(), r1.end(), r2.begin(), r2.end(), out.data(), &Data::smallerThan);
+      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{4, 12}, {}, &Data::data));
+      assert(std::ranges::equal(out, std::array{8}, {}, &Data::data));
 
-      assert(result.in == r1.end());
+      assert(result.in1 == r1.end());
+      assert(result.in2 == r2.end());
       assert(result.out == out.end());
     }
 
     // member pointer Comparator range overload
     {
-      std::array<Data, 2> out;
-      std::same_as<set_difference_result<Iter1, Data*>> decltype(auto) result =
-          std::ranges::set_difference(r1, r2, out.data(), &Data::smallerThan);
+      std::array<Data, 1> out;
+      auto result = std::ranges::set_intersection(r1, r2, out.data(), &Data::smallerThan);
 
-      assert(std::ranges::equal(out, std::array{4, 12}, {}, &Data::data));
+      assert(std::ranges::equal(out, std::array{8}, {}, &Data::data));
 
-      assert(result.in == r1.end());
+      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{4}};
-    using Iter1 = std::array<Data, 3>::iterator;
+    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;
-      std::same_as<set_difference_result<Iter1, Data*>> decltype(auto) result = std::ranges::set_difference(
+      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{1, 5}, {}, &Data::data));
+      assert(std::ranges::equal(out, std::array{3, 5}, {}, &Data::data));
 
-      assert(result.in == r1.end());
+      assert(result.in1 == r1.end());
+      assert(result.in2 == r2.end());
       assert(result.out == out.end());
     }
 
     // range overload
     {
       std::array<Data, 2> out;
-      std::same_as<set_difference_result<Iter1, Data*>> decltype(auto) result =
-          std::ranges::set_difference(r1, r2, out.data(), std::ranges::less{}, proj, proj);
+      auto result = std::ranges::set_intersection(r1, r2, out.data(), std::ranges::less{}, proj, proj);
 
-      assert(std::ranges::equal(out, std::array{1, 5}, {}, &Data::data));
+      assert(std::ranges::equal(out, std::array{3, 5}, {}, &Data::data));
 
-      assert(result.in == r1.end());
+      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;
-      std::same_as<set_difference_result<Iter1, Data*>> decltype(auto) result = std::ranges::set_difference(
+      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{1, 5}, {}, &Data::data));
+      assert(std::ranges::equal(out, std::array{3, 5}, {}, &Data::data));
 
-      assert(result.in == r1.end());
+      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;
-      std::same_as<set_difference_result<Iter1, Data*>> decltype(auto) result =
-          std::ranges::set_difference(r1, r2, out.data(), std::ranges::less{}, &Data::data, &Data::data);
+      auto result = std::ranges::set_intersection(r1, r2, out.data(), std::ranges::less{}, &Data::data, &Data::data);
 
-      assert(std::ranges::equal(out, std::array{1, 5}, {}, &Data::data));
+      assert(std::ranges::equal(out, std::array{3, 5}, {}, &Data::data));
 
-      assert(result.in == r1.end());
+      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, 3> r1{{{4}, {8}, {12}}};
-    std::array<Data, 9> r2{{{1}, {2}, {3}, {5}, {6}, {7}, {9}, {10}, {11}}};
-    std::array expected{4, 8, 12};
+    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, 3> out;
+      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_difference(r1.begin(), r1.end(), r2.begin(), r2.end(), out.data(), comp, proj1, proj2);
+      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, 3> out;
+      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_difference(r1, r2, out.data(), comp, proj1, proj2);
+      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[] = {{2}, {4}};
+    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, 1> out;
-      std::ranges::set_difference(r1, r1 + 2, r2, r2 + 3, out.data(), comp);
-      assert(std::ranges::equal(out, std::array{2}, {}, &Data::data));
+      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, 1> out;
-      std::ranges::set_difference(r1, r2, out.data(), comp);
-      assert(std::ranges::equal(out, std::array{2}, {}, &Data::data));
+      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());
 
+  // Cannot static_assert on the entire permutation test because it exceeds the constexpr execution step limit
+  // due to the large number of combination of types of iterators (it is a 3-dimensional cartesian product)
+  // 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-dimensional cartesian product which is less 
+  // than the step limit.
   runAllIteratorPermutationsTests();
 
   return 0;
 }

libcxx/test/std/algorithms/alg.sorting/sortable_helpers.h

 #define SORTABLE_HELPERS_H
 
 #include <type_traits>
 
 #include "test_macros.h"
 
 #if TEST_STD_VER > 17
 #include <compare>
+#include <iterator>
+#include "test_iterators.h"
 #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;
constexpr TracedCopy& operator=(const TracedCopy& other) {
     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; }
 };
+
+template <class Iter>
+struct NonBorrowedRange {
+  int* data_;
+  size_t size_;
+
+  // TODO: some algorithms calls std::__copy
+  // std::__copy(contiguous_iterator<int*>, sentinel_wrapper<contiguous_iterator<int*>>, contiguous_iterator<int*>) doesn't seem to work.
+  // It seems that it 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<Iter>, Iter, sentinel_wrapper<Iter>>;
+
+  constexpr NonBorrowedRange(int* d, size_t s) : data_{d}, size_{s} {}
+
+  constexpr Iter begin() const { return Iter{data_}; };
+  constexpr Sent end() const { return Sent{Iter{data_ + size_}}; };
+};
 #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));