PR libstdc++/87982 Fix generate_n and fill_n use of _Size parameter

The standard only requires that _Size can be converted to an integral
type, not that it can be used for arithmetic. Add a new set of
__size_to_integer helper functions to do the conversion (which will be
ambiguous if there is no one conversion that is better than any others).

Also add tests for DR 426 which requires these algorithms and search_n
to handle negative values of n.

	PR libstdc++/87982
	* include/bits/stl_algo.h (generate_n): Convert _Size parameter to
	an integral type.
	* include/bits/stl_algobase.h (__size_to_integer): New overloaded
	functions to convert a value to an integral type.
	(__fill_n_a, __fill_n_a): Assert that __n is already an integral type.
	(fill_n): Convert _Size parameter to an integral type.
	* testsuite/25_algorithms/fill_n/dr426.cc: New test.
	* testsuite/25_algorithms/generate_n/87982.cc: New test.
	* testsuite/25_algorithms/generate_n/dr426.cc: New test.

From-SVN: r270646

9 files changed, 430 insertions, 12 deletions

diff --git a/libstdc++-v3/ChangeLog b/libstdc++-v3/ChangeLog
index 130b3c4..f9e5ee4 100644
--- a/libstdc++-v3/ChangeLog
+++ b/libstdc++-v3/ChangeLog
@@ -1,3 +1,19 @@
+2019-04-29  Jonathan Wakely  <jwakely@redhat.com>
+
+	PR libstdc++/87982
+	* include/bits/stl_algo.h (generate_n): Convert _Size parameter to
+	an integral type.
+	* include/bits/stl_algobase.h (__size_to_integer): New overloaded
+	functions to convert a value to an integral type.
+	(__fill_n_a, __fill_n_a): Assert that __n is already an integral type.
+	(fill_n): Convert _Size parameter to an integral type.
+	* testsuite/25_algorithms/fill_n/87982.cc: New test.
+	* testsuite/25_algorithms/fill_n/87982_neg.cc: New test.
+	* testsuite/25_algorithms/fill_n/dr426.cc: New test.
+	* testsuite/25_algorithms/generate_n/87982.cc: New test.
+	* testsuite/25_algorithms/generate_n/87982_neg.cc: New test.
+	* testsuite/25_algorithms/generate_n/dr426.cc: New test.
+
 2019-04-28  Nina Dinka Ranns  <dinka.ranns@gmail.com>
 
 	Adding noexcept-specification on tuple constructors (LWG 2899)
diff --git a/libstdc++-v3/include/bits/stl_algo.h b/libstdc++-v3/include/bits/stl_algo.h
index cb870c4..ae9bb8f 100644
--- a/libstdc++-v3/include/bits/stl_algo.h
+++ b/libstdc++-v3/include/bits/stl_algo.h
@@ -4433,9 +4433,11 @@ _GLIBCXX_BEGIN_NAMESPACE_ALGO
    *  Performs the assignment @c *i = @p __gen() for each @c i in the range
    *  @p [__first,__first+__n).
    *
-   *  _GLIBCXX_RESOLVE_LIB_DEFECTS
-   *  DR 865. More algorithms that throw away information
+   * If @p __n is negative, the function does nothing.
   */
+  // _GLIBCXX_RESOLVE_LIB_DEFECTS
+  // DR 865. More algorithms that throw away information
+  // DR 426. search_n(), fill_n(), and generate_n() with negative n
   template<typename _OutputIterator, typename _Size, typename _Generator>
     _OutputIterator
     generate_n(_OutputIterator __first, _Size __n, _Generator __gen)
@@ -4445,7 +4447,8 @@ _GLIBCXX_BEGIN_NAMESPACE_ALGO
 	    // "the type returned by a _Generator"
 	    __typeof__(__gen())>)
 
-      for (__decltype(__n + 0) __niter = __n;
+      typedef __decltype(std::__size_to_integer(__n)) _IntSize;
+      for (_IntSize __niter = std::__size_to_integer(__n);
 	   __niter > 0; --__niter, (void) ++__first)
 	*__first = __gen();
       return __first;
diff --git a/libstdc++-v3/include/bits/stl_algobase.h b/libstdc++-v3/include/bits/stl_algobase.h
index 3b11394..58bfb6c 100644
--- a/libstdc++-v3/include/bits/stl_algobase.h
+++ b/libstdc++-v3/include/bits/stl_algobase.h
@@ -750,13 +750,65 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 		    __value);
     }
 
