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
29namespace 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
38FOLLY_DYNAMIC_DEF_TYPEINFO(std::nullptr_t)
39FOLLY_DYNAMIC_DEF_TYPEINFO(bool)
40FOLLY_DYNAMIC_DEF_TYPEINFO(std::string)
41FOLLY_DYNAMIC_DEF_TYPEINFO(dynamic::Array)
42FOLLY_DYNAMIC_DEF_TYPEINFO(double)
43FOLLY_DYNAMIC_DEF_TYPEINFO(int64_t)
44FOLLY_DYNAMIC_DEF_TYPEINFO(dynamic::ObjectImpl)
45
46#undef FOLLY_DYNAMIC_DEF_TYPEINFO
47
48const char* dynamic::typeName() const {
49 return typeName(type_);
50}
51
52TypeError::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
58TypeError::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
100bool 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
113bool 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
128dynamic& 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
145dynamic& 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
162dynamic 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
183dynamic 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
196dynamic& dynamic::operator[](StringPiece k) & {
197 auto& obj = get<ObjectImpl>();
198 auto ret = obj.emplace(k, nullptr);
199 return ret.first->second;
200}
201
202dynamic 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
208dynamic 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
219dynamic 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
230dynamic 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
236const 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
256const 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
268std::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
281dynamic::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
287std::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
317char 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
323void 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
336dynamic 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
365dynamic::resolved_json_pointer<dynamic const>
366// clang-format on
367dynamic::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
438const 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