1 /*
2 * Copyright (c) Facebook, Inc. and its affiliates.
3 *
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
7 *
8 * http://www.apache.org/licenses/LICENSE-2.0
9 *
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.
15 */
16
17 #pragma once
18
19 #include <functional>
20 #include <iterator>
21 #include <memory>
22 #include <tuple>
23 #include <type_traits>
24 #include <utility>
25
26 #include <folly/Utility.h>
27 #include <folly/lang/RValueReferenceWrapper.h>
28
29 namespace folly {
30
31 /**
32 * Argument tuple for variadic emplace/constructor calls. Stores arguments by
33 * (decayed) value. Restores original argument types with reference qualifiers
34 * and adornments at unpack time to emulate perfect forwarding.
35 *
36 * Uses inheritance instead of a type alias to std::tuple so that emplace
37 * iterators with implicit unpacking disabled can distinguish between
38 * emplace_args and std::tuple parameters.
39 *
40 * @seealso folly::make_emplace_args
41 * @seealso folly::get_emplace_arg
42 */
43 template <typename... Args>
44 struct emplace_args : public std::tuple<std::decay_t<Args>...> {
45 using storage_type = std::tuple<std::decay_t<Args>...>;
46 using storage_type::storage_type;
47 };
48
49 /**
50 * Pack arguments in a tuple for assignment to a folly::emplace_iterator,
51 * folly::front_emplace_iterator, or folly::back_emplace_iterator. The
52 * iterator's operator= will unpack the tuple and pass the unpacked arguments
53 * to the container's emplace function, which in turn forwards the arguments to
54 * the (multi-argument) constructor of the target class.
55 *
56 * Argument tuples generated with folly::make_emplace_args will be unpacked
57 * before being passed to the container's emplace function, even for iterators
58 * where implicit_unpack is set to false (so they will not implicitly unpack
59 * std::pair or std::tuple arguments to operator=).
60 *
61 * Arguments are copied (lvalues) or moved (rvalues). To avoid copies and moves,
62 * wrap references using std::ref(), std::cref(), and folly::rref(). Beware of
63 * dangling references, especially references to temporary objects created with
64 * folly::rref().
65 *
66 * Note that an argument pack created with folly::make_emplace_args is different
67 * from an argument pack created with std::make_pair or std::make_tuple.
68 * Specifically, passing a std::pair&& or std::tuple&& to an emplace iterator's
69 * operator= will pass rvalue references to all fields of that tuple to the
70 * container's emplace function, while passing an emplace_args&& to operator=
71 * will cast those field references to the exact argument types as passed to
72 * folly::make_emplace_args previously. If all arguments have been wrapped by
73 * std::reference_wrappers or folly::rvalue_reference_wrappers, the result will
74 * be the same as if the container's emplace function had been called directly
75 * (perfect forwarding), with no temporary copies of the arguments.
76 *
77 * @seealso folly::rref
78 *
79 * @example
80 * class Widget { Widget(int, int); };
81 * std::vector<Widget> makeWidgets(const std::vector<int>& in) {
82 * std::vector<Widget> out;
83 * std::transform(
84 * in.begin(),
85 * in.end(),
86 * folly::back_emplacer(out),
87 * [](int i) { return folly::make_emplace_args(i, i); });
88 * return out;
89 * }
90 */
91 template <typename... Args>
make_emplace_args(Args &&...args)92 emplace_args<Args...> make_emplace_args(Args&&... args) noexcept(
93 noexcept(emplace_args<Args...>(std::forward<Args>(args)...))) {
94 return emplace_args<Args...>(std::forward<Args>(args)...);
95 }
96
97 namespace detail {
98 template <typename Arg>
decltype(auto)99 decltype(auto) unwrap_emplace_arg(Arg&& arg) noexcept {
100 return std::forward<Arg>(arg);
101 }
102 template <typename Arg>
decltype(auto)103 decltype(auto) unwrap_emplace_arg(std::reference_wrapper<Arg> arg) noexcept {
104 return arg.get();
105 }
106 template <typename Arg>
decltype(auto)107 decltype(auto) unwrap_emplace_arg(
108 folly::rvalue_reference_wrapper<Arg> arg) noexcept {
109 return std::move(arg).get();
110 }
111 } // namespace detail
112
113 /**
114 * Getter function for unpacking a single emplace argument.
115 *
116 * Calling get_emplace_arg on an emplace_args rvalue reference results in
117 * perfect forwarding of the original input types. A special case are
118 * std::reference_wrapper and folly::rvalue_reference_wrapper objects within
119 * folly::emplace_args. These are also unwrapped so that the bare reference is
120 * returned.
121 *
122 * std::get is not a customization point in the standard library, so the
123 * cleanest solution was to define our own getter function.
124 */
125 template <size_t I, typename... Args>
decltype(auto)126 decltype(auto) get_emplace_arg(emplace_args<Args...>&& args) noexcept {
127 using Out = std::tuple<Args...>;
128 return detail::unwrap_emplace_arg(
129 std::forward<std::tuple_element_t<I, Out>>(std::get<I>(args)));
130 }
131 template <size_t I, typename... Args>
decltype(auto)132 decltype(auto) get_emplace_arg(emplace_args<Args...>& args) noexcept {
133 return detail::unwrap_emplace_arg(std::get<I>(args));
134 }
135 template <size_t I, typename... Args>
decltype(auto)136 decltype(auto) get_emplace_arg(const emplace_args<Args...>& args) noexcept {
137 return detail::unwrap_emplace_arg(std::get<I>(args));
138 }
139 template <size_t I, typename Args>
decltype(auto)140 decltype(auto) get_emplace_arg(Args&& args) noexcept {
141 return std::get<I>(std::move(args));
142 }
143 template <size_t I, typename Args>
decltype(auto)144 decltype(auto) get_emplace_arg(Args& args) noexcept {
145 return std::get<I>(args);
146 }
147 template <size_t I, typename Args>
decltype(auto)148 decltype(auto) get_emplace_arg(const Args& args) noexcept {
149 return std::get<I>(args);
150 }
151
152 namespace detail {
153 /**
154 * Emplace implementation class for folly::emplace_iterator.
155 */
156 template <typename Container>
157 struct Emplace {
EmplaceEmplace158 Emplace(Container& c, typename Container::iterator i)
159 : container(std::addressof(c)), iter(std::move(i)) {}
160 template <typename... Args>
emplaceEmplace161 void emplace(Args&&... args) {
162 iter = container->emplace(iter, std::forward<Args>(args)...);
163 ++iter;
164 }
165 Container* container;
166 typename Container::iterator iter;
167 };
168
169 /**
170 * Emplace implementation class for folly::hint_emplace_iterator.
171 */
172 template <typename Container>
173 struct EmplaceHint {
EmplaceHintEmplaceHint174 EmplaceHint(Container& c, typename Container::iterator i)
175 : container(std::addressof(c)), iter(std::move(i)) {}
176 template <typename... Args>
emplaceEmplaceHint177 void emplace(Args&&... args) {
178 iter = container->emplace_hint(iter, std::forward<Args>(args)...);
179 ++iter;
180 }
181 Container* container;
182 typename Container::iterator iter;
183 };
184
185 /**
186 * Emplace implementation class for folly::front_emplace_iterator.
187 */
188 template <typename Container>
189 struct EmplaceFront {
EmplaceFrontEmplaceFront190 explicit EmplaceFront(Container& c) : container(std::addressof(c)) {}
191 template <typename... Args>
emplaceEmplaceFront192 void emplace(Args&&... args) {
193 container->emplace_front(std::forward<Args>(args)...);
194 }
195 Container* container;
196 };
197
198 /**
199 * Emplace implementation class for folly::back_emplace_iterator.
200 */
201 template <typename Container>
202 struct EmplaceBack {
EmplaceBackEmplaceBack203 explicit EmplaceBack(Container& c) : container(std::addressof(c)) {}
204 template <typename... Args>
emplaceEmplaceBack205 void emplace(Args&&... args) {
206 container->emplace_back(std::forward<Args>(args)...);
207 }
208 Container* container;
209 };
210
211 /**
212 * Generic base class and implementation of all emplace iterator classes.
213 *
214 * Uses the curiously recurring template pattern (CRTP) to cast `this*` to
215 * `Derived*`; i.e., to implement covariant return types in a generic manner.
216 */
217 template <typename Derived, typename EmplaceImpl, bool implicit_unpack>
218 class emplace_iterator_base;
219
220 /**
221 * Partial specialization of emplace_iterator_base with implicit unpacking
222 * disabled.
223 */
224 template <typename Derived, typename EmplaceImpl>
225 class emplace_iterator_base<Derived, EmplaceImpl, false>
226 : protected EmplaceImpl /* protected implementation inheritance */ {
227 public:
228 // Iterator traits.
229 using iterator_category = std::output_iterator_tag;
230 using value_type = void;
231 using difference_type = void;
232 using pointer = void;
233 using reference = void;
234 using container_type =
235 std::remove_reference_t<decltype(*EmplaceImpl::container)>;
236
237 using EmplaceImpl::EmplaceImpl;
238
239 /**
240 * Canonical output operator. Forwards single argument straight to container's
241 * emplace function.
242 */
243 template <typename T>
244 Derived& operator=(T&& arg) {
245 this->emplace(std::forward<T>(arg));
246 return static_cast<Derived&>(*this);
247 }
248
249 /**
250 * Special output operator for packed arguments. Unpacks args and performs
251 * variadic call to container's emplace function.
252 */
253 template <typename... Args>
254 Derived& operator=(emplace_args<Args...>& args) {
255 return unpackAndEmplace(args, std::index_sequence_for<Args...>{});
256 }
257 template <typename... Args>
258 Derived& operator=(const emplace_args<Args...>& args) {
259 return unpackAndEmplace(args, std::index_sequence_for<Args...>{});
260 }
261 template <typename... Args>
262 Derived& operator=(emplace_args<Args...>&& args) {
263 return unpackAndEmplace(
264 std::move(args), std::index_sequence_for<Args...>{});
265 }
266
267 // No-ops.
268 Derived& operator*() { return static_cast<Derived&>(*this); }
269 Derived& operator++() { return static_cast<Derived&>(*this); }
270 Derived& operator++(int) { return static_cast<Derived&>(*this); }
271
272 // We need all of these explicit defaults because the custom operator=
273 // overloads disable implicit generation of these functions.
274 emplace_iterator_base(const emplace_iterator_base&) = default;
275 emplace_iterator_base(emplace_iterator_base&&) noexcept = default;
276 emplace_iterator_base& operator=(emplace_iterator_base&) = default;
277 emplace_iterator_base& operator=(const emplace_iterator_base&) = default;
278 emplace_iterator_base& operator=(emplace_iterator_base&&) noexcept = default;
279
280 protected:
281 template <typename Args, std::size_t... I>
unpackAndEmplace(Args & args,std::index_sequence<I...>)282 Derived& unpackAndEmplace(Args& args, std::index_sequence<I...>) {
283 this->emplace(get_emplace_arg<I>(args)...);
284 return static_cast<Derived&>(*this);
285 }
286 template <typename Args, std::size_t... I>
unpackAndEmplace(const Args & args,std::index_sequence<I...>)287 Derived& unpackAndEmplace(const Args& args, std::index_sequence<I...>) {
288 this->emplace(get_emplace_arg<I>(args)...);
289 return static_cast<Derived&>(*this);
290 }
291 template <typename Args, std::size_t... I>
unpackAndEmplace(Args && args,std::index_sequence<I...>)292 Derived& unpackAndEmplace(Args&& args, std::index_sequence<I...>) {
293 this->emplace(get_emplace_arg<I>(std::move(args))...);
294 return static_cast<Derived&>(*this);
295 }
296 };
297
298 /**
299 * Partial specialization of emplace_iterator_base with implicit unpacking
300 * enabled.
301 *
302 * Uses inheritance rather than SFINAE. operator= requires a single argument,
303 * which makes it very tricky to use std::enable_if or similar.
304 */
305 template <typename Derived, typename EmplaceImpl>
306 class emplace_iterator_base<Derived, EmplaceImpl, true>
307 : public emplace_iterator_base<Derived, EmplaceImpl, false> {
308 private:
309 using Base = emplace_iterator_base<Derived, EmplaceImpl, false>;
310
311 public:
312 using Base::Base;
313 using Base::operator=;
314
315 /**
316 * Special output operator for arguments packed into a std::pair. Unpacks
317 * the pair and performs variadic call to container's emplace function.
318 */
319 template <typename... Args>
320 Derived& operator=(std::pair<Args...>& args) {
321 return this->unpackAndEmplace(args, std::index_sequence_for<Args...>{});
322 }
323 template <typename... Args>
324 Derived& operator=(const std::pair<Args...>& args) {
325 return this->unpackAndEmplace(args, std::index_sequence_for<Args...>{});
326 }
327 template <typename... Args>
328 Derived& operator=(std::pair<Args...>&& args) {
329 return this->unpackAndEmplace(
330 std::move(args), std::index_sequence_for<Args...>{});
331 }
332
333 /**
334 * Special output operator for arguments packed into a std::tuple. Unpacks
335 * the tuple and performs variadic call to container's emplace function.
336 */
337 template <typename... Args>
338 Derived& operator=(std::tuple<Args...>& args) {
339 return this->unpackAndEmplace(args, std::index_sequence_for<Args...>{});
340 }
341 template <typename... Args>
342 Derived& operator=(const std::tuple<Args...>& args) {
343 return this->unpackAndEmplace(args, std::index_sequence_for<Args...>{});
344 }
345 template <typename... Args>
346 Derived& operator=(std::tuple<Args...>&& args) {
347 return this->unpackAndEmplace(
348 std::move(args), std::index_sequence_for<Args...>{});
349 }
350
351 // We need all of these explicit defaults because the custom operator=
352 // overloads disable implicit generation of these functions.
353 emplace_iterator_base(const emplace_iterator_base&) = default;
354 emplace_iterator_base(emplace_iterator_base&&) noexcept = default;
355 emplace_iterator_base& operator=(emplace_iterator_base&) = default;
356 emplace_iterator_base& operator=(const emplace_iterator_base&) = default;
357 emplace_iterator_base& operator=(emplace_iterator_base&&) noexcept = default;
358 };
359
360 /**
361 * Concrete instantiation of emplace_iterator_base. All emplace iterator
362 * classes; folly::emplace_iterator, folly::hint_emplace_iterator,
363 * folly::front_emplace_iterator, and folly::back_emplace_iterator; are just
364 * type aliases of this class.
365 *
366 * It is not possible to alias emplace_iterator_base directly, because type
367 * aliases cannot be used for CRTP.
368 */
369 template <
370 template <typename>
371 class EmplaceImplT,
372 typename Container,
373 bool implicit_unpack>
374 class emplace_iterator_impl
375 : public emplace_iterator_base<
376 emplace_iterator_impl<EmplaceImplT, Container, implicit_unpack>,
377 EmplaceImplT<Container>,
378 implicit_unpack> {
379 private:
380 using Base = emplace_iterator_base<
381 emplace_iterator_impl,
382 EmplaceImplT<Container>,
383 implicit_unpack>;
384
385 public:
386 using Base::Base;
387 using Base::operator=;
388
389 // We need all of these explicit defaults because the custom operator=
390 // overloads disable implicit generation of these functions.
391 emplace_iterator_impl(const emplace_iterator_impl&) = default;
392 emplace_iterator_impl(emplace_iterator_impl&&) noexcept = default;
393 emplace_iterator_impl& operator=(emplace_iterator_impl&) = default;
394 emplace_iterator_impl& operator=(const emplace_iterator_impl&) = default;
395 emplace_iterator_impl& operator=(emplace_iterator_impl&&) noexcept = default;
396 };
397 } // namespace detail
398
399 /**
400 * Behaves just like std::insert_iterator except that it calls emplace()
401 * instead of insert(). Uses perfect forwarding.
402 */
403 template <typename Container, bool implicit_unpack = true>
404 using emplace_iterator =
405 detail::emplace_iterator_impl<detail::Emplace, Container, implicit_unpack>;
406
407 /**
408 * Behaves just like std::insert_iterator except that it calls emplace_hint()
409 * instead of insert(). Uses perfect forwarding.
410 */
411 template <typename Container, bool implicit_unpack = true>
412 using hint_emplace_iterator = detail::
413 emplace_iterator_impl<detail::EmplaceHint, Container, implicit_unpack>;
414
415 /**
416 * Behaves just like std::front_insert_iterator except that it calls
417 * emplace_front() instead of insert(). Uses perfect forwarding.
418 */
419 template <typename Container, bool implicit_unpack = true>
420 using front_emplace_iterator = detail::
421 emplace_iterator_impl<detail::EmplaceFront, Container, implicit_unpack>;
422
423 /**
424 * Behaves just like std::back_insert_iterator except that it calls
425 * emplace_back() instead of insert(). Uses perfect forwarding.
426 */
427 template <typename Container, bool implicit_unpack = true>
428 using back_emplace_iterator = detail::
429 emplace_iterator_impl<detail::EmplaceBack, Container, implicit_unpack>;
430
431 /**
432 * Convenience function to construct a folly::emplace_iterator, analogous to
433 * std::inserter().
434 *
435 * Setting implicit_unpack to false will disable implicit unpacking of
436 * single std::pair and std::tuple arguments to the iterator's operator=. That
437 * may be desirable in case of constructors that expect a std::pair or
438 * std::tuple argument.
439 */
440 template <bool implicit_unpack = true, typename Container>
emplacer(Container & c,typename Container::iterator i)441 emplace_iterator<Container, implicit_unpack> emplacer(
442 Container& c, typename Container::iterator i) {
443 return emplace_iterator<Container, implicit_unpack>(c, std::move(i));
444 }
445
446 /**
447 * Convenience function to construct a folly::hint_emplace_iterator, analogous
448 * to std::inserter().
449 *
450 * Setting implicit_unpack to false will disable implicit unpacking of
451 * single std::pair and std::tuple arguments to the iterator's operator=. That
452 * may be desirable in case of constructors that expect a std::pair or
453 * std::tuple argument.
454 */
455 template <bool implicit_unpack = true, typename Container>
hint_emplacer(Container & c,typename Container::iterator i)456 hint_emplace_iterator<Container, implicit_unpack> hint_emplacer(
457 Container& c, typename Container::iterator i) {
458 return hint_emplace_iterator<Container, implicit_unpack>(c, std::move(i));
459 }
460
461 /**
462 * Convenience function to construct a folly::front_emplace_iterator, analogous
463 * to std::front_inserter().
464 *
465 * Setting implicit_unpack to false will disable implicit unpacking of
466 * single std::pair and std::tuple arguments to the iterator's operator=. That
467 * may be desirable in case of constructors that expect a std::pair or
468 * std::tuple argument.
469 */
470 template <bool implicit_unpack = true, typename Container>
front_emplacer(Container & c)471 front_emplace_iterator<Container, implicit_unpack> front_emplacer(
472 Container& c) {
473 return front_emplace_iterator<Container, implicit_unpack>(c);
474 }
475
476 /**
477 * Convenience function to construct a folly::back_emplace_iterator, analogous
478 * to std::back_inserter().
479 *
480 * Setting implicit_unpack to false will disable implicit unpacking of
481 * single std::pair and std::tuple arguments to the iterator's operator=. That
482 * may be desirable in case of constructors that expect a std::pair or
483 * std::tuple argument.
484 */
485 template <bool implicit_unpack = true, typename Container>
back_emplacer(Container & c)486 back_emplace_iterator<Container, implicit_unpack> back_emplacer(Container& c) {
487 return back_emplace_iterator<Container, implicit_unpack>(c);
488 }
489 } // namespace folly
490