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