SERVER-16801 Require strict equality for $set no-op checks

(cherry picked from commit a7e243500cbf11d1e153f55b551c86713ddf2a9b)

10 files changed, 431 insertions, 33 deletions

diff --git a/jstests/core/index_type_change.js b/jstests/core/index_type_change.js
new file mode 100644
index 00000000000..0c95828ae57
--- /dev/null
+++ b/jstests/core/index_type_change.js
@@ -0,0 +1,37 @@
+/**
+ * Tests that replacing a document with an equivalent document with different types for the fields
+ * will update the index entries associated with that document.
+ */
+
+load("jstests/libs/analyze_plan.js");  // For 'isIndexOnly'.
+
+(function() {
+    "use strict";
+
+    var coll = db.index_type_change;
+    coll.drop();
+    assert.commandWorked(coll.ensureIndex({a: 1}));
+
+    assert.writeOK(coll.insert({a: 2}));
+    assert.eq(1, coll.find({a: {$type: "double"}}).itcount());
+
+    var newVal = new NumberLong(2);
+    var res = coll.update({}, {a: newVal});  // Replacement update.
+    assert.writeOK(res);
+    assert.eq(res.nMatched, 1);
+    if (coll.getMongo().writeMode() == "commands")
+        assert.eq(res.nModified, 1);
+
+    // Make sure it actually changed the type.
+    assert.eq(1, coll.find({a: {$type: "long"}}).itcount());
+
+    // Now use a covered query to ensure the index entry has been updated.
+
+    // First make sure it's actually using a covered index scan.
+    var explain = coll.explain().find({a: 2}, {_id: 0, a: 1});
+    assert(isIndexOnly(explain));
+
+    var updated = coll.findOne({a: 2}, {_id: 0, a: 1});
+
+    assert(updated.a instanceof NumberLong, "Index entry did not change type");
+})();
diff --git a/jstests/core/set_type_change.js b/jstests/core/set_type_change.js
new file mode 100644
index 00000000000..1f24a7c953a
--- /dev/null
+++ b/jstests/core/set_type_change.js
@@ -0,0 +1,26 @@
+/**
+ * Tests that using the $set update modifier to change only the type of a field will actually update
+ * the document, including any relevant indices.
+ */
+
+load("jstests/libs/analyze_plan.js");  // For 'isIndexOnly'.
+
+(function() {
+    "use strict";
+
+    var coll = db.set_type_change;
+    coll.drop();
+    assert.commandWorked(coll.ensureIndex({a: 1}));
+
+    assert.writeOK(coll.insert({a: 2}));
+
+    var newVal = new NumberLong(2);
+    var res = coll.update({}, {$set: {a: newVal}});
+    assert.eq(res.nMatched, 1);
+    if (coll.getMongo().writeMode() == "commands")
+        assert.eq(res.nModified, 1);
+
+    // Make sure it actually changed the type.
+    var updated = coll.findOne();
+    assert(updated.a instanceof NumberLong, "$set did not update type of value: " + updated.a);
+})();
diff --git a/src/mongo/bson/bsonelement.cpp b/src/mongo/bson/bsonelement.cpp
index 5eb40a6bd73..e5091dcae92 100644
--- a/src/mongo/bson/bsonelement.cpp
+++ b/src/mongo/bson/bsonelement.cpp
@@ -394,6 +394,31 @@ int BSONElement::woCompare(const BSONElement& e, bool considerFieldName) const {
     return x;
 }
 
