2013-08-01 François Dumont <fdumont@gcc.gnu.org>

	PR libstdc++/57779
	* include/debug/formatter.h (_Debug_msg_id): Add
	__msg_insert_itself_range entry.
	* include/debug/functions.h (_Insert_range_from_self_is_safe<>):
	New, indicate container types supporting self range insertion in
	GNU implementation.
	(__foreign_iterator): New, check if an iterator points to a given
	sequence.
	* include/debug/macros.h (__glibcxx_check_insert_range): Add check
	using __foreign_iterator.
	(__gibcxx_check_insert_range_after): Likewise.
	* include/debug/string (_Insert_range_from_self_is_safe<>):
	Partially specialized to mark __gnu_debug::basic_string<> as
	supporting self range insert.
	* include/debug/list (_Insert_range_from_self_is_safe<>):
	Partially specialized to mark std::list as supporting self range
	insert if _GLIBCXX_DEBUG_PEDANTIC is not defined.
	* include/debug/forward_list (_Insert_range_from_self_is_safe<>):
	Likewise.
	* src/c++11/debug.cc (_S_debug_messages): Add
	__msg_insert_itself_range_entry message.
	(_Error_formatter::_Parameter::_M_print_description): Display
	iterator sequence address rather than sequence address when the
	parameter type is an iterator.
	(_Error_formatter::_M_print_word): Enhance behavior when
	displaying a word with an appended '\n'.
	* testsuite/util/debug/checks.h (check_insert4<>): New.
	* testsuite/23_containers/deque/debug/insert5_neg.cc: New.
	* testsuite/23_containers/vector/debug/insert5_neg.cc: Likewise.
	* testsuite/23_containers/vector/debug/insert6_neg.cc: Likewise.
	* testsuite/23_containers/vector/debug/57779_neg.cc: Likewise.
	* testsuite/23_containers/list/debug/insert5_neg.cc: Likewise.
	* testsuite/23_containers/forward_list/debug/insert_after4_neg.cc:
	Likewise.


git-svn-id: svn+ssh://gcc.gnu.org/svn/gcc/trunk@201416 138bc75d-0d04-0410-961f-82ee72b054a4

6 files changed, 166 insertions, 12 deletions

diff --git a/libstdc++-v3/include/debug/formatter.h b/libstdc++-v3/include/debug/formatter.h
index 4c65e1ac4da..15dd8d73797 100644
--- a/libstdc++-v3/include/debug/formatter.h
+++ b/libstdc++-v3/include/debug/formatter.h
@@ -114,7 +114,9 @@ namespace __gnu_debug
     // unordered container buckets
     __msg_bucket_index_oob,
     __msg_valid_load_factor,
-    __msg_equal_allocs
+    // others
+    __msg_equal_allocs,
+    __msg_insert_range_from_self
   };
 
   class _Error_formatter
diff --git a/libstdc++-v3/include/debug/forward_list b/libstdc++-v3/include/debug/forward_list
index 90a2e9c3e65..4c8ac371c94 100644
--- a/libstdc++-v3/include/debug/forward_list
+++ b/libstdc++-v3/include/debug/forward_list
@@ -796,6 +796,13 @@ namespace __gnu_debug
       _S_Is_Beginnest(_BaseIt __it, const _Sequence* __seq)
       { return _S_Is(__it, __seq); }
     };
+
+#ifndef _GLIBCXX_DEBUG_PEDANTIC
+  template<class _Tp, class _Alloc>
+    struct _Insert_range_from_self_is_safe<
+      std::__debug::forward_list<_Tp, _Alloc> >
+      { enum { __value = 1 }; };
+#endif
 }
 
 #endif
diff --git a/libstdc++-v3/include/debug/functions.h b/libstdc++-v3/include/debug/functions.h
index 3f16098185c..87478c6fbc1 100644
--- a/libstdc++-v3/include/debug/functions.h
+++ b/libstdc++-v3/include/debug/functions.h
@@ -32,7 +32,11 @@
 #include <bits/c++config.h>
 #include <bits/stl_iterator_base_types.h> // for iterator_traits, categories and
 					  // _Iter_base
