libstdc++: Avoid using std::__to_address with iterators

In r12-3935-g82626be2d633a9 I added the partial specialization
std::pointer_traits<__normal_iterator<It, Cont>> so that __to_address
would work with __normal_iterator objects. Soon after that, François
replaced it in r12-6004-g807ad4bc854cae with an overload of __to_address
that served the same purpose, but was less complicated and less wrong.

I now think that both commits were mistakes, and that instead of adding
hacks to make __normal_iterator work with __to_address, we should not be
using __to_address with iterators at all before C++20.

The pre-C++20 std::__to_address function should only be used with
pointer-like types, specifically allocator_traits<A>::pointer types.
Those pointer-like types are guaranteed to be contiguous iterators, so
that getting a raw memory address from them is OK.

For arbitrary iterators, even random access iterators, we don't know
that it's safe to lower the iterator to a pointer e.g. for std::deque
iterators it's not, because (it + n) == (std::to_address(it) + n) only
holds within the same block of the deque's storage.

For C++20, std::to_address does work correctly for contiguous iterators,
including __normal_iterator, and __to_address just calls std::to_address
so also works. But we have to be sure we have an iterator that satisfies
the std::contiguous_iterator concept for it to be safe, and we can't
check that before C++20.

So for pre-C++20 code the correct way to handle iterators that might be
pointers or might be __normal_iterator is to call __niter_base, and if
necessary use is_pointer to check whether __niter_base returned a real
pointer.

We currently have some uses of std::__to_address with iterators where
we've checked that they're either pointers, or __normal_iterator
wrappers around pointers, or satisfy std::contiguous_iterator. But this
seems a little fragile, and it would be better to just use
std::__niter_base for the pointers and __normal_iterator cases, and use
C++20 std::to_address when the C++20 std::contiguous_iterator concept is
satisfied. This patch does that.

libstdc++-v3/ChangeLog:

	* include/bits/basic_string.h (basic_string::assign): Replace
	use of __to_address with __niter_base or std::to_address as
	appropriate.
	* include/bits/ptr_traits.h (__to_address): Add comment.
	* include/bits/shared_ptr_base.h (__shared_ptr): Qualify calls
	to __to_address.
	* include/bits/stl_algo.h (find): Replace use of __to_address
	with __niter_base or std::to_address as appropriate. Only use
	either of them when the range is not empty.
	* include/bits/stl_iterator.h (__to_address): Remove overload
	for __normal_iterator.
	* include/debug/safe_iterator.h (__to_address): Remove overload
	for _Safe_iterator.
	* include/std/ranges (views::counted): Replace use of
	__to_address with std::to_address.
	* testsuite/24_iterators/normal_iterator/to_address.cc: Removed.

8 files changed, 31 insertions, 62 deletions

diff --git a/libstdc++-v3/include/bits/basic_string.h b/libstdc++-v3/include/bits/basic_string.h
index e9b17ea..16e356e 100644
--- a/libstdc++-v3/include/bits/basic_string.h
+++ b/libstdc++-v3/include/bits/basic_string.h
@@ -1732,18 +1732,25 @@ _GLIBCXX_BEGIN_NAMESPACE_CXX11
 	basic_string&
 	assign(_InputIterator __first, _InputIterator __last)
 	{
+	  using _IterTraits = iterator_traits<_InputIterator>;
+	  if constexpr (is_pointer<decltype(std::__niter_base(__first))>::value
+			  && is_same<typename _IterTraits::value_type,
+				     _CharT>::value)
+	    {
+	      __glibcxx_requires_valid_range(__first, __last);
+	      return _M_replace(size_type(0), size(),
+				std::__niter_base(__first), __last - __first);
+	    }
 #if __cplusplus >= 202002L
-	  if constexpr (contiguous_iterator<_InputIterator>
-			  && is_same_v<iter_value_t<_InputIterator>, _CharT>)
-#else
-	  if constexpr (__is_one_of<_InputIterator, const_iterator, iterator,
-				    const _CharT*, _CharT*>::value)
-#endif
+	  else if constexpr (contiguous_iterator<_InputIterator>
+			       && is_same_v<iter_value_t<_InputIterator>,
+					    _CharT>)
 	    {
 	      __glibcxx_requires_valid_range(__first, __last);
 	      return _M_replace(size_type(0), size(),
 				std::__to_address(__first), __last - __first);
 	    }
+#endif
 	  else
 	    return *this = basic_string(__first, __last, get_allocator());
 	}
