[libc++][ranges] Implement `ranges::clamp`

[var-const]

libcxx/docs/Status/RangesAlgorithms.csv

29–30

Please don't forget to update the link before merging.

libcxx/test/std/algorithms/alg.sorting/alg.clamp/ranges.clamp.pass.cpp

24

Can you also check SFINAE with indirect_­strict_­weak_­order?

33

Ultranit: maybe use different values in different test cases? I know it sounds funny but I'm slightly concerned that return 20; would pass most if not all the tests. :) It might also make it a bit more obvious which value is being returned (high/low/original) when the same value of 20 doesn't have different meanings in different test cases.

39

Can you also check with a comparator that returns something convertible to bool?

41

Can you also add test cases like (10, 10, 20) and (10, 20, 20), i.e., when value is equal to one of the bounds but not the other?

[var-const]

Rebase on main.

[jloser]

libcxx/include/algorithm

290

Please don't forget to remove this merge conflict marker.

[var-const]

Remove conflict marker.

[var-const]

libcxx/include/algorithm

290

Thanks!

[var-const]

• Fix a bug where the result of applying a projection could lose its value category and add a test;
• fix incorrect assertion checking that low <= high and add an assertion test for it;
• add SFINAE tests;
• add ranges::clamp to the relevant robust test suites;
• address the existing feedback.

[var-const]

Fix the CI and rebase.

[var-const]

Fix the CI.

[var-const]

Remove accidental.

[var-const]

Fix the CI.

[ldionne]

LGTM with CI fixed and my comments applied.

libcxx/include/__algorithm/ranges_clamp.h

43

Can we add a test with a predicate that returns something explicitly convertible to bool? This should only be supported in the Ranges version.

46–52

Based on our discussion just now, your value category test is correct, however this optimization is wrong because it can lead to double-moves.

It would be possible to catch this with:

// large values to avoid SSO
int val = 100000000000000000000000000000000;
int low = 200000000000000000000000000000000;
int high = 300000000000000000000000000000000;
auto proj = [](int i) { return std::to_string(i); }; // important: returns a temporary
auto comp = [](std::string lhs, std::string rhs) { // important: moves out of rvalue arguments
    return std::atoi(lhs.c_str()) < std::atoi(rhs.c_str());
};
std::ranges::clamp(val, low, high, comp, proj);

Something like this should trigger a double-move. Probably easier to test with a Tracked value of some sort.

Also, after adding the test, can you make sure that your current implementation does fail?

libcxx/test/std/algorithms/alg.sorting/alg.clamp/ranges.clamp.pass.cpp

10

I would XFAIL this on apple-clang-13. That's the CI issue.

[var-const]

Address feedback

[var-const]

Rebase on main.

libcxx/include/__algorithm/ranges_clamp.h

43

Hmm, it looks like the algorithm constraints actually prevent a return type that's only explicitly (and not implicitly) convertible to bool:

• the algorithm requires indirect_strict_weak_order for _Comp;
• indirect_strict_weak_order requires strict_weak_order;
• strict_weak_order requires relation;
• relation requires boolean-testable;
• boolean-testable requires boolean-testable-impl;
• boolean-testable-impl requires std::convertible_to<T, bool>;
• std::convertible_to<T, bool> requires *both* an explicit and an implicit conversion.

If I'm reading this correctly, the indirect_strict_weak_order constraint prevents the comparator that returns a type explicitly convertible to bool. If so, the bool casts in the definition of clamp in the standard appear redundant (at least for the range algorithm -- since the same wording is used for the classic algorithm as well, perhaps it's there because of it?). What do you think -- perhaps I'm missing something?

46–52

Added a new test case and verified it fails for the original version (I used a simple struct that checks for double-moving).

libcxx/test/std/algorithms/alg.sorting/alg.clamp/ranges.clamp.pass.cpp

10

Right -- it looks like this has already come up before in test/std/ranges/range.adaptors/range.filter/pred.pass.cpp which has the following comment:

// Older Clangs don't properly deduce decltype(auto) with a concept constraint

[var-const]

Fix the CI.

