Re: [Bug libstdc++/61107] stl_algo.h: std::__inplace_stable_partition() doesn't process the whole data range

[François Dumont <frs dot dumont at gmail dot com>]

    I introduced the random tests after Christopher Jefferson request 
to have more intensive tests on those algos. Is it the whole stuff of 
tests using random numbers that you don't like or just the usage of 
mt19937 ? If second is this new version using the usual random_device I 
used so far better ?

If it is the whole usage of random numbers that you don't like I will 
simply get rid of the new tests files.

François

On 10/11/2014 22:45, Jonathan Wakely wrote:
> On 10/11/14 21:50 +0100, François Dumont wrote:
> > Any news about this one ?
> >
> > Here is another version with additional random tests on algos just to 
> > challenge other combinations of tests.
> >
> >    PR libstdc++/61107
> >    * include/bits/stl_algo.h (__inplace_stable_partition): Delete.
> >    (__stable_partition_adaptive): Return __first is range length is 1.
>
> The first "is" should be "if".
>
> The change to stl_algo.h looks OK.
>
> I don't like the use of mt19937 in the tests, I know you committed a
> test I wrote recently that uses mt19937, but that was only meant to
> demonstrate the bug for bugzilla, not necessarily as the final test.
>
> The PRNG produces the exact same sequence of numbers every time (when
> you don't seed it) so if you can make the test fail using a few
> iterations with the PRNG then you can find the input that fails and
> just add that input to the testsuite. I didn't do that for the test I
> put in bugzilla because I didn't have time to work out which input
> caused the memory leak, only that it leaked for *some* easily
> reproducible input. I wasn't trying to start a trend where we use
> fixed sequences of pseudorandom numbers in lots of tests.

Index: include/bits/stl_algo.h
===================================================================
--- include/bits/stl_algo.h	(revision 217320)
+++ include/bits/stl_algo.h	(working copy)
@@ -1512,34 +1512,6 @@
   // partition
 
   /// This is a helper function...
-  /// Requires __len != 0 and !__pred(*__first),
-  /// same as __stable_partition_adaptive.
-  template<typename _ForwardIterator, typename _Predicate, typename _Distance>
-    _ForwardIterator
-    __inplace_stable_partition(_ForwardIterator __first,
-			       _Predicate __pred, _Distance __len)
-    {
-      if (__len == 1)
-	return __first;
-      _ForwardIterator __middle = __first;
-      std::advance(__middle, __len / 2);
-      _ForwardIterator __left_split =
-	std::__inplace_stable_partition(__first, __pred, __len / 2);
-      // Advance past true-predicate values to satisfy this
-      // function's preconditions.
-      _Distance __right_len = __len - __len / 2;
-      _ForwardIterator __right_split =
-	std::__find_if_not_n(__middle, __right_len, __pred);
-      if (__right_len)
-	__right_split = std::__inplace_stable_partition(__middle,
-							__pred,
-							__right_len);
-      std::rotate(__left_split, __middle, __right_split);
-      std::advance(__left_split, std::distance(__middle, __right_split));
-      return __left_split;
-    }
-
-  /// This is a helper function...
   /// Requires __first != __last and !__pred(__first)
   /// and __len == distance(__first, __last).
   ///
@@ -1554,10 +1526,14 @@
 				_Pointer __buffer,
 				_Distance __buffer_size)
     {
+      if (__len == 1)
+	return __first;
+
       if (__len <= __buffer_size)
 	{
 	  _ForwardIterator __result1 = __first;
 	  _Pointer __result2 = __buffer;
+
 	  // The precondition guarantees that !__pred(__first), so
 	  // move that element to the buffer before starting the loop.
 	  // This ensures that we only call __pred once per element.
@@ -1575,31 +1551,33 @@
 		*__result2 = _GLIBCXX_MOVE(*__first);
 		++__result2;
 	      }
+
 	  _GLIBCXX_MOVE3(__buffer, __result2, __result1);
 	  return __result1;
 	}
