SERVER-23114 Compute multikey paths in 2dsphere index key generation.

Propagates information about the prefixes of the indexed fields that
cause the index to be multikey as a result of inserting the generated
keys.

3 files changed, 109 insertions, 25 deletions

diff --git a/src/mongo/db/bson/dotted_path_support.cpp b/src/mongo/db/bson/dotted_path_support.cpp
index cfb10c5a39f..1a9fda88501 100644
--- a/src/mongo/db/bson/dotted_path_support.cpp
+++ b/src/mongo/db/bson/dotted_path_support.cpp
@@ -50,7 +50,9 @@ template <typename BSONElementColl>
 void _extractAllElementsAlongPath(const BSONObj& obj,
                                   StringData path,
                                   BSONElementColl& elements,
-                                  bool expandArrayOnTrailingField) {
+                                  bool expandArrayOnTrailingField,
+                                  size_t depth,
+                                  std::set<size_t>* arrayComponents) {
     BSONElement e = obj.getField(path);
 
     if (e.eoo()) {
@@ -62,8 +64,12 @@ void _extractAllElementsAlongPath(const BSONObj& obj,
             BSONElement e = obj.getField(left);
 
             if (e.type() == Object) {
-                _extractAllElementsAlongPath(
-                    e.embeddedObject(), next, elements, expandArrayOnTrailingField);
+                _extractAllElementsAlongPath(e.embeddedObject(),
+                                             next,
+                                             elements,
+                                             expandArrayOnTrailingField,
+                                             depth + 1,
+                                             arrayComponents);
             } else if (e.type() == Array) {
                 bool allDigits = false;
                 if (next.size() > 0 && std::isdigit(next[0])) {
@@ -73,15 +79,28 @@ void _extractAllElementsAlongPath(const BSONObj& obj,
                     allDigits = temp == next.size() || next[temp] == '.';
                 }
                 if (allDigits) {
-                    _extractAllElementsAlongPath(
-                        e.embeddedObject(), next, elements, expandArrayOnTrailingField);
+                    _extractAllElementsAlongPath(e.embeddedObject(),
+                                                 next,
+                                                 elements,
+                                                 expandArrayOnTrailingField,
+                                                 depth + 1,
+                                                 arrayComponents);
                 } else {
+                    size_t nArrElems = 0;
                     BSONObjIterator i(e.embeddedObject());
                     while (i.more()) {
                         BSONElement e2 = i.next();
                         if (e2.type() == Object || e2.type() == Array)
-                            _extractAllElementsAlongPath(
-                                e2.embeddedObject(), next, elements, expandArrayOnTrailingField);
+                            _extractAllElementsAlongPath(e2.embeddedObject(),
+                                                         next,
+                                                         elements,
+                                                         expandArrayOnTrailingField,
+                                                         depth + 1,
+                                                         arrayComponents);
+                        ++nArrElems;
+                    }
+                    if (arrayComponents && nArrElems > 1) {
+                        arrayComponents->insert(depth);
                     }
                 }
             } else {
@@ -90,9 +109,15 @@ void _extractAllElementsAlongPath(const BSONObj& obj,
         }
     } else {
         if (e.type() == Array && expandArrayOnTrailingField) {
+            size_t nArrElems = 0;
             BSONObjIterator i(e.embeddedObject());
-            while (i.more())
+            while (i.more()) {
                 elements.insert(i.next());
+                ++nArrElems;
+            }
+            if (arrayComponents && nArrElems > 1) {
+                arrayComponents->insert(depth);
+            }
         } else {
             elements.insert(e);
         }
@@ -142,15 +167,21 @@ BSONElement extractElementAtPathOrArrayAlongPath(const BSONObj& obj, const char*
 void extractAllElementsAlongPath(const BSONObj& obj,
                                  StringData path,
                                  BSONElementSet& elements,
-                                 bool expandArrayOnTrailingField) {
-    _extractAllElementsAlongPath(obj, path, elements, expandArrayOnTrailingField);
+                                 bool expandArrayOnTrailingField,
+                                 std::set<size_t>* arrayComponents) {
+    const size_t initialDepth = 0;
+    _extractAllElementsAlongPath(
+        obj, path, elements, expandArrayOnTrailingField, initialDepth, arrayComponents);
 }
 
 void extractAllElementsAlongPath(const BSONObj& obj,
                                  StringData path,
                                  BSONElementMSet& elements,
-                                 bool expandArrayOnTrailingField) {
-    _extractAllElementsAlongPath(obj, path, elements, expandArrayOnTrailingField);
+                                 bool expandArrayOnTrailingField,
+                                 std::set<size_t>* arrayComponents) {
+    const size_t initialDepth = 0;
+    _extractAllElementsAlongPath(
+        obj, path, elements, expandArrayOnTrailingField, initialDepth, arrayComponents);
 }
 
 BSONObj extractElementsBasedOnTemplate(const BSONObj& obj,
diff --git a/src/mongo/db/bson/dotted_path_support.h b/src/mongo/db/bson/dotted_path_support.h
index 9e2a3c9e9d0..c9c6676c75a 100644
--- a/src/mongo/db/bson/dotted_path_support.h
+++ b/src/mongo/db/bson/dotted_path_support.h
@@ -82,25 +82,31 @@ BSONElement extractElementAtPathOrArrayAlongPath(const BSONObj& obj, const char*
  * The 'path' can be specified using a dotted notation in order to traverse through embedded objects
  * and array elements.
  *
+ * This function fills 'arrayComponents' with the positions (starting at 0) of 'path' corresponding
+ * to array values with multiple 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.
+ *   would be added to the set. 'arrayComponents' would be set as std::set<size_t>{0U}.
  *
  *   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.
+ *   {b: 2}, and {b: 3} would be added to the set and 'arrayComponents' would be set as
+ *   std::set<size_t>{0U, 1U} if 'expandArrayOnTrailingField' is true. The elements {b: [1, 2]} and
+ *   {b: [2, 3]} would be added to the set and 'arrayComponents' would be set as
+ *   std::set<size_t>{0U} if 'expandArrayOnTrailingField' is false.
  */
 void extractAllElementsAlongPath(const BSONObj& obj,
                                  StringData path,
                                  BSONElementSet& elements,
-                                 bool expandArrayOnTrailingField = true);
+                                 bool expandArrayOnTrailingField = true,
+                                 std::set<std::size_t>* arrayComponents = nullptr);
 
 void extractAllElementsAlongPath(const BSONObj& obj,
                                  StringData path,
                                  BSONElementMSet& elements,
-                                 bool expandArrayOnTrailingField = true);
+                                 bool expandArrayOnTrailingField = true,
+                                 std::set<std::size_t>* arrayComponents = nullptr);
 
 /**
  * Returns an owned BSONObj with elements in the same order as they appear in the 'pattern' object
diff --git a/src/mongo/db/bson/dotted_path_support_test.cpp b/src/mongo/db/bson/dotted_path_support_test.cpp
index 78d3253d8b5..4473721c3d6 100644
--- a/src/mongo/db/bson/dotted_path_support_test.cpp
+++ b/src/mongo/db/bson/dotted_path_support_test.cpp
@@ -28,6 +28,7 @@
 
 #include "mongo/platform/basic.h"
 
+#include <set>
 #include <vector>
 
 #include "mongo/bson/bsonelement.h"
@@ -139,14 +140,42 @@ void assertBSONElementSetsAreEqual(const std::vector<BSONObj>& expectedObjs,
     }
 }
 
+void dumpArrayComponents(const std::set<size_t>& arrayComponents, StringBuilder* sb) {
+    *sb << "[ ";
+    bool firstIteration = true;
+    for (const auto pos : arrayComponents) {
+        if (!firstIteration) {
+            *sb << ", ";
+        }
+        *sb << pos;
+        firstIteration = false;
+    }
+    *sb << " ]";
+}
+
+void assertArrayComponentsAreEqual(const std::set<size_t>& expectedArrayComponents,
+                                   const std::set<size_t>& actualArrayComponents) {
+    if (expectedArrayComponents != actualArrayComponents) {
+        StringBuilder sb;
+        sb << "Expected: ";
+        dumpArrayComponents(expectedArrayComponents, &sb);
+        sb << ", Actual: ";
+        dumpArrayComponents(actualArrayComponents, &sb);
+        FAIL(sb.str());
+    }
+}
+
 TEST(ExtractAllElementsAlongPath, NestedObjectWithScalarValue) {
     BSONObj obj = BSON("a" << BSON("b" << 1));
 
     BSONElementSet actualElements;
     const bool expandArrayOnTrailingField = true;
-    dps::extractAllElementsAlongPath(obj, "a.b", actualElements, expandArrayOnTrailingField);
+    std::set<size_t> actualArrayComponents;
+    dps::extractAllElementsAlongPath(
+        obj, "a.b", actualElements, expandArrayOnTrailingField, &actualArrayComponents);
 
     assertBSONElementSetsAreEqual({BSON("" << 1)}, actualElements);
+    assertArrayComponentsAreEqual(std::set<size_t>{}, actualArrayComponents);
 }
 
 TEST(ExtractAllElementsAlongPath, NestedObjectWithEmptyArrayValue) {
@@ -154,9 +183,12 @@ TEST(ExtractAllElementsAlongPath, NestedObjectWithEmptyArrayValue) {
 
     BSONElementSet actualElements;
     const bool expandArrayOnTrailingField = true;
-    dps::extractAllElementsAlongPath(obj, "a.b", actualElements, expandArrayOnTrailingField);
+    std::set<size_t> actualArrayComponents;
+    dps::extractAllElementsAlongPath(
+        obj, "a.b", actualElements, expandArrayOnTrailingField, &actualArrayComponents);
 
     assertBSONElementSetsAreEqual(std::vector<BSONObj>{}, actualElements);
+    assertArrayComponentsAreEqual(std::set<size_t>{}, actualArrayComponents);
 }
 
 TEST(ExtractAllElementsAlongPath, NestedObjectWithSingletonArrayValue) {
@@ -164,9 +196,12 @@ TEST(ExtractAllElementsAlongPath, NestedObjectWithSingletonArrayValue) {
 
     BSONElementSet actualElements;
     const bool expandArrayOnTrailingField = true;
-    dps::extractAllElementsAlongPath(obj, "a.b", actualElements, expandArrayOnTrailingField);
+    std::set<size_t> actualArrayComponents;
+    dps::extractAllElementsAlongPath(
+        obj, "a.b", actualElements, expandArrayOnTrailingField, &actualArrayComponents);
 
     assertBSONElementSetsAreEqual({BSON("" << 1)}, actualElements);
+    assertArrayComponentsAreEqual(std::set<size_t>{}, actualArrayComponents);
 }
 
 TEST(ExtractAllElementsAlongPath, NestedObjectWithArrayValue) {
@@ -174,9 +209,12 @@ TEST(ExtractAllElementsAlongPath, NestedObjectWithArrayValue) {
 
     BSONElementSet actualElements;
     const bool expandArrayOnTrailingField = true;
-    dps::extractAllElementsAlongPath(obj, "a.b", actualElements, expandArrayOnTrailingField);
+    std::set<size_t> actualArrayComponents;
+    dps::extractAllElementsAlongPath(
+        obj, "a.b", actualElements, expandArrayOnTrailingField, &actualArrayComponents);
 
     assertBSONElementSetsAreEqual({BSON("" << 1), BSON("" << 2), BSON("" << 3)}, actualElements);
+    assertArrayComponentsAreEqual({1U}, actualArrayComponents);
 }
 
 TEST(ExtractAllElementsAlongPath, ObjectWithArrayOfSubobjectsWithScalarValue) {
@@ -184,9 +222,12 @@ TEST(ExtractAllElementsAlongPath, ObjectWithArrayOfSubobjectsWithScalarValue) {
 
     BSONElementSet actualElements;
     const bool expandArrayOnTrailingField = true;
-    dps::extractAllElementsAlongPath(obj, "a.b", actualElements, expandArrayOnTrailingField);
+    std::set<size_t> actualArrayComponents;
+    dps::extractAllElementsAlongPath(
+        obj, "a.b", actualElements, expandArrayOnTrailingField, &actualArrayComponents);
 
     assertBSONElementSetsAreEqual({BSON("" << 1), BSON("" << 2), BSON("" << 3)}, actualElements);
+    assertArrayComponentsAreEqual({0U}, actualArrayComponents);
 }
 
 TEST(ExtractAllElementsAlongPath, ObjectWithArrayOfSubobjectsWithArrayValues) {
@@ -196,9 +237,12 @@ TEST(ExtractAllElementsAlongPath, ObjectWithArrayOfSubobjectsWithArrayValues) {
 
     BSONElementSet actualElements;
     const bool expandArrayOnTrailingField = true;
-    dps::extractAllElementsAlongPath(obj, "a.b", actualElements, expandArrayOnTrailingField);
+    std::set<size_t> actualArrayComponents;
+    dps::extractAllElementsAlongPath(
+        obj, "a.b", actualElements, expandArrayOnTrailingField, &actualArrayComponents);
 
     assertBSONElementSetsAreEqual({BSON("" << 1), BSON("" << 2), BSON("" << 3)}, actualElements);
+    assertArrayComponentsAreEqual({0U, 1U}, actualArrayComponents);
 }
 
 TEST(ExtractAllElementsAlongPath,
@@ -208,11 +252,14 @@ TEST(ExtractAllElementsAlongPath,
 
     BSONElementSet actualElements;
     const bool expandArrayOnTrailingField = false;
-    dps::extractAllElementsAlongPath(obj, "a.b", actualElements, expandArrayOnTrailingField);
+    std::set<size_t> actualArrayComponents;
+    dps::extractAllElementsAlongPath(
+        obj, "a.b", actualElements, expandArrayOnTrailingField, &actualArrayComponents);
 
     assertBSONElementSetsAreEqual(
         {BSON("" << BSON_ARRAY(1)), BSON("" << BSON_ARRAY(2)), BSON("" << BSON_ARRAY(3))},
         actualElements);
+    assertArrayComponentsAreEqual({0U}, actualArrayComponents);
 }
 
 }  // namespace