libcxx/docs/Status/RangesAlgorithms.csv

 Search,min_element,Nikolas Klauser,`D117025 <https://llvm.org/D117025>`_,✅
 Search,max_element,Nikolas Klauser,`D117523 <https://llvm.org/D117523>`_,✅
 Search,minmax_element,Nikolas Klauser,`D120637 <https://llvm.org/D120637>`_,✅
 Search,count,Nikolas Klauser,`D121523 <https://llvm.org/D121523>`_,✅
 Search,count_if,Nikolas Klauser,`D121523 <https://llvm.org/D121523>`_,✅
 Search,search,Nikolas Klauser,`D124079 <https://llvm.org/D124079>`_,✅
 Search,search_n,Nikolas Klauser,`D124079 <https://llvm.org/D124079>`_,✅
 Search,find_end,Nikolas Klauser,`D124079 <https://llvm.org/D124079>`_,✅
 Read-only,is_partitioned,Nikolas Klauser,`D124440 <https://llvm.org/D124440>`_,✅
 Read-only,is_sorted,Nikolas Klauser,`D125608 <https://llvm.org/D125608>`_,✅
 Read-only,is_sorted_until,Nikolas Klauser,`D125608 <https://llvm.org/D125608>`_,✅
 Read-only,includes,Hui Xie,`D130116 <https://llvm.org/D130116>`,✅
 Read-only,is_heap,Konstantin Varlamov,`D130547 <https://llvm.org/D130547>`_,✅
 Read-only,is_heap_until,Konstantin Varlamov,`D130547 <https://llvm.org/D130547>`_,✅
-Read-only,clamp,Nikolas Klauser,`D126193 <https://llvm.org/D126193>`_,Under review
+Read-only,clamp,Nikolas Klauser,`D126193 <https://llvm.org/D126193>`_,✅
 Read-only,is_permutation,Nikolas Klauser,`D127194 <https://llvm.org/D127194>`_,Under review
 Read-only,for_each,Nikolas Klauser,`D124332 <https://llvm.org/D124332>`_,✅
 Read-only,for_each_n,Nikolas Klauser,`D124332 <https://llvm.org/D124332>`_,✅
 Write,copy,Nikolas Klauser,`D122982 <https://llvm.org/D122982>`_,✅
 Write,copy_if,Nikolas Klauser,`D122982 <https://llvm.org/D122982>`_,✅
 Write,copy_n,Nikolas Klauser,`D122982 <https://llvm.org/D122982>`_,✅
 Write,copy_backward,Nikolas Klauser,`D122982 <https://llvm.org/D122982>`_,✅
 Write,move,Nikolas Klauser,`D126616 <https://llvm.org/D126616>`_,✅

libcxx/include/CMakeLists.txt

set(files
   __algorithm/partition_point.h
   __algorithm/pop_heap.h
   __algorithm/prev_permutation.h
   __algorithm/push_heap.h
   __algorithm/ranges_adjacent_find.h
   __algorithm/ranges_all_of.h
   __algorithm/ranges_any_of.h
   __algorithm/ranges_binary_search.h
+  __algorithm/ranges_clamp.h
   __algorithm/ranges_copy.h
   __algorithm/ranges_copy_backward.h
   __algorithm/ranges_copy_if.h
   __algorithm/ranges_copy_n.h
   __algorithm/ranges_count.h
   __algorithm/ranges_count_if.h
   __algorithm/ranges_equal.h
   __algorithm/ranges_equal_range.h

libcxx/include/__algorithm/clamp.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_CLAMP_H
 #define _LIBCPP___ALGORITHM_CLAMP_H
 
 #include <__algorithm/comp.h>
 #include <__assert>
 #include <__config>
 
 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
 #  pragma GCC system_header
 #endif
 
 _LIBCPP_BEGIN_NAMESPACE_STD
 
 #if _LIBCPP_STD_VER > 14
 template<class _Tp, class _Compare>
 _LIBCPP_NODISCARD_EXT inline
-_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR
+_LIBCPP_INLINE_VISIBILITY constexpr
 const _Tp&
 clamp(const _Tp& __v, const _Tp& __lo, const _Tp& __hi, _Compare __comp)
 {
     _LIBCPP_ASSERT(!__comp(__hi, __lo), "Bad bounds passed to std::clamp");
     return __comp(__v, __lo) ? __lo : __comp(__hi, __v) ? __hi : __v;
 
 }
 
 template<class _Tp>
 _LIBCPP_NODISCARD_EXT inline
-_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR
+_LIBCPP_INLINE_VISIBILITY constexpr
 const _Tp&
 clamp(const _Tp& __v, const _Tp& __lo, const _Tp& __hi)
 {
     return _VSTD::clamp(__v, __lo, __hi, __less<_Tp>());
 }
 #endif
 
 _LIBCPP_END_NAMESPACE_STD
 
 #endif // _LIBCPP___ALGORITHM_CLAMP_H

libcxx/include/__algorithm/ranges_clamp.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_CLAMP_H
+#define _LIBCPP___ALGORITHM_RANGES_CLAMP_H
+
+#include <__assert>
+#include <__config>
+#include <__functional/identity.h>
+#include <__functional/invoke.h>
+#include <__functional/ranges_operations.h>
+#include <__iterator/concepts.h>
+#include <__iterator/projected.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 {
+namespace __clamp {
+struct __fn {
+
+  template <class _Type,
+            class _Proj = identity,
+            indirect_strict_weak_order<projected<const _Type*, _Proj>> _Comp = ranges::less>
+  _LIBCPP_HIDE_FROM_ABI constexpr
+  const _Type& operator()(const _Type& __value,
+                          const _Type& __low,
+                          const _Type& __high,
+                          _Comp __comp = {},
+                          _Proj __proj = {}) const {
+    _LIBCPP_ASSERT(bool(std::invoke(__comp, std::invoke(__proj, __high), std::invoke(__proj, __low))),
+                   "Bad bounds passed to std::ranges::clamp");
+    auto&& __val = std::invoke(__proj, __value);
+    if (std::invoke(__comp, __val, std::invoke(__proj, __low)))
+      return __low;
+    else if (std::invoke(__comp, std::invoke(__proj, __high), __val))
+      return __high;
+    else
+      return __value;
+  }
+
+};
+} // namespace __clamp
+
+inline namespace __cpo {
+  inline constexpr auto clamp = __clamp::__fn{};
+} // namespace __cpo
+} // namespace ranges
+
+_LIBCPP_END_NAMESPACE_STD
+
+#endif // _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES)
+
+#endif // _LIBCPP___ALGORITHM_RANGES_CLAMP_H

