[pstl] A fix for move placement-new (and destroy) allocated objects from raw memory.

https://reviews.llvm.org/D74123

The fix affects follow algorithms:
remove_if, unique, rotate, inplace_merge, partial_sort_copy, set_union, set_intersection, set_difference, set_symmetric_difference.

For "is_trivial" types there are no problems with "creating objects/clean-up"
For non-trivial types the algo results are also correct, but possible incorrect copying/moving "operator=" calls "by raw memory" within one of mentioned algo or incorrect destructor calls in the end of algo.

7 files changed, 240 insertions, 15 deletions

diff --git a/pstl/test/std/algorithms/alg.merge/inplace_merge.pass.cpp b/pstl/test/std/algorithms/alg.merge/inplace_merge.pass.cpp
index 74ecc0c5a706..f2cc4040bb1e 100644
--- a/pstl/test/std/algorithms/alg.merge/inplace_merge.pass.cpp
+++ b/pstl/test/std/algorithms/alg.merge/inplace_merge.pass.cpp
@@ -147,6 +147,13 @@ main()
 
     test_algo_basic_single<int32_t>(run_for_rnd_bi<test_non_const<int32_t>>());
 
+    test_by_type<MemoryChecker>(
+        [](std::size_t idx){ return MemoryChecker{std::int32_t(idx * 2)}; },
+        [](std::size_t idx){ return MemoryChecker{std::int32_t(idx * 2 + 1)}; },
+        [](const MemoryChecker& val1, const MemoryChecker& val2){ return val1.value() == val2.value(); });
+    EXPECT_FALSE(MemoryChecker::alive_objects() < 0, "wrong effect from inplace_merge: number of ctors calls < num of dtors calls");
+    EXPECT_FALSE(MemoryChecker::alive_objects() > 0, "wrong effect from inplace_merge: number of ctors calls > num of dtors calls");
+    
     std::cout << done() << std::endl;
     return 0;
 }
diff --git a/pstl/test/std/algorithms/alg.modifying.operations/remove.pass.cpp b/pstl/test/std/algorithms/alg.modifying.operations/remove.pass.cpp
index cb8b178417d7..c41a31d7310d 100644
--- a/pstl/test/std/algorithms/alg.modifying.operations/remove.pass.cpp
+++ b/pstl/test/std/algorithms/alg.modifying.operations/remove.pass.cpp
@@ -149,6 +149,13 @@ main()
 
     test_algo_basic_single<int32_t>(run_for_rnd_fw<test_non_const>());
 
+    test<MemoryChecker>(MemoryChecker{0}, MemoryChecker{1},
+        [](const MemoryChecker& val){ return val.value() == 1; },
+        [](std::size_t idx){ return MemoryChecker{std::int32_t(idx % 3 == 0)}; }
+    );
+    EXPECT_FALSE(MemoryChecker::alive_objects() < 0, "wrong effect from remove,remove_if: number of ctors calls < num of dtors calls");
+    EXPECT_FALSE(MemoryChecker::alive_objects() > 0, "wrong effect from remove,remove_if: number of ctors calls > num of dtors calls");
+    
     std::cout << done() << std::endl;
     return 0;
 }
diff --git a/pstl/test/std/algorithms/alg.modifying.operations/rotate.pass.cpp b/pstl/test/std/algorithms/alg.modifying.operations/rotate.pass.cpp
index 5eb242e6dd72..03f2b3cb2e87 100644
--- a/pstl/test/std/algorithms/alg.modifying.operations/rotate.pass.cpp
+++ b/pstl/test/std/algorithms/alg.modifying.operations/rotate.pass.cpp
@@ -167,6 +167,9 @@ main()
 {
     test<int32_t>();
     test<wrapper<float64_t>>();
+    test<MemoryChecker>();
+    EXPECT_FALSE(MemoryChecker::alive_objects() < 0, "wrong effect from rotate: number of ctors calls < num of dtors calls");
+    EXPECT_FALSE(MemoryChecker::alive_objects() > 0, "wrong effect from rotate: number of ctors calls > num of dtors calls");
 
     std::cout << done() << std::endl;
     return 0;
diff --git a/pstl/test/std/algorithms/alg.modifying.operations/unique.pass.cpp b/pstl/test/std/algorithms/alg.modifying.operations/unique.pass.cpp
index 79f5518ad2cb..2f68c00401fe 100644
--- a/pstl/test/std/algorithms/alg.modifying.operations/unique.pass.cpp
+++ b/pstl/test/std/algorithms/alg.modifying.operations/unique.pass.cpp
@@ -152,6 +152,12 @@ main()
 
     test_algo_basic_single<int32_t>(run_for_rnd_fw<test_non_const<int32_t>>());
 
+    test<MemoryChecker>(
+        [](std::size_t idx){ return MemoryChecker{std::int32_t(idx / 3)}; },
+        [](const MemoryChecker& val1, const MemoryChecker& val2){ return val1.value() == val2.value(); });
+    EXPECT_FALSE(MemoryChecker::alive_objects() < 0, "wrong effect from unique: number of ctors calls < num of dtors calls");
+    EXPECT_FALSE(MemoryChecker::alive_objects() > 0, "wrong effect from unique: number of ctors calls > num of dtors calls");
+    
     std::cout << done() << std::endl;
     return 0;
 }
