Added a for_each function to iterate through ranges
authorAaryaman Sagar <aary@instagram.com>
Tue, 22 Aug 2017 17:54:11 +0000 (10:54 -0700)
committerFacebook Github Bot <facebook-github-bot@users.noreply.github.com>
Tue, 22 Aug 2017 18:03:54 +0000 (11:03 -0700)
Summary:
Adding a for_each function that allows generalized indexed and breakable iteration through ranges, these can either be runtime ranges (i.e. entities for which std::begin and std::end work) or compile time ranges (as deemed by the presence of a std::tuple_length<>, get<> (ADL resolved) functions)

The function is made to provide a convenient library based solution to the proposal p0589r0, which aims to generalize the range based for loop even further to work with compile time ranges

A drawback of using range based for loops is that sometimes you do not have access to the index within the range.  This provides easy access to that, even with compile time ranges.

Further this also provides a good way to break out of a loop without any overhead when that is not used.

A simple use case would be when using futures, if the user was doing calls to n servers then they would accept the callback with the futures like this

   auto vec = std::vector<std::future<int>>{request_one(), ...};
   when_all(vec.begin(), vec.end()).then([](auto futures) {
     folly::for_each(futures, [](auto& fut) { ... });
   });

Now when this code switches to use tuples instead of the runtime std::vector, then the loop does not need to change, the code will still work just fine

   when_all(future_one, future_two, future_three).then([](auto futures) {
     folly::for_each(futures, [](auto& fut) { ... });
   });

Reviewed By: yfeldblum

Differential Revision: D5557336

fbshipit-source-id: 79fcbafa7e1671f8856f0dcb7bf7996435dadeaa

folly/Foreach-inl.h [new file with mode: 0644]
folly/Foreach.h
folly/Makefile.am
folly/test/ForeachBenchmark.cpp
folly/test/ForeachTest.cpp

