lib/json.c

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