[libc++] Implement [P0769] "Add shift to algorithm" (shift_left, shift_right)

[• Quuxplusone]

Summary

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.

[• Quuxplusone]

Rebased on main. @ldionne ping! :)

[ldionne]

Can you also grab the tests from https://reviews.llvm.org/D60027? Generally speaking, while programmatic tests (like the two nested loops you used) are great because it gives us great coverage, however I try to strike a balance and also have at least some basic and really dumb test cases written entirely manually. This avoids the risk of a bug in the tests.

For some reason, that revision doesn't show up in the "Open Libc++ Reviews" query. I'll try to understand why and fix it.

libcxx/test/std/algorithms/alg.modifying.operations/alg.shift/shift_left.pass.cpp

33

int k = 0;

[• Quuxplusone]

Merged some test cases from D60027.

[zoecarver]

@Quuxplusone I like this patch a lot better than mine. It seems like this implementation is essentially following the sample in the paper. I was meaning to update mine to use that approach but didn't find the time/remember. Anyway, this looks good to me, thanks!

[ldionne]

I'm not done with the review, but I figured I might as well give you the feedback I have right away.

It generally looks good, but I think you might have forgotten about n < 0 in both algorithms.

libcxx/include/algorithm

310

shift_right isn't constexpr in the paper (haven't looked at why yet). We're not allowed to add this as an extension.

3269

Just constexpr should be OK, since this is only enabled after C++17 anyway.

3274

Should we use n <= 0 here instead? This would make it clearer that nothing happens when n < 0.

And actually, it seems to me that the random access iterator path doesn't behave correctly when n < 0. Indeed, we'll move [__first + __n, __last) (where __first + __n lies *before* __first since __n is negative) into __first. If I'm not mistaken, please fix and add tests for this to both algorithms.

3296

inline is unnecessary here, a template already has the right linkage. Applies above too.

3310

If __n is negative, __m is out-of-bounds, and the call to move_backwards is UB anyway because last is inside (first, m]. Please fix and add tests to cover this case.

3331

Do you mean an __n-element window [__trail, __lead) instead (half-open interval)?

3336–3361

Note to self: haven't reviewed this in detail yet.

libcxx/test/std/algorithms/alg.modifying.operations/alg.shift/shift_right.pass.cpp

14

Remove constexpr

[• Quuxplusone]

libcxx/include/algorithm

310

The P-numbered paper doesn't match what was actually landed in http://eel.is/c++draft/alg.shift .
What was landed looks vastly more "C++ library-esque": constexpr in the right places, more UB instead of special-case defined behavior, etc.

3274

http://eel.is/c++draft/alg.shift n >= 0 is a precondition on both algorithms.

3296

This is how all of the algorithms are done, though, from all_of on line 852 all the way to prev_permutation on line 5840. I don't know why they all use inline, but shift_right shouldn't be a special case.

3310

http://eel.is/c++draft/alg.shift n >= 0 is a precondition.

3331

Yes. Also, it's not really "sliding"; it's kind of... leapfrogging? Glitching? We process the window [0, n) and then [n, 2*n) and then [2*n, 3*n) and so on. So this description is already kind of askew. But I'll happily change ( to [, anyway.

libcxx/test/std/algorithms/alg.modifying.operations/alg.shift/shift_right.pass.cpp

14

Not done because I assume this comment was based on the P-numbered paper (the standard standard does have constexpr)

[• Quuxplusone]