-      else
-	{
-	  _ForwardIterator __middle = __first;
-	  std::advance(__middle, __len / 2);
-	  _ForwardIterator __left_split =
-	    std::__stable_partition_adaptive(__first, __middle, __pred,
-					     __len / 2, __buffer,
-					     __buffer_size);
-	  // Advance past true-predicate values to satisfy this
-	  // function's preconditions.
-	  _Distance __right_len = __len - __len / 2;
-	  _ForwardIterator __right_split =
-	    std::__find_if_not_n(__middle, __right_len, __pred);
-	  if (__right_len)
-	    __right_split =
-	      std::__stable_partition_adaptive(__right_split, __last, __pred,
-					       __right_len,
-					       __buffer, __buffer_size);
-	  std::rotate(__left_split, __middle, __right_split);
-	  std::advance(__left_split, std::distance(__middle, __right_split));
-	  return __left_split;
-	}
+
+      _ForwardIterator __middle = __first;
+      std::advance(__middle, __len / 2);
+      _ForwardIterator __left_split =
+	std::__stable_partition_adaptive(__first, __middle, __pred,
+					 __len / 2, __buffer,
+					 __buffer_size);
+
+      // Advance past true-predicate values to satisfy this
+      // function's preconditions.
+      _Distance __right_len = __len - __len / 2;
+      _ForwardIterator __right_split =
+	std::__find_if_not_n(__middle, __right_len, __pred);
+
+      if (__right_len)
+	__right_split =
+	  std::__stable_partition_adaptive(__right_split, __last, __pred,
+					   __right_len,
+					   __buffer, __buffer_size);
+
+      std::rotate(__left_split, __middle, __right_split);
+      std::advance(__left_split, std::distance(__middle, __right_split));
+      return __left_split;
     }
 
   template<typename _ForwardIterator, typename _Predicate>
@@ -1618,16 +1596,11 @@
 	_DistanceType;
 
       _Temporary_buffer<_ForwardIterator, _ValueType> __buf(__first, __last);
