[libc++][ranges] Implement `std::ranges::partial_sort_copy`.

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

(cherry picked from commit db7d7959787ed68f037e2a6e5a70bb0d8c17ab27)

[libc++][ranges] Implement `ranges::shuffle`.

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

[libc++][ranges] Implement `ranges::partial_sort`.

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

[libc++][ranges] Make range algorithms support proxy iterators

Also test all the range algorithms to verify the support.

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

[libc++] Make _LIBCPP_DEBUG_RANDOMIZE_RANGE a function

Reviewed By: ldionne, Mordante, var-const, #libc

Spies: mgorny, libcxx-commits

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

[libc++] Make the Debug mode a configuration-time only option

The debug mode has been broken pretty much ever since it was shipped
because it was possible to enable the debug mode in user code witho

[libc++] Make the Debug mode a configuration-time only option

The debug mode has been broken pretty much ever since it was shipped
because it was possible to enable the debug mode in user code without
actually enabling it in the dylib, leading to ODR violations that
caused various kinds of failures.

This commit makes the debug mode a knob that is configured when
building the library and which can't be changed afterwards. This is
less flexible for users, however it will actually work as intended
and it will allow us, in the future, to add various kinds of checks
that do not assume the same ABI as the normal library. Furthermore,
this will make the debug mode more robust, which means that vendors
might be more tempted to support it properly, which hasn't been the
case with the current debug mode.

This patch shouldn't break any user code, except folks who are building
against a library that doesn't have the debug mode enabled and who try
to enable the debug mode in their code. Such users will get a compile-time
error explaining that this configuration isn't supported anymore.

In the future, we should further increase the granularity of the debug
mode checks so that we can cherry-pick which checks to enable, like we
do for unspecified behavior randomization.

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

show more ...

[libc++] Revert "Protect users from relying on detail headers" & related changes

This commit reverts 5aaefa51 (and also partly 7f285f48e77 and b6d75682f9,
which were related to the original commit).

[libc++] Revert "Protect users from relying on detail headers" & related changes

This commit reverts 5aaefa51 (and also partly 7f285f48e77 and b6d75682f9,
which were related to the original commit). As landed, 5aaefa51 had
unintended consequences on some downstream bots and didn't have proper
coverage upstream due to a few subtle things. Implementing this is
something we should do in libc++, however we'll first need to address
a few issues listed in https://reviews.llvm.org/D106124#3349710.

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

show more ...

[libcxx][modules] protects users from relying on detail headers

libc++ has started splicing standard library headers into much more
fine-grained content for maintainability. It's very likely that ou

[libcxx][modules] protects users from relying on detail headers

libc++ has started splicing standard library headers into much more
fine-grained content for maintainability. It's very likely that outdated
and naive tooling (some of which is outside of LLVM's scope) will
suggest users include things such as <__ranges/access.h> instead of
<ranges>, and Hyrum's law suggests that users will eventually begin to
rely on this without the help of tooling. As such, this commit
intends to protect users from themselves, by making it a hard error for
anyone outside of the standard library to include libc++ detail headers.

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

show more ...

[libc++] Normalize all our '#pragma GCC system_header', and regression-test.

Now we'll notice if a header forgets to include this magic phrase.

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

[libc++] Normalize all our '#pragma GCC system_header', and regression-test.

Now we'll notice if a header forgets to include this magic phrase.

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

show more ...

[libc++] Alphabetize header #includes. NFCI.

The NFC part of D116809. We still want to enforce this in CI,
but the mechanism for that is still to-be-determined.

Differential Revision: https://revie

[libc++] Alphabetize header #includes. NFCI.

The NFC part of D116809. We still want to enforce this in CI,
but the mechanism for that is still to-be-determined.

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

show more ...

[libc++] Fix whitespace in __partial_sort. NFC.

[libc++] Add an early return for __partial_sort of an empty range.

If `__first == __middle`, then `partial_sort` is a no-op; don't
bother to iterate all the way from `__middle` to `__end`.

Fixes #4

[libc++] Add an early return for __partial_sort of an empty range.

If `__first == __middle`, then `partial_sort` is a no-op; don't
bother to iterate all the way from `__middle` to `__end`.

Fixes #49431.

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

show more ...

[libc++] [NFC] Remove an unused parameter from `__sift_down`.

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

[libc++] Unspecified behavior randomization in libc++

This effort is dedicated to deflake the tests of the users which depend
on the unspecified behavior of algorithms and containers. This also
migh

[libc++] Unspecified behavior randomization in libc++

This effort is dedicated to deflake the tests of the users which depend
on the unspecified behavior of algorithms and containers. This also
might help updating the sorting algorithm in libcxx which has the
quadratic worst case in the future or at least create a new one under
flag.

For detailed design, please see the design doc I provide in the patch.

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

show more ...

[libc++][NFC] Remove useless _LIBCPP_PUSH_MACROS

Only files that actually use min/max are required to do this dance.

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

[libcxx][modularisation] moves <utility> content out of <type_traits>

Moves:

* `std::move`, `std::forward`, `std::declval`, and `std::swap` into
`__utility/${FUNCTION_NAME}`.
* `std::swap_ranges`

[libcxx][modularisation] moves <utility> content out of <type_traits>

Moves:

* `std::move`, `std::forward`, `std::declval`, and `std::swap` into
`__utility/${FUNCTION_NAME}`.
* `std::swap_ranges` and `std::iter_swap` into
`__algorithm/${FUNCTION_NAME}`

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

show more ...

[libcxx] Move all algorithms into their own headers

This is a fairly mechanical change, it just moves each algorithm into
its own header. This is intended to be a NFC.

This commit re-applies 7ed7d4

[libcxx] Move all algorithms into their own headers

This is a fairly mechanical change, it just moves each algorithm into
its own header. This is intended to be a NFC.

This commit re-applies 7ed7d4ccb899, which was reverted in 692d7166f771
because the Modules build got broken. The modules build has now been
fixed, so we're re-committing this.

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

Attribution note
----------------
I'm only committing this. This commit is a mix of D103583, D103330 and
D104171 authored by:

Co-authored-by: Christopher Di Bella <[email protected]>
Co-authored-by: zoecarver <[email protected]>

show more ...

[libcxx][gardening] Move all algorithms into their own headers.

This is a fairly mechanical change, it just moves each algorithm into its own header. This is a NFC.

Note: during this change, I burn

[libcxx][gardening] Move all algorithms into their own headers.

This is a fairly mechanical change, it just moves each algorithm into its own header. This is a NFC.

Note: during this change, I burned down all the includes, so this follows "include only and exactly what you use."

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

show more ...