diff --git a/llvm/include/llvm/ADT/Callable.h b/llvm/include/llvm/ADT/Callable.h new file mode 100644 --- /dev/null +++ b/llvm/include/llvm/ADT/Callable.h @@ -0,0 +1,143 @@ +//===-- Callable.h - Templated callable storage object. ---------*- 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 Callable.h +/// Templated callable storage object. +/// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_ADT_CALLABLE_H +#define LLVM_ADT_CALLABLE_H + +#include "llvm/ADT/STLForwardCompat.h" + +#include +#include + +namespace llvm { +namespace callable_impl { + +// clang-format off +template < + typename T, + bool = std::is_function_v>> +> // clang-format on +class Callable { + using value_type = std::remove_reference_t; + using reference = value_type &; + using const_reference = value_type const &; + + std::optional Obj; + + static_assert(!std::is_pointer_v, + "Pointers to non-functions are not callable."); + +public: + Callable() = default; + Callable(T const &O) : Obj(std::in_place, O) {} + + Callable(Callable const &Other) = default; + Callable(Callable &&Other) = default; + + Callable &operator=(Callable const &Other) { + Obj = std::nullopt; + if (Other.Obj) + Obj.emplace(*Other.Obj); + return *this; + } + + Callable &operator=(Callable &&Other) { + Obj = std::nullopt; + if (Other.Obj) + Obj.emplace(std::move(*Other.Obj)); + return *this; + } + + template , int> = 0> + decltype(auto) operator()(Pn &&...Params) { + return (*Obj)(std::forward(Params)...); + } + + template , int> = 0> + decltype(auto) operator()(Pn &&...Params) const { + return (*Obj)(std::forward(Params)...); + } + + bool valid() const { return Obj != std::nullopt; } + bool reset() { return Obj = std::nullopt; } + + operator reference() { return *Obj; } + operator const_reference() const { return *Obj; } +}; + +// Function specialization. No need to waste extra space wrapping with a +// std::optional. +template class Callable { + static constexpr bool IsPtr = std::is_pointer_v>; + + using StorageT = std::conditional_t *>; + using CastT = std::conditional_t; + +private: + StorageT Func = nullptr; + +private: + template static constexpr auto convertIn(In &&I) { + if constexpr (IsPtr) { + // Pointer... just echo it back. + return I; + } else { + // Must be a function reference. Return its address. + return &I; + } + } + +public: + // Construct from a function pointer or reference. + // + // Disable this constructor for references to 'Callable' so we don't violate + // the rule of 0. + template < // clang-format off + typename FnPtrOrRef, + std::enable_if_t< + !std::is_same_v, Callable>, int + > = 0 + > // clang-format on + Callable(FnPtrOrRef &&F) : Func(convertIn(F)) {} + + template , int> = 0> + decltype(auto) operator()(Pn &&...Params) const { + return Func(std::forward(Params)...); + } + + bool valid() const { return Func != nullptr; } + void reset() { Func = nullptr; } + + operator CastT() const { + if constexpr (IsPtr) { + // T is a pointer... just echo it back. + return Func; + } else { + static_assert(std::is_reference_v, + "Expected a reference to a function."); + // T is a function reference... dereference the stored pointer. + return *Func; + } + } +}; + +} // namespace callable_impl + +template using Callable = callable_impl::Callable; + +} // namespace llvm + +#endif // LLVM_ADT_CALLABLE_H diff --git a/llvm/include/llvm/ADT/Closure.h b/llvm/include/llvm/ADT/Closure.h new file mode 100644 --- /dev/null +++ b/llvm/include/llvm/ADT/Closure.h @@ -0,0 +1,269 @@ +//===-- Closure.h - Closure infrstructure. ----------------------*- 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 Closure.h +/// Closure infrastructure. +/// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_ADT_CLOSURE_H +#define LLVM_ADT_CLOSURE_H + +#include "llvm/ADT/Callable.h" +#include "llvm/ADT/RangesConcepts.h" +#include "llvm/ADT/STLForwardCompat.h" + +#include +#include +#include + +namespace llvm { +namespace closure_impl { + +// +// Specialize to 'true' for both closure classes. Used by SFINAE. +// +template struct IsClosureImpl : std::false_type {}; + +template using IsClosure = IsClosureImpl>; + +// +// ClosureCollector - storage for a group of closure objects. The Collector can +// be applied to an iterable range in a single shot. +// +// NOTE: closure objects are stored in reverse order (last to be applied is the +// first element in the collector. This simplifies adding a new closure to an +// existing collector. +// +template struct ClosureCollector {}; + +template +using MakeCollector = ClosureCollector...>; + +template struct GrowCollectorImpl {}; + +template +struct GrowCollectorImpl> { + using type = ClosureCollector; +}; + +// Create a new collector type with additional storage at the front for `T`. +template +using GrowCollector = + typename GrowCollectorImpl, Collector>::type; + +template +struct ClosureCollector : ClosureCollector { + C0 Front; + + // + // This constructor is only used to form the collector for the first two + // closures. + // + template + ClosureCollector(C0 const &F, Tn &&...Others) + : ClosureCollector(std::forward(Others)...), Front(F) {} + + template + ClosureCollector(C0 &&F, Tn &&...Others) + : ClosureCollector(std::forward(Others)...), + Front(std::move(F)) {} + + // + // Only valid to build up form r-value collectors. + // + ClosureCollector(C0 const &F, ClosureCollector &&Others) + : ClosureCollector(std::move(Others)), Front(F) {} + + ClosureCollector(C0 &&F, ClosureCollector &&Others) + : ClosureCollector(std::move(Others)), Front(std::move(F)) {} + + template ::value, int> = 0> + friend auto operator|(IterableT &&Iterable, + ClosureCollector const &Collector) { + // Apply closures to `Iterable` in reverse order. + return std::forward(Iterable) | + static_cast const &>(Collector) | + Collector.Front; + } + + template ::value, int> = 0> + friend auto operator|(ClosureCollector &&Collector, ClosureT &&Closure) { + using CollectorT = GrowCollector; + return CollectorT(std::forward(Closure), std::move(Collector)); + } + + template ::value, int> = 0> + friend auto operator|(ClosureCollector const &Collector, ClosureT &&Closure) { + using CollectorT = GrowCollector; + return CollectorT(std::forward(Closure), Collector); + } +}; + +// +// Empty closure collector specialization. Its only job is to echo the +// iterable range reference back up to the pipe operator of a single-element +// collector. +// +template <> struct ClosureCollector<> { + + template ::value, int> = 0> + friend decltype(auto) operator|(IterableT &&Iterable, ClosureCollector) { + // Identity... forward the iterable reference back up the call-stack. + return std::forward(Iterable); + } +}; + +/// +/// \brief Closure object which carries a parameter. +/// +/// This is used by the `AdapterWithParam` class to carry state for it's pipe +/// operator. +/// +/// \tparam ViewTrans Stateless type which converts an `Iterable` object +/// and a parameter object to a new view. +/// \tparam ParamT Type of the parameter to carry for later view conversion. +/// +template class ParamClosure { + std::tuple...> Params; + + auto idxSeq() const { return std::index_sequence_for(); } + +public: + template < + typename... Qn, + std::enable_if_t< + std::conjunction>...>::value, + int> = 0> + ParamClosure(Qn &&...Ps) : Params(std::forward(Ps)...) {} + + template + static auto toView(IterableT &&Iterable, ParamClosure const &Closure, + std::index_sequence) { + return ViewTrans()(std::forward(Iterable), + std::get(Closure.Params)...); + } + + template + static auto toView(IterableT &&Iterable, ParamClosure &&Closure, + std::index_sequence) { + return ViewTrans()(std::forward(Iterable), + std::move(std::get(Closure.Params))...); + } + + template ::value, int> = 0> + friend auto operator|(IterableT &&Iterable, ParamClosure const &Closure) { + return ParamClosure::toView(std::forward(Iterable), Closure, + Closure.idxSeq()); + } + + template ::value, int> = 0> + friend auto operator|(IterableT &&Iterable, ParamClosure &&Closure) { + return ParamClosure::toView(std::forward(Iterable), Closure, + Closure.idxSeq()); + } + + template ::value, int> = 0> + friend auto operator|(ClosureT &&L, ParamClosure const &R) { + using CollectorT = MakeCollector; + return CollectorT(R, std::forward(L)); + } + + template ::value, int> = 0> + friend auto operator|(ClosureT &&L, ParamClosure &&R) { + using CollectorT = MakeCollector; + return CollectorT(std::move(R), std::forward(L)); + } +}; + +// Inform the ClosureCollector that `ParamClosure` is a closure type. +template +struct IsClosureImpl> : std::true_type {}; + +/// +/// \brief Boiler-plate class which implements the view adapter API for views +/// which rely on a single parameter. +/// +/// \tparam ViewTrans Stateless type which converts an `Iterable` object +/// and a parameter object to a new view. +/// +template struct Adapter { + // + // Synthesize a filter view from a specified iterable and a parameter. + // + template = 0> + auto operator()(IterableT &&Iterable, Pn &&...Params) const { + static_assert(ForwardIterable::value, + "Specified object cannot be iterated."); + return ViewTrans()(std::forward(Iterable), + std::forward(Params)...); + } + + // + // Create an unspecified object which can be used in range closure + // expressions. + // + template = 0> + auto operator()(Pn &&...Params) const { + using ClosureT = ParamClosure; + return ClosureT(std::forward(Params)...); + } +}; + +/// +/// \brief Boiler-plate class which implements the view adapter API for +/// stateless views. +/// +/// \tparam ViewTrans Stateless type which converts an `Iterable` object +/// to a new view. +/// +template struct Adapter { + // + // Synthesize a filter view from a specified iterable object. + // + template auto operator()(IterableT &&Iterable) const { + static_assert(ForwardIterable::value, + "Specified object cannot be iterated."); + return ViewTrans()(std::forward(Iterable)); + } + + // + // Create an unspecified object which can be used in range closure + // expressions. + // + template ::value, int> = 0> + friend auto operator|(IterableT &&Iterable, Adapter) { + return ViewTrans()(std::forward(Iterable)); + } + + template ::value, int> = 0> + friend auto operator|(ClosureT &&L, Adapter R) { + using CollectorT = MakeCollector; + return CollectorT(R, std::forward(L)); + } +}; + +// Inform the ClosureCollector that `SimpleAdapter` is a closure type. +template +struct IsClosureImpl> : std::true_type {}; + +} // namespace closure_impl +} // namespace llvm + +#endif // LLVM_ADT_CLOSURE_H diff --git a/llvm/include/llvm/ADT/Ranges.h b/llvm/include/llvm/ADT/Ranges.h new file mode 100644 --- /dev/null +++ b/llvm/include/llvm/ADT/Ranges.h @@ -0,0 +1,917 @@ +//===-- Ranges.h - Ranges infrstructure. ------------------------*- 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 Ranges.h +/// Ranges infrastructure. +/// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_ADT_RANGES_H +#define LLVM_ADT_RANGES_H + +#include "llvm/ADT/Callable.h" +#include "llvm/ADT/Closure.h" +#include "llvm/ADT/RangesConcepts.h" +#include "llvm/ADT/STLExtras.h" +#include "llvm/ADT/STLForwardCompat.h" +#include "llvm/ADT/SmallString.h" +#include "llvm/ADT/iterator.h" +#include "llvm/Support/raw_ostream.h" + +#include +#include +#include + +namespace llvm { + +/// +/// A sentinel class which compared not-equal to everything. +/// +class unreachable_sentinel_t // NOLINT(readability-identifier-naming) + : public iterator_facade_base { +public: + template + friend bool operator==(unreachable_sentinel_t, T const &) { + return false; + } + + template + friend bool operator==(T const &, unreachable_sentinel_t) { + return false; + } + + template + friend bool operator!=(unreachable_sentinel_t, T const &) { + return true; + } + + template + friend bool operator!=(T const &, unreachable_sentinel_t) { + return true; + } +}; + +namespace range_impl { + +template constexpr auto anchorIterCat() { + using Cat = typename std::iterator_traits::iterator_category; + if constexpr (std::is_base_of_v) { + return Anchor(); + } else { + return Cat(); + } +} + +template +using AnchorIterCategory = + decltype(anchorIterCat, Anchor>()); + +template struct IsIterRangeImpl : std::false_type {}; + +template +struct IsIterRangeImpl> : std::true_type {}; + +template +constexpr inline bool IsIterRange = + IsIterRangeImpl>::value; + +template +constexpr inline bool CmpEn = + // NOLINTNEXTLINE(misc-redundant-expression) + ForwardIterable::value &&ForwardIterable::value && + (IsIterRange + IsIterRange > 0); + +} // namespace range_impl + +template , int> = 0> +inline bool operator==(I1 &&L, I2 &&R) { + return std::equal(adl_begin(L), adl_end(L), adl_begin(R), adl_end(R)); +} + +template , int> = 0> +inline bool operator!=(I1 &&L, I2 &&R) { + return !operator==(L, R); +} + +template , int> = 0> +inline bool operator<(I1 &&L, I2 &&R) { + return std::lexicographical_compare(adl_begin(L), adl_end(L), adl_begin(R), + adl_end(R)); +} + +template , int> = 0> +inline bool operator>(I1 &&L, I2 &&R) { + return operator<(R, L); +} + +template , int> = 0> +inline bool operator<=(I1 &&L, I2 &&R) { + return !operator<(R, L); +} + +template , int> = 0> +inline bool operator>=(I1 &&L, I2 &&R) { + return !operator<(L, R); +} + +template , int> = 0> +raw_ostream &operator<<(raw_ostream &S, RangeT const &Range) { + SmallString<100> ElementStorage; + SmallString<100> LineStorage; + raw_svector_ostream LS(LineStorage); + + static constexpr size_t LineLimit = 20; + + size_t NLines = 1; + bool First = true; + + auto PrintElement = [&](auto const &Element) { + ElementStorage.clear(); + raw_svector_ostream ES(ElementStorage); + ES << Element; + + LS << (First ? "" : ", "); + First = false; + + if (LineStorage.size() != 0 && + LineStorage.size() + ElementStorage.size() + 4 >= LineLimit) { + S << "\n " << LineStorage; + LineStorage.clear(); + ++NLines; + } + LS << ElementStorage; + }; + + S << "{"; + for (auto const &E : Range) + PrintElement(E); + + return S << (NLines == 1 ? " " : "\n ") << LineStorage + << (NLines == 1 ? (First ? "" : " ") : "\n") << '}'; +} + +template ::value, int> = 0> +auto make_range(IterableT &&Iterable) // NOLINT(readability-identifier-naming) + -> decltype(make_range(adl_begin(Iterable), adl_end(Iterable))) { + return make_range(adl_begin(Iterable), adl_end(Iterable)); +} + +//===----------------------------------------------------------------------===// +// views::iota +// + +// Forward declare for doxygen's benefit. +template class iota_range; + +namespace range_impl { + +// +// Unspecialized Iota iterator. +// 1. Mismatched W,B types where B != UnreachableSentinel evaluate to this. +// +// Can implement this later if someone finds a use for it (seems unlikely). +// +template ()> +class iota_iterator {}; // NOLINT(readability-identifier-naming) + +// +// Unbound specialization. +// 1. Equivalence always returns `false`. +// 2. Only a forward iterator. +// +template +class iota_iterator + : public iterator_facade_base< + iota_iterator, + std::forward_iterator_tag, W, ptrdiff_t, W *, W> { + W Pos{}; + +public: + iota_iterator(unreachable_sentinel_t) {} + explicit iota_iterator(W P) : Pos(P) {} + + W operator*() const { return Pos; } + + iota_iterator &operator++() { + ++Pos; + return *this; + } + + bool operator==(iota_iterator const &Other) const { return false; } +}; + +// +// Bound specialization. +// 1. W and B are the same type. +// 2. Comparisons are against the underlying counter (W). +// 3. Random-access iterator. +// +template +class iota_iterator + : public iterator_facade_base, + std::random_access_iterator_tag, W, ptrdiff_t, + W *, W> { + W Pos{}; + +public: + // NOLINTNEXTLINE(readability-identifier-naming) + using difference_type = ptrdiff_t; + + explicit iota_iterator(W P) : Pos(P) {} + + W operator*() const { return Pos; } + + iota_iterator &operator+=(W Addend) { + Pos += Addend; + return *this; + } + + iota_iterator &operator-=(W Subtrahend) { + Pos -= Subtrahend; + return *this; + } + + friend difference_type operator-(iota_iterator L, iota_iterator R) { + return difference_type(L.Pos) - difference_type(R.Pos); + } + + bool operator==(iota_iterator const &Other) const { return Pos == Other.Pos; } + bool operator<(iota_iterator const &Other) const { return Pos < Other.Pos; } +}; + +} // namespace range_impl + +/// +/// Represent a contiguous range of integer-like values. +/// +/// \tparam W Count type - must be integer-like. +/// \tparam B Boundary type. +/// +/// The range of integer-like values spans from `Start` to `Bound`. If the +/// Bound type is left as the default type, the range represents values +/// `[Start, infinity)`. +/// +template +class iota_view // NOLINT(readability-identifier-naming) + : public iterator_range> { + using BaseT = iterator_range>; + +public: + // NOLINTBEGIN(readability-identifier-naming) + using iterator = range_impl::iota_iterator; + using const_iterator = iterator; + // NOLINTEND(readability-identifier-naming) + + iota_view(W Start, B Bound = {}) + : iota_view::iterator_range(iterator(Start), iterator(Bound)) {} +}; + +namespace range_impl { + +template +struct IsIterRangeImpl> : std::true_type {}; + +struct IotaAdapter { + template , int> = 0> + iota_view operator()(W Start, B End) const { + return {Start, static_cast(End)}; + } + + template , int> = 0> + auto operator()(W Start, B End) const { + static_assert(std::is_convertible_v, + "Not implemented; use `views::iota(Start)` for an " + "unbound iota."); + + return iterator_range(nullptr, nullptr); + } + + template iota_view operator()(W Start = {}) const { + return iota_view(Start); + } +}; + +} // namespace range_impl + +namespace views { + +/// +/// A view adapter which generates an `IotaView` over the specified +/// range of integer-like values. +/// +/// Simlar to `std::ranges::views::iota`: +/// - https://en.cppreference.com/w/cpp/ranges/iota_view +/// +/// This view adapter is different from the others in the sense that it +/// generates a new range based on arguments to call overloads. +/// +constexpr inline range_impl::IotaAdapter + iota{}; // NOLINT(readability-identifier-naming) + +} // namespace views + +// +// End views::iota +//===----------------------------------------------------------------------===// + +//===----------------------------------------------------------------------===// +// views::reverse +// + +namespace range_impl { + +struct ToReverseView { + template auto operator()(IterableT &&Iterable) const { + static_assert(ForwardIterable::value, + "IterableT must be a forward iterable object."); + + static_assert(IsBidirectionalIterator>::value, + "Iterable must iterate with a bi-directional iterator type."); + return llvm::reverse(std::forward(Iterable)); + } +}; + +using ReverseAdapterT = closure_impl::Adapter; + +} // namespace range_impl + +namespace views { + +/// +/// A view adapter which reverses the order of elements in a +/// bi-directionally iterable object. +/// +/// Simlar to `std::ranges::views::reverse`: +/// - https://en.cppreference.com/w/cpp/ranges/reverse_view +/// +constexpr inline range_impl::ReverseAdapterT + reverse; // NOLINT(readability-identifier-naming) + +} // namespace views + +// +// End - views::reverse +//===----------------------------------------------------------------------===// + +//===----------------------------------------------------------------------===// +// views::early_inc +// + +namespace range_impl { + +struct ToEarlyIncView { + template auto operator()(IterableT &&Iterable) const { + static_assert(ForwardIterable::value, + "IterableT must be a forward iterable object."); + return make_early_inc_range(Iterable); + } +}; + +using EarlyIncAdapter = closure_impl::Adapter; + +} // namespace range_impl + +namespace views { + +/// +/// A view adapter which applies an early increment to iterators in the +/// incoming range. +/// +/// Early increment means that the iterator is advanced during the +/// `operator*()`. The `operator++()` becomes effectively a no-op. The +/// resulting view should typically only be used in a ranged-for statement to +/// tolerate modifications to the underlying container during the loop body. +/// +/// This view anchors the resulting iterator category to +/// `InputIteratorCategory`. This limits the number of adapters which can +/// follow it in a closure. Generally it is best to apply `views::early_inc` +/// last. +/// +constexpr inline range_impl::EarlyIncAdapter + early_inc{}; // NOLINT(readability-identifier-naming) + +} // namespace views + +// +// End - views::early_inc +//===----------------------------------------------------------------------===// + +//===----------------------------------------------------------------------===// +// views::filter +// + +namespace range_impl { + +struct ToFilterView { + template + auto operator()(IterableT &&Iterable, PredT &&Predicate) const { + return make_filter_range(std::forward(Iterable), + Callable(std::forward(Predicate))); + } +}; + +using FilterAdapter = closure_impl::Adapter; + +} // namespace range_impl + +namespace views { + +constexpr inline range_impl::FilterAdapter + filter{}; // NOLINT(readability-identifier-naming) + +} // namespace views + +// +// End - views::filter +//===----------------------------------------------------------------------===// + +//===----------------------------------------------------------------------===// +// views::transform +// + +namespace range_impl { + +struct ToTransformView { + template + auto operator()(IterableT &&Iterable, TransT &&Transform) const { + static_assert(ForwardIterable::value, + "IterableT must be a forward iterable object."); + + return map_range(std::forward(Iterable), + Callable(Transform)); + } +}; + +using TransformAdapterT = closure_impl::Adapter; + +} // namespace range_impl + +namespace views { + +constexpr inline range_impl::TransformAdapterT + transform{}; // NOLINT(readability-identifier-naming) + +} // namespace views + +// +// End - views::transform +//===----------------------------------------------------------------------===// + +//===----------------------------------------------------------------------===// +// views::elements +// + +namespace range_impl { + +template struct ToElementsView { + struct GetElement { + template decltype(auto) operator()(T &TplOrPr) const { + return std::get(TplOrPr); + } + + template decltype(auto) operator()(T const &TplOrPr) const { + return std::get(TplOrPr); + } + + template decltype(auto) operator()(T &&TplOrPr) const { + return std::get(std::move(TplOrPr)); + } + }; + + template auto operator()(IterableT &&Iterable) const { + return views::transform(Iterable, GetElement()); + } +}; + +template +using ElementsAdapter = closure_impl::Adapter>; + +} // namespace range_impl + +namespace views { + +template +constexpr inline range_impl::ElementsAdapter + elements{}; // NOLINT(readability-identifier-naming) + +} // namespace views + +// +// End - views::elements +//===----------------------------------------------------------------------===// + +//===----------------------------------------------------------------------===// +// views::keys +// + +namespace views { + +constexpr inline range_impl::ElementsAdapter<0> + keys{}; // NOLINT(readability-identifier-naming) + +} // namespace views + +// +// End - views::keys +//===----------------------------------------------------------------------===// + +//===----------------------------------------------------------------------===// +// Values view implementation. +// + +namespace views { + +constexpr inline range_impl::ElementsAdapter<1> + values{}; // NOLINT(readability-identifier-naming) + +} // namespace views + +// +// End - view::values +//===----------------------------------------------------------------------===// + +//===----------------------------------------------------------------------===// +// views::take +// + +namespace range_impl { + +template void advance(IterT &I, size_t N, IterT const &E) { + if constexpr (IsRandomAccessIterator::value) { + auto NDiff = + static_cast::difference_type>(N); + + if (NDiff < std::distance(I, E)) + I += NDiff; + else + I = E; + + } else { + while (I != E && N--) + ++I; + } +} + +struct ToTakeView { + template + auto operator()(IterableT &&Iterable, size_t N) const { + static_assert(ForwardIterable::value, + "Specified object cannot be iterated."); + + auto E = adl_begin(Iterable); + advance(E, N, adl_end(Iterable)); + return make_range(adl_begin(Iterable), std::move(E)); + } +}; + +using TakeAdapter = closure_impl::Adapter; + +} // namespace range_impl + +namespace views { + +constexpr inline range_impl::TakeAdapter + take{}; // NOLINT(readability-identifier-naming) + +} // namespace views + +// +// End - views::take +//===----------------------------------------------------------------------===// + +//===----------------------------------------------------------------------===// +// views::drop +// + +namespace range_impl { + +struct ToDropView { + template + auto operator()(IterableT &&Iterable, size_t N) const { + auto B = adl_begin(Iterable); + auto E = adl_end(Iterable); + advance(B, N, E); + return make_range(std::move(B), std::move(E)); + } +}; + +using DropAdapter = closure_impl::Adapter; + +} // namespace range_impl + +namespace views { + +constexpr inline range_impl::DropAdapter + drop{}; // NOLINT(readability-identifier-naming) + +} // namespace views + +// +// End - views::drop +//===----------------------------------------------------------------------===// + +//===----------------------------------------------------------------------===// +// views::take_while +// + +template +class take_while_iterator // NOLINT(readability-identifier-naming) + : public iterator_adaptor_base< + take_while_iterator, Iter, + range_impl::AnchorIterCategory> { + using BaseT = typename take_while_iterator::iterator_adaptor_base; + +private: + Callable Predicate; + +public: + take_while_iterator(Iter const &I) : BaseT(I) {} + take_while_iterator(Iter &&I) : BaseT(std::move(I)) {} + + take_while_iterator(Iter const &I, Pred P) : BaseT(I), Predicate(P) {} + take_while_iterator(Iter &&I, Pred P) : BaseT(std::move(I)), Predicate(P) {} + + bool operator==(take_while_iterator const &Other) const { + return this->wrapped() == Other.wrapped() || (atEnd() && Other.atEnd()); + } + +private: + bool atEnd() const { + return !Predicate.valid() || !Predicate(*this->wrapped()); + } +}; + +namespace range_impl { + +struct ToTakeWhileView { + template + auto operator()(IterableT &&Iterable, PredT &&Pred) const { + using Iter = take_while_iterator, PredT>; + + return make_range(Iter(adl_begin(Iterable), std::forward(Pred)), + Iter(adl_end(Iterable))); + } +}; + +using TakeWhileAdapter = closure_impl::Adapter; + +} // namespace range_impl + +namespace views { + +constexpr inline range_impl::TakeWhileAdapter + take_while{}; // NOLINT(readability-identifier-naming) + +} // namespace views + +// +// End - views::take_while +//===----------------------------------------------------------------------===// + +//===----------------------------------------------------------------------===// +// views::take_while +// + +template +class drop_while_view // NOLINT(readability-identifier-naming) + : public iterator_range { + using BaseT = iterator_range; + +private: + Callable Predicate; + +public: + using drop_while_view::iterator_range::iterator_range; + + template ::value && + std::is_same_v, Iter>, + int> = 0> + drop_while_view(RangeT &&R, Pred P) + : BaseT(adl_begin(R), adl_end(R)), Predicate(P) {} + + drop_while_view(Iter B, Iter E, Pred P) : BaseT(B, E), Predicate(P) {} + + Iter begin() const { return condAdvance(BaseT::begin()); } + +private: + Iter condAdvance(Iter I) const { + auto E = this->end(); + while (I != E && Predicate(*I)) + ++I; + + return I; + } +}; + +namespace range_impl { + +template +struct IsIterRangeImpl> : std::true_type {}; + +} // namespace range_impl + +namespace range_impl { + +struct ToDropWhileView { + template + auto operator()(IterableT &&Iterable, PredT &&Pred) const { + using IterT = GetIteratorT; + return drop_while_view(Iterable, std::forward(Pred)); + } +}; + +using DropWhileAdapter = closure_impl::Adapter; + +} // namespace range_impl + +namespace views { + +constexpr inline range_impl::DropWhileAdapter + drop_while{}; // NOLINT(readability-identifier-naming) + +} // namespace views + +// +// End - views::drop_while +//===----------------------------------------------------------------------===// + +//===----------------------------------------------------------------------===// +// `to` function implementation. +// + +namespace to_impl { + +template ::value> +struct CompatibleImpl {}; + +template +struct CompatibleImpl : std::false_type {}; + +template +struct CompatibleImpl + : DerefConvertible< + GetIteratorT, + std::remove_reference_t< + decltype(*std::declval>())>> {}; + +template +constexpr inline bool Compatible = CompatibleImpl::value; + +template struct ToAdapter { + using ContainerT = C; + + template struct Closure { + using ContainerT = typename ToAdapter::ContainerT; + + // Carry the extra constructor Params for the `ContainerT`. + std::tuple...> Params; + + Closure(Pn &&...P) : Params(std::forward(P)...) {} + + template + static auto toContainer(Closure const &Closure, IterableT &&Iterable, + std::index_sequence) { + return ContainerT(adl_begin(Iterable), adl_end(Iterable), + std::get(Closure.Params)...); + } + + template + static auto toContainer(Closure &&Closure, IterableT &&Iterable, + std::index_sequence) { + return ContainerT(adl_begin(Iterable), adl_end(Iterable), + std::move(std::get(Closure.Params))...); + } + + template + friend auto operator|(IterableT &&Iterable, Closure const &Closure) { + static_assert(ForwardIterable::value, + "Specified object cannot be iterated."); + + static_assert(Compatible, + "Values are incompatible between the specified " + "iterable object and the container type."); + + static_assert(std::is_constructible_v, + GetIteratorT, Pn...>, + "ContainerT cannot be constructed from a range of " + "the specified iterator type."); + + return Closure::toContainer(Closure, std::forward(Iterable), + std::index_sequence_for()); + } + + template + friend auto operator|(IterableT &&Iterable, Closure &&Closure) { + static_assert(ForwardIterable::value, + "Specified object cannot be iterated."); + + static_assert(Compatible, + "Values are incompatible between the specified " + "iterable object and the container type."); + + static_assert(std::is_constructible_v, + GetIteratorT, Pn...>, + "ContainerT cannot be constructed from a range of " + "the specified iterator type."); + + return Closure::toContainer(std::move(Closure), + std::forward(Iterable), + std::index_sequence_for()); + } + }; + + // + // Synthesize a filter view from a specified iterable and a parameter. + // + template + static auto toContainer(IterableT &&Iterable, Pn &&...Params) { + return ContainerT(adl_begin(Iterable), adl_end(Iterable), + std::forward(Params)...); + } + + // + // Create an unspecified object which can be used in range closure + // expressions. + // + template static auto toClosure(Pn &&...Params) { + return Closure(std::forward(Params)...); + } +}; + +} // namespace to_impl + +/// +/// Create a pipe closure object which converts an incoming iterable +/// object to a new `ContainerT` object. +/// +/// \tparam ContainerT Container type to convert the range to. +/// \tparam ExtraArgs Extra coutput container constructor argument types. +/// +/// \param Args Extra container constructor arguments. +/// +/// \return An unspecified object which supports `operator|()` and copies +/// elements from the input range to a new `ContainerT`. +/// +template +auto to(ExtraArgs &&...Args) { + using AdapterT = to_impl::ToAdapter; + return AdapterT::toClosure(std::forward(Args)...); +} + +/// +/// Create a new `ContainerT object initialized with copies from a +/// specified iterable object. +/// +/// \tparam ContainerT Container type to convert the range to. +/// \tparam IterableT Iterable object type to copy from. +/// \tparam ExtraArgs Extra output container constructor argument types. +/// +/// \param Iterable Iterable object to copy elements from. +/// \param Args Extra container constructor arguments; typically the +/// allocator. +/// +/// \return An unspecified object which supports `operator|()` and copies +/// elements from the input range to a new `ContainerT`. +/// +template , int> = 0> +auto to(IterableT &&Iterable, ExtraArgs &&...Args) { + + static_assert(std::is_constructible_v, + GetIteratorT, ExtraArgs...>, + "ContainerT cannot be constructed from a range of " + "the specified iterator type."); + + using AdapterT = to_impl::ToAdapter; + return AdapterT::toContainer(std::forward(Iterable), + std::forward(Args)...); +} + +// +// End - `to` function implementation. +//===----------------------------------------------------------------------===// + +} // namespace llvm + +#endif // LLVM_ADT_RANGES_H diff --git a/llvm/include/llvm/ADT/RangesConcepts.h b/llvm/include/llvm/ADT/RangesConcepts.h new file mode 100644 --- /dev/null +++ b/llvm/include/llvm/ADT/RangesConcepts.h @@ -0,0 +1,308 @@ +//===- RangesConcepts.h - Pre C++20 Concepts for Ranges SFINAE. ----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 RangesConcepts.h +/// Pre C++20 concepts for SFINAE. +/// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_ADT_RANGESCONCEPTS_H +#define LLVM_ADT_RANGESCONCEPTS_H + +#include +#include +#include + +namespace llvm { + +/// Determine whether the specified type can be dereferenced. +template +class CanDeref : public std::false_type {}; + +template +class CanDeref())>> + : public std::true_type {}; + +/// Determine whether the specified type has a `begin` member function. +template +class HasBegin : public std::false_type {}; + +template +class HasBegin().begin())>> + : public std::true_type {}; + +/// Determine whether an ADL `begin` function exists for the specified type. +template +class HasBeginADL : public std::false_type {}; + +template +class HasBeginADL()))>> + : public std::true_type {}; + +/// Determine whether an `std::begin` function exists for the specified type. +template +class HasBeginSTD : public std::false_type {}; + +template +class HasBeginSTD()))>> + : public std::true_type {}; + +/// Determine whether the specified type has a `end` member function. +template class HasEnd : public std::false_type {}; + +template +class HasEnd().end())>> + : public std::true_type {}; + +/// Determine whether an ADL `end` function exists for the specified type. +template +class HasEndADL : public std::false_type {}; + +template +class HasEndADL()))>> + : public std::true_type {}; + +/// Determine whether an `std::end` function exists for the specified type. +template +class HasEndSTD : public std::false_type {}; + +template +class HasEndSTD>()))>> + : public std::true_type {}; + +/// Determine whether a type dereferences to a type which can be used to +/// construct another specified type. +/// +/// \tparam I Iterator type to dereference. +/// \tparam To Type to query for constructible. +template ::value> +class DerefConstructible : std::false_type {}; + +template +class DerefConstructible + : public std::is_constructible())> {}; + +/// Determine whether a type dereferences to a type which can be converted to +/// another specified type. +/// +/// \tparam I Iterator type to dereference. +/// \tparam To Type to query for convertible. +template ::value> +class DerefConvertible : std::false_type {}; + +template +class DerefConvertible + : public std::is_convertible()), To> {}; + +/// Determine whether a type is an iterator (i.e. belongs to any iterator +/// category). +template +class IsIterator : public std::false_type {}; + +// clang-format off +template +class IsIterator< + T, + std::void_t< + typename std::iterator_traits< + std::remove_cv_t< + std::remove_reference_t + > + >::iterator_category + > +> : public std::true_type {}; +// clang-format on + +/// Determine whether a type belongs to the specified iterator category. +/// +/// \tparam T Iterator type to query. +/// \tparam Cat Iterator category to +template ::value> +class IsIteratorCategory : public std::false_type {}; + +template +class IsIteratorCategory + : public // clang-format off + std::is_base_of< + Cat, + typename std::iterator_traits< + std::remove_reference_t + >::iterator_category + > {}; +// clang-format on + +template +using IsInputIterator = IsIteratorCategory; + +template +using IsOutputIterator = IsIteratorCategory; + +template +using IsForwardIterator = IsIteratorCategory; + +template +using IsBidirectionalIterator = + IsIteratorCategory; + +template +using IsRandomAccessIterator = + IsIteratorCategory; + +/// Determine whether a specified type can be forward iterated using member +/// functions. +template ::value &&HasEnd::value> +class ForwardIterableMember : public std::false_type {}; + +template +class ForwardIterableMember + : public // clang-format off + std::bool_constant< + std::is_same< + decltype(std::declval().begin()), + decltype(std::declval().end()) + >::value + && IsInputIterator().begin())>::value + > {}; +// clang-format on + +/// Determine whether a specified type can be forward iterated using ADL +/// functions. +template ::value &&HasEndADL::value> +class ForwardIterableADL : public std::false_type {}; + +template +class ForwardIterableADL + : public // clang-format off + std::bool_constant< + std::is_same< + decltype(begin(std::declval())), + decltype( end(std::declval())) + >::value + && IsInputIterator()))>::value + > {}; +// clang-format on + +/// Determine whether a specified type can be forward iterated using `std` +/// namespace functions. +template ::value &&HasEndSTD::value> +class ForwardIterableSTD : public std::false_type {}; + +template +class ForwardIterableSTD + : public // clang-format off + std::bool_constant< + std::is_same< + decltype(std::begin(std::declval())), + decltype( std::end(std::declval())) + >::value + && IsInputIterator()))>::value + > {}; +// clang-format on + +template +using ForwardIterable = std::bool_constant::value || + ForwardIterableADL::value || + ForwardIterableSTD::value>; + +/// Call the correct `begin` function associated with a forward iterable +/// container type. +template ::value, + bool ADL = ForwardIterableADL::value, + bool STL = ForwardIterableSTD::value> +class GetBegin {}; + +template +class GetBegin { +public: + template auto operator()(T &&C) const -> decltype(C.begin()) { + return C.begin(); + } +}; + +template +class GetBegin { +public: + template auto operator()(T &&C) const -> decltype(begin(C)) { + return begin(C); + } +}; + +template class GetBegin { +public: + template + auto operator()(T &&C) const -> decltype(std::begin(C)) { + return std::begin(C); + } +}; + +/// Call the correct `end` function associated with a forward iterable container +/// type. +template ::value, + bool ADL = ForwardIterableADL::value, + bool STL = ForwardIterableSTD::value> +class GetEnd {}; + +template +class GetEnd { +public: + template auto operator()(T &&C) const -> decltype(C.end()) { + return C.end(); + } +}; + +template +class GetEnd { +public: + template auto operator()(T &&C) const -> decltype(end(C)) { + return end(C); + } +}; + +template class GetEnd { +public: + template auto operator()(T &&C) const -> decltype(std::end(C)) { + return std::end(C); + } +}; + +/// Determine the forward iterator type associated with a specified container +/// type. +/// +/// Evaluates to `void` if `ContainerT` is not `ForwardIterable`. +template ::value> +class GetIterator { +public: + using type = void; +}; + +template class GetIterator { + using BeginT = GetBegin; + +public: + using type = decltype(std::declval()(std::declval())); +}; + +template +using GetIteratorT = typename GetIterator::type; + +/// Determine whether a specified container type is forward iterable and the +/// dereferenced type is convertible to `T`. +template ::value> +class ForwardIterableAndConvertible : public std::false_type {}; + +template +class ForwardIterableAndConvertible + : public std::is_convertible>()), + T> {}; + +} // namespace llvm + +#endif // LLVM_ADT_RANGESCONCEPTS_H diff --git a/llvm/include/llvm/ADT/STLExtras.h b/llvm/include/llvm/ADT/STLExtras.h --- a/llvm/include/llvm/ADT/STLExtras.h +++ b/llvm/include/llvm/ADT/STLExtras.h @@ -312,7 +312,7 @@ template auto map_range(ContainerTy &&C, FuncTy F) { - return make_range(map_iterator(C.begin(), F), map_iterator(C.end(), F)); + return make_range(map_iterator(adl_begin(C), F), map_iterator(adl_end(C), F)); } /// A base type of mapped iterator, that is useful for building derived diff --git a/llvm/unittests/ADT/CMakeLists.txt b/llvm/unittests/ADT/CMakeLists.txt --- a/llvm/unittests/ADT/CMakeLists.txt +++ b/llvm/unittests/ADT/CMakeLists.txt @@ -56,6 +56,7 @@ PostOrderIteratorTest.cpp PriorityWorklistTest.cpp RangeAdapterTest.cpp + RangesTest.cpp SCCIteratorTest.cpp STLExtrasTest.cpp STLForwardCompatTest.cpp diff --git a/llvm/unittests/ADT/RangesTest.cpp b/llvm/unittests/ADT/RangesTest.cpp new file mode 100644 --- /dev/null +++ b/llvm/unittests/ADT/RangesTest.cpp @@ -0,0 +1,1162 @@ +//===- llvm/unittest/ADT/RangesTest.cpp -------------------------*- 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 +// +//===----------------------------------------------------------------------===// + +#include "llvm/ADT/Ranges.h" + +#include "llvm/Support/Compiler.h" +#include "llvm/Support/Debug.h" +#include "gtest/gtest.h" + +#include +#include +#include + +using namespace llvm; + +namespace { + +template struct IsSingleAdapterImpl : std::false_type {}; + +template +struct IsSingleAdapterImpl> : std::true_type {}; + +template +constexpr inline bool IsSingleAdapter = + IsSingleAdapterImpl>::value; + +auto ToUpper = [](char C) { return static_cast(::toupper(C)); }; + +template > +using GetValType = remove_cvref_t())>; + +template struct EqualComparable { + friend bool operator!=(Derived const &L, Derived const &R) { + return !(L == R); + } +}; + +template struct RelativeComparable { + friend bool operator>(Derived const &L, Derived const &R) { return (R < L); } + + friend bool operator<=(Derived const &L, Derived const &R) { + return !(L > R); + } + + friend bool operator>=(Derived const &L, Derived const &R) { + return !(L < R); + } +}; + +// A wrapper class which counts events. +template +struct Counted : EqualComparable>, RelativeComparable> { + T Val; + + static size_t Construct; + static size_t Destroy; + + static size_t Copy; + static size_t Move; + + static size_t CopyAssign; + static size_t MoveAssign; + + Counted(Counted const &Other) : Val(Other.Val) { ++Copy; } + Counted(Counted &&Other) : Val(std::move(Other.Val)) { ++Move; } + + template < + typename... ArgsT, + std::enable_if_t::value, int> = 0> + Counted(ArgsT &&...Args) : Val(std::forward(Args)...) { + ++Construct; + } + + ~Counted() { ++Destroy; } + + Counted &operator=(Counted const &Other) { + Val = Other.Val; + ++CopyAssign; + } + + Counted &operator=(Counted &&Other) { + Val = std::move(Other.Val); + ++MoveAssign; + } + + explicit operator T &() { return Val; } + + explicit operator T const &() const { return Val; } + + static void reset() { + Construct = 0; + Destroy = 0; + + Copy = 0; + Move = 0; + + CopyAssign = 0; + MoveAssign = 0; + } + + friend bool operator==(Counted const &L, Counted const &R) { + return L.Val == R.Val; + } + + friend bool operator<(Counted const &L, Counted const &R) { + return L.Val < R.Val; + } + + friend bool operator==(T const &L, Counted const &R) { return L == R.Val; } + + friend bool operator==(Counted const &L, T const &R) { return L.Val == R; } + + friend bool operator!=(T const &L, Counted const &R) { return L != R.Val; } + + friend bool operator!=(Counted const &L, T const &R) { return L.Val != R; } +}; + +template size_t Counted::Construct = 0; +template size_t Counted::Destroy = 0; +template size_t Counted::Copy = 0; +template size_t Counted::Move = 0; +template size_t Counted::CopyAssign = 0; +template size_t Counted::MoveAssign = 0; + +template class NonTriv { + T Value{}; + +public: + NonTriv() {} + NonTriv(T V) : Value(V) {} + + NonTriv(NonTriv const &Other) : Value(Other.Value) {} + NonTriv &operator=(NonTriv Other) { + Value = Other.Value; + return *this; + } + + ~NonTriv() {} + + operator T const() { return Value; } + + friend bool operator==(NonTriv L, NonTriv R) { return L.Value == R.Value; } + friend bool operator==(NonTriv L, T R) { return L.Value == R; } + friend bool operator==(T L, NonTriv R) { return L == R.Value; } + + friend bool operator!=(NonTriv L, NonTriv R) { return L.Value != R.Value; } + friend bool operator!=(NonTriv L, T R) { return L.Value != R; } + friend bool operator!=(T L, NonTriv R) { return L != R.Value; } + + friend bool operator<(NonTriv L, NonTriv R) { return L.Value < R.Value; } + friend bool operator<(NonTriv L, T R) { return L.Value < R; } + friend bool operator<(T L, NonTriv R) { return L < R.Value; } + + friend raw_ostream &operator<<(raw_ostream &S, NonTriv NT) { + return S << NT.Value; + } +}; + +template struct Rebind {}; + +template struct Rebind>, U> { + using type = std::list>; +}; + +template struct Rebind, U> { + using type = std::list; +}; + +template struct Rebind, U> { + using type = std::deque; +}; + +template struct Rebind, U> { + using type = std::vector; +}; + +template +struct Rebind, U> { + using type = SmallVector; +}; + +template +using RebindT = typename Rebind::type; + +class RangesTestBase : public testing::Test { +public: + using testing::Test::Test; + + template + void callTest(TestT const &TestIn, ExpT const &Exp, AdaptT &&Adapter, + Pn &&...Params) { + + static_assert(IsSingleAdapter, + "Expected a single adapter for callTest(), not a collection " + "of multiple adapters."); + + static_assert(range_impl::IsIterRange, + "Expected an iterator_range result from the pipe operator."); + + // Ensure comparison to unnamed temporary works + EXPECT_EQ(make_range(Exp), Adapter(TestIn, Params...)); + + { + using RC = RebindT>; + + // Copy the evaluated view to a Container. + auto Container = to(Adapter(TestIn, Params...)); + + // Ensure comparison still true. + EXPECT_EQ(make_range(Exp), Container); + } + + { + using RC = RebindT>; + + // Copy original Range to a Container. + auto Container = TestIn | to(); + + // Ensure comparison true while manipulating contents of the Container. + EXPECT_EQ(Exp, Adapter(Container, Params...)); + } + } + + template + void pipeTest(TestT const &TestIn, ExpT const &Exp, AdaptT &&Adapter) const { + + static_assert(range_impl::IsIterRange, + "Expected an iterator_range result from the pipe operator."); + + // Ensure comparison to unnamed temporary works + EXPECT_EQ(make_range(Exp), TestIn | Adapter); + + { + using RC = RebindT>; + + // Copy the evaluated view to a Container. + auto Container = TestIn | Adapter | to(); + + // Ensure comparison still true. + EXPECT_EQ(make_range(Exp), Container); + } + + { + using RC = RebindT>; + + // Copy original Range to a Container. + auto Container = TestIn | to(); + + // Ensure comparison true while manipulating contents of the Container. + EXPECT_EQ(Exp, Container | Adapter); + } + } +}; + +template class RangesToTest : public RangesTestBase { +public: + using RangesTestBase::RangesTestBase; + + using ContainerT = ToType; +}; + +// clang-format off +using ToTestTypes = + ::testing::Types< + SmallVector, + SmallVector>, + std::list, + std::list>, + std::vector, + std::vector>, + std::deque, + std::deque> + >; +// clang-format on + +TYPED_TEST_SUITE(RangesToTest, ToTestTypes, ); + +TYPED_TEST(RangesToTest, ToTest) { + + using ContainerT = TypeParam; + + auto C = views::iota(1, 4) | to>(); + + char Test[]{'a', 'b', 'c', 'd', 'e', 'f', 'g'}; + + // Simple to() (operator()) + { + auto C = to(Test); + + static_assert(std::is_same::value, + "Expected ContainerT."); + + EXPECT_EQ(C, make_range(Test)); + } + + // Simple to() (operator()) + { + auto C = Test | to(); + + static_assert(std::is_same::value, + "Expected ContainerT."); + + EXPECT_EQ(C, make_range(Test)); + } + + // transform | drop_while | to (pipe) + { + char Exp[]{'D', 'E', 'F', 'G'}; + + auto C = + Test | views::transform(ToUpper) | views::drop(3) | to(); + + static_assert(std::is_same::value, + "Expected ContainerT."); + + EXPECT_EQ(make_range(C), Exp); + } + + // transform | drop_while | to (operator()) + { + char Exp[]{'D', 'E', 'F', 'G'}; + + auto R = Test | views::transform(ToUpper) | views::drop(3); + auto C = to(R); + + static_assert(std::is_same::value, + "Expected ContainerT."); + + EXPECT_EQ(make_range(C), Exp); + } + + // Multiple container conversions. + { + int Test[]{1, 3, 5, 7, 9, 11, 13, 15}; + + auto ComputedResult = Test | to>() | views::reverse | + to>() | to>() | + to(); + + int Exp[]{15, 13, 11, 9, 7, 5, 3, 1}; + + EXPECT_EQ(make_range(Exp), ComputedResult); + } +} + +template class RangesViewsTest : public RangesTestBase { +public: + using ContainerT = C; + ContainerT Container; + + template + void callTest(TestT const &TestIn, ExpT const &Exp, AdaptT &&Adapter, + Pn &&...Params) { + RangesTestBase::template callTest(TestIn, Exp, + std::forward(Adapter), + std::forward(Params)...); + } + + template + void pipeTest(TestT const &Test, ExpT const &Exp, AdaptT &&Adapter) const { + RangesTestBase::template pipeTest( + Test, Exp, std::forward(Adapter)); + } +}; + +// clang-format off +using ViewsTestTypes = + ::testing::Types< + SmallVector, + SmallVector>, + std::list, + std::list>, + std::deque, + std::deque>, + std::vector, + std::vector> + >; +// clang-format on + +TYPED_TEST_SUITE(RangesViewsTest, ViewsTestTypes, ); + +TYPED_TEST(RangesViewsTest, CompareTest) { + int LHSArr[]{1, 2, 3}; + auto LHSCont = LHSArr | to(); + auto L = make_range(LHSCont); + + { + // R is the same sequence as L. + int R[]{1, 2, 3}; + + // compare(iterator_range, Iterable) + EXPECT_TRUE(L == R); + EXPECT_TRUE(!(L != R)); + EXPECT_TRUE(L <= R); + EXPECT_TRUE(L >= R); + EXPECT_TRUE(!(L < R)); + EXPECT_TRUE(!(L > R)); + + // compare(Iterable, iterator_range) + EXPECT_TRUE(R == L); + EXPECT_TRUE(!(R != L)); + EXPECT_TRUE(R <= L); + EXPECT_TRUE(R >= L); + EXPECT_TRUE(!(R < L)); + EXPECT_TRUE(!(R > L)); + + // compare(iterator_range, iterator_range) + auto RPrime = make_range(R); + EXPECT_TRUE(L == RPrime); + EXPECT_TRUE(!(L != RPrime)); + EXPECT_TRUE(L <= RPrime); + EXPECT_TRUE(L >= RPrime); + EXPECT_TRUE(!(L < RPrime)); + EXPECT_TRUE(!(L > RPrime)); + } + + { + // R is lexicographically greater-than L. + int R[]{3}; + + // compare(iterator_range, Iterable) + EXPECT_TRUE(!(L == R)); + EXPECT_TRUE(L != R); + EXPECT_TRUE(L <= R); + EXPECT_TRUE(!(L >= R)); + EXPECT_TRUE(L < R); + EXPECT_TRUE(!(L > R)); + + // compare(Iterable, iterator_range) + EXPECT_TRUE(!(R == L)); + EXPECT_TRUE(R != L); + EXPECT_TRUE(R >= L); + EXPECT_TRUE(!(R <= L)); + EXPECT_TRUE(R > L); + EXPECT_TRUE(!(R < L)); + + // compare(iterator_range, iterator_range) + auto RPrime = make_range(R); + EXPECT_TRUE(!(L == RPrime)); + EXPECT_TRUE(L != RPrime); + EXPECT_TRUE(L <= RPrime); + EXPECT_TRUE(!(L >= RPrime)); + EXPECT_TRUE(L < RPrime); + EXPECT_TRUE(!(L > RPrime)); + } + + { + // R is lexicographically less-than L. + int R[]{1, 2, 2}; + + // compare(iterator_range, Iterable) + EXPECT_TRUE(!(L == R)); + EXPECT_TRUE(L != R); + EXPECT_TRUE(!(L <= R)); + EXPECT_TRUE(L >= R); + EXPECT_TRUE(!(L < R)); + EXPECT_TRUE(L > R); + + // compare(Iterable, iterator_range) + EXPECT_TRUE(!(R == L)); + EXPECT_TRUE(R != L); + EXPECT_TRUE(!(R >= L)); + EXPECT_TRUE(R <= L); + EXPECT_TRUE(!(R > L)); + EXPECT_TRUE(R < L); + + // compare(iterator_range, iterator_range) + auto RPrime = make_range(R); + EXPECT_TRUE(!(L == RPrime)); + EXPECT_TRUE(L != RPrime); + EXPECT_TRUE(!(L <= RPrime)); + EXPECT_TRUE(L >= RPrime); + EXPECT_TRUE(!(L < RPrime)); + EXPECT_TRUE(L > RPrime); + } +} + +TYPED_TEST(RangesViewsTest, IotaTest) { + // bounded + { + int Exp[]{0, 1, 2, 3, 4, 5, 6, 7, 8, 9}; + EXPECT_EQ(Exp, views::iota(0, 10)); + } + + // bounded + { + int Exp[]{'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h'}; + EXPECT_EQ(Exp, views::iota('a', 'i')); + } + + // unbounded + { + int Exp[]{0, 1, 2, 3, 4, 5, 6, 7, 8, 9}; + int *P = Exp; + for (int I : views::iota()) { + if (I == 10) + break; + EXPECT_EQ(I, *P++); + } + } + + // unbounded + { + char Exp[]{'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h'}; + char *P = Exp; + for (char C : views::iota('a')) { + if (C == 'i') + break; + EXPECT_EQ(C, *P++); + } + } + + // Use Iota to index `Chars` array. + { + char Chars[]{'a', 'b', 'c', 'd', 'e', 'f', 'g'}; + char Exp[]{'e', 'd', 'c'}; + auto GetChar = [&](int I) { return Chars[I]; }; + + this->pipeTest(views::iota(2, 5), Exp, + views::reverse | views::transform(GetChar)); + } + + // Use Iota to index `Chars` array (non-trivial wrapper). + { + NonTriv Chars[]{'a', 'b', 'c', 'd', 'e', 'f', 'g'}; + char Exp[]{'e', 'd', 'c'}; + auto GetChar = [&](int I) { return Chars[I]; }; + + this->pipeTest(views::iota(2, 5), Exp, + views::reverse | views::transform(GetChar)); + } +} + +TYPED_TEST(RangesViewsTest, FilterTest) { + + char Test[]{'a', 'b', 'c', 'd', 'e', 'f', 'g'}; + + auto IsEven = [](auto X) { return (X & decltype(X)(1)) == 0; }; + + // filter (operator()). + { + char Exp[]{'b', 'd', 'f'}; + + this->callTest(Test, Exp, views::filter, IsEven); + this->pipeTest(Test, Exp, views::filter(IsEven)); + } + + // filter + filter + { + char Exp[]{'b', 'f'}; + + auto NotD = [](char C) { return C != 'd'; }; + + this->pipeTest(Test, Exp, views::filter(NotD) | views::filter(IsEven)); + } + + // transform + filter + { + char Exp[]{'B', 'D', 'F'}; + + this->pipeTest(Test, Exp, + views::transform(ToUpper) | views::filter(IsEven)); + } + + // filter + filter + reverse + { + char Exp[]{'f', 'b'}; + + auto NotD = [](char C) { return C != 'd'; }; + + auto Adapter = views::filter(NotD) | views::filter(IsEven) | views::reverse; + + this->pipeTest(Test, Exp, Adapter); + } + + // transform + filter + reverse + { + char Exp[]{'F', 'D', 'B'}; + + auto Adapter = + views::transform(ToUpper) | views::filter(IsEven) | views::reverse; + + this->pipeTest(Test, Exp, Adapter); + } + + // filter (nothing valid) + { + auto None = [](char) { return false; }; + this->pipeTest(Test, make_range(&Test[0], &Test[0]), views::filter(None)); + } + + // filter | reverse (nothing valid) + { + auto None = [](char) { return false; }; + this->pipeTest(Test, make_range(&Test[0], &Test[0]), + views::filter(None) | views::reverse); + } +} + +TYPED_TEST(RangesViewsTest, ReverseTest) { + char Test[]{'a', 'b', 'c', 'd', 'e', 'f', 'g'}; + + // reverse + { + char Exp[]{'g', 'f', 'e', 'd', 'c', 'b', 'a'}; + + this->callTest(Test, Exp, views::reverse); + this->pipeTest(Test, Exp, views::reverse); + } + + // reverse x2 + { + char Exp[]{'a', 'b', 'c', 'd', 'e', 'f', 'g'}; + + this->pipeTest(Test, Exp, views::reverse | views::reverse); + } + + // reverse | transform. + { + char Exp[]{'G', 'F', 'E', 'D', 'C', 'B', 'A'}; + + this->pipeTest(Test, Exp, views::reverse | views::transform(::toupper)); + } +} + +TYPED_TEST(RangesViewsTest, TakeTest) { + + char Test[]{'a', 'b', 'c', 'd', 'e', 'f', 'g'}; + + // take + { + char Exp[]{'a', 'b', 'c', 'd'}; + + this->callTest(Test, Exp, views::take, 4); + this->pipeTest(Test, Exp, views::take(4)); + } + + // take | take + { + char Exp[]{'a', 'b', 'c'}; + + this->pipeTest(Test, Exp, views::take(4) | views::take(3)); + } + + // take | reverse + { + char Exp[]{'d', 'c', 'b', 'a'}; + + this->pipeTest(Test, Exp, views::take(4) | views::reverse); + } + + // reverse | take + { + char Exp[]{'g', 'f', 'e', 'd'}; + + this->pipeTest(Test, Exp, views::reverse | views::take(4)); + } + + // take | reverse | drop + { + char Exp[]{'c', 'b', 'a'}; + + this->pipeTest(Test, Exp, views::take(4) | views::reverse | views::drop(1)); + } + + // reverse | take | drop + { + char Exp[]{'e', 'd'}; + + this->pipeTest(Test, Exp, views::reverse | views::take(4) | views::drop(2)); + } + + // take(0) + { + EXPECT_TRUE(empty(Test | views::take(0))); + + // Copy Range to a Container. + auto Container = Test | views::take(0) | to(); + + EXPECT_TRUE(Container.empty()); + Container.clear(); + } + + // take (larger than input) + { + auto &Exp = Test; + this->pipeTest(Test, Exp, views::take(100)); + } +} + +TYPED_TEST(RangesViewsTest, DropTest) { + char Test[]{'a', 'b', 'c', 'd', 'e', 'f', 'g'}; + + // drop + { + char Exp[]{'d', 'e', 'f', 'g'}; + + this->callTest(Test, Exp, views::drop, 3); + this->pipeTest(Test, Exp, views::drop(3)); + } + + // drop | reverse + { + char Exp[]{'g', 'f', 'e'}; + + this->pipeTest(Test, Exp, views::drop(4) | views::reverse); + } + + // reverse | drop + { + char Exp[]{'c', 'b', 'a'}; + + this->pipeTest(Test, Exp, views::reverse | views::drop(4)); + } + + // drop | drop + { + char Exp[]{'d', 'e', 'f', 'g'}; + + this->pipeTest(Test, Exp, views::drop(2) | views::drop(1)); + } + + // drop | take | reverse + { + char Exp[]{'e', 'd', 'c'}; + + this->pipeTest(Test, Exp, views::drop(2) | views::take(3) | views::reverse); + } + + // reverse | drop | take + { + char Exp[]{'e', 'd', 'c'}; + + this->pipeTest(Test, Exp, views::reverse | views::drop(2) | views::take(3)); + } + + // drop (larger than input) + { + EXPECT_TRUE((Test | views::drop(100)).empty()); + + // Copy Range to a Container. + auto Container = Test | views::drop(100) | to(); + + EXPECT_TRUE(Container.empty()); + Container.clear(); + } + + // drop(0) + this->pipeTest(Test, Test, views::drop(0)); +} + +TYPED_TEST(RangesViewsTest, TakeWhileTest) { + char Test[]{'a', 'b', 'c', 'd', 'e', 'f', 'g'}; + + // take_while + { + char Exp[]{'a', 'b', 'c', 'd'}; + auto BeforeE = [](char X) { return X < 'e'; }; + + this->callTest(Test, Exp, views::take_while, BeforeE); + this->pipeTest(Test, Exp, views::take_while(BeforeE)); + } + + // take_while | take_while + { + char Exp[]{'a', 'b', 'c'}; + auto BeforeD = [](char X) { return X < 'd'; }; + auto BeforeE = [](char X) { return X < 'e'; }; + + this->pipeTest(Test, Exp, + views::take_while(BeforeE) | views::take_while(BeforeD)); + } + + // take_while (empty) + { + auto Nothing = [](char) { return false; }; + + this->pipeTest(Test, makeArrayRef(Test).take_front(0), + views::take_while(Nothing)); + } + + // take_while (Everything) + { + auto Everything = [](char) { return true; }; + + this->pipeTest(Test, Test, views::take_while(Everything)); + } +} + +TYPED_TEST(RangesViewsTest, DropWhileTest) { + char Test[]{'a', 'b', 'c', 'd', 'e', 'f', 'g'}; + + // views::drop_while (operator()) + { + char Exp[]{'c', 'd', 'e', 'f', 'g'}; + auto AfterB = [](char C) { return C <= 'b'; }; + + this->callTest(Test, Exp, views::drop_while, AfterB); + this->pipeTest(Test, Exp, views::drop_while(AfterB)); + } + + // views::drop_while (empty) + { + auto Everything = [](char) { return true; }; + EXPECT_TRUE(empty(Test | views::drop_while(Everything))); + + // Copy range to a container. + auto Range = Test | views::drop_while(Everything); + auto Container = Range | to(); + + EXPECT_TRUE(Container.empty()); + Container.clear(); + } +} + +TEST(Ranges, EarlyIncTest) { + int Test[]{1, 3, 5, 7, 9, 11, 13, 15}; + auto GT9 = [](int X) { return X > 9; }; + auto LT9 = [](int X) { return X < 9; }; + + // std::list (operator()) + { + auto List = Test | to>(); + + std::list Tmp; + for (int &I : views::early_inc(List | views::take_while(LT9))) { + Tmp.push_back(I); + List.pop_front(); + } + + int ExpectedL[]{9, 11, 13, 15}; + int ExpectedTmp[]{1, 3, 5, 7}; + + EXPECT_EQ(ExpectedL, make_range(List)); + EXPECT_EQ(ExpectedTmp, make_range(Tmp)); + } + + // std::list (pipe) + { + auto List = Test | to>(); + + std::list Tmp; + for (int &I : List | views::take_while(LT9) | views::early_inc) { + Tmp.push_back(I); + List.pop_front(); + } + + int ExpectedVec[]{9, 11, 13, 15}; + int ExpectedTmp[]{1, 3, 5, 7}; + + EXPECT_EQ(ExpectedVec, make_range(List)); + EXPECT_EQ(ExpectedTmp, make_range(Tmp)); + } + + // SmallVector (reverse | take_while | early_inc) + { + auto Vec = Test | to>(); + + SmallVector Tmp; + for (int &I : + Vec | views::reverse | views::take_while(GT9) | views::early_inc) { + Tmp.emplace_back(I); + Vec.pop_back(); + } + + int ExpectedVec[]{1, 3, 5, 7, 9}; + int ExpectedTmp[]{15, 13, 11}; + + EXPECT_EQ(ExpectedVec, make_range(Vec)); + EXPECT_EQ(ExpectedTmp, make_range(Tmp)); + } +} + +template class RangesExtractTest : public RangesTestBase { +public: + using RangesTestBase::RangesTestBase; + + using ContainerT = C; + + template + void callTest(TestT const &TestIn, ExpT const &Exp, AdaptT &&Adapter, + Pn &&...Params) { + RangesTestBase::template callTest(TestIn, Exp, + std::forward(Adapter), + std::forward(Params)...); + } + + template + void pipeTest(TestT const &Test, ExpT const &Exp, AdaptT &&Adapter) const { + RangesTestBase::template pipeTest( + Test, Exp, std::forward(Adapter)); + } +}; + +// clang-format off +using ExtractTestTypes = + ::testing::Types< + SmallVector>, + SmallVector,NonTriv>>, + std::list>, + std::list,NonTriv>>, + std::vector>, + std::vector,NonTriv>>, + std::deque>, + std::deque,NonTriv>> + >; +// clang-format on + +TYPED_TEST_SUITE(RangesExtractTest, ExtractTestTypes, ); + +TYPED_TEST(RangesExtractTest, KeysTest) { + + std::pair Test[]{{1, 2}, {3, 4}, {5, 6}, {7, 8}, {9, 10}}; + + { + int Exp[]{1, 3, 5, 7, 9}; + + this->callTest(Test, Exp, views::keys); + this->pipeTest(Test, Exp, views::keys); + } +} + +TYPED_TEST(RangesExtractTest, ValuesTest) { + + std::pair Test[]{{1, 2}, {3, 4}, {5, 6}, {7, 8}, {9, 10}}; + + { + int Exp[]{2, 4, 6, 8, 10}; + + this->callTest(Test, Exp, views::values); + this->pipeTest(Test, Exp, views::values); + } +} + +TYPED_TEST(RangesExtractTest, ElementsTest) { + + std::tuple Test[]{{1, 2, 3}, {4, 5, 6}, {7, 8, 9}}; + + { + int Exp[]{3, 6, 9}; + + this->callTest(Test, Exp, views::elements<2>); + this->pipeTest(Test, Exp, views::elements<2>); + } +} + +// Ensure that transform views (keys, values & elements) properly return +// references and are capable of moving a range. +TEST(RangesTest, TransformMoveTest) { + using CInt = Counted; + { + std::pair Test[]{{1, 2}, {3, 4}, {5, 6}, {7, 8}, {9, 10}}; + + CInt::reset(); + auto List = make_range(std::make_move_iterator(std::begin(Test)), + std::make_move_iterator(std::end(Test))) | + views::keys | to>(); + + EXPECT_EQ(CInt::Construct, 0u); + EXPECT_EQ(CInt::Destroy, 0u); + EXPECT_EQ(CInt::Copy, 0u); + EXPECT_EQ(CInt::Move, List.size()); + EXPECT_EQ(CInt::CopyAssign, 0u); + EXPECT_EQ(CInt::MoveAssign, 0u); + + int Exp[]{1, 3, 5, 7, 9}; + EXPECT_EQ(Exp, make_range(List)); + } + + { + std::pair Test[]{{1, 2}, {3, 4}, {5, 6}, {7, 8}, {9, 10}}; + + CInt::reset(); + auto List = make_range(std::make_move_iterator(std::begin(Test)), + std::make_move_iterator(std::end(Test))) | + views::values | to>(); + + EXPECT_EQ(CInt::Construct, 0u); + EXPECT_EQ(CInt::Destroy, 0u); + EXPECT_EQ(CInt::Copy, 0u); + EXPECT_EQ(CInt::Move, List.size()); + EXPECT_EQ(CInt::CopyAssign, 0u); + EXPECT_EQ(CInt::MoveAssign, 0u); + + int Exp[]{2, 4, 6, 8, 10}; + EXPECT_EQ(Exp, make_range(List)); + } + + { + std::tuple Test[]{{1, 2, 3}, {4, 5, 6}, {7, 8, 9}}; + + CInt::reset(); + auto Vec = make_range(std::make_move_iterator(std::begin(Test)), + std::make_move_iterator(std::end(Test))) | + views::elements<2> | to>(); + + EXPECT_EQ(CInt::Construct, 0u); + EXPECT_EQ(CInt::Destroy, 0u); + EXPECT_EQ(CInt::Copy, 0u); + EXPECT_EQ(CInt::Move, Vec.size()); + EXPECT_EQ(CInt::CopyAssign, 0u); + EXPECT_EQ(CInt::MoveAssign, 0u); + + int Exp[]{3, 6, 9}; + EXPECT_EQ(Exp, make_range(Vec)); + } +} + +// Function. +bool isEvenFunc(int X) { return (X & 1) == 0; } +int truncEvenFunc(int X) { return X & ~1; } + +// Stateless lambda. +auto IsEvenLambda = [](int X) { return (X & 1) == 0; }; +auto TruncEvenLambda = [](int X) { return X & ~1; }; + +// Lambda with capture returned from function. +auto getIsEven() { + const int RHS = 1; + return [=](int X) { return (X & RHS) == 0; }; +} + +auto getTruncEven() { + const int RHS = 1; + return [=](int X) { return X & ~RHS; }; +} + +// Functor with state (not default constructible). +struct IsEvenFunctor { + // Add some state to the functor just to be tricky. + int Val; + + IsEvenFunctor(int V) : Val(V) {} + + bool operator()(int X) const { return (X & Val) == 0; } +}; + +struct TruncEvenFunctor { + // Add some state to the functor just to be tricky. + int Val; + + TruncEvenFunctor(int V) : Val(V) {} + + int operator()(int X) const { return X & ~Val; } +}; + +// Ensure that all different callables can be passed to transform, take_while +// and drop_while. +// +// Callables include: +// 1. Function reference +// 2. Function pointer +// 3. Functor +// 4. Lambda (stateless) +// 5. Lambda (with capture) +TEST(RangesTest, CallablesTest) { + + { + Callable FuncRef(isEvenFunc); + + auto Copy(FuncRef); + EXPECT_TRUE(Copy(2)); + EXPECT_FALSE(Copy(3)); + + auto Assign = FuncRef; + EXPECT_TRUE(Assign(2)); + EXPECT_FALSE(Assign(3)); + } + + { + Callable FuncPtr(&isEvenFunc); + + auto Copy(FuncPtr); + EXPECT_TRUE(Copy(2)); + EXPECT_FALSE(Copy(3)); + + auto Assign = FuncPtr; + EXPECT_TRUE(Assign(2)); + EXPECT_FALSE(Assign(3)); + } + + { + Callable RVLambda(getIsEven()); + + auto Copy(RVLambda); + EXPECT_TRUE(Copy(2)); + EXPECT_FALSE(Copy(3)); + + auto Assign = RVLambda; + EXPECT_TRUE(Assign(2)); + EXPECT_FALSE(Assign(3)); + } + + { + Callable LVLambda(IsEvenLambda); + + auto Copy(LVLambda); + EXPECT_TRUE(Copy(2)); + EXPECT_FALSE(Copy(3)); + + auto Assign = LVLambda; + EXPECT_TRUE(Assign(2)); + EXPECT_FALSE(Assign(3)); + } + + { + Callable Functor(IsEvenFunctor(1)); + + auto Copy(Functor); + EXPECT_TRUE(Copy(2)); + EXPECT_FALSE(Copy(3)); + + auto Assign = Functor; + EXPECT_TRUE(Assign(2)); + EXPECT_FALSE(Assign(3)); + } + + // take_while + { + int Test[]{2, 4, 6, 8, 1, 3, 5, 7, 9}; + int Exp[]{2, 4, 6, 8}; + + EXPECT_EQ(Exp, (Test | views::take_while(isEvenFunc))); + EXPECT_EQ(Exp, (Test | views::take_while(&isEvenFunc))); + EXPECT_EQ(Exp, (Test | views::take_while(getIsEven()))); + EXPECT_EQ(Exp, (Test | views::take_while(IsEvenLambda))); + EXPECT_EQ(Exp, (Test | views::take_while(IsEvenFunctor(1)))); + } + + // drop_while + { + int Test[]{2, 4, 6, 8, 1, 3, 5, 7, 9}; + int Exp[]{1, 3, 5, 7, 9}; + + EXPECT_EQ(Exp, (Test | views::drop_while(isEvenFunc))); + EXPECT_EQ(Exp, (Test | views::drop_while(&isEvenFunc))); + EXPECT_EQ(Exp, (Test | views::drop_while(getIsEven()))); + EXPECT_EQ(Exp, (Test | views::drop_while(IsEvenLambda))); + EXPECT_EQ(Exp, (Test | views::drop_while(IsEvenFunctor(1)))); + } + + // transform + { + int Test[]{1, 3, 5, 7, 9}; + int Exp[]{0, 2, 4, 6, 8}; + + EXPECT_EQ(Exp, (Test | views::transform(truncEvenFunc))); + EXPECT_EQ(Exp, (Test | views::transform(&truncEvenFunc))); + EXPECT_EQ(Exp, (Test | views::transform(getTruncEven()))); + EXPECT_EQ(Exp, (Test | views::transform(TruncEvenLambda))); + EXPECT_EQ(Exp, (Test | views::transform(TruncEvenFunctor(1)))); + } +} + +} // namespace