Revert "[libc++][ranges]Refactor `copy{,_backward}` and `move{,_backward}`"

Breaks msan, asan

https://lab.llvm.org/buildbot/#/builders/5/builds/27904

This reverts commit 005916de58f73aa5c4264c084b

Revert "[libc++][ranges]Refactor `copy{,_backward}` and `move{,_backward}`"

Breaks msan, asan

https://lab.llvm.org/buildbot/#/builders/5/builds/27904

This reverts commit 005916de58f73aa5c4264c084ba7b0e21040d88f.

show more ...

[libc++][ranges]Refactor `copy{,_backward}` and `move{,_backward}`

Instead of using `reverse_iterator`, share the optimization between the 4 algorithms. The key observation here that `memmove` appli

[libc++][ranges]Refactor `copy{,_backward}` and `move{,_backward}`

Instead of using `reverse_iterator`, share the optimization between the 4 algorithms. The key observation here that `memmove` applies to both `copy` and `move` identically, and to their `_backward` versions very similarly. All algorithms now follow the same pattern along the lines of:
```
if constexpr (can_memmove<InIter, OutIter>) {
memmove(first, last, out);
} else {
naive_implementation(first, last, out);
}
```
A follow-up will delete `unconstrained_reverse_iterator`.

This patch removes duplication and divergence between `std::copy`, `std::move` and `std::move_backward`. It also improves testing:
- the test for whether the optimization is used only applied to `std::copy` and, more importantly, was essentially a no-op because it would still pass if the optimization was not used;
- there were no tests to make sure the optimization is not used when the effect would be visible.

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

show more ...

[libc++][NFC] Fix some standard-mandated includes comments

Reviewed By: ldionne, #libc

Spies: libcxx-commits

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

[libc++] Rewrites graph_header_deps.py.

The new version is a lot simpler and has less option which were not
used. This uses the CSV files as generated by D133127 as input data.

The current Python s

[libc++] Rewrites graph_header_deps.py.

The new version is a lot simpler and has less option which were not
used. This uses the CSV files as generated by D133127 as input data.

The current Python script has more features but uses a simple "grep"
making the output less accurate:
- Conditionally included header are always included. This is an issue
since part of our includes are unneeded transitive includes. Based on
the language version they may be omitted. The script however always
includes them.
- Includes in comments are processed as-if they are includes. This is an
issue when comments explain how certain data is generated; of course
there are digraphs which the script omits.

This implementation uses Clang's --trace-includes to generate the includes
per header. This means the input of the generation script always has the
real list of includes.

Libc++ is moving from large monolithic Standard headers to more fine
grained headers. For example, algorithm includes every header in
`__algorithm`. Adding all these detail headers in the graph makes the
output unusable. Instead it only shows the Standard headers. The
transitive includes of the detail headers are parsed and "attributed" to
the Standard header including them. This gives an accurate include graph
without the unneeded clutter. Note that this graph is still big.

This changes fixes the cyclic dependency issue with the previous version
of the tool so the markers and its documentation is removed.

Since the input has no cycles the CI test is removed.

Reviewed By: #libc, ldionne

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

show more ...

[libc++] Granularize the rest of memory

Reviewed By: ldionne, #libc

Spies: vitalybuka, paulkirth, libcxx-commits, mgorny

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

[NFC][libc++] Moves transitive includes location.

As discussed in D132284 they will be moved to the end.

Reviewed By: #libc, Mordante

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

Revert "[libc++] Granularize the rest of memory"

Breaks buildbots.

This reverts commit 30adaa730c4768b5eb06719c808b2884fcf53cf3.

[libc++] Granularize the rest of memory

Reviewed By: ldionne, #libc

Spies: libcxx-commits, mgorny

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

[libc++] Reduces the number of transitive includes.

This defines a new policy for removal of transitive includes.
The goal of the policy it to make it relatively easy to remove
headers when needed,

[libc++] Reduces the number of transitive includes.

This defines a new policy for removal of transitive includes.
The goal of the policy it to make it relatively easy to remove
headers when needed, but avoid breaking developers using and
vendors shipping libc++.

The method used is to guard transitive includes based on the
C++ language version. For the upcoming C++23 we can remove
headers when we want, but for other language versions we try
to keep it to a minimum.

In this code the transitive include of `<chrono>` is removed
since D128577 introduces a header cycle between `<format>`
and `<chrono>`. This cycle is indirectly required by the
Standard. Our cycle dependency tool basically is a grep based
tool, so it needs some hints to ignore cycles. With the input
of our transitive include tests we can create a better tool.
However that's out of the scope of this patch.

Note the flag `_LIBCPP_REMOVE_TRANSITIVE_INCLUDES` remains
unchanged. So users can still opt-out of transitives includes
entirely.

Reviewed By: #libc, ldionne, philnik

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

show more ...

[libc++][ranges] Implement `ranges::is_permutation`

Co-authored-by: Konstantin Varlamov <varconst@apple.com>

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

[libc++][NFC] Remove rebase artifact

I found it in this commit: https://github.com/llvm/llvm-project/commit/a203acb9dd7227323d6161431225189d49917744

Reviewed By: Mordante

Differential Revision: ht

[libc++][NFC] Remove rebase artifact

I found it in this commit: https://github.com/llvm/llvm-project/commit/a203acb9dd7227323d6161431225189d49917744

Reviewed By: Mordante

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

show more ...

[libc++][ranges] Implement `ranges::clamp`

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

[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::{prev, next}_permutation`.

Co-authored-by: Konstantin Varlamov <varconst@apple.com>

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

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

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

[libc++][ranges] Implement `ranges::replace_copy{,_if}`.

Co-authored-by: Konstantin Varlamov <varconst@apple.com>

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

[libc++][ranges] Implement `ranges::remove_copy{, _if}`.

Co-authored-by: Hui Xie <hui.xie1990@gmail.com>

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

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

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

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

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

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

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

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

[libc++][ranges] Implement `ranges::is_heap{,_until}`.

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

[libc++][ranges] Implement `ranges::generate{,_n}`.

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

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

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

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

implement `std::ranges::includes` and delegate to `std::includes`

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

[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