SERVER-18579: Clang-Format - reformat code, no comment reflow

27 files changed, 3142 insertions, 3128 deletions

diff --git a/src/mongo/db/index/2d_access_method.cpp b/src/mongo/db/index/2d_access_method.cpp
index db421cb0ffe..531df3369b1 100644
--- a/src/mongo/db/index/2d_access_method.cpp
+++ b/src/mongo/db/index/2d_access_method.cpp
@@ -39,23 +39,21 @@
 
 namespace mongo {
 
-    TwoDAccessMethod::TwoDAccessMethod(IndexCatalogEntry* btreeState,
-                                       SortedDataInterface* btree)
-        : IndexAccessMethod(btreeState, btree) {
-
-        const IndexDescriptor* descriptor = btreeState->descriptor();
-
-        ExpressionParams::parseTwoDParams(descriptor->infoObj(), &_params);
-    }
-
-    /** Finds the key objects to put in an index */
-    void TwoDAccessMethod::getKeys(const BSONObj& obj, BSONObjSet* keys) const {
-        ExpressionKeysPrivate::get2DKeys(obj, _params, keys, NULL);
-    }
-
-    /** Finds all locations in a geo-indexed object */
-    void TwoDAccessMethod::getKeys(const BSONObj& obj, vector<BSONObj>& locs) const {
-        ExpressionKeysPrivate::get2DKeys(obj, _params, NULL, &locs);
-    }
+TwoDAccessMethod::TwoDAccessMethod(IndexCatalogEntry* btreeState, SortedDataInterface* btree)
+    : IndexAccessMethod(btreeState, btree) {
+    const IndexDescriptor* descriptor = btreeState->descriptor();
+
+    ExpressionParams::parseTwoDParams(descriptor->infoObj(), &_params);
+}
+
+/** Finds the key objects to put in an index */
+void TwoDAccessMethod::getKeys(const BSONObj& obj, BSONObjSet* keys) const {
+    ExpressionKeysPrivate::get2DKeys(obj, _params, keys, NULL);
+}
+
+/** Finds all locations in a geo-indexed object */
+void TwoDAccessMethod::getKeys(const BSONObj& obj, vector<BSONObj>& locs) const {
+    ExpressionKeysPrivate::get2DKeys(obj, _params, NULL, &locs);
+}
 
 }  // namespace mongo
diff --git a/src/mongo/db/index/2d_access_method.h b/src/mongo/db/index/2d_access_method.h
index 208df9235cd..644b6addc5b 100644
--- a/src/mongo/db/index/2d_access_method.h
+++ b/src/mongo/db/index/2d_access_method.h
@@ -35,25 +35,28 @@
 
 namespace mongo {
 
-    class IndexCatalogEntry;
-    class IndexDescriptor;
-    struct TwoDIndexingParams;
+class IndexCatalogEntry;
+class IndexDescriptor;
+struct TwoDIndexingParams;
 
-    class TwoDAccessMethod : public IndexAccessMethod {
-    public:
-        TwoDAccessMethod(IndexCatalogEntry* btreeState, SortedDataInterface* btree);
+class TwoDAccessMethod : public IndexAccessMethod {
+public:
+    TwoDAccessMethod(IndexCatalogEntry* btreeState, SortedDataInterface* btree);
 
-    private:
+private:
+    const IndexDescriptor* getDescriptor() {
+        return _descriptor;
+    }
+    TwoDIndexingParams& getParams() {
+        return _params;
+    }
 
-        const IndexDescriptor* getDescriptor() { return _descriptor; }
-        TwoDIndexingParams& getParams() { return _params; }
+    // This really gets the 'locs' from the provided obj.
+    void getKeys(const BSONObj& obj, std::vector<BSONObj>& locs) const;
 
-        // This really gets the 'locs' from the provided obj.
-        void getKeys(const BSONObj& obj, std::vector<BSONObj>& locs) const;
+    virtual void getKeys(const BSONObj& obj, BSONObjSet* keys) const;
 
-        virtual void getKeys(const BSONObj& obj, BSONObjSet* keys) const;
-
-        TwoDIndexingParams _params;
-    };
+    TwoDIndexingParams _params;
+};
 
 }  // namespace mongo
diff --git a/src/mongo/db/index/2d_common.h b/src/mongo/db/index/2d_common.h
index d30b8cd07df..e3ed231f9a4 100644
--- a/src/mongo/db/index/2d_common.h
+++ b/src/mongo/db/index/2d_common.h
@@ -35,10 +35,10 @@
 
 namespace mongo {
 
-    struct TwoDIndexingParams {
-        std::string geo;
-        std::vector<std::pair<std::string, int> > other;
-        std::shared_ptr<GeoHashConverter> geoHashConverter;
-    };
+struct TwoDIndexingParams {
+    std::string geo;
+    std::vector<std::pair<std::string, int>> other;
+    std::shared_ptr<GeoHashConverter> geoHashConverter;
+};
 
 }  // namespace mongo
