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

Generated by: LCOV version 1.13