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