re PR libstdc++/31370 (resizing bugs in std::vector<bool>)

2007-04-02  Matthew Levine  <gcc@severeweblint.org>
	    Paolo Carlini  <pcarlini@suse.de>

	PR libstdc++/31370
	* include/bits/stl_bvector.h (vector<bool>::max_size): Fix.
	(vector<bool>::_M_check_len): Add.
	* include/bits/vector.tcc (_M_fill_insert(iterator, size_type, bool),
	_M_insert_range(iterator, _ForwardIterator, _ForwardIterator,
	std::forward_iterator_tag), _M_insert_aux(iterator, bool)): Use it.
	* testsuite/23_containers/vector/bool/modifiers/insert/31370.cc: New.
	* testsuite/23_containers/vector/bool/capacity/29134.cc: Adjust.

	* include/bits/stl_vector.h (vector<>::_M_check_len): Add.
	* include/bits/vector.tcc (_M_insert_aux(iterator, const _Tp&),
	_M_fill_insert(iterator, size_type, const value_type&),
	_M_range_insert(iterator, _ForwardIterator, _ForwardIterator,
	std::forward_iterator_tag)): Use it.

Co-Authored-By: Paolo Carlini <pcarlini@suse.de>

From-SVN: r123424

6 files changed, 253 insertions, 37 deletions

diff --git a/libstdc++-v3/ChangeLog b/libstdc++-v3/ChangeLog
index 2007552..c59cfcd 100644
--- a/libstdc++-v3/ChangeLog
+++ b/libstdc++-v3/ChangeLog
@@ -1,3 +1,21 @@
+2007-04-02  Matthew Levine  <gcc@severeweblint.org>
+	    Paolo Carlini  <pcarlini@suse.de>
+
+	PR libstdc++/31370
+	* include/bits/stl_bvector.h (vector<bool>::max_size): Fix.
+	(vector<bool>::_M_check_len): Add.
+	* include/bits/vector.tcc (_M_fill_insert(iterator, size_type, bool),
+	_M_insert_range(iterator, _ForwardIterator, _ForwardIterator,
+	std::forward_iterator_tag), _M_insert_aux(iterator, bool)): Use it.
+	* testsuite/23_containers/vector/bool/modifiers/insert/31370.cc: New.
+	* testsuite/23_containers/vector/bool/capacity/29134.cc: Adjust.
+
+	* include/bits/stl_vector.h (vector<>::_M_check_len): Add.
+	* include/bits/vector.tcc (_M_insert_aux(iterator, const _Tp&),
+	_M_fill_insert(iterator, size_type, const value_type&),
+	_M_range_insert(iterator, _ForwardIterator, _ForwardIterator,
+	std::forward_iterator_tag)): Use it.
+
 2007-04-02  Paolo Carlini  <pcarlini@suse.de>
 
 	PR libstdc++/31401 (vstring bits)
diff --git a/libstdc++-v3/include/bits/stl_bvector.h b/libstdc++-v3/include/bits/stl_bvector.h
index 6f24154..d9863e0 100644
--- a/libstdc++-v3/include/bits/stl_bvector.h
+++ b/libstdc++-v3/include/bits/stl_bvector.h
@@ -582,9 +582,11 @@ template<typename _Alloc>
     size_type
     max_size() const
     {
+      const size_type __isize =
+	std::numeric_limits<difference_type>::max() - int(_S_word_bit) + 1;
       const size_type __asize = _M_get_Bit_allocator().max_size();
-      return (__asize <= size_type(-1) / int(_S_word_bit) ?
-	      __asize * int(_S_word_bit) : size_type(-1));
+      return (__asize <= __isize / int(_S_word_bit)
+	      ? __asize * int(_S_word_bit) : __isize);
     }
 
     size_type
@@ -922,6 +924,16 @@ template<typename _Alloc>
     void
     _M_insert_aux(iterator __position, bool __x);
 
+    size_type
+    _M_check_len(size_type __n, const char* __s) const
+    {
+      if (max_size() - size() < __n)
+	__throw_length_error(__N(__s));
+
+      const size_type __len = size() + std::max(size(), __n);
+      return (__len < size() || __len > max_size()) ? max_size() : __len;
+    }
+
     void
     _M_erase_at_end(iterator __pos)
     { this->_M_impl._M_finish = __pos; }
