SERVER-18341 Matcher returns false positives in comparison predicates with MinKey/MaxKey

(cherry picked from commit b5291b87ab3350bff9bd9ef4464a63dcda81ac21)

2 files changed, 134 insertions, 35 deletions

diff --git a/src/mongo/db/matcher/expression_leaf.cpp b/src/mongo/db/matcher/expression_leaf.cpp
index 1ec48ed1f8e..f8d89ca2f04 100644
--- a/src/mongo/db/matcher/expression_leaf.cpp
+++ b/src/mongo/db/matcher/expression_leaf.cpp
@@ -117,14 +117,34 @@ ComparisonMatchExpression::ComparisonMatchExpression(MatchType type,
 bool ComparisonMatchExpression::matchesSingleElement(const BSONElement& e,
                                                      MatchDetails* details) const {
     if (e.canonicalType() != _rhs.canonicalType()) {
-        // some special cases
-        //  jstNULL and undefined are treated the same
+        // We can't call 'compareElements' on elements of different canonical types.  Usually
+        // elements with different canonical types should never match any comparison, but there are
+        // a few exceptions, handled here.
+
+        // jstNULL and undefined are treated the same
         if (e.canonicalType() + _rhs.canonicalType() == 5) {
             return matchType() == EQ || matchType() == LTE || matchType() == GTE;
         }
-
         if (_rhs.type() == MaxKey || _rhs.type() == MinKey) {
-            return matchType() != EQ;
+            switch (matchType()) {
+                // LT and LTE need no distinction here because the two elements that we are
+                // comparing do not even have the same canonical type and are thus not equal
+                // (i.e.the case where we compare MinKey against MinKey would not reach this switch
+                // statement at all).  The same reasoning follows for the lack of distinction
+                // between GTE and GT.
+                case LT:
+                case LTE:
+                    return _rhs.type() == MaxKey;
+                case EQ:
+                    return false;
+                case GT:
+                case GTE:
+                    return _rhs.type() == MinKey;
+                default:
+                    // This is a comparison match expression, so it must be either
+                    // a $lt, $lte, $gt, $gte, or equality expression.
+                    MONGO_UNREACHABLE;
+            }
         }
         return false;
     }
@@ -153,7 +173,6 @@ bool ComparisonMatchExpression::matchesSingleElement(const BSONElement& e,
 
     int x = BSONElement::compareElements(
         e, _rhs, BSONElement::ComparisonRules::kConsiderFieldName, _collator);
-
     switch (matchType()) {
         case LT:
             return x < 0;
diff --git a/src/mongo/db/matcher/expression_leaf_test.cpp b/src/mongo/db/matcher/expression_leaf_test.cpp
index 97bc324c5fd..20b94890bd6 100644
--- a/src/mongo/db/matcher/expression_leaf_test.cpp
+++ b/src/mongo/db/matcher/expression_leaf_test.cpp
@@ -166,18 +166,34 @@ TEST(EqOp, MatchesNestedNull) {
 TEST(EqOp, MatchesMinKey) {
     BSONObj operand = BSON("a" << MinKey);
     EqualityMatchExpression eq("a", operand["a"]);
-    ASSERT(eq.matchesBSON(BSON("a" << MinKey), NULL));
-    ASSERT(!eq.matchesBSON(BSON("a" << MaxKey), NULL));
-    ASSERT(!eq.matchesBSON(BSON("a" << 4), NULL));
+    BSONObj minKeyObj = BSON("a" << MinKey);
+    BSONObj maxKeyObj = BSON("a" << MaxKey);
+    BSONObj numObj = BSON("a" << 4);
+
+    ASSERT(eq.matchesBSON(minKeyObj, NULL));
+    ASSERT(!eq.matchesBSON(maxKeyObj, NULL));
+    ASSERT(!eq.matchesBSON(numObj, NULL));
+
+    ASSERT(eq.matchesSingleElement(minKeyObj.firstElement()));
+    ASSERT(!eq.matchesSingleElement(maxKeyObj.firstElement()));
+    ASSERT(!eq.matchesSingleElement(numObj.firstElement()));
 }
 
 
 TEST(EqOp, MatchesMaxKey) {
     BSONObj operand = BSON("a" << MaxKey);
     EqualityMatchExpression eq("a", operand["a"]);
-    ASSERT(eq.matchesBSON(BSON("a" << MaxKey), NULL));
-    ASSERT(!eq.matchesBSON(BSON("a" << MinKey), NULL));
-    ASSERT(!eq.matchesBSON(BSON("a" << 4), NULL));
+    BSONObj minKeyObj = BSON("a" << MinKey);
+    BSONObj maxKeyObj = BSON("a" << MaxKey);
+    BSONObj numObj = BSON("a" << 4);
+
+    ASSERT(!eq.matchesBSON(minKeyObj, NULL));
+    ASSERT(eq.matchesBSON(maxKeyObj, NULL));
+    ASSERT(!eq.matchesBSON(numObj, NULL));
+
+    ASSERT(!eq.matchesSingleElement(minKeyObj.firstElement()));
+    ASSERT(eq.matchesSingleElement(maxKeyObj.firstElement()));
+    ASSERT(!eq.matchesSingleElement(numObj.firstElement()));
 }
 
 TEST(EqOp, MatchesFullArray) {
@@ -314,17 +330,33 @@ TEST(LtOp, MatchesDotNotationNull) {
 TEST(LtOp, MatchesMinKey) {
     BSONObj operand = BSON("a" << MinKey);
     LTMatchExpression lt("a", operand["a"]);
-    ASSERT(!lt.matchesBSON(BSON("a" << MinKey), NULL));
-    ASSERT(!lt.matchesBSON(BSON("a" << MaxKey), NULL));
-    ASSERT(!lt.matchesBSON(BSON("a" << 4), NULL));
+    BSONObj minKeyObj = BSON("a" << MinKey);
+    BSONObj maxKeyObj = BSON("a" << MaxKey);
+    BSONObj numObj = BSON("a" << 4);
+
+    ASSERT(!lt.matchesBSON(minKeyObj, NULL));
+    ASSERT(!lt.matchesBSON(maxKeyObj, NULL));
+    ASSERT(!lt.matchesBSON(numObj, NULL));
+
+    ASSERT(!lt.matchesSingleElement(minKeyObj.firstElement()));
+    ASSERT(!lt.matchesSingleElement(maxKeyObj.firstElement()));
+    ASSERT(!lt.matchesSingleElement(numObj.firstElement()));
 }
 
 TEST(LtOp, MatchesMaxKey) {
     BSONObj operand = BSON("a" << MaxKey);
     LTMatchExpression lt("a", operand["a"]);
-    ASSERT(!lt.matchesBSON(BSON("a" << MaxKey), NULL));
-    ASSERT(lt.matchesBSON(BSON("a" << MinKey), NULL));
-    ASSERT(lt.matchesBSON(BSON("a" << 4), NULL));
+    BSONObj minKeyObj = BSON("a" << MinKey);
+    BSONObj maxKeyObj = BSON("a" << MaxKey);
+    BSONObj numObj = BSON("a" << 4);
+
+    ASSERT(lt.matchesBSON(minKeyObj, NULL));
+    ASSERT(!lt.matchesBSON(maxKeyObj, NULL));
+    ASSERT(lt.matchesBSON(numObj, NULL));
+
+    ASSERT(lt.matchesSingleElement(minKeyObj.firstElement()));
+    ASSERT(!lt.matchesSingleElement(maxKeyObj.firstElement()));
+    ASSERT(lt.matchesSingleElement(numObj.firstElement()));
 }
 
 TEST(LtOp, ElemMatchKey) {
@@ -412,17 +444,33 @@ TEST(LteOp, MatchesDotNotationNull) {
 TEST(LteOp, MatchesMinKey) {
     BSONObj operand = BSON("a" << MinKey);
     LTEMatchExpression lte("a", operand["a"]);
-    ASSERT(lte.matchesBSON(BSON("a" << MinKey), NULL));
-    ASSERT(!lte.matchesBSON(BSON("a" << MaxKey), NULL));
-    ASSERT(!lte.matchesBSON(BSON("a" << 4), NULL));
+    BSONObj minKeyObj = BSON("a" << MinKey);
+    BSONObj maxKeyObj = BSON("a" << MaxKey);
+    BSONObj numObj = BSON("a" << 4);
+
+    ASSERT(lte.matchesBSON(minKeyObj, NULL));
+    ASSERT(!lte.matchesBSON(maxKeyObj, NULL));
+    ASSERT(!lte.matchesBSON(numObj, NULL));
+
+    ASSERT(lte.matchesSingleElement(minKeyObj.firstElement()));
+    ASSERT(!lte.matchesSingleElement(maxKeyObj.firstElement()));
+    ASSERT(!lte.matchesSingleElement(numObj.firstElement()));
 }
 
 TEST(LteOp, MatchesMaxKey) {
     BSONObj operand = BSON("a" << MaxKey);
     LTEMatchExpression lte("a", operand["a"]);
-    ASSERT(lte.matchesBSON(BSON("a" << MaxKey), NULL));
-    ASSERT(lte.matchesBSON(BSON("a" << MinKey), NULL));
-    ASSERT(lte.matchesBSON(BSON("a" << 4), NULL));
+    BSONObj minKeyObj = BSON("a" << MinKey);
+    BSONObj maxKeyObj = BSON("a" << MaxKey);
+    BSONObj numObj = BSON("a" << 4);
+
+    ASSERT(lte.matchesBSON(minKeyObj, NULL));
+    ASSERT(lte.matchesBSON(maxKeyObj, NULL));
+    ASSERT(lte.matchesBSON(numObj, NULL));
+
+    ASSERT(lte.matchesSingleElement(minKeyObj.firstElement()));
+    ASSERT(lte.matchesSingleElement(maxKeyObj.firstElement()));
+    ASSERT(lte.matchesSingleElement(numObj.firstElement()));
 }
 
 
@@ -499,17 +547,33 @@ TEST(GtOp, MatchesDotNotationNull) {
 TEST(GtOp, MatchesMinKey) {
     BSONObj operand = BSON("a" << MinKey);
     GTMatchExpression gt("a", operand["a"]);
-    ASSERT(!gt.matchesBSON(BSON("a" << MinKey), NULL));
-    ASSERT(gt.matchesBSON(BSON("a" << MaxKey), NULL));
-    ASSERT(gt.matchesBSON(BSON("a" << 4), NULL));
+    BSONObj minKeyObj = BSON("a" << MinKey);
+    BSONObj maxKeyObj = BSON("a" << MaxKey);
+    BSONObj numObj = BSON("a" << 4);
+
+    ASSERT(!gt.matchesBSON(minKeyObj, NULL));
+    ASSERT(gt.matchesBSON(maxKeyObj, NULL));
+    ASSERT(gt.matchesBSON(numObj, NULL));
+
+    ASSERT(!gt.matchesSingleElement(minKeyObj.firstElement()));
+    ASSERT(gt.matchesSingleElement(maxKeyObj.firstElement()));
+    ASSERT(gt.matchesSingleElement(numObj.firstElement()));
 }
 
 TEST(GtOp, MatchesMaxKey) {
     BSONObj operand = BSON("a" << MaxKey);
     GTMatchExpression gt("a", operand["a"]);
-    ASSERT(!gt.matchesBSON(BSON("a" << MaxKey), NULL));
-    ASSERT(!gt.matchesBSON(BSON("a" << MinKey), NULL));
-    ASSERT(!gt.matchesBSON(BSON("a" << 4), NULL));
+    BSONObj minKeyObj = BSON("a" << MinKey);
+    BSONObj maxKeyObj = BSON("a" << MaxKey);
+    BSONObj numObj = BSON("a" << 4);
+
+    ASSERT(!gt.matchesBSON(minKeyObj, NULL));
+    ASSERT(!gt.matchesBSON(maxKeyObj, NULL));
+    ASSERT(!gt.matchesBSON(numObj, NULL));
+
+    ASSERT(!gt.matchesSingleElement(minKeyObj.firstElement()));
+    ASSERT(!gt.matchesSingleElement(maxKeyObj.firstElement()));
+    ASSERT(!gt.matchesSingleElement(numObj.firstElement()));
 }
 
 TEST(GtOp, ElemMatchKey) {
@@ -598,17 +662,33 @@ TEST(GteOp, MatchesDotNotationNull) {
 TEST(GteOp, MatchesMinKey) {
     BSONObj operand = BSON("a" << MinKey);
     GTEMatchExpression gte("a", operand["a"]);
-    ASSERT(gte.matchesBSON(BSON("a" << MinKey), NULL));
-    ASSERT(gte.matchesBSON(BSON("a" << MaxKey), NULL));
-    ASSERT(gte.matchesBSON(BSON("a" << 4), NULL));
+    BSONObj minKeyObj = BSON("a" << MinKey);
+    BSONObj maxKeyObj = BSON("a" << MaxKey);
+    BSONObj numObj = BSON("a" << 4);
+
+    ASSERT(gte.matchesBSON(minKeyObj, NULL));
+    ASSERT(gte.matchesBSON(maxKeyObj, NULL));
+    ASSERT(gte.matchesBSON(numObj, NULL));
+
+    ASSERT(gte.matchesSingleElement(minKeyObj.firstElement()));
+    ASSERT(gte.matchesSingleElement(maxKeyObj.firstElement()));
+    ASSERT(gte.matchesSingleElement(numObj.firstElement()));
 }
 
 TEST(GteOp, MatchesMaxKey) {
     BSONObj operand = BSON("a" << MaxKey);
     GTEMatchExpression gte("a", operand["a"]);
-    ASSERT(gte.matchesBSON(BSON("a" << MaxKey), NULL));
-    ASSERT(!gte.matchesBSON(BSON("a" << MinKey), NULL));
-    ASSERT(!gte.matchesBSON(BSON("a" << 4), NULL));
+    BSONObj minKeyObj = BSON("a" << MinKey);
+    BSONObj maxKeyObj = BSON("a" << MaxKey);
+    BSONObj numObj = BSON("a" << 4);
+
+    ASSERT(!gte.matchesBSON(minKeyObj, NULL));
+    ASSERT(gte.matchesBSON(maxKeyObj, NULL));
+    ASSERT(!gte.matchesBSON(numObj, NULL));
+
+    ASSERT(!gte.matchesSingleElement(minKeyObj.firstElement()));
+    ASSERT(gte.matchesSingleElement(maxKeyObj.firstElement()));
+    ASSERT(!gte.matchesSingleElement(numObj.firstElement()));
 }
 
 TEST(GteOp, ElemMatchKey) {