ucw-json/parse.c

   1 /*
   2  *      UCW JSON Library -- Parser
   3  *
   4  *      (c) 2015 Martin Mares <mj@ucw.cz>
   5  *
   6  *      This software may be freely distributed and used according to the terms
   7  *      of the GNU Lesser General Public License.
   8  */
   9
  10 #include <ucw/lib.h>
  11 #include <ucw/fastbuf.h>
  12 #include <ucw/ff-unicode.h>
  13 #include <ucw/trans.h>
  14 #include <ucw/unicode.h>
  15 #include <ucw-json/json.h>
  16
  17 #include <errno.h>
  18 #include <stdlib.h>
  19
  20 void json_set_input(struct json_context *js, struct fastbuf *in)
  21 {
  22   js->in_fb = in;
  23   js->in_line = 1;
  24   js->in_column = 0;
  25   js->next_char = -1;
  26   js->next_token = NULL;
  27   js->in_eof = 0;
  28   if (!js->trivial_token)
  29     js->trivial_token = json_new_node(js, JSON_INVALID);
  30 }
  31
  32 static void NONRET json_parse_error(struct json_context *js, const char *msg)
  33 {
  34   trans_throw("ucw.js.parse", js, "%s at line %u:%u", msg, js->in_line, js->in_column);
  35 }
  36
  37 static int json_get_char(struct json_context *js)
  38 {
  39   int c = bget_utf8_32_repl(js->in_fb, -2);
  40   if (unlikely(c < 0))
  41     {
  42       if (c == -2)
  43         json_parse_error(js, "Malformed UTF-8 character");
  44       js->in_eof = 1;
  45       // FIXME: Reject alternative sequences
  46       return c;
  47     }
  48   js->in_column++;
  49   return c;
  50 }
  51
  52 static void json_unget_char(struct json_context *js, int c)
  53 {
  54   js->next_char = c;
  55 }
  56
  57 static struct json_node *json_triv_token(struct json_context *js, enum json_node_type type)
  58 {
  59   js->trivial_token->type = type;
  60   return js->trivial_token;
  61 }
  62
  63 static struct json_node *json_parse_number(struct json_context *js, int c)
  64 {
  65   mp_push(js->pool);
  66   char *p = mp_start_noalign(js->pool, 0);
  67
  68   // Optional minus
  69   if (c == '-')
  70     {
  71       p = mp_append_char(js->pool, p, c);
  72       c = json_get_char(js);
  73       if (!(c >= '0' && c <= '9'))
  74         json_parse_error(js, "Malformed number: just minus");
  75     }
  76
  77   // Integer part
  78   if (c == '0')
  79     {
  80       // Leading zeroes are forbidden by RFC 7159
  81       p = mp_append_char(js->pool, p, c);
  82       c = json_get_char(js);
  83       if (c >= '0' && c <= '9')
  84         json_parse_error(js, "Malformed number: leading zero");
  85     }
  86   else
  87     {
  88       while (c >= '0' && c <= '9')
  89         {
  90           p = mp_append_char(js->pool, p, c);
  91           c = json_get_char(js);
  92         }
  93     }
  94
  95   // Fractional part
  96   if (c == '.')
  97     {
  98       p = mp_append_char(js->pool, p, c);
  99       c = json_get_char(js);
 100       if (!(c >= '0' && c <= '9'))
 101         json_parse_error(js, "Malformed number: no digits after decimal point");
 102       while (c >= '0' && c <= '9')
 103         {
 104           p = mp_append_char(js->pool, p, c);
 105           c = json_get_char(js);
 106         }
 107     }
 108
 109   // Exponent
 110   if (c == 'e' || c == 'E')
 111     {
 112       p = mp_append_char(js->pool, p, c);
 113       c = json_get_char(js);
 114       if (c == '+' || c == '-')
 115         {
 116           p = mp_append_char(js->pool, p, c);
 117           c = json_get_char(js);
 118         }
 119       if (!(c >= '0' && c <= '9'))
 120         json_parse_error(js, "Malformed number: empty exponent");
 121       while (c >= '0' && c <= '9')
 122         {
 123           p = mp_append_char(js->pool, p, c);
 124           c = json_get_char(js);
 125         }
 126     }
 127
 128   json_unget_char(js, c);
 129
 130   p = mp_end_string(js->pool, p);
 131   errno = 0;
 132   double val = strtod(p, NULL);
 133   if (errno == ERANGE)
 134     json_parse_error(js, "Number out of range");
 135   mp_pop(js->pool);
 136
 137   return json_new_number(js, val);
 138 }
 139
 140 static struct json_node *json_parse_name(struct json_context *js, int c)
 141 {
 142   char name[16];
 143   uint i = 0;
 144
 145   while (c >= 'a' && c <= 'z')
 146     {
 147       if (i < sizeof(name) - 1)
 148         name[i++] = c;
 149       c = json_get_char(js);
 150     }
 151   if (i >= sizeof(name) - 1)
 152     json_parse_error(js, "Invalid literal name");
 153   name[i] = 0;
 154   json_unget_char(js, c);
 155
 156   struct json_node *n;
 157   if (!strcmp(name, "null"))
 158     n = json_new_null(js);
 159   else if (!strcmp(name, "false"))
 160     n = json_new_bool(js, 0);
 161   else if (!strcmp(name, "true"))
 162     n = json_new_bool(js, 1);
 163   else
 164     json_parse_error(js, "Invalid literal name");
 165
 166   return n;
 167 }
 168
 169 static uint json_parse_hex4(struct json_context *js)
 170 {
 171   uint x = 0;
 172   for (int i=0; i<4; i++)
 173     {
 174       x = x << 4;
 175       int c = json_get_char(js);
 176       if (c >= '0' && c <= '9')
 177         x += c - '0';
 178       else if (c >= 'a' && c <= 'f')
 179         x += c - 'a' + 10;
 180       else if (c >= 'A' && c <= 'F')
 181         x += c - 'A' + 10;
 182       else
 183         json_parse_error(js, "Invalid Unicode escape sequence");
 184     }
 185   return x;
 186 }
 187
 188 static struct json_node *json_parse_string(struct json_context *js, int c)
 189 {
 190   char *p = mp_start_noalign(js->pool, 0);
 191
 192   c = json_get_char(js);
 193   while (c != '"')
 194     {
 195       if (unlikely(c < 0x20))
 196         {
 197           if (c < 0 || c == 0x0d || c == 0x0a)
 198             json_parse_error(js, "Unterminated string");
 199           else
 200             json_parse_error(js, "Invalid control character in string");
 201         }
 202       if (unlikely(c >= 0xd800 && c < 0xf900))
 203         {
 204           if (c < 0xe000)
 205             json_parse_error(js, "Invalid surrogate character in string");
 206           else
 207             json_parse_error(js, "Invalid private-use character in string");
 208         }
 209       if (unlikely(c >= 0xf0000))
 210         {
 211           if (c > 0x10ffff)
 212             json_parse_error(js, "Invalid non-Unicode character in string");
 213           else
 214             json_parse_error(js, "Invalid private-use character in string");
 215         }
 216       if (c == '\\')
 217         {
 218           c = json_get_char(js);
 219           switch (c)
 220             {
 221             case '"':
 222             case '\\':
 223             case '/':
 224               break;
 225             case 'b':
 226               c = 0x08;
 227               break;
 228             case 'f':
 229               c = 0x0c;
 230               break;
 231             case 'n':
 232               c = 0x0a;
 233               break;
 234             case 'r':
 235               c = 0x0d;
 236               break;
 237             case 't':
 238               c = 0x09;
 239               break;
 240             case 'u':
 241               {
 242                 uint x = json_parse_hex4(js);
 243                 if (!x)
 244                   json_parse_error(js, "Zero bytes in strings are not supported");
 245                 if (x >= 0xd800 && x < 0xf900)
 246                   {
 247                     if (x < 0xdc00)
 248                       {
 249                         // High surrogate: low surrogate must follow
 250                         uint y = 0;
 251                         if (json_get_char(js) == '\\' && json_get_char(js) == 'u')
 252                           y = json_parse_hex4(js);
 253                         if (!(y >= 0xdc00 && y < 0xe000))
 254                           json_parse_error(js, "Escaped high surrogate codepoint must be followed by a low surrogate codepoint");
 255                         c = 0x10000 + ((x & 0x03ff) << 10) | (y & 0x03ff);
 256                         if (c > 0xf0000)
 257                           json_parse_error(js, "Invalid escaped private-use character");
 258                       }
 259                     else if (x < 0xe000)
 260                       {
 261                         // Low surrogate
 262                         json_parse_error(js, "Invalid escaped surrogate codepoint");
 263                       }
 264                     else
 265                       json_parse_error(js, "Invalid escaped private-use character");
 266                   }
 267                 else
 268                   c = x;
 269                 break;
 270               }
 271             default:
 272               json_parse_error(js, "Invalid backslash sequence in string");
 273             }
 274         }
 275       p = mp_append_utf8_32(js->pool, p, c);
 276       c = json_get_char(js);
 277     }
 278
 279   p = mp_end_string(js->pool, p);
 280   return json_new_string_ref(js, p);
 281 }
 282
 283 static struct json_node *json_read_token(struct json_context *js)
 284 {
 285   if (unlikely(js->in_eof))
 286     return json_triv_token(js, JSON_EOF);
 287
 288   int c = js->next_char;
 289   if (c >= 0)
 290     js->next_char = -1;
 291   else
 292     c = json_get_char(js);
 293
 294   while (c == 0x20 || c == 0x09 || c == 0x0a || c == 0x0d)
 295     {
 296       if (c == 0x0a)
 297         {
 298           js->in_line++;
 299           js->in_column = 0;
 300         }
 301       c = json_get_char(js);
 302     }
 303   if (c < 0)
 304     return json_triv_token(js, JSON_EOF);
 305
 306   if (c >= '0' && c <= '9' || c == '-')
 307     return json_parse_number(js, c);
 308
 309   if (c >= 'a' && c <= 'z')
 310     return json_parse_name(js, c);
 311
 312   if (c == '"')
 313     return json_parse_string(js, c);
 314
 315   switch (c)
 316     {
 317     case '[':
 318       return json_triv_token(js, JSON_BEGIN_ARRAY);
 319     case ']':
 320       return json_triv_token(js, JSON_END_ARRAY);
 321     case '{':
 322       return json_triv_token(js, JSON_BEGIN_OBJECT);
 323     case '}':
 324       return json_triv_token(js, JSON_END_OBJECT);
 325     case ':':
 326       return json_triv_token(js, JSON_NAME_SEP);
 327     case ',':
 328       return json_triv_token(js, JSON_VALUE_SEP);
 329     case '.':
 330       json_parse_error(js, "Numbers must start with a digit");
 331     case 0xfeff:
 332       json_parse_error(js, "Misplaced byte-order mark, complain in Redmond");
 333     default:
 334       json_parse_error(js, "Invalid character");
 335     }
 336 }
 337
 338 struct json_node *json_peek_token(struct json_context *js)
 339 {
 340   if (!js->next_token)
 341     js->next_token = json_read_token(js);
 342   return js->next_token;
 343 }
 344
 345 struct json_node *json_next_token(struct json_context *js)
 346 {
 347   struct json_node *t = js->next_token;
 348   if (t)
 349     {
 350       js->next_token = NULL;
 351       return t;
 352     }
 353   return json_read_token(js);
 354 }
 355
 356 struct json_node *json_next_value(struct json_context *js)
 357 {
 358   struct json_node *t = json_next_token(js);
 359
 360   switch (t->type)
 361     {
 362     case JSON_EOF:
 363       return NULL;
 364
 365     // Elementary values
 366     case JSON_NULL:
 367     case JSON_BOOLEAN:
 368     case JSON_NUMBER:
 369     case JSON_STRING:
 370       return t;
 371
 372     // Array
 373     case JSON_BEGIN_ARRAY:
 374       {
 375         struct json_node *a = json_new_array(js);
 376         if (json_peek_token(js)->type == JSON_END_ARRAY)
 377           json_next_token(js);
 378         else for (;;)
 379           {
 380             struct json_node *v = json_next_value(js);
 381             if (!v)
 382               json_parse_error(js, "Unterminated array");
 383             json_array_append(a, v);
 384
 385             t = json_next_token(js);
 386             if (t->type == JSON_END_ARRAY)
 387               break;
 388             if (t->type != JSON_VALUE_SEP)
 389               json_parse_error(js, "Comma expected");
 390           }
 391         return a;
 392       }
 393
 394     // Object
 395     case JSON_BEGIN_OBJECT:
 396       {
 397         struct json_node *o = json_new_object(js);
 398         if (json_peek_token(js)->type == JSON_END_OBJECT)
 399           json_next_token(js);
 400         else for (;;)
 401           {
 402             struct json_node *k = json_next_value(js);
 403             if (!k)
 404               json_parse_error(js, "Unterminated object");
 405             if (k->type != JSON_STRING)
 406               json_parse_error(js, "Object key must be a string");
 407
 408             t = json_next_token(js);
 409             if (t->type != JSON_NAME_SEP)
 410               json_parse_error(js, "Colon expected");
 411
 412             struct json_node *v = json_next_value(js);
 413             if (!v)
 414               json_parse_error(js, "Unterminated object");
 415             if (json_object_get(o, k->string))          // FIXME: Optimize
 416               json_parse_error(js, "Key already set");
 417             json_object_set(o, k->string, v);
 418
 419             t = json_next_token(js);
 420             if (t->type == JSON_END_OBJECT)
 421               break;
 422             if (t->type != JSON_VALUE_SEP)
 423               json_parse_error(js, "Comma expected");
 424           }
 425         return o;
 426       }
 427
 428     // Misplaced characters
 429     case JSON_END_ARRAY:
 430       json_parse_error(js, "Misplaced end of array");
 431     case JSON_END_OBJECT:
 432       json_parse_error(js, "Misplaced end of object");
 433     case JSON_NAME_SEP:
 434       json_parse_error(js, "Misplaced colon");
 435     case JSON_VALUE_SEP:
 436       json_parse_error(js, "Misplaced comma");
 437     default:
 438       ASSERT(0);
 439     }
 440 }
 441
 442 struct json_node *json_parse(struct json_context *js, struct fastbuf *fb)
 443 {
 444   json_set_input(js, fb);
 445
 446   struct json_node *n = json_next_value(js);
 447   if (!n)
 448     json_parse_error(js, "Empty input");
 449
 450   struct json_node *t = json_next_token(js);
 451   if (t->type != JSON_EOF)
 452     json_parse_error(js, "Only one top-level value allowed");
 453
 454   return n;
 455 }