diff --git a/folly/Foreach-inl.h b/folly/Foreach-inl.h
new file mode 100644 (file)
index 0000000..bdc0bb1
--- /dev/null
@@ -0,0 +1,393 @@
+/*
+ * Copyright 2017-present Facebook, Inc.
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *   http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#include <cassert>
+#include <cstdint>
+#include <initializer_list>
+#include <iterator>
+#include <tuple>
+#include <type_traits>
+#include <utility>
+
+#include <folly/Traits.h>
+
+namespace folly {
+
+namespace for_each_detail {
+
+namespace adl {
+
+/* using override */
+using std::begin;
+/* using override */
+using std::end;
+/* using override */
+using std::get;
+
+/**
+ * The adl_ functions below lookup the function name in the namespace of the
+ * type of the object being passed into the function.  If no function with
+ * that name exists for the passed object then the default std:: versions are
+ * going to be called
+ */
+template <std::size_t Index, typename Type>
+auto adl_get(Type&& instance) -> decltype(get<Index>(std::declval<Type>())) {
+  return get<Index>(std::forward<Type>(instance));
+}
+template <typename Type>
+auto adl_begin(Type&& instance) -> decltype(begin(instance)) {
+  return begin(instance);
+}
+template <typename Type>
+auto adl_end(Type&& instance) -> decltype(end(instance)) {
+  return end(instance);
+}
+
+} // namespace adl
+
+/**
+ * Enable if the range supports fetching via non member get<>()
+ */
+template <typename T>
+using EnableIfNonMemberGetFound =
+    void_t<decltype(adl::adl_get<0>(std::declval<T>()))>;
+/**
+ * Enable if the range supports fetching via a member get<>()
+ */
+template <typename T>
+using EnableIfMemberGetFound =
+    void_t<decltype(std::declval<T>().template get<0>())>;
+
+/**
+ * A get that tries ADL get<> first and if that is not found tries to execute
+ * a member function get<> on the instance, just as proposed by the structured
+ * bindings proposal here 11.5.3
+ * http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2017/n4659.pdf
+ */
+template <std::size_t Index, typename Type, typename = void>
+struct Get {
+  template <typename T>
+  static auto impl(T&& instance)
+      -> decltype(adl::adl_get<Index>(std::declval<T>())) {
+    return adl::adl_get<Index>(std::forward<T>(instance));
+  }
+};
+template <std::size_t Index, typename Type>
+struct Get<Index, Type, EnableIfMemberGetFound<Type>> {
+  template <typename T>
+  static auto impl(T&& instance)
+      -> decltype(std::declval<T>().template get<Index>()) {
+    return std::forward<T>(instance).template get<Index>();
+  }
+};
+
+/**
+ * Concepts-ish
+ */
+/**
+ * Check if the range is a tuple or a range
+ */
+template <typename Type, typename T = typename std::decay<Type>::type>
+using EnableIfTuple = void_t<
+    decltype(Get<0, T>::impl(std::declval<T>())),
+    decltype(std::tuple_size<T>::value)>;
+
+/**
+ * Check if the range is a range
+ */
+template <typename Type, typename T = typename std::decay<Type>::type>
+using EnableIfRange = void_t<
+    decltype(adl::adl_begin(std::declval<T>())),
+    decltype(adl::adl_end(std::declval<T>()))>;
+
+/**
+ * Forwards the return value of the first element of the range, used to
+ * determine the type of the first element in the range in SFINAE use cases
+ */
+template <typename Sequence, typename = void>
+struct DeclvalSequence {
+  using type = decltype(*(adl::adl_begin(std::declval<Sequence>())));
+};
+
+template <typename Sequence>
+struct DeclvalSequence<Sequence, EnableIfTuple<Sequence>> {
+  using type = decltype(Get<0, Sequence>::impl(std::declval<Sequence>()));
+};
+
+/**
+ * Check if the functor accepts one or two arguments, one of the first element
+ * in the range, assuming that all the other elements can also be passed to the
+ * functor, and the second being an instantiation of std::integral_constant,
+ * and the third being an instantiation of LoopControl, to provide
+ * breakability to the loop
+ */
+template <typename Sequence, typename Func>
+using EnableIfAcceptsOneArgument = void_t<decltype(std::declval<Func>()(
+    std::declval<typename DeclvalSequence<Sequence>::type>()))>;
+template <typename Sequence, typename Func>
+using EnableIfAcceptsTwoArguments = void_t<decltype(std::declval<Func>()(
+    std::declval<typename DeclvalSequence<Sequence>::type>(),
+    std::integral_constant<std::size_t, 0>{}))>;
+template <typename Sequence, typename Func>
+using EnableIfAcceptsThreeArguments = void_t<decltype(std::declval<Func>()(
+    std::declval<typename DeclvalSequence<Sequence>::type>(),
+    std::integral_constant<std::size_t, 0>{},
+    adl::adl_begin(std::declval<Sequence>())))>;
+template <typename Sequence, typename Func>
+using EnableIfBreaksRange = std::enable_if_t<std::is_same<
+    typename std::decay<decltype(std::declval<Func>()(
+        std::declval<typename DeclvalSequence<Sequence>::type>(),
+        std::size_t{0},
+        adl::adl_begin(std::declval<Sequence>())))>::type,
+    LoopControl>::value>;
+template <typename Sequence, typename Func>
+using EnableIfBreaksTuple = std::enable_if_t<std::is_same<
+    typename std::decay<decltype(std::declval<Func>()(
+        std::declval<typename DeclvalSequence<Sequence>::type>(),
+        std::integral_constant<std::size_t, 0>{}))>::type,
+    LoopControl>::value>;
+/**
+ * Enables if the sequence has random access iterators
+ */
+template <typename Sequence>
+using EnableIfRandomAccessIterators = std::enable_if_t<std::is_same<
+    typename std::iterator_traits<typename std::decay<decltype(
+        adl::adl_begin(std::declval<Sequence>()))>::type>::iterator_category,
+    std::random_access_iterator_tag>::value>;
+template <typename Sequence, typename Index>
+using EnableIfHasIndexingOperator =
+    void_t<decltype(std::declval<Sequence>()[std::declval<Index>()])>;
+
+/**
+ * Implementation for the range iteration, this provides specializations in
+ * the case where the function returns a break or continue.
+ */
+template <typename Seq, typename F, typename = void>
+struct ForEachRange {
+  template <typename Sequence, typename Func>
+  static void impl(Sequence&& range, Func& func) {
+    auto first = adl::adl_begin(range);
+    auto last = adl::adl_end(range);
+    for (auto index = std::size_t{0}; first != last; ++index) {
+      auto next = std::next(first);
+      func(*first, index, first);
+      first = next;
+    }
+  }
+};
+
+template <typename Seq, typename F>
+struct ForEachRange<Seq, F, EnableIfBreaksRange<Seq, F>> {
+  template <typename Sequence, typename Func>
+  static void impl(Sequence&& range, Func& func) {
+    auto first = adl::adl_begin(range);
+    auto last = adl::adl_end(range);
+    for (auto index = std::size_t{0}; first != last; ++index) {
+      auto next = std::next(first);
+      if (loop_break == func(*first, index, first)) {
+        break;
+      }
+      first = next;
+    }
+  }
+};
+
+/**
+ * Implementations for the runtime function
+ */
+template <
+    typename Sequence,
+    typename Func,
+    EnableIfAcceptsThreeArguments<Sequence, Func>* = nullptr>
+void for_each_range_impl(Sequence&& range, Func& func) {
+  ForEachRange<Sequence, Func>::impl(std::forward<Sequence>(range), func);
+}
+template <
+    typename Sequence,
+    typename Func,
+    EnableIfAcceptsTwoArguments<Sequence, Func>* = nullptr>
+void for_each_range_impl(Sequence&& range, Func& func) {
+  // make a three arg adaptor for the function passed in so that the main
+  // implementation function can be used
+  auto three_arg_adaptor = [&func](
+                               auto&& ele, auto index, auto) -> decltype(auto) {
+    return func(std::forward<decltype(ele)>(ele), index);
+  };
+  for_each_range_impl(std::forward<Sequence>(range), three_arg_adaptor);
+}
+
+template <
+    typename Sequence,
+    typename Func,
+    EnableIfAcceptsOneArgument<Sequence, Func>* = nullptr>
+void for_each_range_impl(Sequence&& range, Func& func) {
+  // make a three argument adaptor for the function passed in that just ignores
+  // the second and third argument
+  auto three_arg_adaptor = [&func](auto&& ele, auto, auto) -> decltype(auto) {
+    return func(std::forward<decltype(ele)>(ele));
+  };
+  for_each_range_impl(std::forward<Sequence>(range), three_arg_adaptor);
+}
+
+/**
+ * Handlers for iteration
+ */
+/**
+ * The class provides a way to tell whether the function passed in to the
+ * algorithm returns an instance of LoopControl, if it does then the break-able
+ * implementation will be used.  If the function provided to the algorithm
+ * does not use the break API, then the basic no break, 0 overhead
+ * implementation will be used
+ */
+template <typename Seq, typename F, typename = void>
+struct ForEachTupleImpl {
+  template <typename Sequence, typename Func, std::size_t... Indices>
+  static void
+  impl(Sequence&& seq, Func& func, std::index_sequence<Indices...>) {
+    // unroll the loop in an initializer list construction parameter expansion
+    // pack
+    static_cast<void>(std::initializer_list<int>{
+        (func(
+             Get<Indices, Sequence>::impl(std::forward<Sequence>(seq)),
+             std::integral_constant<std::size_t, Indices>{}),
+         0)...});
+  }
+};
+template <typename Seq, typename F>
+struct ForEachTupleImpl<Seq, F, EnableIfBreaksTuple<Seq, F>> {
+  template <typename Sequence, typename Func, std::size_t... Indices>
+  static void
+  impl(Sequence&& seq, Func& func, std::index_sequence<Indices...>) {
+    // unroll the loop in an initializer list construction parameter expansion
+    // pack
+    LoopControl break_or_not = LoopControl::CONTINUE;
+
+    // cast to void to ignore the result, use the initialzer list constructor
+    // to do the loop execution, the ternary conditional will decide whether
+    // or not to evaluate the result
+    static_cast<void>(std::initializer_list<int>{
+        (((break_or_not == loop_continue)
+              ? (break_or_not = func(
+                     Get<Indices, Sequence>::impl(std::forward<Sequence>(seq)),
+                     std::integral_constant<std::size_t, Indices>{}))
+              : (loop_continue)),
+         0)...});
+  }
+};
+
+/**
+ * The two top level compile time loop iteration functions handle the dispatch
+ * based on the number of arguments the passed in function can be passed, if 2
+ * arguments can be passed then the implementation dispatches work further to
+ * the implementation classes above.  If not then an adaptor is constructed
+ * which is passed on to the 2 argument specialization, which then in turn
+ * forwards implementation to the implementation classes above
+ */
+template <
+    typename Sequence,
+    typename Func,
+    EnableIfAcceptsTwoArguments<Sequence, Func>* = nullptr>
+void for_each_tuple_impl(Sequence&& seq, Func& func) {
+  // pass the length as an index sequence to the implementation as an
+  // optimization over manual template "tail recursion" unrolling
+  constexpr auto length =
+      std::tuple_size<typename std::decay<Sequence>::type>::value;
+  ForEachTupleImpl<Sequence, Func>::impl(
+      std::forward<Sequence>(seq), func, std::make_index_sequence<length>{});
+}
+template <
+    typename Sequence,
+    typename Func,
+    EnableIfAcceptsOneArgument<Sequence, Func>* = nullptr>
+void for_each_tuple_impl(Sequence&& seq, Func& func) {
+  // make an adaptor for the function passed in, in case it can only be passed
+  // on argument
+  auto two_arg_adaptor = [&func](auto&& ele, auto) -> decltype(auto) {
+    return func(std::forward<decltype(ele)>(ele));
+  };
+  for_each_tuple_impl(std::forward<Sequence>(seq), two_arg_adaptor);
+}
+
+/**
+ * Top level handlers for the for_each loop, the basic specialization handles
+ * ranges and the specialized version handles compile time ranges (tuple like)
+ *
+ * This implies that if a range is a compile time range, its compile time
+ * get<> API (whether through a member function or through a ADL looked up
+ * method) will be used in preference over iterators
+ */
+template <typename R, typename = void>
+struct ForEachImpl {
+  template <typename Sequence, typename Func>
+  static void impl(Sequence&& range, Func& func) {
+    for_each_tuple_impl(std::forward<Sequence>(range), func);
+  }
+};
+template <typename R>
+struct ForEachImpl<R, EnableIfRange<R>> {
+  template <typename Sequence, typename Func>
+  static void impl(Sequence&& range, Func& func) {
+    for_each_range_impl(std::forward<Sequence>(range), func);
+  }
+};
+
+template <typename S, typename I, typename = void>
+struct FetchIteratorIndexImpl {
+  template <typename Sequence, typename Index>
+  static decltype(auto) impl(Sequence&& sequence, Index&& index) {
+    return std::forward<Sequence>(sequence)[std::forward<Index>(index)];
+  }
+};
+template <typename S, typename I>
+struct FetchIteratorIndexImpl<S, I, EnableIfRandomAccessIterators<S>> {
+  template <typename Sequence, typename Index>
+  static decltype(auto) impl(Sequence&& sequence, Index index) {
+    return *(adl::adl_begin(std::forward<Sequence>(sequence)) + index);
+  }
+};
+template <typename S, typename = void>
+struct FetchImpl {
+  template <typename Sequence, typename Index>
+  static decltype(auto) impl(Sequence&& sequence, Index index) {
+    return Get<static_cast<std::size_t>(index), Sequence>::impl(
+        std::forward<Sequence>(sequence));
+  }
+};
+template <typename S>
+struct FetchImpl<S, EnableIfRange<S>> {
+  template <typename Sequence, typename Index>
+  static decltype(auto) impl(Sequence&& sequence, Index&& index) {
+    return FetchIteratorIndexImpl<Sequence, Index>::impl(
+        std::forward<Sequence>(sequence), std::forward<Index>(index));
+  }
+};
+
+} // namespace for_each_detail
+
+template <typename Sequence, typename Func>
+constexpr Func for_each(Sequence&& range, Func func) {
+  for_each_detail::ForEachImpl<typename std::decay<Sequence>::type>::impl(
+      std::forward<Sequence>(range), func);
+  return func;
+}
+
+template <typename Sequence, typename Index>
+constexpr decltype(auto) fetch(Sequence&& sequence, Index&& index) {
+  return for_each_detail::FetchImpl<Sequence>::impl(
+      std::forward<Sequence>(sequence), std::forward<Index>(index));
+}
+
+} // namespace folly
index 51372ef..82c07a8 100644 (file)
 
 #pragma once
 
