//===- 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 // //===----------------------------------------------------------------------===// /// /// \file /// 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/ADL.h" #include "llvm/ADT/Hashing.h" #include "llvm/ADT/STLForwardCompat.h" #include "llvm/ADT/STLFunctionalExtras.h" #include "llvm/ADT/iterator.h" #include "llvm/ADT/iterator_range.h" #include "llvm/Config/abi-breaking.h" #include "llvm/Support/ErrorHandling.h" #include <algorithm> #include <cassert> #include <cstddef> #include <cstdint> #include <cstdlib> #include <functional> #include <initializer_list> #include <iterator> #include <limits> #include <memory> #include <optional> #include <tuple> #include <type_traits> #include <utility> #ifdef EXPENSIVE_CHECKS #include <random> // for std::mt19937 #endif namespace llvm { //===----------------------------------------------------------------------===// // Extra additions to <type_traits> //===----------------------------------------------------------------------===// template <typename T> struct make_const_ptr { … }; template <typename T> struct make_const_ref { … }; namespace detail { template <class, template <class...> class Op, class... Args> struct detector { … }; detector<std::void_t<Op<Args...>>, Op, Args...>; } // end namespace detail /// Detects if a given trait holds for some set of arguments 'Args'. /// For example, the given trait could be used to detect if a given type /// has a copy assignment operator: /// template<class T> /// using has_copy_assign_t = decltype(std::declval<T&>() /// = std::declval<const T&>()); /// bool fooHasCopyAssign = is_detected<has_copy_assign_t, FooClass>::value; is_detected; /// This class provides various trait information about a callable object. /// * To access the number of arguments: Traits::num_args /// * To access the type of an argument: Traits::arg_t<Index> /// * To access the type of the result: Traits::result_t template <typename T, bool isClass = std::is_class<T>::value> struct function_traits : public function_traits<decltype(&T::operator())> { … }; /// Overload for class function types. function_traits<ReturnType (ClassType::*)(Args...) const, false>; /// Overload for class function types. function_traits<ReturnType (ClassType::*)(Args...), false>; /// Overload for non-class function types. function_traits<ReturnType (*)(Args...), false>; function_traits<ReturnType (*const)(Args...), false>; /// Overload for non-class function type references. function_traits<ReturnType (&)(Args...), false>; /// traits class for checking whether type T is one of any of the given /// types in the variadic list. is_one_of; /// traits class for checking whether type T is a base class for all /// the given types in the variadic list. are_base_of; namespace detail { template <typename T, typename... Us> struct TypesAreDistinct; template <typename T, typename... Us> struct TypesAreDistinct : std::integral_constant<bool, !is_one_of<T, Us...>::value && TypesAreDistinct<Us...>::value> { … }; TypesAreDistinct<T>; } // namespace detail /// Determine if all types in Ts are distinct. /// /// Useful to statically assert when Ts is intended to describe a non-multi set /// of types. /// /// Expensive (currently quadratic in sizeof(Ts...)), and so should only be /// asserted once per instantiation of a type which requires it. template <typename... Ts> struct TypesAreDistinct; template <> struct TypesAreDistinct<> : std::true_type { … }; template <typename... Ts> struct TypesAreDistinct : std::integral_constant<bool, detail::TypesAreDistinct<Ts...>::value> { … }; /// Find the first index where a type appears in a list of types. /// /// FirstIndexOfType<T, Us...>::value is the first index of T in Us. /// /// Typically only meaningful when it is otherwise statically known that the /// type pack has no duplicate types. This should be guaranteed explicitly with /// static_assert(TypesAreDistinct<Us...>::value). /// /// It is a compile-time error to instantiate when T is not present in Us, i.e. /// if is_one_of<T, Us...>::value is false. template <typename T, typename... Us> struct FirstIndexOfType; FirstIndexOfType<T, U, Us...>; FirstIndexOfType<T, T, Us...>; /// Find the type at a given index in a list of types. /// /// TypeAtIndex<I, Ts...> is the type at index I in Ts. TypeAtIndex; /// Helper which adds two underlying types of enumeration type. /// Implicit conversion to a common type is accepted. template <typename EnumTy1, typename EnumTy2, typename UT1 = std::enable_if_t<std::is_enum<EnumTy1>::value, std::underlying_type_t<EnumTy1>>, typename UT2 = std::enable_if_t<std::is_enum<EnumTy2>::value, std::underlying_type_t<EnumTy2>>> constexpr auto addEnumValues(EnumTy1 LHS, EnumTy2 RHS) { … } //===----------------------------------------------------------------------===// // Extra additions to <iterator> //===----------------------------------------------------------------------===// namespace callable_detail { /// Templated storage wrapper for a callable. /// /// This class is consistently default constructible, copy / move /// constructible / assignable. /// /// Supported callable types: /// - Function pointer /// - Function reference /// - Lambda /// - Function object template <typename T, bool = std::is_function_v<std::remove_pointer_t<remove_cvref_t<T>>>> class Callable { using value_type = std::remove_reference_t<T>; using reference = value_type &; using const_reference = value_type const &; std::optional<value_type> Obj; static_assert(!std::is_pointer_v<value_type>, "Pointers to non-functions are not callable."); public: Callable() = default; Callable(T const &O) : … { … } Callable(Callable const &Other) = default; Callable(Callable &&Other) = default; Callable &operator=(Callable const &Other) { … } Callable &operator=(Callable &&Other) { … } template <typename... Pn, std::enable_if_t<std::is_invocable_v<T, Pn...>, int> = 0> decltype(auto) operator()(Pn &&...Params) { … } template <typename... Pn, std::enable_if_t<std::is_invocable_v<T const, Pn...>, int> = 0> decltype(auto) operator()(Pn &&...Params) const { … } bool valid() const { … } bool reset() { … } operator reference() { return *Obj; } operator const_reference() const { return *Obj; } }; // Function specialization. No need to waste extra space wrapping with a // std::optional. Callable<T, true>; } // namespace callable_detail /// Returns true if the given container only contains a single element. template <typename ContainerTy> bool hasSingleElement(ContainerTy &&C) { … } /// Return a range covering \p RangeOrContainer with the first N elements /// excluded. template <typename T> auto drop_begin(T &&RangeOrContainer, size_t N = 1) { … } /// Return a range covering \p RangeOrContainer with the last N elements /// excluded. template <typename T> auto drop_end(T &&RangeOrContainer, size_t N = 1) { … } // mapped_iterator - This is a simple iterator adapter that causes a function to // be applied whenever operator* is invoked on the iterator. template <typename ItTy, typename FuncTy, typename ReferenceTy = decltype(std::declval<FuncTy>()(*std::declval<ItTy>()))> class mapped_iterator : public iterator_adaptor_base< mapped_iterator<ItTy, FuncTy>, ItTy, typename std::iterator_traits<ItTy>::iterator_category, std::remove_reference_t<ReferenceTy>, typename std::iterator_traits<ItTy>::difference_type, std::remove_reference_t<ReferenceTy> *, ReferenceTy> { … }; // map_iterator - Provide a convenient way to create mapped_iterators, just like // make_pair is useful for creating pairs... template <class ItTy, class FuncTy> inline mapped_iterator<ItTy, FuncTy> map_iterator(ItTy I, FuncTy F) { … } template <class ContainerTy, class FuncTy> auto map_range(ContainerTy &&C, FuncTy F) { … } /// A base type of mapped iterator, that is useful for building derived /// iterators that do not need/want to store the map function (as in /// mapped_iterator). These iterators must simply provide a `mapElement` method /// that defines how to map a value of the iterator to the provided reference /// type. template <typename DerivedT, typename ItTy, typename ReferenceTy> class mapped_iterator_base : public iterator_adaptor_base< DerivedT, ItTy, typename std::iterator_traits<ItTy>::iterator_category, std::remove_reference_t<ReferenceTy>, typename std::iterator_traits<ItTy>::difference_type, std::remove_reference_t<ReferenceTy> *, ReferenceTy> { … }; namespace detail { check_has_free_function_rbegin; HasFreeFunctionRBegin; } // namespace detail // Returns an iterator_range over the given container which iterates in reverse. template <typename ContainerTy> auto reverse(ContainerTy &&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 <typename WrappedIteratorT, typename PredicateT, typename IterTag> class filter_iterator_base : public iterator_adaptor_base< filter_iterator_base<WrappedIteratorT, PredicateT, IterTag>, WrappedIteratorT, std::common_type_t<IterTag, typename std::iterator_traits< WrappedIteratorT>::iterator_category>> { … }; /// Specialization of filter_iterator_base for forward iteration only. template <typename WrappedIteratorT, typename PredicateT, typename IterTag = std::forward_iterator_tag> class filter_iterator_impl : public filter_iterator_base<WrappedIteratorT, PredicateT, IterTag> { … }; /// Specialization of filter_iterator_base for bidirectional iteration. filter_iterator_impl<WrappedIteratorT, PredicateT, std::bidirectional_iterator_tag>; namespace detail { template <bool is_bidirectional> struct fwd_or_bidi_tag_impl { … }; template <> struct fwd_or_bidi_tag_impl<true> { … }; /// 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 <typename IterT> struct fwd_or_bidi_tag { … }; } // namespace detail /// Defines filter_iterator to a suitable specialization of /// filter_iterator_impl, based on the underlying iterator's category. filter_iterator; /// 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 <typename RangeT, typename PredicateT> iterator_range<filter_iterator<detail::IterOfRange<RangeT>, PredicateT>> make_filter_range(RangeT &&Range, PredicateT 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 <typename WrappedIteratorT> class early_inc_iterator_impl : public iterator_adaptor_base<early_inc_iterator_impl<WrappedIteratorT>, WrappedIteratorT, std::input_iterator_tag> { … }; /// 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 <typename RangeT> iterator_range<early_inc_iterator_impl<detail::IterOfRange<RangeT>>> make_early_inc_range(RangeT &&Range) { … } // Forward declarations required by zip_shortest/zip_equal/zip_first/zip_longest template <typename R, typename UnaryPredicate> bool all_of(R &&range, UnaryPredicate P); template <typename R, typename UnaryPredicate> bool any_of(R &&range, UnaryPredicate P); template <typename T> bool all_equal(std::initializer_list<T> Values); template <typename R> constexpr size_t range_size(R &&Range); namespace detail { 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<typename... Iters> struct ZipTupleType { … }; zip_traits; template <typename ZipType, typename ReferenceTupleType, typename... Iters> struct zip_common : public zip_traits<ZipType, ReferenceTupleType, Iters...> { … }; template <typename... Iters> struct zip_first : zip_common<zip_first<Iters...>, typename ZipTupleType<Iters...>::type, Iters...> { … }; template <typename... Iters> struct zip_shortest : zip_common<zip_shortest<Iters...>, typename ZipTupleType<Iters...>::type, Iters...> { … }; /// Helper to obtain the iterator types for the tuple storage within `zippy`. template <template <typename...> class ItType, typename TupleStorageType, typename IndexSequence> struct ZippyIteratorTuple; /// Partial specialization for non-const tuple storage. ZippyIteratorTuple<ItType, std::tuple<Args...>, std::index_sequence<Ns...>>; /// Partial specialization for const tuple storage. ZippyIteratorTuple<ItType, const std::tuple<Args...>, std::index_sequence<Ns...>>; template <template <typename...> class ItType, typename... Args> class zippy { … }; } // end namespace detail /// zip iterator for two or more iteratable types. Iteration continues until the /// end of the *shortest* iteratee is reached. template <typename T, typename U, typename... Args> detail::zippy<detail::zip_shortest, T, U, Args...> zip(T &&t, U &&u, Args &&...args) { … } /// zip iterator that assumes that all iteratees have the same length. /// In builds with assertions on, this assumption is checked before the /// iteration starts. template <typename T, typename U, typename... Args> detail::zippy<detail::zip_first, T, U, Args...> zip_equal(T &&t, U &&u, Args &&...args) { … } /// zip iterator that, for the sake of efficiency, assumes the first iteratee to /// be the shortest. Iteration continues until the end of the first iteratee is /// reached. In builds with assertions on, we check that the assumption about /// the first iteratee being the shortest holds. template <typename T, typename U, typename... Args> detail::zippy<detail::zip_first, T, U, Args...> zip_first(T &&t, U &&u, Args &&...args) { … } namespace detail { template <typename Iter> Iter next_or_end(const Iter &I, const Iter &End) { … } template <typename Iter> auto deref_or_none(const Iter &I, const Iter &End) -> std::optional< std::remove_const_t<std::remove_reference_t<decltype(*I)>>> { … } template <typename Iter> struct ZipLongestItemType { … }; template <typename... Iters> struct ZipLongestTupleType { … }; template <typename... Iters> class zip_longest_iterator : public iterator_facade_base< zip_longest_iterator<Iters...>, std::common_type_t< std::forward_iterator_tag, typename std::iterator_traits<Iters>::iterator_category...>, typename ZipLongestTupleType<Iters...>::type, typename std::iterator_traits< std::tuple_element_t<0, std::tuple<Iters...>>>::difference_type, typename ZipLongestTupleType<Iters...>::type *, typename ZipLongestTupleType<Iters...>::type> { … }; template <typename... Args> class zip_longest_range { … }; } // namespace detail /// Iterate over two or more iterators at the same time. Iteration continues /// until all iterators reach the end. The std::optional only contains a value /// if the iterator has not reached the end. template <typename T, typename U, typename... Args> detail::zip_longest_range<T, U, Args...> zip_longest(T &&t, U &&u, Args &&... args) { … } /// Iterator wrapper that concatenates sequences together. /// /// This can concatenate different iterators, even with different types, into /// a single iterator provided the value types of all the concatenated /// iterators expose `reference` and `pointer` types that can be converted to /// `ValueT &` and `ValueT *` respectively. It doesn't support more /// interesting/customized pointer or reference types. /// /// Currently this only supports forward or higher iterator categories as /// inputs and always exposes a forward iterator interface. template <typename ValueT, typename... IterTs> class concat_iterator : public iterator_facade_base<concat_iterator<ValueT, IterTs...>, std::forward_iterator_tag, ValueT> { … }; namespace detail { /// Helper to store a sequence of ranges being concatenated and access them. /// /// This is designed to facilitate providing actual storage when temporaries /// are passed into the constructor such that we can use it as part of range /// based for loops. template <typename ValueT, typename... RangeTs> class concat_range { … }; } // end namespace detail /// Concatenated range across two or more ranges. /// /// The desired value type must be explicitly specified. template <typename ValueT, typename... RangeTs> detail::concat_range<ValueT, RangeTs...> concat(RangeTs &&... Ranges) { … } /// A utility class used to implement an iterator that contains some base object /// and an index. The iterator moves the index but keeps the base constant. template <typename DerivedT, typename BaseT, typename T, typename PointerT = T *, typename ReferenceT = T &> class indexed_accessor_iterator : public llvm::iterator_facade_base<DerivedT, std::random_access_iterator_tag, T, std::ptrdiff_t, PointerT, ReferenceT> { … }; namespace detail { /// The class represents the base of a range of indexed_accessor_iterators. It /// provides support for many different range functionalities, e.g. /// drop_front/slice/etc.. Derived range classes must implement the following /// static methods: /// * ReferenceT dereference_iterator(const BaseT &base, ptrdiff_t index) /// - Dereference an iterator pointing to the base object at the given /// index. /// * BaseT offset_base(const BaseT &base, ptrdiff_t index) /// - Return a new base that is offset from the provide base by 'index' /// elements. template <typename DerivedT, typename BaseT, typename T, typename PointerT = T *, typename ReferenceT = T &> class indexed_accessor_range_base { … }; /// Compare this range with another. /// FIXME: Make me a member function instead of friend when it works in C++20. template <typename OtherT, typename DerivedT, typename BaseT, typename T, typename PointerT, typename ReferenceT> bool operator==(const indexed_accessor_range_base<DerivedT, BaseT, T, PointerT, ReferenceT> &lhs, const OtherT &rhs) { … } template <typename OtherT, typename DerivedT, typename BaseT, typename T, typename PointerT, typename ReferenceT> bool operator!=(const indexed_accessor_range_base<DerivedT, BaseT, T, PointerT, ReferenceT> &lhs, const OtherT &rhs) { … } } // end namespace detail /// This class provides an implementation of a range of /// indexed_accessor_iterators where the base is not indexable. Ranges with /// bases that are offsetable should derive from indexed_accessor_range_base /// instead. Derived range classes are expected to implement the following /// static method: /// * ReferenceT dereference(const BaseT &base, ptrdiff_t index) /// - Dereference an iterator pointing to a parent base at the given index. template <typename DerivedT, typename BaseT, typename T, typename PointerT = T *, typename ReferenceT = T &> class indexed_accessor_range : public detail::indexed_accessor_range_base< DerivedT, std::pair<BaseT, ptrdiff_t>, T, PointerT, ReferenceT> { … }; namespace detail { /// Return a reference to the first or second member of a reference. Otherwise, /// return a copy of the member of a temporary. /// /// When passing a range whose iterators return values instead of references, /// the reference must be dropped from `decltype((elt.first))`, which will /// always be a reference, to avoid returning a reference to a temporary. template <typename EltTy, typename FirstTy> class first_or_second_type { … }; } // end namespace detail /// Given a container of pairs, return a range over the first elements. template <typename ContainerTy> auto make_first_range(ContainerTy &&c) { … } /// Given a container of pairs, return a range over the second elements. template <typename ContainerTy> auto make_second_range(ContainerTy &&c) { … } //===----------------------------------------------------------------------===// // Extra additions to <utility> //===----------------------------------------------------------------------===// /// Function object to check whether the first component of a container /// supported by std::get (like std::pair and std::tuple) compares less than the /// first component of another container. struct less_first { … }; /// Function object to check whether the second component of a container /// supported by std::get (like std::pair and std::tuple) compares less than the /// second component of another container. struct less_second { … }; /// \brief Function object to apply a binary function to the first component of /// a std::pair. template<typename FuncTy> struct on_first { … }; /// Utility type to build an inheritance chain that makes it easy to rank /// overload candidates. template <int N> struct rank : rank<N - 1> { … }; template <> struct rank<0> { … }; namespace detail { template <typename... Ts> struct Visitor; Visitor<HeadT, TailTs...>; Visitor<HeadT>; } // namespace detail /// Returns an opaquely-typed Callable object whose operator() overload set is /// the sum of the operator() overload sets of each CallableT in CallableTs. /// /// The type of the returned object derives from each CallableT in CallableTs. /// The returned object is constructed by invoking the appropriate copy or move /// constructor of each CallableT, as selected by overload resolution on the /// corresponding argument to makeVisitor. /// /// Example: /// /// \code /// auto visitor = makeVisitor([](auto) { return "unhandled type"; }, /// [](int i) { return "int"; }, /// [](std::string s) { return "str"; }); /// auto a = visitor(42); // `a` is now "int". /// auto b = visitor("foo"); // `b` is now "str". /// auto c = visitor(3.14f); // `c` is now "unhandled type". /// \endcode /// /// Example of making a visitor with a lambda which captures a move-only type: /// /// \code /// std::unique_ptr<FooHandler> FH = /* ... */; /// auto visitor = makeVisitor( /// [FH{std::move(FH)}](Foo F) { return FH->handle(F); }, /// [](int i) { return i; }, /// [](std::string s) { return atoi(s); }); /// \endcode template <typename... CallableTs> constexpr decltype(auto) makeVisitor(CallableTs &&...Callables) { … } //===----------------------------------------------------------------------===// // Extra additions to <algorithm> //===----------------------------------------------------------------------===// // We have a copy here so that LLVM behaves the same when using different // standard libraries. template <class Iterator, class RNG> void shuffle(Iterator first, Iterator last, RNG &&g) { … } /// Adapt std::less<T> for array_pod_sort. template<typename T> inline int array_pod_sort_comparator(const void *P1, const void *P2) { … } /// get_array_pod_sort_comparator - This is an internal helper function used to /// get type deduction of T right. template<typename T> inline int (*get_array_pod_sort_comparator(const T &)) (const void*, const void*) { … } #ifdef EXPENSIVE_CHECKS namespace detail { inline unsigned presortShuffleEntropy() { static unsigned Result(std::random_device{}()); return Result; } template <class IteratorTy> inline void presortShuffle(IteratorTy Start, IteratorTy End) { std::mt19937 Generator(presortShuffleEntropy()); llvm::shuffle(Start, End, Generator); } } // end namespace detail #endif /// array_pod_sort - This sorts an array with the specified start and end /// extent. This is just like std::sort, except that it calls qsort instead of /// using an inlined template. qsort is slightly slower than std::sort, but /// most sorts are not performance critical in LLVM and std::sort has to be /// template instantiated for each type, leading to significant measured code /// bloat. This function should generally be used instead of std::sort where /// possible. /// /// This function assumes that you have simple POD-like types that can be /// compared with std::less and can be moved with memcpy. If this isn't true, /// you should use std::sort. /// /// NOTE: If qsort_r were portable, we could allow a custom comparator and /// default to std::less. template<class IteratorTy> inline void array_pod_sort(IteratorTy Start, IteratorTy End) { … } template <class IteratorTy> inline void array_pod_sort( IteratorTy Start, IteratorTy End, int (*Compare)( const typename std::iterator_traits<IteratorTy>::value_type *, const typename std::iterator_traits<IteratorTy>::value_type *)) { … } namespace detail { sort_trivially_copyable; } // namespace detail // Provide wrappers to std::sort which shuffle the elements before sorting // to help uncover non-deterministic behavior (PR35135). template <typename IteratorTy> inline void sort(IteratorTy Start, IteratorTy End) { … } template <typename Container> inline void sort(Container &&C) { … } template <typename IteratorTy, typename Compare> inline void sort(IteratorTy Start, IteratorTy End, Compare Comp) { … } template <typename Container, typename Compare> inline void sort(Container &&C, Compare Comp) { … } /// Get the size of a range. This is a wrapper function around std::distance /// which is only enabled when the operation is O(1). template <typename R> auto size(R &&Range, std::enable_if_t< std::is_base_of<std::random_access_iterator_tag, typename std::iterator_traits<decltype( Range.begin())>::iterator_category>::value, void> * = nullptr) { … } namespace detail { check_has_free_function_size; HasFreeFunctionSize; } // namespace detail /// Returns the size of the \p Range, i.e., the number of elements. This /// implementation takes inspiration from `std::ranges::size` from C++20 and /// delegates the size check to `adl_size` or `std::distance`, in this order of /// preference. Unlike `llvm::size`, this function does *not* guarantee O(1) /// running time, and is intended to be used in generic code that does not know /// the exact range type. template <typename R> constexpr size_t range_size(R &&Range) { … } /// Provide wrappers to std::for_each which take ranges instead of having to /// pass begin/end explicitly. template <typename R, typename UnaryFunction> UnaryFunction for_each(R &&Range, UnaryFunction F) { … } /// Provide wrappers to std::all_of which take ranges instead of having to pass /// begin/end explicitly. template <typename R, typename UnaryPredicate> bool all_of(R &&Range, UnaryPredicate P) { … } /// Provide wrappers to std::any_of which take ranges instead of having to pass /// begin/end explicitly. template <typename R, typename UnaryPredicate> bool any_of(R &&Range, UnaryPredicate P) { … } /// Provide wrappers to std::none_of which take ranges instead of having to pass /// begin/end explicitly. template <typename R, typename UnaryPredicate> bool none_of(R &&Range, UnaryPredicate P) { … } /// Provide wrappers to std::find which take ranges instead of having to pass /// begin/end explicitly. template <typename R, typename T> auto find(R &&Range, const T &Val) { … } /// Provide wrappers to std::find_if which take ranges instead of having to pass /// begin/end explicitly. template <typename R, typename UnaryPredicate> auto find_if(R &&Range, UnaryPredicate P) { … } template <typename R, typename UnaryPredicate> auto find_if_not(R &&Range, UnaryPredicate P) { … } /// Provide wrappers to std::remove_if which take ranges instead of having to /// pass begin/end explicitly. template <typename R, typename UnaryPredicate> auto remove_if(R &&Range, UnaryPredicate P) { … } /// Provide wrappers to std::copy_if which take ranges instead of having to /// pass begin/end explicitly. template <typename R, typename OutputIt, typename UnaryPredicate> OutputIt copy_if(R &&Range, OutputIt Out, UnaryPredicate P) { … } /// Return the single value in \p Range that satisfies /// \p P(<member of \p Range> *, AllowRepeats)->T * returning nullptr /// when no values or multiple values were found. /// When \p AllowRepeats is true, multiple values that compare equal /// are allowed. template <typename T, typename R, typename Predicate> T *find_singleton(R &&Range, Predicate P, bool AllowRepeats = false) { … } /// Return a pair consisting of the single value in \p Range that satisfies /// \p P(<member of \p Range> *, AllowRepeats)->std::pair<T*, bool> returning /// nullptr when no values or multiple values were found, and a bool indicating /// whether multiple values were found to cause the nullptr. /// When \p AllowRepeats is true, multiple values that compare equal are /// allowed. The predicate \p P returns a pair<T *, bool> where T is the /// singleton while the bool indicates whether multiples have already been /// found. It is expected that first will be nullptr when second is true. /// This allows using find_singleton_nested within the predicate \P. template <typename T, typename R, typename Predicate> std::pair<T *, bool> find_singleton_nested(R &&Range, Predicate P, bool AllowRepeats = false) { … } template <typename R, typename OutputIt> OutputIt copy(R &&Range, OutputIt Out) { … } /// Provide wrappers to std::replace_copy_if which take ranges instead of having /// to pass begin/end explicitly. template <typename R, typename OutputIt, typename UnaryPredicate, typename T> OutputIt replace_copy_if(R &&Range, OutputIt Out, UnaryPredicate P, const T &NewValue) { … } /// Provide wrappers to std::replace_copy which take ranges instead of having to /// pass begin/end explicitly. template <typename R, typename OutputIt, typename T> OutputIt replace_copy(R &&Range, OutputIt Out, const T &OldValue, const T &NewValue) { … } /// Provide wrappers to std::replace which take ranges instead of having to pass /// begin/end explicitly. template <typename R, typename T> void replace(R &&Range, const T &OldValue, const T &NewValue) { … } /// Provide wrappers to std::move which take ranges instead of having to /// pass begin/end explicitly. template <typename R, typename OutputIt> OutputIt move(R &&Range, OutputIt Out) { … } namespace detail { check_has_member_contains_t; HasMemberContains; check_has_member_find_t; HasMemberFind; } // namespace detail /// Returns true if \p Element is found in \p Range. Delegates the check to /// either `.contains(Element)`, `.find(Element)`, or `std::find`, in this /// order of preference. This is intended as the canonical way to check if an /// element exists in a range in generic code or range type that does not /// expose a `.contains(Element)` member. template <typename R, typename E> bool is_contained(R &&Range, const E &Element) { … } /// Returns true iff \p Element exists in \p Set. This overload takes \p Set as /// an initializer list and is `constexpr`-friendly. template <typename T, typename E> constexpr bool is_contained(std::initializer_list<T> Set, const E &Element) { … } /// Wrapper function around std::is_sorted to check if elements in a range \p R /// are sorted with respect to a comparator \p C. template <typename R, typename Compare> bool is_sorted(R &&Range, Compare C) { … } /// Wrapper function around std::is_sorted to check if elements in a range \p R /// are sorted in non-descending order. template <typename R> bool is_sorted(R &&Range) { … } /// Wrapper function around std::count to count the number of times an element /// \p Element occurs in the given range \p Range. template <typename R, typename E> auto count(R &&Range, const E &Element) { … } /// Wrapper function around std::count_if to count the number of times an /// element satisfying a given predicate occurs in a range. template <typename R, typename UnaryPredicate> auto count_if(R &&Range, UnaryPredicate P) { … } /// Wrapper function around std::transform to apply a function to a range and /// store the result elsewhere. template <typename R, typename OutputIt, typename UnaryFunction> OutputIt transform(R &&Range, OutputIt d_first, UnaryFunction F) { … } /// Provide wrappers to std::partition which take ranges instead of having to /// pass begin/end explicitly. template <typename R, typename UnaryPredicate> auto partition(R &&Range, UnaryPredicate P) { … } /// Provide wrappers to std::binary_search which take ranges instead of having /// to pass begin/end explicitly. template <typename R, typename T> auto binary_search(R &&Range, T &&Value) { … } template <typename R, typename T, typename Compare> auto binary_search(R &&Range, T &&Value, Compare C) { … } /// Provide wrappers to std::lower_bound which take ranges instead of having to /// pass begin/end explicitly. template <typename R, typename T> auto lower_bound(R &&Range, T &&Value) { … } template <typename R, typename T, typename Compare> auto lower_bound(R &&Range, T &&Value, Compare C) { … } /// Provide wrappers to std::upper_bound which take ranges instead of having to /// pass begin/end explicitly. template <typename R, typename T> auto upper_bound(R &&Range, T &&Value) { … } template <typename R, typename T, typename Compare> auto upper_bound(R &&Range, T &&Value, Compare C) { … } /// Provide wrappers to std::min_element which take ranges instead of having to /// pass begin/end explicitly. template <typename R> auto min_element(R &&Range) { … } template <typename R, typename Compare> auto min_element(R &&Range, Compare C) { … } /// Provide wrappers to std::max_element which take ranges instead of having to /// pass begin/end explicitly. template <typename R> auto max_element(R &&Range) { … } template <typename R, typename Compare> auto max_element(R &&Range, Compare C) { … } /// Provide wrappers to std::mismatch which take ranges instead of having to /// pass begin/end explicitly. /// This function returns a pair of iterators for the first mismatching elements /// from `R1` and `R2`. As an example, if: /// /// R1 = [0, 1, 4, 6], R2 = [0, 1, 5, 6] /// /// this function will return a pair of iterators, first pointing to R1[2] and /// second pointing to R2[2]. template <typename R1, typename R2> auto mismatch(R1 &&Range1, R2 &&Range2) { … } template <typename R> void stable_sort(R &&Range) { … } template <typename R, typename Compare> void stable_sort(R &&Range, Compare C) { … } /// Binary search for the first iterator in a range where a predicate is false. /// Requires that C is always true below some limit, and always false above it. template <typename R, typename Predicate, typename Val = decltype(*adl_begin(std::declval<R>()))> auto partition_point(R &&Range, Predicate P) { … } template<typename Range, typename Predicate> auto unique(Range &&R, Predicate P) { … } /// Wrapper function around std::unique to allow calling unique on a /// container without having to specify the begin/end iterators. template <typename Range> auto unique(Range &&R) { … } /// Wrapper function around std::equal to detect if pair-wise elements between /// two ranges are the same. template <typename L, typename R> bool equal(L &&LRange, R &&RRange) { … } template <typename L, typename R, typename BinaryPredicate> bool equal(L &&LRange, R &&RRange, BinaryPredicate P) { … } /// Returns true if all elements in Range are equal or when the Range is empty. template <typename R> bool all_equal(R &&Range) { … } /// Returns true if all Values in the initializer lists are equal or the list // is empty. template <typename T> bool all_equal(std::initializer_list<T> Values) { … } /// Provide a container algorithm similar to C++ Library Fundamentals v2's /// `erase_if` which is equivalent to: /// /// C.erase(remove_if(C, pred), C.end()); /// /// This version works for any container with an erase method call accepting /// two iterators. template <typename Container, typename UnaryPredicate> void erase_if(Container &C, UnaryPredicate P) { … } /// Wrapper function to remove a value from a container: /// /// C.erase(remove(C.begin(), C.end(), V), C.end()); template <typename Container, typename ValueType> void erase(Container &C, ValueType V) { … } /// Wrapper function to append range `R` to container `C`. /// /// C.insert(C.end(), R.begin(), R.end()); template <typename Container, typename Range> void append_range(Container &C, Range &&R) { … } /// Appends all `Values` to container `C`. template <typename Container, typename... Args> void append_values(Container &C, Args &&...Values) { … } /// Given a sequence container Cont, replace the range [ContIt, ContEnd) with /// the range [ValIt, ValEnd) (which is not from the same container). template<typename Container, typename RandomAccessIterator> void replace(Container &Cont, typename Container::iterator ContIt, typename Container::iterator ContEnd, RandomAccessIterator ValIt, RandomAccessIterator ValEnd) { … } /// Given a sequence container Cont, replace the range [ContIt, ContEnd) with /// the range R. template<typename Container, typename Range = std::initializer_list< typename Container::value_type>> void replace(Container &Cont, typename Container::iterator ContIt, typename Container::iterator ContEnd, Range R) { … } /// An STL-style algorithm similar to std::for_each that applies a second /// functor between every pair of elements. /// /// This provides the control flow logic to, for example, print a /// comma-separated list: /// \code /// interleave(names.begin(), names.end(), /// [&](StringRef name) { os << name; }, /// [&] { os << ", "; }); /// \endcode template <typename ForwardIterator, typename UnaryFunctor, typename NullaryFunctor, typename = std::enable_if_t< !std::is_constructible<StringRef, UnaryFunctor>::value && !std::is_constructible<StringRef, NullaryFunctor>::value>> inline void interleave(ForwardIterator begin, ForwardIterator end, UnaryFunctor each_fn, NullaryFunctor between_fn) { … } template <typename Container, typename UnaryFunctor, typename NullaryFunctor, typename = std::enable_if_t< !std::is_constructible<StringRef, UnaryFunctor>::value && !std::is_constructible<StringRef, NullaryFunctor>::value>> inline void interleave(const Container &c, UnaryFunctor each_fn, NullaryFunctor between_fn) { … } /// Overload of interleave for the common case of string separator. template <typename Container, typename UnaryFunctor, typename StreamT, typename T = detail::ValueOfRange<Container>> inline void interleave(const Container &c, StreamT &os, UnaryFunctor each_fn, const StringRef &separator) { … } template <typename Container, typename StreamT, typename T = detail::ValueOfRange<Container>> inline void interleave(const Container &c, StreamT &os, const StringRef &separator) { … } template <typename Container, typename UnaryFunctor, typename StreamT, typename T = detail::ValueOfRange<Container>> inline void interleaveComma(const Container &c, StreamT &os, UnaryFunctor each_fn) { … } template <typename Container, typename StreamT, typename T = detail::ValueOfRange<Container>> inline void interleaveComma(const Container &c, StreamT &os) { … } //===----------------------------------------------------------------------===// // Extra additions to <memory> //===----------------------------------------------------------------------===// struct FreeDeleter { … }; template<typename First, typename Second> struct pair_hash { … }; /// Binary functor that adapts to any other binary functor after dereferencing /// operands. template <typename T> struct deref { … }; namespace detail { /// Tuple-like type for `zip_enumerator` dereference. template <typename... Refs> struct enumerator_result; EnumeratorTupleType; /// Zippy iterator that uses the second iterator for comparisons. For the /// increment to be safe, the second range has to be the shortest. /// Returns `enumerator_result` on dereference to provide `.index()` and /// `.value()` member functions. /// Note: Because the dereference operator returns `enumerator_result` as a /// value instead of a reference and does not strictly conform to the C++17's /// definition of forward iterator. However, it satisfies all the /// forward_iterator requirements that the `zip_common` and `zippy` depend on /// and fully conforms to the C++20 definition of forward iterator. /// This is similar to `std::vector<bool>::iterator` that returns bit reference /// wrappers on dereference. template <typename... Iters> struct zip_enumerator : zip_common<zip_enumerator<Iters...>, EnumeratorTupleType<Iters...>, Iters...> { … }; enumerator_result<std::size_t, Refs...>; struct index_iterator : llvm::iterator_facade_base<index_iterator, std::random_access_iterator_tag, std::size_t> { … }; /// Infinite stream of increasing 0-based `size_t` indices. struct index_stream { … }; } // end namespace detail /// Increasing range of `size_t` indices. class index_range { … }; /// Given two or more input ranges, returns a new range whose values are /// tuples (A, B, C, ...), such that A is the 0-based index of the item in the /// sequence, and B, C, ..., are the values from the original input ranges. All /// input ranges are required to have equal lengths. Note that the returned /// iterator allows for the values (B, C, ...) to be modified. Example: /// /// ```c++ /// std::vector<char> Letters = {'A', 'B', 'C', 'D'}; /// std::vector<int> Vals = {10, 11, 12, 13}; /// /// for (auto [Index, Letter, Value] : enumerate(Letters, Vals)) { /// printf("Item %zu - %c: %d\n", Index, Letter, Value); /// Value -= 10; /// } /// ``` /// /// Output: /// Item 0 - A: 10 /// Item 1 - B: 11 /// Item 2 - C: 12 /// Item 3 - D: 13 /// /// or using an iterator: /// ```c++ /// for (auto it : enumerate(Vals)) { /// it.value() += 10; /// printf("Item %zu: %d\n", it.index(), it.value()); /// } /// ``` /// /// Output: /// Item 0: 20 /// Item 1: 21 /// Item 2: 22 /// Item 3: 23 /// template <typename FirstRange, typename... RestRanges> auto enumerate(FirstRange &&First, RestRanges &&...Rest) { … } namespace detail { template <typename Predicate, typename... Args> bool all_of_zip_predicate_first(Predicate &&P, Args &&...args) { … } // Just an adaptor to switch the order of argument and have the predicate before // the zipped inputs. template <typename... ArgsThenPredicate, size_t... InputIndexes> bool all_of_zip_predicate_last( std::tuple<ArgsThenPredicate...> argsThenPredicate, std::index_sequence<InputIndexes...>) { … } } // end namespace detail /// Compare two zipped ranges using the provided predicate (as last argument). /// Return true if all elements satisfy the predicate and false otherwise. // Return false if the zipped iterator aren't all at end (size mismatch). template <typename... ArgsAndPredicate> bool all_of_zip(ArgsAndPredicate &&...argsAndPredicate) { … } /// Return true if the sequence [Begin, End) has exactly N items. Runs in O(N) /// time. Not meant for use with random-access iterators. /// Can optionally take a predicate to filter lazily some items. template <typename IterTy, typename Pred = bool (*)(const decltype(*std::declval<IterTy>()) &)> bool hasNItems( IterTy &&Begin, IterTy &&End, unsigned N, Pred &&ShouldBeCounted = [](const decltype(*std::declval<IterTy>()) &) { … } /// Return true if the sequence [Begin, End) has N or more items. Runs in O(N) /// time. Not meant for use with random-access iterators. /// Can optionally take a predicate to lazily filter some items. template <typename IterTy, typename Pred = bool (*)(const decltype(*std::declval<IterTy>()) &)> bool hasNItemsOrMore( IterTy &&Begin, IterTy &&End, unsigned N, Pred &&ShouldBeCounted = [](const decltype(*std::declval<IterTy>()) &) { … } /// Returns true if the sequence [Begin, End) has N or less items. Can /// optionally take a predicate to lazily filter some items. template <typename IterTy, typename Pred = bool (*)(const decltype(*std::declval<IterTy>()) &)> bool hasNItemsOrLess( IterTy &&Begin, IterTy &&End, unsigned N, Pred &&ShouldBeCounted = [](const decltype(*std::declval<IterTy>()) &) { … } /// Returns true if the given container has exactly N items template <typename ContainerTy> bool hasNItems(ContainerTy &&C, unsigned N) { … } /// Returns true if the given container has N or more items template <typename ContainerTy> bool hasNItemsOrMore(ContainerTy &&C, unsigned N) { … } /// Returns true if the given container has N or less items template <typename ContainerTy> bool hasNItemsOrLess(ContainerTy &&C, unsigned N) { … } /// Returns a raw pointer that represents the same address as the argument. /// /// This implementation can be removed once we move to C++20 where it's defined /// as std::to_address(). /// /// The std::pointer_traits<>::to_address(p) variations of these overloads has /// not been implemented. template <class Ptr> auto to_address(const Ptr &P) { … } template <class T> constexpr T *to_address(T *P) { … } // Detect incomplete types, relying on the fact that their size is unknown. namespace detail { has_sizeof; } // namespace detail /// Detects when type `T` is incomplete. This is true for forward declarations /// and false for types with a full definition. is_incomplete_v; } // end namespace llvm namespace std { tuple_size<llvm::detail::enumerator_result<Refs...>>; tuple_element<I, llvm::detail::enumerator_result<Refs...>>; tuple_element<I, const llvm::detail::enumerator_result<Refs...>>; } // namespace std #endif // LLVM_ADT_STLEXTRAS_H
Codebase Browser
llvm