Index: include/llvm/ADT/STLExtras.h =================================================================== --- include/llvm/ADT/STLExtras.h +++ include/llvm/ADT/STLExtras.h @@ -231,33 +231,8 @@ struct has_rbegin : has_rbegin_impl::type> { }; -// Returns an iterator_range over the given container which iterates in reverse. -// Note that the container must have rbegin()/rend() methods for this to work. -template -auto reverse(ContainerTy &&C, - typename std::enable_if::value>::type * = - nullptr) -> decltype(make_range(C.rbegin(), C.rend())) { - return make_range(C.rbegin(), C.rend()); -} - -// Returns a std::reverse_iterator wrapped around the given iterator. -template -std::reverse_iterator make_reverse_iterator(IteratorTy It) { - return std::reverse_iterator(It); -} - -// Returns an iterator_range over the given container which iterates in reverse. -// Note that the container must have begin()/end() methods which return -// bidirectional iterators for this to work. -template -auto reverse( - ContainerTy &&C, - typename std::enable_if::value>::type * = nullptr) - -> decltype(make_range(llvm::make_reverse_iterator(std::end(C)), - llvm::make_reverse_iterator(std::begin(C)))) { - return make_range(llvm::make_reverse_iterator(std::end(C)), - llvm::make_reverse_iterator(std::begin(C))); -} +/// An empty base class used to identify filter iterators in metaprograms. +class filter_iterator_base {}; /// An iterator adaptor that filters the elements of given inner iterators. /// @@ -278,7 +253,8 @@ typename std::common_type< std::forward_iterator_tag, typename std::iterator_traits< - WrappedIteratorT>::iterator_category>::type> { + WrappedIteratorT>::iterator_category>::type>, + filter_iterator_base { using BaseT = iterator_adaptor_base< filter_iterator, WrappedIteratorT, typename std::common_type< @@ -311,8 +287,13 @@ // have to be engaged. filter_iterator(WrappedIteratorT End) : BaseT(End) {} + // Used to implement a predicate to check if an object is a filter_iterator. + template + friend struct is_filter_iterator; + public: using BaseT::operator++; + using BaseT::wrapped; filter_iterator &operator++() { BaseT::operator++(); @@ -323,8 +304,29 @@ template friend iterator_range, PT>> make_filter_range(RT &&, PT); + + /// Move the predicate out of the iterator. This invalidates the iterator. + PredicateT takePredicate() { + assert(Payload && "Cannot find the predicate"); + PredicateT P = std::move(Payload->Pred); + Payload = None; + return std::move(P); + } +}; + +/// Metafunction to determine if T is a filter iterator. +template struct is_filter_iterator { + static const bool value = std::is_base_of::value; }; +/// Returns an iterator_range over the given container which iterates in +/// reverse. Note that the container must have rbegin()/rend() methods for this +/// overload to be selected. +template +auto reverse(ContainerTy &&C) -> decltype(make_range(C.rbegin(), C.rend())) { + return make_range(C.rbegin(), C.rend()); +} + /// Convenience function that takes a range of elements and a predicate, /// and return a new filter_iterator range. /// @@ -343,6 +345,44 @@ FilterIteratorT(std::end(std::forward(Range)))); } +/// Returns a std::reverse_iterator wrapped around the given iterator. +template +std::reverse_iterator make_reverse_iterator(IteratorTy It) { + return std::reverse_iterator(It); +} + +/// Returns an iterator_range over the given container which iterates in +/// reverse. Note that the container must have begin()/end() methods which +/// return bidirectional iterators for overload to be selected. +template +auto reverse( + ContainerTy &&C, + typename std::enable_if< + !has_rbegin::value && + !is_filter_iterator::value>::type * = nullptr) + -> decltype(make_range(llvm::make_reverse_iterator(std::end(C)), + llvm::make_reverse_iterator(std::begin(C)))) { + return make_range(llvm::make_reverse_iterator(std::end(C)), + llvm::make_reverse_iterator(std::begin(C))); +} + +/// Returns an iterator_range over the given filtered range which iterates in +/// reverse. Note that this invalidates the input filtered range. +template +auto reverse( + FilteredRangeT &&R, + typename std::enable_if< + is_filter_iterator::value>::type * = nullptr) + -> decltype(make_filter_range( + make_range(llvm::make_reverse_iterator(R.end().wrapped()), + llvm::make_reverse_iterator(R.begin().wrapped())), + R.begin().takePredicate())) { + return make_filter_range( + make_range(llvm::make_reverse_iterator(R.end().wrapped()), + llvm::make_reverse_iterator(R.begin().wrapped())), + R.begin().takePredicate()); +} + // forward declarations required by zip_shortest/zip_first template bool all_of(R &&range, UnaryPredicate P); Index: unittests/ADT/IteratorTest.cpp =================================================================== --- unittests/ADT/IteratorTest.cpp +++ unittests/ADT/IteratorTest.cpp @@ -8,6 +8,7 @@ //===----------------------------------------------------------------------===// #include "llvm/ADT/iterator.h" +#include "llvm/ADT/ArrayRef.h" #include "llvm/ADT/STLExtras.h" #include "llvm/ADT/SmallVector.h" #include "gtest/gtest.h" @@ -196,6 +197,33 @@ EXPECT_EQ((SmallVector{1, 3, 5}), Actual); } +TEST(FilterIteratorTest, ReverseFilterRange) { + auto IsOdd = [](int N) { return N % 2 == 1; }; + int A[] = {0, 1, 2, 3, 4, 5, 6}; + + // Check basic reversal. + auto Range = reverse(make_filter_range(A, IsOdd)); + SmallVector Actual(Range.begin(), Range.end()); + EXPECT_EQ((SmallVector{5, 3, 1}), Actual); + + // Check that the reverse of the reverse is the original. + auto Range2 = reverse(reverse(make_filter_range(A, IsOdd))); + SmallVector Actual2(Range2.begin(), Range2.end()); + EXPECT_EQ((SmallVector{1, 3, 5}), Actual2); + + // Check empty ranges. + auto Range3 = reverse(make_filter_range(ArrayRef(), IsOdd)); + SmallVector Actual3(Range3.begin(), Range3.end()); + EXPECT_EQ((SmallVector{}), Actual3); + + // Check that we don't skip the first element, provided it isn't filtered + // away. + auto IsEven = [](int N) { return N % 2 == 0; }; + auto Range4 = reverse(make_filter_range(A, IsEven)); + SmallVector Actual4(Range4.begin(), Range4.end()); + EXPECT_EQ((SmallVector{6, 4, 2, 0}), Actual4); +} + TEST(PointerIterator, Basic) { int A[] = {1, 2, 3, 4}; pointer_iterator Begin(std::begin(A)), End(std::end(A)); Index: unittests/IR/BasicBlockTest.cpp =================================================================== --- unittests/IR/BasicBlockTest.cpp +++ unittests/IR/BasicBlockTest.cpp @@ -69,6 +69,15 @@ CI = BB->phis().begin(); EXPECT_NE(CI, BB->phis().end()); + // Test that filtering iterators work with basic blocks. + auto isPhi = [](Instruction &I) { return isa(&I); }; + auto Phis = make_filter_range(*BB, isPhi); + auto ReversedPhis = reverse(make_filter_range(*BB, isPhi)); + EXPECT_EQ(std::distance(Phis.begin(), Phis.end()), 3); + EXPECT_EQ(&*Phis.begin(), P1); + EXPECT_EQ(std::distance(ReversedPhis.begin(), ReversedPhis.end()), 3); + EXPECT_EQ(&*ReversedPhis.begin(), P3); + // And iterate a const range. for (const auto &PN : const_cast(BB.get())->phis()) { EXPECT_EQ(BB.get(), PN.getIncomingBlock(0));