[ADT] Add relation operators for Optional

[timshen]

Summary

Make Optional's behavior the same as the coming std::optional.

[dblaikie]

include/llvm/ADT/Optional.h

155

I'd probably just use if (X && Y) ? (similarly elsewhere)

unittests/ADT/OptionalTest.cpp

380

This seems to have lost the tests for comparison with NoneType (as distinct from the tests with Optional<T>s that are in the non-value state)

But in general - while this is obviously more compact than writing out all the tests explicitly, I wonder if there's a better pivot or other way we could write these tests to be more legible and/or more compact. Did you have any other ideas/things you attempted for testing? as a very rough sketch I'd probably start by wanting to have a test case/function per operator, then figure out how to factor the common functionality of those tests into utilities/helpers. Maybe templates..

[timshen]

Split testcases.

[timshen]

include/llvm/ADT/Optional.h

155

Done. For the context that enforces a cast, I used X.hasValue() instead of bool(X); in other cases I used implicit conversion.

[timshen]

Format.

[dblaikie]

Still trying to figure out how to make the test cases both short and legible - open to ideas, there's no need to take my suggestions as decree or anything.

unittests/ADT/OptionalTest.cpp

387–395

Nice way to get the extra coverage over the asymmetric comparisons!

407–410

I don't think we need to test this whole matrix. Looks like for the equality operator we only need 4 cases (each case containing the 5 cases the CheckOptRelations contains): {None, None}, {None, 3}, {3, None}, {3, 3}, {3, 4}). I'm not sure we need more even for the inequality operators, I think we get coverage for operator<, with say: {None, None}, {None, 3}, {3, None}, {3, 4}, {4, 3} - I suppose {3, 3}.

so, yeah, drop the top right and bottom left corners (because 4 and 3 are equivalent WRT None, but not WRT each other... )

Hmm, wonder what the best way to describe this is...

How would it look if we removed the loops from CheckOptRelations and it just took two Optionals, the relation (via the template parameter), and whether it should be true.

Then each test should consist of 5 lines that perhaps more clearly show the two operands, the operation, and the truthiness:

CheckOptRelations<EqualTo>(None, None, true);
CheckOptRelations<EqualTo>(None, Three, false);
CheckOptRelations<EqualTo>(Three, None, false);
CheckOptRelations<EqualTo>(Three, Three, true);
CheckOptRelations<EqualTo>(Three, Four, false);
CheckOptRelations<EqualTo>(Four, Three, false); // could skip this one when testing equality/inequality

Maybe it can be made more terse (just shorten the name of CheckOptRelations perhaps - it'll be used a lot in a short scope so should be pretty obvious what it does)

Does any of that seem better/reasonable?

I suppose alternatively the test utility could take the comparison once, then an initializer_list of {val, val, expected result} tuples (write a little struct to wrap them). Still ensures that the test cases are fairly self explanatory, which comparison is being tested and what result is expected.

[timshen]

unittests/ADT/OptionalTest.cpp

407–410

I don't think we need to test this whole matrix. Looks like for the equality operator we only need 4 cases (each case containing the 5 cases the CheckOptRelations contains): {None, None}, {None, 3}, {3, None}, {3, 3}, {3, 4}). I'm not sure we need more even for the inequality operators, I think we get coverage for operator<, with say: {None, None}, {None, 3}, {3, None}, {3, 4}, {4, 3} - I suppose {3, 3}.

Yeah I think 9 cases overlap each other a bit. I can remove duplicated cases, but then we (including the future readers) have to reason about the exhaustiveness of test cases in order to make sure of the coverage, where the 9 cases matrix is so obviously exhaustive.

In exhaustiveness's perspective your suggestion seems less comprehensible.

[dblaikie]

unittests/ADT/OptionalTest.cpp

407–410

For myself it raised the opposite question "what's all this testing - are there cases/complexities in the code that I hadn't seen"/"why are there so many 'interesting' cases here"?

Hmm, maybe we could simplify it a bit if we created a noisy type - ie: we shouldn't need to test {3, 3}, {3, 4}, etc... - that's just the underlying type's operator. If we test that it calls the underlying type's operator when both values are non-empty, that should be sufficient. Then we can test the None cases.

That'd still be all the 3 variants of each of {None, None}, {None, Something}, {Something, None}, {Something, Something}.

Happy to chat in person/IRC/pair program up some possible ways this might look - might be faster. (& maybe there's an existing similar ADT in LLVM & we could see how it tests such a matrix? (but my first few attempts to look - APInt/Float didn't find anything useful to draw a parallel from))

[timshen]

As discussed offline, hand craft mock objects to precisely test the std::optional specification.

