Imported Upstream version 2.6.11upstream/2.6.11

1 files changed, 264 insertions, 0 deletions

diff --git a/src/mongo/db/ops/path_support.cpp b/src/mongo/db/ops/path_support.cpp
new file mode 100644
index 00000000000..d46ad1aa977
--- /dev/null
+++ b/src/mongo/db/ops/path_support.cpp
@@ -0,0 +1,264 @@
+/**
+ *    Copyright (C) 2013 10gen 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/db/ops/path_support.h"
+
+#include "mongo/base/string_data.h"
+#include "mongo/bson/mutable/algorithm.h"
+#include "mongo/bson/mutable/document.h"
+#include "mongo/bson/mutable/element.h"
+#include "mongo/util/assert_util.h"
+#include "mongo/util/mongoutils/str.h"
+
+namespace mongo {
+namespace pathsupport {
+
+    namespace {
+
+        bool isNumeric(const StringData& str, size_t* num) {
+            size_t res = 0;
+            for (size_t i = 0; i < str.size(); ++i) {
+                if (str[i] < '0' || str[i] > '9') {
+                    return false;
+                }
+                else {
+                    res = res * 10 + (str[i] - '0');
+                }
+            }
+            *num = res;
+            return true;
+        }
+
+        Status maybePadTo(mutablebson::Element* elemArray,
+                          size_t sizeRequired) {
+            dassert(elemArray->getType() == Array);
+
+            if (sizeRequired > kMaxPaddingAllowed) {
+                return Status(ErrorCodes::CannotBackfillArray,
+                              mongoutils::str::stream() << "can't backfill array to larger than "
+                                                        << kMaxPaddingAllowed << " elements");
+            }
+
+            size_t currSize = mutablebson::countChildren(*elemArray);
+            if (sizeRequired > currSize) {
+                size_t toPad = sizeRequired - currSize;
+                for (size_t i = 0; i < toPad; i++) {
+                    Status status = elemArray->appendNull("");
+                    if (!status.isOK()) {
+                        return status;
+                    }
+                }
+            }
+            return Status::OK();
+        }
+
+    } // unnamed namespace
+
+    Status findLongestPrefix(const FieldRef& prefix,
+                             mutablebson::Element root,
+                             size_t* idxFound,
+                             mutablebson::Element* elemFound) {
+
+        // If root is empty or the prefix is so, there's no point in looking for a prefix.
+        const size_t prefixSize = prefix.numParts();
+        if (!root.hasChildren() || prefixSize == 0) {
+            return Status(ErrorCodes::NonExistentPath,
+                          "either the document or the path are empty");
+        }
+
+        // Loop through prefix's parts. At each iteration, check that the part ('curr') exists
+        // in 'root' and that the type of the previous part ('prev') allows for children.
+        mutablebson::Element curr = root;
+        mutablebson::Element prev = root;
+        size_t i = 0;
+        size_t numericPart = 0;
+        bool viable = true;
+        for (;i < prefixSize; i++) {
+
+            // If prefix wants to reach 'curr' by applying a non-numeric index to an array
+            // 'prev', or if 'curr' wants to traverse a leaf 'prev', then we'd be in a
+            // non-viable path (see definition on the header file).
+            StringData prefixPart = prefix.getPart(i);
+            prev = curr;
+            switch (curr.getType()) {
+
+            case Object:
+                curr = prev[prefixPart];
+                break;
+
+            case Array:
+                if (!isNumeric(prefixPart, &numericPart)) {
+                    viable = false;
+                } else {
+                    curr = prev[numericPart];
+                }
+                break;
+
+            default:
+                viable = false;
+            }
+
+            // If we couldn't find the next field part of the prefix in the document or if the
+            // field part we're in constitutes a non-viable path, we can stop looking.
+            if (!curr.ok() || !viable) {
+                break;
+            }
+        }
+
+        // We broke out of the loop because one of four things happened. (a) 'prefix' and
+        // 'root' have nothing in common, (b) 'prefix' is not viable in 'root', (c) not all the
+        // parts in 'prefix' exist in 'root', or (d) all parts do. In each case, we need to
+        // figure out what index and Element pointer to return.
+        if (i == 0) {
+            return Status(ErrorCodes::NonExistentPath,
+                          "cannot find path in the document");
+        }
+        else if (!viable) {
+            *idxFound = i - 1;
+            *elemFound = prev;
+            return Status(ErrorCodes::PathNotViable,
+                          mongoutils::str::stream() << "cannot use the part (" <<
+                          prefix.getPart(i-1) << " of " << prefix.dottedField() <<
+                          ") to traverse the element ({" <<
+                          curr.toString() << "})");
+        }
+        else if (curr.ok()) {
+            *idxFound = i - 1;
+            *elemFound = curr;
+            return Status::OK();
+        }
+        else {
+            *idxFound = i - 1;
+            *elemFound = prev;
+            return Status::OK();
+        }
+    }
+
+    Status createPathAt(const FieldRef& prefix,
+                        size_t idxFound,
+                        mutablebson::Element elemFound,
+                        mutablebson::Element newElem) {
+        Status status = Status::OK();
+
+        // Sanity check that 'idxField' is an actual part.
+        const size_t size = prefix.numParts();
+        if (idxFound >= size) {
+            return Status(ErrorCodes::BadValue, "index larger than path size");
+        }
+
+        mutablebson::Document& doc = elemFound.getDocument();
+
+        // If we are creating children under an array and a numeric index is next, then perhaps
+        // we need padding.
+        size_t i = idxFound;
+        bool inArray = false;
+        if (elemFound.getType() == mongo::Array) {
+            size_t newIdx = 0;
+            if (!isNumeric(prefix.getPart(idxFound), &newIdx)) {
+                return Status(ErrorCodes::InvalidPath, "Array require numeric fields");
+            }
+
+            status = maybePadTo(&elemFound, newIdx);
+            if (!status.isOK()) {
+                return status;
+            }
+
+            // If there is a next field, that would be an array element. We'd like to mark that
+            // field because we create array elements differently than we do regular objects.
+            if (++i < size) {
+                inArray = true;
+            }
+        }
+
+        // Create all the remaining parts but the last one.
+        for (; i < size - 1 ; i++) {
+            mutablebson::Element elem = doc.makeElementObject(prefix.getPart(i));
+            if (!elem.ok()) {
+                return Status(ErrorCodes::InternalError, "cannot create path");
+            }
+
+            // If this field is an array element, we wrap it in an object (because array
+            // elements are wraped in { "N": <element> } objects.
+            if (inArray) {
+                // TODO pass empty StringData to makeElementObject, when that's supported.
+                mutablebson::Element arrayObj = doc.makeElementObject("" /* it's an array */);
+                if (!arrayObj.ok()) {
+                    return Status(ErrorCodes::InternalError, "cannot create item on array");
+                }
+                status = arrayObj.pushBack(elem);
+                if (!status.isOK()) {
+                    return status;
+                }
+                status = elemFound.pushBack(arrayObj);
+                if (!status.isOK()) {
+                    return status;
+                }
+                inArray = false;
+            }
+            else {
+                status = elemFound.pushBack(elem);
+                if (!status.isOK()) {
+                    return status;
+                }
+            }
+
+            elemFound = elem;
+        }
+
+        // Attach the last element. Here again, if we're in a field that is an array element,
+        // we wrap it in an object first.
+        if (inArray) {
+            // TODO pass empty StringData to makeElementObject, when that's supported.
+            mutablebson::Element arrayObj = doc.makeElementObject("" /* it's an array */);
+            if (!arrayObj.ok()) {
+                return Status(ErrorCodes::InternalError, "cannot create item on array");
+            }
+
+            status = arrayObj.pushBack(newElem);
+            if (!status.isOK()) {
+                return status;
+            }
+
+            status = elemFound.pushBack(arrayObj);
+            if (!status.isOK()) {
+                return status;
+            }
+
+        }
+        else {
+            status = elemFound.pushBack(newElem);
+            if (!status.isOK()) {
+                return status;
+            }
+        }
+
+        return Status::OK();
+    }
+
+} // namespace pathsupport
+} // namespace mongo