diff --git a/libstdc++-v3/include/bits/stl_vector.h b/libstdc++-v3/include/bits/stl_vector.h
index a81c597..f2c4b4b 100644
--- a/libstdc++-v3/include/bits/stl_vector.h
+++ b/libstdc++-v3/include/bits/stl_vector.h
@@ -911,6 +911,17 @@ _GLIBCXX_BEGIN_NESTED_NAMESPACE(std, _GLIBCXX_STD)
       void
       _M_insert_aux(iterator __position, const value_type& __x);
 
+      // Called by the latter.
+      size_type
+      _M_check_len(size_type __n, const char* __s) const
+      {
+	if (max_size() - size() < __n)
+	  __throw_length_error(__N(__s));
+
+	const size_type __len = size() + std::max(size(), __n);
+	return (__len < size() || __len > max_size()) ? max_size() : __len;
+      }
+
       // Internal erase functions follow.
 
       // Called by erase(q1,q2), clear(), resize(), _M_fill_assign,
diff --git a/libstdc++-v3/include/bits/vector.tcc b/libstdc++-v3/include/bits/vector.tcc
index 9b416be..09266a2 100644
--- a/libstdc++-v3/include/bits/vector.tcc
+++ b/libstdc++-v3/include/bits/vector.tcc
@@ -258,17 +258,8 @@ _GLIBCXX_BEGIN_NESTED_NAMESPACE(std, _GLIBCXX_STD)
 	}
       else
 	{
-	  const size_type __old_size = size();
-	  if (__old_size == this->max_size())
-	    __throw_length_error(__N("vector::_M_insert_aux"));
-
-	  // When sizeof(value_type) == 1 and __old_size > size_type(-1)/2
-	  // __len overflows: if we don't notice and _M_allocate doesn't
-	  // throw we crash badly later.
-	  size_type __len = __old_size != 0 ? 2 * __old_size : 1;	  
-	  if (__len < __old_size)
-	    __len = this->max_size();
-
+	  const size_type __len =
+	    _M_check_len(size_type(1), "vector::_M_insert_aux");
 	  pointer __new_start(this->_M_allocate(__len));
 	  pointer __new_finish(__new_start);
 	  try
@@ -343,15 +334,8 @@ _GLIBCXX_BEGIN_NESTED_NAMESPACE(std, _GLIBCXX_STD)
 	    }
 	  else
 	    {
-	      const size_type __old_size = size();
-	      if (this->max_size() - __old_size < __n)
-		__throw_length_error(__N("vector::_M_fill_insert"));
-	      
-	      // See _M_insert_aux above.
-	      size_type __len = __old_size + std::max(__old_size, __n);
-	      if (__len < __old_size)
-		__len = this->max_size();
-
+	      const size_type __len =
+		_M_check_len(__n, "vector::_M_fill_insert");
 	      pointer __new_start(this->_M_allocate(__len));
 	      pointer __new_finish(__new_start);
 	      try
@@ -447,15 +431,8 @@ _GLIBCXX_BEGIN_NESTED_NAMESPACE(std, _GLIBCXX_STD)
 	      }
 	    else
 	      {
-		const size_type __old_size = size();
-		if (this->max_size() - __old_size < __n)
-		  __throw_length_error(__N("vector::_M_range_insert"));	
-
-		// See _M_insert_aux above.
-		size_type __len = __old_size + std::max(__old_size, __n);
-		if (__len < __old_size)
-		  __len = this->max_size();
-
+		const size_type __len =
+		  _M_check_len(__n, "vector::_M_range_insert");
 		pointer __new_start(this->_M_allocate(__len));
 		pointer __new_finish(__new_start);
 		try
@@ -512,7 +489,8 @@ _GLIBCXX_BEGIN_NESTED_NAMESPACE(std, _GLIBCXX_STD)
 	}
       else
 	{
-	  const size_type __len = size() + std::max(size(), __n);
+	  const size_type __len = 
+	    _M_check_len(__n, "vector<bool>::_M_fill_insert");
 	  _Bit_type * __q = this->_M_allocate(__len);
 	  iterator __i = _M_copy_aligned(begin(), __position,
 					 iterator(__q, 0));
@@ -547,7 +525,8 @@ _GLIBCXX_BEGIN_NESTED_NAMESPACE(std, _GLIBCXX_STD)
 	      }
 	    else
 	      {
-		const size_type __len = size() + std::max(size(), __n);
+		const size_type __len =
+		  _M_check_len(__n, "vector<bool>::_M_insert_range");
 		_Bit_type * __q = this->_M_allocate(__len);
 		iterator __i = _M_copy_aligned(begin(), __position,
 					       iterator(__q, 0));
@@ -577,8 +556,8 @@ _GLIBCXX_BEGIN_NESTED_NAMESPACE(std, _GLIBCXX_STD)
 	}
       else
 	{
-	  const size_type __len = size() ? 2 * size()
-	                                 : static_cast<size_type>(_S_word_bit);
+	  const size_type __len =
+	    _M_check_len(size_type(1), "vector<bool>::_M_insert_aux");
 	  _Bit_type * __q = this->_M_allocate(__len);
 	  iterator __i = _M_copy_aligned(begin(), __position,
 					 iterator(__q, 0));
diff --git a/libstdc++-v3/testsuite/23_containers/vector/bool/capacity/29134.cc b/libstdc++-v3/testsuite/23_containers/vector/bool/capacity/29134.cc
index 4290c86..69e5a53 100644
--- a/libstdc++-v3/testsuite/23_containers/vector/bool/capacity/29134.cc
+++ b/libstdc++-v3/testsuite/23_containers/vector/bool/capacity/29134.cc
@@ -1,4 +1,4 @@
-// Copyright (C) 2006 Free Software Foundation, Inc.
+// Copyright (C) 2006, 2007 Free Software Foundation, Inc.
 //
 // This file is part of the GNU ISO C++ Library.  This library is free
 // software; you can redistribute it and/or modify it under the
@@ -28,7 +28,11 @@ void test01()
 
   std::vector<bool> vb;
 
-  VERIFY( vb.max_size() == std::vector<bool>::size_type(-1) );
+  // Actually, vector<bool> is special, see libstdc++/31370.
+  typedef std::vector<bool>::difference_type difference_type;
+  VERIFY( vb.max_size()
+	  == (std::numeric_limits<difference_type>::max()
+	      - int(std::_S_word_bit) + 1) );
 }
 
 int main()
