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