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