1 /*
2 * Copyright 2017-present Facebook, Inc.
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, index_sequence_for<Args...>{});
256 }
257 template <typename... Args>
258 Derived& operator=(const emplace_args<Args...>& args) {
259 return unpackAndEmplace(args, index_sequence_for<Args...>{});
260 }
261 template <typename... Args>
262 Derived& operator=(emplace_args<Args...>&& args) {
263 return unpackAndEmplace(std::move(args), index_sequence_for<Args...>{});
264 }
265
266 // No-ops.
267 Derived& operator*() {
268 return static_cast<Derived&>(*this);
269 }
270 Derived& operator++() {
271 return static_cast<Derived&>(*this);
272 }
273 Derived& operator++(int) {
274 return static_cast<Derived&>(*this);
275 }
276
277 // We need all of these explicit defaults because the custom operator=
278 // overloads disable implicit generation of these functions.
279 emplace_iterator_base(const emplace_iterator_base&) = default;
280 emplace_iterator_base(emplace_iterator_base&&) noexcept = default;
281 emplace_iterator_base& operator=(emplace_iterator_base&) = default;
282 emplace_iterator_base& operator=(const emplace_iterator_base&) = default;
283 emplace_iterator_base& operator=(emplace_iterator_base&&) noexcept = default;
284
285 protected:
286 template <typename Args, std::size_t... I>
unpackAndEmplace(Args & args,index_sequence<I...>)287 Derived& unpackAndEmplace(Args& args, 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(const Args & args,index_sequence<I...>)292 Derived& unpackAndEmplace(const Args& args, index_sequence<I...>) {
293 this->emplace(get_emplace_arg<I>(args)...);
294 return static_cast<Derived&>(*this);
295 }
296 template <typename Args, std::size_t... I>
unpackAndEmplace(Args && args,index_sequence<I...>)297 Derived& unpackAndEmplace(Args&& args, index_sequence<I...>) {
298 this->emplace(get_emplace_arg<I>(std::move(args))...);
299 return static_cast<Derived&>(*this);
300 }
301 };
302
303 /**
304 * Partial specialization of emplace_iterator_base with implicit unpacking
305 * enabled.
306 *
307 * Uses inheritance rather than SFINAE. operator= requires a single argument,
308 * which makes it very tricky to use std::enable_if or similar.
309 */
310 template <typename Derived, typename EmplaceImpl>
311 class emplace_iterator_base<Derived, EmplaceImpl, true>
312 : public emplace_iterator_base<Derived, EmplaceImpl, false> {
313 private:
314 using Base = emplace_iterator_base<Derived, EmplaceImpl, false>;
315
316 public:
317 using Base::Base;
318 using Base::operator=;
319
320 /**
321 * Special output operator for arguments packed into a std::pair. Unpacks
322 * the pair and performs variadic call to container's emplace function.
323 */
324 template <typename... Args>
325 Derived& operator=(std::pair<Args...>& args) {
326 return this->unpackAndEmplace(args, index_sequence_for<Args...>{});
327 }
328 template <typename... Args>
329 Derived& operator=(const std::pair<Args...>& args) {
330 return this->unpackAndEmplace(args, index_sequence_for<Args...>{});
331 }
332 template <typename... Args>
333 Derived& operator=(std::pair<Args...>&& args) {
334 return this->unpackAndEmplace(
335 std::move(args), index_sequence_for<Args...>{});
336 }
337
338 /**
339 * Special output operator for arguments packed into a std::tuple. Unpacks
340 * the tuple and performs variadic call to container's emplace function.
341 */
342 template <typename... Args>
343 Derived& operator=(std::tuple<Args...>& args) {
344 return this->unpackAndEmplace(args, index_sequence_for<Args...>{});
345 }
346 template <typename... Args>
347 Derived& operator=(const std::tuple<Args...>& args) {
348 return this->unpackAndEmplace(args, index_sequence_for<Args...>{});
349 }
350 template <typename... Args>
351 Derived& operator=(std::tuple<Args...>&& args) {
352 return this->unpackAndEmplace(
353 std::move(args), index_sequence_for<Args...>{});
354 }
355
356 // We need all of these explicit defaults because the custom operator=
357 // overloads disable implicit generation of these functions.
358 emplace_iterator_base(const emplace_iterator_base&) = default;
359 emplace_iterator_base(emplace_iterator_base&&) noexcept = default;
360 emplace_iterator_base& operator=(emplace_iterator_base&) = default;
361 emplace_iterator_base& operator=(const emplace_iterator_base&) = default;
362 emplace_iterator_base& operator=(emplace_iterator_base&&) noexcept = default;
363 };
364
365 /**
366 * Concrete instantiation of emplace_iterator_base. All emplace iterator
367 * classes; folly::emplace_iterator, folly::hint_emplace_iterator,
368 * folly::front_emplace_iterator, and folly::back_emplace_iterator; are just
369 * type aliases of this class.
370 *
371 * It is not possible to alias emplace_iterator_base directly, because type
372 * aliases cannot be used for CRTP.
373 */
374 template <
375 template <typename> class EmplaceImplT,
376 typename Container,
377 bool implicit_unpack>
378 class emplace_iterator_impl
379 : public emplace_iterator_base<
380 emplace_iterator_impl<EmplaceImplT, Container, implicit_unpack>,
381 EmplaceImplT<Container>,
382 implicit_unpack> {
383 private:
384 using Base = emplace_iterator_base<
385 emplace_iterator_impl,
386 EmplaceImplT<Container>,
387 implicit_unpack>;
388
389 public:
390 using Base::Base;
391 using Base::operator=;
392
393 // We need all of these explicit defaults because the custom operator=
394 // overloads disable implicit generation of these functions.
395 emplace_iterator_impl(const emplace_iterator_impl&) = default;
396 emplace_iterator_impl(emplace_iterator_impl&&) noexcept = default;
397 emplace_iterator_impl& operator=(emplace_iterator_impl&) = default;
398 emplace_iterator_impl& operator=(const emplace_iterator_impl&) = default;
399 emplace_iterator_impl& operator=(emplace_iterator_impl&&) noexcept = default;
400 };
401 } // namespace detail
402
403 /**
404 * Behaves just like std::insert_iterator except that it calls emplace()
405 * instead of insert(). Uses perfect forwarding.
406 */
407 template <typename Container, bool implicit_unpack = true>
408 using emplace_iterator =
409 detail::emplace_iterator_impl<detail::Emplace, Container, implicit_unpack>;
410
411 /**
412 * Behaves just like std::insert_iterator except that it calls emplace_hint()
413 * instead of insert(). Uses perfect forwarding.
414 */
415 template <typename Container, bool implicit_unpack = true>
416 using hint_emplace_iterator = detail::
417 emplace_iterator_impl<detail::EmplaceHint, Container, implicit_unpack>;
418
419 /**
420 * Behaves just like std::front_insert_iterator except that it calls
421 * emplace_front() instead of insert(). Uses perfect forwarding.
422 */
423 template <typename Container, bool implicit_unpack = true>
424 using front_emplace_iterator = detail::
425 emplace_iterator_impl<detail::EmplaceFront, Container, implicit_unpack>;
426
427 /**
428 * Behaves just like std::back_insert_iterator except that it calls
429 * emplace_back() instead of insert(). Uses perfect forwarding.
430 */
431 template <typename Container, bool implicit_unpack = true>
432 using back_emplace_iterator = detail::
433 emplace_iterator_impl<detail::EmplaceBack, Container, implicit_unpack>;
434
435 /**
436 * Convenience function to construct a folly::emplace_iterator, analogous to
437 * std::inserter().
438 *
439 * Setting implicit_unpack to false will disable implicit unpacking of
440 * single std::pair and std::tuple arguments to the iterator's operator=. That
441 * may be desirable in case of constructors that expect a std::pair or
442 * std::tuple argument.
443 */
444 template <bool implicit_unpack = true, typename Container>
emplacer(Container & c,typename Container::iterator i)445 emplace_iterator<Container, implicit_unpack> emplacer(
446 Container& c,
447 typename Container::iterator i) {
448 return emplace_iterator<Container, implicit_unpack>(c, std::move(i));
449 }
450
451 /**
452 * Convenience function to construct a folly::hint_emplace_iterator, analogous
453 * to std::inserter().
454 *
455 * Setting implicit_unpack to false will disable implicit unpacking of
456 * single std::pair and std::tuple arguments to the iterator's operator=. That
457 * may be desirable in case of constructors that expect a std::pair or
458 * std::tuple argument.
459 */
460 template <bool implicit_unpack = true, typename Container>
hint_emplacer(Container & c,typename Container::iterator i)461 hint_emplace_iterator<Container, implicit_unpack> hint_emplacer(
462 Container& c,
463 typename Container::iterator i) {
464 return hint_emplace_iterator<Container, implicit_unpack>(c, std::move(i));
465 }
466
467 /**
468 * Convenience function to construct a folly::front_emplace_iterator, analogous
469 * to std::front_inserter().
470 *
471 * Setting implicit_unpack to false will disable implicit unpacking of
472 * single std::pair and std::tuple arguments to the iterator's operator=. That
473 * may be desirable in case of constructors that expect a std::pair or
474 * std::tuple argument.
475 */
476 template <bool implicit_unpack = true, typename Container>
front_emplacer(Container & c)477 front_emplace_iterator<Container, implicit_unpack> front_emplacer(
478 Container& c) {
479 return front_emplace_iterator<Container, implicit_unpack>(c);
480 }
481
482 /**
483 * Convenience function to construct a folly::back_emplace_iterator, analogous
484 * to std::back_inserter().
485 *
486 * Setting implicit_unpack to false will disable implicit unpacking of
487 * single std::pair and std::tuple arguments to the iterator's operator=. That
488 * may be desirable in case of constructors that expect a std::pair or
489 * std::tuple argument.
490 */
491 template <bool implicit_unpack = true, typename Container>
back_emplacer(Container & c)492 back_emplace_iterator<Container, implicit_unpack> back_emplacer(Container& c) {
493 return back_emplace_iterator<Container, implicit_unpack>(c);
494 }
495 } // namespace folly
496