diff --git a/src/mongo/db/index/btree_access_method.cpp b/src/mongo/db/index/btree_access_method.cpp
index 7bb294342c8..6bc97956fe8 100644
--- a/src/mongo/db/index/btree_access_method.cpp
+++ b/src/mongo/db/index/btree_access_method.cpp
@@ -36,36 +36,33 @@
 
 namespace mongo {
 
-    using std::vector;
+using std::vector;
 
-    // Standard Btree implementation below.
-    BtreeAccessMethod::BtreeAccessMethod(IndexCatalogEntry* btreeState, SortedDataInterface* btree )
-        : IndexAccessMethod(btreeState, btree) {
+// Standard Btree implementation below.
+BtreeAccessMethod::BtreeAccessMethod(IndexCatalogEntry* btreeState, SortedDataInterface* btree)
+    : IndexAccessMethod(btreeState, btree) {
+    // The key generation wants these values.
+    vector<const char*> fieldNames;
+    vector<BSONElement> fixed;
 
-        // The key generation wants these values.
-        vector<const char*> fieldNames;
-        vector<BSONElement> fixed;
-
-        BSONObjIterator it(_descriptor->keyPattern());
-        while (it.more()) {
-            BSONElement elt = it.next();
-            fieldNames.push_back(elt.fieldName());
-            fixed.push_back(BSONElement());
-        }
-
-        if (0 == _descriptor->version()) {
-            _keyGenerator.reset(new BtreeKeyGeneratorV0(fieldNames, fixed,
-                _descriptor->isSparse()));
-        } else if (1 == _descriptor->version()) {
-            _keyGenerator.reset(new BtreeKeyGeneratorV1(fieldNames, fixed,
-                _descriptor->isSparse()));
-        } else {
-            massert(16745, "Invalid index version for key generation.", false );
-        }
+    BSONObjIterator it(_descriptor->keyPattern());
+    while (it.more()) {
+        BSONElement elt = it.next();
+        fieldNames.push_back(elt.fieldName());
+        fixed.push_back(BSONElement());
     }
 
-    void BtreeAccessMethod::getKeys(const BSONObj& obj, BSONObjSet* keys) const {
-        _keyGenerator->getKeys(obj, keys);
+    if (0 == _descriptor->version()) {
+        _keyGenerator.reset(new BtreeKeyGeneratorV0(fieldNames, fixed, _descriptor->isSparse()));
+    } else if (1 == _descriptor->version()) {
+        _keyGenerator.reset(new BtreeKeyGeneratorV1(fieldNames, fixed, _descriptor->isSparse()));
+    } else {
+        massert(16745, "Invalid index version for key generation.", false);
     }
+}
+
+void BtreeAccessMethod::getKeys(const BSONObj& obj, BSONObjSet* keys) const {
+    _keyGenerator->getKeys(obj, keys);
+}
 
 }  // namespace mongo
diff --git a/src/mongo/db/index/btree_access_method.h b/src/mongo/db/index/btree_access_method.h
index 4133b41b892..4c20deeb931 100644
--- a/src/mongo/db/index/btree_access_method.h
+++ b/src/mongo/db/index/btree_access_method.h
@@ -37,21 +37,21 @@
 
 namespace mongo {
 
-    class IndexDescriptor;
-
-    /**
-     * The IndexAccessMethod for a Btree index.
-     * Any index created with {field: 1} or {field: -1} uses this.
-     */
-    class BtreeAccessMethod : public IndexAccessMethod {
-    public:
-        BtreeAccessMethod(IndexCatalogEntry* btreeState, SortedDataInterface* btree );
-
-    private:
-        virtual void getKeys(const BSONObj& obj, BSONObjSet* keys) const;
-
-        // Our keys differ for V0 and V1.
-        std::unique_ptr<BtreeKeyGenerator> _keyGenerator;
-    };
+class IndexDescriptor;
+
+/**
+ * The IndexAccessMethod for a Btree index.
+ * Any index created with {field: 1} or {field: -1} uses this.
+ */
+class BtreeAccessMethod : public IndexAccessMethod {
+public:
+    BtreeAccessMethod(IndexCatalogEntry* btreeState, SortedDataInterface* btree);
+
+private:
+    virtual void getKeys(const BSONObj& obj, BSONObjSet* keys) const;
+
+    // Our keys differ for V0 and V1.
+    std::unique_ptr<BtreeKeyGenerator> _keyGenerator;
+};
 
 }  // namespace mongo
diff --git a/src/mongo/db/index/btree_key_generator.cpp b/src/mongo/db/index/btree_key_generator.cpp
index bccf688e468..e323272b044 100644
--- a/src/mongo/db/index/btree_key_generator.cpp
+++ b/src/mongo/db/index/btree_key_generator.cpp
@@ -32,361 +32,358 @@
 
 namespace mongo {
 
-    // SortStage checks for this error code in order to informatively error when we try to sort keys
-    // with parallel arrays.
-    const int BtreeKeyGenerator::ParallelArraysCode = 10088;
+// SortStage checks for this error code in order to informatively error when we try to sort keys
+// with parallel arrays.
+const int BtreeKeyGenerator::ParallelArraysCode = 10088;
 
 namespace {
 
-    const BSONObj nullObj = BSON("" << BSONNULL);
-    const BSONElement nullElt = nullObj.firstElement();
-    const BSONObj undefinedObj = BSON("" << BSONUndefined);
-    const BSONElement undefinedElt = undefinedObj.firstElement();
+const BSONObj nullObj = BSON("" << BSONNULL);
+const BSONElement nullElt = nullObj.firstElement();
+const BSONObj undefinedObj = BSON("" << BSONUndefined);
+const BSONElement undefinedElt = undefinedObj.firstElement();
 
-} // namespace
+}  // namespace
 
-    BtreeKeyGenerator::BtreeKeyGenerator(std::vector<const char*> fieldNames,
-                                         std::vector<BSONElement> fixed,
-                                         bool isSparse)
-        : _fieldNames(fieldNames), _isSparse(isSparse), _fixed(fixed) {
-
-        BSONObjBuilder nullKeyBuilder;
-        for (size_t i = 0; i < fieldNames.size(); ++i) {
-            nullKeyBuilder.appendNull("");
-        }
-        _nullKey = nullKeyBuilder.obj();
-
-        _isIdIndex = fieldNames.size() == 1 && std::string("_id") == fieldNames[0];
+BtreeKeyGenerator::BtreeKeyGenerator(std::vector<const char*> fieldNames,
+                                     std::vector<BSONElement> fixed,
+                                     bool isSparse)
+    : _fieldNames(fieldNames), _isSparse(isSparse), _fixed(fixed) {
+    BSONObjBuilder nullKeyBuilder;
+    for (size_t i = 0; i < fieldNames.size(); ++i) {
+        nullKeyBuilder.appendNull("");
     }
+    _nullKey = nullKeyBuilder.obj();
 
-    void BtreeKeyGenerator::getKeys(const BSONObj &obj, BSONObjSet *keys) const {
-        if (_isIdIndex) {
-            // we special case for speed
-            BSONElement e = obj["_id"];
-            if ( e.eoo() ) {
-                keys->insert(_nullKey);
-            }
-            else {
-                int size = e.size() + 5 /* bson over head*/ - 3 /* remove _id string */;
-                BSONObjBuilder b(size);
-                b.appendAs(e, "");
-                keys->insert(b.obj());
-                invariant(keys->begin()->objsize() == size);
-            }
-            return;
-        }
+    _isIdIndex = fieldNames.size() == 1 && std::string("_id") == fieldNames[0];
+}
 
-        // '_fieldNames' and '_fixed' are passed by value so that they can be mutated as part of the
-        // getKeys call.  :|
-        getKeysImpl(_fieldNames, _fixed, obj, keys);
-        if (keys->empty() && ! _isSparse) {
+void BtreeKeyGenerator::getKeys(const BSONObj& obj, BSONObjSet* keys) const {
+    if (_isIdIndex) {
+        // we special case for speed
+        BSONElement e = obj["_id"];
+        if (e.eoo()) {
             keys->insert(_nullKey);
+        } else {
+            int size = e.size() + 5 /* bson over head*/ - 3 /* remove _id string */;
+            BSONObjBuilder b(size);
+            b.appendAs(e, "");
+            keys->insert(b.obj());
+            invariant(keys->begin()->objsize() == size);
         }
+        return;
     }
 
-    static void assertParallelArrays( const char *first, const char *second ) {
-        std::stringstream ss;
-        ss << "cannot index parallel arrays [" << first << "] [" << second << "]";
-        uasserted( BtreeKeyGenerator::ParallelArraysCode ,  ss.str() );
+    // '_fieldNames' and '_fixed' are passed by value so that they can be mutated as part of the
+    // getKeys call.  :|
+    getKeysImpl(_fieldNames, _fixed, obj, keys);
+    if (keys->empty() && !_isSparse) {
+        keys->insert(_nullKey);
     }
+}
 
-    BtreeKeyGeneratorV0::BtreeKeyGeneratorV0(std::vector<const char*> fieldNames,
-                                             std::vector<BSONElement> fixed,
-                                             bool isSparse)
-            : BtreeKeyGenerator(fieldNames, fixed, isSparse) { }
-
-    void BtreeKeyGeneratorV0::getKeysImpl(std::vector<const char*> fieldNames,
-                                          std::vector<BSONElement> fixed,
-                                          const BSONObj &obj,
-                                          BSONObjSet *keys) const {
-        BSONElement arrElt;
-        unsigned arrIdx = ~0;
-        unsigned numNotFound = 0;
-
-        for ( unsigned i = 0; i < fieldNames.size(); ++i ) {
-            if ( *fieldNames[ i ] == '\0' )
-                continue;
+static void assertParallelArrays(const char* first, const char* second) {
+    std::stringstream ss;
+    ss << "cannot index parallel arrays [" << first << "] [" << second << "]";
+    uasserted(BtreeKeyGenerator::ParallelArraysCode, ss.str());
+}
 
-            BSONElement e = obj.getFieldDottedOrArray( fieldNames[ i ] );
+BtreeKeyGeneratorV0::BtreeKeyGeneratorV0(std::vector<const char*> fieldNames,
+                                         std::vector<BSONElement> fixed,
+                                         bool isSparse)
+    : BtreeKeyGenerator(fieldNames, fixed, isSparse) {}
 
-            if ( e.eoo() ) {
-                e = nullElt; // no matching field
-                numNotFound++;
-            }
+void BtreeKeyGeneratorV0::getKeysImpl(std::vector<const char*> fieldNames,
+                                      std::vector<BSONElement> fixed,
+                                      const BSONObj& obj,
+                                      BSONObjSet* keys) const {
+    BSONElement arrElt;
+    unsigned arrIdx = ~0;
+    unsigned numNotFound = 0;
 
-            if ( e.type() != Array )
-                fieldNames[ i ] = ""; // no matching field or non-array match
+    for (unsigned i = 0; i < fieldNames.size(); ++i) {
+        if (*fieldNames[i] == '\0')
+            continue;
 
-            if ( *fieldNames[ i ] == '\0' )
-                // no need for further object expansion (though array expansion still possible)
-                fixed[ i ] = e;
+        BSONElement e = obj.getFieldDottedOrArray(fieldNames[i]);
 
-            if ( e.type() == Array && arrElt.eoo() ) {
-                // we only expand arrays on a single path -- track the path here
-                arrIdx = i;
-                arrElt = e;
-            }
+        if (e.eoo()) {
+            e = nullElt;  // no matching field
+            numNotFound++;
+        }
 
-            // enforce single array path here
-            if ( e.type() == Array && e.rawdata() != arrElt.rawdata() ) {
-                assertParallelArrays( e.fieldName(), arrElt.fieldName() );
-            }
+        if (e.type() != Array)
+            fieldNames[i] = "";  // no matching field or non-array match
+
+        if (*fieldNames[i] == '\0')
+            // no need for further object expansion (though array expansion still possible)
+            fixed[i] = e;
+
+        if (e.type() == Array && arrElt.eoo()) {
+            // we only expand arrays on a single path -- track the path here
+            arrIdx = i;
+            arrElt = e;
         }
 
-        bool allFound = true; // have we found elements for all field names in the key spec?
-        for (std::vector<const char*>::const_iterator i = fieldNames.begin(); i != fieldNames.end();
-             ++i ) {
-            if ( **i != '\0' ) {
-                allFound = false;
-                break;
-            }
+        // enforce single array path here
+        if (e.type() == Array && e.rawdata() != arrElt.rawdata()) {
+            assertParallelArrays(e.fieldName(), arrElt.fieldName());
         }
+    }
 
-        if ( _isSparse && numNotFound == _fieldNames.size()) {
-            // we didn't find any fields
-            // so we're not going to index this document
-            return;
+    bool allFound = true;  // have we found elements for all field names in the key spec?
+    for (std::vector<const char*>::const_iterator i = fieldNames.begin(); i != fieldNames.end();
+         ++i) {
+        if (**i != '\0') {
+            allFound = false;
+            break;
         }
+    }
 
-        bool insertArrayNull = false;
+    if (_isSparse && numNotFound == _fieldNames.size()) {
+        // we didn't find any fields
+        // so we're not going to index this document
+        return;
+    }
 
-        if ( allFound ) {
-            if ( arrElt.eoo() ) {
-                // no terminal array element to expand
-                BSONObjBuilder b(_sizeTracker);
-                for (std::vector< BSONElement >::iterator i = fixed.begin(); i != fixed.end(); ++i)
-                    b.appendAs( *i, "" );
-                keys->insert( b.obj() );
-            }
-            else {
-                // terminal array element to expand, so generate all keys
-                BSONObjIterator i( arrElt.embeddedObject() );
-                if ( i.more() ) {
-                    while (i.more()) {
-                        BSONObjBuilder b(_sizeTracker);
-                        for (unsigned j = 0; j < fixed.size(); ++j) {
-                            if ( j == arrIdx )
-                                b.appendAs( i.next(), "" );
-                            else
-                                b.appendAs( fixed[ j ], "" );
-                        }
-                        keys->insert( b.obj() );
-                    }
-                }
-                else if ( fixed.size() > 1 ) {
-                    insertArrayNull = true;
-                }
-            }
-        }
-        else {
-            // nonterminal array element to expand, so recurse
-            verify( !arrElt.eoo() );
-            BSONObjIterator i( arrElt.embeddedObject() );
-            if ( i.more() ) {
+    bool insertArrayNull = false;
+
+    if (allFound) {
+        if (arrElt.eoo()) {
+            // no terminal array element to expand
+            BSONObjBuilder b(_sizeTracker);
+            for (std::vector<BSONElement>::iterator i = fixed.begin(); i != fixed.end(); ++i)
+                b.appendAs(*i, "");
+            keys->insert(b.obj());
+        } else {
+            // terminal array element to expand, so generate all keys
+            BSONObjIterator i(arrElt.embeddedObject());
+            if (i.more()) {
                 while (i.more()) {
-                    BSONElement e = i.next();
-                    if ( e.type() == Object ) {
-                        getKeysImpl( fieldNames, fixed, e.embeddedObject(), keys );
+                    BSONObjBuilder b(_sizeTracker);
+                    for (unsigned j = 0; j < fixed.size(); ++j) {
+                        if (j == arrIdx)
+                            b.appendAs(i.next(), "");
+                        else
+                            b.appendAs(fixed[j], "");
                     }
+                    keys->insert(b.obj());
                 }
-            }
-            else {
+            } else if (fixed.size() > 1) {
                 insertArrayNull = true;
             }
         }
-
-        if ( insertArrayNull ) {
-            // x : [] - need to insert undefined
-            BSONObjBuilder b(_sizeTracker);
-            for (unsigned j = 0; j < fixed.size(); ++j) {
-                if ( j == arrIdx ) {
-                    b.appendUndefined( "" );
-                }
-                else {
-                    BSONElement e = fixed[j];
-                    if ( e.eoo() )
-                        b.appendNull( "" );
-                    else
-                        b.appendAs( e , "" );
+    } else {
+        // nonterminal array element to expand, so recurse
+        verify(!arrElt.eoo());
+        BSONObjIterator i(arrElt.embeddedObject());
+        if (i.more()) {
+            while (i.more()) {
+                BSONElement e = i.next();
+                if (e.type() == Object) {
+                    getKeysImpl(fieldNames, fixed, e.embeddedObject(), keys);
                 }
             }
-            keys->insert( b.obj() );
+        } else {
+            insertArrayNull = true;
         }
     }
 
-    BtreeKeyGeneratorV1::BtreeKeyGeneratorV1(std::vector<const char*> fieldNames,
-                                             std::vector<BSONElement> fixed,
-                                             bool isSparse)
-        : BtreeKeyGenerator(fieldNames, fixed, isSparse),
-          _emptyPositionalInfo(fieldNames.size()) {
-    }
-
-    BSONElement BtreeKeyGeneratorV1::extractNextElement(const BSONObj &obj,
-                                                        const PositionalPathInfo& positionalInfo,
-                                                        const char** field,
-                                                        bool* arrayNestedArray) const {
-        std::string firstField = mongoutils::str::before(*field, '.');
-        bool haveObjField = !obj.getField(firstField).eoo();
-        BSONElement arrField = positionalInfo.positionallyIndexedElt;
-
-        // An index component field name cannot exist in both a document
-        // array and one of that array's children.
-        uassert(16746,
-                mongoutils::str::stream() <<
-                "Ambiguous field name found in array (do not use numeric field names in "
-                "embedded elements in an array), field: '" << arrField.fieldName() <<
-                "' for array: " << positionalInfo.arrayObj,
-                !haveObjField || !positionalInfo.hasPositionallyIndexedElt());
-
-        *arrayNestedArray = false;
-        if ( haveObjField ) {
-            return obj.getFieldDottedOrArray(*field);
-        }
-        else if (positionalInfo.hasPositionallyIndexedElt()) {
-            if ( arrField.type() == Array ) {
-                *arrayNestedArray = true;
+    if (insertArrayNull) {
+        // x : [] - need to insert undefined
+        BSONObjBuilder b(_sizeTracker);
+        for (unsigned j = 0; j < fixed.size(); ++j) {
+            if (j == arrIdx) {
+                b.appendUndefined("");
+            } else {
+                BSONElement e = fixed[j];
+                if (e.eoo())
+                    b.appendNull("");
+                else
+                    b.appendAs(e, "");
             }
-            *field = positionalInfo.remainingPath;
-            return positionalInfo.dottedElt;
         }
-        return BSONElement();
+        keys->insert(b.obj());
     }
+}
 
-    void BtreeKeyGeneratorV1::_getKeysArrEltFixed(
-            std::vector<const char*>* fieldNames,
-            std::vector<BSONElement>* fixed,
-            const BSONElement& arrEntry,
-            BSONObjSet* keys,
-            unsigned numNotFound,
-            const BSONElement& arrObjElt,
-            const std::set<unsigned>& arrIdxs,
-            bool mayExpandArrayUnembedded,
-            const std::vector<PositionalPathInfo>& positionalInfo) const {
-        // Set up any terminal array values.
-        for (std::set<unsigned>::const_iterator j = arrIdxs.begin(); j != arrIdxs.end(); ++j) {
-            unsigned idx = *j;
-            if (*(*fieldNames)[idx] == '\0') {
-                (*fixed)[idx] = mayExpandArrayUnembedded ? arrEntry : arrObjElt;
-            }
+BtreeKeyGeneratorV1::BtreeKeyGeneratorV1(std::vector<const char*> fieldNames,
+                                         std::vector<BSONElement> fixed,
+                                         bool isSparse)
+    : BtreeKeyGenerator(fieldNames, fixed, isSparse), _emptyPositionalInfo(fieldNames.size()) {}
+
+BSONElement BtreeKeyGeneratorV1::extractNextElement(const BSONObj& obj,
+                                                    const PositionalPathInfo& positionalInfo,
+                                                    const char** field,
+                                                    bool* arrayNestedArray) const {
+    std::string firstField = mongoutils::str::before(*field, '.');
+    bool haveObjField = !obj.getField(firstField).eoo();
+    BSONElement arrField = positionalInfo.positionallyIndexedElt;
+
+    // An index component field name cannot exist in both a document
+    // array and one of that array's children.
+    uassert(16746,
+            mongoutils::str::stream()
+                << "Ambiguous field name found in array (do not use numeric field names in "
+                   "embedded elements in an array), field: '" << arrField.fieldName()
+                << "' for array: " << positionalInfo.arrayObj,
+            !haveObjField || !positionalInfo.hasPositionallyIndexedElt());
+
+    *arrayNestedArray = false;
+    if (haveObjField) {
+        return obj.getFieldDottedOrArray(*field);
+    } else if (positionalInfo.hasPositionallyIndexedElt()) {
+        if (arrField.type() == Array) {
+            *arrayNestedArray = true;
         }
-
-        // Recurse.
-        getKeysImplWithArray(*fieldNames,
-                             *fixed,
-                             arrEntry.type() == Object ? arrEntry.embeddedObject() : BSONObj(),
-                             keys,
-                             numNotFound,
-                             positionalInfo);
+        *field = positionalInfo.remainingPath;
+        return positionalInfo.dottedElt;
     }
-
-    void BtreeKeyGeneratorV1::getKeysImpl(std::vector<const char*> fieldNames,
-                                          std::vector<BSONElement> fixed,
-                                          const BSONObj& obj,
-                                          BSONObjSet* keys) const {
-        getKeysImplWithArray(fieldNames, fixed, obj, keys, 0, _emptyPositionalInfo);
+    return BSONElement();
+}
+
+void BtreeKeyGeneratorV1::_getKeysArrEltFixed(
+    std::vector<const char*>* fieldNames,
+    std::vector<BSONElement>* fixed,
+    const BSONElement& arrEntry,
+    BSONObjSet* keys,
+    unsigned numNotFound,
+    const BSONElement& arrObjElt,
+    const std::set<unsigned>& arrIdxs,
+    bool mayExpandArrayUnembedded,
+    const std::vector<PositionalPathInfo>& positionalInfo) const {
+    // Set up any terminal array values.
+    for (std::set<unsigned>::const_iterator j = arrIdxs.begin(); j != arrIdxs.end(); ++j) {
+        unsigned idx = *j;
+        if (*(*fieldNames)[idx] == '\0') {
+            (*fixed)[idx] = mayExpandArrayUnembedded ? arrEntry : arrObjElt;
+        }
     }
 
-    void BtreeKeyGeneratorV1::getKeysImplWithArray(
-            std::vector<const char*> fieldNames,
-            std::vector<BSONElement> fixed,
-            const BSONObj& obj,
-            BSONObjSet* keys,
-            unsigned numNotFound,
-            const std::vector<PositionalPathInfo>& positionalInfo) const {
-        BSONElement arrElt;
-        std::set<unsigned> arrIdxs;
-        bool mayExpandArrayUnembedded = true;
-        for (unsigned i = 0; i < fieldNames.size(); ++i) {
-            if ( *fieldNames[ i ] == '\0' ) {
-                continue;
-            }
+    // Recurse.
+    getKeysImplWithArray(*fieldNames,
+                         *fixed,
+                         arrEntry.type() == Object ? arrEntry.embeddedObject() : BSONObj(),
+                         keys,
+                         numNotFound,
+                         positionalInfo);
+}
+
+void BtreeKeyGeneratorV1::getKeysImpl(std::vector<const char*> fieldNames,
+                                      std::vector<BSONElement> fixed,
+                                      const BSONObj& obj,
+                                      BSONObjSet* keys) const {
+    getKeysImplWithArray(fieldNames, fixed, obj, keys, 0, _emptyPositionalInfo);
+}
+
+void BtreeKeyGeneratorV1::getKeysImplWithArray(
+    std::vector<const char*> fieldNames,
+    std::vector<BSONElement> fixed,
+    const BSONObj& obj,
+    BSONObjSet* keys,
+    unsigned numNotFound,
+    const std::vector<PositionalPathInfo>& positionalInfo) const {
+    BSONElement arrElt;
+    std::set<unsigned> arrIdxs;
+    bool mayExpandArrayUnembedded = true;
+    for (unsigned i = 0; i < fieldNames.size(); ++i) {
+        if (*fieldNames[i] == '\0') {
+            continue;
+        }
 
-            bool arrayNestedArray;
-            // Extract element matching fieldName[ i ] from object xor array.
-            BSONElement e = extractNextElement(obj,
-                                               positionalInfo[i],
-                                               &fieldNames[i],
-                                               &arrayNestedArray);
-
-            if ( e.eoo() ) {
-                // if field not present, set to null
-                fixed[ i ] = nullElt;
-                // done expanding this field name
-                fieldNames[ i ] = "";
-                numNotFound++;
-            }
-            else if ( e.type() == Array ) {
-                arrIdxs.insert( i );
-                if ( arrElt.eoo() ) {
-                    // we only expand arrays on a single path -- track the path here
-                    arrElt = e;
-                }
-                else if ( e.rawdata() != arrElt.rawdata() ) {
-                    // enforce single array path here
-                    assertParallelArrays( e.fieldName(), arrElt.fieldName() );
-                }
-                if ( arrayNestedArray ) {
-                    mayExpandArrayUnembedded = false;
-                }
+        bool arrayNestedArray;
+        // Extract element matching fieldName[ i ] from object xor array.
+        BSONElement e =
+            extractNextElement(obj, positionalInfo[i], &fieldNames[i], &arrayNestedArray);
+
+        if (e.eoo()) {
+            // if field not present, set to null
+            fixed[i] = nullElt;
+            // done expanding this field name
+            fieldNames[i] = "";
+            numNotFound++;
+        } else if (e.type() == Array) {
+            arrIdxs.insert(i);
+            if (arrElt.eoo()) {
+                // we only expand arrays on a single path -- track the path here
+                arrElt = e;
+            } else if (e.rawdata() != arrElt.rawdata()) {
+                // enforce single array path here
+                assertParallelArrays(e.fieldName(), arrElt.fieldName());
             }
-            else {
-                // not an array - no need for further expansion
-                fixed[ i ] = e;
+            if (arrayNestedArray) {
+                mayExpandArrayUnembedded = false;
             }
+        } else {
+            // not an array - no need for further expansion
+            fixed[i] = e;
         }
+    }
 
-        if ( arrElt.eoo() ) {
-            // No array, so generate a single key.
-            if ( _isSparse && numNotFound == fieldNames.size()) {
-                return;
-            }
-            BSONObjBuilder b(_sizeTracker);
-            for (std::vector< BSONElement >::iterator i = fixed.begin(); i != fixed.end(); ++i) {
-                b.appendAs( *i, "" );
-            }
-            keys->insert( b.obj() );
+    if (arrElt.eoo()) {
+        // No array, so generate a single key.
+        if (_isSparse && numNotFound == fieldNames.size()) {
+            return;
         }
-        else if ( arrElt.embeddedObject().firstElement().eoo() ) {
-            // Empty array, so set matching fields to undefined.
-            _getKeysArrEltFixed(&fieldNames, &fixed, undefinedElt, keys, numNotFound, arrElt,
-                                arrIdxs, true, _emptyPositionalInfo);
+        BSONObjBuilder b(_sizeTracker);
+        for (std::vector<BSONElement>::iterator i = fixed.begin(); i != fixed.end(); ++i) {
+            b.appendAs(*i, "");
         }
-        else {
-            BSONObj arrObj = arrElt.embeddedObject();
-
-            // For positional key patterns, e.g. {'a.1.b': 1}, we lookup the indexed array element
-            // and then traverse the remainder of the field path up front. This prevents us from
-            // having to look up the indexed element again on each recursive call (i.e. once per
-            // array element).
-            std::vector<PositionalPathInfo> subPositionalInfo(fixed.size());
-            for (size_t i = 0; i < fieldNames.size(); ++i) {
-                if (*fieldNames[i] == '\0') {
-                    // We've reached the end of the path.
-                    continue;
-                }
-
-                StringData part = fieldNames[i];
-                part = part.substr(0, part.find('.'));
-                subPositionalInfo[i].positionallyIndexedElt = arrObj[part];
-                if (subPositionalInfo[i].positionallyIndexedElt.eoo()) {
-                    // Not indexing an array by position.
-                    continue;
-                }
-
-                // We're indexing an array element by its position. Traverse the remainder of the
-                // field path now.
-                subPositionalInfo[i].arrayObj = arrObj;
-                subPositionalInfo[i].remainingPath = fieldNames[i];
-                subPositionalInfo[i].dottedElt =
-                    arrObj.getFieldDottedOrArray(subPositionalInfo[i].remainingPath);
+        keys->insert(b.obj());
+    } else if (arrElt.embeddedObject().firstElement().eoo()) {
+        // Empty array, so set matching fields to undefined.
+        _getKeysArrEltFixed(&fieldNames,
+                            &fixed,
+                            undefinedElt,
+                            keys,
+                            numNotFound,
+                            arrElt,
+                            arrIdxs,
+                            true,
+                            _emptyPositionalInfo);
+    } else {
+        BSONObj arrObj = arrElt.embeddedObject();
+
+        // For positional key patterns, e.g. {'a.1.b': 1}, we lookup the indexed array element
+        // and then traverse the remainder of the field path up front. This prevents us from
+        // having to look up the indexed element again on each recursive call (i.e. once per
+        // array element).
+        std::vector<PositionalPathInfo> subPositionalInfo(fixed.size());
+        for (size_t i = 0; i < fieldNames.size(); ++i) {
+            if (*fieldNames[i] == '\0') {
+                // We've reached the end of the path.
+                continue;
             }
 
-            // Generate a key for each element of the indexed array.
-            BSONObjIterator i(arrObj);
-            while (i.more()) {
-                _getKeysArrEltFixed(&fieldNames, &fixed, i.next(), keys, numNotFound, arrElt,
-                                    arrIdxs, mayExpandArrayUnembedded, subPositionalInfo);
+            StringData part = fieldNames[i];
+            part = part.substr(0, part.find('.'));
+            subPositionalInfo[i].positionallyIndexedElt = arrObj[part];
+            if (subPositionalInfo[i].positionallyIndexedElt.eoo()) {
+                // Not indexing an array by position.
+                continue;
             }
+
+            // We're indexing an array element by its position. Traverse the remainder of the
+            // field path now.
+            subPositionalInfo[i].arrayObj = arrObj;
+            subPositionalInfo[i].remainingPath = fieldNames[i];
+            subPositionalInfo[i].dottedElt =
+                arrObj.getFieldDottedOrArray(subPositionalInfo[i].remainingPath);
+        }
+
+        // Generate a key for each element of the indexed array.
+        BSONObjIterator i(arrObj);
+        while (i.more()) {
+            _getKeysArrEltFixed(&fieldNames,
+                                &fixed,
+                                i.next(),
+                                keys,
+                                numNotFound,
+                                arrElt,
+                                arrIdxs,
+                                mayExpandArrayUnembedded,
+                                subPositionalInfo);
         }
     }
+}
 }  // namespace mongo
diff --git a/src/mongo/db/index/btree_key_generator.h b/src/mongo/db/index/btree_key_generator.h
index fe376d7f32b..cb156354b51 100644
--- a/src/mongo/db/index/btree_key_generator.h
+++ b/src/mongo/db/index/btree_key_generator.h
@@ -34,192 +34,194 @@
 
 namespace mongo {
 
+/**
+ * Internal class used by BtreeAccessMethod to generate keys for indexed documents.
+ * This class is meant to be kept under the index access layer.
+ */
+class BtreeKeyGenerator {
+public:
+    BtreeKeyGenerator(std::vector<const char*> fieldNames,
+                      std::vector<BSONElement> fixed,
+                      bool isSparse);
+
+    virtual ~BtreeKeyGenerator() {}
+
+    void getKeys(const BSONObj& obj, BSONObjSet* keys) const;
+
+    static const int ParallelArraysCode;
+
+protected:
+    // These are used by the getKeysImpl(s) below.
+    std::vector<const char*> _fieldNames;
+    bool _isIdIndex;
+    bool _isSparse;
+    BSONObj _nullKey;  // a full key with all fields null
+    BSONSizeTracker _sizeTracker;
+
+private:
+    // We have V0 and V1.  Sigh.
+    virtual void getKeysImpl(std::vector<const char*> fieldNames,
+                             std::vector<BSONElement> fixed,
+                             const BSONObj& obj,
+                             BSONObjSet* keys) const = 0;
+
+    std::vector<BSONElement> _fixed;
+};
+
+class BtreeKeyGeneratorV0 : public BtreeKeyGenerator {
+public:
+    BtreeKeyGeneratorV0(std::vector<const char*> fieldNames,
+                        std::vector<BSONElement> fixed,
+                        bool isSparse);
+
+    virtual ~BtreeKeyGeneratorV0() {}
+
+private:
+    virtual void getKeysImpl(std::vector<const char*> fieldNames,
+                             std::vector<BSONElement> fixed,
+                             const BSONObj& obj,
+                             BSONObjSet* keys) const;
+};
+
+class BtreeKeyGeneratorV1 : public BtreeKeyGenerator {
+public:
+    BtreeKeyGeneratorV1(std::vector<const char*> fieldNames,
+                        std::vector<BSONElement> fixed,
+                        bool isSparse);
+
+    virtual ~BtreeKeyGeneratorV1() {}
+
+private:
     /**
-     * Internal class used by BtreeAccessMethod to generate keys for indexed documents.
-     * This class is meant to be kept under the index access layer.
+     * Stores info regarding traversal of a positional path. A path through a document is
+     * considered positional if this path element names an array element. Generally this means
+     * that the field name consists of [0-9]+, but the implementation just calls .Obj() on
+     * the array and looks for the named field. This logic happens even if the field does
+     * not match [0-9]+.
+     *
+     * Example:
+     *   The path 'a.1.b' can sometimes be positional due to path element '1'. In the document
+     *   {a: [{b: 98}, {b: 99}]} it would be considered positional, and would refer to
+     *   element 99. In the document {a: [{'1': {b: 97}}]}, the path is *not* considered
+     *   positional and would refer to element 97.
      */
-    class BtreeKeyGenerator {
-    public:
-        BtreeKeyGenerator(std::vector<const char*> fieldNames,
-                          std::vector<BSONElement> fixed,
-                          bool isSparse);
-
-        virtual ~BtreeKeyGenerator() { }
-
-        void getKeys(const BSONObj& obj, BSONObjSet* keys) const;
-
-        static const int ParallelArraysCode;
-
-    protected:
-        // These are used by the getKeysImpl(s) below.
-        std::vector<const char*> _fieldNames;
-        bool _isIdIndex;
-        bool _isSparse;
-        BSONObj _nullKey; // a full key with all fields null
-        BSONSizeTracker _sizeTracker;
-
-    private:
-        // We have V0 and V1.  Sigh.
-        virtual void getKeysImpl(std::vector<const char*> fieldNames,
-                                 std::vector<BSONElement> fixed,
-                                 const BSONObj& obj,
-                                 BSONObjSet* keys) const = 0;
-
-        std::vector<BSONElement> _fixed;
+    struct PositionalPathInfo {
+        PositionalPathInfo() : remainingPath("") {}
+
+        bool hasPositionallyIndexedElt() const {
+            return !positionallyIndexedElt.eoo();
+        }
+
+        // Stores the array element indexed by position. If the key pattern has no positional
+        // element, then this is EOO.
+        //
+        // Example:
+        //   Suppose the key pattern is {"a.0.x": 1} and we're extracting keys for document
+        //   {a: [{x: 98}, {x: 99}]}. We should store element {x: 98} here.
+        BSONElement positionallyIndexedElt;
+
+        // The array to which 'positionallyIndexedElt' belongs.
+        BSONObj arrayObj;
+
+        // If we find a positionally indexed element, we traverse the remainder of the path
+        // until we find either another array element or the end of the path. The result of
+        // this traversal (implemented using getFieldDottedOrArray()), is stored here and used
+        // during the recursive call for each array element.
+        //
+        // Example:
+        //   Suppose we have key pattern {"a.1.b.0.c": 1}. The document for which we are
+        //   generating keys is {a: [0, {b: [{c: 99}]}]}. We will find that {b: [{c: 99}]}
+        //   is a positionally indexed element and store it as 'positionallyIndexedElt'.
+        //
+        //   We then call getFieldDottedOrArray() to traverse the remainder of the path,
+        //   "b.1.c". The result is the array [{c: 99}] which is stored here as 'dottedElt'.
+        BSONElement dottedElt;
+
+        // The remaining path that must be traversed in 'dottedElt' to find the indexed
+        // element(s).
+        //
+        // Example:
+        //   Continuing the example above, 'remainingPath' will be "0.c". Note that the path
+        //   "0.c" refers to element 99 in 'dottedElt', [{c: 99}].
+        const char* remainingPath;
     };
 
-    class BtreeKeyGeneratorV0 : public BtreeKeyGenerator {
-    public:
-        BtreeKeyGeneratorV0(std::vector<const char*> fieldNames,
-                            std::vector<BSONElement> fixed,
-                            bool isSparse);
-
-        virtual ~BtreeKeyGeneratorV0() { }
+    /**
+     * @param fieldNames - fields to index, may be postfixes in recursive calls
+     * @param fixed - values that have already been identified for their index fields
+     * @param obj - object from which keys should be extracted, based on names in fieldNames
+     * @param keys - set where index keys are written
+     * @param numNotFound - number of index fields that have already been identified as missing
+     * @param array - array from which keys should be extracted, based on names in fieldNames
+     *        If obj and array are both nonempty, obj will be one of the elements of array.
+     */
+    virtual void getKeysImpl(std::vector<const char*> fieldNames,
+                             std::vector<BSONElement> fixed,
+                             const BSONObj& obj,
+                             BSONObjSet* keys) const;
 
-    private:
-        virtual void getKeysImpl(std::vector<const char*> fieldNames,
-                                 std::vector<BSONElement> fixed,
-                                 const BSONObj& obj,
-                                 BSONObjSet* keys) const;
-    };
+    /**
+     * This recursive method does the heavy-lifting for getKeysImpl().
+     */
+    void getKeysImplWithArray(std::vector<const char*> fieldNames,
+                              std::vector<BSONElement> fixed,
+                              const BSONObj& obj,
+                              BSONObjSet* keys,
+                              unsigned numNotFound,
+                              const std::vector<PositionalPathInfo>& positionalInfo) const;
+    /**
+     * A call to getKeysImplWithArray() begins by calling this for each field in the key
+     * pattern. It uses getFieldDottedOrArray() to traverse the path '*field' in 'obj'.
+     *
+     * The 'positionalInfo' arg is used for handling a field path where 'obj' has an
+     * array indexed by position. See the comments for PositionalPathInfo for more detail.
+     *
+     * Returns the element extracted as a result of traversing the path, or an indexed array
+     * if we encounter one during the path traversal.
+     *
+     * Out-parameters:
+     *   --Sets *field to the remaining path that must be traversed.
+     *   --Sets *arrayNestedArray to true if the returned BSONElement is a nested array that is
+     *     indexed by position in its parent array. Otherwise sets *arrayNestedArray to false.
+     *
+     * Example:
+     *   Suppose we have key pattern {"a.b.c": 1} and we're extracting keys from document
+     *   {a: [{b: {c: 98}}, {b: {c: 99}}]}. On the first call to extractNextElement(), 'obj'
+     *   will be the full document, {a: [{b: {c: 98}}, {b: {c: 99}}]}. The 'positionalInfo'
+     *   argument is not relevant, because the array is not being positionally indexed.
+     *   '*field' will point to "a.b.c".
+     *
+     *   The return value will be the array element [{b: {c: 98}}, {b: {c: 99}}], because path
+     *   traversal stops when an indexed array is encountered. Furthermore, '*field' will be set
+     *   to "b.c".
+     *
+     *   extractNextElement() will then be called from a recursive call to
+     *   getKeysImplWithArray() for each array element. For instance, it will get called with
+     *   'obj' {b: {c: 98}} and '*field' pointing to "b.c". It will return element 98 and
+     *   set '*field' to "". Similarly, it will return elemtn 99 and set '*field' to "" for
+     *   the second array element.
+     */
+    BSONElement extractNextElement(const BSONObj& obj,
+                                   const PositionalPathInfo& positionalInfo,
+                                   const char** field,
+                                   bool* arrayNestedArray) const;
 
-    class BtreeKeyGeneratorV1 : public BtreeKeyGenerator {
-    public:
-        BtreeKeyGeneratorV1(std::vector<const char*> fieldNames,
-                            std::vector<BSONElement> fixed,
-                            bool isSparse);
-
-        virtual ~BtreeKeyGeneratorV1() { }
-
-    private:
-        /**
-         * Stores info regarding traversal of a positional path. A path through a document is
-         * considered positional if this path element names an array element. Generally this means
-         * that the field name consists of [0-9]+, but the implementation just calls .Obj() on
-         * the array and looks for the named field. This logic happens even if the field does
-         * not match [0-9]+.
-         *
-         * Example:
-         *   The path 'a.1.b' can sometimes be positional due to path element '1'. In the document
-         *   {a: [{b: 98}, {b: 99}]} it would be considered positional, and would refer to
-         *   element 99. In the document {a: [{'1': {b: 97}}]}, the path is *not* considered
-         *   positional and would refer to element 97.
-         */
-        struct PositionalPathInfo {
-            PositionalPathInfo() : remainingPath("") {}
-
-            bool hasPositionallyIndexedElt() const { return !positionallyIndexedElt.eoo(); }
-
-            // Stores the array element indexed by position. If the key pattern has no positional
-            // element, then this is EOO.
-            //
-            // Example:
-            //   Suppose the key pattern is {"a.0.x": 1} and we're extracting keys for document
-            //   {a: [{x: 98}, {x: 99}]}. We should store element {x: 98} here.
-            BSONElement positionallyIndexedElt;
-
-            // The array to which 'positionallyIndexedElt' belongs.
-            BSONObj arrayObj;
-
-            // If we find a positionally indexed element, we traverse the remainder of the path
-            // until we find either another array element or the end of the path. The result of
-            // this traversal (implemented using getFieldDottedOrArray()), is stored here and used
-            // during the recursive call for each array element.
-            //
-            // Example:
-            //   Suppose we have key pattern {"a.1.b.0.c": 1}. The document for which we are
-            //   generating keys is {a: [0, {b: [{c: 99}]}]}. We will find that {b: [{c: 99}]}
-            //   is a positionally indexed element and store it as 'positionallyIndexedElt'.
-            //
-            //   We then call getFieldDottedOrArray() to traverse the remainder of the path,
-            //   "b.1.c". The result is the array [{c: 99}] which is stored here as 'dottedElt'.
-            BSONElement dottedElt;
-
-            // The remaining path that must be traversed in 'dottedElt' to find the indexed
-            // element(s).
-            //
-            // Example:
-            //   Continuing the example above, 'remainingPath' will be "0.c". Note that the path
-            //   "0.c" refers to element 99 in 'dottedElt', [{c: 99}].
-            const char* remainingPath;
-        };
-
-        /**
-         * @param fieldNames - fields to index, may be postfixes in recursive calls
-         * @param fixed - values that have already been identified for their index fields
-         * @param obj - object from which keys should be extracted, based on names in fieldNames
-         * @param keys - set where index keys are written
-         * @param numNotFound - number of index fields that have already been identified as missing
-         * @param array - array from which keys should be extracted, based on names in fieldNames
-         *        If obj and array are both nonempty, obj will be one of the elements of array.
-         */
-        virtual void getKeysImpl(std::vector<const char*> fieldNames,
-                                 std::vector<BSONElement> fixed,
-                                 const BSONObj& obj,
-                                 BSONObjSet* keys) const;
-
-        /**
-         * This recursive method does the heavy-lifting for getKeysImpl().
-         */
-        void getKeysImplWithArray(std::vector<const char*> fieldNames,
-                                  std::vector<BSONElement> fixed,
-                                  const BSONObj& obj,
-                                  BSONObjSet* keys,
-                                  unsigned numNotFound,
-                                  const std::vector<PositionalPathInfo>& positionalInfo) const;
-        /**
-         * A call to getKeysImplWithArray() begins by calling this for each field in the key
-         * pattern. It uses getFieldDottedOrArray() to traverse the path '*field' in 'obj'.
-         *
-         * The 'positionalInfo' arg is used for handling a field path where 'obj' has an
-         * array indexed by position. See the comments for PositionalPathInfo for more detail.
-         *
-         * Returns the element extracted as a result of traversing the path, or an indexed array
-         * if we encounter one during the path traversal.
-         *
-         * Out-parameters:
-         *   --Sets *field to the remaining path that must be traversed.
-         *   --Sets *arrayNestedArray to true if the returned BSONElement is a nested array that is
-         *     indexed by position in its parent array. Otherwise sets *arrayNestedArray to false.
-         *
-         * Example:
-         *   Suppose we have key pattern {"a.b.c": 1} and we're extracting keys from document
-         *   {a: [{b: {c: 98}}, {b: {c: 99}}]}. On the first call to extractNextElement(), 'obj'
-         *   will be the full document, {a: [{b: {c: 98}}, {b: {c: 99}}]}. The 'positionalInfo'
-         *   argument is not relevant, because the array is not being positionally indexed.
-         *   '*field' will point to "a.b.c".
-         *
-         *   The return value will be the array element [{b: {c: 98}}, {b: {c: 99}}], because path
-         *   traversal stops when an indexed array is encountered. Furthermore, '*field' will be set
-         *   to "b.c".
-         *
-         *   extractNextElement() will then be called from a recursive call to
-         *   getKeysImplWithArray() for each array element. For instance, it will get called with
-         *   'obj' {b: {c: 98}} and '*field' pointing to "b.c". It will return element 98 and
-         *   set '*field' to "". Similarly, it will return elemtn 99 and set '*field' to "" for
-         *   the second array element.
-         */
-        BSONElement extractNextElement(const BSONObj& obj,
-                                       const PositionalPathInfo& positionalInfo,
-                                       const char** field,
-                                       bool* arrayNestedArray) const;
-
-        /**
-         * Sets extracted elements in 'fixed' for field paths that we have traversed to the end.
-         *
-         * Then calls getKeysImplWithArray() recursively.
-         */
-        void _getKeysArrEltFixed(std::vector<const char*>* fieldNames,
-                                 std::vector<BSONElement>* fixed,
-                                 const BSONElement& arrEntry,
-                                 BSONObjSet* keys,
-                                 unsigned numNotFound,
-                                 const BSONElement& arrObjElt,
-                                 const std::set<unsigned>& arrIdxs,
-                                 bool mayExpandArrayUnembedded,
-                                 const std::vector<PositionalPathInfo>& positionalInfo) const;
-
-        const std::vector<PositionalPathInfo> _emptyPositionalInfo;
-    };
+    /**
+     * Sets extracted elements in 'fixed' for field paths that we have traversed to the end.
+     *
+     * Then calls getKeysImplWithArray() recursively.
+     */
+    void _getKeysArrEltFixed(std::vector<const char*>* fieldNames,
+                             std::vector<BSONElement>* fixed,
+                             const BSONElement& arrEntry,
+                             BSONObjSet* keys,
+                             unsigned numNotFound,
+                             const BSONElement& arrObjElt,
+                             const std::set<unsigned>& arrIdxs,
+                             bool mayExpandArrayUnembedded,
+                             const std::vector<PositionalPathInfo>& positionalInfo) const;
+
+    const std::vector<PositionalPathInfo> _emptyPositionalInfo;
+};
 
 }  // namespace mongo
diff --git a/src/mongo/db/index/btree_key_generator_test.cpp b/src/mongo/db/index/btree_key_generator_test.cpp
index f01f6552f18..23792fb9b87 100644
--- a/src/mongo/db/index/btree_key_generator_test.cpp
+++ b/src/mongo/db/index/btree_key_generator_test.cpp
@@ -41,791 +41,790 @@ using std::vector;
 
 namespace {
 
-    //
-    // Helper functions
-    //
+//
+// Helper functions
+//
 
-    std::string dumpKeyset(const BSONObjSet& objs) {
-        std::stringstream ss;
-        ss << "[ ";
-        for (BSONObjSet::iterator i = objs.begin(); i != objs.end(); ++i) {
-            ss << i->toString() << " ";
-        }
-        ss << "]";
-
-        return ss.str();
+std::string dumpKeyset(const BSONObjSet& objs) {
+    std::stringstream ss;
+    ss << "[ ";
+    for (BSONObjSet::iterator i = objs.begin(); i != objs.end(); ++i) {
+        ss << i->toString() << " ";
     }
+    ss << "]";
 
-    bool keysetsMatch(const BSONObjSet& expected, const BSONObjSet& actual) {
-        if (expected.size() != actual.size()) {
-            return false;
-        }
-
-        for (BSONObjSet::iterator i = expected.begin(); i != expected.end(); ++i) {
-            if (actual.end() == actual.find(*i)) {
-                return false;
-            }
-        }
+    return ss.str();
+}
 
-        return true;
+bool keysetsMatch(const BSONObjSet& expected, const BSONObjSet& actual) {
+    if (expected.size() != actual.size()) {
+        return false;
     }
 
-    bool testKeygen(const BSONObj& kp, const BSONObj& obj,
-                    const BSONObjSet& expectedKeys, bool sparse = false) {
-        //
-        // Step 1: construct the btree key generator object, using the
-        // index key pattern.
-        //
-        vector<const char*> fieldNames;
-        vector<BSONElement> fixed;
-
-        BSONObjIterator it(kp);
-        while (it.more()) {
-            BSONElement elt = it.next();
-            fieldNames.push_back(elt.fieldName());
-            fixed.push_back(BSONElement());
-        }
-
-        unique_ptr<BtreeKeyGenerator> keyGen(
-            new BtreeKeyGeneratorV1(fieldNames, fixed, sparse));
-
-        //
-        // Step 2: ask 'keyGen' to generate index keys for the object 'obj'.
-        //
-        BSONObjSet actualKeys;
-        keyGen->getKeys(obj, &actualKeys);
-
-        //
-        // Step 3: check that the results match the expected result.
-        //
-        bool match = keysetsMatch(expectedKeys, actualKeys);
-        if (!match) {
-            cout << "Expected: " << dumpKeyset(expectedKeys) << ", "
-                 << "Actual: " << dumpKeyset(actualKeys) << endl;
+    for (BSONObjSet::iterator i = expected.begin(); i != expected.end(); ++i) {
+        if (actual.end() == actual.find(*i)) {
+            return false;
         }
-
-        return match;
     }
 
+    return true;
+}
+
+bool testKeygen(const BSONObj& kp,
+                const BSONObj& obj,
+                const BSONObjSet& expectedKeys,
+                bool sparse = false) {
     //
-    // Unit tests
+    // Step 1: construct the btree key generator object, using the
+    // index key pattern.
     //
+    vector<const char*> fieldNames;
+    vector<BSONElement> fixed;
 
-    TEST(BtreeKeyGeneratorTest, GetKeysFromObjectSimple) {
-        BSONObj keyPattern = fromjson("{a: 1}");
-        BSONObj genKeysFrom = fromjson("{b: 4, a: 5}");
-        BSONObjSet expectedKeys;
-        expectedKeys.insert(fromjson("{'': 5}"));
-        ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys));
-    }
-
-    TEST(BtreeKeyGeneratorTest, GetKeysFromObjectDotted) {
-        BSONObj keyPattern = fromjson("{'a.b': 1}");
-        BSONObj genKeysFrom = fromjson("{a: {b: 4}, c: 'foo'}");
-        BSONObjSet expectedKeys;
-        expectedKeys.insert(fromjson("{'': 4}"));
-        ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys));
-    }
-
-    TEST(BtreeKeyGeneratorTest, GetKeysFromArraySimple) {
-        BSONObj keyPattern = fromjson("{a: 1}");
-        BSONObj genKeysFrom = fromjson("{a: [1, 2, 3]}");
-        BSONObjSet expectedKeys;
-        expectedKeys.insert(fromjson("{'': 1}"));
-        expectedKeys.insert(fromjson("{'': 2}"));
-        expectedKeys.insert(fromjson("{'': 3}"));
-        ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys));
-    }
-
-    TEST(BtreeKeyGeneratorTest, GetKeysFromArrayFirstElement) {
-        BSONObj keyPattern = fromjson("{a: 1, b: 1}");
-        BSONObj genKeysFrom = fromjson("{a: [1, 2, 3], b: 2}");
-        BSONObjSet expectedKeys;
-        expectedKeys.insert(fromjson("{'': 1, '': 2}"));
-        expectedKeys.insert(fromjson("{'': 2, '': 2}"));
-        expectedKeys.insert(fromjson("{'': 3, '': 2}"));
-        ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys));
+    BSONObjIterator it(kp);
+    while (it.more()) {
+        BSONElement elt = it.next();
+        fieldNames.push_back(elt.fieldName());
+        fixed.push_back(BSONElement());
     }
 
-    TEST(BtreeKeyGeneratorTest, GetKeysFromArraySecondElement) {
-        BSONObj keyPattern = fromjson("{first: 1, a: 1}");
-        BSONObj genKeysFrom = fromjson("{first: 5, a: [1, 2, 3]}");
-        BSONObjSet expectedKeys;
-        expectedKeys.insert(fromjson("{'': 5, '': 1}"));
-        expectedKeys.insert(fromjson("{'': 5, '': 2}"));
-        expectedKeys.insert(fromjson("{'': 5, '': 3}"));
-        ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys));
-    }
-
-    TEST(BtreeKeyGeneratorTest, GetKeysFromSecondLevelArray) {
-        BSONObj keyPattern = fromjson("{'a.b': 1}");
-        BSONObj genKeysFrom = fromjson("{a: {b: [1, 2, 3]}}");
-        BSONObjSet expectedKeys;
-        expectedKeys.insert(fromjson("{'': 1}"));
-        expectedKeys.insert(fromjson("{'': 2}"));
-        expectedKeys.insert(fromjson("{'': 3}"));
-        ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys));
-    }
-
-    TEST(BtreeKeyGeneratorTest, GetKeysFromParallelArraysBasic) {
-        BSONObj keyPattern = fromjson("{'a': 1, 'b': 1}");
-        BSONObj genKeysFrom = fromjson("{a: [1, 2, 3], b: [1, 2, 3]}}");
-        BSONObjSet expectedKeys;
-        ASSERT_THROWS(testKeygen(keyPattern, genKeysFrom, expectedKeys), UserException);
-    }
-
-    TEST(BtreeKeyGeneratorTest, GetKeysFromArraySubobjectBasic) {
-        BSONObj keyPattern = fromjson("{'a.b': 1}");
-        BSONObj genKeysFrom = fromjson("{a: [{b:1,c:4}, {b:2,c:4}, {b:3,c:4}]}");
-        BSONObjSet expectedKeys;
-        expectedKeys.insert(fromjson("{'': 1}"));
-        expectedKeys.insert(fromjson("{'': 2}"));
-        expectedKeys.insert(fromjson("{'': 3}"));
-        ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys));
-    }
-
-    TEST(BtreeKeyGeneratorTest, GetKeysArraySubobjectCompoundIndex) {
-        BSONObj keyPattern = fromjson("{'a.b': 1, d: 99}");
-        BSONObj genKeysFrom = fromjson("{a: [{b:1,c:4}, {b:2,c:4}, {b:3,c:4}], d: 99}");
-        BSONObjSet expectedKeys;
-        expectedKeys.insert(fromjson("{'': 1, '': 99}"));
-        expectedKeys.insert(fromjson("{'': 2, '': 99}"));
-        expectedKeys.insert(fromjson("{'': 3, '': 99}"));
-        ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys));
-    }
-
-    TEST(BtreeKeyGeneratorTest, GetKeysArraySubobjectSingleMissing) {
-        BSONObj keyPattern = fromjson("{'a.b': 1}");
-        BSONObj genKeysFrom = fromjson("{a: [{foo: 41}, {b:1,c:4}, {b:2,c:4}, {b:3,c:4}]}");
-        BSONObjSet expectedKeys;
-        expectedKeys.insert(fromjson("{'': null}"));
-        expectedKeys.insert(fromjson("{'': 1}"));
-        expectedKeys.insert(fromjson("{'': 2}"));
-        expectedKeys.insert(fromjson("{'': 3}"));
-        ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys));
-    }
-
-    TEST(BtreeKeyGeneratorTest, GetKeysFromArraySubobjectMissing) {
-        BSONObj keyPattern = fromjson("{'a.b': 1}");
-        BSONObj genKeysFrom = fromjson("{a: [{foo: 41}, {foo: 41}, {foo: 41}]}");
-        BSONObjSet expectedKeys;
-        expectedKeys.insert(fromjson("{'': null}"));
-        ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys));
-    }
-
-    TEST(BtreeKeyGeneratorTest, GetKeysMissingField) {
-        BSONObj keyPattern = fromjson("{a: 1}");
-        BSONObj genKeysFrom = fromjson("{b: 1}");
-        BSONObjSet expectedKeys;
-        expectedKeys.insert(fromjson("{'': null}"));
-        ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys));
-    }
-
-    TEST(BtreeKeyGeneratorTest, GetKeysSubobjectMissing) {
-        BSONObj keyPattern = fromjson("{'a.b': 1}");
-        BSONObj genKeysFrom = fromjson("{a: [1, 2]}");
-        BSONObjSet expectedKeys;
-        expectedKeys.insert(fromjson("{'': null}"));
-        ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys));
-    }
-
-    TEST(BtreeKeyGeneratorTest, GetKeysFromCompound) {
-        BSONObj keyPattern = fromjson("{x: 1, y: 1}");
-        BSONObj genKeysFrom = fromjson("{x: 'a', y: 'b'}");
-        BSONObjSet expectedKeys;
-        expectedKeys.insert(fromjson("{'': 'a', '': 'b'}"));
-        ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys));
-    }
+    unique_ptr<BtreeKeyGenerator> keyGen(new BtreeKeyGeneratorV1(fieldNames, fixed, sparse));
 
-    TEST(BtreeKeyGeneratorTest, GetKeysFromCompoundMissing) {
-        BSONObj keyPattern = fromjson("{x: 1, y: 1}");
-        BSONObj genKeysFrom = fromjson("{x: 'a'}");
-        BSONObjSet expectedKeys;
-        expectedKeys.insert(fromjson("{'': 'a', '': null}"));
-        ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys));
-    }
-
-    TEST(BtreeKeyGeneratorTest, GetKeysFromArraySubelementComplex) {
-        BSONObj keyPattern = fromjson("{'a.b': 1}");
-        BSONObj genKeysFrom = fromjson("{a:[{b:[2]}]}");
-        BSONObjSet expectedKeys;
-        expectedKeys.insert(fromjson("{'': 2}"));
-        ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys));
-    }
-
-    TEST(BtreeKeyGeneratorTest, GetKeysFromParallelArraysComplex) {
-        BSONObj keyPattern = fromjson("{'a.b': 1, 'a.c': 1}");
-        BSONObj genKeysFrom = fromjson("{a:[{b:[1],c:[2]}]}");
-        BSONObjSet expectedKeys;
-        ASSERT_THROWS(testKeygen(keyPattern, genKeysFrom, expectedKeys), UserException);
-    }
-
-    TEST(BtreeKeyGeneratorTest, GetKeysAlternateMissing) {
-        BSONObj keyPattern = fromjson("{'a.b': 1, 'a.c': 1}");
-        BSONObj genKeysFrom = fromjson("{a:[{b:1},{c:2}]}");
-        BSONObjSet expectedKeys;
-        expectedKeys.insert(fromjson("{'': null, '': 2}"));
-        expectedKeys.insert(fromjson("{'': 1, '': null}"));
-        ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys));
-    }
-
-    TEST(BtreeKeyGeneratorTest, GetKeysFromMultiComplex) {
-        BSONObj keyPattern = fromjson("{'a.b': 1}");
-        BSONObj genKeysFrom = fromjson("{a:[{b:1},{b:[1,2,3]}]}");
-        BSONObjSet expectedKeys;
-        expectedKeys.insert(fromjson("{'': 1}"));
-        expectedKeys.insert(fromjson("{'': 2}"));
-        expectedKeys.insert(fromjson("{'': 3}"));
-        ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys));
-    }
-
-    TEST(BtreeKeyGeneratorTest, GetKeysArrayEmpty) {
-        BSONObj keyPattern = fromjson("{a: 1}");
-        BSONObj genKeysFrom = fromjson("{a:[1,2]}");
-        BSONObjSet expectedKeys;
-        expectedKeys.insert(fromjson("{'': 1}"));
-        expectedKeys.insert(fromjson("{'': 2}"));
-        ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys));
-
-        genKeysFrom = fromjson("{a: [1]}");
-        expectedKeys.clear();
-        expectedKeys.insert(fromjson("{'': 1}"));
-        ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys));
-
-        genKeysFrom = fromjson("{a: null}");
-        expectedKeys.clear();
-        expectedKeys.insert(fromjson("{'': null}"));
-        ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys));
-
-        genKeysFrom = fromjson("{a: []}");
-        expectedKeys.clear();
-        expectedKeys.insert(fromjson("{'': undefined}"));
-        ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys));
-    }
-
-    TEST(BtreeKeyGeneratorTest, GetKeysFromDoubleArray) {
-        BSONObj keyPattern = fromjson("{a: 1, a: 1}");
-        BSONObj genKeysFrom = fromjson("{a:[1,2]}");
-        BSONObjSet expectedKeys;
-        expectedKeys.insert(fromjson("{'': 1, '': 1}"));
-        expectedKeys.insert(fromjson("{'': 2, '': 2}"));
-        ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys));
-    }
-
-    TEST(BtreeKeyGeneratorTest, GetKeysFromDoubleEmptyArray) {
-        BSONObj keyPattern = fromjson("{a: 1, a: 1}");
-        BSONObj genKeysFrom = fromjson("{a:[]}");
-        BSONObjSet expectedKeys;
-        expectedKeys.insert(fromjson("{'': undefined, '': undefined}"));
-        ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys));
-    }
-
-    TEST(BtreeKeyGeneratorTest, GetKeysFromMultiEmptyArray) {
-        BSONObj keyPattern = fromjson("{a: 1, b: 1}");
-        BSONObj genKeysFrom = fromjson("{a: 1, b: [1, 2]}");
-        BSONObjSet expectedKeys;
-        expectedKeys.insert(fromjson("{'': 1, '': 1}"));
-        expectedKeys.insert(fromjson("{'': 1, '': 2}"));
-        ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys));
-
-        genKeysFrom = fromjson("{a: 1, b: [1]}");
-        expectedKeys.clear();
-        expectedKeys.insert(fromjson("{'': 1, '': 1}"));
-        ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys));
-
-        genKeysFrom = fromjson("{a: 1, b: []}");
-        expectedKeys.clear();
-        expectedKeys.insert(fromjson("{'': 1, '': undefined}"));
-        ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys));
-    }
-
-    TEST(BtreeKeyGeneratorTest, GetKeysFromNestedEmptyArray) {
-        BSONObj keyPattern = fromjson("{'a.b': 1}");
-        BSONObj genKeysFrom = fromjson("{a:[]}");
-        BSONObjSet expectedKeys;
-        expectedKeys.insert(fromjson("{'': null}"));
-        ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys));
-    }
-
-    TEST(BtreeKeyGeneratorTest, GetKeysFromMultiNestedEmptyArray) {
-        BSONObj keyPattern = fromjson("{'a.b': 1, 'a.c': 1}");
-        BSONObj genKeysFrom = fromjson("{a:[]}");
-        BSONObjSet expectedKeys;
-        expectedKeys.insert(fromjson("{'': null, '': null}"));
-        ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys));
-    }
-
-    TEST(BtreeKeyGeneratorTest, GetKeysFromUnevenNestedEmptyArray) {
-        BSONObj keyPattern = fromjson("{'a': 1, 'a.b': 1}");
-        BSONObj genKeysFrom = fromjson("{a:[]}");
-        BSONObjSet expectedKeys;
-        expectedKeys.insert(fromjson("{'': undefined, '': null}"));
-        ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys));
-
-        genKeysFrom = fromjson("{a:[{b: 1}]}");
-        expectedKeys.clear();
-        expectedKeys.insert(fromjson("{'': {b:1}, '': 1}"));
-        ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys));
-
-        genKeysFrom = fromjson("{a:[{b: []}]}");
-        expectedKeys.clear();
-        expectedKeys.insert(fromjson("{'': {b:[]}, '': undefined}"));
-        ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys));
-    }
-
-    TEST(BtreeKeyGeneratorTest, GetKeysFromReverseUnevenNestedEmptyArray) {
-        BSONObj keyPattern = fromjson("{'a.b': 1, 'a': 1}");
-        BSONObj genKeysFrom = fromjson("{a:[]}");
-        BSONObjSet expectedKeys;
-        expectedKeys.insert(fromjson("{'': null, '': undefined}"));
-        ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys));
-    }
-
-    TEST(BtreeKeyGeneratorTest, SparseReverseUnevenNestedEmptyArray) {
-        BSONObj keyPattern = fromjson("{'a.b': 1, 'a': 1}");
-        BSONObj genKeysFrom = fromjson("{a:[]}");
-        BSONObjSet expectedKeys;
-        expectedKeys.insert(fromjson("{'': null, '': undefined}"));
-        // true means sparse
-        ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys, true));
-    }
-
-    TEST(BtreeKeyGeneratorTest, GetKeysFromSparseEmptyArray) {
-        BSONObj keyPattern = fromjson("{'a.b': 1}");
-        BSONObj genKeysFrom = fromjson("{a:1}");
-        BSONObjSet expectedKeys;
-        // true means sparse
-        ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys, true));
-
-        genKeysFrom = fromjson("{a:[]}");
-        // true means sparse
-        ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys, true));
-
-        genKeysFrom = fromjson("{a:[{c:1}]}");
-        // true means sparse
-        ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys, true));
-    }
-
-    TEST(BtreeKeyGeneratorTest, GetKeysFromSparseEmptyArraySecond) {
-        BSONObj keyPattern = fromjson("{z: 1, 'a.b': 1}");
-        BSONObj genKeysFrom = fromjson("{a:1}");
-        BSONObjSet expectedKeys;
-        // true means sparse
-        ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys, true));
-
-        genKeysFrom = fromjson("{a:[]}");
-        // true means sparse
-        ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys, true));
-
-        genKeysFrom = fromjson("{a:[{c:1}]}");
-        // true means sparse
-        ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys, true));
-    }
-
-    TEST(BtreeKeyGeneratorTest, SparseNonObjectMissingNestedField) {
-        BSONObj keyPattern = fromjson("{'a.b': 1}");
-        BSONObj genKeysFrom = fromjson("{a:[]}");
-        BSONObjSet expectedKeys;
-        // true means sparse
-        ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys, true));
-
-        genKeysFrom = fromjson("{a:[1]}");
-        // true means sparse
-        ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys, true));
-
-        genKeysFrom = fromjson("{a:[1,{b:1}]}");
-        expectedKeys.clear();
-        expectedKeys.insert(fromjson("{'': 1}"));
-        // true means sparse
-        ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys, true));
-    }
-
-    TEST(BtreeKeyGeneratorTest, GetKeysFromIndexedArrayIndex) {
-        BSONObj keyPattern = fromjson("{'a.0': 1}");
-        BSONObj genKeysFrom = fromjson("{a:[1]}");
-        BSONObjSet expectedKeys;
-        expectedKeys.insert(fromjson("{'': 1}"));
-        ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys));
-
-        genKeysFrom = fromjson("{a:[[1]]}");
-        expectedKeys.clear();
-        expectedKeys.insert(fromjson("{'': [1]}"));
-        ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys));
-
-        genKeysFrom = fromjson("{a:[[]]}");
-        expectedKeys.clear();
-        expectedKeys.insert(fromjson("{'': undefined}"));
-        ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys));
-
-        genKeysFrom = fromjson("{a:[[]]}");
-        expectedKeys.clear();
-        expectedKeys.insert(fromjson("{'': undefined}"));
-        ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys));
-
-        genKeysFrom = fromjson("{a:{'0':1}}");
-        expectedKeys.clear();
-        expectedKeys.insert(fromjson("{'': 1}"));
-        ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys));
-
-        genKeysFrom = fromjson("{a:[{'0':1}]}");
-        expectedKeys.clear();
-        ASSERT_THROWS(testKeygen(keyPattern, genKeysFrom, expectedKeys), UserException);
-
-        genKeysFrom = fromjson("{a:[1,{'0':2}]}");
-        ASSERT_THROWS(testKeygen(keyPattern, genKeysFrom, expectedKeys), UserException);
-    }
-
-    TEST(BtreeKeyGeneratorTest, GetKeysFromDoubleIndexedArrayIndex) {
-        BSONObj keyPattern = fromjson("{'a.0.0': 1}");
-        BSONObj genKeysFrom = fromjson("{a:[[1]]}");
-        BSONObjSet expectedKeys;
-        expectedKeys.insert(fromjson("{'': 1}"));
-        ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys));
-
-        genKeysFrom = fromjson("{a:[[]]}");
-        expectedKeys.clear();
-        expectedKeys.insert(fromjson("{'': null}"));
-        ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys));
-
-        genKeysFrom = fromjson("{a:[]}");
-        expectedKeys.clear();
-        expectedKeys.insert(fromjson("{'': null}"));
-        ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys));
-
-        genKeysFrom = fromjson("{a:[[[]]]}");
-        expectedKeys.clear();
-        expectedKeys.insert(fromjson("{'': undefined}"));
-        ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys));
-    }
-
-    TEST(BtreeKeyGeneratorTest, GetKeysFromObjectWithinArray) {
-        BSONObj keyPattern = fromjson("{'a.0.b': 1}");
-        BSONObj genKeysFrom = fromjson("{a:[{b:1}]}");
-        BSONObjSet expectedKeys;
-        expectedKeys.insert(fromjson("{'': 1}"));
-        ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys));
-
-        genKeysFrom = fromjson("{a:[{b:[1]}]}");
-        expectedKeys.clear();
-        expectedKeys.insert(fromjson("{'': 1}"));
-        ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys));
-
-        genKeysFrom = fromjson("{a:[{b:[[1]]}]}");
-        expectedKeys.clear();
-        expectedKeys.insert(fromjson("{'': [1]}"));
-        ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys));
-
-        genKeysFrom = fromjson("{a:[[{b:1}]]}");
-        expectedKeys.clear();
-        expectedKeys.insert(fromjson("{'': 1}"));
-        ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys));
-
-        genKeysFrom = fromjson("{a:[[{b:[1]}]]}");
-        expectedKeys.clear();
-        expectedKeys.insert(fromjson("{'': 1}"));
-        ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys));
-
-        genKeysFrom = fromjson("{a:[[{b:[[1]]}]]}");
-        expectedKeys.clear();
-        expectedKeys.insert(fromjson("{'': [1]}"));
-        ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys));
-
-        genKeysFrom = fromjson("{a:[[{b:[]}]]}");
-        expectedKeys.clear();
-        expectedKeys.insert(fromjson("{'': undefined}"));
-        ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys));
-    }
-
-    TEST(BtreeKeyGeneratorTest, GetKeysFromArrayWithinObjectWithinArray) {
-        BSONObj keyPattern = fromjson("{'a.0.b.0': 1}");
-        BSONObj genKeysFrom = fromjson("{a:[{b:[1]}]}");
-        BSONObjSet expectedKeys;
-        expectedKeys.insert(fromjson("{'': 1}"));
-        ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys));
-    }
-
-    TEST(BtreeKeyGeneratorTest, ParallelArraysInNestedObjects) {
-        BSONObj keyPattern = fromjson("{'a.a': 1, 'b.a': 1}");
-        BSONObj genKeysFrom = fromjson("{a:{a:[1]}, b:{a:[1]}}");
-        BSONObjSet expectedKeys;
-        ASSERT_THROWS(testKeygen(keyPattern, genKeysFrom, expectedKeys), UserException);
-    }
-
-    TEST(BtreeKeyGeneratorTest, ParallelArraysUneven) {
-        BSONObj keyPattern = fromjson("{'b.a': 1, 'a': 1}");
-        BSONObj genKeysFrom = fromjson("{b:{a:[1]}, a:[1,2]}");
-        BSONObjSet expectedKeys;
-        ASSERT_THROWS(testKeygen(keyPattern, genKeysFrom, expectedKeys), UserException);
-    }
-
-    TEST(BtreeKeyGeneratorTest, MultipleArraysNotParallel) {
-        BSONObj keyPattern = fromjson("{'a.b.c': 1}");
-        BSONObj genKeysFrom = fromjson("{a: [1, 2, {b: {c: [3, 4]}}]}");
-        BSONObjSet expectedKeys;
-        expectedKeys.insert(fromjson("{'': null}"));
-        expectedKeys.insert(fromjson("{'': 3}"));
-        expectedKeys.insert(fromjson("{'': 4}"));
-        ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys));
-    }
-
-    TEST(BtreeKeyGeneratorTest, MultipleArraysNotParallelCompound) {
-        BSONObj keyPattern = fromjson("{'a.b.c': 1, 'a.b.d': 1}");
-        BSONObj genKeysFrom = fromjson("{a: [1, 2, {b: {c: [3, 4], d: 5}}]}");
-        BSONObjSet expectedKeys;
-        expectedKeys.insert(fromjson("{'': null, '': null}"));
-        expectedKeys.insert(fromjson("{'': 3, '': 5}"));
-        expectedKeys.insert(fromjson("{'': 4, '': 5}"));
-        ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys));
-    }
-
-    TEST(BtreeKeyGeneratorTest, GetKeysComplexNestedArrays) {
-        BSONObj keyPattern = fromjson(
-            "{'a.b.c.d': 1, 'a.g': 1, 'a.b.f': 1, 'a.b.c': 1, 'a.b.e': 1}");
-        BSONObj genKeysFrom = fromjson(
-            "{a: [1, {b: [2, {c: [3, {d: 1}], e: 4}, 5, {f: 6}], g: 7}]}");
-        BSONObjSet expectedKeys;
-        expectedKeys.insert(fromjson("{'':null, '':null, '':null, '':null, '':null}"));
-        expectedKeys.insert(fromjson("{'':null, '':7, '':null, '':null, '':null}"));
-        expectedKeys.insert(fromjson("{'':null, '':7, '':null, '':3, '':4}"));
-        expectedKeys.insert(fromjson("{'':null, '':7, '':6, '':null, '':null}"));
-        expectedKeys.insert(fromjson("{'':1, '':7, '':null, '':{d: 1}, '':4}"));
-        ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys));
-    }
-
-    // Descriptive test. Should future index versions recursively index nested arrays?
-    TEST(BtreeKeyGeneratorTest, GetKeys2DArray) {
-        BSONObj keyPattern = fromjson("{a: 1}");
-        BSONObj genKeysFrom = fromjson("{a: [[2]]}");
-        BSONObjSet expectedKeys;
-        expectedKeys.insert(fromjson("{'': [2]}"));
-        ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys));
-    }
-
-    // Descriptive test. Should parallel indexed arrays be allowed? If not, should empty
-    // or single-element arrays be considered for the parallel array check?
-    TEST(BtreeKeyGeneratorTest, GetKeysParallelEmptyArrays) {
-        BSONObj keyPattern = fromjson("{a: 1, b: 1}");
-        BSONObj genKeysFrom = fromjson("{a: [], b: []}");
-        BSONObjSet expectedKeys;
-        ASSERT_THROWS(testKeygen(keyPattern, genKeysFrom, expectedKeys), UserException);
-    }
-
-    TEST(BtreeKeyGeneratorTest, GetKeysParallelArraysOneArrayEmpty) {
-        BSONObj keyPattern = fromjson("{a: 1, b: 1}");
-        BSONObj genKeysFrom = fromjson("{a: [], b: [1, 2, 3]}");
-        BSONObjSet expectedKeys;
-        ASSERT_THROWS(testKeygen(keyPattern, genKeysFrom, expectedKeys), UserException);
-    }
-
-    TEST(BtreeKeyGeneratorTest, GetKeysParallelArraysOneArrayEmptyNested) {
-        BSONObj keyPattern = fromjson("{'a.b.c': 1, 'a.b.d': 1}");
-        BSONObj genKeysFrom = fromjson("{a: [{b: [{c: [1, 2, 3], d: []}]}]}");
-        BSONObjSet expectedKeys;
-        ASSERT_THROWS(testKeygen(keyPattern, genKeysFrom, expectedKeys), UserException);
-    }
-
-    // Descriptive test. The semantics for key generation are odd for positional key patterns.
-    TEST(BtreeKeyGeneratorTest, GetKeysPositionalKeyPatternMissingElement) {
-        BSONObj keyPattern = fromjson("{'a.2': 1}");
-        BSONObj genKeysFrom = fromjson("{a: [{'2': 5}]}");
-        BSONObjSet expectedKeys;
-        expectedKeys.insert(fromjson("{'': 5}"));
-        ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys));
-    }
-
-    // Descriptive test. The semantics for key generation are odd for positional key patterns.
-    TEST(BtreeKeyGeneratorTest, GetKeysPositionalKeyPatternNestedArray) {
-        BSONObj keyPattern = fromjson("{'a.2': 1}");
-        BSONObj genKeysFrom = fromjson("{a: [[1, 2, 5]]}");
-        BSONObjSet expectedKeys;
-        expectedKeys.insert(fromjson("{'': null}"));
-        ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys));
-    }
-
-    // Descriptive test. The semantics for key generation are odd for positional key patterns.
-    TEST(BtreeKeyGeneratorTest, GetKeysPositionalKeyPatternNestedArray2) {
-        BSONObj keyPattern = fromjson("{'a.2': 1}");
-        BSONObj genKeysFrom = fromjson("{a: [[1, 2, 5], [3, 4, 6], [0, 1, 2]]}");
-        BSONObjSet expectedKeys;
-        expectedKeys.insert(fromjson("{'': [0, 1, 2]}"));
-        ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys));
-    }
-
-    // Descriptive test. The semantics for key generation are odd for positional key patterns.
-    TEST(BtreeKeyGeneratorTest, GetKeysPositionalKeyPatternNestedArray3) {
-        BSONObj keyPattern = fromjson("{'a.2': 1}");
-        BSONObj genKeysFrom = fromjson("{a: [{'0': 1, '1': 2, '2': 5}]}");
-        BSONObjSet expectedKeys;
-        expectedKeys.insert(fromjson("{'': 5}"));
-        ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys));
-    }
-
-    // Descriptive test. The semantics for key generation are odd for positional key patterns.
-    TEST(BtreeKeyGeneratorTest, GetKeysPositionalKeyPatternNestedArray4) {
-        BSONObj keyPattern = fromjson("{'a.b.2': 1}");
-        BSONObj genKeysFrom = fromjson("{a: [{b: [[1, 2, 5]]}]}");
-        BSONObjSet expectedKeys;
-        expectedKeys.insert(fromjson("{'': null}"));
-        ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys));
-    }
-
-    // Descriptive test. The semantics for key generation are odd for positional key patterns.
-    TEST(BtreeKeyGeneratorTest, GetKeysPositionalKeyPatternNestedArray5) {
-        BSONObj keyPattern = fromjson("{'a.2': 1}");
-        BSONObj genKeysFrom = fromjson("{a: [[1, 2, 5], {'2': 6}]}");
-        BSONObjSet expectedKeys;
-        expectedKeys.insert(fromjson("{'': null}"));
-        expectedKeys.insert(fromjson("{'': 6}"));
-        ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys));
-    }
-
-    TEST(BtreeKeyGeneratorTest, GetNullKeyNestedArray) {
-        BSONObj keyPattern = fromjson("{'a.b': 1}");
-        BSONObj genKeysFrom = fromjson("{a: [[1, 2, 5]]}");
-        BSONObjSet expectedKeys;
-        expectedKeys.insert(fromjson("{'': null}"));
-        ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys));
-    }
-
-    TEST(BtreeKeyGeneratorTest, GetKeysUnevenNestedArrays) {
-        BSONObj keyPattern = fromjson("{a: 1, 'a.b': 1}");
-        BSONObj genKeysFrom = fromjson("{a: [1, {b: [2, 3, 4]}]}");
-        BSONObjSet expectedKeys;
-        expectedKeys.insert(fromjson("{'': 1, '': null}"));
-        expectedKeys.insert(fromjson("{'': {b:[2,3,4]}, '': 2}"));
-        expectedKeys.insert(fromjson("{'': {b:[2,3,4]}, '': 3}"));
-        expectedKeys.insert(fromjson("{'': {b:[2,3,4]}, '': 4}"));
-        ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys));
-    }
-
-    // Descriptive test. Should we define better semantics for future index versions in the case of
-    // repeated field names?
-    TEST(BtreeKeyGeneratorTest, GetKeysRepeatedFieldName) {
-        BSONObj keyPattern = fromjson("{a: 1}");
-        BSONObj genKeysFrom = fromjson("{a: 2, a: 3}");
-        BSONObjSet expectedKeys;
-        expectedKeys.insert(fromjson("{'': 2}"));
-        ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys));
-    }
-
-    // Descriptive test. Future index versions may want different or at least more consistent
-    // handling of empty path components.
-    TEST(BtreeKeyGeneratorTest, GetKeysEmptyPathPiece) {
-        BSONObj keyPattern = fromjson("{'a..c': 1}");
-        BSONObj genKeysFrom = fromjson("{a: {'': [{c: 1}, {c: 2}]}}");
-        BSONObjSet expectedKeys;
-        expectedKeys.insert(fromjson("{'': 1}"));
-        expectedKeys.insert(fromjson("{'': 2}"));
-        ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys));
-    }
-
-    // Descriptive test. Future index versions may want different or at least more consistent
-    // handling of empty path components.
-    TEST(BtreeKeyGeneratorTest, GetKeysLastPathPieceEmpty) {
-        BSONObj keyPattern = fromjson("{'a.': 1}");
-
-        BSONObj genKeysFrom = fromjson("{a: 2}");
-        BSONObjSet expectedKeys;
-        expectedKeys.insert(fromjson("{'': 2}"));
-        ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys));
-
-        genKeysFrom = fromjson("{a: {'': 2}}");
-        expectedKeys.clear();
-        expectedKeys.insert(fromjson("{'': {'': 2}}"));
-        ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys));
-    }
-
-    TEST(BtreeKeyGeneratorTest, GetKeysFirstPathPieceEmpty) {
-        BSONObj keyPattern = fromjson("{'.a': 1}");
-        BSONObj genKeysFrom = fromjson("{a: 2}");
-        BSONObjSet expectedKeys;
-        expectedKeys.insert(fromjson("{'': null}"));
-        ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys));
-    }
-
-    TEST(BtreeKeyGeneratorTest, GetKeysFirstPathPieceEmpty2) {
-        BSONObj keyPattern = fromjson("{'.a': 1}");
-        BSONObj genKeysFrom = fromjson("{'': [{a: [1, 2, 3]}]}");
-        BSONObjSet expectedKeys;
-        expectedKeys.insert(fromjson("{'': 1}"));
-        expectedKeys.insert(fromjson("{'': 2}"));
-        expectedKeys.insert(fromjson("{'': 3}"));
-        ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys));
-    }
-
-    TEST(BtreeKeyGeneratorTest, PositionalKeyPatternParallelArrays) {
-        BSONObj keyPattern = fromjson("{a: 1, 'b.0': 1}");
-        BSONObj genKeysFrom = fromjson("{a: [1], b: [2]}");
-        BSONObjSet expectedKeys;
-        ASSERT_THROWS(testKeygen(keyPattern, genKeysFrom, expectedKeys), UserException);
-    }
-
-    // Descriptive test.
-    TEST(BtreeKeyGeneratorTest, PositionalKeyPatternNestedArrays) {
-        BSONObj keyPattern = fromjson("{'a.0.b': 1}");
-        BSONObj genKeysFrom = fromjson("{a: [[{b: 1}]]}");
-        BSONObjSet expectedKeys;
-        expectedKeys.insert(fromjson("{'': 1}"));
-        ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys));
-    }
-
-    // Descriptive test.
-    TEST(BtreeKeyGeneratorTest, PositionalKeyPatternNestedArrays2) {
-        BSONObj keyPattern = fromjson("{'a.0.0.b': 1}");
-        BSONObj genKeysFrom = fromjson("{a: [[{b: 1}]]}");
-        BSONObjSet expectedKeys;
-        expectedKeys.insert(fromjson("{'': 1}"));
-        ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys));
-    }
-
-    // Descriptive test.
-    TEST(BtreeKeyGeneratorTest, PositionalKeyPatternNestedArrays3) {
-        BSONObj keyPattern = fromjson("{'a.0.0.b': 1}");
-        BSONObj genKeysFrom = fromjson("{a: [[[ {b: 1} ]]]}");
-        BSONObjSet expectedKeys;
-        expectedKeys.insert(fromjson("{'': 1}"));
-        ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys));
-    }
-
-    // Descriptive test.
-    TEST(BtreeKeyGeneratorTest, PositionalKeyPatternNestedArrays4) {
-        BSONObj keyPattern = fromjson("{'a.0.0.b': 1}");
-        BSONObj genKeysFrom = fromjson("{a: [[[[ {b: 1} ]]]]}");
-        BSONObjSet expectedKeys;
-        expectedKeys.insert(fromjson("{'': null}"));
-        ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys));
-    }
-
-    TEST(BtreeKeyGeneratorTest, PositionalKeyPatternNestedArrays5) {
-        BSONObj keyPattern = fromjson("{'a.b.1': 1}");
-        BSONObj genKeysFrom = fromjson("{a: [{b: [1, 2]}]}");
-        BSONObjSet expectedKeys;
-        expectedKeys.insert(fromjson("{'': 2}"));
-        ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys));
-    }
-
-    // Descriptive test.
-    TEST(BtreeKeyGeneratorTest, PositionalKeyPatternNestedArrays6) {
-        BSONObj keyPattern = fromjson("{'a': 1, 'a.b': 1, 'a.0.b':1, 'a.b.0': 1, 'a.0.b.0': 1}");
-        BSONObj genKeysFrom = fromjson("{a: [{b: [1,2]}, {b: 3}]}");
-        BSONObjSet expectedKeys;
-        expectedKeys.insert(fromjson("{'': {b:3}, '': 3, '': 1, '': null, '': 1}"));
-        expectedKeys.insert(fromjson("{'': {b:3}, '': 3, '': 2, '': null, '': 1}"));
-        expectedKeys.insert(fromjson("{'': {b:[1,2]}, '': 1, '': 1, '': 1, '': 1}"));
-        expectedKeys.insert(fromjson("{'': {b:[1,2]}, '': 2, '': 2, '': 1, '': 1}"));
-        ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys));
-    }
-
-    // Descriptive test.
-    TEST(BtreeKeyGeneratorTest, PositionalKeyPatternNestedArrays7) {
-        BSONObj keyPattern = fromjson("{'a': 1, 'a.b': 1, 'a.0.b':1, 'a.b.0': 1, 'a.0.b.0': 1}");
-        BSONObj genKeysFrom = fromjson("{a: [{b: [1,2]}, {b: {'0': 3}}]}");
-        BSONObjSet expectedKeys;
-        expectedKeys.insert(fromjson("{'': {b:{'0':3}}, '': {'0':3}, '': 1, '': 3, '': 1}"));
-        expectedKeys.insert(fromjson("{'': {b:{'0':3}}, '': {'0':3}, '': 2, '': 3, '': 1}"));
-        expectedKeys.insert(fromjson("{'': {b:[1,2]}, '': 1, '': 1, '': 1, '': 1}"));
-        expectedKeys.insert(fromjson("{'': {b:[1,2]}, '': 2, '': 2, '': 1, '': 1}"));
-        ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys));
-    }
+    //
+    // Step 2: ask 'keyGen' to generate index keys for the object 'obj'.
+    //
+    BSONObjSet actualKeys;
+    keyGen->getKeys(obj, &actualKeys);
 
