SERVER-27437 Add dotted path expansion for Documents.

7 files changed, 706 insertions, 11 deletions

diff --git a/src/mongo/db/bson/dotted_path_support_test.cpp b/src/mongo/db/bson/dotted_path_support_test.cpp
index b18e949290f..06fa6dc2840 100644
--- a/src/mongo/db/bson/dotted_path_support_test.cpp
+++ b/src/mongo/db/bson/dotted_path_support_test.cpp
@@ -37,6 +37,7 @@
 #include "mongo/bson/bsonmisc.h"
 #include "mongo/bson/bsonobj.h"
 #include "mongo/bson/bsonobjbuilder.h"
+#include "mongo/bson/json.h"
 #include "mongo/db/bson/dotted_path_support.h"
 #include "mongo/unittest/unittest.h"
 
@@ -267,5 +268,216 @@ TEST(ExtractAllElementsAlongPath,
     assertArrayComponentsAreEqual({0U}, actualArrayComponents);
 }
 
+TEST(ExtractAllElementsAlongPath, DoesNotExpandArrayWithinTrailingArray) {
+    BSONObj obj = BSON("a" << BSON("b" << BSON_ARRAY(BSON_ARRAY(1 << 2) << BSON_ARRAY(3 << 4))));
+
+    BSONElementSet actualElements;
+    const bool expandArrayOnTrailingField = true;
+    std::set<size_t> actualArrayComponents;
+    dps::extractAllElementsAlongPath(
+        obj, "a.b", actualElements, expandArrayOnTrailingField, &actualArrayComponents);
+
+    assertBSONElementSetsAreEqual({BSON("" << BSON_ARRAY(1 << 2)), BSON("" << BSON_ARRAY(3 << 4))},
+                                  actualElements);
+    assertArrayComponentsAreEqual({1U}, actualArrayComponents);
+}
+
+TEST(ExtractAllElementsAlongPath, ObjectWithTwoDimensionalArrayOfSubobjects) {
+    // Does not expand the array within the array.
+    BSONObj obj = fromjson("{a: [[{b: 0}, {b: 1}], [{b: 2}, {b: 3}]]}");
+
+    BSONElementSet actualElements;
+    const bool expandArrayOnTrailingField = true;
+    std::set<size_t> actualArrayComponents;
+    dps::extractAllElementsAlongPath(
+        obj, "a.b", actualElements, expandArrayOnTrailingField, &actualArrayComponents);
+
+    assertBSONElementSetsAreEqual({}, actualElements);
+    assertArrayComponentsAreEqual({0U}, actualArrayComponents);
+}
+
+TEST(ExtractAllElementsAlongPath, ObjectWithDiverseStructure) {
+    BSONObj obj = fromjson(
+        "{a: ["
+        "     {b: 0},"
+        "     [{b: 1}, {b: {c: -1}}],"
+        "     'no b here!',"
+        "     {b: [{c: -2}, 'no c here!']},"
+        "     {b: {c: [-3, -4]}}"
+        "]}");
+
+    BSONElementSet actualElements;
+    const bool expandArrayOnTrailingField = true;
+    std::set<size_t> actualArrayComponents;
+    dps::extractAllElementsAlongPath(
+        obj, "a.b.c", actualElements, expandArrayOnTrailingField, &actualArrayComponents);
+
+    assertBSONElementSetsAreEqual({BSON("" << -2), BSON("" << -3), BSON("" << -4)}, actualElements);
+    assertArrayComponentsAreEqual({0U, 1U, 2U}, actualArrayComponents);
+}
+
+TEST(ExtractAllElementsAlongPath, AcceptsNumericFieldNames) {
+    BSONObj obj = BSON("a" << BSON("0" << 1));
+
+    BSONElementSet actualElements;
+    const bool expandArrayOnTrailingField = true;
+    std::set<size_t> actualArrayComponents;
+    dps::extractAllElementsAlongPath(
+        obj, "a.0", actualElements, expandArrayOnTrailingField, &actualArrayComponents);
+
+    assertBSONElementSetsAreEqual({BSON("" << 1)}, actualElements);
+    assertArrayComponentsAreEqual(std::set<size_t>{}, actualArrayComponents);
+}
+
+TEST(ExtractAllElementsAlongPath, UsesNumericFieldNameToExtractElementFromArray) {
+    BSONObj obj = BSON("a" << BSON_ARRAY(1 << BSON("0" << 2)));
+
+    BSONElementSet actualElements;
+    const bool expandArrayOnTrailingField = true;
+    std::set<size_t> actualArrayComponents;
+    dps::extractAllElementsAlongPath(
+        obj, "a.0", actualElements, expandArrayOnTrailingField, &actualArrayComponents);
+
+    assertBSONElementSetsAreEqual({BSON("" << 1)}, actualElements);
+    assertArrayComponentsAreEqual(std::set<size_t>{}, actualArrayComponents);
+}
+
+TEST(ExtractAllElementsAlongPath, TreatsNegativeIndexAsFieldName) {
+    BSONObj obj = BSON("a" << BSON_ARRAY(1 << BSON("-1" << 2) << BSON("b" << 3)));
+
+    BSONElementSet actualElements;
+    const bool expandArrayOnTrailingField = true;
+    std::set<size_t> actualArrayComponents;
+    dps::extractAllElementsAlongPath(
+        obj, "a.-1", actualElements, expandArrayOnTrailingField, &actualArrayComponents);
+
+    assertBSONElementSetsAreEqual({BSON("" << 2)}, actualElements);
+    assertArrayComponentsAreEqual({0U}, actualArrayComponents);
+}
+
+TEST(ExtractAllElementsAlongPath, ExtractsNoValuesFromOutOfBoundsIndex) {
+    BSONObj obj = BSON("a" << BSON_ARRAY(1 << BSON("b" << 2) << BSON("10" << 3)));
+
+    BSONElementSet actualElements;
+    const bool expandArrayOnTrailingField = true;
+    std::set<size_t> actualArrayComponents;
+    dps::extractAllElementsAlongPath(
+        obj, "a.10", actualElements, expandArrayOnTrailingField, &actualArrayComponents);
+
+    assertBSONElementSetsAreEqual({}, actualElements);
+    assertArrayComponentsAreEqual(std::set<size_t>{}, actualArrayComponents);
+}
+
+TEST(ExtractAllElementsAlongPath, DoesNotTreatHexStringAsIndexSpecification) {
+    BSONObj obj = BSON("a" << BSON_ARRAY(1 << BSON("0x2" << 2) << BSON("NOT THIS ONE" << 3)));
+
+    BSONElementSet actualElements;
+    const bool expandArrayOnTrailingField = true;
+    std::set<size_t> actualArrayComponents;
+    dps::extractAllElementsAlongPath(
+        obj, "a.0x2", actualElements, expandArrayOnTrailingField, &actualArrayComponents);
+
+    assertBSONElementSetsAreEqual({BSON("" << 2)}, actualElements);
+    assertArrayComponentsAreEqual({0U}, actualArrayComponents);
+}
+
+TEST(ExtractAllElementsAlongPath, DoesNotAcceptLeadingPlusAsArrayIndex) {
+    BSONObj obj = BSON("a" << BSON_ARRAY(1 << BSON("+2" << 2) << BSON("NOT THIS ONE" << 3)));
+
+    BSONElementSet actualElements;
+    const bool expandArrayOnTrailingField = true;
+    std::set<size_t> actualArrayComponents;
+    dps::extractAllElementsAlongPath(
+        obj, "a.+2", actualElements, expandArrayOnTrailingField, &actualArrayComponents);
+
+    assertBSONElementSetsAreEqual({BSON("" << 2)}, actualElements);
+    assertArrayComponentsAreEqual({0U}, actualArrayComponents);
+}
+
+TEST(ExtractAllElementsAlongPath, DoesNotAcceptTrailingCharactersForArrayIndex) {
+    BSONObj obj = BSON("a" << BSON_ARRAY(1 << BSON("2xyz" << 2) << BSON("NOT THIS ONE" << 3)));
+
+    BSONElementSet actualElements;
+    const bool expandArrayOnTrailingField = true;
+    std::set<size_t> actualArrayComponents;
+    dps::extractAllElementsAlongPath(
+        obj, "a.2xyz", actualElements, expandArrayOnTrailingField, &actualArrayComponents);
+
+    assertBSONElementSetsAreEqual({BSON("" << 2)}, actualElements);
+    assertArrayComponentsAreEqual({0U}, actualArrayComponents);
+}
+
+TEST(ExtractAllElementsAlongPath, DoesNotAcceptNonDigitsForArrayIndex) {
+    BSONObj obj = BSON("a" << BSON_ARRAY(1 << BSON("2x4" << 2) << BSON("NOT THIS ONE" << 3)));
+
+    BSONElementSet actualElements;
+    const bool expandArrayOnTrailingField = true;
+    std::set<size_t> actualArrayComponents;
+    dps::extractAllElementsAlongPath(
+        obj, "a.2x4", actualElements, expandArrayOnTrailingField, &actualArrayComponents);
+
+    assertBSONElementSetsAreEqual({BSON("" << 2)}, actualElements);
+    assertArrayComponentsAreEqual({0U}, actualArrayComponents);
+}
+
+TEST(ExtractAllElementsAlongPath,
+     DoesExtractNestedValuesFromWithinArraysTraversedWithPositionalPaths) {
+    BSONObj obj = BSON("a" << BSON_ARRAY(1 << BSON("2" << 2) << BSON("target" << 3)));
+
+    BSONElementSet actualElements;
+    const bool expandArrayOnTrailingField = true;
+    std::set<size_t> actualArrayComponents;
+    dps::extractAllElementsAlongPath(
+        obj, "a.2.target", actualElements, expandArrayOnTrailingField, &actualArrayComponents);
+
+    assertBSONElementSetsAreEqual({BSON("" << 3)}, actualElements);
+    assertArrayComponentsAreEqual(std::set<size_t>{}, actualArrayComponents);
+}
+
+TEST(ExtractAllElementsAlongPath, DoesExpandMultiplePositionalPathSpecifications) {
+    BSONObj obj(fromjson("{a: [[{b: '(0, 0)'}, {b: '(0, 1)'}], [{b: '(1, 0)'}, {b: '(1, 1)'}]]}"));
+
+    BSONElementSet actualElements;
+    const bool expandArrayOnTrailingField = true;
+    std::set<size_t> actualArrayComponents;
+    dps::extractAllElementsAlongPath(
+        obj, "a.1.0.b", actualElements, expandArrayOnTrailingField, &actualArrayComponents);
+
+    assertBSONElementSetsAreEqual({BSON(""
+                                        << "(1, 0)")},
+                                  actualElements);
+    assertArrayComponentsAreEqual(std::set<size_t>{}, actualArrayComponents);
+}
+
+TEST(ExtractAllElementsAlongPath, DoesAcceptNumericInitialField) {
+    BSONObj obj = BSON("a" << 1 << "0" << 2);
+
+    BSONElementSet actualElements;
+    const bool expandArrayOnTrailingField = true;
+    std::set<size_t> actualArrayComponents;
+    dps::extractAllElementsAlongPath(
+        obj, "0", actualElements, expandArrayOnTrailingField, &actualArrayComponents);
+
+    assertBSONElementSetsAreEqual({BSON("" << 2)}, actualElements);
+    assertArrayComponentsAreEqual(std::set<size_t>{}, actualArrayComponents);
+}
+
+TEST(ExtractAllElementsAlongPath, DoesExpandArrayFoundAfterPositionalSpecification) {
+    BSONObj obj(fromjson("{a: [[{b: '(0, 0)'}, {b: '(0, 1)'}], [{b: '(1, 0)'}, {b: '(1, 1)'}]]}"));
+
+    BSONElementSet actualElements;
+    const bool expandArrayOnTrailingField = true;
+    std::set<size_t> actualArrayComponents;
+    dps::extractAllElementsAlongPath(
+        obj, "a.1.b", actualElements, expandArrayOnTrailingField, &actualArrayComponents);
+
+    assertBSONElementSetsAreEqual({BSON(""
+                                        << "(1, 0)"),
+                                   BSON(""
+                                        << "(1, 1)")},
+                                  actualElements);
+    assertArrayComponentsAreEqual({1U}, actualArrayComponents);
+}
+
 }  // namespace
 }  // namespace mongo
