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