[libc++] ADL-proof <algorithm> by adding _VSTD:: qualification on calls.

[Quuxplusone]

Summary

[libc++] Add _VSTD:: qualifications to ADL-proof <algorithm>.

Relevant blog post: https://quuxplusone.github.io/blog/2019/09/26/uglification-doesnt-stop-adl/

@ldionne: In the <algorithm> commit, I noticed that there are several places where otherwise-well-formed code has been commented out; e.g. look at the codepath in __nth_element following not_sorted:. The commented-out stuff dates back to @howard.hinnant's initial commit. Can I just remove the commented-out stuff, in a separate "NFC" commit?

[ldionne]

@ldionne: In the <algorithm> commit, I noticed that there are several places where otherwise-well-formed code has been commented out; e.g. look at the codepath in __nth_element following not_sorted:. The commented-out stuff dates back to @howard.hinnant's initial commit. Can I just remove the commented-out stuff, in a separate "NFC" commit?

Can you please open up a Phab review for that, just so we can take a look and confirm that we're indeed removing stuff that should be commented out, and that has no purpose anymore?

[Quuxplusone]

[libc++] Include <cstring> and <cwchar> in <__string>.

We seem to be getting lucky that <memory> includes <iterator>
includes <iosfwd> includes <wchar.h>. This gives us the global-namespace
`wmemmove`, but not `_VSTD::wmemmove`.

[libc++] Include C++ headers, not C headers, in <charconv>.

This matches how libc++ does it in all the other headers.
The only header that includes <string.h> is <cstring>.
We need to include <cstring> if we want to use `_VSTD::memmove`
instead of ADL or global-namespace `memmove`.

[Quuxplusone]

Roll this back to just the main <algorithm> commit. The qualification of memmove etc. turned out to be a bit deeper of a rabbit-hole than I initially expected; I'll open a separate Phab review for that one. Meanwhile, on D92776, I plan to wait for CI to be green and then land what-remains-here as one commit.

[Quuxplusone]

This time for sure!

ADL-proof __libcpp_is_nothrow_constructible. The GCC C++20 buildbot hit this ADL call; Clang doesn't, presumably because it uses a compiler builtin instead of this codepath in <type_traits>.
https://buildkite.com/llvm-project/libcxx-ci/builds/674

[rnk]

libcxx/include/algorithm

1739

This broke Chrome, apparently we were using this ADL extension point to enable memmove optimization for some fancy iterators:
https://source.chromium.org/chromium/chromium/src/+/master:base/containers/checked_iterators.h;l=88?q=__unwrap_iter&ss=chromium

This std::copy optimization was added in April, maybe it's not that important:
https://chromium-review.googlesource.com/c/chromium/src/+/1875734

Can you suggest an alternative solution to make std::copy use memmove for some custom iterator?

[Quuxplusone]

libcxx/include/algorithm

1739

Oh, yuck. @ldionne @EricWF might want to take a look.
As the discussion on that pull request indicated, C++20 provides a standard way to make a contiguous iterator that the library will recognize; however, there are two problems with that approach right now. (1) it's not implemented, and (2) it's not the best-designed, for example it requires you to overload std::to_address(CCI) (not as an ADL customization point; actually in std!).
I think it would be useful to users if libc++ provided a simple way to mark an iterator as contiguous, even in C++11/14/17. I suggest:

• libc++ should define the tag type std::contiguous_iterator_tag in all language modes, as an extension.
• libc++ should treat as contiguous, any iterator for which std::is_base_of_v<std::contiguous_iterator_tag, std::iterator_traits<It>::iterator_category>.
• To convert a contiguous iterator it to a pointer, libc++ should call std::to_address(it) just the way it would in C++20(??).

I've opened https://stackoverflow.com/questions/65712091/in-c20-how-do-i-write-a-contiguous-iterator to find out more about how users such as Chromium are supposed to do this kind of stuff.

[ldionne]

libcxx/include/algorithm

1739

I know @EricWF had done a lot of work towards enabling this use-case, and I think he had a consistent design in mind. I'd like him to chime in on this issue.

What Arthur says makes sense to me and I'd be in favour of following that path, however like I said I absolutely want to have Eric's thoughts first because he had worked on the chromium optimization in the first place.

[EricWF]

We definitely want to unqualify __unwrap_iter to unbreak chromium. That's somewhat intended to be a customization point (until the proper contiguous iterator stuff lands).