1 //===- llvm/ADT/STLExtras.h - Useful STL related functions ------*- C++ -*-===//
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
7 //===----------------------------------------------------------------------===//
9 // This file contains some templates that are useful if you are working with the
12 // No library is required when using these functions.
14 //===----------------------------------------------------------------------===//
16 #ifndef LLVM_ADT_STLEXTRAS_H
17 #define LLVM_ADT_STLEXTRAS_H
19 #include "llvm/ADT/Optional.h"
20 #include "llvm/ADT/SmallVector.h"
21 #include "llvm/ADT/iterator.h"
22 #include "llvm/ADT/iterator_range.h"
23 #include "llvm/Config/abi-breaking.h"
24 #include "llvm/Support/ErrorHandling.h"
31 #include <initializer_list>
36 #include <type_traits>
39 #ifdef EXPENSIVE_CHECKS
40 #include <random> // for std::mt19937
45 // Only used by compiler if both template types are the same. Useful when
46 // using SFINAE to test for the existence of member functions.
47 template <typename T, T> struct SameType;
51 template <typename RangeT>
52 using IterOfRange = decltype(std::begin(std::declval<RangeT &>()));
54 template <typename RangeT>
55 using ValueOfRange = typename std::remove_reference<decltype(
56 *std::begin(std::declval<RangeT &>()))>::type;
58 } // end namespace detail
60 //===----------------------------------------------------------------------===//
61 // Extra additions to <type_traits>
62 //===----------------------------------------------------------------------===//
65 struct negation : std::integral_constant<bool, !bool(T::value)> {};
67 template <typename...> struct conjunction : std::true_type {};
68 template <typename B1> struct conjunction<B1> : B1 {};
69 template <typename B1, typename... Bn>
70 struct conjunction<B1, Bn...>
71 : std::conditional<bool(B1::value), conjunction<Bn...>, B1>::type {};
73 template <typename T> struct make_const_ptr {
75 typename std::add_pointer<typename std::add_const<T>::type>::type;
78 template <typename T> struct make_const_ref {
79 using type = typename std::add_lvalue_reference<
80 typename std::add_const<T>::type>::type;
83 //===----------------------------------------------------------------------===//
84 // Extra additions to <functional>
85 //===----------------------------------------------------------------------===//
87 template <class Ty> struct identity {
88 using argument_type = Ty;
90 Ty &operator()(Ty &self) const {
93 const Ty &operator()(const Ty &self) const {
98 template <class Ty> struct less_ptr {
99 bool operator()(const Ty* left, const Ty* right) const {
100 return *left < *right;
104 template <class Ty> struct greater_ptr {
105 bool operator()(const Ty* left, const Ty* right) const {
106 return *right < *left;
110 /// An efficient, type-erasing, non-owning reference to a callable. This is
111 /// intended for use as the type of a function parameter that is not used
112 /// after the function in question returns.
114 /// This class does not own the callable, so it is not in general safe to store
116 template<typename Fn> class function_ref;
118 template<typename Ret, typename ...Params>
119 class function_ref<Ret(Params...)> {
120 Ret (*callback)(intptr_t callable, Params ...params) = nullptr;
123 template<typename Callable>
124 static Ret callback_fn(intptr_t callable, Params ...params) {
125 return (*reinterpret_cast<Callable*>(callable))(
126 std::forward<Params>(params)...);
130 function_ref() = default;
131 function_ref(std::nullptr_t) {}
133 template <typename Callable>
134 function_ref(Callable &&callable,
135 typename std::enable_if<
136 !std::is_same<typename std::remove_reference<Callable>::type,
137 function_ref>::value>::type * = nullptr)
138 : callback(callback_fn<typename std::remove_reference<Callable>::type>),
139 callable(reinterpret_cast<intptr_t>(&callable)) {}
141 Ret operator()(Params ...params) const {
142 return callback(callable, std::forward<Params>(params)...);
145 operator bool() const { return callback; }
148 // deleter - Very very very simple method that is used to invoke operator
149 // delete on something. It is used like this:
151 // for_each(V.begin(), B.end(), deleter<Interval>);
153 inline void deleter(T *Ptr) {
157 //===----------------------------------------------------------------------===//
158 // Extra additions to <iterator>
159 //===----------------------------------------------------------------------===//
161 namespace adl_detail {
165 template <typename ContainerTy>
166 auto adl_begin(ContainerTy &&container)
167 -> decltype(begin(std::forward<ContainerTy>(container))) {
168 return begin(std::forward<ContainerTy>(container));
173 template <typename ContainerTy>
174 auto adl_end(ContainerTy &&container)
175 -> decltype(end(std::forward<ContainerTy>(container))) {
176 return end(std::forward<ContainerTy>(container));
181 template <typename T>
182 void adl_swap(T &&lhs, T &&rhs) noexcept(noexcept(swap(std::declval<T>(),
183 std::declval<T>()))) {
184 swap(std::forward<T>(lhs), std::forward<T>(rhs));
187 } // end namespace adl_detail
189 template <typename ContainerTy>
190 auto adl_begin(ContainerTy &&container)
191 -> decltype(adl_detail::adl_begin(std::forward<ContainerTy>(container))) {
192 return adl_detail::adl_begin(std::forward<ContainerTy>(container));
195 template <typename ContainerTy>
196 auto adl_end(ContainerTy &&container)
197 -> decltype(adl_detail::adl_end(std::forward<ContainerTy>(container))) {
198 return adl_detail::adl_end(std::forward<ContainerTy>(container));
201 template <typename T>
202 void adl_swap(T &&lhs, T &&rhs) noexcept(
203 noexcept(adl_detail::adl_swap(std::declval<T>(), std::declval<T>()))) {
204 adl_detail::adl_swap(std::forward<T>(lhs), std::forward<T>(rhs));
207 /// Test whether \p RangeOrContainer is empty. Similar to C++17 std::empty.
208 template <typename T>
209 constexpr bool empty(const T &RangeOrContainer) {
210 return adl_begin(RangeOrContainer) == adl_end(RangeOrContainer);
213 // mapped_iterator - This is a simple iterator adapter that causes a function to
214 // be applied whenever operator* is invoked on the iterator.
216 template <typename ItTy, typename FuncTy,
217 typename FuncReturnTy =
218 decltype(std::declval<FuncTy>()(*std::declval<ItTy>()))>
219 class mapped_iterator
220 : public iterator_adaptor_base<
221 mapped_iterator<ItTy, FuncTy>, ItTy,
222 typename std::iterator_traits<ItTy>::iterator_category,
223 typename std::remove_reference<FuncReturnTy>::type> {
225 mapped_iterator(ItTy U, FuncTy F)
226 : mapped_iterator::iterator_adaptor_base(std::move(U)), F(std::move(F)) {}
228 ItTy getCurrent() { return this->I; }
230 FuncReturnTy operator*() { return F(*this->I); }
236 // map_iterator - Provide a convenient way to create mapped_iterators, just like
237 // make_pair is useful for creating pairs...
238 template <class ItTy, class FuncTy>
239 inline mapped_iterator<ItTy, FuncTy> map_iterator(ItTy I, FuncTy F) {
240 return mapped_iterator<ItTy, FuncTy>(std::move(I), std::move(F));
243 template <class ContainerTy, class FuncTy>
244 auto map_range(ContainerTy &&C, FuncTy F)
245 -> decltype(make_range(map_iterator(C.begin(), F),
246 map_iterator(C.end(), F))) {
247 return make_range(map_iterator(C.begin(), F), map_iterator(C.end(), F));
250 /// Helper to determine if type T has a member called rbegin().
251 template <typename Ty> class has_rbegin_impl {
255 template <typename Inner>
256 static yes& test(Inner *I, decltype(I->rbegin()) * = nullptr);
259 static no& test(...);
262 static const bool value = sizeof(test<Ty>(nullptr)) == sizeof(yes);
265 /// Metafunction to determine if T& or T has a member called rbegin().
266 template <typename Ty>
267 struct has_rbegin : has_rbegin_impl<typename std::remove_reference<Ty>::type> {
270 // Returns an iterator_range over the given container which iterates in reverse.
271 // Note that the container must have rbegin()/rend() methods for this to work.
272 template <typename ContainerTy>
273 auto reverse(ContainerTy &&C,
274 typename std::enable_if<has_rbegin<ContainerTy>::value>::type * =
275 nullptr) -> decltype(make_range(C.rbegin(), C.rend())) {
276 return make_range(C.rbegin(), C.rend());
279 // Returns a std::reverse_iterator wrapped around the given iterator.
280 template <typename IteratorTy>
281 std::reverse_iterator<IteratorTy> make_reverse_iterator(IteratorTy It) {
282 return std::reverse_iterator<IteratorTy>(It);
285 // Returns an iterator_range over the given container which iterates in reverse.
286 // Note that the container must have begin()/end() methods which return
287 // bidirectional iterators for this to work.
288 template <typename ContainerTy>
291 typename std::enable_if<!has_rbegin<ContainerTy>::value>::type * = nullptr)
292 -> decltype(make_range(llvm::make_reverse_iterator(std::end(C)),
293 llvm::make_reverse_iterator(std::begin(C)))) {
294 return make_range(llvm::make_reverse_iterator(std::end(C)),
295 llvm::make_reverse_iterator(std::begin(C)));
298 /// An iterator adaptor that filters the elements of given inner iterators.
300 /// The predicate parameter should be a callable object that accepts the wrapped
301 /// iterator's reference type and returns a bool. When incrementing or
302 /// decrementing the iterator, it will call the predicate on each element and
303 /// skip any where it returns false.
306 /// int A[] = { 1, 2, 3, 4 };
307 /// auto R = make_filter_range(A, [](int N) { return N % 2 == 1; });
308 /// // R contains { 1, 3 }.
311 /// Note: filter_iterator_base implements support for forward iteration.
312 /// filter_iterator_impl exists to provide support for bidirectional iteration,
313 /// conditional on whether the wrapped iterator supports it.
314 template <typename WrappedIteratorT, typename PredicateT, typename IterTag>
315 class filter_iterator_base
316 : public iterator_adaptor_base<
317 filter_iterator_base<WrappedIteratorT, PredicateT, IterTag>,
319 typename std::common_type<
320 IterTag, typename std::iterator_traits<
321 WrappedIteratorT>::iterator_category>::type> {
322 using BaseT = iterator_adaptor_base<
323 filter_iterator_base<WrappedIteratorT, PredicateT, IterTag>,
325 typename std::common_type<
326 IterTag, typename std::iterator_traits<
327 WrappedIteratorT>::iterator_category>::type>;
330 WrappedIteratorT End;
333 void findNextValid() {
334 while (this->I != End && !Pred(*this->I))
338 // Construct the iterator. The begin iterator needs to know where the end
339 // is, so that it can properly stop when it gets there. The end iterator only
340 // needs the predicate to support bidirectional iteration.
341 filter_iterator_base(WrappedIteratorT Begin, WrappedIteratorT End,
343 : BaseT(Begin), End(End), Pred(Pred) {
348 using BaseT::operator++;
350 filter_iterator_base &operator++() {
357 /// Specialization of filter_iterator_base for forward iteration only.
358 template <typename WrappedIteratorT, typename PredicateT,
359 typename IterTag = std::forward_iterator_tag>
360 class filter_iterator_impl
361 : public filter_iterator_base<WrappedIteratorT, PredicateT, IterTag> {
362 using BaseT = filter_iterator_base<WrappedIteratorT, PredicateT, IterTag>;
365 filter_iterator_impl(WrappedIteratorT Begin, WrappedIteratorT End,
367 : BaseT(Begin, End, Pred) {}
370 /// Specialization of filter_iterator_base for bidirectional iteration.
371 template <typename WrappedIteratorT, typename PredicateT>
372 class filter_iterator_impl<WrappedIteratorT, PredicateT,
373 std::bidirectional_iterator_tag>
374 : public filter_iterator_base<WrappedIteratorT, PredicateT,
375 std::bidirectional_iterator_tag> {
376 using BaseT = filter_iterator_base<WrappedIteratorT, PredicateT,
377 std::bidirectional_iterator_tag>;
378 void findPrevValid() {
379 while (!this->Pred(*this->I))
384 using BaseT::operator--;
386 filter_iterator_impl(WrappedIteratorT Begin, WrappedIteratorT End,
388 : BaseT(Begin, End, Pred) {}
390 filter_iterator_impl &operator--() {
399 template <bool is_bidirectional> struct fwd_or_bidi_tag_impl {
400 using type = std::forward_iterator_tag;
403 template <> struct fwd_or_bidi_tag_impl<true> {
404 using type = std::bidirectional_iterator_tag;
407 /// Helper which sets its type member to forward_iterator_tag if the category
408 /// of \p IterT does not derive from bidirectional_iterator_tag, and to
409 /// bidirectional_iterator_tag otherwise.
410 template <typename IterT> struct fwd_or_bidi_tag {
411 using type = typename fwd_or_bidi_tag_impl<std::is_base_of<
412 std::bidirectional_iterator_tag,
413 typename std::iterator_traits<IterT>::iterator_category>::value>::type;
416 } // namespace detail
418 /// Defines filter_iterator to a suitable specialization of
419 /// filter_iterator_impl, based on the underlying iterator's category.
420 template <typename WrappedIteratorT, typename PredicateT>
421 using filter_iterator = filter_iterator_impl<
422 WrappedIteratorT, PredicateT,
423 typename detail::fwd_or_bidi_tag<WrappedIteratorT>::type>;
425 /// Convenience function that takes a range of elements and a predicate,
426 /// and return a new filter_iterator range.
428 /// FIXME: Currently if RangeT && is a rvalue reference to a temporary, the
429 /// lifetime of that temporary is not kept by the returned range object, and the
430 /// temporary is going to be dropped on the floor after the make_iterator_range
431 /// full expression that contains this function call.
432 template <typename RangeT, typename PredicateT>
433 iterator_range<filter_iterator<detail::IterOfRange<RangeT>, PredicateT>>
434 make_filter_range(RangeT &&Range, PredicateT Pred) {
435 using FilterIteratorT =
436 filter_iterator<detail::IterOfRange<RangeT>, PredicateT>;
438 FilterIteratorT(std::begin(std::forward<RangeT>(Range)),
439 std::end(std::forward<RangeT>(Range)), Pred),
440 FilterIteratorT(std::end(std::forward<RangeT>(Range)),
441 std::end(std::forward<RangeT>(Range)), Pred));
444 /// A pseudo-iterator adaptor that is designed to implement "early increment"
447 /// This is *not a normal iterator* and should almost never be used directly. It
448 /// is intended primarily to be used with range based for loops and some range
451 /// The iterator isn't quite an `OutputIterator` or an `InputIterator` but
452 /// somewhere between them. The constraints of these iterators are:
454 /// - On construction or after being incremented, it is comparable and
455 /// dereferencable. It is *not* incrementable.
456 /// - After being dereferenced, it is neither comparable nor dereferencable, it
457 /// is only incrementable.
459 /// This means you can only dereference the iterator once, and you can only
460 /// increment it once between dereferences.
461 template <typename WrappedIteratorT>
462 class early_inc_iterator_impl
463 : public iterator_adaptor_base<early_inc_iterator_impl<WrappedIteratorT>,
464 WrappedIteratorT, std::input_iterator_tag> {
466 iterator_adaptor_base<early_inc_iterator_impl<WrappedIteratorT>,
467 WrappedIteratorT, std::input_iterator_tag>;
469 using PointerT = typename std::iterator_traits<WrappedIteratorT>::pointer;
472 #if LLVM_ENABLE_ABI_BREAKING_CHECKS
473 bool IsEarlyIncremented = false;
477 early_inc_iterator_impl(WrappedIteratorT I) : BaseT(I) {}
479 using BaseT::operator*;
480 typename BaseT::reference operator*() {
481 #if LLVM_ENABLE_ABI_BREAKING_CHECKS
482 assert(!IsEarlyIncremented && "Cannot dereference twice!");
483 IsEarlyIncremented = true;
488 using BaseT::operator++;
489 early_inc_iterator_impl &operator++() {
490 #if LLVM_ENABLE_ABI_BREAKING_CHECKS
491 assert(IsEarlyIncremented && "Cannot increment before dereferencing!");
492 IsEarlyIncremented = false;
497 using BaseT::operator==;
498 bool operator==(const early_inc_iterator_impl &RHS) const {
499 #if LLVM_ENABLE_ABI_BREAKING_CHECKS
500 assert(!IsEarlyIncremented && "Cannot compare after dereferencing!");
502 return BaseT::operator==(RHS);
506 /// Make a range that does early increment to allow mutation of the underlying
507 /// range without disrupting iteration.
509 /// The underlying iterator will be incremented immediately after it is
510 /// dereferenced, allowing deletion of the current node or insertion of nodes to
511 /// not disrupt iteration provided they do not invalidate the *next* iterator --
512 /// the current iterator can be invalidated.
514 /// This requires a very exact pattern of use that is only really suitable to
515 /// range based for loops and other range algorithms that explicitly guarantee
516 /// to dereference exactly once each element, and to increment exactly once each
518 template <typename RangeT>
519 iterator_range<early_inc_iterator_impl<detail::IterOfRange<RangeT>>>
520 make_early_inc_range(RangeT &&Range) {
521 using EarlyIncIteratorT =
522 early_inc_iterator_impl<detail::IterOfRange<RangeT>>;
523 return make_range(EarlyIncIteratorT(std::begin(std::forward<RangeT>(Range))),
524 EarlyIncIteratorT(std::end(std::forward<RangeT>(Range))));
527 // forward declarations required by zip_shortest/zip_first/zip_longest
528 template <typename R, typename UnaryPredicate>
529 bool all_of(R &&range, UnaryPredicate P);
530 template <typename R, typename UnaryPredicate>
531 bool any_of(R &&range, UnaryPredicate P);
533 template <size_t... I> struct index_sequence;
535 template <class... Ts> struct index_sequence_for;
541 // We have to alias this since inlining the actual type at the usage site
542 // in the parameter list of iterator_facade_base<> below ICEs MSVC 2017.
543 template<typename... Iters> struct ZipTupleType {
544 using type = std::tuple<decltype(*declval<Iters>())...>;
547 template <typename ZipType, typename... Iters>
548 using zip_traits = iterator_facade_base<
549 ZipType, typename std::common_type<std::bidirectional_iterator_tag,
550 typename std::iterator_traits<
551 Iters>::iterator_category...>::type,
552 // ^ TODO: Implement random access methods.
553 typename ZipTupleType<Iters...>::type,
554 typename std::iterator_traits<typename std::tuple_element<
555 0, std::tuple<Iters...>>::type>::difference_type,
556 // ^ FIXME: This follows boost::make_zip_iterator's assumption that all
557 // inner iterators have the same difference_type. It would fail if, for
558 // instance, the second field's difference_type were non-numeric while the
560 typename ZipTupleType<Iters...>::type *,
561 typename ZipTupleType<Iters...>::type>;
563 template <typename ZipType, typename... Iters>
564 struct zip_common : public zip_traits<ZipType, Iters...> {
565 using Base = zip_traits<ZipType, Iters...>;
566 using value_type = typename Base::value_type;
568 std::tuple<Iters...> iterators;
571 template <size_t... Ns> value_type deref(index_sequence<Ns...>) const {
572 return value_type(*std::get<Ns>(iterators)...);
575 template <size_t... Ns>
576 decltype(iterators) tup_inc(index_sequence<Ns...>) const {
577 return std::tuple<Iters...>(std::next(std::get<Ns>(iterators))...);
580 template <size_t... Ns>
581 decltype(iterators) tup_dec(index_sequence<Ns...>) const {
582 return std::tuple<Iters...>(std::prev(std::get<Ns>(iterators))...);
586 zip_common(Iters &&... ts) : iterators(std::forward<Iters>(ts)...) {}
588 value_type operator*() { return deref(index_sequence_for<Iters...>{}); }
590 const value_type operator*() const {
591 return deref(index_sequence_for<Iters...>{});
594 ZipType &operator++() {
595 iterators = tup_inc(index_sequence_for<Iters...>{});
596 return *reinterpret_cast<ZipType *>(this);
599 ZipType &operator--() {
600 static_assert(Base::IsBidirectional,
601 "All inner iterators must be at least bidirectional.");
602 iterators = tup_dec(index_sequence_for<Iters...>{});
603 return *reinterpret_cast<ZipType *>(this);
607 template <typename... Iters>
608 struct zip_first : public zip_common<zip_first<Iters...>, Iters...> {
609 using Base = zip_common<zip_first<Iters...>, Iters...>;
611 bool operator==(const zip_first<Iters...> &other) const {
612 return std::get<0>(this->iterators) == std::get<0>(other.iterators);
615 zip_first(Iters &&... ts) : Base(std::forward<Iters>(ts)...) {}
618 template <typename... Iters>
619 class zip_shortest : public zip_common<zip_shortest<Iters...>, Iters...> {
620 template <size_t... Ns>
621 bool test(const zip_shortest<Iters...> &other, index_sequence<Ns...>) const {
622 return all_of(std::initializer_list<bool>{std::get<Ns>(this->iterators) !=
623 std::get<Ns>(other.iterators)...},
628 using Base = zip_common<zip_shortest<Iters...>, Iters...>;
630 zip_shortest(Iters &&... ts) : Base(std::forward<Iters>(ts)...) {}
632 bool operator==(const zip_shortest<Iters...> &other) const {
633 return !test(other, index_sequence_for<Iters...>{});
637 template <template <typename...> class ItType, typename... Args> class zippy {
639 using iterator = ItType<decltype(std::begin(std::declval<Args>()))...>;
640 using iterator_category = typename iterator::iterator_category;
641 using value_type = typename iterator::value_type;
642 using difference_type = typename iterator::difference_type;
643 using pointer = typename iterator::pointer;
644 using reference = typename iterator::reference;
647 std::tuple<Args...> ts;
649 template <size_t... Ns> iterator begin_impl(index_sequence<Ns...>) const {
650 return iterator(std::begin(std::get<Ns>(ts))...);
652 template <size_t... Ns> iterator end_impl(index_sequence<Ns...>) const {
653 return iterator(std::end(std::get<Ns>(ts))...);
657 zippy(Args &&... ts_) : ts(std::forward<Args>(ts_)...) {}
659 iterator begin() const { return begin_impl(index_sequence_for<Args...>{}); }
660 iterator end() const { return end_impl(index_sequence_for<Args...>{}); }
663 } // end namespace detail
665 /// zip iterator for two or more iteratable types.
666 template <typename T, typename U, typename... Args>
667 detail::zippy<detail::zip_shortest, T, U, Args...> zip(T &&t, U &&u,
669 return detail::zippy<detail::zip_shortest, T, U, Args...>(
670 std::forward<T>(t), std::forward<U>(u), std::forward<Args>(args)...);
673 /// zip iterator that, for the sake of efficiency, assumes the first iteratee to
675 template <typename T, typename U, typename... Args>
676 detail::zippy<detail::zip_first, T, U, Args...> zip_first(T &&t, U &&u,
678 return detail::zippy<detail::zip_first, T, U, Args...>(
679 std::forward<T>(t), std::forward<U>(u), std::forward<Args>(args)...);
683 template <typename Iter>
684 static Iter next_or_end(const Iter &I, const Iter &End) {
690 template <typename Iter>
691 static auto deref_or_none(const Iter &I, const Iter &End)
692 -> llvm::Optional<typename std::remove_const<
693 typename std::remove_reference<decltype(*I)>::type>::type> {
699 template <typename Iter> struct ZipLongestItemType {
701 llvm::Optional<typename std::remove_const<typename std::remove_reference<
702 decltype(*std::declval<Iter>())>::type>::type>;
705 template <typename... Iters> struct ZipLongestTupleType {
706 using type = std::tuple<typename ZipLongestItemType<Iters>::type...>;
709 template <typename... Iters>
710 class zip_longest_iterator
711 : public iterator_facade_base<
712 zip_longest_iterator<Iters...>,
713 typename std::common_type<
714 std::forward_iterator_tag,
715 typename std::iterator_traits<Iters>::iterator_category...>::type,
716 typename ZipLongestTupleType<Iters...>::type,
717 typename std::iterator_traits<typename std::tuple_element<
718 0, std::tuple<Iters...>>::type>::difference_type,
719 typename ZipLongestTupleType<Iters...>::type *,
720 typename ZipLongestTupleType<Iters...>::type> {
722 using value_type = typename ZipLongestTupleType<Iters...>::type;
725 std::tuple<Iters...> iterators;
726 std::tuple<Iters...> end_iterators;
728 template <size_t... Ns>
729 bool test(const zip_longest_iterator<Iters...> &other,
730 index_sequence<Ns...>) const {
732 std::initializer_list<bool>{std::get<Ns>(this->iterators) !=
733 std::get<Ns>(other.iterators)...},
737 template <size_t... Ns> value_type deref(index_sequence<Ns...>) const {
739 deref_or_none(std::get<Ns>(iterators), std::get<Ns>(end_iterators))...);
742 template <size_t... Ns>
743 decltype(iterators) tup_inc(index_sequence<Ns...>) const {
744 return std::tuple<Iters...>(
745 next_or_end(std::get<Ns>(iterators), std::get<Ns>(end_iterators))...);
749 zip_longest_iterator(std::pair<Iters &&, Iters &&>... ts)
750 : iterators(std::forward<Iters>(ts.first)...),
751 end_iterators(std::forward<Iters>(ts.second)...) {}
753 value_type operator*() { return deref(index_sequence_for<Iters...>{}); }
755 value_type operator*() const { return deref(index_sequence_for<Iters...>{}); }
757 zip_longest_iterator<Iters...> &operator++() {
758 iterators = tup_inc(index_sequence_for<Iters...>{});
762 bool operator==(const zip_longest_iterator<Iters...> &other) const {
763 return !test(other, index_sequence_for<Iters...>{});
767 template <typename... Args> class zip_longest_range {
770 zip_longest_iterator<decltype(adl_begin(std::declval<Args>()))...>;
771 using iterator_category = typename iterator::iterator_category;
772 using value_type = typename iterator::value_type;
773 using difference_type = typename iterator::difference_type;
774 using pointer = typename iterator::pointer;
775 using reference = typename iterator::reference;
778 std::tuple<Args...> ts;
780 template <size_t... Ns> iterator begin_impl(index_sequence<Ns...>) const {
781 return iterator(std::make_pair(adl_begin(std::get<Ns>(ts)),
782 adl_end(std::get<Ns>(ts)))...);
785 template <size_t... Ns> iterator end_impl(index_sequence<Ns...>) const {
786 return iterator(std::make_pair(adl_end(std::get<Ns>(ts)),
787 adl_end(std::get<Ns>(ts)))...);
791 zip_longest_range(Args &&... ts_) : ts(std::forward<Args>(ts_)...) {}
793 iterator begin() const { return begin_impl(index_sequence_for<Args...>{}); }
794 iterator end() const { return end_impl(index_sequence_for<Args...>{}); }
796 } // namespace detail
798 /// Iterate over two or more iterators at the same time. Iteration continues
799 /// until all iterators reach the end. The llvm::Optional only contains a value
800 /// if the iterator has not reached the end.
801 template <typename T, typename U, typename... Args>
802 detail::zip_longest_range<T, U, Args...> zip_longest(T &&t, U &&u,
804 return detail::zip_longest_range<T, U, Args...>(
805 std::forward<T>(t), std::forward<U>(u), std::forward<Args>(args)...);
808 /// Iterator wrapper that concatenates sequences together.
810 /// This can concatenate different iterators, even with different types, into
811 /// a single iterator provided the value types of all the concatenated
812 /// iterators expose `reference` and `pointer` types that can be converted to
813 /// `ValueT &` and `ValueT *` respectively. It doesn't support more
814 /// interesting/customized pointer or reference types.
816 /// Currently this only supports forward or higher iterator categories as
817 /// inputs and always exposes a forward iterator interface.
818 template <typename ValueT, typename... IterTs>
819 class concat_iterator
820 : public iterator_facade_base<concat_iterator<ValueT, IterTs...>,
821 std::forward_iterator_tag, ValueT> {
822 using BaseT = typename concat_iterator::iterator_facade_base;
824 /// We store both the current and end iterators for each concatenated
825 /// sequence in a tuple of pairs.
827 /// Note that something like iterator_range seems nice at first here, but the
828 /// range properties are of little benefit and end up getting in the way
829 /// because we need to do mutation on the current iterators.
830 std::tuple<IterTs...> Begins;
831 std::tuple<IterTs...> Ends;
833 /// Attempts to increment a specific iterator.
835 /// Returns true if it was able to increment the iterator. Returns false if
836 /// the iterator is already at the end iterator.
837 template <size_t Index> bool incrementHelper() {
838 auto &Begin = std::get<Index>(Begins);
839 auto &End = std::get<Index>(Ends);
847 /// Increments the first non-end iterator.
849 /// It is an error to call this with all iterators at the end.
850 template <size_t... Ns> void increment(index_sequence<Ns...>) {
851 // Build a sequence of functions to increment each iterator if possible.
852 bool (concat_iterator::*IncrementHelperFns[])() = {
853 &concat_iterator::incrementHelper<Ns>...};
855 // Loop over them, and stop as soon as we succeed at incrementing one.
856 for (auto &IncrementHelperFn : IncrementHelperFns)
857 if ((this->*IncrementHelperFn)())
860 llvm_unreachable("Attempted to increment an end concat iterator!");
863 /// Returns null if the specified iterator is at the end. Otherwise,
864 /// dereferences the iterator and returns the address of the resulting
866 template <size_t Index> ValueT *getHelper() const {
867 auto &Begin = std::get<Index>(Begins);
868 auto &End = std::get<Index>(Ends);
875 /// Finds the first non-end iterator, dereferences, and returns the resulting
878 /// It is an error to call this with all iterators at the end.
879 template <size_t... Ns> ValueT &get(index_sequence<Ns...>) const {
880 // Build a sequence of functions to get from iterator if possible.
881 ValueT *(concat_iterator::*GetHelperFns[])() const = {
882 &concat_iterator::getHelper<Ns>...};
884 // Loop over them, and return the first result we find.
885 for (auto &GetHelperFn : GetHelperFns)
886 if (ValueT *P = (this->*GetHelperFn)())
889 llvm_unreachable("Attempted to get a pointer from an end concat iterator!");
893 /// Constructs an iterator from a squence of ranges.
895 /// We need the full range to know how to switch between each of the
897 template <typename... RangeTs>
898 explicit concat_iterator(RangeTs &&... Ranges)
899 : Begins(std::begin(Ranges)...), Ends(std::end(Ranges)...) {}
901 using BaseT::operator++;
903 concat_iterator &operator++() {
904 increment(index_sequence_for<IterTs...>());
908 ValueT &operator*() const { return get(index_sequence_for<IterTs...>()); }
910 bool operator==(const concat_iterator &RHS) const {
911 return Begins == RHS.Begins && Ends == RHS.Ends;
917 /// Helper to store a sequence of ranges being concatenated and access them.
919 /// This is designed to facilitate providing actual storage when temporaries
920 /// are passed into the constructor such that we can use it as part of range
922 template <typename ValueT, typename... RangeTs> class concat_range {
925 concat_iterator<ValueT,
926 decltype(std::begin(std::declval<RangeTs &>()))...>;
929 std::tuple<RangeTs...> Ranges;
931 template <size_t... Ns> iterator begin_impl(index_sequence<Ns...>) {
932 return iterator(std::get<Ns>(Ranges)...);
934 template <size_t... Ns> iterator end_impl(index_sequence<Ns...>) {
935 return iterator(make_range(std::end(std::get<Ns>(Ranges)),
936 std::end(std::get<Ns>(Ranges)))...);
940 concat_range(RangeTs &&... Ranges)
941 : Ranges(std::forward<RangeTs>(Ranges)...) {}
943 iterator begin() { return begin_impl(index_sequence_for<RangeTs...>{}); }
944 iterator end() { return end_impl(index_sequence_for<RangeTs...>{}); }
947 } // end namespace detail
949 /// Concatenated range across two or more ranges.
951 /// The desired value type must be explicitly specified.
952 template <typename ValueT, typename... RangeTs>
953 detail::concat_range<ValueT, RangeTs...> concat(RangeTs &&... Ranges) {
954 static_assert(sizeof...(RangeTs) > 1,
955 "Need more than one range to concatenate!");
956 return detail::concat_range<ValueT, RangeTs...>(
957 std::forward<RangeTs>(Ranges)...);
960 //===----------------------------------------------------------------------===//
961 // Extra additions to <utility>
962 //===----------------------------------------------------------------------===//
964 /// Function object to check whether the first component of a std::pair
965 /// compares less than the first component of another std::pair.
967 template <typename T> bool operator()(const T &lhs, const T &rhs) const {
968 return lhs.first < rhs.first;
972 /// Function object to check whether the second component of a std::pair
973 /// compares less than the second component of another std::pair.
975 template <typename T> bool operator()(const T &lhs, const T &rhs) const {
976 return lhs.second < rhs.second;
980 /// \brief Function object to apply a binary function to the first component of
982 template<typename FuncTy>
986 template <typename T>
987 auto operator()(const T &lhs, const T &rhs) const
988 -> decltype(func(lhs.first, rhs.first)) {
989 return func(lhs.first, rhs.first);
993 // A subset of N3658. More stuff can be added as-needed.
995 /// Represents a compile-time sequence of integers.
996 template <class T, T... I> struct integer_sequence {
997 using value_type = T;
999 static constexpr size_t size() { return sizeof...(I); }
1002 /// Alias for the common case of a sequence of size_ts.
1003 template <size_t... I>
1004 struct index_sequence : integer_sequence<std::size_t, I...> {};
1006 template <std::size_t N, std::size_t... I>
1007 struct build_index_impl : build_index_impl<N - 1, N - 1, I...> {};
1008 template <std::size_t... I>
1009 struct build_index_impl<0, I...> : index_sequence<I...> {};
1011 /// Creates a compile-time integer sequence for a parameter pack.
1012 template <class... Ts>
1013 struct index_sequence_for : build_index_impl<sizeof...(Ts)> {};
1015 /// Utility type to build an inheritance chain that makes it easy to rank
1016 /// overload candidates.
1017 template <int N> struct rank : rank<N - 1> {};
1018 template <> struct rank<0> {};
1020 /// traits class for checking whether type T is one of any of the given
1021 /// types in the variadic list.
1022 template <typename T, typename... Ts> struct is_one_of {
1023 static const bool value = false;
1026 template <typename T, typename U, typename... Ts>
1027 struct is_one_of<T, U, Ts...> {
1028 static const bool value =
1029 std::is_same<T, U>::value || is_one_of<T, Ts...>::value;
1032 /// traits class for checking whether type T is a base class for all
1033 /// the given types in the variadic list.
1034 template <typename T, typename... Ts> struct are_base_of {
1035 static const bool value = true;
1038 template <typename T, typename U, typename... Ts>
1039 struct are_base_of<T, U, Ts...> {
1040 static const bool value =
1041 std::is_base_of<T, U>::value && are_base_of<T, Ts...>::value;
1044 //===----------------------------------------------------------------------===//
1045 // Extra additions for arrays
1046 //===----------------------------------------------------------------------===//
1048 /// Find the length of an array.
1049 template <class T, std::size_t N>
1050 constexpr inline size_t array_lengthof(T (&)[N]) {
1054 /// Adapt std::less<T> for array_pod_sort.
1055 template<typename T>
1056 inline int array_pod_sort_comparator(const void *P1, const void *P2) {
1057 if (std::less<T>()(*reinterpret_cast<const T*>(P1),
1058 *reinterpret_cast<const T*>(P2)))
1060 if (std::less<T>()(*reinterpret_cast<const T*>(P2),
1061 *reinterpret_cast<const T*>(P1)))
1066 /// get_array_pod_sort_comparator - This is an internal helper function used to
1067 /// get type deduction of T right.
1068 template<typename T>
1069 inline int (*get_array_pod_sort_comparator(const T &))
1070 (const void*, const void*) {
1071 return array_pod_sort_comparator<T>;
1074 /// array_pod_sort - This sorts an array with the specified start and end
1075 /// extent. This is just like std::sort, except that it calls qsort instead of
1076 /// using an inlined template. qsort is slightly slower than std::sort, but
1077 /// most sorts are not performance critical in LLVM and std::sort has to be
1078 /// template instantiated for each type, leading to significant measured code
1079 /// bloat. This function should generally be used instead of std::sort where
1082 /// This function assumes that you have simple POD-like types that can be
1083 /// compared with std::less and can be moved with memcpy. If this isn't true,
1084 /// you should use std::sort.
1086 /// NOTE: If qsort_r were portable, we could allow a custom comparator and
1087 /// default to std::less.
1088 template<class IteratorTy>
1089 inline void array_pod_sort(IteratorTy Start, IteratorTy End) {
1090 // Don't inefficiently call qsort with one element or trigger undefined
1091 // behavior with an empty sequence.
1092 auto NElts = End - Start;
1093 if (NElts <= 1) return;
1094 #ifdef EXPENSIVE_CHECKS
1095 std::mt19937 Generator(std::random_device{}());
1096 std::shuffle(Start, End, Generator);
1098 qsort(&*Start, NElts, sizeof(*Start), get_array_pod_sort_comparator(*Start));
1101 template <class IteratorTy>
1102 inline void array_pod_sort(
1103 IteratorTy Start, IteratorTy End,
1105 const typename std::iterator_traits<IteratorTy>::value_type *,
1106 const typename std::iterator_traits<IteratorTy>::value_type *)) {
1107 // Don't inefficiently call qsort with one element or trigger undefined
1108 // behavior with an empty sequence.
1109 auto NElts = End - Start;
1110 if (NElts <= 1) return;
1111 #ifdef EXPENSIVE_CHECKS
1112 std::mt19937 Generator(std::random_device{}());
1113 std::shuffle(Start, End, Generator);
1115 qsort(&*Start, NElts, sizeof(*Start),
1116 reinterpret_cast<int (*)(const void *, const void *)>(Compare));
1119 // Provide wrappers to std::sort which shuffle the elements before sorting
1120 // to help uncover non-deterministic behavior (PR35135).
1121 template <typename IteratorTy>
1122 inline void sort(IteratorTy Start, IteratorTy End) {
1123 #ifdef EXPENSIVE_CHECKS
1124 std::mt19937 Generator(std::random_device{}());
1125 std::shuffle(Start, End, Generator);
1127 std::sort(Start, End);
1130 template <typename Container> inline void sort(Container &&C) {
1131 llvm::sort(adl_begin(C), adl_end(C));
1134 template <typename IteratorTy, typename Compare>
1135 inline void sort(IteratorTy Start, IteratorTy End, Compare Comp) {
1136 #ifdef EXPENSIVE_CHECKS
1137 std::mt19937 Generator(std::random_device{}());
1138 std::shuffle(Start, End, Generator);
1140 std::sort(Start, End, Comp);
1143 template <typename Container, typename Compare>
1144 inline void sort(Container &&C, Compare Comp) {
1145 llvm::sort(adl_begin(C), adl_end(C), Comp);
1148 //===----------------------------------------------------------------------===//
1149 // Extra additions to <algorithm>
1150 //===----------------------------------------------------------------------===//
1152 /// For a container of pointers, deletes the pointers and then clears the
1154 template<typename Container>
1155 void DeleteContainerPointers(Container &C) {
1161 /// In a container of pairs (usually a map) whose second element is a pointer,
1162 /// deletes the second elements and then clears the container.
1163 template<typename Container>
1164 void DeleteContainerSeconds(Container &C) {
1170 /// Get the size of a range. This is a wrapper function around std::distance
1171 /// which is only enabled when the operation is O(1).
1172 template <typename R>
1173 auto size(R &&Range, typename std::enable_if<
1174 std::is_same<typename std::iterator_traits<decltype(
1175 Range.begin())>::iterator_category,
1176 std::random_access_iterator_tag>::value,
1177 void>::type * = nullptr)
1178 -> decltype(std::distance(Range.begin(), Range.end())) {
1179 return std::distance(Range.begin(), Range.end());
1182 /// Provide wrappers to std::for_each which take ranges instead of having to
1183 /// pass begin/end explicitly.
1184 template <typename R, typename UnaryPredicate>
1185 UnaryPredicate for_each(R &&Range, UnaryPredicate P) {
1186 return std::for_each(adl_begin(Range), adl_end(Range), P);
1189 /// Provide wrappers to std::all_of which take ranges instead of having to pass
1190 /// begin/end explicitly.
1191 template <typename R, typename UnaryPredicate>
1192 bool all_of(R &&Range, UnaryPredicate P) {
1193 return std::all_of(adl_begin(Range), adl_end(Range), P);
1196 /// Provide wrappers to std::any_of which take ranges instead of having to pass
1197 /// begin/end explicitly.
1198 template <typename R, typename UnaryPredicate>
1199 bool any_of(R &&Range, UnaryPredicate P) {
1200 return std::any_of(adl_begin(Range), adl_end(Range), P);
1203 /// Provide wrappers to std::none_of which take ranges instead of having to pass
1204 /// begin/end explicitly.
1205 template <typename R, typename UnaryPredicate>
1206 bool none_of(R &&Range, UnaryPredicate P) {
1207 return std::none_of(adl_begin(Range), adl_end(Range), P);
1210 /// Provide wrappers to std::find which take ranges instead of having to pass
1211 /// begin/end explicitly.
1212 template <typename R, typename T>
1213 auto find(R &&Range, const T &Val) -> decltype(adl_begin(Range)) {
1214 return std::find(adl_begin(Range), adl_end(Range), Val);
1217 /// Provide wrappers to std::find_if which take ranges instead of having to pass
1218 /// begin/end explicitly.
1219 template <typename R, typename UnaryPredicate>
1220 auto find_if(R &&Range, UnaryPredicate P) -> decltype(adl_begin(Range)) {
1221 return std::find_if(adl_begin(Range), adl_end(Range), P);
1224 template <typename R, typename UnaryPredicate>
1225 auto find_if_not(R &&Range, UnaryPredicate P) -> decltype(adl_begin(Range)) {
1226 return std::find_if_not(adl_begin(Range), adl_end(Range), P);
1229 /// Provide wrappers to std::remove_if which take ranges instead of having to
1230 /// pass begin/end explicitly.
1231 template <typename R, typename UnaryPredicate>
1232 auto remove_if(R &&Range, UnaryPredicate P) -> decltype(adl_begin(Range)) {
1233 return std::remove_if(adl_begin(Range), adl_end(Range), P);
1236 /// Provide wrappers to std::copy_if which take ranges instead of having to
1237 /// pass begin/end explicitly.
1238 template <typename R, typename OutputIt, typename UnaryPredicate>
1239 OutputIt copy_if(R &&Range, OutputIt Out, UnaryPredicate P) {
1240 return std::copy_if(adl_begin(Range), adl_end(Range), Out, P);
1243 template <typename R, typename OutputIt>
1244 OutputIt copy(R &&Range, OutputIt Out) {
1245 return std::copy(adl_begin(Range), adl_end(Range), Out);
1248 /// Wrapper function around std::find to detect if an element exists
1250 template <typename R, typename E>
1251 bool is_contained(R &&Range, const E &Element) {
1252 return std::find(adl_begin(Range), adl_end(Range), Element) != adl_end(Range);
1255 /// Wrapper function around std::count to count the number of times an element
1256 /// \p Element occurs in the given range \p Range.
1257 template <typename R, typename E>
1258 auto count(R &&Range, const E &Element) ->
1259 typename std::iterator_traits<decltype(adl_begin(Range))>::difference_type {
1260 return std::count(adl_begin(Range), adl_end(Range), Element);
1263 /// Wrapper function around std::count_if to count the number of times an
1264 /// element satisfying a given predicate occurs in a range.
1265 template <typename R, typename UnaryPredicate>
1266 auto count_if(R &&Range, UnaryPredicate P) ->
1267 typename std::iterator_traits<decltype(adl_begin(Range))>::difference_type {
1268 return std::count_if(adl_begin(Range), adl_end(Range), P);
1271 /// Wrapper function around std::transform to apply a function to a range and
1272 /// store the result elsewhere.
1273 template <typename R, typename OutputIt, typename UnaryPredicate>
1274 OutputIt transform(R &&Range, OutputIt d_first, UnaryPredicate P) {
1275 return std::transform(adl_begin(Range), adl_end(Range), d_first, P);
1278 /// Provide wrappers to std::partition which take ranges instead of having to
1279 /// pass begin/end explicitly.
1280 template <typename R, typename UnaryPredicate>
1281 auto partition(R &&Range, UnaryPredicate P) -> decltype(adl_begin(Range)) {
1282 return std::partition(adl_begin(Range), adl_end(Range), P);
1285 /// Provide wrappers to std::lower_bound which take ranges instead of having to
1286 /// pass begin/end explicitly.
1287 template <typename R, typename T>
1288 auto lower_bound(R &&Range, T &&Value) -> decltype(adl_begin(Range)) {
1289 return std::lower_bound(adl_begin(Range), adl_end(Range),
1290 std::forward<T>(Value));
1293 template <typename R, typename T, typename Compare>
1294 auto lower_bound(R &&Range, T &&Value, Compare C)
1295 -> decltype(adl_begin(Range)) {
1296 return std::lower_bound(adl_begin(Range), adl_end(Range),
1297 std::forward<T>(Value), C);
1300 /// Provide wrappers to std::upper_bound which take ranges instead of having to
1301 /// pass begin/end explicitly.
1302 template <typename R, typename T>
1303 auto upper_bound(R &&Range, T &&Value) -> decltype(adl_begin(Range)) {
1304 return std::upper_bound(adl_begin(Range), adl_end(Range),
1305 std::forward<T>(Value));
1308 template <typename R, typename T, typename Compare>
1309 auto upper_bound(R &&Range, T &&Value, Compare C)
1310 -> decltype(adl_begin(Range)) {
1311 return std::upper_bound(adl_begin(Range), adl_end(Range),
1312 std::forward<T>(Value), C);
1315 template <typename R>
1316 void stable_sort(R &&Range) {
1317 std::stable_sort(adl_begin(Range), adl_end(Range));
1320 template <typename R, typename Compare>
1321 void stable_sort(R &&Range, Compare C) {
1322 std::stable_sort(adl_begin(Range), adl_end(Range), C);
1325 /// Binary search for the first iterator in a range where a predicate is false.
1326 /// Requires that C is always true below some limit, and always false above it.
1327 template <typename R, typename Predicate,
1328 typename Val = decltype(*adl_begin(std::declval<R>()))>
1329 auto partition_point(R &&Range, Predicate P) -> decltype(adl_begin(Range)) {
1330 return std::partition_point(adl_begin(Range), adl_end(Range), P);
1333 /// Wrapper function around std::equal to detect if all elements
1334 /// in a container are same.
1335 template <typename R>
1336 bool is_splat(R &&Range) {
1337 size_t range_size = size(Range);
1338 return range_size != 0 && (range_size == 1 ||
1339 std::equal(adl_begin(Range) + 1, adl_end(Range), adl_begin(Range)));
1342 /// Given a range of type R, iterate the entire range and return a
1343 /// SmallVector with elements of the vector. This is useful, for example,
1344 /// when you want to iterate a range and then sort the results.
1345 template <unsigned Size, typename R>
1346 SmallVector<typename std::remove_const<detail::ValueOfRange<R>>::type, Size>
1347 to_vector(R &&Range) {
1348 return {adl_begin(Range), adl_end(Range)};
1351 /// Provide a container algorithm similar to C++ Library Fundamentals v2's
1352 /// `erase_if` which is equivalent to:
1354 /// C.erase(remove_if(C, pred), C.end());
1356 /// This version works for any container with an erase method call accepting
1358 template <typename Container, typename UnaryPredicate>
1359 void erase_if(Container &C, UnaryPredicate P) {
1360 C.erase(remove_if(C, P), C.end());
1363 /// Given a sequence container Cont, replace the range [ContIt, ContEnd) with
1364 /// the range [ValIt, ValEnd) (which is not from the same container).
1365 template<typename Container, typename RandomAccessIterator>
1366 void replace(Container &Cont, typename Container::iterator ContIt,
1367 typename Container::iterator ContEnd, RandomAccessIterator ValIt,
1368 RandomAccessIterator ValEnd) {
1370 if (ValIt == ValEnd) {
1371 Cont.erase(ContIt, ContEnd);
1373 } else if (ContIt == ContEnd) {
1374 Cont.insert(ContIt, ValIt, ValEnd);
1377 *ContIt++ = *ValIt++;
1381 /// Given a sequence container Cont, replace the range [ContIt, ContEnd) with
1383 template<typename Container, typename Range = std::initializer_list<
1384 typename Container::value_type>>
1385 void replace(Container &Cont, typename Container::iterator ContIt,
1386 typename Container::iterator ContEnd, Range R) {
1387 replace(Cont, ContIt, ContEnd, R.begin(), R.end());
1390 //===----------------------------------------------------------------------===//
1391 // Extra additions to <memory>
1392 //===----------------------------------------------------------------------===//
1394 // Implement make_unique according to N3656.
1396 /// Constructs a `new T()` with the given args and returns a
1397 /// `unique_ptr<T>` which owns the object.
1401 /// auto p = make_unique<int>();
1402 /// auto p = make_unique<std::tuple<int, int>>(0, 1);
1403 template <class T, class... Args>
1404 typename std::enable_if<!std::is_array<T>::value, std::unique_ptr<T>>::type
1405 make_unique(Args &&... args) {
1406 return std::unique_ptr<T>(new T(std::forward<Args>(args)...));
1409 /// Constructs a `new T[n]` with the given args and returns a
1410 /// `unique_ptr<T[]>` which owns the object.
1412 /// \param n size of the new array.
1416 /// auto p = make_unique<int[]>(2); // value-initializes the array with 0's.
1418 typename std::enable_if<std::is_array<T>::value && std::extent<T>::value == 0,
1419 std::unique_ptr<T>>::type
1420 make_unique(size_t n) {
1421 return std::unique_ptr<T>(new typename std::remove_extent<T>::type[n]());
1424 /// This function isn't used and is only here to provide better compile errors.
1425 template <class T, class... Args>
1426 typename std::enable_if<std::extent<T>::value != 0>::type
1427 make_unique(Args &&...) = delete;
1429 struct FreeDeleter {
1430 void operator()(void* v) {
1435 template<typename First, typename Second>
1437 size_t operator()(const std::pair<First, Second> &P) const {
1438 return std::hash<First>()(P.first) * 31 + std::hash<Second>()(P.second);
1442 /// A functor like C++14's std::less<void> in its absence.
1444 template <typename A, typename B> bool operator()(A &&a, B &&b) const {
1445 return std::forward<A>(a) < std::forward<B>(b);
1449 /// A functor like C++14's std::equal<void> in its absence.
1451 template <typename A, typename B> bool operator()(A &&a, B &&b) const {
1452 return std::forward<A>(a) == std::forward<B>(b);
1456 /// Binary functor that adapts to any other binary functor after dereferencing
1458 template <typename T> struct deref {
1461 // Could be further improved to cope with non-derivable functors and
1462 // non-binary functors (should be a variadic template member function
1464 template <typename A, typename B>
1465 auto operator()(A &lhs, B &rhs) const -> decltype(func(*lhs, *rhs)) {
1468 return func(*lhs, *rhs);
1474 template <typename R> class enumerator_iter;
1476 template <typename R> struct result_pair {
1477 using value_reference =
1478 typename std::iterator_traits<IterOfRange<R>>::reference;
1480 friend class enumerator_iter<R>;
1482 result_pair() = default;
1483 result_pair(std::size_t Index, IterOfRange<R> Iter)
1484 : Index(Index), Iter(Iter) {}
1486 result_pair<R> &operator=(const result_pair<R> &Other) {
1487 Index = Other.Index;
1492 std::size_t index() const { return Index; }
1493 const value_reference value() const { return *Iter; }
1494 value_reference value() { return *Iter; }
1497 std::size_t Index = std::numeric_limits<std::size_t>::max();
1498 IterOfRange<R> Iter;
1501 template <typename R>
1502 class enumerator_iter
1503 : public iterator_facade_base<
1504 enumerator_iter<R>, std::forward_iterator_tag, result_pair<R>,
1505 typename std::iterator_traits<IterOfRange<R>>::difference_type,
1506 typename std::iterator_traits<IterOfRange<R>>::pointer,
1507 typename std::iterator_traits<IterOfRange<R>>::reference> {
1508 using result_type = result_pair<R>;
1511 explicit enumerator_iter(IterOfRange<R> EndIter)
1512 : Result(std::numeric_limits<size_t>::max(), EndIter) {}
1514 enumerator_iter(std::size_t Index, IterOfRange<R> Iter)
1515 : Result(Index, Iter) {}
1517 result_type &operator*() { return Result; }
1518 const result_type &operator*() const { return Result; }
1520 enumerator_iter<R> &operator++() {
1521 assert(Result.Index != std::numeric_limits<size_t>::max());
1527 bool operator==(const enumerator_iter<R> &RHS) const {
1528 // Don't compare indices here, only iterators. It's possible for an end
1529 // iterator to have different indices depending on whether it was created
1530 // by calling std::end() versus incrementing a valid iterator.
1531 return Result.Iter == RHS.Result.Iter;
1534 enumerator_iter<R> &operator=(const enumerator_iter<R> &Other) {
1535 Result = Other.Result;
1543 template <typename R> class enumerator {
1545 explicit enumerator(R &&Range) : TheRange(std::forward<R>(Range)) {}
1547 enumerator_iter<R> begin() {
1548 return enumerator_iter<R>(0, std::begin(TheRange));
1551 enumerator_iter<R> end() {
1552 return enumerator_iter<R>(std::end(TheRange));
1559 } // end namespace detail
1561 /// Given an input range, returns a new range whose values are are pair (A,B)
1562 /// such that A is the 0-based index of the item in the sequence, and B is
1563 /// the value from the original sequence. Example:
1565 /// std::vector<char> Items = {'A', 'B', 'C', 'D'};
1566 /// for (auto X : enumerate(Items)) {
1567 /// printf("Item %d - %c\n", X.index(), X.value());
1576 template <typename R> detail::enumerator<R> enumerate(R &&TheRange) {
1577 return detail::enumerator<R>(std::forward<R>(TheRange));
1582 template <typename F, typename Tuple, std::size_t... I>
1583 auto apply_tuple_impl(F &&f, Tuple &&t, index_sequence<I...>)
1584 -> decltype(std::forward<F>(f)(std::get<I>(std::forward<Tuple>(t))...)) {
1585 return std::forward<F>(f)(std::get<I>(std::forward<Tuple>(t))...);
1588 } // end namespace detail
1590 /// Given an input tuple (a1, a2, ..., an), pass the arguments of the
1591 /// tuple variadically to f as if by calling f(a1, a2, ..., an) and
1592 /// return the result.
1593 template <typename F, typename Tuple>
1594 auto apply_tuple(F &&f, Tuple &&t) -> decltype(detail::apply_tuple_impl(
1595 std::forward<F>(f), std::forward<Tuple>(t),
1597 std::tuple_size<typename std::decay<Tuple>::type>::value>{})) {
1598 using Indices = build_index_impl<
1599 std::tuple_size<typename std::decay<Tuple>::type>::value>;
1601 return detail::apply_tuple_impl(std::forward<F>(f), std::forward<Tuple>(t),
1605 /// Return true if the sequence [Begin, End) has exactly N items. Runs in O(N)
1606 /// time. Not meant for use with random-access iterators.
1607 template <typename IterTy>
1609 IterTy &&Begin, IterTy &&End, unsigned N,
1610 typename std::enable_if<
1612 typename std::iterator_traits<typename std::remove_reference<
1613 decltype(Begin)>::type>::iterator_category,
1614 std::random_access_iterator_tag>::value,
1615 void>::type * = nullptr) {
1616 for (; N; --N, ++Begin)
1618 return false; // Too few.
1619 return Begin == End;
1622 /// Return true if the sequence [Begin, End) has N or more items. Runs in O(N)
1623 /// time. Not meant for use with random-access iterators.
1624 template <typename IterTy>
1625 bool hasNItemsOrMore(
1626 IterTy &&Begin, IterTy &&End, unsigned N,
1627 typename std::enable_if<
1629 typename std::iterator_traits<typename std::remove_reference<
1630 decltype(Begin)>::type>::iterator_category,
1631 std::random_access_iterator_tag>::value,
1632 void>::type * = nullptr) {
1633 for (; N; --N, ++Begin)
1635 return false; // Too few.
1639 /// Returns a raw pointer that represents the same address as the argument.
1641 /// The late bound return should be removed once we move to C++14 to better
1642 /// align with the C++20 declaration. Also, this implementation can be removed
1643 /// once we move to C++20 where it's defined as std::to_addres()
1645 /// The std::pointer_traits<>::to_address(p) variations of these overloads has
1646 /// not been implemented.
1647 template <class Ptr> auto to_address(const Ptr &P) -> decltype(P.operator->()) {
1648 return P.operator->();
1650 template <class T> constexpr T *to_address(T *P) { return P; }
1652 } // end namespace llvm
1654 #endif // LLVM_ADT_STLEXTRAS_H