SERVER-28770 Create PullNode

To support PullNode, this patch adds a CopyableMatchExpression class,
which allows it to store a MatchExpression but still be copyable with
the default copy constructor.

This patch also factors out the viability check in PopNode so that
PullNode can use it as well.

10 files changed, 1671 insertions, 43 deletions

diff --git a/jstests/core/update_arrayFilters.js b/jstests/core/update_arrayFilters.js
index ccd636c9809..0081ea66050 100644
--- a/jstests/core/update_arrayFilters.js
+++ b/jstests/core/update_arrayFilters.js
@@ -440,23 +440,16 @@
                "update failed for a reason other than using array updates with $pullAll");
 
     // $pull.
-    // TODO SERVER-28770: $pull should use the new update implementation.
     coll.drop();
+    assert.writeOK(coll.insert({_id: 0, a: [[0, 1], [1, 2]]}));
     if (db.getMongo().writeMode() === "commands") {
-        res = coll.update({_id: 0}, {$pull: {"a.$[i]": {$in: [0]}}}, {arrayFilters: [{i: 0}]});
-        assert.writeErrorWithCode(res, ErrorCodes.InvalidOptions);
-        assert.neq(
-            -1,
-            res.getWriteError().errmsg.indexOf("Cannot use array filters with modifier $pull"),
-            "update failed for a reason other than using array filters with $pull");
+        assert.writeOK(coll.update({_id: 0}, {$pull: {"a.$[i]": 1}}, {arrayFilters: [{i: 2}]}));
+        assert.eq({_id: 0, a: [[0, 1], [2]]}, coll.findOne());
     }
-    assert.writeOK(coll.insert({_id: 0, a: [[0]]}));
-    res = coll.update({_id: 0}, {$pull: {"a.$[]": {$in: [0]}}});
-    assert.writeErrorWithCode(res, 16837);
-    assert.neq(-1,
-               res.getWriteError().errmsg.indexOf(
-                   "cannot use the part (a of a.$[]) to traverse the element ({a: [ [ 0.0 ] ]})"),
-               "update failed for a reason other than using array updates with $pull");
+    assert.writeOK(coll.remove({}));
+    assert.writeOK(coll.insert({_id: 0, a: [[0, 1], [1, 2]]}));
+    assert.writeOK(coll.update({_id: 0}, {$pull: {"a.$[]": 1}}));
+    assert.eq({_id: 0, a: [[0], [2]]}, coll.findOne());
 
     // $pushAll.
     // TODO SERVER-28772: $pushAll should use the new update implementation.
diff --git a/src/mongo/db/matcher/copyable_match_expression.h b/src/mongo/db/matcher/copyable_match_expression.h
new file mode 100644
index 00000000000..f08bf2dc202
--- /dev/null
+++ b/src/mongo/db/matcher/copyable_match_expression.h
@@ -0,0 +1,99 @@
+/**
+ * Copyright (C) 2017 MongoDB 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/>.
+ *
+ * As a special exception, the copyright holders give permission to link the
+ * code of portions of this program with the OpenSSL library under certain
+ * conditions as described in each individual source file and distribute
+ * linked combinations including the program with the OpenSSL library. You
+ * must comply with the GNU Affero General Public License in all respects
+ * for all of the code used other than as permitted herein. If you modify
+ * file(s) with this exception, you may extend this exception to your
+ * version of the file(s), but you are not obligated to do so. If you do not
+ * wish to do so, delete this exception statement from your version. If you
+ * delete this exception statement from all source files in the program,
+ * then also delete it in the license file.
+ */
+
+#pragma once
+
+#include "mongo/db/matcher/expression_parser.h"
+
+namespace mongo {
+
+/**
+ * Classes that must be copyable but want to own a MatchExpression (which deletes its copy
+ * constructor) can instead store a CopyableMatchExpression.
+ *
+ * CopyableMatchExpression stores the BSON expression used to created its MatchExpression, so that
+ * when we want to copy it, we can create a new MatchExpression that is identical to the old one. We
+ * only actually perform this operation, however, when the client wants to mutate the
+ * MatchExpression (by calling setCollator()). The rest of the time, copies of a
+ * CopyableMatchExpression all point to the same immutable MatchExpression. This pattern is similar
+ * to copy-on-write semantics.
+ */
+class CopyableMatchExpression {
+public:
+    /**
+     * Parse 'matchAST' to create a new MatchExpression, throwing a UserException if we encounter an
+     * error.
+     */
+    CopyableMatchExpression(BSONObj matchAST,
+                            std::unique_ptr<const ExtensionsCallback> extensionsCallback,
+                            const CollatorInterface* collator)
+        : _matchAST(matchAST), _extensionsCallback(std::move(extensionsCallback)) {
+        StatusWithMatchExpression parseResult =
+            MatchExpressionParser::parse(_matchAST, *_extensionsCallback, collator);
+        uassertStatusOK(parseResult.getStatus());
+        _matchExpr = std::move(parseResult.getValue());
+    }
+
+    /**
+     * Semantically, this behaves as if the client called setCollator() on the underlying
+     * MatchExpression (which is impossible, because it's const).
+     *
+     * Behind the scenes, it actually makes a new MatchExpression with the new collator. That way,
+     * if there other CopyableMatchExpression objects referencing this MatchExpression, they don't
+     * see the change in collator.
+     */
+    void setCollator(const CollatorInterface* collator) {
+        StatusWithMatchExpression parseResult =
+            MatchExpressionParser::parse(_matchAST, *_extensionsCallback, collator);
+        invariantOK(parseResult.getStatus());
+        _matchExpr = std::move(parseResult.getValue());
+    }
+
+    /**
+     * Overload * so that CopyableMatchExpression can be dereferenced as if it were a pointer to the
+     * underlying MatchExpression.
+     */
+    const MatchExpression& operator*() {
+        return *_matchExpr;
+    }
+
+    /**
+     * Overload -> so that CopyableMatchExpression can be dereferenced as if it were a pointer to
+     * the underlying MatchExpression.
+     */
+    const MatchExpression* operator->() {
+        return &(*_matchExpr);
+    }
+
+private:
+    BSONObj _matchAST;
+    std::shared_ptr<const ExtensionsCallback> _extensionsCallback;
+    std::shared_ptr<const MatchExpression> _matchExpr;
+};
+
+}  // namespace mongo
diff --git a/src/mongo/db/update/SConscript b/src/mongo/db/update/SConscript
index c1496809662..13403b00975 100644
--- a/src/mongo/db/update/SConscript
+++ b/src/mongo/db/update/SConscript
@@ -62,11 +62,13 @@ env.Library(
         'modifier_table.cpp',
         'path_creating_node.cpp',
         'pop_node.cpp',
+        'pull_node.cpp',
         'rename_node.cpp',
         'set_node.cpp',
         'unset_node.cpp',
         'update_array_node.cpp',
         'update_internal_node.cpp',
+        'update_leaf_node.cpp',
         'update_node.cpp',
         'update_object_node.cpp',
     ],
