1
2 /**
3 * Copyright (C) 2018-present MongoDB, Inc.
4 *
5 * This program is free software: you can redistribute it and/or modify
6 * it under the terms of the Server Side Public License, version 1,
7 * as published by MongoDB, Inc.
8 *
9 * This program is distributed in the hope that it will be useful,
10 * but WITHOUT ANY WARRANTY; without even the implied warranty of
11 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12 * Server Side Public License for more details.
13 *
14 * You should have received a copy of the Server Side Public License
15 * along with this program. If not, see
16 * <http://www.mongodb.com/licensing/server-side-public-license>.
17 *
18 * As a special exception, the copyright holders give permission to link the
19 * code of portions of this program with the OpenSSL library under certain
20 * conditions as described in each individual source file and distribute
21 * linked combinations including the program with the OpenSSL library. You
22 * must comply with the Server Side Public License in all respects for
23 * all of the code used other than as permitted herein. If you modify file(s)
24 * with this exception, you may extend this exception to your version of the
25 * file(s), but you are not obligated to do so. If you do not wish to do so,
26 * delete this exception statement from your version. If you delete this
27 * exception statement from all source files in the program, then also delete
28 * it in the license file.
29 */
30
31 #include "mongo/platform/basic.h"
32
33 #include "mongo/db/update/update_object_node.h"
34
35 #include "mongo/db/update/field_checker.h"
36 #include "mongo/db/update/modifier_table.h"
37 #include "mongo/db/update/update_array_node.h"
38 #include "mongo/db/update/update_leaf_node.h"
39 #include "mongo/stdx/memory.h"
40 #include "mongo/util/stringutils.h"
41
42 namespace mongo {
43
44 namespace {
45
46 /**
47 * Parses a field of the form $[<identifier>] into <identifier>. 'field' must be of the form
48 * $[<identifier>]. Returns a non-ok status if 'field' is in the first position in the path or the
49 * array filter identifier does not have a corresponding filter in 'arrayFilters'. Adds the
50 * identifier to 'foundIdentifiers'.
51 */
parseArrayFilterIdentifier(StringData field,size_t position,const FieldRef & fieldRef,const std::map<StringData,std::unique_ptr<ExpressionWithPlaceholder>> & arrayFilters,std::set<std::string> & foundIdentifiers)52 StatusWith<std::string> parseArrayFilterIdentifier(
53 StringData field,
54 size_t position,
55 const FieldRef& fieldRef,
56 const std::map<StringData, std::unique_ptr<ExpressionWithPlaceholder>>& arrayFilters,
57 std::set<std::string>& foundIdentifiers) {
58 dassert(fieldchecker::isArrayFilterIdentifier(field));
59
60 if (position == 0) {
61 return Status(ErrorCodes::BadValue,
62 str::stream() << "Cannot have array filter identifier (i.e. '$[<id>]') "
63 "element in the first position in path '"
64 << fieldRef.dottedField()
65 << "'");
66 }
67
68 auto identifier = field.substr(2, field.size() - 3);
69
70 if (!identifier.empty() && arrayFilters.find(identifier) == arrayFilters.end()) {
71 return Status(ErrorCodes::BadValue,
72 str::stream() << "No array filter found for identifier '" << identifier
73 << "' in path '"
74 << fieldRef.dottedField()
75 << "'");
76 }
77
78 if (!identifier.empty()) {
79 foundIdentifiers.emplace(identifier.toString());
80 }
81
82 return identifier.toString();
83 }
84
85 /**
86 * Gets the child of 'element' named 'field', if it exists. Otherwise returns a non-ok element.
87 */
getChild(mutablebson::Element element,StringData field)88 mutablebson::Element getChild(mutablebson::Element element, StringData field) {
89 if (element.getType() == BSONType::Object) {
90 return element[field];
91 } else if (element.getType() == BSONType::Array) {
92 auto indexFromField = parseUnsignedBase10Integer(field);
93 if (indexFromField) {
94 return element.findNthChild(*indexFromField);
95 }
96 }
97 return element.getDocument().end();
98 }
99
100 /**
101 * Applies 'child' to the child of 'applyParams->element' named 'field' (which will create it, if it
102 * does not exist). If 'applyParams->pathToCreate' is created, then 'applyParams->pathToCreate' is
103 * moved to the end of 'applyParams->pathTaken', and 'applyParams->element' is advanced to the end
104 * of 'applyParams->pathTaken'. Updates 'applyResult' based on whether 'child' was a noop or
105 * affected indexes.
106 */
applyChild(const UpdateNode & child,StringData field,UpdateNode::ApplyParams * applyParams,UpdateNode::ApplyResult * applyResult)107 void applyChild(const UpdateNode& child,
108 StringData field,
109 UpdateNode::ApplyParams* applyParams,
110 UpdateNode::ApplyResult* applyResult) {
111
112 auto pathTakenSizeBefore = applyParams->pathTaken->numParts();
113
114 // A non-ok value for childElement will indicate that we need to append 'field' to the
115 // 'pathToCreate' FieldRef.
116 auto childElement = applyParams->element.getDocument().end();
117 invariant(!childElement.ok());
118 if (!applyParams->pathToCreate->empty()) {
119 // We're already traversing a path with elements that don't exist yet, so we will definitely
120 // need to append.
121 } else {
122 childElement = getChild(applyParams->element, field);
123 }
124
125 if (childElement.ok()) {
126 // The path we've traversed so far already exists in our document, and 'childElement'
127 // represents the Element indicated by the 'field' name or index, which we indicate by
128 // updating the 'pathTaken' FieldRef.
129 applyParams->pathTaken->appendPart(field);
130 } else {
131 // We are traversing path components that do not exist in our document. Any update modifier
132 // that creates new path components (i.e., any modifiers that return true for
133 // allowCreation()) will need to create this component, so we append it to the
134 // 'pathToCreate' FieldRef. If the component cannot be created, pathsupport::createPathAt()
135 // will provide a sensible PathNotViable UserError.
136 childElement = applyParams->element;
137 applyParams->pathToCreate->appendPart(field);
138 }
139
140 auto childApplyParams = *applyParams;
141 childApplyParams.element = childElement;
142 auto childApplyResult = child.apply(childApplyParams);
143
144 applyResult->indexesAffected = applyResult->indexesAffected || childApplyResult.indexesAffected;
145 applyResult->noop = applyResult->noop && childApplyResult.noop;
146
147 // Pop 'field' off of 'pathToCreate' or 'pathTaken'.
148 if (!applyParams->pathToCreate->empty()) {
149 applyParams->pathToCreate->removeLastPart();
150 } else {
151 applyParams->pathTaken->removeLastPart();
152 }
153
154 // If the child is an internal node, it may have created 'pathToCreate' and moved 'pathToCreate'
155 // to the end of 'pathTaken'. We should advance 'element' to the end of 'pathTaken'.
156 if (applyParams->pathTaken->numParts() > pathTakenSizeBefore) {
157 for (auto i = pathTakenSizeBefore; i < applyParams->pathTaken->numParts(); ++i) {
158 applyParams->element =
159 getChild(applyParams->element, applyParams->pathTaken->getPart(i));
160 invariant(applyParams->element.ok());
161 }
162 } else if (!applyParams->pathToCreate->empty()) {
163
164 // If the child is a leaf node, it may have created 'pathToCreate' without moving
165 // 'pathToCreate' to the end of 'pathTaken'. We should move 'pathToCreate' to the end of
166 // 'pathTaken' and advance 'element' to the end of 'pathTaken'.
167 childElement = getChild(applyParams->element, applyParams->pathToCreate->getPart(0));
168 if (childElement.ok()) {
169 applyParams->element = childElement;
170 applyParams->pathTaken->appendPart(applyParams->pathToCreate->getPart(0));
171
172 // Either the path was fully created or not created at all.
173 for (size_t i = 1; i < applyParams->pathToCreate->numParts(); ++i) {
174 applyParams->element =
175 getChild(applyParams->element, applyParams->pathToCreate->getPart(i));
176 invariant(applyParams->element.ok());
177 applyParams->pathTaken->appendPart(applyParams->pathToCreate->getPart(i));
178 }
179
180 applyParams->pathToCreate->clear();
181 }
182 }
183 }
184
185 } // namespace
186
187 // static
parseAndMerge(UpdateObjectNode * root,modifiertable::ModifierType type,BSONElement modExpr,const boost::intrusive_ptr<ExpressionContext> & expCtx,const std::map<StringData,std::unique_ptr<ExpressionWithPlaceholder>> & arrayFilters,std::set<std::string> & foundIdentifiers)188 StatusWith<bool> UpdateObjectNode::parseAndMerge(
189 UpdateObjectNode* root,
190 modifiertable::ModifierType type,
191 BSONElement modExpr,
192 const boost::intrusive_ptr<ExpressionContext>& expCtx,
193 const std::map<StringData, std::unique_ptr<ExpressionWithPlaceholder>>& arrayFilters,
194 std::set<std::string>& foundIdentifiers) {
195 FieldRef fieldRef;
196 if (type != modifiertable::ModifierType::MOD_RENAME) {
197 // General case: Create a path in the tree according to the path specified in the field name
198 // of the "modExpr" element.
199 fieldRef.parse(modExpr.fieldNameStringData());
200 } else {
201 // Special case: For $rename modifiers, we add two nodes to the tree:
202 // 1) a ConflictPlaceholderNode at the path specified in the field name of the "modExpr"
203 // element and
204 auto status = parseAndMerge(root,
205 modifiertable::ModifierType::MOD_CONFLICT_PLACEHOLDER,
206 modExpr,
207 expCtx,
208 arrayFilters,
209 foundIdentifiers);
210 if (!status.isOK()) {
211 return status;
212 }
213
214 // 2) a RenameNode at the path specified by the value of the "modExpr" element, which must
215 // be a string value.
216 if (BSONType::String != modExpr.type()) {
217 return Status(ErrorCodes::BadValue,
218 str::stream() << "The 'to' field for $rename must be a string: "
219 << modExpr);
220 }
221
222 fieldRef.parse(modExpr.valueStringData());
223 }
224
225 // Check that the path is updatable.
226 auto status = fieldchecker::isUpdatable(fieldRef);
227 if (!status.isOK()) {
228 return status;
229 }
230
231 // Check that there is at most one positional ($) part of the path and it is not in the first
232 // position.
233 size_t positionalIndex;
234 size_t positionalCount;
235 bool positional = fieldchecker::isPositional(fieldRef, &positionalIndex, &positionalCount);
236
237 if (positional && positionalCount > 1) {
238 return Status(ErrorCodes::BadValue,
239 str::stream() << "Too many positional (i.e. '$') elements found in path '"
240 << fieldRef.dottedField()
241 << "'");
242 }
243
244 if (positional && positionalIndex == 0) {
245 return Status(
246 ErrorCodes::BadValue,
247 str::stream()
248 << "Cannot have positional (i.e. '$') element in the first position in path '"
249 << fieldRef.dottedField()
250 << "'");
251 }
252
253 // Construct and initialize the leaf node.
254 auto leaf = modifiertable::makeUpdateLeafNode(type);
255 invariant(leaf);
256 status = leaf->init(modExpr, expCtx);
257 if (!status.isOK()) {
258 return status;
259 }
260
261 // Create UpdateInternalNodes along the path.
262 UpdateInternalNode* current = static_cast<UpdateInternalNode*>(root);
263 for (size_t i = 0; i < fieldRef.numParts() - 1; ++i) {
264 auto fieldIsArrayFilterIdentifier =
265 fieldchecker::isArrayFilterIdentifier(fieldRef.getPart(i));
266
267 std::string childName;
268 if (fieldIsArrayFilterIdentifier) {
269 auto status = parseArrayFilterIdentifier(
270 fieldRef.getPart(i), i, fieldRef, arrayFilters, foundIdentifiers);
271 if (!status.isOK()) {
272 return status.getStatus();
273 }
274 childName = status.getValue();
275 } else {
276 childName = fieldRef.getPart(i).toString();
277 }
278
279 auto child = current->getChild(childName);
280 auto childShouldBeArrayNode =
281 fieldchecker::isArrayFilterIdentifier(fieldRef.getPart(i + 1));
282 if (child) {
283 if ((childShouldBeArrayNode && child->type != UpdateNode::Type::Array) ||
284 (!childShouldBeArrayNode && child->type != UpdateNode::Type::Object)) {
285 return Status(ErrorCodes::ConflictingUpdateOperators,
286 str::stream() << "Updating the path '" << fieldRef.dottedField()
287 << "' would create a conflict at '"
288 << fieldRef.dottedSubstring(0, i + 1)
289 << "'");
290 }
291 } else {
292 std::unique_ptr<UpdateInternalNode> ownedChild;
293 if (childShouldBeArrayNode) {
294 ownedChild = stdx::make_unique<UpdateArrayNode>(arrayFilters);
295 } else {
296 ownedChild = stdx::make_unique<UpdateObjectNode>();
297 }
298 child = ownedChild.get();
299 current->setChild(std::move(childName), std::move(ownedChild));
300 }
301 current = static_cast<UpdateInternalNode*>(child);
302 }
303
304 // Add the leaf node to the end of the path.
305 auto fieldIsArrayFilterIdentifier =
306 fieldchecker::isArrayFilterIdentifier(fieldRef.getPart(fieldRef.numParts() - 1));
307
308 std::string childName;
309 if (fieldIsArrayFilterIdentifier) {
310 auto status = parseArrayFilterIdentifier(fieldRef.getPart(fieldRef.numParts() - 1),
311 fieldRef.numParts() - 1,
312 fieldRef,
313 arrayFilters,
314 foundIdentifiers);
315 if (!status.isOK()) {
316 return status.getStatus();
317 }
318 childName = status.getValue();
319 } else {
320 childName = fieldRef.getPart(fieldRef.numParts() - 1).toString();
321 }
322
323 if (current->getChild(childName)) {
324 return Status(ErrorCodes::ConflictingUpdateOperators,
325 str::stream() << "Updating the path '" << fieldRef.dottedField()
326 << "' would create a conflict at '"
327 << fieldRef.dottedField()
328 << "'");
329 }
330 current->setChild(std::move(childName), std::move(leaf));
331
332 return positional;
333 }
334
335 // static
createUpdateNodeByMerging(const UpdateObjectNode & leftNode,const UpdateObjectNode & rightNode,FieldRef * pathTaken)336 std::unique_ptr<UpdateNode> UpdateObjectNode::createUpdateNodeByMerging(
337 const UpdateObjectNode& leftNode, const UpdateObjectNode& rightNode, FieldRef* pathTaken) {
338 auto mergedNode = stdx::make_unique<UpdateObjectNode>();
339
340 mergedNode->_children =
341 createUpdateNodeMapByMerging(leftNode._children, rightNode._children, pathTaken);
342
343 // The "positional" field ("$" notation) lives outside of the _children map, so we merge it
344 // separately.
345 mergedNode->_positionalChild = copyOrMergeAsNecessary(
346 leftNode._positionalChild.get(), rightNode._positionalChild.get(), pathTaken, "$");
347
348 // In Clang-3.9, we can just return mergedNode directly, but in 3.7, we need a std::move
349 return std::move(mergedNode);
350 }
351
getChild(const std::string & field) const352 UpdateNode* UpdateObjectNode::getChild(const std::string& field) const {
353 if (fieldchecker::isPositionalElement(field)) {
354 return _positionalChild.get();
355 }
356
357 auto child = _children.find(field);
358 if (child == _children.end()) {
359 return nullptr;
360 }
361 return child->second.get();
362 }
363
setChild(std::string field,std::unique_ptr<UpdateNode> child)364 void UpdateObjectNode::setChild(std::string field, std::unique_ptr<UpdateNode> child) {
365 if (fieldchecker::isPositionalElement(field)) {
366 invariant(!_positionalChild);
367 _positionalChild = std::move(child);
368 } else {
369 invariant(_children.find(field) == _children.end());
370 _children[std::move(field)] = std::move(child);
371 }
372 }
373
apply(ApplyParams applyParams) const374 UpdateNode::ApplyResult UpdateObjectNode::apply(ApplyParams applyParams) const {
375 bool applyPositional = _positionalChild.get();
376 if (applyPositional) {
377 uassert(ErrorCodes::BadValue,
378 "The positional operator did not find the match needed from the query.",
379 !applyParams.matchedField.empty());
380 }
381
382 auto applyResult = ApplyResult::noopResult();
383
384 for (const auto& pair : _children) {
385
386 // If this child has the same field name as the positional child, they must be merged and
387 // applied.
388 if (applyPositional && pair.first == applyParams.matchedField) {
389
390 // Check if we have stored the result of merging the positional child with this child.
391 auto mergedChild = _mergedChildrenCache.find(pair.first);
392 if (mergedChild == _mergedChildrenCache.end()) {
393
394 // The full path to the merged field is required for error reporting.
395 for (size_t i = 0; i < applyParams.pathToCreate->numParts(); ++i) {
396 applyParams.pathTaken->appendPart(applyParams.pathToCreate->getPart(i));
397 }
398 applyParams.pathTaken->appendPart(applyParams.matchedField);
399 auto insertResult = _mergedChildrenCache.emplace(std::make_pair(
400 pair.first,
401 UpdateNode::createUpdateNodeByMerging(
402 *_positionalChild, *pair.second, applyParams.pathTaken.get())));
403 for (size_t i = 0; i < applyParams.pathToCreate->numParts() + 1; ++i) {
404 applyParams.pathTaken->removeLastPart();
405 }
406 invariant(insertResult.second);
407 mergedChild = insertResult.first;
408 }
409
410 applyChild(*mergedChild->second.get(), pair.first, &applyParams, &applyResult);
411
412 applyPositional = false;
413 continue;
414 }
415
416 // If 'matchedField' is alphabetically before the current child, we should apply the
417 // positional child now.
418 if (applyPositional && applyParams.matchedField < pair.first) {
419 applyChild(
420 *_positionalChild.get(), applyParams.matchedField, &applyParams, &applyResult);
421 applyPositional = false;
422 }
423
424 // Apply the current child.
425 applyChild(*pair.second, pair.first, &applyParams, &applyResult);
426 }
427
428 // 'matchedField' is alphabetically after all children, so we apply it now.
429 if (applyPositional) {
430 applyChild(*_positionalChild.get(), applyParams.matchedField, &applyParams, &applyResult);
431 }
432
433 return applyResult;
434 }
435
436 } // namespace mongo
437