diff --git a/pstl/test/std/algorithms/alg.sorting/alg.set.operations/set.pass.cpp b/pstl/test/std/algorithms/alg.sorting/alg.set.operations/set.pass.cpp
index 5b86dd5bdc27..c85d0e9244fc 100644
--- a/pstl/test/std/algorithms/alg.sorting/alg.set.operations/set.pass.cpp
+++ b/pstl/test/std/algorithms/alg.sorting/alg.set.operations/set.pass.cpp
@@ -51,7 +51,8 @@ struct Num
     }
 };
 
-struct test_one_policy
+template <typename Type>
+struct test_set_union
 {
     template <typename Policy, typename InputIterator1, typename InputIterator2, typename Compare>
     typename std::enable_if<!TestUtils::isReverse<InputIterator1>::value, void>::type
@@ -66,30 +67,101 @@ struct test_one_policy
         Sequence<T1> expect(n);
         Sequence<T1> out(n);
 
-        //1. set_union
         auto expect_res = std::set_union(first1, last1, first2, last2, expect.begin(), comp);
         auto res = std::set_union(exec, first1, last1, first2, last2, out.begin(), comp);
 
         EXPECT_TRUE(expect_res - expect.begin() == res - out.begin(), "wrong result for set_union");
         EXPECT_EQ_N(expect.begin(), out.begin(), std::distance(out.begin(), res), "wrong set_union effect");
+    }
 
-        //2. set_intersection
-        expect_res = std::set_intersection(first1, last1, first2, last2, expect.begin(), comp);
-        res = std::set_intersection(exec, first1, last1, first2, last2, out.begin(), comp);
+    template <typename Policy, typename InputIterator1, typename InputIterator2, typename Compare>
+    typename std::enable_if<TestUtils::isReverse<InputIterator1>::value, void>::type
+    operator()(Policy&& exec, InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2,
+               Compare comp)
+    {
+    }
+};
+
+template <typename Type>
+struct test_set_intersection
+{
+    template <typename Policy, typename InputIterator1, typename InputIterator2, typename Compare>
+    typename std::enable_if<!TestUtils::isReverse<InputIterator1>::value, void>::type
+    operator()(Policy&& exec, InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2,
+               Compare comp)
+    {
+        using T1 = typename std::iterator_traits<InputIterator1>::value_type;
+
+        auto n1 = std::distance(first1, last1);
+        auto n2 = std::distance(first2, last2);
+        auto n = n1 + n2;
+        Sequence<T1> expect(n);
+        Sequence<T1> out(n);
+
+        auto expect_res = std::set_intersection(first1, last1, first2, last2, expect.begin(), comp);
+        auto res = std::set_intersection(exec, first1, last1, first2, last2, out.begin(), comp);
 
         EXPECT_TRUE(expect_res - expect.begin() == res - out.begin(), "wrong result for set_intersection");
         EXPECT_EQ_N(expect.begin(), out.begin(), std::distance(out.begin(), res), "wrong set_intersection effect");
+    }
+
+    template <typename Policy, typename InputIterator1, typename InputIterator2, typename Compare>
+    typename std::enable_if<TestUtils::isReverse<InputIterator1>::value, void>::type
+    operator()(Policy&& exec, InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2,
+               Compare comp)
+    {
+    }
+};
 