(->[
_LIBCPP_CONSTEXPR_AFTER_CXX17->constexpr

[ldionne]

The P-numbered paper doesn't match what was actually landed in http://eel.is/c++draft/alg.shift .

Ah ah. How confusing. Now it makes more sense.

[danra]

In D93819#2520124, @ldionne wrote:

The P-numbered paper doesn't match what was actually landed in http://eel.is/c++draft/alg.shift .

Ah ah. How confusing. Now it makes more sense.

Sorry for being late.
I agree it's confusing. Since there were multiple papers modifying the shift algorithms wording, LWG requested the changes be made in http://open-std.org/JTC1/SC22/WG21/docs/papers/2020/p1243r4.pdf , which was approved in the straw polls at https://wiki.edg.com/bin/view/Wg21prague/StrawPolls

libcxx/docs/Cxx2aStatusPaperStatus.csv

 "`P0528R3 <https://wg21.link/P0528R3>`__","CWG","The Curious Case of Padding Bits, Featuring Atomic Compare-and-Exchange","Rapperswil","",""
 "`P0542R5 <https://wg21.link/P0542R5>`__","CWG","Support for contract based programming in C++","Rapperswil","*Removed in Cologne*","n/a"
 "`P0556R3 <https://wg21.link/P0556R3>`__","LWG","Integral power-of-2 operations","Rapperswil","|Complete|","9.0"
 "`P0619R4 <https://wg21.link/P0619R4>`__","LWG","Reviewing Deprecated Facilities of C++17 for C++20","Rapperswil","|Partial| [#note-P0619]_",""
 "`P0646R1 <https://wg21.link/P0646R1>`__","LWG","Improving the Return Value of Erase-Like Algorithms","Rapperswil","|Complete|","10.0"
 "`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"
 "`P0892R2 <https://wg21.link/P0892R2>`__","CWG","explicit(bool)","Rapperswil","",""
 "`P0898R3 <https://wg21.link/P0898R3>`__","LWG","Standard Library Concepts","Rapperswil","",""
 "`P0935R0 <https://wg21.link/P0935R0>`__","LWG","Eradicating unnecessarily explicit default constructors from the standard library","Rapperswil","",""
 "`P0941R2 <https://wg21.link/P0941R2>`__","CWG","Integrating feature-test macros into the C++ WD","Rapperswil","|In Progress|",""
 "`P1023R0 <https://wg21.link/P1023R0>`__","LWG","constexpr comparison operators for std::array","Rapperswil","|Complete|","8.0"

libcxx/docs/FeatureTestMacroTable.rst

.. table:: Current Status
     ``__cpp_lib_polymorphic_allocator``               *unimplemented*
     ------------------------------------------------- -----------------
     ``__cpp_lib_ranges``                              *unimplemented*
     ------------------------------------------------- -----------------
     ``__cpp_lib_remove_cvref``                        ``201711L``
     ------------------------------------------------- -----------------
     ``__cpp_lib_semaphore``                           ``201907L``
     ------------------------------------------------- -----------------
-    ``__cpp_lib_shift``                               *unimplemented*
+    ``__cpp_lib_shift``                               ``201806L``
     ------------------------------------------------- -----------------
     ``__cpp_lib_smart_ptr_for_overwrite``             *unimplemented*
     ------------------------------------------------- -----------------
     ``__cpp_lib_source_location``                     *unimplemented*
     ------------------------------------------------- -----------------
     ``__cpp_lib_span``                                ``202002L``
     ------------------------------------------------- -----------------
     ``__cpp_lib_ssize``                               ``201902L``

libcxx/include/algorithm

     SampleIterator sample(PopulationIterator first, PopulationIterator last,
                           SampleIterator out, Distance n,
                           UniformRandomBitGenerator&& g); // C++17
 
 template<class RandomAccessIterator, class UniformRandomNumberGenerator>
     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);
 
 template <class ForwardIterator, class Predicate>
     ForwardIterator
     partition(ForwardIterator first, ForwardIterator last, Predicate pred);
 

         {
             difference_type __i = __uid(__g, _Pp(0, __d));
             if (__i != difference_type(0))
                 swap(*__first, *(__first + __i));
         }
     }
 }
 
