[libc++] Test that our algorithms never copy a user-provided comparator.

[• Quuxplusone]

Summary

This is not mandated by the standard, so it goes in libcxx/test/libcxx/.
It's certainly arguable that the algorithms changed here (is_heap, is_sorted, min, max) are harmless and we should just let them copy their comparators once. But at the same time, it's nice to have all our algorithms be 100% consistent and never copy a comparator, not even once.

P.S. — If I find the time, I'll investigate the thing I was talking about way back in D93562, where we change _Comp_ref to be a lightweight value type instead of a reference type, and then we never need to pass the explicit argument <_Comp_ref> to anything. That would be a vastly more invasive PR, touching all the algorithms; this new test would be the regression-test that we would expect to continue passing even after that invasive change.

[• Quuxplusone]

libcxx/include/__algorithm/min_element.h

47–48

In a couple of these cases I drive-by removed inline from function templates. I could put it back.
Do we think inline has any beneficial effect, these days?

$ git grep -L 'inline' ../libcxx/include/__algorithm/*.h
../libcxx/include/__algorithm/comp.h
../libcxx/include/__algorithm/half_positive.h
../libcxx/include/__algorithm/is_partitioned.h
../libcxx/include/__algorithm/partition_copy.h
../libcxx/include/__algorithm/partition_point.h
../libcxx/include/__algorithm/remove.h
../libcxx/include/__algorithm/remove_if.h
../libcxx/include/__algorithm/shuffle.h
../libcxx/include/__algorithm/sift_down.h

libcxx/test/libcxx/algorithms/robust_against_copying_comparators.pass.cpp

105

This one is different because for_each returns the comparator by move (and for UnaryVoid a move is a copy).

[ldionne]

LGTM with comments. Thanks for doing this!

libcxx/include/__algorithm/is_heap_until.h

51

We do need _LIBCPP_HIDE_FROM_ABI here and in other places.

libcxx/include/__algorithm/min_element.h

47–48

I would avoid removing it in this PR. As it happens, I've been doing the same from time to time while refactoring code, and I currently have on my plate to investigate a not insignificant code size regression we've witnessed when building our shared linker cache against a recent libc++, which I suspect is due to that based on some initial investigation.

Before we know for sure what's going on, I would not touch inline.

[ldionne]

libcxx/test/libcxx/algorithms/robust_against_copying_comparators.pass.cpp

121

When/where was TEST_IS_CONSTANT_EVALUATED introduced? I seem to have missed it, but it certainly looks weird to me.

[• Quuxplusone]

libcxx/test/libcxx/algorithms/robust_against_copying_comparators.pass.cpp

121

It came originally from D110598 (at my instigation), but ended up landing yesterday in D113906.
I already know that within 3 years we'll need something finer-grained; I suggested

#define TEST_IS_RUNTIME_OR_CXX20 ...  // for guarding code that became constexpr-friendly in '20
#define TEST_IS_RUNTIME_OR_CXX23 ...  // for guarding code that became constexpr-friendly in '23

But it'll be easy to search-and-replace this later, as soon as someone needs it, so I figure there's no rush to settle on that prematurely.

[• Quuxplusone]

libcxx/include/__algorithm/is_heap_until.h

24

This was missing _LIBCPP_HIDE_FROM_ABI; I've added it.

libcxx/include/__algorithm/is_sorted_until.h

24

This was missing _LIBCPP_HIDE_FROM_ABI; I've added it.

libcxx/include/__algorithm/min_element.h

47–48

Okay. In the new revision, I think I've added inline to all the places. That is:

• When splitting up an already-inline function (min_element) into two new functions, I keep inline on both of them.
• When splitting up a non-inline function (is_heap_until), I add inline to the smaller/public'er one and keep inline off of the larger/now-internal one.

[• Quuxplusone]

Don't remove inline; do include-what-you-use __comp_ref_type. CI should be happy now.

[nilayvaish]

libcxx/include/__algorithm/is_heap_until.h

52

Why does this need to be hidden? Also isn't this already part of the ABI?

[nilayvaish]

libcxx/include/__algorithm/is_heap_until.h

52

Found the ABI spec here: https://libcxxabi.llvm.org/spec.html. So this seems good.

[ldionne]

libcxx/include/__algorithm/is_heap_until.h

52

Just to be clear, that document only explains the functions exported by libc++abi as an implementation of the Itanium C++ ABI.

The reason for hiding is_heap_until is that we don't want it to be part of libc++'s ABI surface in any way, so we can make changes to it later.

[• Quuxplusone]

Oops, fix a copy-paste typo. Now CI should be happy!

[Mordante]

LGTM when the CI is green.

libcxx/include/__algorithm/min_element.h

47–48

I would avoid removing it in this PR. As it happens, I've been doing the same from time to time while refactoring code, and I currently have on my plate to investigate a not insignificant code size regression we've witnessed when building our shared linker cache against a recent libc++, which I suspect is due to that based on some initial investigation.

Before we know for sure what's going on, I would not touch inline.

@ldionne Interesting. Once you've finished your investigation can you share the results. I tend to omit inline for templates since it's not required.

[ldionne]

libcxx/include/__algorithm/min_element.h

47–48

Yup, I omit it too. I will definitely share the results.

[• Quuxplusone]

Aaargh. Fourth time's the charm.
(Also, GCC was complaining about the one-line if (!TEST_IS_CONSTEXPR) (void)foo(); assert(bar); so I added curly braces to them.)

[var-const]

libcxx/test/libcxx/algorithms/robust_against_copying_comparators.pass.cpp

10

Same comment re. <numeric> as the other patch.

17

Optional: consider using a mixin to reduce boilerplate:

struct CopyTracker {
  int *copies_;
  TEST_CONSTEXPR explicit CopyTracker(int *copies) : copies_(copies) {}
  TEST_CONSTEXPR CopyTracker(const CopyTracker& rhs) : copies_(rhs.copies_) { *copies_ += 1; }
};

struct Less : CopyTracker {
  TEST_CONSTEXPR explicit Less(int *copies) : CopyTracker(copies) {}
  TEST_CONSTEXPR bool operator()(void*, void*) const { return false; }
};

// ...

171

Nit: I think LLVM style guide is 80 columns. Also, this would make the assert unconditional (applies below as well).

[jloser]

libcxx/test/libcxx/algorithms/robust_against_copying_comparators.pass.cpp

54

Are you using decltype(nullptr) instead of nullptr_t because of C++03 support or something else?

171

libc++ has its own .clang-format with a ColumnLimit of 120 FWIW.

[• Quuxplusone]

libcxx/test/libcxx/algorithms/robust_against_copying_comparators.pass.cpp

10

Ack. Same answer: that it's a good idea and I should do it for all these (now three) tests but in a different PR.

17

I find "minimize layers of abstraction" to be the best rule for test code. We want to make sure that when it goes wrong, it goes wrong for the right reasons, and not [slight caricature here] because we messed up some template metaprogramming somewhere in the middle of the test. :) It's kinda the same reason I'm not a big fan of reusable helper headers.

54

Out of a completely mistaken set of beliefs that (1) Clang's C++03 mode supported decltype as an extension, (2) Clang's C++03 mode supported nullptr as an extension, (3) libc++'s C++03 mode did not define std::nullptr_t.
It turns out that Clang does not support decltype and nullptr in C++03; those are macros provided by libc++! And libc++ does provide std::nullptr_t. So I'll just switch to that. Thanks.

(In my own code I actually do use decltype(nullptr) out of laziness, because it's core-language and I can't be arsed to remember which header defines the library alias std::nullptr_t. But in this patch-series Louis has already warned me against laziness. ;))

171

Unconditional assert detected by GCC buildkite, and fixed; thanks.
Line-length ugly, but doubling the number of lines strikes me as strictly uglier, so I'm calling this fine.

[• Quuxplusone]

Fifth time's the charm? Buildkite hates me. :)
Removed decltype(nullptr) in favor of std::nullptr_t; fixed up some constexpr-friendliness.

[var-const]

libcxx/test/libcxx/algorithms/robust_against_copying_comparators.pass.cpp

171

libc++ has its own .clang-format with a ColumnLimit of 120 FWIW.

Thanks!

libcxx/include/__algorithm/binary_search.h

 //===----------------------------------------------------------------------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef _LIBCPP___ALGORITHM_BINARY_SEARCH_H
 #define _LIBCPP___ALGORITHM_BINARY_SEARCH_H
 
 #include <__config>
 #include <__algorithm/comp.h>
-#include <__algorithm/lower_bound.h>
 #include <__algorithm/comp_ref_type.h>
+#include <__algorithm/lower_bound.h>
 #include <__iterator/iterator_traits.h>
 
 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
 #pragma GCC system_header
 #endif
 
 _LIBCPP_BEGIN_NAMESPACE_STD
 

libcxx/include/__algorithm/is_heap.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_IS_HEAP_H
 #define _LIBCPP___ALGORITHM_IS_HEAP_H
 
 #include <__config>
 #include <__algorithm/comp.h>
+#include <__algorithm/comp_ref_type.h>
 #include <__algorithm/is_heap_until.h>
 #include <__iterator/iterator_traits.h>
 
 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
 #pragma GCC system_header
 #endif
 
 _LIBCPP_BEGIN_NAMESPACE_STD
 
 template <class _RandomAccessIterator, class _Compare>
 _LIBCPP_NODISCARD_EXT inline
 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
 bool
 is_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
 {
-    return _VSTD::is_heap_until(__first, __last, __comp) == __last;
+    typedef typename __comp_ref_type<_Compare>::type _Comp_ref;
+    return _VSTD::__is_heap_until<_Comp_ref>(__first, __last, __comp) == __last;
 }
 
 template<class _RandomAccessIterator>
 _LIBCPP_NODISCARD_EXT inline
 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
 bool
 is_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
 {
     return _VSTD::is_heap(__first, __last, __less<typename iterator_traits<_RandomAccessIterator>::value_type>());
 }
 
 _LIBCPP_END_NAMESPACE_STD
 
 #endif // _LIBCPP___ALGORITHM_IS_HEAP_H

libcxx/include/__algorithm/is_heap_until.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_IS_HEAP_UNTIL_H
 #define _LIBCPP___ALGORITHM_IS_HEAP_UNTIL_H
 
 #include <__config>
 #include <__algorithm/comp.h>
+#include <__algorithm/comp_ref_type.h>
 #include <__iterator/iterator_traits.h>
 
 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
 #pragma GCC system_header
 #endif
 
 _LIBCPP_BEGIN_NAMESPACE_STD
 
-template <class _RandomAccessIterator, class _Compare>
-_LIBCPP_NODISCARD_EXT _LIBCPP_CONSTEXPR_AFTER_CXX17 _RandomAccessIterator
-is_heap_until(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
+template <class _Compare, class _RandomAccessIterator>
+_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX17 _RandomAccessIterator
+__is_heap_until(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
 {
     typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type;
     difference_type __len = __last - __first;
     difference_type __p = 0;
     difference_type __c = 1;
     _RandomAccessIterator __pp = __first;
     while (__c < __len)
     {
         _RandomAccessIterator __cp = __first + __c;
         if (__comp(*__pp, *__cp))
             return __cp;
         ++__c;
         ++__cp;
         if (__c == __len)
             return __last;
         if (__comp(*__pp, *__cp))
             return __cp;
         ++__p;
         ++__pp;
         __c = 2 * __p + 1;
     }
     return __last;
 }
 
+template <class _RandomAccessIterator, class _Compare>
+_LIBCPP_NODISCARD_EXT inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX17 _RandomAccessIterator
+is_heap_until(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
+{
+    typedef typename __comp_ref_type<_Compare>::type _Comp_ref;
+    return _VSTD::__is_heap_until<_Comp_ref>(__first, __last, __comp);
+}
+
 template<class _RandomAccessIterator>
-_LIBCPP_NODISCARD_EXT inline
-_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
-_RandomAccessIterator
+_LIBCPP_NODISCARD_EXT inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX17 _RandomAccessIterator
 is_heap_until(_RandomAccessIterator __first, _RandomAccessIterator __last)
 {
-    return _VSTD::is_heap_until(__first, __last, __less<typename iterator_traits<_RandomAccessIterator>::value_type>());
+    return _VSTD::__is_heap_until(__first, __last, __less<typename iterator_traits<_RandomAccessIterator>::value_type>());
 }
 
 _LIBCPP_END_NAMESPACE_STD
 
 #endif // _LIBCPP___ALGORITHM_IS_HEAP_UNTIL_H

libcxx/include/__algorithm/is_sorted.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_IS_SORTED_H
 #define _LIBCPP___ALGORITHM_IS_SORTED_H
 
 #include <__algorithm/comp.h>
+#include <__algorithm/comp_ref_type.h>
 #include <__algorithm/is_sorted_until.h>
 #include <__config>
 #include <__iterator/iterator_traits.h>
 
 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
 #pragma GCC system_header
 #endif
 
 _LIBCPP_BEGIN_NAMESPACE_STD
 
 template <class _ForwardIterator, class _Compare>
 _LIBCPP_NODISCARD_EXT inline
 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
 bool
 is_sorted(_ForwardIterator __first, _ForwardIterator __last, _Compare __comp)
 {
-    return _VSTD::is_sorted_until(__first, __last, __comp) == __last;
+    typedef typename __comp_ref_type<_Compare>::type _Comp_ref;
+    return _VSTD::__is_sorted_until<_Comp_ref>(__first, __last, __comp) == __last;
 }
 
 template<class _ForwardIterator>
 _LIBCPP_NODISCARD_EXT inline
 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
 bool
 is_sorted(_ForwardIterator __first, _ForwardIterator __last)
 {
     return _VSTD::is_sorted(__first, __last, __less<typename iterator_traits<_ForwardIterator>::value_type>());
 }
 
 _LIBCPP_END_NAMESPACE_STD
 
 #endif // _LIBCPP___ALGORITHM_IS_SORTED_H

libcxx/include/__algorithm/is_sorted_until.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_IS_SORTED_UNTIL_H
 #define _LIBCPP___ALGORITHM_IS_SORTED_UNTIL_H
 
 #include <__config>
 #include <__algorithm/comp.h>
+#include <__algorithm/comp_ref_type.h>
 #include <__iterator/iterator_traits.h>
 
 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
 #pragma GCC system_header
 #endif
 
 _LIBCPP_BEGIN_NAMESPACE_STD
 
-template <class _ForwardIterator, class _Compare>
-_LIBCPP_NODISCARD_EXT _LIBCPP_CONSTEXPR_AFTER_CXX17 _ForwardIterator
-is_sorted_until(_ForwardIterator __first, _ForwardIterator __last, _Compare __comp)
+template <class _Compare, class _ForwardIterator>
+_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX17 _ForwardIterator
+__is_sorted_until(_ForwardIterator __first, _ForwardIterator __last, _Compare __comp)
 {
     if (__first != __last)
     {
         _ForwardIterator __i = __first;
         while (++__i != __last)
         {
             if (__comp(*__i, *__first))
                 return __i;
             __first = __i;
         }
     }
     return __last;
 }
 
+template <class _ForwardIterator, class _Compare>
+_LIBCPP_NODISCARD_EXT inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX17 _ForwardIterator
+is_sorted_until(_ForwardIterator __first, _ForwardIterator __last, _Compare __comp)
+{
+    typedef typename __comp_ref_type<_Compare>::type _Comp_ref;
+    return _VSTD::__is_sorted_until<_Comp_ref>(__first, __last, __comp);
+}
+
 template<class _ForwardIterator>
-_LIBCPP_NODISCARD_EXT inline
-_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
-_ForwardIterator
+_LIBCPP_NODISCARD_EXT inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX17 _ForwardIterator
 is_sorted_until(_ForwardIterator __first, _ForwardIterator __last)
 {
     return _VSTD::is_sorted_until(__first, __last, __less<typename iterator_traits<_ForwardIterator>::value_type>());
 }
 
 _LIBCPP_END_NAMESPACE_STD
 
 #endif // _LIBCPP___ALGORITHM_IS_SORTED_UNTIL_H

libcxx/include/__algorithm/max.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_MAX_H
 #define _LIBCPP___ALGORITHM_MAX_H
 
 #include <__config>
 #include <__algorithm/comp.h>
+#include <__algorithm/comp_ref_type.h>
 #include <__algorithm/max_element.h>
 #include <initializer_list>
 
 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
 #pragma GCC system_header
 #endif
 
 _LIBCPP_PUSH_MACROS

 #ifndef _LIBCPP_CXX03_LANG
 
 template<class _Tp, class _Compare>
 _LIBCPP_NODISCARD_EXT inline
 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
 _Tp
 max(initializer_list<_Tp> __t, _Compare __comp)
 {
-    return *_VSTD::max_element(__t.begin(), __t.end(), __comp);
+    typedef typename __comp_ref_type<_Compare>::type _Comp_ref;
+    return *_VSTD::__max_element<_Comp_ref>(__t.begin(), __t.end(), __comp);
 }
 
 template<class _Tp>
 _LIBCPP_NODISCARD_EXT inline
 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
 _Tp
 max(initializer_list<_Tp> __t)
 {

libcxx/include/__algorithm/max_element.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_MAX_ELEMENT_H
 #define _LIBCPP___ALGORITHM_MAX_ELEMENT_H
 
 #include <__config>
 #include <__algorithm/comp.h>
+#include <__algorithm/comp_ref_type.h>
 #include <__iterator/iterator_traits.h>
 
 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
 #pragma GCC system_header
 #endif
 
 _LIBCPP_BEGIN_NAMESPACE_STD
 
-template <class _ForwardIterator, class _Compare>
-_LIBCPP_NODISCARD_EXT inline
-_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
-_ForwardIterator
-max_element(_ForwardIterator __first, _ForwardIterator __last, _Compare __comp)
+template <class _Compare, class _ForwardIterator>
+inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX11 _ForwardIterator
+__max_element(_ForwardIterator __first, _ForwardIterator __last, _Compare __comp)
 {
     static_assert(__is_cpp17_forward_iterator<_ForwardIterator>::value,
         "std::max_element requires a ForwardIterator");
     if (__first != __last)
     {
         _ForwardIterator __i = __first;
         while (++__i != __last)
             if (__comp(*__first, *__i))
                 __first = __i;
     }
     return __first;
 }
 
+template <class _ForwardIterator, class _Compare>
+_LIBCPP_NODISCARD_EXT inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX11 _ForwardIterator
+max_element(_ForwardIterator __first, _ForwardIterator __last, _Compare __comp)
+{
+    typedef typename __comp_ref_type<_Compare>::type _Comp_ref;
+    return _VSTD::__max_element<_Comp_ref>(__first, __last, __comp);
+}
+
 
 template <class _ForwardIterator>
-_LIBCPP_NODISCARD_EXT inline
-_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
-_ForwardIterator
+_LIBCPP_NODISCARD_EXT inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX11 _ForwardIterator
 max_element(_ForwardIterator __first, _ForwardIterator __last)
 {
     return _VSTD::max_element(__first, __last,
               __less<typename iterator_traits<_ForwardIterator>::value_type>());
 }
 
 _LIBCPP_END_NAMESPACE_STD
 
 #endif // _LIBCPP___ALGORITHM_MAX_ELEMENT_H

libcxx/include/__algorithm/min.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_MIN_H
 #define _LIBCPP___ALGORITHM_MIN_H
 
 #include <__config>
 #include <__algorithm/comp.h>
+#include <__algorithm/comp_ref_type.h>
 #include <__algorithm/min_element.h>
 #include <initializer_list>
 
 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
 #pragma GCC system_header
 #endif
 
 _LIBCPP_PUSH_MACROS

 #ifndef _LIBCPP_CXX03_LANG
 
 template<class _Tp, class _Compare>
 _LIBCPP_NODISCARD_EXT inline
 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
 _Tp
 min(initializer_list<_Tp> __t, _Compare __comp)
 {
-    return *_VSTD::min_element(__t.begin(), __t.end(), __comp);
+    typedef typename __comp_ref_type<_Compare>::type _Comp_ref;
+    return *_VSTD::__min_element<_Comp_ref>(__t.begin(), __t.end(), __comp);
 }
 
 template<class _Tp>
 _LIBCPP_NODISCARD_EXT inline
 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
 _Tp
 min(initializer_list<_Tp> __t)
 {

libcxx/include/__algorithm/min_element.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_MIN_ELEMENT_H
 #define _LIBCPP___ALGORITHM_MIN_ELEMENT_H
 
 #include <__config>
 #include <__algorithm/comp.h>
+#include <__algorithm/comp_ref_type.h>
 #include <__iterator/iterator_traits.h>
 
 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
 #pragma GCC system_header
 #endif
 
 _LIBCPP_BEGIN_NAMESPACE_STD
 
-template <class _ForwardIterator, class _Compare>
-_LIBCPP_NODISCARD_EXT inline
-_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
-_ForwardIterator
-min_element(_ForwardIterator __first, _ForwardIterator __last, _Compare __comp)
+template <class _Compare, class _ForwardIterator>
+inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX11 _ForwardIterator
+__min_element(_ForwardIterator __first, _ForwardIterator __last, _Compare __comp)
 {
     static_assert(__is_cpp17_forward_iterator<_ForwardIterator>::value,
         "std::min_element requires a ForwardIterator");
     if (__first != __last)
     {
         _ForwardIterator __i = __first;
         while (++__i != __last)
             if (__comp(*__i, *__first))
                 __first = __i;
     }
     return __first;
 }
 
+template <class _ForwardIterator, class _Compare>
+_LIBCPP_NODISCARD_EXT inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX11 _ForwardIterator
+min_element(_ForwardIterator __first, _ForwardIterator __last, _Compare __comp)
+{
+    typedef typename __comp_ref_type<_Compare>::type _Comp_ref;
+    return _VSTD::__min_element<_Comp_ref>(__first, __last, __comp);
+}
+
 template <class _ForwardIterator>
-_LIBCPP_NODISCARD_EXT inline
-_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
-_ForwardIterator
+_LIBCPP_NODISCARD_EXT inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX11 _ForwardIterator
 min_element(_ForwardIterator __first, _ForwardIterator __last)
 {
     return _VSTD::min_element(__first, __last,
               __less<typename iterator_traits<_ForwardIterator>::value_type>());
 }
 
 _LIBCPP_END_NAMESPACE_STD
 
 #endif // _LIBCPP___ALGORITHM_MIN_ELEMENT_H

libcxx/test/libcxx/algorithms/robust_against_copying_comparators.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>
+
+#include <algorithm>
+#include <cassert>
+#include <cstddef>
+
+#include "test_macros.h"
+
+struct Less {
+    int *copies_;
+    TEST_CONSTEXPR explicit Less(int *copies) : copies_(copies) {}
+    TEST_CONSTEXPR_CXX14 Less(const Less& rhs) : copies_(rhs.copies_) { *copies_ += 1; }
+    TEST_CONSTEXPR_CXX14 Less& operator=(const Less&) = default;
+    TEST_CONSTEXPR bool operator()(void*, void*) const { return false; }
+};
+
+struct Equal {
+    int *copies_;
+    TEST_CONSTEXPR explicit Equal(int *copies) : copies_(copies) {}
+    TEST_CONSTEXPR_CXX14 Equal(const Equal& rhs) : copies_(rhs.copies_) { *copies_ += 1; }
+    TEST_CONSTEXPR_CXX14 Equal& operator=(const Equal&) = default;
+    TEST_CONSTEXPR bool operator()(void*, void*) const { return true; }
+};
+
+struct UnaryVoid {
+    int *copies_;
+    TEST_CONSTEXPR explicit UnaryVoid(int *copies) : copies_(copies) {}
+    TEST_CONSTEXPR_CXX14 UnaryVoid(const UnaryVoid& rhs) : copies_(rhs.copies_) { *copies_ += 1; }
+    TEST_CONSTEXPR_CXX14 UnaryVoid& operator=(const UnaryVoid&) = default;
+    TEST_CONSTEXPR_CXX14 void operator()(void*) const {}
+};
+
+struct UnaryTrue {
+    int *copies_;
+    TEST_CONSTEXPR explicit UnaryTrue(int *copies) : copies_(copies) {}
+    TEST_CONSTEXPR_CXX14 UnaryTrue(const UnaryTrue& rhs) : copies_(rhs.copies_) { *copies_ += 1; }
+    TEST_CONSTEXPR_CXX14 UnaryTrue& operator=(const UnaryTrue&) = default;
+    TEST_CONSTEXPR bool operator()(void*) const { return true; }
+};
+
+struct NullaryValue {
+    int *copies_;
+    TEST_CONSTEXPR explicit NullaryValue(int *copies) : copies_(copies) {}
+    TEST_CONSTEXPR_CXX14 NullaryValue(const NullaryValue& rhs) : copies_(rhs.copies_) { *copies_ += 1; }
+    TEST_CONSTEXPR_CXX14 NullaryValue& operator=(const NullaryValue&) = default;
+    TEST_CONSTEXPR std::nullptr_t operator()() const { return nullptr; }
+};
+
+struct UnaryTransform {
+    int *copies_;
+    TEST_CONSTEXPR explicit UnaryTransform(int *copies) : copies_(copies) {}
+    TEST_CONSTEXPR_CXX14 UnaryTransform(const UnaryTransform& rhs) : copies_(rhs.copies_) { *copies_ += 1; }
+    TEST_CONSTEXPR_CXX14 UnaryTransform& operator=(const UnaryTransform&) = default;
+    TEST_CONSTEXPR std::nullptr_t operator()(void*) const { return nullptr; }
+};
+
+struct BinaryTransform {
+    int *copies_;
+    TEST_CONSTEXPR explicit BinaryTransform(int *copies) : copies_(copies) {}
+    TEST_CONSTEXPR_CXX14 BinaryTransform(const BinaryTransform& rhs) : copies_(rhs.copies_) { *copies_ += 1; }
+    TEST_CONSTEXPR_CXX14 BinaryTransform& operator=(const BinaryTransform&) = default;
+    TEST_CONSTEXPR std::nullptr_t operator()(void*, void*) const { return nullptr; }
+};
+
+TEST_CONSTEXPR_CXX20 bool all_the_algorithms()
+{
+    void *a[10] = {};
+    void *b[10] = {};
+    void **first = a;
+    void **mid = a+5;
+    void **last = a+10;
+    void **first2 = b;
+    void **mid2 = b+5;
+    void **last2 = b+10;
+    void *value = nullptr;
+    int count = 1;
+
+    int copies = 0;
+    (void)std::adjacent_find(first, last, Equal(&copies)); assert(copies == 0);
+#if TEST_STD_VER >= 11
+    (void)std::all_of(first, last, UnaryTrue(&copies)); assert(copies == 0);
+    (void)std::any_of(first, last, UnaryTrue(&copies)); assert(copies == 0);
+#endif
+    (void)std::binary_search(first, last, value, Less(&copies)); assert(copies == 0);
+#if TEST_STD_VER > 17
+    (void)std::clamp(value, value, value, Less(&copies)); assert(copies == 0);
+#endif
+    (void)std::count_if(first, last, UnaryTrue(&copies)); assert(copies == 0);
+    (void)std::equal(first, last, first2, Equal(&copies)); assert(copies == 0);
+#if TEST_STD_VER > 11
+    (void)std::equal(first, last, first2, last2, Equal(&copies)); assert(copies == 0);
+#endif
+    (void)std::equal_range(first, last, value, Less(&copies)); assert(copies == 0);
+    (void)std::find_end(first, last, first2, mid2, Equal(&copies)); assert(copies == 0);
+    (void)std::find_if(first, last, UnaryTrue(&copies)); assert(copies == 0);
+    (void)std::find_if_not(first, last, UnaryTrue(&copies)); assert(copies == 0);
+    (void)std::for_each(first, last, UnaryVoid(&copies)); assert(copies == 1); copies = 0;
+#if TEST_STD_VER > 14
+    (void)std::for_each_n(first, count, UnaryVoid(&copies)); assert(copies == 0);
+#endif
+    (void)std::generate(first, last, NullaryValue(&copies)); assert(copies == 0);
+    (void)std::generate_n(first, count, NullaryValue(&copies)); assert(copies == 0);
+    (void)std::includes(first, last, first2, last2, Less(&copies)); assert(copies == 0);
+    (void)std::is_heap(first, last, Less(&copies)); assert(copies == 0);
+    (void)std::is_heap_until(first, last, Less(&copies)); assert(copies == 0);
+    (void)std::is_partitioned(first, last, UnaryTrue(&copies)); assert(copies == 0);
+    (void)std::is_permutation(first, last, first2, Equal(&copies)); assert(copies == 0);
+#if TEST_STD_VER > 11
+    (void)std::is_permutation(first, last, first2, last2, Equal(&copies)); assert(copies == 0);
+#endif
+    (void)std::is_sorted(first, last, Less(&copies)); assert(copies == 0);
+    (void)std::is_sorted_until(first, last, Less(&copies)); assert(copies == 0);
+    if (!TEST_IS_CONSTANT_EVALUATED) { (void)std::inplace_merge(first, mid, last, Less(&copies)); assert(copies == 0); }
+    (void)std::lexicographical_compare(first, last, first2, last2, Less(&copies)); assert(copies == 0);
+    // TODO: lexicographical_compare_three_way
+    (void)std::lower_bound(first, last, value, Less(&copies)); assert(copies == 0);
+    (void)std::make_heap(first, last, Less(&copies)); assert(copies == 0);
+    (void)std::max(value, value, Less(&copies)); assert(copies == 0);
+#if TEST_STD_VER >= 11
+    (void)std::max({ value, value }, Less(&copies)); assert(copies == 0);
+#endif
+    (void)std::max_element(first, last, Less(&copies)); assert(copies == 0);
+    (void)std::merge(first, mid, mid, last, first2, Less(&copies)); assert(copies == 0);
+    (void)std::min(value, value, Less(&copies)); assert(copies == 0);
+#if TEST_STD_VER >= 11
+    (void)std::min({ value, value }, Less(&copies)); assert(copies == 0);
+#endif
+    (void)std::min_element(first, last, Less(&copies)); assert(copies == 0);
+    (void)std::minmax(value, value, Less(&copies)); assert(copies == 0);
+#if TEST_STD_VER >= 11
+    (void)std::minmax({ value, value }, Less(&copies)); assert(copies == 0);
+#endif
+    (void)std::minmax_element(first, last, Less(&copies)); assert(copies == 0);
+    (void)std::mismatch(first, last, first2, Equal(&copies)); assert(copies == 0);
+#if TEST_STD_VER > 11
+    (void)std::mismatch(first, last, first2, last2, Equal(&copies)); assert(copies == 0);
+#endif
+    (void)std::next_permutation(first, last, Less(&copies)); assert(copies == 0);
+#if TEST_STD_VER >= 11
+    (void)std::none_of(first, last, UnaryTrue(&copies)); assert(copies == 0);
+#endif
+    (void)std::nth_element(first, mid, last, Less(&copies)); assert(copies == 0);
+    (void)std::partial_sort(first, mid, last, Less(&copies)); assert(copies == 0);
+    (void)std::partial_sort_copy(first, last, first2, mid2, Less(&copies)); assert(copies == 0);
+    (void)std::partition(first, last, UnaryTrue(&copies)); assert(copies == 0);
+    (void)std::partition_copy(first, last, first2, last2, UnaryTrue(&copies)); assert(copies == 0);
+    (void)std::partition_point(first, last, UnaryTrue(&copies)); assert(copies == 0);
+    (void)std::pop_heap(first, last, Less(&copies)); assert(copies == 0);
+    (void)std::prev_permutation(first, last, Less(&copies)); assert(copies == 0);
+    (void)std::push_heap(first, last, Less(&copies)); assert(copies == 0);
+    (void)std::remove_copy_if(first, last, first2, UnaryTrue(&copies)); assert(copies == 0);
+    (void)std::remove_if(first, last, UnaryTrue(&copies)); assert(copies == 0);
+    (void)std::replace_copy_if(first, last, first2, UnaryTrue(&copies), value); assert(copies == 0);
+    (void)std::replace_if(first, last, UnaryTrue(&copies), value); assert(copies == 0);
+    (void)std::search(first, last, first2, mid2, Equal(&copies)); assert(copies == 0);
+    (void)std::search_n(first, last, count, value, Equal(&copies)); assert(copies == 0);
+    (void)std::set_difference(first, mid, mid, last, first2, Less(&copies)); assert(copies == 0);
+    (void)std::set_intersection(first, mid, mid, last, first2, Less(&copies)); assert(copies == 0);
+    (void)std::set_symmetric_difference(first, mid, mid, last, first2, Less(&copies)); assert(copies == 0);
+    (void)std::set_union(first, mid, mid, last, first2, Less(&copies)); assert(copies == 0);
+    (void)std::sort(first, last, Less(&copies)); assert(copies == 0);
+    (void)std::sort_heap(first, last, Less(&copies)); assert(copies == 0);
+    if (!TEST_IS_CONSTANT_EVALUATED) { (void)std::stable_partition(first, last, UnaryTrue(&copies)); assert(copies == 0); }
+    if (!TEST_IS_CONSTANT_EVALUATED) { (void)std::stable_sort(first, last, Less(&copies)); assert(copies == 0); }
+    (void)std::transform(first, last, first2, UnaryTransform(&copies)); assert(copies == 0);
+    (void)std::transform(first, mid, mid, first2, BinaryTransform(&copies)); assert(copies == 0);
+    (void)std::unique(first, last, Equal(&copies)); assert(copies == 0);
+    (void)std::unique_copy(first, last, first2, Equal(&copies)); assert(copies == 0);
+    (void)std::upper_bound(first, last, value, Less(&copies)); assert(copies == 0);
+
+    return true;
+}
+
+int main(int, char**)
+{
+    all_the_algorithms();
+#if TEST_STD_VER > 17
+    static_assert(all_the_algorithms());
+#endif
+
+    return 0;
+}

libcxx/test/std/algorithms/robust_against_adl.compile.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>
 
 #include <algorithm>
+#include <cstddef>
 #include <functional>
 
 #include "test_macros.h"
 
 struct Incomplete;
 template<class T> struct Holder { T t; };
 
 template<class>
 struct ConvertibleToIntegral {
     TEST_CONSTEXPR operator int() const { return 1; }
 };
 
 struct Tester {
     using Element = Holder<Incomplete>*;
     Element data[10] = {};
 };
 
 struct UnaryVoid { TEST_CONSTEXPR_CXX14 void operator()(void*) const {} };
 struct UnaryTrue { TEST_CONSTEXPR bool operator()(void*) const { return true; } };
-struct NullaryValue { TEST_CONSTEXPR decltype(nullptr) operator()() const { return nullptr; } };
-struct UnaryTransform { TEST_CONSTEXPR decltype(nullptr) operator()(void*) const { return nullptr; } };
-struct BinaryTransform { TEST_CONSTEXPR decltype(nullptr) operator()(void*, void*) const { return nullptr; } };
+struct NullaryValue { TEST_CONSTEXPR std::nullptr_t operator()() const { return nullptr; } };
+struct UnaryTransform { TEST_CONSTEXPR std::nullptr_t operator()(void*) const { return nullptr; } };
+struct BinaryTransform { TEST_CONSTEXPR std::nullptr_t operator()(void*, void*) const { return nullptr; } };
 
 TEST_CONSTEXPR_CXX20 bool all_the_algorithms()
 {
     Tester t;
     Tester u;
     Holder<Incomplete> **first = t.data;
     Holder<Incomplete> **mid = t.data+5;
     Holder<Incomplete> **last = t.data+10;

libcxx/test/std/algorithms/robust_re_difference_type.compile.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>
 //   In the description of the algorithms,
 //   given an iterator a whose difference type is D,
 //   and an expression n of integer-like type other than cv D,
 //   the semantics of a + n and a - n are, respectively,
 //   those of a + D(n) and a - D(n).
 
 #include <algorithm>
+#include <cstddef>
 #include <functional>
 #include <iterator>
 
 #include "test_macros.h"
 
 // This iterator rejects expressions like (a + n) and (a - n)
 // whenever n is of any type other than difference_type.
 //
public:
     template<class X> void operator-=(X) = delete;
     template<class X> friend void operator+(PickyIterator, X) = delete;
     template<class X> friend void operator+(X, PickyIterator) = delete;
     template<class X> friend void operator-(PickyIterator, X) = delete;
 };
 
 struct UnaryVoid { TEST_CONSTEXPR_CXX14 void operator()(void*) const {} };
 struct UnaryTrue { TEST_CONSTEXPR bool operator()(void*) const { return true; } };
-struct NullaryValue { TEST_CONSTEXPR decltype(nullptr) operator()() const { return nullptr; } };
-struct UnaryTransform { TEST_CONSTEXPR decltype(nullptr) operator()(void*) const { return nullptr; } };
-struct BinaryTransform { TEST_CONSTEXPR decltype(nullptr) operator()(void*, void*) const { return nullptr; } };
+struct NullaryValue { TEST_CONSTEXPR std::nullptr_t operator()() const { return nullptr; } };
+struct UnaryTransform { TEST_CONSTEXPR std::nullptr_t operator()(void*) const { return nullptr; } };
+struct BinaryTransform { TEST_CONSTEXPR std::nullptr_t operator()(void*, void*) const { return nullptr; } };
 
 TEST_CONSTEXPR_CXX20 bool all_the_algorithms()
 {
     void *a[10] = {};
     void *b[10] = {};
     auto first = PickyIterator<void**, long>(a);
     auto mid = PickyIterator<void**, long>(a+5);
     auto last = PickyIterator<void**, long>(a+10);