SERVER-29425 implement $sortArray in classic engine

6 files changed, 175 insertions, 113 deletions

diff --git a/src/mongo/db/update/SConscript b/src/mongo/db/update/SConscript
index a8f0bd1dc2b..3e0eb55927f 100644
--- a/src/mongo/db/update/SConscript
+++ b/src/mongo/db/update/SConscript
@@ -133,7 +133,7 @@ env.CppUnitTest(
         'pull_node_test.cpp',
         'pullall_node_test.cpp',
         'push_node_test.cpp',
-        'push_sorter_test.cpp',
+        'pattern_cmp_test.cpp',
         'rename_node_test.cpp',
         'set_node_test.cpp',
         'unset_node_test.cpp',
diff --git a/src/mongo/db/update/pattern_cmp.h b/src/mongo/db/update/pattern_cmp.h
new file mode 100644
index 00000000000..c612bdec29f
--- /dev/null
+++ b/src/mongo/db/update/pattern_cmp.h
@@ -0,0 +1,171 @@
+/**
+ *    Copyright (C) 2021-present MongoDB, Inc.
+ *
+ *    This program is free software: you can redistribute it and/or modify
+ *    it under the terms of the Server Side Public License, version 1,
+ *    as published by MongoDB, Inc.
+ *
+ *    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
+ *    Server Side Public License for more details.
+ *
+ *    You should have received a copy of the Server Side Public License
+ *    along with this program. If not, see
+ *    <http://www.mongodb.com/licensing/server-side-public-license>.
+ *
+ *    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 Server Side 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/bson/mutable/document.h"
+#include "mongo/bson/mutable/element.h"
+#include "mongo/db/bson/dotted_path_support.h"
+#include "mongo/db/exec/document_value/document.h"
+#include "mongo/db/exec/document_value/value_comparator.h"
+#include "mongo/db/field_ref.h"
+#include "mongo/db/jsobj.h"
+#include "mongo/db/query/collation/collator_interface.h"
+
+namespace mongo {
+
+namespace pattern_cmp {
+
+/**
+ * When we include a sort specification, that object should pass the checks in
+ * this function.
+ *
+ * Checks include:
+ *   1. The sort pattern cannot be empty.
+ *   2. The value of each pattern element is 1 or -1.
+ *   3. The sort field cannot be empty.
+ *   4. If the sort field is a dotted field, it does not have any empty parts.
+ */
+static Status checkSortClause(const BSONObj& sortObject) {
+    if (sortObject.isEmpty()) {
+        return Status(ErrorCodes::BadValue,
+                      "The sort pattern is empty when it should be a set of fields.");
+    }
+
+    for (auto&& patternElement : sortObject) {
+        double orderVal = patternElement.isNumber() ? patternElement.Number() : 0;
+        if (orderVal != -1 && orderVal != 1) {
+            return Status(ErrorCodes::BadValue, "The sort element value must be either 1 or -1");
+        }
+
+        FieldRef sortField(patternElement.fieldName());
+        if (sortField.numParts() == 0) {
+            return Status(ErrorCodes::BadValue, "The sort field cannot be empty");
+        }
+
+        for (size_t i = 0; i < sortField.numParts(); ++i) {
+            if (sortField.getPart(i).size() == 0) {
+                return Status(ErrorCodes::BadValue,
+                              str::stream() << "The sort field is a dotted field "
+                                               "but has an empty part: "
+                                            << sortField.dottedField());
+            }
+        }
+    }
+
+    return Status::OK();
+}
+
+}  // namespace pattern_cmp
+
+// Extracts the value for 'pattern' for both 'lhs' and 'rhs' and return true if 'lhs' <
+// 'rhs'. We expect that both 'lhs' and 'rhs' be key patterns.
+class PatternElementCmp {
+public:
+    PatternElementCmp() = default;
+
+    PatternElementCmp(const BSONObj& pattern, const CollatorInterface* collator)
+        : sortPattern(pattern.copy()),
+          useWholeValue(sortPattern.hasField("")),
+          collator(collator) {}
+
+    bool operator()(const mutablebson::Element& lhs, const mutablebson::Element& rhs) const {
+        namespace dps = ::mongo::dotted_path_support;
+        if (useWholeValue) {
+            const int comparedValue = lhs.compareWithElement(rhs, collator, false);
+
+            const bool reversed = (sortPattern.firstElement().number() < 0);
+
+            return (reversed ? comparedValue > 0 : comparedValue < 0);
+        } else {
+            BSONObj lhsObj =
+                lhs.getType() == Object ? lhs.getValueObject() : lhs.getValue().wrap("");
+            BSONObj rhsObj =
+                rhs.getType() == Object ? rhs.getValueObject() : rhs.getValue().wrap("");
+
+            BSONObj lhsKey = dps::extractElementsBasedOnTemplate(lhsObj, sortPattern, true);
+            BSONObj rhsKey = dps::extractElementsBasedOnTemplate(rhsObj, sortPattern, true);
+
+            return lhsKey.woCompare(rhsKey, sortPattern, false, collator) < 0;
+        }
+    }
+
+    BSONObj sortPattern;
+    bool useWholeValue = true;
+    const CollatorInterface* collator = nullptr;
+};
+
+class PatternValueCmp {
+public:
+    PatternValueCmp() = default;
+
+    PatternValueCmp(const BSONObj& pattern,
+                    const BSONElement& originalElement,
+                    const CollatorInterface* collator)
+        : sortPattern(pattern.copy()),
+          useWholeValue(sortPattern.hasField("")),
+          originalObj(BSONObj().addField(originalElement).copy()),
+          collator(collator) {}
+
+    bool operator()(const Value& lhs, const Value& rhs) const {
+        namespace dps = ::mongo::dotted_path_support;
+        if (useWholeValue) {
+            const bool ascending = ValueComparator().getLessThan()(lhs, rhs);
+
+            const bool reversed = (sortPattern.firstElement().number() < 0);
+
+            return (reversed ? !ascending : ascending);
+        } else {
+            BSONObj lhsObj = lhs.isObject() ? lhs.getDocument().toBson() : lhs.wrap("");
+            BSONObj rhsObj = rhs.isObject() ? rhs.getDocument().toBson() : rhs.wrap("");
+
+            BSONObj lhsKey = dps::extractElementsBasedOnTemplate(lhsObj, sortPattern, true);
+            BSONObj rhsKey = dps::extractElementsBasedOnTemplate(rhsObj, sortPattern, true);
+
+            return lhsKey.woCompare(rhsKey, sortPattern, false, collator) < 0;
+        }
+    }
+
+    // Returns the original element passed into the PatternValueCmp constructor.
+    BSONElement getOriginalElement() const {
+        return originalObj.firstElement();
+    }
+
+    BSONObj sortPattern;
+    bool useWholeValue = true;
+
+    /**
+     * We store the original element as an object so that we can call the copy() method on it.
+     * This way, the PatternValueCmp class can have its own copy of the object.
+     */
+    BSONObj originalObj;
+    const CollatorInterface* collator = nullptr;
+};
+
+}  // namespace mongo
diff --git a/src/mongo/db/update/push_sorter_test.cpp b/src/mongo/db/update/pattern_cmp_test.cpp
index 6dfa3219dd8..a6b0f44aadd 100644
--- a/src/mongo/db/update/push_sorter_test.cpp
+++ b/src/mongo/db/update/pattern_cmp_test.cpp
@@ -27,7 +27,7 @@
  *    it in the license file.
  */
 
