Add missing operators for iterator_facade_base

[zturner]

Summary

We were missing operators required to allow calling std::distance, as well as an operator< to match the existing operator>.

[inglorion]

llvm/include/llvm/ADT/iterator.h

93

Do we have a test that exercises this code path? It seems to me that this would compute the negative of the value you want, but it could be that I'm misunderstanding something.

[zturner]

I actually removed the operator-, since it was not providing any value. All other base class operators are implemented in terms of a different operator on the derived class, so that you would get a hard error if the derived operator didn't exist. It was not possible to do this with the difference operator, and so at best if you failed to implement the operator in the derived class you would get a "recursive on all paths" warning, but not an error. Since you ultimately have to implement the same operator in the derived class *anyway*, the base class operator does not seem to provide any value.

The base class operator< stays though as it's still needed.

[chandlerc]

llvm/include/llvm/ADT/iterator.h

117–123

I don't get it...

This recurses through operator>, which recurses through operator<...

The derived class has to define one relational operator. Why can't we insist that it is always operator<? If it is, then the code you've added becomes dead...

[zturner]

llvm/include/llvm/ADT/iterator.h

117–123

Maybe the problem is just that the expectations of derived classes are not well documented. It's jarring to be looking through an interface and seeing 3 / 4 relational operators implemented, or not seeing the difference operator implemented and then trying to figure out if it's an oversight in the implementation, or if I'm expected to implement those. Would it be worth it trying to improve that documentation?

[chandlerc]

llvm/include/llvm/ADT/iterator.h

117–123

Yea, the set of operations the derived class is supposed to implement was discussed a bunch when this got written and seems to have never made it into comments. =[ Improving them would be fantastic.

Maybe also with pointers to example iterators in the unit tests that actually implement the canonical set of operations for a given iterator category?

llvm/include/llvm/ADT/iterator.h

DerivedT operator-(DifferenceTypeT n) const {
     DerivedT tmp = *static_cast<const DerivedT *>(this);
     tmp -= n;
     return tmp;
   }
 
   DerivedT &operator++() {
     return static_cast<DerivedT *>(this)->operator+=(1);
   }
   DerivedT operator++(int) {
     DerivedT tmp = *static_cast<DerivedT *>(this);
     ++*static_cast<DerivedT *>(this);
     return tmp;
   }
   DerivedT &operator--() {
     static_assert(
         IsBidirectional,
         "The decrement operator is only defined for bidirectional iterators.");
     return static_cast<DerivedT *>(this)->operator-=(1);
   }
   DerivedT operator--(int) {
     static_assert(
         IsBidirectional,
         "The decrement operator is only defined for bidirectional iterators.");
     DerivedT tmp = *static_cast<DerivedT *>(this);
     --*static_cast<DerivedT *>(this);
     return tmp;
   }
 
   bool operator!=(const DerivedT &RHS) const {
     return !static_cast<const DerivedT *>(this)->operator==(RHS);
   }
 
+  bool operator<(const DerivedT &RHS) const {
+    static_assert(
+        IsRandomAccess,
+        "Relational operators are only defined for random access iterators.");
+    return !static_cast<const DerivedT *>(this)->operator>(RHS) &&
+           !static_cast<const DerivedT *>(this)->operator==(RHS);
+  }
   bool operator>(const DerivedT &RHS) const {
     static_assert(
         IsRandomAccess,
         "Relational operators are only defined for random access iterators.");
     return !static_cast<const DerivedT *>(this)->operator<(RHS) &&
            !static_cast<const DerivedT *>(this)->operator==(RHS);
   }
   bool operator<=(const DerivedT &RHS) const {