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