lib/json.c

   1 /*
   2  * Copyright (c) 2009, 2010, 2011, 2012, 2014, 2015 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     OVS_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             OVS_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         OVS_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     free(nodes);
 465     return basis;
 466 }
 467
 468 static size_t
 469 json_hash_array(const struct json_array *array, size_t basis)
 470 {
 471     size_t i;
 472
 473     basis = hash_int(array->n, basis);
 474     for (i = 0; i < array->n; i++) {
 475         basis = json_hash(array->elems[i], basis);
 476     }
 477     return basis;
 478 }
 479
 480 size_t
 481 json_hash(const struct json *json, size_t basis)
 482 {
 483     switch (json->type) {
 484     case JSON_OBJECT:
 485         return json_hash_object(json->u.object, basis);
 486
 487     case JSON_ARRAY:
 488         return json_hash_array(&json->u.array, basis);
 489
 490     case JSON_STRING:
 491         return hash_string(json->u.string, basis);
 492
 493     case JSON_NULL:
 494     case JSON_FALSE:
 495     case JSON_TRUE:
 496         return hash_int(json->type << 8, basis);
 497
 498     case JSON_INTEGER:
 499         return hash_int(json->u.integer, basis);
 500
 501     case JSON_REAL:
 502         return hash_double(json->u.real, basis);
 503
 504     case JSON_N_TYPES:
 505     default:
 506         OVS_NOT_REACHED();
 507     }
 508 }
 509
 510 static bool
 511 json_equal_object(const struct shash *a, const struct shash *b)
 512 {
 513     struct shash_node *a_node;
 514
 515     if (shash_count(a) != shash_count(b)) {
 516         return false;
 517     }
 518
 519     SHASH_FOR_EACH (a_node, a) {
 520         struct shash_node *b_node = shash_find(b, a_node->name);
 521         if (!b_node || !json_equal(a_node->data, b_node->data)) {
 522             return false;
 523         }
 524     }
 525
 526     return true;
 527 }
 528
 529 static bool
 530 json_equal_array(const struct json_array *a, const struct json_array *b)
 531 {
 532     size_t i;
 533
 534     if (a->n != b->n) {
 535         return false;
 536     }
 537
 538     for (i = 0; i < a->n; i++) {
 539         if (!json_equal(a->elems[i], b->elems[i])) {
 540             return false;
 541         }
 542     }
 543
 544     return true;
 545 }
 546
 547 bool
 548 json_equal(const struct json *a, const struct json *b)
 549 {
 550     if (a->type != b->type) {
 551         return false;
 552     }
 553
 554     switch (a->type) {
 555     case JSON_OBJECT:
 556         return json_equal_object(a->u.object, b->u.object);
 557
 558     case JSON_ARRAY:
 559         return json_equal_array(&a->u.array, &b->u.array);
 560
 561     case JSON_STRING:
 562         return !strcmp(a->u.string, b->u.string);
 563
 564     case JSON_NULL:
 565     case JSON_FALSE:
 566     case JSON_TRUE:
 567         return true;
 568
 569     case JSON_INTEGER:
 570         return a->u.integer == b->u.integer;
 571
 572     case JSON_REAL:
 573         return a->u.real == b->u.real;
 574
 575     case JSON_N_TYPES:
 576     default:
 577         OVS_NOT_REACHED();
 578     }
 579 }
 580 \f
 581 /* Lexical analysis. */
 582
 583 static void
 584 json_lex_keyword(struct json_parser *p)
 585 {
 586     struct json_token token;
 587     const char *s;
 588
 589     s = ds_cstr(&p->buffer);
 590     if (!strcmp(s, "false")) {
 591         token.type = T_FALSE;
 592     } else if (!strcmp(s, "true")) {
 593         token.type = T_TRUE;
 594     } else if (!strcmp(s, "null")) {
 595         token.type = T_NULL;
 596     } else {
 597         json_error(p, "invalid keyword '%s'", s);
 598         return;
 599     }
 600     json_parser_input(p, &token);
 601 }
 602
 603 static void
 604 json_lex_number(struct json_parser *p)
 605 {
 606     const char *cp = ds_cstr(&p->buffer);
 607     unsigned long long int significand = 0;
 608     struct json_token token;
 609     bool imprecise = false;
 610     bool negative = false;
 611     int pow10 = 0;
 612
 613     /* Leading minus sign. */
 614     if (*cp == '-') {
 615         negative = true;
 616         cp++;
 617     }
 618
 619     /* At least one integer digit, but 0 may not be used as a leading digit for
 620      * a longer number. */
 621     significand = 0;
 622     if (*cp == '0') {
 623         cp++;
 624         if (isdigit((unsigned char) *cp)) {
 625             json_error(p, "leading zeros not allowed");
 626             return;
 627         }
 628     } else if (isdigit((unsigned char) *cp)) {
 629         do {
 630             if (significand <= ULLONG_MAX / 10) {
 631                 significand = significand * 10 + (*cp - '0');
 632             } else {
 633                 pow10++;
 634                 if (*cp != '0') {
 635                     imprecise = true;
 636                 }
 637             }
 638             cp++;
 639         } while (isdigit((unsigned char) *cp));
 640     } else {
 641         json_error(p, "'-' must be followed by digit");
 642         return;
 643     }
 644
 645     /* Optional fraction. */
 646     if (*cp == '.') {
 647         cp++;
 648         if (!isdigit((unsigned char) *cp)) {
 649             json_error(p, "decimal point must be followed by digit");
 650             return;
 651         }
 652         do {
 653             if (significand <= ULLONG_MAX / 10) {
 654                 significand = significand * 10 + (*cp - '0');
 655                 pow10--;
 656             } else if (*cp != '0') {
 657                 imprecise = true;
 658             }
 659             cp++;
 660         } while (isdigit((unsigned char) *cp));
 661     }
 662
 663     /* Optional exponent. */
 664     if (*cp == 'e' || *cp == 'E') {
 665         bool negative_exponent = false;
 666         int exponent;
 667
 668         cp++;
 669         if (*cp == '+') {
 670             cp++;
 671         } else if (*cp == '-') {
 672             negative_exponent = true;
 673             cp++;
 674         }
 675
 676         if (!isdigit((unsigned char) *cp)) {
 677             json_error(p, "exponent must contain at least one digit");
 678             return;
 679         }
 680
 681         exponent = 0;
 682         do {
 683             if (exponent >= INT_MAX / 10) {
 684                 json_error(p, "exponent outside valid range");
 685                 return;
 686             }
 687             exponent = exponent * 10 + (*cp - '0');
 688             cp++;
 689         } while (isdigit((unsigned char) *cp));
 690
 691         if (negative_exponent) {
 692             pow10 -= exponent;
 693         } else {
 694             pow10 += exponent;
 695         }
 696     }
 697
 698     if (*cp != '\0') {
 699         json_error(p, "syntax error in number");
 700         return;
 701     }
 702
 703     /* Figure out number.
 704      *
 705      * We suppress negative zeros as a matter of policy. */
 706     if (!significand) {
 707         token.type = T_INTEGER;
 708         token.u.integer = 0;
 709         json_parser_input(p, &token);
 710         return;
 711     }
 712
 713     if (!imprecise) {
 714         while (pow10 > 0 && significand < ULLONG_MAX / 10) {
 715             significand *= 10;
 716             pow10--;
 717         }
 718         while (pow10 < 0 && significand % 10 == 0) {
 719             significand /= 10;
 720             pow10++;
 721         }
 722         if (pow10 == 0
 723             && significand <= (negative
 724                                ? (unsigned long long int) LLONG_MAX + 1
 725                                : LLONG_MAX)) {
 726             token.type = T_INTEGER;
 727             token.u.integer = negative ? -significand : significand;
 728             json_parser_input(p, &token);
 729             return;
 730         }
 731     }
 732
 733     token.type = T_REAL;
 734     if (!str_to_double(ds_cstr(&p->buffer), &token.u.real)) {
 735         json_error(p, "number outside valid range");
 736         return;
 737     }
 738     /* Suppress negative zero. */
 739     if (token.u.real == 0) {
 740         token.u.real = 0;
 741     }
 742     json_parser_input(p, &token);
 743 }
 744
 745 static const char *
 746 json_lex_4hex(const char *cp, const char *end, int *valuep)
 747 {
 748     unsigned int value;
 749     bool ok;
 750
 751     if (cp + 4 > end) {
 752         return "quoted string ends within \\u escape";
 753     }
 754
 755     value = hexits_value(cp, 4, &ok);
 756     if (!ok) {
 757         return "malformed \\u escape";
 758     }
 759     if (!value) {
 760         return "null bytes not supported in quoted strings";
 761     }
 762     *valuep = value;
 763     return NULL;
 764 }
 765
 766 static const char *
 767 json_lex_unicode(const char *cp, const char *end, struct ds *out)
 768 {
 769     const char *error;
 770     int c0, c1;
 771
 772     error = json_lex_4hex(cp, end, &c0);
 773     if (error) {
 774         ds_clear(out);
 775         ds_put_cstr(out, error);
 776         return NULL;
 777     }
 778     cp += 4;
 779     if (!uc_is_leading_surrogate(c0)) {
 780         ds_put_utf8(out, c0);
 781         return cp;
 782     }
 783
 784     if (cp + 2 > end || *cp++ != '\\' || *cp++ != 'u') {
 785         ds_clear(out);
 786         ds_put_cstr(out, "malformed escaped surrogate pair");
 787         return NULL;
 788     }
 789
 790     error = json_lex_4hex(cp, end, &c1);
 791     if (error) {
 792         ds_clear(out);
 793         ds_put_cstr(out, error);
 794         return NULL;
 795     }
 796     cp += 4;
 797     if (!uc_is_trailing_surrogate(c1)) {
 798         ds_clear(out);
 799         ds_put_cstr(out, "second half of escaped surrogate pair is not "
 800                     "trailing surrogate");
 801         return NULL;
 802     }
 803
 804     ds_put_utf8(out, utf16_decode_surrogate_pair(c0, c1));
 805     return cp;
 806 }
 807
 808 bool
 809 json_string_unescape(const char *in, size_t in_len, char **outp)
 810 {
 811     const char *end = in + in_len;
 812     bool ok = false;
 813     struct ds out;
 814
 815     ds_init(&out);
 816     ds_reserve(&out, in_len);
 817     while (in < end) {
 818         if (*in == '"') {
 819             ds_clear(&out);
 820             ds_put_cstr(&out, "quoted string may not include unescaped \"");
 821             goto exit;
 822         }
 823         if (*in != '\\') {
 824             ds_put_char(&out, *in++);
 825             continue;
 826         }
 827
 828         in++;
 829         if (in >= end) {
 830             /* The JSON parser will never trigger this message, because its
 831              * lexer will never pass in a string that ends in a single
 832              * backslash, but json_string_unescape() has other callers that
 833              * are not as careful.*/
 834             ds_clear(&out);
 835             ds_put_cstr(&out, "quoted string may not end with backslash");
 836             goto exit;
 837         }
 838         switch (*in++) {
 839         case '"': case '\\': case '/':
 840             ds_put_char(&out, in[-1]);
 841             break;
 842
 843         case 'b':
 844             ds_put_char(&out, '\b');
 845             break;
 846
 847         case 'f':
 848             ds_put_char(&out, '\f');
 849             break;
 850
 851         case 'n':
 852             ds_put_char(&out, '\n');
 853             break;
 854
 855         case 'r':
 856             ds_put_char(&out, '\r');
 857             break;
 858
 859         case 't':
 860             ds_put_char(&out, '\t');
 861             break;
 862
 863         case 'u':
 864             in = json_lex_unicode(in, end, &out);
 865             if (!in) {
 866                 goto exit;
 867             }
 868             break;
 869
 870         default:
 871             ds_clear(&out);
 872             ds_put_format(&out, "bad escape \\%c", in[-1]);
 873             goto exit;
 874         }
 875     }
 876     ok = true;
 877
 878 exit:
 879     *outp = ds_cstr(&out);
 880     return ok;
 881 }
 882
 883 void
 884 json_string_escape(const char *in, struct ds *out)
 885 {
 886     struct json json = {
 887         .type = JSON_STRING,
 888         .u.string = CONST_CAST(char *, in),
 889     };
 890     json_to_ds(&json, 0, out);
 891 }
 892
 893 static void
 894 json_parser_input_string(struct json_parser *p, const char *s)
 895 {
 896     struct json_token token;
 897
 898     token.type = T_STRING;
 899     token.u.string = s;
 900     json_parser_input(p, &token);
 901 }
 902
 903 static void
 904 json_lex_string(struct json_parser *p)
 905 {
 906     const char *raw = ds_cstr(&p->buffer);
 907     if (!strchr(raw, '\\')) {
 908         json_parser_input_string(p, raw);
 909     } else {
 910         char *cooked;
 911
 912         if (json_string_unescape(raw, strlen(raw), &cooked)) {
 913             json_parser_input_string(p, cooked);
 914         } else {
 915             json_error(p, "%s", cooked);
 916         }
 917
 918         free(cooked);
 919     }
 920 }
 921
 922 static bool
 923 json_lex_input(struct json_parser *p, unsigned char c)
 924 {
 925     struct json_token token;
 926
 927     switch (p->lex_state) {
 928     case JSON_LEX_START:
 929         switch (c) {
 930         case ' ': case '\t': case '\n': case '\r':
 931             /* Nothing to do. */
 932             return true;
 933
 934         case 'a': case 'b': case 'c': case 'd': case 'e':
 935         case 'f': case 'g': case 'h': case 'i': case 'j':
 936         case 'k': case 'l': case 'm': case 'n': case 'o':
 937         case 'p': case 'q': case 'r': case 's': case 't':
 938         case 'u': case 'v': case 'w': case 'x': case 'y':
 939         case 'z':
 940             p->lex_state = JSON_LEX_KEYWORD;
 941             break;
 942
 943         case '[': case '{': case ']': case '}': case ':': case ',':
 944             token.type = c;
 945             json_parser_input(p, &token);
 946             return true;
 947
 948         case '-':
 949         case '0': case '1': case '2': case '3': case '4':
 950         case '5': case '6': case '7': case '8': case '9':
 951             p->lex_state = JSON_LEX_NUMBER;
 952             break;
 953
 954         case '"':
 955             p->lex_state = JSON_LEX_STRING;
 956             return true;
 957
 958         default:
 959             if (isprint(c)) {
 960                 json_error(p, "invalid character '%c'", c);
 961             } else {
 962                 json_error(p, "invalid character U+%04x", c);
 963             }
 964             return true;
 965         }
 966         break;
 967
 968     case JSON_LEX_KEYWORD:
 969         if (!isalpha((unsigned char) c)) {
 970             json_lex_keyword(p);
 971             return false;
 972         }
 973         break;
 974
 975     case JSON_LEX_NUMBER:
 976         if (!strchr(".0123456789eE-+", c)) {
 977             json_lex_number(p);
 978             return false;
 979         }
 980         break;
 981
 982     case JSON_LEX_STRING:
 983         if (c == '\\') {
 984             p->lex_state = JSON_LEX_ESCAPE;
 985         } else if (c == '"') {
 986             json_lex_string(p);
 987             return true;
 988         } else if (c < 0x20) {
 989             json_error(p, "U+%04X must be escaped in quoted string", c);
 990             return true;
 991         }
 992         break;
 993
 994     case JSON_LEX_ESCAPE:
 995         p->lex_state = JSON_LEX_STRING;
 996         break;
 997
 998     default:
 999         abort();
1000     }
1001     ds_put_char(&p->buffer, c);
1002     return true;
1003 }
1004 \f
1005 /* Parsing. */
1006
1007 /* Parses 'string' as a JSON object or array and returns a newly allocated
1008  * 'struct json'.  The caller must free the returned structure with
1009  * json_destroy() when it is no longer needed.
1010  *
1011  * 'string' must be encoded in UTF-8.
1012  *
1013  * If 'string' is valid JSON, then the returned 'struct json' will be either an
1014  * object (JSON_OBJECT) or an array (JSON_ARRAY).
1015  *
1016  * If 'string' is not valid JSON, then the returned 'struct json' will be a
1017  * string (JSON_STRING) that describes the particular error encountered during
1018  * parsing.  (This is an acceptable means of error reporting because at its top
1019  * level JSON must be either an object or an array; a bare string is not
1020  * valid.) */
1021 struct json *
1022 json_from_string(const char *string)
1023 {
1024     struct json_parser *p = json_parser_create(JSPF_TRAILER);
1025     json_parser_feed(p, string, strlen(string));
1026     return json_parser_finish(p);
1027 }
1028
1029 /* Reads the file named 'file_name', parses its contents as a JSON object or
1030  * array, and returns a newly allocated 'struct json'.  The caller must free
1031  * the returned structure with json_destroy() when it is no longer needed.
1032  *
1033  * The file must be encoded in UTF-8.
1034  *
1035  * See json_from_string() for return value semantics.
1036  */
1037 struct json *
1038 json_from_file(const char *file_name)
1039 {
1040     struct json *json;
1041     FILE *stream;
1042
1043     stream = fopen(file_name, "r");
1044     if (!stream) {
1045         return json_string_create_nocopy(
1046             xasprintf("error opening \"%s\": %s", file_name,
1047                       ovs_strerror(errno)));
1048     }
1049     json = json_from_stream(stream);
1050     fclose(stream);
1051
1052     return json;
1053 }
1054
1055 /* Parses the contents of 'stream' as a JSON object or array, and returns a
1056  * newly allocated 'struct json'.  The caller must free the returned structure
1057  * with json_destroy() when it is no longer needed.
1058  *
1059  * The file must be encoded in UTF-8.
1060  *
1061  * See json_from_string() for return value semantics.
1062  */
1063 struct json *
1064 json_from_stream(FILE *stream)
1065 {
1066     struct json_parser *p;
1067     struct json *json;
1068
1069     p = json_parser_create(JSPF_TRAILER);
1070     for (;;) {
1071         char buffer[BUFSIZ];
1072         size_t n;
1073
1074         n = fread(buffer, 1, sizeof buffer, stream);
1075         if (!n || json_parser_feed(p, buffer, n) != n) {
1076             break;
1077         }
1078     }
1079     json = json_parser_finish(p);
1080
1081     if (ferror(stream)) {
1082         json_destroy(json);
1083         json = json_string_create_nocopy(
1084             xasprintf("error reading JSON stream: %s", ovs_strerror(errno)));
1085     }
1086
1087     return json;
1088 }
1089
1090 struct json_parser *
1091 json_parser_create(int flags)
1092 {
1093     struct json_parser *p = xzalloc(sizeof *p);
1094     p->flags = flags;
1095     return p;
1096 }
1097
1098 size_t
1099 json_parser_feed(struct json_parser *p, const char *input, size_t n)
1100 {
1101     size_t i;
1102     for (i = 0; !p->done && i < n; ) {
1103         if (json_lex_input(p, input[i])) {
1104             p->byte_number++;
1105             if (input[i] == '\n') {
1106                 p->column_number = 0;
1107                 p->line_number++;
1108             } else {
1109                 p->column_number++;
1110             }
1111             i++;
1112         }
1113     }
1114     return i;
1115 }
1116
1117 bool
1118 json_parser_is_done(const struct json_parser *p)
1119 {
1120     return p->done;
1121 }
1122
1123 struct json *
1124 json_parser_finish(struct json_parser *p)
1125 {
1126     struct json *json;
1127
1128     switch (p->lex_state) {
1129     case JSON_LEX_START:
1130         break;
1131
1132     case JSON_LEX_STRING:
1133     case JSON_LEX_ESCAPE:
1134         json_error(p, "unexpected end of input in quoted string");
1135         break;
1136
1137     case JSON_LEX_NUMBER:
1138     case JSON_LEX_KEYWORD:
1139         json_lex_input(p, ' ');
1140         break;
1141     }
1142
1143     if (p->parse_state == JSON_PARSE_START) {
1144         json_error(p, "empty input stream");
1145     } else if (p->parse_state != JSON_PARSE_END) {
1146         json_error(p, "unexpected end of input");
1147     }
1148
1149     if (!p->error) {
1150         ovs_assert(p->height == 1);
1151         ovs_assert(p->stack[0].json != NULL);
1152         json = p->stack[--p->height].json;
1153     } else {
1154         json = json_string_create_nocopy(p->error);
1155         p->error = NULL;
1156     }
1157
1158     json_parser_abort(p);
1159
1160     return json;
1161 }
1162
1163 void
1164 json_parser_abort(struct json_parser *p)
1165 {
1166     if (p) {
1167         ds_destroy(&p->buffer);
1168         if (p->height) {
1169             json_destroy(p->stack[0].json);
1170         }
1171         free(p->stack);
1172         free(p->member_name);
1173         free(p->error);
1174         free(p);
1175     }
1176 }
1177
1178 static struct json_parser_node *
1179 json_parser_top(struct json_parser *p)
1180 {
1181     return &p->stack[p->height - 1];
1182 }
1183
1184 static void
1185 json_parser_put_value(struct json_parser *p, struct json *value)
1186 {
1187     struct json_parser_node *node = json_parser_top(p);
1188     if (node->json->type == JSON_OBJECT) {
1189         json_object_put(node->json, p->member_name, value);
1190         free(p->member_name);
1191         p->member_name = NULL;
1192     } else if (node->json->type == JSON_ARRAY) {
1193         json_array_add(node->json, value);
1194     } else {
1195         OVS_NOT_REACHED();
1196     }
1197 }
1198
1199 static void
1200 json_parser_push(struct json_parser *p,
1201                  struct json *new_json, enum json_parse_state new_state)
1202 {
1203     if (p->height < JSON_MAX_HEIGHT) {
1204         struct json_parser_node *node;
1205
1206         if (p->height >= p->allocated_height) {
1207             p->stack = x2nrealloc(p->stack, &p->allocated_height,
1208                                   sizeof *p->stack);
1209         }
1210
1211         if (p->height > 0) {
1212             json_parser_put_value(p, new_json);
1213         }
1214
1215         node = &p->stack[p->height++];
1216         node->json = new_json;
1217         p->parse_state = new_state;
1218     } else {
1219         json_destroy(new_json);
1220         json_error(p, "input exceeds maximum nesting depth %d",
1221                    JSON_MAX_HEIGHT);
1222     }
1223 }
1224
1225 static void
1226 json_parser_push_object(struct json_parser *p)
1227 {
1228     json_parser_push(p, json_object_create(), JSON_PARSE_OBJECT_INIT);
1229 }
1230
1231 static void
1232 json_parser_push_array(struct json_parser *p)
1233 {
1234     json_parser_push(p, json_array_create_empty(), JSON_PARSE_ARRAY_INIT);
1235 }
1236
1237 static void
1238 json_parse_value(struct json_parser *p, struct json_token *token,
1239                  enum json_parse_state next_state)
1240 {
1241     struct json *value;
1242
1243     switch (token->type) {
1244     case T_FALSE:
1245         value = json_boolean_create(false);
1246         break;
1247
1248     case T_NULL:
1249         value = json_null_create();
1250         break;
1251
1252     case T_TRUE:
1253         value = json_boolean_create(true);
1254         break;
1255
1256     case '{':
1257         json_parser_push_object(p);
1258         return;
1259
1260     case '[':
1261         json_parser_push_array(p);
1262         return;
1263
1264     case T_INTEGER:
1265         value = json_integer_create(token->u.integer);
1266         break;
1267
1268     case T_REAL:
1269         value = json_real_create(token->u.real);
1270         break;
1271
1272     case T_STRING:
1273         value = json_string_create(token->u.string);
1274         break;
1275
1276     case T_EOF:
1277     case '}':
1278     case ']':
1279     case ':':
1280     case ',':
1281     default:
1282         json_error(p, "syntax error expecting value");
1283         return;
1284     }
1285
1286     json_parser_put_value(p, value);
1287     p->parse_state = next_state;
1288 }
1289
1290 static void
1291 json_parser_pop(struct json_parser *p)
1292 {
1293     struct json_parser_node *node;
1294
1295     /* Conserve memory. */
1296     node = json_parser_top(p);
1297     if (node->json->type == JSON_ARRAY) {
1298         json_array_trim(node->json);
1299     }
1300
1301     /* Pop off the top-of-stack. */
1302     if (p->height == 1) {
1303         p->parse_state = JSON_PARSE_END;
1304         if (!(p->flags & JSPF_TRAILER)) {
1305             p->done = true;
1306         }
1307     } else {
1308         p->height--;
1309         node = json_parser_top(p);
1310         if (node->json->type == JSON_ARRAY) {
1311             p->parse_state = JSON_PARSE_ARRAY_NEXT;
1312         } else if (node->json->type == JSON_OBJECT) {
1313             p->parse_state = JSON_PARSE_OBJECT_NEXT;
1314         } else {
1315             OVS_NOT_REACHED();
1316         }
1317     }
1318 }
1319
1320 static void
1321 json_parser_input(struct json_parser *p, struct json_token *token)
1322 {
1323     switch (p->parse_state) {
1324     case JSON_PARSE_START:
1325         if (token->type == '{') {
1326             json_parser_push_object(p);
1327         } else if (token->type == '[') {
1328             json_parser_push_array(p);
1329         } else {
1330             json_error(p, "syntax error at beginning of input");
1331         }
1332         break;
1333
1334     case JSON_PARSE_END:
1335         json_error(p, "trailing garbage at end of input");
1336         break;
1337
1338     case JSON_PARSE_OBJECT_INIT:
1339         if (token->type == '}') {
1340             json_parser_pop(p);
1341             break;
1342         }
1343         /* Fall through. */
1344     case JSON_PARSE_OBJECT_NAME:
1345         if (token->type == T_STRING) {
1346             p->member_name = xstrdup(token->u.string);
1347             p->parse_state = JSON_PARSE_OBJECT_COLON;
1348         } else {
1349             json_error(p, "syntax error parsing object expecting string");
1350         }
1351         break;
1352
1353     case JSON_PARSE_OBJECT_COLON:
1354         if (token->type == ':') {
1355             p->parse_state = JSON_PARSE_OBJECT_VALUE;
1356         } else {
1357             json_error(p, "syntax error parsing object expecting ':'");
1358         }
1359         break;
1360
1361     case JSON_PARSE_OBJECT_VALUE:
1362         json_parse_value(p, token, JSON_PARSE_OBJECT_NEXT);
1363         break;
1364
1365     case JSON_PARSE_OBJECT_NEXT:
1366         if (token->type == ',') {
1367             p->parse_state = JSON_PARSE_OBJECT_NAME;
1368         } else if (token->type == '}') {
1369             json_parser_pop(p);
1370         } else {
1371             json_error(p, "syntax error expecting '}' or ','");
1372         }
1373         break;
1374
1375     case JSON_PARSE_ARRAY_INIT:
1376         if (token->type == ']') {
1377             json_parser_pop(p);
1378             break;
1379         }
1380         /* Fall through. */
1381     case JSON_PARSE_ARRAY_VALUE:
1382         json_parse_value(p, token, JSON_PARSE_ARRAY_NEXT);
1383         break;
1384
1385     case JSON_PARSE_ARRAY_NEXT:
1386         if (token->type == ',') {
1387             p->parse_state = JSON_PARSE_ARRAY_VALUE;
1388         } else if (token->type == ']') {
1389             json_parser_pop(p);
1390         } else {
1391             json_error(p, "syntax error expecting ']' or ','");
1392         }
1393         break;
1394
1395     default:
1396         abort();
1397     }
1398
1399     p->lex_state = JSON_LEX_START;
1400     ds_clear(&p->buffer);
1401 }
1402
1403 static struct json *
1404 json_create(enum json_type type)
1405 {
1406     struct json *json = xmalloc(sizeof *json);
1407     json->type = type;
1408     return json;
1409 }
1410
1411 static void
1412 json_error(struct json_parser *p, const char *format, ...)
1413 {
1414     if (!p->error) {
1415         struct ds msg;
1416         va_list args;
1417
1418         ds_init(&msg);
1419         ds_put_format(&msg, "line %d, column %d, byte %d: ",
1420                       p->line_number, p->column_number, p->byte_number);
1421         va_start(args, format);
1422         ds_put_format_valist(&msg, format, args);
1423         va_end(args);
1424
1425         p->error = ds_steal_cstr(&msg);
1426
1427         p->done = true;
1428     }
1429 }
1430 \f
1431 #define SPACES_PER_LEVEL 2
1432
1433 struct json_serializer {
1434     struct ds *ds;
1435     int depth;
1436     int flags;
1437 };
1438
1439 static void json_serialize(const struct json *, struct json_serializer *);
1440 static void json_serialize_object(const struct shash *object,
1441                                   struct json_serializer *);
1442 static void json_serialize_array(const struct json_array *,
1443                                  struct json_serializer *);
1444 static void json_serialize_string(const char *, struct ds *);
1445
1446 /* Converts 'json' to a string in JSON format, encoded in UTF-8, and returns
1447  * that string.  The caller is responsible for freeing the returned string,
1448  * with free(), when it is no longer needed.
1449  *
1450  * If 'flags' contains JSSF_PRETTY, the output is pretty-printed with each
1451  * nesting level introducing an additional indentation.  Otherwise, the
1452  * returned string does not contain any new-line characters.
1453  *
1454  * If 'flags' contains JSSF_SORT, members of objects in the output are sorted
1455  * in bytewise lexicographic order for reproducibility.  Otherwise, members of
1456  * objects are output in an indeterminate order.
1457  *
1458  * The returned string is valid JSON only if 'json' represents an array or an
1459  * object, since a bare literal does not satisfy the JSON grammar. */
1460 char *
1461 json_to_string(const struct json *json, int flags)
1462 {
1463     struct ds ds;
1464
1465     ds_init(&ds);
1466     json_to_ds(json, flags, &ds);
1467     return ds_steal_cstr(&ds);
1468 }
1469
1470 /* Same as json_to_string(), but the output is appended to 'ds'. */
1471 void
1472 json_to_ds(const struct json *json, int flags, struct ds *ds)
1473 {
1474     struct json_serializer s;
1475
1476     s.ds = ds;
1477     s.depth = 0;
1478     s.flags = flags;
1479     json_serialize(json, &s);
1480 }
1481
1482 static void
1483 json_serialize(const struct json *json, struct json_serializer *s)
1484 {
1485     struct ds *ds = s->ds;
1486
1487     switch (json->type) {
1488     case JSON_NULL:
1489         ds_put_cstr(ds, "null");
1490         break;
1491
1492     case JSON_FALSE:
1493         ds_put_cstr(ds, "false");
1494         break;
1495
1496     case JSON_TRUE:
1497         ds_put_cstr(ds, "true");
1498         break;
1499
1500     case JSON_OBJECT:
1501         json_serialize_object(json->u.object, s);
1502         break;
1503
1504     case JSON_ARRAY:
1505         json_serialize_array(&json->u.array, s);
1506         break;
1507
1508     case JSON_INTEGER:
1509         ds_put_format(ds, "%lld", json->u.integer);
1510         break;
1511
1512     case JSON_REAL:
1513         ds_put_format(ds, "%.*g", DBL_DIG, json->u.real);
1514         break;
1515
1516     case JSON_STRING:
1517         json_serialize_string(json->u.string, ds);
1518         break;
1519
1520     case JSON_N_TYPES:
1521     default:
1522         OVS_NOT_REACHED();
1523     }
1524 }
1525
1526 static void
1527 indent_line(struct json_serializer *s)
1528 {
1529     if (s->flags & JSSF_PRETTY) {
1530         ds_put_char(s->ds, '\n');
1531         ds_put_char_multiple(s->ds, ' ', SPACES_PER_LEVEL * s->depth);
1532     }
1533 }
1534
1535 static void
1536 json_serialize_object_member(size_t i, const struct shash_node *node,
1537                              struct json_serializer *s)
1538 {
1539     struct ds *ds = s->ds;
1540
1541     if (i) {
1542         ds_put_char(ds, ',');
1543         indent_line(s);
1544     }
1545
1546     json_serialize_string(node->name, ds);
1547     ds_put_char(ds, ':');
1548     if (s->flags & JSSF_PRETTY) {
1549         ds_put_char(ds, ' ');
1550     }
1551     json_serialize(node->data, s);
1552 }
1553
1554 static void
1555 json_serialize_object(const struct shash *object, struct json_serializer *s)
1556 {
1557     struct ds *ds = s->ds;
1558
1559     ds_put_char(ds, '{');
1560
1561     s->depth++;
1562     indent_line(s);
1563
1564     if (s->flags & JSSF_SORT) {
1565         const struct shash_node **nodes;
1566         size_t n, i;
1567
1568         nodes = shash_sort(object);
1569         n = shash_count(object);
1570         for (i = 0; i < n; i++) {
1571             json_serialize_object_member(i, nodes[i], s);
1572         }
1573         free(nodes);
1574     } else {
1575         struct shash_node *node;
1576         size_t i;
1577
1578         i = 0;
1579         SHASH_FOR_EACH (node, object) {
1580             json_serialize_object_member(i++, node, s);
1581         }
1582     }
1583
1584     ds_put_char(ds, '}');
1585     s->depth--;
1586 }
1587
1588 static void
1589 json_serialize_array(const struct json_array *array, struct json_serializer *s)
1590 {
1591     struct ds *ds = s->ds;
1592     size_t i;
1593
1594     ds_put_char(ds, '[');
1595     s->depth++;
1596
1597     if (array->n > 0) {
1598         indent_line(s);
1599
1600         for (i = 0; i < array->n; i++) {
1601             if (i) {
1602                 ds_put_char(ds, ',');
1603                 indent_line(s);
1604             }
1605             json_serialize(array->elems[i], s);
1606         }
1607     }
1608
1609     s->depth--;
1610     ds_put_char(ds, ']');
1611 }
1612
1613 static void
1614 json_serialize_string(const char *string, struct ds *ds)
1615 {
1616     uint8_t c;
1617
1618     ds_put_char(ds, '"');
1619     while ((c = *string++) != '\0') {
1620         switch (c) {
1621         case '"':
1622             ds_put_cstr(ds, "\\\"");
1623             break;
1624
1625         case '\\':
1626             ds_put_cstr(ds, "\\\\");
1627             break;
1628
1629         case '\b':
1630             ds_put_cstr(ds, "\\b");
1631             break;
1632
1633         case '\f':
1634             ds_put_cstr(ds, "\\f");
1635             break;
1636
1637         case '\n':
1638             ds_put_cstr(ds, "\\n");
1639             break;
1640
1641         case '\r':
1642             ds_put_cstr(ds, "\\r");
1643             break;
1644
1645         case '\t':
1646             ds_put_cstr(ds, "\\t");
1647             break;
1648
1649         default:
1650             if (c >= 32) {
1651                 ds_put_char(ds, c);
1652             } else {
1653                 ds_put_format(ds, "\\u%04x", c);
1654             }
1655             break;
1656         }
1657     }
1658     ds_put_char(ds, '"');
1659 }