SERVER-29575: Add an $_internalSchemaXor MatchExpression

7 files changed, 291 insertions, 3 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..b6a2701702f 100644
--- a/src/mongo/db/matcher/expression.h
+++ b/src/mongo/db/matcher/expression.h
@@ -100,6 +100,7 @@ public:
         // JSON Schema expressions.
         INTERNAL_SCHEMA_MIN_ITEMS,
         INTERNAL_SCHEMA_MAX_ITEMS,
+        INTERNAL_SCHEMA_XOR,
     };
 
     MatchExpression(MatchType type);
@@ -161,11 +162,21 @@ public:
      */
 
     /**
-     * Is this node a logical operator?  All of these inherit from ListOfMatchExpression.
-     * AND, OR, NOT, NOR.
+     * Returns true if this match expression node operates logically on its children.
+     * For example, the AND node is logical in that it returns true only if all of its
+     * children return true.
      */
     bool isLogical() const {
-        return AND == _matchType || OR == _matchType || NOT == _matchType || NOR == _matchType;
+        switch (_matchType) {
+            case AND:
+            case OR:
+            case NOT:
+            case NOR:
+            case INTERNAL_SCHEMA_XOR:
+                return true;
+            default:
+                return false;
+        }
     }
 
     /**
diff --git a/src/mongo/db/matcher/expression_algo.cpp b/src/mongo/db/matcher/expression_algo.cpp
index 292bf1f590a..0979eb7b475 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"
@@ -346,6 +347,7 @@ 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..d8111a30c2d 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"
@@ -366,6 +367,15 @@ StatusWithMatchExpression MatchExpressionParser::_parse(const BSONObj& obj,
                 eq->setCollator(str::equals("id", rest) ? collator : nullptr);
 
                 root->add(eq.release());
+            } else if (mongoutils::str::equals("_internalSchemaXor", rest)) {
+                if (e.type() != BSONType::Array)
+                    return {
+                        Status(ErrorCodes::TypeMismatch, "$_internalSchemaXor must be an array")};
+                auto xorExpr = stdx::make_unique<InternalSchemaXorMatchExpression>();
+                Status s = _parseTreeList(e.Obj(), xorExpr.get(), collator, childIsTopLevel);
+                if (!s.isOK())
+                    return s;
+                root->add(xorExpr.release());
             } else {
                 return {Status(ErrorCodes::BadValue,
                                mongoutils::str::stream() << "unknown top level operator: "
@@ -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("$_internalSchemaXor", 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..a03ce13349a
--- /dev/null
+++ b/src/mongo/db/matcher/schema/expression_internal_schema_xor.cpp
@@ -0,0 +1,77 @@
+/**
+ *    Copyright (C) 2017 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/platform/basic.h"
+
+#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 {
+constexpr StringData InternalSchemaXorMatchExpression::kInternalSchemaXor;
+
+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, nullptr)) {
+            if (found) {
+                return false;
+            }
+            found = true;
+        }
+    }
+    return found;
+}
+
+bool InternalSchemaXorMatchExpression::matchesSingleElement(const BSONElement& element) const {
+    bool found = false;
+    for (size_t i = 0; i < numChildren(); i++) {
+        if (getChild(i)->matchesSingleElement(element)) {
+            if (found) {
+                return false;
+            }
+            found = true;
+        }
+    }
+    return found;
+}
+
+void InternalSchemaXorMatchExpression::debugString(StringBuilder& debug, int level) const {
+    _debugAddSpace(debug, level);
+    debug << kInternalSchemaXor + "\n";
+    _debugList(debug, level);
+}
+
+void InternalSchemaXorMatchExpression::serialize(BSONObjBuilder* out) const {
+    BSONArrayBuilder arrBob(out->subarrayStart(kInternalSchemaXor));
+    _listToBSON(&arrBob);
+}
+}  //  namespace mongo
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..2c3c65f9147
--- /dev/null
+++ b/src/mongo/db/matcher/schema/expression_internal_schema_xor.h
@@ -0,0 +1,64 @@
+/**
+ *    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. Returns true only if exactly
+ * one of its child nodes matches.
+ */
+class InternalSchemaXorMatchExpression final : public ListOfMatchExpression {
+public:
+    static constexpr StringData kInternalSchemaXor = "$_internalSchemaXor"_sd;
+
+    InternalSchemaXorMatchExpression() : ListOfMatchExpression(INTERNAL_SCHEMA_XOR) {}
+
+    bool matches(const MatchableDocument* doc, MatchDetails* details = nullptr) const final;
+
+    bool matchesSingleElement(const BSONElement& element) const final;
+
+    virtual std::unique_ptr<MatchExpression> shallowClone() const {
+        auto xorCopy = stdx::make_unique<InternalSchemaXorMatchExpression>();
+        for (size_t i = 0; i < numChildren(); ++i) {
+            xorCopy->add(getChild(i)->shallowClone().release());
+        }
+        if (getTag()) {
+            xorCopy->setTag(getTag()->clone());
+        }
+        return std::move(xorCopy);
+    }
+
+    void debugString(StringBuilder& debug, int level = 0) const final;
+
+    void serialize(BSONObjBuilder* out) const final;
+};
+}  // 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..de06ac5d18f
--- /dev/null
+++ b/src/mongo/db/matcher/schema/expression_internal_schema_xor_test.cpp
@@ -0,0 +1,121 @@
+/**
+ *    Copyright (C) 2017 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/platform/basic.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_parser.h"
+#include "mongo/db/matcher/extensions_callback_disallow_extensions.h"
+#include "mongo/db/matcher/schema/expression_internal_schema_xor.h"
+#include "mongo/unittest/unittest.h"
+
+namespace mongo {
+namespace {
+
+using std::unique_ptr;
+
+TEST(InternalSchemaXorOp, MatchesNothingWhenHasNoClauses) {
+    InternalSchemaXorMatchExpression internalSchemaXorOp;
+    ASSERT_FALSE(internalSchemaXorOp.matchesBSON(BSONObj()));
+}
+
+TEST(InternalSchemaXorOp, MatchesSingleClause) {
+    BSONObj matchPredicate = fromjson("{$_internalSchemaXor: [{a: { $ne: 5 }}]}");
+    const CollatorInterface* collator = nullptr;
+    auto expr = MatchExpressionParser::parse(
+        matchPredicate, ExtensionsCallbackDisallowExtensions(), collator);
+
+    ASSERT_OK(expr.getStatus());
+    ASSERT_TRUE(expr.getValue()->matchesBSON(BSON("a" << 4)));
+    ASSERT_TRUE(expr.getValue()->matchesBSON(BSON("a" << BSON_ARRAY(4 << 6))));
+    ASSERT_FALSE(expr.getValue()->matchesBSON(BSON("a" << 5)));
+    ASSERT_FALSE(expr.getValue()->matchesBSON(BSON("a" << BSON_ARRAY(4 << 5))));
+}
+
+TEST(InternalSchemaXorOp, MatchesThreeClauses) {
+    const CollatorInterface* collator = nullptr;
+    BSONObj matchPredicate =
+        fromjson("{$_internalSchemaXor: [{a: { $gt: 10 }}, {a: { $lt: 0 }}, {b: 0}]}");
+
+    auto expr = MatchExpressionParser::parse(
+        matchPredicate, ExtensionsCallbackDisallowExtensions(), collator);
+
+    ASSERT_OK(expr.getStatus());
+    ASSERT_TRUE(expr.getValue()->matchesBSON(BSON("a" << -1)));
+    ASSERT_TRUE(expr.getValue()->matchesBSON(BSON("a" << 11)));
+    ASSERT_FALSE(expr.getValue()->matchesBSON(BSON("a" << 5)));
+    ASSERT_FALSE(expr.getValue()->matchesBSON(BSON("b" << 100)));
+    ASSERT_FALSE(expr.getValue()->matchesBSON(BSON("b" << 101)));
+    ASSERT_FALSE(expr.getValue()->matchesBSON(BSONObj()));
+    ASSERT_TRUE(expr.getValue()->matchesBSON(BSON("a" << 11 << "b" << 100)));
+    ASSERT_FALSE(expr.getValue()->matchesBSON(BSON("a" << 11 << "b" << 0)));
+}
+
+TEST(InternalSchemaXorOp, DoesNotUseElemMatchKey) {
+    const CollatorInterface* collator = nullptr;
+
+    BSONObj matchPredicate = fromjson("{$_internalSchemaXor: [{a: 1}, {b: 2}]}");
+
+    auto expr = MatchExpressionParser::parse(
+        matchPredicate, ExtensionsCallbackDisallowExtensions(), collator);
+    MatchDetails details;
+    details.requestElemMatchKey();
+    ASSERT_OK(expr.getStatus());
+    ASSERT_TRUE(expr.getValue()->matchesBSON(BSON("a" << 1), &details));
+    ASSERT_FALSE(details.hasElemMatchKey());
+    ASSERT_TRUE(expr.getValue()->matchesBSON(BSON("a" << BSON_ARRAY(1) << "b" << BSON_ARRAY(10)),
+                                        &details));
+    ASSERT_FALSE(details.hasElemMatchKey());
+    ASSERT_FALSE(
+        expr.getValue()->matchesBSON(BSON("a" << BSON_ARRAY(3) << "b" << BSON_ARRAY(4)), &details));
+    ASSERT_FALSE(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_FALSE(e1.equivalent(&e2));
+}
+}  // namespace
+}  // namespace mongo