[libcxx] Cast to the right `difference_type` in various algorithms

[fwolff]

Summary

Fixes PR#52151.

[• Quuxplusone]

https://en.cppreference.com/w/cpp/algorithm/ranges/find_end
http://eel.is/c++draft/alg.find.end

Notice that std::ranges::find_end is specifically specified to return an expression involving i + (last2 - first2) where i is an I1 — implying that I1 + D2 ought to be valid, even though ranges::find_end doesn't list that as a Constraint. So I'm inclined to say that the culprit here is the user's iterator type that is implicitly convertible to raw pointer; fix that, and you'll have a lot less grief as you move toward C++20.

If we pursue this PR, I think we should at least use an implicit conversion, not an explicit conversion; I trust _D1 d1 = __len2 - 1 to do-the-right-thing-or-error-out waaay more than I trust static_cast<_D1>(__len2 - 1).

Finally, this needs tests. I recommend copying the approach of libcxx/test/std/algorithms/robust_against_adl.pass.cpp: make two iterator types that play poorly together, as in the OP, and then test them against all the standard algorithms that take multiple iterator types. (This can be a compile-only test.)

[tcanens]

http://eel.is/c++draft/algorithms.requirements#13

[• Quuxplusone]

I've done my proposed testing approach in D113906. I suggest that you rebase after I've merged that, and/or just add it as a "Parent Revision" in Phabricator right now. Then, your testing strategy here can just be to uncomment all of the TODO FIXME'd lines in that test file.

[Mordante]

I also miss tests. In general when fixing a bug it would be nice to add tests based on the reported error.
In this case best follow @Quuxplusone's suggestion for the tests.

libcxx/include/__algorithm/find_end.h

101

Style nit: in general we don't use const variables in libc++.

[fwolff]

Fix the same problem in the other algorithms

[• Quuxplusone]

