SERVER-24508 BSONElement::ComparatorInterface

27 files changed, 696 insertions, 208 deletions

diff --git a/src/mongo/SConscript b/src/mongo/SConscript
index d9f421ece0f..efb9955a979 100644
--- a/src/mongo/SConscript
+++ b/src/mongo/SConscript
@@ -77,6 +77,7 @@ baseSource=[
     'bson/bsontypes.cpp',
     'bson/json.cpp',
     'bson/oid.cpp',
+    'bson/simple_bsonelement_comparator.cpp',
     'bson/simple_bsonobj_comparator.cpp',
     'bson/timestamp.cpp',
     'logger/component_message_log_domain.cpp',
diff --git a/src/mongo/bson/bson_comparator_interface_base.h b/src/mongo/bson/bson_comparator_interface_base.h
new file mode 100644
index 00000000000..eba3a9a36d7
--- /dev/null
+++ b/src/mongo/bson/bson_comparator_interface_base.h
@@ -0,0 +1,199 @@
+/**
+ *    Copyright (C) 2016 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 <initializer_list>
+#include <map>
+#include <set>
+#include <unordered_map>
+#include <unordered_set>
+
+#include "mongo/base/disallow_copying.h"
+#include "mongo/util/assert_util.h"
+
+namespace mongo {
+
+/**
+ * Base class for the BSONObj and BSONElement comparator interfaces.
+ */
+template <typename T>
+class BSONComparatorInterfaceBase {
+    MONGO_DISALLOW_COPYING(BSONComparatorInterfaceBase);
+
+public:
+    /**
+     * A deferred comparison between two objects of type T, which can be converted into a boolean
+     * via the evaluate() method.
+     */
+    struct DeferredComparison {
+        enum class Type {
+            kLT,
+            kLTE,
+            kEQ,
+            kGT,
+            kGTE,
+            kNE,
+        };
+
+        DeferredComparison(Type type, const T& lhs, const T& rhs)
+            : type(type), lhs(lhs), rhs(rhs) {}
+
+        Type type;
+        const T& lhs;
+        const T& rhs;
+    };
+
+    /**
+     * Functor compatible for use with ordered STL containers.
+     */
+    class LessThan {
+    public:
+        explicit LessThan(const BSONComparatorInterfaceBase* comparator)
+            : _comparator(comparator) {}
+
+        bool operator()(const T& lhs, const T& rhs) const {
+            return _comparator->compare(lhs, rhs) < 0;
+        }
+
+    private:
+        const BSONComparatorInterfaceBase* _comparator;
+    };
+
+    /**
+     * Functor compatible for use with unordered STL containers.
+     */
+    class EqualTo {
+    public:
+        explicit EqualTo(const BSONComparatorInterfaceBase* comparator) : _comparator(comparator) {}
+
+        bool operator()(const T& lhs, const T& rhs) const {
+            return _comparator->compare(lhs, rhs) == 0;
+        }
+
+    private:
+        const BSONComparatorInterfaceBase* _comparator;
+    };
+
+    /**
+     * Function object for hashing with respect to this comparator.
+     *
+     * TODO SERVER-23990: Make BSONObj/BSONElement hasher collation-aware.
+     */
+    class Hasher {
+    public:
+        size_t operator()(const T& toHash) const {
+            return _hasher(toHash);
+        }
+
+    private:
+        typename T::Hasher _hasher;
+    };
+
+    using Set = std::set<T, LessThan>;
+
+    using UnorderedSet = std::unordered_set<T, Hasher, EqualTo>;
+
+    template <typename ValueType>
+    using Map = std::map<T, ValueType, LessThan>;
+
+    template <typename ValueType>
+    using UnorderedMap = std::unordered_map<T, ValueType, Hasher, EqualTo>;
+
+    virtual ~BSONComparatorInterfaceBase() = default;
+
+    /**
+     * Compares two BSONObj objects. Returns <0, 0, >0 if 'lhs' < 'rhs', 'lhs' == 'rhs', or 'lhs' >
+     * 'rhs' respectively.
+     */
+    virtual int compare(const T& lhs, const T& rhs) const = 0;
+
+    /**
+     * Evaluates a deferred comparison object generated by invocation of one of the BSONObj operator
+     * overloads for relops.
+     */
+    bool evaluate(DeferredComparison deferredComparison) const {
+        int cmp = compare(deferredComparison.lhs, deferredComparison.rhs);
+        switch (deferredComparison.type) {
+            case DeferredComparison::Type::kLT:
+                return cmp < 0;
+            case DeferredComparison::Type::kLTE:
+                return cmp <= 0;
+            case DeferredComparison::Type::kEQ:
+                return cmp == 0;
+            case DeferredComparison::Type::kGT:
+                return cmp > 0;
+            case DeferredComparison::Type::kGTE:
+                return cmp >= 0;
+            case DeferredComparison::Type::kNE:
+                return cmp != 0;
+        }
+
+        MONGO_UNREACHABLE;
+    }
+
+    /**
+     * Returns a function object which computes whether one BSONObj is less than another under this
+     * comparator. This comparator must outlive the returned function object.
+     */
+    LessThan makeLessThan() const {
+        return LessThan(this);
+    }
+
+    /**
+     * Returns a function object which computes whether one BSONObj is equal to another under this
+     * comparator. This comparator must outlive the returned function object.
+     */
+    EqualTo makeEqualTo() const {
+        return EqualTo(this);
+    }
+
+protected:
+    constexpr BSONComparatorInterfaceBase() = default;
+
+    Set makeSet(std::initializer_list<T> init = {}) const {
+        return Set(init, LessThan(this));
+    }
+
+    UnorderedSet makeUnorderedSet(std::initializer_list<T> init = {}) const {
+        return UnorderedSet(init, 0, Hasher(), EqualTo(this));
+    }
+
+    template <typename ValueType>
+    Map<ValueType> makeMap(std::initializer_list<std::pair<const T, ValueType>> init = {}) const {
+        return Map<ValueType>(init, LessThan(this));
+    }
+
+    template <typename ValueType>
+    UnorderedMap<ValueType> makeBSONObjIndexedUnorderedMap(
+        std::initializer_list<std::pair<const T, ValueType>> init = {}) const {
+        return UnorderedMap<ValueType>(init, 0, Hasher(), EqualTo(this));
+    }
+};
+
+}  // namespace mongo
diff --git a/src/mongo/bson/bsonelement.h b/src/mongo/bson/bsonelement.h
index 4b1f776696f..783f4dd4a20 100644
--- a/src/mongo/bson/bsonelement.h
+++ b/src/mongo/bson/bsonelement.h
@@ -38,6 +38,7 @@
 #include "mongo/base/data_type_endian.h"
 #include "mongo/base/data_view.h"
 #include "mongo/base/string_data_comparator_interface.h"
+#include "mongo/bson/bson_comparator_interface_base.h"
 #include "mongo/bson/bsontypes.h"
 #include "mongo/bson/oid.h"
 #include "mongo/bson/timestamp.h"