-} // namespace
+    //
+    // Step 3: check that the results match the expected result.
+    //
+    bool match = keysetsMatch(expectedKeys, actualKeys);
+    if (!match) {
+        cout << "Expected: " << dumpKeyset(expectedKeys) << ", "
+             << "Actual: " << dumpKeyset(actualKeys) << endl;
+    }
+
+    return match;
+}
+
+//
+// Unit tests
+//
+
+TEST(BtreeKeyGeneratorTest, GetKeysFromObjectSimple) {
+    BSONObj keyPattern = fromjson("{a: 1}");
+    BSONObj genKeysFrom = fromjson("{b: 4, a: 5}");
+    BSONObjSet expectedKeys;
+    expectedKeys.insert(fromjson("{'': 5}"));
+    ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys));
+}
+
+TEST(BtreeKeyGeneratorTest, GetKeysFromObjectDotted) {
+    BSONObj keyPattern = fromjson("{'a.b': 1}");
+    BSONObj genKeysFrom = fromjson("{a: {b: 4}, c: 'foo'}");
+    BSONObjSet expectedKeys;
+    expectedKeys.insert(fromjson("{'': 4}"));
+    ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys));
+}
+
+TEST(BtreeKeyGeneratorTest, GetKeysFromArraySimple) {
+    BSONObj keyPattern = fromjson("{a: 1}");
+    BSONObj genKeysFrom = fromjson("{a: [1, 2, 3]}");
+    BSONObjSet expectedKeys;
+    expectedKeys.insert(fromjson("{'': 1}"));
+    expectedKeys.insert(fromjson("{'': 2}"));
+    expectedKeys.insert(fromjson("{'': 3}"));
+    ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys));
+}
+
+TEST(BtreeKeyGeneratorTest, GetKeysFromArrayFirstElement) {
+    BSONObj keyPattern = fromjson("{a: 1, b: 1}");
+    BSONObj genKeysFrom = fromjson("{a: [1, 2, 3], b: 2}");
+    BSONObjSet expectedKeys;
+    expectedKeys.insert(fromjson("{'': 1, '': 2}"));
+    expectedKeys.insert(fromjson("{'': 2, '': 2}"));
+    expectedKeys.insert(fromjson("{'': 3, '': 2}"));
+    ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys));
+}
+
+TEST(BtreeKeyGeneratorTest, GetKeysFromArraySecondElement) {
+    BSONObj keyPattern = fromjson("{first: 1, a: 1}");
+    BSONObj genKeysFrom = fromjson("{first: 5, a: [1, 2, 3]}");
+    BSONObjSet expectedKeys;
+    expectedKeys.insert(fromjson("{'': 5, '': 1}"));
+    expectedKeys.insert(fromjson("{'': 5, '': 2}"));
+    expectedKeys.insert(fromjson("{'': 5, '': 3}"));
+    ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys));
+}
+
+TEST(BtreeKeyGeneratorTest, GetKeysFromSecondLevelArray) {
+    BSONObj keyPattern = fromjson("{'a.b': 1}");
+    BSONObj genKeysFrom = fromjson("{a: {b: [1, 2, 3]}}");
+    BSONObjSet expectedKeys;
+    expectedKeys.insert(fromjson("{'': 1}"));
+    expectedKeys.insert(fromjson("{'': 2}"));
+    expectedKeys.insert(fromjson("{'': 3}"));
+    ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys));
+}
+
+TEST(BtreeKeyGeneratorTest, GetKeysFromParallelArraysBasic) {
+    BSONObj keyPattern = fromjson("{'a': 1, 'b': 1}");
+    BSONObj genKeysFrom = fromjson("{a: [1, 2, 3], b: [1, 2, 3]}}");
+    BSONObjSet expectedKeys;
+    ASSERT_THROWS(testKeygen(keyPattern, genKeysFrom, expectedKeys), UserException);
+}
+
+TEST(BtreeKeyGeneratorTest, GetKeysFromArraySubobjectBasic) {
+    BSONObj keyPattern = fromjson("{'a.b': 1}");
+    BSONObj genKeysFrom = fromjson("{a: [{b:1,c:4}, {b:2,c:4}, {b:3,c:4}]}");
+    BSONObjSet expectedKeys;
+    expectedKeys.insert(fromjson("{'': 1}"));
+    expectedKeys.insert(fromjson("{'': 2}"));
+    expectedKeys.insert(fromjson("{'': 3}"));
+    ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys));
+}
+
+TEST(BtreeKeyGeneratorTest, GetKeysArraySubobjectCompoundIndex) {
+    BSONObj keyPattern = fromjson("{'a.b': 1, d: 99}");
+    BSONObj genKeysFrom = fromjson("{a: [{b:1,c:4}, {b:2,c:4}, {b:3,c:4}], d: 99}");
+    BSONObjSet expectedKeys;
+    expectedKeys.insert(fromjson("{'': 1, '': 99}"));
+    expectedKeys.insert(fromjson("{'': 2, '': 99}"));
+    expectedKeys.insert(fromjson("{'': 3, '': 99}"));
+    ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys));
+}
+
+TEST(BtreeKeyGeneratorTest, GetKeysArraySubobjectSingleMissing) {
+    BSONObj keyPattern = fromjson("{'a.b': 1}");
+    BSONObj genKeysFrom = fromjson("{a: [{foo: 41}, {b:1,c:4}, {b:2,c:4}, {b:3,c:4}]}");
+    BSONObjSet expectedKeys;
+    expectedKeys.insert(fromjson("{'': null}"));
+    expectedKeys.insert(fromjson("{'': 1}"));
+    expectedKeys.insert(fromjson("{'': 2}"));
+    expectedKeys.insert(fromjson("{'': 3}"));
+    ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys));
+}
+
+TEST(BtreeKeyGeneratorTest, GetKeysFromArraySubobjectMissing) {
+    BSONObj keyPattern = fromjson("{'a.b': 1}");
+    BSONObj genKeysFrom = fromjson("{a: [{foo: 41}, {foo: 41}, {foo: 41}]}");
+    BSONObjSet expectedKeys;
+    expectedKeys.insert(fromjson("{'': null}"));
+    ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys));
+}
+
+TEST(BtreeKeyGeneratorTest, GetKeysMissingField) {
+    BSONObj keyPattern = fromjson("{a: 1}");
+    BSONObj genKeysFrom = fromjson("{b: 1}");
+    BSONObjSet expectedKeys;
+    expectedKeys.insert(fromjson("{'': null}"));
+    ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys));
+}
+
+TEST(BtreeKeyGeneratorTest, GetKeysSubobjectMissing) {
+    BSONObj keyPattern = fromjson("{'a.b': 1}");
+    BSONObj genKeysFrom = fromjson("{a: [1, 2]}");
+    BSONObjSet expectedKeys;
+    expectedKeys.insert(fromjson("{'': null}"));
+    ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys));
+}
+
+TEST(BtreeKeyGeneratorTest, GetKeysFromCompound) {
+    BSONObj keyPattern = fromjson("{x: 1, y: 1}");
+    BSONObj genKeysFrom = fromjson("{x: 'a', y: 'b'}");
+    BSONObjSet expectedKeys;
+    expectedKeys.insert(fromjson("{'': 'a', '': 'b'}"));
+    ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys));
+}
+
+TEST(BtreeKeyGeneratorTest, GetKeysFromCompoundMissing) {
+    BSONObj keyPattern = fromjson("{x: 1, y: 1}");
+    BSONObj genKeysFrom = fromjson("{x: 'a'}");
+    BSONObjSet expectedKeys;
+    expectedKeys.insert(fromjson("{'': 'a', '': null}"));
+    ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys));
+}
+
+TEST(BtreeKeyGeneratorTest, GetKeysFromArraySubelementComplex) {
+    BSONObj keyPattern = fromjson("{'a.b': 1}");
+    BSONObj genKeysFrom = fromjson("{a:[{b:[2]}]}");
+    BSONObjSet expectedKeys;
+    expectedKeys.insert(fromjson("{'': 2}"));
+    ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys));
+}
+
+TEST(BtreeKeyGeneratorTest, GetKeysFromParallelArraysComplex) {
+    BSONObj keyPattern = fromjson("{'a.b': 1, 'a.c': 1}");
+    BSONObj genKeysFrom = fromjson("{a:[{b:[1],c:[2]}]}");
+    BSONObjSet expectedKeys;
+    ASSERT_THROWS(testKeygen(keyPattern, genKeysFrom, expectedKeys), UserException);
+}
+
+TEST(BtreeKeyGeneratorTest, GetKeysAlternateMissing) {
+    BSONObj keyPattern = fromjson("{'a.b': 1, 'a.c': 1}");
+    BSONObj genKeysFrom = fromjson("{a:[{b:1},{c:2}]}");
+    BSONObjSet expectedKeys;
+    expectedKeys.insert(fromjson("{'': null, '': 2}"));
+    expectedKeys.insert(fromjson("{'': 1, '': null}"));
+    ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys));
+}
+
+TEST(BtreeKeyGeneratorTest, GetKeysFromMultiComplex) {
+    BSONObj keyPattern = fromjson("{'a.b': 1}");
+    BSONObj genKeysFrom = fromjson("{a:[{b:1},{b:[1,2,3]}]}");
+    BSONObjSet expectedKeys;
+    expectedKeys.insert(fromjson("{'': 1}"));
+    expectedKeys.insert(fromjson("{'': 2}"));
+    expectedKeys.insert(fromjson("{'': 3}"));
+    ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys));
+}
+
+TEST(BtreeKeyGeneratorTest, GetKeysArrayEmpty) {
+    BSONObj keyPattern = fromjson("{a: 1}");
+    BSONObj genKeysFrom = fromjson("{a:[1,2]}");
+    BSONObjSet expectedKeys;
+    expectedKeys.insert(fromjson("{'': 1}"));
+    expectedKeys.insert(fromjson("{'': 2}"));
+    ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys));
+
+    genKeysFrom = fromjson("{a: [1]}");
+    expectedKeys.clear();
+    expectedKeys.insert(fromjson("{'': 1}"));
+    ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys));
+
+    genKeysFrom = fromjson("{a: null}");
+    expectedKeys.clear();
+    expectedKeys.insert(fromjson("{'': null}"));
+    ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys));
+
+    genKeysFrom = fromjson("{a: []}");
+    expectedKeys.clear();
+    expectedKeys.insert(fromjson("{'': undefined}"));
+    ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys));
+}
+
+TEST(BtreeKeyGeneratorTest, GetKeysFromDoubleArray) {
+    BSONObj keyPattern = fromjson("{a: 1, a: 1}");
+    BSONObj genKeysFrom = fromjson("{a:[1,2]}");
+    BSONObjSet expectedKeys;
+    expectedKeys.insert(fromjson("{'': 1, '': 1}"));
+    expectedKeys.insert(fromjson("{'': 2, '': 2}"));
+    ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys));
+}
+
+TEST(BtreeKeyGeneratorTest, GetKeysFromDoubleEmptyArray) {
+    BSONObj keyPattern = fromjson("{a: 1, a: 1}");
+    BSONObj genKeysFrom = fromjson("{a:[]}");
+    BSONObjSet expectedKeys;
+    expectedKeys.insert(fromjson("{'': undefined, '': undefined}"));
+    ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys));
+}
+
+TEST(BtreeKeyGeneratorTest, GetKeysFromMultiEmptyArray) {
+    BSONObj keyPattern = fromjson("{a: 1, b: 1}");
+    BSONObj genKeysFrom = fromjson("{a: 1, b: [1, 2]}");
+    BSONObjSet expectedKeys;
+    expectedKeys.insert(fromjson("{'': 1, '': 1}"));
+    expectedKeys.insert(fromjson("{'': 1, '': 2}"));
+    ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys));
+
+    genKeysFrom = fromjson("{a: 1, b: [1]}");
+    expectedKeys.clear();
+    expectedKeys.insert(fromjson("{'': 1, '': 1}"));
+    ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys));
+
+    genKeysFrom = fromjson("{a: 1, b: []}");
+    expectedKeys.clear();
+    expectedKeys.insert(fromjson("{'': 1, '': undefined}"));
+    ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys));
+}
+
+TEST(BtreeKeyGeneratorTest, GetKeysFromNestedEmptyArray) {
+    BSONObj keyPattern = fromjson("{'a.b': 1}");
+    BSONObj genKeysFrom = fromjson("{a:[]}");
+    BSONObjSet expectedKeys;
+    expectedKeys.insert(fromjson("{'': null}"));
+    ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys));
+}
+
+TEST(BtreeKeyGeneratorTest, GetKeysFromMultiNestedEmptyArray) {
+    BSONObj keyPattern = fromjson("{'a.b': 1, 'a.c': 1}");
+    BSONObj genKeysFrom = fromjson("{a:[]}");
+    BSONObjSet expectedKeys;
+    expectedKeys.insert(fromjson("{'': null, '': null}"));
+    ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys));
+}
+
+TEST(BtreeKeyGeneratorTest, GetKeysFromUnevenNestedEmptyArray) {
+    BSONObj keyPattern = fromjson("{'a': 1, 'a.b': 1}");
+    BSONObj genKeysFrom = fromjson("{a:[]}");
+    BSONObjSet expectedKeys;
+    expectedKeys.insert(fromjson("{'': undefined, '': null}"));
+    ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys));
+
+    genKeysFrom = fromjson("{a:[{b: 1}]}");
+    expectedKeys.clear();
+    expectedKeys.insert(fromjson("{'': {b:1}, '': 1}"));
+    ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys));
+
+    genKeysFrom = fromjson("{a:[{b: []}]}");
+    expectedKeys.clear();
+    expectedKeys.insert(fromjson("{'': {b:[]}, '': undefined}"));
+    ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys));
+}
+
+TEST(BtreeKeyGeneratorTest, GetKeysFromReverseUnevenNestedEmptyArray) {
+    BSONObj keyPattern = fromjson("{'a.b': 1, 'a': 1}");
+    BSONObj genKeysFrom = fromjson("{a:[]}");
+    BSONObjSet expectedKeys;
+    expectedKeys.insert(fromjson("{'': null, '': undefined}"));
+    ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys));
+}
+
+TEST(BtreeKeyGeneratorTest, SparseReverseUnevenNestedEmptyArray) {
+    BSONObj keyPattern = fromjson("{'a.b': 1, 'a': 1}");
+    BSONObj genKeysFrom = fromjson("{a:[]}");
+    BSONObjSet expectedKeys;
+    expectedKeys.insert(fromjson("{'': null, '': undefined}"));
+    // true means sparse
+    ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys, true));
+}
+
+TEST(BtreeKeyGeneratorTest, GetKeysFromSparseEmptyArray) {
+    BSONObj keyPattern = fromjson("{'a.b': 1}");
+    BSONObj genKeysFrom = fromjson("{a:1}");
+    BSONObjSet expectedKeys;
+    // true means sparse
+    ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys, true));
+
+    genKeysFrom = fromjson("{a:[]}");
+    // true means sparse
+    ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys, true));
+
+    genKeysFrom = fromjson("{a:[{c:1}]}");
+    // true means sparse
+    ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys, true));
+}
+
+TEST(BtreeKeyGeneratorTest, GetKeysFromSparseEmptyArraySecond) {
+    BSONObj keyPattern = fromjson("{z: 1, 'a.b': 1}");
+    BSONObj genKeysFrom = fromjson("{a:1}");
+    BSONObjSet expectedKeys;
+    // true means sparse
+    ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys, true));
+
+    genKeysFrom = fromjson("{a:[]}");
+    // true means sparse
+    ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys, true));
+
+    genKeysFrom = fromjson("{a:[{c:1}]}");
+    // true means sparse
+    ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys, true));
+}
+
+TEST(BtreeKeyGeneratorTest, SparseNonObjectMissingNestedField) {
+    BSONObj keyPattern = fromjson("{'a.b': 1}");
+    BSONObj genKeysFrom = fromjson("{a:[]}");
+    BSONObjSet expectedKeys;
+    // true means sparse
+    ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys, true));
+
+    genKeysFrom = fromjson("{a:[1]}");
+    // true means sparse
+    ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys, true));
+
+    genKeysFrom = fromjson("{a:[1,{b:1}]}");
+    expectedKeys.clear();
+    expectedKeys.insert(fromjson("{'': 1}"));
+    // true means sparse
+    ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys, true));
+}
+
+TEST(BtreeKeyGeneratorTest, GetKeysFromIndexedArrayIndex) {
+    BSONObj keyPattern = fromjson("{'a.0': 1}");
+    BSONObj genKeysFrom = fromjson("{a:[1]}");
+    BSONObjSet expectedKeys;
+    expectedKeys.insert(fromjson("{'': 1}"));
+    ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys));
+
+    genKeysFrom = fromjson("{a:[[1]]}");
+    expectedKeys.clear();
+    expectedKeys.insert(fromjson("{'': [1]}"));
+    ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys));
+
+    genKeysFrom = fromjson("{a:[[]]}");
+    expectedKeys.clear();
+    expectedKeys.insert(fromjson("{'': undefined}"));
+    ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys));
+
+    genKeysFrom = fromjson("{a:[[]]}");
+    expectedKeys.clear();
+    expectedKeys.insert(fromjson("{'': undefined}"));
+    ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys));
+
+    genKeysFrom = fromjson("{a:{'0':1}}");
+    expectedKeys.clear();
+    expectedKeys.insert(fromjson("{'': 1}"));
+    ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys));
+
+    genKeysFrom = fromjson("{a:[{'0':1}]}");
+    expectedKeys.clear();
+    ASSERT_THROWS(testKeygen(keyPattern, genKeysFrom, expectedKeys), UserException);
+
+    genKeysFrom = fromjson("{a:[1,{'0':2}]}");
+    ASSERT_THROWS(testKeygen(keyPattern, genKeysFrom, expectedKeys), UserException);
+}
+
+TEST(BtreeKeyGeneratorTest, GetKeysFromDoubleIndexedArrayIndex) {
+    BSONObj keyPattern = fromjson("{'a.0.0': 1}");
+    BSONObj genKeysFrom = fromjson("{a:[[1]]}");
+    BSONObjSet expectedKeys;
+    expectedKeys.insert(fromjson("{'': 1}"));
+    ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys));
+
+    genKeysFrom = fromjson("{a:[[]]}");
+    expectedKeys.clear();
+    expectedKeys.insert(fromjson("{'': null}"));
+    ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys));
+
+    genKeysFrom = fromjson("{a:[]}");
+    expectedKeys.clear();
+    expectedKeys.insert(fromjson("{'': null}"));
+    ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys));
+
+    genKeysFrom = fromjson("{a:[[[]]]}");
+    expectedKeys.clear();
+    expectedKeys.insert(fromjson("{'': undefined}"));
+    ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys));
+}
+
+TEST(BtreeKeyGeneratorTest, GetKeysFromObjectWithinArray) {
+    BSONObj keyPattern = fromjson("{'a.0.b': 1}");
+    BSONObj genKeysFrom = fromjson("{a:[{b:1}]}");
+    BSONObjSet expectedKeys;
+    expectedKeys.insert(fromjson("{'': 1}"));
+    ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys));
+
+    genKeysFrom = fromjson("{a:[{b:[1]}]}");
+    expectedKeys.clear();
+    expectedKeys.insert(fromjson("{'': 1}"));
+    ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys));
+
+    genKeysFrom = fromjson("{a:[{b:[[1]]}]}");
+    expectedKeys.clear();
+    expectedKeys.insert(fromjson("{'': [1]}"));
+    ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys));
+
+    genKeysFrom = fromjson("{a:[[{b:1}]]}");
+    expectedKeys.clear();
+    expectedKeys.insert(fromjson("{'': 1}"));
+    ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys));
+
+    genKeysFrom = fromjson("{a:[[{b:[1]}]]}");
+    expectedKeys.clear();
+    expectedKeys.insert(fromjson("{'': 1}"));
+    ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys));
+
+    genKeysFrom = fromjson("{a:[[{b:[[1]]}]]}");
+    expectedKeys.clear();
+    expectedKeys.insert(fromjson("{'': [1]}"));
+    ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys));
+
+    genKeysFrom = fromjson("{a:[[{b:[]}]]}");
+    expectedKeys.clear();
+    expectedKeys.insert(fromjson("{'': undefined}"));
+    ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys));
+}
+
+TEST(BtreeKeyGeneratorTest, GetKeysFromArrayWithinObjectWithinArray) {
+    BSONObj keyPattern = fromjson("{'a.0.b.0': 1}");
+    BSONObj genKeysFrom = fromjson("{a:[{b:[1]}]}");
+    BSONObjSet expectedKeys;
+    expectedKeys.insert(fromjson("{'': 1}"));
+    ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys));
+}
+
+TEST(BtreeKeyGeneratorTest, ParallelArraysInNestedObjects) {
+    BSONObj keyPattern = fromjson("{'a.a': 1, 'b.a': 1}");
+    BSONObj genKeysFrom = fromjson("{a:{a:[1]}, b:{a:[1]}}");
+    BSONObjSet expectedKeys;
+    ASSERT_THROWS(testKeygen(keyPattern, genKeysFrom, expectedKeys), UserException);
+}
+
+TEST(BtreeKeyGeneratorTest, ParallelArraysUneven) {
+    BSONObj keyPattern = fromjson("{'b.a': 1, 'a': 1}");
+    BSONObj genKeysFrom = fromjson("{b:{a:[1]}, a:[1,2]}");
+    BSONObjSet expectedKeys;
+    ASSERT_THROWS(testKeygen(keyPattern, genKeysFrom, expectedKeys), UserException);
+}
+
+TEST(BtreeKeyGeneratorTest, MultipleArraysNotParallel) {
+    BSONObj keyPattern = fromjson("{'a.b.c': 1}");
+    BSONObj genKeysFrom = fromjson("{a: [1, 2, {b: {c: [3, 4]}}]}");
+    BSONObjSet expectedKeys;
+    expectedKeys.insert(fromjson("{'': null}"));
+    expectedKeys.insert(fromjson("{'': 3}"));
+    expectedKeys.insert(fromjson("{'': 4}"));
+    ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys));
+}
+
+TEST(BtreeKeyGeneratorTest, MultipleArraysNotParallelCompound) {
+    BSONObj keyPattern = fromjson("{'a.b.c': 1, 'a.b.d': 1}");
+    BSONObj genKeysFrom = fromjson("{a: [1, 2, {b: {c: [3, 4], d: 5}}]}");
+    BSONObjSet expectedKeys;
+    expectedKeys.insert(fromjson("{'': null, '': null}"));
+    expectedKeys.insert(fromjson("{'': 3, '': 5}"));
+    expectedKeys.insert(fromjson("{'': 4, '': 5}"));
+    ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys));
+}
+
+TEST(BtreeKeyGeneratorTest, GetKeysComplexNestedArrays) {
+    BSONObj keyPattern = fromjson("{'a.b.c.d': 1, 'a.g': 1, 'a.b.f': 1, 'a.b.c': 1, 'a.b.e': 1}");
+    BSONObj genKeysFrom = fromjson("{a: [1, {b: [2, {c: [3, {d: 1}], e: 4}, 5, {f: 6}], g: 7}]}");
+    BSONObjSet expectedKeys;
+    expectedKeys.insert(fromjson("{'':null, '':null, '':null, '':null, '':null}"));
+    expectedKeys.insert(fromjson("{'':null, '':7, '':null, '':null, '':null}"));
+    expectedKeys.insert(fromjson("{'':null, '':7, '':null, '':3, '':4}"));
+    expectedKeys.insert(fromjson("{'':null, '':7, '':6, '':null, '':null}"));
+    expectedKeys.insert(fromjson("{'':1, '':7, '':null, '':{d: 1}, '':4}"));
+    ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys));
+}
+
+// Descriptive test. Should future index versions recursively index nested arrays?
+TEST(BtreeKeyGeneratorTest, GetKeys2DArray) {
+    BSONObj keyPattern = fromjson("{a: 1}");
+    BSONObj genKeysFrom = fromjson("{a: [[2]]}");
+    BSONObjSet expectedKeys;
+    expectedKeys.insert(fromjson("{'': [2]}"));
+    ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys));
+}
+
+// Descriptive test. Should parallel indexed arrays be allowed? If not, should empty
+// or single-element arrays be considered for the parallel array check?
+TEST(BtreeKeyGeneratorTest, GetKeysParallelEmptyArrays) {
+    BSONObj keyPattern = fromjson("{a: 1, b: 1}");
+    BSONObj genKeysFrom = fromjson("{a: [], b: []}");
+    BSONObjSet expectedKeys;
+    ASSERT_THROWS(testKeygen(keyPattern, genKeysFrom, expectedKeys), UserException);
+}
+
+TEST(BtreeKeyGeneratorTest, GetKeysParallelArraysOneArrayEmpty) {
+    BSONObj keyPattern = fromjson("{a: 1, b: 1}");
+    BSONObj genKeysFrom = fromjson("{a: [], b: [1, 2, 3]}");
+    BSONObjSet expectedKeys;
+    ASSERT_THROWS(testKeygen(keyPattern, genKeysFrom, expectedKeys), UserException);
+}
+
+TEST(BtreeKeyGeneratorTest, GetKeysParallelArraysOneArrayEmptyNested) {
+    BSONObj keyPattern = fromjson("{'a.b.c': 1, 'a.b.d': 1}");
+    BSONObj genKeysFrom = fromjson("{a: [{b: [{c: [1, 2, 3], d: []}]}]}");
+    BSONObjSet expectedKeys;
+    ASSERT_THROWS(testKeygen(keyPattern, genKeysFrom, expectedKeys), UserException);
+}
+
+// Descriptive test. The semantics for key generation are odd for positional key patterns.
+TEST(BtreeKeyGeneratorTest, GetKeysPositionalKeyPatternMissingElement) {
+    BSONObj keyPattern = fromjson("{'a.2': 1}");
+    BSONObj genKeysFrom = fromjson("{a: [{'2': 5}]}");
+    BSONObjSet expectedKeys;
+    expectedKeys.insert(fromjson("{'': 5}"));
+    ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys));
+}
+
+// Descriptive test. The semantics for key generation are odd for positional key patterns.
+TEST(BtreeKeyGeneratorTest, GetKeysPositionalKeyPatternNestedArray) {
+    BSONObj keyPattern = fromjson("{'a.2': 1}");
+    BSONObj genKeysFrom = fromjson("{a: [[1, 2, 5]]}");
+    BSONObjSet expectedKeys;
+    expectedKeys.insert(fromjson("{'': null}"));
+    ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys));
+}
+
+// Descriptive test. The semantics for key generation are odd for positional key patterns.
+TEST(BtreeKeyGeneratorTest, GetKeysPositionalKeyPatternNestedArray2) {
+    BSONObj keyPattern = fromjson("{'a.2': 1}");
+    BSONObj genKeysFrom = fromjson("{a: [[1, 2, 5], [3, 4, 6], [0, 1, 2]]}");
+    BSONObjSet expectedKeys;
+    expectedKeys.insert(fromjson("{'': [0, 1, 2]}"));
+    ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys));
+}
+
+// Descriptive test. The semantics for key generation are odd for positional key patterns.
+TEST(BtreeKeyGeneratorTest, GetKeysPositionalKeyPatternNestedArray3) {
+    BSONObj keyPattern = fromjson("{'a.2': 1}");
+    BSONObj genKeysFrom = fromjson("{a: [{'0': 1, '1': 2, '2': 5}]}");
+    BSONObjSet expectedKeys;
+    expectedKeys.insert(fromjson("{'': 5}"));
+    ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys));
+}
+
+// Descriptive test. The semantics for key generation are odd for positional key patterns.
+TEST(BtreeKeyGeneratorTest, GetKeysPositionalKeyPatternNestedArray4) {
+    BSONObj keyPattern = fromjson("{'a.b.2': 1}");
+    BSONObj genKeysFrom = fromjson("{a: [{b: [[1, 2, 5]]}]}");
+    BSONObjSet expectedKeys;
+    expectedKeys.insert(fromjson("{'': null}"));
+    ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys));
+}
+
+// Descriptive test. The semantics for key generation are odd for positional key patterns.
+TEST(BtreeKeyGeneratorTest, GetKeysPositionalKeyPatternNestedArray5) {
+    BSONObj keyPattern = fromjson("{'a.2': 1}");
+    BSONObj genKeysFrom = fromjson("{a: [[1, 2, 5], {'2': 6}]}");
+    BSONObjSet expectedKeys;
+    expectedKeys.insert(fromjson("{'': null}"));
+    expectedKeys.insert(fromjson("{'': 6}"));
+    ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys));
+}
+
+TEST(BtreeKeyGeneratorTest, GetNullKeyNestedArray) {
+    BSONObj keyPattern = fromjson("{'a.b': 1}");
+    BSONObj genKeysFrom = fromjson("{a: [[1, 2, 5]]}");
+    BSONObjSet expectedKeys;
+    expectedKeys.insert(fromjson("{'': null}"));
+    ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys));
+}
+
+TEST(BtreeKeyGeneratorTest, GetKeysUnevenNestedArrays) {
+    BSONObj keyPattern = fromjson("{a: 1, 'a.b': 1}");
+    BSONObj genKeysFrom = fromjson("{a: [1, {b: [2, 3, 4]}]}");
+    BSONObjSet expectedKeys;
+    expectedKeys.insert(fromjson("{'': 1, '': null}"));
+    expectedKeys.insert(fromjson("{'': {b:[2,3,4]}, '': 2}"));
+    expectedKeys.insert(fromjson("{'': {b:[2,3,4]}, '': 3}"));
+    expectedKeys.insert(fromjson("{'': {b:[2,3,4]}, '': 4}"));
+    ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys));
+}
+
+// Descriptive test. Should we define better semantics for future index versions in the case of
+// repeated field names?
+TEST(BtreeKeyGeneratorTest, GetKeysRepeatedFieldName) {
+    BSONObj keyPattern = fromjson("{a: 1}");
+    BSONObj genKeysFrom = fromjson("{a: 2, a: 3}");
+    BSONObjSet expectedKeys;
+    expectedKeys.insert(fromjson("{'': 2}"));
+    ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys));
+}
+
+// Descriptive test. Future index versions may want different or at least more consistent
+// handling of empty path components.
+TEST(BtreeKeyGeneratorTest, GetKeysEmptyPathPiece) {
+    BSONObj keyPattern = fromjson("{'a..c': 1}");
+    BSONObj genKeysFrom = fromjson("{a: {'': [{c: 1}, {c: 2}]}}");
+    BSONObjSet expectedKeys;
+    expectedKeys.insert(fromjson("{'': 1}"));
+    expectedKeys.insert(fromjson("{'': 2}"));
+    ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys));
+}
+
+// Descriptive test. Future index versions may want different or at least more consistent
+// handling of empty path components.
+TEST(BtreeKeyGeneratorTest, GetKeysLastPathPieceEmpty) {
+    BSONObj keyPattern = fromjson("{'a.': 1}");
+
+    BSONObj genKeysFrom = fromjson("{a: 2}");
+    BSONObjSet expectedKeys;
+    expectedKeys.insert(fromjson("{'': 2}"));
+    ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys));
+
+    genKeysFrom = fromjson("{a: {'': 2}}");
+    expectedKeys.clear();
+    expectedKeys.insert(fromjson("{'': {'': 2}}"));
+    ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys));
+}
+
+TEST(BtreeKeyGeneratorTest, GetKeysFirstPathPieceEmpty) {
+    BSONObj keyPattern = fromjson("{'.a': 1}");
+    BSONObj genKeysFrom = fromjson("{a: 2}");
+    BSONObjSet expectedKeys;
+    expectedKeys.insert(fromjson("{'': null}"));
+    ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys));
+}
+
+TEST(BtreeKeyGeneratorTest, GetKeysFirstPathPieceEmpty2) {
+    BSONObj keyPattern = fromjson("{'.a': 1}");
+    BSONObj genKeysFrom = fromjson("{'': [{a: [1, 2, 3]}]}");
+    BSONObjSet expectedKeys;
+    expectedKeys.insert(fromjson("{'': 1}"));
+    expectedKeys.insert(fromjson("{'': 2}"));
+    expectedKeys.insert(fromjson("{'': 3}"));
+    ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys));
+}
+
+TEST(BtreeKeyGeneratorTest, PositionalKeyPatternParallelArrays) {
+    BSONObj keyPattern = fromjson("{a: 1, 'b.0': 1}");
+    BSONObj genKeysFrom = fromjson("{a: [1], b: [2]}");
+    BSONObjSet expectedKeys;
+    ASSERT_THROWS(testKeygen(keyPattern, genKeysFrom, expectedKeys), UserException);
+}
+
+// Descriptive test.
+TEST(BtreeKeyGeneratorTest, PositionalKeyPatternNestedArrays) {
+    BSONObj keyPattern = fromjson("{'a.0.b': 1}");
+    BSONObj genKeysFrom = fromjson("{a: [[{b: 1}]]}");
+    BSONObjSet expectedKeys;
+    expectedKeys.insert(fromjson("{'': 1}"));
+    ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys));
+}
+
+// Descriptive test.
+TEST(BtreeKeyGeneratorTest, PositionalKeyPatternNestedArrays2) {
+    BSONObj keyPattern = fromjson("{'a.0.0.b': 1}");
+    BSONObj genKeysFrom = fromjson("{a: [[{b: 1}]]}");
+    BSONObjSet expectedKeys;
+    expectedKeys.insert(fromjson("{'': 1}"));
+    ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys));
+}
+
+// Descriptive test.
+TEST(BtreeKeyGeneratorTest, PositionalKeyPatternNestedArrays3) {
+    BSONObj keyPattern = fromjson("{'a.0.0.b': 1}");
+    BSONObj genKeysFrom = fromjson("{a: [[[ {b: 1} ]]]}");
+    BSONObjSet expectedKeys;
+    expectedKeys.insert(fromjson("{'': 1}"));
+    ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys));
+}
+
+// Descriptive test.
+TEST(BtreeKeyGeneratorTest, PositionalKeyPatternNestedArrays4) {
+    BSONObj keyPattern = fromjson("{'a.0.0.b': 1}");
+    BSONObj genKeysFrom = fromjson("{a: [[[[ {b: 1} ]]]]}");
+    BSONObjSet expectedKeys;
+    expectedKeys.insert(fromjson("{'': null}"));
+    ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys));
+}
+
+TEST(BtreeKeyGeneratorTest, PositionalKeyPatternNestedArrays5) {
+    BSONObj keyPattern = fromjson("{'a.b.1': 1}");
+    BSONObj genKeysFrom = fromjson("{a: [{b: [1, 2]}]}");
+    BSONObjSet expectedKeys;
+    expectedKeys.insert(fromjson("{'': 2}"));
+    ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys));
+}
+
+// Descriptive test.
+TEST(BtreeKeyGeneratorTest, PositionalKeyPatternNestedArrays6) {
+    BSONObj keyPattern = fromjson("{'a': 1, 'a.b': 1, 'a.0.b':1, 'a.b.0': 1, 'a.0.b.0': 1}");
+    BSONObj genKeysFrom = fromjson("{a: [{b: [1,2]}, {b: 3}]}");
+    BSONObjSet expectedKeys;
+    expectedKeys.insert(fromjson("{'': {b:3}, '': 3, '': 1, '': null, '': 1}"));
+    expectedKeys.insert(fromjson("{'': {b:3}, '': 3, '': 2, '': null, '': 1}"));
+    expectedKeys.insert(fromjson("{'': {b:[1,2]}, '': 1, '': 1, '': 1, '': 1}"));
+    expectedKeys.insert(fromjson("{'': {b:[1,2]}, '': 2, '': 2, '': 1, '': 1}"));
+    ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys));
+}
+
+// Descriptive test.
+TEST(BtreeKeyGeneratorTest, PositionalKeyPatternNestedArrays7) {
+    BSONObj keyPattern = fromjson("{'a': 1, 'a.b': 1, 'a.0.b':1, 'a.b.0': 1, 'a.0.b.0': 1}");
+    BSONObj genKeysFrom = fromjson("{a: [{b: [1,2]}, {b: {'0': 3}}]}");
+    BSONObjSet expectedKeys;
+    expectedKeys.insert(fromjson("{'': {b:{'0':3}}, '': {'0':3}, '': 1, '': 3, '': 1}"));
+    expectedKeys.insert(fromjson("{'': {b:{'0':3}}, '': {'0':3}, '': 2, '': 3, '': 1}"));
+    expectedKeys.insert(fromjson("{'': {b:[1,2]}, '': 1, '': 1, '': 1, '': 1}"));
+    expectedKeys.insert(fromjson("{'': {b:[1,2]}, '': 2, '': 2, '': 1, '': 1}"));
+    ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys));
+}
+
+}  // namespace
diff --git a/src/mongo/db/index/expression_keys_private.cpp b/src/mongo/db/index/expression_keys_private.cpp
index 1202b77ce0f..559175444bf 100644
--- a/src/mongo/db/index/expression_keys_private.cpp
+++ b/src/mongo/db/index/expression_keys_private.cpp
@@ -48,471 +48,475 @@
 
 namespace {
 
-    using namespace mongo;
-
-    //
-    // Helper functions for getHaystackKeys
-    //
-
-    /**
-     * Build a new BSONObj with root in it.  If e is non-empty, append that to the key.
-     * Insert the BSONObj into keys.
-     * Used by getHaystackKeys.
-     */
-    void addKey(const string& root, const BSONElement& e, BSONObjSet* keys) {
-        BSONObjBuilder buf;
-        buf.append("", root);
-
-        if (e.eoo())
-            buf.appendNull("");
-        else
-            buf.appendAs(e, "");
-
-        keys->insert(buf.obj());
-    }
+using namespace mongo;
 
-    //
-    // Helper functions for getS2Keys
-    //
+//
+// Helper functions for getHaystackKeys
+//
 
-    static void S2KeysFromRegion(S2RegionCoverer *coverer, const S2Region &region,
-                               vector<string> *out) {
-        vector<S2CellId> covering;
-        coverer->GetCovering(region, &covering);
-        for (size_t i = 0; i < covering.size(); ++i) {
-            out->push_back(covering[i].toString());
-        }
+/**
+ * Build a new BSONObj with root in it.  If e is non-empty, append that to the key.
+ * Insert the BSONObj into keys.
+ * Used by getHaystackKeys.
+ */
+void addKey(const string& root, const BSONElement& e, BSONObjSet* keys) {
+    BSONObjBuilder buf;
+    buf.append("", root);
+
+    if (e.eoo())
+        buf.appendNull("");
+    else
+        buf.appendAs(e, "");
+
+    keys->insert(buf.obj());
+}
+
+//
+// Helper functions for getS2Keys
+//
+
+static void S2KeysFromRegion(S2RegionCoverer* coverer,
+                             const S2Region& region,
+                             vector<string>* out) {
+    vector<S2CellId> covering;
+    coverer->GetCovering(region, &covering);
+    for (size_t i = 0; i < covering.size(); ++i) {
+        out->push_back(covering[i].toString());
     }
+}
 
 
-    Status S2GetKeysForElement(const BSONElement& element,
-                            const S2IndexingParams& params,
-                            vector<string>* out) {
-        GeometryContainer geoContainer;
-        Status status = geoContainer.parseFromStorage(element);
-        if (!status.isOK()) return status;
-
-        S2RegionCoverer coverer;
-        params.configureCoverer(&coverer);
+Status S2GetKeysForElement(const BSONElement& element,
+                           const S2IndexingParams& params,
+                           vector<string>* out) {
+    GeometryContainer geoContainer;
+    Status status = geoContainer.parseFromStorage(element);
+    if (!status.isOK())
+        return status;
 
-        // Don't index big polygon
-        if (geoContainer.getNativeCRS() == STRICT_SPHERE) {
-            return Status(ErrorCodes::BadValue, "can't index geometry with strict winding order");
-        }
+    S2RegionCoverer coverer;
+    params.configureCoverer(&coverer);
 
-        // Only certain geometries can be indexed in the old index format S2_INDEX_VERSION_1.  See
-        // definition of S2IndexVersion for details.
-        if (params.indexVersion == S2_INDEX_VERSION_1 && !geoContainer.isSimpleContainer()) {
-            return Status(ErrorCodes::BadValue,
-                          str::stream()
-                                  << "given geometry can't be indexed in the old index format");
-        }
-
-        // Project the geometry into spherical space
-        if (!geoContainer.supportsProject(SPHERE)) {
-            return Status(ErrorCodes::BadValue,
-                          str::stream() << "can't project geometry into spherical CRS: "
-                                        << element.toString(false));
-        }
-        geoContainer.projectInto(SPHERE);
-
-        invariant(geoContainer.hasS2Region());
+    // Don't index big polygon
+    if (geoContainer.getNativeCRS() == STRICT_SPHERE) {
+        return Status(ErrorCodes::BadValue, "can't index geometry with strict winding order");
+    }
 
-        S2KeysFromRegion(&coverer, geoContainer.getS2Region(), out);
-        return Status::OK();
+    // Only certain geometries can be indexed in the old index format S2_INDEX_VERSION_1.  See
+    // definition of S2IndexVersion for details.
+    if (params.indexVersion == S2_INDEX_VERSION_1 && !geoContainer.isSimpleContainer()) {
+        return Status(ErrorCodes::BadValue,
+                      str::stream() << "given geometry can't be indexed in the old index format");
     }
 
+    // Project the geometry into spherical space
+    if (!geoContainer.supportsProject(SPHERE)) {
+        return Status(ErrorCodes::BadValue,
+                      str::stream() << "can't project geometry into spherical CRS: "
+                                    << element.toString(false));
+    }
+    geoContainer.projectInto(SPHERE);
 
-    /**
-     *  Get the index keys for elements that are GeoJSON.
-     *  Used by getS2Keys.
-     */
-    void getS2GeoKeys(const BSONObj& document, const BSONElementSet& elements,
-                                    const S2IndexingParams& params,
-                                    BSONObjSet* out) {
-        for (BSONElementSet::iterator i = elements.begin(); i != elements.end(); ++i) {
-            vector<string> cells;
-            Status status = S2GetKeysForElement(*i, params, &cells);
-            uassert(16755, str::stream() << "Can't extract geo keys: " << document << "  "
-                    << status.reason(), status.isOK());
+    invariant(geoContainer.hasS2Region());
 
-            uassert(16756, "Unable to generate keys for (likely malformed) geometry: "
-                    + document.toString(),
-                    cells.size() > 0);
+    S2KeysFromRegion(&coverer, geoContainer.getS2Region(), out);
+    return Status::OK();
+}
 
-            for (vector<string>::const_iterator it = cells.begin(); it != cells.end(); ++it) {
-                BSONObjBuilder b;
-                b.append("", *it);
-                out->insert(b.obj());
-            }
-        }
 
-        if (0 == out->size()) {
+/**
+ *  Get the index keys for elements that are GeoJSON.
+ *  Used by getS2Keys.
+ */
+void getS2GeoKeys(const BSONObj& document,
+                  const BSONElementSet& elements,
+                  const S2IndexingParams& params,
+                  BSONObjSet* out) {
+    for (BSONElementSet::iterator i = elements.begin(); i != elements.end(); ++i) {
+        vector<string> cells;
+        Status status = S2GetKeysForElement(*i, params, &cells);
+        uassert(16755,
+                str::stream() << "Can't extract geo keys: " << document << "  " << status.reason(),
+                status.isOK());
+
+        uassert(16756,
+                "Unable to generate keys for (likely malformed) geometry: " + document.toString(),
+                cells.size() > 0);
+
+        for (vector<string>::const_iterator it = cells.begin(); it != cells.end(); ++it) {
             BSONObjBuilder b;
-            b.appendNull("");
+            b.append("", *it);
             out->insert(b.obj());
         }
     }
 
-    /**
-     * Expands array and appends items to 'out'.
-     * Used by getOneLiteralKey.
-     */
-    void getS2LiteralKeysArray(const BSONObj& obj, BSONObjSet* out) {
-        BSONObjIterator objIt(obj);
-        if (!objIt.more()) {
-            // Empty arrays are indexed as undefined.
-            BSONObjBuilder b;
-            b.appendUndefined("");
-            out->insert(b.obj());
-        } else {
-            // Non-empty arrays are exploded.
-            while (objIt.more()) {
-                BSONObjBuilder b;
-                b.appendAs(objIt.next(), "");
-                out->insert(b.obj());
-            }
-        }
+    if (0 == out->size()) {
+        BSONObjBuilder b;
+        b.appendNull("");
+        out->insert(b.obj());
     }
+}
 
-    /**
-     * If 'elt' is an array, expands elt and adds items to 'out'.
-     * Otherwise, adds 'elt' as a single element.
-     * Used by getLiteralKeys.
-     */
-    void getS2OneLiteralKey(const BSONElement& elt, BSONObjSet* out) {
-        if (Array == elt.type()) {
-            getS2LiteralKeysArray(elt.Obj(), out);
-        } else {
-            // One thing, not an array, index as-is.
+/**
+ * Expands array and appends items to 'out'.
+ * Used by getOneLiteralKey.
+ */
+void getS2LiteralKeysArray(const BSONObj& obj, BSONObjSet* out) {
+    BSONObjIterator objIt(obj);
+    if (!objIt.more()) {
+        // Empty arrays are indexed as undefined.
+        BSONObjBuilder b;
+        b.appendUndefined("");
+        out->insert(b.obj());
+    } else {
+        // Non-empty arrays are exploded.
+        while (objIt.more()) {
             BSONObjBuilder b;
-            b.appendAs(elt, "");
+            b.appendAs(objIt.next(), "");
             out->insert(b.obj());
         }
     }
+}
 
-    /**
-     * elements is a non-geo field.  Add the values literally, expanding arrays.
-     * Used by getS2Keys.
-     */
-    void getS2LiteralKeys(const BSONElementSet& elements, BSONObjSet* out) {
-        if (0 == elements.size()) {
-            // Missing fields are indexed as null.
-            BSONObjBuilder b;
-            b.appendNull("");
-            out->insert(b.obj());
-        } else {
-            for (BSONElementSet::iterator i = elements.begin(); i != elements.end(); ++i) {
-                getS2OneLiteralKey(*i, out);
-            }
+/**
+ * If 'elt' is an array, expands elt and adds items to 'out'.
+ * Otherwise, adds 'elt' as a single element.
+ * Used by getLiteralKeys.
+ */
+void getS2OneLiteralKey(const BSONElement& elt, BSONObjSet* out) {
+    if (Array == elt.type()) {
+        getS2LiteralKeysArray(elt.Obj(), out);
+    } else {
+        // One thing, not an array, index as-is.
+        BSONObjBuilder b;
+        b.appendAs(elt, "");
+        out->insert(b.obj());
+    }
+}
+
+/**
+ * elements is a non-geo field.  Add the values literally, expanding arrays.
+ * Used by getS2Keys.
+ */
+void getS2LiteralKeys(const BSONElementSet& elements, BSONObjSet* out) {
+    if (0 == elements.size()) {
+        // Missing fields are indexed as null.
+        BSONObjBuilder b;
+        b.appendNull("");
+        out->insert(b.obj());
+    } else {
+        for (BSONElementSet::iterator i = elements.begin(); i != elements.end(); ++i) {
+            getS2OneLiteralKey(*i, out);
         }
     }
+}
 
-} // namespace
+}  // namespace
 
 namespace mongo {
 
-    using std::pair;
-    using std::string;
-    using std::vector;
-
-    // static
-    void ExpressionKeysPrivate::get2DKeys(const BSONObj &obj,
-                                         const TwoDIndexingParams& params,
-                                         BSONObjSet* keys,
-                                         std::vector<BSONObj>* locs) {
-        BSONElementMSet bSet;
+using std::pair;
+using std::string;
+using std::vector;
 
-        // Get all the nested location fields, but don't return individual elements from
-        // the last array, if it exists.
-        obj.getFieldsDotted(params.geo.c_str(), bSet, false);
+// static
+void ExpressionKeysPrivate::get2DKeys(const BSONObj& obj,
+                                      const TwoDIndexingParams& params,
+                                      BSONObjSet* keys,
+                                      std::vector<BSONObj>* locs) {
+    BSONElementMSet bSet;
 
-        if (bSet.empty())
-            return;
+    // Get all the nested location fields, but don't return individual elements from
+    // the last array, if it exists.
+    obj.getFieldsDotted(params.geo.c_str(), bSet, false);
 
-        for (BSONElementMSet::iterator setI = bSet.begin(); setI != bSet.end(); ++setI) {
-            BSONElement geo = *setI;
+    if (bSet.empty())
+        return;
 
-            if (geo.eoo() || !geo.isABSONObj())
-                continue;
+    for (BSONElementMSet::iterator setI = bSet.begin(); setI != bSet.end(); ++setI) {
+        BSONElement geo = *setI;
 
-            //
-            // Grammar for location lookup:
-            // locs ::= [loc,loc,...,loc]|{<k>:loc,<k>:loc,...,<k>:loc}|loc
-            // loc  ::= { <k1> : #, <k2> : # }|[#, #]|{}
-            //
-            // Empty locations are ignored, preserving single-location semantics
-            //
+        if (geo.eoo() || !geo.isABSONObj())
+            continue;
 
-            BSONObj embed = geo.embeddedObject();
-            if (embed.isEmpty())
-                continue;
+        //
+        // Grammar for location lookup:
+        // locs ::= [loc,loc,...,loc]|{<k>:loc,<k>:loc,...,<k>:loc}|loc
+        // loc  ::= { <k1> : #, <k2> : # }|[#, #]|{}
+        //
+        // Empty locations are ignored, preserving single-location semantics
+        //
 
-            // Differentiate between location arrays and locations
-            // by seeing if the first element value is a number
-            bool singleElement = embed.firstElement().isNumber();
+        BSONObj embed = geo.embeddedObject();
+        if (embed.isEmpty())
+            continue;
 
-            BSONObjIterator oi(embed);
+        // Differentiate between location arrays and locations
+        // by seeing if the first element value is a number
+        bool singleElement = embed.firstElement().isNumber();
 
-            while (oi.more()) {
-                BSONObj locObj;
+        BSONObjIterator oi(embed);
 
-                if (singleElement) {
-                    locObj = embed;
-                } else {
-                    BSONElement locElement = oi.next();
+        while (oi.more()) {
+            BSONObj locObj;
 
-                    uassert(16804, mongoutils::str::stream() <<
-                            "location object expected, location array not in correct format",
-                            locElement.isABSONObj());
+            if (singleElement) {
+                locObj = embed;
+            } else {
+                BSONElement locElement = oi.next();
 
-                    locObj = locElement.embeddedObject();
-                    if(locObj.isEmpty())
-                        continue;
-                }
+                uassert(16804,
+                        mongoutils::str::stream()
+                            << "location object expected, location array not in correct format",
+                        locElement.isABSONObj());
 
-                BSONObjBuilder b(64);
+                locObj = locElement.embeddedObject();
+                if (locObj.isEmpty())
+                    continue;
+            }
 
-                // Remember the actual location object if needed
-                if (locs)
-                    locs->push_back(locObj);
+            BSONObjBuilder b(64);
 
-                // Stop if we don't need to get anything but location objects
-                if (!keys) {
-                    if (singleElement) break;
-                    else continue;
-                }
+            // Remember the actual location object if needed
+            if (locs)
+                locs->push_back(locObj);
 
-                params.geoHashConverter->hash(locObj, &obj).appendHashMin(&b, "");
-
-                // Go through all the other index keys
-                for (vector<pair<string, int> >::const_iterator i = params.other.begin();
-                     i != params.other.end(); ++i) {
-                    // Get *all* fields for the index key
-                    BSONElementSet eSet;
-                    obj.getFieldsDotted(i->first, eSet);
-
-                    if (eSet.size() == 0)
-                        b.appendNull("");
-                    else if (eSet.size() == 1)
-                        b.appendAs(*(eSet.begin()), "");
-                    else {
-                        // If we have more than one key, store as an array of the objects
-                        BSONArrayBuilder aBuilder;
-
-                        for (BSONElementSet::iterator ei = eSet.begin(); ei != eSet.end();
-                             ++ei) {
-                            aBuilder.append(*ei);
-                        }
+            // Stop if we don't need to get anything but location objects
+            if (!keys) {
+                if (singleElement)
+                    break;
+                else
+                    continue;
+            }
 
-                        b.append("", aBuilder.arr());
+            params.geoHashConverter->hash(locObj, &obj).appendHashMin(&b, "");
+
+            // Go through all the other index keys
+            for (vector<pair<string, int>>::const_iterator i = params.other.begin();
+                 i != params.other.end();
+                 ++i) {
+                // Get *all* fields for the index key
+                BSONElementSet eSet;
+                obj.getFieldsDotted(i->first, eSet);
+
+                if (eSet.size() == 0)
+                    b.appendNull("");
+                else if (eSet.size() == 1)
+                    b.appendAs(*(eSet.begin()), "");
+                else {
+                    // If we have more than one key, store as an array of the objects
+                    BSONArrayBuilder aBuilder;
+
+                    for (BSONElementSet::iterator ei = eSet.begin(); ei != eSet.end(); ++ei) {
+                        aBuilder.append(*ei);
                     }
+
+                    b.append("", aBuilder.arr());
                 }
-                keys->insert(b.obj());
-                if(singleElement) break;
             }
+            keys->insert(b.obj());
+            if (singleElement)
+                break;
         }
     }
-
-    // static
-    void ExpressionKeysPrivate::getFTSKeys(const BSONObj &obj,
-                                           const fts::FTSSpec& ftsSpec,
-                                           BSONObjSet* keys) {
-        fts::FTSIndexFormat::getKeys(ftsSpec, obj, keys);
+}
+
+// static
+void ExpressionKeysPrivate::getFTSKeys(const BSONObj& obj,
+                                       const fts::FTSSpec& ftsSpec,
+                                       BSONObjSet* keys) {
+    fts::FTSIndexFormat::getKeys(ftsSpec, obj, keys);
+}
+
+// static
+void ExpressionKeysPrivate::getHashKeys(const BSONObj& obj,
+                                        const string& hashedField,
+                                        HashSeed seed,
+                                        int hashVersion,
+                                        bool isSparse,
+                                        BSONObjSet* keys) {
+    const char* cstr = hashedField.c_str();
+    BSONElement fieldVal = obj.getFieldDottedOrArray(cstr);
+    uassert(16766,
+            "Error: hashed indexes do not currently support array values",
+            fieldVal.type() != Array);
+
+    if (!fieldVal.eoo()) {
+        BSONObj key = BSON("" << makeSingleHashKey(fieldVal, seed, hashVersion));
+        keys->insert(key);
+    } else if (!isSparse) {
+        BSONObj nullObj = BSON("" << BSONNULL);
+        keys->insert(BSON("" << makeSingleHashKey(nullObj.firstElement(), seed, hashVersion)));
     }
-
-    // static
-    void ExpressionKeysPrivate::getHashKeys(const BSONObj& obj,
-                                            const string& hashedField,
-                                            HashSeed seed,
-                                            int hashVersion,
-                                            bool isSparse,
+}
+
+// static
+long long int ExpressionKeysPrivate::makeSingleHashKey(const BSONElement& e, HashSeed seed, int v) {
+    massert(16767, "Only HashVersion 0 has been defined", v == 0);
+    return BSONElementHasher::hash64(e, seed);
+}
+
+// static
+void ExpressionKeysPrivate::getHaystackKeys(const BSONObj& obj,
+                                            const std::string& geoField,
+                                            const std::vector<std::string>& otherFields,
+                                            double bucketSize,
                                             BSONObjSet* keys) {
+    BSONElement loc = obj.getFieldDotted(geoField);
 
-        const char* cstr = hashedField.c_str();
-        BSONElement fieldVal = obj.getFieldDottedOrArray(cstr);
-        uassert(16766, "Error: hashed indexes do not currently support array values",
-                fieldVal.type() != Array );
-
-        if (!fieldVal.eoo()) {
-            BSONObj key = BSON( "" << makeSingleHashKey(fieldVal, seed, hashVersion));
-            keys->insert(key);
-        }
-        else if (!isSparse) {
-            BSONObj nullObj = BSON("" << BSONNULL);
-            keys->insert(BSON("" << makeSingleHashKey(nullObj.firstElement(), seed, hashVersion)));
-        }
+    if (loc.eoo()) {
+        return;
     }
 
-    // static
-    long long int ExpressionKeysPrivate::makeSingleHashKey(const BSONElement& e,
-                                                           HashSeed seed,
-                                                           int v) {
-        massert(16767, "Only HashVersion 0 has been defined" , v == 0 );
-        return BSONElementHasher::hash64(e, seed);
-    }
-
-    // static
-    void ExpressionKeysPrivate::getHaystackKeys(const BSONObj& obj,
-                                                const std::string& geoField,
-                                                const std::vector<std::string>& otherFields,
-                                                double bucketSize,
-                                                BSONObjSet* keys) {
-
-        BSONElement loc = obj.getFieldDotted(geoField);
-
-        if (loc.eoo()) { return; }
-
-        // NOTE: We explicitly test nFields >= 2 to support legacy users who may have indexed
-        // (intentionally or unintentionally) objects/arrays with more than two fields.
-        uassert(16775, str::stream() << "cannot extract [lng, lat] array or object from " << obj,
+    // NOTE: We explicitly test nFields >= 2 to support legacy users who may have indexed
+    // (intentionally or unintentionally) objects/arrays with more than two fields.
+    uassert(16775,
+            str::stream() << "cannot extract [lng, lat] array or object from " << obj,
             loc.isABSONObj() && loc.Obj().nFields() >= 2);
 
-        string root;
-        {
-            BSONObjIterator i(loc.Obj());
-            BSONElement x = i.next();
-            BSONElement y = i.next();
-            root = makeHaystackString(hashHaystackElement(x, bucketSize),
-                                      hashHaystackElement(y, bucketSize));
-        }
-
-        verify(otherFields.size() == 1);
-
-        BSONElementSet all;
-
-        // This is getFieldsDotted (plural not singular) since the object we're indexing
-        // may be an array.
-        obj.getFieldsDotted(otherFields[0], all);
-
-        if (all.size() == 0) {
-            // We're indexing a document that doesn't have the secondary non-geo field present.
-            // XXX: do we want to add this even if all.size() > 0?  result:empty search terms
-            // match everything instead of only things w/empty search terms)
-            addKey(root, BSONElement(), keys);
-        } else {
-            // Ex:If our secondary field is type: "foo" or type: {a:"foo", b:"bar"},
-            // all.size()==1.  We can query on the complete field.
-            // Ex: If our secondary field is type: ["A", "B"] all.size()==2 and all has values
-            // "A" and "B".  The query looks for any of the fields in the array.
-            for (BSONElementSet::iterator i = all.begin(); i != all.end(); ++i) {
-                addKey(root, *i, keys);
-            }
-        }
-    }
-
-    // static
-    int ExpressionKeysPrivate::hashHaystackElement(const BSONElement& e, double bucketSize) {
-        uassert(16776, "geo field is not a number", e.isNumber());
-        double d = e.numberDouble();
-        d += 180;
-        d /= bucketSize;
-        return static_cast<int>(d);
+    string root;
+    {
+        BSONObjIterator i(loc.Obj());
+        BSONElement x = i.next();
+        BSONElement y = i.next();
+        root = makeHaystackString(hashHaystackElement(x, bucketSize),
+                                  hashHaystackElement(y, bucketSize));
     }
 
-    // static
-    std::string ExpressionKeysPrivate::makeHaystackString(int hashedX, int hashedY) {
-        mongoutils::str::stream ss;
-        ss << hashedX << "_" << hashedY;
-        return ss;
+    verify(otherFields.size() == 1);
+
+    BSONElementSet all;
+
+    // This is getFieldsDotted (plural not singular) since the object we're indexing
+    // may be an array.
+    obj.getFieldsDotted(otherFields[0], all);
+
+    if (all.size() == 0) {
+        // We're indexing a document that doesn't have the secondary non-geo field present.
+        // XXX: do we want to add this even if all.size() > 0?  result:empty search terms
+        // match everything instead of only things w/empty search terms)
+        addKey(root, BSONElement(), keys);
+    } else {
+        // Ex:If our secondary field is type: "foo" or type: {a:"foo", b:"bar"},
+        // all.size()==1.  We can query on the complete field.
+        // Ex: If our secondary field is type: ["A", "B"] all.size()==2 and all has values
+        // "A" and "B".  The query looks for any of the fields in the array.
+        for (BSONElementSet::iterator i = all.begin(); i != all.end(); ++i) {
+            addKey(root, *i, keys);
+        }
     }
-
-    void ExpressionKeysPrivate::getS2Keys(const BSONObj& obj,
-                                          const BSONObj& keyPattern,
-                                          const S2IndexingParams& params,
-                                          BSONObjSet* keys) {
-        BSONObjSet keysToAdd;
-
-        // Does one of our documents have a geo field?
-        bool haveGeoField = false;
-
-        // We output keys in the same order as the fields we index.
-        BSONObjIterator i(keyPattern);
-        while (i.more()) {
-            BSONElement e = i.next();
-
-            // First, we get the keys that this field adds.  Either they're added literally from
-            // the value of the field, or they're transformed if the field is geo.
-            BSONElementSet fieldElements;
-            // false means Don't expand the last array, duh.
-            obj.getFieldsDotted(e.fieldName(), fieldElements, false);
-
-            BSONObjSet keysForThisField;
-            if (IndexNames::GEO_2DSPHERE == e.valuestr()) {
-                if (S2_INDEX_VERSION_2 == params.indexVersion) {
-                    // For V2,
-                    // geo: null,
-                    // geo: undefined
-                    // geo: [] 
-                    // should all behave like there is no geo field.  So we look for these cases and
-                    // throw out the field elements if we find them.
-                    if (1 == fieldElements.size()) {
-                        BSONElement elt = *fieldElements.begin();
-                        // Get the :null and :undefined cases.
-                        if (elt.isNull() || Undefined == elt.type()) {
+}
+
+// static
+int ExpressionKeysPrivate::hashHaystackElement(const BSONElement& e, double bucketSize) {
+    uassert(16776, "geo field is not a number", e.isNumber());
+    double d = e.numberDouble();
+    d += 180;
+    d /= bucketSize;
+    return static_cast<int>(d);
+}
+
+// static
+std::string ExpressionKeysPrivate::makeHaystackString(int hashedX, int hashedY) {
+    mongoutils::str::stream ss;
+    ss << hashedX << "_" << hashedY;
+    return ss;
+}
+
+void ExpressionKeysPrivate::getS2Keys(const BSONObj& obj,
+                                      const BSONObj& keyPattern,
+                                      const S2IndexingParams& params,
+                                      BSONObjSet* keys) {
+    BSONObjSet keysToAdd;
+
+    // Does one of our documents have a geo field?
+    bool haveGeoField = false;
+
+    // We output keys in the same order as the fields we index.
+    BSONObjIterator i(keyPattern);
+    while (i.more()) {
+        BSONElement e = i.next();
+
+        // First, we get the keys that this field adds.  Either they're added literally from
+        // the value of the field, or they're transformed if the field is geo.
+        BSONElementSet fieldElements;
+        // false means Don't expand the last array, duh.
+        obj.getFieldsDotted(e.fieldName(), fieldElements, false);
+
+        BSONObjSet keysForThisField;
+        if (IndexNames::GEO_2DSPHERE == e.valuestr()) {
+            if (S2_INDEX_VERSION_2 == params.indexVersion) {
+                // For V2,
+                // geo: null,
+                // geo: undefined
+                // geo: []
+                // should all behave like there is no geo field.  So we look for these cases and
+                // throw out the field elements if we find them.
+                if (1 == fieldElements.size()) {
+                    BSONElement elt = *fieldElements.begin();
+                    // Get the :null and :undefined cases.
+                    if (elt.isNull() || Undefined == elt.type()) {
+                        fieldElements.clear();
+                    } else if (elt.isABSONObj()) {
+                        // And this is the :[] case.
+                        BSONObj obj = elt.Obj();
+                        if (0 == obj.nFields()) {
                             fieldElements.clear();
                         }
-                        else if (elt.isABSONObj()) {
-                            // And this is the :[] case.
-                            BSONObj obj = elt.Obj();
-                            if (0 == obj.nFields()) {
-                                fieldElements.clear();
-                            }
-                        }
-                    }
-
-                    // V2 2dsphere indices require that at least one geo field to be present in a
-                    // document in order to index it.
-                    if (fieldElements.size() > 0) {
-                        haveGeoField = true;
                     }
                 }
 
-                getS2GeoKeys(obj, fieldElements, params, &keysForThisField);
-            } else {
-                getS2LiteralKeys(fieldElements, &keysForThisField);
+                // V2 2dsphere indices require that at least one geo field to be present in a
+                // document in order to index it.
+                if (fieldElements.size() > 0) {
+                    haveGeoField = true;
+                }
             }
 
-            // We expect there to be the missing field element present in the keys if data is
-            // missing.  So, this should be non-empty.
-            verify(!keysForThisField.empty());
+            getS2GeoKeys(obj, fieldElements, params, &keysForThisField);
+        } else {
+            getS2LiteralKeys(fieldElements, &keysForThisField);
+        }
 
-            // We take the Cartesian product of all of the keys.  This requires that we have
-            // some keys to take the Cartesian product with.  If keysToAdd.empty(), we
-            // initialize it.
-            if (keysToAdd.empty()) {
-                keysToAdd = keysForThisField;
-                continue;
-            }
+        // We expect there to be the missing field element present in the keys if data is
+        // missing.  So, this should be non-empty.
+        verify(!keysForThisField.empty());
 
-            BSONObjSet updatedKeysToAdd;
-            for (BSONObjSet::const_iterator it = keysToAdd.begin(); it != keysToAdd.end();
-                    ++it) {
-                for (BSONObjSet::const_iterator newIt = keysForThisField.begin();
-                        newIt!= keysForThisField.end(); ++newIt) {
-                    BSONObjBuilder b;
-                    b.appendElements(*it);
-                    b.append(newIt->firstElement());
-                    updatedKeysToAdd.insert(b.obj());
-                }
-            }
-            keysToAdd = updatedKeysToAdd;
+        // We take the Cartesian product of all of the keys.  This requires that we have
+        // some keys to take the Cartesian product with.  If keysToAdd.empty(), we
+        // initialize it.
+        if (keysToAdd.empty()) {
+            keysToAdd = keysForThisField;
+            continue;
         }
 
-        // Make sure that if we're V2 there's at least one geo field present in the doc.
-        if (S2_INDEX_VERSION_2 == params.indexVersion) {
-            if (!haveGeoField) {
-                return;
+        BSONObjSet updatedKeysToAdd;
+        for (BSONObjSet::const_iterator it = keysToAdd.begin(); it != keysToAdd.end(); ++it) {
+            for (BSONObjSet::const_iterator newIt = keysForThisField.begin();
+                 newIt != keysForThisField.end();
+                 ++newIt) {
+                BSONObjBuilder b;
+                b.appendElements(*it);
+                b.append(newIt->firstElement());
+                updatedKeysToAdd.insert(b.obj());
             }
         }
+        keysToAdd = updatedKeysToAdd;
+    }
 
-        if (keysToAdd.size() > params.maxKeysPerInsert) {
-            warning() << "Insert of geo object generated a high number of keys."
-                      << " num keys: " << keysToAdd.size()
-                      << " obj inserted: " << obj;
+    // Make sure that if we're V2 there's at least one geo field present in the doc.
+    if (S2_INDEX_VERSION_2 == params.indexVersion) {
+        if (!haveGeoField) {
+            return;
         }
+    }
 
-        *keys = keysToAdd;
+    if (keysToAdd.size() > params.maxKeysPerInsert) {
+        warning() << "Insert of geo object generated a high number of keys."
+                  << " num keys: " << keysToAdd.size() << " obj inserted: " << obj;
     }
 
+    *keys = keysToAdd;
+}
+
 }  // namespace mongo
diff --git a/src/mongo/db/index/expression_keys_private.h b/src/mongo/db/index/expression_keys_private.h
index 6e3fb1ea9a0..9aba295b579 100644
--- a/src/mongo/db/index/expression_keys_private.h
+++ b/src/mongo/db/index/expression_keys_private.h
@@ -36,95 +36,94 @@
 
 namespace mongo {
 
-    struct TwoDIndexingParams;
-    struct S2IndexingParams;
+struct TwoDIndexingParams;
+struct S2IndexingParams;
 
-    namespace fts {
+namespace fts {
 
-        class FTSSpec;
+class FTSSpec;
 
-    }  // namespace fts
+}  // namespace fts
+
+/**
+ * Do not use this class or any of its methods directly.  The key generation of btree-indexed
+ * expression indices is kept outside of the access method for testing and for upgrade
+ * compatibility checking.
+ */
+class ExpressionKeysPrivate {
+public:
+    //
+    // 2d
+    //
+
+    static void get2DKeys(const BSONObj& obj,
+                          const TwoDIndexingParams& params,
+                          BSONObjSet* keys,
+                          std::vector<BSONObj>* locs);
+
+    //
+    // FTS
+    //
+
+    static void getFTSKeys(const BSONObj& obj, const fts::FTSSpec& ftsSpec, BSONObjSet* keys);
+
+    //
+    // Hash
+    //
+
+    /**
+     * Generates keys for hash access method.
+     */
+    static void getHashKeys(const BSONObj& obj,
+                            const std::string& hashedField,
+                            HashSeed seed,
+                            int hashVersion,
+                            bool isSparse,
+                            BSONObjSet* keys);
 
     /**
-     * Do not use this class or any of its methods directly.  The key generation of btree-indexed
-     * expression indices is kept outside of the access method for testing and for upgrade
-     * compatibility checking.
+     * Hashing function used by both getHashKeys and the cursors we create.
+     * Exposed for testing in dbtests/namespacetests.cpp and
+     * so mongo/db/index_legacy.cpp can use it.
      */
-    class ExpressionKeysPrivate {
-    public:
-
-        //
-        // 2d
-        //
-
-        static void get2DKeys(const BSONObj &obj,
-                              const TwoDIndexingParams& params,
-                              BSONObjSet* keys,
-                              std::vector<BSONObj>* locs);
-
-        //
-        // FTS
-        //
-
-        static void getFTSKeys(const BSONObj &obj, const fts::FTSSpec& ftsSpec, BSONObjSet* keys);
-
-        //
-        // Hash
-        //
-
-        /**
-         * Generates keys for hash access method.
-         */
-        static void getHashKeys(const BSONObj& obj,
-                                const std::string& hashedField,
-                                HashSeed seed,
-                                int hashVersion,
-                                bool isSparse,
+    static long long int makeSingleHashKey(const BSONElement& e, HashSeed seed, int v);
+
+    //
+    // Haystack
+    //
+
+    /**
+     * Generates keys for haystack access method.
+     */
+    static void getHaystackKeys(const BSONObj& obj,
+                                const std::string& geoField,
+                                const std::vector<std::string>& otherFields,
+                                double bucketSize,
                                 BSONObjSet* keys);
 
-        /**
-         * Hashing function used by both getHashKeys and the cursors we create.
-         * Exposed for testing in dbtests/namespacetests.cpp and
-         * so mongo/db/index_legacy.cpp can use it.
-         */
-        static long long int makeSingleHashKey(const BSONElement& e, HashSeed seed, int v);
-
-        //
-        // Haystack
-        //
-
-        /**
-         * Generates keys for haystack access method.
-         */
-        static void getHaystackKeys(const BSONObj& obj,
-                                    const std::string& geoField,
-                                    const std::vector<std::string>& otherFields,
-                                    double bucketSize,
-                                    BSONObjSet* keys);
-
-        /**
-         * Returns a hash of a BSON element.
-         * Used by getHaystackKeys and HaystackAccessMethod::searchCommand.
-         */
-        static int hashHaystackElement(const BSONElement& e, double bucketSize);
-
-        /**
-         * Joins two strings using underscore as separator.
-         * Used by getHaystackKeys and HaystackAccessMethod::searchCommand.
-         */
-        static std::string makeHaystackString(int hashedX, int hashedY);
-
-        //
-        // S2
-        //
-
-        /**
-         * Generates keys for S2 access method.
-         */
-        static void getS2Keys(const BSONObj& obj,
-                              const BSONObj& keyPattern,
-                              const S2IndexingParams& params,
-                              BSONObjSet* keys);
-    };
+    /**
+     * Returns a hash of a BSON element.
+     * Used by getHaystackKeys and HaystackAccessMethod::searchCommand.
+     */
+    static int hashHaystackElement(const BSONElement& e, double bucketSize);
+
+    /**
+     * Joins two strings using underscore as separator.
+     * Used by getHaystackKeys and HaystackAccessMethod::searchCommand.
+     */
+    static std::string makeHaystackString(int hashedX, int hashedY);
+
+    //
+    // S2
+    //
+
+    /**
+     * Generates keys for S2 access method.
+     */
+    static void getS2Keys(const BSONObj& obj,
+                          const BSONObj& keyPattern,
+                          const S2IndexingParams& params,
+                          BSONObjSet* keys);
+};
 
 }  // namespace mongo
diff --git a/src/mongo/db/index/expression_params.h b/src/mongo/db/index/expression_params.h
index e7b190f5eb9..a7613b027d3 100644
--- a/src/mongo/db/index/expression_params.h
+++ b/src/mongo/db/index/expression_params.h
@@ -34,150 +34,151 @@
 
 namespace mongo {
 
-    class ExpressionParams {
-    public:
-        static void parseTwoDParams(const BSONObj& infoObj, TwoDIndexingParams* out) {
-            BSONObjIterator i(infoObj.getObjectField("key"));
-
-            while (i.more()) {
-                BSONElement e = i.next();
-                if (e.type() == String && IndexNames::GEO_2D == e.valuestr()) {
-                    uassert(16800, "can't have 2 geo fields", out->geo.size() == 0);
-                    uassert(16801, "2d has to be first in index", out->other.size() == 0);
-                    out->geo = e.fieldName();
-                } else {
-                    int order = 1;
-                    if (e.isNumber()) {
-                        order = static_cast<int>(e.Number());
-                    }
-                    out->other.push_back(std::make_pair(e.fieldName(), order));
+class ExpressionParams {
+public:
+    static void parseTwoDParams(const BSONObj& infoObj, TwoDIndexingParams* out) {
+        BSONObjIterator i(infoObj.getObjectField("key"));
+
+        while (i.more()) {
+            BSONElement e = i.next();
+            if (e.type() == String && IndexNames::GEO_2D == e.valuestr()) {
+                uassert(16800, "can't have 2 geo fields", out->geo.size() == 0);
+                uassert(16801, "2d has to be first in index", out->other.size() == 0);
+                out->geo = e.fieldName();
+            } else {
+                int order = 1;
+                if (e.isNumber()) {
+                    order = static_cast<int>(e.Number());
                 }
+                out->other.push_back(std::make_pair(e.fieldName(), order));
             }
-
-            uassert(16802, "no geo field specified", out->geo.size());
-
-            GeoHashConverter::Parameters hashParams;
-            Status paramStatus = GeoHashConverter::parseParameters(infoObj, &hashParams);
-            uassertStatusOK(paramStatus);
-
-            out->geoHashConverter.reset(new GeoHashConverter(hashParams));
         }
 
-        static void parseHashParams(const BSONObj& infoObj,
-                                    HashSeed* seedOut,
-                                    int* versionOut,
-                                    std::string* fieldOut) {
-
-            // Default _seed to DEFAULT_HASH_SEED if "seed" is not included in the index spec
-            // or if the value of "seed" is not a number
-
-            // *** WARNING ***
-            // Choosing non-default seeds will invalidate hashed sharding
-            // Changing the seed default will break existing indexes and sharded collections
-            if (infoObj["seed"].eoo()) {
-                *seedOut = BSONElementHasher::DEFAULT_HASH_SEED;
-            }
-            else {
-                *seedOut = infoObj["seed"].numberInt();
-            }
-
-            // In case we have hashed indexes based on other hash functions in the future, we store
-            // a hashVersion number. If hashVersion changes, "makeSingleHashKey" will need to change
-            // accordingly.  Defaults to 0 if "hashVersion" is not included in the index spec or if
-            // the value of "hashversion" is not a number
-            *versionOut = infoObj["hashVersion"].numberInt();
-
-            // Get the hashfield name
-            BSONElement firstElt = infoObj.getObjectField("key").firstElement();
-            massert(16765, "error: no hashed index field",
-                    firstElt.str().compare(IndexNames::HASHED) == 0);
-            *fieldOut = firstElt.fieldName();
+        uassert(16802, "no geo field specified", out->geo.size());
+
+        GeoHashConverter::Parameters hashParams;
+        Status paramStatus = GeoHashConverter::parseParameters(infoObj, &hashParams);
+        uassertStatusOK(paramStatus);
+
+        out->geoHashConverter.reset(new GeoHashConverter(hashParams));
+    }
+
+    static void parseHashParams(const BSONObj& infoObj,
+                                HashSeed* seedOut,
+                                int* versionOut,
+                                std::string* fieldOut) {
+        // Default _seed to DEFAULT_HASH_SEED if "seed" is not included in the index spec
+        // or if the value of "seed" is not a number
+
+        // *** WARNING ***
+        // Choosing non-default seeds will invalidate hashed sharding
+        // Changing the seed default will break existing indexes and sharded collections
+        if (infoObj["seed"].eoo()) {
+            *seedOut = BSONElementHasher::DEFAULT_HASH_SEED;
+        } else {
+            *seedOut = infoObj["seed"].numberInt();
         }
 
-        static void parseHaystackParams(const BSONObj& infoObj,
-                                        std::string* geoFieldOut,
-                                        std::vector<std::string>* otherFieldsOut,
-                                        double* bucketSizeOut) {
-
-            BSONElement e = infoObj["bucketSize"];
-            uassert(16777, "need bucketSize", e.isNumber());
-            *bucketSizeOut = e.numberDouble();
-            uassert(16769, "bucketSize cannot be zero", *bucketSizeOut != 0.0);
-
-            // Example:
-            // db.foo.ensureIndex({ pos : "geoHaystack", type : 1 }, { bucketSize : 1 })
-            BSONObjIterator i(infoObj.getObjectField("key"));
-            while (i.more()) {
-                BSONElement e = i.next();
-                if (e.type() == String && IndexNames::GEO_HAYSTACK == e.valuestr()) {
-                    uassert(16770, "can't have more than one geo field", geoFieldOut->size() == 0);
-                    uassert(16771, "the geo field has to be first in index",
-                            otherFieldsOut->size() == 0);
-                    *geoFieldOut = e.fieldName();
-                } else {
-                    uassert(16772, "geoSearch can only have 1 non-geo field for now",
-                            otherFieldsOut->size() == 0);
-                    otherFieldsOut->push_back(e.fieldName());
-                }
+        // In case we have hashed indexes based on other hash functions in the future, we store
+        // a hashVersion number. If hashVersion changes, "makeSingleHashKey" will need to change
+        // accordingly.  Defaults to 0 if "hashVersion" is not included in the index spec or if
+        // the value of "hashversion" is not a number
+        *versionOut = infoObj["hashVersion"].numberInt();
+
+        // Get the hashfield name
+        BSONElement firstElt = infoObj.getObjectField("key").firstElement();
+        massert(
+            16765, "error: no hashed index field", firstElt.str().compare(IndexNames::HASHED) == 0);
+        *fieldOut = firstElt.fieldName();
+    }
+
+    static void parseHaystackParams(const BSONObj& infoObj,
+                                    std::string* geoFieldOut,
+                                    std::vector<std::string>* otherFieldsOut,
+                                    double* bucketSizeOut) {
+        BSONElement e = infoObj["bucketSize"];
+        uassert(16777, "need bucketSize", e.isNumber());
+        *bucketSizeOut = e.numberDouble();
+        uassert(16769, "bucketSize cannot be zero", *bucketSizeOut != 0.0);
+
+        // Example:
+        // db.foo.ensureIndex({ pos : "geoHaystack", type : 1 }, { bucketSize : 1 })
+        BSONObjIterator i(infoObj.getObjectField("key"));
+        while (i.more()) {
+            BSONElement e = i.next();
+            if (e.type() == String && IndexNames::GEO_HAYSTACK == e.valuestr()) {
+                uassert(16770, "can't have more than one geo field", geoFieldOut->size() == 0);
+                uassert(
+                    16771, "the geo field has to be first in index", otherFieldsOut->size() == 0);
+                *geoFieldOut = e.fieldName();
+            } else {
+                uassert(16772,
+                        "geoSearch can only have 1 non-geo field for now",
+                        otherFieldsOut->size() == 0);
+                otherFieldsOut->push_back(e.fieldName());
             }
         }
-
-        static void parse2dsphereParams(const BSONObj& infoObj,
-                                        S2IndexingParams* out) {
-            // Set up basic params.
-            out->maxKeysPerInsert = 200;
-
-            // This is advisory.
-            out->maxCellsInCovering = 50;
-
-            // Near distances are specified in meters...sometimes.
-            out->radius = kRadiusOfEarthInMeters;
-
-            // These are not advisory.
-            out->finestIndexedLevel = configValueWithDefaultInt(infoObj,
-                                                                "finestIndexedLevel",
-                S2::kAvgEdge.GetClosestLevel(500.0 / out->radius));
-
-            out->coarsestIndexedLevel = configValueWithDefaultInt(infoObj,
-                                                                  "coarsestIndexedLevel",
-                S2::kAvgEdge.GetClosestLevel(100 * 1000.0 / out->radius));
-
-            static const std::string kIndexVersionFieldName("2dsphereIndexVersion");
-
-            // Determine which version of this index we're using.  If none was set in the descriptor,
-            // assume S2_INDEX_VERSION_1 (alas, the first version predates the existence of the version
-            // field).
-            out->indexVersion = static_cast<S2IndexVersion>(configValueWithDefaultInt(infoObj,
-                                                                                      kIndexVersionFieldName,
-                                                                                      S2_INDEX_VERSION_1));
-
-            uassert(16747, "coarsestIndexedLevel must be >= 0", out->coarsestIndexedLevel >= 0);
-            uassert(16748, "finestIndexedLevel must be <= 30", out->finestIndexedLevel <= 30);
-            uassert(16749, "finestIndexedLevel must be >= coarsestIndexedLevel",
-                    out->finestIndexedLevel >= out->coarsestIndexedLevel);
-
-            massert(17395,
-                    mongoutils::str::stream() << "unsupported geo index version { " << kIndexVersionFieldName
-                                  << " : " << out->indexVersion << " }, only support versions: ["
-                                  << S2_INDEX_VERSION_1 << "," << S2_INDEX_VERSION_2 << "]",
-                    out->indexVersion == S2_INDEX_VERSION_2 || out->indexVersion == S2_INDEX_VERSION_1);
-        }
-
-    private:
-        static double configValueWithDefaultDouble(const BSONObj& infoObj,
-                                                   const std::string& name,
-                                                   double def) {
-            BSONElement e = infoObj[name];
-            if (e.isNumber()) { return e.numberDouble(); }
-            return def;
+    }
+
+    static void parse2dsphereParams(const BSONObj& infoObj, S2IndexingParams* out) {
+        // Set up basic params.
+        out->maxKeysPerInsert = 200;
+
+        // This is advisory.
+        out->maxCellsInCovering = 50;
+
+        // Near distances are specified in meters...sometimes.
+        out->radius = kRadiusOfEarthInMeters;
+
+        // These are not advisory.
+        out->finestIndexedLevel = configValueWithDefaultInt(
+            infoObj, "finestIndexedLevel", S2::kAvgEdge.GetClosestLevel(500.0 / out->radius));
+
+        out->coarsestIndexedLevel =
+            configValueWithDefaultInt(infoObj,
+                                      "coarsestIndexedLevel",
+                                      S2::kAvgEdge.GetClosestLevel(100 * 1000.0 / out->radius));
+
+        static const std::string kIndexVersionFieldName("2dsphereIndexVersion");
+
+        // Determine which version of this index we're using.  If none was set in the descriptor,
+        // assume S2_INDEX_VERSION_1 (alas, the first version predates the existence of the version
+        // field).
+        out->indexVersion = static_cast<S2IndexVersion>(
+            configValueWithDefaultInt(infoObj, kIndexVersionFieldName, S2_INDEX_VERSION_1));
+
+        uassert(16747, "coarsestIndexedLevel must be >= 0", out->coarsestIndexedLevel >= 0);
+        uassert(16748, "finestIndexedLevel must be <= 30", out->finestIndexedLevel <= 30);
+        uassert(16749,
+                "finestIndexedLevel must be >= coarsestIndexedLevel",
+                out->finestIndexedLevel >= out->coarsestIndexedLevel);
+
+        massert(17395,
+                mongoutils::str::stream() << "unsupported geo index version { "
+                                          << kIndexVersionFieldName << " : " << out->indexVersion
+                                          << " }, only support versions: [" << S2_INDEX_VERSION_1
+                                          << "," << S2_INDEX_VERSION_2 << "]",
+                out->indexVersion == S2_INDEX_VERSION_2 || out->indexVersion == S2_INDEX_VERSION_1);
+    }
+
+private:
+    static double configValueWithDefaultDouble(const BSONObj& infoObj,
+                                               const std::string& name,
+                                               double def) {
+        BSONElement e = infoObj[name];
+        if (e.isNumber()) {
+            return e.numberDouble();
         }
+        return def;
+    }
 
-        static int configValueWithDefaultInt(const BSONObj& infoObj, const std::string& name, int def) {
-            BSONElement e = infoObj[name];
-            if (e.isNumber()) { return e.numberInt(); }
-            return def;
+    static int configValueWithDefaultInt(const BSONObj& infoObj, const std::string& name, int def) {
+        BSONElement e = infoObj[name];
+        if (e.isNumber()) {
+            return e.numberInt();
         }
-
-    };
+        return def;
+    }
+};
 
 }  // namespace mongo
diff --git a/src/mongo/db/index/external_key_generator.cpp b/src/mongo/db/index/external_key_generator.cpp
index 4173880d00b..9f93bd6f439 100644
--- a/src/mongo/db/index/external_key_generator.cpp
+++ b/src/mongo/db/index/external_key_generator.cpp
@@ -42,75 +42,68 @@
 namespace mongo {
 
 namespace {
-    void getKeysForUpgradeChecking(const BSONObj& infoObj,
-                                   const BSONObj& doc,
-                                   BSONObjSet* keys) {
-
-        BSONObj keyPattern = infoObj.getObjectField("key");
-
-        string type = IndexNames::findPluginName(keyPattern);
-
-        if (IndexNames::GEO_2D == type) {
-            TwoDIndexingParams params;
-            ExpressionParams::parseTwoDParams(infoObj, &params);
-            ExpressionKeysPrivate::get2DKeys(doc, params, keys, NULL);
-        }
-        else if (IndexNames::GEO_HAYSTACK == type) {
-            string geoField;
-            vector<string> otherFields;
-            double bucketSize;
-            ExpressionParams::parseHaystackParams(infoObj, &geoField, &otherFields, &bucketSize);
-            ExpressionKeysPrivate::getHaystackKeys(doc, geoField, otherFields, bucketSize, keys);
-        }
-        else if (IndexNames::GEO_2DSPHERE == type) {
-            S2IndexingParams params;
-            ExpressionParams::parse2dsphereParams(infoObj, &params);
-            ExpressionKeysPrivate::getS2Keys(doc, keyPattern, params, keys);
+void getKeysForUpgradeChecking(const BSONObj& infoObj, const BSONObj& doc, BSONObjSet* keys) {
+    BSONObj keyPattern = infoObj.getObjectField("key");
+
+    string type = IndexNames::findPluginName(keyPattern);
+
+    if (IndexNames::GEO_2D == type) {
+        TwoDIndexingParams params;
+        ExpressionParams::parseTwoDParams(infoObj, &params);
+        ExpressionKeysPrivate::get2DKeys(doc, params, keys, NULL);
+    } else if (IndexNames::GEO_HAYSTACK == type) {
+        string geoField;
+        vector<string> otherFields;
+        double bucketSize;
+        ExpressionParams::parseHaystackParams(infoObj, &geoField, &otherFields, &bucketSize);
+        ExpressionKeysPrivate::getHaystackKeys(doc, geoField, otherFields, bucketSize, keys);
+    } else if (IndexNames::GEO_2DSPHERE == type) {
+        S2IndexingParams params;
+        ExpressionParams::parse2dsphereParams(infoObj, &params);
+        ExpressionKeysPrivate::getS2Keys(doc, keyPattern, params, keys);
+    } else if (IndexNames::TEXT == type) {
+        fts::FTSSpec spec(infoObj);
+        ExpressionKeysPrivate::getFTSKeys(doc, spec, keys);
+    } else if (IndexNames::HASHED == type) {
+        HashSeed seed;
+        int version;
+        string field;
+        ExpressionParams::parseHashParams(infoObj, &seed, &version, &field);
+        ExpressionKeysPrivate::getHashKeys(
+            doc, field, seed, version, infoObj["sparse"].trueValue(), keys);
+    } else {
+        invariant(IndexNames::BTREE == type);
+
+        std::vector<const char*> fieldNames;
+        std::vector<BSONElement> fixed;
+        BSONObjIterator keyIt(keyPattern);
+        while (keyIt.more()) {
+            BSONElement patternElt = keyIt.next();
+            fieldNames.push_back(patternElt.fieldName());
+            fixed.push_back(BSONElement());
         }
-        else if (IndexNames::TEXT == type) {
-            fts::FTSSpec spec(infoObj);
-            ExpressionKeysPrivate::getFTSKeys(doc, spec, keys);
-        }
-        else if (IndexNames::HASHED == type) {
-            HashSeed seed;
-            int version;
-            string field;
-            ExpressionParams::parseHashParams(infoObj, &seed, &version, &field);
-            ExpressionKeysPrivate::getHashKeys(doc, field, seed, version, infoObj["sparse"].trueValue(), keys);
-        }
-        else {
-            invariant(IndexNames::BTREE == type);
-
-            std::vector<const char *> fieldNames;
-            std::vector<BSONElement> fixed;
-            BSONObjIterator keyIt(keyPattern);
-            while (keyIt.more()) {
-                BSONElement patternElt = keyIt.next();
-                fieldNames.push_back(patternElt.fieldName());
-                fixed.push_back(BSONElement());
-            }
 
-            // XXX: do we care about version
-            BtreeKeyGeneratorV1 keyGen(fieldNames, fixed, infoObj["sparse"].trueValue());
+        // XXX: do we care about version
+        BtreeKeyGeneratorV1 keyGen(fieldNames, fixed, infoObj["sparse"].trueValue());
 
-            keyGen.getKeys(doc, keys);
-        }
+        keyGen.getKeys(doc, keys);
     }
-
-    // cloned from key.cpp to build the below set
-    const int binDataCodeLengths[] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 10, 12, 14, 16, 20, 24, 32};
-    const std::set<int> acceptableBinDataLengths(
-            binDataCodeLengths,
-            binDataCodeLengths + (sizeof(binDataCodeLengths) / sizeof(int)));
-
-    // modified version of the KeyV1Owned constructor that returns the would-be-key's datasize()
-    int keyV1Size(const BSONObj& obj) {
-        BSONObj::iterator i(obj);
-        int size = 0;
-        const int traditionalSize = obj.objsize() + 1;
-        while (i.more()) { 
-            BSONElement e = i.next();
-            switch (e.type()) { 
+}
+
+// cloned from key.cpp to build the below set
+const int binDataCodeLengths[] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 10, 12, 14, 16, 20, 24, 32};
+const std::set<int> acceptableBinDataLengths(binDataCodeLengths,
+                                             binDataCodeLengths +
+                                                 (sizeof(binDataCodeLengths) / sizeof(int)));
+
+// modified version of the KeyV1Owned constructor that returns the would-be-key's datasize()
+int keyV1Size(const BSONObj& obj) {
+    BSONObj::iterator i(obj);
+    int size = 0;
+    const int traditionalSize = obj.objsize() + 1;
+    while (i.more()) {
+        BSONElement e = i.next();
+        switch (e.type()) {
             case MinKey:
             case jstNULL:
             case MaxKey:
@@ -121,86 +114,82 @@ namespace {
                 size += 1;
                 size += OID::kOIDSize;
                 break;
-            case BinData:
-                {
-                    int t = e.binDataType();
-                    // 0-7 and 0x80 to 0x87 are supported by Key
-                    if( (t & 0x78) == 0 && t != ByteArrayDeprecated ) {
-                        int len;
-                        e.binData(len);
-                        if (acceptableBinDataLengths.count(len)) {
-                            size += 1;
-                            size += 1;
-                            size += len;
-                            break;
-                        }
+            case BinData: {
+                int t = e.binDataType();
+                // 0-7 and 0x80 to 0x87 are supported by Key
+                if ((t & 0x78) == 0 && t != ByteArrayDeprecated) {
+                    int len;
+                    e.binData(len);
+                    if (acceptableBinDataLengths.count(len)) {
+                        size += 1;
+                        size += 1;
+                        size += len;
+                        break;
                     }
-                    return traditionalSize;
                 }
+                return traditionalSize;
+            }
             case Date:
                 size += 1;
                 size += sizeof(Date_t);
                 break;
-            case String:
-                {
-                    size += 1;
-                    // note we do not store the terminating null, to save space.
-                    unsigned x = (unsigned) e.valuestrsize() - 1;
-                    if (x > 255) { 
-                        return traditionalSize;
-                    }
-                    size += 1;
-                    size += x;
-                    break;
+            case String: {
+                size += 1;
+                // note we do not store the terminating null, to save space.
+                unsigned x = (unsigned)e.valuestrsize() - 1;
+                if (x > 255) {
+                    return traditionalSize;
                 }
+                size += 1;
+                size += x;
+                break;
+            }
             case NumberInt:
                 size += 1;
                 size += sizeof(double);
                 break;
-            case NumberLong:
-                {
-                    long long n = e._numberLong();
-                    long long m = 2LL << 52;
-                    if( n >= m || n <= -m ) {
-                        // can't represent exactly as a double
-                        return traditionalSize;
-                    }
-                    size += 1;
-                    size += sizeof(double);
-                    break;
+            case NumberLong: {
+                long long n = e._numberLong();
+                long long m = 2LL << 52;
+                if (n >= m || n <= -m) {
+                    // can't represent exactly as a double
+                    return traditionalSize;
                 }
-            case NumberDouble:
-                {
-                    double d = e._numberDouble();
-                    if (std::isnan(d)) {
-                        return traditionalSize;
-                    }
-                    size += 1;
-                    size += sizeof(double);
-                    break;
+                size += 1;
+                size += sizeof(double);
+                break;
+            }
+            case NumberDouble: {
+                double d = e._numberDouble();
+                if (std::isnan(d)) {
+                    return traditionalSize;
                 }
+                size += 1;
+                size += sizeof(double);
+                break;
+            }
             default:
                 // if other types involved, store as traditional BSON
                 return traditionalSize;
-            }
         }
-        return size;
     }
+    return size;
+}
 
-} // namespace
-
-    bool isAnyIndexKeyTooLarge(const BSONObj& index, const BSONObj& doc) {
-        BSONObjSet keys;
-        getKeysForUpgradeChecking(index, doc, &keys);
+}  // namespace
 
-        int largestKeySize = 0;
+bool isAnyIndexKeyTooLarge(const BSONObj& index, const BSONObj& doc) {
+    BSONObjSet keys;
+    getKeysForUpgradeChecking(index, doc, &keys);
 
-        for (BSONObjSet::const_iterator it = keys.begin(); it != keys.end(); ++it) {
-            largestKeySize = std::max(largestKeySize, keyV1Size(*it));
-        }
+    int largestKeySize = 0;
 
-        // BtreeData_V1::KeyMax is 1024
-        return largestKeySize > 1024;
+    for (BSONObjSet::const_iterator it = keys.begin(); it != keys.end(); ++it) {
+        largestKeySize = std::max(largestKeySize, keyV1Size(*it));
     }
 
+    // BtreeData_V1::KeyMax is 1024
+    return largestKeySize > 1024;
+}
+
 }  // namespace mongo
diff --git a/src/mongo/db/index/external_key_generator.h b/src/mongo/db/index/external_key_generator.h
index a340fd56e0e..9dad28f7413 100644
--- a/src/mongo/db/index/external_key_generator.h
+++ b/src/mongo/db/index/external_key_generator.h
@@ -40,7 +40,7 @@
  */
 namespace mongo {
 
-    // Returns whether or not the largest key the index will generate for the document is too large.
-    bool isAnyIndexKeyTooLarge(const BSONObj& index, const BSONObj& doc);
+// Returns whether or not the largest key the index will generate for the document is too large.
+bool isAnyIndexKeyTooLarge(const BSONObj& index, const BSONObj& doc);
 
 }  // namespace mongo
diff --git a/src/mongo/db/index/fts_access_method.cpp b/src/mongo/db/index/fts_access_method.cpp
index 52bc3424518..9676fcbec45 100644
--- a/src/mongo/db/index/fts_access_method.cpp
+++ b/src/mongo/db/index/fts_access_method.cpp
@@ -31,11 +31,11 @@
 
 namespace mongo {
 
-    FTSAccessMethod::FTSAccessMethod(IndexCatalogEntry* btreeState, SortedDataInterface* btree )
-        : IndexAccessMethod(btreeState, btree), _ftsSpec(btreeState->descriptor()->infoObj()) { }
+FTSAccessMethod::FTSAccessMethod(IndexCatalogEntry* btreeState, SortedDataInterface* btree)
+    : IndexAccessMethod(btreeState, btree), _ftsSpec(btreeState->descriptor()->infoObj()) {}
 
-    void FTSAccessMethod::getKeys(const BSONObj& obj, BSONObjSet* keys) const {
-        ExpressionKeysPrivate::getFTSKeys(obj, _ftsSpec, keys);
-    }
+void FTSAccessMethod::getKeys(const BSONObj& obj, BSONObjSet* keys) const {
+    ExpressionKeysPrivate::getFTSKeys(obj, _ftsSpec, keys);
+}
 
 }  // namespace mongo
diff --git a/src/mongo/db/index/fts_access_method.h b/src/mongo/db/index/fts_access_method.h
index 9cf3e825c89..794d1efe360 100644
--- a/src/mongo/db/index/fts_access_method.h
+++ b/src/mongo/db/index/fts_access_method.h
@@ -36,17 +36,19 @@
 
 namespace mongo {
 
-    class FTSAccessMethod : public IndexAccessMethod {
-    public:
-        FTSAccessMethod(IndexCatalogEntry* btreeState, SortedDataInterface* btree);
+class FTSAccessMethod : public IndexAccessMethod {
+public:
+    FTSAccessMethod(IndexCatalogEntry* btreeState, SortedDataInterface* btree);
 
-        const fts::FTSSpec& getSpec() const { return _ftsSpec; }
+    const fts::FTSSpec& getSpec() const {
+        return _ftsSpec;
+    }
 
-    private:
-        // Implemented:
-        virtual void getKeys(const BSONObj& obj, BSONObjSet* keys) const;
+private:
+    // Implemented:
+    virtual void getKeys(const BSONObj& obj, BSONObjSet* keys) const;
 
-        fts::FTSSpec _ftsSpec;
-    };
+    fts::FTSSpec _ftsSpec;
+};
 
-} // namespace mongo
+}  // namespace mongo
diff --git a/src/mongo/db/index/hash_access_method.cpp b/src/mongo/db/index/hash_access_method.cpp
index 47504706590..8262c9019ab 100644
--- a/src/mongo/db/index/hash_access_method.cpp
+++ b/src/mongo/db/index/hash_access_method.cpp
@@ -33,26 +33,25 @@
 
 namespace mongo {
 
-    HashAccessMethod::HashAccessMethod(IndexCatalogEntry* btreeState, SortedDataInterface* btree)
-        : IndexAccessMethod(btreeState, btree) {
-
-        const IndexDescriptor* descriptor = btreeState->descriptor();
-
-        // We can change these if the single-field limitation is lifted later.
-        uassert(16763, "Currently only single field hashed index supported.",
-                1 == descriptor->getNumFields());
-
-        uassert(16764, "Currently hashed indexes cannot guarantee uniqueness. Use a regular index.",
-                !descriptor->unique());
-
-        ExpressionParams::parseHashParams(descriptor->infoObj(),
-                                          &_seed,
-                                          &_hashVersion,
-                                          &_hashedField);
-    }
-
-    void HashAccessMethod::getKeys(const BSONObj& obj, BSONObjSet* keys) const {
-        ExpressionKeysPrivate::getHashKeys(obj, _hashedField, _seed, _hashVersion, _descriptor->isSparse(), keys);
-    }
+HashAccessMethod::HashAccessMethod(IndexCatalogEntry* btreeState, SortedDataInterface* btree)
+    : IndexAccessMethod(btreeState, btree) {
+    const IndexDescriptor* descriptor = btreeState->descriptor();
+
+    // We can change these if the single-field limitation is lifted later.
+    uassert(16763,
+            "Currently only single field hashed index supported.",
+            1 == descriptor->getNumFields());
+
+    uassert(16764,
+            "Currently hashed indexes cannot guarantee uniqueness. Use a regular index.",
+            !descriptor->unique());
+
+    ExpressionParams::parseHashParams(descriptor->infoObj(), &_seed, &_hashVersion, &_hashedField);
+}
+
+void HashAccessMethod::getKeys(const BSONObj& obj, BSONObjSet* keys) const {
+    ExpressionKeysPrivate::getHashKeys(
+        obj, _hashedField, _seed, _hashVersion, _descriptor->isSparse(), keys);
+}
 
 }  // namespace mongo
diff --git a/src/mongo/db/index/hash_access_method.h b/src/mongo/db/index/hash_access_method.h
index 3e986cbc1b0..ea3f36bb647 100644
--- a/src/mongo/db/index/hash_access_method.h
+++ b/src/mongo/db/index/hash_access_method.h
@@ -38,26 +38,26 @@
 
 namespace mongo {
 
-    /**
-     * This is the access method for "hashed" indices.
-     */
-    class HashAccessMethod : public IndexAccessMethod {
-    public:
-        HashAccessMethod(IndexCatalogEntry* btreeState, SortedDataInterface* btree);
+/**
+ * This is the access method for "hashed" indices.
+ */
+class HashAccessMethod : public IndexAccessMethod {
+public:
+    HashAccessMethod(IndexCatalogEntry* btreeState, SortedDataInterface* btree);
 
-    private:
-        virtual void getKeys(const BSONObj& obj, BSONObjSet* keys) const;
+private:
+    virtual void getKeys(const BSONObj& obj, BSONObjSet* keys) const;
 
-        // Only one of our fields is hashed.  This is the field name for it.
-        std::string _hashedField;
+    // Only one of our fields is hashed.  This is the field name for it.
+    std::string _hashedField;
 
-        // _seed defaults to zero.
-        HashSeed _seed;
+    // _seed defaults to zero.
+    HashSeed _seed;
 
-        // _hashVersion defaults to zero.
-        int _hashVersion;
+    // _hashVersion defaults to zero.
+    int _hashVersion;
 
-        BSONObj _missingKey;
-    };
+    BSONObj _missingKey;
+};
 
 }  // namespace mongo
diff --git a/src/mongo/db/index/haystack_access_method.cpp b/src/mongo/db/index/haystack_access_method.cpp
index 263568af37a..66f1b09e813 100644
--- a/src/mongo/db/index/haystack_access_method.cpp
+++ b/src/mongo/db/index/haystack_access_method.cpp
@@ -44,94 +44,97 @@
 
 namespace mongo {
 
-    using std::unique_ptr;
-
-    HaystackAccessMethod::HaystackAccessMethod(IndexCatalogEntry* btreeState, SortedDataInterface* btree)
-        : IndexAccessMethod(btreeState, btree) {
+using std::unique_ptr;
+
+HaystackAccessMethod::HaystackAccessMethod(IndexCatalogEntry* btreeState,
+                                           SortedDataInterface* btree)
+    : IndexAccessMethod(btreeState, btree) {
+    const IndexDescriptor* descriptor = btreeState->descriptor();
+
+    ExpressionParams::parseHaystackParams(
+        descriptor->infoObj(), &_geoField, &_otherFields, &_bucketSize);
+
+    uassert(16773, "no geo field specified", _geoField.size());
+    uassert(16774, "no non-geo fields specified", _otherFields.size());
+}
+
+void HaystackAccessMethod::getKeys(const BSONObj& obj, BSONObjSet* keys) const {
+    ExpressionKeysPrivate::getHaystackKeys(obj, _geoField, _otherFields, _bucketSize, keys);
+}
+
+void HaystackAccessMethod::searchCommand(OperationContext* txn,
+                                         Collection* collection,
+                                         const BSONObj& nearObj,
+                                         double maxDistance,
+                                         const BSONObj& search,
+                                         BSONObjBuilder* result,
+                                         unsigned limit) {
+    Timer t;
+
+    LOG(1) << "SEARCH near:" << nearObj << " maxDistance:" << maxDistance << " search: " << search
+           << endl;
+    int x, y;
+    {
+        BSONObjIterator i(nearObj);
+        x = ExpressionKeysPrivate::hashHaystackElement(i.next(), _bucketSize);
+        y = ExpressionKeysPrivate::hashHaystackElement(i.next(), _bucketSize);
+    }
+    int scale = static_cast<int>(ceil(maxDistance / _bucketSize));
 
-        const IndexDescriptor* descriptor = btreeState->descriptor();
+    GeoHaystackSearchHopper hopper(txn, nearObj, maxDistance, limit, _geoField, collection);
 
-        ExpressionParams::parseHaystackParams(descriptor->infoObj(),
-                                              &_geoField,
-                                              &_otherFields,
-                                              &_bucketSize);
+    long long btreeMatches = 0;
 
-        uassert(16773, "no geo field specified", _geoField.size());
-        uassert(16774, "no non-geo fields specified", _otherFields.size());
-    }
-
-    void HaystackAccessMethod::getKeys(const BSONObj& obj, BSONObjSet* keys) const {
-        ExpressionKeysPrivate::getHaystackKeys(obj, _geoField, _otherFields, _bucketSize, keys);
-    }
+    for (int a = -scale; a <= scale && !hopper.limitReached(); ++a) {
+        for (int b = -scale; b <= scale && !hopper.limitReached(); ++b) {
+            BSONObjBuilder bb;
+            bb.append("", ExpressionKeysPrivate::makeHaystackString(x + a, y + b));
 
-    void HaystackAccessMethod::searchCommand(OperationContext* txn, Collection* collection,
-                                             const BSONObj& nearObj, double maxDistance,
-                                             const BSONObj& search, BSONObjBuilder* result,
-                                             unsigned limit) {
-        Timer t;
-
-        LOG(1) << "SEARCH near:" << nearObj << " maxDistance:" << maxDistance
-               << " search: " << search << endl;
-        int x, y;
-        {
-            BSONObjIterator i(nearObj);
-            x = ExpressionKeysPrivate::hashHaystackElement(i.next(), _bucketSize);
-            y = ExpressionKeysPrivate::hashHaystackElement(i.next(), _bucketSize);
-        }
-        int scale = static_cast<int>(ceil(maxDistance / _bucketSize));
+            for (unsigned i = 0; i < _otherFields.size(); i++) {
+                // See if the non-geo field we're indexing on is in the provided search term.
+                BSONElement e = search.getFieldDotted(_otherFields[i]);
+                if (e.eoo())
+                    bb.appendNull("");
+                else
+                    bb.appendAs(e, "");
+            }
 
-        GeoHaystackSearchHopper hopper(txn, nearObj, maxDistance, limit, _geoField, collection);
+            BSONObj key = bb.obj();
 
-        long long btreeMatches = 0;
+            unordered_set<RecordId, RecordId::Hasher> thisPass;
 
-        for (int a = -scale; a <= scale && !hopper.limitReached(); ++a) {
-            for (int b = -scale; b <= scale && !hopper.limitReached(); ++b) {
-                BSONObjBuilder bb;
-                bb.append("", ExpressionKeysPrivate::makeHaystackString(x + a, y + b));
 
-                for (unsigned i = 0; i < _otherFields.size(); i++) {
-                    // See if the non-geo field we're indexing on is in the provided search term.
-                    BSONElement e = search.getFieldDotted(_otherFields[i]);
-                    if (e.eoo())
-                        bb.appendNull("");
-                    else
-                        bb.appendAs(e, "");
+            unique_ptr<PlanExecutor> exec(
+                InternalPlanner::indexScan(txn, collection, _descriptor, key, key, true));
+            PlanExecutor::ExecState state;
+            RecordId loc;
+            while (PlanExecutor::ADVANCED == (state = exec->getNext(NULL, &loc))) {
+                if (hopper.limitReached()) {
+                    break;
                 }
-
-                BSONObj key = bb.obj();
-
-                unordered_set<RecordId, RecordId::Hasher> thisPass;
-
-
-                unique_ptr<PlanExecutor> exec(InternalPlanner::indexScan(txn,  collection,
-                                                                     _descriptor, key, key, true));
-                PlanExecutor::ExecState state;
-                RecordId loc;
-                while (PlanExecutor::ADVANCED == (state = exec->getNext(NULL, &loc))) {
-                    if (hopper.limitReached()) { break; }
-                    pair<unordered_set<RecordId, RecordId::Hasher>::iterator, bool> p
-                        = thisPass.insert(loc);
-                    // If a new element was inserted (haven't seen the RecordId before), p.second
-                    // is true.
-                    if (p.second) {
-                        hopper.consider(loc);
-                        btreeMatches++;
-                    }
+                pair<unordered_set<RecordId, RecordId::Hasher>::iterator, bool> p =
+                    thisPass.insert(loc);
+                // If a new element was inserted (haven't seen the RecordId before), p.second
+                // is true.
+                if (p.second) {
+                    hopper.consider(loc);
+                    btreeMatches++;
                 }
             }
         }
+    }
 
-        BSONArrayBuilder arr(result->subarrayStart("results"));
-        int num = hopper.appendResultsTo(&arr);
-        arr.done();
+    BSONArrayBuilder arr(result->subarrayStart("results"));
+    int num = hopper.appendResultsTo(&arr);
+    arr.done();
 
-        {
-            BSONObjBuilder b(result->subobjStart("stats"));
-            b.append("time", t.millis());
-            b.appendNumber("btreeMatches", btreeMatches);
-            b.append("n", num);
-            b.done();
-        }
+    {
+        BSONObjBuilder b(result->subobjStart("stats"));
+        b.append("time", t.millis());
+        b.appendNumber("btreeMatches", btreeMatches);
+        b.append("n", num);
+        b.done();
     }
+}
 
 }  // namespace mongo
diff --git a/src/mongo/db/index/haystack_access_method.h b/src/mongo/db/index/haystack_access_method.h
index 1aac55a25e8..d79de3bfffc 100644
--- a/src/mongo/db/index/haystack_access_method.h
+++ b/src/mongo/db/index/haystack_access_method.h
@@ -35,41 +35,45 @@
 
 namespace mongo {
 
-    class Collection;
-    class OperationContext;
+class Collection;
+class OperationContext;
 
-    /**
-     * Maps (lat, lng) to the bucketSize-sided square bucket that contains it.
-     * Examines all documents in a given radius of a given point.
-     * Returns all documents that match a given search restriction.
-     * See http://dochub.mongodb.org/core/haystackindexes
-     *
-     * Use when you want to look for restaurants within 25 miles with a certain name.
-     * Don't use when you want to find the closest open restaurants; see 2d.cpp for that.
-     *
-     * Usage:
-     * db.foo.ensureIndex({ pos : "geoHaystack", type : 1 }, { bucketSize : 1 })
-     *   pos is the name of the field to be indexed that has lat/lng data in an array.
-     *   type is the name of the secondary field to be indexed. 
-     *   bucketSize specifies the dimension of the square bucket for the data in pos.
-     * ALL fields are mandatory.
-     */
-    class HaystackAccessMethod : public IndexAccessMethod {
-    public:
-        HaystackAccessMethod(IndexCatalogEntry* btreeState, SortedDataInterface* btree);
+/**
+ * Maps (lat, lng) to the bucketSize-sided square bucket that contains it.
+ * Examines all documents in a given radius of a given point.
+ * Returns all documents that match a given search restriction.
+ * See http://dochub.mongodb.org/core/haystackindexes
+ *
+ * Use when you want to look for restaurants within 25 miles with a certain name.
+ * Don't use when you want to find the closest open restaurants; see 2d.cpp for that.
+ *
+ * Usage:
+ * db.foo.ensureIndex({ pos : "geoHaystack", type : 1 }, { bucketSize : 1 })
+ *   pos is the name of the field to be indexed that has lat/lng data in an array.
+ *   type is the name of the secondary field to be indexed.
+ *   bucketSize specifies the dimension of the square bucket for the data in pos.
+ * ALL fields are mandatory.
+ */
+class HaystackAccessMethod : public IndexAccessMethod {
+public:
+    HaystackAccessMethod(IndexCatalogEntry* btreeState, SortedDataInterface* btree);
 
-    protected:
-        friend class GeoHaystackSearchCommand;
-        void searchCommand(OperationContext* txn, Collection* collection,
-                           const BSONObj& nearObj, double maxDistance, const BSONObj& search,
-                           BSONObjBuilder* result, unsigned limit);
+protected:
+    friend class GeoHaystackSearchCommand;
+    void searchCommand(OperationContext* txn,
+                       Collection* collection,
+                       const BSONObj& nearObj,
+                       double maxDistance,
+                       const BSONObj& search,
+                       BSONObjBuilder* result,
+                       unsigned limit);
 
-    private:
-        virtual void getKeys(const BSONObj& obj, BSONObjSet* keys) const;
+private:
+    virtual void getKeys(const BSONObj& obj, BSONObjSet* keys) const;
 
-        std::string _geoField;
-        std::vector<std::string> _otherFields;
-        double _bucketSize;
-    };
+    std::string _geoField;
+    std::vector<std::string> _otherFields;
+    double _bucketSize;
+};
 
 }  // namespace mongo
diff --git a/src/mongo/db/index/haystack_access_method_internal.h b/src/mongo/db/index/haystack_access_method_internal.h
index 2f068bfc15f..0ab511f42e4 100644
--- a/src/mongo/db/index/haystack_access_method_internal.h
+++ b/src/mongo/db/index/haystack_access_method_internal.h
@@ -35,58 +35,60 @@
 
 namespace mongo {
 
-    class GeoHaystackSearchHopper {
-    public:
-        /**
-         * Constructed with a point, a max distance from that point, and a max number of
-         * matched points to store.
-         * @param n  The centroid that we're searching
-         * @param maxDistance  The maximum distance to consider from that point
-         * @param limit  The maximum number of results to return
-         * @param geoField  Which field in the provided RecordId has the point to test.
-         */
-        GeoHaystackSearchHopper(OperationContext* txn,
-                                const BSONObj& nearObj, 
-                                double maxDistance,
-                                unsigned limit,
-                                const std::string& geoField,
-                                const Collection* collection)
-            : _txn(txn),
-              _collection(collection),
-              _near(nearObj), 
-              _maxDistance(maxDistance),
-              _limit(limit),
-              _geoField(geoField) { }
+class GeoHaystackSearchHopper {
+public:
+    /**
+     * Constructed with a point, a max distance from that point, and a max number of
+     * matched points to store.
+     * @param n  The centroid that we're searching
+     * @param maxDistance  The maximum distance to consider from that point
+     * @param limit  The maximum number of results to return
+     * @param geoField  Which field in the provided RecordId has the point to test.
+     */
+    GeoHaystackSearchHopper(OperationContext* txn,
+                            const BSONObj& nearObj,
+                            double maxDistance,
+                            unsigned limit,
+                            const std::string& geoField,
+                            const Collection* collection)
+        : _txn(txn),
+          _collection(collection),
+          _near(nearObj),
+          _maxDistance(maxDistance),
+          _limit(limit),
+          _geoField(geoField) {}
 
-        // Consider the point in loc, and keep it if it's within _maxDistance (and we have space for
-        // it)
-        void consider(const RecordId& loc) {
-            if (limitReached()) return;
-            Point p(_collection->docFor(_txn, loc).value().getFieldDotted(_geoField));
-            if (distance(_near, p) > _maxDistance)
-                return;
-            _locs.push_back(loc);
-        }
+    // Consider the point in loc, and keep it if it's within _maxDistance (and we have space for
+    // it)
+    void consider(const RecordId& loc) {
+        if (limitReached())
+            return;
+        Point p(_collection->docFor(_txn, loc).value().getFieldDotted(_geoField));
+        if (distance(_near, p) > _maxDistance)
+            return;
+        _locs.push_back(loc);
+    }
 
-        int appendResultsTo(BSONArrayBuilder* b) {
-            for (unsigned i = 0; i <_locs.size(); i++)
-                b->append(_collection->docFor(_txn, _locs[i]).value());
-            return _locs.size();
-        }
+    int appendResultsTo(BSONArrayBuilder* b) {
+        for (unsigned i = 0; i < _locs.size(); i++)
+            b->append(_collection->docFor(_txn, _locs[i]).value());
+        return _locs.size();
+    }
 
-        // Have we stored as many points as we can?
-        bool limitReached() const {
-            return _locs.size() >= _limit;
-        }
-    private:
-        OperationContext* _txn;
-        const Collection* _collection;
+    // Have we stored as many points as we can?
+    bool limitReached() const {
+        return _locs.size() >= _limit;
+    }
 
-        Point _near;
-        double _maxDistance;
-        unsigned _limit;
-        const std::string _geoField;
-        std::vector<RecordId> _locs;
-    };
+private:
+    OperationContext* _txn;
+    const Collection* _collection;
+
+    Point _near;
+    double _maxDistance;
+    unsigned _limit;
+    const std::string _geoField;
+    std::vector<RecordId> _locs;
+};
 
 }  // namespace mongo
diff --git a/src/mongo/db/index/index_access_method.cpp b/src/mongo/db/index/index_access_method.cpp
index 2e1490f1f4d..18765949789 100644
--- a/src/mongo/db/index/index_access_method.cpp
+++ b/src/mongo/db/index/index_access_method.cpp
@@ -49,408 +49,397 @@
 
 namespace mongo {
 
-    using std::endl;
-    using std::set;
-    using std::vector;
-
-    MONGO_EXPORT_SERVER_PARAMETER(failIndexKeyTooLong, bool, true);
-
-    //
-    // Comparison for external sorter interface
-    //
-
-    // Defined in db/structure/btree/key.cpp
-    // XXX TODO: rename to something more descriptive, etc. etc.
-    int oldCompare(const BSONObj& l,const BSONObj& r, const Ordering &o);
-
-    class BtreeExternalSortComparison {
-    public:
-        BtreeExternalSortComparison(const BSONObj& ordering, int version)
-            : _ordering(Ordering::make(ordering)),
-              _version(version) {
-            invariant(version == 1 || version == 0);
-        }
+using std::endl;
+using std::set;
+using std::vector;
 
-        typedef std::pair<BSONObj, RecordId> Data;
+MONGO_EXPORT_SERVER_PARAMETER(failIndexKeyTooLong, bool, true);
 
-        int operator() (const Data& l, const Data& r) const {
-            int x = (_version == 1
-                        ? l.first.woCompare(r.first, _ordering, /*considerfieldname*/false)
-                        : oldCompare(l.first, r.first, _ordering));
-            if (x) { return x; }
-            return l.second.compare(r.second);
-        }
-    private:
-        const Ordering _ordering;
-        const int _version;
-    };
-
-    IndexAccessMethod::IndexAccessMethod(IndexCatalogEntry* btreeState,
-                                         SortedDataInterface* btree)
-        : _btreeState(btreeState),
-          _descriptor(btreeState->descriptor()),
-          _newInterface(btree) {
-        verify(0 == _descriptor->version() || 1 == _descriptor->version());
-    }
+//
+// Comparison for external sorter interface
+//
 
-    bool IndexAccessMethod::ignoreKeyTooLong(OperationContext *txn) {
-        // Ignore this error if we're on a secondary or if the user requested it
-        return !txn->isPrimaryFor(_btreeState->ns()) || !failIndexKeyTooLong;
+// Defined in db/structure/btree/key.cpp
+// XXX TODO: rename to something more descriptive, etc. etc.
+int oldCompare(const BSONObj& l, const BSONObj& r, const Ordering& o);
+
+class BtreeExternalSortComparison {
+public:
+    BtreeExternalSortComparison(const BSONObj& ordering, int version)
+        : _ordering(Ordering::make(ordering)), _version(version) {
+        invariant(version == 1 || version == 0);
     }
 
-    // Find the keys for obj, put them in the tree pointing to loc
-    Status IndexAccessMethod::insert(OperationContext* txn,
-                                     const BSONObj& obj,
-                                     const RecordId& loc,
-                                     const InsertDeleteOptions& options,
-                                     int64_t* numInserted) {
-        *numInserted = 0;
+    typedef std::pair<BSONObj, RecordId> Data;
 
-        BSONObjSet keys;
-        // Delegate to the subclass.
-        getKeys(obj, &keys);
+    int operator()(const Data& l, const Data& r) const {
+        int x = (_version == 1 ? l.first.woCompare(r.first, _ordering, /*considerfieldname*/ false)
+                               : oldCompare(l.first, r.first, _ordering));
+        if (x) {
+            return x;
+        }
+        return l.second.compare(r.second);
+    }
 
-        Status ret = Status::OK();
-        for (BSONObjSet::const_iterator i = keys.begin(); i != keys.end(); ++i) {
-            Status status = _newInterface->insert(txn, *i, loc, options.dupsAllowed);
+private:
+    const Ordering _ordering;
+    const int _version;
+};
+
+IndexAccessMethod::IndexAccessMethod(IndexCatalogEntry* btreeState, SortedDataInterface* btree)
+    : _btreeState(btreeState), _descriptor(btreeState->descriptor()), _newInterface(btree) {
+    verify(0 == _descriptor->version() || 1 == _descriptor->version());
+}
+
+bool IndexAccessMethod::ignoreKeyTooLong(OperationContext* txn) {
+    // Ignore this error if we're on a secondary or if the user requested it
+    return !txn->isPrimaryFor(_btreeState->ns()) || !failIndexKeyTooLong;
+}
+
+// Find the keys for obj, put them in the tree pointing to loc
+Status IndexAccessMethod::insert(OperationContext* txn,
+                                 const BSONObj& obj,
+                                 const RecordId& loc,
+                                 const InsertDeleteOptions& options,
+                                 int64_t* numInserted) {
+    *numInserted = 0;
+
+    BSONObjSet keys;
+    // Delegate to the subclass.
+    getKeys(obj, &keys);
+
+    Status ret = Status::OK();
+    for (BSONObjSet::const_iterator i = keys.begin(); i != keys.end(); ++i) {
+        Status status = _newInterface->insert(txn, *i, loc, options.dupsAllowed);
+
+        // Everything's OK, carry on.
+        if (status.isOK()) {
+            ++*numInserted;
+            continue;
+        }
 
-            // Everything's OK, carry on.
-            if (status.isOK()) {
-                ++*numInserted;
-                continue;
-            }
+        // Error cases.
 
-            // Error cases.
+        if (status.code() == ErrorCodes::KeyTooLong && ignoreKeyTooLong(txn)) {
+            continue;
+        }
 
-            if (status.code() == ErrorCodes::KeyTooLong && ignoreKeyTooLong(txn)) {
+        if (status.code() == ErrorCodes::DuplicateKeyValue) {
+            // A document might be indexed multiple times during a background index build
+            // if it moves ahead of the collection scan cursor (e.g. via an update).
+            if (!_btreeState->isReady(txn)) {
+                LOG(3) << "key " << *i << " already in index during background indexing (ok)";
                 continue;
             }
-
-            if (status.code() == ErrorCodes::DuplicateKeyValue) {
-                // A document might be indexed multiple times during a background index build
-                // if it moves ahead of the collection scan cursor (e.g. via an update).
-                if (!_btreeState->isReady(txn)) {
-                    LOG(3) << "key " << *i << " already in index during background indexing (ok)";
-                    continue;
-                }
-            }
-
-            // Clean up after ourselves.
-            for (BSONObjSet::const_iterator j = keys.begin(); j != i; ++j) {
-                removeOneKey(txn, *j, loc, options.dupsAllowed);
-                *numInserted = 0;
-            }
-
-            return status;
         }
 
-        if (*numInserted > 1) {
-            _btreeState->setMultikey( txn );
+        // Clean up after ourselves.
+        for (BSONObjSet::const_iterator j = keys.begin(); j != i; ++j) {
+            removeOneKey(txn, *j, loc, options.dupsAllowed);
+            *numInserted = 0;
         }
 
-        return ret;
+        return status;
     }
 
-    void IndexAccessMethod::removeOneKey(OperationContext* txn,
-                                         const BSONObj& key,
-                                         const RecordId& loc,
-                                         bool dupsAllowed) {
-        try {
-            _newInterface->unindex(txn, key, loc, dupsAllowed);
-        } catch (AssertionException& e) {
-            log() << "Assertion failure: _unindex failed "
-                  << _descriptor->indexNamespace() << endl;
-            log() << "Assertion failure: _unindex failed: " << e.what()
-                  << "  key:" << key.toString()
-                  << "  dl:" << loc;
-            logContext();
-        }
+    if (*numInserted > 1) {
+        _btreeState->setMultikey(txn);
     }
 
-    std::unique_ptr<SortedDataInterface::Cursor> IndexAccessMethod::newCursor(
-            OperationContext* txn,
-            bool isForward) const {
-        return _newInterface->newCursor(txn, isForward);
-    }
+    return ret;
+}
 
-    // Remove the provided doc from the index.
-    Status IndexAccessMethod::remove(OperationContext* txn,
-                                     const BSONObj &obj,
+void IndexAccessMethod::removeOneKey(OperationContext* txn,
+                                     const BSONObj& key,
                                      const RecordId& loc,
-                                     const InsertDeleteOptions &options,
-                                     int64_t* numDeleted) {
-
-        BSONObjSet keys;
-        getKeys(obj, &keys);
-        *numDeleted = 0;
-
-        for (BSONObjSet::const_iterator i = keys.begin(); i != keys.end(); ++i) {
-            removeOneKey(txn, *i, loc, options.dupsAllowed);
-            ++*numDeleted;
-        }
-
-        return Status::OK();
+                                     bool dupsAllowed) {
+    try {
+        _newInterface->unindex(txn, key, loc, dupsAllowed);
+    } catch (AssertionException& e) {
+        log() << "Assertion failure: _unindex failed " << _descriptor->indexNamespace() << endl;
+        log() << "Assertion failure: _unindex failed: " << e.what() << "  key:" << key.toString()
+              << "  dl:" << loc;
+        logContext();
+    }
+}
+
+std::unique_ptr<SortedDataInterface::Cursor> IndexAccessMethod::newCursor(OperationContext* txn,
+                                                                          bool isForward) const {
+    return _newInterface->newCursor(txn, isForward);
+}
+
+// Remove the provided doc from the index.
+Status IndexAccessMethod::remove(OperationContext* txn,
+                                 const BSONObj& obj,
+                                 const RecordId& loc,
+                                 const InsertDeleteOptions& options,
+                                 int64_t* numDeleted) {
+    BSONObjSet keys;
+    getKeys(obj, &keys);
+    *numDeleted = 0;
+
+    for (BSONObjSet::const_iterator i = keys.begin(); i != keys.end(); ++i) {
+        removeOneKey(txn, *i, loc, options.dupsAllowed);
+        ++*numDeleted;
     }
 
-    // Return keys in l that are not in r.
-    // Lifted basically verbatim from elsewhere.
-    static void setDifference(const BSONObjSet &l, const BSONObjSet &r, vector<BSONObj*> *diff) {
-        // l and r must use the same ordering spec.
-        verify(l.key_comp().order() == r.key_comp().order());
-        BSONObjSet::const_iterator i = l.begin();
-        BSONObjSet::const_iterator j = r.begin();
-        while ( 1 ) {
-            if ( i == l.end() )
-                break;
-            while ( j != r.end() && j->woCompare( *i ) < 0 )
-                j++;
-            if ( j == r.end() || i->woCompare(*j) != 0  ) {
-                const BSONObj *jo = &*i;
-                diff->push_back( (BSONObj *) jo );
-            }
-            i++;
+    return Status::OK();
+}
+
+// Return keys in l that are not in r.
+// Lifted basically verbatim from elsewhere.
+static void setDifference(const BSONObjSet& l, const BSONObjSet& r, vector<BSONObj*>* diff) {
+    // l and r must use the same ordering spec.
+    verify(l.key_comp().order() == r.key_comp().order());
+    BSONObjSet::const_iterator i = l.begin();
+    BSONObjSet::const_iterator j = r.begin();
+    while (1) {
+        if (i == l.end())
+            break;
+        while (j != r.end() && j->woCompare(*i) < 0)
+            j++;
+        if (j == r.end() || i->woCompare(*j) != 0) {
+            const BSONObj* jo = &*i;
+            diff->push_back((BSONObj*)jo);
         }
+        i++;
     }
+}
 
-    Status IndexAccessMethod::initializeAsEmpty(OperationContext* txn) {
-        return _newInterface->initAsEmpty(txn);
-    }
+Status IndexAccessMethod::initializeAsEmpty(OperationContext* txn) {
+    return _newInterface->initAsEmpty(txn);
+}
 
-    Status IndexAccessMethod::touch(OperationContext* txn, const BSONObj& obj) {
-        BSONObjSet keys;
-        getKeys(obj, &keys);
+Status IndexAccessMethod::touch(OperationContext* txn, const BSONObj& obj) {
+    BSONObjSet keys;
+    getKeys(obj, &keys);
 
-        std::unique_ptr<SortedDataInterface::Cursor> cursor(_newInterface->newCursor(txn));
-        for (BSONObjSet::const_iterator i = keys.begin(); i != keys.end(); ++i) {
-            cursor->seekExact(*i);
-        }
-
-        return Status::OK();
+    std::unique_ptr<SortedDataInterface::Cursor> cursor(_newInterface->newCursor(txn));
+    for (BSONObjSet::const_iterator i = keys.begin(); i != keys.end(); ++i) {
+        cursor->seekExact(*i);
     }
 
+    return Status::OK();
+}
 
-    Status IndexAccessMethod::touch( OperationContext* txn ) const {
-        return _newInterface->touch(txn);
-    }
 
-    RecordId IndexAccessMethod::findSingle(OperationContext* txn, const BSONObj& key) const {
-        std::unique_ptr<SortedDataInterface::Cursor> cursor(_newInterface->newCursor(txn));
-        const auto requestedInfo = kDebugBuild ? SortedDataInterface::Cursor::kKeyAndLoc
-                                               : SortedDataInterface::Cursor::kWantLoc;
-        if (auto kv = cursor->seekExact(key, requestedInfo)) {
-            // StorageEngine should guarantee these.
-            dassert(!kv->loc.isNull());
-            dassert(kv->key.woCompare(key, /*order*/BSONObj(), /*considerFieldNames*/false) == 0);
+Status IndexAccessMethod::touch(OperationContext* txn) const {
+    return _newInterface->touch(txn);
+}
 
-            return kv->loc;
-        }
-
-        return RecordId();
-    }
+RecordId IndexAccessMethod::findSingle(OperationContext* txn, const BSONObj& key) const {
+    std::unique_ptr<SortedDataInterface::Cursor> cursor(_newInterface->newCursor(txn));
+    const auto requestedInfo = kDebugBuild ? SortedDataInterface::Cursor::kKeyAndLoc
+                                           : SortedDataInterface::Cursor::kWantLoc;
+    if (auto kv = cursor->seekExact(key, requestedInfo)) {
+        // StorageEngine should guarantee these.
+        dassert(!kv->loc.isNull());
+        dassert(kv->key.woCompare(key, /*order*/ BSONObj(), /*considerFieldNames*/ false) == 0);
 
-    Status IndexAccessMethod::validate(OperationContext* txn, bool full, int64_t* numKeys,
-                                       BSONObjBuilder* output) {
-        // XXX: long long vs int64_t
-        long long keys = 0;
-        _newInterface->fullValidate(txn, full, &keys, output);
-        *numKeys = keys;
-        return Status::OK();
+        return kv->loc;
     }
 
-    bool IndexAccessMethod::appendCustomStats(OperationContext* txn,
-                                              BSONObjBuilder* output,
-                                              double scale) const {
-        return _newInterface->appendCustomStats(txn, output, scale);
+    return RecordId();
+}
+
+Status IndexAccessMethod::validate(OperationContext* txn,
+                                   bool full,
+                                   int64_t* numKeys,
+                                   BSONObjBuilder* output) {
+    // XXX: long long vs int64_t
+    long long keys = 0;
+    _newInterface->fullValidate(txn, full, &keys, output);
+    *numKeys = keys;
+    return Status::OK();
+}
+
+bool IndexAccessMethod::appendCustomStats(OperationContext* txn,
+                                          BSONObjBuilder* output,
+                                          double scale) const {
+    return _newInterface->appendCustomStats(txn, output, scale);
+}
+
+long long IndexAccessMethod::getSpaceUsedBytes(OperationContext* txn) const {
+    return _newInterface->getSpaceUsedBytes(txn);
+}
+
+Status IndexAccessMethod::validateUpdate(OperationContext* txn,
+                                         const BSONObj& from,
+                                         const BSONObj& to,
+                                         const RecordId& record,
+                                         const InsertDeleteOptions& options,
+                                         UpdateTicket* ticket,
+                                         const MatchExpression* indexFilter) {
+    if (indexFilter == NULL || indexFilter->matchesBSON(from))
+        getKeys(from, &ticket->oldKeys);
+    if (indexFilter == NULL || indexFilter->matchesBSON(to))
+        getKeys(to, &ticket->newKeys);
+    ticket->loc = record;
+    ticket->dupsAllowed = options.dupsAllowed;
+
+    setDifference(ticket->oldKeys, ticket->newKeys, &ticket->removed);
+    setDifference(ticket->newKeys, ticket->oldKeys, &ticket->added);
+
+    ticket->_isValid = true;
+
+    return Status::OK();
+}
+
+Status IndexAccessMethod::update(OperationContext* txn,
+                                 const UpdateTicket& ticket,
+                                 int64_t* numUpdated) {
+    if (!ticket._isValid) {
+        return Status(ErrorCodes::InternalError, "Invalid UpdateTicket in update");
     }
 
-    long long IndexAccessMethod::getSpaceUsedBytes( OperationContext* txn ) const {
-        return _newInterface->getSpaceUsedBytes( txn );
+    if (ticket.oldKeys.size() + ticket.added.size() - ticket.removed.size() > 1) {
+        _btreeState->setMultikey(txn);
     }
 
-    Status IndexAccessMethod::validateUpdate(OperationContext* txn,
-                                             const BSONObj &from,
-                                             const BSONObj &to,
-                                             const RecordId &record,
-                                             const InsertDeleteOptions &options,
-                                             UpdateTicket* ticket,
-                                             const MatchExpression* indexFilter) {
-
-        if (indexFilter == NULL || indexFilter->matchesBSON(from))
-            getKeys(from, &ticket->oldKeys);
-        if (indexFilter == NULL || indexFilter->matchesBSON(to))
-            getKeys(to, &ticket->newKeys);
-        ticket->loc = record;
-        ticket->dupsAllowed = options.dupsAllowed;
-
-        setDifference(ticket->oldKeys, ticket->newKeys, &ticket->removed);
-        setDifference(ticket->newKeys, ticket->oldKeys, &ticket->added);
-
-        ticket->_isValid = true;
-
-        return Status::OK();
+    for (size_t i = 0; i < ticket.removed.size(); ++i) {
+        _newInterface->unindex(txn, *ticket.removed[i], ticket.loc, ticket.dupsAllowed);
     }
 
-    Status IndexAccessMethod::update(OperationContext* txn,
-                                     const UpdateTicket& ticket,
-                                     int64_t* numUpdated) {
-        if (!ticket._isValid) {
-            return Status(ErrorCodes::InternalError, "Invalid UpdateTicket in update");
-        }
-
-        if (ticket.oldKeys.size() + ticket.added.size() - ticket.removed.size() > 1) {
-            _btreeState->setMultikey( txn );
-        }
-
-        for (size_t i = 0; i < ticket.removed.size(); ++i) {
-            _newInterface->unindex(txn,
-                                   *ticket.removed[i],
-                                   ticket.loc,
-                                   ticket.dupsAllowed);
-        }
-
-        for (size_t i = 0; i < ticket.added.size(); ++i) {
-            Status status = _newInterface->insert(txn,
-                                                  *ticket.added[i],
-                                                  ticket.loc,
-                                                  ticket.dupsAllowed);
-            if ( !status.isOK() ) {
-                if (status.code() == ErrorCodes::KeyTooLong && ignoreKeyTooLong(txn)) {
-                    // Ignore.
-                    continue;
-                }
-
-                return status;
+    for (size_t i = 0; i < ticket.added.size(); ++i) {
+        Status status =
+            _newInterface->insert(txn, *ticket.added[i], ticket.loc, ticket.dupsAllowed);
+        if (!status.isOK()) {
+            if (status.code() == ErrorCodes::KeyTooLong && ignoreKeyTooLong(txn)) {
+                // Ignore.
+                continue;
             }
-        }
-
-        *numUpdated = ticket.added.size();
 
-        return Status::OK();
+            return status;
+        }
     }
 
-    std::unique_ptr<IndexAccessMethod::BulkBuilder> IndexAccessMethod::initiateBulk() {
-
-        return std::unique_ptr<BulkBuilder>(new BulkBuilder(this, _descriptor));
+    *numUpdated = ticket.added.size();
+
+    return Status::OK();
+}
+
+std::unique_ptr<IndexAccessMethod::BulkBuilder> IndexAccessMethod::initiateBulk() {
+    return std::unique_ptr<BulkBuilder>(new BulkBuilder(this, _descriptor));
+}
+
+IndexAccessMethod::BulkBuilder::BulkBuilder(const IndexAccessMethod* index,
+                                            const IndexDescriptor* descriptor)
+    : _sorter(Sorter::make(
+          SortOptions()
+              .TempDir(storageGlobalParams.dbpath + "/_tmp")
+              .ExtSortAllowed()
+              .MaxMemoryUsageBytes(100 * 1024 * 1024),
+          BtreeExternalSortComparison(descriptor->keyPattern(), descriptor->version()))),
+      _real(index) {}
+
+Status IndexAccessMethod::BulkBuilder::insert(OperationContext* txn,
+                                              const BSONObj& obj,
+                                              const RecordId& loc,
+                                              const InsertDeleteOptions& options,
+                                              int64_t* numInserted) {
+    BSONObjSet keys;
+    _real->getKeys(obj, &keys);
+
+    _isMultiKey = _isMultiKey || (keys.size() > 1);
+
+    for (BSONObjSet::iterator it = keys.begin(); it != keys.end(); ++it) {
+        _sorter->add(*it, loc);
+        _keysInserted++;
     }
 
-    IndexAccessMethod::BulkBuilder::BulkBuilder(const IndexAccessMethod* index,
-                                                const IndexDescriptor* descriptor)
-            : _sorter(Sorter::make(SortOptions().TempDir(storageGlobalParams.dbpath + "/_tmp")
-                                                .ExtSortAllowed()
-                                                .MaxMemoryUsageBytes(100*1024*1024),
-                                   BtreeExternalSortComparison(descriptor->keyPattern(),
-                                                               descriptor->version())))
-            , _real(index) {
+    if (NULL != numInserted) {
+        *numInserted += keys.size();
     }
 
-    Status IndexAccessMethod::BulkBuilder::insert(OperationContext* txn,
-                                                  const BSONObj& obj,
-                                                  const RecordId& loc,
-                                                  const InsertDeleteOptions& options,
-                                                  int64_t* numInserted) {
-        BSONObjSet keys;
-        _real->getKeys(obj, &keys);
-
-        _isMultiKey = _isMultiKey || (keys.size() > 1);
-
-        for (BSONObjSet::iterator it = keys.begin(); it != keys.end(); ++it) {
-            _sorter->add(*it, loc);
-            _keysInserted++;
-        }
+    return Status::OK();
+}
 
-        if (NULL != numInserted) {
-            *numInserted += keys.size();
-        }
 
-        return Status::OK();
-    }
+Status IndexAccessMethod::commitBulk(OperationContext* txn,
+                                     std::unique_ptr<BulkBuilder> bulk,
+                                     bool mayInterrupt,
+                                     bool dupsAllowed,
+                                     set<RecordId>* dupsToDrop) {
+    Timer timer;
 
+    std::unique_ptr<BulkBuilder::Sorter::Iterator> i(bulk->_sorter->done());
 
-    Status IndexAccessMethod::commitBulk(OperationContext* txn,
-                                         std::unique_ptr<BulkBuilder> bulk,
-                                         bool mayInterrupt,
-                                         bool dupsAllowed,
-                                         set<RecordId>* dupsToDrop) {
+    stdx::unique_lock<Client> lk(*txn->getClient());
+    ProgressMeterHolder pm(*txn->setMessage_inlock("Index Bulk Build: (2/3) btree bottom up",
+                                                   "Index: (2/3) BTree Bottom Up Progress",
+                                                   bulk->_keysInserted,
+                                                   10));
+    lk.unlock();
 
-        Timer timer;
+    std::unique_ptr<SortedDataBuilderInterface> builder;
 
-        std::unique_ptr<BulkBuilder::Sorter::Iterator> i(bulk->_sorter->done());
+    MONGO_WRITE_CONFLICT_RETRY_LOOP_BEGIN {
+        WriteUnitOfWork wunit(txn);
 
-        stdx::unique_lock<Client> lk(*txn->getClient());
-        ProgressMeterHolder pm(*txn->setMessage_inlock("Index Bulk Build: (2/3) btree bottom up",
-                                                       "Index: (2/3) BTree Bottom Up Progress",
-                                                       bulk->_keysInserted,
-                                                       10));
-        lk.unlock();
+        if (bulk->_isMultiKey) {
+            _btreeState->setMultikey(txn);
+        }
 
-        std::unique_ptr<SortedDataBuilderInterface> builder;
+        builder.reset(_newInterface->getBulkBuilder(txn, dupsAllowed));
+        wunit.commit();
+    }
+    MONGO_WRITE_CONFLICT_RETRY_LOOP_END(txn, "setting index multikey flag", "");
 
-        MONGO_WRITE_CONFLICT_RETRY_LOOP_BEGIN {
-            WriteUnitOfWork wunit(txn);
+    while (i->more()) {
+        if (mayInterrupt) {
+            txn->checkForInterrupt();
+        }
 
-            if (bulk->_isMultiKey) {
-                _btreeState->setMultikey( txn );
-            }
+        WriteUnitOfWork wunit(txn);
+        // Improve performance in the btree-building phase by disabling rollback tracking.
+        // This avoids copying all the written bytes to a buffer that is only used to roll back.
+        // Note that this is safe to do, as this entire index-build-in-progress will be cleaned
+        // up by the index system.
+        txn->recoveryUnit()->setRollbackWritesDisabled();
 
-            builder.reset(_newInterface->getBulkBuilder(txn, dupsAllowed));
-            wunit.commit();
-        } MONGO_WRITE_CONFLICT_RETRY_LOOP_END(txn, "setting index multikey flag", "");
+        // Get the next datum and add it to the builder.
+        BulkBuilder::Sorter::Data d = i->next();
+        Status status = builder->addKey(d.first, d.second);
 
-        while (i->more()) {
-            if (mayInterrupt) {
-                txn->checkForInterrupt();
+        if (!status.isOK()) {
+            // Overlong key that's OK to skip?
+            if (status.code() == ErrorCodes::KeyTooLong && ignoreKeyTooLong(txn)) {
+                continue;
             }
 
-            WriteUnitOfWork wunit(txn);
-            // Improve performance in the btree-building phase by disabling rollback tracking.
-            // This avoids copying all the written bytes to a buffer that is only used to roll back.
-            // Note that this is safe to do, as this entire index-build-in-progress will be cleaned
-            // up by the index system.
-            txn->recoveryUnit()->setRollbackWritesDisabled();
+            // Check if this is a duplicate that's OK to skip
+            if (status.code() == ErrorCodes::DuplicateKey) {
+                invariant(!dupsAllowed);  // shouldn't be getting DupKey errors if dupsAllowed.
 
-            // Get the next datum and add it to the builder.
-            BulkBuilder::Sorter::Data d = i->next();
-            Status status = builder->addKey(d.first, d.second);
-
-            if (!status.isOK()) {
-                // Overlong key that's OK to skip?
-                if (status.code() == ErrorCodes::KeyTooLong && ignoreKeyTooLong(txn)) {
+                if (dupsToDrop) {
+                    dupsToDrop->insert(d.second);
                     continue;
                 }
-
-                // Check if this is a duplicate that's OK to skip
-                if (status.code() == ErrorCodes::DuplicateKey) {
-                    invariant(!dupsAllowed); // shouldn't be getting DupKey errors if dupsAllowed.
-
-                    if (dupsToDrop) {
-                        dupsToDrop->insert(d.second);
-                        continue;
-                    }
-                }
-
-                return status;
             }
 
-            // If we're here either it's a dup and we're cool with it or the addKey went just
-            // fine.
-            pm.hit();
-            wunit.commit();
+            return status;
         }
 
-        pm.finished();
-
-        {
-            stdx::lock_guard<Client> lk(*txn->getClient());
-            CurOp::get(txn)->setMessage_inlock("Index Bulk Build: (3/3) btree-middle",
-                                               "Index: (3/3) BTree Middle Progress");
-        }
+        // If we're here either it's a dup and we're cool with it or the addKey went just
+        // fine.
+        pm.hit();
+        wunit.commit();
+    }
 
-        LOG(timer.seconds() > 10 ? 0 : 1 ) << "\t done building bottom layer, going to commit";
+    pm.finished();
 
-        builder->commit(mayInterrupt);
-        return Status::OK();
+    {
+        stdx::lock_guard<Client> lk(*txn->getClient());
+        CurOp::get(txn)->setMessage_inlock("Index Bulk Build: (3/3) btree-middle",
+                                           "Index: (3/3) BTree Middle Progress");
     }
 
+    LOG(timer.seconds() > 10 ? 0 : 1) << "\t done building bottom layer, going to commit";
+
+    builder->commit(mayInterrupt);
+    return Status::OK();
+}
+
 }  // 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 3f311128a2e..5dc88d30d80 100644
--- a/src/mongo/db/index/index_access_method.h
+++ b/src/mongo/db/index/index_access_method.h
@@ -40,250 +40,250 @@
 
 namespace mongo {
 
-    class BSONObjBuilder;
-    class MatchExpression;
-    class UpdateTicket;
-    struct InsertDeleteOptions;
+class BSONObjBuilder;
+class MatchExpression;
+class UpdateTicket;
+struct InsertDeleteOptions;
+
+/**
+ * An IndexAccessMethod is the interface through which all the mutation, lookup, and
+ * traversal of index entries is done. The class is designed so that the underlying index
+ * data structure is opaque to the caller.
+ *
+ * IndexAccessMethods for existing indices are obtained through the system catalog.
+ *
+ * We assume the caller has whatever locks required.  This interface is not thread safe.
+ *
+ */
+class IndexAccessMethod {
+    MONGO_DISALLOW_COPYING(IndexAccessMethod);
+
+public:
+    IndexAccessMethod(IndexCatalogEntry* btreeState, SortedDataInterface* btree);
+    virtual ~IndexAccessMethod() {}
+
+    //
+    // Lookup, traversal, and mutation support
+    //
 
     /**
-     * An IndexAccessMethod is the interface through which all the mutation, lookup, and
-     * traversal of index entries is done. The class is designed so that the underlying index
-     * data structure is opaque to the caller.
-     *
-     * IndexAccessMethods for existing indices are obtained through the system catalog.
-     *
-     * We assume the caller has whatever locks required.  This interface is not thread safe.
+     * Internally generate the keys {k1, ..., kn} for 'obj'.  For each key k, insert (k ->
+     * 'loc') into the index.  'obj' is the object at the location 'loc'.  If not NULL,
+     * 'numInserted' will be set to the number of keys added to the index for the document.  If
+     * there is more than one key for 'obj', either all keys will be inserted or none will.
      *
+     * The behavior of the insertion can be specified through 'options'.
      */
-    class IndexAccessMethod {
-        MONGO_DISALLOW_COPYING(IndexAccessMethod);
-    public:
+    Status insert(OperationContext* txn,
+                  const BSONObj& obj,
+                  const RecordId& loc,
+                  const InsertDeleteOptions& options,
+                  int64_t* numInserted);
 
-        IndexAccessMethod(IndexCatalogEntry* btreeState, SortedDataInterface* btree);
-        virtual ~IndexAccessMethod() { }
+    /**
+     * Analogous to above, but remove the records instead of inserting them.  If not NULL,
+     * numDeleted will be set to the number of keys removed from the index for the document.
+     */
+    Status remove(OperationContext* txn,
+                  const BSONObj& obj,
+                  const RecordId& loc,
+                  const InsertDeleteOptions& options,
+                  int64_t* numDeleted);
 
-        //
-        // Lookup, traversal, and mutation support
-        //
+    /**
+     * Checks whether the index entries for the document 'from', which is placed at location
+     * 'loc' on disk, can be changed to the index entries for the doc 'to'. Provides a ticket
+     * for actually performing the update.
+     *
+     * Returns an error if the update is invalid.  The ticket will also be marked as invalid.
+     * Returns OK if the update should proceed without error.  The ticket is marked as valid.
+     *
+     * There is no obligation to perform the update after performing validation.
+     */
+    Status validateUpdate(OperationContext* txn,
+                          const BSONObj& from,
+                          const BSONObj& to,
+                          const RecordId& loc,
+                          const InsertDeleteOptions& options,
+                          UpdateTicket* ticket,
+                          const MatchExpression* indexFilter);
 
-        /**
-         * Internally generate the keys {k1, ..., kn} for 'obj'.  For each key k, insert (k ->
-         * 'loc') into the index.  'obj' is the object at the location 'loc'.  If not NULL,
-         * 'numInserted' will be set to the number of keys added to the index for the document.  If
-         * there is more than one key for 'obj', either all keys will be inserted or none will.
-         *
-         * The behavior of the insertion can be specified through 'options'.
-         */
-        Status insert(OperationContext* txn,
-                      const BSONObj& obj,
-                      const RecordId& loc,
-                      const InsertDeleteOptions& options,
-                      int64_t* numInserted);
+    /**
+     * Perform a validated update.  The keys for the 'from' object will be removed, and the keys
+     * for the object 'to' will be added.  Returns OK if the update succeeded, failure if it did
+     * not.  If an update does not succeed, the index will be unmodified, and the keys for
+     * 'from' will remain.  Assumes that the index has not changed since validateUpdate was
+     * called.  If the index was changed, we may return an error, as our ticket may have been
+     * invalidated.
+     */
+    Status update(OperationContext* txn, const UpdateTicket& ticket, int64_t* numUpdated);
 
-        /**
-         * Analogous to above, but remove the records instead of inserting them.  If not NULL,
-         * numDeleted will be set to the number of keys removed from the index for the document.
-         */
-        Status remove(OperationContext* txn,
-                      const BSONObj& obj,
-                      const RecordId& loc,
-                      const InsertDeleteOptions& options,
-                      int64_t* numDeleted);
+    /**
+     * Returns an unpositioned cursor over 'this' index.
+     */
+    std::unique_ptr<SortedDataInterface::Cursor> newCursor(OperationContext* txn,
+                                                           bool isForward = true) const;
 
-        /**
-         * Checks whether the index entries for the document 'from', which is placed at location
-         * 'loc' on disk, can be changed to the index entries for the doc 'to'. Provides a ticket
-         * for actually performing the update.
-         *
-         * Returns an error if the update is invalid.  The ticket will also be marked as invalid.
-         * Returns OK if the update should proceed without error.  The ticket is marked as valid.
-         *
-         * There is no obligation to perform the update after performing validation.
-         */
-        Status validateUpdate(OperationContext* txn,
-                              const BSONObj& from,
-                              const BSONObj& to,
-                              const RecordId& loc,
-                              const InsertDeleteOptions& options,
-                              UpdateTicket* ticket,
-                              const MatchExpression* indexFilter);
+    // ------ index level operations ------
 
-        /**
-         * Perform a validated update.  The keys for the 'from' object will be removed, and the keys
-         * for the object 'to' will be added.  Returns OK if the update succeeded, failure if it did
-         * not.  If an update does not succeed, the index will be unmodified, and the keys for
-         * 'from' will remain.  Assumes that the index has not changed since validateUpdate was
-         * called.  If the index was changed, we may return an error, as our ticket may have been
-         * invalidated.
-         */
-        Status update(OperationContext* txn, const UpdateTicket& ticket, int64_t* numUpdated);
 
-        /**
-         * Returns an unpositioned cursor over 'this' index.
-         */
-        std::unique_ptr<SortedDataInterface::Cursor> newCursor(OperationContext* txn,
-                                                               bool isForward = true) const;
+    /**
+     * initializes this index
+     * only called once for the lifetime of the index
+     * if called multiple times, is an error
+     */
+    Status initializeAsEmpty(OperationContext* txn);
 
-        // ------ index level operations ------
+    /**
+     * Try to page-in the pages that contain the keys generated from 'obj'.
+     * This can be used to speed up future accesses to an index by trying to ensure the
+     * appropriate pages are not swapped out.
+     * See prefetch.cpp.
+     */
+    Status touch(OperationContext* txn, const BSONObj& obj);
 
+    /**
+     * this pages in the entire index
+     */
+    Status touch(OperationContext* txn) const;
 
-        /**
-         * initializes this index
-         * only called once for the lifetime of the index
-         * if called multiple times, is an error
-         */
-        Status initializeAsEmpty(OperationContext* txn);
+    /**
+     * Walk the entire index, checking the internal structure for consistency.
+     * Set numKeys to the number of keys in the index.
+     *
+     * 'output' is used to store results of validate when 'full' is true.
+     * If 'full' is false, 'output' may be NULL.
+     *
+     * Return OK if the index is valid.
+     *
+     * Currently wasserts that the index is invalid.  This could/should be changed in
+     * the future to return a Status.
+     */
+    Status validate(OperationContext* txn, bool full, int64_t* numKeys, BSONObjBuilder* output);
 
-        /**
-         * Try to page-in the pages that contain the keys generated from 'obj'.
-         * This can be used to speed up future accesses to an index by trying to ensure the
-         * appropriate pages are not swapped out.
-         * See prefetch.cpp.
-         */
-        Status touch(OperationContext* txn, const BSONObj& obj);
+    /**
+     * Add custom statistics about this index to BSON object builder, for display.
+     *
+     * 'scale' is a scaling factor to apply to all byte statistics.
+     *
+     * Returns true if stats were appended.
+     */
+    bool appendCustomStats(OperationContext* txn, BSONObjBuilder* result, double scale) const;
 
-        /**
-         * this pages in the entire index
-         */
-        Status touch(OperationContext* txn) const;
+    /**
+     * @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* txn) const;
 
-        /**
-         * Walk the entire index, checking the internal structure for consistency.
-         * Set numKeys to the number of keys in the index.
-         *
-         * 'output' is used to store results of validate when 'full' is true.
-         * If 'full' is false, 'output' may be NULL.
-         *
-         * Return OK if the index is valid.
-         *
-         * Currently wasserts that the index is invalid.  This could/should be changed in
-         * the future to return a Status.
-         */
-        Status validate(OperationContext* txn, bool full, int64_t* numKeys, BSONObjBuilder* output);
+    RecordId findSingle(OperationContext* txn, const BSONObj& key) const;
 
-        /**
-         * Add custom statistics about this index to BSON object builder, for display.
-         *
-         * 'scale' is a scaling factor to apply to all byte statistics.
-         *
-         * Returns true if stats were appended.
-         */
-        bool appendCustomStats(OperationContext* txn, BSONObjBuilder* result, double scale) const;
+    //
+    // Bulk operations support
+    //
 
+    class BulkBuilder {
+    public:
         /**
-         * @return The number of bytes consumed by this index.
-         *         Exactly what is counted is not defined based on padding, re-use, etc...
+         * Insert into the BulkBuilder as-if inserting into an IndexAccessMethod.
          */
-        long long getSpaceUsedBytes( OperationContext* txn ) const;
-
-        RecordId findSingle( OperationContext* txn, const BSONObj& key ) const;
-
-        //
-        // Bulk operations support
-        //
-
-        class BulkBuilder {
-        public:
-            /**
-             * Insert into the BulkBuilder as-if inserting into an IndexAccessMethod.
-             */
-            Status insert(OperationContext* txn,
-                          const BSONObj& obj,
-                          const RecordId& loc,
-                          const InsertDeleteOptions& options,
-                          int64_t* numInserted);
+        Status insert(OperationContext* txn,
+                      const BSONObj& obj,
+                      const RecordId& loc,
+                      const InsertDeleteOptions& options,
+                      int64_t* numInserted);
 
-        private:
-            friend class IndexAccessMethod;
+    private:
+        friend class IndexAccessMethod;
 
-            using Sorter = mongo::Sorter<BSONObj, RecordId>;
+        using Sorter = mongo::Sorter<BSONObj, RecordId>;
 
-            BulkBuilder(const IndexAccessMethod* index, const IndexDescriptor* descriptor);
+        BulkBuilder(const IndexAccessMethod* index, const IndexDescriptor* descriptor);
 
-            std::unique_ptr<Sorter> _sorter;
-            const IndexAccessMethod* _real;
-            int64_t _keysInserted = 0;
-            bool _isMultiKey = false;
-        };
+        std::unique_ptr<Sorter> _sorter;
+        const IndexAccessMethod* _real;
+        int64_t _keysInserted = 0;
+        bool _isMultiKey = false;
+    };
 
-        /**
-         * Starts a bulk operation.
-         * You work on the returned BulkBuilder and then call commitBulk.
-         * This can return NULL, meaning bulk mode is not available.
-         *
-         * It is only legal to initiate bulk when the index is new and empty.
-         */
-        std::unique_ptr<BulkBuilder> initiateBulk();
+    /**
+     * Starts a bulk operation.
+     * You work on the returned BulkBuilder and then call commitBulk.
+     * This can return NULL, meaning bulk mode is not available.
+     *
+     * It is only legal to initiate bulk when the index is new and empty.
+     */
+    std::unique_ptr<BulkBuilder> initiateBulk();
 
-        /**
-         * Call this when you are ready to finish your bulk work.
-         * Pass in the BulkBuilder returned from initiateBulk.
-         * @param bulk - something created from initiateBulk
-         * @param mayInterrupt - is this commit interruptable (will cancel)
-         * @param dupsAllowed - if false, error or fill 'dups' if any duplicate values are found
-         * @param dups - if NULL, error out on dups if not allowed
-         *               if not NULL, put the bad RecordIds there
-         */
-        Status commitBulk(OperationContext* txn,
-                          std::unique_ptr<BulkBuilder> bulk,
-                          bool mayInterrupt,
-                          bool dupsAllowed,
-                          std::set<RecordId>* dups);
+    /**
+     * Call this when you are ready to finish your bulk work.
+     * Pass in the BulkBuilder returned from initiateBulk.
+     * @param bulk - something created from initiateBulk
+     * @param mayInterrupt - is this commit interruptable (will cancel)
+     * @param dupsAllowed - if false, error or fill 'dups' if any duplicate values are found
+     * @param dups - if NULL, error out on dups if not allowed
+     *               if not NULL, put the bad RecordIds there
+     */
+    Status commitBulk(OperationContext* txn,
+                      std::unique_ptr<BulkBuilder> bulk,
+                      bool mayInterrupt,
+                      bool dupsAllowed,
+                      std::set<RecordId>* dups);
 
-        /**
-         * Fills 'keys' with the keys that should be generated for 'obj' on this index.
-         */
-        virtual void getKeys(const BSONObj &obj, BSONObjSet *keys) const = 0;
+    /**
+     * Fills 'keys' with the keys that should be generated for 'obj' on this index.
+     */
+    virtual void getKeys(const BSONObj& obj, BSONObjSet* keys) const = 0;
 
-    protected:
-        // Determines whether it's OK to ignore ErrorCodes::KeyTooLong for this OperationContext
-        bool ignoreKeyTooLong(OperationContext* txn);
+protected:
+    // Determines whether it's OK to ignore ErrorCodes::KeyTooLong for this OperationContext
+    bool ignoreKeyTooLong(OperationContext* txn);
 
-        IndexCatalogEntry* _btreeState; // owned by IndexCatalogEntry
-        const IndexDescriptor* _descriptor;
+    IndexCatalogEntry* _btreeState;  // owned by IndexCatalogEntry
+    const IndexDescriptor* _descriptor;
 
-    private:
-        void removeOneKey(OperationContext* txn,
-                          const BSONObj& key,
-                          const RecordId& loc,
-                          bool dupsAllowed);
+private:
+    void removeOneKey(OperationContext* txn,
+                      const BSONObj& key,
+                      const RecordId& loc,
+                      bool dupsAllowed);
 
-        const std::unique_ptr<SortedDataInterface> _newInterface;
-    };
+    const std::unique_ptr<SortedDataInterface> _newInterface;
+};
 
-    /**
-     * Updates are two steps: verify that it's a valid update, and perform it.
-     * validateUpdate fills out the UpdateStatus and update actually applies it.
-     */
-    class UpdateTicket {
-        // No public interface
-    private:
-        friend class IndexAccessMethod;
+/**
+ * Updates are two steps: verify that it's a valid update, and perform it.
+ * validateUpdate fills out the UpdateStatus and update actually applies it.
+ */
+class UpdateTicket {
+    // No public interface
+private:
+    friend class IndexAccessMethod;
 
-        bool _isValid;
+    bool _isValid;
 
-        BSONObjSet oldKeys;
-        BSONObjSet newKeys;
+    BSONObjSet oldKeys;
+    BSONObjSet newKeys;
 
-        // These point into the sets oldKeys and newKeys.
-        std::vector<BSONObj*> removed;
-        std::vector<BSONObj*> added;
+    // These point into the sets oldKeys and newKeys.
+    std::vector<BSONObj*> removed;
+    std::vector<BSONObj*> added;
 
-        RecordId loc;
-        bool dupsAllowed;
-    };
+    RecordId loc;
+    bool dupsAllowed;
+};
 
-    /**
-     * Flags we can set for inserts and deletes (and updates, which are kind of both).
-     */
-    struct InsertDeleteOptions {
-        InsertDeleteOptions() : logIfError(false), dupsAllowed(false) { }
+/**
+ * Flags we can set for inserts and deletes (and updates, which are kind of both).
+ */
+struct InsertDeleteOptions {
+    InsertDeleteOptions() : logIfError(false), dupsAllowed(false) {}
 
-        // If there's an error, log() it.
-        bool logIfError;
+    // If there's an error, log() it.
+    bool logIfError;
 
-        // Are duplicate keys allowed in the index?
-        bool dupsAllowed;
-    };
+    // Are duplicate keys allowed in the index?
+    bool dupsAllowed;
+};
 
 }  // namespace mongo
diff --git a/src/mongo/db/index/index_descriptor.cpp b/src/mongo/db/index/index_descriptor.cpp
index 523b778163d..9d0de13b4d1 100644
--- a/src/mongo/db/index/index_descriptor.cpp
+++ b/src/mongo/db/index/index_descriptor.cpp
@@ -35,61 +35,54 @@
 
 namespace mongo {
 
-    namespace {
-        void populateOptionsMap( std::map<StringData, BSONElement>& theMap,
-                                 const BSONObj& spec ) {
-
-            BSONObjIterator it( spec );
-            while ( it.more() ) {
-                const BSONElement e = it.next();
-
-                StringData fieldName = e.fieldNameStringData();
-                if ( fieldName == "key" ||
-                     fieldName == "ns" ||
-                     fieldName == "name" ||
-                     fieldName == "v" || // not considered for equivalence
-                     fieldName == "textIndexVersion" || // same as "v"
-                     fieldName == "2dsphereIndexVersion" || // same as "v"
-                     fieldName == "background" || // this is a creation time option only
-                     fieldName == "dropDups" || // this is now ignored
-                     fieldName == "sparse" || // checked specially
-                     fieldName == "unique" // check specially
-                     ) {
-                    continue;
-                }
-                theMap[ fieldName ] = e;
-            }
+namespace {
+void populateOptionsMap(std::map<StringData, BSONElement>& theMap, const BSONObj& spec) {
+    BSONObjIterator it(spec);
+    while (it.more()) {
+        const BSONElement e = it.next();
+
+        StringData fieldName = e.fieldNameStringData();
+        if (fieldName == "key" || fieldName == "ns" || fieldName == "name" ||
+            fieldName == "v" ||                     // not considered for equivalence
+            fieldName == "textIndexVersion" ||      // same as "v"
+            fieldName == "2dsphereIndexVersion" ||  // same as "v"
+            fieldName == "background" ||            // this is a creation time option only
+            fieldName == "dropDups" ||              // this is now ignored
+            fieldName == "sparse" ||                // checked specially
+            fieldName == "unique"                   // check specially
+            ) {
+            continue;
         }
+        theMap[fieldName] = e;
     }
+}
+}
 
-    bool IndexDescriptor::areIndexOptionsEquivalent( const IndexDescriptor* other ) const {
-
-        if ( isSparse() != other->isSparse() ) {
-            return false;
-        }
-
-        if ( !isIdIndex() &&
-             unique() != other->unique() ) {
-            // Note: { _id: 1 } or { _id: -1 } implies unique: true.
-            return false;
-        }
+bool IndexDescriptor::areIndexOptionsEquivalent(const IndexDescriptor* other) const {
+    if (isSparse() != other->isSparse()) {
+        return false;
+    }
 
-        // Then compare the rest of the options.
+    if (!isIdIndex() && unique() != other->unique()) {
+        // Note: { _id: 1 } or { _id: -1 } implies unique: true.
+        return false;
+    }
 
-        std::map<StringData, BSONElement> existingOptionsMap;
-        populateOptionsMap( existingOptionsMap, infoObj() );
+    // Then compare the rest of the options.
 
-        std::map<StringData, BSONElement> newOptionsMap;
-        populateOptionsMap( newOptionsMap, other->infoObj() );
+    std::map<StringData, BSONElement> existingOptionsMap;
+    populateOptionsMap(existingOptionsMap, infoObj());
 
-        return existingOptionsMap == newOptionsMap;
-    }
+    std::map<StringData, BSONElement> newOptionsMap;
+    populateOptionsMap(newOptionsMap, other->infoObj());
 
-    void IndexDescriptor::_checkOk() const {
-        if ( _magic == 123987 )
-            return;
-        log() << "uh oh: " << (void*)(this) << " " << _magic;
-        invariant(0);
-    }
+    return existingOptionsMap == newOptionsMap;
+}
 
+void IndexDescriptor::_checkOk() const {
+    if (_magic == 123987)
+        return;
+    log() << "uh oh: " << (void*)(this) << " " << _magic;
+    invariant(0);
+}
 }
diff --git a/src/mongo/db/index/index_descriptor.h b/src/mongo/db/index/index_descriptor.h
index 742e5a3ea16..2bceb9aeb0a 100644
--- a/src/mongo/db/index/index_descriptor.h
+++ b/src/mongo/db/index/index_descriptor.h
@@ -39,181 +39,215 @@
 
 namespace mongo {
 
-    class IndexCatalog;
-    class IndexCatalogEntry;
-    class IndexCatalogEntryContainer;
+class IndexCatalog;
+class IndexCatalogEntry;
+class IndexCatalogEntryContainer;
 
+/**
+ * A cache of information computed from the memory-mapped per-index data (OnDiskIndexData).
+ * Contains accessors for the various immutable index parameters, and an accessor for the
+ * mutable "head" pointer which is index-specific.
+ *
+ * All synchronization is the responsibility of the caller.
+ */
+class IndexDescriptor {
+public:
     /**
-     * A cache of information computed from the memory-mapped per-index data (OnDiskIndexData).
-     * Contains accessors for the various immutable index parameters, and an accessor for the
-     * mutable "head" pointer which is index-specific.
-     *
-     * All synchronization is the responsibility of the caller.
+     * OnDiskIndexData is a pointer to the memory mapped per-index data.
+     * infoObj is a copy of the index-describing BSONObj contained in the OnDiskIndexData.
      */
-    class IndexDescriptor {
-    public:
-        /**
-         * OnDiskIndexData is a pointer to the memory mapped per-index data.
-         * infoObj is a copy of the index-describing BSONObj contained in the OnDiskIndexData.
-         */
-        IndexDescriptor(Collection* collection, const std::string& accessMethodName, BSONObj infoObj)
-            : _magic(123987),
-              _collection(collection),
-              _accessMethodName(accessMethodName),
-              _infoObj(infoObj.getOwned()),
-              _numFields(infoObj.getObjectField("key").nFields()),
-              _keyPattern(infoObj.getObjectField("key").getOwned()),
-              _indexName(infoObj.getStringField("name")),
-              _parentNS(infoObj.getStringField("ns")),
-              _isIdIndex(isIdIndexPattern( _keyPattern )),
-              _sparse(infoObj["sparse"].trueValue()),
-              _unique( _isIdIndex || infoObj["unique"].trueValue() ),
-              _partial(!infoObj["partialFilterExpression"].eoo()),
-              _cachedEntry( NULL )
-        {
-            _indexNamespace = makeIndexNamespace( _parentNS, _indexName );
-
-            _version = 0;
-            BSONElement e = _infoObj["v"];
-            if ( e.isNumber() ) {
-                _version = e.numberInt();
-            }
-        }
-
-        ~IndexDescriptor() {
-            _magic = 555;
-        }
-
-        //
-        // Information about the key pattern.
-        //
-
-        /**
-         * Return the user-provided index key pattern.
-         * Example: {geo: "2dsphere", nonGeo: 1}
-         * Example: {foo: 1, bar: -1}
-         */
-        const BSONObj& keyPattern() const { _checkOk(); return _keyPattern; }
-
-        // How many fields do we index / are in the key pattern?
-        int getNumFields() const { _checkOk(); return _numFields; }
-
-        //
-        // Information about the index's namespace / collection.
-        //
-
-        // Return the name of the index.
-        const std::string& indexName() const { _checkOk(); return _indexName; }
-
-        // Return the name of the indexed collection.
-        const std::string& parentNS() const { return _parentNS; }
-
-        // Return the name of this index's storage area (database.table.$index)
-        const std::string& indexNamespace() const { return _indexNamespace; }
-
-        // Return the name of the access method we must use to access this index's data.
-        const std::string& getAccessMethodName() const { return _accessMethodName; }
-
-        //
-        // Properties every index has
-        //
-
-        // Return what version of index this is.
-        int version() const { return _version; }
-
-        // May each key only occur once?
-        bool unique() const { return _unique; }
-
-        // Is this index sparse?
-        bool isSparse() const { return _sparse; }
-
-        // Is this a partial index?
-        bool isPartial() const { return _partial; }
-
-        // Is this index multikey?
-        bool isMultikey( OperationContext* txn ) const {
-            _checkOk();
-            return _collection->getIndexCatalog()->isMultikey( txn, this );
+    IndexDescriptor(Collection* collection, const std::string& accessMethodName, BSONObj infoObj)
+        : _magic(123987),
+          _collection(collection),
+          _accessMethodName(accessMethodName),
+          _infoObj(infoObj.getOwned()),
+          _numFields(infoObj.getObjectField("key").nFields()),
+          _keyPattern(infoObj.getObjectField("key").getOwned()),
+          _indexName(infoObj.getStringField("name")),
+          _parentNS(infoObj.getStringField("ns")),
+          _isIdIndex(isIdIndexPattern(_keyPattern)),
+          _sparse(infoObj["sparse"].trueValue()),
+          _unique(_isIdIndex || infoObj["unique"].trueValue()),
+          _partial(!infoObj["partialFilterExpression"].eoo()),
+          _cachedEntry(NULL) {
+        _indexNamespace = makeIndexNamespace(_parentNS, _indexName);
+
+        _version = 0;
+        BSONElement e = _infoObj["v"];
+        if (e.isNumber()) {
+            _version = e.numberInt();
         }
+    }
 
-        bool isIdIndex() const { _checkOk(); return _isIdIndex; }
-
-        //
-        // Properties that are Index-specific.
-        //
-
-        // Allow access to arbitrary fields in the per-index info object.  Some indices stash
-        // index-specific data there.
-        BSONElement getInfoElement(const std::string& name) const { return _infoObj[name]; }
+    ~IndexDescriptor() {
+        _magic = 555;
+    }
 
-        //
-        // "Internals" of accessing the index, used by IndexAccessMethod(s).
-        //
+    //
+    // Information about the key pattern.
+    //
 
-        // Return a (rather compact) std::string representation.
-        std::string toString() const { _checkOk(); return _infoObj.toString(); }
-
-        // Return the info object.
-        const BSONObj& infoObj() const { _checkOk(); return _infoObj; }
-
-        // Both the collection and the catalog must outlive the IndexDescriptor
-        const Collection* getCollection() const { return _collection; }
-        const IndexCatalog* getIndexCatalog() const { return _collection->getIndexCatalog(); }
-
-        bool areIndexOptionsEquivalent( const IndexDescriptor* other ) const;
-
-        static bool isIdIndexPattern( const BSONObj &pattern ) {
-            BSONObjIterator i(pattern);
-            BSONElement e = i.next();
-            //_id index must have form exactly {_id : 1} or {_id : -1}.
-            //Allows an index of form {_id : "hashed"} to exist but
-            //do not consider it to be the primary _id index
-            if(! ( strcmp(e.fieldName(), "_id") == 0
-                   && (e.numberInt() == 1 || e.numberInt() == -1)))
-                return false;
-             return i.next().eoo();
-        }
-
-        static std::string makeIndexNamespace( StringData ns,
-                                               StringData name ) {
-            return ns.toString() + ".$" + name.toString();
-        }
-
-    private:
-
-        void _checkOk() const;
-
-        int _magic;
-
-        // Related catalog information of the parent collection
-        Collection* _collection;
-
-        // What access method should we use for this index?
-        std::string _accessMethodName;
-
-        // The BSONObj describing the index.  Accessed through the various members above.
-        const BSONObj _infoObj;
-
-        // --- cached data from _infoObj
-
-        int64_t _numFields; // How many fields are indexed?
-        BSONObj _keyPattern;
-        std::string _indexName;
-        std::string _parentNS;
-        std::string _indexNamespace;
-        bool _isIdIndex;
-        bool _sparse;
-        bool _unique;
-        bool _partial;
-        int _version;
-
-        // only used by IndexCatalogEntryContainer to do caching for perf
-        // users not allowed to touch, and not part of API
-        IndexCatalogEntry* _cachedEntry;
-
-        friend class IndexCatalog;
-        friend class IndexCatalogEntry;
-        friend class IndexCatalogEntryContainer;
-    };
+    /**
+     * Return the user-provided index key pattern.
+     * Example: {geo: "2dsphere", nonGeo: 1}
+     * Example: {foo: 1, bar: -1}
+     */
+    const BSONObj& keyPattern() const {
+        _checkOk();
+        return _keyPattern;
+    }
+
+    // How many fields do we index / are in the key pattern?
+    int getNumFields() const {
+        _checkOk();
+        return _numFields;
+    }
+
+    //
+    // Information about the index's namespace / collection.
+    //
+
+    // Return the name of the index.
+    const std::string& indexName() const {
+        _checkOk();
+        return _indexName;
+    }
+
+    // Return the name of the indexed collection.
+    const std::string& parentNS() const {
+        return _parentNS;
+    }
+
+    // Return the name of this index's storage area (database.table.$index)
+    const std::string& indexNamespace() const {
+        return _indexNamespace;
+    }
+
+    // Return the name of the access method we must use to access this index's data.
+    const std::string& getAccessMethodName() const {
+        return _accessMethodName;
+    }
+
+    //
+    // Properties every index has
+    //
+
+    // Return what version of index this is.
+    int version() const {
+        return _version;
+    }
+
+    // May each key only occur once?
+    bool unique() const {
+        return _unique;
+    }
+
+    // Is this index sparse?
+    bool isSparse() const {
+        return _sparse;
+    }
+
+    // Is this a partial index?
+    bool isPartial() const {
+        return _partial;
+    }
+
+    // Is this index multikey?
+    bool isMultikey(OperationContext* txn) const {
+        _checkOk();
+        return _collection->getIndexCatalog()->isMultikey(txn, this);
+    }
+
+    bool isIdIndex() const {
+        _checkOk();
+        return _isIdIndex;
+    }
+
+    //
+    // Properties that are Index-specific.
+    //
+
+    // Allow access to arbitrary fields in the per-index info object.  Some indices stash
+    // index-specific data there.
+    BSONElement getInfoElement(const std::string& name) const {
+        return _infoObj[name];
+    }
+
+    //
+    // "Internals" of accessing the index, used by IndexAccessMethod(s).
+    //
+
+    // Return a (rather compact) std::string representation.
+    std::string toString() const {
+        _checkOk();
+        return _infoObj.toString();
+    }
+
+    // Return the info object.
+    const BSONObj& infoObj() const {
+        _checkOk();
+        return _infoObj;
+    }
+
+    // Both the collection and the catalog must outlive the IndexDescriptor
+    const Collection* getCollection() const {
+        return _collection;
+    }
+    const IndexCatalog* getIndexCatalog() const {
+        return _collection->getIndexCatalog();
+    }
+
+    bool areIndexOptionsEquivalent(const IndexDescriptor* other) const;
+
+    static bool isIdIndexPattern(const BSONObj& pattern) {
+        BSONObjIterator i(pattern);
+        BSONElement e = i.next();
+        //_id index must have form exactly {_id : 1} or {_id : -1}.
+        // Allows an index of form {_id : "hashed"} to exist but
+        // do not consider it to be the primary _id index
+        if (!(strcmp(e.fieldName(), "_id") == 0 && (e.numberInt() == 1 || e.numberInt() == -1)))
+            return false;
+        return i.next().eoo();
+    }
+
+    static std::string makeIndexNamespace(StringData ns, StringData name) {
+        return ns.toString() + ".$" + name.toString();
+    }
+
+private:
+    void _checkOk() const;
+
+    int _magic;
+
+    // Related catalog information of the parent collection
+    Collection* _collection;
+
+    // What access method should we use for this index?
+    std::string _accessMethodName;
+
+    // The BSONObj describing the index.  Accessed through the various members above.
+    const BSONObj _infoObj;
+
+    // --- cached data from _infoObj
+
+    int64_t _numFields;  // How many fields are indexed?
+    BSONObj _keyPattern;
+    std::string _indexName;
+    std::string _parentNS;
+    std::string _indexNamespace;
+    bool _isIdIndex;
+    bool _sparse;
+    bool _unique;
+    bool _partial;
+    int _version;
+
+    // only used by IndexCatalogEntryContainer to do caching for perf
+    // users not allowed to touch, and not part of API
+    IndexCatalogEntry* _cachedEntry;
+
+    friend class IndexCatalog;
+    friend class IndexCatalogEntry;
+    friend class IndexCatalogEntryContainer;
+};
 
 }  // namespace mongo
diff --git a/src/mongo/db/index/s2_access_method.cpp b/src/mongo/db/index/s2_access_method.cpp
index a9c9630ef67..3fcf4d013a1 100644
--- a/src/mongo/db/index/s2_access_method.cpp
+++ b/src/mongo/db/index/s2_access_method.cpp
@@ -44,67 +44,66 @@
 
 namespace mongo {
 
-    static const string kIndexVersionFieldName("2dsphereIndexVersion");
-
-    S2AccessMethod::S2AccessMethod(IndexCatalogEntry* btreeState, SortedDataInterface* btree)
-        : IndexAccessMethod(btreeState, btree) {
-
-        const IndexDescriptor* descriptor = btreeState->descriptor();
-
-        ExpressionParams::parse2dsphereParams(descriptor->infoObj(),
-                                              &_params);
-
-        int geoFields = 0;
-
-        // Categorize the fields we're indexing and make sure we have a geo field.
-        BSONObjIterator i(descriptor->keyPattern());
-        while (i.more()) {
-            BSONElement e = i.next();
-            if (e.type() == String && IndexNames::GEO_2DSPHERE == e.String() ) {
-                ++geoFields;
-            }
-            else {
-                // We check for numeric in 2d, so that's the check here
-                uassert( 16823, (string)"Cannot use " + IndexNames::GEO_2DSPHERE +
-                                    " index with other special index types: " + e.toString(),
-                         e.isNumber() );
-            }
-        }
-
-        uassert(16750, "Expect at least one geo field, spec=" + descriptor->keyPattern().toString(),
-                geoFields >= 1);
-
-        if (descriptor->isSparse()) {
-            warning() << "Sparse option ignored for index spec "
-                      << descriptor->keyPattern().toString() << "\n";
+static const string kIndexVersionFieldName("2dsphereIndexVersion");
+
+S2AccessMethod::S2AccessMethod(IndexCatalogEntry* btreeState, SortedDataInterface* btree)
+    : IndexAccessMethod(btreeState, btree) {
+    const IndexDescriptor* descriptor = btreeState->descriptor();
+
+    ExpressionParams::parse2dsphereParams(descriptor->infoObj(), &_params);
+
+    int geoFields = 0;
+
+    // Categorize the fields we're indexing and make sure we have a geo field.
+    BSONObjIterator i(descriptor->keyPattern());
+    while (i.more()) {
+        BSONElement e = i.next();
+        if (e.type() == String && IndexNames::GEO_2DSPHERE == e.String()) {
+            ++geoFields;
+        } else {
+            // We check for numeric in 2d, so that's the check here
+            uassert(16823,
+                    (string) "Cannot use " + IndexNames::GEO_2DSPHERE +
+                        " index with other special index types: " + e.toString(),
+                    e.isNumber());
         }
     }
 
-    // static
-    BSONObj S2AccessMethod::fixSpec(const BSONObj& specObj) {
-        // If the spec object has the field "2dsphereIndexVersion", validate it.  If it doesn't, add
-        // {2dsphereIndexVersion: 2}, which is the default for newly-built indexes.
-
-        BSONElement indexVersionElt = specObj[kIndexVersionFieldName];
-        if (indexVersionElt.eoo()) {
-            BSONObjBuilder bob;
-            bob.appendElements(specObj);
-            bob.append(kIndexVersionFieldName, S2_INDEX_VERSION_2);
-            return bob.obj();
-        }
+    uassert(16750,
+            "Expect at least one geo field, spec=" + descriptor->keyPattern().toString(),
+            geoFields >= 1);
 
-        const int indexVersion = indexVersionElt.numberInt();
-        uassert(17394,
-                str::stream() << "unsupported geo index version { " << kIndexVersionFieldName
-                              << " : " << indexVersionElt << " }, only support versions: ["
-                              << S2_INDEX_VERSION_1 << "," << S2_INDEX_VERSION_2 << "]",
-                indexVersionElt.isNumber() && (indexVersion == S2_INDEX_VERSION_2
-                                               || indexVersion == S2_INDEX_VERSION_1));
-        return specObj;
+    if (descriptor->isSparse()) {
+        warning() << "Sparse option ignored for index spec " << descriptor->keyPattern().toString()
+                  << "\n";
     }
-
-    void S2AccessMethod::getKeys(const BSONObj& obj, BSONObjSet* keys) const {
-        ExpressionKeysPrivate::getS2Keys(obj, _descriptor->keyPattern(), _params, keys);
+}
+
+// static
+BSONObj S2AccessMethod::fixSpec(const BSONObj& specObj) {
+    // If the spec object has the field "2dsphereIndexVersion", validate it.  If it doesn't, add
+    // {2dsphereIndexVersion: 2}, which is the default for newly-built indexes.
+
+    BSONElement indexVersionElt = specObj[kIndexVersionFieldName];
+    if (indexVersionElt.eoo()) {
+        BSONObjBuilder bob;
+        bob.appendElements(specObj);
+        bob.append(kIndexVersionFieldName, S2_INDEX_VERSION_2);
+        return bob.obj();
     }
 
+    const int indexVersion = indexVersionElt.numberInt();
+    uassert(17394,
+            str::stream() << "unsupported geo index version { " << kIndexVersionFieldName << " : "
+                          << indexVersionElt << " }, only support versions: [" << S2_INDEX_VERSION_1
+                          << "," << S2_INDEX_VERSION_2 << "]",
+            indexVersionElt.isNumber() &&
+                (indexVersion == S2_INDEX_VERSION_2 || indexVersion == S2_INDEX_VERSION_1));
+    return specObj;
+}
+
+void S2AccessMethod::getKeys(const BSONObj& obj, BSONObjSet* keys) const {
+    ExpressionKeysPrivate::getS2Keys(obj, _descriptor->keyPattern(), _params, keys);
+}
+
 }  // namespace mongo
diff --git a/src/mongo/db/index/s2_access_method.h b/src/mongo/db/index/s2_access_method.h
index 9ce655e47f7..15e0c3a773e 100644
--- a/src/mongo/db/index/s2_access_method.h
+++ b/src/mongo/db/index/s2_access_method.h
@@ -36,22 +36,22 @@
 
 namespace mongo {
 
-    class S2AccessMethod : public IndexAccessMethod {
-    public:
-        S2AccessMethod(IndexCatalogEntry* btreeState, SortedDataInterface* btree);
-
-        /**
-         * Takes an index spec object for this index and returns a copy tweaked to conform to the
-         * expected format.  When an index build is initiated, this function is called on the spec
-         * object the user provides, and the return value of this function is the final spec object
-         * that gets saved in the index catalog.  Throws a UserException if 'specObj' is invalid.
-         */
-        static BSONObj fixSpec(const BSONObj& specObj);
-
-    private:
-        virtual void getKeys(const BSONObj& obj, BSONObjSet* keys) const;
-
-        S2IndexingParams _params;
-    };
+class S2AccessMethod : public IndexAccessMethod {
+public:
+    S2AccessMethod(IndexCatalogEntry* btreeState, SortedDataInterface* btree);
+
+    /**
+     * Takes an index spec object for this index and returns a copy tweaked to conform to the
+     * expected format.  When an index build is initiated, this function is called on the spec
+     * object the user provides, and the return value of this function is the final spec object
+     * that gets saved in the index catalog.  Throws a UserException if 'specObj' is invalid.
+     */
+    static BSONObj fixSpec(const BSONObj& specObj);
+
+private:
+    virtual void getKeys(const BSONObj& obj, BSONObjSet* keys) const;
+
+    S2IndexingParams _params;
+};
 
 }  // namespace mongo
diff --git a/src/mongo/db/index/s2_common.h b/src/mongo/db/index/s2_common.h
index 3df3c833694..fad4087bb89 100644
--- a/src/mongo/db/index/s2_common.h
+++ b/src/mongo/db/index/s2_common.h
@@ -38,52 +38,52 @@
 
 namespace mongo {
 
-    // An enum describing the version of an S2 index.
-    enum S2IndexVersion {
-        // The first version of the S2 index, introduced in MongoDB 2.4.0.  Compatible with MongoDB
-        // 2.4.0 and later.  Supports the following GeoJSON objects: Point, LineString, Polygon.
-        S2_INDEX_VERSION_1 = 1,
+// An enum describing the version of an S2 index.
+enum S2IndexVersion {
+    // The first version of the S2 index, introduced in MongoDB 2.4.0.  Compatible with MongoDB
+    // 2.4.0 and later.  Supports the following GeoJSON objects: Point, LineString, Polygon.
+    S2_INDEX_VERSION_1 = 1,
 
-        // The current version of the S2 index, introduced in MongoDB 2.6.0.  Compatible with
-        // MongoDB 2.6.0 and later.  Introduced support for the following GeoJSON objects:
-        // MultiPoint, MultiLineString, MultiPolygon, GeometryCollection.
-        S2_INDEX_VERSION_2 = 2
-    };
+    // The current version of the S2 index, introduced in MongoDB 2.6.0.  Compatible with
+    // MongoDB 2.6.0 and later.  Introduced support for the following GeoJSON objects:
+    // MultiPoint, MultiLineString, MultiPolygon, GeometryCollection.
+    S2_INDEX_VERSION_2 = 2
+};
 
-    struct S2IndexingParams {
-        // Since we take the cartesian product when we generate keys for an insert,
-        // we need a cap.
-        size_t maxKeysPerInsert;
-        // This is really an advisory parameter that we pass to the cover generator.  The
-        // finest/coarsest index level determine the required # of cells.
-        int maxCellsInCovering;
-        // What's the finest grained level that we'll index?  When we query for a point
-        // we start at that -- we index nothing finer than this.
-        int finestIndexedLevel;
-        // And, what's the coarsest?  When we search in larger coverings we know we
-        // can stop here -- we index nothing coarser than this.
-        int coarsestIndexedLevel;
-        // Version of this index (specific to the index type).
-        S2IndexVersion indexVersion;
+struct S2IndexingParams {
+    // Since we take the cartesian product when we generate keys for an insert,
+    // we need a cap.
+    size_t maxKeysPerInsert;
+    // This is really an advisory parameter that we pass to the cover generator.  The
+    // finest/coarsest index level determine the required # of cells.
+    int maxCellsInCovering;
+    // What's the finest grained level that we'll index?  When we query for a point
+    // we start at that -- we index nothing finer than this.
+    int finestIndexedLevel;
+    // And, what's the coarsest?  When we search in larger coverings we know we
+    // can stop here -- we index nothing coarser than this.
+    int coarsestIndexedLevel;
+    // Version of this index (specific to the index type).
+    S2IndexVersion indexVersion;
 
-        double radius;
+    double radius;
 
-        std::string toString() const {
-            std::stringstream ss;
-            ss << "maxKeysPerInsert: " << maxKeysPerInsert << std::endl;
-            ss << "maxCellsInCovering: " << maxCellsInCovering << std::endl;
-            ss << "finestIndexedLevel: " << finestIndexedLevel << std::endl;
-            ss << "coarsestIndexedLevel: " << coarsestIndexedLevel << std::endl;
-            ss << "indexVersion: " << indexVersion << std::endl;
-            return ss.str();
-        }
+    std::string toString() const {
+        std::stringstream ss;
+        ss << "maxKeysPerInsert: " << maxKeysPerInsert << std::endl;
+        ss << "maxCellsInCovering: " << maxCellsInCovering << std::endl;
+        ss << "finestIndexedLevel: " << finestIndexedLevel << std::endl;
+        ss << "coarsestIndexedLevel: " << coarsestIndexedLevel << std::endl;
+        ss << "indexVersion: " << indexVersion << std::endl;
+        return ss.str();
+    }
 
-        void configureCoverer(S2RegionCoverer *coverer) const {
-            coverer->set_min_level(coarsestIndexedLevel);
-            coverer->set_max_level(finestIndexedLevel);
-            // This is advisory; the two above are strict.
-            coverer->set_max_cells(maxCellsInCovering);
-        }
-    };
+    void configureCoverer(S2RegionCoverer* coverer) const {
+        coverer->set_min_level(coarsestIndexedLevel);
+        coverer->set_max_level(finestIndexedLevel);
+        // This is advisory; the two above are strict.
+        coverer->set_max_cells(maxCellsInCovering);
+    }
+};
 
 }  // namespace mongo