libstdc++: Introduce new headers for C++20 ranges components

This introduces two new headers:

<bits/ranges_base.h> defines the minimal components needed
for using C++20 ranges (customization point objects such as
std::ranges::begin, concepts such as std::ranges::range, etc.)

<bits/ranges_util.h> includes <bits/ranges_base.h> and additionally
defines subrange, which is needed by <bits/ranges_algo.h>.

Most of the content of <bits/ranges_base.h> was previously defined in
<bits/range_access.h>, but a few pieces were only defined in <ranges>.
This meant the entire <ranges> header was needed in <algorithm> and
<memory>, even though they don't use all the range adaptors.

By moving the ranges components out of <bits/range_access.h> that file
is left defining just the contents of [iterator.range] i.e. std::begin,
std::end, std::size etc. and not C++20 ranges components.

For consistency with other C++20 ranges headers, <bits/range_cmp.h> is
renamed to <bits/ranges_cmp.h>.

libstdc++-v3/ChangeLog:

	* include/Makefile.am: Add new headers and adjust for renamed
	header.
	* include/Makefile.in: Regenerate.
	* include/bits/iterator_concepts.h: Adjust for renamed header.
	* include/bits/range_access.h (ranges::*): Move to new
	<bits/ranges_base.h> header.
	* include/bits/ranges_algobase.h: Include new <bits/ranges_base.h>
	header instead of <ranges>.
	* include/bits/ranges_algo.h: Include new <bits/ranges_util.h>
	header.
	* include/bits/range_cmp.h: Moved to...
	* include/bits/ranges_cmp.h: ...here.
	* include/bits/ranges_base.h: New header.
	* include/bits/ranges_util.h: New header.
	* include/experimental/string_view: Include new
	<bits/ranges_base.h> header.
	* include/std/functional: Adjust for renamed header.
	* include/std/ranges (ranges::view_base, ranges::enable_view)
	(ranges::dangling, ranges::borrowed_iterator_t): Move to new
	<bits/ranges_base.h> header.
	(ranges::view_interface, ranges::subrange)
	(ranges::borrowed_subrange_t): Move to new <bits/ranges_util.h>
	header.
	* include/std/span: Include new <bits/ranges_base.h> header.
	* include/std/string_view: Likewise.
	* testsuite/24_iterators/back_insert_iterator/pr93884.cc: Add
	missing <ranges> header.
	* testsuite/24_iterators/front_insert_iterator/pr93884.cc:
	Likewise.

4 files changed, 16 insertions, 404 deletions

diff --git a/libstdc++-v3/include/std/functional b/libstdc++-v3/include/std/functional
index 407b93f..9bad692 100644
--- a/libstdc++-v3/include/std/functional
+++ b/libstdc++-v3/include/std/functional
@@ -65,7 +65,7 @@
 # include <bits/stl_algo.h>
 #endif
 #if __cplusplus > 201703L
-# include <bits/range_cmp.h>
+# include <bits/ranges_cmp.h>
 # include <compare>
 #endif
 
diff --git a/libstdc++-v3/include/std/ranges b/libstdc++-v3/include/std/ranges
index 1bf894d..e7fa449 100644
--- a/libstdc++-v3/include/std/ranges
+++ b/libstdc++-v3/include/std/ranges
@@ -38,12 +38,13 @@
 
 #if __cpp_lib_concepts
 
-#include <bits/refwrap.h>
 #include <compare>
 #include <initializer_list>
 #include <iterator>
 #include <optional>
 #include <tuple>
