[libc++] Granularize algorithm includes

[• Quuxplusone]

Seems fine to me if (1) CI is green and (2) we're all on board for breaking Hyrum's Law this month. I believe I've heard rumors to that effect — "it's very early in the 15.x release cycle, so let's remove all these redundant includes now and give people plenty of time to adjust and/or complain" — but I'll post in the Discord to get some nice explicit confirmation.

libcxx/test/std/containers/sequences/list/list.ops/sort.pass.cpp

47

Could drive-by fix this to std::distance while you're here, if you like...

[Mordante]

Thanks for doing this! (It removes an item of my todo list :-) )
Two requests

1. mention in the commit message that this removes several includes that people accidentally depend on. (in fact the addition in some headers show we already do this ourselves.) This isn't entirely obvious from the current message.
2. mention the changes in the release notes. @ldionne do you want one note or should we mention all includes we removed?

LGTM, I leave the final approval this first cleanup for @ldionne.

libcxx/test/std/containers/sequences/list/list.ops/sort.pass.cpp

47

Slight preference to do that in a separate commit, just in case this one needs to be reverted.

[ldionne]

I am fine with this direction, however I agree CI should be green, and also we need to release-note this. I think the release note can only say that we removed transitive includes of <algorithm>, so if users see issues related to that, they know what the cause is. I don't think it's really useful to list all the headers that we removed <algorithm> *from*.

Requesting changes until those issues are fixed. Also, pinging libc++ vendors just so they are aware of this.

[philnik]

• Address comments; Fix CI

[ldionne]

LGTM with fixed release note and green CI.

libcxx/docs/ReleaseNotes.rst

53 ↗

(On Diff #408502)

[philnik]

• Rebased
• Fix modules build
• Address comment

[philnik]

The libcxxabi/test/test_demangle.pass.cpp change is adding #include <algorithm>. I don't know why phab wants this to be a binary.

[philnik]

• Fix Windows CI

[philnik]

• Try to fix Windows

[philnik]

Rebased

libcxx/include/__bit_reference

 // -*- 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___BIT_REFERENCE
 #define _LIBCPP___BIT_REFERENCE
 
+#include <__algorithm/min.h>
 #include <__bits>
 #include <__config>
-#include <algorithm>
+#include <__memory/pointer_traits.h>
+#include <cstring>
 
 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
 #  pragma GCC system_header
 #endif
 
 _LIBCPP_PUSH_MACROS
 #include <__undef_macros>
 

libcxx/include/__format/formatter.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___FORMAT_FORMATTER_H
 #define _LIBCPP___FORMAT_FORMATTER_H
 
 #include <__algorithm/copy.h>
 #include <__algorithm/fill_n.h>
+#include <__algorithm/transform.h>
 #include <__availability>
 #include <__config>
 #include <__format/format_error.h>
 #include <__format/format_fwd.h>
 #include <__format/format_string.h>
 #include <__format/parser_std_format_spec.h>
 #include <string_view>
 

libcxx/include/__hash_table

 // -*- 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__HASH_TABLE
 #define _LIBCPP__HASH_TABLE
 
+#include <__algorithm/max.h>
+#include <__algorithm/min.h>
 #include <__bits> // __libcpp_clz
 #include <__config>
 #include <__debug>
-#include <algorithm>
 #include <cmath>
 #include <initializer_list>
 #include <iterator>
 #include <memory>
 #include <type_traits>
 #include <utility>
 
 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)

libcxx/include/__split_buffer

 // -*- C++ -*-
 #ifndef _LIBCPP_SPLIT_BUFFER
 #define _LIBCPP_SPLIT_BUFFER
 
+#include <__algorithm/max.h>
+#include <__algorithm/move.h>
+#include <__algorithm/move_backward.h>
 #include <__config>
+#include <__iterator/distance.h>
+#include <__iterator/iterator_traits.h>
+#include <__iterator/move_iterator.h>
+#include <__memory/allocator.h>
+#include <__memory/compressed_pair.h>
 #include <__utility/forward.h>
