SERVER-16256 get rid of ALL match expressions

Every $all should parse to an AND match expression. This simplifies the
implementation, and fixes a bug related to bounds building for $all-$elemMatch
constructions.

(cherry picked from commit 430f62da7380a6864058c2f75a64c5d662a95176)

Conflicts:
	src/mongo/db/matcher/expression_array.cpp
	src/mongo/db/matcher/expression_array.h
	src/mongo/db/query/query_planner_test.cpp
	src/mongo/s/chunk_manager_targeter_test.cpp

12 files changed, 166 insertions, 261 deletions

diff --git a/src/mongo/db/matcher/expression.h b/src/mongo/db/matcher/expression.h
index 8f37a6a7c62..083a2583208 100644
--- a/src/mongo/db/matcher/expression.h
+++ b/src/mongo/db/matcher/expression.h
@@ -50,7 +50,7 @@ namespace mongo {
             AND, OR, NOR, NOT,
 
             // array types
-            ALL, ELEM_MATCH_OBJECT, ELEM_MATCH_VALUE, SIZE,
+            ELEM_MATCH_OBJECT, ELEM_MATCH_VALUE, SIZE,
 
             // leaf types
             LTE, LT, EQ, GT, GTE, REGEX, MOD, EXISTS, MATCH_IN, NIN,
@@ -124,11 +124,11 @@ namespace mongo {
          * Is this node an array operator?  Array operators have multiple clauses but operate on one
          * field.
          *
-         * ALL (AllElemMatchOp)
          * ELEM_MATCH_VALUE, ELEM_MATCH_OBJECT, SIZE (ArrayMatchingMatchExpression)
          */
         bool isArray() const {
-            return SIZE == _matchType || ALL == _matchType || ELEM_MATCH_VALUE == _matchType
+            return SIZE == _matchType
+                   || ELEM_MATCH_VALUE == _matchType
                    || ELEM_MATCH_OBJECT == _matchType;
         }
 
diff --git a/src/mongo/db/matcher/expression_array.cpp b/src/mongo/db/matcher/expression_array.cpp
index 9ba1c956f9a..73209d71d56 100644
--- a/src/mongo/db/matcher/expression_array.cpp
+++ b/src/mongo/db/matcher/expression_array.cpp
@@ -191,91 +191,6 @@ namespace mongo {
     }
 
 
-    // ------
-
-    AllElemMatchOp::~AllElemMatchOp() {
-        for ( unsigned i = 0; i < _list.size(); i++ )
-            delete _list[i];
-        _list.clear();
-    }
-
-    Status AllElemMatchOp::init( const StringData& path ) {
-        _path = path;
-        Status s = _elementPath.init( _path );
-        _elementPath.setTraverseLeafArray( false );
-        return s;
-    }
-
-    void AllElemMatchOp::add( ArrayMatchingMatchExpression* expr ) {
-        verify( expr );
-        _list.push_back( expr );
-    }
-
-    bool AllElemMatchOp::matches( const MatchableDocument* doc, MatchDetails* details ) const {
-        MatchableDocument::IteratorHolder cursor( doc, &_elementPath );
-        while ( cursor->more() ) {
-            ElementIterator::Context e = cursor->next();
-            if ( e.element().type() != Array )
-                continue;
-            if ( _allMatch( e.element().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 ( !static_cast<ArrayMatchingMatchExpression*>(_list[i])->matchesArray(
-                     anArray, NULL ) )
-                return false;
-        }
-        return true;
-    }
-
-
-    void AllElemMatchOp::debugString( StringBuilder& debug, int level ) const {
-        _debugAddSpace( debug, level );
-        debug << _path << " AllElemMatchOp:";
-        MatchExpression::TagData* td = getTag();
-        if (NULL != td) {
-            debug << " ";
-            td->debugString(&debug);
-        }
-        debug << "\n";
-        for ( size_t i = 0; i < _list.size(); i++ ) {
-            _list[i]->debugString( debug, level + 1);
-        }
-
-    }
-
-    bool AllElemMatchOp::equivalent( const MatchExpression* other ) const {
-        if ( matchType() != other->matchType() )
-            return false;
-
-        const AllElemMatchOp* realOther = static_cast<const AllElemMatchOp*>( other );
-        if ( _path != realOther->_path )
-            return false;
-
-        if ( _list.size() != realOther->_list.size() )
-            return false;
-
-        for ( unsigned i = 0; i < _list.size(); i++ )
-            if ( !_list[i]->equivalent( realOther->_list[i] ) )
-                return false;
-
-        return true;
-    }
-
-
     // ---------
 
     Status SizeMatchExpression::init( const StringData& path, int size ) {
diff --git a/src/mongo/db/matcher/expression_array.h b/src/mongo/db/matcher/expression_array.h
index 06f9283bd57..3f1dba5a88b 100644
--- a/src/mongo/db/matcher/expression_array.h
+++ b/src/mongo/db/matcher/expression_array.h
@@ -40,9 +40,6 @@
 
 namespace mongo {
 
-    /**
-     * ALL and ELEM_MATCH inherit from this.
-     */
     class ArrayMatchingMatchExpression : public MatchExpression {
     public:
         ArrayMatchingMatchExpression( MatchType matchType ) : MatchExpression( matchType ){}
@@ -155,55 +152,4 @@ namespace mongo {
         int _size; // >= 0 real, < 0, nothing will match
     };
 
-    /**
-     * i'm suprised this isn't a regular AllMatchExpression
-     */
-    class AllElemMatchOp : public MatchExpression {
-    public:
-        AllElemMatchOp() : MatchExpression( ALL ){}
-        virtual ~AllElemMatchOp();
-
-        Status init( const StringData& path );
-        void add( ArrayMatchingMatchExpression* expr );
-
-        virtual MatchExpression* shallowClone() const {
-            AllElemMatchOp* e = new AllElemMatchOp();
-            e->init(path());
-            for (size_t i = 0; i < _list.size(); ++i) {
-                e->add(reinterpret_cast<ArrayMatchingMatchExpression*>(
-                    _list[i]->shallowClone()));
-            }
-            if ( getTag() ) {
-                e->setTag(getTag()->clone());
-            }
-            return e;
-        }
-
-        virtual bool matches( const MatchableDocument* 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;
-
-        virtual bool equivalent( const MatchExpression* other ) const;
-
-        virtual size_t numChildren() const { return _list.size(); }
-
-        virtual MatchExpression* getChild( size_t i ) const { return _list[i]; }
-
-        virtual std::vector<MatchExpression*>* getChildVector() { return &_list; }
-
-        const StringData path() const { return _path; }
-
-    private:
-        bool _allMatch( const BSONObj& anArray ) const;
-
-        StringData _path;
-        ElementPath _elementPath;
-        std::vector<MatchExpression*> _list;
-    };
-
 }
diff --git a/src/mongo/db/matcher/expression_array_test.cpp b/src/mongo/db/matcher/expression_array_test.cpp
index 6ad91d990ee..626ac72409e 100644
--- a/src/mongo/db/matcher/expression_array_test.cpp
+++ b/src/mongo/db/matcher/expression_array_test.cpp
@@ -291,7 +291,7 @@ namespace mongo {
     }
     */
 
-    TEST( AllElemMatchOp, MatchesElement ) {
+    TEST( AndOfElemMatch, MatchesElement ) {
 
 
         BSONObj baseOperanda1 = BSON( "a" << 1 );
@@ -322,36 +322,35 @@ namespace mongo {
         auto_ptr<AndMatchExpression> and2( new AndMatchExpression() );
         and2->add( eqa2.release() );
         and2->add( eqb2.release() );
+        // and2 = { a : 2, b : 2 }
 
         auto_ptr<ElemMatchObjectMatchExpression> elemMatch2( new ElemMatchObjectMatchExpression() );
         elemMatch2->init( "x", and2.release() );
         // elemMatch2 = { x : { $elemMatch : { a : 2, b : 2 } } }
 
-        AllElemMatchOp op;
-        op.init( "" );
-        op.add( elemMatch1.release() );
-        op.add( elemMatch2.release() );
+        auto_ptr<AndMatchExpression> andOfEM( new AndMatchExpression() );
+        andOfEM->add( elemMatch1.release() );
+        andOfEM->add( elemMatch2.release() );
 
         BSONObj nonArray = BSON( "x" << 4 );
-        ASSERT( !op.matchesSingleElement( nonArray[ "x" ] ) );
+        ASSERT( !andOfEM->matchesSingleElement( nonArray[ "x" ] ) );
         BSONObj emptyArray = BSON( "x" << BSONArray() );
-        ASSERT( !op.matchesSingleElement( emptyArray[ "x" ] ) );
+        ASSERT( !andOfEM->matchesSingleElement( emptyArray[ "x" ] ) );
         BSONObj nonObjArray = BSON( "x" << BSON_ARRAY( 4 ) );
-        ASSERT( !op.matchesSingleElement( nonObjArray[ "x" ] ) );
+        ASSERT( !andOfEM->matchesSingleElement( nonObjArray[ "x" ] ) );
         BSONObj singleObjMatch = BSON( "x" << BSON_ARRAY( BSON( "a" << 1 << "b" << 1 ) ) );
-        ASSERT( !op.matchesSingleElement( singleObjMatch[ "x" ] ) );
+        ASSERT( !andOfEM->matchesSingleElement( singleObjMatch[ "x" ] ) );
         BSONObj otherObjMatch = BSON( "x" << BSON_ARRAY( BSON( "a" << 2 << "b" << 2 ) ) );
-        ASSERT( !op.matchesSingleElement( otherObjMatch[ "x" ] ) );
+        ASSERT( !andOfEM->matchesSingleElement( otherObjMatch[ "x" ] ) );
         BSONObj bothObjMatch = BSON( "x" << BSON_ARRAY( BSON( "a" << 1 << "b" << 1 ) <<
                                                         BSON( "a" << 2 << "b" << 2 ) ) );
-        ASSERT( op.matchesSingleElement( bothObjMatch[ "x" ] ) );
+        ASSERT( andOfEM->matchesSingleElement( bothObjMatch[ "x" ] ) );
         BSONObj noObjMatch = BSON( "x" << BSON_ARRAY( BSON( "a" << 1 << "b" << 2 ) <<
                                                       BSON( "a" << 2 << "b" << 1 ) ) );
-        ASSERT( !op.matchesSingleElement( noObjMatch[ "x" ] ) );
+        ASSERT( !andOfEM->matchesSingleElement( noObjMatch[ "x" ] ) );
     }
 
-
-    TEST( AllElemMatchOp, Matches ) {
+    TEST( AndOfElemMatch, Matches ) {
         BSONObj baseOperandgt1 = BSON( "$gt" << 1 );
         auto_ptr<ComparisonMatchExpression> gt1( new GTMatchExpression() );
         ASSERT( gt1->init( "", baseOperandgt1[ "$gt" ] ).isOK() );
@@ -364,6 +363,7 @@ namespace mongo {
         elemMatch1->init( "x" );
         elemMatch1->add( gt1.release() );
         elemMatch1->add( lt1.release() );
+        // elemMatch1 = { x : { $elemMatch : { $gt : 1 , $lt : 10 } } }
 
         BSONObj baseOperandgt2 = BSON( "$gt" << 101 );
         auto_ptr<ComparisonMatchExpression> gt2( new GTMatchExpression() );
@@ -377,46 +377,27 @@ namespace mongo {
         elemMatch2->init( "x" );
         elemMatch2->add( gt2.release() );
         elemMatch2->add( lt2.release() );
+        // elemMatch2 = { x : { $elemMatch : { $gt : 101 , $lt : 110 } } }
 
-        AllElemMatchOp op;
-        op.init( "x" );
-        op.add( elemMatch1.release() );
-        op.add( elemMatch2.release() );
-
+        auto_ptr<AndMatchExpression> andOfEM( new AndMatchExpression() );
+        andOfEM->add( elemMatch1.release() );
+        andOfEM->add( elemMatch2.release() );
 
         BSONObj nonArray = BSON( "x" << 4 );
-        ASSERT( !op.matchesBSON( nonArray, NULL ) );
+        ASSERT( !andOfEM->matchesBSON( nonArray, NULL ) );
         BSONObj emptyArray = BSON( "x" << BSONArray() );
-        ASSERT( !op.matchesBSON( emptyArray, NULL ) );
+        ASSERT( !andOfEM->matchesBSON( emptyArray, NULL ) );
         BSONObj nonNumberArray = BSON( "x" << BSON_ARRAY( "q" ) );
-        ASSERT( !op.matchesBSON( nonNumberArray, NULL ) );
+        ASSERT( !andOfEM->matchesBSON( nonNumberArray, NULL ) );
         BSONObj singleMatch = BSON( "x" << BSON_ARRAY( 5 ) );
-        ASSERT( !op.matchesBSON( singleMatch, NULL ) );
+        ASSERT( !andOfEM->matchesBSON( singleMatch, NULL ) );
         BSONObj otherMatch = BSON( "x" << BSON_ARRAY( 105 ) );
-        ASSERT( !op.matchesBSON( otherMatch, NULL ) );
+        ASSERT( !andOfEM->matchesBSON( otherMatch, NULL ) );
         BSONObj bothMatch = BSON( "x" << BSON_ARRAY( 5 << 105 ) );
-        ASSERT( op.matchesBSON( bothMatch, NULL ) );
+        ASSERT( andOfEM->matchesBSON( bothMatch, NULL ) );
         BSONObj neitherMatch = BSON( "x" << BSON_ARRAY( 0 << 200 ) );
-        ASSERT( !op.matchesBSON( neitherMatch, NULL ) );
-    }
-
-    /**
-    TEST( AllElemMatchOp, MatchesIndexKey ) {
-        BSONObj baseOperand = BSON( "$lt" << 5 );
-        auto_ptr<LtOp> lt( new ComparisonMatchExpression() );
-        ASSERT( lt->init( "a", baseOperand[ "$lt" ] ).isOK() );
-        auto_ptr<ElemMatchValueMatchExpression> elemMatchValueOp( new ElemMatchValueMatchExpression() );
-        ASSERT( elemMatchValueOp->init( "a", lt.release() ).isOK() );
-        OwnedPointerVector<MatchMatchExpression> subMatchExpressions;
-        subMatchExpressions.mutableVector().push_back( elemMatchValueOp.release() );
-        AllElemMatchOp allElemMatchOp;
-        ASSERT( allElemMatchOp.init( &subMatchExpressions ).isOK() );
-        IndexSpec indexSpec( BSON( "a" << 1 ) );
-        BSONObj indexKey = BSON( "" << "3" );
-        ASSERT( MatchMatchExpression::PartialMatchResult_Unknown ==
-                allElemMatchOp.matchesIndexKey( indexKey, indexSpec ) );
+        ASSERT( !andOfEM->matchesBSON( neitherMatch, NULL ) );
     }
-    */
 
     TEST( SizeMatchExpression, MatchesElement ) {
         BSONObj match = BSON( "a" << BSON_ARRAY( 5 << 6 ) );
diff --git a/src/mongo/db/matcher/expression_parser.cpp b/src/mongo/db/matcher/expression_parser.cpp
index ff4072725f7..348745c7dc4 100644
--- a/src/mongo/db/matcher/expression_parser.cpp
+++ b/src/mongo/db/matcher/expression_parser.cpp
@@ -728,17 +728,14 @@ namespace mongo {
             return StatusWithMatchExpression( ErrorCodes::BadValue, "$all needs an array" );
 
         BSONObj arr = e.Obj();
+        std::auto_ptr<AndMatchExpression> myAnd( new AndMatchExpression() );
+        BSONObjIterator i( arr );
+
         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 StatusWithMatchExpression( s );
-
-            BSONObjIterator i( arr );
             while ( i.more() ) {
                 BSONElement hopefullyElemMatchElement = i.next();
 
@@ -757,17 +754,15 @@ namespace mongo {
                 }
 
                 StatusWithMatchExpression inner =
-                    _parseElemMatch( "", hopefullyElemMatchObj.firstElement(), level );
+                    _parseElemMatch( name, hopefullyElemMatchObj.firstElement(), level );
                 if ( !inner.isOK() )
                     return inner;
-                temp->add( static_cast<ArrayMatchingMatchExpression*>( inner.getValue() ) );
+                myAnd->add( inner.getValue() );
             }
 
-            return StatusWithMatchExpression( temp.release() );
+            return StatusWithMatchExpression( myAnd.release() );
         }
 
-        std::auto_ptr<AndMatchExpression> myAnd( new AndMatchExpression() );
-        BSONObjIterator i( arr );
         while ( i.more() ) {
             BSONElement e = i.next();
 
diff --git a/src/mongo/db/matcher/expression_parser_array_test.cpp b/src/mongo/db/matcher/expression_parser_array_test.cpp
index 9230298a019..e2818bb245b 100644
--- a/src/mongo/db/matcher/expression_parser_array_test.cpp
+++ b/src/mongo/db/matcher/expression_parser_array_test.cpp
@@ -308,6 +308,9 @@ namespace mongo {
         StatusWithMatchExpression result = MatchExpressionParser::parse( query );
         ASSERT_TRUE( result.isOK() );
 
+        // Verify that the $all got parsed to AND.
+        ASSERT_EQUALS( MatchExpression::AND, result.getValue()->matchType() );
+
         ASSERT( !result.getValue()->matchesBSON( BSON( "x" << 1 ) ) );
         ASSERT( !result.getValue()->matchesBSON( BSON( "x" << BSON_ARRAY( 1 ) ) ) );
         ASSERT( !result.getValue()->matchesBSON( BSON( "x" << BSON_ARRAY( 2 ) ) ) );
@@ -321,6 +324,9 @@ namespace mongo {
         StatusWithMatchExpression result = MatchExpressionParser::parse( query );
         ASSERT_TRUE( result.isOK() );
 
+        // Verify that the $all got parsed to AND.
+        ASSERT_EQUALS( MatchExpression::AND, result.getValue()->matchType() );
+
         ASSERT( !result.getValue()->matchesBSON( BSON( "x" << 1 ) ) );
         ASSERT( !result.getValue()->matchesBSON( BSON( "x" << BSON_ARRAY( 1 ) ) ) );
         ASSERT( result.getValue()->matchesBSON( BSON( "x" << BSONNULL ) ) );
@@ -358,6 +364,9 @@ namespace mongo {
         StatusWithMatchExpression result = MatchExpressionParser::parse( query );
         ASSERT_TRUE( result.isOK() );
 
+        // Verify that the $all got parsed to AND.
+        ASSERT_EQUALS( MatchExpression::AND, result.getValue()->matchType() );
+
         BSONObj notMatchFirst = BSON( "a" << "ax" );
         BSONObj notMatchSecond = BSON( "a" << "qqb" );
         BSONObj matchesBoth = BSON( "a" << "ab" );
@@ -378,6 +387,9 @@ namespace mongo {
         StatusWithMatchExpression result = MatchExpressionParser::parse( query );
         ASSERT_TRUE( result.isOK() );
 
+        // Verify that the $all got parsed to AND.
+        ASSERT_EQUALS( MatchExpression::AND, result.getValue()->matchType() );
+
         BSONObj notMatchFirst = BSON( "a" << "ax" );
         BSONObj matchesBoth = BSON( "a" << "abc" );
 
@@ -390,6 +402,9 @@ namespace mongo {
         StatusWithMatchExpression result = MatchExpressionParser::parse( query );
         ASSERT_TRUE( result.isOK() );
 
+        // Verify that the $all got parsed to AND.
+        ASSERT_EQUALS( MatchExpression::AND, result.getValue()->matchType() );
+
         ASSERT( result.getValue()->matchesBSON( BSON( "x" << 5 ) ) );
         ASSERT( result.getValue()->matchesBSON( BSON( "x" << BSON_ARRAY( 5 ) ) ) );
         ASSERT( !result.getValue()->matchesBSON( BSON( "x" << 4 ) ) );
@@ -403,6 +418,12 @@ namespace mongo {
         StatusWithMatchExpression result = MatchExpressionParser::parse( query );
         ASSERT_TRUE( result.isOK() );
 
+        // Verify that the $all got parsed to an AND with a single ELEM_MATCH_OBJECT child.
+        ASSERT_EQUALS( MatchExpression::AND, result.getValue()->matchType() );
+        ASSERT_EQUALS( 1U, result.getValue()->numChildren() );
+        MatchExpression* child = result.getValue()->getChild( 0 );
+        ASSERT_EQUALS( MatchExpression::ELEM_MATCH_OBJECT, child->matchType() );
+
         ASSERT( !result.getValue()->matchesBSON( BSON( "x" << 1 ) ) );
         ASSERT( !result.getValue()->matchesBSON( BSON( "x" << BSON_ARRAY( 1 << 2 ) ) ) );
         ASSERT( !result.getValue()->matchesBSON( BSON( "x" << BSON_ARRAY(  BSON( "x" << 1 ) ) ) ) );
@@ -420,6 +441,12 @@ namespace mongo {
         StatusWithMatchExpression result = MatchExpressionParser::parse( query );
         ASSERT_TRUE( result.isOK() );
 
+        // Verify that the $all got parsed to an AND with a single ELEM_MATCH_OBJECT child.
+        ASSERT_EQUALS( MatchExpression::AND, result.getValue()->matchType() );
+        ASSERT_EQUALS( 1U, result.getValue()->numChildren() );
+        MatchExpression* child = result.getValue()->getChild( 0 );
+        ASSERT_EQUALS( MatchExpression::ELEM_MATCH_OBJECT, child->matchType() );
+
         ASSERT( !result.getValue()->matchesBSON( BSON( "x" << BSON( "y" << 1 ) ) ) );
         ASSERT( !result.getValue()->matchesBSON( BSON( "x" << BSON( "y" <<
                                                                 BSON_ARRAY( 1 << 2 ) ) ) ) );
@@ -459,6 +486,41 @@ namespace mongo {
                                                         BSON( "x" << 1 << "z" << 1 ) ) ) ) ) ) );
     }
 
+    // Check the structure of the resulting MatchExpression, and make sure that the paths
+    // are correct.
+    TEST( MatchExpressionParserArrayTest, AllElemMatch3 ) {
+        BSONObj query = fromjson( "{x: {$all: [{$elemMatch: {y: 1, z: 1}}]}}" );
+        StatusWithMatchExpression result = MatchExpressionParser::parse( query );
+        ASSERT_TRUE( result.isOK() );
+
+        boost::scoped_ptr<MatchExpression> expr( result.getValue() );
+
+        // Root node should be an AND with one child.
+        ASSERT_EQUALS( MatchExpression::AND, expr->matchType() );
+        ASSERT_EQUALS( 1U, expr->numChildren() );
+
+        // Child should be an ELEM_MATCH_OBJECT with one child and path "x".
+        MatchExpression* emObject = expr->getChild( 0 );
+        ASSERT_EQUALS( MatchExpression::ELEM_MATCH_OBJECT, emObject->matchType() );
+        ASSERT_EQUALS( 1U, emObject->numChildren() );
+        ASSERT_EQUALS( "x", emObject->path().toString() );
+
+        // Child should be another AND with two children.
+        MatchExpression* and2 = emObject->getChild( 0 );
+        ASSERT_EQUALS( MatchExpression::AND, and2->matchType() );
+        ASSERT_EQUALS( 2U, and2->numChildren() );
+
+        // Both children should be equalites, with paths "y" and "z".
+        MatchExpression* leaf1 = and2->getChild( 0 );
+        ASSERT_EQUALS( MatchExpression::EQ, leaf1->matchType() );
+        ASSERT_EQUALS( 0U, leaf1->numChildren() );
+        ASSERT_EQUALS( "y", leaf1->path().toString() );
+        MatchExpression* leaf2 = and2->getChild( 1 );
+        ASSERT_EQUALS( MatchExpression::EQ, leaf2->matchType() );
+        ASSERT_EQUALS( 0U, leaf2->numChildren() );
+        ASSERT_EQUALS( "z", leaf2->path().toString() );
+    }
+
     TEST( MatchExpressionParserArrayTest, AllElemMatchBad ) {
         BSONObj internal = BSON( "x" << 1 << "y" << 2 );
 
@@ -471,6 +533,29 @@ namespace mongo {
         ASSERT_FALSE( result.isOK() );
     }
 
+    // You can't mix $elemMatch and regular equality inside $all.
+    TEST( MatchExpressionParserArrayTest, AllElemMatchBadMixed ) {
+        // $elemMatch first, equality second.
+        BSONObj bad1 = fromjson( "{x: {$all: [{$elemMatch: {y: 1}}, 3]}}" );
+        StatusWithMatchExpression result1 = MatchExpressionParser::parse( bad1 );
+        ASSERT_FALSE( result1.isOK() );
+
+        // equality first, $elemMatch second
+        BSONObj bad2 = fromjson( "{x: {$all: [3, {$elemMatch: {y: 1}}]}}" );
+        StatusWithMatchExpression result2 = MatchExpressionParser::parse( bad2 );
+        ASSERT_FALSE( result1.isOK() );
+
+        // $elemMatch first, object second
+        BSONObj bad3 = fromjson( "{x: {$all: [{$elemMatch: {y: 1}}, {z: 1}]}}" );
+        StatusWithMatchExpression result3 = MatchExpressionParser::parse( bad3 );
+        ASSERT_FALSE( result3.isOK() );
+
+        // object first, $elemMatch second
+        BSONObj bad4 = fromjson( "{x: {$all: [{z: 1}, {$elemMatch: {y: 1}}]}}" );
+        StatusWithMatchExpression result4 = MatchExpressionParser::parse( bad4 );
+        ASSERT_FALSE( result4.isOK() );
+    }
+
     // $all with empty string.
     TEST( MatchExpressionParserArrayTest, AllEmptyString ) {
         BSONObj query = BSON( "x" << BSON( "$all" << BSON_ARRAY( "" ) ) );
diff --git a/src/mongo/db/query/canonical_query.cpp b/src/mongo/db/query/canonical_query.cpp
index e07b1385933..72f194fad28 100644
--- a/src/mongo/db/query/canonical_query.cpp
+++ b/src/mongo/db/query/canonical_query.cpp
@@ -118,7 +118,6 @@ namespace {
         case MatchExpression::OR: return "or"; break;
         case MatchExpression::NOR: return "nr"; break;
         case MatchExpression::NOT: return "nt"; break;
-        case MatchExpression::ALL: return "al"; break;
         case MatchExpression::ELEM_MATCH_OBJECT: return "eo"; break;
         case MatchExpression::ELEM_MATCH_VALUE: return "ev"; break;
         case MatchExpression::SIZE: return "sz"; break;
diff --git a/src/mongo/db/query/indexability.h b/src/mongo/db/query/indexability.h
index 7791d4fad8b..03820679436 100644
--- a/src/mongo/db/query/indexability.h
+++ b/src/mongo/db/query/indexability.h
@@ -86,8 +86,7 @@ namespace mongo {
          * Example: a: {$elemMatch: {b:1, c:1}}.
          */
         static bool arrayUsesIndexOnChildren(const MatchExpression* me) {
-            return me->isArray() && (MatchExpression::ELEM_MATCH_OBJECT == me->matchType()
-                                     || MatchExpression::ALL == me->matchType());
+            return me->isArray() && MatchExpression::ELEM_MATCH_OBJECT == me->matchType();
         }
 
         /**
diff --git a/src/mongo/db/query/plan_enumerator.cpp b/src/mongo/db/query/plan_enumerator.cpp
index ec8c8dac4a0..35c629771ea 100644
--- a/src/mongo/db/query/plan_enumerator.cpp
+++ b/src/mongo/db/query/plan_enumerator.cpp
@@ -951,9 +951,7 @@ namespace mongo {
                 bool mandatory = expressionRequiresIndex(child);
 
                 // Recursively prepMemo for the subnode. We fall through
-                // to this case for logical nodes other than AND (e.g. OR)
-                // and for array nodes other than ELEM_MATCH_OBJECT or
-                // ELEM_MATCH_VALUE (e.g. ALL).
+                // to this case for logical nodes other than AND (e.g. OR).
                 if (prepMemo(child, context)) {
                     size_t childID = memoIDForNode(child);
 
diff --git a/src/mongo/db/query/planner_access.cpp b/src/mongo/db/query/planner_access.cpp
index c133a5c92bc..972cf778229 100644
--- a/src/mongo/db/query/planner_access.cpp
+++ b/src/mongo/db/query/planner_access.cpp
@@ -1080,42 +1080,12 @@ namespace mongo {
             else if (Indexability::arrayUsesIndexOnChildren(root)) {
                 QuerySolutionNode* solution = NULL;
 
-                if (MatchExpression::ALL == root->matchType()) {
-                    // Here, we formulate an AND of all the sub-clauses.
-                    auto_ptr<AndHashNode> ahn(new AndHashNode());
-
-                    for (size_t i = 0; i < root->numChildren(); ++i) {
-                        QuerySolutionNode* node = buildIndexedDataAccess(query,
-                                                                         root->getChild(i),
-                                                                         true,
-                                                                         indices);
-                        if (NULL != node) {
-                            ahn->children.push_back(node);
-                        }
-                    }
-
-                    // No children, no point in hashing nothing.
-                    if (0 == ahn->children.size()) { return NULL; }
-
-                    // AND of one child is just that child.
-                    if (1 == ahn->children.size()) {
-                        solution = ahn->children[0];
-                        ahn->children.clear();
-                        ahn.reset();
-                    }
-                    else {
-                        // More than one child.
-                        solution = ahn.release();
-                    }
-                }
-                else {
-                    verify(MatchExpression::ELEM_MATCH_OBJECT);
-                    // The child is an AND.
-                    verify(1 == root->numChildren());
-                    solution = buildIndexedDataAccess(query, root->getChild(0), true, indices);
-                    if (NULL == solution) {
-                        return NULL;
-                    }
+                invariant(MatchExpression::ELEM_MATCH_OBJECT);
+                // The child is an AND.
+                invariant(1 == root->numChildren());
+                solution = buildIndexedDataAccess(query, root->getChild(0), true, indices);
+                if (NULL == solution) {
+                    return NULL;
                 }
 
                 // There may be an array operator above us.
diff --git a/src/mongo/db/query/planner_access.h b/src/mongo/db/query/planner_access.h
index cd3e56fb092..2031f866190 100644
--- a/src/mongo/db/query/planner_access.h
+++ b/src/mongo/db/query/planner_access.h
@@ -211,8 +211,8 @@ namespace mongo {
         //
         // Indexed Data Access methods.
         //
-        // The inArrayOperator flag deserves some attention.  It is set when we're processing a child of
-        // a MatchExpression::ALL or MatchExpression::ELEM_MATCH_OBJECT.
+        // The inArrayOperator flag deserves some attention.  It is set when we're processing a
+        // child of an MatchExpression::ELEM_MATCH_OBJECT.
         //
         // When true, the following behavior changes for all methods below that take it as an argument:
         // 0. No deletion of MatchExpression(s).  In fact,
@@ -253,10 +253,10 @@ namespace mongo {
          * finding all predicates that can use an index directly and returning
          * them in the out-parameter vector 'out'.
          *
-         * Traverses only through $and and array nodes like $all.
+         * Traverses only through AND and ELEM_MATCH_OBJECT nodes.
          *
          * Other nodes (i.e. nodes which cannot use an index directly, and which are
-         * neither $and nor array nodes) are returned in 'subnodesOut' if they are
+         * neither AND nor ELEM_MATCH_OBJECT) are returned in 'subnodesOut' if they are
          * tagged to use an index.
          */
         static void findElemMatchChildren(const MatchExpression* node,
diff --git a/src/mongo/db/query/query_planner_test.cpp b/src/mongo/db/query/query_planner_test.cpp
index c98ea321d66..cc4b4b36f67 100644
--- a/src/mongo/db/query/query_planner_test.cpp
+++ b/src/mongo/db/query/query_planner_test.cpp
@@ -1436,26 +1436,43 @@ namespace {
         addIndex(BSON("foo.b" << 1));
         runQuery(fromjson("{foo: {$all: [ {$elemMatch: {a:1, b:1}}, {$elemMatch: {a:2, b:2}}]}}"));
 
-        ASSERT_EQUALS(getNumSolutions(), 5U);
+        assertNumSolutions(3U);
         assertSolutionExists("{cscan: {dir: 1, filter: {foo:{$all:"
                                 "[{$elemMatch:{a:1,b:1}},{$elemMatch:{a:2,b:2}}]}}}}");
-        // Two solutions exist for 'foo.a' which differ only by assignment of index tags.
-        assertSolutionExists("{fetch: {node: {ixscan: {filter: null, pattern: {'foo.a': 1}}}}}", 2);
-        // Two solutions exist for 'foo.b' which differ only by assignment of index tags.
-        assertSolutionExists("{fetch: {node: {ixscan: {filter: null, pattern: {'foo.b': 1}}}}}", 2);
-
-        // TODO: We're not checking for the filter above because canonically sorting
-        // the filter means that we cannot distinguish between match expressions that
-        // are tagged differently. We may want to add this capability to the query
-        // planner test lib in the future.
-        /*assertSolutionExists("{fetch: {filter: {foo:{$all:[{$elemMatch:{a:1,b:1}},{$elemMatch:{a:2,b:2}}]}}, "
-                                "node: {ixscan: {filter: null, pattern: {'foo.a': 1}}}}}");
-        assertSolutionExists("{fetch: {filter: {foo:{$all:[{$elemMatch:{a:2,b:2}},{$elemMatch:{a:1,b:1}}]}}, "
-                                "node: {ixscan: {filter: null, pattern: {'foo.a': 1}}}}}");
-        assertSolutionExists("{fetch: {filter: {foo:{$all:[{$elemMatch:{b:1,a:1}},{$elemMatch:{a:2,b:2}}]}}, "
-                                "node: {ixscan: {filter: null, pattern: {'foo.b': 1}}}}}");
-        assertSolutionExists("{fetch: {filter: {foo:{$all:[{$elemMatch:{b:2,a:2}},{$elemMatch:{a:1,b:1}}]}}, "
-                                "node: {ixscan: {filter: null, pattern: {'foo.b': 1}}}}}");*/
+
+        assertSolutionExists("{fetch: {node: {ixscan: {filter: null, pattern: {'foo.a': 1}}}}}");
+        assertSolutionExists("{fetch: {node: {ixscan: {filter: null, pattern: {'foo.b': 1}}}}}");
+    }
+
+    TEST_F(QueryPlannerTest, BasicAllElemMatch2) {
+        // true means multikey
+        addIndex(BSON("a.x" << 1), true);
+
+        runQuery(fromjson("{a: {$all: [{$elemMatch: {x: 3}}, {$elemMatch: {y: 5}}]}}"));
+
+        assertNumSolutions(2U);
+        assertSolutionExists("{cscan: {dir: 1}}");
+        assertSolutionExists("{fetch: {filter: {a:{$all:[{$elemMatch:{x:3}},{$elemMatch:{y:5}}]}},"
+                                "node: {ixscan: {pattern: {'a.x': 1},"
+                                    "bounds: {'a.x': [[3,3,true,true]]}}}}}");
+    }
+
+    // SERVER-16256
+    TEST_F(QueryPlannerTest, AllElemMatchCompound) {
+        // true means multikey
+        addIndex(BSON("d" << 1 << "a.b" << 1 << "a.c" << 1), true);
+
+        runQuery(fromjson("{d: 1, a: {$all: [{$elemMatch: {b: 2, c: 2}},"
+                                            "{$elemMatch: {b: 3, c: 3}}]}}"));
+
+        assertNumSolutions(2U);
+        assertSolutionExists("{cscan: {dir: 1}}");
+        assertSolutionExists("{fetch: {filter: {$and: [{a: {$elemMatch: {b: 2, c: 2}}},"
+                                                      "{a: {$elemMatch: {b: 3, c: 3}}}]},"
+                                "node: {ixscan: {filter: null, pattern: {d:1,'a.b':1,'a.c':1},"
+                                    "bounds: {d: [[1,1,true,true]],"
+                                             "'a.b': [[2,2,true,true]],"
+                                             "'a.c': [[2,2,true,true]]}}}}}");
     }
 
     // SERVER-13677