[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

94

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.

95

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

144–146

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

148

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

150

I think this should use iter_value_t.

155

What are these static_casts for?

164

Why are you effectively re-implementing minmax_element here?

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

358

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

155

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.

164

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

155

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

105

I think this comment is more confusing than helpful TBH.

155

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

105

I changed these comments.

155

OK

[fsb4000]

added #include <__iterator/next.h>

[fsb4000]

reordered includes

[philnik]

LGTM % test comment.

libcxx/include/__algorithm/ranges_minmax.h

103

WDYT?

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

361–362

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/same_as.h>
 #include <__config>
 #include <__functional/identity.h>
 #include <__functional/invoke.h>
 #include <__functional/ranges_operations.h>
 #include <__iterator/concepts.h>
+#include <__iterator/next.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>) {
+      // Special-case the one element case. Avoid repeatedly initializing objects from the result of an iterator
+      // dereference when doing so might not be idempotent. The `if constexpr` avoids the extra branch in cases where
+      // it's not needed.
+      if constexpr (!same_as<remove_cvref_t<range_reference_t<_Range>>, _ValueT> ||
+                    is_rvalue_reference_v<range_reference_t<_Range>>) {
+        if (ranges::next(__first) == __last) {
+          // During initialization, members are allowed to refer to already initialized members
+          // (see http://eel.is/c++draft/dcl.init.aggr#6)
+          minmax_result<_ValueT> __result = {*__first, __result.min};
+          return __result;
+        }
+      }
       auto __result = std::__minmax_element_impl(__first, __last, __comp, __proj);
       return {*__result.first, *__result.second};
     } 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)));
       };
 
+      // During initialization, members are allowed to refer to already initialized members
+      // (see http://eel.is/c++draft/dcl.init.aggr#6)
       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>) {
       return __result;
     }
   }
 };
 } // 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

 //     ranges::minmax(R&& r, Comp comp = {}, Proj proj = {});
 
 #include <algorithm>
 #include <array>
 #include <cassert>
 #include <functional>
 #include <memory>
 #include <ranges>
+#include <string>
 
 #include "test_iterators.h"
 
 template <class T>
 concept HasMinMax = requires { std::ranges::minmax(std::declval<T>()); };
 
 struct NoLessThanOp {};
 struct NotTotallyOrdered {
constexpr void test_range() {
 
   {
     // check that an rvalue array works
     int a[] = {1, 2, 3, 4};
     auto ret = std::ranges::minmax(std::move(a));
     assert(ret.min == 1);
     assert(ret.max == 4);
   }
+  {
+    // check that the input iterator isn't moved from multiple times
+    const std::string str{"this long string will be dynamically allocated"};
+    std::string a[] = {str};
+    auto range      = std::ranges::subrange(
+        cpp20_input_iterator(std::move_iterator(a)), sentinel_wrapper(cpp20_input_iterator(std::move_iterator(a + 1))));
+    auto ret = std::ranges::minmax(range);
+    assert(ret.min == str);
+    assert(ret.max == str);
+  }
+  {
+    // check that the forward iterator isn't moved from multiple times
+    const std::string str{"this long string will be dynamically allocated"};
+    std::string a[] = {str};
+    auto range =
+        std::ranges::subrange(forward_iterator(std::move_iterator(a)), forward_iterator(std::move_iterator(a + 1)));
+    auto ret = std::ranges::minmax(range);
+    assert(ret.min == str);
+    assert(ret.max == str);
+  }
 }
 
 constexpr bool test() {
   test_2_arguments();
   test_initializer_list();
   test_range();
 
   return true;
 }
 
 int main(int, char**) {
   test();
   static_assert(test());
 
-  {
-    // check that the 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);
-  }
-
   return 0;
 }