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