c4fe9c1cbcaa5ad1a1d0abe60c37018811852dca
[folly.git] / folly / Iterator.h
1 /*
2  * Copyright 2017 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/Functional.h>
27
28 namespace folly {
29
30 /**
31  * Argument tuple for variadic emplace/constructor calls. Stores arguments by
32  * (decayed) value. Restores original argument types with reference qualifiers
33  * and adornments at unpack time to emulate perfect forwarding.
34  *
35  * Uses inheritance instead of a type alias to std::tuple so that emplace
36  * iterators with implicit unpacking disabled can distinguish between
37  * emplace_args and std::tuple parameters.
38  *
39  * @seealso folly::make_emplace_args
40  * @seealso folly::get_emplace_arg
41  */
42 template <typename... Args>
43 struct emplace_args : public std::tuple<std::decay_t<Args>...> {
44   using storage_type = std::tuple<std::decay_t<Args>...>;
45   using storage_type::storage_type;
46 };
47
48 /**
49  * Pack arguments in a tuple for assignment to a folly::emplace_iterator,
50  * folly::front_emplace_iterator, or folly::back_emplace_iterator. The
51  * iterator's operator= will unpack the tuple and pass the unpacked arguments
52  * to the container's emplace function, which in turn forwards the arguments to
53  * the (multi-argument) constructor of the target class.
54  *
55  * Argument tuples generated with folly::make_emplace_args will be unpacked
56  * before being passed to the container's emplace function, even for iterators
57  * where implicit_unpack is set to false (so they will not implicitly unpack
58  * std::pair or std::tuple arguments to operator=).
59  *
60  * Arguments are copied (lvalues) or moved (rvalues). To avoid copies and moves,
61  * wrap references using std::ref(), std::cref(), and folly::rref(). Beware of
62  * dangling references, especially references to temporary objects created with
63  * folly::rref().
64  *
65  * Note that an argument pack created with folly::make_emplace_args is different
66  * from an argument pack created with std::make_pair or std::make_tuple.
67  * Specifically, passing a std::pair&& or std::tuple&& to an emplace iterator's
68  * operator= will pass rvalue references to all fields of that tuple to the
69  * container's emplace function, while passing an emplace_args&& to operator=
70  * will cast those field references to the exact argument types as passed to
71  * folly::make_emplace_args previously. If all arguments have been wrapped by
72  * std::reference_wrappers or folly::rvalue_reference_wrappers, the result will
73  * be the same as if the container's emplace function had been called directly
74  * (perfect forwarding), with no temporary copies of the arguments.
75  *
76  * @seealso folly::rref
77  *
78  * @example
79  *   class Widget { Widget(int, int); };
80  *   std::vector<Widget> makeWidgets(const std::vector<int>& in) {
81  *     std::vector<Widget> out;
82  *     std::transform(
83  *         in.begin(),
84  *         in.end(),
85  *         folly::back_emplacer(out),
86  *         [](int i) { return folly::make_emplace_args(i, i); });
87  *     return out;
88  *   }
89  */
90 template <typename... Args>
91 emplace_args<Args...> make_emplace_args(Args&&... args) noexcept(
92     noexcept(emplace_args<Args...>(std::forward<Args>(args)...))) {
93   return emplace_args<Args...>(std::forward<Args>(args)...);
94 }
95
96 namespace detail {
97 template <typename Arg>
98 decltype(auto) unwrap_emplace_arg(Arg&& arg) noexcept {
99   return std::forward<Arg>(arg);
100 }
101 template <typename Arg>
102 decltype(auto) unwrap_emplace_arg(std::reference_wrapper<Arg> arg) noexcept {
103   return arg.get();
104 }
105 template <typename Arg>
106 decltype(auto) unwrap_emplace_arg(
107     folly::rvalue_reference_wrapper<Arg> arg) noexcept {
108   return std::move(arg).get();
109 }
110 }
111
112 /**
113  * Getter function for unpacking a single emplace argument.
114  *
115  * Calling get_emplace_arg on an emplace_args rvalue reference results in
116  * perfect forwarding of the original input types. A special case are
117  * std::reference_wrapper and folly::rvalue_reference_wrapper objects within
118  * folly::emplace_args. These are also unwrapped so that the bare reference is
119  * returned.
120  *
121  * std::get is not a customization point in the standard library, so the
122  * cleanest solution was to define our own getter function.
123  */
124 template <size_t I, typename... Args>
125 decltype(auto) get_emplace_arg(emplace_args<Args...>&& args) noexcept {
126   using Out = std::tuple<Args...>;
127   return detail::unwrap_emplace_arg(
128       std::forward<std::tuple_element_t<I, Out>>(std::get<I>(args)));
129 }
130 template <size_t I, typename... Args>
131 decltype(auto) get_emplace_arg(emplace_args<Args...>& args) noexcept {
132   return detail::unwrap_emplace_arg(std::get<I>(args));
133 }
134 template <size_t I, typename... Args>
135 decltype(auto) get_emplace_arg(const emplace_args<Args...>& args) noexcept {
136   return detail::unwrap_emplace_arg(std::get<I>(args));
137 }
138 template <size_t I, typename Args>
139 decltype(auto) get_emplace_arg(Args&& args) noexcept {
140   return std::get<I>(std::move(args));
141 }
142 template <size_t I, typename Args>
143 decltype(auto) get_emplace_arg(Args& args) noexcept {
144   return std::get<I>(args);
145 }
146 template <size_t I, typename Args>
147 decltype(auto) get_emplace_arg(const Args& args) noexcept {
148   return std::get<I>(args);
149 }
150
151 namespace detail {
152 /**
153  * Emplace implementation class for folly::emplace_iterator.
154  */
155 template <typename Container>
156 struct Emplace {
157   Emplace(Container& c, typename Container::iterator i)
158       : container(std::addressof(c)), iter(std::move(i)) {}
159   template <typename... Args>
160   void emplace(Args&&... args) {
161     iter = container->emplace(iter, std::forward<Args>(args)...);
162     ++iter;
163   }
164   Container* container;
165   typename Container::iterator iter;
166 };
167
168 /**
169  * Emplace implementation class for folly::hint_emplace_iterator.
170  */
171 template <typename Container>
172 struct EmplaceHint {
173   EmplaceHint(Container& c, typename Container::iterator i)
174       : container(std::addressof(c)), iter(std::move(i)) {}
175   template <typename... Args>
176   void emplace(Args&&... args) {
177     iter = container->emplace_hint(iter, std::forward<Args>(args)...);
178     ++iter;
179   }
180   Container* container;
181   typename Container::iterator iter;
182 };
183
184 /**
185  * Emplace implementation class for folly::front_emplace_iterator.
186  */
187 template <typename Container>
188 struct EmplaceFront {
189   explicit EmplaceFront(Container& c) : container(std::addressof(c)) {}
190   template <typename... Args>
191   void emplace(Args&&... args) {
192     container->emplace_front(std::forward<Args>(args)...);
193   }
194   Container* container;
195 };
196
197 /**
198  * Emplace implementation class for folly::back_emplace_iterator.
199  */
200 template <typename Container>
201 struct EmplaceBack {
202   explicit EmplaceBack(Container& c) : container(std::addressof(c)) {}
203   template <typename... Args>
204   void emplace(Args&&... args) {
205     container->emplace_back(std::forward<Args>(args)...);
206   }
207   Container* container;
208 };
209
210 /**
211  * Generic base class and implementation of all emplace iterator classes.
212  *
213  * Uses the curiously recurring template pattern (CRTP) to cast `this*` to
214  * `Derived*`; i.e., to implement covariant return types in a generic manner.
215  */
216 template <typename Derived, typename EmplaceImpl, bool implicit_unpack>
217 class emplace_iterator_base;
218
219 /**
220  * Partial specialization of emplace_iterator_base with implicit unpacking
221  * disabled.
222  */
223 template <typename Derived, typename EmplaceImpl>
224 class emplace_iterator_base<Derived, EmplaceImpl, false>
225     : protected EmplaceImpl /* protected implementation inheritance */ {
226  public:
227   // Iterator traits.
228   using iterator_category = std::output_iterator_tag;
229   using value_type = void;
230   using difference_type = void;
231   using pointer = void;
232   using reference = void;
233   using container_type =
234       std::remove_reference_t<decltype(*EmplaceImpl::container)>;
235
236   using EmplaceImpl::EmplaceImpl;
237
238   /**
239    * Canonical output operator. Forwards single argument straight to container's
240    * emplace function.
241    */
242   template <typename T>
243   Derived& operator=(T&& arg) {
244     this->emplace(std::forward<T>(arg));
245     return static_cast<Derived&>(*this);
246   }
247
248   /**
249    * Special output operator for packed arguments. Unpacks args and performs
250    * variadic call to container's emplace function.
251    */
252   template <typename... Args>
253   Derived& operator=(emplace_args<Args...>& args) {
254     return unpackAndEmplace(args, std::index_sequence_for<Args...>{});
255   }
256   template <typename... Args>
257   Derived& operator=(const emplace_args<Args...>& args) {
258     return unpackAndEmplace(args, std::index_sequence_for<Args...>{});
259   }
260   template <typename... Args>
261   Derived& operator=(emplace_args<Args...>&& args) {
262     return unpackAndEmplace(
263         std::move(args), std::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>
287   Derived& unpackAndEmplace(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>
292   Derived& unpackAndEmplace(const Args& args, std::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>
297   Derived& unpackAndEmplace(Args&& args, std::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, std::index_sequence_for<Args...>{});
327   }
328   template <typename... Args>
329   Derived& operator=(const std::pair<Args...>& args) {
330     return this->unpackAndEmplace(args, std::index_sequence_for<Args...>{});
331   }
332   template <typename... Args>
333   Derived& operator=(std::pair<Args...>&& args) {
334     return this->unpackAndEmplace(
335         std::move(args), std::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, std::index_sequence_for<Args...>{});
345   }
346   template <typename... Args>
347   Derived& operator=(const std::tuple<Args...>& args) {
348     return this->unpackAndEmplace(args, std::index_sequence_for<Args...>{});
349   }
350   template <typename... Args>
351   Derived& operator=(std::tuple<Args...>&& args) {
352     return this->unpackAndEmplace(
353         std::move(args), std::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 } // folly::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>
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>
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>
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>
492 back_emplace_iterator<Container, implicit_unpack> back_emplacer(Container& c) {
493   return back_emplace_iterator<Container, implicit_unpack>(c);
494 }
495 }