SERVER-29575: Add an $_internalSchemaXor MatchExpression

8 files changed, 316 insertions, 1 deletions

diff --git a/src/mongo/db/matcher/SConscript b/src/mongo/db/matcher/SConscript
index 192b8ebe96a..3b865fae670 100644
--- a/src/mongo/db/matcher/SConscript
+++ b/src/mongo/db/matcher/SConscript
@@ -46,6 +46,7 @@ env.Library(
         'matchable.cpp',
         'matcher.cpp',
         'schema/expression_internal_schema_num_array_items.cpp',
+        'schema/expression_internal_schema_xor.cpp',
     ],
     LIBDEPS=[
         '$BUILD_DIR/mongo/base',
@@ -67,6 +68,7 @@ env.CppUnitTest(
         'expression_tree_test.cpp',
         'schema/expression_internal_schema_max_items_test.cpp',
         'schema/expression_internal_schema_min_items_test.cpp',
+        'schema/expression_internal_schema_xor_test.cpp',
     ],
     LIBDEPS=[
         '$BUILD_DIR/mongo/db/query/collation/collator_interface_mock',
diff --git a/src/mongo/db/matcher/expression.h b/src/mongo/db/matcher/expression.h
index 292d82107f4..1607c81344b 100644
--- a/src/mongo/db/matcher/expression.h
+++ b/src/mongo/db/matcher/expression.h
@@ -55,6 +55,7 @@ public:
         // tree types
         AND,
         OR,
+        INTERNAL_SCHEMA_XOR,
 
         // array types
         ELEM_MATCH_OBJECT,
@@ -165,7 +166,8 @@ public:
      * AND, OR, NOT, NOR.
      */
     bool isLogical() const {
-        return AND == _matchType || OR == _matchType || NOT == _matchType || NOR == _matchType;
+        return AND == _matchType || OR == _matchType || NOT == _matchType || NOR == _matchType ||
+            INTERNAL_SCHEMA_XOR == _matchType;
     }
 
     /**
diff --git a/src/mongo/db/matcher/expression_algo.cpp b/src/mongo/db/matcher/expression_algo.cpp
index 292bf1f590a..97b5404badf 100644
--- a/src/mongo/db/matcher/expression_algo.cpp
+++ b/src/mongo/db/matcher/expression_algo.cpp
@@ -36,6 +36,7 @@
 #include "mongo/db/matcher/expression_array.h"
 #include "mongo/db/matcher/expression_leaf.h"
 #include "mongo/db/matcher/expression_tree.h"
+#include "mongo/db/matcher/schema/expression_internal_schema_xor.h"
 #include "mongo/db/pipeline/dependencies.h"
 #include "mongo/db/query/collation/collation_index_key.h"
 #include "mongo/db/query/collation/collator_interface.h"
@@ -274,6 +275,25 @@ unique_ptr<MatchExpression> createNorOfNodes(std::vector<unique_ptr<MatchExpress
     return std::move(splitNor);
 }
 
+/**
+ * Creates a MatchExpression that is equivalent to {$_internal_schema_xor: [children[0],
+ * children[1]...]}.
+ */
+unique_ptr<MatchExpression> createInternalSchemaXorOfNodes(
+    std::vector<unique_ptr<MatchExpression>>* children) {
+    if (children->empty()) {
+        return nullptr;
+    }
+
+    unique_ptr<InternalSchemaXorMatchExpression> splitInternalSchemaXor =
+        stdx::make_unique<InternalSchemaXorMatchExpression>();
+    for (auto&& expr : *children) {
+        splitInternalSchemaXor->add(expr.release());
+    }
+
+    return std::move(splitInternalSchemaXor);
+}
+
 void applyRenamesToExpression(MatchExpression* expr, const StringMap<std::string>& renames) {
     if (expr->isArray()) {
         return;
@@ -345,7 +365,9 @@ splitMatchExpressionByWithoutRenames(unique_ptr<MatchExpression> expr,
             }
             return {createNorOfNodes(&separate), createNorOfNodes(&reliant)};
         }
+
         case MatchExpression::OR:
+        case MatchExpression::INTERNAL_SCHEMA_XOR:
         case MatchExpression::NOT: {
             // If we aren't independent, we can't safely split.
             return {nullptr, std::move(expr)};
diff --git a/src/mongo/db/matcher/expression_parser.cpp b/src/mongo/db/matcher/expression_parser.cpp
index 6542d7ac68c..b9fa19e9e12 100644
--- a/src/mongo/db/matcher/expression_parser.cpp
+++ b/src/mongo/db/matcher/expression_parser.cpp
@@ -38,6 +38,7 @@
 #include "mongo/db/matcher/expression_tree.h"
 #include "mongo/db/matcher/schema/expression_internal_schema_max_items.h"
 #include "mongo/db/matcher/schema/expression_internal_schema_min_items.h"
+#include "mongo/db/matcher/schema/expression_internal_schema_xor.h"
 #include "mongo/db/namespace_string.h"
 #include "mongo/stdx/memory.h"
 #include "mongo/util/mongoutils/str.h"
@@ -335,6 +336,15 @@ StatusWithMatchExpression MatchExpressionParser::_parse(const BSONObj& obj,
                 if (!s.isOK())
                     return s;
                 root->add(temp.release());
+            } else if (mongoutils::str::equals("_internal_schema_xor", rest)) {
+                if (e.type() != Array)
+                    return {Status(ErrorCodes::BadValue, "$_internal_schema_xor must be an array")};
+                std::unique_ptr<InternalSchemaXorMatchExpression> temp =
+                    stdx::make_unique<InternalSchemaXorMatchExpression>();
+                Status s = _parseTreeList(e.Obj(), temp.get(), collator, childIsTopLevel);
+                if (!s.isOK())
+                    return s;
+                root->add(temp.release());
             } else if (mongoutils::str::equals("atomic", rest) ||
                        mongoutils::str::equals("isolated", rest)) {
                 if (!topLevel)
@@ -703,6 +713,7 @@ StatusWithMatchExpression MatchExpressionParser::_parseElemMatch(const char* nam
 
         isElemMatchValue = !mongoutils::str::equals("$and", elt.fieldName()) &&
             !mongoutils::str::equals("$nor", elt.fieldName()) &&
+            !mongoutils::str::equals("$_internal_schema_xor", elt.fieldName()) &&
             !mongoutils::str::equals("$or", elt.fieldName()) &&
             !mongoutils::str::equals("$where", elt.fieldName());
     }
diff --git a/src/mongo/db/matcher/schema/expression_internal_schema_xor.cpp b/src/mongo/db/matcher/schema/expression_internal_schema_xor.cpp
new file mode 100644
index 00000000000..42960334335
--- /dev/null
+++ b/src/mongo/db/matcher/schema/expression_internal_schema_xor.cpp
@@ -0,0 +1,76 @@
+// expression_tree.cpp
+
+/**
+ *    Copyright (C) 2013 10gen Inc.
+ *
+ *    This program is free software: you can redistribute it and/or  modify
+ *    it under the terms of the GNU Affero General Public License, version 3,
+ *    as published by the Free Software Foundation.
+ *
+ *    This program is distributed in the hope that it will be useful,
+ *    but WITHOUT ANY WARRANTY; without even the implied warranty of
+ *    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ *    GNU Affero General Public License for more details.
+ *
+ *    You should have received a copy of the GNU Affero General Public License
+ *    along with this program.  If not, see <http://www.gnu.org/licenses/>.
+ *
+ *    As a special exception, the copyright holders give permission to link the
+ *    code of portions of this program with the OpenSSL library under certain
+ *    conditions as described in each individual source file and distribute
+ *    linked combinations including the program with the OpenSSL library. You
+ *    must comply with the GNU Affero General Public License in all respects for
+ *    all of the code used other than as permitted herein. If you modify file(s)
+ *    with this exception, you may extend this exception to your version of the
+ *    file(s), but you are not obligated to do so. If you do not wish to do so,
+ *    delete this exception statement from your version. If you delete this
+ *    exception statement from all source files in the program, then also delete
+ *    it in the license file.
+ */
+
+#include "mongo/db/matcher/schema/expression_internal_schema_xor.h"
+
+#include "mongo/bson/bsonmisc.h"
+#include "mongo/bson/bsonobj.h"
+#include "mongo/bson/bsonobjbuilder.h"
+
+namespace mongo {
+
+bool InternalSchemaXorMatchExpression::matches(const MatchableDocument* doc,
+                                               MatchDetails* details) const {
+    bool found = false;
+    for (size_t i = 0; i < numChildren(); i++) {
+        if (getChild(i)->matches(doc, NULL)) {
+            if (found) {
+                return false;
+            }
+            found = true;
+        }
+    }
+    return found;
+}
+
+bool InternalSchemaXorMatchExpression::matchesSingleElement(const BSONElement& e) const {
+    bool found = false;
+    for (size_t i = 0; i < numChildren(); i++) {
+        if (getChild(i)->matchesSingleElement(e)) {
+            if (found) {
+                return false;
+            }
+            found = true;
+        }
+    }
+    return found;
+}
+
+void InternalSchemaXorMatchExpression::debugString(StringBuilder& debug, int level) const {
+    _debugAddSpace(debug, level);
+    debug << "$_internal_schema_xor\n";
+    _debugList(debug, level);
+}
+
+void InternalSchemaXorMatchExpression::serialize(BSONObjBuilder* out) const {
+    BSONArrayBuilder arrBob(out->subarrayStart("$_internal_schema_xor"));
+    _listToBSON(&arrBob);
+}
+}
diff --git a/src/mongo/db/matcher/schema/expression_internal_schema_xor.h b/src/mongo/db/matcher/schema/expression_internal_schema_xor.h
new file mode 100644
index 00000000000..b76109b4619
--- /dev/null
+++ b/src/mongo/db/matcher/schema/expression_internal_schema_xor.h
@@ -0,0 +1,63 @@
+/**
+ *    Copyright (C) 2017 MongoDB Inc.
+ *
+ *    This program is free software: you can redistribute it and/or  modify
+ *    it under the terms of the GNU Affero General Public License, version 3,
+ *    as published by the Free Software Foundation.
+ *
+ *    This program is distributed in the hope that it will be useful,
+ *    but WITHOUT ANY WARRANTY; without even the implied warranty of
+ *    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ *    GNU Affero General Public License for more details.
+ *
+ *    You should have received a copy of the GNU Affero General Public License
+ *    along with this program.  If not, see <http://www.gnu.org/licenses/>.
+ *
+ *    As a special exception, the copyright holders give permission to link the
+ *    code of portions of this program with the OpenSSL library under certain
+ *    conditions as described in each individual source file and distribute
+ *    linked combinations including the program with the OpenSSL library. You
+ *    must comply with the GNU Affero General Public License in all respects for
+ *    all of the code used other than as permitted herein. If you modify file(s)
+ *    with this exception, you may extend this exception to your version of the
+ *    file(s), but you are not obligated to do so. If you do not wish to do so,
+ *    delete this exception statement from your version. If you delete this
+ *    exception statement from all source files in the program, then also delete
+ *    it in the license file.
+ */
+
+#pragma once
+
+#include "mongo/db/matcher/expression_tree.h"
+
+namespace mongo {
+
+/**
+ * MatchExpression for $_internalSchemaXor keyword. Takes an integer argument that indicates
+ * the maximum amount of elements in an array.
+ */
+class InternalSchemaXorMatchExpression : public ListOfMatchExpression {
+public:
+    InternalSchemaXorMatchExpression() : ListOfMatchExpression(INTERNAL_SCHEMA_XOR) {}
+    virtual ~InternalSchemaXorMatchExpression() {}
+
+    virtual bool matches(const MatchableDocument* doc, MatchDetails* details = 0) const;
+    virtual bool matchesSingleElement(const BSONElement& e) const;
+
+    virtual std::unique_ptr<MatchExpression> shallowClone() const {
+        std::unique_ptr<InternalSchemaXorMatchExpression> self =
+            stdx::make_unique<InternalSchemaXorMatchExpression>();
+        for (size_t i = 0; i < numChildren(); ++i) {
+            self->add(getChild(i)->shallowClone().release());
+        }
+        if (getTag()) {
+            self->setTag(getTag()->clone());
+        }
+        return std::move(self);
+    }
+
+    virtual void debugString(StringBuilder& debug, int level = 0) const;
+
+    virtual void serialize(BSONObjBuilder* out) const;
+};
+}  // namespace mongo
\ No newline at end of file
diff --git a/src/mongo/db/matcher/schema/expression_internal_schema_xor_test.cpp b/src/mongo/db/matcher/schema/expression_internal_schema_xor_test.cpp
new file mode 100644
index 00000000000..d1bb8328364
--- /dev/null
+++ b/src/mongo/db/matcher/schema/expression_internal_schema_xor_test.cpp
@@ -0,0 +1,136 @@
+/**
+ *    Copyright (C) 2012 10gen Inc.
+ *
+ *    This program is free software: you can redistribute it and/or  modify
+ *    it under the terms of the GNU Affero General Public License, version 3,
+ *    as published by the Free Software Foundation.
+ *
+ *    This program is distributed in the hope that it will be useful,
+ *    but WITHOUT ANY WARRANTY; without even the implied warranty of
+ *    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ *    GNU Affero General Public License for more details.
+ *
+ *    You should have received a copy of the GNU Affero General Public License
+ *    along with this program.  If not, see <http://www.gnu.org/licenses/>.
+ *
+ *    As a special exception, the copyright holders give permission to link the
+ *    code of portions of this program with the OpenSSL library under certain
+ *    conditions as described in each individual source file and distribute
+ *    linked combinations including the program with the OpenSSL library. You
+ *    must comply with the GNU Affero General Public License in all respects for
+ *    all of the code used other than as permitted herein. If you modify file(s)
+ *    with this exception, you may extend this exception to your version of the
+ *    file(s), but you are not obligated to do so. If you do not wish to do so,
+ *    delete this exception statement from your version. If you delete this
+ *    exception statement from all source files in the program, then also delete
+ *    it in the license file.
+ */
+
+/** Unit tests for MatchMatchExpression operator implementations in match_operators.{h,cpp}. */
+
+#include "mongo/unittest/unittest.h"
+
+#include "mongo/db/jsobj.h"
+#include "mongo/db/json.h"
+#include "mongo/db/matcher/expression.h"
+#include "mongo/db/matcher/expression_leaf.h"
+#include "mongo/db/matcher/expression_tree.h"
+#include "mongo/db/matcher/schema/expression_internal_schema_xor.h"
+#include "mongo/db/query/collation/collator_interface_mock.h"
+
+namespace mongo {
+
+using std::unique_ptr;
+
+
+
+// TEST(InternalSchemaXorOp, NoClauses) {
+//     InternalSchemaXorMatchExpression internalSchemaXorOp;
+//     ASSERT(internalSchemaXorOp.matchesBSON(BSONObj(), NULL));
+// }
+
+// TEST(InternalSchemaXorOp, MatchesSingleClause) {
+//     BSONObj baseOperand = BSON("$ne" << 5);
+//     unique_ptr<ComparisonMatchExpression> eq(new EqualityMatchExpression());
+//     ASSERT(eq->init("a", baseOperand["$ne"]).isOK());
+//     unique_ptr<NotMatchExpression> ne(new NotMatchExpression());
+//     ASSERT(ne->init(eq.release()).isOK());
+
+//     InternalSchemaXorMatchExpression internalSchemaXorOp;
+//     internalSchemaXorOp.add(ne.release());
+
+//     ASSERT(!internalSchemaXorOp.matchesBSON(BSON("a" << 4), NULL));
+//     ASSERT(!internalSchemaXorOp.matchesBSON(BSON("a" << BSON_ARRAY(4 << 6)), NULL));
+//     ASSERT(internalSchemaXorOp.matchesBSON(BSON("a" << 5), NULL));
+//     ASSERT(internalSchemaXorOp.matchesBSON(BSON("a" << BSON_ARRAY(4 << 5)), NULL));
+// }
+
+// TEST(InternalSchemaXorOp, MatchesThreeClauses) {
+//     BSONObj baseOperand1 = BSON("$gt" << 10);
+//     BSONObj baseOperand2 = BSON("$lt" << 0);
+//     BSONObj baseOperand3 = BSON("b" << 100);
+
+//     unique_ptr<ComparisonMatchExpression> sub1(new GTMatchExpression());
+//     ASSERT(sub1->init("a", baseOperand1["$gt"]).isOK());
+//     unique_ptr<ComparisonMatchExpression> sub2(new LTMatchExpression());
+//     ASSERT(sub2->init("a", baseOperand2["$lt"]).isOK());
+//     unique_ptr<ComparisonMatchExpression> sub3(new EqualityMatchExpression());
+//     ASSERT(sub3->init("b", baseOperand3["b"]).isOK());
+
+//     InternalSchemaXorMatchExpression internalSchemaXorOp;
+//     internalSchemaXorOp.add(sub1.release());
+//     internalSchemaXorOp.add(sub2.release());
+//     internalSchemaXorOp.add(sub3.release());
+
+//     ASSERT(!internalSchemaXorOp.matchesBSON(BSON("a" << -1), NULL));
+//     ASSERT(!internalSchemaXorOp.matchesBSON(BSON("a" << 11), NULL));
+//     ASSERT(internalSchemaXorOp.matchesBSON(BSON("a" << 5), NULL));
+//     ASSERT(!internalSchemaXorOp.matchesBSON(BSON("b" << 100), NULL));
+//     ASSERT(internalSchemaXorOp.matchesBSON(BSON("b" << 101), NULL));
+//     ASSERT(internalSchemaXorOp.matchesBSON(BSONObj(), NULL));
+//     ASSERT(!internalSchemaXorOp.matchesBSON(BSON("a" << 11 << "b" << 100), NULL));
+// }
+
+// TEST(InternalSchemaXorOp, ElemMatchKey) {
+//     BSONObj baseOperand1 = BSON("a" << 1);
+//     BSONObj baseOperand2 = BSON("b" << 2);
+//     unique_ptr<ComparisonMatchExpression> sub1(new EqualityMatchExpression());
+//     ASSERT(sub1->init("a", baseOperand1["a"]).isOK());
+//     unique_ptr<ComparisonMatchExpression> sub2(new EqualityMatchExpression());
+//     ASSERT(sub2->init("b", baseOperand2["b"]).isOK());
+
+//     InternalSchemaXorMatchExpression internalSchemaXorOp;
+//     internalSchemaXorOp.add(sub1.release());
+//     internalSchemaXorOp.add(sub2.release());
+
+//     MatchDetails details;
+//     details.requestElemMatchKey();
+//     ASSERT(!internalSchemaXorOp.matchesBSON(BSON("a" << 1), &details));
+//     ASSERT(!details.hasElemMatchKey());
+//     ASSERT(!internalSchemaXorOp.matchesBSON(BSON("a" << BSON_ARRAY(1) << "b" << BSON_ARRAY(10)), &details));
+//     ASSERT(!details.hasElemMatchKey());
+//     ASSERT(internalSchemaXorOp.matchesBSON(BSON("a" << BSON_ARRAY(3) << "b" << BSON_ARRAY(4)), &details));
+//     // The elem match key feature is not implemented for $internalSchemaXor.
+//     ASSERT(!details.hasElemMatchKey());
+// }
+
+
+// TEST(InternalSchemaXorOp, Equivalent) {
+//     BSONObj baseOperand1 = BSON("a" << 1);
+//     BSONObj baseOperand2 = BSON("b" << 2);
+//     EqualityMatchExpression sub1;
+//     ASSERT(sub1.init("a", baseOperand1["a"]).isOK());
+//     EqualityMatchExpression sub2;
+//     ASSERT(sub2.init("b", baseOperand2["b"]).isOK());
+
+//     InternalSchemaXorMatchExpression e1;
+//     e1.add(sub1.shallowClone().release());
+//     e1.add(sub2.shallowClone().release());
+
+//     InternalSchemaXorMatchExpression e2;
+//     e2.add(sub1.shallowClone().release());
+
+//     ASSERT(e1.equivalent(&e1));
+//     ASSERT(!e1.equivalent(&e2));
+// }
+}
diff --git a/src/mongo/db/query/plan_cache.cpp b/src/mongo/db/query/plan_cache.cpp
index f1f3fb6d6fd..7287f8e8b7a 100644
--- a/src/mongo/db/query/plan_cache.cpp
+++ b/src/mongo/db/query/plan_cache.cpp
@@ -102,6 +102,9 @@ const char* encodeMatchType(MatchExpression::MatchType mt) {
         case MatchExpression::NOR:
             return "nr";
             break;
+        case MatchExpression::INTERNAL_SCHEMA_XOR:
+            return "internalSchemaXor";
+            break;
         case MatchExpression::NOT:
             return "nt";
             break;