-        //3. set_difference
-        expect_res = std::set_difference(first1, last1, first2, last2, expect.begin(), comp);
-        res = std::set_difference(exec, first1, last1, first2, last2, out.begin(), comp);
+template <typename Type>
+struct test_set_difference
+{
+    template <typename Policy, typename InputIterator1, typename InputIterator2, typename Compare>
+    typename std::enable_if<!TestUtils::isReverse<InputIterator1>::value, void>::type
+    operator()(Policy&& exec, InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2,
+               Compare comp)
+    {
+        using T1 = typename std::iterator_traits<InputIterator1>::value_type;
+
+        auto n1 = std::distance(first1, last1);
+        auto n2 = std::distance(first2, last2);
+        auto n = n1 + n2;
+        Sequence<T1> expect(n);
+        Sequence<T1> out(n);
+
+        auto expect_res = std::set_difference(first1, last1, first2, last2, expect.begin(), comp);
+        auto res = std::set_difference(exec, first1, last1, first2, last2, out.begin(), comp);
 
         EXPECT_TRUE(expect_res - expect.begin() == res - out.begin(), "wrong result for set_difference");
         EXPECT_EQ_N(expect.begin(), out.begin(), std::distance(out.begin(), res), "wrong set_difference effect");
+    }
+
+    template <typename Policy, typename InputIterator1, typename InputIterator2, typename Compare>
+    typename std::enable_if<TestUtils::isReverse<InputIterator1>::value, void>::type
+    operator()(Policy&& exec, InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2,
+               Compare comp)
+    {
+    }
+};
 