libcxx/include/algorithm

template<input_range R, class Proj = identity,
   template<input_iterator I, sentinel_for<I> S, class Proj = identity,
            indirect_unary_predicate<projected<I, Proj>> Pred>
     constexpr bool ranges::is_partitioned(I first, S last, Pred pred, Proj proj = {});      // since C++20
 
   template<input_range R, class Proj = identity,
            indirect_unary_predicate<projected<iterator_t<R>, Proj>> Pred>
     constexpr bool ranges::is_partitioned(R&& r, Pred pred, Proj proj = {});                // since C++20
 
+<<<<<<< HEAD
   template<random_access_iterator I, sentinel_for<I> S, class Comp = ranges::less,
           class Proj = identity>
     requires sortable<I, Comp, Proj>
     constexpr I
       ranges::push_heap(I first, S last, Comp comp = {}, Proj proj = {});                   // since C++20
 
   template<random_access_range R, class Comp = ranges::less, class Proj = identity>
     requires sortable<iterator_t<R>, Comp, Proj>
template<input_iterator I, sentinel_for<I> S, class T, class Proj = identity,
     constexpr I ranges::replace_if(I first, S last, Pred pred, const T& new_value, Proj proj = {}); // since C++20
 
   template<input_range R, class T, class Proj = identity,
            indirect_unary_predicate<projected<iterator_t<R>, Proj>> Pred>
     requires indirectly_writable<iterator_t<R>, const T&>
     constexpr borrowed_iterator_t<R>
       ranges::replace_if(R&& r, Pred pred, const T& new_value, Proj proj = {});                     // since C++20
 
+  template<class T, class Proj = identity,
+           indirect_strict_weak_order<projected<const T*, Proj>> Comp = ranges::less>
+    constexpr const T&
+      ranges::clamp(const T& v, const T& lo, const T& hi, Comp comp = {}, Proj proj = {});          // since C++20
+
   template<input_iterator I1, sentinel_for<I1> S1, input_iterator I2, sentinel_for<I2> S2,
            class Proj1 = identity, class Proj2 = identity,
            indirect_strict_weak_order<projected<I1, Proj1>,
                                       projected<I2, Proj2>> Comp = ranges::less>
     constexpr bool
       ranges::lexicographical_compare(I1 first1, S1 last1, I2 first2, S2 last2,
                                       Comp comp = {}, Proj1 proj1 = {}, Proj2 proj2 = {});    // since C++20
 
template<input_range R1, input_range R2, class Pred = ranges::equal_to,
   template<input_range R, weakly_incrementable O, class Proj = identity,
            indirect_equivalence_relation<projected<iterator_t<R>, Proj>> C = ranges::equal_to>
     requires indirectly_copyable<iterator_t<R>, O> &&
              (forward_iterator<iterator_t<R>> ||
               (input_iterator<O> && same_as<range_value_t<R>, iter_value_t<O>>) ||
               indirectly_copyable_storable<iterator_t<R>, O>)
     constexpr unique_copy_result<borrowed_iterator_t<R>, O>
       unique_copy(R&& r, O result, C comp = {}, Proj proj = {});                                   // 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/partition_point.h>
 #include <__algorithm/pop_heap.h>
 #include <__algorithm/prev_permutation.h>
 #include <__algorithm/push_heap.h>
 #include <__algorithm/ranges_adjacent_find.h>
 #include <__algorithm/ranges_all_of.h>
 #include <__algorithm/ranges_any_of.h>
 #include <__algorithm/ranges_binary_search.h>
