lib/json.c

   1 /*
   2  * Copyright (c) 2009, 2010, 2011 Nicira Networks.
   3  *
   4  * Licensed under the Apache License, Version 2.0 (the "License");
   5  * you may not use this file except in compliance with the License.
   6  * You may obtain a copy of the License at:
   7  *
   8  *     http://www.apache.org/licenses/LICENSE-2.0
   9  *
  10  * Unless required by applicable law or agreed to in writing, software
  11  * distributed under the License is distributed on an "AS IS" BASIS,
  12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  13  * See the License for the specific language governing permissions and
  14  * limitations under the License.
  15  */
  16
  17 #include <config.h>
  18
  19 #include "json.h"
  20
  21 #include <assert.h>
  22 #include <ctype.h>
  23 #include <errno.h>
  24 #include <float.h>
  25 #include <limits.h>
  26 #include <string.h>
  27
  28 #include "dynamic-string.h"
  29 #include "hash.h"
  30 #include "shash.h"
  31 #include "unicode.h"
  32 #include "util.h"
  33
  34 /* The type of a JSON token. */
  35 enum json_token_type {
  36     T_EOF = 0,
  37     T_BEGIN_ARRAY = '[',
  38     T_END_ARRAY = ']',
  39     T_BEGIN_OBJECT = '{',
  40     T_END_OBJECT = '}',
  41     T_NAME_SEPARATOR = ':',
  42     T_VALUE_SEPARATOR = ',',
  43     T_FALSE = UCHAR_MAX + 1,
  44     T_NULL,
  45     T_TRUE,
  46     T_INTEGER,
  47     T_REAL,
  48     T_STRING
  49 };
  50
  51 /* A JSON token.
  52  *
  53  * RFC 4627 doesn't define a lexical structure for JSON but I believe this to
  54  * be compliant with the standard.
  55  */
  56 struct json_token {
  57     enum json_token_type type;
  58     union {
  59         double real;
  60         long long int integer;
  61         const char *string;
  62     } u;
  63 };
  64
  65 enum json_lex_state {
  66     JSON_LEX_START,             /* Not inside a token. */
  67     JSON_LEX_NUMBER,            /* Reading a number. */
  68     JSON_LEX_KEYWORD,           /* Reading a keyword. */
  69     JSON_LEX_STRING,            /* Reading a quoted string. */
  70     JSON_LEX_ESCAPE             /* In a quoted string just after a "\". */
  71 };
  72
  73 enum json_parse_state {
  74     JSON_PARSE_START,           /* Beginning of input. */
  75     JSON_PARSE_END,             /* End of input. */
  76
  77     /* Objects. */
  78     JSON_PARSE_OBJECT_INIT,     /* Expecting '}' or an object name. */
  79     JSON_PARSE_OBJECT_NAME,     /* Expecting an object name. */
  80     JSON_PARSE_OBJECT_COLON,    /* Expecting ':'. */
  81     JSON_PARSE_OBJECT_VALUE,    /* Expecting an object value. */
  82     JSON_PARSE_OBJECT_NEXT,     /* Expecting ',' or '}'. */
  83
  84     /* Arrays. */
  85     JSON_PARSE_ARRAY_INIT,      /* Expecting ']' or a value. */
  86     JSON_PARSE_ARRAY_VALUE,     /* Expecting a value. */
  87     JSON_PARSE_ARRAY_NEXT       /* Expecting ',' or ']'. */
  88 };
  89
  90 struct json_parser_node {
  91     struct json *json;
  92 };
  93
  94 /* A JSON parser. */
  95 struct json_parser {
  96     int flags;
  97
  98     /* Lexical analysis. */
  99     enum json_lex_state lex_state;
 100     struct ds buffer;           /* Buffer for accumulating token text. */
 101     int line_number;
 102     int column_number;
 103     int byte_number;
 104
 105     /* Parsing. */
 106     enum json_parse_state parse_state;
 107 #define JSON_MAX_HEIGHT 1000
 108     struct json_parser_node *stack;
 109     size_t height, allocated_height;
 110     char *member_name;
 111
 112     /* Parse status. */
 113     bool done;
 114     char *error;                /* Error message, if any, null if none yet. */
 115 };
 116
 117 static struct json *json_create(enum json_type type);
 118 static void json_parser_input(struct json_parser *, struct json_token *);
 119
 120 static void json_error(struct json_parser *p, const char *format, ...)
 121     PRINTF_FORMAT(2, 3);
 122 \f
 123 const char *
 124 json_type_to_string(enum json_type type)
 125 {
 126     switch (type) {
 127     case JSON_NULL:
 128         return "null";
 129
 130     case JSON_FALSE:
 131         return "false";
 132
 133     case JSON_TRUE:
 134         return "true";
 135
 136     case JSON_OBJECT:
 137         return "object";
 138
 139     case JSON_ARRAY:
 140         return "array";
 141
 142     case JSON_INTEGER:
 143     case JSON_REAL:
 144         return "number";
 145
 146     case JSON_STRING:
 147         return "string";
 148
 149     case JSON_N_TYPES:
 150     default:
 151         return "<invalid>";
 152     }
 153 }
 154 \f
 155 /* Functions for manipulating struct json. */
 156
 157 struct json *
 158 json_null_create(void)
 159 {
 160     return json_create(JSON_NULL);
 161 }
 162
 163 struct json *
 164 json_boolean_create(bool b)
 165 {
 166     return json_create(b ? JSON_TRUE : JSON_FALSE);
 167 }
 168
 169 struct json *
 170 json_string_create_nocopy(char *s)
 171 {
 172     struct json *json = json_create(JSON_STRING);
 173     json->u.string = s;
 174     return json;
 175 }
 176
 177 struct json *
 178 json_string_create(const char *s)
 179 {
 180     return json_string_create_nocopy(xstrdup(s));
 181 }
 182
 183 struct json *
 184 json_array_create_empty(void)
 185 {
 186     struct json *json = json_create(JSON_ARRAY);
 187     json->u.array.elems = NULL;
 188     json->u.array.n = 0;
 189     json->u.array.n_allocated = 0;
 190     return json;
 191 }
 192
 193 void
 194 json_array_add(struct json *array_, struct json *element)
 195 {
 196     struct json_array *array = json_array(array_);
 197     if (array->n >= array->n_allocated) {
 198         array->elems = x2nrealloc(array->elems, &array->n_allocated,
 199                                   sizeof *array->elems);
 200     }
 201     array->elems[array->n++] = element;
 202 }
 203
 204 void
 205 json_array_trim(struct json *array_)
 206 {
 207     struct json_array *array = json_array(array_);
 208     if (array->n < array->n_allocated){
 209         array->n_allocated = array->n;
 210         array->elems = xrealloc(array->elems, array->n * sizeof *array->elems);
 211     }
 212 }
 213
 214 struct json *
 215 json_array_create(struct json **elements, size_t n)
 216 {
 217     struct json *json = json_create(JSON_ARRAY);
 218     json->u.array.elems = elements;
 219     json->u.array.n = n;
 220     json->u.array.n_allocated = n;
 221     return json;
 222 }
 223
 224 struct json *
 225 json_array_create_1(struct json *elem0)
 226 {
 227     struct json **elems = xmalloc(sizeof *elems);
 228     elems[0] = elem0;
 229     return json_array_create(elems, 1);
 230 }
 231
 232 struct json *
 233 json_array_create_2(struct json *elem0, struct json *elem1)
 234 {
 235     struct json **elems = xmalloc(2 * sizeof *elems);
 236     elems[0] = elem0;
 237     elems[1] = elem1;
 238     return json_array_create(elems, 2);
 239 }
 240
 241 struct json *
 242 json_array_create_3(struct json *elem0, struct json *elem1, struct json *elem2)
 243 {
 244     struct json **elems = xmalloc(3 * sizeof *elems);
 245     elems[0] = elem0;
 246     elems[1] = elem1;
 247     elems[2] = elem2;
 248     return json_array_create(elems, 3);
 249 }
 250
 251 struct json *
 252 json_object_create(void)
 253 {
 254     struct json *json = json_create(JSON_OBJECT);
 255     json->u.object = xmalloc(sizeof *json->u.object);
 256     shash_init(json->u.object);
 257     return json;
 258 }
 259
 260 struct json *
 261 json_integer_create(long long int integer)
 262 {
 263     struct json *json = json_create(JSON_INTEGER);
 264     json->u.integer = integer;
 265     return json;
 266 }
 267
 268 struct json *
 269 json_real_create(double real)
 270 {
 271     struct json *json = json_create(JSON_REAL);
 272     json->u.real = real;
 273     return json;
 274 }
 275
 276 void
 277 json_object_put(struct json *json, const char *name, struct json *value)
 278 {
 279     json_destroy(shash_replace(json->u.object, name, value));
 280 }
 281
 282 void
 283 json_object_put_string(struct json *json, const char *name, const char *value)
 284 {
 285     json_object_put(json, name, json_string_create(value));
 286 }
 287
 288 const char *
 289 json_string(const struct json *json)
 290 {
 291     assert(json->type == JSON_STRING);
 292     return json->u.string;
 293 }
 294
 295 struct json_array *
 296 json_array(const struct json *json)
 297 {
 298     assert(json->type == JSON_ARRAY);
 299     return (struct json_array *) &json->u.array;
 300 }
 301
 302 struct shash *
 303 json_object(const struct json *json)
 304 {
 305     assert(json->type == JSON_OBJECT);
 306     return (struct shash *) json->u.object;
 307 }
 308
 309 bool
 310 json_boolean(const struct json *json)
 311 {
 312     assert(json->type == JSON_TRUE || json->type == JSON_FALSE);
 313     return json->type == JSON_TRUE;
 314 }
 315
 316 double
 317 json_real(const struct json *json)
 318 {
 319     assert(json->type == JSON_REAL || json->type == JSON_INTEGER);
 320     return json->type == JSON_REAL ? json->u.real : json->u.integer;
 321 }
 322
 323 int64_t
 324 json_integer(const struct json *json)
 325 {
 326     assert(json->type == JSON_INTEGER);
 327     return json->u.integer;
 328 }
 329 \f
 330 static void json_destroy_object(struct shash *object);
 331 static void json_destroy_array(struct json_array *array);
 332
 333 /* Frees 'json' and everything it points to, recursively. */
 334 void
 335 json_destroy(struct json *json)
 336 {
 337     if (json) {
 338         switch (json->type) {
 339         case JSON_OBJECT:
 340             json_destroy_object(json->u.object);
 341             break;
 342
 343         case JSON_ARRAY:
 344             json_destroy_array(&json->u.array);
 345             break;
 346
 347         case JSON_STRING:
 348             free(json->u.string);
 349             break;
 350
 351         case JSON_NULL:
 352         case JSON_FALSE:
 353         case JSON_TRUE:
 354         case JSON_INTEGER:
 355         case JSON_REAL:
 356             break;
 357
 358         case JSON_N_TYPES:
 359             NOT_REACHED();
 360         }
 361         free(json);
 362     }
 363 }
 364
 365 static void
 366 json_destroy_object(struct shash *object)
 367 {
 368     struct shash_node *node, *next;
 369
 370     SHASH_FOR_EACH_SAFE (node, next, object) {
 371         struct json *value = node->data;
 372
 373         json_destroy(value);
 374         shash_delete(object, node);
 375     }
 376     shash_destroy(object);
 377     free(object);
 378 }
 379
 380 static void
 381 json_destroy_array(struct json_array *array)
 382 {
 383     size_t i;
 384
 385     for (i = 0; i < array->n; i++) {
 386         json_destroy(array->elems[i]);
 387     }
 388     free(array->elems);
 389 }
 390 \f
 391 static struct json *json_clone_object(const struct shash *object);
 392 static struct json *json_clone_array(const struct json_array *array);
 393
 394 /* Returns a deep copy of 'json'. */
 395 struct json *
 396 json_clone(const struct json *json)
 397 {
 398     switch (json->type) {
 399     case JSON_OBJECT:
 400         return json_clone_object(json->u.object);
 401
 402     case JSON_ARRAY:
 403         return json_clone_array(&json->u.array);
 404
 405     case JSON_STRING:
 406         return json_string_create(json->u.string);
 407
 408     case JSON_NULL:
 409     case JSON_FALSE:
 410     case JSON_TRUE:
 411         return json_create(json->type);
 412
 413     case JSON_INTEGER:
 414         return json_integer_create(json->u.integer);
 415
 416     case JSON_REAL:
 417         return json_real_create(json->u.real);
 418
 419     case JSON_N_TYPES:
 420     default:
 421         NOT_REACHED();
 422     }
 423 }
 424
 425 static struct json *
 426 json_clone_object(const struct shash *object)
 427 {
 428     struct shash_node *node;
 429     struct json *json;
 430
 431     json = json_object_create();
 432     SHASH_FOR_EACH (node, object) {
 433         struct json *value = node->data;
 434         json_object_put(json, node->name, json_clone(value));
 435     }
 436     return json;
 437 }
 438
 439 static struct json *
 440 json_clone_array(const struct json_array *array)
 441 {
 442     struct json **elems;
 443     size_t i;
 444
 445     elems = xmalloc(array->n * sizeof *elems);
 446     for (i = 0; i < array->n; i++) {
 447         elems[i] = json_clone(array->elems[i]);
 448     }
 449     return json_array_create(elems, array->n);
 450 }
 451 \f
 452 static size_t
 453 json_hash_object(const struct shash *object, size_t basis)
 454 {
 455     const struct shash_node **nodes;
 456     size_t n, i;
 457
 458     nodes = shash_sort(object);
 459     n = shash_count(object);
 460     for (i = 0; i < n; i++) {
 461         const struct shash_node *node = nodes[i];
 462         basis = hash_string(node->name, basis);
 463         basis = json_hash(node->data, basis);
 464     }
 465     return basis;
 466 }
 467
 468 static size_t
 469 json_hash_array(const struct json_array *array, size_t basis)
 470 {
 471     size_t i;
 472
 473     basis = hash_int(array->n, basis);
 474     for (i = 0; i < array->n; i++) {
 475         basis = json_hash(array->elems[i], basis);
 476     }
 477     return basis;
 478 }
 479
 480 size_t
 481 json_hash(const struct json *json, size_t basis)
 482 {
 483     switch (json->type) {
 484     case JSON_OBJECT:
 485         return json_hash_object(json->u.object, basis);
 486
 487     case JSON_ARRAY:
 488         return json_hash_array(&json->u.array, basis);
 489
 490     case JSON_STRING:
 491         return hash_string(json->u.string, basis);
 492
 493     case JSON_NULL:
 494     case JSON_FALSE:
 495     case JSON_TRUE:
 496         return hash_int(json->type << 8, basis);
 497
 498     case JSON_INTEGER:
 499         return hash_int(json->u.integer, basis);
 500
 501     case JSON_REAL:
 502         return hash_double(json->u.real, basis);
 503
 504     case JSON_N_TYPES:
 505     default:
 506         NOT_REACHED();
 507     }
 508 }
 509
 510 static bool
 511 json_equal_object(const struct shash *a, const struct shash *b)
 512 {
 513     struct shash_node *a_node;
 514
 515     if (shash_count(a) != shash_count(b)) {
 516         return false;
 517     }
 518
 519     SHASH_FOR_EACH (a_node, a) {
 520         struct shash_node *b_node = shash_find(b, a_node->name);
 521         if (!b_node || !json_equal(a_node->data, b_node->data)) {
 522             return false;
 523         }
 524     }
 525
 526     return true;
 527 }
 528
 529 static bool
 530 json_equal_array(const struct json_array *a, const struct json_array *b)
 531 {
 532     size_t i;
 533
 534     if (a->n != b->n) {
 535         return false;
 536     }
 537
 538     for (i = 0; i < a->n; i++) {
 539         if (!json_equal(a->elems[i], b->elems[i])) {
 540             return false;
 541         }
 542     }
 543
 544     return true;
 545 }
 546
 547 bool
 548 json_equal(const struct json *a, const struct json *b)
 549 {
 550     if (a->type != b->type) {
 551         return false;
 552     }
 553
 554     switch (a->type) {
 555     case JSON_OBJECT:
 556         return json_equal_object(a->u.object, b->u.object);
 557
 558     case JSON_ARRAY:
 559         return json_equal_array(&a->u.array, &b->u.array);
 560
 561     case JSON_STRING:
 562         return !strcmp(a->u.string, b->u.string);
 563
 564     case JSON_NULL:
 565     case JSON_FALSE:
 566     case JSON_TRUE:
 567         return true;
 568
 569     case JSON_INTEGER:
 570         return a->u.integer == b->u.integer;
 571
 572     case JSON_REAL:
 573         return a->u.real == b->u.real;
 574
 575     case JSON_N_TYPES:
 576     default:
 577         NOT_REACHED();
 578     }
 579 }
 580 \f
 581 /* Lexical analysis. */
 582
 583 static void
 584 json_lex_keyword(struct json_parser *p)
 585 {
 586     struct json_token token;
 587     const char *s;
 588
 589     s = ds_cstr(&p->buffer);
 590     if (!strcmp(s, "false")) {
 591         token.type = T_FALSE;
 592     } else if (!strcmp(s, "true")) {
 593         token.type = T_TRUE;
 594     } else if (!strcmp(s, "null")) {
 595         token.type = T_NULL;
 596     } else {
 597         json_error(p, "invalid keyword '%s'", s);
 598         return;
 599     }
 600     json_parser_input(p, &token);
 601 }
 602
 603 static void
 604 json_lex_number(struct json_parser *p)
 605 {
 606     const char *cp = ds_cstr(&p->buffer);
 607     unsigned long long int significand = 0;
 608     struct json_token token;
 609     bool imprecise = false;
 610     bool negative = false;
 611     int pow10 = 0;
 612
 613     /* Leading minus sign. */
 614     if (*cp == '-') {
 615         negative = true;
 616         cp++;
 617     }
 618
 619     /* At least one integer digit, but 0 may not be used as a leading digit for
 620      * a longer number. */
 621     significand = 0;
 622     if (*cp == '0') {
 623         cp++;
 624         if (isdigit(*cp)) {
 625             json_error(p, "leading zeros not allowed");
 626             return;
 627         }
 628     } else if (isdigit(*cp)) {
 629         do {
 630             if (significand <= ULLONG_MAX / 10) {
 631                 significand = significand * 10 + (*cp - '0');
 632             } else {
 633                 pow10++;
 634                 if (*cp != '0') {
 635                     imprecise = true;
 636                 }
 637             }
 638             cp++;
 639         } while (isdigit(*cp));
 640     } else {
 641         json_error(p, "'-' must be followed by digit");
 642         return;
 643     }
 644
 645     /* Optional fraction. */
 646     if (*cp == '.') {
 647         cp++;
 648         if (!isdigit(*cp)) {
 649             json_error(p, "decimal point must be followed by digit");
 650             return;
 651         }
 652         do {
 653             if (significand <= ULLONG_MAX / 10) {
 654                 significand = significand * 10 + (*cp - '0');
 655                 pow10--;
 656             } else if (*cp != '0') {
 657                 imprecise = true;
 658             }
 659             cp++;
 660         } while (isdigit(*cp));
 661     }
 662
 663     /* Optional exponent. */
 664     if (*cp == 'e' || *cp == 'E') {
 665         bool negative_exponent = false;
 666         int exponent;
 667
 668         cp++;
 669         if (*cp == '+') {
 670             cp++;
 671         } else if (*cp == '-') {
 672             negative_exponent = true;
 673             cp++;
 674         }
 675
 676         if (!isdigit(*cp)) {
 677             json_error(p, "exponent must contain at least one digit");
 678             return;
 679         }
 680
 681         exponent = 0;
 682         do {
 683             if (exponent >= INT_MAX / 10) {
 684                 json_error(p, "exponent outside valid range");
 685                 return;
 686             }
 687             exponent = exponent * 10 + (*cp - '0');
 688             cp++;
 689         } while (isdigit(*cp));
 690
 691         if (negative_exponent) {
 692             pow10 -= exponent;
 693         } else {
 694             pow10 += exponent;
 695         }
 696     }
 697
 698     if (*cp != '\0') {
 699         json_error(p, "syntax error in number");
 700         return;
 701     }
 702
 703     /* Figure out number.
 704      *
 705      * We suppress negative zeros as a matter of policy. */
 706     if (!significand) {
 707         token.type = T_INTEGER;
 708         token.u.integer = 0;
 709         json_parser_input(p, &token);
 710         return;
 711     }
 712
 713     if (!imprecise) {
 714         while (pow10 > 0 && significand < ULLONG_MAX / 10) {
 715             significand *= 10;
 716             pow10--;
 717         }
 718         while (pow10 < 0 && significand % 10 == 0) {
 719             significand /= 10;
 720             pow10++;
 721         }
 722         if (pow10 == 0
 723             && significand <= (negative
 724                                ? (unsigned long long int) LLONG_MAX + 1
 725                                : LLONG_MAX)) {
 726             token.type = T_INTEGER;
 727             token.u.integer = negative ? -significand : significand;
 728             json_parser_input(p, &token);
 729             return;
 730         }
 731     }
 732
 733     token.type = T_REAL;
 734     if (!str_to_double(ds_cstr(&p->buffer), &token.u.real)) {
 735         json_error(p, "number outside valid range");
 736         return;
 737     }
 738     /* Suppress negative zero. */
 739     if (token.u.real == 0) {
 740         token.u.real = 0;
 741     }
 742     json_parser_input(p, &token);
 743 }
 744
 745 static const char *
 746 json_lex_4hex(const char *cp, const char *end, int *valuep)
 747 {
 748     unsigned int value;
 749
 750     if (cp + 4 > end) {
 751         return "quoted string ends within \\u escape";
 752     }
 753
 754     value = hexits_value(cp, 4, NULL);
 755     if (value == UINT_MAX) {
 756         return "malformed \\u escape";
 757     }
 758     if (!value) {
 759         return "null bytes not supported in quoted strings";
 760     }
 761     *valuep = value;
 762     return NULL;
 763 }
 764
 765 static const char *
 766 json_lex_unicode(const char *cp, const char *end, struct ds *out)
 767 {
 768     const char *error;
 769     int c0, c1;
 770
 771     error = json_lex_4hex(cp, end, &c0);
 772     if (error) {
 773         ds_clear(out);
 774         ds_put_cstr(out, error);
 775         return NULL;
 776     }
 777     cp += 4;
 778     if (!uc_is_leading_surrogate(c0)) {
 779         ds_put_utf8(out, c0);
 780         return cp;
 781     }
 782
 783     if (cp + 2 > end || *cp++ != '\\' || *cp++ != 'u') {
 784         ds_clear(out);
 785         ds_put_cstr(out, "malformed escaped surrogate pair");
 786         return NULL;
 787     }
 788
 789     error = json_lex_4hex(cp, end, &c1);
 790     if (error) {
 791         ds_clear(out);
 792         ds_put_cstr(out, error);
 793         return NULL;
 794     }
 795     cp += 4;
 796     if (!uc_is_trailing_surrogate(c1)) {
 797         ds_clear(out);
 798         ds_put_cstr(out, "second half of escaped surrogate pair is not "
 799                     "trailing surrogate");
 800         return NULL;
 801     }
 802
 803     ds_put_utf8(out, utf16_decode_surrogate_pair(c0, c1));
 804     return cp;
 805 }
 806
 807 bool
 808 json_string_unescape(const char *in, size_t in_len, char **outp)
 809 {
 810     const char *end = in + in_len;
 811     bool ok = false;
 812     struct ds out;
 813
 814     ds_init(&out);
 815     ds_reserve(&out, in_len);
 816     if (in_len > 0 && in[in_len - 1] == '\\') {
 817         ds_put_cstr(&out, "quoted string may not end with backslash");
 818         goto exit;
 819     }
 820     while (in < end) {
 821         if (*in == '"') {
 822             ds_clear(&out);
 823             ds_put_cstr(&out, "quoted string may not include unescaped \"");
 824             goto exit;
 825         }
 826         if (*in != '\\') {
 827             ds_put_char(&out, *in++);
 828             continue;
 829         }
 830
 831         in++;
 832         switch (*in++) {
 833         case '"': case '\\': case '/':
 834             ds_put_char(&out, in[-1]);
 835             break;
 836
 837         case 'b':
 838             ds_put_char(&out, '\b');
 839             break;
 840
 841         case 'f':
 842             ds_put_char(&out, '\f');
 843             break;
 844
 845         case 'n':
 846             ds_put_char(&out, '\n');
 847             break;
 848
 849         case 'r':
 850             ds_put_char(&out, '\r');
 851             break;
 852
 853         case 't':
 854             ds_put_char(&out, '\t');
 855             break;
 856
 857         case 'u':
 858             in = json_lex_unicode(in, end, &out);
 859             if (!in) {
 860                 goto exit;
 861             }
 862             break;
 863
 864         default:
 865             ds_clear(&out);
 866             ds_put_format(&out, "bad escape \\%c", in[-1]);
 867             goto exit;
 868         }
 869     }
 870     ok = true;
 871
 872 exit:
 873     *outp = ds_cstr(&out);
 874     return ok;
 875 }
 876
 877 static void
 878 json_parser_input_string(struct json_parser *p, const char *s)
 879 {
 880     struct json_token token;
 881
 882     token.type = T_STRING;
 883     token.u.string = s;
 884     json_parser_input(p, &token);
 885 }
 886
 887 static void
 888 json_lex_string(struct json_parser *p)
 889 {
 890     const char *raw = ds_cstr(&p->buffer);
 891     if (!strchr(raw, '\\')) {
 892         json_parser_input_string(p, raw);
 893     } else {
 894         char *cooked;
 895
 896         if (json_string_unescape(raw, strlen(raw), &cooked)) {
 897             json_parser_input_string(p, cooked);
 898         } else {
 899             json_error(p, "%s", cooked);
 900         }
 901
 902         free(cooked);
 903     }
 904 }
 905
 906 static bool
 907 json_lex_input(struct json_parser *p, unsigned char c)
 908 {
 909     struct json_token token;
 910
 911     p->byte_number++;
 912     if (c == '\n') {
 913         p->column_number = 0;
 914         p->line_number++;
 915     } else {
 916         p->column_number++;
 917     }
 918
 919     switch (p->lex_state) {
 920     case JSON_LEX_START:
 921         switch (c) {
 922         case ' ': case '\t': case '\n': case '\r':
 923             /* Nothing to do. */
 924             return true;
 925
 926         case 'a': case 'b': case 'c': case 'd': case 'e':
 927         case 'f': case 'g': case 'h': case 'i': case 'j':
 928         case 'k': case 'l': case 'm': case 'n': case 'o':
 929         case 'p': case 'q': case 'r': case 's': case 't':
 930         case 'u': case 'v': case 'w': case 'x': case 'y':
 931         case 'z':
 932             p->lex_state = JSON_LEX_KEYWORD;
 933             break;
 934
 935         case '[': case '{': case ']': case '}': case ':': case ',':
 936             token.type = c;
 937             json_parser_input(p, &token);
 938             return true;
 939
 940         case '-':
 941         case '0': case '1': case '2': case '3': case '4':
 942         case '5': case '6': case '7': case '8': case '9':
 943             p->lex_state = JSON_LEX_NUMBER;
 944             break;
 945
 946         case '"':
 947             p->lex_state = JSON_LEX_STRING;
 948             return true;
 949
 950         default:
 951             if (isprint(c)) {
 952                 json_error(p, "invalid character '%c'", c);
 953             } else {
 954                 json_error(p, "invalid character U+%04x", c);
 955             }
 956             return true;
 957         }
 958         break;
 959
 960     case JSON_LEX_KEYWORD:
 961         if (!isalpha((unsigned char) c)) {
 962             json_lex_keyword(p);
 963             return false;
 964         }
 965         break;
 966
 967     case JSON_LEX_NUMBER:
 968         if (!strchr(".0123456789eE-+", c)) {
 969             json_lex_number(p);
 970             return false;
 971         }
 972         break;
 973
 974     case JSON_LEX_STRING:
 975         if (c == '\\') {
 976             p->lex_state = JSON_LEX_ESCAPE;
 977         } else if (c == '"') {
 978             json_lex_string(p);
 979             return true;
 980         } else if (c < 0x20) {
 981             json_error(p, "U+%04X must be escaped in quoted string", c);
 982             return true;
 983         }
 984         break;
 985
 986     case JSON_LEX_ESCAPE:
 987         p->lex_state = JSON_LEX_STRING;
 988         break;
 989
 990     default:
 991         abort();
 992     }
 993     ds_put_char(&p->buffer, c);
 994     return true;
 995 }
 996 \f
 997 /* Parsing. */
 998
 999 /* Parses 'string' as a JSON object or array and returns a newly allocated
1000  * 'struct json'.  The caller must free the returned structure with
1001  * json_destroy() when it is no longer needed.
1002  *
1003  * 'string' must be encoded in UTF-8.
1004  *
1005  * If 'string' is valid JSON, then the returned 'struct json' will be either an
1006  * object (JSON_OBJECT) or an array (JSON_ARRAY).
1007  *
1008  * If 'string' is not valid JSON, then the returned 'struct json' will be a
1009  * string (JSON_STRING) that describes the particular error encountered during
1010  * parsing.  (This is an acceptable means of error reporting because at its top
1011  * level JSON must be either an object or an array; a bare string is not
1012  * valid.) */
1013 struct json *
1014 json_from_string(const char *string)
1015 {
1016     struct json_parser *p = json_parser_create(JSPF_TRAILER);
1017     json_parser_feed(p, string, strlen(string));
1018     return json_parser_finish(p);
1019 }
1020
1021 /* Reads the file named 'file_name', parses its contents as a JSON object or
1022  * array, and returns a newly allocated 'struct json'.  The caller must free
1023  * the returned structure with json_destroy() when it is no longer needed.
1024  *
1025  * The file must be encoded in UTF-8.
1026  *
1027  * See json_from_string() for return value semantics.
1028  */
1029 struct json *
1030 json_from_file(const char *file_name)
1031 {
1032     struct json *json;
1033     FILE *stream;
1034
1035     stream = fopen(file_name, "r");
1036     if (!stream) {
1037         return json_string_create_nocopy(
1038             xasprintf("error opening \"%s\": %s", file_name, strerror(errno)));
1039     }
1040     json = json_from_stream(stream);
1041     fclose(stream);
1042
1043     return json;
1044 }
1045
1046 /* Parses the contents of 'stream' as a JSON object or array, and returns a
1047  * newly allocated 'struct json'.  The caller must free the returned structure
1048  * with json_destroy() when it is no longer needed.
1049  *
1050  * The file must be encoded in UTF-8.
1051  *
1052  * See json_from_string() for return value semantics.
1053  */
1054 struct json *
1055 json_from_stream(FILE *stream)
1056 {
1057     struct json_parser *p;
1058     struct json *json;
1059
1060     p = json_parser_create(JSPF_TRAILER);
1061     for (;;) {
1062         char buffer[BUFSIZ];
1063         size_t n;
1064
1065         n = fread(buffer, 1, sizeof buffer, stream);
1066         if (!n || json_parser_feed(p, buffer, n) != n) {
1067             break;
1068         }
1069     }
1070     json = json_parser_finish(p);
1071
1072     if (ferror(stream)) {
1073         json_destroy(json);
1074         json = json_string_create_nocopy(
1075             xasprintf("error reading JSON stream: %s", strerror(errno)));
1076     }
1077
1078     return json;
1079 }
1080
1081 struct json_parser *
1082 json_parser_create(int flags)
1083 {
1084     struct json_parser *p = xzalloc(sizeof *p);
1085     p->flags = flags;
1086     return p;
1087 }
1088
1089 size_t
1090 json_parser_feed(struct json_parser *p, const char *input, size_t n)
1091 {
1092     size_t i;
1093     for (i = 0; !p->done && i < n; ) {
1094         if (json_lex_input(p, input[i])) {
1095             i++;
1096         }
1097     }
1098     return i;
1099 }
1100
1101 bool
1102 json_parser_is_done(const struct json_parser *p)
1103 {
1104     return p->done;
1105 }
1106
1107 struct json *
1108 json_parser_finish(struct json_parser *p)
1109 {
1110     struct json *json;
1111
1112     switch (p->lex_state) {
1113     case JSON_LEX_START:
1114         break;
1115
1116     case JSON_LEX_STRING:
1117     case JSON_LEX_ESCAPE:
1118         json_error(p, "unexpected end of input in quoted string");
1119         break;
1120
1121     case JSON_LEX_NUMBER:
1122     case JSON_LEX_KEYWORD:
1123         json_lex_input(p, ' ');
1124         break;
1125     }
1126
1127     if (p->parse_state == JSON_PARSE_START) {
1128         json_error(p, "empty input stream");
1129     } else if (p->parse_state != JSON_PARSE_END) {
1130         json_error(p, "unexpected end of input");
1131     }
1132
1133     if (!p->error) {
1134         assert(p->height == 1);
1135         assert(p->stack[0].json != NULL);
1136         json = p->stack[--p->height].json;
1137     } else {
1138         json = json_string_create_nocopy(p->error);
1139         p->error = NULL;
1140     }
1141
1142     json_parser_abort(p);
1143
1144     return json;
1145 }
1146
1147 void
1148 json_parser_abort(struct json_parser *p)
1149 {
1150     if (p) {
1151         ds_destroy(&p->buffer);
1152         if (p->height) {
1153             json_destroy(p->stack[0].json);
1154         }
1155         free(p->stack);
1156         free(p->member_name);
1157         free(p->error);
1158         free(p);
1159     }
1160 }
1161
1162 static struct json_parser_node *
1163 json_parser_top(struct json_parser *p)
1164 {
1165     return &p->stack[p->height - 1];
1166 }
1167
1168 static void
1169 json_parser_put_value(struct json_parser *p, struct json *value)
1170 {
1171     struct json_parser_node *node = json_parser_top(p);
1172     if (node->json->type == JSON_OBJECT) {
1173         json_object_put(node->json, p->member_name, value);
1174         free(p->member_name);
1175         p->member_name = NULL;
1176     } else if (node->json->type == JSON_ARRAY) {
1177         json_array_add(node->json, value);
1178     } else {
1179         NOT_REACHED();
1180     }
1181 }
1182
1183 static void
1184 json_parser_push(struct json_parser *p,
1185                  struct json *new_json, enum json_parse_state new_state)
1186 {
1187     if (p->height < JSON_MAX_HEIGHT) {
1188         struct json_parser_node *node;
1189
1190         if (p->height >= p->allocated_height) {
1191             p->stack = x2nrealloc(p->stack, &p->allocated_height,
1192                                   sizeof *p->stack);
1193         }
1194
1195         if (p->height > 0) {
1196             json_parser_put_value(p, new_json);
1197         }
1198
1199         node = &p->stack[p->height++];
1200         node->json = new_json;
1201         p->parse_state = new_state;
1202     } else {
1203         json_destroy(new_json);
1204         json_error(p, "input exceeds maximum nesting depth %d",
1205                    JSON_MAX_HEIGHT);
1206     }
1207 }
1208
1209 static void
1210 json_parser_push_object(struct json_parser *p)
1211 {
1212     json_parser_push(p, json_object_create(), JSON_PARSE_OBJECT_INIT);
1213 }
1214
1215 static void
1216 json_parser_push_array(struct json_parser *p)
1217 {
1218     json_parser_push(p, json_array_create_empty(), JSON_PARSE_ARRAY_INIT);
1219 }
1220
1221 static void
1222 json_parse_value(struct json_parser *p, struct json_token *token,
1223                  enum json_parse_state next_state)
1224 {
1225     struct json *value;
1226
1227     switch (token->type) {
1228     case T_FALSE:
1229         value = json_boolean_create(false);
1230         break;
1231
1232     case T_NULL:
1233         value = json_null_create();
1234         break;
1235
1236     case T_TRUE:
1237         value = json_boolean_create(true);
1238         break;
1239
1240     case '{':
1241         json_parser_push_object(p);
1242         return;
1243
1244     case '[':
1245         json_parser_push_array(p);
1246         return;
1247
1248     case T_INTEGER:
1249         value = json_integer_create(token->u.integer);
1250         break;
1251
1252     case T_REAL:
1253         value = json_real_create(token->u.real);
1254         break;
1255
1256     case T_STRING:
1257         value = json_string_create(token->u.string);
1258         break;
1259
1260     case T_EOF:
1261     case '}':
1262     case ']':
1263     case ':':
1264     case ',':
1265     default:
1266         json_error(p, "syntax error expecting value");
1267         return;
1268     }
1269
1270     json_parser_put_value(p, value);
1271     p->parse_state = next_state;
1272 }
1273
1274 static void
1275 json_parser_pop(struct json_parser *p)
1276 {
1277     struct json_parser_node *node;
1278
1279     /* Conserve memory. */
1280     node = json_parser_top(p);
1281     if (node->json->type == JSON_ARRAY) {
1282         json_array_trim(node->json);
1283     }
1284
1285     /* Pop off the top-of-stack. */
1286     if (p->height == 1) {
1287         p->parse_state = JSON_PARSE_END;
1288         if (!(p->flags & JSPF_TRAILER)) {
1289             p->done = true;
1290         }
1291     } else {
1292         p->height--;
1293         node = json_parser_top(p);
1294         if (node->json->type == JSON_ARRAY) {
1295             p->parse_state = JSON_PARSE_ARRAY_NEXT;
1296         } else if (node->json->type == JSON_OBJECT) {
1297             p->parse_state = JSON_PARSE_OBJECT_NEXT;
1298         } else {
1299             NOT_REACHED();
1300         }
1301     }
1302 }
1303
1304 static void
1305 json_parser_input(struct json_parser *p, struct json_token *token)
1306 {
1307     switch (p->parse_state) {
1308     case JSON_PARSE_START:
1309         if (token->type == '{') {
1310             json_parser_push_object(p);
1311         } else if (token->type == '[') {
1312             json_parser_push_array(p);
1313         } else {
1314             json_error(p, "syntax error at beginning of input");
1315         }
1316         break;
1317
1318     case JSON_PARSE_END:
1319         json_error(p, "trailing garbage at end of input");
1320         break;
1321
1322     case JSON_PARSE_OBJECT_INIT:
1323         if (token->type == '}') {
1324             json_parser_pop(p);
1325             break;
1326         }
1327         /* Fall through. */
1328     case JSON_PARSE_OBJECT_NAME:
1329         if (token->type == T_STRING) {
1330             p->member_name = xstrdup(token->u.string);
1331             p->parse_state = JSON_PARSE_OBJECT_COLON;
1332         } else {
1333             json_error(p, "syntax error parsing object expecting string");
1334         }
1335         break;
1336
1337     case JSON_PARSE_OBJECT_COLON:
1338         if (token->type == ':') {
1339             p->parse_state = JSON_PARSE_OBJECT_VALUE;
1340         } else {
1341             json_error(p, "syntax error parsing object expecting ':'");
1342         }
1343         break;
1344
1345     case JSON_PARSE_OBJECT_VALUE:
1346         json_parse_value(p, token, JSON_PARSE_OBJECT_NEXT);
1347         break;
1348
1349     case JSON_PARSE_OBJECT_NEXT:
1350         if (token->type == ',') {
1351             p->parse_state = JSON_PARSE_OBJECT_NAME;
1352         } else if (token->type == '}') {
1353             json_parser_pop(p);
1354         } else {
1355             json_error(p, "syntax error expecting '}' or ','");
1356         }
1357         break;
1358
1359     case JSON_PARSE_ARRAY_INIT:
1360         if (token->type == ']') {
1361             json_parser_pop(p);
1362             break;
1363         }
1364         /* Fall through. */
1365     case JSON_PARSE_ARRAY_VALUE:
1366         json_parse_value(p, token, JSON_PARSE_ARRAY_NEXT);
1367         break;
1368
1369     case JSON_PARSE_ARRAY_NEXT:
1370         if (token->type == ',') {
1371             p->parse_state = JSON_PARSE_ARRAY_VALUE;
1372         } else if (token->type == ']') {
1373             json_parser_pop(p);
1374         } else {
1375             json_error(p, "syntax error expecting ']' or ','");
1376         }
1377         break;
1378
1379     default:
1380         abort();
1381     }
1382
1383     p->lex_state = JSON_LEX_START;
1384     ds_clear(&p->buffer);
1385 }
1386
1387 static struct json *
1388 json_create(enum json_type type)
1389 {
1390     struct json *json = xmalloc(sizeof *json);
1391     json->type = type;
1392     return json;
1393 }
1394
1395 static void
1396 json_error(struct json_parser *p, const char *format, ...)
1397 {
1398     if (!p->error) {
1399         struct ds msg;
1400         va_list args;
1401
1402         ds_init(&msg);
1403         ds_put_format(&msg, "line %d, column %d, byte %d: ",
1404                       p->line_number, p->column_number, p->byte_number);
1405         va_start(args, format);
1406         ds_put_format_valist(&msg, format, args);
1407         va_end(args);
1408
1409         p->error = ds_steal_cstr(&msg);
1410
1411         p->done = true;
1412     }
1413 }
1414 \f
1415 #define SPACES_PER_LEVEL 2
1416
1417 struct json_serializer {
1418     struct ds *ds;
1419     int depth;
1420     int flags;
1421 };
1422
1423 static void json_serialize(const struct json *, struct json_serializer *);
1424 static void json_serialize_object(const struct shash *object,
1425                                   struct json_serializer *);
1426 static void json_serialize_array(const struct json_array *,
1427                                  struct json_serializer *);
1428 static void json_serialize_string(const char *, struct ds *);
1429
1430 /* Converts 'json' to a string in JSON format, encoded in UTF-8, and returns
1431  * that string.  The caller is responsible for freeing the returned string,
1432  * with free(), when it is no longer needed.
1433  *
1434  * If 'flags' contains JSSF_PRETTY, the output is pretty-printed with each
1435  * nesting level introducing an additional indentation.  Otherwise, the
1436  * returned string does not contain any new-line characters.
1437  *
1438  * If 'flags' contains JSSF_SORT, members of objects in the output are sorted
1439  * in bytewise lexicographic order for reproducibility.  Otherwise, members of
1440  * objects are output in an indeterminate order.
1441  *
1442  * The returned string is valid JSON only if 'json' represents an array or an
1443  * object, since a bare literal does not satisfy the JSON grammar. */
1444 char *
1445 json_to_string(const struct json *json, int flags)
1446 {
1447     struct ds ds;
1448
1449     ds_init(&ds);
1450     json_to_ds(json, flags, &ds);
1451     return ds_steal_cstr(&ds);
1452 }
1453
1454 /* Same as json_to_string(), but the output is appended to 'ds'. */
1455 void
1456 json_to_ds(const struct json *json, int flags, struct ds *ds)
1457 {
1458     struct json_serializer s;
1459
1460     s.ds = ds;
1461     s.depth = 0;
1462     s.flags = flags;
1463     json_serialize(json, &s);
1464 }
1465
1466 static void
1467 json_serialize(const struct json *json, struct json_serializer *s)
1468 {
1469     struct ds *ds = s->ds;
1470
1471     switch (json->type) {
1472     case JSON_NULL:
1473         ds_put_cstr(ds, "null");
1474         break;
1475
1476     case JSON_FALSE:
1477         ds_put_cstr(ds, "false");
1478         break;
1479
1480     case JSON_TRUE:
1481         ds_put_cstr(ds, "true");
1482         break;
1483
1484     case JSON_OBJECT:
1485         json_serialize_object(json->u.object, s);
1486         break;
1487
1488     case JSON_ARRAY:
1489         json_serialize_array(&json->u.array, s);
1490         break;
1491
1492     case JSON_INTEGER:
1493         ds_put_format(ds, "%lld", json->u.integer);
1494         break;
1495
1496     case JSON_REAL:
1497         ds_put_format(ds, "%.*g", DBL_DIG, json->u.real);
1498         break;
1499
1500     case JSON_STRING:
1501         json_serialize_string(json->u.string, ds);
1502         break;
1503
1504     case JSON_N_TYPES:
1505     default:
1506         NOT_REACHED();
1507     }
1508 }
1509
1510 static void
1511 indent_line(struct json_serializer *s)
1512 {
1513     if (s->flags & JSSF_PRETTY) {
1514         ds_put_char(s->ds, '\n');
1515         ds_put_char_multiple(s->ds, ' ', SPACES_PER_LEVEL * s->depth);
1516     }
1517 }
1518
1519 static void
1520 json_serialize_object_member(size_t i, const struct shash_node *node,
1521                              struct json_serializer *s)
1522 {
1523     struct ds *ds = s->ds;
1524
1525     if (i) {
1526         ds_put_char(ds, ',');
1527         indent_line(s);
1528     }
1529
1530     json_serialize_string(node->name, ds);
1531     ds_put_char(ds, ':');
1532     if (s->flags & JSSF_PRETTY) {
1533         ds_put_char(ds, ' ');
1534     }
1535     json_serialize(node->data, s);
1536 }
1537
1538 static void
1539 json_serialize_object(const struct shash *object, struct json_serializer *s)
1540 {
1541     struct ds *ds = s->ds;
1542
1543     ds_put_char(ds, '{');
1544
1545     s->depth++;
1546     indent_line(s);
1547
1548     if (s->flags & JSSF_SORT) {
1549         const struct shash_node **nodes;
1550         size_t n, i;
1551
1552         nodes = shash_sort(object);
1553         n = shash_count(object);
1554         for (i = 0; i < n; i++) {
1555             json_serialize_object_member(i, nodes[i], s);
1556         }
1557         free(nodes);
1558     } else {
1559         struct shash_node *node;
1560         size_t i;
1561
1562         i = 0;
1563         SHASH_FOR_EACH (node, object) {
1564             json_serialize_object_member(i++, node, s);
1565         }
1566     }
1567
1568     ds_put_char(ds, '}');
1569     s->depth--;
1570 }
1571
1572 static void
1573 json_serialize_array(const struct json_array *array, struct json_serializer *s)
1574 {
1575     struct ds *ds = s->ds;
1576     size_t i;
1577
1578     ds_put_char(ds, '[');
1579     s->depth++;
1580
1581     if (array->n > 0) {
1582         indent_line(s);
1583
1584         for (i = 0; i < array->n; i++) {
1585             if (i) {
1586                 ds_put_char(ds, ',');
1587                 indent_line(s);
1588             }
1589             json_serialize(array->elems[i], s);
1590         }
1591     }
1592
1593     s->depth--;
1594     ds_put_char(ds, ']');
1595 }
1596
1597 static void
1598 json_serialize_string(const char *string, struct ds *ds)
1599 {
1600     uint8_t c;
1601
1602     ds_put_char(ds, '"');
1603     while ((c = *string++) != '\0') {
1604         switch (c) {
1605         case '"':
1606             ds_put_cstr(ds, "\\\"");
1607             break;
1608
1609         case '\\':
1610             ds_put_cstr(ds, "\\\\");
1611             break;
1612
1613         case '\b':
1614             ds_put_cstr(ds, "\\b");
1615             break;
1616
1617         case '\f':
1618             ds_put_cstr(ds, "\\f");
1619             break;
1620
1621         case '\n':
1622             ds_put_cstr(ds, "\\n");
1623             break;
1624
1625         case '\r':
1626             ds_put_cstr(ds, "\\r");
1627             break;
1628
1629         case '\t':
1630             ds_put_cstr(ds, "\\t");
1631             break;
1632
1633         default:
1634             if (c >= 32) {
1635                 ds_put_char(ds, c);
1636             } else {
1637                 ds_put_format(ds, "\\u%04x", c);
1638             }
1639             break;
1640         }
1641     }
1642     ds_put_char(ds, '"');
1643 }