SERVER-23114 Move functions involving dotted paths to separate library.

The ability to specify a dotted path (e.g. "a.b") to traverse through
embedded objects and array elements isn't defined in the BSON
specification and so it doesn't belong in our BSON library.

The following functions have been defined within a 'dotted_path_support'
namespace and accept an additional BSONObj as their first argument to
replace the associated method on the BSONObj class.

  - extractElementAtPath() is functionally equivalent to
    BSONObj::getFieldDotted().

  - extractElementAtPathOrArrayAlongPath() is functionally equivalent to
    BSONObj::getFieldDottedOrArray().

  - extractAllElementsAlongPath() is functionally equivalent to
    BSONObj::getFieldsDotted().

  - extractElementsBasedOnTemplate() is functionally equivalent to
    BSONObj::extractFields().

  - compareObjectsAccordingToSort() is functionally equivalent to
    BSONObj::woSortOrder().

4 files changed, 606 insertions, 0 deletions

diff --git a/src/mongo/db/bson/SConscript b/src/mongo/db/bson/SConscript
new file mode 100644
index 00000000000..38c42957046
--- /dev/null
+++ b/src/mongo/db/bson/SConscript
@@ -0,0 +1,23 @@
+# -*- mode: python -*-
+
+Import("env")
+
+env.Library(
+    target="dotted_path_support",
+    source=[
+        "dotted_path_support.cpp",
+    ],
+    LIBDEPS=[
+        "$BUILD_DIR/mongo/base",
+    ],
+)
+
+env.CppUnitTest(
+    target="dotted_path_support_test",
+    source=[
+        "dotted_path_support_test.cpp",
+    ],
+    LIBDEPS=[
+        "dotted_path_support",
+    ],
+)
diff --git a/src/mongo/db/bson/dotted_path_support.cpp b/src/mongo/db/bson/dotted_path_support.cpp
new file mode 100644
index 00000000000..cfb10c5a39f
--- /dev/null
+++ b/src/mongo/db/bson/dotted_path_support.cpp
@@ -0,0 +1,211 @@
+/**
+ *    Copyright (C) 2016 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/bson/dotted_path_support.h"
+
+#include <cctype>
+#include <string>
+
+#include "mongo/bson/bsonelement.h"
+#include "mongo/bson/bsonmisc.h"
+#include "mongo/bson/bsonobj.h"
+#include "mongo/bson/bsonobjbuilder.h"
+
+namespace mongo {
+namespace dotted_path_support {
+
+namespace {
+
+const BSONObj kNullObj = BSON("" << BSONNULL);
+const BSONElement kNullElt = kNullObj.firstElement();
+
+template <typename BSONElementColl>
+void _extractAllElementsAlongPath(const BSONObj& obj,
+                                  StringData path,
+                                  BSONElementColl& elements,
+                                  bool expandArrayOnTrailingField) {
+    BSONElement e = obj.getField(path);
+
+    if (e.eoo()) {
+        size_t idx = path.find('.');
+        if (idx != std::string::npos) {
+            StringData left = path.substr(0, idx);
+            StringData next = path.substr(idx + 1, path.size());
+
+            BSONElement e = obj.getField(left);
+
+            if (e.type() == Object) {
+                _extractAllElementsAlongPath(
+                    e.embeddedObject(), next, elements, expandArrayOnTrailingField);
+            } else if (e.type() == Array) {
+                bool allDigits = false;
+                if (next.size() > 0 && std::isdigit(next[0])) {
+                    unsigned temp = 1;
+                    while (temp < next.size() && std::isdigit(next[temp]))
+                        temp++;
+                    allDigits = temp == next.size() || next[temp] == '.';
+                }
+                if (allDigits) {
+                    _extractAllElementsAlongPath(
+                        e.embeddedObject(), next, elements, expandArrayOnTrailingField);
+                } else {
+                    BSONObjIterator i(e.embeddedObject());
+                    while (i.more()) {
+                        BSONElement e2 = i.next();
+                        if (e2.type() == Object || e2.type() == Array)
+                            _extractAllElementsAlongPath(
+                                e2.embeddedObject(), next, elements, expandArrayOnTrailingField);
+                    }
+                }
+            } else {
+                // do nothing: no match
+            }
+        }
+    } else {
+        if (e.type() == Array && expandArrayOnTrailingField) {
+            BSONObjIterator i(e.embeddedObject());
+            while (i.more())
+                elements.insert(i.next());
+        } else {
+            elements.insert(e);
+        }
+    }
+}
+
+}  // namespace
+
+BSONElement extractElementAtPath(const BSONObj& obj, StringData path) {
+    BSONElement e = obj.getField(path);
+    if (e.eoo()) {
+        size_t dot_offset = path.find('.');
+        if (dot_offset != std::string::npos) {
+            StringData left = path.substr(0, dot_offset);
+            StringData right = path.substr(dot_offset + 1);
+            BSONObj sub = obj.getObjectField(left);
+            return sub.isEmpty() ? BSONElement() : extractElementAtPath(sub, right);
+        }
+    }
+
+    return e;
+}
+
+BSONElement extractElementAtPathOrArrayAlongPath(const BSONObj& obj, const char*& path) {
+    const char* p = strchr(path, '.');
+
+    BSONElement sub;
+
+    if (p) {
+        sub = obj.getField(std::string(path, p - path));
+        path = p + 1;
+    } else {
+        sub = obj.getField(path);
+        path = path + strlen(path);
+    }
+
+    if (sub.eoo())
+        return BSONElement();
+    else if (sub.type() == Array || path[0] == '\0')
+        return sub;
+    else if (sub.type() == Object)
+        return extractElementAtPathOrArrayAlongPath(sub.embeddedObject(), path);
+    else
+        return BSONElement();
+}
+
+void extractAllElementsAlongPath(const BSONObj& obj,
+                                 StringData path,
+                                 BSONElementSet& elements,
+                                 bool expandArrayOnTrailingField) {
+    _extractAllElementsAlongPath(obj, path, elements, expandArrayOnTrailingField);
+}
+
+void extractAllElementsAlongPath(const BSONObj& obj,
+                                 StringData path,
+                                 BSONElementMSet& elements,
+                                 bool expandArrayOnTrailingField) {
+    _extractAllElementsAlongPath(obj, path, elements, expandArrayOnTrailingField);
+}
+
+BSONObj extractElementsBasedOnTemplate(const BSONObj& obj,
+                                       const BSONObj& pattern,
+                                       bool useNullIfMissing) {
+    // scanandorder.h can make a zillion of these, so we start the allocation very small.
+    BSONObjBuilder b(32);
+    BSONObjIterator i(pattern);
+    while (i.moreWithEOO()) {
+        BSONElement e = i.next();
+        if (e.eoo())
+            break;
+        BSONElement x = extractElementAtPath(obj, e.fieldName());
+        if (!x.eoo())
+            b.appendAs(x, e.fieldName());
+        else if (useNullIfMissing)
+            b.appendNull(e.fieldName());
+    }
+    return b.obj();
+}
+
+int compareObjectsAccordingToSort(const BSONObj& firstObj,
+                                  const BSONObj& secondObj,
+                                  const BSONObj& sortKey,
+                                  bool assumeDottedPaths) {
+    if (firstObj.isEmpty())
+        return secondObj.isEmpty() ? 0 : -1;
+    if (secondObj.isEmpty())
+        return 1;
+
+    uassert(10060, "compareObjectsAccordingToSort() needs a non-empty sortKey", !sortKey.isEmpty());
+
+    BSONObjIterator i(sortKey);
+    while (1) {
+        BSONElement f = i.next();
+        if (f.eoo())
+            return 0;
+
+        BSONElement l = assumeDottedPaths ? extractElementAtPath(firstObj, f.fieldName())
+                                          : firstObj.getField(f.fieldName());
+        if (l.eoo())
+            l = kNullElt;
+        BSONElement r = assumeDottedPaths ? extractElementAtPath(secondObj, f.fieldName())
+                                          : secondObj.getField(f.fieldName());
+        if (r.eoo())
+            r = kNullElt;
+
+        int x = l.woCompare(r, false);
+        if (f.number() < 0)
+            x = -x;
+        if (x != 0)
+            return x;
+    }
+    return -1;
+}
+
+}  // namespace dotted_path_support
+}  // namespace mongo
diff --git a/src/mongo/db/bson/dotted_path_support.h b/src/mongo/db/bson/dotted_path_support.h
new file mode 100644
index 00000000000..9e2a3c9e9d0
--- /dev/null
+++ b/src/mongo/db/bson/dotted_path_support.h
@@ -0,0 +1,153 @@
+/**
+ *    Copyright (C) 2016 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 <cstddef>
+#include <set>
+
+#include "mongo/bson/bsonobj.h"
+
+namespace mongo {
+namespace dotted_path_support {
+
+/**
+ * Returns the element at the specified path. This function returns BSONElement() if the element
+ * wasn't found.
+ *
+ * The 'path' can be specified using a dotted notation in order to traverse through embedded objects
+ * and array elements.
+ *
+ * Some examples:
+ *
+ *   Consider the document {a: {b: 1}} and the path "a.b". An element with key="b" and value=1 would
+ *   be returned.
+ *
+ *   Consider the document {a: [{b: 1}]} and the path "a.b". BSONElement() would be returned because
+ *   the array value is actually an object with key="0" and value={b: 1}.
+ *
+ *   Consider the document {a: [{b: 1}]} and the path "a.0.b". An element with key="b" and value=1
+ *   would be returned.
+ */
+BSONElement extractElementAtPath(const BSONObj& obj, StringData path);
+
+/**
+ * Returns the element at the specified path, or the first element with an array value encountered
+ * along the specified path. This function returns BSONElement() if the element wasn't found.
+ *
+ * The 'path' can be specified using a dotted notation in order to traverse through embedded objects
+ * and array elements.
+ *
+ * This function modifies 'path' to be the suffix of the path that follows the first element with an
+ * array value. If no such element is present, then 'path' is set as the empty string.
+ *
+ * Some examples:
+ *
+ *   Consider the document {a: {b: [1]}} and the path "a.b". An element with key="b" and value=1
+ *   would be returned. 'path' would be changed to the empty string.
+ *
+ *   Consider the document {a: [{b: 1}]} and the path "a.b". An element with key="a" and
+ *   value=[{b: 1}] would be returned. 'path' would be changed to the string "b".
+ */
+BSONElement extractElementAtPathOrArrayAlongPath(const BSONObj& obj, const char*& path);
+
+/**
+ * Expands arrays along the specified path and adds all elements to the 'elements' set.
+ *
+ * The 'path' can be specified using a dotted notation in order to traverse through embedded objects
+ * and array elements.
+ *
+ * Some examples:
+ *
+ *   Consider the document {a: [{b: 1}, {b: 2}]} and the path "a.b". The elements {b: 1} and {b: 2}
+ *   would be added to the set.
+ *
+ *   Consider the document {a: [{b: [1, 2]}, {b: [2, 3]}]} and the path "a.b". The elements {b: 1},
+ *   {b: 2}, and {b: 3} would be added to the set if 'expandArrayOnTrailingField' is true. The
+ *   elements {b: [1, 2]} and {b: [2, 3]} would be added to the set if 'expandArrayOnTrailingField'
+ *   is false.
+ */
+void extractAllElementsAlongPath(const BSONObj& obj,
+                                 StringData path,
+                                 BSONElementSet& elements,
+                                 bool expandArrayOnTrailingField = true);
+
+void extractAllElementsAlongPath(const BSONObj& obj,
+                                 StringData path,
+                                 BSONElementMSet& elements,
+                                 bool expandArrayOnTrailingField = true);
+
+/**
+ * Returns an owned BSONObj with elements in the same order as they appear in the 'pattern' object
+ * and values extracted from 'obj'.
+ *
+ * The keys of the elements in the 'pattern' object can be specified using a dotted notation in
+ * order to traverse through embedded objects and array elements. The values of the elements in the
+ * 'pattern' object are ignored.
+ *
+ * If 'useNullIfMissing' is true and the key in the 'pattern' object isn't present in 'obj', then a
+ * null value is appended to the returned value instead.
+ *
+ * Some examples:
+ *
+ *   Consider the document {a: 1, b: 1} and the template {b: ""}. The object {b: 1} would be
+ *   returned.
+ *
+ *   Consider the document {a: {b: 1}} and the template {"a.b": ""}. The object {"a.b": 1} would be
+ *   returned.
+ *
+ *   Consider the document {b: 1} and the template {a: "", b: ""}. The object {a: null, b: 1} would
+ *   be returned if 'useNullIfMissing' is true. The object {b: 1} would be returned if
+ *   'useNullIfMissing' is false.
+ */
+BSONObj extractElementsBasedOnTemplate(const BSONObj& obj,
+                                       const BSONObj& pattern,
+                                       bool useNullIfMissing = false);
+
+/**
+ * Compares two objects according to order of elements in the 'sortKey' object. This function
+ * returns -1 if 'firstObj' < 'secondObj' according to 'sortKey', 0 if 'firstObj' == 'secondObj'
+ * according to 'sortKey', and 1 if 'firstObj' > 'secondObj' according to 'sortKey'.
+ *
+ * If 'assumeDottedPaths' is true, then extractElementAtPath() is used to get the element associated
+ * with the key of an element in the 'sortKey' object. If 'assumeDottedPaths' is false, then
+ * BSONObj::getField() is used to get the element associated with the key of an element in the
+ * 'sortKey' object. BSONObj::getField() searches the object for the key verbatim and does no
+ * special handling to traverse through embedded objects and array elements when a "." character is
+ * specified.
+ *
+ * Unlike with BSONObj::woCompare(), the elements don't need to be in the same order between
+ * 'firstObj' and 'secondObj'.
+ */
+int compareObjectsAccordingToSort(const BSONObj& firstObj,
+                                  const BSONObj& secondObj,
+                                  const BSONObj& sortKey,
+                                  bool assumeDottedPaths = false);
+
+}  // namespace dotted_path_support
+}  // namespace mongo
diff --git a/src/mongo/db/bson/dotted_path_support_test.cpp b/src/mongo/db/bson/dotted_path_support_test.cpp
new file mode 100644
index 00000000000..78d3253d8b5
--- /dev/null
+++ b/src/mongo/db/bson/dotted_path_support_test.cpp
@@ -0,0 +1,219 @@
+/**
+ *    Copyright (C) 2016 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 <vector>
+
+#include "mongo/bson/bsonelement.h"
+#include "mongo/bson/bsonmisc.h"
+#include "mongo/bson/bsonobj.h"
+#include "mongo/bson/bsonobjbuilder.h"
+#include "mongo/db/bson/dotted_path_support.h"
+#include "mongo/unittest/unittest.h"
+
+namespace mongo {
+namespace {
+
+namespace dps = ::mongo::dotted_path_support;
+
+TEST(DottedPathSupport, CompareObjectsAccordingToSort) {
+    ASSERT_LT(dps::compareObjectsAccordingToSort(
+                  BSON("a" << 1), BSON("a" << 2), BSON("b" << 1 << "a" << 1)),
+              0);
+    ASSERT_EQ(
+        dps::compareObjectsAccordingToSort(BSON("a" << BSONNULL), BSON("b" << 1), BSON("a" << 1)),
+        0);
+}
+
+TEST(DottedPathSupport, ExtractElementAtPath) {
+    BSONObj obj = BSON("a" << 1 << "b" << BSON("a" << 2) << "c"
+                           << BSON_ARRAY(BSON("a" << 3) << BSON("a" << 4)));
+    ASSERT_EQUALS(1, dps::extractElementAtPath(obj, "a").numberInt());
+    ASSERT_EQUALS(2, dps::extractElementAtPath(obj, "b.a").numberInt());
+    ASSERT_EQUALS(3, dps::extractElementAtPath(obj, "c.0.a").numberInt());
+    ASSERT_EQUALS(4, dps::extractElementAtPath(obj, "c.1.a").numberInt());
+
+    ASSERT_TRUE(dps::extractElementAtPath(obj, "x").eoo());
+    ASSERT_TRUE(dps::extractElementAtPath(obj, "a.x").eoo());
+    ASSERT_TRUE(dps::extractElementAtPath(obj, "x.y").eoo());
+    ASSERT_TRUE(dps::extractElementAtPath(obj, "").eoo());
+    ASSERT_TRUE(dps::extractElementAtPath(obj, ".").eoo());
+    ASSERT_TRUE(dps::extractElementAtPath(obj, "..").eoo());
+    ASSERT_TRUE(dps::extractElementAtPath(obj, "...").eoo());
+    ASSERT_TRUE(dps::extractElementAtPath(obj, "a.").eoo());
+    ASSERT_TRUE(dps::extractElementAtPath(obj, ".a").eoo());
+    ASSERT_TRUE(dps::extractElementAtPath(obj, "b.a.").eoo());
+}
+
+TEST(DottedPathSupport, ExtractElementsBasedOnTemplate) {
+    BSONObj obj = BSON("a" << 10 << "b" << 11);
+
+    ASSERT_EQ(BSON("a" << 10).woCompare(dps::extractElementsBasedOnTemplate(obj, BSON("a" << 1))),
+              0);
+    ASSERT_EQ(BSON("b" << 11).woCompare(dps::extractElementsBasedOnTemplate(obj, BSON("b" << 1))),
+              0);
+    ASSERT_EQ(obj.woCompare(dps::extractElementsBasedOnTemplate(obj, BSON("a" << 1 << "b" << 1))),
+              0);
+
+    ASSERT_EQ(dps::extractElementsBasedOnTemplate(obj, BSON("a" << 1 << "c" << 1))
+                  .firstElement()
+                  .fieldNameStringData(),
+              "a");
+}
+
+void dumpBSONElementSet(const BSONElementSet& elements, StringBuilder* sb) {
+    *sb << "[ ";
+    bool firstIteration = true;
+    for (auto&& elem : elements) {
+        if (!firstIteration) {
+            *sb << ", ";
+        }
+        *sb << "'" << elem << "'";
+        firstIteration = false;
+    }
+    *sb << " ]";
+}
+
+void assertBSONElementSetsAreEqual(const std::vector<BSONObj>& expectedObjs,
+                                   const BSONElementSet& actualElements) {
+    BSONElementSet expectedElements;
+    for (auto&& obj : expectedObjs) {
+        expectedElements.insert(obj.firstElement());
+    }
+
+    if (expectedElements.size() != actualElements.size()) {
+        StringBuilder sb;
+        sb << "Expected set to contain " << expectedElements.size()
+           << " element(s), but actual set contains " << actualElements.size()
+           << " element(s); Expected set: ";
+        dumpBSONElementSet(expectedElements, &sb);
+        sb << ", Actual set: ";
+        dumpBSONElementSet(actualElements, &sb);
+        FAIL(sb.str());
+    }
+
+    // We do our own comparison of the two BSONElementSets because BSONElement::operator== considers
+    // the field name.
+    auto expectedIt = expectedElements.begin();
+    auto actualIt = actualElements.begin();
+
+    for (size_t i = 0; i < expectedElements.size(); ++i) {
+        if (!expectedIt->valuesEqual(*actualIt)) {
+            StringBuilder sb;
+            sb << "Element '" << *expectedIt << "' doesn't have the same value as element '"
+               << *actualIt << "'; Expected set: ";
+            dumpBSONElementSet(expectedElements, &sb);
+            sb << ", Actual set: ";
+            dumpBSONElementSet(actualElements, &sb);
+            FAIL(sb.str());
+        }
+
+        ++expectedIt;
+        ++actualIt;
+    }
+}
+
+TEST(ExtractAllElementsAlongPath, NestedObjectWithScalarValue) {
+    BSONObj obj = BSON("a" << BSON("b" << 1));
+
+    BSONElementSet actualElements;
+    const bool expandArrayOnTrailingField = true;
+    dps::extractAllElementsAlongPath(obj, "a.b", actualElements, expandArrayOnTrailingField);
+
+    assertBSONElementSetsAreEqual({BSON("" << 1)}, actualElements);
+}
+
+TEST(ExtractAllElementsAlongPath, NestedObjectWithEmptyArrayValue) {
+    BSONObj obj = BSON("a" << BSON("b" << BSONArrayBuilder().arr()));
+
+    BSONElementSet actualElements;
+    const bool expandArrayOnTrailingField = true;
+    dps::extractAllElementsAlongPath(obj, "a.b", actualElements, expandArrayOnTrailingField);
+
+    assertBSONElementSetsAreEqual(std::vector<BSONObj>{}, actualElements);
+}
+
+TEST(ExtractAllElementsAlongPath, NestedObjectWithSingletonArrayValue) {
+    BSONObj obj = BSON("a" << BSON("b" << BSON_ARRAY(1)));
+
+    BSONElementSet actualElements;
+    const bool expandArrayOnTrailingField = true;
+    dps::extractAllElementsAlongPath(obj, "a.b", actualElements, expandArrayOnTrailingField);
+
+    assertBSONElementSetsAreEqual({BSON("" << 1)}, actualElements);
+}
+
+TEST(ExtractAllElementsAlongPath, NestedObjectWithArrayValue) {
+    BSONObj obj = BSON("a" << BSON("b" << BSON_ARRAY(1 << 2 << 3)));
+
+    BSONElementSet actualElements;
+    const bool expandArrayOnTrailingField = true;
+    dps::extractAllElementsAlongPath(obj, "a.b", actualElements, expandArrayOnTrailingField);
+
+    assertBSONElementSetsAreEqual({BSON("" << 1), BSON("" << 2), BSON("" << 3)}, actualElements);
+}
+
+TEST(ExtractAllElementsAlongPath, ObjectWithArrayOfSubobjectsWithScalarValue) {
+    BSONObj obj = BSON("a" << BSON_ARRAY(BSON("b" << 1) << BSON("b" << 2) << BSON("b" << 3)));
+
+    BSONElementSet actualElements;
+    const bool expandArrayOnTrailingField = true;
+    dps::extractAllElementsAlongPath(obj, "a.b", actualElements, expandArrayOnTrailingField);
+
+    assertBSONElementSetsAreEqual({BSON("" << 1), BSON("" << 2), BSON("" << 3)}, actualElements);
+}
+
+TEST(ExtractAllElementsAlongPath, ObjectWithArrayOfSubobjectsWithArrayValues) {
+    BSONObj obj =
+        BSON("a" << BSON_ARRAY(BSON("b" << BSON_ARRAY(1 << 2)) << BSON("b" << BSON_ARRAY(2 << 3))
+                                                               << BSON("b" << BSON_ARRAY(3 << 1))));
+
+    BSONElementSet actualElements;
+    const bool expandArrayOnTrailingField = true;
+    dps::extractAllElementsAlongPath(obj, "a.b", actualElements, expandArrayOnTrailingField);
+
+    assertBSONElementSetsAreEqual({BSON("" << 1), BSON("" << 2), BSON("" << 3)}, actualElements);
+}
+
+TEST(ExtractAllElementsAlongPath,
+     ObjectWithArrayOfSubobjectsWithArrayValuesButNotExpandingTrailingArrayValues) {
+    BSONObj obj = BSON("a" << BSON_ARRAY(BSON("b" << BSON_ARRAY(1)) << BSON("b" << BSON_ARRAY(2))
+                                                                    << BSON("b" << BSON_ARRAY(3))));
+
+    BSONElementSet actualElements;
+    const bool expandArrayOnTrailingField = false;
+    dps::extractAllElementsAlongPath(obj, "a.b", actualElements, expandArrayOnTrailingField);
+
+    assertBSONElementSetsAreEqual(
+        {BSON("" << BSON_ARRAY(1)), BSON("" << BSON_ARRAY(2)), BSON("" << BSON_ARRAY(3))},
+        actualElements);
+}
+
+}  // namespace
+}  // namespace mongo