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 }