-      if (__buf.size() > 0)
-	return
-	  std::__stable_partition_adaptive(__first, __last, __pred,
-					   _DistanceType(__buf.requested_size()),
-					   __buf.begin(),
-					   _DistanceType(__buf.size()));
-      else
-	return
-	  std::__inplace_stable_partition(__first, __pred,
-					  _DistanceType(__buf.requested_size()));
+      return
+	std::__stable_partition_adaptive(__first, __last, __pred,
+					 _DistanceType(__buf.requested_size()),
+					 __buf.begin(),
+					 _DistanceType(__buf.size()));
     }
 
   /**
@@ -2471,6 +2444,7 @@
 				     __gnu_cxx::__ops::__val_comp_iter(__comp));
 	      __len11 = std::distance(__first, __first_cut);
 	    }
+
 	  _BidirectionalIterator __new_middle
 	    = std::__rotate_adaptive(__first_cut, __middle, __second_cut,
 				     __len1 - __len11, __len22, __buffer,
@@ -2496,6 +2470,7 @@
     {
       if (__len1 == 0 || __len2 == 0)
 	return;
+
       if (__len1 + __len2 == 2)
 	{
 	  if (__comp(__middle, __first))
@@ -2502,6 +2477,7 @@
 	    std::iter_swap(__first, __middle);
 	  return;
 	}
+
       _BidirectionalIterator __first_cut = __first;
       _BidirectionalIterator __second_cut = __middle;
       _Distance __len11 = 0;
@@ -2524,6 +2500,7 @@
 				 __gnu_cxx::__ops::__val_comp_iter(__comp));
 	  __len11 = std::distance(__first, __first_cut);
 	}
+
       std::rotate(__first_cut, __middle, __second_cut);
       _BidirectionalIterator __new_middle = __first_cut;
       std::advance(__new_middle, std::distance(__middle, __second_cut));
Index: testsuite/25_algorithms/inplace_merge/1.cc
===================================================================
--- testsuite/25_algorithms/inplace_merge/1.cc	(revision 217320)
+++ testsuite/25_algorithms/inplace_merge/1.cc	(working copy)
@@ -20,6 +20,7 @@
 #include <algorithm>
 #include <testsuite_hooks.h>
 #include <testsuite_iterators.h>
+#include <testsuite_new_operators.h>
 
 using __gnu_test::test_container;
 using __gnu_test::bidirectional_iterator_wrapper;
@@ -66,17 +67,27 @@
 {
   bool test __attribute__((unused)) = true;
 
-  S s[4];
+  S s[8];
   s[0].a = 0;
   s[1].a = 1;
-  s[2].a = 0;
-  s[3].a = 1;
+  s[2].a = 2;
+  s[3].a = 3;
+  s[4].a = 0;
+  s[5].a = 1;
+  s[6].a = 2;
+  s[7].a = 3;
+
   s[0].b = 0;
-  s[1].b = 0;
-  s[2].b = 1;
-  s[3].b = 1;
-  inplace_merge(s, s + 2, s + 4);
-  VERIFY( s[0].b == 0 && s[1].b == 1 && s[2].b == 0 && s[3].b == 1 );
+  s[1].b = 1;
+  s[2].b = 2;
+  s[3].b = 3;
+  s[4].b = 4;
+  s[5].b = 5;
+  s[6].b = 6;
+  s[7].b = 7;
+
+  inplace_merge(s, s + 4, s + 8);
+  VERIFY( s[0].b == 0 && s[1].b == 4 && s[2].b == 1 && s[3].b == 5 );
 }
 
 int 
@@ -85,5 +96,15 @@
   test1();
   test2();
   test3();
+
+  __gnu_test::set_new_limit(sizeof(S) * 4);
+  test3();
+
+  __gnu_test::set_new_limit(sizeof(S));
+  test3();
+
+  __gnu_test::set_new_limit(0);
+  test3();
+
   return 0;
 }
Index: testsuite/25_algorithms/inplace_merge/2.cc
===================================================================
--- testsuite/25_algorithms/inplace_merge/2.cc	(revision 0)
+++ testsuite/25_algorithms/inplace_merge/2.cc	(working copy)
@@ -0,0 +1,73 @@
+// Copyright (C) 2014 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/>.
+
+// 25.3.1.2 [lib.stable.sort]
+
+// { dg-options "-std=gnu++11" }
+
+#include <random>
+#include <algorithm>
+#include <vector>
+
+#include <testsuite_new_operators.h>
+#include <testsuite_hooks.h>
+
+using std::inplace_merge;
+using std::sort;
+
+void 
+test1()
+{
+  bool test __attribute__((unused)) = true;
+
+  using namespace __gnu_test;
+
+  std::random_device rng;
+  std::uniform_int_distribution<int> d;
+  std::uniform_int_distribution<int>::param_type p{0, 100};
+  std::uniform_int_distribution<int>::param_type x{0, 1000};
+
+  auto sz1 = d(rng, x);
+  auto sz2 = d(rng, x);
+  std::vector<int> values;
+  values.reserve(sz1 + sz2);
+
+  for (int i = 0; i < 10; ++i)
+  {
+    values.clear();
+    for (int n = 0; n != sz1; ++n)
+      values.push_back(d(rng, x));
+    sort(values.begin(), values.end());
+    
+    for (int n = 0; n != sz2; ++n)
+      values.push_back(d(rng, x));
+    sort(values.begin() + sz1, values.end());
+    
+    set_new_limit(sizeof(int) * d(rng, p));
+
+    inplace_merge(values.begin(), values.begin() + sz1, values.end());
+    
+    for (int n = 1; n < sz1 + sz2; ++n)
+      VERIFY( values[n - 1] <= values[n] );
+  }
+}
+
+int 
+main()
+{
+  test1();
+}
Index: testsuite/25_algorithms/stable_partition/1.cc
===================================================================
--- testsuite/25_algorithms/stable_partition/1.cc	(revision 217320)
+++ testsuite/25_algorithms/stable_partition/1.cc	(working copy)
@@ -19,6 +19,7 @@
 
 #include <algorithm>
 #include <functional>
+#include <testsuite_new_operators.h>
 #include <testsuite_hooks.h>
 
 bool test __attribute__((unused)) = true;
@@ -27,6 +28,9 @@
 const int B[] = {2, 4, 6, 8, 10, 12, 14, 16, 1, 3, 5, 7, 9, 11, 13, 15, 17};
 const int N = sizeof(A) / sizeof(int);
 
+// Index of the middle element that should be returned by the algo.
+const int M = 8;
+
 struct Pred
 {
     bool
@@ -36,20 +40,36 @@
 
 // 25.2.12 stable_partition()
 void
-test02()
+test01()
 {
-    using std::stable_partition;
+  using std::stable_partition;
 
-    int s1[N];
-    std::copy(A, A + N, s1);
+  int s1[N];
+  std::copy(A, A + N, s1);
 
-    stable_partition(s1, s1 + N, Pred());
-    VERIFY(std::equal(s1, s1 + N, B));
+  VERIFY( stable_partition(s1, s1 + N, Pred()) == s1 + M );
+  VERIFY( std::equal(s1, s1 + N, B) );
 }
 
 int
 main()
 {
-  test02();
+  test01();
+
+  // stable_partition rely on an internal buffer if possible. Try to limit the
+  // size of this buffer to see if algo is robust.
+
+  // Limit to half of the necessary buffer.
+  __gnu_test::set_new_limit(sizeof(A) / 2);
+  test01();
+
+  // Limit to just 1 element.
+  __gnu_test::set_new_limit(sizeof(int));
+  test01();
+
+  // Limit to 0
+  __gnu_test::set_new_limit(0);
+  test01();
+
   return 0;
 }
Index: testsuite/25_algorithms/stable_partition/2.cc
===================================================================
--- testsuite/25_algorithms/stable_partition/2.cc	(revision 0)
+++ testsuite/25_algorithms/stable_partition/2.cc	(working copy)
@@ -0,0 +1,68 @@
+//
+// 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/>.
+
+// 25.3.1.2 [lib.stable.sort]
+
+// { dg-options "-std=gnu++11" }
+
+#include <random>
+#include <algorithm>
+#include <vector>
+
+#include <testsuite_new_operators.h>
+#include <testsuite_hooks.h>
+
+using std::inplace_merge;
+using std::sort;
+
+void 
+test1()
+{
+  bool test __attribute__((unused)) = true;
+
+  using namespace __gnu_test;
+
+  std::random_device rng;
+  std::uniform_int_distribution<int> d;
+  std::uniform_int_distribution<int>::param_type p{0, 100};
+  std::uniform_int_distribution<int>::param_type x{0, 1000};
+
+  auto sz = d(rng, x);
+  std::vector<int> values;
+  values.reserve(sz);
+
+  for (int i = 0; i < 10; ++i)
+  {
+    values.clear();
+    for (int n = 0; n != sz; ++n)
+      values.push_back(d(rng, x));
+    
+    set_new_limit(sizeof(int) * d(rng, p));
+
+    auto middle = stable_partition(values.begin(), values.end(),
+				   [](int v)
+				   { return v % 2 == 0; });
+    
+    for (auto it = values.begin(); it != middle; ++it)
+      VERIFY( *it % 2 == 0 );
+  }
+}
+
+int 
+main()
+{
+  test1();
+}
Index: testsuite/25_algorithms/stable_sort/1.cc
===================================================================
--- testsuite/25_algorithms/stable_sort/1.cc	(revision 217320)
+++ testsuite/25_algorithms/stable_sort/1.cc	(working copy)
@@ -18,6 +18,7 @@
 // 25.3.1.2 [lib.stable.sort]
 
 #include <algorithm>
+#include <testsuite_new_operators.h>
 #include <testsuite_hooks.h>
 #include <testsuite_iterators.h>
 
@@ -30,7 +31,7 @@
 void 
 test1()
 {
-  int array[]={0};
+  int array[] = { 0 };
   Container con(array, array);
   stable_sort(con.begin(), con.end());
 }
@@ -38,7 +39,7 @@
 void 
 test2()
 {
-  int array[] = {6, 5, 4, 3, 2, 1, 0};
+  int array[] = { 6, 5, 4, 3, 2, 1, 0 };
   Container con(array, array + 7);
   stable_sort(con.begin(), con.end());
   VERIFY(array[0] == 0 && array[1] == 1 && array[2] == 2 &&
@@ -45,6 +46,7 @@
 	 array[3] == 3 && array[4] == 4 && array[5] == 5 &&
 	 array[6] == 6);
 }
+
 struct S
 {
   int i;
@@ -72,8 +74,7 @@
 void 
 test3()
 {
-
-  S array[] = {-1, -2, 1, 2, -3 ,-5 ,3 , -4, 5, 4};
+  S array[] = { -1, -2, 1, 2, -3 ,-5 ,3 , -4, 5, 4 };
   test_container<S, random_access_iterator_wrapper> con(array,array + 10);
   stable_sort(con.begin(), con.end());
   for(int i = 0; i < 10; ++i)
@@ -85,5 +86,15 @@
 {
   test1();
   test2();
+
   test3();
+
+  __gnu_test::set_new_limit(sizeof(S) * 5);
+  test3();
+
+  __gnu_test::set_new_limit(sizeof(S));
+  test3();
+
+  __gnu_test::set_new_limit(0);
+  test3();
 }
Index: testsuite/25_algorithms/stable_sort/4.cc
===================================================================
--- testsuite/25_algorithms/stable_sort/4.cc	(revision 0)
+++ testsuite/25_algorithms/stable_sort/4.cc	(working copy)
@@ -0,0 +1,66 @@
+// Copyright (C) 2014 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/>.
+
+// 25.3.1.2 [lib.stable.sort]
+
+// { dg-options "-std=gnu++11" }
+
+#include <random>
+#include <algorithm>
+#include <vector>
+
+#include <testsuite_new_operators.h>
+#include <testsuite_hooks.h>
+
+using std::stable_sort;
+
+void 
+test1()
+{
+  bool test __attribute__((unused)) = true;
+
+  using namespace __gnu_test;
+
+  std::random_device rng;
+  std::uniform_int_distribution<int> d;
+  std::uniform_int_distribution<int>::param_type p{0, 100};
+  std::uniform_int_distribution<int>::param_type x{0, 1000};
+
+  auto sz = d(rng, x);
+  std::vector<int> values;
+  values.reserve(sz);
+
+  for (int i = 0; i < 10; ++i)
+  {
+    values.clear();
+    for (int n = 0; n != sz; ++n)
+      values.push_back(d(rng, x));
+
+    set_new_limit(sizeof(int) * d(rng, p));
+
+    std::stable_sort(values.begin(), values.end());
+    
+    for (int n = 1; n < sz; ++n)
+      VERIFY( values[n - 1] <= values[n] );
+  }
+}
+
+int 
+main()
+{
+  test1();
+}
Index: testsuite/util/testsuite_new_operators.h
===================================================================
--- testsuite/util/testsuite_new_operators.h	(revision 0)
+++ testsuite/util/testsuite_new_operators.h	(working copy)
@@ -0,0 +1,69 @@
+// -*- C++ -*-
+// Utility subroutines for the C++ library testsuite. 
+//
+// Copyright (C) 2000-2014 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/>.
+//
+
+#ifndef _GLIBCXX_TESTSUITE_NEW_OPERATORS_H
+#define _GLIBCXX_TESTSUITE_NEW_OPERATORS_H
+
+#include <new>
+
+namespace __gnu_test
+{
+  std::size_t&
+  get_new_limit()
+  {
+    static std::size_t limit = 1024 * 1024;
+    return limit;
+  }
+
+  void
+  set_new_limit(std::size_t l)
+  { get_new_limit() = l; }
+}
+
+void* operator new(std::size_t size) throw(std::bad_alloc)
+{
+  if (size > __gnu_test::get_new_limit())
+    throw std::bad_alloc();
+
+  void* p = std::malloc(size);
+  if (!p)
+    throw std::bad_alloc();
+
+  return p;
+}
+
+void* operator new (std::size_t size, const std::nothrow_t&) throw()
+{
+  if (size > __gnu_test::get_new_limit())
+    return 0;
+
+  return std::malloc(size);
+}
+
+void operator delete(void* p) throw()
+{
+  if (p)
+    std::free(p);
+}
+
+#endif // _GLIBCXX_TESTSUITE_NEW_OPERATORS_H
+
+