Re: [Bug libstdc++/99402] [10/11 Regression] std::copy creates _GLIBCXX_DEBUG false positive for attempt to subscript a dereferenceable (start-of-sequence) iterator

[Jonathan Wakely <jwakely@redhat.com>]

On 11/03/21 18:51 +0100, François Dumont via Libstdc++ wrote:
>I eventually prefer to propose this version.
>
>Compared to the previous one I have the _M_can_advance calling the 
>former one with correct number of elements to check for advance. And 
>the former _M_can_advance is also properly making use of the 
>__dp_sign_max_size precision.
>
>Here is the revisited git log:
>
>    libstdc++: [_GLIBCXX_DEBUG] Fix management of __dp_sign_max_size 
>[PR 99402]
>
>    __dp_sign precision indicates that we found out what iterator 
>comes first or
>    last in the range. __dp_sign_max_size is the same plus it gives 
>the information
>    of the max size of the range that is to say the max_size value 
>such that
>    distance(lhs, rhs) < max_size.
>    Thanks to this additional information we are able to tell when a 
>copy of n elements
>    to that range will fail even if we do not know exactly how large it is.
>
>    This patch makes sure that we are properly using this information.
>
>    libstdc++-v3/ChangeLog:
>
>            PR libstdc++/99402
>            * include/debug/helper_functions.h 
>(__can_advance(_InputIterator,
>            const std::pair<_Diff, _Distance_precision>&, int)): New.
>            (__can_advance(const _Safe_iterator<>&,
>            const std::pair<_Diff, _Distance_precision>&, int)): New.
>            * include/debug/macros.h 
>(__glibcxx_check_can_increment_dist): New,
>            use latter.
>            (__glibcxx_check_can_increment_range): Adapt to use latter.
>            (__glibcxx_check_can_decrement_range): Likewise.
>            * include/debug/safe_iterator.h
>            (_Safe_iterator<>::_M_can_advance(const std::pair<_Diff, 
>_Distance_precision>&,
>            int)): New.
>            (__can_advance(const _Safe_iterator<>&,
>            const std::pair<_Diff, _Distance_precision>&, int)): New.
>            * include/debug/safe_iterator.tcc
>            (_Safe_iterator<>::_M_can_advance(const std::pair<_Diff, 
>_Distance_precision>&,
>            int)): New.
>            (_Safe_iterator<>::_M_valid_range(const _Safe_iterator<>&,
>            std::pair<difference_type, _Distance_precision>&, bool)): 
>Adapt for
>            __dp_sign_max_size.
>            (__copy_move_a): Adapt to use 
>__glibcxx_check_can_increment_dist.
>            (__copy_move_backward_a): Likewise.
>            (__equal_aux): Likewise.
>            * include/debug/stl_iterator.h (__can_advance(const 
>std::reverse_iterator<>&,
>            const std::pair<_Diff, _Distance_precision>&, int)): New.
>            (__can_advance(const std::move_iterator<>&,
>            const std::pair<_Diff, _Distance_precision>&, int)): New.
>            * testsuite/25_algorithms/copy/debug/99402.cc: New test.
>
>Ok to commit if tests are all PASS ?
>
>François
>
>On 07/03/21 10:30 pm, François Dumont wrote:
>>Here is the patch to correctly deal with the new __dp_sign_max_size.
>>
>>I prefer to introduce new __can_advance overloads for this to 
>>correctly deal with the _Distance_precision in it. _M_valid_range 
>>was also ignoring __dp_sign_max_size.
>>
>>    libstdc++: [_GLIBCXX_DEBUG] Fix management of __dp_sign_max_size 
>>[PR 99402]
>>
>>    libstdc++-v3/ChangeLog:
>>
>>            PR libstdc++/99402
>>            * include/debug/helper_functions.h 
>>(__can_advance(_InputIterator,
>>            const std::pair<_Diff, _Distance_precision>&, int)): New.
>>            (__can_advance(const _Safe_iterator<>&,
>>            const std::pair<_Diff, _Distance_precision>&, int)): New.
>>            * include/debug/macros.h 
>>(__glibcxx_check_can_increment_dist): New,
>>            use latter.
>>            (__glibcxx_check_can_increment_range): Adapt to use latter.
>>            (__glibcxx_check_can_decrement_range): Likewise.
>>            * include/debug/safe_iterator.h
>>            (_Safe_iterator<>::_M_can_advance(const std::pair<_Diff, 
>>_Distance_precision>&,
>>            int)): New.
>>            (__can_advance(const _Safe_iterator<>&,
>>            const std::pair<_Diff, _Distance_precision>&, int)): New.
>>            * include/debug/safe_iterator.tcc
>>            (_Safe_iterator<>::_M_can_advance(const std::pair<_Diff, 
>>_Distance_precision>&,
>>            int)): New.
>>            (_Safe_iterator<>::_M_valid_range(const _Safe_iterator<>&,
>>            std::pair<difference_type, _Distance_precision>&, 
>>bool)): Adapt for
>>            __dp_sign_max_size.
>>            (__copy_move_a): Adapt to use 
>>__glibcxx_check_can_increment_dist.
>>            (__copy_move_backward_a): Likewise.
>>            (__equal_aux): Likewise.
>>            * include/debug/stl_iterator.h (__can_advance(const 
>>std::reverse_iterator<>&,
>>            const std::pair<_Diff, _Distance_precision>&, int)): New.
>>            (__can_advance(const std::move_iterator<>&,
>>            const std::pair<_Diff, _Distance_precision>&, int)): New.
>>            * testsuite/25_algorithms/copy/debug/99402.cc: New test.
>>
>>Tested under Linux x86_64.
>>
>>Ok to commit ?
>>
>>François
>>
>

