SERVER-7175 Support for catching conflicting mods in the update driver.

8 files changed, 581 insertions, 87 deletions

diff --git a/src/mongo/db/SConscript b/src/mongo/db/SConscript
index 6baa3da84d6..9343d53f0cb 100644
--- a/src/mongo/db/SConscript
+++ b/src/mongo/db/SConscript
@@ -3,15 +3,44 @@
 Import("env")
 
 #
-# We'd like 'common' to have the abstractions that are shared by several components of the
+# The db/'common' lib has the abstractions that are shared by 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', 'field_parser.cpp'],
-                  LIBDEPS=['$BUILD_DIR/mongo/bson',
-                           '$BUILD_DIR/mongo/foundation'])
+env.StaticLibrary(
+    target= 'common',
+    source= [
+        'field_ref.cpp',
+        'field_ref_set.cpp',
+        'field_parser.cpp',
+    ],
+    LIBDEPS=[
+        '$BUILD_DIR/mongo/bson',
+        '$BUILD_DIR/mongo/foundation',
+    ],
+)
 
-env.CppUnitTest('field_ref_test', ['field_ref_test.cpp'], LIBDEPS=['common'])
+env.CppUnitTest(
+    target= 'field_ref_test',
+    source= 'field_ref_test.cpp',
+    LIBDEPS=[
+        'common',
+    ],
+)
 
-env.CppUnitTest('field_parser_test', ['field_parser_test.cpp'], LIBDEPS=['common'])
+env.CppUnitTest(
+    target= 'field_ref_set_test',
+    source = 'field_ref_set_test.cpp',
+    LIBDEPS=[
+        'common',
+    ],
+)
+
+env.CppUnitTest(
+    target= 'field_parser_test',
+    source= 'field_parser_test.cpp',
+    LIBDEPS=[
+        'common',
+   ],
+)
diff --git a/src/mongo/db/field_ref.cpp b/src/mongo/db/field_ref.cpp
index ab1cbc7046b..a23df8d3d7c 100644
--- a/src/mongo/db/field_ref.cpp
+++ b/src/mongo/db/field_ref.cpp
@@ -16,6 +16,8 @@
 
 #include "mongo/db/field_ref.h"
 
+#include <algorithm> // for min
+
 #include "mongo/util/log.h"
 #include "mongo/util/assert_util.h"
 
@@ -94,11 +96,37 @@ namespace mongo {
         }
     }
 
