[libc++] `<algorithm>`: `ranges::minmax` should dereference iterators only once

[fsb4000]

Summary

In https://reviews.llvm.org/D135248 libcxx/test/std/algorithms/alg.sorting/alg.min.max/ranges.minmax.pass.cpp failed because move_iterator became random_access_iterator and ranges::minmax now chooses this branch.
We can't do *__result.first twice because move_iterator will move the value after the first dereference.

This is basically the same bug as I found in MS STL two days ago: https://github.com/microsoft/STL/pull/3366

[philnik]

libcxx/include/__algorithm/ranges_minmax.h

81

IMO we should special-case the one element case here instead. In no other case will the first and second iterator point to the same element.

82

You have to add a regression test for this.

[fsb4000]

@philnik

You have to add a regression test for this.

We have a test for this.

{
    // check that the range_access iterator isn't moved from multiple times
    std::shared_ptr<int> a[] = { std::make_shared<int>(42) };
    auto range = std::ranges::subrange(std::move_iterator(a), std::move_iterator(a + 1));
    auto [min, max] = std::ranges::minmax(range);
    assert(a[0] == nullptr);
    assert(min != nullptr);
    assert(max == min);
  }

after std::move_iterator will become a range access iterator. But I've added a test for input_move_iterator not to lose testing the else branch in the algorithm range::minmax.

IMO we should special-case the one element case here instead.

Maybe I misunderstood but we not always can call ranges::size to find out that range size is one but we always can check equality iterators...

[fsb4000]

Remove an unneeded move.

[fsb4000]

add std:::

[fsb4000]

TIMEOUT: apple-libc++-backdeployment.cfg.in :: std/thread/thread.condition/notify_all_at_thread_exit_lwg3343.pass.cpp (8020 of 8020)
******************** TEST 'apple-libc++-backdeployment.cfg.in :: std/thread/thread.condition/notify_all_at_thread_exit_lwg3343.pass.cpp' FAILED

Try to rerun CI.

[fsb4000]

clang-format

[fsb4000]

I've created https://github.com/llvm/llvm-project/issues/60449 and https://github.com/llvm/llvm-project/issues/60450

[fsb4000]

rebase + change if constexpr condition

[fsb4000]

range_reference_t

[fsb4000]

clarify comment

[fsb4000]

@philnik

@CaseyCarter after review my MS PR suggested that you (@philnik) had suggested me before