diff --git a/src/mongo/db/pipeline/SConscript b/src/mongo/db/pipeline/SConscript
index 701dbac4037..49783bc5def 100644
--- a/src/mongo/db/pipeline/SConscript
+++ b/src/mongo/db/pipeline/SConscript
@@ -41,6 +41,7 @@ env.Library(
     source=[
         'document.cpp',
         'document_comparator.cpp',
+        'document_path_support.cpp',
         'value.cpp',
         'value_comparator.cpp',
         ],
@@ -67,6 +68,7 @@ env.CppUnitTest(
     source=[
         'document_comparator_test.cpp',
         'document_value_test.cpp',
+        'document_path_support_test.cpp',
         'document_value_test_util_self_test.cpp',
         'value_comparator_test.cpp',
     ],
diff --git a/src/mongo/db/pipeline/document.cpp b/src/mongo/db/pipeline/document.cpp
index 627bafdfd78..573949afb8d 100644
--- a/src/mongo/db/pipeline/document.cpp
+++ b/src/mongo/db/pipeline/document.cpp
@@ -354,10 +354,9 @@ static Value getNestedFieldHelper(const Document& doc,
     return getNestedFieldHelper(val.getDocument(), fieldNames, positions, level + 1);
 }
 
-const Value Document::getNestedField(const FieldPath& fieldNames,
-                                     vector<Position>* positions) const {
-    fassert(16489, fieldNames.getPathLength());
-    return getNestedFieldHelper(*this, fieldNames, positions, 0);
+const Value Document::getNestedField(const FieldPath& path, vector<Position>* positions) const {
+    fassert(16489, path.getPathLength());
+    return getNestedFieldHelper(*this, path, positions, 0);
 }
 
 size_t Document::getApproximateSize() const {
diff --git a/src/mongo/db/pipeline/document.h b/src/mongo/db/pipeline/document.h
index 5dc14ab7aa5..1587428f9aa 100644
--- a/src/mongo/db/pipeline/document.h
+++ b/src/mongo/db/pipeline/document.h
@@ -123,14 +123,13 @@ public:
         return storage().getField(pos).val;
     }
 
-    /** Similar to extractAllElementsAlongPath(), but using FieldPath rather than a dotted string.
-     *  If you pass a non-NULL positions vector, you get back a path suitable
-     *  to pass to MutableDocument::setNestedField.
-     *
-     *  TODO a version that doesn't use FieldPath
+    /**
+     * Returns the Value stored at the location given by 'path', or Value() if no such path exists.
+     * If 'positions' is non-null, it will be filled with a path suitable to pass to
+     * MutableDocument::setNestedField().
      */
-    const Value getNestedField(const FieldPath& fieldNames,
-                               std::vector<Position>* positions = NULL) const;
+    const Value getNestedField(const FieldPath& path,
+                               std::vector<Position>* positions = nullptr) const;
 
     /// Number of fields in this document. O(n)
     size_t size() const {
diff --git a/src/mongo/db/pipeline/document_path_support.cpp b/src/mongo/db/pipeline/document_path_support.cpp
new file mode 100644
index 00000000000..261b7bdf91d
--- /dev/null
+++ b/src/mongo/db/pipeline/document_path_support.cpp
@@ -0,0 +1,142 @@
+/**
+ * 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 <boost/optional.hpp>
+#include <cctype>
+#include <vector>
+
+#include "mongo/db/pipeline/document_path_support.h"
+
+#include "mongo/base/parse_number.h"
+#include "mongo/base/string_data.h"
+#include "mongo/db/pipeline/document.h"
+#include "mongo/db/pipeline/field_path.h"
+#include "mongo/db/pipeline/value.h"
+
+namespace mongo {
+namespace document_path_support {
+
+namespace {
+
+/**
+ * Returns the array index that should be used if 'fieldName' represents a positional path
+ * specification (as '0' does in 'a.0'), or boost::none if 'fieldName' does not represent a
+ * positional path specification.
+ */
+boost::optional<size_t> getPositionalPathSpecification(StringData fieldName) {
+    // Do not accept positions like '-4' or '+4'
+    if (!std::isdigit(fieldName[0])) {
+        return boost::none;
+    }
+    unsigned int index;
+    auto status = parseNumberFromStringWithBase<unsigned int>(fieldName, 10, &index);
+    if (status.isOK()) {
+        return static_cast<size_t>(index);
+    }
+    return boost::none;
+}
+
+/**
+ * If 'value' is an array, invokes 'callback' once on each element of 'value'. Otherwise, if 'value'
+ * is not missing, invokes 'callback' on 'value' itself.
+ */
+void invokeCallbackOnTrailingValue(const Value& value,
+                                   stdx::function<void(const Value&)> callback) {
+    if (value.isArray()) {
+        for (auto&& finalValue : value.getArray()) {
+            if (!finalValue.missing()) {
+                callback(finalValue);
+            }
+        }
+    } else if (!value.missing()) {
+        callback(value);
+    }
+}
+
+void visitAllValuesAtPathHelper(Document doc,
+                                const FieldPath& path,
+                                size_t fieldPathIndex,
+                                stdx::function<void(const Value&)> callback) {
+    invariant(path.getPathLength() > 0 && fieldPathIndex < path.getPathLength());
+
+    // The first field in the path must be treated as a field name, even if it is numeric as in
+    // "0.a.1.b".
+    auto nextValue = doc.getField(path.getFieldName(fieldPathIndex));
+    ++fieldPathIndex;
+    if (path.getPathLength() == fieldPathIndex) {
+        invokeCallbackOnTrailingValue(nextValue, callback);
+        return;
+    }
+
+    // Follow numeric field names as positions in array values. This loop consumes all consecutive
+    // positional specifications, if applicable. For example, it will consume "0" and "1" from the
+    // path "a.0.1.b" if the value at "a" is an array with arrays inside it.
+    while (fieldPathIndex < path.getPathLength() && nextValue.isArray()) {
+        if (auto index = getPositionalPathSpecification(path.getFieldName(fieldPathIndex))) {
+            nextValue = nextValue[*index];
+            ++fieldPathIndex;
+        } else {
+            break;
+        }
+    }
+
+    if (fieldPathIndex == path.getPathLength()) {
+        // The path ended in a positional traversal of arrays (e.g. "a.0").
+        invokeCallbackOnTrailingValue(nextValue, callback);
+        return;
+    }
+
+    if (nextValue.isArray()) {
+        // The positional path specification ended at an array, or we did not have a positional
+        // specification. In either case, there is still more path to explore, so we should go
+        // through all elements and look for the rest of the path in any objects we encounter.
+        //
+        // Note we do not expand arrays within arrays this way. For example, {a: [[{b: 1}]]} has no
+        // values on the path "a.b", but {a: [{b: 1}]} does.
+        for (auto&& subValue : nextValue.getArray()) {
+            if (subValue.getType() == BSONType::Object) {
+                visitAllValuesAtPathHelper(subValue.getDocument(), path, fieldPathIndex, callback);
+            }
+        }
+    } else if (nextValue.getType() == BSONType::Object) {
+        visitAllValuesAtPathHelper(nextValue.getDocument(), path, fieldPathIndex, callback);
+    }
+}
+
+}  // namespace
+
+void visitAllValuesAtPath(Document doc,
+                          const FieldPath& path,
+                          stdx::function<void(const Value&)> callback) {
+    visitAllValuesAtPathHelper(std::move(doc), path, 0, callback);
+}
+
+}  // namespace document_path_support
+}  // namespace mongo
diff --git a/src/mongo/db/pipeline/document_path_support.h b/src/mongo/db/pipeline/document_path_support.h
new file mode 100644
index 00000000000..60020873947
--- /dev/null
+++ b/src/mongo/db/pipeline/document_path_support.h
@@ -0,0 +1,55 @@
+/**
+ * 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 <vector>
+
+#include "mongo/db/pipeline/document.h"
+#include "mongo/db/pipeline/expression_context.h"
+#include "mongo/db/pipeline/field_path.h"
+#include "mongo/db/pipeline/value.h"
+#include "mongo/db/pipeline/value_comparator.h"
+#include "mongo/stdx/functional.h"
+
+namespace mongo {
+namespace document_path_support {
+
+/**
+ * Calls 'callback' once for each value found at 'path' in the document 'doc'. If an array value is
+ * found at 'path', it is expanded and 'callback' is invoked once for each value within the array.
+ *
+ * For example, 'callback' will be invoked on the values 1, 1, {a: 1}, 2 and 3 are on the path "x.y"
+ * in the document {x: [{y: 1}, {y: 1}, {y: {a: 1}}, {y: [2, 3]}, 3, 4]}.
+ */
+void visitAllValuesAtPath(Document doc,
+                          const FieldPath& path,
+                          stdx::function<void(const Value&)> callback);
+
+}  // namespace document_path_support
+}  // namespace mongo
diff --git a/src/mongo/db/pipeline/document_path_support_test.cpp b/src/mongo/db/pipeline/document_path_support_test.cpp
new file mode 100644
index 00000000000..cb3a2e1b3b5
--- /dev/null
+++ b/src/mongo/db/pipeline/document_path_support_test.cpp
@@ -0,0 +1,286 @@
+/**
+ * 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 <boost/optional.hpp>
+#include <vector>
+
+#include "mongo/base/string_data.h"
+#include "mongo/bson/json.h"
+#include "mongo/db/pipeline/document.h"
+#include "mongo/db/pipeline/document_comparator.h"
+#include "mongo/db/pipeline/document_path_support.h"
+#include "mongo/db/pipeline/document_value_test_util.h"
+#include "mongo/db/pipeline/field_path.h"
+#include "mongo/db/pipeline/value.h"
+#include "mongo/unittest/unittest.h"
+
+namespace mongo {
+namespace document_path_support {
+
+namespace {
+using std::vector;
+
+const ValueComparator kDefaultValueComparator{};
+
+TEST(VisitAllValuesAtPathTest, NestedObjectWithScalarValue) {
+    auto values = kDefaultValueComparator.makeUnorderedValueSet();
+    auto callback = [&values](const Value& val) { values.insert(val); };
+    Document doc{{"a", Document{{"b", 1}}}};
+    visitAllValuesAtPath(doc, FieldPath("a.b"), callback);
+    ASSERT_EQ(values.size(), 1UL);
+    ASSERT_EQ(values.count(Value(1)), 1UL);
+}
+
+TEST(VisitAllValuesAtPathTest, NestedObjectWithEmptyArrayValue) {
+    auto values = kDefaultValueComparator.makeUnorderedValueSet();
+    auto callback = [&values](const Value& val) { values.insert(val); };
+    Document doc{{"a", Document{{"b", vector<Value>{}}}}};
+    visitAllValuesAtPath(doc, FieldPath("a.b"), callback);
+    ASSERT_EQ(values.size(), 0UL);
+}
+
+TEST(VisitAllValuesAtPathTest, NestedObjectWithSingletonArrayValue) {
+    auto values = kDefaultValueComparator.makeUnorderedValueSet();
+    auto callback = [&values](const Value& val) { values.insert(val); };
+    Document doc{{"a", Document{{"b", vector<Value>{Value(1)}}}}};
+    visitAllValuesAtPath(doc, FieldPath("a.b"), callback);
+    ASSERT_EQ(values.size(), 1UL);
+    ASSERT_EQ(values.count(Value(1)), 1UL);
+}
+
+TEST(VisitAllValuesAtPathTest, NestedObjectWithArrayValue) {
+    auto values = kDefaultValueComparator.makeUnorderedValueSet();
+    auto callback = [&values](const Value& val) { values.insert(val); };
+    Document doc{{"a", Document{{"b", vector<Value>{Value(1), Value(2), Value(3)}}}}};
+    visitAllValuesAtPath(doc, FieldPath("a.b"), callback);
+    ASSERT_EQ(values.size(), 3UL);
+    ASSERT_EQ(values.count(Value(1)), 1UL);
+    ASSERT_EQ(values.count(Value(2)), 1UL);
+    ASSERT_EQ(values.count(Value(3)), 1UL);
+}
+
+TEST(VisitAllValuesAtPathTest, ObjectWithArrayOfSubobjectsWithScalarValue) {
+    auto values = kDefaultValueComparator.makeUnorderedValueSet();
+    auto callback = [&values](const Value& val) { values.insert(val); };
+    Document doc{
+        {"a", vector<Document>{Document{{"b", 1}}, Document{{"b", 2}}, Document{{"b", 3}}}}};
+    visitAllValuesAtPath(doc, FieldPath("a.b"), callback);
+    ASSERT_EQ(values.size(), 3UL);
+    ASSERT_EQ(values.count(Value(1)), 1UL);
+    ASSERT_EQ(values.count(Value(2)), 1UL);
+    ASSERT_EQ(values.count(Value(3)), 1UL);
+}
+
+TEST(VisitAllValuesAtPathTest, ObjectWithArrayOfSubobjectsWithArrayValues) {
+    auto values = kDefaultValueComparator.makeUnorderedValueSet();
+    auto callback = [&values](const Value& val) { values.insert(val); };
+    Document doc{{"a",
+                  vector<Document>{Document{{"b", vector<Value>{Value(1), Value(2)}}},
+                                   Document{{"b", vector<Value>{Value(2), Value(3)}}},
+                                   Document{{"b", vector<Value>{Value(3), Value(1)}}}}}};
+    visitAllValuesAtPath(doc, FieldPath("a.b"), callback);
+    ASSERT_EQ(values.size(), 3UL);
+    ASSERT_EQ(values.count(Value(1)), 1UL);
+    ASSERT_EQ(values.count(Value(2)), 1UL);
+    ASSERT_EQ(values.count(Value(3)), 1UL);
+}
+
+TEST(VisitAllValuesAtPathTest, ObjectWithTwoDimensionalArrayOfSubobjects) {
+    auto values = kDefaultValueComparator.makeUnorderedValueSet();
+    auto callback = [&values](const Value& val) { values.insert(val); };
+    Document doc(fromjson("{a: [[{b: 0}, {b: 1}], [{b: 2}, {b: 3}]]}"));
+    visitAllValuesAtPath(doc, FieldPath("a.b"), callback);
+    ASSERT_EQ(values.size(), 0UL);
+}
+
+TEST(VisitAllValuesAtPathTest, ObjectWithDiverseStructure) {
+    auto values = kDefaultValueComparator.makeUnorderedValueSet();
+    auto callback = [&values](const Value& val) { values.insert(val); };
+    Document doc(
+        fromjson("{a: ["
+                 "     {b: 0},"
+                 "     [{b: 1}, {b: {c: -1}}],"
+                 "     'no b here!',"
+                 "     {b: [{c: -2}, 'no c here!']},"
+                 "     {b: {c: [-3, -4]}}"
+                 "]}"));
+    visitAllValuesAtPath(doc, FieldPath("a.b.c"), callback);
+    ASSERT_EQ(values.size(), 3UL);
+    ASSERT_EQ(values.count(Value(-2)), 1UL);
+    ASSERT_EQ(values.count(Value(-3)), 1UL);
+    ASSERT_EQ(values.count(Value(-4)), 1UL);
+}
+
+TEST(VisitAllValuesAtPathTest, AcceptsNumericFieldNames) {
+    auto values = kDefaultValueComparator.makeUnorderedValueSet();
+    auto callback = [&values](const Value& val) { values.insert(val); };
+    Document doc{{"a", Document{{"0", 1}}}};
+    visitAllValuesAtPath(doc, FieldPath("a.0"), callback);
+    ASSERT_EQ(values.size(), 1UL);
+    ASSERT_EQ(values.count(Value(1)), 1UL);
+}
+
+TEST(VisitAllValuesAtPathTest, UsesNumericFieldNameToExtractElementFromArray) {
+    auto values = kDefaultValueComparator.makeUnorderedValueSet();
+    auto callback = [&values](const Value& val) { values.insert(val); };
+    Document doc{{"a", vector<Value>{Value(1), Value(Document{{"0", 1}})}}};
+    visitAllValuesAtPath(doc, FieldPath("a.0"), callback);
+    ASSERT_EQ(values.size(), 1UL);
+    ASSERT_EQ(values.count(Value(1)), 1UL);
+}
+
+TEST(VisitAllValuesAtPathTest, TreatsNegativeIndexAsFieldName) {
+    auto values = kDefaultValueComparator.makeUnorderedValueSet();
+    auto callback = [&values](const Value& val) { values.insert(val); };
+    Document doc{
+        {"a",
+         vector<Value>{
+             Value(0), Value(1), Value(Document{{"-1", "target"_sd}}), Value(Document{{"b", 3}})}}};
+    visitAllValuesAtPath(doc, FieldPath("a.-1"), callback);
+    ASSERT_EQ(values.size(), 1UL);
+    ASSERT_EQ(values.count(Value("target"_sd)), 1UL);
+}
+
+TEST(VisitAllValuesAtPathTest, ExtractsNoValuesFromOutOfBoundsIndex) {
+    auto values = kDefaultValueComparator.makeUnorderedValueSet();
+    auto callback = [&values](const Value& val) { values.insert(val); };
+    Document doc{
+        {"a", vector<Value>{Value(1), Value(Document{{"b", 2}}), Value(Document{{"10", 3}})}}};
+    visitAllValuesAtPath(doc, FieldPath("a.10"), callback);
+    ASSERT_EQ(values.size(), 0UL);
+}
+
+TEST(VisitAllValuesAtPathTest, DoesNotTreatHexStringAsIndexSpecification) {
+    auto values = kDefaultValueComparator.makeUnorderedValueSet();
+    auto callback = [&values](const Value& val) { values.insert(val); };
+    Document doc{{"a",
+                  vector<Value>{Value(1),
+                                Value(Document{{"0x2", 2}}),
+                                Value(Document{{"NOT THIS ONE", 3}})}}};
+    visitAllValuesAtPath(doc, FieldPath("a.0x2"), callback);
+    ASSERT_EQ(values.size(), 1UL);
+    ASSERT_EQ(values.count(Value(2)), 1UL);
+}
+
+TEST(VisitAllValuesAtPathTest, DoesNotAcceptLeadingPlusAsArrayIndex) {
+    auto values = kDefaultValueComparator.makeUnorderedValueSet();
+    auto callback = [&values](const Value& val) { values.insert(val); };
+    Document doc{{"a",
+                  vector<Value>{
+                      Value(1), Value(Document{{"+2", 2}}), Value(Document{{"NOT THIS ONE", 3}})}}};
+    visitAllValuesAtPath(doc, FieldPath("a.+2"), callback);
+    ASSERT_EQ(values.size(), 1UL);
+    ASSERT_EQ(values.count(Value(2)), 1UL);
+}
+
+TEST(VisitAllValuesAtPathTest, DoesNotAcceptTrailingCharactersForArrayIndex) {
+    auto values = kDefaultValueComparator.makeUnorderedValueSet();
+    auto callback = [&values](const Value& val) { values.insert(val); };
+    Document doc{{"a",
+                  vector<Value>{Value(1),
+                                Value(Document{{"2xyz", 2}}),
+                                Value(Document{{"NOT THIS ONE", 3}})}}};
+    visitAllValuesAtPath(doc, FieldPath("a.2xyz"), callback);
+    ASSERT_EQ(values.size(), 1UL);
+    ASSERT_EQ(values.count(Value(2)), 1UL);
+}
+
+TEST(VisitAllValuesAtPathTest, DoesNotAcceptNonDigitsForArrayIndex) {
+    auto values = kDefaultValueComparator.makeUnorderedValueSet();
+    auto callback = [&values](const Value& val) { values.insert(val); };
+    Document doc{{"a",
+                  vector<Value>{Value(1),
+                                Value(Document{{"2x4", 2}}),
+                                Value(Document{{"NOT THIS ONE", 3}})}}};
+    visitAllValuesAtPath(doc, FieldPath("a.2x4"), callback);
+    ASSERT_EQ(values.size(), 1UL);
+    ASSERT_EQ(values.count(Value(2)), 1UL);
+}
+
+TEST(VisitAllValuesAtPathTest,
+     DoesExtractNestedValuesFromWithinArraysTraversedWithPositionalPaths) {
+    auto values = kDefaultValueComparator.makeUnorderedValueSet();
+    auto callback = [&values](const Value& val) { values.insert(val); };
+    Document doc{
+        {"a", vector<Value>{Value(1), Value(Document{{"2", 2}}), Value(Document{{"target", 3}})}}};
+    visitAllValuesAtPath(doc, FieldPath("a.2.target"), callback);
+    ASSERT_EQ(values.size(), 1UL);
+    ASSERT_EQ(values.count(Value(3)), 1UL);
+}
+
+TEST(VisitAllValuesAtPathTest, DoesExpandMultiplePositionalPathSpecifications) {
+    auto values = kDefaultValueComparator.makeUnorderedValueSet();
+    auto callback = [&values](const Value& val) { values.insert(val); };
+    Document doc(fromjson("{a: [[{b: '(0, 0)'}, {b: '(0, 1)'}], [{b: '(1, 0)'}, {b: '(1, 1)'}]]}"));
+    visitAllValuesAtPath(doc, FieldPath("a.1.0.b"), callback);
+    ASSERT_EQ(values.size(), 1UL);
+    ASSERT_EQ(values.count(Value("(1, 0)"_sd)), 1UL);
+}
+
+TEST(VisitAllValuesAtPathTest, DoesAcceptNumericInitialField) {
+    auto values = kDefaultValueComparator.makeUnorderedValueSet();
+    auto callback = [&values](const Value& val) { values.insert(val); };
+    Document doc{{"a", 1}, {"0", 2}};
+    visitAllValuesAtPath(doc, FieldPath("0"), callback);
+    ASSERT_EQ(values.size(), 1UL);
+    ASSERT_EQ(values.count(Value(2)), 1UL);
+}
+
+TEST(VisitAllValuesAtPathTest, DoesExpandArrayFoundAfterPositionalSpecification) {
+    auto values = kDefaultValueComparator.makeUnorderedValueSet();
+    auto callback = [&values](const Value& val) { values.insert(val); };
+    Document doc(fromjson("{a: [[{b: '(0, 0)'}, {b: '(0, 1)'}], [{b: '(1, 0)'}, {b: '(1, 1)'}]]}"));
+    visitAllValuesAtPath(doc, FieldPath("a.1.b"), callback);
+    ASSERT_EQ(values.size(), 2UL);
+    ASSERT_EQ(values.count(Value("(1, 0)"_sd)), 1UL);
+    ASSERT_EQ(values.count(Value("(1, 1)"_sd)), 1UL);
+}
+
+TEST(VisitAllValuesAtPathTest, DoesNotAddMissingValueToResults) {
+    auto values = kDefaultValueComparator.makeUnorderedValueSet();
+    auto callback = [&values](const Value& val) { values.insert(val); };
+    Document doc{{"a", Value()}};
+    visitAllValuesAtPath(doc, FieldPath("a"), callback);
+    ASSERT_EQ(values.size(), 0UL);
+}
+
+TEST(VisitAllValuesAtPathTest, DoesNotAddMissingValueWithinArrayToResults) {
+    auto values = kDefaultValueComparator.makeUnorderedValueSet();
+    auto callback = [&values](const Value& val) { values.insert(val); };
+    Document doc{{"a", vector<Value>{Value(1), Value(), Value(2)}}};
+    visitAllValuesAtPath(doc, FieldPath("a"), callback);
+    ASSERT_EQ(values.size(), 2UL);
+    ASSERT_EQ(values.count(Value(1)), 1UL);
+    ASSERT_EQ(values.count(Value(2)), 1UL);
+}
+
+}  // namespace
+}  // namespace document_path_support
+}  // namespace mongo