-    void FieldRef::clear() {
-        _size = 0;
-        _variable.clear();
-        _fieldBase.reset();
-        _replacements.clear();
+    bool FieldRef::isPrefixOf( const FieldRef& other ) const {
+        // Can't be a prefix if the size is equal to or larger.
+        if ( _size >= other._size ) {
+            return false;
+        }
+
+        // Empty FieldRef is not a prefix of anything.
+        if ( _size == 0 ) {
+            return false;
+        }
+
+        size_t common = commonPrefixSize( other );
+        return common == _size && other._size > common;
+    }
+
+    size_t FieldRef::commonPrefixSize( const FieldRef& other ) const {
+        if (_size == 0 || other._size == 0) {
+            return 0;
+        }
+
+        size_t maxPrefixSize = std::min( _size-1, other._size-1 );
+        size_t prefixSize = 0;
+
+        while ( prefixSize <= maxPrefixSize ) {
+            if ( getPart( prefixSize ) != other.getPart( prefixSize ) ) {
+                break;
+            }
+            prefixSize++;
+        }
+
+        return prefixSize;
     }
 
     std::string FieldRef::dottedField( size_t offset ) const {
@@ -117,27 +145,9 @@ namespace mongo {
         return res;
     }
 
-    bool FieldRef::isPrefixOf( const FieldRef& other ) const {
-        // Can't be a prefix if equal to or larger
-        if ( other._size <= _size )
-            return false;
-
-        for ( size_t i = 0; i < _size; i++ ) {
-            // Get parts
-            StringData part = getPart( i );
-            StringData otherPart = other.getPart( i );
-
-            // If the parts are diff, can't be a prefix
-            if ( part != otherPart )
-                return false;
-        }
-        return true;
-    }
-
     bool FieldRef::equalsDottedField( const StringData& other ) const {
         StringData rest = other;
 
-
         for ( size_t i = 0; i < _size; i++ ) {
 
             StringData part = getPart( i );
@@ -161,6 +171,34 @@ namespace mongo {
         return false;
     }
 
+    int FieldRef::compare(const FieldRef& other) const {
+        const size_t toCompare = std::min(_size, other._size);
+        for (size_t i = 0; i < toCompare; i++) {
+            if (getPart(i) == other.getPart(i)) {
+                continue;
+            }
+            return getPart(i) < other.getPart(i) ? -1 : 1;
+        }
+
+        const size_t rest = _size - toCompare;
+        const size_t otherRest = other._size - toCompare;
+        if ((rest == 0) && (otherRest == 0)) {
+            return 0;
+        }
+        else if (rest < otherRest ) {
+            return -1;
+        }
+        else {
+            return 1;
+        }
+    }
+
+    void FieldRef::clear() {
+        _size = 0;
+        _variable.clear();
+        _fieldBase.reset();
+        _replacements.clear();
+    }
 
     size_t FieldRef::numReplaced() const {
         size_t res = 0;
@@ -172,4 +210,8 @@ namespace mongo {
         return res;
     }
 
+    std::ostream& operator<<(std::ostream& stream, const FieldRef& field) {
+        return stream << field.dottedField();
+    }
+
 } // namespace mongo
diff --git a/src/mongo/db/field_ref.h b/src/mongo/db/field_ref.h
index ed3a110715b..e04497f7ae1 100644
--- a/src/mongo/db/field_ref.h
+++ b/src/mongo/db/field_ref.h
@@ -17,6 +17,7 @@
 #pragma once
 
 #include <boost/scoped_array.hpp>
+#include <iosfwd>
 #include <string>
 #include <vector>
 
@@ -63,12 +64,34 @@ namespace mongo {
         StringData getPart(size_t i) const;
 
         /**
+         * Returns true when 'this' FieldRef is a prefix of 'other'. Equality is not considered
+         * a prefix.
+         */
+        bool isPrefixOf( const FieldRef& other ) const;
+
+        /**
+         * Returns the number of field parts in the prefix that 'this' and 'other' share.
+         */
+        size_t commonPrefixSize( const FieldRef& other ) const;
+
+        /**
          * Returns a copy of the full dotted field in its current state (i.e., some parts may
          * have been replaced since the parse() call).
          */
         std::string dottedField( size_t offset = 0 ) const;
 
         /**
+         * Compares the full dotted path represented by this FieldRef to other
+         */
+        bool equalsDottedField( const StringData& other ) const;
+
+        /**
+         * Return 0 if 'this' is equal to 'other' lexicographically, -1 if is it less than or
+         * +1 if it is greater than.
+         */
+        int compare( const FieldRef& other ) const;
+
+        /**
          * Resets the internal state. See note in parse() call.
          */
         void clear();
@@ -88,34 +111,13 @@ namespace mongo {
          */
         size_t numReplaced() const;
 
-        /**
-         * Compares the full dotted path represented by this FieldRef to other
-         */
-        bool equalsDottedField( const StringData& other ) const;
-
-        /**
-         * Compares the full dotted path represented by this FieldRef to other,
-         * and that we are a prefix of them.
-         *
-         * Returns true when 'this' is a prefix of 'other'; equality is not considered a prefix.
-         */
-        bool isPrefixOf( const FieldRef& other ) const;
-
     private:
-        // Dotted fields are most often not longer than three parts. We use a mixed structure
+        // Dotted fields are most often not longer than four parts. We use a mixed structure
         // here that will not require any extra memory allocation when that is the case. And
         // handle larger dotted fields if it is. The idea is not to penalize the common case
         // with allocations.
         static const size_t kReserveAhead = 4;
 
-        size_t _size;                                // # of field parts stored
-        StringData _fixed[kReserveAhead];            // first kResevedAhead field components
-        std::vector<StringData> _variable;           // remaining field components
-
-        // Areas that _fixed and _variable point to.
-        boost::scoped_array<char> _fieldBase;        // concatenation of null-terminated parts
-        std::vector<std::string> _replacements;      // added with the setPart call
-
         /** Converts the field part index to the variable part equivalent */
         size_t getIndex(size_t i) const { return i-kReserveAhead; }
 
@@ -125,10 +127,46 @@ namespace mongo {
          */
         size_t appendPart(const StringData& part);
 
+        // number of field parts stored
+        size_t _size;
+
+        // first kResevedAhead field components
+        StringData _fixed[kReserveAhead];
+
+         // remaining field components
+        std::vector<StringData> _variable;
+
+        // concatenation of null-terminated parts pointed to by _fixed and _variable
+        boost::scoped_array<char> _fieldBase;
+
+        // back memory added with the setPart call pointed to by _fized and _variable
+        std::vector<std::string> _replacements;
     };
 
     inline bool operator==(const FieldRef& lhs, const FieldRef& rhs) {
-        return lhs.equalsDottedField(rhs.dottedField());
+        return lhs.compare(rhs) == 0;
+    }
+
+    inline bool operator!=(const FieldRef& lhs, const FieldRef& rhs) {
+        return lhs.compare(rhs) != 0;
+    }
+
+    inline bool operator<(const FieldRef& lhs, const FieldRef& rhs) {
+        return lhs.compare(rhs) < 0;
+    }
+
+    inline bool operator<=(const FieldRef& lhs, const FieldRef& rhs) {
+        return lhs.compare(rhs) <= 0;
     }
 
+    inline bool operator>(const FieldRef& lhs, const FieldRef& rhs) {
+        return lhs.compare(rhs) > 0;
+    }
+
+    inline bool operator>=(const FieldRef& lhs, const FieldRef& rhs) {
+        return lhs.compare(rhs) >= 0;
+    }
+
+    std::ostream& operator<<(std::ostream& stream, const FieldRef& value);
+
 } // namespace mongo
diff --git a/src/mongo/db/field_ref_set.cpp b/src/mongo/db/field_ref_set.cpp
new file mode 100644
index 00000000000..f4970d5d405
--- /dev/null
+++ b/src/mongo/db/field_ref_set.cpp
@@ -0,0 +1,87 @@
+/**
+ *    Copyright (C) 2013 10gen Inc.
+ *
+ *    This program is free software: you can redistribute it and/or  modify
+ *    it under the terms of the GNU Affero General Public License, version 3,
+ *    as published by the Free Software Foundation.
+ *
+ *    This program is distributed in the hope that it will be useful,
+ *    but WITHOUT ANY WARRANTY; without even the implied warranty of
+ *    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ *    GNU Affero General Public License for more details.
+ *
+ *    You should have received a copy of the GNU Affero General Public License
+ *    along with this program.  If not, see <http://www.gnu.org/licenses/>.
+ */
+
+#include "mongo/db/field_ref_set.h"
+
+#include "mongo/util/assert_util.h"
+
+namespace mongo {
+
+    namespace {
+
+        // For legacy purposes, we must handle empty fieldnames, which FieldRef clearly
+        // prohibits. It is preferrable to have FieldRef keep that constraint and relax it here
+        // -- stricly in update code. The rationale is that, if we want to ban data with no
+        // field names, we must allow that data to be updated.
+        StringData safeFirstPart(const FieldRef* fieldRef) {
+            if (fieldRef->numParts() == 0) {
+                return StringData();
+            }
+            else {
+                return fieldRef->getPart(0);
+            }
+        }
+
+    }
+
+    bool FieldRefSet::FieldRefPtrLessThan::operator()(const FieldRef* l, const FieldRef* r) const {
+            return *l < *r;
+    }
+
+    FieldRefSet::FieldRefSet() {
+    }
+
+    bool FieldRefSet::insert(const FieldRef* toInsert, const FieldRef** conflict) {
+
+        // We can determine if two fields conflict by checking their common prefix.
+        //
+        // If each field is exactly of the size of the common prefix, this means the fields are
+        // the same. If one of the fields is greater than the common prefix and the other
+        // isn't, the latter is a prefix of the former. And vice-versa.
+        //
+        // Example:
+        //
+        // inserted >      |    a          a.c
+        // exiting  v      |   (0)        (+1)
+        // ----------------|------------------------
+        //      a (0)      |  equal      prefix <
+        //      a.b (+1)   | prefix ^      *
+        //
+        // * Disjoint sub-trees
+
+        // At each insertion, we only need to bother checking the fields in the set that have
+        // at least some common prefix with the 'toInsert' field.
+        StringData  prefixStr = safeFirstPart(toInsert);
+        FieldRef prefixField;
+        prefixField.parse(prefixStr);
+        FieldSet::iterator it = _fieldSet.lower_bound(&prefixField);
+
+        // Now, iterate over all the present fields in the set that have the same prefix.
+        while (it != _fieldSet.end() && safeFirstPart(*it) == prefixStr) {
+            size_t common = (*it)->commonPrefixSize(*toInsert);
+            if ((*it)->numParts() == common || toInsert->numParts() == common) {
+                *conflict = *it;
+                return false;
+            }
+            ++it;
+        }
+
+        _fieldSet.insert(it, toInsert);
+        *conflict = NULL;
+        return true;
+    }
+
+} // namespace mongo
diff --git a/src/mongo/db/field_ref_set.h b/src/mongo/db/field_ref_set.h
new file mode 100644
index 00000000000..c1e8b413e81
--- /dev/null
+++ b/src/mongo/db/field_ref_set.h
@@ -0,0 +1,57 @@
+/**
+ *    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 <set>
+
+#include "mongo/base/disallow_copying.h"
+#include "mongo/db/field_ref.h"
+
+namespace mongo {
+
+    /**
+     * A FieldRefSet holds a set of FieldRefs's that do not conflict with one another, that is,
+     * they target different subtrees of a given document. Two fieldRef's would conflict if they
+     * are equal or one is prefix of the other.
+     */
+    class FieldRefSet {
+        MONGO_DISALLOW_COPYING(FieldRefSet);
+    public:
+        FieldRefSet();
+
+        /**
+         * Returns true if the field 'toInsert' can be added in the set without
+         * conflicts. Otwerwise returns false and fill in '*conflict' with the field 'toInsert'
+         * clashed with.
+         *
+         * There is no ownership transfer of 'toInsert'. The caller is responsible for
+         * maintaining it alive for as long as the FieldRefSet is so. By the same token
+         * 'conflict' can only be referred to while the FieldRefSet can.
+         */
+        bool insert(const FieldRef* toInsert, const FieldRef** conflict);
+
+    private:
+        struct FieldRefPtrLessThan {
+            bool operator()(const FieldRef* lhs, const FieldRef* rhs) const;
+        };
+        typedef std::set<const FieldRef*, FieldRefPtrLessThan> FieldSet;
+
+        // A set of field_ref pointers, none of which is owned here.
+        FieldSet _fieldSet;
+    };
+
+} // namespace mongo
diff --git a/src/mongo/db/field_ref_set_test.cpp b/src/mongo/db/field_ref_set_test.cpp
new file mode 100644
index 00000000000..d1a76e7eeeb
--- /dev/null
+++ b/src/mongo/db/field_ref_set_test.cpp
@@ -0,0 +1,148 @@
+/**
+ *    Copyright 2013 10gen Inc.
+ *
+ *    Licensed under the Apache License, Version 2.0 (the "License");
+ *    you may not use this file except in compliance with the License.
+ *    You may obtain a copy of the License at
+ *
+ *    http://www.apache.org/licenses/LICENSE-2.0
+ *
+ *    Unless required by applicable law or agreed to in writing, software
+ *    distributed under the License is distributed on an "AS IS" BASIS,
+ *    WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ *    See the License for the specific language governing permissions and
+ *    limitations under the License.
+ */
+
+#include "mongo/db/field_ref_set.h"
+
+#include "mongo/db/field_ref.h"
+#include "mongo/unittest/unittest.h"
+
+namespace {
+
+    using mongo::FieldRef;
+    using mongo::FieldRefSet;
+
+    TEST(EmptySet, Normal) {
+        // insert "b"
+        FieldRefSet fieldSet;
+        FieldRef bSimple;
+        bSimple.parse("b");
+        const FieldRef* conflict;
+        ASSERT_TRUE(fieldSet.insert(&bSimple, &conflict));
+        ASSERT_EQUALS(static_cast<const FieldRef*>(NULL), conflict);
+
+        // insert "a", OK
+        FieldRef aSimple;
+        aSimple.parse("a");
+        ASSERT_TRUE(fieldSet.insert(&aSimple, &conflict));
+        ASSERT_EQUALS(static_cast<const FieldRef*>(NULL), conflict);
+
+        // insert "c", OK
+        FieldRef cSimple;
+        cSimple.parse("c");
+        ASSERT_TRUE(fieldSet.insert(&cSimple, &conflict));
+        ASSERT_EQUALS(static_cast<const FieldRef*>(NULL), conflict);
+    }
+
+    TEST(EmptySet, Conflict) {
+        // insert "a.b"
+        FieldRefSet fieldSet;
+        FieldRef aDotB;
+        aDotB.parse("a.b");
+        const FieldRef* conflict;
+        ASSERT_TRUE(fieldSet.insert(&aDotB, &conflict));
+        ASSERT_EQUALS(static_cast<const FieldRef*>(NULL), conflict);
+
+        // insert "a", conflicts with "a.b"
+        FieldRef prefix;
+        prefix.parse("a");
+        ASSERT_FALSE(fieldSet.insert(&prefix, &conflict));
+        ASSERT_EQUALS(aDotB, *conflict);
+
+        // insert "a.b.c", conflicts with "a.b"
+        FieldRef superSet;
+        superSet.parse("a.b.c");
+        ASSERT_FALSE(fieldSet.insert(&superSet, &conflict));
+        ASSERT_EQUALS(aDotB, *conflict);
+    }
+
+    TEST(EmptySet, EmptyField) {
+        // Old data may have empty field names. We test that we can catch conflicts if we try
+        // to insert an empty field twice.
+        FieldRefSet fieldSet;
+        FieldRef empty;
+        const FieldRef* conflict;
+        ASSERT_TRUE(fieldSet.insert(&empty, &conflict));
+        ASSERT_EQUALS(static_cast<const FieldRef*>(NULL), conflict);
+
+        ASSERT_FALSE(fieldSet.insert(&empty, &conflict));
+        ASSERT_EQUALS(empty, *conflict);
+    }
+
+    TEST(NotEmptySet, Normal) {
+        // insert "b.c" and "b.e"
+        FieldRefSet fieldSet;
+        FieldRef bDotC;
+        bDotC.parse("b.c");
+        FieldRef bDotE;
+        bDotE.parse("b.e");
+        const FieldRef* conflict;
+        ASSERT_TRUE(fieldSet.insert(&bDotC, &conflict));
+        ASSERT_EQUALS(static_cast<const FieldRef*>(NULL), conflict);
+        ASSERT_TRUE(fieldSet.insert(&bDotE, &conflict));
+        ASSERT_EQUALS(static_cast<const FieldRef*>(NULL), conflict);
+
+        // insert "a" before, OK
+        FieldRef aSimple;
+        aSimple.parse("a");
+        ASSERT_TRUE(fieldSet.insert(&aSimple, &conflict));
+        ASSERT_EQUALS(static_cast<const FieldRef*>(NULL), conflict);
+
+        // insert "b.d" in the middle, OK
+        FieldRef bDotD;
+        bDotD.parse("b.d");
+        ASSERT_TRUE(fieldSet.insert(&bDotD, &conflict));
+        ASSERT_EQUALS(static_cast<const FieldRef*>(NULL), conflict);
+
+        // insert "c" after, OK
+        FieldRef cSimple;
+        cSimple.parse("c");
+        ASSERT_TRUE(fieldSet.insert(&cSimple, &conflict));
+        ASSERT_EQUALS(static_cast<const FieldRef*>(NULL), conflict);
+    }
+
+    TEST(NotEmpty, Conflict) {
+       // insert "b.c" and "b.e"
+        FieldRefSet fieldSet;
+        FieldRef bDotC;
+        bDotC.parse("b.c");
+        FieldRef bDotE;
+        bDotE.parse("b.e");
+        const FieldRef* conflict;
+        ASSERT_TRUE(fieldSet.insert(&bDotC, &conflict));
+        ASSERT_EQUALS(static_cast<const FieldRef*>(NULL), conflict);
+        ASSERT_TRUE(fieldSet.insert(&bDotE, &conflict));
+        ASSERT_EQUALS(static_cast<const FieldRef*>(NULL), conflict);
+
+        // insert "b" before, conflicts "b.c"
+        FieldRef bSimple;
+        bSimple.parse("b");
+        ASSERT_FALSE(fieldSet.insert(&bSimple, &conflict));
+        ASSERT_EQUALS(bDotC, *conflict);
+
+        // insert: "b.c.d" in the "middle", conflicts "b.c"
+        FieldRef bDotCDotD;
+        bDotCDotD.parse("b.c.d");
+        ASSERT_FALSE(fieldSet.insert(&bDotCDotD, &conflict));
+        ASSERT_EQUALS(bDotC, *conflict);
+
+        // insert: "b.e.f" at the end, conflicts "b.e"
+        FieldRef bDotEDotF;
+        bDotEDotF.parse("b.e.f");
+        ASSERT_FALSE(fieldSet.insert(&bDotEDotF, &conflict));
+        ASSERT_EQUALS(bDotE, *conflict);
+    }
+
+} // unnamed namespace
diff --git a/src/mongo/db/field_ref_test.cpp b/src/mongo/db/field_ref_test.cpp
index 007af16c103..b33cf44fbb4 100644
--- a/src/mongo/db/field_ref_test.cpp
+++ b/src/mongo/db/field_ref_test.cpp
@@ -139,42 +139,74 @@ namespace {
         ASSERT_EQUALS(fieldRef.numReplaced(), 1U);
     }
 
-    TEST(Prefix, Normal) {
-        FieldRef prefix;
-        FieldRef other;
+    TEST( Prefix, Normal ) {
+        FieldRef prefix, base;
+        base.parse( "a.b.c" );
 
-        // Positive case
         prefix.parse( "a.b" );
-        other.parse( "a.b.c" );
-        ASSERT( prefix.isPrefixOf( other ) );
+        ASSERT_TRUE( prefix.isPrefixOf( base ) );
+
         prefix.parse( "a" );
-        ASSERT( prefix.isPrefixOf( other ) );
+        ASSERT_TRUE( prefix.isPrefixOf( base ) );
+    }
+
+    TEST( Prefix, Dotted ) {
+        FieldRef prefix, base;
+        base.parse( "a.0.c" );
         prefix.parse( "a.0" );
-        other.parse( "a.0.c" );
-        ASSERT( prefix.isPrefixOf( other ) );
+        ASSERT_TRUE( prefix.isPrefixOf( base ) );
+    }
 
-        // All these tests are for a prefix of "a.b" in other
-        // Negative cases
+    TEST( Prefix, NoPrefixes ) {
+        FieldRef prefix, base;
         prefix.parse( "a.b" );
-        other.parse( "a.b" );
-        ASSERT( !prefix.isPrefixOf( other ) );
-        other.parse( "a" );
-        ASSERT( !prefix.isPrefixOf( other ) );
-        other.parse( "b" );
-        ASSERT( !prefix.isPrefixOf( other ) );
-        other.parse( "" );
-        ASSERT( !prefix.isPrefixOf( other ) );
+        base.parse( "a.b" );
+        ASSERT_FALSE( prefix.isPrefixOf( base ) );
+
+        base.parse( "a" );
+        ASSERT_FALSE( prefix.isPrefixOf( base ) );
+
+        base.parse( "b" );
+        ASSERT_FALSE( prefix.isPrefixOf( base ) );
+    }
 
-        // Change to no prefix, empty string, and other is "" also
-        prefix.parse( "" );
-        ASSERT( !prefix.isPrefixOf( other ) );
+    TEST( Prefix, EmptyBase ) {
+        FieldRef field, empty;
+        field.parse( "a" );
+        ASSERT_FALSE( field.isPrefixOf( empty ) );
+        ASSERT_FALSE( empty.isPrefixOf( field ) );
+        ASSERT_FALSE( empty.isPrefixOf( empty ) );
+    }
+
+    TEST( PrefixSize, Normal ) {
+        FieldRef fieldA, fieldB;
+        fieldA.parse( "a.b" );
+
+        fieldB.parse( "a" );
+        ASSERT_EQUALS( fieldA.commonPrefixSize( fieldB ), 1U );
+
+        fieldB.parse( "a.b" );
+        ASSERT_EQUALS( fieldA.commonPrefixSize( fieldB ), 2U );
+
+        fieldB.parse( "a.b.c" );
+        ASSERT_EQUALS( fieldA.commonPrefixSize( fieldB ), 2U );
+    }
 
-        // Change other to "a", leave prefix at ""
-        other.parse( "a" );
-        ASSERT( !prefix.isPrefixOf( other ) );
+    TEST( PrefixSize, NoCommonatility ) {
+        FieldRef fieldA, fieldB;
+        fieldA.parse( "a" );
+        fieldB.parse( "b" );
+        ASSERT_EQUALS( fieldA.commonPrefixSize( fieldB ), 0U );
     }
 
-    TEST(Equality, Simple1 ) {
+    TEST( PrefixSize, Empty ) {
+        FieldRef fieldA, empty;
+        fieldA.parse( "a" );
+        ASSERT_EQUALS( fieldA.commonPrefixSize( empty ), 0U );
+        ASSERT_EQUALS( empty.commonPrefixSize( fieldA ), 0U );
+    }
+
+    TEST( Equality, Simple1 ) {
         FieldRef a;
         a.parse( "a.b" );
         ASSERT( a.equalsDottedField( "a.b" ) );
@@ -183,7 +215,7 @@ namespace {
         ASSERT( !a.equalsDottedField( "a.b.c" ) );
     }
 
-    TEST(Equality, Simple2 ) {
+    TEST( Equality, Simple2 ) {
         FieldRef a;
         a.parse( "a" );
         ASSERT( !a.equalsDottedField( "a.b" ) );
@@ -192,6 +224,51 @@ namespace {
         ASSERT( !a.equalsDottedField( "a.b.c" ) );
     }
 
+    TEST( Comparison, BothEmpty ) {
+        FieldRef a;
+        ASSERT_TRUE( a == a );
+        ASSERT_FALSE( a != a );
+        ASSERT_FALSE( a < a );
+        ASSERT_TRUE( a <= a );
+        ASSERT_FALSE( a > a );
+        ASSERT_TRUE( a >= a );
+    }
+
+    TEST( Comparison, EqualInSize ) {
+        FieldRef a, b;
+        a.parse( "a.b.c" );
+        b.parse( "a.d.c" );
+        ASSERT_FALSE( a == b );
+        ASSERT_TRUE( a != b );
+        ASSERT_TRUE( a < b );
+        ASSERT_TRUE( a <= b );
+        ASSERT_FALSE( a > b );
+        ASSERT_FALSE( a >= b );
+    }
+
+    TEST( Comparison, NonEqual ) {
+        FieldRef a, b;
+        a.parse( "a.b.c" );
+        b.parse( "b.d" );
+        ASSERT_FALSE( a == b );
+        ASSERT_TRUE( a != b );
+        ASSERT_TRUE( a < b );
+        ASSERT_TRUE( a <= b );
+        ASSERT_FALSE( a > b );
+        ASSERT_FALSE( a >= b );
+    }
+
+    TEST( Comparison, MixedEmtpyAndNot ) {
+        FieldRef a, b;
+        a.parse( "a" );
+        ASSERT_FALSE( a == b );
+        ASSERT_TRUE( a != b );
+        ASSERT_FALSE( a < b );
+        ASSERT_FALSE( a <= b );
+        ASSERT_TRUE( a > b );
+        ASSERT_TRUE( a >= b );
+    }
+
     TEST( DottedField, Simple1 ) {
         FieldRef a;
         a.parse( "a.b.c.d.e" );
@@ -205,4 +282,4 @@ namespace {
         ASSERT_EQUALS( "", a.dottedField(6) );
     }
 
-} // namespace mongo
+} // namespace
diff --git a/src/mongo/db/ops/update_driver.cpp b/src/mongo/db/ops/update_driver.cpp
index 08734b41774..3c38d4dc3ce 100644
--- a/src/mongo/db/ops/update_driver.cpp
+++ b/src/mongo/db/ops/update_driver.cpp
@@ -20,6 +20,7 @@
 #include "mongo/base/string_data.h"
 #include "mongo/bson/mutable/document.h"
 #include "mongo/db/field_ref.h"
+#include "mongo/db/field_ref_set.h"
 #include "mongo/db/ops/modifier_interface.h"
 #include "mongo/db/ops/modifier_object_replace.h"
 #include "mongo/db/ops/modifier_table.h"
@@ -145,7 +146,10 @@ namespace mongo {
         // TODO: assert that update() is called at most once in a !_multi case.
 
         mutablebson::Document doc(oldObj);
+        FieldRefSet targetFields;
 
+        // Ask each of the mods to type check whether they can operate over the current document
+        // and, if so, to change that document accordingly.
         for (vector<ModifierInterface*>::iterator it = _mods.begin(); it != _mods.end(); ++it) {
             ModifierInterface::ExecInfo execInfo;
             Status status = (*it)->prepare(doc.root(), matchedField, &execInfo);
@@ -153,21 +157,33 @@ namespace mongo {
                 return status;
             }
 
-            // TODO: gather the fields that each mod is interested on and check for conflicts.
-            // for (int i = 0; i < ModifierInterface::ExecInfo::MAX_NUM_FIELDS; i++) {
-            //     if (execInfo.fieldRef[i] == 0) {
-            //         break;
-            //     }
-            // }
+            // Gather which fields this mod is interested on and whether these fields were
+            // "taken" by previous mods.  Note that not all mods are multi-field mods. When we
+            // see an empty field, we may stop looking for others.
+            for (int i = 0; i < ModifierInterface::ExecInfo::MAX_NUM_FIELDS; i++) {
+                if (execInfo.fieldRef[i] == 0) {
+                    break;
+                }
+
+                const FieldRef* other;
+                if (!targetFields.insert(execInfo.fieldRef[i], &other)) {
+                    return Status(ErrorCodes::ConflictingUpdateOperators,
+                                  mongoutils::str::stream()
+                                      << "Cannot update '" << other->dottedField()
+                                      << "' and '" << execInfo.fieldRef[i]->dottedField()
+                                      << "' at the same time");
+                }
+            }
 
             if (!execInfo.noOp) {
-                status = (*it)->apply();
+                Status status = (*it)->apply();
                 if (!status.isOK()) {
                     return status;
                 }
             }
         }
 
+        // If we require a replication oplog entry for this update, go ahead and generate one.
         if (_logOp && logOpRec) {
             mutablebson::Document logDoc;
             for (vector<ModifierInterface*>::iterator it = _mods.begin(); it != _mods.end(); ++it) {