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

Differential Revision: https://reviews.llvm.org/D126193

(cherry picked from commit a203acb9dd7227323d6161431225189d49917744)

14 files changed, 241 insertions, 9 deletions

diff --git a/libcxx/docs/Status/RangesAlgorithms.csv b/libcxx/docs/Status/RangesAlgorithms.csv
index 8938c99..6982f1e 100644
--- a/libcxx/docs/Status/RangesAlgorithms.csv
+++ b/libcxx/docs/Status/RangesAlgorithms.csv
@@ -32,7 +32,7 @@ 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>`_,✅
diff --git a/libcxx/include/CMakeLists.txt b/libcxx/include/CMakeLists.txt
index 957779d..7ce9b66 100644
--- a/libcxx/include/CMakeLists.txt
+++ b/libcxx/include/CMakeLists.txt
@@ -72,6 +72,7 @@ set(files
   __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
diff --git a/libcxx/include/__algorithm/clamp.h b/libcxx/include/__algorithm/clamp.h
index b3762b8..30ddbdc 100644
--- a/libcxx/include/__algorithm/clamp.h
+++ b/libcxx/include/__algorithm/clamp.h
@@ -22,7 +22,7 @@ _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)
 {
@@ -33,7 +33,7 @@ clamp(const _Tp& __v, const _Tp& __lo, const _Tp& __hi, _Compare __comp)
 
 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)
 {
diff --git a/libcxx/include/__algorithm/ranges_clamp.h b/libcxx/include/__algorithm/ranges_clamp.h
new file mode 100644
index 0000000..bdde97e
--- /dev/null
+++ b/libcxx/include/__algorithm/ranges_clamp.h
@@ -0,0 +1,65 @@
+//===----------------------------------------------------------------------===//
+//
+// 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>
+#include <__utility/forward.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");
+
+    if (std::invoke(__comp, std::invoke(__proj, __value), std::invoke(__proj, __low)))
+      return __low;
+    else if (std::invoke(__comp, std::invoke(__proj, __high), std::invoke(__proj, __value)))
+      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
diff --git a/libcxx/include/algorithm b/libcxx/include/algorithm
index ab5ad55..227a408 100644
--- a/libcxx/include/algorithm
+++ b/libcxx/include/algorithm
@@ -593,6 +593,11 @@ namespace ranges {
     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>,
@@ -931,6 +936,7 @@ namespace ranges {
               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
+<<<<<<< HEAD
 
   template<class I, class O>
       using remove_copy_result = in_out_result<I, O>;                                              // Since C++20
@@ -1764,6 +1770,7 @@ template <class BidirectionalIterator, class Compare>
 #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>
diff --git a/libcxx/include/module.modulemap.in b/libcxx/include/module.modulemap.in
index 897c2c8..0b33ffd 100644
--- a/libcxx/include/module.modulemap.in
+++ b/libcxx/include/module.modulemap.in
@@ -311,6 +311,7 @@ module std [system] {
       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" }
diff --git a/libcxx/test/libcxx/algorithms/ranges_robust_against_copying_comparators.pass.cpp b/libcxx/test/libcxx/algorithms/ranges_robust_against_copying_comparators.pass.cpp
index 0196235..1582981 100644
--- a/libcxx/test/libcxx/algorithms/ranges_robust_against_copying_comparators.pass.cpp
+++ b/libcxx/test/libcxx/algorithms/ranges_robust_against_copying_comparators.pass.cpp
@@ -98,7 +98,7 @@ constexpr bool all_the_algorithms()
     (void)std::ranges::any_of(a, UnaryTrue(&copies)); assert(copies == 0);
     (void)std::ranges::binary_search(first, last, value, Less(&copies)); assert(copies == 0);
     (void)std::ranges::binary_search(a, value, Less(&copies)); assert(copies == 0);
-    //(void)std::ranges::clamp(value, value, value, Less(&copies)); assert(copies == 0);
+    (void)std::ranges::clamp(value, value, value, Less(&copies)); assert(copies == 0);
     (void)std::ranges::count_if(first, last, UnaryTrue(&copies)); assert(copies == 0);
     (void)std::ranges::count_if(a, UnaryTrue(&copies)); assert(copies == 0);
     (void)std::ranges::copy_if(first, last, first2, UnaryTrue(&copies)); assert(copies == 0);
diff --git a/libcxx/test/libcxx/algorithms/ranges_robust_against_copying_projections.pass.cpp b/libcxx/test/libcxx/algorithms/ranges_robust_against_copying_projections.pass.cpp
index aa75226..074df6e 100644
--- a/libcxx/test/libcxx/algorithms/ranges_robust_against_copying_projections.pass.cpp
+++ b/libcxx/test/libcxx/algorithms/ranges_robust_against_copying_projections.pass.cpp
@@ -80,7 +80,7 @@ constexpr bool all_the_algorithms()
     (void)std::ranges::any_of(a, UnaryTrue(), Proj(&copies)); assert(copies == 0);
     (void)std::ranges::binary_search(first, last, value, Less(), Proj(&copies)); assert(copies == 0);
     (void)std::ranges::binary_search(a, value, Less(), Proj(&copies)); assert(copies == 0);
-    //(void)std::ranges::clamp(T(), T(), T(), Less(), Proj(&copies)); assert(copies == 0);
+    (void)std::ranges::clamp(T(), T(), T(), Less(), Proj(&copies)); assert(copies == 0);
     (void)std::ranges::count(first, last, value, Proj(&copies)); assert(copies == 0);
     (void)std::ranges::count(a, value, Proj(&copies)); assert(copies == 0);
     (void)std::ranges::count_if(first, last, UnaryTrue(), Proj(&copies)); assert(copies == 0);
diff --git a/libcxx/test/libcxx/private_headers.verify.cpp b/libcxx/test/libcxx/private_headers.verify.cpp
index 3c14d13..49fce41 100644
--- a/libcxx/test/libcxx/private_headers.verify.cpp
+++ b/libcxx/test/libcxx/private_headers.verify.cpp
@@ -109,6 +109,7 @@ END-SCRIPT
 #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'}}
diff --git a/libcxx/test/std/algorithms/alg.sorting/alg.clamp/assert.ranges_clamp.pass.cpp b/libcxx/test/std/algorithms/alg.sorting/alg.clamp/assert.ranges_clamp.pass.cpp
new file mode 100644
index 0000000..789ce1e
--- /dev/null
+++ b/libcxx/test/std/algorithms/alg.sorting/alg.clamp/assert.ranges_clamp.pass.cpp
@@ -0,0 +1,34 @@
+//===----------------------------------------------------------------------===//
+//
+// 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
+//
+//===----------------------------------------------------------------------===//
+
+// REQUIRES: has-unix-headers
+// UNSUPPORTED: c++03, c++11, c++14, c++17, libcpp-has-no-incomplete-ranges
+// XFAIL: use_system_cxx_lib && target={{.+}}-apple-macosx{{10.9|10.10|10.11|10.12|10.13|10.14|10.15|11.0|12.0}}
+// ADDITIONAL_COMPILE_FLAGS: -D_LIBCPP_ENABLE_ASSERTIONS=1
+
+// <algorithm>
+
+// In a call to `ranges::clamp(val, low, high)`, `low` must be `<= high`.
+
+#include <algorithm>
+#include <functional>
+
+#include "check_assertion.h"
+
+int main(int, char**) {
+  std::ranges::clamp(1, 2, 0, std::ranges::greater{});
+  TEST_LIBCPP_ASSERT_FAILURE(std::ranges::clamp(1, 2, 0), "Bad bounds passed to std::ranges::clamp");
+
+  std::ranges::clamp(1, 0, 2);
+  TEST_LIBCPP_ASSERT_FAILURE(std::ranges::clamp(1, 0, 2, std::ranges::greater{}),
+      "Bad bounds passed to std::ranges::clamp");
+
+  std::ranges::clamp(1, 1, 1); // Equal bounds should be fine.
+
+  return 0;
+}
diff --git a/libcxx/test/std/algorithms/alg.sorting/alg.clamp/ranges.clamp.pass.cpp b/libcxx/test/std/algorithms/alg.sorting/alg.clamp/ranges.clamp.pass.cpp
new file mode 100644
index 0000000..fe5f54d
--- /dev/null
+++ b/libcxx/test/std/algorithms/alg.sorting/alg.clamp/ranges.clamp.pass.cpp
@@ -0,0 +1,123 @@
+//===----------------------------------------------------------------------===//
+//
+// 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
+
+// Older Clangs don't properly deduce decltype(auto) with a concept constraint
+// XFAIL: apple-clang-13.0
+
+// 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>
+#include <utility>
+
+template <class T, class Comp = std::ranges::less, class Proj = std::identity>
+concept HasClamp =
+    requires(T&& val, T&& low, T&& high, Comp&& comp, Proj&& proj) {
+      std::ranges::clamp(std::forward<T>(val), std::forward<T>(low), std::forward<T>(high),
+          std::forward<Comp>(comp), std::forward<Proj>(proj));
+    };
+
+struct NoComp {};
+struct CreateNoComp {
+  auto operator()(int) const { return NoComp(); }
+};
+
+static_assert(HasClamp<int, std::ranges::less, std::identity>);
+static_assert(!HasClamp<NoComp>);
+static_assert(!HasClamp<int, NoComp>);
+static_assert(!HasClamp<int, std::ranges::less, CreateNoComp>);
+
+constexpr bool test() {
+  { // low < val < high
+    int val = 2;
+    int low = 1;
+    int high = 3;
+    std::same_as<const int&> decltype(auto) ret = std::ranges::clamp(val, low, high);
+    assert(ret == 2);
+    assert(&ret == &val);
+  }
+
+  { // low > val < high
+    assert(std::ranges::clamp(10, 20, 30) == 20);
+  }
+
+  { // low < val > high
+    assert(std::ranges::clamp(15, 5, 10) == 10);
+  }
+
+  { // low == val == high
+    int val = 10;
+    assert(&std::ranges::clamp(val, 10, 10) == &val);
+  }
+
+  { // Check that a custom comparator works.
+    assert(std::ranges::clamp(10, 30, 20, std::ranges::greater{}) == 20);
+  }
+
+  { // Check that a custom projection works.
+    struct S {
+      int i;
+
+      constexpr const int& lvalue_proj() const { return i; }
+      constexpr int prvalue_proj() const { return i; }
+    };
+
+    struct Comp {
+      constexpr bool operator()(const int& lhs, const int& rhs) const { return lhs < rhs; }
+      constexpr bool operator()(int&& lhs, int&& rhs) const { return lhs > rhs; }
+    };
+
+    auto val = S{10};
+    auto low = S{20};
+    auto high = S{30};
+    // Check that the value category of the projection return type is preserved.
+    assert(&std::ranges::clamp(val, low, high, Comp{}, &S::lvalue_proj) == &low);
+    assert(&std::ranges::clamp(val, high, low, Comp{}, &S::prvalue_proj) == &low);
+  }
+
+  { // Check that the implementation doesn't cause double moves (which could result from calling the projection on
+    // `value` once and then forwarding the result into the comparator).
+    struct CheckDoubleMove {
+      int i;
+      bool moved = false;
+
+      constexpr explicit CheckDoubleMove(int set_i) : i(set_i) {}
+      constexpr CheckDoubleMove(const CheckDoubleMove&) = default;
+      constexpr CheckDoubleMove(CheckDoubleMove&& rhs) noexcept : i(rhs.i) {
+        assert(!rhs.moved);
+        rhs.moved = true;
+      }
+    };
+
+    auto val = CheckDoubleMove{20};
+    auto low = CheckDoubleMove{10};
+    auto high = CheckDoubleMove{30};
+
+    auto moving_comp = [](CheckDoubleMove lhs, CheckDoubleMove rhs) { return lhs.i < rhs.i; };
+    auto prvalue_proj = [](const CheckDoubleMove& x) -> CheckDoubleMove { return x; };
+    assert(&std::ranges::clamp(val, low, high, moving_comp, prvalue_proj) == &val);
+  }
+
+  return true;
+}
+
+int main(int, char**) {
+  test();
+  static_assert(test());
+
+  return 0;
+}
diff --git a/libcxx/test/std/algorithms/ranges_robust_against_nonbool_predicates.pass.cpp b/libcxx/test/std/algorithms/ranges_robust_against_nonbool_predicates.pass.cpp
index 222b45f..114a099 100644
--- a/libcxx/test/std/algorithms/ranges_robust_against_nonbool_predicates.pass.cpp
+++ b/libcxx/test/std/algorithms/ranges_robust_against_nonbool_predicates.pass.cpp
@@ -109,7 +109,7 @@ constexpr bool test_all() {
   test(std::ranges::includes, in, in2, binary_pred);
   test(std::ranges::is_heap, in, binary_pred);
   test(std::ranges::is_heap_until, in, binary_pred);
-  //std::ranges::clamp(2, 1, 3, binary_pred);
+  std::ranges::clamp(2, 1, 3, binary_pred);
   //test(std::ranges::is_permutation, in, in2, binary_pred);
   test(std::ranges::copy_if, in, out, unary_pred);
   test(std::ranges::remove_copy_if, in, out, unary_pred);
diff --git a/libcxx/test/std/algorithms/ranges_robust_against_omitting_invoke.pass.cpp b/libcxx/test/std/algorithms/ranges_robust_against_omitting_invoke.pass.cpp
index a820026..787c92f 100644
--- a/libcxx/test/std/algorithms/ranges_robust_against_omitting_invoke.pass.cpp
+++ b/libcxx/test/std/algorithms/ranges_robust_against_omitting_invoke.pass.cpp
@@ -67,7 +67,7 @@ constexpr bool test_all() {
 
   Bar a{Foo{1}};
   Bar b{Foo{2}};
-  //Bar c{Foo{3}};
+  Bar c{Foo{3}};
 
   Foo x{2};
   size_t count = 1;
@@ -116,7 +116,7 @@ constexpr bool test_all() {
   test(std::ranges::includes, in, in2, &Foo::binary_pred, &Bar::val, &Bar::val);
   test(std::ranges::is_heap, in, &Foo::binary_pred, &Bar::val);
   test(std::ranges::is_heap_until, in, &Foo::binary_pred, &Bar::val);
-  //std::ranges::clamp(b, a, c, &Foo::binary_pred);
+  std::ranges::clamp(b, a, c, &Foo::binary_pred, &Bar::val);
   //test(std::ranges::is_permutation, in, in2, &Foo::binary_pred, &Bar::val, &Bar::val);
   test(std::ranges::for_each, in, &Foo::unary_pred, &Bar::val);
   std::ranges::for_each_n(in.begin(), count, &Foo::unary_pred, &Bar::val);
diff --git a/libcxx/test/std/library/description/conventions/customization.point.object/niebloid.compile.pass.cpp b/libcxx/test/std/library/description/conventions/customization.point.object/niebloid.compile.pass.cpp
index 5abe476..2be8a7e 100644
--- a/libcxx/test/std/library/description/conventions/customization.point.object/niebloid.compile.pass.cpp
+++ b/libcxx/test/std/library/description/conventions/customization.point.object/niebloid.compile.pass.cpp
@@ -65,7 +65,7 @@ static_assert(test(std::ranges::adjacent_find, a));
 static_assert(test(std::ranges::all_of, a, odd));
 static_assert(test(std::ranges::any_of, a, odd));
 static_assert(test(std::ranges::binary_search, a, 42));
-//static_assert(test(std::ranges::clamp, 42, 42, 42));
+static_assert(test(std::ranges::clamp, 42, 42, 42));
 static_assert(test(std::ranges::copy, a, a));
 static_assert(test(std::ranges::copy_backward, a, a));
 static_assert(test(std::ranges::copy_if, a, a, odd));