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/Config/abi-breaking.h"
  25 #include "llvm/Support/ErrorHandling.h"
  26 #include <algorithm>
  27 #include <cassert>
  28 #include <cstddef>
  29 #include <cstdint>
  30 #include <cstdlib>
  31 #include <functional>
  32 #include <initializer_list>
  33 #include <iterator>
  34 #include <limits>
  35 #include <memory>
  36 #include <tuple>
  37 #include <type_traits>
  38 #include <utility>
  39
  40 #ifdef EXPENSIVE_CHECKS
  41 #include <random> // for std::mt19937
  42 #endif
  43
  44 namespace llvm {
  45
  46 // Only used by compiler if both template types are the same.  Useful when
  47 // using SFINAE to test for the existence of member functions.
  48 template <typename T, T> struct SameType;
  49
  50 namespace detail {
  51
  52 template <typename RangeT>
  53 using IterOfRange = decltype(std::begin(std::declval<RangeT &>()));
  54
  55 template <typename RangeT>
  56 using ValueOfRange = typename std::remove_reference<decltype(
  57     *std::begin(std::declval<RangeT &>()))>::type;
  58
  59 } // end namespace detail
  60
  61 //===----------------------------------------------------------------------===//
  62 //     Extra additions to <type_traits>
  63 //===----------------------------------------------------------------------===//
  64
  65 template <typename T>
  66 struct negation : std::integral_constant<bool, !bool(T::value)> {};
  67
  68 template <typename...> struct conjunction : std::true_type {};
  69 template <typename B1> struct conjunction<B1> : B1 {};
  70 template <typename B1, typename... Bn>
  71 struct conjunction<B1, Bn...>
  72     : std::conditional<bool(B1::value), conjunction<Bn...>, B1>::type {};
  73
  74 template <typename T> struct make_const_ptr {
  75   using type =
  76       typename std::add_pointer<typename std::add_const<T>::type>::type;
  77 };
  78
  79 template <typename T> struct make_const_ref {
  80   using type = typename std::add_lvalue_reference<
  81       typename std::add_const<T>::type>::type;
  82 };
  83
  84 //===----------------------------------------------------------------------===//
  85 //     Extra additions to <functional>
  86 //===----------------------------------------------------------------------===//
  87
  88 template <class Ty> struct identity {
  89   using argument_type = Ty;
  90
  91   Ty &operator()(Ty &self) const {
  92     return self;
  93   }
  94   const Ty &operator()(const Ty &self) const {
  95     return self;
  96   }
  97 };
  98
  99 template <class Ty> struct less_ptr {
 100   bool operator()(const Ty* left, const Ty* right) const {
 101     return *left < *right;
 102   }
 103 };
 104
 105 template <class Ty> struct greater_ptr {
 106   bool operator()(const Ty* left, const Ty* right) const {
 107     return *right < *left;
 108   }
 109 };
 110
 111 /// An efficient, type-erasing, non-owning reference to a callable. This is
 112 /// intended for use as the type of a function parameter that is not used
 113 /// after the function in question returns.
 114 ///
 115 /// This class does not own the callable, so it is not in general safe to store
 116 /// a function_ref.
 117 template<typename Fn> class function_ref;
 118
 119 template<typename Ret, typename ...Params>
 120 class function_ref<Ret(Params...)> {
 121   Ret (*callback)(intptr_t callable, Params ...params) = nullptr;
 122   intptr_t callable;
 123
 124   template<typename Callable>
 125   static Ret callback_fn(intptr_t callable, Params ...params) {
 126     return (*reinterpret_cast<Callable*>(callable))(
 127         std::forward<Params>(params)...);
 128   }
 129
 130 public:
 131   function_ref() = default;
 132   function_ref(std::nullptr_t) {}
 133
 134   template <typename Callable>
 135   function_ref(Callable &&callable,
 136                typename std::enable_if<
 137                    !std::is_same<typename std::remove_reference<Callable>::type,
 138                                  function_ref>::value>::type * = nullptr)
 139       : callback(callback_fn<typename std::remove_reference<Callable>::type>),
 140         callable(reinterpret_cast<intptr_t>(&callable)) {}
 141
 142   Ret operator()(Params ...params) const {
 143     return callback(callable, std::forward<Params>(params)...);
 144   }
 145
 146   operator bool() const { return callback; }
 147 };
 148
 149 // deleter - Very very very simple method that is used to invoke operator
 150 // delete on something.  It is used like this:
 151 //
 152 //   for_each(V.begin(), B.end(), deleter<Interval>);
 153 template <class T>
 154 inline void deleter(T *Ptr) {
 155   delete Ptr;
 156 }
 157
 158 //===----------------------------------------------------------------------===//
 159 //     Extra additions to <iterator>
 160 //===----------------------------------------------------------------------===//
 161
 162 namespace adl_detail {
 163
 164 using std::begin;
 165
 166 template <typename ContainerTy>
 167 auto adl_begin(ContainerTy &&container)
 168     -> decltype(begin(std::forward<ContainerTy>(container))) {
 169   return begin(std::forward<ContainerTy>(container));
 170 }
 171
 172 using std::end;
 173
 174 template <typename ContainerTy>
 175 auto adl_end(ContainerTy &&container)
 176     -> decltype(end(std::forward<ContainerTy>(container))) {
 177   return end(std::forward<ContainerTy>(container));
 178 }
 179
 180 using std::swap;
 181
 182 template <typename T>
 183 void adl_swap(T &&lhs, T &&rhs) noexcept(noexcept(swap(std::declval<T>(),
 184                                                        std::declval<T>()))) {
 185   swap(std::forward<T>(lhs), std::forward<T>(rhs));
 186 }
 187
 188 } // end namespace adl_detail
 189
 190 template <typename ContainerTy>
 191 auto adl_begin(ContainerTy &&container)
 192     -> decltype(adl_detail::adl_begin(std::forward<ContainerTy>(container))) {
 193   return adl_detail::adl_begin(std::forward<ContainerTy>(container));
 194 }
 195
 196 template <typename ContainerTy>
 197 auto adl_end(ContainerTy &&container)
 198     -> decltype(adl_detail::adl_end(std::forward<ContainerTy>(container))) {
 199   return adl_detail::adl_end(std::forward<ContainerTy>(container));
 200 }
 201
 202 template <typename T>
 203 void adl_swap(T &&lhs, T &&rhs) noexcept(
 204     noexcept(adl_detail::adl_swap(std::declval<T>(), std::declval<T>()))) {
 205   adl_detail::adl_swap(std::forward<T>(lhs), std::forward<T>(rhs));
 206 }
 207
 208 /// Test whether \p RangeOrContainer is empty. Similar to C++17 std::empty.
 209 template <typename T>
 210 constexpr bool empty(const T &RangeOrContainer) {
 211   return adl_begin(RangeOrContainer) == adl_end(RangeOrContainer);
 212 }
 213
 214 // mapped_iterator - This is a simple iterator adapter that causes a function to
 215 // be applied whenever operator* is invoked on the iterator.
 216
 217 template <typename ItTy, typename FuncTy,
 218           typename FuncReturnTy =
 219             decltype(std::declval<FuncTy>()(*std::declval<ItTy>()))>
 220 class mapped_iterator
 221     : public iterator_adaptor_base<
 222              mapped_iterator<ItTy, FuncTy>, ItTy,
 223              typename std::iterator_traits<ItTy>::iterator_category,
 224              typename std::remove_reference<FuncReturnTy>::type> {
 225 public:
 226   mapped_iterator(ItTy U, FuncTy F)
 227     : mapped_iterator::iterator_adaptor_base(std::move(U)), F(std::move(F)) {}
 228
 229   ItTy getCurrent() { return this->I; }
 230
 231   FuncReturnTy operator*() { return F(*this->I); }
 232
 233 private:
 234   FuncTy F;
 235 };
 236
 237 // map_iterator - Provide a convenient way to create mapped_iterators, just like
 238 // make_pair is useful for creating pairs...
 239 template <class ItTy, class FuncTy>
 240 inline mapped_iterator<ItTy, FuncTy> map_iterator(ItTy I, FuncTy F) {
 241   return mapped_iterator<ItTy, FuncTy>(std::move(I), std::move(F));
 242 }
 243
 244 /// Helper to determine if type T has a member called rbegin().
 245 template <typename Ty> class has_rbegin_impl {
 246   using yes = char[1];
 247   using no = char[2];
 248
 249   template <typename Inner>
 250   static yes& test(Inner *I, decltype(I->rbegin()) * = nullptr);
 251
 252   template <typename>
 253   static no& test(...);
 254
 255 public:
 256   static const bool value = sizeof(test<Ty>(nullptr)) == sizeof(yes);
 257 };
 258
 259 /// Metafunction to determine if T& or T has a member called rbegin().
 260 template <typename Ty>
 261 struct has_rbegin : has_rbegin_impl<typename std::remove_reference<Ty>::type> {
 262 };
 263
 264 // Returns an iterator_range over the given container which iterates in reverse.
 265 // Note that the container must have rbegin()/rend() methods for this to work.
 266 template <typename ContainerTy>
 267 auto reverse(ContainerTy &&C,
 268              typename std::enable_if<has_rbegin<ContainerTy>::value>::type * =
 269                  nullptr) -> decltype(make_range(C.rbegin(), C.rend())) {
 270   return make_range(C.rbegin(), C.rend());
 271 }
 272
 273 // Returns a std::reverse_iterator wrapped around the given iterator.
 274 template <typename IteratorTy>
 275 std::reverse_iterator<IteratorTy> make_reverse_iterator(IteratorTy It) {
 276   return std::reverse_iterator<IteratorTy>(It);
 277 }
 278
 279 // Returns an iterator_range over the given container which iterates in reverse.
 280 // Note that the container must have begin()/end() methods which return
 281 // bidirectional iterators for this to work.
 282 template <typename ContainerTy>
 283 auto reverse(
 284     ContainerTy &&C,
 285     typename std::enable_if<!has_rbegin<ContainerTy>::value>::type * = nullptr)
 286     -> decltype(make_range(llvm::make_reverse_iterator(std::end(C)),
 287                            llvm::make_reverse_iterator(std::begin(C)))) {
 288   return make_range(llvm::make_reverse_iterator(std::end(C)),
 289                     llvm::make_reverse_iterator(std::begin(C)));
 290 }
 291
 292 /// An iterator adaptor that filters the elements of given inner iterators.
 293 ///
 294 /// The predicate parameter should be a callable object that accepts the wrapped
 295 /// iterator's reference type and returns a bool. When incrementing or
 296 /// decrementing the iterator, it will call the predicate on each element and
 297 /// skip any where it returns false.
 298 ///
 299 /// \code
 300 ///   int A[] = { 1, 2, 3, 4 };
 301 ///   auto R = make_filter_range(A, [](int N) { return N % 2 == 1; });
 302 ///   // R contains { 1, 3 }.
 303 /// \endcode
 304 ///
 305 /// Note: filter_iterator_base implements support for forward iteration.
 306 /// filter_iterator_impl exists to provide support for bidirectional iteration,
 307 /// conditional on whether the wrapped iterator supports it.
 308 template <typename WrappedIteratorT, typename PredicateT, typename IterTag>
 309 class filter_iterator_base
 310     : public iterator_adaptor_base<
 311           filter_iterator_base<WrappedIteratorT, PredicateT, IterTag>,
 312           WrappedIteratorT,
 313           typename std::common_type<
 314               IterTag, typename std::iterator_traits<
 315                            WrappedIteratorT>::iterator_category>::type> {
 316   using BaseT = iterator_adaptor_base<
 317       filter_iterator_base<WrappedIteratorT, PredicateT, IterTag>,
 318       WrappedIteratorT,
 319       typename std::common_type<
 320           IterTag, typename std::iterator_traits<
 321                        WrappedIteratorT>::iterator_category>::type>;
 322
 323 protected:
 324   WrappedIteratorT End;
 325   PredicateT Pred;
 326
 327   void findNextValid() {
 328     while (this->I != End && !Pred(*this->I))
 329       BaseT::operator++();
 330   }
 331
 332   // Construct the iterator. The begin iterator needs to know where the end
 333   // is, so that it can properly stop when it gets there. The end iterator only
 334   // needs the predicate to support bidirectional iteration.
 335   filter_iterator_base(WrappedIteratorT Begin, WrappedIteratorT End,
 336                        PredicateT Pred)
 337       : BaseT(Begin), End(End), Pred(Pred) {
 338     findNextValid();
 339   }
 340
 341 public:
 342   using BaseT::operator++;
 343
 344   filter_iterator_base &operator++() {
 345     BaseT::operator++();
 346     findNextValid();
 347     return *this;
 348   }
 349 };
 350
 351 /// Specialization of filter_iterator_base for forward iteration only.
 352 template <typename WrappedIteratorT, typename PredicateT,
 353           typename IterTag = std::forward_iterator_tag>
 354 class filter_iterator_impl
 355     : public filter_iterator_base<WrappedIteratorT, PredicateT, IterTag> {
 356   using BaseT = filter_iterator_base<WrappedIteratorT, PredicateT, IterTag>;
 357
 358 public:
 359   filter_iterator_impl(WrappedIteratorT Begin, WrappedIteratorT End,
 360                        PredicateT Pred)
 361       : BaseT(Begin, End, Pred) {}
 362 };
 363
 364 /// Specialization of filter_iterator_base for bidirectional iteration.
 365 template <typename WrappedIteratorT, typename PredicateT>
 366 class filter_iterator_impl<WrappedIteratorT, PredicateT,
 367                            std::bidirectional_iterator_tag>
 368     : public filter_iterator_base<WrappedIteratorT, PredicateT,
 369                                   std::bidirectional_iterator_tag> {
 370   using BaseT = filter_iterator_base<WrappedIteratorT, PredicateT,
 371                                      std::bidirectional_iterator_tag>;
 372   void findPrevValid() {
 373     while (!this->Pred(*this->I))
 374       BaseT::operator--();
 375   }
 376
 377 public:
 378   using BaseT::operator--;
 379
 380   filter_iterator_impl(WrappedIteratorT Begin, WrappedIteratorT End,
 381                        PredicateT Pred)
 382       : BaseT(Begin, End, Pred) {}
 383
 384   filter_iterator_impl &operator--() {
 385     BaseT::operator--();
 386     findPrevValid();
 387     return *this;
 388   }
 389 };
 390
 391 namespace detail {
 392
 393 template <bool is_bidirectional> struct fwd_or_bidi_tag_impl {
 394   using type = std::forward_iterator_tag;
 395 };
 396
 397 template <> struct fwd_or_bidi_tag_impl<true> {
 398   using type = std::bidirectional_iterator_tag;
 399 };
 400
 401 /// Helper which sets its type member to forward_iterator_tag if the category
 402 /// of \p IterT does not derive from bidirectional_iterator_tag, and to
 403 /// bidirectional_iterator_tag otherwise.
 404 template <typename IterT> struct fwd_or_bidi_tag {
 405   using type = typename fwd_or_bidi_tag_impl<std::is_base_of<
 406       std::bidirectional_iterator_tag,
 407       typename std::iterator_traits<IterT>::iterator_category>::value>::type;
 408 };
 409
 410 } // namespace detail
 411
 412 /// Defines filter_iterator to a suitable specialization of
 413 /// filter_iterator_impl, based on the underlying iterator's category.
 414 template <typename WrappedIteratorT, typename PredicateT>
 415 using filter_iterator = filter_iterator_impl<
 416     WrappedIteratorT, PredicateT,
 417     typename detail::fwd_or_bidi_tag<WrappedIteratorT>::type>;
 418
 419 /// Convenience function that takes a range of elements and a predicate,
 420 /// and return a new filter_iterator range.
 421 ///
 422 /// FIXME: Currently if RangeT && is a rvalue reference to a temporary, the
 423 /// lifetime of that temporary is not kept by the returned range object, and the
 424 /// temporary is going to be dropped on the floor after the make_iterator_range
 425 /// full expression that contains this function call.
 426 template <typename RangeT, typename PredicateT>
 427 iterator_range<filter_iterator<detail::IterOfRange<RangeT>, PredicateT>>
 428 make_filter_range(RangeT &&Range, PredicateT Pred) {
 429   using FilterIteratorT =
 430       filter_iterator<detail::IterOfRange<RangeT>, PredicateT>;
 431   return make_range(
 432       FilterIteratorT(std::begin(std::forward<RangeT>(Range)),
 433                       std::end(std::forward<RangeT>(Range)), Pred),
 434       FilterIteratorT(std::end(std::forward<RangeT>(Range)),
 435                       std::end(std::forward<RangeT>(Range)), Pred));
 436 }
 437
 438 /// A pseudo-iterator adaptor that is designed to implement "early increment"
 439 /// style loops.
 440 ///
 441 /// This is *not a normal iterator* and should almost never be used directly. It
 442 /// is intended primarily to be used with range based for loops and some range
 443 /// algorithms.
 444 ///
 445 /// The iterator isn't quite an `OutputIterator` or an `InputIterator` but
 446 /// somewhere between them. The constraints of these iterators are:
 447 ///
 448 /// - On construction or after being incremented, it is comparable and
 449 ///   dereferencable. It is *not* incrementable.
 450 /// - After being dereferenced, it is neither comparable nor dereferencable, it
 451 ///   is only incrementable.
 452 ///
 453 /// This means you can only dereference the iterator once, and you can only
 454 /// increment it once between dereferences.
 455 template <typename WrappedIteratorT>
 456 class early_inc_iterator_impl
 457     : public iterator_adaptor_base<early_inc_iterator_impl<WrappedIteratorT>,
 458                                    WrappedIteratorT, std::input_iterator_tag> {
 459   using BaseT =
 460       iterator_adaptor_base<early_inc_iterator_impl<WrappedIteratorT>,
 461                             WrappedIteratorT, std::input_iterator_tag>;
 462
 463   using PointerT = typename std::iterator_traits<WrappedIteratorT>::pointer;
 464
 465 protected:
 466 #if LLVM_ENABLE_ABI_BREAKING_CHECKS
 467   bool IsEarlyIncremented = false;
 468 #endif
 469
 470 public:
 471   early_inc_iterator_impl(WrappedIteratorT I) : BaseT(I) {}
 472
 473   using BaseT::operator*;
 474   typename BaseT::reference operator*() {
 475 #if LLVM_ENABLE_ABI_BREAKING_CHECKS
 476     assert(!IsEarlyIncremented && "Cannot dereference twice!");
 477     IsEarlyIncremented = true;
 478 #endif
 479     return *(this->I)++;
 480   }
 481
 482   using BaseT::operator++;
 483   early_inc_iterator_impl &operator++() {
 484 #if LLVM_ENABLE_ABI_BREAKING_CHECKS
 485     assert(IsEarlyIncremented && "Cannot increment before dereferencing!");
 486     IsEarlyIncremented = false;
 487 #endif
 488     return *this;
 489   }
 490
 491   using BaseT::operator==;
 492   bool operator==(const early_inc_iterator_impl &RHS) const {
 493 #if LLVM_ENABLE_ABI_BREAKING_CHECKS
 494     assert(!IsEarlyIncremented && "Cannot compare after dereferencing!");
 495 #endif
 496     return BaseT::operator==(RHS);
 497   }
 498 };
 499
 500 /// Make a range that does early increment to allow mutation of the underlying
 501 /// range without disrupting iteration.
 502 ///
 503 /// The underlying iterator will be incremented immediately after it is
 504 /// dereferenced, allowing deletion of the current node or insertion of nodes to
 505 /// not disrupt iteration provided they do not invalidate the *next* iterator --
 506 /// the current iterator can be invalidated.
 507 ///
 508 /// This requires a very exact pattern of use that is only really suitable to
 509 /// range based for loops and other range algorithms that explicitly guarantee
 510 /// to dereference exactly once each element, and to increment exactly once each
 511 /// element.
 512 template <typename RangeT>
 513 iterator_range<early_inc_iterator_impl<detail::IterOfRange<RangeT>>>
 514 make_early_inc_range(RangeT &&Range) {
 515   using EarlyIncIteratorT =
 516       early_inc_iterator_impl<detail::IterOfRange<RangeT>>;
 517   return make_range(EarlyIncIteratorT(std::begin(std::forward<RangeT>(Range))),
 518                     EarlyIncIteratorT(std::end(std::forward<RangeT>(Range))));
 519 }
 520
 521 // forward declarations required by zip_shortest/zip_first/zip_longest
 522 template <typename R, typename UnaryPredicate>
 523 bool all_of(R &&range, UnaryPredicate P);
 524 template <typename R, typename UnaryPredicate>
 525 bool any_of(R &&range, UnaryPredicate P);
 526
 527 template <size_t... I> struct index_sequence;
 528
 529 template <class... Ts> struct index_sequence_for;
 530
 531 namespace detail {
 532
 533 using std::declval;
 534
 535 // We have to alias this since inlining the actual type at the usage site
 536 // in the parameter list of iterator_facade_base<> below ICEs MSVC 2017.
 537 template<typename... Iters> struct ZipTupleType {
 538   using type = std::tuple<decltype(*declval<Iters>())...>;
 539 };
 540
 541 template <typename ZipType, typename... Iters>
 542 using zip_traits = iterator_facade_base<
 543     ZipType, typename std::common_type<std::bidirectional_iterator_tag,
 544                                        typename std::iterator_traits<
 545                                            Iters>::iterator_category...>::type,
 546     // ^ TODO: Implement random access methods.
 547     typename ZipTupleType<Iters...>::type,
 548     typename std::iterator_traits<typename std::tuple_element<
 549         0, std::tuple<Iters...>>::type>::difference_type,
 550     // ^ FIXME: This follows boost::make_zip_iterator's assumption that all
 551     // inner iterators have the same difference_type. It would fail if, for
 552     // instance, the second field's difference_type were non-numeric while the
 553     // first is.
 554     typename ZipTupleType<Iters...>::type *,
 555     typename ZipTupleType<Iters...>::type>;
 556
 557 template <typename ZipType, typename... Iters>
 558 struct zip_common : public zip_traits<ZipType, Iters...> {
 559   using Base = zip_traits<ZipType, Iters...>;
 560   using value_type = typename Base::value_type;
 561
 562   std::tuple<Iters...> iterators;
 563
 564 protected:
 565   template <size_t... Ns> value_type deref(index_sequence<Ns...>) const {
 566     return value_type(*std::get<Ns>(iterators)...);
 567   }
 568
 569   template <size_t... Ns>
 570   decltype(iterators) tup_inc(index_sequence<Ns...>) const {
 571     return std::tuple<Iters...>(std::next(std::get<Ns>(iterators))...);
 572   }
 573
 574   template <size_t... Ns>
 575   decltype(iterators) tup_dec(index_sequence<Ns...>) const {
 576     return std::tuple<Iters...>(std::prev(std::get<Ns>(iterators))...);
 577   }
 578
 579 public:
 580   zip_common(Iters &&... ts) : iterators(std::forward<Iters>(ts)...) {}
 581
 582   value_type operator*() { return deref(index_sequence_for<Iters...>{}); }
 583
 584   const value_type operator*() const {
 585     return deref(index_sequence_for<Iters...>{});
 586   }
 587
 588   ZipType &operator++() {
 589     iterators = tup_inc(index_sequence_for<Iters...>{});
 590     return *reinterpret_cast<ZipType *>(this);
 591   }
 592
 593   ZipType &operator--() {
 594     static_assert(Base::IsBidirectional,
 595                   "All inner iterators must be at least bidirectional.");
 596     iterators = tup_dec(index_sequence_for<Iters...>{});
 597     return *reinterpret_cast<ZipType *>(this);
 598   }
 599 };
 600
 601 template <typename... Iters>
 602 struct zip_first : public zip_common<zip_first<Iters...>, Iters...> {
 603   using Base = zip_common<zip_first<Iters...>, Iters...>;
 604
 605   bool operator==(const zip_first<Iters...> &other) const {
 606     return std::get<0>(this->iterators) == std::get<0>(other.iterators);
 607   }
 608
 609   zip_first(Iters &&... ts) : Base(std::forward<Iters>(ts)...) {}
 610 };
 611
 612 template <typename... Iters>
 613 class zip_shortest : public zip_common<zip_shortest<Iters...>, Iters...> {
 614   template <size_t... Ns>
 615   bool test(const zip_shortest<Iters...> &other, index_sequence<Ns...>) const {
 616     return all_of(std::initializer_list<bool>{std::get<Ns>(this->iterators) !=
 617                                               std::get<Ns>(other.iterators)...},
 618                   identity<bool>{});
 619   }
 620
 621 public:
 622   using Base = zip_common<zip_shortest<Iters...>, Iters...>;
 623
 624   zip_shortest(Iters &&... ts) : Base(std::forward<Iters>(ts)...) {}
 625
 626   bool operator==(const zip_shortest<Iters...> &other) const {
 627     return !test(other, index_sequence_for<Iters...>{});
 628   }
 629 };
 630
 631 template <template <typename...> class ItType, typename... Args> class zippy {
 632 public:
 633   using iterator = ItType<decltype(std::begin(std::declval<Args>()))...>;
 634   using iterator_category = typename iterator::iterator_category;
 635   using value_type = typename iterator::value_type;
 636   using difference_type = typename iterator::difference_type;
 637   using pointer = typename iterator::pointer;
 638   using reference = typename iterator::reference;
 639
 640 private:
 641   std::tuple<Args...> ts;
 642
 643   template <size_t... Ns> iterator begin_impl(index_sequence<Ns...>) const {
 644     return iterator(std::begin(std::get<Ns>(ts))...);
 645   }
 646   template <size_t... Ns> iterator end_impl(index_sequence<Ns...>) const {
 647     return iterator(std::end(std::get<Ns>(ts))...);
 648   }
 649
 650 public:
 651   zippy(Args &&... ts_) : ts(std::forward<Args>(ts_)...) {}
 652
 653   iterator begin() const { return begin_impl(index_sequence_for<Args...>{}); }
 654   iterator end() const { return end_impl(index_sequence_for<Args...>{}); }
 655 };
 656
 657 } // end namespace detail
 658
 659 /// zip iterator for two or more iteratable types.
 660 template <typename T, typename U, typename... Args>
 661 detail::zippy<detail::zip_shortest, T, U, Args...> zip(T &&t, U &&u,
 662                                                        Args &&... args) {
 663   return detail::zippy<detail::zip_shortest, T, U, Args...>(
 664       std::forward<T>(t), std::forward<U>(u), std::forward<Args>(args)...);
 665 }
 666
 667 /// zip iterator that, for the sake of efficiency, assumes the first iteratee to
 668 /// be the shortest.
 669 template <typename T, typename U, typename... Args>
 670 detail::zippy<detail::zip_first, T, U, Args...> zip_first(T &&t, U &&u,
 671                                                           Args &&... args) {
 672   return detail::zippy<detail::zip_first, T, U, Args...>(
 673       std::forward<T>(t), std::forward<U>(u), std::forward<Args>(args)...);
 674 }
 675
 676 namespace detail {
 677 template <typename Iter>
 678 static Iter next_or_end(const Iter &I, const Iter &End) {
 679   if (I == End)
 680     return End;
 681   return std::next(I);
 682 }
 683
 684 template <typename Iter>
 685 static auto deref_or_none(const Iter &I, const Iter &End)
 686     -> llvm::Optional<typename std::remove_const<
 687         typename std::remove_reference<decltype(*I)>::type>::type> {
 688   if (I == End)
 689     return None;
 690   return *I;
 691 }
 692
 693 template <typename Iter> struct ZipLongestItemType {
 694   using type =
 695       llvm::Optional<typename std::remove_const<typename std::remove_reference<
 696           decltype(*std::declval<Iter>())>::type>::type>;
 697 };
 698
 699 template <typename... Iters> struct ZipLongestTupleType {
 700   using type = std::tuple<typename ZipLongestItemType<Iters>::type...>;
 701 };
 702
 703 template <typename... Iters>
 704 class zip_longest_iterator
 705     : public iterator_facade_base<
 706           zip_longest_iterator<Iters...>,
 707           typename std::common_type<
 708               std::forward_iterator_tag,
 709               typename std::iterator_traits<Iters>::iterator_category...>::type,
 710           typename ZipLongestTupleType<Iters...>::type,
 711           typename std::iterator_traits<typename std::tuple_element<
 712               0, std::tuple<Iters...>>::type>::difference_type,
 713           typename ZipLongestTupleType<Iters...>::type *,
 714           typename ZipLongestTupleType<Iters...>::type> {
 715 public:
 716   using value_type = typename ZipLongestTupleType<Iters...>::type;
 717
 718 private:
 719   std::tuple<Iters...> iterators;
 720   std::tuple<Iters...> end_iterators;
 721
 722   template <size_t... Ns>
 723   bool test(const zip_longest_iterator<Iters...> &other,
 724             index_sequence<Ns...>) const {
 725     return llvm::any_of(
 726         std::initializer_list<bool>{std::get<Ns>(this->iterators) !=
 727                                     std::get<Ns>(other.iterators)...},
 728         identity<bool>{});
 729   }
 730
 731   template <size_t... Ns> value_type deref(index_sequence<Ns...>) const {
 732     return value_type(
 733         deref_or_none(std::get<Ns>(iterators), std::get<Ns>(end_iterators))...);
 734   }
 735
 736   template <size_t... Ns>
 737   decltype(iterators) tup_inc(index_sequence<Ns...>) const {
 738     return std::tuple<Iters...>(
 739         next_or_end(std::get<Ns>(iterators), std::get<Ns>(end_iterators))...);
 740   }
 741
 742 public:
 743   zip_longest_iterator(std::pair<Iters &&, Iters &&>... ts)
 744       : iterators(std::forward<Iters>(ts.first)...),
 745         end_iterators(std::forward<Iters>(ts.second)...) {}
 746
 747   value_type operator*() { return deref(index_sequence_for<Iters...>{}); }
 748
 749   value_type operator*() const { return deref(index_sequence_for<Iters...>{}); }
 750
 751   zip_longest_iterator<Iters...> &operator++() {
 752     iterators = tup_inc(index_sequence_for<Iters...>{});
 753     return *this;
 754   }
 755
 756   bool operator==(const zip_longest_iterator<Iters...> &other) const {
 757     return !test(other, index_sequence_for<Iters...>{});
 758   }
 759 };
 760
 761 template <typename... Args> class zip_longest_range {
 762 public:
 763   using iterator =
 764       zip_longest_iterator<decltype(adl_begin(std::declval<Args>()))...>;
 765   using iterator_category = typename iterator::iterator_category;
 766   using value_type = typename iterator::value_type;
 767   using difference_type = typename iterator::difference_type;
 768   using pointer = typename iterator::pointer;
 769   using reference = typename iterator::reference;
 770
 771 private:
 772   std::tuple<Args...> ts;
 773
 774   template <size_t... Ns> iterator begin_impl(index_sequence<Ns...>) const {
 775     return iterator(std::make_pair(adl_begin(std::get<Ns>(ts)),
 776                                    adl_end(std::get<Ns>(ts)))...);
 777   }
 778
 779   template <size_t... Ns> iterator end_impl(index_sequence<Ns...>) const {
 780     return iterator(std::make_pair(adl_end(std::get<Ns>(ts)),
 781                                    adl_end(std::get<Ns>(ts)))...);
 782   }
 783
 784 public:
 785   zip_longest_range(Args &&... ts_) : ts(std::forward<Args>(ts_)...) {}
 786
 787   iterator begin() const { return begin_impl(index_sequence_for<Args...>{}); }
 788   iterator end() const { return end_impl(index_sequence_for<Args...>{}); }
 789 };
 790 } // namespace detail
 791
 792 /// Iterate over two or more iterators at the same time. Iteration continues
 793 /// until all iterators reach the end. The llvm::Optional only contains a value
 794 /// if the iterator has not reached the end.
 795 template <typename T, typename U, typename... Args>
 796 detail::zip_longest_range<T, U, Args...> zip_longest(T &&t, U &&u,
 797                                                      Args &&... args) {
 798   return detail::zip_longest_range<T, U, Args...>(
 799       std::forward<T>(t), std::forward<U>(u), std::forward<Args>(args)...);
 800 }
 801
 802 /// Iterator wrapper that concatenates sequences together.
 803 ///
 804 /// This can concatenate different iterators, even with different types, into
 805 /// a single iterator provided the value types of all the concatenated
 806 /// iterators expose `reference` and `pointer` types that can be converted to
 807 /// `ValueT &` and `ValueT *` respectively. It doesn't support more
 808 /// interesting/customized pointer or reference types.
 809 ///
 810 /// Currently this only supports forward or higher iterator categories as
 811 /// inputs and always exposes a forward iterator interface.
 812 template <typename ValueT, typename... IterTs>
 813 class concat_iterator
 814     : public iterator_facade_base<concat_iterator<ValueT, IterTs...>,
 815                                   std::forward_iterator_tag, ValueT> {
 816   using BaseT = typename concat_iterator::iterator_facade_base;
 817
 818   /// We store both the current and end iterators for each concatenated
 819   /// sequence in a tuple of pairs.
 820   ///
 821   /// Note that something like iterator_range seems nice at first here, but the
 822   /// range properties are of little benefit and end up getting in the way
 823   /// because we need to do mutation on the current iterators.
 824   std::tuple<IterTs...> Begins;
 825   std::tuple<IterTs...> Ends;
 826
 827   /// Attempts to increment a specific iterator.
 828   ///
 829   /// Returns true if it was able to increment the iterator. Returns false if
 830   /// the iterator is already at the end iterator.
 831   template <size_t Index> bool incrementHelper() {
 832     auto &Begin = std::get<Index>(Begins);
 833     auto &End = std::get<Index>(Ends);
 834     if (Begin == End)
 835       return false;
 836
 837     ++Begin;
 838     return true;
 839   }
 840
 841   /// Increments the first non-end iterator.
 842   ///
 843   /// It is an error to call this with all iterators at the end.
 844   template <size_t... Ns> void increment(index_sequence<Ns...>) {
 845     // Build a sequence of functions to increment each iterator if possible.
 846     bool (concat_iterator::*IncrementHelperFns[])() = {
 847         &concat_iterator::incrementHelper<Ns>...};
 848
 849     // Loop over them, and stop as soon as we succeed at incrementing one.
 850     for (auto &IncrementHelperFn : IncrementHelperFns)
 851       if ((this->*IncrementHelperFn)())
 852         return;
 853
 854     llvm_unreachable("Attempted to increment an end concat iterator!");
 855   }
 856
 857   /// Returns null if the specified iterator is at the end. Otherwise,
 858   /// dereferences the iterator and returns the address of the resulting
 859   /// reference.
 860   template <size_t Index> ValueT *getHelper() const {
 861     auto &Begin = std::get<Index>(Begins);
 862     auto &End = std::get<Index>(Ends);
 863     if (Begin == End)
 864       return nullptr;
 865
 866     return &*Begin;
 867   }
 868
 869   /// Finds the first non-end iterator, dereferences, and returns the resulting
 870   /// reference.
 871   ///
 872   /// It is an error to call this with all iterators at the end.
 873   template <size_t... Ns> ValueT &get(index_sequence<Ns...>) const {
 874     // Build a sequence of functions to get from iterator if possible.
 875     ValueT *(concat_iterator::*GetHelperFns[])() const = {
 876         &concat_iterator::getHelper<Ns>...};
 877
 878     // Loop over them, and return the first result we find.
 879     for (auto &GetHelperFn : GetHelperFns)
 880       if (ValueT *P = (this->*GetHelperFn)())
 881         return *P;
 882
 883     llvm_unreachable("Attempted to get a pointer from an end concat iterator!");
 884   }
 885
 886 public:
 887   /// Constructs an iterator from a squence of ranges.
 888   ///
 889   /// We need the full range to know how to switch between each of the
 890   /// iterators.
 891   template <typename... RangeTs>
 892   explicit concat_iterator(RangeTs &&... Ranges)
 893       : Begins(std::begin(Ranges)...), Ends(std::end(Ranges)...) {}
 894
 895   using BaseT::operator++;
 896
 897   concat_iterator &operator++() {
 898     increment(index_sequence_for<IterTs...>());
 899     return *this;
 900   }
 901
 902   ValueT &operator*() const { return get(index_sequence_for<IterTs...>()); }
 903
 904   bool operator==(const concat_iterator &RHS) const {
 905     return Begins == RHS.Begins && Ends == RHS.Ends;
 906   }
 907 };
 908
 909 namespace detail {
 910
 911 /// Helper to store a sequence of ranges being concatenated and access them.
 912 ///
 913 /// This is designed to facilitate providing actual storage when temporaries
 914 /// are passed into the constructor such that we can use it as part of range
 915 /// based for loops.
 916 template <typename ValueT, typename... RangeTs> class concat_range {
 917 public:
 918   using iterator =
 919       concat_iterator<ValueT,
 920                       decltype(std::begin(std::declval<RangeTs &>()))...>;
 921
 922 private:
 923   std::tuple<RangeTs...> Ranges;
 924
 925   template <size_t... Ns> iterator begin_impl(index_sequence<Ns...>) {
 926     return iterator(std::get<Ns>(Ranges)...);
 927   }
 928   template <size_t... Ns> iterator end_impl(index_sequence<Ns...>) {
 929     return iterator(make_range(std::end(std::get<Ns>(Ranges)),
 930                                std::end(std::get<Ns>(Ranges)))...);
 931   }
 932
 933 public:
 934   concat_range(RangeTs &&... Ranges)
 935       : Ranges(std::forward<RangeTs>(Ranges)...) {}
 936
 937   iterator begin() { return begin_impl(index_sequence_for<RangeTs...>{}); }
 938   iterator end() { return end_impl(index_sequence_for<RangeTs...>{}); }
 939 };
 940
 941 } // end namespace detail
 942
 943 /// Concatenated range across two or more ranges.
 944 ///
 945 /// The desired value type must be explicitly specified.
 946 template <typename ValueT, typename... RangeTs>
 947 detail::concat_range<ValueT, RangeTs...> concat(RangeTs &&... Ranges) {
 948   static_assert(sizeof...(RangeTs) > 1,
 949                 "Need more than one range to concatenate!");
 950   return detail::concat_range<ValueT, RangeTs...>(
 951       std::forward<RangeTs>(Ranges)...);
 952 }
 953
 954 //===----------------------------------------------------------------------===//
 955 //     Extra additions to <utility>
 956 //===----------------------------------------------------------------------===//
 957
 958 /// Function object to check whether the first component of a std::pair
 959 /// compares less than the first component of another std::pair.
 960 struct less_first {
 961   template <typename T> bool operator()(const T &lhs, const T &rhs) const {
 962     return lhs.first < rhs.first;
 963   }
 964 };
 965
 966 /// Function object to check whether the second component of a std::pair
 967 /// compares less than the second component of another std::pair.
 968 struct less_second {
 969   template <typename T> bool operator()(const T &lhs, const T &rhs) const {
 970     return lhs.second < rhs.second;
 971   }
 972 };
 973
 974 /// \brief Function object to apply a binary function to the first component of
 975 /// a std::pair.
 976 template<typename FuncTy>
 977 struct on_first {
 978   FuncTy func;
 979
 980   template <typename T>
 981   auto operator()(const T &lhs, const T &rhs) const
 982       -> decltype(func(lhs.first, rhs.first)) {
 983     return func(lhs.first, rhs.first);
 984   }
 985 };
 986
 987 // A subset of N3658. More stuff can be added as-needed.
 988
 989 /// Represents a compile-time sequence of integers.
 990 template <class T, T... I> struct integer_sequence {
 991   using value_type = T;
 992
 993   static constexpr size_t size() { return sizeof...(I); }
 994 };
 995
 996 /// Alias for the common case of a sequence of size_ts.
 997 template <size_t... I>
 998 struct index_sequence : integer_sequence<std::size_t, I...> {};
 999
1000 template <std::size_t N, std::size_t... I>
1001 struct build_index_impl : build_index_impl<N - 1, N - 1, I...> {};
1002 template <std::size_t... I>
1003 struct build_index_impl<0, I...> : index_sequence<I...> {};
1004
1005 /// Creates a compile-time integer sequence for a parameter pack.
1006 template <class... Ts>
1007 struct index_sequence_for : build_index_impl<sizeof...(Ts)> {};
1008
1009 /// Utility type to build an inheritance chain that makes it easy to rank
1010 /// overload candidates.
1011 template <int N> struct rank : rank<N - 1> {};
1012 template <> struct rank<0> {};
1013
1014 /// traits class for checking whether type T is one of any of the given
1015 /// types in the variadic list.
1016 template <typename T, typename... Ts> struct is_one_of {
1017   static const bool value = false;
1018 };
1019
1020 template <typename T, typename U, typename... Ts>
1021 struct is_one_of<T, U, Ts...> {
1022   static const bool value =
1023       std::is_same<T, U>::value || is_one_of<T, Ts...>::value;
1024 };
1025
1026 /// traits class for checking whether type T is a base class for all
1027 ///  the given types in the variadic list.
1028 template <typename T, typename... Ts> struct are_base_of {
1029   static const bool value = true;
1030 };
1031
1032 template <typename T, typename U, typename... Ts>
1033 struct are_base_of<T, U, Ts...> {
1034   static const bool value =
1035       std::is_base_of<T, U>::value && are_base_of<T, Ts...>::value;
1036 };
1037
1038 //===----------------------------------------------------------------------===//
1039 //     Extra additions for arrays
1040 //===----------------------------------------------------------------------===//
1041
1042 /// Find the length of an array.
1043 template <class T, std::size_t N>
1044 constexpr inline size_t array_lengthof(T (&)[N]) {
1045   return N;
1046 }
1047
1048 /// Adapt std::less<T> for array_pod_sort.
1049 template<typename T>
1050 inline int array_pod_sort_comparator(const void *P1, const void *P2) {
1051   if (std::less<T>()(*reinterpret_cast<const T*>(P1),
1052                      *reinterpret_cast<const T*>(P2)))
1053     return -1;
1054   if (std::less<T>()(*reinterpret_cast<const T*>(P2),
1055                      *reinterpret_cast<const T*>(P1)))
1056     return 1;
1057   return 0;
1058 }
1059
1060 /// get_array_pod_sort_comparator - This is an internal helper function used to
1061 /// get type deduction of T right.
1062 template<typename T>
1063 inline int (*get_array_pod_sort_comparator(const T &))
1064              (const void*, const void*) {
1065   return array_pod_sort_comparator<T>;
1066 }
1067
1068 /// array_pod_sort - This sorts an array with the specified start and end
1069 /// extent.  This is just like std::sort, except that it calls qsort instead of
1070 /// using an inlined template.  qsort is slightly slower than std::sort, but
1071 /// most sorts are not performance critical in LLVM and std::sort has to be
1072 /// template instantiated for each type, leading to significant measured code
1073 /// bloat.  This function should generally be used instead of std::sort where
1074 /// possible.
1075 ///
1076 /// This function assumes that you have simple POD-like types that can be
1077 /// compared with std::less and can be moved with memcpy.  If this isn't true,
1078 /// you should use std::sort.
1079 ///
1080 /// NOTE: If qsort_r were portable, we could allow a custom comparator and
1081 /// default to std::less.
1082 template<class IteratorTy>
1083 inline void array_pod_sort(IteratorTy Start, IteratorTy End) {
1084   // Don't inefficiently call qsort with one element or trigger undefined
1085   // behavior with an empty sequence.
1086   auto NElts = End - Start;
1087   if (NElts <= 1) return;
1088 #ifdef EXPENSIVE_CHECKS
1089   std::mt19937 Generator(std::random_device{}());
1090   std::shuffle(Start, End, Generator);
1091 #endif
1092   qsort(&*Start, NElts, sizeof(*Start), get_array_pod_sort_comparator(*Start));
1093 }
1094
1095 template <class IteratorTy>
1096 inline void array_pod_sort(
1097     IteratorTy Start, IteratorTy End,
1098     int (*Compare)(
1099         const typename std::iterator_traits<IteratorTy>::value_type *,
1100         const typename std::iterator_traits<IteratorTy>::value_type *)) {
1101   // Don't inefficiently call qsort with one element or trigger undefined
1102   // behavior with an empty sequence.
1103   auto NElts = End - Start;
1104   if (NElts <= 1) return;
1105 #ifdef EXPENSIVE_CHECKS
1106   std::mt19937 Generator(std::random_device{}());
1107   std::shuffle(Start, End, Generator);
1108 #endif
1109   qsort(&*Start, NElts, sizeof(*Start),
1110         reinterpret_cast<int (*)(const void *, const void *)>(Compare));
1111 }
1112
1113 // Provide wrappers to std::sort which shuffle the elements before sorting
1114 // to help uncover non-deterministic behavior (PR35135).
1115 template <typename IteratorTy>
1116 inline void sort(IteratorTy Start, IteratorTy End) {
1117 #ifdef EXPENSIVE_CHECKS
1118   std::mt19937 Generator(std::random_device{}());
1119   std::shuffle(Start, End, Generator);
1120 #endif
1121   std::sort(Start, End);
1122 }
1123
1124 template <typename Container> inline void sort(Container &&C) {
1125   llvm::sort(adl_begin(C), adl_end(C));
1126 }
1127
1128 template <typename IteratorTy, typename Compare>
1129 inline void sort(IteratorTy Start, IteratorTy End, Compare Comp) {
1130 #ifdef EXPENSIVE_CHECKS
1131   std::mt19937 Generator(std::random_device{}());
1132   std::shuffle(Start, End, Generator);
1133 #endif
1134   std::sort(Start, End, Comp);
1135 }
1136
1137 template <typename Container, typename Compare>
1138 inline void sort(Container &&C, Compare Comp) {
1139   llvm::sort(adl_begin(C), adl_end(C), Comp);
1140 }
1141
1142 //===----------------------------------------------------------------------===//
1143 //     Extra additions to <algorithm>
1144 //===----------------------------------------------------------------------===//
1145
1146 /// For a container of pointers, deletes the pointers and then clears the
1147 /// container.
1148 template<typename Container>
1149 void DeleteContainerPointers(Container &C) {
1150   for (auto V : C)
1151     delete V;
1152   C.clear();
1153 }
1154
1155 /// In a container of pairs (usually a map) whose second element is a pointer,
1156 /// deletes the second elements and then clears the container.
1157 template<typename Container>
1158 void DeleteContainerSeconds(Container &C) {
1159   for (auto &V : C)
1160     delete V.second;
1161   C.clear();
1162 }
1163
1164 /// Get the size of a range. This is a wrapper function around std::distance
1165 /// which is only enabled when the operation is O(1).
1166 template <typename R>
1167 auto size(R &&Range, typename std::enable_if<
1168                          std::is_same<typename std::iterator_traits<decltype(
1169                                           Range.begin())>::iterator_category,
1170                                       std::random_access_iterator_tag>::value,
1171                          void>::type * = nullptr)
1172     -> decltype(std::distance(Range.begin(), Range.end())) {
1173   return std::distance(Range.begin(), Range.end());
1174 }
1175
1176 /// Provide wrappers to std::for_each which take ranges instead of having to
1177 /// pass begin/end explicitly.
1178 template <typename R, typename UnaryPredicate>
1179 UnaryPredicate for_each(R &&Range, UnaryPredicate P) {
1180   return std::for_each(adl_begin(Range), adl_end(Range), P);
1181 }
1182
1183 /// Provide wrappers to std::all_of which take ranges instead of having to pass
1184 /// begin/end explicitly.
1185 template <typename R, typename UnaryPredicate>
1186 bool all_of(R &&Range, UnaryPredicate P) {
1187   return std::all_of(adl_begin(Range), adl_end(Range), P);
1188 }
1189
1190 /// Provide wrappers to std::any_of which take ranges instead of having to pass
1191 /// begin/end explicitly.
1192 template <typename R, typename UnaryPredicate>
1193 bool any_of(R &&Range, UnaryPredicate P) {
1194   return std::any_of(adl_begin(Range), adl_end(Range), P);
1195 }
1196
1197 /// Provide wrappers to std::none_of which take ranges instead of having to pass
1198 /// begin/end explicitly.
1199 template <typename R, typename UnaryPredicate>
1200 bool none_of(R &&Range, UnaryPredicate P) {
1201   return std::none_of(adl_begin(Range), adl_end(Range), P);
1202 }
1203
1204 /// Provide wrappers to std::find which take ranges instead of having to pass
1205 /// begin/end explicitly.
1206 template <typename R, typename T>
1207 auto find(R &&Range, const T &Val) -> decltype(adl_begin(Range)) {
1208   return std::find(adl_begin(Range), adl_end(Range), Val);
1209 }
1210
1211 /// Provide wrappers to std::find_if which take ranges instead of having to pass
1212 /// begin/end explicitly.
1213 template <typename R, typename UnaryPredicate>
1214 auto find_if(R &&Range, UnaryPredicate P) -> decltype(adl_begin(Range)) {
1215   return std::find_if(adl_begin(Range), adl_end(Range), P);
1216 }
1217
1218 template <typename R, typename UnaryPredicate>
1219 auto find_if_not(R &&Range, UnaryPredicate P) -> decltype(adl_begin(Range)) {
1220   return std::find_if_not(adl_begin(Range), adl_end(Range), P);
1221 }
1222
1223 /// Provide wrappers to std::remove_if which take ranges instead of having to
1224 /// pass begin/end explicitly.
1225 template <typename R, typename UnaryPredicate>
1226 auto remove_if(R &&Range, UnaryPredicate P) -> decltype(adl_begin(Range)) {
1227   return std::remove_if(adl_begin(Range), adl_end(Range), P);
1228 }
1229
1230 /// Provide wrappers to std::copy_if which take ranges instead of having to
1231 /// pass begin/end explicitly.
1232 template <typename R, typename OutputIt, typename UnaryPredicate>
1233 OutputIt copy_if(R &&Range, OutputIt Out, UnaryPredicate P) {
1234   return std::copy_if(adl_begin(Range), adl_end(Range), Out, P);
1235 }
1236
1237 template <typename R, typename OutputIt>
1238 OutputIt copy(R &&Range, OutputIt Out) {
1239   return std::copy(adl_begin(Range), adl_end(Range), Out);
1240 }
1241
1242 /// Wrapper function around std::find to detect if an element exists
1243 /// in a container.
1244 template <typename R, typename E>
1245 bool is_contained(R &&Range, const E &Element) {
1246   return std::find(adl_begin(Range), adl_end(Range), Element) != adl_end(Range);
1247 }
1248
1249 /// Wrapper function around std::count to count the number of times an element
1250 /// \p Element occurs in the given range \p Range.
1251 template <typename R, typename E>
1252 auto count(R &&Range, const E &Element) ->
1253     typename std::iterator_traits<decltype(adl_begin(Range))>::difference_type {
1254   return std::count(adl_begin(Range), adl_end(Range), Element);
1255 }
1256
1257 /// Wrapper function around std::count_if to count the number of times an
1258 /// element satisfying a given predicate occurs in a range.
1259 template <typename R, typename UnaryPredicate>
1260 auto count_if(R &&Range, UnaryPredicate P) ->
1261     typename std::iterator_traits<decltype(adl_begin(Range))>::difference_type {
1262   return std::count_if(adl_begin(Range), adl_end(Range), P);
1263 }
1264
1265 /// Wrapper function around std::transform to apply a function to a range and
1266 /// store the result elsewhere.
1267 template <typename R, typename OutputIt, typename UnaryPredicate>
1268 OutputIt transform(R &&Range, OutputIt d_first, UnaryPredicate P) {
1269   return std::transform(adl_begin(Range), adl_end(Range), d_first, P);
1270 }
1271
1272 /// Provide wrappers to std::partition which take ranges instead of having to
1273 /// pass begin/end explicitly.
1274 template <typename R, typename UnaryPredicate>
1275 auto partition(R &&Range, UnaryPredicate P) -> decltype(adl_begin(Range)) {
1276   return std::partition(adl_begin(Range), adl_end(Range), P);
1277 }
1278
1279 /// Provide wrappers to std::lower_bound which take ranges instead of having to
1280 /// pass begin/end explicitly.
1281 template <typename R, typename ForwardIt>
1282 auto lower_bound(R &&Range, ForwardIt I) -> decltype(adl_begin(Range)) {
1283   return std::lower_bound(adl_begin(Range), adl_end(Range), I);
1284 }
1285
1286 template <typename R, typename ForwardIt, typename Compare>
1287 auto lower_bound(R &&Range, ForwardIt I, Compare C)
1288     -> decltype(adl_begin(Range)) {
1289   return std::lower_bound(adl_begin(Range), adl_end(Range), I, C);
1290 }
1291
1292 /// Provide wrappers to std::upper_bound which take ranges instead of having to
1293 /// pass begin/end explicitly.
1294 template <typename R, typename ForwardIt>
1295 auto upper_bound(R &&Range, ForwardIt I) -> decltype(adl_begin(Range)) {
1296   return std::upper_bound(adl_begin(Range), adl_end(Range), I);
1297 }
1298
1299 template <typename R, typename ForwardIt, typename Compare>
1300 auto upper_bound(R &&Range, ForwardIt I, Compare C)
1301     -> decltype(adl_begin(Range)) {
1302   return std::upper_bound(adl_begin(Range), adl_end(Range), I, C);
1303 }
1304 /// Wrapper function around std::equal to detect if all elements
1305 /// in a container are same.
1306 template <typename R>
1307 bool is_splat(R &&Range) {
1308   size_t range_size = size(Range);
1309   return range_size != 0 && (range_size == 1 ||
1310          std::equal(adl_begin(Range) + 1, adl_end(Range), adl_begin(Range)));
1311 }
1312
1313 /// Given a range of type R, iterate the entire range and return a
1314 /// SmallVector with elements of the vector.  This is useful, for example,
1315 /// when you want to iterate a range and then sort the results.
1316 template <unsigned Size, typename R>
1317 SmallVector<typename std::remove_const<detail::ValueOfRange<R>>::type, Size>
1318 to_vector(R &&Range) {
1319   return {adl_begin(Range), adl_end(Range)};
1320 }
1321
1322 /// Provide a container algorithm similar to C++ Library Fundamentals v2's
1323 /// `erase_if` which is equivalent to:
1324 ///
1325 ///   C.erase(remove_if(C, pred), C.end());
1326 ///
1327 /// This version works for any container with an erase method call accepting
1328 /// two iterators.
1329 template <typename Container, typename UnaryPredicate>
1330 void erase_if(Container &C, UnaryPredicate P) {
1331   C.erase(remove_if(C, P), C.end());
1332 }
1333
1334 //===----------------------------------------------------------------------===//
1335 //     Extra additions to <memory>
1336 //===----------------------------------------------------------------------===//
1337
1338 // Implement make_unique according to N3656.
1339
1340 /// Constructs a `new T()` with the given args and returns a
1341 ///        `unique_ptr<T>` which owns the object.
1342 ///
1343 /// Example:
1344 ///
1345 ///     auto p = make_unique<int>();
1346 ///     auto p = make_unique<std::tuple<int, int>>(0, 1);
1347 template <class T, class... Args>
1348 typename std::enable_if<!std::is_array<T>::value, std::unique_ptr<T>>::type
1349 make_unique(Args &&... args) {
1350   return std::unique_ptr<T>(new T(std::forward<Args>(args)...));
1351 }
1352
1353 /// Constructs a `new T[n]` with the given args and returns a
1354 ///        `unique_ptr<T[]>` which owns the object.
1355 ///
1356 /// \param n size of the new array.
1357 ///
1358 /// Example:
1359 ///
1360 ///     auto p = make_unique<int[]>(2); // value-initializes the array with 0's.
1361 template <class T>
1362 typename std::enable_if<std::is_array<T>::value && std::extent<T>::value == 0,
1363                         std::unique_ptr<T>>::type
1364 make_unique(size_t n) {
1365   return std::unique_ptr<T>(new typename std::remove_extent<T>::type[n]());
1366 }
1367
1368 /// This function isn't used and is only here to provide better compile errors.
1369 template <class T, class... Args>
1370 typename std::enable_if<std::extent<T>::value != 0>::type
1371 make_unique(Args &&...) = delete;
1372
1373 struct FreeDeleter {
1374   void operator()(void* v) {
1375     ::free(v);
1376   }
1377 };
1378
1379 template<typename First, typename Second>
1380 struct pair_hash {
1381   size_t operator()(const std::pair<First, Second> &P) const {
1382     return std::hash<First>()(P.first) * 31 + std::hash<Second>()(P.second);
1383   }
1384 };
1385
1386 /// A functor like C++14's std::less<void> in its absence.
1387 struct less {
1388   template <typename A, typename B> bool operator()(A &&a, B &&b) const {
1389     return std::forward<A>(a) < std::forward<B>(b);
1390   }
1391 };
1392
1393 /// A functor like C++14's std::equal<void> in its absence.
1394 struct equal {
1395   template <typename A, typename B> bool operator()(A &&a, B &&b) const {
1396     return std::forward<A>(a) == std::forward<B>(b);
1397   }
1398 };
1399
1400 /// Binary functor that adapts to any other binary functor after dereferencing
1401 /// operands.
1402 template <typename T> struct deref {
1403   T func;
1404
1405   // Could be further improved to cope with non-derivable functors and
1406   // non-binary functors (should be a variadic template member function
1407   // operator()).
1408   template <typename A, typename B>
1409   auto operator()(A &lhs, B &rhs) const -> decltype(func(*lhs, *rhs)) {
1410     assert(lhs);
1411     assert(rhs);
1412     return func(*lhs, *rhs);
1413   }
1414 };
1415
1416 namespace detail {
1417
1418 template <typename R> class enumerator_iter;
1419
1420 template <typename R> struct result_pair {
1421   friend class enumerator_iter<R>;
1422
1423   result_pair() = default;
1424   result_pair(std::size_t Index, IterOfRange<R> Iter)
1425       : Index(Index), Iter(Iter) {}
1426
1427   result_pair<R> &operator=(const result_pair<R> &Other) {
1428     Index = Other.Index;
1429     Iter = Other.Iter;
1430     return *this;
1431   }
1432
1433   std::size_t index() const { return Index; }
1434   const ValueOfRange<R> &value() const { return *Iter; }
1435   ValueOfRange<R> &value() { return *Iter; }
1436
1437 private:
1438   std::size_t Index = std::numeric_limits<std::size_t>::max();
1439   IterOfRange<R> Iter;
1440 };
1441
1442 template <typename R>
1443 class enumerator_iter
1444     : public iterator_facade_base<
1445           enumerator_iter<R>, std::forward_iterator_tag, result_pair<R>,
1446           typename std::iterator_traits<IterOfRange<R>>::difference_type,
1447           typename std::iterator_traits<IterOfRange<R>>::pointer,
1448           typename std::iterator_traits<IterOfRange<R>>::reference> {
1449   using result_type = result_pair<R>;
1450
1451 public:
1452   explicit enumerator_iter(IterOfRange<R> EndIter)
1453       : Result(std::numeric_limits<size_t>::max(), EndIter) {}
1454
1455   enumerator_iter(std::size_t Index, IterOfRange<R> Iter)
1456       : Result(Index, Iter) {}
1457
1458   result_type &operator*() { return Result; }
1459   const result_type &operator*() const { return Result; }
1460
1461   enumerator_iter<R> &operator++() {
1462     assert(Result.Index != std::numeric_limits<size_t>::max());
1463     ++Result.Iter;
1464     ++Result.Index;
1465     return *this;
1466   }
1467
1468   bool operator==(const enumerator_iter<R> &RHS) const {
1469     // Don't compare indices here, only iterators.  It's possible for an end
1470     // iterator to have different indices depending on whether it was created
1471     // by calling std::end() versus incrementing a valid iterator.
1472     return Result.Iter == RHS.Result.Iter;
1473   }
1474
1475   enumerator_iter<R> &operator=(const enumerator_iter<R> &Other) {
1476     Result = Other.Result;
1477     return *this;
1478   }
1479
1480 private:
1481   result_type Result;
1482 };
1483
1484 template <typename R> class enumerator {
1485 public:
1486   explicit enumerator(R &&Range) : TheRange(std::forward<R>(Range)) {}
1487
1488   enumerator_iter<R> begin() {
1489     return enumerator_iter<R>(0, std::begin(TheRange));
1490   }
1491
1492   enumerator_iter<R> end() {
1493     return enumerator_iter<R>(std::end(TheRange));
1494   }
1495
1496 private:
1497   R TheRange;
1498 };
1499
1500 } // end namespace detail
1501
1502 /// Given an input range, returns a new range whose values are are pair (A,B)
1503 /// such that A is the 0-based index of the item in the sequence, and B is
1504 /// the value from the original sequence.  Example:
1505 ///
1506 /// std::vector<char> Items = {'A', 'B', 'C', 'D'};
1507 /// for (auto X : enumerate(Items)) {
1508 ///   printf("Item %d - %c\n", X.index(), X.value());
1509 /// }
1510 ///
1511 /// Output:
1512 ///   Item 0 - A
1513 ///   Item 1 - B
1514 ///   Item 2 - C
1515 ///   Item 3 - D
1516 ///
1517 template <typename R> detail::enumerator<R> enumerate(R &&TheRange) {
1518   return detail::enumerator<R>(std::forward<R>(TheRange));
1519 }
1520
1521 namespace detail {
1522
1523 template <typename F, typename Tuple, std::size_t... I>
1524 auto apply_tuple_impl(F &&f, Tuple &&t, index_sequence<I...>)
1525     -> decltype(std::forward<F>(f)(std::get<I>(std::forward<Tuple>(t))...)) {
1526   return std::forward<F>(f)(std::get<I>(std::forward<Tuple>(t))...);
1527 }
1528
1529 } // end namespace detail
1530
1531 /// Given an input tuple (a1, a2, ..., an), pass the arguments of the
1532 /// tuple variadically to f as if by calling f(a1, a2, ..., an) and
1533 /// return the result.
1534 template <typename F, typename Tuple>
1535 auto apply_tuple(F &&f, Tuple &&t) -> decltype(detail::apply_tuple_impl(
1536     std::forward<F>(f), std::forward<Tuple>(t),
1537     build_index_impl<
1538         std::tuple_size<typename std::decay<Tuple>::type>::value>{})) {
1539   using Indices = build_index_impl<
1540       std::tuple_size<typename std::decay<Tuple>::type>::value>;
1541
1542   return detail::apply_tuple_impl(std::forward<F>(f), std::forward<Tuple>(t),
1543                                   Indices{});
1544 }
1545
1546 /// Return true if the sequence [Begin, End) has exactly N items. Runs in O(N)
1547 /// time. Not meant for use with random-access iterators.
1548 template <typename IterTy>
1549 bool hasNItems(
1550     IterTy &&Begin, IterTy &&End, unsigned N,
1551     typename std::enable_if<
1552         !std::is_same<
1553             typename std::iterator_traits<typename std::remove_reference<
1554                 decltype(Begin)>::type>::iterator_category,
1555             std::random_access_iterator_tag>::value,
1556         void>::type * = nullptr) {
1557   for (; N; --N, ++Begin)
1558     if (Begin == End)
1559       return false; // Too few.
1560   return Begin == End;
1561 }
1562
1563 /// Return true if the sequence [Begin, End) has N or more items. Runs in O(N)
1564 /// time. Not meant for use with random-access iterators.
1565 template <typename IterTy>
1566 bool hasNItemsOrMore(
1567     IterTy &&Begin, IterTy &&End, unsigned N,
1568     typename std::enable_if<
1569         !std::is_same<
1570             typename std::iterator_traits<typename std::remove_reference<
1571                 decltype(Begin)>::type>::iterator_category,
1572             std::random_access_iterator_tag>::value,
1573         void>::type * = nullptr) {
1574   for (; N; --N, ++Begin)
1575     if (Begin == End)
1576       return false; // Too few.
1577   return true;
1578 }
1579
1580 } // end namespace llvm
1581
1582 #endif // LLVM_ADT_STLEXTRAS_H