back_emplace_iterator and related classes and utility functions
[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  * Common typedefs and methods for folly::emplace_iterator,
154  * folly::front_emplace_iterator, and folly::back_emplace_iterator. Implements
155  * everything except the actual emplace function call.
156  */
157 template <typename Derived, typename Container, bool implicit_unpack>
158 class emplace_iterator_base;
159
160 /**
161  * Partial specialization of emplace_iterator_base with implicit unpacking
162  * disabled.
163  */
164 template <typename Derived, typename Container>
165 class emplace_iterator_base<Derived, Container, false> {
166  public:
167   // Iterator traits.
168   using iterator_category = std::output_iterator_tag;
169   using value_type = void;
170   using difference_type = void;
171   using pointer = void;
172   using reference = void;
173   using container_type = Container;
174
175   explicit emplace_iterator_base(Container& container)
176       : container(std::addressof(container)) {}
177
178   /**
179    * Canonical output operator. Forwards single argument straight to container's
180    * emplace function.
181    */
182   template <typename T>
183   Derived& operator=(T&& arg) {
184     return static_cast<Derived*>(this)->emplace(std::forward<T>(arg));
185   }
186
187   /**
188    * Special output operator for packed arguments. Unpacks args and performs
189    * variadic call to container's emplace function.
190    */
191   template <typename... Args>
192   Derived& operator=(emplace_args<Args...>& args) {
193     return unpackAndEmplace(args, std::index_sequence_for<Args...>{});
194   }
195   template <typename... Args>
196   Derived& operator=(const emplace_args<Args...>& args) {
197     return unpackAndEmplace(args, std::index_sequence_for<Args...>{});
198   }
199   template <typename... Args>
200   Derived& operator=(emplace_args<Args...>&& args) {
201     return unpackAndEmplace(
202         std::move(args), std::index_sequence_for<Args...>{});
203   }
204
205   // No-ops.
206   Derived& operator*() {
207     return static_cast<Derived&>(*this);
208   }
209   Derived& operator++() {
210     return static_cast<Derived&>(*this);
211   }
212   Derived& operator++(int) {
213     return static_cast<Derived&>(*this);
214   }
215
216   // We need all of these explicit defaults because the custom operator=
217   // overloads disable implicit generation of these functions.
218   emplace_iterator_base(const emplace_iterator_base&) = default;
219   emplace_iterator_base(emplace_iterator_base&&) noexcept = default;
220   emplace_iterator_base& operator=(emplace_iterator_base&) = default;
221   emplace_iterator_base& operator=(const emplace_iterator_base&) = default;
222   emplace_iterator_base& operator=(emplace_iterator_base&&) noexcept = default;
223
224  protected:
225   using Class = emplace_iterator_base;
226
227   template <typename Args, std::size_t... I>
228   Derived& unpackAndEmplace(Args& args, std::index_sequence<I...>) {
229     return static_cast<Derived*>(this)->emplace(get_emplace_arg<I>(args)...);
230   }
231   template <typename Args, std::size_t... I>
232   Derived& unpackAndEmplace(const Args& args, std::index_sequence<I...>) {
233     return static_cast<Derived*>(this)->emplace(get_emplace_arg<I>(args)...);
234   }
235   template <typename Args, std::size_t... I>
236   Derived& unpackAndEmplace(Args&& args, std::index_sequence<I...>) {
237     return static_cast<Derived*>(this)->emplace(
238         get_emplace_arg<I>(std::move(args))...);
239   }
240
241   Container* container;
242 };
243
244 /**
245  * Partial specialization of emplace_iterator_base with implicit unpacking
246  * enabled.
247  *
248  * Uses inheritance rather than SFINAE. operator= requires a single argument,
249  * which makes it impossible to use std::enable_if or similar.
250  */
251 template <typename Derived, typename Container>
252 class emplace_iterator_base<Derived, Container, true>
253     : public emplace_iterator_base<Derived, Container, false> {
254  public:
255   using emplace_iterator_base<Derived, Container, false>::emplace_iterator_base;
256   using emplace_iterator_base<Derived, Container, false>::operator=;
257
258   /**
259    * Special output operator for arguments packed into a std::pair. Unpacks
260    * the pair and performs variadic call to container's emplace function.
261    */
262   template <typename... Args>
263   Derived& operator=(std::pair<Args...>& args) {
264     return this->unpackAndEmplace(args, std::index_sequence_for<Args...>{});
265   }
266   template <typename... Args>
267   Derived& operator=(const std::pair<Args...>& args) {
268     return this->unpackAndEmplace(args, std::index_sequence_for<Args...>{});
269   }
270   template <typename... Args>
271   Derived& operator=(std::pair<Args...>&& args) {
272     return this->unpackAndEmplace(
273         std::move(args), std::index_sequence_for<Args...>{});
274   }
275
276   /**
277    * Special output operator for arguments packed into a std::tuple. Unpacks
278    * the tuple and performs variadic call to container's emplace function.
279    */
280   template <typename... Args>
281   Derived& operator=(std::tuple<Args...>& args) {
282     return this->unpackAndEmplace(args, std::index_sequence_for<Args...>{});
283   }
284   template <typename... Args>
285   Derived& operator=(const std::tuple<Args...>& args) {
286     return this->unpackAndEmplace(args, std::index_sequence_for<Args...>{});
287   }
288   template <typename... Args>
289   Derived& operator=(std::tuple<Args...>&& args) {
290     return this->unpackAndEmplace(
291         std::move(args), std::index_sequence_for<Args...>{});
292   }
293
294   // We need all of these explicit defaults because the custom operator=
295   // overloads disable implicit generation of these functions.
296   emplace_iterator_base(const emplace_iterator_base&) = default;
297   emplace_iterator_base(emplace_iterator_base&&) noexcept = default;
298   emplace_iterator_base& operator=(emplace_iterator_base&) = default;
299   emplace_iterator_base& operator=(const emplace_iterator_base&) = default;
300   emplace_iterator_base& operator=(emplace_iterator_base&&) noexcept = default;
301 };
302 } // folly::detail
303
304 /**
305  * Behaves just like std::insert_iterator except that it calls emplace()
306  * instead of insert(). Uses perfect forwarding.
307  */
308 template <typename Container, bool implicit_unpack = true>
309 class emplace_iterator : public detail::emplace_iterator_base<
310                              emplace_iterator<Container>,
311                              Container,
312                              implicit_unpack> {
313  private:
314   using Base = detail::emplace_iterator_base<
315       emplace_iterator<Container>,
316       Container,
317       implicit_unpack>;
318
319  public:
320   emplace_iterator(Container& container, typename Container::iterator i)
321       : Base(container), iter(std::move(i)) {}
322
323   using Base::operator=;
324
325   // We need all of these explicit defaults because the custom operator=
326   // overloads disable implicit generation of these functions.
327   emplace_iterator(const emplace_iterator&) = default;
328   emplace_iterator(emplace_iterator&&) noexcept = default;
329   emplace_iterator& operator=(emplace_iterator&) = default;
330   emplace_iterator& operator=(const emplace_iterator&) = default;
331   emplace_iterator& operator=(emplace_iterator&&) noexcept = default;
332
333  protected:
334   typename Container::iterator iter;
335
336  private:
337   friend typename Base::Class;
338   template <typename... Args>
339   emplace_iterator& emplace(Args&&... args) {
340     iter = this->container->emplace(iter, std::forward<Args>(args)...);
341     ++iter;
342     return *this;
343   }
344 };
345
346 /**
347  * Behaves just like std::front_insert_iterator except that it calls
348  * emplace_front() instead of insert_front(). Uses perfect forwarding.
349  */
350 template <typename Container, bool implicit_unpack = true>
351 class front_emplace_iterator : public detail::emplace_iterator_base<
352                                    front_emplace_iterator<Container>,
353                                    Container,
354                                    implicit_unpack> {
355  private:
356   using Base = detail::emplace_iterator_base<
357       front_emplace_iterator<Container>,
358       Container,
359       implicit_unpack>;
360
361  public:
362   using Base::Base;
363   using Base::operator=;
364
365   // We need all of these explicit defaults because the custom operator=
366   // overloads disable implicit generation of these functions.
367   front_emplace_iterator(const front_emplace_iterator&) = default;
368   front_emplace_iterator(front_emplace_iterator&&) noexcept = default;
369   front_emplace_iterator& operator=(front_emplace_iterator&) = default;
370   front_emplace_iterator& operator=(const front_emplace_iterator&) = default;
371   front_emplace_iterator& operator=(front_emplace_iterator&&) noexcept =
372       default;
373
374  private:
375   friend typename Base::Class;
376   template <typename... Args>
377   front_emplace_iterator& emplace(Args&&... args) {
378     this->container->emplace_front(std::forward<Args>(args)...);
379     return *this;
380   }
381 };
382
383 /**
384  * Behaves just like std::back_insert_iterator except that it calls
385  * emplace_back() instead of insert_back(). Uses perfect forwarding.
386  */
387 template <typename Container, bool implicit_unpack = true>
388 class back_emplace_iterator : public detail::emplace_iterator_base<
389                                   back_emplace_iterator<Container>,
390                                   Container,
391                                   implicit_unpack> {
392  private:
393   using Base = detail::emplace_iterator_base<
394       back_emplace_iterator<Container>,
395       Container,
396       implicit_unpack>;
397
398  public:
399   using Base::Base;
400   using Base::operator=;
401
402   // We need all of these explicit defaults because the custom operator=
403   // overloads disable implicit generation of these functions.
404   back_emplace_iterator(const back_emplace_iterator&) = default;
405   back_emplace_iterator(back_emplace_iterator&&) noexcept = default;
406   back_emplace_iterator& operator=(back_emplace_iterator&) = default;
407   back_emplace_iterator& operator=(const back_emplace_iterator&) = default;
408   back_emplace_iterator& operator=(back_emplace_iterator&&) noexcept = default;
409
410  private:
411   friend typename Base::Class;
412   template <typename... Args>
413   back_emplace_iterator& emplace(Args&&... args) {
414     this->container->emplace_back(std::forward<Args>(args)...);
415     return *this;
416   }
417 };
418
419 /**
420  * Convenience function to construct a folly::emplace_iterator, analogous to
421  * std::inserter().
422  *
423  * Setting implicit_unpack to false will disable implicit unpacking of
424  * single std::pair and std::tuple arguments to the iterator's operator=. That
425  * may be desirable in case of constructors that expect a std::pair or
426  * std::tuple argument.
427  */
428 template <bool implicit_unpack = true, typename Container>
429 emplace_iterator<Container, implicit_unpack> emplacer(
430     Container& c,
431     typename Container::iterator i) {
432   return emplace_iterator<Container, implicit_unpack>(c, std::move(i));
433 }
434
435 /**
436  * Convenience function to construct a folly::front_emplace_iterator, analogous
437  * to std::front_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 front_emplace_iterator<Container, implicit_unpack> front_emplacer(
446     Container& c) {
447   return front_emplace_iterator<Container, implicit_unpack>(c);
448 }
449
450 /**
451  * Convenience function to construct a folly::back_emplace_iterator, analogous
452  * to std::back_inserter().
453  *
454  * Setting implicit_unpack to false will disable implicit unpacking of
455  * single std::pair and std::tuple arguments to the iterator's operator=. That
456  * may be desirable in case of constructors that expect a std::pair or
457  * std::tuple argument.
458  */
459 template <bool implicit_unpack = true, typename Container>
460 back_emplace_iterator<Container, implicit_unpack> back_emplacer(Container& c) {
461   return back_emplace_iterator<Container, implicit_unpack>(c);
462 }
463 }