[gcc(refs/users/giulianob/heads/autopar_rebase2)] libstdc++: Make std::copy_n work with negative and non-integral sizes

[gcc(refs/users/giulianob/heads/autopar_rebase2)] libstdc++: Make std::copy_n work with negative and non-integral sizes

[Giuliano Belinassi]

https://gcc.gnu.org/g:7504e899d9ebe90ba46040acb1f8141ed0dad435

commit 7504e899d9ebe90ba46040acb1f8141ed0dad435
Author: Jonathan Wakely <jwakely@redhat.com>
Date:   Thu Jun 4 13:52:21 2020 +0100

    libstdc++: Make std::copy_n work with negative and non-integral sizes
    
    Since it was added in C++11, std::copy_n and std::ranges::copy_n should
    do nothing given a negative size, but for random access iterators we add
    the size to the iterator, possibly resulting in undefined behaviour.
    
    Also, C++20 clarified that std::copy_n requires the Size type to be
    convertible to an integral type. We previously assumed that it could be
    directly used in arithmetic expressions, without conversion to an
    integral type.
    
    This also fixes a bug in the random_access_iterator_wrapper helper adds
    some convenience aliases for using the iterator wrappers.
    
    libstdc++-v3/ChangeLog:
    
            * include/bits/ranges_algobase.h (__copy_n_fn): Only call
            ranges::copy for positive values.
            * include/bits/stl_algo.h (copy_n): Convert Size argument to an
            integral type and only call __copy_n for positive values.
            * testsuite/util/testsuite_iterators.h
            (random_access_iterator_wrapper::operator+=): Fix range check for
            negative values.
            (output_container, input_container, forward_container)
            (bidirectional_container, random_access_container): New alias
            templates.
            * testsuite/25_algorithms/copy_n/5.cc: New test.

Diff:
---
 libstdc++-v3/include/bits/ranges_algobase.h       |  7 +-
 libstdc++-v3/include/bits/stl_algo.h              | 11 ++-
 libstdc++-v3/testsuite/25_algorithms/copy_n/5.cc  | 97 +++++++++++++++++++++++
 libstdc++-v3/testsuite/util/testsuite_iterators.h | 28 ++++++-
 4 files changed, 137 insertions(+), 6 deletions(-)

diff --git a/libstdc++-v3/include/bits/ranges_algobase.h b/libstdc++-v3/include/bits/ranges_algobase.h
index 80c9a774301..49ca5ed4155 100644
--- a/libstdc++-v3/include/bits/ranges_algobase.h
+++ b/libstdc++-v3/include/bits/ranges_algobase.h
@@ -492,13 +492,16 @@ namespace ranges
 		 _Out __result) const
       {
 	if constexpr (random_access_iterator<_Iter>)
-	  return ranges::copy(__first, __first + __n, std::move(__result));
+	  {
+	    if (__n > 0)
+	      return ranges::copy(__first, __first + __n, std::move(__result));
+	  }
 	else
 	  {
 	    for (; __n > 0; --__n, (void)++__result, (void)++__first)
 	      *__result = *__first;
-	    return {std::move(__first), std::move(__result)};
 	  }
+	return {std::move(__first), std::move(__result)};
       }
   };
 
diff --git a/libstdc++-v3/include/bits/stl_algo.h b/libstdc++-v3/include/bits/stl_algo.h
index 932ece55529..b743c87cb80 100644
--- a/libstdc++-v3/include/bits/stl_algo.h
+++ b/libstdc++-v3/include/bits/stl_algo.h
@@ -771,10 +771,15 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
 	    typename iterator_traits<_InputIterator>::value_type>)
-      __glibcxx_requires_can_increment(__first, __n);
-      __glibcxx_requires_can_increment(__result, __n);
 
-      return std::__copy_n(__first, __n, __result,
+      const auto __n2 = std::__size_to_integer(__n);
+      if (__n2 <= 0)
+	return __result;
+
+      __glibcxx_requires_can_increment(__first, __n2);
+      __glibcxx_requires_can_increment(__result, __n2);
+
+      return std::__copy_n(__first, __n2, __result,
 			   std::__iterator_category(__first));
     }
 
