lib/json.c

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