Branch data Line data Source code
1 : : // Copyright 2014 BitPay Inc.
2 : : // Copyright (c) 2015-present The Bitcoin Core developers
3 : : // Distributed under the MIT software license, see the accompanying
4 : : // file COPYING or https://opensource.org/licenses/mit-license.php.
5 : :
6 : : #include <univalue.h>
7 : : #include <univalue_utffilter.h>
8 : :
9 : : #include <cstdint>
10 : : #include <cstring>
11 : : #include <string>
12 : : #include <string_view>
13 : : #include <utility>
14 : : #include <vector>
15 : :
16 : : /*
17 : : * According to stackexchange, the original json test suite wanted
18 : : * to limit depth to 22. Widely-deployed PHP bails at depth 512,
19 : : * so we will follow PHP's lead, which should be more than sufficient
20 : : * (further stackexchange comments indicate depth > 32 rarely occurs).
21 : : */
22 : : static constexpr size_t MAX_JSON_DEPTH = 512;
23 : :
24 : 8377582 : static bool json_isdigit(int ch)
25 : : {
26 : 8377582 : return ((ch >= '0') && (ch <= '9'));
27 : : }
28 : :
29 : : // convert hexadecimal string to unsigned integer
30 : 646 : static const char *hatoui(const char *first, const char *last,
31 : : unsigned int& out)
32 : : {
33 : 646 : unsigned int result = 0;
34 [ + + ]: 3230 : for (; first != last; ++first)
35 : : {
36 : 2584 : int digit;
37 [ + + ]: 2584 : if (json_isdigit(*first))
38 : 1268 : digit = *first - '0';
39 : :
40 [ + + ]: 1316 : else if (*first >= 'a' && *first <= 'f')
41 : 1294 : digit = *first - 'a' + 10;
42 : :
43 [ + - ]: 22 : else if (*first >= 'A' && *first <= 'F')
44 : 22 : digit = *first - 'A' + 10;
45 : :
46 : : else
47 : : break;
48 : :
49 : 2584 : result = 16 * result + digit;
50 : : }
51 : 646 : out = result;
52 : :
53 : 646 : return first;
54 : : }
55 : :
56 : 7138228 : enum jtokentype getJsonToken(std::string& tokenVal, unsigned int& consumed,
57 : : const char *raw, const char *end)
58 : : {
59 : 7138228 : tokenVal.clear();
60 : 7138228 : consumed = 0;
61 : :
62 : 7138228 : const char *rawStart = raw;
63 : :
64 [ + + + + ]: 9145832 : while (raw < end && (json_isspace(*raw))) // skip whitespace
65 : 2007604 : raw++;
66 : :
67 [ + + ]: 7138228 : if (raw >= end)
68 : : return JTOK_NONE;
69 : :
70 [ + + + + : 6919295 : switch (*raw) {
+ + + + +
+ ]
71 : :
72 : 356793 : case '{':
73 : 356793 : raw++;
74 : 356793 : consumed = (raw - rawStart);
75 : 356793 : return JTOK_OBJ_OPEN;
76 : 356776 : case '}':
77 : 356776 : raw++;
78 : 356776 : consumed = (raw - rawStart);
79 : 356776 : return JTOK_OBJ_CLOSE;
80 : 150125 : case '[':
81 : 150125 : raw++;
82 : 150125 : consumed = (raw - rawStart);
83 : 150125 : return JTOK_ARR_OPEN;
84 : 149076 : case ']':
85 : 149076 : raw++;
86 : 149076 : consumed = (raw - rawStart);
87 : 149076 : return JTOK_ARR_CLOSE;
88 : :
89 : 1082186 : case ':':
90 : 1082186 : raw++;
91 : 1082186 : consumed = (raw - rawStart);
92 : 1082186 : return JTOK_COLON;
93 : 879648 : case ',':
94 : 879648 : raw++;
95 : 879648 : consumed = (raw - rawStart);
96 : 879648 : return JTOK_COMMA;
97 : :
98 : 17993 : case 'n':
99 : 17993 : case 't':
100 : 17993 : case 'f':
101 [ + + ]: 17993 : if (!strncmp(raw, "null", 4)) {
102 : 728 : raw += 4;
103 : 728 : consumed = (raw - rawStart);
104 : 728 : return JTOK_KW_NULL;
105 [ + + ]: 17265 : } else if (!strncmp(raw, "true", 4)) {
106 : 15097 : raw += 4;
107 : 15097 : consumed = (raw - rawStart);
108 : 15097 : return JTOK_KW_TRUE;
109 [ + + ]: 2168 : } else if (!strncmp(raw, "false", 5)) {
110 : 2163 : raw += 5;
111 : 2163 : consumed = (raw - rawStart);
112 : 2163 : return JTOK_KW_FALSE;
113 : : } else
114 : : return JTOK_ERR;
115 : :
116 : 2165715 : case '-':
117 : 2165715 : case '0':
118 : 2165715 : case '1':
119 : 2165715 : case '2':
120 : 2165715 : case '3':
121 : 2165715 : case '4':
122 : 2165715 : case '5':
123 : 2165715 : case '6':
124 : 2165715 : case '7':
125 : 2165715 : case '8':
126 : 2165715 : case '9': {
127 : : // part 1: int
128 [ + + ]: 2165715 : std::string numStr;
129 : :
130 : 2165715 : const char *first = raw;
131 : :
132 : 2165715 : const char *firstDigit = first;
133 [ + + ]: 2165715 : if (!json_isdigit(*firstDigit))
134 : 41159 : firstDigit++;
135 [ + + + + ]: 2165715 : if ((*firstDigit == '0') && json_isdigit(firstDigit[1]))
136 : : return JTOK_ERR;
137 : :
138 [ + - ]: 2165714 : numStr += *raw; // copy first char
139 : 2165714 : raw++;
140 : :
141 [ + + + - : 2165714 : if ((*first == '-') && (raw < end) && (!json_isdigit(*raw)))
+ - ]
142 : : return JTOK_ERR;
143 : :
144 [ + + + + ]: 6875209 : while (raw < end && json_isdigit(*raw)) { // copy digits
145 [ + - ]: 4709495 : numStr += *raw;
146 : 4709495 : raw++;
147 : : }
148 : :
149 : : // part 2: frac
150 [ + + + + ]: 2165714 : if (raw < end && *raw == '.') {
151 [ + - ]: 54799 : numStr += *raw; // copy .
152 : 54799 : raw++;
153 : :
154 [ + - + - ]: 54799 : if (raw >= end || !json_isdigit(*raw))
155 : : return JTOK_ERR;
156 [ + + + + ]: 577221 : while (raw < end && json_isdigit(*raw)) { // copy digits
157 [ + - ]: 522422 : numStr += *raw;
158 : 522422 : raw++;
159 : : }
160 : : }
161 : :
162 : : // part 3: exp
163 [ + + + + : 2165714 : if (raw < end && (*raw == 'e' || *raw == 'E')) {
+ + ]
164 [ + - ]: 23972 : numStr += *raw; // copy E
165 : 23972 : raw++;
166 : :
167 [ + - + + : 23972 : if (raw < end && (*raw == '-' || *raw == '+')) { // copy +/-
+ + ]
168 [ + - ]: 23965 : numStr += *raw;
169 : 23965 : raw++;
170 : : }
171 : :
172 [ + - + + ]: 23972 : if (raw >= end || !json_isdigit(*raw))
173 : : return JTOK_ERR;
174 [ + + + + ]: 71897 : while (raw < end && json_isdigit(*raw)) { // copy digits
175 [ + - ]: 47928 : numStr += *raw;
176 : 47928 : raw++;
177 : : }
178 : : }
179 : :
180 [ + - ]: 2165711 : tokenVal = numStr;
181 : 2165711 : consumed = (raw - rawStart);
182 : 2165711 : return JTOK_NUMBER;
183 : 2165715 : }
184 : :
185 : 1760957 : case '"': {
186 : 1760957 : raw++; // skip "
187 : :
188 : 1760957 : std::string valStr;
189 : 1760957 : JSONUTF8StringFilter writer(valStr);
190 : :
191 : 4695542484 : while (true) {
192 [ + + + + ]: 4695542484 : if (raw >= end || (unsigned char)*raw < 0x20)
193 : : return JTOK_ERR;
194 : :
195 [ + + ]: 4695542480 : else if (*raw == '\\') {
196 : 693 : raw++; // skip backslash
197 : :
198 [ + - ]: 693 : if (raw >= end)
199 : : return JTOK_ERR;
200 : :
201 [ + + + + : 693 : switch (*raw) {
+ + + + +
+ ]
202 [ + - ]: 16 : case '"': writer.push_back('\"'); break;
203 [ + - ]: 4 : case '\\': writer.push_back('\\'); break;
204 [ + - ]: 2 : case '/': writer.push_back('/'); break;
205 [ + - ]: 4 : case 'b': writer.push_back('\b'); break;
206 [ + - ]: 4 : case 'f': writer.push_back('\f'); break;
207 [ + - ]: 5 : case 'n': writer.push_back('\n'); break;
208 [ + - ]: 4 : case 'r': writer.push_back('\r'); break;
209 [ + - ]: 4 : case 't': writer.push_back('\t'); break;
210 : :
211 : 646 : case 'u': {
212 : 646 : unsigned int codepoint;
213 [ + - + - ]: 1292 : if (raw + 1 + 4 >= end ||
214 : 646 : hatoui(raw + 1, raw + 1 + 4, codepoint) !=
215 : : raw + 1 + 4)
216 : 0 : return JTOK_ERR;
217 [ + - ]: 646 : writer.push_back_u(codepoint);
218 : 646 : raw += 4;
219 : 646 : break;
220 : : }
221 : : default:
222 : : return JTOK_ERR;
223 : :
224 : : }
225 : :
226 : 689 : raw++; // skip esc'd char
227 : : }
228 : :
229 [ + + ]: 4695541787 : else if (*raw == '"') {
230 : 1760949 : raw++; // skip "
231 : 1760949 : break; // stop scanning
232 : : }
233 : :
234 : : else {
235 [ + - ]: 4693780838 : writer.push_back(static_cast<unsigned char>(*raw));
236 : 4693780838 : raw++;
237 : : }
238 : : }
239 : :
240 [ + + + + ]: 3521898 : if (!writer.finalize())
241 : : return JTOK_ERR;
242 [ + - ]: 1760945 : tokenVal = valStr;
243 : 1760945 : consumed = (raw - rawStart);
244 : 1760945 : return JTOK_STRING;
245 : 1760957 : }
246 : :
247 : : default:
248 : : return JTOK_ERR;
249 : : }
250 : : }
251 : :
252 : : enum expect_bits : unsigned {
253 : : EXP_OBJ_NAME = (1U << 0),
254 : : EXP_COLON = (1U << 1),
255 : : EXP_ARR_VALUE = (1U << 2),
256 : : EXP_VALUE = (1U << 3),
257 : : EXP_NOT_VALUE = (1U << 4),
258 : : };
259 : :
260 : : #define expect(bit) (expectMask & (EXP_##bit))
261 : : #define setExpect(bit) (expectMask |= EXP_##bit)
262 : : #define clearExpect(bit) (expectMask &= ~EXP_##bit)
263 : :
264 : 219005 : bool UniValue::read(std::string_view json)
265 : : {
266 [ + - ]: 219005 : UniValue parsed;
267 [ + - + + ]: 219005 : if (!parsed.read_impl(json)) {
268 [ + - ]: 78 : setNull();
269 : : return false;
270 : : }
271 : 218927 : *this = std::move(parsed);
272 : 218927 : return true;
273 : 219005 : }
274 : :
275 : 219005 : bool UniValue::read_impl(std::string_view str_in)
276 : : {
277 : 219005 : clear();
278 : :
279 : 219005 : uint32_t expectMask = 0;
280 : 219005 : std::vector<UniValue*> stack;
281 : :
282 : 219005 : std::string tokenVal;
283 : 219005 : unsigned int consumed;
284 : 219005 : enum jtokentype tok = JTOK_NONE;
285 : 219005 : enum jtokentype last_tok = JTOK_NONE;
286 : 219005 : const char* raw{str_in.data()};
287 : 219005 : const char* end{raw + str_in.size()};
288 : 5092093 : do {
289 : 5092093 : last_tok = tok;
290 : :
291 [ + - ]: 5092093 : tok = getJsonToken(tokenVal, consumed, raw, end);
292 [ + + ]: 5092093 : if (tok == JTOK_NONE || tok == JTOK_ERR)
293 : : return false;
294 : 5092047 : raw += consumed;
295 : :
296 [ + + ]: 5092047 : bool isValueOpen = jsonTokenIsValue(tok) ||
297 [ + + ]: 2974599 : tok == JTOK_OBJ_OPEN || tok == JTOK_ARR_OPEN;
298 : :
299 [ + + ]: 5092047 : if (expect(VALUE)) {
300 [ + + ]: 1082181 : if (!isValueOpen)
301 : : return false;
302 : 1082179 : clearExpect(VALUE);
303 : :
304 [ + + ]: 4009866 : } else if (expect(ARR_VALUE)) {
305 : 242725 : bool isArrValue = isValueOpen || (tok == JTOK_ARR_CLOSE);
306 [ + + ]: 242725 : if (!isArrValue)
307 : : return false;
308 : :
309 : 242723 : clearExpect(ARR_VALUE);
310 : :
311 [ + + ]: 3767141 : } else if (expect(OBJ_NAME)) {
312 : 1143812 : bool isObjName = (tok == JTOK_OBJ_CLOSE || tok == JTOK_STRING);
313 [ + + ]: 1143812 : if (!isObjName)
314 : : return false;
315 : :
316 [ + + ]: 2623329 : } else if (expect(COLON)) {
317 [ + + ]: 1082187 : if (tok != JTOK_COLON)
318 : : return false;
319 : 1082184 : clearExpect(COLON);
320 : :
321 [ + + ]: 1541142 : } else if (!expect(COLON) && (tok == JTOK_COLON)) {
322 : : return false;
323 : : }
324 : :
325 [ + + ]: 5092035 : if (expect(NOT_VALUE)) {
326 [ + + ]: 2404340 : if (isValueOpen)
327 : : return false;
328 : 2404338 : clearExpect(NOT_VALUE);
329 : : }
330 : :
331 [ + + + + : 5092033 : switch (tok) {
+ + + - ]
332 : :
333 : 506914 : case JTOK_OBJ_OPEN:
334 : 506914 : case JTOK_ARR_OPEN: {
335 [ + + ]: 506914 : VType utyp = (tok == JTOK_OBJ_OPEN ? VOBJ : VARR);
336 [ - + + + ]: 506914 : if (!stack.size()) {
337 [ + + ]: 218884 : if (utyp == VOBJ)
338 [ + - ]: 218182 : setObject();
339 : : else
340 [ + - ]: 702 : setArray();
341 [ + - ]: 218884 : stack.push_back(this);
342 : : } else {
343 : 288030 : UniValue tmpVal(utyp);
344 : 288030 : UniValue *top = stack.back();
345 [ + - ]: 288030 : top->values.push_back(tmpVal);
346 : :
347 : 288030 : UniValue *newTop = &(top->values.back());
348 [ + - ]: 288030 : stack.push_back(newTop);
349 : 288030 : }
350 : :
351 [ - + + + ]: 506914 : if (stack.size() > MAX_JSON_DEPTH)
352 : : return false;
353 : :
354 [ + + ]: 506912 : if (utyp == VOBJ)
355 : 356791 : setExpect(OBJ_NAME);
356 : : else
357 : 150121 : setExpect(ARR_VALUE);
358 : : break;
359 : : }
360 : :
361 : 505848 : case JTOK_OBJ_CLOSE:
362 : 505848 : case JTOK_ARR_CLOSE: {
363 [ - + + - : 505848 : if (!stack.size() || (last_tok == JTOK_COMMA))
+ + ]
364 : : return false;
365 : :
366 [ + + ]: 505846 : VType utyp = (tok == JTOK_OBJ_CLOSE ? VOBJ : VARR);
367 : 505846 : UniValue *top = stack.back();
368 [ + + ]: 505846 : if (utyp != top->getType())
369 : : return false;
370 : :
371 : 505845 : stack.pop_back();
372 : 505845 : clearExpect(OBJ_NAME);
373 : 505845 : setExpect(NOT_VALUE);
374 : 505845 : break;
375 : : }
376 : :
377 : 1082184 : case JTOK_COLON: {
378 [ - + + - ]: 1082184 : if (!stack.size())
379 : : return false;
380 : :
381 : 1082184 : UniValue *top = stack.back();
382 [ + - ]: 1082184 : if (top->getType() != VOBJ)
383 : : return false;
384 : :
385 : 1082184 : setExpect(VALUE);
386 : 1082184 : break;
387 : : }
388 : :
389 : 879644 : case JTOK_COMMA: {
390 [ - + ]: 879644 : if (!stack.size() ||
391 [ + - + - ]: 879644 : (last_tok == JTOK_COMMA) || (last_tok == JTOK_ARR_OPEN))
392 : : return false;
393 : :
394 : 879644 : UniValue *top = stack.back();
395 [ + + ]: 879644 : if (top->getType() == VOBJ)
396 : 787024 : setExpect(OBJ_NAME);
397 : : else
398 : 92620 : setExpect(ARR_VALUE);
399 : : break;
400 : : }
401 : :
402 : 17985 : case JTOK_KW_NULL:
403 : 17985 : case JTOK_KW_TRUE:
404 : 17985 : case JTOK_KW_FALSE: {
405 [ + + + ]: 17985 : UniValue tmpVal;
406 [ + + + ]: 17985 : switch (tok) {
407 : : case JTOK_KW_NULL:
408 : : // do nothing more
409 : : break;
410 : 15095 : case JTOK_KW_TRUE:
411 [ + - ]: 15095 : tmpVal.setBool(true);
412 : : break;
413 : 2163 : case JTOK_KW_FALSE:
414 [ + - ]: 2163 : tmpVal.setBool(false);
415 : : break;
416 : : default: /* impossible */ break;
417 : : }
418 : :
419 [ - + + + ]: 17985 : if (!stack.size()) {
420 [ + - ]: 40 : *this = tmpVal;
421 : : break;
422 : : }
423 : :
424 : 17945 : UniValue *top = stack.back();
425 [ + - ]: 17945 : top->values.push_back(tmpVal);
426 : :
427 : 17945 : setExpect(NOT_VALUE);
428 : 17945 : break;
429 : 17985 : }
430 : :
431 : 338515 : case JTOK_NUMBER: {
432 [ - + ]: 677030 : UniValue tmpVal(VNUM, tokenVal);
433 [ - + + + ]: 338515 : if (!stack.size()) {
434 [ + - ]: 58 : *this = tmpVal;
435 : : break;
436 : : }
437 : :
438 : 338457 : UniValue *top = stack.back();
439 [ + - ]: 338457 : top->values.push_back(tmpVal);
440 : :
441 : 338457 : setExpect(NOT_VALUE);
442 : 338457 : break;
443 : 338515 : }
444 : :
445 : 1760943 : case JTOK_STRING: {
446 [ + + ]: 1760943 : if (expect(OBJ_NAME)) {
447 : 1082187 : UniValue *top = stack.back();
448 [ + - ]: 1082187 : top->keys.push_back(tokenVal);
449 : 1082187 : clearExpect(OBJ_NAME);
450 : 1082187 : setExpect(COLON);
451 : : } else {
452 [ - + ]: 1357512 : UniValue tmpVal(VSTR, tokenVal);
453 [ - + + + ]: 678756 : if (!stack.size()) {
454 [ + - ]: 3 : *this = tmpVal;
455 : 3 : break;
456 : : }
457 : 678753 : UniValue *top = stack.back();
458 [ + - ]: 678753 : top->values.push_back(tmpVal);
459 : 678756 : }
460 : :
461 : 1760940 : setExpect(NOT_VALUE);
462 : 1760940 : break;
463 : : }
464 : :
465 : : default:
466 : : return false;
467 : : }
468 [ + + ]: 5092028 : } while (!stack.empty ());
469 : :
470 : : /* Check that nothing follows the initial construct (parsed above). */
471 [ + - ]: 218940 : tok = getJsonToken(tokenVal, consumed, raw, end);
472 [ + + ]: 218940 : if (tok != JTOK_NONE)
473 : 13 : return false;
474 : :
475 : : return true;
476 : 219005 : }
|
