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