[libc++] Adds missing forward_list merge tests.

[Mordante]

Summary

During the review of D112660 it turned out the tests for
std::forward_list::merge are incomplete.

Adds tests for the rvalue reference overloads. The tests are extended to
better test the Effects [forward.list.ops]/25 and Remarks
[forward.list.ops]/27 of the function:

• x is empty after the merge.
• Pointers and references to the moved elements of x now refer to those same elements but as members of *this.
• Iterators referring to the moved elements will continue to refer to their elements, but they now behave as iterators into *this, not into x.
• The algorithm is stable.

[• Quuxplusone]

LGTM assuming these tests are all basically copied from the std::list tests.

libcxx/test/std/containers/sequences/forwardlist/forwardlist.ops/merge_lvalue_pred.pass.cpp

65

I assume this is copied from an existing test, because otherwise typedef T* P; is certainly overkill. ;) No complaints if we're just matching somewhere else, though.

libcxx/test/std/containers/sequences/forwardlist/forwardlist.ops/merge_rvalue.pass.cpp

9

Honestly this probably works in c++03 mode, too, doesn't it?

[ldionne]

Thanks for increasing our coverage!

[Mordante]

libcxx/test/std/containers/sequences/forwardlist/forwardlist.ops/merge_lvalue_pred.pass.cpp

65

It was copied/moved from merge_pred.pass.cpp. I added the P just for consistency, but I agree it's a bit of overkill.

libcxx/test/std/containers/sequences/forwardlist/forwardlist.ops/merge_rvalue.pass.cpp

9

No it doesn't forward_list:837

#ifndef _LIBCPP_CXX03_LANG
    _LIBCPP_INLINE_VISIBILITY
    void merge(forward_list&& __x) {merge(__x, __less<value_type>());}
    template <class _Compare>
        _LIBCPP_INLINE_VISIBILITY
        void merge(forward_list&& __x, _Compare __comp)
        {merge(__x, _VSTD::move(__comp));}
#endif // _LIBCPP_CXX03_LANG

But judging by your question and your recent commits I guess I'll test whether this code can be made available in C++03. Obviously that will be in a separate patch.
(At least I will fix the horrible indention.)

libcxx/test/std/containers/sequences/forwardlist/forwardlist.ops/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
-//
-//===----------------------------------------------------------------------===//
-
-// <forward_list>
-
-// void merge(forward_list&& x);
-
-#include <forward_list>
-#include <iterator>
-#include <cassert>
-
-#include "test_macros.h"
-#include "min_allocator.h"
-
-int main(int, char**)
-{
-    {
-        typedef int T;
-        typedef std::forward_list<T> C;
-        const T t1[] = {3, 5, 6, 7, 12, 13};
-        const T t2[] = {0, 1, 2, 4, 8, 9, 10, 11, 14, 15};
-        const T t3[] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15};
-        C c1(std::begin(t1), std::end(t1));
-        C c2(std::begin(t2), std::end(t2));
-        c1.merge(c2);
-        C c3(std::begin(t3), std::end(t3));
-        assert(c1 == c3);
-    }
-#if TEST_STD_VER >= 11
-    {
-        typedef int T;
-        typedef std::forward_list<T, min_allocator<T>> C;
-        const T t1[] = {3, 5, 6, 7, 12, 13};
-        const T t2[] = {0, 1, 2, 4, 8, 9, 10, 11, 14, 15};
-        const T t3[] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15};
-        C c1(std::begin(t1), std::end(t1));
-        C c2(std::begin(t2), std::end(t2));
-        c1.merge(c2);
-        C c3(std::begin(t3), std::end(t3));
-        assert(c1 == c3);
-    }
-#endif
-
-  return 0;
-}

