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

1 files changed, 771 insertions, 772 deletions

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