-        //4. set_symmetric_difference
-        expect_res = std::set_symmetric_difference(first1, last1, first2, last2, expect.begin(), comp);
-        res = std::set_symmetric_difference(exec, first1, last1, first2, last2, out.begin(), comp);
+template <typename Type>
+struct test_set_symmetric_difference
+{
+    template <typename Policy, typename InputIterator1, typename InputIterator2, typename Compare>
+    typename std::enable_if<!TestUtils::isReverse<InputIterator1>::value, void>::type
+    operator()(Policy&& exec, InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2,
+               Compare comp)
+    {
+        using T1 = typename std::iterator_traits<InputIterator1>::value_type;
+
+        auto n1 = std::distance(first1, last1);
+        auto n2 = std::distance(first2, last2);
+        auto n = n1 + n2;
+        Sequence<T1> expect(n);
+        Sequence<T1> out(n);
+
+        auto expect_res = std::set_symmetric_difference(first1, last1, first2, last2, expect.begin(), comp);
+        auto res = std::set_symmetric_difference(exec, first1, last1, first2, last2, out.begin(), comp);
 
         EXPECT_TRUE(expect_res - expect.begin() == res - out.begin(), "wrong result for set_symmetric_difference");
         EXPECT_EQ_N(expect.begin(), out.begin(), std::distance(out.begin(), res),
@@ -118,31 +190,68 @@ test_set(Compare compare)
         for (std::size_t m = 0; m < n_max; m = m <= 16 ? m + 1 : size_t(2.71828 * m))
         {
             //prepare the input ranges
-            Sequence<T1> in1(n, [](std::size_t k) { return rand() % (2 * k + 1); });
+            Sequence<T1> in1(n, [n](std::size_t k) { return rand() % (2 * k + 1); });
             Sequence<T2> in2(m, [m](std::size_t k) { return (m % 2) * rand() + rand() % (k + 1); });
 
             std::sort(in1.begin(), in1.end(), compare);
             std::sort(in2.begin(), in2.end(), compare);
 
-            invoke_on_all_policies(test_one_policy(), in1.begin(), in1.end(), in2.cbegin(), in2.cend(), compare);
+            invoke_on_all_policies(test_set_union<T1>(), in1.begin(), in1.end(), in2.cbegin(), in2.cend(),
+                                        compare);
+
+            invoke_on_all_policies(test_set_intersection<T1>(), in1.begin(), in1.end(), in2.cbegin(), in2.cend(),
+                                        compare);
+
+            invoke_on_all_policies(test_set_difference<T1>(), in1.begin(), in1.end(), in2.cbegin(), in2.cend(),
+                                        compare);
+
+            invoke_on_all_policies(test_set_symmetric_difference<T1>(), in1.begin(), in1.end(), in2.cbegin(),
+                                        in2.cend(), compare);
         }
     }
 }
 
 template <typename T>
-struct test_non_const
+struct test_non_const_set_difference
 {
     template <typename Policy, typename InputIterator, typename OutputInterator>
     void
     operator()(Policy&& exec, InputIterator input_iter, OutputInterator out_iter)
     {
         set_difference(exec, input_iter, input_iter, input_iter, input_iter, out_iter, non_const(std::less<T>()));
+    }
+};
 
+template <typename T>
+struct test_non_const_set_intersection
+{
+    template <typename Policy, typename InputIterator, typename OutputInterator>
+    void
+    operator()(Policy&& exec, InputIterator input_iter, OutputInterator out_iter)
+    {
         set_intersection(exec, input_iter, input_iter, input_iter, input_iter, out_iter, non_const(std::less<T>()));
+    }
+};
 
+template <typename T>
+struct test_non_const_set_symmetric_difference
+{
+    template <typename Policy, typename InputIterator, typename OutputInterator>
+    void
+    operator()(Policy&& exec, InputIterator input_iter, OutputInterator out_iter)
+    {
         set_symmetric_difference(exec, input_iter, input_iter, input_iter, input_iter, out_iter,
                                  non_const(std::less<T>()));
+    }
+};
 
+template <typename T>
+struct test_non_const_set_union
+{
+    template <typename Policy, typename InputIterator, typename OutputInterator>
+    void
+    operator()(Policy&& exec, InputIterator input_iter, OutputInterator out_iter)
+    {
         set_union(exec, input_iter, input_iter, input_iter, input_iter, out_iter, non_const(std::less<T>()));
     }
 };
@@ -154,7 +263,19 @@ main()
     test_set<float64_t, float64_t>(std::less<>());
     test_set<Num<int64_t>, Num<int32_t>>([](const Num<int64_t>& x, const Num<int32_t>& y) { return x < y; });
 
-    test_algo_basic_double<int32_t>(run_for_rnd_fw<test_non_const<int32_t>>());
+    test_set<MemoryChecker, MemoryChecker>([](const MemoryChecker& val1, const MemoryChecker& val2) -> bool {
+        return val1.value() < val2.value();
+    });
+    EXPECT_FALSE(MemoryChecker::alive_objects() < 0, "wrong effect from set algorithms: number of ctors calls < num of dtors calls");
+    EXPECT_FALSE(MemoryChecker::alive_objects() > 0, "wrong effect from set algorithms: number of ctors calls > num of dtors calls");
+
+    test_algo_basic_double<int32_t>(run_for_rnd_fw<test_non_const_set_difference<int32_t>>());
+
+    test_algo_basic_double<int32_t>(run_for_rnd_fw<test_non_const_set_intersection<int32_t>>());
+
+    test_algo_basic_double<int32_t>(run_for_rnd_fw<test_non_const_set_symmetric_difference<int32_t>>());
+
+    test_algo_basic_double<int32_t>(run_for_rnd_fw<test_non_const_set_union<int32_t>>());
 
     std::cout << done() << std::endl;
 
diff --git a/pstl/test/std/algorithms/alg.sorting/partial_sort_copy.pass.cpp b/pstl/test/std/algorithms/alg.sorting/partial_sort_copy.pass.cpp
index 3fe1d5ae4a12..ad0f0d6ef9b0 100644
--- a/pstl/test/std/algorithms/alg.sorting/partial_sort_copy.pass.cpp
+++ b/pstl/test/std/algorithms/alg.sorting/partial_sort_copy.pass.cpp
@@ -186,6 +186,11 @@ main()
 
     test_algo_basic_double<int32_t>(run_for_rnd<test_non_const<int32_t>>());
 
+    test_partial_sort_copy<MemoryChecker>(
+        [](const MemoryChecker& val1, const MemoryChecker& val2){ return val1.value() < val2.value(); });
+    EXPECT_FALSE(MemoryChecker::alive_objects() < 0, "wrong effect from partial_sort_copy: number of ctors calls < num of dtors calls");
+    EXPECT_FALSE(MemoryChecker::alive_objects() > 0, "wrong effect from partial_sort_copy: number of ctors calls > num of dtors calls");
+    
     std::cout << done() << std::endl;
     return 0;
 }
diff --git a/pstl/test/support/utils.h b/pstl/test/support/utils.h
index 541dc8c3f754..090f9377cece 100644
--- a/pstl/test/support/utils.h
+++ b/pstl/test/support/utils.h
@@ -231,6 +231,82 @@ fill_data(Iterator first, Iterator last, F f)
     }
 }
 
