SERVER-47730 Add IdempotencyTest for delta oplog entries

2 files changed, 142 insertions, 83 deletions

diff --git a/src/mongo/db/update/document_diff_test.cpp b/src/mongo/db/update/document_diff_test.cpp
index abaec9b8570..a928060a0e2 100644
--- a/src/mongo/db/update/document_diff_test.cpp
+++ b/src/mongo/db/update/document_diff_test.cpp
@@ -31,15 +31,11 @@
 
 #include "mongo/platform/basic.h"
 
-#include <algorithm>
-#include <random>
-
 #include "mongo/bson/bson_depth.h"
 #include "mongo/bson/json.h"
-#include "mongo/db/exec/document_value/document.h"
-#include "mongo/db/exec/document_value/value.h"
 #include "mongo/db/update/document_diff_applier.h"
 #include "mongo/db/update/document_diff_calculator.h"
+#include "mongo/db/update/document_diff_test_helpers.h"
 #include "mongo/logv2/log.h"
 #include "mongo/platform/random.h"
 #include "mongo/unittest/bson_test_util.h"
@@ -48,7 +44,6 @@
 namespace mongo::doc_diff {
 namespace {
 
-
 // We use the same seed and random number generator throughout the tests to be able to reproduce a
 // failure easily.
 auto getSeed() {
@@ -60,43 +55,6 @@ PseudoRandom* getRNG() {
     return &rng;
 }
 
-BSONObj createObjWithLargePrefix(StringData suffix, int len = 100) {
-    const static auto largeObj = BSON("prefixLargeField" << std::string(len, 'a'));
-    return largeObj.addFields(fromjson(suffix.rawData()));
-}
-
-std::string getFieldName(int level, int fieldNum) {
-    return str::stream() << "f" << level << fieldNum;
-}
-
-Value getScalarFieldValue() {
-    auto rng = getRNG();
-    switch (rng->nextInt64(10)) {
-        case 0:
-            return Value("val"_sd);
-        case 1:
-            return Value(BSONNULL);
-        case 2:
-            return Value(-1LL);
-        case 3:
-            return Value(0);
-        case 4:
-            return Value(1.10);
-        case 5:
-            return Value(false);
-        case 6:
-            return Value(BSONRegEx("p"));
-        case 7:
-            return Value(Date_t());
-        case 8:
-            return Value(UUID::gen());
-        case 9:
-            return Value(BSONBinData("asdf", 4, BinDataGeneral));
-        default:
-            MONGO_UNREACHABLE;
-    }
-}
-
 std::vector<BSONObj> getDocumentsRepo() {
     const static std::vector<BSONObj> documents = {
         createObjWithLargePrefix("{}"),  // Empty object.
@@ -149,10 +107,13 @@ void runTest(std::vector<BSONObj> documents, size_t numSimulations) {
         std::shuffle(documents.begin(), documents.end(), rng->urbg());
 
         auto preDoc = documents[0];
+        std::vector<BSONObj> diffs;
+        diffs.reserve(documents.size() - 1);
         for (size_t i = 1; i < documents.size(); ++i) {
             const auto diff = computeDiff(preDoc, documents[i]);
 
             ASSERT(diff);
+            diffs.push_back(*diff);
             const auto postObj = applyDiff(preDoc, *diff);
             ASSERT_BSONOBJ_BINARY_EQ(documents[i], postObj);
 
@@ -161,57 +122,29 @@ void runTest(std::vector<BSONObj> documents, size_t numSimulations) {
 
             preDoc = documents[i];
         }
-    }
-}
-TEST(DocumentDiffTest, PredefinedDocumentsTest) {
-    runTest(getDocumentsRepo(), 10);
-}
 
-BSONObj generateDoc(MutableDocument* doc, int depthLevel) {
-    // Append a large field at each level so that the likelihood of generating a sub-diff is high.
-    doc->reset(createObjWithLargePrefix("{}", 100), true);
-
-    // Reduce the probabilty of generated nested objects as we go deeper. After depth level 6, we
-    // should not be generating anymore nested objects.
-    const double subObjProbability = 0.3 - (depthLevel * 0.05);
-    const double subArrayProbability = 0.2 - (depthLevel * 0.05);
-
-    auto rng = getRNG();
-    const int numFields = (5 - depthLevel) + rng->nextInt32(4);
-    for (int fieldNum = 0; fieldNum < numFields; ++fieldNum) {
-        const auto fieldName = getFieldName(depthLevel, fieldNum);
-        auto num = rng->nextCanonicalDouble();
-        if (num <= subObjProbability) {
-            MutableDocument subDoc;
-            doc->addField(fieldName, Value(generateDoc(&subDoc, depthLevel + 1)));
-        } else if (num <= (subObjProbability + subArrayProbability)) {
-            std::uniform_int_distribution<int> arrayLengthGen(0, 10);
-            const auto length = arrayLengthGen(rng->urbg());
-            std::vector<Value> values;
-
-            // Make sure that only one array element is a document to avoid exponentially bloating
-            // up the document.
-            if (length) {
-                MutableDocument subDoc;
-                values.push_back(Value(generateDoc(&subDoc, depthLevel + 1)));
+        // Verify that re-applying any suffix of the diffs in the sequence order will end produce
+        // the same end state.
+        for (size_t start = 0; start < diffs.size(); ++start) {
+            auto endObj = documents.back();
+            for (size_t i = start; i < diffs.size(); ++i) {
+                endObj = applyDiff(endObj, diffs[i]);
             }
-            for (auto i = 1; i < length; i++) {
-                values.push_back(getScalarFieldValue());
-            }
-            doc->addField(fieldName, Value(values));
-        } else {
-            doc->addField(fieldName, getScalarFieldValue());
+            ASSERT_BSONOBJ_BINARY_EQ(endObj, documents.back());
         }
     }
-    return doc->freeze().toBson();
+}
+TEST(DocumentDiffTest, PredefinedDocumentsTest) {
+    runTest(getDocumentsRepo(), 10);
 }
 
 TEST(DocumentDiffTest, RandomizedDocumentBuilderTest) {
     const auto numDocs = 20;
     std::vector<BSONObj> documents(numDocs);
+    auto rng = getRNG();
     for (int i = 0; i < numDocs; ++i) {
         MutableDocument doc;
-        documents[i] = generateDoc(&doc, 0);
+        documents[i] = generateDoc(rng, &doc, 0);
     }
     runTest(std::move(documents), 10);
 }
diff --git a/src/mongo/db/update/document_diff_test_helpers.h b/src/mongo/db/update/document_diff_test_helpers.h
new file mode 100644
index 00000000000..09d545cba47
--- /dev/null
+++ b/src/mongo/db/update/document_diff_test_helpers.h
@@ -0,0 +1,126 @@
+/**
+ *    Copyright (C) 2020-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 <algorithm>
+
+#include "mongo/bson/json.h"
+#include "mongo/db/exec/document_value/document.h"
+#include "mongo/db/exec/document_value/value.h"
+#include "mongo/db/update/document_diff_applier.h"
+#include "mongo/db/update/document_diff_calculator.h"
+#include "mongo/platform/random.h"
+#include "mongo/unittest/bson_test_util.h"
+#include "mongo/unittest/unittest.h"
+
+namespace mongo::doc_diff {
+
+BSONObj createObjWithLargePrefix(const std::string& suffix) {
+    const static auto largeObj = BSON("prefixLargeField" << std::string(200, 'a'));
+    return largeObj.addFields(fromjson(suffix));
+}
+
+std::string getFieldName(int level, int fieldNum) {
+    return str::stream() << "f" << level << fieldNum;
+}
+
+Value getScalarFieldValue(PseudoRandom* rng) {
+    switch (rng->nextInt32(10)) {
+        case 0:
+            return Value("val"_sd);
+        case 1:
+            return Value(BSONNULL);
+        case 2:
+            return Value(-1LL);
+        case 3:
+            return Value(0);
+        case 4:
+            return Value(1.10);
+        case 5:
+            return Value(false);
+        case 6:
+            return Value(BSONRegEx("p"));
+        case 7:
+            return Value(Date_t());
+        case 8:
+            return Value(UUID::gen());
+        case 9:
+            return Value(BSONBinData("asdf", 4, BinDataGeneral));
+        default:
+            MONGO_UNREACHABLE;
+    }
+}
+
+BSONObj generateDoc(PseudoRandom* rng, MutableDocument* doc, int depthLevel) {
+    // Append a large field at each level so that the likelihood of generating a sub-diff is high.
+    auto largeFieldObj = createObjWithLargePrefix("{}");
+    doc->addField("prefixLargeField", Value(largeFieldObj.firstElement()));
+
+    // Reduce the probabilty of generated nested objects as we go deeper. After depth level 6, we
+    // should not be generating anymore nested objects.
+    const double subObjProbability = 0.3 - (depthLevel * 0.05);
+    const double subArrayProbability = 0.2 - (depthLevel * 0.05);
+
+    const int numFields = (5 - depthLevel) + rng->nextInt32(4);
+    for (int fieldNum = 0; fieldNum < numFields; ++fieldNum) {
+        const auto fieldName = getFieldName(depthLevel, fieldNum);
+        auto num = rng->nextCanonicalDouble();
+        if (num <= subObjProbability) {
+            MutableDocument subDoc;
+            doc->addField(fieldName, Value(generateDoc(rng, &subDoc, depthLevel + 1)));
+        } else if (num <= (subObjProbability + subArrayProbability)) {
+            const auto arrayLength = rng->nextInt32(10);
+            std::vector<Value> values;
+            auto numSubObjs = 0;
+            for (auto i = 0; i < arrayLength; i++) {
+                // The probablilty of generating a sub-object goes down as we generate more
+                // sub-objects and as the array position increases.
+                if (!rng->nextInt32(2 + numSubObjs + i)) {
+                    MutableDocument subDoc;
+
+                    // Ensure that the depth is higher as we generate more sub-objects, to avoid
+                    // bloating up the document size exponentially.
+                    values.push_back(
+                        Value(generateDoc(rng, &subDoc, depthLevel + 1 + numSubObjs * 2)));
+                    ++numSubObjs;
+                } else {
+                    values.push_back(getScalarFieldValue(rng));
+                }
+            }
+
+            doc->addField(fieldName, Value(values));
+        } else {
+            doc->addField(fieldName, getScalarFieldValue(rng));
+        }
+    }
+    return doc->freeze().toBson();
+}
+
+}  // namespace mongo::doc_diff