How do folks feel about a different approach (https://github.com/fsb4000/STL/compare/fix2900...CaseyCarter:STL:minmax) that detects the problem case "for free" by unrolling the first loop iteration? (Bugfix aside, this feels like a cleaner implementation of minmax by avoiding codeshare with minmax_element.) (Note that the maximum and minimum element can only be the same when the range has a single element.)

I will update this patch later when we finish with the MS PR to the final version of that PR.

[fsb4000]

based on https://github.com/microsoft/STL/pull/3384

[fsb4000]

clang-format

[fsb4000]

try to fix tests

[fsb4000]

try again

[fsb4000]

Because "The machines hosting the AIX libc++ pre-commit CI workers will be down for maintenance for a couple of hours over the weekend. We expect everything to be back online by Monday"
I think this patch is ready for review.

[philnik]

libcxx/include/__algorithm/ranges_minmax.h

129–131

These should either be static_asserts or simply not exist at all.

133

This has been asserted already, there is no need to check it twice.

135

I think this should use iter_value_t.

140

What are these static_casts for?

149

Why are you effectively re-implementing minmax_element here?

libcxx/test/std/algorithms/alg.sorting/alg.min.max/ranges.minmax.pass.cpp

337

Couldn't you use a cpp20_input_iterator<std::move_iterator<std::string>>? That would make this test constexpr-compatible and avoid implementing another iterator.

[fsb4000]

applying code review's suggestions.

[fsb4000]

libcxx/include/__algorithm/ranges_minmax.h

140

MS STL uses the static_casts. I used for consistency with MS STL. I asked them why the static_cast are needed and I added more static_casts here. After their answer and if the static_casts are optionally needed I could remove them.

149

To implement special-case the one element case without adding an addional if.

Ok, I try another approach.

[fsb4000]

clang-format

[fsb4000]

fix tests

[fsb4000]

add constexpr test

[fsb4000]

format

[fsb4000]

I renamed the variable for consistency with other tests.

[fsb4000]

libcxx/include/__algorithm/ranges_minmax.h

140

Casey answered me:
indirectly_copyable_storable<_It, _ValueT*> (https://eel.is/c++draft/alg.req.ind.copy#2) requires that _ValueT is copyable, but the reference type of the input range (and _It) isn't necessarily const _ValueT& so we don't have the same guarantee of implicit convertibility. In fact there's no requirement on that algorithm that lets us implicitly convert the result of an iterator dereference to _ValueT. There is a requirement that constructible_from<_ValueT, iter_reference_t<_It>> holds, however, so we can perform the conversion explicitly with static_cast.

https://github.com/microsoft/STL/pull/3384#discussion_r1099671173

[philnik]

libcxx/include/__algorithm/ranges_minmax.h

86–87

90

I think this comment is more confusing than helpful TBH.

140

IMO we should add them in another patch then, since this should be checked for all algorithms (most return an iterator, so there shouldn't be many cases) and tested. Could you open an issue for this so we don't forget?

[fsb4000]

I changed comments, removed static_casts, used ranges::next instead of ++

I created an issue https://github.com/llvm/llvm-project/issues/60680

libcxx/include/__algorithm/ranges_minmax.h

90

I changed these comments.

140

OK

[fsb4000]

added #include <__iterator/next.h>

[fsb4000]

reordered includes

[philnik]

LGTM % test comment.

libcxx/include/__algorithm/ranges_minmax.h

90

WDYT?

libcxx/test/std/algorithms/alg.sorting/alg.min.max/ranges.minmax.pass.cpp

372–389

Could you remove this and instead use the constexpr test case with forward_iterators, so the we actually test for the bug now, instead of waiting for move_iterator to be random-access?

[fsb4000]

rebased, changed the comments, changed the test

[fsb4000]

clang-format

[fsb4000]

This comment was removed by fsb4000.

[fsb4000]

typo

libcxx/include/__algorithm/ranges_minmax.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_MINMAX_H
 #define _LIBCPP___ALGORITHM_RANGES_MINMAX_H
 
 #include <__algorithm/min_max_result.h>
 #include <__algorithm/minmax_element.h>
 #include <__assert>
 #include <__concepts/copyable.h>
+#include <__concepts/swappable.h>
 #include <__config>
 #include <__functional/identity.h>
 #include <__functional/invoke.h>
 #include <__functional/ranges_operations.h>
 #include <__iterator/concepts.h>
+#include <__iterator/iterator_traits.h>
 #include <__iterator/projected.h>
 #include <__ranges/access.h>
 #include <__ranges/concepts.h>
 #include <__utility/forward.h>
 #include <__utility/move.h>
 #include <__utility/pair.h>
 #include <initializer_list>
 
struct __fn {
   ranges::minmax_result<range_value_t<_Range>> operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {}) const {
     auto __first = ranges::begin(__r);
     auto __last = ranges::end(__r);
     using _ValueT = range_value_t<_Range>;
 
     _LIBCPP_ASSERT(__first != __last, "range has to contain at least one element");
 
     if constexpr (forward_range<_Range>) {
-      auto __result = std::__minmax_element_impl(__first, __last, __comp, __proj);
-      return {*__result.first, *__result.second};
+      return __minmax_fwd_unchecked(__first, __last, __comp, __proj);
     } else {
       // input_iterators can't be copied, so the implementation for input_iterators has to store
       // the values instead of a pointer to the correct values
       auto __less = [&](auto&& __a, auto&& __b) -> bool {
         return std::invoke(__comp, std::invoke(__proj, std::forward<decltype(__a)>(__a)),
                                    std::invoke(__proj, std::forward<decltype(__b)>(__b)));
       };
 
       ranges::minmax_result<_ValueT> __result = {*__first, __result.min};
       if (__first == __last || ++__first == __last)
         return __result;
 
       if (__less(*__first, __result.min))
         __result.min = *__first;
       else
         __result.max = *__first;
 
if constexpr (forward_range<_Range>) {
             __result.min = std::move(__i);
           if (!__less(*__first, __result.max))
             __result.max = *__first;
         }
       }
       return __result;
     }
   }
+
+private:
+  template <class _It, class _Se, class _Pr, class _Pj>
+  [[nodiscard]] static constexpr minmax_result<__iter_value_type<_It>>
+  __minmax_fwd_unchecked(_It __first, const _Se __last, _Pr& __pred, _Pj& __proj) {
+    _LIBCPP_ASSERT(forward_iterator<_It>, "_It must be forward_iterator");
+    _LIBCPP_ASSERT((sentinel_for<_Se, _It>), "_Se must be sentinel for _It");
+    _LIBCPP_ASSERT((indirect_strict_weak_order<_Pr, projected<_It, _Pj>>), "");
+
+    _LIBCPP_ASSERT(__first != __last, "range has to contain at least one element");
+
+    using _ValueT = __iter_value_type<_It>;
+
+    auto __found_min = __first;
+    if (++__first == __last) {
+      // This initialization is correct, similar to the N4928 [dcl.init.aggr]/6 example
+      minmax_result<_ValueT> __result = {static_cast<_ValueT>(*__found_min), __result.min};
+      return __result;
+    }
+
+    auto __found_max = __first;
+    if (std::invoke(__pred, std::invoke(__proj, *__found_max), std::invoke(__proj, *__found_min))) {
+      ranges::swap(__found_min, __found_max);
+    }
+
+    while (++__first != __last) { // process one or two elements
+      _It __prev = __first;
+      if (++__first == __last) { // process last element
+        if (std::invoke(__pred, std::invoke(__proj, *__prev), std::invoke(__proj, *__found_min))) {
+          __found_min = __prev;
+        } else if (!std::invoke(__pred, std::invoke(__proj, *__prev), std::invoke(__proj, *__found_max))) {
+          __found_max = __prev;
+        }
+
+        break;
+      }
+
+      // process two elements
+      if (std::invoke(__pred, std::invoke(__proj, *__first), std::invoke(__proj, *__prev))) {
+        // test __first for new smallest
+        if (std::invoke(__pred, std::invoke(__proj, *__first), std::invoke(__proj, *__found_min))) {
+          __found_min = __first;
+        }
+
+        if (!std::invoke(__pred, std::invoke(__proj, *__prev), std::invoke(__proj, *__found_max))) {
+          __found_max = __prev;
+        }
+      } else { // test __prev for new smallest
+        if (std::invoke(__pred, std::invoke(__proj, *__prev), std::invoke(__proj, *__found_min))) {
+          __found_min = __prev;
+        }
+
+        if (!std::invoke(__pred, std::invoke(__proj, *__first), std::invoke(__proj, *__found_max))) {
+          __found_max = __first;
+        }
+      }
+    }
+
+    return {static_cast<_ValueT>(*__found_min), static_cast<_ValueT>(*__found_max)};
+  }
 };
 } // namespace __minmax
 
 inline namespace __cpo {
   inline constexpr auto minmax = __minmax::__fn{};
 } // namespace __cpo
 } // namespace ranges
 
 _LIBCPP_END_NAMESPACE_STD
 
 _LIBCPP_POP_MACROS
 
 #endif // _LIBCPP_STD_VER > 17
 
 #endif // _LIBCPP___ALGORITHM_RANGES_MINMAX_H

