PR libstdc++/60587

[Jonathan Wakely]

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.


-------------- next part --------------
--- debug/functions.h.orig	2014-03-19 21:34:43.038647394 +0000
+++ debug/functions.h	2014-03-19 21:35:53.502617461 +0000
@@ -175,62 +175,6 @@
       return __first;
     }
 
-#if __cplusplus >= 201103L
-  // Default implementation.
-  template<typename _Iterator, typename _Sequence>
-    inline bool
-    __foreign_iterator_aux4(const _Safe_iterator<_Iterator, _Sequence>& __it,
-			    typename _Sequence::const_pointer __begin,
-			    typename _Sequence::const_pointer __other)
-    {
-      typedef typename _Sequence::const_pointer _PointerType;
-      constexpr std::less<_PointerType> __l{};
-
-      return (__l(__other, __begin)
-	      || __l(std::addressof(*(__it._M_get_sequence()->_M_base().end()
-				      - 1)), __other));
-    }
-
-  // Fallback when address type cannot be implicitely casted to sequence
-  // const_pointer.
-  template<typename _Iterator, typename _Sequence,
-	   typename _InputIterator>
-    inline bool
-    __foreign_iterator_aux4(const _Safe_iterator<_Iterator, _Sequence>&,
-			    _InputIterator, ...)
-    { return true; }
-
-  template<typename _Iterator, typename _Sequence, typename _InputIterator>
-    inline bool
-    __foreign_iterator_aux3(const _Safe_iterator<_Iterator, _Sequence>& __it,
-			    _InputIterator __other,
-			    std::true_type)
-    {
-      // Only containers with all elements in contiguous memory can have their
-      // elements passed through pointers.
-      // Arithmetics is here just to make sure we are not dereferencing
-      // past-the-end iterator.
-      if (__it._M_get_sequence()->_M_base().begin()
-	  != __it._M_get_sequence()->_M_base().end())
-	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)
-	  return (__foreign_iterator_aux4
-		  (__it,
-		   std::addressof(*(__it._M_get_sequence()->_M_base().begin())),
-		   std::addressof(*__other)));
-      return true;
-    }
-			   
-  /* Fallback overload for which we can't say, assume it is valid. */
-  template<typename _Iterator, typename _Sequence, typename _InputIterator>
-    inline bool
-    __foreign_iterator_aux3(const _Safe_iterator<_Iterator, _Sequence>& __it,
-			    _InputIterator __other,
-			    std::false_type)
-    { return true; }
-#endif
-
   /** Checks that iterators do not belong to the same sequence. */
   template<typename _Iterator, typename _Sequence, typename _OtherIterator>
     inline bool
@@ -238,29 +182,12 @@
 		const _Safe_iterator<_OtherIterator, _Sequence>& __other,
 		std::input_iterator_tag)
     { return __it._M_get_sequence() != __other._M_get_sequence(); }
-			   
-#if __cplusplus >= 201103L
-  /* This overload detects when passing pointers to the contained elements
-     rather than using iterators.
-   */
-  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)
-    {
-      typedef typename _Sequence::const_iterator _ItType;
-      typedef typename std::iterator_traits<_ItType>::reference _Ref;
-      return __foreign_iterator_aux3(__it, __other,
-				     std::is_lvalue_reference<_Ref>());
-    }
-#endif
-			   
+
   /* Fallback overload for which we can't say, assume it is valid. */
   template<typename _Iterator, typename _Sequence, typename _InputIterator>
     inline bool
     __foreign_iterator_aux2(const _Safe_iterator<_Iterator, _Sequence>&,
-			   _InputIterator,
+			   const _InputIterator&,
 			   std::input_iterator_tag)
     { return true; }