+struct MemoryChecker {
+    // static counters and state tags
+    static std::atomic<std::int64_t> alive_object_counter; // initialized outside
+    static constexpr std::int64_t alive_state = 0xAAAAAAAAAAAAAAAA;
+    static constexpr std::int32_t dead_state = 0; // only used as a set value to cancel alive_state
+
+    std::int32_t _value; // object value used for algorithms
+    std::int64_t _state; // state tag used for checks
+
+    // ctors, dtors, assign ops
+    explicit MemoryChecker(std::int32_t value = 0) : _value(value) {
+        // check for EXPECT_TRUE(state() != alive_state, ...) has not been done since we cannot guarantee that
+        // raw memory for object being constructed does not have a bit sequence being equal to alive_state
+
+        // set constructed state and increment counter for living object
+        inc_alive_objects();
+        _state = alive_state;
+    }
+    MemoryChecker(MemoryChecker&& other) : _value(other.value()) {
+        // check for EXPECT_TRUE(state() != alive_state, ...) has not been done since
+        // compiler can optimize out the move ctor call that results in false positive failure
+        EXPECT_TRUE(other.state() == alive_state, "wrong effect from MemoryChecker(MemoryChecker&&): attemp to construct an object from non-existing object");
+        // set constructed state and increment counter for living object
+        inc_alive_objects();
+        _state = alive_state;
+    }
+    MemoryChecker(const MemoryChecker& other) : _value(other.value()) {
+        // check for EXPECT_TRUE(state() != alive_state, ...) has not been done since
+        // compiler can optimize out the copy ctor call that results in false positive failure
+        EXPECT_TRUE(other.state() == alive_state, "wrong effect from MemoryChecker(const MemoryChecker&): attemp to construct an object from non-existing object");
+        // set constructed state and increment counter for living object
+        inc_alive_objects();
+        _state = alive_state;
+    }
+    MemoryChecker& operator=(MemoryChecker&& other) {
+        // check if we do not assign over uninitialized memory
+        EXPECT_TRUE(state() == alive_state, "wrong effect from MemoryChecker::operator=(MemoryChecker&& other): attemp to assign to non-existing object");
+        EXPECT_TRUE(other.state() == alive_state, "wrong effect from MemoryChecker::operator=(MemoryChecker&& other): attemp to assign from non-existing object");
+        // just assign new value, counter is the same, state is the same
+        _value = other.value();
+
+        return *this;
+    }
+    MemoryChecker& operator=(const MemoryChecker& other) {
+        // check if we do not assign over uninitialized memory
+        EXPECT_TRUE(state() == alive_state, "wrong effect from MemoryChecker::operator=(const MemoryChecker& other): attemp to assign to non-existing object");
+        EXPECT_TRUE(other.state() == alive_state, "wrong effect from MemoryChecker::operator=(const MemoryChecker& other): attemp to assign from non-existing object");
+        // just assign new value, counter is the same, state is the same
+        _value = other.value();
+
+        return *this;
+    }
+    ~MemoryChecker() {
+        // check if we do not double destruct the object
+        EXPECT_TRUE(state() == alive_state, "wrong effect from ~MemoryChecker(): attemp to destroy non-existing object");
+        // set destructed state and decrement counter for living object
+        static_cast<volatile std::int64_t&>(_state) = dead_state;
+        dec_alive_objects();
+    }
+
+    // getters
+    std::int32_t value() const { return _value; }
+    std::int64_t state() const { return _state; }
+    static std::int32_t alive_objects() { return alive_object_counter.load(); }
+private:
+    // setters
+    void inc_alive_objects() { alive_object_counter.fetch_add(1); }
+    void dec_alive_objects() { alive_object_counter.fetch_sub(1); }
+};
+
+std::atomic<std::int64_t> MemoryChecker::alive_object_counter{0};
+
+std::ostream& operator<<(std::ostream& os, const MemoryChecker& val) { return (os << val.value()); }
+bool operator==(const MemoryChecker& v1, const MemoryChecker& v2) { return v1.value() == v2.value(); }
+bool operator<(const MemoryChecker& v1, const MemoryChecker& v2) { return v1.value() < v2.value(); }
+
 // Sequence<T> is a container of a sequence of T with lots of kinds of iterators.
 // Prefixes on begin/end mean:
 //      c = "const"