pintos-os.org Git - openvswitch/blob - lib/json.c

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