+bool BSONElement::binaryEqual(const BSONElement& rhs) const {
+    const int elemSize = size();
+
+    if (elemSize != rhs.size()) {
+        return false;
+    }
+
+    return (elemSize == 0) || (memcmp(data, rhs.rawdata(), elemSize) == 0);
+}
+
+bool BSONElement::binaryEqualValues(const BSONElement& rhs) const {
+    // The binaryEqual method above implicitly compares the type, but we need to do so explicitly
+    // here. It doesn't make sense to consider to BSONElement objects as binaryEqual if they have
+    // the same bit pattern but different types (consider an integer and a double).
+    if (type() != rhs.type())
+        return false;
+
+    const int valueSize = valuesize();
+    if (valueSize != rhs.valuesize()) {
+        return false;
+    }
+
+    return (valueSize == 0) || (memcmp(value(), rhs.value(), valueSize) == 0);
+}
+
 BSONObj BSONElement::embeddedObjectUserCheck() const {
     if (MONGO_likely(isABSONObj()))
         return BSONObj(value());
diff --git a/src/mongo/bson/bsonelement.h b/src/mongo/bson/bsonelement.h
index ccbdd9f72f5..8a2b26e3751 100644
--- a/src/mongo/bson/bsonelement.h
+++ b/src/mongo/bson/bsonelement.h
@@ -481,6 +481,20 @@ public:
         return !operator==(r);
     }
 
+    /**
+     * Compares the raw bytes of the two BSONElements, including the field names. This will treat
+     * different types (e.g. integers and doubles) as distinct values, even if they have the same
+     * field name and bit pattern in the value portion of the BSON element.
+     */
+    bool binaryEqual(const BSONElement& rhs) const;
+
+    /**
+     * Compares the raw bytes of the two BSONElements, excluding the field names. This will treat
+     * different types (e.g integers and doubles) as distinct values, even if they have the same bit
+     * pattern in the value portion of the BSON element.
+     */
+    bool binaryEqualValues(const BSONElement& rhs) const;
+
     /** Well ordered comparison.
         @return <0: l<r. 0:l==r. >0:l>r
         order by type, field name, and field value.
diff --git a/src/mongo/db/index/index_access_method.cpp b/src/mongo/db/index/index_access_method.cpp
index d731f9cbfed..7c06793d3ea 100644
--- a/src/mongo/db/index/index_access_method.cpp
+++ b/src/mongo/db/index/index_access_method.cpp
@@ -33,6 +33,7 @@
 #include "mongo/db/index/btree_access_method.h"
 
 #include <vector>
+#include <utility>
 
 #include "mongo/base/error_codes.h"
 #include "mongo/base/status.h"
@@ -50,6 +51,7 @@
 namespace mongo {
 
 using std::endl;
+using std::pair;
 using std::set;
 using std::vector;
 
@@ -191,26 +193,6 @@ Status IndexAccessMethod::remove(OperationContext* txn,
     return Status::OK();
 }
 
-// Return keys in l that are not in r.
-// Lifted basically verbatim from elsewhere.
-static void setDifference(const BSONObjSet& l, const BSONObjSet& r, vector<BSONObj*>* diff) {
-    // l and r must use the same ordering spec.
-    verify(l.key_comp().order() == r.key_comp().order());
-    BSONObjSet::const_iterator i = l.begin();
-    BSONObjSet::const_iterator j = r.begin();
-    while (1) {
-        if (i == l.end())
-            break;
-        while (j != r.end() && j->woCompare(*i) < 0)
-            j++;
-        if (j == r.end() || i->woCompare(*j) != 0) {
-            const BSONObj* jo = &*i;
-            diff->push_back((BSONObj*)jo);
-        }
-        i++;
-    }
-}
-
 Status IndexAccessMethod::initializeAsEmpty(OperationContext* txn) {
     return _newInterface->initAsEmpty(txn);
 }
@@ -268,6 +250,42 @@ long long IndexAccessMethod::getSpaceUsedBytes(OperationContext* txn) const {
     return _newInterface->getSpaceUsedBytes(txn);
 }
 
+pair<vector<BSONObj>, vector<BSONObj>> IndexAccessMethod::setDifference(const BSONObjSet& left,
+                                                                        const BSONObjSet& right) {
+    // Two iterators to traverse the two sets in sorted order.
+    auto leftIt = left.begin();
+    auto rightIt = right.begin();
+    vector<BSONObj> onlyLeft;
+    vector<BSONObj> onlyRight;
+
+    while (leftIt != left.end() && rightIt != right.end()) {
+        const int cmp = leftIt->woCompare(*rightIt);
+        if (cmp == 0) {
+            // 'leftIt' and 'rightIt' compare equal using woCompare(), but may not be identical,
+            // which should result in an index change.
+            if (!leftIt->binaryEqual(*rightIt)) {
+                onlyLeft.push_back(*leftIt);
+                onlyRight.push_back(*rightIt);
+            }
+            ++leftIt;
+            ++rightIt;
+            continue;
+        } else if (cmp > 0) {
+            onlyRight.push_back(*rightIt);
+            ++rightIt;
+        } else {
+            onlyLeft.push_back(*leftIt);
+            ++leftIt;
+        }
+    }
+
+    // Add the rest of 'left' to 'onlyLeft', and the rest of 'right' to 'onlyRight', if any.
+    onlyLeft.insert(onlyLeft.end(), leftIt, left.end());
+    onlyRight.insert(onlyRight.end(), rightIt, right.end());
+
+    return {std::move(onlyLeft), std::move(onlyRight)};
+}
+
 Status IndexAccessMethod::validateUpdate(OperationContext* txn,
                                          const BSONObj& from,
                                          const BSONObj& to,
@@ -282,8 +300,7 @@ Status IndexAccessMethod::validateUpdate(OperationContext* txn,
     ticket->loc = record;
     ticket->dupsAllowed = options.dupsAllowed;
 
-    setDifference(ticket->oldKeys, ticket->newKeys, &ticket->removed);
-    setDifference(ticket->newKeys, ticket->oldKeys, &ticket->added);
+    std::tie(ticket->removed, ticket->added) = setDifference(ticket->oldKeys, ticket->newKeys);
 
     ticket->_isValid = true;
 
@@ -302,12 +319,11 @@ Status IndexAccessMethod::update(OperationContext* txn,
     }
 
     for (size_t i = 0; i < ticket.removed.size(); ++i) {
-        _newInterface->unindex(txn, *ticket.removed[i], ticket.loc, ticket.dupsAllowed);
+        _newInterface->unindex(txn, ticket.removed[i], ticket.loc, ticket.dupsAllowed);
     }
 
     for (size_t i = 0; i < ticket.added.size(); ++i) {
-        Status status =
-            _newInterface->insert(txn, *ticket.added[i], ticket.loc, ticket.dupsAllowed);
+        Status status = _newInterface->insert(txn, ticket.added[i], ticket.loc, ticket.dupsAllowed);
         if (!status.isOK()) {
             if (status.code() == ErrorCodes::KeyTooLong && ignoreKeyTooLong(txn)) {
                 // Ignore.
diff --git a/src/mongo/db/index/index_access_method.h b/src/mongo/db/index/index_access_method.h
index df62c4ae937..401f0dbe0e4 100644
--- a/src/mongo/db/index/index_access_method.h
+++ b/src/mongo/db/index/index_access_method.h
@@ -239,6 +239,17 @@ public:
      */
     virtual void getKeys(const BSONObj& obj, BSONObjSet* keys) const = 0;
 
