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 #undef LOCAL_DEBUG
  11
  12 #include <ucw/lib.h>
  13 #include <ucw/trans.h>
  14 #include <ucw/ff-unicode.h>
  15 #include <ucw/unicode.h>
  16 #include <ucw-json/json.h>
  17
  18 #include <errno.h>
  19 #include <stdlib.h>
  20
  21 void json_set_input(struct json_context *js, struct fastbuf *in)
  22 {
  23   js->in_fb = in;
  24   js->in_line = 1;
  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 // FIXME: Report column as well as line?
  33 static void NONRET json_parse_error(struct json_context *js, const char *msg)
  34 {
  35   trans_throw("ucw.js.parse", js, "%s at line %u", msg, js->in_line);
  36 }
  37
  38 static int json_get_char(struct json_context *js)
  39 {
  40   int c = bget_utf8_32_repl(js->in_fb, -2);
  41   if (unlikely(c < 0))
  42     {
  43       if (c == -2)
  44         json_parse_error(js, "Malformed UTF-8 character");
  45       js->in_eof = 1;
  46       // FIXME: Reject alternative sequences
  47       return c;
  48     }
  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       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                 break;
 265               }
 266             default:
 267               json_parse_error(js, "Invalid backslash sequence in string");
 268             }
 269         }
 270       p = mp_append_utf8_32(js->pool, p, c);
 271       c = json_get_char(js);
 272     }
 273
 274   p = mp_end_string(js->pool, p);
 275   return json_new_string_ref(js, p);
 276 }
 277
 278 struct json_node *json_peek_token(struct json_context *js)
 279 {
 280   if (unlikely(js->in_eof))
 281     return json_triv_token(js, JSON_EOF);
 282
 283   int c = js->next_char;
 284   if (c >= 0)
 285     js->next_char = -1;
 286   else
 287     c = json_get_char(js);
 288
 289   while (c == 0x20 || c == 0x09 || c == 0x0a || c == 0x0d)
 290     {
 291       if (c == 0x0a)
 292         js->in_line++;
 293       c = json_get_char(js);
 294     }
 295   if (c < 0)
 296     return json_triv_token(js, JSON_EOF);
 297
 298   if (c >= '0' && c <= '9' || c == '-')
 299     return json_parse_number(js, c);
 300
 301   if (c >= 'a' && c <= 'z')
 302     return json_parse_name(js, c);
 303
 304   if (c == '"')
 305     return json_parse_string(js, c);
 306
 307   switch (c)
 308     {
 309     case '[':
 310       return json_triv_token(js, JSON_BEGIN_ARRAY);
 311     case ']':
 312       return json_triv_token(js, JSON_END_ARRAY);
 313     case '{':
 314       return json_triv_token(js, JSON_BEGIN_OBJECT);
 315     case '}':
 316       return json_triv_token(js, JSON_END_OBJECT);
 317     case ':':
 318       return json_triv_token(js, JSON_NAME_SEP);
 319     case ',':
 320       return json_triv_token(js, JSON_VALUE_SEP);
 321     default:
 322       json_parse_error(js, "Invalid character");
 323     }
 324 }
 325
 326 struct json_node *json_next_token(struct json_context *js)
 327 {
 328   if (!js->next_token)
 329     json_peek_token(js);
 330   struct json_node *t = js->next_token;
 331   js->next_token = NULL;
 332   return t;
 333 }
 334
 335 struct json_node *json_next_object(struct json_context *js)
 336 {
 337   struct json_node *t = json_next_token(js);
 338
 339   switch (t->type)
 340     {
 341     case JSON_EOF:
 342       return NULL;
 343
 344     // Elementary values
 345     case JSON_NULL:
 346     case JSON_BOOLEAN:
 347     case JSON_NUMBER:
 348     case JSON_STRING:
 349       return t;
 350
 351     // Array
 352     case JSON_BEGIN_ARRAY:
 353       {
 354         struct json_node *a = json_new_array(js);
 355         if (json_peek_token(js)->type == JSON_END_ARRAY)
 356           json_next_token(js);
 357         else for (;;)
 358           {
 359             struct json_node *v = json_next_object(js);
 360             if (!v)
 361               json_parse_error(js, "Unterminated array");
 362             json_array_append(a, v);
 363
 364             t = json_next_token(js);
 365             if (t->type == JSON_END_ARRAY)
 366               break;
 367             if (t->type != JSON_VALUE_SEP)
 368               json_parse_error(js, "Comma expected");
 369           }
 370         return a;
 371       }
 372
 373     // Object
 374     case JSON_BEGIN_OBJECT:
 375       {
 376         struct json_node *o = json_new_object(js);
 377         if (json_peek_token(js)->type == JSON_END_OBJECT)
 378           json_next_token(js);
 379         else for (;;)
 380           {
 381             struct json_node *k = json_next_object(js);
 382             if (!k)
 383               json_parse_error(js, "Unterminated object");
 384             if (k->type != JSON_STRING)
 385               json_parse_error(js, "Object key must be a string");
 386
 387             t = json_next_token(js);
 388             if (t->type != JSON_NAME_SEP)
 389               json_parse_error(js, "Colon expected");
 390
 391             struct json_node *v = json_next_object(js);
 392             if (!v)
 393               json_parse_error(js, "Unterminated object");
 394             if (json_object_get(o, k->string))          // FIXME: Optimize
 395               json_parse_error(js, "Key already set");
 396             json_object_set(o, k->string, v);
 397
 398             t = json_next_token(js);
 399             if (t->type == JSON_END_OBJECT)
 400               break;
 401             if (t->type != JSON_VALUE_SEP)
 402               json_parse_error(js, "Comma expected");
 403           }
 404         return o;
 405       }
 406
 407     // Misplaced characters
 408     case JSON_END_ARRAY:
 409       json_parse_error(js, "Misplaced end of array");
 410     case JSON_END_OBJECT:
 411       json_parse_error(js, "Misplaced end of object");
 412     case JSON_NAME_SEP:
 413       json_parse_error(js, "Misplaced colon");
 414     case JSON_VALUE_SEP:
 415       json_parse_error(js, "Misplaced comma");
 416     default:
 417       ASSERT(0);
 418     }
 419 }
 420
 421 struct json_node *json_parse(struct json_context *js, struct fastbuf *fb)
 422 {
 423   json_set_input(js, fb);
 424
 425   struct json_node *n = json_next_object(js);
 426   if (!n)
 427     json_parse_error(js, "Empty input");
 428
 429   struct json_node *t = json_next_token(js);
 430   if (t->type != JSON_EOF)
 431     json_parse_error(js, "Only one top-level value allowed");
 432
 433   return n;
 434 }