[libc++] s/_VSTD::declval/declval/g. NFCI.

[libc++][NFC] Remove _VSTD:: when not needed.

Reviewed By: #libc, Quuxplusone

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

[libc++] NFC: Normalize `#endif //` comment indentation

[libc++] Further improve the contiguous-iterator story, and fix some bugs.

- Quality-of-implementation: Avoid calling __unwrap_iter in constexpr contexts.
The user might conceivably write a cont

[libc++] Further improve the contiguous-iterator story, and fix some bugs.

- Quality-of-implementation: Avoid calling __unwrap_iter in constexpr contexts.
The user might conceivably write a contiguous iterator where normal iterator
arithmetic is constexpr-friendly but `std::to_address(it)` isn't.

- Bugfix: When you pass contiguous iterators to `std::copy`, you should get
back your contiguous iterator type, not a raw pointer. That means that
libc++ can't `__unwrap_iter` unless it also does `__rewrap_iter`.
Fortunately, this is implementable.

- Improve test coverage of the new `contiguous_iterator` test iterator.
This catches the bug described above.

- Tests: Stop testing that we can `std::copy` //into// an `input_iterator`.
Our test iterators may currently support that, but it seems nonsensical to me.

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

show more ...

Revert "Revert "[libc++] [P0879] constexpr std::nth_element, and rewrite its tests.""

This reverts commit b6ffece32035a90d181101f356bd9c04ea1d3122.

