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 }
  29
  30 static void NONRET json_parse_error(struct json_context *js, const char *msg)
  31 {
  32   trans_throw("ucw.js.parse", js, "%s at line %u:%u", msg, js->in_line, js->in_column);
  33 }
  34
  35 static int json_get_char(struct json_context *js)
  36 {
  37   int c = bget_utf8_32_repl(js->in_fb, -2);
  38   if (unlikely(c < 0))
  39     {
  40       if (c == -2)
  41         json_parse_error(js, "Malformed UTF-8 character");
  42       js->in_eof = 1;
  43       // FIXME: Reject alternative sequences
  44       return c;
  45     }
  46   js->in_column++;
  47   return c;
  48 }
  49
  50 static void json_unget_char(struct json_context *js, int c)
  51 {
  52   js->next_char = c;
  53 }
  54
  55 static struct json_node *json_triv_token(struct json_context *js, enum json_node_type type)
  56 {
  57   js->trivial_token->type = type;
  58   return js->trivial_token;
  59 }
  60
  61 static struct json_node *json_parse_number(struct json_context *js, int c)
  62 {
  63   mp_push(js->pool);
  64   char *p = mp_start_noalign(js->pool, 0);
  65
  66   // Optional minus
  67   if (c == '-')
  68     {
  69       p = mp_append_char(js->pool, p, c);
  70       c = json_get_char(js);
  71       if (!(c >= '0' && c <= '9'))
  72         json_parse_error(js, "Malformed number: just minus");
  73     }
  74
  75   // Integer part
  76   if (c == '0')
  77     {
  78       // Leading zeroes are forbidden by RFC 7159
  79       p = mp_append_char(js->pool, p, c);
  80       c = json_get_char(js);
  81       if (c >= '0' && c <= '9')
  82         json_parse_error(js, "Malformed number: leading zero");
  83     }
  84   else
  85     {
  86       while (c >= '0' && c <= '9')
  87         {
  88           p = mp_append_char(js->pool, p, c);
  89           c = json_get_char(js);
  90         }
  91     }
  92
  93   // Fractional part
  94   if (c == '.')
  95     {
  96       p = mp_append_char(js->pool, p, c);
  97       c = json_get_char(js);
  98       if (!(c >= '0' && c <= '9'))
  99         json_parse_error(js, "Malformed number: no digits after decimal point");
 100       while (c >= '0' && c <= '9')
 101         {
 102           p = mp_append_char(js->pool, p, c);
 103           c = json_get_char(js);
 104         }
 105     }
 106
 107   // Exponent
 108   if (c == 'e' || c == 'E')
 109     {
 110       p = mp_append_char(js->pool, p, c);
 111       c = json_get_char(js);
 112       if (c == '+' || c == '-')
 113         {
 114           p = mp_append_char(js->pool, p, c);
 115           c = json_get_char(js);
 116         }
 117       if (!(c >= '0' && c <= '9'))
 118         json_parse_error(js, "Malformed number: empty exponent");
 119       while (c >= '0' && c <= '9')
 120         {
 121           p = mp_append_char(js->pool, p, c);
 122           c = json_get_char(js);
 123         }
 124     }
 125
 126   json_unget_char(js, c);
 127
 128   p = mp_end_string(js->pool, p);
 129   errno = 0;
 130   double val = strtod(p, NULL);
 131   if (errno == ERANGE)
 132     json_parse_error(js, "Number out of range");
 133   mp_pop(js->pool);
 134
 135   return json_new_number(js, val);
 136 }
 137
 138 static struct json_node *json_parse_name(struct json_context *js, int c)
 139 {
 140   char name[16];
 141   uint i = 0;
 142
 143   while (c >= 'a' && c <= 'z')
 144     {
 145       if (i < sizeof(name) - 1)
 146         name[i++] = c;
 147       c = json_get_char(js);
 148     }
 149   if (i >= sizeof(name) - 1)
 150     json_parse_error(js, "Invalid literal name");
 151   name[i] = 0;
 152   json_unget_char(js, c);
 153
 154   struct json_node *n;
 155   if (!strcmp(name, "null"))
 156     n = json_new_null(js);
 157   else if (!strcmp(name, "false"))
 158     n = json_new_bool(js, 0);
 159   else if (!strcmp(name, "true"))
 160     n = json_new_bool(js, 1);
 161   else
 162     json_parse_error(js, "Invalid literal name");
 163
 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     case '.':
 328       json_parse_error(js, "Numbers must start with a digit");
 329     case 0xfeff:
 330       json_parse_error(js, "Misplaced byte-order mark, complain in Redmond");
 331     default:
 332       json_parse_error(js, "Invalid character");
 333     }
 334 }
 335
 336 struct json_node *json_peek_token(struct json_context *js)
 337 {
 338   if (!js->next_token)
 339     js->next_token = json_read_token(js);
 340   return js->next_token;
 341 }
 342
 343 struct json_node *json_next_token(struct json_context *js)
 344 {
 345   struct json_node *t = js->next_token;
 346   if (t)
 347     {
 348       js->next_token = NULL;
 349       return t;
 350     }
 351   return json_read_token(js);
 352 }
 353
 354 struct json_node *json_next_value(struct json_context *js)
 355 {
 356   struct json_node *t = json_next_token(js);
 357
 358   switch (t->type)
 359     {
 360     case JSON_EOF:
 361       return NULL;
 362
 363     // Elementary values
 364     case JSON_NULL:
 365     case JSON_BOOLEAN:
 366     case JSON_NUMBER:
 367     case JSON_STRING:
 368       return t;
 369
 370     // Array
 371     case JSON_BEGIN_ARRAY:
 372       {
 373         struct json_node *a = json_new_array(js);
 374         if (json_peek_token(js)->type == JSON_END_ARRAY)
 375           json_next_token(js);
 376         else for (;;)
 377           {
 378             struct json_node *v = json_next_value(js);
 379             if (!v)
 380               json_parse_error(js, "Unterminated array");
 381             json_array_append(a, v);
 382
 383             t = json_next_token(js);
 384             if (t->type == JSON_END_ARRAY)
 385               break;
 386             if (t->type != JSON_VALUE_SEP)
 387               json_parse_error(js, "Comma or right bracket expected");
 388           }
 389         return a;
 390       }
 391
 392     // Object
 393     case JSON_BEGIN_OBJECT:
 394       {
 395         struct json_node *o = json_new_object(js);
 396         if (json_peek_token(js)->type == JSON_END_OBJECT)
 397           json_next_token(js);
 398         else for (;;)
 399           {
 400             struct json_node *k = json_next_value(js);
 401             if (!k)
 402               json_parse_error(js, "Unterminated object");
 403             if (k->type != JSON_STRING)
 404               json_parse_error(js, "Object key must be a string");
 405
 406             t = json_next_token(js);
 407             if (t->type != JSON_NAME_SEP)
 408               json_parse_error(js, "Colon expected");
 409
 410             struct json_node *v = json_next_value(js);
 411             if (!v)
 412               json_parse_error(js, "Unterminated object");
 413             if (json_object_get(o, k->string))          // FIXME: Optimize
 414               json_parse_error(js, "Key already set");
 415             json_object_set(o, k->string, v);
 416
 417             t = json_next_token(js);
 418             if (t->type == JSON_END_OBJECT)
 419               break;
 420             if (t->type != JSON_VALUE_SEP)
 421               json_parse_error(js, "Comma expected");
 422           }
 423         return o;
 424       }
 425
 426     // Misplaced characters
 427     case JSON_END_ARRAY:
 428       json_parse_error(js, "Misplaced end of array");
 429     case JSON_END_OBJECT:
 430       json_parse_error(js, "Misplaced end of object");
 431     case JSON_NAME_SEP:
 432       json_parse_error(js, "Misplaced colon");
 433     case JSON_VALUE_SEP:
 434       json_parse_error(js, "Misplaced comma");
 435     default:
 436       ASSERT(0);
 437     }
 438 }
 439
 440 struct json_node *json_parse(struct json_context *js, struct fastbuf *fb)
 441 {
 442   json_set_input(js, fb);
 443
 444   struct json_node *n = json_next_value(js);
 445   if (!n)
 446     json_parse_error(js, "Empty input");
 447
 448   struct json_node *t = json_next_token(js);
 449   if (t->type != JSON_EOF)
 450     json_parse_error(js, "Only one top-level value allowed");
 451
 452   return n;
 453 }