+    /**
+     * Splits the sets 'left' and 'right' into two vectors, the first containing the elements that
+     * only appeared in 'left', and the second containing only elements that appeared in 'right'.
+     *
+     * Note this considers objects which are not identical as distinct objects. For example,
+     * setDifference({BSON("a" << 0.0)}, {BSON("a" << 0LL)}) would result in the pair
+     * ( {BSON("a" << 0.0)}, {BSON("a" << 0LL)} ).
+     */
+    static std::pair<std::vector<BSONObj>, std::vector<BSONObj>> setDifference(
+        const BSONObjSet& left, const BSONObjSet& right);
+
 protected:
     // Determines whether it's OK to ignore ErrorCodes::KeyTooLong for this OperationContext
     bool ignoreKeyTooLong(OperationContext* txn);
@@ -269,9 +280,8 @@ private:
     BSONObjSet oldKeys;
     BSONObjSet newKeys;
 
-    // These point into the sets oldKeys and newKeys.
-    std::vector<BSONObj*> removed;
-    std::vector<BSONObj*> added;
+    std::vector<BSONObj> removed;
+    std::vector<BSONObj> added;
 
     RecordId loc;
     bool dupsAllowed;
diff --git a/src/mongo/db/ops/modifier_set.cpp b/src/mongo/db/ops/modifier_set.cpp
index 93abc04f892..c6966fae079 100644
--- a/src/mongo/db/ops/modifier_set.cpp
+++ b/src/mongo/db/ops/modifier_set.cpp
@@ -152,16 +152,24 @@ Status ModifierSet::prepare(mutablebson::Element root,
     // in-place and no-op logic
     //
 
-    // If the field path is not fully present, then this mod cannot be in place, nor is a
-    // noOp.
+    // If the field path is not fully present, then this mod cannot be in place, nor is it a noOp.
     if (!_preparedState->elemFound.ok() || _preparedState->idxFound < (_fieldRef.numParts() - 1)) {
         return Status::OK();
     }
 
-    // If the value being $set is the same as the one already in the doc, than this is a
-    // noOp.
+    // If the value being $set is the same as the one already in the doc, than this is a noOp. We
+    // use binary equality to compare so that any change to the document is considered, unlike using
+    // a comparison that winds up in woCompare (see SERVER-16801). In the case where elemFound
+    // doesn't have a serialized representation, we just declare the operation to not be a
+    // no-op. This is potentially a missed optimization, but is unlikely to cause much pain since in
+    // the normal update workflow we only admit one modification on any path from a leaf to the
+    // document root. In that domain, hasValue will always be true. We may encounter a
+    // non-serialized elemFound in the case where our base document is the result of calling
+    // populateDocumentWithQueryFields, so this could cause us to do slightly more work than
+    // strictly necessary in the case where an update (w upsert:true) becomes an insert.
     if (_preparedState->elemFound.ok() && _preparedState->idxFound == (_fieldRef.numParts() - 1) &&
-        _preparedState->elemFound.compareWithBSONElement(_val, false /*ignore field*/) == 0) {
+        _preparedState->elemFound.hasValue() &&
+        _preparedState->elemFound.getValue().binaryEqualValues(_val)) {
         execInfo->noOp = _preparedState->noOp = true;
     }
 
diff --git a/src/mongo/db/ops/modifier_set_test.cpp b/src/mongo/db/ops/modifier_set_test.cpp
index 76dbbeae0e8..1579b096722 100644
--- a/src/mongo/db/ops/modifier_set_test.cpp
+++ b/src/mongo/db/ops/modifier_set_test.cpp
@@ -119,6 +119,33 @@ TEST(SimpleMod, PrepareNoOp) {
     ASSERT_TRUE(execInfo.noOp);
 }
 
+TEST(SimpleMod, PrepareNotNoOp) {
+    Document doc(fromjson("{a: NumberInt(2)}"));
+    Mod setMod(fromjson("{$set: {a: NumberLong(2)}}"));
+
+    ModifierInterface::ExecInfo execInfo;
+    ASSERT_OK(setMod.prepare(doc.root(), "", &execInfo));
+
+    ASSERT_EQUALS(execInfo.fieldRef[0]->dottedField(), "a");
+    ASSERT_FALSE(execInfo.noOp);
+}
+
+TEST(SimpleMod, PrepareIdentityOpOnDeserializedIsNotANoOp) {
+    Document doc(fromjson("{a: { b: NumberInt(0)}}"));
+
+    // Apply a mutation to the document that will make it non-serialized.
+    doc.root()["a"]["b"].setValueInt(2);
+
+    // Apply an op that would be a no-op.
+    Mod setMod(fromjson("{$set: {a: {b : NumberInt(2)}}}"));
+
+    ModifierInterface::ExecInfo execInfo;
+    ASSERT_OK(setMod.prepare(doc.root(), "", &execInfo));
+
+    ASSERT_EQUALS(execInfo.fieldRef[0]->dottedField(), "a");
+    ASSERT_FALSE(execInfo.noOp);
+}
+
 TEST(SimpleMod, PrepareSetOnInsert) {
     Document doc(fromjson("{a: 1}"));
     Mod setMod(fromjson("{$setOnInsert: {a: 2}}"));
@@ -236,6 +263,17 @@ TEST(DottedMod, PrepareNoOp) {
     ASSERT_TRUE(execInfo.noOp);
 }
 
+TEST(DottedMod, PrepareNotNoOp) {
+    Document doc(fromjson("{a: {b: NumberLong(2)}}"));
+    Mod setMod(fromjson("{$set: {'a.b': NumberInt(2)}}"));
+
+    ModifierInterface::ExecInfo execInfo;
+    ASSERT_OK(setMod.prepare(doc.root(), "", &execInfo));
+
+    ASSERT_EQUALS(execInfo.fieldRef[0]->dottedField(), "a.b");
+    ASSERT_FALSE(execInfo.noOp);
+}
+
 TEST(DottedMod, PreparePathNotViable) {
     Document doc(fromjson("{a:1}"));
     Mod setMod(fromjson("{$set: {'a.b': 2}}"));
@@ -372,6 +410,17 @@ TEST(IndexedMod, PrepareNoOp) {
     ASSERT_TRUE(execInfo.noOp);
 }
 
+TEST(IndexedMod, PrepareNotNoOp) {
+    Document doc(fromjson("{a: [{b: 0},{b: 1},{b: 2.0}]}"));
+    Mod setMod(fromjson("{$set: {'a.2.b': NumberInt(2)}}"));
+
+    ModifierInterface::ExecInfo execInfo;
+    ASSERT_OK(setMod.prepare(doc.root(), "", &execInfo));
+
+    ASSERT_EQUALS(execInfo.fieldRef[0]->dottedField(), "a.2.b");
+    ASSERT_FALSE(execInfo.noOp);
+}
+
 TEST(IndexedMod, PrepareNonViablePath) {
     Document doc(fromjson("{a: 0}"));
     Mod setMod(fromjson("{$set: {'a.2.b': 2}}"));
diff --git a/src/mongo/dbtests/SConscript b/src/mongo/dbtests/SConscript
index 5e9ad0a9a66..f56098bfa1f 100644
--- a/src/mongo/dbtests/SConscript
+++ b/src/mongo/dbtests/SConscript
@@ -71,6 +71,7 @@ dbtest = env.Program(
         'executor_registry.cpp',
         'extensions_callback_real_test.cpp',
         'gle_test.cpp',
+        'index_access_method_test.cpp',
         'indexcatalogtests.cpp',
         'indexupdatetests.cpp',
         'jsobjtests.cpp',
diff --git a/src/mongo/dbtests/index_access_method_test.cpp b/src/mongo/dbtests/index_access_method_test.cpp
new file mode 100644
index 00000000000..e9cbf32fac1
--- /dev/null
+++ b/src/mongo/dbtests/index_access_method_test.cpp
@@ -0,0 +1,212 @@
+/**
+ *    Copyright (C) 2015 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.
+ */
+
+#include "mongo/platform/basic.h"
+
+#include "mongo/db/index/index_access_method.h"
+#include "mongo/unittest/unittest.h"
+#include "mongo/bson/bsonobj.h"
+#include "mongo/db/json.h"
+
+namespace mongo {
+
+namespace {
+using std::vector;
+
+TEST(IndexAccessMethodSetDifference, EmptyInputsShouldHaveNoDifference) {
+    BSONObjSet left = {};
+    BSONObjSet right = {};
+    auto diff = IndexAccessMethod::setDifference(left, right);
+    ASSERT_EQ(0UL, diff.first.size());
+    ASSERT_EQ(0UL, diff.second.size());
+}
+
+TEST(IndexAccessMethodSetDifference, EmptyLeftShouldHaveNoDifference) {
+    BSONObjSet left = {};
+    BSONObjSet right = {BSON("" << 0)};
+    auto diff = IndexAccessMethod::setDifference(left, right);
+    ASSERT_EQ(0UL, diff.first.size());
+    ASSERT_EQ(1UL, diff.second.size());
+}
+
+TEST(IndexAccessMethodSetDifference, EmptyRightShouldReturnAllOfLeft) {
+    BSONObjSet left = {BSON("" << 0), BSON("" << 1)};
+    BSONObjSet right = {};
+    auto diff = IndexAccessMethod::setDifference(left, right);
+    ASSERT_EQ(2UL, diff.first.size());
+    ASSERT_EQ(0UL, diff.second.size());
+}
+
+TEST(IndexAccessMethodSetDifference, IdenticalSetsShouldHaveNoDifference) {
+    BSONObjSet left = {BSON("" << 0),
+                       BSON(""
+                            << "string"),
+                       BSON("" << BSONNULL)};
+    BSONObjSet right = {BSON("" << 0),
+                        BSON(""
+                             << "string"),
+                        BSON("" << BSONNULL)};
+    auto diff = IndexAccessMethod::setDifference(left, right);
+    ASSERT_EQ(0UL, diff.first.size());
+    ASSERT_EQ(0UL, diff.second.size());
+}
+
+//
+// Number type comparisons.
+//
+
+void assertDistinct(BSONObj left, BSONObj right) {
+    BSONObjSet leftSet = {left};
+    BSONObjSet rightSet = {right};
+    auto diff = IndexAccessMethod::setDifference(leftSet, rightSet);
+    ASSERT_EQ(1UL, diff.first.size());
+    ASSERT_EQ(1UL, diff.second.size());
+}
+
+TEST(IndexAccessMethodSetDifference, ZerosOfDifferentTypesAreNotEquivalent) {
+    const BSONObj intObj = BSON("" << static_cast<int>(0));
+    const BSONObj longObj = BSON("" << static_cast<long long>(0));
+    const BSONObj doubleObj = BSON("" << static_cast<double>(0.0));
+
+    // These should compare equal with woCompare(), but should not be treated equal by the index.
+    ASSERT_EQ(0, intObj.woCompare(longObj));
+    ASSERT_EQ(0, longObj.woCompare(doubleObj));
+
+    assertDistinct(intObj, longObj);
+    assertDistinct(intObj, doubleObj);
+
+    assertDistinct(longObj, intObj);
+    assertDistinct(longObj, doubleObj);
+
+    assertDistinct(doubleObj, intObj);
+    assertDistinct(doubleObj, longObj);
+
+    if (mongo::Decimal128::enabled) {
+        const BSONObj decimalObj = fromjson("{'': NumberDecimal('0')}");
+
+        ASSERT_EQ(0, doubleObj.woCompare(decimalObj));
+
+        assertDistinct(intObj, decimalObj);
+        assertDistinct(longObj, decimalObj);
+        assertDistinct(doubleObj, decimalObj);
+
+        assertDistinct(decimalObj, intObj);
+        assertDistinct(decimalObj, longObj);
+        assertDistinct(decimalObj, doubleObj);
+    }
+}
+
+TEST(IndexAccessMethodSetDifference, ShouldDetectOneDifferenceAmongManySimilarities) {
+    BSONObjSet left = {BSON("" << 0),
+                       BSON(""
+                            << "string"),
+                       BSON("" << BSONNULL),
+                       BSON("" << static_cast<long long>(1)),  // This is different.
+                       BSON("" << BSON("sub"
+                                       << "document")),
+                       BSON("" << BSON_ARRAY(1 << "hi" << 42))};
+    BSONObjSet right = {BSON("" << 0),
+                        BSON(""
+                             << "string"),
+                        BSON("" << BSONNULL),
+                        BSON("" << static_cast<double>(1.0)),  // This is different.
+                        BSON("" << BSON("sub"
+                                        << "document")),
+                        BSON("" << BSON_ARRAY(1 << "hi" << 42))};
+    auto diff = IndexAccessMethod::setDifference(left, right);
+    ASSERT_EQUALS(1UL, diff.first.size());
+    ASSERT_EQUALS(1UL, diff.second.size());
+}
+
+TEST(IndexAccessMethodSetDifference, SingleObjInLeftShouldFindCorrespondingObjInRight) {
+    BSONObjSet left = {BSON("" << 2)};
+    BSONObjSet right = {BSON("" << 1), BSON("" << 2), BSON("" << 3)};
+    auto diff = IndexAccessMethod::setDifference(left, right);
+    ASSERT_EQUALS(0UL, diff.first.size());
+    ASSERT_EQUALS(2UL, diff.second.size());
+}
+
+TEST(IndexAccessMethodSetDifference, SingleObjInRightShouldFindCorrespondingObjInLeft) {
+    BSONObjSet left = {BSON("" << 1), BSON("" << 2), BSON("" << 3)};
+    BSONObjSet right = {BSON("" << 2)};
+    auto diff = IndexAccessMethod::setDifference(left, right);
+    ASSERT_EQUALS(2UL, diff.first.size());
+    ASSERT_EQUALS(0UL, diff.second.size());
+}
+
+TEST(IndexAccessMethodSetDifference, LeftSetAllSmallerThanRightShouldBeDisjoint) {
+    BSONObjSet left = {BSON("" << 1), BSON("" << 2), BSON("" << 3)};
+    BSONObjSet right = {BSON("" << 4), BSON("" << 5), BSON("" << 6)};
+    auto diff = IndexAccessMethod::setDifference(left, right);
+    ASSERT_EQUALS(3UL, diff.first.size());
+    ASSERT_EQUALS(3UL, diff.second.size());
+    for (auto&& obj : diff.first) {
+        ASSERT(left.find(obj) != left.end());
+    }
+    for (auto&& obj : diff.second) {
+        ASSERT(right.find(obj) != right.end());
+    }
+}
+
+TEST(IndexAccessMethodSetDifference, LeftSetAllLargerThanRightShouldBeDisjoint) {
+    BSONObjSet left = {BSON("" << 4), BSON("" << 5), BSON("" << 6)};
+    BSONObjSet right = {BSON("" << 1), BSON("" << 2), BSON("" << 3)};
+    auto diff = IndexAccessMethod::setDifference(left, right);
+    ASSERT_EQUALS(3UL, diff.first.size());
+    ASSERT_EQUALS(3UL, diff.second.size());
+    for (auto&& obj : diff.first) {
+        ASSERT(left.find(obj) != left.end());
+    }
+    for (auto&& obj : diff.second) {
+        ASSERT(right.find(obj) != right.end());
+    }
+}
+
+TEST(IndexAccessMethodSetDifference, ShouldNotReportOverlapsFromNonDisjointSets) {
+    BSONObjSet left = {BSON("" << 0), BSON("" << 1), BSON("" << 4), BSON("" << 6)};
+    BSONObjSet right = {BSON("" << -1), BSON("" << 1), BSON("" << 3), BSON("" << 4), BSON("" << 7)};
+    auto diff = IndexAccessMethod::setDifference(left, right);
+    ASSERT_EQUALS(2UL, diff.first.size());   // 0, 6.
+    ASSERT_EQUALS(3UL, diff.second.size());  // -1, 3, 7.
+    for (auto&& obj : diff.first) {
+        ASSERT(left.find(obj) != left.end());
+        // Make sure it's not in the intersection.
+        ASSERT(obj != BSON("" << 1));
+        ASSERT(obj != BSON("" << 4));
+    }
+    for (auto&& obj : diff.second) {
+        ASSERT(right.find(obj) != right.end());
+        // Make sure it's not in the intersection.
+        ASSERT(obj != BSON("" << 1));
+        ASSERT(obj != BSON("" << 4));
+    }
+}
+
+}  // namespace
+
+}  // namespace mongo