-#include <bits/cpp_type_traits.h>         // for __is_integer
+#include <bits/cpp_type_traits.h>	  // for __is_integer
+#if __cplusplus >= 201103L
+# include <bits/stl_function.h>		  // for less and greater_equal
+# include <type_traits>			  // for common_type
+#endif
 #include <debug/formatter.h>
 
 namespace __gnu_debug
@@ -40,6 +44,10 @@ namespace __gnu_debug
   template<typename _Iterator, typename _Sequence>
     class _Safe_iterator;
 
+  template<typename _Sequence>
+    struct _Insert_range_from_self_is_safe
+    { enum { __value = 0 }; };
+
   // An arbitrary iterator pointer is not singular.
   inline bool
   __check_singular_aux(const void*) { return false; }
@@ -162,6 +170,123 @@ namespace __gnu_debug
       return __first;
     }
 
+#if __cplusplus >= 201103L
+  template<typename _Iterator, typename _Sequence,
+	   typename _InputIterator,
+	   typename _PointerType1,
+	   typename _PointerType2>
+    inline bool
+    __foreign_iterator_aux4(const _Safe_iterator<_Iterator, _Sequence>& __it,
+			    _InputIterator __other,
+			    _PointerType1, _PointerType2)
+    {
+      typedef typename std::common_type<_PointerType1,
+					_PointerType2>::type _PointerType;
+      std::less<_PointerType> __l;
+      std::greater_equal<_PointerType> __ge;
+
+      return
+	__l(std::addressof(*__other),
+	    std::addressof(*(__it._M_get_sequence()->_M_base().begin())))
+	|| __ge(std::addressof(*__other),
+		std::addressof(*(__it._M_get_sequence()->_M_base().end() - 1)) + 1);
+      
+    }
+			  
+  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, __other,
+			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
+    __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(); }
+			   
+#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,
+			   std::input_iterator_tag)
+    { return true; }
+			   
+  template<typename _Iterator, typename _Sequence,
+	   typename _Integral>
+    inline bool
+    __foreign_iterator_aux(const _Safe_iterator<_Iterator, _Sequence>& __it,
+			   _Integral __other,
+			   std::__true_type)
+    { return true; }
+
+  template<typename _Iterator, typename _Sequence,
+	   typename _InputIterator>
+    inline bool
+    __foreign_iterator_aux(const _Safe_iterator<_Iterator, _Sequence>& __it,
+			   _InputIterator __other,
+			   std::__false_type)
+    {
+      return
+	_Insert_range_from_self_is_safe<_Sequence>::__value
+	|| __foreign_iterator_aux2(__it, __other,
+				   std::__iterator_category(__it));
+    }
+
+  template<typename _Iterator, typename _Sequence,
+	   typename _InputIterator>
+    inline bool
+    __foreign_iterator(const _Safe_iterator<_Iterator, _Sequence>& __it,
+		       _InputIterator __other)
+    {
+      typedef typename std::__is_integer<_InputIterator>::__type _Integral;
+      return __foreign_iterator_aux(__it, __other, _Integral());
+    }
+
   /** Checks that __s is non-NULL or __n == 0, and then returns __s. */
   template<typename _CharT, typename _Integer>
     inline const _CharT*
diff --git a/libstdc++-v3/include/debug/list b/libstdc++-v3/include/debug/list
index 1ae8507ca86..fd00b0148a9 100644
--- a/libstdc++-v3/include/debug/list
+++ b/libstdc++-v3/include/debug/list
@@ -791,4 +791,13 @@ namespace __debug
 } // namespace __debug
 } // namespace std
 
+#ifndef _GLIBCXX_DEBUG_PEDANTIC
+namespace __gnu_debug
+{
+  template<class _Tp, class _Alloc>
+    struct _Insert_range_from_self_is_safe<std::__debug::list<_Tp, _Alloc> >
+    { enum { __value = 1 }; };
+}
+#endif
+
 #endif