+#include <folly/Preprocessor.h>
+
+#include <type_traits>
+
+namespace folly {
+
 /**
- * This header is deprecated
+ * @function for_each
+ *
+ * folly::for_each is a generalized iteration algorithm.  Example:
+ *
+ *  auto one = std::make_tuple(1, 2, 3);
+ *  auto two = std::vector<int>{1, 2, 3};
+ *  auto func = [](auto element, auto index) {
+ *    cout << index << " : " << element << endl;
+ *  };
+ *  folly::for_each(one, func);
+ *  folly::for_each(two, func);
+ *
+ * The for_each function allows iteration through sequences, these
+ * can either be runtime sequences (i.e. entities for which std::begin and
+ * std::end work) or compile time sequences (as deemed by the presence of
+ * std::tuple_length<>, get<> (ADL resolved) functions)
  *
- * Use range-based for loops, and if necessary Ranges-v3.
+ * The function is made to provide a convenient library based alternative to
+ * the proposal p0589r0, which aims to generalize the range based for loop
+ * even further to work with compile time sequences.
  *
- * Some of the messaging here presumes that you have coded:
+ * A drawback of using range based for loops is that sometimes you do not have
+ * access to the index within the range.  This provides easy access to that,
+ * even with compile time sequences.
  *
- *     #include <range/v3/all.hpp>
- *     using namespace ranges;
+ * And breaking out is easy
+ *
+ *  auto range_one = std::vector<int>{1, 2, 3};
+ *  auto range_two = std::make_tuple(1, 2, 3);
+ *  auto func = [](auto ele, auto index) {
+ *    cout << "Element at index " << index << " : " << ele;
+ *    if (index == 1) {
+ *      return folly::loop_break;
+ *    }
+ *    return folly::loop_continue;
+ *  };
+ *  folly_for_each(range_one, func);
+ *  folly_for_each(range_two, func);
+ *
+ * A simple use case would be when using futures, if the user was doing calls
+ * to n servers then they would accept the callback with the futures like this
+ *
+ *  auto vec = std::vector<std::future<int>>{request_one(), ...};
+ *  when_all(vec.begin(), vec.end()).then([](auto futures) {
+ *    folly::for_each(futures, [](auto& fut) { ... });
+ *  });
+ *
+ * Now when this code switches to use tuples instead of the runtime
+ * std::vector, then the loop does not need to change, the code will still
+ * work just fine
+ *
+ *  when_all(future_one, future_two, future_three).then([](auto futures) {
+ *    folly::for_each(futures, [](auto& fut) { ... });
+ *  });
  */
+template <typename Range, typename Func>
+constexpr Func for_each(Range&& range, Func func);
 
-#include <folly/Preprocessor.h>
-#include <type_traits>
+/**
+ * The user should return loop_break and loop_continue if they want to iterate
+ * in such a way that they can preemptively stop the loop and break out when
+ * certain conditions are met
+ */
+namespace for_each_detail {
+enum class LoopControl : bool { BREAK, CONTINUE };
+} // namespace for_each_detail
+
+constexpr auto loop_break = for_each_detail::LoopControl::BREAK;
+constexpr auto loop_continue = for_each_detail::LoopControl::CONTINUE;
+
+/**
+ * Utility method to help access elements of a sequence with one uniform
+ * interface
+ *
+ * This can be useful for example when you are looping through a sequence and
+ * want to modify another sequence based on the information in the current
+ * sequence
+ *
+ *  auto range_one = std::make_tuple(1, 2, 3);
+ *  auto range_two = std::make_tuple(4, 5, 6);
+ *  folly::for_each(range_one, [&range_two](auto ele, auto index) {
+ *    folly::fetch(range_two, index) = ele;
+ *  });
+ *
+ * For non-tuple like ranges, this works by first trying to use the iterator
+ * class if the iterator has been marked to be a random access iterator.  This
+ * should be inspectable via the std::iterator_traits traits class.  If the
+ * iterator class is not present or is not a random access iterator then the
+ * implementation falls back to trying to use the indexing operator
+ * (operator[]) to fetch the required element
+ */
+template <typename Sequence, typename Index>
+constexpr decltype(auto) fetch(Sequence&& sequence, Index&& index);
+
+} // namespace folly
 
