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/bson/mutable/algorithm.h"
34 
35 #include "mongo/bson/mutable/document.h"
36 #include "mongo/bson/mutable/mutable_bson_test_utils.h"
37 #include "mongo/db/json.h"
38 #include "mongo/db/query/collation/collator_interface_mock.h"
39 #include "mongo/platform/basic.h"
40 #include "mongo/unittest/unittest.h"
41 
42 namespace {
43 
44 using mongo::CollatorInterfaceMock;
45 using mongo::Status;
46 using namespace mongo::mutablebson;
47 
48 class DocumentTest : public mongo::unittest::Test {
49 public:
DocumentTest()50     DocumentTest() : _doc() {}
51 
doc()52     Document& doc() {
53         return _doc;
54     }
55 
56 private:
57     Document _doc;
58 };
59 
TEST_F(DocumentTest,FindInEmptyObject)60 TEST_F(DocumentTest, FindInEmptyObject) {
61     Element leftChild = doc().root().leftChild();
62     ASSERT_FALSE(leftChild.ok());
63     Element found = findElementNamed(leftChild, "X");
64     ASSERT_FALSE(found.ok());
65     ASSERT_EQUALS(&leftChild.getDocument(), &found.getDocument());
66     ASSERT_EQUALS(leftChild.getIdx(), found.getIdx());
67 }
68 
69 class OneChildTest : public DocumentTest {
setUp()70     virtual void setUp() {
71         ASSERT_EQUALS(Status::OK(), doc().root().appendBool("t", true));
72     }
73 };
74 
TEST_F(OneChildTest,FindNoMatch)75 TEST_F(OneChildTest, FindNoMatch) {
76     Element leftChild = doc().root().leftChild();
77     ASSERT_TRUE(leftChild.ok());
78     Element found = findElementNamed(leftChild, "f");
79     ASSERT_FALSE(found.ok());
80     ASSERT_EQUALS(&leftChild.getDocument(), &found.getDocument());
81 }
82 
TEST_F(OneChildTest,FindMatch)83 TEST_F(OneChildTest, FindMatch) {
84     Element leftChild = doc().root().leftChild();
85     ASSERT_TRUE(leftChild.ok());
86     Element found = findElementNamed(leftChild, "t");
87     ASSERT_TRUE(found.ok());
88     ASSERT_EQUALS(&leftChild.getDocument(), &found.getDocument());
89     ASSERT_EQUALS(found.getFieldName(), "t");
90     found = findElementNamed(found.rightSibling(), "t");
91     ASSERT_FALSE(found.ok());
92     ASSERT_EQUALS(&leftChild.getDocument(), &found.getDocument());
93 }
94 
95 class ManyChildrenTest : public DocumentTest {
setUp()96     virtual void setUp() {
97         ASSERT_EQUALS(Status::OK(), doc().root().appendString("begin", "a"));
98         ASSERT_EQUALS(Status::OK(), doc().root().appendString("repeated_sparse", "b"));
99         ASSERT_EQUALS(Status::OK(), doc().root().appendString("repeated_dense", "c"));
100         ASSERT_EQUALS(Status::OK(), doc().root().appendString("repeated_dense", "d"));
101         ASSERT_EQUALS(Status::OK(), doc().root().appendString("middle", "e"));
102         ASSERT_EQUALS(Status::OK(), doc().root().appendString("repeated_sparse", "f"));
103         ASSERT_EQUALS(Status::OK(), doc().root().appendString("end", "g"));
104     }
105 };
106 
TEST_F(ManyChildrenTest,FindAtStart)107 TEST_F(ManyChildrenTest, FindAtStart) {
108     static const char kName[] = "begin";
109     Element leftChild = doc().root().leftChild();
110     ASSERT_TRUE(leftChild.ok());
111     Element found = findElementNamed(leftChild, kName);
112     ASSERT_TRUE(found.ok());
113     ASSERT_EQUALS(found.getFieldName(), kName);
114     ASSERT_EQUALS(&leftChild.getDocument(), &found.getDocument());
115     ASSERT_FALSE(findElementNamed(found.rightSibling(), kName).ok());
116 }
117 
TEST_F(ManyChildrenTest,FindInMiddle)118 TEST_F(ManyChildrenTest, FindInMiddle) {
119     static const char kName[] = "middle";
120     Element leftChild = doc().root().leftChild();
121     ASSERT_TRUE(leftChild.ok());
122     Element found = findElementNamed(leftChild, kName);
123     ASSERT_TRUE(found.ok());
124     ASSERT_EQUALS(found.getFieldName(), kName);
125     ASSERT_EQUALS(&leftChild.getDocument(), &found.getDocument());
126     ASSERT_FALSE(findElementNamed(found.rightSibling(), kName).ok());
127 }
128 
TEST_F(ManyChildrenTest,FindAtEnd)129 TEST_F(ManyChildrenTest, FindAtEnd) {
130     static const char kName[] = "end";
131     Element leftChild = doc().root().leftChild();
132     ASSERT_TRUE(leftChild.ok());
133     Element found = findElementNamed(leftChild, kName);
134     ASSERT_TRUE(found.ok());
135     ASSERT_EQUALS(found.getFieldName(), kName);
136     ASSERT_EQUALS(&leftChild.getDocument(), &found.getDocument());
137     ASSERT_FALSE(findElementNamed(found.rightSibling(), kName).ok());
138 }
139 
TEST_F(ManyChildrenTest,FindRepeatedSparse)140 TEST_F(ManyChildrenTest, FindRepeatedSparse) {
141     static const char kName[] = "repeated_sparse";
142     Element leftChild = doc().root().leftChild();
143     ASSERT_TRUE(leftChild.ok());
144     Element first = findElementNamed(leftChild, kName);
145     ASSERT_TRUE(first.ok());
146     ASSERT_EQUALS(first.getFieldName(), kName);
147     ASSERT_EQUALS(&leftChild.getDocument(), &first.getDocument());
148     Element second = findElementNamed(first.rightSibling(), kName);
149     ASSERT_TRUE(second.ok());
150     ASSERT_EQUALS(&first.getDocument(), &second.getDocument());
151     ASSERT_NOT_EQUALS(first.getIdx(), second.getIdx());
152     Element none = findElementNamed(second.rightSibling(), kName);
153     ASSERT_FALSE(none.ok());
154 }
155 
TEST_F(ManyChildrenTest,FindRepeatedDense)156 TEST_F(ManyChildrenTest, FindRepeatedDense) {
157     static const char kName[] = "repeated_dense";
158     Element leftChild = doc().root().leftChild();
159     ASSERT_TRUE(leftChild.ok());
160     Element first = findElementNamed(leftChild, kName);
161     ASSERT_TRUE(first.ok());
162     ASSERT_EQUALS(first.getFieldName(), kName);
163     ASSERT_EQUALS(&leftChild.getDocument(), &first.getDocument());
164     Element second = findElementNamed(first.rightSibling(), kName);
165     ASSERT_TRUE(second.ok());
166     ASSERT_EQUALS(&first.getDocument(), &second.getDocument());
167     ASSERT_NOT_EQUALS(first.getIdx(), second.getIdx());
168     Element none = findElementNamed(second.rightSibling(), kName);
169     ASSERT_FALSE(none.ok());
170 }
171 
TEST_F(ManyChildrenTest,FindDoesNotSearchWithinChildren)172 TEST_F(ManyChildrenTest, FindDoesNotSearchWithinChildren) {
173     static const char kName[] = "in_child";
174     Element found_before_add = findElementNamed(doc().root().leftChild(), kName);
175     ASSERT_FALSE(found_before_add.ok());
176     Element subdoc = doc().makeElementObject("child");
177     ASSERT_EQUALS(Status::OK(), doc().root().pushBack(subdoc));
178     ASSERT_EQUALS(Status::OK(), subdoc.appendBool(kName, true));
179     Element found_after_add = findElementNamed(doc().root().leftChild(), kName);
180     ASSERT_FALSE(found_after_add.ok());
181 }
182 
TEST_F(ManyChildrenTest,getNthSibling)183 TEST_F(ManyChildrenTest, getNthSibling) {
184     const Element leftChild = doc().root().leftChild();
185     ASSERT_TRUE(leftChild.ok());
186     const Element rightChild = doc().root().rightChild();
187     ASSERT_TRUE(rightChild.ok());
188 
189     // Check that moving zero is a no-op
190     Element zeroAway = getNthSibling(leftChild, 0);
191     ASSERT_TRUE(zeroAway.ok());
192     ASSERT_EQUALS(leftChild, zeroAway);
193     zeroAway = getNthSibling(rightChild, 0);
194     ASSERT_TRUE(zeroAway.ok());
195     ASSERT_EQUALS(rightChild, zeroAway);
196 
197     // Check that moving left of leftmost gets a not-ok element.
198     Element badLeft = getNthSibling(leftChild, -1);
199     ASSERT_FALSE(badLeft.ok());
200 
201     // Check that moving right of rightmost gets a non-ok element.
202     Element badRight = getNthSibling(rightChild, 1);
203     ASSERT_FALSE(badRight.ok());
204 
205     // Check that the moving one right from leftmost gets us the expected element.
206     Element target = leftChild.rightSibling();
207     ASSERT_TRUE(target.ok());
208     Element query = getNthSibling(leftChild, 1);
209     ASSERT_TRUE(target.ok());
210     ASSERT_EQUALS(target, query);
211 
212     // And the same from the other side
213     target = rightChild.leftSibling();
214     ASSERT_TRUE(target.ok());
215     query = getNthSibling(rightChild, -1);
216     ASSERT_TRUE(target.ok());
217     ASSERT_EQUALS(target, query);
218 
219     // Ensure that walking more chidren than we have gets us past the end
220     const int children = countChildren(doc().root());
221     query = getNthSibling(leftChild, children);
222     ASSERT_FALSE(query.ok());
223     query = getNthSibling(rightChild, -children);
224     ASSERT_FALSE(query.ok());
225 
226     // Ensure that walking all the children in either direction gets
227     // us to the other right/left child.
228     query = getNthSibling(leftChild, children - 1);
229     ASSERT_TRUE(query.ok());
230     ASSERT_EQUALS(rightChild, query);
231     query = getNthSibling(rightChild, -(children - 1));
232     ASSERT_TRUE(query.ok());
233     ASSERT_EQUALS(leftChild, query);
234 }
235 
236 class CountTest : public DocumentTest {
setUp()237     virtual void setUp() {
238         Element root = doc().root();
239 
240         ASSERT_OK(root.appendInt("leaf", 0));
241 
242         Element one = doc().makeElementObject("oneChild");
243         ASSERT_TRUE(one.ok());
244         ASSERT_OK(one.appendInt("one", 1));
245         ASSERT_OK(root.pushBack(one));
246 
247         Element threeChildren = doc().makeElementObject("threeChildren");
248         ASSERT_TRUE(one.ok());
249         ASSERT_OK(threeChildren.appendInt("one", 1));
250         ASSERT_OK(threeChildren.appendInt("two", 2));
251         ASSERT_OK(threeChildren.appendInt("three", 3));
252         ASSERT_OK(root.pushBack(threeChildren));
253     }
254 };
255 
TEST_F(CountTest,EmptyDocument)256 TEST_F(CountTest, EmptyDocument) {
257     // Doesn't use the fixture but belongs in the same group of tests.
258     Document doc;
259     ASSERT_EQUALS(countChildren(doc.root()), 0u);
260 }
261 
TEST_F(CountTest,EmptyElement)262 TEST_F(CountTest, EmptyElement) {
263     Element leaf = findFirstChildNamed(doc().root(), "leaf");
264     ASSERT_TRUE(leaf.ok());
265     ASSERT_EQUALS(countChildren(leaf), 0u);
266 }
267 
TEST_F(CountTest,OneChildElement)268 TEST_F(CountTest, OneChildElement) {
269     Element oneChild = findFirstChildNamed(doc().root(), "oneChild");
270     ASSERT_TRUE(oneChild.ok());
271     ASSERT_EQUALS(countChildren(oneChild), 1u);
272 }
273 
TEST_F(CountTest,ManyChildren)274 TEST_F(CountTest, ManyChildren) {
275     Element threeChildren = findFirstChildNamed(doc().root(), "threeChildren");
276     ASSERT_TRUE(threeChildren.ok());
277     ASSERT_EQUALS(countChildren(threeChildren), 3u);
278 }
279 
TEST_F(CountTest,CountSiblingsNone)280 TEST_F(CountTest, CountSiblingsNone) {
281     ConstElement current = findFirstChildNamed(doc().root(), "oneChild");
282     ASSERT_TRUE(current.ok());
283 
284     current = current.leftChild();
285     ASSERT_TRUE(current.ok());
286 
287     ASSERT_EQUALS(0U, countSiblingsLeft(current));
288     ASSERT_EQUALS(0U, countSiblingsRight(current));
289 }
290 
TEST_F(CountTest,CountSiblingsMany)291 TEST_F(CountTest, CountSiblingsMany) {
292     ConstElement current = findFirstChildNamed(doc().root(), "threeChildren");
293     ASSERT_TRUE(current.ok());
294 
295     current = current.leftChild();
296     ASSERT_TRUE(current.ok());
297 
298     ASSERT_EQUALS(0U, countSiblingsLeft(current));
299     ASSERT_EQUALS(2U, countSiblingsRight(current));
300 
301     current = current.rightSibling();
302     ASSERT_TRUE(current.ok());
303     ASSERT_EQUALS(1U, countSiblingsLeft(current));
304     ASSERT_EQUALS(1U, countSiblingsRight(current));
305 
306     current = current.rightSibling();
307     ASSERT_TRUE(current.ok());
308     ASSERT_EQUALS(2U, countSiblingsLeft(current));
309     ASSERT_EQUALS(0U, countSiblingsRight(current));
310 
311     current = current.rightSibling();
312     ASSERT_FALSE(current.ok());
313 }
314 
TEST(DeduplicateTest,ManyDuplicates)315 TEST(DeduplicateTest, ManyDuplicates) {
316     Document doc(mongo::fromjson("{ x : [ 1, 2, 2, 3, 3, 3, 4, 4, 4 ] }"));
317     deduplicateChildren(doc.root().leftChild(), woEqual(nullptr, false));
318     ASSERT_TRUE(checkDoc(doc, mongo::fromjson("{x : [ 1, 2, 3, 4 ]}")));
319 }
320 
TEST(FullNameTest,RootField)321 TEST(FullNameTest, RootField) {
322     Document doc(mongo::fromjson("{ x : 1 }"));
323     ASSERT_EQUALS("x", getFullName(doc.root().leftChild()));
324 }
325 
TEST(FullNameTest,OneLevel)326 TEST(FullNameTest, OneLevel) {
327     Document doc(mongo::fromjson("{ x : { y: 1 } }"));
328     ASSERT_EQUALS("x.y", getFullName(doc.root().leftChild().leftChild()));
329 }
330 
TEST(FullNameTest,InsideArray)331 TEST(FullNameTest, InsideArray) {
332     Document doc(mongo::fromjson("{ x : { y: [ 1 , 2 ] } }"));
333     ASSERT_EQUALS("x.y.1",
334                   getFullName(doc.root().leftChild().leftChild().leftChild().rightSibling()));
335 }
336 
TEST(WoLessTest,CollationAware)337 TEST(WoLessTest, CollationAware) {
338     CollatorInterfaceMock collator(CollatorInterfaceMock::MockType::kReverseString);
339     Document less(mongo::fromjson("{ x: 'cbc' }"));
340     Document greater(mongo::fromjson("{ x: 'abd' }"));
341 
342     woLess comp(&collator, true);
343     ASSERT_TRUE(comp(less.root(), greater.root()));
344     ASSERT_FALSE(comp(greater.root(), less.root()));
345 }
346 
TEST(WoGreaterTest,CollationAware)347 TEST(WoGreaterTest, CollationAware) {
348     CollatorInterfaceMock collator(CollatorInterfaceMock::MockType::kReverseString);
349     Document less(mongo::fromjson("{ x: 'cbc' }"));
350     Document greater(mongo::fromjson("{ x: 'abd' }"));
351 
352     woGreater comp(&collator, true);
353     ASSERT_TRUE(comp(greater.root(), less.root()));
354     ASSERT_FALSE(comp(less.root(), greater.root()));
355 }
356 
TEST(WoEqualTest,CollationAware)357 TEST(WoEqualTest, CollationAware) {
358     CollatorInterfaceMock collator(CollatorInterfaceMock::MockType::kAlwaysEqual);
359     Document docA(mongo::fromjson("{ x: 'not' }"));
360     Document docB(mongo::fromjson("{ x: 'equal' }"));
361 
362     woEqual comp(&collator, true);
363     ASSERT_TRUE(comp(docA.root(), docB.root()));
364     ASSERT_TRUE(comp(docB.root(), docA.root()));
365 }
366 
TEST(WoEqualToTest,CollationAware)367 TEST(WoEqualToTest, CollationAware) {
368     CollatorInterfaceMock collator(CollatorInterfaceMock::MockType::kAlwaysEqual);
369     Document docA(mongo::fromjson("{ x: 'not' }"));
370     Document docB(mongo::fromjson("{ x: 'equal' }"));
371 
372     woEqualTo comp(docA.root(), &collator, true);
373     ASSERT_TRUE(comp(docB.root()));
374 }
375 
376 }  // namespace
377