+#if _LIBCPP_STD_VER > 17
+
+// shift_left, shift_right
+
+template <class _ForwardIterator>
+inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
+_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 _LIBCPP_CONSTEXPR_AFTER_CXX17
+_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)
 {
     for (; __first != __last; ++__first)
         if (!__pred(*__first))
             break;
     if ( __first == __last )

libcxx/include/version

 #   define __cpp_lib_math_constants                     201907L
 # endif
 // # define __cpp_lib_polymorphic_allocator                201902L
 // # define __cpp_lib_ranges                               201811L
 # define __cpp_lib_remove_cvref                         201711L
 # 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
 # define __cpp_lib_ssize                                201902L
 # define __cpp_lib_starts_ends_with                     201711L
 # undef  __cpp_lib_string_view
 # define __cpp_lib_string_view                          201803L
 // # define __cpp_lib_syncbuf                              201803L

libcxx/test/std/algorithms/alg.modifying.operations/alg.shift/shift_left.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
+//
+//===----------------------------------------------------------------------===//
+
+// 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;
+}

libcxx/test/std/algorithms/alg.modifying.operations/alg.shift/shift_right.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
+//
+//===----------------------------------------------------------------------===//
+
+// 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;
+}

libcxx/test/std/language.support/support.limits/support.limits.general/algorithm.version.pass.cpp

 
 # ifndef __cpp_lib_sample
 #   error "__cpp_lib_sample should be defined in c++20"
 # endif
 # if __cpp_lib_sample != 201603L
 #   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
-# 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
 
 # ifndef __cpp_lib_clamp
 #   error "__cpp_lib_clamp should be defined in c++2b"
 # endif
 # if __cpp_lib_clamp != 201603L
 #   error "__cpp_lib_clamp should have the value 201603L in c++2b"

 
 # ifndef __cpp_lib_sample
 #   error "__cpp_lib_sample should be defined in c++2b"
 # endif
 # if __cpp_lib_sample != 201603L
 #   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
-# 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
 
 int main(int, char**) { return 0; }

libcxx/test/std/language.support/support.limits/support.limits.general/version.version.pass.cpp

 #     error "__cpp_lib_shared_timed_mutex should have the value 201402L in c++20"
 #   endif
 # else
 #   ifdef __cpp_lib_shared_timed_mutex
 #     error "__cpp_lib_shared_timed_mutex should not be defined when !defined(_LIBCPP_HAS_NO_THREADS) is not defined!"
 #   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)
 #   ifndef __cpp_lib_smart_ptr_for_overwrite
 #     error "__cpp_lib_smart_ptr_for_overwrite should be defined in c++20"
 #   endif
 #   if __cpp_lib_smart_ptr_for_overwrite != 202002L
 #     error "__cpp_lib_smart_ptr_for_overwrite should have the value 202002L in c++20"

 #     error "__cpp_lib_shared_timed_mutex should have the value 201402L in c++2b"
 #   endif
 # else
 #   ifdef __cpp_lib_shared_timed_mutex
 #     error "__cpp_lib_shared_timed_mutex should not be defined when !defined(_LIBCPP_HAS_NO_THREADS) is not defined!"
 #   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)
 #   ifndef __cpp_lib_smart_ptr_for_overwrite
 #     error "__cpp_lib_smart_ptr_for_overwrite should be defined in c++2b"
 #   endif
 #   if __cpp_lib_smart_ptr_for_overwrite != 202002L
 #     error "__cpp_lib_smart_ptr_for_overwrite should have the value 202002L in c++2b"

libcxx/utils/generate_feature_test_macro_components.py

feature_test_macros = [ add_version_header(x) for x in [
     "values": { "c++14": 201402 },
     "headers": ["shared_mutex"],
     "depends": "!defined(_LIBCPP_HAS_NO_THREADS)",
     "internal_depends": "!defined(_LIBCPP_HAS_NO_THREADS)",
   }, {
     "name": "__cpp_lib_shift",
     "values": { "c++20": 201806 },
     "headers": ["algorithm"],
-    "unimplemented": True,
   }, {
     "name": "__cpp_lib_smart_ptr_for_overwrite",
     "values": { "c++20": 202002 },
     "headers": ["memory"],
     "unimplemented": True,
   }, {
     "name": "__cpp_lib_source_location",
     "values": { "c++20": 201907 },