[dblaikie]

This seems a bit more complicated than what we were discussing - perhaps it's for good reason. But to give a sense, this is sort of what I was picturing.

(some notes:

• I don't think it's worth checking that comparisons with None do not invoke the underlying type's comparison operators - yes, it's a possible bug, but seems like the sort of excess testing that's easy to fall into with mocking because we can
• did find one 'bug' in the implementation, op==(const T&, const Optional<T>&) inverted its arguments and called op==(const Optional<T>&, const T&) which isn't technically how it's spec'd, but one could argue the spec is overly narrow. I'm kind of OK 'fixing' that and having the test be a bit more narrow for simplicity...
• It's still annoying to have the EXPECT lines in another function since gtest doesn't give a backtrace on the EXPECT failure. But there's nothing really to be done about that short of writing out all the EXPECT lines, which seems lame/annoying/difficult/verbose/not worth it. But all the more reason that splitting this into one test per operator like this is at least a little helpful.)
  
  template <typename OperatorT, typename T> void CheckRelation(const Optional<T> &L, const Optional<T> &R, bool Expected) { EXPECT_EQ(Expected, OperatorT::apply(L, R));
  
  if (L) EXPECT_EQ(Expected, OperatorT::apply(*L, R)); else EXPECT_EQ(Expected, OperatorT::apply(None, R));
  
  if (R) EXPECT_EQ(Expected, OperatorT::apply(L, *R)); else EXPECT_EQ(Expected, OperatorT::apply(L, None)); }

struct EqualityMock {};

const Optional<EqualityMock> NoneEq, EqualityLhs((EqualityMock())),
    EqualityRhs((EqualityMock()));
bool IsEqual;

bool operator==(const EqualityMock &Lhs, const EqualityMock &Rhs) {
  EXPECT_EQ(&Lhs, &*EqualityLhs);
  EXPECT_EQ(&Rhs, &*EqualityRhs);
  return IsEqual;
}

TEST_F(OptionalTest, OperatorEqual) {
  CheckRelation<EqualTo>(NoneEq, NoneEq, true);
  CheckRelation<EqualTo>(NoneEq, EqualityLhs, false);
  CheckRelation<EqualTo>(EqualityLhs, NoneEq, false);

  IsEqual = false;
  CheckRelation<EqualTo>(EqualityLhs, EqualityRhs, false);
  IsEqual = true;
  CheckRelation<EqualTo>(EqualityLhs, EqualityRhs, true);
}

TEST_F(OptionalTest, OperatorNotEqual) {
  CheckRelation<NotEqualTo>(NoneEq, NoneEq, false);
  CheckRelation<NotEqualTo>(NoneEq, EqualityLhs, true);
  CheckRelation<NotEqualTo>(EqualityLhs, NoneEq, true);

  IsEqual = false;
  CheckRelation<NotEqualTo>(EqualityLhs, EqualityRhs, true);
  IsEqual = true;
  CheckRelation<NotEqualTo>(EqualityLhs, EqualityRhs, false);
}

struct InequalityMock { };

const Optional<InequalityMock> NoneIneq, InequalityLhs((InequalityMock())),
    InequalityRhs((InequalityMock()));
bool IsLess;

bool operator<(const InequalityMock &Lhs, const InequalityMock &Rhs) {
  EXPECT_EQ(&Lhs, &*InequalityLhs);
  EXPECT_EQ(&Rhs, &*InequalityRhs);
  return IsLess;
}

TEST_F(OptionalTest, OperatorLess) {
  CheckRelation<Less>(NoneIneq, NoneIneq, false);
  CheckRelation<Less>(NoneIneq, InequalityRhs, true);
  CheckRelation<Less>(InequalityLhs, NoneIneq, false);

  IsLess = false;
  CheckRelation<Less>(InequalityLhs, InequalityRhs, false);
  IsLess = true;
  CheckRelation<Less>(InequalityLhs, InequalityRhs, true);
}

TEST_F(OptionalTest, OperatorGreater) {
  CheckRelation<Greater>(NoneIneq, NoneIneq, false);
  CheckRelation<Greater>(NoneIneq, InequalityRhs, false);
  CheckRelation<Greater>(InequalityLhs, NoneIneq, true);

  IsLess = false;
  CheckRelation<Greater>(InequalityRhs, InequalityLhs, false);
  IsLess = true;
  CheckRelation<Greater>(InequalityRhs, InequalityLhs, true);
}

TEST_F(OptionalTest, OperatorLessEqual) {
  CheckRelation<LessEqual>(NoneIneq, NoneIneq, true);
  CheckRelation<LessEqual>(NoneIneq, InequalityRhs, true);
  CheckRelation<LessEqual>(InequalityLhs, NoneIneq, false);

  IsLess = false;
  CheckRelation<LessEqual>(InequalityRhs, InequalityLhs, true);
  IsLess = true;
  CheckRelation<LessEqual>(InequalityRhs, InequalityLhs, false);
}

TEST_F(OptionalTest, OperatorGreaterEqual) {
  CheckRelation<GreaterEqual>(NoneIneq, NoneIneq, true);
  CheckRelation<GreaterEqual>(NoneIneq, InequalityRhs, false);
  CheckRelation<GreaterEqual>(InequalityLhs, NoneIneq, true);

  IsLess = false;
  CheckRelation<GreaterEqual>(InequalityLhs, InequalityRhs, true);
  IsLess = true;
  CheckRelation<GreaterEqual>(InequalityLhs, InequalityRhs, false);
}

[timshen]

Done.

I used non-literal for CheckRelation, e.g.
CheckRelation<Greater>(InequalityRhs, InequalityLhs, IsLess);

So that it seems more readable (read as Rhs is less then Lhs).

[dblaikie]

Fair enough - I felt like using the boolean literal rather than referring to the global made it a bit simpler/clearer (& consistent with the None cases). The operation is already mentioned in the template parameter. But yeah - nothing's great here, totally up to you.

[timshen]

The operation is already mentioned in the template parameter.

This is why it's closer to what we want to test - "Greater operator on Lhs and Rhs" is equivalent to "Rhs is less then Lhs".

[timshen]

Thanks for the review!

include/llvm/ADT/Optional.h

 };
 
 template <typename T> struct isPodLike;
 template <typename T> struct isPodLike<Optional<T> > {
   // An Optional<T> is pod-like if T is.
   static const bool value = isPodLike<T>::value;
 };
 