+  // Used by fill_n, generate_n, etc. to convert _Size to an integral type:
+  inline _GLIBCXX_CONSTEXPR int
+  __size_to_integer(int __n) { return __n; }
+  inline _GLIBCXX_CONSTEXPR unsigned
+  __size_to_integer(unsigned __n) { return __n; }
+  inline _GLIBCXX_CONSTEXPR long
+  __size_to_integer(long __n) { return __n; }
+  inline _GLIBCXX_CONSTEXPR unsigned long
+  __size_to_integer(unsigned long __n) { return __n; }
+  inline _GLIBCXX_CONSTEXPR long long
+  __size_to_integer(long long __n) { return __n; }
+  inline _GLIBCXX_CONSTEXPR unsigned long long
+  __size_to_integer(unsigned long long __n) { return __n; }
+
+#if defined(__GLIBCXX_TYPE_INT_N_0)
+  inline _GLIBCXX_CONSTEXPR __GLIBCXX_TYPE_INT_N_0
+  __size_to_integer(__GLIBCXX_TYPE_INT_N_0 __n) { return __n; }
+  inline _GLIBCXX_CONSTEXPR unsigned __GLIBCXX_TYPE_INT_N_0
+  __size_to_integer(unsigned __GLIBCXX_TYPE_INT_N_0 __n) { return __n; }
+#endif
+#if defined(__GLIBCXX_TYPE_INT_N_1)
+  inline _GLIBCXX_CONSTEXPR __GLIBCXX_TYPE_INT_N_1
+  __size_to_integer(__GLIBCXX_TYPE_INT_N_1 __n) { return __n; }
+  inline _GLIBCXX_CONSTEXPR unsigned __GLIBCXX_TYPE_INT_N_1
+  __size_to_integer(unsigned __GLIBCXX_TYPE_INT_N_1 __n) { return __n; }
+#endif
+#if defined(__GLIBCXX_TYPE_INT_N_2)
+  inline _GLIBCXX_CONSTEXPR __GLIBCXX_TYPE_INT_N_2
+  __size_to_integer(__GLIBCXX_TYPE_INT_N_2 __n) { return __n; }
+  inline _GLIBCXX_CONSTEXPR unsigned __GLIBCXX_TYPE_INT_N_2
+  __size_to_integer(unsigned __GLIBCXX_TYPE_INT_N_2 __n) { return __n; }
+#endif
+#if defined(__GLIBCXX_TYPE_INT_N_3)
+  inline _GLIBCXX_CONSTEXPR unsigned __GLIBCXX_TYPE_INT_N_3
+  __size_to_integer(__GLIBCXX_TYPE_INT_N_3 __n) { return __n; }
+  inline _GLIBCXX_CONSTEXPR __GLIBCXX_TYPE_INT_N_3
+  __size_to_integer(unsigned __GLIBCXX_TYPE_INT_N_3 __n) { return __n; }
+#endif
+
+  inline _GLIBCXX_CONSTEXPR long long
+  __size_to_integer(float __n) { return __n; }
+  inline _GLIBCXX_CONSTEXPR long long
+  __size_to_integer(double __n) { return __n; }
+  inline _GLIBCXX_CONSTEXPR long long
+  __size_to_integer(long double __n) { return __n; }
+#if !defined(__STRICT_ANSI__) && defined(_GLIBCXX_USE_FLOAT128)
+  inline _GLIBCXX_CONSTEXPR long long
+  __size_to_integer(__float128 __n) { return __n; }
+#endif
+
   template<typename _OutputIterator, typename _Size, typename _Tp>
     inline typename
     __gnu_cxx::__enable_if<!__is_scalar<_Tp>::__value, _OutputIterator>::__type
     __fill_n_a(_OutputIterator __first, _Size __n, const _Tp& __value)
     {
-      for (__decltype(__n + 0) __niter = __n;
-	   __niter > 0; --__niter, (void) ++__first)
+#if __cplusplus >= 201103L
+      static_assert(is_integral<_Size>{}, "fill_n must pass integral size");
+#endif
+      for (; __n > 0; --__n, (void) ++__first)
 	*__first = __value;
       return __first;
     }
@@ -766,9 +818,11 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
     __gnu_cxx::__enable_if<__is_scalar<_Tp>::__value, _OutputIterator>::__type
     __fill_n_a(_OutputIterator __first, _Size __n, const _Tp& __value)
     {
+#if __cplusplus >= 201103L
+      static_assert(is_integral<_Size>{}, "fill_n must pass integral size");
+#endif
       const _Tp __tmp = __value;
-      for (__decltype(__n + 0) __niter = __n;
-	   __niter > 0; --__niter, (void) ++__first)
+      for (; __n > 0; --__n, (void) ++__first)
 	*__first = __tmp;
       return __first;
     }
@@ -792,21 +846,24 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
    *
    *  This function fills a range with copies of the same value.  For char
    *  types filling contiguous areas of memory, this becomes an inline call
-   *  to @c memset or @ wmemset.
+   *  to @c memset or @c wmemset.
    *
