SERVER-9820: Introduce Path and iterators such that all bson walking logic is one place

16 files changed, 824 insertions, 304 deletions

diff --git a/src/mongo/SConscript b/src/mongo/SConscript
index 2abb1018dcc..a7488efb45a 100644
--- a/src/mongo/SConscript
+++ b/src/mongo/SConscript
@@ -113,12 +113,19 @@ env.CppUnitTest('namespacestring_test', ['db/namespacestring_test.cpp'],
 env.CppUnitTest('index_set_test', ['db/index_set_test.cpp'],
                 LIBDEPS=['bson','index_set'])
 
+env.StaticLibrary('path',
+                  ['db/matcher/path.cpp',
+                   'db/matcher/path_internal.cpp'],
+                  LIBDEPS=['bson',
+                           '$BUILD_DIR/mongo/db/common'])
+
+env.CppUnitTest('path_test', ['db/matcher/path_test.cpp'],
+                LIBDEPS=['path'])
 
 
 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',
@@ -126,6 +133,7 @@ env.StaticLibrary('expressions',
                    'db/matcher/matchable.cpp',
                    'db/matcher/match_details.cpp'],
                   LIBDEPS=['bson',
+                           'path',
                            '$BUILD_DIR/mongo/db/common',
                            '$BUILD_DIR/third_party/pcrecpp'
                            ] )
@@ -139,7 +147,6 @@ env.StaticLibrary('expressions_where',
                   ['db/matcher/expression_where.cpp'],
                   LIBDEPS=['expressions'] )
 
