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