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 }