libcxx/test/std/algorithms/alg.sorting/alg.min.max/ranges.minmax.pass.cpp

 constexpr bool test() {
   test_2_arguments();
   test_initializer_list();
   test_range();
 
   return true;
 }
 
+class input_move_iterator {
+public:
+  using iterator_category = std::input_iterator_tag;
+  using iterator_concept  = std::input_iterator_tag;
+  using difference_type   = std::ptrdiff_t;
+  using value_type        = std::shared_ptr<int>;
+  using pointer           = std::shared_ptr<int>*;
+  using reference         = std::shared_ptr<int>&&;
+
+  input_move_iterator() = default;
+  explicit input_move_iterator(std::shared_ptr<int>* ptr) : m_ptr(ptr) {}
+
+  reference operator*() const { return std::ranges::iter_move(m_ptr); }
+  pointer operator->() const { return m_ptr; }
+
+  input_move_iterator& operator++() {
+    ++m_ptr;
+    return *this;
+  }
+  input_move_iterator operator++(int) {
+    input_move_iterator tmp = *this;
+    ++*this;
+    return tmp;
+  }
+
+  friend bool operator==(const input_move_iterator&, const input_move_iterator&) = default;
+
+private:
+  std::shared_ptr<int>* m_ptr{nullptr};
+};
+
 int main(int, char**) {
   test();
   static_assert(test());
 
   {
-    // check that the iterator isn't moved from multiple times
+    // check that the random access iterator isn't moved from multiple times
     std::shared_ptr<int> a[] = { std::make_shared<int>(42) };
     auto range = std::ranges::subrange(std::move_iterator(a), std::move_iterator(a + 1));
     auto [min, max] = std::ranges::minmax(range);
     assert(a[0] == nullptr);
     assert(min != nullptr);
     assert(max == min);
   }
+  {
+    // check that the input iterator isn't moved from multiple times
+    std::shared_ptr<int> a[] = {std::make_shared<int>(42)};
+    auto range               = std::ranges::subrange(input_move_iterator(a), input_move_iterator(a + 1));
+    auto [min, max]          = std::ranges::minmax(range);
+    assert(a[0] == nullptr);
+    assert(min != nullptr);
+    assert(max == min);
+  }
 
   return 0;
 }