LCOV - code coverage report
Current view: top level - include/llvm/ADT - STLExtras.h (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 118 120 98.3 %
Date: 2018-02-21 06:32:55 Functions: 1806 2305 78.4 %
Legend: Lines: hit not hit

          Line data    Source code
       1             : //===- llvm/ADT/STLExtras.h - Useful STL related functions ------*- C++ -*-===//
       2             : //
       3             : //                     The LLVM Compiler Infrastructure
       4             : //
       5             : // This file is distributed under the University of Illinois Open Source
       6             : // License. See LICENSE.TXT for details.
       7             : //
       8             : //===----------------------------------------------------------------------===//
       9             : //
      10             : // This file contains some templates that are useful if you are working with the
      11             : // STL at all.
      12             : //
      13             : // No library is required when using these functions.
      14             : //
      15             : //===----------------------------------------------------------------------===//
      16             : 
      17             : #ifndef LLVM_ADT_STLEXTRAS_H
      18             : #define LLVM_ADT_STLEXTRAS_H
      19             : 
      20             : #include "llvm/ADT/Optional.h"
      21             : #include "llvm/ADT/SmallVector.h"
      22             : #include "llvm/ADT/iterator.h"
      23             : #include "llvm/ADT/iterator_range.h"
      24             : #include "llvm/Support/ErrorHandling.h"
      25             : #include <algorithm>
      26             : #include <cassert>
      27             : #include <cstddef>
      28             : #include <cstdint>
      29             : #include <cstdlib>
      30             : #include <functional>
      31             : #include <initializer_list>
      32             : #include <iterator>
      33             : #include <limits>
      34             : #include <memory>
      35             : #include <tuple>
      36             : #include <type_traits>
      37             : #include <utility>
      38             : 
      39             : namespace llvm {
      40             : 
      41             : // Only used by compiler if both template types are the same.  Useful when
      42             : // using SFINAE to test for the existence of member functions.
      43             : template <typename T, T> struct SameType;
      44             : 
      45             : namespace detail {
      46             : 
      47             : template <typename RangeT>
      48             : using IterOfRange = decltype(std::begin(std::declval<RangeT &>()));
      49             : 
      50             : template <typename RangeT>
      51             : using ValueOfRange = typename std::remove_reference<decltype(
      52             :     *std::begin(std::declval<RangeT &>()))>::type;
      53             : 
      54             : } // end namespace detail
      55             : 
      56             : //===----------------------------------------------------------------------===//
      57             : //     Extra additions to <functional>
      58             : //===----------------------------------------------------------------------===//
      59             : 
      60             : template <class Ty> struct identity {
      61             :   using argument_type = Ty;
      62             : 
      63             :   Ty &operator()(Ty &self) const {
      64             :     return self;
      65             :   }
      66             :   const Ty &operator()(const Ty &self) const {
      67             :     return self;
      68             :   }
      69             : };
      70             : 
      71             : template <class Ty> struct less_ptr {
      72             :   bool operator()(const Ty* left, const Ty* right) const {
      73   255708900 :     return *left < *right;
      74             :   }
      75             : };
      76             : 
      77             : template <class Ty> struct greater_ptr {
      78             :   bool operator()(const Ty* left, const Ty* right) const {
      79             :     return *right < *left;
      80             :   }
      81             : };
      82             : 
      83             : /// An efficient, type-erasing, non-owning reference to a callable. This is
      84             : /// intended for use as the type of a function parameter that is not used
      85             : /// after the function in question returns.
      86             : ///
      87             : /// This class does not own the callable, so it is not in general safe to store
      88             : /// a function_ref.
      89             : template<typename Fn> class function_ref;
      90             : 
      91             : template<typename Ret, typename ...Params>
      92             : class function_ref<Ret(Params...)> {
      93             :   Ret (*callback)(intptr_t callable, Params ...params) = nullptr;
      94             :   intptr_t callable;
      95             : 
      96             :   template<typename Callable>
      97    18322027 :   static Ret callback_fn(intptr_t callable, Params ...params) {
      98    12923503 :     return (*reinterpret_cast<Callable*>(callable))(
      99    18322752 :         std::forward<Params>(params)...);
     100             :   }
     101             : 
     102             : public:
     103       29702 :   function_ref() = default;
     104           1 :   function_ref(std::nullptr_t) {}
     105             : 
     106             :   template <typename Callable>
     107    40142248 :   function_ref(Callable &&callable,
     108             :                typename std::enable_if<
     109             :                    !std::is_same<typename std::remove_reference<Callable>::type,
     110             :                                  function_ref>::value>::type * = nullptr)
     111             :       : callback(callback_fn<typename std::remove_reference<Callable>::type>),
     112    43878985 :         callable(reinterpret_cast<intptr_t>(&callable)) {}
     113             : 
     114         151 :   Ret operator()(Params ...params) const {
     115    18322127 :     return callback(callable, std::forward<Params>(params)...);
     116             :   }
     117             : 
     118             :   operator bool() const { return callback; }
     119             : };
     120             : 
     121             : // deleter - Very very very simple method that is used to invoke operator
     122             : // delete on something.  It is used like this:
     123             : //
     124             : //   for_each(V.begin(), B.end(), deleter<Interval>);
     125             : template <class T>
     126             : inline void deleter(T *Ptr) {
     127             :   delete Ptr;
     128             : }
     129             : 
     130             : //===----------------------------------------------------------------------===//
     131             : //     Extra additions to <iterator>
     132             : //===----------------------------------------------------------------------===//
     133             : 
     134             : namespace adl_detail {
     135             : 
     136             : using std::begin;
     137             : 
     138             : template <typename ContainerTy>
     139             : auto adl_begin(ContainerTy &&container)
     140             :     -> decltype(begin(std::forward<ContainerTy>(container))) {
     141             :   return begin(std::forward<ContainerTy>(container));
     142             : }
     143             : 
     144             : using std::end;
     145             : 
     146             : template <typename ContainerTy>
     147             : auto adl_end(ContainerTy &&container)
     148             :     -> decltype(end(std::forward<ContainerTy>(container))) {
     149             :   return end(std::forward<ContainerTy>(container));
     150             : }
     151             : 
     152             : using std::swap;
     153             : 
     154             : template <typename T>
     155             : void adl_swap(T &&lhs, T &&rhs) noexcept(noexcept(swap(std::declval<T>(),
     156             :                                                        std::declval<T>()))) {
     157             :   swap(std::forward<T>(lhs), std::forward<T>(rhs));
     158             : }
     159             : 
     160             : } // end namespace adl_detail
     161             : 
     162             : template <typename ContainerTy>
     163             : auto adl_begin(ContainerTy &&container)
     164             :     -> decltype(adl_detail::adl_begin(std::forward<ContainerTy>(container))) {
     165             :   return adl_detail::adl_begin(std::forward<ContainerTy>(container));
     166             : }
     167             : 
     168             : template <typename ContainerTy>
     169             : auto adl_end(ContainerTy &&container)
     170             :     -> decltype(adl_detail::adl_end(std::forward<ContainerTy>(container))) {
     171             :   return adl_detail::adl_end(std::forward<ContainerTy>(container));
     172             : }
     173             : 
     174             : template <typename T>
     175             : void adl_swap(T &&lhs, T &&rhs) noexcept(
     176             :     noexcept(adl_detail::adl_swap(std::declval<T>(), std::declval<T>()))) {
     177             :   adl_detail::adl_swap(std::forward<T>(lhs), std::forward<T>(rhs));
     178             : }
     179             : 
     180             : // mapped_iterator - This is a simple iterator adapter that causes a function to
     181             : // be applied whenever operator* is invoked on the iterator.
     182             : 
     183             : template <typename ItTy, typename FuncTy,
     184             :           typename FuncReturnTy =
     185             :             decltype(std::declval<FuncTy>()(*std::declval<ItTy>()))>
     186        3288 : class mapped_iterator
     187             :     : public iterator_adaptor_base<
     188             :              mapped_iterator<ItTy, FuncTy>, ItTy,
     189             :              typename std::iterator_traits<ItTy>::iterator_category,
     190             :              typename std::remove_reference<FuncReturnTy>::type> {
     191             : public:
     192             :   mapped_iterator(ItTy U, FuncTy F)
     193         460 :     : mapped_iterator::iterator_adaptor_base(std::move(U)), F(std::move(F)) {}
     194             : 
     195             :   ItTy getCurrent() { return this->I; }
     196             : 
     197     6082320 :   FuncReturnTy operator*() { return F(*this->I); }
     198             : 
     199             : private:
     200             :   FuncTy F;
     201             : };
     202             : 
     203             : // map_iterator - Provide a convenient way to create mapped_iterators, just like
     204             : // make_pair is useful for creating pairs...
     205             : template <class ItTy, class FuncTy>
     206         460 : inline mapped_iterator<ItTy, FuncTy> map_iterator(ItTy I, FuncTy F) {
     207         460 :   return mapped_iterator<ItTy, FuncTy>(std::move(I), std::move(F));
     208             : }
     209             : 
     210             : /// Helper to determine if type T has a member called rbegin().
     211             : template <typename Ty> class has_rbegin_impl {
     212             :   using yes = char[1];
     213             :   using no = char[2];
     214             : 
     215             :   template <typename Inner>
     216             :   static yes& test(Inner *I, decltype(I->rbegin()) * = nullptr);
     217             : 
     218             :   template <typename>
     219             :   static no& test(...);
     220             : 
     221             : public:
     222             :   static const bool value = sizeof(test<Ty>(nullptr)) == sizeof(yes);
     223             : };
     224             : 
     225             : /// Metafunction to determine if T& or T has a member called rbegin().
     226             : template <typename Ty>
     227             : struct has_rbegin : has_rbegin_impl<typename std::remove_reference<Ty>::type> {
     228             : };
     229             : 
     230             : // Returns an iterator_range over the given container which iterates in reverse.
     231             : // Note that the container must have rbegin()/rend() methods for this to work.
     232             : template <typename ContainerTy>
     233        2005 : auto reverse(ContainerTy &&C,
     234             :              typename std::enable_if<has_rbegin<ContainerTy>::value>::type * =
     235             :                  nullptr) -> decltype(make_range(C.rbegin(), C.rend())) {
     236     9546017 :   return make_range(C.rbegin(), C.rend());
     237             : }
     238             : 
     239             : // Returns a std::reverse_iterator wrapped around the given iterator.
     240             : template <typename IteratorTy>
     241             : std::reverse_iterator<IteratorTy> make_reverse_iterator(IteratorTy It) {
     242             :   return std::reverse_iterator<IteratorTy>(It);
     243             : }
     244             : 
     245             : // Returns an iterator_range over the given container which iterates in reverse.
     246             : // Note that the container must have begin()/end() methods which return
     247             : // bidirectional iterators for this to work.
     248             : template <typename ContainerTy>
     249             : auto reverse(
     250             :     ContainerTy &&C,
     251             :     typename std::enable_if<!has_rbegin<ContainerTy>::value>::type * = nullptr)
     252             :     -> decltype(make_range(llvm::make_reverse_iterator(std::end(C)),
     253             :                            llvm::make_reverse_iterator(std::begin(C)))) {
     254             :   return make_range(llvm::make_reverse_iterator(std::end(C)),
     255             :                     llvm::make_reverse_iterator(std::begin(C)));
     256             : }
     257             : 
     258             : /// An iterator adaptor that filters the elements of given inner iterators.
     259             : ///
     260             : /// The predicate parameter should be a callable object that accepts the wrapped
     261             : /// iterator's reference type and returns a bool. When incrementing or
     262             : /// decrementing the iterator, it will call the predicate on each element and
     263             : /// skip any where it returns false.
     264             : ///
     265             : /// \code
     266             : ///   int A[] = { 1, 2, 3, 4 };
     267             : ///   auto R = make_filter_range(A, [](int N) { return N % 2 == 1; });
     268             : ///   // R contains { 1, 3 }.
     269             : /// \endcode
     270             : template <typename WrappedIteratorT, typename PredicateT>
     271      316099 : class filter_iterator
     272             :     : public iterator_adaptor_base<
     273             :           filter_iterator<WrappedIteratorT, PredicateT>, WrappedIteratorT,
     274             :           typename std::common_type<
     275             :               std::forward_iterator_tag,
     276             :               typename std::iterator_traits<
     277             :                   WrappedIteratorT>::iterator_category>::type> {
     278             :   using BaseT = iterator_adaptor_base<
     279             :       filter_iterator<WrappedIteratorT, PredicateT>, WrappedIteratorT,
     280             :       typename std::common_type<
     281             :           std::forward_iterator_tag,
     282             :           typename std::iterator_traits<WrappedIteratorT>::iterator_category>::
     283             :           type>;
     284             : 
     285           4 :   struct PayloadType {
     286             :     WrappedIteratorT End;
     287             :     PredicateT Pred;
     288             :   };
     289             : 
     290             :   Optional<PayloadType> Payload;
     291             : 
     292       64533 :   void findNextValid() {
     293             :     assert(Payload && "Payload should be engaged when findNextValid is called");
     294       86746 :     while (this->I != Payload->End && !Payload->Pred(*this->I))
     295             :       BaseT::operator++();
     296       64533 :   }
     297             : 
     298             :   // Construct the begin iterator. The begin iterator requires to know where end
     299             :   // is, so that it can properly stop when it hits end.
     300             :   filter_iterator(WrappedIteratorT Begin, WrappedIteratorT End, PredicateT Pred)
     301             :       : BaseT(std::move(Begin)),
     302             :         Payload(PayloadType{std::move(End), std::move(Pred)}) {
     303       47441 :     findNextValid();
     304             :   }
     305             : 
     306             :   // Construct the end iterator. It's not incrementable, so Payload doesn't
     307             :   // have to be engaged.
     308             :   filter_iterator(WrappedIteratorT End) : BaseT(End) {}
     309             : 
     310             : public:
     311             :   using BaseT::operator++;
     312             : 
     313           9 :   filter_iterator &operator++() {
     314             :     BaseT::operator++();
     315       17092 :     findNextValid();
     316           9 :     return *this;
     317             :   }
     318             : 
     319             :   template <typename RT, typename PT>
     320             :   friend iterator_range<filter_iterator<detail::IterOfRange<RT>, PT>>
     321             :   make_filter_range(RT &&, PT);
     322             : };
     323             : 
     324             : /// Convenience function that takes a range of elements and a predicate,
     325             : /// and return a new filter_iterator range.
     326             : ///
     327             : /// FIXME: Currently if RangeT && is a rvalue reference to a temporary, the
     328             : /// lifetime of that temporary is not kept by the returned range object, and the
     329             : /// temporary is going to be dropped on the floor after the make_iterator_range
     330             : /// full expression that contains this function call.
     331             : template <typename RangeT, typename PredicateT>
     332             : iterator_range<filter_iterator<detail::IterOfRange<RangeT>, PredicateT>>
     333       47937 : make_filter_range(RangeT &&Range, PredicateT Pred) {
     334             :   using FilterIteratorT =
     335             :       filter_iterator<detail::IterOfRange<RangeT>, PredicateT>;
     336             :   return make_range(FilterIteratorT(std::begin(std::forward<RangeT>(Range)),
     337             :                                     std::end(std::forward<RangeT>(Range)),
     338             :                                     std::move(Pred)),
     339       47937 :                     FilterIteratorT(std::end(std::forward<RangeT>(Range))));
     340             : }
     341             : 
     342             : // forward declarations required by zip_shortest/zip_first
     343             : template <typename R, typename UnaryPredicate>
     344             : bool all_of(R &&range, UnaryPredicate P);
     345             : 
     346             : template <size_t... I> struct index_sequence;
     347             : 
     348             : template <class... Ts> struct index_sequence_for;
     349             : 
     350             : namespace detail {
     351             : 
     352             : using std::declval;
     353             : 
     354             : // We have to alias this since inlining the actual type at the usage site
     355             : // in the parameter list of iterator_facade_base<> below ICEs MSVC 2017.
     356             : template<typename... Iters> struct ZipTupleType {
     357             :   using type = std::tuple<decltype(*declval<Iters>())...>;
     358             : };
     359             : 
     360             : template <typename ZipType, typename... Iters>
     361             : using zip_traits = iterator_facade_base<
     362             :     ZipType, typename std::common_type<std::bidirectional_iterator_tag,
     363             :                                        typename std::iterator_traits<
     364             :                                            Iters>::iterator_category...>::type,
     365             :     // ^ TODO: Implement random access methods.
     366             :     typename ZipTupleType<Iters...>::type,
     367             :     typename std::iterator_traits<typename std::tuple_element<
     368             :         0, std::tuple<Iters...>>::type>::difference_type,
     369             :     // ^ FIXME: This follows boost::make_zip_iterator's assumption that all
     370             :     // inner iterators have the same difference_type. It would fail if, for
     371             :     // instance, the second field's difference_type were non-numeric while the
     372             :     // first is.
     373             :     typename ZipTupleType<Iters...>::type *,
     374             :     typename ZipTupleType<Iters...>::type>;
     375             : 
     376             : template <typename ZipType, typename... Iters>
     377             : struct zip_common : public zip_traits<ZipType, Iters...> {
     378             :   using Base = zip_traits<ZipType, Iters...>;
     379             :   using value_type = typename Base::value_type;
     380             : 
     381             :   std::tuple<Iters...> iterators;
     382             : 
     383             : protected:
     384             :   template <size_t... Ns> value_type deref(index_sequence<Ns...>) const {
     385          47 :     return value_type(*std::get<Ns>(iterators)...);
     386             :   }
     387             : 
     388             :   template <size_t... Ns>
     389             :   decltype(iterators) tup_inc(index_sequence<Ns...>) const {
     390             :     return std::tuple<Iters...>(std::next(std::get<Ns>(iterators))...);
     391             :   }
     392             : 
     393             :   template <size_t... Ns>
     394             :   decltype(iterators) tup_dec(index_sequence<Ns...>) const {
     395             :     return std::tuple<Iters...>(std::prev(std::get<Ns>(iterators))...);
     396             :   }
     397             : 
     398             : public:
     399             :   zip_common(Iters &&... ts) : iterators(std::forward<Iters>(ts)...) {}
     400             : 
     401             :   value_type operator*() { return deref(index_sequence_for<Iters...>{}); }
     402             : 
     403             :   const value_type operator*() const {
     404             :     return deref(index_sequence_for<Iters...>{});
     405             :   }
     406             : 
     407             :   ZipType &operator++() {
     408             :     iterators = tup_inc(index_sequence_for<Iters...>{});
     409             :     return *reinterpret_cast<ZipType *>(this);
     410             :   }
     411             : 
     412             :   ZipType &operator--() {
     413             :     static_assert(Base::IsBidirectional,
     414             :                   "All inner iterators must be at least bidirectional.");
     415             :     iterators = tup_dec(index_sequence_for<Iters...>{});
     416             :     return *reinterpret_cast<ZipType *>(this);
     417             :   }
     418             : };
     419             : 
     420             : template <typename... Iters>
     421             : struct zip_first : public zip_common<zip_first<Iters...>, Iters...> {
     422             :   using Base = zip_common<zip_first<Iters...>, Iters...>;
     423             : 
     424             :   bool operator==(const zip_first<Iters...> &other) const {
     425             :     return std::get<0>(this->iterators) == std::get<0>(other.iterators);
     426             :   }
     427             : 
     428             :   zip_first(Iters &&... ts) : Base(std::forward<Iters>(ts)...) {}
     429             : };
     430             : 
     431             : template <typename... Iters>
     432             : class zip_shortest : public zip_common<zip_shortest<Iters...>, Iters...> {
     433             :   template <size_t... Ns>
     434      913096 :   bool test(const zip_shortest<Iters...> &other, index_sequence<Ns...>) const {
     435     2739256 :     return all_of(std::initializer_list<bool>{std::get<Ns>(this->iterators) !=
     436             :                                               std::get<Ns>(other.iterators)...},
     437      913096 :                   identity<bool>{});
     438             :   }
     439             : 
     440             : public:
     441             :   using Base = zip_common<zip_shortest<Iters...>, Iters...>;
     442             : 
     443             :   zip_shortest(Iters &&... ts) : Base(std::forward<Iters>(ts)...) {}
     444             : 
     445             :   bool operator==(const zip_shortest<Iters...> &other) const {
     446      913096 :     return !test(other, index_sequence_for<Iters...>{});
     447             :   }
     448             : };
     449             : 
     450           6 : template <template <typename...> class ItType, typename... Args> class zippy {
     451             : public:
     452             :   using iterator = ItType<decltype(std::begin(std::declval<Args>()))...>;
     453             :   using iterator_category = typename iterator::iterator_category;
     454             :   using value_type = typename iterator::value_type;
     455             :   using difference_type = typename iterator::difference_type;
     456             :   using pointer = typename iterator::pointer;
     457             :   using reference = typename iterator::reference;
     458             : 
     459             : private:
     460             :   std::tuple<Args...> ts;
     461             : 
     462             :   template <size_t... Ns> iterator begin_impl(index_sequence<Ns...>) const {
     463             :     return iterator(std::begin(std::get<Ns>(ts))...);
     464             :   }
     465             :   template <size_t... Ns> iterator end_impl(index_sequence<Ns...>) const {
     466             :     return iterator(std::end(std::get<Ns>(ts))...);
     467             :   }
     468             : 
     469             : public:
     470             :   zippy(Args &&... ts_) : ts(std::forward<Args>(ts_)...) {}
     471             : 
     472             :   iterator begin() const { return begin_impl(index_sequence_for<Args...>{}); }
     473             :   iterator end() const { return end_impl(index_sequence_for<Args...>{}); }
     474             : };
     475             : 
     476             : } // end namespace detail
     477             : 
     478             : /// zip iterator for two or more iteratable types.
     479             : template <typename T, typename U, typename... Args>
     480             : detail::zippy<detail::zip_shortest, T, U, Args...> zip(T &&t, U &&u,
     481             :                                                        Args &&... args) {
     482             :   return detail::zippy<detail::zip_shortest, T, U, Args...>(
     483             :       std::forward<T>(t), std::forward<U>(u), std::forward<Args>(args)...);
     484             : }
     485             : 
     486             : /// zip iterator that, for the sake of efficiency, assumes the first iteratee to
     487             : /// be the shortest.
     488             : template <typename T, typename U, typename... Args>
     489             : detail::zippy<detail::zip_first, T, U, Args...> zip_first(T &&t, U &&u,
     490             :                                                           Args &&... args) {
     491             :   return detail::zippy<detail::zip_first, T, U, Args...>(
     492             :       std::forward<T>(t), std::forward<U>(u), std::forward<Args>(args)...);
     493             : }
     494             : 
     495             : /// Iterator wrapper that concatenates sequences together.
     496             : ///
     497             : /// This can concatenate different iterators, even with different types, into
     498             : /// a single iterator provided the value types of all the concatenated
     499             : /// iterators expose `reference` and `pointer` types that can be converted to
     500             : /// `ValueT &` and `ValueT *` respectively. It doesn't support more
     501             : /// interesting/customized pointer or reference types.
     502             : ///
     503             : /// Currently this only supports forward or higher iterator categories as
     504             : /// inputs and always exposes a forward iterator interface.
     505             : template <typename ValueT, typename... IterTs>
     506             : class concat_iterator
     507             :     : public iterator_facade_base<concat_iterator<ValueT, IterTs...>,
     508             :                                   std::forward_iterator_tag, ValueT> {
     509             :   using BaseT = typename concat_iterator::iterator_facade_base;
     510             : 
     511             :   /// We store both the current and end iterators for each concatenated
     512             :   /// sequence in a tuple of pairs.
     513             :   ///
     514             :   /// Note that something like iterator_range seems nice at first here, but the
     515             :   /// range properties are of little benefit and end up getting in the way
     516             :   /// because we need to do mutation on the current iterators.
     517             :   std::tuple<std::pair<IterTs, IterTs>...> IterPairs;
     518             : 
     519             :   /// Attempts to increment a specific iterator.
     520             :   ///
     521             :   /// Returns true if it was able to increment the iterator. Returns false if
     522             :   /// the iterator is already at the end iterator.
     523     1960786 :   template <size_t Index> bool incrementHelper() {
     524             :     auto &IterPair = std::get<Index>(IterPairs);
     525     1960786 :     if (IterPair.first == IterPair.second)
     526             :       return false;
     527             : 
     528         260 :     ++IterPair.first;
     529     1659067 :     return true;
     530             :   }
     531             : 
     532             :   /// Increments the first non-end iterator.
     533             :   ///
     534             :   /// It is an error to call this with all iterators at the end.
     535     1659066 :   template <size_t... Ns> void increment(index_sequence<Ns...>) {
     536             :     // Build a sequence of functions to increment each iterator if possible.
     537     1659066 :     bool (concat_iterator::*IncrementHelperFns[])() = {
     538             :         &concat_iterator::incrementHelper<Ns>...};
     539             : 
     540             :     // Loop over them, and stop as soon as we succeed at incrementing one.
     541     2262506 :     for (auto &IncrementHelperFn : IncrementHelperFns)
     542     1960786 :       if ((this->*IncrementHelperFn)())
     543     1659067 :         return;
     544             : 
     545           0 :     llvm_unreachable("Attempted to increment an end concat iterator!");
     546             :   }
     547             : 
     548             :   /// Returns null if the specified iterator is at the end. Otherwise,
     549             :   /// dereferences the iterator and returns the address of the resulting
     550             :   /// reference.
     551     1960914 :   template <size_t Index> ValueT *getHelper() const {
     552             :     auto &IterPair = std::get<Index>(IterPairs);
     553     1960914 :     if (IterPair.first == IterPair.second)
     554             :       return nullptr;
     555             : 
     556         272 :     return &*IterPair.first;
     557             :   }
     558             : 
     559             :   /// Finds the first non-end iterator, dereferences, and returns the resulting
     560             :   /// reference.
     561             :   ///
     562             :   /// It is an error to call this with all iterators at the end.
     563     1659178 :   template <size_t... Ns> ValueT &get(index_sequence<Ns...>) const {
     564             :     // Build a sequence of functions to get from iterator if possible.
     565     1659178 :     ValueT *(concat_iterator::*GetHelperFns[])() const = {
     566             :         &concat_iterator::getHelper<Ns>...};
     567             : 
     568             :     // Loop over them, and return the first result we find.
     569     2262652 :     for (auto &GetHelperFn : GetHelperFns)
     570     1960915 :       if (ValueT *P = (this->*GetHelperFn)())
     571     1659178 :         return *P;
     572             : 
     573           0 :     llvm_unreachable("Attempted to get a pointer from an end concat iterator!");
     574             :   }
     575             : 
     576             : public:
     577             :   /// Constructs an iterator from a squence of ranges.
     578             :   ///
     579             :   /// We need the full range to know how to switch between each of the
     580             :   /// iterators.
     581             :   template <typename... RangeTs>
     582             :   explicit concat_iterator(RangeTs &&... Ranges)
     583             :       : IterPairs({std::begin(Ranges), std::end(Ranges)}...) {}
     584             : 
     585             :   using BaseT::operator++;
     586             : 
     587             :   concat_iterator &operator++() {
     588     1659067 :     increment(index_sequence_for<IterTs...>());
     589             :     return *this;
     590             :   }
     591             : 
     592     1659178 :   ValueT &operator*() const { return get(index_sequence_for<IterTs...>()); }
     593             : 
     594             :   bool operator==(const concat_iterator &RHS) const {
     595             :     return IterPairs == RHS.IterPairs;
     596             :   }
     597             : };
     598             : 
     599             : namespace detail {
     600             : 
     601             : /// Helper to store a sequence of ranges being concatenated and access them.
     602             : ///
     603             : /// This is designed to facilitate providing actual storage when temporaries
     604             : /// are passed into the constructor such that we can use it as part of range
     605             : /// based for loops.
     606           1 : template <typename ValueT, typename... RangeTs> class concat_range {
     607             : public:
     608             :   using iterator =
     609             :       concat_iterator<ValueT,
     610             :                       decltype(std::begin(std::declval<RangeTs &>()))...>;
     611             : 
     612             : private:
     613             :   std::tuple<RangeTs...> Ranges;
     614             : 
     615             :   template <size_t... Ns> iterator begin_impl(index_sequence<Ns...>) {
     616             :     return iterator(std::get<Ns>(Ranges)...);
     617             :   }
     618             :   template <size_t... Ns> iterator end_impl(index_sequence<Ns...>) {
     619             :     return iterator(make_range(std::end(std::get<Ns>(Ranges)),
     620             :                                std::end(std::get<Ns>(Ranges)))...);
     621             :   }
     622             : 
     623             : public:
     624             :   concat_range(RangeTs &&... Ranges)
     625             :       : Ranges(std::forward<RangeTs>(Ranges)...) {}
     626             : 
     627             :   iterator begin() { return begin_impl(index_sequence_for<RangeTs...>{}); }
     628             :   iterator end() { return end_impl(index_sequence_for<RangeTs...>{}); }
     629             : };
     630             : 
     631             : } // end namespace detail
     632             : 
     633             : /// Concatenated range across two or more ranges.
     634             : ///
     635             : /// The desired value type must be explicitly specified.
     636             : template <typename ValueT, typename... RangeTs>
     637             : detail::concat_range<ValueT, RangeTs...> concat(RangeTs &&... Ranges) {
     638             :   static_assert(sizeof...(RangeTs) > 1,
     639             :                 "Need more than one range to concatenate!");
     640             :   return detail::concat_range<ValueT, RangeTs...>(
     641             :       std::forward<RangeTs>(Ranges)...);
     642             : }
     643             : 
     644             : //===----------------------------------------------------------------------===//
     645             : //     Extra additions to <utility>
     646             : //===----------------------------------------------------------------------===//
     647             : 
     648             : /// \brief Function object to check whether the first component of a std::pair
     649             : /// compares less than the first component of another std::pair.
     650             : struct less_first {
     651             :   template <typename T> bool operator()(const T &lhs, const T &rhs) const {
     652             :     return lhs.first < rhs.first;
     653             :   }
     654             : };
     655             : 
     656             : /// \brief Function object to check whether the second component of a std::pair
     657             : /// compares less than the second component of another std::pair.
     658             : struct less_second {
     659             :   template <typename T> bool operator()(const T &lhs, const T &rhs) const {
     660             :     return lhs.second < rhs.second;
     661             :   }
     662             : };
     663             : 
     664             : // A subset of N3658. More stuff can be added as-needed.
     665             : 
     666             : /// \brief Represents a compile-time sequence of integers.
     667             : template <class T, T... I> struct integer_sequence {
     668             :   using value_type = T;
     669             : 
     670             :   static constexpr size_t size() { return sizeof...(I); }
     671             : };
     672             : 
     673             : /// \brief Alias for the common case of a sequence of size_ts.
     674             : template <size_t... I>
     675             : struct index_sequence : integer_sequence<std::size_t, I...> {};
     676             : 
     677             : template <std::size_t N, std::size_t... I>
     678             : struct build_index_impl : build_index_impl<N - 1, N - 1, I...> {};
     679             : template <std::size_t... I>
     680             : struct build_index_impl<0, I...> : index_sequence<I...> {};
     681             : 
     682             : /// \brief Creates a compile-time integer sequence for a parameter pack.
     683             : template <class... Ts>
     684             : struct index_sequence_for : build_index_impl<sizeof...(Ts)> {};
     685             : 
     686             : /// Utility type to build an inheritance chain that makes it easy to rank
     687             : /// overload candidates.
     688             : template <int N> struct rank : rank<N - 1> {};
     689             : template <> struct rank<0> {};
     690             : 
     691             : /// \brief traits class for checking whether type T is one of any of the given
     692             : /// types in the variadic list.
     693             : template <typename T, typename... Ts> struct is_one_of {
     694             :   static const bool value = false;
     695             : };
     696             : 
     697             : template <typename T, typename U, typename... Ts>
     698             : struct is_one_of<T, U, Ts...> {
     699             :   static const bool value =
     700             :       std::is_same<T, U>::value || is_one_of<T, Ts...>::value;
     701             : };
     702             : 
     703             : /// \brief traits class for checking whether type T is a base class for all
     704             : ///  the given types in the variadic list.
     705             : template <typename T, typename... Ts> struct are_base_of {
     706             :   static const bool value = true;
     707             : };
     708             : 
     709             : template <typename T, typename U, typename... Ts>
     710             : struct are_base_of<T, U, Ts...> {
     711             :   static const bool value =
     712             :       std::is_base_of<T, U>::value && are_base_of<T, Ts...>::value;
     713             : };
     714             : 
     715             : //===----------------------------------------------------------------------===//
     716             : //     Extra additions for arrays
     717             : //===----------------------------------------------------------------------===//
     718             : 
     719             : /// Find the length of an array.
     720             : template <class T, std::size_t N>
     721             : constexpr inline size_t array_lengthof(T (&)[N]) {
     722             :   return N;
     723             : }
     724             : 
     725             : /// Adapt std::less<T> for array_pod_sort.
     726             : template<typename T>
     727     7091934 : inline int array_pod_sort_comparator(const void *P1, const void *P2) {
     728     6609846 :   if (std::less<T>()(*reinterpret_cast<const T*>(P1),
     729             :                      *reinterpret_cast<const T*>(P2)))
     730             :     return -1;
     731     3208162 :   if (std::less<T>()(*reinterpret_cast<const T*>(P2),
     732             :                      *reinterpret_cast<const T*>(P1)))
     733             :     return 1;
     734       49216 :   return 0;
     735             : }
     736             : 
     737             : /// get_array_pod_sort_comparator - This is an internal helper function used to
     738             : /// get type deduction of T right.
     739             : template<typename T>
     740             : inline int (*get_array_pod_sort_comparator(const T &))
     741             :              (const void*, const void*) {
     742             :   return array_pod_sort_comparator<T>;
     743             : }
     744             : 
     745             : /// array_pod_sort - This sorts an array with the specified start and end
     746             : /// extent.  This is just like std::sort, except that it calls qsort instead of
     747             : /// using an inlined template.  qsort is slightly slower than std::sort, but
     748             : /// most sorts are not performance critical in LLVM and std::sort has to be
     749             : /// template instantiated for each type, leading to significant measured code
     750             : /// bloat.  This function should generally be used instead of std::sort where
     751             : /// possible.
     752             : ///
     753             : /// This function assumes that you have simple POD-like types that can be
     754             : /// compared with std::less and can be moved with memcpy.  If this isn't true,
     755             : /// you should use std::sort.
     756             : ///
     757             : /// NOTE: If qsort_r were portable, we could allow a custom comparator and
     758             : /// default to std::less.
     759             : template<class IteratorTy>
     760             : inline void array_pod_sort(IteratorTy Start, IteratorTy End) {
     761             :   // Don't inefficiently call qsort with one element or trigger undefined
     762             :   // behavior with an empty sequence.
     763    14012243 :   auto NElts = End - Start;
     764    14358136 :   if (NElts <= 1) return;
     765      439072 :   qsort(&*Start, NElts, sizeof(*Start), get_array_pod_sort_comparator(*Start));
     766             : }
     767             : 
     768             : template <class IteratorTy>
     769             : inline void array_pod_sort(
     770             :     IteratorTy Start, IteratorTy End,
     771             :     int (*Compare)(
     772             :         const typename std::iterator_traits<IteratorTy>::value_type *,
     773             :         const typename std::iterator_traits<IteratorTy>::value_type *)) {
     774             :   // Don't inefficiently call qsort with one element or trigger undefined
     775             :   // behavior with an empty sequence.
     776        2170 :   auto NElts = End - Start;
     777      183032 :   if (NElts <= 1) return;
     778       16799 :   qsort(&*Start, NElts, sizeof(*Start),
     779             :         reinterpret_cast<int (*)(const void *, const void *)>(Compare));
     780             : }
     781             : 
     782             : //===----------------------------------------------------------------------===//
     783             : //     Extra additions to <algorithm>
     784             : //===----------------------------------------------------------------------===//
     785             : 
     786             : /// For a container of pointers, deletes the pointers and then clears the
     787             : /// container.
     788             : template<typename Container>
     789             : void DeleteContainerPointers(Container &C) {
     790        1448 :   for (auto V : C)
     791         383 :     delete V;
     792             :   C.clear();
     793             : }
     794             : 
     795             : /// In a container of pairs (usually a map) whose second element is a pointer,
     796             : /// deletes the second elements and then clears the container.
     797             : template<typename Container>
     798      191017 : void DeleteContainerSeconds(Container &C) {
     799     1247489 :   for (auto &V : C)
     800      872575 :     delete V.second;
     801      191017 :   C.clear();
     802      191017 : }
     803             : 
     804             : /// Provide wrappers to std::for_each which take ranges instead of having to
     805             : /// pass begin/end explicitly.
     806             : template <typename R, typename UnaryPredicate>
     807          72 : UnaryPredicate for_each(R &&Range, UnaryPredicate P) {
     808          72 :   return std::for_each(adl_begin(Range), adl_end(Range), P);
     809             : }
     810             : 
     811             : /// Provide wrappers to std::all_of which take ranges instead of having to pass
     812             : /// begin/end explicitly.
     813             : template <typename R, typename UnaryPredicate>
     814      946016 : bool all_of(R &&Range, UnaryPredicate P) {
     815      947507 :   return std::all_of(adl_begin(Range), adl_end(Range), P);
     816             : }
     817             : 
     818             : /// Provide wrappers to std::any_of which take ranges instead of having to pass
     819             : /// begin/end explicitly.
     820             : template <typename R, typename UnaryPredicate>
     821      146282 : bool any_of(R &&Range, UnaryPredicate P) {
     822      146618 :   return std::any_of(adl_begin(Range), adl_end(Range), P);
     823             : }
     824             : 
     825             : /// Provide wrappers to std::none_of which take ranges instead of having to pass
     826             : /// begin/end explicitly.
     827             : template <typename R, typename UnaryPredicate>
     828      416660 : bool none_of(R &&Range, UnaryPredicate P) {
     829      416660 :   return std::none_of(adl_begin(Range), adl_end(Range), P);
     830             : }
     831             : 
     832             : /// Provide wrappers to std::find which take ranges instead of having to pass
     833             : /// begin/end explicitly.
     834             : template <typename R, typename T>
     835          74 : auto find(R &&Range, const T &Val) -> decltype(adl_begin(Range)) {
     836     5524602 :   return std::find(adl_begin(Range), adl_end(Range), Val);
     837             : }
     838             : 
     839             : /// Provide wrappers to std::find_if which take ranges instead of having to pass
     840             : /// begin/end explicitly.
     841             : template <typename R, typename UnaryPredicate>
     842       73287 : auto find_if(R &&Range, UnaryPredicate P) -> decltype(adl_begin(Range)) {
     843      118399 :   return std::find_if(adl_begin(Range), adl_end(Range), P);
     844             : }
     845             : 
     846             : template <typename R, typename UnaryPredicate>
     847             : auto find_if_not(R &&Range, UnaryPredicate P) -> decltype(adl_begin(Range)) {
     848             :   return std::find_if_not(adl_begin(Range), adl_end(Range), P);
     849             : }
     850             : 
     851             : /// Provide wrappers to std::remove_if which take ranges instead of having to
     852             : /// pass begin/end explicitly.
     853             : template <typename R, typename UnaryPredicate>
     854       26954 : auto remove_if(R &&Range, UnaryPredicate P) -> decltype(adl_begin(Range)) {
     855       28784 :   return std::remove_if(adl_begin(Range), adl_end(Range), P);
     856             : }
     857             : 
     858             : /// Provide wrappers to std::copy_if which take ranges instead of having to
     859             : /// pass begin/end explicitly.
     860             : template <typename R, typename OutputIt, typename UnaryPredicate>
     861        6046 : OutputIt copy_if(R &&Range, OutputIt Out, UnaryPredicate P) {
     862        8493 :   return std::copy_if(adl_begin(Range), adl_end(Range), Out, P);
     863             : }
     864             : 
     865             : template <typename R, typename OutputIt>
     866             : OutputIt copy(R &&Range, OutputIt Out) {
     867             :   return std::copy(adl_begin(Range), adl_end(Range), Out);
     868             : }
     869             : 
     870             : /// Wrapper function around std::find to detect if an element exists
     871             : /// in a container.
     872             : template <typename R, typename E>
     873       14631 : bool is_contained(R &&Range, const E &Element) {
     874    31751584 :   return std::find(adl_begin(Range), adl_end(Range), Element) != adl_end(Range);
     875             : }
     876             : 
     877             : /// Wrapper function around std::count to count the number of times an element
     878             : /// \p Element occurs in the given range \p Range.
     879             : template <typename R, typename E>
     880             : auto count(R &&Range, const E &Element) ->
     881             :     typename std::iterator_traits<decltype(adl_begin(Range))>::difference_type {
     882             :   return std::count(adl_begin(Range), adl_end(Range), Element);
     883             : }
     884             : 
     885             : /// Wrapper function around std::count_if to count the number of times an
     886             : /// element satisfying a given predicate occurs in a range.
     887             : template <typename R, typename UnaryPredicate>
     888       11625 : auto count_if(R &&Range, UnaryPredicate P) ->
     889             :     typename std::iterator_traits<decltype(adl_begin(Range))>::difference_type {
     890       11625 :   return std::count_if(adl_begin(Range), adl_end(Range), P);
     891             : }
     892             : 
     893             : /// Wrapper function around std::transform to apply a function to a range and
     894             : /// store the result elsewhere.
     895             : template <typename R, typename OutputIt, typename UnaryPredicate>
     896         103 : OutputIt transform(R &&Range, OutputIt d_first, UnaryPredicate P) {
     897       55175 :   return std::transform(adl_begin(Range), adl_end(Range), d_first, P);
     898             : }
     899             : 
     900             : /// Provide wrappers to std::partition which take ranges instead of having to
     901             : /// pass begin/end explicitly.
     902             : template <typename R, typename UnaryPredicate>
     903          14 : auto partition(R &&Range, UnaryPredicate P) -> decltype(adl_begin(Range)) {
     904          14 :   return std::partition(adl_begin(Range), adl_end(Range), P);
     905             : }
     906             : 
     907             : /// Provide wrappers to std::lower_bound which take ranges instead of having to
     908             : /// pass begin/end explicitly.
     909             : template <typename R, typename ForwardIt>
     910             : auto lower_bound(R &&Range, ForwardIt I) -> decltype(adl_begin(Range)) {
     911             :   return std::lower_bound(adl_begin(Range), adl_end(Range), I);
     912             : }
     913             : 
     914             : /// \brief Given a range of type R, iterate the entire range and return a
     915             : /// SmallVector with elements of the vector.  This is useful, for example,
     916             : /// when you want to iterate a range and then sort the results.
     917             : template <unsigned Size, typename R>
     918             : SmallVector<typename std::remove_const<detail::ValueOfRange<R>>::type, Size>
     919           2 : to_vector(R &&Range) {
     920           2 :   return {adl_begin(Range), adl_end(Range)};
     921             : }
     922             : 
     923             : /// Provide a container algorithm similar to C++ Library Fundamentals v2's
     924             : /// `erase_if` which is equivalent to:
     925             : ///
     926             : ///   C.erase(remove_if(C, pred), C.end());
     927             : ///
     928             : /// This version works for any container with an erase method call accepting
     929             : /// two iterators.
     930             : template <typename Container, typename UnaryPredicate>
     931       25372 : void erase_if(Container &C, UnaryPredicate P) {
     932        1976 :   C.erase(remove_if(C, P), C.end());
     933       25372 : }
     934             : 
     935             : //===----------------------------------------------------------------------===//
     936             : //     Extra additions to <memory>
     937             : //===----------------------------------------------------------------------===//
     938             : 
     939             : // Implement make_unique according to N3656.
     940             : 
     941             : /// \brief Constructs a `new T()` with the given args and returns a
     942             : ///        `unique_ptr<T>` which owns the object.
     943             : ///
     944             : /// Example:
     945             : ///
     946             : ///     auto p = make_unique<int>();
     947             : ///     auto p = make_unique<std::tuple<int, int>>(0, 1);
     948             : template <class T, class... Args>
     949             : typename std::enable_if<!std::is_array<T>::value, std::unique_ptr<T>>::type
     950    30498857 : make_unique(Args &&... args) {
     951    69627336 :   return std::unique_ptr<T>(new T(std::forward<Args>(args)...));
     952             : }
     953             : 
     954             : /// \brief Constructs a `new T[n]` with the given args and returns a
     955             : ///        `unique_ptr<T[]>` which owns the object.
     956             : ///
     957             : /// \param n size of the new array.
     958             : ///
     959             : /// Example:
     960             : ///
     961             : ///     auto p = make_unique<int[]>(2); // value-initializes the array with 0's.
     962             : template <class T>
     963             : typename std::enable_if<std::is_array<T>::value && std::extent<T>::value == 0,
     964             :                         std::unique_ptr<T>>::type
     965      239888 : make_unique(size_t n) {
     966     1391361 :   return std::unique_ptr<T>(new typename std::remove_extent<T>::type[n]());
     967             : }
     968             : 
     969             : /// This function isn't used and is only here to provide better compile errors.
     970             : template <class T, class... Args>
     971             : typename std::enable_if<std::extent<T>::value != 0>::type
     972             : make_unique(Args &&...) = delete;
     973             : 
     974             : struct FreeDeleter {
     975             :   void operator()(void* v) {
     976           2 :     ::free(v);
     977             :   }
     978             : };
     979             : 
     980             : template<typename First, typename Second>
     981             : struct pair_hash {
     982             :   size_t operator()(const std::pair<First, Second> &P) const {
     983     4484748 :     return std::hash<First>()(P.first) * 31 + std::hash<Second>()(P.second);
     984             :   }
     985             : };
     986             : 
     987             : /// A functor like C++14's std::less<void> in its absence.
     988             : struct less {
     989             :   template <typename A, typename B> bool operator()(A &&a, B &&b) const {
     990    79607632 :     return std::forward<A>(a) < std::forward<B>(b);
     991             :   }
     992             : };
     993             : 
     994             : /// A functor like C++14's std::equal<void> in its absence.
     995             : struct equal {
     996             :   template <typename A, typename B> bool operator()(A &&a, B &&b) const {
     997     2333474 :     return std::forward<A>(a) == std::forward<B>(b);
     998             :   }
     999             : };
    1000             : 
    1001             : /// Binary functor that adapts to any other binary functor after dereferencing
    1002             : /// operands.
    1003             : template <typename T> struct deref {
    1004             :   T func;
    1005             : 
    1006             :   // Could be further improved to cope with non-derivable functors and
    1007             :   // non-binary functors (should be a variadic template member function
    1008             :   // operator()).
    1009             :   template <typename A, typename B>
    1010             :   auto operator()(A &lhs, B &rhs) const -> decltype(func(*lhs, *rhs)) {
    1011             :     assert(lhs);
    1012             :     assert(rhs);
    1013             :     return func(*lhs, *rhs);
    1014             :   }
    1015             : };
    1016             : 
    1017             : namespace detail {
    1018             : 
    1019             : template <typename R> class enumerator_iter;
    1020             : 
    1021             : template <typename R> struct result_pair {
    1022             :   friend class enumerator_iter<R>;
    1023             : 
    1024             :   result_pair() = default;
    1025         150 :   result_pair(std::size_t Index, IterOfRange<R> Iter)
    1026         150 :       : Index(Index), Iter(Iter) {}
    1027             : 
    1028             :   result_pair<R> &operator=(const result_pair<R> &Other) {
    1029          89 :     Index = Other.Index;
    1030          89 :     Iter = Other.Iter;
    1031             :     return *this;
    1032             :   }
    1033             : 
    1034             :   std::size_t index() const { return Index; }
    1035             :   const ValueOfRange<R> &value() const { return *Iter; }
    1036             :   ValueOfRange<R> &value() { return *Iter; }
    1037             : 
    1038             : private:
    1039             :   std::size_t Index = std::numeric_limits<std::size_t>::max();
    1040             :   IterOfRange<R> Iter;
    1041             : };
    1042             : 
    1043             : template <typename R>
    1044             : class enumerator_iter
    1045             :     : public iterator_facade_base<
    1046             :           enumerator_iter<R>, std::forward_iterator_tag, result_pair<R>,
    1047             :           typename std::iterator_traits<IterOfRange<R>>::difference_type,
    1048             :           typename std::iterator_traits<IterOfRange<R>>::pointer,
    1049             :           typename std::iterator_traits<IterOfRange<R>>::reference> {
    1050             :   using result_type = result_pair<R>;
    1051             : 
    1052             : public:
    1053             :   explicit enumerator_iter(IterOfRange<R> EndIter)
    1054             :       : Result(std::numeric_limits<size_t>::max(), EndIter) {}
    1055             : 
    1056             :   enumerator_iter(std::size_t Index, IterOfRange<R> Iter)
    1057             :       : Result(Index, Iter) {}
    1058             : 
    1059             :   result_type &operator*() { return Result; }
    1060             :   const result_type &operator*() const { return Result; }
    1061             : 
    1062             :   enumerator_iter<R> &operator++() {
    1063             :     assert(Result.Index != std::numeric_limits<size_t>::max());
    1064       15382 :     ++Result.Iter;
    1065       42068 :     ++Result.Index;
    1066             :     return *this;
    1067             :   }
    1068             : 
    1069             :   bool operator==(const enumerator_iter<R> &RHS) const {
    1070             :     // Don't compare indices here, only iterators.  It's possible for an end
    1071             :     // iterator to have different indices depending on whether it was created
    1072             :     // by calling std::end() versus incrementing a valid iterator.
    1073         291 :     return Result.Iter == RHS.Result.Iter;
    1074             :   }
    1075             : 
    1076             :   enumerator_iter<R> &operator=(const enumerator_iter<R> &Other) {
    1077             :     Result = Other.Result;
    1078             :     return *this;
    1079             :   }
    1080             : 
    1081             : private:
    1082             :   result_type Result;
    1083             : };
    1084             : 
    1085             : template <typename R> class enumerator {
    1086             : public:
    1087             :   explicit enumerator(R &&Range) : TheRange(std::forward<R>(Range)) {}
    1088             : 
    1089             :   enumerator_iter<R> begin() {
    1090             :     return enumerator_iter<R>(0, std::begin(TheRange));
    1091             :   }
    1092             : 
    1093             :   enumerator_iter<R> end() {
    1094             :     return enumerator_iter<R>(std::end(TheRange));
    1095             :   }
    1096             : 
    1097             : private:
    1098             :   R TheRange;
    1099             : };
    1100             : 
    1101             : } // end namespace detail
    1102             : 
    1103             : /// Given an input range, returns a new range whose values are are pair (A,B)
    1104             : /// such that A is the 0-based index of the item in the sequence, and B is
    1105             : /// the value from the original sequence.  Example:
    1106             : ///
    1107             : /// std::vector<char> Items = {'A', 'B', 'C', 'D'};
    1108             : /// for (auto X : enumerate(Items)) {
    1109             : ///   printf("Item %d - %c\n", X.index(), X.value());
    1110             : /// }
    1111             : ///
    1112             : /// Output:
    1113             : ///   Item 0 - A
    1114             : ///   Item 1 - B
    1115             : ///   Item 2 - C
    1116             : ///   Item 3 - D
    1117             : ///
    1118             : template <typename R> detail::enumerator<R> enumerate(R &&TheRange) {
    1119             :   return detail::enumerator<R>(std::forward<R>(TheRange));
    1120             : }
    1121             : 
    1122             : namespace detail {
    1123             : 
    1124             : template <typename F, typename Tuple, std::size_t... I>
    1125         195 : auto apply_tuple_impl(F &&f, Tuple &&t, index_sequence<I...>)
    1126             :     -> decltype(std::forward<F>(f)(std::get<I>(std::forward<Tuple>(t))...)) {
    1127         195 :   return std::forward<F>(f)(std::get<I>(std::forward<Tuple>(t))...);
    1128             : }
    1129             : 
    1130             : } // end namespace detail
    1131             : 
    1132             : /// Given an input tuple (a1, a2, ..., an), pass the arguments of the
    1133             : /// tuple variadically to f as if by calling f(a1, a2, ..., an) and
    1134             : /// return the result.
    1135             : template <typename F, typename Tuple>
    1136             : auto apply_tuple(F &&f, Tuple &&t) -> decltype(detail::apply_tuple_impl(
    1137             :     std::forward<F>(f), std::forward<Tuple>(t),
    1138             :     build_index_impl<
    1139             :         std::tuple_size<typename std::decay<Tuple>::type>::value>{})) {
    1140             :   using Indices = build_index_impl<
    1141             :       std::tuple_size<typename std::decay<Tuple>::type>::value>;
    1142             : 
    1143             :   return detail::apply_tuple_impl(std::forward<F>(f), std::forward<Tuple>(t),
    1144         195 :                                   Indices{});
    1145             : }
    1146             : 
    1147             : } // end namespace llvm
    1148             : 
    1149             : #endif // LLVM_ADT_STLEXTRAS_H

Generated by: LCOV version 1.13