diff --git a/libstdc++-v3/testsuite/23_containers/vector/bool/modifiers/insert/31370.cc b/libstdc++-v3/testsuite/23_containers/vector/bool/modifiers/insert/31370.cc
new file mode 100644
index 0000000..0c4d0a8
--- /dev/null
+++ b/libstdc++-v3/testsuite/23_containers/vector/bool/modifiers/insert/31370.cc
@@ -0,0 +1,192 @@
+// Copyright (C) 2007 Free Software Foundation, Inc.
+//
+// This file is part of the GNU ISO C++ Library.  This library is free
+// software; you can redistribute it and/or modify it under the
+// terms of the GNU General Public License as published by the
+// Free Software Foundation; either version 2, or (at your option)
+// any later version.
+
+// This library is distributed in the hope that it will be useful,
+// but WITHOUT ANY WARRANTY; without Pred the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+// GNU General Public License for more details.
+
+// You should have received a copy of the GNU General Public License along
+// with this library; see the file COPYING.  If not, write to the Free
+// Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301,
+// USA.
+
+// 23.2.5 class vector<bool> [lib.vector.bool]
+
+// { dg-do run { xfail *-*-darwin8.[0-4].* } }
+
+#include <vector>
+#include <stdexcept>
+#include <testsuite_hooks.h>
+
+inline void
+check_cap_ge_size(const std::vector<bool>& x)
+{
+  if (x.capacity() < x.size())
+    throw std::logic_error("");
+}
+
+inline void
+check_cap_eq_maxsize(const std::vector<bool>& x)
+{
+  if (x.capacity() != x.max_size())
+    throw std::logic_error("");
+}
+
+// libstdc++/31370
+void test01()
+{
+  bool test __attribute__((unused)) = true;
+  int myexit = 0;
+
+  try
+    {
+      std::vector<bool> x;
+      x.reserve(x.max_size());
+      check_cap_eq_maxsize(x);
+    }
+  catch(std::bad_alloc&)
+    { }
+  catch(std::exception&)
+    { ++myexit; }
+  
+  // When doubling is too big, but smaller is sufficient, the resize
+  // should do smaller and be happy.  It certainly shouldn't throw
+  // other exceptions or crash.
+  try
+    {
+      std::vector<bool> x;
+      x.resize(x.max_size() / 2 + 1, false); 
+      for(int i = 0; i < std::_S_word_bit; ++i)
+	x.push_back(false);
+      check_cap_ge_size(x);
+    }
+  catch(std::bad_alloc&)
+    { }
+  catch(std::exception&)
+    { ++myexit; }
+  
+  try
+    {
+      std::vector<bool> x;
+      x.resize(x.max_size() / 2 + 1, false); 
+      x.insert(x.end(), std::_S_word_bit, false);
+      check_cap_ge_size(x);
+    }
+  catch(std::bad_alloc&)
+    { }
+  catch(std::exception&)
+    { ++myexit; }
+  
+  try
+    {
+      std::vector<bool> x;
+      x.resize(x.max_size() / 2 + 1, false); 
+      std::vector<bool> y(std::_S_word_bit, false);
+      x.insert(x.end(), y.begin(), y.end());
+      check_cap_ge_size(x);
+    }
+  catch(std::bad_alloc&)
+    { }
+  catch(std::exception&)
+    { ++myexit; }
+
+  // These tests are currently only relevant to bool: don't get burned
+  // by the attempt to round up when near the max size.
+  try
+    {
+      std::vector<bool> x;
+      x.resize(x.max_size() - std::_S_word_bit, false); 
+      for(int i = 0; i < std::_S_word_bit; ++i)
+	x.push_back(false);
+      check_cap_ge_size(x);
+    }
+  catch(std::bad_alloc&)
+    { }
+  catch(std::exception&)
+    { ++myexit; }
+  
+  try
+    {
+      std::vector<bool> x;
+      x.resize(x.max_size() - std::_S_word_bit, false); 
+      x.insert(x.end(), std::_S_word_bit, false);
+      check_cap_ge_size(x);
+    }
+  catch(std::bad_alloc&)
+    { }
+  catch(std::exception&)
+    { ++myexit; }
+
+  try
+    {
+      std::vector<bool> x;
+      x.resize(x.max_size() - std::_S_word_bit, false); 
+      std::vector<bool> y(std::_S_word_bit, false);
+      x.insert(x.end(), y.begin(), y.end());
+      check_cap_ge_size(x);
+    }
+  catch(std::bad_alloc&)
+    { }
+  catch(std::exception&)
+    { ++myexit; }
+  
+  // Attempts to put in more than max_size() items should result in a
+  // length error.
+  try
+    {
+      std::vector<bool> x;
+      x.resize(x.max_size() - std::_S_word_bit, false); 
+      for(int i = 0; i < std::_S_word_bit + 1; ++i)
+	x.push_back(false);
+      ++myexit;
+    }
+  catch(std::bad_alloc)
+    { }
+  catch(std::length_error)
+    { }
+  catch(std::exception)
+    { ++myexit; }
+  
+  try
+    {
+      std::vector<bool> x;
+      x.resize(x.max_size() - std::_S_word_bit, false); 
+      x.insert(x.end(), std::_S_word_bit + 1, false);
+      ++myexit;
+    }
+  catch(std::bad_alloc)
+    { }
+  catch(std::length_error)
+    { }
+  catch(std::exception)
+    { ++myexit; }
+
+  try
+    {
+      std::vector<bool> x;
+      x.resize(x.max_size() - std::_S_word_bit, false); 
+      std::vector<bool> y(std::_S_word_bit + 1, false);
+      x.insert(x.end(), y.begin(), y.end());
+      ++myexit;
+    }
+  catch(std::bad_alloc)
+    { }
+  catch(std::length_error)
+    { }
+  catch(std::exception)
+    { ++myexit; }
+
+  VERIFY( !myexit );
+}
+
+int main()
+{
+  test01();
+  return 0;
+}