libcxx/test/std/containers/sequences/forwardlist/forwardlist.ops/merge_lvalue.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
+//
+//===----------------------------------------------------------------------===//
+
+// <forward_list>
+
+// void merge(forward_list& x);
+
+#include <forward_list>
+#include <iterator>
+#include <vector>
+#include <cassert>
+
+#include "test_macros.h"
+#include "min_allocator.h"
+
+#if TEST_STD_VER >= 11
+#  include <functional>
+#endif
+
+/// Helper struct to test a stable sort.
+///
+/// relation comparison uses a.
+/// equality comparison uses a and b.
+struct value {
+  int a;
+  int b;
+
+  friend bool operator<(const value& lhs, const value& rhs) { return lhs.a < rhs.a; }
+  friend bool operator==(const value& lhs, const value& rhs) { return lhs.a == rhs.a && lhs.b == rhs.b; }
+};
+
+int main(int, char**) {
+  { // Basic merge operation.
+    typedef int T;
+    typedef std::forward_list<T> C;
+    const T t1[] = {3, 5, 6, 7, 12, 13};
+    const T t2[] = {0, 1, 2, 4, 8, 9, 10, 11, 14, 15};
+    const T t3[] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15};
+
+    C c1(std::begin(t1), std::end(t1));
+    C c2(std::begin(t2), std::end(t2));
+    c1.merge(c2);
+    assert(c2.empty());
+
+    C c3(std::begin(t3), std::end(t3));
+    assert(c1 == c3);
+  }
+  { // Pointers, references, and iterators should remain valid after merging.
+    typedef int T;
+    typedef std::forward_list<T> C;
+    typedef T* P;
+    typedef typename C::iterator I;
+    const T to[3] = {0, 1, 2};
+
+    C c2(std::begin(to), std::end(to));
+    I io[3] = {c2.begin(), ++c2.begin(), ++ ++c2.begin()};
+#if TEST_STD_VER >= 11
+    std::reference_wrapper<T> ro[3] = {*io[0], *io[1], *io[2]};
+#endif
+    P po[3] = {&*io[0], &*io[1], &*io[2]};
+
+    C c1;
+    c1.merge(c2);
+    assert(c2.empty());
+
+    for (size_t i = 0; i < 3; ++i) {
+      assert(to[i] == *io[i]);
+#if TEST_STD_VER >= 11
+      assert(to[i] == ro[i].get());
+#endif
+      assert(to[i] == *po[i]);
+    }
+  }
+  { // Sorting is stable.
+    typedef value T;
+    typedef std::forward_list<T> C;
+    const T t1[] = {{0, 0}, {2, 0}, {3, 0}};
+    const T t2[] = {{0, 1}, {1, 1}, {2, 1}, {4, 1}};
+    const T t3[] = {{0, 0}, {0, 1}, {1, 1}, {2, 0}, {2, 1}, {3, 0}, {4, 1}};
+
+    C c1(std::begin(t1), std::end(t1));
+    C c2(std::begin(t2), std::end(t2));
+    c1.merge(c2);
+    assert(c2.empty());
+
+    C c3(std::begin(t3), std::end(t3));
+    assert(c1 == c3);
+  }
+#if TEST_STD_VER >= 11
+  { // Test with a different allocator.
+    typedef int T;
+    typedef std::forward_list<T, min_allocator<T>> C;
+    const T t1[] = {3, 5, 6, 7, 12, 13};
+    const T t2[] = {0, 1, 2, 4, 8, 9, 10, 11, 14, 15};
+    const T t3[] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15};
+
+    C c1(std::begin(t1), std::end(t1));
+    C c2(std::begin(t2), std::end(t2));
+    c1.merge(c2);
+    assert(c2.empty());
+
+    C c3(std::begin(t3), std::end(t3));
+    assert(c1 == c3);
+  }
+#endif
+
+  return 0;
+}

