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