[gcc r17-2858] libstdc++: Introduce segmented iterator concept and traversal

https://gcc.gnu.org/g:133a57041f2d000f4089006770f10dc5c21ced04

commit r17-2858-g133a57041f2d000f4089006770f10dc5c21ced04
Author: Patrick Palka <[email protected]>
Date:   Fri Jul 31 14:54:12 2026 -0400

    libstdc++: Introduce segmented iterator concept and traversal
    
    This patch defines a new utility function std::__for_each_segment for
    iterating over "segmented" iterators, i.e. iterators for ranges composed
    of sub-ranges.  Such iterators must provide a static member function
    _S_for_each_segment implementing traversal over their segments via a
    callback function.  This patch implements such traversal for iterators
    of std::deque, ranges::join_view and ranges::concat_view.
    
            PR libstdc++/123211
    
    libstdc++-v3/ChangeLog:
    
            * include/bits/stl_deque.h (_Deque_iterator::_S_for_each_segment):
            Define.
            (_Deque_iterator::_S_enable_for_each_segment): Define.
            * include/bits/stl_iterator_base_funcs.h: Include <bits/move.h>.
            (__for_each_segment): Define.
            * include/bits/stl_iterator_base_types.h: Include
            <ext/type_traits.h> in C++98 mode.
            (__enable_for_each_segment): Define.
            (__segmented_iterator): Define in C++20.
            * include/debug/safe_iterator.h
            (_Safe_iterator::_S_for_each_segment): Define.
            (_Safe_iterator::_S_enable_for_each_segment): Define.
            * include/std/ranges (join_view::_Iterator::_Iterator): New
            constructor taking both an inner and outer iterator.
            (join_view::_Iterator::_S_for_each_segment): Define.
            (join_view::_Iterator::_S_enable_for_each_segment): Define.
            (concat_view::_Iterator::_S_for_each_segment): Define.
            (concat_view::_Iterator::_S_enable_for_each_segment): Define.
            * testsuite/23_containers/deque/for_each_segment.cc: New test.
            * testsuite/std/ranges/adaptors/join/for_each_segment.cc: New test.
            * testsuite/std/ranges/concat/for_each_segment.cc: New test.
    
    Reviewed-by: Jonathan Wakely <[email protected]>

Diff:
---
 libstdc++-v3/include/bits/stl_deque.h              |  37 ++++++++
 .../include/bits/stl_iterator_base_funcs.h         |  21 +++++
 .../include/bits/stl_iterator_base_types.h         |  24 ++++-
 libstdc++-v3/include/debug/safe_iterator.h         |  13 +++
 libstdc++-v3/include/std/ranges                    | 100 +++++++++++++++++++++
 .../23_containers/deque/for_each_segment.cc        |  74 +++++++++++++++
 .../std/ranges/adaptors/join/for_each_segment.cc   |  80 +++++++++++++++++
 .../std/ranges/concat/for_each_segment.cc          |  67 ++++++++++++++
 8 files changed, 415 insertions(+), 1 deletion(-)

diff --git a/libstdc++-v3/include/bits/stl_deque.h b/libstdc++-v3/include/bits/stl_deque.h
index 29a3f1b62896..b51342e1751d 100644
--- a/libstdc++-v3/include/bits/stl_deque.h
+++ b/libstdc++-v3/include/bits/stl_deque.h
@@ -417,6 +417,43 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
       friend _Self
       operator+(difference_type __n, const _Self& __x) _GLIBCXX_NOEXCEPT
       { return __x + __n; }
