1 | /* |
2 | * Copyright (c) Facebook, Inc. and its affiliates. |
3 | * |
4 | * Licensed under the Apache License, Version 2.0 (the "License"); |
5 | * you may not use this file except in compliance with the License. |
6 | * You may obtain a copy of the License at |
7 | * |
8 | * http://www.apache.org/licenses/LICENSE-2.0 |
9 | * |
10 | * Unless required by applicable law or agreed to in writing, software |
11 | * distributed under the License is distributed on an "AS IS" BASIS, |
12 | * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. |
13 | * See the License for the specific language governing permissions and |
14 | * limitations under the License. |
15 | */ |
16 | |
17 | #include <folly/dynamic.h> |
18 | |
19 | #include <numeric> |
20 | |
21 | #include <glog/logging.h> |
22 | |
23 | #include <folly/Format.h> |
24 | #include <folly/container/Enumerate.h> |
25 | #include <folly/hash/Hash.h> |
26 | #include <folly/lang/Assume.h> |
27 | #include <folly/lang/Exception.h> |
28 | |
29 | namespace folly { |
30 | |
31 | ////////////////////////////////////////////////////////////////////// |
32 | |
33 | #define FOLLY_DYNAMIC_DEF_TYPEINFO(T) \ |
34 | constexpr const char* dynamic::TypeInfo<T>::name; \ |
35 | constexpr dynamic::Type dynamic::TypeInfo<T>::type; \ |
36 | // |
37 | |
38 | FOLLY_DYNAMIC_DEF_TYPEINFO(std::nullptr_t) |
39 | FOLLY_DYNAMIC_DEF_TYPEINFO(bool) |
40 | FOLLY_DYNAMIC_DEF_TYPEINFO(std::string) |
41 | FOLLY_DYNAMIC_DEF_TYPEINFO(dynamic::Array) |
42 | FOLLY_DYNAMIC_DEF_TYPEINFO(double) |
43 | FOLLY_DYNAMIC_DEF_TYPEINFO(int64_t) |
44 | FOLLY_DYNAMIC_DEF_TYPEINFO(dynamic::ObjectImpl) |
45 | |
46 | #undef FOLLY_DYNAMIC_DEF_TYPEINFO |
47 | |
48 | const char* dynamic::typeName() const { |
49 | return typeName(type_); |
50 | } |
51 | |
52 | TypeError::TypeError(const std::string& expected, dynamic::Type actual) |
53 | : std::runtime_error(sformat( |
54 | "TypeError: expected dynamic type `{}', but had type `{}'" , |
55 | expected, |
56 | dynamic::typeName(actual))) {} |
57 | |
58 | TypeError::TypeError( |
59 | const std::string& expected, |
60 | dynamic::Type actual1, |
61 | dynamic::Type actual2) |
62 | : std::runtime_error(sformat( |
63 | "TypeError: expected dynamic types `{}, but had types `{}' and `{}'" , |
64 | expected, |
65 | dynamic::typeName(actual1), |
66 | dynamic::typeName(actual2))) {} |
67 | |
68 | // This is a higher-order preprocessor macro to aid going from runtime |
69 | // types to the compile time type system. |
70 | #define FB_DYNAMIC_APPLY(type, apply) \ |
71 | do { \ |
72 | switch ((type)) { \ |
73 | case NULLT: \ |
74 | apply(std::nullptr_t); \ |
75 | break; \ |
76 | case ARRAY: \ |
77 | apply(Array); \ |
78 | break; \ |
79 | case BOOL: \ |
80 | apply(bool); \ |
81 | break; \ |
82 | case DOUBLE: \ |
83 | apply(double); \ |
84 | break; \ |
85 | case INT64: \ |
86 | apply(int64_t); \ |
87 | break; \ |
88 | case OBJECT: \ |
89 | apply(ObjectImpl); \ |
90 | break; \ |
91 | case STRING: \ |
92 | apply(std::string); \ |
93 | break; \ |
94 | default: \ |
95 | CHECK(0); \ |
96 | abort(); \ |
97 | } \ |
98 | } while (0) |
99 | |
100 | bool dynamic::operator<(dynamic const& o) const { |
101 | if (UNLIKELY(type_ == OBJECT || o.type_ == OBJECT)) { |
102 | throw_exception<TypeError>("object" , type_); |
103 | } |
104 | if (type_ != o.type_) { |
105 | return type_ < o.type_; |
106 | } |
107 | |
108 | #define FB_X(T) return CompareOp<T>::comp(*getAddress<T>(), *o.getAddress<T>()) |
109 | FB_DYNAMIC_APPLY(type_, FB_X); |
110 | #undef FB_X |
111 | } |
112 | |
113 | bool dynamic::operator==(dynamic const& o) const { |
114 | if (type() != o.type()) { |
115 | if (isNumber() && o.isNumber()) { |
116 | auto& integ = isInt() ? *this : o; |
117 | auto& doubl = isInt() ? o : *this; |
118 | return integ.asInt() == doubl.asDouble(); |
119 | } |
120 | return false; |
121 | } |
122 | |
123 | #define FB_X(T) return *getAddress<T>() == *o.getAddress<T>(); |
124 | FB_DYNAMIC_APPLY(type_, FB_X); |
125 | #undef FB_X |
126 | } |
127 | |
128 | dynamic& dynamic::operator=(dynamic const& o) { |
129 | if (&o != this) { |
130 | if (type_ == o.type_) { |
131 | #define FB_X(T) *getAddress<T>() = *o.getAddress<T>() |
132 | FB_DYNAMIC_APPLY(type_, FB_X); |
133 | #undef FB_X |
134 | } else { |
135 | destroy(); |
136 | #define FB_X(T) new (getAddress<T>()) T(*o.getAddress<T>()) |
137 | FB_DYNAMIC_APPLY(o.type_, FB_X); |
138 | #undef FB_X |
139 | type_ = o.type_; |
140 | } |
141 | } |
142 | return *this; |
143 | } |
144 | |
145 | dynamic& dynamic::operator=(dynamic&& o) noexcept { |
146 | if (&o != this) { |
147 | if (type_ == o.type_) { |
148 | #define FB_X(T) *getAddress<T>() = std::move(*o.getAddress<T>()) |
149 | FB_DYNAMIC_APPLY(type_, FB_X); |
150 | #undef FB_X |
151 | } else { |
152 | destroy(); |
153 | #define FB_X(T) new (getAddress<T>()) T(std::move(*o.getAddress<T>())) |
154 | FB_DYNAMIC_APPLY(o.type_, FB_X); |
155 | #undef FB_X |
156 | type_ = o.type_; |
157 | } |
158 | } |
159 | return *this; |
160 | } |
161 | |
162 | dynamic const& dynamic::atImpl(dynamic const& idx) const& { |
163 | if (auto* parray = get_nothrow<Array>()) { |
164 | if (!idx.isInt()) { |
165 | throw_exception<TypeError>("int64" , idx.type()); |
166 | } |
167 | if (idx < 0 || idx >= parray->size()) { |
168 | throw_exception<std::out_of_range>("out of range in dynamic array" ); |
169 | } |
170 | return (*parray)[size_t(idx.asInt())]; |
171 | } else if (auto* pobject = get_nothrow<ObjectImpl>()) { |
172 | auto it = pobject->find(idx); |
173 | if (it == pobject->end()) { |
174 | throw_exception<std::out_of_range>( |
175 | sformat("couldn't find key {} in dynamic object" , idx.asString())); |
176 | } |
177 | return it->second; |
178 | } else { |
179 | throw_exception<TypeError>("object/array" , type()); |
180 | } |
181 | } |
182 | |
183 | dynamic const& dynamic::at(StringPiece idx) const& { |
184 | auto* pobject = get_nothrow<ObjectImpl>(); |
185 | if (!pobject) { |
186 | throw_exception<TypeError>("object" , type()); |
187 | } |
188 | auto it = pobject->find(idx); |
189 | if (it == pobject->end()) { |
190 | throw_exception<std::out_of_range>( |
191 | sformat("couldn't find key {} in dynamic object" , idx)); |
192 | } |
193 | return it->second; |
194 | } |
195 | |
196 | dynamic& dynamic::operator[](StringPiece k) & { |
197 | auto& obj = get<ObjectImpl>(); |
198 | auto ret = obj.emplace(k, nullptr); |
199 | return ret.first->second; |
200 | } |
201 | |
202 | dynamic dynamic::getDefault(StringPiece k, const dynamic& v) const& { |
203 | auto& obj = get<ObjectImpl>(); |
204 | auto it = obj.find(k); |
205 | return it == obj.end() ? v : it->second; |
206 | } |
207 | |
208 | dynamic dynamic::getDefault(StringPiece k, dynamic&& v) const& { |
209 | auto& obj = get<ObjectImpl>(); |
210 | auto it = obj.find(k); |
211 | // Avoid clang bug with ternary |
212 | if (it == obj.end()) { |
213 | return std::move(v); |
214 | } else { |
215 | return it->second; |
216 | } |
217 | } |
218 | |
219 | dynamic dynamic::getDefault(StringPiece k, const dynamic& v) && { |
220 | auto& obj = get<ObjectImpl>(); |
221 | auto it = obj.find(k); |
222 | // Avoid clang bug with ternary |
223 | if (it == obj.end()) { |
224 | return v; |
225 | } else { |
226 | return std::move(it->second); |
227 | } |
228 | } |
229 | |
230 | dynamic dynamic::getDefault(StringPiece k, dynamic&& v) && { |
231 | auto& obj = get<ObjectImpl>(); |
232 | auto it = obj.find(k); |
233 | return std::move(it == obj.end() ? v : it->second); |
234 | } |
235 | |
236 | const dynamic* dynamic::get_ptrImpl(dynamic const& idx) const& { |
237 | if (auto* parray = get_nothrow<Array>()) { |
238 | if (!idx.isInt()) { |
239 | throw_exception<TypeError>("int64" , idx.type()); |
240 | } |
241 | if (idx < 0 || idx >= parray->size()) { |
242 | return nullptr; |
243 | } |
244 | return &(*parray)[size_t(idx.asInt())]; |
245 | } else if (auto* pobject = get_nothrow<ObjectImpl>()) { |
246 | auto it = pobject->find(idx); |
247 | if (it == pobject->end()) { |
248 | return nullptr; |
249 | } |
250 | return &it->second; |
251 | } else { |
252 | throw_exception<TypeError>("object/array" , type()); |
253 | } |
254 | } |
255 | |
256 | const dynamic* dynamic::get_ptr(StringPiece idx) const& { |
257 | auto* pobject = get_nothrow<ObjectImpl>(); |
258 | if (!pobject) { |
259 | throw_exception<TypeError>("object" , type()); |
260 | } |
261 | auto it = pobject->find(idx); |
262 | if (it == pobject->end()) { |
263 | return nullptr; |
264 | } |
265 | return &it->second; |
266 | } |
267 | |
268 | std::size_t dynamic::size() const { |
269 | if (auto* ar = get_nothrow<Array>()) { |
270 | return ar->size(); |
271 | } |
272 | if (auto* obj = get_nothrow<ObjectImpl>()) { |
273 | return obj->size(); |
274 | } |
275 | if (auto* str = get_nothrow<std::string>()) { |
276 | return str->size(); |
277 | } |
278 | throw_exception<TypeError>("array/object/string" , type()); |
279 | } |
280 | |
281 | dynamic::iterator dynamic::erase(const_iterator first, const_iterator last) { |
282 | auto& arr = get<Array>(); |
283 | return get<Array>().erase( |
284 | arr.begin() + (first - arr.begin()), arr.begin() + (last - arr.begin())); |
285 | } |
286 | |
287 | std::size_t dynamic::hash() const { |
288 | switch (type()) { |
289 | case NULLT: |
290 | return 0xBAAAAAAD; |
291 | case OBJECT: { |
292 | // Accumulate using addition instead of using hash_range (as in the ARRAY |
293 | // case), as we need a commutative hash operation since unordered_map's |
294 | // iteration order is unspecified. |
295 | auto h = std::hash<std::pair<dynamic const, dynamic>>{}; |
296 | return std::accumulate( |
297 | items().begin(), |
298 | items().end(), |
299 | size_t{0x0B1EC7}, |
300 | [&](auto acc, auto const& item) { return acc + h(item); }); |
301 | } |
302 | case ARRAY: |
303 | return folly::hash::hash_range(begin(), end()); |
304 | case INT64: |
305 | return std::hash<int64_t>()(getInt()); |
306 | case DOUBLE: |
307 | return std::hash<double>()(getDouble()); |
308 | case BOOL: |
309 | return std::hash<bool>()(getBool()); |
310 | case STRING: |
311 | // keep consistent with detail::DynamicHasher |
312 | return Hash()(getString()); |
313 | } |
314 | assume_unreachable(); |
315 | } |
316 | |
317 | char const* dynamic::typeName(Type t) { |
318 | #define FB_X(T) return TypeInfo<T>::name |
319 | FB_DYNAMIC_APPLY(t, FB_X); |
320 | #undef FB_X |
321 | } |
322 | |
323 | void dynamic::destroy() noexcept { |
324 | // This short-circuit speeds up some microbenchmarks. |
325 | if (type_ == NULLT) { |
326 | return; |
327 | } |
328 | |
329 | #define FB_X(T) detail::Destroy::destroy(getAddress<T>()) |
330 | FB_DYNAMIC_APPLY(type_, FB_X); |
331 | #undef FB_X |
332 | type_ = NULLT; |
333 | u_.nul = nullptr; |
334 | } |
335 | |
336 | dynamic dynamic::merge_diff(const dynamic& source, const dynamic& target) { |
337 | if (!source.isObject() || source.type() != target.type()) { |
338 | return target; |
339 | } |
340 | |
341 | dynamic diff = object; |
342 | |
343 | // added/modified keys |
344 | for (const auto& pair : target.items()) { |
345 | auto it = source.find(pair.first); |
346 | if (it == source.items().end()) { |
347 | diff[pair.first] = pair.second; |
348 | } else { |
349 | diff[pair.first] = merge_diff(source[pair.first], target[pair.first]); |
350 | } |
351 | } |
352 | |
353 | // removed keys |
354 | for (const auto& pair : source.items()) { |
355 | auto it = target.find(pair.first); |
356 | if (it == target.items().end()) { |
357 | diff[pair.first] = nullptr; |
358 | } |
359 | } |
360 | |
361 | return diff; |
362 | } |
363 | |
364 | // clang-format off |
365 | dynamic::resolved_json_pointer<dynamic const> |
366 | // clang-format on |
367 | dynamic::try_get_ptr(json_pointer const& jsonPtr) const& { |
368 | using err_code = json_pointer_resolution_error_code; |
369 | using error = json_pointer_resolution_error<dynamic const>; |
370 | |
371 | auto const& tokens = jsonPtr.tokens(); |
372 | if (tokens.empty()) { |
373 | return json_pointer_resolved_value<dynamic const>{ |
374 | nullptr, this, {nullptr, nullptr}, 0}; |
375 | } |
376 | |
377 | dynamic const* curr = this; |
378 | dynamic const* prev = nullptr; |
379 | |
380 | size_t curr_idx{0}; |
381 | StringPiece curr_key{}; |
382 | |
383 | for (auto it : enumerate(tokens)) { |
384 | // hit bottom but pointer not exhausted yet |
385 | if (!curr) { |
386 | return makeUnexpected( |
387 | error{err_code::json_pointer_out_of_bounds, it.index, prev}); |
388 | } |
389 | prev = curr; |
390 | // handle lookup in array |
391 | if (auto const* parray = curr->get_nothrow<dynamic::Array>()) { |
392 | if (it->size() > 1 && it->at(0) == '0') { |
393 | return makeUnexpected( |
394 | error{err_code::index_has_leading_zero, it.index, prev}); |
395 | } |
396 | // if last element of pointer is '-', this is an append operation |
397 | if (it->size() == 1 && it->at(0) == '-') { |
398 | // was '-' the last token in pointer? |
399 | if (it.index == tokens.size() - 1) { |
400 | return makeUnexpected( |
401 | error{err_code::append_requested, it.index, prev}); |
402 | } |
403 | // Cannot resolve past '-' in an array |
404 | curr = nullptr; |
405 | continue; |
406 | } |
407 | auto const idx = tryTo<size_t>(*it); |
408 | if (!idx.hasValue()) { |
409 | return makeUnexpected( |
410 | error{err_code::index_not_numeric, it.index, prev}); |
411 | } |
412 | if (idx.value() < parray->size()) { |
413 | curr = &(*parray)[idx.value()]; |
414 | curr_idx = idx.value(); |
415 | } else { |
416 | return makeUnexpected( |
417 | error{err_code::index_out_of_bounds, it.index, prev}); |
418 | } |
419 | continue; |
420 | } |
421 | // handle lookup in object |
422 | if (auto const* pobject = curr->get_nothrow<dynamic::ObjectImpl>()) { |
423 | auto const sub_it = pobject->find(*it); |
424 | if (sub_it == pobject->end()) { |
425 | return makeUnexpected(error{err_code::key_not_found, it.index, prev}); |
426 | } |
427 | curr = &sub_it->second; |
428 | curr_key = *it; |
429 | continue; |
430 | } |
431 | return makeUnexpected( |
432 | error{err_code::element_not_object_or_array, it.index, prev}); |
433 | } |
434 | return json_pointer_resolved_value<dynamic const>{ |
435 | prev, curr, curr_key, curr_idx}; |
436 | } |
437 | |
438 | const dynamic* dynamic::get_ptr(json_pointer const& jsonPtr) const& { |
439 | using err_code = json_pointer_resolution_error_code; |
440 | |
441 | auto ret = try_get_ptr(jsonPtr); |
442 | if (ret.hasValue()) { |
443 | return ret.value().value; |
444 | } |
445 | |
446 | auto const ctx = ret.error().context; |
447 | auto const objType = ctx ? ctx->type() : Type::NULLT; |
448 | |
449 | switch (ret.error().error_code) { |
450 | case err_code::key_not_found: |
451 | return nullptr; |
452 | case err_code::index_out_of_bounds: |
453 | return nullptr; |
454 | case err_code::append_requested: |
455 | return nullptr; |
456 | case err_code::index_not_numeric: |
457 | throw std::invalid_argument("array index is not numeric" ); |
458 | case err_code::index_has_leading_zero: |
459 | throw std::invalid_argument( |
460 | "leading zero not allowed when indexing arrays" ); |
461 | case err_code::element_not_object_or_array: |
462 | throw_exception<TypeError>("object/array" , objType); |
463 | case err_code::json_pointer_out_of_bounds: |
464 | return nullptr; |
465 | case err_code::other: |
466 | default: |
467 | return nullptr; |
468 | } |
469 | assume_unreachable(); |
470 | } |
471 | |
472 | ////////////////////////////////////////////////////////////////////// |
473 | |
474 | } // namespace folly |
475 | |