-/// \brief Poison comparison between two \c Optional objects. Clients needs to
-/// explicitly compare the underlying values and account for empty \c Optional
-/// objects.
-///
-/// This routine will never be defined. It returns \c void to help diagnose
-/// errors at compile time.
-template<typename T, typename U>
-void operator==(const Optional<T> &X, const Optional<U> &Y);
+template <typename T, typename U>
+bool operator==(const Optional<T> &X, const Optional<U> &Y) {
+  if (X.hasValue() && Y.hasValue())
+    return *X == *Y;
+  return X.hasValue() == Y.hasValue();
+}
+
+template <typename T, typename U>
+bool operator!=(const Optional<T> &X, const Optional<U> &Y) {
+  return !(X == Y);
+}
+
+template <typename T, typename U>
+bool operator<(const Optional<T> &X, const Optional<U> &Y) {
+  if (X.hasValue() && Y.hasValue())
+    return *X < *Y;
+  return X.hasValue() < Y.hasValue();
+}
+
+template <typename T, typename U>
+bool operator<=(const Optional<T> &X, const Optional<U> &Y) {
+  return !(Y < X);
+}
+
+template <typename T, typename U>
+bool operator>(const Optional<T> &X, const Optional<U> &Y) {
+  return Y < X;
+}
+
+template <typename T, typename U>
+bool operator>=(const Optional<T> &X, const Optional<U> &Y) {
+  return !(X < Y);
+}
 
 template<typename T>
 bool operator==(const Optional<T> &X, NoneType) {
   return !X.hasValue();
 }
 
 template<typename T>
 bool operator==(NoneType, const Optional<T> &X) {
   return X == None;
 }
 
 template<typename T>
 bool operator!=(const Optional<T> &X, NoneType) {
   return !(X == None);
 }
 
 template<typename T>
 bool operator!=(NoneType, const Optional<T> &X) {
   return X != None;
 }
