[libc++] Make std::stable_sort constexpr friendly (#110320)

Implementing `constexpr std::stable_sort`. This is part of P2562R1,
tracked via issue #105360.

Closes #119394

Co-authored-by: A. Ji

[libc++] Make std::stable_sort constexpr friendly (#110320)

Implementing `constexpr std::stable_sort`. This is part of P2562R1,
tracked via issue #105360.

Closes #119394

Co-authored-by: A. Jiang <de34@live.cn>
Co-authored-by: Louis Dionne <ldionne.2@gmail.com>

show more ...

[libc++] Put _LIBCPP_NODEBUG on all internal aliases (#118710)

This significantly reduces the amount of debug information generated
for codebases using libc++, without hurting the debugging experie

[libc++] Put _LIBCPP_NODEBUG on all internal aliases (#118710)

This significantly reduces the amount of debug information generated
for codebases using libc++, without hurting the debugging experience.

show more ...

[libc++] Refactor the configuration macros to being always defined (#112094)

This is a follow-up to #89178. This updates the `<__config_site>`
macros.

Reapply "[libc++] Simplify the implementation of std::sort a bit (#104902)" (#114023)

This reverts commit ef44e4659878f2. The patch was originally reverted
because it was
deemed to introduce a perfo

Reapply "[libc++] Simplify the implementation of std::sort a bit (#104902)" (#114023)

This reverts commit ef44e4659878f2. The patch was originally reverted
because it was
deemed to introduce a performance regression for small inputs, however
it also fixed
a previous performance regression for larger inputs. So overall, this
patch is desirable.

show more ...

Revert "[libc++] Simplify the implementation of std::sort a bit (#104902)"

This reverts commit d4ffccfce103b01401b8a9222e373f2d404f8439, which
caused a performance regression that needs to be invest

Revert "[libc++] Simplify the implementation of std::sort a bit (#104902)"

This reverts commit d4ffccfce103b01401b8a9222e373f2d404f8439, which
caused a performance regression that needs to be investigated further.

show more ...

[libc++][modules] Fix missing and incorrect includes (#108850)

This patch adds a large number of missing includes in the libc++ headers
and the test suite. Those were found as part of the effort to

[libc++][modules] Fix missing and incorrect includes (#108850)

This patch adds a large number of missing includes in the libc++ headers
and the test suite. Those were found as part of the effort to move
towards a mostly monolithic top-level std module.

show more ...

[libc++] Simplify the implementation of std::sort a bit (#104902)

This does a few things to canonicalize the library a bit. Specifically
- use `__desugars_to_v` instead of the custom `__is_simple_c

[libc++] Simplify the implementation of std::sort a bit (#104902)

This does a few things to canonicalize the library a bit. Specifically
- use `__desugars_to_v` instead of the custom `__is_simple_comparator`
- make `__use_branchless_sort` an inline variable
- remove the `_maybe_branchless` versions of the `__sortN` functions and
overload based on whether we can do branchless sorting instead.

show more ...

[libc++] Marks a variable const. (#88562)

This removes a TODO from the code base.

[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++][hardening] Categorize more assertions. (#75918)

Also introduce `_LIBCPP_ASSERT_PEDANTIC` for assertions violating which
results in a no-op or other benign behavior, but which may neverthel

[libc++][hardening] Categorize more assertions. (#75918)

Also introduce `_LIBCPP_ASSERT_PEDANTIC` for assertions violating which
results in a no-op or other benign behavior, but which may nevertheless
indicate a bug in the invoking code.

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++][NFC] Refactor __enable_if return types to defaulted template parameters

This brings most of the enable_ifs in libc++ to the same style. It also has the nice side-effect of reducing the size

[libc++][NFC] Refactor __enable_if return types to defaulted template parameters

This brings most of the enable_ifs in libc++ to the same style. It also has the nice side-effect of reducing the size of names of these symbols, since the depedent return type is shorter.

Reviewed By: #libc, ldionne

Spies: ldionne, libcxx-commits

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

show more ...

[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++][hardening][NFC] Introduce `_LIBCPP_ASSERT_UNCATEGORIZED`.

Replace most uses of `_LIBCPP_ASSERT` with
`_LIBCPP_ASSERT_UNCATEGORIZED`.

This is done as a prerequisite to introducing hardened

[libc++][hardening][NFC] Introduce `_LIBCPP_ASSERT_UNCATEGORIZED`.

Replace most uses of `_LIBCPP_ASSERT` with
`_LIBCPP_ASSERT_UNCATEGORIZED`.

This is done as a prerequisite to introducing hardened mode to libc++.
The idea is to make enabling assertions an opt-in with (somewhat)
fine-grained controls over which categories of assertions are enabled.
The vast majority of assertions are currently uncategorized; the new
macro will allow turning on `_LIBCPP_ASSERT` (the underlying mechanism
for all kinds of assertions) without enabling all the uncategorized
assertions (in the future; this patch preserves the current behavior).

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

show more ...

[libc++] Merge _LIBCPP_FUNC_VIS, _LIBCPP_TYPE_VIS and _LIBCPP_EXCEPTION_ABI into _LIBCPP_EXPORTED_FROM_ABI

These macros are always defined identically, so we can simplify the code a bit by merging t

[libc++] Merge _LIBCPP_FUNC_VIS, _LIBCPP_TYPE_VIS and _LIBCPP_EXCEPTION_ABI into _LIBCPP_EXPORTED_FROM_ABI

These macros are always defined identically, so we can simplify the code a bit by merging them.

Reviewed By: ldionne, #libc

Spies: libcxx-commits, krytarowski, smeenai

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

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

[libcxx] Add strict weak ordering checks to sorting algorithms

This is the implementation of the first proposal of strict weak ordering checks described in https://discourse.llvm.org/t/rfc-strict-we

[libcxx] Add strict weak ordering checks to sorting algorithms

This is the implementation of the first proposal of strict weak ordering checks described in https://discourse.llvm.org/t/rfc-strict-weak-ordering-checks-in-the-debug-libc/70217

This targets the most vulnerable algorithms like std::sort

Reviewed By: philnik, #libc

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

show more ...

[libc++][NFC] Rename iterator category checks to make it obvious that they check //only// the iterator category

We plan to add concepts for checking that iterators actually provide what they claim t

[libc++][NFC] Rename iterator category checks to make it obvious that they check //only// the iterator category

We plan to add concepts for checking that iterators actually provide what they claim to. This is to avoid people thinking that these type traits actually check the iterator requirements in more detail.

Reviewed By: ldionne, #libc

Spies: Mordante, libcxx-commits, wenlei

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

show more ...

[libc++] Avoid dereferencing a const iterator in std::sort

This is a workaround to provide a grace period for folks that were
broken by D147089. As a fly-by, also apply comments by Mark I had
someho

[libc++] Avoid dereferencing a const iterator in std::sort

This is a workaround to provide a grace period for folks that were
broken by D147089. As a fly-by, also apply comments by Mark I had
somehow missed in the review.

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

show more ...

[libc++] Add assertions for potential OOB reads in std::sort

We introduced an optimization to std::sort in 4eddbf9f10a6. However,
that optimization led to issues where users that were passing invali

[libc++] Add assertions for potential OOB reads in std::sort

We introduced an optimization to std::sort in 4eddbf9f10a6. However,
that optimization led to issues where users that were passing invalid
comparators to std::sort could start seeing OOB reads. This led to
the revert of the std::sort optimization from the LLVM 16 release
(see https://llvm.org/D146421).

This patch introduces _LIBCPP_ASSERTs to the places in the algorithm
where we make an assumption that the comparator will be consistent and
hence avoid a bounds check based on that. If the comparator happens not
to be consistent with itself, these are the places where we would
incorrectly go out of bounds. This allows users that enable libc++
assertions to catch such misuse at the cost of basically a bounds
check. For users that do not enable libc++ assertions (which is 99.9%
of users since assertions are off by default), this is basically a
no-op, and in fact the assertion will turn into a __builtin_assume,
making it explicit to the compiler that it can rely on the fact that
we're not going out of bounds.

I think this patch strikes the right balance. Folks that want absolute
performance will get what they want, since it is a precondition for the
comparator to be consistent, so the bounds checks are technically not
mandatory. Folks who want more safety *already* need to be enabling
libc++ assertions to catch other types of bugs (like operator[] OOB),
so this solution should also work for them.

I do think we have a lot of work towards popularizing the use of libc++
assertions and integrating it better so that users don't have to know
about the obscure _LIBCPP_ENABLE_ASSERTIONS macro to enable them, but
that's a separate concern.

rdar://106897934

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

show more ...

[libc++][NFC] Move __insertion_sort_move to partial_sort.h

The __insertion_sort_move helper function is only used in partial_sort.h,
so it makes sense to define it there.

Differential Revision: htt

[libc++][NFC] Move __insertion_sort_move to partial_sort.h

The __insertion_sort_move helper function is only used in partial_sort.h,
so it makes sense to define it there.

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

show more ...

[libc++][NFC] Fix typo in comment

[libc++][NFC] Simplify __sort{4,5}

Don't return the number of swaps; it's not used anywhere.

Reviewed By: Mordante, #libc, avogelsgesang

Spies: libcxx-commits

Differential Revision: https://revie

[libc++][NFC] Simplify __sort{4,5}

Don't return the number of swaps; it's not used anywhere.

Reviewed By: Mordante, #libc, avogelsgesang

Spies: libcxx-commits

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

show more ...

[libc++][NFC] Replace _LIBCPP_STD_VER > x with _LIBCPP_STD_VER >= x

This change is almost fully mechanical. The only interesting change is in `generate_feature_test_macro_components.py` to generate

[libc++][NFC] Replace _LIBCPP_STD_VER > x with _LIBCPP_STD_VER >= x

This change is almost fully mechanical. The only interesting change is in `generate_feature_test_macro_components.py` to generate `_LIBCPP_STD_VER >=` instead. To avoid churn in the git-blame this commit should be added to the `.git-blame-ignore-revs` once committed.

Reviewed By: ldionne, var-const, #libc

Spies: jloser, libcxx-commits, arichardson, arphaman, wenlei

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

show more ...