Revert "SERVER-8192 rewritten V1 btree key generation"

This reverts commit 441b3c183c76399f248205989dec757708601394.

1 files changed, 32 insertions, 147 deletions

diff --git a/src/mongo/db/index/btree_key_generator.h b/src/mongo/db/index/btree_key_generator.h
index df866e9870c..2c1af304cb4 100644
--- a/src/mongo/db/index/btree_key_generator.h
+++ b/src/mongo/db/index/btree_key_generator.h
@@ -43,7 +43,9 @@ namespace mongo {
         BtreeKeyGenerator(std::vector<const char*> fieldNames, std::vector<BSONElement> fixed, bool isSparse);
         virtual ~BtreeKeyGenerator() { }
 
-        Status getKeys(const BSONObj &obj, BSONObjSet *keys) const;
+        void getKeys(const BSONObj &obj, BSONObjSet *keys) const;
+
+        static const int ParallelArraysCode;
 
     protected:
         // These are used by the getKeysImpl(s) below.
@@ -55,9 +57,9 @@ namespace mongo {
         BSONSizeTracker _sizeTracker;
     private:
         // We have V0 and V1.  Sigh.
-        virtual Status getKeysImpl(std::vector<const char*> fieldNames, std::vector<BSONElement> fixed,
-                                   const BSONObj &obj, BSONObjSet *keys) const = 0;
-        std::vector<BSONElement> _fixed;
+        virtual void getKeysImpl(vector<const char*> fieldNames, vector<BSONElement> fixed,
+                                 const BSONObj &obj, BSONObjSet *keys) const = 0;
+        vector<BSONElement> _fixed;
     };
 
     class BtreeKeyGeneratorV0 : public BtreeKeyGenerator {
@@ -65,10 +67,10 @@ namespace mongo {
         BtreeKeyGeneratorV0(std::vector<const char*> fieldNames, std::vector<BSONElement> fixed,
                             bool isSparse);
         virtual ~BtreeKeyGeneratorV0() { }
-        
+
     private:
-        virtual Status getKeysImpl(std::vector<const char*> fieldNames, std::vector<BSONElement> fixed,
-                                   const BSONObj &obj, BSONObjSet *keys) const;
+        virtual void getKeysImpl(vector<const char*> fieldNames, vector<BSONElement> fixed,
+                                 const BSONObj &obj, BSONObjSet *keys) const;
     };
 
     class BtreeKeyGeneratorV1 : public BtreeKeyGenerator {
@@ -78,151 +80,34 @@ namespace mongo {
         virtual ~BtreeKeyGeneratorV1() { }
 
     private:
-        // Our approach to generating keys is to generate key parts for one field in
-        // the key pattern at a time. A 'KeyElementList' stores the elements extracted
-        // from the original BSON object for each index field individually. There is one
-        // outer list per key pattern field; the inner lists store the extracted elements
-        // that will be used to construct the keys.
-        //
-        // Ex.
-        //   Say we have index {a: 1, b: 1} and we are generating keys for the object
-        //   {a: 3, b: [4, 5, 6]}. The first step is to construct the following KeyElementList:
-        //     [ [ El(3) ], [ El(4), El(5), El(6) ] ]
-        //   where the notation El(n) denotes a BSONElement for a numeric field.
-        typedef vector< vector<BSONElement> > KeyElementList;
-
-        // Btree key generation is a recursive process. As we recur through the input BSONObj,
-        // we pass along a 'KeygenContext', which wraps up any state we need about where we
-        // are in the keygen process.
-        struct KeygenContext {
-            // Index into '_keyPattern' corresponding to the field that we are currently
-            // generating fields for. Ex: For key pattern {a: 1, b: 1, c: 1}, 'kpIndex'
-            // will be set to 0 when generating keys for "a", 1 when generating keys for "b",
-            // and 2 when generating keys for "c".
-            size_t kpIndex;
-
-            // Index which keeps track of where we are in the path of the indexed field.
-            // Ex: Say we have key pattern {a: 1, "b.c.d": 1, e: 1}, and we are currently
-            // generating keys for "b.c.d" (i.e. kpIndex==1). Then 'pathPosition' will be 0
-            // when generating keys for "b", 1 when generating keys for "b.c", and 2 when
-            // generating keys for "b.c.d".
-            size_t pathPosition;
-
-            // Are we generating keys for an element of an indexed array?
-            bool inArray;
-        };
-
-        /**
-         * Top-level key generation implementation for V1 btree indices. Parameters:
-         *   'fieldNames' -- A list of the field names in the index key pattern. For index
-         *      {"a.b.c": 1, "foo": -1, "bar.0.a": 1}, then this will be ["a.b.c", "foo", "bar.0.a"]
-         *   'fixed' -- Required by the method signature in the superclass, but not used.
-         *   'obj' -- The object for which we will generate index keys.
-         *
-         * Returns the set of index keys generated from 'obj' according to the key pattern
-         * in 'fieldNames' through the out-parameter 'keys'.
-         */
-        virtual Status getKeysImpl(std::vector<const char*> fieldNames, std::vector<BSONElement> fixed,
-                                   const BSONObj &obj, BSONObjSet *keys) const;
-
-        /**
-         * Generates keys for the BSONElement 'el' according to the context in 'context' and
-         * the index key pattern stored in '_keyPattern'.
-         */
-        Status getKeysForElement(const BSONElement& el,
-                                 KeygenContext context,
-                                 std::vector<BSONElement>* out) const;
-
-        /**
-         * getKeysForElement(...) delegates to this function if 'el' is an indexed array. Special
-         * key generation logic for arrays lives here.
-         */
-        Status getKeysForArrayElement(const BSONElement& el,
-                                      KeygenContext context,
-                                      std::vector<BSONElement>* out) const;
-
         /**
-         * A helper for getKeysForArrayElement(...) which handles key patterns that have a
-         * positional element, such as {"a.0": 1}.
-         *
-         * Returns true through the out-parameter 'isPositional' if keys have been successively
-         * generated for a positional pattern. Otherwise sets 'isPositional' to false (returning
-         * a status of OK) and does nothing.
-         */
-        Status handlePositionalKeypattern(const BSONElement& el,
-                                          KeygenContext context,
-                                          bool* isPositional,
-                                          std::vector<BSONElement>* out) const;
-
-        /**
-         * getKeysForElement(...) delegates to this function if 'el' is neither an indexed
-         * array nor an indexed subobject.
-         */
-        Status getKeysForSimpleElement(const BSONElement& el,
-                                       KeygenContext context,
-                                       std::vector<BSONElement>* out) const;
-
+         * @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(vector<const char*> fieldNames, vector<BSONElement> fixed,
+                                 const BSONObj &obj, BSONObjSet *keys) const;
+
+        // These guys are called by getKeysImpl.
+        void getKeysImplWithArray(vector<const char*> fieldNames, vector<BSONElement> fixed,
+                                  const BSONObj &obj, BSONObjSet *keys, unsigned numNotFound,
+                                  const BSONObj &array) const;
         /**
-         * Outputs the final btree keys in 'keys', constructing them using the extracted
-         * BSONElements in 'kel'.
-         *
-         * Ex.
-         *   Continuing the example from above, suppose that 'kel' is as show below:
-         *     [ [ El(3) ], [ El(4), El(5), El(6) ] ]
-         *   We would return the following three keys:
-         *     {"": 3, "": 4}
-         *     {"": 3, "": 5}
-         *     {"": 3, "": 6}
+         * @param arrayNestedArray - set if the returned element is an array nested directly
+                                     within arr.
          */
-        void buildKeyObjects(const KeyElementList& kel, BSONObjSet *keys) const;
-
-        //
-        // Helper functions.
-        //
+        BSONElement extractNextElement(const BSONObj &obj, const BSONObj &arr, const char *&field,
+                                       bool &arrayNestedArray ) const;
+        void _getKeysArrEltFixed(vector<const char*> &fieldNames, vector<BSONElement> &fixed,
+                                 const BSONElement &arrEntry, BSONObjSet *keys,
+                                 unsigned numNotFound, const BSONElement &arrObjElt,
+                                 const set<unsigned> &arrIdxs, bool mayExpandArrayUnembedded) const;
 
-        /**
-         * Returns an error status if 'obj' has multiple arrays at position 'pathPosition' that
-         * are indexed. This is made illegal because it would require generating keys for the
-         * Cartesian product.
-         *
-         * Ex:
-         *   Say we have key pattern {"a.b": 1, "a.c": 1} and 'obj' is {a: {b: [1], c: [2]}}.
-         *   This method will return an error when 'pathPosition' is 1, as both "a.b" and "a.c"
-         *   are arrays.
-         */
-        Status checkForParallelArrays(const BSONObj& obj, size_t pathPosition) const;
-
-        /**
-         * Returns true if 'context' points to the last position in the path for the
-         * current field.
-         *
-         * Ex.
-         *   Say the keypattern is {"a": 1, "b.c.d": 1, "e": 1} and 'context.kpIndex'
-         *   is 1 (we are generating keys for "b.c.d"). This function will return true
-         *   if and only if 'context.pathPosition' is 2.
-         */
-        bool lastPathPosition(const KeygenContext& context) const;
-
-        //
-        // Member vars.
-        //
-
-        // A representation of the key pattern as a list of list of strings. There is one outer
-        // list per field in the index. Each of these fields is represented as a lit of the dotted
-        // path components.
-        //
-        // Ex.
-        //  Say the index is {"a.b.c": 1, "foo": -1, "bar.0.a": 1}. Then '_keyPattern' is:
-        //    [ [ "a", "b", "c" ],
-        //      [ "foo" ],
-        //      [ "bar", "0", "a" ] ]
-        typedef std::vector< std::vector<string> > KeyPattern;
-        KeyPattern _keyPattern;
-
-        // The BSONObj {"": undefined}.
         BSONObj _undefinedObj;
-
-        // A BSONElement containing value 'undefined'.
         BSONElement _undefinedElt;
     };