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

["François Dumont" <frs.dumont@gmail.com>]

On 08/04/21 3:07 pm, Jonathan Wakely wrote:
> 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;
>
Yes, I missed that. I tested and committed with this simplification.
>
> I don't understand any of this code, but it's currently broken so OK
> for trunk.
>
Maybe there will be something to do to clarify then.