2011-07-19 François Dumont <francois.cppdevs@free.fr>

        * include/debug/safe_unordered_base.h, safe_unordered_sequence.h,
        safe_unordered_sequence.tcc, safe_local_iterator.h,
        safe_local_iterator.tcc: New, support for unordered sequence safe
        local iterators.
        * include/Makefile.am: Add previous files.
        * include/Makefile.in: Regenerate.
        * include/debug/unordered_map, unordered_set: Implement
        _Safe_unordered_sequence and expose _Safe_local_iterator.
        * include/debug/safe_iterator.h, safe_iterator.tcc: Refactor
        _Safe_iterator::_M_get_distance static method to expose it as
        __get_distance function and use it in _Safe_local_iterator type.
        * include/debug/formatter.h: Add __msg_local_iter_compare_bad
        _Debug_msg_id enum entry to notify invalid comparison between local
        iterators from different buckets. Add _Parameter constructor from
        _Safe_local_iterator.
        * include/debug/functions.h: Add __valid_range overload for
        _Safe_local_iterator.
        * src/debug.cc: Add _Safe_unordered_sequence_base and
        _Safe_local_iterator_base methods implementations.
        * config/abi/pre/gnu.ver: Add export of some
        _Safe_unordered_sequence_base and _Safe_local_iterator_base methods.
        * testsuite/util/debug/checks.h: Add use_invalid_iterator function to
        simulate use of a singular iterator.
        * testsuite/util/debug/unordered_checks.h: New, several functions
        to simulate classic invalid usage of unordered sequence local
        iterators.
        * testsuite/23_containers/unordered_map/debug/
        use_erased_local_iterator_neg.cc, invalid_local_iterator_range_neg.cc,
        use_invalid_local_iterator_neg.cc, use_invalid_iterator_neg.cc,
        invalid_local_iterator_compare_neg.cc: New.
        * testsuite/23_containers/unordered_multimap/debug/
        use_erased_local_iterator_neg.cc, invalid_local_iterator_range_neg.cc,
        use_invalid_local_iterator_neg.cc, use_invalid_iterator_neg.cc,
        invalid_local_iterator_compare_neg.cc: New.
        * testsuite/23_containers/unordered_set/debug/
        use_erased_local_iterator_neg.cc, invalid_local_iterator_range_neg.cc,
        use_invalid_local_iterator_neg.cc, use_invalid_iterator_neg.cc,
        invalid_local_iterator_compare_neg.cc: New.
        * testsuite/23_containers/unordered_multiset/debug/
        use_erased_local_iterator_neg.cc, invalid_local_iterator_range_neg.cc,
        use_invalid_local_iterator_neg.cc, use_invalid_iterator_neg.cc,
        invalid_local_iterator_compare_neg.cc: New.


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

1 files changed, 240 insertions, 60 deletions

diff --git a/libstdc++-v3/include/debug/unordered_map b/libstdc++-v3/include/debug/unordered_map
index 4f087b75992..93ce517b1f7 100644
--- a/libstdc++-v3/include/debug/unordered_map
+++ b/libstdc++-v3/include/debug/unordered_map
@@ -35,8 +35,9 @@
 #else
 # include <unordered_map>
 
-#include <debug/safe_sequence.h>
+#include <debug/safe_unordered_sequence.h>
 #include <debug/safe_iterator.h>