diff --git a/libstdc++-v3/testsuite/25_algorithms/copy_n/5.cc b/libstdc++-v3/testsuite/25_algorithms/copy_n/5.cc
new file mode 100644
index 00000000000..2ea8c9da0dd
--- /dev/null
+++ b/libstdc++-v3/testsuite/25_algorithms/copy_n/5.cc
@@ -0,0 +1,97 @@
+// Copyright (C) 2020 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 { target c++11 } }
+
+#include <algorithm>
+#include <testsuite_iterators.h>
+
+void
+test01()
+{
+  // Negative sizes should be a no-op
+
+  const int from[2] = { 1, 2 };
+  __gnu_test::input_container<const int> f(from);
+  int* to = nullptr;
+  std::copy_n(f.begin(), -1, to);
+
+  std::copy_n(from, -20000, to); // random access
+
+  __gnu_test::random_access_container<const int> f2(from);
+  std::copy_n(f2.end(), -1, to);
+  std::copy_n(f2.begin(), -1, to);
+}
+
+struct Size
+{
+  operator long() const { return 2L; }
+
+  void operator++() = delete;
+  void operator--() = delete;
+  void operator++(int) = delete;
+  void operator--(int) = delete;
+
+  template<typename T> friend void operator+(Size, T) = delete;
+  template<typename T> friend void operator+(T, Size) = delete;
+  template<typename T> friend void operator-(Size, T) = delete;
+  template<typename T> friend void operator-(T, Size) = delete;
+  template<typename T> friend void operator==(Size, T) = delete;
+  template<typename T> friend void operator==(T, Size) = delete;
+  template<typename T> friend void operator!=(Size, T) = delete;
+  template<typename T> friend void operator!=(T, Size) = delete;
+  template<typename T> friend void operator<(Size, T) = delete;
+  template<typename T> friend void operator<(T, Size) = delete;
+  template<typename T> friend void operator<=(Size, T) = delete;
+  template<typename T> friend void operator<=(T, Size) = delete;
+  template<typename T> friend void operator>(Size, T) = delete;
+  template<typename T> friend void operator>(T, Size) = delete;
+  template<typename T> friend void operator>=(Size, T) = delete;
+  template<typename T> friend void operator>=(T, Size) = delete;
+};
+
+void
+test02()
+{
+  // C++20 only requires that Size is convertible to an integral type,
+  // it doesn't need to support any arithmetic or relational expressions.
+
+  const int from[3] = { 1, 2, 3 };
+  __gnu_test::input_container<const int> f(from);
+  int to[3] = { };
+  __gnu_test::output_container<int> t(to);
+  Size s;
+  std::copy_n(f.begin(), s, t.begin());
+  VERIFY( to[0] == 1 );
+  VERIFY( to[1] == 2 );
+  VERIFY( to[2] == 0 );
+
+  const int from2[3] = { 11, 22, 33 };
+  __gnu_test::random_access_container<const int> f2(from2);
+  __gnu_test::output_container<int> t2(to);
+  std::copy_n(f2.begin(), s, t2.begin());
+  VERIFY( to[0] == 11 );
+  VERIFY( to[1] == 22 );
+  VERIFY( to[2] == 0 );
+}
+
+int
+main()
+{
+  test01();
+  test02();
+}
diff --git a/libstdc++-v3/testsuite/util/testsuite_iterators.h b/libstdc++-v3/testsuite/util/testsuite_iterators.h
index 71b672c85fa..2eaafa16bee 100644
--- a/libstdc++-v3/testsuite/util/testsuite_iterators.h
+++ b/libstdc++-v3/testsuite/util/testsuite_iterators.h
@@ -509,7 +509,7 @@ namespace __gnu_test
 	}
       else
 	{
-	  ITERATOR_VERIFY(n <= this->ptr - this->SharedInfo->first);
+	  ITERATOR_VERIFY(-n <= this->ptr - this->SharedInfo->first);
 	  this->ptr += n;
 	}
       return *this;
@@ -627,6 +627,28 @@ namespace __gnu_test
     { return bounds.size(); }
   };
 
+#if __cplusplus >= 201103L
+  template<typename T>
+    using output_container
+      = test_container<T, output_iterator_wrapper>;
+
+  template<typename T>
+    using input_container
+      = test_container<T, input_iterator_wrapper>;
+
+  template<typename T>
+    using forward_container
+      = test_container<T, forward_iterator_wrapper>;
+
+  template<typename T>
+    using bidirectional_container
+      = test_container<T, bidirectional_iterator_wrapper>;
+
+  template<typename T>
+    using random_access_container
+      = test_container<T, random_access_iterator_wrapper>;
+#endif
+
 #if __cplusplus > 201703L
   template<typename T>
     struct contiguous_iterator_wrapper
@@ -690,6 +712,10 @@ namespace __gnu_test
       { return iter -= n; }
     };
 
+  template<typename T>
+    using contiguous_container
+      = test_container<T, contiguous_iterator_wrapper>;
+
   // A move-only input iterator type.
   template<typename T>
     struct input_iterator_wrapper_nocopy : input_iterator_wrapper<T>