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     } u;
  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->u.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->u.array.elems = NULL;
 188     json->u.array.n = 0;
 189     json->u.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->u.array.elems = elements;
 219     json->u.array.n = n;
 220     json->u.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->u.object = xmalloc(sizeof *json->u.object);
 256     shash_init(json->u.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->u.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->u.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->u.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->u.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->u.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->u.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->u.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->u.real : json->u.integer;
 338 }
 339
 340 int64_t
 341 json_integer(const struct json *json)
 342 {
 343     ovs_assert(json->type == JSON_INTEGER);
 344     return json->u.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->u.object);
 358             break;
 359
 360         case JSON_ARRAY:
 361             json_destroy_array(&json->u.array);
 362             break;
 363
 364         case JSON_STRING:
 365             free(json->u.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->u.object);
 418
 419     case JSON_ARRAY:
 420         return json_clone_array(&json->u.array);
 421
 422     case JSON_STRING:
 423         return json_string_create(json->u.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->u.integer);
 432
 433     case JSON_REAL:
 434         return json_real_create(json->u.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->u.object, basis);
 519
 520     case JSON_ARRAY:
 521         return json_hash_array(&json->u.array, basis);
 522
 523     case JSON_STRING:
 524         return hash_string(json->u.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->u.integer, basis);
 533
 534     case JSON_REAL:
 535         return hash_double(json->u.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->u.object, b->u.object);
 594
 595     case JSON_ARRAY:
 596         return json_equal_array(&a->u.array, &b->u.array);
 597
 598     case JSON_STRING:
 599         return !strcmp(a->u.string, b->u.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->u.integer == b->u.integer;
 608
 609     case JSON_REAL:
 610         return a->u.real == b->u.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                 json_error(p, "exponent outside valid range");
 722                 return;
 723             }
 724             exponent = exponent * 10 + (*cp - '0');
 725             cp++;
 726         } while (isdigit((unsigned char) *cp));
 727
 728         if (negative_exponent) {
 729             pow10 -= exponent;
 730         } else {
 731             pow10 += exponent;
 732         }
 733     }
 734
 735     if (*cp != '\0') {
 736         json_error(p, "syntax error in number");
 737         return;
 738     }
 739
 740     /* Figure out number.
 741      *
 742      * We suppress negative zeros as a matter of policy. */
 743     if (!significand) {
 744         token.type = T_INTEGER;
 745         token.u.integer = 0;
 746         json_parser_input(p, &token);
 747         return;
 748     }
 749
 750     if (!imprecise) {
 751         while (pow10 > 0 && significand < ULLONG_MAX / 10) {
 752             significand *= 10;
 753             pow10--;
 754         }
 755         while (pow10 < 0 && significand % 10 == 0) {
 756             significand /= 10;
 757             pow10++;
 758         }
 759         if (pow10 == 0
 760             && significand <= (negative
 761                                ? (unsigned long long int) LLONG_MAX + 1
 762                                : LLONG_MAX)) {
 763             token.type = T_INTEGER;
 764             token.u.integer = negative ? -significand : significand;
 765             json_parser_input(p, &token);
 766             return;
 767         }
 768     }
 769
 770     token.type = T_REAL;
 771     if (!str_to_double(ds_cstr(&p->buffer), &token.u.real)) {
 772         json_error(p, "number outside valid range");
 773         return;
 774     }
 775     /* Suppress negative zero. */
 776     if (token.u.real == 0) {
 777         token.u.real = 0;
 778     }
 779     json_parser_input(p, &token);
 780 }
 781
 782 static const char *
 783 json_lex_4hex(const char *cp, const char *end, int *valuep)
 784 {
 785     unsigned int value;
 786     bool ok;
 787
 788     if (cp + 4 > end) {
 789         return "quoted string ends within \\u escape";
 790     }
 791
 792     value = hexits_value(cp, 4, &ok);
 793     if (!ok) {
 794         return "malformed \\u escape";
 795     }
 796     if (!value) {
 797         return "null bytes not supported in quoted strings";
 798     }
 799     *valuep = value;
 800     return NULL;
 801 }
 802
 803 static const char *
 804 json_lex_unicode(const char *cp, const char *end, struct ds *out)
 805 {
 806     const char *error;
 807     int c0, c1;
 808
 809     error = json_lex_4hex(cp, end, &c0);
 810     if (error) {
 811         ds_clear(out);
 812         ds_put_cstr(out, error);
 813         return NULL;
 814     }
 815     cp += 4;
 816     if (!uc_is_leading_surrogate(c0)) {
 817         ds_put_utf8(out, c0);
 818         return cp;
 819     }
 820
 821     if (cp + 2 > end || *cp++ != '\\' || *cp++ != 'u') {
 822         ds_clear(out);
 823         ds_put_cstr(out, "malformed escaped surrogate pair");
 824         return NULL;
 825     }
 826
 827     error = json_lex_4hex(cp, end, &c1);
 828     if (error) {
 829         ds_clear(out);
 830         ds_put_cstr(out, error);
 831         return NULL;
 832     }
 833     cp += 4;
 834     if (!uc_is_trailing_surrogate(c1)) {
 835         ds_clear(out);
 836         ds_put_cstr(out, "second half of escaped surrogate pair is not "
 837                     "trailing surrogate");
 838         return NULL;
 839     }
 840
 841     ds_put_utf8(out, utf16_decode_surrogate_pair(c0, c1));
 842     return cp;
 843 }
 844
 845 bool
 846 json_string_unescape(const char *in, size_t in_len, char **outp)
 847 {
 848     const char *end = in + in_len;
 849     bool ok = false;
 850     struct ds out;
 851
 852     ds_init(&out);
 853     ds_reserve(&out, in_len);
 854     while (in < end) {
 855         if (*in == '"') {
 856             ds_clear(&out);
 857             ds_put_cstr(&out, "quoted string may not include unescaped \"");
 858             goto exit;
 859         }
 860         if (*in != '\\') {
 861             ds_put_char(&out, *in++);
 862             continue;
 863         }
 864
 865         in++;
 866         if (in >= end) {
 867             /* The JSON parser will never trigger this message, because its
 868              * lexer will never pass in a string that ends in a single
 869              * backslash, but json_string_unescape() has other callers that
 870              * are not as careful.*/
 871             ds_clear(&out);
 872             ds_put_cstr(&out, "quoted string may not end with backslash");
 873             goto exit;
 874         }
 875         switch (*in++) {
 876         case '"': case '\\': case '/':
 877             ds_put_char(&out, in[-1]);
 878             break;
 879
 880         case 'b':
 881             ds_put_char(&out, '\b');
 882             break;
 883
 884         case 'f':
 885             ds_put_char(&out, '\f');
 886             break;
 887
 888         case 'n':
 889             ds_put_char(&out, '\n');
 890             break;
 891
 892         case 'r':
 893             ds_put_char(&out, '\r');
 894             break;
 895
 896         case 't':
 897             ds_put_char(&out, '\t');
 898             break;
 899
 900         case 'u':
 901             in = json_lex_unicode(in, end, &out);
 902             if (!in) {
 903                 goto exit;
 904             }
 905             break;
 906
 907         default:
 908             ds_clear(&out);
 909             ds_put_format(&out, "bad escape \\%c", in[-1]);
 910             goto exit;
 911         }
 912     }
 913     ok = true;
 914
 915 exit:
 916     *outp = ds_cstr(&out);
 917     return ok;
 918 }
 919
 920 void
 921 json_string_escape(const char *in, struct ds *out)
 922 {
 923     struct json json = {
 924         .type = JSON_STRING,
 925         .u.string = CONST_CAST(char *, in),
 926     };
 927     json_to_ds(&json, 0, out);
 928 }
 929
 930 static void
 931 json_parser_input_string(struct json_parser *p, const char *s)
 932 {
 933     struct json_token token;
 934
 935     token.type = T_STRING;
 936     token.u.string = s;
 937     json_parser_input(p, &token);
 938 }
 939
 940 static void
 941 json_lex_string(struct json_parser *p)
 942 {
 943     const char *raw = ds_cstr(&p->buffer);
 944     if (!strchr(raw, '\\')) {
 945         json_parser_input_string(p, raw);
 946     } else {
 947         char *cooked;
 948
 949         if (json_string_unescape(raw, strlen(raw), &cooked)) {
 950             json_parser_input_string(p, cooked);
 951         } else {
 952             json_error(p, "%s", cooked);
 953         }
 954
 955         free(cooked);
 956     }
 957 }
 958
 959 static bool
 960 json_lex_input(struct json_parser *p, unsigned char c)
 961 {
 962     struct json_token token;
 963
 964     switch (p->lex_state) {
 965     case JSON_LEX_START:
 966         switch (c) {
 967         case ' ': case '\t': case '\n': case '\r':
 968             /* Nothing to do. */
 969             return true;
 970
 971         case 'a': case 'b': case 'c': case 'd': case 'e':
 972         case 'f': case 'g': case 'h': case 'i': case 'j':
 973         case 'k': case 'l': case 'm': case 'n': case 'o':
 974         case 'p': case 'q': case 'r': case 's': case 't':
 975         case 'u': case 'v': case 'w': case 'x': case 'y':
 976         case 'z':
 977             p->lex_state = JSON_LEX_KEYWORD;
 978             break;
 979
 980         case '[': case '{': case ']': case '}': case ':': case ',':
 981             token.type = c;
 982             json_parser_input(p, &token);
 983             return true;
 984
 985         case '-':
 986         case '0': case '1': case '2': case '3': case '4':
 987         case '5': case '6': case '7': case '8': case '9':
 988             p->lex_state = JSON_LEX_NUMBER;
 989             break;
 990
 991         case '"':
 992             p->lex_state = JSON_LEX_STRING;
 993             return true;
 994
 995         default:
 996             if (isprint(c)) {
 997                 json_error(p, "invalid character '%c'", c);
 998             } else {
 999                 json_error(p, "invalid character U+%04x", c);
1000             }
1001             return true;
1002         }
1003         break;
1004
1005     case JSON_LEX_KEYWORD:
1006         if (!isalpha((unsigned char) c)) {
1007             json_lex_keyword(p);
1008             return false;
1009         }
1010         break;
1011
1012     case JSON_LEX_NUMBER:
1013         if (!strchr(".0123456789eE-+", c)) {
1014             json_lex_number(p);
1015             return false;
1016         }
1017         break;
1018
1019     case JSON_LEX_STRING:
1020         if (c == '\\') {
1021             p->lex_state = JSON_LEX_ESCAPE;
1022         } else if (c == '"') {
1023             json_lex_string(p);
1024             return true;
1025         } else if (c < 0x20) {
1026             json_error(p, "U+%04X must be escaped in quoted string", c);
1027             return true;
1028         }
1029         break;
1030
1031     case JSON_LEX_ESCAPE:
1032         p->lex_state = JSON_LEX_STRING;
1033         break;
1034
1035     default:
1036         abort();
1037     }
1038     ds_put_char(&p->buffer, c);
1039     return true;
1040 }
1041 \f
1042 /* Parsing. */
1043
1044 /* Parses 'string' as a JSON object or array and returns a newly allocated
1045  * 'struct json'.  The caller must free the returned structure with
1046  * json_destroy() when it is no longer needed.
1047  *
1048  * 'string' must be encoded in UTF-8.
1049  *
1050  * If 'string' is valid JSON, then the returned 'struct json' will be either an
1051  * object (JSON_OBJECT) or an array (JSON_ARRAY).
1052  *
1053  * If 'string' is not valid JSON, then the returned 'struct json' will be a
1054  * string (JSON_STRING) that describes the particular error encountered during
1055  * parsing.  (This is an acceptable means of error reporting because at its top
1056  * level JSON must be either an object or an array; a bare string is not
1057  * valid.) */
1058 struct json *
1059 json_from_string(const char *string)
1060 {
1061     struct json_parser *p = json_parser_create(JSPF_TRAILER);
1062     json_parser_feed(p, string, strlen(string));
1063     return json_parser_finish(p);
1064 }
1065
1066 /* Reads the file named 'file_name', parses its contents as a JSON object or
1067  * array, and returns a newly allocated 'struct json'.  The caller must free
1068  * the returned structure with json_destroy() when it is no longer needed.
1069  *
1070  * The file must be encoded in UTF-8.
1071  *
1072  * See json_from_string() for return value semantics.
1073  */
1074 struct json *
1075 json_from_file(const char *file_name)
1076 {
1077     struct json *json;
1078     FILE *stream;
1079
1080     stream = fopen(file_name, "r");
1081     if (!stream) {
1082         return json_string_create_nocopy(
1083             xasprintf("error opening \"%s\": %s", file_name,
1084                       ovs_strerror(errno)));
1085     }
1086     json = json_from_stream(stream);
1087     fclose(stream);
1088
1089     return json;
1090 }
1091
1092 /* Parses the contents of 'stream' as a JSON object or array, and returns a
1093  * newly allocated 'struct json'.  The caller must free the returned structure
1094  * with json_destroy() when it is no longer needed.
1095  *
1096  * The file must be encoded in UTF-8.
1097  *
1098  * See json_from_string() for return value semantics.
1099  */
1100 struct json *
1101 json_from_stream(FILE *stream)
1102 {
1103     struct json_parser *p;
1104     struct json *json;
1105
1106     p = json_parser_create(JSPF_TRAILER);
1107     for (;;) {
1108         char buffer[BUFSIZ];
1109         size_t n;
1110
1111         n = fread(buffer, 1, sizeof buffer, stream);
1112         if (!n || json_parser_feed(p, buffer, n) != n) {
1113             break;
1114         }
1115     }
1116     json = json_parser_finish(p);
1117
1118     if (ferror(stream)) {
1119         json_destroy(json);
1120         json = json_string_create_nocopy(
1121             xasprintf("error reading JSON stream: %s", ovs_strerror(errno)));
1122     }
1123
1124     return json;
1125 }
1126
1127 struct json_parser *
1128 json_parser_create(int flags)
1129 {
1130     struct json_parser *p = xzalloc(sizeof *p);
1131     p->flags = flags;
1132     return p;
1133 }
1134
1135 size_t
1136 json_parser_feed(struct json_parser *p, const char *input, size_t n)
1137 {
1138     size_t i;
1139     for (i = 0; !p->done && i < n; ) {
1140         if (json_lex_input(p, input[i])) {
1141             p->byte_number++;
1142             if (input[i] == '\n') {
1143                 p->column_number = 0;
1144                 p->line_number++;
1145             } else {
1146                 p->column_number++;
1147             }
1148             i++;
1149         }
1150     }
1151     return i;
1152 }
1153
1154 bool
1155 json_parser_is_done(const struct json_parser *p)
1156 {
1157     return p->done;
1158 }
1159
1160 struct json *
1161 json_parser_finish(struct json_parser *p)
1162 {
1163     struct json *json;
1164
1165     switch (p->lex_state) {
1166     case JSON_LEX_START:
1167         break;
1168
1169     case JSON_LEX_STRING:
1170     case JSON_LEX_ESCAPE:
1171         json_error(p, "unexpected end of input in quoted string");
1172         break;
1173
1174     case JSON_LEX_NUMBER:
1175     case JSON_LEX_KEYWORD:
1176         json_lex_input(p, ' ');
1177         break;
1178     }
1179
1180     if (p->parse_state == JSON_PARSE_START) {
1181         json_error(p, "empty input stream");
1182     } else if (p->parse_state != JSON_PARSE_END) {
1183         json_error(p, "unexpected end of input");
1184     }
1185
1186     if (!p->error) {
1187         ovs_assert(p->height == 1);
1188         ovs_assert(p->stack[0].json != NULL);
1189         json = p->stack[--p->height].json;
1190     } else {
1191         json = json_string_create_nocopy(p->error);
1192         p->error = NULL;
1193     }
1194
1195     json_parser_abort(p);
1196
1197     return json;
1198 }
1199
1200 void
1201 json_parser_abort(struct json_parser *p)
1202 {
1203     if (p) {
1204         ds_destroy(&p->buffer);
1205         if (p->height) {
1206             json_destroy(p->stack[0].json);
1207         }
1208         free(p->stack);
1209         free(p->member_name);
1210         free(p->error);
1211         free(p);
1212     }
1213 }
1214
1215 static struct json_parser_node *
1216 json_parser_top(struct json_parser *p)
1217 {
1218     return &p->stack[p->height - 1];
1219 }
1220
1221 static void
1222 json_parser_put_value(struct json_parser *p, struct json *value)
1223 {
1224     struct json_parser_node *node = json_parser_top(p);
1225     if (node->json->type == JSON_OBJECT) {
1226         json_object_put_nocopy(node->json, p->member_name, value);
1227         p->member_name = NULL;
1228     } else if (node->json->type == JSON_ARRAY) {
1229         json_array_add(node->json, value);
1230     } else {
1231         OVS_NOT_REACHED();
1232     }
1233 }
1234
1235 static void
1236 json_parser_push(struct json_parser *p,
1237                  struct json *new_json, enum json_parse_state new_state)
1238 {
1239     if (p->height < JSON_MAX_HEIGHT) {
1240         struct json_parser_node *node;
1241
1242         if (p->height >= p->allocated_height) {
1243             p->stack = x2nrealloc(p->stack, &p->allocated_height,
1244                                   sizeof *p->stack);
1245         }
1246
1247         if (p->height > 0) {
1248             json_parser_put_value(p, new_json);
1249         }
1250
1251         node = &p->stack[p->height++];
1252         node->json = new_json;
1253         p->parse_state = new_state;
1254     } else {
1255         json_destroy(new_json);
1256         json_error(p, "input exceeds maximum nesting depth %d",
1257                    JSON_MAX_HEIGHT);
1258     }
1259 }
1260
1261 static void
1262 json_parser_push_object(struct json_parser *p)
1263 {
1264     json_parser_push(p, json_object_create(), JSON_PARSE_OBJECT_INIT);
1265 }
1266
1267 static void
1268 json_parser_push_array(struct json_parser *p)
1269 {
1270     json_parser_push(p, json_array_create_empty(), JSON_PARSE_ARRAY_INIT);
1271 }
1272
1273 static void
1274 json_parse_value(struct json_parser *p, struct json_token *token,
1275                  enum json_parse_state next_state)
1276 {
1277     struct json *value;
1278
1279     switch (token->type) {
1280     case T_FALSE:
1281         value = json_boolean_create(false);
1282         break;
1283
1284     case T_NULL:
1285         value = json_null_create();
1286         break;
1287
1288     case T_TRUE:
1289         value = json_boolean_create(true);
1290         break;
1291
1292     case '{':
1293         json_parser_push_object(p);
1294         return;
1295
1296     case '[':
1297         json_parser_push_array(p);
1298         return;
1299
1300     case T_INTEGER:
1301         value = json_integer_create(token->u.integer);
1302         break;
1303
1304     case T_REAL:
1305         value = json_real_create(token->u.real);
1306         break;
1307
1308     case T_STRING:
1309         value = json_string_create(token->u.string);
1310         break;
1311
1312     case T_EOF:
1313     case '}':
1314     case ']':
1315     case ':':
1316     case ',':
1317     default:
1318         json_error(p, "syntax error expecting value");
1319         return;
1320     }
1321
1322     json_parser_put_value(p, value);
1323     p->parse_state = next_state;
1324 }
1325
1326 static void
1327 json_parser_pop(struct json_parser *p)
1328 {
1329     struct json_parser_node *node;
1330
1331     /* Conserve memory. */
1332     node = json_parser_top(p);
1333     if (node->json->type == JSON_ARRAY) {
1334         json_array_trim(node->json);
1335     }
1336
1337     /* Pop off the top-of-stack. */
1338     if (p->height == 1) {
1339         p->parse_state = JSON_PARSE_END;
1340         if (!(p->flags & JSPF_TRAILER)) {
1341             p->done = true;
1342         }
1343     } else {
1344         p->height--;
1345         node = json_parser_top(p);
1346         if (node->json->type == JSON_ARRAY) {
1347             p->parse_state = JSON_PARSE_ARRAY_NEXT;
1348         } else if (node->json->type == JSON_OBJECT) {
1349             p->parse_state = JSON_PARSE_OBJECT_NEXT;
1350         } else {
1351             OVS_NOT_REACHED();
1352         }
1353     }
1354 }
1355
1356 static void
1357 json_parser_input(struct json_parser *p, struct json_token *token)
1358 {
1359     switch (p->parse_state) {
1360     case JSON_PARSE_START:
1361         if (token->type == '{') {
1362             json_parser_push_object(p);
1363         } else if (token->type == '[') {
1364             json_parser_push_array(p);
1365         } else {
1366             json_error(p, "syntax error at beginning of input");
1367         }
1368         break;
1369
1370     case JSON_PARSE_END:
1371         json_error(p, "trailing garbage at end of input");
1372         break;
1373
1374     case JSON_PARSE_OBJECT_INIT:
1375         if (token->type == '}') {
1376             json_parser_pop(p);
1377             break;
1378         }
1379         /* Fall through. */
1380     case JSON_PARSE_OBJECT_NAME:
1381         if (token->type == T_STRING) {
1382             p->member_name = xstrdup(token->u.string);
1383             p->parse_state = JSON_PARSE_OBJECT_COLON;
1384         } else {
1385             json_error(p, "syntax error parsing object expecting string");
1386         }
1387         break;
1388
1389     case JSON_PARSE_OBJECT_COLON:
1390         if (token->type == ':') {
1391             p->parse_state = JSON_PARSE_OBJECT_VALUE;
1392         } else {
1393             json_error(p, "syntax error parsing object expecting ':'");
1394         }
1395         break;
1396
1397     case JSON_PARSE_OBJECT_VALUE:
1398         json_parse_value(p, token, JSON_PARSE_OBJECT_NEXT);
1399         break;
1400
1401     case JSON_PARSE_OBJECT_NEXT:
1402         if (token->type == ',') {
1403             p->parse_state = JSON_PARSE_OBJECT_NAME;
1404         } else if (token->type == '}') {
1405             json_parser_pop(p);
1406         } else {
1407             json_error(p, "syntax error expecting '}' or ','");
1408         }
1409         break;
1410
1411     case JSON_PARSE_ARRAY_INIT:
1412         if (token->type == ']') {
1413             json_parser_pop(p);
1414             break;
1415         }
1416         /* Fall through. */
1417     case JSON_PARSE_ARRAY_VALUE:
1418         json_parse_value(p, token, JSON_PARSE_ARRAY_NEXT);
1419         break;
1420
1421     case JSON_PARSE_ARRAY_NEXT:
1422         if (token->type == ',') {
1423             p->parse_state = JSON_PARSE_ARRAY_VALUE;
1424         } else if (token->type == ']') {
1425             json_parser_pop(p);
1426         } else {
1427             json_error(p, "syntax error expecting ']' or ','");
1428         }
1429         break;
1430
1431     default:
1432         abort();
1433     }
1434
1435     p->lex_state = JSON_LEX_START;
1436     ds_clear(&p->buffer);
1437 }
1438
1439 static struct json *
1440 json_create(enum json_type type)
1441 {
1442     struct json *json = xmalloc(sizeof *json);
1443     json->type = type;
1444     json->count = 1;
1445     return json;
1446 }
1447
1448 static void
1449 json_error(struct json_parser *p, const char *format, ...)
1450 {
1451     if (!p->error) {
1452         struct ds msg;
1453         va_list args;
1454
1455         ds_init(&msg);
1456         ds_put_format(&msg, "line %d, column %d, byte %d: ",
1457                       p->line_number, p->column_number, p->byte_number);
1458         va_start(args, format);
1459         ds_put_format_valist(&msg, format, args);
1460         va_end(args);
1461
1462         p->error = ds_steal_cstr(&msg);
1463
1464         p->done = true;
1465     }
1466 }
1467 \f
1468 #define SPACES_PER_LEVEL 2
1469
1470 struct json_serializer {
1471     struct ds *ds;
1472     int depth;
1473     int flags;
1474 };
1475
1476 static void json_serialize(const struct json *, struct json_serializer *);
1477 static void json_serialize_object(const struct shash *object,
1478                                   struct json_serializer *);
1479 static void json_serialize_array(const struct json_array *,
1480                                  struct json_serializer *);
1481 static void json_serialize_string(const char *, struct ds *);
1482
1483 /* Converts 'json' to a string in JSON format, encoded in UTF-8, and returns
1484  * that string.  The caller is responsible for freeing the returned string,
1485  * with free(), when it is no longer needed.
1486  *
1487  * If 'flags' contains JSSF_PRETTY, the output is pretty-printed with each
1488  * nesting level introducing an additional indentation.  Otherwise, the
1489  * returned string does not contain any new-line characters.
1490  *
1491  * If 'flags' contains JSSF_SORT, members of objects in the output are sorted
1492  * in bytewise lexicographic order for reproducibility.  Otherwise, members of
1493  * objects are output in an indeterminate order.
1494  *
1495  * The returned string is valid JSON only if 'json' represents an array or an
1496  * object, since a bare literal does not satisfy the JSON grammar. */
1497 char *
1498 json_to_string(const struct json *json, int flags)
1499 {
1500     struct ds ds;
1501
1502     ds_init(&ds);
1503     json_to_ds(json, flags, &ds);
1504     return ds_steal_cstr(&ds);
1505 }
1506
1507 /* Same as json_to_string(), but the output is appended to 'ds'. */
1508 void
1509 json_to_ds(const struct json *json, int flags, struct ds *ds)
1510 {
1511     struct json_serializer s;
1512
1513     s.ds = ds;
1514     s.depth = 0;
1515     s.flags = flags;
1516     json_serialize(json, &s);
1517 }
1518
1519 static void
1520 json_serialize(const struct json *json, struct json_serializer *s)
1521 {
1522     struct ds *ds = s->ds;
1523
1524     switch (json->type) {
1525     case JSON_NULL:
1526         ds_put_cstr(ds, "null");
1527         break;
1528
1529     case JSON_FALSE:
1530         ds_put_cstr(ds, "false");
1531         break;
1532
1533     case JSON_TRUE:
1534         ds_put_cstr(ds, "true");
1535         break;
1536
1537     case JSON_OBJECT:
1538         json_serialize_object(json->u.object, s);
1539         break;
1540
1541     case JSON_ARRAY:
1542         json_serialize_array(&json->u.array, s);
1543         break;
1544
1545     case JSON_INTEGER:
1546         ds_put_format(ds, "%lld", json->u.integer);
1547         break;
1548
1549     case JSON_REAL:
1550         ds_put_format(ds, "%.*g", DBL_DIG, json->u.real);
1551         break;
1552
1553     case JSON_STRING:
1554         json_serialize_string(json->u.string, ds);
1555         break;
1556
1557     case JSON_N_TYPES:
1558     default:
1559         OVS_NOT_REACHED();
1560     }
1561 }
1562
1563 static void
1564 indent_line(struct json_serializer *s)
1565 {
1566     if (s->flags & JSSF_PRETTY) {
1567         ds_put_char(s->ds, '\n');
1568         ds_put_char_multiple(s->ds, ' ', SPACES_PER_LEVEL * s->depth);
1569     }
1570 }
1571
1572 static void
1573 json_serialize_object_member(size_t i, const struct shash_node *node,
1574                              struct json_serializer *s)
1575 {
1576     struct ds *ds = s->ds;
1577
1578     if (i) {
1579         ds_put_char(ds, ',');
1580         indent_line(s);
1581     }
1582
1583     json_serialize_string(node->name, ds);
1584     ds_put_char(ds, ':');
1585     if (s->flags & JSSF_PRETTY) {
1586         ds_put_char(ds, ' ');
1587     }
1588     json_serialize(node->data, s);
1589 }
1590
1591 static void
1592 json_serialize_object(const struct shash *object, struct json_serializer *s)
1593 {
1594     struct ds *ds = s->ds;
1595
1596     ds_put_char(ds, '{');
1597
1598     s->depth++;
1599     indent_line(s);
1600
1601     if (s->flags & JSSF_SORT) {
1602         const struct shash_node **nodes;
1603         size_t n, i;
1604
1605         nodes = shash_sort(object);
1606         n = shash_count(object);
1607         for (i = 0; i < n; i++) {
1608             json_serialize_object_member(i, nodes[i], s);
1609         }
1610         free(nodes);
1611     } else {
1612         struct shash_node *node;
1613         size_t i;
1614
1615         i = 0;
1616         SHASH_FOR_EACH (node, object) {
1617             json_serialize_object_member(i++, node, s);
1618         }
1619     }
1620
1621     ds_put_char(ds, '}');
1622     s->depth--;
1623 }
1624
1625 static void
1626 json_serialize_array(const struct json_array *array, struct json_serializer *s)
1627 {
1628     struct ds *ds = s->ds;
1629     size_t i;
1630
1631     ds_put_char(ds, '[');
1632     s->depth++;
1633
1634     if (array->n > 0) {
1635         indent_line(s);
1636
1637         for (i = 0; i < array->n; i++) {
1638             if (i) {
1639                 ds_put_char(ds, ',');
1640                 indent_line(s);
1641             }
1642             json_serialize(array->elems[i], s);
1643         }
1644     }
1645
1646     s->depth--;
1647     ds_put_char(ds, ']');
1648 }
1649
1650 static const char *chars_escaping[256] = {
1651         "\\u0000", "\\u0001", "\\u0002", "\\u0003", "\\u0004", "\\u0005", "\\u0006", "\\u0007",
1652         "\\b", "\\t", "\\n", "\\u000b", "\\f", "\\r", "\\u000e", "\\u000f",
1653         "\\u0010", "\\u0011", "\\u0012", "\\u0013", "\\u0014", "\\u0015", "\\u0016", "\\u0017",
1654         "\\u0018", "\\u0019", "\\u001a", "\\u001b", "\\u001c", "\\u001d", "\\u001e", "\\u001f",
1655         " ", "!", "\\\"", "#", "$", "%", "&", "'",
1656         "(", ")", "*", "+", ",", "-", ".", "/",
1657         "0", "1", "2", "3", "4", "5", "6", "7",
1658         "8", "9", ":", ";", "<", "=", ">", "?",
1659         "@", "A", "B", "C", "D", "E", "F", "G",
1660         "H", "I", "J", "K", "L", "M", "N", "O",
1661         "P", "Q", "R", "S", "T", "U", "V", "W",
1662         "X", "Y", "Z", "[", "\\\\", "]", "^", "_",
1663         "`", "a", "b", "c", "d", "e", "f", "g",
1664         "h", "i", "j", "k", "l", "m", "n", "o",
1665         "p", "q", "r", "s", "t", "u", "v", "w",
1666         "x", "y", "z", "{", "|", "}", "~", "\x7f",
1667         "\x80", "\x81", "\x82", "\x83", "\x84", "\x85", "\x86", "\x87",
1668         "\x88", "\x89", "\x8a", "\x8b", "\x8c", "\x8d", "\x8e", "\x8f",
1669         "\x90", "\x91", "\x92", "\x93", "\x94", "\x95", "\x96", "\x97",
1670         "\x98", "\x99", "\x9a", "\x9b", "\x9c", "\x9d", "\x9e", "\x9f",
1671         "\xa0", "\xa1", "\xa2", "\xa3", "\xa4", "\xa5", "\xa6", "\xa7",
1672         "\xa8", "\xa9", "\xaa", "\xab", "\xac", "\xad", "\xae", "\xaf",
1673         "\xb0", "\xb1", "\xb2", "\xb3", "\xb4", "\xb5", "\xb6", "\xb7",
1674         "\xb8", "\xb9", "\xba", "\xbb", "\xbc", "\xbd", "\xbe", "\xbf",
1675         "\xc0", "\xc1", "\xc2", "\xc3", "\xc4", "\xc5", "\xc6", "\xc7",
1676         "\xc8", "\xc9", "\xca", "\xcb", "\xcc", "\xcd", "\xce", "\xcf",
1677         "\xd0", "\xd1", "\xd2", "\xd3", "\xd4", "\xd5", "\xd6", "\xd7",
1678         "\xd8", "\xd9", "\xda", "\xdb", "\xdc", "\xdd", "\xde", "\xdf",
1679         "\xe0", "\xe1", "\xe2", "\xe3", "\xe4", "\xe5", "\xe6", "\xe7",
1680         "\xe8", "\xe9", "\xea", "\xeb", "\xec", "\xed", "\xee", "\xef",
1681         "\xf0", "\xf1", "\xf2", "\xf3", "\xf4", "\xf5", "\xf6", "\xf7",
1682         "\xf8", "\xf9", "\xfa", "\xfb", "\xfc", "\xfd", "\xfe", "\xff"
1683 };
1684
1685 static void
1686 json_serialize_string(const char *string, struct ds *ds)
1687 {
1688     uint8_t c;
1689     uint8_t c2;
1690     const char *escape;
1691
1692     ds_put_char(ds, '"');
1693     while ((c = *string++) != '\0') {
1694         escape = chars_escaping[c];
1695         while ((c2 = *escape++) != '\0') {
1696             ds_put_char(ds, c2);
1697         }
1698     }
1699     ds_put_char(ds, '"');
1700 }