1// -*- C++ -*-
2//===----------------------------------------------------------------------===//
3//
4// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
5// See https://llvm.org/LICENSE.txt for license information.
6// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
7//
8//===----------------------------------------------------------------------===//
9
10#ifndef _LIBCPP___RANGES_MOVABLE_BOX_H
11#define _LIBCPP___RANGES_MOVABLE_BOX_H
12
13#include <__concepts/constructible.h>
14#include <__concepts/copyable.h>
15#include <__concepts/movable.h>
16#include <__config>
17#include <__memory/addressof.h>
18#include <__memory/construct_at.h>
19#include <__optional/optional.h>
20#include <__type_traits/is_constructible.h>
21#include <__type_traits/is_nothrow_constructible.h>
22#include <__type_traits/is_object.h>
23#include <__utility/forward.h>
24#include <__utility/in_place.h>
25#include <__utility/move.h>
26
27#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
28# pragma GCC system_header
29#endif
30
31_LIBCPP_PUSH_MACROS
32#include <__undef_macros>
33
34_LIBCPP_BEGIN_NAMESPACE_STD
35
36#if _LIBCPP_STD_VER >= 20
37
38// __movable_box allows turning a type that is move-constructible (but maybe not move-assignable) into
39// a type that is both move-constructible and move-assignable. It does that by introducing an empty state
40// and basically doing destroy-then-copy-construct in the assignment operator. The empty state is necessary
41// to handle the case where the copy construction fails after destroying the object.
42//
43// In some cases, we can completely avoid the use of an empty state; we provide a specialization of
44// __movable_box that does this, see below for the details.
45
46// until C++23, `__movable_box` was named `__copyable_box` and required the stored type to be copy-constructible, not
47// just move-constructible; we preserve the old behavior in pre-C++23 modes.
48template <class _Tp>
49concept __movable_box_object =
50# if _LIBCPP_STD_VER >= 23
51 move_constructible<_Tp>
52# else
53 copy_constructible<_Tp>
54# endif
55 && is_object_v<_Tp>;
56
57namespace ranges {
58// Primary template - uses std::optional and introduces an empty state in case assignment fails.
59template <__movable_box_object _Tp>
60class __movable_box {
61 _LIBCPP_NO_UNIQUE_ADDRESS optional<_Tp> __val_;
62
63public:
64 template <class... _Args>
65 requires is_constructible_v<_Tp, _Args...>
66 _LIBCPP_HIDE_FROM_ABI constexpr explicit __movable_box(in_place_t, _Args&&... __args) noexcept(
67 is_nothrow_constructible_v<_Tp, _Args...>)
68 : __val_(in_place, std::forward<_Args>(__args)...) {}
69
70 _LIBCPP_HIDE_FROM_ABI constexpr __movable_box() noexcept(is_nothrow_default_constructible_v<_Tp>)
71 requires default_initializable<_Tp>
72 : __val_(in_place) {}
73
74 _LIBCPP_HIDE_FROM_ABI __movable_box(__movable_box const&) = default;
75 _LIBCPP_HIDE_FROM_ABI __movable_box(__movable_box&&) = default;
76
77 _LIBCPP_HIDE_FROM_ABI constexpr __movable_box&
78 operator=(__movable_box const& __other) noexcept(is_nothrow_copy_constructible_v<_Tp>)
79# if _LIBCPP_STD_VER >= 23
80 requires copy_constructible<_Tp>
81# endif
82 {
83 if (this != std::addressof(__other)) {
84 if (__other.__has_value())
85 __val_.emplace(*__other);
86 else
87 __val_.reset();
88 }
89 return *this;
90 }
91
92 _LIBCPP_HIDE_FROM_ABI __movable_box& operator=(__movable_box&&)
93 requires movable<_Tp>
94 = default;
95
96 _LIBCPP_HIDE_FROM_ABI constexpr __movable_box&
97 operator=(__movable_box&& __other) noexcept(is_nothrow_move_constructible_v<_Tp>) {
98 if (this != std::addressof(__other)) {
99 if (__other.__has_value())
100 __val_.emplace(std::move(*__other));
101 else
102 __val_.reset();
103 }
104 return *this;
105 }
106
107 _LIBCPP_HIDE_FROM_ABI constexpr _Tp const& operator*() const noexcept { return *__val_; }
108 _LIBCPP_HIDE_FROM_ABI constexpr _Tp& operator*() noexcept { return *__val_; }
109
110 _LIBCPP_HIDE_FROM_ABI constexpr const _Tp* operator->() const noexcept { return __val_.operator->(); }
111 _LIBCPP_HIDE_FROM_ABI constexpr _Tp* operator->() noexcept { return __val_.operator->(); }
112
113 _LIBCPP_HIDE_FROM_ABI constexpr bool __has_value() const noexcept { return __val_.has_value(); }
114};
115
116// This partial specialization implements an optimization for when we know we don't need to store
117// an empty state to represent failure to perform an assignment. For copy-assignment, this happens:
118//
119// 1. If the type is copyable (which includes copy-assignment), we can use the type's own assignment operator
120// directly and avoid using std::optional.
121// 2. If the type is not copyable, but it is nothrow-copy-constructible, then we can implement assignment as
122// destroy-and-then-construct and we know it will never fail, so we don't need an empty state.
123//
124// The exact same reasoning can be applied for move-assignment, with copyable replaced by movable and
125// nothrow-copy-constructible replaced by nothrow-move-constructible. This specialization is enabled
126// whenever we can apply any of these optimizations for both the copy assignment and the move assignment
127// operator.
128
129# if _LIBCPP_STD_VER >= 23
130template <class _Tp>
131concept __doesnt_need_empty_state =
132 (copy_constructible<_Tp>
133 // 1. If copy_constructible<T> is true, movable-box<T> should store only a T if either T models
134 // copyable, or is_nothrow_move_constructible_v<T> && is_nothrow_copy_constructible_v<T> is true.
135 ? copyable<_Tp> || (is_nothrow_move_constructible_v<_Tp> && is_nothrow_copy_constructible_v<_Tp>)
136 // 2. Otherwise, movable-box<T> should store only a T if either T models movable or
137 // is_nothrow_move_constructible_v<T> is true.
138 : movable<_Tp> || is_nothrow_move_constructible_v<_Tp>);
139
140// When _Tp doesn't have an assignment operator, we must implement __movable_box's assignment operator
141// by doing destroy_at followed by construct_at. However, that implementation strategy leads to UB if the nested
142// _Tp is potentially overlapping, as it is doing a non-transparent replacement of the sub-object, which means that
143// we're not considered "nested" inside the movable-box anymore, and since we're not nested within it, [basic.life]/1.5
144// says that we essentially just reused the storage of the movable-box for a completely unrelated object and ended the
145// movable-box's lifetime.
146// https://github.com/llvm/llvm-project/issues/70494#issuecomment-1845646490
147//
148// Hence, when the _Tp doesn't have an assignment operator, we can't risk making it a potentially-overlapping
149// subobject because of the above, and we don't use [[no_unique_address]] in that case.
150template <class _Tp>
151concept __can_use_no_unique_address = (copy_constructible<_Tp> ? copyable<_Tp> : movable<_Tp>);
152
153# else
154
155template <class _Tp>
156concept __doesnt_need_empty_state_for_copy = copyable<_Tp> || is_nothrow_copy_constructible_v<_Tp>;
157
158template <class _Tp>
159concept __doesnt_need_empty_state_for_move = movable<_Tp> || is_nothrow_move_constructible_v<_Tp>;
160
161template <class _Tp>
162concept __doesnt_need_empty_state = __doesnt_need_empty_state_for_copy<_Tp> && __doesnt_need_empty_state_for_move<_Tp>;
163
164template <class _Tp>
165concept __can_use_no_unique_address = copyable<_Tp>;
166# endif
167
168template <class _Tp>
169struct __movable_box_holder {
170 _Tp __val_;
171
172 template <class... _Args>
173 _LIBCPP_HIDE_FROM_ABI constexpr explicit __movable_box_holder(in_place_t, _Args&&... __args)
174 : __val_(std::forward<_Args>(__args)...) {}
175};
176
177template <class _Tp>
178 requires __can_use_no_unique_address<_Tp>
179struct __movable_box_holder<_Tp> {
180 _LIBCPP_NO_UNIQUE_ADDRESS _Tp __val_;
181
182 template <class... _Args>
183 _LIBCPP_HIDE_FROM_ABI constexpr explicit __movable_box_holder(in_place_t, _Args&&... __args)
184 : __val_(std::forward<_Args>(__args)...) {}
185};
186
187template <__movable_box_object _Tp>
188 requires __doesnt_need_empty_state<_Tp>
189class __movable_box<_Tp> {
190 _LIBCPP_NO_UNIQUE_ADDRESS __movable_box_holder<_Tp> __holder_;
191
192public:
193 template <class... _Args>
194 requires is_constructible_v<_Tp, _Args...>
195 _LIBCPP_HIDE_FROM_ABI constexpr explicit __movable_box(in_place_t __inplace, _Args&&... __args) noexcept(
196 is_nothrow_constructible_v<_Tp, _Args...>)
197 : __holder_(__inplace, std::forward<_Args>(__args)...) {}
198
199 _LIBCPP_HIDE_FROM_ABI constexpr __movable_box() noexcept(is_nothrow_default_constructible_v<_Tp>)
200 requires default_initializable<_Tp>
201 : __holder_(in_place_t{}) {}
202
203 _LIBCPP_HIDE_FROM_ABI __movable_box(__movable_box const&) = default;
204 _LIBCPP_HIDE_FROM_ABI __movable_box(__movable_box&&) = default;
205
206 // Implementation of assignment operators in case we perform optimization (1)
207 _LIBCPP_HIDE_FROM_ABI __movable_box& operator=(__movable_box const&)
208 requires copyable<_Tp>
209 = default;
210 _LIBCPP_HIDE_FROM_ABI __movable_box& operator=(__movable_box&&)
211 requires movable<_Tp>
212 = default;
213
214 // Implementation of assignment operators in case we perform optimization (2)
215 _LIBCPP_HIDE_FROM_ABI constexpr __movable_box& operator=(__movable_box const& __other) noexcept {
216 static_assert(is_nothrow_copy_constructible_v<_Tp>);
217 static_assert(!__can_use_no_unique_address<_Tp>);
218 if (this != std::addressof(__other)) {
219 std::destroy_at(std::addressof(__holder_.__val_));
220 std::construct_at(std::addressof(__holder_.__val_), __other.__holder_.__val_);
221 }
222 return *this;
223 }
224
225 _LIBCPP_HIDE_FROM_ABI constexpr __movable_box& operator=(__movable_box&& __other) noexcept {
226 static_assert(is_nothrow_move_constructible_v<_Tp>);
227 static_assert(!__can_use_no_unique_address<_Tp>);
228 if (this != std::addressof(__other)) {
229 std::destroy_at(std::addressof(__holder_.__val_));
230 std::construct_at(std::addressof(__holder_.__val_), std::move(__other.__holder_.__val_));
231 }
232 return *this;
233 }
234
235 _LIBCPP_HIDE_FROM_ABI constexpr _Tp const& operator*() const noexcept { return __holder_.__val_; }
236 _LIBCPP_HIDE_FROM_ABI constexpr _Tp& operator*() noexcept { return __holder_.__val_; }
237
238 _LIBCPP_HIDE_FROM_ABI constexpr const _Tp* operator->() const noexcept { return std::addressof(__holder_.__val_); }
239 _LIBCPP_HIDE_FROM_ABI constexpr _Tp* operator->() noexcept { return std::addressof(__holder_.__val_); }
240
241 _LIBCPP_HIDE_FROM_ABI constexpr bool __has_value() const noexcept { return true; }
242};
243} // namespace ranges
244
245#endif // _LIBCPP_STD_VER >= 20
246
247_LIBCPP_END_NAMESPACE_STD
248
249_LIBCPP_POP_MACROS
250
251#endif // _LIBCPP___RANGES_MOVABLE_BOX_H
252