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       c = json_get_char(js);
  99       if (!(c >= '0' && c <= '9'))
 100         json_parse_error(js, "Malformed number: no digits after decimal point");
 101       while (c >= '0' && c <= '9')
 102         {
 103           p = mp_append_char(js->pool, p, c);
 104           c = json_get_char(js);
 105         }
 106     }
 107
 108   // Exponent
 109   if (c == 'e' || c == 'E')
 110     {
 111       p = mp_append_char(js->pool, p, c);
 112       c = json_get_char(js);
 113       if (c == '+' || c == '-')
 114         {
 115           p = mp_append_char(js->pool, p, c);
 116           c = json_get_char(js);
 117         }
 118       if (!(c >= '0' && c <= '9'))
 119         json_parse_error(js, "Malformed number: empty exponent");
 120       while (c >= '0' && c <= '9')
 121         {
 122           p = mp_append_char(js->pool, p, c);
 123           c = json_get_char(js);
 124         }
 125     }
 126
 127   json_unget_char(js, c);
 128
 129   p = mp_end_string(js->pool, p);
 130   errno = 0;
 131   double val = strtod(p, NULL);
 132   if (errno == ERANGE)
 133     json_parse_error(js, "Number out of range");
 134   mp_pop(js->pool);
 135
 136   return json_new_number(js, val);
 137 }
 138
 139 static struct json_node *json_parse_name(struct json_context *js, int c)
 140 {
 141   mp_push(js->pool);
 142   char *p = mp_start_noalign(js->pool, 0);
 143
 144   while (c >= 'a' && c <= 'z')
 145     {
 146       p = mp_append_char(js->pool, p, c);
 147       c = json_get_char(js);
 148     }
 149   json_unget_char(js, c);
 150
 151   p = mp_end_string(js->pool, p);
 152   struct json_node *n;
 153   if (!strcmp(p, "null"))
 154     n = json_new_null(js);
 155   else if (!strcmp(p, "false"))
 156     n = json_new_bool(js, 0);
 157   else if (!strcmp(p, "true"))
 158     n = json_new_bool(js, 1);
 159   else
 160     json_parse_error(js, "Invalid literal name");
 161
 162   mp_pop(js->pool);
 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         js->in_line++;
 295       c = json_get_char(js);
 296     }
 297   if (c < 0)
 298     return json_triv_token(js, JSON_EOF);
 299
 300   if (c >= '0' && c <= '9' || c == '-')
 301     return json_parse_number(js, c);
 302
 303   if (c >= 'a' && c <= 'z')
 304     return json_parse_name(js, c);
 305
 306   if (c == '"')
 307     return json_parse_string(js, c);
 308
 309   switch (c)
 310     {
 311     case '[':
 312       return json_triv_token(js, JSON_BEGIN_ARRAY);
 313     case ']':
 314       return json_triv_token(js, JSON_END_ARRAY);
 315     case '{':
 316       return json_triv_token(js, JSON_BEGIN_OBJECT);
 317     case '}':
 318       return json_triv_token(js, JSON_END_OBJECT);
 319     case ':':
 320       return json_triv_token(js, JSON_NAME_SEP);
 321     case ',':
 322       return json_triv_token(js, JSON_VALUE_SEP);
 323     default:
 324       json_parse_error(js, "Invalid character");
 325     }
 326 }
 327
 328 struct json_node *json_peek_token(struct json_context *js)
 329 {
 330   if (!js->next_token)
 331     js->next_token = json_read_token(js);
 332   return js->next_token;
 333 }
 334
 335 struct json_node *json_next_token(struct json_context *js)
 336 {
 337   struct json_node *t = js->next_token;
 338   if (t)
 339     {
 340       js->next_token = NULL;
 341       return t;
 342     }
 343   return json_read_token(js);
 344 }
 345
 346 struct json_node *json_next_value(struct json_context *js)
 347 {
 348   struct json_node *t = json_next_token(js);
 349
 350   switch (t->type)
 351     {
 352     case JSON_EOF:
 353       return NULL;
 354
 355     // Elementary values
 356     case JSON_NULL:
 357     case JSON_BOOLEAN:
 358     case JSON_NUMBER:
 359     case JSON_STRING:
 360       return t;
 361
 362     // Array
 363     case JSON_BEGIN_ARRAY:
 364       {
 365         struct json_node *a = json_new_array(js);
 366         if (json_peek_token(js)->type == JSON_END_ARRAY)
 367           json_next_token(js);
 368         else for (;;)
 369           {
 370             struct json_node *v = json_next_value(js);
 371             if (!v)
 372               json_parse_error(js, "Unterminated array");
 373             json_array_append(a, v);
 374
 375             t = json_next_token(js);
 376             if (t->type == JSON_END_ARRAY)
 377               break;
 378             if (t->type != JSON_VALUE_SEP)
 379               json_parse_error(js, "Comma expected");
 380           }
 381         return a;
 382       }
 383
 384     // Object
 385     case JSON_BEGIN_OBJECT:
 386       {
 387         struct json_node *o = json_new_object(js);
 388         if (json_peek_token(js)->type == JSON_END_OBJECT)
 389           json_next_token(js);
 390         else for (;;)
 391           {
 392             struct json_node *k = json_next_value(js);
 393             if (!k)
 394               json_parse_error(js, "Unterminated object");
 395             if (k->type != JSON_STRING)
 396               json_parse_error(js, "Object key must be a string");
 397
 398             t = json_next_token(js);
 399             if (t->type != JSON_NAME_SEP)
 400               json_parse_error(js, "Colon expected");
 401
 402             struct json_node *v = json_next_value(js);
 403             if (!v)
 404               json_parse_error(js, "Unterminated object");
 405             if (json_object_get(o, k->string))          // FIXME: Optimize
 406               json_parse_error(js, "Key already set");
 407             json_object_set(o, k->string, v);
 408
 409             t = json_next_token(js);
 410             if (t->type == JSON_END_OBJECT)
 411               break;
 412             if (t->type != JSON_VALUE_SEP)
 413               json_parse_error(js, "Comma expected");
 414           }
 415         return o;
 416       }
 417
 418     // Misplaced characters
 419     case JSON_END_ARRAY:
 420       json_parse_error(js, "Misplaced end of array");
 421     case JSON_END_OBJECT:
 422       json_parse_error(js, "Misplaced end of object");
 423     case JSON_NAME_SEP:
 424       json_parse_error(js, "Misplaced colon");
 425     case JSON_VALUE_SEP:
 426       json_parse_error(js, "Misplaced comma");
 427     default:
 428       ASSERT(0);
 429     }
 430 }
 431
 432 struct json_node *json_parse(struct json_context *js, struct fastbuf *fb)
 433 {
 434   json_set_input(js, fb);
 435
 436   struct json_node *n = json_next_value(js);
 437   if (!n)
 438     json_parse_error(js, "Empty input");
 439
 440   struct json_node *t = json_next_token(js);
 441   if (t->type != JSON_EOF)
 442     json_parse_error(js, "Only one top-level value allowed");
 443
 444   return n;
 445 }