SERVER-13807 Remove old query framework related to shard targeting

14 files changed, 29 insertions, 5892 deletions

diff --git a/src/mongo/SConscript b/src/mongo/SConscript
index ae76cff908d..e4d27a05125 100644
--- a/src/mongo/SConscript
+++ b/src/mongo/SConscript
@@ -456,7 +456,6 @@ env.Library("coredb", [
         "db/pipeline/field_path.cpp",
         "db/pipeline/value.cpp",
         "db/projection.cpp",
-        "db/queryutil.cpp",
         "db/stats/timer_stats.cpp",
         "s/shardconnection.cpp",
         ]
diff --git a/src/mongo/db/commands/find_and_modify.cpp b/src/mongo/db/commands/find_and_modify.cpp
index e6b92512064..9d9e8d189a5 100644
--- a/src/mongo/db/commands/find_and_modify.cpp
+++ b/src/mongo/db/commands/find_and_modify.cpp
@@ -40,7 +40,6 @@
 #include "mongo/db/ops/delete.h"
 #include "mongo/db/ops/update.h"
 #include "mongo/db/ops/update_lifecycle_impl.h"
-#include "mongo/db/queryutil.h"
 #include "mongo/db/query/get_runner.h"
 #include "mongo/db/storage/mmap_v1/dur_transaction.h"
 
@@ -155,7 +154,7 @@ namespace mongo {
             }
 
             BSONObj queryModified = queryOriginal;
-            if ( found && doc["_id"].type() && ! isSimpleIdQuery( queryOriginal ) ) {
+            if ( found && doc["_id"].type() && ! CanonicalQuery::isSimpleIdQuery( queryOriginal ) ) {
                 // we're going to re-write the query to be more efficient
                 // we have to be a little careful because of positional operators
                 // maybe we can pass this all through eventually, but right now isn't an easy way
diff --git a/src/mongo/db/keypattern.cpp b/src/mongo/db/keypattern.cpp
index ecd44b448c4..222253e4c4d 100644
--- a/src/mongo/db/keypattern.cpp
+++ b/src/mongo/db/keypattern.cpp
@@ -31,7 +31,6 @@
 #include "mongo/db/keypattern.h"
 
 #include "mongo/db/hasher.h"
-#include "mongo/db/queryutil.h"
 #include "mongo/util/mongoutils/str.h"
 
 using namespace mongoutils;
@@ -136,87 +135,6 @@ namespace mongo {
         return newBound.obj();
     }
 
-    typedef vector<pair<BSONObj,BSONObj> >::const_iterator BoundListIter;
-
-    BoundList KeyPattern::keyBounds( const FieldRangeSet& queryConstraints ) const {
-        // To construct our bounds we will generate intervals based on constraints for
-        // the first field, then compound intervals based on constraints for the first
-        // 2 fields, then compound intervals for the first 3 fields, etc.
-        // As we loop through the fields, we start generating new intervals that will later
-        // get extended in another iteration of the loop.  We define these partially constructed
-        // intervals using pairs of BSONObjBuilders (shared_ptrs, since after one iteration of the
-        // loop they still must exist outside their scope).
-        typedef vector< pair< shared_ptr<BSONObjBuilder> ,
-                              shared_ptr<BSONObjBuilder> > > BoundBuilders;
-        BoundBuilders builders;
-        builders.push_back( make_pair( shared_ptr<BSONObjBuilder>( new BSONObjBuilder() ),
-                                       shared_ptr<BSONObjBuilder>( new BSONObjBuilder() ) ) );
-        BSONObjIterator i( _pattern );
-        // until equalityOnly is false, we are just dealing with equality (no range or $in queries).
-        bool equalityOnly = true;
-        while( i.more() ) {
-            BSONElement e = i.next();
-
-            // get the relevant intervals for this field, but we may have to transform the
-            // list of what's relevant according to the expression for this field
-            const FieldRange &fr = queryConstraints.range( e.fieldName() );
-            const vector<FieldInterval> &oldIntervals = fr.intervals();
-            BoundList fieldBounds = _transformFieldBounds( oldIntervals , e );
-
-            if ( equalityOnly ) {
-                if ( fieldBounds.size() == 1 &&
-                     ( fieldBounds.front().first == fieldBounds.front().second ) ){
-                    // this field is only a single point-interval
-                    BoundBuilders::const_iterator j;
-                    for( j = builders.begin(); j != builders.end(); ++j ) {
-                        j->first->appendElements( fieldBounds.front().first );
-                        j->second->appendElements( fieldBounds.front().first );
-                    }
-                }
-                else {
-                    // This clause is the first to generate more than a single point.
-                    // We only execute this clause once. After that, we simplify the bound
-                    // extensions to prevent combinatorial explosion.
-                    equalityOnly = false;
-
-                    BoundBuilders newBuilders;
-                    BoundBuilders::const_iterator i;
-                    for( i = builders.begin(); i != builders.end(); ++i ) {
-                        BSONObj first = i->first->obj();
-                        BSONObj second = i->second->obj();
-
-                        for(BoundListIter j = fieldBounds.begin(); j != fieldBounds.end(); ++j ) {
-                            uassert( 16452,
-                                     "combinatorial limit of $in partitioning of results exceeded" ,
-                                     newBuilders.size() < MAX_IN_COMBINATIONS );
-                            newBuilders.push_back(
-                                     make_pair( shared_ptr<BSONObjBuilder>( new BSONObjBuilder() ),
-                                                shared_ptr<BSONObjBuilder>( new BSONObjBuilder())));
-                            newBuilders.back().first->appendElements( first );
-                            newBuilders.back().second->appendElements( second );
-                            newBuilders.back().first->appendElements( j->first );
-                            newBuilders.back().second->appendElements( j->second );
-                        }
-                    }
-                    builders = newBuilders;
-                }
-            }
-            else {
-                // if we've already generated a range or multiple point-intervals
-                // just extend what we've generated with min/max bounds for this field
-                BoundBuilders::const_iterator j;
-                for( j = builders.begin(); j != builders.end(); ++j ) {
-                    j->first->appendElements( fieldBounds.front().first );
-                    j->second->appendElements( fieldBounds.back().second );
-                }
-            }
-        }
-        BoundList ret;
-        for( BoundBuilders::const_iterator i = builders.begin(); i != builders.end(); ++i )
-            ret.push_back( make_pair( i->first->obj(), i->second->obj() ) );
-        return ret;
-    }
-
     BoundList KeyPattern::keyBounds( const BSONObj& keyPattern, const IndexBounds& indexBounds ) {
         invariant(indexBounds.fields.size() == (size_t)keyPattern.nFields());
 
@@ -308,47 +226,4 @@ namespace mongo {
         return ret;
     }
 
-    BoundList KeyPattern::_transformFieldBounds( const vector<FieldInterval>& oldIntervals ,
-                                                 const BSONElement& field  ) const {
-
-        BoundList ret;
-        vector<FieldInterval>::const_iterator i;
-        for( i = oldIntervals.begin(); i != oldIntervals.end(); ++i ) {
-            if ( isAscending( field ) ){
-                // straightforward map [a,b] --> [a,b]
-                ret.push_back( make_pair( BSON( field.fieldName() << i->_lower._bound ) ,
-                                          BSON( field.fieldName() << i->_upper._bound ) ) );
-            } else if ( isDescending( field ) ) {
-                // reverse [a,b] --> [b,a]
-                ret.push_back( make_pair( BSON( field.fieldName() << i->_upper._bound ) ,
-                                          BSON( field.fieldName() << i->_lower._bound ) ) );
-            } else if ( isHashed( field ) ){
-                if ( i->equality() ) {
-                    // hash [a,a] --> [hash(a),hash(a)]
-                    long long int h = BSONElementHasher::hash64( i->_lower._bound ,
-                                                             BSONElementHasher::DEFAULT_HASH_SEED );
-                    ret.push_back( make_pair( BSON( field.fieldName() << h ) ,
-                                              BSON( field.fieldName() << h ) ) );
-                } else {
-                    // if it's a range interval and this field is hashed, just generate one
-                    // big interval from MinKey to MaxKey, since these vals could lie anywhere
-                    ret.clear();
-                    ret.push_back( make_pair( BSON( field.fieldName() << MINKEY ) ,
-                                              BSON( field.fieldName() << MAXKEY ) ) );
-                    break;
-                }
-            }
-        }
-
-        if ( isDescending( field ) ) {
-            // now order is [ [2,1], [4,3] , [6,5]....[n,n-1] ].  Reverse to get decreasing order.
-            reverse( ret.begin() , ret.end() );
-        } else if ( isHashed( field ) ){
-            // [ hash(a) , hash(b) , hash(c) ...] no longer in order, so sort before returning
-            sort( ret.begin() , ret.end() );
-        }
-
-        return ret;
-    }
-
 } // namespace mongo
diff --git a/src/mongo/db/keypattern.h b/src/mongo/db/keypattern.h
index 3e99a1c9d85..3e0eebfb613 100644
--- a/src/mongo/db/keypattern.h
+++ b/src/mongo/db/keypattern.h
@@ -38,9 +38,6 @@
 
 namespace mongo {
 
-    struct FieldInterval;
-    class FieldRangeSet;
-
     /**
      * A BoundList contains intervals specified by inclusive start
      * and end bounds.  The intervals should be nonoverlapping and occur in
@@ -61,6 +58,10 @@ namespace mongo {
      */
     class KeyPattern {
     public:
+
+        //maximum number of intervals produced by $in queries.
+        static const unsigned MAX_IN_COMBINATIONS = 4000000;
+
         /*
          * We are allowing implicit conversion from BSON
          */
@@ -148,32 +149,6 @@ namespace mongo {
          */
         BSONObj extractSingleKey( const BSONObj& doc ) const;
 
-        /**@param queryConstraints a FieldRangeSet, usually formed from parsing a query
-         * @return an ordered list of bounds generated using this KeyPattern and the
-         * constraints from the FieldRangeSet.  This function is used in sharding to
-         * determine where to route queries according to the shard key pattern.
-         *
-         * Examples:
-         * If this KeyPattern is { a : 1  }
-         * FieldRangeSet( {a : 5 } ) --> returns [{a : 5}, {a : 5 } ]
-         * FieldRangeSet( {a : {$gt : 3}} ) --> returns [({a : 3} , { a : MaxInt})]
-         *
-         * If this KeyPattern is { a : "hashed }
-         * FieldRangeSet( {a : 5 } --> returns [ ({ a : hash(5) }, {a : hash(5) }) ]
-         *
-         * The bounds returned by this function may be a superset of those defined
-         * by the constraints.  For instance, if this KeyPattern is {a : 1}
-         * FieldRanget( { a : {$in : [1,2]} , b : {$in : [3,4,5]} } )
-         *        --> returns [({a : 1 , b : 3} , {a : 1 , b : 5}]),
-         *                    [({a : 2 , b : 3} , {a : 2 , b : 5}])
-         *
-         * The queryConstraints should be defined for all the fields in this keypattern
-         * (i.e. the value of frsp->matchPossibleForSingleKeyFRS(_pattern) should be true,
-         * otherwise this function could throw).
-         *
-         */
-        BoundList keyBounds( const FieldRangeSet& queryConstraints ) const;
-
         /**
          * Return an ordered list of bounds generated using this KeyPattern and the
          * bounds from the IndexBounds.  This function is used in sharding to
@@ -228,13 +203,6 @@ namespace mongo {
             return ( fieldExpression.isNumber()  && fieldExpression.numberInt() == -1 );
         }
 
-        /* Takes a list of intervals corresponding to constraints on a given field
-         * in this keypattern, and transforms them into a list of bounds
-         * based on the expression for 'field'
-         */
-        BoundList _transformFieldBounds( const vector<FieldInterval>& oldIntervals ,
-                                         const BSONElement& field ) const;
-
     };
 
 } // namespace mongo
diff --git a/src/mongo/db/ops/update.cpp b/src/mongo/db/ops/update.cpp
index 33e082f8d32..8b0d7a506fe 100644
--- a/src/mongo/db/ops/update.cpp
+++ b/src/mongo/db/ops/update.cpp
@@ -48,7 +48,6 @@
 #include "mongo/db/query/lite_parsed_query.h"
 #include "mongo/db/query/query_planner_common.h"
 #include "mongo/db/query/runner_yield_policy.h"
-#include "mongo/db/queryutil.h"
 #include "mongo/db/repl/is_master.h"
 #include "mongo/db/repl/oplog.h"
 #include "mongo/db/storage/mmap_v1/dur_transaction.h"
diff --git a/src/mongo/db/queryutil-inl.h b/src/mongo/db/queryutil-inl.h
deleted file mode 100644
index 6d1b7a29d77..00000000000
--- a/src/mongo/db/queryutil-inl.h
+++ /dev/null
@@ -1,125 +0,0 @@
-// @file queryutil-inl.h - Inline definitions for frequently called queryutil.h functions
-
-/*    Copyright 2011 10gen Inc.
- *
- *    Licensed under the Apache License, Version 2.0 (the "License");
- *    you may not use this file except in compliance with the License.
- *    You may obtain a copy of the License at
- *
- *    http://www.apache.org/licenses/LICENSE-2.0
- *
- *    Unless required by applicable law or agreed to in writing, software
- *    distributed under the License is distributed on an "AS IS" BASIS,
- *    WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
- *    See the License for the specific language governing permissions and
- *    limitations under the License.
- */
-
-namespace mongo {
-    
-    inline bool FieldInterval::equality() const {
-        if ( _cachedEquality == -1 ) {
-            _cachedEquality = ( _lower._inclusive && _upper._inclusive && _lower._bound.woCompare( _upper._bound, false ) == 0 );
-        }
-        return _cachedEquality != 0;
-    }
-
-    inline bool FieldRange::equality() const {
-        return
-            !empty() &&
-            min().woCompare( max(), false ) == 0 &&
-            maxInclusive() &&
-            minInclusive();
-    }
-
-    inline const FieldRange &FieldRangeSet::range( const char *fieldName ) const {
-        map<string,FieldRange>::const_iterator f = _ranges.find( fieldName );
-        if ( f == _ranges.end() )
-            return universalRange();
-        return f->second;
-    }
-
-    inline FieldRange &FieldRangeSet::range( const char *fieldName ) {
-        map<string,FieldRange>::iterator f = _ranges.find( fieldName );
-        if ( f == _ranges.end() ) {
-            _ranges.insert( make_pair( string( fieldName ), universalRange() ) );
-            return _ranges.find( fieldName )->second;
-        }
-        return f->second;
-    }
-
-    inline bool FieldRangeSet::matchPossible() const {
-        for( map<string,FieldRange>::const_iterator i = _ranges.begin(); i != _ranges.end(); ++i ) {
-            if ( i->second.empty() ) {
-                return false;
-            }
-        }
-        return true;
-    }
-    
-    inline bool FieldRangeSet::matchPossibleForIndex( const BSONObj &keyPattern ) const {
-        if ( !_singleKey ) {
-            return matchPossible();   
-        }
-        BSONObjIterator i( keyPattern );
-        while( i.more() ) {
-            BSONElement e = i.next();
-            if ( e.fieldName() == string( "$natural" ) ) {
-                return true;
-            }
-            if ( range( e.fieldName() ).empty() ) {
-                return false;
-            }
-        }
-        return true;
-    }
-
-    inline unsigned FieldRangeVector::size() const {
-        unsigned ret = 1;
-        for( vector<FieldRange>::const_iterator i = _ranges.begin(); i != _ranges.end(); ++i ) {
-            unsigned long long product =
-                    (unsigned long long)ret * (unsigned long long)i->intervals().size();
-            // Check for overflow SERVER-5415.
-            verify( ( product >> 32 ) == 0 );
-            ret = static_cast<unsigned>( product );
-        }
-        return ret;
-    }
-    
-    inline void FieldRangeVectorIterator::CompoundRangeCounter::set( int i, int newVal ) {
-        resetIntervalCount();
-        _i[ i ] = newVal;
-    }
-    
-    inline void FieldRangeVectorIterator::CompoundRangeCounter::inc( int i ) {
-        resetIntervalCount();
-        ++_i[ i ];
-    }
-    
-    inline void FieldRangeVectorIterator::CompoundRangeCounter::setZeroes( int i ) {
-        resetIntervalCount();
-        for( int j = i; j < (int)_i.size(); ++j ) _i[ j ] = 0;
-    }
-    
-    inline void FieldRangeVectorIterator::CompoundRangeCounter::setUnknowns( int i ) {
-        resetIntervalCount();
-        for( int j = i; j < (int)_i.size(); ++j ) _i[ j ] = -1;
-    }
-
-    inline FieldRangeSetPair *OrRangeGenerator::topFrsp() const {
-        FieldRangeSetPair *ret = new FieldRangeSetPair( _baseSet );
-        if (_orSets.size()) {
-            *ret &= _orSets.front();
-        }
-        return ret;
-    }
-
-    inline FieldRangeSetPair *OrRangeGenerator::topFrspOriginal() const {
-        FieldRangeSetPair *ret = new FieldRangeSetPair( _baseSet );
-        if (_originalOrSets.size()) {
-            *ret &= _originalOrSets.front();
-        }
-        return ret;
-    }
-
-} // namespace mongo
diff --git a/src/mongo/db/queryutil.cpp b/src/mongo/db/queryutil.cpp
deleted file mode 100644
index d93e3f3d88d..00000000000
--- a/src/mongo/db/queryutil.cpp
+++ /dev/null
@@ -1,1894 +0,0 @@
-/*    Copyright 2009 10gen Inc.
- *
- *    Licensed under the Apache License, Version 2.0 (the "License");
- *    you may not use this file except in compliance with the License.
- *    You may obtain a copy of the License at
- *
- *    http://www.apache.org/licenses/LICENSE-2.0
- *
- *    Unless required by applicable law or agreed to in writing, software
- *    distributed under the License is distributed on an "AS IS" BASIS,
- *    WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
- *    See the License for the specific language governing permissions and
- *    limitations under the License.
- */
-
-#include "mongo/pch.h"
-
-#include "mongo/db/queryutil.h"
-
-#include "mongo/db/index_names.h"
-#include "mongo/db/matcher.h"
-#include "mongo/util/mongoutils/str.h"
-
-namespace mongo {
-
-    using namespace mongoutils;
-    using namespace mongoutils::str;
-
-    extern BSONObj staticNull;
-    extern BSONObj staticUndefined;
-
-    /** returns a string that when used as a matcher, would match a super set of regex()
-        returns "" for complex regular expressions
-        used to optimize queries in some simple regex cases that start with '^'
-
-        if purePrefix != NULL, sets it to whether the regex can be converted to a range query
-    */
-    string simpleRegex(const char* regex, const char* flags, bool* purePrefix) {
-        string r = "";
-
-        if (purePrefix) *purePrefix = false;
-
-        bool multilineOK;
-        if ( regex[0] == '\\' && regex[1] == 'A') {
-            multilineOK = true;
-            regex += 2;
-        }
-        else if (regex[0] == '^') {
-            multilineOK = false;
-            regex += 1;
-        }
-        else {
-            return r;
-        }
-
-        bool extended = false;
-        while (*flags) {
-            switch (*(flags++)) {
-            case 'm': // multiline
-                if (multilineOK)
-                    continue;
-                else
-                    return r;
-            case 'x': // extended
-                extended = true;
-                break;
-            default:
-                return r; // cant use index
-            }
-        }
-
-        stringstream ss;
-
-        while(*regex) {
-            char c = *(regex++);
-            if ( c == '*' || c == '?' ) {
-                // These are the only two symbols that make the last char optional
-                r = ss.str();
-                r = r.substr( 0 , r.size() - 1 );
-                return r; //breaking here fails with /^a?/
-            }
-            else if (c == '|') {
-                // whole match so far is optional. Nothing we can do here.
-                return string();
-            }
-            else if (c == '\\') {
-                c = *(regex++);
-                if (c == 'Q'){
-                    // \Q...\E quotes everything inside
-                    while (*regex) {
-                        c = (*regex++);
-                        if (c == '\\' && (*regex == 'E')){
-                            regex++; //skip the 'E'
-                            break; // go back to start of outer loop
-                        }
-                        else {
-                            ss << c; // character should match itself
-                        }
-                    }
-                }
-                else if ((c >= 'A' && c <= 'Z') ||
-                        (c >= 'a' && c <= 'z') ||
-                        (c >= '0' && c <= '0') ||
-                        (c == '\0')) {
-                    // don't know what to do with these
-                    r = ss.str();
-                    break;
-                }
-                else {
-                    // slash followed by non-alphanumeric represents the following char
-                    ss << c;
-                }
-            }
-            else if (strchr("^$.[()+{", c)) {
-                // list of "metacharacters" from man pcrepattern
-                r = ss.str();
-                break;
-            }
-            else if (extended && c == '#') {
-                // comment
-                r = ss.str();
-                break;
-            }
-            else if (extended && isspace(c)) {
-                continue;
-            }
-            else {
-                // self-matching char
-                ss << c;
-            }
-        }
-
-        if ( r.empty() && *regex == 0 ) {
-            r = ss.str();
-            if (purePrefix) *purePrefix = !r.empty();
-        }
-
-        return r;
-    }
-    inline string simpleRegex(const BSONElement& e) {
-        switch(e.type()) {
-        case RegEx:
-            return simpleRegex(e.regex(), e.regexFlags());
-        case Object: {
-            BSONObj o = e.embeddedObject();
-            return simpleRegex(o["$regex"].valuestrsafe(), o["$options"].valuestrsafe());
-        }
-        default: verify(false); return ""; //return squashes compiler warning
-        }
-    }
-
-    string simpleRegexEnd( string regex ) {
-        ++regex[ regex.length() - 1 ];
-        return regex;
-    }
-
-
-    FieldRange::FieldRange( const BSONElement &e, bool isNot, bool optimize ) :
-    _exactMatchRepresentation() {
-        int op = e.getGtLtOp();
-
-        // NOTE with $not, we could potentially form a complementary set of intervals.
-        if ( !isNot && !e.eoo() && e.type() != RegEx && op == BSONObj::opIN ) {
-            bool exactMatchesOnly = true;
-            set<BSONElement,element_lt> vals;
-            vector<FieldRange> regexes;
-            uassert( 12580 , "invalid query" , e.isABSONObj() );
-            BSONObjIterator i( e.embeddedObject() );
-            while( i.more() ) {
-                BSONElement ie = i.next();
-                uassert( 15881, "$elemMatch not allowed within $in",
-                         ie.type() != Object ||
-                         ie.embeddedObject().firstElement().getGtLtOp() != BSONObj::opELEM_MATCH );
-                if ( ie.type() == RegEx ) {
-                    exactMatchesOnly = false;
-                    regexes.push_back( FieldRange( ie, false, optimize ) );
-                }
-                else {
-                    // A document array may be indexed by its first element, by undefined
-                    // if it is empty, or as a full array if it is embedded within another
-                    // array.
-                    vals.insert( ie );                        
-                    if ( ie.type() == Array ) {
-                        exactMatchesOnly = false;
-                        BSONElement temp = ie.embeddedObject().firstElement();
-                        if ( temp.eoo() ) {
-                            temp = staticUndefined.firstElement();
-                        }                        
-                        vals.insert( temp );
-                    }
-                    if ( ie.isNull() ) {
-                        // A null index key will not always match a null query value (eg
-                        // SERVER-4529).  As a result, a field range containing null cannot be an
-                        // exact match representation.
-                        exactMatchesOnly = false;
-                    }
-                }
-            }
-
-            _exactMatchRepresentation = exactMatchesOnly;
-            for( set<BSONElement,element_lt>::const_iterator i = vals.begin(); i != vals.end(); ++i )
-                _intervals.push_back( FieldInterval(*i) );
-
-            for( vector<FieldRange>::const_iterator i = regexes.begin(); i != regexes.end(); ++i )
-                *this |= *i;
-
-            return;
-        }
-
-        // A document array may be indexed by its first element, by undefined
-        // if it is empty, or as a full array if it is embedded within another
-        // array.
-        if ( e.type() == Array && op == BSONObj::Equality ) {
-
-            _intervals.push_back( FieldInterval(e) );
-            BSONElement temp = e.embeddedObject().firstElement();
-            if ( temp.eoo() ) {
-             	temp = staticUndefined.firstElement();
-            }
-            if ( temp < e ) {
-                _intervals.insert( _intervals.begin() , temp );
-            }
-            else {
-                _intervals.push_back( FieldInterval(temp) );
-            }
-
-            return;
-        }
-
-        _intervals.push_back( FieldInterval() );
-        FieldInterval &initial = _intervals[ 0 ];
-        BSONElement &lower = initial._lower._bound;
-        bool &lowerInclusive = initial._lower._inclusive;
-        BSONElement &upper = initial._upper._bound;
-        bool &upperInclusive = initial._upper._inclusive;
-        lower = minKey.firstElement();
-        lowerInclusive = true;
-        upper = maxKey.firstElement();
-        upperInclusive = true;
-
-        if ( e.eoo() ) {
-            _exactMatchRepresentation = true;
-            return;
-        }
-
-        bool existsSpec = false;
-        if ( op == BSONObj::opEXISTS ) {
-            existsSpec = e.trueValue();
-        }
-        
-        if ( e.type() == RegEx
-                || (e.type() == Object && !e.embeddedObject()["$regex"].eoo())
-           ) {
-            uassert( 13454, "invalid regular expression operator", op == BSONObj::Equality || op == BSONObj::opREGEX );
-            if ( !isNot ) { // no optimization for negated regex - we could consider creating 2 intervals comprising all nonmatching prefixes
-                const string r = simpleRegex(e);
-                if ( r.size() ) {
-                    lower = addObj( BSON( "" << r ) ).firstElement();
-                    upper = addObj( BSON( "" << simpleRegexEnd( r ) ) ).firstElement();
-                    upperInclusive = false;
-                }
-                else {
-                    BSONObjBuilder b1(32), b2(32);
-                    b1.appendMinForType( "" , String );
-                    lower = addObj( b1.obj() ).firstElement();
-
-                    b2.appendMaxForType( "" , String );
-                    upper = addObj( b2.obj() ).firstElement();
-                    upperInclusive = false; //MaxForType String is an empty Object
-                }
-
-                // regex matches self - regex type > string type
-                if (e.type() == RegEx) {
-                    BSONElement re = addObj( BSON( "" << e ) ).firstElement();
-                    _intervals.push_back( FieldInterval(re) );
-                }
-                else {
-                    BSONObj orig = e.embeddedObject();
-                    BSONObjBuilder b;
-                    b.appendRegex("", orig["$regex"].valuestrsafe(), orig["$options"].valuestrsafe());
-                    BSONElement re = addObj( b.obj() ).firstElement();
-                    _intervals.push_back( FieldInterval(re) );
-                }
-
-            }
-            return;
-        }
-
-        // Identify simple cases where this FieldRange represents the exact set of BSONElement
-        // values matching the query expression element used to construct the FieldRange.
-
-        if ( // If type bracketing is enabled (see 'optimize' case at the end of this function) ...
-             optimize &&
-             // ... and the operator isn't within a $not clause ...
-             !isNot &&
-             // ... and the operand is of a type that implements exact type bracketing and will be
-             // exactly represented in an index key (eg is not null or an array) ...
-             e.isSimpleType() ) {
-            switch( op ) {
-                // ... and the operator is one for which this constructor will determine exact
-                // bounds on the values that match ...
-                case BSONObj::Equality:
-                case BSONObj::LT:
-                case BSONObj::LTE:
-                case BSONObj::GT:
-                case BSONObj::GTE:
-                    // ... then this FieldRange exactly characterizes those documents that match the
-                    // operator.
-                    _exactMatchRepresentation = true;
-                default:
-                    break;
-            }
-        }
-
-        if ( isNot ) {
-            switch( op ) {
-            case BSONObj::Equality:
-                return;
-//                    op = BSONObj::NE;
-//                    break;
-            case BSONObj::opALL:
-            case BSONObj::opMOD: // NOTE for mod and type, we could consider having 1-2 intervals comprising the complementary types (multiple intervals already possible with $in)
-            case BSONObj::opTYPE:
-                // no bound calculation
-                return;
-            case BSONObj::NE:
-                op = BSONObj::Equality;
-                break;
-            case BSONObj::LT:
-                op = BSONObj::GTE;
-                break;
-            case BSONObj::LTE:
-                op = BSONObj::GT;
-                break;
-            case BSONObj::GT:
-                op = BSONObj::LTE;
-                break;
-            case BSONObj::GTE:
-                op = BSONObj::LT;
-                break;
-            case BSONObj::opEXISTS:
-                existsSpec = !existsSpec;
-                break;
-            default: // otherwise doesn't matter
-                break;
-            }
-        }
-        switch( op ) {
-        case BSONObj::Equality:
-            lower = upper = e;
-            break;
-        case BSONObj::NE: {
-            // this will invalidate the upper/lower references above
-            _intervals.push_back( FieldInterval() );
-            // optimize doesn't make sense for negative ranges
-            _intervals[ 0 ]._upper._bound = e;
-            _intervals[ 0 ]._upper._inclusive = false;
-            _intervals[ 1 ]._lower._bound = e;
-            _intervals[ 1 ]._lower._inclusive = false;
-            _intervals[ 1 ]._upper._bound = maxKey.firstElement();
-            _intervals[ 1 ]._upper._inclusive = true;
-            optimize = false; // don't run optimize code below
-            break;
-        }
-        case BSONObj::LT:
-            upperInclusive = false;
-        case BSONObj::LTE:
-            upper = e;
-            break;
-        case BSONObj::GT:
-            lowerInclusive = false;
-        case BSONObj::GTE:
-            lower = e;
-            break;
-        case BSONObj::opALL: {
-            uassert( 10370 ,  "$all requires array", e.type() == Array );
-            BSONObjIterator i( e.embeddedObject() );
-            bool bound = false;
-            while ( i.more() ) {
-                BSONElement x = i.next();
-                if ( x.type() == Object && x.embeddedObject().firstElement().getGtLtOp() == BSONObj::opELEM_MATCH ) {
-                    // taken care of elsewhere
-                }
-                else if ( x.type() != RegEx ) {
-                    lower = upper = x;
-                    bound = true;
-                    break;
-                }
-            }
-            if ( !bound ) { // if no good non regex bound found, try regex bounds
-                BSONObjIterator i( e.embeddedObject() );
-                while( i.more() ) {
-                    BSONElement x = i.next();
-                    if ( x.type() != RegEx )
-                        continue;
-                    string simple = simpleRegex( x.regex(), x.regexFlags() );
-                    if ( !simple.empty() ) {
-                        lower = addObj( BSON( "" << simple ) ).firstElement();
-                        upper = addObj( BSON( "" << simpleRegexEnd( simple ) ) ).firstElement();
-                        break;
-                    }
-                }
-            }
-            break;
-        }
-        case BSONObj::opMOD: {
-            {
-                BSONObjBuilder b;
-                b.appendMinForType( "" , NumberDouble );
-                lower = addObj( b.obj() ).firstElement();
-            }
-            {
-                BSONObjBuilder b;
-                b.appendMaxForType( "" , NumberDouble );
-                upper = addObj( b.obj() ).firstElement();
-            }
-            break;
-        }
-        case BSONObj::opTYPE: {
-            BSONType t = (BSONType)e.numberInt();
-            {
-                BSONObjBuilder b;
-                b.appendMinForType( "" , t );
-                lower = addObj( b.obj() ).firstElement();
-            }
-            {
-                BSONObjBuilder b;
-                b.appendMaxForType( "" , t );
-                upper = addObj( b.obj() ).firstElement();
-            }
-
-            break;
-        }
-        case BSONObj::opREGEX:
-        case BSONObj::opOPTIONS:
-            // These operators are handled via their encapsulating object, so no bounds are
-            // generated for them individually.
-            break;
-        case BSONObj::opELEM_MATCH: {
-            log() << "warning: shouldn't get here?" << endl;
-            break;
-        }
-        case BSONObj::opWITHIN:
-            _special.add(IndexNames::GEO_2D, SpecialIndices::NO_INDEX_REQUIRED);
-            _special.add(IndexNames::GEO_2DSPHERE, SpecialIndices::NO_INDEX_REQUIRED);
-            break;
-        case BSONObj::opNEAR:
-            _special.add(IndexNames::GEO_2D, SpecialIndices::INDEX_REQUIRED);
-            _special.add(IndexNames::GEO_2DSPHERE, SpecialIndices::INDEX_REQUIRED);
-            break;
-        case BSONObj::opGEO_INTERSECTS:
-            _special.add(IndexNames::GEO_2DSPHERE, SpecialIndices::NO_INDEX_REQUIRED);
-            break;
-        case BSONObj::opEXISTS: {
-            if ( !existsSpec ) {
-                lower = upper = staticNull.firstElement();
-            }
-            optimize = false;
-            break;
-        }
-        default:
-            break;
-        }
-
-        // If 'optimize' is set, then bracket the field range by bson type.  For example, if this
-        // FieldRange is constructed with the operator { $gt:5 }, then the lower bound will be 5
-        // at this point but the upper bound will be MaxKey.  If 'optimize' is true, the upper bound
-        // is bracketed to the highest possible bson numeric value.  This is consistent with the
-        // Matcher's $gt implementation.
-
-        if ( optimize ) {
-            if ( lower.type() != MinKey && upper.type() == MaxKey && lower.isSimpleType() ) { // TODO: get rid of isSimpleType
-                BSONObjBuilder b;
-                b.appendMaxForType( lower.fieldName() , lower.type() );
-                upper = addObj( b.obj() ).firstElement();
-                if ( upper.canonicalType() != lower.canonicalType() ) {
-                    // _exactMatchRepresentation will be set if lower.isSimpleType(), requiring that
-                    // this field range exactly describe the values matching its query operator.  If
-                    // lower's max for type is not of the same canonical type as lower, it is
-                    // assumed to be the lowest value of the next canonical type meaning the upper
-                    // bound should be exclusive.
-                    upperInclusive = false;
-                }
-            }
-            else if ( lower.type() == MinKey && upper.type() != MaxKey && upper.isSimpleType() ) { // TODO: get rid of isSimpleType
-                BSONObjBuilder b;
-                b.appendMinForType( upper.fieldName() , upper.type() );
-                lower = addObj( b.obj() ).firstElement();
-                if ( lower.canonicalType() != upper.canonicalType() ) {
-                    // _exactMatchRepresentation will be set if upper.isSimpleType(), requiring that
-                    // this field range exactly describe the values matching its query operator.  If
-                    // upper's min for type is not of the same canonical type as upper, it is
-                    // assumed to be the highest value of the previous canonical type meaning the
-                    // lower bound should be exclusive.
-                    lowerInclusive = false;
-                }
-            }
-        }
-
-    }
-
-    void FieldRange::finishOperation( const vector<FieldInterval> &newIntervals,
-                                     const FieldRange &other, bool exactMatchRepresentation ) {
-        _intervals = newIntervals;
-        for( vector<BSONObj>::const_iterator i = other._objData.begin(); i != other._objData.end(); ++i )
-            _objData.push_back( *i );
-        if (_special.empty() && !other._special.empty())
-            _special = other._special;
-        _exactMatchRepresentation = exactMatchRepresentation;
-        // A manipulated FieldRange may no longer be valid within a parent context.
-        _elemMatchContext = BSONElement();
-    }
-
-    /** @return the maximum of two lower bounds, considering inclusivity. */
-    static FieldBound maxLowerBound( const FieldBound& a, const FieldBound& b ) {
-        int cmp = a._bound.woCompare( b._bound, false );
-        if ( ( cmp == 0 && !b._inclusive ) || cmp < 0 )
-            return b;
-        return a;
-    }
-
-    /** @return the minimum of two upper bounds, considering inclusivity. */
-    static FieldBound minUpperBound( const FieldBound& a, const FieldBound& b ) {
-        int cmp = a._bound.woCompare( b._bound, false );
-        if ( ( cmp == 0 && !b._inclusive ) || cmp > 0 )
-            return b;
-        return a;
-    }
-
-    /**
-     * @return true when the overlap of two intervals is a valid interval.
-     * @param one, @param two - The intervals.
-     * @param result - The resulting overlap.
-     */
-    static bool fieldIntervalOverlap( const FieldInterval& one, const FieldInterval& two,
-                                      FieldInterval& result ) {
-        result._lower = maxLowerBound( one._lower, two._lower );
-        result._upper = minUpperBound( one._upper, two._upper );
-        return result.isStrictValid();
-    }
-
-    const FieldRange &FieldRange::intersect( const FieldRange &other, bool singleKey ) {
-        // If 'this' FieldRange is universal(), intersect by copying the 'other' range into 'this'.
-        if ( universal() ) {
-            SpecialIndices intersectSpecial = _special.combineWith(other._special);
-            *this = other;
-            _special = intersectSpecial;
-            return *this;
-        }
-        // Range intersections are not taken for multikey indexes.  See SERVER-958.
-        if ( !singleKey && !universal() ) {
-            SpecialIndices intersectSpecial = _special.combineWith(other._special);
-            // Pick 'other' range if it is smaller than or equal to 'this'.
-            if ( other <= *this ) {
-             	*this = other;
-            }
-            _exactMatchRepresentation = false;
-            _special = intersectSpecial;
-            return *this;
-        }
-        vector<FieldInterval> newIntervals;
-        vector<FieldInterval>::const_iterator i = _intervals.begin();
-        vector<FieldInterval>::const_iterator j = other._intervals.begin();
-        while( i != _intervals.end() && j != other._intervals.end() ) {
-            FieldInterval overlap;
-            if ( fieldIntervalOverlap( *i, *j, overlap ) ) {
-                // If the two intervals overlap, add the overlap to the result.
-                newIntervals.push_back( overlap );
-            }
-            // Increment the iterator with the current interval having the lower upper bound.  The
-            // next interval of this iterator may overlap with the current interval of the other
-            // iterator.
-            if ( i->_upper == minUpperBound( i->_upper, j->_upper ) ) {
-                ++i;
-            }
-            else {
-                ++j;
-            }
-        }
-        finishOperation( newIntervals, other,
-                         mustBeExactMatchRepresentation() &&
-                         other.mustBeExactMatchRepresentation() );
-        return *this;
-    }
-
-    /** Helper class for assembling a union of FieldRange objects. */
-    class RangeUnionBuilder : boost::noncopyable {
-    public:
-        RangeUnionBuilder() : _initial( true ) {}
-        /** @param next: Supply next ordered interval, ordered by _lower FieldBound. */
-        void nextOrderedInterval( const FieldInterval &next ) {
-            if ( _initial ) {
-                _tail = next;
-                _initial = false;
-                return;
-            }
-            if ( !handleDisjoint( next ) ) {
-                handleExtend( next );
-            }
-        }
-        void done() {
-            if ( !_initial ) {
-                _unionIntervals.push_back( _tail );
-            }
-        }
-        const vector<FieldInterval> &unionIntervals() const { return _unionIntervals; }
-    private:
-        /** If _tail and next are disjoint, next becomes the new _tail. */
-        bool handleDisjoint( const FieldInterval &next ) {
-            int cmp = _tail._upper._bound.woCompare( next._lower._bound, false );
-            if ( ( cmp < 0 ) ||
-                ( cmp == 0 && !_tail._upper._inclusive && !next._lower._inclusive ) ) {
-                _unionIntervals.push_back( _tail );
-                _tail = next;
-                return true;
-            }
-            return false;
-        }
-        /** Extend _tail to upper bound of next if necessary. */
-        void handleExtend( const FieldInterval &next ) {
-            int cmp = _tail._upper._bound.woCompare( next._upper._bound, false );
-            if ( ( cmp < 0 ) ||
-                ( cmp == 0 && !_tail._upper._inclusive && next._upper._inclusive ) ) {
-                _tail._upper = next._upper;
-            }            
-        }
-        bool _initial;
-        FieldInterval _tail;
-        vector<FieldInterval> _unionIntervals;
-    };
-
-    const FieldRange &FieldRange::operator|=( const FieldRange &other ) {
-        RangeUnionBuilder b;
-        vector<FieldInterval>::const_iterator i = _intervals.begin();
-        vector<FieldInterval>::const_iterator j = other._intervals.begin();
-        while( i != _intervals.end() && j != other._intervals.end() ) {
-            int cmp = i->_lower._bound.woCompare( j->_lower._bound, false );
-            if ( cmp < 0 || ( cmp == 0 && i->_lower._inclusive ) ) {
-                b.nextOrderedInterval( *i++ );
-            }
-            else {
-                b.nextOrderedInterval( *j++ );
-            }
-        }
-        while( i != _intervals.end() ) {
-            b.nextOrderedInterval( *i++ );
-        }
-        while( j != other._intervals.end() ) {
-            b.nextOrderedInterval( *j++ );
-        }
-        b.done();
-        finishOperation( b.unionIntervals(), other, false );
-        return *this;
-    }
-
-    const FieldRange &FieldRange::operator-=( const FieldRange &other ) {
-        vector<FieldInterval> newIntervals;
-        vector<FieldInterval>::iterator i = _intervals.begin();
-        vector<FieldInterval>::const_iterator j = other._intervals.begin();
-        while( i != _intervals.end() && j != other._intervals.end() ) {
-            int cmp = i->_lower._bound.woCompare( j->_lower._bound, false );
-            if ( cmp < 0 ||
-                    ( cmp == 0 && i->_lower._inclusive && !j->_lower._inclusive ) ) {
-                int cmp2 = i->_upper._bound.woCompare( j->_lower._bound, false );
-                if ( cmp2 < 0 ) {
-                    newIntervals.push_back( *i );
-                    ++i;
-                }
-                else if ( cmp2 == 0 ) {
-                    newIntervals.push_back( *i );
-                    if ( newIntervals.back()._upper._inclusive && j->_lower._inclusive ) {
-                        newIntervals.back()._upper._inclusive = false;
-                    }
-                    ++i;
-                }
-                else {
-                    newIntervals.push_back( *i );
-                    newIntervals.back()._upper = j->_lower;
-                    newIntervals.back()._upper.flipInclusive();
-                    int cmp3 = i->_upper._bound.woCompare( j->_upper._bound, false );
-                    if ( cmp3 < 0 ||
-                            ( cmp3 == 0 && ( !i->_upper._inclusive || j->_upper._inclusive ) ) ) {
-                        ++i;
-                    }
-                    else {
-                        i->_lower = j->_upper;
-                        i->_lower.flipInclusive();
-                        ++j;
-                    }
-                }
-            }
-            else {
-                int cmp2 = i->_lower._bound.woCompare( j->_upper._bound, false );
-                if ( cmp2 > 0 ||
-                        ( cmp2 == 0 && ( !i->_lower._inclusive || !j->_upper._inclusive ) ) ) {
-                    ++j;
-                }
-                else {
-                    int cmp3 = i->_upper._bound.woCompare( j->_upper._bound, false );
-                    if ( cmp3 < 0 ||
-                            ( cmp3 == 0 && ( !i->_upper._inclusive || j->_upper._inclusive ) ) ) {
-                        ++i;
-                    }
-                    else {
-                        i->_lower = j->_upper;
-                        i->_lower.flipInclusive();
-                        ++j;
-                    }
-                }
-            }
-        }
-        while( i != _intervals.end() ) {
-            newIntervals.push_back( *i );
-            ++i;
-        }
-        finishOperation( newIntervals, other, false );
-        return *this;
-    }
-
-    // TODO write a proper implementation that doesn't do a full copy
-    bool FieldRange::operator<=( const FieldRange &other ) const {
-        FieldRange temp = *this;
-        temp -= other;
-        return temp.empty();
-    }
-
-    bool FieldRange::universal() const {
-        if ( empty() ) {
-            return false;
-        }
-        if ( minKey.firstElement().woCompare( min(), false ) != 0 ) {
-            return false;
-        }
-        if ( maxKey.firstElement().woCompare( max(), false ) != 0 ) {
-            return false;
-        }
-        // TODO ensure that adjacent intervals are not possible (the two intervals should be
-        // merged), and just determine if the range is universal by testing _intervals.size() == 1.
-        for ( unsigned i = 1; i < _intervals.size(); ++i ) {
-            const FieldBound &prev = _intervals[ i-1 ]._upper;
-            const FieldBound &curr = _intervals[ i ]._lower;
-            if ( !prev._inclusive && !curr._inclusive ) {
-                return false;
-            }
-            if ( prev._bound.woCompare( curr._bound ) < 0 ) {
-                return false;
-            }
-        }
-        return true;
-    }
-
-    bool FieldRange::isPointIntervalSet() const {
-        if ( _intervals.empty() ) {
-            return false;
-        }
-        for( vector<FieldInterval>::const_iterator i = _intervals.begin(); i != _intervals.end();
-             ++i ) {
-            if ( !i->equality() ) {
-                return false;
-            }
-        }
-        return true;
-    }
-
-    void FieldRange::setExclusiveBounds() {
-        for( vector<FieldInterval>::iterator i = _intervals.begin(); i != _intervals.end(); ++i ) {
-            i->_lower._inclusive = false;
-            i->_upper._inclusive = false;
-        }
-    }
-
-    void FieldRange::reverse( FieldRange &ret ) const {
-        verify( _special.empty() );
-        ret._intervals.clear();
-        ret._objData = _objData;
-        for( vector<FieldInterval>::const_reverse_iterator i = _intervals.rbegin(); i != _intervals.rend(); ++i ) {
-            FieldInterval fi;
-            fi._lower = i->_upper;
-            fi._upper = i->_lower;
-            ret._intervals.push_back( fi );
-        }
-    }
-    
-    BSONObj FieldRange::addObj( const BSONObj &o ) {
-        _objData.push_back( o );
-        return o;
-    }
-
-    string FieldInterval::toString() const {
-        StringBuilder buf;
-        buf << ( _lower._inclusive ? "[" : "(" ) << " ";
-        buf << _lower._bound.toString( false );
-        buf << " , ";
-        buf << _upper._bound.toString( false );
-        buf << " " << ( _upper._inclusive ? "]" : ")" );
-        return buf.str();
-    }
-
-
-    string FieldRange::toString() const {
-        StringBuilder buf;
-        buf << "(FieldRange special: { " << _special.toString() << "} intervals: ";
-        for (vector<FieldInterval>::const_iterator i = _intervals.begin(); i != _intervals.end(); ++i) {
-            buf << i->toString() << " ";
-        }
-        buf << ")";
-        return buf.str();
-    }
-
-    SpecialIndices FieldRangeSet::getSpecial() const {
-        for (map<string, FieldRange>::const_iterator i = _ranges.begin(); i != _ranges.end(); i++) {
-            if (!i->second.getSpecial().empty()) {
-                return i->second.getSpecial();
-            }
-        }
-        return SpecialIndices();
-    }
-
-    /**
-     * Btree scanning for a multidimentional key range will yield a
-     * multidimensional box.  The idea here is that if an 'other'
-     * multidimensional box contains the current box we don't have to scan
-     * the current box.  If the 'other' box contains the current box in
-     * all dimensions but one, we can safely subtract the values of 'other'
-     * along that one dimension from the values for the current box on the
-     * same dimension.  In other situations, subtracting the 'other'
-     * box from the current box yields a result that is not a box (but
-     * rather can be expressed as a union of boxes).  We don't support
-     * such splitting currently in calculating index ranges.  Note that
-     * where I have said 'box' above, I actually mean sets of boxes because
-     * a field range can consist of multiple intervals.
-     */    
-    const FieldRangeSet &FieldRangeSet::operator-=( const FieldRangeSet &other ) {
-        int nUnincluded = 0;
-        string unincludedKey;
-        map<string,FieldRange>::const_iterator i = _ranges.begin();
-        map<string,FieldRange>::const_iterator j = other._ranges.begin();
-        while( nUnincluded < 2 && i != _ranges.end() && j != other._ranges.end() ) {
-            int cmp = i->first.compare( j->first );
-            if ( cmp == 0 ) {
-                if ( i->second <= j->second ) {
-                    // nothing
-                }
-                else {
-                    ++nUnincluded;
-                    unincludedKey = i->first;
-                }
-                ++i;
-                ++j;
-            }
-            else if ( cmp < 0 ) {
-                ++i;
-            }
-            else {
-                // other has a bound we don't, nothing can be done
-                return *this;
-            }
-        }
-        if ( j != other._ranges.end() ) {
-            // other has a bound we don't, nothing can be done
-            return *this;
-        }
-        if ( nUnincluded > 1 ) {
-            return *this;
-        }
-        if ( nUnincluded == 0 ) {
-            makeEmpty();
-            return *this;
-        }
-        // nUnincluded == 1
-        range( unincludedKey.c_str() ) -= other.range( unincludedKey.c_str() );
-        appendQueries( other );
-        return *this;
-    }
-    
-    const FieldRangeSet &FieldRangeSet::operator&=( const FieldRangeSet &other ) {
-        map<string,FieldRange>::iterator i = _ranges.begin();
-        map<string,FieldRange>::const_iterator j = other._ranges.begin();
-        while( i != _ranges.end() && j != other._ranges.end() ) {
-            int cmp = i->first.compare( j->first );
-            if ( cmp == 0 ) {
-                // Same field name, so find range intersection.
-                i->second.intersect( j->second, _singleKey );
-                ++i;
-                ++j;
-            }
-            else if ( cmp < 0 ) {
-                // Field present in *this.
-                ++i;
-            }
-            else {
-                // Field not present in *this, so add it.
-                range( j->first.c_str() ) = j->second;
-                ++j;
-            }
-        }
-        while( j != other._ranges.end() ) {
-            // Field not present in *this, add it.
-            range( j->first.c_str() ) = j->second;
-            ++j;
-        }
-        appendQueries( other );
-        return *this;
-    }    
-    
-    void FieldRangeSet::appendQueries( const FieldRangeSet &other ) {
-        for( vector<BSONObj>::const_iterator i = other._queries.begin(); i != other._queries.end(); ++i ) {
-            _queries.push_back( *i );
-        }
-    }
-    
-    void FieldRangeSet::makeEmpty() {
-        for( map<string,FieldRange>::iterator i = _ranges.begin(); i != _ranges.end(); ++i ) {
-            i->second.makeEmpty();
-        }
-    }    
-    
-    void FieldRangeSet::handleOp( const char* matchFieldName, const BSONElement& op, bool isNot,
-                                  bool optimize ) {
-        int opType = op.getGtLtOp();
-
-        // If the first $all element's first op is an $elemMatch, generate bounds for it
-        // and ignore the remaining $all elements.  SERVER-664
-        if ( opType == BSONObj::opALL ) {
-            uassert( 13050, "$all requires array", op.type() == Array );
-            BSONElement firstAllClause = op.embeddedObject().firstElement();
-            if ( firstAllClause.type() == Object ) {
-                BSONElement firstAllClauseOp = firstAllClause.embeddedObject().firstElement();
-                if ( firstAllClauseOp.getGtLtOp() == BSONObj::opELEM_MATCH ) {
-                    handleElemMatch( matchFieldName, firstAllClauseOp, isNot, optimize );
-                    return;
-                }
-            }
-        }
-
-        if ( opType == BSONObj::opELEM_MATCH ) {
-            handleElemMatch( matchFieldName, op, isNot, optimize );
-        }
-        else {
-            intersectMatchField( matchFieldName, op, isNot, optimize );
-        }
-    }
-
-    void FieldRangeSet::handleNotOp( const char* matchFieldName, const BSONElement& notOp,
-                                     bool optimize ) {
-        switch( notOp.type() ) {
-            case Object: {
-                BSONObjIterator notOpIterator( notOp.embeddedObject() );
-                while( notOpIterator.more() ) {
-                    BSONElement opToNegate = notOpIterator.next();
-                    uassert( 13034, "invalid use of $not",
-                             opToNegate.getGtLtOp() != BSONObj::Equality );
-                    handleOp( matchFieldName, opToNegate, true, optimize );
-                }
-                break;
-            }
-            case RegEx:
-                handleOp( matchFieldName, notOp, true, optimize );
-                break;
-            default:
-                uassert( 13041, "invalid use of $not", false );
-        }
-    }
-
-    void FieldRangeSet::handleElemMatch( const char* matchFieldName, const BSONElement& elemMatch,
-                                         bool isNot, bool optimize ) {
-        adjustMatchField();
-        if ( !_boundElemMatch ) {
-            return;
-        }
-        if ( isNot ) {
-            // SERVER-5740 $elemMatch queries may depend on multiple fields, so $not:$elemMatch
-            // cannot in general generate range constraints for a single field.
-            return;
-        }
-        BSONObj elemMatchObj = elemMatch.embeddedObjectUserCheck();
-        BSONElement firstElemMatchElement = elemMatchObj.firstElement();
-        if ( firstElemMatchElement.getGtLtOp() != BSONObj::Equality ||
-            str::equals( firstElemMatchElement.fieldName(), "$not" ) ) {
-            // Handle $elemMatch applied to top level elements (where $elemMatch fields are
-            // operators).  SERVER-1264
-            BSONObj namedMatchExpression = elemMatch.wrap( matchFieldName );
-            FieldRangeSet elemMatchRanges( _ns.c_str(),
-                                           namedMatchExpression,
-                                           true, // SERVER-4180 Generate single key index bounds.
-                                           optimize,
-                                           false // Prevent computing FieldRanges for nested
-                                                 // $elemMatch expressions, which the index key
-                                                 // generation implementation does not support.
-                                           );
-            *this &= elemMatchRanges;
-        }
-        else {
-            // Handle $elemMatch applied to nested elements ($elemMatch fields are not operators,
-            // but full match specifications).
-
-            FieldRangeSet elemMatchRanges( _ns.c_str(), elemMatchObj, _singleKey, optimize );
-            // Set the parent $elemMatch context on direct $elemMatch children (those with undotted
-            // field names).
-            for( map<string,FieldRange>::iterator i = elemMatchRanges._ranges.begin();
-                 i != elemMatchRanges._ranges.end(); ++i ) {
-                if ( !str::contains( i->first, '.' ) ) {
-                    i->second.setElemMatchContext( elemMatch );
-                }
-            }
-            scoped_ptr<FieldRangeSet> prefixedRanges
-                    ( elemMatchRanges.prefixed( matchFieldName ) );
-            *this &= *prefixedRanges;
-        }
-    }
-
-    void FieldRangeSet::handleConjunctionClauses( const BSONObj& clauses, bool optimize ) {
-        BSONObjIterator clausesIterator( clauses );
-        while( clausesIterator.more() ) {
-            BSONElement clause = clausesIterator.next();
-            uassert( 14817, "$and/$or elements must be objects", clause.type() == Object );
-            BSONObjIterator clauseIterator( clause.embeddedObject() );
-            while( clauseIterator.more() ) {
-                BSONElement matchElement = clauseIterator.next();
-                handleMatchField( matchElement, optimize );
-            }
-        }
-    }
-
-    void FieldRangeSet::handleMatchField( const BSONElement& matchElement, bool optimize ) {
-        const char* matchFieldName = matchElement.fieldName();
-        if ( matchFieldName[ 0 ] == '$' ) {
-            if ( str::equals( matchFieldName, "$and" ) ) {
-                uassert( 14816, "$and expression must be a nonempty array",
-                         matchElement.type() == Array &&
-                         matchElement.embeddedObject().nFields() > 0 );
-                handleConjunctionClauses( matchElement.embeddedObject(), optimize );
-                return;
-            }
-        
-            adjustMatchField();
-
-            if ( str::equals( matchFieldName, "$or" ) ) {
-                // Check for a singleton $or expression.
-                if ( matchElement.type() == Array &&
-                     matchElement.embeddedObject().nFields() == 1 ) {
-                    // Compute field bounds for a singleton $or expression as if it is a $and
-                    // expression.  With only one clause, the matching semantics are the same.
-                    // SERVER-6416
-                    handleConjunctionClauses( matchElement.embeddedObject(), optimize );
-                }
-                return;
-            }
-        
-            if ( str::equals( matchFieldName, "$nor" ) ) {
-                return;
-            }
-
-            if ( str::equals( matchFieldName, "$where" ) ) {
-                return;
-            }
-
-            if ( str::equals( matchFieldName, "$atomic" ) ||
-                 str::equals( matchFieldName, "$isolated" ) ) {
-                return;
-            }
-        }
-        
-        bool equality =
-            // Check for a parsable '$' operator within a match element, indicating the object
-            // should not be matched as is but parsed.
-            // NOTE This only checks for a '$' prefix in the first embedded field whereas Matcher
-            // checks all embedded fields.
-            ( getGtLtOp( matchElement ) == BSONObj::Equality ) &&
-            // Similarly check for the $not meta operator.
-            !( matchElement.type() == Object &&
-               str::equals( matchElement.embeddedObject().firstElementFieldName(), "$not" ) );
-
-        if ( equality ) {
-            intersectMatchField( matchFieldName, matchElement, false, optimize );
-            return;
-        }
-
-        bool untypedRegex =
-            ( matchElement.type() == Object ) &&
-            matchElement.embeddedObject().hasField( "$regex" );
-
-        if ( untypedRegex ) {
-            // $regex/$options pairs must be handled together and so are passed via the
-            // element encapsulating them.
-            intersectMatchField( matchFieldName, matchElement, false, optimize );
-            // Other elements may remain to be handled, below.
-        }
-
-        BSONObjIterator matchExpressionIterator( matchElement.embeddedObject() );
-        while( matchExpressionIterator.more() ) {
-            BSONElement opElement = matchExpressionIterator.next();
-            if ( str::equals( opElement.fieldName(), "$not" ) ) {
-                handleNotOp( matchFieldName, opElement, optimize );
-            }
-            else {
-                handleOp( matchFieldName, opElement, false, optimize );
-            }
-        }
-    }
-
-    FieldRangeSet::FieldRangeSet( const char *ns, const BSONObj &query, bool singleKey,
-                                 bool optimize ) :
-    _ns( ns ),
-    _queries( 1, query.getOwned() ),
-    _singleKey( singleKey ),
-    _exactMatchRepresentation( true ),
-    _boundElemMatch( true ) {
-        init( optimize );
-    }
-
-    FieldRangeSet::FieldRangeSet( const char* ns, const BSONObj& query, bool singleKey,
-                                  bool optimize, bool boundElemMatch ) :
-        _ns( ns ),
-        _queries( 1, query.getOwned() ),
-        _singleKey( singleKey ),
-        _exactMatchRepresentation( true ),
-        _boundElemMatch( boundElemMatch ) {
-        init( optimize );
-    }
-
-    void FieldRangeSet::init( bool optimize ) {
-        BSONObjIterator i( _queries[ 0 ] );
-        while( i.more() ) {
-            handleMatchField( i.next(), optimize );
-        }
-    }
-    
-    /**
-     * TODO When operators are refactored to a standard interface, a version of this should be
-     * part of that interface.
-     */
-    void FieldRangeSet::adjustMatchField() {
-        _exactMatchRepresentation = false;
-    }
-    
-    void FieldRangeSet::intersectMatchField( const char *fieldName, const BSONElement &matchElement,
-                                            bool isNot, bool optimize ) {
-        FieldRange &selectedRange = range( fieldName );
-        selectedRange.intersect( FieldRange( matchElement, isNot, optimize ), _singleKey );
-        if ( !selectedRange.mustBeExactMatchRepresentation() ) {
-            _exactMatchRepresentation = false;
-        }
-    }
-
-    /**
-     * @return true if @param range is universal or can be easily identified as a reverse universal
-     * range (see FieldRange::reverse()).
-     */
-    static bool universalOrReverseUniversalRange( const FieldRange& range ) {
-        if ( range.universal() ) {
-            return true;
-        }
-        if ( range.intervals().size() != 1 ) {
-            return false;
-        }
-        if ( !range.min().valuesEqual( maxKey.firstElement() ) ) {
-            return false;
-        }
-        if ( !range.max().valuesEqual( minKey.firstElement() ) ) {
-            return false;
-        }
-        return true;
-    }
-
-    FieldRangeVector::FieldRangeVector( const FieldRangeSet &frs, BSONObj keyPattern,
-                                        int direction ) :
-        _keyPattern(keyPattern),
-        _direction( direction >= 0 ? 1 : -1 ),
-        _hasAllIndexedRanges( true ) {
-        verify( frs.matchPossibleForIndex( keyPattern));
-        _queries = frs._queries;
-
-        // For key generation
-        BSONObjIterator it(_keyPattern);
-        while (it.more()) {
-            BSONElement elt = it.next();
-            _fieldNames.push_back(elt.fieldName());
-            _fixed.push_back(BSONElement());
-        }
-
-        _keyGenerator.reset(new BtreeKeyGeneratorV1(_fieldNames, _fixed, false));
-
-        map<string,BSONElement> topFieldElemMatchContexts;
-        BSONObjIterator i(keyPattern);
-        while( i.more() ) {
-            BSONElement e = i.next();
-            const FieldRange *range = &frs.range( e.fieldName() );
-            verify( !range->empty() );
-
-            if ( !frs.singleKey() ) {
-                // Some constraints across different fields cannot be correctly intersected on a
-                // multikey index.  SERVER-958
-                //
-                // Given a multikey index { 'a.b':1, 'a.c':1 } and query { 'a.b':3, 'a.c':3 } only
-                // the index field 'a.b' is constrained to the range [3, 3], while the index
-                // field 'a.c' is just constrained to be within minkey and maxkey.  This
-                // implementation ensures that the document { a:[ { b:3 }, { c:3 } ] }, which
-                // generates index keys { 'a.b':3, 'a.c':null } and { 'a.b':null and 'a.c':3 } will
-                // be retrieved for the query.
-                //
-                // However, if the query is instead { a:{ $elemMatch:{ b:3, c:3 } } } then the
-                // document { a:[ { b:3 }, { c:3 } ] } should not match the query and both index
-                // fields 'a.b' and 'a.c' are constrained to the range [3, 3].
-
-                // If no other field with the same topField has been constrained ...
-                string topField = str::before( e.fieldName(), '.' );
-                if ( topFieldElemMatchContexts.count( topField ) == 0 ) {
-                    // ... and this field is constrained ...
-                    if ( !range->universal() ) {
-                        // ... record this field's elemMatchContext for its topField.
-                        topFieldElemMatchContexts[ topField ] = range->elemMatchContext();
-                    }
-                }
-
-                // Else if an already constrained field is not an $elemMatch sibling of this field
-                // (does not share its elemMatchContext) ...
-                else if ( range->elemMatchContext().eoo() ||
-                          range->elemMatchContext().rawdata() !=
-                              topFieldElemMatchContexts[ topField ].rawdata() ) {
-                    // ... this field's parsed range cannot be used.
-                    range = &frs.universalRange();
-                    _hasAllIndexedRanges = false;
-                }
-            }
-
-            int number = (int) e.number(); // returns 0.0 if not numeric
-            bool forward = ( ( number >= 0 ? 1 : -1 ) * ( direction >= 0 ? 1 : -1 ) > 0 );
-            if ( forward ) {
-                _ranges.push_back( *range );
-            }
-            else {
-                _ranges.push_back( FieldRange( BSONObj().firstElement(), false, true ) );
-                range->reverse( _ranges.back() );
-            }
-            verify( !_ranges.back().empty() );
-        }
-        uassert( 13385, "combinatorial limit of $in partitioning of result set exceeded",
-                size() < MAX_IN_COMBINATIONS );
-    }    
-
-    bool FieldRangeVector::isSingleInterval() const {
-        size_t i = 0;
-
-        // Skip all equality ranges.
-        while( i < _ranges.size() && _ranges[ i ].equality() ) {
-            ++i;
-        }
-
-        // If there are no ranges left ...
-        if ( i >= _ranges.size() ) {
-            // ... then all ranges are equalities.
-            return true;
-        }
-
-        // If the first non equality range does not consist of a single interval ...
-        if ( _ranges[ i ].intervals().size() != 1 ) {
-            // ... then the full FieldRangeVector does not consist of a single interval.
-            return false;
-        }
-        ++i;
-
-        while( i < _ranges.size() ) {
-            // If a range after the first non equality is not universal ...
-            if ( !universalOrReverseUniversalRange( _ranges[ i ] ) ) {
-                // ... then the full FieldRangeVector does not consist of a single interval.
-                return false;
-            }
-            ++i;
-        }
-
-        // The FieldRangeVector consists of zero or more equalities, then zero or one inequality
-        // with a single interval, then zero or more universal ranges.
-        return true;
-    }
-
-    BSONObj FieldRangeVector::startKey() const {
-        BSONObjBuilder b;
-        BSONObjIterator keys(_keyPattern);
-        vector<FieldRange>::const_iterator i = _ranges.begin();
-        for( ; i != _ranges.end(); ++i, ++keys ) {
-            // Append lower bounds until an exclusive bound is found.
-            const FieldInterval &fi = i->intervals().front();
-            b.appendAs( fi._lower._bound, "" );
-            if ( !fi._lower._inclusive ) {
-                ++i;
-                ++keys;
-                break;
-            }
-        }
-        for( ; i != _ranges.end(); ++i, ++keys ) {
-            // After the first exclusive bound is found, use extreme values for subsequent fields.
-            // For example, on index { a:1, b:1 } with query { a:{ $gt: 5 } } the start key is
-            // { '':5, '':MaxKey }.
-            bool forward = ( ( (*keys).number() >= 0 ? 1 : -1 ) * _direction > 0 );
-            if ( forward ) {
-                b.appendMaxKey( "" );
-            }
-            else {
-                b.appendMinKey( "" );
-            }
-        }
-        return b.obj();
-    }
-
-    bool FieldRangeVector::startKeyInclusive() const {
-        for( vector<FieldRange>::const_iterator i = _ranges.begin(); i != _ranges.end(); ++i ) {
-            if( !i->intervals().front()._lower._inclusive ) {
-                return false;
-            }
-        }
-        return true;
-    }
-
-    BSONObj FieldRangeVector::endKey() const {
-        BSONObjBuilder b;
-        BSONObjIterator keys(_keyPattern);
-        vector<FieldRange>::const_iterator i = _ranges.begin();
-        for( ; i != _ranges.end(); ++i, ++keys ) {
-            // Append upper bounds until an exclusive bound is found.
-            const FieldInterval &fi = i->intervals().back();
-            b.appendAs( fi._upper._bound, "" );
-            if ( !fi._upper._inclusive ) {
-                ++i;
-                ++keys;
-                break;
-            }
-        }
-        for( ; i != _ranges.end(); ++i, ++keys ) {
-            // After the first exclusive bound is found, use extreme values for subsequent fields.
-            // For example, on index { a:1, b:1 } with query { a:{ $lt: 5 } } the end key is
-            // { '':5, '':MinKey }.
-            bool forward = ( ( (*keys).number() >= 0 ? 1 : -1 ) * _direction > 0 );
-            if ( forward ) {
-                b.appendMinKey( "" );
-            }
-            else {
-                b.appendMaxKey( "" );
-            }
-        }
-        return b.obj();
-    }
-
-    bool FieldRangeVector::endKeyInclusive() const {
-        for( vector<FieldRange>::const_iterator i = _ranges.begin(); i != _ranges.end(); ++i ) {
-            if( !i->intervals().front()._upper._inclusive ) {
-                return false;
-            }
-        }
-        return true;
-    }
-
-    BSONObj FieldRangeVector::obj() const {
-        BSONObjBuilder b;
-        BSONObjIterator k(_keyPattern);
-        for( int i = 0; i < (int)_ranges.size(); ++i ) {
-            BSONArrayBuilder a( b.subarrayStart( k.next().fieldName() ) );
-            for( vector<FieldInterval>::const_iterator j = _ranges[ i ].intervals().begin();
-                j != _ranges[ i ].intervals().end(); ++j ) {
-                a << BSONArray( BSON_ARRAY( j->_lower._bound << j->_upper._bound ).clientReadable() );
-            }
-            a.done();
-        }
-        return b.obj();
-    }
-    
-    FieldRange *FieldRangeSet::__universalRange = 0;
-    const FieldRange &FieldRangeSet::universalRange() const {
-        FieldRange *&ret = __universalRange;
-        if ( ret == 0 ) {
-            // TODO: SERVER-5112
-            ret = new FieldRange( BSONObj().firstElement(), false, true );
-        }
-        return *ret;
-    }
-
-    bool FieldRangeSet::isPointIntervalSet( const string& fieldname ) const {
-
-        const vector<FieldInterval>& intervals = range( fieldname.c_str() ).intervals();
-
-        if ( intervals.empty() ) {
-            return false;
-        }
-
-        vector<FieldInterval>::const_iterator i;
-        for(i = intervals.begin() ; i != intervals.end(); ++i){
-            if (! i->equality() ) {
-                return false;
-            }
-        }
-        return true;
-    }
-
-    int FieldRangeSet::numNonUniversalRanges() const {
-        int count = 0;
-        for( map<string,FieldRange>::const_iterator i = _ranges.begin(); i != _ranges.end(); ++i ) {
-            if ( !i->second.universal() )
-                ++count;
-        }
-        return count;
-    }
-
-    FieldRangeSet *FieldRangeSet::subset( const BSONObj &fields ) const {
-        FieldRangeSet *ret = new FieldRangeSet( ns(), BSONObj(), _singleKey, true );
-        BSONObjIterator i( fields );
-        while( i.more() ) {
-            BSONElement e = i.next();
-            if ( !range( e.fieldName() ).universal() ) {
-                ret->range( e.fieldName() ) = range( e.fieldName() );
-            }
-        }
-        ret->_queries = _queries;
-        return ret;
-    }
-
-    FieldRangeSet* FieldRangeSet::prefixed( const string& prefix ) const {
-        auto_ptr<FieldRangeSet> ret( new FieldRangeSet( ns(), BSONObj(), _singleKey, true ) );
-        for( map<string,FieldRange>::const_iterator i = ranges().begin(); i != ranges().end();
-            ++i ) {
-            string prefixedFieldName = prefix + "." + i->first;
-            ret->range( prefixedFieldName.c_str() ) = i->second;
-        }
-        ret->_queries = _queries;
-        return ret.release();
-    }
-
-    string FieldRangeSet::toString() const {
-        BSONObjBuilder bob;
-        for( map<string,FieldRange>::const_iterator i = _ranges.begin(); i != _ranges.end(); ++i ) {
-            bob << i->first << i->second.toString();
-        }
-        return bob.obj().jsonString();
-    }
-    
-    bool FieldRangeSetPair::noNonUniversalRanges() const {
-        return _singleKey.numNonUniversalRanges() == 0 && _multiKey.numNonUniversalRanges() == 0;
-    }
-
-    FieldRangeSetPair &FieldRangeSetPair::operator&=( const FieldRangeSetPair &other ) {
-        _singleKey &= other._singleKey;
-        _multiKey &= other._multiKey;
-        return *this;
-    }
-
-    FieldRangeSetPair &FieldRangeSetPair::operator-=( const FieldRangeSet &scanned ) {
-        _singleKey -= scanned;
-        _multiKey -= scanned;
-        return *this;            
-    }
-    
-    string FieldRangeSetPair::toString() const {
-        return BSON(
-                    "singleKey" << _singleKey.toString() <<
-                    "multiKey" << _multiKey.toString()
-                    ).jsonString();
-    }
-
-    bool FieldRangeVector::matchesElement( const BSONElement &e, int i, bool forward ) const {
-        bool eq;
-        int l = matchingLowElement( e, i, forward, eq );
-        return ( l % 2 == 0 ); // if we're inside an interval
-    }
-
-    // binary search for interval containing the specified element
-    // an even return value indicates that the element is contained within a valid interval
-    int FieldRangeVector::matchingLowElement( const BSONElement &e, int i, bool forward, bool &lowEquality ) const {
-        lowEquality = false;
-        int l = -1;
-        int h = _ranges[ i ].intervals().size() * 2;
-        while( l + 1 < h ) {
-            int m = ( l + h ) / 2;
-            BSONElement toCmp;
-            bool toCmpInclusive;
-            const FieldInterval &interval = _ranges[ i ].intervals()[ m / 2 ];
-            if ( m % 2 == 0 ) {
-                toCmp = interval._lower._bound;
-                toCmpInclusive = interval._lower._inclusive;
-            }
-            else {
-                toCmp = interval._upper._bound;
-                toCmpInclusive = interval._upper._inclusive;
-            }
-            int cmp = toCmp.woCompare( e, false );
-            if ( !forward ) {
-                cmp = -cmp;
-            }
-            if ( cmp < 0 ) {
-                l = m;
-            }
-            else if ( cmp > 0 ) {
-                h = m;
-            }
-            else {
-                if ( m % 2 == 0 ) {
-                    lowEquality = true;
-                }
-                int ret = m;
-                // if left match and inclusive, all good
-                // if left match and not inclusive, return right before left bound
-                // if right match and inclusive, return left bound
-                // if right match and not inclusive, return right bound
-                if ( ( m % 2 == 0 && !toCmpInclusive ) || ( m % 2 == 1 && toCmpInclusive ) ) {
-                    --ret;
-                }
-                return ret;
-            }
-        }
-        verify( l + 1 == h );
-        return l;
-    }
-
-    bool FieldRangeVector::matchesKey( const BSONObj &key ) const {
-        BSONObjIterator j( key );
-        BSONObjIterator k(_keyPattern);
-        for( int l = 0; l < (int)_ranges.size(); ++l ) {
-            int number = (int) k.next().number();
-            bool forward = ( number >= 0 ? 1 : -1 ) * ( _direction >= 0 ? 1 : -1 ) > 0;
-            if ( !matchesElement( j.next(), l, forward ) ) {
-                return false;
-            }
-        }
-        return true;
-    }
-    
-    bool FieldRangeVector::matches( const BSONObj &obj ) const {
-        bool ok = false;
-
-        BSONObjSet keys;
-
-        /**
-         * Key generation by design is behind the index interface.  There is an exception here
-         * because $or uses key generation to dedup its results.  When $or is fixed to not require
-         * this, key generation will be removed from here.
-         */
-        _keyGenerator->getKeys(obj, &keys);
-
-        // TODO The representation of matching keys could potentially be optimized
-        // more for the case at hand.  (For example, we can potentially consider
-        // fields individually instead of constructing several bson objects using
-        // multikey arrays.)  But getKeys() canonically defines the key set for a
-        // given object and for now we are using it as is.
-        for( BSONObjSet::const_iterator i = keys.begin(); i != keys.end(); ++i ) {
-            if ( matchesKey( *i ) ) {
-                ok = true;
-                break;
-            }
-        }
-
-        LOG(5) << "FieldRangeVector::matches() returns " << ok << endl;
-
-        return ok;
-    }
-
-    BSONObj FieldRangeVector::firstMatch( const BSONObj &obj ) const {
-        // NOTE Only works in forward direction.
-        verify( _direction >= 0 );
-        BSONObjCmp oc(_keyPattern);
-        BSONObjSet keys(oc);
-        // See FieldRangeVector::matches for comment on key generation.
-        _keyGenerator->getKeys(obj, &keys);
-        for( BSONObjSet::const_iterator i = keys.begin(); i != keys.end(); ++i ) {
-            if ( matchesKey( *i ) ) {
-                return *i;
-            }
-        }
-        return BSONObj();
-    }
-    
-    string FieldRangeVector::toString() const {
-        BSONObjBuilder bob;
-        BSONObjIterator i(_keyPattern);
-        for( vector<FieldRange>::const_iterator r = _ranges.begin();
-            r != _ranges.end() && i.more(); ++r ) {
-            BSONElement e = i.next();
-            bob << e.fieldName() << r->toString();
-        }
-        return bob.obj().jsonString();
-    }
-    
-    FieldRangeVectorIterator::FieldRangeVectorIterator( const FieldRangeVector &v,
-                                                       int singleIntervalLimit ) :
-    _v( v ),
-    _i( _v._ranges.size(), singleIntervalLimit ),
-    _cmp( _v._ranges.size(), 0 ),
-    _inc( _v._ranges.size(), false ),
-    _after(),
-    _endNonUniversalRanges( endNonUniversalRanges() ) {
-    }
-    
-    // TODO optimize more SERVER-5450.
-    int FieldRangeVectorIterator::advance( const BSONObj &curr ) {
-        BSONObjIterator j( curr );
-        BSONObjIterator o( _v._keyPattern);
-        // track first field for which we are not at the end of the valid values,
-        // since we may need to advance from the key prefix ending with this field
-        int latestNonEndpoint = -1;
-        // iterate over fields to determine appropriate advance method
-        for( int i = 0; i < _endNonUniversalRanges; ++i ) {
-            if ( i > 0 && !_v._ranges[ i - 1 ].intervals()[ _i.get( i - 1 ) ].equality() ) {
-                // if last bound was inequality, we don't know anything about where we are for this field
-                // TODO if possible avoid this certain cases when value in previous field of the previous
-                // key is the same as value of previous field in current key
-                _i.setUnknowns( i );
-            }
-            BSONElement oo = o.next();
-            bool reverse = ( ( oo.number() < 0 ) ^ ( _v._direction < 0 ) );
-            BSONElement jj = j.next();
-            if ( _i.get( i ) == -1 ) { // unknown position for this field, do binary search
-                bool lowEquality;
-                int l = _v.matchingLowElement( jj, i, !reverse, lowEquality );
-                if ( l % 2 == 0 ) { // we are in a valid range for this field
-                    _i.set( i, l / 2 );
-                    int diff = (int)_v._ranges[ i ].intervals().size() - _i.get( i );
-                    if ( diff > 1 ) {
-                        latestNonEndpoint = i;
-                    }
-                    else if ( diff == 1 ) {
-                        int x = _v._ranges[ i ].intervals()[ _i.get( i ) ]._upper._bound.woCompare( jj, false );
-                        if ( x != 0 ) {
-                            latestNonEndpoint = i;
-                        }
-                    }
-                    continue;
-                }
-                else {   // not in a valid range for this field - determine if and how to advance
-                    // check if we're after the last interval for this field
-                    if ( l == (int)_v._ranges[ i ].intervals().size() * 2 - 1 ) {
-                        if ( latestNonEndpoint == -1 ) {
-                            return -2;
-                        }
-                        return advancePastZeroed( latestNonEndpoint + 1 );
-                    }
-                    _i.set( i, ( l + 1 ) / 2 );
-                    if ( lowEquality ) {
-                        return advancePast( i + 1 );
-                    }
-                    return advanceToLowerBound( i );
-                }
-            }
-            bool first = true;
-            bool eq = false;
-            // _i.get( i ) != -1, so we have a starting interval for this field
-            // which serves as a lower/equal bound on the first iteration -
-            // we advance from this interval to find a matching interval
-            while( _i.get( i ) < (int)_v._ranges[ i ].intervals().size() ) {
-
-                int advanceMethod = validateCurrentInterval( i, jj, reverse, first, eq );
-                if ( advanceMethod >= 0 ) {
-                    return advanceMethod;
-                }
-                if ( advanceMethod == -1 && !hasReachedLimitForLastInterval( i ) ) {
-                    break;
-                }
-                // advance to next interval and reset remaining fields
-                _i.inc( i );
-                _i.setZeroes( i + 1 );
-                first = false;
-            }
-            int diff = (int)_v._ranges[ i ].intervals().size() - _i.get( i );
-            if ( diff > 1 || ( !eq && diff == 1 ) ) {
-                // check if we're not at the end of valid values for this field
-                latestNonEndpoint = i;
-            }
-            else if ( diff == 0 ) {   // check if we're past the last interval for this field
-                if ( latestNonEndpoint == -1 ) {
-                    return -2;
-                }
-                // more values possible, skip...
-                return advancePastZeroed( latestNonEndpoint + 1 );
-            }
-        }
-        _i.incSingleIntervalCount();
-        return -1;
-    }
-
-    void FieldRangeVectorIterator::prepDive() {
-        for( int j = 0; j < _i.size(); ++j ) {
-            _cmp[ j ] = &_v._ranges[ j ].intervals().front()._lower._bound;
-            _inc[ j ] = _v._ranges[ j ].intervals().front()._lower._inclusive;
-        }
-        _i.resetIntervalCount();
-    }
-    
-    int FieldRangeVectorIterator::validateCurrentInterval( int intervalIdx,
-                                                          const BSONElement &currElt,
-                                                          bool reverse, bool first,
-                                                          bool &eqInclusiveUpperBound ) {
-        eqInclusiveUpperBound = false;
-        FieldIntervalMatcher matcher
-                ( _v._ranges[ intervalIdx ].intervals()[ _i.get( intervalIdx ) ], currElt,
-                 reverse );
-
-        if ( matcher.isEqInclusiveUpperBound() ) {
-            eqInclusiveUpperBound = true;
-            return -1;
-        }
-        if ( matcher.isGteUpperBound() ) {
-            return -2;
-        }
-
-        // below the upper bound
-
-        if ( intervalIdx == 0 && first ) {
-            // the value of 1st field won't go backward, so don't check lower bound
-            // TODO maybe we can check 'first' only?
-            return -1;
-        }
-
-        if ( matcher.isEqExclusiveLowerBound() ) {
-            return advancePastZeroed( intervalIdx + 1 );
-        }
-        if ( matcher.isLtLowerBound() ) {
-            _i.setZeroes( intervalIdx + 1 );
-            return advanceToLowerBound( intervalIdx );
-        }
-
-        return -1;
-    }
-    
-    int FieldRangeVectorIterator::advanceToLowerBound( int i ) {
-        _cmp[ i ] = &_v._ranges[ i ].intervals()[ _i.get( i ) ]._lower._bound;
-        _inc[ i ] = _v._ranges[ i ].intervals()[ _i.get( i ) ]._lower._inclusive;
-        for( int j = i + 1; j < _i.size(); ++j ) {
-            _cmp[ j ] = &_v._ranges[ j ].intervals().front()._lower._bound;
-            _inc[ j ] = _v._ranges[ j ].intervals().front()._lower._inclusive;
-        }
-        _after = false;
-        return i;
-    }
-    
-    int FieldRangeVectorIterator::advancePast( int i ) {
-        _after = true;
-        return i;
-    }
-    
-    int FieldRangeVectorIterator::advancePastZeroed( int i ) {
-        _i.setZeroes( i );
-        return advancePast( i );
-    }
-
-    int FieldRangeVectorIterator::endNonUniversalRanges() const {
-        int i = _v._ranges.size() - 1;
-        while( i > -1 && universalOrReverseUniversalRange( _v._ranges[ i ] ) ) {
-            --i;
-        }
-        return i + 1;
-    }
-
-    FieldRangeVectorIterator::CompoundRangeCounter::CompoundRangeCounter( int size,
-                                                                         int singleIntervalLimit ) :
-    _i( size, -1 ),
-    _singleIntervalCount(),
-    _singleIntervalLimit( singleIntervalLimit ) {
-    }
-    
-    string FieldRangeVectorIterator::CompoundRangeCounter::toString() const {
-        BSONArrayBuilder bab;
-        for( vector<int>::const_iterator i = _i.begin(); i != _i.end(); ++i ) {
-            bab << *i;
-        }
-        return BSON( "i" << bab.arr() <<
-                     "count" << _singleIntervalCount <<
-                     "limit" << _singleIntervalLimit
-                     ).jsonString();
-    }
-    
-    FieldRangeVectorIterator::FieldIntervalMatcher::FieldIntervalMatcher
-    ( const FieldInterval &interval, const BSONElement &element, bool reverse ) :
-    _interval( interval ),
-    _element( element ),
-    _reverse( reverse ) {
-    }
-    
-    int FieldRangeVectorIterator::FieldIntervalMatcher::lowerCmp() const {
-        if ( !_lowerCmp._valid ) {
-            setCmp( _lowerCmp, _interval._lower._bound );
-        }
-        return _lowerCmp._cmp;
-    }
-    
-    int FieldRangeVectorIterator::FieldIntervalMatcher::upperCmp() const {
-        if ( !_upperCmp._valid ) {
-            setCmp( _upperCmp, _interval._upper._bound );
-            if ( _interval.equality() ) {
-                _lowerCmp = _upperCmp;
-            }
-        }
-        return _upperCmp._cmp;
-    }
-
-    OrRangeGenerator::OrRangeGenerator(const char *ns, const BSONObj &query, bool optimize)
-                                      : _baseSet(ns, query, optimize), _orFound() {
-        BSONObjIterator i( _baseSet.originalQuery() );
-        
-        while (i.more()) {
-            BSONElement e = i.next();
-            if (strcmp(e.fieldName(), "$or") == 0) {
-                uassert( 13262, "$or requires nonempty array", e.type() == Array && e.embeddedObject().nFields() > 0 );
-                BSONObjIterator j( e.embeddedObject() );
-                while( j.more() ) {
-                    BSONElement f = j.next();
-                    uassert( 13263, "$or array must contain objects", f.type() == Object );
-                    _orSets.push_back( FieldRangeSetPair( ns, f.embeddedObject(), optimize ) );
-                    uassert( 13291, "$or may not contain 'special' query", _orSets.back().getSpecial().empty() );
-                    _originalOrSets.push_back( _orSets.back() );
-                }
-                _orFound = true;
-                continue;
-            }
-        }
-    }
-
-    void OrRangeGenerator::assertMayPopOrClause() {
-        massert( 13274, "no or clause to pop", _orFound && !orRangesExhausted() );        
-    }
-
-    void OrRangeGenerator::popOrClauseSingleKey() {
-        assertMayPopOrClause();
-        FieldRangeSet *toDiff = &_originalOrSets.front()._singleKey;
-        _popOrClause( toDiff, -1, BSONObj() );
-    }
-
-    void OrRangeGenerator::_popOrClause( const FieldRangeSet *toDiff, int idxNo, const BSONObj &keyPattern ) {
-        list<FieldRangeSetPair>::iterator i = _orSets.begin();
-        list<FieldRangeSetPair>::iterator j = _originalOrSets.begin();
-        ++i;
-        ++j;
-        while( i != _orSets.end() ) {
-            *i -= *toDiff;
-            // Check if match is possible at all, and if it is possible for the recently scanned index.
-            if( !i->matchPossible() ) {
-                i = _orSets.erase( i );
-                j = _originalOrSets.erase( j );
-            }
-            else {
-                ++i;
-                ++j;
-            }
-        }
-        _oldOrSets.push_front( _orSets.front() );
-        _orSets.pop_front();
-        _originalOrSets.pop_front();
-    }
-
-
-    long long applySkipLimit( long long num , const BSONObj& cmd ) {
-        BSONElement s = cmd["skip"];
-        BSONElement l = cmd["limit"];
-
-        if ( s.isNumber() ) {
-            num = num - s.numberLong();
-            if ( num < 0 ) {
-                num = 0;
-            }
-        }
-
-        if ( l.isNumber() ) {
-            long long limit = l.numberLong();
-            if( limit < 0 ){
-                limit = -limit;
-            }
-
-            if ( limit < num && limit != 0 ) { // 0 limit means no limit
-                num = limit;
-            }
-        }
-
-        return num;
-    }
-
-    bool isSimpleIdQuery( const BSONObj& query ) {
-        BSONObjIterator i(query);
-        
-        if( !i.more() ) 
-            return false;
-        
-        BSONElement e = i.next();
-        
-        if( i.more() ) 
-            return false;
-        
-        if( strcmp("_id", e.fieldName()) != 0 ) 
-            return false;
-        
-        if ( e.isSimpleType() ) // e.g. not something like { _id : { $gt : ...
-            return true;
-        
-        if ( e.type() == Object )
-            return e.Obj().firstElementFieldName()[0] != '$';
-        
-        return false;
-    }
-
-} // namespace mongo
diff --git a/src/mongo/db/queryutil.h b/src/mongo/db/queryutil.h
deleted file mode 100644
index 23ab584f11e..00000000000
--- a/src/mongo/db/queryutil.h
+++ /dev/null
@@ -1,729 +0,0 @@
-/*    Copyright 2009 10gen Inc.
- *
- *    Licensed under the Apache License, Version 2.0 (the "License");
- *    you may not use this file except in compliance with the License.
- *    You may obtain a copy of the License at
- *
- *    http://www.apache.org/licenses/LICENSE-2.0
- *
- *    Unless required by applicable law or agreed to in writing, software
- *    distributed under the License is distributed on an "AS IS" BASIS,
- *    WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
- *    See the License for the specific language governing permissions and
- *    limitations under the License.
- */
-
-#pragma once
-
-#include "jsobj.h"
-#include "mongo/db/index/btree_key_generator.h"
-
-namespace mongo {
-
-    //maximum number of intervals produced by $in queries.
-    static const unsigned MAX_IN_COMBINATIONS = 4000000;
-
-    /**
-     * One side of an interval of BSONElements, defined by a value and a boolean indicating if the
-     * interval includes the value.
-     */
-    struct FieldBound {
-        BSONElement _bound;
-        bool _inclusive;
-        bool operator==( const FieldBound &other ) const {
-            return _bound.woCompare( other._bound ) == 0 &&
-                   _inclusive == other._inclusive;
-        }
-        void flipInclusive() { _inclusive = !_inclusive; }
-    };
-
-    // Keep track of what special indices we're using.  This can be nontrivial
-    // because an index could be required by one operator but not by another.
-    struct SpecialIndices {
-        // Unlike true/false, this is readable.  :)
-        enum IndexRequired {
-            INDEX_REQUIRED,
-            NO_INDEX_REQUIRED,
-        };
-        map<string, bool> _indexRequired;
-
-        bool has(const string& name) const {
-            return _indexRequired.end() != _indexRequired.find(name);
-        }
-
-        SpecialIndices combineWith(const SpecialIndices& other) {
-            SpecialIndices ret = *this;
-            for (map<string, bool>::const_iterator it = other._indexRequired.begin();
-                 it != other._indexRequired.end(); ++it) {
-                ret._indexRequired[it->first] = ret._indexRequired[it->first] || it->second;
-            }
-            return ret;
-        }
-
-
-        void add(const string& name, IndexRequired req) {
-            _indexRequired[name] = _indexRequired[name] || (req == INDEX_REQUIRED);
-        }
-
-        bool allRequireIndex() const {
-            for (map<string, bool>::const_iterator it = _indexRequired.begin();
-                 it != _indexRequired.end(); ++it) {
-                if (!it->second) { return false; }
-            }
-            return true;
-        }
-
-        bool empty() const { return _indexRequired.empty(); }
-        string toString() const {
-            stringstream ss;
-            for (map<string, bool>::const_iterator it = _indexRequired.begin();
-                 it != _indexRequired.end(); ++it) {
-                ss << it->first;
-                ss << (it->second ? " (needs index)" : " (no index needed)");
-                ss << ", ";
-            }
-            return ss.str();
-        }
-    };
-
-    /** An interval defined between a lower and an upper FieldBound. */
-    struct FieldInterval {
-        FieldInterval() : _cachedEquality( -1 ) {}
-        FieldInterval( const BSONElement& e ) : _cachedEquality( -1 ) {
-            _lower._bound = _upper._bound = e;
-            _lower._inclusive = _upper._inclusive = true;
-        }
-        FieldBound _lower;
-        FieldBound _upper;
-        /**
-         * @return true when the interval can contain one or more values.
-         * NOTE May also return true in certain 'empty' discrete cases like x > false && x < true.
-         */
-        bool isStrictValid() const {
-            int cmp = _lower._bound.woCompare( _upper._bound, false );
-            return ( cmp < 0 || ( cmp == 0 && _lower._inclusive && _upper._inclusive ) );
-        }
-        /** @return true if the interval is an equality constraint. */
-        bool equality() const;
-        mutable int _cachedEquality;
-
-        string toString() const;
-    };
-
-    /**
-     * An ordered list of FieldIntervals expressing constraints on valid
-     * BSONElement values for a field.
-     */
-    class FieldRange {
-    public:
-        /**
-         * Creates a FieldRange representing a superset of the BSONElement values matching a query
-         *     expression element.
-         * @param e - The query expression element.
-         * @param isNot - Indicates that 'e' appears within a query $not clause and its matching
-         *     semantics are inverted.
-         * @param optimize - If true, the range may be bracketed by 'e''s data type.
-         *     TODO It is unclear why 'optimize' is optional, see SERVER-5165.
-         */
-        FieldRange( const BSONElement &e , bool isNot, bool optimize );
-
-        void setElemMatchContext( const BSONElement& elemMatchContext ) {
-            _elemMatchContext = elemMatchContext;
-        }
-
-        /**
-         * @return Range intersection with 'other'.
-         * @param singleKey - Indicate whether intersection will be performed in a single value or
-         *     multi value context.
-         */
-        const FieldRange &intersect( const FieldRange &other, bool singleKey );
-        /** @return Range union with 'other'. */
-        const FieldRange &operator|=( const FieldRange &other );
-        /** @return Range of elements elements included in 'this' but not 'other'. */
-        const FieldRange &operator-=( const FieldRange &other );
-        /** @return true iff this range is a subset of 'other'. */
-        bool operator<=( const FieldRange &other ) const;
-
-        /**
-         * If there are any valid values for this range, the extreme values can
-         * be extracted.
-         */
-        
-        BSONElement min() const { verify( !empty() ); return _intervals[ 0 ]._lower._bound; }
-        BSONElement max() const { verify( !empty() ); return _intervals[ _intervals.size() - 1 ]._upper._bound; }
-        bool minInclusive() const { verify( !empty() ); return _intervals[ 0 ]._lower._inclusive; }
-        bool maxInclusive() const { verify( !empty() ); return _intervals[ _intervals.size() - 1 ]._upper._inclusive; }
-
-        /** @return true iff this range expresses a single equality interval. */
-        bool equality() const;
-        /**
-         * @return true iff this range includes all BSONElements
-         * (the range is the universal set of BSONElements).
-         */
-        bool universal() const;
-        /** @return true iff this range includes no BSONElements. */
-        bool empty() const { return _intervals.empty(); }
-        /**
-         * @return true in many cases when this FieldRange represents the exact set of BSONElement
-         * values matching the query expression element used to construct the FieldRange.  This
-         * attribute is used to implement higher level optimizations and is computed with a simple
-         * implementation that identifies common (but not all) cases of this property and may return
-         * false negatives.
-         */
-        bool mustBeExactMatchRepresentation() const { return _exactMatchRepresentation; }
-        /* Checks whether this FieldRange is a non-empty union of point-intervals.
-         * Examples:
-         *  FieldRange( { a:3 } ), isPointIntervalSet() -> true
-         *  FieldRange( { a:{ $in:[ 1, 2 ] } } ), isPointIntervalSet() -> true
-         *  FieldRange( { a:{ $gt:5 } } ), isPointIntervalSet() -> false
-         *  FieldRange( {} ), isPointIntervalSet() -> false
-         */
-        bool isPointIntervalSet() const;
-        const BSONElement& elemMatchContext() const { return _elemMatchContext; }
-        
-        /** Empty the range so it includes no BSONElements. */
-        void makeEmpty() { _intervals.clear(); }
-        const vector<FieldInterval> &intervals() const { return _intervals; }
-        const SpecialIndices& getSpecial() const { return _special; }
-        /** Make component intervals noninclusive. */
-        void setExclusiveBounds();
-        /**
-         * Constructs a range where all FieldIntervals and FieldBounds are in
-         * the opposite order of the current range.
-         * NOTE the resulting intervals might not be strictValid().
-         */
-        void reverse( FieldRange &ret ) const;
-
-        string toString() const;
-    private:
-        BSONObj addObj( const BSONObj &o );
-        void finishOperation( const vector<FieldInterval> &newIntervals, const FieldRange &other,
-                              bool exactMatchRepresentation );
-        vector<FieldInterval> _intervals;
-        // Owns memory for our BSONElements.
-        vector<BSONObj> _objData;
-        SpecialIndices _special; // Index type name of a non standard (eg '2d') index required by a
-                              // parsed query operator (eg '$near').  Could be >1.
-        bool _exactMatchRepresentation;
-        BSONElement _elemMatchContext; // Parent $elemMatch object of the field constraint that
-                                       // generated this FieldRange.  For example if the query is
-                                       // { a:{ $elemMatch:{ b:1, c:1 } } }, then the
-                                       // _elemMatchContext for the FieldRange on 'a.b' is the query
-                                       // element having field name '$elemMatch'.
-    };
-
-    /**
-     * A set of FieldRanges determined from constraints on the fields of a query,
-     * that may be used to determine index bounds.
-     */
-    class FieldRangeSet {
-    public:
-        friend class OrRangeGenerator;
-        friend class FieldRangeVector;
-        /**
-         * Creates a FieldRangeSet representing a superset of the documents matching a query.
-         * @param ns - The query's namespace.
-         * @param query - The query.
-         * @param singleKey - Indicates that document fields contain single values (there are no
-         *     multiply valued fields).
-         * @param optimize - If true, each field's value range may be bracketed by data type.
-         *     TODO It is unclear why 'optimize' is optional, see SERVER-5165.
-         */
-        FieldRangeSet( const char *ns, const BSONObj &query , bool singleKey , bool optimize );
-
-        /** @return range for the given field. */
-        const FieldRange &range( const char *fieldName ) const;
-        /** @return range for the given field.  Public for testing. */
-        FieldRange &range( const char *fieldName );
-        /** @return the number of non universal ranges. */
-        int numNonUniversalRanges() const;
-        /** @return the field ranges comprising this set. */
-        const map<string,FieldRange> &ranges() const { return _ranges; }
-        /** 
-         * @return true if a match could be possible on every field. Generally this
-         * is not useful information for a single key FieldRangeSet and
-         * matchPossibleForIndex() should be used instead.
-         */
-        bool matchPossible() const;
-        /**
-         * @return true if a match could be possible given the value of _singleKey
-         * and index key 'keyPattern'.
-         * @param keyPattern May be {} or {$natural:1} for a non index scan.
-         */
-        bool matchPossibleForIndex( const BSONObj &keyPattern ) const;
-        /**
-         * @return true in many cases when this FieldRangeSet represents the exact set of BSONObjs
-         * matching the query expression used to construct the FieldRangeSet.  This attribute is
-         * used to implement higher level optimizations and is computed with a simple implementation
-         * that identifies common (but not all) cases of this property and may return false
-         * negatives.
-         */
-        bool mustBeExactMatchRepresentation() const { return _exactMatchRepresentation; }
-        
-        /* Checks whether this FieldRangeSet is a non-empty union of point-intervals
-         * on a given field.
-         * Examples:
-         *  FieldRangeSet({a : 3}), isPointIntervalSet("a") -> true
-         *  FieldRangeSet({a : {$in : [1 , 2]}}), isPointIntervalSet("a") -> true
-         *  FieldRangeSet({}), isPointIntervalSet("a") -> false
-         *  FieldRangeSet({b : 1}), isPointIntervalSet("a") -> false
-         *
-         * Used in determining "suitability" for hashedindexes, and also in
-         * sharding for determining the relevant shards for a query.
-         *
-         * TODO: move this into FieldRange instead of FieldRangeSet
-         */
-        bool isPointIntervalSet( const string& fieldname ) const;
-
-        const char *ns() const { return _ns.c_str(); }
-        
-        // QueryPattern pattern( const BSONObj &sort = BSONObj() ) const;
-        SpecialIndices getSpecial() const;
-
-        /**
-         * @return a FieldRangeSet approximation of the documents in 'this' but
-         * not in 'other'.  The approximation will be a superset of the documents
-         * in 'this' but not 'other'.
-         */
-        const FieldRangeSet &operator-=( const FieldRangeSet &other );
-        /** @return intersection of 'this' with 'other'. */
-        const FieldRangeSet &operator&=( const FieldRangeSet &other );
-
-        /**
-         * @return - A new FieldRangeSet based on this FieldRangeSet, but with only
-         * a subset of the fields.
-         * @param fields - Only fields which are represented as field names in this object
-         * will be included in the returned FieldRangeSet.
-         */
-        FieldRangeSet *subset( const BSONObj &fields ) const;
-        
-        /**
-         * @return A new FieldRangeSet based on this FieldRangeSet, but with all field names
-         * prefixed by the specified @param prefix field name.
-         */
-        FieldRangeSet* prefixed( const string& prefix ) const;
-        
-        bool singleKey() const { return _singleKey; }
-        
-        BSONObj originalQuery() const { return _queries[ 0 ]; }
-        
-        string toString() const;
-
-    private:
-        /**
-         * Private constructor for implementation specific delegate objects.
-         * @param boundElemMatch - If false, FieldRanges will not be computed for $elemMatch
-         *     expressions.
-         */
-        FieldRangeSet( const char* ns, const BSONObj& query, bool singleKey, bool optimize,
-                       bool boundElemMatch );
-        /** Initializer shared by the constructors. */
-        void init( bool optimize );
-
-        void appendQueries( const FieldRangeSet &other );
-        void makeEmpty();
-
-        /**
-         * Query parsing routines.
-         * TODO integrate these with an external query parser shared by the matcher.  SERVER-1009
-         */
-        void handleMatchField( const BSONElement& matchElement, bool optimize );
-        void handleConjunctionClauses( const BSONObj& clauses, bool optimize );
-        void handleOp( const char* matchFieldName, const BSONElement& op, bool isNot,
-                       bool optimize );
-        void handleNotOp( const char* matchFieldName, const BSONElement& notOp, bool optimize );
-        void handleElemMatch( const char* matchFieldName, const BSONElement& elemMatch, bool isNot,
-                              bool optimize );
-
-        /** Must be called when a match element is skipped or modified to generate a FieldRange. */
-        void adjustMatchField();
-        void intersectMatchField( const char *fieldName, const BSONElement &matchElement,
-                                 bool isNot, bool optimize );
-        static FieldRange *__universalRange;
-        const FieldRange &universalRange() const;
-        map<string,FieldRange> _ranges;
-        string _ns;
-        // Owns memory for FieldRange BSONElements.
-        vector<BSONObj> _queries;
-        bool _singleKey;
-        bool _exactMatchRepresentation;
-        bool _boundElemMatch;
-    };
-
-    /**
-     * A pair of FieldRangeSets, one representing constraints for single key
-     * indexes and the other representing constraints for multi key indexes and
-     * unindexed scans.  In several member functions the caller is asked to
-     * supply an index so that the implementation may utilize the proper
-     * FieldRangeSet and return results that are appropriate with respect to that
-     * supplied index.
-     */
-    class FieldRangeSetPair {
-    public:
-        FieldRangeSetPair( const char *ns, const BSONObj &query, bool optimize=true )
-        :_singleKey( ns, query, true, optimize ), _multiKey( ns, query, false, optimize ) {}
-
-        /** @return a field range in the single key FieldRangeSet. */
-        const FieldRange &shardKeyRange( const char *fieldName ) const {
-            return _singleKey.range( fieldName );
-        }
-        /** @return true if the range limits are equivalent to an empty query. */
-        bool noNonUniversalRanges() const;
-        /** @return false if a match is impossible regardless of index. */
-        bool matchPossible() const { return _multiKey.matchPossible(); }
-        /**
-         * @return false if a match is impossible on the specified index.
-         * @param idxNo -1 for non index scan.
-         */
-        const char *ns() const { return _singleKey.ns(); }
-
-        SpecialIndices getSpecial() const { return _singleKey.getSpecial(); }
-
-        /** Intersect with another FieldRangeSetPair. */
-        FieldRangeSetPair &operator&=( const FieldRangeSetPair &other );
-        /**
-         * Subtract a FieldRangeSet, generally one expressing a range that has
-         * already been scanned.
-         */
-        FieldRangeSetPair &operator-=( const FieldRangeSet &scanned );
-        
-        bool matchPossibleForSingleKeyFRS( const BSONObj &keyPattern ) const {
-            return _singleKey.matchPossibleForIndex( keyPattern );
-        }
-        
-        BSONObj originalQuery() const { return _singleKey.originalQuery(); }
-
-        const FieldRangeSet getSingleKeyFRS() const { return _singleKey; }
-        const FieldRangeSet getMultiKeyFRS() const { return _singleKey; }
-
-        string toString() const;
-    private:
-        FieldRangeSetPair( const FieldRangeSet &singleKey, const FieldRangeSet &multiKey )
-        :_singleKey( singleKey ), _multiKey( multiKey ) {}
-        /** matchPossibleForIndex() must be true. */
-        FieldRangeSet _singleKey;
-        FieldRangeSet _multiKey;
-        friend class OrRangeGenerator;
-        friend struct QueryUtilIndexed;
-    };
-    
-    /**
-     * An ordered list of fields and their FieldRanges, corresponding to valid
-     * index keys for a given index spec.
-     */
-    class FieldRangeVector {
-    public:
-        /**
-         * @param frs The valid ranges for all fields, as defined by the query spec.  None of the
-         * fields in indexSpec may be empty() ranges of frs.
-         * @param indexSpec The index spec (key pattern and info)
-         * @param direction The direction of index traversal
-         */
-        FieldRangeVector( const FieldRangeSet &frs, BSONObj keyPattern, int direction );
-
-        /**
-         * Methods for identifying compound start and end btree bounds describing this field range
-         * vector.
-         *
-         * A FieldRangeVector contains the FieldRange bounds for every field of an index.  A
-         * FieldRangeVectorIterator may be used to efficiently search for btree keys within these
-         * bounds.  Alternatively, a single compound field interval of the btree may be scanned,
-         * between a compound field start point and end point.  If isSingleInterval() is true then
-         * the interval between the start and end points will be an exact description of this
-         * FieldRangeVector, otherwise the start/end interval will be a superset of this
-         * FieldRangeVector.  For example:
-         *
-         * index { a:1 }, query { a:{ $gt:2, $lte:4 } }
-         *     -> frv ( 2, 4 ]
-         *         -> start/end bounds ( { '':2 }, { '':4 } ]
-         *
-         * index { a:1, b:1 }, query { a:2, b:{ $gte:7, $lt:9 } }
-         *     -> frv [ 2, 2 ], [ 7, 9 )
-         *         -> start/end bounds [ { '':2, '':7 }, { '':2, '':9 } )
-         *
-         * index { a:1, b:-1 }, query { a:2, b:{ $gte:7, $lt:9 } }
-         *     -> frv [ 2, 2 ], ( 9, 7 ]
-         *         -> start/end bounds ( { '':2, '':9 }, { '':2, '':7 } ]
-         *
-         * index { a:1, b:1 }, query { a:{ $gte:7, $lt:9 } }
-         *     -> frv [ 7, 9 )
-         *         -> start/end bounds [ { '':7, '':MinKey }, { '':9, '':MinKey } )
-         *
-         * index { a:1, b:1 }, query { a:{ $gte:2, $lte:5 }, b:{ $gte:7, $lte:9 } }
-         *     -> frv [ 2, 5 ], [ 7, 9 ]
-         *         -> start/end bounds [ { '':2, '':7 }, { '':5, '':9 } ]
-         *            (isSingleInterval() == false)
-         */
-
-        /**
-         * @return true if this FieldRangeVector represents a single interval within a btree,
-         * comprised of all keys between a single start point and a single end point.
-         */
-        bool isSingleInterval() const;
-
-        /**
-         * @return a starting point for an index traversal, a lower bound on the ranges represented
-         * by this FieldRangeVector according to the btree's native ordering.
-         */
-        BSONObj startKey() const;
-
-        /** @return true if the startKey() bound is inclusive. */
-        bool startKeyInclusive() const;
-
-        /**
-         * @return an end point for an index traversal, an upper bound on the ranges represented
-         * by this FieldRangeVector according to the btree's native ordering.
-         */
-        BSONObj endKey() const;
-
-        /** @return true if the endKey() bound is inclusive. */
-        bool endKeyInclusive() const;
-
-        /** @return the number of index ranges represented by 'this' */
-        unsigned size() const;
-
-        /** @return a client readable representation of 'this' */
-        BSONObj obj() const;
-        
-        /**
-         * @return true iff the provided document matches valid ranges on all
-         * of this FieldRangeVector's fields, which is the case iff this document
-         * would be returned while scanning the index corresponding to this
-         * FieldRangeVector.  This function is used for $or clause deduping.
-         */
-        bool matches( const BSONObj &obj ) const;
-
-        /**
-         * @return true if all values in the provided index key are contained within the field
-         * ranges of their respective fields in this FieldRangeVector.
-         *
-         * For example, given a query { a:3, b:4 } and index { a:1, b:1 }, the FieldRangeVector is
-         * [ [[ 3, 3 ]], [[ 4, 4 ]] ], consisting of field range [[ 3, 3 ]] on field 'a' and
-         * [[ 4, 4 ]] on field 'b'.  The index key { '':3, '':4 } matches, but the index key
-         * { '':3, '':5 } does not match because the value 5 in the second field is not contained in
-         * the field range [[ 4, 4 ]] for field 'b'.
-         */
-        bool matchesKey( const BSONObj& key ) const;
-
-        /**
-         * @return first key of 'obj' that would be encountered by a forward
-         * index scan using this FieldRangeVector, BSONObj() if no such key.
-         */
-        BSONObj firstMatch( const BSONObj &obj ) const;
-
-        /**
-         * @return true if all ranges within the field range set on fields of this index are
-         * represented in this field range vector.  May be false in certain multikey index cases
-         * when intervals on two fields cannot both be used, see comments related to SERVER-958 in
-         * FieldRangeVector().
-         */
-        bool hasAllIndexedRanges() const { return _hasAllIndexedRanges; }
-
-        string toString() const;
-        
-    private:
-        int matchingLowElement( const BSONElement &e, int i, bool direction, bool &lowEquality ) const;
-        bool matchesElement( const BSONElement &e, int i, bool direction ) const;
-        vector<FieldRange> _ranges;
-        BSONObj _keyPattern;
-        int _direction;
-        vector<BSONObj> _queries; // make sure mem owned
-        bool _hasAllIndexedRanges;
-        friend class FieldRangeVectorIterator;
-
-        vector<const char*> _fieldNames;
-        vector<BSONElement> _fixed;
-        // See FieldRangeVector::matches for comment on key generation.
-        scoped_ptr<BtreeKeyGenerator> _keyGenerator;
-    };
-    
-    /**
-     * Helper class for iterating through an ordered representation of keys
-     * to find those keys that match a specified FieldRangeVector.
-     */
-    class FieldRangeVectorIterator {
-    public:
-        /**
-         * @param v - a FieldRangeVector representing matching keys.
-         * @param singleIntervalLimit - The maximum number of keys to match a single (compound)
-         *     interval before advancing to the next interval.  Limit checking is disabled if 0.
-         */
-        FieldRangeVectorIterator( const FieldRangeVector &v, int singleIntervalLimit );
-
-        /**
-         * @return Suggested advance method through an ordered list of keys with lookup support
-         *      (generally a btree).
-         *   -2 Iteration is complete, no need to advance further.
-         *   -1 Advance to the next ordered key, without skipping.
-         *  >=0 Skip parameter, let's call it 'r'.  If after() is true, skip past the key prefix
-         *      comprised of the first r elements of curr.  For example, if curr is {a:1,b:1}, the
-         *      index is {a:1,b:1}, the direction is 1, and r == 1, skip past {a:1,b:MaxKey}.  If
-         *      after() is false, skip to the key comprised of the first r elements of curr followed
-         *      by the (r+1)th and greater elements of cmp() (with inclusivity specified by the
-         *      (r+1)th and greater elements of inc()).  For example, if curr is {a:1,b:1}, the
-         *      index is {a:1,b:1}, the direction is 1, r == 1, cmp()[1] == b:4, and inc()[1] ==
-         *      true, then skip to {a:1,b:4}.  Note that the element field names in curr and cmp()
-         *      should generally be ignored when performing index key comparisons.
-         * @param curr The key at the current position in the list of keys.  Values of curr must be
-         *      supplied in order.
-         */
-        int advance( const BSONObj &curr );
-        const vector<const BSONElement *> &cmp() const { return _cmp; }
-        const vector<bool> &inc() const { return _inc; }
-        bool after() const { return _after; }
-        void prepDive();
-
-        /**
-         * Helper class representing a position within a vector of ranges.  Public for testing.
-         */
-        class CompoundRangeCounter {
-        public:
-            CompoundRangeCounter( int size, int singleIntervalLimit );
-            int size() const { return (int)_i.size(); }
-            int get( int i ) const { return _i[ i ]; }
-            void set( int i, int newVal );
-            void inc( int i );
-            void setZeroes( int i );
-            void setUnknowns( int i );
-            void incSingleIntervalCount() {
-                if ( isTrackingIntervalCounts() ) ++_singleIntervalCount;
-            }
-            bool hasSingleIntervalCountReachedLimit() const {
-                return isTrackingIntervalCounts() && _singleIntervalCount >= _singleIntervalLimit;
-            }
-            void resetIntervalCount() { _singleIntervalCount = 0; }
-            string toString() const;
-        private:
-            bool isTrackingIntervalCounts() const { return _singleIntervalLimit > 0; }
-            vector<int> _i;
-            int _singleIntervalCount;
-            int _singleIntervalLimit;
-        };
-
-        /**
-         * Helper class for matching a BSONElement with the bounds of a FieldInterval.  Some
-         * internal comparison results are cached. Public for testing.
-         */
-        class FieldIntervalMatcher {
-        public:
-            FieldIntervalMatcher( const FieldInterval &interval, const BSONElement &element,
-                                 bool reverse );
-            bool isEqInclusiveUpperBound() const {
-                return upperCmp() == 0 && _interval._upper._inclusive;
-            }
-            bool isGteUpperBound() const { return upperCmp() >= 0; }
-            bool isEqExclusiveLowerBound() const {
-                return lowerCmp() == 0 && !_interval._lower._inclusive;
-            }
-            bool isLtLowerBound() const { return lowerCmp() < 0; }
-        private:
-            struct BoundCmp {
-                BoundCmp() : _cmp(), _valid() {}
-                void set( int cmp ) { _cmp = cmp; _valid = true; }
-                int _cmp;
-                bool _valid;
-            };
-            int mayReverse( int val ) const { return _reverse ? -val : val; }
-            int cmp( const BSONElement &bound ) const {
-                return mayReverse( _element.woCompare( bound, false ) );
-            }
-            void setCmp( BoundCmp &boundCmp, const BSONElement &bound ) const {
-                boundCmp.set( cmp( bound ) );
-            }
-            int lowerCmp() const;
-            int upperCmp() const;
-            const FieldInterval &_interval;
-            const BSONElement &_element;
-            bool _reverse;
-            mutable BoundCmp _lowerCmp;
-            mutable BoundCmp _upperCmp;
-        };
-
-    private:
-        /**
-         * @return values similar to advance()
-         *   -2 Iteration is complete for the current interval.
-         *   -1 Iteration is not complete for the current interval.
-         *  >=0 Return value to be forwarded by advance().
-         */
-        int validateCurrentInterval( int intervalIdx, const BSONElement &currElt,
-                                    bool reverse, bool first, bool &eqInclusiveUpperBound );
-        
-        /** Skip to curr / i / nextbounds. */
-        int advanceToLowerBound( int i );
-        /** Skip to curr / i / superlative. */
-        int advancePast( int i );
-        /** Skip to curr / i / superlative and reset following interval positions. */
-        int advancePastZeroed( int i );
-
-        bool hasReachedLimitForLastInterval( int intervalIdx ) const {
-            return
-                _i.hasSingleIntervalCountReachedLimit() &&
-                ( intervalIdx + 1 == _endNonUniversalRanges );
-        }
-
-        /** @return the index of the last non universal range + 1. */
-        int endNonUniversalRanges() const;
-
-        const FieldRangeVector &_v;
-        CompoundRangeCounter _i;
-        vector<const BSONElement*> _cmp;
-        vector<bool> _inc;
-        bool _after;
-        int _endNonUniversalRanges;
-    };
-    
-    /**
-     * As we iterate through $or clauses this class generates a FieldRangeSetPair
-     * for the current $or clause, in some cases by excluding ranges that were
-     * included in a previous clause.
-     */
-    class OrRangeGenerator {
-    public:
-        OrRangeGenerator( const char *ns, const BSONObj &query , bool optimize=true );
-
-        /** @return true iff we are done scanning $or clauses, or if there are no $or clauses. */
-        bool orRangesExhausted() const { return _orSets.empty(); }
-        /** Iterates to the next $or clause by removing the current $or clause. */
-        void popOrClauseSingleKey();
-        /** @return FieldRangeSetPair for the current $or clause. */
-        FieldRangeSetPair *topFrsp() const;
-        /**
-         * @return original FieldRangeSetPair for the current $or clause. While the
-         * original bounds are looser, they are composed of fewer ranges and it
-         * is faster to do operations with them; when they can be used instead of
-         * more precise bounds, they should.
-         */
-        FieldRangeSetPair *topFrspOriginal() const;
-        
-        SpecialIndices getSpecial() const { return _baseSet.getSpecial(); }
-    private:
-        void assertMayPopOrClause();
-        void _popOrClause( const FieldRangeSet *toDiff, int idxNo, const BSONObj &keyPattern );
-        FieldRangeSetPair _baseSet;
-        list<FieldRangeSetPair> _orSets;
-        list<FieldRangeSetPair> _originalOrSets;
-        // ensure memory is owned
-        list<FieldRangeSetPair> _oldOrSets;
-        bool _orFound;
-        friend struct QueryUtilIndexed;
-    };
-
-    /** returns a string that when used as a matcher, would match a super set of regex()
-        returns "" for complex regular expressions
-        used to optimize queries in some simple regex cases that start with '^'
-
-        if purePrefix != NULL, sets it to whether the regex can be converted to a range query
-    */
-    string simpleRegex(const char* regex, const char* flags, bool* purePrefix=NULL);
-
-    /** returns the upper bound of a query that matches prefix */
-    string simpleRegexEnd( string prefix );
-
-    long long applySkipLimit( long long num , const BSONObj& cmd );
-    
-    bool isSimpleIdQuery( const BSONObj& query );
-
-} // namespace mongo
-
-#include "queryutil-inl.h"
diff --git a/src/mongo/dbtests/namespacetests.cpp b/src/mongo/dbtests/namespacetests.cpp
index 485855131fb..d0536b0bf8c 100644
--- a/src/mongo/dbtests/namespacetests.cpp
+++ b/src/mongo/dbtests/namespacetests.cpp
@@ -38,7 +38,6 @@
 #include "mongo/db/index_names.h"
 #include "mongo/db/json.h"
 #include "mongo/db/query/internal_plans.h"
-#include "mongo/db/queryutil.h"
 #include "mongo/db/storage/extent.h"
 #include "mongo/db/storage/extent_manager.h"
 #include "mongo/db/storage/mmap_v1/dur_transaction.h"
diff --git a/src/mongo/dbtests/queryutiltests.cpp b/src/mongo/dbtests/queryutiltests.cpp
deleted file mode 100644
index 0c78145fd77..00000000000
--- a/src/mongo/dbtests/queryutiltests.cpp
+++ /dev/null
@@ -1,2963 +0,0 @@
-// queryutiltests.cpp : query utility unit tests
-//
-
-/**
- *    Copyright (C) 2009 10gen Inc.
- *
- *    This program is free software: you can redistribute it and/or  modify
- *    it under the terms of the GNU Affero General Public License, version 3,
- *    as published by the Free Software Foundation.
- *
- *    This program is distributed in the hope that it will be useful,
- *    but WITHOUT ANY WARRANTY; without even the implied warranty of
- *    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
- *    GNU Affero General Public License for more details.
- *
- *    You should have received a copy of the GNU Affero General Public License
- *    along with this program.  If not, see <http://www.gnu.org/licenses/>.
- *
- *    As a special exception, the copyright holders give permission to link the
- *    code of portions of this program with the OpenSSL library under certain
- *    conditions as described in each individual source file and distribute
- *    linked combinations including the program with the OpenSSL library. You
- *    must comply with the GNU Affero General Public License in all respects
- *    for all of the code used other than as permitted herein. If you modify
- *    file(s) with this exception, you may extend this exception to your
- *    version of the file(s), but you are not obligated to do so. If you do not
- *    wish to do so, delete this exception statement from your version. If you
- *    delete this exception statement from all source files in the program,
- *    then also delete it in the license file.
- */
-
-#include "mongo/pch.h"
-
-#include "mongo/db/catalog/collection.h"
-#include "mongo/db/catalog/database.h"
-#include "mongo/db/index/index_descriptor.h"
-#include "mongo/db/instance.h"
-#include "mongo/db/json.h"
-#include "mongo/db/pdfile.h"
-#include "mongo/db/queryutil.h"
-#include "mongo/db/storage/mmap_v1/dur_transaction.h"
-#include "mongo/db/structure/catalog/namespace_details.h"
-#include "mongo/dbtests/dbtests.h"
-
-namespace QueryUtilTests {
-
-    namespace FieldIntervalTests {
-        class ToString {
-        public:
-            void run() {
-                BSONObj obj = BSON( "a" << 1 );
-                FieldInterval fieldInterval( obj.firstElement() );
-                fieldInterval.toString(); // Just test that we don't crash.
-            }
-        };
-    } // namespace FieldIntervalTests
-    
-    //
-    // TODO: Test cases inside namespace FieldRangeTests are testing
-    // code that will soon be fully deprecated and should eventually
-    // be deleted.
-    //
-    // Analogous tests for the new query system can be found in the
-    // index bounds builder test (db/query/index_bounds_builder_test.cpp).
-    //
-    namespace FieldRangeTests {
-        class ToString {
-        public:
-            void run() {
-                BSONObj obj = BSON( "a" << 1 );
-                FieldRange fieldRange( obj.firstElement(), false, true );
-                fieldRange.toString(); // Just test that we don't crash.
-            }
-        };        
-        
-        class Base {
-        public:
-            virtual ~Base() {}
-            void run() {
-                const FieldRangeSet s( "ns", query(), true, true );
-                checkElt( lower(), s.range( "a" ).min() );
-                checkElt( upper(), s.range( "a" ).max() );
-                ASSERT_EQUALS( lowerInclusive(), s.range( "a" ).minInclusive() );
-                ASSERT_EQUALS( upperInclusive(), s.range( "a" ).maxInclusive() );
-                ASSERT_EQUALS( mustBeExactMatchRepresentation(),
-                               s.range( "a" ).mustBeExactMatchRepresentation() );
-                ASSERT_EQUALS( isPointIntervalSet(),
-                               s.range( "a" ).isPointIntervalSet() );
-            }
-        protected:
-            virtual BSONObj query() = 0;
-            virtual BSONElement lower() { return minKey.firstElement(); }
-            virtual bool lowerInclusive() { return true; }
-            virtual BSONElement upper() { return maxKey.firstElement(); }
-            virtual bool upperInclusive() { return true; }
-            virtual bool mustBeExactMatchRepresentation() { return false; }
-            virtual bool isPointIntervalSet() { return false; }
-            static void checkElt( BSONElement expected, BSONElement actual ) {
-                if ( expected.woCompare( actual, false ) ) {
-                    mongo::unittest::log() << "expected: " << expected << ", got: " << actual;
-                    ASSERT( false );
-                }
-            }
-        };
-
-
-        class NumericBase : public Base {
-        public:
-            NumericBase() {
-                o = BSON( "min" << -numeric_limits<double>::max() << "max" << numeric_limits<double>::max() );
-            }
-
-            virtual BSONElement lower() { return o["min"]; }
-            virtual BSONElement upper() { return o["max"]; }
-        private:
-            BSONObj o;
-        };
-
-        class EmptyQuery : public Base {
-            virtual BSONObj query() { return BSONObj(); }
-            virtual bool mustBeExactMatchRepresentation() { return true; }
-        };
-
-        class Eq : public Base {
-        public:
-            Eq() : o_( BSON( "a" << 1 ) ) {}
-            virtual BSONObj query() { return o_; }
-            virtual BSONElement lower() { return o_.firstElement(); }
-            virtual BSONElement upper() { return o_.firstElement(); }
-            virtual bool mustBeExactMatchRepresentation() { return true; }
-            virtual bool isPointIntervalSet() { return true; }
-            BSONObj o_;
-        };
-
-        class DupEq : public Eq {
-        public:
-            virtual BSONObj query() { return BSON( "a" << 1 << "b" << 2 << "a" << 1 ); }
-        };
-
-        class Lt : public NumericBase {
-        public:
-            Lt() : o_( BSON( "-" << 1 ) ) {}
-            virtual BSONObj query() { return BSON( "a" << LT << 1 ); }
-            virtual BSONElement upper() { return o_.firstElement(); }
-            virtual bool upperInclusive() { return false; }
-            virtual bool mustBeExactMatchRepresentation() { return true; }
-            BSONObj o_;
-        };
-
-        class Lte : public Lt {
-            virtual BSONObj query() { return BSON( "a" << LTE << 1 ); }
-            virtual bool upperInclusive() { return true; }
-            virtual bool mustBeExactMatchRepresentation() { return true; }
-        };
-
-        class LtDate : public Base {
-        public:
-            LtDate() :
-                _o( BSON( "" << Date_t( 5000 ) ) ),
-                _o2( BSON( "" << true ) ) {
-            }
-            virtual BSONObj query() { return BSON( "a" << LT << _o.firstElement() ); }
-            virtual BSONElement lower() {
-                // $lt:date is bounded from below by 'true', the highest value of the next lowest
-                // canonical type.
-                return _o2.firstElement();
-            }
-            virtual bool lowerInclusive() {
-                // 'true' should not match $lt:date, so the bound is exclusive.
-                return false;
-            }
-            virtual BSONElement upper() { return _o.firstElement(); }
-            virtual bool upperInclusive() { return false; }
-            virtual bool mustBeExactMatchRepresentation() { return true; }
-        private:
-            BSONObj _o, _o2;
-        };
-
-        class Gt : public NumericBase {
-        public:
-            Gt() : o_( BSON( "-" << 1 ) ) {}
-            virtual BSONObj query() { return BSON( "a" << GT << 1 ); }
-            virtual BSONElement lower() { return o_.firstElement(); }
-            virtual bool lowerInclusive() { return false; }
-            virtual bool mustBeExactMatchRepresentation() { return true; }
-            BSONObj o_;
-        };
-
-        class Gte : public Gt {
-            virtual BSONObj query() { return BSON( "a" << GTE << 1 ); }
-            virtual bool mustBeExactMatchRepresentation() { return true; }
-            virtual bool lowerInclusive() { return true; }
-        };
-
-        class GtString : public Base {
-        public:
-            GtString() :
-                _o( BSON( "" << "abc" ) ),
-                _o2( BSON( "" << BSONObj() ) ) {
-            }
-            virtual BSONObj query() { return BSON( "a" << GT << _o.firstElement() ); }
-            virtual BSONElement lower() { return _o.firstElement(); }
-            virtual bool lowerInclusive() { return false; }
-            virtual BSONElement upper() {
-                // $gt:string is bounded from above by '{}', the lowest value of the next highest
-                // canonical type.
-                return _o2.firstElement();
-            }
-            virtual bool upperInclusive() {
-                // '{}' should not match $gt:string, so the bound is exclusive.
-                return false;
-            }
-            virtual bool mustBeExactMatchRepresentation() { return true; }
-        private:
-            BSONObj _o, _o2;
-        };
-
-        class TwoLt : public Lt {
-            virtual BSONObj query() { return BSON( "a" << LT << 1 << LT << 5 ); }
-        };
-
-        class TwoGt : public Gt {
-            virtual BSONObj query() { return BSON( "a" << GT << 0 << GT << 1 ); }
-        };
-
-        class EqGte : public Eq {
-            virtual BSONObj query() { return BSON( "a" << 1 << "a" << GTE << 1 ); }
-        };
-
-        class EqGteInvalid {
-        public:
-            void run() {
-                FieldRangeSet frs( "ns", BSON( "a" << 1 << "a" << GTE << 2 ), true, true );
-                ASSERT( !frs.matchPossible() );
-            }
-        };
-
-        struct RegexBase : Base {
-            void run() { //need to only look at first interval
-                FieldRangeSet s( "ns", query(), true, true );
-                checkElt( lower(), s.range( "a" ).intervals()[0]._lower._bound );
-                checkElt( upper(), s.range( "a" ).intervals()[0]._upper._bound );
-                ASSERT_EQUALS( lowerInclusive(), s.range( "a" ).intervals()[0]._lower._inclusive );
-                ASSERT_EQUALS( upperInclusive(), s.range( "a" ).intervals()[0]._upper._inclusive );
-            }
-        };
-
-        class Regex : public RegexBase {
-        public:
-            Regex() : o1_( BSON( "" << "abc" ) ), o2_( BSON( "" << "abd" ) ) {}
-            virtual BSONObj query() {
-                BSONObjBuilder b;
-                b.appendRegex( "a", "^abc" );
-                return b.obj();
-            }
-            virtual BSONElement lower() { return o1_.firstElement(); }
-            virtual BSONElement upper() { return o2_.firstElement(); }
-            virtual bool upperInclusive() { return false; }
-            BSONObj o1_, o2_;
-        };
-
-        class RegexObj : public RegexBase {
-        public:
-            RegexObj() : o1_( BSON( "" << "abc" ) ), o2_( BSON( "" << "abd" ) ) {}
-            virtual BSONObj query() { return BSON("a" << BSON("$regex" << "^abc")); }
-            virtual BSONElement lower() { return o1_.firstElement(); }
-            virtual BSONElement upper() { return o2_.firstElement(); }
-            virtual bool upperInclusive() { return false; }
-            BSONObj o1_, o2_;
-        };
-
-        class UnhelpfulRegex : public RegexBase {
-        public:
-            UnhelpfulRegex() {
-                BSONObjBuilder b;
-                b.appendMinForType("lower", String);
-                b.appendMaxForType("upper", String);
-                limits = b.obj();
-            }
-
-            virtual BSONObj query() {
-                BSONObjBuilder b;
-                b.appendRegex( "a", "abc" );
-                return b.obj();
-            }
-            virtual BSONElement lower() { return limits["lower"]; }
-            virtual BSONElement upper() { return limits["upper"]; }
-            virtual bool upperInclusive() { return false; }
-            BSONObj limits;
-        };
-
-        class In : public Base {
-        public:
-            In() : o1_( BSON( "-" << -3 ) ), o2_( BSON( "-" << 44 ) ) {}
-            virtual BSONObj query() {
-                vector< int > vals;
-                vals.push_back( 4 );
-                vals.push_back( 8 );
-                vals.push_back( 44 );
-                vals.push_back( -1 );
-                vals.push_back( -3 );
-                vals.push_back( 0 );
-                BSONObjBuilder bb;
-                bb.append( "$in", vals );
-                BSONObjBuilder b;
-                b.append( "a", bb.done() );
-                return b.obj();
-            }
-            virtual BSONElement lower() { return o1_.firstElement(); }
-            virtual BSONElement upper() { return o2_.firstElement(); }
-            virtual bool mustBeExactMatchRepresentation() { return true; }
-            virtual bool isPointIntervalSet() { return true; }
-            BSONObj o1_, o2_;
-        };
-
-        class And : public Base {
-        public:
-            And() : _o1( BSON( "-" << 0 ) ), _o2( BSON( "-" << 10 ) ) {}
-            void run() {
-                Base::run();
-                const FieldRangeSet s( "ns", query(), true, true );
-                // There should not be an index constraint recorded for the $and field.
-                ASSERT( s.range( "$and" ).universal() );
-            }
-        private:
-            virtual BSONObj query() {
-                return BSON( "$and" <<
-                            BSON_ARRAY( BSON( "a" << GT << 0 ) << BSON( "a" << LTE << 10 ) ) );
-            }
-            virtual bool mustBeExactMatchRepresentation() { return true; }
-            virtual BSONElement lower() { return _o1.firstElement(); }
-            virtual bool lowerInclusive() { return false; }
-            virtual BSONElement upper() { return _o2.firstElement(); }
-            BSONObj _o1, _o2;
-        };
-
-        /**
-         * Field bounds of a query clause within a singleton $or expression are intersected with
-         * those of the overall query.  SERVER-6416
-         */
-        class SingletonOr : public Base {
-        public:
-            SingletonOr() :
-                _obj( BSON( "" << 5 ) ) {
-            }
-            void run() {
-                Base::run();
-                const FieldRangeSet s( "ns", query(), true, true );
-                // There should not be an index constraint recorded for the $or field.
-                ASSERT( s.range( "$or" ).universal() );
-            }
-        private:
-            virtual BSONObj query() {
-                // There is a single $or clause.
-                return fromjson( "{$or:[{a:5}]}" );
-            }
-            virtual bool mustBeExactMatchRepresentation() {
-                // The 'a' FieldRange is an exact match representation (it is an equality), though
-                // not the overall FieldRangeSet.
-                return true;
-            }
-            virtual bool isPointIntervalSet() { return true; }
-            virtual BSONElement lower() { return _obj.firstElement(); }
-            virtual BSONElement upper() { return _obj.firstElement(); }
-            BSONObj _obj;
-        };
-
-        /**
-         * Field bounds of a query clause within a nested singleton $or expression are intersected
-         * with those of the overall query.  SERVER-6416
-         */
-        class NestedSingletonOr : public SingletonOr {
-            virtual BSONObj query() {
-                // There is a single $or clause.
-                return fromjson( "{$or:[{$or:[{a:5}]}]}" );
-            }
-        };
-
-        /**
-         * Field bounds of a query clause within a non singleton $or expression are not intersected
-         * with those of the overall query.
-         */
-        class NonSingletonOr : public Base {
-        public:
-            void run() {
-                Base::run();
-                const FieldRangeSet s( "ns", query(), true, true );
-                // There should not be an index constraint recorded for the $or field.
-                ASSERT( s.range( "$or" ).universal() );
-            }
-        private:
-            virtual BSONObj query() {
-                // There is more than one $or clause.
-                return fromjson( "{$or:[{a:5},{a:6}]}" );
-            }
-            virtual bool mustBeExactMatchRepresentation() {
-                // The 'a' FieldRange is an exact match representation (the default universal range
-                // matches anything), though not the overall FieldRangeSet.
-                return true;
-            }
-        };
-        
-        class Empty {
-        public:
-            void run() {
-                FieldRangeSet s( "ns", BSON( "a" << GT << 5 << LT << 5 ), true, true );
-                const FieldRange &r = s.range( "a" );
-                ASSERT( r.empty() );
-                ASSERT( !r.equality() );
-                ASSERT( !r.universal() );
-                ASSERT( r.mustBeExactMatchRepresentation() );
-            }
-        };
-        
-        class Equality {
-        public:
-            void run() {
-                FieldRangeSet s( "ns", BSON( "a" << 1 ), true, true );
-                ASSERT( s.range( "a" ).equality() );
-                FieldRangeSet s2( "ns", BSON( "a" << GTE << 1 << LTE << 1 ), true, true );
-                ASSERT( s2.range( "a" ).equality() );
-                FieldRangeSet s3( "ns", BSON( "a" << GT << 1 << LTE << 1 ), true, true );
-                ASSERT( !s3.range( "a" ).equality() );
-                FieldRangeSet s4( "ns", BSON( "a" << GTE << 1 << LT << 1 ), true, true );
-                ASSERT( !s4.range( "a" ).equality() );
-                FieldRangeSet s5( "ns", BSON( "a" << GTE << 1 << LTE << 1 << GT << 1 ), true,
-                                  true );
-                ASSERT( !s5.range( "a" ).equality() );
-                FieldRangeSet s6( "ns", BSON( "a" << GTE << 1 << LTE << 1 << LT << 1 ), true,
-                                  true );
-                ASSERT( !s6.range( "a" ).equality() );
-            }
-        };
-
-        class NoWhere {
-        public:
-            void run() {
-                ASSERT_EQUALS( 0, FieldRangeSet( "ns", BSON( "$where" << 1 ), true, true )
-                                       .numNonUniversalRanges() );
-            }
-        };
-
-        class Numeric {
-        public:
-            void run() {
-                FieldRangeSet f( "", BSON( "a" << 1 ), true, true );
-                ASSERT( f.range( "a" ).min().woCompare( BSON( "a" << 2.0 ).firstElement() ) < 0 );
-                ASSERT( f.range( "a" ).min().woCompare( BSON( "a" << 0.0 ).firstElement() ) > 0 );
-            }
-        };
-
-        class InLowerBound {
-        public:
-            void run() {
-                FieldRangeSet f( "", fromjson( "{a:{$gt:4,$in:[1,2,3,4,5,6]}}" ), true, true );
-                ASSERT( f.range( "a" ).min().woCompare( BSON( "a" << 5.0 ).firstElement(), false ) == 0 );
-                ASSERT( f.range( "a" ).max().woCompare( BSON( "a" << 6.0 ).firstElement(), false ) == 0 );
-            }
-        };
-
-        class InUpperBound {
-        public:
-            void run() {
-                FieldRangeSet f( "", fromjson( "{a:{$lt:4,$in:[1,2,3,4,5,6]}}" ), true, true );
-                ASSERT( f.range( "a" ).min().woCompare( BSON( "a" << 1.0 ).firstElement(), false ) == 0 );
-                ASSERT( f.range( "a" ).max().woCompare( BSON( "a" << 3.0 ).firstElement(), false ) == 0 );
-            }
-        };
-
-        /** Check union of two non overlapping ranges. */
-        class BoundUnion {
-        public:
-            void run() {
-                FieldRangeSet frs( "", fromjson( "{a:{$gt:1,$lt:9},b:{$gt:9,$lt:12}}" ), true,
-                                   true );
-                FieldRange ret = frs.range( "a" );
-                ret |= frs.range( "b" );
-                ASSERT_EQUALS( 2U, ret.intervals().size() );
-            }
-        };
-
-        /** Check union of two ranges where one includes another. */
-        class BoundUnionFullyContained {
-        public:
-            void run() {
-                FieldRangeSet frs( "",
-                                   fromjson( "{a:{$gt:1,$lte:9},b:{$gt:2,$lt:8},"
-                                             "c:{$gt:2,$lt:9},d:{$gt:2,$lte:9}}" ), true, true );
-                FieldRange u = frs.range( "a" );
-                u |= frs.range( "b" );
-                ASSERT_EQUALS( 1U, u.intervals().size() );
-                ASSERT_EQUALS( frs.range( "a" ).toString(), u.toString() );
-                u |= frs.range( "c" );
-                ASSERT_EQUALS( 1U, u.intervals().size() );
-                ASSERT_EQUALS( frs.range( "a" ).toString(), u.toString() );
-                u |= frs.range( "d" );
-                ASSERT_EQUALS( 1U, u.intervals().size() );
-                ASSERT_EQUALS( frs.range( "a" ).toString(), u.toString() );
-            }
-        };
-
-        /**
-         * Check union of two ranges where one does not include another because of an inclusive
-         * bound.
-         */
-        class BoundUnionOverlapWithInclusivity {
-        public:
-            void run() {
-                FieldRangeSet frs( "", fromjson( "{a:{$gt:1,$lt:9},b:{$gt:2,$lte:9}}" ), true,
-                                   true );
-                FieldRange u = frs.range( "a" );
-                u |= frs.range( "b" );
-                ASSERT_EQUALS( 1U, u.intervals().size() );
-                FieldRangeSet expected( "", fromjson( "{a:{$gt:1,$lte:9}}" ), true, true );
-                ASSERT_EQUALS( expected.range( "a" ).toString(), u.toString() );
-            }
-        };
-        
-        /** Check union of two empty ranges. */
-        class BoundUnionEmpty {
-        public:
-            void run() {
-                FieldRangeSet frs( "", fromjson( "{a:{$in:[]},b:{$in:[]}}" ), true, true );
-                FieldRange a = frs.range( "a" );
-                a |= frs.range( "b" );
-                ASSERT( a.empty() );
-                ASSERT_EQUALS( 0U, a.intervals().size() );
-            }
-        };
-
-        class MultiBound {
-        public:
-            void run() {
-                FieldRangeSet frs1( "", fromjson( "{a:{$in:[1,3,5,7,9]}}" ), true, true );
-                FieldRangeSet frs2( "", fromjson( "{a:{$in:[2,3,5,8,9]}}" ), true, true );
-                FieldRange fr1 = frs1.range( "a" );
-                FieldRange fr2 = frs2.range( "a" );
-                fr1.intersect( fr2, true );
-                ASSERT( fr1.min().woCompare( BSON( "a" << 3.0 ).firstElement(), false ) == 0 );
-                ASSERT( fr1.max().woCompare( BSON( "a" << 9.0 ).firstElement(), false ) == 0 );
-                vector< FieldInterval > intervals = fr1.intervals();
-                vector< FieldInterval >::const_iterator j = intervals.begin();
-                double expected[] = { 3, 5, 9 };
-                for( int i = 0; i < 3; ++i, ++j ) {
-                    ASSERT_EQUALS( expected[ i ], j->_lower._bound.number() );
-                    ASSERT( j->_lower._inclusive );
-                    ASSERT( j->_lower == j->_upper );
-                }
-                ASSERT( j == intervals.end() );
-            }
-        };
-
-        class DiffBase {
-        public:
-            virtual ~DiffBase() {}
-            void run() {
-                FieldRangeSet frs( "", fromjson( obj().toString() ), true, true );
-                FieldRange ret = frs.range( "a" );
-                ret -= frs.range( "b" );
-                check( ret );
-            }
-        protected:
-            void check( const FieldRange &fr ) {
-                vector< FieldInterval > fi = fr.intervals();
-                ASSERT_EQUALS( len(), fi.size() );
-                int i = 0;
-                for( vector< FieldInterval >::const_iterator j = fi.begin(); j != fi.end(); ++j ) {
-                    ASSERT_EQUALS( nums()[ i ], j->_lower._bound.numberInt() );
-                    ASSERT_EQUALS( incs()[ i ], j->_lower._inclusive );
-                    ++i;
-                    ASSERT_EQUALS( nums()[ i ], j->_upper._bound.numberInt() );
-                    ASSERT_EQUALS( incs()[ i ], j->_upper._inclusive );
-                    ++i;
-                }
-            }
-            virtual unsigned len() const = 0;
-            virtual const int *nums() const = 0;
-            virtual const bool *incs() const = 0;
-            virtual BSONObj obj() const = 0;
-        };
-
-        class TwoRangeBase : public DiffBase {
-        public:
-            TwoRangeBase( string obj, int low, int high, bool lowI, bool highI )
-                : _obj( obj ) {
-                _n[ 0 ] = low;
-                _n[ 1 ] = high;
-                _b[ 0 ] = lowI;
-                _b[ 1 ] = highI;
-            }
-        private:
-            virtual unsigned len() const { return 1; }
-            virtual const int *nums() const { return _n; }
-            virtual const bool *incs() const { return _b; }
-            virtual BSONObj obj() const { return fromjson( _obj ); }
-            string _obj;
-            int _n[ 2 ];
-            bool _b[ 2 ];
-        };
-
-        struct Diff1 : public TwoRangeBase {
-            Diff1() : TwoRangeBase( "{a:{$gt:1,$lt:2},b:{$gt:3,$lt:4}}", 1, 2, false, false ) {}
-        };
-
-        struct Diff2 : public TwoRangeBase {
-            Diff2() : TwoRangeBase( "{a:{$gt:1,$lt:2},b:{$gt:2,$lt:4}}", 1, 2, false, false ) {}
-        };
-
-        struct Diff3 : public TwoRangeBase {
-            Diff3() : TwoRangeBase( "{a:{$gt:1,$lte:2},b:{$gt:2,$lt:4}}", 1, 2, false, true ) {}
-        };
-
-        struct Diff4 : public TwoRangeBase {
-            Diff4() : TwoRangeBase( "{a:{$gt:1,$lt:2},b:{$gte:2,$lt:4}}", 1, 2, false, false) {}
-        };
-
-        struct Diff5 : public TwoRangeBase {
-            Diff5() : TwoRangeBase( "{a:{$gt:1,$lte:2},b:{$gte:2,$lt:4}}", 1, 2, false, false) {}
-        };
-
-        struct Diff6 : public TwoRangeBase {
-            Diff6() : TwoRangeBase( "{a:{$gt:1,$lte:3},b:{$gte:2,$lt:4}}", 1, 2, false, false) {}
-        };
-
-        struct Diff7 : public TwoRangeBase {
-            Diff7() : TwoRangeBase( "{a:{$gt:1,$lte:3},b:{$gt:2,$lt:4}}", 1, 2, false, true) {}
-        };
-
-        struct Diff8 : public TwoRangeBase {
-            Diff8() : TwoRangeBase( "{a:{$gt:1,$lt:4},b:{$gt:2,$lt:4}}", 1, 2, false, true) {}
-        };
-
-        struct Diff9 : public TwoRangeBase {
-            Diff9() : TwoRangeBase( "{a:{$gt:1,$lt:4},b:{$gt:2,$lte:4}}", 1, 2, false, true) {}
-        };
-
-        struct Diff10 : public TwoRangeBase {
-            Diff10() : TwoRangeBase( "{a:{$gt:1,$lte:4},b:{$gt:2,$lte:4}}", 1, 2, false, true) {}
-        };
-
-        class SplitRangeBase : public DiffBase {
-        public:
-            SplitRangeBase( string obj, int low1, bool low1I, int high1, bool high1I, int low2, bool low2I, int high2, bool high2I )
-                : _obj( obj ) {
-                _n[ 0 ] = low1;
-                _n[ 1 ] = high1;
-                _n[ 2 ] = low2;
-                _n[ 3 ] = high2;
-                _b[ 0 ] = low1I;
-                _b[ 1 ] = high1I;
-                _b[ 2 ] = low2I;
-                _b[ 3 ] = high2I;
-            }
-        private:
-            virtual unsigned len() const { return 2; }
-            virtual const int *nums() const { return _n; }
-            virtual const bool *incs() const { return _b; }
-            virtual BSONObj obj() const { return fromjson( _obj ); }
-            string _obj;
-            int _n[ 4 ];
-            bool _b[ 4 ];
-        };
-
-        struct Diff11 : public SplitRangeBase {
-            Diff11() : SplitRangeBase( "{a:{$gt:1,$lte:4},b:{$gt:2,$lt:4}}", 1, false, 2, true, 4, true, 4, true) {}
-        };
-
-        struct Diff12 : public SplitRangeBase {
-            Diff12() : SplitRangeBase( "{a:{$gt:1,$lt:5},b:{$gt:2,$lt:4}}", 1, false, 2, true, 4, true, 5, false) {}
-        };
-
-        struct Diff13 : public TwoRangeBase {
-            Diff13() : TwoRangeBase( "{a:{$gt:1,$lt:5},b:{$gt:1,$lt:4}}", 4, 5, true, false) {}
-        };
-
-        struct Diff14 : public SplitRangeBase {
-            Diff14() : SplitRangeBase( "{a:{$gte:1,$lt:5},b:{$gt:1,$lt:4}}", 1, true, 1, true, 4, true, 5, false) {}
-        };
-
-        struct Diff15 : public TwoRangeBase {
-            Diff15() : TwoRangeBase( "{a:{$gt:1,$lt:5},b:{$gte:1,$lt:4}}", 4, 5, true, false) {}
-        };
-
-        struct Diff16 : public TwoRangeBase {
-            Diff16() : TwoRangeBase( "{a:{$gte:1,$lt:5},b:{$gte:1,$lt:4}}", 4, 5, true, false) {}
-        };
-
-        struct Diff17 : public TwoRangeBase {
-            Diff17() : TwoRangeBase( "{a:{$gt:1,$lt:5},b:{$gt:0,$lt:4}}", 4, 5, true, false) {}
-        };
-
-        struct Diff18 : public TwoRangeBase {
-            Diff18() : TwoRangeBase( "{a:{$gt:1,$lt:5},b:{$gt:0,$lte:4}}", 4, 5, false, false) {}
-        };
-
-        struct Diff19 : public TwoRangeBase {
-            Diff19() : TwoRangeBase( "{a:{$gte:1,$lte:5},b:{$gte:0,$lte:1}}", 1, 5, false, true) {}
-        };
-
-        struct Diff20 : public TwoRangeBase {
-            Diff20() : TwoRangeBase( "{a:{$gt:1,$lte:5},b:{$gte:0,$lte:1}}", 1, 5, false, true) {}
-        };
-
-        struct Diff21 : public TwoRangeBase {
-            Diff21() : TwoRangeBase( "{a:{$gte:1,$lte:5},b:{$gte:0,$lt:1}}", 1, 5, true, true) {}
-        };
-
-        struct Diff22 : public TwoRangeBase {
-            Diff22() : TwoRangeBase( "{a:{$gt:1,$lte:5},b:{$gte:0,$lt:1}}", 1, 5, false, true) {}
-        };
-
-        struct Diff23 : public TwoRangeBase {
-            Diff23() : TwoRangeBase( "{a:{$gt:1,$lte:5},b:{$gte:0,$lt:0.5}}", 1, 5, false, true) {}
-        };
-
-        struct Diff24 : public TwoRangeBase {
-            Diff24() : TwoRangeBase( "{a:{$gt:1,$lte:5},b:0}", 1, 5, false, true) {}
-        };
-
-        struct Diff25 : public TwoRangeBase {
-            Diff25() : TwoRangeBase( "{a:{$gte:1,$lte:5},b:0}", 1, 5, true, true) {}
-        };
-
-        struct Diff26 : public TwoRangeBase {
-            Diff26() : TwoRangeBase( "{a:{$gt:1,$lte:5},b:1}", 1, 5, false, true) {}
-        };
-
-        struct Diff27 : public TwoRangeBase {
-            Diff27() : TwoRangeBase( "{a:{$gte:1,$lte:5},b:1}", 1, 5, false, true) {}
-        };
-
-        struct Diff28 : public SplitRangeBase {
-            Diff28() : SplitRangeBase( "{a:{$gte:1,$lte:5},b:3}", 1, true, 3, false, 3, false, 5, true) {}
-        };
-
-        struct Diff29 : public TwoRangeBase {
-            Diff29() : TwoRangeBase( "{a:{$gte:1,$lte:5},b:5}", 1, 5, true, false) {}
-        };
-
-        struct Diff30 : public TwoRangeBase {
-            Diff30() : TwoRangeBase( "{a:{$gte:1,$lt:5},b:5}", 1, 5, true, false) {}
-        };
-
-        struct Diff31 : public TwoRangeBase {
-            Diff31() : TwoRangeBase( "{a:{$gte:1,$lt:5},b:6}", 1, 5, true, false) {}
-        };
-
-        struct Diff32 : public TwoRangeBase {
-            Diff32() : TwoRangeBase( "{a:{$gte:1,$lte:5},b:6}", 1, 5, true, true) {}
-        };
-
-        class EmptyBase : public DiffBase {
-        public:
-            EmptyBase( string obj )
-                : _obj( obj ) {}
-        private:
-            virtual unsigned len() const { return 0; }
-            virtual const int *nums() const { return 0; }
-            virtual const bool *incs() const { return 0; }
-            virtual BSONObj obj() const { return fromjson( _obj ); }
-            string _obj;
-        };
-
-        struct Diff33 : public EmptyBase {
-            Diff33() : EmptyBase( "{a:{$gte:1,$lte:5},b:{$gt:0,$lt:6}}" ) {}
-        };
-
-        struct Diff34 : public EmptyBase {
-            Diff34() : EmptyBase( "{a:{$gte:1,$lte:5},b:{$gte:1,$lt:6}}" ) {}
-        };
-
-        struct Diff35 : public EmptyBase {
-            Diff35() : EmptyBase( "{a:{$gt:1,$lte:5},b:{$gte:1,$lt:6}}" ) {}
-        };
-
-        struct Diff36 : public EmptyBase {
-            Diff36() : EmptyBase( "{a:{$gt:1,$lte:5},b:{$gt:1,$lt:6}}" ) {}
-        };
-
-        struct Diff37 : public TwoRangeBase {
-            Diff37() : TwoRangeBase( "{a:{$gte:1,$lte:5},b:{$gt:1,$lt:6}}", 1, 1, true, true ) {}
-        };
-
-        struct Diff38 : public EmptyBase {
-            Diff38() : EmptyBase( "{a:{$gt:1,$lt:5},b:{$gt:0,$lt:5}}" ) {}
-        };
-
-        struct Diff39 : public EmptyBase {
-            Diff39() : EmptyBase( "{a:{$gt:1,$lt:5},b:{$gt:0,$lte:5}}" ) {}
-        };
-
-        struct Diff40 : public EmptyBase {
-            Diff40() : EmptyBase( "{a:{$gt:1,$lte:5},b:{$gt:0,$lte:5}}" ) {}
-        };
-
-        struct Diff41 : public TwoRangeBase {
-            Diff41() : TwoRangeBase( "{a:{$gte:1,$lte:5},b:{$gt:0,$lt:5}}", 5, 5, true, true ) {}
-        };
-
-        struct Diff42 : public EmptyBase {
-            Diff42() : EmptyBase( "{a:{$gt:1,$lt:5},b:{$gt:1,$lt:5}}" ) {}
-        };
-
-        struct Diff43 : public EmptyBase {
-            Diff43() : EmptyBase( "{a:{$gt:1,$lt:5},b:{$gt:1,$lte:5}}" ) {}
-        };
-
-        struct Diff44 : public EmptyBase {
-            Diff44() : EmptyBase( "{a:{$gt:1,$lt:5},b:{$gte:1,$lt:5}}" ) {}
-        };
-
-        struct Diff45 : public EmptyBase {
-            Diff45() : EmptyBase( "{a:{$gt:1,$lt:5},b:{$gte:1,$lte:5}}" ) {}
-        };
-
-        struct Diff46 : public TwoRangeBase {
-            Diff46() : TwoRangeBase( "{a:{$gt:1,$lte:5},b:{$gt:1,$lt:5}}", 5, 5, true, true ) {}
-        };
-
-        struct Diff47 : public EmptyBase {
-            Diff47() : EmptyBase( "{a:{$gt:1,$lte:5},b:{$gt:1,$lte:5}}" ) {}
-        };
-
-        struct Diff48 : public TwoRangeBase {
-            Diff48() : TwoRangeBase( "{a:{$gt:1,$lte:5},b:{$gte:1,$lt:5}}", 5, 5, true, true ) {}
-        };
-
-        struct Diff49 : public EmptyBase {
-            Diff49() : EmptyBase( "{a:{$gt:1,$lte:5},b:{$gte:1,$lte:5}}" ) {}
-        };
-
-        struct Diff50 : public TwoRangeBase {
-            Diff50() : TwoRangeBase( "{a:{$gte:1,$lt:5},b:{$gt:1,$lt:5}}", 1, 1, true, true ) {}
-        };
-
-        struct Diff51 : public TwoRangeBase {
-            Diff51() : TwoRangeBase( "{a:{$gte:1,$lt:5},b:{$gt:1,$lte:5}}", 1, 1, true, true ) {}
-        };
-
-        struct Diff52 : public EmptyBase {
-            Diff52() : EmptyBase( "{a:{$gte:1,$lt:5},b:{$gte:1,$lt:5}}" ) {}
-        };
-
-        struct Diff53 : public EmptyBase {
-            Diff53() : EmptyBase( "{a:{$gte:1,$lt:5},b:{$gte:1,$lte:5}}" ) {}
-        };
-
-        struct Diff54 : public SplitRangeBase {
-            Diff54() : SplitRangeBase( "{a:{$gte:1,$lte:5},b:{$gt:1,$lt:5}}", 1, true, 1, true, 5, true, 5, true ) {}
-        };
-
-        struct Diff55 : public TwoRangeBase {
-            Diff55() : TwoRangeBase( "{a:{$gte:1,$lte:5},b:{$gt:1,$lte:5}}", 1, 1, true, true ) {}
-        };
-
-        struct Diff56 : public TwoRangeBase {
-            Diff56() : TwoRangeBase( "{a:{$gte:1,$lte:5},b:{$gte:1,$lt:5}}", 5, 5, true, true ) {}
-        };
-
-        struct Diff57 : public EmptyBase {
-            Diff57() : EmptyBase( "{a:{$gte:1,$lte:5},b:{$gte:1,$lte:5}}" ) {}
-        };
-
-        struct Diff58 : public TwoRangeBase {
-            Diff58() : TwoRangeBase( "{a:1,b:{$gt:1,$lt:5}}", 1, 1, true, true ) {}
-        };
-
-        struct Diff59 : public EmptyBase {
-            Diff59() : EmptyBase( "{a:1,b:{$gte:1,$lt:5}}" ) {}
-        };
-
-        struct Diff60 : public EmptyBase {
-            Diff60() : EmptyBase( "{a:2,b:{$gte:1,$lt:5}}" ) {}
-        };
-
-        struct Diff61 : public EmptyBase {
-            Diff61() : EmptyBase( "{a:5,b:{$gte:1,$lte:5}}" ) {}
-        };
-
-        struct Diff62 : public TwoRangeBase {
-            Diff62() : TwoRangeBase( "{a:5,b:{$gt:1,$lt:5}}", 5, 5, true, true ) {}
-        };
-
-        struct Diff63 : public EmptyBase {
-            Diff63() : EmptyBase( "{a:5,b:5}" ) {}
-        };
-
-        struct Diff64 : public TwoRangeBase {
-            Diff64() : TwoRangeBase( "{a:{$gte:1,$lte:2},b:{$gt:0,$lte:1}}", 1, 2, false, true ) {}
-        };
-
-        class DiffMulti1 : public DiffBase {
-        public:
-            void run() {
-                FieldRangeSet frs( "", fromjson( "{a:{$gt:1,$lt:9},b:{$gt:0,$lt:2},"
-                                                 "c:3,d:{$gt:4,$lt:5},e:{$gt:7,$lt:10}}" ), true,
-                                   true );
-                FieldRange ret = frs.range( "a" );
-                FieldRange other = frs.range( "b" );
-                other |= frs.range( "c" );
-                other |= frs.range( "d" );
-                other |= frs.range( "e" );
-                ret -= other;
-                check( ret );
-            }
-        protected:
-            virtual unsigned len() const { return 3; }
-            virtual const int *nums() const { static int n[] = { 2, 3, 3, 4, 5, 7 }; return n; }
-            virtual const bool *incs() const { static bool b[] = { true, false, false, true, true, true }; return b; }
-            virtual BSONObj obj() const { return BSONObj(); }
-        };
-
-        class DiffMulti2 : public DiffBase {
-        public:
-            void run() {
-                FieldRangeSet frs( "", fromjson( "{a:{$gt:1,$lt:9},b:{$gt:0,$lt:2},"
-                                                 "c:3,d:{$gt:4,$lt:5},e:{$gt:7,$lt:10}}" ), true,
-                                   true );
-                FieldRange mask = frs.range( "a" );
-                FieldRange ret = frs.range( "b" );
-                ret |= frs.range( "c" );
-                ret |= frs.range( "d" );
-                ret |= frs.range( "e" );
-                ret -= mask;
-                check( ret );
-            }
-        protected:
-            virtual unsigned len() const { return 2; }
-            virtual const int *nums() const { static int n[] = { 0, 1, 9, 10 }; return n; }
-            virtual const bool *incs() const { static bool b[] = { false, true, true, false }; return b; }
-            virtual BSONObj obj() const { return BSONObj(); }
-        };
-        
-        class Universal {
-        public:
-            void run() {
-                FieldRangeSet frs1( "", BSON( "a" << 1 ), true, true );
-                FieldRange f1 = frs1.range( "a" );
-                ASSERT( !f1.universal() );
-                ASSERT( frs1.range( "b" ).universal() );
-                
-                FieldRangeSet frs2( "", BSON( "a" << GT << 1 ), true, true );
-                FieldRange f2 = frs2.range( "a" );
-                ASSERT( !f2.universal() );
-
-                FieldRangeSet frs3( "", BSON( "a" << LT << 1 ), true, true );
-                FieldRange f3 = frs3.range( "a" );
-                ASSERT( !frs3.range( "a" ).universal() );
-
-                FieldRangeSet frs4( "", BSON( "a" << NE << 1 ), true, true );
-                FieldRange f4 = frs4.range( "a" );
-                ASSERT( !f4.universal() );
-
-                f1 |= f4;
-                ASSERT( f1.universal() );
-                f1.intersect( f2, true );
-                ASSERT( !f1.universal() );
-
-                FieldRangeSet frs5( "", BSON( "a" << GT << 1 << LTE << 2 ), true, true );
-                FieldRange f5 = frs5.range( "a" );
-                ASSERT( !f5.universal() );
-                
-                FieldRangeSet frs6( "", BSONObj(), true, true );
-                FieldRange f6 = frs6.range( "a" );
-                ASSERT( f6.universal() );
-                
-                f6 -= f5;
-                ASSERT( !f6.universal() );
-            }
-        };
-
-        /** Field range calculation for an untyped $regex within a $elemMatch. */
-        class ElemMatchRegex {
-        public:
-            void run() {
-                FieldRangeSet frs( "", BSON( "a" << BSON( "$elemMatch" << BSON("$regex" << "^x") ) ), true, true );
-                ASSERT( !frs.range( "a" ).universal() );
-                ASSERT_EQUALS( "x", frs.range( "a" ).min().String() );
-            }
-        };
-
-        /**
-         * The elemMatchContext is preserved when two FieldRanges are intersected, singleKey ==
-         * false, and the resulting FieldRange is an unmodified copy of one of the original two
-         * FieldRanges.  For example, if FieldRange a == [[1, 10]] is intersected with FieldRange b
-         * == [[5, 5]], a will be replaced with b.  In this case, because a becomes an exact copy of
-         * b, b's elemMatchContext will be copied to a.
-         */
-        class PreserveNonUniversalElemMatchContext {
-        public:
-            void run() {
-                BSONObj query = fromjson( "{a:{$elemMatch:{b:1}},c:{$lt:5},d:1}" );
-                _expectedElemMatchContext = query.firstElement().Obj().firstElement();
-
-                // The elemMatchContext is set properly for the 'a.b' field.
-                FieldRangeSet frs( "", query, true, true );
-                assertElemMatchContext( frs.range( "a.b" ) );
-
-                // The elemMatchContext is preserved after intersecting with a superset range.
-                frs.range( "a.b" ).intersect( frs.range( "c" ), false );
-                assertElemMatchContext( frs.range( "a.b" ) );
-
-                // The elemMatchContext is forwarded after intersecting with a subset range.
-                frs.range( "c" ).intersect( frs.range( "a.b" ), false );
-                assertElemMatchContext( frs.range( "c" ) );
-
-                // The elemMatchContext is cleared after a _single key_ intersection.
-                frs.range( "a.b" ).intersect( frs.range( "d" ), true /* singleKey */ );
-                ASSERT( frs.range( "a.b" ).elemMatchContext().eoo() );
-            }
-        private:
-            void assertElemMatchContext( const FieldRange& range ) {
-                ASSERT_EQUALS( _expectedElemMatchContext.rawdata(),
-                               range.elemMatchContext().rawdata() );
-            }
-            BSONElement _expectedElemMatchContext;
-        };
-
-        /** Intersect two universal ranges, one special. */
-        class IntersectSpecial {
-        public:
-            void run() {
-                FieldRangeSet frs( "", fromjson( "{loc:{$near:[0,0],$maxDistance:5}}" ), true,
-                                   true );
-                // The intersection is special.
-                ASSERT( !frs.range( "loc" ).getSpecial().empty() );
-            }
-        };
-        
-        namespace ExactMatchRepresentation {
-
-            class NotExactMatchRepresentation {
-            public:
-                NotExactMatchRepresentation( const BSONObj &query ) : _query( query ) {}
-                virtual ~NotExactMatchRepresentation() {}
-                void run() {
-                    ASSERT( !FieldRangeSet( "", _query, !multikey(),
-                                            true ).range( "a" ).mustBeExactMatchRepresentation() );
-                }
-            protected:
-                virtual bool multikey() const { return false; }
-            private:
-                BSONObj _query;
-            };
-            
-            struct EqualArray : public NotExactMatchRepresentation {
-                EqualArray() : NotExactMatchRepresentation( BSON( "a" << BSON_ARRAY( "1" ) ) ) {}
-            };
-            
-            struct EqualEmptyArray : public NotExactMatchRepresentation {
-                EqualEmptyArray() : NotExactMatchRepresentation( fromjson( "{a:[]}" ) ) {}
-            };
-            
-            struct EqualNull : public NotExactMatchRepresentation {
-                EqualNull() : NotExactMatchRepresentation( fromjson( "{a:null}" ) ) {}
-            };
-
-            struct InArray : public NotExactMatchRepresentation {
-                InArray() : NotExactMatchRepresentation( fromjson( "{a:{$in:[[1]]}}" ) ) {}
-            };
-            
-            struct InRegex : public NotExactMatchRepresentation {
-                InRegex() : NotExactMatchRepresentation( fromjson( "{a:{$in:[/^a/]}}" ) ) {}
-            };
-            
-            struct InNull : public NotExactMatchRepresentation {
-                InNull() : NotExactMatchRepresentation( fromjson( "{a:{$in:[null]}}" ) ) {}
-            };
-
-            struct Exists : public NotExactMatchRepresentation {
-                Exists() : NotExactMatchRepresentation( fromjson( "{a:{$exists:false}}" ) ) {}
-            };
-
-            struct UntypedRegex : public NotExactMatchRepresentation {
-                UntypedRegex() : NotExactMatchRepresentation( BSON( "a" << BSONObjBuilder().appendRegex("$regex", "^a", "").obj() ) ) {}
-            };
-
-            struct UntypedRegexString : public NotExactMatchRepresentation {
-                UntypedRegexString() : NotExactMatchRepresentation( BSON( "a" << BSON( "$regex" << "^a" ) ) ) {}
-            };
-
-            struct NotIn : public NotExactMatchRepresentation {
-                NotIn() : NotExactMatchRepresentation( fromjson( "{a:{$not:{$in:[0]}}}" ) ) {}
-            };
-
-            struct NotGt : public NotExactMatchRepresentation {
-                NotGt() : NotExactMatchRepresentation( fromjson( "{a:{$not:{$gt:0}}}" ) ) {}
-            };
-            
-            struct GtArray : public NotExactMatchRepresentation {
-                GtArray() : NotExactMatchRepresentation( fromjson( "{a:{$gt:[0]}}" ) ) {}
-            };
-            
-            struct GtNull : public NotExactMatchRepresentation {
-                GtNull() : NotExactMatchRepresentation( fromjson( "{a:{$gt:null}}" ) ) {}
-            };
-
-            struct LtObject : public NotExactMatchRepresentation {
-                LtObject() : NotExactMatchRepresentation( fromjson( "{a:{$lt:{}}}" ) ) {}
-            };
-
-            /** Descriptive test - behavior could potentially be different. */
-            struct NotNe : public NotExactMatchRepresentation {
-                NotNe() : NotExactMatchRepresentation( fromjson( "{a:{$not:{$ne:4}}}" ) ) {}
-            };
-            
-            class MultikeyIntersection : public NotExactMatchRepresentation {
-            public:
-                MultikeyIntersection() : NotExactMatchRepresentation
-                        ( BSON( "a" << GTE << 0 << "a" << 0 ) ) {
-                }
-            private:
-                virtual bool multikey() const { return true; }                
-            };
-            
-            class Intersection {
-            public:
-                void run() {
-                    FieldRangeSet set( "", BSON( "a" << 1 << "b" << GT << 2 << "c" << NE << 10 ),
-                                       true, true );
-                    FieldRange &a = set.range( "a" );
-                    FieldRange &b = set.range( "b" );
-                    FieldRange &c = set.range( "c" );
-                    FieldRange &missing = set.range( "missing" );
-                    ASSERT( a.mustBeExactMatchRepresentation() );
-                    ASSERT( b.mustBeExactMatchRepresentation() );
-                    ASSERT( !c.mustBeExactMatchRepresentation() );
-                    ASSERT( missing.mustBeExactMatchRepresentation() );
-                    
-                    // Intersecting two exact matches preserves the mustBeExactMatchRepresentation
-                    // property.
-                    a.intersect( missing, true );
-                    ASSERT( a.mustBeExactMatchRepresentation() );
-                    a.intersect( b, true );
-                    ASSERT( a.mustBeExactMatchRepresentation() );
-                    
-                    // Other operations clear the mustBeExactMatchRepresentation property.
-                    b.intersect( c, true );
-                    ASSERT( !b.mustBeExactMatchRepresentation() );                    
-                }
-            };
-            
-            class Union {
-            public:
-                void run() {
-                    FieldRangeSet set( "", BSON( "left" << 1 << "right" << GT << 2 ), true, true );
-                    FieldRange &left = set.range( "left" );
-                    FieldRange &right = set.range( "right" );
-                    left |= right;
-                    ASSERT( !left.mustBeExactMatchRepresentation() );
-                }
-            };
-
-            class Difference {
-            public:
-                void run() {
-                    FieldRangeSet set( "", BSON( "left" << 1 << "right" << GT << 2 ), true, true );
-                    FieldRange &left = set.range( "left" );
-                    FieldRange &right = set.range( "right" );
-                    left -= right;
-                    ASSERT( !left.mustBeExactMatchRepresentation() );
-                }
-            };
-
-        } // namespace ExactMatchRepresentation
-        
-    } // namespace FieldRangeTests
-
-    namespace FieldRangeSetTests {
-
-        class Basics {
-        public:
-            void run() {
-                {
-                    BSONObj obj = BSON( "a" << 1 );
-                    FieldRangeSet fieldRangeSet( "", obj, true, true );
-                    fieldRangeSet.toString(); // Just test that we don't crash.
-                }
-
-                {
-                    boost::shared_ptr<FieldRangeSet> frs;
-                    {
-                        string ns = str::stream() << "foo";
-                        frs.reset( new FieldRangeSet( ns.c_str(), BSONObj(), true, true ) );
-                    }
-                    ASSERT_EQUALS( string( "foo" ), frs->ns() );
-                }
-            }
-        };
-
-        class Intersect {
-        public:
-            void run() {
-                FieldRangeSet frs1( "", fromjson( "{b:{$in:[5,6]},c:7,d:{$in:[8,9]}}" ), true,
-                                    true );
-                FieldRangeSet frs2( "", fromjson( "{a:1,b:5,c:{$in:[7,8]},d:{$in:[8,9]},e:10}" ),
-                                    true, true );
-                frs1 &= frs2;
-                FieldRangeSet expectedResult( "", fromjson( "{a:1,b:5,c:7,d:{$in:[8,9]},e:10}" ),
-                                              true, true );
-                ASSERT_EQUALS( frs1.toString(), expectedResult.toString() );
-            }
-        };
-        
-        class MultiKeyIntersect {
-        public:
-            void run() {
-                FieldRangeSet frs1( "", BSONObj(), false, true );
-                FieldRangeSet frs2( "", BSON( "a" << GT << 4 ), false, true );
-                FieldRangeSet frs3( "", BSON( "a" << LT << 6 ), false, true );
-                // An intersection with a universal range is allowed.
-                frs1 &= frs2;
-                ASSERT_EQUALS( frs2.toString(), frs1.toString() );
-                // An intersection with non universal range is not allowed, as it might prevent a
-                // valid multikey match.
-                frs1 &= frs3;
-                ASSERT_EQUALS( frs2.toString(), frs1.toString() );
-                // Now intersect with a fully contained range.
-                FieldRangeSet frs4( "", BSON( "a" << GT << 6 ), false, true );
-                frs1 &= frs4;
-                ASSERT_EQUALS( frs4.toString(), frs1.toString() );
-            }
-        };
-
-        /* Intersecting an empty multikey range with another range produces an empty range. */
-        class EmptyMultiKeyIntersect {
-        public:
-            void run() {
-                FieldRangeSet frs1( "", BSON( "a" << BSON( "$in" << BSONArray() ) ), false, true );
-                FieldRangeSet frs2( "", BSON( "a" << 5 ), false, true );
-                ASSERT( frs1.range( "a" ).empty() );
-                frs1 &= frs2;
-                ASSERT( frs1.range( "a" ).empty() );
-            }
-        };
-
-        class MultiKeyDiff {
-        public:
-            void run() {
-                FieldRangeSet frs1( "", BSON( "a" << GT << 4 ), false, true );
-                FieldRangeSet frs2( "", BSON( "a" << GT << 6 ), false, true );
-                // Range subtraction is no different for multikey ranges.
-                frs1 -= frs2;
-                FieldRangeSet expectedResult( "", BSON( "a" << GT << 4 << LTE << 6 ), true, true );
-                ASSERT_EQUALS( frs1.toString(), expectedResult.toString() );
-            }
-        };
-        
-        class MatchPossible {
-        public:
-            void run() {
-                FieldRangeSet frs1( "", BSON( "a" << GT << 4 ), true, true );
-                ASSERT( frs1.matchPossible() );
-                // Conflicting constraints invalid for a single key set.
-                FieldRangeSet frs2( "", BSON( "a" << GT << 4 << LT << 2 ), true, true );
-                ASSERT( !frs2.matchPossible() );
-                // Conflicting constraints not possible for a multi key set.
-                FieldRangeSet frs3( "", BSON( "a" << GT << 4 << LT << 2 ), false, true );
-                ASSERT( frs3.matchPossible() );
-            }
-        };
-        
-        class MatchPossibleForIndex {
-        public:
-            void run() {
-                // Conflicting constraints not possible for a multi key set.
-                FieldRangeSet frs1( "", BSON( "a" << GT << 4 << LT << 2 ), false, true );
-                ASSERT( frs1.matchPossibleForIndex( BSON( "a" << 1 ) ) );
-                // Conflicting constraints for a multi key set.
-                FieldRangeSet frs2( "", BSON( "a" << GT << 4 << LT << 2 ), true, true );
-                ASSERT( !frs2.matchPossibleForIndex( BSON( "a" << 1 ) ) );
-                // If the index doesn't include the key, it is not single key invalid.
-                ASSERT( frs2.matchPossibleForIndex( BSON( "b" << 1 ) ) );
-                // If the index key is not an index, the set is not single key invalid.
-                ASSERT( frs2.matchPossibleForIndex( BSON( "$natural" << 1 ) ) );
-                ASSERT( frs2.matchPossibleForIndex( BSONObj() ) );
-            }
-        };
-        
-        class Subset {
-        public:
-            void run() {
-                _frs1.reset
-                ( new FieldRangeSet
-                 ( "", BSON( "a" << GT << 4 << LT << 4 << "b" << 5 << "c" << 6 ), true, true ) );
-                _frs2.reset( _frs1->subset( BSON( "a" << 1 << "b" << 1 << "d" << 1 ) ) );
-
-                // An empty range should be copied.
-                ASSERT( _frs1->range( "a" ).empty() );
-                ASSERT( _frs2->range( "a" ).empty() );
-                assertRangeCopied( "a" );
-
-                assertRangeCopied( "b" );
-                assertRangeNotCopied( "c" );
-                assertRangeNotCopied( "d" );
-            }
-        private:
-            void assertRangeCopied( const string &fieldName ) {
-                ASSERT_EQUALS( _frs1->range( fieldName.c_str() ).toString(),
-                              _frs2->range( fieldName.c_str() ).toString() );
-            }
-            void assertRangeNotCopied( const string &fieldName ) {
-                ASSERT_EQUALS( _frs1->range( "qqqqq" ).toString(), // Missing field, universal range
-                              _frs2->range( fieldName.c_str() ).toString() );
-            }
-            auto_ptr<FieldRangeSet> _frs1;
-            auto_ptr<FieldRangeSet> _frs2;
-        };
-
-        /** Duplicate a FieldRangeSet, but with prefixed field names. */
-        class Prefixed {
-        public:
-            void run() {
-                FieldRangeSet original( "", BSON( "a" << 1 ), true, true );
-                scoped_ptr<FieldRangeSet> prefixed( original.prefixed( "prefix" ) );
-                ASSERT( prefixed->singleKey() );
-                ASSERT( prefixed->range( "a" ).universal() );
-                ASSERT( prefixed->range( "prefix.a" ).equality() );
-            }
-        };
-
-        /** No field range is generated for an $atomic field.  SERVER-5354 */
-        class Atomic {
-        public:
-            void run() {
-                FieldRangeSet ranges( "", BSON( "a" << 1 << "$atomic" << 1 ), true, true );
-                // No range is computed for the '$atomic' field.
-                ASSERT( ranges.range( "$atomic" ).universal() );
-                // A standard equality range is computed for the 'a' field.
-                ASSERT( ranges.range( "a" ).equality() );
-            }
-        };
-
-        namespace ElemMatch {
-            
-            /** Field ranges generated for the $elemMatch operator. */
-            class Ranges {
-            public:
-                void run() {
-                    FieldRangeSet set( "", fromjson( "{ a:{ $elemMatch:{ b:1, c:2 } } }" ), true,
-                                       true );
-                    ASSERT( set.range( "a.b" ).equality() );
-                    ASSERT( set.range( "a.c" ).equality() );
-                    ASSERT( !set.range( "a.d" ).equality() );
-                    ASSERT( !set.range( "a" ).equality() );
-                }
-            };
-            
-            /**
-             * Field ranges generated when the $elemMatch operator is applied to top level
-             * elements.
-             */
-            class TopLevelElements {
-            public:
-                void run() {
-                    FieldRangeSet set( "", fromjson( "{ a:{ $elemMatch:{ $gte:5, $lte:5 } } }" ),
-                                       true, true );
-                    // No constraints exist for operator based field names like "a.$gte".
-                    ASSERT( set.range( "a.$gte" ).universal() );
-                    ASSERT( set.range( "a.$lte" ).universal() );
-                    // The index ranges for the $elemMatch subexpressions are intersected in a
-                    // single value context, generating an equality index bound.  SERVER-4180
-                    ASSERT( set.range( "a" ).equality() );
-                }
-            };
-            
-            /**
-             * Field ranges generated when the $elemMatch operator is applied to a top level
-             * $not meta operator.
-             */
-            class TopLevelNotElement {
-            public:
-                void run() {
-                    FieldRangeSet set( "", fromjson( "{ a:{ $elemMatch:{ $not:{ $ne:5 } } } }" ),
-                                       true, true );
-                    // No constraints exist for operator based field names like "a.$not".
-                    ASSERT( set.range( "a.$not" ).universal() );
-                    ASSERT( set.range( "a.$not.$ne" ).universal() );
-                    ASSERT( set.range( "a" ).equality() );
-                }
-            };
-            
-            /** Field ranges generated for $elemMatch nested within a top level $elemMatch. */
-            class TopLevelNested {
-            public:
-                void run() {
-                    FieldRangeSet set( "", fromjson( "{ a:{ $elemMatch:{ $elemMatch:{ $in:[ 5 ] "
-                                                     "} } } }" ),
-                                       true, true );
-                    ASSERT_EQUALS( 0, set.numNonUniversalRanges() );
-                    FieldRangeSet set2( "", fromjson( "{ a:{ $elemMatch:{ $elemMatch:{ b:{ "
-                                                      "$in:[ 5 ] } } } } }" ),
-                                       true, true );
-                    ASSERT_EQUALS( 0, set2.numNonUniversalRanges() );
-                }
-            };
-
-            /** Field ranges generated for $not:$elemMatch queries. */
-            class Not {
-            public:
-                void run() {
-                    FieldRangeSet set( "",
-                                       fromjson( "{ a:{ $not:{ $elemMatch:{ b:{ $ne:1 } } } } }" ),
-                                       true, true );
-                    ASSERT( !set.range( "a.b" ).equality() );
-                    ASSERT( set.range( "a.b" ).universal() );
-                }
-            };
-            
-            /** Field ranges generated for nested $elemMatch expressions. */
-            class Nested {
-            public:
-                void run() {
-                    FieldRangeSet set( "",
-                                       fromjson( "{ a:{ $elemMatch:{ b:{ $elemMatch:{ c:1"
-                                                " } } } } }" ),
-                                       true, true );
-                    // No constraints are generated for the following fields.
-                    BSONArray universalFields = BSON_ARRAY( "a" << "a.b" << "b" << "b.c" << "c" );
-                    BSONObjIterator i( universalFields );
-                    while( i.more() ) {
-                        ASSERT( set.range( i.next().String().c_str() ).universal() );
-                    }
-                    // A correct constraint is generated for a nested $elemMatch field.
-                    ASSERT( set.range( "a.b.c" ).equality() );
-                    ASSERT_EQUALS( 1, set.range( "a.b.c" ).min().number() );
-                }
-            };
-
-            /** Field ranges generated for an $elemMatch expression nested within $all. */
-            class AllNested {
-            public:
-                void run() {
-                    FieldRangeSet set( "",
-                                       fromjson( "{ a:{ $elemMatch:{ b:{ $all:"
-                                                 "[ { $elemMatch:{ c:1 } }, { $elemMatch:{ d:2 } } ]"
-                                                 " } } } }" ),
-                                       true, true );
-                    // No constraints are generated for the following fields.
-                    BSONArray universalFields = BSON_ARRAY( "a" << "a.b" << "b" << "b.c" << "c"
-                                                           << "b.d" << "d" << "a.b.d" );
-                    BSONObjIterator i( universalFields );
-                    while( i.more() ) {
-                        ASSERT( set.range( i.next().String().c_str() ).universal() );
-                    }
-                    // A correct constraint is generated for the first nested $elemMatch field.
-                    ASSERT( set.range( "a.b.c" ).equality() );
-                    ASSERT_EQUALS( 1, set.range( "a.b.c" ).min().number() );
-                }
-            };
-            
-        } // namespace ElemMatch
-
-        namespace ExactMatchRepresentation {
-
-            class ExactMatchRepresentation {
-            public:
-                ExactMatchRepresentation( const BSONObj &query ) : _query( query ) {}
-                void run() {
-                    ASSERT( FieldRangeSet( "", _query, true, true )
-                            .mustBeExactMatchRepresentation() );
-                }
-            private:
-                BSONObj _query;
-            };
-
-            class NotExactMatchRepresentation {
-            public:
-                NotExactMatchRepresentation( const BSONObj &query ) : _query( query ) {}
-                void run() {
-                    ASSERT( !FieldRangeSet( "", _query, true, true )
-                            .mustBeExactMatchRepresentation() );
-                }
-            private:
-                BSONObj _query;
-            };
-
-            struct EmptyQuery : public ExactMatchRepresentation {
-                EmptyQuery() : ExactMatchRepresentation( BSONObj() ) {}
-            };
-            
-            struct Equal : public ExactMatchRepresentation {
-                Equal() : ExactMatchRepresentation( BSON( "a" << 0 ) ) {}
-            };
-            
-            struct In : public ExactMatchRepresentation {
-                In() : ExactMatchRepresentation( fromjson( "{a:{$in:[0,1]}}" ) ) {}
-            };
-            
-            struct Where : public NotExactMatchRepresentation {
-                Where() : NotExactMatchRepresentation( BSON( "a" << 0 << "$where" << "foo" ) ) {}
-            };
-
-            struct Not : public NotExactMatchRepresentation {
-                Not() : NotExactMatchRepresentation( fromjson( "{a:{$not:{$in:[0]}}}" ) ) {}
-            };
-
-            struct Regex : public NotExactMatchRepresentation {
-                Regex() : NotExactMatchRepresentation( fromjson( "{a:/^a/}" ) ) {}
-            };
-
-            struct UntypedRegex : public NotExactMatchRepresentation {
-                UntypedRegex() : NotExactMatchRepresentation( BSON( "a" << BSONObjBuilder().appendRegex("$regex", "^a", "").obj() ) ) {}
-            };
-
-            struct UntypedRegexString : public NotExactMatchRepresentation {
-                UntypedRegexString() : NotExactMatchRepresentation( BSON( "a" << BSON( "$regex" << "^a" ) ) ) {}
-            };
-            
-            struct And : public ExactMatchRepresentation {
-                And() : ExactMatchRepresentation( fromjson( "{$and:[{a:{$in:[0,1]}}]}" ) ) {}
-            };
-
-            struct Or : public NotExactMatchRepresentation {
-                Or() : NotExactMatchRepresentation( fromjson( "{$or:[{a:{$in:[0,1]}}]}" ) ) {}
-            };
-
-            struct All : public NotExactMatchRepresentation {
-                All() : NotExactMatchRepresentation( fromjson( "{a:{$all:[0]}}" ) ) {}
-            };
-
-            struct ElemMatch : public NotExactMatchRepresentation {
-                ElemMatch() : NotExactMatchRepresentation( fromjson( "{a:{$elemMatch:{b:1}}}" ) ) {}
-            };
-
-            struct AllElemMatch : public NotExactMatchRepresentation {
-                AllElemMatch() :
-                        NotExactMatchRepresentation( fromjson( "{a:{$all:[{$elemMatch:{b:1}}]}}" ) ) {}
-            };
-            
-            struct NotSecondField : public NotExactMatchRepresentation {
-                NotSecondField() :
-                        NotExactMatchRepresentation( fromjson( "{a:{$in:[1],$not:{$in:[0]}}}" ) ) {}
-            };
-            
-        } // namespace ExactMatchRepresentation
-        
-    } // namespace FieldRangeSetTests
-    
-    namespace FieldRangeSetPairTests {
-
-        class ToString {
-        public:
-            void run() {
-                BSONObj obj = BSON( "a" << 1 );
-                FieldRangeSetPair FieldRangeSetPair( "", obj );
-                FieldRangeSetPair.toString(); // Just test that we don't crash.
-            }
-        };
-
-        class NoNonUniversalRanges {
-        public:
-            void run() {
-                FieldRangeSetPair frsp1( "", BSONObj() );
-                ASSERT( frsp1.noNonUniversalRanges() );
-                FieldRangeSetPair frsp2( "", BSON( "a" << 1 ) );
-                ASSERT( !frsp2.noNonUniversalRanges() );
-                FieldRangeSetPair frsp3( "", BSON( "a" << GT << 1 ) );
-                ASSERT( !frsp3.noNonUniversalRanges() );
-                // A single key invalid constraint is not universal.
-                FieldRangeSetPair frsp4( "", BSON( "a" << GT << 1 << LT << 0 ) );
-                ASSERT( !frsp4.noNonUniversalRanges() );
-                // Still not universal if multikey invalid constraint.
-                FieldRangeSetPair frsp5( "", BSON( "a" << BSON( "$in" << BSONArray() ) ) );
-                ASSERT( !frsp5.noNonUniversalRanges() );
-            }
-        };
-        
-        class MatchPossible {
-        public:
-            void run() {
-                // Match possible for simple query.
-                FieldRangeSetPair frsp1( "", BSON( "a" << 1 ) );
-                ASSERT( frsp1.matchPossible() );
-                // Match possible for single key invalid query.
-                FieldRangeSetPair frsp2( "", BSON( "a" << GT << 1 << LT << 0 ) );
-                ASSERT( frsp2.matchPossible() );
-            }
-        };
-
-        class IndexBase {
-            Lock::DBWrite _lk;
-            Client::Context _ctx;
-            DurTransaction _txn;
-        public:
-            IndexBase() : _lk(ns()), _ctx( ns() ) , indexNum_( 0 ) {
-                userCreateNS( &_txn, _ctx.db(), ns(), BSONObj(), false );
-            }
-            ~IndexBase() {
-                if ( !nsd() )
-                    return;
-                _ctx.db()->dropCollection( &_txn, ns() );
-            }
-        protected:
-            static const char *ns() { return "unittests.FieldRangeSetPairTests"; }
-            Client::Context* ctx() { return &_ctx; }
-            Database* db() { return _ctx.db(); }
-            Collection* collection() { return db()->getCollection( ns() ); }
-            NamespaceDetails *nsd() { return collection()->detailsWritable(); }
-
-            int indexno( const BSONObj &key ) {
-                stringstream ss;
-                ss << indexNum_++;
-                string name = ss.str();
-                client_.resetIndexCache();
-                client_.ensureIndex( ns(), key, false, name.c_str() );
-
-                IndexCatalog* catalog = collection()->getIndexCatalog();
-                IndexDescriptor* desc = catalog->findIndexByKeyPattern( key );
-                invariant( desc );
-
-                int x = nsd()->_catalogFindIndexByName(collection(), desc->indexName(), false);
-                invariant( x >= 0 );
-
-                return x;
-            }
-
-            static DBDirectClient client_;
-        private:
-            int indexNum_;
-        };
-        DBDirectClient IndexBase::client_;
-
-    } // namespace FieldRangeSetPairTests
-    
-    namespace FieldRangeVectorTests {
-
-        class ToString {
-        public:
-            void run() {
-                BSONObj obj = BSON( "a" << 1 );
-                FieldRangeSet fieldRangeSet( "", obj, true, true );
-                BSONObj indexSpec( BSON( "a" << 1 ) );
-                FieldRangeVector fieldRangeVector( fieldRangeSet, indexSpec, 1 );
-                fieldRangeVector.toString(); // Just test that we don't crash.
-            }
-        };
-
-        /**
-         * Check FieldRangeVector::hasAllIndexedRanges(), indicating when all indexed field ranges
-         * in a field range set are represented in a field range vector (and none are excluded due
-         * to multikey index field name conflicts).
-         */
-        class HasAllIndexedRanges {
-        public:
-            void run() {
-                // Single key index.
-                ASSERT( rangesRepresented( BSON( "a" << 1 ), true, BSON( "a" << 1 ) ) );
-                // Multikey index, but no unrepresented ranges.
-                ASSERT( rangesRepresented( BSON( "a" << 1 ), false, BSON( "a" << 1 ) ) );
-                // Multikey index, but no unrepresented ranges in the index.
-                ASSERT( rangesRepresented( BSON( "a" << 1 ), false,
-                                           BSON( "a" << 1 << "b" << 2 ) ) );
-                // Compound multikey index with no unrepresented ranges.
-                ASSERT( rangesRepresented( BSON( "a" << 1 << "b" << 1 ), false,
-                                           BSON( "a" << 2 << "b" << 3 ) ) );
-                // Compound multikey index with range 'a.c' unrepresented because of a conflict
-                // with range 'a.b', hence 'false' expected.
-                ASSERT( !rangesRepresented( BSON( "a.b" << 1 << "a.c" << 1 ), false,
-                                            BSON( "a.b" << 2 << "a.c" << 3 ) ) );
-                // Compound multikey index without conflicts due to use of the $elemMatch operator.
-                ASSERT( rangesRepresented( BSON( "a.b" << 1 << "a.c" << 1 ), false,
-                                           BSON( "a" << BSON( "$elemMatch" <<
-                                                              BSON( "b" << 2 << "c" << 3 ) ) ) ) );
-                // Single key index.
-                ASSERT( rangesRepresented( BSON( "a.b" << 1 << "a.c" << 1 ), true,
-                                           BSON( "a.b" << 2 << "a.c" << 3 ) ) );
-            }
-        private:
-            bool rangesRepresented( const BSONObj& index, bool singleKey, const BSONObj& query ) {
-                FieldRangeSet fieldRangeSet( "", query, singleKey, true );
-                BSONObj indexSpec( index );
-                FieldRangeVector fieldRangeVector( fieldRangeSet, indexSpec, 1 );
-                return fieldRangeVector.hasAllIndexedRanges();
-            }
-        };
-
-        /** Detecting cases where a FieldRangeVector describes a single btree interval. */
-        class SingleInterval {
-        public:
-            void run() {
-                // Equality on a single field is a single interval.
-                FieldRangeVector frv1( FieldRangeSet( "dummy", BSON( "a" << 5 ), true, true ),
-                                       ( BSON( "a" << 1 ) ),
-                                       1 );
-                ASSERT( frv1.isSingleInterval() );
-                // Single interval on a single field is a single interval.
-                FieldRangeVector frv2( FieldRangeSet( "dummy", BSON( "a" << GT << 5 ), true, true ),
-                                       ( BSON( "a" << 1 ) ),
-                                       1 );
-                ASSERT( frv2.isSingleInterval() );
-                // Multiple intervals on a single field is not a single interval.
-                FieldRangeVector frv3( FieldRangeSet( "dummy",
-                                                      fromjson( "{a:{$in:[4,5]}}" ),
-                                                      true,
-                                                      true ),
-                                      ( BSON( "a" << 1 ) ),
-                                      1 );
-                ASSERT( !frv3.isSingleInterval() );
-
-                // Equality on two fields is a compound single interval.
-                FieldRangeVector frv4( FieldRangeSet( "dummy",
-                                                      BSON( "a" << 5 << "b" << 6 ),
-                                                      true,
-                                                      true ),
-                                       ( BSON( "a" << 1 << "b" << 1 ) ),
-                                       1 );
-                ASSERT( frv4.isSingleInterval() );
-                // Equality on first field and single interval on second field is a compound
-                // single interval.
-                FieldRangeVector frv5( FieldRangeSet( "dummy",
-                                                      BSON( "a" << 5 << "b" << GT << 6 ),
-                                                      true,
-                                                      true ),
-                                       ( BSON( "a" << 1 << "b" << 1 ) ),
-                                       1 );
-                ASSERT( frv5.isSingleInterval() );
-                // Single interval on first field and single interval on second field is not a
-                // compound single interval.
-                FieldRangeVector frv6( FieldRangeSet( "dummy",
-                                                      BSON( "a" << LT << 5 << "b" << GT << 6 ),
-                                                      true,
-                                                      true ),
-                                       ( BSON( "a" << 1 << "b" << 1 ) ),
-                                       1 );
-                ASSERT( !frv6.isSingleInterval() );
-                // Multiple intervals on two fields is not a compound single interval.
-                FieldRangeVector frv7( FieldRangeSet( "dummy",
-                                                      fromjson( "{a:{$in:[4,5]},b:{$in:[7,8]}}" ),
-                                                      true,
-                                                      true ),
-                                       ( BSON( "a" << 1 << "b" << 1 ) ),
-                                       1 );
-                ASSERT( !frv7.isSingleInterval() );
-
-                // With missing second field is still a single compound interval.
-                FieldRangeVector frv8( FieldRangeSet( "dummy",
-                                                      BSON( "a" << 5 ),
-                                                      true,
-                                                      true ),
-                                       ( BSON( "a" << 1 << "b" << 1 ) ),
-                                       1 );
-                ASSERT( frv8.isSingleInterval() );
-                // With missing second field is still a single compound interval.
-                FieldRangeVector frv9( FieldRangeSet( "dummy",
-                                                      BSON( "b" << 5 ),
-                                                      true,
-                                                      true ),
-                                       ( BSON( "a" << 1 << "b" << 1 ) ),
-                                       1 );
-                ASSERT( !frv9.isSingleInterval() );
-
-                // Equality on first two fields and single interval on third field is a compound
-                // single interval.
-                FieldRangeVector frv10( FieldRangeSet( "dummy",
-                                                       fromjson( "{a:5,b:6,c:{$gt:7}}" ),
-                                                       true,
-                                                       true ),
-                                        ( BSON( "a" << 1 << "b" << 1 << "c" << 1 ) ),
-                                        1 );
-                ASSERT( frv10.isSingleInterval() );
-
-                // Equality, then single interval, then missing is a compound single interval.
-                FieldRangeVector frv11( FieldRangeSet( "dummy",
-                                                       fromjson( "{a:5,b:{$gt:7}}" ),
-                                                       true,
-                                                       true ),
-                                        ( BSON( "a" << 1 << "b" << 1 << "c" << 1 ) ),
-                                        1 );
-                ASSERT( frv11.isSingleInterval() );
-                // Equality, then single interval, then missing, then missing is a compound single
-                // interval.
-                FieldRangeVector frv12( FieldRangeSet( "dummy",
-                                                       fromjson( "{a:5,b:{$gt:7}}" ),
-                                                       true,
-                                                       true ),
-                                        ( BSON( "a" << 1 <<
-                                                         "b" << 1 <<
-                                                         "c" << 1 <<
-                                                         "d" << 1 ) ),
-                                        1 );
-                ASSERT( frv12.isSingleInterval() );
-                // Equality, then single interval, then missing, then missing, with mixed order
-                // fields is a compound single interval.
-                FieldRangeVector frv13( FieldRangeSet( "dummy",
-                                                       fromjson( "{a:5,b:{$gt:7}}" ),
-                                                       true,
-                                                       true ),
-                                        ( BSON( "a" << 1 <<
-                                                         "b" << 1 <<
-                                                         "c" << 1 <<
-                                                         "d" << -1 ) ),
-                                        1 );
-                ASSERT( frv13.isSingleInterval() );
-                // Equality, then single interval, then missing, then single interval is not a
-                // compound single interval.
-                FieldRangeVector frv14( FieldRangeSet( "dummy",
-                                                       fromjson( "{a:5,b:{$gt:7},d:{$gt:1}}" ),
-                                                       true,
-                                                       true ),
-                                        ( BSON( "a" << 1 <<
-                                                         "b" << 1 <<
-                                                         "c" << 1 <<
-                                                         "d" << 1 ) ),
-                                        1 );
-                ASSERT( !frv14.isSingleInterval() );
-            }
-        };
-
-        /** Check start and end key values. */
-        class StartEndKey {
-        public:
-            void run() {
-                // Equality on a single field.
-                FieldRangeVector frv1( FieldRangeSet( "dummy", BSON( "a" << 5 ), true, true ),
-                                       ( BSON( "a" << 1 ) ),
-                                       1 );
-                ASSERT_EQUALS( BSON( "" << 5 ), frv1.startKey() );
-                ASSERT( frv1.startKeyInclusive() );
-                ASSERT_EQUALS( BSON( "" << 5 ), frv1.endKey() );
-                ASSERT( frv1.endKeyInclusive() );
-                // Single interval on a single field.
-                FieldRangeVector frv2( FieldRangeSet( "dummy", BSON( "a" << GT << 5 ), true, true ),
-                                       ( BSON( "a" << 1 ) ),
-                                       1 );
-                ASSERT_EQUALS( BSON( "" << 5 ), frv2.startKey() );
-                ASSERT( !frv2.startKeyInclusive() );
-                ASSERT_EQUALS( BSON( "" << numeric_limits<double>::max() ), frv2.endKey() );
-                ASSERT( frv2.endKeyInclusive() );
-
-                // Equality on two fields.
-                FieldRangeVector frv3( FieldRangeSet( "dummy",
-                                                      BSON( "a" << 5 << "b" << 6 ),
-                                                      true,
-                                                      true ),
-                                       ( BSON( "a" << 1 << "b" << 1 ) ),
-                                       1 );
-                ASSERT_EQUALS( BSON( "" << 5 << "" << 6 ), frv3.startKey() );
-                ASSERT( frv3.startKeyInclusive() );
-                ASSERT_EQUALS( BSON( "" << 5 << "" << 6 ), frv3.endKey() );
-                ASSERT( frv3.endKeyInclusive() );
-                // Equality on first field and single interval on second field.
-                FieldRangeVector frv4( FieldRangeSet( "dummy",
-                                                      BSON( "a" << 5 << "b" << LT << 6 ),
-                                                      true,
-                                                      true ),
-                                       ( BSON( "a" << 1 << "b" << 1 ) ),
-                                       1 );
-                ASSERT_EQUALS( BSON( "" << 5 << "" << -numeric_limits<double>::max() ),
-                               frv4.startKey() );
-                ASSERT( frv4.startKeyInclusive() );
-                ASSERT_EQUALS( BSON( "" << 5 << "" << 6 ),
-                               frv4.endKey() );
-                ASSERT( !frv4.endKeyInclusive() );
-
-                // With missing second field.
-                FieldRangeVector frv5( FieldRangeSet( "dummy",
-                                                      BSON( "a" << 5 ),
-                                                      true,
-                                                      true ),
-                                       ( BSON( "a" << 1 << "b" << 1 ) ),
-                                       1 );
-                ASSERT_EQUALS( BSON( "" << 5 << "" << MINKEY ), frv5.startKey() );
-                ASSERT( frv5.startKeyInclusive() );
-                ASSERT_EQUALS( BSON( "" << 5 << "" << MAXKEY ), frv5.endKey() );
-                ASSERT( frv5.endKeyInclusive() );
-                // Equality, then single interval, then missing.
-                FieldRangeVector frv6( FieldRangeSet( "dummy",
-                                                      fromjson( "{a:5,b:{$gt:7}}" ),
-                                                      true,
-                                                      true ),
-                                       ( BSON( "a" << 1 << "b" << 1 << "c" << 1 ) ),
-                                       1 );
-                ASSERT_EQUALS( BSON( "" << 5 << "" << 7 << "" << MAXKEY ), frv6.startKey() );
-                ASSERT( !frv6.startKeyInclusive() );
-                ASSERT_EQUALS( BSON( "" << 5 <<
-                                     "" << numeric_limits<double>::max() <<
-                                     "" << MAXKEY ),
-                               frv6.endKey() );
-                ASSERT( frv6.endKeyInclusive() );
-                // Equality, then single interval, then missing, then missing.
-                FieldRangeVector frv7( FieldRangeSet( "dummy",
-                                                      fromjson( "{a:5,b:{$gt:7}}" ),
-                                                      true,
-                                                      true ),
-                                       ( BSON( "a" << 1 <<
-                                                        "b" << 1 <<
-                                                        "c" << 1 <<
-                                                        "d" << 1 ) ),
-                                       1 );
-                ASSERT_EQUALS( BSON( "" << 5 << "" << 7 << "" << MAXKEY << "" << MAXKEY ),
-                               frv7.startKey() );
-                ASSERT( !frv7.startKeyInclusive() );
-                ASSERT_EQUALS( BSON( "" << 5 <<
-                                     "" << numeric_limits<double>::max() <<
-                                     "" << MAXKEY <<
-                                     "" << MAXKEY ),
-                               frv7.endKey() );
-                ASSERT( frv7.endKeyInclusive() );
-
-                // Equality, then single exclusive interval on both ends, then missing, then
-                // missing with mixed direction index ordering.
-                FieldRangeVector frv8( FieldRangeSet( "dummy",
-                                                      fromjson( "{a:5,b:{$gt:7,$lt:10}}" ),
-                                                      true,
-                                                      true ),
-                                       ( BSON( "a" << 1 <<
-                                                        "b" << 1 <<
-                                                        "c" << 1 <<
-                                                        "d" << -1 ) ),
-                                       1 );
-                ASSERT_EQUALS( BSON( "" << 5 << "" << 7 << "" << MAXKEY << "" << MINKEY ),
-                               frv8.startKey() );
-                ASSERT( !frv8.startKeyInclusive() );
-                ASSERT_EQUALS( BSON( "" << 5 << "" << 10 << "" << MINKEY << "" << MAXKEY ),
-                               frv8.endKey() );
-                ASSERT( !frv8.endKeyInclusive() );
-                // Equality, then single exclusive interval on both ends, then missing, then
-                // missing with mixed direction index ordering and reverse direction traversal.
-                FieldRangeVector frv9( FieldRangeSet( "dummy",
-                                                      fromjson( "{a:5,b:{$gt:7,$lt:10}}" ),
-                                                      true,
-                                                      true ),
-                                       ( BSON( "a" << 1 <<
-                                                        "b" << 1 <<
-                                                        "c" << 1 <<
-                                                        "d" << -1 ) ),
-                                       -1 );
-                ASSERT_EQUALS( BSON( "" << 5 << "" << 10 << "" << MINKEY << "" << MAXKEY ),
-                               frv9.startKey() );
-                ASSERT( !frv9.startKeyInclusive() );
-                ASSERT_EQUALS( BSON( "" << 5 << "" << 7 << "" << MAXKEY << "" << MINKEY ),
-                               frv9.endKey() );
-                ASSERT( !frv9.endKeyInclusive() );
-            }
-        };
-
-    } // namespace FieldRangeVectorTests
-    
-    // These are currently descriptive, not normative tests.  SERVER-5450
-    namespace FieldRangeVectorIteratorTests {
-        
-        class Base {
-        public:
-            virtual ~Base() {}
-            void run() {
-                FieldRangeSet fieldRangeSet( "", query(), true, true );
-                FieldRangeVector fieldRangeVector( fieldRangeSet, index(), 1 );
-                _iterator.reset( new FieldRangeVectorIterator( fieldRangeVector,
-                                                              singleIntervalLimit() ) );
-                _iterator->advance( fieldRangeVector.startKey() );
-                _iterator->prepDive();
-                check();
-            }
-        protected:
-            virtual BSONObj query() = 0;
-            virtual BSONObj index() = 0;
-            virtual int singleIntervalLimit() { return 0; }
-            virtual void check() = 0;
-            void assertAdvanceToNext( const BSONObj &current ) {
-                ASSERT_EQUALS( -1, advance( current ) );
-            }
-            void assertAdvanceTo( const BSONObj &current, const BSONObj &target,
-                                 const BSONObj &inclusive = BSONObj() ) {
-                int partition = advance( current );
-                ASSERT( !iterator().after() );
-                BSONObjBuilder advanceToBuilder;
-                advanceToBuilder.appendElements( currentPrefix( current, partition ) );
-                for( int i = partition; i < (int)iterator().cmp().size(); ++i ) {
-                    advanceToBuilder << *iterator().cmp()[ i ];
-                }
-                assertEqualWithoutFieldNames( target, advanceToBuilder.obj() );
-                if ( !inclusive.isEmpty() ) {
-                    BSONObjIterator inc( inclusive );
-                    for( int i = 0; i < partition; ++i ) inc.next();
-                    for( int i = partition; i < (int)iterator().inc().size(); ++i ) {
-                        ASSERT_EQUALS( inc.next().Bool(), iterator().inc()[ i ] );
-                    }
-                }
-            }
-            void assertAdvanceToAfter( const BSONObj &current, const BSONObj &target ) {
-                int partition = advance( current );
-                ASSERT( iterator().after() );
-                assertEqualWithoutFieldNames( target, currentPrefix( current, partition ) );
-            }
-            void assertDoneAdvancing( const BSONObj &current ) {
-                ASSERT_EQUALS( -2, advance( current ) );                    
-            }
-            BSONElement minElt() const { return minKey.firstElement(); }
-            BSONElement maxElt() const { return maxKey.firstElement(); }
-        private:
-            static bool equalWithoutFieldNames( const BSONObj &one, const BSONObj &two ) {
-                return one.woCompare( two, BSONObj(), false ) == 0;
-            }
-            static void assertEqualWithoutFieldNames( const BSONObj &one, const BSONObj &two ) {
-                if ( !equalWithoutFieldNames( one, two ) ) {
-                    mongo::unittest::log() << one << " != " << two << endl;
-                    ASSERT( equalWithoutFieldNames( one, two ) );
-                }
-            }
-            BSONObj currentPrefix( const BSONObj &current, int partition ) {
-                ASSERT( partition >= 0 );
-                BSONObjIterator currentIter( current );
-                BSONObjBuilder prefixBuilder;
-                for( int i = 0; i < partition; ++i ) {
-                    prefixBuilder << currentIter.next();
-                }
-                return prefixBuilder.obj();                
-            }
-            FieldRangeVectorIterator &iterator() { return *_iterator; }
-            int advance( const BSONObj &current ) {
-                return iterator().advance( current );
-            }
-            scoped_ptr<FieldRangeVectorIterator> _iterator;
-        };
-        
-        class AdvanceToNextIntervalEquality : public Base {
-            BSONObj query() { return fromjson( "{a:{$in:[0,1]}}" ); }
-            BSONObj index() { return BSON( "a" << 1 ); }
-            void check() {
-                assertAdvanceToNext( BSON( "a" << 0 ) );
-                assertAdvanceTo( BSON( "a" << 0.5 ), BSON( "a" << 1 ) );
-            }
-        };
-        
-        class AdvanceToNextIntervalExclusiveInequality : public Base {
-            BSONObj query() { return fromjson( "{a:{$in:['a',/^q/,'z']}}" ); }
-            BSONObj index() { return BSON( "a" << 1 ); }
-            void check() {
-                assertAdvanceToNext( BSON( "a" << "a" ) );
-                assertAdvanceToNext( BSON( "a" << "q" ) );
-                assertAdvanceTo( BSON( "a" << "r" ), BSON( "a" << "z" ) );
-                assertAdvanceToNext( BSON( "a" << "z" ) );
-            }            
-        };
-
-        class AdvanceToNextIntervalEqualityReverse : public Base {
-            BSONObj query() { return fromjson( "{a:{$in:[0,1]}}" ); }
-            BSONObj index() { return BSON( "a" << -1 ); }
-            void check() {
-                assertAdvanceToNext( BSON( "a" << 1 ) );
-                assertAdvanceTo( BSON( "a" << 0.5 ), BSON( "a" << 0 ) );
-            }
-        };
-
-        class AdvanceToNextIntervalEqualityCompound : public Base {
-            BSONObj query() { return fromjson( "{a:{$in:[0,1]},b:{$in:[4,5]}}" ); }
-            BSONObj index() { return BSON( "a" << 1 << "b" << 1 ); }
-            void check() {
-                assertAdvanceToNext( BSON( "a" << 0 << "b" << 5 ) );
-                assertAdvanceToAfter( BSON( "a" << 0 << "b" << 6 ), BSON( "a" << 0 ) );
-                assertAdvanceTo( BSON( "a" << 1 << "b" << 2 ), BSON( "a" << 1 << "b" << 4 ) );
-                assertAdvanceToNext( BSON( "a" << 1 << "b" << 4 ) );
-                assertDoneAdvancing( BSON( "a" << 1 << "b" << 5.1 ) );
-            }            
-        };
-
-        class AdvanceToNextIntervalIntermediateEqualityCompound : public Base {
-            BSONObj query() { return fromjson( "{a:{$in:[0,1]},b:{$in:[4,5]}}" ); }
-            BSONObj index() { return BSON( "a" << 1 << "b" << 1 ); }
-            void check() {
-                assertAdvanceToNext( BSON( "a" << 0 << "b" << 5 ) );
-                assertAdvanceTo( BSON( "a" << 0.5 << "b" << 6 ), BSON( "a" << 1 << "b" << 4 ) );
-                assertAdvanceToNext( BSON( "a" << 1 << "b" << 4 ) );
-            }            
-        };
-
-        class AdvanceToNextIntervalIntermediateInMixed : public Base {
-            BSONObj query() { return fromjson( "{a:{$in:[0,1]},b:{$in:[/^a/,'c'],$ne:'a'}}" ); }
-            BSONObj index() { return BSON( "a" << 1 << "b" << 1 ); }
-            void check() {
-                assertAdvanceTo( BSON( "a" << 0 << "b" << "bb" ), BSON( "a" << 0 << "b" << "c" ),
-                                BSON( "a" << 0 << "b" << true ) );
-                assertAdvanceTo( BSON( "a" << 0.5 << "b" << "a" ), BSON( "a" << 1 << "b" << "a" ),
-                                BSON( "a" << true << "b" << false ) );
-            }            
-        };
-
-        class BeforeLowerBound : public Base {
-            BSONObj query() { return fromjson( "{a:{$in:[0,1]},b:{$in:[4,5]}}" ); }
-            BSONObj index() { return BSON( "a" << 1 << "b" << 1 ); }
-            void check() {
-                assertAdvanceTo( BSON( "a" << 0 << "b" << 1 ), BSON( "a" << 0 << "b" << 4 ) );
-                assertAdvanceToNext( BSON( "a" << 0 << "b" << 4 ) );
-            }            
-        };
-        
-        class BeforeLowerBoundMixed : public Base {
-            BSONObj query() { return fromjson( "{a:{$in:[0,1]},b:{$in:[/^a/,'c'],$ne:'a'}}" ); }
-            BSONObj index() { return BSON( "a" << 1 << "b" << 1 ); }
-            void check() {
-                assertAdvanceTo( BSON( "a" << 0 << "b" << "" ), BSON( "a" << 0 << "b" << "a" ),
-                                BSON( "a" << 0 << "b" << false ) );
-                assertAdvanceTo( BSON( "a" << 1 << "b" << "bb" ), BSON( "a" << 1 << "b" << "c" ),
-                                BSON( "a" << 0 << "b" << true ) );
-            }            
-        };
-        
-        class AdvanceToNextExclusiveIntervalCompound : public Base {
-            BSONObj query() { return fromjson( "{a:{$in:['x',/^y/],$ne:'y'},b:{$in:[0,1]}}" ); }
-            BSONObj index() { return fromjson( "{a:1,b:1}" ); }
-            void check() {
-                assertAdvanceToNext( BSON( "a" << "x" << "b" << 1 ) );
-                assertAdvanceToAfter( BSON( "a" << "y" << "b" << 0 ), BSON( "a" << "y" ) );
-                assertAdvanceToNext( BSON( "a" << "yy" << "b" << 0 ) );
-            }
-        };
-        
-        class AdvanceRange : public Base {
-            BSONObj query() { return fromjson( "{a:{$gt:2,$lt:8}}" ); }
-            BSONObj index() { return fromjson( "{a:1}" ); }
-            void check() {
-                assertAdvanceToNext( BSON( "a" << 2 ) );
-                assertAdvanceToNext( BSON( "a" << 4 ) );
-                assertAdvanceToNext( BSON( "a" << 5 ) );
-                assertDoneAdvancing( BSON( "a" << 9 ) );
-            }
-        };
-        
-        class AdvanceInRange : public Base {
-            BSONObj query() { return fromjson( "{a:{$in:[0,1]},b:{$gt:2,$lt:8}}" ); }
-            BSONObj index() { return fromjson( "{a:1,b:1}" ); }
-            void check() {
-                assertAdvanceToNext( BSON( "a" << 0 << "b" << 5 ) );
-                assertAdvanceToNext( BSON( "a" << 0 << "b" << 5 ) );
-            }
-        };
-        
-        class AdvanceRangeIn : public Base {
-            BSONObj query() { return fromjson( "{a:{$gt:2,$lt:8},b:{$in:[0,1]}}" ); }
-            BSONObj index() { return fromjson( "{a:1,b:1}" ); }
-            void check() {
-                assertAdvanceToNext( BSON( "a" << 4 << "b" << 1 ) );
-                assertAdvanceToNext( BSON( "a" << 5 << "b" << 0 ) );
-            }
-        };
-
-        class AdvanceRangeRange : public Base {
-            BSONObj query() { return fromjson( "{a:{$gt:2,$lt:8},b:{$gt:1,$lt:4}}" ); }
-            BSONObj index() { return fromjson( "{a:1,b:1}" ); }
-            void check() {
-                assertAdvanceTo( BSON( "a" << 4 << "b" << 0 ), BSON( "a" << 4 << "b" << 1 ) );
-                assertAdvanceToAfter( BSON( "a" << 4 << "b" << 6 ), BSON( "a" << 4 ) );
-            }
-        };
-
-        class AdvanceRangeRangeMultiple : public Base {
-            BSONObj query() { return fromjson( "{a:{$gt:2,$lt:8},b:{$gt:1,$lt:4}}" ); }
-            BSONObj index() { return fromjson( "{a:1,b:1}" ); }
-            void check() {
-                assertAdvanceToNext( BSON( "a" << 4 << "b" << 3 ) );
-                assertAdvanceToNext( BSON( "a" << 4 << "b" << 3 ) );
-            }
-        };
-
-        class AdvanceRangeRangeIn : public Base {
-            BSONObj query() { return fromjson( "{a:{$gt:2,$lt:8},b:{$gt:1,$lt:4},c:{$in:[6,7]}}" ); }
-            BSONObj index() { return fromjson( "{a:1,b:1,c:1}" ); }
-            void check() {
-                assertAdvanceToNext( BSON( "a" << 4 << "b" << 3 << "c" << 7 ) );
-                assertAdvanceToAfter( BSON( "a" << 4 << "b" << 6 << "c" << 7 ), BSON( "a" << 4 ) );
-                assertAdvanceToNext( BSON( "a" << 5 << "b" << 3 << "c" << 6 ) );
-            }
-        };
-        
-        class AdvanceRangeMixed : public Base {
-            BSONObj query() {
-                return fromjson( "{a:{$gt:2,$lt:8},b:{$in:['a',/^b/],$ne:'b'}}" );
-            }
-            BSONObj index() { return fromjson( "{a:1,b:1}" ); }
-            void check() {
-                assertAdvanceToNext( BSON( "a" << 4 << "b" << "a" ) );
-                assertAdvanceToAfter( fromjson( "{a:4,b:'b'}" ), BSON( "a" << 4 << "b" << "b" ) );
-            }            
-        };
-
-        class AdvanceRangeMixed2 : public Base {
-            BSONObj query() {
-                return fromjson( "{a:{$gt:2,$lt:8},b:{$in:['a',/^b/],$ne:'b'}}" );
-            }
-            BSONObj index() { return fromjson( "{a:1,b:1}" ); }
-            void check() {
-                assertAdvanceToNext( BSON( "a" << 4 << "b" << "a" ) );
-                assertAdvanceTo( BSON( "a" << 4 << "b" << "aa" ), BSON( "a" << 4 << "b" << "b" ),
-                                BSON( "a" << 0 << "b" << false ) );
-            }            
-        };
-
-        class AdvanceRangeMixedIn : public Base {
-            BSONObj query() {
-                return fromjson( "{a:{$gt:2,$lt:8},b:{$in:[/^a/,'c']},c:{$in:[6,7]}}" );
-            }
-            BSONObj index() { return fromjson( "{a:1,b:1,c:1}" ); }
-            void check() {
-                assertAdvanceToNext( BSON( "a" << 4 << "b" << "aa" << "c" << 7 ) );
-                assertAdvanceToAfter( fromjson( "{a:4,b:/^q/,c:7}" ), BSON( "a" << 4 ) );
-                assertAdvanceToNext( BSON( "a" << 5 << "b" << "c" << "c" << 6 ) );
-            }
-        };
-
-        class AdvanceRangeMixedMixed : public Base {
-            BSONObj query() {
-                return fromjson( "{a:{$gt:2,$lt:8},b:{$in:['a',/^b/],$ne:'b'},"
-                                "c:{$in:[/^a/,'c'],$ne:'a'}}" );
-            }
-            BSONObj index() { return fromjson( "{a:1,b:1,c:1}" ); }
-            void check() {
-                assertAdvanceTo( BSON( "a" << 4 << "b" << "a" << "c" << "bb" ),
-                                BSON( "a" << 4 << "b" << "a" << "c" << "c" ) );
-                assertAdvanceTo( BSON( "a" << 4 << "b" << "aa" << "c" << "b" ),
-                                BSON( "a" << 4 << "b" << "b" << "c" << "a" ),
-                                BSON( "a" << 0 << "b" << false << "c" << false ) );
-            }
-        };
-        
-        class AdvanceMixedMixedIn : public Base {
-            BSONObj query() {
-                return fromjson( "{a:{$in:[/^a/,'c']},b:{$in:[/^a/,'c']},c:{$in:[6,7]}}" );
-            }
-            BSONObj index() { return fromjson( "{a:1,b:1,c:1}" ); }
-            void check() {
-                assertAdvanceToNext( BSON( "a" << "a" << "b" << "aa" << "c" << 7 ) );
-                assertAdvanceToAfter( fromjson( "{a:'a',b:/^q/,c:7}" ), BSON( "a" << "a" ) );
-                assertAdvanceToNext( BSON( "a" << "c" << "b" << "c" << "c" << 6 ) );
-            }
-        };
-
-        namespace CompoundRangeCounter {
-
-            class RangeTracking {
-            public:
-                RangeTracking() : _counter( 2, 0 ) {}
-                void run() {
-                    ASSERT_EQUALS( 2, _counter.size() );
-                    checkValues( -1, -1 );
-
-                    _counter.setZeroes( 0 );
-                    checkValues( 0, 0 );
-
-                    _counter.setUnknowns( 1 );
-                    checkValues( 0, -1 );
-
-                    _counter.setZeroes( 1 );
-                    checkValues( 0, 0 );
-
-                    _counter.setUnknowns( 0 );
-                    checkValues( -1, -1 );
-                    
-                    _counter.set( 0, 3 );
-                    checkValues( 3, -1 );
-
-                    _counter.inc( 0 );
-                    checkValues( 4, -1 );
-
-                    _counter.set( 1, 5 );
-                    checkValues( 4, 5 );
-
-                    _counter.inc( 1 );
-                    checkValues( 4, 6 );
-                }
-            private:
-                void checkValues( int first, int second ) {
-                    ASSERT_EQUALS( first, _counter.get( 0 ) );
-                    ASSERT_EQUALS( second, _counter.get( 1 ) );                
-                }
-                FieldRangeVectorIterator::CompoundRangeCounter _counter;
-            };
-            
-            class SingleIntervalCount {
-            public:
-                SingleIntervalCount() : _counter( 2, 2 ) {}
-                void run() {
-                    assertLimitNotReached();
-
-                    _counter.incSingleIntervalCount();
-                    assertLimitNotReached();
-
-                    _counter.incSingleIntervalCount();
-                    assertLimitReached();
-
-                    _counter.set( 1, 1 );
-                    assertLimitNotReached();
-                }
-            private:
-                void assertLimitReached() const {
-                    ASSERT( _counter.hasSingleIntervalCountReachedLimit() );
-                }
-                void assertLimitNotReached() const {
-                    ASSERT( !_counter.hasSingleIntervalCountReachedLimit() );
-                }
-                FieldRangeVectorIterator::CompoundRangeCounter _counter;
-            };
-            
-            class SingleIntervalCountUpdateBase {
-            public:
-                SingleIntervalCountUpdateBase() : _counter( 2, 1 ) {}
-                virtual ~SingleIntervalCountUpdateBase() {}
-                void run() {
-                    _counter.incSingleIntervalCount();
-                    ASSERT( _counter.hasSingleIntervalCountReachedLimit() );
-                    applyUpdate();
-                    ASSERT( !_counter.hasSingleIntervalCountReachedLimit() );                    
-                }
-            protected:
-                virtual void applyUpdate() = 0;
-                FieldRangeVectorIterator::CompoundRangeCounter &counter() { return _counter; }
-            private:
-                FieldRangeVectorIterator::CompoundRangeCounter _counter;
-            };
-
-            class Set : public SingleIntervalCountUpdateBase {
-                void applyUpdate() { counter().set( 0, 1 ); }
-            };
-
-            class Inc : public SingleIntervalCountUpdateBase {
-                void applyUpdate() { counter().inc( 1 ); }
-            };
-
-            class SetZeroes : public SingleIntervalCountUpdateBase {
-                void applyUpdate() { counter().setZeroes( 0 ); }
-            };
-
-            class SetUnknowns : public SingleIntervalCountUpdateBase {
-                void applyUpdate() { counter().setUnknowns( 1 ); }
-            };
-
-        } // namespace CompoundRangeCounter
-
-        namespace FieldIntervalMatcher {
-            
-            class IsEqInclusiveUpperBound {
-            public:
-                void run() {
-                    BSONObj exclusiveInterval = BSON( "$lt" << 5 );
-                    for ( int i = 4; i <= 6; ++i ) {
-                        for ( int reverse = 0; reverse < 2; ++reverse ) {
-                            ASSERT( !isEqInclusiveUpperBound( exclusiveInterval, BSON( "" << i ),
-                                                             reverse ) );
-                        }
-                    }
-                    BSONObj inclusiveInterval = BSON( "$lte" << 4 );
-                    for ( int i = 3; i <= 5; i += 2 ) {
-                        for ( int reverse = 0; reverse < 2; ++reverse ) {
-                            ASSERT( !isEqInclusiveUpperBound( inclusiveInterval, BSON( "" << i ),
-                                                             reverse ) );
-                        }
-                    }
-                    ASSERT( isEqInclusiveUpperBound( inclusiveInterval, BSON( "" << 4 ), true ) );
-                    ASSERT( isEqInclusiveUpperBound( inclusiveInterval, BSON( "" << 4 ), false ) );
-                }
-            private:
-                bool isEqInclusiveUpperBound( const BSONObj &intervalSpec,
-                                             const BSONObj &elementSpec,
-                                             bool reverse ) {
-                    FieldRange range( intervalSpec.firstElement(), false, true );
-                    BSONElement element = elementSpec.firstElement();
-                    FieldRangeVectorIterator::FieldIntervalMatcher matcher
-                            ( range.intervals()[ 0 ], element, reverse );
-                    return matcher.isEqInclusiveUpperBound();
-                }
-            };
-            
-            class IsGteUpperBound {
-            public:
-                void run() {
-                    BSONObj exclusiveInterval = BSON( "$lt" << 5 );
-                    ASSERT( !isGteUpperBound( exclusiveInterval, BSON( "" << 4 ), false ) );
-                    ASSERT( isGteUpperBound( exclusiveInterval, BSON( "" << 5 ), false ) );
-                    ASSERT( isGteUpperBound( exclusiveInterval, BSON( "" << 6 ), false ) );
-                    ASSERT( isGteUpperBound( exclusiveInterval, BSON( "" << 4 ), true ) );
-                    ASSERT( isGteUpperBound( exclusiveInterval, BSON( "" << 5 ), true ) );
-                    ASSERT( !isGteUpperBound( exclusiveInterval, BSON( "" << 6 ), true ) );
-                    BSONObj inclusiveInterval = BSON( "$lte" << 4 );
-                    ASSERT( !isGteUpperBound( inclusiveInterval, BSON( "" << 3 ), false ) );
-                    ASSERT( isGteUpperBound( inclusiveInterval, BSON( "" << 4 ), false ) );
-                    ASSERT( isGteUpperBound( inclusiveInterval, BSON( "" << 5 ), false ) );
-                    ASSERT( isGteUpperBound( inclusiveInterval, BSON( "" << 3 ), true ) );
-                    ASSERT( isGteUpperBound( inclusiveInterval, BSON( "" << 4 ), true ) );
-                    ASSERT( !isGteUpperBound( inclusiveInterval, BSON( "" << 5 ), true ) );
-                }
-            private:
-                bool isGteUpperBound( const BSONObj &intervalSpec, const BSONObj &elementSpec,
-                                     bool reverse ) {
-                    FieldRange range( intervalSpec.firstElement(), false, true );
-                    BSONElement element = elementSpec.firstElement();
-                    FieldRangeVectorIterator::FieldIntervalMatcher matcher
-                            ( range.intervals()[ 0 ], element, reverse );
-                    return matcher.isGteUpperBound();
-                }
-            };
-
-            class IsEqExclusiveLowerBound {
-            public:
-                void run() {
-                    BSONObj exclusiveInterval = BSON( "$gt" << 5 );
-                    for ( int i = 4; i <= 6; i += 2 ) {
-                        for ( int reverse = 0; reverse < 2; ++reverse ) {
-                            ASSERT( !isEqExclusiveLowerBound( exclusiveInterval, BSON( "" << i ),
-                                                             reverse ) );
-                        }
-                    }
-                    ASSERT( isEqExclusiveLowerBound( exclusiveInterval, BSON( "" << 5 ), true ) );
-                    ASSERT( isEqExclusiveLowerBound( exclusiveInterval, BSON( "" << 5 ), false ) );
-                    BSONObj inclusiveInterval = BSON( "$gte" << 4 );
-                    for ( int i = 3; i <= 5; ++i ) {
-                        for ( int reverse = 0; reverse < 2; ++reverse ) {
-                            ASSERT( !isEqExclusiveLowerBound( inclusiveInterval, BSON( "" << i ),
-                                                             reverse ) );
-                        }
-                    }
-                }
-            private:
-                bool isEqExclusiveLowerBound( const BSONObj &intervalSpec,
-                                             const BSONObj &elementSpec,
-                                             bool reverse ) {
-                    FieldRange range( intervalSpec.firstElement(), false, true );
-                    BSONElement element = elementSpec.firstElement();
-                    FieldRangeVectorIterator::FieldIntervalMatcher matcher
-                            ( range.intervals()[ 0 ], element, reverse );
-                    return matcher.isEqExclusiveLowerBound();
-                }
-            };
-
-            class IsLtLowerBound {
-            public:
-                void run() {
-                    BSONObj exclusiveInterval = BSON( "$gt" << 5 );
-                    ASSERT( isLtLowerBound( exclusiveInterval, BSON( "" << 4 ), false ) );
-                    ASSERT( !isLtLowerBound( exclusiveInterval, BSON( "" << 5 ), false ) );
-                    ASSERT( !isLtLowerBound( exclusiveInterval, BSON( "" << 6 ), false ) );
-                    ASSERT( !isLtLowerBound( exclusiveInterval, BSON( "" << 4 ), true ) );
-                    ASSERT( !isLtLowerBound( exclusiveInterval, BSON( "" << 5 ), true ) );
-                    ASSERT( isLtLowerBound( exclusiveInterval, BSON( "" << 6 ), true ) );
-                    BSONObj inclusiveInterval = BSON( "$gte" << 4 );
-                    ASSERT( isLtLowerBound( inclusiveInterval, BSON( "" << 3 ), false ) );
-                    ASSERT( !isLtLowerBound( inclusiveInterval, BSON( "" << 4 ), false ) );
-                    ASSERT( !isLtLowerBound( inclusiveInterval, BSON( "" << 5 ), false ) );
-                    ASSERT( !isLtLowerBound( inclusiveInterval, BSON( "" << 3 ), true ) );
-                    ASSERT( !isLtLowerBound( inclusiveInterval, BSON( "" << 4 ), true ) );
-                    ASSERT( isLtLowerBound( inclusiveInterval, BSON( "" << 5 ), true ) );
-                }
-            private:
-                bool isLtLowerBound( const BSONObj &intervalSpec, const BSONObj &elementSpec,
-                                     bool reverse ) {
-                    FieldRange range( intervalSpec.firstElement(), false, true );
-                    BSONElement element = elementSpec.firstElement();
-                    FieldRangeVectorIterator::FieldIntervalMatcher matcher
-                            ( range.intervals()[ 0 ], element, reverse );
-                    return matcher.isLtLowerBound();
-                }
-            };
-            
-            class CheckLowerAfterUpper {
-            public:
-                void run() {
-                    BSONObj intervalSpec = BSON( "$in" << BSON_ARRAY( 1 << 2 ) );
-                    BSONObj elementSpec = BSON( "" << 1 );
-                    FieldRange range( intervalSpec.firstElement(), false, true );
-                    BSONElement element = elementSpec.firstElement();
-                    FieldRangeVectorIterator::FieldIntervalMatcher matcher
-                            ( range.intervals()[ 0 ], element, false );
-                    ASSERT( matcher.isEqInclusiveUpperBound() );
-                    ASSERT( matcher.isGteUpperBound() );
-                    ASSERT( !matcher.isEqExclusiveLowerBound() );
-                    ASSERT( !matcher.isLtLowerBound() );
-                }
-            };
-
-        } // namespace FieldIntervalMatcher
-
-        namespace SingleIntervalLimit {
-
-            class NoLimit : public Base {
-                BSONObj query() { return BSON( "a" << 1 ); }
-                BSONObj index() { return BSON( "a" << 1 ); }
-                int singleIntervalLimit() { return 0; }
-                void check() {
-                    for( int i = 0; i < 100; ++i ) {
-                        assertAdvanceToNext( BSON( "a" << 1 ) );
-                    }
-                }
-            };
-
-            class OneIntervalLimit : public Base {
-                BSONObj query() { return BSON( "a" << 1 ); }
-                BSONObj index() { return BSON( "a" << 1 ); }
-                int singleIntervalLimit() { return 3; }
-                void check() {
-                    for( int i = 0; i < 3; ++i ) {
-                        assertAdvanceToNext( BSON( "a" << 1 ) );
-                    }
-                    assertDoneAdvancing( BSON( "a" << 1 ) );
-                }
-            };
-
-            class TwoIntervalLimit : public Base {
-                BSONObj query() { return fromjson( "{a:{$in:[0,1]}}" ); }
-                BSONObj index() { return BSON( "a" << 1 ); }
-                int singleIntervalLimit() { return 2; }
-                void check() {
-                    for( int i = 0; i < 2; ++i ) {
-                        assertAdvanceToNext( BSON( "a" << 0 ) );
-                    }
-                    assertAdvanceTo( BSON( "a" << 0 ), BSON( "a" << 1 ) );
-                    for( int i = 0; i < 2; ++i ) {
-                        assertAdvanceToNext( BSON( "a" << 1 ) );
-                    }
-                    assertDoneAdvancing( BSON( "a" << 1 ) );
-                }
-            };
-
-            class ThreeIntervalLimitUnreached : public Base {
-                BSONObj query() { return fromjson( "{a:{$in:[0,1,2]}}" ); }
-                BSONObj index() { return BSON( "a" << 1 ); }
-                int singleIntervalLimit() { return 2; }
-                void check() {
-                    for( int i = 0; i < 2; ++i ) {
-                        assertAdvanceToNext( BSON( "a" << 0 ) );
-                    }
-                    assertAdvanceTo( BSON( "a" << 1.5 ), BSON( "a" << 2 ) );
-                }
-            };
-
-            class FirstIntervalExhaustedBeforeLimit : public Base {
-                BSONObj query() { return fromjson( "{a:{$in:[0,1]}}" ); }
-                BSONObj index() { return BSON( "a" << 1 ); }
-                int singleIntervalLimit() { return 3; }
-                void check() {
-                    assertAdvanceToNext( BSON( "a" << 0 ) );
-                    for( int i = 0; i < 3; ++i ) {
-                        assertAdvanceToNext( BSON( "a" << 1 ) );
-                    }
-                    assertDoneAdvancing( BSON( "a" << 1 ) );
-                }
-            };
-
-            class FirstIntervalNotExhaustedAtLimit : public Base {
-                BSONObj query() { return fromjson( "{a:{$in:[0,1]}}" ); }
-                BSONObj index() { return BSON( "a" << 1 ); }
-                int singleIntervalLimit() { return 3; }
-                void check() {
-                    for( int i = 0; i < 3; ++i ) {
-                        assertAdvanceToNext( BSON( "a" << 0 ) );
-                    }
-                    for( int i = 0; i < 3; ++i ) {
-                        assertAdvanceToNext( BSON( "a" << 1 ) );
-                    }
-                    assertDoneAdvancing( BSON( "a" << 1 ) );
-                }
-            };
-            
-            class EqualIn : public Base {
-                BSONObj query() { return fromjson( "{a:1,b:{$in:[0,1]}}" ); }
-                BSONObj index() { return BSON( "a" << 1 << "b" << 1 ); }
-                int singleIntervalLimit() { return 3; }
-                void check() {
-                    for( int i = 0; i < 3; ++i ) {
-                        assertAdvanceToNext( BSON( "a" << 1 << "b" << 0 ) );
-                    }
-                    assertAdvanceTo( BSON( "a" << 1 << "b" << 0 ), BSON( "a" << 1 << "b" << 1 ) );
-                    for( int i = 0; i < 3; ++i ) {
-                        assertAdvanceToNext( BSON( "a" << 1 << "b" << 1 ) );
-                    }
-                    assertDoneAdvancing( BSON( "a" << 1 << "b" << 1 ) );
-                }
-            };
-            
-            class TwoIntervalIntermediateValue : public Base {
-                BSONObj query() { return fromjson( "{a:{$in:[0,1]}}" ); }
-                BSONObj index() { return BSON( "a" << 1 ); }
-                int singleIntervalLimit() { return 3; }
-                void check() {
-                    for( int i = 0; i < 2; ++i ) {
-                        assertAdvanceToNext( BSON( "a" << 0 ) );
-                    }
-                    assertAdvanceTo( BSON( "a" << 0.5 ), BSON( "a" << 1 ) );
-                    for( int i = 0; i < 3; ++i ) {
-                        assertAdvanceToNext( BSON( "a" << 1 ) );
-                    }
-                    assertDoneAdvancing( BSON( "a" << 1 ) );
-                }
-            };
-
-            class InGte : public Base {
-                BSONObj query() { return fromjson( "{a:{$in:[0,1]},b:{$gte:5}}" ); }
-                BSONObj index() { return BSON( "a" << 1 << "b" << 1 ); }
-                int singleIntervalLimit() { return 1; }
-                void check() {
-                    assertAdvanceToNext( BSON( "a" << 0 << "b" << 5 ) );
-                    assertAdvanceToAfter( BSON( "a" << 0 << "b" << 5 ), BSON( "a" << 0 ) );
-                    assertAdvanceTo( BSON( "a" << 0.5 << "b" << 6 ), BSON( "a" << 1 << "b" << 5 ) );
-                    assertAdvanceToNext( BSON( "a" << 1 << "b" << 7 ) );
-                    assertDoneAdvancing( BSON( "a" << 1 << "b" << 7 ) );
-                }
-            };
-            
-            class InEmptyGte : public Base {
-                BSONObj query() { return fromjson( "{a:{$in:[0,1,2,3,4]},b:{$gte:5}}" ); }
-                BSONObj index() { return BSON( "a" << 1 << "b" << 1 ); }
-                int singleIntervalLimit() { return 1; }
-                void check() {
-                    assertAdvanceToNext( BSON( "a" << 1 << "b" << 5 ) );
-                    assertAdvanceToAfter( BSON( "a" << 1 << "b" << 5 ), BSON( "a" << 1 ) );
-                    assertAdvanceTo( BSON( "a" << 2 << "b" << 2 ),
-                                    BSON( "a" << 2 << "b" << 5 ) );
-                    assertAdvanceToNext( BSON( "a" << 3 << "b" << 5 ) );
-                    assertDoneAdvancing( BSON( "a" << 4.1 << "b" << 2 ) );
-                }
-            };
-            
-            class InGt : public Base {
-                BSONObj query() { return fromjson( "{a:{$in:[0,1]},b:{$gt:5}}" ); }
-                BSONObj index() { return BSON( "a" << 1 << "b" << 1 ); }
-                int singleIntervalLimit() { return 1; }
-                void check() {
-                    assertAdvanceToNext( BSON( "a" << 0 << "b" << 5.1 ) );
-                    assertAdvanceToAfter( BSON( "a" << 0 << "b" << 5.1 ), BSON( "a" << 0 ) );
-                    assertAdvanceToAfter( BSON( "a" << 1 << "b" << 5 ),
-                                          BSON( "a" << 1 << "b" << 5 ) );
-                    assertAdvanceToNext( BSON( "a" << 1 << "b" << 5.01 ) );
-                    assertDoneAdvancing( BSON( "a" << 1 << "b" << 5.01 ) );
-                }
-            };
-
-            class InEmptyGt : public Base {
-                BSONObj query() { return fromjson( "{a:{$in:[0,1,2,3,4]},b:{$gt:5}}" ); }
-                BSONObj index() { return BSON( "a" << 1 << "b" << 1 ); }
-                int singleIntervalLimit() { return 1; }
-                void check() {
-                    assertAdvanceToNext( BSON( "a" << 1 << "b" << 5.1 ) );
-                    assertAdvanceToAfter( BSON( "a" << 1 << "b" << 5.1 ), BSON( "a" << 1 ) );
-                    assertAdvanceTo( BSON( "a" << 2 << "b" << 2 ),
-                                     BSON( "a" << 2 << "b" << 5 ) );
-                    assertAdvanceToNext( BSON( "a" << 3 << "b" << 5.01 ) );
-                    assertDoneAdvancing( BSON( "a" << 4.1 << "b" << 2 ) );
-                }
-            };
-
-            class InLt : public Base {
-                BSONObj query() { return fromjson( "{a:{$in:[0,1]},b:{$lt:5}}" ); }
-                BSONObj index() { return BSON( "a" << 1 << "b" << 1 ); }
-                int singleIntervalLimit() { return 1; }
-                void check() {
-                    assertAdvanceToNext( BSON( "a" << 0 << "b" << 2 ) );
-                    assertAdvanceToAfter( BSON( "a" << 0 << "b" << 2 ), BSON( "a" << 0 ) );
-                    assertDoneAdvancing( BSON( "a" << 1 << "b" << 5 ) );
-                }
-            };
-
-            class InGteLt : public Base {
-                BSONObj query() { return fromjson( "{a:{$in:[0,1,2]},b:{$gte:2,$lt:5}}" ); }
-                BSONObj index() { return BSON( "a" << 1 << "b" << 1 ); }
-                int singleIntervalLimit() { return 1; }
-                void check() {
-                    assertAdvanceToNext( BSON( "a" << 0 << "b" << 3 ) );
-                    assertAdvanceToAfter( BSON( "a" << 0 << "b" << 4 ), BSON( "a" << 0 ) );
-                    assertAdvanceToAfter( BSON( "a" << 1 << "b" << 5 ), BSON( "a" << 1 ) );
-                    assertAdvanceToNext( BSON( "a" << 2 << "b" << 4 ) );
-                    assertDoneAdvancing( BSON( "a" << 2 << "b" << 4 ) );
-                }
-            };
-
-            class InGtHigherLimit : public Base {
-                BSONObj query() { return fromjson( "{a:{$in:[0,1,2]},b:{$gt:5}}" ); }
-                BSONObj index() { return BSON( "a" << 1 << "b" << 1 ); }
-                int singleIntervalLimit() { return 2; }
-                void check() {
-                    assertAdvanceToNext( BSON( "a" << 0 << "b" << 5.1 ) );
-                    assertAdvanceToNext( BSON( "a" << 0 << "b" << 6 ) );
-                    assertAdvanceToAfter( BSON( "a" << 0 << "b" << 7 ), BSON( "a" << 0 ) );
-                    assertAdvanceToAfter( BSON( "a" << 1 << "b" << 5 ),
-                                         BSON( "a" << 1 << "b" << 5 ) );
-                    assertAdvanceToAfter( BSON( "a" << 2 << "b" << 5 ),
-                                         BSON( "a" << 2 << "b" << 5 ) );
-                    assertAdvanceToNext( BSON( "a" << 2 << "b" << 5.01 ) );
-                    assertAdvanceToNext( BSON( "a" << 2 << "b" << 5.02 ) );
-                    assertDoneAdvancing( BSON( "a" << 2 << "b" << 5.02 ) );
-                }
-            };
-
-            /**
-             * The singleIntervalLimit feature should not be used with multiple range bounds, in
-             * spite of the corner case checked in this test.
-             */
-            class TwoRange : public Base {
-                BSONObj query() { return fromjson( "{a:{$in:[/^a/,/^c/]}}" ); }
-                BSONObj index() { return BSON( "a" << 1 ); }
-                int singleIntervalLimit() { return 2; }
-                void check() {
-                    for( int i = 0; i < 2; ++i ) {
-                        assertAdvanceToNext( BSON( "a" << "a" ) );
-                    }
-                    assertAdvanceTo( BSON( "a" << "b" ), BSON( "a" << "c" ) );
-                }
-            };
-
-            class IndexPrefix : public Base {
-                BSONObj query() { return fromjson( "{a:{$in:[1,2]}}" ); }
-                BSONObj index() { return BSON( "a" << 1 << "b" << 1 ); }
-                int singleIntervalLimit() { return 1; }
-                void check() {
-                    assertAdvanceToNext( BSON( "a" << 1 << "b" << 1 ) );
-                    assertAdvanceTo( BSON( "a" << 1 << "b" << 3 ),
-                                     BSON( "a" << 2 << "b" << minElt() ) );
-                    assertAdvanceToNext( BSON( "a" << 2 << "b" << 0 ) );
-                    assertDoneAdvancing( BSON( "a" << 2 << "b" << 1 ) );
-                }
-            };
-            
-            class IndexPrefixReverseOrder : public Base {
-                BSONObj query() { return fromjson( "{a:{$in:[1,2]}}" ); }
-                BSONObj index() { return BSON( "a" << 1 << "b" << -1 ); }
-                int singleIntervalLimit() { return 1; }
-                void check() {
-                    assertAdvanceToNext( BSON( "a" << 1 << "b" << 1 ) );
-                    assertAdvanceTo( BSON( "a" << 1 << "b" << 0 ),
-                                    BSON( "a" << 2 << "b" << maxElt() ) );
-                    assertAdvanceToNext( BSON( "a" << 2 << "b" << 1 ) );
-                    assertDoneAdvancing( BSON( "a" << 2 << "b" << 0 ) );
-                }
-            };
-            
-            class LongerIndexPrefix : public Base {
-                BSONObj query() { return fromjson( "{a:{$in:[1,2,3]}}" ); }
-                BSONObj index() { return BSON( "a" << 1 << "b" << 1 << "c" << 1 ); }
-                int singleIntervalLimit() { return 1; }
-                void check() {
-                    assertAdvanceToNext( BSON( "a" << 1 << "b" << 1 << "c" << 1 ) );
-                    assertAdvanceTo( BSON( "a" << 1 << "b" << 1 << "c" << 1 ),
-                                     BSON( "a" << 2 << "b" << minElt() << "c" << minElt() ) );
-                    assertAdvanceTo( BSON( "a" << 2.5 << "b" << 1 << "c" << 2 ),
-                                     BSON( "a" << 3 << "b" << minElt() << "c" << minElt() ) );
-                    assertDoneAdvancing( BSON( "a" << 4 << "b" << 1 << "c" << 1 ) );
-                }
-            };
-            
-        } // namespace SameRangeLimit
-        
-    } // namespace FieldRangeVectorIteratorTests
-    
-    class All : public Suite {
-    public:
-        All() : Suite( "queryutil" ) {}
-
-        void setupTests() {
-            add<FieldIntervalTests::ToString>();
-            add<FieldRangeTests::ToString>();
-            add<FieldRangeTests::EmptyQuery>();
-            add<FieldRangeTests::Eq>();
-            add<FieldRangeTests::DupEq>();
-            add<FieldRangeTests::Lt>();
-            add<FieldRangeTests::Lte>();
-            add<FieldRangeTests::LtDate>();
-            add<FieldRangeTests::Gt>();
-            add<FieldRangeTests::Gte>();
-            add<FieldRangeTests::GtString>();
-            add<FieldRangeTests::TwoLt>();
-            add<FieldRangeTests::TwoGt>();
-            add<FieldRangeTests::EqGte>();
-            add<FieldRangeTests::EqGteInvalid>();
-            add<FieldRangeTests::Regex>();
-            add<FieldRangeTests::RegexObj>();
-            add<FieldRangeTests::UnhelpfulRegex>();
-            add<FieldRangeTests::In>();
-            add<FieldRangeTests::And>();
-            add<FieldRangeTests::SingletonOr>();
-            add<FieldRangeTests::NestedSingletonOr>();
-            add<FieldRangeTests::NonSingletonOr>();
-            add<FieldRangeTests::Empty>();
-            add<FieldRangeTests::Equality>();
-            add<FieldRangeTests::NoWhere>();
-            add<FieldRangeTests::Numeric>();
-            add<FieldRangeTests::InLowerBound>();
-            add<FieldRangeTests::InUpperBound>();
-            add<FieldRangeTests::BoundUnion>();
-            add<FieldRangeTests::BoundUnionFullyContained>();
-            add<FieldRangeTests::BoundUnionOverlapWithInclusivity>();
-            add<FieldRangeTests::BoundUnionEmpty>();
-            add<FieldRangeTests::MultiBound>();
-            add<FieldRangeTests::Diff1>();
-            add<FieldRangeTests::Diff2>();
-            add<FieldRangeTests::Diff3>();
-            add<FieldRangeTests::Diff4>();
-            add<FieldRangeTests::Diff5>();
-            add<FieldRangeTests::Diff6>();
-            add<FieldRangeTests::Diff7>();
-            add<FieldRangeTests::Diff8>();
-            add<FieldRangeTests::Diff9>();
-            add<FieldRangeTests::Diff10>();
-            add<FieldRangeTests::Diff11>();
-            add<FieldRangeTests::Diff12>();
-            add<FieldRangeTests::Diff13>();
-            add<FieldRangeTests::Diff14>();
-            add<FieldRangeTests::Diff15>();
-            add<FieldRangeTests::Diff16>();
-            add<FieldRangeTests::Diff17>();
-            add<FieldRangeTests::Diff18>();
-            add<FieldRangeTests::Diff19>();
-            add<FieldRangeTests::Diff20>();
-            add<FieldRangeTests::Diff21>();
-            add<FieldRangeTests::Diff22>();
-            add<FieldRangeTests::Diff23>();
-            add<FieldRangeTests::Diff24>();
-            add<FieldRangeTests::Diff25>();
-            add<FieldRangeTests::Diff26>();
-            add<FieldRangeTests::Diff27>();
-            add<FieldRangeTests::Diff28>();
-            add<FieldRangeTests::Diff29>();
-            add<FieldRangeTests::Diff30>();
-            add<FieldRangeTests::Diff31>();
-            add<FieldRangeTests::Diff32>();
-            add<FieldRangeTests::Diff33>();
-            add<FieldRangeTests::Diff34>();
-            add<FieldRangeTests::Diff35>();
-            add<FieldRangeTests::Diff36>();
-            add<FieldRangeTests::Diff37>();
-            add<FieldRangeTests::Diff38>();
-            add<FieldRangeTests::Diff39>();
-            add<FieldRangeTests::Diff40>();
-            add<FieldRangeTests::Diff41>();
-            add<FieldRangeTests::Diff42>();
-            add<FieldRangeTests::Diff43>();
-            add<FieldRangeTests::Diff44>();
-            add<FieldRangeTests::Diff45>();
-            add<FieldRangeTests::Diff46>();
-            add<FieldRangeTests::Diff47>();
-            add<FieldRangeTests::Diff48>();
-            add<FieldRangeTests::Diff49>();
-            add<FieldRangeTests::Diff50>();
-            add<FieldRangeTests::Diff51>();
-            add<FieldRangeTests::Diff52>();
-            add<FieldRangeTests::Diff53>();
-            add<FieldRangeTests::Diff54>();
-            add<FieldRangeTests::Diff55>();
-            add<FieldRangeTests::Diff56>();
-            add<FieldRangeTests::Diff57>();
-            add<FieldRangeTests::Diff58>();
-            add<FieldRangeTests::Diff59>();
-            add<FieldRangeTests::Diff60>();
-            add<FieldRangeTests::Diff61>();
-            add<FieldRangeTests::Diff62>();
-            add<FieldRangeTests::Diff63>();
-            add<FieldRangeTests::Diff64>();
-            add<FieldRangeTests::DiffMulti1>();
-            add<FieldRangeTests::DiffMulti2>();
-            add<FieldRangeTests::Universal>();
-            add<FieldRangeTests::ElemMatchRegex>();
-            add<FieldRangeTests::PreserveNonUniversalElemMatchContext>();
-            add<FieldRangeTests::IntersectSpecial>();
-            add<FieldRangeTests::ExactMatchRepresentation::EqualArray>();
-            add<FieldRangeTests::ExactMatchRepresentation::EqualEmptyArray>();
-            add<FieldRangeTests::ExactMatchRepresentation::EqualNull>();
-            add<FieldRangeTests::ExactMatchRepresentation::InArray>();
-            add<FieldRangeTests::ExactMatchRepresentation::InRegex>();
-            add<FieldRangeTests::ExactMatchRepresentation::InNull>();
-            add<FieldRangeTests::ExactMatchRepresentation::Exists>();
-            add<FieldRangeTests::ExactMatchRepresentation::UntypedRegex>();
-            add<FieldRangeTests::ExactMatchRepresentation::UntypedRegexString>();
-            add<FieldRangeTests::ExactMatchRepresentation::NotIn>();
-            add<FieldRangeTests::ExactMatchRepresentation::NotGt>();
-            add<FieldRangeTests::ExactMatchRepresentation::GtArray>();
-            add<FieldRangeTests::ExactMatchRepresentation::GtNull>();
-            add<FieldRangeTests::ExactMatchRepresentation::LtObject>();
-            add<FieldRangeTests::ExactMatchRepresentation::NotNe>();
-            add<FieldRangeTests::ExactMatchRepresentation::MultikeyIntersection>();
-            add<FieldRangeTests::ExactMatchRepresentation::Intersection>();
-            add<FieldRangeTests::ExactMatchRepresentation::Union>();
-            add<FieldRangeTests::ExactMatchRepresentation::Difference>();
-            add<FieldRangeSetTests::Basics>();
-            add<FieldRangeSetTests::Intersect>();
-            add<FieldRangeSetTests::MultiKeyIntersect>();
-            add<FieldRangeSetTests::EmptyMultiKeyIntersect>();
-            add<FieldRangeSetTests::MultiKeyDiff>();
-            add<FieldRangeSetTests::MatchPossible>();
-            add<FieldRangeSetTests::MatchPossibleForIndex>();
-            add<FieldRangeSetTests::Subset>();
-            add<FieldRangeSetTests::Prefixed>();
-            add<FieldRangeSetTests::Atomic>();
-            add<FieldRangeSetTests::ElemMatch::Ranges>();
-            add<FieldRangeSetTests::ElemMatch::TopLevelElements>();
-            add<FieldRangeSetTests::ElemMatch::TopLevelNotElement>();
-            add<FieldRangeSetTests::ElemMatch::TopLevelNested>();
-            add<FieldRangeSetTests::ElemMatch::Not>();
-            add<FieldRangeSetTests::ElemMatch::Nested>();
-            add<FieldRangeSetTests::ElemMatch::AllNested>();
-            add<FieldRangeSetTests::ExactMatchRepresentation::EmptyQuery>();
-            add<FieldRangeSetTests::ExactMatchRepresentation::Equal>();
-            add<FieldRangeSetTests::ExactMatchRepresentation::In>();
-            add<FieldRangeSetTests::ExactMatchRepresentation::Where>();
-            add<FieldRangeSetTests::ExactMatchRepresentation::Not>();
-            add<FieldRangeSetTests::ExactMatchRepresentation::Regex>();
-            add<FieldRangeSetTests::ExactMatchRepresentation::UntypedRegex>();
-            add<FieldRangeSetTests::ExactMatchRepresentation::UntypedRegexString>();
-            add<FieldRangeSetTests::ExactMatchRepresentation::And>();
-            add<FieldRangeSetTests::ExactMatchRepresentation::Or>();
-            add<FieldRangeSetTests::ExactMatchRepresentation::All>();
-            add<FieldRangeSetTests::ExactMatchRepresentation::ElemMatch>();
-            add<FieldRangeSetTests::ExactMatchRepresentation::AllElemMatch>();
-            add<FieldRangeSetTests::ExactMatchRepresentation::NotSecondField>();
-            add<FieldRangeSetPairTests::ToString>();
-            add<FieldRangeSetPairTests::NoNonUniversalRanges>();
-            add<FieldRangeSetPairTests::MatchPossible>();
-            add<FieldRangeVectorTests::ToString>();
-            add<FieldRangeVectorTests::HasAllIndexedRanges>();
-            add<FieldRangeVectorTests::SingleInterval>();
-            add<FieldRangeVectorTests::StartEndKey>();
-            add<FieldRangeVectorIteratorTests::AdvanceToNextIntervalEquality>();
-            add<FieldRangeVectorIteratorTests::AdvanceToNextIntervalExclusiveInequality>();
-            add<FieldRangeVectorIteratorTests::AdvanceToNextIntervalEqualityReverse>();
-            add<FieldRangeVectorIteratorTests::AdvanceToNextIntervalEqualityCompound>();
-            add<FieldRangeVectorIteratorTests::AdvanceToNextIntervalIntermediateEqualityCompound>();
-            add<FieldRangeVectorIteratorTests::AdvanceToNextIntervalIntermediateInMixed>();
-            add<FieldRangeVectorIteratorTests::BeforeLowerBound>();
-            add<FieldRangeVectorIteratorTests::BeforeLowerBoundMixed>();
-            add<FieldRangeVectorIteratorTests::AdvanceToNextExclusiveIntervalCompound>();
-            add<FieldRangeVectorIteratorTests::AdvanceRange>();
-            add<FieldRangeVectorIteratorTests::AdvanceInRange>();
-            add<FieldRangeVectorIteratorTests::AdvanceRangeIn>();
-            add<FieldRangeVectorIteratorTests::AdvanceRangeRange>();
-            add<FieldRangeVectorIteratorTests::AdvanceRangeRangeMultiple>();
-            add<FieldRangeVectorIteratorTests::AdvanceRangeRangeIn>();
-            add<FieldRangeVectorIteratorTests::AdvanceRangeMixed>();
-            add<FieldRangeVectorIteratorTests::AdvanceRangeMixed2>();
-            add<FieldRangeVectorIteratorTests::AdvanceRangeMixedIn>();
-            add<FieldRangeVectorIteratorTests::AdvanceRangeMixedMixed>();
-            add<FieldRangeVectorIteratorTests::AdvanceMixedMixedIn>();
-            add<FieldRangeVectorIteratorTests::CompoundRangeCounter::RangeTracking>();
-            add<FieldRangeVectorIteratorTests::CompoundRangeCounter::SingleIntervalCount>();
-            add<FieldRangeVectorIteratorTests::CompoundRangeCounter::Set>();
-            add<FieldRangeVectorIteratorTests::CompoundRangeCounter::Inc>();
-            add<FieldRangeVectorIteratorTests::CompoundRangeCounter::SetZeroes>();
-            add<FieldRangeVectorIteratorTests::CompoundRangeCounter::SetUnknowns>();
-            add<FieldRangeVectorIteratorTests::FieldIntervalMatcher::IsEqInclusiveUpperBound>();
-            add<FieldRangeVectorIteratorTests::FieldIntervalMatcher::IsGteUpperBound>();
-            add<FieldRangeVectorIteratorTests::FieldIntervalMatcher::IsEqExclusiveLowerBound>();
-            add<FieldRangeVectorIteratorTests::FieldIntervalMatcher::IsLtLowerBound>();
-            add<FieldRangeVectorIteratorTests::FieldIntervalMatcher::CheckLowerAfterUpper>();
-            add<FieldRangeVectorIteratorTests::SingleIntervalLimit::NoLimit>();
-            add<FieldRangeVectorIteratorTests::SingleIntervalLimit::OneIntervalLimit>();
-            add<FieldRangeVectorIteratorTests::SingleIntervalLimit::TwoIntervalLimit>();
-            add<FieldRangeVectorIteratorTests::SingleIntervalLimit::ThreeIntervalLimitUnreached>();
-            add<FieldRangeVectorIteratorTests::SingleIntervalLimit::
-                    FirstIntervalExhaustedBeforeLimit>();
-            add<FieldRangeVectorIteratorTests::SingleIntervalLimit::
-                    FirstIntervalNotExhaustedAtLimit>();
-            add<FieldRangeVectorIteratorTests::SingleIntervalLimit::EqualIn>();
-            add<FieldRangeVectorIteratorTests::SingleIntervalLimit::TwoIntervalIntermediateValue>();
-            add<FieldRangeVectorIteratorTests::SingleIntervalLimit::InGte>();
-            add<FieldRangeVectorIteratorTests::SingleIntervalLimit::InEmptyGte>();
-            add<FieldRangeVectorIteratorTests::SingleIntervalLimit::InGt>();
-            add<FieldRangeVectorIteratorTests::SingleIntervalLimit::InEmptyGt>();
-            add<FieldRangeVectorIteratorTests::SingleIntervalLimit::InLt>();
-            add<FieldRangeVectorIteratorTests::SingleIntervalLimit::InGteLt>();
-            add<FieldRangeVectorIteratorTests::SingleIntervalLimit::InGtHigherLimit>();
-            add<FieldRangeVectorIteratorTests::SingleIntervalLimit::TwoRange>();
-            add<FieldRangeVectorIteratorTests::SingleIntervalLimit::IndexPrefix>();
-            add<FieldRangeVectorIteratorTests::SingleIntervalLimit::IndexPrefixReverseOrder>();
-            add<FieldRangeVectorIteratorTests::SingleIntervalLimit::LongerIndexPrefix>();
-        }
-    } myall;
-
-} // namespace QueryUtilTests
-
diff --git a/src/mongo/dbtests/repltests.cpp b/src/mongo/dbtests/repltests.cpp
index 64ef01e091a..ed67adaf6b0 100644
--- a/src/mongo/dbtests/repltests.cpp
+++ b/src/mongo/dbtests/repltests.cpp
@@ -36,7 +36,6 @@
 #include "mongo/db/db.h"
 #include "mongo/db/instance.h"
 #include "mongo/db/json.h"
-#include "mongo/db/queryutil.h"
 #include "mongo/db/repl/master_slave.h"
 #include "mongo/db/repl/oplog.h"
 #include "mongo/db/repl/repl_settings.h"
diff --git a/src/mongo/s/chunk.cpp b/src/mongo/s/chunk.cpp
index f030ef09ed6..33b85814617 100644
--- a/src/mongo/s/chunk.cpp
+++ b/src/mongo/s/chunk.cpp
@@ -35,7 +35,6 @@
 #include "mongo/client/connpool.h"
 #include "mongo/client/dbclientcursor.h"
 #include "mongo/db/query/lite_parsed_query.h"
-#include "mongo/db/queryutil.h"
 #include "mongo/db/write_concern.h"
 #include "mongo/platform/random.h"
 #include "mongo/s/chunk_diff.h"
diff --git a/src/mongo/s/commands_public.cpp b/src/mongo/s/commands_public.cpp
index c48000caacd..caed4bb8f82 100644
--- a/src/mongo/s/commands_public.cpp
+++ b/src/mongo/s/commands_public.cpp
@@ -50,7 +50,6 @@
 #include "mongo/db/pipeline/document_source.h"
 #include "mongo/db/pipeline/expression_context.h"
 #include "mongo/db/query/lite_parsed_query.h"
-#include "mongo/db/queryutil.h"
 #include "mongo/s/client_info.h"
 #include "mongo/s/chunk.h"
 #include "mongo/s/config.h"
@@ -844,6 +843,30 @@ namespace mongo {
                 actions.addAction(ActionType::find);
                 out->push_back(Privilege(parseResourcePattern(dbname, cmdObj), actions));
             }
+            long long applySkipLimit( long long num , const BSONObj& cmd ) {
+                BSONElement s = cmd["skip"];
+                BSONElement l = cmd["limit"];
+
+                if ( s.isNumber() ) {
+                    num = num - s.numberLong();
+                    if ( num < 0 ) {
+                        num = 0;
+                    }
+                }
+
+                if ( l.isNumber() ) {
+                    long long limit = l.numberLong();
+                    if( limit < 0 ){
+                        limit = -limit;
+                    }
+
+                    if ( limit < num && limit != 0 ) { // 0 limit means no limit
+                        num = limit;
+                    }
+                }
+
+                return num;
+            }
             bool run( const string& dbName,
                     BSONObj& cmdObj,
                     int options,
diff --git a/src/mongo/s/shardkey.h b/src/mongo/s/shardkey.h
index aa63fe9ec3c..8dec3e65b27 100644
--- a/src/mongo/s/shardkey.h
+++ b/src/mongo/s/shardkey.h
@@ -139,18 +139,6 @@ namespace mongo {
          */
         BSONObj moveToFront(const BSONObj& obj) const;
 
-        /**@param queryConstraints a FieldRangeSet formed from parsing a query
-         * @return an ordered list of bounds generated using this KeyPattern
-         * and the constraints from the FieldRangeSet
-         *
-         * The value of frsp->matchPossibleForSingleKeyFRS(fromQuery) should be true,
-         * otherwise this function could throw.
-         *
-         */
-        BoundList keyBounds( const FieldRangeSet& queryConstraints ) const{
-            return pattern.keyBounds( queryConstraints );
-        }
-
     private:
         KeyPattern pattern;
         BSONObj gMin;