+#include <debug/safe_local_iterator.h>
 
 namespace std _GLIBCXX_VISIBILITY(default)
 {
@@ -49,15 +50,16 @@ namespace __debug
 	   typename _Alloc = std::allocator<_Key> >
     class unordered_map
     : public _GLIBCXX_STD_C::unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>,
-      public __gnu_debug::_Safe_sequence<unordered_map<_Key, _Tp, _Hash,
-						       _Pred, _Alloc> >
+      public __gnu_debug::_Safe_unordered_sequence<unordered_map<_Key, _Tp,
+							_Hash, _Pred, _Alloc> >
     {
       typedef _GLIBCXX_STD_C::unordered_map<_Key, _Tp, _Hash,
 					    _Pred, _Alloc> _Base;
-      typedef __gnu_debug::_Safe_sequence<unordered_map> _Safe_base;
+      typedef __gnu_debug::_Safe_unordered_sequence<unordered_map> _Safe_base;
       typedef typename _Base::const_iterator _Base_const_iterator;
       typedef typename _Base::iterator _Base_iterator;
-      typedef __gnu_debug::_Equal_to<_Base_const_iterator> _Equal;
+      typedef typename _Base::const_local_iterator _Base_const_local_iterator;
+      typedef typename _Base::local_iterator _Base_local_iterator;
 
     public:
       typedef typename _Base::size_type       size_type;
@@ -72,6 +74,10 @@ namespace __debug
 					  unordered_map> iterator;
       typedef __gnu_debug::_Safe_iterator<_Base_const_iterator,
 					  unordered_map> const_iterator;
+      typedef __gnu_debug::_Safe_local_iterator<_Base_local_iterator,
+					  unordered_map> local_iterator;
+      typedef __gnu_debug::_Safe_local_iterator<_Base_const_local_iterator,
+					  unordered_map> const_local_iterator;
 
       explicit
       unordered_map(size_type __n = 10,
@@ -81,7 +87,7 @@ namespace __debug
       : _Base(__n, __hf, __eql, __a) { }
 
       template<typename _InputIterator>
-        unordered_map(_InputIterator __first, _InputIterator __last, 
+	unordered_map(_InputIterator __first, _InputIterator __last, 
 		      size_type __n = 0,
 		      const hasher& __hf = hasher(), 
 		      const key_equal& __eql = key_equal(), 
@@ -176,15 +182,36 @@ namespace __debug
       { return const_iterator(_Base::end(), this); }
 
       // local versions
-      using _Base::begin;
-      using _Base::end;
-      using _Base::cbegin;
-      using _Base::cend;
+      local_iterator
+      begin(size_type __b)
+      { return local_iterator(_Base::begin(__b), __b, this); }
+
+      local_iterator
+      end(size_type __b)
+      { return local_iterator(_Base::end(__b), __b, this); }
+
+      const_local_iterator
+      begin(size_type __b) const
+      { return const_local_iterator(_Base::begin(__b), __b, this); }
+
+      const_local_iterator
+      end(size_type __b) const
+      { return const_local_iterator(_Base::end(__b), __b, this); }
+
+      const_local_iterator
+      cbegin(size_type __b) const
+      { return const_local_iterator(_Base::cbegin(__b), __b, this); }
+
+      const_local_iterator
+      cend(size_type __b) const
+      { return const_local_iterator(_Base::cend(__b), __b, this); }
 
       std::pair<iterator, bool>
       insert(const value_type& __obj)
       {
+	size_type __bucket_count = this->bucket_count();
 	std::pair<_Base_iterator, bool> __res = _Base::insert(__obj);
+	_M_check_rehashed(__bucket_count);
 	return std::make_pair(iterator(__res.first, this), __res.second);
       }
 
@@ -192,43 +219,56 @@ namespace __debug
       insert(const_iterator __hint, const value_type& __obj)
       {
 	__glibcxx_check_insert(__hint);
-	return iterator(_Base::insert(__hint.base(), __obj), this);
+	size_type __bucket_count = this->bucket_count();
+	_Base_iterator __it = _Base::insert(__hint.base(), __obj); 
+	_M_check_rehashed(__bucket_count);
+	return iterator(__it, this);
       }
 
       template<typename _Pair, typename = typename
 	       std::enable_if<std::is_convertible<_Pair,
 						  value_type>::value>::type>
-        std::pair<iterator, bool>
-        insert(_Pair&& __obj)
-        {
+	std::pair<iterator, bool>
+	insert(_Pair&& __obj)
+	{
+	  size_type __bucket_count = this->bucket_count();
 	  std::pair<_Base_iterator, bool> __res =
 	    _Base::insert(std::forward<_Pair>(__obj));
+	  _M_check_rehashed(__bucket_count);
 	  return std::make_pair(iterator(__res.first, this), __res.second);
 	}
 
       template<typename _Pair, typename = typename
 	       std::enable_if<std::is_convertible<_Pair,
 						  value_type>::value>::type>
-        iterator
-        insert(const_iterator __hint, _Pair&& __obj)
-        {
+	iterator
+	insert(const_iterator __hint, _Pair&& __obj)
+	{
 	  __glibcxx_check_insert(__hint);
-	  return iterator(_Base::insert(__hint.base(),
-					std::forward<_Pair>(__obj)),
-			  this);
+	  size_type __bucket_count = this->bucket_count();
+	  _Base_iterator __it =
+	    _Base::insert(__hint.base(), std::forward<_Pair>(__obj));
+	  _M_check_rehashed(__bucket_count);
+	  return iterator(__it, this);
 	}
 
       void
       insert(std::initializer_list<value_type> __l)
-      { _Base::insert(__l); }
+      {
+	size_type __bucket_count = this->bucket_count();
+	_Base::insert(__l);
+	_M_check_rehashed(__bucket_count);
+      }
 
       template<typename _InputIterator>
-        void
-        insert(_InputIterator __first, _InputIterator __last)
-        {
+	void
+	insert(_InputIterator __first, _InputIterator __last)
+	{
 	  __glibcxx_check_valid_range(__first, __last);
+	  size_type __bucket_count = this->bucket_count();
 	  _Base::insert(__gnu_debug::__base(__first),
 			__gnu_debug::__base(__last));
+	  _M_check_rehashed(__bucket_count);
 	}
 
       iterator
@@ -264,8 +304,15 @@ namespace __debug
 	_Base_iterator __victim(_Base::find(__key));
 	if (__victim != _Base::end())
 	  {
-	    this->_M_invalidate_if(_Equal(__victim));
+	    this->_M_invalidate_if([__victim](_Base_const_iterator __it)
+			    { return __it == __victim; });
+	    _Base_local_iterator __local_victim = _S_to_local(__victim);
+	    this->_M_invalidate_local_if(
+			    [__local_victim](_Base_const_local_iterator __it)
+			    { return __it == __local_victim; });
+	    size_type __bucket_count = this->bucket_count();
 	    _Base::erase(__victim);
+	    _M_check_rehashed(__bucket_count);
 	    __ret = 1;
 	  }
 	return __ret;
@@ -275,8 +322,17 @@ namespace __debug
       erase(const_iterator __it)
       {
 	__glibcxx_check_erase(__it);
-	this->_M_invalidate_if(_Equal(__it.base()));
-	return iterator(_Base::erase(__it.base()), this);
+	_Base_const_iterator __victim = __it.base();
+	this->_M_invalidate_if([__victim](_Base_const_iterator __it)
+			{ return __it == __victim; });
+	_Base_const_local_iterator __local_victim = _S_to_local(__victim);
+	this->_M_invalidate_local_if(
+			[__local_victim](_Base_const_local_iterator __it)
+			{ return __it == __local_victim; });
+	size_type __bucket_count = this->bucket_count();
+	_Base_iterator __next = _Base::erase(__it.base()); 
+	_M_check_rehashed(__bucket_count);
+	return iterator(__next, this);
       }
 
       iterator
@@ -290,10 +346,17 @@ namespace __debug
 				  _M_message(__gnu_debug::__msg_valid_range)
 				  ._M_iterator(__first, "first")
 				  ._M_iterator(__last, "last"));
-	    this->_M_invalidate_if(_Equal(__tmp));
+	    this->_M_invalidate_if([__tmp](_Base_const_iterator __it)
+			    { return __it == __tmp; });
+	    _Base_const_local_iterator __local_tmp = _S_to_local(__tmp);
+	    this->_M_invalidate_local_if(
+			    [__local_tmp](_Base_const_local_iterator __it)
+			    { return __it == __local_tmp; });
 	  }
-	return iterator(_Base::erase(__first.base(),
-				     __last.base()), this);
+	size_type __bucket_count = this->bucket_count();
+	_Base_iterator __next = _Base::erase(__first.base(), __last.base());
+	_M_check_rehashed(__bucket_count);
+	return iterator(__next, this);
       }
 
       _Base&
@@ -304,11 +367,37 @@ namespace __debug
 
     private:
       void
+      _M_invalidate_locals()
+      {
+	_Base_local_iterator __local_end = _Base::end(0);
+	this->_M_invalidate_local_if(
+			[__local_end](_Base_const_local_iterator __it)
+			{ return __it != __local_end; });
+      }
+
+      void
       _M_invalidate_all()
       {
-	typedef __gnu_debug::_Not_equal_to<_Base_const_iterator> _Not_equal;
-	this->_M_invalidate_if(_Not_equal(_Base::end()));
+	_Base_iterator __end = _Base::end();
+	this->_M_invalidate_if([__end](_Base_const_iterator __it)
+			{ return __it != __end; });
+	_M_invalidate_locals();
       }
+
+      void
+      _M_check_rehashed(size_type __prev_count)
+      {
+	if (__prev_count != this->bucket_count())
+	  _M_invalidate_locals();
+      }
+
+      static _Base_local_iterator
+      _S_to_local(_Base_iterator __it)
+      { return _Base_local_iterator(__it._M_cur_node); }
+
+      static _Base_const_local_iterator
+      _S_to_local(_Base_const_iterator __it)
+      { return _Base_const_local_iterator(__it._M_cur_node); }
     };
 
   template<typename _Key, typename _Tp, typename _Hash,
@@ -341,15 +430,17 @@ namespace __debug
     class unordered_multimap
     : public _GLIBCXX_STD_C::unordered_multimap<_Key, _Tp, _Hash,
 						_Pred, _Alloc>,
-      public __gnu_debug::_Safe_sequence<unordered_multimap<_Key, _Tp, _Hash,
-							    _Pred, _Alloc> >
+      public __gnu_debug::_Safe_unordered_sequence<unordered_multimap<_Key,
+						_Tp, _Hash, _Pred, _Alloc> >
     {
       typedef _GLIBCXX_STD_C::unordered_multimap<_Key, _Tp, _Hash,
 						 _Pred, _Alloc> _Base;
-      typedef __gnu_debug::_Safe_sequence<unordered_multimap> _Safe_base;
+      typedef __gnu_debug::_Safe_unordered_sequence<unordered_multimap>
+	_Safe_base;
       typedef typename _Base::const_iterator _Base_const_iterator;
       typedef typename _Base::iterator _Base_iterator;
-      typedef __gnu_debug::_Equal_to<_Base_const_iterator> _Equal;
+      typedef typename _Base::const_local_iterator _Base_const_local_iterator;
+      typedef typename _Base::local_iterator _Base_local_iterator;
 
     public:
       typedef typename _Base::size_type       size_type;
@@ -364,6 +455,10 @@ namespace __debug
 					  unordered_multimap> iterator;
       typedef __gnu_debug::_Safe_iterator<_Base_const_iterator,
 					  unordered_multimap> const_iterator;
+      typedef __gnu_debug::_Safe_local_iterator<
+	_Base_local_iterator, unordered_multimap> local_iterator;
+      typedef __gnu_debug::_Safe_local_iterator<
+	_Base_const_local_iterator, unordered_multimap> const_local_iterator;
 
       explicit
       unordered_multimap(size_type __n = 10,
@@ -373,7 +468,7 @@ namespace __debug
       : _Base(__n, __hf, __eql, __a) { }
 
       template<typename _InputIterator>
-        unordered_multimap(_InputIterator __first, _InputIterator __last, 
+	unordered_multimap(_InputIterator __first, _InputIterator __last, 
 			   size_type __n = 0,
 			   const hasher& __hf = hasher(), 
 			   const key_equal& __eql = key_equal(), 
@@ -468,28 +563,60 @@ namespace __debug
       { return const_iterator(_Base::end(), this); }
 
       // local versions
-      using _Base::begin;
-      using _Base::end;
-      using _Base::cbegin;
-      using _Base::cend;
+      local_iterator
+      begin(size_type __b)
+      { return local_iterator(_Base::begin(__b), __b, this); }
+
+      local_iterator
+      end(size_type __b)
+      { return local_iterator(_Base::end(__b), __b, this); }
+
+      const_local_iterator
+      begin(size_type __b) const
+      { return const_local_iterator(_Base::begin(__b), __b, this); }
+
+      const_local_iterator
+      end(size_type __b) const
+      { return const_local_iterator(_Base::end(__b), __b, this); }
+
+      const_local_iterator
+      cbegin(size_type __b) const
+      { return const_local_iterator(_Base::cbegin(__b), __b, this); }
+
+      const_local_iterator
+      cend(size_type __b) const
+      { return const_local_iterator(_Base::cend(__b), __b, this); }
 
       iterator
       insert(const value_type& __obj)
-      { return iterator(_Base::insert(__obj), this); }
+      {
+	size_type __bucket_count = this->bucket_count();
+	_Base_iterator __it = _Base::insert(__obj);
+	_M_check_rehashed(__bucket_count);
+	return iterator(__it, this);
+      }
 
       iterator
       insert(const_iterator __hint, const value_type& __obj)
       {
 	__glibcxx_check_insert(__hint);
-	return iterator(_Base::insert(__hint.base(), __obj), this);
+	size_type __bucket_count = this->bucket_count();
+	_Base_iterator __it = _Base::insert(__hint.base(), __obj);
+	_M_check_rehashed(__bucket_count);
+	return iterator(__it, this);
       }
 
       template<typename _Pair, typename = typename
 	       std::enable_if<std::is_convertible<_Pair,
 						  value_type>::value>::type>
-        iterator
-        insert(_Pair&& __obj)
-        { return iterator(_Base::insert(std::forward<_Pair>(__obj)), this); }
+	iterator
+	insert(_Pair&& __obj)
+	{
+	  size_type __bucket_count = this->bucket_count();
+	  _Base_iterator __it = _Base::insert(std::forward<_Pair>(__obj));
+	  _M_check_rehashed(__bucket_count);
+	  return iterator(__it, this);
+	}
 
       template<typename _Pair, typename = typename
 	       std::enable_if<std::is_convertible<_Pair,
@@ -498,9 +625,11 @@ namespace __debug
 	insert(const_iterator __hint, _Pair&& __obj)
 	{
 	  __glibcxx_check_insert(__hint);
-	  return iterator(_Base::insert(__hint.base(),
-					std::forward<_Pair>(__obj)),
-			  this);
+	  size_type __bucket_count = this->bucket_count();
+	  _Base_iterator __it =
+	    _Base::insert(__hint.base(), std::forward<_Pair>(__obj));
+	  _M_check_rehashed(__bucket_count);
+	  return iterator(__it, this);
 	}
 
       void
@@ -508,12 +637,14 @@ namespace __debug
       { _Base::insert(__l); }
 
       template<typename _InputIterator>
-        void
-        insert(_InputIterator __first, _InputIterator __last)
-        {
+	void
+	insert(_InputIterator __first, _InputIterator __last)
+	{
 	  __glibcxx_check_valid_range(__first, __last);
+	  size_type __bucket_count = this->bucket_count();
 	  _Base::insert(__gnu_debug::__base(__first),
 			__gnu_debug::__base(__last));
+	  _M_check_rehashed(__bucket_count);
 	}
 
       iterator
@@ -546,14 +677,21 @@ namespace __debug
       erase(const key_type& __key)
       {
 	size_type __ret(0);
+	size_type __bucket_count = this->bucket_count();
 	std::pair<_Base_iterator, _Base_iterator> __pair =
 	  _Base::equal_range(__key);
 	for (_Base_iterator __victim = __pair.first; __victim != __pair.second;)
 	  {
-	    this->_M_invalidate_if(_Equal(__victim));
+	    this->_M_invalidate_if([__victim](_Base_const_iterator __it)
+			    { return __it == __victim; });
+	    _Base_local_iterator __local_victim = _S_to_local(__victim);
+	    this->_M_invalidate_local_if(
+			    [__local_victim](_Base_const_local_iterator __it)
+			    { return __it == __local_victim; });
 	    _Base::erase(__victim++);
 	    ++__ret;
 	  }
+	_M_check_rehashed(__bucket_count);
 	return __ret;
       }
 
@@ -561,8 +699,17 @@ namespace __debug
       erase(const_iterator __it)
       {
 	__glibcxx_check_erase(__it);
-	this->_M_invalidate_if(_Equal(__it.base()));
-	return iterator(_Base::erase(__it.base()), this);
+	_Base_const_iterator __victim = __it.base();
+	this->_M_invalidate_if([__victim](_Base_const_iterator __it)
+			{ return __it == __victim; });
+	_Base_const_local_iterator __local_victim = _S_to_local(__victim);
+	this->_M_invalidate_local_if(
+			[__local_victim](_Base_const_local_iterator __it)
+			{ return __it == __local_victim; });
+	size_type __bucket_count = this->bucket_count();
+	_Base_iterator __next = _Base::erase(__it.base());
+	_M_check_rehashed(__bucket_count);
+	return iterator(__next, this);
       }
 
       iterator
@@ -576,10 +723,17 @@ namespace __debug
 				  _M_message(__gnu_debug::__msg_valid_range)
 				  ._M_iterator(__first, "first")
 				  ._M_iterator(__last, "last"));
-	    this->_M_invalidate_if(_Equal(__tmp));
+	    this->_M_invalidate_if([__tmp](_Base_const_iterator __it)
+			    { return __it == __tmp; });
+	    _Base_const_local_iterator __local_tmp = _S_to_local(__tmp);
+	    this->_M_invalidate_local_if(
+			    [__local_tmp](_Base_const_local_iterator __it)
+			    { return __it == __local_tmp; });
 	  }
-	return iterator(_Base::erase(__first.base(),
-				     __last.base()), this);
+	size_type __bucket_count = this->bucket_count();
+	_Base_iterator __next = _Base::erase(__first.base(), __last.base());
+	_M_check_rehashed(__bucket_count);
+	return iterator(__next, this);
       }
 
       _Base&
@@ -590,11 +744,37 @@ namespace __debug
 
     private:
       void
+      _M_invalidate_locals()
+      {
+	_Base_local_iterator __local_end = _Base::end(0);
+	this->_M_invalidate_local_if(
+			[__local_end](_Base_const_local_iterator __it)
+			{ return __it != __local_end; });
+      }
+
+      void
       _M_invalidate_all()
       {
-	typedef __gnu_debug::_Not_equal_to<_Base_const_iterator> _Not_equal;
-	this->_M_invalidate_if(_Not_equal(_Base::end()));
+	_Base_iterator __end = _Base::end();
+	this->_M_invalidate_if([__end](_Base_const_iterator __it)
+			{ return __it != __end; });
+	_M_invalidate_locals();
       }
+
+      void
+      _M_check_rehashed(size_type __prev_count)
+      {
+	if (__prev_count != this->bucket_count())
+	  _M_invalidate_locals();
+      }
+
+      static _Base_local_iterator
+      _S_to_local(_Base_iterator __it)
+      { return _Base_local_iterator(__it._M_cur_node); }
+
+      static _Base_const_local_iterator
+      _S_to_local(_Base_const_iterator __it)
+      { return _Base_const_local_iterator(__it._M_cur_node); }
     };
 
   template<typename _Key, typename _Tp, typename _Hash,