libstdc++: Add move_sentinel, common_iterator and counted_iterator

This implements most of the remaining C++20 additions to the <iterator>
header.

	* include/bits/iterator_concepts.h (ranges::iter_swap): Fix parameter
	types of poison pill overload. Use remove_reference_t when checking
	constraints.
	* include/bits/stl_iterator.h (move_sentinel): Define for C++20.
	(move_iterator): Adjust definitions of nested types for C++20. Add
	hidden friends for move_sentinel operations, iter_move and iter_swap.
	(common_iterator, counted_iterator): Define for C++20.
	* testsuite/24_iterators/move_iterator/cust.cc: New test.
	* testsuite/24_iterators/move_iterator/sentinel.cc: New test.
	* testsuite/24_iterators/common_iterator/1.cc: New test.
	* testsuite/24_iterators/counted_iterator/1.cc: New test.

git-svn-id: https://gcc.gnu.org/svn/gcc/trunk@278698 138bc75d-0d04-0410-961f-82ee72b054a4

7 files changed, 1105 insertions, 9 deletions

diff --git a/libstdc++-v3/ChangeLog b/libstdc++-v3/ChangeLog
index 09202af787f..4ea06a37a1f 100644
--- a/libstdc++-v3/ChangeLog
+++ b/libstdc++-v3/ChangeLog
@@ -1,5 +1,17 @@
 2019-11-25  Jonathan Wakely  <jwakely@redhat.com>
 
+	* include/bits/iterator_concepts.h (ranges::iter_swap): Fix parameter
+	types of poison pill overload. Use remove_reference_t when checking
+	constraints.
+	* include/bits/stl_iterator.h (move_sentinel): Define for C++20.
+	(move_iterator): Adjust definitions of nested types for C++20. Add
+	hidden friends for move_sentinel operations, iter_move and iter_swap.
+	(common_iterator, counted_iterator): Define for C++20.
+	* testsuite/24_iterators/move_iterator/cust.cc: New test.
+	* testsuite/24_iterators/move_iterator/sentinel.cc: New test.
+	* testsuite/24_iterators/common_iterator/1.cc: New test.
+	* testsuite/24_iterators/counted_iterator/1.cc: New test.
+
 	PR libstdc++/91786
 	* include/bits/fs_path.h (filesystem_error): Move definition before
 	the use in u8path.
