SERVER-6400 new expression tree and parser

Will eventually replace Matcher

22 files changed, 5830 insertions, 0 deletions

diff --git a/src/mongo/SConscript b/src/mongo/SConscript
index fac782eadc4..a97b27c0d6b 100644
--- a/src/mongo/SConscript
+++ b/src/mongo/SConscript
@@ -111,6 +111,35 @@ env.CppUnitTest('index_set_test', ['db/index_set_test.cpp'],
                 LIBDEPS=['bson','index_set'])
 
 
+
+env.StaticLibrary('expressions',
+                  ['db/matcher/expression.cpp',
+                   'db/matcher/expression_array.cpp',
+                   'db/matcher/expression_internal.cpp',
+                   'db/matcher/expression_leaf.cpp',
+                   'db/matcher/expression_tree.cpp',
+                   'db/matcher/expression_parser.cpp',
+                   'db/matcher/expression_parser_tree.cpp'],
+                  LIBDEPS=['bson',
+                           '$BUILD_DIR/mongo/db/common',
+                           '$BUILD_DIR/third_party/pcrecpp'
+                           ] )
+
+env.CppUnitTest('expression_test',
+                ['db/matcher/expression_test.cpp',
+                 'db/matcher/expression_leaf_test.cpp',
+                 'db/matcher/expression_tree_test.cpp',
+                 'db/matcher/expression_array_test.cpp'],
+                LIBDEPS=['expressions'] )
+
+env.CppUnitTest('expression_parser_test',
+                ['db/matcher/expression_parser_test.cpp',
+                 'db/matcher/expression_parser_array_test.cpp',
+                 'db/matcher/expression_parser_tree_test.cpp',
+                 'db/matcher/expression_parser_leaf_test.cpp'],
+                LIBDEPS=['expressions'] )
+
+
 env.CppUnitTest('bson_extract_test', ['bson/util/bson_extract_test.cpp'], LIBDEPS=['bson'])
 
 env.CppUnitTest('descriptive_stats_test',
diff --git a/src/mongo/db/matcher/expression.cpp b/src/mongo/db/matcher/expression.cpp
new file mode 100644
index 00000000000..8d563c28711
--- /dev/null
+++ b/src/mongo/db/matcher/expression.cpp
@@ -0,0 +1,42 @@
+// expression.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/>.
+ */
+
+#include "mongo/db/matcher/expression.h"
+
+#include "mongo/bson/bsonobjiterator.h"
+#include "mongo/bson/bsonobj.h"
+#include "mongo/bson/bsonmisc.h"
+#include "mongo/db/matcher.h"
+#include "mongo/util/log.h"
+
+namespace mongo {
+
+    string Expression::toString() const {
+        StringBuilder buf;
+        debugString( buf, 0 );
+        return buf.str();
+    }
+
+    void Expression::_debugAddSpace( StringBuilder& debug, int level ) const {
+        for ( int i = 0; i < level; i++ )
+            debug << "    ";
+    }
+
+}
+
+
diff --git a/src/mongo/db/matcher/expression.h b/src/mongo/db/matcher/expression.h
new file mode 100644
index 00000000000..734fb4e75c8
--- /dev/null
+++ b/src/mongo/db/matcher/expression.h
@@ -0,0 +1,55 @@
+// expression.h
+
+/**
+ *    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/>.
+ */
+
+#pragma once
+
+#include "mongo/base/disallow_copying.h"
+#include "mongo/base/status.h"
+#include "mongo/bson/bsonobj.h"
+
+namespace mongo {
+
+    class TreeExpression;
+    class MatchDetails;
+
+    class Expression {
+        MONGO_DISALLOW_COPYING( Expression );
+
+    public:
+        Expression(){}
+        virtual ~Expression(){}
+
+        /**
+         * determins if the doc matches the expression
+         * there could be an expression that looks at fields, or the entire doc
+         */
+        virtual bool matches( const BSONObj& doc, MatchDetails* details = 0 ) const = 0;
+
+        /**
+         * does the element match the expression
+         * not valid for all expressions ($where) where this will immediately return false
+         */
+        virtual bool matchesSingleElement( const BSONElement& e ) const = 0;
+
+        virtual string toString() const;
+        virtual void debugString( StringBuilder& debug, int level = 0 ) const = 0;
+    protected:
+        void _debugAddSpace( StringBuilder& debug, int level ) const;
+    };
+
+}
diff --git a/src/mongo/db/matcher/expression_array.cpp b/src/mongo/db/matcher/expression_array.cpp
new file mode 100644
index 00000000000..6c1acc5f9a8
--- /dev/null
+++ b/src/mongo/db/matcher/expression_array.cpp
@@ -0,0 +1,348 @@
+// expression_array.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/>.
+ */
+
+#include "mongo/db/matcher/expression_array.h"
+
+#include "mongo/bson/bsonobjiterator.h"
+#include "mongo/db/field_ref.h"
+#include "mongo/db/matcher.h"
+#include "mongo/db/matcher/expression_internal.h"
+#include "mongo/util/log.h"
+
+namespace mongo {
+
+
+    // ----------
+
+    Status AllExpression::init( const StringData& path ) {
+        _path = path;
+        return Status::OK();
+    }
+
+    bool AllExpression::matches( const BSONObj& doc, MatchDetails* details ) const {
+        FieldRef path;
+        path.parse(_path);
+
+        bool traversedArray = false;
+        int32_t idxPath = 0;
+        BSONElement e = getFieldDottedOrArray( doc, path, &idxPath, &traversedArray );
+
+        string rest = pathToString( path, idxPath+1 );
+
+        if ( e.type() != Array || traversedArray || rest.size() == 0 ) {
+            return matchesSingleElement( e );
+        }
+
+        BSONElementSet all;
+
+        BSONObjIterator i( e.Obj() );
+        while ( i.more() ) {
+            BSONElement e = i.next();
+            if ( ! e.isABSONObj() )
+                continue;
+
+            e.Obj().getFieldsDotted( rest, all );
+        }
+
+        return _match( all );
+    }
+
+    bool AllExpression::matchesSingleElement( const BSONElement& e ) const {
+        if ( _arrayEntries.size() == 0 )
+            return false;
+
+        if ( e.eoo() )
+            return _arrayEntries.singleNull();
+
+        BSONElementSet all;
+
+        if ( e.type() == Array ) {
+            BSONObjIterator i( e.Obj() );
+            while ( i.more() ) {
+                all.insert( i.next() );
+            }
+        }
+        else {
+            // this is the part i want to remove
+            all.insert( e );
+        }
+
+        return _match( all );
+    }
+
+    bool AllExpression::_match( const BSONElementSet& all ) const {
+
+        if ( all.size() == 0 )
+            return _arrayEntries.singleNull();
+
+        const BSONElementSet& equalities = _arrayEntries.equalities();
+        for ( BSONElementSet::const_iterator i = equalities.begin(); i != equalities.end(); ++i ) {
+            BSONElement foo = *i;
+            if ( all.count( foo ) == 0 )
+                return false;
+        }
+
+        for ( size_t i = 0; i < _arrayEntries.numRegexes(); i++ ) {
+
+            bool found = false;
+            for ( BSONElementSet::const_iterator j = all.begin(); j != all.end(); ++j ) {
+                BSONElement bar = *j;
+                if ( _arrayEntries.regex(i)->matchesSingleElement( bar ) ) {
+                    found = true;
+                    break;
+                }
+            }
+            if ( ! found )
+                return false;
+
+        }
+
+        return true;
+    }
+
+    void AllExpression::debugString( StringBuilder& debug, int level ) const {
+        _debugAddSpace( debug, level );
+        debug << _path << " $all TODO\n";
+    }
+
+    // -------
+
+    bool ArrayMatchingExpression::matches( const BSONObj& doc, MatchDetails* details ) const {
+
+        FieldRef path;
+        path.parse(_path);
+
+        bool traversedArray = false;
+        int32_t idxPath = 0;
+        BSONElement e = getFieldDottedOrArray( doc, path, &idxPath, &traversedArray );
+
+        string rest = pathToString( path, idxPath+1 );
+
+        if ( rest.size() == 0 ) {
+            if ( e.type() == Array )
+                return matchesArray( e.Obj(), details );
+            return false;
+        }
+
+        if ( e.type() != Array )
+            return false;
+
+        BSONObjIterator i( e.Obj() );
+        while ( i.more() ) {
+            BSONElement x = i.next();
+            if ( ! x.isABSONObj() )
+                continue;
+
+            BSONElement sub = x.Obj().getFieldDotted( rest );
+            if ( sub.type() != Array )
+                continue;
+
+            if ( matchesArray( sub.Obj(), NULL ) ) {
+                if ( details && details->needRecord() ) {
+                    // trying to match crazy semantics??
+                    details->setElemMatchKey( x.fieldName() );
+                }
+                return true;
+            }
+        }
+
+        return false;
+    }
+
+    bool ArrayMatchingExpression::matchesSingleElement( const BSONElement& e ) const {
+        if ( e.type() != Array )
+            return false;
+        return matchesArray( e.Obj(), NULL );
+    }
+
+
+    // -------
+
+    Status ElemMatchObjectExpression::init( const StringData& path, const Expression* sub ) {
+        _path = path;
+        _sub.reset( sub );
+        return Status::OK();
+    }
+
+
+
+    bool ElemMatchObjectExpression::matchesArray( const BSONObj& anArray, MatchDetails* details ) const {
+        BSONObjIterator i( anArray );
+        while ( i.more() ) {
+            BSONElement inner = i.next();
+            if ( !inner.isABSONObj() )
+                continue;
+            if ( _sub->matches( inner.Obj(), NULL ) ) {
+                if ( details && details->needRecord() ) {
+                    details->setElemMatchKey( inner.fieldName() );
+                }
+                return true;
+            }
+        }
+        return false;
+    }
+
+    void ElemMatchObjectExpression::debugString( StringBuilder& debug, int level ) const {
+        _debugAddSpace( debug, level );
+        debug << _path << " $elemMatch\n";
+        _sub->debugString( debug, level + 1 );
+    }
+
+
+    // -------
+
+    ElemMatchValueExpression::~ElemMatchValueExpression() {
+        for ( unsigned i = 0; i < _subs.size(); i++ )
+            delete _subs[i];
+        _subs.clear();
+    }
+
+    Status ElemMatchValueExpression::init( const StringData& path, const Expression* sub ) {
+        init( path );
+        add( sub );
+        return Status::OK();
+    }
+
+    Status ElemMatchValueExpression::init( const StringData& path ) {
+        _path = path;
+        return Status::OK();
+    }
+
+
+    void ElemMatchValueExpression::add( const Expression* sub ) {
+        verify( sub );
+        _subs.push_back( sub );
+    }
+
+    bool ElemMatchValueExpression::matchesArray( const BSONObj& anArray, MatchDetails* details ) const {
+        BSONObjIterator i( anArray );
+        while ( i.more() ) {
+            BSONElement inner = i.next();
+
+            if ( _arrayElementMatchesAll( inner ) ) {
+                if ( details && details->needRecord() ) {
+                    details->setElemMatchKey( inner.fieldName() );
+                }
+                return true;
+            }
+        }
+        return false;
+    }
+
+    bool ElemMatchValueExpression::_arrayElementMatchesAll( const BSONElement& e ) const {
+        for ( unsigned i = 0; i < _subs.size(); i++ ) {
+            if ( !_subs[i]->matchesSingleElement( e ) )
+                return false;
+        }
+        return true;
+    }
+
+    void ElemMatchValueExpression::debugString( StringBuilder& debug, int level ) const {
+        _debugAddSpace( debug, level );
+        debug << _path << " $elemMatch\n";
+        for ( unsigned i = 0; i < _subs.size(); i++ ) {
+            _subs[i]->debugString( debug, level + 1 );
+        }
+    }
+
+
+    // ------
+
+    AllElemMatchOp::~AllElemMatchOp() {
+        for ( unsigned i = 0; i < _list.size(); i++ )
+            delete _list[i];
+        _list.clear();
+    }
+
+    Status AllElemMatchOp::init( const StringData& path ) {
+        _path = path;
+        return Status::OK();
+    }
+
+    void AllElemMatchOp::add( const ArrayMatchingExpression* expr ) {
+        verify( expr );
+        _list.push_back( expr );
+    }
+
+    bool AllElemMatchOp::matches( const BSONObj& doc, MatchDetails* details ) const {
+        BSONElementSet all;
+        doc.getFieldsDotted( _path, all, false );
+
+        for ( BSONElementSet::const_iterator i = all.begin(); i != all.end(); ++i ) {
+            BSONElement sub = *i;
+            if ( sub.type() != Array )
+                continue;
+            if ( _allMatch( sub.Obj() ) ) {
+                return true;
+            }
+        }
+        return false;
+    }
+
+    bool AllElemMatchOp::matchesSingleElement( const BSONElement& e ) const {
+        if ( e.type() != Array )
+            return false;
+
+        return _allMatch( e.Obj() );
+    }
+
+    bool AllElemMatchOp::_allMatch( const BSONObj& anArray ) const {
+        if ( _list.size() == 0 )
+            return false;
+        for ( unsigned i = 0; i < _list.size(); i++ ) {
+            if ( !_list[i]->matchesArray( anArray, NULL ) )
+                return false;
+        }
+        return true;
+    }
+
+
+    void AllElemMatchOp::debugString( StringBuilder& debug, int level ) const {
+        _debugAddSpace( debug, level );
+        debug << _path << " AllElemMatchOp: " << _path << "\n";
+        for ( size_t i = 0; i < _list.size(); i++ ) {
+            _list[i]->debugString( debug, level + 1);
+        }
+    }
+
+
+    // ---------
+
+    Status SizeExpression::init( const StringData& path, int size ) {
+        _path = path;
+        _size = size;
+        return Status::OK();
+    }
+
+    bool SizeExpression::matchesArray( const BSONObj& anArray, MatchDetails* details ) const {
+        if ( _size < 0 )
+            return false;
+        return anArray.nFields() == _size;
+    }
+
+    void SizeExpression::debugString( StringBuilder& debug, int level ) const {
+        _debugAddSpace( debug, level );
+        debug << _path << " $size : " << _size << "\n";
+    }
+
+
+    // ------------------
+
+
+
+}
diff --git a/src/mongo/db/matcher/expression_array.h b/src/mongo/db/matcher/expression_array.h
new file mode 100644
index 00000000000..07856284d9a
--- /dev/null
+++ b/src/mongo/db/matcher/expression_array.h
@@ -0,0 +1,144 @@
+// expression_array.h
+
+/**
+ *    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/>.
+ */
+
+#pragma once
+
+#include <vector>
+
+#include "mongo/base/status.h"
+#include "mongo/bson/bsonobj.h"
+#include "mongo/bson/bsonmisc.h"
+#include "mongo/db/matcher/expression.h"
+#include "mongo/db/matcher/expression_leaf.h"
+
+namespace mongo {
+    /**
+     * this SHOULD extend from ArrayMatchingExpression
+     * the only reason it can't is
+
+     > db.foo.insert( { x : 5 } )
+     > db.foo.insert( { x : [5] } )
+     > db.foo.find( { x : { $all : [ 5 ] } } )
+     { "_id" : ObjectId("5162b5c3f98a76ce1e70ed0c"), "x" : 5 }
+     { "_id" : ObjectId("5162b5c5f98a76ce1e70ed0d"), "x" : [ 5 ] }
+
+     * the { x : 5}  doc should NOT match
+     *
+     */
+    class AllExpression : public Expression {
+    public:
+        Status init( const StringData& path );
+        ArrayFilterEntries* getArrayFilterEntries() { return &_arrayEntries; }
+
+        virtual bool matches( const BSONObj& doc, MatchDetails* details = 0 ) const;
+
+        virtual bool matchesSingleElement( const BSONElement& e ) const;
+
+        virtual void debugString( StringBuilder& debug, int level ) const;
+    private:
+        bool _match( const BSONElementSet& all ) const;
+
+        StringData _path;
+        ArrayFilterEntries _arrayEntries;
+    };
+
+
+    class ArrayMatchingExpression : public Expression {
+    public:
+        virtual ~ArrayMatchingExpression(){}
+
+        virtual bool matches( const BSONObj& doc, MatchDetails* details ) const;
+
+        /**
+         * @param e - has to be an array.  calls matchesArray with e as an array
+         */
+        virtual bool matchesSingleElement( const BSONElement& e ) const;
+
+        virtual bool matchesArray( const BSONObj& anArray, MatchDetails* details ) const = 0;
+
+    protected:
+        StringData _path;
+    };
+
+
+    class ElemMatchObjectExpression : public ArrayMatchingExpression {
+    public:
+        Status init( const StringData& path, const Expression* sub );
+
+        bool matchesArray( const BSONObj& anArray, MatchDetails* details ) const;
+
+        virtual void debugString( StringBuilder& debug, int level ) const;
+    private:
+        boost::scoped_ptr<const Expression> _sub;
+    };
+
+    class ElemMatchValueExpression : public ArrayMatchingExpression {
+    public:
+        virtual ~ElemMatchValueExpression();
+
+        Status init( const StringData& path );
+        Status init( const StringData& path, const Expression* sub );
+        void add( const Expression* sub );
+
+        bool matchesArray( const BSONObj& anArray, MatchDetails* details ) const;
+
+        virtual void debugString( StringBuilder& debug, int level ) const;
+    private:
+        bool _arrayElementMatchesAll( const BSONElement& e ) const;
+
+        std::vector< const Expression* > _subs;
+    };
+
+
+    /**
+     * i'm suprised this isn't a regular AllExpression
+     */
+    class AllElemMatchOp : public Expression {
+    public:
+        virtual ~AllElemMatchOp();
+
+        Status init( const StringData& path );
+        void add( const ArrayMatchingExpression* expr );
+
+        virtual bool matches( const BSONObj& doc, MatchDetails* details ) const;
+
+        /**
+         * @param e has to be an array
+         */
+        virtual bool matchesSingleElement( const BSONElement& e ) const;
+
+        virtual void debugString( StringBuilder& debug, int level ) const;
+    private:
+        bool _allMatch( const BSONObj& anArray ) const;
+
+        StringData _path;
+        std::vector< const ArrayMatchingExpression* > _list;
+    };
+
+    class SizeExpression : public ArrayMatchingExpression {
+    public:
+        Status init( const StringData& path, int size );
+
+        virtual bool matchesArray( const BSONObj& anArray, MatchDetails* details ) const;
+
+        virtual void debugString( StringBuilder& debug, int level ) const;
+    private:
+        int _size; // >= 0 real, < 0, nothing will match
+    };
+
+}
diff --git a/src/mongo/db/matcher/expression_array_test.cpp b/src/mongo/db/matcher/expression_array_test.cpp
new file mode 100644
index 00000000000..58d47d155a5
--- /dev/null
+++ b/src/mongo/db/matcher/expression_array_test.cpp
@@ -0,0 +1,646 @@
+/**
+ *    Copyright (C) 2012 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/>.
+ */
+
+/** Unit tests for MatchExpression operator implementations in match_operators.{h,cpp}. */
+
+#include "mongo/unittest/unittest.h"
+
+#include "mongo/db/jsobj.h"
+#include "mongo/db/json.h"
+#include "mongo/db/matcher.h"
+#include "mongo/db/matcher/expression.h"
+#include "mongo/db/matcher/expression_array.h"
+#include "mongo/db/matcher/expression_tree.h"
+
+namespace mongo {
+
+    TEST( AllExpression, MatchesElementSingle ) {
+        BSONObj operand = BSON_ARRAY( 1 << 1 );
+        BSONObj match = BSON( "a" << 1 );
+        BSONObj notMatch = BSON( "a" << 2 );
+        AllExpression all;
+        all.getArrayFilterEntries()->addEquality( operand[0] );
+        all.getArrayFilterEntries()->addEquality( operand[1] );
+
+        ASSERT( all.matchesSingleElement( match[ "a" ] ) );
+        ASSERT( !all.matchesSingleElement( notMatch[ "a" ] ) );
+    }
+
+    TEST( AllExpression, MatchesEmpty ) {
+
+        BSONObj notMatch = BSON( "a" << 2 );
+        AllExpression all;
+
+        ASSERT( !all.matchesSingleElement( notMatch[ "a" ] ) );
+        ASSERT( !all.matches( BSON( "a" << 1 ), NULL ) );
+        ASSERT( !all.matches( BSONObj(), NULL ) );
+    }
+
+    TEST( AllExpression, MatchesElementMultiple ) {
+        BSONObj operand = BSON_ARRAY( 1 << "r" );
+        AllExpression all;
+        all.getArrayFilterEntries()->addEquality( operand[0] );
+        all.getArrayFilterEntries()->addEquality( operand[1] );
+
+        BSONObj notMatchFirst = BSON( "a" << 1 );
+        BSONObj notMatchSecond = BSON( "a" << "r" );
+        BSONObj notMatchArray = BSON( "a" << BSON_ARRAY( 1 << "s" ) ); // XXX
+
+        ASSERT( !all.matchesSingleElement( notMatchFirst[ "a" ] ) );
+        ASSERT( !all.matchesSingleElement( notMatchSecond[ "a" ] ) );
+        ASSERT( !all.matchesSingleElement( notMatchArray[ "a" ] ) );
+    }
+
+    TEST( AllExpression, MatchesScalar ) {
+        BSONObj operand = BSON_ARRAY( 5 );
+        AllExpression all;
+        all.init( "a" );
+        all.getArrayFilterEntries()->addEquality( operand[0] );
+
+        ASSERT( all.matches( BSON( "a" << 5.0 ), NULL ) );
+        ASSERT( !all.matches( BSON( "a" << 4 ), NULL ) );
+    }
+
+    TEST( AllExpression, MatchesArrayValue ) {
+        BSONObj operand = BSON_ARRAY( 5 );
+        AllExpression all;
+        all.init( "a" );
+        all.getArrayFilterEntries()->addEquality( operand[0] );
+
+        ASSERT( all.matches( BSON( "a" << BSON_ARRAY( 5.0 << 6 ) ), NULL ) );
+        ASSERT( !all.matches( BSON( "a" << BSON_ARRAY( 6 << 7 ) ), NULL ) );
+        ASSERT( !all.matches( BSON( "a" << BSON_ARRAY( BSON_ARRAY( 5 ) ) ), NULL ) );
+    }
+
+    TEST( AllExpression, MatchesNonArrayMultiValues ) {
+        BSONObj operand = BSON_ARRAY( 5 << 6 );
+        AllExpression all;
+        all.init( "a.b" );
+        all.getArrayFilterEntries()->addEquality( operand[0] );
+        all.getArrayFilterEntries()->addEquality( operand[1] );
+
+        ASSERT( all.matches( BSON( "a" << BSON_ARRAY( BSON( "b" << 5.0 ) << BSON( "b" << 6 ) ) ),
+                             NULL ) );
+        ASSERT( all.matches( BSON( "a" << BSON_ARRAY( BSON( "b" << BSON_ARRAY( 5.0 << 7 ) ) <<
+                                                      BSON( "b" << BSON_ARRAY( 10 << 6 ) ) ) ),
+                             NULL ) );
+        ASSERT( !all.matches( BSON( "a" << BSON_ARRAY( BSON( "b" << 5.0 ) << BSON( "c" << 6 ) ) ),
+                              NULL ) );
+    }
+
+    TEST( AllExpression, MatchesArrayAndNonArrayMultiValues ) {
+        BSONObj operand = BSON_ARRAY( 1 << 2 << 3 << 4 );
+        AllExpression all;
+        all.init( "a.b" );
+        all.getArrayFilterEntries()->addEquality( operand[0] );
+        all.getArrayFilterEntries()->addEquality( operand[1] );
+        all.getArrayFilterEntries()->addEquality( operand[2] );
+        all.getArrayFilterEntries()->addEquality( operand[3] );
+
+        ASSERT( all.matches( BSON( "a" << BSON_ARRAY( BSON( "b" << BSON_ARRAY( 4 << 5 << 2 ) ) <<
+                                                      BSON( "b" << 3 ) <<
+                                                      BSON( "b" << BSONArray() ) <<
+                                                      BSON( "b" << BSON_ARRAY( 1 ) ) ) ),
+                             NULL ) );
+    }
+
+    TEST( AllExpression, MatchesNull ) {
+        BSONObjBuilder allArray;
+        allArray.appendNull( "0" );
+        BSONObj operand = allArray.obj();
+
+        AllExpression all;
+        ASSERT( all.init( "a" ).isOK() );
+        all.getArrayFilterEntries()->addEquality( operand[0] );
+
+        ASSERT( all.matches( BSONObj(), NULL ) );
+        ASSERT( all.matches( BSON( "a" << BSONNULL ), NULL ) );
+        ASSERT( !all.matches( BSON( "a" << 4 ), NULL ) );
+    }
+
+    TEST( AllExpression, MatchesFullArray ) {
+        BSONObj operand = BSON_ARRAY( BSON_ARRAY( 1 << 2 ) << 1 );
+        AllExpression all;
+        ASSERT( all.init( "a" ).isOK() );
+        all.getArrayFilterEntries()->addEquality( operand[0] );
+        all.getArrayFilterEntries()->addEquality( operand[1] );
+
+        // $all does not match full arrays.
+        ASSERT( !all.matches( BSON( "a" << BSON_ARRAY( 1 << 2 ) ), NULL ) );
+        ASSERT( !all.matches( BSON( "a" << BSON_ARRAY( 1 << 2 << 3 ) ), NULL ) );
+        ASSERT( !all.matches( BSON( "a" << BSON_ARRAY( 1 ) ), NULL ) );
+        ASSERT( !all.matches( BSON( "a" << 1 ), NULL ) );
+    }
+
+    TEST( AllExpression, ElemMatchKey ) {
+        BSONObj operand = BSON_ARRAY( 5 );
+        AllExpression all;
+        ASSERT( all.init( "a" ).isOK() );
+        all.getArrayFilterEntries()->addEquality( operand[0] );
+
+        MatchDetails details;
+        details.requestElemMatchKey();
+        ASSERT( !all.matches( BSON( "a" << 4 ), &details ) );
+        ASSERT( !details.hasElemMatchKey() );
+        ASSERT( all.matches( BSON( "a" << 5 ), &details ) );
+        ASSERT( !details.hasElemMatchKey() );
+        ASSERT( all.matches( BSON( "a" << BSON_ARRAY( 1 << 2 << 5 ) ), &details ) );
+        // The elemMatchKey feature is not implemented for $all.
+        ASSERT( !details.hasElemMatchKey() );
+    }
+
+    TEST( AllExpression, MatchesMinKey ) {
+        BSONObj operand = BSON_ARRAY( MinKey );
+        AllExpression all;
+        ASSERT( all.init( "a" ).isOK() );
+        all.getArrayFilterEntries()->addEquality( operand[0] );
+
+        ASSERT( all.matches( BSON( "a" << MinKey ), NULL ) );
+        ASSERT( !all.matches( BSON( "a" << MaxKey ), NULL ) );
+        ASSERT( !all.matches( BSON( "a" << 4 ), NULL ) );
+    }
+
+    TEST( AllExpression, MatchesMaxKey ) {
+        BSONObj operand = BSON_ARRAY( MaxKey );
+        AllExpression all;
+        ASSERT( all.init( "a" ).isOK() );
+        all.getArrayFilterEntries()->addEquality( operand[0] );
+
+        ASSERT( all.matches( BSON( "a" << MaxKey ), NULL ) );
+        ASSERT( !all.matches( BSON( "a" << MinKey ), NULL ) );
+        ASSERT( !all.matches( BSON( "a" << 4 ), NULL ) );
+    }
+
+    /**
+    TEST( AllExpression, MatchesIndexKey ) {
+        BSONObj operand = BSON( "$all" << BSON_ARRAY( 5 ) );
+        AllExpression all;
+        ASSERT( all.init( "a", operand[ "$all" ] ).isOK() );
+        IndexSpec indexSpec( BSON( "a" << 1 ) );
+        BSONObj indexKey = BSON( "" << "7" );
+        ASSERT( MatchExpression::PartialMatchResult_Unknown ==
+                all.matchesIndexKey( indexKey, indexSpec ) );
+    }
+    */
+
+    TEST( ElemMatchObjectExpression, MatchesElementSingle ) {
+        BSONObj baseOperand = BSON( "b" << 5 );
+        BSONObj match = BSON( "a" << BSON_ARRAY( BSON( "b" << 5.0 ) ) );
+        BSONObj notMatch = BSON( "a" << BSON_ARRAY( BSON( "b" << 6 ) ) );
+        auto_ptr<ComparisonExpression> eq( new ComparisonExpression() );
+        ASSERT( eq->init( "b", ComparisonExpression::EQ, baseOperand[ "b" ] ).isOK() );
+        ElemMatchObjectExpression op;
+        ASSERT( op.init( "a", eq.release() ).isOK() );
+        ASSERT( op.matchesSingleElement( match[ "a" ] ) );
+        ASSERT( !op.matchesSingleElement( notMatch[ "a" ] ) );
+    }
+
+    TEST( ElemMatchObjectExpression, MatchesElementArray ) {
+        BSONObj baseOperand = BSON( "1" << 5 );
+        BSONObj match = BSON( "a" << BSON_ARRAY( BSON_ARRAY( 's' << 5.0 ) ) );
+        BSONObj notMatch = BSON( "a" << BSON_ARRAY( BSON_ARRAY( 5 << 6 ) ) );
+        auto_ptr<ComparisonExpression> eq( new ComparisonExpression() );
+        ASSERT( eq->init( "1", ComparisonExpression::EQ, baseOperand[ "1" ] ).isOK() );
+        ElemMatchObjectExpression op;
+        ASSERT( op.init( "a", eq.release() ).isOK() );
+        ASSERT( op.matchesSingleElement( match[ "a" ] ) );
+        ASSERT( !op.matchesSingleElement( notMatch[ "a" ] ) );
+    }
+
+    TEST( ElemMatchObjectExpression, MatchesElementMultiple ) {
+        BSONObj baseOperand1 = BSON( "b" << 5 );
+        BSONObj baseOperand2 = BSON( "b" << 6 );
+        BSONObj baseOperand3 = BSON( "c" << 7 );
+        BSONObj notMatch1 = BSON( "a" << BSON_ARRAY( BSON( "b" << 5 << "c" << 7 ) ) );
+        BSONObj notMatch2 = BSON( "a" << BSON_ARRAY( BSON( "b" << 6 << "c" << 7 ) ) );
+        BSONObj notMatch3 = BSON( "a" << BSON_ARRAY( BSON( "b" << BSON_ARRAY( 5 << 6 ) ) ) );
+        BSONObj match =
+            BSON( "a" << BSON_ARRAY( BSON( "b" << BSON_ARRAY( 5 << 6 ) << "c" << 7 ) ) );
+        auto_ptr<ComparisonExpression> eq1( new ComparisonExpression() );
+        ASSERT( eq1->init( "b", ComparisonExpression::EQ, baseOperand1[ "b" ] ).isOK() );
+        auto_ptr<ComparisonExpression> eq2( new ComparisonExpression() );
+        ASSERT( eq2->init( "b", ComparisonExpression::EQ, baseOperand2[ "b" ] ).isOK() );
+        auto_ptr<ComparisonExpression> eq3( new ComparisonExpression() );
+        ASSERT( eq3->init( "c", ComparisonExpression::EQ, baseOperand3[ "c" ] ).isOK() );
+
+        auto_ptr<AndExpression> andOp( new AndExpression() );
+        andOp->add( eq1.release() );
+        andOp->add( eq2.release() );
+        andOp->add( eq3.release() );
+
+        ElemMatchObjectExpression op;
+        ASSERT( op.init( "a", andOp.release() ).isOK() );
+        ASSERT( !op.matchesSingleElement( notMatch1[ "a" ] ) );
+        ASSERT( !op.matchesSingleElement( notMatch2[ "a" ] ) );
+        ASSERT( !op.matchesSingleElement( notMatch3[ "a" ] ) );
+        ASSERT( op.matchesSingleElement( match[ "a" ] ) );
+    }
+
+    TEST( ElemMatchObjectExpression, MatchesNonArray ) {
+        BSONObj baseOperand = BSON( "b" << 5 );
+        auto_ptr<ComparisonExpression> eq( new ComparisonExpression() );
+        ASSERT( eq->init( "b", ComparisonExpression::EQ, baseOperand[ "b" ] ).isOK() );
+        ElemMatchObjectExpression op;
+        ASSERT( op.init( "a", eq.release() ).isOK() );
+        // Directly nested objects are not matched with $elemMatch.  An intervening array is
+        // required.
+        ASSERT( !op.matches( BSON( "a" << BSON( "b" << 5 ) ), NULL ) );
+        ASSERT( !op.matches( BSON( "a" << BSON( "0" << ( BSON( "b" << 5 ) ) ) ), NULL ) );
+        ASSERT( !op.matches( BSON( "a" << 4 ), NULL ) );
+    }
+
+    TEST( ElemMatchObjectExpression, MatchesArrayObject ) {
+        BSONObj baseOperand = BSON( "b" << 5 );
+        auto_ptr<ComparisonExpression> eq( new ComparisonExpression() );
+        ASSERT( eq->init( "b", ComparisonExpression::EQ, baseOperand[ "b" ] ).isOK() );
+        ElemMatchObjectExpression op;
+        ASSERT( op.init( "a", eq.release() ).isOK() );
+        ASSERT( op.matches( BSON( "a" << BSON_ARRAY( BSON( "b" << 5 ) ) ), NULL ) );
+        ASSERT( op.matches( BSON( "a" << BSON_ARRAY( 4 << BSON( "b" << 5 ) ) ), NULL ) );
+        ASSERT( op.matches( BSON( "a" << BSON_ARRAY( BSONObj() << BSON( "b" << 5 ) ) ), NULL ) );
+        ASSERT( op.matches( BSON( "a" << BSON_ARRAY( BSON( "b" << 6 ) << BSON( "b" << 5 ) ) ),
+                            NULL ) );
+    }
+
+    TEST( ElemMatchObjectExpression, MatchesMultipleNamedValues ) {
+        BSONObj baseOperand = BSON( "c" << 5 );
+        auto_ptr<ComparisonExpression> eq( new ComparisonExpression() );
+        ASSERT( eq->init( "c", ComparisonExpression::EQ, baseOperand[ "c" ] ).isOK() );
+        ElemMatchObjectExpression op;
+        ASSERT( op.init( "a.b", eq.release() ).isOK() );
+        ASSERT( op.matches( BSON( "a" <<
+                                  BSON_ARRAY( BSON( "b" <<
+                                                    BSON_ARRAY( BSON( "c" <<
+                                                                      5 ) ) ) ) ),
+                            NULL ) );
+        ASSERT( op.matches( BSON( "a" <<
+                                  BSON_ARRAY( BSON( "b" <<
+                                                    BSON_ARRAY( BSON( "c" <<
+                                                                      1 ) ) ) <<
+                                              BSON( "b" <<
+                                                    BSON_ARRAY( BSON( "c" <<
+                                                                      5 ) ) ) ) ),
+                            NULL ) );
+    }
+
+    TEST( ElemMatchObjectExpression, ElemMatchKey ) {
+        BSONObj baseOperand = BSON( "c" << 6 );
+        auto_ptr<ComparisonExpression> eq( new ComparisonExpression() );
+        ASSERT( eq->init( "c", ComparisonExpression::EQ, baseOperand[ "c" ] ).isOK() );
+        ElemMatchObjectExpression op;
+        ASSERT( op.init( "a.b", eq.release() ).isOK() );
+        MatchDetails details;
+        details.requestElemMatchKey();
+        ASSERT( !op.matches( BSONObj(), &details ) );
+        ASSERT( !details.hasElemMatchKey() );
+        ASSERT( !op.matches( BSON( "a" << BSON( "b" << BSON_ARRAY( BSON( "c" << 7 ) ) ) ),
+                             &details ) );
+        ASSERT( !details.hasElemMatchKey() );
+        ASSERT( op.matches( BSON( "a" << BSON( "b" << BSON_ARRAY( 3 << BSON( "c" << 6 ) ) ) ),
+                            &details ) );
+        ASSERT( details.hasElemMatchKey() );
+        // The entry within the $elemMatch array is reported.
+        ASSERT_EQUALS( "1", details.elemMatchKey() );
+        ASSERT( op.matches( BSON( "a" <<
+                                  BSON_ARRAY( 1 << 2 <<
+                                              BSON( "b" << BSON_ARRAY( 3 <<
+                                                                       5 <<
+                                                                       BSON( "c" << 6 ) ) ) ) ),
+                            &details ) );
+        ASSERT( details.hasElemMatchKey() );
+        // The entry within a parent of the $elemMatch array is reported.
+        ASSERT_EQUALS( "2", details.elemMatchKey() );
+    }
+
+    /**
+    TEST( ElemMatchObjectExpression, MatchesIndexKey ) {
+        BSONObj baseOperand = BSON( "b" << 5 );
+        auto_ptr<ComparisonExpression> eq( new ComparisonExpression() );
+        ASSERT( eq->init( "b", baseOperand[ "b" ] ).isOK() );
+        ElemMatchObjectExpression op;
+        ASSERT( op.init( "a", eq.release() ).isOK() );
+        IndexSpec indexSpec( BSON( "a.b" << 1 ) );
+        BSONObj indexKey = BSON( "" << "5" );
+        ASSERT( MatchExpression::PartialMatchResult_Unknown ==
+                op.matchesIndexKey( indexKey, indexSpec ) );
+    }
+    */
+
+    TEST( ElemMatchValueExpression, MatchesElementSingle ) {
+        BSONObj baseOperand = BSON( "$gt" << 5 );
+        BSONObj match = BSON( "a" << BSON_ARRAY( 6 ) );
+        BSONObj notMatch = BSON( "a" << BSON_ARRAY( 4 ) );
+        auto_ptr<ComparisonExpression> gt( new ComparisonExpression() );
+        ASSERT( gt->init( "", ComparisonExpression::GT, baseOperand[ "$gt" ] ).isOK() );
+        ElemMatchValueExpression op;
+        ASSERT( op.init( "a", gt.release() ).isOK() );
+        ASSERT( op.matchesSingleElement( match[ "a" ] ) );
+        ASSERT( !op.matchesSingleElement( notMatch[ "a" ] ) );
+    }
+
+    TEST( ElemMatchValueExpression, MatchesElementMultiple ) {
+        BSONObj baseOperand1 = BSON( "$gt" << 1 );
+        BSONObj baseOperand2 = BSON( "$lt" << 10 );
+        BSONObj notMatch1 = BSON( "a" << BSON_ARRAY( 0 << 1 ) );
+        BSONObj notMatch2 = BSON( "a" << BSON_ARRAY( 10 << 11 ) );
+        BSONObj match = BSON( "a" << BSON_ARRAY( 0 << 5 << 11 ) );
+        auto_ptr<ComparisonExpression> gt( new ComparisonExpression() );
+        ASSERT( gt->init( "", ComparisonExpression::GT, baseOperand1[ "$gt" ] ).isOK() );
+        auto_ptr<ComparisonExpression> lt( new ComparisonExpression() );
+        ASSERT( lt->init( "", ComparisonExpression::LT, baseOperand2[ "$lt" ] ).isOK() );
+
+        ElemMatchValueExpression op;
+        ASSERT( op.init( "a" ).isOK() );
+        op.add( gt.release() );
+        op.add( lt.release() );
+
+        ASSERT( !op.matchesSingleElement( notMatch1[ "a" ] ) );
+        ASSERT( !op.matchesSingleElement( notMatch2[ "a" ] ) );
+        ASSERT( op.matchesSingleElement( match[ "a" ] ) );
+    }
+
+    TEST( ElemMatchValueExpression, MatchesNonArray ) {
+        BSONObj baseOperand = BSON( "$gt" << 5 );
+        auto_ptr<ComparisonExpression> gt( new ComparisonExpression() );
+        ASSERT( gt->init( "", ComparisonExpression::GT, baseOperand[ "$gt" ] ).isOK() );
+        ElemMatchObjectExpression op;
+        ASSERT( op.init( "a", gt.release() ).isOK() );
+        // Directly nested objects are not matched with $elemMatch.  An intervening array is
+        // required.
+        ASSERT( !op.matches( BSON( "a" << 6 ), NULL ) );
+        ASSERT( !op.matches( BSON( "a" << BSON( "0" << 6 ) ), NULL ) );
+    }
+
+    TEST( ElemMatchValueExpression, MatchesArrayScalar ) {
+        BSONObj baseOperand = BSON( "$gt" << 5 );
+        auto_ptr<ComparisonExpression> gt( new ComparisonExpression() );
+        ASSERT( gt->init( "", ComparisonExpression::GT, baseOperand[ "$gt" ] ).isOK() );
+        ElemMatchValueExpression op;
+        ASSERT( op.init( "a", gt.release() ).isOK() );
+        ASSERT( op.matches( BSON( "a" << BSON_ARRAY( 6 ) ), NULL ) );
+        ASSERT( op.matches( BSON( "a" << BSON_ARRAY( 4 << 6 ) ), NULL ) );
+        ASSERT( op.matches( BSON( "a" << BSON_ARRAY( BSONObj() << 7 ) ), NULL ) );
+    }
+
+    TEST( ElemMatchValueExpression, MatchesMultipleNamedValues ) {
+        BSONObj baseOperand = BSON( "$gt" << 5 );
+        auto_ptr<ComparisonExpression> gt( new ComparisonExpression() );
+        ASSERT( gt->init( "", ComparisonExpression::GT, baseOperand[ "$gt" ] ).isOK() );
+        ElemMatchValueExpression op;
+        ASSERT( op.init( "a.b", gt.release() ).isOK() );
+        ASSERT( op.matches( BSON( "a" << BSON_ARRAY( BSON( "b" << BSON_ARRAY( 6 ) ) ) ), NULL ) );
+        ASSERT( op.matches( BSON( "a" <<
+                                  BSON_ARRAY( BSON( "b" << BSON_ARRAY( 4 ) ) <<
+                                              BSON( "b" << BSON_ARRAY( 4 << 6 ) ) ) ),
+                            NULL ) );
+    }
+
+    TEST( ElemMatchValueExpression, ElemMatchKey ) {
+        BSONObj baseOperand = BSON( "$gt" << 6 );
+        auto_ptr<ComparisonExpression> gt( new ComparisonExpression() );
+        ASSERT( gt->init( "", ComparisonExpression::GT, baseOperand[ "$gt" ] ).isOK() );
+        ElemMatchValueExpression op;
+        ASSERT( op.init( "a.b", gt.release() ).isOK() );
+        MatchDetails details;
+        details.requestElemMatchKey();
+        ASSERT( !op.matches( BSONObj(), &details ) );
+        ASSERT( !details.hasElemMatchKey() );
+        ASSERT( !op.matches( BSON( "a" << BSON( "b" << BSON_ARRAY( 2 ) ) ),
+                             &details ) );
+        ASSERT( !details.hasElemMatchKey() );
+        ASSERT( op.matches( BSON( "a" << BSON( "b" << BSON_ARRAY( 3 << 7 ) ) ),
+                            &details ) );
+        ASSERT( details.hasElemMatchKey() );
+        // The entry within the $elemMatch array is reported.
+        ASSERT_EQUALS( "1", details.elemMatchKey() );
+        ASSERT( op.matches( BSON( "a" <<
+                                  BSON_ARRAY( 1 << 2 <<
+                                              BSON( "b" << BSON_ARRAY( 3 << 7 ) ) ) ),
+                            &details ) );
+        ASSERT( details.hasElemMatchKey() );
+        // The entry within a parent of the $elemMatch array is reported.
+        ASSERT_EQUALS( "2", details.elemMatchKey() );
+    }
+
+    /**
+    TEST( ElemMatchValueExpression, MatchesIndexKey ) {
+        BSONObj baseOperand = BSON( "$lt" << 5 );
+        auto_ptr<LtOp> lt( new ComparisonExpression() );
+        ASSERT( lt->init( "a", baseOperand[ "$lt" ] ).isOK() );
+        ElemMatchValueExpression op;
+        ASSERT( op.init( "a", lt.release() ).isOK() );
+        IndexSpec indexSpec( BSON( "a" << 1 ) );
+        BSONObj indexKey = BSON( "" << "3" );
+        ASSERT( MatchExpression::PartialMatchResult_Unknown ==
+                op.matchesIndexKey( indexKey, indexSpec ) );
+    }
+    */
+
+    TEST( AllElemMatchOp, MatchesElement ) {
+
+
+        BSONObj baseOperanda1 = BSON( "a" << 1 );
+        auto_ptr<ComparisonExpression> eqa1( new ComparisonExpression() );
+        ASSERT( eqa1->init( "a", ComparisonExpression::EQ, baseOperanda1[ "a" ] ).isOK() );
+
+        BSONObj baseOperandb1 = BSON( "b" << 1 );
+        auto_ptr<ComparisonExpression> eqb1( new ComparisonExpression() );
+        ASSERT( eqb1->init( "b", ComparisonExpression::EQ, baseOperandb1[ "b" ] ).isOK() );
+
+        auto_ptr<AndExpression> and1( new AndExpression() );
+        and1->add( eqa1.release() );
+        and1->add( eqb1.release() );
+        // and1 = { a : 1, b : 1 }
+
+        auto_ptr<ElemMatchObjectExpression> elemMatch1( new ElemMatchObjectExpression() );
+        elemMatch1->init( "x", and1.release() );
+        // elemMatch1 = { x : { $elemMatch : { a : 1, b : 1 } } }
+
+        BSONObj baseOperanda2 = BSON( "a" << 2 );
+        auto_ptr<ComparisonExpression> eqa2( new ComparisonExpression() );
+        ASSERT( eqa2->init( "a", ComparisonExpression::EQ, baseOperanda2[ "a" ] ).isOK() );
+
+        BSONObj baseOperandb2 = BSON( "b" << 2 );
+        auto_ptr<ComparisonExpression> eqb2( new ComparisonExpression() );
+        ASSERT( eqb2->init( "b", ComparisonExpression::EQ, baseOperandb2[ "b" ] ).isOK() );
+
+        auto_ptr<AndExpression> and2( new AndExpression() );
+        and2->add( eqa2.release() );
+        and2->add( eqb2.release() );
+
+        auto_ptr<ElemMatchObjectExpression> elemMatch2( new ElemMatchObjectExpression() );
+        elemMatch2->init( "x", and2.release() );
+        // elemMatch2 = { x : { $elemMatch : { a : 2, b : 2 } } }
+
+        AllElemMatchOp op;
+        op.init( "" );
+        op.add( elemMatch1.release() );
+        op.add( elemMatch2.release() );
+
+        BSONObj nonArray = BSON( "x" << 4 );
+        ASSERT( !op.matchesSingleElement( nonArray[ "x" ] ) );
+        BSONObj emptyArray = BSON( "x" << BSONArray() );
+        ASSERT( !op.matchesSingleElement( emptyArray[ "x" ] ) );
+        BSONObj nonObjArray = BSON( "x" << BSON_ARRAY( 4 ) );
+        ASSERT( !op.matchesSingleElement( nonObjArray[ "x" ] ) );
+        BSONObj singleObjMatch = BSON( "x" << BSON_ARRAY( BSON( "a" << 1 << "b" << 1 ) ) );
+        ASSERT( !op.matchesSingleElement( singleObjMatch[ "x" ] ) );
+        BSONObj otherObjMatch = BSON( "x" << BSON_ARRAY( BSON( "a" << 2 << "b" << 2 ) ) );
+        ASSERT( !op.matchesSingleElement( otherObjMatch[ "x" ] ) );
+        BSONObj bothObjMatch = BSON( "x" << BSON_ARRAY( BSON( "a" << 1 << "b" << 1 ) <<
+                                                        BSON( "a" << 2 << "b" << 2 ) ) );
+        ASSERT( op.matchesSingleElement( bothObjMatch[ "x" ] ) );
+        BSONObj noObjMatch = BSON( "x" << BSON_ARRAY( BSON( "a" << 1 << "b" << 2 ) <<
+                                                      BSON( "a" << 2 << "b" << 1 ) ) );
+        ASSERT( !op.matchesSingleElement( noObjMatch[ "x" ] ) );
+    }
+
+
+    TEST( AllElemMatchOp, Matches ) {
+        BSONObj baseOperandgt1 = BSON( "$gt" << 1 );
+        auto_ptr<ComparisonExpression> gt1( new ComparisonExpression() );
+        ASSERT( gt1->init( "", ComparisonExpression::GT, baseOperandgt1[ "$gt" ] ).isOK() );
+
+        BSONObj baseOperandlt1 = BSON( "$lt" << 10 );
+        auto_ptr<ComparisonExpression> lt1( new ComparisonExpression() );
+        ASSERT( lt1->init( "", ComparisonExpression::LT, baseOperandlt1[ "$lt" ] ).isOK() );
+
+        auto_ptr<ElemMatchValueExpression> elemMatch1( new ElemMatchValueExpression() );
+        elemMatch1->init( "x" );
+        elemMatch1->add( gt1.release() );
+        elemMatch1->add( lt1.release() );
+
+        BSONObj baseOperandgt2 = BSON( "$gt" << 101 );
+        auto_ptr<ComparisonExpression> gt2( new ComparisonExpression() );
+        ASSERT( gt2->init( "", ComparisonExpression::GT, baseOperandgt2[ "$gt" ] ).isOK() );
+
+        BSONObj baseOperandlt2 = BSON( "$lt" << 110 );
+        auto_ptr<ComparisonExpression> lt2( new ComparisonExpression() );
+        ASSERT( lt2->init( "", ComparisonExpression::LT, baseOperandlt2[ "$lt" ] ).isOK() );
+
+        auto_ptr<ElemMatchValueExpression> elemMatch2( new ElemMatchValueExpression() );
+        elemMatch2->init( "x" );
+        elemMatch2->add( gt2.release() );
+        elemMatch2->add( lt2.release() );
+
+        AllElemMatchOp op;
+        op.init( "x" );
+        op.add( elemMatch1.release() );
+        op.add( elemMatch2.release() );
+
+
+        BSONObj nonArray = BSON( "x" << 4 );
+        ASSERT( !op.matches( nonArray, NULL ) );
+        BSONObj emptyArray = BSON( "x" << BSONArray() );
+        ASSERT( !op.matches( emptyArray, NULL ) );
+        BSONObj nonNumberArray = BSON( "x" << BSON_ARRAY( "q" ) );
+        ASSERT( !op.matches( nonNumberArray, NULL ) );
+        BSONObj singleMatch = BSON( "x" << BSON_ARRAY( 5 ) );
+        ASSERT( !op.matches( singleMatch, NULL ) );
+        BSONObj otherMatch = BSON( "x" << BSON_ARRAY( 105 ) );
+        ASSERT( !op.matches( otherMatch, NULL ) );
+        BSONObj bothMatch = BSON( "x" << BSON_ARRAY( 5 << 105 ) );
+        ASSERT( op.matches( bothMatch, NULL ) );
+        BSONObj neitherMatch = BSON( "x" << BSON_ARRAY( 0 << 200 ) );
+        ASSERT( !op.matches( neitherMatch, NULL ) );
+    }
+
+    /**
+    TEST( AllElemMatchOp, MatchesIndexKey ) {
+        BSONObj baseOperand = BSON( "$lt" << 5 );
+        auto_ptr<LtOp> lt( new ComparisonExpression() );
+        ASSERT( lt->init( "a", baseOperand[ "$lt" ] ).isOK() );
+        auto_ptr<ElemMatchValueExpression> elemMatchValueOp( new ElemMatchValueExpression() );
+        ASSERT( elemMatchValueOp->init( "a", lt.release() ).isOK() );
+        OwnedPointerVector<MatchExpression> subExpressions;
+        subExpressions.mutableVector().push_back( elemMatchValueOp.release() );
+        AllElemMatchOp allElemMatchOp;
+        ASSERT( allElemMatchOp.init( &subExpressions ).isOK() );
+        IndexSpec indexSpec( BSON( "a" << 1 ) );
+        BSONObj indexKey = BSON( "" << "3" );
+        ASSERT( MatchExpression::PartialMatchResult_Unknown ==
+                allElemMatchOp.matchesIndexKey( indexKey, indexSpec ) );
+    }
+    */
+
+    TEST( SizeExpression, MatchesElement ) {
+        BSONObj match = BSON( "a" << BSON_ARRAY( 5 << 6 ) );
+        BSONObj notMatch = BSON( "a" << BSON_ARRAY( 5 ) );
+        SizeExpression size;
+        ASSERT( size.init( "", 2 ).isOK() );
+        ASSERT( size.matchesSingleElement( match.firstElement() ) );
+        ASSERT( !size.matchesSingleElement( notMatch.firstElement() ) );
+    }
+
+    TEST( SizeExpression, MatchesNonArray ) {
+        // Non arrays do not match.
+        BSONObj stringValue = BSON( "a" << "z" );
+        BSONObj numberValue = BSON( "a" << 0 );
+        BSONObj arrayValue = BSON( "a" << BSONArray() );
+        SizeExpression size;
+        ASSERT( size.init( "", 0 ).isOK() );
+        ASSERT( !size.matchesSingleElement( stringValue.firstElement() ) );
+        ASSERT( !size.matchesSingleElement( numberValue.firstElement() ) );
+        ASSERT( size.matchesSingleElement( arrayValue.firstElement() ) );
+    }
+
+    TEST( SizeExpression, MatchesArray ) {
+        SizeExpression size;
+        ASSERT( size.init( "a", 2 ).isOK() );
+        ASSERT( size.matches( BSON( "a" << BSON_ARRAY( 4 << 5.5 ) ), NULL ) );
+        // Arrays are not unwound to look for matching subarrays.
+        ASSERT( !size.matches( BSON( "a" << BSON_ARRAY( 4 << 5.5 << BSON_ARRAY( 1 << 2 ) ) ),
+                               NULL ) );
+    }
+
+    TEST( SizeExpression, MatchesNestedArray ) {
+        SizeExpression size;
+        ASSERT( size.init( "a.2", 2 ).isOK() );
+        // A numerically referenced nested array is matched.
+        ASSERT( size.matches( BSON( "a" << BSON_ARRAY( 4 << 5.5 << BSON_ARRAY( 1 << 2 ) ) ),
+                              NULL ) );
+    }
+
+    TEST( SizeExpression, ElemMatchKey ) {
+        SizeExpression size;
+        ASSERT( size.init( "a.b", 3 ).isOK() );
+        MatchDetails details;
+        details.requestElemMatchKey();
+        ASSERT( !size.matches( BSON( "a" << 1 ), &details ) );
+        ASSERT( !details.hasElemMatchKey() );
+        ASSERT( size.matches( BSON( "a" << BSON( "b" << BSON_ARRAY( 1 << 2 << 3 ) ) ), &details ) );
+        ASSERT( !details.hasElemMatchKey() );
+        ASSERT( size.matches( BSON( "a" <<
+                                    BSON_ARRAY( 2 <<
+                                                BSON( "b" << BSON_ARRAY( 1 << 2 << 3 ) ) ) ),
+                              &details ) );
+        ASSERT( details.hasElemMatchKey() );
+        ASSERT_EQUALS( "1", details.elemMatchKey() );
+    }
+
+    /**
+       TEST( SizeExpression, MatchesIndexKey ) {
+       BSONObj operand = BSON( "$size" << 4 );
+       SizeExpression size;
+       ASSERT( size.init( "a", operand[ "$size" ] ).isOK() );
+       IndexSpec indexSpec( BSON( "a" << 1 ) );
+       BSONObj indexKey = BSON( "" << 1 );
+       ASSERT( MatchExpression::PartialMatchResult_Unknown ==
+       size.matchesIndexKey( indexKey, indexSpec ) );
+       }
+    */
+
+} // namespace mongo
diff --git a/src/mongo/db/matcher/expression_internal.cpp b/src/mongo/db/matcher/expression_internal.cpp
new file mode 100644
index 00000000000..323549f8dda
--- /dev/null
+++ b/src/mongo/db/matcher/expression_internal.cpp
@@ -0,0 +1,94 @@
+// expression_internal.h
+
+/**
+ *    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/>.
+ */
+
+#include "mongo/db/matcher/expression_internal.h"
+
+namespace mongo {
+
+    bool isAllDigits( const StringData& str ) {
+        for ( unsigned i = 0; i < str.size(); i++ ) {
+            if ( !isdigit( str[i] ) )
+                return false;
+        }
+        return true;
+    }
+
+    string pathToString( const FieldRef& path, int32_t size ) {
+        string res;
+        if ( (size_t)size > path.numParts() ) {
+            return res;
+        }
+
+        res = path.getPart( size ).toString();
+        for (size_t i = (size_t)size + 1; i < path.numParts(); i++ ) {
+            res += ".";
+            res += path.getPart( i ).toString();
+        }
+        return res;
+    }
+
+    BSONElement getFieldDottedOrArray( const BSONObj& doc,
+                                       const FieldRef& path,
+                                       int32_t* idxPath,
+                                       bool* inArray )  {
+        BSONElement res;
+
+        BSONObj curr = doc;
+        bool stop = false;
+        size_t partNum = 0;
+        while ( partNum < path.numParts() && !stop ) {
+
+            res = curr.getField( path.getPart( partNum ) );
+
+            switch ( res.type() ) {
+
+            case EOO:
+                stop = true;
+                break;
+
+            case Object:
+                curr = res.Obj();
+                ++partNum;
+                break;
+
+            case Array:
+                if ( partNum+1 < path.numParts() && isAllDigits( path.getPart( partNum+1 ) ) ) {
+                    *inArray = true;
+                    curr = res.Obj();
+                    ++partNum;
+                }
+                else {
+                    stop = true;
+                }
+                break;
+
+            default:
+                if ( partNum+1 < path.numParts() ) {
+                    res = BSONElement();
+                }
+                stop = true;
+
+            }
+        }
+
+        *idxPath = partNum;
+        return res;
+    }
+
+
+}  // namespace mongo
diff --git a/src/mongo/db/matcher/expression_internal.h b/src/mongo/db/matcher/expression_internal.h
new file mode 100644
index 00000000000..05486fd78e5
--- /dev/null
+++ b/src/mongo/db/matcher/expression_internal.h
@@ -0,0 +1,38 @@
+// expression_internal.h
+
+/**
+ *    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/>.
+ */
+
+#pragma once
+
+#include "mongo/base/string_data.h"
+#include "mongo/db/field_ref.h"
+#include "mongo/db/jsobj.h"
+#include "mongo/platform/cstdint.h"
+
+namespace mongo {
+
+    // XXX document me
+    string pathToString( const FieldRef& path, int32_t size );
+
+    // XXX document me
+    // Replaces getFieldDottedOrArray without recursion nor string manipulation
+    BSONElement getFieldDottedOrArray( const BSONObj& doc,
+                                       const FieldRef& path,
+                                       int32_t* idxPath,
+                                       bool* inArray );
+
+}  // namespace mongo
diff --git a/src/mongo/db/matcher/expression_leaf.cpp b/src/mongo/db/matcher/expression_leaf.cpp
new file mode 100644
index 00000000000..fdbf50c9922
--- /dev/null
+++ b/src/mongo/db/matcher/expression_leaf.cpp
@@ -0,0 +1,398 @@
+// expression_leaf.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/>.
+ */
+
+#include "mongo/db/matcher/expression_leaf.h"
+
+#include "mongo/bson/bsonobjiterator.h"
+#include "mongo/bson/bsonobj.h"
+#include "mongo/bson/bsonmisc.h"
+#include "mongo/db/field_ref.h"
+#include "mongo/db/matcher.h"
+#include "mongo/db/matcher/expression_internal.h"
+#include "mongo/util/log.h"
+
+namespace mongo {
+
+    bool LeafExpression::matches( const BSONObj& doc, MatchDetails* details ) const {
+        //log() << "e doc: " << doc << " path: " << _path << std::endl;
+
+        FieldRef path;
+        path.parse(_path);
+
+        bool traversedArray = false;
+        int32_t idxPath = 0;
+        BSONElement e = getFieldDottedOrArray( doc, path, &idxPath, &traversedArray );
+
+        string rest = pathToString( path, idxPath+1 );
+
+        if ( e.type() != Array || traversedArray ) {
+            return matchesSingleElement( e );
+        }
+
+        BSONObjIterator i( e.Obj() );
+        while ( i.more() ) {
+            BSONElement x = i.next();
+            bool found = false;
+            if ( rest.size() == 0 ) {
+                found = matchesSingleElement( x );
+            }
+            else if ( x.isABSONObj() ) {
+                BSONElement y = x.Obj().getField( rest );
+                found = matchesSingleElement( y );
+            }
+
+            if ( found ) {
+                if ( !_allHaveToMatch ) {
+                    if ( details && details->needRecord() ) {
+                        // this block doesn't have to be inside the _allHaveToMatch handler
+                        // but this matches the old semantics
+                        details->setElemMatchKey( x.fieldName() );
+                    }
+                    return true;
+                }
+            }
+            else if ( _allHaveToMatch ) {
+                return false;
+            }
+        }
+
+        return matchesSingleElement( e );
+    }
+
+    // -------------
+
+    Status ComparisonExpression::init( const StringData& path, Type type, const BSONElement& rhs ) {
+        _path = path;
+        _type = type;
+        _rhs = rhs;
+        if ( rhs.eoo() ) {
+            return Status( ErrorCodes::BadValue, "need a real operand" );
+        }
+
+        _allHaveToMatch = _type == NE;
+
+        return Status::OK();
+    }
+
+
+    bool ComparisonExpression::matchesSingleElement( const BSONElement& e ) const {
+        //log() << "\t ComparisonExpression e: " << e << " _rhs: " << _rhs << std::endl;
+
+        if ( e.canonicalType() != _rhs.canonicalType() ) {
+            // some special cases
+            //  jstNULL and undefined are treated the same
+            if ( e.canonicalType() + _rhs.canonicalType() == 5 ) {
+                return _type == EQ || _type == LTE || _type == GTE;
+            }
+            return _invertForNE( false );
+        }
+
+        if ( _rhs.type() == Array ) {
+            if ( _type != EQ && _type != NE ) {
+                return false;
+            }
+        }
+
+        int x = compareElementValues( e, _rhs );
+
+        switch ( _type ) {
+        case LT:
+            return x < 0;
+        case LTE:
+            return x <= 0;
+        case EQ:
+            return x == 0;
+        case GT:
+            return x > 0;
+        case GTE:
+            return x >= 0;
+        case NE:
+            return x != 0;
+        }
+        throw 1;
+    }
+
+    bool ComparisonExpression::_invertForNE( bool normal ) const {
+        if ( _type == NE )
+            return !normal;
+        return normal;
+    }
+
+    void ComparisonExpression::debugString( StringBuilder& debug, int level ) const {
+        _debugAddSpace( debug, level );
+        debug << _path << " ";
+        switch ( _type ) {
+        case LT: debug << "$lt"; break;
+        case LTE: debug << "$lte"; break;
+        case EQ: debug << "=="; break;
+        case GT: debug << "$gt"; break;
+        case GTE: debug << "$gte"; break;
+        case NE: debug << "$ne"; break;
+        }
+        debug << " " << _rhs.toString( false ) << "\n";
+    }
+
+    // ---------------
+
+    // TODO: move
+    inline pcrecpp::RE_Options flags2options(const char* flags) {
+        pcrecpp::RE_Options options;
+        options.set_utf8(true);
+        while ( flags && *flags ) {
+            if ( *flags == 'i' )
+                options.set_caseless(true);
+            else if ( *flags == 'm' )
+                options.set_multiline(true);
+            else if ( *flags == 'x' )
+                options.set_extended(true);
+            else if ( *flags == 's' )
+                options.set_dotall(true);
+            flags++;
+        }
+        return options;
+    }
+
+    Status RegexExpression::init( const StringData& path, const BSONElement& e ) {
+        if ( e.type() != RegEx )
+            return Status( ErrorCodes::BadValue, "regex not a regex" );
+        return init( path, e.regex(), e.regexFlags() );
+    }
+
+
+    Status RegexExpression::init( const StringData& path, const StringData& regex, const StringData& options ) {
+        _path = path;
+
+        if ( regex.size() > RegexMatcher::MaxPatternSize ) {
+            return Status( ErrorCodes::BadValue, "Regular expression is too long" );
+        }
+
+        _regex = regex.toString();
+        _flags = options.toString();
+        _re.reset( new pcrecpp::RE( _regex.c_str(), flags2options( _flags.c_str() ) ) );
+        return Status::OK();
+    }
+
+    bool RegexExpression::matchesSingleElement( const BSONElement& e ) const {
+        //log() << "RegexExpression::matchesSingleElement _regex: " << _regex << " e: " << e << std::endl;
+        switch (e.type()) {
+        case String:
+        case Symbol:
+            //if (rm._prefix.empty())
+                return _re->PartialMatch(e.valuestr());
+                //else
+                //return !strncmp(e.valuestr(), rm._prefix.c_str(), rm._prefix.size());
+        case RegEx:
+            return _regex == e.regex() && _flags == e.regexFlags();
+        default:
+            return false;
+        }
+    }
+
+    void RegexExpression::debugString( StringBuilder& debug, int level ) const {
+        _debugAddSpace( debug, level );
+        debug << _path << " regex /" << _regex << "/" << _flags << "\n";
+    }
+
+    // ---------
+
+    Status ModExpression::init( const StringData& path, int divisor, int remainder ) {
+        _path = path;
+        if ( divisor == 0 )
+            return Status( ErrorCodes::BadValue, "divisor cannot be 0" );
+        _divisor = divisor;
+        _remainder = remainder;
+        return Status::OK();
+    }
+
+    bool ModExpression::matchesSingleElement( const BSONElement& e ) const {
+        if ( !e.isNumber() )
+            return false;
+        return e.numberLong() % _divisor == _remainder;
+    }
+
+    void ModExpression::debugString( StringBuilder& debug, int level ) const {
+        _debugAddSpace( debug, level );
+        debug << _path << " mod " << _divisor << " % x == "  << _remainder << "\n";
+    }
+
+
+    // ------------------
+
+    Status ExistsExpression::init( const StringData& path, bool exists ) {
+        _path = path;
+        _exists = exists;
+        return Status::OK();
+    }
+
+    bool ExistsExpression::matchesSingleElement( const BSONElement& e ) const {
+        if ( e.eoo() ) {
+            return !_exists;
+        }
+        return _exists;
+    }
+
+    void ExistsExpression::debugString( StringBuilder& debug, int level ) const {
+        _debugAddSpace( debug, level );
+        debug << _path << " exists: " << _exists << "\n";
+    }
+
+    // ----
+
+    Status TypeExpression::init( const StringData& path, int type ) {
+        _path = path;
+        _type = type;
+        return Status::OK();
+    }
+
+    bool TypeExpression::matchesSingleElement( const BSONElement& e ) const {
+        return e.type() == _type;
+    }
+
+    bool TypeExpression::matches( const BSONObj& doc, MatchDetails* details ) const {
+        return _matches( _path, doc, details );
+    }
+
+    bool TypeExpression::_matches( const StringData& path, const BSONObj& doc, MatchDetails* details ) const {
+
+        FieldRef pathRef;
+        pathRef.parse(path);
+
+        bool traversedArray = false;
+        int32_t idxPath = 0;
+        BSONElement e = getFieldDottedOrArray( doc, pathRef, &idxPath, &traversedArray );
+
+        string rest = pathToString( pathRef, idxPath+1 );
+
+        if ( e.type() != Array ) {
+            return matchesSingleElement( e );
+        }
+
+        BSONObjIterator i( e.Obj() );
+        while ( i.more() ) {
+            BSONElement x = i.next();
+            bool found = false;
+            if ( rest.size() == 0 ) {
+                found = matchesSingleElement( x );
+            }
+            else if ( x.isABSONObj() ) {
+                found = _matches( rest, x.Obj(), details );
+            }
+
+            if ( found ) {
+                if ( details && details->needRecord() ) {
+                    // this block doesn't have to be inside the _allHaveToMatch handler
+                    // but this matches the old semantics
+                    details->setElemMatchKey( x.fieldName() );
+                }
+                return true;
+            }
+        }
+
+        return false;
+    }
+
+    void TypeExpression::debugString( StringBuilder& debug, int level ) const {
+        _debugAddSpace( debug, level );
+        debug << _path << " type: " << _type << "\n";
+    }
+
+
+    // --------
+
+    ArrayFilterEntries::ArrayFilterEntries(){
+        _hasNull = false;
+    }
+
+    ArrayFilterEntries::~ArrayFilterEntries() {
+        for ( unsigned i = 0; i < _regexes.size(); i++ )
+            delete _regexes[i];
+        _regexes.clear();
+    }
+
+    Status ArrayFilterEntries::addEquality( const BSONElement& e ) {
+        if ( e.isABSONObj() ) {
+            if ( e.Obj().firstElement().fieldName()[0] == '$' )
+                return Status( ErrorCodes::BadValue, "cannot next $ under $in" );
+        }
+
+        if ( e.type() == RegEx )
+            return Status( ErrorCodes::BadValue, "ArrayFilterEntries equality cannot be a regex" );
+
+        if ( e.type() == jstNULL ) {
+            _hasNull = true;
+        }
+
+        _equalities.insert( e );
+        return Status::OK();
+    }
+
+    Status ArrayFilterEntries::addRegex( RegexExpression* expr ) {
+        _regexes.push_back( expr );
+        return Status::OK();
+    }
+
+    // -----------
+
+    void InExpression::init( const StringData& path ) {
+        _path = path;
+        _allHaveToMatch = false;
+    }
+
+
+    bool InExpression::matchesSingleElement( const BSONElement& e ) const {
+        if ( _arrayEntries.hasNull() && e.eoo() )
+            return true;
+
+        if ( _arrayEntries.contains( e ) )
+            return true;
+
+        for ( unsigned i = 0; i < _arrayEntries.numRegexes(); i++ ) {
+            if ( _arrayEntries.regex(i)->matchesSingleElement( e ) )
+                return true;
+        }
+
+        return false;
+    }
+
+    void InExpression::debugString( StringBuilder& debug, int level ) const {
+        _debugAddSpace( debug, level );
+        debug << _path << " $in: TODO\n";
+    }
+
+
+    // ----------
+
+    void NinExpression::init( const StringData& path ) {
+        _path = path;
+        _allHaveToMatch = true;
+    }
+
+
+    bool NinExpression::matchesSingleElement( const BSONElement& e ) const {
+        return !_in.matchesSingleElement( e );
+    }
+
+
+    void NinExpression::debugString( StringBuilder& debug, int level ) const {
+        _debugAddSpace( debug, level );
+        debug << _path << " $nin: TODO\n";
+    }
+
+}
+
+
diff --git a/src/mongo/db/matcher/expression_leaf.h b/src/mongo/db/matcher/expression_leaf.h
new file mode 100644
index 00000000000..1b836366754
--- /dev/null
+++ b/src/mongo/db/matcher/expression_leaf.h
@@ -0,0 +1,184 @@
+// expression_leaf.h
+
+/**
+ *    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/>.
+ */
+
+#pragma once
+
+#include <pcrecpp.h>
+
+#include <boost/scoped_ptr.hpp>
+
+#include "mongo/bson/bsonobj.h"
+#include "mongo/bson/bsonmisc.h"
+#include "mongo/db/matcher/expression.h"
+
+namespace mongo {
+
+    class LeafExpression : public Expression {
+    public:
+        LeafExpression() {
+            _allHaveToMatch = false;
+        }
+
+        virtual ~LeafExpression(){}
+
+        virtual bool matches( const BSONObj& doc, MatchDetails* details = 0 ) const;
+
+        virtual bool matchesSingleElement( const BSONElement& e ) const = 0;
+    protected:
+        StringData _path;
+        bool _allHaveToMatch;
+    };
+
+    // -----
+
+    class ComparisonExpression : public LeafExpression {
+    public:
+        enum Type { LTE, LT, EQ, GT, GTE, NE };
+
+        Status init( const StringData& path, Type type, const BSONElement& rhs );
+
+        virtual ~ComparisonExpression(){}
+
+        virtual Type getType() const { return _type; }
+
+        virtual bool matchesSingleElement( const BSONElement& e ) const;
+
+        virtual void debugString( StringBuilder& debug, int level = 0 ) const;
+    protected:
+        bool _invertForNE( bool normal ) const;
+
+    private:
+        Type _type;
+        BSONElement _rhs;
+    };
+
+    class RegexExpression : public LeafExpression {
+    public:
+        Status init( const StringData& path, const StringData& regex, const StringData& options );
+        Status init( const StringData& path, const BSONElement& e );
+
+        virtual bool matchesSingleElement( const BSONElement& e ) const;
+
+        virtual void debugString( StringBuilder& debug, int level ) const;
+    private:
+        std::string _regex;
+        std::string _flags;
+        boost::scoped_ptr<pcrecpp::RE> _re;
+    };
+
+    class ModExpression : public LeafExpression {
+    public:
+        Status init( const StringData& path, int divisor, int remainder );
+
+        virtual bool matchesSingleElement( const BSONElement& e ) const;
+
+        virtual void debugString( StringBuilder& debug, int level ) const;
+    private:
+        int _divisor;
+        int _remainder;
+    };
+
+    class ExistsExpression : public LeafExpression {
+    public:
+        Status init( const StringData& path, bool exists );
+
+        virtual bool matchesSingleElement( const BSONElement& e ) const;
+
+        virtual void debugString( StringBuilder& debug, int level ) const;
+    private:
+        bool _exists;
+    };
+
+    class TypeExpression : public Expression {
+    public:
+        Status init( const StringData& path, int type );
+
+        virtual bool matchesSingleElement( const BSONElement& e ) const;
+
+        virtual bool matches( const BSONObj& doc, MatchDetails* details = 0 ) const;
+
+        virtual void debugString( StringBuilder& debug, int level ) const;
+    private:
+        bool _matches( const StringData& path, const BSONObj& doc, MatchDetails* details = 0 ) const;
+
+        StringData _path;
+        int _type;
+    };
+
+    /**
+     * INTERNAL
+     * terrible name
+     * holds the entries of an $in or $all
+     * either scalars or regex
+     */
+    class ArrayFilterEntries {
+        MONGO_DISALLOW_COPYING( ArrayFilterEntries );
+    public:
+        ArrayFilterEntries();
+        ~ArrayFilterEntries();
+
+        Status addEquality( const BSONElement& e );
+        Status addRegex( RegexExpression* expr );
+
+        const BSONElementSet& equalities() const { return _equalities; }
+        bool contains( const BSONElement& elem ) const { return _equalities.count(elem) > 0; }
+
+        size_t numRegexes() const { return _regexes.size(); }
+        RegexExpression* regex( int idx ) const { return _regexes[idx]; }
+
+        bool hasNull() const { return _hasNull; }
+        bool singleNull() const { return size() == 1 && _hasNull; }
+        int size() const { return _equalities.size() + _regexes.size(); }
+
+    private:
+        bool _hasNull; // if _equalities has a jstNULL element in it
+        BSONElementSet _equalities;
+        std::vector<RegexExpression*> _regexes;
+    };
+
+
+    /**
+     * query operator: $in
+     */
+    class InExpression : public LeafExpression {
+    public:
+        void init( const StringData& path );
+        ArrayFilterEntries* getArrayFilterEntries() { return &_arrayEntries; }
+
+        virtual bool matchesSingleElement( const BSONElement& e ) const;
+
+        virtual void debugString( StringBuilder& debug, int level ) const;
+    private:
+        ArrayFilterEntries _arrayEntries;
+    };
+
+    class NinExpression : public LeafExpression {
+    public:
+        void init( const StringData& path );
+        ArrayFilterEntries* getArrayFilterEntries() { return _in.getArrayFilterEntries(); }
+
+        virtual bool matchesSingleElement( const BSONElement& e ) const;
+
+        virtual void debugString( StringBuilder& debug, int level ) const;
+    private:
+        InExpression _in;
+    };
+
+
+
+}
diff --git a/src/mongo/db/matcher/expression_leaf_test.cpp b/src/mongo/db/matcher/expression_leaf_test.cpp
new file mode 100644
index 00000000000..9f11fad8c5e
--- /dev/null
+++ b/src/mongo/db/matcher/expression_leaf_test.cpp
@@ -0,0 +1,1567 @@
+/**
+ *    Copyright (C) 2012 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/>.
+ */
+
+/** Unit tests for MatchExpression operator implementations in match_operators.{h,cpp}. */
+
+#include "mongo/unittest/unittest.h"
+
+#include "mongo/db/jsobj.h"
+#include "mongo/db/json.h"
+#include "mongo/db/matcher.h"
+#include "mongo/db/matcher/expression.h"
+#include "mongo/db/matcher/expression_leaf.h"
+
+namespace mongo {
+
+    TEST( EqOp, MatchesElement ) {
+        BSONObj operand = BSON( "a" << 5 );
+        BSONObj match = BSON( "a" << 5.0 );
+        BSONObj notMatch = BSON( "a" << 6 );
+
+        ComparisonExpression eq;
+        eq.init( "", ComparisonExpression::EQ, operand["a"] );
+        ASSERT( eq.matchesSingleElement( match.firstElement() ) );
+        ASSERT( !eq.matchesSingleElement( notMatch.firstElement() ) );
+    }
+
+
+    TEST( EqOp, InvalidEooOperand ) {
+        BSONObj operand;
+        ComparisonExpression eq;
+        ASSERT( !eq.init( "", ComparisonExpression::EQ, operand.firstElement() ).isOK() );
+    }
+
+    TEST( EqOp, MatchesScalar ) {
+        BSONObj operand = BSON( "a" << 5 );
+        ComparisonExpression eq;
+        eq.init( "a", ComparisonExpression::EQ, operand[ "a" ] );
+        ASSERT( eq.matches( BSON( "a" << 5.0 ), NULL ) );
+        ASSERT( !eq.matches( BSON( "a" << 4 ), NULL ) );
+    }
+
+    TEST( EqOp, MatchesArrayValue ) {
+        BSONObj operand = BSON( "a" << 5 );
+        ComparisonExpression eq;
+        eq.init( "a", ComparisonExpression::EQ, operand[ "a" ] );
+        ASSERT( eq.matches( BSON( "a" << BSON_ARRAY( 5.0 << 6 ) ), NULL ) );
+        ASSERT( !eq.matches( BSON( "a" << BSON_ARRAY( 6 << 7 ) ), NULL ) );
+    }
+
+    TEST( EqOp, MatchesReferencedObjectValue ) {
+        BSONObj operand = BSON( "a.b" << 5 );
+        ComparisonExpression eq;
+        eq.init( "a.b", ComparisonExpression::EQ, operand[ "a.b" ] );
+        ASSERT( eq.matches( BSON( "a" << BSON( "b" << 5 ) ), NULL ) );
+        ASSERT( eq.matches( BSON( "a" << BSON( "b" << BSON_ARRAY( 5 ) ) ), NULL ) );
+        ASSERT( eq.matches( BSON( "a" << BSON_ARRAY( BSON( "b" << 5 ) ) ), NULL ) );
+    }
+
+    TEST( EqOp, MatchesReferencedArrayValue ) {
+        BSONObj operand = BSON( "a.0" << 5 );
+        ComparisonExpression eq;
+        eq.init( "a.0", ComparisonExpression::EQ, operand[ "a.0" ] );
+        ASSERT( eq.matches( BSON( "a" << BSON_ARRAY( 5 ) ), NULL ) );
+        ASSERT( !eq.matches( BSON( "a" << BSON_ARRAY( BSON_ARRAY( 5 ) ) ), NULL ) );
+    }
+
+    TEST( EqOp, MatchesNull ) {
+        BSONObj operand = BSON( "a" << BSONNULL );
+        ComparisonExpression eq;
+        eq.init( "a", ComparisonExpression::EQ, operand[ "a" ] );
+        ASSERT( eq.matches( BSONObj(), NULL ) );
+        ASSERT( eq.matches( BSON( "a" << BSONNULL ), NULL ) );
+        ASSERT( !eq.matches( BSON( "a" << 4 ), NULL ) );
+    }
+
+    TEST( EqOp, MatchesMinKey ) {
+        BSONObj operand = BSON( "a" << MinKey );
+        ComparisonExpression eq;
+        eq.init( "a", ComparisonExpression::EQ, operand[ "a" ] );
+        ASSERT( eq.matches( BSON( "a" << MinKey ), NULL ) );
+        ASSERT( !eq.matches( BSON( "a" << MaxKey ), NULL ) );
+        ASSERT( !eq.matches( BSON( "a" << 4 ), NULL ) );
+    }
+
+
+
+    TEST( EqOp, MatchesMaxKey ) {
+        BSONObj operand = BSON( "a" << MaxKey );
+        ComparisonExpression eq;
+        ASSERT( eq.init( "a", ComparisonExpression::EQ, operand[ "a" ] ).isOK() );
+        ASSERT( eq.matches( BSON( "a" << MaxKey ), NULL ) );
+        ASSERT( !eq.matches( BSON( "a" << MinKey ), NULL ) );
+        ASSERT( !eq.matches( BSON( "a" << 4 ), NULL ) );
+    }
+
+    TEST( EqOp, MatchesFullArray ) {
+        BSONObj operand = BSON( "a" << BSON_ARRAY( 1 << 2 ) );
+        ComparisonExpression eq;
+        ASSERT( eq.init( "a", ComparisonExpression::EQ, operand[ "a" ] ).isOK() );
+        ASSERT( eq.matches( BSON( "a" << BSON_ARRAY( 1 << 2 ) ), NULL ) );
+        ASSERT( !eq.matches( BSON( "a" << BSON_ARRAY( 1 << 2 << 3 ) ), NULL ) );
+        ASSERT( !eq.matches( BSON( "a" << BSON_ARRAY( 1 ) ), NULL ) );
+        ASSERT( !eq.matches( BSON( "a" << 1 ), NULL ) );
+    }
+
+    TEST( EqOp, ElemMatchKey ) {
+        BSONObj operand = BSON( "a" << 5 );
+        ComparisonExpression eq;
+        ASSERT( eq.init( "a", ComparisonExpression::EQ, operand[ "a" ] ).isOK() );
+        MatchDetails details;
+        details.requestElemMatchKey();
+        ASSERT( !eq.matches( BSON( "a" << 4 ), &details ) );
+        ASSERT( !details.hasElemMatchKey() );
+        ASSERT( eq.matches( BSON( "a" << 5 ), &details ) );
+        ASSERT( !details.hasElemMatchKey() );
+        ASSERT( eq.matches( BSON( "a" << BSON_ARRAY( 1 << 2 << 5 ) ), &details ) );
+        ASSERT( details.hasElemMatchKey() );
+        ASSERT_EQUALS( "2", details.elemMatchKey() );
+    }
+
+    /**
+       TEST( EqOp, MatchesIndexKeyScalar ) {
+       BSONObj operand = BSON( "a" << 6 );
+       ComparisonExpression eq;
+       ASSERT( eq.init( "a", ComparisonExpression::EQ, operand[ "a" ] ).isOK() );
+       IndexSpec indexSpec( BSON( "a" << 1 ) );
+       ASSERT( MatchExpression::PartialMatchResult_True ==
+       eq.matchesIndexKey( BSON( "" << 6 ), indexSpec ) );
+       ASSERT( MatchExpression::PartialMatchResult_False ==
+       eq.matchesIndexKey( BSON( "" << 4 ), indexSpec ) );
+       ASSERT( MatchExpression::PartialMatchResult_False ==
+       eq.matchesIndexKey( BSON( "" << BSON_ARRAY( 6 ) ), indexSpec ) );
+       }
+
+       TEST( EqOp, MatchesIndexKeyMissing ) {
+       BSONObj operand = BSON( "a" << 6 );
+       ComparisonExpression eq;
+       ASSERT( eq.init( "a", ComparisonExpression::EQ, operand[ "a" ] ).isOK() );
+       IndexSpec indexSpec( BSON( "b" << 1 ) );
+       ASSERT( MatchExpression::PartialMatchResult_Unknown ==
+       eq.matchesIndexKey( BSON( "" << 6 ), indexSpec ) );
+       ASSERT( MatchExpression::PartialMatchResult_Unknown ==
+       eq.matchesIndexKey( BSON( "" << 4 ), indexSpec ) );
+       ASSERT( MatchExpression::PartialMatchResult_Unknown ==
+       eq.matchesIndexKey( BSON( "" << BSON_ARRAY( 8 << 6 ) ), indexSpec ) );
+       }
+
+       TEST( EqOp, MatchesIndexKeyArray ) {
+       BSONObj operand = BSON( "a" << BSON_ARRAY( 4 << 5 ) );
+       ComparisonExpression eq
+       ASSERT( eq.init( "a", operand[ "a" ] ).isOK() );
+       IndexSpec indexSpec( BSON( "a" << 1 ) );
+       ASSERT( MatchExpression::PartialMatchResult_Unknown ==
+       eq.matchesIndexKey( BSON( "" << 4 ), indexSpec ) );
+       }
+
+       TEST( EqOp, MatchesIndexKeyArrayValue ) {
+       BSONObj operand = BSON( "a" << 6 );
+       ComparisonExpression eq
+       ASSERT( eq.init( "a", operand[ "a" ] ).isOK() );
+       IndexSpec indexSpec( BSON( "loc" << "mockarrayvalue" << "a" << 1 ) );
+       ASSERT( MatchExpression::PartialMatchResult_True ==
+       eq.matchesIndexKey( BSON( "" << "dummygeohash" << "" << 6 ), indexSpec ) );
+       ASSERT( MatchExpression::PartialMatchResult_False ==
+       eq.matchesIndexKey( BSON( "" << "dummygeohash" << "" << 4 ), indexSpec ) );
+       ASSERT( MatchExpression::PartialMatchResult_True ==
+       eq.matchesIndexKey( BSON( "" << "dummygeohash" <<
+       "" << BSON_ARRAY( 8 << 6 ) ), indexSpec ) );
+       }
+    */
+    TEST( LtOp, MatchesElement ) {
+        BSONObj operand = BSON( "$lt" << 5 );
+        BSONObj match = BSON( "a" << 4.5 );
+        BSONObj notMatch = BSON( "a" << 6 );
+        BSONObj notMatchEqual = BSON( "a" << 5 );
+        BSONObj notMatchWrongType = BSON( "a" << "foo" );
+        ComparisonExpression lt;
+        ASSERT( lt.init( "", ComparisonExpression::LT, operand[ "$lt" ] ).isOK() );
+        ASSERT( lt.matchesSingleElement( match.firstElement() ) );
+        ASSERT( !lt.matchesSingleElement( notMatch.firstElement() ) );
+        ASSERT( !lt.matchesSingleElement( notMatchEqual.firstElement() ) );
+        ASSERT( !lt.matchesSingleElement( notMatchWrongType.firstElement() ) );
+    }
+
+    TEST( LtOp, InvalidEooOperand ) {
+        BSONObj operand;
+        ComparisonExpression lt;
+        ASSERT( !lt.init( "", ComparisonExpression::LT, operand.firstElement() ).isOK() );
+    }
+
+    TEST( LtOp, MatchesScalar ) {
+        BSONObj operand = BSON( "$lt" << 5 );
+        ComparisonExpression lt;
+        ASSERT( lt.init( "a", ComparisonExpression::LT, operand[ "$lt" ] ).isOK() );
+        ASSERT( lt.matches( BSON( "a" << 4.5 ), NULL ) );
+        ASSERT( !lt.matches( BSON( "a" << 6 ), NULL ) );
+    }
+
+    TEST( LtOp, MatchesArrayValue ) {
+        BSONObj operand = BSON( "$lt" << 5 );
+        ComparisonExpression lt;
+        ASSERT( lt.init( "a", ComparisonExpression::LT, operand[ "$lt" ] ).isOK() );
+        ASSERT( lt.matches( BSON( "a" << BSON_ARRAY( 6 << 4.5 ) ), NULL ) );
+        ASSERT( !lt.matches( BSON( "a" << BSON_ARRAY( 6 << 7 ) ), NULL ) );
+    }
+
+    TEST( LtOp, MatchesWholeArray ) {
+        BSONObj operand = BSON( "$lt" << BSON_ARRAY( 5 ) );
+        ComparisonExpression lt;
+        ASSERT( lt.init( "a", ComparisonExpression::LT, operand[ "$lt" ] ).isOK() );
+        // Arrays are not comparable as inequalities.
+        ASSERT( !lt.matches( BSON( "a" << BSON_ARRAY( 4 ) ), NULL ) );
+    }
+
+    TEST( LtOp, MatchesNull ) {
+        BSONObj operand = BSON( "$lt" << BSONNULL );
+        ComparisonExpression lt;
+        ASSERT( lt.init( "a", ComparisonExpression::LT, operand[ "$lt" ] ).isOK() );
+        ASSERT( !lt.matches( BSONObj(), NULL ) );
+        ASSERT( !lt.matches( BSON( "a" << BSONNULL ), NULL ) );
+        ASSERT( !lt.matches( BSON( "a" << 4 ), NULL ) );
+    }
+
+    TEST( LtOp, MatchesMinKey ) {
+        BSONObj operand = BSON( "a" << MinKey );
+        ComparisonExpression lt;
+        ASSERT( lt.init( "a", ComparisonExpression::LT, operand[ "a" ] ).isOK() );
+        ASSERT( !lt.matches( BSON( "a" << MinKey ), NULL ) );
+        ASSERT( !lt.matches( BSON( "a" << MaxKey ), NULL ) );
+        ASSERT( !lt.matches( BSON( "a" << 4 ), NULL ) );
+    }
+
+    TEST( LtOp, MatchesMaxKey ) {
+        BSONObj operand = BSON( "a" << MaxKey );
+        ComparisonExpression lt;
+        ASSERT( lt.init( "a", ComparisonExpression::LT, operand[ "a" ] ).isOK() );
+        ASSERT( !lt.matches( BSON( "a" << MaxKey ), NULL ) );
+        ASSERT( lt.matches( BSON( "a" << MinKey ), NULL ) );
+        ASSERT( lt.matches( BSON( "a" << 4 ), NULL ) );
+    }
+
+    TEST( LtOp, ElemMatchKey ) {
+        BSONObj operand = BSON( "$lt" << 5 );
+        ComparisonExpression lt;
+        ASSERT( lt.init( "a", ComparisonExpression::LT, operand[ "$lt" ] ).isOK() );
+        MatchDetails details;
+        details.requestElemMatchKey();
+        ASSERT( !lt.matches( BSON( "a" << 6 ), &details ) );
+        ASSERT( !details.hasElemMatchKey() );
+        ASSERT( lt.matches( BSON( "a" << 4 ), &details ) );
+        ASSERT( !details.hasElemMatchKey() );
+        ASSERT( lt.matches( BSON( "a" << BSON_ARRAY( 6 << 2 << 5 ) ), &details ) );
+        ASSERT( details.hasElemMatchKey() );
+        ASSERT_EQUALS( "1", details.elemMatchKey() );
+    }
+
+    /**
+       TEST( LtOp, MatchesIndexKeyScalar ) {
+       BSONObj operand = BSON( "$lt" << 6 );
+       LtOp lt;
+       ASSERT( lt.init( "a", operand[ "$lt" ] ).isOK() );
+       IndexSpec indexSpec( BSON( "a" << 1 ) );
+       ASSERT( MatchExpression::PartialMatchResult_True ==
+       lt.matchesIndexKey( BSON( "" << 3 ), indexSpec ) );
+       ASSERT( MatchExpression::PartialMatchResult_False ==
+       lt.matchesIndexKey( BSON( "" << 6 ), indexSpec ) );
+       ASSERT( MatchExpression::PartialMatchResult_False ==
+       lt.matchesIndexKey( BSON( "" << BSON_ARRAY( 5 ) ), indexSpec ) );
+       }
+
+       TEST( LtOp, MatchesIndexKeyMissing ) {
+       BSONObj operand = BSON( "$lt" << 6 );
+       LtOp lt;
+       ASSERT( lt.init( "a", operand[ "$lt" ] ).isOK() );
+       IndexSpec indexSpec( BSON( "b" << 1 ) );
+       ASSERT( MatchExpression::PartialMatchResult_Unknown ==
+       lt.matchesIndexKey( BSON( "" << 6 ), indexSpec ) );
+       ASSERT( MatchExpression::PartialMatchResult_Unknown ==
+       lt.matchesIndexKey( BSON( "" << 4 ), indexSpec ) );
+       ASSERT( MatchExpression::PartialMatchResult_Unknown ==
+       lt.matchesIndexKey( BSON( "" << BSON_ARRAY( 8 << 6 ) ), indexSpec ) );
+       }
+
+       TEST( LtOp, MatchesIndexKeyArray ) {
+       BSONObj operand = BSON( "$lt" << BSON_ARRAY( 4 << 5 ) );
+       LtOp lt;
+       ASSERT( lt.init( "a", operand[ "$lt" ] ).isOK() );
+       IndexSpec indexSpec( BSON( "a" << 1 ) );
+       ASSERT( MatchExpression::PartialMatchResult_Unknown ==
+       lt.matchesIndexKey( BSON( "" << 3 ), indexSpec ) );
+       }
+    
+       TEST( LtOp, MatchesIndexKeyArrayValue ) {
+       BSONObj operand = BSON( "$lt" << 6 );
+       LtOp lt;
+       ASSERT( lt.init( "a", operand[ "$lt" ] ).isOK() );
+       IndexSpec indexSpec( BSON( "loc" << "mockarrayvalue" << "a" << 1 ) );
+       ASSERT( MatchExpression::PartialMatchResult_True ==
+       lt.matchesIndexKey( BSON( "" << "dummygeohash" << "" << 3 ), indexSpec ) );
+       ASSERT( MatchExpression::PartialMatchResult_False ==
+       lt.matchesIndexKey( BSON( "" << "dummygeohash" << "" << 6 ), indexSpec ) );
+       ASSERT( MatchExpression::PartialMatchResult_True ==
+       lt.matchesIndexKey( BSON( "" << "dummygeohash" <<
+       "" << BSON_ARRAY( 8 << 6 << 4 ) ), indexSpec ) );
+       }
+    */
+    TEST( LteOp, MatchesElement ) {
+        BSONObj operand = BSON( "$lte" << 5 );
+        BSONObj match = BSON( "a" << 4.5 );
+        BSONObj equalMatch = BSON( "a" << 5 );
+        BSONObj notMatch = BSON( "a" << 6 );
+        BSONObj notMatchWrongType = BSON( "a" << "foo" );
+        ComparisonExpression lte;
+        ASSERT( lte.init( "", ComparisonExpression::LTE, operand[ "$lte" ] ).isOK() );
+        ASSERT( lte.matchesSingleElement( match.firstElement() ) );
+        ASSERT( lte.matchesSingleElement( equalMatch.firstElement() ) );
+        ASSERT( !lte.matchesSingleElement( notMatch.firstElement() ) );
+        ASSERT( !lte.matchesSingleElement( notMatchWrongType.firstElement() ) );
+    }
+
+    TEST( LteOp, InvalidEooOperand ) {
+        BSONObj operand;
+        ComparisonExpression lte;
+        ASSERT( !lte.init( "", ComparisonExpression::LTE, operand.firstElement() ).isOK() );
+    }
+
+    TEST( LteOp, MatchesScalar ) {
+        BSONObj operand = BSON( "$lte" << 5 );
+        ComparisonExpression lte;
+        ASSERT( lte.init( "a", ComparisonExpression::LTE, operand[ "$lte" ] ).isOK() );
+        ASSERT( lte.matches( BSON( "a" << 4.5 ), NULL ) );
+        ASSERT( !lte.matches( BSON( "a" << 6 ), NULL ) );
+    }
+
+    TEST( LteOp, MatchesArrayValue ) {
+        BSONObj operand = BSON( "$lte" << 5 );
+        ComparisonExpression lte;
+        ASSERT( lte.init( "a", ComparisonExpression::LTE, operand[ "$lte" ] ).isOK() );
+        ASSERT( lte.matches( BSON( "a" << BSON_ARRAY( 6 << 4.5 ) ), NULL ) );
+        ASSERT( !lte.matches( BSON( "a" << BSON_ARRAY( 6 << 7 ) ), NULL ) );
+    }
+
+    TEST( LteOp, MatchesWholeArray ) {
+        BSONObj operand = BSON( "$lte" << BSON_ARRAY( 5 ) );
+        ComparisonExpression lte;
+        ASSERT( lte.init( "a", ComparisonExpression::LTE, operand[ "$lte" ] ).isOK() );
+        // Arrays are not comparable as inequalities.
+        ASSERT( !lte.matches( BSON( "a" << BSON_ARRAY( 4 ) ), NULL ) );
+    }
+
+    TEST( LteOp, MatchesNull ) {
+        BSONObj operand = BSON( "$lte" << BSONNULL );
+        ComparisonExpression lte;
+        ASSERT( lte.init( "a", ComparisonExpression::LTE, operand[ "$lte" ] ).isOK() );
+        ASSERT( lte.matches( BSONObj(), NULL ) );
+        ASSERT( lte.matches( BSON( "a" << BSONNULL ), NULL ) );
+        ASSERT( !lte.matches( BSON( "a" << 4 ), NULL ) );
+    }
+
+    TEST( LteOp, MatchesMinKey ) {
+        BSONObj operand = BSON( "a" << MinKey );
+        ComparisonExpression lte;
+        ASSERT( lte.init( "a", ComparisonExpression::LTE, operand[ "a" ] ).isOK() );
+        ASSERT( lte.matches( BSON( "a" << MinKey ), NULL ) );
+        ASSERT( !lte.matches( BSON( "a" << MaxKey ), NULL ) );
+        ASSERT( !lte.matches( BSON( "a" << 4 ), NULL ) );
+    }
+
+    TEST( LteOp, MatchesMaxKey ) {
+        BSONObj operand = BSON( "a" << MaxKey );
+        ComparisonExpression lte;
+        ASSERT( lte.init( "a", ComparisonExpression::LTE, operand[ "a" ] ).isOK() );
+        ASSERT( lte.matches( BSON( "a" << MaxKey ), NULL ) );
+        ASSERT( lte.matches( BSON( "a" << MinKey ), NULL ) );
+        ASSERT( lte.matches( BSON( "a" << 4 ), NULL ) );
+    }
+
+
+    TEST( LteOp, ElemMatchKey ) {
+        BSONObj operand = BSON( "$lte" << 5 );
+        ComparisonExpression lte;
+        ASSERT( lte.init( "a", ComparisonExpression::LTE, operand[ "$lte" ] ).isOK() );
+        MatchDetails details;
+        details.requestElemMatchKey();
+        ASSERT( !lte.matches( BSON( "a" << 6 ), &details ) );
+        ASSERT( !details.hasElemMatchKey() );
+        ASSERT( lte.matches( BSON( "a" << 4 ), &details ) );
+        ASSERT( !details.hasElemMatchKey() );
+        ASSERT( lte.matches( BSON( "a" << BSON_ARRAY( 6 << 2 << 5 ) ), &details ) );
+        ASSERT( details.hasElemMatchKey() );
+        ASSERT_EQUALS( "1", details.elemMatchKey() );
+    }
+
+    /**
+       TEST( LteOp, MatchesIndexKeyScalar ) {
+       BSONObj operand = BSON( "$lte" << 6 );
+       LteOp lte;
+       ASSERT( lte.init( "a", operand[ "$lte" ] ).isOK() );
+       IndexSpec indexSpec( BSON( "a" << 1 ) );
+       ASSERT( MatchExpression::PartialMatchResult_True ==
+       lte.matchesIndexKey( BSON( "" << 6 ), indexSpec ) );
+       ASSERT( MatchExpression::PartialMatchResult_False ==
+       lte.matchesIndexKey( BSON( "" << 7 ), indexSpec ) );
+       ASSERT( MatchExpression::PartialMatchResult_False ==
+       lte.matchesIndexKey( BSON( "" << BSON_ARRAY( 5 ) ), indexSpec ) );
+       }
+
+       TEST( LteOp, MatchesIndexKeyMissing ) {
+       BSONObj operand = BSON( "$lte" << 6 );
+       LteOp lte;
+       ASSERT( lte.init( "a", operand[ "$lte" ] ).isOK() );
+       IndexSpec indexSpec( BSON( "b" << 1 ) );
+       ASSERT( MatchExpression::PartialMatchResult_Unknown ==
+       lte.matchesIndexKey( BSON( "" << 7 ), indexSpec ) );
+       ASSERT( MatchExpression::PartialMatchResult_Unknown ==
+       lte.matchesIndexKey( BSON( "" << 4 ), indexSpec ) );
+       ASSERT( MatchExpression::PartialMatchResult_Unknown ==
+       lte.matchesIndexKey( BSON( "" << BSON_ARRAY( 8 << 6 ) ), indexSpec ) );
+       }
+
+       TEST( LteOp, MatchesIndexKeyArray ) {
+       BSONObj operand = BSON( "$lte" << BSON_ARRAY( 4 << 5 ) );
+       LteOp lte;
+       ASSERT( lte.init( "a", operand[ "$lte" ] ).isOK() );
+       IndexSpec indexSpec( BSON( "a" << 1 ) );
+       ASSERT( MatchExpression::PartialMatchResult_Unknown ==
+       lte.matchesIndexKey( BSON( "" << 3 ), indexSpec ) );
+       }
+
+       TEST( LteOp, MatchesIndexKeyArrayValue ) {
+       BSONObj operand = BSON( "$lte" << 6 );
+       LteOp lte;
+       ASSERT( lte.init( "a", operand[ "$lte" ] ).isOK() );
+       IndexSpec indexSpec( BSON( "loc" << "mockarrayvalue" << "a" << 1 ) );
+       ASSERT( MatchExpression::PartialMatchResult_True ==
+       lte.matchesIndexKey( BSON( "" << "dummygeohash" << "" << 3 ), indexSpec ) );
+       ASSERT( MatchExpression::PartialMatchResult_False ==
+       lte.matchesIndexKey( BSON( "" << "dummygeohash" << "" << 7 ), indexSpec ) );
+       ASSERT( MatchExpression::PartialMatchResult_True ==
+       lte.matchesIndexKey( BSON( "" << "dummygeohash" <<
+       "" << BSON_ARRAY( 8 << 6 << 4 ) ), indexSpec ) );
+       }
+
+       TEST( GtOp, MatchesElement ) {
+       BSONObj operand = BSON( "$gt" << 5 );
+       BSONObj match = BSON( "a" << 5.5 );
+       BSONObj notMatch = BSON( "a" << 4 );
+       BSONObj notMatchEqual = BSON( "a" << 5 );
+       BSONObj notMatchWrongType = BSON( "a" << "foo" );
+       GtOp gt;
+       ASSERT( gt.init( "", operand[ "$gt" ] ).isOK() );
+       ASSERT( gt.matchesSingleElement( match.firstElement() ) );
+       ASSERT( !gt.matchesSingleElement( notMatch.firstElement() ) );
+       ASSERT( !gt.matchesSingleElement( notMatchEqual.firstElement() ) );
+       ASSERT( !gt.matchesSingleElement( notMatchWrongType.firstElement() ) );
+       }
+    */
+
+    TEST( GtOp, InvalidEooOperand ) {
+        BSONObj operand;
+        ComparisonExpression gt;
+        ASSERT( !gt.init( "", ComparisonExpression::GT, operand.firstElement() ).isOK() );
+    }
+
+    TEST( GtOp, MatchesScalar ) {
+        BSONObj operand = BSON( "$gt" << 5 );
+        ComparisonExpression gt;
+        ASSERT( gt.init( "a", ComparisonExpression::GT, operand[ "$gt" ] ).isOK() );
+        ASSERT( gt.matches( BSON( "a" << 5.5 ), NULL ) );
+        ASSERT( !gt.matches( BSON( "a" << 4 ), NULL ) );
+    }
+
+    TEST( GtOp, MatchesArrayValue ) {
+        BSONObj operand = BSON( "$gt" << 5 );
+        ComparisonExpression gt;
+        ASSERT( gt.init( "a", ComparisonExpression::GT, operand[ "$gt" ] ).isOK() );
+        ASSERT( gt.matches( BSON( "a" << BSON_ARRAY( 3 << 5.5 ) ), NULL ) );
+        ASSERT( !gt.matches( BSON( "a" << BSON_ARRAY( 2 << 4 ) ), NULL ) );
+    }
+
+    TEST( GtOp, MatchesWholeArray ) {
+        BSONObj operand = BSON( "$gt" << BSON_ARRAY( 5 ) );
+        ComparisonExpression gt;
+        ASSERT( gt.init( "a", ComparisonExpression::GT, operand[ "$gt" ] ).isOK() );
+        // Arrays are not comparable as inequalities.
+        ASSERT( !gt.matches( BSON( "a" << BSON_ARRAY( 6 ) ), NULL ) );
+    }
+
+    TEST( GtOp, MatchesNull ) {
+        BSONObj operand = BSON( "$gt" << BSONNULL );
+        ComparisonExpression gt;
+        ASSERT( gt.init( "a", ComparisonExpression::GT, operand[ "$gt" ] ).isOK() );
+        ASSERT( !gt.matches( BSONObj(), NULL ) );
+        ASSERT( !gt.matches( BSON( "a" << BSONNULL ), NULL ) );
+        ASSERT( !gt.matches( BSON( "a" << 4 ), NULL ) );
+    }
+
+    TEST( GtOp, MatchesMinKey ) {
+        BSONObj operand = BSON( "a" << MinKey );
+        ComparisonExpression gt;
+        ASSERT( gt.init( "a", ComparisonExpression::GT, operand[ "a" ] ).isOK() );
+        ASSERT( !gt.matches( BSON( "a" << MinKey ), NULL ) );
+        ASSERT( gt.matches( BSON( "a" << MaxKey ), NULL ) );
+        ASSERT( gt.matches( BSON( "a" << 4 ), NULL ) );
+    }
+
+    TEST( GtOp, MatchesMaxKey ) {
+        BSONObj operand = BSON( "a" << MaxKey );
+        ComparisonExpression gt;
+        ASSERT( gt.init( "a", ComparisonExpression::GT, operand[ "a" ] ).isOK() );
+        ASSERT( !gt.matches( BSON( "a" << MaxKey ), NULL ) );
+        ASSERT( !gt.matches( BSON( "a" << MinKey ), NULL ) );
+        ASSERT( !gt.matches( BSON( "a" << 4 ), NULL ) );
+    }
+
+    TEST( GtOp, ElemMatchKey ) {
+        BSONObj operand = BSON( "$gt" << 5 );
+        ComparisonExpression gt;
+        ASSERT( gt.init( "a", ComparisonExpression::GT, operand[ "$gt" ] ).isOK() );
+        MatchDetails details;
+        details.requestElemMatchKey();
+        ASSERT( !gt.matches( BSON( "a" << 4 ), &details ) );
+        ASSERT( !details.hasElemMatchKey() );
+        ASSERT( gt.matches( BSON( "a" << 6 ), &details ) );
+        ASSERT( !details.hasElemMatchKey() );
+        ASSERT( gt.matches( BSON( "a" << BSON_ARRAY( 2 << 6 << 5 ) ), &details ) );
+        ASSERT( details.hasElemMatchKey() );
+        ASSERT_EQUALS( "1", details.elemMatchKey() );
+    }
+
+    /**
+       TEST( GtOp, MatchesIndexKeyScalar ) {
+       BSONObj operand = BSON( "$gt" << 6 );
+       GtOp gt;
+       ASSERT( gt.init( "a", operand[ "$gt" ] ).isOK() );
+       IndexSpec indexSpec( BSON( "a" << 1 ) );
+       ASSERT( MatchExpression::PartialMatchResult_True ==
+       gt.matchesIndexKey( BSON( "" << 7 ), indexSpec ) );
+       ASSERT( MatchExpression::PartialMatchResult_False ==
+       gt.matchesIndexKey( BSON( "" << 6 ), indexSpec ) );
+       ASSERT( MatchExpression::PartialMatchResult_False ==
+       gt.matchesIndexKey( BSON( "" << BSON_ARRAY( 9 ) ), indexSpec ) );
+       }
+
+       TEST( GtOp, MatchesIndexKeyMissing ) {
+       BSONObj operand = BSON( "$gt" << 6 );
+       GtOp gt;
+       ASSERT( gt.init( "a", operand[ "$gt" ] ).isOK() );
+       IndexSpec indexSpec( BSON( "b" << 1 ) );
+       ASSERT( MatchExpression::PartialMatchResult_Unknown ==
+       gt.matchesIndexKey( BSON( "" << 7 ), indexSpec ) );
+       ASSERT( MatchExpression::PartialMatchResult_Unknown ==
+       gt.matchesIndexKey( BSON( "" << 4 ), indexSpec ) );
+       ASSERT( MatchExpression::PartialMatchResult_Unknown ==
+       gt.matchesIndexKey( BSON( "" << BSON_ARRAY( 8 << 6 ) ), indexSpec ) );
+       }
+
+       TEST( GtOp, MatchesIndexKeyArray ) {
+       BSONObj operand = BSON( "$gt" << BSON_ARRAY( 4 << 5 ) );
+       GtOp gt;
+       ASSERT( gt.init( "a", operand[ "$gt" ] ).isOK() );
+       IndexSpec indexSpec( BSON( "a" << 1 ) );
+       ASSERT( MatchExpression::PartialMatchResult_Unknown ==
+       gt.matchesIndexKey( BSON( "" << 8 ), indexSpec ) );
+       }
+    
+       TEST( GtOp, MatchesIndexKeyArrayValue ) {
+       BSONObj operand = BSON( "$gt" << 6 );
+       GtOp gt;
+       ASSERT( gt.init( "a", operand[ "$gt" ] ).isOK() );
+       IndexSpec indexSpec( BSON( "loc" << "mockarrayvalue" << "a" << 1 ) );
+       ASSERT( MatchExpression::PartialMatchResult_True ==
+       gt.matchesIndexKey( BSON( "" << "dummygeohash" << "" << 7 ), indexSpec ) );
+       ASSERT( MatchExpression::PartialMatchResult_False ==
+       gt.matchesIndexKey( BSON( "" << "dummygeohash" << "" << 3 ), indexSpec ) );
+       ASSERT( MatchExpression::PartialMatchResult_True ==
+       gt.matchesIndexKey( BSON( "" << "dummygeohash" <<
+       "" << BSON_ARRAY( 8 << 6 << 4 ) ), indexSpec ) );
+       }
+    */
+
+    TEST( ComparisonExpression, MatchesElement ) {
+        BSONObj operand = BSON( "$gte" << 5 );
+        BSONObj match = BSON( "a" << 5.5 );
+        BSONObj equalMatch = BSON( "a" << 5 );
+        BSONObj notMatch = BSON( "a" << 4 );
+        BSONObj notMatchWrongType = BSON( "a" << "foo" );
+        ComparisonExpression gte;
+        ASSERT( gte.init( "", ComparisonExpression::GTE, operand[ "$gte" ] ).isOK() );
+        ASSERT( gte.matchesSingleElement( match.firstElement() ) );
+        ASSERT( gte.matchesSingleElement( equalMatch.firstElement() ) );
+        ASSERT( !gte.matchesSingleElement( notMatch.firstElement() ) );
+        ASSERT( !gte.matchesSingleElement( notMatchWrongType.firstElement() ) );
+    }
+
+    TEST( ComparisonExpression, InvalidEooOperand ) {
+        BSONObj operand;
+        ComparisonExpression gte;
+        ASSERT( !gte.init( "", ComparisonExpression::GTE, operand.firstElement() ).isOK() );
+    }
+
+    TEST( ComparisonExpression, MatchesScalar ) {
+        BSONObj operand = BSON( "$gte" << 5 );
+        ComparisonExpression gte;
+        ASSERT( gte.init( "a", ComparisonExpression::GTE, operand[ "$gte" ] ).isOK() );
+        ASSERT( gte.matches( BSON( "a" << 5.5 ), NULL ) );
+        ASSERT( !gte.matches( BSON( "a" << 4 ), NULL ) );
+    }
+
+    TEST( ComparisonExpression, MatchesArrayValue ) {
+        BSONObj operand = BSON( "$gte" << 5 );
+        ComparisonExpression gte;
+        ASSERT( gte.init( "a", ComparisonExpression::GTE, operand[ "$gte" ] ).isOK() );
+        ASSERT( gte.matches( BSON( "a" << BSON_ARRAY( 4 << 5.5 ) ), NULL ) );
+        ASSERT( !gte.matches( BSON( "a" << BSON_ARRAY( 1 << 2 ) ), NULL ) );
+    }
+
+    TEST( ComparisonExpression, MatchesWholeArray ) {
+        BSONObj operand = BSON( "$gte" << BSON_ARRAY( 5 ) );
+        ComparisonExpression gte;
+        ASSERT( gte.init( "a", ComparisonExpression::GTE, operand[ "$gte" ] ).isOK() );
+        // Arrays are not comparable as inequalities.
+        ASSERT( !gte.matches( BSON( "a" << BSON_ARRAY( 6 ) ), NULL ) );
+    }
+
+    TEST( ComparisonExpression, MatchesNull ) {
+        BSONObj operand = BSON( "$gte" << BSONNULL );
+        ComparisonExpression gte;
+        ASSERT( gte.init( "a", ComparisonExpression::GTE, operand[ "$gte" ] ).isOK() );
+        ASSERT( gte.matches( BSONObj(), NULL ) );
+        ASSERT( gte.matches( BSON( "a" << BSONNULL ), NULL ) );
+        ASSERT( !gte.matches( BSON( "a" << 4 ), NULL ) );
+    }
+
+    TEST( ComparisonExpression, MatchesMinKey ) {
+        BSONObj operand = BSON( "a" << MinKey );
+        ComparisonExpression gte;
+        ASSERT( gte.init( "a", ComparisonExpression::GTE, operand[ "a" ] ).isOK() );
+        ASSERT( gte.matches( BSON( "a" << MinKey ), NULL ) );
+        ASSERT( gte.matches( BSON( "a" << MaxKey ), NULL ) );
+        ASSERT( gte.matches( BSON( "a" << 4 ), NULL ) );
+    }
+
+    TEST( ComparisonExpression, MatchesMaxKey ) {
+        BSONObj operand = BSON( "a" << MaxKey );
+        ComparisonExpression gte;
+        ASSERT( gte.init( "a", ComparisonExpression::GTE, operand[ "a" ] ).isOK() );
+        ASSERT( gte.matches( BSON( "a" << MaxKey ), NULL ) );
+        ASSERT( !gte.matches( BSON( "a" << MinKey ), NULL ) );
+        ASSERT( !gte.matches( BSON( "a" << 4 ), NULL ) );
+    }
+
+    TEST( ComparisonExpression, ElemMatchKey ) {
+        BSONObj operand = BSON( "$gte" << 5 );
+        ComparisonExpression gte;
+        ASSERT( gte.init( "a", ComparisonExpression::GTE, operand[ "$gte" ] ).isOK() );
+        MatchDetails details;
+        details.requestElemMatchKey();
+        ASSERT( !gte.matches( BSON( "a" << 4 ), &details ) );
+        ASSERT( !details.hasElemMatchKey() );
+        ASSERT( gte.matches( BSON( "a" << 6 ), &details ) );
+        ASSERT( !details.hasElemMatchKey() );
+        ASSERT( gte.matches( BSON( "a" << BSON_ARRAY( 2 << 6 << 5 ) ), &details ) );
+        ASSERT( details.hasElemMatchKey() );
+        ASSERT_EQUALS( "1", details.elemMatchKey() );
+    }
+
+    /**
+       TEST( GteOp, MatchesIndexKeyScalar ) {
+       BSONObj operand = BSON( "$gte" << 6 );
+       GteOp gte;
+       ASSERT( gte.init( "a", operand[ "$gte" ] ).isOK() );
+       IndexSpec indexSpec( BSON( "a" << 1 ) );
+       ASSERT( MatchExpression::PartialMatchResult_True ==
+       gte.matchesIndexKey( BSON( "" << 6 ), indexSpec ) );
+       ASSERT( MatchExpression::PartialMatchResult_False ==
+       gte.matchesIndexKey( BSON( "" << 5 ), indexSpec ) );
+       ASSERT( MatchExpression::PartialMatchResult_False ==
+       gte.matchesIndexKey( BSON( "" << BSON_ARRAY( 7 ) ), indexSpec ) );
+       }
+
+       TEST( GteOp, MatchesIndexKeyMissing ) {
+       BSONObj operand = BSON( "$gte" << 6 );
+       GteOp gte;
+       ASSERT( gte.init( "a", operand[ "$gte" ] ).isOK() );
+       IndexSpec indexSpec( BSON( "b" << 1 ) );
+       ASSERT( MatchExpression::PartialMatchResult_Unknown ==
+       gte.matchesIndexKey( BSON( "" << 6 ), indexSpec ) );
+       ASSERT( MatchExpression::PartialMatchResult_Unknown ==
+       gte.matchesIndexKey( BSON( "" << 4 ), indexSpec ) );
+       ASSERT( MatchExpression::PartialMatchResult_Unknown ==
+       gte.matchesIndexKey( BSON( "" << BSON_ARRAY( 8 << 6 ) ), indexSpec ) );
+       }
+
+       TEST( GteOp, MatchesIndexKeyArray ) {
+       BSONObj operand = BSON( "$gte" << BSON_ARRAY( 4 << 5 ) );
+       GteOp gte;
+       ASSERT( gte.init( "a", operand[ "$gte" ] ).isOK() );
+       IndexSpec indexSpec( BSON( "a" << 1 ) );
+       ASSERT( MatchExpression::PartialMatchResult_Unknown ==
+       gte.matchesIndexKey( BSON( "" << 6 ), indexSpec ) );
+       }
+
+       TEST( GteOp, MatchesIndexKeyArrayValue ) {
+       BSONObj operand = BSON( "$gte" << 6 );
+       GteOp gte;
+       ASSERT( gte.init( "a", operand[ "$gte" ] ).isOK() );
+       IndexSpec indexSpec( BSON( "loc" << "mockarrayvalue" << "a" << 1 ) );
+       ASSERT( MatchExpression::PartialMatchResult_True ==
+       gte.matchesIndexKey( BSON( "" << "dummygeohash" << "" << 6 ), indexSpec ) );
+       ASSERT( MatchExpression::PartialMatchResult_False ==
+       gte.matchesIndexKey( BSON( "" << "dummygeohash" << "" << 3 ), indexSpec ) );
+       ASSERT( MatchExpression::PartialMatchResult_True ==
+       gte.matchesIndexKey( BSON( "" << "dummygeohash" <<
+       "" << BSON_ARRAY( 8 << 6 << 4 ) ), indexSpec ) );
+       }
+    */
+
+    TEST( NeOp, MatchesElement ) {
+        BSONObj operand = BSON( "$ne" << 5 );
+        BSONObj match = BSON( "a" << 6 );
+        BSONObj notMatch = BSON( "a" << 5 );
+        ComparisonExpression ne;
+        ASSERT( ne.init( "", ComparisonExpression::NE, operand[ "$ne" ] ).isOK() );
+        ASSERT( ne.matchesSingleElement( match.firstElement() ) );
+        ASSERT( !ne.matchesSingleElement( notMatch.firstElement() ) );
+    }
+
+    TEST( NeOp, InvalidEooOperand ) {
+        BSONObj operand;
+        ComparisonExpression ne;
+        ASSERT( !ne.init( "", ComparisonExpression::NE, operand.firstElement() ).isOK() );
+    }
+
+    TEST( NeOp, MatchesScalar ) {
+        BSONObj operand = BSON( "$ne" << 5 );
+        ComparisonExpression ne;
+        ASSERT( ne.init( "a", ComparisonExpression::NE, operand[ "$ne" ] ).isOK() );
+        ASSERT( ne.matches( BSON( "a" << 4 ), NULL ) );
+        ASSERT( !ne.matches( BSON( "a" << 5 ), NULL ) );
+    }
+
+    TEST( NeOp, MatchesArrayValue ) {
+        BSONObj operand = BSON( "$ne" << 5 );
+        ComparisonExpression ne;
+        ASSERT( ne.init( "a", ComparisonExpression::NE, operand[ "$ne" ] ).isOK() );
+        ASSERT( ne.matches( BSON( "a" << BSON_ARRAY( 4 << 6 ) ), NULL ) );
+        ASSERT( !ne.matches( BSON( "a" << BSON_ARRAY( 4 << 5 ) ), NULL ) );
+        ASSERT( !ne.matches( BSON( "a" << BSON_ARRAY( 5 << 5 ) ), NULL ) );
+    }
+
+    TEST( NeOp, MatchesNull ) {
+        BSONObj operand = BSON( "$ne" << BSONNULL );
+        ComparisonExpression ne;
+        ASSERT( ne.init( "a", ComparisonExpression::NE, operand[ "$ne" ] ).isOK() );
+        ASSERT( ne.matches( BSON( "a" << 4 ), NULL ) );
+        ASSERT( !ne.matches( BSONObj(), NULL ) );
+        ASSERT( !ne.matches( BSON( "a" << BSONNULL ), NULL ) );
+    }
+
+    TEST( NeOp, ElemMatchKey ) {
+        BSONObj operand = BSON( "$ne" << 5 );
+        ComparisonExpression ne;
+        ASSERT( ne.init( "a", ComparisonExpression::NE, operand[ "$ne" ] ).isOK() );
+        MatchDetails details;
+        details.requestElemMatchKey();
+        ASSERT( !ne.matches( BSON( "a" << BSON_ARRAY( 2 << 6 << 5 ) ), &details ) );
+        ASSERT( !details.hasElemMatchKey() );
+        ASSERT( ne.matches( BSON( "a" << BSON_ARRAY( 2 << 6 ) ), &details ) );
+        // The elemMatchKey feature is not implemented for $ne.
+        ASSERT( !details.hasElemMatchKey() );
+    }
+
+    /**
+       TEST( NeOp, MatchesIndexKey ) {
+       BSONObj operand = BSON( "$ne" << 5 );
+       NeOp ne;
+       ASSERT( ne.init( "a", operand[ "$ne" ] ).isOK() );
+       IndexSpec indexSpec( BSON( "a" << 1 ) );
+       BSONObj indexKey = BSON( "" << 1 );
+       ASSERT( MatchExpression::PartialMatchResult_Unknown ==
+       ne.matchesIndexKey( indexKey, indexSpec ) );
+       }
+    */
+
+    TEST( RegexExpression, MatchesElementExact ) {
+        BSONObj match = BSON( "a" << "b" );
+        BSONObj notMatch = BSON( "a" << "c" );
+        RegexExpression regex;
+        ASSERT( regex.init( "", "b", "" ).isOK() );
+        ASSERT( regex.matchesSingleElement( match.firstElement() ) );
+        ASSERT( !regex.matchesSingleElement( notMatch.firstElement() ) );
+    }
+
+    TEST( RegexExpression, TooLargePattern ) {
+        string tooLargePattern( 50 * 1000, 'z' );
+        RegexExpression regex;
+        ASSERT( !regex.init( "a", tooLargePattern, "" ).isOK() );
+    }
+
+    TEST( RegexExpression, MatchesElementSimplePrefix ) {
+        BSONObj match = BSON( "x" << "abc" );
+        BSONObj notMatch = BSON( "x" << "adz" );
+        RegexExpression regex;
+        ASSERT( regex.init( "", "^ab", "" ).isOK() );
+        ASSERT( regex.matchesSingleElement( match.firstElement() ) );
+        ASSERT( !regex.matchesSingleElement( notMatch.firstElement() ) );
+    }
+
+    TEST( RegexExpression, MatchesElementCaseSensitive ) {
+        BSONObj match = BSON( "x" << "abc" );
+        BSONObj notMatch = BSON( "x" << "ABC" );
+        RegexExpression regex;
+        ASSERT( regex.init( "", "abc", "" ).isOK() );
+        ASSERT( regex.matchesSingleElement( match.firstElement() ) );
+        ASSERT( !regex.matchesSingleElement( notMatch.firstElement() ) );
+    }
+
+    TEST( RegexExpression, MatchesElementCaseInsensitive ) {
+        BSONObj match = BSON( "x" << "abc" );
+        BSONObj matchUppercase = BSON( "x" << "ABC" );
+        BSONObj notMatch = BSON( "x" << "abz" );
+        RegexExpression regex;
+        ASSERT( regex.init( "", "abc", "i" ).isOK() );
+        ASSERT( regex.matchesSingleElement( match.firstElement() ) );
+        ASSERT( regex.matchesSingleElement( matchUppercase.firstElement() ) );
+        ASSERT( !regex.matchesSingleElement( notMatch.firstElement() ) );
+    }
+
+    TEST( RegexExpression, MatchesElementMultilineOff ) {
+        BSONObj match = BSON( "x" << "az" );
+        BSONObj notMatch = BSON( "x" << "\naz" );
+        RegexExpression regex;
+        ASSERT( regex.init( "", "^a", "" ).isOK() );
+        ASSERT( regex.matchesSingleElement( match.firstElement() ) );
+        ASSERT( !regex.matchesSingleElement( notMatch.firstElement() ) );
+    }
+
+    TEST( RegexExpression, MatchesElementMultilineOn ) {
+        BSONObj match = BSON( "x" << "az" );
+        BSONObj matchMultiline = BSON( "x" << "\naz" );
+        BSONObj notMatch = BSON( "x" << "\n\n" );
+        RegexExpression regex;
+        ASSERT( regex.init( "", "^a", "m" ).isOK() );
+        ASSERT( regex.matchesSingleElement( match.firstElement() ) );
+        ASSERT( regex.matchesSingleElement( matchMultiline.firstElement() ) );
+        ASSERT( !regex.matchesSingleElement( notMatch.firstElement() ) );
+    }
+
+    TEST( RegexExpression, MatchesElementExtendedOff ) {
+        BSONObj match = BSON( "x" << "a b" );
+        BSONObj notMatch = BSON( "x" << "ab" );
+        RegexExpression regex;
+        ASSERT( regex.init( "", "a b", "" ).isOK() );
+        ASSERT( regex.matchesSingleElement( match.firstElement() ) );
+        ASSERT( !regex.matchesSingleElement( notMatch.firstElement() ) );
+    }
+
+    TEST( RegexExpression, MatchesElementExtendedOn ) {
+        BSONObj match = BSON( "x" << "ab" );
+        BSONObj notMatch = BSON( "x" << "a b" );
+        RegexExpression regex;
+        ASSERT( regex.init( "", "a b", "x" ).isOK() );
+        ASSERT( regex.matchesSingleElement( match.firstElement() ) );
+        ASSERT( !regex.matchesSingleElement( notMatch.firstElement() ) );
+    }
+
+    TEST( RegexExpression, MatchesElementDotAllOff ) {
+        BSONObj match = BSON( "x" << "a b" );
+        BSONObj notMatch = BSON( "x" << "a\nb" );
+        RegexExpression regex;
+        ASSERT( regex.init( "", "a.b", "" ).isOK() );
+        ASSERT( regex.matchesSingleElement( match.firstElement() ) );
+        ASSERT( !regex.matchesSingleElement( notMatch.firstElement() ) );
+    }
+
+    TEST( RegexExpression, MatchesElementDotAllOn ) {
+        BSONObj match = BSON( "x" << "a b" );
+        BSONObj matchDotAll = BSON( "x" << "a\nb" );
+        BSONObj notMatch = BSON( "x" << "ab" );
+        RegexExpression regex;
+        ASSERT( regex.init( "", "a.b", "s" ).isOK() );
+        ASSERT( regex.matchesSingleElement( match.firstElement() ) );
+        ASSERT( regex.matchesSingleElement( matchDotAll.firstElement() ) );
+        ASSERT( !regex.matchesSingleElement( notMatch.firstElement() ) );
+    }
+
+    TEST( RegexExpression, MatchesElementMultipleFlags ) {
+        BSONObj matchMultilineDotAll = BSON( "x" << "\na\nb" );
+        RegexExpression regex;
+        ASSERT( regex.init( "", "^a.b", "ms" ).isOK() );
+        ASSERT( regex.matchesSingleElement( matchMultilineDotAll.firstElement() ) );
+    }
+
+    TEST( RegexExpression, MatchesElementRegexType ) {
+        BSONObj match = BSONObjBuilder().appendRegex( "x", "yz", "i" ).obj();
+        BSONObj notMatchPattern = BSONObjBuilder().appendRegex( "x", "r", "i" ).obj();
+        BSONObj notMatchFlags = BSONObjBuilder().appendRegex( "x", "yz", "s" ).obj();
+        RegexExpression regex;
+        ASSERT( regex.init( "", "yz", "i" ).isOK() );
+        ASSERT( regex.matchesSingleElement( match.firstElement() ) );
+        ASSERT( !regex.matchesSingleElement( notMatchPattern.firstElement() ) );
+        ASSERT( !regex.matchesSingleElement( notMatchFlags.firstElement() ) );
+    }
+
+    TEST( RegexExpression, MatchesElementSymbolType ) {
+        BSONObj match = BSONObjBuilder().appendSymbol( "x", "yz" ).obj();
+        BSONObj notMatch = BSONObjBuilder().appendSymbol( "x", "gg" ).obj();
+        RegexExpression regex;
+        ASSERT( regex.init( "", "yz", "" ).isOK() );
+        ASSERT( regex.matchesSingleElement( match.firstElement() ) );
+        ASSERT( !regex.matchesSingleElement( notMatch.firstElement() ) );
+    }
+
+    TEST( RegexExpression, MatchesElementWrongType ) {
+        BSONObj notMatchInt = BSON( "x" << 1 );
+        BSONObj notMatchBool = BSON( "x" << true );
+        RegexExpression regex;
+        ASSERT( regex.init( "", "1", "" ).isOK() );
+        ASSERT( !regex.matchesSingleElement( notMatchInt.firstElement() ) );
+        ASSERT( !regex.matchesSingleElement( notMatchBool.firstElement() ) );
+    }
+
+    TEST( RegexExpression, MatchesElementUtf8 ) {
+        BSONObj multiByteCharacter = BSON( "x" << "\xc2\xa5" );
+        RegexExpression regex;
+        ASSERT( regex.init( "", "^.$", "" ).isOK() );
+        ASSERT( regex.matchesSingleElement( multiByteCharacter.firstElement() ) );
+    }
+
+    TEST( RegexExpression, MatchesScalar ) {
+        RegexExpression regex;
+        ASSERT( regex.init( "a", "b", "" ).isOK() );
+        ASSERT( regex.matches( BSON( "a" << "b" ), NULL ) );
+        ASSERT( !regex.matches( BSON( "a" << "c" ), NULL ) );
+    }
+
+    TEST( RegexExpression, MatchesArrayValue ) {
+        RegexExpression regex;
+        ASSERT( regex.init( "a", "b", "" ).isOK() );
+        ASSERT( regex.matches( BSON( "a" << BSON_ARRAY( "c" << "b" ) ), NULL ) );
+        ASSERT( !regex.matches( BSON( "a" << BSON_ARRAY( "d" << "c" ) ), NULL ) );
+    }
+
+    TEST( RegexExpression, MatchesNull ) {
+        RegexExpression regex;
+        ASSERT( regex.init( "a", "b", "" ).isOK() );
+        ASSERT( !regex.matches( BSONObj(), NULL ) );
+        ASSERT( !regex.matches( BSON( "a" << BSONNULL ), NULL ) );
+    }
+
+    TEST( RegexExpression, ElemMatchKey ) {
+        RegexExpression regex;
+        ASSERT( regex.init( "a", "b", "" ).isOK() );
+        MatchDetails details;
+        details.requestElemMatchKey();
+        ASSERT( !regex.matches( BSON( "a" << "c" ), &details ) );
+        ASSERT( !details.hasElemMatchKey() );
+        ASSERT( regex.matches( BSON( "a" << "b" ), &details ) );
+        ASSERT( !details.hasElemMatchKey() );
+        ASSERT( regex.matches( BSON( "a" << BSON_ARRAY( "c" << "b" ) ), &details ) );
+        ASSERT( details.hasElemMatchKey() );
+        ASSERT_EQUALS( "1", details.elemMatchKey() );
+    }
+
+    /**
+       TEST( RegexExpression, MatchesIndexKeyScalar ) {
+       RegexExpression regex;
+       ASSERT( regex.init( "a", "xyz", "" ).isOK() );
+       IndexSpec indexSpec( BSON( "a" << 1 ) );
+       ASSERT( MatchExpression::PartialMatchResult_True ==
+       regex.matchesIndexKey( BSON( "" << "z xyz" ), indexSpec ) );
+       ASSERT( MatchExpression::PartialMatchResult_False ==
+       regex.matchesIndexKey( BSON( "" << "xy" ), indexSpec ) );
+       ASSERT( MatchExpression::PartialMatchResult_False ==
+       regex.matchesIndexKey( BSON( "" << BSON_ARRAY( "xyz" ) ), indexSpec ) );
+       }
+
+       TEST( RegexExpression, MatchesIndexKeyMissing ) {
+       RegexExpression regex;
+       ASSERT( regex.init( "a", "xyz", "" ).isOK() );
+       IndexSpec indexSpec( BSON( "b" << 1 ) );
+       ASSERT( MatchExpression::PartialMatchResult_Unknown ==
+       regex.matchesIndexKey( BSON( "" << "z xyz" ), indexSpec ) );
+       ASSERT( MatchExpression::PartialMatchResult_Unknown ==
+       regex.matchesIndexKey( BSON( "" << "xy" ), indexSpec ) );
+       ASSERT( MatchExpression::PartialMatchResult_Unknown ==
+       regex.matchesIndexKey( BSON( "" << BSON_ARRAY( 8 << "xyz" ) ), indexSpec ) );
+       }
+
+       TEST( RegexExpression, MatchesIndexKeyArrayValue ) {
+       RegexExpression regex;
+       ASSERT( regex.init( "a", "xyz", "" ).isOK() );
+       IndexSpec indexSpec( BSON( "loc" << "mockarrayvalue" << "a" << 1 ) );
+       ASSERT( MatchExpression::PartialMatchResult_True ==
+       regex.matchesIndexKey( BSON( "" << "dummygeohash" << "" << "xyz" ), indexSpec ) );
+       ASSERT( MatchExpression::PartialMatchResult_False ==
+       regex.matchesIndexKey( BSON( "" << "dummygeohash" << "" << "z" ), indexSpec ) );
+       ASSERT( MatchExpression::PartialMatchResult_True ==
+       regex.matchesIndexKey( BSON( "" << "dummygeohash" <<
+       "" << BSON_ARRAY( "r" << 6 << "xyz" ) ), indexSpec ) );
+       }
+    */
+
+    TEST( ModExpression, MatchesElement ) {
+        BSONObj match = BSON( "a" << 1 );
+        BSONObj largerMatch = BSON( "a" << 4.0 );
+        BSONObj longLongMatch = BSON( "a" << 68719476736LL );
+        BSONObj notMatch = BSON( "a" << 6 );
+        BSONObj negativeNotMatch = BSON( "a" << -2 );
+        ModExpression mod;
+        ASSERT( mod.init( "", 3, 1 ).isOK() );
+        ASSERT( mod.matchesSingleElement( match.firstElement() ) );
+        ASSERT( mod.matchesSingleElement( largerMatch.firstElement() ) );
+        ASSERT( mod.matchesSingleElement( longLongMatch.firstElement() ) );
+        ASSERT( !mod.matchesSingleElement( notMatch.firstElement() ) );
+        ASSERT( !mod.matchesSingleElement( negativeNotMatch.firstElement() ) );
+    }
+
+    TEST( ModExpression, ZeroDivisor ) {
+        ModExpression mod;
+        ASSERT( !mod.init( "", 0, 1 ).isOK() );
+    }
+
+    TEST( ModExpression, MatchesScalar ) {
+        ModExpression mod;
+        ASSERT( mod.init( "a", 5, 2 ).isOK() );
+        ASSERT( mod.matches( BSON( "a" << 7.0 ), NULL ) );
+        ASSERT( !mod.matches( BSON( "a" << 4 ), NULL ) );
+    }
+
+    TEST( ModExpression, MatchesArrayValue ) {
+        ModExpression mod;
+        ASSERT( mod.init( "a", 5, 2 ).isOK() );
+        ASSERT( mod.matches( BSON( "a" << BSON_ARRAY( 5 << 12LL ) ), NULL ) );
+        ASSERT( !mod.matches( BSON( "a" << BSON_ARRAY( 6 << 8 ) ), NULL ) );
+    }
+
+    TEST( ModExpression, MatchesNull ) {
+        ModExpression mod;
+        ASSERT( mod.init( "a", 5, 2 ).isOK() );
+        ASSERT( !mod.matches( BSONObj(), NULL ) );
+        ASSERT( !mod.matches( BSON( "a" << BSONNULL ), NULL ) );
+    }
+
+    TEST( ModExpression, ElemMatchKey ) {
+        ModExpression mod;
+        ASSERT( mod.init( "a", 5, 2 ).isOK() );
+        MatchDetails details;
+        details.requestElemMatchKey();
+        ASSERT( !mod.matches( BSON( "a" << 4 ), &details ) );
+        ASSERT( !details.hasElemMatchKey() );
+        ASSERT( mod.matches( BSON( "a" << 2 ), &details ) );
+        ASSERT( !details.hasElemMatchKey() );
+        ASSERT( mod.matches( BSON( "a" << BSON_ARRAY( 1 << 2 << 5 ) ), &details ) );
+        ASSERT( details.hasElemMatchKey() );
+        ASSERT_EQUALS( "1", details.elemMatchKey() );
+    }
+    /**
+       TEST( ModExpression, MatchesIndexKey ) {
+       BSONObj operand = BSON( "$mod" << BSON_ARRAY( 2 << 1 ) );
+       ModExpression mod;
+       ASSERT( mod.init( "a", operand[ "$mod" ] ).isOK() );
+       IndexSpec indexSpec( BSON( "a" << 1 ) );
+       BSONObj indexKey = BSON( "" << 1 );
+       ASSERT( MatchExpression::PartialMatchResult_Unknown ==
+       mod.matchesIndexKey( indexKey, indexSpec ) );
+       }
+    */
+
+    TEST( ExistsExpression, MatchesElement ) {
+        BSONObj existsInt = BSON( "a" << 5 );
+        BSONObj existsNull = BSON( "a" << BSONNULL );
+        BSONObj doesntExist = BSONObj();
+        ExistsExpression exists;
+        ASSERT( exists.init( "", true ).isOK() );
+        ASSERT( exists.matchesSingleElement( existsInt.firstElement() ) );
+        ASSERT( exists.matchesSingleElement( existsNull.firstElement() ) );
+        ASSERT( !exists.matchesSingleElement( doesntExist.firstElement() ) );
+    }
+
+    TEST( ExistsExpression, MatchesElementExistsFalse ) {
+        BSONObj existsInt = BSON( "a" << 5 );
+        BSONObj existsNull = BSON( "a" << BSONNULL );
+        BSONObj doesntExist = BSONObj();
+        ExistsExpression exists;
+        ASSERT( exists.init( "", false ).isOK() );
+        ASSERT( !exists.matchesSingleElement( existsInt.firstElement() ) );
+        ASSERT( !exists.matchesSingleElement( existsNull.firstElement() ) );
+        ASSERT( exists.matchesSingleElement( doesntExist.firstElement() ) );
+    }
+
+    TEST( ExistsExpression, MatchesElementExistsTrueValue ) {
+        BSONObj exists = BSON( "a" << 5 );
+        BSONObj missing = BSONObj();
+        ExistsExpression existsTrueValue;
+        ExistsExpression existsFalseValue;
+        ASSERT( existsTrueValue.init( "", true ).isOK() );
+        ASSERT( existsFalseValue.init( "", false ).isOK() );
+        ASSERT( existsTrueValue.matchesSingleElement( exists.firstElement() ) );
+        ASSERT( !existsFalseValue.matchesSingleElement( exists.firstElement() ) );
+        ASSERT( !existsTrueValue.matchesSingleElement( missing.firstElement() ) );
+        ASSERT( existsFalseValue.matchesSingleElement( missing.firstElement() ) );
+    }
+
+    TEST( ExistsExpression, MatchesScalar ) {
+        ExistsExpression exists;
+        ASSERT( exists.init( "a", true ).isOK() );
+        ASSERT( exists.matches( BSON( "a" << 1 ), NULL ) );
+        ASSERT( exists.matches( BSON( "a" << BSONNULL ), NULL ) );
+        ASSERT( !exists.matches( BSON( "b" << 1 ), NULL ) );
+    }
+
+    TEST( ExistsExpression, MatchesScalarFalse ) {
+        ExistsExpression exists;
+        ASSERT( exists.init( "a", false ).isOK() );
+        ASSERT( !exists.matches( BSON( "a" << 1 ), NULL ) );
+        ASSERT( !exists.matches( BSON( "a" << BSONNULL ), NULL ) );
+        ASSERT( exists.matches( BSON( "b" << 1 ), NULL ) );
+    }
+
+    TEST( ExistsExpression, MatchesArray ) {
+        ExistsExpression exists;
+        ASSERT( exists.init( "a", true ).isOK() );
+        ASSERT( exists.matches( BSON( "a" << BSON_ARRAY( 4 << 5.5 ) ), NULL ) );
+    }
+
+    TEST( ExistsExpression, ElemMatchKey ) {
+        ExistsExpression exists;
+        ASSERT( exists.init( "a.b", true ).isOK() );
+        MatchDetails details;
+        details.requestElemMatchKey();
+        ASSERT( !exists.matches( BSON( "a" << 1 ), &details ) );
+        ASSERT( !details.hasElemMatchKey() );
+        ASSERT( exists.matches( BSON( "a" << BSON( "b" << 6 ) ), &details ) );
+        ASSERT( !details.hasElemMatchKey() );
+        ASSERT( exists.matches( BSON( "a" << BSON_ARRAY( 2 << BSON( "b" << 7 ) ) ), &details ) );
+        ASSERT( details.hasElemMatchKey() );
+        ASSERT_EQUALS( "1", details.elemMatchKey() );
+    }
+    /**
+       TEST( ExistsExpression, MatchesIndexKey ) {
+       BSONObj operand = BSON( "$exists" << true );
+       ExistsExpression exists;
+       ASSERT( exists.init( "a", operand[ "$exists" ] ).isOK() );
+       IndexSpec indexSpec( BSON( "a" << 1 ) );
+       BSONObj indexKey = BSON( "" << 1 );
+       ASSERT( MatchExpression::PartialMatchResult_Unknown ==
+       exists.matchesIndexKey( indexKey, indexSpec ) );
+       }
+    */
+
+
+
+    TEST( TypeExpression, MatchesElementStringType ) {
+        BSONObj match = BSON( "a" << "abc" );
+        BSONObj notMatch = BSON( "a" << 5 );
+        TypeExpression type;
+        ASSERT( type.init( "", String ).isOK() );
+        ASSERT( type.matchesSingleElement( match[ "a" ] ) );
+        ASSERT( !type.matchesSingleElement( notMatch[ "a" ] ) );
+    }
+
+    TEST( TypeExpression, MatchesElementNullType ) {
+        BSONObj match = BSON( "a" << BSONNULL );
+        BSONObj notMatch = BSON( "a" << "abc" );
+        TypeExpression type;
+        ASSERT( type.init( "", jstNULL ).isOK() );
+        ASSERT( type.matchesSingleElement( match[ "a" ] ) );
+        ASSERT( !type.matchesSingleElement( notMatch[ "a" ] ) );
+    }
+
+    TEST( TypeExpression, InvalidTypeExpressionerand ) {
+        // If the provided type number is not a valid BSONType, it is not a parse error.  The
+        // operator will simply not match anything.
+        BSONObj notMatch1 = BSON( "a" << BSONNULL );
+        BSONObj notMatch2 = BSON( "a" << "abc" );
+        TypeExpression type;
+        ASSERT( type.init( "", JSTypeMax + 1 ).isOK() );
+        ASSERT( !type.matchesSingleElement( notMatch1[ "a" ] ) );
+        ASSERT( !type.matchesSingleElement( notMatch2[ "a" ] ) );
+    }
+
+    TEST( TypeExpression, MatchesScalar ) {
+        TypeExpression type;
+        ASSERT( type.init( "a", Bool ).isOK() );
+        ASSERT( type.matches( BSON( "a" << true ), NULL ) );
+        ASSERT( !type.matches( BSON( "a" << 1 ), NULL ) );
+    }
+
+    TEST( TypeExpression, MatchesArray ) {
+        TypeExpression type;
+        ASSERT( type.init( "a", NumberInt ).isOK() );
+        ASSERT( type.matches( BSON( "a" << BSON_ARRAY( 4 ) ), NULL ) );
+        ASSERT( type.matches( BSON( "a" << BSON_ARRAY( 4 << "a" ) ), NULL ) );
+        ASSERT( type.matches( BSON( "a" << BSON_ARRAY( "a" << 4 ) ), NULL ) );
+        ASSERT( !type.matches( BSON( "a" << BSON_ARRAY( "a" ) ), NULL ) );
+        ASSERT( !type.matches( BSON( "a" << BSON_ARRAY( BSON_ARRAY( 4 ) ) ), NULL ) );
+    }
+
+    TEST( TypeExpression, MatchesOuterArray ) {
+        TypeExpression type;
+        ASSERT( type.init( "a", Array ).isOK() );
+        // The outer array is not matched.
+        ASSERT( !type.matches( BSON( "a" << BSONArray() ), NULL ) );
+        ASSERT( !type.matches( BSON( "a" << BSON_ARRAY( 4 << "a" ) ), NULL ) );
+        ASSERT( type.matches( BSON( "a" << BSON_ARRAY( BSONArray() << 2 ) ), NULL ) );
+        ASSERT( !type.matches( BSON( "a" << "bar" ), NULL ) );
+    }
+
+    TEST( TypeExpression, MatchesNull ) {
+        TypeExpression type;
+        ASSERT( type.init( "a", jstNULL ).isOK() );
+        ASSERT( type.matches( BSON( "a" << BSONNULL ), NULL ) );
+        ASSERT( !type.matches( BSON( "a" << 4 ), NULL ) );
+        ASSERT( !type.matches( BSONObj(), NULL ) );
+    }
+
+    TEST( TypeExpression, ElemMatchKey ) {
+        TypeExpression type;
+        ASSERT( type.init( "a.b", String ).isOK() );
+        MatchDetails details;
+        details.requestElemMatchKey();
+        ASSERT( !type.matches( BSON( "a" << 1 ), &details ) );
+        ASSERT( !details.hasElemMatchKey() );
+        ASSERT( type.matches( BSON( "a" << BSON( "b" << "string" ) ), &details ) );
+        ASSERT( !details.hasElemMatchKey() );
+        ASSERT( type.matches( BSON( "a" << BSON( "b" << BSON_ARRAY( "string" ) ) ), &details ) );
+        ASSERT( details.hasElemMatchKey() );
+        ASSERT_EQUALS( "0", details.elemMatchKey() );
+        ASSERT( type.matches( BSON( "a" <<
+                                    BSON_ARRAY( 2 <<
+                                                BSON( "b" << BSON_ARRAY( "string" ) ) ) ),
+                              &details ) );
+        ASSERT( details.hasElemMatchKey() );
+        ASSERT_EQUALS( "1", details.elemMatchKey() );
+    }
+    /**
+       TEST( TypeExpression, MatchesIndexKey ) {
+       BSONObj operand = BSON( "$type" << 2 );
+       TypeExpression type;
+       ASSERT( type.init( "a", operand[ "$type" ] ).isOK() );
+       IndexSpec indexSpec( BSON( "a" << 1 ) );
+       BSONObj indexKey = BSON( "" << "q" );
+       ASSERT( MatchExpression::PartialMatchResult_Unknown ==
+       type.matchesIndexKey( indexKey, indexSpec ) );
+       }
+    */
+
+
+    TEST( InExpression, MatchesElementSingle ) {
+        BSONArray operand = BSON_ARRAY( 1 );
+        BSONObj match = BSON( "a" << 1 );
+        BSONObj notMatch = BSON( "a" << 2 );
+        InExpression in;
+        in.getArrayFilterEntries()->addEquality( operand.firstElement() );
+        ASSERT( in.matchesSingleElement( match[ "a" ] ) );
+        ASSERT( !in.matchesSingleElement( notMatch[ "a" ] ) );
+    }
+
+    TEST( InExpression, MatchesEmpty ) {
+        InExpression in;
+        in.init( "a" );
+
+        BSONObj notMatch = BSON( "a" << 2 );
+        ASSERT( !in.matchesSingleElement( notMatch[ "a" ] ) );
+        ASSERT( !in.matches( BSON( "a" << 1 ), NULL ) );
+        ASSERT( !in.matches( BSONObj(), NULL ) );
+    }
+
+    TEST( InExpression, MatchesElementMultiple ) {
+        BSONObj operand = BSON_ARRAY( 1 << "r" << true << 1 );
+        InExpression in;
+        in.getArrayFilterEntries()->addEquality( operand[0] );
+        in.getArrayFilterEntries()->addEquality( operand[1] );
+        in.getArrayFilterEntries()->addEquality( operand[2] );
+        in.getArrayFilterEntries()->addEquality( operand[3] );
+
+        BSONObj matchFirst = BSON( "a" << 1 );
+        BSONObj matchSecond = BSON( "a" << "r" );
+        BSONObj matchThird = BSON( "a" << true );
+        BSONObj notMatch = BSON( "a" << false );
+        ASSERT( in.matchesSingleElement( matchFirst[ "a" ] ) );
+        ASSERT( in.matchesSingleElement( matchSecond[ "a" ] ) );
+        ASSERT( in.matchesSingleElement( matchThird[ "a" ] ) );
+        ASSERT( !in.matchesSingleElement( notMatch[ "a" ] ) );
+    }
+
+
+    TEST( InExpression, MatchesScalar ) {
+        BSONObj operand = BSON_ARRAY( 5 );
+        InExpression in;
+        in.init( "a" );
+        in.getArrayFilterEntries()->addEquality( operand.firstElement() );
+
+        ASSERT( in.matches( BSON( "a" << 5.0 ), NULL ) );
+        ASSERT( !in.matches( BSON( "a" << 4 ), NULL ) );
+    }
+
+    TEST( InExpression, MatchesArrayValue ) {
+        BSONObj operand = BSON_ARRAY( 5 );
+        InExpression in;
+        in.init( "a" );
+        in.getArrayFilterEntries()->addEquality( operand.firstElement() );
+
+        ASSERT( in.matches( BSON( "a" << BSON_ARRAY( 5.0 << 6 ) ), NULL ) );
+        ASSERT( !in.matches( BSON( "a" << BSON_ARRAY( 6 << 7 ) ), NULL ) );
+        ASSERT( !in.matches( BSON( "a" << BSON_ARRAY( BSON_ARRAY( 5 ) ) ), NULL ) );
+    }
+
+    TEST( InExpression, MatchesNull ) {
+        BSONObj operand = BSON_ARRAY( BSONNULL );
+
+        InExpression in;
+        in.init( "a" );
+        in.getArrayFilterEntries()->addEquality( operand.firstElement() );
+
+        ASSERT( in.matches( BSONObj(), NULL ) );
+        ASSERT( in.matches( BSON( "a" << BSONNULL ), NULL ) );
+        ASSERT( !in.matches( BSON( "a" << 4 ), NULL ) );
+    }
+
+    TEST( InExpression, MatchesMinKey ) {
+        BSONObj operand = BSON_ARRAY( MinKey );
+        InExpression in;
+        in.init( "a" );
+        in.getArrayFilterEntries()->addEquality( operand.firstElement() );
+
+        ASSERT( in.matches( BSON( "a" << MinKey ), NULL ) );
+        ASSERT( !in.matches( BSON( "a" << MaxKey ), NULL ) );
+        ASSERT( !in.matches( BSON( "a" << 4 ), NULL ) );
+    }
+
+    TEST( InExpression, MatchesMaxKey ) {
+        BSONObj operand = BSON_ARRAY( MaxKey );
+        InExpression in;
+        in.init( "a" );
+        in.getArrayFilterEntries()->addEquality( operand.firstElement() );
+
+        ASSERT( in.matches( BSON( "a" << MaxKey ), NULL ) );
+        ASSERT( !in.matches( BSON( "a" << MinKey ), NULL ) );
+        ASSERT( !in.matches( BSON( "a" << 4 ), NULL ) );
+    }
+
+    TEST( InExpression, MatchesFullArray ) {
+        BSONObj operand = BSON_ARRAY( BSON_ARRAY( 1 << 2 ) << 4 << 5 );
+        InExpression in;
+        in.init( "a" );
+        in.getArrayFilterEntries()->addEquality( operand[0] );
+        in.getArrayFilterEntries()->addEquality( operand[1] );
+        in.getArrayFilterEntries()->addEquality( operand[2] );
+
+        ASSERT( in.matches( BSON( "a" << BSON_ARRAY( 1 << 2 ) ), NULL ) );
+        ASSERT( !in.matches( BSON( "a" << BSON_ARRAY( 1 << 2 << 3 ) ), NULL ) );
+        ASSERT( !in.matches( BSON( "a" << BSON_ARRAY( 1 ) ), NULL ) );
+        ASSERT( !in.matches( BSON( "a" << 1 ), NULL ) );
+    }
+
+    TEST( InExpression, ElemMatchKey ) {
+        BSONObj operand = BSON_ARRAY( 5 << 2 );
+        InExpression in;
+        in.init( "a" );
+        in.getArrayFilterEntries()->addEquality( operand[0] );
+        in.getArrayFilterEntries()->addEquality( operand[1] );
+
+        MatchDetails details;
+        details.requestElemMatchKey();
+        ASSERT( !in.matches( BSON( "a" << 4 ), &details ) );
+        ASSERT( !details.hasElemMatchKey() );
+        ASSERT( in.matches( BSON( "a" << 5 ), &details ) );
+        ASSERT( !details.hasElemMatchKey() );
+        ASSERT( in.matches( BSON( "a" << BSON_ARRAY( 1 << 2 << 5 ) ), &details ) );
+        ASSERT( details.hasElemMatchKey() );
+        ASSERT_EQUALS( "1", details.elemMatchKey() );
+    }
+
+    /**
+    TEST( InExpression, MatchesIndexKeyScalar ) {
+        BSONObj operand = BSON( "$in" << BSON_ARRAY( 6 << 5 ) );
+        InExpression in;
+        ASSERT( in.init( "a", operand[ "$in" ] ).isOK() );
+        IndexSpec indexSpec( BSON( "a" << 1 ) );
+        ASSERT( MatchExpression::PartialMatchResult_True ==
+                in.matchesIndexKey( BSON( "" << 6 ), indexSpec ) );
+        ASSERT( MatchExpression::PartialMatchResult_True ==
+                in.matchesIndexKey( BSON( "" << 5 ), indexSpec ) );
+        ASSERT( MatchExpression::PartialMatchResult_False ==
+                in.matchesIndexKey( BSON( "" << 4 ), indexSpec ) );
+        ASSERT( MatchExpression::PartialMatchResult_False ==
+                in.matchesIndexKey( BSON( "" << BSON_ARRAY( 6 ) ), indexSpec ) );
+    }
+
+    TEST( InExpression, MatchesIndexKeyMissing ) {
+        BSONObj operand = BSON( "$in" << BSON_ARRAY( 6 ) );
+        ComparisonExpression eq
+            ASSERT( eq.init( "a", operand[ "$in" ] ).isOK() );
+        IndexSpec indexSpec( BSON( "b" << 1 ) );
+        ASSERT( MatchExpression::PartialMatchResult_Unknown ==
+                eq.matchesIndexKey( BSON( "" << 6 ), indexSpec ) );
+        ASSERT( MatchExpression::PartialMatchResult_Unknown ==
+                eq.matchesIndexKey( BSON( "" << 4 ), indexSpec ) );
+        ASSERT( MatchExpression::PartialMatchResult_Unknown ==
+                eq.matchesIndexKey( BSON( "" << BSON_ARRAY( 8 << 6 ) ), indexSpec ) );
+    }
+
+    TEST( InExpression, MatchesIndexKeyArray ) {
+        BSONObj operand = BSON( "$in" << BSON_ARRAY( 4 << BSON_ARRAY( 5 ) ) );
+        InExpression in;
+        ASSERT( in.init( "a", operand[ "$in" ] ).isOK() );
+        IndexSpec indexSpec( BSON( "a" << 1 ) );
+        ASSERT( MatchExpression::PartialMatchResult_Unknown ==
+                in.matchesIndexKey( BSON( "" << 4 ), indexSpec ) );
+        ASSERT( MatchExpression::PartialMatchResult_Unknown ==
+                in.matchesIndexKey( BSON( "" << 5 ), indexSpec ) );
+    }
+    
+    TEST( InExpression, MatchesIndexKeyArrayValue ) {
+        BSONObjBuilder inArray;
+        inArray.append( "0", 4 ).append( "1", 5 ).appendRegex( "2", "abc", "" );
+        BSONObj operand = BSONObjBuilder().appendArray( "$in", inArray.obj() ).obj();
+        InExpression in;
+        ASSERT( in.init( "a", operand[ "$in" ] ).isOK() );
+        IndexSpec indexSpec( BSON( "loc" << "mockarrayvalue" << "a" << 1 ) );
+        ASSERT( MatchExpression::PartialMatchResult_True ==
+                in.matchesIndexKey( BSON( "" << "dummygeohash" << "" << 4 ), indexSpec ) );
+        ASSERT( MatchExpression::PartialMatchResult_False ==
+                in.matchesIndexKey( BSON( "" << "dummygeohash" << "" << 6 ), indexSpec ) );
+        ASSERT( MatchExpression::PartialMatchResult_True ==
+                in.matchesIndexKey( BSON( "" << "dummygeohash" << "" << "abcd" ), indexSpec ) );
+        ASSERT( MatchExpression::PartialMatchResult_True ==
+                in.matchesIndexKey( BSONObjBuilder()
+                                    .append( "", "dummygeohash" )
+                                    .appendRegex( "", "abc", "" ).obj(),
+                                    indexSpec ) );
+        ASSERT( MatchExpression::PartialMatchResult_False ==
+                in.matchesIndexKey( BSON( "" << "dummygeohash" << "" << "ab" ), indexSpec ) );
+        ASSERT( MatchExpression::PartialMatchResult_True ==
+                in.matchesIndexKey( BSON( "" << "dummygeohash" <<
+                                          "" << BSON_ARRAY( 8 << 5 ) ), indexSpec ) );
+        ASSERT( MatchExpression::PartialMatchResult_False ==
+                in.matchesIndexKey( BSON( "" << "dummygeohash" <<
+                                          "" << BSON_ARRAY( 8 << 9 ) ), indexSpec ) );
+        ASSERT( MatchExpression::PartialMatchResult_True ==
+                in.matchesIndexKey( BSON( "" << "dummygeohash" <<
+                                          "" << BSON_ARRAY( 8 << "abc" ) ), indexSpec ) );
+        ASSERT( MatchExpression::PartialMatchResult_False ==
+                in.matchesIndexKey( BSON( "" << "dummygeohash" <<
+                                          "" << BSON_ARRAY( 8 << "ac" ) ), indexSpec ) );
+    }
+    */
+
+    TEST( NinExpression, MatchesElementSingle ) {
+        BSONObj operands = BSON_ARRAY( 1 );
+        BSONObj match = BSON( "a" << 2 );
+        BSONObj notMatch = BSON( "a" << 1 );
+        NinExpression nin;
+        nin.getArrayFilterEntries()->addEquality( operands.firstElement() );
+        ASSERT( nin.matchesSingleElement( match[ "a" ] ) );
+        ASSERT( !nin.matchesSingleElement( notMatch[ "a" ] ) );
+    }
+
+    TEST( NinExpression, MatchesElementMultiple ) {
+        BSONArray operand = BSON_ARRAY( 1 << "r" << true << 1 );
+        BSONObj match = BSON( "a" << false );
+        BSONObj notMatchFirst = BSON( "a" << 1 );
+        BSONObj notMatchSecond = BSON( "a" << "r" );
+        BSONObj notMatchThird = BSON( "a" << true );
+        NinExpression nin;
+        nin.getArrayFilterEntries()->addEquality( operand[0] );
+        nin.getArrayFilterEntries()->addEquality( operand[1] );
+        nin.getArrayFilterEntries()->addEquality( operand[2] );
+        nin.getArrayFilterEntries()->addEquality( operand[3] );
+        ASSERT( nin.matchesSingleElement( match[ "a" ] ) );
+        ASSERT( !nin.matchesSingleElement( notMatchFirst[ "a" ] ) );
+        ASSERT( !nin.matchesSingleElement( notMatchSecond[ "a" ] ) );
+        ASSERT( !nin.matchesSingleElement( notMatchThird[ "a" ] ) );
+    }
+
+    TEST( NinExpression, MatchesScalar ) {
+        BSONObj operand = BSON_ARRAY( 5 );
+        NinExpression nin;
+        nin.init( "a" );
+        nin.getArrayFilterEntries()->addEquality( operand.firstElement() );
+        ASSERT( nin.matches( BSON( "a" << 4 ), NULL ) );
+        ASSERT( !nin.matches( BSON( "a" << 5 ), NULL ) );
+        ASSERT( !nin.matches( BSON( "a" << 5.0 ), NULL ) );
+    }
+
+    TEST( NinExpression, MatchesArrayValue ) {
+        BSONObj operand = BSON_ARRAY( 5 );
+        NinExpression nin;
+        nin.init( "a" );
+        nin.getArrayFilterEntries()->addEquality( operand.firstElement() );
+        ASSERT( !nin.matches( BSON( "a" << BSON_ARRAY( 5.0 << 6 ) ), NULL ) );
+        ASSERT( nin.matches( BSON( "a" << BSON_ARRAY( 6 << 7 ) ), NULL ) );
+        ASSERT( nin.matches( BSON( "a" << BSON_ARRAY( BSON_ARRAY( 5 ) ) ), NULL ) );
+    }
+
+    TEST( NinExpression, MatchesNull ) {
+        BSONObjBuilder ninArray;
+        ninArray.appendNull( "0" );
+        BSONObj operand = ninArray.obj();
+        NinExpression nin;
+        nin.init( "a" );
+        nin.getArrayFilterEntries()->addEquality( operand.firstElement() );
+        ASSERT( !nin.matches( BSONObj(), NULL ) );
+        ASSERT( !nin.matches( BSON( "a" << BSONNULL ), NULL ) );
+        ASSERT( nin.matches( BSON( "a" << 4 ), NULL ) );
+    }
+
+    TEST( NinExpression, MatchesFullArray ) {
+        BSONArray operand = BSON_ARRAY( BSON_ARRAY( 1 << 2 ) << 4 << 5 );
+        NinExpression nin;
+        nin.init( "a" );
+        nin.getArrayFilterEntries()->addEquality( operand[0] );
+        nin.getArrayFilterEntries()->addEquality( operand[1] );
+        nin.getArrayFilterEntries()->addEquality( operand[2] );
+        ASSERT( !nin.matches( BSON( "a" << BSON_ARRAY( 1 << 2 ) ), NULL ) );
+        ASSERT( nin.matches( BSON( "a" << BSON_ARRAY( 1 << 2 << 3 ) ), NULL ) );
+        ASSERT( nin.matches( BSON( "a" << BSON_ARRAY( 1 ) ), NULL ) );
+        ASSERT( nin.matches( BSON( "a" << 1 ), NULL ) );
+    }
+
+    TEST( NinExpression, ElemMatchKey ) {
+        BSONArray operand = BSON_ARRAY( 5 << 2 );
+        NinExpression nin;
+        nin.init( "a" );
+        nin.getArrayFilterEntries()->addEquality( operand[0] );
+        nin.getArrayFilterEntries()->addEquality( operand[1] );
+
+        MatchDetails details;
+        details.requestElemMatchKey();
+        ASSERT( !nin.matches( BSON( "a" << 2 ), &details ) );
+        ASSERT( !details.hasElemMatchKey() );
+        ASSERT( nin.matches( BSON( "a" << 3 ), &details ) );
+        ASSERT( !details.hasElemMatchKey() );
+        ASSERT( nin.matches( BSON( "a" << BSON_ARRAY( 1 << 3 << 6 ) ), &details ) );
+        // The elemMatchKey feature is not implemented for $nin.
+        ASSERT( !details.hasElemMatchKey() );
+    }
+
+    /**
+    TEST( NinExpression, MatchesIndexKey ) {
+        BSONObj operand = BSON( "$nin" << BSON_ARRAY( 5 ) );
+        NinExpression nin;
+        ASSERT( nin.init( "a", operand[ "$nin" ] ).isOK() );
+        IndexSpec indexSpec( BSON( "a" << 1 ) );
+        BSONObj indexKey = BSON( "" << "7" );
+        ASSERT( MatchExpression::PartialMatchResult_Unknown ==
+                nin.matchesIndexKey( indexKey, indexSpec ) );
+    }
+    */
+
+}
diff --git a/src/mongo/db/matcher/expression_parser.cpp b/src/mongo/db/matcher/expression_parser.cpp
new file mode 100644
index 00000000000..ccebeef0aea
--- /dev/null
+++ b/src/mongo/db/matcher/expression_parser.cpp
@@ -0,0 +1,484 @@
+// expression_parser.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/>.
+ */
+
+#include "mongo/db/matcher/expression_parser.h"
+
+#include "mongo/bson/bsonmisc.h"
+#include "mongo/bson/bsonobj.h"
+#include "mongo/bson/bsonobjbuilder.h"
+#include "mongo/bson/bsonobjiterator.h"
+#include "mongo/db/matcher/expression_array.h"
+#include "mongo/db/matcher/expression_leaf.h"
+#include "mongo/db/matcher/expression_tree.h"
+#include "mongo/util/log.h"
+#include "mongo/util/mongoutils/str.h"
+
+namespace mongo {
+
+    StatusWithExpression ExpressionParser::_parseComparison( const char* name,
+                                                                ComparisonExpression::Type cmp,
+                                                                const BSONElement& e ) {
+        std::auto_ptr<ComparisonExpression> temp( new ComparisonExpression() );
+
+        Status s = temp->init( name, cmp, e );
+        if ( !s.isOK() )
+            return StatusWithExpression(s);
+
+        return StatusWithExpression( temp.release() );
+    }
+
+    StatusWithExpression ExpressionParser::_parseSubField( const char* name,
+                                                           const BSONElement& e ) {
+
+        // TODO: these should move to getGtLtOp, or its replacement
+
+        if ( mongoutils::str::equals( "$eq", e.fieldName() ) )
+            return _parseComparison( name, ComparisonExpression::EQ, e );
+
+        if ( mongoutils::str::equals( "$not", e.fieldName() ) ) {
+            return _parseNot( name, e );
+        }
+
+
+        int x = e.getGtLtOp(-1);
+        switch ( x ) {
+        case -1:
+            return StatusWithExpression( ErrorCodes::BadValue,
+                                         mongoutils::str::stream() << "unknown operator: "
+                                         << e.fieldName() );
+        case BSONObj::LT:
+            return _parseComparison( name, ComparisonExpression::LT, e );
+        case BSONObj::LTE:
+            return _parseComparison( name, ComparisonExpression::LTE, e );
+        case BSONObj::GT:
+            return _parseComparison( name, ComparisonExpression::GT, e );
+        case BSONObj::GTE:
+            return _parseComparison( name, ComparisonExpression::GTE, e );
+        case BSONObj::NE:
+            return _parseComparison( name, ComparisonExpression::NE, e );
+        case BSONObj::Equality:
+            return _parseComparison( name, ComparisonExpression::EQ, e );
+
+        case BSONObj::opIN: {
+            if ( e.type() != Array )
+                return StatusWithExpression( ErrorCodes::BadValue, "$in needs an array" );
+            std::auto_ptr<InExpression> temp( new InExpression() );
+            temp->init( name );
+            Status s = _parseArrayFilterEntries( temp->getArrayFilterEntries(), e.Obj() );
+            if ( !s.isOK() )
+                return StatusWithExpression( s );
+            return StatusWithExpression( temp.release() );
+        }
+
+        case BSONObj::NIN: {
+            if ( e.type() != Array )
+                return StatusWithExpression( ErrorCodes::BadValue, "$nin needs an array" );
+            std::auto_ptr<NinExpression> temp( new NinExpression() );
+            temp->init( name );
+            Status s = _parseArrayFilterEntries( temp->getArrayFilterEntries(), e.Obj() );
+            if ( !s.isOK() )
+                return StatusWithExpression( s );
+            return StatusWithExpression( temp.release() );
+        }
+
+        case BSONObj::opSIZE: {
+            int size = 0;
+            if ( e.type() == String ) {
+                // matching old odd semantics
+                size = 0;
+            }
+            else if ( e.type() == NumberInt || e.type() == NumberLong ) {
+                size = e.numberInt();
+            }
+            else if ( e.type() == NumberDouble ) {
+                if ( e.numberInt() == e.numberDouble() ) {
+                    size = e.numberInt();
+                }
+                else {
+                    // old semantcs require exact numeric match
+                    // so [1,2] != 1 or 2
+                    size = -1;
+                }
+            }
+            else {
+                return StatusWithExpression( ErrorCodes::BadValue, "$size needs a number" );
+            }
+
+            std::auto_ptr<SizeExpression> temp( new SizeExpression() );
+            Status s = temp->init( name, size );
+            if ( !s.isOK() )
+                return StatusWithExpression( s );
+            return StatusWithExpression( temp.release() );
+        }
+
+        case BSONObj::opEXISTS: {
+            if ( e.eoo() )
+                return StatusWithExpression( ErrorCodes::BadValue, "$exists can't be eoo" );
+            std::auto_ptr<ExistsExpression> temp( new ExistsExpression() );
+            Status s = temp->init( name, e.trueValue() );
+            if ( !s.isOK() )
+                return StatusWithExpression( s );
+            return StatusWithExpression( temp.release() );
+        }
+
+        case BSONObj::opTYPE: {
+            if ( !e.isNumber() )
+                return StatusWithExpression( ErrorCodes::BadValue, "$type has to be a number" );
+            int type = e.numberInt();
+            if ( e.type() != NumberInt && type != e.number() )
+                type = -1;
+            std::auto_ptr<TypeExpression> temp( new TypeExpression() );
+            Status s = temp->init( name, type );
+            if ( !s.isOK() )
+                return StatusWithExpression( s );
+            return StatusWithExpression( temp.release() );
+        }
+
+
+        case BSONObj::opMOD:
+            return _parseMOD( name, e );
+
+        case BSONObj::opOPTIONS:
+            return StatusWithExpression( ErrorCodes::BadValue, "$options has to be after a $regex" );
+
+        case BSONObj::opELEM_MATCH:
+            return _parseElemMatch( name, e );
+
+        case BSONObj::opALL:
+            return _parseAll( name, e );
+
+        default:
+            return StatusWithExpression( ErrorCodes::BadValue, "not done" );
+        }
+
+    }
+
+    StatusWithExpression ExpressionParser::parse( const BSONObj& obj ) {
+
+        std::auto_ptr<AndExpression> root( new AndExpression() );
+
+        BSONObjIterator i( obj );
+        while ( i.more() ){
+
+            BSONElement e = i.next();
+            if ( e.fieldName()[0] == '$' ) {
+                const char * rest = e.fieldName() + 1;
+
+                // TODO: optimize if block?
+                if ( mongoutils::str::equals( "or", rest ) ) {
+                    if ( e.type() != Array )
+                        return StatusWithExpression( ErrorCodes::BadValue,
+                                                     "$or needs an array" );
+                    std::auto_ptr<OrExpression> temp( new OrExpression() );
+                    Status s = _parseTreeList( e.Obj(), temp.get() );
+                    if ( !s.isOK() )
+                        return StatusWithExpression( s );
+                    root->add( temp.release() );
+                }
+                else if ( mongoutils::str::equals( "and", rest ) ) {
+                    if ( e.type() != Array )
+                        return StatusWithExpression( ErrorCodes::BadValue,
+                                                     "and needs an array" );
+                    std::auto_ptr<AndExpression> temp( new AndExpression() );
+                    Status s = _parseTreeList( e.Obj(), temp.get() );
+                    if ( !s.isOK() )
+                        return StatusWithExpression( s );
+                    root->add( temp.release() );
+                }
+                else if ( mongoutils::str::equals( "nor", rest ) ) {
+                    if ( e.type() != Array )
+                        return StatusWithExpression( ErrorCodes::BadValue,
+                                                     "and needs an array" );
+                    std::auto_ptr<NorExpression> temp( new NorExpression() );
+                    Status s = _parseTreeList( e.Obj(), temp.get() );
+                    if ( !s.isOK() )
+                        return StatusWithExpression( s );
+                    root->add( temp.release() );
+                }
+                else {
+                    return StatusWithExpression( ErrorCodes::BadValue,
+                                                 mongoutils::str::stream()
+                                                 << "unkown operator: "
+                                                 << e.fieldName() );
+                }
+
+                continue;
+            }
+
+            if ( e.type() == Object && e.Obj().firstElement().fieldName()[0] == '$' ) {
+                Status s = _parseSub( e.fieldName(), e.Obj(), root.get() );
+                if ( !s.isOK() )
+                    return StatusWithExpression( s );
+                continue;
+            }
+
+            if ( e.type() == RegEx ) {
+                StatusWithExpression result = _parseRegexElement( e.fieldName(), e );
+                if ( !result.isOK() )
+                    return result;
+                root->add( result.getValue() );
+                continue;
+            }
+
+            std::auto_ptr<ComparisonExpression> eq( new ComparisonExpression() );
+            Status s = eq->init( e.fieldName(), ComparisonExpression::EQ, e );
+            if ( !s.isOK() )
+                return StatusWithExpression( s );
+
+            root->add( eq.release() );
+        }
+
+        return StatusWithExpression( root.release() );
+    }
+
+    Status ExpressionParser::_parseSub( const char* name,
+                                        const BSONObj& sub,
+                                        AndExpression* root ) {
+
+        bool first = true;
+
+        BSONObjIterator j( sub );
+        while ( j.more() ) {
+            BSONElement deep = j.next();
+
+            int op = deep.getGtLtOp();
+            if ( op == BSONObj::opREGEX ) {
+                if ( !first )
+                    return Status( ErrorCodes::BadValue, "$regex has to be first" );
+
+                StatusWithExpression s = _parseRegexDocument( name, sub );
+                if ( !s.isOK() )
+                    return s.getStatus();
+                root->add( s.getValue() );
+                return Status::OK();
+            }
+
+            StatusWithExpression s = _parseSubField( name, deep );
+            if ( !s.isOK() )
+                return s.getStatus();
+            root->add( s.getValue() );
+        }
+        return Status::OK();
+    }
+
+
+
+    StatusWithExpression ExpressionParser::_parseMOD( const char* name,
+                                                      const BSONElement& e ) {
+
+        if ( e.type() != Array )
+            return StatusWithExpression( ErrorCodes::BadValue, "malformed mod, needs to be an array" );
+
+        BSONObjIterator i( e.Obj() );
+
+        if ( !i.more() )
+            return StatusWithExpression( ErrorCodes::BadValue, "malformed mod, not enough elements" );
+        BSONElement d = i.next();
+        if ( !d.isNumber() )
+            return StatusWithExpression( ErrorCodes::BadValue, "malformed mod, divisor not a number" );
+
+        if ( !i.more() )
+            return StatusWithExpression( ErrorCodes::BadValue, "malformed mod, not enough elements" );
+        BSONElement r = i.next();
+        if ( !d.isNumber() )
+            return StatusWithExpression( ErrorCodes::BadValue, "malformed mod, remainder not a number" );
+
+        if ( i.more() )
+            return StatusWithExpression( ErrorCodes::BadValue, "malformed mod, too many elements" );
+
+        std::auto_ptr<ModExpression> temp( new ModExpression() );
+        Status s = temp->init( name, d.numberInt(), r.numberInt() );
+        if ( !s.isOK() )
+            return StatusWithExpression( s );
+        return StatusWithExpression( temp.release() );
+    }
+
+    StatusWithExpression ExpressionParser::_parseRegexElement( const char* name,
+                                                               const BSONElement& e ) {
+        if ( e.type() != RegEx )
+            return StatusWithExpression( ErrorCodes::BadValue, "not a regex" );
+
+        std::auto_ptr<RegexExpression> temp( new RegexExpression() );
+        Status s = temp->init( name, e.regex(), e.regexFlags() );
+        if ( !s.isOK() )
+            return StatusWithExpression( s );
+        return StatusWithExpression( temp.release() );
+    }
+
+    StatusWithExpression ExpressionParser::_parseRegexDocument( const char* name,
+                                                                const BSONObj& doc ) {
+        string regex;
+        string regexOptions;
+
+        BSONObjIterator i( doc );
+        while ( i.more() ) {
+            BSONElement e = i.next();
+            switch ( e.getGtLtOp() ) {
+            case BSONObj::opREGEX:
+                if ( e.type() != String )
+                    return StatusWithExpression( ErrorCodes::BadValue,
+                                                 "$regex has to be a string" );
+                regex = e.String();
+                break;
+            case BSONObj::opOPTIONS:
+                if ( e.type() != String )
+                    return StatusWithExpression( ErrorCodes::BadValue,
+                                                 "$options has to be a string" );
+                regexOptions = e.String();
+                break;
+            default:
+                return StatusWithExpression( ErrorCodes::BadValue,
+                                             mongoutils::str::stream()
+                                             << "bad $regex doc option: " << e.fieldName() );
+            }
+
+        }
+
+        std::auto_ptr<RegexExpression> temp( new RegexExpression() );
+        Status s = temp->init( name, regex, regexOptions );
+        if ( !s.isOK() )
+            return StatusWithExpression( s );
+        return StatusWithExpression( temp.release() );
+
+    }
+
+    Status ExpressionParser::_parseArrayFilterEntries( ArrayFilterEntries* entries,
+                                                       const BSONObj& theArray ) {
+
+
+        BSONObjIterator i( theArray );
+        while ( i.more() ) {
+            BSONElement e = i.next();
+
+            if ( e.type() == RegEx ) {
+                std::auto_ptr<RegexExpression> r( new RegexExpression() );
+                Status s = r->init( "", e );
+                if ( !s.isOK() )
+                    return s;
+                s =  entries->addRegex( r.release() );
+                if ( !s.isOK() )
+                    return s;
+            }
+            else {
+                Status s = entries->addEquality( e );
+                if ( !s.isOK() )
+                    return s;
+            }
+        }
+        return Status::OK();
+
+    }
+
+    StatusWithExpression ExpressionParser::_parseElemMatch( const char* name,
+                                                            const BSONElement& e ) {
+        if ( e.type() != Object )
+            return StatusWithExpression( ErrorCodes::BadValue, "$elemMatch needs an Object" );
+
+        BSONObj obj = e.Obj();
+        if ( obj.firstElement().fieldName()[0] == '$' ) {
+            // value case
+
+            AndExpression theAnd;
+            Status s = _parseSub( "", obj, &theAnd );
+            if ( !s.isOK() )
+                return StatusWithExpression( s );
+
+            std::auto_ptr<ElemMatchValueExpression> temp( new ElemMatchValueExpression() );
+            s = temp->init( name );
+            if ( !s.isOK() )
+                return StatusWithExpression( s );
+
+            for ( size_t i = 0; i < theAnd.size(); i++ ) {
+                temp->add( theAnd.get( i ) );
+            }
+            theAnd.clearAndRelease();
+
+            return StatusWithExpression( temp.release() );
+        }
+
+        // object case
+
+        StatusWithExpression sub = parse( obj );
+        if ( !sub.isOK() )
+            return sub;
+
+        std::auto_ptr<ElemMatchObjectExpression> temp( new ElemMatchObjectExpression() );
+        Status status = temp->init( name, sub.getValue() );
+        if ( !status.isOK() )
+            return StatusWithExpression( status );
+
+        return StatusWithExpression( temp.release() );
+    }
+
+    StatusWithExpression ExpressionParser::_parseAll( const char* name,
+                                                      const BSONElement& e ) {
+        if ( e.type() != Array )
+            return StatusWithExpression( ErrorCodes::BadValue, "$all needs an array" );
+
+        BSONObj arr = e.Obj();
+        if ( arr.firstElement().type() == Object &&
+             mongoutils::str::equals( "$elemMatch",
+                                      arr.firstElement().Obj().firstElement().fieldName() ) ) {
+            // $all : [ { $elemMatch : {} } ... ]
+
+            std::auto_ptr<AllElemMatchOp> temp( new AllElemMatchOp() );
+            Status s = temp->init( name );
+            if ( !s.isOK() )
+                return StatusWithExpression( s );
+
+            BSONObjIterator i( arr );
+            while ( i.more() ) {
+                BSONElement hopefullyElemMatchElemennt = i.next();
+
+                if ( hopefullyElemMatchElemennt.type() != Object ) {
+                    // $all : [ { $elemMatch : ... }, 5 ]
+                    return StatusWithExpression( ErrorCodes::BadValue,
+                                                 "$all/$elemMatch has to be consistent" );
+                }
+
+                BSONObj hopefullyElemMatchObj = hopefullyElemMatchElemennt.Obj();
+                if ( !mongoutils::str::equals( "$elemMatch",
+                                               hopefullyElemMatchObj.firstElement().fieldName() ) ) {
+                    // $all : [ { $elemMatch : ... }, { x : 5 } ]
+                    return StatusWithExpression( ErrorCodes::BadValue,
+                                                 "$all/$elemMatch has to be consistent" );
+                }
+
+                StatusWithExpression inner = _parseElemMatch( "", hopefullyElemMatchObj.firstElement() );
+                if ( !inner.isOK() )
+                    return inner;
+                temp->add( static_cast<ArrayMatchingExpression*>( inner.getValue() ) );
+            }
+
+            return StatusWithExpression( temp.release() );
+        }
+
+        std::auto_ptr<AllExpression> temp( new AllExpression() );
+        Status s = temp->init( name );
+        if ( !s.isOK() )
+            return StatusWithExpression( s );
+
+        s = _parseArrayFilterEntries( temp->getArrayFilterEntries(), arr );
+        if ( !s.isOK() )
+            return StatusWithExpression( s );
+
+        return StatusWithExpression( temp.release() );
+    }
+
+
+}
diff --git a/src/mongo/db/matcher/expression_parser.h b/src/mongo/db/matcher/expression_parser.h
new file mode 100644
index 00000000000..2655da3f556
--- /dev/null
+++ b/src/mongo/db/matcher/expression_parser.h
@@ -0,0 +1,87 @@
+// expression_parser.h
+
+/**
+ *    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/>.
+ */
+
+#pragma once
+
+#include "mongo/base/status.h"
+#include "mongo/base/status_with.h"
+#include "mongo/db/matcher/expression.h"
+#include "mongo/db/matcher/expression_leaf.h"
+#include "mongo/db/matcher/expression_tree.h"
+
+namespace mongo {
+
+    typedef StatusWith<Expression*> StatusWithExpression;
+
+    class ExpressionParser {
+    public:
+        static StatusWithExpression parse( const BSONObj& obj );
+
+    private:
+
+        /**
+         * parses a field in a sub expression
+         * if the query is { x : { $gt : 5, $lt : 8 } }
+         * e is { $gt : 5, $lt : 8 }
+         */
+        static Status _parseSub( const char* name,
+                                 const BSONObj& obj,
+                                 AndExpression* root );
+
+        /**
+         * parses a single field in a sub expression
+         * if the query is { x : { $gt : 5, $lt : 8 } }
+         * e is $gt : 5
+         */
+        static StatusWithExpression _parseSubField( const char* name,
+                                                    const BSONElement& e );
+
+        static StatusWithExpression _parseComparison( const char* name,
+                                                      ComparisonExpression::Type cmp,
+                                                      const BSONElement& e );
+
+        static StatusWithExpression _parseMOD( const char* name,
+                                               const BSONElement& e );
+
+        static StatusWithExpression _parseRegexElement( const char* name,
+                                                        const BSONElement& e );
+
+        static StatusWithExpression _parseRegexDocument( const char* name,
+                                                         const BSONObj& doc );
+
+
+        static Status _parseArrayFilterEntries( ArrayFilterEntries* entries,
+                                                const BSONObj& theArray );
+
+        // arrays
+
+        static StatusWithExpression _parseElemMatch( const char* name,
+                                                     const BSONElement& e );
+
+        static StatusWithExpression _parseAll( const char* name,
+                                               const BSONElement& e );
+
+        // tree
+
+        static Status _parseTreeList( const BSONObj& arr, ListOfExpression* out );
+
+        static StatusWithExpression _parseNot( const char* name, const BSONElement& e );
+
+    };
+
+}
diff --git a/src/mongo/db/matcher/expression_parser_array_test.cpp b/src/mongo/db/matcher/expression_parser_array_test.cpp
new file mode 100644
index 00000000000..ed4d091b6d0
--- /dev/null
+++ b/src/mongo/db/matcher/expression_parser_array_test.cpp
@@ -0,0 +1,195 @@
+// expression_parser_array_test.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/>.
+ */
+
+#include "mongo/unittest/unittest.h"
+
+#include "mongo/db/matcher/expression_parser.h"
+
+#include "mongo/bson/bsonobj.h"
+#include "mongo/bson/bsonobjbuilder.h"
+#include "mongo/bson/bsonmisc.h"
+#include "mongo/db/json.h"
+#include "mongo/db/matcher.h"
+#include "mongo/db/matcher/expression.h"
+#include "mongo/db/matcher/expression_array.h"
+
+namespace mongo {
+
+    TEST( ExpressionParserArrayTest, Size1 ) {
+        BSONObj query = BSON( "x" << BSON( "$size" << 2 ) );
+        StatusWithExpression result = ExpressionParser::parse( query );
+        ASSERT_TRUE( result.isOK() );
+
+        ASSERT( !result.getValue()->matches( BSON( "x" << 1 ) ) );
+        ASSERT( result.getValue()->matches( BSON( "x" << BSON_ARRAY( 1 << 2 ) ) ) );
+        ASSERT( !result.getValue()->matches( BSON( "x" << BSON_ARRAY( 1  ) ) ) );
+        ASSERT( !result.getValue()->matches( BSON( "x" << BSON_ARRAY( 1 << 2 << 3 ) ) ) );
+    }
+
+    TEST( ExpressionParserArrayTest, SizeAsString ) {
+        BSONObj query = BSON( "x" << BSON( "$size" << "a" ) );
+        StatusWithExpression result = ExpressionParser::parse( query );
+        ASSERT_TRUE( result.isOK() );
+
+        ASSERT( !result.getValue()->matches( BSON( "x" << 1 ) ) );
+        ASSERT( !result.getValue()->matches( BSON( "x" << BSON_ARRAY( 1 << 2 ) ) ) );
+        ASSERT( result.getValue()->matches( BSON( "x" << BSONArray() ) ) );
+        ASSERT( !result.getValue()->matches( BSON( "x" << BSON_ARRAY( 1 ) ) ) );
+    }
+
+    TEST( ExpressionParserArrayTest, SizeWithDouble ) {
+        BSONObj query = BSON( "x" << BSON( "$size" << 2.5 ) );
+        StatusWithExpression result = ExpressionParser::parse( query );
+        ASSERT_TRUE( result.isOK() );
+
+        ASSERT( !result.getValue()->matches( BSON( "x" << 1 ) ) );
+        ASSERT( !result.getValue()->matches( BSON( "x" << BSON_ARRAY( 1 << 2 ) ) ) );
+        ASSERT( !result.getValue()->matches( BSON( "x" << BSON_ARRAY( 1  ) ) ) );
+        ASSERT( !result.getValue()->matches( BSON( "x" << BSONArray() ) ) );
+        ASSERT( !result.getValue()->matches( BSON( "x" << BSON_ARRAY( 1 << 2 << 3 ) ) ) );
+    }
+
+    TEST( ExpressionParserArrayTest, SizeBad ) {
+        BSONObj query = BSON( "x" << BSON( "$size" << BSONNULL ) );
+        StatusWithExpression result = ExpressionParser::parse( query );
+        ASSERT_FALSE( result.isOK() );
+    }
+
+    // ---------
+
+    TEST( ExpressionParserArrayTest, ElemMatchArr1 ) {
+        BSONObj query = BSON( "x" << BSON( "$elemMatch" << BSON( "x" << 1 << "y" << 2 ) ) );
+        StatusWithExpression result = ExpressionParser::parse( query );
+        ASSERT_TRUE( result.isOK() );
+
+        ASSERT( !result.getValue()->matches( BSON( "x" << 1 ) ) );
+        ASSERT( !result.getValue()->matches( BSON( "x" << BSON_ARRAY( 1 << 2 ) ) ) );
+        ASSERT( !result.getValue()->matches( BSON( "x" << BSON_ARRAY(  BSON( "x" << 1 ) ) ) ) );
+        ASSERT( result.getValue()->matches( BSON( "x" <<
+                                                  BSON_ARRAY( BSON( "x" << 1 << "y" << 2 ) ) ) ) );
+
+    }
+
+    TEST( ExpressionParserArrayTest, ElemMatchVal1 ) {
+        BSONObj query = BSON( "x" << BSON( "$elemMatch" << BSON( "$gt" << 5 ) ) );
+        StatusWithExpression result = ExpressionParser::parse( query );
+        ASSERT_TRUE( result.isOK() );
+
+        ASSERT( !result.getValue()->matches( BSON( "x" << 1 ) ) );
+        ASSERT( !result.getValue()->matches( BSON( "x" << BSON_ARRAY( 4 ) ) ) );
+        ASSERT( result.getValue()->matches( BSON( "x" << BSON_ARRAY( 6 ) ) ) );
+    }
+
+    TEST( ExpressionParserArrayTest, All1 ) {
+        BSONObj query = BSON( "x" << BSON( "$all" << BSON_ARRAY( 1 << 2 ) ) );
+        StatusWithExpression result = ExpressionParser::parse( query );
+        ASSERT_TRUE( result.isOK() );
+
+        ASSERT( !result.getValue()->matches( BSON( "x" << 1 ) ) );
+        ASSERT( !result.getValue()->matches( BSON( "x" << BSON_ARRAY( 1 ) ) ) );
+        ASSERT( !result.getValue()->matches( BSON( "x" << BSON_ARRAY( 2 ) ) ) );
+        ASSERT( result.getValue()->matches( BSON( "x" << BSON_ARRAY( 1 << 2 ) ) ) );
+        ASSERT( result.getValue()->matches( BSON( "x" << BSON_ARRAY( 1 << 2 << 3 ) ) ) );
+        ASSERT( !result.getValue()->matches( BSON( "x" << BSON_ARRAY( 2 << 3 ) ) ) );
+    }
+
+    TEST( ExpressionParserArrayTest, AllBadArg ) {
+        BSONObj query = BSON( "x" << BSON( "$all" << 1 ) );
+        StatusWithExpression result = ExpressionParser::parse( query );
+        ASSERT_FALSE( result.isOK() );
+    }
+
+    TEST( ExpressionParserArrayTest, AllBadRegexArg ) {
+        string tooLargePattern( 50 * 1000, 'z' );
+        BSONObjBuilder allArray;
+        allArray.appendRegex( "0", tooLargePattern, "" );
+        BSONObjBuilder operand;
+        operand.appendArray( "$all", allArray.obj() );
+
+        BSONObj query = BSON( "x" << operand.obj() );
+
+        StatusWithExpression result = ExpressionParser::parse( query );
+        ASSERT_FALSE( result.isOK() );
+    }
+
+
+    TEST( ExpressionParserArrayTest, AllRegex1 ) {
+        BSONObjBuilder allArray;
+        allArray.appendRegex( "0", "^a", "" );
+        allArray.appendRegex( "1", "B", "i" );
+        BSONObjBuilder all;
+        all.appendArray( "$all", allArray.obj() );
+        BSONObj query = BSON( "a" << all.obj() );
+
+        StatusWithExpression result = ExpressionParser::parse( query );
+        ASSERT_TRUE( result.isOK() );
+
+        BSONObj notMatchFirst = BSON( "a" << "ax" );
+        BSONObj notMatchSecond = BSON( "a" << "qqb" );
+        BSONObj matchesBoth = BSON( "a" << "ab" );
+
+        ASSERT( !result.getValue()->matchesSingleElement( notMatchFirst[ "a" ] ) );
+        ASSERT( !result.getValue()->matchesSingleElement( notMatchSecond[ "a" ] ) );
+        ASSERT( result.getValue()->matchesSingleElement( matchesBoth[ "a" ] ) );
+    }
+
+    TEST( ExpressionParserArrayTest, AllRegex2 ) {
+        BSONObjBuilder allArray;
+        allArray.appendRegex( "0", "^a", "" );
+        allArray.append( "1", "abc" );
+        BSONObjBuilder all;
+        all.appendArray( "$all", allArray.obj() );
+        BSONObj query = BSON( "a" << all.obj() );
+
+        StatusWithExpression result = ExpressionParser::parse( query );
+        ASSERT_TRUE( result.isOK() );
+
+        BSONObj notMatchFirst = BSON( "a" << "ax" );
+        BSONObj matchesBoth = BSON( "a" << "abc" );
+
+        ASSERT( !result.getValue()->matchesSingleElement( notMatchFirst[ "a" ] ) );
+        ASSERT( result.getValue()->matchesSingleElement( matchesBoth[ "a" ] ) );
+    }
+
+    TEST( ExpressionParserArrayTest, AllElemMatch1 ) {
+        BSONObj internal = BSON( "x" << 1 << "y" << 2 );
+        BSONObj query = BSON( "x" << BSON( "$all" << BSON_ARRAY( BSON( "$elemMatch" << internal ) ) ) );
+        StatusWithExpression result = ExpressionParser::parse( query );
+        ASSERT_TRUE( result.isOK() );
+
+        ASSERT( !result.getValue()->matches( BSON( "x" << 1 ) ) );
+        ASSERT( !result.getValue()->matches( BSON( "x" << BSON_ARRAY( 1 << 2 ) ) ) );
+        ASSERT( !result.getValue()->matches( BSON( "x" << BSON_ARRAY(  BSON( "x" << 1 ) ) ) ) );
+        ASSERT( result.getValue()->matches( BSON( "x" <<
+                                                  BSON_ARRAY( BSON( "x" << 1 << "y" << 2 ) ) ) ) );
+
+    }
+
+    TEST( ExpressionParserArrayTest, AllElemMatchBad ) {
+        BSONObj internal = BSON( "x" << 1 << "y" << 2 );
+
+        BSONObj query = BSON( "x" << BSON( "$all" << BSON_ARRAY( BSON( "$elemMatch" << internal ) << 5 ) ) );
+        StatusWithExpression result = ExpressionParser::parse( query );
+        ASSERT_FALSE( result.isOK() );
+
+        query = BSON( "x" << BSON( "$all" << BSON_ARRAY( 5 << BSON( "$elemMatch" << internal ) ) ) );
+        result = ExpressionParser::parse( query );
+        ASSERT_FALSE( result.isOK() );
+    }
+
+}
diff --git a/src/mongo/db/matcher/expression_parser_leaf_test.cpp b/src/mongo/db/matcher/expression_parser_leaf_test.cpp
new file mode 100644
index 00000000000..88dd86b2b66
--- /dev/null
+++ b/src/mongo/db/matcher/expression_parser_leaf_test.cpp
@@ -0,0 +1,342 @@
+// expression_parser_leaf_test.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/>.
+ */
+
+#include "mongo/unittest/unittest.h"
+
+#include "mongo/db/matcher/expression_parser.h"
+
+#include "mongo/bson/bsonobj.h"
+#include "mongo/bson/bsonobjbuilder.h"
+#include "mongo/bson/bsonmisc.h"
+#include "mongo/db/json.h"
+#include "mongo/db/matcher.h"
+#include "mongo/db/matcher/expression.h"
+#include "mongo/db/matcher/expression_leaf.h"
+
+namespace mongo {
+
+    TEST( ExpressionParserLeafTest, SimpleEQ2 ) {
+        BSONObj query = BSON( "x" << BSON( "$eq" << 2 ) );
+        StatusWithExpression result = ExpressionParser::parse( query );
+        ASSERT_TRUE( result.isOK() );
+
+        ASSERT( !result.getValue()->matches( BSON( "x" << 1 ) ) );
+        ASSERT( result.getValue()->matches( BSON( "x" << 2 ) ) );
+        ASSERT( !result.getValue()->matches( BSON( "x" << 3 ) ) );
+    }
+
+    TEST( ExpressionParserLeafTest, SimpleGT1 ) {
+        BSONObj query = BSON( "x" << BSON( "$gt" << 2 ) );
+        StatusWithExpression result = ExpressionParser::parse( query );
+        ASSERT_TRUE( result.isOK() );
+
+        ASSERT( !result.getValue()->matches( BSON( "x" << 2 ) ) );
+        ASSERT( result.getValue()->matches( BSON( "x" << 3 ) ) );
+    }
+
+    TEST( ExpressionParserLeafTest, SimpleLT1 ) {
+        BSONObj query = BSON( "x" << BSON( "$lt" << 2 ) );
+        StatusWithExpression result = ExpressionParser::parse( query );
+        ASSERT_TRUE( result.isOK() );
+
+        ASSERT( result.getValue()->matches( BSON( "x" << 1 ) ) );
+        ASSERT( !result.getValue()->matches( BSON( "x" << 2 ) ) );
+        ASSERT( !result.getValue()->matches( BSON( "x" << 3 ) ) );
+    }
+
+    TEST( ExpressionParserLeafTest, SimpleGTE1 ) {
+        BSONObj query = BSON( "x" << BSON( "$gte" << 2 ) );
+        StatusWithExpression result = ExpressionParser::parse( query );
+        ASSERT_TRUE( result.isOK() );
+
+        ASSERT( !result.getValue()->matches( BSON( "x" << 1 ) ) );
+        ASSERT( result.getValue()->matches( BSON( "x" << 2 ) ) );
+        ASSERT( result.getValue()->matches( BSON( "x" << 3 ) ) );
+    }
+
+    TEST( ExpressionParserLeafTest, SimpleLTE1 ) {
+        BSONObj query = BSON( "x" << BSON( "$lte" << 2 ) );
+        StatusWithExpression result = ExpressionParser::parse( query );
+        ASSERT_TRUE( result.isOK() );
+
+        ASSERT( result.getValue()->matches( BSON( "x" << 1 ) ) );
+        ASSERT( result.getValue()->matches( BSON( "x" << 2 ) ) );
+        ASSERT( !result.getValue()->matches( BSON( "x" << 3 ) ) );
+    }
+
+    TEST( ExpressionParserLeafTest, SimpleNE1 ) {
+        BSONObj query = BSON( "x" << BSON( "$ne" << 2 ) );
+        StatusWithExpression result = ExpressionParser::parse( query );
+        ASSERT_TRUE( result.isOK() );
+
+        ASSERT( result.getValue()->matches( BSON( "x" << 1 ) ) );
+        ASSERT( !result.getValue()->matches( BSON( "x" << 2 ) ) );
+        ASSERT( result.getValue()->matches( BSON( "x" << 3 ) ) );
+    }
+
+    TEST( ExpressionParserLeafTest, SimpleModBad1 ) {
+        BSONObj query = BSON( "x" << BSON( "$mod" << BSON_ARRAY( 3 << 2 ) ) );
+        StatusWithExpression result = ExpressionParser::parse( query );
+        ASSERT_TRUE( result.isOK() );
+
+        query = BSON( "x" << BSON( "$mod" << BSON_ARRAY( 3 ) ) );
+        result = ExpressionParser::parse( query );
+        ASSERT_TRUE( !result.isOK() );
+
+        query = BSON( "x" << BSON( "$mod" << BSON_ARRAY( 3 << 2 << 4 ) ) );
+        result = ExpressionParser::parse( query );
+        ASSERT_TRUE( !result.isOK() );
+
+        query = BSON( "x" << BSON( "$mod" << BSON_ARRAY( "q" << 2 ) ) );
+        result = ExpressionParser::parse( query );
+        ASSERT_TRUE( !result.isOK() );
+
+        query = BSON( "x" << BSON( "$mod" << 3 ) );
+        result = ExpressionParser::parse( query );
+        ASSERT_TRUE( !result.isOK() );
+
+        query = BSON( "x" << BSON( "$mod" << BSON( "a" << 1 << "b" << 2 ) ) );
+        result = ExpressionParser::parse( query );
+        ASSERT_TRUE( !result.isOK() );
+    }
+
+    TEST( ExpressionParserLeafTest, SimpleMod1 ) {
+        BSONObj query = BSON( "x" << BSON( "$mod" << BSON_ARRAY( 3 << 2 ) ) );
+        StatusWithExpression result = ExpressionParser::parse( query );
+        ASSERT_TRUE( result.isOK() );
+
+        ASSERT( result.getValue()->matches( BSON( "x" << 5 ) ) );
+        ASSERT( !result.getValue()->matches( BSON( "x" << 4 ) ) );
+        ASSERT( result.getValue()->matches( BSON( "x" << 8 ) ) );
+    }
+
+    TEST( ExpressionParserLeafTest, SimpleModNotNumber ) {
+        BSONObj query = BSON( "x" << BSON( "$mod" << BSON_ARRAY( 2 << "r" ) ) );
+        StatusWithExpression result = ExpressionParser::parse( query );
+        ASSERT_TRUE( result.isOK() );
+
+        ASSERT( result.getValue()->matches( BSON( "x" << 2 ) ) );
+        ASSERT( result.getValue()->matches( BSON( "x" << 4 ) ) );
+        ASSERT( !result.getValue()->matches( BSON( "x" << 5 ) ) );
+        ASSERT( !result.getValue()->matches( BSON( "x" << "a" ) ) );
+    }
+
+
+    TEST( ExpressionParserLeafTest, SimpleIN1 ) {
+        BSONObj query = BSON( "x" << BSON( "$in" << BSON_ARRAY( 2 << 3 ) ) );
+        StatusWithExpression result = ExpressionParser::parse( query );
+        ASSERT_TRUE( result.isOK() );
+
+        ASSERT( !result.getValue()->matches( BSON( "x" << 1 ) ) );
+        ASSERT( result.getValue()->matches( BSON( "x" << 2 ) ) );
+        ASSERT( result.getValue()->matches( BSON( "x" << 3 ) ) );
+    }
+
+
+    TEST( ExpressionParserLeafTest, INNotArray ) {
+        BSONObj query = BSON( "x" << BSON( "$in" << 5 ) );
+        StatusWithExpression result = ExpressionParser::parse( query );
+        ASSERT_FALSE( result.isOK() );
+    }
+
+    TEST( ExpressionParserLeafTest, INNotElemMatch ) {
+        BSONObj query = BSON( "x" << BSON( "$in" << BSON_ARRAY( BSON( "$elemMatch" << 1 ) ) ) );
+        StatusWithExpression result = ExpressionParser::parse( query );
+        ASSERT_FALSE( result.isOK() );
+    }
+
+    TEST( ExpressionParserLeafTest, INRegexTooLong ) {
+        string tooLargePattern( 50 * 1000, 'z' );
+        BSONObjBuilder inArray;
+        inArray.appendRegex( "0", tooLargePattern, "" );
+        BSONObjBuilder operand;
+        operand.appendArray( "$in", inArray.obj() );
+        BSONObj query = BSON( "x" << operand.obj() );
+        StatusWithExpression result = ExpressionParser::parse( query );
+        ASSERT_FALSE( result.isOK() );
+    }
+
+    TEST( ExpressionParserLeafTest, INRegexTooLong2 ) {
+        string tooLargePattern( 50 * 1000, 'z' );
+        BSONObj query = BSON( "x" << BSON( "$in" << BSON_ARRAY( BSON( "$regex" << tooLargePattern ) ) ) );
+        StatusWithExpression result = ExpressionParser::parse( query );
+        ASSERT_FALSE( result.isOK() );
+    }
+
+    TEST( ExpressionParserLeafTest, INRegexStuff ) {
+        BSONObjBuilder inArray;
+        inArray.appendRegex( "0", "^a", "" );
+        inArray.appendRegex( "1", "B", "i" );
+        inArray.append( "2", 4 );
+        BSONObjBuilder operand;
+        operand.appendArray( "$in", inArray.obj() );
+
+        BSONObj query = BSON( "a" << operand.obj() );
+        StatusWithExpression result = ExpressionParser::parse( query );
+        ASSERT_TRUE( result.isOK() );
+
+        BSONObj matchFirst = BSON( "a" << "ax" );
+        BSONObj matchFirstRegex = BSONObjBuilder().appendRegex( "a", "^a", "" ).obj();
+        BSONObj matchSecond = BSON( "a" << "qqb" );
+        BSONObj matchSecondRegex = BSONObjBuilder().appendRegex( "a", "B", "i" ).obj();
+        BSONObj matchThird = BSON( "a" << 4 );
+        BSONObj notMatch = BSON( "a" << "l" );
+        BSONObj notMatchRegex = BSONObjBuilder().appendRegex( "a", "B", "" ).obj();
+
+        ASSERT( result.getValue()->matches( matchFirst ) );
+        ASSERT( result.getValue()->matches( matchFirstRegex ) );
+        ASSERT( result.getValue()->matches( matchSecond ) );
+        ASSERT( result.getValue()->matches( matchSecondRegex ) );
+        ASSERT( result.getValue()->matches( matchThird ) );
+        ASSERT( !result.getValue()->matches( notMatch ) );
+        ASSERT( !result.getValue()->matches( notMatchRegex ) );
+    }
+
+    TEST( ExpressionParserLeafTest, SimpleNIN1 ) {
+        BSONObj query = BSON( "x" << BSON( "$nin" << BSON_ARRAY( 2 << 3 ) ) );
+        StatusWithExpression result = ExpressionParser::parse( query );
+        ASSERT_TRUE( result.isOK() );
+
+        ASSERT( result.getValue()->matches( BSON( "x" << 1 ) ) );
+        ASSERT( !result.getValue()->matches( BSON( "x" << 2 ) ) );
+        ASSERT( !result.getValue()->matches( BSON( "x" << 3 ) ) );
+    }
+
+    TEST( ExpressionParserLeafTest, NINNotArray ) {
+        BSONObj query = BSON( "x" << BSON( "$nin" << 5 ) );
+        StatusWithExpression result = ExpressionParser::parse( query );
+        ASSERT_FALSE( result.isOK() );
+    }
+
+
+    TEST( ExpressionParserLeafTest, Regex1 ) {
+        BSONObjBuilder b;
+        b.appendRegex( "x", "abc", "i" );
+        BSONObj query = b.obj();
+        StatusWithExpression result = ExpressionParser::parse( query );
+        ASSERT_TRUE( result.isOK() );
+
+        ASSERT( result.getValue()->matches( BSON( "x" << "abc" ) ) );
+        ASSERT( result.getValue()->matches( BSON( "x" << "ABC" ) ) );
+        ASSERT( !result.getValue()->matches( BSON( "x" << "AC" ) ) );
+    }
+
+    TEST( ExpressionParserLeafTest, Regex2 ) {
+        BSONObj query = BSON( "x" << BSON( "$regex" << "abc" << "$options" << "i" ) );
+        StatusWithExpression result = ExpressionParser::parse( query );
+        ASSERT_TRUE( result.isOK() );
+
+        ASSERT( result.getValue()->matches( BSON( "x" << "abc" ) ) );
+        ASSERT( result.getValue()->matches( BSON( "x" << "ABC" ) ) );
+        ASSERT( !result.getValue()->matches( BSON( "x" << "AC" ) ) );
+    }
+
+    TEST( ExpressionParserLeafTest, RegexBad ) {
+        BSONObj query = BSON( "x" << BSON( "$regex" << "abc" << "$optionas" << "i" ) );
+        StatusWithExpression result = ExpressionParser::parse( query );
+        ASSERT_FALSE( result.isOK() );
+
+        query = BSON( "x" << BSON( "$optionas" << "i" ) );
+        result = ExpressionParser::parse( query );
+        ASSERT_FALSE( result.isOK() );
+
+        query = BSON( "x" << BSON( "$options" << "i" ) );
+        result = ExpressionParser::parse( query );
+        ASSERT_FALSE( result.isOK() );
+
+    }
+
+    TEST( ExpressionParserLeafTest, ExistsYes1 ) {
+        BSONObjBuilder b;
+        b.appendBool( "$exists", true );
+        BSONObj query = BSON( "x" << b.obj() );
+        StatusWithExpression result = ExpressionParser::parse( query );
+        ASSERT_TRUE( result.isOK() );
+
+        ASSERT( result.getValue()->matches( BSON( "x" << "abc" ) ) );
+        ASSERT( !result.getValue()->matches( BSON( "y" << "AC" ) ) );
+    }
+
+    TEST( ExpressionParserLeafTest, ExistsNO1 ) {
+        BSONObjBuilder b;
+        b.appendBool( "$exists", false );
+        BSONObj query = BSON( "x" << b.obj() );
+        StatusWithExpression result = ExpressionParser::parse( query );
+        ASSERT_TRUE( result.isOK() );
+
+        ASSERT( !result.getValue()->matches( BSON( "x" << "abc" ) ) );
+        ASSERT( result.getValue()->matches( BSON( "y" << "AC" ) ) );
+    }
+
+    TEST( ExpressionParserLeafTest, Type1 ) {
+        BSONObj query = BSON( "x" << BSON( "$type" << String ) );
+        StatusWithExpression result = ExpressionParser::parse( query );
+        ASSERT_TRUE( result.isOK() );
+
+        ASSERT( result.getValue()->matches( BSON( "x" << "abc" ) ) );
+        ASSERT( !result.getValue()->matches( BSON( "x" << 5 ) ) );
+    }
+
+    TEST( ExpressionParserLeafTest, Type2 ) {
+        BSONObj query = BSON( "x" << BSON( "$type" << (double)NumberDouble ) );
+        StatusWithExpression result = ExpressionParser::parse( query );
+        ASSERT_TRUE( result.isOK() );
+
+        ASSERT( result.getValue()->matches( BSON( "x" << 5.3 ) ) );
+        ASSERT( !result.getValue()->matches( BSON( "x" << 5 ) ) );
+    }
+
+    TEST( ExpressionParserLeafTest, TypeDoubleOperator ) {
+        BSONObj query = BSON( "x" << BSON( "$type" << 1.5 ) );
+        StatusWithExpression result = ExpressionParser::parse( query );
+        ASSERT_TRUE( result.isOK() );
+
+        ASSERT( !result.getValue()->matches( BSON( "x" << 5.3 ) ) );
+        ASSERT( !result.getValue()->matches( BSON( "x" << 5 ) ) );
+    }
+
+    TEST( ExpressionParserLeafTest, TypeNull ) {
+        BSONObj query = BSON( "x" << BSON( "$type" << jstNULL ) );
+        StatusWithExpression result = ExpressionParser::parse( query );
+        ASSERT_TRUE( result.isOK() );
+
+        ASSERT( !result.getValue()->matches( BSONObj() ) );
+        ASSERT( !result.getValue()->matches( BSON( "x" << 5 ) ) );
+        BSONObjBuilder b;
+        b.appendNull( "x" );
+        ASSERT( result.getValue()->matches( b.obj() ) );
+    }
+
+    TEST( ExpressionParserLeafTest, TypeBadType ) {
+        BSONObjBuilder b;
+        b.append( "$type", ( JSTypeMax + 1 ) );
+        BSONObj query = BSON( "x" << b.obj() );
+        StatusWithExpression result = ExpressionParser::parse( query );
+        ASSERT_TRUE( result.isOK() );
+
+        ASSERT( !result.getValue()->matches( BSON( "x" << 5.3 ) ) );
+        ASSERT( !result.getValue()->matches( BSON( "x" << 5 ) ) );
+    }
+
+    TEST( ExpressionParserLeafTest, TypeBad ) {
+        BSONObj query = BSON( "x" << BSON( "$type" << BSON( "x" << 1 ) ) );
+        StatusWithExpression result = ExpressionParser::parse( query );
+        ASSERT_FALSE( result.isOK() );
+    }
+
+}
diff --git a/src/mongo/db/matcher/expression_parser_test.cpp b/src/mongo/db/matcher/expression_parser_test.cpp
new file mode 100644
index 00000000000..3cff591b299
--- /dev/null
+++ b/src/mongo/db/matcher/expression_parser_test.cpp
@@ -0,0 +1,100 @@
+// expression_parser_test.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/>.
+ */
+
+#include "mongo/unittest/unittest.h"
+
+#include "mongo/db/matcher/expression_parser.h"
+
+#include "mongo/bson/bsonobj.h"
+#include "mongo/bson/bsonobjbuilder.h"
+#include "mongo/bson/bsonmisc.h"
+#include "mongo/db/json.h"
+#include "mongo/db/matcher.h"
+#include "mongo/db/matcher/expression.h"
+#include "mongo/db/matcher/expression_leaf.h"
+
+namespace mongo {
+
+    /// HACK HACK HACK
+
+    MatchDetails::MatchDetails() :
+        _elemMatchKeyRequested() {
+        resetOutput();
+    }
+    void MatchDetails::resetOutput() {
+        _loadedRecord = false;
+        _elemMatchKeyFound = false;
+        _elemMatchKey = "";
+    }
+
+    // ----------------------------
+
+    TEST( ExpressionParserTest, SimpleEQ1 ) {
+        BSONObj query = BSON( "x" << 2 );
+        StatusWithExpression result = ExpressionParser::parse( query );
+        ASSERT_TRUE( result.isOK() );
+
+        ASSERT( result.getValue()->matches( BSON( "x" << 2 ) ) );
+        ASSERT( !result.getValue()->matches( BSON( "x" << 3 ) ) );
+    }
+
+    TEST( ExpressionParserTest, Multiple1 ) {
+        BSONObj query = BSON( "x" << 5 << "y" << BSON( "$gt" << 5 << "$lt" << 8 ) );
+        StatusWithExpression result = ExpressionParser::parse( query );
+        ASSERT_TRUE( result.isOK() );
+
+        ASSERT( result.getValue()->matches( BSON( "x" << 5 << "y" << 7 ) ) );
+        ASSERT( result.getValue()->matches( BSON( "x" << 5 << "y" << 6 ) ) );
+        ASSERT( !result.getValue()->matches( BSON( "x" << 6 << "y" << 7 ) ) );
+        ASSERT( !result.getValue()->matches( BSON( "x" << 5 << "y" << 9 ) ) );
+        ASSERT( !result.getValue()->matches( BSON( "x" << 5 << "y" << 4 ) ) );
+    }
+
+    StatusWith<int> fib( int n ) {
+        if ( n < 0 ) return StatusWith<int>( ErrorCodes::BadValue, "paramter to fib has to be >= 0" );
+        if ( n <= 1 ) return StatusWith<int>( 1 );
+        StatusWith<int> a = fib( n - 1 );
+        StatusWith<int> b = fib( n - 2 );
+        if ( !a.isOK() ) return a;
+        if ( !b.isOK() ) return b;
+        return StatusWith<int>( a.getValue() + b.getValue() );
+    }
+
+    TEST( StatusWithTest, Fib1 ) {
+        StatusWith<int> x = fib( -2 );
+        ASSERT( !x.isOK() );
+
+        x = fib(0);
+        ASSERT( x.isOK() );
+        ASSERT( 1 == x.getValue() );
+
+        x = fib(1);
+        ASSERT( x.isOK() );
+        ASSERT( 1 == x.getValue() );
+
+        x = fib(2);
+        ASSERT( x.isOK() );
+        ASSERT( 2 == x.getValue() );
+
+        x = fib(3);
+        ASSERT( x.isOK() );
+        ASSERT( 3 == x.getValue() );
+
+
+    }
+}
diff --git a/src/mongo/db/matcher/expression_parser_tree.cpp b/src/mongo/db/matcher/expression_parser_tree.cpp
new file mode 100644
index 00000000000..599adfea031
--- /dev/null
+++ b/src/mongo/db/matcher/expression_parser_tree.cpp
@@ -0,0 +1,79 @@
+// expression_parser_tree.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/>.
+ */
+
+#include "mongo/db/matcher/expression_parser.h"
+
+#include "mongo/bson/bsonobj.h"
+#include "mongo/bson/bsonobjbuilder.h"
+#include "mongo/bson/bsonobjiterator.h"
+#include "mongo/db/matcher/expression_array.h"
+#include "mongo/db/matcher/expression_leaf.h"
+#include "mongo/db/matcher/expression_tree.h"
+#include "mongo/util/log.h"
+#include "mongo/util/mongoutils/str.h"
+
+namespace mongo {
+
+    Status ExpressionParser::_parseTreeList( const BSONObj& arr, ListOfExpression* out ) {
+        BSONObjIterator i( arr );
+        while ( i.more() ) {
+            BSONElement e = i.next();
+
+            if ( e.type() != Object )
+                return Status( ErrorCodes::BadValue,
+                               "$or/$and/$nor entries need to be full objects" );
+
+            StatusWithExpression sub = parse( e.Obj() );
+            if ( !sub.isOK() )
+                return sub.getStatus();
+
+            out->add( sub.getValue() );
+        }
+        return Status::OK();
+    }
+
+    StatusWithExpression ExpressionParser::_parseNot( const char* name,
+                                                      const BSONElement& e ) {
+        if ( e.type() == RegEx ) {
+            StatusWithExpression s = _parseRegexElement( name, e );
+            if ( !s.isOK() )
+                return s;
+            std::auto_ptr<NotExpression> n( new NotExpression() );
+            Status s2 = n->init( s.getValue() );
+            if ( !s2.isOK() )
+                return StatusWithExpression( s2 );
+            return StatusWithExpression( n.release() );
+        }
+
+        if ( e.type() != Object )
+            return StatusWithExpression( ErrorCodes::BadValue, "$not needs a regex or a document" );
+
+        std::auto_ptr<AndExpression> theAnd( new AndExpression() );
+        Status s = _parseSub( name, e.Obj(), theAnd.get() );
+        if ( !s.isOK() )
+            return StatusWithExpression( s );
+
+        std::auto_ptr<NotExpression> theNot( new NotExpression() );
+        s = theNot->init( theAnd.release() );
+        if ( !s.isOK() )
+            return StatusWithExpression( s );
+
+        return StatusWithExpression( theNot.release() );
+    }
+
+}
diff --git a/src/mongo/db/matcher/expression_parser_tree_test.cpp b/src/mongo/db/matcher/expression_parser_tree_test.cpp
new file mode 100644
index 00000000000..bd315b4ff1a
--- /dev/null
+++ b/src/mongo/db/matcher/expression_parser_tree_test.cpp
@@ -0,0 +1,106 @@
+// expression_parser_tree_test.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/>.
+ */
+
+#include "mongo/unittest/unittest.h"
+
+#include "mongo/db/matcher/expression_parser.h"
+
+#include "mongo/bson/bsonobj.h"
+#include "mongo/bson/bsonobjbuilder.h"
+#include "mongo/bson/bsonmisc.h"
+#include "mongo/db/json.h"
+#include "mongo/db/matcher.h"
+#include "mongo/db/matcher/expression.h"
+#include "mongo/db/matcher/expression_leaf.h"
+
+namespace mongo {
+
+    TEST( ExpressionParserTreeTest, OR1 ) {
+        BSONObj query = BSON( "$or" << BSON_ARRAY( BSON( "x" << 1 ) <<
+                                                   BSON( "y" << 2 ) ) );
+        StatusWithExpression result = ExpressionParser::parse( query );
+        ASSERT_TRUE( result.isOK() );
+
+        ASSERT( result.getValue()->matches( BSON( "x" << 1 ) ) );
+        ASSERT( result.getValue()->matches( BSON( "y" << 2 ) ) );
+        ASSERT( !result.getValue()->matches( BSON( "x" << 3 ) ) );
+        ASSERT( !result.getValue()->matches( BSON( "y" << 1 ) ) );
+    }
+
+    TEST( ExpressionParserTreeTest, OREmbedded ) {
+        BSONObj query1 = BSON( "$or" << BSON_ARRAY( BSON( "x" << 1 ) <<
+                                                    BSON( "y" << 2 ) ) );
+        BSONObj query2 = BSON( "$or" << BSON_ARRAY( query1 ) );
+        StatusWithExpression result = ExpressionParser::parse( query2 );
+        ASSERT_TRUE( result.isOK() );
+
+        ASSERT( result.getValue()->matches( BSON( "x" << 1 ) ) );
+        ASSERT( result.getValue()->matches( BSON( "y" << 2 ) ) );
+        ASSERT( !result.getValue()->matches( BSON( "x" << 3 ) ) );
+        ASSERT( !result.getValue()->matches( BSON( "y" << 1 ) ) );
+    }
+
+
+    TEST( ExpressionParserTreeTest, AND1 ) {
+        BSONObj query = BSON( "$and" << BSON_ARRAY( BSON( "x" << 1 ) <<
+                                                    BSON( "y" << 2 ) ) );
+        StatusWithExpression result = ExpressionParser::parse( query );
+        ASSERT_TRUE( result.isOK() );
+
+        ASSERT( !result.getValue()->matches( BSON( "x" << 1 ) ) );
+        ASSERT( !result.getValue()->matches( BSON( "y" << 2 ) ) );
+        ASSERT( !result.getValue()->matches( BSON( "x" << 3 ) ) );
+        ASSERT( !result.getValue()->matches( BSON( "y" << 1 ) ) );
+        ASSERT( result.getValue()->matches( BSON( "x" << 1 << "y" << 2 ) ) );
+        ASSERT( !result.getValue()->matches( BSON( "x" << 2 << "y" << 2 ) ) );
+    }
+
+    TEST( ExpressionParserTreeTest, NOREmbedded ) {
+        BSONObj query = BSON( "$nor" << BSON_ARRAY( BSON( "x" << 1 ) <<
+                                                    BSON( "y" << 2 ) ) );
+        StatusWithExpression result = ExpressionParser::parse( query );
+        ASSERT_TRUE( result.isOK() );
+
+        ASSERT( !result.getValue()->matches( BSON( "x" << 1 ) ) );
+        ASSERT( !result.getValue()->matches( BSON( "y" << 2 ) ) );
+        ASSERT( result.getValue()->matches( BSON( "x" << 3 ) ) );
+        ASSERT( result.getValue()->matches( BSON( "y" << 1 ) ) );
+    }
+
+    TEST( ExpressionParserTreeTest, NOT1 ) {
+        BSONObj query = BSON( "x" << BSON( "$not" << BSON( "$gt" << 5 ) ) );
+        StatusWithExpression result = ExpressionParser::parse( query );
+        ASSERT_TRUE( result.isOK() );
+
+        ASSERT( result.getValue()->matches( BSON( "x" << 2 ) ) );
+        ASSERT( !result.getValue()->matches( BSON( "x" << 8 ) ) );
+    }
+
+    TEST( ExpressionParserLeafTest, NotRegex1 ) {
+        BSONObjBuilder b;
+        b.appendRegex( "$not", "abc", "i" );
+        BSONObj query = BSON( "x" << b.obj() );
+        StatusWithExpression result = ExpressionParser::parse( query );
+        ASSERT_TRUE( result.isOK() );
+
+        ASSERT( !result.getValue()->matches( BSON( "x" << "abc" ) ) );
+        ASSERT( !result.getValue()->matches( BSON( "x" << "ABC" ) ) );
+        ASSERT( result.getValue()->matches( BSON( "x" << "AC" ) ) );
+    }
+
+}
diff --git a/src/mongo/db/matcher/expression_test.cpp b/src/mongo/db/matcher/expression_test.cpp
new file mode 100644
index 00000000000..44424e11d64
--- /dev/null
+++ b/src/mongo/db/matcher/expression_test.cpp
@@ -0,0 +1,113 @@
+// expression_test.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/>.
+ */
+
+/** Unit tests for MatchExpression operator implementations in match_operators.{h,cpp}. */
+
+#include "mongo/unittest/unittest.h"
+
+#include "mongo/bson/bsonobj.h"
+#include "mongo/bson/bsonobjbuilder.h"
+#include "mongo/bson/bsonmisc.h"
+#include "mongo/db/json.h"
+#include "mongo/db/matcher.h"
+#include "mongo/db/matcher/expression.h"
+#include "mongo/db/matcher/expression_leaf.h"
+
+namespace mongo {
+
+    /// HACK HACK HACK
+
+    MatchDetails::MatchDetails() :
+        _elemMatchKeyRequested() {
+        resetOutput();
+    }
+    void MatchDetails::resetOutput() {
+        _loadedRecord = false;
+        _elemMatchKeyFound = false;
+        _elemMatchKey = "";
+    }
+
+
+    // ----------------------
+
+    TEST( ExpressionTest, Parse1 ) {
+        //TreeExpression* e = NULL;
+        //Status s = Expression::parse( BSON( "x" << 1 ), &e );
+        //ASSERT_TRUE( s.isOK() );
+    }
+
+    TEST( LeafExpressionTest, Equal1 ) {
+        BSONObj temp = BSON( "x" << 5 );
+        ComparisonExpression e;
+        e.init( "x", ComparisonExpression::EQ, temp["x"] );
+
+        ASSERT_TRUE( e.matches( fromjson( "{ x : 5 }" ) ) );
+        ASSERT_TRUE( e.matches( fromjson( "{ x : [5] }" ) ) );
+        ASSERT_TRUE( e.matches( fromjson( "{ x : [1,5] }" ) ) );
+        ASSERT_TRUE( e.matches( fromjson( "{ x : [1,5,2] }" ) ) );
+        ASSERT_TRUE( e.matches( fromjson( "{ x : [5,2] }" ) ) );
+
+        ASSERT_FALSE( e.matches( fromjson( "{ x : null }" ) ) );
+        ASSERT_FALSE( e.matches( fromjson( "{ x : 6 }" ) ) );
+        ASSERT_FALSE( e.matches( fromjson( "{ x : [4,2] }" ) ) );
+        ASSERT_FALSE( e.matches( fromjson( "{ x : [[5]] }" ) ) );
+    }
+
+    TEST( LeafExpressionTest, Comp1 ) {
+        BSONObj temp = BSON( "x" << 5 );
+
+        {
+            ComparisonExpression e;
+            e.init( "x", ComparisonExpression::LTE, temp["x"] );
+            ASSERT_TRUE( e.matches( fromjson( "{ x : 5 }" ) ) );
+            ASSERT_TRUE( e.matches( fromjson( "{ x : 4 }" ) ) );
+            ASSERT_FALSE( e.matches( fromjson( "{ x : 6 }" ) ) );
+            ASSERT_FALSE( e.matches( fromjson( "{ x : 'eliot' }" ) ) );
+        }
+
+        {
+            ComparisonExpression e;
+            e.init( "x", ComparisonExpression::LT, temp["x"] );
+            ASSERT_FALSE( e.matches( fromjson( "{ x : 5 }" ) ) );
+            ASSERT_TRUE( e.matches( fromjson( "{ x : 4 }" ) ) );
+            ASSERT_FALSE( e.matches( fromjson( "{ x : 6 }" ) ) );
+            ASSERT_FALSE( e.matches( fromjson( "{ x : 'eliot' }" ) ) );
+        }
+
+        {
+            ComparisonExpression e;
+            e.init( "x", ComparisonExpression::GTE, temp["x"] );
+            ASSERT_TRUE( e.matches( fromjson( "{ x : 5 }" ) ) );
+            ASSERT_FALSE( e.matches( fromjson( "{ x : 4 }" ) ) );
+            ASSERT_TRUE( e.matches( fromjson( "{ x : 6 }" ) ) );
+            ASSERT_FALSE( e.matches( fromjson( "{ x : 'eliot' }" ) ) );
+        }
+
+        {
+            ComparisonExpression e;
+            e.init( "x", ComparisonExpression::GT, temp["x"] );
+            ASSERT_FALSE( e.matches( fromjson( "{ x : 5 }" ) ) );
+            ASSERT_FALSE( e.matches( fromjson( "{ x : 4 }" ) ) );
+            ASSERT_TRUE( e.matches( fromjson( "{ x : 6 }" ) ) );
+            ASSERT_FALSE( e.matches( fromjson( "{ x : 'eliot' }" ) ) );
+        }
+
+
+    }
+
+}
diff --git a/src/mongo/db/matcher/expression_tree.cpp b/src/mongo/db/matcher/expression_tree.cpp
new file mode 100644
index 00000000000..e344e816158
--- /dev/null
+++ b/src/mongo/db/matcher/expression_tree.cpp
@@ -0,0 +1,136 @@
+// expression_tree.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/>.
+ */
+
+#include "mongo/db/matcher/expression_tree.h"
+
+#include "mongo/bson/bsonobjiterator.h"
+#include "mongo/bson/bsonobj.h"
+#include "mongo/bson/bsonmisc.h"
+#include "mongo/db/matcher.h"
+#include "mongo/util/log.h"
+
+namespace mongo {
+
+    ListOfExpression::~ListOfExpression() {
+        for ( unsigned i = 0; i < _expressions.size(); i++ )
+            delete _expressions[i];
+        _expressions.clear();
+    }
+
+    void ListOfExpression::add( Expression* e ) {
+        verify( e );
+        _expressions.push_back( e );
+    }
+
+
+    void ListOfExpression::_debugList( StringBuilder& debug, int level ) const {
+        for ( unsigned i = 0; i < _expressions.size(); i++ )
+            _expressions[i]->debugString( debug, level + 1 );
+    }
+
+    // -----
+
+    bool AndExpression::matches( const BSONObj& doc, MatchDetails* details ) const {
+        for ( size_t i = 0; i < size(); i++ ) {
+            if ( !get(i)->matches( doc, details ) ) {
+                if ( details )
+                    details->resetOutput();
+                return false;
+            }
+        }
+        return true;
+    }
+
+    bool AndExpression::matchesSingleElement( const BSONElement& e ) const {
+        for ( size_t i = 0; i < size(); i++ ) {
+            if ( !get(i)->matchesSingleElement( e ) ) {
+                return false;
+            }
+        }
+        return true;
+    }
+
+
+    void AndExpression::debugString( StringBuilder& debug, int level ) const {
+        _debugAddSpace( debug, level );
+        debug << "$and\n";
+        _debugList( debug, level );
+    }
+
+    // -----
+
+    bool OrExpression::matches( const BSONObj& doc, MatchDetails* details ) const {
+        for ( size_t i = 0; i < size(); i++ ) {
+            if ( get(i)->matches( doc, NULL ) ) {
+                return true;
+            }
+        }
+        return false;
+    }
+
+    bool OrExpression::matchesSingleElement( const BSONElement& e ) const {
+        for ( size_t i = 0; i < size(); i++ ) {
+            if ( get(i)->matchesSingleElement( e ) ) {
+                return true;
+            }
+        }
+        return false;
+    }
+
+
+    void OrExpression::debugString( StringBuilder& debug, int level ) const {
+        _debugAddSpace( debug, level );
+        debug << "$or\n";
+        _debugList( debug, level );
+    }
+
+    // ----
+
+    bool NorExpression::matches( const BSONObj& doc, MatchDetails* details ) const {
+        for ( size_t i = 0; i < size(); i++ ) {
+            if ( get(i)->matches( doc, NULL ) ) {
+                return false;
+            }
+        }
+        return true;
+    }
+
+    bool NorExpression::matchesSingleElement( const BSONElement& e ) const {
+        for ( size_t i = 0; i < size(); i++ ) {
+            if ( get(i)->matchesSingleElement( e ) ) {
+                return false;
+            }
+        }
+        return true;
+    }
+
+    void NorExpression::debugString( StringBuilder& debug, int level ) const {
+        _debugAddSpace( debug, level );
+        debug << "$nor\n";
+        _debugList( debug, level );
+    }
+
+    // -------
+
+    void NotExpression::debugString( StringBuilder& debug, int level ) const {
+        _debugAddSpace( debug, level );
+        debug << "$not\n";
+        _exp->debugString( debug, level + 1 );
+    }
+
+}
diff --git a/src/mongo/db/matcher/expression_tree.h b/src/mongo/db/matcher/expression_tree.h
new file mode 100644
index 00000000000..4223b9a797b
--- /dev/null
+++ b/src/mongo/db/matcher/expression_tree.h
@@ -0,0 +1,109 @@
+// expression_tree.h
+
+/**
+ *    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/>.
+ */
+
+#pragma once
+
+#include "mongo/db/matcher/expression.h"
+
+#include <boost/scoped_ptr.hpp>
+
+/**
+ * this contains all Expessions that define the structure of the tree
+ * they do not look at the structure of the documents themselves, just combine other things
+ */
+namespace mongo {
+
+    class ListOfExpression : public Expression {
+    public:
+        virtual ~ListOfExpression();
+
+        /**
+         * @param e - I take ownership
+         */
+        void add( Expression* e );
+
+        /**
+         * clears all the thingsd we own, and does NOT delete
+         * someone else has taken ownership
+         */
+        void clearAndRelease() { _expressions.clear(); }
+
+        size_t size() const { return _expressions.size(); }
+        Expression* get( size_t i ) const { return _expressions[i]; }
+
+    protected:
+        void _debugList( StringBuilder& debug, int level ) const;
+
+    private:
+        std::vector< Expression* > _expressions;
+    };
+
+    class AndExpression : public ListOfExpression {
+    public:
+        virtual ~AndExpression(){}
+
+        virtual bool matches( const BSONObj& doc, MatchDetails* details = 0 ) const;
+        virtual bool matchesSingleElement( const BSONElement& e ) const;
+
+        virtual void debugString( StringBuilder& debug, int level = 0 ) const;
+    };
+
+    class OrExpression : public ListOfExpression {
+    public:
+        virtual ~OrExpression(){}
+
+        virtual bool matches( const BSONObj& doc, MatchDetails* details = 0 ) const;
+        virtual bool matchesSingleElement( const BSONElement& e ) const;
+
+        virtual void debugString( StringBuilder& debug, int level = 0 ) const;
+    };
+
+    class NorExpression : public ListOfExpression {
+    public:
+        virtual ~NorExpression(){}
+
+        virtual bool matches( const BSONObj& doc, MatchDetails* details = 0 ) const;
+        virtual bool matchesSingleElement( const BSONElement& e ) const;
+
+        virtual void debugString( StringBuilder& debug, int level = 0 ) const;
+    };
+
+    class NotExpression : public Expression {
+    public:
+        /**
+         * @param exp - I own it, and will delete
+         */
+        virtual Status init( Expression* exp ) {
+            _exp.reset( exp );
+            return Status::OK();
+        }
+
+        virtual bool matches( const BSONObj& doc, MatchDetails* details = 0 ) const {
+            return !_exp->matches( doc, NULL );
+        }
+
+        virtual bool matchesSingleElement( const BSONElement& e ) const {
+            return !_exp->matchesSingleElement( e );
+        }
+
+        virtual void debugString( StringBuilder& debug, int level = 0 ) const;
+    private:
+        boost::scoped_ptr<Expression> _exp;
+    };
+
+}
diff --git a/src/mongo/db/matcher/expression_tree_test.cpp b/src/mongo/db/matcher/expression_tree_test.cpp
new file mode 100644
index 00000000000..4dabbbbfef9
--- /dev/null
+++ b/src/mongo/db/matcher/expression_tree_test.cpp
@@ -0,0 +1,534 @@
+/**
+ *    Copyright (C) 2012 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/>.
+ */
+
+/** Unit tests for MatchExpression operator implementations in match_operators.{h,cpp}. */
+
+#include "mongo/unittest/unittest.h"
+
+#include "mongo/db/jsobj.h"
+#include "mongo/db/json.h"
+#include "mongo/db/matcher.h"
+#include "mongo/db/matcher/expression.h"
+#include "mongo/db/matcher/expression_tree.h"
+#include "mongo/db/matcher/expression_leaf.h"
+
+namespace mongo {
+
+    TEST( NotExpression, MatchesScalar ) {
+        BSONObj baseOperand = BSON( "$lt" << 5 );
+        auto_ptr<ComparisonExpression> lt( new ComparisonExpression() );
+        ASSERT( lt->init( "a", ComparisonExpression::LT, baseOperand[ "$lt" ] ).isOK() );
+        NotExpression notOp;
+        ASSERT( notOp.init( lt.release() ).isOK() );
+        ASSERT( notOp.matches( BSON( "a" << 6 ), NULL ) );
+        ASSERT( !notOp.matches( BSON( "a" << 4 ), NULL ) );
+    }
+
+    TEST( NotExpression, MatchesArray ) {
+        BSONObj baseOperand = BSON( "$lt" << 5 );
+        auto_ptr<ComparisonExpression> lt( new ComparisonExpression() );
+        ASSERT( lt->init( "a", ComparisonExpression::LT, baseOperand[ "$lt" ] ).isOK() );
+        NotExpression notOp;
+        ASSERT( notOp.init( lt.release() ).isOK() );
+        ASSERT( notOp.matches( BSON( "a" << BSON_ARRAY( 6 ) ), NULL ) );
+        ASSERT( !notOp.matches( BSON( "a" << BSON_ARRAY( 4 ) ), NULL ) );
+        // All array elements must match.
+        ASSERT( !notOp.matches( BSON( "a" << BSON_ARRAY( 4 << 5 << 6 ) ), NULL ) );
+    }
+
+    TEST( NotExpression, ElemMatchKey ) {
+        BSONObj baseOperand = BSON( "$lt" << 5 );
+        auto_ptr<ComparisonExpression> lt( new ComparisonExpression() );
+        ASSERT( lt->init( "a", ComparisonExpression::LT, baseOperand[ "$lt" ] ).isOK() );
+        NotExpression notOp;
+        ASSERT( notOp.init( lt.release() ).isOK() );
+        MatchDetails details;
+        details.requestElemMatchKey();
+        ASSERT( !notOp.matches( BSON( "a" << BSON_ARRAY( 1 ) ), &details ) );
+        ASSERT( !details.hasElemMatchKey() );
+        ASSERT( notOp.matches( BSON( "a" << 6 ), &details ) );
+        ASSERT( !details.hasElemMatchKey() );
+        ASSERT( notOp.matches( BSON( "a" << BSON_ARRAY( 6 ) ), &details ) );
+        // elemMatchKey is not implemented for negative match operators.
+        ASSERT( !details.hasElemMatchKey() );
+    }
+    /*
+      TEST( NotExpression, MatchesIndexKey ) {
+      BSONObj baseOperand = BSON( "$lt" << 5 );
+      auto_ptr<ComparisonExpression> lt( new ComparisonExpression() );
+      ASSERT( lt->init( "a", baseOperand[ "$lt" ] ).isOK() );
+      NotExpression notOp;
+      ASSERT( notOp.init( lt.release() ).isOK() );
+      IndexSpec indexSpec( BSON( "a" << 1 ) );
+      BSONObj indexKey = BSON( "" << "7" );
+      ASSERT( MatchExpression::PartialMatchResult_Unknown ==
+      notOp.matchesIndexKey( indexKey, indexSpec ) );
+      }
+    */
+
+    /**
+    TEST( AndOp, MatchesElementSingleClause ) {
+        BSONObj baseOperand = BSON( "$lt" << 5 );
+        BSONObj match = BSON( "a" << 4 );
+        BSONObj notMatch = BSON( "a" << 5 );
+        auto_ptr<ComparisonExpression> lt( new ComparisonExpression() );
+        ASSERT( lt->init( "", baseOperand[ "$lt" ] ).isOK() );
+        OwnedPointerVector<MatchExpression> subExpressions;
+        subExpressions.mutableVector().push_back( lt.release() );
+        AndOp andOp;
+        ASSERT( andOp.init( &subExpressions ).isOK() );
+        ASSERT( andOp.matchesSingleElement( match[ "a" ] ) );
+        ASSERT( !andOp.matchesSingleElement( notMatch[ "a" ] ) );
+    }
+    */
+
+    TEST( AndOp, NoClauses ) {
+        AndExpression andExpression;
+        ASSERT( andExpression.matches( BSONObj(), NULL ) );
+    }
+
+    TEST( AndOp, MatchesElementThreeClauses ) {
+        BSONObj baseOperand1 = BSON( "$lt" << "z1" );
+        BSONObj baseOperand2 = BSON( "$gt" << "a1" );
+        BSONObj match = BSON( "a" << "r1" );
+        BSONObj notMatch1 = BSON( "a" << "z1" );
+        BSONObj notMatch2 = BSON( "a" << "a1" );
+        BSONObj notMatch3 = BSON( "a" << "r" );
+
+        auto_ptr<ComparisonExpression> sub1( new ComparisonExpression() );
+        ASSERT( sub1->init( "a", ComparisonExpression::LT, baseOperand1[ "$lt" ] ).isOK() );
+        auto_ptr<ComparisonExpression> sub2( new ComparisonExpression() );
+        ASSERT( sub2->init( "a", ComparisonExpression::GT, baseOperand2[ "$gt" ] ).isOK() );
+        auto_ptr<RegexExpression> sub3( new RegexExpression() );
+        ASSERT( sub3->init( "a", "1", "" ).isOK() );
+
+        AndExpression andOp;
+        andOp.add( sub1.release() );
+        andOp.add( sub2.release() );
+        andOp.add( sub3.release() );
+
+        ASSERT( andOp.matches( match ) );
+        ASSERT( !andOp.matches( notMatch1 ) );
+        ASSERT( !andOp.matches( notMatch2 ) );
+        ASSERT( !andOp.matches( notMatch3 ) );
+    }
+
+    TEST( AndOp, MatchesSingleClause ) {
+        BSONObj baseOperand = BSON( "$ne" << 5 );
+        auto_ptr<ComparisonExpression> ne( new ComparisonExpression() );
+        ASSERT( ne->init( "a", ComparisonExpression::NE, baseOperand[ "$ne" ] ).isOK() );
+
+        AndExpression andOp;
+        andOp.add( ne.release() );
+
+        ASSERT( andOp.matches( BSON( "a" << 4 ), NULL ) );
+        ASSERT( andOp.matches( BSON( "a" << BSON_ARRAY( 4 << 6 ) ), NULL ) );
+        ASSERT( !andOp.matches( BSON( "a" << 5 ), NULL ) );
+        ASSERT( !andOp.matches( BSON( "a" << BSON_ARRAY( 4 << 5 ) ), NULL ) );
+    }
+
+    TEST( AndOp, MatchesThreeClauses ) {
+        BSONObj baseOperand1 = BSON( "$gt" << 1 );
+        BSONObj baseOperand2 = BSON( "$lt" << 10 );
+        BSONObj baseOperand3 = BSON( "$lt" << 100 );
+
+        auto_ptr<ComparisonExpression> sub1( new ComparisonExpression() );
+        ASSERT( sub1->init( "a", ComparisonExpression::GT, baseOperand1[ "$gt" ] ).isOK() );
+
+        auto_ptr<ComparisonExpression> sub2( new ComparisonExpression() );
+        ASSERT( sub2->init( "a", ComparisonExpression::LT, baseOperand2[ "$lt" ] ).isOK() );
+
+        auto_ptr<ComparisonExpression> sub3( new ComparisonExpression() );
+        ASSERT( sub3->init( "b", ComparisonExpression::LT, baseOperand3[ "$lt" ] ).isOK() );
+
+        AndExpression andOp;
+        andOp.add( sub1.release() );
+        andOp.add( sub2.release() );
+        andOp.add( sub3.release() );
+
+        ASSERT( andOp.matches( BSON( "a" << 5 << "b" << 6 ), NULL ) );
+        ASSERT( !andOp.matches( BSON( "a" << 5 ), NULL ) );
+        ASSERT( !andOp.matches( BSON( "b" << 6 ), NULL ) );
+        ASSERT( !andOp.matches( BSON( "a" << 1 << "b" << 6 ), NULL ) );
+        ASSERT( !andOp.matches( BSON( "a" << 10 << "b" << 6 ), NULL ) );
+    }
+
+    TEST( AndOp, ElemMatchKey ) {
+        BSONObj baseOperand1 = BSON( "a" << 1 );
+        BSONObj baseOperand2 = BSON( "b" << 2 );
+
+        auto_ptr<ComparisonExpression> sub1( new ComparisonExpression() );
+        ASSERT( sub1->init( "a", ComparisonExpression::EQ, baseOperand1[ "a" ] ).isOK() );
+
+        auto_ptr<ComparisonExpression> sub2( new ComparisonExpression() );
+        ASSERT( sub2->init( "b", ComparisonExpression::EQ, baseOperand2[ "b" ] ).isOK() );
+
+        AndExpression andOp;
+        andOp.add( sub1.release() );
+        andOp.add( sub2.release() );
+
+        MatchDetails details;
+        details.requestElemMatchKey();
+        ASSERT( !andOp.matches( BSON( "a" << BSON_ARRAY( 1 ) ), &details ) );
+        ASSERT( !details.hasElemMatchKey() );
+        ASSERT( !andOp.matches( BSON( "b" << BSON_ARRAY( 2 ) ), &details ) );
+        ASSERT( !details.hasElemMatchKey() );
+        ASSERT( andOp.matches( BSON( "a" << BSON_ARRAY( 1 ) << "b" << BSON_ARRAY( 1 << 2 ) ),
+                               &details ) );
+        ASSERT( details.hasElemMatchKey() );
+        // The elem match key for the second $and clause is recorded.
+        ASSERT_EQUALS( "1", details.elemMatchKey() );
+    }
+
+    /**
+    TEST( AndOp, MatchesIndexKeyWithoutUnknown ) {
+        BSONObj baseOperand1 = BSON( "$gt" << 1 );
+        BSONObj baseOperand2 = BSON( "$lt" << 5 );
+        auto_ptr<ComparisonExpression> sub1( new ComparisonExpression() );
+        ASSERT( sub1->init( "a", baseOperand1[ "$gt" ] ).isOK() );
+        auto_ptr<ComparisonExpression> sub2( new ComparisonExpression() );
+        ASSERT( sub2->init( "a", baseOperand2[ "$lt" ] ).isOK() );
+        OwnedPointerVector<MatchExpression> subExpressions;
+        subExpressions.mutableVector().push_back( sub1.release() );
+        subExpressions.mutableVector().push_back( sub2.release() );
+        AndOp andOp;
+        ASSERT( andOp.init( &subExpressions ).isOK() );
+        IndexSpec indexSpec( BSON( "a" << 1 ) );
+        ASSERT( MatchExpression::PartialMatchResult_True ==
+                andOp.matchesIndexKey( BSON( "" << 3 ), indexSpec ) );
+        ASSERT( MatchExpression::PartialMatchResult_False ==
+                andOp.matchesIndexKey( BSON( "" << 0 ), indexSpec ) );
+        ASSERT( MatchExpression::PartialMatchResult_False ==
+                andOp.matchesIndexKey( BSON( "" << 6 ), indexSpec ) );
+    }
+
+    TEST( AndOp, MatchesIndexKeyWithUnknown ) {
+        BSONObj baseOperand1 = BSON( "$gt" << 1 );
+        BSONObj baseOperand2 = BSON( "$lt" << 5 );
+        // This part will return PartialMatchResult_Unknown.
+        BSONObj baseOperand3 = BSON( "$ne" << 5 );
+        auto_ptr<ComparisonExpression> sub1( new ComparisonExpression() );
+        ASSERT( sub1->init( "a", baseOperand1[ "$gt" ] ).isOK() );
+        auto_ptr<ComparisonExpression> sub2( new ComparisonExpression() );
+        ASSERT( sub2->init( "a", baseOperand2[ "$lt" ] ).isOK() );
+        auto_ptr<NeOp> sub3( new NeOp() );
+        ASSERT( sub3->init( "a", baseOperand3[ "$ne" ] ).isOK() );
+        OwnedPointerVector<MatchExpression> subExpressions;
+        subExpressions.mutableVector().push_back( sub1.release() );
+        subExpressions.mutableVector().push_back( sub2.release() );
+        subExpressions.mutableVector().push_back( sub3.release() );
+        AndOp andOp;
+        ASSERT( andOp.init( &subExpressions ).isOK() );
+        IndexSpec indexSpec( BSON( "a" << 1 ) );
+        ASSERT( MatchExpression::PartialMatchResult_Unknown ==
+                andOp.matchesIndexKey( BSON( "" << 3 ), indexSpec ) );
+        ASSERT( MatchExpression::PartialMatchResult_False ==
+                andOp.matchesIndexKey( BSON( "" << 0 ), indexSpec ) );
+        ASSERT( MatchExpression::PartialMatchResult_False ==
+                andOp.matchesIndexKey( BSON( "" << 6 ), indexSpec ) );
+    }
+    */
+
+    /**
+    TEST( OrOp, MatchesElementSingleClause ) {
+        BSONObj baseOperand = BSON( "$lt" << 5 );
+        BSONObj match = BSON( "a" << 4 );
+        BSONObj notMatch = BSON( "a" << 5 );
+        auto_ptr<ComparisonExpression> lt( new ComparisonExpression() );
+        ASSERT( lt->init( "a", baseOperand[ "$lt" ] ).isOK() );
+        OwnedPointerVector<MatchExpression> subExpressions;
+        subExpressions.mutableVector().push_back( lt.release() );
+        OrOp orOp;
+        ASSERT( orOp.init( &subExpressions ).isOK() );
+        ASSERT( orOp.matchesSingleElement( match[ "a" ] ) );
+        ASSERT( !orOp.matchesSingleElement( notMatch[ "a" ] ) );
+    }
+    */
+
+    TEST( OrOp, NoClauses ) {
+        OrExpression orOp;
+        ASSERT( !orOp.matches( BSONObj(), NULL ) );
+    }
+    /*
+    TEST( OrOp, MatchesElementThreeClauses ) {
+        BSONObj baseOperand1 = BSON( "$lt" << 0 );
+        BSONObj baseOperand2 = BSON( "$gt" << 10 );
+        BSONObj baseOperand3 = BSON( "a" << 5 );
+        BSONObj match1 = BSON( "a" << -1 );
+        BSONObj match2 = BSON( "a" << 11 );
+        BSONObj match3 = BSON( "a" << 5 );
+        BSONObj notMatch = BSON( "a" << "6" );
+        auto_ptr<ComparisonExpression> sub1( new ComparisonExpression() );
+        ASSERT( sub1->init( "a", baseOperand1[ "$lt" ] ).isOK() );
+        auto_ptr<ComparisonExpression> sub2( new ComparisonExpression() );
+        ASSERT( sub2->init( "a", baseOperand2[ "$gt" ] ).isOK() );
+        auto_ptr<ComparisonExpression> sub3( new ComparisonExpression() );
+        ASSERT( sub3->init( "a", baseOperand3[ "a" ] ).isOK() );
+        OwnedPointerVector<MatchExpression> subExpressions;
+        subExpressions.mutableVector().push_back( sub1.release() );
+        subExpressions.mutableVector().push_back( sub2.release() );
+        subExpressions.mutableVector().push_back( sub3.release() );
+        OrOp orOp;
+        ASSERT( orOp.init( &subExpressions ).isOK() );
+        ASSERT( orOp.matchesSingleElement( match1[ "a" ] ) );
+        ASSERT( orOp.matchesSingleElement( match2[ "a" ] ) );
+        ASSERT( orOp.matchesSingleElement( match3[ "a" ] ) );
+        ASSERT( !orOp.matchesSingleElement( notMatch[ "a" ] ) );
+    }
+    */
+    TEST( OrOp, MatchesSingleClause ) {
+        BSONObj baseOperand = BSON( "$ne" << 5 );
+        auto_ptr<ComparisonExpression> ne( new ComparisonExpression() );
+        ASSERT( ne->init( "a", ComparisonExpression::NE, baseOperand[ "$ne" ] ).isOK() );
+
+        OrExpression orOp;
+        orOp.add( ne.release() );
+
+        ASSERT( orOp.matches( BSON( "a" << 4 ), NULL ) );
+        ASSERT( orOp.matches( BSON( "a" << BSON_ARRAY( 4 << 6 ) ), NULL ) );
+        ASSERT( !orOp.matches( BSON( "a" << 5 ), NULL ) );
+        ASSERT( !orOp.matches( BSON( "a" << BSON_ARRAY( 4 << 5 ) ), NULL ) );
+    }
+
+    TEST( OrOp, MatchesThreeClauses ) {
+        BSONObj baseOperand1 = BSON( "$gt" << 10 );
+        BSONObj baseOperand2 = BSON( "$lt" << 0 );
+        BSONObj baseOperand3 = BSON( "b" << 100 );
+        auto_ptr<ComparisonExpression> sub1( new ComparisonExpression() );
+        ASSERT( sub1->init( "a", ComparisonExpression::GT, baseOperand1[ "$gt" ] ).isOK() );
+        auto_ptr<ComparisonExpression> sub2( new ComparisonExpression() );
+        ASSERT( sub2->init( "a", ComparisonExpression::LT, baseOperand2[ "$lt" ] ).isOK() );
+        auto_ptr<ComparisonExpression> sub3( new ComparisonExpression() );
+        ASSERT( sub3->init( "b", ComparisonExpression::EQ, baseOperand3[ "b" ] ).isOK() );
+
+        OrExpression orOp;
+        orOp.add( sub1.release() );
+        orOp.add( sub2.release() );
+        orOp.add( sub3.release() );
+
+        ASSERT( orOp.matches( BSON( "a" << -1 ), NULL ) );
+        ASSERT( orOp.matches( BSON( "a" << 11 ), NULL ) );
+        ASSERT( !orOp.matches( BSON( "a" << 5 ), NULL ) );
+        ASSERT( orOp.matches( BSON( "b" << 100 ), NULL ) );
+        ASSERT( !orOp.matches( BSON( "b" << 101 ), NULL ) );
+        ASSERT( !orOp.matches( BSONObj(), NULL ) );
+        ASSERT( orOp.matches( BSON( "a" << 11 << "b" << 100 ), NULL ) );
+    }
+
+    TEST( OrOp, ElemMatchKey ) {
+        BSONObj baseOperand1 = BSON( "a" << 1 );
+        BSONObj baseOperand2 = BSON( "b" << 2 );
+        auto_ptr<ComparisonExpression> sub1( new ComparisonExpression() );
+        ASSERT( sub1->init( "a", ComparisonExpression::EQ, baseOperand1[ "a" ] ).isOK() );
+        auto_ptr<ComparisonExpression> sub2( new ComparisonExpression() );
+        ASSERT( sub2->init( "b", ComparisonExpression::EQ, baseOperand2[ "b" ] ).isOK() );
+
+        OrExpression orOp;
+        orOp.add( sub1.release() );
+        orOp.add( sub2.release() );
+
+        MatchDetails details;
+        details.requestElemMatchKey();
+        ASSERT( !orOp.matches( BSONObj(), &details ) );
+        ASSERT( !details.hasElemMatchKey() );
+        ASSERT( !orOp.matches( BSON( "a" << BSON_ARRAY( 10 ) << "b" << BSON_ARRAY( 10 ) ),
+                               &details ) );
+        ASSERT( !details.hasElemMatchKey() );
+        ASSERT( orOp.matches( BSON( "a" << BSON_ARRAY( 1 ) << "b" << BSON_ARRAY( 1 << 2 ) ),
+                              &details ) );
+        // The elem match key feature is not implemented for $or.
+        ASSERT( !details.hasElemMatchKey() );
+    }
+
+    /**
+    TEST( OrOp, MatchesIndexKeyWithoutUnknown ) {
+        BSONObj baseOperand1 = BSON( "$gt" << 5 );
+        BSONObj baseOperand2 = BSON( "$lt" << 1 );
+        auto_ptr<ComparisonExpression> sub1( new ComparisonExpression() );
+        ASSERT( sub1->init( "a", baseOperand1[ "$gt" ] ).isOK() );
+        auto_ptr<ComparisonExpression> sub2( new ComparisonExpression() );
+        ASSERT( sub2->init( "a", baseOperand2[ "$lt" ] ).isOK() );
+        OwnedPointerVector<MatchExpression> subExpressions;
+        subExpressions.mutableVector().push_back( sub1.release() );
+        subExpressions.mutableVector().push_back( sub2.release() );
+        OrOp orOp;
+        ASSERT( orOp.init( &subExpressions ).isOK() );
+        IndexSpec indexSpec( BSON( "a" << 1 ) );
+        ASSERT( MatchExpression::PartialMatchResult_False ==
+                orOp.matchesIndexKey( BSON( "" << 3 ), indexSpec ) );
+        ASSERT( MatchExpression::PartialMatchResult_True ==
+                orOp.matchesIndexKey( BSON( "" << 0 ), indexSpec ) );
+        ASSERT( MatchExpression::PartialMatchResult_True ==
+                orOp.matchesIndexKey( BSON( "" << 6 ), indexSpec ) );
+    }
+    
+    TEST( OrOp, MatchesIndexKeyWithUnknown ) {
+        BSONObj baseOperand1 = BSON( "$gt" << 5 );
+        BSONObj baseOperand2 = BSON( "$lt" << 1 );
+        // This part will return PartialMatchResult_Unknown.
+        BSONObj baseOperand3 = BSON( "$ne" << 5 );
+        auto_ptr<ComparisonExpression> sub1( new ComparisonExpression() );
+        ASSERT( sub1->init( "a", baseOperand1[ "$gt" ] ).isOK() );
+        auto_ptr<ComparisonExpression> sub2( new ComparisonExpression() );
+        ASSERT( sub2->init( "a", baseOperand2[ "$lt" ] ).isOK() );
+        auto_ptr<NeOp> sub3( new NeOp() );
+        ASSERT( sub3->init( "a", baseOperand3[ "$ne" ] ).isOK() );
+        OwnedPointerVector<MatchExpression> subExpressions;
+        subExpressions.mutableVector().push_back( sub1.release() );
+        subExpressions.mutableVector().push_back( sub2.release() );
+        subExpressions.mutableVector().push_back( sub3.release() );
+        OrOp orOp;
+        ASSERT( orOp.init( &subExpressions ).isOK() );
+        IndexSpec indexSpec( BSON( "a" << 1 ) );
+        ASSERT( MatchExpression::PartialMatchResult_Unknown ==
+                orOp.matchesIndexKey( BSON( "" << 3 ), indexSpec ) );
+        ASSERT( MatchExpression::PartialMatchResult_True ==
+                orOp.matchesIndexKey( BSON( "" << 0 ), indexSpec ) );
+        ASSERT( MatchExpression::PartialMatchResult_True ==
+                orOp.matchesIndexKey( BSON( "" << 6 ), indexSpec ) );
+    }
+    */
+
+    /**
+    TEST( NorOp, MatchesElementSingleClause ) {
+        BSONObj baseOperand = BSON( "$lt" << 5 );
+        BSONObj match = BSON( "a" << 5 );
+        BSONObj notMatch = BSON( "a" << 4 );
+        auto_ptr<ComparisonExpression> lt( new ComparisonExpression() );
+        ASSERT( lt->init( "a", baseOperand[ "$lt" ] ).isOK() );
+        OwnedPointerVector<MatchExpression> subExpressions;
+        subExpressions.mutableVector().push_back( lt.release() );
+        NorOp norOp;
+        ASSERT( norOp.init( &subExpressions ).isOK() );
+        ASSERT( norOp.matchesSingleElement( match[ "a" ] ) );
+        ASSERT( !norOp.matchesSingleElement( notMatch[ "a" ] ) );
+    }
+    */
+
+    TEST( NorOp, NoClauses ) {
+        NorExpression norOp;
+        ASSERT( norOp.matches( BSONObj(), NULL ) );
+    }
+    /*
+    TEST( NorOp, MatchesElementThreeClauses ) {
+        BSONObj baseOperand1 = BSON( "$lt" << 0 );
+        BSONObj baseOperand2 = BSON( "$gt" << 10 );
+        BSONObj baseOperand3 = BSON( "a" << 5 );
+        BSONObj notMatch1 = BSON( "a" << -1 );
+        BSONObj notMatch2 = BSON( "a" << 11 );
+        BSONObj notMatch3 = BSON( "a" << 5 );
+        BSONObj match = BSON( "a" << "6" );
+        auto_ptr<ComparisonExpression> sub1( new ComparisonExpression() );
+        ASSERT( sub1->init( "a", baseOperand1[ "$lt" ] ).isOK() );
+        auto_ptr<ComparisonExpression> sub2( new ComparisonExpression() );
+        ASSERT( sub2->init( "a", baseOperand2[ "$gt" ] ).isOK() );
+        auto_ptr<ComparisonExpression> sub3( new ComparisonExpression() );
+        ASSERT( sub3->init( "a", baseOperand3[ "a" ] ).isOK() );
+        OwnedPointerVector<MatchExpression> subExpressions;
+        subExpressions.mutableVector().push_back( sub1.release() );
+        subExpressions.mutableVector().push_back( sub2.release() );
+        subExpressions.mutableVector().push_back( sub3.release() );
+        NorOp norOp;
+        ASSERT( norOp.init( &subExpressions ).isOK() );
+        ASSERT( !norOp.matchesSingleElement( notMatch1[ "a" ] ) );
+        ASSERT( !norOp.matchesSingleElement( notMatch2[ "a" ] ) );
+        ASSERT( !norOp.matchesSingleElement( notMatch3[ "a" ] ) );
+        ASSERT( norOp.matchesSingleElement( match[ "a" ] ) );
+    }
+    */
+
+    TEST( NorOp, MatchesSingleClause ) {
+        BSONObj baseOperand = BSON( "$ne" << 5 );
+        auto_ptr<ComparisonExpression> ne( new ComparisonExpression() );
+        ASSERT( ne->init( "a", ComparisonExpression::NE, baseOperand[ "$ne" ] ).isOK() );
+
+        NorExpression norOp;
+        norOp.add( ne.release() );
+
+        ASSERT( !norOp.matches( BSON( "a" << 4 ), NULL ) );
+        ASSERT( !norOp.matches( BSON( "a" << BSON_ARRAY( 4 << 6 ) ), NULL ) );
+        ASSERT( norOp.matches( BSON( "a" << 5 ), NULL ) );
+        ASSERT( norOp.matches( BSON( "a" << BSON_ARRAY( 4 << 5 ) ), NULL ) );
+    }
+
+    TEST( NorOp, MatchesThreeClauses ) {
+        BSONObj baseOperand1 = BSON( "$gt" << 10 );
+        BSONObj baseOperand2 = BSON( "$lt" << 0 );
+        BSONObj baseOperand3 = BSON( "b" << 100 );
+
+        auto_ptr<ComparisonExpression> sub1( new ComparisonExpression() );
+        ASSERT( sub1->init( "a", ComparisonExpression::GT, baseOperand1[ "$gt" ] ).isOK() );
+        auto_ptr<ComparisonExpression> sub2( new ComparisonExpression() );
+        ASSERT( sub2->init( "a", ComparisonExpression::LT, baseOperand2[ "$lt" ] ).isOK() );
+        auto_ptr<ComparisonExpression> sub3( new ComparisonExpression() );
+        ASSERT( sub3->init( "b", ComparisonExpression::EQ, baseOperand3[ "b" ] ).isOK() );
+
+        NorExpression norOp;
+        norOp.add( sub1.release() );
+        norOp.add( sub2.release() );
+        norOp.add( sub3.release() );
+
+        ASSERT( !norOp.matches( BSON( "a" << -1 ), NULL ) );
+        ASSERT( !norOp.matches( BSON( "a" << 11 ), NULL ) );
+        ASSERT( norOp.matches( BSON( "a" << 5 ), NULL ) );
+        ASSERT( !norOp.matches( BSON( "b" << 100 ), NULL ) );
+        ASSERT( norOp.matches( BSON( "b" << 101 ), NULL ) );
+        ASSERT( norOp.matches( BSONObj(), NULL ) );
+        ASSERT( !norOp.matches( BSON( "a" << 11 << "b" << 100 ), NULL ) );
+    }
+
+    TEST( NorOp, ElemMatchKey ) {
+        BSONObj baseOperand1 = BSON( "a" << 1 );
+        BSONObj baseOperand2 = BSON( "b" << 2 );
+        auto_ptr<ComparisonExpression> sub1( new ComparisonExpression() );
+        ASSERT( sub1->init( "a", ComparisonExpression::EQ, baseOperand1[ "a" ] ).isOK() );
+        auto_ptr<ComparisonExpression> sub2( new ComparisonExpression() );
+        ASSERT( sub2->init( "b", ComparisonExpression::EQ, baseOperand2[ "b" ] ).isOK() );
+
+        NorExpression norOp;
+        norOp.add( sub1.release() );
+        norOp.add( sub2.release() );
+
+        MatchDetails details;
+        details.requestElemMatchKey();
+        ASSERT( !norOp.matches( BSON( "a" << 1 ), &details ) );
+        ASSERT( !details.hasElemMatchKey() );
+        ASSERT( !norOp.matches( BSON( "a" << BSON_ARRAY( 1 ) << "b" << BSON_ARRAY( 10 ) ),
+                                &details ) );
+        ASSERT( !details.hasElemMatchKey() );
+        ASSERT( norOp.matches( BSON( "a" << BSON_ARRAY( 3 ) << "b" << BSON_ARRAY( 4 ) ),
+                               &details ) );
+        // The elem match key feature is not implemented for $nor.
+        ASSERT( !details.hasElemMatchKey() );
+    }
+
+    /**
+    TEST( NorOp, MatchesIndexKey ) {
+        BSONObj baseOperand = BSON( "a" << 5 );
+        auto_ptr<ComparisonExpression> eq( new ComparisonExpression() );
+        ASSERT( eq->init( "a", baseOperand[ "a" ] ).isOK() );
+        OwnedPointerVector<MatchExpression> subExpressions;
+        subExpressions.mutableVector().push_back( eq.release() );
+        NorOp norOp;
+        ASSERT( norOp.init( &subExpressions ).isOK() );
+        IndexSpec indexSpec( BSON( "a" << 1 ) );
+        BSONObj indexKey = BSON( "" << "7" );
+        ASSERT( MatchExpression::PartialMatchResult_Unknown ==
+                norOp.matchesIndexKey( indexKey, indexSpec ) );
+    }
+    */
+
+}