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   mp_push(js->pool);
 143   char *p = mp_start_noalign(js->pool, 0);
 144
 145   while (c >= 'a' && c <= 'z')
 146     {
 147       p = mp_append_char(js->pool, p, c);
 148       c = json_get_char(js);
 149     }
 150   json_unget_char(js, c);
 151
 152   p = mp_end_string(js->pool, p);
 153   struct json_node *n;
 154   if (!strcmp(p, "null"))
 155     n = json_new_null(js);
 156   else if (!strcmp(p, "false"))
 157     n = json_new_bool(js, 0);
 158   else if (!strcmp(p, "true"))
 159     n = json_new_bool(js, 1);
 160   else
 161     json_parse_error(js, "Invalid literal name");
 162
 163   mp_pop(js->pool);
 164   return n;
 165 }
 166
 167 static uint json_parse_hex4(struct json_context *js)
 168 {
 169   uint x = 0;
 170   for (int i=0; i<4; i++)
 171     {
 172       x = x << 4;
 173       int c = json_get_char(js);
 174       if (c >= '0' && c <= '9')
 175         x += c - '0';
 176       else if (c >= 'a' && c <= 'f')
 177         x += c - 'a' + 10;
 178       else if (c >= 'A' && c <= 'F')
 179         x += c - 'A' + 10;
 180       else
 181         json_parse_error(js, "Invalid Unicode escape sequence");
 182     }
 183   return x;
 184 }
 185
 186 static struct json_node *json_parse_string(struct json_context *js, int c)
 187 {
 188   char *p = mp_start_noalign(js->pool, 0);
 189
 190   c = json_get_char(js);
 191   while (c != '"')
 192     {
 193       if (unlikely(c < 0x20))
 194         {
 195           if (c < 0 || c == 0x0d || c == 0x0a)
 196             json_parse_error(js, "Unterminated string");
 197           else
 198             json_parse_error(js, "Invalid control character in string");
 199         }
 200       if (unlikely(c >= 0xd800 && c < 0xf900))
 201         {
 202           if (c < 0xe000)
 203             json_parse_error(js, "Invalid surrogate character in string");
 204           else
 205             json_parse_error(js, "Invalid private-use character in string");
 206         }
 207       if (unlikely(c > 0xf0000))
 208         {
 209           if (c > 0x10ffff)
 210             json_parse_error(js, "Invalid non-Unicode character in string");
 211           else
 212             json_parse_error(js, "Invalid private-use character in string");
 213         }
 214       if (c == '\\')
 215         {
 216           c = json_get_char(js);
 217           switch (c)
 218             {
 219             case '"':
 220             case '\\':
 221             case '/':
 222               break;
 223             case 'b':
 224               c = 0x08;
 225               break;
 226             case 'f':
 227               c = 0x0c;
 228               break;
 229             case 'n':
 230               c = 0x0a;
 231               break;
 232             case 'r':
 233               c = 0x0d;
 234               break;
 235             case 't':
 236               c = 0x09;
 237               break;
 238             case 'u':
 239               {
 240                 uint x = json_parse_hex4(js);
 241                 if (!x)
 242                   json_parse_error(js, "Zero bytes in strings are not supported");
 243                 if (x >= 0xd800 && x < 0xf900)
 244                   {
 245                     if (x < 0xdc00)
 246                       {
 247                         // High surrogate: low surrogate must follow
 248                         uint y = 0;
 249                         if (json_get_char(js) == '\\' && json_get_char(js) == 'u')
 250                           y = json_parse_hex4(js);
 251                         if (!(y >= 0xdc00 && y < 0xe000))
 252                           json_parse_error(js, "Escaped high surrogate codepoint must be followed by a low surrogate codepoint");
 253                         c = 0x10000 + ((x & 0x03ff) << 10) | (y & 0x03ff);
 254                         if (c > 0xf0000)
 255                           json_parse_error(js, "Invalid escaped private-use character");
 256                       }
 257                     else if (x < 0xe000)
 258                       {
 259                         // Low surrogate
 260                         json_parse_error(js, "Invalid escaped surrogate codepoint");
 261                       }
 262                     else
 263                       json_parse_error(js, "Invalid escaped private-use character");
 264                   }
 265                 else
 266                   c = x;
 267                 break;
 268               }
 269             default:
 270               json_parse_error(js, "Invalid backslash sequence in string");
 271             }
 272         }
 273       p = mp_append_utf8_32(js->pool, p, c);
 274       c = json_get_char(js);
 275     }
 276
 277   p = mp_end_string(js->pool, p);
 278   return json_new_string_ref(js, p);
 279 }
 280
 281 static struct json_node *json_read_token(struct json_context *js)
 282 {
 283   if (unlikely(js->in_eof))
 284     return json_triv_token(js, JSON_EOF);
 285
 286   int c = js->next_char;
 287   if (c >= 0)
 288     js->next_char = -1;
 289   else
 290     c = json_get_char(js);
 291
 292   while (c == 0x20 || c == 0x09 || c == 0x0a || c == 0x0d)
 293     {
 294       if (c == 0x0a)
 295         {
 296           js->in_line++;
 297           js->in_column = 0;
 298         }
 299       c = json_get_char(js);
 300     }
 301   if (c < 0)
 302     return json_triv_token(js, JSON_EOF);
 303
 304   if (c >= '0' && c <= '9' || c == '-')
 305     return json_parse_number(js, c);
 306
 307   if (c >= 'a' && c <= 'z')
 308     return json_parse_name(js, c);
 309
 310   if (c == '"')
 311     return json_parse_string(js, c);
 312
 313   switch (c)
 314     {
 315     case '[':
 316       return json_triv_token(js, JSON_BEGIN_ARRAY);
 317     case ']':
 318       return json_triv_token(js, JSON_END_ARRAY);
 319     case '{':
 320       return json_triv_token(js, JSON_BEGIN_OBJECT);
 321     case '}':
 322       return json_triv_token(js, JSON_END_OBJECT);
 323     case ':':
 324       return json_triv_token(js, JSON_NAME_SEP);
 325     case ',':
 326       return json_triv_token(js, JSON_VALUE_SEP);
 327     default:
 328       json_parse_error(js, "Invalid character");
 329     }
 330 }
 331
 332 struct json_node *json_peek_token(struct json_context *js)
 333 {
 334   if (!js->next_token)
 335     js->next_token = json_read_token(js);
 336   return js->next_token;
 337 }
 338
 339 struct json_node *json_next_token(struct json_context *js)
 340 {
 341   struct json_node *t = js->next_token;
 342   if (t)
 343     {
 344       js->next_token = NULL;
 345       return t;
 346     }
 347   return json_read_token(js);
 348 }
 349
 350 struct json_node *json_next_value(struct json_context *js)
 351 {
 352   struct json_node *t = json_next_token(js);
 353
 354   switch (t->type)
 355     {
 356     case JSON_EOF:
 357       return NULL;
 358
 359     // Elementary values
 360     case JSON_NULL:
 361     case JSON_BOOLEAN:
 362     case JSON_NUMBER:
 363     case JSON_STRING:
 364       return t;
 365
 366     // Array
 367     case JSON_BEGIN_ARRAY:
 368       {
 369         struct json_node *a = json_new_array(js);
 370         if (json_peek_token(js)->type == JSON_END_ARRAY)
 371           json_next_token(js);
 372         else for (;;)
 373           {
 374             struct json_node *v = json_next_value(js);
 375             if (!v)
 376               json_parse_error(js, "Unterminated array");
 377             json_array_append(a, v);
 378
 379             t = json_next_token(js);
 380             if (t->type == JSON_END_ARRAY)
 381               break;
 382             if (t->type != JSON_VALUE_SEP)
 383               json_parse_error(js, "Comma expected");
 384           }
 385         return a;
 386       }
 387
 388     // Object
 389     case JSON_BEGIN_OBJECT:
 390       {
 391         struct json_node *o = json_new_object(js);
 392         if (json_peek_token(js)->type == JSON_END_OBJECT)
 393           json_next_token(js);
 394         else for (;;)
 395           {
 396             struct json_node *k = json_next_value(js);
 397             if (!k)
 398               json_parse_error(js, "Unterminated object");
 399             if (k->type != JSON_STRING)
 400               json_parse_error(js, "Object key must be a string");
 401
 402             t = json_next_token(js);
 403             if (t->type != JSON_NAME_SEP)
 404               json_parse_error(js, "Colon expected");
 405
 406             struct json_node *v = json_next_value(js);
 407             if (!v)
 408               json_parse_error(js, "Unterminated object");
 409             if (json_object_get(o, k->string))          // FIXME: Optimize
 410               json_parse_error(js, "Key already set");
 411             json_object_set(o, k->string, v);
 412
 413             t = json_next_token(js);
 414             if (t->type == JSON_END_OBJECT)
 415               break;
 416             if (t->type != JSON_VALUE_SEP)
 417               json_parse_error(js, "Comma expected");
 418           }
 419         return o;
 420       }
 421
 422     // Misplaced characters
 423     case JSON_END_ARRAY:
 424       json_parse_error(js, "Misplaced end of array");
 425     case JSON_END_OBJECT:
 426       json_parse_error(js, "Misplaced end of object");
 427     case JSON_NAME_SEP:
 428       json_parse_error(js, "Misplaced colon");
 429     case JSON_VALUE_SEP:
 430       json_parse_error(js, "Misplaced comma");
 431     default:
 432       ASSERT(0);
 433     }
 434 }
 435
 436 struct json_node *json_parse(struct json_context *js, struct fastbuf *fb)
 437 {
 438   json_set_input(js, fb);
 439
 440   struct json_node *n = json_next_value(js);
 441   if (!n)
 442     json_parse_error(js, "Empty input");
 443
 444   struct json_node *t = json_next_token(js);
 445   if (t->type != JSON_EOF)
 446     json_parse_error(js, "Only one top-level value allowed");
 447
 448   return n;
 449 }