folly/Foreach-inl.h

   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 #include <cassert>
  18 #include <cstdint>
  19 #include <initializer_list>
  20 #include <iterator>
  21 #include <tuple>
  22 #include <type_traits>
  23 #include <utility>
  24
  25 #include <folly/Traits.h>
  26
  27 namespace folly {
  28
  29 namespace for_each_detail {
  30
  31 namespace adl {
  32
  33 /* using override */
  34 using std::begin;
  35 /* using override */
  36 using std::end;
  37 /* using override */
  38 using std::get;
  39
  40 /**
  41  * The adl_ functions below lookup the function name in the namespace of the
  42  * type of the object being passed into the function.  If no function with
  43  * that name exists for the passed object then the default std:: versions are
  44  * going to be called
  45  */
  46 template <std::size_t Index, typename Type>
  47 auto adl_get(Type&& instance) -> decltype(get<Index>(std::declval<Type>())) {
  48   return get<Index>(std::forward<Type>(instance));
  49 }
  50 template <typename Type>
  51 auto adl_begin(Type&& instance) -> decltype(begin(instance)) {
  52   return begin(instance);
  53 }
  54 template <typename Type>
  55 auto adl_end(Type&& instance) -> decltype(end(instance)) {
  56   return end(instance);
  57 }
  58
  59 } // namespace adl
  60
  61 /**
  62  * Enable if the range supports fetching via non member get<>()
  63  */
  64 template <typename T>
  65 using EnableIfNonMemberGetFound =
  66     void_t<decltype(adl::adl_get<0>(std::declval<T>()))>;
  67 /**
  68  * Enable if the range supports fetching via a member get<>()
  69  */
  70 template <typename T>
  71 using EnableIfMemberGetFound =
  72     void_t<decltype(std::declval<T>().template get<0>())>;
  73
  74 /**
  75  * A get that tries ADL get<> first and if that is not found tries to execute
  76  * a member function get<> on the instance, just as proposed by the structured
  77  * bindings proposal here 11.5.3
  78  * http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2017/n4659.pdf
  79  */
  80 template <std::size_t Index, typename Type, typename = void>
  81 struct Get {
  82   template <typename T>
  83   static auto impl(T&& instance)
  84       -> decltype(adl::adl_get<Index>(std::declval<T>())) {
  85     return adl::adl_get<Index>(std::forward<T>(instance));
  86   }
  87 };
  88 template <std::size_t Index, typename Type>
  89 struct Get<Index, Type, EnableIfMemberGetFound<Type>> {
  90   template <typename T>
  91   static auto impl(T&& instance)
  92       -> decltype(std::declval<T>().template get<Index>()) {
  93     return std::forward<T>(instance).template get<Index>();
  94   }
  95 };
  96
  97 /**
  98  * Concepts-ish
  99  */
 100 /**
 101  * Check if the range is a tuple or a range
 102  */
 103 template <typename Type, typename T = typename std::decay<Type>::type>
 104 using EnableIfTuple = void_t<
 105     decltype(Get<0, T>::impl(std::declval<T>())),
 106     decltype(std::tuple_size<T>::value)>;
 107
 108 /**
 109  * Check if the range is a range
 110  */
 111 template <typename Type, typename T = typename std::decay<Type>::type>
 112 using EnableIfRange = void_t<
 113     decltype(adl::adl_begin(std::declval<T>())),
 114     decltype(adl::adl_end(std::declval<T>()))>;
 115
 116 /**
 117  * Forwards the return value of the first element of the range, used to
 118  * determine the type of the first element in the range in SFINAE use cases
 119  */
 120 template <typename Sequence, typename = void>
 121 struct DeclvalSequence {
 122   using type = decltype(*(adl::adl_begin(std::declval<Sequence>())));
 123 };
 124
 125 template <typename Sequence>
 126 struct DeclvalSequence<Sequence, EnableIfTuple<Sequence>> {
 127   using type = decltype(Get<0, Sequence>::impl(std::declval<Sequence>()));
 128 };
 129
 130 /**
 131  * Check if the functor accepts one or two arguments, one of the first element
 132  * in the range, assuming that all the other elements can also be passed to the
 133  * functor, and the second being an instantiation of std::integral_constant,
 134  * and the third being an instantiation of LoopControl, to provide
 135  * breakability to the loop
 136  */
 137 template <typename Sequence, typename Func>
 138 using EnableIfAcceptsOneArgument = void_t<decltype(std::declval<Func>()(
 139     std::declval<typename DeclvalSequence<Sequence>::type>()))>;
 140 template <typename Sequence, typename Func>
 141 using EnableIfAcceptsTwoArguments = void_t<decltype(std::declval<Func>()(
 142     std::declval<typename DeclvalSequence<Sequence>::type>(),
 143     std::integral_constant<std::size_t, 0>{}))>;
 144 template <typename Sequence, typename Func>
 145 using EnableIfAcceptsThreeArguments = void_t<decltype(std::declval<Func>()(
 146     std::declval<typename DeclvalSequence<Sequence>::type>(),
 147     std::integral_constant<std::size_t, 0>{},
 148     adl::adl_begin(std::declval<Sequence>())))>;
 149 template <typename Sequence, typename Func>
 150 using EnableIfBreaksRange = std::enable_if_t<std::is_same<
 151     typename std::decay<decltype(std::declval<Func>()(
 152         std::declval<typename DeclvalSequence<Sequence>::type>(),
 153         std::size_t{0},
 154         adl::adl_begin(std::declval<Sequence>())))>::type,
 155     LoopControl>::value>;
 156 template <typename Sequence, typename Func>
 157 using EnableIfBreaksTuple = std::enable_if_t<std::is_same<
 158     typename std::decay<decltype(std::declval<Func>()(
 159         std::declval<typename DeclvalSequence<Sequence>::type>(),
 160         std::integral_constant<std::size_t, 0>{}))>::type,
 161     LoopControl>::value>;
 162 /**
 163  * Enables if the sequence has random access iterators
 164  */
 165 template <typename Sequence>
 166 using EnableIfRandomAccessIterators = std::enable_if_t<std::is_same<
 167     typename std::iterator_traits<typename std::decay<decltype(
 168         adl::adl_begin(std::declval<Sequence>()))>::type>::iterator_category,
 169     std::random_access_iterator_tag>::value>;
 170 template <typename Sequence, typename Index>
 171 using EnableIfHasIndexingOperator =
 172     void_t<decltype(std::declval<Sequence>()[std::declval<Index>()])>;
 173
 174 /**
 175  * Implementation for the range iteration, this provides specializations in
 176  * the case where the function returns a break or continue.
 177  */
 178 template <typename Seq, typename F, typename = void>
 179 struct ForEachRange {
 180   template <typename Sequence, typename Func>
 181   static void impl(Sequence&& range, Func& func) {
 182     auto first = adl::adl_begin(range);
 183     auto last = adl::adl_end(range);
 184     for (auto index = std::size_t{0}; first != last; ++index) {
 185       auto next = std::next(first);
 186       func(*first, index, first);
 187       first = next;
 188     }
 189   }
 190 };
 191
 192 template <typename Seq, typename F>
 193 struct ForEachRange<Seq, F, EnableIfBreaksRange<Seq, F>> {
 194   template <typename Sequence, typename Func>
 195   static void impl(Sequence&& range, Func& func) {
 196     auto first = adl::adl_begin(range);
 197     auto last = adl::adl_end(range);
 198     for (auto index = std::size_t{0}; first != last; ++index) {
 199       auto next = std::next(first);
 200       if (loop_break == func(*first, index, first)) {
 201         break;
 202       }
 203       first = next;
 204     }
 205   }
 206 };
 207
 208 /**
 209  * Implementations for the runtime function
 210  */
 211 template <
 212     typename Sequence,
 213     typename Func,
 214     EnableIfAcceptsThreeArguments<Sequence, Func>* = nullptr>
 215 void for_each_range_impl(Sequence&& range, Func& func) {
 216   ForEachRange<Sequence, Func>::impl(std::forward<Sequence>(range), func);
 217 }
 218 template <
 219     typename Sequence,
 220     typename Func,
 221     EnableIfAcceptsTwoArguments<Sequence, Func>* = nullptr>
 222 void for_each_range_impl(Sequence&& range, Func& func) {
 223   // make a three arg adaptor for the function passed in so that the main
 224   // implementation function can be used
 225   auto three_arg_adaptor = [&func](
 226                                auto&& ele, auto index, auto) -> decltype(auto) {
 227     return func(std::forward<decltype(ele)>(ele), index);
 228   };
 229   for_each_range_impl(std::forward<Sequence>(range), three_arg_adaptor);
 230 }
 231
 232 template <
 233     typename Sequence,
 234     typename Func,
 235     EnableIfAcceptsOneArgument<Sequence, Func>* = nullptr>
 236 void for_each_range_impl(Sequence&& range, Func& func) {
 237   // make a three argument adaptor for the function passed in that just ignores
 238   // the second and third argument
 239   auto three_arg_adaptor = [&func](auto&& ele, auto, auto) -> decltype(auto) {
 240     return func(std::forward<decltype(ele)>(ele));
 241   };
 242   for_each_range_impl(std::forward<Sequence>(range), three_arg_adaptor);
 243 }
 244
 245 /**
 246  * Handlers for iteration
 247  */
 248 /**
 249  * The class provides a way to tell whether the function passed in to the
 250  * algorithm returns an instance of LoopControl, if it does then the break-able
 251  * implementation will be used.  If the function provided to the algorithm
 252  * does not use the break API, then the basic no break, 0 overhead
 253  * implementation will be used
 254  */
 255 template <typename Seq, typename F, typename = void>
 256 struct ForEachTupleImpl {
 257   template <typename Sequence, typename Func, std::size_t... Indices>
 258   static void
 259   impl(Sequence&& seq, Func& func, std::index_sequence<Indices...>) {
 260     // unroll the loop in an initializer list construction parameter expansion
 261     // pack
 262     static_cast<void>(std::initializer_list<int>{
 263         (func(
 264              Get<Indices, Sequence>::impl(std::forward<Sequence>(seq)),
 265              std::integral_constant<std::size_t, Indices>{}),
 266          0)...});
 267   }
 268 };
 269 template <typename Seq, typename F>
 270 struct ForEachTupleImpl<Seq, F, EnableIfBreaksTuple<Seq, F>> {
 271   template <typename Sequence, typename Func, std::size_t... Indices>
 272   static void
 273   impl(Sequence&& seq, Func& func, std::index_sequence<Indices...>) {
 274     // unroll the loop in an initializer list construction parameter expansion
 275     // pack
 276     LoopControl break_or_not = LoopControl::CONTINUE;
 277
 278     // cast to void to ignore the result, use the initialzer list constructor
 279     // to do the loop execution, the ternary conditional will decide whether
 280     // or not to evaluate the result
 281     static_cast<void>(std::initializer_list<int>{
 282         (((break_or_not == loop_continue)
 283               ? (break_or_not = func(
 284                      Get<Indices, Sequence>::impl(std::forward<Sequence>(seq)),
 285                      std::integral_constant<std::size_t, Indices>{}))
 286               : (loop_continue)),
 287          0)...});
 288   }
 289 };
 290
 291 /**
 292  * The two top level compile time loop iteration functions handle the dispatch
 293  * based on the number of arguments the passed in function can be passed, if 2
 294  * arguments can be passed then the implementation dispatches work further to
 295  * the implementation classes above.  If not then an adaptor is constructed
 296  * which is passed on to the 2 argument specialization, which then in turn
 297  * forwards implementation to the implementation classes above
 298  */
 299 template <
 300     typename Sequence,
 301     typename Func,
 302     EnableIfAcceptsTwoArguments<Sequence, Func>* = nullptr>
 303 void for_each_tuple_impl(Sequence&& seq, Func& func) {
 304   // pass the length as an index sequence to the implementation as an
 305   // optimization over manual template "tail recursion" unrolling
 306   constexpr auto length =
 307       std::tuple_size<typename std::decay<Sequence>::type>::value;
 308   ForEachTupleImpl<Sequence, Func>::impl(
 309       std::forward<Sequence>(seq), func, std::make_index_sequence<length>{});
 310 }
 311 template <
 312     typename Sequence,
 313     typename Func,
 314     EnableIfAcceptsOneArgument<Sequence, Func>* = nullptr>
 315 void for_each_tuple_impl(Sequence&& seq, Func& func) {
 316   // make an adaptor for the function passed in, in case it can only be passed
 317   // on argument
 318   auto two_arg_adaptor = [&func](auto&& ele, auto) -> decltype(auto) {
 319     return func(std::forward<decltype(ele)>(ele));
 320   };
 321   for_each_tuple_impl(std::forward<Sequence>(seq), two_arg_adaptor);
 322 }
 323
 324 /**
 325  * Top level handlers for the for_each loop, the basic specialization handles
 326  * ranges and the specialized version handles compile time ranges (tuple like)
 327  *
 328  * This implies that if a range is a compile time range, its compile time
 329  * get<> API (whether through a member function or through a ADL looked up
 330  * method) will be used in preference over iterators
 331  */
 332 template <typename R, typename = void>
 333 struct ForEachImpl {
 334   template <typename Sequence, typename Func>
 335   static void impl(Sequence&& range, Func& func) {
 336     for_each_tuple_impl(std::forward<Sequence>(range), func);
 337   }
 338 };
 339 template <typename R>
 340 struct ForEachImpl<R, EnableIfRange<R>> {
 341   template <typename Sequence, typename Func>
 342   static void impl(Sequence&& range, Func& func) {
 343     for_each_range_impl(std::forward<Sequence>(range), func);
 344   }
 345 };
 346
 347 template <typename S, typename I, typename = void>
 348 struct FetchIteratorIndexImpl {
 349   template <typename Sequence, typename Index>
 350   static decltype(auto) impl(Sequence&& sequence, Index&& index) {
 351     return std::forward<Sequence>(sequence)[std::forward<Index>(index)];
 352   }
 353 };
 354 template <typename S, typename I>
 355 struct FetchIteratorIndexImpl<S, I, EnableIfRandomAccessIterators<S>> {
 356   template <typename Sequence, typename Index>
 357   static decltype(auto) impl(Sequence&& sequence, Index index) {
 358     return *(adl::adl_begin(std::forward<Sequence>(sequence)) + index);
 359   }
 360 };
 361 template <typename S, typename = void>
 362 struct FetchImpl {
 363   template <typename Sequence, typename Index>
 364   static decltype(auto) impl(Sequence&& sequence, Index index) {
 365     return Get<static_cast<std::size_t>(index), Sequence>::impl(
 366         std::forward<Sequence>(sequence));
 367   }
 368 };
 369 template <typename S>
 370 struct FetchImpl<S, EnableIfRange<S>> {
 371   template <typename Sequence, typename Index>
 372   static decltype(auto) impl(Sequence&& sequence, Index&& index) {
 373     return FetchIteratorIndexImpl<Sequence, Index>::impl(
 374         std::forward<Sequence>(sequence), std::forward<Index>(index));
 375   }
 376 };
 377
 378 } // namespace for_each_detail
 379
 380 template <typename Sequence, typename Func>
 381 constexpr Func for_each(Sequence&& range, Func func) {
 382   for_each_detail::ForEachImpl<typename std::decay<Sequence>::type>::impl(
 383       std::forward<Sequence>(range), func);
 384   return func;
 385 }
 386
 387 template <typename Sequence, typename Index>
 388 constexpr decltype(auto) fetch(Sequence&& sequence, Index&& index) {
 389   return for_each_detail::FetchImpl<Sequence>::impl(
 390       std::forward<Sequence>(sequence), std::forward<Index>(index));
 391 }
 392
 393 } // namespace folly