diff --git a/libstdc++-v3/include/bits/ptr_traits.h b/libstdc++-v3/include/bits/ptr_traits.h
index ca67fee..cef88f61 100644
--- a/libstdc++-v3/include/bits/ptr_traits.h
+++ b/libstdc++-v3/include/bits/ptr_traits.h
@@ -211,6 +211,10 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
       return __ptr;
     }
 
+  // This should only be used for pointer-like types (e.g. allocator pointers)
+  // and (in C++20 and later) for types satisfying std::contiguous_iterator.
+  // It should not be used for arbitrary random access iterators, because
+  // they might not be contiguous iterators (e.g. deque::iterator isn't).
   template<typename _Ptr>
     constexpr typename std::pointer_traits<_Ptr>::element_type*
     __to_address(const _Ptr& __ptr)
diff --git a/libstdc++-v3/include/bits/shared_ptr_base.h b/libstdc++-v3/include/bits/shared_ptr_base.h
index ef0658f..9a7617e 100644
--- a/libstdc++-v3/include/bits/shared_ptr_base.h
+++ b/libstdc++-v3/include/bits/shared_ptr_base.h
@@ -1560,7 +1560,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	__shared_ptr(unique_ptr<_Yp, _Del>&& __r)
 	: _M_ptr(__r.get()), _M_refcount()
 	{
-	  auto __raw = __to_address(__r.get());
+	  auto __raw = std::__to_address(__r.get());
 	  _M_refcount = __shared_count<_Lp>(std::move(__r));
 	  _M_enable_shared_from_this_with(__raw);
 	}
@@ -1576,7 +1576,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	__shared_ptr(unique_ptr<_Tp1, _Del>&& __r, __sp_array_delete)
 	: _M_ptr(__r.get()), _M_refcount()
 	{
-	  auto __raw = __to_address(__r.get());
+	  auto __raw = std::__to_address(__r.get());
 	  _M_refcount = __shared_count<_Lp>(std::move(__r));
 	  _M_enable_shared_from_this_with(__raw);
 	}
diff --git a/libstdc++-v3/include/bits/stl_algo.h b/libstdc++-v3/include/bits/stl_algo.h
index 780bd8e..c10f8aa 100644
--- a/libstdc++-v3/include/bits/stl_algo.h
+++ b/libstdc++-v3/include/bits/stl_algo.h
@@ -3834,7 +3834,7 @@ _GLIBCXX_BEGIN_NAMESPACE_ALGO
       using _ValT = typename iterator_traits<_InputIterator>::value_type;
       if constexpr (__can_use_memchr_for_find<_ValT, _Tp>)
 	if constexpr (is_pointer_v<decltype(std::__niter_base(__first))>
-#if __cpp_lib_concepts
+#if __glibcxx_concepts && __glibcxx_to_address
 			|| contiguous_iterator<_InputIterator>
 #endif
 		     )
@@ -3847,11 +3847,17 @@ _GLIBCXX_BEGIN_NAMESPACE_ALGO
 	      return __last;
 	    else if (!__is_constant_evaluated())
 	      {
-		const void* __p0 = std::__to_address(__first);
 		const int __ival = static_cast<int>(__val);
-		if (auto __n = std::distance(__first, __last); __n > 0)
-		  if (auto __p1 = __builtin_memchr(__p0, __ival, __n))
-		    return __first + ((const char*)__p1 - (const char*)__p0);
+		if (auto __n = __last - __first; __n > 0)
+		  {
+#if __glibcxx_concepts && __glibcxx_to_address
+		    const void* __p0 = std::to_address(__first);
+#else
+		    const void* __p0 = std::__niter_base(__first);
+#endif
+		    if (auto __p1 = __builtin_memchr(__p0, __ival, __n))
+		      return __first + ((const char*)__p1 - (const char*)__p0);
+		  }
 		return __last;
 	      }
 	  }
