[libc++] Alphabetize header inclusions. NFCI

[• Quuxplusone]

Summary

This should be a trivial NFC.
It's worth remarking that historically libc++ includes <__config> before all other headers (in case some header depends on <__config> macros). However, if all our headers include <__config>, then it doesn't really matter — maybe we include <__bit> first, but then <__bit> includes <__config>, so it all works out.

I'm not sure what's going on with the errors in https://buildkite.com/llvm-project/libcxx-ci/builds/3355 (on the Apple builds only).

[• Quuxplusone]

Roll in "alphabetize all headers." Poke buildkite.

[• Quuxplusone]

Merge the __wrap_iter part; keep this open for the alphabetize-headers part.

[ldionne]

LGTM but let's fix the Apple issue before committing this.

[zoecarver]

Not exactly sure why the tests are failing... I couldn't reproduce locally :(

Anyway, this lgtm as well, assuming you fix the tests.

[• Quuxplusone]

Move <__config> to the top of every file again (although I still don't see a physical reason that should matter). FWIW, I can't reproduce the Apple failures locally on my Macbook.
Poke buildbot.

[• Quuxplusone]

git checkout main -- all of the headers involved in the Apple modules failure, https://buildkite.com/llvm-project/libcxx-ci/builds/3355
This presumably leaves some kind of trap for the next refactorer, but at least maybe it'll narrow down where the trap is.

[• Quuxplusone]

Add __threading_support to the modulemap. I think this is going to work!

[teemperor]

I wonder if the stds_include.sh.cpp should also use the -fmodules-local-submodule-visibility flag. The default -fmodules can't really handle top modules that include textual headers. We're using the same flag in LLVM to build since D74892 (see also rG82b47b2978405f802a33b00d046e6f18ef6a47be for why)

[• Quuxplusone]

libcxx/include/module.modulemap

548 ↗

(On Diff #348645)

@teemperor wrote:

I wonder if the stds_include.sh.cpp should also use the -fmodules-local-submodule-visibility flag. The default -fmodules can't really handle top modules that include textual headers. We're using the same flag in LLVM to build since D74892 (see also rG82b47b2978405f802a33b00d046e6f18ef6a47be for why)

I don't know enough modules to say whether that flag would help. However, I don't think the problem here is related to textual headers at all (I mean, it's not because of headers like <cassert>). The problem here seems to be that e.g. <mutex> and <thread> both #include <__threading_support>; and so the contents of header "__threading_support" were winding up duplicated in both module std.mutex and module std.thread. (We see random heisenbuggy duplication issues with other headers too, e.g. the partial specializations in "__iterator/iterator_traits.h" end up duplicated and thus ambiguous.)

What we really need is a way to "share" the common helper header __threading_support between mutex and thread (and so on). My impression is that the only(?) tool we have right now for doing that is to make __threading_support a whole module in its own right.

Personally I would be quite happy to replace all of module.modulemap with a single umbrella module std that simply includes everything; and then worry about "modularizing the STL" sometime down the road. This year in particular we seem to be having our hands full merely "headerizing" it! :)

[teemperor]

libcxx/include/module.modulemap

548 ↗

(On Diff #348645)

Sorry, I think I should have made clear that I meant 'headers that are not in a module' when I said 'textual' (as those headers behave similar to the actual textual headers declared in a modulemap).

And yes, having all the headers (even helpers) in their own submodule would probably help a lot with the bugs caused by the duplication. I'm not familiar enough with libc++ to say how much work that would be. Just commenting as I pushed for that specific test and I don't just want to leave it to others to keep it green :)

libcxx/include/__iterator/iterator_traits.h

 // -*- C++ -*-
 //===----------------------------------------------------------------------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef _LIBCPP___ITERATOR_ITERATOR_TRAITS_H
 #define _LIBCPP___ITERATOR_ITERATOR_TRAITS_H
 
 #include <__config>
-#include <concepts>
 #include <__iterator/incrementable_traits.h>
 #include <__iterator/readable_traits.h>
+#include <concepts>
 #include <type_traits>
 
 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
 #pragma GCC system_header
 #endif
 
 _LIBCPP_PUSH_MACROS
 #include <__undef_macros>
struct _LIBCPP_TEMPLATE_VIS iterator_traits<_Tp*>
     typedef random_access_iterator_tag iterator_category;
 #if _LIBCPP_STD_VER > 17
     typedef contiguous_iterator_tag    iterator_concept;
 #endif
 };
 
 template <class _Tp, class _Up, bool = __has_iterator_category<iterator_traits<_Tp> >::value>
 struct __has_iterator_category_convertible_to
-    : _BoolConstant<is_convertible<typename iterator_traits<_Tp>::iterator_category, _Up>::value>
+    : is_convertible<typename iterator_traits<_Tp>::iterator_category, _Up>
 {};
 
 template <class _Tp, class _Up>
 struct __has_iterator_category_convertible_to<_Tp, _Up, false> : false_type {};
 
 template <class _Tp, class _Up, bool = __has_iterator_concept<_Tp>::value>
 struct __has_iterator_concept_convertible_to
-    : _BoolConstant<is_convertible<typename _Tp::iterator_concept, _Up>::value>
+    : is_convertible<typename _Tp::iterator_concept, _Up>
 {};
 
 template <class _Tp, class _Up>
 struct __has_iterator_concept_convertible_to<_Tp, _Up, false> : false_type {};
 
 template <class _Tp>
 struct __is_cpp17_input_iterator : public __has_iterator_category_convertible_to<_Tp, input_iterator_tag> {};
 
 template <class _Tp>
 struct __is_cpp17_forward_iterator : public __has_iterator_category_convertible_to<_Tp, forward_iterator_tag> {};
 
 template <class _Tp>
 struct __is_cpp17_bidirectional_iterator : public __has_iterator_category_convertible_to<_Tp, bidirectional_iterator_tag> {};
 
 template <class _Tp>
 struct __is_cpp17_random_access_iterator : public __has_iterator_category_convertible_to<_Tp, random_access_iterator_tag> {};
 
-// __is_cpp17_contiguous_iterator determines if an iterator is contiguous,
-// either because it advertises itself as such (in C++20) or because it
-// is a pointer type or a known trivial wrapper around a pointer type,
-// such as __wrap_iter<T*>.
+// __is_cpp17_contiguous_iterator determines if an iterator is known by
+// libc++ to be contiguous, either because it advertises itself as such
+// (in C++20) or because it is a pointer type or a known trivial wrapper
+// around a pointer type, such as __wrap_iter<T*>. Such iterators receive
+// special "contiguous" optimizations in std::copy and std::sort.
 //
 #if _LIBCPP_STD_VER > 17
 template <class _Tp>
 struct __is_cpp17_contiguous_iterator : _Or<
     __has_iterator_category_convertible_to<_Tp, contiguous_iterator_tag>,
     __has_iterator_concept_convertible_to<_Tp, contiguous_iterator_tag>
 > {};
 #else

libcxx/include/iterator

 public:
     typedef _Iter                                                      iterator_type;
     typedef typename iterator_traits<iterator_type>::value_type        value_type;
     typedef typename iterator_traits<iterator_type>::difference_type   difference_type;
     typedef typename iterator_traits<iterator_type>::pointer           pointer;
     typedef typename iterator_traits<iterator_type>::reference         reference;
     typedef typename iterator_traits<iterator_type>::iterator_category iterator_category;
 #if _LIBCPP_STD_VER > 17
-    typedef _If<__is_cpp17_contiguous_iterator<_Iter>::value,
-                contiguous_iterator_tag, iterator_category>            iterator_concept;
+    typedef contiguous_iterator_tag                                    iterator_concept;
 #endif
 
 private:
     iterator_type __i;
 public:
     _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_IF_NODEBUG __wrap_iter() _NOEXCEPT
 #if _LIBCPP_STD_VER > 11
                 : __i{}

     template <class _Iter1>
     _LIBCPP_CONSTEXPR_IF_NODEBUG friend
     __wrap_iter<_Iter1>
     operator+(typename __wrap_iter<_Iter1>::difference_type, __wrap_iter<_Iter1>) _NOEXCEPT;
 };
 
 #if _LIBCPP_STD_VER <= 17
 template <class _It>
