343 lines · cpp
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-exception6//7//===----------------------------------------------------------------------===//8 9// UNSUPPORTED: c++03 && !stdlib=libc++10// ADDITIONAL_COMPILE_FLAGS(has-fconstexpr-steps): -fconstexpr-steps=900000011 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 type41 {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 size47 {48 Vector v;49 50 // starts with size 051 {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 160 {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 270 {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 size92 {93 Vector v;94 95 // starts with size 096 {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 1105 {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 2115 {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 vector137 {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 reserving171 {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 the200 // vector must increase capacity, the implementation needs to make sure that it doesn't end up inserting201 // from a dangling reference.202 //203 // Second, if the vector doesn't need to grow but its elements get shifted internally, the implementation204 // must make sure that it doesn't end up inserting from an element whose position has changed.205 {206 // When capacity must increase207 {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 test221 222 // vector is {2, 1, 0, 3...}223 // Note that old v[1] has been set to 0 when it was moved-from224 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 around233 {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 test243 244 // vector is {2, 1, 0}245 // Note that old v[1] has been set to 0 when it was moved-from246 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 capacity256 {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 its284 // final location, we would have invalidated iterators, when a different approach would allow us to still provide285 // the strong exception safety guarantee.286 //287 // Instead of the naive approach, libc++ emplaces the new element into its final location immediately, and only288 // after this has been done do we start making non-reversible changes to the vector's underlying storage. This289 // test pins down that behavior, although that is something that we don't advertise widely and could potentially290 // 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 safety294 // guarantee for types that are nothrow move constructible or copy insertable, but that's not what we're295 // 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 iterators307 308 v.emplace(v.cend(), 3, /* do throw */ true); // this shouldn't throw since we shouldn't move this element at all309 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 > 17339 static_assert(tests());340#endif341 return 0;342}343