[Bug c++/99402] New: std::copy creates _GLIBCXX_DEBUG false positive for attempt to subscript a dereferenceable (start-of-sequence) iterator

[Bug c++/99402] New: std::copy creates _GLIBCXX_DEBUG false positive for attempt to subscript a dereferenceable (start-of-sequence) iterator

[kip at thevertigo dot com]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=99402

            Bug ID: 99402
           Summary: std::copy creates _GLIBCXX_DEBUG false positive for
                    attempt to subscript a dereferenceable
                    (start-of-sequence) iterator
           Product: gcc
           Version: 10.2.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: c++
          Assignee: unassigned at gcc dot gnu.org
          Reporter: kip at thevertigo dot com
  Target Milestone: ---

The following is a minimal:

// Standard C++ / POSIX system headers...
#include <algorithm>
#include <set>
#include <vector>

using namespace std;

int main()
{
    // Container of eleven elements...
    const set<int> Source = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };

    // Goal is to copy the first ten elements in to here, or 0 to 9 inclusive.
    //  It has space for ten elements...
    vector<int> Destination(10);

    // This should point to the end of the source range, or element with value
    //  10 which is the first value after the range to be copied...
    const auto EndIterator = next(cbegin(Source), 10);

    // This results in memory corruption, or an abort with STL debugging
    //  enabled. copy_n(..., 10, ...) works fine...
    copy(cbegin(Source), EndIterator, begin(Destination));

    return 0;
}

Compile and run with the following:

    $ g++-10 -D_GLIBCXX_DEBUG test.cpp -o test -g3 -std=c++17 && ./test 

I see the following:

    /usr/include/c++/10/bits/stl_algobase.h:566:
    In function:
        _OI std::copy(_II, _II, _OI) [with _II = 
        __gnu_debug::_Safe_iterator<std::_Rb_tree_const_iterator<int>, 
        std::__debug::set<int>, std::bidirectional_iterator_tag>; _OI = 
        __gnu_debug::_Safe_iterator<__gnu_cxx::__normal_iterator<int*, 
        std::__cxx1998::vector<int, std::allocator<int> > >, 
        std::__debug::vector<int>, std::random_access_iterator_tag>]

    Error: attempt to subscript a dereferenceable (start-of-sequence) iterator 
    11 step from its current position, which falls outside its dereferenceable 
    range.

    Objects involved in the operation:
        iterator "__result" @ 0x0x7ffc3a448040 {
          type = __gnu_cxx::__normal_iterator<int*, std::__cxx1998::vector<int,
std::allocator<int> > > (mutable iterator);
          state = dereferenceable (start-of-sequence);
          references sequence with type 'std::__debug::vector<int,
std::allocator<int> >' @ 0x0x7ffc3a4480d0
        }
    Aborted (core dumped)

I've been advised from another who ran the same test that this works fine with
GCC 8 and 9, so it may be a regression.

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

