lib/json.c

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