2 * Copyright 2017 Facebook, Inc.
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
8 * http://www.apache.org/licenses/LICENSE-2.0
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
25 #include <type_traits>
29 #include <folly/Iterator.h>
30 #include <folly/portability/GTest.h>
34 * Container type used for unit tests.
37 using Container = std::deque<T>;
39 // Constructor and assignment operator call counters for struct Object.
40 std::size_t gDefaultCtrCnt;
41 std::size_t gCopyCtrCnt;
42 std::size_t gMoveCtrCnt;
43 std::size_t gExplicitCtrCnt;
44 std::size_t gMultiargCtrCnt;
45 std::size_t gCopyOpCnt;
46 std::size_t gMoveOpCnt;
47 std::size_t gConvertOpCnt;
50 * Class that increases various counters to keep track of how objects have
51 * been constructed or assigned to, to verify iterator behavior.
57 Object(const Object&) {
60 Object(Object&&) noexcept {
63 explicit Object(int) {
66 explicit Object(int, int) {
69 Object& operator=(const Object&) {
73 Object& operator=(Object&&) noexcept {
77 Object& operator=(int) noexcept {
84 * Reset all call counters to 0.
86 void init_counters() {
87 gDefaultCtrCnt = gCopyCtrCnt = gMoveCtrCnt = gExplicitCtrCnt =
88 gMultiargCtrCnt = gCopyOpCnt = gMoveOpCnt = gConvertOpCnt = 0;
92 * Test for iterator copy and move.
94 template <typename Iterator>
95 void copy_and_move_test(Container<int>& q, Iterator it) {
97 const auto it2(it); // copy construct
98 it = it2; // copy assign from const
99 it = it; // self assign
100 auto it3(std::move(it)); // move construct
101 it = std::move(it3); // move assign
102 // Make sure iterator still works.
103 it = 4711; // emplace
104 EXPECT_EQ(q, Container<int>{4711});
108 * Test for emplacement with perfect forwarding.
110 template <typename Iterator>
111 void emplace_test(Container<Object>& q, Iterator it) {
112 using folly::make_emplace_args;
115 it = Object{}; // default construct + move construct
116 Object obj; // default construct
117 it = obj; // copy construct
118 it = std::move(obj); // move construct
119 const Object obj2; // default construct
120 it = obj2; // copy construct from const
121 it = std::move(obj2); // copy construct (const defeats move)
122 it = 0; // explicit construct
123 it = make_emplace_args(0, 0); // explicit multiarg construct
124 it = std::make_pair(0, 0); // implicit multiarg construct
125 it = std::make_tuple(0, 0); // implicit multiarg construct
126 auto args = make_emplace_args(Object{}); // default construct + move construct
127 it = args; // copy construct
128 it = const_cast<const decltype(args)&>(args); // copy construct from const
129 it = std::move(args); // move construct
130 auto args2 = std::make_tuple(Object{}); // default construct + move construct
131 it = args2; // (implicit multiarg) copy construct
132 it = std::move(args2); // (implicit multiarg) move construct
133 auto args3 = std::make_pair(0, 0);
134 it = args3; // implicit multiarg construct
135 it = std::move(args3); // implicit multiarg construct
136 ASSERT_EQ(q.size(), 16);
137 EXPECT_EQ(gDefaultCtrCnt, 5);
138 EXPECT_EQ(gCopyCtrCnt, 6);
139 EXPECT_EQ(gMoveCtrCnt, 6);
140 EXPECT_EQ(gExplicitCtrCnt, 1);
141 EXPECT_EQ(gMultiargCtrCnt, 5);
142 EXPECT_EQ(gCopyOpCnt, 0);
143 EXPECT_EQ(gMoveOpCnt, 0);
144 EXPECT_EQ(gConvertOpCnt, 0);
148 using namespace folly;
151 * Basic tests for folly::emplace_iterator.
153 TEST(EmplaceIterator, EmplacerTest) {
156 copy_and_move_test(q, emplacer(q, q.begin()));
160 emplace_test(q, emplacer(q, q.begin()));
164 auto it = emplacer(q, q.begin());
168 it = emplacer(q, q.begin());
171 EXPECT_EQ(q, Container<int>({3, 4, 0, 1, 2}));
176 * Basic tests for folly::front_emplace_iterator.
178 TEST(EmplaceIterator, FrontEmplacerTest) {
181 copy_and_move_test(q, front_emplacer(q));
185 emplace_test(q, front_emplacer(q));
189 auto it = front_emplacer(q);
193 it = front_emplacer(q);
196 EXPECT_EQ(q, Container<int>({4, 3, 2, 1, 0}));
201 * Basic tests for folly::back_emplace_iterator.
203 TEST(EmplaceIterator, BackEmplacerTest) {
206 copy_and_move_test(q, back_emplacer(q));
210 emplace_test(q, back_emplacer(q));
214 auto it = back_emplacer(q);
218 it = back_emplacer(q);
221 EXPECT_EQ(q, Container<int>({0, 1, 2, 3, 4}));
226 * Basic tests for folly::hint_emplace_iterator.
228 TEST(EmplaceIterator, HintEmplacerTest) {
231 std::map<int, Object> m;
232 auto it = hint_emplacer(m, m.end());
233 it = make_emplace_args(
234 std::piecewise_construct,
235 std::forward_as_tuple(0),
236 std::forward_as_tuple(0));
237 it = make_emplace_args(
238 std::piecewise_construct,
239 std::forward_as_tuple(1),
240 std::forward_as_tuple(0, 0));
241 it = make_emplace_args(
242 std::piecewise_construct,
243 std::forward_as_tuple(2),
244 std::forward_as_tuple(Object{}));
245 ASSERT_EQ(m.size(), 3);
246 EXPECT_EQ(gDefaultCtrCnt, 1);
247 EXPECT_EQ(gCopyCtrCnt, 0);
248 EXPECT_EQ(gMoveCtrCnt, 1);
249 EXPECT_EQ(gExplicitCtrCnt, 1);
250 EXPECT_EQ(gMultiargCtrCnt, 1);
251 EXPECT_EQ(gCopyOpCnt, 0);
252 EXPECT_EQ(gMoveOpCnt, 0);
253 EXPECT_EQ(gConvertOpCnt, 0);
257 explicit O(int i) : i(i) {}
258 bool operator<(const O& other) const {
261 bool operator==(const O& other) const {
266 std::vector<int> v1 = {0, 1, 2, 3, 4};
267 std::vector<int> v2 = {0, 2, 4};
274 hint_emplacer(diff, diff.end()));
275 ASSERT_EQ(diff, std::set<O>({O(1), O(3)}));
280 * Test std::copy() with explicit conversion. This would not compile with a
281 * std::back_insert_iterator, because the constructor of Object that takes a
282 * single int is explicit.
284 TEST(EmplaceIterator, Copy) {
286 Container<int> in({0, 1, 2});
287 Container<Object> out;
288 std::copy(in.begin(), in.end(), back_emplacer(out));
289 EXPECT_EQ(3, out.size());
290 EXPECT_EQ(gDefaultCtrCnt, 0);
291 EXPECT_EQ(gCopyCtrCnt, 0);
292 EXPECT_EQ(gMoveCtrCnt, 0);
293 EXPECT_EQ(gExplicitCtrCnt, 3);
294 EXPECT_EQ(gMultiargCtrCnt, 0);
295 EXPECT_EQ(gCopyOpCnt, 0);
296 EXPECT_EQ(gMoveOpCnt, 0);
297 EXPECT_EQ(gConvertOpCnt, 0);
301 * Test std::transform() with multi-argument constructors. This would require
302 * a temporary Object with std::back_insert_iterator.
304 TEST(EmplaceIterator, Transform) {
306 Container<int> in({0, 1, 2});
307 Container<Object> out;
308 std::transform(in.begin(), in.end(), back_emplacer(out), [](int i) {
309 return make_emplace_args(i, i);
311 EXPECT_EQ(3, out.size());
312 EXPECT_EQ(gDefaultCtrCnt, 0);
313 EXPECT_EQ(gCopyCtrCnt, 0);
314 EXPECT_EQ(gMoveCtrCnt, 0);
315 EXPECT_EQ(gExplicitCtrCnt, 0);
316 EXPECT_EQ(gMultiargCtrCnt, 3);
317 EXPECT_EQ(gCopyOpCnt, 0);
318 EXPECT_EQ(gMoveOpCnt, 0);
319 EXPECT_EQ(gConvertOpCnt, 0);
323 * Test multi-argument store and forward.
325 TEST(EmplaceIterator, EmplaceArgs) {
329 const Object& o4 = o3;
333 // Test copy construction.
334 auto args = make_emplace_args(0, o1, o2, o3, o4, Object{}, std::cref(o2));
337 EXPECT_EQ(gDefaultCtrCnt, 0);
338 EXPECT_EQ(gCopyCtrCnt, 5);
339 EXPECT_EQ(gMoveCtrCnt, 0);
340 EXPECT_EQ(gExplicitCtrCnt, 0);
341 EXPECT_EQ(gMultiargCtrCnt, 0);
342 EXPECT_EQ(gCopyOpCnt, 0);
343 EXPECT_EQ(gMoveOpCnt, 0);
344 EXPECT_EQ(gConvertOpCnt, 0);
346 // Test copy assignment.
349 EXPECT_EQ(gDefaultCtrCnt, 0);
350 EXPECT_EQ(gCopyCtrCnt, 0);
351 EXPECT_EQ(gMoveCtrCnt, 0);
352 EXPECT_EQ(gExplicitCtrCnt, 0);
353 EXPECT_EQ(gMultiargCtrCnt, 0);
354 EXPECT_EQ(gCopyOpCnt, 5);
355 EXPECT_EQ(gMoveOpCnt, 0);
356 EXPECT_EQ(gConvertOpCnt, 0);
362 auto args = make_emplace_args(
363 0, o1, o2, o3, o4, Object{}, std::cref(o2), rref(std::move(o5)));
364 EXPECT_EQ(gDefaultCtrCnt, 1);
365 EXPECT_EQ(gCopyCtrCnt, 4);
366 EXPECT_EQ(gMoveCtrCnt, 1);
367 EXPECT_EQ(gExplicitCtrCnt, 0);
368 EXPECT_EQ(gMultiargCtrCnt, 0);
369 EXPECT_EQ(gCopyOpCnt, 0);
370 EXPECT_EQ(gMoveOpCnt, 0);
371 EXPECT_EQ(gConvertOpCnt, 0);
373 // Test move construction.
375 auto args2 = std::move(args);
376 EXPECT_EQ(gDefaultCtrCnt, 0);
377 EXPECT_EQ(gCopyCtrCnt, 0);
378 EXPECT_EQ(gMoveCtrCnt, 5);
379 EXPECT_EQ(gExplicitCtrCnt, 0);
380 EXPECT_EQ(gMultiargCtrCnt, 0);
381 EXPECT_EQ(gCopyOpCnt, 0);
382 EXPECT_EQ(gMoveOpCnt, 0);
383 EXPECT_EQ(gConvertOpCnt, 0);
385 // Test move assignment.
387 args = std::move(args2);
388 EXPECT_EQ(gDefaultCtrCnt, 0);
389 EXPECT_EQ(gCopyCtrCnt, 0);
390 EXPECT_EQ(gMoveCtrCnt, 0);
391 EXPECT_EQ(gExplicitCtrCnt, 0);
392 EXPECT_EQ(gMultiargCtrCnt, 0);
393 EXPECT_EQ(gCopyOpCnt, 0);
394 EXPECT_EQ(gMoveOpCnt, 5);
395 EXPECT_EQ(gConvertOpCnt, 0);
397 // Make sure arguments are stored correctly. lvalues by reference, rvalues
398 // by (moved) copy. Rvalues cannot be stored by reference because they may
399 // refer to an expired temporary by the time they are accessed.
403 std::tuple_element_t<0, decltype(args)::storage_type>>::value,
408 std::tuple_element_t<1, decltype(args)::storage_type>>::value,
413 std::tuple_element_t<2, decltype(args)::storage_type>>::value,
418 std::tuple_element_t<3, decltype(args)::storage_type>>::value,
423 std::tuple_element_t<4, decltype(args)::storage_type>>::value,
428 std::tuple_element_t<5, decltype(args)::storage_type>>::value,
432 std::reference_wrapper<const Object>,
433 std::tuple_element_t<6, decltype(args)::storage_type>>::value,
437 rvalue_reference_wrapper<Object>,
438 std::tuple_element_t<7, decltype(args)::storage_type>>::value,
441 // Check whether args.get() restores the original argument type for
442 // rvalue references to emplace_args.
444 std::is_same<int&&, decltype(get_emplace_arg<0>(std::move(args)))>::
448 std::is_same<Object&, decltype(get_emplace_arg<1>(std::move(args)))>::
454 decltype(get_emplace_arg<2>(std::move(args)))>::value,
457 std::is_same<Object&, decltype(get_emplace_arg<3>(std::move(args)))>::
463 decltype(get_emplace_arg<4>(std::move(args)))>::value,
466 std::is_same<Object&&, decltype(get_emplace_arg<5>(std::move(args)))>::
472 decltype(get_emplace_arg<6>(std::move(args)))>::value,
475 std::is_same<Object&&, decltype(get_emplace_arg<7>(std::move(args)))>::
479 // lvalue references to emplace_args should behave mostly like std::tuples.
480 // Note that get_emplace_arg<7>(args) does not compile, because
481 // folly::rvalue_reference_wrappers can only be unwrapped through an rvalue
484 std::is_same<int&, decltype(get_emplace_arg<0>(args))>::value, "");
486 std::is_same<Object&, decltype(get_emplace_arg<1>(args))>::value, "");
488 std::is_same<Object&, decltype(get_emplace_arg<2>(args))>::value, "");
490 std::is_same<Object&, decltype(get_emplace_arg<3>(args))>::value, "");
492 std::is_same<Object&, decltype(get_emplace_arg<4>(args))>::value, "");
494 std::is_same<Object&, decltype(get_emplace_arg<5>(args))>::value, "");
496 std::is_same<const Object&, decltype(get_emplace_arg<6>(args))>::value,
502 * Test implicit unpacking.
504 TEST(EmplaceIterator, ImplicitUnpack) {
505 static std::size_t multiCtrCnt;
506 static std::size_t pairCtrCnt;
507 static std::size_t tupleCtrCnt;
513 explicit Object2(const std::pair<int, int>&) {
516 explicit Object2(const std::tuple<int, int>&) {
521 auto test = [](auto&& it, bool expectUnpack) {
522 multiCtrCnt = pairCtrCnt = tupleCtrCnt = 0;
523 it = std::make_pair(0, 0);
524 it = std::make_tuple(0, 0);
526 EXPECT_EQ(multiCtrCnt, 2);
527 EXPECT_EQ(pairCtrCnt, 0);
528 EXPECT_EQ(tupleCtrCnt, 0);
530 EXPECT_EQ(multiCtrCnt, 0);
531 EXPECT_EQ(pairCtrCnt, 1);
532 EXPECT_EQ(tupleCtrCnt, 1);
536 Container<Object2> q;
538 test(emplacer(q, q.begin()), true);
539 test(emplacer<false>(q, q.begin()), false);
540 test(front_emplacer(q), true);
541 test(front_emplacer<false>(q), false);
542 test(back_emplacer(q), true);
543 test(back_emplacer<false>(q), false);