lib/json.c

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