ADT: Add explicit conversions for reverse ilist iterators

[dexonsmith]

Summary

Add explicit conversions between forward and reverse ilist iterators.
These follow the conversion conventions of std::reverse_iterator, which
are off-by-one: the newly-constructed "reverse" iterator dereferences to
the previous node of the one sent in. This has the benefit of
converting reverse ranges in place:

• If [I, E) is a valid range,
• then [reverse(E), reverse(I)) gives the same range in reverse order.

ilist_iterator::getReverse() is unchanged: it returns a reverse iterator
to the *same* node.

Note: we should probably add some release notes for LLVM 4.0 around the
ilist changes, and I think it makes sense to have these conversions in
(and described there). There's been some debate about whether to keep,
delete, or rename getReverse(), but for now I'd just like to get the
explicit conversions in and we can decide later whether to make
getReverse() harder to access.

[dblaikie]

Seems (to my best understanding) this is necessary (there must be an iterator->reverse_iterator ctor that does the off-by-1 thing) and sufficient (it can/must be explicit) to meet the C++ standard "reversible container" requirements. (I was curious if 'explicit' was OK, seems it may be necessary - so, great!)

(some optional feedback on the testing - wrote it about one of the test cases, applies equally to the other)

llvm/unittests/ADT/IListIteratorTest.cpp

147–165

Is it necessary to test all these dimensions together? (I take it this is testing all conversions to/from reverse iterators, const (reverse) iterators, and begin/end, and one off begin, so that's 2 * 2 * 2 * 3.

Are some of these in useful equivalence classes that could be reduced down? (for example the const V non-const seems pretty orthogonal to the value set (begin/end/begin+1) - actually they all seem pretty orthogonal & so perhaps 2 + 2 + 2 + 3 test cases would suffice (or maybe even less if some of the tests cross equivalence classes)?)

168–173

static_assert instead?

[dexonsmith]

Thanks for the review! I made the suggested changes to the tests and committed in r294349.

llvm/include/llvm/ADT/ilist_iterator.h

public:
   // a nonconst iterator...
   template <bool RHSIsConst>
   typename std::enable_if<IsConst || !RHSIsConst, ilist_iterator &>::type
   operator=(const ilist_iterator<OptionsT, IsReverse, RHSIsConst> &RHS) {
     NodePtr = RHS.NodePtr;
     return *this;
   }
 
-  /// Convert from an iterator to its reverse.
+  /// Explicit conversion between forward/reverse iterators.
   ///
-  /// TODO: Roll this into the implicit constructor once we're sure that no one
-  /// is relying on the std::reverse_iterator off-by-one semantics.
+  /// Translate between forward and reverse iterators without changing range
+  /// boundaries.  The resulting iterator will dereference (and have a handle)
+  /// to the previous node, which is somewhat unexpected; but converting the
+  /// two endpoints in a range will give the same range in reverse.
+  ///
+  /// This matches std::reverse_iterator conversions.
+  explicit ilist_iterator(
+      const ilist_iterator<OptionsT, !IsReverse, IsConst> &RHS)
+      : ilist_iterator(++RHS.getReverse()) {}
+
+  /// Get a reverse iterator to the same node.
+  ///
+  /// Gives a reverse iterator that will dereference (and have a handle) to the
+  /// same node.  Converting the endpoint iterators in a range will give a
+  /// different range; for range operations, use the explicit conversions.
   ilist_iterator<OptionsT, !IsReverse, IsConst> getReverse() const {
     if (NodePtr)
       return ilist_iterator<OptionsT, !IsReverse, IsConst>(*NodePtr);
     return ilist_iterator<OptionsT, !IsReverse, IsConst>();
   }
 
   /// Const-cast.
   ilist_iterator<OptionsT, IsReverse, false> getNonConst() const {

llvm/include/llvm/CodeGen/MachineInstrBundleIterator.h

public:
   template <class OtherTy>
   MachineInstrBundleIterator(
       const MachineInstrBundleIterator<OtherTy, IsReverse> &I,
       typename std::enable_if<std::is_convertible<OtherTy *, Ty *>::value,
                               void *>::type = nullptr)
       : MII(I.getInstrIterator()) {}
   MachineInstrBundleIterator() : MII(nullptr) {}
 
+  /// Explicit conversion between forward/reverse iterators.
+  ///
+  /// Translate between forward and reverse iterators without changing range
+  /// boundaries.  The resulting iterator will dereference (and have a handle)
+  /// to the previous node, which is somewhat unexpected; but converting the
+  /// two endpoints in a range will give the same range in reverse.
+  ///
+  /// This matches std::reverse_iterator conversions.
+  explicit MachineInstrBundleIterator(
+      const MachineInstrBundleIterator<Ty, !IsReverse> &I)
+      : MachineInstrBundleIterator(++I.getReverse()) {}
+
   /// Get the bundle iterator for the given instruction's bundle.
   static MachineInstrBundleIterator getAtBundleBegin(instr_iterator MI) {
     return MachineInstrBundleIteratorHelper<IsReverse>::getBundleBegin(MI);
   }
 
   reference operator*() const { return *MII; }
   pointer operator->() const { return &operator*(); }
 
MachineInstrBundleIterator operator++(int) {
     ++*this;
     return Temp;
   }
 
   instr_iterator getInstrIterator() const { return MII; }
 
   nonconst_iterator getNonConstIterator() const { return MII.getNonConst(); }
 
+  /// Get a reverse iterator to the same node.
+  ///
+  /// Gives a reverse iterator that will dereference (and have a handle) to the
+  /// same node.  Converting the endpoint iterators in a range will give a
+  /// different range; for range operations, use the explicit conversions.
   reverse_iterator getReverse() const { return MII.getReverse(); }
 };
 
 } // end namespace llvm
 
 #endif