libcxx/test/std/containers/sequences/forwardlist/forwardlist.ops/merge_lvalue_pred.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
+//
+//===----------------------------------------------------------------------===//
+
+// <forward_list>
+
+// template <class Compare> void merge(forward_list& x, Compare comp);
+
+#include <forward_list>
+#include <iterator>
+#include <vector>
+#include <cassert>
+
+#include "test_macros.h"
+#include "min_allocator.h"
+
+#if TEST_STD_VER >= 11
+#  include <functional>
+#endif
+
+/// Helper for testing a stable sort.
+///
+/// The relation operator uses \ref a.
+/// The equality operator uses \ref a and \ref b.
+struct value {
+  int a;
+  int b;
+
+  friend bool operator>(const value& lhs, const value& rhs) { return lhs.a > rhs.a; }
+  friend bool operator==(const value& lhs, const value& rhs) { return lhs.a == rhs.a && lhs.b == rhs.b; }
+};
+
+int main(int, char**) {
+  { // Basic merge operation.
+    typedef int T;
+    typedef std::forward_list<T> C;
+    const T t1[] = {13, 12, 7, 6, 5, 3};
+    const T t2[] = {15, 14, 11, 10, 9, 8, 4, 2, 1, 0};
+    const T t3[] = {15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0};
+
+    C c1(std::begin(t1), std::end(t1));
+    C c2(std::begin(t2), std::end(t2));
+    c1.merge(c2, std::greater<T>());
+    assert(c2.empty());
+
+    C c3(std::begin(t3), std::end(t3));
+    assert(c1 == c3);
+  }
+  { // Pointers, references, and iterators should remain valid after merging.
+    typedef int T;
+    typedef std::forward_list<T> C;
+    typedef T* P;
+    typedef typename C::iterator I;
+    const T to[3] = {2, 1, 0};
+
+    C c2(std::begin(to), std::end(to));
+    I io[3] = {c2.begin(), ++c2.begin(), ++ ++c2.begin()};
+#if TEST_STD_VER >= 11
+    std::reference_wrapper<T> ro[3] = {*io[0], *io[1], *io[2]};
+#endif
+    P po[3] = {&*io[0], &*io[1], &*io[2]};
+
+    C c1;
+    c1.merge(c2, std::greater<T>());
+    assert(c2.empty());
+
+    for (size_t i = 0; i < 3; ++i) {
+      assert(to[i] == *io[i]);
+#if TEST_STD_VER >= 11
+      assert(to[i] == ro[i].get());
+#endif
+      assert(to[i] == *po[i]);
+    }
+  }
+  { // Sorting is stable.
+    typedef value T;
+    typedef std::forward_list<T> C;
+    const T t1[] = {{3, 0}, {2, 0}, {0, 0}};
+    const T t2[] = {{4, 1}, {2, 1}, {1, 1}, {0, 1}};
+    const T t3[] = {{4, 1}, {3, 0}, {2, 0}, {2, 1}, {1, 1}, {0, 0}, {0, 1}};
+
+    C c1(std::begin(t1), std::end(t1));
+    C c2(std::begin(t2), std::end(t2));
+    c1.merge(c2, std::greater<T>());
+    assert(c2.empty());
+
+    C c3(std::begin(t3), std::end(t3));
+    assert(c1 == c3);
+  }
+
+#if TEST_STD_VER >= 11
+  { // Test with a different allocator.
+    typedef int T;
+    typedef std::forward_list<T, min_allocator<T>> C;
+    const T t1[] = {13, 12, 7, 6, 5, 3};
+    const T t2[] = {15, 14, 11, 10, 9, 8, 4, 2, 1, 0};
+    const T t3[] = {15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0};
+
+    C c1(std::begin(t1), std::end(t1));
+    C c2(std::begin(t2), std::end(t2));
+    c1.merge(c2, std::greater<T>());
+    assert(c2.empty());
+
+    C c3(std::begin(t3), std::end(t3));
+    assert(c1 == c3);
+  }
+#endif
+
+  return 0;
+}

libcxx/test/std/containers/sequences/forwardlist/forwardlist.ops/merge_pred.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
-//
-//===----------------------------------------------------------------------===//
-
-// <forward_list>
-
-// template <class Compare> void merge(forward_list&& x, Compare comp);
-
-#include <forward_list>
-#include <iterator>
-#include <functional>
-#include <cassert>
-
-#include "test_macros.h"
-#include "min_allocator.h"
-
-int main(int, char**)
-{
-    {
-        typedef int T;
-        typedef std::forward_list<T> C;
-        const T t1[] = {13, 12, 7, 6, 5, 3};
-        const T t2[] = {15, 14, 11, 10, 9, 8, 4, 2, 1, 0};
-        const T t3[] = {15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0};
-        C c1(std::begin(t1), std::end(t1));
-        C c2(std::begin(t2), std::end(t2));
-        c1.merge(c2, std::greater<T>());
-        C c3(std::begin(t3), std::end(t3));
-        assert(c1 == c3);
-    }
-#if TEST_STD_VER >= 11
-    {
-        typedef int T;
-        typedef std::forward_list<T, min_allocator<T>> C;
-        const T t1[] = {13, 12, 7, 6, 5, 3};
-        const T t2[] = {15, 14, 11, 10, 9, 8, 4, 2, 1, 0};
-        const T t3[] = {15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0};
-        C c1(std::begin(t1), std::end(t1));
-        C c2(std::begin(t2), std::end(t2));
-        c1.merge(c2, std::greater<T>());
-        C c3(std::begin(t3), std::end(t3));
-        assert(c1 == c3);
-    }
-#endif
-
-  return 0;
-}

