1 // expression_tree.cpp
2
3
4 /**
5 * Copyright (C) 2018-present MongoDB, Inc.
6 *
7 * This program is free software: you can redistribute it and/or modify
8 * it under the terms of the Server Side Public License, version 1,
9 * as published by MongoDB, Inc.
10 *
11 * This program is distributed in the hope that it will be useful,
12 * but WITHOUT ANY WARRANTY; without even the implied warranty of
13 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 * Server Side Public License for more details.
15 *
16 * You should have received a copy of the Server Side Public License
17 * along with this program. If not, see
18 * <http://www.mongodb.com/licensing/server-side-public-license>.
19 *
20 * As a special exception, the copyright holders give permission to link the
21 * code of portions of this program with the OpenSSL library under certain
22 * conditions as described in each individual source file and distribute
23 * linked combinations including the program with the OpenSSL library. You
24 * must comply with the Server Side Public License in all respects for
25 * all of the code used other than as permitted herein. If you modify file(s)
26 * with this exception, you may extend this exception to your version of the
27 * file(s), but you are not obligated to do so. If you do not wish to do so,
28 * delete this exception statement from your version. If you delete this
29 * exception statement from all source files in the program, then also delete
30 * it in the license file.
31 */
32
33 #include "mongo/db/matcher/expression_tree.h"
34
35 #include "mongo/bson/bsonmisc.h"
36 #include "mongo/bson/bsonobj.h"
37 #include "mongo/bson/bsonobjbuilder.h"
38 #include "mongo/db/matcher/expression_always_boolean.h"
39
40 namespace mongo {
41
~ListOfMatchExpression()42 ListOfMatchExpression::~ListOfMatchExpression() {
43 for (unsigned i = 0; i < _expressions.size(); i++) {
44 delete _expressions[i];
45 }
46 _expressions.clear();
47 }
48
add(MatchExpression * e)49 void ListOfMatchExpression::add(MatchExpression* e) {
50 verify(e);
51 _expressions.push_back(e);
52 }
53
54
_debugList(StringBuilder & debug,int level) const55 void ListOfMatchExpression::_debugList(StringBuilder& debug, int level) const {
56 for (unsigned i = 0; i < _expressions.size(); i++)
57 _expressions[i]->debugString(debug, level + 1);
58 }
59
_listToBSON(BSONArrayBuilder * out) const60 void ListOfMatchExpression::_listToBSON(BSONArrayBuilder* out) const {
61 for (unsigned i = 0; i < _expressions.size(); i++) {
62 BSONObjBuilder childBob(out->subobjStart());
63 _expressions[i]->serialize(&childBob);
64 }
65 out->doneFast();
66 }
67
getOptimizer() const68 MatchExpression::ExpressionOptimizerFunc ListOfMatchExpression::getOptimizer() const {
69 return [](std::unique_ptr<MatchExpression> expression) -> std::unique_ptr<MatchExpression> {
70 auto& children = static_cast<ListOfMatchExpression&>(*expression)._expressions;
71
72 // Recursively apply optimizations to child expressions.
73 for (auto& childExpression : children) {
74 // Since 'childExpression' is a reference to a member of the ListOfMatchExpression's
75 // child array, this assignment replaces the original child with the optimized child.
76 // We must set this child's entry in '_expressions' to null after assigning ownership to
77 // 'childExpressionPtr'. Otherwise, if the call to optimize() throws we will attempt to
78 // free twice.
79 std::unique_ptr<MatchExpression> childExpressionPtr(childExpression);
80 childExpression = nullptr;
81
82 auto optimizedExpression = MatchExpression::optimize(std::move(childExpressionPtr));
83 childExpression = optimizedExpression.release();
84 }
85
86 // Associativity of AND and OR: an AND absorbs the children of any ANDs among its children
87 // (and likewise for any OR with OR children).
88 MatchType matchType = expression->matchType();
89 if (matchType == AND || matchType == OR) {
90 std::vector<MatchExpression*> absorbedExpressions;
91 for (MatchExpression*& childExpression : children) {
92 if (childExpression->matchType() == matchType) {
93 // Move this child out of the children array.
94 std::unique_ptr<ListOfMatchExpression> childExpressionPtr(
95 static_cast<ListOfMatchExpression*>(childExpression));
96 childExpression = nullptr; // Null out this child's entry in _expressions, so
97 // that it will be deleted by the erase call below.
98
99 // Move all of the grandchildren from the child expression to
100 // absorbedExpressions.
101 auto& grandChildren = childExpressionPtr->_expressions;
102 absorbedExpressions.insert(
103 absorbedExpressions.end(), grandChildren.begin(), grandChildren.end());
104 grandChildren.clear();
105
106 // Note that 'childExpressionPtr' will now be destroyed.
107 }
108 }
109
110 // We replaced each destroyed child expression with nullptr. Now we remove those
111 // nullptrs from the array.
112 children.erase(std::remove(children.begin(), children.end(), nullptr), children.end());
113
114 // Append the absorbed children to the end of the array.
115 children.insert(children.end(), absorbedExpressions.begin(), absorbedExpressions.end());
116 }
117
118 if (children.size() == 1) {
119 if ((matchType == AND || matchType == OR || matchType == INTERNAL_SCHEMA_XOR)) {
120 // Simplify AND/OR/XOR with exactly one operand to an expression consisting of just
121 // that operand.
122 MatchExpression* simplifiedExpression = children.front();
123 children.clear();
124 return std::unique_ptr<MatchExpression>(simplifiedExpression);
125 } else if (matchType == NOR) {
126 // Simplify NOR of exactly one operand to NOT of that operand.
127 auto simplifiedExpression = stdx::make_unique<NotMatchExpression>();
128 invariantOK(simplifiedExpression->init(children.front()));
129 children.clear();
130 return std::move(simplifiedExpression);
131 }
132 }
133
134 return expression;
135 };
136 }
137
equivalent(const MatchExpression * other) const138 bool ListOfMatchExpression::equivalent(const MatchExpression* other) const {
139 if (matchType() != other->matchType())
140 return false;
141
142 const ListOfMatchExpression* realOther = static_cast<const ListOfMatchExpression*>(other);
143
144 if (_expressions.size() != realOther->_expressions.size())
145 return false;
146
147 // TOOD: order doesn't matter
148 for (unsigned i = 0; i < _expressions.size(); i++)
149 if (!_expressions[i]->equivalent(realOther->_expressions[i]))
150 return false;
151
152 return true;
153 }
154
155 // -----
156
matches(const MatchableDocument * doc,MatchDetails * details) const157 bool AndMatchExpression::matches(const MatchableDocument* doc, MatchDetails* details) const {
158 for (size_t i = 0; i < numChildren(); i++) {
159 if (!getChild(i)->matches(doc, details)) {
160 if (details)
161 details->resetOutput();
162 return false;
163 }
164 }
165 return true;
166 }
167
matchesSingleElement(const BSONElement & e,MatchDetails * details) const168 bool AndMatchExpression::matchesSingleElement(const BSONElement& e, MatchDetails* details) const {
169 for (size_t i = 0; i < numChildren(); i++) {
170 if (!getChild(i)->matchesSingleElement(e, details)) {
171 return false;
172 }
173 }
174 return true;
175 }
176
177
debugString(StringBuilder & debug,int level) const178 void AndMatchExpression::debugString(StringBuilder& debug, int level) const {
179 _debugAddSpace(debug, level);
180 debug << "$and\n";
181 _debugList(debug, level);
182 }
183
serialize(BSONObjBuilder * out) const184 void AndMatchExpression::serialize(BSONObjBuilder* out) const {
185 if (!numChildren()) {
186 // It is possible for an AndMatchExpression to have no children, resulting in the serialized
187 // expression {$and: []}, which is not a valid query object.
188 return;
189 }
190
191 BSONArrayBuilder arrBob(out->subarrayStart("$and"));
192 _listToBSON(&arrBob);
193 arrBob.doneFast();
194 }
195
196 // -----
197
matches(const MatchableDocument * doc,MatchDetails * details) const198 bool OrMatchExpression::matches(const MatchableDocument* doc, MatchDetails* details) const {
199 for (size_t i = 0; i < numChildren(); i++) {
200 if (getChild(i)->matches(doc, NULL)) {
201 return true;
202 }
203 }
204 return false;
205 }
206
matchesSingleElement(const BSONElement & e,MatchDetails * details) const207 bool OrMatchExpression::matchesSingleElement(const BSONElement& e, MatchDetails* details) const {
208 for (size_t i = 0; i < numChildren(); i++) {
209 if (getChild(i)->matchesSingleElement(e, details)) {
210 return true;
211 }
212 }
213 return false;
214 }
215
216
debugString(StringBuilder & debug,int level) const217 void OrMatchExpression::debugString(StringBuilder& debug, int level) const {
218 _debugAddSpace(debug, level);
219 debug << "$or\n";
220 _debugList(debug, level);
221 }
222
serialize(BSONObjBuilder * out) const223 void OrMatchExpression::serialize(BSONObjBuilder* out) const {
224 if (!numChildren()) {
225 out->append(AlwaysFalseMatchExpression::kName, 1);
226 return;
227 }
228 BSONArrayBuilder arrBob(out->subarrayStart("$or"));
229 _listToBSON(&arrBob);
230 }
231
232 // ----
233
matches(const MatchableDocument * doc,MatchDetails * details) const234 bool NorMatchExpression::matches(const MatchableDocument* doc, MatchDetails* details) const {
235 for (size_t i = 0; i < numChildren(); i++) {
236 if (getChild(i)->matches(doc, NULL)) {
237 return false;
238 }
239 }
240 return true;
241 }
242
matchesSingleElement(const BSONElement & e,MatchDetails * details) const243 bool NorMatchExpression::matchesSingleElement(const BSONElement& e, MatchDetails* details) const {
244 for (size_t i = 0; i < numChildren(); i++) {
245 if (getChild(i)->matchesSingleElement(e, details)) {
246 return false;
247 }
248 }
249 return true;
250 }
251
debugString(StringBuilder & debug,int level) const252 void NorMatchExpression::debugString(StringBuilder& debug, int level) const {
253 _debugAddSpace(debug, level);
254 debug << "$nor\n";
255 _debugList(debug, level);
256 }
257
serialize(BSONObjBuilder * out) const258 void NorMatchExpression::serialize(BSONObjBuilder* out) const {
259 BSONArrayBuilder arrBob(out->subarrayStart("$nor"));
260 _listToBSON(&arrBob);
261 }
262
263 // -------
264
debugString(StringBuilder & debug,int level) const265 void NotMatchExpression::debugString(StringBuilder& debug, int level) const {
266 _debugAddSpace(debug, level);
267 debug << "$not\n";
268 _exp->debugString(debug, level + 1);
269 }
270
serialize(BSONObjBuilder * out) const271 void NotMatchExpression::serialize(BSONObjBuilder* out) const {
272 BSONObjBuilder childBob;
273 _exp->serialize(&childBob);
274
275 BSONObj tempObj = childBob.obj();
276
277 // We don't know what the inner object is, and thus whether serializing to $not will result in a
278 // parseable MatchExpression. As a fix, we change it to $nor, which is always parseable.
279 BSONArrayBuilder tBob(out->subarrayStart("$nor"));
280 tBob.append(tempObj);
281 tBob.doneFast();
282 }
283
equivalent(const MatchExpression * other) const284 bool NotMatchExpression::equivalent(const MatchExpression* other) const {
285 if (matchType() != other->matchType())
286 return false;
287
288 return _exp->equivalent(other->getChild(0));
289 }
290
291
getOptimizer() const292 MatchExpression::ExpressionOptimizerFunc NotMatchExpression::getOptimizer() const {
293 return [](std::unique_ptr<MatchExpression> expression) {
294 auto& notExpression = static_cast<NotMatchExpression&>(*expression);
295 notExpression._exp = MatchExpression::optimize(std::move(notExpression._exp));
296
297 return expression;
298 };
299 }
300 }
301