SERVER-43349 Skip double-$not during $elemMatch serialization

2 files changed, 181 insertions, 9 deletions

diff --git a/src/mongo/db/matcher/expression_array.cpp b/src/mongo/db/matcher/expression_array.cpp
index b1436c0345c..e775b512b99 100644
--- a/src/mongo/db/matcher/expression_array.cpp
+++ b/src/mongo/db/matcher/expression_array.cpp
@@ -182,6 +182,38 @@ void ElemMatchValueMatchExpression::debugString(StringBuilder& debug, int level)
     }
 }
 
+namespace {
+/**
+ * Helps consolidates double, triple, or more $nots into a single $not or zero $nots. Traverses the
+ * children of 'expr' to find the first child of a $not which is not a single-child $and or a $not.
+ * Returns that child and the number of $nots encountered along the way.
+ */
+std::pair<int, MatchExpression*> consolidateMultipleNotsAndGetChildOfNot(MatchExpression* expr) {
+    using MatchType = MatchExpression::MatchType;
+    invariant(expr->matchType() == MatchType::NOT);
+    int numberOfConsecutiveNots = 1;
+    expr = expr->getChild(0);
+
+    auto isSingleChildAndContainingANot = [](auto* expr) {
+        return expr->matchType() == MatchType::AND && expr->numChildren() == 1UL &&
+            expr->getChild(0)->matchType() == MatchType::NOT;
+    };
+    while (true) {
+        if (expr->matchType() == MatchType::NOT) {
+            expr = expr->getChild(0);
+            ++numberOfConsecutiveNots;
+        } else if (isSingleChildAndContainingANot(expr)) {
+            expr = expr->getChild(0);
+            invariant(expr->matchType() == MatchType::NOT);
+        } else {
+            // This expression is not a $not or an $and containing only a $not, so we're done.
+            break;
+        }
+    }
+    return {numberOfConsecutiveNots, expr};
+}
+}  // namespace
+
 void ElemMatchValueMatchExpression::serialize(BSONObjBuilder* out) const {
     BSONObjBuilder emBob;
 
@@ -189,9 +221,12 @@ void ElemMatchValueMatchExpression::serialize(BSONObjBuilder* out) const {
     // ElemMatchValue however as $nor is a top-level expression and expects that contained
     // expressions have path information. For this case we will serialize to $not.
     if (_subs.size() == 1 && _subs[0]->matchType() == MatchType::NOT) {
-        std::vector<MatchExpression*> childList{_subs[0]->getChild(0)};
+        int numberOfConsecutiveNots;
+        MatchExpression* notChildExpr;
+        std::tie(numberOfConsecutiveNots, notChildExpr) =
+            consolidateMultipleNotsAndGetChildOfNot(_subs[0]);
 
-        MatchExpression* notChildExpr = _subs[0]->getChild(0);
+        auto childList = std::vector<MatchExpression*>{notChildExpr};
         if (notChildExpr->matchType() == MatchType::AND) {
             childList = *notChildExpr->getChildVector();
         }
@@ -204,17 +239,18 @@ void ElemMatchValueMatchExpression::serialize(BSONObjBuilder* out) const {
         if (allChildrenArePathMatchExpression) {
             BSONObjBuilder pathBuilder(out->subobjStart(path()));
             BSONObjBuilder elemMatchBuilder(pathBuilder.subobjStart("$elemMatch"));
-            BSONObjBuilder notBuilder(elemMatchBuilder.subobjStart("$not"));
+            auto* builderForChildren = &elemMatchBuilder;
+            auto notBuilder = boost::optional<BSONObjBuilder>();
+            if (numberOfConsecutiveNots % 2 == 1) {
+                notBuilder.emplace(elemMatchBuilder.subobjStart("$not"));
+                builderForChildren = notBuilder.get_ptr();
+            }
 
             for (auto&& child : childList) {
                 BSONObjBuilder predicate;
                 child->serialize(&predicate);
-                notBuilder.appendElements(predicate.obj().firstElement().embeddedObject());
+                builderForChildren->appendElements(predicate.obj().firstElement().embeddedObject());
             }
-
-            notBuilder.doneFast();
-            elemMatchBuilder.doneFast();
-            pathBuilder.doneFast();
             return;
         }
     }
@@ -280,4 +316,4 @@ bool SizeMatchExpression::equivalent(const MatchExpression* other) const {
 
 
 // ------------------
-}
+}  // namespace mongo
diff --git a/src/mongo/db/matcher/expression_serialization_test.cpp b/src/mongo/db/matcher/expression_serialization_test.cpp
index b34afa725b4..5f042186084 100644
--- a/src/mongo/db/matcher/expression_serialization_test.cpp
+++ b/src/mongo/db/matcher/expression_serialization_test.cpp
@@ -301,6 +301,59 @@ TEST(SerializeBasic, ExpressionElemMatchValueWithNotLessThanGreaterThanSerialize
     ASSERT_EQ(original.matches(obj), reserialized.matches(obj));
 }
 
+TEST(SerializeBasic, ExpressionElemMatchValueWithDoubleNotSerializesCorrectly) {
+    boost::intrusive_ptr<ExpressionContextForTest> expCtx(new ExpressionContextForTest());
+    Matcher original(fromjson("{x: {$elemMatch: {$not: {$not: {$eq: 10}}}}}"),
+                     expCtx,
+                     ExtensionsCallbackNoop(),
+                     MatchExpressionParser::kAllowAllSpecialFeatures);
+    auto serialization = serialize(original.getMatchExpression());
+    ASSERT_BSONOBJ_EQ(serialization, fromjson("{x: {$elemMatch: {$eq: 10}}}"));
+    Matcher reserialized(serialization,
+                         expCtx,
+                         ExtensionsCallbackNoop(),
+                         MatchExpressionParser::kAllowAllSpecialFeatures);
+    ASSERT_BSONOBJ_EQ(*reserialized.getQuery(), fromjson("{x: {$elemMatch: {$eq: 10}}}"));
+    ASSERT_BSONOBJ_EQ(*reserialized.getQuery(), serialize(reserialized.getMatchExpression()));
+
+    auto obj = fromjson("{x: [10]}");
+    ASSERT_EQ(original.matches(obj), reserialized.matches(obj));
+}
+
+TEST(SerializeBasic, ExpressionElemMatchValueWithNotNESerializesCorrectly) {
+    boost::intrusive_ptr<ExpressionContextForTest> expCtx(new ExpressionContextForTest());
+    Matcher original(fromjson("{x: {$elemMatch: {$not: {$ne: 10}}}}"),
+                     expCtx,
+                     ExtensionsCallbackNoop(),
+                     MatchExpressionParser::kAllowAllSpecialFeatures);
+    Matcher reserialized(serialize(original.getMatchExpression()),
+                         expCtx,
+                         ExtensionsCallbackNoop(),
+                         MatchExpressionParser::kAllowAllSpecialFeatures);
+    ASSERT_BSONOBJ_EQ(*reserialized.getQuery(), fromjson("{x: {$elemMatch: {$eq: 10}}}"));
+    ASSERT_BSONOBJ_EQ(*reserialized.getQuery(), serialize(reserialized.getMatchExpression()));
+
+    auto obj = fromjson("{x: [10]}");
+    ASSERT_EQ(original.matches(obj), reserialized.matches(obj));
+}
+
+TEST(SerializeBasic, ExpressionElemMatchValueWithTripleNotSerializesCorrectly) {
+    boost::intrusive_ptr<ExpressionContextForTest> expCtx(new ExpressionContextForTest());
+    Matcher original(fromjson("{x: {$elemMatch: {$not: {$not: {$not: {$eq: 10}}}}}}"),
+                     expCtx,
+                     ExtensionsCallbackNoop(),
+                     MatchExpressionParser::kAllowAllSpecialFeatures);
+    Matcher reserialized(serialize(original.getMatchExpression()),
+                         expCtx,
+                         ExtensionsCallbackNoop(),
+                         MatchExpressionParser::kAllowAllSpecialFeatures);
+    ASSERT_BSONOBJ_EQ(*reserialized.getQuery(), fromjson("{x: {$elemMatch: {$not: {$eq: 10}}}}"));
+    ASSERT_BSONOBJ_EQ(*reserialized.getQuery(), serialize(reserialized.getMatchExpression()));
+
+    auto obj = fromjson("{x: [10]}");
+    ASSERT_EQ(original.matches(obj), reserialized.matches(obj));
+}
+
 TEST(SerializeBasic, ExpressionElemMatchObjectWithNorSerializesCorrectly) {
     boost::intrusive_ptr<ExpressionContextForTest> expCtx(new ExpressionContextForTest());
     Matcher original(fromjson("{x: {$elemMatch: {$nor: [{y: 2}]}}}"),
@@ -1055,6 +1108,89 @@ TEST(SerializeBasic, ExpressionNotWithGeoSerializesCorrectly) {
     ASSERT_EQ(original.matches(obj), reserialized.matches(obj));
 }
 
+TEST(SerializeBasic, ExpressionNotNotDirectlySerializesCorrectly) {
+    boost::intrusive_ptr<ExpressionContextForTest> expCtx(new ExpressionContextForTest());
+    // At the time of this writing, the MatchExpression parser does not ever create a NOT with a
+    // direct NOT child, instead creating a NOT -> AND -> NOT. This test manually constructs such an
+    // expression in case it ever turns up, since that should still be able to serialize to
+    // {$not: {$not: ...}}.
+    auto originalBSON = fromjson("{a: {$not: {$not: {$eq: 2}}}}");
+    auto equalityRHSElem = originalBSON["a"]["$not"]["$not"]["$eq"];
+    auto equalityExpression = std::make_unique<EqualityMatchExpression>();
+    ASSERT_OK(equalityExpression->init("a"_sd, equalityRHSElem));
+
+    auto nestedNot = std::make_unique<NotMatchExpression>(equalityExpression.release());
+    auto topNot = std::make_unique<NotMatchExpression>(nestedNot.release());
+    Matcher reserialized(serialize(topNot.get()),
+                         expCtx,
+                         ExtensionsCallbackNoop(),
+                         MatchExpressionParser::kAllowAllSpecialFeatures);
+    ASSERT_BSONOBJ_EQ(*reserialized.getQuery(), fromjson("{$nor: [{$nor: [{a: {$eq: 2}}]}]}"));
+
+    auto obj = fromjson("{a: 2}");
+    ASSERT_EQ(topNot->matchesBSON(obj), reserialized.matches(obj));
+}
+
+TEST(SerializeBasic, ExpressionNotWithoutPathChildrenSerializesCorrectly) {
+    // The grammar only permits a $not under a given path. For example, {a: {$not: {$eq: 4}}} is OK
+    // but {$not: {a: 4}} is not OK). However, we sometimes use the NOT MatchExpression to negate
+    // clauses within a JSONSchema. In such circumstances we need to be able to serialize the tree
+    // and re-parse it but the parser will reject the NOT in the place it's in. As a result, we need
+    // to translate the NOT to a $nor.
+
+    // MatchExpression tree expected:
+    //  {$or: [
+    //    {$and: [
+    //      {foo: {$_internalSchemaType: [2]}},
+    //      {foo: {$not: {
+    //        // This whole $or represents the {maxLength: 4}, since the restriction only applies if
+    //        // the element is the right type.
+    //        $or: [
+    //          {$_internalSchemaMaxLength: 4},
+    //          {foo: {$not: {$_internalSchemaType: [2]}}}
+    //        ]
+    //      }}}
+    //    ]},
+    //    {foo: {$not: {$exists: true}}}
+    //  ]}
+    BSONObj query =
+        fromjson("{$jsonSchema: {properties: {foo: {type: 'string', not: {maxLength: 4}}}}}");
+    boost::intrusive_ptr<ExpressionContextForTest> expCtx(new ExpressionContextForTest());
+    auto expression = unittest::assertGet(MatchExpressionParser::parse(query, expCtx));
+
+    Matcher reserialized(serialize(expression.get()),
+                         expCtx,
+                         ExtensionsCallbackNoop(),
+                         MatchExpressionParser::kAllowAllSpecialFeatures);
+
+    ASSERT_BSONOBJ_EQ(*reserialized.getQuery(),
+                      fromjson("{$and: ["
+                               "  {$and: ["
+                               "    {$or: ["
+                               "      {$nor: [{foo: {$exists: true}}]},"
+                               "      {$and: ["
+                               "        {$nor: ["  // <-- This is the interesting part of this test.
+                               "          {$and: ["
+                               "            {$or: ["
+                               "              {$nor: [{foo: {$_internalSchemaType: [2]}}]},"
+                               "              {foo: {$_internalSchemaMaxLength: 4}}"
+                               "            ]}"
+                               "          ]}"
+                               "        ]},"
+                               "        {foo: {$_internalSchemaType: [2]}}"
+                               "      ]}"
+                               "    ]}"
+                               "  ]}"
+                               "]}"));
+    ASSERT_BSONOBJ_EQ(*reserialized.getQuery(), serialize(reserialized.getMatchExpression()));
+
+    BSONObj obj = fromjson("{foo: 'abc'}");
+    ASSERT_EQ(expression->matchesBSON(obj), reserialized.matches(obj));
+
+    obj = fromjson("{foo: 'acbdf'}");
+    ASSERT_EQ(expression->matchesBSON(obj), reserialized.matches(obj));
+}
+
 TEST(SerializeBasic, ExpressionNorSerializesCorrectly) {
     boost::intrusive_ptr<ExpressionContextForTest> expCtx(new ExpressionContextForTest());
     Matcher original(fromjson("{$nor: [{x: 3}, {x: {$lt: 1}}]}"),