-#include <algorithm>
+#include <memory>
 #include <type_traits>
 
 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
 #  pragma GCC system_header
 #endif
 
 _LIBCPP_PUSH_MACROS
 #include <__undef_macros>

libcxx/include/__tree

 // -*- 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___TREE
 #define _LIBCPP___TREE
 
+#include <__algorithm/min.h>
 #include <__config>
 #include <__utility/forward.h>
-#include <algorithm>
 #include <iterator>
 #include <limits>
 #include <memory>
 #include <stdexcept>
 
 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
 #  pragma GCC system_header
 #endif

libcxx/include/array

 template <size_t I, class T, size_t N> const T& get(const array<T, N>&) noexcept;   // constexpr in C++14
 template <size_t I, class T, size_t N> T&& get(array<T, N>&&) noexcept;             // constexpr in C++14
 template <size_t I, class T, size_t N> const T&& get(const array<T, N>&&) noexcept; // constexpr in C++14
 
 }  // std
 
 */
 
+#include <__algorithm/equal.h>
+#include <__algorithm/fill_n.h>
+#include <__algorithm/lexicographical_compare.h>
+#include <__algorithm/swap_ranges.h>
 #include <__config>
 #include <__debug>
 #include <__tuple>
-#include <algorithm>
 #include <cstdlib> // for _LIBCPP_UNREACHABLE
 #include <iterator>
 #include <stdexcept>
 #include <type_traits>
 #include <utility>
 #include <version>
 
 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)

libcxx/include/deque

 template <class T, class Allocator, class Predicate>
     typename deque<T, Allocator>::size_type
     erase_if(deque<T, Allocator>& c, Predicate pred);    // C++20
 
 }  // std
 
 */
 
+#include <__algorithm/copy.h>
+#include <__algorithm/copy_backward.h>
+#include <__algorithm/equal.h>
+#include <__algorithm/fill_n.h>
+#include <__algorithm/lexicographical_compare.h>
+#include <__algorithm/min.h>
+#include <__algorithm/remove.h>
+#include <__algorithm/remove_if.h>
 #include <__config>
 #include <__debug>
 #include <__iterator/iterator_traits.h>
 #include <__split_buffer>
 #include <__utility/forward.h>
-#include <algorithm>
 #include <compare>
 #include <initializer_list>
 #include <iterator>
 #include <limits>
 #include <stdexcept>
 #include <type_traits>
 #include <version>
 

libcxx/include/experimental/functional

inline namespace fundamentals_v1 {
   } // namespace experimental
 
 } // namespace std
 
 */
 
 #include <__debug>
 #include <__memory/uses_allocator.h>
-#include <algorithm>
 #include <array>
 #include <experimental/__config>
 #include <functional>
 #include <type_traits>
 #include <unordered_map>
 #include <vector>
 
 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)

libcxx/include/experimental/simd

public:
   friend simd_mask operator!=(const simd_mask&, const simd_mask&) noexcept;
 };
 
 } // parallelism_v2
 } // std::experimental
 
 */
 
-#include <algorithm>
 #include <array>
 #include <cstddef>
 #include <experimental/__config>
 #include <functional>
 
 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
 #  pragma GCC system_header
 #endif

libcxx/include/ext/hash_map

template <class Key, class T, class Hash, class Pred, class Alloc>
     bool
     operator!=(const hash_multimap<Key, T, Hash, Pred, Alloc>& x,
                const hash_multimap<Key, T, Hash, Pred, Alloc>& y);
 
 }  // __gnu_cxx
 
 */
 
+#include <__algorithm/is_permutation.h>
 #include <__config>
 #include <__hash_table>
 #include <ext/__hash>
 #include <functional>
 #include <stdexcept>
 #include <type_traits>
 
 #if defined(__DEPRECATED) && __DEPRECATED

libcxx/include/ext/hash_set

 template <class Value, class Hash, class Pred, class Alloc>
     bool
     operator!=(const hash_multiset<Value, Hash, Pred, Alloc>& x,
                const hash_multiset<Value, Hash, Pred, Alloc>& y);
 }  // __gnu_cxx
 
 */
 
