1 // path_test.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/unittest/unittest.h"
34 
35 #include "mongo/db/jsobj.h"
36 #include "mongo/db/json.h"
37 #include "mongo/db/matcher/path.h"
38 
39 namespace mongo {
40 
41 using std::string;
42 
TEST(Path,Root1)43 TEST(Path, Root1) {
44     ElementPath p;
45     ASSERT(p.init("a").isOK());
46 
47     BSONObj doc = BSON("x" << 4 << "a" << 5);
48 
49     BSONElementIterator cursor(&p, doc);
50     ASSERT(cursor.more());
51     ElementIterator::Context e = cursor.next();
52     ASSERT_EQUALS((string) "a", e.element().fieldName());
53     ASSERT_EQUALS(5, e.element().numberInt());
54     ASSERT(!cursor.more());
55 }
56 
TEST(Path,RootArray1)57 TEST(Path, RootArray1) {
58     ElementPath p;
59     ASSERT(p.init("a").isOK());
60 
61     BSONObj doc = BSON("x" << 4 << "a" << BSON_ARRAY(5 << 6));
62 
63     BSONElementIterator cursor(&p, doc);
64 
65     ASSERT(cursor.more());
66     BSONElementIterator::Context e = cursor.next();
67     ASSERT_EQUALS(5, e.element().numberInt());
68 
69     ASSERT(cursor.more());
70     e = cursor.next();
71     ASSERT_EQUALS(6, e.element().numberInt());
72 
73     ASSERT(cursor.more());
74     e = cursor.next();
75     ASSERT_EQUALS(Array, e.element().type());
76 
77     ASSERT(!cursor.more());
78 }
79 
TEST(Path,RootArray2)80 TEST(Path, RootArray2) {
81     ElementPath p;
82     ASSERT_OK(p.init("a"));
83     p.setLeafArrayBehavior(ElementPath::LeafArrayBehavior::kNoTraversal);
84 
85     BSONObj doc = BSON("x" << 4 << "a" << BSON_ARRAY(5 << 6));
86 
87     BSONElementIterator cursor(&p, doc);
88 
89     ASSERT(cursor.more());
90     BSONElementIterator::Context e = cursor.next();
91     ASSERT(e.element().type() == Array);
92 
93     ASSERT(!cursor.more());
94 }
95 
TEST(Path,Nested1)96 TEST(Path, Nested1) {
97     ElementPath p;
98     ASSERT(p.init("a.b").isOK());
99 
100     BSONObj doc =
101         BSON("a" << BSON_ARRAY(BSON("b" << 5) << 3 << BSONObj() << BSON("b" << BSON_ARRAY(9 << 11))
102                                               << BSON("b" << 7)));
103 
104     BSONElementIterator cursor(&p, doc);
105 
106     ASSERT(cursor.more());
107     BSONElementIterator::Context e = cursor.next();
108     ASSERT_EQUALS(5, e.element().numberInt());
109 
110     ASSERT(cursor.more());
111     e = cursor.next();
112     ASSERT(e.element().eoo());
113     ASSERT_EQUALS((string) "2", e.arrayOffset().fieldName());
114 
115     ASSERT(cursor.more());
116     e = cursor.next();
117     ASSERT_EQUALS(9, e.element().numberInt());
118 
119     ASSERT(cursor.more());
120     e = cursor.next();
121     ASSERT_EQUALS(11, e.element().numberInt());
122 
123     ASSERT(cursor.more());
124     e = cursor.next();
125     ASSERT_EQUALS(Array, e.element().type());
126     ASSERT_EQUALS(2, e.element().Obj().nFields());
127 
128     ASSERT(cursor.more());
129     e = cursor.next();
130     ASSERT_EQUALS(7, e.element().numberInt());
131 
132     ASSERT(!cursor.more());
133 }
134 
TEST(Path,NestedPartialMatchScalar)135 TEST(Path, NestedPartialMatchScalar) {
136     ElementPath p;
137     ASSERT(p.init("a.b").isOK());
138 
139     BSONObj doc = BSON("a" << 4);
140 
141     BSONElementIterator cursor(&p, doc);
142 
143     ASSERT(cursor.more());
144     BSONElementIterator::Context e = cursor.next();
145     ASSERT(e.element().eoo());
146     ASSERT(e.arrayOffset().eoo());
147 
148     ASSERT(!cursor.more());
149 }
150 
151 // When the path (partially or in its entirety) refers to an array,
152 // the iteration logic does not return an EOO.
153 // what we want ideally.
TEST(Path,NestedPartialMatchArray)154 TEST(Path, NestedPartialMatchArray) {
155     ElementPath p;
156     ASSERT(p.init("a.b").isOK());
157 
158     BSONObj doc = BSON("a" << BSON_ARRAY(4));
159 
160     BSONElementIterator cursor(&p, doc);
161 
162     ASSERT(!cursor.more());
163 }
164 
165 // Note that this describes existing behavior and not necessarily
TEST(Path,NestedEmptyArray)166 TEST(Path, NestedEmptyArray) {
167     ElementPath p;
168     ASSERT(p.init("a.b").isOK());
169 
170     BSONObj doc = BSON("a" << BSON("b" << BSONArray()));
171 
172     BSONElementIterator cursor(&p, doc);
173 
174     ASSERT(cursor.more());
175     BSONElementIterator::Context e = cursor.next();
176     ASSERT_EQUALS(Array, e.element().type());
177     ASSERT_EQUALS(0, e.element().Obj().nFields());
178 
179     ASSERT(!cursor.more());
180 }
181 
TEST(Path,NestedNoLeaf1)182 TEST(Path, NestedNoLeaf1) {
183     ElementPath p;
184     ASSERT_OK(p.init("a.b"));
185     p.setLeafArrayBehavior(ElementPath::LeafArrayBehavior::kNoTraversal);
186 
187     BSONObj doc =
188         BSON("a" << BSON_ARRAY(BSON("b" << 5) << 3 << BSONObj() << BSON("b" << BSON_ARRAY(9 << 11))
189                                               << BSON("b" << 7)));
190 
191     BSONElementIterator cursor(&p, doc);
192 
193     ASSERT(cursor.more());
194     BSONElementIterator::Context e = cursor.next();
195     ASSERT_EQUALS(5, e.element().numberInt());
196 
197     ASSERT(cursor.more());
198     e = cursor.next();
199     ASSERT(e.element().eoo());
200     ASSERT_EQUALS((string) "2", e.arrayOffset().fieldName());
201 
202     ASSERT(cursor.more());
203     e = cursor.next();
204     ASSERT_EQUALS(Array, e.element().type());
205     ASSERT_EQUALS(2, e.element().Obj().nFields());
206 
207     ASSERT(cursor.more());
208     e = cursor.next();
209     ASSERT_EQUALS(7, e.element().numberInt());
210 
211     ASSERT(!cursor.more());
212 }
213 
TEST(Path,MatchSubpathReturnsArrayOnSubpath)214 TEST(Path, MatchSubpathReturnsArrayOnSubpath) {
215     ElementPath path;
216     ASSERT_OK(path.init("a.b.c"));
217     path.setLeafArrayBehavior(ElementPath::LeafArrayBehavior::kNoTraversal);
218     path.setNonLeafArrayBehavior(ElementPath::NonLeafArrayBehavior::kMatchSubpath);
219 
220     BSONObj doc = BSON("a" << BSON_ARRAY(BSON("b" << 5)));
221 
222     BSONElementIterator cursor(&path, doc);
223 
224     ASSERT(cursor.more());
225     auto context = cursor.next();
226     ASSERT_BSONELT_EQ(doc.firstElement(), context.element());
227 
228     ASSERT(!cursor.more());
229 }
230 
TEST(Path,MatchSubpathWithTraverseLeafFalseReturnsLeafArrayOnPath)231 TEST(Path, MatchSubpathWithTraverseLeafFalseReturnsLeafArrayOnPath) {
232     ElementPath path;
233     ASSERT_OK(path.init("a.b.c"));
234     path.setLeafArrayBehavior(ElementPath::LeafArrayBehavior::kNoTraversal);
235     path.setNonLeafArrayBehavior(ElementPath::NonLeafArrayBehavior::kMatchSubpath);
236 
237     BSONObj doc = BSON("a" << BSON("b" << BSON("c" << BSON_ARRAY(1 << 2))));
238 
239     BSONElementIterator cursor(&path, doc);
240 
241     ASSERT(cursor.more());
242     auto context = cursor.next();
243     ASSERT_BSONELT_EQ(fromjson("{c: [1, 2]}").firstElement(), context.element());
244 
245     ASSERT(!cursor.more());
246 }
247 
TEST(Path,MatchSubpathWithTraverseLeafTrueReturnsLeafArrayAndValuesOnPath)248 TEST(Path, MatchSubpathWithTraverseLeafTrueReturnsLeafArrayAndValuesOnPath) {
249     ElementPath path;
250     ASSERT_OK(path.init("a.b.c"));
251     path.setLeafArrayBehavior(ElementPath::LeafArrayBehavior::kTraverse);
252     path.setNonLeafArrayBehavior(ElementPath::NonLeafArrayBehavior::kMatchSubpath);
253 
254     BSONObj doc = BSON("a" << BSON("b" << BSON("c" << BSON_ARRAY(1 << 2))));
255 
256     BSONElementIterator cursor(&path, doc);
257 
258     ASSERT(cursor.more());
259     BSONElementIterator::Context context = cursor.next();
260     ASSERT_EQUALS(1, context.element().numberInt());
261 
262     ASSERT(cursor.more());
263     context = cursor.next();
264     ASSERT_EQUALS(2, context.element().numberInt());
265 
266     ASSERT(cursor.more());
267     context = cursor.next();
268     ASSERT_BSONELT_EQ(fromjson("{c: [1, 2]}").firstElement(), context.element());
269 
270     ASSERT(!cursor.more());
271 }
272 
TEST(Path,MatchSubpathWithMultipleArraysReturnsOutermostArray)273 TEST(Path, MatchSubpathWithMultipleArraysReturnsOutermostArray) {
274     ElementPath path;
275     ASSERT_OK(path.init("a.b.c"));
276     path.setLeafArrayBehavior(ElementPath::LeafArrayBehavior::kTraverse);
277     path.setNonLeafArrayBehavior(ElementPath::NonLeafArrayBehavior::kMatchSubpath);
278 
279     BSONObj doc = fromjson("{a: [{b: [{c: [1]}]}]}");
280 
281     BSONElementIterator cursor(&path, doc);
282 
283     ASSERT(cursor.more());
284     auto context = cursor.next();
285     ASSERT_BSONELT_EQ(fromjson("{a: [{b: [{c: [1]}]}]}").firstElement(), context.element());
286 
287     ASSERT(!cursor.more());
288 }
289 
TEST(Path,NoTraversalOfNonLeafArrayReturnsNothingWithNonLeafArrayInDoc)290 TEST(Path, NoTraversalOfNonLeafArrayReturnsNothingWithNonLeafArrayInDoc) {
291     ElementPath path;
292     ASSERT_OK(path.init("a.b"));
293     path.setLeafArrayBehavior(ElementPath::LeafArrayBehavior::kTraverse);
294     path.setNonLeafArrayBehavior(ElementPath::NonLeafArrayBehavior::kNoTraversal);
295 
296     BSONObj doc = fromjson("{a: [{b: 1}]}");
297 
298     BSONElementIterator cursor(&path, doc);
299     ASSERT(!cursor.more());
300 }
301 
TEST(Path,MatchSubpathWithNumericalPathComponentReturnsEntireArray)302 TEST(Path, MatchSubpathWithNumericalPathComponentReturnsEntireArray) {
303     ElementPath path;
304     ASSERT_OK(path.init("a.0.b"));
305     path.setLeafArrayBehavior(ElementPath::LeafArrayBehavior::kTraverse);
306     path.setNonLeafArrayBehavior(ElementPath::NonLeafArrayBehavior::kMatchSubpath);
307 
308     BSONObj doc = fromjson("{a: [{b: 1}]}");
309 
310     BSONElementIterator cursor(&path, doc);
311 
312     ASSERT(cursor.more());
313     auto context = cursor.next();
314     ASSERT_BSONELT_EQ(fromjson("{a: [{b: 1}]}").firstElement(), context.element());
315 
316     ASSERT(!cursor.more());
317 }
318 
TEST(Path,ArrayIndex1)319 TEST(Path, ArrayIndex1) {
320     ElementPath p;
321     ASSERT(p.init("a.1").isOK());
322 
323     BSONObj doc = BSON("a" << BSON_ARRAY(5 << 7 << 3));
324 
325     BSONElementIterator cursor(&p, doc);
326 
327     ASSERT(cursor.more());
328     BSONElementIterator::Context e = cursor.next();
329     ASSERT_EQUALS(7, e.element().numberInt());
330 
331     ASSERT(!cursor.more());
332 }
333 
TEST(Path,ArrayIndex2)334 TEST(Path, ArrayIndex2) {
335     ElementPath p;
336     ASSERT(p.init("a.1").isOK());
337 
338     BSONObj doc = BSON("a" << BSON_ARRAY(5 << BSON_ARRAY(2 << 4) << 3));
339 
340     BSONElementIterator cursor(&p, doc);
341 
342     ASSERT(cursor.more());
343     BSONElementIterator::Context e = cursor.next();
344     ASSERT_EQUALS(Array, e.element().type());
345 
346     ASSERT(!cursor.more());
347 }
348 
TEST(Path,ArrayIndex3)349 TEST(Path, ArrayIndex3) {
350     ElementPath p;
351     ASSERT(p.init("a.1").isOK());
352 
353     BSONObj doc = BSON("a" << BSON_ARRAY(5 << BSON("1" << 4) << 3));
354 
355     BSONElementIterator cursor(&p, doc);
356 
357     ASSERT(cursor.more());
358     BSONElementIterator::Context e = cursor.next();
359     ASSERT_EQUALS(4, e.element().numberInt());
360 
361     ASSERT(cursor.more());
362     e = cursor.next();
363     ASSERT_BSONOBJ_EQ(BSON("1" << 4), e.element().Obj());
364 
365     ASSERT(!cursor.more());
366 }
367 
TEST(Path,ArrayIndexNested1)368 TEST(Path, ArrayIndexNested1) {
369     ElementPath p;
370     ASSERT(p.init("a.1.b").isOK());
371 
372     BSONObj doc = BSON("a" << BSON_ARRAY(5 << BSON("b" << 4) << 3));
373 
374     BSONElementIterator cursor(&p, doc);
375 
376     ASSERT(cursor.more());
377     BSONElementIterator::Context e = cursor.next();
378     ASSERT(e.element().eoo());
379 
380     ASSERT(cursor.more());
381     e = cursor.next();
382     ASSERT_EQUALS(4, e.element().numberInt());
383 
384 
385     ASSERT(!cursor.more());
386 }
387 
TEST(Path,ArrayIndexNested2)388 TEST(Path, ArrayIndexNested2) {
389     ElementPath p;
390     ASSERT(p.init("a.1.b").isOK());
391 
392     BSONObj doc = BSON("a" << BSON_ARRAY(5 << BSON_ARRAY(BSON("b" << 4)) << 3));
393 
394     BSONElementIterator cursor(&p, doc);
395 
396     ASSERT(cursor.more());
397     BSONElementIterator::Context e = cursor.next();
398     ASSERT_EQUALS(4, e.element().numberInt());
399 
400 
401     ASSERT(!cursor.more());
402 }
403 
404 // SERVER-15899: test iteration using a path that generates no elements, but traverses a long
405 // array containing subdocuments with nested arrays.
TEST(Path,NonMatchingLongArrayOfSubdocumentsWithNestedArrays)406 TEST(Path, NonMatchingLongArrayOfSubdocumentsWithNestedArrays) {
407     ElementPath p;
408     ASSERT(p.init("a.b.x").isOK());
409 
410     // Build the document {a: [{b: []}, {b: []}, {b: []}, ...]}.
411     BSONObj subdoc = BSON("b" << BSONArray());
412     BSONArrayBuilder builder;
413     for (int i = 0; i < 100 * 1000; ++i) {
414         builder.append(subdoc);
415     }
416     BSONObj doc = BSON("a" << builder.arr());
417 
418     BSONElementIterator cursor(&p, doc);
419 
420     // The path "a.b.x" matches no elements.
421     ASSERT(!cursor.more());
422 }
423 
424 // When multiple arrays are traversed implicitly in the same path,
425 // ElementIterator::Context::arrayOffset() should always refer to the current offset of the
426 // outermost array that is implicitly traversed.
TEST(Path,NestedArrayImplicitTraversal)427 TEST(Path, NestedArrayImplicitTraversal) {
428     ElementPath p;
429     ASSERT(p.init("a.b").isOK());
430     BSONObj doc = fromjson("{a: [{b: [2, 3]}, {b: [4, 5]}]}");
431     BSONElementIterator cursor(&p, doc);
432 
433     ASSERT(cursor.more());
434     ElementIterator::Context e = cursor.next();
435     ASSERT_EQUALS(NumberInt, e.element().type());
436     ASSERT_EQUALS(2, e.element().numberInt());
437     ASSERT_EQUALS("0", e.arrayOffset().fieldNameStringData());
438 
439     ASSERT(cursor.more());
440     e = cursor.next();
441     ASSERT_EQUALS(NumberInt, e.element().type());
442     ASSERT_EQUALS(3, e.element().numberInt());
443     ASSERT_EQUALS("0", e.arrayOffset().fieldNameStringData());
444 
445     ASSERT(cursor.more());
446     e = cursor.next();
447     ASSERT_EQUALS(Array, e.element().type());
448     ASSERT_BSONOBJ_EQ(BSON("0" << 2 << "1" << 3), e.element().Obj());
449     ASSERT_EQUALS("0", e.arrayOffset().fieldNameStringData());
450 
451     ASSERT(cursor.more());
452     e = cursor.next();
453     ASSERT_EQUALS(NumberInt, e.element().type());
454     ASSERT_EQUALS(4, e.element().numberInt());
455     ASSERT_EQUALS("1", e.arrayOffset().fieldNameStringData());
456 
457     ASSERT(cursor.more());
458     e = cursor.next();
459     ASSERT_EQUALS(NumberInt, e.element().type());
460     ASSERT_EQUALS(5, e.element().numberInt());
461     ASSERT_EQUALS("1", e.arrayOffset().fieldNameStringData());
462 
463     ASSERT(cursor.more());
464     e = cursor.next();
465     ASSERT_EQUALS(Array, e.element().type());
466     ASSERT_BSONOBJ_EQ(BSON("0" << 4 << "1" << 5), e.element().Obj());
467     ASSERT_EQUALS("1", e.arrayOffset().fieldNameStringData());
468 
469     ASSERT(!cursor.more());
470 }
471 
472 // SERVER-14886: when an array is being traversed explictly at the same time that a nested array
473 // is being traversed implicitly, ElementIterator::Context::arrayOffset() should return the
474 // current offset of the array being implicitly traversed.
TEST(Path,ArrayOffsetWithImplicitAndExplicitTraversal)475 TEST(Path, ArrayOffsetWithImplicitAndExplicitTraversal) {
476     ElementPath p;
477     ASSERT(p.init("a.0.b").isOK());
478     BSONObj doc = fromjson("{a: [{b: [2, 3]}, {b: [4, 5]}]}");
479     BSONElementIterator cursor(&p, doc);
480 
481     ASSERT(cursor.more());
482     ElementIterator::Context e = cursor.next();
483     ASSERT_EQUALS(EOO, e.element().type());
484     ASSERT_EQUALS("0", e.arrayOffset().fieldNameStringData());  // First elt of outer array.
485 
486     ASSERT(cursor.more());
487     e = cursor.next();
488     ASSERT_EQUALS(NumberInt, e.element().type());
489     ASSERT_EQUALS(2, e.element().numberInt());
490     ASSERT_EQUALS("0", e.arrayOffset().fieldNameStringData());  // First elt of inner array.
491 
492     ASSERT(cursor.more());
493     e = cursor.next();
494     ASSERT_EQUALS(NumberInt, e.element().type());
495     ASSERT_EQUALS(3, e.element().numberInt());
496     ASSERT_EQUALS("1", e.arrayOffset().fieldNameStringData());  // Second elt of inner array.
497 
498     ASSERT(cursor.more());
499     e = cursor.next();
500     ASSERT_EQUALS(Array, e.element().type());
501     ASSERT_BSONOBJ_EQ(BSON("0" << 2 << "1" << 3), e.element().Obj());
502     ASSERT(e.arrayOffset().eoo());
503 
504     ASSERT(cursor.more());
505     e = cursor.next();
506     ASSERT_EQUALS(EOO, e.element().type());
507     ASSERT_EQUALS("1", e.arrayOffset().fieldNameStringData());  // Second elt of outer array.
508 
509     ASSERT(!cursor.more());
510 }
511 
TEST(SimpleArrayElementIterator,SimpleNoArrayLast1)512 TEST(SimpleArrayElementIterator, SimpleNoArrayLast1) {
513     BSONObj obj = BSON("a" << BSON_ARRAY(5 << BSON("x" << 6) << BSON_ARRAY(7 << 9) << 11));
514     SimpleArrayElementIterator i(obj["a"], false);
515 
516     ASSERT(i.more());
517     ElementIterator::Context e = i.next();
518     ASSERT_EQUALS(5, e.element().numberInt());
519 
520     ASSERT(i.more());
521     e = i.next();
522     ASSERT_EQUALS(6, e.element().Obj()["x"].numberInt());
523 
524     ASSERT(i.more());
525     e = i.next();
526     ASSERT_EQUALS(7, e.element().Obj().firstElement().numberInt());
527 
528     ASSERT(i.more());
529     e = i.next();
530     ASSERT_EQUALS(11, e.element().numberInt());
531 
532     ASSERT(!i.more());
533 }
534 
TEST(SimpleArrayElementIterator,SimpleArrayLast1)535 TEST(SimpleArrayElementIterator, SimpleArrayLast1) {
536     BSONObj obj = BSON("a" << BSON_ARRAY(5 << BSON("x" << 6) << BSON_ARRAY(7 << 9) << 11));
537     SimpleArrayElementIterator i(obj["a"], true);
538 
539     ASSERT(i.more());
540     ElementIterator::Context e = i.next();
541     ASSERT_EQUALS(5, e.element().numberInt());
542 
543     ASSERT(i.more());
544     e = i.next();
545     ASSERT_EQUALS(6, e.element().Obj()["x"].numberInt());
546 
547     ASSERT(i.more());
548     e = i.next();
549     ASSERT_EQUALS(7, e.element().Obj().firstElement().numberInt());
550 
551     ASSERT(i.more());
552     e = i.next();
553     ASSERT_EQUALS(11, e.element().numberInt());
554 
555     ASSERT(i.more());
556     e = i.next();
557     ASSERT_EQUALS(Array, e.element().type());
558 
559     ASSERT(!i.more());
560 }
561 
TEST(SingleElementElementIterator,Simple1)562 TEST(SingleElementElementIterator, Simple1) {
563     BSONObj obj = BSON("x" << 3 << "y" << 5);
564     SingleElementElementIterator i(obj["y"]);
565 
566     ASSERT(i.more());
567     ElementIterator::Context e = i.next();
568     ASSERT_EQUALS(5, e.element().numberInt());
569 
570     ASSERT(!i.more());
571 }
572 }
573