diff --git a/libstdc++-v3/include/debug/macros.h b/libstdc++-v3/include/debug/macros.h
index 26732c9e3e2..521e8c0fa47 100644
--- a/libstdc++-v3/include/debug/macros.h
+++ b/libstdc++-v3/include/debug/macros.h
@@ -72,11 +72,11 @@ _GLIBCXX_DEBUG_VERIFY(_First != _Last,					\
 */
 #define __glibcxx_check_insert(_Position)				\
 _GLIBCXX_DEBUG_VERIFY(!_Position._M_singular(),				\
-		      _M_message(__gnu_debug::__msg_insert_singular) \
+		      _M_message(__gnu_debug::__msg_insert_singular)	\
 		      ._M_sequence(*this, "this")			\
 		      ._M_iterator(_Position, #_Position));		\
 _GLIBCXX_DEBUG_VERIFY(_Position._M_attached_to(this),			\
-		      _M_message(__gnu_debug::__msg_insert_different) \
+		      _M_message(__gnu_debug::__msg_insert_different)	\
 		      ._M_sequence(*this, "this")			\
 		      ._M_iterator(_Position, #_Position))
 
@@ -101,15 +101,16 @@ _GLIBCXX_DEBUG_VERIFY(!_Position._M_is_end(),				\
  *  that it reference the sequence we are inserting into, and that the
  *  iterator range [_First, Last) is a valid (possibly empty)
  *  range. Note that this macro is only valid when the container is a
- *  _Safe_sequence and the iterator is a _Safe_iterator.
- *
- *  @todo We would like to be able to check for noninterference of
- *  _Position and the range [_First, _Last), but that can't (in
- *  general) be done.
+ *  _Safe_sequence and the _Position iterator is a _Safe_iterator.
 */
 #define __glibcxx_check_insert_range(_Position,_First,_Last)		\
 __glibcxx_check_valid_range(_First,_Last);				\
-__glibcxx_check_insert(_Position)
+__glibcxx_check_insert(_Position);					\
+_GLIBCXX_DEBUG_VERIFY(__gnu_debug::__foreign_iterator(_Position,_First),\
+		      _M_message(__gnu_debug::__msg_insert_range_from_self)\
+		      ._M_iterator(_First, #_First)			\
+		      ._M_iterator(_Last, #_Last)			\
+		      ._M_sequence(*this, "this"))
 
 /** Verify that we can insert the values in the iterator range
  *  [_First, _Last) into *this after the iterator _Position.  Insertion
@@ -126,7 +127,12 @@ __glibcxx_check_insert(_Position)
 */
 #define __glibcxx_check_insert_range_after(_Position,_First,_Last)	\
 __glibcxx_check_valid_range(_First,_Last);				\
-__glibcxx_check_insert_after(_Position)
+__glibcxx_check_insert_after(_Position);					\
+_GLIBCXX_DEBUG_VERIFY(__gnu_debug::__foreign_iterator(_Position,_First),\
+		      _M_message(__gnu_debug::__msg_insert_range_from_self)\
+		      ._M_iterator(_First, #_First)			\
+		      ._M_iterator(_Last, #_Last)			\
+		      ._M_sequence(*this, "this"))
 
 /** Verify that we can erase the element referenced by the iterator
  * _Position. We can erase the element if the _Position iterator is
@@ -332,7 +338,7 @@ _GLIBCXX_DEBUG_VERIFY(_F > 0.0f,					\
 		      _M_message(__gnu_debug::__msg_valid_load_factor)	\
                       ._M_sequence(*this, "this"))
 
-#define __glibcxx_check_equal_allocs(_Other)			\
+#define __glibcxx_check_equal_allocs(_Other)				\
 _GLIBCXX_DEBUG_VERIFY(this->get_allocator() == _Other.get_allocator(),	\
 		      _M_message(__gnu_debug::__msg_equal_allocs)	\
 		      ._M_sequence(*this, "this"))
diff --git a/libstdc++-v3/include/debug/string b/libstdc++-v3/include/debug/string
index 8a5bf9b0367..9e856c1ee8c 100644
--- a/libstdc++-v3/include/debug/string
+++ b/libstdc++-v3/include/debug/string
@@ -1156,6 +1156,11 @@ namespace __gnu_debug
   typedef basic_string<wchar_t> wstring;
 #endif
 
+  template<typename _CharT, typename _Traits, typename _Allocator>
+    struct _Insert_range_from_self_is_safe<
+      __gnu_debug::basic_string<_CharT, _Traits, _Allocator> >
+      { enum { __value = 1 }; };
+
 } // namespace __gnu_debug
 
 #endif