SERVER-36889 split IndexAccessMethod into interface and abstract implementation

17 files changed, 303 insertions, 198 deletions

diff --git a/src/mongo/db/index/2d_access_method.cpp b/src/mongo/db/index/2d_access_method.cpp
index f1db4b83969..7e515c6f984 100644
--- a/src/mongo/db/index/2d_access_method.cpp
+++ b/src/mongo/db/index/2d_access_method.cpp
@@ -41,7 +41,7 @@
 namespace mongo {
 
 TwoDAccessMethod::TwoDAccessMethod(IndexCatalogEntry* btreeState, SortedDataInterface* btree)
-    : IndexAccessMethod(btreeState, btree) {
+    : AbstractIndexAccessMethod(btreeState, btree) {
     const IndexDescriptor* descriptor = btreeState->descriptor();
 
     ExpressionParams::parseTwoDParams(descriptor->infoObj(), &_params);
diff --git a/src/mongo/db/index/2d_access_method.h b/src/mongo/db/index/2d_access_method.h
index 1a5451266b1..96c3afa50ad 100644
--- a/src/mongo/db/index/2d_access_method.h
+++ b/src/mongo/db/index/2d_access_method.h
@@ -39,7 +39,7 @@ class IndexCatalogEntry;
 class IndexDescriptor;
 struct TwoDIndexingParams;
 
-class TwoDAccessMethod : public IndexAccessMethod {
+class TwoDAccessMethod : public AbstractIndexAccessMethod {
 public:
     TwoDAccessMethod(IndexCatalogEntry* btreeState, SortedDataInterface* btree);
 
diff --git a/src/mongo/db/index/btree_access_method.cpp b/src/mongo/db/index/btree_access_method.cpp
index b18a86598be..c58c9499008 100644
--- a/src/mongo/db/index/btree_access_method.cpp
+++ b/src/mongo/db/index/btree_access_method.cpp
@@ -42,7 +42,7 @@ using std::vector;
 
 // Standard Btree implementation below.
 BtreeAccessMethod::BtreeAccessMethod(IndexCatalogEntry* btreeState, SortedDataInterface* btree)
-    : IndexAccessMethod(btreeState, btree) {
+    : AbstractIndexAccessMethod(btreeState, btree) {
     // The key generation wants these values.
     vector<const char*> fieldNames;
     vector<BSONElement> fixed;
diff --git a/src/mongo/db/index/btree_access_method.h b/src/mongo/db/index/btree_access_method.h
index 11b811806a3..e93eddf7b31 100644
--- a/src/mongo/db/index/btree_access_method.h
+++ b/src/mongo/db/index/btree_access_method.h
@@ -42,7 +42,7 @@ class IndexDescriptor;
  * The IndexAccessMethod for a Btree index.
  * Any index created with {field: 1} or {field: -1} uses this.
  */
-class BtreeAccessMethod : public IndexAccessMethod {
+class BtreeAccessMethod : public AbstractIndexAccessMethod {
 public:
     BtreeAccessMethod(IndexCatalogEntry* btreeState, SortedDataInterface* btree);
 
diff --git a/src/mongo/db/index/fts_access_method.cpp b/src/mongo/db/index/fts_access_method.cpp
index 203e555d52e..f6419a573c5 100644
--- a/src/mongo/db/index/fts_access_method.cpp
+++ b/src/mongo/db/index/fts_access_method.cpp
@@ -34,7 +34,7 @@
 namespace mongo {
 
 FTSAccessMethod::FTSAccessMethod(IndexCatalogEntry* btreeState, SortedDataInterface* btree)
-    : IndexAccessMethod(btreeState, btree), _ftsSpec(btreeState->descriptor()->infoObj()) {}
+    : AbstractIndexAccessMethod(btreeState, btree), _ftsSpec(btreeState->descriptor()->infoObj()) {}
 
 void FTSAccessMethod::doGetKeys(const BSONObj& obj,
                                 BSONObjSet* keys,
diff --git a/src/mongo/db/index/fts_access_method.h b/src/mongo/db/index/fts_access_method.h
index d3148ae3d96..0a32e9acfc7 100644
--- a/src/mongo/db/index/fts_access_method.h
+++ b/src/mongo/db/index/fts_access_method.h
@@ -36,7 +36,7 @@
 
 namespace mongo {
 
-class FTSAccessMethod : public IndexAccessMethod {
+class FTSAccessMethod : public AbstractIndexAccessMethod {
 public:
     FTSAccessMethod(IndexCatalogEntry* btreeState, SortedDataInterface* btree);
 
diff --git a/src/mongo/db/index/hash_access_method.cpp b/src/mongo/db/index/hash_access_method.cpp
index a2e25d71e7d..9b6d1b9b5fb 100644
--- a/src/mongo/db/index/hash_access_method.cpp
+++ b/src/mongo/db/index/hash_access_method.cpp
@@ -36,7 +36,7 @@
 namespace mongo {
 
 HashAccessMethod::HashAccessMethod(IndexCatalogEntry* btreeState, SortedDataInterface* btree)
-    : IndexAccessMethod(btreeState, btree) {
+    : AbstractIndexAccessMethod(btreeState, btree) {
     const IndexDescriptor* descriptor = btreeState->descriptor();
 
     // We can change these if the single-field limitation is lifted later.
diff --git a/src/mongo/db/index/hash_access_method.h b/src/mongo/db/index/hash_access_method.h
index 99a82454a82..b205531fee0 100644
--- a/src/mongo/db/index/hash_access_method.h
+++ b/src/mongo/db/index/hash_access_method.h
@@ -43,7 +43,7 @@ class CollatorInterface;
 /**
  * This is the access method for "hashed" indices.
  */
-class HashAccessMethod : public IndexAccessMethod {
+class HashAccessMethod : public AbstractIndexAccessMethod {
 public:
     HashAccessMethod(IndexCatalogEntry* btreeState, SortedDataInterface* btree);
 
diff --git a/src/mongo/db/index/haystack_access_method.cpp b/src/mongo/db/index/haystack_access_method.cpp
index 28b7728c1c2..eecaf057f6b 100644
--- a/src/mongo/db/index/haystack_access_method.cpp
+++ b/src/mongo/db/index/haystack_access_method.cpp
@@ -53,7 +53,7 @@ namespace dps = ::mongo::dotted_path_support;
 
 HaystackAccessMethod::HaystackAccessMethod(IndexCatalogEntry* btreeState,
                                            SortedDataInterface* btree)
-    : IndexAccessMethod(btreeState, btree) {
+    : AbstractIndexAccessMethod(btreeState, btree) {
     const IndexDescriptor* descriptor = btreeState->descriptor();
 
     ExpressionParams::parseHaystackParams(
diff --git a/src/mongo/db/index/haystack_access_method.h b/src/mongo/db/index/haystack_access_method.h
index a6aef7a2df4..8d46ff2c6f5 100644
--- a/src/mongo/db/index/haystack_access_method.h
+++ b/src/mongo/db/index/haystack_access_method.h
@@ -54,7 +54,7 @@ class OperationContext;
  *   bucketSize specifies the dimension of the square bucket for the data in pos.
  * ALL fields are mandatory.
  */
-class HaystackAccessMethod : public IndexAccessMethod {
+class HaystackAccessMethod : public AbstractIndexAccessMethod {
 public:
     HaystackAccessMethod(IndexCatalogEntry* btreeState, SortedDataInterface* btree);
 
diff --git a/src/mongo/db/index/index_access_method.cpp b/src/mongo/db/index/index_access_method.cpp
index d2f12401f4a..c5b1dafabe5 100644
--- a/src/mongo/db/index/index_access_method.cpp
+++ b/src/mongo/db/index/index_access_method.cpp
@@ -133,18 +133,19 @@ private:
     const IndexVersion _version;
 };
 
-IndexAccessMethod::IndexAccessMethod(IndexCatalogEntry* btreeState, SortedDataInterface* btree)
+AbstractIndexAccessMethod::AbstractIndexAccessMethod(IndexCatalogEntry* btreeState,
+                                                     SortedDataInterface* btree)
     : _btreeState(btreeState), _descriptor(btreeState->descriptor()), _newInterface(btree) {
     verify(IndexDescriptor::isIndexVersionSupported(_descriptor->version()));
 }
 
 // TODO SERVER-36385: Remove this when there is no KeyTooLong error.
-bool IndexAccessMethod::ignoreKeyTooLong() {
+bool AbstractIndexAccessMethod::ignoreKeyTooLong() {
     return !failIndexKeyTooLongParam();
 }
 
 // TODO SERVER-36385: Remove this when there is no KeyTooLong error.
-bool IndexAccessMethod::shouldCheckIndexKeySize(OperationContext* opCtx) {
+bool AbstractIndexAccessMethod::shouldCheckIndexKeySize(OperationContext* opCtx) {
     // Don't check index key size if we cannot write to the collection. That indicates we are a
     // secondary node and we should accept any index key.
     const NamespaceString collName(_btreeState->ns());
@@ -158,7 +159,7 @@ bool IndexAccessMethod::shouldCheckIndexKeySize(OperationContext* opCtx) {
         ServerGlobalParams::FeatureCompatibility::Version::kFullyDowngradedTo40;
 }
 
-bool IndexAccessMethod::isFatalError(OperationContext* opCtx, Status status, BSONObj key) {
+bool AbstractIndexAccessMethod::isFatalError(OperationContext* opCtx, Status status, BSONObj key) {
     // If the status is Status::OK(), or if it is ErrorCodes::KeyTooLong and the user has chosen to
     // ignore this error, return false immediately.
     // TODO SERVER-36385: Remove this when there is no KeyTooLong error.
@@ -176,11 +177,11 @@ bool IndexAccessMethod::isFatalError(OperationContext* opCtx, Status status, BSO
 }
 
 // Find the keys for obj, put them in the tree pointing to loc.
-Status IndexAccessMethod::insert(OperationContext* opCtx,
-                                 const BSONObj& obj,
-                                 const RecordId& loc,
-                                 const InsertDeleteOptions& options,
-                                 int64_t* numInserted) {
+Status AbstractIndexAccessMethod::insert(OperationContext* opCtx,
+                                         const BSONObj& obj,
+                                         const RecordId& loc,
+                                         const InsertDeleteOptions& options,
+                                         int64_t* numInserted) {
     invariant(numInserted);
     *numInserted = 0;
     bool checkIndexKeySize = shouldCheckIndexKeySize(opCtx);
@@ -219,10 +220,10 @@ Status IndexAccessMethod::insert(OperationContext* opCtx,
     return Status::OK();
 }
 
-void IndexAccessMethod::removeOneKey(OperationContext* opCtx,
-                                     const BSONObj& key,
-                                     const RecordId& loc,
-                                     bool dupsAllowed) {
+void AbstractIndexAccessMethod::removeOneKey(OperationContext* opCtx,
+                                             const BSONObj& key,
+                                             const RecordId& loc,
+                                             bool dupsAllowed) {
 
     try {
         _newInterface->unindex(opCtx, key, loc, dupsAllowed);
@@ -234,17 +235,22 @@ void IndexAccessMethod::removeOneKey(OperationContext* opCtx,
     }
 }
 
-std::unique_ptr<SortedDataInterface::Cursor> IndexAccessMethod::newCursor(OperationContext* opCtx,
-                                                                          bool isForward) const {
+std::unique_ptr<SortedDataInterface::Cursor> AbstractIndexAccessMethod::newCursor(
+    OperationContext* opCtx, bool isForward) const {
     return _newInterface->newCursor(opCtx, isForward);
 }
 
+std::unique_ptr<SortedDataInterface::Cursor> AbstractIndexAccessMethod::newCursor(
+    OperationContext* opCtx) const {
+    return newCursor(opCtx, true);
+}
+
 // Remove the provided doc from the index.
-Status IndexAccessMethod::remove(OperationContext* opCtx,
-                                 const BSONObj& obj,
-                                 const RecordId& loc,
-                                 const InsertDeleteOptions& options,
-                                 int64_t* numDeleted) {
+Status AbstractIndexAccessMethod::remove(OperationContext* opCtx,
+                                         const BSONObj& obj,
+                                         const RecordId& loc,
+                                         const InsertDeleteOptions& options,
+                                         int64_t* numDeleted) {
     invariant(numDeleted);
     *numDeleted = 0;
     BSONObjSet keys = SimpleBSONObjComparator::kInstance.makeBSONObjSet();
@@ -268,11 +274,11 @@ Status IndexAccessMethod::remove(OperationContext* opCtx,
     return Status::OK();
 }
 
-Status IndexAccessMethod::initializeAsEmpty(OperationContext* opCtx) {
+Status AbstractIndexAccessMethod::initializeAsEmpty(OperationContext* opCtx) {
     return _newInterface->initAsEmpty(opCtx);
 }
 
-Status IndexAccessMethod::touch(OperationContext* opCtx, const BSONObj& obj) {
+Status AbstractIndexAccessMethod::touch(OperationContext* opCtx, const BSONObj& obj) {
     BSONObjSet keys = SimpleBSONObjComparator::kInstance.makeBSONObjSet();
     // There's no need to compute the prefixes of the indexed fields that cause the index to be
     // multikey when paging a document's index entries into memory.
@@ -289,11 +295,12 @@ Status IndexAccessMethod::touch(OperationContext* opCtx, const BSONObj& obj) {
 }
 
 
-Status IndexAccessMethod::touch(OperationContext* opCtx) const {
+Status AbstractIndexAccessMethod::touch(OperationContext* opCtx) const {
     return _newInterface->touch(opCtx);
 }
 
-RecordId IndexAccessMethod::findSingle(OperationContext* opCtx, const BSONObj& requestedKey) const {
+RecordId AbstractIndexAccessMethod::findSingle(OperationContext* opCtx,
+                                               const BSONObj& requestedKey) const {
     // Generate the key for this index.
     BSONObj actualKey;
     if (_btreeState->getCollator()) {
@@ -327,26 +334,26 @@ RecordId IndexAccessMethod::findSingle(OperationContext* opCtx, const BSONObj& r
     return RecordId();
 }
 
-void IndexAccessMethod::validate(OperationContext* opCtx,
-                                 int64_t* numKeys,
-                                 ValidateResults* fullResults) {
+void AbstractIndexAccessMethod::validate(OperationContext* opCtx,
+                                         int64_t* numKeys,
+                                         ValidateResults* fullResults) {
     long long keys = 0;
     _newInterface->fullValidate(opCtx, &keys, fullResults);
     *numKeys = keys;
 }
 
-bool IndexAccessMethod::appendCustomStats(OperationContext* opCtx,
-                                          BSONObjBuilder* output,
-                                          double scale) const {
+bool AbstractIndexAccessMethod::appendCustomStats(OperationContext* opCtx,
+                                                  BSONObjBuilder* output,
+                                                  double scale) const {
     return _newInterface->appendCustomStats(opCtx, output, scale);
 }
 
-long long IndexAccessMethod::getSpaceUsedBytes(OperationContext* opCtx) const {
+long long AbstractIndexAccessMethod::getSpaceUsedBytes(OperationContext* opCtx) const {
     return _newInterface->getSpaceUsedBytes(opCtx);
 }
 
-pair<vector<BSONObj>, vector<BSONObj>> IndexAccessMethod::setDifference(const BSONObjSet& left,
-                                                                        const BSONObjSet& right) {
+pair<vector<BSONObj>, vector<BSONObj>> AbstractIndexAccessMethod::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();
@@ -381,13 +388,13 @@ pair<vector<BSONObj>, vector<BSONObj>> IndexAccessMethod::setDifference(const BS
     return {std::move(onlyLeft), std::move(onlyRight)};
 }
 
-Status IndexAccessMethod::validateUpdate(OperationContext* opCtx,
-                                         const BSONObj& from,
-                                         const BSONObj& to,
-                                         const RecordId& record,
-                                         const InsertDeleteOptions& options,
-                                         UpdateTicket* ticket,
-                                         const MatchExpression* indexFilter) {
+Status AbstractIndexAccessMethod::validateUpdate(OperationContext* opCtx,
+                                                 const BSONObj& from,
+                                                 const BSONObj& to,
+                                                 const RecordId& record,
+                                                 const InsertDeleteOptions& options,
+                                                 UpdateTicket* ticket,
+                                                 const MatchExpression* indexFilter) {
     if (!indexFilter || indexFilter->matchesBSON(from)) {
         // There's no need to compute the prefixes of the indexed fields that possibly caused the
         // index to be multikey when the old version of the document was written since the index
@@ -415,10 +422,10 @@ Status IndexAccessMethod::validateUpdate(OperationContext* opCtx,
     return Status::OK();
 }
 
-Status IndexAccessMethod::update(OperationContext* opCtx,
-                                 const UpdateTicket& ticket,
-                                 int64_t* numInserted,
-                                 int64_t* numDeleted) {
+Status AbstractIndexAccessMethod::update(OperationContext* opCtx,
+                                         const UpdateTicket& ticket,
+                                         int64_t* numInserted,
+                                         int64_t* numDeleted) {
     invariant(ticket.newKeys.size() ==
               ticket.oldKeys.size() + ticket.added.size() - ticket.removed.size());
     invariant(numInserted);
@@ -469,11 +476,11 @@ Status IndexAccessMethod::update(OperationContext* opCtx,
     return Status::OK();
 }
 
-Status IndexAccessMethod::compact(OperationContext* opCtx) {
+Status AbstractIndexAccessMethod::compact(OperationContext* opCtx) {
     return this->_newInterface->compact(opCtx);
 }
 
-std::unique_ptr<IndexAccessMethod::BulkBuilder> IndexAccessMethod::initiateBulk(
+std::unique_ptr<IndexAccessMethod::BulkBuilder> AbstractIndexAccessMethod::initiateBulk(
     size_t maxMemoryUsageBytes) {
     return std::unique_ptr<BulkBuilder>(new BulkBuilder(this, _descriptor, maxMemoryUsageBytes));
 }
@@ -528,11 +535,11 @@ IndexAccessMethod::BulkBuilder::Sorter::Iterator* IndexAccessMethod::BulkBuilder
     return _sorter->done();
 }
 
-Status IndexAccessMethod::commitBulk(OperationContext* opCtx,
-                                     BulkBuilder* bulk,
-                                     bool mayInterrupt,
-                                     bool dupsAllowed,
-                                     set<RecordId>* dupsToDrop) {
+Status AbstractIndexAccessMethod::commitBulk(OperationContext* opCtx,
+                                             BulkBuilder* bulk,
+                                             bool mayInterrupt,
+                                             bool dupsAllowed,
+                                             set<RecordId>* dupsToDrop) {
     Timer timer;
 
     std::unique_ptr<BulkBuilder::Sorter::Iterator> it(bulk->done());
@@ -614,15 +621,15 @@ Status IndexAccessMethod::commitBulk(OperationContext* opCtx,
     return Status::OK();
 }
 
-void IndexAccessMethod::setIndexIsMultikey(OperationContext* opCtx, MultikeyPaths paths) {
+void AbstractIndexAccessMethod::setIndexIsMultikey(OperationContext* opCtx, MultikeyPaths paths) {
     _btreeState->setMultikey(opCtx, paths);
 }
 
-void IndexAccessMethod::getKeys(const BSONObj& obj,
-                                GetKeysMode mode,
-                                BSONObjSet* keys,
-                                BSONObjSet* multikeyMetadataKeys,
-                                MultikeyPaths* multikeyPaths) const {
+void AbstractIndexAccessMethod::getKeys(const BSONObj& obj,
+                                        GetKeysMode mode,
+                                        BSONObjSet* keys,
+                                        BSONObjSet* multikeyMetadataKeys,
+                                        MultikeyPaths* multikeyPaths) const {
     // TODO SERVER-36385: Remove ErrorCodes::KeyTooLong.
     static stdx::unordered_set<int> whiteList{ErrorCodes::CannotBuildIndexKeys,
                                               // Btree
@@ -678,12 +685,17 @@ void IndexAccessMethod::getKeys(const BSONObj& obj,
     }
 }
 
-bool IndexAccessMethod::shouldMarkIndexAsMultikey(const BSONObjSet& keys,
-                                                  const BSONObjSet& multikeyMetadataKeys,
-                                                  const MultikeyPaths& multikeyPaths) const {
+bool AbstractIndexAccessMethod::shouldMarkIndexAsMultikey(
+    const BSONObjSet& keys,
+    const BSONObjSet& multikeyMetadataKeys,
+    const MultikeyPaths& multikeyPaths) const {
     return (keys.size() > 1 || isMultikeyFromPaths(multikeyPaths));
 }
 
+SortedDataInterface* AbstractIndexAccessMethod::getSortedDataInterface_forTest() const {
+    return _newInterface.get();
+}
+
 }  // namespace mongo
 
 #include "mongo/db/sorter/sorter.cpp"
diff --git a/src/mongo/db/index/index_access_method.h b/src/mongo/db/index/index_access_method.h
index 404ec76243f..ff5fd462bcf 100644
--- a/src/mongo/db/index/index_access_method.h
+++ b/src/mongo/db/index/index_access_method.h
@@ -65,8 +65,8 @@ class IndexAccessMethod {
     MONGO_DISALLOW_COPYING(IndexAccessMethod);
 
 public:
-    IndexAccessMethod(IndexCatalogEntry* btreeState, SortedDataInterface* btree);
-    virtual ~IndexAccessMethod() {}
+    IndexAccessMethod() = default;
+    virtual ~IndexAccessMethod() = default;
 
     //
     // Lookup, traversal, and mutation support
@@ -80,21 +80,21 @@ public:
      *
      * The behavior of the insertion can be specified through 'options'.
      */
-    Status insert(OperationContext* opCtx,
-                  const BSONObj& obj,
-                  const RecordId& loc,
-                  const InsertDeleteOptions& options,
-                  int64_t* numInserted);
+    virtual Status insert(OperationContext* opCtx,
+                          const BSONObj& obj,
+                          const RecordId& loc,
+                          const InsertDeleteOptions& options,
+                          int64_t* numInserted) = 0;
 
     /**
      * Analogous to above, but remove the records instead of inserting them.
      * 'numDeleted' will be set to the number of keys removed from the index for the document.
      */
-    Status remove(OperationContext* opCtx,
-                  const BSONObj& obj,
-                  const RecordId& loc,
-                  const InsertDeleteOptions& options,
-                  int64_t* numDeleted);
+    virtual Status remove(OperationContext* opCtx,
+                          const BSONObj& obj,
+                          const RecordId& loc,
+                          const InsertDeleteOptions& options,
+                          int64_t* numDeleted) = 0;
 
     /**
      * Checks whether the index entries for the document 'from', which is placed at location
@@ -106,13 +106,13 @@ public:
      *
      * There is no obligation to perform the update after performing validation.
      */
-    Status validateUpdate(OperationContext* opCtx,
-                          const BSONObj& from,
-                          const BSONObj& to,
-                          const RecordId& loc,
-                          const InsertDeleteOptions& options,
-                          UpdateTicket* ticket,
-                          const MatchExpression* indexFilter);
+    virtual Status validateUpdate(OperationContext* opCtx,
+                                  const BSONObj& from,
+                                  const BSONObj& to,
+                                  const RecordId& loc,
+                                  const InsertDeleteOptions& options,
+                                  UpdateTicket* ticket,
+                                  const MatchExpression* indexFilter) = 0;
 
     /**
      * Perform a validated update.  The keys for the 'from' object will be removed, and the keys
@@ -125,16 +125,18 @@ public:
      * 'numInserted' will be set to the number of keys inserted into the index for the document.
      * 'numDeleted' will be set to the number of keys removed from the index for the document.
      */
-    Status update(OperationContext* opCtx,
-                  const UpdateTicket& ticket,
-                  int64_t* numInserted,
-                  int64_t* numDeleted);
+    virtual Status update(OperationContext* opCtx,
+                          const UpdateTicket& ticket,
+                          int64_t* numInserted,
+                          int64_t* numDeleted) = 0;
 
     /**
      * Returns an unpositioned cursor over 'this' index.
      */
-    std::unique_ptr<SortedDataInterface::Cursor> newCursor(OperationContext* opCtx,
-                                                           bool isForward = true) const;
+    virtual std::unique_ptr<SortedDataInterface::Cursor> newCursor(OperationContext* opCtx,
+                                                                   bool isForward) const = 0;
+    virtual std::unique_ptr<SortedDataInterface::Cursor> newCursor(
+        OperationContext* opCtx) const = 0;
 
     // ------ index level operations ------
 
@@ -144,7 +146,7 @@ public:
      * only called once for the lifetime of the index
      * if called multiple times, is an error
      */
-    Status initializeAsEmpty(OperationContext* opCtx);
+    virtual Status initializeAsEmpty(OperationContext* opCtx) = 0;
 
     /**
      * Try to page-in the pages that contain the keys generated from 'obj'.
@@ -152,18 +154,20 @@ public:
      * appropriate pages are not swapped out.
      * See prefetch.cpp.
      */
-    Status touch(OperationContext* opCtx, const BSONObj& obj);
+    virtual Status touch(OperationContext* opCtx, const BSONObj& obj) = 0;
 
     /**
      * this pages in the entire index
      */
-    Status touch(OperationContext* opCtx) const;
+    virtual Status touch(OperationContext* opCtx) const = 0;
 
     /**
      * Walk the entire index, checking the internal structure for consistency.
      * Set numKeys to the number of keys in the index.
      */
-    void validate(OperationContext* opCtx, int64_t* numKeys, ValidateResults* fullResults);
+    virtual void validate(OperationContext* opCtx,
+                          int64_t* numKeys,
+                          ValidateResults* fullResults) = 0;
 
     /**
      * Add custom statistics about this index to BSON object builder, for display.
@@ -172,26 +176,28 @@ public:
      *
      * Returns true if stats were appended.
      */
-    bool appendCustomStats(OperationContext* opCtx, BSONObjBuilder* result, double scale) const;
+    virtual bool appendCustomStats(OperationContext* opCtx,
+                                   BSONObjBuilder* result,
+                                   double scale) const = 0;
 
     /**
      * @return The number of bytes consumed by this index.
      *         Exactly what is counted is not defined based on padding, re-use, etc...
      */
-    long long getSpaceUsedBytes(OperationContext* opCtx) const;
+    virtual long long getSpaceUsedBytes(OperationContext* opCtx) const = 0;
 
-    RecordId findSingle(OperationContext* opCtx, const BSONObj& key) const;
+    virtual RecordId findSingle(OperationContext* opCtx, const BSONObj& key) const = 0;
 
     /**
      * Attempt compaction to regain disk space if the indexed record store supports
      * compaction-in-place.
      */
-    Status compact(OperationContext* opCtx);
+    virtual Status compact(OperationContext* opCtx) = 0;
 
     /**
      * Sets this index as multikey with the provided paths.
      */
-    void setIndexIsMultikey(OperationContext* opCtx, MultikeyPaths paths);
+    virtual void setIndexIsMultikey(OperationContext* opCtx, MultikeyPaths paths) = 0;
 
     //
     // Bulk operations support
@@ -224,7 +230,7 @@ public:
         Sorter::Iterator* done();
 
     private:
-        friend class IndexAccessMethod;
+        friend class AbstractIndexAccessMethod;
 
         BulkBuilder(const IndexAccessMethod* index,
                     const IndexDescriptor* descriptor,
@@ -257,7 +263,7 @@ public:
      * maxMemoryUsageBytes: amount of memory consumed before the external sorter starts spilling to
      *                      disk
      */
-    std::unique_ptr<BulkBuilder> initiateBulk(size_t maxMemoryUsageBytes);
+    virtual std::unique_ptr<BulkBuilder> initiateBulk(size_t maxMemoryUsageBytes) = 0;
 
     /**
      * Call this when you are ready to finish your bulk work.
@@ -268,11 +274,11 @@ public:
      * @param dups - if NULL, error out on dups if not allowed
      *               if not NULL, put the bad RecordIds there
      */
-    Status commitBulk(OperationContext* opCtx,
-                      BulkBuilder* bulk,
-                      bool mayInterrupt,
-                      bool dupsAllowed,
-                      std::set<RecordId>* dups);
+    virtual Status commitBulk(OperationContext* opCtx,
+                              BulkBuilder* bulk,
+                              bool mayInterrupt,
+                              bool dupsAllowed,
+                              std::set<RecordId>* dups) = 0;
 
     /**
      * Specifies whether getKeys should relax the index constraints or not, in order of most
@@ -304,11 +310,11 @@ public:
      * keys are not associated with the document itself, but instead represent multi-key path
      * information that must be stored in a reserved keyspace within the index.
      */
-    void getKeys(const BSONObj& obj,
-                 GetKeysMode mode,
-                 BSONObjSet* keys,
-                 BSONObjSet* multikeyMetadataKeys,
-                 MultikeyPaths* multikeyPaths) const;
+    virtual void getKeys(const BSONObj& obj,
+                         GetKeysMode mode,
+                         BSONObjSet* keys,
+                         BSONObjSet* multikeyMetadataKeys,
+                         MultikeyPaths* multikeyPaths) const = 0;
 
     /**
      * Given the set of keys, multikeyMetadataKeys and multikeyPaths generated by a particular
@@ -316,18 +322,7 @@ public:
      */
     virtual bool shouldMarkIndexAsMultikey(const BSONObjSet& keys,
                                            const BSONObjSet& multikeyMetadataKeys,
-                                           const MultikeyPaths& multikeyPaths) const;
-
-    /**
-     * 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);
+                                           const MultikeyPaths& multikeyPaths) const = 0;
 
     /**
      * Returns the set of multikey metadata paths stored in the index. Only index types which can
@@ -342,60 +337,7 @@ public:
      * For test use only. Provides direct access to the SortedDataInterface, allowing tests to write
      * invalid entries that would otherwise not be possible via IndexAccessMethod.
      */
-    SortedDataInterface* getSortedDataInterface_forTest() {
-        return _newInterface.get();
-    }
-
-protected:
-    /**
-     * Fills 'keys' with the keys that should be generated for 'obj' on this index.
-     *
-     * If the 'multikeyPaths' pointer is non-null, then it must point to an empty vector. If this
-     * index type supports tracking path-level multikey information, then this function resizes
-     * 'multikeyPaths' to have the same number of elements as the index key pattern and fills each
-     * element with the prefixes of the indexed field that would cause this index to be multikey as
-     * a result of inserting 'keys'.
-     *
-     * If the 'multikeyMetadataKeys' pointer is non-null, then the function will populate the
-     * BSONObjSet with any multikey metadata keys generated while processing the document. These
-     * keys are not associated with the document itself, but instead represent multi-key path
-     * information that must be stored in a reserved keyspace within the index.
-     */
-    virtual void doGetKeys(const BSONObj& obj,
-                           BSONObjSet* keys,
-                           BSONObjSet* multikeyMetadataKeys,
-                           MultikeyPaths* multikeyPaths) const = 0;
-
-    /**
-     * Determine whether the given Status represents an exception that should cause the indexing
-     * process to abort. The 'key' argument is passed in to allow the offending entry to be logged
-     * in the event that a non-fatal 'ErrorCodes::DuplicateKeyValue' is encountered during a
-     * background index build.
-     */
-    bool isFatalError(OperationContext* opCtx, Status status, BSONObj key);
-
-    IndexCatalogEntry* _btreeState;  // owned by IndexCatalogEntry
-    const IndexDescriptor* _descriptor;
-
-private:
-    /**
-     * Determines whether it's OK to ignore ErrorCodes::KeyTooLong for this OperationContext
-     * TODO SERVER-36385: Remove this function.
-     */
-    bool ignoreKeyTooLong();
-
-    /**
-     * If true, we should check whether the index key exceeds the hardcoded limit.
-     * TODO SERVER-36385: Remove this function.
-     */
-    bool shouldCheckIndexKeySize(OperationContext* opCtx);
-
-    void removeOneKey(OperationContext* opCtx,
-                      const BSONObj& key,
-                      const RecordId& loc,
-                      bool dupsAllowed);
-
-    const std::unique_ptr<SortedDataInterface> _newInterface;
+    virtual SortedDataInterface* getSortedDataInterface_forTest() const = 0;
 };
 
 /**
@@ -410,7 +352,7 @@ public:
           newMultikeyMetadataKeys(newKeys) {}
 
 private:
-    friend class IndexAccessMethod;
+    friend class AbstractIndexAccessMethod;
 
     bool _isValid{false};
 
@@ -446,4 +388,155 @@ struct InsertDeleteOptions {
         IndexAccessMethod::GetKeysMode::kEnforceConstraints;
 };
 
+/**
+ * Provides implementations for many functions in the IndexAccessMethod interface that will be
+ * shared across concrete implementations.
+ *
+ * IndexCatalogEntry owns an instance of IndexAccessMethod; an IndexCatalogEntry is also required
+ * for the initialization and core functionality of this abstract class. To avoid any circular
+ * dependencies, it is important that IndexAccessMethod remain an interface.
+ */
+class AbstractIndexAccessMethod : public IndexAccessMethod {
+    MONGO_DISALLOW_COPYING(AbstractIndexAccessMethod);
+
+public:
+    /**
+     * 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);
+
+    AbstractIndexAccessMethod(IndexCatalogEntry* btreeState, SortedDataInterface* btree);
+
+    Status insert(OperationContext* opCtx,
+                  const BSONObj& obj,
+                  const RecordId& loc,
+                  const InsertDeleteOptions& options,
+                  int64_t* numInserted) final;
+
+    Status remove(OperationContext* opCtx,
+                  const BSONObj& obj,
+                  const RecordId& loc,
+                  const InsertDeleteOptions& options,
+                  int64_t* numDeleted) final;
+
+    Status validateUpdate(OperationContext* opCtx,
+                          const BSONObj& from,
+                          const BSONObj& to,
+                          const RecordId& loc,
+                          const InsertDeleteOptions& options,
+                          UpdateTicket* ticket,
+                          const MatchExpression* indexFilter) final;
+
+    Status update(OperationContext* opCtx,
+                  const UpdateTicket& ticket,
+                  int64_t* numInserted,
+                  int64_t* numDeleted) final;
+
+    std::unique_ptr<SortedDataInterface::Cursor> newCursor(OperationContext* opCtx,
+                                                           bool isForward) const final;
+    std::unique_ptr<SortedDataInterface::Cursor> newCursor(OperationContext* opCtx) const final;
+
+    Status initializeAsEmpty(OperationContext* opCtx) final;
+
+    Status touch(OperationContext* opCtx, const BSONObj& obj) final;
+
+    Status touch(OperationContext* opCtx) const final;
+
+    void validate(OperationContext* opCtx, int64_t* numKeys, ValidateResults* fullResults) final;
+
+    bool appendCustomStats(OperationContext* opCtx,
+                           BSONObjBuilder* result,
+                           double scale) const final;
+
+    long long getSpaceUsedBytes(OperationContext* opCtx) const final;
+
+    RecordId findSingle(OperationContext* opCtx, const BSONObj& key) const final;
+
+    Status compact(OperationContext* opCtx) final;
+
+    void setIndexIsMultikey(OperationContext* opCtx, MultikeyPaths paths) final;
+
+    std::unique_ptr<BulkBuilder> initiateBulk(size_t maxMemoryUsageBytes) final;
+
+    Status commitBulk(OperationContext* opCtx,
+                      BulkBuilder* bulk,
+                      bool mayInterrupt,
+                      bool dupsAllowed,
+                      std::set<RecordId>* dups) final;
+
+    void getKeys(const BSONObj& obj,
+                 GetKeysMode mode,
+                 BSONObjSet* keys,
+                 BSONObjSet* multikeyMetadataKeys,
+                 MultikeyPaths* multikeyPaths) const final;
+
+    bool shouldMarkIndexAsMultikey(const BSONObjSet& keys,
+                                   const BSONObjSet& multikeyMetadataKeys,
+                                   const MultikeyPaths& multikeyPaths) const override;
+
+    SortedDataInterface* getSortedDataInterface_forTest() const final;
+
+protected:
+    /**
+     * Fills 'keys' with the keys that should be generated for 'obj' on this index.
+     *
+     * If the 'multikeyPaths' pointer is non-null, then it must point to an empty vector. If this
+     * index type supports tracking path-level multikey information, then this function resizes
+     * 'multikeyPaths' to have the same number of elements as the index key pattern and fills each
+     * element with the prefixes of the indexed field that would cause this index to be multikey as
+     * a result of inserting 'keys'.
+     *
+     * If the 'multikeyMetadataKeys' pointer is non-null, then the function will populate the
+     * BSONObjSet with any multikey metadata keys generated while processing the document. These
+     * keys are not associated with the document itself, but instead represent multi-key path
+     * information that must be stored in a reserved keyspace within the index.
+     */
+    virtual void doGetKeys(const BSONObj& obj,
+                           BSONObjSet* keys,
+                           BSONObjSet* multikeyMetadataKeys,
+                           MultikeyPaths* multikeyPaths) const = 0;
+
+    IndexCatalogEntry* const _btreeState;  // owned by IndexCatalogEntry
+    const IndexDescriptor* const _descriptor;
+
+private:
+    /**
+     * Determine whether the given Status represents an exception that should cause the indexing
+     * process to abort. The 'key' argument is passed in to allow the offending entry to be logged
+     * in the event that a non-fatal 'ErrorCodes::DuplicateKeyValue' is encountered during a
+     * background index build.
+     */
+    bool isFatalError(OperationContext* opCtx, Status status, BSONObj key);
+
+    /**
+     * Determines whether it's OK to ignore ErrorCodes::KeyTooLong for this OperationContext
+     * TODO SERVER-36385: Remove this function.
+     */
+    bool ignoreKeyTooLong();
+
+    /**
+     * If true, we should check whether the index key exceeds the hardcoded limit.
+     * TODO SERVER-36385: Remove this function.
+     */
+    bool shouldCheckIndexKeySize(OperationContext* opCtx);
+
+    /**
+     * Removes a single key from the index.
+     *
+     * Used by remove() only.
+     */
+    void removeOneKey(OperationContext* opCtx,
+                      const BSONObj& key,
+                      const RecordId& loc,
+                      bool dupsAllowed);
+
+    const std::unique_ptr<SortedDataInterface> _newInterface;
+};
+
 }  // namespace mongo
diff --git a/src/mongo/db/index/s2_access_method.cpp b/src/mongo/db/index/s2_access_method.cpp
index 6e7c17569f9..fdf4ee33583 100644
--- a/src/mongo/db/index/s2_access_method.cpp
+++ b/src/mongo/db/index/s2_access_method.cpp
@@ -47,7 +47,7 @@ namespace mongo {
 static const string kIndexVersionFieldName("2dsphereIndexVersion");
 
 S2AccessMethod::S2AccessMethod(IndexCatalogEntry* btreeState, SortedDataInterface* btree)
-    : IndexAccessMethod(btreeState, btree) {
+    : AbstractIndexAccessMethod(btreeState, btree) {
     const IndexDescriptor* descriptor = btreeState->descriptor();
 
     ExpressionParams::initialize2dsphereParams(
diff --git a/src/mongo/db/index/s2_access_method.h b/src/mongo/db/index/s2_access_method.h
index bc4456cabe8..d9278a5edf9 100644
--- a/src/mongo/db/index/s2_access_method.h
+++ b/src/mongo/db/index/s2_access_method.h
@@ -37,7 +37,7 @@
 
 namespace mongo {
 
-class S2AccessMethod : public IndexAccessMethod {
+class S2AccessMethod : public AbstractIndexAccessMethod {
 public:
     S2AccessMethod(IndexCatalogEntry* btreeState, SortedDataInterface* btree);
 
diff --git a/src/mongo/db/index/wildcard_access_method.cpp b/src/mongo/db/index/wildcard_access_method.cpp
index 4816c29ac22..072bf6d1980 100644
--- a/src/mongo/db/index/wildcard_access_method.cpp
+++ b/src/mongo/db/index/wildcard_access_method.cpp
@@ -36,7 +36,7 @@ namespace mongo {
 
 WildcardAccessMethod::WildcardAccessMethod(IndexCatalogEntry* wildcardState,
                                            SortedDataInterface* btree)
-    : IndexAccessMethod(wildcardState, btree),
+    : AbstractIndexAccessMethod(wildcardState, btree),
       _keyGen(
           _descriptor->keyPattern(), _descriptor->pathProjection(), _btreeState->getCollator()) {}
 
diff --git a/src/mongo/db/index/wildcard_access_method.h b/src/mongo/db/index/wildcard_access_method.h
index e7c061f5134..096fcf744a4 100644
--- a/src/mongo/db/index/wildcard_access_method.h
+++ b/src/mongo/db/index/wildcard_access_method.h
@@ -41,7 +41,7 @@ namespace mongo {
  * $** indexes store a special metadata key for each path in the index that is multikey. This class
  * provides an interface to access the multikey metadata: see getMultikeyPathSet().
  */
-class WildcardAccessMethod final : public IndexAccessMethod {
+class WildcardAccessMethod final : public AbstractIndexAccessMethod {
 public:
     WildcardAccessMethod(IndexCatalogEntry* wildcardState, SortedDataInterface* btree);
 
diff --git a/src/mongo/dbtests/index_access_method_test.cpp b/src/mongo/dbtests/index_access_method_test.cpp
index 44ee0eddabd..b4cf7cdf8f5 100644
--- a/src/mongo/dbtests/index_access_method_test.cpp
+++ b/src/mongo/dbtests/index_access_method_test.cpp
@@ -43,7 +43,7 @@ TEST(IndexAccessMethodSetDifference, EmptyInputsShouldHaveNoDifference) {
     SimpleBSONObjComparator bsonCmp;
     BSONObjSet left = bsonCmp.makeBSONObjSet();
     BSONObjSet right = bsonCmp.makeBSONObjSet();
-    auto diff = IndexAccessMethod::setDifference(left, right);
+    auto diff = AbstractIndexAccessMethod::setDifference(left, right);
     ASSERT_EQ(0UL, diff.first.size());
     ASSERT_EQ(0UL, diff.second.size());
 }
@@ -52,7 +52,7 @@ TEST(IndexAccessMethodSetDifference, EmptyLeftShouldHaveNoDifference) {
     SimpleBSONObjComparator bsonCmp;
     BSONObjSet left = bsonCmp.makeBSONObjSet();
     BSONObjSet right = bsonCmp.makeBSONObjSet({BSON("" << 0)});
-    auto diff = IndexAccessMethod::setDifference(left, right);
+    auto diff = AbstractIndexAccessMethod::setDifference(left, right);
     ASSERT_EQ(0UL, diff.first.size());
     ASSERT_EQ(1UL, diff.second.size());
 }
@@ -61,7 +61,7 @@ TEST(IndexAccessMethodSetDifference, EmptyRightShouldReturnAllOfLeft) {
     SimpleBSONObjComparator bsonCmp;
     BSONObjSet left = bsonCmp.makeBSONObjSet({BSON("" << 0), BSON("" << 1)});
     BSONObjSet right = bsonCmp.makeBSONObjSet();
-    auto diff = IndexAccessMethod::setDifference(left, right);
+    auto diff = AbstractIndexAccessMethod::setDifference(left, right);
     ASSERT_EQ(2UL, diff.first.size());
     ASSERT_EQ(0UL, diff.second.size());
 }
@@ -76,7 +76,7 @@ TEST(IndexAccessMethodSetDifference, IdenticalSetsShouldHaveNoDifference) {
                                                BSON(""
                                                     << "string"),
                                                BSON("" << BSONNULL)});
-    auto diff = IndexAccessMethod::setDifference(left, right);
+    auto diff = AbstractIndexAccessMethod::setDifference(left, right);
     ASSERT_EQ(0UL, diff.first.size());
     ASSERT_EQ(0UL, diff.second.size());
 }
@@ -89,7 +89,7 @@ void assertDistinct(BSONObj left, BSONObj right) {
     SimpleBSONObjComparator bsonCmp;
     BSONObjSet leftSet = bsonCmp.makeBSONObjSet({left});
     BSONObjSet rightSet = bsonCmp.makeBSONObjSet({right});
-    auto diff = IndexAccessMethod::setDifference(leftSet, rightSet);
+    auto diff = AbstractIndexAccessMethod::setDifference(leftSet, rightSet);
     ASSERT_EQ(1UL, diff.first.size());
     ASSERT_EQ(1UL, diff.second.size());
 }
@@ -145,7 +145,7 @@ TEST(IndexAccessMethodSetDifference, ShouldDetectOneDifferenceAmongManySimilarit
                                 BSON("" << BSON("sub"
                                                 << "document")),
                                 BSON("" << BSON_ARRAY(1 << "hi" << 42))});
-    auto diff = IndexAccessMethod::setDifference(left, right);
+    auto diff = AbstractIndexAccessMethod::setDifference(left, right);
     ASSERT_EQUALS(1UL, diff.first.size());
     ASSERT_EQUALS(1UL, diff.second.size());
 }
@@ -154,7 +154,7 @@ TEST(IndexAccessMethodSetDifference, SingleObjInLeftShouldFindCorrespondingObjIn
     SimpleBSONObjComparator bsonCmp;
     BSONObjSet left = bsonCmp.makeBSONObjSet({BSON("" << 2)});
     BSONObjSet right = bsonCmp.makeBSONObjSet({BSON("" << 1), BSON("" << 2), BSON("" << 3)});
-    auto diff = IndexAccessMethod::setDifference(left, right);
+    auto diff = AbstractIndexAccessMethod::setDifference(left, right);
     ASSERT_EQUALS(0UL, diff.first.size());
     ASSERT_EQUALS(2UL, diff.second.size());
 }
@@ -163,7 +163,7 @@ TEST(IndexAccessMethodSetDifference, SingleObjInRightShouldFindCorrespondingObjI
     SimpleBSONObjComparator bsonCmp;
     BSONObjSet left = bsonCmp.makeBSONObjSet({BSON("" << 1), BSON("" << 2), BSON("" << 3)});
     BSONObjSet right = bsonCmp.makeBSONObjSet({BSON("" << 2)});
-    auto diff = IndexAccessMethod::setDifference(left, right);
+    auto diff = AbstractIndexAccessMethod::setDifference(left, right);
     ASSERT_EQUALS(2UL, diff.first.size());
     ASSERT_EQUALS(0UL, diff.second.size());
 }
@@ -172,7 +172,7 @@ TEST(IndexAccessMethodSetDifference, LeftSetAllSmallerThanRightShouldBeDisjoint)
     SimpleBSONObjComparator bsonCmp;
     BSONObjSet left = bsonCmp.makeBSONObjSet({BSON("" << 1), BSON("" << 2), BSON("" << 3)});
     BSONObjSet right = bsonCmp.makeBSONObjSet({BSON("" << 4), BSON("" << 5), BSON("" << 6)});
-    auto diff = IndexAccessMethod::setDifference(left, right);
+    auto diff = AbstractIndexAccessMethod::setDifference(left, right);
     ASSERT_EQUALS(3UL, diff.first.size());
     ASSERT_EQUALS(3UL, diff.second.size());
     for (auto&& obj : diff.first) {
@@ -187,7 +187,7 @@ TEST(IndexAccessMethodSetDifference, LeftSetAllLargerThanRightShouldBeDisjoint)
     SimpleBSONObjComparator bsonCmp;
     BSONObjSet left = bsonCmp.makeBSONObjSet({BSON("" << 4), BSON("" << 5), BSON("" << 6)});
     BSONObjSet right = bsonCmp.makeBSONObjSet({BSON("" << 1), BSON("" << 2), BSON("" << 3)});
-    auto diff = IndexAccessMethod::setDifference(left, right);
+    auto diff = AbstractIndexAccessMethod::setDifference(left, right);
     ASSERT_EQUALS(3UL, diff.first.size());
     ASSERT_EQUALS(3UL, diff.second.size());
     for (auto&& obj : diff.first) {
@@ -204,7 +204,7 @@ TEST(IndexAccessMethodSetDifference, ShouldNotReportOverlapsFromNonDisjointSets)
         bsonCmp.makeBSONObjSet({BSON("" << 0), BSON("" << 1), BSON("" << 4), BSON("" << 6)});
     BSONObjSet right = bsonCmp.makeBSONObjSet(
         {BSON("" << -1), BSON("" << 1), BSON("" << 3), BSON("" << 4), BSON("" << 7)});
-    auto diff = IndexAccessMethod::setDifference(left, right);
+    auto diff = AbstractIndexAccessMethod::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) {