[ADT] Add an early-increment iterator and range adaptor.

[chandlerc]

Summary

This allows us to model the common LLVM idiom of incrementing
immediately after dereferencing so that we can remove or update the
entity w/o losing our ability to reach the "next".

[chandlerc]

Update with actual documentation (instead of it being missing or talking about
the wrong thing) and a more direct implementation strategy.

Initially, I tried to make this behave more like a normal forward iterator.
Unfortunately, that makes it substantially less powerful than the
early-increment patterned loops we use throughout LLVM because it precludes the
current iterator from becoming invalid -- we compare against it when
incrementing.

Instead, this now directly models the early-increment loops in LLVM. It makes
it a weird quasi-iterator-like thing, despite claiming to be an InputIterator.
I'm not sure if people will be happy with this but it seems functional and to
work quite nicely with the way LLVM would want to use it.

[chandlerc]

Now with correct usage of the ABI breaking checks macro and fixing a silly
compile error.

[dblaikie]

Yeah, that's vaguely frightening as a thing (I mean, yeah, the assertions help catch misuse - but still).

Got a pointer to an example of where you want to do this? Any chance of inverting this into a lambda-driven algorithm instead, maybe?

pre_inc_for(R, [&](const auto &V) {
  ...
});

[chandlerc]

We have many, many for loops still using iterators for this....

If you search for thinsg like Foo &Var = *It++; with different
identifiers you will find a bunch.

I think we would be unsuccessful at converting them to lambda accepting
algorithms. The range based for loop seems likely the most we would succeed
in threading through how people think about this.... I mean, if there is no
consensus for this iterator-like thing, then maybe we have to go w/
algorithms. My fear is that it means we will just go with iterator for
loops.

[dblaikie]

Fair enough. An algorithm has issues with break/continue (well, continue can be easily transformed to 'return', though that can hinder readability, especially for long loop bodies where it's not immediately obvious that the return is from a lambda, rather than from the function as a whole) that this won't. Hopefully the assertions are enough to catch any particularly weird usage.

llvm/include/llvm/ADT/STLExtras.h

using FilterIteratorT =
       filter_iterator<detail::IterOfRange<RangeT>, PredicateT>;
   return make_range(
       FilterIteratorT(std::begin(std::forward<RangeT>(Range)),
                       std::end(std::forward<RangeT>(Range)), Pred),
       FilterIteratorT(std::end(std::forward<RangeT>(Range)),
                       std::end(std::forward<RangeT>(Range)), Pred));
 }
 
+/// An iterator adaptor that does an early increment of the iterator immediately
+/// after it is dereferenced.
+///
+template <typename WrappedIteratorT>
+class early_inc_iterator
+    : public iterator_adaptor_base<early_inc_iterator<WrappedIteratorT>,
+                                   WrappedIteratorT,
+                                   std::forward_iterator_tag> {
+  using BaseT =
+      iterator_adaptor_base<early_inc_iterator<WrappedIteratorT>,
+                            WrappedIteratorT, std::forward_iterator_tag>;
+
+  using PointerT = typename std::iterator_traits<WrappedIteratorT>::pointer;
+
+protected:
+  WrappedIteratorT NextI;
+
+public:
+  // Construct the iterator. The begin iterator needs to know where the end
+  // is, so that it can properly stop when it gets there. The end iterator only
+  // needs the predicate to support bidirectional iteration.
+  early_inc_iterator(WrappedIteratorT I) : BaseT(I), NextI(I) {}
+
+  using BaseT::operator*;
+  typename BaseT::reference operator*() {
+    // The first time we dereference the iterator, we know we're not at the end
+    // so we can compute the next iterator. We do this early (here), prior to
+    // any possible mutation of the sequence we are iterating over by the user
+    // after the reference to this node is returned.
+    if (this->I == NextI)
+      ++NextI;
+
+    return BaseT::operator*();
+  }
+
+  using BaseT::operator++;
+  early_inc_iterator &operator++() {
+    // If we haven't yet computed the next iterator, do so.
+    if (this->I == NextI)
+      ++NextI;
+
+    // And mark that this is now the current iterator.
+    this->I = NextI;
+    return *this;
+  }
+};
+
+template <typename RangeT>
+iterator_range<early_inc_iterator<detail::IterOfRange<RangeT>>>
+make_early_inc_range(RangeT &&Range) {
+  using EarlyIncIteratorT = early_inc_iterator<detail::IterOfRange<RangeT>>;
+  return make_range(EarlyIncIteratorT(std::begin(std::forward<RangeT>(Range))),
+                    EarlyIncIteratorT(std::end(std::forward<RangeT>(Range))));
+}
+
 // forward declarations required by zip_shortest/zip_first
 template <typename R, typename UnaryPredicate>
 bool all_of(R &&range, UnaryPredicate P);
 
 template <size_t... I> struct index_sequence;
 
 template <class... Ts> struct index_sequence_for;
 

llvm/unittests/ADT/STLExtrasTest.cpp

TEST(STLExtrasTest, ADLTest) {
   EXPECT_EQ(s.swap_val, "lhs");
   EXPECT_EQ(s2.swap_val, "rhs");
 
   int count = 0;
   llvm::for_each(s, [&count](int) { ++count; });
   EXPECT_EQ(5, count);
 }
 
+TEST(STLExtrasTest, EarlyIncrementTest) {
+  std::list<int> L = {1, 2, 3, 4};
+
+  auto EIR = make_early_inc_range(L);
+
+  auto I = EIR.begin();
+  auto EI = EIR.end();
+  EXPECT_NE(I, EI);
+
+  EXPECT_EQ(1, *I);
+  // Repeated dereferences work.
+  EXPECT_EQ(1, *I);
+
+  // Basic increment works, including repeated dereferences.
+  ++I;
+  EXPECT_NE(I, EI);
+  EXPECT_EQ(2, *I);
+  EXPECT_EQ(2, *I);
+
+  // Inserting shouldn't break anything. We should be able to keep dereferencing
+  // the currrent iterator and increment. The increment to go to the "next"
+  // iterator from before we inserted.
+  L.insert(std::next(L.begin(), 2), -1);
+  EXPECT_EQ(2, *I);
+  ++I;
+  EXPECT_EQ(3, *I);
+  EXPECT_EQ(3, *I);
+
+  // We should also be able to increment past something without looking at it.
+  ++I;
+  ++I;
+  EXPECT_EQ(EIR.end(), I);
+}
+
 } // namespace