[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

15

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

15

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","",""
 "`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","",""
 "`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_is_constant_evaluated``               ``201811L``
     ------------------------------------------------- -----------------
     ``__cpp_lib_list_remove_return_type``             ``201806L``
     ------------------------------------------------- -----------------
     ``__cpp_lib_math_constants``                      ``201907L``
     ------------------------------------------------- -----------------
     ``__cpp_lib_ranges``                              *unimplemented*
     ------------------------------------------------- -----------------
+    ``__cpp_lib_shift``                               ``201806L``
+    ------------------------------------------------- -----------------
     ``__cpp_lib_span``                                ``202002L``
     ------------------------------------------------- -----------------
     ``__cpp_lib_three_way_comparison``                *unimplemented*
     ------------------------------------------------- -----------------
     ``__cpp_lib_to_array``                            ``201907L``
     ================================================= =================
 

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

 __cpp_lib_result_of_sfinae                              201210L <functional> <type_traits>
 __cpp_lib_robust_nonmodifying_seq_ops                   201304L <algorithm>
 __cpp_lib_sample                                        201603L <algorithm>
 __cpp_lib_scoped_lock                                   201703L <mutex>
 __cpp_lib_shared_mutex                                  201505L <shared_mutex>
 __cpp_lib_shared_ptr_arrays                             201611L <memory>
 __cpp_lib_shared_ptr_weak_type                          201606L <memory>
 __cpp_lib_shared_timed_mutex                            201402L <shared_mutex>
+__cpp_lib_shift                                         201806L <algorithm>
 __cpp_lib_span                                          202002L <span>
 __cpp_lib_string_udls                                   201304L <string>
 __cpp_lib_string_view                                   201606L <string> <string_view>
 __cpp_lib_three_way_comparison                          201711L <compare>
 __cpp_lib_to_array                                      201907L <array>
 __cpp_lib_to_chars                                      201611L <utility>
 __cpp_lib_transformation_trait_aliases                  201304L <type_traits>
 __cpp_lib_transparent_operators                         201510L <functional>

 # if !defined(_LIBCPP_HAS_NO_BUILTIN_IS_CONSTANT_EVALUATED)
 #   define __cpp_lib_is_constant_evaluated              201811L
 # endif
 # define __cpp_lib_list_remove_return_type              201806L
 # if defined(__cpp_concepts) && __cpp_concepts >= 201811L
 #   define __cpp_lib_math_constants                     201907L
 # endif
 // # define __cpp_lib_ranges                               201811L
+# define __cpp_lib_shift                                201806L
 # define __cpp_lib_span                                 202002L
 // # define __cpp_lib_three_way_comparison                 201711L
 # define __cpp_lib_to_array                             201907L
 #endif
 
 #endif // _LIBCPP_VERSIONH

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 (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));
+            }
+        }
+    }
+    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));
+            }
+        }
+    }
+    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

 
 /*  Constant                                 Value
     __cpp_lib_clamp                          201603L [C++17]
     __cpp_lib_constexpr_swap_algorithms      201806L [C++2a]
     __cpp_lib_parallel_algorithm             201603L [C++17]
     __cpp_lib_ranges                         201811L [C++2a]
     __cpp_lib_robust_nonmodifying_seq_ops    201304L [C++14]
     __cpp_lib_sample                         201603L [C++17]
+    __cpp_lib_shift                          201806L [C++2a]
 */
 
 #include <algorithm>
 #include "test_macros.h"
 
 #if TEST_STD_VER < 14
 
 # ifdef __cpp_lib_clamp

 # ifdef __cpp_lib_robust_nonmodifying_seq_ops
 #   error "__cpp_lib_robust_nonmodifying_seq_ops should not be defined before c++14"
 # endif
 
 # ifdef __cpp_lib_sample
 #   error "__cpp_lib_sample should not be defined before c++17"
 # endif
 
+# ifdef __cpp_lib_shift
+#   error "__cpp_lib_shift should not be defined before c++2a"
+# endif
+
 #elif TEST_STD_VER == 14
 
 # ifdef __cpp_lib_clamp
 #   error "__cpp_lib_clamp should not be defined before c++17"
 # endif
 
 # ifdef __cpp_lib_constexpr_swap_algorithms
 #   error "__cpp_lib_constexpr_swap_algorithms should not be defined before c++2a"

 # if __cpp_lib_robust_nonmodifying_seq_ops != 201304L
 #   error "__cpp_lib_robust_nonmodifying_seq_ops should have the value 201304L in c++14"
 # endif
 
 # ifdef __cpp_lib_sample
 #   error "__cpp_lib_sample should not be defined before c++17"
 # endif
 
+# ifdef __cpp_lib_shift
+#   error "__cpp_lib_shift should not be defined before c++2a"
+# endif
+
 #elif TEST_STD_VER == 17
 
 # ifndef __cpp_lib_clamp
 #   error "__cpp_lib_clamp should be defined in c++17"
 # endif
 # if __cpp_lib_clamp != 201603L
 #   error "__cpp_lib_clamp should have the value 201603L in c++17"
 # endif

 
 # ifndef __cpp_lib_sample
 #   error "__cpp_lib_sample should be defined in c++17"
 # endif
 # if __cpp_lib_sample != 201603L
 #   error "__cpp_lib_sample should have the value 201603L in c++17"
 # endif
 
