SERVER-5710 Changed KeyPattern.hasField() sematics to consider dotted field prefixes.

12 files changed, 234 insertions, 27 deletions

diff --git a/src/mongo/SConscript b/src/mongo/SConscript
index 5dbfb7c1e8f..41f57bbe999 100644
--- a/src/mongo/SConscript
+++ b/src/mongo/SConscript
@@ -17,7 +17,7 @@ Import("darwin windows solaris linux nix")
 env.SConscript(['base/SConscript',
                 'db/auth/SConscript',
                 'db/fts/SConscript',
-                'db/ops/SConscript',
+                'db/SConscript',
                 'platform/SConscript',
                 's/SConscript',
                 'unittest/SConscript'])
@@ -267,9 +267,11 @@ env.StaticLibrary("coredb", [
         "s/shardconnection.cpp",
         ],
                   LIBDEPS=['db/auth/serverauth',
+                           'db/common',
                            'server_parameters',
                            'geoparser',
-                           'geoquery'])
+                           'geoquery',
+                           '$BUILD_DIR/mongo/foundation'])
 
 coreServerFiles = [ "db/client_basic.cpp",
                     "db/common.cpp",
@@ -547,7 +549,7 @@ env.StaticLibrary("serveronly", serverOnlyFiles,
                   LIBDEPS=["coreshard",
                            "db/auth/authmongod",
                            "db/fts/ftsmongod",
-                           "db/ops/update",
+                           "db/common",
                            "dbcmdline",
                            "defaultversion",
                            "geoparser",
diff --git a/src/mongo/base/string_data-inl.h b/src/mongo/base/string_data-inl.h
index 00b403a569c..9d6d024df9c 100644
--- a/src/mongo/base/string_data-inl.h
+++ b/src/mongo/base/string_data-inl.h
@@ -61,8 +61,11 @@ namespace mongo {
             dest[size()] = 0;
     }
 
-    inline size_t StringData::find( char c ) const {
-        const void* x = memchr( _data, c, size() );
+    inline size_t StringData::find( char c, size_t fromPos ) const {
+        if ( fromPos >= size() )
+            return string::npos;
+
+        const void* x = memchr( _data + fromPos, c, _size - fromPos );
         if ( x == 0 )
             return string::npos;
         return static_cast<size_t>( static_cast<const char*>(x) - _data );
diff --git a/src/mongo/base/string_data.h b/src/mongo/base/string_data.h
index a54de185905..dca41fa1e9a 100644
--- a/src/mongo/base/string_data.h
+++ b/src/mongo/base/string_data.h
@@ -96,7 +96,7 @@ namespace mongo {
         // finders
         //
 
-        size_t find( char c ) const;
+        size_t find( char c , size_t fromPos = 0 ) const;
         size_t find( const StringData& needle ) const;
 
         /**
diff --git a/src/mongo/db/SConscript b/src/mongo/db/SConscript
new file mode 100644
index 00000000000..2d3a4f65734
--- /dev/null
+++ b/src/mongo/db/SConscript
@@ -0,0 +1,15 @@
+# -*- mode: python -*-
+
+Import("env")
+
+#
+# We'd like 'common' to have the abstractions that are shared by several components of the
+# server. Ideally, many of the object in 'coredb' should be moved here when their dependencies
+# get resolved.
+#
+
+env.StaticLibrary('common', ['field_ref.cpp'],
+                  LIBDEPS=['$BUILD_DIR/mongo/bson',
+                           '$BUILD_DIR/mongo/foundation'])
+
+env.CppUnitTest('field_ref_test', ['field_ref_test.cpp'], LIBDEPS=['common'])
diff --git a/src/mongo/db/ops/field_ref.cpp b/src/mongo/db/field_ref.cpp
index f4dac8f9097..7b9f5631140 100644
--- a/src/mongo/db/ops/field_ref.cpp
+++ b/src/mongo/db/field_ref.cpp
@@ -14,7 +14,7 @@
  *    along with this program.  If not, see <http://www.gnu.org/licenses/>.
  */
 
-#include "mongo/db/ops/field_ref.h"
+#include "mongo/db/field_ref.h"
 #include "mongo/util/assert_util.h"
 
 namespace mongo {
diff --git a/src/mongo/db/ops/field_ref.h b/src/mongo/db/field_ref.h
index ea7b7dab34d..ea7b7dab34d 100644
--- a/src/mongo/db/ops/field_ref.h
+++ b/src/mongo/db/field_ref.h
diff --git a/src/mongo/db/ops/field_ref_test.cpp b/src/mongo/db/field_ref_test.cpp
index e6645acffc1..e84a9d1158a 100644
--- a/src/mongo/db/ops/field_ref_test.cpp
+++ b/src/mongo/db/field_ref_test.cpp
@@ -18,7 +18,7 @@
 #include "mongo/base/error_codes.h"
 #include "mongo/base/status.h"
 #include "mongo/base/string_data.h"
-#include "mongo/db/ops/field_ref.h"
+#include "mongo/db/field_ref.h"
 #include "mongo/unittest/unittest.h"
 #include "mongo/util/mongoutils/str.h"
 
diff --git a/src/mongo/db/keypattern.cpp b/src/mongo/db/keypattern.cpp
index 5123048d816..89eca1f16c6 100644
--- a/src/mongo/db/keypattern.cpp
+++ b/src/mongo/db/keypattern.cpp
@@ -17,14 +17,29 @@
 */
 
 #include "mongo/db/keypattern.h"
-#include "mongo/util/mongoutils/str.h"
+
 #include "mongo/db/hasher.h"
 #include "mongo/db/queryutil.h"
+#include "mongo/util/mongoutils/str.h"
 
 using namespace mongoutils;
 
 namespace mongo {
 
+    KeyPattern::KeyPattern( const BSONObj& pattern ): _pattern( pattern ) {
+
+        // Extract all prefixes of each field in pattern.
+        BSONForEach( field, _pattern ) {
+            StringData fieldName = field.fieldName();
+            size_t pos = fieldName.find( '.' );
+            while ( pos != string::npos ) {
+                _prefixes.insert( StringData( field.fieldName(), pos ) );
+                pos = fieldName.find( '.', pos+1 );
+            }
+            _prefixes.insert( fieldName );
+        }
+    }
+
     BSONObj KeyPattern::extractSingleKey(const BSONObj& doc ) const {
         if ( _pattern.isEmpty() )
             return BSONObj();
diff --git a/src/mongo/db/keypattern.h b/src/mongo/db/keypattern.h
index fae49bb931a..a25ce2b87e5 100644
--- a/src/mongo/db/keypattern.h
+++ b/src/mongo/db/keypattern.h
@@ -20,6 +20,7 @@
 
 #include "mongo/base/string_data.h"
 #include "mongo/db/jsobj.h"
+#include "mongo/platform/unordered_set.h"
 #include "mongo/util/mongoutils/str.h"
 
 namespace mongo {
@@ -47,7 +48,10 @@ namespace mongo {
      */
     class KeyPattern {
     public:
-        KeyPattern( const BSONObj& pattern ): _pattern( pattern ) {}
+        /*
+         * We are allowing implicit conversion from BSON
+         */
+        KeyPattern( const BSONObj& pattern );
 
         /*
          *  Returns a BSON representation of this KeyPattern.
@@ -55,10 +59,12 @@ namespace mongo {
         BSONObj toBSON() const { return _pattern; }
 
         /*
-         * Returns true if the given fieldname is the name of one element of the (potentially)
-         * compound key described by this KeyPattern.
+         * Returns true if the given fieldname is the (dotted prefix of the) name of one
+         * element of the (potentially) compound key described by this KeyPattern.
          */
-        bool hasField( const StringData& fieldname ) const { return _pattern.hasField( fieldname ); }
+        bool hasField( const StringData& fieldname ) const {
+            return _prefixes.find( fieldname ) != _prefixes.end();
+        }
 
         /*
          * Gets the element of this pattern corresponding to the given fieldname.
@@ -159,12 +165,33 @@ namespace mongo {
 
     private:
         BSONObj _pattern;
+
+        // Each field in the '_pattern' may be itself a dotted field. We store all the prefixes
+        // of each field here. For instance, if a pattern is { 'a.b.c': 1, x: 1 }, we'll store
+        // here 'a', 'a.b', 'a.b.c', and 'x'.
+        //
+        // Since we're indexing into '_pattern's field names, it must stay constant after
+        // constructed.
+        struct PrefixHasher {
+            size_t operator()( const StringData& strData ) const {
+                size_t result = 0;
+                const char* p = strData.rawData();
+                for (size_t len = strData.size(); len > 0; len-- ) {
+                    result = ( result * 131 ) + *p++;
+                }
+                return result;
+            }
+        };
+        unordered_set<StringData, PrefixHasher> _prefixes;
+
         bool isAscending( const BSONElement& fieldExpression ) const {
             return ( fieldExpression.isNumber()  && fieldExpression.numberInt() == 1 );
         }
+
         bool isDescending( const BSONElement& fieldExpression ) const {
             return ( fieldExpression.isNumber()  && fieldExpression.numberInt() == -1 );
         }
+
         bool isHashed( const BSONElement& fieldExpression ) const {
             return mongoutils::str::equals( fieldExpression.valuestrsafe() , "hashed" );
         }
@@ -178,5 +205,4 @@ namespace mongo {
 
     };
 
-
 } // namespace mongo
diff --git a/src/mongo/db/ops/SConscript b/src/mongo/db/ops/SConscript
deleted file mode 100644
index eb33dfb5680..00000000000
--- a/src/mongo/db/ops/SConscript
+++ /dev/null
@@ -1,9 +0,0 @@
-# -*- mode: python -*-
-
-Import("env")
-
-env.StaticLibrary('update', ['field_ref.cpp'],
-                  LIBDEPS=['$BUILD_DIR/mongo/bson',
-                           '$BUILD_DIR/mongo/foundation'])
-
-env.CppUnitTest('field_ref_test', ['field_ref_test.cpp'], LIBDEPS=['update'])
diff --git a/src/mongo/db/ops/update_internal.cpp b/src/mongo/db/ops/update_internal.cpp
index 0dfb7993ec1..5e6a2a7b32c 100644
--- a/src/mongo/db/ops/update_internal.cpp
+++ b/src/mongo/db/ops/update_internal.cpp
@@ -20,10 +20,10 @@
 
 #include <algorithm> // for max
 
-#include "mongo/db/oplog.h"
-#include "mongo/db/ops/field_ref.h"
+#include "mongo/db/field_ref.h"
 #include "mongo/db/jsobjmanipulator.h"
 #include "mongo/db/pdfile.h"
+#include "mongo/db/oplog.h"
 #include "mongo/util/mongoutils/str.h"
 
 #include "update_internal.h"
diff --git a/src/mongo/dbtests/keypatterntests.cpp b/src/mongo/dbtests/keypatterntests.cpp
index 7d8568c5706..641dea16c8f 100644
--- a/src/mongo/dbtests/keypatterntests.cpp
+++ b/src/mongo/dbtests/keypatterntests.cpp
@@ -95,6 +95,161 @@ namespace KeyPatternTests {
         }
     };
 
+    class HasFieldTests {
+    public:
+        void run() {
+            // TEST(HasField, SameKey)
+            {
+                KeyPattern keyPat( BSON( "x" << 1 ) );
+                ASSERT_TRUE( keyPat.hasField( "x" ) );
+            }
+
+            // TEST( HasField, DifferentKey )
+            {
+                KeyPattern keyPat( BSON( "x" << 1 ) );
+                ASSERT_FALSE( keyPat.hasField( "y" ) );
+            }
+
+            // TEST( HasField, SameKey2Levels )
+            {
+                KeyPattern keyPat( BSON( "x.y" << 1 ) );
+                ASSERT_TRUE( keyPat.hasField( "x.y" ) );
+            }
+
+            // TEST( HasField, SameKeyPartial )
+            {
+                KeyPattern keyPat( BSON( "xyz.a" << 1 ) );
+                ASSERT_TRUE( keyPat.hasField( "xyz" ) );
+            }
+
+            // TEST( HasField, DifferentChildKey )
+            {
+                KeyPattern keyPat( BSON( "x.y" << 1 ) );
+                ASSERT_FALSE( keyPat.hasField( "x.b" ) );
+            }
+
+            // TEST( HasField, DifferentRootKeyDotted )
+            {
+                KeyPattern keyPat( BSON( "x.y" << 1 ) );
+                ASSERT_FALSE( keyPat.hasField( "a.y" ) );
+            }
+
+            // TEST( HasField, SameRootKeyPartial )
+            {
+                KeyPattern keyPat( BSON( "x.y" << 1 ) );
+                ASSERT_TRUE( keyPat.hasField( "x" ) );
+            }
+
+            // TEST( HasField, DifferentRootKeyPartial )
+            {
+                KeyPattern keyPat( BSON( "x.y" << 1 ) );
+                ASSERT_FALSE( keyPat.hasField( "a" ) );
+            }
+
+            // TEST( HasField, DifferentMatchingChildKey )
+            {
+                KeyPattern keyPat( BSON( "x.y" << 1 ) );
+                ASSERT_FALSE( keyPat.hasField( "y" ) );
+            }
+
+            // TEST( HasField, SameKey3Level )
+            {
+                KeyPattern keyPat( BSON( "x.y.z" << 1 ) );
+                ASSERT_TRUE( keyPat.hasField( "x.y.z" ) );
+            }
+
+            // TEST( HasField, Same3LevelKeyPartialUpto1 )
+            {
+                KeyPattern keyPat( BSON( "x.y.z" << 1 ) );
+                ASSERT_TRUE( keyPat.hasField( "x" ) );
+            }
+
+            // TEST( HasField, Same3LevelKeyPartialUpto2 )
+            {
+                KeyPattern keyPat( BSON( "x.y.z" << 1 ) );
+                ASSERT_TRUE( keyPat.hasField( "x.y" ) );
+            }
+
+            // TEST( HasField, DifferentDottedRoot3Level )
+            {
+                KeyPattern keyPat( BSON( "x.y.z" << 1 ) );
+                ASSERT_FALSE( keyPat.hasField( "x.b" ) );
+            }
+
+            // TEST( HasField, DifferentRoot3Levels )
+            {
+                KeyPattern keyPat( BSON( "x.y.z" << 1 ) );
+                ASSERT_FALSE( keyPat.hasField( "a" ) );
+            }
+
+            // TEST( HasField, SameCompoundHasField )
+            {
+                KeyPattern keyPat( BSON( "x" << 1 << "y" << -1 ) );
+                ASSERT_TRUE( keyPat.hasField( "y" ) );
+            }
+
+            // TEST( HasField, SameDottedCompoundHasField )
+            {
+                KeyPattern keyPat( BSON( "x.y" << 1 << "a.b" << -1 ) );
+                ASSERT_TRUE( keyPat.hasField( "a.b" ) );
+            }
+
+            // TEST( HasField, Same3LevelEmbeddedCompoundHasField )
+            {
+                KeyPattern keyPat( BSON( "x.y" << 1 << "a.b.c" << -1 ) );
+                ASSERT_TRUE( keyPat.hasField( "a" ) );
+            }
+
+            // TEST( HasField, DifferentCompoundHasField )
+            {
+                KeyPattern keyPat( BSON( "x" << 1 << "y" << -1 ) );
+                ASSERT_FALSE( keyPat.hasField( "z" ) );
+            }
+
+            // TEST( HasField, DifferentDottedCompoundHasField )
+            {
+                KeyPattern keyPat( BSON( "x.y" << 1 << "a.b" << -1 ) );
+                ASSERT_FALSE( keyPat.hasField( "a.j" ) );
+            }
+
+            // TEST( HasField, SameRootLongerObjKey )
+            {
+                KeyPattern keyPat( BSON( "x" << 1 ) );
+                ASSERT_FALSE( keyPat.hasField( "x.y.z" ) );
+            }
+
+            // TEST( HasField, DifferentRootLongerObjKey )
+            {
+                KeyPattern keyPat( BSON( "x" << 1 ) );
+                ASSERT_FALSE( keyPat.hasField( "a.b.c" ) );
+            }
+
+            // TEST( HasField, DifferentRootPrefixObjKey )
+            {
+                KeyPattern keyPat( BSON( "xyz.a" << 1 ) );
+                ASSERT_FALSE( keyPat.hasField( "xy" ) );
+            }
+
+            // TEST( HasField, DifferentRootPrefixHasField )
+            {
+                KeyPattern keyPat( BSON( "xyz" << 1 ) );
+                ASSERT_FALSE( keyPat.hasField( "xyzabc" ) );
+            }
+
+            // TEST( HasField, DifferentRootPartialPrefixObjKey )
+            {
+                KeyPattern keyPat( BSON( "xyz" << 1 ) );
+                ASSERT_FALSE( keyPat.hasField( "xy.z" ) );
+            }
+
+            // TEST( HasField, DifferentRootPartialPrefixHasField )
+            {
+                KeyPattern keyPat( BSON( "xy.z" << 1 ) );
+                ASSERT_FALSE( keyPat.hasField( "xyz" ) );
+            }
+        }
+    };
+
     class All : public Suite {
     public:
         All() : Suite( "keypattern" ) {
@@ -102,8 +257,8 @@ namespace KeyPatternTests {
 
         void setupTests() {
             add< ExtendRangeBoundTests >();
+            add< HasFieldTests >();
         }
     } myall;
 
-} // namespace JsobjTests
-
+} // namespace KeyPatternTests