contrib/llvm-project/llvm/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/iterator.h"
  21 #include "llvm/ADT/iterator_range.h"
  22 #include "llvm/Config/abi-breaking.h"
  23 #include "llvm/Support/ErrorHandling.h"
  24 #include <algorithm>
  25 #include <cassert>
  26 #include <cstddef>
  27 #include <cstdint>
  28 #include <cstdlib>
  29 #include <functional>
  30 #include <initializer_list>
  31 #include <iterator>
  32 #include <limits>
  33 #include <memory>
  34 #include <tuple>
  35 #include <type_traits>
  36 #include <utility>
  37
  38 #ifdef EXPENSIVE_CHECKS
  39 #include <random> // for std::mt19937
  40 #endif
  41
  42 namespace llvm {
  43
  44 // Only used by compiler if both template types are the same.  Useful when
  45 // using SFINAE to test for the existence of member functions.
  46 template <typename T, T> struct SameType;
  47
  48 namespace detail {
  49
  50 template <typename RangeT>
  51 using IterOfRange = decltype(std::begin(std::declval<RangeT &>()));
  52
  53 template <typename RangeT>
  54 using ValueOfRange = typename std::remove_reference<decltype(
  55     *std::begin(std::declval<RangeT &>()))>::type;
  56
  57 } // end namespace detail
  58
  59 //===----------------------------------------------------------------------===//
  60 //     Extra additions to <type_traits>
  61 //===----------------------------------------------------------------------===//
  62
  63 template <typename T>
  64 struct negation : std::integral_constant<bool, !bool(T::value)> {};
  65
  66 template <typename...> struct conjunction : std::true_type {};
  67 template <typename B1> struct conjunction<B1> : B1 {};
  68 template <typename B1, typename... Bn>
  69 struct conjunction<B1, Bn...>
  70     : std::conditional<bool(B1::value), conjunction<Bn...>, B1>::type {};
  71
  72 template <typename T> struct make_const_ptr {
  73   using type =
  74       typename std::add_pointer<typename std::add_const<T>::type>::type;
  75 };
  76
  77 template <typename T> struct make_const_ref {
  78   using type = typename std::add_lvalue_reference<
  79       typename std::add_const<T>::type>::type;
  80 };
  81
  82 /// Utilities for detecting if a given trait holds for some set of arguments
  83 /// 'Args'. For example, the given trait could be used to detect if a given type
  84 /// has a copy assignment operator:
  85 ///   template<class T>
  86 ///   using has_copy_assign_t = decltype(std::declval<T&>()
  87 ///                                                 = std::declval<const T&>());
  88 ///   bool fooHasCopyAssign = is_detected<has_copy_assign_t, FooClass>::value;
  89 namespace detail {
  90 template <typename...> using void_t = void;
  91 template <class, template <class...> class Op, class... Args> struct detector {
  92   using value_t = std::false_type;
  93 };
  94 template <template <class...> class Op, class... Args>
  95 struct detector<void_t<Op<Args...>>, Op, Args...> {
  96   using value_t = std::true_type;
  97 };
  98 } // end namespace detail
  99
 100 template <template <class...> class Op, class... Args>
 101 using is_detected = typename detail::detector<void, Op, Args...>::value_t;
 102
 103 /// Check if a Callable type can be invoked with the given set of arg types.
 104 namespace detail {
 105 template <typename Callable, typename... Args>
 106 using is_invocable =
 107     decltype(std::declval<Callable &>()(std::declval<Args>()...));
 108 } // namespace detail
 109
 110 template <typename Callable, typename... Args>
 111 using is_invocable = is_detected<detail::is_invocable, Callable, Args...>;
 112
 113 /// This class provides various trait information about a callable object.
 114 ///   * To access the number of arguments: Traits::num_args
 115 ///   * To access the type of an argument: Traits::arg_t<Index>
 116 ///   * To access the type of the result:  Traits::result_t
 117 template <typename T, bool isClass = std::is_class<T>::value>
 118 struct function_traits : public function_traits<decltype(&T::operator())> {};
 119
 120 /// Overload for class function types.
 121 template <typename ClassType, typename ReturnType, typename... Args>
 122 struct function_traits<ReturnType (ClassType::*)(Args...) const, false> {
 123   /// The number of arguments to this function.
 124   enum { num_args = sizeof...(Args) };
 125
 126   /// The result type of this function.
 127   using result_t = ReturnType;
 128
 129   /// The type of an argument to this function.
 130   template <size_t Index>
 131   using arg_t = typename std::tuple_element<Index, std::tuple<Args...>>::type;
 132 };
 133 /// Overload for class function types.
 134 template <typename ClassType, typename ReturnType, typename... Args>
 135 struct function_traits<ReturnType (ClassType::*)(Args...), false>
 136     : function_traits<ReturnType (ClassType::*)(Args...) const> {};
 137 /// Overload for non-class function types.
 138 template <typename ReturnType, typename... Args>
 139 struct function_traits<ReturnType (*)(Args...), false> {
 140   /// The number of arguments to this function.
 141   enum { num_args = sizeof...(Args) };
 142
 143   /// The result type of this function.
 144   using result_t = ReturnType;
 145
 146   /// The type of an argument to this function.
 147   template <size_t i>
 148   using arg_t = typename std::tuple_element<i, std::tuple<Args...>>::type;
 149 };
 150 /// Overload for non-class function type references.
 151 template <typename ReturnType, typename... Args>
 152 struct function_traits<ReturnType (&)(Args...), false>
 153     : public function_traits<ReturnType (*)(Args...)> {};
 154
 155 //===----------------------------------------------------------------------===//
 156 //     Extra additions to <functional>
 157 //===----------------------------------------------------------------------===//
 158
 159 template <class Ty> struct identity {
 160   using argument_type = Ty;
 161
 162   Ty &operator()(Ty &self) const {
 163     return self;
 164   }
 165   const Ty &operator()(const Ty &self) const {
 166     return self;
 167   }
 168 };
 169
 170 /// An efficient, type-erasing, non-owning reference to a callable. This is
 171 /// intended for use as the type of a function parameter that is not used
 172 /// after the function in question returns.
 173 ///
 174 /// This class does not own the callable, so it is not in general safe to store
 175 /// a function_ref.
 176 template<typename Fn> class function_ref;
 177
 178 template<typename Ret, typename ...Params>
 179 class function_ref<Ret(Params...)> {
 180   Ret (*callback)(intptr_t callable, Params ...params) = nullptr;
 181   intptr_t callable;
 182
 183   template<typename Callable>
 184   static Ret callback_fn(intptr_t callable, Params ...params) {
 185     return (*reinterpret_cast<Callable*>(callable))(
 186         std::forward<Params>(params)...);
 187   }
 188
 189 public:
 190   function_ref() = default;
 191   function_ref(std::nullptr_t) {}
 192
 193   template <typename Callable>
 194   function_ref(
 195       Callable &&callable,
 196       std::enable_if_t<
 197           !std::is_same<std::remove_cv_t<std::remove_reference_t<Callable>>,
 198                         function_ref>::value> * = nullptr)
 199       : callback(callback_fn<typename std::remove_reference<Callable>::type>),
 200         callable(reinterpret_cast<intptr_t>(&callable)) {}
 201
 202   Ret operator()(Params ...params) const {
 203     return callback(callable, std::forward<Params>(params)...);
 204   }
 205
 206   explicit operator bool() const { return callback; }
 207 };
 208
 209 // deleter - Very very very simple method that is used to invoke operator
 210 // delete on something.  It is used like this:
 211 //
 212 //   for_each(V.begin(), B.end(), deleter<Interval>);
 213 template <class T>
 214 inline void deleter(T *Ptr) {
 215   delete Ptr;
 216 }
 217
 218 //===----------------------------------------------------------------------===//
 219 //     Extra additions to <iterator>
 220 //===----------------------------------------------------------------------===//
 221
 222 namespace adl_detail {
 223
 224 using std::begin;
 225
 226 template <typename ContainerTy>
 227 decltype(auto) adl_begin(ContainerTy &&container) {
 228   return begin(std::forward<ContainerTy>(container));
 229 }
 230
 231 using std::end;
 232
 233 template <typename ContainerTy>
 234 decltype(auto) adl_end(ContainerTy &&container) {
 235   return end(std::forward<ContainerTy>(container));
 236 }
 237
 238 using std::swap;
 239
 240 template <typename T>
 241 void adl_swap(T &&lhs, T &&rhs) noexcept(noexcept(swap(std::declval<T>(),
 242                                                        std::declval<T>()))) {
 243   swap(std::forward<T>(lhs), std::forward<T>(rhs));
 244 }
 245
 246 } // end namespace adl_detail
 247
 248 template <typename ContainerTy>
 249 decltype(auto) adl_begin(ContainerTy &&container) {
 250   return adl_detail::adl_begin(std::forward<ContainerTy>(container));
 251 }
 252
 253 template <typename ContainerTy>
 254 decltype(auto) adl_end(ContainerTy &&container) {
 255   return adl_detail::adl_end(std::forward<ContainerTy>(container));
 256 }
 257
 258 template <typename T>
 259 void adl_swap(T &&lhs, T &&rhs) noexcept(
 260     noexcept(adl_detail::adl_swap(std::declval<T>(), std::declval<T>()))) {
 261   adl_detail::adl_swap(std::forward<T>(lhs), std::forward<T>(rhs));
 262 }
 263
 264 /// Test whether \p RangeOrContainer is empty. Similar to C++17 std::empty.
 265 template <typename T>
 266 constexpr bool empty(const T &RangeOrContainer) {
 267   return adl_begin(RangeOrContainer) == adl_end(RangeOrContainer);
 268 }
 269
 270 /// Returns true if the given container only contains a single element.
 271 template <typename ContainerTy> bool hasSingleElement(ContainerTy &&C) {
 272   auto B = std::begin(C), E = std::end(C);
 273   return B != E && std::next(B) == E;
 274 }
 275
 276 /// Return a range covering \p RangeOrContainer with the first N elements
 277 /// excluded.
 278 template <typename T> auto drop_begin(T &&RangeOrContainer, size_t N) {
 279   return make_range(std::next(adl_begin(RangeOrContainer), N),
 280                     adl_end(RangeOrContainer));
 281 }
 282
 283 // mapped_iterator - This is a simple iterator adapter that causes a function to
 284 // be applied whenever operator* is invoked on the iterator.
 285
 286 template <typename ItTy, typename FuncTy,
 287           typename FuncReturnTy =
 288             decltype(std::declval<FuncTy>()(*std::declval<ItTy>()))>
 289 class mapped_iterator
 290     : public iterator_adaptor_base<
 291              mapped_iterator<ItTy, FuncTy>, ItTy,
 292              typename std::iterator_traits<ItTy>::iterator_category,
 293              typename std::remove_reference<FuncReturnTy>::type> {
 294 public:
 295   mapped_iterator(ItTy U, FuncTy F)
 296     : mapped_iterator::iterator_adaptor_base(std::move(U)), F(std::move(F)) {}
 297
 298   ItTy getCurrent() { return this->I; }
 299
 300   FuncReturnTy operator*() const { return F(*this->I); }
 301
 302 private:
 303   FuncTy F;
 304 };
 305
 306 // map_iterator - Provide a convenient way to create mapped_iterators, just like
 307 // make_pair is useful for creating pairs...
 308 template <class ItTy, class FuncTy>
 309 inline mapped_iterator<ItTy, FuncTy> map_iterator(ItTy I, FuncTy F) {
 310   return mapped_iterator<ItTy, FuncTy>(std::move(I), std::move(F));
 311 }
 312
 313 template <class ContainerTy, class FuncTy>
 314 auto map_range(ContainerTy &&C, FuncTy F) {
 315   return make_range(map_iterator(C.begin(), F), map_iterator(C.end(), F));
 316 }
 317
 318 /// Helper to determine if type T has a member called rbegin().
 319 template <typename Ty> class has_rbegin_impl {
 320   using yes = char[1];
 321   using no = char[2];
 322
 323   template <typename Inner>
 324   static yes& test(Inner *I, decltype(I->rbegin()) * = nullptr);
 325
 326   template <typename>
 327   static no& test(...);
 328
 329 public:
 330   static const bool value = sizeof(test<Ty>(nullptr)) == sizeof(yes);
 331 };
 332
 333 /// Metafunction to determine if T& or T has a member called rbegin().
 334 template <typename Ty>
 335 struct has_rbegin : has_rbegin_impl<typename std::remove_reference<Ty>::type> {
 336 };
 337
 338 // Returns an iterator_range over the given container which iterates in reverse.
 339 // Note that the container must have rbegin()/rend() methods for this to work.
 340 template <typename ContainerTy>
 341 auto reverse(ContainerTy &&C,
 342              std::enable_if_t<has_rbegin<ContainerTy>::value> * = nullptr) {
 343   return make_range(C.rbegin(), C.rend());
 344 }
 345
 346 // Returns a std::reverse_iterator wrapped around the given iterator.
 347 template <typename IteratorTy>
 348 std::reverse_iterator<IteratorTy> make_reverse_iterator(IteratorTy It) {
 349   return std::reverse_iterator<IteratorTy>(It);
 350 }
 351
 352 // Returns an iterator_range over the given container which iterates in reverse.
 353 // Note that the container must have begin()/end() methods which return
 354 // bidirectional iterators for this to work.
 355 template <typename ContainerTy>
 356 auto reverse(ContainerTy &&C,
 357              std::enable_if_t<!has_rbegin<ContainerTy>::value> * = nullptr) {
 358   return make_range(llvm::make_reverse_iterator(std::end(C)),
 359                     llvm::make_reverse_iterator(std::begin(C)));
 360 }
 361
 362 /// An iterator adaptor that filters the elements of given inner iterators.
 363 ///
 364 /// The predicate parameter should be a callable object that accepts the wrapped
 365 /// iterator's reference type and returns a bool. When incrementing or
 366 /// decrementing the iterator, it will call the predicate on each element and
 367 /// skip any where it returns false.
 368 ///
 369 /// \code
 370 ///   int A[] = { 1, 2, 3, 4 };
 371 ///   auto R = make_filter_range(A, [](int N) { return N % 2 == 1; });
 372 ///   // R contains { 1, 3 }.
 373 /// \endcode
 374 ///
 375 /// Note: filter_iterator_base implements support for forward iteration.
 376 /// filter_iterator_impl exists to provide support for bidirectional iteration,
 377 /// conditional on whether the wrapped iterator supports it.
 378 template <typename WrappedIteratorT, typename PredicateT, typename IterTag>
 379 class filter_iterator_base
 380     : public iterator_adaptor_base<
 381           filter_iterator_base<WrappedIteratorT, PredicateT, IterTag>,
 382           WrappedIteratorT,
 383           typename std::common_type<
 384               IterTag, typename std::iterator_traits<
 385                            WrappedIteratorT>::iterator_category>::type> {
 386   using BaseT = iterator_adaptor_base<
 387       filter_iterator_base<WrappedIteratorT, PredicateT, IterTag>,
 388       WrappedIteratorT,
 389       typename std::common_type<
 390           IterTag, typename std::iterator_traits<
 391                        WrappedIteratorT>::iterator_category>::type>;
 392
 393 protected:
 394   WrappedIteratorT End;
 395   PredicateT Pred;
 396
 397   void findNextValid() {
 398     while (this->I != End && !Pred(*this->I))
 399       BaseT::operator++();
 400   }
 401
 402   // Construct the iterator. The begin iterator needs to know where the end
 403   // is, so that it can properly stop when it gets there. The end iterator only
 404   // needs the predicate to support bidirectional iteration.
 405   filter_iterator_base(WrappedIteratorT Begin, WrappedIteratorT End,
 406                        PredicateT Pred)
 407       : BaseT(Begin), End(End), Pred(Pred) {
 408     findNextValid();
 409   }
 410
 411 public:
 412   using BaseT::operator++;
 413
 414   filter_iterator_base &operator++() {
 415     BaseT::operator++();
 416     findNextValid();
 417     return *this;
 418   }
 419 };
 420
 421 /// Specialization of filter_iterator_base for forward iteration only.
 422 template <typename WrappedIteratorT, typename PredicateT,
 423           typename IterTag = std::forward_iterator_tag>
 424 class filter_iterator_impl
 425     : public filter_iterator_base<WrappedIteratorT, PredicateT, IterTag> {
 426   using BaseT = filter_iterator_base<WrappedIteratorT, PredicateT, IterTag>;
 427
 428 public:
 429   filter_iterator_impl(WrappedIteratorT Begin, WrappedIteratorT End,
 430                        PredicateT Pred)
 431       : BaseT(Begin, End, Pred) {}
 432 };
 433
 434 /// Specialization of filter_iterator_base for bidirectional iteration.
 435 template <typename WrappedIteratorT, typename PredicateT>
 436 class filter_iterator_impl<WrappedIteratorT, PredicateT,
 437                            std::bidirectional_iterator_tag>
 438     : public filter_iterator_base<WrappedIteratorT, PredicateT,
 439                                   std::bidirectional_iterator_tag> {
 440   using BaseT = filter_iterator_base<WrappedIteratorT, PredicateT,
 441                                      std::bidirectional_iterator_tag>;
 442   void findPrevValid() {
 443     while (!this->Pred(*this->I))
 444       BaseT::operator--();
 445   }
 446
 447 public:
 448   using BaseT::operator--;
 449
 450   filter_iterator_impl(WrappedIteratorT Begin, WrappedIteratorT End,
 451                        PredicateT Pred)
 452       : BaseT(Begin, End, Pred) {}
 453
 454   filter_iterator_impl &operator--() {
 455     BaseT::operator--();
 456     findPrevValid();
 457     return *this;
 458   }
 459 };
 460
 461 namespace detail {
 462
 463 template <bool is_bidirectional> struct fwd_or_bidi_tag_impl {
 464   using type = std::forward_iterator_tag;
 465 };
 466
 467 template <> struct fwd_or_bidi_tag_impl<true> {
 468   using type = std::bidirectional_iterator_tag;
 469 };
 470
 471 /// Helper which sets its type member to forward_iterator_tag if the category
 472 /// of \p IterT does not derive from bidirectional_iterator_tag, and to
 473 /// bidirectional_iterator_tag otherwise.
 474 template <typename IterT> struct fwd_or_bidi_tag {
 475   using type = typename fwd_or_bidi_tag_impl<std::is_base_of<
 476       std::bidirectional_iterator_tag,
 477       typename std::iterator_traits<IterT>::iterator_category>::value>::type;
 478 };
 479
 480 } // namespace detail
 481
 482 /// Defines filter_iterator to a suitable specialization of
 483 /// filter_iterator_impl, based on the underlying iterator's category.
 484 template <typename WrappedIteratorT, typename PredicateT>
 485 using filter_iterator = filter_iterator_impl<
 486     WrappedIteratorT, PredicateT,
 487     typename detail::fwd_or_bidi_tag<WrappedIteratorT>::type>;
 488
 489 /// Convenience function that takes a range of elements and a predicate,
 490 /// and return a new filter_iterator range.
 491 ///
 492 /// FIXME: Currently if RangeT && is a rvalue reference to a temporary, the
 493 /// lifetime of that temporary is not kept by the returned range object, and the
 494 /// temporary is going to be dropped on the floor after the make_iterator_range
 495 /// full expression that contains this function call.
 496 template <typename RangeT, typename PredicateT>
 497 iterator_range<filter_iterator<detail::IterOfRange<RangeT>, PredicateT>>
 498 make_filter_range(RangeT &&Range, PredicateT Pred) {
 499   using FilterIteratorT =
 500       filter_iterator<detail::IterOfRange<RangeT>, PredicateT>;
 501   return make_range(
 502       FilterIteratorT(std::begin(std::forward<RangeT>(Range)),
 503                       std::end(std::forward<RangeT>(Range)), Pred),
 504       FilterIteratorT(std::end(std::forward<RangeT>(Range)),
 505                       std::end(std::forward<RangeT>(Range)), Pred));
 506 }
 507
 508 /// A pseudo-iterator adaptor that is designed to implement "early increment"
 509 /// style loops.
 510 ///
 511 /// This is *not a normal iterator* and should almost never be used directly. It
 512 /// is intended primarily to be used with range based for loops and some range
 513 /// algorithms.
 514 ///
 515 /// The iterator isn't quite an `OutputIterator` or an `InputIterator` but
 516 /// somewhere between them. The constraints of these iterators are:
 517 ///
 518 /// - On construction or after being incremented, it is comparable and
 519 ///   dereferencable. It is *not* incrementable.
 520 /// - After being dereferenced, it is neither comparable nor dereferencable, it
 521 ///   is only incrementable.
 522 ///
 523 /// This means you can only dereference the iterator once, and you can only
 524 /// increment it once between dereferences.
 525 template <typename WrappedIteratorT>
 526 class early_inc_iterator_impl
 527     : public iterator_adaptor_base<early_inc_iterator_impl<WrappedIteratorT>,
 528                                    WrappedIteratorT, std::input_iterator_tag> {
 529   using BaseT =
 530       iterator_adaptor_base<early_inc_iterator_impl<WrappedIteratorT>,
 531                             WrappedIteratorT, std::input_iterator_tag>;
 532
 533   using PointerT = typename std::iterator_traits<WrappedIteratorT>::pointer;
 534
 535 protected:
 536 #if LLVM_ENABLE_ABI_BREAKING_CHECKS
 537   bool IsEarlyIncremented = false;
 538 #endif
 539
 540 public:
 541   early_inc_iterator_impl(WrappedIteratorT I) : BaseT(I) {}
 542
 543   using BaseT::operator*;
 544   typename BaseT::reference operator*() {
 545 #if LLVM_ENABLE_ABI_BREAKING_CHECKS
 546     assert(!IsEarlyIncremented && "Cannot dereference twice!");
 547     IsEarlyIncremented = true;
 548 #endif
 549     return *(this->I)++;
 550   }
 551
 552   using BaseT::operator++;
 553   early_inc_iterator_impl &operator++() {
 554 #if LLVM_ENABLE_ABI_BREAKING_CHECKS
 555     assert(IsEarlyIncremented && "Cannot increment before dereferencing!");
 556     IsEarlyIncremented = false;
 557 #endif
 558     return *this;
 559   }
 560
 561   using BaseT::operator==;
 562   bool operator==(const early_inc_iterator_impl &RHS) const {
 563 #if LLVM_ENABLE_ABI_BREAKING_CHECKS
 564     assert(!IsEarlyIncremented && "Cannot compare after dereferencing!");
 565 #endif
 566     return BaseT::operator==(RHS);
 567   }
 568 };
 569
 570 /// Make a range that does early increment to allow mutation of the underlying
 571 /// range without disrupting iteration.
 572 ///
 573 /// The underlying iterator will be incremented immediately after it is
 574 /// dereferenced, allowing deletion of the current node or insertion of nodes to
 575 /// not disrupt iteration provided they do not invalidate the *next* iterator --
 576 /// the current iterator can be invalidated.
 577 ///
 578 /// This requires a very exact pattern of use that is only really suitable to
 579 /// range based for loops and other range algorithms that explicitly guarantee
 580 /// to dereference exactly once each element, and to increment exactly once each
 581 /// element.
 582 template <typename RangeT>
 583 iterator_range<early_inc_iterator_impl<detail::IterOfRange<RangeT>>>
 584 make_early_inc_range(RangeT &&Range) {
 585   using EarlyIncIteratorT =
 586       early_inc_iterator_impl<detail::IterOfRange<RangeT>>;
 587   return make_range(EarlyIncIteratorT(std::begin(std::forward<RangeT>(Range))),
 588                     EarlyIncIteratorT(std::end(std::forward<RangeT>(Range))));
 589 }
 590
 591 // forward declarations required by zip_shortest/zip_first/zip_longest
 592 template <typename R, typename UnaryPredicate>
 593 bool all_of(R &&range, UnaryPredicate P);
 594 template <typename R, typename UnaryPredicate>
 595 bool any_of(R &&range, UnaryPredicate P);
 596
 597 namespace detail {
 598
 599 using std::declval;
 600
 601 // We have to alias this since inlining the actual type at the usage site
 602 // in the parameter list of iterator_facade_base<> below ICEs MSVC 2017.
 603 template<typename... Iters> struct ZipTupleType {
 604   using type = std::tuple<decltype(*declval<Iters>())...>;
 605 };
 606
 607 template <typename ZipType, typename... Iters>
 608 using zip_traits = iterator_facade_base<
 609     ZipType, typename std::common_type<std::bidirectional_iterator_tag,
 610                                        typename std::iterator_traits<
 611                                            Iters>::iterator_category...>::type,
 612     // ^ TODO: Implement random access methods.
 613     typename ZipTupleType<Iters...>::type,
 614     typename std::iterator_traits<typename std::tuple_element<
 615         0, std::tuple<Iters...>>::type>::difference_type,
 616     // ^ FIXME: This follows boost::make_zip_iterator's assumption that all
 617     // inner iterators have the same difference_type. It would fail if, for
 618     // instance, the second field's difference_type were non-numeric while the
 619     // first is.
 620     typename ZipTupleType<Iters...>::type *,
 621     typename ZipTupleType<Iters...>::type>;
 622
 623 template <typename ZipType, typename... Iters>
 624 struct zip_common : public zip_traits<ZipType, Iters...> {
 625   using Base = zip_traits<ZipType, Iters...>;
 626   using value_type = typename Base::value_type;
 627
 628   std::tuple<Iters...> iterators;
 629
 630 protected:
 631   template <size_t... Ns> value_type deref(std::index_sequence<Ns...>) const {
 632     return value_type(*std::get<Ns>(iterators)...);
 633   }
 634
 635   template <size_t... Ns>
 636   decltype(iterators) tup_inc(std::index_sequence<Ns...>) const {
 637     return std::tuple<Iters...>(std::next(std::get<Ns>(iterators))...);
 638   }
 639
 640   template <size_t... Ns>
 641   decltype(iterators) tup_dec(std::index_sequence<Ns...>) const {
 642     return std::tuple<Iters...>(std::prev(std::get<Ns>(iterators))...);
 643   }
 644
 645 public:
 646   zip_common(Iters &&... ts) : iterators(std::forward<Iters>(ts)...) {}
 647
 648   value_type operator*() { return deref(std::index_sequence_for<Iters...>{}); }
 649
 650   const value_type operator*() const {
 651     return deref(std::index_sequence_for<Iters...>{});
 652   }
 653
 654   ZipType &operator++() {
 655     iterators = tup_inc(std::index_sequence_for<Iters...>{});
 656     return *reinterpret_cast<ZipType *>(this);
 657   }
 658
 659   ZipType &operator--() {
 660     static_assert(Base::IsBidirectional,
 661                   "All inner iterators must be at least bidirectional.");
 662     iterators = tup_dec(std::index_sequence_for<Iters...>{});
 663     return *reinterpret_cast<ZipType *>(this);
 664   }
 665 };
 666
 667 template <typename... Iters>
 668 struct zip_first : public zip_common<zip_first<Iters...>, Iters...> {
 669   using Base = zip_common<zip_first<Iters...>, Iters...>;
 670
 671   bool operator==(const zip_first<Iters...> &other) const {
 672     return std::get<0>(this->iterators) == std::get<0>(other.iterators);
 673   }
 674
 675   zip_first(Iters &&... ts) : Base(std::forward<Iters>(ts)...) {}
 676 };
 677
 678 template <typename... Iters>
 679 class zip_shortest : public zip_common<zip_shortest<Iters...>, Iters...> {
 680   template <size_t... Ns>
 681   bool test(const zip_shortest<Iters...> &other,
 682             std::index_sequence<Ns...>) const {
 683     return all_of(std::initializer_list<bool>{std::get<Ns>(this->iterators) !=
 684                                               std::get<Ns>(other.iterators)...},
 685                   identity<bool>{});
 686   }
 687
 688 public:
 689   using Base = zip_common<zip_shortest<Iters...>, Iters...>;
 690
 691   zip_shortest(Iters &&... ts) : Base(std::forward<Iters>(ts)...) {}
 692
 693   bool operator==(const zip_shortest<Iters...> &other) const {
 694     return !test(other, std::index_sequence_for<Iters...>{});
 695   }
 696 };
 697
 698 template <template <typename...> class ItType, typename... Args> class zippy {
 699 public:
 700   using iterator = ItType<decltype(std::begin(std::declval<Args>()))...>;
 701   using iterator_category = typename iterator::iterator_category;
 702   using value_type = typename iterator::value_type;
 703   using difference_type = typename iterator::difference_type;
 704   using pointer = typename iterator::pointer;
 705   using reference = typename iterator::reference;
 706
 707 private:
 708   std::tuple<Args...> ts;
 709
 710   template <size_t... Ns>
 711   iterator begin_impl(std::index_sequence<Ns...>) const {
 712     return iterator(std::begin(std::get<Ns>(ts))...);
 713   }
 714   template <size_t... Ns> iterator end_impl(std::index_sequence<Ns...>) const {
 715     return iterator(std::end(std::get<Ns>(ts))...);
 716   }
 717
 718 public:
 719   zippy(Args &&... ts_) : ts(std::forward<Args>(ts_)...) {}
 720
 721   iterator begin() const {
 722     return begin_impl(std::index_sequence_for<Args...>{});
 723   }
 724   iterator end() const { return end_impl(std::index_sequence_for<Args...>{}); }
 725 };
 726
 727 } // end namespace detail
 728
 729 /// zip iterator for two or more iteratable types.
 730 template <typename T, typename U, typename... Args>
 731 detail::zippy<detail::zip_shortest, T, U, Args...> zip(T &&t, U &&u,
 732                                                        Args &&... args) {
 733   return detail::zippy<detail::zip_shortest, T, U, Args...>(
 734       std::forward<T>(t), std::forward<U>(u), std::forward<Args>(args)...);
 735 }
 736
 737 /// zip iterator that, for the sake of efficiency, assumes the first iteratee to
 738 /// be the shortest.
 739 template <typename T, typename U, typename... Args>
 740 detail::zippy<detail::zip_first, T, U, Args...> zip_first(T &&t, U &&u,
 741                                                           Args &&... args) {
 742   return detail::zippy<detail::zip_first, T, U, Args...>(
 743       std::forward<T>(t), std::forward<U>(u), std::forward<Args>(args)...);
 744 }
 745
 746 namespace detail {
 747 template <typename Iter>
 748 Iter next_or_end(const Iter &I, const Iter &End) {
 749   if (I == End)
 750     return End;
 751   return std::next(I);
 752 }
 753
 754 template <typename Iter>
 755 auto deref_or_none(const Iter &I, const Iter &End) -> llvm::Optional<
 756     std::remove_const_t<std::remove_reference_t<decltype(*I)>>> {
 757   if (I == End)
 758     return None;
 759   return *I;
 760 }
 761
 762 template <typename Iter> struct ZipLongestItemType {
 763   using type =
 764       llvm::Optional<typename std::remove_const<typename std::remove_reference<
 765           decltype(*std::declval<Iter>())>::type>::type>;
 766 };
 767
 768 template <typename... Iters> struct ZipLongestTupleType {
 769   using type = std::tuple<typename ZipLongestItemType<Iters>::type...>;
 770 };
 771
 772 template <typename... Iters>
 773 class zip_longest_iterator
 774     : public iterator_facade_base<
 775           zip_longest_iterator<Iters...>,
 776           typename std::common_type<
 777               std::forward_iterator_tag,
 778               typename std::iterator_traits<Iters>::iterator_category...>::type,
 779           typename ZipLongestTupleType<Iters...>::type,
 780           typename std::iterator_traits<typename std::tuple_element<
 781               0, std::tuple<Iters...>>::type>::difference_type,
 782           typename ZipLongestTupleType<Iters...>::type *,
 783           typename ZipLongestTupleType<Iters...>::type> {
 784 public:
 785   using value_type = typename ZipLongestTupleType<Iters...>::type;
 786
 787 private:
 788   std::tuple<Iters...> iterators;
 789   std::tuple<Iters...> end_iterators;
 790
 791   template <size_t... Ns>
 792   bool test(const zip_longest_iterator<Iters...> &other,
 793             std::index_sequence<Ns...>) const {
 794     return llvm::any_of(
 795         std::initializer_list<bool>{std::get<Ns>(this->iterators) !=
 796                                     std::get<Ns>(other.iterators)...},
 797         identity<bool>{});
 798   }
 799
 800   template <size_t... Ns> value_type deref(std::index_sequence<Ns...>) const {
 801     return value_type(
 802         deref_or_none(std::get<Ns>(iterators), std::get<Ns>(end_iterators))...);
 803   }
 804
 805   template <size_t... Ns>
 806   decltype(iterators) tup_inc(std::index_sequence<Ns...>) const {
 807     return std::tuple<Iters...>(
 808         next_or_end(std::get<Ns>(iterators), std::get<Ns>(end_iterators))...);
 809   }
 810
 811 public:
 812   zip_longest_iterator(std::pair<Iters &&, Iters &&>... ts)
 813       : iterators(std::forward<Iters>(ts.first)...),
 814         end_iterators(std::forward<Iters>(ts.second)...) {}
 815
 816   value_type operator*() { return deref(std::index_sequence_for<Iters...>{}); }
 817
 818   value_type operator*() const {
 819     return deref(std::index_sequence_for<Iters...>{});
 820   }
 821
 822   zip_longest_iterator<Iters...> &operator++() {
 823     iterators = tup_inc(std::index_sequence_for<Iters...>{});
 824     return *this;
 825   }
 826
 827   bool operator==(const zip_longest_iterator<Iters...> &other) const {
 828     return !test(other, std::index_sequence_for<Iters...>{});
 829   }
 830 };
 831
 832 template <typename... Args> class zip_longest_range {
 833 public:
 834   using iterator =
 835       zip_longest_iterator<decltype(adl_begin(std::declval<Args>()))...>;
 836   using iterator_category = typename iterator::iterator_category;
 837   using value_type = typename iterator::value_type;
 838   using difference_type = typename iterator::difference_type;
 839   using pointer = typename iterator::pointer;
 840   using reference = typename iterator::reference;
 841
 842 private:
 843   std::tuple<Args...> ts;
 844
 845   template <size_t... Ns>
 846   iterator begin_impl(std::index_sequence<Ns...>) const {
 847     return iterator(std::make_pair(adl_begin(std::get<Ns>(ts)),
 848                                    adl_end(std::get<Ns>(ts)))...);
 849   }
 850
 851   template <size_t... Ns> iterator end_impl(std::index_sequence<Ns...>) const {
 852     return iterator(std::make_pair(adl_end(std::get<Ns>(ts)),
 853                                    adl_end(std::get<Ns>(ts)))...);
 854   }
 855
 856 public:
 857   zip_longest_range(Args &&... ts_) : ts(std::forward<Args>(ts_)...) {}
 858
 859   iterator begin() const {
 860     return begin_impl(std::index_sequence_for<Args...>{});
 861   }
 862   iterator end() const { return end_impl(std::index_sequence_for<Args...>{}); }
 863 };
 864 } // namespace detail
 865
 866 /// Iterate over two or more iterators at the same time. Iteration continues
 867 /// until all iterators reach the end. The llvm::Optional only contains a value
 868 /// if the iterator has not reached the end.
 869 template <typename T, typename U, typename... Args>
 870 detail::zip_longest_range<T, U, Args...> zip_longest(T &&t, U &&u,
 871                                                      Args &&... args) {
 872   return detail::zip_longest_range<T, U, Args...>(
 873       std::forward<T>(t), std::forward<U>(u), std::forward<Args>(args)...);
 874 }
 875
 876 /// Iterator wrapper that concatenates sequences together.
 877 ///
 878 /// This can concatenate different iterators, even with different types, into
 879 /// a single iterator provided the value types of all the concatenated
 880 /// iterators expose `reference` and `pointer` types that can be converted to
 881 /// `ValueT &` and `ValueT *` respectively. It doesn't support more
 882 /// interesting/customized pointer or reference types.
 883 ///
 884 /// Currently this only supports forward or higher iterator categories as
 885 /// inputs and always exposes a forward iterator interface.
 886 template <typename ValueT, typename... IterTs>
 887 class concat_iterator
 888     : public iterator_facade_base<concat_iterator<ValueT, IterTs...>,
 889                                   std::forward_iterator_tag, ValueT> {
 890   using BaseT = typename concat_iterator::iterator_facade_base;
 891
 892   /// We store both the current and end iterators for each concatenated
 893   /// sequence in a tuple of pairs.
 894   ///
 895   /// Note that something like iterator_range seems nice at first here, but the
 896   /// range properties are of little benefit and end up getting in the way
 897   /// because we need to do mutation on the current iterators.
 898   std::tuple<IterTs...> Begins;
 899   std::tuple<IterTs...> Ends;
 900
 901   /// Attempts to increment a specific iterator.
 902   ///
 903   /// Returns true if it was able to increment the iterator. Returns false if
 904   /// the iterator is already at the end iterator.
 905   template <size_t Index> bool incrementHelper() {
 906     auto &Begin = std::get<Index>(Begins);
 907     auto &End = std::get<Index>(Ends);
 908     if (Begin == End)
 909       return false;
 910
 911     ++Begin;
 912     return true;
 913   }
 914
 915   /// Increments the first non-end iterator.
 916   ///
 917   /// It is an error to call this with all iterators at the end.
 918   template <size_t... Ns> void increment(std::index_sequence<Ns...>) {
 919     // Build a sequence of functions to increment each iterator if possible.
 920     bool (concat_iterator::*IncrementHelperFns[])() = {
 921         &concat_iterator::incrementHelper<Ns>...};
 922
 923     // Loop over them, and stop as soon as we succeed at incrementing one.
 924     for (auto &IncrementHelperFn : IncrementHelperFns)
 925       if ((this->*IncrementHelperFn)())
 926         return;
 927
 928     llvm_unreachable("Attempted to increment an end concat iterator!");
 929   }
 930
 931   /// Returns null if the specified iterator is at the end. Otherwise,
 932   /// dereferences the iterator and returns the address of the resulting
 933   /// reference.
 934   template <size_t Index> ValueT *getHelper() const {
 935     auto &Begin = std::get<Index>(Begins);
 936     auto &End = std::get<Index>(Ends);
 937     if (Begin == End)
 938       return nullptr;
 939
 940     return &*Begin;
 941   }
 942
 943   /// Finds the first non-end iterator, dereferences, and returns the resulting
 944   /// reference.
 945   ///
 946   /// It is an error to call this with all iterators at the end.
 947   template <size_t... Ns> ValueT &get(std::index_sequence<Ns...>) const {
 948     // Build a sequence of functions to get from iterator if possible.
 949     ValueT *(concat_iterator::*GetHelperFns[])() const = {
 950         &concat_iterator::getHelper<Ns>...};
 951
 952     // Loop over them, and return the first result we find.
 953     for (auto &GetHelperFn : GetHelperFns)
 954       if (ValueT *P = (this->*GetHelperFn)())
 955         return *P;
 956
 957     llvm_unreachable("Attempted to get a pointer from an end concat iterator!");
 958   }
 959
 960 public:
 961   /// Constructs an iterator from a sequence of ranges.
 962   ///
 963   /// We need the full range to know how to switch between each of the
 964   /// iterators.
 965   template <typename... RangeTs>
 966   explicit concat_iterator(RangeTs &&... Ranges)
 967       : Begins(std::begin(Ranges)...), Ends(std::end(Ranges)...) {}
 968
 969   using BaseT::operator++;
 970
 971   concat_iterator &operator++() {
 972     increment(std::index_sequence_for<IterTs...>());
 973     return *this;
 974   }
 975
 976   ValueT &operator*() const {
 977     return get(std::index_sequence_for<IterTs...>());
 978   }
 979
 980   bool operator==(const concat_iterator &RHS) const {
 981     return Begins == RHS.Begins && Ends == RHS.Ends;
 982   }
 983 };
 984
 985 namespace detail {
 986
 987 /// Helper to store a sequence of ranges being concatenated and access them.
 988 ///
 989 /// This is designed to facilitate providing actual storage when temporaries
 990 /// are passed into the constructor such that we can use it as part of range
 991 /// based for loops.
 992 template <typename ValueT, typename... RangeTs> class concat_range {
 993 public:
 994   using iterator =
 995       concat_iterator<ValueT,
 996                       decltype(std::begin(std::declval<RangeTs &>()))...>;
 997
 998 private:
 999   std::tuple<RangeTs...> Ranges;
1000
1001   template <size_t... Ns> iterator begin_impl(std::index_sequence<Ns...>) {
1002     return iterator(std::get<Ns>(Ranges)...);
1003   }
1004   template <size_t... Ns> iterator end_impl(std::index_sequence<Ns...>) {
1005     return iterator(make_range(std::end(std::get<Ns>(Ranges)),
1006                                std::end(std::get<Ns>(Ranges)))...);
1007   }
1008
1009 public:
1010   concat_range(RangeTs &&... Ranges)
1011       : Ranges(std::forward<RangeTs>(Ranges)...) {}
1012
1013   iterator begin() { return begin_impl(std::index_sequence_for<RangeTs...>{}); }
1014   iterator end() { return end_impl(std::index_sequence_for<RangeTs...>{}); }
1015 };
1016
1017 } // end namespace detail
1018
1019 /// Concatenated range across two or more ranges.
1020 ///
1021 /// The desired value type must be explicitly specified.
1022 template <typename ValueT, typename... RangeTs>
1023 detail::concat_range<ValueT, RangeTs...> concat(RangeTs &&... Ranges) {
1024   static_assert(sizeof...(RangeTs) > 1,
1025                 "Need more than one range to concatenate!");
1026   return detail::concat_range<ValueT, RangeTs...>(
1027       std::forward<RangeTs>(Ranges)...);
1028 }
1029
1030 /// A utility class used to implement an iterator that contains some base object
1031 /// and an index. The iterator moves the index but keeps the base constant.
1032 template <typename DerivedT, typename BaseT, typename T,
1033           typename PointerT = T *, typename ReferenceT = T &>
1034 class indexed_accessor_iterator
1035     : public llvm::iterator_facade_base<DerivedT,
1036                                         std::random_access_iterator_tag, T,
1037                                         std::ptrdiff_t, PointerT, ReferenceT> {
1038 public:
1039   ptrdiff_t operator-(const indexed_accessor_iterator &rhs) const {
1040     assert(base == rhs.base && "incompatible iterators");
1041     return index - rhs.index;
1042   }
1043   bool operator==(const indexed_accessor_iterator &rhs) const {
1044     return base == rhs.base && index == rhs.index;
1045   }
1046   bool operator<(const indexed_accessor_iterator &rhs) const {
1047     assert(base == rhs.base && "incompatible iterators");
1048     return index < rhs.index;
1049   }
1050
1051   DerivedT &operator+=(ptrdiff_t offset) {
1052     this->index += offset;
1053     return static_cast<DerivedT &>(*this);
1054   }
1055   DerivedT &operator-=(ptrdiff_t offset) {
1056     this->index -= offset;
1057     return static_cast<DerivedT &>(*this);
1058   }
1059
1060   /// Returns the current index of the iterator.
1061   ptrdiff_t getIndex() const { return index; }
1062
1063   /// Returns the current base of the iterator.
1064   const BaseT &getBase() const { return base; }
1065
1066 protected:
1067   indexed_accessor_iterator(BaseT base, ptrdiff_t index)
1068       : base(base), index(index) {}
1069   BaseT base;
1070   ptrdiff_t index;
1071 };
1072
1073 namespace detail {
1074 /// The class represents the base of a range of indexed_accessor_iterators. It
1075 /// provides support for many different range functionalities, e.g.
1076 /// drop_front/slice/etc.. Derived range classes must implement the following
1077 /// static methods:
1078 ///   * ReferenceT dereference_iterator(const BaseT &base, ptrdiff_t index)
1079 ///     - Dereference an iterator pointing to the base object at the given
1080 ///       index.
1081 ///   * BaseT offset_base(const BaseT &base, ptrdiff_t index)
1082 ///     - Return a new base that is offset from the provide base by 'index'
1083 ///       elements.
1084 template <typename DerivedT, typename BaseT, typename T,
1085           typename PointerT = T *, typename ReferenceT = T &>
1086 class indexed_accessor_range_base {
1087 public:
1088   using RangeBaseT =
1089       indexed_accessor_range_base<DerivedT, BaseT, T, PointerT, ReferenceT>;
1090
1091   /// An iterator element of this range.
1092   class iterator : public indexed_accessor_iterator<iterator, BaseT, T,
1093                                                     PointerT, ReferenceT> {
1094   public:
1095     // Index into this iterator, invoking a static method on the derived type.
1096     ReferenceT operator*() const {
1097       return DerivedT::dereference_iterator(this->getBase(), this->getIndex());
1098     }
1099
1100   private:
1101     iterator(BaseT owner, ptrdiff_t curIndex)
1102         : indexed_accessor_iterator<iterator, BaseT, T, PointerT, ReferenceT>(
1103               owner, curIndex) {}
1104
1105     /// Allow access to the constructor.
1106     friend indexed_accessor_range_base<DerivedT, BaseT, T, PointerT,
1107                                        ReferenceT>;
1108   };
1109
1110   indexed_accessor_range_base(iterator begin, iterator end)
1111       : base(offset_base(begin.getBase(), begin.getIndex())),
1112         count(end.getIndex() - begin.getIndex()) {}
1113   indexed_accessor_range_base(const iterator_range<iterator> &range)
1114       : indexed_accessor_range_base(range.begin(), range.end()) {}
1115   indexed_accessor_range_base(BaseT base, ptrdiff_t count)
1116       : base(base), count(count) {}
1117
1118   iterator begin() const { return iterator(base, 0); }
1119   iterator end() const { return iterator(base, count); }
1120   ReferenceT operator[](unsigned index) const {
1121     assert(index < size() && "invalid index for value range");
1122     return DerivedT::dereference_iterator(base, index);
1123   }
1124   ReferenceT front() const {
1125     assert(!empty() && "expected non-empty range");
1126     return (*this)[0];
1127   }
1128   ReferenceT back() const {
1129     assert(!empty() && "expected non-empty range");
1130     return (*this)[size() - 1];
1131   }
1132
1133   /// Compare this range with another.
1134   template <typename OtherT> bool operator==(const OtherT &other) const {
1135     return size() ==
1136                static_cast<size_t>(std::distance(other.begin(), other.end())) &&
1137            std::equal(begin(), end(), other.begin());
1138   }
1139   template <typename OtherT> bool operator!=(const OtherT &other) const {
1140     return !(*this == other);
1141   }
1142
1143   /// Return the size of this range.
1144   size_t size() const { return count; }
1145
1146   /// Return if the range is empty.
1147   bool empty() const { return size() == 0; }
1148
1149   /// Drop the first N elements, and keep M elements.
1150   DerivedT slice(size_t n, size_t m) const {
1151     assert(n + m <= size() && "invalid size specifiers");
1152     return DerivedT(offset_base(base, n), m);
1153   }
1154
1155   /// Drop the first n elements.
1156   DerivedT drop_front(size_t n = 1) const {
1157     assert(size() >= n && "Dropping more elements than exist");
1158     return slice(n, size() - n);
1159   }
1160   /// Drop the last n elements.
1161   DerivedT drop_back(size_t n = 1) const {
1162     assert(size() >= n && "Dropping more elements than exist");
1163     return DerivedT(base, size() - n);
1164   }
1165
1166   /// Take the first n elements.
1167   DerivedT take_front(size_t n = 1) const {
1168     return n < size() ? drop_back(size() - n)
1169                       : static_cast<const DerivedT &>(*this);
1170   }
1171
1172   /// Take the last n elements.
1173   DerivedT take_back(size_t n = 1) const {
1174     return n < size() ? drop_front(size() - n)
1175                       : static_cast<const DerivedT &>(*this);
1176   }
1177
1178   /// Allow conversion to any type accepting an iterator_range.
1179   template <typename RangeT, typename = std::enable_if_t<std::is_constructible<
1180                                  RangeT, iterator_range<iterator>>::value>>
1181   operator RangeT() const {
1182     return RangeT(iterator_range<iterator>(*this));
1183   }
1184
1185   /// Returns the base of this range.
1186   const BaseT &getBase() const { return base; }
1187
1188 private:
1189   /// Offset the given base by the given amount.
1190   static BaseT offset_base(const BaseT &base, size_t n) {
1191     return n == 0 ? base : DerivedT::offset_base(base, n);
1192   }
1193
1194 protected:
1195   indexed_accessor_range_base(const indexed_accessor_range_base &) = default;
1196   indexed_accessor_range_base(indexed_accessor_range_base &&) = default;
1197   indexed_accessor_range_base &
1198   operator=(const indexed_accessor_range_base &) = default;
1199
1200   /// The base that owns the provided range of values.
1201   BaseT base;
1202   /// The size from the owning range.
1203   ptrdiff_t count;
1204 };
1205 } // end namespace detail
1206
1207 /// This class provides an implementation of a range of
1208 /// indexed_accessor_iterators where the base is not indexable. Ranges with
1209 /// bases that are offsetable should derive from indexed_accessor_range_base
1210 /// instead. Derived range classes are expected to implement the following
1211 /// static method:
1212 ///   * ReferenceT dereference(const BaseT &base, ptrdiff_t index)
1213 ///     - Dereference an iterator pointing to a parent base at the given index.
1214 template <typename DerivedT, typename BaseT, typename T,
1215           typename PointerT = T *, typename ReferenceT = T &>
1216 class indexed_accessor_range
1217     : public detail::indexed_accessor_range_base<
1218           DerivedT, std::pair<BaseT, ptrdiff_t>, T, PointerT, ReferenceT> {
1219 public:
1220   indexed_accessor_range(BaseT base, ptrdiff_t startIndex, ptrdiff_t count)
1221       : detail::indexed_accessor_range_base<
1222             DerivedT, std::pair<BaseT, ptrdiff_t>, T, PointerT, ReferenceT>(
1223             std::make_pair(base, startIndex), count) {}
1224   using detail::indexed_accessor_range_base<
1225       DerivedT, std::pair<BaseT, ptrdiff_t>, T, PointerT,
1226       ReferenceT>::indexed_accessor_range_base;
1227
1228   /// Returns the current base of the range.
1229   const BaseT &getBase() const { return this->base.first; }
1230
1231   /// Returns the current start index of the range.
1232   ptrdiff_t getStartIndex() const { return this->base.second; }
1233
1234   /// See `detail::indexed_accessor_range_base` for details.
1235   static std::pair<BaseT, ptrdiff_t>
1236   offset_base(const std::pair<BaseT, ptrdiff_t> &base, ptrdiff_t index) {
1237     // We encode the internal base as a pair of the derived base and a start
1238     // index into the derived base.
1239     return std::make_pair(base.first, base.second + index);
1240   }
1241   /// See `detail::indexed_accessor_range_base` for details.
1242   static ReferenceT
1243   dereference_iterator(const std::pair<BaseT, ptrdiff_t> &base,
1244                        ptrdiff_t index) {
1245     return DerivedT::dereference(base.first, base.second + index);
1246   }
1247 };
1248
1249 /// Given a container of pairs, return a range over the second elements.
1250 template <typename ContainerTy> auto make_second_range(ContainerTy &&c) {
1251   return llvm::map_range(
1252       std::forward<ContainerTy>(c),
1253       [](decltype((*std::begin(c))) elt) -> decltype((elt.second)) {
1254         return elt.second;
1255       });
1256 }
1257
1258 //===----------------------------------------------------------------------===//
1259 //     Extra additions to <utility>
1260 //===----------------------------------------------------------------------===//
1261
1262 /// Function object to check whether the first component of a std::pair
1263 /// compares less than the first component of another std::pair.
1264 struct less_first {
1265   template <typename T> bool operator()(const T &lhs, const T &rhs) const {
1266     return lhs.first < rhs.first;
1267   }
1268 };
1269
1270 /// Function object to check whether the second component of a std::pair
1271 /// compares less than the second component of another std::pair.
1272 struct less_second {
1273   template <typename T> bool operator()(const T &lhs, const T &rhs) const {
1274     return lhs.second < rhs.second;
1275   }
1276 };
1277
1278 /// \brief Function object to apply a binary function to the first component of
1279 /// a std::pair.
1280 template<typename FuncTy>
1281 struct on_first {
1282   FuncTy func;
1283
1284   template <typename T>
1285   decltype(auto) operator()(const T &lhs, const T &rhs) const {
1286     return func(lhs.first, rhs.first);
1287   }
1288 };
1289
1290 /// Utility type to build an inheritance chain that makes it easy to rank
1291 /// overload candidates.
1292 template <int N> struct rank : rank<N - 1> {};
1293 template <> struct rank<0> {};
1294
1295 /// traits class for checking whether type T is one of any of the given
1296 /// types in the variadic list.
1297 template <typename T, typename... Ts> struct is_one_of {
1298   static const bool value = false;
1299 };
1300
1301 template <typename T, typename U, typename... Ts>
1302 struct is_one_of<T, U, Ts...> {
1303   static const bool value =
1304       std::is_same<T, U>::value || is_one_of<T, Ts...>::value;
1305 };
1306
1307 /// traits class for checking whether type T is a base class for all
1308 ///  the given types in the variadic list.
1309 template <typename T, typename... Ts> struct are_base_of {
1310   static const bool value = true;
1311 };
1312
1313 template <typename T, typename U, typename... Ts>
1314 struct are_base_of<T, U, Ts...> {
1315   static const bool value =
1316       std::is_base_of<T, U>::value && are_base_of<T, Ts...>::value;
1317 };
1318
1319 //===----------------------------------------------------------------------===//
1320 //     Extra additions for arrays
1321 //===----------------------------------------------------------------------===//
1322
1323 // We have a copy here so that LLVM behaves the same when using different
1324 // standard libraries.
1325 template <class Iterator, class RNG>
1326 void shuffle(Iterator first, Iterator last, RNG &&g) {
1327   // It would be better to use a std::uniform_int_distribution,
1328   // but that would be stdlib dependent.
1329   for (auto size = last - first; size > 1; ++first, (void)--size)
1330     std::iter_swap(first, first + g() % size);
1331 }
1332
1333 /// Find the length of an array.
1334 template <class T, std::size_t N>
1335 constexpr inline size_t array_lengthof(T (&)[N]) {
1336   return N;
1337 }
1338
1339 /// Adapt std::less<T> for array_pod_sort.
1340 template<typename T>
1341 inline int array_pod_sort_comparator(const void *P1, const void *P2) {
1342   if (std::less<T>()(*reinterpret_cast<const T*>(P1),
1343                      *reinterpret_cast<const T*>(P2)))
1344     return -1;
1345   if (std::less<T>()(*reinterpret_cast<const T*>(P2),
1346                      *reinterpret_cast<const T*>(P1)))
1347     return 1;
1348   return 0;
1349 }
1350
1351 /// get_array_pod_sort_comparator - This is an internal helper function used to
1352 /// get type deduction of T right.
1353 template<typename T>
1354 inline int (*get_array_pod_sort_comparator(const T &))
1355              (const void*, const void*) {
1356   return array_pod_sort_comparator<T>;
1357 }
1358
1359 #ifdef EXPENSIVE_CHECKS
1360 namespace detail {
1361
1362 inline unsigned presortShuffleEntropy() {
1363   static unsigned Result(std::random_device{}());
1364   return Result;
1365 }
1366
1367 template <class IteratorTy>
1368 inline void presortShuffle(IteratorTy Start, IteratorTy End) {
1369   std::mt19937 Generator(presortShuffleEntropy());
1370   std::shuffle(Start, End, Generator);
1371 }
1372
1373 } // end namespace detail
1374 #endif
1375
1376 /// array_pod_sort - This sorts an array with the specified start and end
1377 /// extent.  This is just like std::sort, except that it calls qsort instead of
1378 /// using an inlined template.  qsort is slightly slower than std::sort, but
1379 /// most sorts are not performance critical in LLVM and std::sort has to be
1380 /// template instantiated for each type, leading to significant measured code
1381 /// bloat.  This function should generally be used instead of std::sort where
1382 /// possible.
1383 ///
1384 /// This function assumes that you have simple POD-like types that can be
1385 /// compared with std::less and can be moved with memcpy.  If this isn't true,
1386 /// you should use std::sort.
1387 ///
1388 /// NOTE: If qsort_r were portable, we could allow a custom comparator and
1389 /// default to std::less.
1390 template<class IteratorTy>
1391 inline void array_pod_sort(IteratorTy Start, IteratorTy End) {
1392   // Don't inefficiently call qsort with one element or trigger undefined
1393   // behavior with an empty sequence.
1394   auto NElts = End - Start;
1395   if (NElts <= 1) return;
1396 #ifdef EXPENSIVE_CHECKS
1397   detail::presortShuffle<IteratorTy>(Start, End);
1398 #endif
1399   qsort(&*Start, NElts, sizeof(*Start), get_array_pod_sort_comparator(*Start));
1400 }
1401
1402 template <class IteratorTy>
1403 inline void array_pod_sort(
1404     IteratorTy Start, IteratorTy End,
1405     int (*Compare)(
1406         const typename std::iterator_traits<IteratorTy>::value_type *,
1407         const typename std::iterator_traits<IteratorTy>::value_type *)) {
1408   // Don't inefficiently call qsort with one element or trigger undefined
1409   // behavior with an empty sequence.
1410   auto NElts = End - Start;
1411   if (NElts <= 1) return;
1412 #ifdef EXPENSIVE_CHECKS
1413   detail::presortShuffle<IteratorTy>(Start, End);
1414 #endif
1415   qsort(&*Start, NElts, sizeof(*Start),
1416         reinterpret_cast<int (*)(const void *, const void *)>(Compare));
1417 }
1418
1419 namespace detail {
1420 template <typename T>
1421 // We can use qsort if the iterator type is a pointer and the underlying value
1422 // is trivially copyable.
1423 using sort_trivially_copyable = conjunction<
1424     std::is_pointer<T>,
1425     is_trivially_copyable<typename std::iterator_traits<T>::value_type>>;
1426 } // namespace detail
1427
1428 // Provide wrappers to std::sort which shuffle the elements before sorting
1429 // to help uncover non-deterministic behavior (PR35135).
1430 template <typename IteratorTy,
1431           std::enable_if_t<!detail::sort_trivially_copyable<IteratorTy>::value,
1432                            int> = 0>
1433 inline void sort(IteratorTy Start, IteratorTy End) {
1434 #ifdef EXPENSIVE_CHECKS
1435   detail::presortShuffle<IteratorTy>(Start, End);
1436 #endif
1437   std::sort(Start, End);
1438 }
1439
1440 // Forward trivially copyable types to array_pod_sort. This avoids a large
1441 // amount of code bloat for a minor performance hit.
1442 template <typename IteratorTy,
1443           std::enable_if_t<detail::sort_trivially_copyable<IteratorTy>::value,
1444                            int> = 0>
1445 inline void sort(IteratorTy Start, IteratorTy End) {
1446   array_pod_sort(Start, End);
1447 }
1448
1449 template <typename Container> inline void sort(Container &&C) {
1450   llvm::sort(adl_begin(C), adl_end(C));
1451 }
1452
1453 template <typename IteratorTy, typename Compare>
1454 inline void sort(IteratorTy Start, IteratorTy End, Compare Comp) {
1455 #ifdef EXPENSIVE_CHECKS
1456   detail::presortShuffle<IteratorTy>(Start, End);
1457 #endif
1458   std::sort(Start, End, Comp);
1459 }
1460
1461 template <typename Container, typename Compare>
1462 inline void sort(Container &&C, Compare Comp) {
1463   llvm::sort(adl_begin(C), adl_end(C), Comp);
1464 }
1465
1466 //===----------------------------------------------------------------------===//
1467 //     Extra additions to <algorithm>
1468 //===----------------------------------------------------------------------===//
1469
1470 /// Get the size of a range. This is a wrapper function around std::distance
1471 /// which is only enabled when the operation is O(1).
1472 template <typename R>
1473 auto size(R &&Range,
1474           std::enable_if_t<std::is_same<typename std::iterator_traits<decltype(
1475                                             Range.begin())>::iterator_category,
1476                                         std::random_access_iterator_tag>::value,
1477                            void> * = nullptr) {
1478   return std::distance(Range.begin(), Range.end());
1479 }
1480
1481 /// Provide wrappers to std::for_each which take ranges instead of having to
1482 /// pass begin/end explicitly.
1483 template <typename R, typename UnaryPredicate>
1484 UnaryPredicate for_each(R &&Range, UnaryPredicate P) {
1485   return std::for_each(adl_begin(Range), adl_end(Range), P);
1486 }
1487
1488 /// Provide wrappers to std::all_of which take ranges instead of having to pass
1489 /// begin/end explicitly.
1490 template <typename R, typename UnaryPredicate>
1491 bool all_of(R &&Range, UnaryPredicate P) {
1492   return std::all_of(adl_begin(Range), adl_end(Range), P);
1493 }
1494
1495 /// Provide wrappers to std::any_of which take ranges instead of having to pass
1496 /// begin/end explicitly.
1497 template <typename R, typename UnaryPredicate>
1498 bool any_of(R &&Range, UnaryPredicate P) {
1499   return std::any_of(adl_begin(Range), adl_end(Range), P);
1500 }
1501
1502 /// Provide wrappers to std::none_of which take ranges instead of having to pass
1503 /// begin/end explicitly.
1504 template <typename R, typename UnaryPredicate>
1505 bool none_of(R &&Range, UnaryPredicate P) {
1506   return std::none_of(adl_begin(Range), adl_end(Range), P);
1507 }
1508
1509 /// Provide wrappers to std::find which take ranges instead of having to pass
1510 /// begin/end explicitly.
1511 template <typename R, typename T> auto find(R &&Range, const T &Val) {
1512   return std::find(adl_begin(Range), adl_end(Range), Val);
1513 }
1514
1515 /// Provide wrappers to std::find_if which take ranges instead of having to pass
1516 /// begin/end explicitly.
1517 template <typename R, typename UnaryPredicate>
1518 auto find_if(R &&Range, UnaryPredicate P) {
1519   return std::find_if(adl_begin(Range), adl_end(Range), P);
1520 }
1521
1522 template <typename R, typename UnaryPredicate>
1523 auto find_if_not(R &&Range, UnaryPredicate P) {
1524   return std::find_if_not(adl_begin(Range), adl_end(Range), P);
1525 }
1526
1527 /// Provide wrappers to std::remove_if which take ranges instead of having to
1528 /// pass begin/end explicitly.
1529 template <typename R, typename UnaryPredicate>
1530 auto remove_if(R &&Range, UnaryPredicate P) {
1531   return std::remove_if(adl_begin(Range), adl_end(Range), P);
1532 }
1533
1534 /// Provide wrappers to std::copy_if which take ranges instead of having to
1535 /// pass begin/end explicitly.
1536 template <typename R, typename OutputIt, typename UnaryPredicate>
1537 OutputIt copy_if(R &&Range, OutputIt Out, UnaryPredicate P) {
1538   return std::copy_if(adl_begin(Range), adl_end(Range), Out, P);
1539 }
1540
1541 template <typename R, typename OutputIt>
1542 OutputIt copy(R &&Range, OutputIt Out) {
1543   return std::copy(adl_begin(Range), adl_end(Range), Out);
1544 }
1545
1546 /// Wrapper function around std::find to detect if an element exists
1547 /// in a container.
1548 template <typename R, typename E>
1549 bool is_contained(R &&Range, const E &Element) {
1550   return std::find(adl_begin(Range), adl_end(Range), Element) != adl_end(Range);
1551 }
1552
1553 /// Wrapper function around std::is_sorted to check if elements in a range \p R
1554 /// are sorted with respect to a comparator \p C.
1555 template <typename R, typename Compare> bool is_sorted(R &&Range, Compare C) {
1556   return std::is_sorted(adl_begin(Range), adl_end(Range), C);
1557 }
1558
1559 /// Wrapper function around std::is_sorted to check if elements in a range \p R
1560 /// are sorted in non-descending order.
1561 template <typename R> bool is_sorted(R &&Range) {
1562   return std::is_sorted(adl_begin(Range), adl_end(Range));
1563 }
1564
1565 /// Wrapper function around std::count to count the number of times an element
1566 /// \p Element occurs in the given range \p Range.
1567 template <typename R, typename E> auto count(R &&Range, const E &Element) {
1568   return std::count(adl_begin(Range), adl_end(Range), Element);
1569 }
1570
1571 /// Wrapper function around std::count_if to count the number of times an
1572 /// element satisfying a given predicate occurs in a range.
1573 template <typename R, typename UnaryPredicate>
1574 auto count_if(R &&Range, UnaryPredicate P) {
1575   return std::count_if(adl_begin(Range), adl_end(Range), P);
1576 }
1577
1578 /// Wrapper function around std::transform to apply a function to a range and
1579 /// store the result elsewhere.
1580 template <typename R, typename OutputIt, typename UnaryPredicate>
1581 OutputIt transform(R &&Range, OutputIt d_first, UnaryPredicate P) {
1582   return std::transform(adl_begin(Range), adl_end(Range), d_first, P);
1583 }
1584
1585 /// Provide wrappers to std::partition which take ranges instead of having to
1586 /// pass begin/end explicitly.
1587 template <typename R, typename UnaryPredicate>
1588 auto partition(R &&Range, UnaryPredicate P) {
1589   return std::partition(adl_begin(Range), adl_end(Range), P);
1590 }
1591
1592 /// Provide wrappers to std::lower_bound which take ranges instead of having to
1593 /// pass begin/end explicitly.
1594 template <typename R, typename T> auto lower_bound(R &&Range, T &&Value) {
1595   return std::lower_bound(adl_begin(Range), adl_end(Range),
1596                           std::forward<T>(Value));
1597 }
1598
1599 template <typename R, typename T, typename Compare>
1600 auto lower_bound(R &&Range, T &&Value, Compare C) {
1601   return std::lower_bound(adl_begin(Range), adl_end(Range),
1602                           std::forward<T>(Value), C);
1603 }
1604
1605 /// Provide wrappers to std::upper_bound which take ranges instead of having to
1606 /// pass begin/end explicitly.
1607 template <typename R, typename T> auto upper_bound(R &&Range, T &&Value) {
1608   return std::upper_bound(adl_begin(Range), adl_end(Range),
1609                           std::forward<T>(Value));
1610 }
1611
1612 template <typename R, typename T, typename Compare>
1613 auto upper_bound(R &&Range, T &&Value, Compare C) {
1614   return std::upper_bound(adl_begin(Range), adl_end(Range),
1615                           std::forward<T>(Value), C);
1616 }
1617
1618 template <typename R>
1619 void stable_sort(R &&Range) {
1620   std::stable_sort(adl_begin(Range), adl_end(Range));
1621 }
1622
1623 template <typename R, typename Compare>
1624 void stable_sort(R &&Range, Compare C) {
1625   std::stable_sort(adl_begin(Range), adl_end(Range), C);
1626 }
1627
1628 /// Binary search for the first iterator in a range where a predicate is false.
1629 /// Requires that C is always true below some limit, and always false above it.
1630 template <typename R, typename Predicate,
1631           typename Val = decltype(*adl_begin(std::declval<R>()))>
1632 auto partition_point(R &&Range, Predicate P) {
1633   return std::partition_point(adl_begin(Range), adl_end(Range), P);
1634 }
1635
1636 /// Wrapper function around std::equal to detect if all elements
1637 /// in a container are same.
1638 template <typename R>
1639 bool is_splat(R &&Range) {
1640   size_t range_size = size(Range);
1641   return range_size != 0 && (range_size == 1 ||
1642          std::equal(adl_begin(Range) + 1, adl_end(Range), adl_begin(Range)));
1643 }
1644
1645 /// Provide a container algorithm similar to C++ Library Fundamentals v2's
1646 /// `erase_if` which is equivalent to:
1647 ///
1648 ///   C.erase(remove_if(C, pred), C.end());
1649 ///
1650 /// This version works for any container with an erase method call accepting
1651 /// two iterators.
1652 template <typename Container, typename UnaryPredicate>
1653 void erase_if(Container &C, UnaryPredicate P) {
1654   C.erase(remove_if(C, P), C.end());
1655 }
1656
1657 /// Given a sequence container Cont, replace the range [ContIt, ContEnd) with
1658 /// the range [ValIt, ValEnd) (which is not from the same container).
1659 template<typename Container, typename RandomAccessIterator>
1660 void replace(Container &Cont, typename Container::iterator ContIt,
1661              typename Container::iterator ContEnd, RandomAccessIterator ValIt,
1662              RandomAccessIterator ValEnd) {
1663   while (true) {
1664     if (ValIt == ValEnd) {
1665       Cont.erase(ContIt, ContEnd);
1666       return;
1667     } else if (ContIt == ContEnd) {
1668       Cont.insert(ContIt, ValIt, ValEnd);
1669       return;
1670     }
1671     *ContIt++ = *ValIt++;
1672   }
1673 }
1674
1675 /// Given a sequence container Cont, replace the range [ContIt, ContEnd) with
1676 /// the range R.
1677 template<typename Container, typename Range = std::initializer_list<
1678                                  typename Container::value_type>>
1679 void replace(Container &Cont, typename Container::iterator ContIt,
1680              typename Container::iterator ContEnd, Range R) {
1681   replace(Cont, ContIt, ContEnd, R.begin(), R.end());
1682 }
1683
1684 /// An STL-style algorithm similar to std::for_each that applies a second
1685 /// functor between every pair of elements.
1686 ///
1687 /// This provides the control flow logic to, for example, print a
1688 /// comma-separated list:
1689 /// \code
1690 ///   interleave(names.begin(), names.end(),
1691 ///              [&](StringRef name) { os << name; },
1692 ///              [&] { os << ", "; });
1693 /// \endcode
1694 template <typename ForwardIterator, typename UnaryFunctor,
1695           typename NullaryFunctor,
1696           typename = typename std::enable_if<
1697               !std::is_constructible<StringRef, UnaryFunctor>::value &&
1698               !std::is_constructible<StringRef, NullaryFunctor>::value>::type>
1699 inline void interleave(ForwardIterator begin, ForwardIterator end,
1700                        UnaryFunctor each_fn, NullaryFunctor between_fn) {
1701   if (begin == end)
1702     return;
1703   each_fn(*begin);
1704   ++begin;
1705   for (; begin != end; ++begin) {
1706     between_fn();
1707     each_fn(*begin);
1708   }
1709 }
1710
1711 template <typename Container, typename UnaryFunctor, typename NullaryFunctor,
1712           typename = typename std::enable_if<
1713               !std::is_constructible<StringRef, UnaryFunctor>::value &&
1714               !std::is_constructible<StringRef, NullaryFunctor>::value>::type>
1715 inline void interleave(const Container &c, UnaryFunctor each_fn,
1716                        NullaryFunctor between_fn) {
1717   interleave(c.begin(), c.end(), each_fn, between_fn);
1718 }
1719
1720 /// Overload of interleave for the common case of string separator.
1721 template <typename Container, typename UnaryFunctor, typename StreamT,
1722           typename T = detail::ValueOfRange<Container>>
1723 inline void interleave(const Container &c, StreamT &os, UnaryFunctor each_fn,
1724                        const StringRef &separator) {
1725   interleave(c.begin(), c.end(), each_fn, [&] { os << separator; });
1726 }
1727 template <typename Container, typename StreamT,
1728           typename T = detail::ValueOfRange<Container>>
1729 inline void interleave(const Container &c, StreamT &os,
1730                        const StringRef &separator) {
1731   interleave(
1732       c, os, [&](const T &a) { os << a; }, separator);
1733 }
1734
1735 template <typename Container, typename UnaryFunctor, typename StreamT,
1736           typename T = detail::ValueOfRange<Container>>
1737 inline void interleaveComma(const Container &c, StreamT &os,
1738                             UnaryFunctor each_fn) {
1739   interleave(c, os, each_fn, ", ");
1740 }
1741 template <typename Container, typename StreamT,
1742           typename T = detail::ValueOfRange<Container>>
1743 inline void interleaveComma(const Container &c, StreamT &os) {
1744   interleaveComma(c, os, [&](const T &a) { os << a; });
1745 }
1746
1747 //===----------------------------------------------------------------------===//
1748 //     Extra additions to <memory>
1749 //===----------------------------------------------------------------------===//
1750
1751 struct FreeDeleter {
1752   void operator()(void* v) {
1753     ::free(v);
1754   }
1755 };
1756
1757 template<typename First, typename Second>
1758 struct pair_hash {
1759   size_t operator()(const std::pair<First, Second> &P) const {
1760     return std::hash<First>()(P.first) * 31 + std::hash<Second>()(P.second);
1761   }
1762 };
1763
1764 /// Binary functor that adapts to any other binary functor after dereferencing
1765 /// operands.
1766 template <typename T> struct deref {
1767   T func;
1768
1769   // Could be further improved to cope with non-derivable functors and
1770   // non-binary functors (should be a variadic template member function
1771   // operator()).
1772   template <typename A, typename B> auto operator()(A &lhs, B &rhs) const {
1773     assert(lhs);
1774     assert(rhs);
1775     return func(*lhs, *rhs);
1776   }
1777 };
1778
1779 namespace detail {
1780
1781 template <typename R> class enumerator_iter;
1782
1783 template <typename R> struct result_pair {
1784   using value_reference =
1785       typename std::iterator_traits<IterOfRange<R>>::reference;
1786
1787   friend class enumerator_iter<R>;
1788
1789   result_pair() = default;
1790   result_pair(std::size_t Index, IterOfRange<R> Iter)
1791       : Index(Index), Iter(Iter) {}
1792
1793   result_pair<R>(const result_pair<R> &Other)
1794       : Index(Other.Index), Iter(Other.Iter) {}
1795   result_pair<R> &operator=(const result_pair<R> &Other) {
1796     Index = Other.Index;
1797     Iter = Other.Iter;
1798     return *this;
1799   }
1800
1801   std::size_t index() const { return Index; }
1802   const value_reference value() const { return *Iter; }
1803   value_reference value() { return *Iter; }
1804
1805 private:
1806   std::size_t Index = std::numeric_limits<std::size_t>::max();
1807   IterOfRange<R> Iter;
1808 };
1809
1810 template <typename R>
1811 class enumerator_iter
1812     : public iterator_facade_base<
1813           enumerator_iter<R>, std::forward_iterator_tag, result_pair<R>,
1814           typename std::iterator_traits<IterOfRange<R>>::difference_type,
1815           typename std::iterator_traits<IterOfRange<R>>::pointer,
1816           typename std::iterator_traits<IterOfRange<R>>::reference> {
1817   using result_type = result_pair<R>;
1818
1819 public:
1820   explicit enumerator_iter(IterOfRange<R> EndIter)
1821       : Result(std::numeric_limits<size_t>::max(), EndIter) {}
1822
1823   enumerator_iter(std::size_t Index, IterOfRange<R> Iter)
1824       : Result(Index, Iter) {}
1825
1826   result_type &operator*() { return Result; }
1827   const result_type &operator*() const { return Result; }
1828
1829   enumerator_iter<R> &operator++() {
1830     assert(Result.Index != std::numeric_limits<size_t>::max());
1831     ++Result.Iter;
1832     ++Result.Index;
1833     return *this;
1834   }
1835
1836   bool operator==(const enumerator_iter<R> &RHS) const {
1837     // Don't compare indices here, only iterators.  It's possible for an end
1838     // iterator to have different indices depending on whether it was created
1839     // by calling std::end() versus incrementing a valid iterator.
1840     return Result.Iter == RHS.Result.Iter;
1841   }
1842
1843   enumerator_iter<R>(const enumerator_iter<R> &Other) : Result(Other.Result) {}
1844   enumerator_iter<R> &operator=(const enumerator_iter<R> &Other) {
1845     Result = Other.Result;
1846     return *this;
1847   }
1848
1849 private:
1850   result_type Result;
1851 };
1852
1853 template <typename R> class enumerator {
1854 public:
1855   explicit enumerator(R &&Range) : TheRange(std::forward<R>(Range)) {}
1856
1857   enumerator_iter<R> begin() {
1858     return enumerator_iter<R>(0, std::begin(TheRange));
1859   }
1860
1861   enumerator_iter<R> end() {
1862     return enumerator_iter<R>(std::end(TheRange));
1863   }
1864
1865 private:
1866   R TheRange;
1867 };
1868
1869 } // end namespace detail
1870
1871 /// Given an input range, returns a new range whose values are are pair (A,B)
1872 /// such that A is the 0-based index of the item in the sequence, and B is
1873 /// the value from the original sequence.  Example:
1874 ///
1875 /// std::vector<char> Items = {'A', 'B', 'C', 'D'};
1876 /// for (auto X : enumerate(Items)) {
1877 ///   printf("Item %d - %c\n", X.index(), X.value());
1878 /// }
1879 ///
1880 /// Output:
1881 ///   Item 0 - A
1882 ///   Item 1 - B
1883 ///   Item 2 - C
1884 ///   Item 3 - D
1885 ///
1886 template <typename R> detail::enumerator<R> enumerate(R &&TheRange) {
1887   return detail::enumerator<R>(std::forward<R>(TheRange));
1888 }
1889
1890 namespace detail {
1891
1892 template <typename F, typename Tuple, std::size_t... I>
1893 decltype(auto) apply_tuple_impl(F &&f, Tuple &&t, std::index_sequence<I...>) {
1894   return std::forward<F>(f)(std::get<I>(std::forward<Tuple>(t))...);
1895 }
1896
1897 } // end namespace detail
1898
1899 /// Given an input tuple (a1, a2, ..., an), pass the arguments of the
1900 /// tuple variadically to f as if by calling f(a1, a2, ..., an) and
1901 /// return the result.
1902 template <typename F, typename Tuple>
1903 decltype(auto) apply_tuple(F &&f, Tuple &&t) {
1904   using Indices = std::make_index_sequence<
1905       std::tuple_size<typename std::decay<Tuple>::type>::value>;
1906
1907   return detail::apply_tuple_impl(std::forward<F>(f), std::forward<Tuple>(t),
1908                                   Indices{});
1909 }
1910
1911 /// Return true if the sequence [Begin, End) has exactly N items. Runs in O(N)
1912 /// time. Not meant for use with random-access iterators.
1913 /// Can optionally take a predicate to filter lazily some items.
1914 template<typename IterTy,
1915          typename Pred = bool (*)(const decltype(*std::declval<IterTy>()) &)>
1916 bool hasNItems(
1917     IterTy &&Begin, IterTy &&End, unsigned N,
1918     Pred &&ShouldBeCounted =
1919         [](const decltype(*std::declval<IterTy>()) &) { return true; },
1920     std::enable_if_t<
1921         !std::is_same<typename std::iterator_traits<std::remove_reference_t<
1922                           decltype(Begin)>>::iterator_category,
1923                       std::random_access_iterator_tag>::value,
1924         void> * = nullptr) {
1925   for (; N; ++Begin) {
1926     if (Begin == End)
1927       return false; // Too few.
1928     N -= ShouldBeCounted(*Begin);
1929   }
1930   for (; Begin != End; ++Begin)
1931     if (ShouldBeCounted(*Begin))
1932       return false; // Too many.
1933   return true;
1934 }
1935
1936 /// Return true if the sequence [Begin, End) has N or more items. Runs in O(N)
1937 /// time. Not meant for use with random-access iterators.
1938 /// Can optionally take a predicate to lazily filter some items.
1939 template<typename IterTy,
1940          typename Pred = bool (*)(const decltype(*std::declval<IterTy>()) &)>
1941 bool hasNItemsOrMore(
1942     IterTy &&Begin, IterTy &&End, unsigned N,
1943     Pred &&ShouldBeCounted =
1944         [](const decltype(*std::declval<IterTy>()) &) { return true; },
1945     std::enable_if_t<
1946         !std::is_same<typename std::iterator_traits<std::remove_reference_t<
1947                           decltype(Begin)>>::iterator_category,
1948                       std::random_access_iterator_tag>::value,
1949         void> * = nullptr) {
1950   for (; N; ++Begin) {
1951     if (Begin == End)
1952       return false; // Too few.
1953     N -= ShouldBeCounted(*Begin);
1954   }
1955   return true;
1956 }
1957
1958 /// Returns true if the sequence [Begin, End) has N or less items. Can
1959 /// optionally take a predicate to lazily filter some items.
1960 template <typename IterTy,
1961           typename Pred = bool (*)(const decltype(*std::declval<IterTy>()) &)>
1962 bool hasNItemsOrLess(
1963     IterTy &&Begin, IterTy &&End, unsigned N,
1964     Pred &&ShouldBeCounted = [](const decltype(*std::declval<IterTy>()) &) {
1965       return true;
1966     }) {
1967   assert(N != std::numeric_limits<unsigned>::max());
1968   return !hasNItemsOrMore(Begin, End, N + 1, ShouldBeCounted);
1969 }
1970
1971 /// Returns true if the given container has exactly N items
1972 template <typename ContainerTy> bool hasNItems(ContainerTy &&C, unsigned N) {
1973   return hasNItems(std::begin(C), std::end(C), N);
1974 }
1975
1976 /// Returns true if the given container has N or more items
1977 template <typename ContainerTy>
1978 bool hasNItemsOrMore(ContainerTy &&C, unsigned N) {
1979   return hasNItemsOrMore(std::begin(C), std::end(C), N);
1980 }
1981
1982 /// Returns true if the given container has N or less items
1983 template <typename ContainerTy>
1984 bool hasNItemsOrLess(ContainerTy &&C, unsigned N) {
1985   return hasNItemsOrLess(std::begin(C), std::end(C), N);
1986 }
1987
1988 /// Returns a raw pointer that represents the same address as the argument.
1989 ///
1990 /// This implementation can be removed once we move to C++20 where it's defined
1991 /// as std::to_address().
1992 ///
1993 /// The std::pointer_traits<>::to_address(p) variations of these overloads has
1994 /// not been implemented.
1995 template <class Ptr> auto to_address(const Ptr &P) { return P.operator->(); }
1996 template <class T> constexpr T *to_address(T *P) { return P; }
1997
1998 } // end namespace llvm
1999
2000 #endif // LLVM_ADT_STLEXTRAS_H