LGTM mod the one unnecessary diff, and indentation. (Don't trust clang-format; it likes to mess up libc++ style.)

libcxx/include/__algorithm/copy_n.h

63

Note for the record: This un-uglified name is technically OK because it's a library reserved name. We actually do the same trick in __make_heap below. If I hadn't seen that in __make_heap, I'd totally have objected to this. ;) But given the precedent, I think it's OK.

libcxx/include/__algorithm/make_heap.h

33 ↗

(On Diff #387359)

We shouldn't need to cast the 2 here — this is just plain old "integral minus integral" subtraction. We don't cast 1 on line 30, for example. So I recommend reverting this diff.

34 ↗

(On Diff #387359)

You've broken the indentation here (and various places, especially in sort.h). Please make sure to preserve the existing indentation style wherever you change code. (If it's 2-space, leave it 2-space; if it's 4-space, leave it 4-space; don't mix styles within the same function.)

[fwolff]

libcxx/include/__algorithm/make_heap.h

34 ↗

(On Diff #387359)

I've tried to, but Arcanist wouldn't let me update this revision without the clang-format changes. Is there a special option I can use to suppress this?

[• Quuxplusone]

libcxx/include/__algorithm/make_heap.h

34 ↗

(On Diff #387359)

I do think there's some arc option for that, but I don't use arc myself. I just use git show -U999 > foo.diff and then "Update Diff" in the right sidebar at the top of the page.

[fwolff]

libcxx/include/__algorithm/make_heap.h

34 ↗

(On Diff #387359)

OK. I was unsure because the "Contributing to libc++" guide says that you have to use arc for submitting patches, but then I'll just do it via "Update Diff".

[fwolff]

@Quuxplusone I think I've addressed all of your comments now.

[• Quuxplusone]

LGTM once CI is green. You'll have to rebase on the updated D113906, or just wait until it's landed (which I hope can be soon, like, tomorrow).

[Mordante]

LGTM after addressing @Quuxplusone's comments.

If you need somebody to land the patch after it's finished, then please provide "Your name <email@domain>".

libcxx/include/__algorithm/find_end.h

101

To make reviewing easier, can you mark comments as done when you've addressed them?

libcxx/include/__algorithm/make_heap.h

34 ↗

(On Diff #387359)

For libc++ we really prefer arc else the CI isn't triggered. For arc you can use --nolint or press n at all suggestions arc makes.

[• Quuxplusone]

libcxx/include/__algorithm/make_heap.h

34 ↗

(On Diff #387359)

or else the CI isn't triggered

I use plain old git diff -U999 + "Update Diff", and I'm not aware that my PRs ever fail to trigger CI. (The only thing to watch out for is sometimes if you update twice in very quick succession, the builder may get confused when it goes to pull a revision and the revision is already gone. But I assume arc would have the same problem.)

That said, yeah, arc --nolint was exactly the thing I was trying to think of.

[ldionne]

libcxx/include/__algorithm/make_heap.h

34 ↗

(On Diff #387359)

I know at some point you at least had to make sure the right tags were added to the review, otherwise CI wouldn't get triggered. And arc diff made sure this happened, but I've seen cases where manually uploaded diffs didn't have the right tags.

It's been a while since I've seen this issue, to be fair.

[Mordante]

libcxx/include/__algorithm/make_heap.h

34 ↗

(On Diff #387359)

That issue was why I switched from direct uploads to arc. I wasn't aware the issue has since been resolved.

[• Quuxplusone]

libcxx/include/__algorithm/make_heap.h

34 ↗

(On Diff #387359)

Aha. IIUC, I do this part manually too: when I upload a diff, Phab asks me questions like "what repository" ("llvm"-tab-complete: the GitHub monorepo) and "what project" ("libc++"-tab-complete) and "what reviewers" (typically "ldionne, mordante, libc++"). It would not surprise me if, when I didn't put in "libc++" for the project, it failed to trigger buildkite. But for me that's all just part of the process of uploading a diff.

[fwolff]

Rebased on rG4a8734deb7d5, so this is now ready, I think.

@Mordante Yes, I need someone to commit this for me. You can use the same name and email as in commit 738e7f1231949ec248c1d8d154783338215613d1. Thanks!

libcxx/include/__algorithm/copy_n.h

 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
 typename enable_if
 <
     __is_cpp17_random_access_iterator<_InputIterator>::value,
     _OutputIterator
 >::type
 copy_n(_InputIterator __first, _Size __orig_n, _OutputIterator __result)
 {
+    typedef typename iterator_traits<_InputIterator>::difference_type difference_type;
     typedef decltype(_VSTD::__convert_to_integral(__orig_n)) _IntegralSize;
     _IntegralSize __n = __orig_n;
-    return _VSTD::copy(__first, __first + __n, __result);
+    return _VSTD::copy(__first, __first + difference_type(__n), __result);
 }
 
 _LIBCPP_END_NAMESPACE_STD
 
 #endif // _LIBCPP___ALGORITHM_COPY_N_H

libcxx/include/__algorithm/find_end.h

while (true) {
     }
   }
 }
 
 template <class _BinaryPredicate, class _RandomAccessIterator1, class _RandomAccessIterator2>
 _LIBCPP_CONSTEXPR_AFTER_CXX11 _RandomAccessIterator1 __find_end(
     _RandomAccessIterator1 __first1, _RandomAccessIterator1 __last1, _RandomAccessIterator2 __first2,
     _RandomAccessIterator2 __last2, _BinaryPredicate __pred, random_access_iterator_tag, random_access_iterator_tag) {
+  typedef typename iterator_traits<_RandomAccessIterator1>::difference_type _D1;
+  typedef typename iterator_traits<_RandomAccessIterator2>::difference_type _D2;
   // Take advantage of knowing source and pattern lengths.  Stop short when source is smaller than pattern
-  typename iterator_traits<_RandomAccessIterator2>::difference_type __len2 = __last2 - __first2;
+  _D2 __len2 = __last2 - __first2;
   if (__len2 == 0)
     return __last1;
-  typename iterator_traits<_RandomAccessIterator1>::difference_type __len1 = __last1 - __first1;
+  _D1 __len1 = __last1 - __first1;
   if (__len1 < __len2)
     return __last1;
-  const _RandomAccessIterator1 __s = __first1 + (__len2 - 1); // End of pattern match can't go before here
+  const _RandomAccessIterator1 __s = __first1 + _D1(__len2 - 1); // End of pattern match can't go before here
   _RandomAccessIterator1 __l1 = __last1;
   _RandomAccessIterator2 __l2 = __last2;
   --__l2;
   while (true) {
     while (true) {
       if (__s == __l1)
         return __last1;
       if (__pred(*--__l1, *__l2))

libcxx/include/__algorithm/search.h

__search(_RandomAccessIterator1 __first1, _RandomAccessIterator1 __last1, _RandomAccessIterator2 __first2,
   typedef typename iterator_traits<_RandomAccessIterator2>::difference_type _D2;
   // Take advantage of knowing source and pattern lengths.  Stop short when source is smaller than pattern
   const _D2 __len2 = __last2 - __first2;
   if (__len2 == 0)
     return _VSTD::make_pair(__first1, __first1);
   const _D1 __len1 = __last1 - __first1;
   if (__len1 < __len2)
     return _VSTD::make_pair(__last1, __last1);
-  const _RandomAccessIterator1 __s = __last1 - (__len2 - 1); // Start of pattern match can't go beyond here
+  const _RandomAccessIterator1 __s = __last1 - _D1(__len2 - 1); // Start of pattern match can't go beyond here
 
   while (true) {
     while (true) {
       if (__first1 == __s)
         return _VSTD::make_pair(__last1, __last1);
       if (__pred(*__first1, *__first2))
         break;
       ++__first1;
     }
 
     _RandomAccessIterator1 __m1 = __first1;
     _RandomAccessIterator2 __m2 = __first2;
     while (true) {
       if (++__m2 == __last2)
-        return _VSTD::make_pair(__first1, __first1 + __len2);
+        return _VSTD::make_pair(__first1, __first1 + _D1(__len2));
       ++__m1; // no need to check range on __m1 because __s guarantees we have enough source
       if (!__pred(*__m1, *__m2)) {
         ++__first1;
         break;
       }
     }
   }
 }

libcxx/include/__algorithm/search_n.h

_LIBCPP_CONSTEXPR_AFTER_CXX17 _ForwardIterator __search_n(_ForwardIterator __first, _ForwardIterator __last,
   }
 }
 
 template <class _BinaryPredicate, class _RandomAccessIterator, class _Size, class _Tp>
 _LIBCPP_CONSTEXPR_AFTER_CXX17 _RandomAccessIterator __search_n(_RandomAccessIterator __first,
                                                                _RandomAccessIterator __last, _Size __count,
                                                                const _Tp& __value_, _BinaryPredicate __pred,
                                                                random_access_iterator_tag) {
+  typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type;
   if (__count <= 0)
     return __first;
   _Size __len = static_cast<_Size>(__last - __first);
   if (__len < __count)
     return __last;
-  const _RandomAccessIterator __s = __last - (__count - 1); // Start of pattern match can't go beyond here
+  const _RandomAccessIterator __s = __last - difference_type(__count - 1); // Start of pattern match can't go beyond here
   while (true) {
     // Find first element in sequence that matchs __value_, with a mininum of loop checks
     while (true) {
       if (__first >= __s) // return __last if no element matches __value_
         return __last;
       if (__pred(*__first, __value_))
         break;
       ++__first;

libcxx/include/__algorithm/sift_down.h

__sift_down(_RandomAccessIterator __first, _RandomAccessIterator /*__last*/,
     difference_type __child = __start - __first;
 
     if (__len < 2 || (__len - 2) / 2 < __child)
         return;
 
     __child = 2 * __child + 1;
     _RandomAccessIterator __child_i = __first + __child;
 
-    if ((__child + 1) < __len && __comp(*__child_i, *(__child_i + 1))) {
+    if ((__child + 1) < __len && __comp(*__child_i, *(__child_i + difference_type(1)))) {
         // right-child exists and is greater than left-child
         ++__child_i;
         ++__child;
     }
 
     // check if we are in heap-order
     if (__comp(*__child_i, *__start))
         // we are, __start is larger than it's largest child
         return;
 
     value_type __top(_VSTD::move(*__start));
     do
     {
         // we are not in heap-order, swap the parent with its largest child
         *__start = _VSTD::move(*__child_i);
         __start = __child_i;
 
         if ((__len - 2) / 2 < __child)
             break;
 
         // recompute the child based off of the updated parent
         __child = 2 * __child + 1;
         __child_i = __first + __child;
 
-        if ((__child + 1) < __len && __comp(*__child_i, *(__child_i + 1))) {
+        if ((__child + 1) < __len && __comp(*__child_i, *(__child_i + difference_type(1)))) {
             // right-child exists and is greater than left-child
             ++__child_i;
             ++__child;
         }
 
         // check if we are in heap-order
     } while (!__comp(*__child_i, __top));
     *__start = _VSTD::move(__top);
 }
 
 _LIBCPP_END_NAMESPACE_STD
 
 #endif // _LIBCPP___ALGORITHM_SIFT_DOWN_H

libcxx/include/__algorithm/sort.h

if (__first != __last)
         }
     }
 }
 
 template <class _Compare, class _RandomAccessIterator>
 void
 __insertion_sort_3(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
 {
+    typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type;
     typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type;
-    _RandomAccessIterator __j = __first+2;
-    _VSTD::__sort3<_Compare>(__first, __first+1, __j, __comp);
-    for (_RandomAccessIterator __i = __j+1; __i != __last; ++__i)
+    _RandomAccessIterator __j = __first+difference_type(2);
+    _VSTD::__sort3<_Compare>(__first, __first+difference_type(1), __j, __comp);
+    for (_RandomAccessIterator __i = __j+difference_type(1); __i != __last; ++__i)
     {
         if (__comp(*__i, *__j))
         {
             value_type __t(_VSTD::move(*__i));
             _RandomAccessIterator __k = __j;
             __j = __i;
             do
             {
                 *__j = _VSTD::move(*__k);
                 __j = __k;
             } while (__j != __first && __comp(__t, *--__k));
             *__j = _VSTD::move(__t);
         }
         __j = __i;
     }
 }
 
 template <class _Compare, class _RandomAccessIterator>
 bool
 __insertion_sort_incomplete(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
 {
+    typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type;
     switch (__last - __first)
     {
     case 0:
     case 1:
         return true;
     case 2:
         if (__comp(*--__last, *__first))
             swap(*__first, *__last);
         return true;
     case 3:
-        _VSTD::__sort3<_Compare>(__first, __first+1, --__last, __comp);
+        _VSTD::__sort3<_Compare>(__first, __first+difference_type(1), --__last, __comp);
         return true;
     case 4:
-        _VSTD::__sort4<_Compare>(__first, __first+1, __first+2, --__last, __comp);
+        _VSTD::__sort4<_Compare>(__first, __first+difference_type(1), __first+difference_type(2), --__last, __comp);
         return true;
     case 5:
-        _VSTD::__sort5<_Compare>(__first, __first+1, __first+2, __first+3, --__last, __comp);
+        _VSTD::__sort5<_Compare>(__first, __first+difference_type(1), __first+difference_type(2), __first+difference_type(3), --__last, __comp);
         return true;
     }
     typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type;
-    _RandomAccessIterator __j = __first+2;
-    _VSTD::__sort3<_Compare>(__first, __first+1, __j, __comp);
+    _RandomAccessIterator __j = __first+difference_type(2);
+    _VSTD::__sort3<_Compare>(__first, __first+difference_type(1), __j, __comp);
     const unsigned __limit = 8;
     unsigned __count = 0;
-    for (_RandomAccessIterator __i = __j+1; __i != __last; ++__i)
+    for (_RandomAccessIterator __i = __j+difference_type(1); __i != __last; ++__i)
     {
         if (__comp(*__i, *__j))
         {
             value_type __t(_VSTD::move(*__i));
             _RandomAccessIterator __k = __j;
             __j = __i;
             do
             {
__restart:
         case 0:
         case 1:
             return;
         case 2:
             if (__comp(*--__last, *__first))
                 swap(*__first, *__last);
             return;
         case 3:
-            _VSTD::__sort3<_Compare>(__first, __first+1, --__last, __comp);
+            _VSTD::__sort3<_Compare>(__first, __first+difference_type(1), --__last, __comp);
             return;
         case 4:
-            _VSTD::__sort4<_Compare>(__first, __first+1, __first+2, --__last, __comp);
+            _VSTD::__sort4<_Compare>(__first, __first+difference_type(1), __first+difference_type(2), --__last, __comp);
             return;
         case 5:
-            _VSTD::__sort5<_Compare>(__first, __first+1, __first+2, __first+3, --__last, __comp);
+            _VSTD::__sort5<_Compare>(__first, __first+difference_type(1), __first+difference_type(2), __first+difference_type(3), --__last, __comp);
             return;
         }
         if (__len <= __limit)
         {
             _VSTD::__insertion_sort_3<_Compare>(__first, __last, __comp);
             return;
         }
         // __len > 5
__restart:
             swap(*__i, *__m);
             ++__n_swaps;
         }
         // [__first, __i) < *__i and *__i <= [__i+1, __last)
         // If we were given a perfect partition, see if insertion sort is quick...
         if (__n_swaps == 0)
         {
             bool __fs = _VSTD::__insertion_sort_incomplete<_Compare>(__first, __i, __comp);
-            if (_VSTD::__insertion_sort_incomplete<_Compare>(__i+1, __last, __comp))
+            if (_VSTD::__insertion_sort_incomplete<_Compare>(__i+difference_type(1), __last, __comp))
             {
                 if (__fs)
                     return;
                 __last = __i;
                 continue;
             }
             else
             {
                 if (__fs)
                 {
                     __first = ++__i;
                     continue;
                 }
             }
         }
         // sort smaller range with recursive call and larger with tail recursion elimination
         if (__i - __first < __last - __i)
         {
           _VSTD::__introsort<_Compare>(__first, __i, __comp, __depth);
           __first = ++__i;
         }
         else
         {
-          _VSTD::__introsort<_Compare>(__i + 1, __last, __comp, __depth);
+          _VSTD::__introsort<_Compare>(__i + difference_type(1), __last, __comp, __depth);
           __last = __i;
         }
     }
 }
 
 template <typename _Number>
 inline _LIBCPP_HIDE_FROM_ABI _Number __log2i(_Number __n) {
   _Number __log2 = 0;

libcxx/test/std/algorithms/robust_re_difference_type.compile.pass.cpp

 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);
     auto first2 = PickyIterator<void**, long long>(b);
+    auto mid2 = PickyIterator<void**, long long>(b+5);
     auto last2 = PickyIterator<void**, long long>(b+10);
     void *value = nullptr;
     int count = 1;
 
     (void)std::adjacent_find(first, last);
     (void)std::adjacent_find(first, last, std::equal_to<void*>());
 #if TEST_STD_VER >= 11
     (void)std::all_of(first, last, UnaryTrue());
     (void)std::any_of(first, last, UnaryTrue());
 #endif
     (void)std::binary_search(first, last, value);
     (void)std::binary_search(first, last, value, std::less<void*>());
 #if TEST_STD_VER > 17
     (void)std::clamp(value, value, value);
     (void)std::clamp(value, value, value, std::less<void*>());
 #endif
     (void)std::copy(first, last, first2);
     (void)std::copy_backward(first, last, last2);
-    // TODO FIXME (void)std::copy_n(first, count, first2);
+    (void)std::copy_n(first, count, first2);
     (void)std::count(first, last, value);
     (void)std::count_if(first, last, UnaryTrue());
     (void)std::distance(first, last);
     (void)std::equal(first, last, first2);
     (void)std::equal(first, last, first2, std::equal_to<void*>());
 #if TEST_STD_VER > 11
     (void)std::equal(first, last, first2, last2);
     (void)std::equal(first, last, first2, last2, std::equal_to<void*>());
 #endif
     (void)std::equal_range(first, last, value);
     (void)std::equal_range(first, last, value, std::less<void*>());
     (void)std::fill(first, last, value);
     (void)std::fill_n(first, count, value);
     (void)std::find(first, last, value);
-    // TODO FIXME (void)std::find_end(first, last, first2, mid2);
-    // TODO FIXME (void)std::find_end(first, last, first2, mid2, std::equal_to<void*>());
+    (void)std::find_end(first, last, first2, mid2);
+    (void)std::find_end(first, last, first2, mid2, std::equal_to<void*>());
     (void)std::find_if(first, last, UnaryTrue());
     (void)std::find_if_not(first, last, UnaryTrue());
     (void)std::for_each(first, last, UnaryVoid());
 #if TEST_STD_VER > 14
     (void)std::for_each_n(first, count, UnaryVoid());
 #endif
     (void)std::generate(first, last, NullaryValue());
     (void)std::generate_n(first, count, NullaryValue());
#endif
     if (!TEST_IS_CONSTANT_EVALUATED) (void)std::inplace_merge(first, mid, last);
     if (!TEST_IS_CONSTANT_EVALUATED) (void)std::inplace_merge(first, mid, last, std::less<void*>());
     (void)std::iter_swap(first, mid);
     (void)std::lexicographical_compare(first, last, first2, last2);
     (void)std::lexicographical_compare(first, last, first2, last2, std::less<void*>());
     // TODO: lexicographical_compare_three_way
     (void)std::lower_bound(first, last, value);
     (void)std::lower_bound(first, last, value, std::less<void*>());
-    // TODO FIXME (void)std::make_heap(first, last);
-    // TODO FIXME (void)std::make_heap(first, last, std::less<void*>());
+    (void)std::make_heap(first, last);
+    (void)std::make_heap(first, last, std::less<void*>());
     (void)std::max(value, value);
     (void)std::max(value, value, std::less<void*>());
 #if TEST_STD_VER >= 11
     (void)std::max({ value, value });
     (void)std::max({ value, value }, std::less<void*>());
 #endif
     (void)std::max_element(first, last);
     (void)std::max_element(first, last, std::less<void*>());

 #endif
     (void)std::move(first, last, first2);
     (void)std::move_backward(first, last, last2);
     (void)std::next_permutation(first, last);
     (void)std::next_permutation(first, last, std::less<void*>());
     (void)std::none_of(first, last, UnaryTrue());
     (void)std::nth_element(first, mid, last);
     (void)std::nth_element(first, mid, last, std::less<void*>());
-    // TODO FIXME (void)std::partial_sort(first, mid, last);
-    // TODO FIXME (void)std::partial_sort(first, mid, last, std::less<void*>());
-    // TODO FIXME (void)std::partial_sort_copy(first, last, first2, mid2);
-    // TODO FIXME (void)std::partial_sort_copy(first, last, first2, mid2, std::less<void*>());
+    (void)std::partial_sort(first, mid, last);
+    (void)std::partial_sort(first, mid, last, std::less<void*>());
+    (void)std::partial_sort_copy(first, last, first2, mid2);
+    (void)std::partial_sort_copy(first, last, first2, mid2, std::less<void*>());
     (void)std::partition(first, last, UnaryTrue());
     (void)std::partition_copy(first, last, first2, last2, UnaryTrue());
     (void)std::partition_point(first, last, UnaryTrue());
-    // TODO FIXME (void)std::pop_heap(first, last);
-    // TODO FIXME (void)std::pop_heap(first, last, std::less<void*>());
+    (void)std::pop_heap(first, last);
+    (void)std::pop_heap(first, last, std::less<void*>());
     (void)std::prev_permutation(first, last);
     (void)std::prev_permutation(first, last, std::less<void*>());
     (void)std::push_heap(first, last);
     (void)std::push_heap(first, last, std::less<void*>());
     (void)std::remove(first, last, value);
     (void)std::remove_copy(first, last, first2, value);
     (void)std::remove_copy_if(first, last, first2, UnaryTrue());
     (void)std::remove_if(first, last, UnaryTrue());
     (void)std::replace(first, last, value, value);
     (void)std::replace_copy(first, last, first2, value, value);
     (void)std::replace_copy_if(first, last, first2, UnaryTrue(), value);
     (void)std::replace_if(first, last, UnaryTrue(), value);
     (void)std::reverse(first, last);
     (void)std::reverse_copy(first, last, first2);
     (void)std::rotate(first, mid, last);
     (void)std::rotate_copy(first, mid, last, first2);
-    // TODO FIXME (void)std::search(first, last, first2, mid2);
-    // TODO FIXME (void)std::search(first, last, first2, mid2, std::equal_to<void*>());
-    // TODO FIXME (void)std::search_n(first, last, count, value);
-    // TODO FIXME (void)std::search_n(first, last, count, value, std::equal_to<void*>());
+    (void)std::search(first, last, first2, mid2);
+    (void)std::search(first, last, first2, mid2, std::equal_to<void*>());
+    (void)std::search_n(first, last, count, value);
+    (void)std::search_n(first, last, count, value, std::equal_to<void*>());
     (void)std::set_difference(first, mid, mid, last, first2);
     (void)std::set_difference(first, mid, mid, last, first2, std::less<void*>());
     (void)std::set_intersection(first, mid, mid, last, first2);
     (void)std::set_intersection(first, mid, mid, last, first2, std::less<void*>());
     (void)std::set_symmetric_difference(first, mid, mid, last, first2);
     (void)std::set_symmetric_difference(first, mid, mid, last, first2, std::less<void*>());
     (void)std::set_union(first, mid, mid, last, first2);
     (void)std::set_union(first, mid, mid, last, first2, std::less<void*>());
 #if TEST_STD_VER > 17
     (void)std::shift_left(first, last, count);
     (void)std::shift_right(first, last, count);
 #endif
-    // TODO FIXME (void)std::sort(first, last);
-    // TODO FIXME (void)std::sort(first, last, std::less<void*>());
-    // TODO FIXME (void)std::sort_heap(first, last);
-    // TODO FIXME (void)std::sort_heap(first, last, std::less<void*>());
+    (void)std::sort(first, last);
+    (void)std::sort(first, last, std::less<void*>());
+    (void)std::sort_heap(first, last);
+    (void)std::sort_heap(first, last, std::less<void*>());
     if (!TEST_IS_CONSTANT_EVALUATED) (void)std::stable_partition(first, last, UnaryTrue());
     if (!TEST_IS_CONSTANT_EVALUATED) (void)std::stable_sort(first, last);
     if (!TEST_IS_CONSTANT_EVALUATED) (void)std::stable_sort(first, last, std::less<void*>());
     (void)std::swap_ranges(first, last, first2);
     (void)std::transform(first, last, first2, UnaryTransform());
     (void)std::transform(first, mid, mid, first2, BinaryTransform());
     (void)std::unique(first, last);
     (void)std::unique(first, last, std::equal_to<void*>());