+#include <bits/ranges_util.h>
+#include <bits/refwrap.h>
 
 /**
  * @defgroup ranges Ranges
@@ -56,410 +57,18 @@ namespace std _GLIBCXX_VISIBILITY(default)
 _GLIBCXX_BEGIN_NAMESPACE_VERSION
 namespace ranges
 {
-  // [range.range] The range concept.
-  // [range.sized] The sized_range concept.
-  // Defined in <bits/range_access.h>
-
-  // [range.refinements]
-  // Defined in <bits/range_access.h>
-
-  struct view_base { };
-
-  template<typename _Tp>
-    inline constexpr bool enable_view = derived_from<_Tp, view_base>;
-
-  template<typename _Tp>
-    concept view
-      = range<_Tp> && movable<_Tp> && default_initializable<_Tp>
-	&& enable_view<_Tp>;
-
-  /// A range which can be safely converted to a view.
-  template<typename _Tp>
-    concept viewable_range = range<_Tp>
-      && (borrowed_range<_Tp> || view<remove_cvref_t<_Tp>>);
-
-  namespace __detail
-  {
-    template<typename _Range>
-      concept __simple_view = view<_Range> && range<const _Range>
-	&& same_as<iterator_t<_Range>, iterator_t<const _Range>>
-	&& same_as<sentinel_t<_Range>, sentinel_t<const _Range>>;
-
-    template<typename _It>
-      concept __has_arrow = input_iterator<_It>
-	&& (is_pointer_v<_It> || requires(_It __it) { __it.operator->(); });
-
-    template<typename _Tp, typename _Up>
-      concept __not_same_as
-	= !same_as<remove_cvref_t<_Tp>, remove_cvref_t<_Up>>;
-  } // namespace __detail
-
-  template<typename _Derived>
-    requires is_class_v<_Derived> && same_as<_Derived, remove_cv_t<_Derived>>
-    class view_interface : public view_base
-    {
-    private:
-      constexpr _Derived& _M_derived() noexcept
-      {
-	static_assert(derived_from<_Derived, view_interface<_Derived>>);
-	static_assert(view<_Derived>);
-	return static_cast<_Derived&>(*this);
-      }
-
-      constexpr const _Derived& _M_derived() const noexcept
-      {
-	static_assert(derived_from<_Derived, view_interface<_Derived>>);
-	static_assert(view<_Derived>);
-	return static_cast<const _Derived&>(*this);
-      }
-
-    public:
-      constexpr bool
-      empty() requires forward_range<_Derived>
-      { return ranges::begin(_M_derived()) == ranges::end(_M_derived()); }
-
-      constexpr bool
-      empty() const requires forward_range<const _Derived>
-      { return ranges::begin(_M_derived()) == ranges::end(_M_derived()); }
-
-      constexpr explicit
-      operator bool() requires requires { ranges::empty(_M_derived()); }
-      { return !ranges::empty(_M_derived()); }
-
-      constexpr explicit
-      operator bool() const requires requires { ranges::empty(_M_derived()); }
-      { return !ranges::empty(_M_derived()); }
-
-      constexpr auto
-      data() requires contiguous_iterator<iterator_t<_Derived>>
-      { return to_address(ranges::begin(_M_derived())); }
-
-      constexpr auto
-      data() const
-      requires range<const _Derived>
-	&& contiguous_iterator<iterator_t<const _Derived>>
-      { return to_address(ranges::begin(_M_derived())); }
-
-      constexpr auto
-      size()
-      requires forward_range<_Derived>
-	&& sized_sentinel_for<sentinel_t<_Derived>, iterator_t<_Derived>>
-      { return ranges::end(_M_derived()) - ranges::begin(_M_derived()); }
-
-      constexpr auto
-      size() const
-      requires forward_range<const _Derived>
-	&& sized_sentinel_for<sentinel_t<const _Derived>,
-			      iterator_t<const _Derived>>
-      { return ranges::end(_M_derived()) - ranges::begin(_M_derived()); }
-
-      constexpr decltype(auto)
-      front() requires forward_range<_Derived>
-      {
-	__glibcxx_assert(!empty());
-	return *ranges::begin(_M_derived());
-      }
-
-      constexpr decltype(auto)
-      front() const requires forward_range<const _Derived>
-      {
-	__glibcxx_assert(!empty());
-	return *ranges::begin(_M_derived());
-      }
-
-      constexpr decltype(auto)
-      back()
-      requires bidirectional_range<_Derived> && common_range<_Derived>
-      {
-	__glibcxx_assert(!empty());
-	return *ranges::prev(ranges::end(_M_derived()));
-      }
-
-      constexpr decltype(auto)
-      back() const
-      requires bidirectional_range<const _Derived>
-	&& common_range<const _Derived>
-      {
-	__glibcxx_assert(!empty());
-	return *ranges::prev(ranges::end(_M_derived()));
-      }
-
-      template<random_access_range _Range = _Derived>
-	constexpr decltype(auto)
-	operator[](range_difference_t<_Range> __n)
-	{ return ranges::begin(_M_derived())[__n]; }
-
-      template<random_access_range _Range = const _Derived>
-	constexpr decltype(auto)
-	operator[](range_difference_t<_Range> __n) const
-	{ return ranges::begin(_M_derived())[__n]; }
-    };
-
-  namespace __detail
-  {
-    template<class _From, class _To>
-      concept __convertible_to_non_slicing = convertible_to<_From, _To>
-	&& !(is_pointer_v<decay_t<_From>> && is_pointer_v<decay_t<_To>>
-	    && __not_same_as<remove_pointer_t<decay_t<_From>>,
-			     remove_pointer_t<decay_t<_To>>>);
-
-    template<typename _Tp>
-      concept __pair_like
-	= !is_reference_v<_Tp> && requires(_Tp __t)
-	{
-	  typename tuple_size<_Tp>::type;
-	  requires derived_from<tuple_size<_Tp>, integral_constant<size_t, 2>>;
-	  typename tuple_element_t<0, remove_const_t<_Tp>>;
-	  typename tuple_element_t<1, remove_const_t<_Tp>>;
-	  { get<0>(__t) } -> convertible_to<const tuple_element_t<0, _Tp>&>;
-	  { get<1>(__t) } -> convertible_to<const tuple_element_t<1, _Tp>&>;
-	};
-
-    template<typename _Tp, typename _Up, typename _Vp>
-      concept __pair_like_convertible_from
-	= !range<_Tp> && __pair_like<_Tp>
-	&& constructible_from<_Tp, _Up, _Vp>
-	&& __convertible_to_non_slicing<_Up, tuple_element_t<0, _Tp>>
-	&& convertible_to<_Vp, tuple_element_t<1, _Tp>>;
-
-    template<typename _Tp>
-      concept __iterator_sentinel_pair
-	= !range<_Tp> && __pair_like<_Tp>
-	&& sentinel_for<tuple_element_t<1, _Tp>, tuple_element_t<0, _Tp>>;
-
-  } // namespace __detail
-
-  enum class subrange_kind : bool { unsized, sized };
-
-  template<input_or_output_iterator _It, sentinel_for<_It> _Sent = _It,
-	   subrange_kind _Kind = sized_sentinel_for<_Sent, _It>
-	     ? subrange_kind::sized : subrange_kind::unsized>
-    requires (_Kind == subrange_kind::sized || !sized_sentinel_for<_Sent, _It>)
-    class subrange : public view_interface<subrange<_It, _Sent, _Kind>>
-    {
-    private:
-      // XXX: gcc complains when using constexpr here
-      static const bool _S_store_size
-	= _Kind == subrange_kind::sized && !sized_sentinel_for<_Sent, _It>;
-
-      _It _M_begin = _It();
-      _Sent _M_end = _Sent();
-
-      template<typename, bool = _S_store_size>
-	struct _Size
-	{ };
-
-      template<typename _Tp>
-	struct _Size<_Tp, true>
-	{ __detail::__make_unsigned_like_t<_Tp> _M_size; };
-
-      [[no_unique_address]] _Size<iter_difference_t<_It>> _M_size = {};
-
-    public:
-      subrange() = default;
-
-      constexpr
-      subrange(__detail::__convertible_to_non_slicing<_It> auto __i, _Sent __s)
-	requires (!_S_store_size)
-      : _M_begin(std::move(__i)), _M_end(__s)
-      { }
-
-      constexpr
-      subrange(__detail::__convertible_to_non_slicing<_It> auto __i, _Sent __s,
-	       __detail::__make_unsigned_like_t<iter_difference_t<_It>> __n)
-	requires (_Kind == subrange_kind::sized)
-      : _M_begin(std::move(__i)), _M_end(__s)
-      {
-	using __detail::__to_unsigned_like;
-	__glibcxx_assert(__n == __to_unsigned_like(ranges::distance(__i, __s)));
-	if constexpr (_S_store_size)
-	  _M_size._M_size = __n;
-      }
-
-      template<__detail::__not_same_as<subrange> _Rng>
-	requires borrowed_range<_Rng>
-	  && __detail::__convertible_to_non_slicing<iterator_t<_Rng>, _It>
-	  && convertible_to<sentinel_t<_Rng>, _Sent>
-	constexpr
-	subrange(_Rng&& __r) requires _S_store_size && sized_range<_Rng>
-	: subrange{__r, ranges::size(__r)}
-	{ }
-
-      template<__detail::__not_same_as<subrange> _Rng>
-	requires borrowed_range<_Rng>
-	  && __detail::__convertible_to_non_slicing<iterator_t<_Rng>, _It>
-	  && convertible_to<sentinel_t<_Rng>, _Sent>
-	constexpr
-	subrange(_Rng&& __r) requires (!_S_store_size)
-	: subrange{ranges::begin(__r), ranges::end(__r)}
-	{ }
-
-      template<borrowed_range _Rng>
-	requires __detail::__convertible_to_non_slicing<iterator_t<_Rng>, _It>
-	  && convertible_to<sentinel_t<_Rng>, _Sent>
-	constexpr
-	subrange(_Rng&& __r,
-		 __detail::__make_unsigned_like_t<iter_difference_t<_It>> __n)
-	requires (_Kind == subrange_kind::sized)
-	: subrange{ranges::begin(__r), ranges::end(__r), __n}
-	{ }
-
-      template<__detail::__not_same_as<subrange> _PairLike>
-	requires __detail::__pair_like_convertible_from<_PairLike, const _It&,
-							const _Sent&>
-      constexpr
-      operator _PairLike() const
-      { return _PairLike(_M_begin, _M_end); }
-
-      constexpr _It
-      begin() const requires copyable<_It>
-      { return _M_begin; }
-
-      [[nodiscard]] constexpr _It
-      begin() requires (!copyable<_It>)
-      { return std::move(_M_begin); }
-
-      constexpr _Sent end() const { return _M_end; }
-
-      constexpr bool empty() const { return _M_begin == _M_end; }
-
-      constexpr __detail::__make_unsigned_like_t<iter_difference_t<_It>>
-      size() const requires (_Kind == subrange_kind::sized)
-      {
-	if constexpr (_S_store_size)
-	  return _M_size._M_size;
-	else
-	  return __detail::__to_unsigned_like(_M_end - _M_begin);
-      }
-
-      [[nodiscard]] constexpr subrange
-      next(iter_difference_t<_It> __n = 1) const &
-	requires forward_iterator<_It>
-      {
-	auto __tmp = *this;
-	__tmp.advance(__n);
-	return __tmp;
-      }
-
-      [[nodiscard]] constexpr subrange
-      next(iter_difference_t<_It> __n = 1) &&
-      {
-	advance(__n);
-	return std::move(*this);
-      }
-
-      [[nodiscard]] constexpr subrange
-      prev(iter_difference_t<_It> __n = 1) const
-	requires bidirectional_iterator<_It>
-      {
-	auto __tmp = *this;
-	__tmp.advance(-__n);
-	return __tmp;
-      }
-
-      constexpr subrange&
-      advance(iter_difference_t<_It> __n)
-      {
-	// _GLIBCXX_RESOLVE_LIB_DEFECTS
-	// 3433. subrange::advance(n) has UB when n < 0
-	if constexpr (bidirectional_iterator<_It>)
-	  if (__n < 0)
-	    {
-	      ranges::advance(_M_begin, __n);
-	      if constexpr (_S_store_size)
-		_M_size._M_size += __detail::__to_unsigned_like(-__n);
-	      return *this;
-	    }
-
-	__glibcxx_assert(__n >= 0);
-	auto __d = __n - ranges::advance(_M_begin, __n, _M_end);
-	if constexpr (_S_store_size)
-	  _M_size._M_size -= __detail::__to_unsigned_like(__d);
-	return *this;
-      }
-    };
-
-  template<input_or_output_iterator _It, sentinel_for<_It> _Sent>
-    subrange(_It, _Sent) -> subrange<_It, _Sent>;
-
-  template<input_or_output_iterator _It, sentinel_for<_It> _Sent>
-    subrange(_It, _Sent,
-	     __detail::__make_unsigned_like_t<iter_difference_t<_It>>)
-      -> subrange<_It, _Sent, subrange_kind::sized>;
-
-  template<__detail::__iterator_sentinel_pair _Pr>
-    subrange(_Pr)
-      -> subrange<tuple_element_t<0, _Pr>, tuple_element_t<1, _Pr>>;
-
-  template<__detail::__iterator_sentinel_pair _Pr>
-    subrange(_Pr, __detail::__make_unsigned_like_t<iter_difference_t<
-						     tuple_element_t<0, _Pr>>>)
-      -> subrange<tuple_element_t<0, _Pr>, tuple_element_t<1, _Pr>,
-		  subrange_kind::sized>;
-
-  template<borrowed_range _Rng>
-    subrange(_Rng&&)
-      -> subrange<iterator_t<_Rng>, sentinel_t<_Rng>,
-		 (sized_range<_Rng>
-		  || sized_sentinel_for<sentinel_t<_Rng>, iterator_t<_Rng>>)
-		 ? subrange_kind::sized : subrange_kind::unsized>;
-
-  template<borrowed_range _Rng>
-    subrange(_Rng&&,
-	     __detail::__make_unsigned_like_t<range_difference_t<_Rng>>)
-      -> subrange<iterator_t<_Rng>, sentinel_t<_Rng>, subrange_kind::sized>;
-
-  template<size_t _Num, class _It, class _Sent, subrange_kind _Kind>
-    requires (_Num < 2)
-    constexpr auto
-    get(const subrange<_It, _Sent, _Kind>& __r)
-    {
-      if constexpr (_Num == 0)
-	return __r.begin();
-      else
-	return __r.end();
-    }
-
-  template<size_t _Num, class _It, class _Sent, subrange_kind _Kind>
-    requires (_Num < 2)
-    constexpr auto
-    get(subrange<_It, _Sent, _Kind>&& __r)
-    {
-      if constexpr (_Num == 0)
-	return __r.begin();
-      else
-	return __r.end();
-    }
-
-  template<input_or_output_iterator _It, sentinel_for<_It> _Sent,
-	   subrange_kind _Kind>
-    inline constexpr bool
-      enable_borrowed_range<subrange<_It, _Sent, _Kind>> = true;
-
-} // namespace ranges
-
-  using ranges::get;
-
-namespace ranges
-{
-  /// Type returned by algorithms instead of a dangling iterator or subrange.
-  struct dangling
-  {
-    constexpr dangling() noexcept = default;
-    template<typename... _Args>
-      constexpr dangling(_Args&&...) noexcept { }
-  };
+  // [range.access] customization point objects
+  // [range.req] range and view concepts
+  // [range.dangling] dangling iterator handling
+  // Defined in <bits/ranges_base.h>
 
-  template<range _Range>
-    using borrowed_iterator_t = conditional_t<borrowed_range<_Range>,
-					      iterator_t<_Range>,
-					      dangling>;
+  // [view.interface] View interface
+  // [range.subrange] Sub-ranges
+  // Defined in <bits/ranges_util.h>
 
-  template<range _Range>
-    using borrowed_subrange_t = conditional_t<borrowed_range<_Range>,
-					      subrange<iterator_t<_Range>>,
-					      dangling>;
+  // C++20 24.6 [range.factories] Range factories
 
+  /// A view that contains no elements.
   template<typename _Tp> requires is_object_v<_Tp>
     class empty_view
     : public view_interface<empty_view<_Tp>>
@@ -1038,6 +647,8 @@ namespace views
     istream_view(basic_istream<_CharT, _Traits>& __s)
     { return basic_istream_view<_Val, _CharT, _Traits>{__s}; }
 
+  // C++20 24.7 [range.adaptors] Range adaptors
+
 namespace __detail
 {
   struct _Empty { };
diff --git a/libstdc++-v3/include/std/span b/libstdc++-v3/include/std/span
index 1cdc058..fb34940 100644
--- a/libstdc++-v3/include/std/span
+++ b/libstdc++-v3/include/std/span
@@ -41,7 +41,7 @@
 #include <type_traits>
 #include <array>
 #include <bits/stl_iterator.h>
-#include <bits/range_access.h>
+#include <bits/ranges_base.h>
 
 #if __cpp_lib_concepts
 namespace std _GLIBCXX_VISIBILITY(default)
diff --git a/libstdc++-v3/include/std/string_view b/libstdc++-v3/include/std/string_view
index f05ff32..32c51b2 100644
--- a/libstdc++-v3/include/std/string_view
+++ b/libstdc++-v3/include/std/string_view
@@ -41,6 +41,7 @@
 #include <bits/char_traits.h>
 #include <bits/functional_hash.h>
 #include <bits/range_access.h>
+#include <bits/ranges_base.h>
 #include <bits/ostream_insert.h>
 #include <ext/numeric_traits.h>