-#include "mongo/db/update/push_sorter.h"
+#include "mongo/db/update/pattern_cmp.h"
 
 #include "mongo/bson/mutable/algorithm.h"
 #include "mongo/bson/mutable/document.h"
diff --git a/src/mongo/db/update/push_node.cpp b/src/mongo/db/update/push_node.cpp
index f428269a924..3a4e7c1705c 100644
--- a/src/mongo/db/update/push_node.cpp
+++ b/src/mongo/db/update/push_node.cpp
@@ -49,40 +49,6 @@ const StringData PushNode::kPositionClauseName = "$position";
 namespace {
 
 /**
- * When the $sort clause in a $push modifer is an object, that object should pass the checks in
- * this function.
- */
-Status checkSortClause(const BSONObj& sortObject) {
-    if (sortObject.isEmpty()) {
-        return Status(ErrorCodes::BadValue,
-                      "The $sort pattern is empty when it should be a set of fields.");
-    }
-
-    for (auto&& patternElement : sortObject) {
-        double orderVal = patternElement.isNumber() ? patternElement.Number() : 0;
-        if (orderVal != -1 && orderVal != 1) {
-            return Status(ErrorCodes::BadValue, "The $sort element value must be either 1 or -1");
-        }
-
-        FieldRef sortField(patternElement.fieldName());
-        if (sortField.numParts() == 0) {
-            return Status(ErrorCodes::BadValue, "The $sort field cannot be empty");
-        }
-
-        for (size_t i = 0; i < sortField.numParts(); ++i) {
-            if (sortField.getPart(i).size() == 0) {
-                return Status(ErrorCodes::BadValue,
-                              str::stream() << "The $sort field is a dotted field "
-                                               "but has an empty part: "
-                                            << sortField.dottedField());
-            }
-        }
-    }
-
-    return Status::OK();
-}
-
-/**
  * std::abs(LLONG_MIN) results in undefined behavior on 2's complement systems because the
  * absolute value of LLONG_MIN cannot be represented in a 'long long'.
  *
@@ -157,7 +123,7 @@ Status PushNode::init(BSONElement modExpr, const boost::intrusive_ptr<Expression
             auto sortClause = sortIt->second;
 
             if (sortClause.type() == BSONType::Object) {
-                auto status = checkSortClause(sortClause.embeddedObject());
+                auto status = pattern_cmp::checkSortClause(sortClause.embeddedObject());
 
                 if (status.isOK()) {
                     _sort = PatternElementCmp(sortClause.embeddedObject(), expCtx->getCollator());
diff --git a/src/mongo/db/update/push_node.h b/src/mongo/db/update/push_node.h
index 38b4b00bc66..77cc6b5d125 100644
--- a/src/mongo/db/update/push_node.h
+++ b/src/mongo/db/update/push_node.h
@@ -36,7 +36,7 @@
 
 #include "mongo/base/string_data.h"
 #include "mongo/db/update/modifier_node.h"
-#include "mongo/db/update/push_sorter.h"
+#include "mongo/db/update/pattern_cmp.h"
 
 namespace mongo {
 
diff --git a/src/mongo/db/update/push_sorter.h b/src/mongo/db/update/push_sorter.h
deleted file mode 100644
index 139529533ae..00000000000
--- a/src/mongo/db/update/push_sorter.h
+++ /dev/null
@@ -1,75 +0,0 @@
-/**
- *    Copyright (C) 2018-present MongoDB, Inc.
- *
- *    This program is free software: you can redistribute it and/or modify
- *    it under the terms of the Server Side Public License, version 1,
- *    as published by MongoDB, Inc.
- *
- *    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
- *    Server Side Public License for more details.
- *
- *    You should have received a copy of the Server Side Public License
- *    along with this program. If not, see
- *    <http://www.mongodb.com/licensing/server-side-public-license>.
- *
- *    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 Server Side 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/bson/mutable/document.h"
-#include "mongo/bson/mutable/element.h"
-#include "mongo/db/bson/dotted_path_support.h"
-#include "mongo/db/jsobj.h"
-#include "mongo/db/query/collation/collator_interface.h"
-
-namespace mongo {
-
-// Extracts the value for 'pattern' for both 'lhs' and 'rhs' and return true if 'lhs' <
-// 'rhs'. We expect that both 'lhs' and 'rhs' be key patterns.
-struct PatternElementCmp {
-    PatternElementCmp() = default;
-
-    PatternElementCmp(const BSONObj& pattern, const CollatorInterface* collator)
-        : sortPattern(pattern), useWholeValue(pattern.hasField("")), collator(collator) {}
-
-    bool operator()(const mutablebson::Element& lhs, const mutablebson::Element& rhs) const {
-        namespace dps = ::mongo::dotted_path_support;
-        if (useWholeValue) {
-            const int comparedValue = lhs.compareWithElement(rhs, collator, false);
-
-            const bool reversed = (sortPattern.firstElement().number() < 0);
-
-            return (reversed ? comparedValue > 0 : comparedValue < 0);
-        } else {
-            // TODO: Push on to mutable in the future, and to support non-contiguous Elements.
-            BSONObj lhsObj =
-                lhs.getType() == Object ? lhs.getValueObject() : lhs.getValue().wrap("");
-            BSONObj rhsObj =
-                rhs.getType() == Object ? rhs.getValueObject() : rhs.getValue().wrap("");
-
-            BSONObj lhsKey = dps::extractElementsBasedOnTemplate(lhsObj, sortPattern, true);
-            BSONObj rhsKey = dps::extractElementsBasedOnTemplate(rhsObj, sortPattern, true);
-
-            return lhsKey.woCompare(rhsKey, sortPattern, false, collator) < 0;
-        }
-    }
-
-    BSONObj sortPattern;
-    bool useWholeValue = true;
-    const CollatorInterface* collator = nullptr;
-};
-
-}  // namespace mongo