>diff --git a/libstdc++-v3/include/debug/helper_functions.h b/libstdc++-v3/include/debug/helper_functions.h
>index 513e5460eba..c0144ced979 100644
>--- a/libstdc++-v3/include/debug/helper_functions.h
>+++ b/libstdc++-v3/include/debug/helper_functions.h
>@@ -291,6 +291,18 @@ namespace __gnu_debug
>     __can_advance(const _Safe_iterator<_Iterator, _Sequence, _Category>&,
> 		  _Size);
> 
>+  template<typename _InputIterator, typename _Diff>
>+    _GLIBCXX_CONSTEXPR
>+    inline bool
>+    __can_advance(_InputIterator, const std::pair<_Diff, _Distance_precision>&, int)
>+    { return true; }
>+
>+  template<typename _Iterator, typename _Sequence, typename _Category,
>+	   typename _Diff>
>+    bool
>+    __can_advance(const _Safe_iterator<_Iterator, _Sequence, _Category>&,
>+		  const std::pair<_Diff, _Distance_precision>&, int);
>+
>   /** Helper function to extract base iterator of random access safe iterator
>    *  in order to reduce performance impact of debug mode.  Limited to random
>    *  access iterator because it is the only category for which it is possible
>diff --git a/libstdc++-v3/include/debug/macros.h b/libstdc++-v3/include/debug/macros.h
>index 0988437046f..9ac52ebd09d 100644
>--- a/libstdc++-v3/include/debug/macros.h
>+++ b/libstdc++-v3/include/debug/macros.h
>@@ -94,6 +94,12 @@ _GLIBCXX_DEBUG_VERIFY(__gnu_debug::__can_advance(_First, _Size),	\
> 		      ._M_iterator(_First, #_First)			\
> 		      ._M_integer(_Size, #_Size))
> 
>+#define __glibcxx_check_can_increment_dist(_First,_Dist,_Way)		\
>+  _GLIBCXX_DEBUG_VERIFY(__gnu_debug::__can_advance(_First, _Dist, _Way), \
>+		      _M_message(__gnu_debug::__msg_iter_subscript_oob)	\
>+		      ._M_iterator(_First, #_First)			\
>+		      ._M_integer(_Way * _Dist.first, #_Dist))
>+
> #define __glibcxx_check_can_increment_range(_First1,_Last1,_First2)	\
>   do									\
>   {									\
>@@ -105,7 +111,7 @@ _GLIBCXX_DEBUG_VERIFY(__gnu_debug::__can_advance(_First, _Size),	\
> 			._M_iterator(_Last1, #_Last1),			\
> 			__FILE__,__LINE__,__PRETTY_FUNCTION__);		\
>     _GLIBCXX_DEBUG_VERIFY_AT_F(						\
>-			__gnu_debug::__can_advance(_First2, __dist.first),\
>+			__gnu_debug::__can_advance(_First2, __dist, 1), \
> 			_M_message(__gnu_debug::__msg_iter_subscript_oob)\
> 			._M_iterator(_First2, #_First2)			\
> 			._M_integer(__dist.first),			\
>@@ -123,7 +129,7 @@ _GLIBCXX_DEBUG_VERIFY(__gnu_debug::__can_advance(_First, _Size),	\
> 			._M_iterator(_Last1, #_Last1),			\
> 			__FILE__,__LINE__,__PRETTY_FUNCTION__);		\
>     _GLIBCXX_DEBUG_VERIFY_AT_F(						\
>-			__gnu_debug::__can_advance(_First2, -__dist.first),\
>+			__gnu_debug::__can_advance(_First2, __dist, -1), \
> 			_M_message(__gnu_debug::__msg_iter_subscript_oob)\
> 			._M_iterator(_First2, #_First2)			\
> 			._M_integer(-__dist.first),			\
>diff --git a/libstdc++-v3/include/debug/safe_iterator.h b/libstdc++-v3/include/debug/safe_iterator.h
>index a10df190969..8e138fd32e5 100644
>--- a/libstdc++-v3/include/debug/safe_iterator.h
>+++ b/libstdc++-v3/include/debug/safe_iterator.h
>@@ -407,6 +407,12 @@ namespace __gnu_debug
>       bool
>       _M_can_advance(difference_type __n, bool __strict = false) const;
> 
>+      // Can we advance the iterator using @p __dist in @p __way direction.
>+      template<typename _Diff>
>+	bool
>+	_M_can_advance(const std::pair<_Diff, _Distance_precision>& __dist,
>+		       int __way) const;
>+
>       // Is the iterator range [*this, __rhs) valid?
>       bool
>       _M_valid_range(const _Safe_iterator& __rhs,
>@@ -958,6 +964,14 @@ namespace __gnu_debug
> 		  _Size __n)
>     { return __it._M_can_advance(__n); }
> 
>+  template<typename _Iterator, typename _Sequence, typename _Category,
>+	   typename _Diff>
>+    inline bool
>+    __can_advance(const _Safe_iterator<_Iterator, _Sequence, _Category>& __it,
>+		  const std::pair<_Diff, _Distance_precision>& __dist,
>+		  int __way)
>+    { return __it._M_can_advance(__dist, __way); }
>+
>   template<typename _Iterator, typename _Sequence>
>     _Iterator
>     __base(const _Safe_iterator<_Iterator, _Sequence,
>diff --git a/libstdc++-v3/include/debug/safe_iterator.tcc b/libstdc++-v3/include/debug/safe_iterator.tcc
>index 81deb10125b..6f14c40bf41 100644
>--- a/libstdc++-v3/include/debug/safe_iterator.tcc
>+++ b/libstdc++-v3/include/debug/safe_iterator.tcc
>@@ -92,22 +92,30 @@ namespace __gnu_debug
>       if (__n == 0)
> 	return true;
> 
>+      std::pair<difference_type, _Distance_precision> __dist = __n < 0
>+	? _M_get_distance_from_begin()
>+	: _M_get_distance_to_end();
>+
>       if (__n < 0)
>-	{
>-	  std::pair<difference_type, _Distance_precision> __dist =
>-	    _M_get_distance_from_begin();
>-	  return __dist.second == __dp_exact
>-	    ? __dist.first >= -__n
>+	__n = -__n;
>+
>+      return __dist.second > __dp_sign
>+	? __dist.first >= __n
> 	: !__strict && __dist.first > 0;
>     }
>-      else
>+
>+  template<typename _Iterator, typename _Sequence, typename _Category>
>+    template<typename _Diff>
>+      bool
>+      _Safe_iterator<_Iterator, _Sequence, _Category>::
>+      _M_can_advance(const std::pair<_Diff, _Distance_precision>& __dist,
>+		     int __way) const
>       {
>-	  std::pair<difference_type, _Distance_precision> __dist =
>-	    _M_get_distance_to_end();
> 	return __dist.second == __dp_exact
>-	    ? __dist.first >= __n
>-	    : !__strict && __dist.first > 0;
>-	}
>+	  ? _M_can_advance(__way * __dist.first)
>+	  : _M_can_advance(__way * (__dist.first == 0
>+				    ? 0
>+				    : __dist.first < 0 ? -1 : 1));
>       }
> 
>   template<typename _Iterator, typename _Sequence, typename _Category>
>@@ -194,20 +202,15 @@ namespace __gnu_debug
>       switch (__dist.second)
> 	{
> 	case __dp_equality:
>-	  if (__dist.first == 0)
>+	  // Assume that this is a valid range; we can't check anything else.
> 	  return true;
>-	  break;
> 
>-	case __dp_sign:
>-	case __dp_exact:
>+	default:
> 	  // If range is not empty first iterator must be dereferenceable.
>-	  if (__dist.first > 0)
>-	    return !__check_dereferenceable || _M_dereferenceable();
>-	  return __dist.first == 0;
>+	  return __dist.first == 0
>+	    || (__dist.first > 0
>+		&& (!__check_dereferenceable || _M_dereferenceable()));
> 	}

This doesn't really make sense to use a switch now, it could be
simply:

if (__dist.second != __dp_equality)
   {
     // If range is not empty first iterator must be dereferenceable.
     return __dist.first == 0
       || (__dist.first > 0
           && (!__check_dereferenceable || _M_dereferenceable()));
   }

// Assume that this is a valid range; we can't check anything else.
return true;


I don't understand any of this code, but it's currently broken so OK
for trunk.