Subversion Repositories QNX 8.QNX8 LLVM/Clang compiler suite

Rev

Blame | Last modification | View Log | Download | RSS feed

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