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 <cstring>
10 : : #include <string>
11 : : #include <string_view>
12 : : #include <vector>
13 : :
14 : : /*
15 : : * According to stackexchange, the original json test suite wanted
16 : : * to limit depth to 22. Widely-deployed PHP bails at depth 512,
17 : : * so we will follow PHP's lead, which should be more than sufficient
18 : : * (further stackexchange comments indicate depth > 32 rarely occurs).
19 : : */
20 : : static constexpr size_t MAX_JSON_DEPTH = 512;
21 : :
22 : 45483438 : static bool json_isdigit(int ch)
23 : : {
24 : 45483438 : return ((ch >= '0') && (ch <= '9'));
25 : : }
26 : :
27 : : // convert hexadecimal string to unsigned integer
28 : 41334 : static const char *hatoui(const char *first, const char *last,
29 : : unsigned int& out)
30 : : {
31 : 41334 : unsigned int result = 0;
32 [ + + ]: 206222 : for (; first != last; ++first)
33 : : {
34 : 165059 : int digit;
35 [ + + ]: 165059 : if (json_isdigit(*first))
36 : 94421 : digit = *first - '0';
37 : :
38 [ + + ]: 70638 : else if (*first >= 'a' && *first <= 'f')
39 : 37772 : digit = *first - 'a' + 10;
40 : :
41 [ + + ]: 32866 : else if (*first >= 'A' && *first <= 'F')
42 : 32695 : digit = *first - 'A' + 10;
43 : :
44 : : else
45 : : break;
46 : :
47 : 164888 : result = 16 * result + digit;
48 : : }
49 : 41334 : out = result;
50 : :
51 : 41334 : return first;
52 : : }
53 : :
54 : 13629984 : enum jtokentype getJsonToken(std::string& tokenVal, unsigned int& consumed,
55 : : const char *raw, const char *end)
56 : : {
57 : 13629984 : tokenVal.clear();
58 : 13629984 : consumed = 0;
59 : :
60 : 13629984 : const char *rawStart = raw;
61 : :
62 [ + + + + ]: 14987859 : while (raw < end && (json_isspace(*raw))) // skip whitespace
63 : 1357875 : raw++;
64 : :
65 [ + + ]: 13629984 : if (raw >= end)
66 : : return JTOK_NONE;
67 : :
68 [ + + + + : 13612260 : switch (*raw) {
+ + + + +
+ ]
69 : :
70 : 57452 : case '{':
71 : 57452 : raw++;
72 : 57452 : consumed = (raw - rawStart);
73 : 57452 : return JTOK_OBJ_OPEN;
74 : 51237 : case '}':
75 : 51237 : raw++;
76 : 51237 : consumed = (raw - rawStart);
77 : 51237 : return JTOK_OBJ_CLOSE;
78 : 337092 : case '[':
79 : 337092 : raw++;
80 : 337092 : consumed = (raw - rawStart);
81 : 337092 : return JTOK_ARR_OPEN;
82 : 315421 : case ']':
83 : 315421 : raw++;
84 : 315421 : consumed = (raw - rawStart);
85 : 315421 : return JTOK_ARR_CLOSE;
86 : :
87 : 1092583 : case ':':
88 : 1092583 : raw++;
89 : 1092583 : consumed = (raw - rawStart);
90 : 1092583 : return JTOK_COLON;
91 : 2437657 : case ',':
92 : 2437657 : raw++;
93 : 2437657 : consumed = (raw - rawStart);
94 : 2437657 : return JTOK_COMMA;
95 : :
96 : 22928 : case 'n':
97 : 22928 : case 't':
98 : 22928 : case 'f':
99 [ + + ]: 22928 : if (!strncmp(raw, "null", 4)) {
100 : 17565 : raw += 4;
101 : 17565 : consumed = (raw - rawStart);
102 : 17565 : return JTOK_KW_NULL;
103 [ + + ]: 5363 : } else if (!strncmp(raw, "true", 4)) {
104 : 1749 : raw += 4;
105 : 1749 : consumed = (raw - rawStart);
106 : 1749 : return JTOK_KW_TRUE;
107 [ + + ]: 3614 : } else if (!strncmp(raw, "false", 5)) {
108 : 3504 : raw += 5;
109 : 3504 : consumed = (raw - rawStart);
110 : 3504 : return JTOK_KW_FALSE;
111 : : } else
112 : : return JTOK_ERR;
113 : :
114 : 7998848 : case '-':
115 : 7998848 : case '0':
116 : 7998848 : case '1':
117 : 7998848 : case '2':
118 : 7998848 : case '3':
119 : 7998848 : case '4':
120 : 7998848 : case '5':
121 : 7998848 : case '6':
122 : 7998848 : case '7':
123 : 7998848 : case '8':
124 : 7998848 : case '9': {
125 : : // part 1: int
126 [ + + ]: 7998848 : std::string numStr;
127 : :
128 : 7998848 : const char *first = raw;
129 : :
130 : 7998848 : const char *firstDigit = first;
131 [ + + ]: 7998848 : if (!json_isdigit(*firstDigit))
132 : 82597 : firstDigit++;
133 [ + + + + ]: 7998848 : if ((*firstDigit == '0') && json_isdigit(firstDigit[1]))
134 : : return JTOK_ERR;
135 : :
136 [ + - ]: 7998782 : numStr += *raw; // copy first char
137 : 7998782 : raw++;
138 : :
139 [ + + + + : 7998782 : if ((*first == '-') && (raw < end) && (!json_isdigit(*raw)))
+ + ]
140 : : return JTOK_ERR;
141 : :
142 [ + + + + ]: 41186272 : while (raw < end && json_isdigit(*raw)) { // copy digits
143 [ + - ]: 33187564 : numStr += *raw;
144 : 33187564 : raw++;
145 : : }
146 : :
147 : : // part 2: frac
148 [ + + + + ]: 7998708 : if (raw < end && *raw == '.') {
149 [ + - ]: 31050 : numStr += *raw; // copy .
150 : 31050 : raw++;
151 : :
152 [ + + + + ]: 31050 : if (raw >= end || !json_isdigit(*raw))
153 : : return JTOK_ERR;
154 [ + + + + ]: 1065953 : while (raw < end && json_isdigit(*raw)) { // copy digits
155 [ + - ]: 1035008 : numStr += *raw;
156 : 1035008 : raw++;
157 : : }
158 : : }
159 : :
160 : : // part 3: exp
161 [ + + + + : 7998603 : if (raw < end && (*raw == 'e' || *raw == 'E')) {
+ + ]
162 [ + - ]: 19475 : numStr += *raw; // copy E
163 : 19475 : raw++;
164 : :
165 [ + + + + : 19475 : if (raw < end && (*raw == '-' || *raw == '+')) { // copy +/-
+ + ]
166 [ + - ]: 11214 : numStr += *raw;
167 : 11214 : raw++;
168 : : }
169 : :
170 [ + + + + ]: 19475 : if (raw >= end || !json_isdigit(*raw))
171 : : return JTOK_ERR;
172 [ + + + + ]: 519709 : while (raw < end && json_isdigit(*raw)) { // copy digits
173 [ + - ]: 500423 : numStr += *raw;
174 : 500423 : raw++;
175 : : }
176 : : }
177 : :
178 [ + - ]: 7998414 : tokenVal = numStr;
179 : 7998414 : consumed = (raw - rawStart);
180 : 7998414 : return JTOK_NUMBER;
181 : 7998848 : }
182 : :
183 : 1297724 : case '"': {
184 : 1297724 : raw++; // skip "
185 : :
186 : 1297724 : std::string valStr;
187 : 1297724 : JSONUTF8StringFilter writer(valStr);
188 : :
189 : 111092998 : while (true) {
190 [ + + + + ]: 111092998 : if (raw >= end || (unsigned char)*raw < 0x20)
191 : : return JTOK_ERR;
192 : :
193 [ + + ]: 111092006 : else if (*raw == '\\') {
194 : 63064 : raw++; // skip backslash
195 : :
196 [ + + ]: 63064 : if (raw >= end)
197 : : return JTOK_ERR;
198 : :
199 [ + + + + : 63018 : switch (*raw) {
+ + + + +
+ ]
200 [ + - ]: 3610 : case '"': writer.push_back('\"'); break;
201 [ + - ]: 3906 : case '\\': writer.push_back('\\'); break;
202 [ + - ]: 1514 : case '/': writer.push_back('/'); break;
203 [ + - ]: 2003 : case 'b': writer.push_back('\b'); break;
204 [ + - ]: 5703 : case 'f': writer.push_back('\f'); break;
205 [ + - ]: 1420 : case 'n': writer.push_back('\n'); break;
206 [ + - ]: 1545 : case 'r': writer.push_back('\r'); break;
207 [ + - ]: 1875 : case 't': writer.push_back('\t'); break;
208 : :
209 : 41387 : case 'u': {
210 : 41387 : unsigned int codepoint;
211 [ + + + + ]: 82721 : if (raw + 1 + 4 >= end ||
212 : 41334 : hatoui(raw + 1, raw + 1 + 4, codepoint) !=
213 : : raw + 1 + 4)
214 : 224 : return JTOK_ERR;
215 [ + - ]: 41163 : writer.push_back_u(codepoint);
216 : 41163 : raw += 4;
217 : 41163 : break;
218 : : }
219 : : default:
220 : : return JTOK_ERR;
221 : :
222 : : }
223 : :
224 : 62739 : raw++; // skip esc'd char
225 : : }
226 : :
227 [ + + ]: 111028942 : else if (*raw == '"') {
228 : 1296407 : raw++; // skip "
229 : 1296407 : break; // stop scanning
230 : : }
231 : :
232 : : else {
233 [ + - ]: 109732535 : writer.push_back(static_cast<unsigned char>(*raw));
234 : 109732535 : raw++;
235 : : }
236 : : }
237 : :
238 [ + + + + ]: 2592814 : if (!writer.finalize())
239 : : return JTOK_ERR;
240 [ + - ]: 1296142 : tokenVal = valStr;
241 : 1296142 : consumed = (raw - rawStart);
242 : 1296142 : return JTOK_STRING;
243 : 1297724 : }
244 : :
245 : : default:
246 : : return JTOK_ERR;
247 : : }
248 : : }
249 : :
250 : : enum expect_bits : unsigned {
251 : : EXP_OBJ_NAME = (1U << 0),
252 : : EXP_COLON = (1U << 1),
253 : : EXP_ARR_VALUE = (1U << 2),
254 : : EXP_VALUE = (1U << 3),
255 : : EXP_NOT_VALUE = (1U << 4),
256 : : };
257 : :
258 : : #define expect(bit) (expectMask & (EXP_##bit))
259 : : #define setExpect(bit) (expectMask |= EXP_##bit)
260 : : #define clearExpect(bit) (expectMask &= ~EXP_##bit)
261 : :
262 : 21779 : bool UniValue::read(std::string_view str_in)
263 : : {
264 : 21779 : clear();
265 : :
266 : 21779 : uint32_t expectMask = 0;
267 : 21779 : std::vector<UniValue*> stack;
268 : :
269 : 21779 : std::string tokenVal;
270 : 21779 : unsigned int consumed;
271 : 21779 : enum jtokentype tok = JTOK_NONE;
272 : 21779 : enum jtokentype last_tok = JTOK_NONE;
273 : 21779 : const char* raw{str_in.data()};
274 : 21779 : const char* end{raw + str_in.size()};
275 : 7562261 : do {
276 : 7562261 : last_tok = tok;
277 : :
278 [ + - ]: 7562261 : tok = getJsonToken(tokenVal, consumed, raw, end);
279 [ + + ]: 7562261 : if (tok == JTOK_NONE || tok == JTOK_ERR)
280 : : return false;
281 : 7558127 : raw += consumed;
282 : :
283 [ + + ]: 7558127 : bool isValueOpen = jsonTokenIsValue(tok) ||
284 [ + + ]: 4291412 : tok == JTOK_OBJ_OPEN || tok == JTOK_ARR_OPEN;
285 : :
286 [ + + ]: 7558127 : if (expect(VALUE)) {
287 [ + + ]: 1092435 : if (!isValueOpen)
288 : : return false;
289 : 1092404 : clearExpect(VALUE);
290 : :
291 [ + + ]: 6465692 : } else if (expect(ARR_VALUE)) {
292 : 1733945 : bool isArrValue = isValueOpen || (tok == JTOK_ARR_CLOSE);
293 [ + + ]: 1733945 : if (!isArrValue)
294 : : return false;
295 : :
296 : 1733902 : clearExpect(ARR_VALUE);
297 : :
298 [ + + ]: 4731747 : } else if (expect(OBJ_NAME)) {
299 : 1097327 : bool isObjName = (tok == JTOK_OBJ_CLOSE || tok == JTOK_STRING);
300 [ + + ]: 1097327 : if (!isObjName)
301 : : return false;
302 : :
303 [ + + ]: 3634420 : } else if (expect(COLON)) {
304 [ + + ]: 1092518 : if (tok != JTOK_COLON)
305 : : return false;
306 : 1092469 : clearExpect(COLON);
307 : :
308 [ + + ]: 2541902 : } else if (!expect(COLON) && (tok == JTOK_COLON)) {
309 : : return false;
310 : : }
311 : :
312 [ + + ]: 7557878 : if (expect(NOT_VALUE)) {
313 [ + + ]: 3615443 : if (isValueOpen)
314 : : return false;
315 : 3615336 : clearExpect(NOT_VALUE);
316 : : }
317 : :
318 [ + + + + : 7557771 : switch (tok) {
+ + + - ]
319 : :
320 : 394470 : case JTOK_OBJ_OPEN:
321 : 394470 : case JTOK_ARR_OPEN: {
322 [ + + ]: 394470 : VType utyp = (tok == JTOK_OBJ_OPEN ? VOBJ : VARR);
323 [ - + + + ]: 394470 : if (!stack.size()) {
324 [ + + ]: 11533 : if (utyp == VOBJ)
325 [ + - ]: 3472 : setObject();
326 : : else
327 [ + - ]: 8061 : setArray();
328 [ + - ]: 11533 : stack.push_back(this);
329 : : } else {
330 : 382937 : UniValue tmpVal(utyp);
331 : 382937 : UniValue *top = stack.back();
332 [ + - ]: 382937 : top->values.push_back(tmpVal);
333 : :
334 : 382937 : UniValue *newTop = &(top->values.back());
335 [ + - ]: 382937 : stack.push_back(newTop);
336 : 382937 : }
337 : :
338 [ - + + + ]: 394470 : if (stack.size() > MAX_JSON_DEPTH)
339 : : return false;
340 : :
341 [ + + ]: 394465 : if (utyp == VOBJ)
342 : 57404 : setExpect(OBJ_NAME);
343 : : else
344 : 337061 : setExpect(ARR_VALUE);
345 : : break;
346 : : }
347 : :
348 : 366607 : case JTOK_OBJ_CLOSE:
349 : 366607 : case JTOK_ARR_CLOSE: {
350 [ - + + + : 366607 : if (!stack.size() || (last_tok == JTOK_COMMA))
+ + ]
351 : : return false;
352 : :
353 [ + + ]: 366519 : VType utyp = (tok == JTOK_OBJ_CLOSE ? VOBJ : VARR);
354 : 366519 : UniValue *top = stack.back();
355 [ + + ]: 366519 : if (utyp != top->getType())
356 : : return false;
357 : :
358 : 366495 : stack.pop_back();
359 : 366495 : clearExpect(OBJ_NAME);
360 : 366495 : setExpect(NOT_VALUE);
361 : 366495 : break;
362 : : }
363 : :
364 : 1092469 : case JTOK_COLON: {
365 [ - + + - ]: 1092469 : if (!stack.size())
366 : : return false;
367 : :
368 : 1092469 : UniValue *top = stack.back();
369 [ + - ]: 1092469 : if (top->getType() != VOBJ)
370 : : return false;
371 : :
372 : 1092469 : setExpect(VALUE);
373 : 1092469 : break;
374 : : }
375 : :
376 : 2437616 : case JTOK_COMMA: {
377 [ - + ]: 2437616 : if (!stack.size() ||
378 [ + + + - ]: 2437616 : (last_tok == JTOK_COMMA) || (last_tok == JTOK_ARR_OPEN))
379 : : return false;
380 : :
381 : 2437562 : UniValue *top = stack.back();
382 [ + + ]: 2437562 : if (top->getType() == VOBJ)
383 : 1040148 : setExpect(OBJ_NAME);
384 : : else
385 : 1397414 : setExpect(ARR_VALUE);
386 : : break;
387 : : }
388 : :
389 : 22815 : case JTOK_KW_NULL:
390 : 22815 : case JTOK_KW_TRUE:
391 : 22815 : case JTOK_KW_FALSE: {
392 [ + + + ]: 22815 : UniValue tmpVal;
393 [ + + + ]: 22815 : switch (tok) {
394 : : case JTOK_KW_NULL:
395 : : // do nothing more
396 : : break;
397 : 1747 : case JTOK_KW_TRUE:
398 [ + - ]: 1747 : tmpVal.setBool(true);
399 : : break;
400 : 3504 : case JTOK_KW_FALSE:
401 [ + - ]: 3504 : tmpVal.setBool(false);
402 : : break;
403 : : default: /* impossible */ break;
404 : : }
405 : :
406 [ - + + + ]: 22815 : if (!stack.size()) {
407 [ + - ]: 602 : *this = tmpVal;
408 : : break;
409 : : }
410 : :
411 : 22213 : UniValue *top = stack.back();
412 [ + - ]: 22213 : top->values.push_back(tmpVal);
413 : :
414 : 22213 : setExpect(NOT_VALUE);
415 : 22213 : break;
416 : 22815 : }
417 : :
418 : 1947697 : case JTOK_NUMBER: {
419 [ - + ]: 3895394 : UniValue tmpVal(VNUM, tokenVal);
420 [ - + + + ]: 1947697 : if (!stack.size()) {
421 [ + - ]: 2424 : *this = tmpVal;
422 : : break;
423 : : }
424 : :
425 : 1945273 : UniValue *top = stack.back();
426 [ + - ]: 1945273 : top->values.push_back(tmpVal);
427 : :
428 : 1945273 : setExpect(NOT_VALUE);
429 : 1945273 : break;
430 : 1947697 : }
431 : :
432 : 1296097 : case JTOK_STRING: {
433 [ + + ]: 1296097 : if (expect(OBJ_NAME)) {
434 : 1092562 : UniValue *top = stack.back();
435 [ + - ]: 1092562 : top->keys.push_back(tokenVal);
436 : 1092562 : clearExpect(OBJ_NAME);
437 : 1092562 : setExpect(COLON);
438 : : } else {
439 [ - + ]: 407070 : UniValue tmpVal(VSTR, tokenVal);
440 [ - + + + ]: 203535 : if (!stack.size()) {
441 [ + - ]: 4168 : *this = tmpVal;
442 : 4168 : break;
443 : : }
444 : 199367 : UniValue *top = stack.back();
445 [ + - ]: 199367 : top->values.push_back(tmpVal);
446 : 203535 : }
447 : :
448 : 1291929 : setExpect(NOT_VALUE);
449 : 1291929 : break;
450 : : }
451 : :
452 : : default:
453 : : return false;
454 : : }
455 [ + + ]: 7557600 : } while (!stack.empty ());
456 : :
457 : : /* Check that nothing follows the initial construct (parsed above). */
458 [ + - ]: 17118 : tok = getJsonToken(tokenVal, consumed, raw, end);
459 [ + + ]: 17118 : if (tok != JTOK_NONE)
460 : 308 : return false;
461 : :
462 : : return true;
463 : 21779 : }
464 : :
|