+
+      template<typename _Fn>
+	static _Self
+	_S_for_each_segment(_Self __first, _Self __last, _Fn __func)
+	{
+	  if (__first._M_node == __last._M_node)
+	    {
+	      _Elt_pointer __ret = __func(__first._M_cur, __last._M_cur);
+	      if (__ret != __last._M_cur)
+		return _Self(__ret, __first._M_node);
+	      return __last;
+	    }
+	  else
+	    {
+	      _Elt_pointer __ret = __func(__first._M_cur, __first._M_last);
+	      if (__ret != __first._M_last)
+		return _Self(__ret, __first._M_node);
+
+	      for (_Map_pointer __node = __first._M_node + 1;
+		   __node < __last._M_node;
+		   ++__node)
+		{
+		  _Elt_pointer __end = *__node + _S_buffer_size();
+		  __ret = __func(*__node, __end);
+		  if (__ret != __end)
+		    return _Self(__ret, __node);
+		}
+
+	      __ret = __func(__last._M_first, __last._M_cur);
+	      if (__ret != __last._M_cur)
+		return _Self(__ret, __last._M_node);
+
+	      return __last;
+	    }
+	}
+
+      static const bool _S_enable_for_each_segment = true;
     };
 
   /**
diff --git a/libstdc++-v3/include/bits/stl_iterator_base_funcs.h b/libstdc++-v3/include/bits/stl_iterator_base_funcs.h
index 2762090c6e48..e6c10601432b 100644
--- a/libstdc++-v3/include/bits/stl_iterator_base_funcs.h
+++ b/libstdc++-v3/include/bits/stl_iterator_base_funcs.h
@@ -66,6 +66,7 @@
 #include <bits/concept_check.h>
 #include <debug/assertions.h>
 #include <bits/stl_iterator_base_types.h>
+#include <bits/move.h> // For _GLIBCXX_MOVE
 
 namespace std _GLIBCXX_VISIBILITY(default)
 {
@@ -383,6 +384,26 @@ namespace __detail
 #define _GLIBCXX_ITER_MOVE(__it) _GLIBCXX_MOVE(*__it)
 #endif
 
+  /* Mechanism for traversing ranges that are composed of "segments" of other
+     ranges, such as std::deque and ranges::join_view.  The callback __func
+     is sequentially called on each constituent segment as a pair of inner
+     iterators.  If the callback returns something other than the past-the-end
+     inner iterator, then the rest of the traversal gets short-circuited and
+     returns the iterator at which we stopped.  */
+  template<typename _Iter, typename _Fn>
+#if __cplusplus >= 201103L
+    constexpr
+    __enable_if_t<__enable_for_each_segment<_Iter>, _Iter>
+#else
+    _Iter
+#endif
+    __for_each_segment(_Iter __first, _Iter __last, _Fn __func)
+    {
+      return _Iter::_S_for_each_segment(_GLIBCXX_MOVE(__first),
+					_GLIBCXX_MOVE(__last),
+					_GLIBCXX_MOVE(__func));
+    }
+
   /// @endcond
 
 _GLIBCXX_END_NAMESPACE_VERSION
diff --git a/libstdc++-v3/include/bits/stl_iterator_base_types.h b/libstdc++-v3/include/bits/stl_iterator_base_types.h
index 2366b5b5ce3e..f2abd28e2417 100644
--- a/libstdc++-v3/include/bits/stl_iterator_base_types.h
+++ b/libstdc++-v3/include/bits/stl_iterator_base_types.h
@@ -66,7 +66,9 @@
 #include <bits/c++config.h>
 
 #if __cplusplus >= 201103L
-# include <type_traits>  // For __void_t, is_convertible
+# include <type_traits>  // For __void_t, is_convertible, __enable_if_t
+#else
+# include <ext/type_traits.h> // For __gnu_cxx::__enable_if
 #endif
 
 #if __cplusplus > 201703L && __cpp_concepts >= 201907L
@@ -283,6 +285,26 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
     { enum { __value = __is_base_of(random_access_iterator_tag, _Cat) }; };
 #endif
 
