[libc++] Implement [P0769] "Add shift to algorithm" (shift_left, shift_right)
I believe this is a complete implementation of std::shift_left and std::shift_right from
http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2018/p0769r2.pdf
Some test cases copied-with-modification from D60027.
Differential Revision: https://reviews.llvm.org/D93819
GitOrigin-RevId: 3fbd3eaf28c1e6f2bb9519022611829dfe3b0464
diff --git a/docs/Cxx2aStatusPaperStatus.csv b/docs/Cxx2aStatusPaperStatus.csv
index 8991a03..e30a289 100644
--- a/docs/Cxx2aStatusPaperStatus.csv
+++ b/docs/Cxx2aStatusPaperStatus.csv
@@ -38,7 +38,7 @@
"`P0722R3 <https://wg21.link/P0722R3>`__","CWG","Efficient sized delete for variable sized classes","Rapperswil","|Complete|","9.0"
"`P0758R1 <https://wg21.link/P0758R1>`__","LWG","Implicit conversion traits and utility functions","Rapperswil","|Complete|",""
"`P0759R1 <https://wg21.link/P0759R1>`__","LWG","fpos Requirements","Rapperswil","|Complete|","11.0"
-"`P0769R2 <https://wg21.link/P0769R2>`__","LWG","Add shift to <algorithm>","Rapperswil","",""
+"`P0769R2 <https://wg21.link/P0769R2>`__","LWG","Add shift to <algorithm>","Rapperswil","|Complete|","12.0"
"`P0788R3 <https://wg21.link/P0788R3>`__","LWG","Standard Library Specification in a Concepts and Contracts World","Rapperswil","*Removed in Cologne*","n/a"
"`P0879R0 <https://wg21.link/P0879R0>`__","LWG","Constexpr for swap and swap related functions Also resolves LWG issue 2800.","Rapperswil","",""
"`P0887R1 <https://wg21.link/P0887R1>`__","LWG","The identity metafunction","Rapperswil","|Complete|","8.0"
diff --git a/docs/FeatureTestMacroTable.rst b/docs/FeatureTestMacroTable.rst
index b5db1e0..ed05488 100644
--- a/docs/FeatureTestMacroTable.rst
+++ b/docs/FeatureTestMacroTable.rst
@@ -266,7 +266,7 @@
------------------------------------------------- -----------------
``__cpp_lib_semaphore`` ``201907L``
------------------------------------------------- -----------------
- ``__cpp_lib_shift`` *unimplemented*
+ ``__cpp_lib_shift`` ``201806L``
------------------------------------------------- -----------------
``__cpp_lib_smart_ptr_for_overwrite`` *unimplemented*
------------------------------------------------- -----------------
diff --git a/include/algorithm b/include/algorithm
index da55e5e..77711d2 100644
--- a/include/algorithm
+++ b/include/algorithm
@@ -301,6 +301,16 @@
void shuffle(RandomAccessIterator first, RandomAccessIterator last,
UniformRandomNumberGenerator&& g);
+template<class ForwardIterator>
+ constexpr ForwardIterator
+ shift_left(ForwardIterator first, ForwardIterator last,
+ typename iterator_traits<ForwardIterator>::difference_type n); // C++20
+
+template<class ForwardIterator>
+ constexpr ForwardIterator
+ shift_right(ForwardIterator first, ForwardIterator last,
+ typename iterator_traits<ForwardIterator>::difference_type n); // C++20
+
template <class InputIterator, class Predicate>
constexpr bool // constexpr in C++20
is_partitioned(InputIterator first, InputIterator last, Predicate pred);
@@ -3259,6 +3269,111 @@
}
}
+#if _LIBCPP_STD_VER > 17
+
+// shift_left, shift_right
+
+template <class _ForwardIterator>
+inline _LIBCPP_INLINE_VISIBILITY constexpr
+_ForwardIterator
+shift_left(_ForwardIterator __first, _ForwardIterator __last,
+ typename iterator_traits<_ForwardIterator>::difference_type __n)
+{
+ if (__n == 0) {
+ return __last;
+ }
+
+ _ForwardIterator __m = __first;
+ if constexpr (__is_cpp17_random_access_iterator<_ForwardIterator>::value) {
+ if (__n >= __last - __first) {
+ return __first;
+ }
+ __m += __n;
+ } else {
+ for (; __n > 0; --__n) {
+ if (__m == __last) {
+ return __first;
+ }
+ ++__m;
+ }
+ }
+ return _VSTD::move(__m, __last, __first);
+}
+
+template <class _ForwardIterator>
+inline _LIBCPP_INLINE_VISIBILITY constexpr
+_ForwardIterator
+shift_right(_ForwardIterator __first, _ForwardIterator __last,
+ typename iterator_traits<_ForwardIterator>::difference_type __n)
+{
+ if (__n == 0) {
+ return __first;
+ }
+
+ if constexpr (__is_cpp17_random_access_iterator<_ForwardIterator>::value) {
+ decltype(__n) __d = __last - __first;
+ if (__n >= __d) {
+ return __last;
+ }
+ _ForwardIterator __m = __first + (__d - __n);
+ return _VSTD::move_backward(__first, __m, __last);
+ } else if constexpr (__is_cpp17_bidirectional_iterator<_ForwardIterator>::value) {
+ _ForwardIterator __m = __last;
+ for (; __n > 0; --__n) {
+ if (__m == __first) {
+ return __last;
+ }
+ --__m;
+ }
+ return _VSTD::move_backward(__first, __m, __last);
+ } else {
+ _ForwardIterator __ret = __first;
+ for (; __n > 0; --__n) {
+ if (__ret == __last) {
+ return __last;
+ }
+ ++__ret;
+ }
+
+ // We have an __n-element scratch space from __first to __ret.
+ // Slide an __n-element window [__trail, __lead) from left to right.
+ // We're essentially doing swap_ranges(__first, __ret, __trail, __lead)
+ // over and over; but once __lead reaches __last we needn't bother
+ // to save the values of elements [__trail, __last).
+
+ auto __trail = __first;
+ auto __lead = __ret;
+ while (__trail != __ret) {
+ if (__lead == __last) {
+ _VSTD::move(__first, __trail, __ret);
+ return __ret;
+ }
+ ++__trail;
+ ++__lead;
+ }
+
+ _ForwardIterator __mid = __first;
+ while (true) {
+ if (__lead == __last) {
+ __trail = _VSTD::move(__mid, __ret, __trail);
+ _VSTD::move(__first, __mid, __trail);
+ return __ret;
+ }
+ swap(*__mid, *__trail);
+ ++__mid;
+ ++__trail;
+ ++__lead;
+ if (__mid == __ret) {
+ __mid = __first;
+ }
+ }
+ }
+}
+
+#endif // _LIBCPP_STD_VER > 17
+
+// is_partitioned
+
template <class _InputIterator, class _Predicate>
_LIBCPP_NODISCARD_EXT _LIBCPP_CONSTEXPR_AFTER_CXX17 bool
is_partitioned(_InputIterator __first, _InputIterator __last, _Predicate __pred)
diff --git a/include/version b/include/version
index 5f036a5..813bc1a 100644
--- a/include/version
+++ b/include/version
@@ -339,7 +339,7 @@
# if !defined(_LIBCPP_HAS_NO_THREADS)
# define __cpp_lib_semaphore 201907L
# endif
-// # define __cpp_lib_shift 201806L
+# define __cpp_lib_shift 201806L
// # define __cpp_lib_smart_ptr_for_overwrite 202002L
// # define __cpp_lib_source_location 201907L
# define __cpp_lib_span 202002L
diff --git a/test/std/algorithms/alg.modifying.operations/alg.shift/shift_left.pass.cpp b/test/std/algorithms/alg.modifying.operations/alg.shift/shift_left.pass.cpp
new file mode 100644
index 0000000..90540f4
--- /dev/null
+++ b/test/std/algorithms/alg.modifying.operations/alg.shift/shift_left.pass.cpp
@@ -0,0 +1,128 @@
+//===----------------------------------------------------------------------===//
+//
+// 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
+//
+//===----------------------------------------------------------------------===//
+
+// UNSUPPORTED: c++03, c++11, c++14, c++17
+
+// <algorithm>
+
+// template<class ForwardIterator>
+// constexpr ForwardIterator
+// shift_left(ForwardIterator first, ForwardIterator last,
+// typename iterator_traits<ForwardIterator>::difference_type n);
+
+#include <algorithm>
+#include <cassert>
+
+#include "test_macros.h"
+#include "test_iterators.h"
+#include "MoveOnly.h"
+
+template<class T, class Iter>
+constexpr bool test()
+{
+ int orig[] = {3,1,4,1,5, 9,2,6,5,3, 5,8,9,7,9};
+ T work[] = {3,1,4,1,5, 9,2,6,5,3, 5,8,9,7,9};
+
+ for (int n = 0; n <= 15; ++n) {
+ for (int k = 0; k <= n+2; ++k) {
+ std::copy(orig, orig+n, work);
+ Iter it = std::shift_left(Iter(work), Iter(work+n), k);
+ if (0 <= k && k < n) {
+ assert(it == Iter(work+n-k));
+ assert(std::equal(orig+k, orig+n, work, work+n-k));
+ } else {
+ assert(it == Iter(work));
+ assert(std::equal(orig, orig+n, work, work+n));
+ }
+ }
+ }
+
+ // n == 0
+ {
+ T input[] = { 0, 1, 2 };
+ const T expected[] = { 0, 1, 2 };
+ Iter b = Iter(std::begin(input));
+ Iter e = Iter(std::end(input));
+ Iter it = std::shift_left(b, e, 0);
+ assert(std::equal(std::begin(expected), std::end(expected), b, e));
+ assert(it == e);
+ }
+
+ // n > 0 && n < len
+ {
+ T input[] = { 0, 1, 2 };
+ const T expected[] = { 1, 2 };
+ Iter b = Iter(std::begin(input));
+ Iter e = Iter(std::end(input));
+ Iter it = std::shift_left(b, e, 1);
+ assert(std::equal(std::begin(expected), std::end(expected), b, it));
+ }
+ {
+ T input[] = { 1, 2, 3, 4, 5, 6, 7, 8 };
+ const T expected[] = { 3, 4, 5, 6, 7, 8 };
+ Iter b = Iter(std::begin(input));
+ Iter e = Iter(std::end(input));
+ Iter it = std::shift_left(b, e, 2);
+ assert(std::equal(std::begin(expected), std::end(expected), b, it));
+ }
+ {
+ T input[] = { 1, 2, 3, 4, 5, 6, 7, 8 };
+ const T expected[] = { 7, 8 };
+ Iter b = Iter(std::begin(input));
+ Iter e = Iter(std::end(input));
+ Iter it = std::shift_left(b, e, 6);
+ assert(std::equal(std::begin(expected), std::end(expected), b, it));
+ }
+
+ // n == len
+ {
+ T input[] = { 0, 1, 2 };
+ const T expected[] = { 0, 1, 2 };
+ Iter b = Iter(std::begin(input));
+ Iter e = Iter(std::end(input));
+ Iter it = std::shift_left(b, e, std::size(input));
+ assert(std::equal(std::begin(expected), std::end(expected), b, e));
+ assert(it == b);
+ }
+
+ // n > len
+ {
+ T input[] = { 0, 1, 2 };
+ const T expected[] = { 0, 1, 2 };
+ Iter b = Iter(std::begin(input));
+ Iter e = Iter(std::end(input));
+ Iter it = std::shift_left(b, e, std::size(input) + 1);
+ assert(std::equal(std::begin(expected), std::end(expected), b, e));
+ assert(it == b);
+ }
+
+ return true;
+}
+
+int main(int, char**)
+{
+ test<int, forward_iterator<int*>>();
+ test<int, bidirectional_iterator<int*>>();
+ test<int, random_access_iterator<int*>>();
+ test<int, int*>();
+ test<MoveOnly, forward_iterator<MoveOnly*>>();
+ test<MoveOnly, bidirectional_iterator<MoveOnly*>>();
+ test<MoveOnly, random_access_iterator<MoveOnly*>>();
+ test<MoveOnly, MoveOnly*>();
+
+ static_assert(test<int, forward_iterator<int*>>());
+ static_assert(test<int, bidirectional_iterator<int*>>());
+ static_assert(test<int, random_access_iterator<int*>>());
+ static_assert(test<int, int*>());
+ static_assert(test<MoveOnly, forward_iterator<MoveOnly*>>());
+ static_assert(test<MoveOnly, bidirectional_iterator<MoveOnly*>>());
+ static_assert(test<MoveOnly, random_access_iterator<MoveOnly*>>());
+ static_assert(test<MoveOnly, MoveOnly*>());
+
+ return 0;
+}
diff --git a/test/std/algorithms/alg.modifying.operations/alg.shift/shift_right.pass.cpp b/test/std/algorithms/alg.modifying.operations/alg.shift/shift_right.pass.cpp
new file mode 100644
index 0000000..d92387c
--- /dev/null
+++ b/test/std/algorithms/alg.modifying.operations/alg.shift/shift_right.pass.cpp
@@ -0,0 +1,127 @@
+//===----------------------------------------------------------------------===//
+//
+// 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
+//
+//===----------------------------------------------------------------------===//
+
+// UNSUPPORTED: c++03, c++11, c++14, c++17
+
+// <algorithm>
+
+// template<class ForwardIterator>
+// constexpr ForwardIterator
+// shift_right(ForwardIterator first, ForwardIterator last,
+// typename iterator_traits<ForwardIterator>::difference_type n);
+
+#include <algorithm>
+#include <cassert>
+
+#include "test_macros.h"
+#include "test_iterators.h"
+#include "MoveOnly.h"
+
+template<class T, class Iter>
+constexpr bool test()
+{
+ int orig[] = {3,1,4,1,5, 9,2,6,5,3, 5,8,9,7,9};
+ T work[] = {3,1,4,1,5, 9,2,6,5,3, 5,8,9,7,9};
+
+ for (int n = 0; n <= 15; ++n) {
+ for (int k = 0; k <= n+2; ++k) {
+ std::copy(orig, orig+n, work);
+ Iter it = std::shift_right(Iter(work), Iter(work+n), k);
+ if (k < n) {
+ assert(it == Iter(work+k));
+ assert(std::equal(orig, orig+n-k, work+k, work+n));
+ } else {
+ assert(it == Iter(work+n));
+ assert(std::equal(orig, orig+n, work, work+n));
+ }
+ }
+ }
+
+ // n == 0
+ {
+ T input[] = { 0, 1, 2 };
+ const T expected[] = { 0, 1, 2 };
+ Iter b = Iter(std::begin(input));
+ Iter e = Iter(std::end(input));
+ Iter it = std::shift_right(b, e, 0);
+ assert(std::equal(std::begin(expected), std::end(expected), it, e));
+ }
+
+ // n > 0 && n < len
+ {
+ T input[] = { 0, 1, 2 };
+ const T expected[] = { 0, 1 };
+ Iter b = Iter(std::begin(input));
+ Iter e = Iter(std::end(input));
+ Iter it = std::shift_right(b, e, 1);
+ assert(std::equal(std::begin(expected), std::end(expected), it, e));
+ }
+ {
+ T input[] = { 1, 2, 3, 4, 5, 6, 7, 8 };
+ const T expected[] = { 1, 2, 3, 4, 5, 6 };
+ Iter b = Iter(std::begin(input));
+ Iter e = Iter(std::end(input));
+ Iter it = std::shift_right(b, e, 2);
+ assert(std::equal(std::begin(expected), std::end(expected), it, e));
+ }
+ {
+ T input[] = { 1, 2, 3, 4, 5, 6, 7, 8 };
+ const T expected[] = { 1, 2 };
+ Iter b = Iter(std::begin(input));
+ Iter e = Iter(std::end(input));
+ Iter it = std::shift_right(b, e, 6);
+ assert(std::equal(std::begin(expected), std::end(expected), it, e));
+ }
+
+ // n == len
+ {
+ T input[] = { 0, 1, 2 };
+ const T expected[] = { 0, 1, 2 };
+ Iter b = Iter(std::begin(input));
+ Iter e = Iter(std::end(input));
+ Iter it = std::shift_right(b, e, std::size(input));
+ assert(std::equal(std::begin(expected), std::end(expected), b, e));
+ assert(it == e);
+ }
+
+ // n > len
+ {
+ T input[] = { 0, 1, 2 };
+ const T expected[] = { 0, 1, 2 };
+ Iter b = Iter(std::begin(input));
+ Iter e = Iter(std::end(input));
+ Iter it = std::shift_right(b, e, std::size(input) + 1);
+ assert(std::equal(std::begin(expected), std::end(expected), b, e));
+ assert(it == e);
+ }
+
+ return true;
+}
+
+int main(int, char**)
+{
+ test<int, forward_iterator<int*>>();
+ test<int, bidirectional_iterator<int*>>();
+ test<int, random_access_iterator<int*>>();
+ test<int, int*>();
+ test<MoveOnly, forward_iterator<MoveOnly*>>();
+ test<MoveOnly, bidirectional_iterator<MoveOnly*>>();
+ test<MoveOnly, random_access_iterator<MoveOnly*>>();
+ test<MoveOnly, MoveOnly*>();
+
+ static_assert(test<int, forward_iterator<int*>>());
+ static_assert(test<int, bidirectional_iterator<int*>>());
+ static_assert(test<int, random_access_iterator<int*>>());
+ static_assert(test<int, int*>());
+ static_assert(test<MoveOnly, forward_iterator<MoveOnly*>>());
+ static_assert(test<MoveOnly, bidirectional_iterator<MoveOnly*>>());
+ static_assert(test<MoveOnly, random_access_iterator<MoveOnly*>>());
+ static_assert(test<MoveOnly, MoveOnly*>());
+
+ return 0;
+}
diff --git a/test/std/language.support/support.limits/support.limits.general/algorithm.version.pass.cpp b/test/std/language.support/support.limits/support.limits.general/algorithm.version.pass.cpp
index 4e570d2..e081ca7 100644
--- a/test/std/language.support/support.limits/support.limits.general/algorithm.version.pass.cpp
+++ b/test/std/language.support/support.limits/support.limits.general/algorithm.version.pass.cpp
@@ -201,17 +201,11 @@
# error "__cpp_lib_sample should have the value 201603L in c++20"
# endif
-# if !defined(_LIBCPP_VERSION)
-# ifndef __cpp_lib_shift
-# error "__cpp_lib_shift should be defined in c++20"
-# endif
-# if __cpp_lib_shift != 201806L
-# error "__cpp_lib_shift should have the value 201806L in c++20"
-# endif
-# else // _LIBCPP_VERSION
-# ifdef __cpp_lib_shift
-# error "__cpp_lib_shift should not be defined because it is unimplemented in libc++!"
-# endif
+# ifndef __cpp_lib_shift
+# error "__cpp_lib_shift should be defined in c++20"
+# endif
+# if __cpp_lib_shift != 201806L
+# error "__cpp_lib_shift should have the value 201806L in c++20"
# endif
#elif TEST_STD_VER > 20
@@ -276,17 +270,11 @@
# error "__cpp_lib_sample should have the value 201603L in c++2b"
# endif
-# if !defined(_LIBCPP_VERSION)
-# ifndef __cpp_lib_shift
-# error "__cpp_lib_shift should be defined in c++2b"
-# endif
-# if __cpp_lib_shift != 201806L
-# error "__cpp_lib_shift should have the value 201806L in c++2b"
-# endif
-# else // _LIBCPP_VERSION
-# ifdef __cpp_lib_shift
-# error "__cpp_lib_shift should not be defined because it is unimplemented in libc++!"
-# endif
+# ifndef __cpp_lib_shift
+# error "__cpp_lib_shift should be defined in c++2b"
+# endif
+# if __cpp_lib_shift != 201806L
+# error "__cpp_lib_shift should have the value 201806L in c++2b"
# endif
#endif // TEST_STD_VER > 20
diff --git a/test/std/language.support/support.limits/support.limits.general/version.version.pass.cpp b/test/std/language.support/support.limits/support.limits.general/version.version.pass.cpp
index 289145f..9e96e2e 100644
--- a/test/std/language.support/support.limits/support.limits.general/version.version.pass.cpp
+++ b/test/std/language.support/support.limits/support.limits.general/version.version.pass.cpp
@@ -3072,17 +3072,11 @@
# endif
# endif
-# if !defined(_LIBCPP_VERSION)
-# ifndef __cpp_lib_shift
-# error "__cpp_lib_shift should be defined in c++20"
-# endif
-# if __cpp_lib_shift != 201806L
-# error "__cpp_lib_shift should have the value 201806L in c++20"
-# endif
-# else // _LIBCPP_VERSION
-# ifdef __cpp_lib_shift
-# error "__cpp_lib_shift should not be defined because it is unimplemented in libc++!"
-# endif
+# ifndef __cpp_lib_shift
+# error "__cpp_lib_shift should be defined in c++20"
+# endif
+# if __cpp_lib_shift != 201806L
+# error "__cpp_lib_shift should have the value 201806L in c++20"
# endif
# if !defined(_LIBCPP_VERSION)
@@ -4287,17 +4281,11 @@
# endif
# endif
-# if !defined(_LIBCPP_VERSION)
-# ifndef __cpp_lib_shift
-# error "__cpp_lib_shift should be defined in c++2b"
-# endif
-# if __cpp_lib_shift != 201806L
-# error "__cpp_lib_shift should have the value 201806L in c++2b"
-# endif
-# else // _LIBCPP_VERSION
-# ifdef __cpp_lib_shift
-# error "__cpp_lib_shift should not be defined because it is unimplemented in libc++!"
-# endif
+# ifndef __cpp_lib_shift
+# error "__cpp_lib_shift should be defined in c++2b"
+# endif
+# if __cpp_lib_shift != 201806L
+# error "__cpp_lib_shift should have the value 201806L in c++2b"
# endif
# if !defined(_LIBCPP_VERSION)
diff --git a/utils/generate_feature_test_macro_components.py b/utils/generate_feature_test_macro_components.py
index dc9a5bc..00de15d 100755
--- a/utils/generate_feature_test_macro_components.py
+++ b/utils/generate_feature_test_macro_components.py
@@ -522,7 +522,6 @@
"name": "__cpp_lib_shift",
"values": { "c++20": 201806 },
"headers": ["algorithm"],
- "unimplemented": True,
}, {
"name": "__cpp_lib_smart_ptr_for_overwrite",
"values": { "c++20": 202002 },