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