@@ -85,6 +87,7 @@ env.CppUnitTest(
         'arithmetic_node_test.cpp',
         'bit_node_test.cpp',
         'pop_node_test.cpp',
+        'pull_node_test.cpp',
         'rename_node_test.cpp',
         'set_node_test.cpp',
         'unset_node_test.cpp',
diff --git a/src/mongo/db/update/modifier_table.cpp b/src/mongo/db/update/modifier_table.cpp
index 73ea732c4aa..e0028d8b5a2 100644
--- a/src/mongo/db/update/modifier_table.cpp
+++ b/src/mongo/db/update/modifier_table.cpp
@@ -51,6 +51,7 @@
 #include "mongo/db/update/bit_node.h"
 #include "mongo/db/update/conflict_placeholder_node.h"
 #include "mongo/db/update/pop_node.h"
+#include "mongo/db/update/pull_node.h"
 #include "mongo/db/update/rename_node.h"
 #include "mongo/db/update/set_node.h"
 #include "mongo/db/update/unset_node.h"
@@ -198,6 +199,8 @@ std::unique_ptr<UpdateLeafNode> makeUpdateLeafNode(ModifierType modType) {
             return stdx::make_unique<ArithmeticNode>(ArithmeticNode::ArithmeticOp::kMultiply);
         case MOD_POP:
             return stdx::make_unique<PopNode>();
+        case MOD_PULL:
+            return stdx::make_unique<PullNode>();
         case MOD_RENAME:
             return stdx::make_unique<RenameNode>();
         case MOD_SET:
diff --git a/src/mongo/db/update/pop_node.cpp b/src/mongo/db/update/pop_node.cpp
index a5a94ba3005..4b3f6273db3 100644
--- a/src/mongo/db/update/pop_node.cpp
+++ b/src/mongo/db/update/pop_node.cpp
@@ -31,8 +31,6 @@
 #include "mongo/db/update/pop_node.h"
 
 #include "mongo/db/matcher/expression_parser.h"
-#include "mongo/db/update/path_support.h"
-#include "mongo/util/stringutils.h"
 
 namespace mongo {
 
@@ -70,33 +68,13 @@ void PopNode::apply(mutablebson::Element element,
     }
 
     if (!pathToCreate->empty()) {
-        // There were path components which we could not traverse. If 'element' is a nested object
-        // which does not contain 'pathToCreate', then this is a no-op (e.g. {$pop: {"a.b.c": 1}}
-        // for document {a: {b: {}}}).
-        //
-        // If the element is an array, but the numeric path does not exist, then this is also a
-        // no-op (e.g. {$pop: {"a.2.b": 1}} for document {a: [{b: 0}, {b: 1}]}).
-        //
-        // Otherwise, this the path contains a blocking leaf or array element, which is an error.
-        if (element.getType() == BSONType::Object) {
-            *noop = true;
-            return;
-        }
-
-        if (element.getType() == BSONType::Array &&
-            parseUnsignedBase10Integer(pathToCreate->getPart(0))) {
-            *noop = true;
-            return;
-        }
-
-        uasserted(ErrorCodes::PathNotViable,
-                  str::stream() << "Cannot use the part (" << pathToCreate->getPart(0) << ") of ("
-                                << pathTaken->dottedField()
-                                << "."
-                                << pathToCreate->dottedField()
-                                << ") to traverse the element ({"
-                                << element.toString()
-                                << "})");
+        // There were path components we could not traverse. We treat this as a no-op, unless it
+        // would have been impossible to create those elements, which we check with
+        // checkViability().
+        UpdateLeafNode::checkViability(element, *pathToCreate, *pathTaken);
+
+        *noop = true;
+        return;
     }
 
     invariant(!pathTaken->empty());
diff --git a/src/mongo/db/update/pull_node.cpp b/src/mongo/db/update/pull_node.cpp
new file mode 100644
index 00000000000..45052c0c0f9
--- /dev/null
+++ b/src/mongo/db/update/pull_node.cpp
@@ -0,0 +1,214 @@
+/**
+ * Copyright (C) 2017 MongoDB 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/>.
+ *
+ * As a special exception, the copyright holders give permission to link the
+ * code of portions of this program with the OpenSSL library under certain
+ * conditions as described in each individual source file and distribute
+ * linked combinations including the program with the OpenSSL library. You
+ * must comply with the GNU Affero General Public License in all respects
+ * for all of the code used other than as permitted herein. If you modify
+ * file(s) with this exception, you may extend this exception to your
+ * version of the file(s), but you are not obligated to do so. If you do not
+ * wish to do so, delete this exception statement from your version. If you
+ * delete this exception statement from all source files in the program,
+ * then also delete it in the license file.
+ */
+
+#include "mongo/platform/basic.h"
+
+#include "mongo/db/update/pull_node.h"
+
+#include "mongo/db/matcher/copyable_match_expression.h"
+#include "mongo/db/matcher/extensions_callback_disallow_extensions.h"
+#include "mongo/db/query/collation/collator_interface.h"
+
+namespace mongo {
+
+/**
+ * The ObjectMatcher is used when the $pull condition is specified as an object and the first field
+ * of that object is not an operator (like $gt).
+ */
+class PullNode::ObjectMatcher : public PullNode::ElementMatcher {
+public:
+    ObjectMatcher(BSONObj matchCondition, const CollatorInterface* collator)
+        : _matchExpr(
+              matchCondition, stdx::make_unique<ExtensionsCallbackDisallowExtensions>(), collator) {
+    }
+
+    std::unique_ptr<ElementMatcher> clone() const final {
+        return stdx::make_unique<ObjectMatcher>(*this);
+    }
+
+    bool match(mutablebson::ConstElement element) final {
+        if (element.getType() == mongo::Object) {
+            return _matchExpr->matchesBSON(element.getValueObject());
+        } else {
+            return false;
+        }
+    }
+
+    void setCollator(const CollatorInterface* collator) final {
+        _matchExpr.setCollator(collator);
+    }
+
+private:
+    CopyableMatchExpression _matchExpr;
+};
+
+/**
+ * The WrappedObjectMatcher is used when the condition is a regex or an object with an operator as
+ * its first field (e.g., {$gt: ...}). It is possible that the element we want to compare is not an
+ * object, so we wrap it in an object before comparing it. We also wrap the MatchExpression in an
+ * empty object so that we are comparing the MatchCondition and the array element at the same level.
+ * This hack allows us to use a MatchExpression to check a BSONElement.
+ */
+class PullNode::WrappedObjectMatcher : public PullNode::ElementMatcher {
+public:
+    WrappedObjectMatcher(BSONElement matchCondition, const CollatorInterface* collator)
+        : _matchExpr(matchCondition.wrap(""),
+                     stdx::make_unique<ExtensionsCallbackDisallowExtensions>(),
+                     collator) {}
+
+    std::unique_ptr<ElementMatcher> clone() const final {
+        return stdx::make_unique<WrappedObjectMatcher>(*this);
+    }
+
+    bool match(mutablebson::ConstElement element) final {
+        BSONObj candidate = element.getValue().wrap("");
+        return _matchExpr->matchesBSON(candidate);
+    }
+
+    void setCollator(const CollatorInterface* collator) final {
+        _matchExpr.setCollator(collator);
+    }
+
+private:
+    CopyableMatchExpression _matchExpr;
+};
+
+/**
+ * The EqualityMatcher is used when the condition is a primitive value or an array value. We require
+ * an exact match.
+ */
+class PullNode::EqualityMatcher : public PullNode::ElementMatcher {
+public:
+    EqualityMatcher(BSONElement modExpr, const CollatorInterface* collator)
+        : _modExpr(modExpr), _collator(collator) {}
+
+    std::unique_ptr<ElementMatcher> clone() const final {
+        return stdx::make_unique<EqualityMatcher>(*this);
+    }
+
+    bool match(mutablebson::ConstElement element) final {
+        return (element.compareWithBSONElement(_modExpr, _collator, false) == 0);
+    }
+
+    void setCollator(const CollatorInterface* collator) final {
+        _collator = collator;
+    }
+
+private:
+    BSONElement _modExpr;
+    const CollatorInterface* _collator;
+};
+
+Status PullNode::init(BSONElement modExpr, const CollatorInterface* collator) {
+    invariant(modExpr.ok());
+
+    try {
+        if (modExpr.type() == mongo::Object &&
+            modExpr.embeddedObject().firstElement().getGtLtOp(-1) == -1) {
+            _matcher = stdx::make_unique<ObjectMatcher>(modExpr.embeddedObject(), collator);
+        } else if (modExpr.type() == mongo::Object || modExpr.type() == mongo::RegEx) {
+            _matcher = stdx::make_unique<WrappedObjectMatcher>(modExpr, collator);
+        } else {
+            _matcher = stdx::make_unique<EqualityMatcher>(modExpr, collator);
+        }
+    } catch (UserException& exception) {
+        return exception.toStatus();
+    }
+
+    return Status::OK();
+}
+
+void PullNode::apply(mutablebson::Element element,
+                     FieldRef* pathToCreate,
+                     FieldRef* pathTaken,
+                     StringData matchedField,
+                     bool fromReplication,
+                     bool validateForStorage,
+                     const FieldRefSet& immutablePaths,
+                     const UpdateIndexData* indexData,
+                     LogBuilder* logBuilder,
+                     bool* indexesAffected,
+                     bool* noop) const {
+    *indexesAffected = false;
+    *noop = false;
+
+    if (!pathToCreate->empty()) {
+        // There were path components we could not traverse. We treat this as a no-op, unless it
+        // would have been impossible to create those elements, which we check with
+        // checkViability().
+        UpdateLeafNode::checkViability(element, *pathToCreate, *pathTaken);
+
+        *noop = true;
+        return;
+    }
+
+    // This operation only applies to arrays
+    uassert(ErrorCodes::BadValue,
+            "Cannot apply $pull to a non-array value",
+            element.getType() == mongo::Array);
+
+    size_t numRemoved = 0;
+    auto cursor = element.leftChild();
+    while (cursor.ok()) {
+        // Make sure to get the next array element now, because if we remove the 'cursor' element,
+        // the rightSibling pointer will be invalidated.
+        auto nextElement = cursor.rightSibling();
+        if (_matcher->match(cursor)) {
+            invariantOK(cursor.remove());
+            numRemoved++;
+        }
+        cursor = nextElement;
+    }
+
+    if (numRemoved == 0) {
+        *noop = true;
+        return;  // Skip the index check and logging steps.
+    }
+
+    // Determine if indexes are affected.
+    if (indexData && indexData->mightBeIndexed(pathTaken->dottedField())) {
+        *indexesAffected = true;
+    }
+
+    if (logBuilder) {
+        auto& doc = logBuilder->getDocument();
+        auto logElement = doc.makeElementArray(pathTaken->dottedField());
+
+        for (auto cursor = element.leftChild(); cursor.ok(); cursor = cursor.rightSibling()) {
+            dassert(cursor.hasValue());
+
+            auto copy = doc.makeElementWithNewFieldName(StringData(), cursor.getValue());
+            uassert(ErrorCodes::InternalError, "could not create copy element", copy.ok());
+            uassertStatusOK(logElement.pushBack(copy));
+        }
+
+        uassertStatusOK(logBuilder->addToSets(logElement));
+    }
+}
+
+}  // namespace mongo
diff --git a/src/mongo/db/update/pull_node.h b/src/mongo/db/update/pull_node.h
new file mode 100644
index 00000000000..981b99c600e
--- /dev/null
+++ b/src/mongo/db/update/pull_node.h
@@ -0,0 +1,82 @@
+/**
+ * Copyright (C) 2017 MongoDB 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/>.
+ *
+ * As a special exception, the copyright holders give permission to link the
+ * code of portions of this program with the OpenSSL library under certain
+ * conditions as described in each individual source file and distribute
+ * linked combinations including the program with the OpenSSL library. You
+ * must comply with the GNU Affero General Public License in all respects
+ * for all of the code used other than as permitted herein. If you modify
+ * file(s) with this exception, you may extend this exception to your
+ * version of the file(s), but you are not obligated to do so. If you do not
+ * wish to do so, delete this exception statement from your version. If you
+ * delete this exception statement from all source files in the program,
+ * then also delete it in the license file.
+ */
+
+#pragma once
+
+#include "mongo/base/clonable_ptr.h"
+#include "mongo/db/update/update_leaf_node.h"
+#include "mongo/stdx/memory.h"
+
+namespace mongo {
+
+class PullNode final : public UpdateLeafNode {
+public:
+    Status init(BSONElement modExpr, const CollatorInterface* collator) final;
+
+    void apply(mutablebson::Element element,
+               FieldRef* pathToCreate,
+               FieldRef* pathTaken,
+               StringData matchedField,
+               bool fromReplication,
+               bool validateForStorage,
+               const FieldRefSet& immutablePaths,
+               const UpdateIndexData* indexData,
+               LogBuilder* logBuilder,
+               bool* indexesAffected,
+               bool* noop) const final;
+
+    std::unique_ptr<UpdateNode> clone() const final {
+        return stdx::make_unique<PullNode>(*this);
+    }
+
+    void setCollator(const CollatorInterface* collator) final {
+        _matcher->setCollator(collator);
+    }
+
+private:
+    /**
+     * PullNode::apply() uses an ElementMatcher to determine which array elements meet the $pull
+     * condition. The different subclasses of ElementMatcher implement the different kinds of checks
+     * that can be used for a $pull operation.
+     */
+    class ElementMatcher {
+    public:
+        virtual ~ElementMatcher() = default;
+        virtual std::unique_ptr<ElementMatcher> clone() const = 0;
+        virtual bool match(mutablebson::ConstElement element) = 0;
+        virtual void setCollator(const CollatorInterface* collator) = 0;
+    };
+
+    class ObjectMatcher;
+    class WrappedObjectMatcher;
+    class EqualityMatcher;
+
+    clonable_ptr<ElementMatcher> _matcher;
+};
+
+}  // namespace mongo
diff --git a/src/mongo/db/update/pull_node_test.cpp b/src/mongo/db/update/pull_node_test.cpp
new file mode 100644
index 00000000000..cdc67f74d43
--- /dev/null
+++ b/src/mongo/db/update/pull_node_test.cpp
@@ -0,0 +1,1179 @@
+/**
+ * Copyright (C) 2017 MongoDB 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/>.
+ *
+ * As a special exception, the copyright holders give permission to link the
+ * code of portions of this program with the OpenSSL library under certain
+ * conditions as described in each individual source file and distribute
+ * linked combinations including the program with the OpenSSL library. You
+ * must comply with the GNU Affero General Public License in all respects
+ * for all of the code used other than as permitted herein. If you modify
+ * file(s) with this exception, you may extend this exception to your
+ * version of the file(s), but you are not obligated to do so. If you do not
+ * wish to do so, delete this exception statement from your version. If you
+ * delete this exception statement from all source files in the program,
+ * then also delete it in the license file.
+ */
+
+#include "mongo/platform/basic.h"
+
+#include "mongo/db/update/pull_node.h"
+
+#include "mongo/bson/mutable/algorithm.h"
+#include "mongo/bson/mutable/mutable_bson_test_utils.h"
+#include "mongo/db/json.h"
+#include "mongo/db/query/collation/collator_interface_mock.h"
+#include "mongo/unittest/death_test.h"
+#include "mongo/unittest/unittest.h"
+
+namespace {
+
+using namespace mongo;
+using mongo::mutablebson::Document;
+using mongo::mutablebson::Element;
+using mongo::mutablebson::countChildren;
+
+TEST(PullNodeTest, InitWithBadMatchExpressionFails) {
+    auto update = fromjson("{$pull: {a: {b: {$foo: 1}}}}");
+    const CollatorInterface* collator = nullptr;
+    PullNode node;
+    auto status = node.init(update["$pull"]["a"], collator);
+    ASSERT_NOT_OK(status);
+    ASSERT_EQUALS(ErrorCodes::BadValue, status);
+}
+
+TEST(PullNodeTest, InitWithBadTopLevelOperatorFails) {
+    auto update = fromjson("{$pull: {a: {$foo: 1}}}");
+    const CollatorInterface* collator = nullptr;
+    PullNode node;
+    auto status = node.init(update["$pull"]["a"], collator);
+    ASSERT_NOT_OK(status);
+    ASSERT_EQUALS(ErrorCodes::BadValue, status);
+}
+
+TEST(PullNodeTest, TargetNotFound) {
+    auto update = fromjson("{$pull : {a: {$lt: 1}}}");
+    const CollatorInterface* collator = nullptr;
+    PullNode node;
+    ASSERT_OK(node.init(update["$pull"]["a"], collator));
+
+    Document doc(fromjson("{}"));
+    FieldRef pathToCreate("a");
+    FieldRef pathTaken("");
+    StringData matchedField;
+    auto fromReplication = false;
+    auto validateForStorage = true;
+    FieldRefSet immutablePaths;
+    UpdateIndexData indexData;
+    indexData.addPath("a");
+    Document logDoc;
+    LogBuilder logBuilder(logDoc.root());
+    auto indexesAffected = false;
+    auto noop = false;
+    node.apply(doc.root(),
+               &pathToCreate,
+               &pathTaken,
+               matchedField,
+               fromReplication,
+               validateForStorage,
+               immutablePaths,
+               &indexData,
+               &logBuilder,
+               &indexesAffected,
+               &noop);
+    ASSERT_TRUE(noop);
+    ASSERT_FALSE(indexesAffected);
+    ASSERT_EQUALS(fromjson("{}"), doc);
+    ASSERT_TRUE(doc.isInPlaceModeEnabled());
+    ASSERT_EQUALS(fromjson("{}"), logDoc);
+}
+
+TEST(PullNodeTest, ApplyToStringFails) {
+    auto update = fromjson("{$pull : {a: {$lt: 1}}}");
+    const CollatorInterface* collator = nullptr;
+    PullNode node;
+    ASSERT_OK(node.init(update["$pull"]["a"], collator));
+
+    Document doc(fromjson("{a: 'foo'}"));
+    FieldRef pathToCreate("");
+    FieldRef pathTaken("a");
+    StringData matchedField;
+    auto fromReplication = false;
+    auto validateForStorage = true;
+    FieldRefSet immutablePaths;
+    UpdateIndexData indexData;
+    indexData.addPath("a");
+    Document logDoc;
+    LogBuilder logBuilder(logDoc.root());
+    auto indexesAffected = false;
+    auto noop = false;
+    ASSERT_THROWS_CODE_AND_WHAT(node.apply(doc.root()["a"],
+                                           &pathToCreate,
+                                           &pathTaken,
+                                           matchedField,
+                                           fromReplication,
+                                           validateForStorage,
+                                           immutablePaths,
+                                           &indexData,
+                                           &logBuilder,
+                                           &indexesAffected,
+                                           &noop),
+                                UserException,
+                                ErrorCodes::BadValue,
+                                "Cannot apply $pull to a non-array value");
+}
+
+TEST(PullNodeTest, ApplyToObjectFails) {
+    auto update = fromjson("{$pull : {a: {$lt: 1}}}");
+    const CollatorInterface* collator = nullptr;
+    PullNode node;
+    ASSERT_OK(node.init(update["$pull"]["a"], collator));
+
+    Document doc(fromjson("{a: {foo: 'bar'}}"));
+    FieldRef pathToCreate("");
+    FieldRef pathTaken("a");
+    StringData matchedField;
+    auto fromReplication = false;
+    auto validateForStorage = true;
+    FieldRefSet immutablePaths;
+    UpdateIndexData indexData;
+    indexData.addPath("a");
+    Document logDoc;
+    LogBuilder logBuilder(logDoc.root());
+    auto indexesAffected = false;
+    auto noop = false;
+    ASSERT_THROWS_CODE_AND_WHAT(node.apply(doc.root()["a"],
+                                           &pathToCreate,
+                                           &pathTaken,
+                                           matchedField,
+                                           fromReplication,
+                                           validateForStorage,
+                                           immutablePaths,
+                                           &indexData,
+                                           &logBuilder,
+                                           &indexesAffected,
+                                           &noop),
+                                UserException,
+                                ErrorCodes::BadValue,
+                                "Cannot apply $pull to a non-array value");
+}
+
+TEST(PullNodeTest, ApplyToNonViablePathFails) {
+    auto update = fromjson("{$pull : {'a.b': {$lt: 1}}}");
+    const CollatorInterface* collator = nullptr;
+    PullNode node;
+    ASSERT_OK(node.init(update["$pull"]["a.b"], collator));
+
+    Document doc(fromjson("{a: 1}"));
+    FieldRef pathToCreate("b");
+    FieldRef pathTaken("a");
+    StringData matchedField;
+    auto fromReplication = false;
+    auto validateForStorage = true;
+    FieldRefSet immutablePaths;
+    UpdateIndexData indexData;
+    indexData.addPath("a");
+    Document logDoc;
+    LogBuilder logBuilder(logDoc.root());
+    auto indexesAffected = false;
+    auto noop = false;
+    ASSERT_THROWS_CODE_AND_WHAT(
+        node.apply(doc.root()["a"],
+                   &pathToCreate,
+                   &pathTaken,
+                   matchedField,
+                   fromReplication,
+                   validateForStorage,
+                   immutablePaths,
+                   &indexData,
+                   &logBuilder,
+                   &indexesAffected,
+                   &noop),
+        UserException,
+        ErrorCodes::PathNotViable,
+        "Cannot use the part (b) of (a.b) to traverse the element ({a: 1})");
+}
+
+TEST(PullNodeTest, ApplyToMissingElement) {
+    auto update = fromjson("{$pull: {'a.b.c.d': {$lt: 1}}}");
+    const CollatorInterface* collator = nullptr;
+    PullNode node;
+    ASSERT_OK(node.init(update["$pull"]["a.b.c.d"], collator));
+
+    Document doc(fromjson("{a: {b: {c: {}}}}"));
+    FieldRef pathToCreate("d");
+    FieldRef pathTaken("a.b.c");
+    StringData matchedField;
+    auto fromReplication = false;
+    auto validateForStorage = true;
+    FieldRefSet immutablePaths;
+    UpdateIndexData indexData;
+    indexData.addPath("a");
+    Document logDoc;
+    LogBuilder logBuilder(logDoc.root());
+    auto indexesAffected = false;
+    auto noop = false;
+    node.apply(doc.root()["a"]["b"]["c"],
+               &pathToCreate,
+               &pathTaken,
+               matchedField,
+               fromReplication,
+               validateForStorage,
+               immutablePaths,
+               &indexData,
+               &logBuilder,
+               &indexesAffected,
+               &noop);
+    ASSERT_TRUE(noop);
+    ASSERT_FALSE(indexesAffected);
+    ASSERT_EQUALS(fromjson("{a: {b: {c: {}}}}"), doc);
+    ASSERT_TRUE(doc.isInPlaceModeEnabled());
+    ASSERT_EQUALS(fromjson("{}"), logDoc);
+}
+
+TEST(PullNodeTest, ApplyToEmptyArray) {
+    auto update = fromjson("{$pull : {a: {$lt: 1}}}");
+    const CollatorInterface* collator = nullptr;
+    PullNode node;
+    ASSERT_OK(node.init(update["$pull"]["a"], collator));
+
+    Document doc(fromjson("{a: []}"));
+    FieldRef pathToCreate("");
+    FieldRef pathTaken("a");
+    StringData matchedField;
+    auto fromReplication = false;
+    auto validateForStorage = true;
+    FieldRefSet immutablePaths;
+    UpdateIndexData indexData;
+    indexData.addPath("a");
+    Document logDoc;
+    LogBuilder logBuilder(logDoc.root());
+    auto indexesAffected = false;
+    auto noop = false;
+    node.apply(doc.root()["a"],
+               &pathToCreate,
+               &pathTaken,
+               matchedField,
+               fromReplication,
+               validateForStorage,
+               immutablePaths,
+               &indexData,
+               &logBuilder,
+               &indexesAffected,
+               &noop);
+    ASSERT_TRUE(noop);
+    ASSERT_FALSE(indexesAffected);
+    ASSERT_EQUALS(fromjson("{a: []}"), doc);
+    ASSERT_TRUE(doc.isInPlaceModeEnabled());
+    ASSERT_EQUALS(fromjson("{}"), logDoc);
+}
+
+TEST(PullNodeTest, ApplyToArrayMatchingNone) {
+    auto update = fromjson("{$pull : {a: {$lt: 1}}}");
+    const CollatorInterface* collator = nullptr;
+    PullNode node;
+    ASSERT_OK(node.init(update["$pull"]["a"], collator));
+
+    Document doc(fromjson("{a: [2, 3, 4, 5]}"));
+    FieldRef pathToCreate("");
+    FieldRef pathTaken("a");
+    StringData matchedField;
+    auto fromReplication = false;
+    auto validateForStorage = true;
+    FieldRefSet immutablePaths;
+    UpdateIndexData indexData;
+    indexData.addPath("a");
+    Document logDoc;
+    LogBuilder logBuilder(logDoc.root());
+    auto indexesAffected = false;
+    auto noop = false;
+    node.apply(doc.root()["a"],
+               &pathToCreate,
+               &pathTaken,
+               matchedField,
+               fromReplication,
+               validateForStorage,
+               immutablePaths,
+               &indexData,
+               &logBuilder,
+               &indexesAffected,
+               &noop);
+    ASSERT_TRUE(noop);
+    ASSERT_FALSE(indexesAffected);
+    ASSERT_EQUALS(fromjson("{a: [2, 3, 4, 5]}"), doc);
+    ASSERT_TRUE(doc.isInPlaceModeEnabled());
+    ASSERT_EQUALS(fromjson("{}"), logDoc);
+}
+
+TEST(PullNodeTest, ApplyToArrayMatchingOne) {
+    auto update = fromjson("{$pull : {a: {$lt: 1}}}");
+    const CollatorInterface* collator = nullptr;
+    PullNode node;
+    ASSERT_OK(node.init(update["$pull"]["a"], collator));
+
+    Document doc(fromjson("{a: [0, 1, 2, 3]}"));
+    FieldRef pathToCreate("");
+    FieldRef pathTaken("a");
+    StringData matchedField;
+    auto fromReplication = false;
+    auto validateForStorage = true;
+    FieldRefSet immutablePaths;
+    UpdateIndexData indexData;
+    indexData.addPath("a");
+    Document logDoc;
+    LogBuilder logBuilder(logDoc.root());
+    auto indexesAffected = false;
+    auto noop = false;
+    node.apply(doc.root()["a"],
+               &pathToCreate,
+               &pathTaken,
+               matchedField,
+               fromReplication,
+               validateForStorage,
+               immutablePaths,
+               &indexData,
+               &logBuilder,
+               &indexesAffected,
+               &noop);
+    ASSERT_FALSE(noop);
+    ASSERT_TRUE(indexesAffected);
+    ASSERT_EQUALS(fromjson("{a: [1, 2, 3]}"), doc);
+    ASSERT_FALSE(doc.isInPlaceModeEnabled());
+    ASSERT_EQUALS(fromjson("{$set: {a: [1, 2, 3]}}"), logDoc);
+}
+
+TEST(PullNodeTest, ApplyToArrayMatchingSeveral) {
+    auto update = fromjson("{$pull : {a: {$lt: 1}}}");
+    const CollatorInterface* collator = nullptr;
+    PullNode node;
+    ASSERT_OK(node.init(update["$pull"]["a"], collator));
+
+    Document doc(fromjson("{a: [0, 1, 0, 2, 0, 3, 0, 4, 0, 5]}"));
+    FieldRef pathToCreate("");
+    FieldRef pathTaken("a");
+    StringData matchedField;
+    auto fromReplication = false;
+    auto validateForStorage = true;
+    FieldRefSet immutablePaths;
+    UpdateIndexData indexData;
+    indexData.addPath("a");
+    Document logDoc;
+    LogBuilder logBuilder(logDoc.root());
+    auto indexesAffected = false;
+    auto noop = false;
+    node.apply(doc.root()["a"],
+               &pathToCreate,
+               &pathTaken,
+               matchedField,
+               fromReplication,
+               validateForStorage,
+               immutablePaths,
+               &indexData,
+               &logBuilder,
+               &indexesAffected,
+               &noop);
+    ASSERT_FALSE(noop);
+    ASSERT_TRUE(indexesAffected);
+    ASSERT_EQUALS(fromjson("{a: [1, 2, 3, 4, 5]}"), doc);
+    ASSERT_FALSE(doc.isInPlaceModeEnabled());
+    ASSERT_EQUALS(fromjson("{$set: {a: [1, 2, 3, 4, 5]}}"), logDoc);
+}
+
+TEST(PullNodeTest, ApplyToArrayMatchingAll) {
+    auto update = fromjson("{$pull : {a: {$lt: 1}}}");
+    const CollatorInterface* collator = nullptr;
+    PullNode node;
+    ASSERT_OK(node.init(update["$pull"]["a"], collator));
+
+    Document doc(fromjson("{a: [0, -1, -2, -3, -4, -5]}"));
+    FieldRef pathToCreate("");
+    FieldRef pathTaken("a");
+    StringData matchedField;
+    auto fromReplication = false;
+    auto validateForStorage = true;
+    FieldRefSet immutablePaths;
+    UpdateIndexData indexData;
+    indexData.addPath("a");
+    Document logDoc;
+    LogBuilder logBuilder(logDoc.root());
+    auto indexesAffected = false;
+    auto noop = false;
+    node.apply(doc.root()["a"],
+               &pathToCreate,
+               &pathTaken,
+               matchedField,
+               fromReplication,
+               validateForStorage,
+               immutablePaths,
+               &indexData,
+               &logBuilder,
+               &indexesAffected,
+               &noop);
+    ASSERT_FALSE(noop);
+    ASSERT_TRUE(indexesAffected);
+    ASSERT_EQUALS(fromjson("{a: []}"), doc);
+    ASSERT_FALSE(doc.isInPlaceModeEnabled());
+    ASSERT_EQUALS(fromjson("{$set: {a: []}}"), logDoc);
+}
+
+TEST(PullNodeTest, ApplyNoIndexDataNoLogBuilder) {
+    auto update = fromjson("{$pull : {a: {$lt: 1}}}");
+    const CollatorInterface* collator = nullptr;
+    PullNode node;
+    ASSERT_OK(node.init(update["$pull"]["a"], collator));
+
+    Document doc(fromjson("{a: [0, 1, 2, 3]}"));
+    FieldRef pathToCreate("");
+    FieldRef pathTaken("a");
+    StringData matchedField;
+    auto fromReplication = false;
+    auto validateForStorage = true;
+    FieldRefSet immutablePaths;
+    UpdateIndexData* indexData = nullptr;
+    LogBuilder* logBuilder = nullptr;
+    auto indexesAffected = false;
+    auto noop = false;
+    node.apply(doc.root()["a"],
+               &pathToCreate,
+               &pathTaken,
+               matchedField,
+               fromReplication,
+               validateForStorage,
+               immutablePaths,
+               indexData,
+               logBuilder,
+               &indexesAffected,
+               &noop);
+    ASSERT_FALSE(noop);
+    ASSERT_FALSE(indexesAffected);
+    ASSERT_EQUALS(fromjson("{a: [1, 2, 3]}"), doc);
+    ASSERT_FALSE(doc.isInPlaceModeEnabled());
+}
+
+TEST(PullNodeTest, ApplyWithCollation) {
+    // With the collation, this update will pull any string whose reverse is greater than the
+    // reverse of the "abc" string.
+    auto update = fromjson("{$pull : {a: {$gt: 'abc'}}}");
+    CollatorInterfaceMock collator(CollatorInterfaceMock::MockType::kReverseString);
+    PullNode node;
+    ASSERT_OK(node.init(update["$pull"]["a"], &collator));
+
+    Document doc(fromjson("{a: ['zaa', 'zcc', 'zbb', 'zee']}"));
+    FieldRef pathToCreate("");
+    FieldRef pathTaken("a");
+    StringData matchedField;
+    auto fromReplication = false;
+    auto validateForStorage = true;
+    FieldRefSet immutablePaths;
+    UpdateIndexData indexData;
+    indexData.addPath("a");
+    Document logDoc;
+    LogBuilder logBuilder(logDoc.root());
+    auto indexesAffected = false;
+    auto noop = false;
+    node.apply(doc.root()["a"],
+               &pathToCreate,
+               &pathTaken,
+               matchedField,
+               fromReplication,
+               validateForStorage,
+               immutablePaths,
+               &indexData,
+               &logBuilder,
+               &indexesAffected,
+               &noop);
+    ASSERT_FALSE(noop);
+    ASSERT_TRUE(indexesAffected);
+    ASSERT_EQUALS(fromjson("{a: ['zaa', 'zbb']}"), doc);
+    ASSERT_FALSE(doc.isInPlaceModeEnabled());
+    ASSERT_EQUALS(fromjson("{$set: {a: ['zaa', 'zbb']}}"), logDoc);
+}
+
+TEST(PullNodeTest, ApplyWithCollationDoesNotAffectNonStringMatches) {
+    auto update = fromjson("{$pull : {a: {$lt: 1}}}");
+    CollatorInterfaceMock collator(CollatorInterfaceMock::MockType::kAlwaysEqual);
+    PullNode node;
+    ASSERT_OK(node.init(update["$pull"]["a"], &collator));
+
+    Document doc(fromjson("{a: [2, 1, 0, -1, -2, -3]}"));
+    FieldRef pathToCreate("");
+    FieldRef pathTaken("a");
+    StringData matchedField;
+    auto fromReplication = false;
+    auto validateForStorage = true;
+    FieldRefSet immutablePaths;
+    UpdateIndexData indexData;
+    indexData.addPath("a");
+    Document logDoc;
+    LogBuilder logBuilder(logDoc.root());
+    auto indexesAffected = false;
+    auto noop = false;
+    node.apply(doc.root()["a"],
+               &pathToCreate,
+               &pathTaken,
+               matchedField,
+               fromReplication,
+               validateForStorage,
+               immutablePaths,
+               &indexData,
+               &logBuilder,
+               &indexesAffected,
+               &noop);
+    ASSERT_FALSE(noop);
+    ASSERT_TRUE(indexesAffected);
+    ASSERT_EQUALS(fromjson("{a: [2, 1]}"), doc);
+    ASSERT_FALSE(doc.isInPlaceModeEnabled());
+    ASSERT_EQUALS(fromjson("{$set: {a: [2, 1]}}"), logDoc);
+}
+
+TEST(PullNodeTest, ApplyWithCollationDoesNotAffectRegexMatches) {
+    auto update = fromjson("{$pull : {a: /a/}}");
+    CollatorInterfaceMock collator(CollatorInterfaceMock::MockType::kAlwaysEqual);
+    PullNode node;
+    ASSERT_OK(node.init(update["$pull"]["a"], &collator));
+
+    Document doc(fromjson("{a: ['b', 'a', 'aab', 'cb', 'bba']}"));
+    FieldRef pathToCreate("");
+    FieldRef pathTaken("a");
+    StringData matchedField;
+    auto fromReplication = false;
+    auto validateForStorage = true;
+    FieldRefSet immutablePaths;
+    UpdateIndexData indexData;
+    indexData.addPath("a");
+    Document logDoc;
+    LogBuilder logBuilder(logDoc.root());
+    auto indexesAffected = false;
+    auto noop = false;
+    node.apply(doc.root()["a"],
+               &pathToCreate,
+               &pathTaken,
+               matchedField,
+               fromReplication,
+               validateForStorage,
+               immutablePaths,
+               &indexData,
+               &logBuilder,
+               &indexesAffected,
+               &noop);
+    ASSERT_FALSE(noop);
+    ASSERT_TRUE(indexesAffected);
+    ASSERT_EQUALS(fromjson("{a: ['b', 'cb']}"), doc);
+    ASSERT_FALSE(doc.isInPlaceModeEnabled());
+    ASSERT_EQUALS(fromjson("{$set: {a: ['b', 'cb']}}"), logDoc);
+}
+
+TEST(PullNodeTest, ApplyStringLiteralMatchWithCollation) {
+    auto update = fromjson("{$pull : {a: 'c'}}");
+    CollatorInterfaceMock collator(CollatorInterfaceMock::MockType::kAlwaysEqual);
+    PullNode node;
+    ASSERT_OK(node.init(update["$pull"]["a"], &collator));
+
+    Document doc(fromjson("{a: ['b', 'a', 'aab', 'cb', 'bba']}"));
+    FieldRef pathToCreate("");
+    FieldRef pathTaken("a");
+    StringData matchedField;
+    auto fromReplication = false;
+    auto validateForStorage = true;
+    FieldRefSet immutablePaths;
+    UpdateIndexData indexData;
+    indexData.addPath("a");
+    Document logDoc;
+    LogBuilder logBuilder(logDoc.root());
+    auto indexesAffected = false;
+    auto noop = false;
+    node.apply(doc.root()["a"],
+               &pathToCreate,
+               &pathTaken,
+               matchedField,
+               fromReplication,
+               validateForStorage,
+               immutablePaths,
+               &indexData,
+               &logBuilder,
+               &indexesAffected,
+               &noop);
+    ASSERT_FALSE(noop);
+    ASSERT_TRUE(indexesAffected);
+    ASSERT_EQUALS(fromjson("{a: []}"), doc);
+    ASSERT_FALSE(doc.isInPlaceModeEnabled());
+    ASSERT_EQUALS(fromjson("{$set: {a: []}}"), logDoc);
+}
+
+TEST(PullNodeTest, ApplyCollationDoesNotAffectNumberLiteralMatches) {
+    auto update = fromjson("{$pull : {a: 99}}");
+    CollatorInterfaceMock collator(CollatorInterfaceMock::MockType::kAlwaysEqual);
+    PullNode node;
+    ASSERT_OK(node.init(update["$pull"]["a"], &collator));
+
+    Document doc(fromjson("{a: ['a', 99, 'b', 2, 'c', 99, 'd']}"));
+    FieldRef pathToCreate("");
+    FieldRef pathTaken("a");
+    StringData matchedField;
+    auto fromReplication = false;
+    auto validateForStorage = true;
+    FieldRefSet immutablePaths;
+    UpdateIndexData indexData;
+    indexData.addPath("a");
+    Document logDoc;
+    LogBuilder logBuilder(logDoc.root());
+    auto indexesAffected = false;
+    auto noop = false;
+    node.apply(doc.root()["a"],
+               &pathToCreate,
+               &pathTaken,
+               matchedField,
+               fromReplication,
+               validateForStorage,
+               immutablePaths,
+               &indexData,
+               &logBuilder,
+               &indexesAffected,
+               &noop);
+    ASSERT_FALSE(noop);
+    ASSERT_TRUE(indexesAffected);
+    ASSERT_EQUALS(fromjson("{a: ['a', 'b', 2, 'c', 'd']}"), doc);
+    ASSERT_FALSE(doc.isInPlaceModeEnabled());
+    ASSERT_EQUALS(fromjson("{$set: {a: ['a', 'b', 2, 'c', 'd']}}"), logDoc);
+}
+
+TEST(PullNodeTest, ApplyStringMatchAfterSetCollator) {
+    auto update = fromjson("{$pull : {a: 'c'}}");
+    PullNode node;
+    const CollatorInterface* collator = nullptr;
+    ASSERT_OK(node.init(update["$pull"]["a"], collator));
+
+    // First without a collator.
+    Document doc(fromjson("{ a : ['a', 'b', 'c', 'd'] }"));
+    FieldRef pathToCreate("");
+    FieldRef pathTaken("a");
+    StringData matchedField;
+    auto fromReplication = false;
+    auto validateForStorage = true;
+    FieldRefSet immutablePaths;
+    UpdateIndexData* indexData = nullptr;
+    LogBuilder* logBuilder = nullptr;
+    auto indexesAffected = false;
+    auto noop = false;
+    node.apply(doc.root()["a"],
+               &pathToCreate,
+               &pathTaken,
+               matchedField,
+               fromReplication,
+               validateForStorage,
+               immutablePaths,
+               indexData,
+               logBuilder,
+               &indexesAffected,
+               &noop);
+    ASSERT_FALSE(noop);
+    ASSERT_FALSE(indexesAffected);
+    ASSERT_EQUALS(fromjson("{a: ['a', 'b', 'd']}"), doc);
+    ASSERT_FALSE(doc.isInPlaceModeEnabled());
+
+    // Now with a collator.
+    CollatorInterfaceMock mockCollator(CollatorInterfaceMock::MockType::kAlwaysEqual);
+    node.setCollator(&mockCollator);
+    indexesAffected = false;
+    noop = false;
+    Document doc2(fromjson("{ a : ['a', 'b', 'c', 'd'] }"));
+    node.apply(doc2.root()["a"],
+               &pathToCreate,
+               &pathTaken,
+               matchedField,
+               fromReplication,
+               validateForStorage,
+               immutablePaths,
+               indexData,
+               logBuilder,
+               &indexesAffected,
+               &noop);
+    ASSERT_FALSE(noop);
+    ASSERT_FALSE(indexesAffected);
+    ASSERT_EQUALS(fromjson("{a: []}"), doc2);
+    ASSERT_FALSE(doc2.isInPlaceModeEnabled());
+}
+
+TEST(PullNodeTest, SetCollatorDoesNotAffectClone) {
+    auto update = fromjson("{$pull : {a: 'c'}}");
+    PullNode node;
+    const CollatorInterface* collator = nullptr;
+    ASSERT_OK(node.init(update["$pull"]["a"], collator));
+
+    auto cloneNode = node.clone();
+
+    CollatorInterfaceMock mockCollator(CollatorInterfaceMock::MockType::kAlwaysEqual);
+    node.setCollator(&mockCollator);
+
+    // The original node should now have collation.
+    Document doc(fromjson("{ a : ['a', 'b', 'c', 'd'] }"));
+    FieldRef pathToCreate("");
+    FieldRef pathTaken("a");
+    StringData matchedField;
+    auto fromReplication = false;
+    auto validateForStorage = true;
+    FieldRefSet immutablePaths;
+    UpdateIndexData* indexData = nullptr;
+    LogBuilder* logBuilder = nullptr;
+    auto indexesAffected = false;
+    auto noop = false;
+    node.apply(doc.root()["a"],
+               &pathToCreate,
+               &pathTaken,
+               matchedField,
+               fromReplication,
+               validateForStorage,
+               immutablePaths,
+               indexData,
+               logBuilder,
+               &indexesAffected,
+               &noop);
+    ASSERT_FALSE(noop);
+    ASSERT_FALSE(indexesAffected);
+    ASSERT_EQUALS(fromjson("{a: []}"), doc);
+    ASSERT_FALSE(doc.isInPlaceModeEnabled());
+
+    // The clone should have exact string matches (no collation).
+    indexesAffected = false;
+    noop = false;
+    Document doc2(fromjson("{ a : ['a', 'b', 'c', 'd'] }"));
+    cloneNode->apply(doc2.root()["a"],
+                     &pathToCreate,
+                     &pathTaken,
+                     matchedField,
+                     fromReplication,
+                     validateForStorage,
+                     immutablePaths,
+                     indexData,
+                     logBuilder,
+                     &indexesAffected,
+                     &noop);
+    ASSERT_FALSE(noop);
+    ASSERT_FALSE(indexesAffected);
+    ASSERT_EQUALS(fromjson("{a: ['a', 'b', 'd']}"), doc2);
+    ASSERT_FALSE(doc2.isInPlaceModeEnabled());
+}
+
+TEST(PullNodeTest, ApplyComplexDocAndMatching1) {
+    auto update = fromjson(
+        "{$pull: {'a.b': {$or: ["
+        "  {'y': {$exists: true }},"
+        "  {'z' : {$exists : true}} "
+        "]}}}");
+    const CollatorInterface* collator = nullptr;
+    PullNode node;
+    ASSERT_OK(node.init(update["$pull"]["a.b"], collator));
+
+    Document doc(fromjson("{a: {b: [{x: 1}, {y: 'y'}, {x: 2}, {z: 'z'}]}}"));
+    FieldRef pathToCreate("");
+    FieldRef pathTaken("a.b");
+    StringData matchedField;
+    auto fromReplication = false;
+    auto validateForStorage = true;
+    FieldRefSet immutablePaths;
+    UpdateIndexData indexData;
+    indexData.addPath("a");
+    Document logDoc;
+    LogBuilder logBuilder(logDoc.root());
+    auto indexesAffected = false;
+    auto noop = false;
+    node.apply(doc.root()["a"]["b"],
+               &pathToCreate,
+               &pathTaken,
+               matchedField,
+               fromReplication,
+               validateForStorage,
+               immutablePaths,
+               &indexData,
+               &logBuilder,
+               &indexesAffected,
+               &noop);
+    ASSERT_FALSE(noop);
+    ASSERT_TRUE(indexesAffected);
+    ASSERT_EQUALS(fromjson("{a: {b: [{x: 1}, {x: 2}]}}"), doc);
+    ASSERT_FALSE(doc.isInPlaceModeEnabled());
+    ASSERT_EQUALS(fromjson("{$set: {'a.b': [{x: 1}, {x: 2}]}}"), logDoc);
+}
+
+TEST(PullNodeTest, ApplyComplexDocAndMatching2) {
+    auto update = fromjson("{$pull: {'a.b': {'y': {$exists: true}}}}");
+    const CollatorInterface* collator = nullptr;
+    PullNode node;
+    ASSERT_OK(node.init(update["$pull"]["a.b"], collator));
+
+    Document doc(fromjson("{a: {b: [{x: 1}, {y: 'y'}, {x: 2}, {z: 'z'}]}}"));
+    FieldRef pathToCreate("");
+    FieldRef pathTaken("a.b");
+    StringData matchedField;
+    auto fromReplication = false;
+    auto validateForStorage = true;
+    FieldRefSet immutablePaths;
+    UpdateIndexData indexData;
+    indexData.addPath("a");
+    Document logDoc;
+    LogBuilder logBuilder(logDoc.root());
+    auto indexesAffected = false;
+    auto noop = false;
+    node.apply(doc.root()["a"]["b"],
+               &pathToCreate,
+               &pathTaken,
+               matchedField,
+               fromReplication,
+               validateForStorage,
+               immutablePaths,
+               &indexData,
+               &logBuilder,
+               &indexesAffected,
+               &noop);
+    ASSERT_FALSE(noop);
+    ASSERT_TRUE(indexesAffected);
+    ASSERT_EQUALS(fromjson("{a: {b: [{x: 1}, {x: 2}, {z: 'z'}]}}"), doc);
+    ASSERT_FALSE(doc.isInPlaceModeEnabled());
+    ASSERT_EQUALS(fromjson("{$set: {'a.b': [{x: 1}, {x: 2}, {z: 'z'}]}}"), logDoc);
+}
+
+TEST(PullNodeTest, ApplyComplexDocAndMatching3) {
+    auto update = fromjson("{$pull: {'a.b': {$in: [{x: 1}, {y: 'y'}]}}}");
+    const CollatorInterface* collator = nullptr;
+    PullNode node;
+    ASSERT_OK(node.init(update["$pull"]["a.b"], collator));
+
+    Document doc(fromjson("{a: {b: [{x: 1}, {y: 'y'}, {x: 2}, {z: 'z'}]}}"));
+    FieldRef pathToCreate("");
+    FieldRef pathTaken("a.b");
+    StringData matchedField;
+    auto fromReplication = false;
+    auto validateForStorage = true;
+    FieldRefSet immutablePaths;
+    UpdateIndexData indexData;
+    indexData.addPath("a");
+    Document logDoc;
+    LogBuilder logBuilder(logDoc.root());
+    auto indexesAffected = false;
+    auto noop = false;
+    node.apply(doc.root()["a"]["b"],
+               &pathToCreate,
+               &pathTaken,
+               matchedField,
+               fromReplication,
+               validateForStorage,
+               immutablePaths,
+               &indexData,
+               &logBuilder,
+               &indexesAffected,
+               &noop);
+    ASSERT_FALSE(noop);
+    ASSERT_TRUE(indexesAffected);
+    ASSERT_EQUALS(fromjson("{a: {b: [{x: 2}, {z: 'z'}]}}"), doc);
+    ASSERT_FALSE(doc.isInPlaceModeEnabled());
+    ASSERT_EQUALS(fromjson("{$set: {'a.b': [{x: 2}, {z: 'z'}]}}"), logDoc);
+}
+
+TEST(PullNodeTest, ApplyFullPredicateWithCollation) {
+    auto update = fromjson("{$pull: {'a.b': {x: 'blah'}}}");
+    CollatorInterfaceMock collator(CollatorInterfaceMock::MockType::kAlwaysEqual);
+    PullNode node;
+    ASSERT_OK(node.init(update["$pull"]["a.b"], &collator));
+
+    Document doc(fromjson("{a: {b: [{x: 'foo', y: 1}, {x: 'bar', y: 2}, {x: 'baz', y: 3}]}}"));
+    FieldRef pathToCreate("");
+    FieldRef pathTaken("a.b");
+    StringData matchedField;
+    auto fromReplication = false;
+    auto validateForStorage = true;
+    FieldRefSet immutablePaths;
+    UpdateIndexData indexData;
+    indexData.addPath("a");
+    Document logDoc;
+    LogBuilder logBuilder(logDoc.root());
+    auto indexesAffected = false;
+    auto noop = false;
+    node.apply(doc.root()["a"]["b"],
+               &pathToCreate,
+               &pathTaken,
+               matchedField,
+               fromReplication,
+               validateForStorage,
+               immutablePaths,
+               &indexData,
+               &logBuilder,
+               &indexesAffected,
+               &noop);
+    ASSERT_FALSE(noop);
+    ASSERT_TRUE(indexesAffected);
+    ASSERT_EQUALS(fromjson("{a: {b: []}}"), doc);
+    ASSERT_FALSE(doc.isInPlaceModeEnabled());
+    ASSERT_EQUALS(fromjson("{$set: {'a.b': []}}"), logDoc);
+}
+
+TEST(PullNodeTest, ApplyScalarValueMod) {
+    auto update = fromjson("{$pull: {a: 1}}");
+    const CollatorInterface* collator = nullptr;
+    PullNode node;
+    ASSERT_OK(node.init(update["$pull"]["a"], collator));
+
+    Document doc(fromjson("{a: [1, 2, 1, 2, 1, 2]}"));
+    FieldRef pathToCreate("");
+    FieldRef pathTaken("a");
+    StringData matchedField;
+    auto fromReplication = false;
+    auto validateForStorage = true;
+    FieldRefSet immutablePaths;
+    UpdateIndexData indexData;
+    indexData.addPath("a");
+    Document logDoc;
+    LogBuilder logBuilder(logDoc.root());
+    auto indexesAffected = false;
+    auto noop = false;
+    node.apply(doc.root()["a"],
+               &pathToCreate,
+               &pathTaken,
+               matchedField,
+               fromReplication,
+               validateForStorage,
+               immutablePaths,
+               &indexData,
+               &logBuilder,
+               &indexesAffected,
+               &noop);
+    ASSERT_FALSE(noop);
+    ASSERT_TRUE(indexesAffected);
+    ASSERT_EQUALS(fromjson("{a: [2, 2, 2]}"), doc);
+    ASSERT_FALSE(doc.isInPlaceModeEnabled());
+    ASSERT_EQUALS(fromjson("{$set: {a: [2, 2, 2]}}"), logDoc);
+}
+
+TEST(PullNodeTest, ApplyObjectValueMod) {
+    auto update = fromjson("{$pull: {a: {y: 2}}}");
+    const CollatorInterface* collator = nullptr;
+    PullNode node;
+    ASSERT_OK(node.init(update["$pull"]["a"], collator));
+
+    Document doc(fromjson("{a: [{x: 1}, {y: 2}, {x: 1}, {y: 2}]}"));
+    FieldRef pathToCreate("");
+    FieldRef pathTaken("a");
+    StringData matchedField;
+    auto fromReplication = false;
+    auto validateForStorage = true;
+    FieldRefSet immutablePaths;
+    UpdateIndexData indexData;
+    indexData.addPath("a");
+    Document logDoc;
+    LogBuilder logBuilder(logDoc.root());
+    auto indexesAffected = false;
+    auto noop = false;
+    node.apply(doc.root()["a"],
+               &pathToCreate,
+               &pathTaken,
+               matchedField,
+               fromReplication,
+               validateForStorage,
+               immutablePaths,
+               &indexData,
+               &logBuilder,
+               &indexesAffected,
+               &noop);
+    ASSERT_FALSE(noop);
+    ASSERT_TRUE(indexesAffected);
+    ASSERT_EQUALS(fromjson("{a: [{x: 1}, {x: 1}]}"), doc);
+    ASSERT_FALSE(doc.isInPlaceModeEnabled());
+    ASSERT_EQUALS(fromjson("{$set: {a: [{x: 1}, {x: 1}]}}"), logDoc);
+}
+
+TEST(PullNodeTest, DocumentationExample1) {
+    auto update = fromjson("{$pull: {flags: 'msr'}}");
+    const CollatorInterface* collator = nullptr;
+    PullNode node;
+    ASSERT_OK(node.init(update["$pull"]["flags"], collator));
+
+    Document doc(fromjson("{flags: ['vme', 'de', 'pse', 'tsc', 'msr', 'pae', 'mce']}"));
+    FieldRef pathToCreate("");
+    FieldRef pathTaken("flags");
+    StringData matchedField;
+    auto fromReplication = false;
+    auto validateForStorage = true;
+    FieldRefSet immutablePaths;
+    UpdateIndexData indexData;
+    indexData.addPath("a");
+    Document logDoc;
+    LogBuilder logBuilder(logDoc.root());
+    auto indexesAffected = false;
+    auto noop = false;
+    node.apply(doc.root()["flags"],
+               &pathToCreate,
+               &pathTaken,
+               matchedField,
+               fromReplication,
+               validateForStorage,
+               immutablePaths,
+               &indexData,
+               &logBuilder,
+               &indexesAffected,
+               &noop);
+    ASSERT_FALSE(noop);
+    ASSERT_FALSE(indexesAffected);
+    ASSERT_EQUALS(fromjson("{flags: ['vme', 'de', 'pse', 'tsc', 'pae', 'mce']}"), doc);
+    ASSERT_FALSE(doc.isInPlaceModeEnabled());
+    ASSERT_EQUALS(fromjson("{$set: {flags: ['vme', 'de', 'pse', 'tsc', 'pae', 'mce']}}"), logDoc);
+}
+
+TEST(PullNodeTest, DocumentationExample2a) {
+    auto update = fromjson("{$pull: {votes: 7}}");
+    const CollatorInterface* collator = nullptr;
+    PullNode node;
+    ASSERT_OK(node.init(update["$pull"]["votes"], collator));
+
+    Document doc(fromjson("{votes: [3, 5, 6, 7, 7, 8]}"));
+    FieldRef pathToCreate("");
+    FieldRef pathTaken("votes");
+    StringData matchedField;
+    auto fromReplication = false;
+    auto validateForStorage = true;
+    FieldRefSet immutablePaths;
+    UpdateIndexData indexData;
+    indexData.addPath("a");
+    Document logDoc;
+    LogBuilder logBuilder(logDoc.root());
+    auto indexesAffected = false;
+    auto noop = false;
+    node.apply(doc.root()["votes"],
+               &pathToCreate,
+               &pathTaken,
+               matchedField,
+               fromReplication,
+               validateForStorage,
+               immutablePaths,
+               &indexData,
+               &logBuilder,
+               &indexesAffected,
+               &noop);
+    ASSERT_FALSE(noop);
+    ASSERT_FALSE(indexesAffected);
+    ASSERT_EQUALS(fromjson("{votes: [3, 5, 6, 8]}"), doc);
+    ASSERT_FALSE(doc.isInPlaceModeEnabled());
+    ASSERT_EQUALS(fromjson("{$set: {votes: [3, 5, 6, 8]}}"), logDoc);
+}
+
+TEST(PullNodeTest, DocumentationExample2b) {
+    auto update = fromjson("{$pull: {votes: {$gt: 6}}}");
+    const CollatorInterface* collator = nullptr;
+    PullNode node;
+    ASSERT_OK(node.init(update["$pull"]["votes"], collator));
+
+    Document doc(fromjson("{votes: [3, 5, 6, 7, 7, 8]}"));
+    FieldRef pathToCreate("");
+    FieldRef pathTaken("votes");
+    StringData matchedField;
+    auto fromReplication = false;
+    auto validateForStorage = true;
+    FieldRefSet immutablePaths;
+    UpdateIndexData indexData;
+    indexData.addPath("a");
+    Document logDoc;
+    LogBuilder logBuilder(logDoc.root());
+    auto indexesAffected = false;
+    auto noop = false;
+    node.apply(doc.root()["votes"],
+               &pathToCreate,
+               &pathTaken,
+               matchedField,
+               fromReplication,
+               validateForStorage,
+               immutablePaths,
+               &indexData,
+               &logBuilder,
+               &indexesAffected,
+               &noop);
+    ASSERT_FALSE(noop);
+    ASSERT_FALSE(indexesAffected);
+    ASSERT_EQUALS(fromjson("{votes: [3, 5, 6]}"), doc);
+    ASSERT_FALSE(doc.isInPlaceModeEnabled());
+    ASSERT_EQUALS(fromjson("{$set: {votes: [3, 5, 6]}}"), logDoc);
+}
+
+TEST(PullNodeTest, ApplyPullWithObjectValueToArrayWithNonObjectValue) {
+    auto update = fromjson("{$pull: {a: {x: 1}}}");
+    const CollatorInterface* collator = nullptr;
+    PullNode node;
+    ASSERT_OK(node.init(update["$pull"]["a"], collator));
+
+    Document doc(fromjson("{a: [{x: 1}, 2]}"));
+    FieldRef pathToCreate("");
+    FieldRef pathTaken("a");
+    StringData matchedField;
+    auto fromReplication = false;
+    auto validateForStorage = true;
+    FieldRefSet immutablePaths;
+    UpdateIndexData indexData;
+    indexData.addPath("a");
+    Document logDoc;
+    LogBuilder logBuilder(logDoc.root());
+    auto indexesAffected = false;
+    auto noop = false;
+    node.apply(doc.root()["a"],
+               &pathToCreate,
+               &pathTaken,
+               matchedField,
+               fromReplication,
+               validateForStorage,
+               immutablePaths,
+               &indexData,
+               &logBuilder,
+               &indexesAffected,
+               &noop);
+    ASSERT_FALSE(noop);
+    ASSERT_TRUE(indexesAffected);
+    ASSERT_EQUALS(fromjson("{a: [2]}"), doc);
+    ASSERT_FALSE(doc.isInPlaceModeEnabled());
+    ASSERT_EQUALS(fromjson("{$set: {a: [2]}}"), logDoc);
+}
+
+TEST(PullNodeTest, SERVER_3988) {
+    auto update = fromjson("{$pull: {y: /yz/}}");
+    const CollatorInterface* collator = nullptr;
+    PullNode node;
+    ASSERT_OK(node.init(update["$pull"]["y"], collator));
+
+    Document doc(fromjson("{x: 1, y: [2, 3, 4, 'abc', 'xyz']}"));
+    FieldRef pathToCreate("");
+    FieldRef pathTaken("y");
+    StringData matchedField;
+    auto fromReplication = false;
+    auto validateForStorage = true;
+    FieldRefSet immutablePaths;
+    UpdateIndexData indexData;
+    indexData.addPath("a");
+    Document logDoc;
+    LogBuilder logBuilder(logDoc.root());
+    auto indexesAffected = false;
+    auto noop = false;
+    node.apply(doc.root()["y"],
+               &pathToCreate,
+               &pathTaken,
+               matchedField,
+               fromReplication,
+               validateForStorage,
+               immutablePaths,
+               &indexData,
+               &logBuilder,
+               &indexesAffected,
+               &noop);
+    ASSERT_FALSE(noop);
+    ASSERT_FALSE(indexesAffected);
+    ASSERT_EQUALS(fromjson("{x: 1, y: [2, 3, 4, 'abc']}"), doc);
+    ASSERT_FALSE(doc.isInPlaceModeEnabled());
+    ASSERT_EQUALS(fromjson("{$set: {y: [2, 3, 4, 'abc']}}"), logDoc);
+}
+
+}  // namespace mongo
diff --git a/src/mongo/db/update/update_leaf_node.cpp b/src/mongo/db/update/update_leaf_node.cpp
new file mode 100644
index 00000000000..85376cfb322
--- /dev/null
+++ b/src/mongo/db/update/update_leaf_node.cpp
@@ -0,0 +1,63 @@
+/**
+ * Copyright (C) 2017 MongoDB 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/>.
+ *
+ * As a special exception, the copyright holders give permission to link the
+ * code of portions of this program with the OpenSSL library under certain
+ * conditions as described in each individual source file and distribute
+ * linked combinations including the program with the OpenSSL library. You
+ * must comply with the GNU Affero General Public License in all respects
+ * for all of the code used other than as permitted herein. If you modify
+ * file(s) with this exception, you may extend this exception to your
+ * version of the file(s), but you are not obligated to do so. If you do not
+ * wish to do so, delete this exception statement from your version. If you
+ * delete this exception statement from all source files in the program,
+ * then also delete it in the license file.
+ */
+
+#include "mongo/platform/basic.h"
+
+#include "mongo/db/update/update_leaf_node.h"
+
+#include "mongo/util/stringutils.h"
+
+namespace mongo {
+
+void UpdateLeafNode::checkViability(mutablebson::Element element,
+                                    const FieldRef& pathToCreate,
+                                    const FieldRef& pathTaken) {
+    invariant(!pathToCreate.empty());
+
+    if (element.getType() == BSONType::Object) {
+        // 'pathTaken' leads to an object, so we know it will be possible to create 'pathToCreate'
+        // at that path.
+    } else if (element.getType() == BSONType::Array &&
+               parseUnsignedBase10Integer(pathToCreate.getPart(0))) {
+        // 'pathTaken' leads to an array, so we know we can add elements at that path so long as the
+        // next component is a valid array index. We don't check, but we expect that the index will
+        // be out of bounds. (Otherwise it would be part of 'pathTaken' and we wouldn't need to
+        // create it.)
+    } else {
+        uasserted(ErrorCodes::PathNotViable,
+                  str::stream() << "Cannot use the part (" << pathToCreate.getPart(0) << ") of ("
+                                << pathTaken.dottedField()
+                                << "."
+                                << pathToCreate.dottedField()
+                                << ") to traverse the element ({"
+                                << element.toString()
+                                << "})");
+    }
+}
+
+}  // namespace
diff --git a/src/mongo/db/update/update_leaf_node.h b/src/mongo/db/update/update_leaf_node.h
index 739ee538f62..357def1685e 100644
--- a/src/mongo/db/update/update_leaf_node.h
+++ b/src/mongo/db/update/update_leaf_node.h
@@ -52,6 +52,20 @@ public:
      * multiple documents.
      */
     virtual Status init(BSONElement modExpr, const CollatorInterface* collator) = 0;
+
+    /* Check if it would be possible to create the path at 'pathToCreate' but don't actually create
+     * it. If 'element' is not an embedded object or array (e.g., we are trying to create path
+     * "a.b.c" in the document {a: 1}) or 'element' is an array but the first component in
+     * 'pathToCreate' is not an array index (e.g., the path "a.b.c" in the document
+     * {a: [{b: 1}, {b: 2}]}), then this function throws a UserException with
+     * ErrorCode::PathNotViable. Otherwise, this function is a no-op.
+     *
+     * With the exception of $unset, update modifiers that do not create nonexistent paths ($pop,
+     * $pull, $pullAll) still generate an error when it is not possible to create the path.
+     */
+    static void checkViability(mutablebson::Element element,
+                               const FieldRef& pathToCreate,
+                               const FieldRef& pathTaken);
 };
 
 }  // namespace mongo