[libc++] Add tests to make sure that stable algorithms work without memory available

[ldionne]

libcxx/test/std/algorithms/alg.modifying.operations/alg.partitions/stable_partition.pass.cpp

298

I think you want ->reset() here instead.

300

Same problem below as well.

libcxx/test/std/algorithms/alg.sorting/alg.merge/inplace_merge.pass.cpp

115–118

Indentation is wrong. Please also enclose this in braces to clearly delimit that it's a test of its own.

libcxx/test/support/count_new.h

423–429

Just to clarify, this is temporary to figure out whether that is what's causing the AIX issues right?

[philnik]

Address comments

[philnik]

libcxx/test/support/count_new.h

423–429

Yes, this was a test - and that test failed.

[ldionne]

LGTM but please don't forget to undo the temporary changes.

@power-llvm-team Could someone please have a look at the failures on AIX? We suspect those are related to how the linker handles weak defs being overridden in a user program. I ran into similar issues here: https://github.com/llvm/llvm-project/blob/main/libcxx/test/std/language.support/support.dynamic/new.delete/new.delete.single/new.size_align_nothrow.replace.indirect.pass.cpp#L16

libcxx/utils/ci/buildkite-pipeline.yml

34 ↗

(On Diff #531478)

You need to get rid of this diff before shipping!

libcxx/include/__algorithm/stable_partition.h

__second_half_done:
     //         |
 }
 
 template <class _AlgPolicy, class _Predicate, class _ForwardIterator>
 _LIBCPP_HIDE_FROM_ABI _ForwardIterator
 __stable_partition_impl(_ForwardIterator __first, _ForwardIterator __last, _Predicate __pred,
                    forward_iterator_tag)
 {
-    const unsigned __alloc_limit = 3;  // might want to make this a function of trivial assignment
+    typedef typename iterator_traits<_ForwardIterator>::difference_type difference_type;
+    typedef typename iterator_traits<_ForwardIterator>::value_type value_type;
+
+    const difference_type __alloc_limit = 3;  // might want to make this a function of trivial assignment
     // Either prove all true and return __first or point to first false
     while (true)
     {
         if (__first == __last)
             return __first;
         if (!__pred(*__first))
             break;
         ++__first;
     }
     // We now have a reduced range [__first, __last)
     // *__first is known to be false
-    typedef typename iterator_traits<_ForwardIterator>::difference_type difference_type;
-    typedef typename iterator_traits<_ForwardIterator>::value_type value_type;
     difference_type __len = _IterOps<_AlgPolicy>::distance(__first, __last);
     pair<value_type*, ptrdiff_t> __p(0, 0);
     unique_ptr<value_type, __return_temporary_buffer> __h;
     if (__len >= __alloc_limit)
     {
 // TODO: Remove the use of std::get_temporary_buffer
 _LIBCPP_SUPPRESS_DEPRECATED_PUSH
         __p = _VSTD::get_temporary_buffer<value_type>(__len);

libcxx/test/std/algorithms/alg.modifying.operations/alg.partitions/stable_partition.pass.cpp

 //   requires ShuffleIterator<Iter>
 //         && CopyConstructible<Pred>
 //   Iter
 //   stable_partition(Iter first, Iter last, Pred pred);
 
 #include <algorithm>
 #include <cassert>
 #include <memory>
+#include <vector>
 
-#include "test_macros.h"
+#include "count_new.h"
 #include "test_iterators.h"
+#include "test_macros.h"
 
 struct is_odd
 {
     bool operator()(const int& i) const {return i & 1;}
 };
 
 struct odd_first
 {
     bool operator()(const std::pair<int,int>& p) const
         {return p.first & 1;}
 };
 
 template <class Iter>
 void
 test()
 {
-    {  // check mixed
+  { // check mixed
     typedef std::pair<int,int> P;
     P array[] =
     {
         P(0, 1),
         P(0, 2),
         P(1, 1),
         P(1, 2),
         P(2, 1),
test()
     assert(array[2] == P(3, 1));
     assert(array[3] == P(3, 2));
     assert(array[4] == P(0, 1));
     assert(array[5] == P(0, 2));
     assert(array[6] == P(2, 1));
     assert(array[7] == P(2, 2));
     assert(array[8] == P(4, 1));
     assert(array[9] == P(4, 2));
-    }
-    {
     typedef std::pair<int,int> P;
     P array[] =
     {
         P(0, 1),
         P(0, 2),
         P(1, 1),
         P(1, 2),
         P(2, 1),
test()
     // check one true
     r = std::stable_partition(Iter(array), Iter(array+1), odd_first());
     assert(base(r) == array+1);
     assert(array[0] == P(1, 1));
     // check one false
     r = std::stable_partition(Iter(array+4), Iter(array+5), odd_first());
     assert(base(r) == array+4);
     assert(array[4] == P(0, 1));
-    }
-    {  // check all false
+  { // check all false
     typedef std::pair<int,int> P;
     P array[] =
     {
         P(0, 1),
         P(0, 2),
         P(2, 1),
         P(2, 2),
         P(4, 1),
test()
     assert(array[2] == P(2, 1));
     assert(array[3] == P(2, 2));
     assert(array[4] == P(4, 1));
     assert(array[5] == P(4, 2));
     assert(array[6] == P(6, 1));
     assert(array[7] == P(6, 2));
     assert(array[8] == P(8, 1));
     assert(array[9] == P(8, 2));
-    }
-    {  // check all true
+  { // check all true
     typedef std::pair<int,int> P;
     P array[] =
     {
         P(1, 1),
         P(1, 2),
         P(3, 1),
         P(3, 2),
         P(5, 1),
test()
     assert(array[2] == P(3, 1));
     assert(array[3] == P(3, 2));
     assert(array[4] == P(5, 1));
     assert(array[5] == P(5, 2));
     assert(array[6] == P(7, 1));
     assert(array[7] == P(7, 2));
     assert(array[8] == P(9, 1));
     assert(array[9] == P(9, 2));
-    }
-    {  // check all false but first true
+  { // check all false but first true
     typedef std::pair<int,int> P;
     P array[] =
     {
         P(1, 1),
         P(0, 2),
         P(2, 1),
         P(2, 2),
         P(4, 1),
test()
     assert(array[2] == P(2, 1));
     assert(array[3] == P(2, 2));
     assert(array[4] == P(4, 1));
     assert(array[5] == P(4, 2));
     assert(array[6] == P(6, 1));
     assert(array[7] == P(6, 2));
     assert(array[8] == P(8, 1));
     assert(array[9] == P(8, 2));
-    }
-    {  // check all false but last true
+  { // check all false but last true
     typedef std::pair<int,int> P;
     P array[] =
     {
         P(0, 1),
         P(0, 2),
         P(2, 1),
         P(2, 2),
         P(4, 1),
test()
     assert(array[2] == P(0, 2));
     assert(array[3] == P(2, 1));
     assert(array[4] == P(2, 2));
     assert(array[5] == P(4, 1));
     assert(array[6] == P(4, 2));
     assert(array[7] == P(6, 1));
     assert(array[8] == P(6, 2));
     assert(array[9] == P(8, 1));
-    }
-    {  // check all true but first false
+  { // check all true but first false
     typedef std::pair<int,int> P;
     P array[] =
     {
         P(0, 1),
         P(1, 2),
         P(3, 1),
         P(3, 2),
         P(5, 1),
test()
     assert(array[2] == P(3, 2));
     assert(array[3] == P(5, 1));
     assert(array[4] == P(5, 2));
     assert(array[5] == P(7, 1));
     assert(array[6] == P(7, 2));
     assert(array[7] == P(9, 1));
     assert(array[8] == P(9, 2));
     assert(array[9] == P(0, 1));
-    }
-    {  // check all true but last false
+  { // check all true but last false
     typedef std::pair<int,int> P;
     P array[] =
     {
         P(1, 1),
         P(1, 2),
         P(3, 1),
         P(3, 2),
         P(5, 1),
test()
     assert(array[2] == P(3, 1));
     assert(array[3] == P(3, 2));
     assert(array[4] == P(5, 1));
     assert(array[5] == P(5, 2));
     assert(array[6] == P(7, 1));
     assert(array[7] == P(7, 2));
     assert(array[8] == P(9, 1));
     assert(array[9] == P(0, 2));
-    }
+#if TEST_STD_VER >= 11 && !defined(TEST_HAS_NO_EXCEPTIONS)
+  { // check that the algorithm still works when no memory is available
+    std::vector<int> vec(150, 3);
+    vec[5]                             = 6;
+    getGlobalMemCounter()->throw_after = 0;
+    std::stable_partition(vec.begin(), vec.end(), [](int i) { return i < 5; });
+    assert(std::is_partitioned(vec.begin(), vec.end(), [](int i) { return i < 5; }));
+    vec[5]                             = 6;
+    getGlobalMemCounter()->throw_after = 0;
+    std::stable_partition(
+        forward_iterator<int*>(vec.data()), forward_iterator<int*>(vec.data() + vec.size()), [](int i) {
+          return i < 5;
+        });
+    assert(std::is_partitioned(vec.begin(), vec.end(), [](int i) { return i < 5; }));
+    getGlobalMemCounter()->reset();
+  }
+#endif // TEST_STD_VER >= 11 && !defined(TEST_HAS_NO_EXCEPTIONS)
 }
 
 #if TEST_STD_VER >= 11
 
 struct is_null
 {
     template <class P>
         bool operator()(const P& p) {return p == 0;}

libcxx/test/std/algorithms/alg.sorting/alg.merge/inplace_merge.pass.cpp

 //===----------------------------------------------------------------------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 
 // <algorithm>
 
 // template<BidirectionalIterator Iter>
 //   requires ShuffleIterator<Iter>
 //         && LessThanComparable<Iter::value_type>
 //   void
 //   inplace_merge(Iter first, Iter middle, Iter last);
 
+// XFAIL: LIBCXX-AIX-FIXME
+
 #include <algorithm>
-#include <random>
 #include <cassert>
+#include <random>
+#include <vector>
 
-#include "test_macros.h"
+#include "count_new.h"
 #include "test_iterators.h"
+#include "test_macros.h"
 
 #if TEST_STD_VER >= 11
 struct S {
     S() : i_(0) {}
     S(int i) : i_(i) {}
 
     S(const S&  rhs) : i_(rhs.i_) {}
     S(      S&& rhs) : i_(rhs.i_) { rhs.i_ = -1; }
int main(int, char**)
     test<bidirectional_iterator<int*> >();
     test<random_access_iterator<int*> >();
     test<int*>();
 
 #if TEST_STD_VER >= 11
     test<bidirectional_iterator<S*> >();
     test<random_access_iterator<S*> >();
     test<S*>();
-#endif // TEST_STD_VER >= 11
+#endif
+
+#if TEST_STD_VER >= 11 && !defined(TEST_HAS_NO_EXCEPTIONS)
+    {
+        std::vector<int> vec(150, 3);
+        getGlobalMemCounter()->throw_after = 0;
+        std::inplace_merge(vec.begin(), vec.begin() + 100, vec.end());
+        assert(std::all_of(vec.begin(), vec.end(), [](int i) { return i == 3; }));
+    }
+#endif // TEST_STD_VER >= 11 && !defined(TEST_HAS_NO_EXCEPTIONS)
 
   return 0;
 }

libcxx/test/std/algorithms/alg.sorting/alg.sort/stable.sort/stable_sort.pass.cpp

 
 // template<RandomAccessIterator Iter>
 //   requires ShuffleIterator<Iter>
 //         && LessThanComparable<Iter::value_type>
 //   void
 //   stable_sort(Iter first, Iter last);
 
 #include <algorithm>
+#include <cassert>
 #include <iterator>
 #include <random>
-#include <cassert>
 
+#include "count_new.h"
 #include "test_macros.h"
 
 std::mt19937 randomness;
 
 template <class RI>
 void
 test_sort_helper(RI f, RI l)
 {
int main(int, char**)
     test_larger_sorts(256);
     test_larger_sorts(257);
     test_larger_sorts(499);
     test_larger_sorts(500);
     test_larger_sorts(997);
     test_larger_sorts(1000);
     test_larger_sorts(1009);
 
+#if !defined(TEST_HAS_NO_EXCEPTIONS)
+    { // check that the algorithm works without memory
+        std::vector<int> vec(150, 3);
+        getGlobalMemCounter()->throw_after = 0;
+        std::stable_sort(vec.begin(), vec.end());
+    }
+#endif // !defined(TEST_HAS_NO_EXCEPTIONS)
+
   return 0;
 }

libcxx/test/support/count_new.h

 //===----------------------------------------------------------------------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef COUNT_NEW_H
 #define COUNT_NEW_H
 
-# include <cstdlib>
-# include <cassert>
-# include <new>
+#include <algorithm>
+#include <cassert>
+#include <cstdlib>
+#include <new>
 #include <type_traits>
 
 #include "test_macros.h"
 
 #if defined(TEST_HAS_SANITIZERS)
 #define DISABLE_NEW_COUNT
 #endif
 
public:
     std::size_t last_new_array_size;
     std::size_t last_new_array_align;
     std::size_t last_delete_array_align;
 
 public:
     void newCalled(std::size_t s)
     {
         assert(disable_allocations == false);
-        assert(s);
         if (throw_after == 0) {
             throw_after = never_throw_value;
             detail::throw_bad_alloc_helper();
         } else if (throw_after != never_throw_value) {
             --throw_after;
         }
         ++new_called;
         ++outstanding_new;
void alignedDeleteCalled(void *p, std::size_t a) {
       deleteCalled(p);
       ++aligned_delete_called;
       last_delete_align = a;
     }
 
     void newArrayCalled(std::size_t s)
     {
         assert(disable_allocations == false);
-        assert(s);
         if (throw_after == 0) {
             throw_after = never_throw_value;
             detail::throw_bad_alloc_helper();
         } else {
             // don't decrement throw_after here. newCalled will end up doing that.
         }
         ++outstanding_array_new;
         ++new_array_called;

 #if defined(_LIBCPP_MSVCRT_LIKE) || \
   (!defined(_LIBCPP_VERSION) && defined(_WIN32))
 #define USE_ALIGNED_ALLOC
 #endif
 
 void* operator new(std::size_t s, std::align_val_t av) TEST_THROW_SPEC(std::bad_alloc) {
   const std::size_t a = static_cast<std::size_t>(av);
   getGlobalMemCounter()->alignedNewCalled(s, a);
-  void *ret;
+  void *ret = nullptr;
 #ifdef USE_ALIGNED_ALLOC
   ret = _aligned_malloc(s, a);
 #else
-  posix_memalign(&ret, a, s);
+  assert(posix_memalign(&ret, std::max(a, sizeof(void*)), s) != EINVAL);
 #endif
   if (ret == nullptr)
     detail::throw_bad_alloc_helper();
   return ret;
 }
 
 void operator delete(void *p, std::align_val_t av) TEST_NOEXCEPT {
   const std::size_t a = static_cast<std::size_t>(av);
   getGlobalMemCounter()->alignedDeleteCalled(p, a);
   if (p) {
 #ifdef USE_ALIGNED_ALLOC
     ::_aligned_free(p);
 #else
     ::free(p);
 #endif
   }
 }
 
 void* operator new[](std::size_t s, std::align_val_t av) TEST_THROW_SPEC(std::bad_alloc) {
   const std::size_t a = static_cast<std::size_t>(av);
   getGlobalMemCounter()->alignedNewArrayCalled(s, a);