SERVER-26964 Make FieldPath more efficient

8 files changed, 61 insertions, 179 deletions

diff --git a/src/mongo/db/pipeline/document.cpp b/src/mongo/db/pipeline/document.cpp
index 51fd08d4d20..627bafdfd78 100644
--- a/src/mongo/db/pipeline/document.cpp
+++ b/src/mongo/db/pipeline/document.cpp
@@ -335,7 +335,7 @@ static Value getNestedFieldHelper(const Document& doc,
                                   const FieldPath& fieldNames,
                                   vector<Position>* positions,
                                   size_t level) {
-    const string& fieldName = fieldNames.getFieldName(level);
+    const auto fieldName = fieldNames.getFieldName(level);
     const Position pos = doc.positionOf(fieldName);
 
     if (!pos.found())
diff --git a/src/mongo/db/pipeline/document_source.cpp b/src/mongo/db/pipeline/document_source.cpp
index b5e5309d9e6..b83ec851ebe 100644
--- a/src/mongo/db/pipeline/document_source.cpp
+++ b/src/mongo/db/pipeline/document_source.cpp
@@ -110,8 +110,7 @@ std::set<std::string> extractModifiedDependencies(const std::set<std::string>& d
     // should not be included in the modified dependencies.
     for (auto&& dependency : dependencies) {
         bool preserved = false;
-        auto depAsPath = FieldPath(dependency);
-        auto firstField = depAsPath.getFieldName(0);
+        auto firstField = FieldPath::extractFirstFieldFromDottedPath(dependency).toString();
         // If even a prefix is preserved, the path is preserved, so search for any prefixes of
         // 'dependency' as well. 'preservedPaths' is an *ordered* set, so we only have to search the
         // range ['firstField', 'dependency'] to find any prefixes of 'dependency'.
diff --git a/src/mongo/db/pipeline/document_value_test.cpp b/src/mongo/db/pipeline/document_value_test.cpp
index f8f451bede1..c0182cb2fc4 100644
--- a/src/mongo/db/pipeline/document_value_test.cpp
+++ b/src/mongo/db/pipeline/document_value_test.cpp
@@ -206,14 +206,14 @@ public:
         ASSERT_VALUE_EQ(md.peek()["x"]["y"]["z"], Value("nested"));
 
         // Set a nested field using setNestedField
-        FieldPath xxyyzz = string("xx.yy.zz");
+        FieldPath xxyyzz("xx.yy.zz");
         md.setNestedField(xxyyzz, Value("nested"));
         ASSERT_VALUE_EQ(md.peek().getNestedField(xxyyzz), Value("nested"));
 
         // Set a nested fields through an existing empty document
         md["xxx"] = Value(Document());
         md["xxx"]["yyy"] = Value(Document());
-        FieldPath xxxyyyzzz = string("xxx.yyy.zzz");
+        FieldPath xxxyyyzzz("xxx.yyy.zzz");
         md.setNestedField(xxxyyyzzz, Value("nested"));
         ASSERT_VALUE_EQ(md.peek().getNestedField(xxxyyyzzz), Value("nested"));
 
diff --git a/src/mongo/db/pipeline/field_path.cpp b/src/mongo/db/pipeline/field_path.cpp
index 4fa7d699b52..b54fbe88b2c 100644
--- a/src/mongo/db/pipeline/field_path.cpp
+++ b/src/mongo/db/pipeline/field_path.cpp
@@ -35,84 +35,36 @@
 
 namespace mongo {
 
-using std::ostream;
 using std::string;
-using std::stringstream;
 using std::vector;
 
-using namespace mongoutils;
-
-const char FieldPath::prefix[] = "$";
-
-std::string FieldPath::getFullyQualifiedPath(StringData prefix, StringData suffix) {
+string FieldPath::getFullyQualifiedPath(StringData prefix, StringData suffix) {
     if (prefix.empty()) {
         return suffix.toString();
     }
+
     return str::stream() << prefix << "." << suffix;
 }
 
-FieldPath::FieldPath(const vector<string>& fieldNames) {
-    massert(16409, "FieldPath cannot be constructed from an empty vector.", !fieldNames.empty());
-    _fieldNames.reserve(fieldNames.size());
-    for (auto fieldName : fieldNames) {
-        pushFieldName(fieldName);
+FieldPath::FieldPath(std::string inputPath)
+    : _fieldPath(std::move(inputPath)), _fieldPathDotPosition{string::npos} {
+    uassert(40352, "FieldPath cannot be constructed with empty string", !_fieldPath.empty());
+    uassert(40353, "FieldPath must not end with a '.'.", _fieldPath[_fieldPath.size() - 1] != '.');
+
+    // Store index delimiter position for use in field lookup.
+    size_t dotPos;
+    size_t startPos = 0;
+    while (string::npos != (dotPos = _fieldPath.find('.', startPos))) {
+        _fieldPathDotPosition.push_back(dotPos);
+        startPos = dotPos + 1;
     }
-}
-
-FieldPath::FieldPath(const string& fieldPath) {
-    // Split 'fieldPath' at the dots.
-    size_t startpos = 0;
-    while (true) {
-        // Find the next dot.
-        const size_t dotpos = fieldPath.find('.', startpos);
 
-        // If there are no more dots, use the remainder of the string.
-        if (dotpos == fieldPath.npos) {
-            string lastFieldName = fieldPath.substr(startpos, dotpos);
-            pushFieldName(lastFieldName);
-            break;
-        }
+    _fieldPathDotPosition.push_back(_fieldPath.size());
 
-        // Use the string up to the dot.
-        const size_t length = dotpos - startpos;
-        string nextFieldName = fieldPath.substr(startpos, length);
-        pushFieldName(nextFieldName);
-
-        // Start the next search after the dot.
-        startpos = dotpos + 1;
+    // Validate fields.
+    for (size_t i = 0; i < getPathLength(); ++i) {
+        uassertValidFieldName(getFieldName(i));
     }
-    verify(getPathLength() > 0);
-}
-
-string FieldPath::fullPath() const {
-    stringstream ss;
-    const bool includePrefix = false;
-    writePath(ss, includePrefix);
-    return ss.str();
-}
-
-string FieldPath::fullPathWithPrefix() const {
-    stringstream ss;
-    const bool includePrefix = true;
-    writePath(ss, includePrefix);
-    return ss.str();
-}
-
-void FieldPath::writePath(ostream& outStream, bool includePrefix) const {
-    if (includePrefix)
-        outStream << prefix;
-
-    const size_t n = _fieldNames.size();
-
-    verify(n > 0);
-    outStream << _fieldNames[0];
-    for (size_t i = 1; i < n; ++i)
-        outStream << '.' << _fieldNames[i];
-}
-
-FieldPath FieldPath::tail() const {
-    vector<string> allButFirst(_fieldNames.begin() + 1, _fieldNames.end());
-    return FieldPath(allButFirst);
 }
 
 void FieldPath::uassertValidFieldName(StringData fieldName) {
@@ -123,9 +75,4 @@ void FieldPath::uassertValidFieldName(StringData fieldName) {
     uassert(
         16412, "FieldPath field names may not contain '.'.", fieldName.find('.') == string::npos);
 }
-
-void FieldPath::pushFieldName(const string& fieldName) {
-    uassertValidFieldName(fieldName);
-    _fieldNames.push_back(fieldName);
-}
 }
diff --git a/src/mongo/db/pipeline/field_path.h b/src/mongo/db/pipeline/field_path.h
index 8ac025f899e..2a93e607078 100644
--- a/src/mongo/db/pipeline/field_path.h
+++ b/src/mongo/db/pipeline/field_path.h
@@ -28,7 +28,6 @@
 
 #pragma once
 
-#include <iosfwd>
 #include <string>
 #include <vector>
 
@@ -57,11 +56,7 @@ public:
      * Returns the substring of 'path' until the first '.', or the entire string if there is no '.'.
      */
     static StringData extractFirstFieldFromDottedPath(StringData path) {
-        const auto firstDot = path.find('.');
-        if (firstDot == std::string::npos) {
-            return path;
-        }
-        return path.substr(0, firstDot);
+        return path.substr(0, path.find('.'));
     }
 
     /**
@@ -69,67 +64,58 @@ public:
      *
      * Field names are validated using uassertValidFieldName().
      */
-    FieldPath(const std::string& fieldPath);
-
-    /**
-     * Throws a UserException if 'fieldNames' is empty or if any of the field names fail validation.
-     *
-     * Field names are validated using uassertValidFieldName().
-     */
-    FieldPath(const std::vector<std::string>& fieldNames);
+    /* implicit */ FieldPath(std::string inputPath);
+    /* implicit */ FieldPath(StringData inputPath) : FieldPath(inputPath.toString()) {}
+    /* implicit */ FieldPath(const char* inputPath) : FieldPath(std::string(inputPath)) {}
 
     /**
      * Returns the number of path elements in the field path.
      */
     size_t getPathLength() const {
-        return _fieldNames.size();
+        return _fieldPathDotPosition.size() - 1;
     }
 
     /**
      * Return the ith field name from this path using zero-based indexes.
      */
-    const std::string& getFieldName(size_t i) const {
+    StringData getFieldName(size_t i) const {
         dassert(i < getPathLength());
-        return _fieldNames[i];
+        const auto begin = _fieldPathDotPosition[i] + 1;
+        const auto end = _fieldPathDotPosition[i + 1];
+        return StringData(&_fieldPath[begin], end - begin);
     }
 
     /**
      * Returns the full path, not including the prefix 'FieldPath::prefix'.
      */
-    std::string fullPath() const;
+    const std::string& fullPath() const {
+        return _fieldPath;
+    }
 
     /**
      * Returns the full path, including the prefix 'FieldPath::prefix'.
      */
-    std::string fullPathWithPrefix() const;
-
-    /**
-     * Write the full path to 'outStream', including the prefix 'FieldPath::prefix' if
-     * 'includePrefix' is specified.
-     */
-    void writePath(std::ostream& outStream, bool includePrefix) const;
-
-    static const char* getPrefix() {
-        return prefix;
+    std::string fullPathWithPrefix() const {
+        return prefix + _fieldPath;
     }
-
     /**
      * A FieldPath like this but missing the first element (useful for recursion).
      * Precondition getPathLength() > 1.
      */
-    FieldPath tail() const;
+    FieldPath tail() const {
+        massert(16409, "FieldPath::tail() called on single element path", getPathLength() > 1);
+        return {_fieldPath.substr(_fieldPathDotPosition[1] + 1)};
+    }
 
 private:
-    /**
-     * Push a new field name to the back of the vector of names comprising the field path.
-     *
-     * Throws a UserException if 'fieldName' does not pass validation done by
-     * uassertValidFieldName().
-     */
-    void pushFieldName(const std::string& fieldName);
+    static const char prefix = '$';
 
-    static const char prefix[];
+    // Contains the full field path, with each field delimited by a '.' character.
+    std::string _fieldPath;
 
-    std::vector<std::string> _fieldNames;
+    // Contains the position of field delimiter dots in '_fieldPath'. The first element contains
+    // string::npos (which evaluates to -1) and the last contains _fieldPath.size() to facilitate
+    // lookup.
+    std::vector<size_t> _fieldPathDotPosition;
 };
 }
diff --git a/src/mongo/db/pipeline/field_path_test.cpp b/src/mongo/db/pipeline/field_path_test.cpp
index 83df46410ae..6886e0116a7 100644
--- a/src/mongo/db/pipeline/field_path_test.cpp
+++ b/src/mongo/db/pipeline/field_path_test.cpp
@@ -45,15 +45,6 @@ public:
     }
 };
 
-/** FieldPath constructed from empty vector. */
-class EmptyVector {
-public:
-    void run() {
-        vector<string> vec;
-        ASSERT_THROWS(FieldPath path(vec), MsgAssertionException);
-    }
-};
-
 /** FieldPath constructed from a simple string (without dots). */
 class Simple {
 public:
@@ -66,18 +57,6 @@ public:
     }
 };
 
-/** FieldPath constructed from a single element vector. */
-class SimpleVector {
-public:
-    void run() {
-        vector<string> vec(1, "foo");
-        FieldPath path(vec);
-        ASSERT_EQUALS(1U, path.getPathLength());
-        ASSERT_EQUALS("foo", path.getFieldName(0));
-        ASSERT_EQUALS("foo", path.fullPath());
-    }
-};
-
 /** FieldPath consisting of a '$' character. */
 class DollarSign {
 public:
@@ -107,28 +86,6 @@ public:
     }
 };
 
-/** FieldPath constructed from a single element vector containing a dot. */
-class VectorWithDot {
-public:
-    void run() {
-        vector<string> vec(1, "fo.o");
-        ASSERT_THROWS(FieldPath path(vec), UserException);
-    }
-};
-
-/** FieldPath constructed from a two element vector. */
-class TwoFieldVector {
-public:
-    void run() {
-        vector<string> vec;
-        vec.push_back("foo");
-        vec.push_back("bar");
-        FieldPath path(vec);
-        ASSERT_EQUALS(2U, path.getPathLength());
-        ASSERT_EQUALS("foo.bar", path.fullPath());
-    }
-};
-
 /** FieldPath with a '$' prefix in the second field. */
 class DollarSignPrefixSecondField {
 public:
@@ -174,6 +131,14 @@ public:
     }
 };
 
+/** FieldPath constructed with only dots. */
+class OnlyDots {
+public:
+    void run() {
+        ASSERT_THROWS(FieldPath path("..."), UserException);
+    }
+};
+
 /** FieldPath constructed from a string with one letter between two dots. */
 class LetterBetweenDots {
 public:
@@ -192,17 +157,6 @@ public:
     }
 };
 
-/** FieldPath constructed with a vector containing a null character. */
-class VectorNullCharacter {
-public:
-    void run() {
-        vector<string> vec;
-        vec.push_back("foo");
-        vec.push_back(string("b\0r", 3));
-        ASSERT_THROWS(FieldPath path(vec), UserException);
-    }
-};
-
 /** Tail of a FieldPath. */
 class Tail {
 public:
@@ -228,22 +182,18 @@ public:
     All() : Suite("field_path") {}
     void setupTests() {
         add<Empty>();
-        add<EmptyVector>();
         add<Simple>();
-        add<SimpleVector>();
         add<DollarSign>();
         add<DollarSignPrefix>();
         add<Dotted>();
-        add<VectorWithDot>();
-        add<TwoFieldVector>();
         add<DollarSignPrefixSecondField>();
         add<TwoDotted>();
         add<TerminalDot>();
         add<PrefixDot>();
         add<AdjacentDots>();
+        add<OnlyDots>();
         add<LetterBetweenDots>();
         add<NullCharacter>();
-        add<VectorNullCharacter>();
         add<Tail>();
         add<TailThreeFields>();
     }
diff --git a/src/mongo/db/pipeline/parsed_add_fields.cpp b/src/mongo/db/pipeline/parsed_add_fields.cpp
index 3f9b5427a32..2bca98f21bd 100644
--- a/src/mongo/db/pipeline/parsed_add_fields.cpp
+++ b/src/mongo/db/pipeline/parsed_add_fields.cpp
@@ -66,7 +66,7 @@ void ParsedAddFields::parse(const BSONObj& spec, const VariablesParseState& vari
                 auto remainingPath = FieldPath(elem.fieldName());
                 auto child = _root.get();
                 while (remainingPath.getPathLength() > 1) {
-                    child = child->addOrGetChild(remainingPath.getFieldName(0));
+                    child = child->addOrGetChild(remainingPath.getFieldName(0).toString());
                     remainingPath = remainingPath.tail();
                 }
                 // It is illegal to construct an empty FieldPath, so the above loop ends one
@@ -103,7 +103,7 @@ bool ParsedAddFields::parseObjectAsExpression(StringData pathToObject,
         // This is an expression like {$add: [...]}. We have already verified that it has only one
         // field.
         invariant(objSpec.nFields() == 1);
-        _root->addComputedField(pathToObject.toString(),
+        _root->addComputedField(pathToObject,
                                 Expression::parseExpression(objSpec, variablesParseState));
         return true;
     }
diff --git a/src/mongo/db/pipeline/parsed_inclusion_projection.cpp b/src/mongo/db/pipeline/parsed_inclusion_projection.cpp
index 77fccf8107f..abac372be7e 100644
--- a/src/mongo/db/pipeline/parsed_inclusion_projection.cpp
+++ b/src/mongo/db/pipeline/parsed_inclusion_projection.cpp
@@ -206,7 +206,7 @@ void InclusionNode::addComputedField(const FieldPath& path, boost::intrusive_ptr
         _orderToProcessAdditionsAndChildren.push_back(fieldName);
         return;
     }
-    addOrGetChild(path.getFieldName(0))->addComputedField(path.tail(), expr);
+    addOrGetChild(path.getFieldName(0).toString())->addComputedField(path.tail(), expr);
 }
 
 void InclusionNode::addIncludedField(const FieldPath& path) {
@@ -214,7 +214,7 @@ void InclusionNode::addIncludedField(const FieldPath& path) {
         _inclusions.insert(path.fullPath());
         return;
     }
-    addOrGetChild(path.getFieldName(0))->addIncludedField(path.tail());
+    addOrGetChild(path.getFieldName(0).toString())->addIncludedField(path.tail());
 }
 
 InclusionNode* InclusionNode::addOrGetChild(std::string field) {
@@ -299,7 +299,7 @@ void ParsedInclusionProjection::parse(const BSONObj& spec,
                 auto remainingPath = FieldPath(elem.fieldName());
                 auto child = _root.get();
                 while (remainingPath.getPathLength() > 1) {
-                    child = child->addOrGetChild(remainingPath.getFieldName(0));
+                    child = child->addOrGetChild(remainingPath.getFieldName(0).toString());
                     remainingPath = remainingPath.tail();
                 }
                 // It is illegal to construct an empty FieldPath, so the above loop ends one
@@ -350,7 +350,7 @@ bool ParsedInclusionProjection::parseObjectAsExpression(
         // This is an expression like {$add: [...]}. We have already verified that it has only one
         // field.
         invariant(objSpec.nFields() == 1);
-        _root->addComputedField(pathToObject.toString(),
+        _root->addComputedField(pathToObject,
                                 Expression::parseExpression(objSpec, variablesParseState));
         return true;
     }