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"
23#include "llvm/ADT/iterator_range.h"
24#include "llvm/Config/abi-breaking.h"
25#include "llvm/Support/ErrorHandling.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
44namespace 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.
48template <typename T, T> struct SameType;
49
50namespace detail {
51
52template <typename RangeT>
53using IterOfRange = decltype(std::begin(std::declval<RangeT &>()));
54
55template <typename RangeT>
56using 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
65template <typename T>
66struct negation : std::integral_constant<bool, !bool(T::value)> {};
67
68template <typename...> struct conjunction : std::true_type {};
69template <typename B1> struct conjunction<B1> : B1 {};
70template <typename B1, typename... Bn>
71struct conjunction<B1, Bn...>
72 : std::conditional<bool(B1::value), conjunction<Bn...>, B1>::type {};
73
74//===----------------------------------------------------------------------===//
75// Extra additions to <functional>
76//===----------------------------------------------------------------------===//
77
78template <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
89template <class Ty> struct less_ptr {
90 bool operator()(const Ty* left, const Ty* right) const {
91 return *left < *right;
92 }
93};
94
95template <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.
107template<typename Fn> class function_ref;
108
109template<typename Ret, typename ...Params>
110class 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
120public:
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>);
143template <class T>
144inline void deleter(T *Ptr) {
145 delete Ptr;
146}
147
148//===----------------------------------------------------------------------===//
149// Extra additions to <iterator>
150//===----------------------------------------------------------------------===//
151
152namespace adl_detail {
153
154using std::begin;
155
156template <typename ContainerTy>
157auto adl_begin(ContainerTy &&container)
158 -> decltype(begin(std::forward<ContainerTy>(container))) {
159 return begin(std::forward<ContainerTy>(container));
160}
161
162using std::end;
163
164template <typename ContainerTy>
165auto adl_end(ContainerTy &&container)
166 -> decltype(end(std::forward<ContainerTy>(container))) {
167 return end(std::forward<ContainerTy>(container));
168}
169
170using std::swap;
171
172template <typename T>
173void 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
180template <typename ContainerTy>
181auto 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
186template <typename ContainerTy>
187auto 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
192template <typename T>
193void 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.
199template <typename T>
200constexpr 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
207template <typename ItTy, typename FuncTy,
208 typename FuncReturnTy =
209 decltype(std::declval<FuncTy>()(*std::declval<ItTy>()))>
210class mapped_iterator
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> {
215public:
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
223private:
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...
229template <class ItTy, class FuncTy>
230inline mapped_iterator<ItTy, FuncTy> map_iterator(ItTy I, FuncTy F) {
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().
235template <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
245public:
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().
250template <typename Ty>
251struct 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.
256template <typename ContainerTy>
257auto 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.
264template <typename IteratorTy>
265std::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.
272template <typename ContainerTy>
273auto reverse(
274 ContainerTy &&C,
275 typename std::enable_if<!has_rbegin<ContainerTy>::value>::type * = nullptr)
276 -> decltype(make_range(llvm::make_reverse_iterator(std::end(C)),
277 llvm::make_reverse_iterator(std::begin(C)))) {
278 return make_range(llvm::make_reverse_iterator(std::end(C)),
279 llvm::make_reverse_iterator(std::begin(C)));
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.
298template <typename WrappedIteratorT, typename PredicateT, typename IterTag>
299class filter_iterator_base
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> {
306 using BaseT = iterator_adaptor_base<
307 filter_iterator_base<WrappedIteratorT, PredicateT, IterTag>,
308 WrappedIteratorT,
309 typename std::common_type<
310 IterTag, typename std::iterator_traits<
311 WrappedIteratorT>::iterator_category>::type>;
312
313protected:
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
331public:
332 using BaseT::operator++;
333
334 filter_iterator_base &operator++() {
335 BaseT::operator++();
336 findNextValid();
337 return *this;
338 }
339};
340
341/// Specialization of filter_iterator_base for forward iteration only.
342template <typename WrappedIteratorT, typename PredicateT,
343 typename IterTag = std::forward_iterator_tag>
344class filter_iterator_impl
345 : public filter_iterator_base<WrappedIteratorT, PredicateT, IterTag> {
346 using BaseT = filter_iterator_base<WrappedIteratorT, PredicateT, IterTag>;
347
348public:
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.
355template <typename WrappedIteratorT, typename PredicateT>
356class 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
367public:
368 using BaseT::operator--;
369
370 filter_iterator_impl(WrappedIteratorT Begin, WrappedIteratorT End,
371 PredicateT Pred)
372 : BaseT(Begin, End, Pred) {}
373
374 filter_iterator_impl &operator--() {
375 BaseT::operator--();
376 findPrevValid();
377 return *this;
378 }
379};
380
381namespace detail {
382
383template <bool is_bidirectional> struct fwd_or_bidi_tag_impl {
384 using type = std::forward_iterator_tag;
385};
386
387template <> 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.
394template <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.
404template <typename WrappedIteratorT, typename PredicateT>
405using filter_iterator = filter_iterator_impl<
406 WrappedIteratorT, PredicateT,
407 typename detail::fwd_or_bidi_tag<WrappedIteratorT>::type>;
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.
416template <typename RangeT, typename PredicateT>
417iterator_range<filter_iterator<detail::IterOfRange<RangeT>, PredicateT>>
418make_filter_range(RangeT &&Range, PredicateT Pred) {
419 using FilterIteratorT =
420 filter_iterator<detail::IterOfRange<RangeT>, PredicateT>;
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.
445template <typename WrappedIteratorT>
446class early_inc_iterator_impl
447 : public iterator_adaptor_base<early_inc_iterator_impl<WrappedIteratorT>,
448 WrappedIteratorT, std::input_iterator_tag> {
449 using BaseT =
450 iterator_adaptor_base<early_inc_iterator_impl<WrappedIteratorT>,
451 WrappedIteratorT, std::input_iterator_tag>;
452
453 using PointerT = typename std::iterator_traits<WrappedIteratorT>::pointer;
454
455protected:
456#if LLVM_ENABLE_ABI_BREAKING_CHECKS
457 bool IsEarlyIncremented = false;
458#endif
459
460public:
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++;
473 early_inc_iterator_impl &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.
502template <typename RangeT>
503iterator_range<early_inc_iterator_impl<detail::IterOfRange<RangeT>>>
504make_early_inc_range(RangeT &&Range) {
505 using EarlyIncIteratorT =
506 early_inc_iterator_impl<detail::IterOfRange<RangeT>>;
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
512template <typename R, typename UnaryPredicate>
513bool all_of(R &&range, UnaryPredicate P);
514
515template <size_t... I> struct index_sequence;
516
517template <class... Ts> struct index_sequence_for;
518
519namespace detail {
520
521using 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.
525template<typename... Iters> struct ZipTupleType {
526 using type = std::tuple<decltype(*declval<Iters>())...>;
527};
528
529template <typename ZipType, typename... Iters>
530using zip_traits = iterator_facade_base<
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
545template <typename ZipType, typename... Iters>
546struct 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
552protected:
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
567public:
568 zip_common(Iters &&... ts) : iterators(std::forward<Iters>(ts)...) {}
569
570 value_type operator*() { return deref(index_sequence_for<Iters...>{}); }
571
572 const value_type operator*() const {
573 return deref(index_sequence_for<Iters...>{});
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
589template <typename... Iters>
590struct 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
600template <typename... Iters>
601class 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
609public:
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
619template <template <typename...> class ItType, typename... Args> class zippy {
620public:
621 using iterator = ItType<decltype(std::begin(std::declval<Args>()))...>;
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
628private:
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
638public:
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.
648template <typename T, typename U, typename... Args>
649detail::zippy<detail::zip_shortest, T, U, Args...> zip(T &&t, U &&u,
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.
657template <typename T, typename U, typename... Args>
658detail::zippy<detail::zip_first, T, U, Args...> zip_first(T &&t, U &&u,
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.
674template <typename ValueT, typename... IterTs>
675class concat_iterator
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
748public:
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
759 concat_iterator &operator++() {
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
771namespace 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.
778template <typename ValueT, typename... RangeTs> class concat_range {
779public:
780 using iterator =
781 concat_iterator<ValueT,
782 decltype(std::begin(std::declval<RangeTs &>()))...>;
783
784private:
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
795public:
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.
808template <typename ValueT, typename... RangeTs>
809detail::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.
822struct 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.
830struct 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.
838template<typename FuncTy>
839struct 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.
852template <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.
859template <size_t... I>
860struct index_sequence : integer_sequence<std::size_t, I...> {};
861
862template <std::size_t N, std::size_t... I>
863struct build_index_impl : build_index_impl<N - 1, N - 1, I...> {};
864template <std::size_t... I>
865struct build_index_impl<0, I...> : index_sequence<I...> {};
866
867/// Creates a compile-time integer sequence for a parameter pack.
868template <class... Ts>
869struct 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.
873template <int N> struct rank : rank<N - 1> {};
874template <> 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.
878template <typename T, typename... Ts> struct is_one_of {
879 static const bool value = false;
880};
881
882template <typename T, typename U, typename... Ts>
883struct 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.
890template <typename T, typename... Ts> struct are_base_of {
891 static const bool value = true;
892};
893
894template <typename T, typename U, typename... Ts>
895struct 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.
905template <class T, std::size_t N>
906constexpr inline size_t array_lengthof(T (&)[N]) {
907 return N;
908}
909
910/// Adapt std::less<T> for array_pod_sort.
911template<typename T>
912inline 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.
924template<typename T>
925inline 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.
944template<class IteratorTy>
945inline 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
957template <class IteratorTy>
958inline 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).
977template <typename IteratorTy>
978inline 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
986template <typename Container> inline void sort(Container &&C) {
987 llvm::sort(adl_begin(C), adl_end(C));
988}
989
990template <typename IteratorTy, typename Compare>
991inline 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
999template <typename Container, typename Compare>
1000inline 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.
1010template<typename Container>
1011void 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.
1019template<typename Container>
1020void 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).
1028template <typename R>
1029auto 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.
1040template <typename R, typename UnaryPredicate>
1041UnaryPredicate 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.
1047template <typename R, typename UnaryPredicate>
1048bool 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.
1054template <typename R, typename UnaryPredicate>
1055bool 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.
1061template <typename R, typename UnaryPredicate>
1062bool 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.
1068template <typename R, typename T>
1069auto 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.
1075template <typename R, typename UnaryPredicate>
1076auto find_if(R &&Range, UnaryPredicate P) -> decltype(adl_begin(Range)) {
1077 return std::find_if(adl_begin(Range), adl_end(Range), P);
1078}
1079
1080template <typename R, typename UnaryPredicate>
1081auto 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.
1087template <typename R, typename UnaryPredicate>
1088auto 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.
1094template <typename R, typename OutputIt, typename UnaryPredicate>
1095OutputIt copy_if(R &&Range, OutputIt Out, UnaryPredicate P) {
1096 return std::copy_if(adl_begin(Range), adl_end(Range), Out, P);
1097}
1098
1099template <typename R, typename OutputIt>
1100OutputIt 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.
1106template <typename R, typename E>
1107bool 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.
1113template <typename R, typename E>
1114auto 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.
1121template <typename R, typename UnaryPredicate>
1122auto 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.
1129template <typename R, typename OutputIt, typename UnaryPredicate>
1130OutputIt 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.
1136template <typename R, typename UnaryPredicate>
1137auto 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.
1143template <typename R, typename ForwardIt>
1144auto lower_bound(R &&Range, ForwardIt I) -> decltype(adl_begin(Range)) {
1145 return std::lower_bound(adl_begin(Range), adl_end(Range), I);
1146}
1147
1148template <typename R, typename ForwardIt, typename Compare>
1149auto 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.
1156template <typename R, typename ForwardIt>
1157auto upper_bound(R &&Range, ForwardIt I) -> decltype(adl_begin(Range)) {
1158 return std::upper_bound(adl_begin(Range), adl_end(Range), I);
1159}
1160
1161template <typename R, typename ForwardIt, typename Compare>
1162auto 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.
1168template <typename R>
1169bool 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.
1178template <unsigned Size, typename R>
1179SmallVector<typename std::remove_const<detail::ValueOfRange<R>>::type, Size>
1180to_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.
1191template <typename Container, typename UnaryPredicate>
1192void 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);
1209template <class T, class... Args>
1210typename std::enable_if<!std::is_array<T>::value, std::unique_ptr<T>>::type
1211make_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.
1223template <class T>
1224typename std::enable_if<std::is_array<T>::value && std::extent<T>::value == 0,
1225 std::unique_ptr<T>>::type
1226make_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.
1231template <class T, class... Args>
1232typename std::enable_if<std::extent<T>::value != 0>::type
1233make_unique(Args &&...) = delete;
1234
1235struct FreeDeleter {
1236 void operator()(void* v) {
1237 ::free(v);
1238 }
1239};
1240
1241template<typename First, typename Second>
1242struct 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.
1249struct 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.
1256struct 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.
1264template <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
1278namespace detail {
1279
1280template <typename R> class enumerator_iter;
1281
1282template <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
1289 result_pair<R> &operator=(const result_pair<R> &Other) {
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
1299private:
1300 std::size_t Index = std::numeric_limits<std::size_t>::max();
1301 IterOfRange<R> Iter;
1302};
1303
1304template <typename R>
1305class 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
1313public:
1314 explicit enumerator_iter(IterOfRange<R> EndIter)
1315 : Result(std::numeric_limits<size_t>::max(), EndIter) {}
1316
1317 enumerator_iter(std::size_t Index, IterOfRange<R> Iter)
1318 : Result(Index, Iter) {}
1319
1320 result_type &operator*() { return Result; }
1321 const result_type &operator*() const { return Result; }
1322
1323 enumerator_iter<R> &operator++() {
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
1337 enumerator_iter<R> &operator=(const enumerator_iter<R> &Other) {
1338 Result = Other.Result;
1339 return *this;
1340 }
1341
1342private:
1343 result_type Result;
1344};
1345
1346template <typename R> class enumerator {
1347public:
1348 explicit enumerator(R &&Range) : TheRange(std::forward<R>(Range)) {}
1349
1350 enumerator_iter<R> begin() {
1351 return enumerator_iter<R>(0, std::begin(TheRange));
1352 }
1353
1354 enumerator_iter<R> end() {
1355 return enumerator_iter<R>(std::end(TheRange));
1356 }
1357
1358private:
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///
1379template <typename R> detail::enumerator<R> enumerate(R &&TheRange) {
1380 return detail::enumerator<R>(std::forward<R>(TheRange));
1381}
1382
1383namespace detail {
1384
1385template <typename F, typename Tuple, std::size_t... I>
1386auto apply_tuple_impl(F &&f, Tuple &&t, index_sequence<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.
1396template <typename F, typename Tuple>
1397auto apply_tuple(F &&f, Tuple &&t) -> decltype(detail::apply_tuple_impl(
1398 std::forward<F>(f), std::forward<Tuple>(t),
1399 build_index_impl<
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
1411