LCOV - code coverage report
Current view: top level - include/llvm/ADT - STLExtras.h (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 863 1458 59.2 %
Date: 2018-10-14 09:39:32 Functions: 1015 3651 27.8 %
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/Config/abi-breaking.h"
      25             : #include "llvm/Support/ErrorHandling.h"
      26             : #include <algorithm>
      27             : #include <cassert>
      28             : #include <cstddef>
      29             : #include <cstdint>
      30             : #include <cstdlib>
      31             : #include <functional>
      32             : #include <initializer_list>
      33             : #include <iterator>
      34             : #include <limits>
      35             : #include <memory>
      36             : #include <tuple>
      37             : #include <type_traits>
      38             : #include <utility>
      39             : 
      40             : #ifdef EXPENSIVE_CHECKS
      41             : #include <random> // for std::mt19937
      42             : #endif
      43             : 
      44             : namespace llvm {
      45             : 
      46             : // Only used by compiler if both template types are the same.  Useful when
      47             : // using SFINAE to test for the existence of member functions.
      48             : template <typename T, T> struct SameType;
      49             : 
      50             : namespace detail {
      51             : 
      52             : template <typename RangeT>
      53             : using IterOfRange = decltype(std::begin(std::declval<RangeT &>()));
      54             : 
      55             : template <typename RangeT>
      56             : using ValueOfRange = typename std::remove_reference<decltype(
      57             :     *std::begin(std::declval<RangeT &>()))>::type;
      58             : 
      59             : } // end namespace detail
      60             : 
      61             : //===----------------------------------------------------------------------===//
      62             : //     Extra additions to <type_traits>
      63             : //===----------------------------------------------------------------------===//
      64             : 
      65             : template <typename T>
      66             : struct negation : std::integral_constant<bool, !bool(T::value)> {};
      67             : 
      68             : template <typename...> struct conjunction : std::true_type {};
      69             : template <typename B1> struct conjunction<B1> : B1 {};
      70             : template <typename B1, typename... Bn>
      71             : struct conjunction<B1, Bn...>
      72             :     : std::conditional<bool(B1::value), conjunction<Bn...>, B1>::type {};
      73             : 
      74             : //===----------------------------------------------------------------------===//
      75             : //     Extra additions to <functional>
      76             : //===----------------------------------------------------------------------===//
      77             : 
      78             : template <class Ty> struct identity {
      79             :   using argument_type = Ty;
      80             : 
      81           0 :   Ty &operator()(Ty &self) const {
      82           0 :     return self;
      83             :   }
      84           0 :   const Ty &operator()(const Ty &self) const {
      85           0 :     return self;
      86             :   }
      87             : };
      88             : 
      89             : template <class Ty> struct less_ptr {
      90           0 :   bool operator()(const Ty* left, const Ty* right) const {
      91     5464567 :     return *left < *right;
      92             :   }
      93             : };
      94             : 
      95             : template <class Ty> struct greater_ptr {
      96             :   bool operator()(const Ty* left, const Ty* right) const {
      97             :     return *right < *left;
      98             :   }
      99             : };
     100             : 
     101             : /// An efficient, type-erasing, non-owning reference to a callable. This is
     102             : /// intended for use as the type of a function parameter that is not used
     103             : /// after the function in question returns.
     104             : ///
     105             : /// This class does not own the callable, so it is not in general safe to store
     106             : /// a function_ref.
     107             : template<typename Fn> class function_ref;
     108             : 
     109             : template<typename Ret, typename ...Params>
     110             : class function_ref<Ret(Params...)> {
     111             :   Ret (*callback)(intptr_t callable, Params ...params) = nullptr;
     112             :   intptr_t callable;
     113             : 
     114             :   template<typename Callable>
     115    70056934 :   static Ret callback_fn(intptr_t callable, Params ...params) {
     116    62731236 :     return (*reinterpret_cast<Callable*>(callable))(
     117    70056913 :         std::forward<Params>(params)...);
     118             :   }
     119     5852150 : 
     120     5142075 : public:
     121     5852149 :   function_ref() = default;
     122             :   function_ref(std::nullptr_t) {}
     123     9897245 : 
     124     8830372 :   template <typename Callable>
     125    58665501 :   function_ref(Callable &&callable,
     126             :                typename std::enable_if<
     127     6644254 :                    !std::is_same<typename std::remove_reference<Callable>::type,
     128     6360311 :                                  function_ref>::value>::type * = nullptr)
     129     6644254 :       : callback(callback_fn<typename std::remove_reference<Callable>::type>),
     130    48768508 :         callable(reinterpret_cast<intptr_t>(&callable)) {}
     131     9725848 : 
     132     9450912 :   Ret operator()(Params ...params) const {
     133    21842214 :     return callback(callable, std::forward<Params>(params)...);
     134             :   }
     135    12610467 : 
     136    12371441 :   operator bool() const { return callback; }
     137    71187411 : };
     138     8223677 : 
     139     1267313 : // deleter - Very very very simple method that is used to invoke operator
     140     1040954 : // delete on something.  It is used like this:
     141    79003022 : //
     142    58520640 : //   for_each(V.begin(), B.end(), deleter<Interval>);
     143     2126194 : template <class T>
     144       42999 : inline void deleter(T *Ptr) {
     145    28223863 :   delete Ptr;
     146    93793848 : }
     147      633594 : 
     148        6723 : //===----------------------------------------------------------------------===//
     149     2015879 : //     Extra additions to <iterator>
     150    24860827 : //===----------------------------------------------------------------------===//
     151      412783 : 
     152       57683 : namespace adl_detail {
     153      857565 : 
     154      961436 : using std::begin;
     155       29661 : 
     156       27339 : template <typename ContainerTy>
     157    11964988 : auto adl_begin(ContainerTy &&container)
     158       10050 :     -> decltype(begin(std::forward<ContainerTy>(container))) {
     159      814914 :   return begin(std::forward<ContainerTy>(container));
     160       72531 : }
     161      815428 : 
     162    11445772 : using std::end;
     163      172847 : 
     164      123082 : template <typename ContainerTy>
     165      146186 : auto adl_end(ContainerTy &&container)
     166           0 :     -> decltype(end(std::forward<ContainerTy>(container))) {
     167     7225072 :   return end(std::forward<ContainerTy>(container));
     168      383266 : }
     169      398816 : 
     170           0 : using std::swap;
     171     1215719 : 
     172     1215719 : template <typename T>
     173    34177674 : void adl_swap(T &&lhs, T &&rhs) noexcept(noexcept(swap(std::declval<T>(),
     174           0 :                                                        std::declval<T>()))) {
     175     1642234 :   swap(std::forward<T>(lhs), std::forward<T>(rhs));
     176     1636173 : }
     177     2201231 : 
     178         354 : } // end namespace adl_detail
     179       18165 : 
     180        1514 : template <typename ContainerTy>
     181       18165 : auto adl_begin(ContainerTy &&container)
     182      559018 :     -> decltype(adl_detail::adl_begin(std::forward<ContainerTy>(container))) {
     183      194534 :   return adl_detail::adl_begin(std::forward<ContainerTy>(container));
     184      194276 : }
     185     1248415 : 
     186           0 : template <typename ContainerTy>
     187        5160 : auto adl_end(ContainerTy &&container)
     188        1541 :     -> decltype(adl_detail::adl_end(std::forward<ContainerTy>(container))) {
     189        1541 :   return adl_detail::adl_end(std::forward<ContainerTy>(container));
     190     1054139 : }
     191        3992 : 
     192        3982 : template <typename T>
     193     1271493 : void adl_swap(T &&lhs, T &&rhs) noexcept(
     194           0 :     noexcept(adl_detail::adl_swap(std::declval<T>(), std::declval<T>()))) {
     195        1301 :   adl_detail::adl_swap(std::forward<T>(lhs), std::forward<T>(rhs));
     196        1301 : }
     197        1301 : 
     198          15 : // mapped_iterator - This is a simple iterator adapter that causes a function to
     199         734 : // be applied whenever operator* is invoked on the iterator.
     200         734 : 
     201     4939300 : template <typename ItTy, typename FuncTy,
     202           0 :           typename FuncReturnTy =
     203       11367 :             decltype(std::declval<FuncTy>()(*std::declval<ItTy>()))>
     204        3195 : class mapped_iterator
     205        3226 :     : public iterator_adaptor_base<
     206           0 :              mapped_iterator<ItTy, FuncTy>, ItTy,
     207        7327 :              typename std::iterator_traits<ItTy>::iterator_category,
     208        7296 :              typename std::remove_reference<FuncReturnTy>::type> {
     209        7274 : public:
     210         237 :   mapped_iterator(ItTy U, FuncTy F)
     211      128224 :     : mapped_iterator::iterator_adaptor_base(std::move(U)), F(std::move(F)) {}
     212       11372 : 
     213      128145 :   ItTy getCurrent() { return this->I; }
     214           0 : 
     215     4813512 :   FuncReturnTy operator*() { return F(*this->I); }
     216       29587 : 
     217       35349 : private:
     218           0 :   FuncTy F;
     219         504 : };
     220         226 : 
     221         504 : // map_iterator - Provide a convenient way to create mapped_iterators, just like
     222        3415 : // make_pair is useful for creating pairs...
     223         550 : template <class ItTy, class FuncTy>
     224         572 : inline mapped_iterator<ItTy, FuncTy> map_iterator(ItTy I, FuncTy F) {
     225         550 :   return mapped_iterator<ItTy, FuncTy>(std::move(I), std::move(F));
     226           0 : }
     227        1100 : 
     228         256 : /// Helper to determine if type T has a member called rbegin().
     229         256 : template <typename Ty> class has_rbegin_impl {
     230           0 :   using yes = char[1];
     231        4015 :   using no = char[2];
     232        1113 : 
     233        4015 :   template <typename Inner>
     234           0 :   static yes& test(Inner *I, decltype(I->rbegin()) * = nullptr);
     235        1751 : 
     236        1407 :   template <typename>
     237        1407 :   static no& test(...);
     238           0 : 
     239     6830455 : public:
     240         483 :   static const bool value = sizeof(test<Ty>(nullptr)) == sizeof(yes);
     241         483 : };
     242           0 : 
     243         620 : /// Metafunction to determine if T& or T has a member called rbegin().
     244         620 : template <typename Ty>
     245         620 : struct has_rbegin : has_rbegin_impl<typename std::remove_reference<Ty>::type> {
     246           0 : };
     247        1635 : 
     248        1635 : // Returns an iterator_range over the given container which iterates in reverse.
     249        1635 : // Note that the container must have rbegin()/rend() methods for this to work.
     250           0 : template <typename ContainerTy>
     251         673 : auto reverse(ContainerTy &&C,
     252         673 :              typename std::enable_if<has_rbegin<ContainerTy>::value>::type * =
     253        5354 :                  nullptr) -> decltype(make_range(C.rbegin(), C.rend())) {
     254    35402460 :   return make_range(C.rbegin(), C.rend());
     255       60322 : }
     256        1440 : 
     257     5726190 : // Returns a std::reverse_iterator wrapped around the given iterator.
     258           0 : template <typename IteratorTy>
     259       12716 : std::reverse_iterator<IteratorTy> make_reverse_iterator(IteratorTy It) {
     260       12716 :   return std::reverse_iterator<IteratorTy>(It);
     261        1406 : }
     262    13176907 : 
     263      550546 : // Returns an iterator_range over the given container which iterates in reverse.
     264         444 : // Note that the container must have begin()/end() methods which return
     265         444 : // bidirectional iterators for this to work.
     266           0 : template <typename ContainerTy>
     267        6238 : auto reverse(
     268         583 :     ContainerTy &&C,
     269         583 :     typename std::enable_if<!has_rbegin<ContainerTy>::value>::type * = nullptr)
     270           0 :     -> decltype(make_range(llvm::make_reverse_iterator(std::end(C)),
     271          41 :                            llvm::make_reverse_iterator(std::begin(C)))) {
     272          41 :   return make_range(llvm::make_reverse_iterator(std::end(C)),
     273       28316 :                     llvm::make_reverse_iterator(std::begin(C)));
     274          57 : }
     275          41 : 
     276          41 : /// An iterator adaptor that filters the elements of given inner iterators.
     277     2832761 : ///
     278             : /// The predicate parameter should be a callable object that accepts the wrapped
     279           1 : /// iterator's reference type and returns a bool. When incrementing or
     280           1 : /// decrementing the iterator, it will call the predicate on each element and
     281           1 : /// skip any where it returns false.
     282      176735 : ///
     283           1 : /// \code
     284        4305 : ///   int A[] = { 1, 2, 3, 4 };
     285           1 : ///   auto R = make_filter_range(A, [](int N) { return N % 2 == 1; });
     286          38 : ///   // R contains { 1, 3 }.
     287         543 : /// \endcode
     288         543 : ///
     289         543 : /// Note: filter_iterator_base implements support for forward iteration.
     290           0 : /// filter_iterator_impl exists to provide support for bidirectional iteration,
     291           1 : /// conditional on whether the wrapped iterator supports it.
     292           1 : template <typename WrappedIteratorT, typename PredicateT, typename IterTag>
     293     2884368 : class filter_iterator_base
     294         194 :     : public iterator_adaptor_base<
     295        1512 :           filter_iterator_base<WrappedIteratorT, PredicateT, IterTag>,
     296        1512 :           WrappedIteratorT,
     297        1512 :           typename std::common_type<
     298           0 :               IterTag, typename std::iterator_traits<
     299           0 :                            WrappedIteratorT>::iterator_category>::type> {
     300           0 :   using BaseT = iterator_adaptor_base<
     301        2543 :       filter_iterator_base<WrappedIteratorT, PredicateT, IterTag>,
     302           0 :       WrappedIteratorT,
     303         128 :       typename std::common_type<
     304        2628 :           IterTag, typename std::iterator_traits<
     305         155 :                        WrappedIteratorT>::iterator_category>::type>;
     306           0 : 
     307          76 : protected:
     308          76 :   WrappedIteratorT End;
     309          76 :   PredicateT Pred;
     310          46 : 
     311     2107861 :   void findNextValid() {
     312     4207411 :     while (this->I != End && !Pred(*this->I))
     313           0 :       BaseT::operator++();
     314     2107861 :   }
     315     1821330 : 
     316     3633825 :   // Construct the iterator. The begin iterator needs to know where the end
     317           0 :   // is, so that it can properly stop when it gets there. The end iterator only
     318     1821330 :   // needs the predicate to support bidirectional iteration.
     319       18658 :   filter_iterator_base(WrappedIteratorT Begin, WrappedIteratorT End,
     320         556 :                        PredicateT Pred)
     321       36550 :       : BaseT(Begin), End(End), Pred(Pred) {
     322       18658 :     findNextValid();
     323        1885 :   }
     324        2086 : 
     325           0 : public:
     326        1885 :   using BaseT::operator++;
     327     1821587 : 
     328      669623 :   filter_iterator_base &operator++() {
     329     1820924 :     BaseT::operator++();
     330     1934047 :     findNextValid();
     331     1820586 :     return *this;
     332     1820398 :   }
     333           0 : };
     334     1820398 : 
     335     1823981 : /// Specialization of filter_iterator_base for forward iteration only.
     336     1820398 : template <typename WrappedIteratorT, typename PredicateT,
     337        4853 :           typename IterTag = std::forward_iterator_tag>
     338        1130 : class filter_iterator_impl
     339         188 :     : public filter_iterator_base<WrappedIteratorT, PredicateT, IterTag> {
     340         188 :   using BaseT = filter_iterator_base<WrappedIteratorT, PredicateT, IterTag>;
     341         188 : 
     342           0 : public:
     343           0 :   filter_iterator_impl(WrappedIteratorT Begin, WrappedIteratorT End,
     344           1 :                        PredicateT Pred)
     345           0 :       : BaseT(Begin, End, Pred) {}
     346         420 : };
     347           1 : 
     348           0 : /// Specialization of filter_iterator_base for bidirectional iteration.
     349           0 : template <typename WrappedIteratorT, typename PredicateT>
     350      170389 : class filter_iterator_impl<WrappedIteratorT, PredicateT,
     351           0 :                            std::bidirectional_iterator_tag>
     352           0 :     : public filter_iterator_base<WrappedIteratorT, PredicateT,
     353           0 :                                   std::bidirectional_iterator_tag> {
     354           0 :   using BaseT = filter_iterator_base<WrappedIteratorT, PredicateT,
     355          76 :                                      std::bidirectional_iterator_tag>;
     356       39901 :   void findPrevValid() {
     357      111898 :     while (!this->Pred(*this->I))
     358           0 :       BaseT::operator--();
     359       39825 :   }
     360          12 : 
     361          64 : public:
     362           0 :   using BaseT::operator--;
     363        7097 : 
     364         273 :   filter_iterator_impl(WrappedIteratorT Begin, WrappedIteratorT End,
     365         284 :                        PredicateT Pred)
     366           0 :       : BaseT(Begin, End, Pred) {}
     367          72 : 
     368          74 :   filter_iterator_impl &operator--() {
     369          75 :     BaseT::operator--();
     370       21858 :     findPrevValid();
     371          74 :     return *this;
     372           0 :   }
     373          67 : };
     374           0 : 
     375          64 : namespace detail {
     376          64 : 
     377          64 : template <bool is_bidirectional> struct fwd_or_bidi_tag_impl {
     378           0 :   using type = std::forward_iterator_tag;
     379        2131 : };
     380        2131 : 
     381        2131 : template <> struct fwd_or_bidi_tag_impl<true> {
     382     1820586 :   using type = std::bidirectional_iterator_tag;
     383        2131 : };
     384     3641172 : 
     385     1822529 : /// Helper which sets its type member to forward_iterator_tag if the category
     386           0 : /// of \p IterT does not derive from bidirectional_iterator_tag, and to
     387     3642966 : /// bidirectional_iterator_tag otherwise.
     388        2358 : template <typename IterT> struct fwd_or_bidi_tag {
     389        2170 :   using type = typename fwd_or_bidi_tag_impl<std::is_base_of<
     390         376 :       std::bidirectional_iterator_tag,
     391        1413 :       typename std::iterator_traits<IterT>::iterator_category>::value>::type;
     392        1413 : };
     393        1413 : 
     394           0 : } // namespace detail
     395           0 : 
     396           0 : /// Defines filter_iterator to a suitable specialization of
     397           0 : /// filter_iterator_impl, based on the underlying iterator's category.
     398           0 : template <typename WrappedIteratorT, typename PredicateT>
     399          90 : using filter_iterator = filter_iterator_impl<
     400          90 :     WrappedIteratorT, PredicateT,
     401          90 :     typename detail::fwd_or_bidi_tag<WrappedIteratorT>::type>;
     402             : 
     403          94 : /// Convenience function that takes a range of elements and a predicate,
     404          94 : /// and return a new filter_iterator range.
     405          94 : ///
     406           0 : /// FIXME: Currently if RangeT && is a rvalue reference to a temporary, the
     407          94 : /// lifetime of that temporary is not kept by the returned range object, and the
     408           0 : /// temporary is going to be dropped on the floor after the make_iterator_range
     409          94 : /// full expression that contains this function call.
     410           0 : template <typename RangeT, typename PredicateT>
     411         111 : iterator_range<filter_iterator<detail::IterOfRange<RangeT>, PredicateT>>
     412       18386 : make_filter_range(RangeT &&Range, PredicateT Pred) {
     413         111 :   using FilterIteratorT =
     414             :       filter_iterator<detail::IterOfRange<RangeT>, PredicateT>;
     415       36549 :   return make_range(
     416           0 :       FilterIteratorT(std::begin(std::forward<RangeT>(Range)),
     417           0 :                       std::end(std::forward<RangeT>(Range)), Pred),
     418           0 :       FilterIteratorT(std::end(std::forward<RangeT>(Range)),
     419       18342 :                       std::end(std::forward<RangeT>(Range)), Pred));
     420         236 : }
     421          67 : 
     422             : /// A pseudo-iterator adaptor that is designed to implement "early increment"
     423         405 : /// style loops.
     424         236 : ///
     425         236 : /// This is *not a normal iterator* and should almost never be used directly. It
     426             : /// is intended primarily to be used with range based for loops and some range
     427         185 : /// algorithms.
     428        1090 : ///
     429           8 : /// The iterator isn't quite an `OutputIterator` or an `InputIterator` but
     430           0 : /// somewhere between them. The constraints of these iterators are:
     431        1094 : ///
     432          12 : /// - On construction or after being incremented, it is comparable and
     433          12 : ///   dereferencable. It is *not* incrementable.
     434             : /// - After being dereferenced, it is neither comparable nor dereferencable, it
     435        1190 : ///   is only incrementable.
     436      910401 : ///
     437         433 : /// This means you can only dereference the iterator once, and you can only
     438           0 : /// increment it once between dereferences.
     439         108 : template <typename WrappedIteratorT>
     440         433 : class early_inc_iterator_impl
     441         108 :     : public iterator_adaptor_base<early_inc_iterator_impl<WrappedIteratorT>,
     442           0 :                                    WrappedIteratorT, std::input_iterator_tag> {
     443     3641280 :   using BaseT =
     444         433 :       iterator_adaptor_base<early_inc_iterator_impl<WrappedIteratorT>,
     445         108 :                             WrappedIteratorT, std::input_iterator_tag>;
     446         237 : 
     447         624 :   using PointerT = typename std::iterator_traits<WrappedIteratorT>::pointer;
     448         624 : 
     449         861 : protected:
     450           0 : #if LLVM_ENABLE_ABI_BREAKING_CHECKS
     451     3056657 :   bool IsEarlyIncremented = false;
     452         132 : #endif
     453         369 : 
     454          90 : public:
     455        2501 :   early_inc_iterator_impl(WrappedIteratorT I) : BaseT(I) {}
     456        2501 : 
     457        2501 :   using BaseT::operator*;
     458           0 :   typename BaseT::reference operator*() {
     459           0 : #if LLVM_ENABLE_ABI_BREAKING_CHECKS
     460           0 :     assert(!IsEarlyIncremented && "Cannot dereference twice!");
     461           0 :     IsEarlyIncremented = true;
     462           0 : #endif
     463           0 :     return *(this->I)++;
     464         520 :   }
     465      129559 : 
     466           0 :   using BaseT::operator++;
     467         520 :   early_inc_iterator_impl &operator++() {
     468           0 : #if LLVM_ENABLE_ABI_BREAKING_CHECKS
     469           0 :     assert(IsEarlyIncremented && "Cannot increment before dereferencing!");
     470      125361 :     IsEarlyIncremented = false;
     471         520 : #endif
     472           0 :     return *this;
     473           0 :   }
     474             : 
     475           0 :   using BaseT::operator==;
     476           0 :   bool operator==(const early_inc_iterator_impl &RHS) const {
     477           0 : #if LLVM_ENABLE_ABI_BREAKING_CHECKS
     478           0 :     assert(!IsEarlyIncremented && "Cannot compare after dereferencing!");
     479           0 : #endif
     480             :     return BaseT::operator==(RHS);
     481           0 :   }
     482           0 : };
     483           0 : 
     484           0 : /// Make a range that does early increment to allow mutation of the underlying
     485           0 : /// range without disrupting iteration.
     486             : ///
     487           0 : /// The underlying iterator will be incremented immediately after it is
     488           0 : /// dereferenced, allowing deletion of the current node or insertion of nodes to
     489           0 : /// not disrupt iteration provided they do not invalidate the *next* iterator --
     490           0 : /// the current iterator can be invalidated.
     491           0 : ///
     492             : /// This requires a very exact pattern of use that is only really suitable to
     493           0 : /// range based for loops and other range algorithms that explicitly guarantee
     494           0 : /// to dereference exactly once each element, and to increment exactly once each
     495           0 : /// element.
     496           0 : template <typename RangeT>
     497           0 : iterator_range<early_inc_iterator_impl<detail::IterOfRange<RangeT>>>
     498             : make_early_inc_range(RangeT &&Range) {
     499           0 :   using EarlyIncIteratorT =
     500           0 :       early_inc_iterator_impl<detail::IterOfRange<RangeT>>;
     501           0 :   return make_range(EarlyIncIteratorT(std::begin(std::forward<RangeT>(Range))),
     502           0 :                     EarlyIncIteratorT(std::end(std::forward<RangeT>(Range))));
     503           0 : }
     504             : 
     505           0 : // forward declarations required by zip_shortest/zip_first
     506           0 : template <typename R, typename UnaryPredicate>
     507           0 : bool all_of(R &&range, UnaryPredicate P);
     508           0 : 
     509           0 : template <size_t... I> struct index_sequence;
     510             : 
     511           0 : template <class... Ts> struct index_sequence_for;
     512           0 : 
     513           0 : namespace detail {
     514           0 : 
     515           0 : using std::declval;
     516             : 
     517           0 : // We have to alias this since inlining the actual type at the usage site
     518           0 : // in the parameter list of iterator_facade_base<> below ICEs MSVC 2017.
     519           0 : template<typename... Iters> struct ZipTupleType {
     520           0 :   using type = std::tuple<decltype(*declval<Iters>())...>;
     521           0 : };
     522             : 
     523           0 : template <typename ZipType, typename... Iters>
     524           0 : using zip_traits = iterator_facade_base<
     525           0 :     ZipType, typename std::common_type<std::bidirectional_iterator_tag,
     526           0 :                                        typename std::iterator_traits<
     527           0 :                                            Iters>::iterator_category...>::type,
     528             :     // ^ TODO: Implement random access methods.
     529           0 :     typename ZipTupleType<Iters...>::type,
     530           2 :     typename std::iterator_traits<typename std::tuple_element<
     531           0 :         0, std::tuple<Iters...>>::type>::difference_type,
     532           0 :     // ^ FIXME: This follows boost::make_zip_iterator's assumption that all
     533           0 :     // inner iterators have the same difference_type. It would fail if, for
     534             :     // instance, the second field's difference_type were non-numeric while the
     535           0 :     // first is.
     536           0 :     typename ZipTupleType<Iters...>::type *,
     537           2 :     typename ZipTupleType<Iters...>::type>;
     538           0 : 
     539           0 : template <typename ZipType, typename... Iters>
     540             : struct zip_common : public zip_traits<ZipType, Iters...> {
     541           0 :   using Base = zip_traits<ZipType, Iters...>;
     542           0 :   using value_type = typename Base::value_type;
     543           0 : 
     544           0 :   std::tuple<Iters...> iterators;
     545           0 : 
     546           0 : protected:
     547           0 :   template <size_t... Ns> value_type deref(index_sequence<Ns...>) const {
     548      713493 :     return value_type(*std::get<Ns>(iterators)...);
     549           0 :   }
     550           0 : 
     551           0 :   template <size_t... Ns>
     552           0 :   decltype(iterators) tup_inc(index_sequence<Ns...>) const {
     553           0 :     return std::tuple<Iters...>(std::next(std::get<Ns>(iterators))...);
     554           0 :   }
     555           0 : 
     556           0 :   template <size_t... Ns>
     557      457108 :   decltype(iterators) tup_dec(index_sequence<Ns...>) const {
     558           0 :     return std::tuple<Iters...>(std::prev(std::get<Ns>(iterators))...);
     559           0 :   }
     560           0 : 
     561           0 : public:
     562      457108 :   zip_common(Iters &&... ts) : iterators(std::forward<Iters>(ts)...) {}
     563           0 : 
     564           8 :   value_type operator*() { return deref(index_sequence_for<Iters...>{}); }
     565           0 : 
     566           0 :   const value_type operator*() const {
     567           0 :     return deref(index_sequence_for<Iters...>{});
     568           0 :   }
     569           0 : 
     570           0 :   ZipType &operator++() {
     571           0 :     iterators = tup_inc(index_sequence_for<Iters...>{});
     572           0 :     return *reinterpret_cast<ZipType *>(this);
     573           0 :   }
     574           8 : 
     575          16 :   ZipType &operator--() {
     576           0 :     static_assert(Base::IsBidirectional,
     577           4 :                   "All inner iterators must be at least bidirectional.");
     578           8 :     iterators = tup_dec(index_sequence_for<Iters...>{});
     579           0 :     return *reinterpret_cast<ZipType *>(this);
     580           4 :   }
     581           8 : };
     582           0 : 
     583           8 : template <typename... Iters>
     584           0 : struct zip_first : public zip_common<zip_first<Iters...>, Iters...> {
     585           0 :   using Base = zip_common<zip_first<Iters...>, Iters...>;
     586           0 : 
     587           0 :   bool operator==(const zip_first<Iters...> &other) const {
     588           0 :     return std::get<0>(this->iterators) == std::get<0>(other.iterators);
     589           0 :   }
     590      508180 : 
     591           0 :   zip_first(Iters &&... ts) : Base(std::forward<Iters>(ts)...) {}
     592           0 : };
     593           0 : 
     594             : template <typename... Iters>
     595           0 : class zip_shortest : public zip_common<zip_shortest<Iters...>, Iters...> {
     596           0 :   template <size_t... Ns>
     597           0 :   bool test(const zip_shortest<Iters...> &other, index_sequence<Ns...>) const {
     598           8 :     return all_of(std::initializer_list<bool>{std::get<Ns>(this->iterators) !=
     599           8 :                                               std::get<Ns>(other.iterators)...},
     600      526066 :                   identity<bool>{});
     601      526058 :   }
     602      526063 : 
     603           4 : public:
     604       56842 :   using Base = zip_common<zip_shortest<Iters...>, Iters...>;
     605       56838 : 
     606       56842 :   zip_shortest(Iters &&... ts) : Base(std::forward<Iters>(ts)...) {}
     607           4 : 
     608      469224 :   bool operator==(const zip_shortest<Iters...> &other) const {
     609      469254 :     return !test(other, index_sequence_for<Iters...>{});
     610      469220 :   }
     611           1 : };
     612           0 : 
     613             : template <template <typename...> class ItType, typename... Args> class zippy {
     614           0 : public:
     615           0 :   using iterator = ItType<decltype(std::begin(std::declval<Args>()))...>;
     616             :   using iterator_category = typename iterator::iterator_category;
     617           0 :   using value_type = typename iterator::value_type;
     618           1 :   using difference_type = typename iterator::difference_type;
     619           0 :   using pointer = typename iterator::pointer;
     620           0 :   using reference = typename iterator::reference;
     621           0 : 
     622           0 : private:
     623           0 :   std::tuple<Args...> ts;
     624             : 
     625           0 :   template <size_t... Ns> iterator begin_impl(index_sequence<Ns...>) const {
     626          11 :     return iterator(std::begin(std::get<Ns>(ts))...);
     627           0 :   }
     628           0 :   template <size_t... Ns> iterator end_impl(index_sequence<Ns...>) const {
     629           0 :     return iterator(std::end(std::get<Ns>(ts))...);
     630           0 :   }
     631          14 : 
     632           0 : public:
     633           0 :   zippy(Args &&... ts_) : ts(std::forward<Args>(ts_)...) {}
     634           0 : 
     635           0 :   iterator begin() const { return begin_impl(index_sequence_for<Args...>{}); }
     636           0 :   iterator end() const { return end_impl(index_sequence_for<Args...>{}); }
     637           0 : };
     638           0 : 
     639           0 : } // end namespace detail
     640           0 : 
     641           0 : /// zip iterator for two or more iteratable types.
     642             : template <typename T, typename U, typename... Args>
     643           0 : detail::zippy<detail::zip_shortest, T, U, Args...> zip(T &&t, U &&u,
     644           0 :                                                        Args &&... args) {
     645           0 :   return detail::zippy<detail::zip_shortest, T, U, Args...>(
     646           0 :       std::forward<T>(t), std::forward<U>(u), std::forward<Args>(args)...);
     647           0 : }
     648           0 : 
     649           0 : /// zip iterator that, for the sake of efficiency, assumes the first iteratee to
     650           0 : /// be the shortest.
     651           0 : template <typename T, typename U, typename... Args>
     652           0 : detail::zippy<detail::zip_first, T, U, Args...> zip_first(T &&t, U &&u,
     653           0 :                                                           Args &&... args) {
     654           0 :   return detail::zippy<detail::zip_first, T, U, Args...>(
     655          10 :       std::forward<T>(t), std::forward<U>(u), std::forward<Args>(args)...);
     656           0 : }
     657           0 : 
     658           0 : /// Iterator wrapper that concatenates sequences together.
     659           2 : ///
     660           0 : /// This can concatenate different iterators, even with different types, into
     661           0 : /// a single iterator provided the value types of all the concatenated
     662           0 : /// iterators expose `reference` and `pointer` types that can be converted to
     663           0 : /// `ValueT &` and `ValueT *` respectively. It doesn't support more
     664             : /// interesting/customized pointer or reference types.
     665           0 : ///
     666           0 : /// Currently this only supports forward or higher iterator categories as
     667             : /// inputs and always exposes a forward iterator interface.
     668           0 : template <typename ValueT, typename... IterTs>
     669       18274 : class concat_iterator
     670             :     : public iterator_facade_base<concat_iterator<ValueT, IterTs...>,
     671           2 :                                   std::forward_iterator_tag, ValueT> {
     672     1116469 :   using BaseT = typename concat_iterator::iterator_facade_base;
     673             : 
     674           1 :   /// We store both the current and end iterators for each concatenated
     675           1 :   /// sequence in a tuple of pairs.
     676           0 :   ///
     677           1 :   /// Note that something like iterator_range seems nice at first here, but the
     678           1 :   /// range properties are of little benefit and end up getting in the way
     679             :   /// because we need to do mutation on the current iterators.
     680           2 :   std::tuple<IterTs...> Begins;
     681           2 :   std::tuple<IterTs...> Ends;
     682             : 
     683           1 :   /// Attempts to increment a specific iterator.
     684           1 :   ///
     685             :   /// Returns true if it was able to increment the iterator. Returns false if
     686           1 :   /// the iterator is already at the end iterator.
     687     3801172 :   template <size_t Index> bool incrementHelper() {
     688           0 :     auto &Begin = std::get<Index>(Begins);
     689           0 :     auto &End = std::get<Index>(Ends);
     690     3801158 :     if (Begin == End)
     691           0 :       return false;
     692           0 : 
     693        9238 :     ++Begin;
     694     3016287 :     return true;
     695           0 :   }
     696       89371 : 
     697           0 :   /// Increments the first non-end iterator.
     698           0 :   ///
     699       89371 :   /// It is an error to call this with all iterators at the end.
     700           0 :   template <size_t... Ns> void increment(index_sequence<Ns...>) {
     701           0 :     // Build a sequence of functions to increment each iterator if possible.
     702           4 :     bool (concat_iterator::*IncrementHelperFns[])() = {
     703       89371 :         &concat_iterator::incrementHelper<Ns>...};
     704           0 : 
     705     1412720 :     // Loop over them, and stop as soon as we succeed at incrementing one.
     706           0 :     for (auto &IncrementHelperFn : IncrementHelperFns)
     707           0 :       if ((this->*IncrementHelperFn)())
     708     1412720 :         return;
     709           0 : 
     710           0 :     llvm_unreachable("Attempted to increment an end concat iterator!");
     711        9058 :   }
     712     1323349 : 
     713           0 :   /// Returns null if the specified iterator is at the end. Otherwise,
     714      281873 :   /// dereferences the iterator and returns the address of the resulting
     715           0 :   /// reference.
     716           0 :   template <size_t Index> ValueT *getHelper() const {
     717      281873 :     auto &Begin = std::get<Index>(Begins);
     718     1566155 :     auto &End = std::get<Index>(Ends);
     719           0 :     if (Begin == End)
     720     1566329 :       return nullptr;
     721      280830 : 
     722           0 :     return &*Begin;
     723      589907 :   }
     724     1777347 : 
     725     1777347 :   /// Finds the first non-end iterator, dereferences, and returns the resulting
     726     2156062 :   /// reference.
     727        3065 :   ///
     728           0 :   /// It is an error to call this with all iterators at the end.
     729          16 :   template <size_t... Ns> ValueT &get(index_sequence<Ns...>) const {
     730      311099 :     // Build a sequence of functions to get from iterator if possible.
     731           0 :     ValueT *(concat_iterator::*GetHelperFns[])() const = {
     732      412602 :         &concat_iterator::getHelper<Ns>...};
     733        2090 : 
     734     1494069 :     // Loop over them, and return the first result we find.
     735      412618 :     for (auto &GetHelperFn : GetHelperFns)
     736       10820 :       if (ValueT *P = (this->*GetHelperFn)())
     737     1491979 :         return *P;
     738       10820 : 
     739      412602 :     llvm_unreachable("Attempted to get a pointer from an end concat iterator!");
     740           0 :   }
     741     1014685 : 
     742      100617 : public:
     743       11285 :   /// Constructs an iterator from a squence of ranges.
     744     1025505 :   ///
     745       89578 :   /// We need the full range to know how to switch between each of the
     746          28 :   /// iterators.
     747           8 :   template <typename... RangeTs>
     748      611359 :   explicit concat_iterator(RangeTs &&... Ranges)
     749           4 :       : Begins(std::begin(Ranges)...), Ends(std::end(Ranges)...) {}
     750     1411677 : 
     751         222 :   using BaseT::operator++;
     752         541 : 
     753     1402619 :   concat_iterator &operator++() {
     754     1426623 :     increment(index_sequence_for<IterTs...>());
     755        9381 :     return *this;
     756     1426327 :   }
     757         331 : 
     758           0 :   ValueT &operator*() const { return get(index_sequence_for<IterTs...>()); }
     759           8 : 
     760     1981838 :   bool operator==(const concat_iterator &RHS) const {
     761     1981279 :     return Begins == RHS.Begins && Ends == RHS.Ends;
     762     1417796 :   }
     763     1567343 : };
     764           0 : 
     765     1566248 : namespace detail {
     766      568204 : 
     767         748 : /// Helper to store a sequence of ranges being concatenated and access them.
     768      566935 : ///
     769     1778203 : /// This is designed to facilitate providing actual storage when temporaries
     770     1778219 : /// are passed into the constructor such that we can use it as part of range
     771     1566255 : /// based for loops.
     772      839443 : template <typename ValueT, typename... RangeTs> class concat_range {
     773      839388 : public:
     774      566374 :   using iterator =
     775       21302 :       concat_iterator<ValueT,
     776       10301 :                       decltype(std::begin(std::declval<RangeTs &>()))...>;
     777       21247 : 
     778      850911 : private:
     779       10356 :   std::tuple<RangeTs...> Ranges;
     780      850872 : 
     781       31082 :   template <size_t... Ns> iterator begin_impl(index_sequence<Ns...>) {
     782       40388 :     return iterator(std::get<Ns>(Ranges)...);
     783       21257 :   }
     784     1142422 :   template <size_t... Ns> iterator end_impl(index_sequence<Ns...>) {
     785     1141671 :     return iterator(make_range(std::end(std::get<Ns>(Ranges)),
     786      850884 :                                std::end(std::get<Ns>(Ranges)))...);
     787         961 :   }
     788     1566712 : 
     789          10 : public:
     790         746 :   concat_range(RangeTs &&... Ranges)
     791         172 :       : Ranges(std::forward<RangeTs>(Ranges)...) {}
     792     1575907 : 
     793         857 :   iterator begin() { return begin_impl(index_sequence_for<RangeTs...>{}); }
     794     2299178 :   iterator end() { return end_impl(index_sequence_for<RangeTs...>{}); }
     795        9511 : };
     796         145 : 
     797     2300527 : } // end namespace detail
     798        9511 : 
     799        1204 : /// Concatenated range across two or more ranges.
     800         174 : ///
     801           0 : /// The desired value type must be explicitly specified.
     802           6 : template <typename ValueT, typename... RangeTs>
     803        3703 : detail::concat_range<ValueT, RangeTs...> concat(RangeTs &&... Ranges) {
     804        1467 :   static_assert(sizeof...(RangeTs) > 1,
     805        3288 :                 "Need more than one range to concatenate!");
     806           0 :   return detail::concat_range<ValueT, RangeTs...>(
     807           0 :       std::forward<RangeTs>(Ranges)...);
     808         585 : }
     809        3065 : 
     810        4081 : //===----------------------------------------------------------------------===//
     811        2620 : //     Extra additions to <utility>
     812           0 : //===----------------------------------------------------------------------===//
     813        1032 : 
     814         384 : /// Function object to check whether the first component of a std::pair
     815         218 : /// compares less than the first component of another std::pair.
     816           0 : struct less_first {
     817         915 :   template <typename T> bool operator()(const T &lhs, const T &rhs) const {
     818      332997 :     return lhs.first < rhs.first;
     819         697 :   }
     820           6 : };
     821      291918 : 
     822        1428 : /// Function object to check whether the second component of a std::pair
     823       11209 : /// compares less than the second component of another std::pair.
     824         921 : struct less_second {
     825         724 :   template <typename T> bool operator()(const T &lhs, const T &rhs) const {
     826      590303 :     return lhs.second < rhs.second;
     827       11341 :   }
     828       11919 : };
     829      602205 : 
     830           0 : /// \brief Function object to apply a binary function to the first component of
     831         283 : /// a std::pair.
     832          15 : template<typename FuncTy>
     833       10955 : struct on_first {
     834      414063 :   FuncTy func;
     835       10953 : 
     836       21591 :   template <typename T>
     837      412907 :   auto operator()(const T &lhs, const T &rhs) const
     838       21247 :       -> decltype(func(lhs.first, rhs.first)) {
     839       85611 :     return func(lhs.first, rhs.first);
     840        9511 :   }
     841       10671 : };
     842     1045273 : 
     843       30885 : // A subset of N3658. More stuff can be added as-needed.
     844       21247 : 
     845     1016762 : /// Represents a compile-time sequence of integers.
     846        1513 : template <class T, T... I> struct integer_sequence {
     847        1881 :   using value_type = T;
     848         688 : 
     849         414 :   static constexpr size_t size() { return sizeof...(I); }
     850           0 : };
     851         742 : 
     852         904 : /// Alias for the common case of a sequence of size_ts.
     853         730 : template <size_t... I>
     854         111 : struct index_sequence : integer_sequence<std::size_t, I...> {};
     855     1420288 : 
     856           0 : template <std::size_t N, std::size_t... I>
     857     1417229 : struct build_index_impl : build_index_impl<N - 1, N - 1, I...> {};
     858        3049 : template <std::size_t... I>
     859         987 : struct build_index_impl<0, I...> : index_sequence<I...> {};
     860           0 : 
     861     2002194 : /// Creates a compile-time integer sequence for a parameter pack.
     862     1980947 : template <class... Ts>
     863     1417229 : struct index_sequence_for : build_index_impl<sizeof...(Ts)> {};
     864       18274 : 
     865       39521 : /// Utility type to build an inheritance chain that makes it easy to rank
     866           0 : /// overload candidates.
     867      590636 : template <int N> struct rank : rank<N - 1> {};
     868       24262 : template <> struct rank<0> {};
     869      566374 : 
     870         878 : /// traits class for checking whether type T is one of any of the given
     871         329 : /// types in the variadic list.
     872           0 : template <typename T, typename... Ts> struct is_one_of {
     873      839388 :   static const bool value = false;
     874      840484 : };
     875      566485 : 
     876           0 : template <typename T, typename U, typename... Ts>
     877         143 : struct is_one_of<T, U, Ts...> {
     878         143 :   static const bool value =
     879      851218 :       std::is_same<T, U>::value || is_one_of<T, Ts...>::value;
     880             : };
     881      850855 : 
     882         331 : /// traits class for checking whether type T is a base class for all
     883           6 : ///  the given types in the variadic list.
     884           0 : template <typename T, typename... Ts> struct are_base_of {
     885     1141559 :   static const bool value = true;
     886     1141559 : };
     887      851953 : 
     888           0 : template <typename T, typename U, typename... Ts>
     889           0 : struct are_base_of<T, U, Ts...> {
     890        1098 :   static const bool value =
     891         331 :       std::is_base_of<T, U>::value && are_base_of<T, Ts...>::value;
     892           0 : };
     893           0 : 
     894           0 : //===----------------------------------------------------------------------===//
     895          55 : //     Extra additions for arrays
     896           0 : //===----------------------------------------------------------------------===//
     897           0 : 
     898          55 : /// Find the length of an array.
     899           0 : template <class T, std::size_t N>
     900           0 : constexpr inline size_t array_lengthof(T (&)[N]) {
     901           0 :   return N;
     902           0 : }
     903         601 : 
     904     1417229 : /// Adapt std::less<T> for array_pod_sort.
     905           0 : template<typename T>
     906    22408900 : inline int array_pod_sort_comparator(const void *P1, const void *P2) {
     907    21499229 :   if (std::less<T>()(*reinterpret_cast<const T*>(P1),
     908     1417230 :                      *reinterpret_cast<const T*>(P2)))
     909       19430 :     return -1;
     910     8290243 :   if (std::less<T>()(*reinterpret_cast<const T*>(P2),
     911      573966 :                      *reinterpret_cast<const T*>(P1)))
     912     7680338 :     return 1;
     913           0 :   return 0;
     914         746 : }
     915       30190 : 
     916         349 : /// get_array_pod_sort_comparator - This is an internal helper function used to
     917           0 : /// get type deduction of T right.
     918       20155 : template<typename T>
     919          43 : inline int (*get_array_pod_sort_comparator(const T &))
     920         725 :              (const void*, const void*) {
     921       10010 :   return array_pod_sort_comparator<T>;
     922         103 : }
     923           0 : 
     924       48994 : /// array_pod_sort - This sorts an array with the specified start and end
     925       46932 : /// extent.  This is just like std::sort, except that it calls qsort instead of
     926      504969 : /// using an inlined template.  qsort is slightly slower than std::sort, but
     927      502182 : /// most sorts are not performance critical in LLVM and std::sort has to be
     928       24962 : /// template instantiated for each type, leading to significant measured code
     929           0 : /// bloat.  This function should generally be used instead of std::sort where
     930       13226 : /// possible.
     931        3049 : ///
     932        2374 : /// This function assumes that you have simple POD-like types that can be
     933           0 : /// compared with std::less and can be moved with memcpy.  If this isn't true,
     934           0 : /// you should use std::sort.
     935           0 : ///
     936        2909 : /// NOTE: If qsort_r were portable, we could allow a custom comparator and
     937         394 : /// default to std::less.
     938         529 : template<class IteratorTy>
     939           0 : inline void array_pod_sort(IteratorTy Start, IteratorTy End) {
     940           0 :   // Don't inefficiently call qsort with one element or trigger undefined
     941           0 :   // behavior with an empty sequence.
     942      544728 :   auto NElts = End - Start;
     943      803332 :   if (NElts <= 1) return;
     944         632 : #ifdef EXPENSIVE_CHECKS
     945           0 :   std::mt19937 Generator(std::random_device{}());
     946     3070463 :   std::shuffle(Start, End, Generator);
     947     6140926 : #endif
     948      595284 :   qsort(&*Start, NElts, sizeof(*Start), get_array_pod_sort_comparator(*Start));
     949        1799 : }
     950     1330970 : 
     951        3519 : template <class IteratorTy>
     952     1333121 : inline void array_pod_sort(
     953      125054 :     IteratorTy Start, IteratorTy End,
     954        1824 :     int (*Compare)(
     955        1429 :         const typename std::iterator_traits<IteratorTy>::value_type *,
     956        1098 :         const typename std::iterator_traits<IteratorTy>::value_type *)) {
     957           7 :   // Don't inefficiently call qsort with one element or trigger undefined
     958         142 :   // behavior with an empty sequence.
     959        2551 :   auto NElts = End - Start;
     960      228935 :   if (NElts <= 1) return;
     961           0 : #ifdef EXPENSIVE_CHECKS
     962     1024188 :   std::mt19937 Generator(std::random_device{}());
     963     1023442 :   std::shuffle(Start, End, Generator);
     964             : #endif
     965       20638 :   qsort(&*Start, NElts, sizeof(*Start),
     966        1402 :         reinterpret_cast<int (*)(const void *, const void *)>(Compare));
     967        1969 : }
     968    42995772 : 
     969    42548624 : // Provide wrappers to std::sort which shuffle the elements before sorting
     970           0 : // to help uncover non-deterministic behavior (PR35135).
     971         725 : template <typename IteratorTy>
     972     2504417 : inline void sort(IteratorTy Start, IteratorTy End) {
     973        1250 : #ifdef EXPENSIVE_CHECKS
     974        6995 :   std::mt19937 Generator(std::random_device{}());
     975           0 :   std::shuffle(Start, End, Generator);
     976             : #endif
     977     4766604 :   std::sort(Start, End);
     978         617 : }
     979             : 
     980      131236 : template <typename Container> inline void sort(Container &&C) {
     981             :   llvm::sort(adl_begin(C), adl_end(C));
     982      135455 : }
     983        5332 : 
     984             : template <typename IteratorTy, typename Compare>
     985        3582 : inline void sort(IteratorTy Start, IteratorTy End, Compare Comp) {
     986      111725 : #ifdef EXPENSIVE_CHECKS
     987           0 :   std::mt19937 Generator(std::random_device{}());
     988      115702 :   std::shuffle(Start, End, Generator);
     989        2062 : #endif
     990      858816 :   std::sort(Start, End, Comp);
     991         407 : }
     992           0 : 
     993             : template <typename Container, typename Compare>
     994        1240 : inline void sort(Container &&C, Compare Comp) {
     995         407 :   llvm::sort(adl_begin(C), adl_end(C), Comp);
     996        1240 : }
     997           0 : 
     998           0 : //===----------------------------------------------------------------------===//
     999        1015 : //     Extra additions to <algorithm>
    1000          59 : //===----------------------------------------------------------------------===//
    1001           0 : 
    1002          17 : /// For a container of pointers, deletes the pointers and then clears the
    1003      142710 : /// container.
    1004           0 : template<typename Container>
    1005        6322 : void DeleteContainerPointers(Container &C) {
    1006        7426 :   for (auto V : C)
    1007         431 :     delete V;
    1008           0 :   C.clear();
    1009        6452 : }
    1010           9 : 
    1011           0 : /// In a container of pairs (usually a map) whose second element is a pointer,
    1012           0 : /// deletes the second elements and then clears the container.
    1013           0 : template<typename Container>
    1014     3309878 : void DeleteContainerSeconds(Container &C) {
    1015     8894398 :   for (auto &V : C)
    1016     5387285 :     delete V.second;
    1017     3309877 :   C.clear();
    1018     3309878 : }
    1019          15 : 
    1020        1503 : /// Get the size of a range. This is a wrapper function around std::distance
    1021           0 : /// which is only enabled when the operation is O(1).
    1022        1710 : template <typename R>
    1023         207 : auto size(R &&Range, typename std::enable_if<
    1024         169 :                          std::is_same<typename std::iterator_traits<decltype(
    1025           0 :                                           Range.begin())>::iterator_category,
    1026           0 :                                       std::random_access_iterator_tag>::value,
    1027           0 :                          void>::type * = nullptr)
    1028          60 :     -> decltype(std::distance(Range.begin(), Range.end())) {
    1029           0 :   return std::distance(Range.begin(), Range.end());
    1030         236 : }
    1031           0 : 
    1032         519 : /// Provide wrappers to std::for_each which take ranges instead of having to
    1033           0 : /// pass begin/end explicitly.
    1034         519 : template <typename R, typename UnaryPredicate>
    1035          75 : UnaryPredicate for_each(R &&Range, UnaryPredicate P) {
    1036          80 :   return std::for_each(adl_begin(Range), adl_end(Range), P);
    1037           0 : }
    1038         156 : 
    1039         363 : /// Provide wrappers to std::all_of which take ranges instead of having to pass
    1040         207 : /// begin/end explicitly.
    1041           1 : template <typename R, typename UnaryPredicate>
    1042     1339667 : bool all_of(R &&Range, UnaryPredicate P) {
    1043     1373625 :   return std::all_of(adl_begin(Range), adl_end(Range), P);
    1044          70 : }
    1045        8278 : 
    1046        8160 : /// Provide wrappers to std::any_of which take ranges instead of having to pass
    1047           0 : /// begin/end explicitly.
    1048          30 : template <typename R, typename UnaryPredicate>
    1049   175794115 : bool any_of(R &&Range, UnaryPredicate P) {
    1050   175794336 :   return std::any_of(adl_begin(Range), adl_end(Range), P);
    1051         659 : }
    1052         729 : 
    1053          70 : /// Provide wrappers to std::none_of which take ranges instead of having to pass
    1054           0 : /// begin/end explicitly.
    1055        1663 : template <typename R, typename UnaryPredicate>
    1056        1660 : bool none_of(R &&Range, UnaryPredicate P) {
    1057           0 :   return std::none_of(adl_begin(Range), adl_end(Range), P);
    1058         111 : }
    1059         111 : 
    1060           0 : /// Provide wrappers to std::find which take ranges instead of having to pass
    1061        1565 : /// begin/end explicitly.
    1062      367106 : template <typename R, typename T>
    1063      366881 : auto find(R &&Range, const T &Val) -> decltype(adl_begin(Range)) {
    1064     5463620 :   return std::find(adl_begin(Range), adl_end(Range), Val);
    1065         210 : }
    1066        3737 : 
    1067        8561 : /// Provide wrappers to std::find_if which take ranges instead of having to pass
    1068       10186 : /// begin/end explicitly.
    1069        3830 : template <typename R, typename UnaryPredicate>
    1070      168813 : auto find_if(R &&Range, UnaryPredicate P) -> decltype(adl_begin(Range)) {
    1071      221212 :   return std::find_if(adl_begin(Range), adl_end(Range), P);
    1072           0 : }
    1073           1 : 
    1074           0 : template <typename R, typename UnaryPredicate>
    1075      201703 : auto find_if_not(R &&Range, UnaryPredicate P) -> decltype(adl_begin(Range)) {
    1076      218078 :   return std::find_if_not(adl_begin(Range), adl_end(Range), P);
    1077       16375 : }
    1078           0 : 
    1079       21636 : /// Provide wrappers to std::remove_if which take ranges instead of having to
    1080       21824 : /// pass begin/end explicitly.
    1081    13356553 : template <typename R, typename UnaryPredicate>
    1082    14334091 : auto remove_if(R &&Range, UnaryPredicate P) -> decltype(adl_begin(Range)) {
    1083      952012 :   return std::remove_if(adl_begin(Range), adl_end(Range), P);
    1084      860718 : }
    1085      687943 : 
    1086      687996 : /// Provide wrappers to std::copy_if which take ranges instead of having to
    1087             : /// pass begin/end explicitly.
    1088      141146 : template <typename R, typename OutputIt, typename UnaryPredicate>
    1089      154309 : OutputIt copy_if(R &&Range, OutputIt Out, UnaryPredicate P) {
    1090        3181 :   return std::copy_if(adl_begin(Range), adl_end(Range), Out, P);
    1091      165047 : }
    1092       52995 : 
    1093           0 : template <typename R, typename OutputIt>
    1094           0 : OutputIt copy(R &&Range, OutputIt Out) {
    1095           0 :   return std::copy(adl_begin(Range), adl_end(Range), Out);
    1096          52 : }
    1097          52 : 
    1098       53169 : /// Wrapper function around std::find to detect if an element exists
    1099       53201 : /// in a container.
    1100        1073 : template <typename R, typename E>
    1101     5712239 : bool is_contained(R &&Range, const E &Element) {
    1102    28555866 :   return std::find(adl_begin(Range), adl_end(Range), Element) != adl_end(Range);
    1103       50150 : }
    1104       45275 : 
    1105          32 : /// Wrapper function around std::count to count the number of times an element
    1106           0 : /// \p Element occurs in the given range \p Range.
    1107           0 : template <typename R, typename E>
    1108           2 : auto count(R &&Range, const E &Element) ->
    1109           0 :     typename std::iterator_traits<decltype(adl_begin(Range))>::difference_type {
    1110          18 :   return std::count(adl_begin(Range), adl_end(Range), Element);
    1111           0 : }
    1112           0 : 
    1113         528 : /// Wrapper function around std::count_if to count the number of times an
    1114         528 : /// element satisfying a given predicate occurs in a range.
    1115           0 : template <typename R, typename UnaryPredicate>
    1116           0 : auto count_if(R &&Range, UnaryPredicate P) ->
    1117           0 :     typename std::iterator_traits<decltype(adl_begin(Range))>::difference_type {
    1118          72 :   return std::count_if(adl_begin(Range), adl_end(Range), P);
    1119      723479 : }
    1120      723479 : 
    1121       38282 : /// Wrapper function around std::transform to apply a function to a range and
    1122     6227095 : /// store the result elsewhere.
    1123         829 : template <typename R, typename OutputIt, typename UnaryPredicate>
    1124         112 : OutputIt transform(R &&Range, OutputIt d_first, UnaryPredicate P) {
    1125         454 :   return std::transform(adl_begin(Range), adl_end(Range), d_first, P);
    1126           0 : }
    1127           0 : 
    1128             : /// Provide wrappers to std::partition which take ranges instead of having to
    1129           0 : /// pass begin/end explicitly.
    1130        6577 : template <typename R, typename UnaryPredicate>
    1131           1 : auto partition(R &&Range, UnaryPredicate P) -> decltype(adl_begin(Range)) {
    1132           0 :   return std::partition(adl_begin(Range), adl_end(Range), P);
    1133           0 : }
    1134             : 
    1135          10 : /// Provide wrappers to std::lower_bound which take ranges instead of having to
    1136          10 : /// pass begin/end explicitly.
    1137           0 : template <typename R, typename ForwardIt>
    1138       16078 : auto lower_bound(R &&Range, ForwardIt I) -> decltype(adl_begin(Range)) {
    1139           0 :   return std::lower_bound(adl_begin(Range), adl_end(Range), I);
    1140             : }
    1141       70361 : 
    1142       58289 : template <typename R, typename ForwardIt, typename Compare>
    1143           0 : auto lower_bound(R &&Range, ForwardIt I, Compare C)
    1144          18 :     -> decltype(adl_begin(Range)) {
    1145       82892 :   return std::lower_bound(adl_begin(Range), adl_end(Range), I, C);
    1146             : }
    1147           0 : 
    1148           0 : /// Provide wrappers to std::upper_bound which take ranges instead of having to
    1149             : /// pass begin/end explicitly.
    1150           0 : template <typename R, typename ForwardIt>
    1151        2317 : auto upper_bound(R &&Range, ForwardIt I) -> decltype(adl_begin(Range)) {
    1152             :   return std::upper_bound(adl_begin(Range), adl_end(Range), I);
    1153           0 : }
    1154           0 : 
    1155           0 : template <typename R, typename ForwardIt, typename Compare>
    1156           0 : auto upper_bound(R &&Range, ForwardIt I, Compare C)
    1157          72 :     -> decltype(adl_begin(Range)) {
    1158         116 :   return std::upper_bound(adl_begin(Range), adl_end(Range), I, C);
    1159           0 : }
    1160           0 : /// Wrapper function around std::equal to detect if all elements
    1161           0 : /// in a container are same.
    1162      196124 : template <typename R>
    1163           0 : bool is_splat(R &&Range) {
    1164           0 :   size_t range_size = size(Range);
    1165           0 :   return range_size != 0 && (range_size == 1 ||
    1166           0 :          std::equal(adl_begin(Range) + 1, adl_end(Range), adl_begin(Range)));
    1167           0 : }
    1168             : 
    1169             : /// Given a range of type R, iterate the entire range and return a
    1170             : /// SmallVector with elements of the vector.  This is useful, for example,
    1171             : /// when you want to iterate a range and then sort the results.
    1172             : template <unsigned Size, typename R>
    1173             : SmallVector<typename std::remove_const<detail::ValueOfRange<R>>::type, Size>
    1174           2 : to_vector(R &&Range) {
    1175           2 :   return {adl_begin(Range), adl_end(Range)};
    1176             : }
    1177             : 
    1178             : /// Provide a container algorithm similar to C++ Library Fundamentals v2's
    1179             : /// `erase_if` which is equivalent to:
    1180             : ///
    1181             : ///   C.erase(remove_if(C, pred), C.end());
    1182             : ///
    1183             : /// This version works for any container with an erase method call accepting
    1184             : /// two iterators.
    1185             : template <typename Container, typename UnaryPredicate>
    1186        4100 : void erase_if(Container &C, UnaryPredicate P) {
    1187        4100 :   C.erase(remove_if(C, P), C.end());
    1188        4100 : }
    1189             : 
    1190             : //===----------------------------------------------------------------------===//
    1191             : //     Extra additions to <memory>
    1192             : //===----------------------------------------------------------------------===//
    1193           0 : 
    1194             : // Implement make_unique according to N3656.
    1195      327101 : 
    1196      655474 : /// Constructs a `new T()` with the given args and returns a
    1197      327102 : ///        `unique_ptr<T>` which owns the object.
    1198      272175 : ///
    1199      540014 : /// Example:
    1200      304284 : ///
    1201       37513 : ///     auto p = make_unique<int>();
    1202       40754 : ///     auto p = make_unique<std::tuple<int, int>>(0, 1);
    1203        3241 : template <class T, class... Args>
    1204       52966 : typename std::enable_if<!std::is_array<T>::value, std::unique_ptr<T>>::type
    1205    44920858 : make_unique(Args &&... args) {
    1206    52567713 :   return std::unique_ptr<T>(new T(std::forward<Args>(args)...));
    1207           0 : }
    1208         637 : 
    1209         637 : /// Constructs a `new T[n]` with the given args and returns a
    1210          63 : ///        `unique_ptr<T[]>` which owns the object.
    1211         485 : ///
    1212      563036 : /// \param n size of the new array.
    1213     9709844 : ///
    1214     9725949 : /// Example:
    1215       79893 : ///
    1216         240 : ///     auto p = make_unique<int[]>(2); // value-initializes the array with 0's.
    1217          20 : template <class T>
    1218       59877 : typename std::enable_if<std::is_array<T>::value && std::extent<T>::value == 0,
    1219           0 :                         std::unique_ptr<T>>::type
    1220      170152 : make_unique(size_t n) {
    1221     2643134 :   return std::unique_ptr<T>(new typename std::remove_extent<T>::type[n]());
    1222         445 : }
    1223         191 : 
    1224         191 : /// This function isn't used and is only here to provide better compile errors.
    1225     6314948 : template <class T, class... Args>
    1226     6324239 : typename std::enable_if<std::extent<T>::value != 0>::type
    1227      335934 : make_unique(Args &&...) = delete;
    1228      655704 : 
    1229        2962 : struct FreeDeleter {
    1230       16653 :   void operator()(void* v) {
    1231         274 :     ::free(v);
    1232         202 :   }
    1233      549597 : };
    1234       33492 : 
    1235        8566 : template<typename First, typename Second>
    1236       10699 : struct pair_hash {
    1237           6 :   size_t operator()(const std::pair<First, Second> &P) const {
    1238     6500943 :     return std::hash<First>()(P.first) * 31 + std::hash<Second>()(P.second);
    1239        2343 :   }
    1240       47231 : };
    1241         349 : 
    1242         349 : /// A functor like C++14's std::less<void> in its absence.
    1243         156 : struct less {
    1244         907 :   template <typename A, typename B> bool operator()(A &&a, B &&b) const {
    1245      122054 :     return std::forward<A>(a) < std::forward<B>(b);
    1246       16476 :   }
    1247           3 : };
    1248          27 : 
    1249          24 : /// A functor like C++14's std::equal<void> in its absence.
    1250          26 : struct equal {
    1251        3288 :   template <typename A, typename B> bool operator()(A &&a, B &&b) const {
    1252       79023 :     return std::forward<A>(a) == std::forward<B>(b);
    1253          66 :   }
    1254           6 : };
    1255        3126 : 
    1256           0 : /// Binary functor that adapts to any other binary functor after dereferencing
    1257        3051 : /// operands.
    1258        3376 : template <typename T> struct deref {
    1259         420 :   T func;
    1260         449 : 
    1261           0 :   // Could be further improved to cope with non-derivable functors and
    1262         118 :   // non-binary functors (should be a variadic template member function
    1263         118 :   // operator()).
    1264           2 :   template <typename A, typename B>
    1265        1411 :   auto operator()(A &lhs, B &rhs) const -> decltype(func(*lhs, *rhs)) {
    1266        2368 :     assert(lhs);
    1267           0 :     assert(rhs);
    1268          14 :     return func(*lhs, *rhs);
    1269      417438 :   }
    1270      836506 : };
    1271          21 : 
    1272          21 : namespace detail {
    1273          93 : 
    1274         166 : template <typename R> class enumerator_iter;
    1275           8 : 
    1276           0 : template <typename R> struct result_pair {
    1277       39022 :   friend class enumerator_iter<R>;
    1278          28 : 
    1279          53 :   result_pair() = default;
    1280         194 :   result_pair(std::size_t Index, IterOfRange<R> Iter)
    1281          92 :       : Index(Index), Iter(Iter) {}
    1282           0 : 
    1283           2 :   result_pair<R> &operator=(const result_pair<R> &Other) {
    1284           4 :     Index = Other.Index;
    1285    91914437 :     Iter = Other.Iter;
    1286          37 :     return *this;
    1287          61 :   }
    1288          24 : 
    1289         767 :   std::size_t index() const { return Index; }
    1290         769 :   const ValueOfRange<R> &value() const { return *Iter; }
    1291       25920 :   ValueOfRange<R> &value() { return *Iter; }
    1292         414 : 
    1293           8 : private:
    1294          13 :   std::size_t Index = std::numeric_limits<std::size_t>::max();
    1295         219 :   IterOfRange<R> Iter;
    1296         164 : };
    1297           0 : 
    1298          29 : template <typename R>
    1299       53348 : class enumerator_iter
    1300           0 :     : public iterator_facade_base<
    1301     3060000 :           enumerator_iter<R>, std::forward_iterator_tag, result_pair<R>,
    1302          29 :           typename std::iterator_traits<IterOfRange<R>>::difference_type,
    1303         620 :           typename std::iterator_traits<IterOfRange<R>>::pointer,
    1304        1333 :           typename std::iterator_traits<IterOfRange<R>>::reference> {
    1305        1333 :   using result_type = result_pair<R>;
    1306           0 : 
    1307          37 : public:
    1308          37 :   explicit enumerator_iter(IterOfRange<R> EndIter)
    1309           0 :       : Result(std::numeric_limits<size_t>::max(), EndIter) {}
    1310           2 : 
    1311           2 :   enumerator_iter(std::size_t Index, IterOfRange<R> Iter)
    1312           0 :       : Result(Index, Iter) {}
    1313       52571 : 
    1314     1306999 :   result_type &operator*() { return Result; }
    1315           0 :   const result_type &operator*() const { return Result; }
    1316          61 : 
    1317           7 :   enumerator_iter<R> &operator++() {
    1318           0 :     assert(Result.Index != std::numeric_limits<size_t>::max());
    1319         308 :     ++Result.Iter;
    1320         397 :     ++Result.Index;
    1321             :     return *this;
    1322        9354 :   }
    1323       10614 : 
    1324           0 :   bool operator==(const enumerator_iter<R> &RHS) const {
    1325         628 :     // Don't compare indices here, only iterators.  It's possible for an end
    1326         628 :     // iterator to have different indices depending on whether it was created
    1327             :     // by calling std::end() versus incrementing a valid iterator.
    1328       33033 :     return Result.Iter == RHS.Result.Iter;
    1329       64922 :   }
    1330           0 : 
    1331         424 :   enumerator_iter<R> &operator=(const enumerator_iter<R> &Other) {
    1332         424 :     Result = Other.Result;
    1333             :     return *this;
    1334           0 :   }
    1335           0 : 
    1336           0 : private:
    1337        2850 :   result_type Result;
    1338        3535 : };
    1339        3762 : 
    1340        3762 : template <typename R> class enumerator {
    1341           0 : public:
    1342           0 :   explicit enumerator(R &&Range) : TheRange(std::forward<R>(Range)) {}
    1343           0 : 
    1344           0 :   enumerator_iter<R> begin() {
    1345           0 :     return enumerator_iter<R>(0, std::begin(TheRange));
    1346           0 :   }
    1347           0 : 
    1348        2598 :   enumerator_iter<R> end() {
    1349        2598 :     return enumerator_iter<R>(std::end(TheRange));
    1350           7 :   }
    1351          14 : 
    1352           0 : private:
    1353           0 :   R TheRange;
    1354           0 : };
    1355          41 : 
    1356         307 : } // end namespace detail
    1357           0 : 
    1358          28 : /// Given an input range, returns a new range whose values are are pair (A,B)
    1359          40 : /// such that A is the 0-based index of the item in the sequence, and B is
    1360          12 : /// the value from the original sequence.  Example:
    1361           0 : ///
    1362           0 : /// std::vector<char> Items = {'A', 'B', 'C', 'D'};
    1363           0 : /// for (auto X : enumerate(Items)) {
    1364          13 : ///   printf("Item %d - %c\n", X.index(), X.value());
    1365          13 : /// }
    1366           0 : ///
    1367           0 : /// Output:
    1368           0 : ///   Item 0 - A
    1369           0 : ///   Item 1 - B
    1370           0 : ///   Item 2 - C
    1371           0 : ///   Item 3 - D
    1372           0 : ///
    1373           0 : template <typename R> detail::enumerator<R> enumerate(R &&TheRange) {
    1374      373228 :   return detail::enumerator<R>(std::forward<R>(TheRange));
    1375           0 : }
    1376           0 : 
    1377           0 : namespace detail {
    1378           0 : 
    1379           0 : template <typename F, typename Tuple, std::size_t... I>
    1380           0 : auto apply_tuple_impl(F &&f, Tuple &&t, index_sequence<I...>)
    1381             :     -> decltype(std::forward<F>(f)(std::get<I>(std::forward<Tuple>(t))...)) {
    1382           0 :   return std::forward<F>(f)(std::get<I>(std::forward<Tuple>(t))...);
    1383           0 : }
    1384           0 : 
    1385          15 : } // end namespace detail
    1386           0 : 
    1387             : /// Given an input tuple (a1, a2, ..., an), pass the arguments of the
    1388           0 : /// tuple variadically to f as if by calling f(a1, a2, ..., an) and
    1389          28 : /// return the result.
    1390         201 : template <typename F, typename Tuple>
    1391           0 : auto apply_tuple(F &&f, Tuple &&t) -> decltype(detail::apply_tuple_impl(
    1392           0 :     std::forward<F>(f), std::forward<Tuple>(t),
    1393           0 :     build_index_impl<
    1394           0 :         std::tuple_size<typename std::decay<Tuple>::type>::value>{})) {
    1395           0 :   using Indices = build_index_impl<
    1396           0 :       std::tuple_size<typename std::decay<Tuple>::type>::value>;
    1397           2 : 
    1398           2 :   return detail::apply_tuple_impl(std::forward<F>(f), std::forward<Tuple>(t),
    1399          11 :                                   Indices{});
    1400           0 : }
    1401           0 : 
    1402           0 : } // end namespace llvm
    1403        1358 : 
    1404        1358 : #endif // LLVM_ADT_STLEXTRAS_H

Generated by: LCOV version 1.13