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