libcxx/test/std/containers/sequences/forwardlist/forwardlist.ops/merge_rvalue.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
+//
+//===----------------------------------------------------------------------===//
+
+// UNSUPPORTED: c++03
+
+// <forward_list>
+
+// void merge(forward_list&& x);
+
+#include <forward_list>
+#include <functional>
+#include <iterator>
+#include <vector>
+#include <cassert>
+
+#include "test_macros.h"
+#include "min_allocator.h"
+
+/// Helper for testing a stable sort.
+///
+/// The relation operator uses \ref a.
+/// The equality operator uses \ref a and \ref b.
+struct value {
+  int a;
+  int b;
+
+  friend bool operator<(const value& lhs, const value& rhs) { return lhs.a < rhs.a; }
+  friend bool operator==(const value& lhs, const value& rhs) { return lhs.a == rhs.a && lhs.b == rhs.b; }
+};
+
+int main(int, char**) {
+  { // Basic merge operation.
+    typedef int T;
+    typedef std::forward_list<T> C;
+    const T t1[] = {3, 5, 6, 7, 12, 13};
+    const T t2[] = {0, 1, 2, 4, 8, 9, 10, 11, 14, 15};
+    const T t3[] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15};
+
+    C c1(std::begin(t1), std::end(t1));
+    C c2(std::begin(t2), std::end(t2));
+    c1.merge(std::move(c2));
+    assert(c2.empty());
+
+    C c3(std::begin(t3), std::end(t3));
+    assert(c1 == c3);
+  }
+  { // Pointers, references, and iterators should remain valid after merging.
+    typedef int T;
+    typedef std::forward_list<T> C;
+    typedef T* P;
+    typedef typename C::iterator I;
+    const T to[3] = {0, 1, 2};
+
+    C c2(std::begin(to), std::end(to));
+    I io[3] = {c2.begin(), ++c2.begin(), ++ ++c2.begin()};
+    std::reference_wrapper<T> ro[3] = {*io[0], *io[1], *io[2]};
+    P po[3] = {&*io[0], &*io[1], &*io[2]};
+
+    C c1;
+    c1.merge(std::move(c2));
+    assert(c2.empty());
+
+    for (size_t i = 0; i < 3; ++i) {
+      assert(to[i] == *io[i]);
+      assert(to[i] == ro[i].get());
+      assert(to[i] == *po[i]);
+    }
+  }
+  { // Sorting is stable.
+    typedef value T;
+    typedef std::forward_list<T> C;
+    const T t1[] = {{0, 0}, {2, 0}, {3, 0}};
+    const T t2[] = {{0, 1}, {1, 1}, {2, 1}, {4, 1}};
+    const T t3[] = {{0, 0}, {0, 1}, {1, 1}, {2, 0}, {2, 1}, {3, 0}, {4, 1}};
+
+    C c1(std::begin(t1), std::end(t1));
+    C c2(std::begin(t2), std::end(t2));
+    c1.merge(std::move(c2));
+    assert(c2.empty());
+
+    C c3(std::begin(t3), std::end(t3));
+    assert(c1 == c3);
+  }
+  { // Test with a different allocator.
+    typedef int T;
+    typedef std::forward_list<T, min_allocator<T>> C;
+    const T t1[] = {3, 5, 6, 7, 12, 13};
+    const T t2[] = {0, 1, 2, 4, 8, 9, 10, 11, 14, 15};
+    const T t3[] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15};
+
+    C c1(std::begin(t1), std::end(t1));
+    C c2(std::begin(t2), std::end(t2));
+    c1.merge(std::move(c2));
+    assert(c2.empty());
+
+    C c3(std::begin(t3), std::end(t3));
+    assert(c1 == c3);
+  }
+
+  return 0;
+}