-struct __is_cpp17_contiguous_iterator<__wrap_iter<_It> > : __is_cpp17_contiguous_iterator<_It> {};
+struct __is_cpp17_contiguous_iterator<__wrap_iter<_It> > : true_type {};
 #endif
 
 template <class _Iter>
 _LIBCPP_CONSTEXPR
-_EnableIf<__is_cpp17_contiguous_iterator<_Iter>::value, decltype(_VSTD::__to_address(declval<_Iter>()))>
+decltype(_VSTD::__to_address(declval<_Iter>()))
 __to_address(__wrap_iter<_Iter> __w) _NOEXCEPT {
     return _VSTD::__to_address(__w.base());
 }
 
 template <class _Iter1, class _Iter2>
 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_IF_NODEBUG
 bool
 operator==(const __wrap_iter<_Iter1>& __x, const __wrap_iter<_Iter2>& __y) _NOEXCEPT

libcxx/test/libcxx/iterators/contiguous_iterators.pass.cpp

public:
     friend bool operator!=(const Self&, const Self&);
     friend bool operator<(const Self&, const Self&);
     friend bool operator>(const Self&, const Self&);
     friend bool operator<=(const Self&, const Self&);
     friend bool operator>=(const Self&, const Self&);
 };
 #endif
 
+struct fake_deque_iterator : std::deque<int>::iterator {
+    using element_type = int;
+};
+static_assert(std::__is_cpp17_random_access_iterator<fake_deque_iterator>::value, "");
+static_assert(!std::__is_cpp17_contiguous_iterator<fake_deque_iterator>::value, "");
+
+#if TEST_STD_VER >= 20
+struct fake2_deque_iterator : std::deque<int>::iterator {
+    using iterator_concept = std::contiguous_iterator_tag;
+    using element_type = int;
+};
+static_assert(std::__is_cpp17_random_access_iterator<fake2_deque_iterator>::value, "");
+static_assert(std::__is_cpp17_contiguous_iterator<fake2_deque_iterator>::value, "");
+#endif
+
 int main(int, char**)
 {
 //  basic tests
     static_assert(( std::__is_cpp17_contiguous_iterator<char *>::value), "");
     static_assert(( std::__is_cpp17_contiguous_iterator<const char *>::value), "");
     static_assert(( std::__is_cpp17_contiguous_iterator<int *>::value), "");
     static_assert(( std::__is_cpp17_contiguous_iterator<int **>::value), "");
     static_assert(( std::__is_cpp17_contiguous_iterator<T *>::value), "");

 #endif
 
     static_assert(( std::__is_cpp17_contiguous_iterator<std::__wrap_iter<char *> >::value), "");
     static_assert(( std::__is_cpp17_contiguous_iterator<std::__wrap_iter<const char *> >::value), "");
     static_assert(( std::__is_cpp17_contiguous_iterator<std::__wrap_iter<int *> >::value), "");
 
     static_assert(( std::__is_cpp17_contiguous_iterator<std::__wrap_iter<T *> >::value), "");
     static_assert(( std::__is_cpp17_contiguous_iterator<std::__wrap_iter<std::__wrap_iter<T *> > >::value), "");
-    static_assert((!std::__is_cpp17_contiguous_iterator<std::__wrap_iter<std::reverse_iterator<T *> > >::value), "");
 
-    static_assert((!std::__is_cpp17_contiguous_iterator<std::__wrap_iter<my_random_access_iterator> >::value), "");
-    static_assert((!std::__is_cpp17_contiguous_iterator<std::__wrap_iter<std::__wrap_iter<my_random_access_iterator> > >::value), "");
-    static_assert((!std::__is_cpp17_contiguous_iterator<std::__wrap_iter<std::reverse_iterator<my_random_access_iterator> > >::value), "");
+    // Here my_random_access_iterator is standing in for some user's fancy pointer type, written pre-C++20.
+    static_assert(( std::__is_cpp17_contiguous_iterator<std::__wrap_iter<my_random_access_iterator> >::value), "");
+    static_assert(( std::__is_cpp17_contiguous_iterator<std::__wrap_iter<std::__wrap_iter<my_random_access_iterator> > >::value), "");
 
 #if TEST_STD_VER >= 20
     static_assert(( std::__is_cpp17_contiguous_iterator<std::__wrap_iter<my_contiguous_iterator> >::value), "");
     static_assert(( std::__is_cpp17_contiguous_iterator<std::__wrap_iter<std::__wrap_iter<my_contiguous_iterator> > >::value), "");
-    static_assert((!std::__is_cpp17_contiguous_iterator<std::__wrap_iter<std::reverse_iterator<my_contiguous_iterator> > >::value), "");
 #endif
 
 //  iterators in the libc++ test suite
     static_assert((!std::__is_cpp17_contiguous_iterator<output_iterator       <char *> >::value), "");
-    static_assert((!std::__is_cpp17_contiguous_iterator<cpp17_input_iterator        <char *> >::value), "");
+    static_assert((!std::__is_cpp17_contiguous_iterator<cpp17_input_iterator  <char *> >::value), "");
     static_assert((!std::__is_cpp17_contiguous_iterator<forward_iterator      <char *> >::value), "");
     static_assert((!std::__is_cpp17_contiguous_iterator<bidirectional_iterator<char *> >::value), "");
     static_assert((!std::__is_cpp17_contiguous_iterator<random_access_iterator<char *> >::value), "");
 #if TEST_STD_VER >= 20
     static_assert(( std::__is_cpp17_contiguous_iterator<contiguous_iterator   <char *> >::value), "");
 #endif
     static_assert((!std::__is_cpp17_contiguous_iterator<ThrowingIterator      <char *> >::value), "");
     static_assert((!std::__is_cpp17_contiguous_iterator<NonThrowingIterator   <char *> >::value), "");
//  string
     static_assert((!std::__is_cpp17_contiguous_iterator<std::wstring::reverse_iterator>      ::value), "");
     static_assert((!std::__is_cpp17_contiguous_iterator<std::wstring::const_reverse_iterator>::value), "");
 
 //  deque is random-access but not contiguous
     static_assert((!std::__is_cpp17_contiguous_iterator<std::deque<int>::iterator>                   ::value), "");
     static_assert((!std::__is_cpp17_contiguous_iterator<std::deque<int>::const_iterator>             ::value), "");
     static_assert((!std::__is_cpp17_contiguous_iterator<std::deque<int>::reverse_iterator>           ::value), "");
     static_assert((!std::__is_cpp17_contiguous_iterator<std::deque<int>::const_reverse_iterator>     ::value), "");
-    static_assert((!std::__is_cpp17_contiguous_iterator<std::__wrap_iter<std::deque<int>::iterator> >::value), "");
 
 //  vector<bool> is random-access but not contiguous
     static_assert((!std::__is_cpp17_contiguous_iterator<std::vector<bool>::iterator>                   ::value), "");
     static_assert((!std::__is_cpp17_contiguous_iterator<std::vector<bool>::const_iterator>             ::value), "");
     static_assert((!std::__is_cpp17_contiguous_iterator<std::vector<bool>::reverse_iterator>           ::value), "");
     static_assert((!std::__is_cpp17_contiguous_iterator<std::vector<bool>::const_reverse_iterator>     ::value), "");
-    static_assert((!std::__is_cpp17_contiguous_iterator<std::__wrap_iter<std::vector<bool>::iterator> >::value), "");
 
 #if TEST_STD_VER >= 11
     static_assert(( std::__is_cpp17_contiguous_iterator<std::initializer_list<int>::iterator>      ::value), "");
     static_assert(( std::__is_cpp17_contiguous_iterator<std::initializer_list<int>::const_iterator>::value), "");
 #endif
 
 #if TEST_STD_VER >= 17
     static_assert(( std::__is_cpp17_contiguous_iterator<std::string_view::iterator>      ::value), "");