include/llvm/ADT/STLExtras.h

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