SERVER-13731 make depth limit in parsing work for deep trees other than AND and OR

(cherry picked from commit 78c850d9c512596a3a8f7e937840d67f52a14baf)

4 files changed, 77 insertions, 19 deletions

diff --git a/src/mongo/db/matcher/expression_parser.cpp b/src/mongo/db/matcher/expression_parser.cpp
index 2dd26cc4b4f..e8b1ad250ce 100644
--- a/src/mongo/db/matcher/expression_parser.cpp
+++ b/src/mongo/db/matcher/expression_parser.cpp
@@ -87,7 +87,8 @@ namespace mongo {
     StatusWithMatchExpression MatchExpressionParser::_parseSubField( const BSONObj& context,
                                                                      const AndMatchExpression* andSoFar,
                                                                      const char* name,
-                                                                     const BSONElement& e ) {
+                                                                     const BSONElement& e,
+                                                                     int level ) {
 
         // TODO: these should move to getGtLtOp, or its replacement
 
@@ -95,7 +96,7 @@ namespace mongo {
             return _parseComparison( name, new EqualityMatchExpression(), e );
 
         if ( mongoutils::str::equals( "$not", e.fieldName() ) ) {
-            return _parseNot( name, e );
+            return _parseNot( name, e, level );
         }
 
         int x = e.getGtLtOp(-1);
@@ -258,10 +259,10 @@ namespace mongo {
         }
 
         case BSONObj::opELEM_MATCH:
-            return _parseElemMatch( name, e );
+            return _parseElemMatch( name, e, level );
 
         case BSONObj::opALL:
-            return _parseAll( name, e );
+            return _parseAll( name, e, level );
 
         case BSONObj::opWITHIN:
         case BSONObj::opGEO_INTERSECTS:
@@ -377,7 +378,7 @@ namespace mongo {
             }
 
             if ( _isExpressionDocument( e, false ) ) {
-                Status s = _parseSub( e.fieldName(), e.Obj(), root.get() );
+                Status s = _parseSub( e.fieldName(), e.Obj(), root.get(), level );
                 if ( !s.isOK() )
                     return StatusWithMatchExpression( s );
                 continue;
@@ -410,13 +411,23 @@ namespace mongo {
 
     Status MatchExpressionParser::_parseSub( const char* name,
                                              const BSONObj& sub,
-                                             AndMatchExpression* root ) {
+                                             AndMatchExpression* root,
+                                             int level ) {
         // The one exception to {field : {fully contained argument} } is, of course, geo.  Example:
         // sub == { field : {$near[Sphere]: [0,0], $maxDistance: 1000, $minDistance: 10 } }
         // We peek inside of 'sub' to see if it's possibly a $near.  If so, we can't iterate over
         // its subfields and parse them one at a time (there is no $maxDistance without $near), so
         // we hand the entire object over to the geo parsing routines.
 
+        if (level > kMaximumTreeDepth) {
+            mongoutils::str::stream ss;
+            ss << "exceeded maximum query tree depth of " << kMaximumTreeDepth
+               << " at " << sub.toString();
+            return Status( ErrorCodes::BadValue, ss );
+        }
+
+        level++;
+
         BSONObjIterator geoIt(sub);
         if (geoIt.more()) {
             BSONElement firstElt = geoIt.next();
@@ -447,7 +458,7 @@ namespace mongo {
         while ( j.more() ) {
             BSONElement deep = j.next();
 
-            StatusWithMatchExpression s = _parseSubField( sub, root, name, deep );
+            StatusWithMatchExpression s = _parseSubField( sub, root, name, deep, level );
             if ( !s.isOK() )
                 return s.getStatus();
 
@@ -636,7 +647,8 @@ namespace mongo {
     }
 
     StatusWithMatchExpression MatchExpressionParser::_parseElemMatch( const char* name,
-                                                            const BSONElement& e ) {
+                                                                      const BSONElement& e,
+                                                                      int level ) {
         if ( e.type() != Object )
             return StatusWithMatchExpression( ErrorCodes::BadValue, "$elemMatch needs an Object" );
 
@@ -666,7 +678,7 @@ namespace mongo {
             // value case
 
             AndMatchExpression theAnd;
-            Status s = _parseSub( "", obj, &theAnd );
+            Status s = _parseSub( "", obj, &theAnd, level );
             if ( !s.isOK() )
                 return StatusWithMatchExpression( s );
 
@@ -689,7 +701,7 @@ namespace mongo {
 
         // object case
 
-        StatusWithMatchExpression sub = _parse( obj, false );
+        StatusWithMatchExpression sub = _parse( obj, level );
         if ( !sub.isOK() )
             return sub;
 
@@ -709,7 +721,8 @@ namespace mongo {
     }
 
     StatusWithMatchExpression MatchExpressionParser::_parseAll( const char* name,
-                                                      const BSONElement& e ) {
+                                                                const BSONElement& e,
+                                                                int level ) {
         if ( e.type() != Array )
             return StatusWithMatchExpression( ErrorCodes::BadValue, "$all needs an array" );
 
@@ -742,7 +755,8 @@ namespace mongo {
                                                  "$all/$elemMatch has to be consistent" );
                 }
 
-                StatusWithMatchExpression inner = _parseElemMatch( "", hopefullyElemMatchObj.firstElement() );
+                StatusWithMatchExpression inner =
+                    _parseElemMatch( "", hopefullyElemMatchObj.firstElement(), level );
                 if ( !inner.isOK() )
                     return inner;
                 temp->add( static_cast<ArrayMatchingMatchExpression*>( inner.getValue() ) );
diff --git a/src/mongo/db/matcher/expression_parser.h b/src/mongo/db/matcher/expression_parser.h
index 6b714429920..b4c45e6cb81 100644
--- a/src/mongo/db/matcher/expression_parser.h
+++ b/src/mongo/db/matcher/expression_parser.h
@@ -92,7 +92,8 @@ namespace mongo {
          */
         static Status _parseSub( const char* name,
                                  const BSONObj& obj,
-                                 AndMatchExpression* root );
+                                 AndMatchExpression* root,
+                                 int level );
 
         /**
          * parses a single field in a sub expression
@@ -102,7 +103,8 @@ namespace mongo {
         static StatusWithMatchExpression _parseSubField( const BSONObj& context,
                                                          const AndMatchExpression* andSoFar,
                                                          const char* name,
-                                                         const BSONElement& e );
+                                                         const BSONElement& e,
+                                                         int level );
 
         static StatusWithMatchExpression _parseComparison( const char* name,
                                                            ComparisonMatchExpression* cmp,
@@ -124,16 +126,20 @@ namespace mongo {
         // arrays
 
         static StatusWithMatchExpression _parseElemMatch( const char* name,
-                                                     const BSONElement& e );
+                                                          const BSONElement& e,
+                                                          int level );
 
         static StatusWithMatchExpression _parseAll( const char* name,
-                                               const BSONElement& e );
+                                                    const BSONElement& e,
+                                                    int level );
 
         // tree
 
         static Status _parseTreeList( const BSONObj& arr, ListOfMatchExpression* out, int level );
 
-        static StatusWithMatchExpression _parseNot( const char* name, const BSONElement& e );
+        static StatusWithMatchExpression _parseNot( const char* name,
+                                                    const BSONElement& e,
+                                                    int level );
 
         // The maximum allowed depth of a query tree. Just to guard against stack overflow.
         static const int kMaximumTreeDepth;
diff --git a/src/mongo/db/matcher/expression_parser_tree.cpp b/src/mongo/db/matcher/expression_parser_tree.cpp
index aa36aff60b2..04a25dac779 100644
--- a/src/mongo/db/matcher/expression_parser_tree.cpp
+++ b/src/mongo/db/matcher/expression_parser_tree.cpp
@@ -70,7 +70,8 @@ namespace mongo {
     }
 
     StatusWithMatchExpression MatchExpressionParser::_parseNot( const char* name,
-                                                      const BSONElement& e ) {
+                                                                const BSONElement& e,
+                                                                int level ) {
         if ( e.type() == RegEx ) {
             StatusWithMatchExpression s = _parseRegexElement( name, e );
             if ( !s.isOK() )
@@ -90,7 +91,7 @@ namespace mongo {
             return StatusWithMatchExpression( ErrorCodes::BadValue, "$not cannot be empty" );
 
         std::auto_ptr<AndMatchExpression> theAnd( new AndMatchExpression() );
-        Status s = _parseSub( name, notObject, theAnd.get() );
+        Status s = _parseSub( name, notObject, theAnd.get(), level );
         if ( !s.isOK() )
             return StatusWithMatchExpression( s );
 
diff --git a/src/mongo/db/matcher/expression_parser_tree_test.cpp b/src/mongo/db/matcher/expression_parser_tree_test.cpp
index eec96a91049..aba286fb4c3 100644
--- a/src/mongo/db/matcher/expression_parser_tree_test.cpp
+++ b/src/mongo/db/matcher/expression_parser_tree_test.cpp
@@ -136,6 +136,43 @@ namespace mongo {
         ASSERT_FALSE( result.isOK() );
     }
 
+    // We should also exceed the depth limit through deeply nested $not.
+    TEST( MatchExpressionParserTreeTest, MaximumTreeDepthExceededNestedNots ) {
+        static const int depth = 105;
+
+        std::stringstream ss;
+        ss << "{a: ";
+        for (int i = 0; i < depth; i++) {
+            ss << "{$not: ";
+        }
+        ss << "{$eq: 5}";
+        for (int i = 0; i < depth+1; i++) {
+            ss << "}";
+        }
+
+        BSONObj query = fromjson( ss.str() );
+        StatusWithMatchExpression result = MatchExpressionParser::parse( query );
+        ASSERT_FALSE( result.isOK() );
+    }
+
+    // Depth limit with nested $elemMatch object.
+    TEST( MatchExpressionParserTreeTest, MaximumTreeDepthExceededNestedElemMatch ) {
+        static const int depth = 105;
+
+        std::stringstream ss;
+        for (int i = 0; i < depth; i++) {
+            ss << "{a: {$elemMatch: ";
+        }
+        ss << "{b: 5}";
+        for (int i = 0; i < depth; i++) {
+            ss << "}}";
+        }
+
+        BSONObj query = fromjson( ss.str() );
+        StatusWithMatchExpression result = MatchExpressionParser::parse( query );
+        ASSERT_FALSE( result.isOK() );
+    }
+
     TEST( MatchExpressionParserLeafTest, NotRegex1 ) {
         BSONObjBuilder b;
         b.appendRegex( "$not", "abc", "i" );