+#include <__algorithm/is_permutation.h>
 #include <__config>
 #include <__hash_table>
 #include <ext/__hash>
 #include <functional>
 
 #if defined(__DEPRECATED) && __DEPRECATED
 #if defined(_LIBCPP_WARNING)
     _LIBCPP_WARNING("Use of the header <ext/hash_set> is deprecated.  Migrate to <unordered_set>")

libcxx/include/format

 
 */
 
 // Make sure all feature-test macros are available.
 #include <version>
 // Enable the contents of the header only when libc++ was built with LIBCXX_ENABLE_INCOMPLETE_FEATURES.
 #if !defined(_LIBCPP_HAS_NO_INCOMPLETE_FORMAT)
 
+#include <__algorithm/clamp.h>
 #include <__config>
 #include <__debug>
 #include <__format/format_arg.h>
 #include <__format/format_args.h>
 #include <__format/format_context.h>
 #include <__format/format_error.h>
 #include <__format/format_fwd.h>
 #include <__format/format_parse_context.h>

libcxx/include/forward_list

 template <class T, class Allocator, class Predicate>
     typename forward_list<T, Allocator>::size_type
     erase_if(forward_list<T, Allocator>& c, Predicate pred);    // C++20
 
 }  // std
 
 */
 
+#include <__algorithm/lexicographical_compare.h>
+#include <__algorithm/min.h>
 #include <__config>
 #include <__utility/forward.h>
-#include <algorithm>
 #include <initializer_list>
 #include <iterator>
 #include <limits>
 #include <memory>
 #include <type_traits>
 #include <version>
 
 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)

libcxx/include/fstream

 
 typedef basic_fstream<char>    fstream;
 typedef basic_fstream<wchar_t> wfstream;
 
 }  // std
 
 */
 
+#include <__algorithm/max.h>
 #include <__availability>
 #include <__config>
 #include <__debug>
 #include <__locale>
 #include <cstdio>
 #include <cstdlib>
 #include <istream>
 #include <ostream>

libcxx/include/list

 template <class T, class Allocator, class Predicate>
     typename list<T, Allocator>::size_type
     erase_if(list<T, Allocator>& c, Predicate pred);    // C++20
 
 }  // std
 
 */
 
+#include <__algorithm/equal.h>
+#include <__algorithm/lexicographical_compare.h>
+#include <__algorithm/min.h>
 #include <__config>
 #include <__debug>
 #include <__utility/forward.h>
-#include <algorithm>
 #include <initializer_list>
 #include <iterator>
 #include <limits>
 #include <memory>
 #include <type_traits>
 #include <version>
 
 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)

libcxx/include/locale

 class messages_base;
 template <class charT> class messages;
 template <class charT> class messages_byname;
 
 }  // std
 
 */
 
+#include <__algorithm/equal.h>
+#include <__algorithm/find.h>
+#include <__algorithm/max.h>
+#include <__algorithm/reverse.h>
 #include <__config>
 #include <__debug>
 #include <__locale>
-#include <algorithm>
 #ifndef __APPLE__
 # include <cstdarg>
 #endif
 #include <cstdio>
 #include <cstdlib>
 #include <ctime>
 #include <ios>
 #include <iterator>

libcxx/include/map

 template <class Key, class T, class Compare, class Allocator, class Predicate>
 typename multimap<Key, T, Compare, Allocator>::size_type
 erase_if(multimap<Key, T, Compare, Allocator>& c, Predicate pred);  // C++20
 
 }  // std
 
 */
 
+#include <__algorithm/equal.h>
+#include <__algorithm/lexicographical_compare.h>
 #include <__config>
 #include <__debug>
 #include <__functional/is_transparent.h>
 #include <__iterator/iterator_traits.h>
 #include <__node_handle>
 #include <__tree>
 #include <__utility/forward.h>
 #include <compare>

libcxx/include/queue

template <class T, class Container, class Compare>
   void swap(priority_queue<T, Container, Compare>& x,
             priority_queue<T, Container, Compare>& y)
             noexcept(noexcept(x.swap(y)));
 
 }  // std
 
 */
 
