Implement LWG-3918 std::uninitialized_move/_n and guaranteed copy elision (#5135)

frederick-vs-ja · StephanTLavavej · web-flow · commit 649a4f2d2b96 · 2024-12-04T22:47:45.000-08:00
Co-authored-by: Stephan T. Lavavej &lt;stl@nuwen.net&gt;
diff --git a/stl/inc/execution b/stl/inc/execution
@@ -137,11 +137,6 @@ template <>
 struct is_execution_policy<execution::unsequenced_policy> : true_type {};
 #endif // _HAS_CXX20
 
-template <class _Ty, class _FwdIt>
-void _Construct_in_place_by_deref(_Ty& _Val, const _FwdIt& _Iter) {
-    ::new (static_cast<void*>(_STD addressof(_Val))) _Ty(*_Iter);
-}
-
 template <class _Ty, class _UnaryOp, class _FwdIt>
 void _Construct_in_place_by_transform_deref(_Ty& _Val, _UnaryOp _Transform_op, const _FwdIt& _Iter) {
     ::new (static_cast<void*>(_STD addressof(_Val))) _Ty(_Transform_op(*_Iter));
diff --git a/stl/inc/memory b/stl/inc/memory
@@ -141,7 +141,7 @@ _NoThrowFwdIt uninitialized_copy_n(const _InIt _First, const _Diff _Count_raw, _
         _Uninitialized_backout<decltype(_UDest)> _Backout{_UDest};
 
         for (; _Count > 0; --_Count, (void) ++_UFirst) {
-            _Backout._Emplace_back(*_UFirst);
+            _Backout._Emplace_back_deref(_UFirst);
         }
 
         _UDest = _Backout._Release();
@@ -294,7 +294,7 @@ pair<_InIt, _NoThrowFwdIt> uninitialized_move_n(_InIt _First, const _Diff _Count
         _Uninitialized_backout<decltype(_UDest)> _Backout{_UDest};
 
         for (; _Count > 0; --_Count, (void) ++_UFirst) {
-            _Backout._Emplace_back(_STD move(*_UFirst));
+            _Backout._Emplace_back_deref_move(_UFirst);
         }
 
         _UDest = _Backout._Release();
diff --git a/stl/inc/xmemory b/stl/inc/xmemory
@@ -1601,6 +1601,12 @@ void _Return_temporary_buffer(_Ty* const _Pbuf) noexcept {
     }
 }
 
+template <class _Ty, class _InIt>
+void _Construct_in_place_by_deref(_Ty& _Val, const _InIt& _Iter)
+    noexcept(noexcept(::new (static_cast<void*>(_STD addressof(_Val))) _Ty(*_Iter))) {
+    ::new (static_cast<void*>(_STD addressof(_Val))) _Ty(*_Iter);
+}
+
 template <class _NoThrowFwdIt>
 struct _NODISCARD _Uninitialized_backout {
     // struct to undo partially constructed ranges in _Uninitialized_xxx algorithms
@@ -1625,26 +1631,43 @@ struct _NODISCARD _Uninitialized_backout {
         ++_Last;
     }
 
+    template <class _InIt>
+    void _Emplace_back_deref(const _InIt& _Iter) {
+        // construct a new element at *_Last from the result of dereferencing _Iter and increment.
+        _STD _Construct_in_place_by_deref(*_Last, _Iter);
+        ++_Last;
+    }
+
+    template <class _InIt>
+    void _Emplace_back_deref_move(const _InIt& _Iter) {
+        // construct a new element at *_Last from the result of dereferencing _Iter and increment,
+        // with lvalue cast to xvalue if necessary for uninitialized_move(_n).
+        if constexpr (is_lvalue_reference_v<decltype(*_Iter)>) {
+            _STD _Construct_in_place(*_Last, _STD move(*_Iter));
+        } else {
+            _STD _Construct_in_place_by_deref(*_Last, _Iter);
+        }
+        ++_Last;
+    }
+
     constexpr _NoThrowFwdIt _Release() { // suppress any exception handling backout and return _Last
         _First = _Last;
         return _Last;
     }
 };
 
 template <class _InIt, class _NoThrowFwdIt>
-_CONSTEXPR20 _NoThrowFwdIt _Uninitialized_move_unchecked(_InIt _First, const _InIt _Last, _NoThrowFwdIt _Dest) {
+_NoThrowFwdIt _Uninitialized_move_unchecked(_InIt _First, const _InIt _Last, _NoThrowFwdIt _Dest) {
     // move [_First, _Last) to raw [_Dest, ...)
     if constexpr (_Iter_move_cat<_InIt, _NoThrowFwdIt>::_Bitcopy_constructible) {
-#if _HAS_CXX20
+#if 0 // TRANSITION, _HAS_CXX26
         if (!_STD is_constant_evaluated())
-#endif // _HAS_CXX20
-        {
-            return _STD _Copy_memmove(_First, _Last, _Dest);
-        }
+#endif // _HAS_CXX26
+        { return _STD _Copy_memmove(_First, _Last, _Dest); }
     }
     _Uninitialized_backout<_NoThrowFwdIt> _Backout{_Dest};
     for (; _First != _Last; ++_First) {
-        _Backout._Emplace_back(_STD move(*_First));
+        _Backout._Emplace_back_deref_move(_First);
     }
 
     return _Backout._Release();
@@ -1905,20 +1928,18 @@ _CONSTEXPR20 _Alloc_ptr_t<_Alloc> _Uninitialized_copy_n(
 }
 
 template <class _InIt, class _NoThrowFwdIt>
-_CONSTEXPR20 _NoThrowFwdIt _Uninitialized_copy_unchecked(_InIt _First, const _InIt _Last, _NoThrowFwdIt _Dest) {
+_NoThrowFwdIt _Uninitialized_copy_unchecked(_InIt _First, const _InIt _Last, _NoThrowFwdIt _Dest) {
     // copy [_First, _Last) to raw [_Dest, ...)
     if constexpr (_Iter_copy_cat<_InIt, _NoThrowFwdIt>::_Bitcopy_constructible) {
-#if _HAS_CXX20
+#if 0 // TRANSITION, _HAS_CXX26
         if (!_STD is_constant_evaluated())
-#endif // _HAS_CXX20
-        {
-            return _STD _Copy_memmove(_First, _Last, _Dest);
-        }
+#endif // _HAS_CXX26
+        { return _STD _Copy_memmove(_First, _Last, _Dest); }
     }
 
     _Uninitialized_backout<_NoThrowFwdIt> _Backout{_Dest};
     for (; _First != _Last; ++_First) {
-        _Backout._Emplace_back(*_First);
+        _Backout._Emplace_back_deref(_First);
     }
 
     return _Backout._Release();
diff --git a/tests/std/tests/P0040R3_extending_memory_management_tools/test.cpp b/tests/std/tests/P0040R3_extending_memory_management_tools/test.cpp
@@ -58,6 +58,10 @@ template <typename T, size_t Count>
 struct uninitialized_storage {
     alignas(T) char storage[sizeof(T) * Count];
 
+    uninitialized_storage() {
+        fill(std::begin(storage), std::end(storage), fillChar);
+    }
+
     T* begin() {
         return &reinterpret_cast<T&>(storage);
     }
@@ -196,6 +200,122 @@ void test_destroy_n() {
     assert(g_alive == 0);
 }
 
+struct copy_elision_dest;
+
+class pinned {
+public:
+    explicit pinned(int n) : n_{n} {}
+
+    pinned(const pinned&)            = delete;
+    pinned& operator=(const pinned&) = delete;
+
+private:
+    friend copy_elision_dest;
+
+    int n_;
+};
+
+class pinned_ioterator {
+private:
+    struct arrow_proxy {
+        pinned val_;
+
+        pinned* operator->() {
+            return &val_;
+        }
+    };
+
+public:
+    using iterator_category = input_iterator_tag;
+    using difference_type   = int;
+    using value_type        = pinned;
+    using pointer           = arrow_proxy;
+    using reference         = pinned;
+
+    explicit pinned_ioterator(int n) : n_{n} {}
+
+    pinned operator*() const {
+        return pinned{n_};
+    }
+    pinned_ioterator& operator++() {
+        ++n_;
+        return *this;
+    }
+    pinned_ioterator operator++(int) {
+        auto old = *this;
+        ++*this;
+        return old;
+    }
+
+    arrow_proxy operator->() const {
+        return arrow_proxy{pinned{n_}};
+    }
+
+    friend bool operator==(pinned_ioterator i, pinned_ioterator j) {
+        return i.n_ == j.n_;
+    }
+#if !_HAS_CXX20
+    friend bool operator!=(pinned_ioterator i, pinned_ioterator j) {
+        return !(i == j);
+    }
+#endif // !_HAS_CXX20
+
+private:
+    int n_;
+};
+
+struct copy_elision_dest {
+    explicit copy_elision_dest(pinned x) : n_{x.n_} {}
+
+    int n_;
+};
+
+// std::uninitialized_copy/_n are required to perform guaranteed copy elision since C++17.
+void test_guaranteed_copy_elision_uninitialized_copy() {
+    constexpr int len = 42;
+
+    uninitialized_storage<copy_elision_dest, len> us;
+    uninitialized_copy(pinned_ioterator{0}, pinned_ioterator{len}, us.begin());
+    for (int i = 0; i != len; ++i) {
+        assert(us.begin()[i].n_ == i);
+    }
+    destroy(us.begin(), us.end());
+}
+
+void test_guaranteed_copy_elision_uninitialized_copy_n() {
+    constexpr int len = 42;
+
+    uninitialized_storage<copy_elision_dest, len> us;
+    uninitialized_copy_n(pinned_ioterator{0}, len, us.begin());
+    for (int i = 0; i != len; ++i) {
+        assert(us.begin()[i].n_ == i);
+    }
+    destroy(us.begin(), us.end());
+}
+
+// Also test LWG-3918 "std::uninitialized_move/_n and guaranteed copy elision".
+void test_guaranteed_copy_elision_uninitialized_move() {
+    constexpr int len = 42;
+
+    uninitialized_storage<copy_elision_dest, len> us;
+    uninitialized_move(pinned_ioterator{0}, pinned_ioterator{len}, us.begin());
+    for (int i = 0; i != len; ++i) {
+        assert(us.begin()[i].n_ == i);
+    }
+    destroy(us.begin(), us.end());
+}
+
+void test_guaranteed_copy_elision_uninitialized_move_n() {
+    constexpr int len = 42;
+
+    uninitialized_storage<copy_elision_dest, len> us;
+    uninitialized_move_n(pinned_ioterator{0}, len, us.begin());
+    for (int i = 0; i != len; ++i) {
+        assert(us.begin()[i].n_ == i);
+    }
+    destroy(us.begin(), us.end());
+}
+
 int main() {
     test_uninitialized_move();
     test_uninitialized_move_n();
@@ -206,4 +326,9 @@ int main() {
     test_destroy_at();
     test_destroy();
     test_destroy_n();
+
+    test_guaranteed_copy_elision_uninitialized_copy();
+    test_guaranteed_copy_elision_uninitialized_copy_n();
+    test_guaranteed_copy_elision_uninitialized_move();
+    test_guaranteed_copy_elision_uninitialized_move_n();
 }
diff --git a/tests/std/tests/P0784R7_library_machinery/test.cpp b/tests/std/tests/P0784R7_library_machinery/test.cpp
@@ -84,6 +84,9 @@ constexpr bool test() {
         assert(equal(begin(expected_copy), end(expected_copy), begin(output), end(output)));
     }
 
+#if 1 // TRANSITION, !_HAS_CXX26
+    if (!is_constant_evaluated())
+#endif // !_HAS_CXX26
     { // _Uninitialized_copy_unchecked
         int_wrapper_copy input[] = {1, 2, 3, 4};
         int_wrapper_copy output[4];
@@ -133,6 +136,9 @@ constexpr bool test() {
         }
     }
 
+#if 1 // TRANSITION, !_HAS_CXX26
+    if (!is_constant_evaluated())
+#endif // !_HAS_CXX26
     { // _Uninitialized_move_unchecked
         int_wrapper_move input[] = {1, 2, 3, 4};
         int_wrapper_move output[4];

Original file line number	Diff line number	Diff line change
`@@ -141,7 +141,7 @@ _NoThrowFwdIt uninitialized_copy_n(const _InIt _First, const _Diff _Count_raw, _`
`141`	`141`	`_Uninitialized_backout<decltype(_UDest)> _Backout{_UDest};`
`142`	`142`
`143`	`143`	`for (; _Count > 0; --_Count, (void) ++_UFirst) {`
`144`		`- _Backout._Emplace_back(*_UFirst);`
	`144`	`+ _Backout._Emplace_back_deref(_UFirst);`
`145`	`145`	`}`
`146`	`146`
`147`	`147`	`_UDest = _Backout._Release();`
`@@ -294,7 +294,7 @@ pair<_InIt, _NoThrowFwdIt> uninitialized_move_n(_InIt _First, const _Diff _Count`
`294`	`294`	`_Uninitialized_backout<decltype(_UDest)> _Backout{_UDest};`
`295`	`295`
`296`	`296`	`for (; _Count > 0; --_Count, (void) ++_UFirst) {`
`297`		`- _Backout._Emplace_back(_STD move(*_UFirst));`
	`297`	`+ _Backout._Emplace_back_deref_move(_UFirst);`
`298`	`298`	`}`
`299`	`299`
`300`	`300`	`_UDest = _Backout._Release();`
Original file line number	Diff line number	Diff line change
`@@ -84,6 +84,9 @@ constexpr bool test() {`
`84`	`84`	`assert(equal(begin(expected_copy), end(expected_copy), begin(output), end(output)));`
`85`	`85`	`}`
`86`	`86`
	`87`	`+#if 1 // TRANSITION, !_HAS_CXX26`
	`88`	`+ if (!is_constant_evaluated())`
	`89`	`+#endif // !_HAS_CXX26`
`87`	`90`	`{ // _Uninitialized_copy_unchecked`
`88`	`91`	`int_wrapper_copy input[] = {1, 2, 3, 4};`
`89`	`92`	`int_wrapper_copy output[4];`
`@@ -133,6 +136,9 @@ constexpr bool test() {`
`133`	`136`	`}`
`134`	`137`	`}`
`135`	`138`
	`139`	`+#if 1 // TRANSITION, !_HAS_CXX26`
	`140`	`+ if (!is_constant_evaluated())`
	`141`	`+#endif // !_HAS_CXX26`
`136`	`142`	`{ // _Uninitialized_move_unchecked`
`137`	`143`	`int_wrapper_move input[] = {1, 2, 3, 4};`
`138`	`144`	`int_wrapper_move output[4];`