PR libstdc++/60587

[Jonathan Wakely <jwakely at redhat dot com>]

I'm debugging http://gcc.gnu.org/bugzilla/show_bug.cgi?id=60587 and
have found a number of problems.

Firstly, the bug report is correct, this overload dereferences the
__other argument without checking if that is OK:

  template<typename _Iterator, typename _Sequence, typename _InputIterator>
    inline bool
    __foreign_iterator_aux3(const _Safe_iterator<_Iterator, _Sequence>& __it,
          _InputIterator __other,
          std::true_type)

Secondly, in this testcase we should never even have reached that
overload, because we should have gone to this overload of _aux2:

  template<typename _Iterator, typename _Sequence, typename _OtherIterator>
    inline bool
    __foreign_iterator_aux2(const _Safe_iterator<_Iterator, _Sequence>& __it,
    const _Safe_iterator<_OtherIterator, _Sequence>& __other,
    std::input_iterator_tag)
    { return __it._M_get_sequence() != __other._M_get_sequence(); }

However that is not chosen by overload resolution because this is a better
match when __other is non-const:

  template<typename _Iterator, typename _Sequence, typename _InputIterator>
    inline bool
    __foreign_iterator_aux2(const _Safe_iterator<_Iterator, _Sequence>& __it,
          _InputIterator __other,
          std::random_access_iterator_tag)

Fixing the overload resolution bug makes the testcase in the PR pass,
but the underlying problem of dereferencing an invalid iterator still
exists and can be shown by changing the testcase slightly:

#define _GLIBCXX_DEBUG
#include <vector>
int main() {
    std::vector<int> a;
    std::vector<long> b;
    a.push_back(1);
    a.insert(a.end(), b.begin(), b.end());
}

That still dereferences b.begin(), but that too can be fixed (either
as suggested in the PR or by passing the begin and end iterators into
the __foreign_iter function) but I think there's still another
problem.

I'm looking again at the code that attempts to check if we have
contiguous storage:

  if (std::addressof(*(__it._M_get_sequence()->_M_base().end() - 1))
      - std::addressof(*(__it._M_get_sequence()->_M_base().begin()))
      == __it._M_get_sequence()->size() - 1)

Are we really sure that ensures contiguous iterators? What if we have
a deque with three blocks laid out in memory like this:
 
 1XXXXXXX........3XXxxxxx................2XXXXXXX
 ^                  ^
 begin()            end()

1 is the start of the first block, 2 is the start of the second block
and 3 is the start of the third block.
X is an element, x is reserved but uninitialized capacity
. is unallocated memory (or memory not used by the deque)

Here we have end() - begin() == size() but non-contiguous memory.
If the __other iterator happens to point to the unallocated memory
between 1 and 3 then it will appear to be part of the deque, but
isn't.

I think the safe thing to do is (as I suggested at the time) to have a
trait saying which iterator types refer to contiguous memory. Our
debug mode only supports our own containers, so the ones which are
contiguous are known.  For 4.9.0 I think the right option is simply
to remove __foreign_iterator_aux3 and __foreign_iterator_aux4
completely. The fixed version of __foreign_iterator_aux2() can detect
when we have iterators referring to the same sequence, which is what
we really want to detect. That's what the attached patch does and what
I'm going to test.

Attachment: patch.txt
Description: Text document