+#include <__algorithm/make_heap.h>
+#include <__algorithm/pop_heap.h>
+#include <__algorithm/push_heap.h>
 #include <__config>
 #include <__iterator/iterator_traits.h>
 #include <__memory/uses_allocator.h>
 #include <__utility/forward.h>
-#include <algorithm>
 #include <compare>
 #include <deque>
 #include <functional>
 #include <type_traits>
 #include <vector>
 #include <version>
 
 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)

libcxx/include/random

 #include <__random/subtract_with_carry_engine.h>
 #include <__random/uniform_int_distribution.h>
 #include <__random/uniform_random_bit_generator.h>
 #include <__random/uniform_real_distribution.h>
 #include <__random/weibull_distribution.h>
 #include <initializer_list>
 #include <version>
 
-#include <algorithm>   // for backward compatibility; TODO remove it
 #include <cmath>       // for backward compatibility; TODO remove it
 #include <cstddef>     // for backward compatibility; TODO remove it
 #include <cstdint>     // for backward compatibility; TODO remove it
 #include <iosfwd>      // for backward compatibility; TODO remove it
 #include <limits>      // for backward compatibility; TODO remove it
 #include <numeric>     // for backward compatibility; TODO remove it
 #include <string>      // for backward compatibility; TODO remove it
 #include <type_traits> // for backward compatibility; TODO remove it
 #include <vector>      // for backward compatibility; TODO remove it
 
 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
 #  pragma GCC system_header
 #endif
 
 #endif // _LIBCPP_RANDOM

libcxx/include/set

 template <class Key, class Compare, class Allocator, class Predicate>
 typename multiset<Key, Compare, Allocator>::size_type
 erase_if(multiset<Key, Compare, Allocator>& c, Predicate pred);  // C++20
 
 }  // std
 
 */
 
+#include <__algorithm/equal.h>
+#include <__algorithm/lexicographical_compare.h>
 #include <__config>
 #include <__debug>
 #include <__functional/is_transparent.h>
 #include <__iterator/iterator_traits.h>
 #include <__node_handle>
 #include <__tree>
 #include <__utility/forward.h>
 #include <compare>

libcxx/include/string

 basic_string<char8_t>  operator "" s( const char8_t *str,  size_t len ); // C++20
 basic_string<char16_t> operator "" s( const char16_t *str, size_t len ); // C++14
 basic_string<char32_t> operator "" s( const char32_t *str, size_t len ); // C++14
 
 }  // std
 
 */
 
+#include <__algorithm/max.h>
+#include <__algorithm/remove.h>
+#include <__algorithm/remove_if.h>
 #include <__config>
 #include <__debug>
 #include <__ios/fpos.h>
 #include <__iterator/wrap_iter.h>
-#include <algorithm>
 #include <compare>
 #include <cstdio>  // EOF
 #include <cstdlib>
 #include <cstring>
 #include <initializer_list>
 #include <iosfwd>
 #include <iterator>
 #include <memory>

libcxx/include/string_view

 #include <__config>
 #include <__debug>
 #include <__ranges/concepts.h>
 #include <__ranges/data.h>
 #include <__ranges/enable_borrowed_range.h>
 #include <__ranges/enable_view.h>
 #include <__ranges/size.h>
 #include <__string>
-#include <algorithm>
 #include <compare>
 #include <iosfwd>
 #include <iterator>
 #include <limits>
 #include <stdexcept>
 #include <type_traits>
 #include <version>
 

libcxx/include/unordered_map

template <class Key, class T, class Hash, class Pred, class Alloc>
     bool
     operator!=(const unordered_multimap<Key, T, Hash, Pred, Alloc>& x,
                const unordered_multimap<Key, T, Hash, Pred, Alloc>& y);
 
 }  // std
 
 */
 
+#include <__algorithm/is_permutation.h>
 #include <__config>
 #include <__debug>
 #include <__functional/is_transparent.h>
 #include <__hash_table>
 #include <__iterator/iterator_traits.h>
 #include <__memory/addressof.h>
 #include <__node_handle>
 #include <__utility/forward.h>

