SERVER-47280 Add machinery for applying document deltas

4 files changed, 660 insertions, 0 deletions

diff --git a/src/mongo/db/update/SConscript b/src/mongo/db/update/SConscript
index 47073586e53..f5e14816dba 100644
--- a/src/mongo/db/update/SConscript
+++ b/src/mongo/db/update/SConscript
@@ -30,6 +30,7 @@ env.Library(
         'compare_node.cpp',
         'current_date_node.cpp',
         'document_diff_calculator.cpp',
+        'document_diff_applier.cpp',
         'document_diff_serialization.cpp',
         'modifier_node.cpp',
         'modifier_table.cpp',
@@ -81,6 +82,7 @@ env.CppUnitTest(
         'current_date_node_test.cpp',
         'document_diff_calculator_test.cpp',
         'document_diff_serialization_test.cpp',
+        'document_diff_applier_test.cpp',
         'field_checker_test.cpp',
         'log_builder_test.cpp',
         'modifier_table_test.cpp',
diff --git a/src/mongo/db/update/document_diff_applier.cpp b/src/mongo/db/update/document_diff_applier.cpp
new file mode 100644
index 00000000000..d726d5d0a87
--- /dev/null
+++ b/src/mongo/db/update/document_diff_applier.cpp
@@ -0,0 +1,259 @@
+/**
+ *    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.
+ */
+
+#include "mongo/platform/basic.h"
+
+#include "mongo/db/update/document_diff_applier.h"
+
+#include "mongo/stdx/variant.h"
+#include "mongo/util/string_map.h"
+#include "mongo/util/visit_helper.h"
+
+namespace mongo::doc_diff {
+namespace {
+struct Update {
+    BSONElement newElt;
+};
+struct Insert {
+    BSONElement newElt;
+};
+struct Delete {};
+struct SubDiff {
+    DiffType type() const {
+        return stdx::holds_alternative<DocumentDiffReader>(reader) ? DiffType::kDocument
+                                                                   : DiffType::kArray;
+    }
+
+    stdx::variant<DocumentDiffReader, ArrayDiffReader> reader;
+};
+
+// This struct stores the tables we build from an object diff before applying it.
+struct DocumentDiffTables {
+    // Types of modifications that can be done to a field.
+    using FieldModification = stdx::variant<Delete, Update, Insert, SubDiff>;
+
+    /**
+     * Inserts to the table and throws if the key exists already, which would mean that the
+     * diff is invalid.
+     */
+    void safeInsert(StringData fieldName, FieldModification mod) {
+        auto [it, inserted] = fieldMap.insert({fieldName, std::move(mod)});
+        uassert(4728000, str::stream() << "duplicate field name in diff: " << fieldName, inserted);
+    }
+
+    // Map from field name to modification for that field.
+    StringDataMap<FieldModification> fieldMap;
+
+    // Order in which new fields should be added to the pre image.
+    std::vector<BSONElement> fieldsToInsert;
+};
+
+DocumentDiffTables buildObjDiffTables(DocumentDiffReader* reader) {
+    DocumentDiffTables out;
+
+    boost::optional<StringData> optFieldName;
+    while ((optFieldName = reader->nextDelete())) {
+        out.safeInsert(*optFieldName, Delete{});
+    }
+
+    boost::optional<BSONElement> nextUpdate;
+    while ((nextUpdate = reader->nextUpdate())) {
+        out.safeInsert(nextUpdate->fieldNameStringData(), Update{*nextUpdate});
+        out.fieldsToInsert.push_back(*nextUpdate);
+    }
+
+    boost::optional<BSONElement> nextInsert;
+    while ((nextInsert = reader->nextInsert())) {
+        out.safeInsert(nextInsert->fieldNameStringData(), Insert{*nextInsert});
+        out.fieldsToInsert.push_back(*nextInsert);
+    }
+
+    for (auto next = reader->nextSubDiff(); next; next = reader->nextSubDiff()) {
+        out.safeInsert(next->first, SubDiff{next->second});
+    }
+    return out;
+}
+
+// Mutually recursive with applyDiffToObject().
+void applyDiffToArray(const BSONObj& preImage, ArrayDiffReader* reader, BSONArrayBuilder* builder);
+
+void applyDiffToObject(const BSONObj& preImage,
+                       DocumentDiffReader* reader,
+                       BSONObjBuilder* builder) {
+    // First build some tables so we can quickly apply the diff. We shouldn't need to examine the
+    // diff again once this is done.
+    const DocumentDiffTables tables = buildObjDiffTables(reader);
+
+    // Keep track of what fields we already appended, so that we can insert the rest at the end.
+    StringDataSet fieldsToSkipInserting;
+
+    for (auto&& elt : preImage) {
+        auto it = tables.fieldMap.find(elt.fieldNameStringData());
+        if (it == tables.fieldMap.end()) {
+            // Field is not modified, so we append it as is.
+            builder->append(elt);
+            continue;
+        }
+
+        stdx::visit(
+            visit_helper::Overloaded{
+                [](Delete) {
+                    // Do nothing.
+                },
+
+                [&builder, &elt, &fieldsToSkipInserting](const Update& update) {
+                    builder->append(update.newElt);
+                    fieldsToSkipInserting.insert(elt.fieldNameStringData());
+                },
+
+                [](const Insert&) {
+                    // Skip the pre-image version of the field. We'll add it at the end.
+                },
+
+                [&builder, &elt](const SubDiff& subDiff) {
+                    const auto type = subDiff.type();
+                    if (elt.type() == BSONType::Object && type == DiffType::kDocument) {
+                        BSONObjBuilder subBob(builder->subobjStart(elt.fieldNameStringData()));
+                        auto reader = stdx::get<DocumentDiffReader>(subDiff.reader);
+                        applyDiffToObject(elt.embeddedObject(), &reader, &subBob);
+                    } else if (elt.type() == BSONType::Array && type == DiffType::kArray) {
+                        BSONArrayBuilder subBob(builder->subarrayStart(elt.fieldNameStringData()));
+                        auto reader = stdx::get<ArrayDiffReader>(subDiff.reader);
+                        applyDiffToArray(elt.embeddedObject(), &reader, &subBob);
+                    } else {
+                        // There's a type mismatch. The diff was expecting one type but the pre
+                        // image contains a value of a different type. This means we are
+                        // re-applying a diff.
+
+                        // There must be some future operation which changed the type of this field
+                        // from object/array to something else. So we set this field to null field
+                        // and expect the future value to overwrite the value here.
+
+                        builder->appendNull(elt.fieldNameStringData());
+                    }
+
+                    // Note: There's no need to update 'fieldsToSkipInserting' here, because a
+                    // field cannot appear in both the sub-diff and insert section.
+                },
+            },
+            it->second);
+    }
+
+    // Insert remaining fields to the end.
+    for (auto&& elt : tables.fieldsToInsert) {
+        if (!fieldsToSkipInserting.count(elt.fieldNameStringData())) {
+            builder->append(elt);
+        }
+    }
+}
+
+/**
+ * Given an (optional) member of the pre image array and a modification, apply the modification and
+ * add it to the post image array in 'builder'.
+ */
+void appendNewValueForIndex(boost::optional<BSONElement> preImageValue,
+                            const ArrayDiffReader::ArrayModification& modification,
+                            BSONArrayBuilder* builder) {
+    stdx::visit(
+        visit_helper::Overloaded{
+            [builder](const BSONElement& update) { builder->append(update); },
+            [builder, &preImageValue](auto reader) {
+                if (!preImageValue) {
+                    // The pre-image's array was shorter than we expected. This means some
+                    // future oplog entry will either re-write the value of this array index
+                    // (or some parent) so we append a null and move on.
+                    builder->appendNull();
+                    return;
+                }
+
+                if constexpr (std::is_same_v<decltype(reader), ArrayDiffReader>) {
+                    if (preImageValue->type() == BSONType::Array) {
+                        BSONArrayBuilder sub(builder->subarrayStart());
+                        applyDiffToArray(preImageValue->embeddedObject(), &reader, &sub);
+                        return;
+                    }
+                } else if constexpr (std::is_same_v<decltype(reader), DocumentDiffReader>) {
+                    if (preImageValue->type() == BSONType::Object) {
+                        BSONObjBuilder sub(builder->subobjStart());
+                        applyDiffToObject(preImageValue->embeddedObject(), &reader, &sub);
+                        return;
+                    }
+                }
+
+                // The type does not match what we expected. This means some future oplog
+                // entry will either re-write the value of this array index (or some
+                // parent) so we append a null and move on.
+                builder->appendNull();
+            },
+        },
+        modification);
+}
+
+void applyDiffToArray(const BSONObj& arrayPreImage,
+                      ArrayDiffReader* reader,
+                      BSONArrayBuilder* builder) {
+    const auto resizeVal = reader->newSize();
+    // Each modification is an optional pair where the first component is the array index and the
+    // second is the modification type.
+    auto nextMod = reader->next();
+    BSONObjIterator preImageIt(arrayPreImage);
+
+    size_t idx = 0;
+    for (; preImageIt.more() && (!resizeVal || idx < *resizeVal); ++idx, ++preImageIt) {
+        if (nextMod && idx == nextMod->first) {
+            appendNewValueForIndex(*preImageIt, nextMod->second, builder);
+            nextMod = reader->next();
+        } else {
+            // This index is not in the diff so we keep the value in the pre image.
+            builder->append(*preImageIt);
+        }
+    }
+
+    // Deal with remaining fields in the diff if the pre image was too short.
+    for (; (resizeVal && idx < *resizeVal) || nextMod; ++idx) {
+        if (nextMod && idx == nextMod->first) {
+            appendNewValueForIndex(boost::none, nextMod->second, builder);
+            nextMod = reader->next();
+        } else {
+            // This field is not mentioned in the diff so we pad the post image with null.
+            builder->appendNull();
+        }
+    }
+
+    invariant(!resizeVal || *resizeVal == idx);
+}
+}  // namespace
+
+BSONObj applyDiff(const BSONObj& pre, const Diff& diff) {
+    DocumentDiffReader reader(diff);
+    BSONObjBuilder out;
+    applyDiffToObject(pre, &reader, &out);
+    return out.obj();
+}
+}  // namespace mongo::doc_diff
diff --git a/src/mongo/db/update/document_diff_applier.h b/src/mongo/db/update/document_diff_applier.h
new file mode 100644
index 00000000000..a825ee2cac9
--- /dev/null
+++ b/src/mongo/db/update/document_diff_applier.h
@@ -0,0 +1,42 @@
+/**
+ *    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 "mongo/bson/bsonobjbuilder.h"
+#include "mongo/db/update/document_diff_serialization.h"
+
+namespace mongo {
+namespace doc_diff {
+/**
+ * Applies the diff to 'pre' and returns the post image. Throws if the diff is invalid.
+ */
+BSONObj applyDiff(const BSONObj& pre, const Diff& diff);
+}  // namespace doc_diff
+}  // namespace mongo
diff --git a/src/mongo/db/update/document_diff_applier_test.cpp b/src/mongo/db/update/document_diff_applier_test.cpp
new file mode 100644
index 00000000000..5ce053a9b64
--- /dev/null
+++ b/src/mongo/db/update/document_diff_applier_test.cpp
@@ -0,0 +1,357 @@
+/**
+ *    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.
+ */
+
+#define MONGO_LOGV2_DEFAULT_COMPONENT ::mongo::logv2::LogComponent::kTest
+
+#include "mongo/platform/basic.h"
+
+#include "mongo/bson/json.h"
+#include "mongo/db/update/document_diff_applier.h"
+#include "mongo/db/update/document_diff_serialization.h"
+#include "mongo/logv2/log.h"
+#include "mongo/unittest/unittest.h"
+
+namespace mongo::doc_diff {
+namespace {
+/**
+ * Checks that applying the diff (once or twice) to 'preImage' produces the expected post image.
+ */
+void checkDiff(const BSONObj& preImage, const BSONObj& expectedPost, const Diff& diff) {
+    BSONObj postImage = applyDiff(preImage, diff);
+
+    // This *MUST* check for binary equality, which is what we enforce between replica set
+    // members. Logical equality (through woCompare() or ASSERT_BSONOBJ_EQ) is not enough to show
+    // that the applier actually works.
+    if (!expectedPost.binaryEqual(postImage)) {
+        FAIL(str::stream() << "Post image does not match expected "
+                           << "Expected " << expectedPost << " == " << postImage
+                           << ". Pre image is " << preImage);
+    }
+
+    BSONObj postImageAgain = applyDiff(postImage, diff);
+    if (!expectedPost.binaryEqual(postImageAgain)) {
+        FAIL(str::stream() << "Diff is not idempotent"
+                           << "Expected diff to be idempotent, but applying it once gives "
+                           << expectedPost << " and applying it twice gives " << postImageAgain);
+    }
+}
+
+TEST(DiffApplierTest, DeleteSimple) {
+    const BSONObj preImage(BSON("f1" << 1 << "foo" << 2 << "f2" << 3));
+
+    DocumentDiffBuilder builder;
+    builder.addDelete("f1");
+    builder.addDelete("f2");
+    builder.addDelete("f3");
+
+    auto diff = builder.release();
+
+    checkDiff(preImage, BSON("foo" << 2), diff);
+}
+
+TEST(DiffApplierTest, InsertSimple) {
+    const BSONObj preImage(BSON("f1" << 1 << "foo" << 2 << "f2" << 3));
+
+    const BSONObj storage(BSON("a" << 1 << "b" << 2));
+    DocumentDiffBuilder builder;
+    builder.addInsert("f1", storage["a"]);
+    builder.addInsert("newField", storage["b"]);
+
+    auto diff = builder.release();
+    checkDiff(preImage, BSON("foo" << 2 << "f2" << 3 << "f1" << 1 << "newField" << 2), diff);
+}
+
+TEST(DiffApplierTest, UpdateSimple) {
+    const BSONObj preImage(BSON("f1" << 0 << "foo" << 2 << "f2" << 3));
+
+    const BSONObj storage(BSON("a" << 1 << "b" << 2));
+    DocumentDiffBuilder builder;
+    builder.addUpdate("f1", storage["a"]);
+    builder.addUpdate("newField", storage["b"]);
+
+    auto diff = builder.release();
+    checkDiff(preImage, BSON("f1" << 1 << "foo" << 2 << "f2" << 3 << "newField" << 2), diff);
+}
+
+TEST(DiffApplierTest, SubObjDiffSimple) {
+    const BSONObj preImage(
+        BSON("obj" << BSON("dField" << 0 << "iField" << 0 << "uField" << 0) << "otherField" << 0));
+
+    const BSONObj storage(BSON("a" << 1 << "b" << 2));
+    DocumentDiffBuilder builder;
+    {
+        DocumentDiffBuilder sub(builder.startSubObjDiff("obj"));
+        sub.addDelete("dField");
+        sub.addInsert("iField", storage["a"]);
+        sub.addUpdate("uField", storage["b"]);
+    }
+
+    auto diff = builder.release();
+    checkDiff(
+        preImage, BSON("obj" << BSON("uField" << 2 << "iField" << 1) << "otherField" << 0), diff);
+}
+
+TEST(DiffApplierTest, SubArrayDiffSimpleWithAppend) {
+    const BSONObj preImage(BSON("arr" << BSON_ARRAY(999 << 999 << 999 << 999)));
+
+    const BSONObj storage(BSON("a" << 1 << "b" << 2));
+    DocumentDiffBuilder builder;
+    {
+        ArrayDiffBuilder sub(builder.startSubArrDiff("arr"));
+        sub.addUpdate(1, storage["a"]);
+        sub.addUpdate(4, storage["b"]);
+    }
+
+    auto diff = builder.release();
+
+    checkDiff(preImage, BSON("arr" << BSON_ARRAY(999 << 1 << 999 << 999 << 2)), diff);
+}
+
+TEST(DiffApplierTest, SubArrayDiffSimpleWithTruncate) {
+    const BSONObj preImage(BSON("arr" << BSON_ARRAY(999 << 999 << 999 << 999)));
+
+    const BSONObj storage(BSON("a" << 1 << "b" << 2));
+    DocumentDiffBuilder builder;
+    {
+        ArrayDiffBuilder sub(builder.startSubArrDiff("arr"));
+        sub.addUpdate(1, storage["a"]);
+        sub.setResize(3);
+    }
+
+    auto diff = builder.release();
+    checkDiff(preImage, BSON("arr" << BSON_ARRAY(999 << 1 << 999)), diff);
+}
+
+TEST(DiffApplierTest, SubArrayDiffSimpleWithNullPadding) {
+    const BSONObj preImage(BSON("arr" << BSON_ARRAY(0)));
+
+    BSONObj storage(BSON("a" << 1));
+    DocumentDiffBuilder builder;
+    {
+        ArrayDiffBuilder sub(builder.startSubArrDiff("arr"));
+        sub.addUpdate(3, storage["a"]);
+    }
+
+    auto diff = builder.release();
+
+    checkDiff(preImage, BSON("arr" << BSON_ARRAY(0 << NullLabeler{} << NullLabeler{} << 1)), diff);
+}
+
+TEST(DiffApplierTest, NestedSubObjUpdateScalar) {
+    BSONObj storage(BSON("a" << 1));
+    DocumentDiffBuilder builder;
+    {
+        DocumentDiffBuilder sub(builder.startSubObjDiff("subObj"));
+        {
+            DocumentDiffBuilder subSub(sub.startSubObjDiff("subObj"));
+            subSub.addUpdate("a", storage["a"]);
+        }
+    }
+
+    auto diff = builder.release();
+
+    // Check the case where the object matches the structure we expect.
+    BSONObj preImage(fromjson("{subObj: {subObj: {a: 0}}}"));
+    checkDiff(preImage, fromjson("{subObj: {subObj: {a: 1}}}"), diff);
+
+    // Check cases where the object does not match the structure we expect.
+    preImage = BSON("someOtherField" << 1);
+    checkDiff(preImage,
+              preImage,  // In this case the diff is a no-op.
+              diff);
+
+    preImage = BSON("dummyA" << 1 << "dummyB" << 2 << "subObj"
+                             << "scalar!"
+                             << "dummyC" << 3 << "dummyD" << 4);
+    checkDiff(
+        preImage, fromjson("{dummyA: 1, dummyB: 2, subObj: null, dummyC: 3, dummyD: 4}"), diff);
+
+    preImage = BSON("dummyA" << 1 << "dummyB" << 2 << "subObj"
+                             << BSON("subDummyA" << 1 << "subObj"
+                                                 << "scalar!"
+                                                 << "subDummyB" << 2)
+                             << "dummyC" << 3);
+    checkDiff(preImage,
+              fromjson("{dummyA: 1, dummyB: 2, "
+                       "subObj: {subDummyA: 1, subObj: null, subDummyB: 2}, dummyC: 3}"),
+              diff);
+}
+
+// Case where the diff contains sub diffs for several array indices.
+TEST(DiffApplierTest, UpdateArrayOfObjectsSubDiff) {
+
+    BSONObj storage(
+        BSON("uFieldNew" << 999 << "newObj" << BSON("x" << 1) << "a" << 1 << "b" << 2 << "c" << 3));
+    DocumentDiffBuilder builder;
+    {
+        builder.addDelete("dFieldA");
+        builder.addDelete("dFieldB");
+        builder.addUpdate("uField", storage["uFieldNew"]);
+
+        ArrayDiffBuilder subArr(builder.startSubArrDiff("arr"));
+        {
+            {
+                DocumentDiffBuilder subObjBuilder(subArr.startSubObjDiff(1));
+                subObjBuilder.addUpdate("a", storage["a"]);
+            }
+
+            {
+                DocumentDiffBuilder subObjBuilder(subArr.startSubObjDiff(2));
+                subObjBuilder.addUpdate("b", storage["b"]);
+            }
+
+            {
+                DocumentDiffBuilder subObjBuilder(subArr.startSubObjDiff(3));
+                subObjBuilder.addUpdate("c", storage["c"]);
+            }
+            subArr.addUpdate(4, storage["newObj"]);
+        }
+    }
+
+    auto diff = builder.release();
+
+    // Case where the object matches the structure we expect.
+    BSONObj preImage(
+        fromjson("{uField: 1, dFieldA: 1, arr: [null, {a:0}, {b:0}, {c:0}], "
+                 "dFieldB: 1}"));
+    checkDiff(preImage, fromjson("{uField: 999, arr: [null, {a:1}, {b:2}, {c:3}, {x: 1}]}"), diff);
+
+    preImage = fromjson("{uField: 1, dFieldA: 1, arr: [{a:0}, {b:0}, {c:0}, {}], dFieldB: 1}");
+    checkDiff(preImage,
+              fromjson("{uField: 999, arr: [{a: 0}, {b:0, a:1}, {c:0, b:2}, {c:3}, {x: 1}]}"),
+              diff);
+
+    // Case where the diff is a noop.
+    preImage = fromjson("{arr: [null, {a:1}, {b:2}, {c:3}, {x: 1}], uField: 999}");
+    checkDiff(preImage, preImage, diff);
+
+    // Case where the pre image has scalars in the array instead of objects. In this case we set
+    // some of the indices to null, expecting some future operation to overwrite them. Indexes with
+    // an explicit 'update' operation will be overwritten.
+    preImage = fromjson("{arr: [0,0,0,0,{x: 2}], uField: 1}");
+    checkDiff(preImage, fromjson("{arr: [0, null, null, null, {x: 1}], uField: 999}"), diff);
+
+    // Case where the pre image array is too short. Since the diff contains an array of object sub
+    // diffs, the output will be all nulls, which will presumably be overwritten by a future
+    // operation.
+    preImage = fromjson("{arr: [], uField: 1}");
+    checkDiff(preImage, fromjson("{arr: [null, null, null, null, {x: 1}], uField: 999}"), diff);
+
+    // Case where the pre image array is longer than the (presumed) post image.
+    preImage = fromjson("{arr: [0,{},{},{},4,5,6], uField: 1}");
+    checkDiff(
+        preImage, fromjson("{arr: [0, {a:1}, {b:2}, {c:3}, {x:1}, 5, 6], uField: 999}"), diff);
+
+    // Case where the pre image 'arr' field is an object instead of an array. In this
+    // situation, we know that some later operation will overwrite the field, so we set it to null
+    // ensuring that it keeps its position in the document.
+    preImage = fromjson("{dummyA: 1, arr: {foo: 1}, dummyB: 1}");
+    checkDiff(preImage, fromjson("{dummyA: 1, arr: null, dummyB: 1, uField: 999}"), diff);
+
+    // Case where pre image 'arr' field is a scalar. Again, we set it to null.
+    preImage = fromjson("{dummyA: 1, arr: 1, dummyB: 1}");
+    checkDiff(preImage, fromjson("{dummyA: 1, arr: null, dummyB: 1, uField: 999}"), diff);
+}
+
+// Case where an array diff rewrites several non contiguous indices which are objects.
+TEST(DiffApplierTest, UpdateArrayOfObjectsWithUpdateOperationNonContiguous) {
+    BSONObj storage(BSON("dummyA" << 997 << "dummyB" << BSON("newVal" << 998) << "dummyC" << 999));
+    DocumentDiffBuilder builder;
+    {
+        ArrayDiffBuilder subArr(builder.startSubArrDiff("arr"));
+        {
+            subArr.addUpdate(1, storage["dummyA"]);
+            subArr.addUpdate(2, storage["dummyB"]);
+            subArr.addUpdate(5, storage["dummyC"]);
+        }
+    }
+
+    auto diff = builder.release();
+
+    // Case where the object matches the structure we expect.
+    BSONObj preImage(fromjson("{arr: [null, {}, {}, {}, {}, {}]}"));
+    checkDiff(preImage, fromjson("{arr: [null, 997, {newVal: 998}, {}, {}, 999]}"), diff);
+
+    // Case where null padding is necessary before the last element.
+    preImage = fromjson("{arr: [{}, {}, {}, {}]}");
+    checkDiff(preImage, fromjson("{arr: [{}, 997, {newVal: 998}, {}, null, 999]}"), diff);
+
+    // Case where the diff is a noop.
+    preImage = fromjson("{arr: [{}, 997, {newVal: 998}, {}, {}, 999]}");
+    checkDiff(preImage, preImage, diff);
+
+    // Case where the pre image array is longer than the (presumed) post image.
+    preImage = fromjson("{arr: [0,1,2,3,4,5,6]}");
+    checkDiff(preImage, fromjson("{arr: [0, 997, {newVal: 998}, 3, 4, 999, 6]}"), diff);
+
+    // Case where the pre image array contains sub-arrays. The sub-arrays will get overwritten.
+    preImage = fromjson("{arr: [0, 1, [], [], ['a', 'b'], 5, 6]}");
+    checkDiff(preImage, fromjson("{arr: [0, 997, {newVal: 998}, [], ['a', 'b'], 999, 6]}"), diff);
+
+    // Case where the pre image array contains objects. The objects will be replaced
+    preImage = fromjson("{arr: [0, {x:1}, 2, 3, {x:1}, 5, 6]}");
+    checkDiff(preImage, fromjson("{arr: [0, 997, {newVal: 998}, 3, {x:1}, 999, 6]}"), diff);
+
+    // Case where 'arr' field is an object. The type mismatch implies that a future operation will
+    // re-write the field, so it is set to null.
+    preImage = fromjson("{arr: {x: 1}}");
+    checkDiff(preImage, fromjson("{arr: null}"), diff);
+
+    // Case where 'arr' field is a scalar. The type mismatch implies that a future operation will
+    // re-write the field, so it is set to null.
+    preImage = fromjson("{arr: 'scalar!'}");
+    checkDiff(preImage, fromjson("{arr: null}"), diff);
+
+    // Case where the pre image 'arr' field is an object instead of an array. In this
+    // situation, we know that some later operation will overwrite the field, so we set it to null
+    // ensuring that it keeps its position in the document.
+    preImage = fromjson("{dummyA: 1, arr: {foo: 1}, dummyB: 1}");
+    checkDiff(preImage, fromjson("{dummyA: 1, arr: null, dummyB: 1}"), diff);
+
+    // Case where pre image 'arr' field is a scalar. Again, we set it to null.
+    preImage = fromjson("{dummyA: 1, arr: 1, dummyB: 1}");
+    checkDiff(preImage, fromjson("{dummyA: 1, arr: null, dummyB: 1}"), diff);
+}
+
+TEST(DiffApplierTest, DiffWithDuplicateFields) {
+    BSONObj diff = fromjson("{d: {dupField: false}, u: {dupField: 'new value'}}");
+    ASSERT_THROWS_CODE(applyDiff(BSONObj(), diff), DBException, 4728000);
+}
+
+TEST(DiffApplierTest, EmptyDiff) {
+    BSONObj emptyDiff;
+    ASSERT_THROWS_CODE(applyDiff(BSONObj(), emptyDiff), DBException, 4770500);
+}
+
+TEST(DiffApplierTest, ArrayDiffAtTop) {
+    BSONObj arrDiff = fromjson("{a: true, l: 5, '0': {d: false}}");
+    ASSERT_THROWS_CODE(applyDiff(BSONObj(), arrDiff), DBException, 4770503);
+}
+}  // namespace
+}  // namespace mongo::doc_diff