[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

 
 #ifndef LLVM_ADT_STLEXTRAS_H
 #define LLVM_ADT_STLEXTRAS_H
 
 #include "llvm/ADT/Optional.h"
 #include "llvm/ADT/SmallVector.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>
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));
 }
 
+/// 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> {
+  using BaseT =
+      iterator_adaptor_base<early_inc_iterator_impl<WrappedIteratorT>,
+                            WrappedIteratorT, std::input_iterator_tag>;
+
+  using PointerT = typename std::iterator_traits<WrappedIteratorT>::pointer;
+
+protected:
+#if LLVM_ENABLE_ABI_BREAKING_CHECKS
+  bool IsEarlyIncremented = false;
+#endif
+
+public:
+  early_inc_iterator_impl(WrappedIteratorT I) : BaseT(I) {}
+
+  using BaseT::operator*;
+  typename BaseT::reference operator*() {
+#if LLVM_ENABLE_ABI_BREAKING_CHECKS
+    assert(!IsEarlyIncremented && "Cannot dereference twice!");
+    IsEarlyIncremented = true;
+#endif
+    return *(this->I)++;
+  }
+
+  using BaseT::operator++;
+  early_inc_iterator_impl &operator++() {
+#if LLVM_ENABLE_ABI_BREAKING_CHECKS
+    assert(IsEarlyIncremented && "Cannot increment before dereferencing!");
+    IsEarlyIncremented = false;
+#endif
+    return *this;
+  }
+
+  using BaseT::operator==;
+  bool operator==(const early_inc_iterator_impl &RHS) const {
+#if LLVM_ENABLE_ABI_BREAKING_CHECKS
+    assert(!IsEarlyIncremented && "Cannot compare after dereferencing!");
+#endif
+    return BaseT::operator==(RHS);
+  }
+};
+
+/// 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) {
+  using EarlyIncIteratorT =
+      early_inc_iterator_impl<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);
+#if LLVM_ENABLE_ABI_BREAKING_CHECKS
+#ifndef NDEBUG
+  // Repeated dereferences are not allowed.
+  EXPECT_DEATH(*I, "Cannot dereference");
+  // Comparison after dereference is not allowed.
+  EXPECT_DEATH((void)(I == EI), "Cannot compare");
+  EXPECT_DEATH((void)(I != EI), "Cannot compare");
+#endif
+#endif
+
+  ++I;
+  EXPECT_NE(I, EI);
+#if LLVM_ENABLE_ABI_BREAKING_CHECKS
+#ifndef NDEBUG
+  // You cannot increment prior to dereference.
+  EXPECT_DEATH(++I, "Cannot increment");
+#endif
+#endif
+  EXPECT_EQ(2, *I);
+#if LLVM_ENABLE_ABI_BREAKING_CHECKS
+#ifndef NDEBUG
+  // Repeated dereferences are not allowed.
+  EXPECT_DEATH(*I, "Cannot dereference");
+#endif
+#endif
+
+  // 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);
+  ++I;
+  EXPECT_EQ(3, *I);
+
+  // Erasing the front including the current doesn't break incrementing.
+  L.erase(L.begin(), std::prev(L.end()));
+  ++I;
+  EXPECT_EQ(4, *I);
+  ++I;
+  EXPECT_EQ(EIR.end(), I);
+}
+
 } // namespace