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