SERVER-13656 Use new query framework in getShardsForQuery on mongos

9 files changed, 932 insertions, 41 deletions

diff --git a/src/mongo/SConscript b/src/mongo/SConscript
index 57c87437ee0..81a47c0978a 100644
--- a/src/mongo/SConscript
+++ b/src/mongo/SConscript
@@ -745,6 +745,7 @@ mongosLibraryFiles = [
     "s/version_manager.cpp",
     "s/version_mongos.cpp",
     "s/mongos_persistence_stubs.cpp",
+    "s/expression_where_noop.cpp",
     ]
 
 env.Library( "mongoscore",
diff --git a/src/mongo/db/keypattern.cpp b/src/mongo/db/keypattern.cpp
index c2a1f18cba2..ecd44b448c4 100644
--- a/src/mongo/db/keypattern.cpp
+++ b/src/mongo/db/keypattern.cpp
@@ -217,6 +217,97 @@ namespace mongo {
         return ret;
     }
 
+    BoundList KeyPattern::keyBounds( const BSONObj& keyPattern, const IndexBounds& indexBounds ) {
+        invariant(indexBounds.fields.size() == (size_t)keyPattern.nFields());
+
+        // If any field is unsatisfied, return empty bound list.
+        for (vector<OrderedIntervalList>::const_iterator it = indexBounds.fields.begin();
+                it != indexBounds.fields.end(); it++) {
+            if (it->intervals.size() == 0) {
+                return BoundList();
+            }
+        }
+        // To construct our bounds we will generate intervals based on bounds 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 keyIter( keyPattern );
+        // until equalityOnly is false, we are just dealing with equality (no range or $in queries).
+        bool equalityOnly = true;
+
+        for (size_t i = 0; i < indexBounds.fields.size(); i++) {
+            BSONElement e = keyIter.next();
+
+            StringData fieldName = e.fieldNameStringData();
+
+            // 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 OrderedIntervalList& oil = indexBounds.fields[i];
+            const vector<Interval>& intervals = oil.intervals;
+
+            if ( equalityOnly ) {
+                if ( intervals.size() == 1 && intervals.front().isPoint() ){
+                    // this field is only a single point-interval
+                    BoundBuilders::const_iterator j;
+                    for( j = builders.begin(); j != builders.end(); ++j ) {
+                        j->first->appendAs( intervals.front().start, fieldName );
+                        j->second->appendAs( intervals.front().end, fieldName );
+                    }
+                }
+                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;
+
+                    for(BoundBuilders::const_iterator it = builders.begin(); it != builders.end(); ++it ) {
+                        BSONObj first = it->first->obj();
+                        BSONObj second = it->second->obj();
+
+                        for ( vector<Interval>::const_iterator interval = intervals.begin();
+                                interval != intervals.end(); ++interval )
+                        {
+                            uassert( 17439,
+                                     "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->appendAs( interval->start, fieldName );
+                            newBuilders.back().second->appendAs( interval->end, fieldName );
+                        }
+                    }
+                    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->appendAs( intervals.front().start, fieldName );
+                    j->second->appendAs( intervals.back().end, fieldName );
+                }
+            }
+        }
+        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::_transformFieldBounds( const vector<FieldInterval>& oldIntervals ,
                                                  const BSONElement& field  ) const {
 
diff --git a/src/mongo/db/keypattern.h b/src/mongo/db/keypattern.h
index b5ba777cecd..3e99a1c9d85 100644
--- a/src/mongo/db/keypattern.h
+++ b/src/mongo/db/keypattern.h
@@ -34,6 +34,7 @@
 #include "mongo/db/jsobj.h"
 #include "mongo/platform/unordered_set.h"
 #include "mongo/util/mongoutils/str.h"
+#include "mongo/db/query/index_bounds.h"
 
 namespace mongo {
 
@@ -173,6 +174,31 @@ namespace mongo {
          */
         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
+         * determine where to route queries according to the shard key pattern.
+         *
+         * Examples:
+         *
+         * Key { a: 1 }, Bounds a: [0] => { a: 0 } -> { a: 0 }
+         * Key { a: 1 }, Bounds a: [2, 3) => { a: 2 } -> { a: 3 }  // bound inclusion ignored.
+         *
+         * The bounds returned by this function may be a superset of those defined
+         * by the constraints.  For instance, if this KeyPattern is {a : 1, b: 1}
+         * Bounds: { a : {$in : [1,2]} , b : {$in : [3,4,5]} }
+         *         => {a : 1 , b : 3} -> {a : 1 , b : 5}, {a : 2 , b : 3} -> {a : 2 , b : 5}
+         *
+         * If the IndexBounds are not defined for all the fields in this keypattern, which
+         * means some fields are unsatisfied, an empty BoundList could return.
+         *
+         */
+        static BoundList keyBounds( const BSONObj& keyPattern, const IndexBounds& indexBounds );
+
+        static bool isHashed( const BSONElement& fieldExpression ) {
+            return mongoutils::str::equals( fieldExpression.valuestrsafe() , "hashed" );
+        }
+
     private:
         BSONObj _pattern;
 
@@ -202,10 +228,6 @@ namespace mongo {
             return ( fieldExpression.isNumber()  && fieldExpression.numberInt() == -1 );
         }
 
-        bool isHashed( const BSONElement& fieldExpression ) const {
-            return mongoutils::str::equals( fieldExpression.valuestrsafe() , "hashed" );
-        }
-
         /* 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'
diff --git a/src/mongo/db/matcher/expression_where.cpp b/src/mongo/db/matcher/expression_where.cpp
index 8f02a748467..8486155a6e9 100644
--- a/src/mongo/db/matcher/expression_where.cpp
+++ b/src/mongo/db/matcher/expression_where.cpp
@@ -192,6 +192,7 @@ namespace mongo {
     }
 
     MONGO_INITIALIZER( MatchExpressionWhere )( ::mongo::InitializerContext* context ) {
+        // This could be overrided by MatchExpressionWhereNoOp in mongos
         expressionParserWhereCallback = expressionParserWhereCallbackReal;
         return Status::OK();
     }
diff --git a/src/mongo/s/SConscript b/src/mongo/s/SConscript
index f5c0a14492a..2c15f24a1e2 100644
--- a/src/mongo/s/SConscript
+++ b/src/mongo/s/SConscript
@@ -330,5 +330,17 @@ env.Library(
     ],
 )
 
-
+env.CppUnitTest(
+    target='chunk_manager_targeter_test',
+    source=[
+        'chunk_manager_targeter_test.cpp',
+    ],
+    LIBDEPS=[
+        '$BUILD_DIR/mongo/coredb',
+        '$BUILD_DIR/mongo/coreserver',
+        '$BUILD_DIR/mongo/coreshard',
+        '$BUILD_DIR/mongo/mongocommon',
+        '$BUILD_DIR/mongo/mongoscore',
+    ]
+)
 
diff --git a/src/mongo/s/chunk.cpp b/src/mongo/s/chunk.cpp
index 8625f501943..f030ef09ed6 100644
--- a/src/mongo/s/chunk.cpp
+++ b/src/mongo/s/chunk.cpp
@@ -52,6 +52,10 @@
 #include "mongo/util/concurrency/ticketholder.h"
 #include "mongo/util/startup_test.h"
 #include "mongo/util/timer.h"
+#include "mongo/db/query/canonical_query.h"
+#include "mongo/db/query/query_planner.h"
+#include "mongo/db/query/query_planner_common.h"
+#include "mongo/db/query/index_bounds_builder.h"
 
 namespace mongo {
 
@@ -1156,49 +1160,39 @@ namespace mongo {
     }
 
     void ChunkManager::getShardsForQuery( set<Shard>& shards , const BSONObj& query ) const {
-        // TODO Determine if the third argument to OrRangeGenerator() is necessary, see SERVER-5165.
-        OrRangeGenerator org(_ns.c_str(), query, false);
-
-        const SpecialIndices special = org.getSpecial();
-        if (special.has("2d") || special.has("2dsphere")) {
-            BSONForEach(field, query) {
-                if (getGtLtOp(field) == BSONObj::opNEAR) {
-                    uassert(13501, "use geoNear command rather than $near query", false);
-                    // TODO: convert to geoNear rather than erroring out
-                }
-                // $within queries are fine
-            }
-        } else if (!special.empty()) {
-            uassert(13502, "unrecognized special query type: " + special.toString(), false);
-        }
+        CanonicalQuery* canonicalQuery;
+        Status status = CanonicalQuery::canonicalize(_ns, query, &canonicalQuery);
+        uassert(status.code(), status.reason(), status.isOK());
 
-        do {
-            boost::scoped_ptr<FieldRangeSetPair> frsp (org.topFrsp());
+        boost::scoped_ptr<CanonicalQuery> canonicalQueryPtr(canonicalQuery);
 
-            // special case if most-significant field isn't in query
-            FieldRange range = frsp->shardKeyRange(_key.key().firstElementFieldName());
-            if ( range.universal() ) {
-                getShardsForRange( shards, _key.globalMin(), _key.globalMax() );
-                return;
-            }
-            
-            if ( frsp->matchPossibleForSingleKeyFRS( _key.key() ) ) {
-                BoundList ranges = _key.keyBounds( frsp->getSingleKeyFRS() );
-                for ( BoundList::const_iterator it=ranges.begin(); it != ranges.end(); ++it ){
+        // Query validation
+        if (QueryPlannerCommon::hasNode(canonicalQuery->root(), MatchExpression::GEO_NEAR)) {
+            uassert(13501, "use geoNear command rather than $near query", false);
+        }
 
-                    getShardsForRange( shards, it->first /*min*/, it->second /*max*/ );
+        // Transforms query into bounds for each field in the shard key
+        // for example :
+        //   Key { a: 1, b: 1 },
+        //   Query { a : { $gte : 1, $lt : 2 },
+        //            b : { $gte : 3, $lt : 4 } }
+        //   => Bounds { a : [1, 2), b : [3, 4) }
+        IndexBounds bounds = getIndexBoundsForQuery(_key.key(), canonicalQuery);
 
-                    // once we know we need to visit all shards no need to keep looping
-                    if( shards.size() == _shards.size() ) return;
-                }
-            }
+        // Transforms bounds for each shard key field into full shard key ranges
+        // for example :
+        //   Key { a : 1, b : 1 }
+        //   Bounds { a : [1, 2), b : [3, 4) }
+        //   => Ranges { a : 1, b : 3 } => { a : 2, b : 4 }
+        BoundList ranges = KeyPattern::keyBounds(_key.key(), bounds);
 
-            if (!org.orRangesExhausted())
-                org.popOrClauseSingleKey();
+        for ( BoundList::const_iterator it=ranges.begin(); it != ranges.end(); ++it ){
+            getShardsForRange( shards, it->first /*min*/, it->second /*max*/ );
 
+            // once we know we need to visit all shards no need to keep looping
+            if( shards.size() == _shards.size() ) break;
         }
-        while (!org.orRangesExhausted());
-        
+
         // SERVER-4914 Some clients of getShardsForQuery() assume at least one shard will be
         // returned.  For now, we satisfy that assumption by adding a shard with no matches rather
         // than return an empty set of shards.
@@ -1231,6 +1225,106 @@ namespace mongo {
         all.insert(_shards.begin(), _shards.end());
     }
 
+    IndexBounds ChunkManager::getIndexBoundsForQuery(const BSONObj& key, const CanonicalQuery* canonicalQuery) {
+        // $text is not allowed in planning since we don't have text index on mongos.
+        //
+        // TODO: Treat $text query as a no-op in planning. So with shard key {a: 1},
+        //       the query { a: 2, $text: { ... } } will only target to {a: 2}.
+        if (QueryPlannerCommon::hasNode(canonicalQuery->root(), MatchExpression::TEXT)) {
+            IndexBounds bounds;
+            IndexBoundsBuilder::allValuesBounds(key, &bounds); // [minKey, maxKey]
+            return bounds;
+        }
+
+        // Consider shard key as an index
+        string accessMethod = IndexNames::BTREE;
+        if (KeyPattern::isHashed(key.firstElement())) {
+            accessMethod = IndexNames::HASHED;
+        }
+
+        // Use query framework to generate index bounds
+        QueryPlannerParams plannerParams;
+        // Must use "shard key" index
+        plannerParams.options = QueryPlannerParams::NO_TABLE_SCAN;
+        IndexEntry indexEntry(key, accessMethod, false /* multiKey */, false /* sparse */, "shardkey", BSONObj());
+        plannerParams.indices.push_back(indexEntry);
+
+        vector<QuerySolution*> solutions;
+        Status status = QueryPlanner::plan(*canonicalQuery, plannerParams, &solutions);
+        uassert(status.code(), status.reason(), status.isOK());
+
+        IndexBounds bounds;
+
+        for (vector<QuerySolution*>::const_iterator it = solutions.begin();
+                bounds.size() == 0 && it != solutions.end(); it++) {
+            // Try next solution if we failed to generate index bounds, i.e. bounds.size() == 0
+            bounds = collapseQuerySolution((*it)->root.get());
+        }
+
+        if (bounds.size() == 0) {
+            // We cannot plan the query without collection scan, so target to all shards.
+            IndexBoundsBuilder::allValuesBounds(key, &bounds); // [minKey, maxKey]
+        }
+        return bounds;
+    }
+
+    IndexBounds ChunkManager::collapseQuerySolution( const QuerySolutionNode* node ) {
+        if (node->children.size() == 0) {
+            invariant(node->getType() == STAGE_IXSCAN);
+
+            const IndexScanNode* ixNode = static_cast<const IndexScanNode*>( node );
+            return ixNode->bounds;
+        }
+
+        if (node->children.size() == 1) {
+            // e.g. FETCH -> IXSCAN
+            return collapseQuerySolution( node->children.front() );
+        }
+
+        // children.size() > 1, assert it's OR / SORT_MERGE.
+        if ( node->getType() != STAGE_OR && node->getType() != STAGE_SORT_MERGE ) {
+            // Unexpected node. We should never reach here.
+            error() << "could not generate index bounds on query solution tree: " << node->toString();
+            dassert(false); // We'd like to know this error in testing.
+
+            // Bail out with all shards in production, since this isn't a fatal error.
+            return IndexBounds();
+        }
+
+        IndexBounds bounds;
+        for ( vector<QuerySolutionNode*>::const_iterator it = node->children.begin();
+                it != node->children.end(); it++ )
+        {
+            // The first branch under OR
+            if ( it == node->children.begin() ) {
+                invariant(bounds.size() == 0);
+                bounds = collapseQuerySolution( *it );
+                if (bounds.size() == 0) { // Got unexpected node in query solution tree
+                    return IndexBounds();
+                }
+                continue;
+            }
+
+            IndexBounds childBounds = collapseQuerySolution( *it );
+            if (childBounds.size() == 0) { // Got unexpected node in query solution tree
+                return IndexBounds();
+            }
+
+            invariant(childBounds.size() == bounds.size());
+            for ( size_t i = 0; i < bounds.size(); i++ ) {
+                bounds.fields[i].intervals.insert( bounds.fields[i].intervals.end(),
+                                                   childBounds.fields[i].intervals.begin(),
+                                                   childBounds.fields[i].intervals.end() );
+            }
+        }
+
+        for ( size_t i = 0; i < bounds.size(); i++ ) {
+            IndexBoundsBuilder::unionize( &bounds.fields[i] );
+        }
+
+        return bounds;
+    }
+
     bool ChunkManager::compatibleWith( const ChunkManager& other, const Shard& shard ) const {
         // Return true if the shard version is the same in the two chunk managers
         // TODO: This doesn't need to be so strong, just major vs
diff --git a/src/mongo/s/chunk.h b/src/mongo/s/chunk.h
index b02b9140883..a9b1422ada6 100644
--- a/src/mongo/s/chunk.h
+++ b/src/mongo/s/chunk.h
@@ -37,6 +37,7 @@
 #include "mongo/s/shard.h"
 #include "mongo/s/shardkey.h"
 #include "mongo/util/concurrency/ticketholder.h"
+#include "mongo/db/query/query_solution.h"
 
 namespace mongo {
 
@@ -438,6 +439,24 @@ namespace mongo {
         /** @param shards set to the shards covered by the interval [min, max], see SERVER-4791 */
         void getShardsForRange( set<Shard>& shards, const BSONObj& min, const BSONObj& max ) const;
 
+        // Transforms query into bounds for each field in the shard key
+        // for example :
+        //   Key { a: 1, b: 1 },
+        //   Query { a : { $gte : 1, $lt : 2 },
+        //            b : { $gte : 3, $lt : 4 } }
+        //   => Bounds { a : [1, 2), b : [3, 4) }
+        static IndexBounds getIndexBoundsForQuery(const BSONObj& key, const CanonicalQuery* canonicalQuery);
+
+        // Collapse query solution tree.
+        //
+        // If it has OR node, the result could be a superset of the index bounds generated.
+        // Since to give a single IndexBounds, this gives the union of bounds on each field.
+        // for example:
+        //   OR: { a: (0, 1), b: (0, 1) },
+        //       { a: (2, 3), b: (2, 3) }
+        //   =>  { a: (0, 1), (2, 3), b: (0, 1), (2, 3) }
+        static IndexBounds collapseQuerySolution( const QuerySolutionNode* node );
+
         ChunkMap getChunkMap() const { return _chunkMap; }
 
         /**
diff --git a/src/mongo/s/chunk_manager_targeter_test.cpp b/src/mongo/s/chunk_manager_targeter_test.cpp
new file mode 100644
index 00000000000..2084120861f
--- /dev/null
+++ b/src/mongo/s/chunk_manager_targeter_test.cpp
@@ -0,0 +1,521 @@
+/**
+ *    Copyright (C) 2014 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/db/json.h"
+#include "mongo/db/namespace_string.h"
+#include "mongo/db/query/interval.h"
+#include "mongo/s/chunk.h"
+#include "mongo/unittest/unittest.h"
+
+namespace {
+
+    using namespace mongo;
+
+    /**
+     * ChunkManager targeting test
+     *
+     * TODO:
+     *   Pull the implementation out of chunk.cpp
+     */
+
+    // Utility function to create a CanonicalQuery
+    CanonicalQuery* canonicalize(const char* queryStr) {
+        BSONObj queryObj = fromjson(queryStr);
+        CanonicalQuery* cq;
+        Status result = CanonicalQuery::canonicalize("test.foo", queryObj, &cq);
+        ASSERT_OK(result);
+        return cq;
+    }
+
+    void CheckIndexBoundsWithKey(const char* keyStr,
+                                 const char* queryStr,
+                                 const IndexBounds& expectedBounds) {
+
+        auto_ptr<CanonicalQuery> query(canonicalize(queryStr));
+        ASSERT(query.get() != NULL);
+
+        BSONObj key = fromjson(keyStr);
+
+        IndexBounds indexBounds = ChunkManager::getIndexBoundsForQuery(key, query.get());
+        ASSERT_EQUALS(indexBounds.size(), expectedBounds.size());
+        for (size_t i = 0; i < indexBounds.size(); i++) {
+            const OrderedIntervalList& oil = indexBounds.fields[i];
+            const OrderedIntervalList& expectedOil = expectedBounds.fields[i];
+            ASSERT_EQUALS(oil.intervals.size(), expectedOil.intervals.size());
+            for (size_t i = 0; i < oil.intervals.size(); i++) {
+                if (Interval::INTERVAL_EQUALS != oil.intervals[i].compare(expectedOil.intervals[i])) {
+                    log() << oil.intervals[i] << " != " << expectedOil.intervals[i];
+                }
+                ASSERT_EQUALS(Interval::INTERVAL_EQUALS, oil.intervals[i].compare(expectedOil.intervals[i]));
+            }
+        }
+    }
+
+    // Assume shard key is { a: 1 }
+    void CheckIndexBounds(const char* queryStr, const OrderedIntervalList& expectedOil) {
+        auto_ptr<CanonicalQuery> query(canonicalize(queryStr));
+        ASSERT(query.get() != NULL);
+
+        BSONObj key = fromjson("{a: 1}");
+
+        IndexBounds indexBounds = ChunkManager::getIndexBoundsForQuery(key, query.get());
+        ASSERT_EQUALS(indexBounds.size(), 1U);
+        const OrderedIntervalList& oil = indexBounds.fields.front();
+
+        if (oil.intervals.size() != expectedOil.intervals.size()) {
+            for (size_t i = 0; i < oil.intervals.size(); i++) {
+                log() << oil.intervals[i];
+            }
+        }
+
+        ASSERT_EQUALS(oil.intervals.size(), expectedOil.intervals.size());
+        for (size_t i = 0; i < oil.intervals.size(); i++) {
+            ASSERT_EQUALS(Interval::INTERVAL_EQUALS, oil.intervals[i].compare(expectedOil.intervals[i]));
+        }
+    }
+
+    const double INF = std::numeric_limits<double>::infinity();
+
+    // { a: 2 } -> a: [2, 2]
+    TEST(CMCollapseTreeTest, Basic) {
+        OrderedIntervalList expected;
+        expected.intervals.push_back(Interval(BSON("" << 2 << "" << 2), true, true));
+        CheckIndexBounds("{a: 2}", expected);
+    }
+
+    // { b: 2 } -> a: [MinKey, MaxKey]
+    TEST(CMCollapseTreeTest, AllValue) {
+        OrderedIntervalList expected;
+        BSONObjBuilder builder;
+        builder.appendMinKey("");
+        builder.appendMaxKey("");
+        expected.intervals.push_back(Interval(builder.obj(), true, true));
+        CheckIndexBounds("{b: 2}", expected);
+    }
+
+    // { 'a' : { '$not' : { '$gt' : 1 } } } -> a: [MinKey, 1.0], (inf.0, MaxKey]
+    TEST(CMCollapseTreeTest, NegativeGT) {
+        OrderedIntervalList expected;
+        {
+            BSONObjBuilder builder;
+            builder.appendMinKey("");
+            builder.appendNumber("", 1.0);
+            expected.intervals.push_back(Interval(builder.obj(), true, true));
+        }
+        {
+            BSONObjBuilder builder;
+            builder.append("", std::numeric_limits<double>::infinity());
+            builder.appendMaxKey("");
+            expected.intervals.push_back(Interval(builder.obj(), false, true));
+        }
+        CheckIndexBounds("{ 'a' : { '$not' : { '$gt' : 1 } } }", expected);
+    }
+
+    // {$or: [{a: 20}, {$and: [{a:1}, {b:7}]}]} -> a: [1.0, 1.0], [20.0, 20.0]
+    TEST(CMCollapseTreeTest, OrWithAndChild) {
+        OrderedIntervalList expected;
+        expected.intervals.push_back(Interval(BSON("" << 1.0 << "" << 1.0), true, true));
+        expected.intervals.push_back(Interval(BSON("" << 20.0 << "" << 20.0), true, true));
+        CheckIndexBounds("{$or: [{a: 20}, {$and: [{a:1}, {b:7}]}]}", expected);
+    }
+
+    // {a:20, $or: [{b:1}, {c:7}]} -> a: [20.0, 20.0]
+    TEST(CMCollapseTreeTest, AndWithUnindexedOrChild) {
+        // Logic rewrite could give a tree with root OR.
+        OrderedIntervalList expected;
+        expected.intervals.push_back(Interval(BSON("" << 20.0 << "" << 20.0), true, true));
+        CheckIndexBounds("{a:20, $or: [{b:1}, {c:7}]}", expected);
+    }
+
+    // {$or: [{a:{$gt:2,$lt:10}}, {a:{$gt:0,$lt:5}}]} -> a: (0.0, 10.0)
+    TEST(CMCollapseTreeTest, OrOfAnd) {
+        OrderedIntervalList expected;
+        expected.intervals.push_back(Interval(BSON("" << 0.0 << "" << 10.0), false, false));
+        CheckIndexBounds("{$or: [{a:{$gt:2,$lt:10}}, {a:{$gt:0,$lt:5}}]}", expected);
+    }
+
+    // {$or: [{a:{$gt:2,$lt:10}}, {a:{$gt:0,$lt:15}}, {a:{$gt:20}}]}
+    //   -> a: (0.0, 15.0), (20.0, inf.0]
+    TEST(CMCollapseTreeTest, OrOfAnd2) {
+        OrderedIntervalList expected;
+        expected.intervals.push_back(Interval(BSON("" << 0.0 << "" << 15.0), false, false));
+        expected.intervals.push_back(Interval(BSON("" << 20.0 << "" << INF), false, true));
+        CheckIndexBounds("{$or: [{a:{$gt:2,$lt:10}}, {a:{$gt:0,$lt:15}}, {a:{$gt:20}}]}", expected);
+    }
+
+    // "{$or: [{a:{$gt:1,$lt:5},b:6}, {a:3,b:{$gt:0,$lt:10}}]}" -> a: (1.0, 5.0)
+    TEST(CMCollapseTreeTest, OrOfAnd3) {
+        OrderedIntervalList expected;
+        expected.intervals.push_back(Interval(BSON("" << 1.0 << "" << 5.0), false, false));
+        CheckIndexBounds("{$or: [{a:{$gt:1,$lt:5},b:6}, {a:3,b:{$gt:0,$lt:10}}]}", expected);
+    }
+
+    //
+    //  Compound shard key
+    //
+
+    // "{$or: [{a:{$gt:1,$lt:5}, b:{$gt:0,$lt:3}, c:6}, "
+    //        "{a:3, b:{$gt:1,$lt:2}, c:{$gt:0,$lt:10}}]}",
+    // -> a: (1.0, 5.0), b: (0.0, 3.0)
+    TEST(CMCollapseTreeTest, OrOfAnd4) {
+        IndexBounds expectedBounds;
+        expectedBounds.fields.push_back(OrderedIntervalList());
+        expectedBounds.fields.push_back(OrderedIntervalList());
+
+        expectedBounds.fields[0].intervals.push_back(
+            Interval(BSON("" << 1.0 << "" << 5.0), false, false));
+        expectedBounds.fields[1].intervals.push_back(
+            Interval(BSON("" << 0.0 << "" << 3.0), false, false));
+
+        CheckIndexBoundsWithKey(
+            "{a: 1, b: 1}", // shard key
+            "{$or: [{a:{$gt:1,$lt:5}, b:{$gt:0,$lt:3}, c:6}, "
+                   "{a:3, b:{$gt:1,$lt:2}, c:{$gt:0,$lt:10}}]}",
+            expectedBounds);
+    }
+
+    // "{$or: [{a:{$gt:1,$lt:5}, c:6}, "
+    //        "{a:3, b:{$gt:1,$lt:2}, c:{$gt:0,$lt:10}}]}"));
+    // ->
+    TEST(CMCollapseTreeTest, OrOfAnd5) {
+        IndexBounds expectedBounds;
+        expectedBounds.fields.push_back(OrderedIntervalList());
+        expectedBounds.fields.push_back(OrderedIntervalList());
+
+        expectedBounds.fields[0].intervals.push_back(
+            Interval(BSON("" << 1.0 << "" << 5.0), false, false));
+        BSONObjBuilder builder;
+        builder.appendMinKey("");
+        builder.appendMaxKey("");
+        expectedBounds.fields[1].intervals.push_back(
+            Interval(builder.obj(), true, true));
+
+        CheckIndexBoundsWithKey(
+            "{a: 1, b: 1}", // shard key
+            "{$or: [{a:{$gt:1,$lt:5}, c:6}, "
+                   "{a:3, b:{$gt:1,$lt:2}, c:{$gt:0,$lt:10}}]}",
+            expectedBounds);
+    }
+
+    // {$or: [{a:{$in:[1]},b:{$in:[1]}}, {a:{$in:[1,5]},b:{$in:[1,5]}}]}
+    // -> a: [1], [5]; b: [1], [5]
+    TEST(CMCollapseTreeTest, OrOfAnd6) {
+        IndexBounds expectedBounds;
+        expectedBounds.fields.push_back(OrderedIntervalList());
+        expectedBounds.fields.push_back(OrderedIntervalList());
+
+        // a: [1], [5]
+        expectedBounds.fields[0].intervals.push_back(
+            Interval(BSON("" << 1.0 << "" << 1.0), true, true));
+        expectedBounds.fields[0].intervals.push_back(
+            Interval(BSON("" << 5.0 << "" << 5.0), true, true));
+
+        // b: [1], [5]
+        expectedBounds.fields[1].intervals.push_back(
+            Interval(BSON("" << 1.0 << "" << 1.0), true, true));
+        expectedBounds.fields[1].intervals.push_back(
+            Interval(BSON("" << 5.0 << "" << 5.0), true, true));
+
+        CheckIndexBoundsWithKey(
+            "{a: 1, b: 1}", // shard key
+            "{$or: [{a:{$in:[1]},b:{$in:[1]}}, {a:{$in:[1,5]},b:{$in:[1,5]}}]}",
+            expectedBounds);
+    }
+
+    //
+    // Array operators
+    //
+
+    // {a : {$elemMatch: {b:1}}} -> a.b: [MinKey, MaxKey]
+    // Shard key doesn't allow multikey, but query on array should succeed without error.
+    TEST(CMCollapseTreeTest, ElemMatchOneField) {
+        IndexBounds expectedBounds;
+        expectedBounds.fields.push_back(OrderedIntervalList());
+        OrderedIntervalList& oil = expectedBounds.fields.front();
+        oil.intervals.push_back(Interval(BSON("" << 1 << "" << 1), true, true));
+        CheckIndexBoundsWithKey("{'a.b': 1}", "{a : {$elemMatch: {b:1}}}", expectedBounds);
+    }
+
+    // {foo: {$all: [ {$elemMatch: {a:1, b:1}}, {$elemMatch: {a:2, b:2}}]}}
+    //    -> foo.a: [1, 1]
+    // Or -> foo.a: [2, 2]
+    TEST(CMCollapseTreeTest, BasicAllElemMatch) {
+        Interval expectedInterval1(BSON("" << 1 << "" << 1), true, true);
+        Interval expectedInterval2(BSON("" << 2 << "" << 2), true, true);
+
+        const char* queryStr = "{foo: {$all: [ {$elemMatch: {a:1, b:1}}, {$elemMatch: {a:2, b:2}}]}}";
+        auto_ptr<CanonicalQuery> query(canonicalize(queryStr));
+        ASSERT(query.get() != NULL);
+
+        BSONObj key = fromjson("{'foo.a': 1}");
+
+        IndexBounds indexBounds = ChunkManager::getIndexBoundsForQuery(key, query.get());
+        ASSERT_EQUALS(indexBounds.size(), 1U);
+        const OrderedIntervalList& oil = indexBounds.fields.front();
+        ASSERT_EQUALS(oil.intervals.size(), 1U);
+        const Interval& interval = oil.intervals.front();
+
+        // Choose one of the two possible solutions.
+        // Two solutions differ only by assignment of index tags.
+        ASSERT(Interval::INTERVAL_EQUALS == interval.compare(expectedInterval1)
+            || Interval::INTERVAL_EQUALS == interval.compare(expectedInterval2));
+    }
+
+    // {a : [1, 2, 3]} -> a: [1, 1], [[1, 2, 3], [1, 2, 3]]
+    TEST(CMCollapseTreeTest, ArrayEquality) {
+        OrderedIntervalList expected;
+        expected.intervals.push_back(Interval(BSON("" << 1 << "" << 1),  true, true));
+        BSONArray array(BSON_ARRAY(1 << 2 << 3));
+
+        Interval interval(BSON("" << array << "" << array),  true, true);
+        expected.intervals.push_back(interval);
+        CheckIndexBounds("{a : [1, 2, 3]}", expected);
+    }
+
+
+    //
+    //  Features: Regex, $where, $text, hashed key
+    //
+
+    // { a: /abc/ } -> a: ["", {}), [/abc/, /abc/]
+    TEST(CMCollapseTreeTest, Regex) {
+        OrderedIntervalList expected;
+        expected.intervals.push_back(
+            Interval(BSON("" << "" << "" << BSONObj()), true, false));
+        BSONObjBuilder builder;
+        builder.appendRegex("", "abc");
+        builder.appendRegex("", "abc");
+        expected.intervals.push_back(Interval(builder.obj(), true, true));
+        CheckIndexBounds("{ a: /abc/ }", expected);
+    }
+
+    // {$where: 'this.credits == this.debits' }
+    TEST(CMCollapseTreeTest, Where) {
+        OrderedIntervalList expected;
+        BSONObjBuilder builder;
+        builder.appendMinKey("");
+        builder.appendMaxKey("");
+        expected.intervals.push_back(Interval(builder.obj(), true, true));
+        CheckIndexBounds("{$where: 'this.credits == this.debits' }", expected);
+    }
+
+    // { $text: { $search: "coffee -cake" } }
+    TEST(CMCollapseTreeTest, Text) {
+        OrderedIntervalList expected;
+        BSONObjBuilder builder;
+        builder.appendMinKey("");
+        builder.appendMaxKey("");
+        expected.intervals.push_back(Interval(builder.obj(), true, true));
+        CheckIndexBounds("{ $text: { $search: 'coffee -cake' } }", expected);
+    }
+
+    // { a: 2, $text: { $search: "leche", $language: "es" } }
+    TEST(CMCollapseTreeTest, TextWithQuery) {
+        OrderedIntervalList expected;
+        BSONObjBuilder builder;
+        builder.appendMinKey("");
+        builder.appendMaxKey("");
+        expected.intervals.push_back(Interval(builder.obj(), true, true));
+        CheckIndexBounds("{ a: 2, $text: { $search: 'leche', $language: 'es' } }", expected);
+    }
+
+    //  { a: 0 } -> hashed a: [hash(0), hash(0)]
+    TEST(CMCollapseTreeTest, HashedSinglePoint) {
+        const char* queryStr = "{ a: 0 }";
+        auto_ptr<CanonicalQuery> query(canonicalize(queryStr));
+        ASSERT(query.get() != NULL);
+
+        BSONObj key = fromjson("{a: 'hashed'}");
+
+        IndexBounds indexBounds = ChunkManager::getIndexBoundsForQuery(key, query.get());
+        ASSERT_EQUALS(indexBounds.size(), 1U);
+        const OrderedIntervalList& oil = indexBounds.fields.front();
+        ASSERT_EQUALS(oil.intervals.size(), 1U);
+        const Interval& interval = oil.intervals.front();
+        ASSERT(interval.isPoint());
+    }
+
+    // { a: { $lt: 2, $gt: 1} } -> hashed a: [Minkey, Maxkey]
+    TEST(CMCollapseTreeTest, HashedRange) {
+        IndexBounds expectedBounds;
+        expectedBounds.fields.push_back(OrderedIntervalList());
+        OrderedIntervalList& expectedOil = expectedBounds.fields.front();
+        BSONObjBuilder builder;
+        builder.appendMinKey("");
+        builder.appendMaxKey("");
+        expectedOil.intervals.push_back(Interval(builder.obj(), true, true));
+        CheckIndexBoundsWithKey("{a: 'hashed'}", "{ a: { $lt: 2, $gt: 1} }", expectedBounds);
+    }
+
+    // { a: /abc/ } -> hashed a: [Minkey, Maxkey]
+    TEST(CMCollapseTreeTest, HashedRegex) {
+        IndexBounds expectedBounds;
+        expectedBounds.fields.push_back(OrderedIntervalList());
+        OrderedIntervalList& expectedOil = expectedBounds.fields.front();
+        BSONObjBuilder builder;
+        builder.appendMinKey("");
+        builder.appendMaxKey("");
+        expectedOil.intervals.push_back(Interval(builder.obj(), true, true));
+
+        CheckIndexBoundsWithKey("{a: 'hashed'}", "{ a: /abc/ }", expectedBounds);
+    }
+
+    /**
+     * KeyPattern key bounds generation test
+     */
+
+    void CheckBoundList(const BoundList& list, const BoundList& expected) {
+        ASSERT_EQUALS(list.size(), expected.size());
+        for (size_t i = 0; i < list.size(); i++) {
+            ASSERT_EQUALS(list[i].first.woCompare(expected[i].first), 0);
+            ASSERT_EQUALS(list[i].second.woCompare(expected[i].second), 0);
+        }
+    }
+
+    // Key { a: 1 }, Bounds a: [0]
+    //  => { a: 0 } -> { a: 0 }
+    TEST(CMKeyBoundsTest, Basic) {
+        IndexBounds indexBounds;
+        indexBounds.fields.push_back(OrderedIntervalList());
+        indexBounds.fields.front().intervals.push_back(
+            Interval(BSON("" << 0 << "" << 0), true, true));
+
+        BoundList expectedList;
+        expectedList.push_back(make_pair(fromjson("{a: 0}"), fromjson("{a: 0}")));
+
+        BoundList list = KeyPattern::keyBounds(fromjson("{a: 1}"), indexBounds);
+        CheckBoundList(list, expectedList);
+    }
+
+    // Key { a: 1 }, Bounds a: [2, 3)
+    //  => { a: 2 } -> { a: 3 }  // bound inclusion is ignored.
+    TEST(CMKeyBoundsTest, SingleInterval) {
+        IndexBounds indexBounds;
+        indexBounds.fields.push_back(OrderedIntervalList());
+        indexBounds.fields.front().intervals.push_back(
+            Interval(BSON("" << 2 << "" << 3), true, false));
+
+        BoundList expectedList;
+        expectedList.push_back(make_pair(fromjson("{a: 2}"), fromjson("{a: 3}")));
+
+        BoundList list = KeyPattern::keyBounds(fromjson("{a: 1}"), indexBounds);
+        CheckBoundList(list, expectedList);
+    }
+
+    // Key { a: 1, b: 1, c: 1 }, Bounds a: [2, 3), b: [2, 3), c: [2: 3)
+    //  => { a: 2, b: 2, c: 2 } -> { a: 3, b: 3, c: 3 }
+    TEST(CMKeyBoundsTest, MultiIntervals) {
+        IndexBounds indexBounds;
+        indexBounds.fields.push_back(OrderedIntervalList());
+        indexBounds.fields.push_back(OrderedIntervalList());
+        indexBounds.fields.push_back(OrderedIntervalList());
+        indexBounds.fields[0].intervals.push_back(
+            Interval(BSON("" << 2 << "" << 3), true, false));
+        indexBounds.fields[1].intervals.push_back(
+            Interval(BSON("" << 2 << "" << 3), true, false));
+        indexBounds.fields[2].intervals.push_back(
+            Interval(BSON("" << 2 << "" << 3), true, false));
+
+        BoundList expectedList;
+        expectedList.push_back(make_pair(
+            fromjson("{ a: 2, b: 2, c: 2 }"),
+            fromjson("{ a: 3, b: 3, c: 3 }")));
+
+        BoundList list = KeyPattern::keyBounds(fromjson("{a: 1, b: 1, c: 1}"), indexBounds);
+        CheckBoundList(list, expectedList);
+    }
+
+    // Key { a: 1, b: 1, c: 1 }, Bounds a: [0, 0], b: { $in: [4, 5, 6] }, c: [2: 3)
+    //  => { a: 0, b: 4, c: 2 } -> { a: 0, b: 4, c: 3 }
+    //     { a: 0, b: 5, c: 2 } -> { a: 0, b: 5, c: 3 }
+    //     { a: 0, b: 6, c: 2 } -> { a: 0, b: 6, c: 3 }
+    TEST(CMKeyBoundsTest, IntervalExpansion) {
+        IndexBounds indexBounds;
+        indexBounds.fields.push_back(OrderedIntervalList());
+        indexBounds.fields.push_back(OrderedIntervalList());
+        indexBounds.fields.push_back(OrderedIntervalList());
+
+        indexBounds.fields[0].intervals.push_back(
+            Interval(BSON("" << 0 << "" << 0), true, true));
+
+        indexBounds.fields[1].intervals.push_back(
+            Interval(BSON("" << 4 << "" << 4), true, true));
+        indexBounds.fields[1].intervals.push_back(
+            Interval(BSON("" << 5 << "" << 5), true, true));
+        indexBounds.fields[1].intervals.push_back(
+            Interval(BSON("" << 6 << "" << 6), true, true));
+
+        indexBounds.fields[2].intervals.push_back(
+            Interval(BSON("" << 2 << "" << 3), true, false));
+
+        BoundList expectedList;
+        expectedList.push_back(make_pair(
+            fromjson("{ a: 0, b: 4, c: 2 }"),
+            fromjson("{ a: 0, b: 4, c: 3 }")));
+        expectedList.push_back(make_pair(
+            fromjson("{ a: 0, b: 5, c: 2 }"),
+            fromjson("{ a: 0, b: 5, c: 3 }")));
+        expectedList.push_back(make_pair(
+            fromjson("{ a: 0, b: 6, c: 2 }"),
+            fromjson("{ a: 0, b: 6, c: 3 }")));
+
+        BoundList list = KeyPattern::keyBounds(fromjson("{a: 1, b: 1, c: 1}"), indexBounds);
+        CheckBoundList(list, expectedList);
+    }
+
+    // Key { a: 1, b: 1, c: 1 }, Bounds a: [0, 1], b: { $in: [4, 5, 6] }, c: [2: 3)
+    //  => { a: 0, b: 4, c: 2 } -> { a: 1, b: 6, c: 3 }
+    // Since field "a" is not a point, expasion after "a" is not allowed.
+    TEST(CMKeyBoundsTest, NonPointIntervalExpasion) {
+        IndexBounds indexBounds;
+        indexBounds.fields.push_back(OrderedIntervalList());
+        indexBounds.fields.push_back(OrderedIntervalList());
+        indexBounds.fields.push_back(OrderedIntervalList());
+
+        indexBounds.fields[0].intervals.push_back(
+            Interval(BSON("" << 0 << "" << 1), true, true));
+
+        indexBounds.fields[1].intervals.push_back(
+            Interval(BSON("" << 4 << "" << 4), true, true));
+        indexBounds.fields[1].intervals.push_back(
+            Interval(BSON("" << 5 << "" << 5), true, true));
+        indexBounds.fields[1].intervals.push_back(
+            Interval(BSON("" << 6 << "" << 6), true, true));
+
+        indexBounds.fields[2].intervals.push_back(
+            Interval(BSON("" << 2 << "" << 3), true, false));
+
+        BoundList expectedList;
+        expectedList.push_back(make_pair(
+            fromjson("{ a: 0, b: 4, c: 2 }"),
+            fromjson("{ a: 1, b: 6, c: 3 }")));
+        BoundList list = KeyPattern::keyBounds(fromjson("{a: 1, b: 1, c: 1}"), indexBounds);
+        CheckBoundList(list, expectedList);
+    }
+
+} // end namespace
diff --git a/src/mongo/s/expression_where_noop.cpp b/src/mongo/s/expression_where_noop.cpp
new file mode 100644
index 00000000000..1a88989e4bf
--- /dev/null
+++ b/src/mongo/s/expression_where_noop.cpp
@@ -0,0 +1,130 @@
+// expression_where_noop.cpp
+
+/**
+ *    Copyright (C) 2013 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/base/init.h"
+#include "mongo/db/matcher/expression.h"
+#include "mongo/db/matcher/expression_parser.h"
+
+namespace mongo {
+
+    /**
+     * Bogus no-op $where match expression to parse $where in mongos,
+     * since mongos doesn't have script engine to compile JS functions.
+     *
+     * Linked into mongos, instead of the real WhereMatchExpression.
+     */
+    class WhereNoOpMatchExpression : public MatchExpression {
+    public:
+        WhereNoOpMatchExpression() : MatchExpression( WHERE ){ }
+        virtual ~WhereNoOpMatchExpression(){}
+
+        Status init( const StringData& theCode );
+
+        virtual bool matches( const MatchableDocument* doc, MatchDetails* details = 0 ) const {
+            return false;
+        }
+
+        virtual bool matchesSingleElement( const BSONElement& e ) const {
+            return false;
+        }
+
+        virtual MatchExpression* shallowClone() const {
+            WhereNoOpMatchExpression* e = new WhereNoOpMatchExpression();
+            e->init(_code);
+            if ( getTag() ) {
+                e->setTag(getTag()->clone());
+            }
+            return e;
+        }
+
+        virtual void debugString( StringBuilder& debug, int level = 0 ) const;
+
+        virtual bool equivalent( const MatchExpression* other ) const ;
+
+        virtual void resetTag() { setTag(NULL); }
+
+    private:
+        string _code;
+    };
+
+    Status WhereNoOpMatchExpression::init(const StringData& theCode ) {
+        if ( theCode.size() == 0 )
+            return Status( ErrorCodes::BadValue, "code for $where cannot be empty" );
+
+        _code = theCode.toString();
+
+        return Status::OK();
+    }
+
+    void WhereNoOpMatchExpression::debugString( StringBuilder& debug, int level ) const {
+        _debugAddSpace( debug, level );
+        debug << "$where (only in mongos)\n";
+
+        _debugAddSpace( debug, level + 1 );
+        debug << "code: " << _code << "\n";
+    }
+
+    bool WhereNoOpMatchExpression::equivalent( const MatchExpression* other ) const {
+        if ( matchType() != other->matchType() )
+            return false;
+        const WhereNoOpMatchExpression* noopOther = static_cast<const WhereNoOpMatchExpression*>(other);
+        return _code == noopOther->_code;
+    }
+
+
+    // -----------------
+
+    StatusWithMatchExpression expressionParserWhereCallbackNoOp(const BSONElement& where) {
+        auto_ptr<WhereNoOpMatchExpression> exp( new WhereNoOpMatchExpression() );
+        if ( where.type() == String || where.type() == Code ) {
+            Status s = exp->init( where.valuestr() );
+            if ( !s.isOK() )
+                return StatusWithMatchExpression( s );
+            return StatusWithMatchExpression( exp.release() );
+        }
+
+        if ( where.type() == CodeWScope ) {
+            Status s = exp->init( where.codeWScopeCode() );
+            if ( !s.isOK() )
+                return StatusWithMatchExpression( s );
+            return StatusWithMatchExpression( exp.release() );
+        }
+
+        return StatusWithMatchExpression( ErrorCodes::BadValue, "$where got bad type" );
+    }
+
+    // Override callback
+    MONGO_INITIALIZER_WITH_PREREQUISITES( MatchExpressionWhereNoOp, ("MatchExpressionWhere") )( ::mongo::InitializerContext* context ) {
+        expressionParserWhereCallback = expressionParserWhereCallbackNoOp;
+        return Status::OK();
+    }
+
+}