[libc++] Fix missing and incorrect push/pop macros (#79204)

We recently noticed that the unwrap_iter.h file was pushing macros, but
it was pushing them again instead of popping them at the end of t

[libc++] Fix missing and incorrect push/pop macros (#79204)

We recently noticed that the unwrap_iter.h file was pushing macros, but
it was pushing them again instead of popping them at the end of the
file. This led to libc++ basically swallowing any custom definition of
these macros in user code:

#define min HELLO
#include <algorithm>
// min is not HELLO anymore, it's not defined

While investigating this issue, I noticed that our push/pop pragmas were
actually entirely wrong too. Indeed, instead of pushing macros like
`move`, we'd push `move(int, int)` in the pragma, which is not a valid
macro name. As a result, we would not actually push macros like `move`
-- instead we'd simply undefine them. This led to the following code not
working:

#define move HELLO
#include <algorithm>
// move is not HELLO anymore

Fixing the pragma push/pop incantations led to a cascade of issues
because we use identifiers like `move` in a large number of places, and
all of these headers would now need to do the push/pop dance.

This patch fixes all these issues. First, it adds a check that we don't
swallow important names like min, max, move or refresh as explained
above. This is done by augmenting the existing
system_reserved_names.gen.py test to also check that the macros are what
we expect after including each header.

Second, it fixes the push/pop pragmas to work properly and adds missing
pragmas to all the files I could detect a failure in via the newly added
test.

rdar://121365472

show more ...

[libc++][hardening] Categorize assertions related to strict weak ordering (#77405)

If a user passes a comparator that doesn't satisfy strict weak ordering
(see https://eel.is/c++draft/algorithms#al

[libc++][hardening] Categorize assertions related to strict weak ordering (#77405)

If a user passes a comparator that doesn't satisfy strict weak ordering
(see https://eel.is/c++draft/algorithms#alg.sorting.general) to
a sorting algorithm, the algorithm can produce an incorrect result or
even lead
to an out-of-bounds access. Unfortunately, comprehensively validating
that a given comparator indeed satisfies the strict weak ordering
requirement is prohibitively expensive (see [the related
RFC](https://discourse.llvm.org/t/rfc-strict-weak-ordering-checks-in-the-debug-libc/70217)).
As a result, we have three independent sets of checks:

- assertions that catch out-of-bounds accesses within the algorithms'
implementation. These are relatively cheap; however, they cannot catch
the underlying cause and cannot prevent the case where an invalid
comparator would result in an incorrectly-sorted sequence without
actually triggering an OOB access;

- debug comparators that wrap a given comparator and on each comparison
check that if `(a < b)`, then `!(b < a)`, where `<` stands for the
user-provided comparator. This performs up to 2x number of comparisons
but doesn't affect the algorithmic complexity. While this approach can
find more issues, it is still a heuristic;

- a comprehensive check of the comparator that validates up to 100
elements in the resulting sorted sequence (see the RFC above for
details). The check is expensive but the 100 element limit can somewhat
compensate for that, especially for large values of `N`.

The first set of checks is enabled in the fast hardening mode while the
other two are only enabled in the debug mode.

This patch also removes the
`_LIBCPP_DEBUG_STRICT_WEAK_ORDERING_CHECK` macro that
previously was used to selectively enable the 100-element check.
Now this check is enabled unconditionally in the debug mode.

Also, introduce a new category
`_LIBCPP_ASSERT_SEMANTIC_REQUIREMENT`. This category is
intended for checking the semantic requirements from the Standard.
Typically, these are hard or impossible to completely validate, so
these checks are expected to be heuristic in nature and potentially
quite expensive.

See https://reviews.llvm.org/D150264 for additional background.
Fixes #71496

show more ...

[libc++] Format the code base (#74334)

This patch runs clang-format on all of libcxx/include and libcxx/src, in
accordance with the RFC discussed at [1]. Follow-up patches will format
the benchmar

[libc++] Format the code base (#74334)

This patch runs clang-format on all of libcxx/include and libcxx/src, in
accordance with the RFC discussed at [1]. Follow-up patches will format
the benchmarks, the test suite and remaining parts of the code. I'm
splitting this one into its own patch so the diff is a bit easier to
review.

This patch was generated with:

find libcxx/include libcxx/src -type f \
| grep -v 'module.modulemap.in' \
| grep -v 'CMakeLists.txt' \
| grep -v 'README.txt' \
| grep -v 'libcxx.imp' \
| grep -v '__config_site.in' \
| xargs clang-format -i

A Git merge driver is available in libcxx/utils/clang-format-merge-driver.sh
to help resolve merge and rebase issues across these formatting changes.

[1]: https://discourse.llvm.org/t/rfc-clang-formatting-all-of-libc-once-and-for-all

show more ...

[libc++] Replace uses of _VSTD:: by std:: (#74331)

As part of the upcoming clang-formatting of libc++, this patch performs
the long desired removal of the _VSTD macro.

See https://discourse.llvm

[libc++] Replace uses of _VSTD:: by std:: (#74331)

As part of the upcoming clang-formatting of libc++, this patch performs
the long desired removal of the _VSTD macro.

See https://discourse.llvm.org/t/rfc-clang-formatting-all-of-libc-once-and-for-all
for the clang-format proposal.

show more ...

[libc++] Add assertions for potential OOB reads in std::nth_element (#67023)

Same as https://reviews.llvm.org/D147089 but for std::nth_element

[libc++] Remove the legacy debug mode.

See https://discourse.llvm.org/t/rfc-removing-the-legacy-debug-mode-from-libc/71026

Reviewed By: #libc, Mordante, ldionne

Differential Revision: https://revi

[libc++] Remove the legacy debug mode.

See https://discourse.llvm.org/t/rfc-removing-the-legacy-debug-mode-from-libc/71026

Reviewed By: #libc, Mordante, ldionne

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

show more ...

[libc++] Refactor __less

This simplifies the usage of `__less` by making the class not depend on the types compared, but instead the `operator()`. We can't remove the template completely because we

[libc++] Refactor __less

This simplifies the usage of `__less` by making the class not depend on the types compared, but instead the `operator()`. We can't remove the template completely because we explicitly instantiate `std::__sort` with `__less<T>`.

Reviewed By: ldionne, #libc

Spies: arichardson, EricWF, libcxx-commits, mgrang

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

show more ...

[libc++][NFC] Prefer type aliases over structs

Reviewed By: ldionne, #libc

Spies: sstefan1, libcxx-commits, jeroen.dobbelaere

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

[libc++][NFC] Rename the constexpr macros

This was discussed on Discord with the consensus that we should rename the macros.

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

[libc++][NFC] Rename the constexpr macros

This was discussed on Discord with the consensus that we should rename the macros.

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

Spies: libcxx-commits

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

show more ...

[libc++] Add a bunch of missing _LIBCPP_HIDE_FROM_ABI

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

Spies: jloser, libcxx-commits, arichardson, miyuki

Differential Revision: https://r

[libc++] Add a bunch of missing _LIBCPP_HIDE_FROM_ABI

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

Spies: jloser, libcxx-commits, arichardson, miyuki

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

show more ...

[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++][ranges] Implement `ranges::nth_element`.

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

[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++] 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 <cjdb@google.com>
Co-authored-by: zoecarver <z.zoelec2@gmail.com>

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 ...