+/**
+ * Everything below this is deprecated.  Use the folly::for_each algorithm above
+ * instead
+ */
 /*
  * Form a local variable name from "FOR_EACH_" x __LINE__, so that
  * FOR_EACH can be nested without creating shadowed declarations.
@@ -223,3 +316,5 @@ downTo(T& iter, const U& begin) {
  */
 #define FOR_EACH_RANGE_R(i, begin, end) \
   for (auto i = (false ? (begin) : (end)); ::folly::detail::downTo(i, (begin));)
+
+#include <folly/Foreach-inl.h>
index ca03d5a..40f9d7f 100644 (file)
@@ -187,6 +187,7 @@ nobase_follyinclude_HEADERS = \
        FixedString.h \
        folly-config.h \
        Foreach.h \
+       Foreach-inl.h \
        FormatArg.h \
        FormatTraits.h \
        Format.h \
index c58d89f..63988c7 100644 (file)
@@ -32,12 +32,236 @@ using namespace folly::detail;
 // 3. Use FOR_EACH_KV loop to iterate through the map.
 
 std::map<int, std::string> bmMap; // For use in benchmarks below.
+std::vector<int> vec_one;
+std::vector<int> vec_two;
 
 void setupBenchmark(size_t iters) {
   bmMap.clear();
   for (size_t i = 0; i < iters; ++i) {
     bmMap[i] = "teststring";
   }
+
+  vec_one.clear();
+  vec_two.clear();
+  vec_one.resize(iters);
+  vec_two.resize(iters);
+}
+
+BENCHMARK(ForEachFunctionNoAssign, iters) {
+  BenchmarkSuspender suspender;
+
+  int sumKeys = 0;
+  std::string sumValues;
+  setupBenchmark(iters);
+
+  suspender.dismissing([&]() {
+    folly::for_each(bmMap, [&](auto& key_val_pair) {
+      sumKeys += key_val_pair.first;
+      sumValues += key_val_pair.second;
+    });
+    doNotOptimizeAway(sumKeys);
+  });
+}
+
+BENCHMARK(StdForEachFunctionNoAssign, iters) {
+  BenchmarkSuspender suspender;
+
+  int sumKeys = 0;
+  std::string sumValues;
+  setupBenchmark(iters);
+
+  suspender.dismissing([&]() {
+    std::for_each(bmMap.begin(), bmMap.end(), [&](auto& key_val_pair) {
+      sumKeys += key_val_pair.first;
+      sumValues += key_val_pair.second;
+    });
+    doNotOptimizeAway(sumKeys);
+  });
+}
+
+BENCHMARK(RangeBasedForLoopNoAssign, iters) {
+  BenchmarkSuspender suspender;
+  int sumKeys = 0;
+  std::string sumValues;
+  setupBenchmark(iters);
+
+  suspender.dismissing([&]() {
+    for (auto& key_val_pair : bmMap) {
+      sumKeys += key_val_pair.first;
+      sumValues += key_val_pair.second;
+    }
+    doNotOptimizeAway(sumKeys);
+  });
+}
+
+BENCHMARK(ManualLoopNoAssign, iters) {
+  BenchmarkSuspender suspender;
+
+  int sumKeys = 0;
+  std::string sumValues;
+  setupBenchmark(iters);
+
+  suspender.dismissing([&]() {
+    for (auto iter = bmMap.begin(); iter != bmMap.end(); ++iter) {
+      sumKeys += iter->first;
+      sumValues += iter->second;
+    }
+    doNotOptimizeAway(sumKeys);
+  });
+}
+
+BENCHMARK(ForEachFunctionAssign, iters) {
+  BenchmarkSuspender suspender;
+
+  int sumKeys = 0;
+  std::string sumValues;
+  setupBenchmark(iters);
+
+  suspender.dismissing([&]() {
+    folly::for_each(bmMap, [&](auto& key_val_pair) {
+      const int k = key_val_pair.first;
+      const std::string v = key_val_pair.second;
+      sumKeys += k;
+      sumValues += v;
+    });
+  });
+}
+
+BENCHMARK(StdForEachFunctionAssign, iters) {
+  BenchmarkSuspender suspender;
+
+  int sumKeys = 0;
+  std::string sumValues;
+  setupBenchmark(iters);
+
+  suspender.dismissing([&]() {
+    std::for_each(bmMap.begin(), bmMap.end(), [&](auto& key_val_pair) {
+      const int k = key_val_pair.first;
+      const std::string v = key_val_pair.second;
+      sumKeys += k;
+      sumValues += v;
+    });
+  });
+}
+
+BENCHMARK(RangeBasedForLoopAssign, iters) {
+  BenchmarkSuspender suspender;
+
+  int sumKeys = 0;
+  std::string sumValues;
+  setupBenchmark(iters);
+
+  suspender.dismissing([&]() {
+    for (auto& key_val_pair : bmMap) {
+      const int k = key_val_pair.first;
+      const std::string v = key_val_pair.second;
+      sumKeys += k;
+      sumValues += v;
+    }
+  });
+}
+
+BENCHMARK(ManualLoopAssign, iters) {
+  BenchmarkSuspender suspender;
+
+  int sumKeys = 0;
+  std::string sumValues;
+  setupBenchmark(iters);
+
+  suspender.dismissing([&]() {
+    for (auto iter = bmMap.begin(); iter != bmMap.end(); ++iter) {
+      const int k = iter->first;
+      const std::string v = iter->second;
+      sumKeys += k;
+      sumValues += v;
+    }
+  });
+}
+
+BENCHMARK(ForEachFunctionNoAssignWithIndexManipulation, iters) {
+  BenchmarkSuspender suspender;
+
+  int sumKeys = 0;
+  std::string sumValues;
+  setupBenchmark(iters);
+
+  suspender.dismissing([&]() {
+    folly::for_each(bmMap, [&](auto& key_val_pair, auto index) {
+      sumKeys += key_val_pair.first;
+      sumValues += key_val_pair.second;
+      sumValues += index;
+    });
+  });
+}
+
+BENCHMARK(StdForEachFunctionNoAssignWithIndexManipulation, iters) {
+  BenchmarkSuspender suspender;
+
+  int sumKeys = 0;
+  std::string sumValues;
+  setupBenchmark(iters);
+
+  suspender.dismissing([&]() {
+    auto index = std::size_t{0};
+    std::for_each(bmMap.begin(), bmMap.end(), [&](auto& key_val_pair) {
+      sumKeys += key_val_pair.first;
+      sumValues += key_val_pair.second;
+      sumValues += index;
+      ++index;
+    });
+  });
+}
+
+BENCHMARK(RangeBasedForLoopNoAssignWithIndexManipulation, iters) {
+  BenchmarkSuspender suspender;
+
+  int sumKeys = 0;
+  std::string sumValues;
+  setupBenchmark(iters);
+
+  suspender.dismissing([&]() {
+    auto index = std::size_t{0};
+    for (auto& key_val_pair : bmMap) {
+      sumKeys += key_val_pair.first;
+      sumValues += key_val_pair.second;
+      sumValues += index;
+    }
+  });
+}
+
+BENCHMARK(ForEachFunctionFetch, iters) {
+  BenchmarkSuspender suspender;
+  setupBenchmark(iters);
+
+  suspender.dismissing([&]() {
+    folly::for_each(bmMap, [&](auto& key_val_pair, auto index) {
+      folly::fetch(vec_one, index) = key_val_pair.first;
+    });
+  });
+}
+
+BENCHMARK(StdForEachFunctionFetch, iters) {
+  BenchmarkSuspender suspender;
+  setupBenchmark(iters);
+
+  suspender.dismissing([&]() {
+    auto index = std::size_t{0};
+    std::for_each(bmMap.begin(), bmMap.end(), [&](auto& key_val_pair) {
+      *(vec_one.begin() + index++) = key_val_pair.first;
+    });
+  });
+}
+
+BENCHMARK(ForLoopFetch, iters) {
+  BenchmarkSuspender suspender;
+  setupBenchmark(iters);
+
+  suspender.dismissing([&]() {
+    auto index = std::size_t{0};
+    for (auto& key_val_pair : bmMap) {
+      *(vec_one.begin() + index++) = key_val_pair.first;
+    }
+  });
 }
 
 BENCHMARK(ForEachKVNoMacroAssign, iters) {
@@ -66,18 +290,6 @@ BENCHMARK(ForEachKVNoMacroNoAssign, iters) {
   }
 }
 
