SkJSON.cpp 28 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702703704705706707708709710711712713714715716717718719720721722723724725726727728729730731732733734735736737738739740741742743744745746747748749750751752753754755756757758759760761762763764765766767768769770771772773774775776777778779780781782783784785786787788789790791792793794795796797798799800801802803804805806807808809810811812813814815816817818819820821822823824825826827828829830831832833834835836837838839840841842843844845846847848849850851852853854855856857858859860861862863864865866867868869870871872873874875876877878879880881882883884885886887888889890891892893894895896897898899900901902903904905906907908909910911912913914915916917
  1. /*
  2. * Copyright 2018 Google Inc.
  3. *
  4. * Use of this source code is governed by a BSD-style license that can be
  5. * found in the LICENSE file.
  6. */
  7. #include "src/utils/SkJSON.h"
  8. #include "include/core/SkStream.h"
  9. #include "include/core/SkString.h"
  10. #include "include/private/SkMalloc.h"
  11. #include "include/utils/SkParse.h"
  12. #include "src/utils/SkUTF.h"
  13. #include <cmath>
  14. #include <tuple>
  15. #include <vector>
  16. namespace skjson {
  17. // #define SK_JSON_REPORT_ERRORS
  18. static_assert( sizeof(Value) == 8, "");
  19. static_assert(alignof(Value) == 8, "");
  20. static constexpr size_t kRecAlign = alignof(Value);
  21. void Value::init_tagged(Tag t) {
  22. memset(fData8, 0, sizeof(fData8));
  23. fData8[Value::kTagOffset] = SkTo<uint8_t>(t);
  24. SkASSERT(this->getTag() == t);
  25. }
  26. // Pointer values store a type (in the upper kTagBits bits) and a pointer.
  27. void Value::init_tagged_pointer(Tag t, void* p) {
  28. *this->cast<uintptr_t>() = reinterpret_cast<uintptr_t>(p);
  29. if (sizeof(Value) == sizeof(uintptr_t)) {
  30. // For 64-bit, we rely on the pointer upper bits being unused/zero.
  31. SkASSERT(!(fData8[kTagOffset] & kTagMask));
  32. fData8[kTagOffset] |= SkTo<uint8_t>(t);
  33. } else {
  34. // For 32-bit, we need to zero-initialize the upper 32 bits
  35. SkASSERT(sizeof(Value) == sizeof(uintptr_t) * 2);
  36. this->cast<uintptr_t>()[kTagOffset >> 2] = 0;
  37. fData8[kTagOffset] = SkTo<uint8_t>(t);
  38. }
  39. SkASSERT(this->getTag() == t);
  40. SkASSERT(this->ptr<void>() == p);
  41. }
  42. NullValue::NullValue() {
  43. this->init_tagged(Tag::kNull);
  44. SkASSERT(this->getTag() == Tag::kNull);
  45. }
  46. BoolValue::BoolValue(bool b) {
  47. this->init_tagged(Tag::kBool);
  48. *this->cast<bool>() = b;
  49. SkASSERT(this->getTag() == Tag::kBool);
  50. }
  51. NumberValue::NumberValue(int32_t i) {
  52. this->init_tagged(Tag::kInt);
  53. *this->cast<int32_t>() = i;
  54. SkASSERT(this->getTag() == Tag::kInt);
  55. }
  56. NumberValue::NumberValue(float f) {
  57. this->init_tagged(Tag::kFloat);
  58. *this->cast<float>() = f;
  59. SkASSERT(this->getTag() == Tag::kFloat);
  60. }
  61. // Vector recs point to externally allocated slabs with the following layout:
  62. //
  63. // [size_t n] [REC_0] ... [REC_n-1] [optional extra trailing storage]
  64. //
  65. // Long strings use extra_alloc_size == 1 to store the \0 terminator.
  66. //
  67. template <typename T, size_t extra_alloc_size = 0>
  68. static void* MakeVector(const void* src, size_t size, SkArenaAlloc& alloc) {
  69. // The Ts are already in memory, so their size should be safe.
  70. const auto total_size = sizeof(size_t) + size * sizeof(T) + extra_alloc_size;
  71. auto* size_ptr = reinterpret_cast<size_t*>(alloc.makeBytesAlignedTo(total_size, kRecAlign));
  72. *size_ptr = size;
  73. sk_careful_memcpy(size_ptr + 1, src, size * sizeof(T));
  74. return size_ptr;
  75. }
  76. ArrayValue::ArrayValue(const Value* src, size_t size, SkArenaAlloc& alloc) {
  77. this->init_tagged_pointer(Tag::kArray, MakeVector<Value>(src, size, alloc));
  78. SkASSERT(this->getTag() == Tag::kArray);
  79. }
  80. // Strings have two flavors:
  81. //
  82. // -- short strings (len <= 7) -> these are stored inline, in the record
  83. // (one byte reserved for null terminator/type):
  84. //
  85. // [str] [\0]|[max_len - actual_len]
  86. //
  87. // Storing [max_len - actual_len] allows the 'len' field to double-up as a
  88. // null terminator when size == max_len (this works 'cause kShortString == 0).
  89. //
  90. // -- long strings (len > 7) -> these are externally allocated vectors (VectorRec<char>).
  91. //
  92. // The string data plus a null-char terminator are copied over.
  93. //
  94. namespace {
  95. // An internal string builder with a fast 8 byte short string load path
  96. // (for the common case where the string is not at the end of the stream).
  97. class FastString final : public Value {
  98. public:
  99. FastString(const char* src, size_t size, const char* eos, SkArenaAlloc& alloc) {
  100. SkASSERT(src <= eos);
  101. if (size > kMaxInlineStringSize) {
  102. this->initLongString(src, size, alloc);
  103. SkASSERT(this->getTag() == Tag::kString);
  104. return;
  105. }
  106. static_assert(static_cast<uint8_t>(Tag::kShortString) == 0, "please don't break this");
  107. static_assert(sizeof(Value) == 8, "");
  108. // TODO: LIKELY
  109. if (src + 7 <= eos) {
  110. this->initFastShortString(src, size);
  111. } else {
  112. this->initShortString(src, size);
  113. }
  114. SkASSERT(this->getTag() == Tag::kShortString);
  115. }
  116. private:
  117. static constexpr size_t kMaxInlineStringSize = sizeof(Value) - 1;
  118. void initLongString(const char* src, size_t size, SkArenaAlloc& alloc) {
  119. SkASSERT(size > kMaxInlineStringSize);
  120. this->init_tagged_pointer(Tag::kString, MakeVector<char, 1>(src, size, alloc));
  121. auto* data = this->cast<VectorValue<char, Value::Type::kString>>()->begin();
  122. const_cast<char*>(data)[size] = '\0';
  123. }
  124. void initShortString(const char* src, size_t size) {
  125. SkASSERT(size <= kMaxInlineStringSize);
  126. this->init_tagged(Tag::kShortString);
  127. sk_careful_memcpy(this->cast<char>(), src, size);
  128. // Null terminator provided by init_tagged() above (fData8 is zero-initialized).
  129. }
  130. void initFastShortString(const char* src, size_t size) {
  131. SkASSERT(size <= kMaxInlineStringSize);
  132. // Load 8 chars and mask out the tag and \0 terminator.
  133. uint64_t* s64 = this->cast<uint64_t>();
  134. memcpy(s64, src, 8);
  135. #if defined(SK_CPU_LENDIAN)
  136. *s64 &= 0x00ffffffffffffffULL >> ((kMaxInlineStringSize - size) * 8);
  137. #else
  138. static_assert(false, "Big-endian builds are not supported at this time.");
  139. #endif
  140. }
  141. };
  142. } // namespace
  143. StringValue::StringValue(const char* src, size_t size, SkArenaAlloc& alloc) {
  144. new (this) FastString(src, size, src, alloc);
  145. }
  146. ObjectValue::ObjectValue(const Member* src, size_t size, SkArenaAlloc& alloc) {
  147. this->init_tagged_pointer(Tag::kObject, MakeVector<Member>(src, size, alloc));
  148. SkASSERT(this->getTag() == Tag::kObject);
  149. }
  150. // Boring public Value glue.
  151. static int inline_strcmp(const char a[], const char b[]) {
  152. for (;;) {
  153. char c = *a++;
  154. if (c == 0) {
  155. break;
  156. }
  157. if (c != *b++) {
  158. return 1;
  159. }
  160. }
  161. return *b != 0;
  162. }
  163. const Value& ObjectValue::operator[](const char* key) const {
  164. // Reverse search for duplicates resolution (policy: return last).
  165. const auto* begin = this->begin();
  166. const auto* member = this->end();
  167. while (member > begin) {
  168. --member;
  169. if (0 == inline_strcmp(key, member->fKey.as<StringValue>().begin())) {
  170. return member->fValue;
  171. }
  172. }
  173. static const Value g_null = NullValue();
  174. return g_null;
  175. }
  176. namespace {
  177. // Lexer/parser inspired by rapidjson [1], sajson [2] and pjson [3].
  178. //
  179. // [1] https://github.com/Tencent/rapidjson/
  180. // [2] https://github.com/chadaustin/sajson
  181. // [3] https://pastebin.com/hnhSTL3h
  182. // bit 0 (0x01) - plain ASCII string character
  183. // bit 1 (0x02) - whitespace
  184. // bit 2 (0x04) - string terminator (" \\ \0 [control chars] **AND } ]** <- see matchString notes)
  185. // bit 3 (0x08) - 0-9
  186. // bit 4 (0x10) - 0-9 e E .
  187. // bit 5 (0x20) - scope terminator (} ])
  188. static constexpr uint8_t g_token_flags[256] = {
  189. // 0 1 2 3 4 5 6 7 8 9 A B C D E F
  190. 4, 4, 4, 4, 4, 4, 4, 4, 4, 6, 6, 4, 4, 6, 4, 4, // 0
  191. 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, // 1
  192. 3, 1, 4, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0x11,1, // 2
  193. 0x19,0x19,0x19,0x19,0x19,0x19,0x19,0x19, 0x19,0x19, 1, 1, 1, 1, 1, 1, // 3
  194. 1, 1, 1, 1, 1, 0x11,1, 1, 1, 1, 1, 1, 1, 1, 1, 1, // 4
  195. 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 4,0x25, 1, 1, // 5
  196. 1, 1, 1, 1, 1, 0x11,1, 1, 1, 1, 1, 1, 1, 1, 1, 1, // 6
  197. 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,0x25, 1, 1, // 7
  198. // 128-255
  199. 0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,0,
  200. 0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,0,
  201. 0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,0,
  202. 0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,0
  203. };
  204. static inline bool is_ws(char c) { return g_token_flags[static_cast<uint8_t>(c)] & 0x02; }
  205. static inline bool is_eostring(char c) { return g_token_flags[static_cast<uint8_t>(c)] & 0x04; }
  206. static inline bool is_digit(char c) { return g_token_flags[static_cast<uint8_t>(c)] & 0x08; }
  207. static inline bool is_numeric(char c) { return g_token_flags[static_cast<uint8_t>(c)] & 0x10; }
  208. static inline bool is_eoscope(char c) { return g_token_flags[static_cast<uint8_t>(c)] & 0x20; }
  209. static inline const char* skip_ws(const char* p) {
  210. while (is_ws(*p)) ++p;
  211. return p;
  212. }
  213. static inline float pow10(int32_t exp) {
  214. static constexpr float g_pow10_table[63] =
  215. {
  216. 1.e-031f, 1.e-030f, 1.e-029f, 1.e-028f, 1.e-027f, 1.e-026f, 1.e-025f, 1.e-024f,
  217. 1.e-023f, 1.e-022f, 1.e-021f, 1.e-020f, 1.e-019f, 1.e-018f, 1.e-017f, 1.e-016f,
  218. 1.e-015f, 1.e-014f, 1.e-013f, 1.e-012f, 1.e-011f, 1.e-010f, 1.e-009f, 1.e-008f,
  219. 1.e-007f, 1.e-006f, 1.e-005f, 1.e-004f, 1.e-003f, 1.e-002f, 1.e-001f, 1.e+000f,
  220. 1.e+001f, 1.e+002f, 1.e+003f, 1.e+004f, 1.e+005f, 1.e+006f, 1.e+007f, 1.e+008f,
  221. 1.e+009f, 1.e+010f, 1.e+011f, 1.e+012f, 1.e+013f, 1.e+014f, 1.e+015f, 1.e+016f,
  222. 1.e+017f, 1.e+018f, 1.e+019f, 1.e+020f, 1.e+021f, 1.e+022f, 1.e+023f, 1.e+024f,
  223. 1.e+025f, 1.e+026f, 1.e+027f, 1.e+028f, 1.e+029f, 1.e+030f, 1.e+031f
  224. };
  225. static constexpr int32_t k_exp_offset = SK_ARRAY_COUNT(g_pow10_table) / 2;
  226. // We only support negative exponents for now.
  227. SkASSERT(exp <= 0);
  228. return (exp >= -k_exp_offset) ? g_pow10_table[exp + k_exp_offset]
  229. : std::pow(10.0f, static_cast<float>(exp));
  230. }
  231. class DOMParser {
  232. public:
  233. explicit DOMParser(SkArenaAlloc& alloc)
  234. : fAlloc(alloc) {
  235. fValueStack.reserve(kValueStackReserve);
  236. fUnescapeBuffer.reserve(kUnescapeBufferReserve);
  237. }
  238. const Value parse(const char* p, size_t size) {
  239. if (!size) {
  240. return this->error(NullValue(), p, "invalid empty input");
  241. }
  242. const char* p_stop = p + size - 1;
  243. // We're only checking for end-of-stream on object/array close('}',']'),
  244. // so we must trim any whitespace from the buffer tail.
  245. while (p_stop > p && is_ws(*p_stop)) --p_stop;
  246. SkASSERT(p_stop >= p && p_stop < p + size);
  247. if (!is_eoscope(*p_stop)) {
  248. return this->error(NullValue(), p_stop, "invalid top-level value");
  249. }
  250. p = skip_ws(p);
  251. switch (*p) {
  252. case '{':
  253. goto match_object;
  254. case '[':
  255. goto match_array;
  256. default:
  257. return this->error(NullValue(), p, "invalid top-level value");
  258. }
  259. match_object:
  260. SkASSERT(*p == '{');
  261. p = skip_ws(p + 1);
  262. this->pushObjectScope();
  263. if (*p == '}') goto pop_object;
  264. // goto match_object_key;
  265. match_object_key:
  266. p = skip_ws(p);
  267. if (*p != '"') return this->error(NullValue(), p, "expected object key");
  268. p = this->matchString(p, p_stop, [this](const char* key, size_t size, const char* eos) {
  269. this->pushObjectKey(key, size, eos);
  270. });
  271. if (!p) return NullValue();
  272. p = skip_ws(p);
  273. if (*p != ':') return this->error(NullValue(), p, "expected ':' separator");
  274. ++p;
  275. // goto match_value;
  276. match_value:
  277. p = skip_ws(p);
  278. switch (*p) {
  279. case '\0':
  280. return this->error(NullValue(), p, "unexpected input end");
  281. case '"':
  282. p = this->matchString(p, p_stop, [this](const char* str, size_t size, const char* eos) {
  283. this->pushString(str, size, eos);
  284. });
  285. break;
  286. case '[':
  287. goto match_array;
  288. case 'f':
  289. p = this->matchFalse(p);
  290. break;
  291. case 'n':
  292. p = this->matchNull(p);
  293. break;
  294. case 't':
  295. p = this->matchTrue(p);
  296. break;
  297. case '{':
  298. goto match_object;
  299. default:
  300. p = this->matchNumber(p);
  301. break;
  302. }
  303. if (!p) return NullValue();
  304. // goto match_post_value;
  305. match_post_value:
  306. SkASSERT(!this->inTopLevelScope());
  307. p = skip_ws(p);
  308. switch (*p) {
  309. case ',':
  310. ++p;
  311. if (this->inObjectScope()) {
  312. goto match_object_key;
  313. } else {
  314. SkASSERT(this->inArrayScope());
  315. goto match_value;
  316. }
  317. case ']':
  318. goto pop_array;
  319. case '}':
  320. goto pop_object;
  321. default:
  322. return this->error(NullValue(), p - 1, "unexpected value-trailing token");
  323. }
  324. // unreachable
  325. SkASSERT(false);
  326. pop_object:
  327. SkASSERT(*p == '}');
  328. if (this->inArrayScope()) {
  329. return this->error(NullValue(), p, "unexpected object terminator");
  330. }
  331. this->popObjectScope();
  332. // goto pop_common
  333. pop_common:
  334. SkASSERT(is_eoscope(*p));
  335. if (this->inTopLevelScope()) {
  336. SkASSERT(fValueStack.size() == 1);
  337. // Success condition: parsed the top level element and reached the stop token.
  338. return p == p_stop
  339. ? fValueStack.front()
  340. : this->error(NullValue(), p + 1, "trailing root garbage");
  341. }
  342. if (p == p_stop) {
  343. return this->error(NullValue(), p, "unexpected end-of-input");
  344. }
  345. ++p;
  346. goto match_post_value;
  347. match_array:
  348. SkASSERT(*p == '[');
  349. p = skip_ws(p + 1);
  350. this->pushArrayScope();
  351. if (*p != ']') goto match_value;
  352. // goto pop_array;
  353. pop_array:
  354. SkASSERT(*p == ']');
  355. if (this->inObjectScope()) {
  356. return this->error(NullValue(), p, "unexpected array terminator");
  357. }
  358. this->popArrayScope();
  359. goto pop_common;
  360. SkASSERT(false);
  361. return NullValue();
  362. }
  363. std::tuple<const char*, const SkString> getError() const {
  364. return std::make_tuple(fErrorToken, fErrorMessage);
  365. }
  366. private:
  367. SkArenaAlloc& fAlloc;
  368. // Pending values stack.
  369. static constexpr size_t kValueStackReserve = 256;
  370. std::vector<Value> fValueStack;
  371. // String unescape buffer.
  372. static constexpr size_t kUnescapeBufferReserve = 512;
  373. std::vector<char> fUnescapeBuffer;
  374. // Tracks the current object/array scope, as an index into fStack:
  375. //
  376. // - for objects: fScopeIndex = (index of first value in scope)
  377. // - for arrays : fScopeIndex = -(index of first value in scope)
  378. //
  379. // fScopeIndex == 0 IFF we are at the top level (no current/active scope).
  380. intptr_t fScopeIndex = 0;
  381. // Error reporting.
  382. const char* fErrorToken = nullptr;
  383. SkString fErrorMessage;
  384. bool inTopLevelScope() const { return fScopeIndex == 0; }
  385. bool inObjectScope() const { return fScopeIndex > 0; }
  386. bool inArrayScope() const { return fScopeIndex < 0; }
  387. // Helper for masquerading raw primitive types as Values (bypassing tagging, etc).
  388. template <typename T>
  389. class RawValue final : public Value {
  390. public:
  391. explicit RawValue(T v) {
  392. static_assert(sizeof(T) <= sizeof(Value), "");
  393. *this->cast<T>() = v;
  394. }
  395. T operator *() const { return *this->cast<T>(); }
  396. };
  397. template <typename VectorT>
  398. void popScopeAsVec(size_t scope_start) {
  399. SkASSERT(scope_start > 0);
  400. SkASSERT(scope_start <= fValueStack.size());
  401. using T = typename VectorT::ValueT;
  402. static_assert( sizeof(T) >= sizeof(Value), "");
  403. static_assert( sizeof(T) % sizeof(Value) == 0, "");
  404. static_assert(alignof(T) == alignof(Value), "");
  405. const auto scope_count = fValueStack.size() - scope_start,
  406. count = scope_count / (sizeof(T) / sizeof(Value));
  407. SkASSERT(scope_count % (sizeof(T) / sizeof(Value)) == 0);
  408. const auto* begin = reinterpret_cast<const T*>(fValueStack.data() + scope_start);
  409. // Restore the previous scope index from saved placeholder value,
  410. // and instantiate as a vector of values in scope.
  411. auto& placeholder = fValueStack[scope_start - 1];
  412. fScopeIndex = *static_cast<RawValue<intptr_t>&>(placeholder);
  413. placeholder = VectorT(begin, count, fAlloc);
  414. // Drop the (consumed) values in scope.
  415. fValueStack.resize(scope_start);
  416. }
  417. void pushObjectScope() {
  418. // Save a scope index now, and then later we'll overwrite this value as the Object itself.
  419. fValueStack.push_back(RawValue<intptr_t>(fScopeIndex));
  420. // New object scope.
  421. fScopeIndex = SkTo<intptr_t>(fValueStack.size());
  422. }
  423. void popObjectScope() {
  424. SkASSERT(this->inObjectScope());
  425. this->popScopeAsVec<ObjectValue>(SkTo<size_t>(fScopeIndex));
  426. SkDEBUGCODE(
  427. const auto& obj = fValueStack.back().as<ObjectValue>();
  428. SkASSERT(obj.is<ObjectValue>());
  429. for (const auto& member : obj) {
  430. SkASSERT(member.fKey.is<StringValue>());
  431. }
  432. )
  433. }
  434. void pushArrayScope() {
  435. // Save a scope index now, and then later we'll overwrite this value as the Array itself.
  436. fValueStack.push_back(RawValue<intptr_t>(fScopeIndex));
  437. // New array scope.
  438. fScopeIndex = -SkTo<intptr_t>(fValueStack.size());
  439. }
  440. void popArrayScope() {
  441. SkASSERT(this->inArrayScope());
  442. this->popScopeAsVec<ArrayValue>(SkTo<size_t>(-fScopeIndex));
  443. SkDEBUGCODE(
  444. const auto& arr = fValueStack.back().as<ArrayValue>();
  445. SkASSERT(arr.is<ArrayValue>());
  446. )
  447. }
  448. void pushObjectKey(const char* key, size_t size, const char* eos) {
  449. SkASSERT(this->inObjectScope());
  450. SkASSERT(fValueStack.size() >= SkTo<size_t>(fScopeIndex));
  451. SkASSERT(!((fValueStack.size() - SkTo<size_t>(fScopeIndex)) & 1));
  452. this->pushString(key, size, eos);
  453. }
  454. void pushTrue() {
  455. fValueStack.push_back(BoolValue(true));
  456. }
  457. void pushFalse() {
  458. fValueStack.push_back(BoolValue(false));
  459. }
  460. void pushNull() {
  461. fValueStack.push_back(NullValue());
  462. }
  463. void pushString(const char* s, size_t size, const char* eos) {
  464. fValueStack.push_back(FastString(s, size, eos, fAlloc));
  465. }
  466. void pushInt32(int32_t i) {
  467. fValueStack.push_back(NumberValue(i));
  468. }
  469. void pushFloat(float f) {
  470. fValueStack.push_back(NumberValue(f));
  471. }
  472. template <typename T>
  473. T error(T&& ret_val, const char* p, const char* msg) {
  474. #if defined(SK_JSON_REPORT_ERRORS)
  475. fErrorToken = p;
  476. fErrorMessage.set(msg);
  477. #endif
  478. return ret_val;
  479. }
  480. const char* matchTrue(const char* p) {
  481. SkASSERT(p[0] == 't');
  482. if (p[1] == 'r' && p[2] == 'u' && p[3] == 'e') {
  483. this->pushTrue();
  484. return p + 4;
  485. }
  486. return this->error(nullptr, p, "invalid token");
  487. }
  488. const char* matchFalse(const char* p) {
  489. SkASSERT(p[0] == 'f');
  490. if (p[1] == 'a' && p[2] == 'l' && p[3] == 's' && p[4] == 'e') {
  491. this->pushFalse();
  492. return p + 5;
  493. }
  494. return this->error(nullptr, p, "invalid token");
  495. }
  496. const char* matchNull(const char* p) {
  497. SkASSERT(p[0] == 'n');
  498. if (p[1] == 'u' && p[2] == 'l' && p[3] == 'l') {
  499. this->pushNull();
  500. return p + 4;
  501. }
  502. return this->error(nullptr, p, "invalid token");
  503. }
  504. const std::vector<char>* unescapeString(const char* begin, const char* end) {
  505. fUnescapeBuffer.clear();
  506. for (const auto* p = begin; p != end; ++p) {
  507. if (*p != '\\') {
  508. fUnescapeBuffer.push_back(*p);
  509. continue;
  510. }
  511. if (++p == end) {
  512. return nullptr;
  513. }
  514. switch (*p) {
  515. case '"': fUnescapeBuffer.push_back( '"'); break;
  516. case '\\': fUnescapeBuffer.push_back('\\'); break;
  517. case '/': fUnescapeBuffer.push_back( '/'); break;
  518. case 'b': fUnescapeBuffer.push_back('\b'); break;
  519. case 'f': fUnescapeBuffer.push_back('\f'); break;
  520. case 'n': fUnescapeBuffer.push_back('\n'); break;
  521. case 'r': fUnescapeBuffer.push_back('\r'); break;
  522. case 't': fUnescapeBuffer.push_back('\t'); break;
  523. case 'u': {
  524. if (p + 4 >= end) {
  525. return nullptr;
  526. }
  527. uint32_t hexed;
  528. const char hex_str[] = {p[1], p[2], p[3], p[4], '\0'};
  529. const auto* eos = SkParse::FindHex(hex_str, &hexed);
  530. if (!eos || *eos) {
  531. return nullptr;
  532. }
  533. char utf8[SkUTF::kMaxBytesInUTF8Sequence];
  534. const auto utf8_len = SkUTF::ToUTF8(SkTo<SkUnichar>(hexed), utf8);
  535. fUnescapeBuffer.insert(fUnescapeBuffer.end(), utf8, utf8 + utf8_len);
  536. p += 4;
  537. } break;
  538. default: return nullptr;
  539. }
  540. }
  541. return &fUnescapeBuffer;
  542. }
  543. template <typename MatchFunc>
  544. const char* matchString(const char* p, const char* p_stop, MatchFunc&& func) {
  545. SkASSERT(*p == '"');
  546. const auto* s_begin = p + 1;
  547. bool requires_unescape = false;
  548. do {
  549. // Consume string chars.
  550. // This is the fast path, and hopefully we only hit it once then quick-exit below.
  551. for (p = p + 1; !is_eostring(*p); ++p);
  552. if (*p == '"') {
  553. // Valid string found.
  554. if (!requires_unescape) {
  555. func(s_begin, p - s_begin, p_stop);
  556. } else {
  557. // Slow unescape. We could avoid this extra copy with some effort,
  558. // but in practice escaped strings should be rare.
  559. const auto* buf = this->unescapeString(s_begin, p);
  560. if (!buf) {
  561. break;
  562. }
  563. SkASSERT(!buf->empty());
  564. func(buf->data(), buf->size(), buf->data() + buf->size() - 1);
  565. }
  566. return p + 1;
  567. }
  568. if (*p == '\\') {
  569. requires_unescape = true;
  570. ++p;
  571. continue;
  572. }
  573. // End-of-scope chars are special: we use them to tag the end of the input.
  574. // Thus they cannot be consumed indiscriminately -- we need to check if we hit the
  575. // end of the input. To that effect, we treat them as string terminators above,
  576. // then we catch them here.
  577. if (is_eoscope(*p)) {
  578. continue;
  579. }
  580. // Invalid/unexpected char.
  581. break;
  582. } while (p != p_stop);
  583. // Premature end-of-input, or illegal string char.
  584. return this->error(nullptr, s_begin - 1, "invalid string");
  585. }
  586. const char* matchFastFloatDecimalPart(const char* p, int sign, float f, int exp) {
  587. SkASSERT(exp <= 0);
  588. for (;;) {
  589. if (!is_digit(*p)) break;
  590. f = f * 10.f + (*p++ - '0'); --exp;
  591. if (!is_digit(*p)) break;
  592. f = f * 10.f + (*p++ - '0'); --exp;
  593. }
  594. const auto decimal_scale = pow10(exp);
  595. if (is_numeric(*p) || !decimal_scale) {
  596. SkASSERT((*p == '.' || *p == 'e' || *p == 'E') || !decimal_scale);
  597. // Malformed input, or an (unsupported) exponent, or a collapsed decimal factor.
  598. return nullptr;
  599. }
  600. this->pushFloat(sign * f * decimal_scale);
  601. return p;
  602. }
  603. const char* matchFastFloatPart(const char* p, int sign, float f) {
  604. for (;;) {
  605. if (!is_digit(*p)) break;
  606. f = f * 10.f + (*p++ - '0');
  607. if (!is_digit(*p)) break;
  608. f = f * 10.f + (*p++ - '0');
  609. }
  610. if (!is_numeric(*p)) {
  611. // Matched (integral) float.
  612. this->pushFloat(sign * f);
  613. return p;
  614. }
  615. return (*p == '.') ? this->matchFastFloatDecimalPart(p + 1, sign, f, 0)
  616. : nullptr;
  617. }
  618. const char* matchFast32OrFloat(const char* p) {
  619. int sign = 1;
  620. if (*p == '-') {
  621. sign = -1;
  622. ++p;
  623. }
  624. const auto* digits_start = p;
  625. int32_t n32 = 0;
  626. // This is the largest absolute int32 value we can handle before
  627. // risking overflow *on the next digit* (214748363).
  628. static constexpr int32_t kMaxInt32 = (std::numeric_limits<int32_t>::max() - 9) / 10;
  629. if (is_digit(*p)) {
  630. n32 = (*p++ - '0');
  631. for (;;) {
  632. if (!is_digit(*p) || n32 > kMaxInt32) break;
  633. n32 = n32 * 10 + (*p++ - '0');
  634. }
  635. }
  636. if (!is_numeric(*p)) {
  637. // Did we actually match any digits?
  638. if (p > digits_start) {
  639. this->pushInt32(sign * n32);
  640. return p;
  641. }
  642. return nullptr;
  643. }
  644. if (*p == '.') {
  645. const auto* decimals_start = ++p;
  646. int exp = 0;
  647. for (;;) {
  648. if (!is_digit(*p) || n32 > kMaxInt32) break;
  649. n32 = n32 * 10 + (*p++ - '0'); --exp;
  650. if (!is_digit(*p) || n32 > kMaxInt32) break;
  651. n32 = n32 * 10 + (*p++ - '0'); --exp;
  652. }
  653. if (!is_numeric(*p)) {
  654. // Did we actually match any digits?
  655. if (p > decimals_start) {
  656. this->pushFloat(sign * n32 * pow10(exp));
  657. return p;
  658. }
  659. return nullptr;
  660. }
  661. if (n32 > kMaxInt32) {
  662. // we ran out on n32 bits
  663. return this->matchFastFloatDecimalPart(p, sign, n32, exp);
  664. }
  665. }
  666. return this->matchFastFloatPart(p, sign, n32);
  667. }
  668. const char* matchNumber(const char* p) {
  669. if (const auto* fast = this->matchFast32OrFloat(p)) return fast;
  670. // slow fallback
  671. char* matched;
  672. float f = strtof(p, &matched);
  673. if (matched > p) {
  674. this->pushFloat(f);
  675. return matched;
  676. }
  677. return this->error(nullptr, p, "invalid numeric token");
  678. }
  679. };
  680. void Write(const Value& v, SkWStream* stream) {
  681. switch (v.getType()) {
  682. case Value::Type::kNull:
  683. stream->writeText("null");
  684. break;
  685. case Value::Type::kBool:
  686. stream->writeText(*v.as<BoolValue>() ? "true" : "false");
  687. break;
  688. case Value::Type::kNumber:
  689. stream->writeScalarAsText(*v.as<NumberValue>());
  690. break;
  691. case Value::Type::kString:
  692. stream->writeText("\"");
  693. stream->writeText(v.as<StringValue>().begin());
  694. stream->writeText("\"");
  695. break;
  696. case Value::Type::kArray: {
  697. const auto& array = v.as<ArrayValue>();
  698. stream->writeText("[");
  699. bool first_value = true;
  700. for (const auto& v : array) {
  701. if (!first_value) stream->writeText(",");
  702. Write(v, stream);
  703. first_value = false;
  704. }
  705. stream->writeText("]");
  706. break;
  707. }
  708. case Value::Type::kObject:
  709. const auto& object = v.as<ObjectValue>();
  710. stream->writeText("{");
  711. bool first_member = true;
  712. for (const auto& member : object) {
  713. SkASSERT(member.fKey.getType() == Value::Type::kString);
  714. if (!first_member) stream->writeText(",");
  715. Write(member.fKey, stream);
  716. stream->writeText(":");
  717. Write(member.fValue, stream);
  718. first_member = false;
  719. }
  720. stream->writeText("}");
  721. break;
  722. }
  723. }
  724. } // namespace
  725. SkString Value::toString() const {
  726. SkDynamicMemoryWStream wstream;
  727. Write(*this, &wstream);
  728. const auto data = wstream.detachAsData();
  729. // TODO: is there a better way to pass data around without copying?
  730. return SkString(static_cast<const char*>(data->data()), data->size());
  731. }
  732. static constexpr size_t kMinChunkSize = 4096;
  733. DOM::DOM(const char* data, size_t size)
  734. : fAlloc(kMinChunkSize) {
  735. DOMParser parser(fAlloc);
  736. fRoot = parser.parse(data, size);
  737. }
  738. void DOM::write(SkWStream* stream) const {
  739. Write(fRoot, stream);
  740. }
  741. } // namespace skjson