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 <algorithm>
34 #include <cstddef>
35 #include <vector>
36
37 #include "mongo/base/string_data_comparator_interface.h"
38 #include "mongo/bson/mutable/const_element.h"
39 #include "mongo/bson/mutable/element.h"
40 #include "mongo/util/mongoutils/str.h"
41
42 namespace mongo {
43 namespace mutablebson {
44
45 /** For an overview of mutable BSON, please see the file document.h in this directory.
46 *
47 * This file defines, in analogy with <algorithm>, a collection of useful algorithms for
48 * use with mutable BSON classes. In particular, algorithms for searching, sorting,
49 * indexed access, and counting are included.
50 */
51
52 /** 'findElement' searches rightward among the sibiling Elements of 'first', returning an
53 * Element representing the first item matching the predicate 'predicate'. If no Element
54 * matches, then the 'ok' method on the returned Element will return false.
55 */
56 template <typename ElementType, typename Predicate>
findElement(ElementType first,Predicate predicate)57 inline ElementType findElement(ElementType first, Predicate predicate) {
58 while (first.ok() && !predicate(first))
59 first = first.rightSibling();
60 return first;
61 }
62
63 /** A predicate for findElement that matches on the field name of Elements. */
64 struct FieldNameEquals {
65 // The lifetime of this object must be a subset of the lifetime of 'fieldName'.
FieldNameEqualsFieldNameEquals66 explicit FieldNameEquals(StringData fieldName) : fieldName(fieldName) {}
67
operatorFieldNameEquals68 bool operator()(const ConstElement& element) const {
69 return (fieldName == element.getFieldName());
70 }
71
72 StringData fieldName;
73 };
74
75 /** An overload of findElement that delegates to the special implementation
76 * Element::findElementNamed to reduce traffic across the Element API.
77 */
78 template <typename ElementType>
findElement(ElementType first,FieldNameEquals predicate)79 inline ElementType findElement(ElementType first, FieldNameEquals predicate) {
80 return first.ok() ? first.findElementNamed(predicate.fieldName) : first;
81 }
82
83 /** A convenience wrapper around findElement<ElementType, FieldNameEquals>. */
84 template <typename ElementType>
findElementNamed(ElementType first,StringData fieldName)85 inline ElementType findElementNamed(ElementType first, StringData fieldName) {
86 return findElement(first, FieldNameEquals(fieldName));
87 }
88
89 /** Finds the first child under 'parent' that matches the given predicate. If no such child
90 * Element is found, the returned Element's 'ok' method will return false.
91 */
92 template <typename ElementType, typename Predicate>
findFirstChild(ElementType parent,Predicate predicate)93 inline ElementType findFirstChild(ElementType parent, Predicate predicate) {
94 return findElement(parent.leftchild(), predicate);
95 }
96
97 /** An overload of findFirstChild that delegates to the special implementation
98 * Element::findFirstChildNamed to reduce traffic across the Element API.
99 */
100 template <typename ElementType>
findFirstChild(ElementType parent,FieldNameEquals predicate)101 inline ElementType findFirstChild(ElementType parent, FieldNameEquals predicate) {
102 return parent.ok() ? parent.findFirstChildNamed(predicate.fieldName) : parent;
103 }
104
105 /** Finds the first child under 'parent' that matches the given field name. If no such child
106 * Element is found, the returned Element's 'ok' method will return false.
107 */
108 template <typename ElementType>
findFirstChildNamed(ElementType parent,StringData fieldName)109 inline ElementType findFirstChildNamed(ElementType parent, StringData fieldName) {
110 return findFirstChild(parent, FieldNameEquals(fieldName));
111 }
112
113 /** A less-than ordering for Elements that compares based on the Element field names. */
114 class FieldNameLessThan {
115 // TODO: This should possibly derive from std::binary_function.
116 public:
operator()117 inline bool operator()(const ConstElement& left, const ConstElement& right) const {
118 return left.getFieldName() < right.getFieldName();
119 }
120 };
121
122 /** Sort any children of Element 'parent' by way of Comparator 'comp', which should provide
123 * an operator() that takes two const Element&'s and implements a strict weak ordering.
124 */
125 template <typename Comparator>
sortChildren(Element parent,Comparator comp)126 void sortChildren(Element parent, Comparator comp) {
127 // TODO: The following works, but obviously is not ideal.
128
129 // First, build a vector of the children.
130 std::vector<Element> children;
131 Element current = parent.leftChild();
132 while (current.ok()) {
133 children.push_back(current);
134 current = current.rightSibling();
135 }
136
137 // Then, sort the child vector with our comparator.
138 std::sort(children.begin(), children.end(), comp);
139
140 // Finally, reorder the children of parent according to the ordering established in
141 // 'children'.
142 std::vector<Element>::iterator where = children.begin();
143 const std::vector<Element>::iterator end = children.end();
144 for (; where != end; ++where) {
145 // Detach from its current location.
146 where->remove().transitional_ignore();
147 // Make it the new rightmost element.
148 parent.pushBack(*where).transitional_ignore();
149 }
150 }
151
152 /** Remove any consecutive children that compare as identical according to 'comp'. The
153 * children must be sorted (see sortChildren, above), and the equality comparator here
154 * must be compatible with the comparator used for the sort.
155 */
156 template <typename EqualityComparator>
deduplicateChildren(Element parent,EqualityComparator equal)157 void deduplicateChildren(Element parent, EqualityComparator equal) {
158 Element current = parent.leftChild();
159 while (current.ok()) {
160 Element next = current.rightSibling();
161 if (next.ok() && equal(current, next)) {
162 next.remove().transitional_ignore();
163 } else {
164 current = next;
165 }
166 }
167 }
168
169 /** A less-than ordering for Elements that compares based on woCompare */
170 class woLess {
171 // TODO: This should possibly derive from std::binary_function.
172 public:
173 woLess(const StringData::ComparatorInterface* comparator, bool considerFieldName = true)
_comp(comparator)174 : _comp(comparator), _considerFieldName(considerFieldName) {}
175
operator()176 inline bool operator()(const ConstElement& left, const ConstElement& right) const {
177 return left.compareWithElement(right, _comp, _considerFieldName) < 0;
178 }
179
180 private:
181 const StringData::ComparatorInterface* _comp = nullptr;
182 const bool _considerFieldName;
183 };
184
185 /** A greater-than ordering for Elements that compares based on woCompare */
186 class woGreater {
187 // TODO: This should possibly derive from std::binary_function.
188 public:
189 woGreater(const StringData::ComparatorInterface* comparator, bool considerFieldName = true)
_comp(comparator)190 : _comp(comparator), _considerFieldName(considerFieldName) {}
191
operator()192 inline bool operator()(const ConstElement& left, const ConstElement& right) const {
193 return left.compareWithElement(right, _comp, _considerFieldName) > 0;
194 }
195
196 private:
197 const StringData::ComparatorInterface* _comp = nullptr;
198 const bool _considerFieldName;
199 };
200
201 /** An equality predicate for elements that compares based on woCompare */
202 class woEqual {
203 // TODO: This should possibly derive from std::binary_function.
204 public:
205 woEqual(const StringData::ComparatorInterface* comparator, bool considerFieldName = true)
_comp(comparator)206 : _comp(comparator), _considerFieldName(considerFieldName) {}
207
operator()208 inline bool operator()(const ConstElement& left, const ConstElement& right) const {
209 return left.compareWithElement(right, _comp, _considerFieldName) == 0;
210 }
211
212 private:
213 const StringData::ComparatorInterface* _comp = nullptr;
214 const bool _considerFieldName;
215 };
216
217 /** An equality predicate for elements that compares based on woCompare */
218 class woEqualTo {
219 // TODO: This should possibly derive from std::binary_function.
220 public:
221 woEqualTo(const ConstElement& value,
222 const StringData::ComparatorInterface* comparator,
223 bool considerFieldName = true)
_value(value)224 : _value(value), _comp(comparator), _considerFieldName(considerFieldName) {}
225
operator()226 inline bool operator()(const ConstElement& elt) const {
227 return _value.compareWithElement(elt, _comp, _considerFieldName) == 0;
228 }
229
230 private:
231 const ConstElement _value;
232 const StringData::ComparatorInterface* _comp = nullptr;
233 const bool _considerFieldName;
234 };
235
236 // NOTE: Originally, these truly were algorithms, in that they executed the loop over a
237 // generic ElementType. However, these operations were later made intrinsic to
238 // Element/Document for performance reasons. These functions hare here for backward
239 // compatibility, and just delegate to the appropriate Element or ConstElement method of
240 // the same name.
241
242 /** Return the element that is 'n' Elements to the left in the sibling chain of 'element'. */
243 template <typename ElementType>
getNthLeftSibling(ElementType element,std::size_t n)244 ElementType getNthLeftSibling(ElementType element, std::size_t n) {
245 return element.leftSibling(n);
246 }
247
248 /** Return the element that is 'n' Elements to the right in the sibling chain of 'element'. */
249 template <typename ElementType>
getNthRightSibling(ElementType element,std::size_t n)250 ElementType getNthRightSibling(ElementType element, std::size_t n) {
251 return element.rightSibling(n);
252 }
253
254 /** Move 'n' Elements left or right in the sibling chain of 'element' */
255 template <typename ElementType>
getNthSibling(ElementType element,int n)256 ElementType getNthSibling(ElementType element, int n) {
257 return (n < 0) ? getNthLeftSibling(element, -n) : getNthRightSibling(element, n);
258 }
259
260 /** Get the child that is 'n' Elements to the right of 'element's left child. */
261 template <typename ElementType>
getNthChild(ElementType element,std::size_t n)262 ElementType getNthChild(ElementType element, std::size_t n) {
263 return element.findNthChild(n);
264 }
265
266 /** Returns the number of valid siblings to the left of 'element'. */
267 template <typename ElementType>
countSiblingsLeft(ElementType element)268 std::size_t countSiblingsLeft(ElementType element) {
269 return element.countSiblingsLeft();
270 }
271
272 /** Returns the number of valid siblings to the right of 'element'. */
273 template <typename ElementType>
countSiblingsRight(ElementType element)274 std::size_t countSiblingsRight(ElementType element) {
275 return element.countSiblingsRight();
276 }
277
278 /** Return the number of children of 'element'. */
279 template <typename ElementType>
countChildren(ElementType element)280 std::size_t countChildren(ElementType element) {
281 return element.countChildren();
282 }
283
284 /** Return the full (path) name of this element separating each name with the delim string. */
285 template <typename ElementType>
286 std::string getFullName(ElementType element, char delim = '.') {
287 std::vector<StringData> names;
288 ElementType curr = element;
289 while (curr.ok() && curr.parent().ok()) {
290 names.push_back(curr.getFieldName());
291 curr = curr.parent();
292 }
293
294 mongoutils::str::stream name;
295 bool first = true;
296 for (std::vector<StringData>::reverse_iterator it = names.rbegin(); it != names.rend(); ++it) {
297 if (!first)
298 name << delim;
299 name << *it;
300 first = false;
301 }
302 return name;
303 }
304 } // namespace mutablebson
305 } // namespace mongo
306