-/// \brief Poison comparison between two \c Optional objects. Clients needs to
-/// explicitly compare the underlying values and account for empty \c Optional
-/// objects.
-///
-/// This routine will never be defined. It returns \c void to help diagnose
-/// errors at compile time.
-template<typename T, typename U>
-void operator!=(const Optional<T> &X, const Optional<U> &Y);
-
-/// \brief Poison comparison between two \c Optional objects. Clients needs to
-/// explicitly compare the underlying values and account for empty \c Optional
-/// objects.
-///
-/// This routine will never be defined. It returns \c void to help diagnose
-/// errors at compile time.
-template<typename T, typename U>
-void operator<(const Optional<T> &X, const Optional<U> &Y);
-
-/// \brief Poison comparison between two \c Optional objects. Clients needs to
-/// explicitly compare the underlying values and account for empty \c Optional
-/// objects.
-///
-/// This routine will never be defined. It returns \c void to help diagnose
-/// errors at compile time.
-template<typename T, typename U>
-void operator<=(const Optional<T> &X, const Optional<U> &Y);
-
-/// \brief Poison comparison between two \c Optional objects. Clients needs to
-/// explicitly compare the underlying values and account for empty \c Optional
-/// objects.
-///
-/// This routine will never be defined. It returns \c void to help diagnose
-/// errors at compile time.
-template<typename T, typename U>
-void operator>=(const Optional<T> &X, const Optional<U> &Y);
-
-/// \brief Poison comparison between two \c Optional objects. Clients needs to
-/// explicitly compare the underlying values and account for empty \c Optional
-/// objects.
-///
-/// This routine will never be defined. It returns \c void to help diagnose
-/// errors at compile time.
-template<typename T, typename U>
-void operator>(const Optional<T> &X, const Optional<U> &Y);
+
+template <typename T> bool operator<(const Optional<T> &X, NoneType) {
+  return false;
+}
+
+template <typename T> bool operator<(NoneType, const Optional<T> &X) {
+  return X.hasValue();
+}
+
+template <typename T> bool operator<=(const Optional<T> &X, NoneType) {
+  return !(None < X);
+}
+
+template <typename T> bool operator<=(NoneType, const Optional<T> &X) {
+  return !(X < None);
+}
+
+template <typename T> bool operator>(const Optional<T> &X, NoneType) {
+  return None < X;
+}
+
+template <typename T> bool operator>(NoneType, const Optional<T> &X) {
+  return X < None;
+}
+
+template <typename T> bool operator>=(const Optional<T> &X, NoneType) {
+  return None <= X;
+}
+
+template <typename T> bool operator>=(NoneType, const Optional<T> &X) {
+  return X <= None;
+}
+
+template <typename T> bool operator==(const Optional<T> &X, const T &Y) {
+  return X.hasValue() && *X == Y;
+}
+
+template <typename T> bool operator==(const T &X, const Optional<T> &Y) {
+  return Y == X;
+}
+
+template <typename T> bool operator!=(const Optional<T> &X, const T &Y) {
+  return !(X == Y);
+}
+
+template <typename T> bool operator!=(const T &X, const Optional<T> &Y) {
+  return !(X == Y);
+}
+
+template <typename T> bool operator<(const Optional<T> &X, const T &Y) {
+  return !X.hasValue() || *X < Y;
+}
+
+template <typename T> bool operator<(const T &X, const Optional<T> &Y) {
+  return Y.hasValue() && X < *Y;
+}
+
+template <typename T> bool operator<=(const Optional<T> &X, const T &Y) {
+  return !(Y < X);
+}
+
+template <typename T> bool operator<=(const T &X, const Optional<T> &Y) {
+  return !(Y < X);
+}
+
+template <typename T> bool operator>(const Optional<T> &X, const T &Y) {
+  return Y < X;
+}
+
+template <typename T> bool operator>(const T &X, const Optional<T> &Y) {
+  return Y < X;
+}
+
+template <typename T> bool operator>=(const Optional<T> &X, const T &Y) {
+  return !(X < Y);
+}
+
+template <typename T> bool operator>=(const T &X, const Optional<T> &Y) {
+  return !(X < Y);
+}
 
 } // end llvm namespace
 
 #endif

unittests/ADT/OptionalTest.cpp

TEST_F(OptionalTest, MoveGetValueOr) {
   EXPECT_EQ(5, std::move(A).getValueOr(MoveOnly(42)).val);
   EXPECT_EQ(1u, MoveOnly::MoveConstructions);
   EXPECT_EQ(0u, MoveOnly::MoveAssignments);
   EXPECT_EQ(2u, MoveOnly::Destructions);
 }
 
 #endif // LLVM_HAS_RVALUE_REFERENCE_THIS
 