libcxx/test/std/containers/sequences/forwardlist/forwardlist.ops/merge_rvalue_pred.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
+//
+//===----------------------------------------------------------------------===//
+
+// UNSUPPORTED: c++03
+
+// <forward_list>
+
+// template <class Compare> void merge(forward_list&& x, Compare comp);
+
+#include <forward_list>
+#include <functional>
+#include <iterator>
+#include <vector>
+#include <cassert>
+
+#include "test_macros.h"
+#include "min_allocator.h"
+
+/// Helper for testing a stable sort.
+///
+/// The relation operator uses \ref a.
+/// The equality operator uses \ref a and \ref b.
+struct value {
+  int a;
+  int b;
+
+  friend bool operator>(const value& lhs, const value& rhs) { return lhs.a > rhs.a; }
+  friend bool operator==(const value& lhs, const value& rhs) { return lhs.a == rhs.a && lhs.b == rhs.b; }
+};
+
+int main(int, char**) {
+  { // Basic merge operation.
+    typedef int T;
+    typedef std::forward_list<T> C;
+    const T t1[] = {13, 12, 7, 6, 5, 3};
+    const T t2[] = {15, 14, 11, 10, 9, 8, 4, 2, 1, 0};
+    const T t3[] = {15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0};
+
+    C c1(std::begin(t1), std::end(t1));
+    C c2(std::begin(t2), std::end(t2));
+    c1.merge(std::move(c2), std::greater<T>());
+    assert(c2.empty());
+
+    C c3(std::begin(t3), std::end(t3));
+    assert(c1 == c3);
+  }
+  { // Pointers, references, and iterators should remain valid after merging.
+    typedef int T;
+    typedef std::forward_list<T> C;
+    typedef T* P;
+    typedef typename C::iterator I;
+    const T to[3] = {2, 1, 0};
+
+    C c2(std::begin(to), std::end(to));
+    I io[3] = {c2.begin(), ++c2.begin(), ++ ++c2.begin()};
+    std::reference_wrapper<T> ro[3] = {*io[0], *io[1], *io[2]};
+    P po[3] = {&*io[0], &*io[1], &*io[2]};
+
+    C c1;
+    c1.merge(std::move(c2), std::greater<T>());
+    assert(c2.empty());
+
+    for (size_t i = 0; i < 3; ++i) {
+      assert(to[i] == *io[i]);
+      assert(to[i] == ro[i].get());
+      assert(to[i] == *po[i]);
+    }
+  }
+  { // Sorting is stable.
+    typedef value T;
+    typedef std::forward_list<T> C;
+    const T t1[] = {{3, 0}, {2, 0}, {0, 0}};
+    const T t2[] = {{4, 1}, {2, 1}, {1, 1}, {0, 1}};
+    const T t3[] = {{4, 1}, {3, 0}, {2, 0}, {2, 1}, {1, 1}, {0, 0}, {0, 1}};
+
+    C c1(std::begin(t1), std::end(t1));
+    C c2(std::begin(t2), std::end(t2));
+    c1.merge(std::move(c2), std::greater<T>());
+    assert(c2.empty());
+
+    C c3(std::begin(t3), std::end(t3));
+    assert(c1 == c3);
+  }
+
+  { // Test with a different allocator.
+    typedef int T;
+    typedef std::forward_list<T, min_allocator<T>> C;
+    const T t1[] = {13, 12, 7, 6, 5, 3};
+    const T t2[] = {15, 14, 11, 10, 9, 8, 4, 2, 1, 0};
+    const T t3[] = {15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0};
+
+    C c1(std::begin(t1), std::end(t1));
+    C c2(std::begin(t2), std::end(t2));
+    c1.merge(std::move(c2), std::greater<T>());
+    assert(c2.empty());
+
+    C c3(std::begin(t3), std::end(t3));
+    assert(c1 == c3);
+  }
+
+  return 0;
+}