1//===----------------------------------------------------------------------===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8
9// UNSUPPORTED: c++03 && !stdlib=libc++
10// ADDITIONAL_COMPILE_FLAGS(has-fconstexpr-steps): -fconstexpr-steps=9000000
11
12// <vector>
13
14// template <class... Args> iterator emplace(const_iterator pos, Args&&... args);
15
16#include <cassert>
17#include <cstddef>
18#include <type_traits>
19#include <utility>
20#include <vector>
21
22#include "asan_testing.h"
23#include "common.h"
24#include "min_allocator.h"
25#include "MoveOnly.h"
26#include "test_allocator.h"
27#include "test_macros.h"
28
29template <class T>
30struct has_moved_from_sentinel_value : std::false_type {};
31
32template <>
33struct has_moved_from_sentinel_value<MoveOnly> : std::true_type {};
34
35template <template <class...> class Allocator, class T>
36TEST_CONSTEXPR_CXX20 void test() {
37 using Vector = std::vector<T, Allocator<T> >;
38 using Iterator = typename Vector::iterator;
39
40 // Check the return type
41 {
42 Vector v;
43 ASSERT_SAME_TYPE(decltype(v.emplace(v.cbegin(), 1)), Iterator);
44 }
45
46 // Emplace at the end of a vector with increasing size
47 {
48 Vector v;
49
50 // starts with size 0
51 {
52 Iterator it = v.emplace(v.cend(), 0);
53 assert(it == v.end() - 1);
54 assert(v.size() == 1);
55 assert(v[0] == T(0));
56 assert(is_contiguous_container_asan_correct(v));
57 }
58
59 // starts with size 1
60 {
61 Iterator it = v.emplace(v.cend(), 1);
62 assert(it == v.end() - 1);
63 assert(v.size() == 2);
64 assert(v[0] == T(0));
65 assert(v[1] == T(1));
66 assert(is_contiguous_container_asan_correct(v));
67 }
68
69 // starts with size 2
70 {
71 Iterator it = v.emplace(v.cend(), 2);
72 assert(it == v.end() - 1);
73 assert(v.size() == 3);
74 assert(v[0] == T(0));
75 assert(v[1] == T(1));
76 assert(v[2] == T(2));
77 assert(is_contiguous_container_asan_correct(v));
78 }
79
80 // starts with size n...
81 for (std::size_t n = 3; n != 100; ++n) {
82 Iterator it = v.emplace(v.cend(), n);
83 assert(it == v.end() - 1);
84 assert(v.size() == n + 1);
85 for (std::size_t i = 0; i != n + 1; ++i)
86 assert(v[i] == T(i));
87 assert(is_contiguous_container_asan_correct(v));
88 }
89 }
90
91 // Emplace at the start of a vector with increasing size
92 {
93 Vector v;
94
95 // starts with size 0
96 {
97 Iterator it = v.emplace(v.cbegin(), 0);
98 assert(it == v.begin());
99 assert(v.size() == 1);
100 assert(v[0] == T(0));
101 assert(is_contiguous_container_asan_correct(v));
102 }
103
104 // starts with size 1
105 {
106 Iterator it = v.emplace(v.cbegin(), 1);
107 assert(it == v.begin());
108 assert(v.size() == 2);
109 assert(v[0] == T(1));
110 assert(v[1] == T(0));
111 assert(is_contiguous_container_asan_correct(v));
112 }
113
114 // starts with size 2
115 {
116 Iterator it = v.emplace(v.cbegin(), 2);
117 assert(it == v.begin());
118 assert(v.size() == 3);
119 assert(v[0] == T(2));
120 assert(v[1] == T(1));
121 assert(v[2] == T(0));
122 assert(is_contiguous_container_asan_correct(v));
123 }
124
125 // starts with size n...
126 for (std::size_t n = 3; n != 100; ++n) {
127 Iterator it = v.emplace(v.cbegin(), n);
128 assert(it == v.begin());
129 assert(v.size() == n + 1);
130 for (std::size_t i = 0; i != n + 1; ++i)
131 assert(v[i] == T(n - i));
132 assert(is_contiguous_container_asan_correct(v));
133 }
134 }
135
136 // Emplace somewhere inside the vector
137 {
138 Vector v;
139 v.emplace_back(0);
140 v.emplace_back(1);
141 v.emplace_back(2);
142 // vector is {0, 1, 2}
143
144 {
145 Iterator it = v.emplace(v.cbegin() + 1, 3);
146 // vector is {0, 3, 1, 2}
147 assert(it == v.begin() + 1);
148 assert(v.size() == 4);
149 assert(v[0] == T(0));
150 assert(v[1] == T(3));
151 assert(v[2] == T(1));
152 assert(v[3] == T(2));
153 assert(is_contiguous_container_asan_correct(v));
154 }
155
156 {
157 Iterator it = v.emplace(v.cbegin() + 2, 4);
158 // vector is {0, 3, 4, 1, 2}
159 assert(it == v.begin() + 2);
160 assert(v.size() == 5);
161 assert(v[0] == T(0));
162 assert(v[1] == T(3));
163 assert(v[2] == T(4));
164 assert(v[3] == T(1));
165 assert(v[4] == T(2));
166 assert(is_contiguous_container_asan_correct(v));
167 }
168 }
169
170 // Emplace after reserving
171 {
172 Vector v;
173 v.emplace_back(0);
174 v.emplace_back(1);
175 v.emplace_back(2);
176 // vector is {0, 1, 2}
177
178 v.reserve(1000);
179 Iterator it = v.emplace(v.cbegin() + 1, 3);
180 assert(it == v.begin() + 1);
181 assert(v.size() == 4);
182 assert(v[0] == T(0));
183 assert(v[1] == T(3));
184 assert(v[2] == T(1));
185 assert(v[3] == T(2));
186 assert(is_contiguous_container_asan_correct(v));
187 }
188
189 // Emplace with the same type that's stored in the vector (as opposed to just constructor arguments)
190 {
191 Vector v;
192 Iterator it = v.emplace(v.cbegin(), T(1));
193 assert(it == v.begin());
194 assert(v.size() == 1);
195 assert(v[0] == T(1));
196 assert(is_contiguous_container_asan_correct(v));
197 }
198
199 // Emplace from an element inside the vector itself. This is interesting for two reasons. First, if the
200 // vector must increase capacity, the implementation needs to make sure that it doesn't end up inserting
201 // from a dangling reference.
202 //
203 // Second, if the vector doesn't need to grow but its elements get shifted internally, the implementation
204 // must make sure that it doesn't end up inserting from an element whose position has changed.
205 {
206 // When capacity must increase
207 {
208 Vector v;
209 v.emplace_back(1);
210 v.emplace_back(2);
211
212 while (v.size() < v.capacity()) {
213 v.emplace_back(3);
214 }
215 assert(v.size() == v.capacity());
216 // vector is {1, 2, 3...}
217
218 std::size_t old_cap = v.capacity();
219 v.emplace(v.cbegin(), std::move(v[1]));
220 assert(v.capacity() > old_cap); // test the test
221
222 // vector is {2, 1, 0, 3...}
223 // Note that old v[1] has been set to 0 when it was moved-from
224 assert(v.size() >= 3);
225 assert(v[0] == T(2));
226 assert(v[1] == T(1));
227 if (has_moved_from_sentinel_value<T>::value)
228 assert(v[2] == T(0));
229 assert(is_contiguous_container_asan_correct(v));
230 }
231
232 // When elements shift around
233 {
234 Vector v;
235 v.emplace_back(1);
236 v.emplace_back(2);
237 // vector is {1, 2}
238
239 v.reserve(3);
240 std::size_t old_cap = v.capacity();
241 v.emplace(v.cbegin(), std::move(v[1]));
242 assert(v.capacity() == old_cap); // test the test
243
244 // vector is {2, 1, 0}
245 // Note that old v[1] has been set to 0 when it was moved-from
246 assert(v.size() == 3);
247 assert(v[0] == T(2));
248 assert(v[1] == T(1));
249 if (has_moved_from_sentinel_value<T>::value)
250 assert(v[2] == T(0));
251 assert(is_contiguous_container_asan_correct(v));
252 }
253 }
254
255 // Make sure that we don't reallocate when we have sufficient capacity
256 {
257 Vector v;
258 v.reserve(8);
259 assert(v.capacity() >= 8);
260
261 std::size_t old_capacity = v.capacity();
262 v.emplace_back(0);
263 v.emplace_back(1);
264 v.emplace_back(2);
265 v.emplace_back(3);
266 assert(v.capacity() == old_capacity);
267
268 v.emplace(v.cend(), 4);
269 assert(v.size() == 5);
270 assert(v.capacity() == old_capacity);
271 assert(v[0] == T(0));
272 assert(v[1] == T(1));
273 assert(v[2] == T(2));
274 assert(v[3] == T(3));
275 assert(v[4] == T(4));
276 assert(is_contiguous_container_asan_correct(v));
277 }
278
279 // Make sure that we correctly handle the case where an exception would be thrown if moving the element into place.
280 // This is a very specific test that aims to validate that the implementation doesn't create a temporary object e.g.
281 // on the stack and then moves it into its final location inside the newly allocated vector storage.
282 //
283 // If that were the case, and if the element happened to throw upon move construction or move assignment into its
284 // final location, we would have invalidated iterators, when a different approach would allow us to still provide
285 // the strong exception safety guarantee.
286 //
287 // Instead of the naive approach, libc++ emplaces the new element into its final location immediately, and only
288 // after this has been done do we start making non-reversible changes to the vector's underlying storage. This
289 // test pins down that behavior, although that is something that we don't advertise widely and could potentially
290 // change in the future.
291#if defined(_LIBCPP_VERSION) && !defined(TEST_HAS_NO_EXCEPTIONS)
292 {
293 // This ensures that we test what we intend to test: the Standard requires the strong exception safety
294 // guarantee for types that are nothrow move constructible or copy insertable, but that's not what we're
295 // trying to test. We're trying to test the stronger libc++ guarantee.
296 static_assert(!std::is_nothrow_move_constructible<ThrowingMoveOnly>::value, "");
297 static_assert(!std::is_copy_constructible<ThrowingMoveOnly>::value, "");
298
299 std::vector<ThrowingMoveOnly, Allocator<ThrowingMoveOnly> > v;
300 v.emplace_back(0, /* do throw */ false);
301 v.emplace_back(1, /* do throw */ false);
302
303 while (v.size() < v.capacity()) {
304 v.emplace_back(2, /* do throw */ false);
305 }
306 assert(v.size() == v.capacity()); // the next emplace will be forced to invalidate iterators
307
308 v.emplace(v.cend(), 3, /* do throw */ true); // this shouldn't throw since we shouldn't move this element at all
309
310 assert(v.size() >= 3);
311 assert(v[0] == ThrowingMoveOnly(0));
312 assert(v[1] == ThrowingMoveOnly(1));
313 assert(v.back() == ThrowingMoveOnly(3));
314 assert(is_contiguous_container_asan_correct(v));
315 }
316#endif // defined(_LIBCPP_VERSION) && !defined(TEST_HAS_NO_EXCEPTIONS)
317}
318
319TEST_CONSTEXPR_CXX20 bool tests() {
320 test<std::allocator, int>();
321 test<min_allocator, int>();
322 test<safe_allocator, int>();
323
324 test<std::allocator, MoveOnly>();
325 test<min_allocator, MoveOnly>();
326 test<safe_allocator, MoveOnly>();
327
328 test<std::allocator, NonTriviallyRelocatable>();
329 test<min_allocator, NonTriviallyRelocatable>();
330 test<safe_allocator, NonTriviallyRelocatable>();
331
332 // test<limited_allocator<int, 7> >();
333 return true;
334}
335
336int main(int, char**) {
337 tests();
338#if TEST_STD_VER > 17
339 static_assert(tests());
340#endif
341 return 0;
342}
343

source code of libcxx/test/std/containers/sequences/vector/vector.modifiers/emplace.pass.cpp