+# ifdef __cpp_lib_shift
+#   error "__cpp_lib_shift should not be defined before c++2a"
+# endif
+
 #elif TEST_STD_VER > 17
 
 # ifndef __cpp_lib_clamp
 #   error "__cpp_lib_clamp should be defined in c++2a"
 # endif
 # if __cpp_lib_clamp != 201603L
 #   error "__cpp_lib_clamp should have the value 201603L in c++2a"
 # endif

 
 # ifndef __cpp_lib_sample
 #   error "__cpp_lib_sample should be defined in c++2a"
 # endif
 # if __cpp_lib_sample != 201603L
 #   error "__cpp_lib_sample should have the value 201603L in c++2a"
 # endif
 
+# ifndef __cpp_lib_shift
+#   error "__cpp_lib_shift should be defined in c++2a"
+# endif
+# if __cpp_lib_shift != 201806L
+#   error "__cpp_lib_shift should have the value 201806L in c++2a"
+# endif
+
 #endif // TEST_STD_VER > 17
 
 int main(int, char**) { return 0; }

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

/*  Constant                                       Value
     __cpp_lib_result_of_sfinae                     201210L [C++14]
     __cpp_lib_robust_nonmodifying_seq_ops          201304L [C++14]
     __cpp_lib_sample                               201603L [C++17]
     __cpp_lib_scoped_lock                          201703L [C++17]
     __cpp_lib_shared_mutex                         201505L [C++17]
     __cpp_lib_shared_ptr_arrays                    201611L [C++17]
     __cpp_lib_shared_ptr_weak_type                 201606L [C++17]
     __cpp_lib_shared_timed_mutex                   201402L [C++14]
+    __cpp_lib_shift                                201806L [C++2a]
     __cpp_lib_span                                 202002L [C++2a]
     __cpp_lib_string_udls                          201304L [C++14]
     __cpp_lib_string_view                          201606L [C++17]
     __cpp_lib_three_way_comparison                 201711L [C++2a]
     __cpp_lib_to_array                             201907L [C++2a]
     __cpp_lib_to_chars                             201611L [C++17]
     __cpp_lib_transformation_trait_aliases         201304L [C++14]
     __cpp_lib_transparent_operators                201210L [C++14]

 # ifdef __cpp_lib_shared_ptr_weak_type
 #   error "__cpp_lib_shared_ptr_weak_type should not be defined before c++17"
 # endif
 
 # ifdef __cpp_lib_shared_timed_mutex
 #   error "__cpp_lib_shared_timed_mutex should not be defined before c++14"
 # endif
 
+# ifdef __cpp_lib_shift
+#   error "__cpp_lib_shift should not be defined before c++2a"
+# endif
+
 # ifdef __cpp_lib_span
 #   error "__cpp_lib_span should not be defined before c++2a"
 # endif
 
 # ifdef __cpp_lib_string_udls
 #   error "__cpp_lib_string_udls should not be defined before c++14"
 # endif
 

 #     error "__cpp_lib_shared_timed_mutex should have the value 201402L in c++14"
 #   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
 
+# ifdef __cpp_lib_shift
+#   error "__cpp_lib_shift should not be defined before c++2a"
+# endif
+
 # ifdef __cpp_lib_span
 #   error "__cpp_lib_span should not be defined before c++2a"
 # endif
 
 # ifndef __cpp_lib_string_udls
 #   error "__cpp_lib_string_udls should be defined in c++14"
 # endif
 # if __cpp_lib_string_udls != 201304L

 #     error "__cpp_lib_shared_timed_mutex should have the value 201402L in c++17"
 #   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
 
+# ifdef __cpp_lib_shift
+#   error "__cpp_lib_shift should not be defined before c++2a"
+# endif
+
 # ifdef __cpp_lib_span
 #   error "__cpp_lib_span should not be defined before c++2a"
 # endif
 
 # ifndef __cpp_lib_string_udls
 #   error "__cpp_lib_string_udls should be defined in c++17"
 # endif
 # if __cpp_lib_string_udls != 201304L

 #     error "__cpp_lib_shared_timed_mutex should have the value 201402L in c++2a"
 #   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
 
+# ifndef __cpp_lib_shift
+#   error "__cpp_lib_shift should be defined in c++2a"
+# endif
+# if __cpp_lib_shift != 201806L
+#   error "__cpp_lib_shift should have the value 201806L in c++2a"
+# endif
+
 # ifndef __cpp_lib_span
 #   error "__cpp_lib_span should be defined in c++2a"
 # endif
 # if __cpp_lib_span != 202002L
 #   error "__cpp_lib_span should have the value 202002L in c++2a"
 # endif
 
 # ifndef __cpp_lib_string_udls

libcxx/utils/generate_feature_test_macro_components.py

# C++2a
     "values": { "c++2a": int(201811) },
     "headers": ["unordered_map", "unordered_set"],
   }, {
     "name": "__cpp_lib_ranges",
     "values": { "c++2a": int(201811) },
     "headers": ["algorithm", "functional", "iterator", "memory", "ranges"],
     "unimplemented": True,
   }, {
+    "name": "__cpp_lib_shift",
+    "values": { "c++2a": int(201806) },
+    "headers": ["algorithm"],
+  }, {
     "name": "__cpp_lib_bit_cast",
     "values": { "c++2a": int(201806) },
     "headers": ["bit"],
     "unimplemented": True,
   }, {
     "name": "__cpp_lib_atomic_ref",
     "values": { "c++2a": int(201806) },
     "headers": ["atomic"],