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 <cstdio>
       9             : #include <cstdint>
      10             : #include <cstring>
      11             : #include <string>
      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       22513 : static bool json_isdigit(int ch)
      23             : {
      24       22513 :     return ((ch >= '0') && (ch <= '9'));
      25             : }
      26             : 
      27             : // convert hexadecimal string to unsigned integer
      28          50 : static const char *hatoui(const char *first, const char *last,
      29             :                           unsigned int& out)
      30             : {
      31          50 :     unsigned int result = 0;
      32         250 :     for (; first != last; ++first)
      33             :     {
      34             :         int digit;
      35         200 :         if (json_isdigit(*first))
      36         150 :             digit = *first - '0';
      37             : 
      38          50 :         else if (*first >= 'a' && *first <= 'f')
      39          28 :             digit = *first - 'a' + 10;
      40             : 
      41          22 :         else if (*first >= 'A' && *first <= 'F')
      42          22 :             digit = *first - 'A' + 10;
      43             : 
      44             :         else
      45           0 :             break;
      46             : 
      47         200 :         result = 16 * result + digit;
      48         200 :     }
      49          50 :     out = result;
      50             : 
      51          50 :     return first;
      52             : }
      53             : 
      54       53609 : enum jtokentype getJsonToken(std::string& tokenVal, unsigned int& consumed,
      55             :                             const char *raw, const char *end)
      56             : {
      57       53609 :     tokenVal.clear();
      58       53609 :     consumed = 0;
      59             : 
      60       53609 :     const char *rawStart = raw;
      61             : 
      62       88649 :     while (raw < end && (json_isspace(*raw)))          // skip whitespace
      63       35040 :         raw++;
      64             : 
      65       53609 :     if (raw >= end)
      66         217 :         return JTOK_NONE;
      67             : 
      68       53392 :     switch (*raw) {
      69             : 
      70             :     case '{':
      71         279 :         raw++;
      72         279 :         consumed = (raw - rawStart);
      73         279 :         return JTOK_OBJ_OPEN;
      74             :     case '}':
      75         263 :         raw++;
      76         263 :         consumed = (raw - rawStart);
      77         263 :         return JTOK_OBJ_CLOSE;
      78             :     case '[':
      79        5359 :         raw++;
      80        5359 :         consumed = (raw - rawStart);
      81        5359 :         return JTOK_ARR_OPEN;
      82             :     case ']':
      83        4823 :         raw++;
      84        4823 :         consumed = (raw - rawStart);
      85        4823 :         return JTOK_ARR_CLOSE;
      86             : 
      87             :     case ':':
      88        1092 :         raw++;
      89        1092 :         consumed = (raw - rawStart);
      90        1092 :         return JTOK_COLON;
      91             :     case ',':
      92       16770 :         raw++;
      93       16770 :         consumed = (raw - rawStart);
      94       16770 :         return JTOK_COMMA;
      95             : 
      96             :     case 'n':
      97             :     case 't':
      98             :     case 'f':
      99         195 :         if (!strncmp(raw, "null", 4)) {
     100           7 :             raw += 4;
     101           7 :             consumed = (raw - rawStart);
     102           7 :             return JTOK_KW_NULL;
     103         188 :         } else if (!strncmp(raw, "true", 4)) {
     104          94 :             raw += 4;
     105          94 :             consumed = (raw - rawStart);
     106          94 :             return JTOK_KW_TRUE;
     107          94 :         } else if (!strncmp(raw, "false", 5)) {
     108          89 :             raw += 5;
     109          89 :             consumed = (raw - rawStart);
     110          89 :             return JTOK_KW_FALSE;
     111             :         } else
     112           5 :             return JTOK_ERR;
     113             : 
     114             :     case '-':
     115             :     case '0':
     116             :     case '1':
     117             :     case '2':
     118             :     case '3':
     119             :     case '4':
     120             :     case '5':
     121             :     case '6':
     122             :     case '7':
     123             :     case '8':
     124             :     case '9': {
     125             :         // part 1: int
     126        8399 :         std::string numStr;
     127             : 
     128        8399 :         const char *first = raw;
     129             : 
     130        8399 :         const char *firstDigit = first;
     131        8399 :         if (!json_isdigit(*firstDigit))
     132         766 :             firstDigit++;
     133        5061 :         if ((*firstDigit == '0') && json_isdigit(firstDigit[1]))
     134           1 :             return JTOK_ERR;
     135             : 
     136        5060 :         numStr += *raw;                       // copy first char
     137        5060 :         raw++;
     138             : 
     139        5060 :         if ((*first == '-') && (raw < end) && (!json_isdigit(*raw)))
     140           0 :             return JTOK_ERR;
     141             : 
     142       30433 :         while (raw < end && json_isdigit(*raw)) {  // copy digits
     143       11783 :             numStr += *raw;
     144       11783 :             raw++;
     145             :         }
     146             : 
     147             :         // part 2: frac
     148        5060 :         if (raw < end && *raw == '.') {
     149         227 :             numStr += *raw;                   // copy .
     150         227 :             raw++;
     151             : 
     152         227 :             if (raw >= end || !json_isdigit(*raw))
     153           0 :                 return JTOK_ERR;
     154        1941 :             while (raw < end && json_isdigit(*raw)) { // copy digits
     155         800 :                 numStr += *raw;
     156         800 :                 raw++;
     157             :             }
     158         227 :         }
     159             : 
     160             :         // part 3: exp
     161        5060 :         if (raw < end && (*raw == 'e' || *raw == 'E')) {
     162        1694 :             numStr += *raw;                   // copy E
     163          25 :             raw++;
     164             : 
     165          25 :             if (raw < end && (*raw == '-' || *raw == '+')) { // copy +/-
     166          18 :                 numStr += *raw;
     167          18 :                 raw++;
     168          18 :             }
     169             : 
     170          25 :             if (raw >= end || !json_isdigit(*raw))
     171           3 :                 return JTOK_ERR;
     172         100 :             while (raw < end && json_isdigit(*raw)) { // copy digits
     173          34 :                 numStr += *raw;
     174          34 :                 raw++;
     175             :             }
     176          22 :         }
     177             : 
     178        3388 :         tokenVal = numStr;
     179        5057 :         consumed = (raw - rawStart);
     180        5057 :         return JTOK_NUMBER;
     181       11737 :         }
     182             : 
     183             :     case '"': {
     184       16194 :         raw++;                                // skip "
     185             : 
     186       16194 :         std::string valStr;
     187       16194 :         JSONUTF8StringFilter writer(valStr);
     188             : 
     189      898806 :         while (true) {
     190      898806 :             if (raw >= end || (unsigned char)*raw < 0x20)
     191           4 :                 return JTOK_ERR;
     192             : 
     193      898802 :             else if (*raw == '\\') {
     194          81 :                 raw++;                        // skip backslash
     195             : 
     196          81 :                 if (raw >= end)
     197           0 :                     return JTOK_ERR;
     198             : 
     199          81 :                 switch (*raw) {
     200           7 :                 case '"':  writer.push_back('\"'); break;
     201           3 :                 case '\\': writer.push_back('\\'); break;
     202           2 :                 case '/':  writer.push_back('/'); break;
     203           3 :                 case 'b':  writer.push_back('\b'); break;
     204           3 :                 case 'f':  writer.push_back('\f'); break;
     205           3 :                 case 'n':  writer.push_back('\n'); break;
     206           3 :                 case 'r':  writer.push_back('\r'); break;
     207           3 :                 case 't':  writer.push_back('\t'); break;
     208             : 
     209             :                 case 'u': {
     210             :                     unsigned int codepoint;
     211         100 :                     if (raw + 1 + 4 >= end ||
     212          50 :                         hatoui(raw + 1, raw + 1 + 4, codepoint) !=
     213          50 :                                raw + 1 + 4)
     214           0 :                         return JTOK_ERR;
     215          50 :                     writer.push_back_u(codepoint);
     216          50 :                     raw += 4;
     217          50 :                     break;
     218             :                     }
     219             :                 default:
     220           4 :                     return JTOK_ERR;
     221             : 
     222             :                 }
     223             : 
     224          77 :                 raw++;                        // skip esc'd char
     225          77 :             }
     226             : 
     227      898721 :             else if (*raw == '"') {
     228       16186 :                 raw++;                        // skip "
     229       16186 :                 break;                        // stop scanning
     230             :             }
     231             : 
     232             :             else {
     233      882535 :                 writer.push_back(static_cast<unsigned char>(*raw));
     234      882535 :                 raw++;
     235             :             }
     236             :         }
     237             : 
     238       16186 :         if (!writer.finalize())
     239           4 :             return JTOK_ERR;
     240       16182 :         tokenVal = valStr;
     241       16182 :         consumed = (raw - rawStart);
     242       16182 :         return JTOK_STRING;
     243       16194 :         }
     244             : 
     245             :     default:
     246          18 :         return JTOK_ERR;
     247             :     }
     248       56947 : }
     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         279 : bool UniValue::read(const char *raw, size_t size)
     263             : {
     264         279 :     clear();
     265             : 
     266         279 :     uint32_t expectMask = 0;
     267         279 :     std::vector<UniValue*> stack;
     268             : 
     269         279 :     std::string tokenVal;
     270             :     unsigned int consumed;
     271         279 :     enum jtokentype tok = JTOK_NONE;
     272         279 :     enum jtokentype last_tok = JTOK_NONE;
     273         279 :     const char* end = raw + size;
     274         279 :     do {
     275       46687 :         last_tok = tok;
     276             : 
     277       46687 :         tok = getJsonToken(tokenVal, consumed, raw, end);
     278       46687 :         if (tok == JTOK_NONE || tok == JTOK_ERR)
     279          36 :             return false;
     280       46651 :         raw += consumed;
     281             : 
     282       75232 :         bool isValueOpen = jsonTokenIsValue(tok) ||
     283       28581 :             tok == JTOK_OBJ_OPEN || tok == JTOK_ARR_OPEN;
     284             : 
     285       46651 :         if (expect(VALUE)) {
     286        1088 :             if (!isValueOpen)
     287           2 :                 return false;
     288        1086 :             clearExpect(VALUE);
     289             : 
     290       46649 :         } else if (expect(ARR_VALUE)) {
     291       21272 :             bool isArrValue = isValueOpen || (tok == JTOK_ARR_CLOSE);
     292       21272 :             if (!isArrValue)
     293           2 :                 return false;
     294             : 
     295       21270 :             clearExpect(ARR_VALUE);
     296             : 
     297       45561 :         } else if (expect(OBJ_NAME)) {
     298        1108 :             bool isObjName = (tok == JTOK_OBJ_CLOSE || tok == JTOK_STRING);
     299        1108 :             if (!isObjName)
     300           4 :                 return false;
     301             : 
     302       24287 :         } else if (expect(COLON)) {
     303        1092 :             if (tok != JTOK_COLON)
     304           2 :                 return false;
     305        1090 :             clearExpect(COLON);
     306             : 
     307       23181 :         } else if (!expect(COLON) && (tok == JTOK_COLON)) {
     308           1 :             return false;
     309             :         }
     310             : 
     311       46640 :         if (expect(NOT_VALUE)) {
     312       22912 :             if (isValueOpen)
     313           2 :                 return false;
     314       22910 :             clearExpect(NOT_VALUE);
     315       22910 :         }
     316             : 
     317       46638 :         switch (tok) {
     318             : 
     319             :         case JTOK_OBJ_OPEN:
     320             :         case JTOK_ARR_OPEN: {
     321        5634 :             VType utyp = (tok == JTOK_OBJ_OPEN ? VOBJ : VARR);
     322        5634 :             if (!stack.size()) {
     323         224 :                 if (utyp == VOBJ)
     324          81 :                     setObject();
     325             :                 else
     326         143 :                     setArray();
     327         224 :                 stack.push_back(this);
     328         224 :             } else {
     329        5410 :                 UniValue tmpVal(utyp);
     330        5410 :                 UniValue *top = stack.back();
     331        5410 :                 top->values.push_back(tmpVal);
     332             : 
     333        5410 :                 UniValue *newTop = &(top->values.back());
     334        5410 :                 stack.push_back(newTop);
     335        5410 :             }
     336             : 
     337        5634 :             if (stack.size() > MAX_JSON_DEPTH)
     338           1 :                 return false;
     339             : 
     340        5633 :             if (utyp == VOBJ)
     341         277 :                 setExpect(OBJ_NAME);
     342             :             else
     343        5356 :                 setExpect(ARR_VALUE);
     344        5633 :             break;
     345             :             }
     346             : 
     347             :         case JTOK_OBJ_CLOSE:
     348             :         case JTOK_ARR_CLOSE: {
     349        5083 :             if (!stack.size() || (last_tok == JTOK_COMMA))
     350           2 :                 return false;
     351             : 
     352        5081 :             VType utyp = (tok == JTOK_OBJ_CLOSE ? VOBJ : VARR);
     353        5081 :             UniValue *top = stack.back();
     354        5081 :             if (utyp != top->getType())
     355           1 :                 return false;
     356             : 
     357        5080 :             stack.pop_back();
     358        5080 :             clearExpect(OBJ_NAME);
     359        5080 :             setExpect(NOT_VALUE);
     360        5080 :             break;
     361             :             }
     362             : 
     363             :         case JTOK_COLON: {
     364        1090 :             if (!stack.size())
     365           0 :                 return false;
     366             : 
     367        1090 :             UniValue *top = stack.back();
     368        1090 :             if (top->getType() != VOBJ)
     369           0 :                 return false;
     370             : 
     371        1090 :             setExpect(VALUE);
     372        1090 :             break;
     373             :             }
     374             : 
     375             :         case JTOK_COMMA: {
     376       33532 :             if (!stack.size() ||
     377       16766 :                 (last_tok == JTOK_COMMA) || (last_tok == JTOK_ARR_OPEN))
     378           0 :                 return false;
     379             : 
     380       16766 :             UniValue *top = stack.back();
     381       16766 :             if (top->getType() == VOBJ)
     382         834 :                 setExpect(OBJ_NAME);
     383             :             else
     384       15932 :                 setExpect(ARR_VALUE);
     385       16766 :             break;
     386             :             }
     387             : 
     388             :         case JTOK_KW_NULL:
     389             :         case JTOK_KW_TRUE:
     390             :         case JTOK_KW_FALSE: {
     391         187 :             UniValue tmpVal;
     392         187 :             switch (tok) {
     393             :             case JTOK_KW_NULL:
     394             :                 // do nothing more
     395           6 :                 break;
     396             :             case JTOK_KW_TRUE:
     397          92 :                 tmpVal.setBool(true);
     398          92 :                 break;
     399             :             case JTOK_KW_FALSE:
     400          89 :                 tmpVal.setBool(false);
     401          89 :                 break;
     402           0 :             default: /* impossible */ break;
     403             :             }
     404             : 
     405         187 :             if (!stack.size()) {
     406          16 :                 *this = tmpVal;
     407          16 :                 break;
     408             :             }
     409             : 
     410         171 :             UniValue *top = stack.back();
     411         171 :             top->values.push_back(tmpVal);
     412             : 
     413         171 :             setExpect(NOT_VALUE);
     414         171 :             break;
     415         187 :             }
     416             : 
     417             :         case JTOK_NUMBER: {
     418        1698 :             UniValue tmpVal(VNUM, tokenVal);
     419        1698 :             if (!stack.size()) {
     420          26 :                 *this = tmpVal;
     421          26 :                 break;
     422             :             }
     423             : 
     424        1672 :             UniValue *top = stack.back();
     425        1672 :             top->values.push_back(tmpVal);
     426             : 
     427        1672 :             setExpect(NOT_VALUE);
     428        1672 :             break;
     429        1698 :             }
     430             : 
     431             :         case JTOK_STRING: {
     432       16180 :             if (expect(OBJ_NAME)) {
     433        1092 :                 UniValue *top = stack.back();
     434        1092 :                 top->keys.push_back(tokenVal);
     435        1092 :                 clearExpect(OBJ_NAME);
     436        1092 :                 setExpect(COLON);
     437        1092 :             } else {
     438       15088 :                 UniValue tmpVal(VSTR, tokenVal);
     439       15088 :                 if (!stack.size()) {
     440           2 :                     *this = tmpVal;
     441           2 :                     break;
     442             :                 }
     443       15086 :                 UniValue *top = stack.back();
     444       15086 :                 top->values.push_back(tmpVal);
     445       15088 :             }
     446             : 
     447       16178 :             setExpect(NOT_VALUE);
     448       16178 :             break;
     449             :             }
     450             : 
     451             :         default:
     452           0 :             return false;
     453             :         }
     454       46634 :     } while (!stack.empty ());
     455             : 
     456             :     /* Check that nothing follows the initial construct (parsed above).  */
     457         226 :     tok = getJsonToken(tokenVal, consumed, raw, end);
     458         226 :     if (tok != JTOK_NONE)
     459          13 :         return false;
     460             : 
     461         213 :     return true;
     462         279 : }
     463             :