[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++] Forward more algorithms to the classic algorithms (#114674)

This partially addresses #105687.

[libc++] Speed up set_intersection() by fast-forwarding over ranges of non-matching elements with one-sided binary search. (#75230)

One-sided binary search, aka meta binary search, has been in the p

[libc++] Speed up set_intersection() by fast-forwarding over ranges of non-matching elements with one-sided binary search. (#75230)

One-sided binary search, aka meta binary search, has been in the public
domain for decades, and has the general advantage of being constant time
in the best case, with the downside of executing at most 2*log(N)
comparisons vs classic binary search's exact log(N). There are two
scenarios in which it really shines: the first one is when operating
over non-random-access iterators, because the classic algorithm requires
knowing the container's size upfront, which adds N iterator increments
to the complexity. The second one is when traversing the container in
order, trying to fast-forward to the next value: in that case the
classic algorithm requires at least O(N*log(N)) comparisons and, for
non-random-access iterators, O(N^2) iterator increments, whereas the
one-sided version will yield O(N) operations on both counts, with a
best-case of O(log(N)) comparisons which is very common in practice.

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

Fixing conflicting macro definitions between curses.h and the standard library.

POSIX allows certain macros to exist with generic names (i.e. refresh(), move(), and erase()) to exist in `curses.h` w

Fixing conflicting macro definitions between curses.h and the standard library.

POSIX allows certain macros to exist with generic names (i.e. refresh(), move(), and erase()) to exist in `curses.h` which conflict with functions found in std::filesystem, among others. This patch undefs the macros in question and adds them to LIBCPP_PUSH_MACROS and LIBCPP_POP_MACROS.

Reviewed By: #libc, philnik, ldionne

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

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

[libc++] Granularize <type_traits> includes in <compare>

Reviewed By: Mordante, #libc

Spies: libcxx-commits

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

[libc++] Avoid instantiating type_trait classes

Use `using` aliases to avoid instantiating lots of types

Reviewed By: ldionne, #libc

Spies: libcxx-commits, miyuki

Differential Revision: https://r

[libc++] Avoid instantiating type_trait classes

Use `using` aliases to avoid instantiating lots of types

Reviewed By: ldionne, #libc

Spies: libcxx-commits, miyuki

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

show more ...

[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++] Make <ranges> non-experimental

When we ship LLVM 16, <ranges> won't be considered experimental anymore.
We might as well do this sooner rather than later.

Differential Revision: https://re

[libc++] Make <ranges> non-experimental

When we ship LLVM 16, <ranges> won't be considered experimental anymore.
We might as well do this sooner rather than later.

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

show more ...

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

Also fix `ranges::stable_sort` and `ranges::inplace_merge` to support
proxy iterators now that their internal implementations can correctly
dispatch `rot

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

Also fix `ranges::stable_sort` and `ranges::inplace_merge` to support
proxy iterators now that their internal implementations can correctly
dispatch `rotate`.

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

show more ...

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

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

[libc++][ranges] implement `std::ranges::unique{_copy}`

implement `std::ranges::unique` and `std::ranges::unique_copy`

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

[libc++] Make `_IterOps::__iter_move` more similar to `std::ranges::iter_move`.

Avoid relying on `iterator_traits` and instead deduce the return type of
dereferencing the iterator. Additionally, add

[libc++] Make `_IterOps::__iter_move` more similar to `std::ranges::iter_move`.

Avoid relying on `iterator_traits` and instead deduce the return type of
dereferencing the iterator. Additionally, add a static check to reject
iterators with incorrect `iterator_traits` at compile time.

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

show more ...

[libc++][ranges] implement `std::ranges::equal_range`

implement `std::ranges::equal_range` which delegates to
`std::equal_range`

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

[libc++] Fix proxy iterator issues that trigger an assertion in Chromium.

Crash report:
https://bugs.chromium.org/p/chromium/issues/detail?id=1346012

The triggered assertion is related sorting with

[libc++] Fix proxy iterator issues that trigger an assertion in Chromium.

Crash report:
https://bugs.chromium.org/p/chromium/issues/detail?id=1346012

The triggered assertion is related sorting with `v8::internal::AtomicSlot`.
`AtomicSlot` is a proxy iterator with a proxy type `AtomicSlot::Reference`
(see https://chromium.googlesource.com/v8/v8/+/9bcb5eb590643db0c1f688fea316c7f1f4786a3c/src/objects/slots-atomic-inl.h).

https://reviews.llvm.org/D130197 correctly spotted the issue in
`__iter_move` but doesn't actually fix the issue. The reason is that
`AtomicSlot::operator*` returns a prvalue `Reference`. After the fix in
D130197, the return type of `__iter_move` is `Reference&&`. But the
rvalue reference is bound to the temporary value returned by
`operator*`, which will be dangling after `__iter_move` returns.

The idea of the fix in this change is borrowed from C++17's move_iterator
https://timsong-cpp.github.io/cppwp/n4659/move.iterators#move.iterator-1
When the underlying reference is a prvalue, we just return it by value.

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

show more ...

[libc++] Fix `_IterOps::__iter_move` to support proxy iterators.

The return type was specified incorrectly for proxy iterators that
define `reference` to be a class that implicitly converts to
`valu

[libc++] Fix `_IterOps::__iter_move` to support proxy iterators.

The return type was specified incorrectly for proxy iterators that
define `reference` to be a class that implicitly converts to
`value_type`. `__iter_move` would end up returning an object of type
`reference` which would then implicitly convert to `value_type`; thus,
the function will return a `value_type&&` rvalue reference to the local
temporary.

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

show more ...

[libc++][ranges] Implement `ranges::{,stable_}partition`.

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

[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++] Implement ranges::find_end, ranges::search{, _n}

Reviewed By: var-const, #libc, huixie90

Spies: thakis, h-vetinari, huixie90, libcxx-commits, mgorny

Differential Revision: https://reviews

[libc++] Implement ranges::find_end, ranges::search{, _n}

Reviewed By: var-const, #libc, huixie90

Spies: thakis, h-vetinari, huixie90, libcxx-commits, mgorny

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

show more ...

Revert "[libc++] Implement ranges::find_end, ranges::search{, _n}"

This reverts commit 76a76518507ccc59ccdad5b83f44dc8c3d9593c7.

[libc++] Implement ranges::find_end, ranges::search{, _n}

Reviewed By: var-const, #libc, huixie90

Spies: h-vetinari, huixie90, libcxx-commits, mgorny

Differential Revision: https://reviews.llvm.or

[libc++] Implement ranges::find_end, ranges::search{, _n}

Reviewed By: var-const, #libc, huixie90

Spies: h-vetinari, huixie90, libcxx-commits, mgorny

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

show more ...

[lib++][ranges][NFC] Refactor `iterator_operations.h` to use tags.

Change the mechanism in `iterator_operations.h` to pass around a generic
policy tag indicating whether an internal function is bein

[lib++][ranges][NFC] Refactor `iterator_operations.h` to use tags.

Change the mechanism in `iterator_operations.h` to pass around a generic
policy tag indicating whether an internal function is being invoked from
a "classic" STL algorithm or a ranges algorithm. `IterOps` is now
a template class specialized on the policy tag.

The advantage is that this mechanism is more generic and allows defining
arbitrary conditions in a clean manner.

Also add a few more iterator functions to `IterOps`.

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

show more ...

[libc++][ranges] implement `std::ranges::set_intersection`

implement `std::ranges::set_intersection` by reusing the classic `std::set_intersenction`
added unit tests

Differential Revision: https://

[libc++][ranges] implement `std::ranges::set_intersection`

implement `std::ranges::set_intersection` by reusing the classic `std::set_intersenction`
added unit tests

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

show more ...