//===- llvm/ADT/STLExtras.h - Useful STL related functions ------*- C++ -*-===// // // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. // See https://llvm.org/LICENSE.txt for license information. // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception // //===----------------------------------------------------------------------===// // // This file contains some templates that are useful if you are working with the // STL at all. // // No library is required when using these functions. // //===----------------------------------------------------------------------===// #ifndef LLVM_ADT_STLEXTRAS_H #define LLVM_ADT_STLEXTRAS_H #include "llvm/ADT/Optional.h" #include "llvm/ADT/SmallVector.h" #include "llvm/ADT/iterator.h" #include "llvm/ADT/iterator_range.h" #include "llvm/Config/abi-breaking.h" #include "llvm/Support/ErrorHandling.h" #include #include #include #include #include #include #include #include #include #include #include #include #include #ifdef EXPENSIVE_CHECKS #include // for std::mt19937 #endif namespace llvm { // Only used by compiler if both template types are the same. Useful when // using SFINAE to test for the existence of member functions. template struct SameType; namespace detail { template using IterOfRange = decltype(std::begin(std::declval())); template using ValueOfRange = typename std::remove_reference()))>::type; } // end namespace detail //===----------------------------------------------------------------------===// // Extra additions to //===----------------------------------------------------------------------===// template struct negation : std::integral_constant {}; template struct conjunction : std::true_type {}; template struct conjunction : B1 {}; template struct conjunction : std::conditional, B1>::type {}; template struct make_const_ptr { using type = typename std::add_pointer::type>::type; }; template struct make_const_ref { using type = typename std::add_lvalue_reference< typename std::add_const::type>::type; }; //===----------------------------------------------------------------------===// // Extra additions to //===----------------------------------------------------------------------===// template struct identity { using argument_type = Ty; Ty &operator()(Ty &self) const { return self; } const Ty &operator()(const Ty &self) const { return self; } }; /// An efficient, type-erasing, non-owning reference to a callable. This is /// intended for use as the type of a function parameter that is not used /// after the function in question returns. /// /// This class does not own the callable, so it is not in general safe to store /// a function_ref. template class function_ref; template class function_ref { Ret (*callback)(intptr_t callable, Params ...params) = nullptr; intptr_t callable; template static Ret callback_fn(intptr_t callable, Params ...params) { return (*reinterpret_cast(callable))( std::forward(params)...); } public: function_ref() = default; function_ref(std::nullptr_t) {} template function_ref(Callable &&callable, typename std::enable_if< !std::is_same::type, function_ref>::value>::type * = nullptr) : callback(callback_fn::type>), callable(reinterpret_cast(&callable)) {} Ret operator()(Params ...params) const { return callback(callable, std::forward(params)...); } operator bool() const { return callback; } }; // deleter - Very very very simple method that is used to invoke operator // delete on something. It is used like this: // // for_each(V.begin(), B.end(), deleter); template inline void deleter(T *Ptr) { delete Ptr; } //===----------------------------------------------------------------------===// // Extra additions to //===----------------------------------------------------------------------===// namespace adl_detail { using std::begin; template auto adl_begin(ContainerTy &&container) -> decltype(begin(std::forward(container))) { return begin(std::forward(container)); } using std::end; template auto adl_end(ContainerTy &&container) -> decltype(end(std::forward(container))) { return end(std::forward(container)); } using std::swap; template void adl_swap(T &&lhs, T &&rhs) noexcept(noexcept(swap(std::declval(), std::declval()))) { swap(std::forward(lhs), std::forward(rhs)); } } // end namespace adl_detail template auto adl_begin(ContainerTy &&container) -> decltype(adl_detail::adl_begin(std::forward(container))) { return adl_detail::adl_begin(std::forward(container)); } template auto adl_end(ContainerTy &&container) -> decltype(adl_detail::adl_end(std::forward(container))) { return adl_detail::adl_end(std::forward(container)); } template void adl_swap(T &&lhs, T &&rhs) noexcept( noexcept(adl_detail::adl_swap(std::declval(), std::declval()))) { adl_detail::adl_swap(std::forward(lhs), std::forward(rhs)); } /// Test whether \p RangeOrContainer is empty. Similar to C++17 std::empty. template constexpr bool empty(const T &RangeOrContainer) { return adl_begin(RangeOrContainer) == adl_end(RangeOrContainer); } // mapped_iterator - This is a simple iterator adapter that causes a function to // be applied whenever operator* is invoked on the iterator. template ()(*std::declval()))> class mapped_iterator : public iterator_adaptor_base< mapped_iterator, ItTy, typename std::iterator_traits::iterator_category, typename std::remove_reference::type> { public: mapped_iterator(ItTy U, FuncTy F) : mapped_iterator::iterator_adaptor_base(std::move(U)), F(std::move(F)) {} ItTy getCurrent() { return this->I; } FuncReturnTy operator*() { return F(*this->I); } private: FuncTy F; }; // map_iterator - Provide a convenient way to create mapped_iterators, just like // make_pair is useful for creating pairs... template inline mapped_iterator map_iterator(ItTy I, FuncTy F) { return mapped_iterator(std::move(I), std::move(F)); } template auto map_range(ContainerTy &&C, FuncTy F) -> decltype(make_range(map_iterator(C.begin(), F), map_iterator(C.end(), F))) { return make_range(map_iterator(C.begin(), F), map_iterator(C.end(), F)); } /// Helper to determine if type T has a member called rbegin(). template class has_rbegin_impl { using yes = char[1]; using no = char[2]; template static yes& test(Inner *I, decltype(I->rbegin()) * = nullptr); template static no& test(...); public: static const bool value = sizeof(test(nullptr)) == sizeof(yes); }; /// Metafunction to determine if T& or T has a member called rbegin(). template struct has_rbegin : has_rbegin_impl::type> { }; // Returns an iterator_range over the given container which iterates in reverse. // Note that the container must have rbegin()/rend() methods for this to work. template auto reverse(ContainerTy &&C, typename std::enable_if::value>::type * = nullptr) -> decltype(make_range(C.rbegin(), C.rend())) { return make_range(C.rbegin(), C.rend()); } // Returns a std::reverse_iterator wrapped around the given iterator. template std::reverse_iterator make_reverse_iterator(IteratorTy It) { return std::reverse_iterator(It); } // Returns an iterator_range over the given container which iterates in reverse. // Note that the container must have begin()/end() methods which return // bidirectional iterators for this to work. template auto reverse( ContainerTy &&C, typename std::enable_if::value>::type * = nullptr) -> decltype(make_range(llvm::make_reverse_iterator(std::end(C)), llvm::make_reverse_iterator(std::begin(C)))) { return make_range(llvm::make_reverse_iterator(std::end(C)), llvm::make_reverse_iterator(std::begin(C))); } /// An iterator adaptor that filters the elements of given inner iterators. /// /// The predicate parameter should be a callable object that accepts the wrapped /// iterator's reference type and returns a bool. When incrementing or /// decrementing the iterator, it will call the predicate on each element and /// skip any where it returns false. /// /// \code /// int A[] = { 1, 2, 3, 4 }; /// auto R = make_filter_range(A, [](int N) { return N % 2 == 1; }); /// // R contains { 1, 3 }. /// \endcode /// /// Note: filter_iterator_base implements support for forward iteration. /// filter_iterator_impl exists to provide support for bidirectional iteration, /// conditional on whether the wrapped iterator supports it. template class filter_iterator_base : public iterator_adaptor_base< filter_iterator_base, WrappedIteratorT, typename std::common_type< IterTag, typename std::iterator_traits< WrappedIteratorT>::iterator_category>::type> { using BaseT = iterator_adaptor_base< filter_iterator_base, WrappedIteratorT, typename std::common_type< IterTag, typename std::iterator_traits< WrappedIteratorT>::iterator_category>::type>; protected: WrappedIteratorT End; PredicateT Pred; void findNextValid() { while (this->I != End && !Pred(*this->I)) BaseT::operator++(); } // Construct the iterator. The begin iterator needs to know where the end // is, so that it can properly stop when it gets there. The end iterator only // needs the predicate to support bidirectional iteration. filter_iterator_base(WrappedIteratorT Begin, WrappedIteratorT End, PredicateT Pred) : BaseT(Begin), End(End), Pred(Pred) { findNextValid(); } public: using BaseT::operator++; filter_iterator_base &operator++() { BaseT::operator++(); findNextValid(); return *this; } }; /// Specialization of filter_iterator_base for forward iteration only. template class filter_iterator_impl : public filter_iterator_base { using BaseT = filter_iterator_base; public: filter_iterator_impl(WrappedIteratorT Begin, WrappedIteratorT End, PredicateT Pred) : BaseT(Begin, End, Pred) {} }; /// Specialization of filter_iterator_base for bidirectional iteration. template class filter_iterator_impl : public filter_iterator_base { using BaseT = filter_iterator_base; void findPrevValid() { while (!this->Pred(*this->I)) BaseT::operator--(); } public: using BaseT::operator--; filter_iterator_impl(WrappedIteratorT Begin, WrappedIteratorT End, PredicateT Pred) : BaseT(Begin, End, Pred) {} filter_iterator_impl &operator--() { BaseT::operator--(); findPrevValid(); return *this; } }; namespace detail { template struct fwd_or_bidi_tag_impl { using type = std::forward_iterator_tag; }; template <> struct fwd_or_bidi_tag_impl { using type = std::bidirectional_iterator_tag; }; /// Helper which sets its type member to forward_iterator_tag if the category /// of \p IterT does not derive from bidirectional_iterator_tag, and to /// bidirectional_iterator_tag otherwise. template struct fwd_or_bidi_tag { using type = typename fwd_or_bidi_tag_impl::iterator_category>::value>::type; }; } // namespace detail /// Defines filter_iterator to a suitable specialization of /// filter_iterator_impl, based on the underlying iterator's category. template using filter_iterator = filter_iterator_impl< WrappedIteratorT, PredicateT, typename detail::fwd_or_bidi_tag::type>; /// Convenience function that takes a range of elements and a predicate, /// and return a new filter_iterator range. /// /// FIXME: Currently if RangeT && is a rvalue reference to a temporary, the /// lifetime of that temporary is not kept by the returned range object, and the /// temporary is going to be dropped on the floor after the make_iterator_range /// full expression that contains this function call. template iterator_range, PredicateT>> make_filter_range(RangeT &&Range, PredicateT Pred) { using FilterIteratorT = filter_iterator, PredicateT>; return make_range( FilterIteratorT(std::begin(std::forward(Range)), std::end(std::forward(Range)), Pred), FilterIteratorT(std::end(std::forward(Range)), std::end(std::forward(Range)), Pred)); } /// A pseudo-iterator adaptor that is designed to implement "early increment" /// style loops. /// /// This is *not a normal iterator* and should almost never be used directly. It /// is intended primarily to be used with range based for loops and some range /// algorithms. /// /// The iterator isn't quite an `OutputIterator` or an `InputIterator` but /// somewhere between them. The constraints of these iterators are: /// /// - On construction or after being incremented, it is comparable and /// dereferencable. It is *not* incrementable. /// - After being dereferenced, it is neither comparable nor dereferencable, it /// is only incrementable. /// /// This means you can only dereference the iterator once, and you can only /// increment it once between dereferences. template class early_inc_iterator_impl : public iterator_adaptor_base, WrappedIteratorT, std::input_iterator_tag> { using BaseT = iterator_adaptor_base, WrappedIteratorT, std::input_iterator_tag>; using PointerT = typename std::iterator_traits::pointer; protected: #if LLVM_ENABLE_ABI_BREAKING_CHECKS bool IsEarlyIncremented = false; #endif public: early_inc_iterator_impl(WrappedIteratorT I) : BaseT(I) {} using BaseT::operator*; typename BaseT::reference operator*() { #if LLVM_ENABLE_ABI_BREAKING_CHECKS assert(!IsEarlyIncremented && "Cannot dereference twice!"); IsEarlyIncremented = true; #endif return *(this->I)++; } using BaseT::operator++; early_inc_iterator_impl &operator++() { #if LLVM_ENABLE_ABI_BREAKING_CHECKS assert(IsEarlyIncremented && "Cannot increment before dereferencing!"); IsEarlyIncremented = false; #endif return *this; } using BaseT::operator==; bool operator==(const early_inc_iterator_impl &RHS) const { #if LLVM_ENABLE_ABI_BREAKING_CHECKS assert(!IsEarlyIncremented && "Cannot compare after dereferencing!"); #endif return BaseT::operator==(RHS); } }; /// Make a range that does early increment to allow mutation of the underlying /// range without disrupting iteration. /// /// The underlying iterator will be incremented immediately after it is /// dereferenced, allowing deletion of the current node or insertion of nodes to /// not disrupt iteration provided they do not invalidate the *next* iterator -- /// the current iterator can be invalidated. /// /// This requires a very exact pattern of use that is only really suitable to /// range based for loops and other range algorithms that explicitly guarantee /// to dereference exactly once each element, and to increment exactly once each /// element. template iterator_range>> make_early_inc_range(RangeT &&Range) { using EarlyIncIteratorT = early_inc_iterator_impl>; return make_range(EarlyIncIteratorT(std::begin(std::forward(Range))), EarlyIncIteratorT(std::end(std::forward(Range)))); } // forward declarations required by zip_shortest/zip_first/zip_longest template bool all_of(R &&range, UnaryPredicate P); template bool any_of(R &&range, UnaryPredicate P); namespace detail { using std::declval; // We have to alias this since inlining the actual type at the usage site // in the parameter list of iterator_facade_base<> below ICEs MSVC 2017. template struct ZipTupleType { using type = std::tuple())...>; }; template using zip_traits = iterator_facade_base< ZipType, typename std::common_type::iterator_category...>::type, // ^ TODO: Implement random access methods. typename ZipTupleType::type, typename std::iterator_traits>::type>::difference_type, // ^ FIXME: This follows boost::make_zip_iterator's assumption that all // inner iterators have the same difference_type. It would fail if, for // instance, the second field's difference_type were non-numeric while the // first is. typename ZipTupleType::type *, typename ZipTupleType::type>; template struct zip_common : public zip_traits { using Base = zip_traits; using value_type = typename Base::value_type; std::tuple iterators; protected: template value_type deref(std::index_sequence) const { return value_type(*std::get(iterators)...); } template decltype(iterators) tup_inc(std::index_sequence) const { return std::tuple(std::next(std::get(iterators))...); } template decltype(iterators) tup_dec(std::index_sequence) const { return std::tuple(std::prev(std::get(iterators))...); } public: zip_common(Iters &&... ts) : iterators(std::forward(ts)...) {} value_type operator*() { return deref(std::index_sequence_for{}); } const value_type operator*() const { return deref(std::index_sequence_for{}); } ZipType &operator++() { iterators = tup_inc(std::index_sequence_for{}); return *reinterpret_cast(this); } ZipType &operator--() { static_assert(Base::IsBidirectional, "All inner iterators must be at least bidirectional."); iterators = tup_dec(std::index_sequence_for{}); return *reinterpret_cast(this); } }; template struct zip_first : public zip_common, Iters...> { using Base = zip_common, Iters...>; bool operator==(const zip_first &other) const { return std::get<0>(this->iterators) == std::get<0>(other.iterators); } zip_first(Iters &&... ts) : Base(std::forward(ts)...) {} }; template class zip_shortest : public zip_common, Iters...> { template bool test(const zip_shortest &other, std::index_sequence) const { return all_of(std::initializer_list{std::get(this->iterators) != std::get(other.iterators)...}, identity{}); } public: using Base = zip_common, Iters...>; zip_shortest(Iters &&... ts) : Base(std::forward(ts)...) {} bool operator==(const zip_shortest &other) const { return !test(other, std::index_sequence_for{}); } }; template