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

(cherry picked from commit b5291b87ab3350bff9bd9ef4464a63dcda81ac21)

3 files changed, 232 insertions, 35 deletions

diff --git a/jstests/core/min_max_key.js b/jstests/core/min_max_key.js
new file mode 100644
index 00000000000..d65d68292fa
--- /dev/null
+++ b/jstests/core/min_max_key.js
@@ -0,0 +1,98 @@
+// Tests the behavior of queries using MinKey and MaxKey
+
+(function() {
+    "use strict";
+
+    load("jstests/aggregation/extras/utils.js");  // For 'resultsEq'.
+
+    const coll = db.test_min_max;
+    coll.drop();
+
+    const allElements = [
+        {_id: "a_max_key", a: MaxKey},
+        {_id: "a_min_key", a: MinKey},
+        {_id: "a_null", a: null},
+        {_id: "a_number", a: 4},
+        {_id: "a_subobject", a: {b: "hi"}},
+        {_id: "a_undefined", a: undefined},
+        {_id: "a_string", a: "hello"}
+    ];
+
+    assert.writeOK(coll.insert(allElements));
+
+    function testQueriesWithMinOrMaxKey() {
+        const eqMinRes = coll.find({a: {$eq: MinKey}}).toArray();
+        const expectedEqMin = [{_id: "a_min_key", a: MinKey}];
+        assert(resultsEq(expectedEqMin, eqMinRes), tojson(eqMinRes));
+
+        const gtMinRes = coll.find({a: {$gt: MinKey}}).toArray();
+        const expectedGtMin = [
+            {_id: "a_max_key", a: MaxKey},
+            {_id: "a_null", a: null},
+            {_id: "a_number", a: 4},
+            {_id: "a_subobject", a: {b: "hi"}},
+            {_id: "a_undefined", a: undefined},
+            {_id: "a_string", a: "hello"}
+        ];
+        assert(resultsEq(expectedGtMin, gtMinRes), tojson(gtMinRes));
+
+        const gteMinRes = coll.find({a: {$gte: MinKey}}).toArray();
+        assert(resultsEq(allElements, gteMinRes), tojson(gteMinRes));
+
+        const ltMinRes = coll.find({a: {$lt: MinKey}}).toArray();
+        assert(resultsEq([], ltMinRes), tojson(ltMinRes));
+
+        const lteMinRes = coll.find({a: {$lte: MinKey}}).toArray();
+        assert(resultsEq(expectedEqMin, lteMinRes), tojson(lteMinRes));
+
+        const eqMaxRes = coll.find({a: {$eq: MaxKey}}).toArray();
+        const expectedEqMax = [{_id: "a_max_key", a: MaxKey}];
+        assert(resultsEq(expectedEqMax, eqMaxRes), tojson(eqMaxRes));
+
+        const gtMaxRes = coll.find({a: {$gt: MaxKey}}).toArray();
+        assert(resultsEq([], gtMaxRes), tojson(gtMaxRes));
+
+        const gteMaxRes = coll.find({a: {$gte: MaxKey}}).toArray();
+        assert(resultsEq(expectedEqMax, gteMaxRes), tojson(gteMaxRes));
+
+        const ltMaxRes = coll.find({a: {$lt: MaxKey}}).toArray();
+        const expectedLtMax = [
+            {_id: "a_min_key", a: MinKey},
+            {_id: "a_null", a: null},
+            {_id: "a_number", a: 4},
+            {_id: "a_subobject", a: {b: "hi"}},
+            {_id: "a_undefined", a: undefined},
+            {_id: "a_string", a: "hello"}
+        ];
+        assert(resultsEq(expectedLtMax, ltMaxRes), tojson(ltMaxRes));
+
+        const lteMaxRes = coll.find({a: {$lte: MaxKey}}).toArray();
+        assert(resultsEq(allElements, lteMaxRes), tojson(lteMaxRes));
+    }
+
+    function testTypeBracketedQueries() {
+        // Queries that do not involve MinKey or MaxKey follow type bracketing and thus do not
+        // return MinKey or MaxKey as results. These queries are being run to test this
+        // functionality.
+        const numRes = coll.find({a: {$gt: 3}}).toArray();
+        const expectedNum = [{_id: "a_number", a: 4}];
+        assert(resultsEq(expectedNum, numRes), tojson(numRes));
+        const noNum = coll.find({a: {$lt: 3}}).toArray();
+        assert(resultsEq([], noNum), tojson(noNum));
+
+        const stringRes = coll.find({a: {$gt: "best"}}).toArray();
+        const expectedString = [{_id: "a_string", a: "hello"}];
+        assert(resultsEq(expectedString, stringRes), tojson(stringRes));
+    }
+
+    testQueriesWithMinOrMaxKey();
+    testTypeBracketedQueries();
+
+    assert.commandWorked(coll.createIndex({a: 1}));
+    // TODO: SERVER-35921 The results of the queries above should not change based on the
+    // presence of an index
+    assert.commandWorked(coll.dropIndexes());
+
+    testQueriesWithMinOrMaxKey();
+    testTypeBracketedQueries();
+}());
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) {