[redi at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=99402

Jonathan Wakely <redi at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
     Ever confirmed|0                           |1
      Known to work|                            |9.3.0
   Target Milestone|---                         |10.3
            Summary|std::copy creates           |[10/11 Regression]
                   |_GLIBCXX_DEBUG false        |std::copy creates
                   |positive for attempt to     |_GLIBCXX_DEBUG false
                   |subscript a dereferenceable |positive for attempt to
                   |(start-of-sequence)         |subscript a dereferenceable
                   |iterator                    |(start-of-sequence)
                   |                            |iterator
                 CC|                            |fdumont at gcc dot gnu.org
      Known to fail|                            |10.1.0, 10.2.0, 11.0
             Status|UNCONFIRMED                 |NEW
   Last reconfirmed|                            |2021-03-05

--- Comment #1 from Jonathan Wakely <redi at gcc dot gnu.org> ---
Probably caused by r276600

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

[redi at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=99402

--- Comment #2 from Jonathan Wakely <redi at gcc dot gnu.org> ---
(In reply to Kip Warner from comment #0)
>     // This results in memory corruption, or an abort with STL debugging

I don't see any memory corruption, I think it's just a bug in the Debug Mode
checks, which aborts when it shouldn't do. Without those bad checks it doesn't
abort, and works correctly.

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

[redi at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=99402

--- Comment #3 from Jonathan Wakely <redi at gcc dot gnu.org> ---
François, this can't be right:

          return std::make_pair(-__seq_dist.first,
                                __seq_dist.second == __dp_exact
                                ? __dp_sign_max_size : __seq_dist.second);

This uses __seq_dist.second, but __seq_dist comes from _SeqTraits::_S_size
which is:

  template<typename _Sequence>
    struct _Sequence_traits
    {
      typedef _Distance_traits<typename _Sequence::iterator> _DistTraits;

      static typename _DistTraits::__type
      _S_size(const _Sequence& __seq)
      { return std::make_pair(__seq.size(), __dp_exact); }
    };

i.e. __seq_dist.second is always __dp_exact, so this function always returns
__dp_sign_max_size.

You should be using __base_dist.second, no?

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

[redi at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=99402

--- Comment #4 from Jonathan Wakely <redi at gcc dot gnu.org> ---
This causes __valid_range to return {11, __dp_sign_max_size} and then we check
__result._M_can_advance(11) which fails.

We don't want to advance the result by the size of the other sequence, only by
distance(__first, __last). We don't care if there are elements in the sequence
past __last because we're not trying to copy them.

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

[redi at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=99402

--- Comment #5 from Jonathan Wakely <redi at gcc dot gnu.org> ---
(In reply to Jonathan Wakely from comment #3)
> You should be using __base_dist.second, no?

No, it's not that simple. I don't understand how this code is meant to work,
but this can't be right:

      if (this->_M_is_begin())
        {
          if (__rhs._M_is_before_begin())
            return std::make_pair(-1, __dp_exact);

          if (__rhs._M_is_end())
            return __seq_dist;

          return std::make_pair(__seq_dist.first,
                                __seq_dist.second == __dp_exact
                                ? __dp_sign_max_size : __seq_dist.second);
        }

We can't use __seq_dist.first as the distance, because we have already
established that __rhs is not the end iterator, so it must be before the end.
And so the distance we're trying to find must be less than __seq_dist.first.

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

[redi at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=99402

--- Comment #6 from Jonathan Wakely <redi at gcc dot gnu.org> ---
Reduced:

#include <algorithm>
#include <set>
#include <vector>

using namespace std;

int main()
{
    // any container with non-random access iterators:
    const set<int> source = { 0, 1 };
    vector<int> dest(1);
    copy(source.begin(), ++source.begin(), dest.begin());
}

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

[fdumont at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=99402

François Dumont <fdumont at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Assignee|unassigned at gcc dot gnu.org      |fdumont at gcc dot gnu.org
             Status|NEW                         |ASSIGNED

--- Comment #7 from François Dumont <fdumont at gcc dot gnu.org> ---
Yes, when I introduced __dp_sign_max_size in the _Distance_precision enum I
forgot to adapt some code.

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

[kip at thevertigo dot com]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=99402

--- Comment #8 from Kip Warner <kip at thevertigo dot com> ---
And for anyone finding this from a search engine, the temporary workaround is
to use std::copy_n.

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

[rguenth at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=99402

Richard Biener <rguenth at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|10.3                        |10.4

--- Comment #9 from Richard Biener <rguenth at gcc dot gnu.org> ---
GCC 10.3 is being released, retargeting bugs to GCC 10.4.

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

[rguenth at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=99402

Richard Biener <rguenth at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Priority|P3                          |P2

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

[redi at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=99402

Jonathan Wakely <redi at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
            Summary|[10/11 Regression]          |[10 Regression] std::copy
                   |std::copy creates           |creates _GLIBCXX_DEBUG
                   |_GLIBCXX_DEBUG false        |false positive for attempt
                   |positive for attempt to     |to subscript a
                   |subscript a dereferenceable |dereferenceable
                   |(start-of-sequence)         |(start-of-sequence)
                   |iterator                    |iterator

--- Comment #10 from Jonathan Wakely <redi at gcc dot gnu.org> ---
This was fixed on trunk by r11-8100:

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.

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

[kip at thevertigo dot com]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=99402

--- Comment #11 from Kip Warner <kip at thevertigo dot com> ---
Thanks Jonathan. That was a constructive follow up.

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

[redi at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=99402

--- Comment #12 from Jonathan Wakely <redi at gcc dot gnu.org> ---
François fixed it. I just pasted the info here that didn't get automatically
added by the commit hooks, for some reason.

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

[fdumont at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=99402

--- Comment #13 from François Dumont <fdumont at gcc dot gnu.org> ---
Fixed on gcc-10 branch by this commit
https://gcc.gnu.org/git/?p=gcc.git;a=commit;h=ab83ce42ea0b2fbc09d51b7bd5e69905dcaa2041.

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

[redi at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=99402

Jonathan Wakely <redi at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
         Resolution|---                         |FIXED
             Status|ASSIGNED                    |RESOLVED

--- Comment #14 from Jonathan Wakely <redi at gcc dot gnu.org> ---
Fixed for 10.4 then. Thanks, François.