[libc++] Granularize algorithm includes
Reviewed By: Mordante, ldionne, Quuxplusone, #libc, #libc_abi
Spies: #libc_vendors, libcxx-commits, miyuki
Differential Revision: https://reviews.llvm.org/D119667
NOKEYCHECK=True
GitOrigin-RevId: 2e2f3158c604adb8401a2a44a03f58d4b6f1c7f9
diff --git a/docs/ReleaseNotes.rst b/docs/ReleaseNotes.rst
index 0b77702..c57a7de 100644
--- a/docs/ReleaseNotes.rst
+++ b/docs/ReleaseNotes.rst
@@ -52,6 +52,10 @@
``<filesystem>`` header. The associated macro
``_LIBCPP_DEPRECATED_EXPERIMENTAL_FILESYSTEM`` has also been removed.
+- Transitive includes of ``<algorithm>`` have been removed. If you see compiler errors
+ related to missing declarations inside namespace ``std`` when updating libc++,
+ you are probably missing ``#include <algorithm>`` in a file where you use algorithms.
+
ABI Changes
-----------
diff --git a/include/__bit_reference b/include/__bit_reference
index 482738f..423acee 100644
--- a/include/__bit_reference
+++ b/include/__bit_reference
@@ -10,9 +10,13 @@
#ifndef _LIBCPP___BIT_REFERENCE
#define _LIBCPP___BIT_REFERENCE
+#include <__algorithm/min.h>
#include <__bits>
#include <__config>
-#include <algorithm>
+#include <__iterator/iterator_traits.h>
+#include <__memory/pointer_traits.h>
+#include <cstring>
+#include <type_traits>
#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
# pragma GCC system_header
diff --git a/include/__filesystem/path.h b/include/__filesystem/path.h
index 89b5107..6b4b1ae 100644
--- a/include/__filesystem/path.h
+++ b/include/__filesystem/path.h
@@ -10,6 +10,8 @@
#ifndef _LIBCPP___FILESYSTEM_PATH_H
#define _LIBCPP___FILESYSTEM_PATH_H
+#include <__algorithm/replace.h>
+#include <__algorithm/replace_copy.h>
#include <__availability>
#include <__config>
#include <__iterator/back_insert_iterator.h>
diff --git a/include/__format/formatter.h b/include/__format/formatter.h
index 1f42314..7e1ae31 100644
--- a/include/__format/formatter.h
+++ b/include/__format/formatter.h
@@ -12,6 +12,7 @@
#include <__algorithm/copy.h>
#include <__algorithm/fill_n.h>
+#include <__algorithm/transform.h>
#include <__availability>
#include <__config>
#include <__format/format_error.h>
diff --git a/include/__hash_table b/include/__hash_table
index cce9145..6b1f65c 100644
--- a/include/__hash_table
+++ b/include/__hash_table
@@ -10,10 +10,12 @@
#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 <__functional/hash.h>
#include <cmath>
#include <initializer_list>
#include <iterator>
diff --git a/include/__split_buffer b/include/__split_buffer
index bd6d231..9565e16 100644
--- a/include/__split_buffer
+++ b/include/__split_buffer
@@ -2,9 +2,17 @@
#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)
diff --git a/include/__tree b/include/__tree
index 2733a1e..eeb6b11 100644
--- a/include/__tree
+++ b/include/__tree
@@ -10,9 +10,9 @@
#ifndef _LIBCPP___TREE
#define _LIBCPP___TREE
+#include <__algorithm/min.h>
#include <__config>
#include <__utility/forward.h>
-#include <algorithm>
#include <iterator>
#include <limits>
#include <memory>
diff --git a/include/array b/include/array
index 8d6a3b5..e55ee43 100644
--- a/include/array
+++ b/include/array
@@ -108,11 +108,14 @@
*/
+#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 <__utility/unreachable.h>
-#include <algorithm>
#include <iterator>
#include <stdexcept>
#include <type_traits>
diff --git a/include/bitset b/include/bitset
index fa37e70..875e8ef 100644
--- a/include/bitset
+++ b/include/bitset
@@ -112,8 +112,10 @@
*/
+#include <__algorithm/fill.h>
#include <__bit_reference>
#include <__config>
+#include <__functional/unary_function.h>
#include <climits>
#include <cstddef>
#include <iosfwd>
diff --git a/include/deque b/include/deque
index 33e7134..fc96475 100644
--- a/include/deque
+++ b/include/deque
@@ -160,12 +160,20 @@
*/
+#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 <__algorithm/unwrap_iter.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>
diff --git a/include/experimental/functional b/include/experimental/functional
index de21ab6..087f7c9 100644
--- a/include/experimental/functional
+++ b/include/experimental/functional
@@ -62,7 +62,6 @@
#include <__debug>
#include <__memory/uses_allocator.h>
-#include <algorithm>
#include <array>
#include <experimental/__config>
#include <functional>
diff --git a/include/experimental/simd b/include/experimental/simd
index 6e8bfab..31426a9 100644
--- a/include/experimental/simd
+++ b/include/experimental/simd
@@ -649,7 +649,6 @@
*/
-#include <algorithm>
#include <array>
#include <cstddef>
#include <experimental/__config>
diff --git a/include/ext/hash_map b/include/ext/hash_map
index 4d9c08c..1816626 100644
--- a/include/ext/hash_map
+++ b/include/ext/hash_map
@@ -201,6 +201,7 @@
*/
+#include <__algorithm/is_permutation.h>
#include <__config>
#include <__hash_table>
#include <ext/__hash>
diff --git a/include/ext/hash_set b/include/ext/hash_set
index 254f482..cbd621b 100644
--- a/include/ext/hash_set
+++ b/include/ext/hash_set
@@ -192,6 +192,7 @@
*/
+#include <__algorithm/is_permutation.h>
#include <__config>
#include <__hash_table>
#include <ext/__hash>
diff --git a/include/format b/include/format
index 03c25f1..356a305 100644
--- a/include/format
+++ b/include/format
@@ -122,6 +122,7 @@
// 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>
diff --git a/include/forward_list b/include/forward_list
index 5e864fe..e01a8e7 100644
--- a/include/forward_list
+++ b/include/forward_list
@@ -179,9 +179,11 @@
*/
+#include <__algorithm/comp.h>
+#include <__algorithm/lexicographical_compare.h>
+#include <__algorithm/min.h>
#include <__config>
#include <__utility/forward.h>
-#include <algorithm>
#include <initializer_list>
#include <iterator>
#include <limits>
diff --git a/include/fstream b/include/fstream
index 9ee3d14..d7d8fb1 100644
--- a/include/fstream
+++ b/include/fstream
@@ -179,6 +179,7 @@
*/
+#include <__algorithm/max.h>
#include <__availability>
#include <__config>
#include <__debug>
diff --git a/include/list b/include/list
index 91e2c97..c643cb5 100644
--- a/include/list
+++ b/include/list
@@ -180,10 +180,13 @@
*/
+#include <__algorithm/comp.h>
+#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>
diff --git a/include/locale b/include/locale
index ed2b971..fa82d44 100644
--- a/include/locale
+++ b/include/locale
@@ -187,10 +187,14 @@
*/
+#include <__algorithm/equal.h>
+#include <__algorithm/find.h>
+#include <__algorithm/max.h>
+#include <__algorithm/reverse.h>
+#include <__algorithm/unwrap_iter.h>
#include <__config>
#include <__debug>
#include <__locale>
-#include <algorithm>
#ifndef __APPLE__
# include <cstdarg>
#endif
diff --git a/include/map b/include/map
index cb856fa..a68c6d1 100644
--- a/include/map
+++ b/include/map
@@ -528,6 +528,8 @@
*/
+#include <__algorithm/equal.h>
+#include <__algorithm/lexicographical_compare.h>
#include <__config>
#include <__debug>
#include <__functional/is_transparent.h>
diff --git a/include/queue b/include/queue
index fe0af16..b8b7ec4 100644
--- a/include/queue
+++ b/include/queue
@@ -217,11 +217,13 @@
*/
+#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>
diff --git a/include/random b/include/random
index 0c7d490..cf1ac24 100644
--- a/include/random
+++ b/include/random
@@ -1717,7 +1717,6 @@
#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
diff --git a/include/regex b/include/regex
index f2b53f1..dadd7b9 100644
--- a/include/regex
+++ b/include/regex
@@ -762,6 +762,7 @@
} // std
*/
+#include <__algorithm/find.h>
#include <__config>
#include <__debug>
#include <__iterator/wrap_iter.h>
diff --git a/include/set b/include/set
index 898fa6c..b346e57 100644
--- a/include/set
+++ b/include/set
@@ -471,6 +471,8 @@
*/
+#include <__algorithm/equal.h>
+#include <__algorithm/lexicographical_compare.h>
#include <__config>
#include <__debug>
#include <__functional/is_transparent.h>
diff --git a/include/string b/include/string
index 809ae41..3e7f2e9 100644
--- a/include/string
+++ b/include/string
@@ -518,11 +518,14 @@
*/
+#include <__algorithm/max.h>
+#include <__algorithm/min.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>
diff --git a/include/string_view b/include/string_view
index 48fd083..a5256fb 100644
--- a/include/string_view
+++ b/include/string_view
@@ -195,6 +195,7 @@
*/
+#include <__algorithm/min.h>
#include <__config>
#include <__debug>
#include <__ranges/concepts.h>
@@ -203,7 +204,6 @@
#include <__ranges/enable_view.h>
#include <__ranges/size.h>
#include <__string>
-#include <algorithm>
#include <compare>
#include <iosfwd>
#include <iterator>
diff --git a/include/unordered_map b/include/unordered_map
index f0f5d1c..34c3d18 100644
--- a/include/unordered_map
+++ b/include/unordered_map
@@ -514,6 +514,7 @@
*/
+#include <__algorithm/is_permutation.h>
#include <__config>
#include <__debug>
#include <__functional/is_transparent.h>
diff --git a/include/unordered_set b/include/unordered_set
index b3a653f..bf972be 100644
--- a/include/unordered_set
+++ b/include/unordered_set
@@ -459,6 +459,7 @@
*/
+#include <__algorithm/is_permutation.h>
#include <__config>
#include <__debug>
#include <__functional/is_transparent.h>
diff --git a/include/valarray b/include/valarray
index 5536398..ac1ca9b 100644
--- a/include/valarray
+++ b/include/valarray
@@ -341,8 +341,14 @@
*/
+#include <__algorithm/copy.h>
+#include <__algorithm/count.h>
+#include <__algorithm/fill.h>
+#include <__algorithm/max_element.h>
+#include <__algorithm/min.h>
+#include <__algorithm/min_element.h>
+#include <__algorithm/unwrap_iter.h>
#include <__config>
-#include <algorithm>
#include <cmath>
#include <cstddef>
#include <functional>
diff --git a/include/vector b/include/vector
index 43584e0..26683ae 100644
--- a/include/vector
+++ b/include/vector
@@ -271,14 +271,22 @@
*/
+#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 <__algorithm/unwrap_iter.h>
#include <__bit_reference>
#include <__config>
#include <__debug>
+#include <__functional/hash.h>
#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>
diff --git a/test/std/containers/sequences/forwardlist/forwardlist.cons/deduct.pass.cpp b/test/std/containers/sequences/forwardlist/forwardlist.cons/deduct.pass.cpp
index 61f31af..74eb69b 100644
--- a/test/std/containers/sequences/forwardlist/forwardlist.cons/deduct.pass.cpp
+++ b/test/std/containers/sequences/forwardlist/forwardlist.cons/deduct.pass.cpp
@@ -14,6 +14,7 @@
// -> forward_list<typename iterator_traits<InputIterator>::value_type, Allocator>;
//
+#include <algorithm>
#include <forward_list>
#include <iterator>
#include <cassert>
diff --git a/test/std/containers/sequences/list/list.ops/sort.pass.cpp b/test/std/containers/sequences/list/list.ops/sort.pass.cpp
index 3157b28..6349a3d 100644
--- a/test/std/containers/sequences/list/list.ops/sort.pass.cpp
+++ b/test/std/containers/sequences/list/list.ops/sort.pass.cpp
@@ -10,6 +10,7 @@
// void sort();
+#include <algorithm>
#include <list>
#include <random>
#include <vector>
diff --git a/test/std/utilities/format/format.formatter/format.formatter.spec/formatter.floating_point.pass.cpp b/test/std/utilities/format/format.formatter/format.formatter.spec/formatter.floating_point.pass.cpp
index 1934471..f249037 100644
--- a/test/std/utilities/format/format.formatter/format.formatter.spec/formatter.floating_point.pass.cpp
+++ b/test/std/utilities/format/format.formatter/format.formatter.spec/formatter.floating_point.pass.cpp
@@ -26,6 +26,7 @@
#include <format>
+#include <algorithm>
#include <array>
#include <cassert>
#include <cmath>