LLVM  7.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"
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 //===----------------------------------------------------------------------===//
74 // Extra additions to <functional>
75 //===----------------------------------------------------------------------===//
76 
77 template <class Ty> struct identity {
78  using argument_type = Ty;
79 
80  Ty &operator()(Ty &self) const {
81  return self;
82  }
83  const Ty &operator()(const Ty &self) const {
84  return self;
85  }
86 };
87 
88 template <class Ty> struct less_ptr {
89  bool operator()(const Ty* left, const Ty* right) const {
90  return *left < *right;
91  }
92 };
93 
94 template <class Ty> struct greater_ptr {
95  bool operator()(const Ty* left, const Ty* right) const {
96  return *right < *left;
97  }
98 };
99 
100 /// An efficient, type-erasing, non-owning reference to a callable. This is
101 /// intended for use as the type of a function parameter that is not used
102 /// after the function in question returns.
103 ///
104 /// This class does not own the callable, so it is not in general safe to store
105 /// a function_ref.
106 template<typename Fn> class function_ref;
107 
108 template<typename Ret, typename ...Params>
109 class function_ref<Ret(Params...)> {
110  Ret (*callback)(intptr_t callable, Params ...params) = nullptr;
111  intptr_t callable;
112 
113  template<typename Callable>
114  static Ret callback_fn(intptr_t callable, Params ...params) {
115  return (*reinterpret_cast<Callable*>(callable))(
116  std::forward<Params>(params)...);
117  }
118 
119 public:
120  function_ref() = default;
121  function_ref(std::nullptr_t) {}
122 
123  template <typename Callable>
124  function_ref(Callable &&callable,
125  typename std::enable_if<
126  !std::is_same<typename std::remove_reference<Callable>::type,
127  function_ref>::value>::type * = nullptr)
128  : callback(callback_fn<typename std::remove_reference<Callable>::type>),
129  callable(reinterpret_cast<intptr_t>(&callable)) {}
130 
131  Ret operator()(Params ...params) const {
132  return callback(callable, std::forward<Params>(params)...);
133  }
134 
135  operator bool() const { return callback; }
136 };
137 
138 // deleter - Very very very simple method that is used to invoke operator
139 // delete on something. It is used like this:
140 //
141 // for_each(V.begin(), B.end(), deleter<Interval>);
142 template <class T>
143 inline void deleter(T *Ptr) {
144  delete Ptr;
145 }
146 
147 //===----------------------------------------------------------------------===//
148 // Extra additions to <iterator>
149 //===----------------------------------------------------------------------===//
150 
151 namespace adl_detail {
152 
153 using std::begin;
154 
155 template <typename ContainerTy>
156 auto adl_begin(ContainerTy &&container)
157  -> decltype(begin(std::forward<ContainerTy>(container))) {
158  return begin(std::forward<ContainerTy>(container));
159 }
160 
161 using std::end;
162 
163 template <typename ContainerTy>
164 auto adl_end(ContainerTy &&container)
165  -> decltype(end(std::forward<ContainerTy>(container))) {
166  return end(std::forward<ContainerTy>(container));
167 }
168 
169 using std::swap;
170 
171 template <typename T>
172 void adl_swap(T &&lhs, T &&rhs) noexcept(noexcept(swap(std::declval<T>(),
173  std::declval<T>()))) {
174  swap(std::forward<T>(lhs), std::forward<T>(rhs));
175 }
176 
177 } // end namespace adl_detail
178 
179 template <typename ContainerTy>
180 auto adl_begin(ContainerTy &&container)
181  -> decltype(adl_detail::adl_begin(std::forward<ContainerTy>(container))) {
182  return adl_detail::adl_begin(std::forward<ContainerTy>(container));
183 }
184 
185 template <typename ContainerTy>
186 auto adl_end(ContainerTy &&container)
187  -> decltype(adl_detail::adl_end(std::forward<ContainerTy>(container))) {
188  return adl_detail::adl_end(std::forward<ContainerTy>(container));
189 }
190 
191 template <typename T>
192 void adl_swap(T &&lhs, T &&rhs) noexcept(
193  noexcept(adl_detail::adl_swap(std::declval<T>(), std::declval<T>()))) {
194  adl_detail::adl_swap(std::forward<T>(lhs), std::forward<T>(rhs));
195 }
196 
197 // mapped_iterator - This is a simple iterator adapter that causes a function to
198 // be applied whenever operator* is invoked on the iterator.
199 
200 template <typename ItTy, typename FuncTy,
201  typename FuncReturnTy =
202  decltype(std::declval<FuncTy>()(*std::declval<ItTy>()))>
204  : public iterator_adaptor_base<
205  mapped_iterator<ItTy, FuncTy>, ItTy,
206  typename std::iterator_traits<ItTy>::iterator_category,
207  typename std::remove_reference<FuncReturnTy>::type> {
208 public:
209  mapped_iterator(ItTy U, FuncTy F)
210  : mapped_iterator::iterator_adaptor_base(std::move(U)), F(std::move(F)) {}
211 
212  ItTy getCurrent() { return this->I; }
213 
214  FuncReturnTy operator*() { return F(*this->I); }
215 
216 private:
217  FuncTy F;
218 };
219 
220 // map_iterator - Provide a convenient way to create mapped_iterators, just like
221 // make_pair is useful for creating pairs...
222 template <class ItTy, class FuncTy>
224  return mapped_iterator<ItTy, FuncTy>(std::move(I), std::move(F));
225 }
226 
227 /// Helper to determine if type T has a member called rbegin().
228 template <typename Ty> class has_rbegin_impl {
229  using yes = char[1];
230  using no = char[2];
231 
232  template <typename Inner>
233  static yes& test(Inner *I, decltype(I->rbegin()) * = nullptr);
234 
235  template <typename>
236  static no& test(...);
237 
238 public:
239  static const bool value = sizeof(test<Ty>(nullptr)) == sizeof(yes);
240 };
241 
242 /// Metafunction to determine if T& or T has a member called rbegin().
243 template <typename Ty>
244 struct has_rbegin : has_rbegin_impl<typename std::remove_reference<Ty>::type> {
245 };
246 
247 // Returns an iterator_range over the given container which iterates in reverse.
248 // Note that the container must have rbegin()/rend() methods for this to work.
249 template <typename ContainerTy>
250 auto reverse(ContainerTy &&C,
251  typename std::enable_if<has_rbegin<ContainerTy>::value>::type * =
252  nullptr) -> decltype(make_range(C.rbegin(), C.rend())) {
253  return make_range(C.rbegin(), C.rend());
254 }
255 
256 // Returns a std::reverse_iterator wrapped around the given iterator.
257 template <typename IteratorTy>
258 std::reverse_iterator<IteratorTy> make_reverse_iterator(IteratorTy It) {
259  return std::reverse_iterator<IteratorTy>(It);
260 }
261 
262 // Returns an iterator_range over the given container which iterates in reverse.
263 // Note that the container must have begin()/end() methods which return
264 // bidirectional iterators for this to work.
265 template <typename ContainerTy>
266 auto reverse(
267  ContainerTy &&C,
268  typename std::enable_if<!has_rbegin<ContainerTy>::value>::type * = nullptr)
273 }
274 
275 /// An iterator adaptor that filters the elements of given inner iterators.
276 ///
277 /// The predicate parameter should be a callable object that accepts the wrapped
278 /// iterator's reference type and returns a bool. When incrementing or
279 /// decrementing the iterator, it will call the predicate on each element and
280 /// skip any where it returns false.
281 ///
282 /// \code
283 /// int A[] = { 1, 2, 3, 4 };
284 /// auto R = make_filter_range(A, [](int N) { return N % 2 == 1; });
285 /// // R contains { 1, 3 }.
286 /// \endcode
287 ///
288 /// Note: filter_iterator_base implements support for forward iteration.
289 /// filter_iterator_impl exists to provide support for bidirectional iteration,
290 /// conditional on whether the wrapped iterator supports it.
291 template <typename WrappedIteratorT, typename PredicateT, typename IterTag>
293  : public iterator_adaptor_base<
294  filter_iterator_base<WrappedIteratorT, PredicateT, IterTag>,
295  WrappedIteratorT,
296  typename std::common_type<
297  IterTag, typename std::iterator_traits<
298  WrappedIteratorT>::iterator_category>::type> {
301  WrappedIteratorT,
302  typename std::common_type<
303  IterTag, typename std::iterator_traits<
304  WrappedIteratorT>::iterator_category>::type>;
305 
306 protected:
307  WrappedIteratorT End;
308  PredicateT Pred;
309 
310  void findNextValid() {
311  while (this->I != End && !Pred(*this->I))
312  BaseT::operator++();
313  }
314 
315  // Construct the iterator. The begin iterator needs to know where the end
316  // is, so that it can properly stop when it gets there. The end iterator only
317  // needs the predicate to support bidirectional iteration.
318  filter_iterator_base(WrappedIteratorT Begin, WrappedIteratorT End,
319  PredicateT Pred)
320  : BaseT(Begin), End(End), Pred(Pred) {
321  findNextValid();
322  }
323 
324 public:
325  using BaseT::operator++;
326 
328  BaseT::operator++();
329  findNextValid();
330  return *this;
331  }
332 };
333 
334 /// Specialization of filter_iterator_base for forward iteration only.
335 template <typename WrappedIteratorT, typename PredicateT,
336  typename IterTag = std::forward_iterator_tag>
338  : public filter_iterator_base<WrappedIteratorT, PredicateT, IterTag> {
340 
341 public:
342  filter_iterator_impl(WrappedIteratorT Begin, WrappedIteratorT End,
343  PredicateT Pred)
344  : BaseT(Begin, End, Pred) {}
345 };
346 
347 /// Specialization of filter_iterator_base for bidirectional iteration.
348 template <typename WrappedIteratorT, typename PredicateT>
349 class filter_iterator_impl<WrappedIteratorT, PredicateT,
350  std::bidirectional_iterator_tag>
351  : public filter_iterator_base<WrappedIteratorT, PredicateT,
352  std::bidirectional_iterator_tag> {
353  using BaseT = filter_iterator_base<WrappedIteratorT, PredicateT,
354  std::bidirectional_iterator_tag>;
355  void findPrevValid() {
356  while (!this->Pred(*this->I))
357  BaseT::operator--();
358  }
359 
360 public:
361  using BaseT::operator--;
362 
363  filter_iterator_impl(WrappedIteratorT Begin, WrappedIteratorT End,
364  PredicateT Pred)
365  : BaseT(Begin, End, Pred) {}
366 
368  BaseT::operator--();
369  findPrevValid();
370  return *this;
371  }
372 };
373 
374 namespace detail {
375 
376 template <bool is_bidirectional> struct fwd_or_bidi_tag_impl {
377  using type = std::forward_iterator_tag;
378 };
379 
380 template <> struct fwd_or_bidi_tag_impl<true> {
381  using type = std::bidirectional_iterator_tag;
382 };
383 
384 /// Helper which sets its type member to forward_iterator_tag if the category
385 /// of \p IterT does not derive from bidirectional_iterator_tag, and to
386 /// bidirectional_iterator_tag otherwise.
387 template <typename IterT> struct fwd_or_bidi_tag {
388  using type = typename fwd_or_bidi_tag_impl<std::is_base_of<
389  std::bidirectional_iterator_tag,
390  typename std::iterator_traits<IterT>::iterator_category>::value>::type;
391 };
392 
393 } // namespace detail
394 
395 /// Defines filter_iterator to a suitable specialization of
396 /// filter_iterator_impl, based on the underlying iterator's category.
397 template <typename WrappedIteratorT, typename PredicateT>
399  WrappedIteratorT, PredicateT,
401 
402 /// Convenience function that takes a range of elements and a predicate,
403 /// and return a new filter_iterator range.
404 ///
405 /// FIXME: Currently if RangeT && is a rvalue reference to a temporary, the
406 /// lifetime of that temporary is not kept by the returned range object, and the
407 /// temporary is going to be dropped on the floor after the make_iterator_range
408 /// full expression that contains this function call.
409 template <typename RangeT, typename PredicateT>
411 make_filter_range(RangeT &&Range, PredicateT Pred) {
412  using FilterIteratorT =
414  return make_range(
415  FilterIteratorT(std::begin(std::forward<RangeT>(Range)),
416  std::end(std::forward<RangeT>(Range)), Pred),
417  FilterIteratorT(std::end(std::forward<RangeT>(Range)),
418  std::end(std::forward<RangeT>(Range)), Pred));
419 }
420 
421 // forward declarations required by zip_shortest/zip_first
422 template <typename R, typename UnaryPredicate>
423 bool all_of(R &&range, UnaryPredicate P);
424 
425 template <size_t... I> struct index_sequence;
426 
427 template <class... Ts> struct index_sequence_for;
428 
429 namespace detail {
430 
431 using std::declval;
432 
433 // We have to alias this since inlining the actual type at the usage site
434 // in the parameter list of iterator_facade_base<> below ICEs MSVC 2017.
435 template<typename... Iters> struct ZipTupleType {
436  using type = std::tuple<decltype(*declval<Iters>())...>;
437 };
438 
439 template <typename ZipType, typename... Iters>
441  ZipType, typename std::common_type<std::bidirectional_iterator_tag,
442  typename std::iterator_traits<
443  Iters>::iterator_category...>::type,
444  // ^ TODO: Implement random access methods.
445  typename ZipTupleType<Iters...>::type,
446  typename std::iterator_traits<typename std::tuple_element<
447  0, std::tuple<Iters...>>::type>::difference_type,
448  // ^ FIXME: This follows boost::make_zip_iterator's assumption that all
449  // inner iterators have the same difference_type. It would fail if, for
450  // instance, the second field's difference_type were non-numeric while the
451  // first is.
452  typename ZipTupleType<Iters...>::type *,
453  typename ZipTupleType<Iters...>::type>;
454 
455 template <typename ZipType, typename... Iters>
456 struct zip_common : public zip_traits<ZipType, Iters...> {
457  using Base = zip_traits<ZipType, Iters...>;
458  using value_type = typename Base::value_type;
459 
460  std::tuple<Iters...> iterators;
461 
462 protected:
463  template <size_t... Ns> value_type deref(index_sequence<Ns...>) const {
464  return value_type(*std::get<Ns>(iterators)...);
465  }
466 
467  template <size_t... Ns>
468  decltype(iterators) tup_inc(index_sequence<Ns...>) const {
469  return std::tuple<Iters...>(std::next(std::get<Ns>(iterators))...);
470  }
471 
472  template <size_t... Ns>
473  decltype(iterators) tup_dec(index_sequence<Ns...>) const {
474  return std::tuple<Iters...>(std::prev(std::get<Ns>(iterators))...);
475  }
476 
477 public:
478  zip_common(Iters &&... ts) : iterators(std::forward<Iters>(ts)...) {}
479 
481 
482  const value_type operator*() const {
484  }
485 
486  ZipType &operator++() {
487  iterators = tup_inc(index_sequence_for<Iters...>{});
488  return *reinterpret_cast<ZipType *>(this);
489  }
490 
491  ZipType &operator--() {
492  static_assert(Base::IsBidirectional,
493  "All inner iterators must be at least bidirectional.");
494  iterators = tup_dec(index_sequence_for<Iters...>{});
495  return *reinterpret_cast<ZipType *>(this);
496  }
497 };
498 
499 template <typename... Iters>
500 struct zip_first : public zip_common<zip_first<Iters...>, Iters...> {
501  using Base = zip_common<zip_first<Iters...>, Iters...>;
502 
503  bool operator==(const zip_first<Iters...> &other) const {
504  return std::get<0>(this->iterators) == std::get<0>(other.iterators);
505  }
506 
507  zip_first(Iters &&... ts) : Base(std::forward<Iters>(ts)...) {}
508 };
509 
510 template <typename... Iters>
511 class zip_shortest : public zip_common<zip_shortest<Iters...>, Iters...> {
512  template <size_t... Ns>
513  bool test(const zip_shortest<Iters...> &other, index_sequence<Ns...>) const {
514  return all_of(std::initializer_list<bool>{std::get<Ns>(this->iterators) !=
515  std::get<Ns>(other.iterators)...},
516  identity<bool>{});
517  }
518 
519 public:
520  using Base = zip_common<zip_shortest<Iters...>, Iters...>;
521 
522  zip_shortest(Iters &&... ts) : Base(std::forward<Iters>(ts)...) {}
523 
524  bool operator==(const zip_shortest<Iters...> &other) const {
525  return !test(other, index_sequence_for<Iters...>{});
526  }
527 };
528 
529 template <template <typename...> class ItType, typename... Args> class zippy {
530 public:
531  using iterator = ItType<decltype(std::begin(std::declval<Args>()))...>;
532  using iterator_category = typename iterator::iterator_category;
533  using value_type = typename iterator::value_type;
534  using difference_type = typename iterator::difference_type;
535  using pointer = typename iterator::pointer;
536  using reference = typename iterator::reference;
537 
538 private:
539  std::tuple<Args...> ts;
540 
541  template <size_t... Ns> iterator begin_impl(index_sequence<Ns...>) const {
542  return iterator(std::begin(std::get<Ns>(ts))...);
543  }
544  template <size_t... Ns> iterator end_impl(index_sequence<Ns...>) const {
545  return iterator(std::end(std::get<Ns>(ts))...);
546  }
547 
548 public:
549  zippy(Args &&... ts_) : ts(std::forward<Args>(ts_)...) {}
550 
551  iterator begin() const { return begin_impl(index_sequence_for<Args...>{}); }
552  iterator end() const { return end_impl(index_sequence_for<Args...>{}); }
553 };
554 
555 } // end namespace detail
556 
557 /// zip iterator for two or more iteratable types.
558 template <typename T, typename U, typename... Args>
560  Args &&... args) {
561  return detail::zippy<detail::zip_shortest, T, U, Args...>(
562  std::forward<T>(t), std::forward<U>(u), std::forward<Args>(args)...);
563 }
564 
565 /// zip iterator that, for the sake of efficiency, assumes the first iteratee to
566 /// be the shortest.
567 template <typename T, typename U, typename... Args>
569  Args &&... args) {
570  return detail::zippy<detail::zip_first, T, U, Args...>(
571  std::forward<T>(t), std::forward<U>(u), std::forward<Args>(args)...);
572 }
573 
574 /// Iterator wrapper that concatenates sequences together.
575 ///
576 /// This can concatenate different iterators, even with different types, into
577 /// a single iterator provided the value types of all the concatenated
578 /// iterators expose `reference` and `pointer` types that can be converted to
579 /// `ValueT &` and `ValueT *` respectively. It doesn't support more
580 /// interesting/customized pointer or reference types.
581 ///
582 /// Currently this only supports forward or higher iterator categories as
583 /// inputs and always exposes a forward iterator interface.
584 template <typename ValueT, typename... IterTs>
586  : public iterator_facade_base<concat_iterator<ValueT, IterTs...>,
587  std::forward_iterator_tag, ValueT> {
588  using BaseT = typename concat_iterator::iterator_facade_base;
589 
590  /// We store both the current and end iterators for each concatenated
591  /// sequence in a tuple of pairs.
592  ///
593  /// Note that something like iterator_range seems nice at first here, but the
594  /// range properties are of little benefit and end up getting in the way
595  /// because we need to do mutation on the current iterators.
596  std::tuple<std::pair<IterTs, IterTs>...> IterPairs;
597 
598  /// Attempts to increment a specific iterator.
599  ///
600  /// Returns true if it was able to increment the iterator. Returns false if
601  /// the iterator is already at the end iterator.
602  template <size_t Index> bool incrementHelper() {
603  auto &IterPair = std::get<Index>(IterPairs);
604  if (IterPair.first == IterPair.second)
605  return false;
606 
607  ++IterPair.first;
608  return true;
609  }
610 
611  /// Increments the first non-end iterator.
612  ///
613  /// It is an error to call this with all iterators at the end.
614  template <size_t... Ns> void increment(index_sequence<Ns...>) {
615  // Build a sequence of functions to increment each iterator if possible.
616  bool (concat_iterator::*IncrementHelperFns[])() = {
617  &concat_iterator::incrementHelper<Ns>...};
618 
619  // Loop over them, and stop as soon as we succeed at incrementing one.
620  for (auto &IncrementHelperFn : IncrementHelperFns)
621  if ((this->*IncrementHelperFn)())
622  return;
623 
624  llvm_unreachable("Attempted to increment an end concat iterator!");
625  }
626 
627  /// Returns null if the specified iterator is at the end. Otherwise,
628  /// dereferences the iterator and returns the address of the resulting
629  /// reference.
630  template <size_t Index> ValueT *getHelper() const {
631  auto &IterPair = std::get<Index>(IterPairs);
632  if (IterPair.first == IterPair.second)
633  return nullptr;
634 
635  return &*IterPair.first;
636  }
637 
638  /// Finds the first non-end iterator, dereferences, and returns the resulting
639  /// reference.
640  ///
641  /// It is an error to call this with all iterators at the end.
642  template <size_t... Ns> ValueT &get(index_sequence<Ns...>) const {
643  // Build a sequence of functions to get from iterator if possible.
644  ValueT *(concat_iterator::*GetHelperFns[])() const = {
645  &concat_iterator::getHelper<Ns>...};
646 
647  // Loop over them, and return the first result we find.
648  for (auto &GetHelperFn : GetHelperFns)
649  if (ValueT *P = (this->*GetHelperFn)())
650  return *P;
651 
652  llvm_unreachable("Attempted to get a pointer from an end concat iterator!");
653  }
654 
655 public:
656  /// Constructs an iterator from a squence of ranges.
657  ///
658  /// We need the full range to know how to switch between each of the
659  /// iterators.
660  template <typename... RangeTs>
661  explicit concat_iterator(RangeTs &&... Ranges)
662  : IterPairs({std::begin(Ranges), std::end(Ranges)}...) {}
663 
664  using BaseT::operator++;
665 
667  increment(index_sequence_for<IterTs...>());
668  return *this;
669  }
670 
671  ValueT &operator*() const { return get(index_sequence_for<IterTs...>()); }
672 
673  bool operator==(const concat_iterator &RHS) const {
674  return IterPairs == RHS.IterPairs;
675  }
676 };
677 
678 namespace detail {
679 
680 /// Helper to store a sequence of ranges being concatenated and access them.
681 ///
682 /// This is designed to facilitate providing actual storage when temporaries
683 /// are passed into the constructor such that we can use it as part of range
684 /// based for loops.
685 template <typename ValueT, typename... RangeTs> class concat_range {
686 public:
687  using iterator =
689  decltype(std::begin(std::declval<RangeTs &>()))...>;
690 
691 private:
692  std::tuple<RangeTs...> Ranges;
693 
694  template <size_t... Ns> iterator begin_impl(index_sequence<Ns...>) {
695  return iterator(std::get<Ns>(Ranges)...);
696  }
697  template <size_t... Ns> iterator end_impl(index_sequence<Ns...>) {
698  return iterator(make_range(std::end(std::get<Ns>(Ranges)),
699  std::end(std::get<Ns>(Ranges)))...);
700  }
701 
702 public:
703  concat_range(RangeTs &&... Ranges)
704  : Ranges(std::forward<RangeTs>(Ranges)...) {}
705 
706  iterator begin() { return begin_impl(index_sequence_for<RangeTs...>{}); }
707  iterator end() { return end_impl(index_sequence_for<RangeTs...>{}); }
708 };
709 
710 } // end namespace detail
711 
712 /// Concatenated range across two or more ranges.
713 ///
714 /// The desired value type must be explicitly specified.
715 template <typename ValueT, typename... RangeTs>
716 detail::concat_range<ValueT, RangeTs...> concat(RangeTs &&... Ranges) {
717  static_assert(sizeof...(RangeTs) > 1,
718  "Need more than one range to concatenate!");
719  return detail::concat_range<ValueT, RangeTs...>(
720  std::forward<RangeTs>(Ranges)...);
721 }
722 
723 //===----------------------------------------------------------------------===//
724 // Extra additions to <utility>
725 //===----------------------------------------------------------------------===//
726 
727 /// Function object to check whether the first component of a std::pair
728 /// compares less than the first component of another std::pair.
729 struct less_first {
730  template <typename T> bool operator()(const T &lhs, const T &rhs) const {
731  return lhs.first < rhs.first;
732  }
733 };
734 
735 /// Function object to check whether the second component of a std::pair
736 /// compares less than the second component of another std::pair.
737 struct less_second {
738  template <typename T> bool operator()(const T &lhs, const T &rhs) const {
739  return lhs.second < rhs.second;
740  }
741 };
742 
743 // A subset of N3658. More stuff can be added as-needed.
744 
745 /// Represents a compile-time sequence of integers.
746 template <class T, T... I> struct integer_sequence {
747  using value_type = T;
748 
749  static constexpr size_t size() { return sizeof...(I); }
750 };
751 
752 /// Alias for the common case of a sequence of size_ts.
753 template <size_t... I>
754 struct index_sequence : integer_sequence<std::size_t, I...> {};
755 
756 template <std::size_t N, std::size_t... I>
757 struct build_index_impl : build_index_impl<N - 1, N - 1, I...> {};
758 template <std::size_t... I>
759 struct build_index_impl<0, I...> : index_sequence<I...> {};
760 
761 /// Creates a compile-time integer sequence for a parameter pack.
762 template <class... Ts>
763 struct index_sequence_for : build_index_impl<sizeof...(Ts)> {};
764 
765 /// Utility type to build an inheritance chain that makes it easy to rank
766 /// overload candidates.
767 template <int N> struct rank : rank<N - 1> {};
768 template <> struct rank<0> {};
769 
770 /// traits class for checking whether type T is one of any of the given
771 /// types in the variadic list.
772 template <typename T, typename... Ts> struct is_one_of {
773  static const bool value = false;
774 };
775 
776 template <typename T, typename U, typename... Ts>
777 struct is_one_of<T, U, Ts...> {
778  static const bool value =
779  std::is_same<T, U>::value || is_one_of<T, Ts...>::value;
780 };
781 
782 /// traits class for checking whether type T is a base class for all
783 /// the given types in the variadic list.
784 template <typename T, typename... Ts> struct are_base_of {
785  static const bool value = true;
786 };
787 
788 template <typename T, typename U, typename... Ts>
789 struct are_base_of<T, U, Ts...> {
790  static const bool value =
791  std::is_base_of<T, U>::value && are_base_of<T, Ts...>::value;
792 };
793 
794 //===----------------------------------------------------------------------===//
795 // Extra additions for arrays
796 //===----------------------------------------------------------------------===//
797 
798 /// Find the length of an array.
799 template <class T, std::size_t N>
800 constexpr inline size_t array_lengthof(T (&)[N]) {
801  return N;
802 }
803 
804 /// Adapt std::less<T> for array_pod_sort.
805 template<typename T>
806 inline int array_pod_sort_comparator(const void *P1, const void *P2) {
807  if (std::less<T>()(*reinterpret_cast<const T*>(P1),
808  *reinterpret_cast<const T*>(P2)))
809  return -1;
810  if (std::less<T>()(*reinterpret_cast<const T*>(P2),
811  *reinterpret_cast<const T*>(P1)))
812  return 1;
813  return 0;
814 }
815 
816 /// get_array_pod_sort_comparator - This is an internal helper function used to
817 /// get type deduction of T right.
818 template<typename T>
819 inline int (*get_array_pod_sort_comparator(const T &))
820  (const void*, const void*) {
821  return array_pod_sort_comparator<T>;
822 }
823 
824 /// array_pod_sort - This sorts an array with the specified start and end
825 /// extent. This is just like std::sort, except that it calls qsort instead of
826 /// using an inlined template. qsort is slightly slower than std::sort, but
827 /// most sorts are not performance critical in LLVM and std::sort has to be
828 /// template instantiated for each type, leading to significant measured code
829 /// bloat. This function should generally be used instead of std::sort where
830 /// possible.
831 ///
832 /// This function assumes that you have simple POD-like types that can be
833 /// compared with std::less and can be moved with memcpy. If this isn't true,
834 /// you should use std::sort.
835 ///
836 /// NOTE: If qsort_r were portable, we could allow a custom comparator and
837 /// default to std::less.
838 template<class IteratorTy>
839 inline void array_pod_sort(IteratorTy Start, IteratorTy End) {
840  // Don't inefficiently call qsort with one element or trigger undefined
841  // behavior with an empty sequence.
842  auto NElts = End - Start;
843  if (NElts <= 1) return;
844 #ifdef EXPENSIVE_CHECKS
845  std::mt19937 Generator(std::random_device{}());
846  std::shuffle(Start, End, Generator);
847 #endif
848  qsort(&*Start, NElts, sizeof(*Start), get_array_pod_sort_comparator(*Start));
849 }
850 
851 template <class IteratorTy>
852 inline void array_pod_sort(
853  IteratorTy Start, IteratorTy End,
854  int (*Compare)(
855  const typename std::iterator_traits<IteratorTy>::value_type *,
856  const typename std::iterator_traits<IteratorTy>::value_type *)) {
857  // Don't inefficiently call qsort with one element or trigger undefined
858  // behavior with an empty sequence.
859  auto NElts = End - Start;
860  if (NElts <= 1) return;
861 #ifdef EXPENSIVE_CHECKS
862  std::mt19937 Generator(std::random_device{}());
863  std::shuffle(Start, End, Generator);
864 #endif
865  qsort(&*Start, NElts, sizeof(*Start),
866  reinterpret_cast<int (*)(const void *, const void *)>(Compare));
867 }
868 
869 // Provide wrappers to std::sort which shuffle the elements before sorting
870 // to help uncover non-deterministic behavior (PR35135).
871 template <typename IteratorTy>
872 inline void sort(IteratorTy Start, IteratorTy End) {
873 #ifdef EXPENSIVE_CHECKS
874  std::mt19937 Generator(std::random_device{}());
875  std::shuffle(Start, End, Generator);
876 #endif
877  std::sort(Start, End);
878 }
879 
880 template <typename IteratorTy, typename Compare>
881 inline void sort(IteratorTy Start, IteratorTy End, Compare Comp) {
882 #ifdef EXPENSIVE_CHECKS
883  std::mt19937 Generator(std::random_device{}());
884  std::shuffle(Start, End, Generator);
885 #endif
886  std::sort(Start, End, Comp);
887 }
888 
889 //===----------------------------------------------------------------------===//
890 // Extra additions to <algorithm>
891 //===----------------------------------------------------------------------===//
892 
893 /// For a container of pointers, deletes the pointers and then clears the
894 /// container.
895 template<typename Container>
896 void DeleteContainerPointers(Container &C) {
897  for (auto V : C)
898  delete V;
899  C.clear();
900 }
901 
902 /// In a container of pairs (usually a map) whose second element is a pointer,
903 /// deletes the second elements and then clears the container.
904 template<typename Container>
905 void DeleteContainerSeconds(Container &C) {
906  for (auto &V : C)
907  delete V.second;
908  C.clear();
909 }
910 
911 /// Provide wrappers to std::for_each which take ranges instead of having to
912 /// pass begin/end explicitly.
913 template <typename R, typename UnaryPredicate>
914 UnaryPredicate for_each(R &&Range, UnaryPredicate P) {
915  return std::for_each(adl_begin(Range), adl_end(Range), P);
916 }
917 
918 /// Provide wrappers to std::all_of which take ranges instead of having to pass
919 /// begin/end explicitly.
920 template <typename R, typename UnaryPredicate>
921 bool all_of(R &&Range, UnaryPredicate P) {
922  return std::all_of(adl_begin(Range), adl_end(Range), P);
923 }
924 
925 /// Provide wrappers to std::any_of which take ranges instead of having to pass
926 /// begin/end explicitly.
927 template <typename R, typename UnaryPredicate>
928 bool any_of(R &&Range, UnaryPredicate P) {
929  return std::any_of(adl_begin(Range), adl_end(Range), P);
930 }
931 
932 /// Provide wrappers to std::none_of which take ranges instead of having to pass
933 /// begin/end explicitly.
934 template <typename R, typename UnaryPredicate>
935 bool none_of(R &&Range, UnaryPredicate P) {
936  return std::none_of(adl_begin(Range), adl_end(Range), P);
937 }
938 
939 /// Provide wrappers to std::find which take ranges instead of having to pass
940 /// begin/end explicitly.
941 template <typename R, typename T>
942 auto find(R &&Range, const T &Val) -> decltype(adl_begin(Range)) {
943  return std::find(adl_begin(Range), adl_end(Range), Val);
944 }
945 
946 /// Provide wrappers to std::find_if which take ranges instead of having to pass
947 /// begin/end explicitly.
948 template <typename R, typename UnaryPredicate>
949 auto find_if(R &&Range, UnaryPredicate P) -> decltype(adl_begin(Range)) {
950  return std::find_if(adl_begin(Range), adl_end(Range), P);
951 }
952 
953 template <typename R, typename UnaryPredicate>
954 auto find_if_not(R &&Range, UnaryPredicate P) -> decltype(adl_begin(Range)) {
955  return std::find_if_not(adl_begin(Range), adl_end(Range), P);
956 }
957 
958 /// Provide wrappers to std::remove_if which take ranges instead of having to
959 /// pass begin/end explicitly.
960 template <typename R, typename UnaryPredicate>
961 auto remove_if(R &&Range, UnaryPredicate P) -> decltype(adl_begin(Range)) {
962  return std::remove_if(adl_begin(Range), adl_end(Range), P);
963 }
964 
965 /// Provide wrappers to std::copy_if which take ranges instead of having to
966 /// pass begin/end explicitly.
967 template <typename R, typename OutputIt, typename UnaryPredicate>
968 OutputIt copy_if(R &&Range, OutputIt Out, UnaryPredicate P) {
969  return std::copy_if(adl_begin(Range), adl_end(Range), Out, P);
970 }
971 
972 template <typename R, typename OutputIt>
973 OutputIt copy(R &&Range, OutputIt Out) {
974  return std::copy(adl_begin(Range), adl_end(Range), Out);
975 }
976 
977 /// Wrapper function around std::find to detect if an element exists
978 /// in a container.
979 template <typename R, typename E>
980 bool is_contained(R &&Range, const E &Element) {
981  return std::find(adl_begin(Range), adl_end(Range), Element) != adl_end(Range);
982 }
983 
984 /// Wrapper function around std::count to count the number of times an element
985 /// \p Element occurs in the given range \p Range.
986 template <typename R, typename E>
987 auto count(R &&Range, const E &Element) ->
988  typename std::iterator_traits<decltype(adl_begin(Range))>::difference_type {
989  return std::count(adl_begin(Range), adl_end(Range), Element);
990 }
991 
992 /// Wrapper function around std::count_if to count the number of times an
993 /// element satisfying a given predicate occurs in a range.
994 template <typename R, typename UnaryPredicate>
995 auto count_if(R &&Range, UnaryPredicate P) ->
996  typename std::iterator_traits<decltype(adl_begin(Range))>::difference_type {
997  return std::count_if(adl_begin(Range), adl_end(Range), P);
998 }
999 
1000 /// Wrapper function around std::transform to apply a function to a range and
1001 /// store the result elsewhere.
1002 template <typename R, typename OutputIt, typename UnaryPredicate>
1003 OutputIt transform(R &&Range, OutputIt d_first, UnaryPredicate P) {
1004  return std::transform(adl_begin(Range), adl_end(Range), d_first, P);
1005 }
1006 
1007 /// Provide wrappers to std::partition which take ranges instead of having to
1008 /// pass begin/end explicitly.
1009 template <typename R, typename UnaryPredicate>
1010 auto partition(R &&Range, UnaryPredicate P) -> decltype(adl_begin(Range)) {
1011  return std::partition(adl_begin(Range), adl_end(Range), P);
1012 }
1013 
1014 /// Provide wrappers to std::lower_bound which take ranges instead of having to
1015 /// pass begin/end explicitly.
1016 template <typename R, typename ForwardIt>
1017 auto lower_bound(R &&Range, ForwardIt I) -> decltype(adl_begin(Range)) {
1018  return std::lower_bound(adl_begin(Range), adl_end(Range), I);
1019 }
1020 
1021 /// Given a range of type R, iterate the entire range and return a
1022 /// SmallVector with elements of the vector. This is useful, for example,
1023 /// when you want to iterate a range and then sort the results.
1024 template <unsigned Size, typename R>
1026 to_vector(R &&Range) {
1027  return {adl_begin(Range), adl_end(Range)};
1028 }
1029 
1030 /// Provide a container algorithm similar to C++ Library Fundamentals v2's
1031 /// `erase_if` which is equivalent to:
1032 ///
1033 /// C.erase(remove_if(C, pred), C.end());
1034 ///
1035 /// This version works for any container with an erase method call accepting
1036 /// two iterators.
1037 template <typename Container, typename UnaryPredicate>
1038 void erase_if(Container &C, UnaryPredicate P) {
1039  C.erase(remove_if(C, P), C.end());
1040 }
1041 
1042 /// Get the size of a range. This is a wrapper function around std::distance
1043 /// which is only enabled when the operation is O(1).
1044 template <typename R>
1045 auto size(R &&Range, typename std::enable_if<
1046  std::is_same<typename std::iterator_traits<decltype(
1047  Range.begin())>::iterator_category,
1048  std::random_access_iterator_tag>::value,
1049  void>::type * = nullptr)
1050  -> decltype(std::distance(Range.begin(), Range.end())) {
1051  return std::distance(Range.begin(), Range.end());
1052 }
1053 
1054 //===----------------------------------------------------------------------===//
1055 // Extra additions to <memory>
1056 //===----------------------------------------------------------------------===//
1057 
1058 // Implement make_unique according to N3656.
1059 
1060 /// Constructs a `new T()` with the given args and returns a
1061 /// `unique_ptr<T>` which owns the object.
1062 ///
1063 /// Example:
1064 ///
1065 /// auto p = make_unique<int>();
1066 /// auto p = make_unique<std::tuple<int, int>>(0, 1);
1067 template <class T, class... Args>
1068 typename std::enable_if<!std::is_array<T>::value, std::unique_ptr<T>>::type
1069 make_unique(Args &&... args) {
1070  return std::unique_ptr<T>(new T(std::forward<Args>(args)...));
1071 }
1072 
1073 /// Constructs a `new T[n]` with the given args and returns a
1074 /// `unique_ptr<T[]>` which owns the object.
1075 ///
1076 /// \param n size of the new array.
1077 ///
1078 /// Example:
1079 ///
1080 /// auto p = make_unique<int[]>(2); // value-initializes the array with 0's.
1081 template <class T>
1082 typename std::enable_if<std::is_array<T>::value && std::extent<T>::value == 0,
1083  std::unique_ptr<T>>::type
1084 make_unique(size_t n) {
1085  return std::unique_ptr<T>(new typename std::remove_extent<T>::type[n]());
1086 }
1087 
1088 /// This function isn't used and is only here to provide better compile errors.
1089 template <class T, class... Args>
1090 typename std::enable_if<std::extent<T>::value != 0>::type
1091 make_unique(Args &&...) = delete;
1092 
1093 struct FreeDeleter {
1094  void operator()(void* v) {
1095  ::free(v);
1096  }
1097 };
1098 
1099 template<typename First, typename Second>
1100 struct pair_hash {
1101  size_t operator()(const std::pair<First, Second> &P) const {
1102  return std::hash<First>()(P.first) * 31 + std::hash<Second>()(P.second);
1103  }
1104 };
1105 
1106 /// A functor like C++14's std::less<void> in its absence.
1107 struct less {
1108  template <typename A, typename B> bool operator()(A &&a, B &&b) const {
1109  return std::forward<A>(a) < std::forward<B>(b);
1110  }
1111 };
1112 
1113 /// A functor like C++14's std::equal<void> in its absence.
1114 struct equal {
1115  template <typename A, typename B> bool operator()(A &&a, B &&b) const {
1116  return std::forward<A>(a) == std::forward<B>(b);
1117  }
1118 };
1119 
1120 /// Binary functor that adapts to any other binary functor after dereferencing
1121 /// operands.
1122 template <typename T> struct deref {
1123  T func;
1124 
1125  // Could be further improved to cope with non-derivable functors and
1126  // non-binary functors (should be a variadic template member function
1127  // operator()).
1128  template <typename A, typename B>
1129  auto operator()(A &lhs, B &rhs) const -> decltype(func(*lhs, *rhs)) {
1130  assert(lhs);
1131  assert(rhs);
1132  return func(*lhs, *rhs);
1133  }
1134 };
1135 
1136 namespace detail {
1137 
1138 template <typename R> class enumerator_iter;
1139 
1140 template <typename R> struct result_pair {
1141  friend class enumerator_iter<R>;
1142 
1143  result_pair() = default;
1144  result_pair(std::size_t Index, IterOfRange<R> Iter)
1145  : Index(Index), Iter(Iter) {}
1146 
1148  Index = Other.Index;
1149  Iter = Other.Iter;
1150  return *this;
1151  }
1152 
1153  std::size_t index() const { return Index; }
1154  const ValueOfRange<R> &value() const { return *Iter; }
1155  ValueOfRange<R> &value() { return *Iter; }
1156 
1157 private:
1159  IterOfRange<R> Iter;
1160 };
1161 
1162 template <typename R>
1163 class enumerator_iter
1164  : public iterator_facade_base<
1165  enumerator_iter<R>, std::forward_iterator_tag, result_pair<R>,
1166  typename std::iterator_traits<IterOfRange<R>>::difference_type,
1167  typename std::iterator_traits<IterOfRange<R>>::pointer,
1168  typename std::iterator_traits<IterOfRange<R>>::reference> {
1169  using result_type = result_pair<R>;
1170 
1171 public:
1173  : Result(std::numeric_limits<size_t>::max(), EndIter) {}
1174 
1176  : Result(Index, Iter) {}
1177 
1178  result_type &operator*() { return Result; }
1179  const result_type &operator*() const { return Result; }
1180 
1183  ++Result.Iter;
1184  ++Result.Index;
1185  return *this;
1186  }
1187 
1188  bool operator==(const enumerator_iter<R> &RHS) const {
1189  // Don't compare indices here, only iterators. It's possible for an end
1190  // iterator to have different indices depending on whether it was created
1191  // by calling std::end() versus incrementing a valid iterator.
1192  return Result.Iter == RHS.Result.Iter;
1193  }
1194 
1196  Result = Other.Result;
1197  return *this;
1198  }
1199 
1200 private:
1201  result_type Result;
1202 };
1203 
1204 template <typename R> class enumerator {
1205 public:
1206  explicit enumerator(R &&Range) : TheRange(std::forward<R>(Range)) {}
1207 
1209  return enumerator_iter<R>(0, std::begin(TheRange));
1210  }
1211 
1213  return enumerator_iter<R>(std::end(TheRange));
1214  }
1215 
1216 private:
1217  R TheRange;
1218 };
1219 
1220 } // end namespace detail
1221 
1222 /// Given an input range, returns a new range whose values are are pair (A,B)
1223 /// such that A is the 0-based index of the item in the sequence, and B is
1224 /// the value from the original sequence. Example:
1225 ///
1226 /// std::vector<char> Items = {'A', 'B', 'C', 'D'};
1227 /// for (auto X : enumerate(Items)) {
1228 /// printf("Item %d - %c\n", X.index(), X.value());
1229 /// }
1230 ///
1231 /// Output:
1232 /// Item 0 - A
1233 /// Item 1 - B
1234 /// Item 2 - C
1235 /// Item 3 - D
1236 ///
1237 template <typename R> detail::enumerator<R> enumerate(R &&TheRange) {
1238  return detail::enumerator<R>(std::forward<R>(TheRange));
1239 }
1240 
1241 namespace detail {
1242 
1243 template <typename F, typename Tuple, std::size_t... I>
1245  -> decltype(std::forward<F>(f)(std::get<I>(std::forward<Tuple>(t))...)) {
1246  return std::forward<F>(f)(std::get<I>(std::forward<Tuple>(t))...);
1247 }
1248 
1249 } // end namespace detail
1250 
1251 /// Given an input tuple (a1, a2, ..., an), pass the arguments of the
1252 /// tuple variadically to f as if by calling f(a1, a2, ..., an) and
1253 /// return the result.
1254 template <typename F, typename Tuple>
1255 auto apply_tuple(F &&f, Tuple &&t) -> decltype(detail::apply_tuple_impl(
1256  std::forward<F>(f), std::forward<Tuple>(t),
1258  std::tuple_size<typename std::decay<Tuple>::type>::value>{})) {
1259  using Indices = build_index_impl<
1260  std::tuple_size<typename std::decay<Tuple>::type>::value>;
1261 
1262  return detail::apply_tuple_impl(std::forward<F>(f), std::forward<Tuple>(t),
1263  Indices{});
1264 }
1265 
1266 } // end namespace llvm
1267 
1268 #endif // LLVM_ADT_STLEXTRAS_H
detail::concat_range< ValueT, RangeTs... > concat(RangeTs &&... Ranges)
Concatenated range across two or more ranges.
Definition: STLExtras.h:716
result_pair(std::size_t Index, IterOfRange< R > Iter)
Definition: STLExtras.h:1144
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:905
uint64_t CallInst * C
void DeleteContainerPointers(Container &C)
For a container of pointers, deletes the pointers and then clears the container.
Definition: STLExtras.h:896
bool operator()(const Ty *left, const Ty *right) const
Definition: STLExtras.h:95
ZipType & operator++()
Definition: STLExtras.h:486
bool operator==(const enumerator_iter< R > &RHS) const
Definition: STLExtras.h:1188
const_iterator end(StringRef path)
Get end iterator over path.
Definition: Path.cpp:250
filter_iterator_impl(WrappedIteratorT Begin, WrappedIteratorT End, PredicateT Pred)
Definition: STLExtras.h:363
zippy(Args &&... ts_)
Definition: STLExtras.h:549
GCNRegPressure max(const GCNRegPressure &P1, const GCNRegPressure &P2)
Ret operator()(Params ...params) const
Definition: STLExtras.h:131
const_iterator begin(StringRef path, Style style=Style::native)
Get begin iterator over path.
Definition: Path.cpp:241
bool operator()(const T &lhs, const T &rhs) const
Definition: STLExtras.h:730
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:390
Compute iterated dominance frontiers using a linear time algorithm.
Definition: AllocatorList.h:24
typename std::remove_reference< decltype(*std::begin(std::declval< RangeT & >()))>::type ValueOfRange
Definition: STLExtras.h:56
decltype(iterators) tup_inc(index_sequence< Ns... >) const
Definition: STLExtras.h:468
Function object to check whether the second component of a std::pair compares less than the second co...
Definition: STLExtras.h:737
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:968
typename iterator::value_type value_type
Definition: STLExtras.h:533
const Ty & operator()(const Ty &self) const
Definition: STLExtras.h:83
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:318
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:819
bool operator()(const T &lhs, const T &rhs) const
Definition: STLExtras.h:738
An efficient, type-erasing, non-owning reference to a callable.
Definition: STLExtras.h:106
A functor like C++14&#39;s std::less<void> in its absence.
Definition: STLExtras.h:1107
zip_common(Iters &&... ts)
Definition: STLExtras.h:478
void adl_swap(T &&lhs, T &&rhs) noexcept(noexcept(adl_detail::adl_swap(std::declval< T >(), std::declval< T >())))
Definition: STLExtras.h:192
enumerator_iter(IterOfRange< R > EndIter)
Definition: STLExtras.h:1172
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:995
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:921
F(f)
std::tuple< decltype(*declval< Iters >())... > type
Definition: STLExtras.h:436
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:1069
typename iterator::pointer pointer
Definition: STLExtras.h:535
int array_pod_sort_comparator(const void *P1, const void *P2)
Adapt std::less<T> for array_pod_sort.
Definition: STLExtras.h:806
void adl_swap(T &&lhs, T &&rhs) noexcept(noexcept(swap(std::declval< T >(), std::declval< T >())))
Definition: STLExtras.h:172
Metafunction to determine if T& or T has a member called rbegin().
Definition: STLExtras.h:244
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:124
Ty & operator()(Ty &self) const
Definition: STLExtras.h:80
Definition: BitVector.h:921
concat_range(RangeTs &&... Ranges)
Definition: STLExtras.h:703
std::bidirectional_iterator_tag type
Definition: STLExtras.h:381
void operator()(void *v)
Definition: STLExtras.h:1094
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:935
decltype(iterators) tup_dec(index_sequence< Ns... >) const
Definition: STLExtras.h:473
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:1026
Alias for the common case of a sequence of size_ts.
Definition: STLExtras.h:425
ELFYAML::ELF_STO Other
Definition: ELFYAML.cpp:773
auto reverse(ContainerTy &&C, typename std::enable_if< has_rbegin< ContainerTy >::value >::type *=nullptr) -> decltype(make_range(C.rbegin(), C.rend()))
Definition: STLExtras.h:250
bool operator()(const Ty *left, const Ty *right) const
Definition: STLExtras.h:89
#define T
enumerator_iter< R > & operator++()
Definition: STLExtras.h:1181
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:1255
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:1010
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:1017
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:1175
Helper to store a sequence of ranges being concatenated and access them.
Definition: STLExtras.h:685
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:987
traits class for checking whether type T is one of any of the given types in the variadic list...
Definition: STLExtras.h:772
ValueOfRange< R > & value()
Definition: STLExtras.h:1155
typename iterator::reference reference
Definition: STLExtras.h:536
#define P(N)
ItType< decltype(std::begin(std::declval< Args >()))... > iterator
Definition: STLExtras.h:531
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:839
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:1129
auto adl_end(ContainerTy &&container) -> decltype(end(std::forward< ContainerTy >(container)))
Definition: STLExtras.h:164
ZipType & operator--()
Definition: STLExtras.h:491
CRTP base class for adapting an iterator to a different type.
Definition: iterator.h:208
mapped_iterator(ItTy U, FuncTy F)
Definition: STLExtras.h:209
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:559
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
const result_type & operator*() const
Definition: STLExtras.h:1179
mapped_iterator< ItTy, FuncTy > map_iterator(ItTy I, FuncTy F)
Definition: STLExtras.h:223
auto adl_begin(ContainerTy &&container) -> decltype(adl_detail::adl_begin(std::forward< ContainerTy >(container)))
Definition: STLExtras.h:180
void sort(IteratorTy Start, IteratorTy End, Compare Comp)
Definition: STLExtras.h:881
filter_iterator_impl(WrappedIteratorT Begin, WrappedIteratorT End, PredicateT Pred)
Definition: STLExtras.h:342
Helper to determine if type T has a member called rbegin().
Definition: STLExtras.h:228
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:928
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:949
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:961
auto find_if_not(R &&Range, UnaryPredicate P) -> decltype(adl_begin(Range))
Definition: STLExtras.h:954
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:568
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:942
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
static constexpr size_t size()
Definition: STLExtras.h:749
iterator end() const
Definition: STLExtras.h:552
void sort(IteratorTy Start, IteratorTy End)
Definition: STLExtras.h:872
bool operator()(A &&a, B &&b) const
Definition: STLExtras.h:1108
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:1244
A functor like C++14&#39;s std::equal<void> in its absence.
Definition: STLExtras.h:1114
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:463
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:1045
This is a &#39;vector&#39; (really, a variable-sized array), optimized for the case when the array is small...
Definition: SmallVector.h:841
constexpr size_t array_lengthof(T(&)[N])
Find the length of an array.
Definition: STLExtras.h:800
An iterator adaptor that filters the elements of given inner iterators.
Definition: STLExtras.h:292
Creates a compile-time integer sequence for a parameter pack.
Definition: STLExtras.h:427
auto adl_begin(ContainerTy &&container) -> decltype(begin(std::forward< ContainerTy >(container)))
Definition: STLExtras.h:156
typename iterator::difference_type difference_type
Definition: STLExtras.h:534
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:1038
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
Definition: BitVector.h:924
A range adaptor for a pair of iterators.
bool operator()(A &&a, B &&b) const
Definition: STLExtras.h:1115
std::forward_iterator_tag type
Definition: STLExtras.h:377
Represents a compile-time sequence of integers.
Definition: STLExtras.h:746
filter_iterator_base & operator++()
Definition: STLExtras.h:327
Basic Alias true
Helper which sets its type member to forward_iterator_tag if the category of IterT does not derive fr...
Definition: STLExtras.h:387
enumerator_iter< R > & operator=(const enumerator_iter< R > &Other)
Definition: STLExtras.h:1195
concat_iterator & operator++()
Definition: STLExtras.h:666
FuncReturnTy operator*()
Definition: STLExtras.h:214
result_pair< R > & operator=(const result_pair< R > &Other)
Definition: STLExtras.h:1147
ValueT & operator*() const
Definition: STLExtras.h:671
bool operator==(const zip_first< Iters... > &other) const
Definition: STLExtras.h:503
WrappedIteratorT End
Definition: STLExtras.h:307
#define I(x, y, z)
Definition: MD5.cpp:58
#define N
bool operator==(const concat_iterator &RHS) const
Definition: STLExtras.h:673
typename iterator::iterator_category iterator_category
Definition: STLExtras.h:532
value_type operator*()
Definition: STLExtras.h:480
decltype(std::begin(std::declval< RangeT & >())) IterOfRange
Definition: STLExtras.h:52
const ValueOfRange< R > & value() const
Definition: STLExtras.h:1154
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:411
std::tuple< Iters... > iterators
Definition: STLExtras.h:460
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:1003
const value_type operator*() const
Definition: STLExtras.h:482
auto adl_end(ContainerTy &&container) -> decltype(adl_detail::adl_end(std::forward< ContainerTy >(container)))
Definition: STLExtras.h:186
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
std::reverse_iterator< IteratorTy > make_reverse_iterator(IteratorTy It)
Definition: STLExtras.h:258
traits class for checking whether type T is a base class for all the given types in the variadic list...
Definition: STLExtras.h:784
enumerator_iter< R > begin()
Definition: STLExtras.h:1208
constexpr char Size[]
Key for Kernel::Arg::Metadata::mSize.
enumerator_iter< R > end()
Definition: STLExtras.h:1212
Specialization of filter_iterator_base for forward iteration only.
Definition: STLExtras.h:337
iterator begin() const
Definition: STLExtras.h:551
Binary functor that adapts to any other binary functor after dereferencing operands.
Definition: STLExtras.h:1122
Iterator wrapper that concatenates sequences together.
Definition: STLExtras.h:585
Utility type to build an inheritance chain that makes it easy to rank overload candidates.
Definition: STLExtras.h:767
zip_shortest(Iters &&... ts)
Definition: STLExtras.h:522
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:914
void deleter(T *Ptr)
Definition: STLExtras.h:143
OutputIt copy(R &&Range, OutputIt Out)
Definition: STLExtras.h:973
zip_first(Iters &&... ts)
Definition: STLExtras.h:507
std::size_t index() const
Definition: STLExtras.h:1153
Function object to check whether the first component of a std::pair compares less than the first comp...
Definition: STLExtras.h:729
constexpr char Args[]
Key for Kernel::Metadata::mArgs.
concat_iterator(RangeTs &&... Ranges)
Constructs an iterator from a squence of ranges.
Definition: STLExtras.h:661
bool operator==(const zip_shortest< Iters... > &other) const
Definition: STLExtras.h:524
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:1237
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:980
size_t operator()(const std::pair< First, Second > &P) const
Definition: STLExtras.h:1101