diff --git a/libstdc++-v3/include/bits/stl_iterator.h b/libstdc++-v3/include/bits/stl_iterator.h
index 1fbc115..46e0d46 100644
--- a/libstdc++-v3/include/bits/stl_iterator.h
+++ b/libstdc++-v3/include/bits/stl_iterator.h
@@ -1348,18 +1348,6 @@ namespace std _GLIBCXX_VISIBILITY(default)
 {
 _GLIBCXX_BEGIN_NAMESPACE_VERSION
 
-#if __cplusplus >= 201103L && __cplusplus <= 201703L
-  // Need to overload __to_address because the pointer_traits primary template
-  // will deduce element_type of __normal_iterator<T*, C> as T* rather than T.
-  template<typename _Iterator, typename _Container>
-    [[__gnu__::__always_inline__]] _GLIBCXX_NODISCARD
-    constexpr auto
-    __to_address(const __gnu_cxx::__normal_iterator<_Iterator,
-						    _Container>& __it) noexcept
-    -> decltype(std::__to_address(__it.base()))
-    { return std::__to_address(__it.base()); }
-#endif
-
 #if __cplusplus >= 201103L
   /**
    * @addtogroup iterators
diff --git a/libstdc++-v3/include/debug/safe_iterator.h b/libstdc++-v3/include/debug/safe_iterator.h
index d3e959b..983cbae 100644
--- a/libstdc++-v3/include/debug/safe_iterator.h
+++ b/libstdc++-v3/include/debug/safe_iterator.h
@@ -1161,23 +1161,6 @@ namespace __gnu_debug
 
 } // namespace __gnu_debug
 
-#if __cplusplus >= 201103L && __cplusplus <= 201703L
-namespace std _GLIBCXX_VISIBILITY(default)
-{
-_GLIBCXX_BEGIN_NAMESPACE_VERSION
-
-  template<typename _Iterator, typename _Container, typename _Sequence>
-    constexpr auto
-    __to_address(const __gnu_debug::_Safe_iterator<
-		 __gnu_cxx::__normal_iterator<_Iterator, _Container>,
-		 _Sequence>& __it) noexcept
-    -> decltype(std::__to_address(__it.base().base()))
-    { return std::__to_address(__it.base().base()); }
-
-_GLIBCXX_END_NAMESPACE_VERSION
-}
-#endif
-
 #undef _GLIBCXX20_CONSTEXPR_NON_LITERAL_SCOPE_END
 #undef _GLIBCXX20_CONSTEXPR_NON_LITERAL_SCOPE_BEGIN
 #undef _GLIBCXX_DEBUG_VERIFY_DIST_OPERANDS
diff --git a/libstdc++-v3/include/std/ranges b/libstdc++-v3/include/std/ranges
index 5b45588..9f23372 100644
--- a/libstdc++-v3/include/std/ranges
+++ b/libstdc++-v3/include/std/ranges
@@ -3935,7 +3935,7 @@ namespace views::__adaptor
       operator() [[nodiscard]] (_Iter __i, iter_difference_t<_Iter> __n) const
       {
 	if constexpr (contiguous_iterator<_Iter>)
-	  return span(std::__to_address(__i), __n);
+	  return span(std::to_address(__i), __n);
 	else if constexpr (random_access_iterator<_Iter>)
 	  return subrange(__i, __i + __n);
 	else
diff --git a/libstdc++-v3/testsuite/24_iterators/normal_iterator/to_address.cc b/libstdc++-v3/testsuite/24_iterators/normal_iterator/to_address.cc
deleted file mode 100644
index 6afc654..0000000
--- a/libstdc++-v3/testsuite/24_iterators/normal_iterator/to_address.cc
+++ /dev/null
@@ -1,19 +0,0 @@
-// { dg-do compile { target { c++11 } } }
-#include <string>
-#include <vector>
-#include <memory>
-
-#include <testsuite_allocator.h>
-
-char* p __attribute__((unused))
-  = std::__to_address(std::string("1").begin());
-const char* q __attribute__((unused))
-  = std::__to_address(std::string("2").cbegin());
-int* r __attribute__((unused))
-  = std::__to_address(std::vector<int>(1, 1).begin());
-const int* s __attribute__((unused))
-  = std::__to_address(std::vector<int>(1, 1).cbegin());
-int* t __attribute__((unused))
-  = std::__to_address(std::vector<int, __gnu_test::CustomPointerAlloc<int>>(1, 1).begin());
-const int* u __attribute__((unused))
-  = std::__to_address(std::vector<int, __gnu_test::CustomPointerAlloc<int>>(1, 1).cbegin());