libcxx/include/unordered_set

 template <class Value, class Hash, class Pred, class Alloc>
     bool
     operator!=(const unordered_multiset<Value, Hash, Pred, Alloc>& x,
                const unordered_multiset<Value, Hash, Pred, Alloc>& y);
 }  // std
 
 */
 
+#include <__algorithm/is_permutation.h>
 #include <__config>
 #include <__debug>
 #include <__functional/is_transparent.h>
 #include <__hash_table>
 #include <__memory/addressof.h>
 #include <__node_handle>
 #include <__utility/forward.h>
 #include <compare>

libcxx/include/valarray

 template <class T> unspecified2 begin(const valarray<T>& v);
 template <class T> unspecified1 end(valarray<T>& v);
 template <class T> unspecified2 end(const valarray<T>& v);
 
 }  // std
 
 */
 
+#include <__algorithm/copy.h>
+#include <__algorithm/count.h>
+#include <__algorithm/fill.h>
+#include <__algorithm/max_element.h>
+#include <__algorithm/min.h>
 #include <__config>
-#include <algorithm>
 #include <cmath>
 #include <cstddef>
 #include <functional>
 #include <initializer_list>
 #include <new>
 #include <version>
 
 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)

libcxx/include/vector

 template <class T, class Allocator, class Predicate>
 typename vector<T, Allocator>::size_type
 erase_if(vector<T, Allocator>& c, Predicate pred);    // C++20
 
 }  // std
 
 */
 
+#include <__algorithm/copy.h>
+#include <__algorithm/equal.h>
+#include <__algorithm/fill_n.h>
+#include <__algorithm/lexicographical_compare.h>
+#include <__algorithm/remove.h>
+#include <__algorithm/remove_if.h>
+#include <__algorithm/rotate.h>
 #include <__bit_reference>
 #include <__config>
 #include <__debug>
 #include <__iterator/iterator_traits.h>
 #include <__iterator/wrap_iter.h>
 #include <__split_buffer>
 #include <__utility/forward.h>
-#include <algorithm>
 #include <climits>
 #include <compare>
 #include <cstdlib>
 #include <cstring>
 #include <initializer_list>
 #include <iosfwd> // for forward declaration of vector
 #include <limits>
 #include <memory>

libcxx/test/std/containers/sequences/forwardlist/forwardlist.cons/deduct.pass.cpp

 //===----------------------------------------------------------------------===//
 //
 // 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
 //
 //===----------------------------------------------------------------------===//
 
 // <forward_list>
 // UNSUPPORTED: c++03, c++11, c++14
 
 // template <class InputIterator, class Allocator = allocator<typename iterator_traits<InputIterator>::value_type>>
 //    forward_list(InputIterator, InputIterator, Allocator = Allocator())
 //    -> forward_list<typename iterator_traits<InputIterator>::value_type, Allocator>;
 //
 
+#include <algorithm>
 #include <forward_list>
 #include <iterator>
 #include <cassert>
 #include <cstddef>
 #include <climits> // INT_MAX
 
 #include "deduction_guides_sfinae_checks.h"
 #include "test_macros.h"

libcxx/test/std/containers/sequences/list/list.ops/sort.pass.cpp

 //===----------------------------------------------------------------------===//
 //
 // 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
 //
 //===----------------------------------------------------------------------===//
 
 // <list>
 
 // void sort();
 
+#include <algorithm>
 #include <list>
 #include <random>
 #include <vector>
 #include <cassert>
 
 #include "test_macros.h"
 #include "min_allocator.h"
 
void test_stable(int N)
     for (int i = 0; i < N; ++i)
         v.push_back(Payload(i/2));
     std::shuffle(v.begin(), v.end(), randomness);
     for (int i = 0; i < N; ++i)
         v[i].side = i;
 
     C c(v.begin(), v.end());
     c.sort();
     assert(distance(c.begin(), c.end()) == N);
 
 //  Are we sorted?
     typename C::const_iterator j = c.begin();
     for (int i = 0; i < N; ++i, ++j)
         assert(j->val == i/2);
 
 //  Are we stable?
     for (C::const_iterator it = c.begin(); it != c.end(); ++it)