+#include <__algorithm/ranges_clamp.h>
 #include <__algorithm/ranges_copy.h>
 #include <__algorithm/ranges_copy_backward.h>
 #include <__algorithm/ranges_copy_if.h>
 #include <__algorithm/ranges_copy_n.h>
 #include <__algorithm/ranges_count.h>
 #include <__algorithm/ranges_count_if.h>
 #include <__algorithm/ranges_equal.h>
 #include <__algorithm/ranges_equal_range.h>

libcxx/include/module.modulemap.in

module __algorithm {
       module partition_point                 { private header "__algorithm/partition_point.h" }
       module pop_heap                        { private header "__algorithm/pop_heap.h" }
       module prev_permutation                { private header "__algorithm/prev_permutation.h" }
       module push_heap                       { private header "__algorithm/push_heap.h" }
       module ranges_adjacent_find            { private header "__algorithm/ranges_adjacent_find.h" }
       module ranges_all_of                   { private header "__algorithm/ranges_all_of.h" }
       module ranges_any_of                   { private header "__algorithm/ranges_any_of.h" }
       module ranges_binary_search            { private header "__algorithm/ranges_binary_search.h" }
+      module ranges_clamp                    { private header "__algorithm/ranges_clamp.h" }
       module ranges_copy                     { private header "__algorithm/ranges_copy.h" }
       module ranges_copy_backward            { private header "__algorithm/ranges_copy_backward.h" }
       module ranges_copy_if                  { private header "__algorithm/ranges_copy_if.h" }
       module ranges_copy_n                   { private header "__algorithm/ranges_copy_n.h" }
       module ranges_count                    { private header "__algorithm/ranges_count.h" }
       module ranges_count_if                 { private header "__algorithm/ranges_count_if.h" }
       module ranges_equal                    { private header "__algorithm/ranges_equal.h" }
       module ranges_equal_range              { private header "__algorithm/ranges_equal_range.h" }

libcxx/test/libcxx/private_headers.verify.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
 //
 //===----------------------------------------------------------------------===//
 

 #include <__algorithm/partition_point.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/partition_point.h'}}
 #include <__algorithm/pop_heap.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/pop_heap.h'}}
 #include <__algorithm/prev_permutation.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/prev_permutation.h'}}
 #include <__algorithm/push_heap.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/push_heap.h'}}
 #include <__algorithm/ranges_adjacent_find.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_adjacent_find.h'}}
 #include <__algorithm/ranges_all_of.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_all_of.h'}}
 #include <__algorithm/ranges_any_of.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_any_of.h'}}
 #include <__algorithm/ranges_binary_search.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_binary_search.h'}}
+#include <__algorithm/ranges_clamp.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_clamp.h'}}
 #include <__algorithm/ranges_copy.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_copy.h'}}
 #include <__algorithm/ranges_copy_backward.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_copy_backward.h'}}
 #include <__algorithm/ranges_copy_if.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_copy_if.h'}}
 #include <__algorithm/ranges_copy_n.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_copy_n.h'}}
 #include <__algorithm/ranges_count.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_count.h'}}
 #include <__algorithm/ranges_count_if.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_count_if.h'}}
 #include <__algorithm/ranges_equal.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_equal.h'}}
 #include <__algorithm/ranges_equal_range.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_equal_range.h'}}

libcxx/test/std/algorithms/alg.sorting/alg.clamp/ranges.clamp.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<class T, class Proj = identity,
+//          indirect_strict_weak_order<projected<const T*, Proj>> Comp = ranges::less>
+//   constexpr const T&
+//     ranges::clamp(const T& v, const T& lo, const T& hi, Comp comp = {}, Proj proj = {});
+
+#include <algorithm>
+#include <cassert>
+#include <functional>
+
+constexpr bool test() {
+  { // low < val < high
+    auto val = 20;
+    auto low = 10;
+    auto high = 30;
+    std::same_as<const int&> decltype(auto) ret = std::ranges::clamp(val, low, high);
+    assert(ret == 20);
+  }
+  // val < low < high
+  assert(std::ranges::clamp(10, 20, 30) == 20);
+
+  // low < high < val
+  assert(std::ranges::clamp(30, 10, 20) == 20);
+
+  // check that the comparator is used
+  assert(std::ranges::clamp(10, 30, 20, std::ranges::greater{}) == 20);
+
+  { // low = val = high
+    int val = 10;
+    assert(&std::ranges::clamp(val, 10, 10) == &val);
+  }
+
+  { // check that the projection is used
+    struct S {
+      int i;
+    };
+
+    auto val = S{10};
+    auto low = S{20};
+    auto high = S{30};
+    assert(&std::ranges::clamp(val, low, high, {}, &S::i) == &low);
+  }
+  return true;
+}
+
+int main(int, char**) {
+  test();
+  static_assert(test());
+
+  return 0;
+}