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