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