diff --git a/libstdc++-v3/include/bits/iterator_concepts.h b/libstdc++-v3/include/bits/iterator_concepts.h
index 3843ba5d57f..97aed72e255 100644
--- a/libstdc++-v3/include/bits/iterator_concepts.h
+++ b/libstdc++-v3/include/bits/iterator_concepts.h
@@ -700,7 +700,7 @@ namespace ranges
   namespace __cust_iswap
   {
     template<typename _It1, typename _It2>
-      void iter_swap(_It1&, _It2&) = delete;
+      void iter_swap(_It1, _It2) = delete;
 
     template<typename _Tp, typename _Up>
       concept __adl_iswap
@@ -744,7 +744,8 @@ namespace ranges
     public:
       template<typename _Tp, typename _Up>
 	requires __adl_iswap<_Tp, _Up>
-	|| (readable<_Tp> && readable<_Up>
+	|| (readable<remove_reference_t<_Tp>>
+	    && readable<remove_reference_t<_Up>>
 	    && swappable_with<iter_reference_t<_Tp>, iter_reference_t<_Up>>)
 	|| (indirectly_movable_storable<_Tp, _Up>
 	    && indirectly_movable_storable<_Up, _Tp>)
diff --git a/libstdc++-v3/include/bits/stl_iterator.h b/libstdc++-v3/include/bits/stl_iterator.h
index a707621c9ed..89cca64438c 100644
--- a/libstdc++-v3/include/bits/stl_iterator.h
+++ b/libstdc++-v3/include/bits/stl_iterator.h
@@ -73,6 +73,11 @@
 # define __cpp_lib_array_constexpr 201803
 #endif
 
+#if __cplusplus > 201703L
+# include <compare>
+# include <new>
+#endif
+
 namespace std _GLIBCXX_VISIBILITY(default)
 {
 _GLIBCXX_BEGIN_NAMESPACE_VERSION
@@ -1055,12 +1060,61 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
     { return __it.base(); }
 
 #if __cplusplus >= 201103L
-
   /**
    * @addtogroup iterators
    * @{
    */
 
+#if __cplusplus > 201703L && __cpp_lib_concepts
+  template<semiregular _Sent>
+    class move_sentinel
+    {
+    public:
+      constexpr
+      move_sentinel()
+      noexcept(is_nothrow_default_constructible_v<_Sent>)
+      : _M_last() { }
+
+      constexpr explicit
+      move_sentinel(_Sent __s)
+      noexcept(is_nothrow_move_constructible_v<_Sent>)
+      : _M_last(std::move(__s)) { }
+
+      template<typename _S2> requires convertible_to<const _S2&, _Sent>
+	constexpr
+	move_sentinel(const move_sentinel<_S2>& __s)
+	noexcept(is_nothrow_constructible_v<_Sent, const _S2&>)
+	: _M_last(__s.base())
+	{ }
+
+      template<typename _S2> requires assignable_from<_Sent&, const _S2&>
+	constexpr move_sentinel&
+	operator=(const move_sentinel<_S2>& __s)
+	noexcept(is_nothrow_assignable_v<_Sent, const _S2&>)
+	{
+	  _M_last = __s.base();
+	  return *this;
+	}
+
+      constexpr _Sent
+      base() const
+      noexcept(is_nothrow_copy_constructible_v<_Sent>)
+      { return _M_last; }
+
+    private:
+      _Sent _M_last;
+    };
+
+  namespace __detail
+  {
+    // Weaken iterator_category _Cat to _Limit if it is derived from that,
+    // otherwise use _Otherwise.
+    template<typename _Cat, typename _Limit, typename _Otherwise = _Cat>
+      using __clamp_iter_cat
+	= conditional_t<derived_from<_Cat, _Limit>, _Limit, _Otherwise>;
+  }
+#endif // C++20
+
   // 24.4.3  Move iterators
   /**
    *  Class template move_iterator is an iterator adapter with the same
@@ -1073,14 +1127,27 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
   template<typename _Iterator>
     class move_iterator
     {
-    protected:
       _Iterator _M_current;
 
-      typedef iterator_traits<_Iterator>		__traits_type;
-      typedef typename __traits_type::reference		__base_ref;
+      using __traits_type = iterator_traits<_Iterator>;
+#if __cplusplus > 201703L && __cpp_lib_concepts
+      using __base_cat = typename __traits_type::iterator_category;
+#else
+      using __base_ref = typename __traits_type::reference;
+#endif
 
     public:
-      typedef _Iterator					iterator_type;
+      using iterator_type = _Iterator;
+
+#if __cplusplus > 201703L && __cpp_lib_concepts
+      using iterator_concept = input_iterator_tag;
+      using iterator_category
+	= __detail::__clamp_iter_cat<__base_cat, random_access_iterator_tag>;
+      using value_type = iter_value_t<_Iterator>;
+      using difference_type = iter_difference_t<_Iterator>;
+      using pointer = _Iterator;
+      using reference = iter_rvalue_reference_t<_Iterator>;
+#else
       typedef typename __traits_type::iterator_category iterator_category;
       typedef typename __traits_type::value_type  	value_type;
       typedef typename __traits_type::difference_type	difference_type;
@@ -1091,6 +1158,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
       typedef typename conditional<is_reference<__base_ref>::value,
 			 typename remove_reference<__base_ref>::type&&,
 			 __base_ref>::type		reference;
+#endif
 
       _GLIBCXX17_CONSTEXPR
       move_iterator()
@@ -1172,6 +1240,34 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
       _GLIBCXX17_CONSTEXPR reference
       operator[](difference_type __n) const
       { return std::move(_M_current[__n]); }
+
+#if __cplusplus > 201703L && __cpp_lib_concepts
+      template<sentinel_for<_Iterator> _Sent>
+	friend constexpr bool
+	operator==(const move_iterator& __x, const move_sentinel<_Sent>& __y)
+	{ return __x.base() == __y.base(); }
+
+      template<sized_sentinel_for<_Iterator> _Sent>
+	friend constexpr iter_difference_t<_Iterator>
+	operator-(const move_sentinel<_Sent>& __x, const move_iterator& __y)
+	{ return __x.base() - __y.base(); }
+
+      template<sized_sentinel_for<_Iterator> _Sent>
+	friend constexpr iter_difference_t<_Iterator>
+	operator-(const move_iterator& __x, const move_sentinel<_Sent>& __y)
+	{ return __x.base() - __y.base(); }
+
+      friend constexpr iter_rvalue_reference_t<_Iterator>
+      iter_move(const move_iterator& __i)
+      noexcept(noexcept(ranges::iter_move(__i._M_current)))
+      { return ranges::iter_move(__i._M_current); }
+
+      template<indirectly_swappable<_Iterator> _Iter2>
+	friend constexpr void
+	iter_swap(const move_iterator& __x, const move_iterator<_Iter2>& __y)
+	noexcept(noexcept(ranges::iter_swap(__x._M_current, __y._M_current)))
+	{ return ranges::iter_swap(__x._M_current, __y._M_current); }
+#endif // C++20
     };
 
   // Note: See __normal_iterator operators note from Gaby to understand
@@ -1285,6 +1381,592 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
     __make_move_if_noexcept_iterator(_Tp* __i)
     { return _ReturnType(__i); }
 
+#if __cplusplus > 201703L && __cpp_lib_concepts
+  // [iterators.common] Common iterators
+
+  namespace __detail
+  {
+    template<input_or_output_iterator _It>
+      class _Common_iter_proxy
+      {
+	iter_value_t<_It> _M_keep;
+
+	_Common_iter_proxy(iter_reference_t<_It>&& __x)
+	: _M_keep(std::move(__x)) { }
+
+	template<typename _Iter, typename _Sent>
+	  friend class common_iterator;
+
+      public:
+	const iter_value_t<_It>*
+	operator->() const
+	{ return std::__addressof(_M_keep); }
+      };
+
+    template<typename _It>
+      concept __common_iter_has_arrow = readable<const _It>
+	&& (requires(const _It& __it) { __it.operator->(); }
+	    || is_reference_v<iter_reference_t<_It>>
+	    || constructible_from<iter_value_t<_It>, iter_reference_t<_It>>);
+
+  } // namespace __detail
+
+  /// An iterator/sentinel adaptor for representing a non-common range.
+  template<input_or_output_iterator _It, sentinel_for<_It> _Sent>
+    requires (!same_as<_It, _Sent>)
+  class common_iterator
+  {
+    template<typename _Tp, typename _Up>
+      static constexpr bool
+      _S_noexcept1()
+      {
+	if constexpr (is_trivially_default_constructible_v<_Tp>)
+	  return is_nothrow_assignable_v<_Tp, _Up>;
+	else
+	  return is_nothrow_constructible_v<_Tp, _Up>;
+      }
+
+    template<typename _It2, typename _Sent2>
+      static constexpr bool
+      _S_noexcept()
+      { return _S_noexcept1<_It, _It2>() && _S_noexcept1<_Sent, _Sent2>(); }
+
+  public:
+    constexpr
+    common_iterator()
+    noexcept(is_nothrow_default_constructible_v<_It>)
+    : _M_it(), _M_index(0)
+    { }
+
+    constexpr
+    common_iterator(_It __i)
+    noexcept(is_nothrow_move_constructible_v<_It>)
+    : _M_it(std::move(__i)), _M_index(0)
+    { }
+
+    constexpr
+    common_iterator(_Sent __s)
+    noexcept(is_nothrow_move_constructible_v<_Sent>)
+    : _M_sent(std::move(__s)), _M_index(1)
+    { }
+
+    template<typename _It2, typename _Sent2>
+      requires convertible_to<const _It2&, _It>
+	&& convertible_to<const _Sent2&, _Sent>
+      constexpr
+      common_iterator(const common_iterator<_It2, _Sent2>& __x)
+      noexcept(_S_noexcept<const _It2&, const _Sent2&>())
+      : _M_valueless(), _M_index(__x._M_index)
+      {
+	if (_M_index == 0)
+	  {
+	    if constexpr (is_trivially_default_constructible_v<_It>)
+	      _M_it = std::move(__x._M_it);
+	    else
+	      ::new((void*)std::__addressof(_M_it)) _It(__x._M_it);
+	  }
+	else if (_M_index == 1)
+	  {
+	    if constexpr (is_trivially_default_constructible_v<_Sent>)
+	      _M_sent = std::move(__x._M_sent);
+	    else
+	      ::new((void*)std::__addressof(_M_sent)) _Sent(__x._M_sent);
+	  }
+      }
+
+    constexpr
+    common_iterator(const common_iterator& __x)
+    noexcept(_S_noexcept<const _It&, const _Sent&>())
+    : _M_valueless(), _M_index(__x._M_index)
+    {
+      if (_M_index == 0)
+	{
+	  if constexpr (is_trivially_default_constructible_v<_It>)
+	    _M_it = std::move(__x._M_it);
+	  else
+	    ::new((void*)std::__addressof(_M_it)) _It(__x._M_it);
+	}
+      else if (_M_index == 1)
+	{
+	  if constexpr (is_trivially_default_constructible_v<_Sent>)
+	    _M_sent = std::move(__x._M_sent);
+	  else
+	    ::new((void*)std::__addressof(_M_sent)) _Sent(__x._M_sent);
+	}
+    }
+
+    common_iterator&
+    operator=(const common_iterator& __x)
+    noexcept(is_nothrow_copy_assignable_v<_It>
+	     && is_nothrow_copy_assignable_v<_Sent>
+	     && is_nothrow_copy_constructible_v<_It>
+	     && is_nothrow_copy_constructible_v<_Sent>)
+    {
+      return this->operator=<_It, _Sent>(__x);
+    }
+
+    template<typename _It2, typename _Sent2>
+      requires convertible_to<const _It2&, _It>
+	&& convertible_to<const _Sent2&, _Sent>
+	&& assignable_from<_It&, const _It2&>
+	&& assignable_from<_Sent&, const _Sent2&>
+      common_iterator&
+      operator=(const common_iterator<_It2, _Sent2>& __x)
+      noexcept(is_nothrow_constructible_v<_It, const _It2&>
+	       && is_nothrow_constructible_v<_Sent, const _Sent2&>
+	       && is_nothrow_assignable_v<_It, const _It2&>
+	       && is_nothrow_assignable_v<_Sent, const _Sent2&>)
+      {
+	switch(_M_index << 2 | __x._M_index)
+	  {
+	  case 0b0000:
+	    _M_it = __x._M_it;
+	    break;
+	  case 0b0101:
+	    _M_sent = __x._M_sent;
+	    break;
+	  case 0b0001:
+	    _M_it.~_It();
+	    _M_index = -1;
+	    [[fallthrough]];
+	  case 0b1001:
+	    ::new((void*)std::__addressof(_M_sent)) _Sent(__x._M_sent);
+	    _M_index = 1;
+	    break;
+	  case 0b0100:
+	    _M_sent.~_Sent();
+	    _M_index = -1;
+	    [[fallthrough]];
+	  case 0b1000:
+	    ::new((void*)std::__addressof(_M_it)) _It(__x._M_it);
+	    _M_index = 0;
+	    break;
+	  default:
+	    __glibcxx_assert(__x._M_has_value());
+	    __builtin_unreachable();
+	  }
+	return *this;
+      }
+
+    ~common_iterator()
+    {
+      switch (_M_index)
+	{
+	case 0:
+	  _M_it.~_It();
+	  break;
+	case 1:
+	  _M_sent.~_Sent();
+	  break;
+	}
+    }
+
+    decltype(auto)
+    operator*()
+    {
+      __glibcxx_assert(_M_index == 0);
+      return *_M_it;
+    }
+
+    decltype(auto)
+    operator*() const requires __detail::__dereferenceable<const _It>
+    {
+      __glibcxx_assert(_M_index == 0);
+      return *_M_it;
+    }
+
+    decltype(auto)
+    operator->() const requires __detail::__common_iter_has_arrow<_It>
+    {
+      __glibcxx_assert(_M_index == 0);
+      if constexpr (is_pointer_v<_It> || requires { _M_it.operator->(); })
+	return _M_it;
+      else if constexpr (is_reference_v<iter_reference_t<_It>>)
+	{
+	  auto&& __tmp = *_M_it;
+	  return std::__addressof(__tmp);
+	}
+      else
+	return _Common_iter_proxy(*_M_it);
+    }
+
+    common_iterator&
+    operator++()
+    {
+      __glibcxx_assert(_M_index == 0);
+      ++_M_it;
+      return *this;
+    }
+
+    decltype(auto)
+    operator++(int)
+    {
+      __glibcxx_assert(_M_index == 0);
+      if constexpr (forward_iterator<_It>)
+	{
+	  common_iterator __tmp = *this;
+	  ++*this;
+	  return __tmp;
+	}
+      else
+	return _M_it++;
+    }
+
+    template<typename _It2, sentinel_for<_It> _Sent2>
+      requires sentinel_for<_Sent, _It2>
+      friend bool
+      operator==(const common_iterator& __x,
+		 const common_iterator<_It2, _Sent2>& __y)
+      {
+	switch(__x._M_index << 2 | __y._M_index)
+	  {
+	  case 0b0000:
+	  case 0b0101:
+	    return true;
+	  case 0b0001:
+	    return __x._M_it == __y._M_sent;
+	  case 0b0100:
+	    return __x._M_sent == __y._M_it;
+	  default:
+	    __glibcxx_assert(__x._M_has_value());
+	    __glibcxx_assert(__y._M_has_value());
+	    __builtin_unreachable();
+	  }
+      }
+
+    template<typename _It2, sentinel_for<_It> _Sent2>
+      requires sentinel_for<_Sent, _It2> && equality_comparable_with<_It, _It2>
+      friend bool
+      operator==(const common_iterator& __x,
+		 const common_iterator<_It2, _Sent2>& __y)
+      {
+	switch(__x._M_index << 2 | __y._M_index)
+	  {
+	  case 0b0101:
+	    return true;
+	  case 0b0000:
+	    return __x._M_it == __y._M_it;
+	  case 0b0001:
+	    return __x._M_it == __y._M_sent;
+	  case 0b0100:
+	    return __x._M_sent == __y._M_it;
+	  default:
+	    __glibcxx_assert(__x._M_has_value());
+	    __glibcxx_assert(__y._M_has_value());
+	    __builtin_unreachable();
+	  }
+      }
+
+    template<sized_sentinel_for<_It> _It2, sized_sentinel_for<_It> _Sent2>
+      requires sized_sentinel_for<_Sent, _It2>
+      friend iter_difference_t<_It2>
+      operator-(const common_iterator& __x,
+		const common_iterator<_It2, _Sent2>& __y)
+      {
+	switch(__x._M_index << 2 | __y._M_index)
+	  {
+	  case 0b0101:
+	    return 0;
+	  case 0b0000:
+	    return __x._M_it - __y._M_it;
+	  case 0b0001:
+	    return __x._M_it - __y._M_sent;
+	  case 0b0100:
+	    return __x._M_sent - __y._M_it;
+	  default:
+	    __glibcxx_assert(__x._M_has_value());
+	    __glibcxx_assert(__y._M_has_value());
+	    __builtin_unreachable();
+	  }
+      }
+
+    friend iter_rvalue_reference_t<_It>
+    iter_move(const common_iterator& __i)
+    noexcept(noexcept(ranges::iter_move(std::declval<const _It&>())))
+    requires input_iterator<_It>
+    {
+      __glibcxx_assert(__i._M_index == 0);
+      return ranges::iter_move(__i._M_it);
+    }
+
+    template<indirectly_swappable<_It> _It2, typename _Sent2>
+      friend void
+      iter_swap(const common_iterator& __x,
+		const common_iterator<_It2, _Sent2>& __y)
+      noexcept(noexcept(ranges::iter_swap(std::declval<const _It&>(),
+					  std::declval<const _It2&>())))
+      {
+	__glibcxx_assert(__x._M_index == 0);
+	__glibcxx_assert(__y._M_index == 0);
+	return ranges::iter_swap(__x._M_it, __y._M_it);
+      }
+
+  private:
+    template<input_or_output_iterator _It2, sentinel_for<_It2> _Sent2>
+      friend class common_iterator;
+
+    bool _M_has_value() const noexcept { return _M_index < 2; }
+
+    union
+    {
+      _It _M_it;
+      _Sent _M_sent;
+      unsigned char _M_valueless;
+    };
+    unsigned char _M_index; // 0==_M_it, 1==_M_sent, 2==valueless
+  };
+
+  template<typename _It, typename _Sent>
+    struct incrementable_traits<common_iterator<_It, _Sent>>
+    {
+      using difference_type = iter_difference_t<_It>;
+    };
+
+  namespace __detail
+  {
+    // FIXME: This has to be at namespace-scope because of PR 92078.
+    template<typename _Iter>
+      struct __common_iter_ptr
+	{
+	  using type = void;
+	};
+
+    template<typename _Iter>
+      requires __detail::__common_iter_has_arrow<_Iter>
+      struct __common_iter_ptr<_Iter>
+      {
+	using type = decltype(std::declval<const _Iter&>().operator->());
+      };
+  } // namespace __detail
+
+  template<input_iterator _It, typename _Sent>
+    struct iterator_traits<common_iterator<_It, _Sent>>
+    {
+      using iterator_concept = conditional_t<forward_iterator<_It>,
+	    forward_iterator_tag, input_iterator_tag>;
+      using iterator_category = __detail::__clamp_iter_cat<
+	typename iterator_traits<_It>::iterator_category,
+	forward_iterator_tag, input_iterator_tag>;
+      using value_type = iter_value_t<_It>;
+      using difference_type = iter_difference_t<_It>;
+      using pointer = typename
+	__detail::__common_iter_ptr<common_iterator<_It, _Sent>>::type;
+      using reference = iter_reference_t<_It>;
+    };
+
+  // [iterators.counted] Counted iterators
+
+  /// An iterator adaptor that keeps track of the distance to the end.
+  template<input_or_output_iterator _It>
+    class counted_iterator
+    {
+    public:
+      using iterator_type = _It;
+
+      constexpr counted_iterator() = default;
+
+      constexpr
+      counted_iterator(_It __i, iter_difference_t<_It> __n)
+      : _M_current(__i), _M_length(__n)
+      { __glibcxx_assert(__n >= 0); }
+
+      template<typename _It2>
+	requires convertible_to<const _It2&, _It>
+	constexpr
+	counted_iterator(const counted_iterator<_It2>& __x)
+	: _M_current(__x._M_current), _M_length(__x._M_length)
+	{ }
+
+      template<typename _It2>
+	requires assignable_from<_It&, const _It2&>
+	constexpr counted_iterator&
+	operator=(const counted_iterator<_It2>& __x)
+	{
+	  _M_current = __x._M_current;
+	  _M_length = __x._M_length;
+	  return *this;
+	}
+
+      constexpr _It
+      base() const &
+      noexcept(is_nothrow_copy_constructible_v<_It>)
+      requires copy_constructible<_It>
+      { return _M_current; }
+
+      constexpr _It
+      base() &&
+      noexcept(is_nothrow_move_constructible_v<_It>)
+      { return std::move(_M_current); }
+
+      constexpr iter_difference_t<_It>
+      count() const noexcept { return _M_length; }
+
+      constexpr decltype(auto)
+      operator*()
+      noexcept(noexcept(*_M_current))
+      { return *_M_current; }
+
+      constexpr decltype(auto)
+      operator*() const
+      noexcept(noexcept(*_M_current))
+      requires __detail::__dereferenceable<const _It>
+      { return *_M_current; }
+
+      constexpr counted_iterator&
+      operator++()
+      {
+	__glibcxx_assert(_M_length > 0);
+	++_M_current;
+	--_M_length;
+	return *this;
+      }
+
+      decltype(auto)
+      operator++(int)
+      {
+	__glibcxx_assert(_M_length > 0);
+	--_M_length;
+	__try
+	  {
+	    return _M_current++;
+	  } __catch(...) {
+	    ++_M_length;
+	    throw;
+	  }
+
+      }
+
+      constexpr counted_iterator
+      operator++(int) requires forward_iterator<_It>
+      {
+	auto __tmp = *this;
+	++*this;
+	return __tmp;
+      }
+
+      constexpr counted_iterator&
+      operator--() requires bidirectional_iterator<_It>
+      {
+	--_M_current;
+	++_M_length;
+	return *this;
+      }
+
+      constexpr counted_iterator
+      operator--(int) requires bidirectional_iterator<_It>
+      {
+	auto __tmp = *this;
+	--*this;
+	return __tmp;
+      }
+
+      constexpr counted_iterator
+      operator+(iter_difference_t<_It> __n) const
+	requires random_access_iterator<_It>
+      { return counted_iterator(_M_current + __n, _M_length - __n); }
+
+      friend constexpr counted_iterator
+      operator+(iter_difference_t<_It> __n, const counted_iterator& __x)
+      requires random_access_iterator<_It>
+      { return __x + __n; }
+
+      constexpr counted_iterator&
+      operator+=(iter_difference_t<_It> __n)
+      requires random_access_iterator<_It>
+      {
+	__glibcxx_assert(__n <= _M_length);
+	_M_current += __n;
+	_M_length -= __n;
+	return *this;
+      }
+
+      constexpr counted_iterator
+      operator-(iter_difference_t<_It> __n) const
+      requires random_access_iterator<_It>
+      { return counted_iterator(_M_current - __n, _M_length + __n); }
+
+      template<common_with<_It> _It2>
+	friend constexpr iter_difference_t<_It2>
+	operator-(const counted_iterator& __x,
+		  const counted_iterator<_It2>& __y)
+	{ return __y._M_length - __x._M_length; }
+
+      friend constexpr iter_difference_t<_It>
+      operator-(const counted_iterator& __x, default_sentinel_t)
+      { return -__x._M_length; }
+
+      friend constexpr iter_difference_t<_It>
+      operator-(default_sentinel_t, const counted_iterator& __y)
+      { return __y._M_length; }
+
+      constexpr counted_iterator&
+      operator-=(iter_difference_t<_It> __n)
+      requires random_access_iterator<_It>
+      {
+	__glibcxx_assert(-__n <= _M_length);
+	_M_current -= __n;
+	_M_length += __n;
+	return *this;
+      }
+
+      constexpr decltype(auto)
+      operator[](iter_difference_t<_It> __n) const
+      noexcept(noexcept(_M_current[__n]))
+      requires random_access_iterator<_It>
+      {
+	__glibcxx_assert(__n < _M_length);
+	return _M_current[__n];
+      }
+
+      template<common_with<_It> _It2>
+	friend constexpr bool
+	operator==(const counted_iterator& __x,
+		   const counted_iterator<_It2>& __y)
+	{ return __x._M_length == __y._M_length; }
+
+      friend constexpr bool
+      operator==(const counted_iterator& __x, default_sentinel_t)
+      { return __x._M_length == 0; }
+
+      template<common_with<_It> _It2>
+	friend constexpr strong_ordering
+	operator<=>(const counted_iterator& __x,
+		    const counted_iterator<_It2>& __y)
+	{ return __y._M_length <=> __x._M_length; }
+
+      friend constexpr iter_rvalue_reference_t<_It>
+      iter_move(const counted_iterator& __i)
+      noexcept(noexcept(ranges::iter_move(__i._M_current)))
+      requires input_iterator<_It>
+      { return ranges::iter_move(__i._M_current); }
+
+      template<indirectly_swappable<_It> _It2>
+	friend constexpr void
+	iter_swap(const counted_iterator& __x,
+		  const counted_iterator<_It2>& __y)
+	noexcept(noexcept(ranges::iter_swap(__x._M_current, __y._M_current)))
+	{ ranges::iter_swap(__x._M_current, __y._M_current); }
+
+    private:
+      template<input_or_output_iterator _It2> friend class counted_iterator;
+
+      _It _M_current = _It();
+      iter_difference_t<_It> _M_length = 0;
+    };
+
+  template<typename _It>
+    struct incrementable_traits<counted_iterator<_It>>
+    {
+      using difference_type = iter_difference_t<_It>;
+    };
+
+  template<input_iterator _It>
+    struct iterator_traits<counted_iterator<_It>> : iterator_traits<_It>
+    {
+      using pointer = void;
+    };
+#endif // C++20
+
   // @} group iterators
 
   template<typename _Iterator>
@@ -1332,8 +2014,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
     using __iter_to_alloc_t =
     pair<add_const_t<__iter_key_t<_InputIterator>>,
 	 __iter_val_t<_InputIterator>>;
-
-#endif
+#endif // __cpp_deduction_guides
 
 _GLIBCXX_END_NAMESPACE_VERSION
 } // namespace
diff --git a/libstdc++-v3/testsuite/24_iterators/common_iterator/1.cc b/libstdc++-v3/testsuite/24_iterators/common_iterator/1.cc
new file mode 100644
index 00000000000..275ef53fe6a
--- /dev/null
+++ b/libstdc++-v3/testsuite/24_iterators/common_iterator/1.cc
@@ -0,0 +1,160 @@
+// Copyright (C) 2019 Free Software Foundation, Inc.
+//
+// This file is part of the GNU ISO C++ Library.  This library is free
+// software; you can redistribute it and/or modify it under the
+// terms of the GNU General Public License as published by the
+// Free Software Foundation; either version 3, or (at your option)
+// any later version.
+
+// This library is distributed in the hope that it will be useful,
+// but WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+// GNU General Public License for more details.
+
+// You should have received a copy of the GNU General Public License along
+// with this library; see the file COPYING3.  If not see
+// <http://www.gnu.org/licenses/>.
+
+// { dg-options "-std=gnu++2a" }
+// { dg-do run { target c++2a } }
+
+#include <iterator>
+#include <testsuite_hooks.h>
+
+void
+test01()
+{
+  using I = std::common_iterator<int*, const int*>;
+  static_assert( std::is_default_constructible_v<I> );
+  static_assert( std::is_copy_constructible_v<I> );
+  static_assert( std::is_copy_assignable_v<I> );
+  static_assert( std::is_constructible_v<I, int*> );
+  static_assert( std::is_constructible_v<I, const int*> );
+
+  struct sentinel { operator int*() const { return nullptr; } };
+  using K = std::common_iterator<int*, sentinel>;
+  static_assert( std::is_constructible_v<I, const K&> );
+  static_assert( std::is_assignable_v<I, const K&> );
+
+  struct sentinel2
+  {
+    const int* p;
+    sentinel2(const int* p = 0) : p(p) { }
+    bool operator==(const int* p) const { return p == this->p; }
+  };
+
+  using J = std::common_iterator<const int*, sentinel2>;
+  static_assert( std::is_constructible_v<J, const I&> );
+  static_assert( std::is_convertible_v<const I&, J> );
+}
+
+void
+test02()
+{
+  struct sentinel { int limit; };
+
+  struct iterator
+  {
+    using iterator_category = std::input_iterator_tag;
+    using value_type = int;
+    using difference_type = std::ptrdiff_t;
+    using reference = const int&;
+
+    const int& operator*() const { return counter; }
+
+    iterator& operator++() { ++counter; return *this; }
+
+    iterator operator++(int) { auto i = *this; ++counter; return i; }
+
+    bool operator==(sentinel s) const { return counter == s.limit; }
+
+    int counter = 0;
+  };
+
+  static_assert( std::sentinel_for<sentinel, iterator> );
+
+  int out[5] = { };
+  std::common_iterator<int*, const int*> obegin = std::begin(out);
+  std::common_iterator<int*, const int*> oend = std::cend(out);
+
+  iterator i;
+  sentinel s{5};
+  std::common_iterator<iterator, sentinel> begin = i, end = s;
+  while (begin != end)
+    *obegin++ = *begin++;
+
+  VERIFY(obegin == oend);
+  for (int& i : out)
+    VERIFY( i == (&i - out) );
+}
+
+void
+test03()
+{
+  int arr[2] = { 1, 2 };
+  std::common_iterator<int*, const int*> i = std::ranges::begin(arr);
+  std::common_iterator<int*, const int*> end = std::ranges::cend(arr);
+  VERIFY( i != end );
+  VERIFY( (end - i) == 2 );
+  VERIFY( (i - end) == -2 );
+  auto j = i;
+  VERIFY( j == i );
+  VERIFY( (j - i) == 0 );
+  j = end;
+  VERIFY( j != i );
+  VERIFY( j == end );
+  j = std::ranges::next(i);
+  VERIFY( j != i );
+  VERIFY( j != end );
+  VERIFY( (end - j) == 1 );
+  VERIFY( (j - i) == 1 );
+  VERIFY( (i - j) == -1 );
+  ++j;
+  VERIFY( j == end );
+  VERIFY( (end - j) == 0 );
+  j = i;
+  VERIFY( j == i );
+  VERIFY( (j - end) == -2 );
+  VERIFY( (j - i) == 0 );
+
+  try
+  {
+    struct S { operator const int*() const { throw 1; } };
+    i = std::common_iterator<int*, S>(S{});
+    VERIFY( false );
+  }
+  catch (int)
+  {
+  }
+}
+
+void
+test04()
+{
+  struct X
+  {
+    X(int i) : i(i) { }
+    X(X&& x) : i(x.i) { x.i = -1; }
+    X& operator=(X&& x) { i = x.i; x.i = 0; return *this; }
+    int i;
+  };
+
+  X arr[] = { 1, 2 };
+  std::common_iterator<X*, const X*> i(arr), j(arr+1);
+  std::ranges::iter_swap(i, j);
+  VERIFY( arr[0].i == 2 );
+  VERIFY( arr[1].i == 1 );
+
+  X x = std::ranges::iter_move(i);
+  VERIFY( arr[0].i == -1 );
+  VERIFY( x.i == 2 );
+}
+
+int
+main()
+{
+  test01();
+  test02();
+  test03();
+  test04();
+}
diff --git a/libstdc++-v3/testsuite/24_iterators/counted_iterator/1.cc b/libstdc++-v3/testsuite/24_iterators/counted_iterator/1.cc
new file mode 100644
index 00000000000..b31469cdebf
--- /dev/null
+++ b/libstdc++-v3/testsuite/24_iterators/counted_iterator/1.cc
@@ -0,0 +1,101 @@
+// Copyright (C) 2019 Free Software Foundation, Inc.
+//
+// This file is part of the GNU ISO C++ Library.  This library is free
+// software; you can redistribute it and/or modify it under the
+// terms of the GNU General Public License as published by the
+// Free Software Foundation; either version 3, or (at your option)
+// any later version.
+
+// This library is distributed in the hope that it will be useful,
+// but WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+// GNU General Public License for more details.
+
+// You should have received a copy of the GNU General Public License along
+// with this library; see the file COPYING3.  If not see
+// <http://www.gnu.org/licenses/>.
+
+// { dg-options "-std=gnu++2a" }
+// { dg-do run { target c++2a } }
+
+#include <iterator>
+#include <testsuite_hooks.h>
+
+void
+test01()
+{
+  using I = std::counted_iterator<int*>;
+  static_assert( std::is_default_constructible_v<I> );
+  static_assert( std::is_copy_constructible_v<I> );
+  static_assert( std::is_copy_assignable_v<I> );
+  static_assert( ! std::is_constructible_v<I, int*> );
+  static_assert( std::is_constructible_v<I, int*, std::ptrdiff_t> );
+
+  using J = std::counted_iterator<const int*>;
+  static_assert( std::is_constructible_v<J, const I&> );
+  static_assert( std::is_convertible_v<const I&, J> );
+}
+
+void
+test02()
+{
+  int in[3] = { 1, 2, 3 };
+  std::counted_iterator<const int*> in_iter(std::begin(in), std::ssize(in));
+  VERIFY( in_iter.base() == in );
+  VERIFY( (std::default_sentinel - in_iter) == 3 );
+  VERIFY( (in_iter - std::default_sentinel) == -3 );
+
+  int out[4] = { };
+  std::counted_iterator<int*> out_iter(std::begin(out), std::ssize(out));
+  VERIFY( out_iter.base() == out );
+  VERIFY( (std::default_sentinel - out_iter) == 4 );
+  VERIFY( (out_iter - std::default_sentinel) == -4 );
+
+  while (in_iter != std::default_sentinel && out_iter != std::default_sentinel)
+    *out_iter++ = *in_iter++;
+
+  VERIFY(in_iter == std::default_sentinel);
+  VERIFY(out_iter != std::default_sentinel);
+  VERIFY( out[0] == 1 );
+  VERIFY( out[1] == 2 );
+  VERIFY( out[2] == 3 );
+  VERIFY( out[3] == 0 );
+
+  auto out2 = out_iter;
+  out2 += 1;
+  VERIFY( out2 == std::default_sentinel );
+  VERIFY( (out2 <=> out_iter) == std::strong_ordering::greater );
+  out2 -= 3;
+  VERIFY( (out_iter - out2) == 2 );
+  VERIFY( (out2 <=> out_iter) == std::strong_ordering::less );
+}
+
+void
+test03()
+{
+  struct X
+  {
+    X(int i) : i(i) { }
+    X(X&& x) : i(x.i) { x.i = -1; }
+    X& operator=(X&& x) { i = x.i; x.i = 0; return *this; }
+    int i;
+  };
+
+  X arr[] = { 1, 2 };
+  std::counted_iterator<X*> i(arr, 2), j(arr + 1, 1);
+  std::ranges::iter_swap(i, j);
+  VERIFY( arr[0].i == 2 );
+  VERIFY( arr[1].i == 1 );
+
+  X x = std::ranges::iter_move(i);
+  VERIFY( arr[0].i == -1 );
+  VERIFY( x.i == 2 );
+}
+
+int
+main()
+{
+  test01();
+  test02();
+  test03();
+}
diff --git a/libstdc++-v3/testsuite/24_iterators/move_iterator/cust.cc b/libstdc++-v3/testsuite/24_iterators/move_iterator/cust.cc
new file mode 100644
index 00000000000..6d0817dc204
--- /dev/null
+++ b/libstdc++-v3/testsuite/24_iterators/move_iterator/cust.cc
@@ -0,0 +1,50 @@
+// Copyright (C) 2019 Free Software Foundation, Inc.
+//
+// This file is part of the GNU ISO C++ Library.  This library is free
+// software; you can redistribute it and/or modify it under the
+// terms of the GNU General Public License as published by the
+// Free Software Foundation; either version 3, or (at your option)
+// any later version.
+
+// This library is distributed in the hope that it will be useful,
+// but WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+// GNU General Public License for more details.
+
+// You should have received a copy of the GNU General Public License along
+// with this library; see the file COPYING3.  If not see
+// <http://www.gnu.org/licenses/>.
+
+// { dg-options "-std=gnu++2a" }
+// { dg-do run { target c++2a } }
+
+#include <iterator>
+#include <testsuite_hooks.h>
+
+void
+test01()
+{
+  struct X
+  {
+    X(int i) : i(i) { }
+    X(X&& x) : i(x.i) { x.i = -1; }
+    X& operator=(X&& x) { i = x.i; x.i = 0; return *this; }
+    int i;
+  };
+
+  X arr[] = { 1, 2 };
+  std::move_iterator<X*> i(arr), j(arr + 1);
+  std::ranges::iter_swap(i, j);
+  VERIFY( arr[0].i == 2 );
+  VERIFY( arr[1].i == 1 );
+
+  X x = std::ranges::iter_move(i);
+  VERIFY( arr[0].i == -1 );
+  VERIFY( x.i == 2 );
+}
+
+int
+main()
+{
+  test01();
+}
diff --git a/libstdc++-v3/testsuite/24_iterators/move_iterator/sentinel.cc b/libstdc++-v3/testsuite/24_iterators/move_iterator/sentinel.cc
new file mode 100644
index 00000000000..875a8fc37c4
--- /dev/null
+++ b/libstdc++-v3/testsuite/24_iterators/move_iterator/sentinel.cc
@@ -0,0 +1,91 @@
+// Copyright (C) 2019 Free Software Foundation, Inc.
+//
+// This file is part of the GNU ISO C++ Library.  This library is free
+// software; you can redistribute it and/or modify it under the
+// terms of the GNU General Public License as published by the
+// Free Software Foundation; either version 3, or (at your option)
+// any later version.
+
+// This library is distributed in the hope that it will be useful,
+// but WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+// GNU General Public License for more details.
+
+// You should have received a copy of the GNU General Public License along
+// with this library; see the file COPYING3.  If not see
+// <http://www.gnu.org/licenses/>.
+
+// { dg-options "-std=gnu++2a" }
+// { dg-do run { target c++2a } }
+
+#include <iterator>
+#include <testsuite_hooks.h>
+
+void
+test01()
+{
+  using S = std::move_sentinel<const int*>;
+  using M = std::move_iterator<int*>;
+
+  static_assert( std::is_default_constructible_v<S> );
+  static_assert( std::is_copy_constructible_v<S> );
+  static_assert( std::is_copy_assignable_v<S> );
+  static_assert( std::is_constructible_v<S, std::move_sentinel<int*>> );
+  static_assert( std::is_assignable_v<S, std::move_sentinel<int*>> );
+
+  constexpr S s;
+  static_assert( s.base() == nullptr );
+
+  constexpr M m;
+  static_assert( m == s );
+  static_assert( s == m );
+  static_assert( !(m != s) );
+  static_assert( !(s != m) );
+
+  int i = 0;
+  M m2(&i);
+  VERIFY( m2 != s );
+  VERIFY( s != m2 );
+  VERIFY( !(m2 == s) );
+  VERIFY( !(s == m2) );
+}
+
+void
+test02()
+{
+  struct sentinel { int limit; };
+
+  struct iterator
+  {
+    using iterator_category = std::input_iterator_tag;
+    using value_type = int;
+    using difference_type = std::ptrdiff_t;
+    using reference = const int&;
+
+    const int& operator*() const { return counter; }
+
+    iterator& operator++() { ++counter; return *this; }
+
+    iterator operator++(int) { auto i = *this; ++counter; return i; }
+
+    bool operator==(sentinel s) const { return counter == s.limit; }
+
+    int counter = 0;
+  };
+
+  static_assert( std::sentinel_for<sentinel, iterator> );
+
+  iterator i;
+  sentinel s{5};
+  int count = 0;
+  for (auto m = std::make_move_iterator(i); m != std::move_sentinel{s}; ++m)
+    ++count;
+  VERIFY( count == 5 );
+}
+
+int
+main()
+{
+  test01();
+  test02();
+}