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

Generated by: LCOV version 1.13