-
 env.CppUnitTest('expression_test',
                 ['db/matcher/expression_test.cpp',
                  'db/matcher/expression_leaf_test.cpp',
diff --git a/src/mongo/db/matcher/expression_array.cpp b/src/mongo/db/matcher/expression_array.cpp
index 40c967413f5..b2330e82355 100644
--- a/src/mongo/db/matcher/expression_array.cpp
+++ b/src/mongo/db/matcher/expression_array.cpp
@@ -18,63 +18,38 @@
 
 #include "mongo/db/matcher/expression_array.h"
 
-#include "mongo/bson/bsonobjiterator.h"
 #include "mongo/db/field_ref.h"
-#include "mongo/db/matcher/expression_internal.h"
+#include "mongo/db/jsobj.h"
 #include "mongo/util/log.h"
 
 namespace mongo {
 
-    bool ArrayMatchingMatchExpression::matches( const MatchableDocument* doc, MatchDetails* details ) const {
-
-        FieldRef path;
-        path.parse(_path);
-
-        bool traversedArray = false;
-        size_t idxPath = 0;
-        BSONElement e = doc->getFieldDottedOrArray( path, &idxPath, &traversedArray );
-
-        string rest = path.dottedField( idxPath+1 );
-        bool restIsNumber = isAllDigits( rest );
+    Status ArrayMatchingMatchExpression::initPath( const StringData& path ) {
+        _path = path;
+        Status s = _elementPath.init( _path );
+        _elementPath.setTraverseLeafArray( false );
+        return s;
+    }
 
-        if ( rest.size() == 0 ) {
-            if ( e.type() == Array )
-                return matchesArray( e.Obj(), details );
-            return false;
-        }
+    bool ArrayMatchingMatchExpression::matches( const MatchableDocument* doc, MatchDetails* details ) const {
 
-        if ( e.type() != Array )
-            return false;
+        boost::scoped_ptr<ElementIterator> cursor( doc->getIterator( _elementPath ) );
 
-        BSONObjIterator i( e.Obj() );
-        while ( i.more() ) {
-            BSONElement x = i.next();
-            if ( ! x.isABSONObj() )
+        while ( cursor->more() ) {
+            ElementIterator::Element e = cursor->next();
+            if ( e.element().type() != Array )
                 continue;
 
-            if ( restIsNumber && rest == x.fieldName() ) {
-                if ( matchesArray( x.Obj(), NULL ) ) {
-                    if ( details && details->needRecord() ) {
-                        // trying to match crazy semantics??
-                        details->setElemMatchKey( x.fieldName() );
-                    }
-                    return true;
-                }
-            }
+            bool amIRoot = e.arrayOffset().eoo();
 
-            BSONElement sub = x.Obj().getFieldDotted( rest );
-            if ( sub.type() != Array )
+            if ( !matchesArray( e.element().Obj(), amIRoot ? details : NULL ) )
                 continue;
 
-            if ( matchesArray( sub.Obj(), NULL ) ) {
-                if ( details && details->needRecord() ) {
-                    // trying to match crazy semantics??
-                    details->setElemMatchKey( x.fieldName() );
-                }
-                return true;
+            if ( !amIRoot && details && details->needRecord() && !e.arrayOffset().eoo() ) {
+                details->setElemMatchKey( e.arrayOffset().fieldName() );
             }
+            return true;
         }
-
         return false;
     }
 
@@ -108,13 +83,10 @@ namespace mongo {
     // -------
 
     Status ElemMatchObjectMatchExpression::init( const StringData& path, const MatchExpression* sub ) {
-        _path = path;
         _sub.reset( sub );
-        return Status::OK();
+        return initPath( path );
     }
 
-
-
     bool ElemMatchObjectMatchExpression::matchesArray( const BSONObj& anArray, MatchDetails* details ) const {
         BSONObjIterator i( anArray );
         while ( i.more() ) {
@@ -133,7 +105,7 @@ namespace mongo {
 
     void ElemMatchObjectMatchExpression::debugString( StringBuilder& debug, int level ) const {
         _debugAddSpace( debug, level );
-        debug << _path << " $elemMatch\n";
+        debug << path() << " $elemMatch\n";
         _sub->debugString( debug, level + 1 );
     }
 
@@ -153,8 +125,7 @@ namespace mongo {
     }
 
     Status ElemMatchValueMatchExpression::init( const StringData& path ) {
-        _path = path;
-        return Status::OK();
+        return initPath( path );
     }
 
 
@@ -188,7 +159,7 @@ namespace mongo {
 
     void ElemMatchValueMatchExpression::debugString( StringBuilder& debug, int level ) const {
         _debugAddSpace( debug, level );
-        debug << _path << " $elemMatch\n";
+        debug << path() << " $elemMatch\n";
         for ( unsigned i = 0; i < _subs.size(); i++ ) {
             _subs[i]->debugString( debug, level + 1 );
         }
@@ -205,7 +176,9 @@ namespace mongo {
 
     Status AllElemMatchOp::init( const StringData& path ) {
         _path = path;
-        return Status::OK();
+        Status s = _elementPath.init( _path );
+        _elementPath.setTraverseLeafArray( false );
+        return s;
     }
 
     void AllElemMatchOp::add( const ArrayMatchingMatchExpression* expr ) {
@@ -214,16 +187,13 @@ namespace mongo {
     }
 
     bool AllElemMatchOp::matches( const MatchableDocument* 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 )
+        boost::scoped_ptr<ElementIterator> cursor( doc->getIterator( _elementPath ) );
+        while ( cursor->more() ) {
+            ElementIterator::Element e = cursor->next();
+            if ( e.element().type() != Array )
                 continue;
-            if ( _allMatch( sub.Obj() ) ) {
+            if ( _allMatch( e.element().Obj() ) )
                 return true;
-            }
         }
         return false;
     }
@@ -276,9 +246,8 @@ namespace mongo {
     // ---------
 
     Status SizeMatchExpression::init( const StringData& path, int size ) {
-        _path = path;
         _size = size;
-        return Status::OK();
+        return initPath( path );
     }
 
     bool SizeMatchExpression::matchesArray( const BSONObj& anArray, MatchDetails* details ) const {
@@ -289,7 +258,7 @@ namespace mongo {
 
     void SizeMatchExpression::debugString( StringBuilder& debug, int level ) const {
         _debugAddSpace( debug, level );
-        debug << _path << " $size : " << _size << "\n";
+        debug << path() << " $size : " << _size << "\n";
     }
 
     bool SizeMatchExpression::equivalent( const MatchExpression* other ) const {
@@ -297,7 +266,7 @@ namespace mongo {
             return false;
 
         const SizeMatchExpression* realOther = static_cast<const SizeMatchExpression*>( other );
-        return _path == realOther->_path && _size == realOther->_size;
+        return path() == realOther->path() && _size == realOther->_size;
     }
 
 
diff --git a/src/mongo/db/matcher/expression_array.h b/src/mongo/db/matcher/expression_array.h
index d573781aeaa..d141020a9e5 100644
--- a/src/mongo/db/matcher/expression_array.h
+++ b/src/mongo/db/matcher/expression_array.h
@@ -33,6 +33,8 @@ namespace mongo {
         ArrayMatchingMatchExpression( MatchType matchType ) : MatchExpression( matchType ){}
         virtual ~ArrayMatchingMatchExpression(){}
 
+        Status initPath( const StringData& path );
+
         virtual bool matches( const MatchableDocument* doc, MatchDetails* details ) const;
 
         /**
@@ -44,8 +46,10 @@ namespace mongo {
 
         bool equivalent( const MatchExpression* other ) const;
 
-    protected:
+        const StringData& path() const { return _path; }
+    private:
         StringData _path;
+        ElementPath _elementPath;
     };
 
 
@@ -114,6 +118,7 @@ namespace mongo {
         bool _allMatch( const BSONObj& anArray ) const;
 
         StringData _path;
+        ElementPath _elementPath;
         std::vector< const ArrayMatchingMatchExpression* > _list;
     };
 
diff --git a/src/mongo/db/matcher/expression_geo.cpp b/src/mongo/db/matcher/expression_geo.cpp
index 85fcc6e570a..1cb3239cc87 100644
--- a/src/mongo/db/matcher/expression_geo.cpp
+++ b/src/mongo/db/matcher/expression_geo.cpp
@@ -22,9 +22,8 @@
 namespace mongo {
 
     Status GeoMatchExpression::init( const StringData& path, const GeoQuery& query ) {
-        initPath( path );
         _query = query;
-        return Status::OK();
+        return initPath( path );
     }
 
     bool GeoMatchExpression::matchesSingleElement( const BSONElement& e ) const {
diff --git a/src/mongo/db/matcher/expression_leaf.cpp b/src/mongo/db/matcher/expression_leaf.cpp
index db3c819cbbe..4c62026d8c8 100644
--- a/src/mongo/db/matcher/expression_leaf.cpp
+++ b/src/mongo/db/matcher/expression_leaf.cpp
@@ -22,106 +22,30 @@
 #include "mongo/bson/bsonobj.h"
 #include "mongo/bson/bsonmisc.h"
 #include "mongo/db/field_ref.h"
-#include "mongo/db/matcher/expression_internal.h"
+#include "mongo/db/jsobj.h"
+#include "mongo/db/matcher/path.h"
 #include "mongo/util/log.h"
 
 namespace mongo {
 
-    void LeafMatchExpression::initPath( const StringData& path ) {
+    Status LeafMatchExpression::initPath( const StringData& path ) {
         _path = path;
-        _fieldRef.parse( _path );
+        return _elementPath.init( _path );
     }
 
-    bool LeafMatchExpression::_matchesElementExpandArray( const BSONElement& e ) const {
-        if ( e.eoo() )
-            return false;
-
-        if ( matchesSingleElement( e ) )
-            return true;
-
-        if ( e.type() == Array ) {
-            BSONObjIterator i( e.Obj() );
-            while ( i.more() ){
-                BSONElement sub = i.next();
-                if ( matchesSingleElement( sub ) )
-                    return true;
-            }
-        }
-
-        return false;
-    }
 
     bool LeafMatchExpression::matches( const MatchableDocument* doc, MatchDetails* details ) const {
-        return _matches( _fieldRef, doc, details );
-    }
-
-    bool LeafMatchExpression::_matches( const FieldRef& fieldRef,
-                                        const MatchableDocument* doc,
-                                        MatchDetails* details ) const {
-
-        bool traversedArray = false;
-        size_t idxPath = 0;
-        BSONElement e = doc->getFieldDottedOrArray( fieldRef, &idxPath, &traversedArray );
-
-        if ( e.type() != Array || traversedArray ) {
-            return matchesSingleElement( e );
-        }
-
-        string rest = fieldRef.dottedField( idxPath + 1 );
-        StringData next;
-        bool nextIsNumber = false;
-        if ( rest.size() > 0 ){
-            next = fieldRef.getPart( idxPath + 1 );
-            nextIsNumber = isAllDigits( next );
-        }
-
-        BSONObjIterator i( e.Obj() );
-        while ( i.more() ) {
-            BSONElement x = i.next();
-
-            bool found = false;
-            if ( rest.size() == 0 ) {
-                found = matchesSingleElement( x );
-            }
-            else if ( x.type() == Object ) {
-                FieldRef myFieldRef;
-                myFieldRef.parse( rest );
-                BSONMatchableDocument myDoc( x.Obj() );
-                found = _matches( myFieldRef, &myDoc, NULL );
-            }
-
-
-            if ( !found && nextIsNumber && next == x.fieldName() ) {
-                string reallyNext = fieldRef.dottedField( idxPath + 2 );
-                if ( reallyNext.size() == 0 ) {
-                    found = matchesSingleElement( x );
-                }
-                else if ( x.isABSONObj() ) {
-                    // TODO: this is slow
-                    FieldRef myFieldRef;
-                    myFieldRef.parse( "x." + reallyNext );
-                    BSONObjBuilder b;
-                    b.appendAs( x, "x" );
-                    BSONObj temp = b.obj();
-                    BSONMatchableDocument myDoc( temp );
-                    found = _matches( myFieldRef, &myDoc, NULL );
-                }
-            }
-
-            if ( found ) {
-                if ( details && details->needRecord() ) {
-                    details->setElemMatchKey( x.fieldName() );
-                }
-                return true;
+        boost::scoped_ptr<ElementIterator> cursor( doc->getIterator( _elementPath ) );
+        while ( cursor->more() ) {
+            ElementIterator::Element e = cursor->next();
+            if ( !matchesSingleElement( e.element() ) )
+                continue;
+            if ( details && details->needRecord() && !e.arrayOffset().eoo() ) {
+                details->setElemMatchKey( e.arrayOffset().fieldName() );
             }
+            return true;
         }
-
-        if ( rest.size() > 0 ) {
-            // we're supposed to have gone further down
-            return false;
-        }
-
-        return matchesSingleElement( e );
+        return false;
     }
 
     // -------------
@@ -139,7 +63,6 @@ namespace mongo {
 
 
     Status ComparisonMatchExpression::init( const StringData& path, const BSONElement& rhs ) {
-        initPath( path );
         _rhs = rhs;
 
         if ( rhs.eoo() ) {
@@ -161,7 +84,7 @@ namespace mongo {
             return Status( ErrorCodes::BadValue, "bad match type for ComparisonMatchExpression" );
         }
 
-        return Status::OK();
+        return initPath( path );
     }
 
 
@@ -263,8 +186,6 @@ namespace mongo {
 
 
     Status RegexMatchExpression::init( const StringData& path, const StringData& regex, const StringData& options ) {
-        initPath( path );
-
         if ( regex.size() > MaxPatternSize ) {
             return Status( ErrorCodes::BadValue, "Regular expression is too long" );
         }
@@ -272,7 +193,8 @@ namespace mongo {
         _regex = regex.toString();
         _flags = options.toString();
         _re.reset( new pcrecpp::RE( _regex.c_str(), flags2options( _flags.c_str() ) ) );
-        return Status::OK();
+
+        return initPath( path );
     }
 
     bool RegexMatchExpression::matchesSingleElement( const BSONElement& e ) const {
@@ -300,12 +222,11 @@ namespace mongo {
     // ---------
 
     Status ModMatchExpression::init( const StringData& path, int divisor, int remainder ) {
-        initPath( path );
         if ( divisor == 0 )
             return Status( ErrorCodes::BadValue, "divisor cannot be 0" );
         _divisor = divisor;
         _remainder = remainder;
-        return Status::OK();
+        return initPath( path );
     }
 
     bool ModMatchExpression::matchesSingleElement( const BSONElement& e ) const {
@@ -334,8 +255,7 @@ namespace mongo {
     // ------------------
 
     Status ExistsMatchExpression::init( const StringData& path ) {
-        initPath( path );
-        return Status::OK();
+        return initPath( path );
     }
 
     bool ExistsMatchExpression::matchesSingleElement( const BSONElement& e ) const {
@@ -361,7 +281,7 @@ namespace mongo {
     Status TypeMatchExpression::init( const StringData& path, int type ) {
         _path = path;
         _type = type;
-        return Status::OK();
+        return _elementPath.init( _path );
     }
 
     bool TypeMatchExpression::matchesSingleElement( const BSONElement& e ) const {
@@ -369,46 +289,19 @@ namespace mongo {
     }
 
     bool TypeMatchExpression::matches( const MatchableDocument* doc, MatchDetails* details ) const {
-        return _matches( _path, doc, details );
-    }
-
-    bool TypeMatchExpression::_matches( const StringData& path,
-                                        const MatchableDocument* doc,
-                                        MatchDetails* details ) const {
-
-        FieldRef fieldRef;
-        fieldRef.parse( path );
-
-        bool traversedArray = false;
-        size_t idxPath = 0;
-        BSONElement e = doc->getFieldDottedOrArray( fieldRef, &idxPath, &traversedArray );
-
-        string rest = fieldRef.dottedField( 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() ) {
-                BSONMatchableDocument doc( x.Obj() );
-                found = _matches( rest, &doc, details );
-            }
-
-            if ( found ) {
-                if ( details && details->needRecord() ) {
-                    details->setElemMatchKey( x.fieldName() );
-                }
-                return true;
+        boost::scoped_ptr<ElementIterator> cursor( doc->getIterator( _elementPath ) );
+        while ( cursor->more() ) {
+            ElementIterator::Element e = cursor->next();
+            if ( e.outerArray() )
+                continue;
+
+            if ( !matchesSingleElement( e.element() ) )
+                continue;
+            if ( details && details->needRecord() && !e.arrayOffset().eoo() ) {
+                details->setElemMatchKey( e.arrayOffset().fieldName() );
             }
+            return true;
         }
-
         return false;
     }
 
@@ -489,8 +382,8 @@ namespace mongo {
 
     // -----------
 
-    void InMatchExpression::init( const StringData& path ) {
-        initPath( path );
+    Status InMatchExpression::init( const StringData& path ) {
+        return initPath( path );
     }
 
     bool InMatchExpression::_matchesRealElement( const BSONElement& e ) const {
diff --git a/src/mongo/db/matcher/expression_leaf.h b/src/mongo/db/matcher/expression_leaf.h
index 1f4501bedc7..681040e0307 100644
--- a/src/mongo/db/matcher/expression_leaf.h
+++ b/src/mongo/db/matcher/expression_leaf.h
@@ -45,20 +45,11 @@ namespace mongo {
         const StringData path() const { return _path; }
 
     protected:
-        void initPath( const StringData& path );
+        Status initPath( const StringData& path );
 
     private:
-        bool _matches( const FieldRef& fieldRef,
-                       const MatchableDocument* doc,
-                       MatchDetails* details ) const;
-
-
-
-
-        bool _matchesElementExpandArray( const BSONElement& e ) const;
-
         StringData _path;
-        FieldRef _fieldRef;
+        ElementPath _elementPath;
     };
 
     // -----
@@ -230,6 +221,7 @@ namespace mongo {
                        MatchDetails* details = 0 ) const;
 
         StringData _path;
+        ElementPath _elementPath;
         int _type;
     };
 
@@ -275,7 +267,7 @@ namespace mongo {
     class InMatchExpression : public LeafMatchExpression {
     public:
         InMatchExpression() : LeafMatchExpression( MATCH_IN ){}
-        void init( const StringData& path );
+        Status init( const StringData& path );
 
         virtual LeafMatchExpression* shallowClone() const;
 
diff --git a/src/mongo/db/matcher/expression_leaf_test.cpp b/src/mongo/db/matcher/expression_leaf_test.cpp
index e2e8ca27e7b..3c90c4ec1bf 100644
--- a/src/mongo/db/matcher/expression_leaf_test.cpp
+++ b/src/mongo/db/matcher/expression_leaf_test.cpp
@@ -116,6 +116,14 @@ namespace mongo {
         ASSERT( !eq.matchesBSON( BSON( "a" << 1 ), NULL ) );
     }
 
+    TEST( EqOp, MatchesThroughNestedArray ) {
+        BSONObj operand = BSON( "a.b.c.d" << 3 );
+        EqualityMatchExpression eq;
+        eq.init( "a.b.c.d", operand["a.b.c.d"] );
+        BSONObj obj = fromjson("{a:{b:[{c:[{d:1},{d:2}]},{c:[{d:3}]}]}}");
+        ASSERT( eq.matchesBSON( obj, NULL ) );
+    }
+
     TEST( EqOp, ElemMatchKey ) {
         BSONObj operand = BSON( "a" << 5 );
         EqualityMatchExpression eq;
diff --git a/src/mongo/db/matcher/expression_parser.cpp b/src/mongo/db/matcher/expression_parser.cpp
index f8abbca6c03..60501729c16 100644
--- a/src/mongo/db/matcher/expression_parser.cpp
+++ b/src/mongo/db/matcher/expression_parser.cpp
@@ -92,8 +92,10 @@ namespace mongo {
             if ( e.type() != Array )
                 return StatusWithMatchExpression( ErrorCodes::BadValue, "$in needs an array" );
             std::auto_ptr<InMatchExpression> temp( new InMatchExpression() );
-            temp->init( name );
-            Status s = _parseArrayFilterEntries( temp->getArrayFilterEntries(), e.Obj() );
+            Status s = temp->init( name );
+            if ( !s.isOK() )
+                return StatusWithMatchExpression( s );
+            s = _parseArrayFilterEntries( temp->getArrayFilterEntries(), e.Obj() );
             if ( !s.isOK() )
                 return StatusWithMatchExpression( s );
             return StatusWithMatchExpression( temp.release() );
@@ -103,8 +105,10 @@ namespace mongo {
             if ( e.type() != Array )
                 return StatusWithMatchExpression( ErrorCodes::BadValue, "$nin needs an array" );
             std::auto_ptr<InMatchExpression> temp( new InMatchExpression() );
-            temp->init( name );
-            Status s = _parseArrayFilterEntries( temp->getArrayFilterEntries(), e.Obj() );
+            Status s = temp->init( name );
+            if ( !s.isOK() )
+                return StatusWithMatchExpression( s );
+            s = _parseArrayFilterEntries( temp->getArrayFilterEntries(), e.Obj() );
             if ( !s.isOK() )
                 return StatusWithMatchExpression( s );
 
diff --git a/src/mongo/db/matcher/matchable.cpp b/src/mongo/db/matcher/matchable.cpp
index 3dac11ce43a..b471e43543a 100644
--- a/src/mongo/db/matcher/matchable.cpp
+++ b/src/mongo/db/matcher/matchable.cpp
@@ -18,7 +18,6 @@
 
 #include "mongo/pch.h"
 #include "mongo/db/jsobj.h"
-#include "mongo/db/matcher/expression_internal.h"
 #include "mongo/db/matcher/matchable.h"
 
 namespace mongo {
@@ -33,17 +32,4 @@ namespace mongo {
     BSONMatchableDocument::~BSONMatchableDocument() {
     }
 
-
-    BSONElement BSONMatchableDocument::getFieldDottedOrArray( const FieldRef& path,
-                                                              size_t* idxPath,
-                                                              bool* inArray ) const {
-        return mongo::getFieldDottedOrArray( _obj, path, idxPath, inArray );
-    }
-
-    void BSONMatchableDocument::getFieldsDotted( const StringData& name,
-                                                 BSONElementSet &ret,
-                                                 bool expandLastArray ) const {
-        return _obj.getFieldsDotted( name, ret, expandLastArray );
-    }
-
 }
diff --git a/src/mongo/db/matcher/matchable.h b/src/mongo/db/matcher/matchable.h
index 4b93331899e..c980bc2749e 100644
--- a/src/mongo/db/matcher/matchable.h
+++ b/src/mongo/db/matcher/matchable.h
@@ -20,6 +20,7 @@
 
 #include "mongo/bson/bsonobj.h"
 #include "mongo/db/field_ref.h"
+#include "mongo/db/matcher/path.h"
 
 namespace mongo {
 
@@ -29,13 +30,7 @@ namespace mongo {
 
         virtual BSONObj toBSON() const = 0;
 
-        virtual BSONElement getFieldDottedOrArray( const FieldRef& path,
-                                                   size_t* idxPath,
-                                                   bool* inArray ) const = 0;
-
-        virtual void getFieldsDotted( const StringData& name,
-                                      BSONElementSet &ret,
-                                      bool expandLastArray = true ) const = 0;
+        virtual ElementIterator* getIterator( const ElementPath& path ) const = 0;
 
     };
 
@@ -46,13 +41,9 @@ namespace mongo {
 
         virtual BSONObj toBSON() const { return _obj; }
 
-        virtual BSONElement getFieldDottedOrArray( const FieldRef& path,
-                                                   size_t* idxPath,
-                                                   bool* inArray ) const;
-
-        virtual void getFieldsDotted( const StringData& name,
-                                      BSONElementSet &ret,
-                                      bool expandLastArray = true ) const;
+        virtual ElementIterator* getIterator( const ElementPath& path ) const {
+            return new BSONElementIterator( path, _obj );
+        }
 
     private:
         BSONObj _obj;
diff --git a/src/mongo/db/matcher/matcher.cpp b/src/mongo/db/matcher/matcher.cpp
index cfd482d3b33..f0b13ce0624 100644
--- a/src/mongo/db/matcher/matcher.cpp
+++ b/src/mongo/db/matcher/matcher.cpp
@@ -40,13 +40,7 @@ namespace mongo {
             return _doc.replaceFieldNames( _pattern );
         }
 
-        virtual BSONElement getFieldDottedOrArray( const FieldRef& path,
-                                                   size_t* idxPath,
-                                                   bool* inArray ) const;
-
-        virtual void getFieldsDotted( const StringData& name,
-                                      BSONElementSet &ret,
-                                      bool expandLastArray = true ) const;
+        virtual ElementIterator* getIterator( const ElementPath& path ) const;
 
     private:
 
@@ -57,6 +51,14 @@ namespace mongo {
 
     };
 
+    ElementIterator* IndexKeyMatchableDocument::getIterator( const ElementPath& path ) const {
+        BSONElement e = _getElement( path.fieldRef() );
+        if ( e.type() == Array )
+            return new SimpleArrayElementIterator( e, true );
+        return new SingleElementElementIterator( e );
+    }
+
+
     BSONElement IndexKeyMatchableDocument::_getElement( const FieldRef& path ) const {
         BSONObjIterator patternIterator( _pattern );
         BSONObjIterator docIterator( _doc );
@@ -75,37 +77,6 @@ namespace mongo {
     }
 
 
-    BSONElement IndexKeyMatchableDocument::getFieldDottedOrArray( const FieldRef& path,
-                                                                  size_t* idxPath,
-                                                                  bool* inArray ) const {
-        BSONElement res = _getElement( path );
-        if ( !res.eoo() ) {
-            *idxPath = path.numParts() - 1;
-            *inArray = false;
-        }
-
-        return res;
-    }
-
-    void IndexKeyMatchableDocument::getFieldsDotted( const StringData& name,
-                                                     BSONElementSet &ret,
-                                                     bool expandLastArray ) const {
-        BSONObjIterator patternIterator( _pattern );
-        BSONObjIterator docIterator( _doc );
-
-        while ( patternIterator.more() ) {
-            BSONElement patternElement = patternIterator.next();
-            verify( docIterator.more() );
-            BSONElement docElement = docIterator.next();
-
-            if ( name == patternElement.fieldName() ) {
-                ret.insert( docElement );
-            }
-        }
-
-    }
-
-
     // -----------------
 
     Matcher2::Matcher2( const BSONObj& pattern, bool nested )
diff --git a/src/mongo/db/matcher/path.cpp b/src/mongo/db/matcher/path.cpp
new file mode 100644
index 00000000000..320ea31ad79
--- /dev/null
+++ b/src/mongo/db/matcher/path.cpp
@@ -0,0 +1,245 @@
+// path.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/pch.h"
+#include "mongo/db/jsobj.h"
+#include "mongo/db/matcher/path_internal.h"
+#include "mongo/db/matcher/path.h"
+
+namespace mongo {
+
+    Status ElementPath::init( const StringData& path ) {
+        _shouldTraverseLeafArray = true;
+        _fieldRef.parse( path );
+        return Status::OK();
+    }
+
+    // -----
+
+    ElementIterator::~ElementIterator(){
+    }
+
+    void ElementIterator::Element::reset() {
+        _element = BSONElement();
+    }
+
+    void ElementIterator::Element::reset( BSONElement element,
+                                          BSONElement arrayOffset,
+                                          bool outerArray ) {
+        _element = element;
+        _arrayOffset = arrayOffset;
+        _outerArray = outerArray;
+    }
+
+
+    // ------
+
+    SimpleArrayElementIterator::SimpleArrayElementIterator( const BSONElement& theArray, bool returnArrayLast )
+        : _theArray( theArray ), _returnArrayLast( returnArrayLast ), _iterator( theArray.Obj() ) {
+
+    }
+
+    bool SimpleArrayElementIterator::more() {
+        return _iterator.more() || _returnArrayLast;
+    }
+
+    ElementIterator::Element SimpleArrayElementIterator::next() {
+        if ( _iterator.more() ) {
+            Element e;
+            e.reset( _iterator.next(), BSONElement(), false );
+            return e;
+        }
+        _returnArrayLast = false;
+        Element e;
+        e.reset( _theArray, BSONElement(), true );
+        return e;
+    }
+
+
+
+    // ------
+
+    BSONElementIterator::BSONElementIterator( const ElementPath& path, const BSONObj& context )
+        : _path( path ), _context( context ) {
+        _state = BEGIN;
+        //log() << "path: " << path.fieldRef().dottedField() << " context: " << context << endl;
+    }
+
+    BSONElementIterator::~BSONElementIterator() {
+    }
+
+    void BSONElementIterator::ArrayIterationState::reset( const FieldRef& ref, int start ) {
+        restOfPath = ref.dottedField( start );
+        hasMore = restOfPath.size() > 0;
+        if ( hasMore ) {
+            nextPieceOfPath = ref.getPart( start );
+            nextPieceOfPathIsNumber = isAllDigits( nextPieceOfPath );
+        }
+        else {
+            nextPieceOfPathIsNumber = false;
+        }
+    }
+
+    bool BSONElementIterator::ArrayIterationState::isArrayOffsetMatch( const StringData& fieldName ) const {
+        if ( !nextPieceOfPathIsNumber )
+            return false;
+        return nextPieceOfPath == fieldName;
+    }
+
+
+    void BSONElementIterator::ArrayIterationState::startIterator( BSONElement e ) {
+        _theArray = e;
+        _iterator.reset( new BSONObjIterator( _theArray.Obj() ) );
+    }
+
+    bool BSONElementIterator::ArrayIterationState::more() {
+        return _iterator && _iterator->more();
+    }
+
+    BSONElement BSONElementIterator::ArrayIterationState::next() {
+        _current = _iterator->next();
+        return _current;
+    }
+
+
+    bool BSONElementIterator::more() {
+        if ( _subCursor ) {
+
+            if ( _subCursor->more() )
+                return true;
+
+            _subCursor.reset();
+
+            if ( _arrayIterationState.isArrayOffsetMatch( _arrayIterationState._current.fieldName() ) ) {
+                if ( _arrayIterationState.nextEntireRest() ) {
+                    _next.reset( _arrayIterationState._current, _arrayIterationState._current, true );
+                    _arrayIterationState._current = BSONElement();
+                    return true;
+                }
+
+                _subCursorPath.reset( new ElementPath() );
+                _subCursorPath->init( _arrayIterationState.restOfPath.substr( _arrayIterationState.nextPieceOfPath.size() + 1 ) );
+                _subCursorPath->setTraverseLeafArray( _path.shouldTraverseLeafArray() );
+                _subCursor.reset( new BSONElementIterator( *_subCursorPath, _arrayIterationState._current.Obj() ) );
+                _arrayIterationState._current = BSONElement();
+                return more();
+            }
+
+        }
+
+        if ( !_next.element().eoo() )
+            return true;
+
+        if ( _state == DONE ){
+            return false;
+        }
+
+        if ( _state == BEGIN ) {
+            size_t idxPath = 0;
+            BSONElement e = getFieldDottedOrArray( _context, _path.fieldRef(), &idxPath );
+
+            if ( e.type() != Array ) {
+                _next.reset( e, BSONElement(), false );
+                _state = DONE;
+                return true;
+            }
+
+            // its an array
+
+            _arrayIterationState.reset( _path.fieldRef(), idxPath + 1 );
+
+            if ( !_arrayIterationState.hasMore && !_path.shouldTraverseLeafArray() ) {
+                _next.reset( e, BSONElement(), true );
+                _state = DONE;
+                return true;
+            }
+
+            _arrayIterationState.startIterator( e );
+            _state = IN_ARRAY;
+            return more();
+        }
+
+        if ( _state == IN_ARRAY ) {
+
+            while ( _arrayIterationState.more() ) {
+
+                BSONElement x = _arrayIterationState.next();
+                if ( !_arrayIterationState.hasMore ) {
+                    _next.reset( x, x, false );
+                    return true;
+                }
+
+                // i have deeper to go
+
+                if ( x.type() == Object ) {
+                    _subCursorPath.reset( new ElementPath() );
+                    _subCursorPath->init( _arrayIterationState.restOfPath );
+                    _subCursorPath->setTraverseLeafArray( _path.shouldTraverseLeafArray() );
+
+                    _subCursor.reset( new BSONElementIterator( *_subCursorPath, x.Obj() ) );
+                    return more();
+                }
+
+
+                if ( _arrayIterationState.isArrayOffsetMatch( x.fieldName() ) ) {
+
+                    if ( _arrayIterationState.nextEntireRest() ) {
+                        _next.reset( x, x, false );
+                        return true;
+                    }
+
+                    if ( x.isABSONObj() ) {
+                        _subCursorPath.reset( new ElementPath() );
+                        _subCursorPath->init( _arrayIterationState.restOfPath.substr( _arrayIterationState.nextPieceOfPath.size() + 1 ) );
+                        _subCursorPath->setTraverseLeafArray( _path.shouldTraverseLeafArray() );
+                        BSONElementIterator* real = new BSONElementIterator( *_subCursorPath, _arrayIterationState._current.Obj() );
+                        _subCursor.reset( real );
+                        real->_arrayIterationState.reset( _subCursorPath->fieldRef(), 0 );
+                        real->_arrayIterationState.startIterator( x );
+                        real->_state = IN_ARRAY;
+                        _arrayIterationState._current = BSONElement();
+                        return more();
+                    }
+                }
+
+            }
+
+            if ( _arrayIterationState.hasMore )
+                return false;
+
+            _next.reset( _arrayIterationState._theArray, BSONElement(), true );
+            _state = DONE;
+            return true;
+        }
+
+        return false;
+    }
+
+    ElementIterator::Element BSONElementIterator::next() {
+        if ( _subCursor ) {
+            Element e = _subCursor->next();
+            e.setArrayOffset( _arrayIterationState._current );
+            return e;
+        }
+        Element x = _next;
+        _next.reset();
+        return x;
+    }
+
+
+}
diff --git a/src/mongo/db/matcher/path.h b/src/mongo/db/matcher/path.h
new file mode 100644
index 00000000000..08f4caed258
--- /dev/null
+++ b/src/mongo/db/matcher/path.h
@@ -0,0 +1,146 @@
+// path.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 <boost/scoped_ptr.hpp>
+
+#include "mongo/base/status.h"
+#include "mongo/base/string_data.h"
+#include "mongo/bson/bsonobj.h"
+#include "mongo/bson/bsonobjiterator.h"
+#include "mongo/db/field_ref.h"
+
+namespace mongo {
+
+    class ElementPath {
+    public:
+        Status init( const StringData& path );
+
+        void setTraverseLeafArray( bool b ) { _shouldTraverseLeafArray = b; }
+
+        const FieldRef& fieldRef() const { return _fieldRef; }
+        bool shouldTraverseLeafArray() const { return _shouldTraverseLeafArray; }
+
+    private:
+        FieldRef _fieldRef;
+        bool _shouldTraverseLeafArray;
+    };
+
+    class ElementIterator {
+    public:
+        class Element {
+        public:
+
+            void reset();
+
+            void reset( BSONElement element, BSONElement arrayOffset, bool outerArray );
+
+            void setArrayOffset( BSONElement e ) { _arrayOffset = e; }
+
+            BSONElement element() const { return _element; }
+            BSONElement arrayOffset() const { return _arrayOffset; }
+            bool outerArray() const { return _outerArray; }
+
+        private:
+            BSONElement _element;
+            BSONElement _arrayOffset;
+            bool _outerArray;
+        };
+
+        virtual ~ElementIterator();
+
+        virtual bool more() = 0;
+        virtual Element next() = 0;
+
+    };
+
+    // ---------------------------------------------------------------
+
+    class SingleElementElementIterator : public ElementIterator {
+    public:
+        explicit SingleElementElementIterator( BSONElement e )
+            : _seen( false ) {
+            _element.reset( e, BSONElement(), false );
+        }
+        virtual ~SingleElementElementIterator(){}
+
+        virtual bool more() { return !_seen; }
+        virtual Element next() { _seen = true; return _element; }
+
+    private:
+        bool _seen;
+        ElementIterator::Element _element;
+    };
+
+    class SimpleArrayElementIterator : public ElementIterator {
+    public:
+        SimpleArrayElementIterator( const BSONElement& theArray, bool returnArrayLast );
+
+        virtual bool more();
+        virtual Element next();
+
+    private:
+        BSONElement _theArray;
+        bool _returnArrayLast;
+        BSONObjIterator _iterator;
+    };
+
+    class BSONElementIterator : public ElementIterator {
+    public:
+        BSONElementIterator( const ElementPath& path, const BSONObj& context );
+        virtual ~BSONElementIterator();
+
+        bool more();
+        Element next();
+
+    private:
+        const ElementPath& _path;
+        BSONObj _context;
+
+        enum State { BEGIN, IN_ARRAY, DONE } _state;
+        Element _next;
+
+        struct ArrayIterationState {
+
+            void reset( const FieldRef& ref, int start );
+            void startIterator( BSONElement theArray );
+
+            bool more();
+            BSONElement next();
+
+            bool isArrayOffsetMatch( const StringData& fieldName ) const;
+            bool nextEntireRest() const { return nextPieceOfPath.size() == restOfPath.size(); }
+
+            string restOfPath;
+            bool hasMore;
+            StringData nextPieceOfPath;
+            bool nextPieceOfPathIsNumber;
+
+            BSONElement _theArray;
+            BSONElement _current;
+            boost::scoped_ptr<BSONObjIterator> _iterator;
+        };
+
+        ArrayIterationState _arrayIterationState;
+
+        boost::scoped_ptr<ElementIterator> _subCursor;
+        boost::scoped_ptr<ElementPath> _subCursorPath;
+    };
+
+}
diff --git a/src/mongo/db/matcher/expression_internal.cpp b/src/mongo/db/matcher/path_internal.cpp
index ba8c75a3596..95ccfbd6fbb 100644
--- a/src/mongo/db/matcher/expression_internal.cpp
+++ b/src/mongo/db/matcher/path_internal.cpp
@@ -1,4 +1,4 @@
-// expression_internal.h
+// path_internal.h
 
 /**
  *    Copyright (C) 2013 10gen Inc.
@@ -16,7 +16,7 @@
  *    along with this program.  If not, see <http://www.gnu.org/licenses/>.
  */
 
-#include "mongo/db/matcher/expression_internal.h"
+#include "mongo/db/matcher/path_internal.h"
 
 namespace mongo {
 
@@ -30,8 +30,7 @@ namespace mongo {
 
     BSONElement getFieldDottedOrArray( const BSONObj& doc,
                                        const FieldRef& path,
-                                       size_t* idxPath,
-                                       bool* inArray )  {
+                                       size_t* idxPath ) {
         if ( path.numParts() == 0 )
             return doc.getField( "" );
 
@@ -56,14 +55,7 @@ namespace mongo {
                 break;
 
             case Array:
-                if ( partNum+1 < path.numParts() && isAllDigits( path.getPart( partNum+1 ) ) ) {
-                    //*inArray = true;
-                    curr = res.Obj();
-                    stop = true;
-                }
-                else {
-                    stop = true;
-                }
+                stop = true;
                 break;
 
             default:
diff --git a/src/mongo/db/matcher/expression_internal.h b/src/mongo/db/matcher/path_internal.h
index 8e51dbb4ebf..8210fb6b59c 100644
--- a/src/mongo/db/matcher/expression_internal.h
+++ b/src/mongo/db/matcher/path_internal.h
@@ -1,4 +1,4 @@
-// expression_internal.h
+// path_internal.h
 
 /**
  *    Copyright (C) 2013 10gen Inc.
@@ -31,7 +31,6 @@ namespace mongo {
     // Replaces getFieldDottedOrArray without recursion nor string manipulation
     BSONElement getFieldDottedOrArray( const BSONObj& doc,
                                        const FieldRef& path,
-                                       size_t* idxPath,
-                                       bool* inArray );
+                                       size_t* idxPath );
 
 }  // namespace mongo
diff --git a/src/mongo/db/matcher/path_test.cpp b/src/mongo/db/matcher/path_test.cpp
new file mode 100644
index 00000000000..6fdf2f045bb
--- /dev/null
+++ b/src/mongo/db/matcher/path_test.cpp
@@ -0,0 +1,313 @@
+// path_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/jsobj.h"
+#include "mongo/db/matcher/path.h"
+
+namespace mongo {
+
+    TEST( Path, Root1 ) {
+        ElementPath p;
+        ASSERT( p.init( "a" ).isOK() );
+
+        BSONObj doc = BSON( "x" << 4 << "a" << 5 );
+
+        BSONElementIterator cursor( p, doc );
+        ASSERT( cursor.more() );
+        ElementIterator::Element e = cursor.next();
+        ASSERT_EQUALS( (string)"a", e.element().fieldName() );
+        ASSERT_EQUALS( 5, e.element().numberInt() );
+        ASSERT( !cursor.more() );
+    }
+
+    TEST( Path, RootArray1 ) {
+        ElementPath p;
+        ASSERT( p.init( "a" ).isOK() );
+
+        BSONObj doc = BSON( "x" << 4 << "a" << BSON_ARRAY( 5 << 6 ) );
+
+        BSONElementIterator cursor( p, doc );
+
+        ASSERT( cursor.more() );
+        BSONElementIterator::Element e = cursor.next();
+        ASSERT_EQUALS( 5, e.element().numberInt() );
+
+        ASSERT( cursor.more() );
+        e = cursor.next();
+        ASSERT_EQUALS( 6, e.element().numberInt() );
+
+        ASSERT( cursor.more() );
+        e = cursor.next();
+        ASSERT_EQUALS( Array, e.element().type() );
+
+        ASSERT( !cursor.more() );
+    }
+
+    TEST( Path, RootArray2 ) {
+        ElementPath p;
+        ASSERT( p.init( "a" ).isOK() );
+        p.setTraverseLeafArray( false );
+
+        BSONObj doc = BSON( "x" << 4 << "a" << BSON_ARRAY( 5 << 6 ) );
+
+        BSONElementIterator cursor( p, doc );
+
+        ASSERT( cursor.more() );
+        BSONElementIterator::Element e = cursor.next();
+        ASSERT( e.element().type() == Array );
+
+        ASSERT( !cursor.more() );
+    }
+
+    TEST( Path, Nested1 ) {
+        ElementPath p;
+        ASSERT( p.init( "a.b" ).isOK() );
+
+        BSONObj doc = BSON( "a" << BSON_ARRAY( BSON( "b" << 5 ) <<
+                                               3 <<
+                                               BSONObj() <<
+                                               BSON( "b" << BSON_ARRAY( 9 << 11 ) ) <<
+                                               BSON( "b" << 7 ) ) );
+
+        BSONElementIterator cursor( p, doc );
+
+        ASSERT( cursor.more() );
+        BSONElementIterator::Element e = cursor.next();
+        ASSERT_EQUALS( 5, e.element().numberInt() );
+        ASSERT( !e.outerArray() );
+
+        ASSERT( cursor.more() );
+        e = cursor.next();
+        ASSERT( e.element().eoo() );
+        ASSERT_EQUALS( (string)"2", e.arrayOffset().fieldName() );
+        ASSERT( !e.outerArray() );
+
+        ASSERT( cursor.more() );
+        e = cursor.next();
+        ASSERT_EQUALS( 9, e.element().numberInt() );
+        ASSERT( !e.outerArray() );
+
+        ASSERT( cursor.more() );
+        e = cursor.next();
+        ASSERT_EQUALS( 11, e.element().numberInt() );
+        ASSERT( !e.outerArray() );
+
+        ASSERT( cursor.more() );
+        e = cursor.next();
+        ASSERT_EQUALS( Array, e.element().type() );
+        ASSERT_EQUALS( 2, e.element().Obj().nFields() );
+        ASSERT( e.outerArray() );
+
+        ASSERT( cursor.more() );
+        e = cursor.next();
+        ASSERT_EQUALS( 7, e.element().numberInt() );
+        ASSERT( !e.outerArray() );
+
+        ASSERT( !cursor.more() );
+    }
+
+    TEST( Path, NestedNoLeaf1 ) {
+        ElementPath p;
+        ASSERT( p.init( "a.b" ).isOK() );
+        p.setTraverseLeafArray( false );
+
+        BSONObj doc = BSON( "a" << BSON_ARRAY( BSON( "b" << 5 ) <<
+                                               3 <<
+                                               BSONObj() <<
+                                               BSON( "b" << BSON_ARRAY( 9 << 11 ) ) <<
+                                               BSON( "b" << 7 ) ) );
+
+        BSONElementIterator cursor( p, doc );
+
+        ASSERT( cursor.more() );
+        BSONElementIterator::Element e = cursor.next();
+        ASSERT_EQUALS( 5, e.element().numberInt() );
+        ASSERT( !e.outerArray() );
+
+        ASSERT( cursor.more() );
+        e = cursor.next();
+        ASSERT( e.element().eoo() );
+        ASSERT_EQUALS( (string)"2", e.arrayOffset().fieldName() );
+        ASSERT( !e.outerArray() );
+
+        ASSERT( cursor.more() );
+        e = cursor.next();
+        ASSERT_EQUALS( Array, e.element().type() );
+        ASSERT_EQUALS( 2, e.element().Obj().nFields() );
+        ASSERT( e.outerArray() );
+
+        ASSERT( cursor.more() );
+        e = cursor.next();
+        ASSERT_EQUALS( 7, e.element().numberInt() );
+        ASSERT( !e.outerArray() );
+
+        ASSERT( !cursor.more() );
+    }
+
+
+    TEST( Path, ArrayIndex1 ) {
+        ElementPath p;
+        ASSERT( p.init( "a.1" ).isOK() );
+
+        BSONObj doc = BSON( "a" << BSON_ARRAY( 5 << 7 << 3 ) );
+
+        BSONElementIterator cursor( p, doc );
+
+        ASSERT( cursor.more() );
+        BSONElementIterator::Element e = cursor.next();
+        ASSERT_EQUALS( 7, e.element().numberInt() );
+
+        ASSERT( !cursor.more() );
+    }
+
+    TEST( Path, ArrayIndex2 ) {
+        ElementPath p;
+        ASSERT( p.init( "a.1" ).isOK() );
+
+        BSONObj doc = BSON( "a" << BSON_ARRAY( 5 << BSON_ARRAY( 2 << 4 ) << 3 ) );
+
+        BSONElementIterator cursor( p, doc );
+
+        ASSERT( cursor.more() );
+        BSONElementIterator::Element e = cursor.next();
+        ASSERT_EQUALS( Array, e.element().type() );
+
+        ASSERT( !cursor.more() );
+    }
+
+    TEST( Path, ArrayIndex3 ) {
+        ElementPath p;
+        ASSERT( p.init( "a.1" ).isOK() );
+
+        BSONObj doc = BSON( "a" << BSON_ARRAY( 5 << BSON( "1" << 4 ) << 3 ) );
+
+        BSONElementIterator cursor( p, doc );
+
+        ASSERT( cursor.more() );
+        BSONElementIterator::Element e = cursor.next();
+        ASSERT_EQUALS( 4, e.element().numberInt() );
+
+        ASSERT( cursor.more() );
+        e = cursor.next();
+        ASSERT_EQUALS( BSON( "1" << 4 ), e.element().Obj() );
+
+        ASSERT( !cursor.more() );
+    }
+
+    TEST( Path, ArrayIndexNested1 ) {
+        ElementPath p;
+        ASSERT( p.init( "a.1.b" ).isOK() );
+
+        BSONObj doc = BSON( "a" << BSON_ARRAY( 5 << BSON( "b" << 4 ) << 3 ) );
+
+        BSONElementIterator cursor( p, doc );
+
+        ASSERT( cursor.more() );
+        BSONElementIterator::Element e = cursor.next();
+        ASSERT( e.element().eoo() );
+
+        ASSERT( cursor.more() );
+        e = cursor.next();
+        ASSERT_EQUALS( 4, e.element().numberInt() );
+
+
+        ASSERT( !cursor.more() );
+    }
+
+    TEST( Path, ArrayIndexNested2 ) {
+        ElementPath p;
+        ASSERT( p.init( "a.1.b" ).isOK() );
+
+        BSONObj doc = BSON( "a" << BSON_ARRAY( 5 << BSON_ARRAY( BSON( "b" << 4 ) ) << 3 ) );
+
+        BSONElementIterator cursor( p, doc );
+
+        ASSERT( cursor.more() );
+        BSONElementIterator::Element e = cursor.next();
+        ASSERT_EQUALS( 4, e.element().numberInt() );
+
+
+        ASSERT( !cursor.more() );
+    }
+
+    TEST( SimpleArrayElementIterator, SimpleNoArrayLast1 ) {
+        BSONObj obj = BSON( "a" << BSON_ARRAY( 5 << BSON( "x" << 6 ) << BSON_ARRAY( 7 << 9 ) << 11 ) );
+        SimpleArrayElementIterator i( obj["a"], false );
+
+        ASSERT( i.more() );
+        ElementIterator::Element e = i.next();
+        ASSERT_EQUALS( 5, e.element().numberInt() );
+
+        ASSERT( i.more() );
+        e = i.next();
+        ASSERT_EQUALS( 6, e.element().Obj()["x"].numberInt() );
+
+        ASSERT( i.more() );
+        e = i.next();
+        ASSERT_EQUALS( 7, e.element().Obj().firstElement().numberInt() );
+
+        ASSERT( i.more() );
+        e = i.next();
+        ASSERT_EQUALS( 11, e.element().numberInt() );
+
+        ASSERT( !i.more() );
+    }
+
+    TEST( SimpleArrayElementIterator, SimpleArrayLast1 ) {
+        BSONObj obj = BSON( "a" << BSON_ARRAY( 5 << BSON( "x" << 6 ) << BSON_ARRAY( 7 << 9 ) << 11 ) );
+        SimpleArrayElementIterator i( obj["a"], true );
+
+        ASSERT( i.more() );
+        ElementIterator::Element e = i.next();
+        ASSERT_EQUALS( 5, e.element().numberInt() );
+
+        ASSERT( i.more() );
+        e = i.next();
+        ASSERT_EQUALS( 6, e.element().Obj()["x"].numberInt() );
+
+        ASSERT( i.more() );
+        e = i.next();
+        ASSERT_EQUALS( 7, e.element().Obj().firstElement().numberInt() );
+
+        ASSERT( i.more() );
+        e = i.next();
+        ASSERT_EQUALS( 11, e.element().numberInt() );
+
+        ASSERT( i.more() );
+        e = i.next();
+        ASSERT_EQUALS( Array, e.element().type() );
+
+        ASSERT( !i.more() );
+    }
+
+    TEST( SingleElementElementIterator, Simple1 ) {
+        BSONObj obj = BSON( "x" << 3 << "y" << 5 );
+        SingleElementElementIterator i( obj["y"] );
+
+        ASSERT( i.more() );
+        ElementIterator::Element e = i.next();
+        ASSERT_EQUALS( 5, e.element().numberInt() );
+
+        ASSERT( !i.more() );
+
+    }
+
+}