[ADT] - Add llvm::make_mapped_range

[grimar]

Summary

This adds a helper for convenience to create mapped iterator ranges.

For use in D45166.

[dblaikie]

Seems fine to me

[• espindola]

LGTM too.

[arichardson]

include/llvm/ADT/STLExtras.h

208

Will using Optional here make lld slower with D45166 and a Release+Assertions build?
Can the compiler optimize away all the Optional assertions? Maybe using [F](ItTy It) { llvm_unreachable("end() derefeneced"); return F(It); } is easier to optimize?

[grimar]

include/llvm/ADT/STLExtras.h

208

I do not think LLD can be slower because of using Optional or even something slower than that here.
Speaking about D45166, the number of elements in loops where this is used is always small (we are iterating over linker script tree nodes there).

FWIW, filter_iterator also use Optional.

Also, I think David is right and it would not work.

[arichardson]

Seems like at -O2 clang 5.0.0 can optimize away all the optional checks (https://godbolt.org/g/rbGYrN)

[dblaikie]

Hah, wow - didn't know you could include LLVM headers in godbolt code...
that's super handy :D

[grimar]

Sorry, I am abandoning this. I think D45166 patch (for which this was written) will not be landed soon.
If anyone thinks this can be OK to land this one stand-alone for something, I'll be happy to do that.

include/llvm/ADT/STLExtras.h

class mapped_iterator
     : public iterator_adaptor_base<
              mapped_iterator<ItTy, FuncTy>, ItTy,
              typename std::iterator_traits<ItTy>::iterator_category,
              typename std::remove_reference<FuncReturnTy>::type> {
 public:
   mapped_iterator(ItTy U, FuncTy F)
     : mapped_iterator::iterator_adaptor_base(std::move(U)), F(std::move(F)) {}
 
+  // Constructor for the end iterator. Not dereferencable, hence no FuncTy.
+  mapped_iterator(ItTy U)
+      : mapped_iterator::iterator_adaptor_base(std::move(U)) {}
+
   ItTy getCurrent() { return this->I; }
 
-  FuncReturnTy operator*() { return F(*this->I); }
+  FuncReturnTy operator*() { return (*F)(*this->I); }
 
 private:
-  FuncTy F;
+  Optional<FuncTy> F;
 };
 
 // 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) {
   return mapped_iterator<ItTy, FuncTy>(std::move(I), std::move(F));
 }
 
+template <typename ItT, typename PredicateT>
+using mapped_iterator_range = iterator_range<mapped_iterator<ItT, PredicateT>>;
+
+/// Convenience function that takes a range of elements and a predicate,
+/// and return a new mapped_iterator range.
+template <typename RangeT, typename PredicateT>
+mapped_iterator_range<detail::IterOfRange<RangeT>, PredicateT>
+make_mapped_range(RangeT &&Range, PredicateT Pred) {
+  using MappedItT = mapped_iterator<detail::IterOfRange<RangeT>, PredicateT>;
+  auto I = MappedItT(std::begin(std::forward<RangeT>(Range)), std::move(Pred));
+  auto E = MappedItT(std::end(std::forward<RangeT>(Range)));
+  return make_range(I, E);
+}
+
 /// Helper to determine if type T has a member called rbegin().
 template <typename Ty> class has_rbegin_impl {
   using yes = char[1];
   using no = char[2];
 
   template <typename Inner>
   static yes& test(Inner *I, decltype(I->rbegin()) * = nullptr);
 

unittests/ADT/MappedIteratorTest.cpp

TEST(MappedIteratorTest, FunctionPreservesReferences) {
   std::map<int, int> M({ {1, 1} });
 
   auto I = map_iterator(V.begin(), [&](int X) -> int& { return M[X]; });
   *I = 42;
 
   EXPECT_EQ(M[1], 42) << "assignment should have modified M";
 }
 
+TEST(MappedIteratorTest, MappedRange) {
+  std::vector<int> V({0, 1, 2});
+
+  size_t I = 1;
+  for (int Val : make_mapped_range(V, [](int X) { return X + 1; }))
+    EXPECT_EQ(Val, I++) << "should have applied function in dereference";
+}
+
 } // anonymous namespace