+#pragma GCC diagnostic push
+#pragma GCC diagnostic ignored "-Wc++14-extensions" // variable templates
+  template<typename _Iter, typename = void>
+    const bool __enable_for_each_segment = false;
+
+  template<typename _Iter>
+    const bool __enable_for_each_segment<_Iter,
+#if __cplusplus >= 201103L
+      __enable_if_t<_Iter::_S_enable_for_each_segment>
+#else
+      typename __gnu_cxx::__enable_if<_Iter::_S_enable_for_each_segment, void>::__type
+#endif
+      > = true;
+#pragma GCC diagnostic pop
+
+#if __cpp_lib_concepts
+  template<typename _Iter>
+    concept __segmented_iterator = __enable_for_each_segment<_Iter>;
+#endif
+
   /// @endcond
   /// @}
 
diff --git a/libstdc++-v3/include/debug/safe_iterator.h b/libstdc++-v3/include/debug/safe_iterator.h
index ceda5575a523..8c049961cca1 100644
--- a/libstdc++-v3/include/debug/safe_iterator.h
+++ b/libstdc++-v3/include/debug/safe_iterator.h
@@ -582,6 +582,19 @@ namespace __gnu_debug
 	  return __lhs.base() != __rhs.base();
 	}
 #endif // three-way comparison
+
+      template<typename _Fn>
+	static _GLIBCXX14_CONSTEXPR _Self
+	_S_for_each_segment(_Self __first, _Self __last, _Fn __func)
+	{
+	  __glibcxx_check_valid_range(__first, __last);
+	  _Iterator __ret
+	    = _Iterator::_S_for_each_segment(__first.base(), __last.base(), __func);
+	  return _Self(__ret, __first._M_sequence);
+	}
+
+      static const bool _S_enable_for_each_segment
+	= std::__enable_for_each_segment<_Iterator>;
     };
 
   template<typename _Iterator, typename _Sequence>
diff --git a/libstdc++-v3/include/std/ranges b/libstdc++-v3/include/std/ranges
index 07e26542f9e2..a7fb2312fe88 100644
--- a/libstdc++-v3/include/std/ranges
+++ b/libstdc++-v3/include/std/ranges
@@ -3149,6 +3149,13 @@ namespace views::__adaptor
 	    : _M_outer(std::move(__outer)), _M_parent(__parent)
 	  { _M_satisfy(); }
 
+	  constexpr
+	  _Iterator(_Parent* __parent, _Outer_iter __outer, _Inner_iter __inner)
+	    requires forward_range<_Base>
+	    : _M_outer(std::move(__outer)), _M_inner(std::move(__inner)),
+	      _M_parent(__parent)
+	  { }
+
 	  constexpr explicit
 	  _Iterator(_Parent* __parent) requires (!forward_range<_Base>)
 	    : _M_parent(__parent)
@@ -3272,6 +3279,50 @@ namespace views::__adaptor
 
 	  friend _Iterator<!_Const>;
 	  template<bool> friend struct _Sentinel;
+
+	  template<typename _Fn>
+	    static constexpr _Iterator
+	    _S_for_each_segment(_Iterator __first, _Iterator __last, _Fn __func)
+	    {
+	      _Inner_iter __first_inner = __first._M_get_inner();
+	      _Outer_iter __first_outer = __first._M_get_outer();
+	      _Inner_iter __last_inner = __last._M_get_inner();
+	      _Outer_iter __last_outer = __last._M_get_outer();
+
+	      if (__first_outer == __last_outer)
+		{
+		  auto __ret = __func(__first_inner, __last_inner);
+		  return _Iterator(__first._M_parent, __first_outer, __ret);
+		}
+	      else
+		{
+		  auto __end = ranges::end(*__first_outer);
+		  auto __ret = __func(__first_inner, __end);
+		  if (__ret != __end)
+		    return _Iterator(__first._M_parent, __first_outer, __ret);
+
+		  while (++__first_outer != __last_outer)
+		    {
+		      __end = ranges::end(*__first_outer);
+		      __ret = __func(ranges::begin(*__first_outer), __end);
+		      if (__ret != __end)
+			return _Iterator(__first._M_parent, __first_outer, __ret);
+		    }
+
+		  if (__last != __last._M_parent->end())
+		    {
+		      __end = __last_inner;
+		      __ret = __func(ranges::begin(*__last_outer), __end);
+		      if (__ret != __end)
+			return _Iterator(__first._M_parent, __first_outer, __ret);
+		    }
+
+		  return __last;
+		}
+	    }
+
+	  static constexpr bool _S_enable_for_each_segment
+	    = forward_iterator<_Iterator>;
 	};
 
       template<bool _Const>
