contrib/llvm/include/llvm/ADT/STLExtras.h

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