The bug is now fixed (it was a stupid cut-and-pas

Revert "Revert "[libc++] [P0879] constexpr std::nth_element, and rewrite its tests.""

This reverts commit b6ffece32035a90d181101f356bd9c04ea1d3122.

The bug is now fixed (it was a stupid cut-and-paste kind of error),
and the regression test added. The new patch is also simpler than the old one!

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

show more ...

Revert "[libc++] [P0879] constexpr std::nth_element, and rewrite its tests."

This reverts commit 207d4be4d9d39fbb9aca30e5d5d11245db9bccc1 due to returning incorrect results. Regression test case pos

Revert "[libc++] [P0879] constexpr std::nth_element, and rewrite its tests."

This reverts commit 207d4be4d9d39fbb9aca30e5d5d11245db9bccc1 due to returning incorrect results. Regression test case posted in D96074.

show more ...

[libc++] [P0879] constexpr std::sort

This completes libc++'s implementation of
P0879 "Constexpr for swap and swap related functions."
http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2018/p0879r0.

[libc++] [P0879] constexpr std::sort

This completes libc++'s implementation of
P0879 "Constexpr for swap and swap related functions."
http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2018/p0879r0.html

For the feature-macro adjustment, see
https://cplusplus.github.io/LWG/issue3256

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

show more ...

[libc++] Rationalize our treatment of contiguous iterators and __unwrap_iter().

- Implement C++20's changes to `reverse_iterator`, so that it won't be
accidentally counted as a contiguous iterat

[libc++] Rationalize our treatment of contiguous iterators and __unwrap_iter().

- Implement C++20's changes to `reverse_iterator`, so that it won't be
accidentally counted as a contiguous iterator in C++20 mode.
- Implement C++20's changes to `move_iterator` as well.
- `move_iterator` should not be contiguous. This fixes a bug where
we optimized `std::copy`-of-move-iterators in an observable way.
Add a regression test for that bugfix.
- Add libcxx tests for `__is_cpp17_contiguous_iterator` of all relevant
standard iterator types. Particularly check that vector::iterator
is still considered contiguous in all C++ modes, even C++03.

After this patch, there continues to be no supported way to write your
own iterator type in C++17-and-earlier such that libc++ will consider it
"contiguous"; however, we now fully support the C++20 approach (in C++20
mode only). If you want user-defined contiguous iterators in C++17-and-earlier,
libc++'s position is "please upgrade to C++20."

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

show more ...

[libc++] [P0879] constexpr std::nth_element, and rewrite its tests.

This patch is more than just adding the `constexpr` keyword, because
the old code relied on `goto`, and `goto` is not constexpr-fr

[libc++] [P0879] constexpr std::nth_element, and rewrite its tests.

This patch is more than just adding the `constexpr` keyword, because
the old code relied on `goto`, and `goto` is not constexpr-friendly.
Refactor to eliminate `goto`, and then mark it as constexpr in C++20.

I freely admit that the name `__nth_element_partloop` is bad;
I couldn't find any better name because I don't really know
what this loop is doing, conceptually. Vice versa, I think
`__nth_element_find_guard` has a decent name.

Now the only one we're still missing from P0879 is `sort`.

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

show more ...

[libc++] [P0879] constexpr heap and partial_sort algorithms

Now the only ones we're still missing from P0879
are `sort` and `nth_element`.

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

[libc++] [P0879] constexpr std::reverse, partition, *_permutation.

After this patch, the only parts of P0879 that remain missing will be
std::nth_element, std::sort, and the heap/partial_sort algori

[libc++] [P0879] constexpr std::reverse, partition, *_permutation.

After this patch, the only parts of P0879 that remain missing will be
std::nth_element, std::sort, and the heap/partial_sort algorithms.

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

show more ...

[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/sc

[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

show more ...

[libc++] [P0935] [C++20] Eradicating unnecessarily explicit default constructors from the standard library.

http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2018/p0935r0.html

Reviewed By: ldionne

[libc++] [P0935] [C++20] Eradicating unnecessarily explicit default constructors from the standard library.

http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2018/p0935r0.html

Reviewed By: ldionne, #libc

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

show more ...

[libc++] Add a missing `<_Compare>` template argument.

Sometimes `_Compare` is an lvalue reference type, so letting it be
deduced is pretty much always wrong. (Well, less efficient than
it could be,

[libc++] Add a missing `<_Compare>` template argument.

Sometimes `_Compare` is an lvalue reference type, so letting it be
deduced is pretty much always wrong. (Well, less efficient than
it could be, anyway.)

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

show more ...

[libc++] Consistently replace `::new(__p) T` with `::new ((void*)__p) T`. NFCI.

Everywhere, normalize the whitespace to `::new (EXPR) T`.
Everywhere, normalize the spelling of the cast to `(void*)EX

[libc++] Consistently replace `::new(__p) T` with `::new ((void*)__p) T`. NFCI.

Everywhere, normalize the whitespace to `::new (EXPR) T`.
Everywhere, normalize the spelling of the cast to `(void*)EXPR`.

Without the cast to `(void*)`, the expression triggers ADL on GCC.
(I think this is a GCC bug: https://gcc.gnu.org/bugzilla/show_bug.cgi?id=98249)
Even if it doesn't trigger ADL, it still seems incorrect to use any argument
that's not exactly `(void*)` because that opens the possibility of overload
resolution picking a user-defined overload of `operator new`, which would be
wrong.

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

show more ...

[libc++] Fix some one-off typos in comments. NFCI.

[libc++] s/Birdirectional/Bidirectional/g. NFCI.

[libc++] Add _VSTD:: qualifications to ADL-proof <algorithm>.

Relevant blog post: https://quuxplusone.github.io/blog/2019/09/26/uglification-doesnt-stop-adl/

Differential Revision: https://reviews.

[libc++] Add _VSTD:: qualifications to ADL-proof <algorithm>.

Relevant blog post: https://quuxplusone.github.io/blog/2019/09/26/uglification-doesnt-stop-adl/

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

show more ...

[libc++] ADL-proof <iterator>. `__convert_to_integral` is not a customization point.

The interesting change here is that we no longer consider `__convert_to_integral`
an ADL customization point for

[libc++] ADL-proof <iterator>. `__convert_to_integral` is not a customization point.

The interesting change here is that we no longer consider `__convert_to_integral`
an ADL customization point for the user's types. I think the new behavior
is defensible. The old behavior had come from D7449, where Marshall explicitly
said "people can't define their own [`__convert_to_integral` overloads]."

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

show more ...

[libc++] Update the commented "synopsis" in <algorithm> to match current reality.

The synopsis now reflects what's implemented. It does NOT reflect
all of what's specified in C++20. The "constexpr i

[libc++] Update the commented "synopsis" in <algorithm> to match current reality.

The synopsis now reflects what's implemented. It does NOT reflect
all of what's specified in C++20. The "constexpr in C++20" markings
are still missing from these 12 algorithms, because they are still
unimplemented by libc++:

reverse partition sort nth_element next_permutation prev_permutation
push_heap pop_heap make_heap sort_heap partial_sort partial_sort_copy

All of the above algorithms were excluded from [P0202].

All of the above algorithms were made constexpr in [P0879] (along with
swap_ranges, iter_swap, and rotate — we've already implemented those three).

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

show more ...

[libc++] [P0202] constexpr set_union, set_difference, set_symmetric_difference, merge

These had been waiting on the ability to use `std::copy` from
constexpr code (which in turn had been waiting on

[libc++] [P0202] constexpr set_union, set_difference, set_symmetric_difference, merge

These had been waiting on the ability to use `std::copy` from
constexpr code (which in turn had been waiting on the ability to
use `is_constant_evaluated()` to switch between `memmove` and non-`memmove`
implementations of `std::copy`). That work landed a while ago,
so these algorithms can all be constexpr in C++20 now.

Simultaneously, update the tests for the set algorithms.

- Use an element type with "equivalent but not identical" values.
- The custom-comparator tests now pass something different from `operator<`.
- Make the constexpr coverage match the non-constexpr coverage.

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

show more ...

[libc++] fix std::sort(T**, T**)

previously, invocations of std::sort(T**, T**) casted the arguments to
(size_t *). this breaks sorting on systems for which pointers don't fit
in a size_t. change th

[libc++] fix std::sort(T**, T**)

previously, invocations of std::sort(T**, T**) casted the arguments to
(size_t *). this breaks sorting on systems for which pointers don't fit
in a size_t. change the cast to (uintptr_t *) and add a test.

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

show more ...

[libc++] Consistently replace `std::` qualification with `_VSTD::` or nothing. NFCI.

I used a lot of `git grep` to find places where `std::` was being used
outside of comments and assert-messages. T

[libc++] Consistently replace `std::` qualification with `_VSTD::` or nothing. NFCI.

I used a lot of `git grep` to find places where `std::` was being used
outside of comments and assert-messages. There were three outcomes:

- Qualified function calls, e.g. `std::move` becomes `_VSTD::move`.
This is the most common case.

- Typenames that don't need qualification, e.g. `std::allocator` becomes `allocator`.
Leaving these as `_VSTD::allocator` would also be fine, but I decided
that removing the qualification is more consistent with existing practice.

- Names that specifically need un-versioned `std::` qualification,
or that I wasn't sure about. For example, I didn't touch any code in
<atomic>, <math.h>, <new>, or any ext/ or experimental/ headers;
and I didn't touch any instances of `std::type_info`.

In some deduction guides, we were accidentally using `class Alloc = typename std::allocator<T>`,
despite `std::allocator<T>`'s type-ness not being template-dependent.
Because `std::allocator` is a qualified name, this did parse as we intended;
but what we meant was simply `class Alloc = allocator<T>`.

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

show more ...

[libc++] Replace several uses of 0 by nullptr

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

[libc++] Remove _LIBCPP_CONSTEXPR_AFTER_CXX17_WITH_IS_CONSTANT_EVALUATED.

Zoe Carver says: "We decided that libc++ only supports C++20 constexpr algorithms
when `is_constant_evaluated` is also suppo

[libc++] Remove _LIBCPP_CONSTEXPR_AFTER_CXX17_WITH_IS_CONSTANT_EVALUATED.

Zoe Carver says: "We decided that libc++ only supports C++20 constexpr algorithms
when `is_constant_evaluated` is also supported. Here's a link to the discussion."
https://reviews.llvm.org/D65721#inline-735682

Remove _LIBCPP_HAS_NO_BUILTIN_IS_CONSTANT_EVALUATED from tests, too.
See Louis's 5911e6a8857f146fb5a8f23af1d768aba25e7c3e if needed to fix bots.
I've applied `UNSUPPORTED: clang-8` preemptively to the altered tests;
I don't know for sure that this was needed, because no clang-8 buildbots
are triggered on pull requests.

show more ...