@@ -10347,6 +10398,55 @@ namespace ranges
 	  ranges::swap(*__it1, *__it2);
       }, __x._M_it, __y._M_it);
     }
+
+    template<typename _Fn>
+      static constexpr _Iterator
+      _S_for_each_segment(_Iterator __first, _Iterator __last, _Fn __func)
+      {
+	return _S_invoke_with_runtime_index([&]<size_t _Ix>() -> _Iterator {
+	  return _S_invoke_with_runtime_index([&]<size_t _Iy>() -> _Iterator {
+	    if constexpr (_Ix == _Iy)
+	      {
+		auto __ret = __func(std::get<_Ix>(__first._M_it), std::get<_Iy>(__last._M_it));
+		return _Iterator(__first._M_parent, std::in_place_index<_Ix>, __ret);
+	      }
+	    else if constexpr (_Ix < _Iy)
+	      {
+		auto __first_range = std::get<_Ix>(__first._M_parent->_M_views);
+		auto __ret = __func(std::get<_Ix>(__first._M_it),
+				    ranges::end(__first_range));
+		if (__ret != ranges::end(__first_range))
+		  return _Iterator(__first._M_parent, std::in_place_index<_Ix>, __ret);
+
+		return [&]<size_t _Idx = _Ix + 1>(this auto&& __self) -> _Iterator {
+		  if constexpr (_Idx < _Iy)
+		    {
+		      auto __mid_range = std::get<_Idx>(__first._M_parent->_M_views);
+		      auto __mid_ret = __func(ranges::begin(__mid_range),
+					      ranges::end(__mid_range));
+		      if (__mid_ret != ranges::end(__mid_range))
+			return _Iterator(__first._M_parent, std::in_place_index<_Idx>, __mid_ret);
+		      return __self.template operator()<_Idx + 1>();
+		    }
+		  else
+		    {
+		      auto __last_range = std::get<_Iy>(__last._M_parent->_M_views);
+		      auto __last_ret = __func(ranges::begin(__last_range),
+					       std::get<_Iy>(__last._M_it));
+		      return _Iterator(__first._M_parent, std::in_place_index<_Iy>, __last_ret);
+		    }
+		}();
+	      }
+	    else
+	      {
+		__builtin_unreachable();
+		__glibcxx_assert(false);
+	      }
+	  }, __last._M_it.index());
+	}, __first._M_it.index());
+      }
+
+    static constexpr bool _S_enable_for_each_segment = true;
   };
 
   namespace views
