[gcc r8-10856] libstdc++: Fix division by zero in std::sample

[gcc r8-10856] libstdc++: Fix division by zero in std::sample

[Patrick Palka]

https://gcc.gnu.org/g:378b238923e6b19ab941d2b350f1db873d131940

commit r8-10856-g378b238923e6b19ab941d2b350f1db873d131940
Author: Patrick Palka <ppalka@redhat.com>
Date:   Mon Sep 21 20:48:23 2020 -0400

    libstdc++: Fix division by zero in std::sample
    
    This fixes a division by zero in the selection-sampling std::__sample
    overload when the input range is empty (and hence __unsampled_sz is 0).
    
    libstdc++-v3/ChangeLog:
    
            * include/bits/stl_algo.h (__sample): Exit early when the
            input range is empty.
            * testsuite/25_algorithms/sample/3.cc: New test.
    
    (cherry picked from commit 813ad9c4dd5a779f12ad2abf710c6e75a3117ef0)

Diff:
---
 libstdc++-v3/include/bits/stl_algo.h             |  3 ++
 libstdc++-v3/testsuite/25_algorithms/sample/3.cc | 50 ++++++++++++++++++++++++
 2 files changed, 53 insertions(+)

diff --git a/libstdc++-v3/include/bits/stl_algo.h b/libstdc++-v3/include/bits/stl_algo.h
index 753ebb7a09c..5c3d29bee5f 100644
--- a/libstdc++-v3/include/bits/stl_algo.h
+++ b/libstdc++-v3/include/bits/stl_algo.h
@@ -5754,6 +5754,9 @@ _GLIBCXX_BEGIN_NAMESPACE_ALGO
       using _Gen = remove_reference_t<_UniformRandomBitGenerator>;
       using __uc_type = common_type_t<typename _Gen::result_type, _USize>;
 
+      if (__first == __last)
+	return __out;
+
       __distrib_type __d{};
       _Size __unsampled_sz = std::distance(__first, __last);
       __n = std::min(__n, __unsampled_sz);
diff --git a/libstdc++-v3/testsuite/25_algorithms/sample/3.cc b/libstdc++-v3/testsuite/25_algorithms/sample/3.cc
new file mode 100644
index 00000000000..e89c40e27ee
--- /dev/null
+++ b/libstdc++-v3/testsuite/25_algorithms/sample/3.cc
@@ -0,0 +1,50 @@
+// 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-options "-std=gnu++17" }
+// { dg-do run { target c++17 } }
+// { dg-require-cstdint "" }
+
+#include <algorithm>
+#include <random>
+#include <testsuite_hooks.h>
+#include <testsuite_iterators.h>
+
+std::mt19937 rng;
+
+using std::sample;
+using __gnu_test::test_container;
+using __gnu_test::output_iterator_wrapper;
+using __gnu_test::forward_iterator_wrapper;
+
+void
+test01()
+{
+  const int in = 0;
+  test_container<const int, forward_iterator_wrapper> pop(&in, &in);
+  int out;
+  test_container<int, output_iterator_wrapper> samp(&out, &out + 1);
+
+  auto it = sample(pop.begin(), pop.end(), samp.begin(), 1, rng);
+  VERIFY( it.ptr == &out );
+}
+
+int
+main()
+{
+  test01();
+}