-TEST_F(OptionalTest, NoneComparison) {
-  Optional<int> o;
-  EXPECT_EQ(o, None);
-  EXPECT_EQ(None, o);
-  EXPECT_FALSE(o != None);
-  EXPECT_FALSE(None != o);
-  o = 3;
-  EXPECT_FALSE(o == None);
-  EXPECT_FALSE(None == o);
-  EXPECT_TRUE(o != None);
-  EXPECT_TRUE(None != o);
+TEST_F(OptionalTest, Comparisonn) {
+  Optional<int> Opts[] = {None, 3, 4};
+
+  //      None 3 4
+  // None    = < <
+  //    3    > = <
+  //    4    > > =
+  int Results[3][3] = {
+    { 0, -1, -1 },
+    { 1,  0, -1 },
+    { 1,  1,  0 },
+  };
+
+  for (int i = 0; i < 3; i++) {
+    for (int j = 0; j < 3; j++) {
+      switch (Results[i][j]) {
+      case -1:
+        EXPECT_FALSE(Opts[i] == Opts[j]);
+        EXPECT_TRUE(Opts[i] != Opts[j]);
+        EXPECT_TRUE(Opts[i] < Opts[j]);
+        EXPECT_FALSE(Opts[i] > Opts[j]);
+        EXPECT_TRUE(Opts[i] <= Opts[j]);
+        EXPECT_FALSE(Opts[i] >= Opts[j]);
+        if (Opts[i].hasValue()) {
+          EXPECT_FALSE(*Opts[i] == Opts[j]);
+          EXPECT_TRUE(*Opts[i] != Opts[j]);
+          EXPECT_TRUE(*Opts[i] < Opts[j]);
+          EXPECT_FALSE(*Opts[i] > Opts[j]);
+          EXPECT_TRUE(*Opts[i] <= Opts[j]);
+          EXPECT_FALSE(*Opts[i] >= Opts[j]);
+        }
+        if (Opts[j].hasValue()) {
+          EXPECT_FALSE(Opts[i] == *Opts[j]);
+          EXPECT_TRUE(Opts[i] != *Opts[j]);
+          EXPECT_TRUE(Opts[i] < *Opts[j]);
+          EXPECT_FALSE(Opts[i] > *Opts[j]);
+          EXPECT_TRUE(Opts[i] <= *Opts[j]);
+          EXPECT_FALSE(Opts[i] >= *Opts[j]);
+        }
+        break;
+      case 0:
+        EXPECT_TRUE(Opts[i] == Opts[j]);
+        EXPECT_FALSE(Opts[i] != Opts[j]);
+        EXPECT_FALSE(Opts[i] < Opts[j]);
+        EXPECT_FALSE(Opts[i] > Opts[j]);
+        EXPECT_TRUE(Opts[i] <= Opts[j]);
+        EXPECT_TRUE(Opts[i] >= Opts[j]);
+        if (Opts[i].hasValue()) {
+          EXPECT_TRUE(*Opts[i] == Opts[j]);
+          EXPECT_FALSE(*Opts[i] != Opts[j]);
+          EXPECT_FALSE(*Opts[i] < Opts[j]);
+          EXPECT_FALSE(*Opts[i] > Opts[j]);
+          EXPECT_TRUE(*Opts[i] <= Opts[j]);
+          EXPECT_TRUE(*Opts[i] >= Opts[j]);
+        }
+        if (Opts[j].hasValue()) {
+          EXPECT_TRUE(Opts[i] == *Opts[j]);
+          EXPECT_FALSE(Opts[i] != *Opts[j]);
+          EXPECT_FALSE(Opts[i] < *Opts[j]);
+          EXPECT_FALSE(Opts[i] > *Opts[j]);
+          EXPECT_TRUE(Opts[i] <= *Opts[j]);
+          EXPECT_TRUE(Opts[i] >= *Opts[j]);
+        }
+        break;
+      case 1:
+        EXPECT_FALSE(Opts[i] == Opts[j]);
+        EXPECT_TRUE(Opts[i] != Opts[j]);
+        EXPECT_FALSE(Opts[i] < Opts[j]);
+        EXPECT_TRUE(Opts[i] > Opts[j]);
+        EXPECT_FALSE(Opts[i] <= Opts[j]);
+        EXPECT_TRUE(Opts[i] >= Opts[j]);
+        if (Opts[i].hasValue()) {
+          EXPECT_FALSE(*Opts[i] == Opts[j]);
+          EXPECT_TRUE(*Opts[i] != Opts[j]);
+          EXPECT_FALSE(*Opts[i] < Opts[j]);
+          EXPECT_TRUE(*Opts[i] > Opts[j]);
+          EXPECT_FALSE(*Opts[i] <= Opts[j]);
+          EXPECT_TRUE(*Opts[i] >= Opts[j]);
+        }
+        if (Opts[j].hasValue()) {
+          EXPECT_FALSE(Opts[i] == *Opts[j]);
+          EXPECT_TRUE(Opts[i] != *Opts[j]);
+          EXPECT_FALSE(Opts[i] < *Opts[j]);
+          EXPECT_TRUE(Opts[i] > *Opts[j]);
+          EXPECT_FALSE(Opts[i] <= *Opts[j]);
+          EXPECT_TRUE(Opts[i] >= *Opts[j]);
+        }
+        break;
+      }
+    }
+  }
 }
 
 } // end anonymous namespace