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