llvm/unittests/ADT/IListIteratorTest.cpp

TEST(IListIteratorTest, CheckEraseReverse) {
   auto RI = L.rbegin();
   EXPECT_EQ(&B, &*RI);
   L.remove(*RI++);
   EXPECT_EQ(&A, &*RI);
   L.remove(*RI++);
   EXPECT_EQ(L.rend(), RI);
 }
 
+TEST(IListIteratorTest, ReverseConstructor) {
+  simple_ilist<Node> L;
+  const simple_ilist<Node> &CL = L;
+  Node A, B;
+  L.insert(L.end(), A);
+  L.insert(L.end(), B);
+
+  // Save typing.
+  typedef simple_ilist<Node>::iterator iterator;
+  typedef simple_ilist<Node>::reverse_iterator reverse_iterator;
+  typedef simple_ilist<Node>::const_iterator const_iterator;
+  typedef simple_ilist<Node>::const_reverse_iterator const_reverse_iterator;
+
+  // Check explicit conversions.
+  EXPECT_EQ(++CL.begin(), const_iterator(++CL.rbegin()));
+  EXPECT_EQ(++CL.begin(), const_iterator(++L.rbegin()));
+  EXPECT_EQ(++CL.rbegin(), const_reverse_iterator(++CL.begin()));
+  EXPECT_EQ(++CL.rbegin(), const_reverse_iterator(++L.begin()));
+  EXPECT_EQ(++L.begin(), iterator(++L.rbegin()));
+  EXPECT_EQ(++L.rbegin(), reverse_iterator(++L.begin()));
+  EXPECT_EQ(CL.begin(), const_iterator(CL.rend()));
+  EXPECT_EQ(CL.begin(), const_iterator(L.rend()));
+  EXPECT_EQ(CL.end(), const_iterator(CL.rbegin()));
+  EXPECT_EQ(CL.end(), const_iterator(L.rbegin()));
+  EXPECT_EQ(CL.rbegin(), const_reverse_iterator(CL.end()));
+  EXPECT_EQ(CL.rbegin(), const_reverse_iterator(L.end()));
+  EXPECT_EQ(CL.rend(), const_reverse_iterator(CL.begin()));
+  EXPECT_EQ(CL.rend(), const_reverse_iterator(L.begin()));
+  EXPECT_EQ(L.begin(), iterator(L.rend()));
+  EXPECT_EQ(L.end(), iterator(L.rbegin()));
+  EXPECT_EQ(L.rbegin(), reverse_iterator(L.end()));
+  EXPECT_EQ(L.rend(), reverse_iterator(L.begin()));
+
+  // Confirm lack of implicit conversions.
+  EXPECT_FALSE((std::is_convertible<iterator, reverse_iterator>::value));
+  EXPECT_FALSE((std::is_convertible<reverse_iterator, iterator>::value));
+  EXPECT_FALSE(
+      (std::is_convertible<const_iterator, const_reverse_iterator>::value));
+  EXPECT_FALSE(
+      (std::is_convertible<const_reverse_iterator, const_iterator>::value));
+}
+
 } // end namespace

llvm/unittests/CodeGen/MachineInstrBundleIteratorTest.cpp

