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