-BENCHMARK(ManualLoopNoAssign, iters) {
-  int sumKeys = 0;
-  std::string sumValues;
-
-  BENCHMARK_SUSPEND { setupBenchmark(iters); }
-
-  for (auto iter = bmMap.begin(); iter != bmMap.end(); ++iter) {
-    sumKeys += iter->first;
-    sumValues += iter->second;
-  }
-}
-
 BENCHMARK(ForEachKVMacro, iters) {
   int sumKeys = 0;
   std::string sumValues;
index 6940cc7..95b02b4 100644 (file)
 
 #include <folly/Foreach.h>
 
+#include <initializer_list>
+#include <iterator>
 #include <list>
 #include <map>
 #include <string>
+#include <tuple>
 #include <vector>
 
 #include <folly/portability/GTest.h>
 using namespace folly;
 using namespace folly::detail;
 
+namespace folly {
+namespace test {
+
+class TestRValueConstruct {
+ public:
+  TestRValueConstruct() = default;
+  TestRValueConstruct(TestRValueConstruct&&) noexcept {
+    this->constructed_from_rvalue = true;
+  }
+  TestRValueConstruct(const TestRValueConstruct&) {
+    this->constructed_from_rvalue = false;
+  }
+  TestRValueConstruct& operator=(const TestRValueConstruct&) = delete;
+  TestRValueConstruct& operator=(TestRValueConstruct&&) = delete;
+
+  bool constructed_from_rvalue{false};
+};
+
+class TestAdlIterable {
+ public:
+  std::vector<int> vec{0, 1, 2, 3};
+};
+
+auto begin(TestAdlIterable& instance) {
+  return instance.vec.begin();
+}
+auto begin(const TestAdlIterable& instance) {
+  return instance.vec.begin();
+}
+auto end(TestAdlIterable& instance) {
+  return instance.vec.end();
+}
+auto end(const TestAdlIterable& instance) {
+  return instance.vec.end();
+}
+
+class TestBothIndexingAndIter {
+ public:
+  class Iterator {
+   public:
+    using difference_type = std::size_t;
+    using value_type = int;
+    using pointer = int*;
+    using reference = int&;
+    using iterator_category = std::random_access_iterator_tag;
+    int& operator*() {
+      return this->val;
+    }
+    Iterator operator+(int) {
+      return *this;
+    }
+    explicit Iterator(int& val_in) : val{val_in} {}
+    int& val;
+  };
+  auto begin() {
+    this->called_begin = true;
+    return Iterator{val};
+  }
+  auto end() {
+    return Iterator{val};
+  }
+  int& operator[](int) {
+    return this->val;
+  }
+
+  int val{0};
+  bool called_begin = false;
+};
+} // namespace test
+} // namespace folly
+
+TEST(Foreach, ForEachFunctionBasic) {
+  auto range = std::make_tuple(1, 2, 3);
+  auto result_range = std::vector<int>{};
+  auto correct_result_range = std::vector<int>{1, 2, 3};
+
+  folly::for_each(range, [&](auto ele) { result_range.push_back(ele); });
+
+  EXPECT_TRUE(std::equal(
+      result_range.begin(), result_range.end(), correct_result_range.begin()));
+}
+
+TEST(Foreach, ForEachFunctionBasicRuntimeOneArg) {
+  auto range = std::vector<int>{1, 2, 3};
+  auto current = 0;
+  folly::for_each(range, [&](auto ele) {
+    if (current == 0) {
+      EXPECT_EQ(ele, 1);
+    } else if (current == 1) {
+      EXPECT_EQ(ele, 2);
+    } else {
+      EXPECT_EQ(ele, 3);
+    }
+    ++current;
+  });
+}
+
+TEST(Foreach, ForEachFunctionBasicRuntimeTwoArg) {
+  auto range = std::vector<int>{1, 2, 3};
+  folly::for_each(range, [](auto ele, auto index) {
+    EXPECT_TRUE(index < 3);
+    if (index == 0) {
+      EXPECT_EQ(ele, 1);
+    } else if (index == 1) {
+      EXPECT_EQ(ele, 2);
+    } else if (index == 2) {
+      EXPECT_EQ(ele, 3);
+    }
+  });
+}
+
+TEST(Foreach, ForEachFunctionBasicRuntimeThreeArg) {
+  auto range = std::list<int>{1, 2, 3};
+  auto result_range = std::list<int>{1, 3};
+  folly::for_each(range, [&](auto ele, auto, auto iter) {
+    if (ele == 2) {
+      range.erase(iter);
+    }
+  });
+  EXPECT_TRUE(std::equal(range.begin(), range.end(), result_range.begin()));
+}
+
+TEST(Foreach, ForEachFunctionBasicTupleOneArg) {
+  auto range = std::make_tuple(1, 2, 3);
+  auto current = 0;
+  folly::for_each(range, [&](auto ele) {
+    if (current == 0) {
+      EXPECT_EQ(ele, 1);
+    } else if (current == 1) {
+      EXPECT_EQ(ele, 2);
+    } else {
+      EXPECT_EQ(ele, 3);
+    }
+    ++current;
+  });
+}
+
+TEST(Foreach, ForEachFunctionBasicTupleTwoArg) {
+  auto range = std::make_tuple(1, 2, 3);
+  folly::for_each(range, [](auto ele, auto index) {
+    EXPECT_TRUE(index < 3);
+    if (index == 0) {
+      EXPECT_EQ(ele, 1);
+    } else if (index == 1) {
+      EXPECT_EQ(ele, 2);
+    } else if (index == 2) {
+      EXPECT_EQ(ele, 3);
+    }
+  });
+}
+
+TEST(Foreach, ForEachFunctionBreakRuntimeOneArg) {
+  auto range = std::vector<int>{1, 2, 3};
+  auto iterations = 0;
+  folly::for_each(range, [&](auto) {
+    ++iterations;
+    if (iterations == 1) {
+      return folly::loop_break;
+    }
+    return folly::loop_continue;
+  });
+  EXPECT_EQ(iterations, 1);
+}
+
+TEST(Foreach, ForEachFunctionBreakRuntimeTwoArg) {
+  auto range = std::vector<int>{1, 2, 3};
+  auto iterations = 0;
+  folly::for_each(range, [&](auto, auto index) {
+    ++iterations;
+    if (index == 1) {
+      return folly::loop_break;
+    }
+    return folly::loop_continue;
+  });
+  EXPECT_EQ(iterations, 2);
+}
+
+TEST(Foreach, ForEachFunctionBreakRuntimeThreeArg) {
+  auto range = std::vector<int>{1, 2, 3};
+  auto iterations = 0;
+  folly::for_each(range, [&](auto, auto index, auto) {
+    ++iterations;
+    if (index == 1) {
+      return folly::loop_break;
+    }
+    return folly::loop_continue;
+  });
+  EXPECT_EQ(iterations, 2);
+}
+
+TEST(Foreach, ForEachFunctionBreakTupleOneArg) {
+  auto range = std::vector<int>{1, 2, 3};
+  auto iterations = 0;
+  folly::for_each(range, [&](auto) {
+    ++iterations;
+    if (iterations == 1) {
+      return folly::loop_break;
+    }
+    return folly::loop_continue;
+  });
+  EXPECT_EQ(iterations, 1);
+}
+
+TEST(Foreach, ForEachFunctionBreakTupleTwoArg) {
+  auto range = std::vector<int>{1, 2, 3};
+  auto iterations = 0;
+  folly::for_each(range, [&](auto, auto index) {
+    ++iterations;
+    if (index == 1) {
+      return folly::loop_break;
+    }
+    return folly::loop_continue;
+  });
+  EXPECT_EQ(iterations, 2);
+}
+
+TEST(Foreach, ForEachFunctionArray) {
+  auto range = std::array<int, 3>{{1, 2, 3}};
+  auto iterations = 0;
+  folly::for_each(range, [&](auto, auto index) {
+    ++iterations;
+    if (index == 1) {
+      return folly::loop_break;
+    }
+    return folly::loop_continue;
+  });
+  EXPECT_EQ(iterations, 2);
+}
+
+TEST(Foreach, ForEachFunctionInitializerListBasic) {
+  folly::for_each(std::initializer_list<int>{1, 2, 3}, [](auto ele) { ++ele; });
+}
+
+TEST(Foreach, ForEachFunctionTestForward) {
+  using folly::test::TestRValueConstruct;
+  auto range_one = std::vector<TestRValueConstruct>{};
+  range_one.resize(3);
+
+  folly::for_each(std::move(range_one), [](auto ele) {
+    EXPECT_FALSE(ele.constructed_from_rvalue);
+  });
+
+  folly::for_each(
+      std::make_tuple(TestRValueConstruct{}, TestRValueConstruct{}),
+      [](auto ele) { EXPECT_TRUE(ele.constructed_from_rvalue); });
+}
+
+TEST(Foreach, ForEachFunctionAdlIterable) {
+  auto range = test::TestAdlIterable{};
+  auto iterations = 0;
+  folly::for_each(range, [&](auto ele, auto index) {
+    ++iterations;
+    EXPECT_EQ(ele, index);
+  });
+  EXPECT_EQ(iterations, 4);
+}
+
+TEST(ForEach, FetchRandomAccessIterator) {
+  auto vec = std::vector<int>{1, 2, 3};
+  auto& second = folly::fetch(vec, 1);
+  EXPECT_EQ(second, 2);
+  second = 3;
+  EXPECT_EQ(second, 3);
+}
+
+TEST(ForEach, FetchIndexing) {
+  auto mp = std::map<int, int>{{1, 2}};
+  auto& ele = folly::fetch(mp, 1);
+  EXPECT_EQ(ele, 2);
+  ele = 3;
+  EXPECT_EQ(ele, 3);
+}
+
+TEST(ForEach, FetchTuple) {
+  auto mp = std::make_tuple(1, 2, 3);
+  auto& ele = folly::fetch(mp, std::integral_constant<int, 1>{});
+  EXPECT_EQ(ele, 2);
+  ele = 3;
+  EXPECT_EQ(ele, 3);
+}
+
+TEST(ForEach, FetchTestPreferIterator) {
+  auto range = test::TestBothIndexingAndIter{};
+  auto& ele = folly::fetch(range, 0);
+  EXPECT_TRUE(range.called_begin);
+  EXPECT_EQ(ele, 0);
+  ele = 2;
+  EXPECT_EQ(folly::fetch(range, 0), 2);
+}
+
 TEST(Foreach, ForEachRvalue) {
   const char* const hello = "hello";
   int n = 0;