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/db/field_ref.h"
32
33 #include <algorithm> // for min
34
35 #include "mongo/util/assert_util.h"
36
37 namespace mongo {
38
39 const size_t FieldRef::kReserveAhead;
40
FieldRef()41 FieldRef::FieldRef() : _size(0), _cachedSize(0) {}
42
FieldRef(StringData path)43 FieldRef::FieldRef(StringData path) {
44 parse(path);
45 }
46
parse(StringData path)47 void FieldRef::parse(StringData path) {
48 clear();
49
50 if (path.size() == 0) {
51 return;
52 }
53
54 // We guarantee that accesses through getPart() will be valid while 'this' is. So we
55 // keep a copy in a local sting.
56
57 _dotted = path.toString();
58
59 // Separate the field parts using '.' as a delimiter.
60 std::string::iterator beg = _dotted.begin();
61 std::string::iterator cur = beg;
62 const std::string::iterator end = _dotted.end();
63 while (true) {
64 if (cur != end && *cur != '.') {
65 cur++;
66 continue;
67 }
68
69 // If cur != beg then we advanced cur in the loop above, so we have a real sequence
70 // of characters to add as a new part. Otherwise, we may be parsing something odd,
71 // like "..", and we need to add an empty StringData piece to represent the "part"
72 // in-between the dots. This also handles the case where 'beg' and 'cur' are both
73 // at 'end', which can happen if we are parsing anything with a terminal "."
74 // character. In that case, we still need to add an empty part, but we will break
75 // out of the loop below since we will not execute the guarded 'continue' and will
76 // instead reach the break statement.
77
78 if (cur != beg)
79 appendParsedPart(StringData(&*beg, cur - beg));
80 else
81 appendParsedPart(StringData());
82
83 if (cur != end) {
84 beg = ++cur;
85 continue;
86 }
87
88 break;
89 }
90 }
91
setPart(size_t i,StringData part)92 void FieldRef::setPart(size_t i, StringData part) {
93 dassert(i < _size);
94
95 if (_replacements.empty()) {
96 _replacements.resize(_size);
97 }
98
99 _replacements[i] = part.toString();
100 if (i < kReserveAhead) {
101 _fixed[i] = boost::none;
102 } else {
103 _variable[getIndex(i)] = boost::none;
104 }
105 }
106
appendPart(StringData part)107 void FieldRef::appendPart(StringData part) {
108 if (_replacements.empty()) {
109 _replacements.resize(_size);
110 }
111
112 _replacements.push_back(part.toString());
113
114 if (_size < kReserveAhead) {
115 _fixed[_size] = boost::none;
116 } else {
117 _variable.push_back(boost::none);
118 }
119 _size++;
120 }
121
removeLastPart()122 void FieldRef::removeLastPart() {
123 if (_size == 0) {
124 return;
125 }
126
127 if (!_replacements.empty()) {
128 _replacements.pop_back();
129 }
130
131 if (_size > kReserveAhead) {
132 dassert(_variable.size() == _size - kReserveAhead);
133 _variable.pop_back();
134 }
135
136 _size--;
137 }
138
appendParsedPart(StringData part)139 size_t FieldRef::appendParsedPart(StringData part) {
140 if (_size < kReserveAhead) {
141 _fixed[_size] = part;
142 } else {
143 _variable.push_back(part);
144 }
145 _size++;
146 _cachedSize++;
147 return _size;
148 }
149
reserialize() const150 void FieldRef::reserialize() const {
151 std::string nextDotted;
152 // Reserve some space in the string. We know we will have, at minimum, a character for
153 // each component we are writing, and a dot for each component, less one. We don't want
154 // to reserve more, since we don't want to forfeit the SSO if it is applicable.
155 nextDotted.reserve((_size > 0) ? (_size * 2) - 1 : 0);
156
157 // Concatenate the fields to a new string
158 for (size_t i = 0; i != _size; ++i) {
159 if (i > 0)
160 nextDotted.append(1, '.');
161 const StringData part = getPart(i);
162 nextDotted.append(part.rawData(), part.size());
163 }
164
165 // Make the new string our contents
166 _dotted.swap(nextDotted);
167
168 // Before we reserialize, it's possible that _cachedSize != _size because parts were added or
169 // removed. This reserialization process reconciles the components in our cached string
170 // (_dotted) with the modified path.
171 _cachedSize = _size;
172
173 // Fixup the parts to refer to the new string
174 std::string::const_iterator where = _dotted.begin();
175 const std::string::const_iterator end = _dotted.end();
176 for (size_t i = 0; i != _size; ++i) {
177 boost::optional<StringData>& part =
178 (i < kReserveAhead) ? _fixed[i] : _variable[getIndex(i)];
179 const size_t size = part ? part.get().size() : _replacements[i].size();
180
181 // There is one case where we expect to see the "where" iterator to be at "end" here: we
182 // are at the last part of the FieldRef and that part is the empty string. In that case, we
183 // need to make sure we do not dereference the "where" iterator.
184 dassert(where != end || (size == 0 && i == _size - 1));
185 part = StringData((size > 0) ? &*where : nullptr, size);
186 where += size;
187 // skip over '.' unless we are at the end.
188 if (where != end) {
189 dassert(*where == '.');
190 ++where;
191 }
192 }
193
194 // Drop any replacements
195 _replacements.clear();
196 }
197
getPart(size_t i) const198 StringData FieldRef::getPart(size_t i) const {
199 dassert(i < _size);
200
201 const boost::optional<StringData>& part =
202 (i < kReserveAhead) ? _fixed[i] : _variable[getIndex(i)];
203 if (part) {
204 return part.get();
205 } else {
206 return StringData(_replacements[i]);
207 }
208 }
209
isPrefixOf(const FieldRef & other) const210 bool FieldRef::isPrefixOf(const FieldRef& other) const {
211 // Can't be a prefix if the size is equal to or larger.
212 if (_size >= other._size) {
213 return false;
214 }
215
216 // Empty FieldRef is not a prefix of anything.
217 if (_size == 0) {
218 return false;
219 }
220
221 size_t common = commonPrefixSize(other);
222 return common == _size && other._size > common;
223 }
224
commonPrefixSize(const FieldRef & other) const225 size_t FieldRef::commonPrefixSize(const FieldRef& other) const {
226 if (_size == 0 || other._size == 0) {
227 return 0;
228 }
229
230 size_t maxPrefixSize = std::min(_size - 1, other._size - 1);
231 size_t prefixSize = 0;
232
233 while (prefixSize <= maxPrefixSize) {
234 if (getPart(prefixSize) != other.getPart(prefixSize)) {
235 break;
236 }
237 prefixSize++;
238 }
239
240 return prefixSize;
241 }
242
dottedField(size_t offset) const243 StringData FieldRef::dottedField(size_t offset) const {
244 return dottedSubstring(offset, numParts());
245 }
246
dottedSubstring(size_t startPart,size_t endPart) const247 StringData FieldRef::dottedSubstring(size_t startPart, size_t endPart) const {
248 if (_size == 0 || startPart >= endPart || endPart > numParts())
249 return StringData();
250
251 if (!_replacements.empty() || _size != _cachedSize)
252 reserialize();
253 dassert(_replacements.empty() && _size == _cachedSize);
254
255 StringData result(_dotted);
256
257 // Fast-path if we want the whole thing
258 if (startPart == 0 && endPart == numParts())
259 return result;
260
261 size_t startChar = 0;
262 for (size_t i = 0; i < startPart; ++i) {
263 startChar += getPart(i).size() + 1; // correct for '.'
264 }
265 size_t endChar = startChar;
266 for (size_t i = startPart; i < endPart; ++i) {
267 endChar += getPart(i).size() + 1;
268 }
269 // correct for last '.'
270 if (endPart != numParts())
271 --endChar;
272
273 return result.substr(startChar, endChar - startChar);
274 }
275
equalsDottedField(StringData other) const276 bool FieldRef::equalsDottedField(StringData other) const {
277 StringData rest = other;
278
279 for (size_t i = 0; i < _size; i++) {
280 StringData part = getPart(i);
281
282 if (!rest.startsWith(part))
283 return false;
284
285 if (i == _size - 1)
286 return rest.size() == part.size();
287
288 // make sure next thing is a dot
289 if (rest.size() == part.size())
290 return false;
291
292 if (rest[part.size()] != '.')
293 return false;
294
295 rest = rest.substr(part.size() + 1);
296 }
297
298 return false;
299 }
300
compare(const FieldRef & other) const301 int FieldRef::compare(const FieldRef& other) const {
302 const size_t toCompare = std::min(_size, other._size);
303 for (size_t i = 0; i < toCompare; i++) {
304 if (getPart(i) == other.getPart(i)) {
305 continue;
306 }
307 return getPart(i) < other.getPart(i) ? -1 : 1;
308 }
309
310 const size_t rest = _size - toCompare;
311 const size_t otherRest = other._size - toCompare;
312 if ((rest == 0) && (otherRest == 0)) {
313 return 0;
314 } else if (rest < otherRest) {
315 return -1;
316 } else {
317 return 1;
318 }
319 }
320
clear()321 void FieldRef::clear() {
322 _size = 0;
323 _cachedSize = 0;
324 _variable.clear();
325 _dotted.clear();
326 _replacements.clear();
327 }
328
operator <<(std::ostream & stream,const FieldRef & field)329 std::ostream& operator<<(std::ostream& stream, const FieldRef& field) {
330 return stream << field.dottedField();
331 }
332
333 } // namespace mongo
334