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    25113125 : static bool json_isdigit(int ch)
      23             : {
      24    25113125 :     return ((ch >= '0') && (ch <= '9'));
      25             : }
      26             : 
      27             : // convert hexadecimal string to unsigned integer
      28        1163 : static const char *hatoui(const char *first, const char *last,
      29             :                           unsigned int& out)
      30             : {
      31        1163 :     unsigned int result = 0;
      32        5815 :     for (; first != last; ++first)
      33             :     {
      34             :         int digit;
      35        4652 :         if (json_isdigit(*first))
      36        2792 :             digit = *first - '0';
      37             : 
      38        1860 :         else if (*first >= 'a' && *first <= 'f')
      39        1838 :             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        4652 :         result = 16 * result + digit;
      48        4652 :     }
      49        1163 :     out = result;
      50             : 
      51        1163 :     return first;
      52             : }
      53             : 
      54    21046235 : enum jtokentype getJsonToken(std::string& tokenVal, unsigned int& consumed,
      55             :                             const char *raw, const char *end)
      56             : {
      57    21046235 :     tokenVal.clear();
      58    21046235 :     consumed = 0;
      59             : 
      60    21046235 :     const char *rawStart = raw;
      61             : 
      62    26118056 :     while (raw < end && (json_isspace(*raw)))          // skip whitespace
      63     5071821 :         raw++;
      64             : 
      65    21046235 :     if (raw >= end)
      66      512825 :         return JTOK_NONE;
      67             : 
      68    20533410 :     switch (*raw) {
      69             : 
      70             :     case '{':
      71      571615 :         raw++;
      72      571615 :         consumed = (raw - rawStart);
      73      571615 :         return JTOK_OBJ_OPEN;
      74             :     case '}':
      75      571599 :         raw++;
      76      571599 :         consumed = (raw - rawStart);
      77      571599 :         return JTOK_OBJ_CLOSE;
      78             :     case '[':
      79      485260 :         raw++;
      80      485260 :         consumed = (raw - rawStart);
      81      485260 :         return JTOK_ARR_OPEN;
      82             :     case ']':
      83      484724 :         raw++;
      84      484724 :         consumed = (raw - rawStart);
      85      484724 :         return JTOK_ARR_CLOSE;
      86             : 
      87             :     case ':':
      88     2221569 :         raw++;
      89     2221569 :         consumed = (raw - rawStart);
      90     2221569 :         return JTOK_COLON;
      91             :     case ',':
      92     2841076 :         raw++;
      93     2841076 :         consumed = (raw - rawStart);
      94     2841076 :         return JTOK_COMMA;
      95             : 
      96             :     case 'n':
      97             :     case 't':
      98             :     case 'f':
      99       40237 :         if (!strncmp(raw, "null", 4)) {
     100        8192 :             raw += 4;
     101        8192 :             consumed = (raw - rawStart);
     102        8192 :             return JTOK_KW_NULL;
     103       32045 :         } else if (!strncmp(raw, "true", 4)) {
     104       20727 :             raw += 4;
     105       20727 :             consumed = (raw - rawStart);
     106       20727 :             return JTOK_KW_TRUE;
     107       11318 :         } else if (!strncmp(raw, "false", 5)) {
     108       11305 :             raw += 5;
     109       11305 :             consumed = (raw - rawStart);
     110       11305 :             return JTOK_KW_FALSE;
     111             :         } else
     112          13 :             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     8775372 :         std::string numStr;
     127             : 
     128     8775372 :         const char *first = raw;
     129             : 
     130     8775372 :         const char *firstDigit = first;
     131     8775372 :         if (!json_isdigit(*firstDigit))
     132      128000 :             firstDigit++;
     133     7203112 :         if ((*firstDigit == '0') && json_isdigit(firstDigit[1]))
     134           1 :             return JTOK_ERR;
     135             : 
     136     7203111 :         numStr += *raw;                       // copy first char
     137     7203111 :         raw++;
     138             : 
     139     7203111 :         if ((*first == '-') && (raw < end) && (!json_isdigit(*raw)))
     140           0 :             return JTOK_ERR;
     141             : 
     142    37592206 :         while (raw < end && json_isdigit(*raw)) {  // copy digits
     143    14770461 :             numStr += *raw;
     144    14770461 :             raw++;
     145             :         }
     146             : 
     147             :         // part 2: frac
     148     7203111 :         if (raw < end && *raw == '.') {
     149       72132 :             numStr += *raw;                   // copy .
     150       72132 :             raw++;
     151             : 
     152       72132 :             if (raw >= end || !json_isdigit(*raw))
     153           0 :                 return JTOK_ERR;
     154     1189615 :             while (raw < end && json_isdigit(*raw)) { // copy digits
     155      533128 :                 numStr += *raw;
     156      533128 :                 raw++;
     157             :             }
     158       72132 :         }
     159             : 
     160             :         // part 3: exp
     161     7203111 :         if (raw < end && (*raw == 'e' || *raw == 'E')) {
     162      827268 :             numStr += *raw;                   // copy E
     163       41138 :             raw++;
     164             : 
     165       41138 :             if (raw < end && (*raw == '-' || *raw == '+')) { // copy +/-
     166       41131 :                 numStr += *raw;
     167       41131 :                 raw++;
     168       41131 :             }
     169             : 
     170       41138 :             if (raw >= end || !json_isdigit(*raw))
     171           3 :                 return JTOK_ERR;
     172      220332 :             while (raw < end && json_isdigit(*raw)) { // copy digits
     173       82260 :                 numStr += *raw;
     174       82260 :                 raw++;
     175             :             }
     176       41135 :         }
     177             : 
     178     6416978 :         tokenVal = numStr;
     179     7203108 :         consumed = (raw - rawStart);
     180     7203108 :         return JTOK_NUMBER;
     181    10347632 :         }
     182             : 
     183             :     case '"': {
     184     4541938 :         raw++;                                // skip "
     185             : 
     186     4541938 :         std::string valStr;
     187     4541938 :         JSONUTF8StringFilter writer(valStr);
     188             : 
     189   308529659 :         while (true) {
     190   308529659 :             if (raw >= end || (unsigned char)*raw < 0x20)
     191           4 :                 return JTOK_ERR;
     192             : 
     193   308529655 :             else if (*raw == '\\') {
     194        1238 :                 raw++;                        // skip backslash
     195             : 
     196        1238 :                 if (raw >= end)
     197           0 :                     return JTOK_ERR;
     198             : 
     199        1238 :                 switch (*raw) {
     200          27 :                 case '"':  writer.push_back('\"'); break;
     201           7 :                 case '\\': writer.push_back('\\'); break;
     202           2 :                 case '/':  writer.push_back('/'); break;
     203           7 :                 case 'b':  writer.push_back('\b'); break;
     204           7 :                 case 'f':  writer.push_back('\f'); break;
     205           7 :                 case 'n':  writer.push_back('\n'); break;
     206           7 :                 case 'r':  writer.push_back('\r'); break;
     207           7 :                 case 't':  writer.push_back('\t'); break;
     208             : 
     209             :                 case 'u': {
     210             :                     unsigned int codepoint;
     211        2326 :                     if (raw + 1 + 4 >= end ||
     212        1163 :                         hatoui(raw + 1, raw + 1 + 4, codepoint) !=
     213        1163 :                                raw + 1 + 4)
     214           0 :                         return JTOK_ERR;
     215        1163 :                     writer.push_back_u(codepoint);
     216        1163 :                     raw += 4;
     217        1163 :                     break;
     218             :                     }
     219             :                 default:
     220           4 :                     return JTOK_ERR;
     221             : 
     222             :                 }
     223             : 
     224        1234 :                 raw++;                        // skip esc'd char
     225        1234 :             }
     226             : 
     227   308528417 :             else if (*raw == '"') {
     228     4541930 :                 raw++;                        // skip "
     229     4541930 :                 break;                        // stop scanning
     230             :             }
     231             : 
     232             :             else {
     233   303986487 :                 writer.push_back(static_cast<unsigned char>(*raw));
     234   303986487 :                 raw++;
     235             :             }
     236             :         }
     237             : 
     238     4541930 :         if (!writer.finalize())
     239           4 :             return JTOK_ERR;
     240     4541926 :         tokenVal = valStr;
     241     4541926 :         consumed = (raw - rawStart);
     242     4541926 :         return JTOK_STRING;
     243     4541938 :         }
     244             : 
     245             :     default:
     246          20 :         return JTOK_ERR;
     247             :     }
     248    22618495 : }
     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      512897 : bool UniValue::read(const char *raw, size_t size)
     263             : {
     264      512897 :     clear();
     265             : 
     266      512897 :     uint32_t expectMask = 0;
     267      512897 :     std::vector<UniValue*> stack;
     268             : 
     269      512897 :     std::string tokenVal;
     270             :     unsigned int consumed;
     271      512897 :     enum jtokentype tok = JTOK_NONE;
     272      512897 :     enum jtokentype last_tok = JTOK_NONE;
     273      512897 :     const char* end = raw + size;
     274      512897 :     do {
     275    12559004 :         last_tok = tok;
     276             : 
     277    12559004 :         tok = getJsonToken(tokenVal, consumed, raw, end);
     278    12559002 :         if (tok == JTOK_NONE || tok == JTOK_ERR)
     279          46 :             return false;
     280    12558956 :         raw += consumed;
     281             : 
     282    19734794 :         bool isValueOpen = jsonTokenIsValue(tok) ||
     283     7175838 :             tok == JTOK_OBJ_OPEN || tok == JTOK_ARR_OPEN;
     284             : 
     285    12558958 :         if (expect(VALUE)) {
     286     2221565 :             if (!isValueOpen)
     287           2 :                 return false;
     288     2221563 :             clearExpect(VALUE);
     289             : 
     290    12558956 :         } else if (expect(ARR_VALUE)) {
     291     1675444 :             bool isArrValue = isValueOpen || (tok == JTOK_ARR_CLOSE);
     292     1675444 :             if (!isArrValue)
     293           2 :                 return false;
     294             : 
     295     1675442 :             clearExpect(ARR_VALUE);
     296             : 
     297    10337391 :         } else if (expect(OBJ_NAME)) {
     298     2222479 :             bool isObjName = (tok == JTOK_OBJ_CLOSE || tok == JTOK_STRING);
     299     2222479 :             if (!isObjName)
     300           4 :                 return false;
     301             : 
     302     8661945 :         } else if (expect(COLON)) {
     303     2221569 :             if (tok != JTOK_COLON)
     304           2 :                 return false;
     305     2221567 :             clearExpect(COLON);
     306             : 
     307     6439468 :         } else if (!expect(COLON) && (tok == JTOK_COLON)) {
     308           1 :             return false;
     309             :         }
     310             : 
     311    12558947 :         if (expect(NOT_VALUE)) {
     312     5926591 :             if (isValueOpen)
     313           2 :                 return false;
     314     5926589 :             clearExpect(NOT_VALUE);
     315     5926589 :         }
     316             : 
     317    12558945 :         switch (tok) {
     318             : 
     319             :         case JTOK_OBJ_OPEN:
     320             :         case JTOK_ARR_OPEN: {
     321     1056871 :             VType utyp = (tok == JTOK_OBJ_OPEN ? VOBJ : VARR);
     322     1056871 :             if (!stack.size()) {
     323      512210 :                 if (utyp == VOBJ)
     324      511905 :                     setObject();
     325             :                 else
     326         305 :                     setArray();
     327      512210 :                 stack.push_back(this);
     328      512210 :             } else {
     329      544661 :                 UniValue tmpVal(utyp);
     330      544661 :                 UniValue *top = stack.back();
     331      544661 :                 top->values.push_back(tmpVal);
     332             : 
     333      544661 :                 UniValue *newTop = &(top->values.back());
     334      544661 :                 stack.push_back(newTop);
     335      544661 :             }
     336             : 
     337     1056871 :             if (stack.size() > MAX_JSON_DEPTH)
     338           1 :                 return false;
     339             : 
     340     1056870 :             if (utyp == VOBJ)
     341      571613 :                 setExpect(OBJ_NAME);
     342             :             else
     343      485257 :                 setExpect(ARR_VALUE);
     344     1056870 :             break;
     345             :             }
     346             : 
     347             :         case JTOK_OBJ_CLOSE:
     348             :         case JTOK_ARR_CLOSE: {
     349     1056320 :             if (!stack.size() || (last_tok == JTOK_COMMA))
     350           2 :                 return false;
     351             : 
     352     1056318 :             VType utyp = (tok == JTOK_OBJ_CLOSE ? VOBJ : VARR);
     353     1056318 :             UniValue *top = stack.back();
     354     1056318 :             if (utyp != top->getType())
     355           1 :                 return false;
     356             : 
     357     1056317 :             stack.pop_back();
     358     1056317 :             clearExpect(OBJ_NAME);
     359     1056317 :             setExpect(NOT_VALUE);
     360     1056317 :             break;
     361             :             }
     362             : 
     363             :         case JTOK_COLON: {
     364     2221567 :             if (!stack.size())
     365           0 :                 return false;
     366             : 
     367     2221567 :             UniValue *top = stack.back();
     368     2221567 :             if (top->getType() != VOBJ)
     369           0 :                 return false;
     370             : 
     371     2221567 :             setExpect(VALUE);
     372     2221567 :             break;
     373             :             }
     374             : 
     375             :         case JTOK_COMMA: {
     376     5682144 :             if (!stack.size() ||
     377     2841072 :                 (last_tok == JTOK_COMMA) || (last_tok == JTOK_ARR_OPEN))
     378           0 :                 return false;
     379             : 
     380     2841072 :             UniValue *top = stack.back();
     381     2841072 :             if (top->getType() == VOBJ)
     382     1650869 :                 setExpect(OBJ_NAME);
     383             :             else
     384     1190203 :                 setExpect(ARR_VALUE);
     385     2841072 :             break;
     386             :             }
     387             : 
     388             :         case JTOK_KW_NULL:
     389             :         case JTOK_KW_TRUE:
     390             :         case JTOK_KW_FALSE: {
     391       40221 :             UniValue tmpVal;
     392       40221 :             switch (tok) {
     393             :             case JTOK_KW_NULL:
     394             :                 // do nothing more
     395        8191 :                 break;
     396             :             case JTOK_KW_TRUE:
     397       20725 :                 tmpVal.setBool(true);
     398       20725 :                 break;
     399             :             case JTOK_KW_FALSE:
     400       11305 :                 tmpVal.setBool(false);
     401       11305 :                 break;
     402           0 :             default: /* impossible */ break;
     403             :             }
     404             : 
     405       40221 :             if (!stack.size()) {
     406         492 :                 *this = tmpVal;
     407         492 :                 break;
     408             :             }
     409             : 
     410       39729 :             UniValue *top = stack.back();
     411       39729 :             top->values.push_back(tmpVal);
     412             : 
     413       39729 :             setExpect(NOT_VALUE);
     414       39729 :             break;
     415       40221 :             }
     416             : 
     417             :         case JTOK_NUMBER: {
     418      800970 :             UniValue tmpVal(VNUM, tokenVal);
     419      800970 :             if (!stack.size()) {
     420         170 :                 *this = tmpVal;
     421         170 :                 break;
     422             :             }
     423             : 
     424      800800 :             UniValue *top = stack.back();
     425      800800 :             top->values.push_back(tmpVal);
     426             : 
     427      800800 :             setExpect(NOT_VALUE);
     428      800800 :             break;
     429      800970 :             }
     430             : 
     431             :         case JTOK_STRING: {
     432     4541924 :             if (expect(OBJ_NAME)) {
     433     2221569 :                 UniValue *top = stack.back();
     434     2221569 :                 top->keys.push_back(tokenVal);
     435     2221569 :                 clearExpect(OBJ_NAME);
     436     2221569 :                 setExpect(COLON);
     437     2221569 :             } else {
     438     2320355 :                 UniValue tmpVal(VSTR, tokenVal);
     439     2320355 :                 if (!stack.size()) {
     440           4 :                     *this = tmpVal;
     441           4 :                     break;
     442             :                 }
     443     2320351 :                 UniValue *top = stack.back();
     444     2320351 :                 top->values.push_back(tmpVal);
     445     2320355 :             }
     446             : 
     447     4541920 :             setExpect(NOT_VALUE);
     448     4541920 :             break;
     449             :             }
     450             : 
     451             :         default:
     452           0 :             return false;
     453             :         }
     454    12558941 :     } while (!stack.empty ());
     455             : 
     456             :     /* Check that nothing follows the initial construct (parsed above).  */
     457      512834 :     tok = getJsonToken(tokenVal, consumed, raw, end);
     458      512834 :     if (tok != JTOK_NONE)
     459          13 :         return false;
     460             : 
     461      512821 :     return true;
     462      512901 : }
     463             :