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 #pragma once 32 33 #include <cstdint> 34 #include <string> 35 36 #include "mongo/base/status.h" 37 #include "mongo/bson/mutable/element.h" 38 #include "mongo/db/field_ref.h" 39 #include "mongo/db/field_ref_set.h" 40 #include "mongo/db/matcher/expression.h" 41 #include "mongo/db/matcher/expression_leaf.h" 42 43 namespace mongo { 44 45 namespace pathsupport { 46 47 // Cap on the number of nulls we'll add to an array if we're inserting to an index that 48 // doesn't exist. 49 static const size_t kMaxPaddingAllowed = 1500000; 50 51 // Convenience type to hold equality matches at particular paths from a MatchExpression 52 typedef std::map<StringData, const EqualityMatchExpression*> EqualityMatches; 53 54 /** 55 * Finds the longest portion of 'prefix' that exists in document rooted at 'root' and is 56 * "viable." A viable path is one that, if fully created on a given doc, would not 57 * change the existing types of any fields in that doc. (See examples below.) 58 * 59 * If a prefix indeed exists, 'idxFound' is set to indicate how many parts in common 60 * 'prefix' and 'doc' have. 'elemFound' would point to the Element corresponding to 61 * prefix[idxFound] in 'doc'. The call would return an OK status in this case. 62 * 63 * If a prefix is not viable, returns a status "PathNotViable". 'idxFound' is set to 64 * indicate the part in the document that caused the path to be not viable. 'elemFound' 65 * would point to the Element corresponding to prefix[idxFound] in 'doc'. 66 * 67 * If a prefix does not exist, the call returns "NonExistentPath". 'elemFound' and 68 * 'idxFound' are indeterminate in this case. 69 * 70 * Definition of a "Viable Path": 71 * 72 * A field reference 'p_1.p_2.[...].p_n', where 'p_i' is a field part, is said to be 73 * a viable path in a given document D if the creation of each part 'p_i', 0 <= i < n 74 * in D does not force 'p_i' to change types. In other words, no existing 'p_i' in D 75 * may have a different type, other than the 'p_n'. 76 * 77 * 'a.b.c' is a viable path in {a: {b: {c: 1}}} 78 * 'a.b.c' is a viable path in {a: {b: {c: {d: 1}}}} 79 * 'a.b.c' is NOT a viable path in {a: {b: 1}}, because b would have changed types 80 * 'a.0.b' is a viable path in {a: [{b: 1}, {c: 1}]} 81 * 'a.0.b' is a viable path in {a: {"0": {b: 1}}} 82 * 'a.0.b' is NOT a viable path in {a: 1}, because a would have changed types 83 * 'a.5.b' is a viable path in in {a: []} (padding would occur) 84 */ 85 Status findLongestPrefix(const FieldRef& prefix, 86 mutablebson::Element root, 87 size_t* idxFound, 88 mutablebson::Element* elemFound); 89 90 /** 91 * Creates the parts 'prefix[idxRoot]', 'prefix[idxRoot+1]', ..., 'prefix[<numParts>-1]' under 92 * 'elemFound' and adds 'newElem' as a child of that path. Returns the first element that was 93 * created along the path, if successful, or an error code describing why not, otherwise. 94 * 95 * createPathAt is designed to work with 'findLongestPrefix' in that it can create the 96 * field parts in 'prefix' that are missing from a given document. 'elemFound' points 97 * to the element in the doc that is the parent of prefix[idxRoot]. 98 */ 99 StatusWith<mutablebson::Element> createPathAt(const FieldRef& prefix, 100 size_t idxRoot, 101 mutablebson::Element elemFound, 102 mutablebson::Element newElem); 103 104 /** 105 * Uses the above methods to set the given value at the specified path in a mutable 106 * Document, creating parents of the path if necessary. 107 * 108 * Returns PathNotViable if the path cannot be created without modifying the type of another 109 * element, see above. 110 */ 111 Status setElementAtPath(const FieldRef& path, const BSONElement& value, mutablebson::Document* doc); 112 113 /** 114 * Finds and returns-by-path all the equality matches in a particular MatchExpression. 115 * 116 * This method is meant to be used with the methods below, which allow efficient use of the 117 * equality matches without needing to serialize to a BSONObj. 118 * 119 * Returns NotSingleValueField if the match expression has equality operators for 120 * conflicting paths - equality paths conflict if they are the same or one path is a prefix 121 * of the other. 122 * 123 * Ex: 124 * { a : 1, b : 1 } -> no conflict 125 * { a : 1, a.b : 1 } -> conflict 126 * { _id : { x : 1 }, _id.y : 1 } -> conflict 127 * { a : 1, a : 1 } -> conflict 128 */ 129 Status extractEqualityMatches(const MatchExpression& root, EqualityMatches* equalities); 130 131 /** 132 * Same as the above, but ignores all paths except for paths in a specified set. 133 * Equality matches with paths completely distinct from these paths are ignored. 134 * 135 * For a full equality match, the path of an equality found must not be a suffix of one of 136 * the specified path - otherwise it isn't clear how to construct a full value for a field 137 * at that path. 138 * 139 * Generally this is useful for shard keys and _ids which need unambiguous extraction from 140 * queries. 141 * 142 * Ex: 143 * { a : 1 }, full path 'a' -> a $eq 1 extracted 144 * { a : 1 }, full path 'a.b' -> a $eq 1 extracted 145 * { 'a.b' : 1 }, full path 'a' -> NotExactValueField error 146 * ('a.b' doesn't specify 'a' fully) 147 * { 'a.b' : 1 }, full path 'a.b' -> 'a.b' $eq 1 extracted 148 * { '_id' : 1 }, full path '_id' -> '_id' $eq 1 extracted 149 * { '_id.x' : 1 }, full path '_id' -> NotExactValueFieldError 150 */ 151 Status extractFullEqualityMatches(const MatchExpression& root, 152 const FieldRefSet& fullPathsToExtract, 153 EqualityMatches* equalities); 154 155 /** 156 * Returns the equality match which is at or a parent of the specified path string. The 157 * path string must be a valid dotted path. 158 * 159 * If a parent equality is found, returns the BSONElement data from that equality (which 160 * includes the BSON value), the path of the parent element (prefixStr), and the remainder 161 * of the path (which may be empty). 162 * 163 * EOO() is returned if there were no equalities at any point along the path. 164 * 165 * Ex: 166 * Given equality matches of: 167 * 'a.b' : 1, 'c' : 2 168 * Path 'a' has no equality match parent (EOO) 169 * Path 'c' has an eqmatch parent of 'c' : 2 170 * Path 'c.d' has an eqmatch parent of 'c' : 2 171 * Path 'a.b' has an eqmatch parent of 'a.b' : 1 172 * Path 'a.b.c' has an eqmatch parent of 'a.b' : 1 173 * 174 */ 175 BSONElement findParentEqualityElement(const EqualityMatches& equalities, 176 const FieldRef& path, 177 int* parentPathParts); 178 179 /** 180 * Adds the BSON values from equality matches into the given document at the equality match 181 * paths. 182 * 183 * Returns PathNotViable similar to setElementAtPath above. If equality paths do not 184 * conflict, as is enforced by extractEqualityMatches, this function should return OK. 185 */ 186 Status addEqualitiesToDoc(const EqualityMatches& equalities, mutablebson::Document* doc); 187 188 } // namespace pathsupport 189 190 } // namespace mongo 191