TEST(MachineInstrBundleIteratorTest, CompareToBundledMI) {
   ASSERT_TRUE(I != MBI.getIterator());
   ASSERT_TRUE(I != CMBI.getIterator());
   ASSERT_TRUE(MBI.getIterator() != CI);
   ASSERT_TRUE(CMBI.getIterator() != CI);
   ASSERT_TRUE(CI != MBI.getIterator());
   ASSERT_TRUE(CI != CMBI.getIterator());
 }
 
+struct MyUnbundledInstr
+    : ilist_node<MyUnbundledInstr, ilist_sentinel_tracking<true>> {
+  bool isBundledWithPred() const { return false; }
+  bool isBundledWithSucc() const { return false; }
+};
+typedef MachineInstrBundleIterator<MyUnbundledInstr> unbundled_iterator;
+typedef MachineInstrBundleIterator<const MyUnbundledInstr>
+    const_unbundled_iterator;
+typedef MachineInstrBundleIterator<MyUnbundledInstr, true>
+    reverse_unbundled_iterator;
+typedef MachineInstrBundleIterator<const MyUnbundledInstr, true>
+    const_reverse_unbundled_iterator;
+
+TEST(MachineInstrBundleIteratorTest, ReverseConstructor) {
+  simple_ilist<MyUnbundledInstr, ilist_sentinel_tracking<true>> L;
+  const auto &CL = L;
+  MyUnbundledInstr A, B;
+  L.insert(L.end(), A);
+  L.insert(L.end(), B);
+
+  // Save typing.
+  typedef MachineInstrBundleIterator<MyUnbundledInstr> iterator;
+  typedef MachineInstrBundleIterator<MyUnbundledInstr, true> reverse_iterator;
+  typedef MachineInstrBundleIterator<const MyUnbundledInstr> const_iterator;
+  typedef MachineInstrBundleIterator<const MyUnbundledInstr, true>
+      const_reverse_iterator;
+
+  // Convert to bundle iterators.
+  auto begin = [&]() -> iterator { return L.begin(); };
+  auto end = [&]() -> iterator { return L.end(); };
+  auto rbegin = [&]() -> reverse_iterator { return L.rbegin(); };
+  auto rend = [&]() -> reverse_iterator { return L.rend(); };
+  auto cbegin = [&]() -> const_iterator { return CL.begin(); };
+  auto cend = [&]() -> const_iterator { return CL.end(); };
+  auto crbegin = [&]() -> const_reverse_iterator { return CL.rbegin(); };
+  auto crend = [&]() -> const_reverse_iterator { return CL.rend(); };
+
+  // Check explicit conversions.
+  EXPECT_EQ(++cbegin(), const_iterator(++crbegin()));
+  EXPECT_EQ(++cbegin(), const_iterator(++rbegin()));
+  EXPECT_EQ(++crbegin(), const_reverse_iterator(++cbegin()));
+  EXPECT_EQ(++crbegin(), const_reverse_iterator(++begin()));
+  EXPECT_EQ(++begin(), iterator(++rbegin()));
+  EXPECT_EQ(++rbegin(), reverse_iterator(++begin()));
+  EXPECT_EQ(cbegin(), const_iterator(crend()));
+  EXPECT_EQ(cbegin(), const_iterator(rend()));
+  EXPECT_EQ(cend(), const_iterator(crbegin()));
+  EXPECT_EQ(cend(), const_iterator(rbegin()));
+  EXPECT_EQ(crbegin(), const_reverse_iterator(cend()));
+  EXPECT_EQ(crbegin(), const_reverse_iterator(end()));
+  EXPECT_EQ(crend(), const_reverse_iterator(cbegin()));
+  EXPECT_EQ(crend(), const_reverse_iterator(begin()));
+  EXPECT_EQ(begin(), iterator(rend()));
+  EXPECT_EQ(end(), iterator(rbegin()));
+  EXPECT_EQ(rbegin(), reverse_iterator(end()));
+  EXPECT_EQ(rend(), reverse_iterator(begin()));
+
+  // Confirm lack of implicit conversions.
+  EXPECT_FALSE((std::is_convertible<iterator, reverse_iterator>::value));
+  EXPECT_FALSE((std::is_convertible<reverse_iterator, iterator>::value));
+  EXPECT_FALSE(
+      (std::is_convertible<const_iterator, const_reverse_iterator>::value));
+  EXPECT_FALSE(
+      (std::is_convertible<const_reverse_iterator, const_iterator>::value));
+}
+
 } // end namespace