PR libstdc++/78448 limit vector::max_size and deque::max_size

The container requirements imply that max_size() can't exceed the
maximum value of the container's difference_type. Enforce this for
std::vector and std::deque, and add checks to ensure the container
doesn't grow larger than that.

	PR libstdc++/78448
	* include/bits/deque.tcc (deque::_M_range_initialize): Use
	_S_check_init_len to check size.
	(deque::_M_push_back_aux, deque::_M_push_front_aux): Throw length
	error if size would exceed max_size().
	* include/bits/stl_deque.h (_Deque_base::size_type): Remove typedef.
	(_Deque_base(_Deque_base&&, const allocator_type&, size_t)): Use
	size_t instead of size_type.
	(deq(size_type, const allocator_type&)
	(deq(size_type, const value_type&, const allocator_type&)
	(deque::_M_initialize_dispatch): Use _S_check_init_len to check size.
	(deque::max_size): Call _S_max_size.
	(deque::_S_check_init_len, deque::_S_max_size): New functions.
	* include/bits/stl_vector.h (vector(size_type, const allocator_type&))
	(vector(size_type, const value_type&, const allocator_type&))
	(vector::_M_initialize_dispatch, vector::_M_range_initialize): Use
	_S_check_init_len to check size.
	(vector::max_size): Call _S_max_size.
	(vector::_M_check_len): Prevent max from being expanded as a
	function-like macro.
	(vector::_S_check_init_len, vector::_S_max_size): New functions.
	* include/bits/vector.tcc (vector::_M_assign_aux): Use
	_S_check_init_len to check size.
	* testsuite/23_containers/deque/capacity/max_size.cc: New test.
	* testsuite/23_containers/vector/capacity/max_size.cc: New test.

From-SVN: r263789

7 files changed, 381 insertions, 15 deletions

diff --git a/libstdc++-v3/ChangeLog b/libstdc++-v3/ChangeLog
index 4639c5e..dfe3a52 100644
--- a/libstdc++-v3/ChangeLog
+++ b/libstdc++-v3/ChangeLog
@@ -1,3 +1,31 @@
+2018-08-22  Jonathan Wakely  <jwakely@redhat.com>
+
+	PR libstdc++/78448
+	* include/bits/deque.tcc (deque::_M_range_initialize): Use
+	_S_check_init_len to check size.
+	(deque::_M_push_back_aux, deque::_M_push_front_aux): Throw length
+	error if size would exceed max_size().
+	* include/bits/stl_deque.h (_Deque_base::size_type): Remove typedef.
+	(_Deque_base(_Deque_base&&, const allocator_type&, size_t)): Use
+	size_t instead of size_type.
+	(deq(size_type, const allocator_type&)
+	(deq(size_type, const value_type&, const allocator_type&)
+	(deque::_M_initialize_dispatch): Use _S_check_init_len to check size.
+	(deque::max_size): Call _S_max_size.
+	(deque::_S_check_init_len, deque::_S_max_size): New functions.
+	* include/bits/stl_vector.h (vector(size_type, const allocator_type&))
+	(vector(size_type, const value_type&, const allocator_type&))
+	(vector::_M_initialize_dispatch, vector::_M_range_initialize): Use
+	_S_check_init_len to check size.
+	(vector::max_size): Call _S_max_size.
+	(vector::_M_check_len): Prevent max from being expanded as a
+	function-like macro.
+	(vector::_S_check_init_len, vector::_S_max_size): New functions.
+	* include/bits/vector.tcc (vector::_M_assign_aux): Use
+	_S_check_init_len to check size.
+	* testsuite/23_containers/deque/capacity/max_size.cc: New test.
+	* testsuite/23_containers/vector/capacity/max_size.cc: New test.
+
 2018-08-22  François Dumont  <fdumont@gcc.gnu.org>
 
 	PR libstdc++/68222
diff --git a/libstdc++-v3/include/bits/deque.tcc b/libstdc++-v3/include/bits/deque.tcc
index 8724a19..a22948a 100644
--- a/libstdc++-v3/include/bits/deque.tcc
+++ b/libstdc++-v3/include/bits/deque.tcc
@@ -443,7 +443,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
                           std::forward_iterator_tag)
       {
         const size_type __n = std::distance(__first, __last);
-        this->_M_initialize_map(__n);
+        this->_M_initialize_map(_S_check_init_len(__n, _M_get_Tp_allocator()));
 
         _Map_pointer __cur_node;
         __try
@@ -484,6 +484,10 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
       _M_push_back_aux(const value_type& __t)
 #endif
       {
+	if (size() == max_size())
+	  __throw_length_error(
+	      __N("cannot create std::deque larger than max_size()"));
+
 	_M_reserve_map_at_back();
 	*(this->_M_impl._M_finish._M_node + 1) = this->_M_allocate_node();
 	__try
@@ -519,6 +523,10 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
       _M_push_front_aux(const value_type& __t)
 #endif
       {
+	if (size() == max_size())
+	  __throw_length_error(
+	      __N("cannot create std::deque larger than max_size()"));
+
 	_M_reserve_map_at_front();
 	*(this->_M_impl._M_start._M_node - 1) = this->_M_allocate_node();
 	__try
diff --git a/libstdc++-v3/include/bits/stl_deque.h b/libstdc++-v3/include/bits/stl_deque.h
index 58a01c8..555be16 100644
--- a/libstdc++-v3/include/bits/stl_deque.h
+++ b/libstdc++-v3/include/bits/stl_deque.h
@@ -493,7 +493,6 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
 
     public:
       typedef _Alloc		  allocator_type;
-      typedef typename _Alloc_traits::size_type size_type;
 
       allocator_type
       get_allocator() const _GLIBCXX_NOEXCEPT
@@ -535,7 +534,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
       : _Deque_base(std::move(__x), typename _Alloc_traits::is_always_equal{})
       { }
 
-      _Deque_base(_Deque_base&& __x, const allocator_type& __a, size_type __n)
+      _Deque_base(_Deque_base&& __x, const allocator_type& __a, size_t __n)
       : _M_impl(__a)
       {
 	if (__x.get_allocator() == __a)
@@ -930,7 +929,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
        */
       explicit
       deque(size_type __n, const allocator_type& __a = allocator_type())
-      : _Base(__a, __n)
+      : _Base(__a, _S_check_init_len(__n, __a))
       { _M_default_initialize(); }
 
       /**
@@ -943,7 +942,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
        */
       deque(size_type __n, const value_type& __value,
 	    const allocator_type& __a = allocator_type())
-      : _Base(__a, __n)
+      : _Base(__a, _S_check_init_len(__n, __a))
       { _M_fill_initialize(__value); }
 #else
       /**
@@ -957,7 +956,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
       explicit
       deque(size_type __n, const value_type& __value = value_type(),
 	    const allocator_type& __a = allocator_type())
-      : _Base(__a, __n)
+      : _Base(__a, _S_check_init_len(__n, __a))
       { _M_fill_initialize(__value); }
 #endif
 
@@ -1298,7 +1297,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
       /**  Returns the size() of the largest possible %deque.  */
       size_type
       max_size() const _GLIBCXX_NOEXCEPT
-      { return _Alloc_traits::max_size(_M_get_Tp_allocator()); }
+      { return _S_max_size(_M_get_Tp_allocator()); }
 
 #if __cplusplus >= 201103L
       /**
@@ -1875,10 +1874,28 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
 	void
 	_M_initialize_dispatch(_Integer __n, _Integer __x, __true_type)
 	{
-	  _M_initialize_map(static_cast<size_type>(__n));
+	  _M_initialize_map(_S_check_init_len(static_cast<size_type>(__n),
+					      _M_get_Tp_allocator()));
 	  _M_fill_initialize(__x);
 	}
 
+      static size_t
+      _S_check_init_len(size_t __n, const allocator_type& __a)
+      {
+	if (__n > _S_max_size(__a))
+	  __throw_length_error(
+	      __N("cannot create std::deque larger than max_size()"));
+	return __n;
+      }
+
+      static size_type
+      _S_max_size(const _Tp_alloc_type& __a) _GLIBCXX_NOEXCEPT
+      {
+	const size_t __diffmax = __gnu_cxx::__numeric_traits<ptrdiff_t>::__max;
+	const size_t __allocmax = _Alloc_traits::max_size(__a);
+	return (std::min)(__diffmax, __allocmax);
+      }
+
       // called by the range constructor to implement [23.1.1]/9
       template<typename _InputIterator>
 	void
diff --git a/libstdc++-v3/include/bits/stl_vector.h b/libstdc++-v3/include/bits/stl_vector.h
index 424971a..6bb75b7 100644
--- a/libstdc++-v3/include/bits/stl_vector.h
+++ b/libstdc++-v3/include/bits/stl_vector.h
@@ -459,7 +459,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
        */
       explicit
       vector(size_type __n, const allocator_type& __a = allocator_type())
-      : _Base(__n, __a)
+      : _Base(_S_check_init_len(__n, __a), __a)
       { _M_default_initialize(__n); }
 
       /**
@@ -472,7 +472,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
        */
       vector(size_type __n, const value_type& __value,
 	     const allocator_type& __a = allocator_type())
-      : _Base(__n, __a)
+      : _Base(_S_check_init_len(__n, __a), __a)
       { _M_fill_initialize(__n, __value); }
 #else
       /**
@@ -486,7 +486,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
       explicit
       vector(size_type __n, const value_type& __value = value_type(),
 	     const allocator_type& __a = allocator_type())
-      : _Base(__n, __a)
+      : _Base(_S_check_init_len(__n, __a), __a)
       { _M_fill_initialize(__n, __value); }
 #endif
 
@@ -872,7 +872,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
       /**  Returns the size() of the largest possible %vector.  */
       size_type
       max_size() const _GLIBCXX_NOEXCEPT
-      { return _Alloc_traits::max_size(_M_get_Tp_allocator()); }
+      { return _S_max_size(_M_get_Tp_allocator()); }
 
 #if __cplusplus >= 201103L
       /**
@@ -1485,7 +1485,8 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
 	void
 	_M_initialize_dispatch(_Integer __n, _Integer __value, __true_type)
 	{
-	  this->_M_impl._M_start = _M_allocate(static_cast<size_type>(__n));
+	  this->_M_impl._M_start = _M_allocate(_S_check_init_len(
+		static_cast<size_type>(__n), _M_get_Tp_allocator()));
 	  this->_M_impl._M_end_of_storage =
 	    this->_M_impl._M_start + static_cast<size_type>(__n);
 	  _M_fill_initialize(static_cast<size_type>(__n), __value);
@@ -1528,7 +1529,8 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
 			    std::forward_iterator_tag)
 	{
 	  const size_type __n = std::distance(__first, __last);
-	  this->_M_impl._M_start = this->_M_allocate(__n);
+	  this->_M_impl._M_start
+	    = this->_M_allocate(_S_check_init_len(__n, _M_get_Tp_allocator()));
 	  this->_M_impl._M_end_of_storage = this->_M_impl._M_start + __n;
 	  this->_M_impl._M_finish =
 	    std::__uninitialized_copy_a(__first, __last,
@@ -1707,10 +1709,28 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
 	if (max_size() - size() < __n)
 	  __throw_length_error(__N(__s));
 
-	const size_type __len = size() + std::max(size(), __n);
+	const size_type __len = size() + (std::max)(size(), __n);
 	return (__len < size() || __len > max_size()) ? max_size() : __len;
       }
 
+      // Called by constructors to check initial size.
+      static size_type
+      _S_check_init_len(size_type __n, const allocator_type& __a)
+      {
+	if (__n > _S_max_size(_Tp_alloc_type(__a)))
+	  __throw_length_error(
+	      __N("cannot create std::vector larger than max_size()"));
+	return __n;
+      }
+
+      static size_type
+      _S_max_size(const _Tp_alloc_type& __a) _GLIBCXX_NOEXCEPT
+      {
+	const size_t __diffmax = __gnu_cxx::__numeric_traits<ptrdiff_t>::__max;
+	const size_t __allocmax = _Alloc_traits::max_size(__a);
+	return (std::min)(__diffmax, __allocmax);
+      }
+
       // 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 86a7117..a1d114a 100644
--- a/libstdc++-v3/include/bits/vector.tcc
+++ b/libstdc++-v3/include/bits/vector.tcc
@@ -293,6 +293,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
 
 	if (__len > capacity())
 	  {
+	    _S_check_init_len(__len, _M_get_Tp_allocator());
 	    pointer __tmp(_M_allocate_and_copy(__len, __first, __last));
 	    _GLIBCXX_ASAN_ANNOTATE_REINIT;
 	    std::_Destroy(this->_M_impl._M_start, this->_M_impl._M_finish,
diff --git a/libstdc++-v3/testsuite/23_containers/deque/capacity/max_size.cc b/libstdc++-v3/testsuite/23_containers/deque/capacity/max_size.cc
new file mode 100644
index 0000000..3dabdd0
--- /dev/null
+++ b/libstdc++-v3/testsuite/23_containers/deque/capacity/max_size.cc
@@ -0,0 +1,146 @@
+// Copyright (C) 2018 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 3, or (at your option)
+// any later version.
+
+// This library is distributed in the hope that it will be useful,
+// but WITHOUT ANY WARRANTY; without even 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 COPYING3.  If not see
+// <http://www.gnu.org/licenses/>.
+
+// { dg-do run }
+
+#include <deque>
+#include <stdexcept>
+#include <limits>
+#include <testsuite_hooks.h>
+
+using test_type = std::deque<char>;
+
+typedef test_type::size_type size_type;
+typedef test_type::difference_type difference_type;
+
+const difference_type diffmax = std::numeric_limits<difference_type>::max();
+
+void
+test01()
+{
+  test_type v;
+  VERIFY( v.max_size() <= diffmax );
+}
+
+void
+test02()
+{
+  size_type n = size_type(diffmax) + 1;
+  VERIFY( n > test_type().max_size() );
+
+  try {
+    test_type v(n);
+    VERIFY( false );
+  } catch (const std::length_error&) { }
+
+  try {
+    test_type v(n, 'x');
+    VERIFY( false );
+  } catch (const std::length_error&) { }
+
+  try {
+    test_type v(n, 'x', test_type::allocator_type());
+    VERIFY( false );
+  } catch (const std::length_error&) { }
+}
+
+#ifdef __GLIBCXX_TYPE_INT_N_0
+template<typename T, typename U, bool = (sizeof(T) > sizeof(long long))>
+  struct Base_
+  {
+    typedef T difference_type;
+    typedef U size_type;
+  };
+
+template<typename T, typename U>
+  struct Base_<T, U, false>
+  {
+    typedef long long difference_type;
+    typedef unsigned long long size_type;
+  };
+
+typedef Base_<__GLIBCXX_TYPE_INT_N_0, unsigned __GLIBCXX_TYPE_INT_N_0> Base;
+#else
+struct Base
+{
+  typedef long long difference_type;
+  typedef unsigned long long size_type;
+};
+#endif
+
+// An iterator with a difference_type larger than ptrdiff_t
+struct Iter : Base
+{
+  typedef std::random_access_iterator_tag iterator_category;
+  typedef char value_type;
+  typedef const char* pointer;
+  typedef const char& reference;
+  using Base::difference_type;
+
+  Iter() : n(0) { }
+  Iter(size_type n) : n(n) { }
+
+  reference operator*() const { return value; }
+  pointer operator->() const { return &value; }
+
+  Iter& operator++() { ++n; return *this; }
+  Iter operator++(int) { Iter tmp(*this); ++n; return tmp; }
+  Iter& operator--() { --n; return *this; }
+  Iter operator--(int) { Iter tmp(*this); --n; return tmp; }
+
+  Iter& operator+=(difference_type d) { n += d; return *this; }
+  Iter& operator-=(difference_type d) { n -= d; return *this; }
+
+  difference_type operator-(const Iter& rhs) const { return n - rhs.n; }
+
+  reference operator[](difference_type d) const { return value; }
+
+  bool operator==(const Iter& rhs) const { return n == rhs.n; }
+  bool operator!=(const Iter& rhs) const { return n != rhs.n; }
+  bool operator<(const Iter& rhs) const { return n < rhs.n; }
+  bool operator>(const Iter& rhs) const { return n > rhs.n; }
+  bool operator<=(const Iter& rhs) const { return n <= rhs.n; }
+  bool operator>=(const Iter& rhs) const { return n >= rhs.n; }
+
+private:
+  size_type n;
+  static const char value = 'x';
+};
+
+Iter operator+(Iter i, Iter::difference_type n) { return i += n; }
+Iter operator+(Iter::difference_type n, Iter i) { return i += n; }
+Iter operator-(Iter::difference_type n, Iter i) { return i -= n; }
+
+void
+test03()
+{
+  Iter first, last(Iter::size_type(diffmax) + 1);
+  VERIFY( std::distance(first, last) > test_type().max_size() );
+
+  try {
+    test_type vec(first, last);
+    VERIFY(false);
+  } catch (const std::length_error&) { }
+}
+
+int
+main()
+{
+  test01();
+  test02();
+  test03();
+}
diff --git a/libstdc++-v3/testsuite/23_containers/vector/capacity/max_size.cc b/libstdc++-v3/testsuite/23_containers/vector/capacity/max_size.cc
new file mode 100644
index 0000000..499cd76
--- /dev/null
+++ b/libstdc++-v3/testsuite/23_containers/vector/capacity/max_size.cc
@@ -0,0 +1,146 @@
+// Copyright (C) 2018 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 3, or (at your option)
+// any later version.
+
+// This library is distributed in the hope that it will be useful,
+// but WITHOUT ANY WARRANTY; without even 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 COPYING3.  If not see
+// <http://www.gnu.org/licenses/>.
+
+// { dg-do run }
+
+#include <vector>
+#include <stdexcept>
+#include <limits>
+#include <testsuite_hooks.h>
+
+using test_type = std::vector<char>;
+
+typedef test_type::size_type size_type;
+typedef test_type::difference_type difference_type;
+
+const difference_type diffmax = std::numeric_limits<difference_type>::max();
+
+void
+test01()
+{
+  test_type v;
+  VERIFY( v.max_size() <= diffmax );
+}
+
+void
+test02()
+{
+  size_type n = size_type(diffmax) + 1;
+  VERIFY( n > test_type().max_size() );
+
+  try {
+    test_type v(n);
+    VERIFY( false );
+  } catch (const std::length_error&) { }
+
+  try {
+    test_type v(n, 'x');
+    VERIFY( false );
+  } catch (const std::length_error&) { }
+
+  try {
+    test_type v(n, 'x', test_type::allocator_type());
+    VERIFY( false );
+  } catch (const std::length_error&) { }
+}
+
+#ifdef __GLIBCXX_TYPE_INT_N_0
+template<typename T, typename U, bool = (sizeof(T) > sizeof(long long))>
+  struct Base_
+  {
+    typedef T difference_type;
+    typedef U size_type;
+  };
+
+template<typename T, typename U>
+  struct Base_<T, U, false>
+  {
+    typedef long long difference_type;
+    typedef unsigned long long size_type;
+  };
+
+typedef Base_<__GLIBCXX_TYPE_INT_N_0, unsigned __GLIBCXX_TYPE_INT_N_0> Base;
+#else
+struct Base
+{
+  typedef long long difference_type;
+  typedef unsigned long long size_type;
+};
+#endif
+
+// An iterator with a difference_type larger than ptrdiff_t
+struct Iter : Base
+{
+  typedef std::random_access_iterator_tag iterator_category;
+  typedef char value_type;
+  typedef const char* pointer;
+  typedef const char& reference;
+  using Base::difference_type;
+
+  Iter() : n(0) { }
+  Iter(size_type n) : n(n) { }
+
+  reference operator*() const { return value; }
+  pointer operator->() const { return &value; }
+
+  Iter& operator++() { ++n; return *this; }
+  Iter operator++(int) { Iter tmp(*this); ++n; return tmp; }
+  Iter& operator--() { --n; return *this; }
+  Iter operator--(int) { Iter tmp(*this); --n; return tmp; }
+
+  Iter& operator+=(difference_type d) { n += d; return *this; }
+  Iter& operator-=(difference_type d) { n -= d; return *this; }
+
+  difference_type operator-(const Iter& rhs) const { return n - rhs.n; }
+
+  reference operator[](difference_type d) const { return value; }
+
+  bool operator==(const Iter& rhs) const { return n == rhs.n; }
+  bool operator!=(const Iter& rhs) const { return n != rhs.n; }
+  bool operator<(const Iter& rhs) const { return n < rhs.n; }
+  bool operator>(const Iter& rhs) const { return n > rhs.n; }
+  bool operator<=(const Iter& rhs) const { return n <= rhs.n; }
+  bool operator>=(const Iter& rhs) const { return n >= rhs.n; }
+
+private:
+  size_type n;
+  static const char value = 'x';
+};
+
+Iter operator+(Iter i, Iter::difference_type n) { return i += n; }
+Iter operator+(Iter::difference_type n, Iter i) { return i += n; }
+Iter operator-(Iter::difference_type n, Iter i) { return i -= n; }
+
+void
+test03()
+{
+  Iter first, last(Iter::size_type(diffmax) + 1);
+  VERIFY( std::distance(first, last) > test_type().max_size() );
+
+  try {
+    test_type vec(first, last);
+    VERIFY(false);
+  } catch (const std::length_error&) { }
+}
+
+int
+main()
+{
+  test01();
+  test02();
+  test03();
+}