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
27namespace 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
36FOLLY_DYNAMIC_DEF_TYPEINFO(std::nullptr_t)
37FOLLY_DYNAMIC_DEF_TYPEINFO(bool)
38FOLLY_DYNAMIC_DEF_TYPEINFO(std::string)
39FOLLY_DYNAMIC_DEF_TYPEINFO(dynamic::Array)
40FOLLY_DYNAMIC_DEF_TYPEINFO(double)
41FOLLY_DYNAMIC_DEF_TYPEINFO(int64_t)
42FOLLY_DYNAMIC_DEF_TYPEINFO(dynamic::ObjectImpl)
43
44#undef FOLLY_DYNAMIC_DEF_TYPEINFO
45
46const char* dynamic::typeName() const {
47 return typeName(type_);
48}
49
50TypeError::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
56TypeError::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
66TypeError::TypeError(const TypeError&) noexcept(
67 std::is_nothrow_copy_constructible<std::runtime_error>::value) = default;
68TypeError& TypeError::operator=(const TypeError&) noexcept(
69 std::is_nothrow_copy_assignable<std::runtime_error>::value) = default;
70TypeError::TypeError(TypeError&&) noexcept(
71 std::is_nothrow_move_constructible<std::runtime_error>::value) = default;
72TypeError& TypeError::operator=(TypeError&&) noexcept(
73 std::is_nothrow_move_assignable<std::runtime_error>::value) = default;
74TypeError::~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
108bool 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
121bool 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
136dynamic& 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
153dynamic& 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
170dynamic 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
191dynamic 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
204dynamic& dynamic::operator[](StringPiece k) & {
205 auto& obj = get<ObjectImpl>();
206 auto ret = obj.emplace(k, nullptr);
207 return ret.first->second;
208}
209
210dynamic 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
216dynamic 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
227dynamic 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
238dynamic 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
244const 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
264const 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
276std::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
289dynamic::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
295std::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
325char 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
331void 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
344dynamic 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
373dynamic::resolved_json_pointer<dynamic const>
374// clang-format on
375dynamic::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
446const 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