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                 :   16249820 : static bool json_isdigit(int ch)
      24                 :            : {
      25         [ +  + ]:   16249820 :     return ((ch >= '0') && (ch <= '9'));
      26                 :            : }
      27                 :            : 
      28                 :            : // convert hexadecimal string to unsigned integer
      29                 :      12453 : static const char *hatoui(const char *first, const char *last,
      30                 :            :                           unsigned int& out)
      31                 :            : {
      32                 :      12453 :     unsigned int result = 0;
      33         [ +  + ]:      62197 :     for (; first != last; ++first)
      34                 :            :     {
      35                 :            :         int digit;
      36         [ +  + ]:      49776 :         if (json_isdigit(*first))
      37                 :      30677 :             digit = *first - '0';
      38                 :            : 
      39   [ +  +  +  + ]:      19099 :         else if (*first >= 'a' && *first <= 'f')
      40                 :      10384 :             digit = *first - 'a' + 10;
      41                 :            : 
      42   [ +  +  +  + ]:       8715 :         else if (*first >= 'A' && *first <= 'F')
      43                 :       8683 :             digit = *first - 'A' + 10;
      44                 :            : 
      45                 :            :         else
      46                 :         32 :             break;
      47                 :            : 
      48                 :      49744 :         result = 16 * result + digit;
      49                 :      49744 :     }
      50                 :      12453 :     out = result;
      51                 :            : 
      52                 :      12453 :     return first;
      53                 :            : }
      54                 :            : 
      55                 :    4716631 : enum jtokentype getJsonToken(std::string& tokenVal, unsigned int& consumed,
      56                 :            :                             const char *raw, const char *end)
      57                 :            : {
      58                 :    4716631 :     tokenVal.clear();
      59                 :    4716631 :     consumed = 0;
      60                 :            : 
      61                 :    4716631 :     const char *rawStart = raw;
      62                 :            : 
      63   [ +  +  +  + ]:    5397959 :     while (raw < end && (json_isspace(*raw)))          // skip whitespace
      64                 :     681328 :         raw++;
      65                 :            : 
      66         [ +  + ]:    4716631 :     if (raw >= end)
      67                 :       4864 :         return JTOK_NONE;
      68                 :            : 
      69   [ +  +  +  +  :    4711767 :     switch (*raw) {
          +  +  +  +  +  
                      + ]
      70                 :            : 
      71                 :            :     case '{':
      72                 :      14238 :         raw++;
      73                 :      14238 :         consumed = (raw - rawStart);
      74                 :      14238 :         return JTOK_OBJ_OPEN;
      75                 :            :     case '}':
      76                 :      12037 :         raw++;
      77                 :      12037 :         consumed = (raw - rawStart);
      78                 :      12037 :         return JTOK_OBJ_CLOSE;
      79                 :            :     case '[':
      80                 :      80255 :         raw++;
      81                 :      80255 :         consumed = (raw - rawStart);
      82                 :      80255 :         return JTOK_ARR_OPEN;
      83                 :            :     case ']':
      84                 :      75779 :         raw++;
      85                 :      75779 :         consumed = (raw - rawStart);
      86                 :      75779 :         return JTOK_ARR_CLOSE;
      87                 :            : 
      88                 :            :     case ':':
      89                 :     341005 :         raw++;
      90                 :     341005 :         consumed = (raw - rawStart);
      91                 :     341005 :         return JTOK_COLON;
      92                 :            :     case ',':
      93                 :     498911 :         raw++;
      94                 :     498911 :         consumed = (raw - rawStart);
      95                 :     498911 :         return JTOK_COMMA;
      96                 :            : 
      97                 :            :     case 'n':
      98                 :            :     case 't':
      99                 :            :     case 'f':
     100         [ +  + ]:       4879 :         if (!strncmp(raw, "null", 4)) {
     101                 :       2141 :             raw += 4;
     102                 :       2141 :             consumed = (raw - rawStart);
     103                 :       2141 :             return JTOK_KW_NULL;
     104         [ +  + ]:       2738 :         } else if (!strncmp(raw, "true", 4)) {
     105                 :        758 :             raw += 4;
     106                 :        758 :             consumed = (raw - rawStart);
     107                 :        758 :             return JTOK_KW_TRUE;
     108         [ +  + ]:       1980 :         } else if (!strncmp(raw, "false", 5)) {
     109                 :       1925 :             raw += 5;
     110                 :       1925 :             consumed = (raw - rawStart);
     111                 :       1925 :             return JTOK_KW_FALSE;
     112                 :            :         } else
     113                 :         55 :             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                 :    3110446 :         std::string numStr;
     128                 :            : 
     129                 :    3110446 :         const char *first = raw;
     130                 :            : 
     131                 :    3110446 :         const char *firstDigit = first;
     132   [ +  +  +  + ]:    3110446 :         if (!json_isdigit(*firstDigit))
     133                 :      54434 :             firstDigit++;
     134   [ +  +  +  -  :    2725578 :         if ((*firstDigit == '0') && json_isdigit(firstDigit[1]))
                   +  + ]
     135                 :         21 :             return JTOK_ERR;
     136                 :            : 
     137         [ +  - ]:    2725557 :         numStr += *raw;                       // copy first char
     138                 :    2725557 :         raw++;
     139                 :            : 
     140   [ +  +  +  +  :    2725557 :         if ((*first == '-') && (raw < end) && (!json_isdigit(*raw)))
             +  -  +  + ]
     141                 :          1 :             return JTOK_ERR;
     142                 :            : 
     143   [ +  +  +  -  :   29129504 :         while (raw < end && json_isdigit(*raw)) {  // copy digits
                   +  + ]
     144         [ +  - ]:   13105541 :             numStr += *raw;
     145                 :   13105541 :             raw++;
     146                 :            :         }
     147                 :            : 
     148                 :            :         // part 2: frac
     149   [ +  +  +  + ]:    2725556 :         if (raw < end && *raw == '.') {
     150         [ +  - ]:      16132 :             numStr += *raw;                   // copy .
     151                 :      16132 :             raw++;
     152                 :            : 
     153   [ +  -  +  -  :      16132 :             if (raw >= end || !json_isdigit(*raw))
                   -  + ]
     154                 :          0 :                 return JTOK_ERR;
     155   [ +  +  +  -  :     100452 :             while (raw < end && json_isdigit(*raw)) { // copy digits
                   +  + ]
     156         [ +  - ]:      34156 :                 numStr += *raw;
     157                 :      34156 :                 raw++;
     158                 :            :             }
     159                 :      16132 :         }
     160                 :            : 
     161                 :            :         // part 3: exp
     162   [ +  +  +  + ]:    2725556 :         if (raw < end && (*raw == 'e' || *raw == 'E')) {
     163         [ +  + ]:     192742 :             numStr += *raw;                   // copy E
     164                 :        308 :             raw++;
     165                 :            : 
     166   [ +  +  +  +  :        308 :             if (raw < end && (*raw == '-' || *raw == '+')) { // copy +/-
                   +  + ]
     167         [ +  - ]:        101 :                 numStr += *raw;
     168                 :        101 :                 raw++;
     169                 :        101 :             }
     170                 :            : 
     171   [ +  +  +  -  :        308 :             if (raw >= end || !json_isdigit(*raw))
                   +  + ]
     172                 :          5 :                 return JTOK_ERR;
     173   [ +  +  +  -  :       4798 :             while (raw < end && json_isdigit(*raw)) { // copy digits
                   +  + ]
     174         [ +  - ]:       2123 :                 numStr += *raw;
     175                 :       2123 :                 raw++;
     176                 :            :             }
     177                 :        303 :         }
     178                 :            : 
     179         [ +  + ]:    2533117 :         tokenVal = numStr;
     180                 :    2725551 :         consumed = (raw - rawStart);
     181                 :    2725551 :         return JTOK_NUMBER;
     182                 :    3495314 :         }
     183                 :            : 
     184                 :            :     case '"': {
     185                 :     573830 :         raw++;                                // skip "
     186                 :            : 
     187                 :     573830 :         std::string valStr;
     188         [ +  - ]:     573830 :         JSONUTF8StringFilter writer(valStr);
     189                 :            : 
     190                 :   23918363 :         while (true) {
     191   [ +  +  +  + ]:   23918363 :             if (raw >= end || (unsigned char)*raw < 0x20)
     192                 :        307 :                 return JTOK_ERR;
     193                 :            : 
     194         [ +  + ]:   23918056 :             else if (*raw == '\\') {
     195                 :      15220 :                 raw++;                        // skip backslash
     196                 :            : 
     197         [ +  + ]:      15220 :                 if (raw >= end)
     198                 :          2 :                     return JTOK_ERR;
     199                 :            : 
     200   [ +  +  +  +  :      15218 :                 switch (*raw) {
          +  +  +  +  +  
                      + ]
     201         [ +  - ]:        542 :                 case '"':  writer.push_back('\"'); break;
     202         [ +  - ]:       1587 :                 case '\\': writer.push_back('\\'); break;
     203         [ +  - ]:         57 :                 case '/':  writer.push_back('/'); break;
     204         [ +  - ]:         89 :                 case 'b':  writer.push_back('\b'); break;
     205         [ +  - ]:        338 :                 case 'f':  writer.push_back('\f'); break;
     206         [ +  - ]:         36 :                 case 'n':  writer.push_back('\n'); break;
     207         [ +  - ]:          2 :                 case 'r':  writer.push_back('\r'); break;
     208         [ +  - ]:        103 :                 case 't':  writer.push_back('\t'); break;
     209                 :            : 
     210                 :            :                 case 'u': {
     211                 :            :                     unsigned int codepoint;
     212   [ +  +  +  + ]:      24912 :                     if (raw + 1 + 4 >= end ||
     213         [ +  - ]:      12453 :                         hatoui(raw + 1, raw + 1 + 4, codepoint) !=
     214                 :      12453 :                                raw + 1 + 4)
     215                 :         38 :                         return JTOK_ERR;
     216         [ +  - ]:      12421 :                     writer.push_back_u(codepoint);
     217                 :      12421 :                     raw += 4;
     218                 :      12421 :                     break;
     219                 :            :                     }
     220                 :            :                 default:
     221                 :          5 :                     return JTOK_ERR;
     222                 :            : 
     223                 :            :                 }
     224                 :            : 
     225                 :      15175 :                 raw++;                        // skip esc'd char
     226                 :      15175 :             }
     227                 :            : 
     228         [ +  + ]:   23902836 :             else if (*raw == '"') {
     229                 :     573478 :                 raw++;                        // skip "
     230                 :     573478 :                 break;                        // stop scanning
     231                 :            :             }
     232                 :            : 
     233                 :            :             else {
     234         [ +  - ]:   23329358 :                 writer.push_back(static_cast<unsigned char>(*raw));
     235                 :   23329358 :                 raw++;
     236                 :            :             }
     237                 :            :         }
     238                 :            : 
     239   [ +  -  +  + ]:     573478 :         if (!writer.finalize())
     240                 :        103 :             return JTOK_ERR;
     241         [ +  - ]:     573375 :         tokenVal = valStr;
     242                 :     573375 :         consumed = (raw - rawStart);
     243                 :     573375 :         return JTOK_STRING;
     244                 :     573830 :         }
     245                 :            : 
     246                 :            :     default:
     247                 :        387 :         return JTOK_ERR;
     248                 :            :     }
     249                 :    5101499 : }
     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                 :       5883 : bool UniValue::read(std::string_view str_in)
     264                 :            : {
     265                 :       5883 :     clear();
     266                 :            : 
     267                 :       5883 :     uint32_t expectMask = 0;
     268                 :       5883 :     std::vector<UniValue*> stack;
     269                 :            : 
     270                 :       5883 :     std::string tokenVal;
     271                 :            :     unsigned int consumed;
     272                 :       5883 :     enum jtokentype tok = JTOK_NONE;
     273                 :       5883 :     enum jtokentype last_tok = JTOK_NONE;
     274                 :       5883 :     const char* raw{str_in.data()};
     275                 :       5883 :     const char* end{raw + str_in.size()};
     276                 :       5883 :     do {
     277                 :    1795112 :         last_tok = tok;
     278                 :            : 
     279         [ +  - ]:    1795112 :         tok = getJsonToken(tokenVal, consumed, raw, end);
     280   [ +  +  +  + ]:    1795112 :         if (tok == JTOK_NONE || tok == JTOK_ERR)
     281                 :       1590 :             return false;
     282                 :    1793522 :         raw += consumed;
     283                 :            : 
     284   [ +  -  +  + ]:    2815740 :         bool isValueOpen = jsonTokenIsValue(tok) ||
     285         [ +  + ]:    1022218 :             tok == JTOK_OBJ_OPEN || tok == JTOK_ARR_OPEN;
     286                 :            : 
     287         [ +  + ]:    1793522 :         if (expect(VALUE)) {
     288         [ +  + ]:     340977 :             if (!isValueOpen)
     289                 :          6 :                 return false;
     290                 :     340971 :             clearExpect(VALUE);
     291                 :            : 
     292         [ +  + ]:    1793516 :         } else if (expect(ARR_VALUE)) {
     293         [ +  + ]:     251804 :             bool isArrValue = isValueOpen || (tok == JTOK_ARR_CLOSE);
     294         [ +  + ]:     251804 :             if (!isArrValue)
     295                 :          7 :                 return false;
     296                 :            : 
     297                 :     251797 :             clearExpect(ARR_VALUE);
     298                 :            : 
     299         [ +  + ]:    1452538 :         } else if (expect(OBJ_NAME)) {
     300         [ +  + ]:     341305 :             bool isObjName = (tok == JTOK_OBJ_CLOSE || tok == JTOK_STRING);
     301         [ +  + ]:     341305 :             if (!isObjName)
     302                 :          6 :                 return false;
     303                 :            : 
     304         [ +  + ]:    1200735 :         } else if (expect(COLON)) {
     305         [ +  + ]:     341009 :             if (tok != JTOK_COLON)
     306                 :         16 :                 return false;
     307                 :     340993 :             clearExpect(COLON);
     308                 :            : 
     309   [ +  -  +  + ]:     859420 :         } else if (!expect(COLON) && (tok == JTOK_COLON)) {
     310                 :          8 :             return false;
     311                 :            :         }
     312                 :            : 
     313         [ +  + ]:    1793479 :         if (expect(NOT_VALUE)) {
     314         [ +  + ]:     854746 :             if (isValueOpen)
     315                 :         20 :                 return false;
     316                 :     854726 :             clearExpect(NOT_VALUE);
     317                 :     854726 :         }
     318                 :            : 
     319   [ +  +  +  +  :    1793459 :         switch (tok) {
             +  +  +  - ]
     320                 :            : 
     321                 :            :         case JTOK_OBJ_OPEN:
     322                 :            :         case JTOK_ARR_OPEN: {
     323                 :      94478 :             VType utyp = (tok == JTOK_OBJ_OPEN ? VOBJ : VARR);
     324         [ +  + ]:      94478 :             if (!stack.size()) {
     325         [ +  + ]:       2966 :                 if (utyp == VOBJ)
     326         [ +  - ]:       1242 :                     setObject();
     327                 :            :                 else
     328         [ +  - ]:       1724 :                     setArray();
     329         [ +  - ]:       2966 :                 stack.push_back(this);
     330                 :       2966 :             } else {
     331         [ -  + ]:      91512 :                 UniValue tmpVal(utyp);
     332                 :      91512 :                 UniValue *top = stack.back();
     333         [ +  - ]:      91512 :                 top->values.push_back(tmpVal);
     334                 :            : 
     335                 :      91512 :                 UniValue *newTop = &(top->values.back());
     336         [ +  - ]:      91512 :                 stack.push_back(newTop);
     337                 :      91512 :             }
     338                 :            : 
     339         [ +  + ]:      94478 :             if (stack.size() > MAX_JSON_DEPTH)
     340                 :          3 :                 return false;
     341                 :            : 
     342         [ +  + ]:      94475 :             if (utyp == VOBJ)
     343                 :      14230 :                 setExpect(OBJ_NAME);
     344                 :            :             else
     345                 :      80245 :                 setExpect(ARR_VALUE);
     346                 :      94475 :             break;
     347                 :            :             }
     348                 :            : 
     349                 :            :         case JTOK_OBJ_CLOSE:
     350                 :            :         case JTOK_ARR_CLOSE: {
     351   [ +  +  +  + ]:      87805 :             if (!stack.size() || (last_tok == JTOK_COMMA))
     352                 :         10 :                 return false;
     353                 :            : 
     354                 :      87795 :             VType utyp = (tok == JTOK_OBJ_CLOSE ? VOBJ : VARR);
     355                 :      87795 :             UniValue *top = stack.back();
     356   [ +  -  +  + ]:      87795 :             if (utyp != top->getType())
     357                 :          6 :                 return false;
     358                 :            : 
     359                 :      87789 :             stack.pop_back();
     360                 :      87789 :             clearExpect(OBJ_NAME);
     361                 :      87789 :             setExpect(NOT_VALUE);
     362                 :      87789 :             break;
     363                 :            :             }
     364                 :            : 
     365                 :            :         case JTOK_COLON: {
     366         [ -  + ]:     340993 :             if (!stack.size())
     367                 :          0 :                 return false;
     368                 :            : 
     369                 :     340993 :             UniValue *top = stack.back();
     370   [ +  -  +  - ]:     340993 :             if (top->getType() != VOBJ)
     371                 :          0 :                 return false;
     372                 :            : 
     373                 :     340993 :             setExpect(VALUE);
     374                 :     340993 :             break;
     375                 :            :             }
     376                 :            : 
     377                 :            :         case JTOK_COMMA: {
     378   [ +  +  +  - ]:     997792 :             if (!stack.size() ||
     379         [ +  - ]:     498893 :                 (last_tok == JTOK_COMMA) || (last_tok == JTOK_ARR_OPEN))
     380                 :          6 :                 return false;
     381                 :            : 
     382                 :     498893 :             UniValue *top = stack.back();
     383   [ +  -  +  + ]:     498893 :             if (top->getType() == VOBJ)
     384                 :     327194 :                 setExpect(OBJ_NAME);
     385                 :            :             else
     386                 :     171699 :                 setExpect(ARR_VALUE);
     387                 :     498893 :             break;
     388                 :            :             }
     389                 :            : 
     390                 :            :         case JTOK_KW_NULL:
     391                 :            :         case JTOK_KW_TRUE:
     392                 :            :         case JTOK_KW_FALSE: {
     393         [ +  - ]:       4824 :             UniValue tmpVal;
     394   [ +  +  -  + ]:       4824 :             switch (tok) {
     395                 :            :             case JTOK_KW_NULL:
     396                 :            :                 // do nothing more
     397                 :       2141 :                 break;
     398                 :            :             case JTOK_KW_TRUE:
     399         [ +  - ]:        758 :                 tmpVal.setBool(true);
     400                 :        758 :                 break;
     401                 :            :             case JTOK_KW_FALSE:
     402         [ +  - ]:       1925 :                 tmpVal.setBool(false);
     403                 :       1925 :                 break;
     404                 :          0 :             default: /* impossible */ break;
     405                 :            :             }
     406                 :            : 
     407         [ +  + ]:       4824 :             if (!stack.size()) {
     408         [ +  - ]:        211 :                 *this = tmpVal;
     409                 :        211 :                 break;
     410                 :            :             }
     411                 :            : 
     412                 :       4613 :             UniValue *top = stack.back();
     413         [ +  - ]:       4613 :             top->values.push_back(tmpVal);
     414                 :            : 
     415                 :       4613 :             setExpect(NOT_VALUE);
     416                 :       4613 :             break;
     417                 :       4824 :             }
     418                 :            : 
     419                 :            :         case JTOK_NUMBER: {
     420   [ +  -  +  - ]:     193093 :             UniValue tmpVal(VNUM, tokenVal);
     421         [ +  + ]:     193093 :             if (!stack.size()) {
     422         [ +  - ]:        467 :                 *this = tmpVal;
     423                 :        467 :                 break;
     424                 :            :             }
     425                 :            : 
     426                 :     192626 :             UniValue *top = stack.back();
     427         [ +  - ]:     192626 :             top->values.push_back(tmpVal);
     428                 :            : 
     429                 :     192626 :             setExpect(NOT_VALUE);
     430                 :     192626 :             break;
     431                 :     193093 :             }
     432                 :            : 
     433                 :            :         case JTOK_STRING: {
     434         [ +  + ]:     573367 :             if (expect(OBJ_NAME)) {
     435                 :     341026 :                 UniValue *top = stack.back();
     436         [ +  - ]:     341026 :                 top->keys.push_back(tokenVal);
     437                 :     341026 :                 clearExpect(OBJ_NAME);
     438                 :     341026 :                 setExpect(COLON);
     439                 :     341026 :             } else {
     440   [ +  -  -  + ]:     232341 :                 UniValue tmpVal(VSTR, tokenVal);
     441         [ +  + ]:     232341 :                 if (!stack.size()) {
     442         [ +  - ]:       1011 :                     *this = tmpVal;
     443                 :       1011 :                     break;
     444                 :            :                 }
     445                 :     231330 :                 UniValue *top = stack.back();
     446         [ +  - ]:     231330 :                 top->values.push_back(tmpVal);
     447      [ -  +  + ]:     232341 :             }
     448                 :            : 
     449                 :     572356 :             setExpect(NOT_VALUE);
     450                 :     572356 :             break;
     451                 :            :             }
     452                 :            : 
     453                 :            :         default:
     454                 :          0 :             return false;
     455                 :            :         }
     456         [ +  + ]:    1793434 :     } while (!stack.empty ());
     457                 :            : 
     458                 :            :     /* Check that nothing follows the initial construct (parsed above).  */
     459         [ +  - ]:       4205 :     tok = getJsonToken(tokenVal, consumed, raw, end);
     460         [ +  + ]:       4205 :     if (tok != JTOK_NONE)
     461                 :         70 :         return false;
     462                 :            : 
     463                 :       4135 :     return true;
     464                 :       5883 : }
     465                 :            :