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