Branch data Line data Source code
1 : : // Copyright 2014 BitPay Inc.
2 : : // Distributed under the MIT software license, see the accompanying
3 : : // file COPYING or https://opensource.org/licenses/mit-license.php.
4 : :
5 : : #include <univalue.h>
6 : : #include <univalue_utffilter.h>
7 : :
8 : : #include <cstdint>
9 : : #include <cstdio>
10 : : #include <cstring>
11 : : #include <string>
12 : : #include <string_view>
13 : : #include <vector>
14 : :
15 : : /*
16 : : * According to stackexchange, the original json test suite wanted
17 : : * to limit depth to 22. Widely-deployed PHP bails at depth 512,
18 : : * so we will follow PHP's lead, which should be more than sufficient
19 : : * (further stackexchange comments indicate depth > 32 rarely occurs).
20 : : */
21 : : static constexpr size_t MAX_JSON_DEPTH = 512;
22 : :
23 : 45832669 : static bool json_isdigit(int ch)
24 : : {
25 [ + + ]: 45832669 : return ((ch >= '0') && (ch <= '9'));
26 : : }
27 : :
28 : : // convert hexadecimal string to unsigned integer
29 : 38349 : static const char *hatoui(const char *first, const char *last,
30 : : unsigned int& out)
31 : : {
32 : 38349 : unsigned int result = 0;
33 [ + + ]: 191283 : for (; first != last; ++first)
34 : : {
35 : 153121 : int digit;
36 [ + + ]: 153121 : if (json_isdigit(*first))
37 : 92094 : digit = *first - '0';
38 : :
39 [ + + + + ]: 61027 : else if (*first >= 'a' && *first <= 'f')
40 : 27072 : digit = *first - 'a' + 10;
41 : :
42 [ + + + + ]: 33955 : else if (*first >= 'A' && *first <= 'F')
43 : 33768 : digit = *first - 'A' + 10;
44 : :
45 : : else
46 : 187 : break;
47 : :
48 : 152934 : result = 16 * result + digit;
49 [ - + + ]: 153121 : }
50 : 38349 : out = result;
51 : :
52 : 76698 : return first;
53 : 38349 : }
54 : :
55 : 21796782 : enum jtokentype getJsonToken(std::string& tokenVal, unsigned int& consumed,
56 : : const char *raw, const char *end)
57 : : {
58 : 21796782 : tokenVal.clear();
59 : 21796782 : consumed = 0;
60 : :
61 : 21796782 : const char *rawStart = raw;
62 : :
63 [ + + + + ]: 23350309 : while (raw < end && (json_isspace(*raw))) // skip whitespace
64 : 1553527 : raw++;
65 : :
66 [ + + ]: 21796782 : if (raw >= end)
67 : 16928 : return JTOK_NONE;
68 : :
69 [ + + + + : 21779854 : switch (*raw) {
+ + + + +
+ ]
70 : :
71 : : case '{':
72 : 47671 : raw++;
73 : 47671 : consumed = (raw - rawStart);
74 : 47671 : return JTOK_OBJ_OPEN;
75 : : case '}':
76 : 41287 : raw++;
77 : 41287 : consumed = (raw - rawStart);
78 : 41287 : return JTOK_OBJ_CLOSE;
79 : : case '[':
80 : 481690 : raw++;
81 : 481690 : consumed = (raw - rawStart);
82 : 481690 : return JTOK_ARR_OPEN;
83 : : case ']':
84 : 450113 : raw++;
85 : 450113 : consumed = (raw - rawStart);
86 : 450113 : return JTOK_ARR_CLOSE;
87 : :
88 : : case ':':
89 : 894945 : raw++;
90 : 894945 : consumed = (raw - rawStart);
91 : 894945 : return JTOK_COLON;
92 : : case ',':
93 : 3950473 : raw++;
94 : 3950473 : consumed = (raw - rawStart);
95 : 3950473 : return JTOK_COMMA;
96 : :
97 : : case 'n':
98 : : case 't':
99 : : case 'f':
100 [ + + ]: 17206 : if (!strncmp(raw, "null", 4)) {
101 : 12581 : raw += 4;
102 : 12581 : consumed = (raw - rawStart);
103 : 12581 : return JTOK_KW_NULL;
104 [ + + ]: 4625 : } else if (!strncmp(raw, "true", 4)) {
105 : 1468 : raw += 4;
106 : 1468 : consumed = (raw - rawStart);
107 : 1468 : return JTOK_KW_TRUE;
108 [ + + ]: 3157 : } else if (!strncmp(raw, "false", 5)) {
109 : 3036 : raw += 5;
110 : 3036 : consumed = (raw - rawStart);
111 : 3036 : return JTOK_KW_FALSE;
112 : : } else
113 : 121 : return JTOK_ERR;
114 : :
115 : : case '-':
116 : : case '0':
117 : : case '1':
118 : : case '2':
119 : : case '3':
120 : : case '4':
121 : : case '5':
122 : : case '6':
123 : : case '7':
124 : : case '8':
125 : : case '9': {
126 : : // part 1: int
127 : 14666421 : std::string numStr;
128 : :
129 : 14666421 : const char *first = raw;
130 : :
131 : 14666421 : const char *firstDigit = first;
132 [ + + + + ]: 14666421 : if (!json_isdigit(*firstDigit))
133 : 174503 : firstDigit++;
134 [ + + + - : 8321217 : if ((*firstDigit == '0') && json_isdigit(firstDigit[1]))
+ + ]
135 : 37 : return JTOK_ERR;
136 : :
137 [ + - ]: 8321180 : numStr += *raw; // copy first char
138 : 8321180 : raw++;
139 : :
140 [ + + + + : 8321180 : if ((*first == '-') && (raw < end) && (!json_isdigit(*raw)))
+ - + + ]
141 : 42 : return JTOK_ERR;
142 : :
143 [ + + + - : 75237155 : while (raw < end && json_isdigit(*raw)) { // copy digits
+ + ]
144 [ + - ]: 31862417 : numStr += *raw;
145 : 31862417 : raw++;
146 : : }
147 : :
148 : : // part 2: frac
149 [ + + + + ]: 8321138 : if (raw < end && *raw == '.') {
150 [ + - ]: 78761 : numStr += *raw; // copy .
151 : 78761 : raw++;
152 : :
153 [ + + + - : 78761 : if (raw >= end || !json_isdigit(*raw))
+ + ]
154 : 53 : return JTOK_ERR;
155 [ + + + - : 3373400 : while (raw < end && json_isdigit(*raw)) { // copy digits
+ + ]
156 [ + - ]: 1608295 : numStr += *raw;
157 : 1608295 : raw++;
158 : : }
159 : 78708 : }
160 : :
161 : : // part 3: exp
162 [ + + + + ]: 8321085 : if (raw < end && (*raw == 'e' || *raw == 'E')) {
163 [ + + ]: 3190524 : numStr += *raw; // copy E
164 : 17922 : raw++;
165 : :
166 [ + + + + : 17922 : if (raw < end && (*raw == '-' || *raw == '+')) { // copy +/-
+ + ]
167 [ + - ]: 12704 : numStr += *raw;
168 : 12704 : raw++;
169 : 12704 : }
170 : :
171 [ + + + - : 17922 : if (raw >= end || !json_isdigit(*raw))
+ + ]
172 : 119 : return JTOK_ERR;
173 [ + + + - : 206554 : while (raw < end && json_isdigit(*raw)) { // copy digits
+ + ]
174 [ + - ]: 85710 : numStr += *raw;
175 : 85710 : raw++;
176 : : }
177 : 17803 : }
178 : :
179 [ + + ]: 5148364 : tokenVal = numStr;
180 : 8320966 : consumed = (raw - rawStart);
181 : 8320966 : return JTOK_NUMBER;
182 : 21011625 : }
183 : :
184 : : case '"': {
185 : 1229075 : raw++; // skip "
186 : :
187 : 1229075 : std::string valStr;
188 [ + - ]: 1229075 : JSONUTF8StringFilter writer(valStr);
189 : :
190 : 110063936 : while (true) {
191 [ + + + + ]: 110063936 : if (raw >= end || (unsigned char)*raw < 0x20)
192 : 850 : return JTOK_ERR;
193 : :
194 [ + + ]: 110063086 : else if (*raw == '\\') {
195 : 79957 : raw++; // skip backslash
196 : :
197 [ + + ]: 79957 : if (raw >= end)
198 : 39 : return JTOK_ERR;
199 : :
200 [ + + + + : 79918 : switch (*raw) {
+ + + + +
+ ]
201 [ + - ]: 2840 : case '"': writer.push_back('\"'); break;
202 [ + - ]: 20345 : case '\\': writer.push_back('\\'); break;
203 [ + - ]: 1494 : case '/': writer.push_back('/'); break;
204 [ + - ]: 1596 : case 'b': writer.push_back('\b'); break;
205 [ + - ]: 10863 : case 'f': writer.push_back('\f'); break;
206 [ + - ]: 1645 : case 'n': writer.push_back('\n'); break;
207 [ + - ]: 1262 : case 'r': writer.push_back('\r'); break;
208 [ + - ]: 1461 : case 't': writer.push_back('\t'); break;
209 : :
210 : : case 'u': {
211 : 38370 : unsigned int codepoint;
212 [ + + + + ]: 76719 : if (raw + 1 + 4 >= end ||
213 [ + - ]: 38349 : hatoui(raw + 1, raw + 1 + 4, codepoint) !=
214 : 38349 : raw + 1 + 4)
215 : 208 : return JTOK_ERR;
216 [ + - ]: 38162 : writer.push_back_u(codepoint);
217 : 38162 : raw += 4;
218 : 38162 : break;
219 [ + + ]: 38370 : }
220 : : default:
221 : 42 : return JTOK_ERR;
222 : :
223 : : }
224 : :
225 : 79668 : raw++; // skip esc'd char
226 : 79668 : }
227 : :
228 [ + + ]: 109983129 : else if (*raw == '"') {
229 : 1227936 : raw++; // skip "
230 : 1227936 : break; // stop scanning
231 : : }
232 : :
233 : : else {
234 [ + - ]: 108755193 : writer.push_back(static_cast<unsigned char>(*raw));
235 : 108755193 : raw++;
236 : : }
237 : : }
238 : :
239 [ + - + + ]: 1227936 : if (!writer.finalize())
240 : 234 : return JTOK_ERR;
241 [ + - ]: 1227702 : tokenVal = valStr;
242 : 1227702 : consumed = (raw - rawStart);
243 : 1227702 : return JTOK_STRING;
244 : 1229075 : }
245 : :
246 : : default:
247 : 973 : return JTOK_ERR;
248 : : }
249 : 28141986 : }
250 : :
251 : : enum expect_bits : unsigned {
252 : : EXP_OBJ_NAME = (1U << 0),
253 : : EXP_COLON = (1U << 1),
254 : : EXP_ARR_VALUE = (1U << 2),
255 : : EXP_VALUE = (1U << 3),
256 : : EXP_NOT_VALUE = (1U << 4),
257 : : };
258 : :
259 : : #define expect(bit) (expectMask & (EXP_##bit))
260 : : #define setExpect(bit) (expectMask |= EXP_##bit)
261 : : #define clearExpect(bit) (expectMask &= ~EXP_##bit)
262 : :
263 : 20005 : bool UniValue::read(std::string_view str_in)
264 : : {
265 : 20005 : clear();
266 : :
267 : 20005 : uint32_t expectMask = 0;
268 : 20005 : std::vector<UniValue*> stack;
269 : :
270 : 20005 : std::string tokenVal;
271 : 20005 : unsigned int consumed;
272 : 20005 : enum jtokentype tok = JTOK_NONE;
273 : 20005 : enum jtokentype last_tok = JTOK_NONE;
274 : 20005 : const char* raw{str_in.data()};
275 : 20005 : const char* end{raw + str_in.size()};
276 : 20005 : do {
277 : 10306336 : last_tok = tok;
278 : :
279 [ + - ]: 10306336 : tok = getJsonToken(tokenVal, consumed, raw, end);
280 [ + + + + ]: 10306336 : if (tok == JTOK_NONE || tok == JTOK_ERR)
281 : 3209 : return false;
282 : 10303127 : raw += consumed;
283 : :
284 [ - + + + ]: 16169287 : bool isValueOpen = jsonTokenIsValue(tok) ||
285 [ + + ]: 5866160 : tok == JTOK_OBJ_OPEN || tok == JTOK_ARR_OPEN;
286 : :
287 [ + + ]: 10303127 : if (expect(VALUE)) {
288 [ + + ]: 894837 : if (!isValueOpen)
289 : 24 : return false;
290 : 894813 : clearExpect(VALUE);
291 : :
292 [ + + ]: 10303103 : } else if (expect(ARR_VALUE)) {
293 [ + + ]: 3579365 : bool isArrValue = isValueOpen || (tok == JTOK_ARR_CLOSE);
294 [ + + ]: 3579365 : if (!isArrValue)
295 : 30 : return false;
296 : :
297 : 3579335 : clearExpect(ARR_VALUE);
298 : :
299 [ + + + + ]: 9408290 : } else if (expect(OBJ_NAME)) {
300 [ + + ]: 899497 : bool isObjName = (tok == JTOK_OBJ_CLOSE || tok == JTOK_STRING);
301 [ + + ]: 899497 : if (!isObjName)
302 : 33 : return false;
303 : :
304 [ + + + + ]: 5828925 : } else if (expect(COLON)) {
305 [ + + ]: 894927 : if (tok != JTOK_COLON)
306 : 29 : return false;
307 : 894898 : clearExpect(COLON);
308 : :
309 [ + - + + ]: 4929399 : } else if (!expect(COLON) && (tok == JTOK_COLON)) {
310 : 31 : return false;
311 : : }
312 : :
313 [ + + ]: 10302980 : if (expect(NOT_VALUE)) {
314 [ + + ]: 4911274 : if (isValueOpen)
315 : 78 : return false;
316 : 4911196 : clearExpect(NOT_VALUE);
317 : 4911196 : }
318 : :
319 [ + + + - : 10302902 : switch (tok) {
+ + + + ]
320 : :
321 : : case JTOK_OBJ_OPEN:
322 : : case JTOK_ARR_OPEN: {
323 : 529312 : VType utyp = (tok == JTOK_OBJ_OPEN ? VOBJ : VARR);
324 [ + + ]: 529312 : if (!stack.size()) {
325 [ + + ]: 11426 : if (utyp == VOBJ)
326 [ + - ]: 4072 : setObject();
327 : : else
328 [ + - ]: 7354 : setArray();
329 [ - + ]: 11426 : stack.push_back(this);
330 : 11426 : } else {
331 [ + - ]: 517886 : UniValue tmpVal(utyp);
332 : 517886 : UniValue *top = stack.back();
333 [ + - ]: 517886 : top->values.push_back(tmpVal);
334 : :
335 : 517886 : UniValue *newTop = &(top->values.back());
336 [ + - ]: 517886 : stack.push_back(newTop);
337 : 517886 : }
338 : :
339 [ + + ]: 529312 : if (stack.size() > MAX_JSON_DEPTH)
340 : 7 : return false;
341 : :
342 [ + + ]: 529305 : if (utyp == VOBJ)
343 : 47656 : setExpect(OBJ_NAME);
344 : : else
345 : 481649 : setExpect(ARR_VALUE);
346 : 529305 : break;
347 [ + + ]: 529312 : }
348 : :
349 : : case JTOK_OBJ_CLOSE:
350 : : case JTOK_ARR_CLOSE: {
351 [ + + + + ]: 491373 : if (!stack.size() || (last_tok == JTOK_COMMA))
352 : 38 : return false;
353 : :
354 : 491335 : VType utyp = (tok == JTOK_OBJ_CLOSE ? VOBJ : VARR);
355 : 491335 : UniValue *top = stack.back();
356 [ - + + + ]: 491335 : if (utyp != top->getType())
357 : 14 : return false;
358 : :
359 : 491321 : stack.pop_back();
360 : 491321 : clearExpect(OBJ_NAME);
361 : 491321 : setExpect(NOT_VALUE);
362 : 491321 : break;
363 : 491335 : }
364 : :
365 : : case JTOK_COLON: {
366 [ + - ]: 894898 : if (!stack.size())
367 : 0 : return false;
368 : :
369 : 894898 : UniValue *top = stack.back();
370 [ - + - + ]: 894898 : if (top->getType() != VOBJ)
371 : 0 : return false;
372 : :
373 : 894898 : setExpect(VALUE);
374 : 894898 : break;
375 : 894898 : }
376 : :
377 : : case JTOK_COMMA: {
378 [ + + - + ]: 7900854 : if (!stack.size() ||
379 [ + - ]: 3950421 : (last_tok == JTOK_COMMA) || (last_tok == JTOK_ARR_OPEN))
380 : 12 : return false;
381 : :
382 : 3950421 : UniValue *top = stack.back();
383 [ + - + + ]: 3950421 : if (top->getType() == VOBJ)
384 : 852159 : setExpect(OBJ_NAME);
385 : : else
386 : 3098262 : setExpect(ARR_VALUE);
387 : : break;
388 : 3950421 : }
389 : :
390 : : case JTOK_KW_NULL:
391 : : case JTOK_KW_TRUE:
392 : : case JTOK_KW_FALSE: {
393 [ - + ]: 17079 : UniValue tmpVal;
394 [ + + + - ]: 17079 : switch (tok) {
395 : : case JTOK_KW_NULL:
396 : : // do nothing more
397 : : break;
398 : : case JTOK_KW_TRUE:
399 [ + - ]: 1467 : tmpVal.setBool(true);
400 : 1467 : break;
401 : : case JTOK_KW_FALSE:
402 [ + - ]: 3036 : tmpVal.setBool(false);
403 : 3036 : break;
404 : 0 : default: /* impossible */ break;
405 : : }
406 : :
407 [ + + ]: 17079 : if (!stack.size()) {
408 [ + - ]: 507 : *this = tmpVal;
409 : 507 : break;
410 : : }
411 : :
412 : 16572 : UniValue *top = stack.back();
413 [ - + ]: 16572 : top->values.push_back(tmpVal);
414 : :
415 : 16572 : setExpect(NOT_VALUE);
416 : : break;
417 : 17079 : }
418 : :
419 : : case JTOK_NUMBER: {
420 [ - + - + ]: 3192128 : UniValue tmpVal(VNUM, tokenVal);
421 [ + + ]: 3192128 : if (!stack.size()) {
422 [ + - ]: 2525 : *this = tmpVal;
423 : 2525 : break;
424 : : }
425 : :
426 : 3189603 : UniValue *top = stack.back();
427 [ - + ]: 3189603 : top->values.push_back(tmpVal);
428 : :
429 : 3189603 : setExpect(NOT_VALUE);
430 : : break;
431 : 3192128 : }
432 : :
433 : : case JTOK_STRING: {
434 [ + + ]: 1227679 : if (expect(OBJ_NAME)) {
435 : 894959 : UniValue *top = stack.back();
436 [ - + ]: 894959 : top->keys.push_back(tokenVal);
437 : 894959 : clearExpect(OBJ_NAME);
438 : 894959 : setExpect(COLON);
439 : 894959 : } else {
440 [ - + - + ]: 332720 : UniValue tmpVal(VSTR, tokenVal);
441 [ + + ]: 332720 : if (!stack.size()) {
442 [ + - ]: 3605 : *this = tmpVal;
443 : 3605 : break;
444 : : }
445 : 329115 : UniValue *top = stack.back();
446 [ + - ]: 329115 : top->values.push_back(tmpVal);
447 [ - + + ]: 332720 : }
448 : :
449 : 1224074 : setExpect(NOT_VALUE);
450 : 1224074 : break;
451 : : }
452 : :
453 : : default:
454 : 0 : return false;
455 : : }
456 [ + + + + ]: 13075551 : } while (!stack.empty ());
457 : :
458 : : /* Check that nothing follows the initial construct (parsed above). */
459 [ + - ]: 16500 : tok = getJsonToken(tokenVal, consumed, raw, end);
460 [ + + ]: 16500 : if (tok != JTOK_NONE)
461 : 264 : return false;
462 : :
463 : 16236 : return true;
464 : 2792429 : }
465 : :
|