diff --git a/libstdc++-v3/testsuite/23_containers/deque/for_each_segment.cc b/libstdc++-v3/testsuite/23_containers/deque/for_each_segment.cc
new file mode 100644
index 000000000000..d6127b0f0e2c
--- /dev/null
+++ b/libstdc++-v3/testsuite/23_containers/deque/for_each_segment.cc
@@ -0,0 +1,74 @@
+// { dg-do run }
+
+#include <deque>
+#include <algorithm>
+#include <testsuite_hooks.h>
+
+struct Finder
+{
+  static int call_count;
+
+  int target;
+
+  explicit Finder(int t) : target(t) { }
+
+  int*
+  operator()(int* first, int* last) const
+  {
+    ++call_count;
+    return std::find(first, last, target);
+  }
+};
+
+int Finder::call_count = 0;
+
+void
+test01()
+{
+  // A deque of 500 ints spans ~4 internal nodes (128 elements per node)
+  // Node 0: elements   0 - 127
+  // Node 1: elements 128 - 255
+  // Node 2: elements 256 - 383
+  // Node 3: elements 384 - 499
+  std::deque<int> d;
+  for (int i = 0; i < 500; ++i)
+    d.push_back(i);
+
+  std::deque<int>::iterator it;
+
+  Finder::call_count = 0;
+  it = std::__for_each_segment(d.begin(), d.begin() + 100, Finder(50));
+  VERIFY( it == d.begin() + 50 );
+  VERIFY( Finder::call_count == 1 );
+
+  Finder::call_count = 0;
+  it = std::__for_each_segment(d.begin(), d.begin() + 100, Finder(999));
+  VERIFY( it == d.begin() + 100 );
+  VERIFY( Finder::call_count == 1 );
+
+  Finder::call_count = 0;
+  it = std::__for_each_segment(d.begin(), d.end(), Finder(100));
+  VERIFY( it == d.begin() + 100 );
+  VERIFY( Finder::call_count == 1 );
+
+  Finder::call_count = 0;
+  it = std::__for_each_segment(d.begin(), d.end(), Finder(200));
+  VERIFY( it == d.begin() + 200 );
+  VERIFY( Finder::call_count == 2 );
+
+  Finder::call_count = 0;
+  it = std::__for_each_segment(d.begin(), d.end(), Finder(450));
+  VERIFY( it == d.begin() + 450 );
+  VERIFY( Finder::call_count == 4 );
+
+  Finder::call_count = 0;
+  it = std::__for_each_segment(d.begin(), d.end(), Finder(999));
+  VERIFY( it == d.end() );
+  VERIFY( Finder::call_count == 4 );
+}
+
+int
+main()
+{
+  test01();
+}
diff --git a/libstdc++-v3/testsuite/std/ranges/adaptors/join/for_each_segment.cc b/libstdc++-v3/testsuite/std/ranges/adaptors/join/for_each_segment.cc
new file mode 100644
index 000000000000..aad00606c97f
--- /dev/null
+++ b/libstdc++-v3/testsuite/std/ranges/adaptors/join/for_each_segment.cc
@@ -0,0 +1,80 @@
+// { dg-do run { target c++20 } }
+
+#include <ranges>
+#include <vector>
+#include <algorithm>
+#include <testsuite_hooks.h>
+
+namespace ranges = std::ranges;
+
+void
+test01()
+{
+  // 4 discrete vectors serving as segments
+  std::vector<std::vector<int>> vec
+    = { {0, 1, 2},   // Segment 0
+	{3, 4, 5},   // Segment 1
+	{6, 7, 8},   // Segment 2
+	{9, 10, 11}  // Segment 3
+      };
+
+  auto jv = vec | std::views::join;
+  std::__segmented_iterator auto begin = jv.begin();
+  std::__segmented_iterator auto end = jv.end();
+
+  static int call_count = 0;
+  auto make_finder = [](int target) {
+    return [target](auto first, auto last) {
+      if (first != last)
+	++call_count;
+      return std::find(first, last, target);
+    };
+  };
+
+  call_count = 0;
+  auto it = std::__for_each_segment(ranges::next(begin, 3), ranges::next(begin, 6),
+				    make_finder(4));
+  VERIFY( it == ranges::next(begin, 4) );
+  VERIFY( call_count == 1 );
+
+  call_count = 0;
+  it = std::__for_each_segment(ranges::next(begin, 3), ranges::next(begin, 6),
+			       make_finder(99));
+  VERIFY( it == ranges::next(begin, 6) );
+  VERIFY( call_count == 1 );
+
+  call_count = 0;
+  it = std::__for_each_segment(ranges::next(begin, 1), ranges::next(begin, 11),
+			       make_finder(2));
+  VERIFY( it == ranges::next(begin, 2) );
+  VERIFY( call_count == 1 );
+
+  call_count = 0;
+  it = std::__for_each_segment(ranges::next(begin, 1), ranges::next(begin, 11),
+			       make_finder(7));
+  VERIFY( it == ranges::next(begin, 7) );
+  VERIFY( call_count == 3 );
+
+  call_count = 0;
+  it = std::__for_each_segment(ranges::next(begin, 1), ranges::next(begin, 11),
+			       make_finder(9));
+  VERIFY( it == ranges::next(begin, 9) );
+  VERIFY( call_count == 4 );
+
+  call_count = 0;
+  it = std::__for_each_segment(ranges::next(begin, 1), ranges::next(begin, 11),
+			       make_finder(99));
+  VERIFY( it == ranges::next(begin, 11) );
+  VERIFY( call_count == 4 );
+
+  call_count = 0;
+  it = std::__for_each_segment(ranges::next(begin, 1), end, make_finder(99));
+  VERIFY( it == end );
+  VERIFY( call_count == 4 );
+}
+
+int
+main()
+{
+  test01();
+}
diff --git a/libstdc++-v3/testsuite/std/ranges/concat/for_each_segment.cc b/libstdc++-v3/testsuite/std/ranges/concat/for_each_segment.cc
new file mode 100644
index 000000000000..a74372b50456
--- /dev/null
+++ b/libstdc++-v3/testsuite/std/ranges/concat/for_each_segment.cc
@@ -0,0 +1,67 @@
+// { dg-do run { target c++26 } }
+
+#include <ranges>
+#include <vector>
+#include <algorithm>
+#include <testsuite_hooks.h>
+
+namespace ranges = std::ranges;
+
+void
+test01()
+{
+  // 4 discrete vectors serving as segments
+  std::vector<int> v0 = {0, 1, 2};    // Segment 0
+  std::vector<int> v1 = {3, 4, 5};    // Segment 1
+  std::vector<int> v2 = {6, 7, 8};    // Segment 2
+  std::vector<int> v3 = {9, 10, 11};  // Segment 3
+
+  auto cv = std::views::concat(v0, v1, v2, v3);
+  std::__segmented_iterator auto begin = cv.begin();
+  std::__segmented_iterator auto end = cv.end();
+
+  static int call_count = 0;
+  auto make_finder = [](int target) {
+    return [target](auto first, auto last) {
+      if (first != last)
+	++call_count;
+      return std::find(first, last, target);
+    };
+  };
+
+  call_count = 0;
+  auto it = std::__for_each_segment(begin + 3, begin + 6, make_finder(4));
+  VERIFY( it == begin + 4 );
+  VERIFY( call_count == 1 );
+
+  call_count = 0;
+  it = std::__for_each_segment(begin + 3, begin + 6, make_finder(99));
+  VERIFY( it == begin + 6 );
+  VERIFY( call_count == 1 );
+
+  call_count = 0;
+  it = std::__for_each_segment(begin + 1, begin + 11, make_finder(2));
+  VERIFY( it == begin + 2 );
+  VERIFY( call_count == 1 );
+
+  call_count = 0;
+  it = std::__for_each_segment(begin + 1, begin + 11, make_finder(7));
+  VERIFY( it == begin + 7 );
+  VERIFY( call_count == 3 );
+
+  call_count = 0;
+  it = std::__for_each_segment(begin + 1, begin + 11, make_finder(9));
+  VERIFY( it == begin + 9 );
+  VERIFY( call_count == 4 );
+
+  call_count = 0;
+  it = std::__for_each_segment(begin + 1, end, make_finder(99));
+  VERIFY( it == end );
+  VERIFY( call_count == 4 );
+}
+
+int
+main()
+{
+  test01();
+}