-   *  _GLIBCXX_RESOLVE_LIB_DEFECTS
-   *  DR 865. More algorithms that throw away information
+   *  If @p __n is negative, the function does nothing.
   */
+  // _GLIBCXX_RESOLVE_LIB_DEFECTS
+  // DR 865. More algorithms that throw away information
+  // DR 426. search_n(), fill_n(), and generate_n() with negative n
   template<typename _OI, typename _Size, typename _Tp>
     inline _OI
     fill_n(_OI __first, _Size __n, const _Tp& __value)
     {
       // concept requirements
       __glibcxx_function_requires(_OutputIteratorConcept<_OI, _Tp>)
-      __glibcxx_requires_can_increment(__first, __n);
 
       return std::__niter_wrap(__first,
-		std::__fill_n_a(std::__niter_base(__first), __n, __value));
+	  std::__fill_n_a(std::__niter_base(__first),
+			  std::__size_to_integer(__n),
+			  __value));
     }
 
   template<bool _BoolType>
diff --git a/libstdc++-v3/testsuite/25_algorithms/fill_n/87982.cc b/libstdc++-v3/testsuite/25_algorithms/fill_n/87982.cc
new file mode 100644
index 0000000..79bad88
--- /dev/null
+++ b/libstdc++-v3/testsuite/25_algorithms/fill_n/87982.cc
@@ -0,0 +1,87 @@
+// Copyright (C) 2019 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 <algorithm>
+#include <testsuite_hooks.h>
+
+int a[4] = { 0, 1, 2, 3 };
+int g;
+enum E { e2 = 2 };
+
+struct Num
+{
+  char val;
+
+  operator char() const { return val; }
+
+private:
+  void operator+() const;
+  void operator+(int) const;
+  void operator+(Num) const;
+  void operator<(int) const;
+  void operator>(int) const;
+  void operator<=(int) const;
+  void operator>=(int) const;
+  void operator==(int) const;
+  void operator!=(int) const;
+};
+
+void
+test01()
+{
+  int* p;
+
+  g = -1;
+  p = std::fill_n(a, true, g); // bool as Size
+  VERIFY( p == a+1 );
+  VERIFY( a[0] == g );
+  VERIFY( a[1] == 1 );
+  VERIFY( a[2] == 2 );
+  VERIFY( a[3] == 3 );
+
+  g = -2;
+  p = std::fill_n(a, e2, g); // enumeration type as Size
+  VERIFY( p == a+2 );
+  VERIFY( a[0] == g );
+  VERIFY( a[1] == g );
+  VERIFY( a[2] == 2 );
+  VERIFY( a[3] == 3 );
+
+  g = -3;
+  p = std::fill_n(a, 3.5, g); // floating point type as Size
+  VERIFY( p == a+3 );
+  VERIFY( a[0] == g );
+  VERIFY( a[1] == g );
+  VERIFY( a[2] == g );
+  VERIFY( a[3] == 3 );
+
+  g = -4;
+  Num n = { 3 };
+  p = std::fill_n(a, n, g); // non-scalar type as Size
+  VERIFY( p == a+3 );
+  VERIFY( a[0] == g );
+  VERIFY( a[1] == g );
+  VERIFY( a[2] == g );
+  VERIFY( a[3] == 3 );
+}
+
+int main()
+{
+  test01();
+}
diff --git a/libstdc++-v3/testsuite/25_algorithms/fill_n/87982_neg.cc b/libstdc++-v3/testsuite/25_algorithms/fill_n/87982_neg.cc
new file mode 100644
index 0000000..fbd368d
--- /dev/null
+++ b/libstdc++-v3/testsuite/25_algorithms/fill_n/87982_neg.cc
@@ -0,0 +1,31 @@
+// Copyright (C) 2019 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 compile }
+
+#include <algorithm>
+
+// PR libstdc++/87982
+
+void test01()
+{
+  int a[2];
+  std::fill_n(a, a+2, -1);
+}
+
+// { dg-error "no matching function" "" { target *-*-* } 0 }
+// { dg-prune-output "invalid conversion" }
diff --git a/libstdc++-v3/testsuite/25_algorithms/fill_n/dr426.cc b/libstdc++-v3/testsuite/25_algorithms/fill_n/dr426.cc
new file mode 100644
index 0000000..2a0a515
--- /dev/null
+++ b/libstdc++-v3/testsuite/25_algorithms/fill_n/dr426.cc
@@ -0,0 +1,58 @@
+// Copyright (C) 2019 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 <algorithm>
+#include <testsuite_hooks.h>
+
+// DR 426. search_n(), fill_n(), and generate_n() with negative n
+
+void
+test01()
+{
+  int i = 99;
+  std::fill_n(&i, 0, 13);
+  VERIFY( i == 99 );
+  std::fill_n(&i, -1, 13);
+  VERIFY( i == 99 );
+  std::fill_n(&i, -100, 13);
+  VERIFY( i == 99 );
+}
+
+struct X
+{
+  X() { }
+  X(const X&) { throw 1; }
+  X& operator=(const X&) { throw 1u; }
+};
+
+void
+test02()
+{
+  X x;
+  std::fill_n(&x, 0, x);
+  std::fill_n(&x, -1, x);
+  std::fill_n(&x, -100, x);
+}
+
+int
+main()
+{
+  test01();
+  test02();
+}
diff --git a/libstdc++-v3/testsuite/25_algorithms/generate_n/87982.cc b/libstdc++-v3/testsuite/25_algorithms/generate_n/87982.cc
new file mode 100644
index 0000000..cc0780a
--- /dev/null
+++ b/libstdc++-v3/testsuite/25_algorithms/generate_n/87982.cc
@@ -0,0 +1,88 @@
+// Copyright (C) 2019 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 <algorithm>
+#include <testsuite_hooks.h>
+
+int a[4] = { 0, 1, 2, 3 };
+int g;
+int gen() { return g; }
+enum E { e2 = 2 };
+
+struct Num
+{
+  char val;
+
+  operator char() const { return val; }
+
+private:
+  void operator+() const;
+  void operator+(int) const;
+  void operator+(Num) const;
+  void operator<(int) const;
+  void operator>(int) const;
+  void operator<=(int) const;
+  void operator>=(int) const;
+  void operator==(int) const;
+  void operator!=(int) const;
+};
+
+void
+test01()
+{
+  int* p;
+
+  g = -1;
+  p = std::generate_n(a, true, &gen); // bool as Size
+  VERIFY( p == a+1 );
+  VERIFY( a[0] == g );
+  VERIFY( a[1] == 1 );
+  VERIFY( a[2] == 2 );
+  VERIFY( a[3] == 3 );
+
+  g = -2;
+  p = std::generate_n(a, e2, &gen); // enumeration type as Size
+  VERIFY( p == a+2 );
+  VERIFY( a[0] == g );
+  VERIFY( a[1] == g );
+  VERIFY( a[2] == 2 );
+  VERIFY( a[3] == 3 );
+
+  g = -3;
+  p = std::generate_n(a, 3.5, &gen); // floating point type as Size
+  VERIFY( p == a+3 );
+  VERIFY( a[0] == g );
+  VERIFY( a[1] == g );
+  VERIFY( a[2] == g );
+  VERIFY( a[3] == 3 );
+
+  g = -4;
+  Num n = { 3 };
+  p = std::generate_n(a, n, &gen); // non-scalar type as Size
+  VERIFY( p == a+3 );
+  VERIFY( a[0] == g );
+  VERIFY( a[1] == g );
+  VERIFY( a[2] == g );
+  VERIFY( a[3] == 3 );
+}
+
+int main()
+{
+  test01();
+}
diff --git a/libstdc++-v3/testsuite/25_algorithms/generate_n/87982_neg.cc b/libstdc++-v3/testsuite/25_algorithms/generate_n/87982_neg.cc
new file mode 100644
index 0000000..88134bd
--- /dev/null
+++ b/libstdc++-v3/testsuite/25_algorithms/generate_n/87982_neg.cc
@@ -0,0 +1,32 @@
+// Copyright (C) 2019 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 compile }
+
+#include <algorithm>
+
+// PR libstdc++/87982
+
+void test01()
+{
+  int gen();
+  int a[2];
+  std::generate_n(a, a+2, &gen);
+}
+
+// { dg-error "no matching function" "" { target *-*-* } 0 }
+// { dg-prune-output "invalid conversion" }
diff --git a/libstdc++-v3/testsuite/25_algorithms/generate_n/dr426.cc b/libstdc++-v3/testsuite/25_algorithms/generate_n/dr426.cc
new file mode 100644
index 0000000..87a132b
--- /dev/null
+++ b/libstdc++-v3/testsuite/25_algorithms/generate_n/dr426.cc
@@ -0,0 +1,46 @@
+// Copyright (C) 2019 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 <algorithm>
+#include <testsuite_hooks.h>
+
+// DR 426. search_n(), fill_n(), and generate_n() with negative n
+
+struct Gen
+{
+  int operator()() const { throw 1; }
+};
+
+void
+test01()
+{
+  int i = 99;
+  std::generate_n(&i, 0, Gen());
+  VERIFY( i == 99 );
+  std::generate_n(&i, -1, Gen());
+  VERIFY( i == 99 );
+  std::generate_n(&i, -100, Gen());
+  VERIFY( i == 99 );
+}
+
+int
+main()
+{
+  test01();
+}