@@ -77,6 +78,15 @@ int compareElementValues(const BSONElement& l,
 */
 class BSONElement {
 public:
+    // Declared in bsonobj_comparator_interface.h.
+    class ComparatorInterface;
+
+    /**
+     * Operator overloads for relops return a DeferredComparison which can subsequently be evaluated
+     * by a BSONObj::ComparatorInterface.
+     */
+    using DeferredComparison = BSONComparatorInterfaceBase<BSONElement>::DeferredComparison;
+
     /** These functions, which start with a capital letter, throw a MsgAssertionException if the
         element is not of the required type. Example:
 
@@ -473,21 +483,16 @@ public:
         return p + strlen(p) + 1;
     }
 
-    /** like operator== but doesn't check the fieldname,
-        just the value.
-    */
-    bool valuesEqual(const BSONElement& r) const {
-        return woCompare(r, false) == 0;
-    }
-
-    /** Returns true if elements are equal. */
-    bool operator==(const BSONElement& r) const {
-        return woCompare(r, true) == 0;
-    }
-    /** Returns true if elements are unequal. */
-    bool operator!=(const BSONElement& r) const {
-        return !operator==(r);
-    }
+    //
+    // Comparison API.
+    //
+    // BSONElement instances can be compared via a raw bytewise comparison or a logical comparison.
+    //
+    // Logical comparison can be done either using woCompare() or with operator overloads. Most
+    // callers should prefer operator overloads. Note that the operator overloads return a
+    // DeferredComparison, which must subsequently be evaluated by a
+    // BSONElement::ComparatorInterface. See bsonelement_comparator_interface.h for details.
+    //
 
     /**
      * Compares the raw bytes of the two BSONElements, including the field names. This will treat
@@ -513,6 +518,40 @@ public:
                   bool considerFieldName = true,
                   const StringData::ComparatorInterface* comparator = nullptr) const;
 
+    DeferredComparison operator<(const BSONElement& other) const {
+        return DeferredComparison(DeferredComparison::Type::kLT, *this, other);
+    }
+
+    DeferredComparison operator<=(const BSONElement& other) const {
+        return DeferredComparison(DeferredComparison::Type::kLTE, *this, other);
+    }
+
+    DeferredComparison operator>(const BSONElement& other) const {
+        return DeferredComparison(DeferredComparison::Type::kGT, *this, other);
+    }
+
+    DeferredComparison operator>=(const BSONElement& other) const {
+        return DeferredComparison(DeferredComparison::Type::kGTE, *this, other);
+    }
+
+    DeferredComparison operator==(const BSONElement& other) const {
+        return DeferredComparison(DeferredComparison::Type::kEQ, *this, other);
+    }
+
+    DeferredComparison operator!=(const BSONElement& other) const {
+        return DeferredComparison(DeferredComparison::Type::kNE, *this, other);
+    }
+
+    /** like operator== but doesn't check the fieldname,
+        just the value.
+
+        TODO: Delete this method. Callers should use the appropriate
+        BSONElement::ComparatorInterface instead.
+    */
+    bool valuesEqual(const BSONElement& r) const {
+        return woCompare(r, false) == 0;
+    }
+
     /**
      * Functor compatible with std::hash for std::unordered_{map,set}
      * Warning: The hash function is subject to change. Do not use in cases where hashes need
@@ -586,16 +625,6 @@ public:
         return mongo::OID::from(start);
     }
 
-    /** this does not use fieldName in the comparison, just the value */
-    bool operator<(const BSONElement& other) const {
-        int x = (int)canonicalType() - (int)other.canonicalType();
-        if (x < 0)
-            return true;
-        else if (x > 0)
-            return false;
-        return compareElementValues(*this, other) < 0;
-    }
-
     // @param maxLen don't scan more than maxLen bytes
     explicit BSONElement(const char* d, int maxLen) : data(d) {
         if (eoo()) {
diff --git a/src/mongo/bson/bsonelement_comparator.h b/src/mongo/bson/bsonelement_comparator.h
new file mode 100644
index 00000000000..c1e1d9bfd7a
--- /dev/null
+++ b/src/mongo/bson/bsonelement_comparator.h
@@ -0,0 +1,70 @@
+/**
+ *    Copyright (C) 2016 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/base/string_data_comparator_interface.h"
+#include "mongo/bson/bsonelement_comparator_interface.h"
+
+namespace mongo {
+
+/**
+ * A BSONElement comparator that supports:
+ * - Ignoring field names during comparison.
+ * - Passing a custom string comparator.
+ */
+class BSONElementComparator final : public BSONElement::ComparatorInterface {
+public:
+    enum class FieldNamesMode {
+        kConsider,
+        kIgnore,
+    };
+
+    /**
+     * Constructs a BSONElement comparator.
+     *
+     * Will not consider the elements' field names in comparisons if 'fieldNamesMode' is kIgnore.
+     *
+     * If 'stringComparator' is null, uses default binary string comparison. Otherwise,
+     * 'stringComparator' is used for all string comparisons.
+     */
+    BSONElementComparator(FieldNamesMode fieldNamesMode,
+                          const StringData::ComparatorInterface* stringComparator)
+        : _fieldNamesMode(fieldNamesMode), _stringComparator(stringComparator) {}
+
+    int compare(const BSONElement& lhs, const BSONElement& rhs) const final {
+        const bool considerFieldName = (_fieldNamesMode == FieldNamesMode::kConsider);
+        return lhs.woCompare(rhs, considerFieldName, _stringComparator);
+    }
+
+private:
+    FieldNamesMode _fieldNamesMode;
+    const StringData::ComparatorInterface* _stringComparator;
+};
+
+}  // namespace mongo
diff --git a/src/mongo/bson/bsonelement_comparator_interface.h b/src/mongo/bson/bsonelement_comparator_interface.h
new file mode 100644
index 00000000000..c6223a2d352
--- /dev/null
+++ b/src/mongo/bson/bsonelement_comparator_interface.h
@@ -0,0 +1,103 @@
+/**
+ *    Copyright (C) 2016 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/bson/bson_comparator_interface_base.h"
+#include "mongo/bson/bsonelement.h"
+
+namespace mongo {
+
+/**
+ * A BSONElement::ComparatorInterface is an abstract class for comparing BSONElement objects. Usage
+ * for comparing two BSON elements, 'lhs' and 'rhs', where 'comparator' is an instance of a class
+ * implementing this interface, is as shown below:
+ *
+ *  bool lessThan = comparator.evaluate(lhs < rhs);
+ *  bool lessThanOrEqual = comparator.evaluate(lhs <= rhs);
+ *  bool equal = comparator.evaluate(lhs == rhs);
+ *  bool greaterThanOrEqual = comparator.evaluate(lhs >= rhs);
+ *  bool greaterThan = comparator.evaluate(lhs > rhs);
+ *  bool notEqual = comparator.evaluate(lhs != rhs);
+ *
+ * Can also be used to obtain function objects compatible for use with standard library algorithms
+ * such as std::sort, and to construct STL sets and maps which respect this comparator.
+ *
+ * All methods are thread-safe.
+ */
+class BSONElement::ComparatorInterface : public BSONComparatorInterfaceBase<BSONElement> {
+public:
+    /**
+     * Constructs a BSONEltSet whose equivalence classes are given by this comparator. This
+     * comparator must outlive the returned set.
+     */
+    Set makeBSONEltSet(std::initializer_list<BSONElement> init = {}) const {
+        return makeSet(init);
+    }
+
+    /**
+     * Constructs a BSONEltUnorderedSet whose equivalence classes are given by this
+     * comparator. This comparator must outlive the returned set.
+     */
+    UnorderedSet makeBSONEltUnorderedSet(std::initializer_list<BSONElement> init = {}) const {
+        return makeUnorderedSet(init);
+    }
+
+    /**
+     * Constructs an ordered map from BSONElement to type ValueType whose ordering is given by this
+     * comparator. This comparator must outlive the returned map.
+     */
+    template <typename ValueType>
+    Map<ValueType> makeBSONEltIndexedMap(
+        std::initializer_list<std::pair<const BSONElement, ValueType>> init = {}) const {
+        return makeMap(init);
+    }
+
+    /**
+     * Constructs an unordered map from BSONElement to type ValueType whose ordering is given by
+     * this comparator. This comparator must outlive the returned map.
+     */
+    template <typename ValueType>
+    UnorderedMap<ValueType> makeBSONEltIndexedUnorderedMap(
+        std::initializer_list<std::pair<const BSONElement, ValueType>> init = {}) const {
+        return makeUnorderedMap(init);
+    }
+};
+
+using BSONEltSet = BSONComparatorInterfaceBase<BSONElement>::Set;
+
+using BSONEltUnorderedSet = BSONComparatorInterfaceBase<BSONElement>::UnorderedSet;
+
+template <typename ValueType>
+using BSONEltIndexedMap = BSONComparatorInterfaceBase<BSONElement>::Map<ValueType>;
+
+template <typename ValueType>
+using BSONEltIndexedUnorderedMap =
+    BSONComparatorInterfaceBase<BSONElement>::UnorderedMap<ValueType>;
+
+}  // namespace mongo
diff --git a/src/mongo/bson/bsonobj.cpp b/src/mongo/bson/bsonobj.cpp
index ca2e0991403..06d8a28c950 100644
--- a/src/mongo/bson/bsonobj.cpp
+++ b/src/mongo/bson/bsonobj.cpp
@@ -192,14 +192,15 @@ size_t BSONObj::Hasher::operator()(const BSONObj& obj) const {
     return hash;
 }
 
-bool BSONObj::isPrefixOf(const BSONObj& otherObj) const {
+bool BSONObj::isPrefixOf(const BSONObj& otherObj,
+                         const BSONElement::ComparatorInterface& eltCmp) const {
     BSONObjIterator a(*this);
     BSONObjIterator b(otherObj);
 
     while (a.more() && b.more()) {
         BSONElement x = a.next();
         BSONElement y = b.next();
-        if (x != y)
+        if (eltCmp.evaluate(x != y))
             return false;
     }
 
diff --git a/src/mongo/bson/bsonobj.h b/src/mongo/bson/bsonobj.h
index cfd35c2513f..77f13fd533b 100644
--- a/src/mongo/bson/bsonobj.h
+++ b/src/mongo/bson/bsonobj.h
@@ -40,7 +40,9 @@
 #include "mongo/base/disallow_copying.h"
 #include "mongo/base/string_data.h"
 #include "mongo/base/string_data_comparator_interface.h"
+#include "mongo/bson/bson_comparator_interface_base.h"
 #include "mongo/bson/bsonelement.h"
+#include "mongo/bson/bsonelement_comparator_interface.h"
 #include "mongo/bson/bsontypes.h"
 #include "mongo/bson/oid.h"
 #include "mongo/bson/timestamp.h"
@@ -102,23 +104,7 @@ public:
      * Operator overloads for relops return a DeferredComparison which can subsequently be evaluated
      * by a BSONObj::ComparatorInterface.
      */
-    struct DeferredComparison {
-        enum class Type {
-            kLT,
-            kLTE,
-            kEQ,
-            kGT,
-            kGTE,
-            kNE,
-        };
-
-        DeferredComparison(Type type, const BSONObj& lhs, const BSONObj& rhs)
-            : type(type), lhs(lhs), rhs(rhs) {}
-
-        Type type;
-        const BSONObj& lhs;
-        const BSONObj& rhs;
-    };
+    using DeferredComparison = BSONComparatorInterfaceBase<BSONObj>::DeferredComparison;
 
     static const char kMinBSONLength = 5;
 
@@ -484,12 +470,13 @@ public:
     };
 
     /**
-     * @param otherObj
-     * @return true if 'this' is a prefix of otherObj- in other words if
-     * otherObj contains the same field names and field vals in the same
-     * order as 'this', plus optionally some additional elements.
+     * Returns true if 'this' is a prefix of otherObj- in other words if otherObj contains the same
+     * field names and field vals in the same order as 'this', plus optionally some additional
+     * elements.
+     *
+     * All comparisons between elements are made using 'eltCmp'.
      */
-    bool isPrefixOf(const BSONObj& otherObj) const;
+    bool isPrefixOf(const BSONObj& otherObj, const BSONElement::ComparatorInterface& eltCmp) const;
 
     /**
      * @param otherObj
diff --git a/src/mongo/bson/bsonobj_comparator_interface.h b/src/mongo/bson/bsonobj_comparator_interface.h
index a063f638391..4240f19b3f4 100644
--- a/src/mongo/bson/bsonobj_comparator_interface.h
+++ b/src/mongo/bson/bsonobj_comparator_interface.h
@@ -28,15 +28,8 @@
 
 #pragma once
 
-#include <initializer_list>
-#include <map>
-#include <set>
-#include <unordered_map>
-#include <unordered_set>
-
-#include "mongo/base/disallow_copying.h"
+#include "mongo/bson/bson_comparator_interface_base.h"
 #include "mongo/bson/bsonobj.h"
-#include "mongo/util/assert_util.h"
 
 namespace mongo {
 
@@ -57,152 +50,53 @@ namespace mongo {
  *
  * All methods are thread-safe.
  */
-class BSONObj::ComparatorInterface {
-    MONGO_DISALLOW_COPYING(ComparatorInterface);
-
+class BSONObj::ComparatorInterface : public BSONComparatorInterfaceBase<BSONObj> {
 public:
     /**
-     * Functor compatible for use with ordered STL containers.
-     */
-    class LessThan {
-    public:
-        explicit LessThan(const ComparatorInterface* comparator) : _comparator(comparator) {}
-
-        bool operator()(const BSONObj& lhs, const BSONObj& rhs) const {
-            return _comparator->compare(lhs, rhs) < 0;
-        }
-
-    private:
-        const ComparatorInterface* _comparator;
-    };
-
-    /**
-     * Functor compatible for use with unordered STL containers.
-     */
-    class EqualTo {
-    public:
-        explicit EqualTo(const ComparatorInterface* comparator) : _comparator(comparator) {}
-
-        bool operator()(const BSONObj& lhs, const BSONObj& rhs) const {
-            return _comparator->compare(lhs, rhs) == 0;
-        }
-
-    private:
-        const ComparatorInterface* _comparator;
-    };
-
-    using BSONObjSet = std::set<BSONObj, BSONObj::ComparatorInterface::LessThan>;
-
-    // TODO SERVER-23990: Make the BSONObj hash collation-aware.
-    using BSONObjUnorderedSet =
-        std::unordered_set<BSONObj, BSONObj::Hasher, BSONObj::ComparatorInterface::EqualTo>;
-
-    template <typename T>
-    using BSONObjIndexedMap = std::map<BSONObj, T, BSONObj::ComparatorInterface::LessThan>;
-
-    // TODO SERVER-23990: Make the BSONObj hash collation-aware.
-    template <typename T>
-    using BSONObjIndexedUnorderedMap =
-        std::unordered_map<BSONObj, T, BSONObj::Hasher, BSONObj::ComparatorInterface::EqualTo>;
-
-    virtual ~ComparatorInterface() = default;
-
-    /**
-     * Compares two BSONObj objects. Returns <0, 0, >0 if 'lhs' < 'rhs', 'lhs' == 'rhs', or 'lhs' >
-     * 'rhs' respectively.
+     * Constructs a BSONObjSet whose equivalence classes are given by this comparator. This
+     * comparator must outlive the returned set.
      */
-    virtual int compare(const BSONObj& lhs, const BSONObj& rhs) const = 0;
-
-    /**
-     * Evaluates a deferred comparison object generated by invocation of one of the BSONObj operator
-     * overloads for relops.
-     */
-    bool evaluate(BSONObj::DeferredComparison deferredComparison) const {
-        int cmp = compare(deferredComparison.lhs, deferredComparison.rhs);
-        switch (deferredComparison.type) {
-            case BSONObj::DeferredComparison::Type::kLT:
-                return cmp < 0;
-            case BSONObj::DeferredComparison::Type::kLTE:
-                return cmp <= 0;
-            case BSONObj::DeferredComparison::Type::kEQ:
-                return cmp == 0;
-            case BSONObj::DeferredComparison::Type::kGT:
-                return cmp > 0;
-            case BSONObj::DeferredComparison::Type::kGTE:
-                return cmp >= 0;
-            case BSONObj::DeferredComparison::Type::kNE:
-                return cmp != 0;
-        }
-
-        MONGO_UNREACHABLE;
-    }
-
-    /**
-     * Returns a function object which computes whether one BSONObj is less than another under this
-     * comparator. This comparator must outlive the returned function object.
-     */
-    LessThan makeLessThan() const {
-        return LessThan(this);
-    }
-
-    /**
-     * Returns a function object which computes whether one BSONObj is equal to another under this
-     * comparator. This comparator must outlive the returned function object.
-     */
-    EqualTo makeEqualTo() const {
-        return EqualTo(this);
-    }
-
-    /**
-     * Constructs a BSONObjSet whose ordering is given by this comparator. This comparator must
-     * outlive the returned set.
-     */
-    BSONObjSet makeBSONObjSet(std::initializer_list<BSONObj> init = {}) const {
-        return BSONObjSet(init, LessThan(this));
+    Set makeBSONObjSet(std::initializer_list<BSONObj> init = {}) const {
+        return makeSet(init);
     }
 
     /**
      * Constructs a BSONObjUnorderedSet whose equivalence classes are given by this
      * comparator. This comparator must outlive the returned set.
      */
-    BSONObjUnorderedSet makeBSONObjUnorderedSet(std::initializer_list<BSONObj> init = {}) const {
-        // TODO SERVER-23990: Make the BSONObj hash collation-aware.
-        return BSONObjUnorderedSet(init, 0, BSONObj::Hasher(), EqualTo(this));
+    UnorderedSet makeBSONObjUnorderedSet(std::initializer_list<BSONObj> init = {}) const {
+        return makeUnorderedSet(init);
     }
 
     /**
-     * Constructs an ordered map from BSONObj to type T whose ordering is given by this comparator.
-     * This comparator must outlive the returned map.
+     * Constructs an ordered map from BSONObj to type ValueType whose ordering is given by this
+     * comparator.  This comparator must outlive the returned map.
      */
-    template <typename T>
-    BSONObjIndexedMap<T> makeBSONObjIndexedMap(
-        std::initializer_list<std::pair<const BSONObj, T>> init = {}) const {
-        return BSONObjIndexedMap<T>(init, LessThan(this));
+    template <typename ValueType>
+    Map<ValueType> makeBSONObjIndexedMap(
+        std::initializer_list<std::pair<const BSONObj, ValueType>> init = {}) const {
+        return makeMap(init);
     }
 
     /**
-     * Constructs an unordered map from BSONObj to type T whose ordering is given by this
+     * Constructs an unordered map from BSONObj to type ValueType whose ordering is given by this
      * comparator. This comparator must outlive the returned map.
      */
-    template <typename T>
-    BSONObjIndexedUnorderedMap<T> makeBSONObjIndexedUnorderedMap(
-        std::initializer_list<std::pair<const BSONObj, T>> init = {}) const {
-        // TODO SERVER-23990: Make the BSONObj hash collation-aware.
-        return BSONObjIndexedUnorderedMap<T>(init, 0, BSONObj::Hasher(), EqualTo(this));
+    template <typename ValueType>
+    UnorderedMap<ValueType> makeBSONObjIndexedUnorderedMap(
+        std::initializer_list<std::pair<const BSONObj, ValueType>> init = {}) const {
+        return makeUnorderedMap(init);
     }
-
-protected:
-    constexpr ComparatorInterface() = default;
 };
 
-using BSONObjSet = BSONObj::ComparatorInterface::BSONObjSet;
+using BSONObjSet = BSONComparatorInterfaceBase<BSONObj>::Set;
 
-using BSONObjUnorderedSet = BSONObj::ComparatorInterface::BSONObjUnorderedSet;
+using BSONObjUnorderedSet = BSONComparatorInterfaceBase<BSONObj>::UnorderedSet;
 
-template <typename T>
-using BSONObjIndexedMap = BSONObj::ComparatorInterface::BSONObjIndexedMap<T>;
+template <typename ValueType>
+using BSONObjIndexedMap = BSONComparatorInterfaceBase<BSONObj>::Map<ValueType>;
 
-template <typename T>
-using BSONObjIndexedUnorderedMap = BSONObj::ComparatorInterface::BSONObjIndexedUnorderedMap<T>;
+template <typename ValueType>
+using BSONObjIndexedUnorderedMap = BSONComparatorInterfaceBase<BSONObj>::UnorderedMap<ValueType>;
 
 }  // namespace mongo
diff --git a/src/mongo/bson/mutable/mutable_bson_test.cpp b/src/mongo/bson/mutable/mutable_bson_test.cpp
index d1584ff9714..26930dfa2c8 100644
--- a/src/mongo/bson/mutable/mutable_bson_test.cpp
+++ b/src/mongo/bson/mutable/mutable_bson_test.cpp
@@ -1797,7 +1797,7 @@ TEST(Document, ValueOfEphemeralObjectElementIsEmpty) {
     ASSERT_OK(root.pushBack(ephemeralObject));
     ASSERT_FALSE(ephemeralObject.hasValue());
     // NOTE: You really shouldn't rely on this behavior; this test is mostly for coverage.
-    ASSERT_EQUALS(mongo::BSONElement(), ephemeralObject.getValue());
+    ASSERT_BSONELT_EQ(mongo::BSONElement(), ephemeralObject.getValue());
 }
 
 TEST(Element, RemovingRemovedElementFails) {
diff --git a/src/mongo/bson/simple_bsonelement_comparator.cpp b/src/mongo/bson/simple_bsonelement_comparator.cpp
new file mode 100644
index 00000000000..542d5a68f2a
--- /dev/null
+++ b/src/mongo/bson/simple_bsonelement_comparator.cpp
@@ -0,0 +1,37 @@
+/**
+ *    Copyright (C) 2016 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/bson/simple_bsonelement_comparator.h"
+
+namespace mongo {
+
+const SimpleBSONElementComparator SimpleBSONElementComparator::kInstance{};
+
+}  // namespace mongo
diff --git a/src/mongo/bson/simple_bsonelement_comparator.h b/src/mongo/bson/simple_bsonelement_comparator.h
new file mode 100644
index 00000000000..001f70d21fe
--- /dev/null
+++ b/src/mongo/bson/simple_bsonelement_comparator.h
@@ -0,0 +1,50 @@
+/**
+ *    Copyright (C) 2016 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/bson/bsonelement_comparator_interface.h"
+
+namespace mongo {
+
+/**
+ * A BSONElement comparator that has simple binary compare semantics. The comparison considers both
+ * the field name of the element and the element's value.
+ */
+class SimpleBSONElementComparator final : public BSONElement::ComparatorInterface {
+public:
+    // Global simple comparator for stateless BSONObj comparisons. BSONObj comparisons that require
+    // database logic, such as collations, much instantiate their own comparator.
+    static const SimpleBSONElementComparator kInstance;
+
+    int compare(const BSONElement& lhs, const BSONElement& rhs) const final {
+        return lhs.woCompare(rhs, true, nullptr);
+    }
+};
+
+}  // namespace mongo
diff --git a/src/mongo/client/replica_set_monitor.cpp b/src/mongo/client/replica_set_monitor.cpp
index 02fc1ba5a08..d23ad5f48fa 100644
--- a/src/mongo/client/replica_set_monitor.cpp
+++ b/src/mongo/client/replica_set_monitor.cpp
@@ -34,6 +34,7 @@
 #include <algorithm>
 #include <limits>
 
+#include "mongo/bson/simple_bsonelement_comparator.h"
 #include "mongo/client/connpool.h"
 #include "mongo/client/global_conn_pool.h"
 #include "mongo/client/read_preference.h"
@@ -892,8 +893,10 @@ bool Node::matches(const ReadPreference pref) const {
 
 bool Node::matches(const BSONObj& tag) const {
     BSONForEach(tagCriteria, tag) {
-        if (this->tags[tagCriteria.fieldNameStringData()] != tagCriteria)
+        if (SimpleBSONElementComparator::kInstance.evaluate(
+                this->tags[tagCriteria.fieldNameStringData()] != tagCriteria)) {
             return false;
+        }
     }
 
     return true;
diff --git a/src/mongo/db/catalog/coll_mod.cpp b/src/mongo/db/catalog/coll_mod.cpp
index 7421d632981..ef04c2bc877 100644
--- a/src/mongo/db/catalog/coll_mod.cpp
+++ b/src/mongo/db/catalog/coll_mod.cpp
@@ -32,6 +32,7 @@
 
 #include <boost/optional.hpp>
 
+#include "mongo/bson/simple_bsonelement_comparator.h"
 #include "mongo/db/background.h"
 #include "mongo/db/catalog/collection.h"
 #include "mongo/db/catalog/collection_catalog_entry.h"
@@ -198,7 +199,7 @@ Status collMod(OperationContext* txn,
                 continue;
             }
 
-            if (oldExpireSecs != newExpireSecs) {
+            if (SimpleBSONElementComparator::kInstance.evaluate(oldExpireSecs != newExpireSecs)) {
                 result->appendAs(oldExpireSecs, "expireAfterSeconds_old");
                 // Change the value of "expireAfterSeconds" on disk.
                 coll->getCatalogEntry()->updateTTLSetting(
diff --git a/src/mongo/db/catalog/collection.cpp b/src/mongo/db/catalog/collection.cpp
index de28926819a..cfd67e79ede 100644
--- a/src/mongo/db/catalog/collection.cpp
+++ b/src/mongo/db/catalog/collection.cpp
@@ -39,6 +39,7 @@
 #include "mongo/base/counter.h"
 #include "mongo/base/owned_pointer_map.h"
 #include "mongo/bson/ordering.h"
+#include "mongo/bson/simple_bsonelement_comparator.h"
 #include "mongo/bson/simple_bsonobj_comparator.h"
 #include "mongo/db/background.h"
 #include "mongo/db/catalog/collection_catalog_entry.h"
@@ -606,7 +607,7 @@ StatusWith<RecordId> Collection::updateDocument(OperationContext* txn,
     SnapshotId sid = txn->recoveryUnit()->getSnapshotId();
 
     BSONElement oldId = oldDoc.value()["_id"];
-    if (!oldId.eoo() && (oldId != newDoc["_id"]))
+    if (!oldId.eoo() && SimpleBSONElementComparator::kInstance.evaluate(oldId != newDoc["_id"]))
         return StatusWith<RecordId>(
             ErrorCodes::InternalError, "in Collection::updateDocument _id mismatch", 13596);
 
diff --git a/src/mongo/db/catalog/index_catalog.cpp b/src/mongo/db/catalog/index_catalog.cpp
index cfffe585778..702bc51ec73 100644
--- a/src/mongo/db/catalog/index_catalog.cpp
+++ b/src/mongo/db/catalog/index_catalog.cpp
@@ -36,6 +36,7 @@
 
 #include <vector>
 
+#include "mongo/bson/simple_bsonelement_comparator.h"
 #include "mongo/bson/simple_bsonobj_comparator.h"
 #include "mongo/db/audit.h"
 #include "mongo/db/background.h"
@@ -1117,7 +1118,7 @@ IndexDescriptor* IndexCatalog::findShardKeyPrefixedIndex(OperationContext* txn,
         if (desc->isPartial())
             continue;
 
-        if (!shardKey.isPrefixOf(desc->keyPattern()))
+        if (!shardKey.isPrefixOf(desc->keyPattern(), SimpleBSONElementComparator::kInstance))
             continue;
 
         if (!desc->isMultikey(txn) && hasSimpleCollation)
diff --git a/src/mongo/db/index/index_descriptor.cpp b/src/mongo/db/index/index_descriptor.cpp
index 9d0de13b4d1..3e27759a3a9 100644
--- a/src/mongo/db/index/index_descriptor.cpp
+++ b/src/mongo/db/index/index_descriptor.cpp
@@ -30,7 +30,13 @@
 
 #define MONGO_LOG_DEFAULT_COMPONENT ::mongo::logger::LogComponent::kIndex
 
+#include "mongo/platform/basic.h"
+
 #include "mongo/db/index/index_descriptor.h"
+
+#include <algorithm>
+
+#include "mongo/bson/simple_bsonelement_comparator.h"
 #include "mongo/util/log.h"
 
 namespace mongo {
@@ -76,7 +82,16 @@ bool IndexDescriptor::areIndexOptionsEquivalent(const IndexDescriptor* other) co
     std::map<StringData, BSONElement> newOptionsMap;
     populateOptionsMap(newOptionsMap, other->infoObj());
 
-    return existingOptionsMap == newOptionsMap;
+    return existingOptionsMap.size() == newOptionsMap.size() &&
+        std::equal(existingOptionsMap.begin(),
+                   existingOptionsMap.end(),
+                   newOptionsMap.begin(),
+                   [](const std::pair<StringData, BSONElement>& lhs,
+                      const std::pair<StringData, BSONElement>& rhs) {
+                       return lhs.first == rhs.first &&
+                           SimpleBSONElementComparator::kInstance.evaluate(lhs.second ==
+                                                                           rhs.second);
+                   });
 }
 
 void IndexDescriptor::_checkOk() const {
diff --git a/src/mongo/db/matcher/expression_leaf_test.cpp b/src/mongo/db/matcher/expression_leaf_test.cpp
index 40f50115c84..293ed59c85c 100644
--- a/src/mongo/db/matcher/expression_leaf_test.cpp
+++ b/src/mongo/db/matcher/expression_leaf_test.cpp
@@ -1731,7 +1731,8 @@ TEST(InMatchExpression, ChangingCollationAfterAddingEqualitiesPreservesEqualitie
     ASSERT(in.getEqualities().size() == 1);
     in.setCollator(&collatorReverseString);
     ASSERT(in.getEqualities().size() == 2);
-    ASSERT(in.getEqualities() == BSONElementSet({obj1.firstElement(), obj2.firstElement()}));
+    ASSERT(in.getEqualities().count(obj1.firstElement()));
+    ASSERT(in.getEqualities().count(obj2.firstElement()));
 }
 
 std::vector<uint32_t> bsonArrayToBitPositions(const BSONArray& ba) {
diff --git a/src/mongo/db/query/planner_analysis.cpp b/src/mongo/db/query/planner_analysis.cpp
index 7298959764f..47345801b95 100644
--- a/src/mongo/db/query/planner_analysis.cpp
+++ b/src/mongo/db/query/planner_analysis.cpp
@@ -33,6 +33,7 @@
 #include <set>
 #include <vector>
 
+#include "mongo/bson/simple_bsonelement_comparator.h"
 #include "mongo/db/bson/dotted_path_support.h"
 #include "mongo/db/index/expression_params.h"
 #include "mongo/db/index/s2_common.h"
@@ -409,11 +410,12 @@ bool QueryPlannerAnalysis::explodeForSort(const CanonicalQuery& query,
 
         // See if it's the order we're looking for.
         BSONObj possibleSort = resultingSortBob.obj();
-        if (!desiredSort.isPrefixOf(possibleSort)) {
+        if (!desiredSort.isPrefixOf(possibleSort, SimpleBSONElementComparator::kInstance)) {
             // We can't get the sort order from the index scan. See if we can
             // get the sort by reversing the scan.
             BSONObj reversePossibleSort = QueryPlannerCommon::reverseSortObj(possibleSort);
-            if (!desiredSort.isPrefixOf(reversePossibleSort)) {
+            if (!desiredSort.isPrefixOf(reversePossibleSort,
+                                        SimpleBSONElementComparator::kInstance)) {
                 // Can't get the sort order from the reversed index scan either. Give up.
                 return false;
             } else {
diff --git a/src/mongo/db/query/query_planner.cpp b/src/mongo/db/query/query_planner.cpp
index 91df25ff3fc..0dc90505fb3 100644
--- a/src/mongo/db/query/query_planner.cpp
+++ b/src/mongo/db/query/query_planner.cpp
@@ -36,6 +36,7 @@
 #include <vector>
 
 #include "mongo/base/string_data.h"
+#include "mongo/bson/simple_bsonelement_comparator.h"
 #include "mongo/client/dbclientinterface.h"  // For QueryOption_foobar
 #include "mongo/db/bson/dotted_path_support.h"
 #include "mongo/db/matcher/expression_algo.h"
@@ -253,7 +254,7 @@ QuerySolution* buildWholeIXSoln(const IndexEntry& index,
 }
 
 bool providesSort(const CanonicalQuery& query, const BSONObj& kp) {
-    return query.getQueryRequest().getSort().isPrefixOf(kp);
+    return query.getQueryRequest().getSort().isPrefixOf(kp, SimpleBSONElementComparator::kInstance);
 }
 
 // static
diff --git a/src/mongo/db/query/query_solution.cpp b/src/mongo/db/query/query_solution.cpp
index ade1cf451b1..ed9ab70b4cc 100644
--- a/src/mongo/db/query/query_solution.cpp
+++ b/src/mongo/db/query/query_solution.cpp
@@ -31,6 +31,7 @@
 #include "mongo/db/query/query_solution.h"
 
 #include "mongo/bson/bsontypes.h"
+#include "mongo/bson/simple_bsonelement_comparator.h"
 #include "mongo/db/index_names.h"
 #include "mongo/db/matcher/expression_geo.h"
 #include "mongo/db/query/collation/collation_index_key.h"
@@ -603,7 +604,8 @@ std::set<StringData> IndexScanNode::getFieldsWithStringBounds(const IndexBounds&
         while (keyPatternIterator.more() && startKeyIterator.more() && endKeyIterator.more()) {
             BSONElement startKey = startKeyIterator.next();
             BSONElement endKey = endKeyIterator.next();
-            if (startKey != endKey || CollationIndexKey::isCollatableType(startKey.type())) {
+            if (SimpleBSONElementComparator::kInstance.evaluate(startKey != endKey) ||
+                CollationIndexKey::isCollatableType(startKey.type())) {
                 if (!rangeCanContainString(
                         startKey, endKey, (startKeyIterator.more() || bounds.endKeyInclusive))) {
                     // If the first non-point range cannot contain strings, we don't need to
@@ -689,7 +691,8 @@ void IndexScanNode::computeProperties() {
         BSONObjIterator endIter(bounds.endKey);
         while (keyIter.more() && startIter.more() && endIter.more()) {
             BSONElement key = keyIter.next();
-            if (startIter.next() == endIter.next()) {
+            if (SimpleBSONElementComparator::kInstance.evaluate(startIter.next() ==
+                                                                endIter.next())) {
                 equalityFields.insert(key.fieldName());
             }
         }
diff --git a/src/mongo/db/repl/rs_rollback.cpp b/src/mongo/db/repl/rs_rollback.cpp
index fa69436ba33..b1fd726d062 100644
--- a/src/mongo/db/repl/rs_rollback.cpp
+++ b/src/mongo/db/repl/rs_rollback.cpp
@@ -36,6 +36,7 @@
 #include <algorithm>
 #include <memory>
 
+#include "mongo/bson/bsonelement_comparator.h"
 #include "mongo/bson/util/bson_extract.h"
 #include "mongo/db/auth/authorization_manager.h"
 #include "mongo/db/auth/authorization_manager_global.h"
@@ -140,7 +141,11 @@ struct DocID {
             return true;
         if (comp > 0)
             return false;
-        return _id < other._id;
+
+        const StringData::ComparatorInterface* stringComparator = nullptr;
+        BSONElementComparator eltCmp(BSONElementComparator::FieldNamesMode::kIgnore,
+                                     stringComparator);
+        return eltCmp.evaluate(_id < other._id);
     }
 };
 
diff --git a/src/mongo/dbtests/jsobjtests.cpp b/src/mongo/dbtests/jsobjtests.cpp
index 72d18905a5f..a6b3fea9547 100644
--- a/src/mongo/dbtests/jsobjtests.cpp
+++ b/src/mongo/dbtests/jsobjtests.cpp
@@ -37,6 +37,7 @@
 #include <iostream>
 
 #include "mongo/bson/bsonobj_comparator.h"
+#include "mongo/bson/simple_bsonelement_comparator.h"
 #include "mongo/bson/util/builder.h"
 #include "mongo/db/bson/dotted_path_support.h"
 #include "mongo/db/jsobj.h"
@@ -309,26 +310,29 @@ public:
 class IsPrefixOf : public Base {
 public:
     void run() {
+        SimpleBSONElementComparator eltCmp;
         {
             BSONObj k = BSON("x" << 1);
-            verify(!k.isPrefixOf(BSON("a" << 1)));
-            verify(k.isPrefixOf(BSON("x" << 1)));
-            verify(k.isPrefixOf(BSON("x" << 1 << "a" << 1)));
-            verify(!k.isPrefixOf(BSON("a" << 1 << "x" << 1)));
+            ASSERT(!k.isPrefixOf(BSON("a" << 1), eltCmp));
+            ASSERT(k.isPrefixOf(BSON("x" << 1), eltCmp));
+            ASSERT(k.isPrefixOf(BSON("x" << 1 << "a" << 1), eltCmp));
+            ASSERT(!k.isPrefixOf(BSON("a" << 1 << "x" << 1), eltCmp));
         }
         {
             BSONObj k = BSON("x" << 1 << "y" << 1);
-            verify(!k.isPrefixOf(BSON("x" << 1)));
-            verify(!k.isPrefixOf(BSON("x" << 1 << "z" << 1)));
-            verify(k.isPrefixOf(BSON("x" << 1 << "y" << 1)));
-            verify(k.isPrefixOf(BSON("x" << 1 << "y" << 1 << "z" << 1)));
+            ASSERT(!k.isPrefixOf(BSON("x" << 1), eltCmp));
+            ASSERT(!k.isPrefixOf(BSON("x" << 1 << "z" << 1), eltCmp));
+            ASSERT(k.isPrefixOf(BSON("x" << 1 << "y" << 1), eltCmp));
+            ASSERT(k.isPrefixOf(BSON("x" << 1 << "y" << 1 << "z" << 1), eltCmp));
         }
         {
             BSONObj k = BSON("x" << 1);
-            verify(!k.isPrefixOf(BSON("x"
-                                      << "hi")));
-            verify(k.isPrefixOf(BSON("x" << 1 << "a"
-                                         << "hi")));
+            ASSERT(!k.isPrefixOf(BSON("x"
+                                      << "hi"),
+                                 eltCmp));
+            ASSERT(k.isPrefixOf(BSON("x" << 1 << "a"
+                                         << "hi"),
+                                eltCmp));
         }
         {
             BSONObj k = BSON("x" << 1);
diff --git a/src/mongo/dbtests/namespacetests.cpp b/src/mongo/dbtests/namespacetests.cpp
index 7be6bdd1b24..021d5b59293 100644
--- a/src/mongo/dbtests/namespacetests.cpp
+++ b/src/mongo/dbtests/namespacetests.cpp
@@ -111,7 +111,7 @@ public:
 
         BSONObj missingField = IndexLegacy::getMissingField(&txn, NULL, spec);
         ASSERT_EQUALS(NumberLong, missingField.firstElement().type());
-        ASSERT_EQUALS(nullFieldFromKey, missingField.firstElement());
+        ASSERT_BSONELT_EQ(nullFieldFromKey, missingField.firstElement());
     }
 };
 
@@ -143,7 +143,7 @@ public:
         // the right key).
         BSONObj missingField = IndexLegacy::getMissingField(&txn, NULL, spec);
         ASSERT_EQUALS(NumberLong, missingField.firstElement().type());
-        ASSERT_EQUALS(nullFieldFromKey, missingField.firstElement());
+        ASSERT_BSONELT_EQ(nullFieldFromKey, missingField.firstElement());
     }
 };
 
diff --git a/src/mongo/s/commands/cluster_shard_collection_cmd.cpp b/src/mongo/s/commands/cluster_shard_collection_cmd.cpp
index 1f580f97493..9c9df5eead2 100644
--- a/src/mongo/s/commands/cluster_shard_collection_cmd.cpp
+++ b/src/mongo/s/commands/cluster_shard_collection_cmd.cpp
@@ -34,6 +34,7 @@
 #include <set>
 #include <vector>
 
+#include "mongo/bson/simple_bsonelement_comparator.h"
 #include "mongo/bson/simple_bsonobj_comparator.h"
 #include "mongo/bson/util/bson_extract.h"
 #include "mongo/client/connpool.h"
@@ -349,7 +350,7 @@ public:
             BSONObj currentKey = idx["key"].embeddedObject();
             // Check 2.i. and 2.ii.
             if (!idx["sparse"].trueValue() && idx["filter"].eoo() && idx["collation"].eoo() &&
-                proposedKey.isPrefixOf(currentKey)) {
+                proposedKey.isPrefixOf(currentKey, SimpleBSONElementComparator::kInstance)) {
                 // We can't currently use hashed indexes with a non-default hash seed
                 // Check v.
                 // Note that this means that, for sharding, we only support one hashed index
diff --git a/src/mongo/unittest/bson_test_util.cpp b/src/mongo/unittest/bson_test_util.cpp
index 57d93d36026..1f4e52d19ff 100644
--- a/src/mongo/unittest/bson_test_util.cpp
+++ b/src/mongo/unittest/bson_test_util.cpp
@@ -55,5 +55,12 @@ GENERATE_BSON_CMP_FUNC(BSONObj, GT, SimpleBSONObjComparator::kInstance, >);
 GENERATE_BSON_CMP_FUNC(BSONObj, GTE, SimpleBSONObjComparator::kInstance, >=);
 GENERATE_BSON_CMP_FUNC(BSONObj, NE, SimpleBSONObjComparator::kInstance, !=);
 
+GENERATE_BSON_CMP_FUNC(BSONElement, EQ, SimpleBSONElementComparator::kInstance, ==);
+GENERATE_BSON_CMP_FUNC(BSONElement, LT, SimpleBSONElementComparator::kInstance, <);
+GENERATE_BSON_CMP_FUNC(BSONElement, LTE, SimpleBSONElementComparator::kInstance, <=);
+GENERATE_BSON_CMP_FUNC(BSONElement, GT, SimpleBSONElementComparator::kInstance, >);
+GENERATE_BSON_CMP_FUNC(BSONElement, GTE, SimpleBSONElementComparator::kInstance, >=);
+GENERATE_BSON_CMP_FUNC(BSONElement, NE, SimpleBSONElementComparator::kInstance, !=);
+
 }  // namespace unittest
 }  // namespace mongo
diff --git a/src/mongo/unittest/bson_test_util.h b/src/mongo/unittest/bson_test_util.h
index 9a83a3fd482..a70af117f35 100644
--- a/src/mongo/unittest/bson_test_util.h
+++ b/src/mongo/unittest/bson_test_util.h
@@ -28,6 +28,7 @@
 
 #pragma once
 
+#include "mongo/bson/simple_bsonelement_comparator.h"
 #include "mongo/bson/simple_bsonobj_comparator.h"
 #include "mongo/unittest/unittest.h"
 
@@ -47,6 +48,16 @@
 #define ASSERT_BSONOBJ_GTE(a, b) ASSERT_BSON_COMPARISON(BSONObjGTE, a, b)
 #define ASSERT_BSONOBJ_NE(a, b) ASSERT_BSON_COMPARISON(BSONObjNE, a, b)
 
+/**
+ * Use to compare two instances of type BSONElement under the default comparator in unit tests.
+ */
+#define ASSERT_BSONELT_EQ(a, b) ASSERT_BSON_COMPARISON(BSONElementEQ, a, b)
+#define ASSERT_BSONELT_LT(a, b) ASSERT_BSON_COMPARISON(BSONElementLT, a, b)
+#define ASSERT_BSONELT_LTE(a, b) ASSERT_BSON_COMPARISON(BSONElementLTE, a, b)
+#define ASSERT_BSONELT_GT(a, b) ASSERT_BSON_COMPARISON(BSONElementGT, a, b)
+#define ASSERT_BSONELT_GTE(a, b) ASSERT_BSON_COMPARISON(BSONElementGTE, a, b)
+#define ASSERT_BSONELT_NE(a, b) ASSERT_BSON_COMPARISON(BSONElementNE, a, b)
+
 namespace mongo {
 namespace unittest {
 
@@ -64,6 +75,13 @@ DECLARE_BSON_CMP_FUNC(BSONObj, LTE);
 DECLARE_BSON_CMP_FUNC(BSONObj, GT);
 DECLARE_BSON_CMP_FUNC(BSONObj, GTE);
 DECLARE_BSON_CMP_FUNC(BSONObj, NE);
+
+DECLARE_BSON_CMP_FUNC(BSONElement, EQ);
+DECLARE_BSON_CMP_FUNC(BSONElement, LT);
+DECLARE_BSON_CMP_FUNC(BSONElement, LTE);
+DECLARE_BSON_CMP_FUNC(BSONElement, GT);
+DECLARE_BSON_CMP_FUNC(BSONElement, GTE);
+DECLARE_BSON_CMP_FUNC(BSONElement, NE);
 #undef DECLARE_BSON_CMP_FUNC
 
 }  // namespace unittest
diff --git a/src/mongo/unittest/unittest_test.cpp b/src/mongo/unittest/unittest_test.cpp
index c9d8fa7a9a8..03c00a34712 100644
--- a/src/mongo/unittest/unittest_test.cpp
+++ b/src/mongo/unittest/unittest_test.cpp
@@ -189,6 +189,60 @@ TEST(UnitTestSelfTest, BSONObjGTE) {
                             << "bar"));
 }
 
+TEST(UnitTestSelfTest, BSONElementEQ) {
+    mongo::BSONObj obj1 = BSON("foo"
+                               << "bar");
+    mongo::BSONObj obj2 = BSON("foo"
+                               << "bar");
+    ASSERT_BSONELT_EQ(obj1.firstElement(), obj2.firstElement());
+}
+
+TEST(UnitTestSelfTest, BSONElementNE) {
+    mongo::BSONObj obj1 = BSON("foo"
+                               << "bar");
+    mongo::BSONObj obj2 = BSON("foo"
+                               << "baz");
+    ASSERT_BSONELT_NE(obj1.firstElement(), obj2.firstElement());
+}
+
+TEST(UnitTestSelfTest, BSONElementLT) {
+    mongo::BSONObj obj1 = BSON("foo"
+                               << "bar");
+    mongo::BSONObj obj2 = BSON("foo"
+                               << "baz");
+    ASSERT_BSONELT_LT(obj1.firstElement(), obj2.firstElement());
+}
+
+TEST(UnitTestSelfTest, BSONElementLTE) {
+    mongo::BSONObj obj1 = BSON("foo"
+                               << "bar");
+    mongo::BSONObj obj2 = BSON("foo"
+                               << "bar");
+    mongo::BSONObj obj3 = BSON("foo"
+                               << "baz");
+    ASSERT_BSONELT_LTE(obj1.firstElement(), obj2.firstElement());
+    ASSERT_BSONELT_LTE(obj1.firstElement(), obj3.firstElement());
+}
+
+TEST(UnitTestSelfTest, BSONElementGT) {
+    mongo::BSONObj obj1 = BSON("foo"
+                               << "bar");
+    mongo::BSONObj obj2 = BSON("foo"
+                               << "baz");
+    ASSERT_BSONELT_GT(obj2.firstElement(), obj1.firstElement());
+}
+
+TEST(UnitTestSelfTest, BSONElementGTE) {
+    mongo::BSONObj obj1 = BSON("foo"
+                               << "bar");
+    mongo::BSONObj obj2 = BSON("foo"
+                               << "bar");
+    mongo::BSONObj obj3 = BSON("foo"
+                               << "baz");
+    ASSERT_BSONELT_GTE(obj3.firstElement(), obj2.firstElement());
+    ASSERT_BSONELT_GTE(obj2.firstElement(), obj1.firstElement());
+}
+
 DEATH_TEST(DeathTestSelfTest, TestDeath, "Invariant failure false") {
     invariant(false);
 }