silo/masstree/json.cc

   1 /* Masstree
   2  * Eddie Kohler, Yandong Mao, Robert Morris
   3  * Copyright (c) 2012-2014 President and Fellows of Harvard College
   4  * Copyright (c) 2012-2014 Massachusetts Institute of Technology
   5  *
   6  * Permission is hereby granted, free of charge, to any person obtaining a
   7  * copy of this software and associated documentation files (the "Software"),
   8  * to deal in the Software without restriction, subject to the conditions
   9  * listed in the Masstree LICENSE file. These conditions include: you must
  10  * preserve this copyright notice, and you cannot mention the copyright
  11  * holders in advertising related to the Software without their permission.
  12  * The Software is provided WITHOUT ANY WARRANTY, EXPRESS OR IMPLIED. This
  13  * notice is a summary of the Masstree LICENSE file; the license in that file
  14  * is legally binding.
  15  */
  16 // -*- c-basic-offset: 4 -*-
  17 #include "json.hh"
  18 #include "compiler.hh"
  19 #include <ctype.h>
  20 namespace lcdf {
  21
  22 /** @class Json
  23     @brief Json data.
  24
  25     The Json class represents Json data: null values, booleans, numbers,
  26     strings, and combinations of these primitives into arrays and objects.
  27
  28     Json objects are not references, and two Json values cannot share
  29     subobjects. This differs from Javascript. For example:
  30
  31     <code>
  32     Json j1 = Json::make_object(), j2 = Json::make_object();
  33     j1.set("a", j2); // stores a COPY of j2 in j1
  34     j2.set("b", 1);
  35     assert(j1.unparse() == "{\"a\":{}}");
  36     assert(j2.unparse() == "{\"b\":1}");
  37     </code>
  38
  39     Compare this with the Javascript code:
  40
  41     <code>
  42     var j1 = {}, j2 = {};
  43     j1.a = j2; // stores a REFERENCE to j2 in j1
  44     j2.b = 1;
  45     assert(JSON.stringify(j1) == "{\"a\":{\"b\":1}}");
  46     </code>
  47
  48     Most Json functions for extracting components and typed values behave
  49     liberally. For example, objects silently convert to integers, and
  50     extracting properties from non-objects is allowed. This should make it
  51     easier to work with untrusted objects. (Json objects often originate
  52     from untrusted sources, and may not have the types you expect.) If you
  53     prefer an assertion to fail when a Json object has an unexpected type,
  54     use the checked <tt>as_</tt> and <code>at</code> functions, rather than
  55     the liberal <tt>to_</tt>, <tt>get</tt>, and <tt>operator[]</code>
  56     functions. */
  57
  58 const Json::null_t Json::null;
  59 const Json Json::null_json;
  60 static const String array_string("[Array]", 7);
  61 static const String object_string("[Object]", 8);
  62
  63 // Array internals
  64
  65 Json::ArrayJson* Json::ArrayJson::make(int n) {
  66     int cap = n < 8 ? 8 : n;
  67     char* buf = new char[sizeof(ArrayJson) + cap * sizeof(Json)];
  68     return new((void*) buf) ArrayJson(cap);
  69 }
  70
  71 void Json::ArrayJson::destroy(ArrayJson* aj) {
  72     if (aj)
  73         for (int i = 0; i != aj->size; ++i)
  74             aj->a[i].~Json();
  75     delete[] reinterpret_cast<char*>(aj);
  76 }
  77
  78
  79 // Object internals
  80
  81 Json::ObjectJson::ObjectJson(const ObjectJson &x)
  82     : ComplexJson(), os_(x.os_), n_(x.n_), capacity_(x.capacity_),
  83       hash_(x.hash_)
  84 {
  85     size = x.size;
  86     grow(true);
  87 }
  88
  89 Json::ObjectJson::~ObjectJson()
  90 {
  91     ObjectItem *ob = os_, *oe = ob + n_;
  92     for (; ob != oe; ++ob)
  93         if (ob->next_ > -2)
  94             ob->~ObjectItem();
  95     delete[] reinterpret_cast<char *>(os_);
  96 }
  97
  98 void Json::ObjectJson::grow(bool copy)
  99 {
 100     if (copy && !capacity_)
 101         return;
 102     int new_capacity;
 103     if (copy)
 104         new_capacity = capacity_;
 105     else if (capacity_)
 106         new_capacity = capacity_ * 2;
 107     else
 108         new_capacity = 8;
 109     ObjectItem *new_os = reinterpret_cast<ObjectItem *>(operator new[](sizeof(ObjectItem) * new_capacity));
 110     ObjectItem *ob = os_, *oe = ob + n_;
 111     for (ObjectItem *oi = new_os; ob != oe; ++oi, ++ob) {
 112         if (ob->next_ == -2)
 113             oi->next_ = -2;
 114         else if (copy)
 115             new((void*) oi) ObjectItem(ob->v_.first, ob->v_.second, ob->next_);
 116         else
 117             memcpy(oi, ob, sizeof(ObjectItem));
 118     }
 119     if (!copy)
 120         operator delete[](reinterpret_cast<void *>(os_));
 121     os_ = new_os;
 122     capacity_ = new_capacity;
 123 }
 124
 125 void Json::ObjectJson::rehash()
 126 {
 127     hash_.assign(hash_.size() * 2, -1);
 128     for (int i = n_ - 1; i >= 0; --i) {
 129         ObjectItem &oi = item(i);
 130         if (oi.next_ > -2) {
 131             int b = bucket(oi.v_.first.data(), oi.v_.first.length());
 132             oi.next_ = hash_[b];
 133             hash_[b] = i;
 134         }
 135     }
 136 }
 137
 138 int Json::ObjectJson::find_insert(const String &key, const Json &value)
 139 {
 140     if (hash_.empty())
 141         hash_.assign(8, -1);
 142     int *b = &hash_[bucket(key.data(), key.length())], chain = 0;
 143     while (*b >= 0 && os_[*b].v_.first != key) {
 144         b = &os_[*b].next_;
 145         ++chain;
 146     }
 147     if (*b >= 0)
 148         return *b;
 149     else {
 150         *b = n_;
 151         if (n_ == capacity_)
 152             grow(false);
 153         // NB 'b' is invalid now
 154         new ((void *) &os_[n_]) ObjectItem(key, value, -1);
 155         ++n_;
 156         ++size;
 157         if (chain > 4)
 158             rehash();
 159         return n_ - 1;
 160     }
 161 }
 162
 163 Json &Json::ObjectJson::get_insert(Str key)
 164 {
 165     if (hash_.empty())
 166         hash_.assign(8, -1);
 167     int *b = &hash_[bucket(key.data(), key.length())], chain = 0;
 168     while (*b >= 0 && os_[*b].v_.first != key) {
 169         b = &os_[*b].next_;
 170         ++chain;
 171     }
 172     if (*b >= 0)
 173         return os_[*b].v_.second;
 174     else {
 175         *b = n_;
 176         if (n_ == capacity_)
 177             grow(false);
 178         // NB 'b' is invalid now
 179         new ((void *) &os_[n_]) ObjectItem(String(key.data(), key.length()), null_json, -1);
 180         ++n_;
 181         ++size;
 182         if (chain > 4)
 183             rehash();
 184         return os_[n_ - 1].v_.second;
 185     }
 186 }
 187
 188 void Json::ObjectJson::erase(int p) {
 189     const ObjectItem& oi = item(p);
 190     int* b = &hash_[bucket(oi.v_.first.data(), oi.v_.first.length())];
 191     while (*b >= 0 && *b != p)
 192         b = &os_[*b].next_;
 193     assert(*b == p);
 194     *b = os_[p].next_;
 195     os_[p].~ObjectItem();
 196     os_[p].next_ = -2;
 197     --size;
 198 }
 199
 200 Json::size_type Json::ObjectJson::erase(Str key) {
 201     int* b = &hash_[bucket(key.data(), key.length())];
 202     while (*b >= 0 && os_[*b].v_.first != key)
 203         b = &os_[*b].next_;
 204     if (*b >= 0) {
 205         int p = *b;
 206         *b = os_[p].next_;
 207         os_[p].~ObjectItem();
 208         os_[p].next_ = -2;
 209         --size;
 210         return 1;
 211     } else
 212         return 0;
 213 }
 214
 215 namespace {
 216 template <typename T> bool string_to_int_key(const char *first,
 217                                              const char *last, T& x)
 218 {
 219     if (first == last || !isdigit((unsigned char) *first)
 220         || (first[0] == '0' && first + 1 != last))
 221         return false;
 222     // XXX integer overflow
 223     x = *first - '0';
 224     for (++first; first != last && isdigit((unsigned char) *first); ++first)
 225         x = 10 * x + *first - '0';
 226     return first == last;
 227 }
 228 }
 229
 230 void Json::hard_uniqueify_array(bool convert, int ncap_in) {
 231     if (!convert)
 232         precondition(is_null() || is_array());
 233
 234     rep_type old_u = u_;
 235
 236     unsigned ncap = std::max(ncap_in, 8);
 237     if (old_u.x.type == j_array && old_u.a.x)
 238         ncap = std::max(ncap, unsigned(old_u.a.x->size));
 239     // New capacity: Round up to a power of 2, up to multiples of 1<<14.
 240     unsigned xcap = iceil_log2(ncap);
 241     if (xcap <= (1U << 14))
 242         ncap = xcap;
 243     else
 244         ncap = ((ncap - 1) | ((1U << 14) - 1)) + 1;
 245     u_.a.x = ArrayJson::make(ncap);
 246     u_.a.type = j_array;
 247
 248     if (old_u.x.type == j_array && old_u.a.x && old_u.a.x->refcount == 1) {
 249         u_.a.x->size = old_u.a.x->size;
 250         memcpy(u_.a.x->a, old_u.a.x->a, sizeof(Json) * u_.a.x->size);
 251         delete[] reinterpret_cast<char*>(old_u.a.x);
 252     } else if (old_u.x.type == j_array && old_u.a.x) {
 253         u_.a.x->size = old_u.a.x->size;
 254         Json* last = u_.a.x->a + u_.a.x->size;
 255         for (Json* it = u_.a.x->a, *oit = old_u.a.x->a; it != last; ++it, ++oit)
 256             new((void*) it) Json(*oit);
 257         old_u.a.x->deref(j_array);
 258     } else if (old_u.x.type == j_object && old_u.o.x) {
 259         ObjectItem *ob = old_u.o.x->os_, *oe = ob + old_u.o.x->n_;
 260         unsigned i;
 261         for (; ob != oe; ++ob)
 262             if (ob->next_ > -2
 263                 && string_to_int_key(ob->v_.first.begin(),
 264                                      ob->v_.first.end(), i)) {
 265                 if (i >= unsigned(u_.a.x->capacity))
 266                     hard_uniqueify_array(false, i + 1);
 267                 if (i >= unsigned(u_.a.x->size)) {
 268                     memset(&u_.a.x->a[u_.a.x->size], 0, sizeof(Json) * (i + 1 - u_.a.x->size));
 269                     u_.a.x->size = i + 1;
 270                 }
 271                 u_.a.x->a[i] = ob->v_.second;
 272             }
 273         old_u.o.x->deref(j_object);
 274     } else if (old_u.x.type < 0)
 275         old_u.str.deref();
 276 }
 277
 278 void Json::hard_uniqueify_object(bool convert) {
 279     if (!convert)
 280         precondition(is_null() || is_object());
 281     ObjectJson* noj;
 282     if (u_.x.type == j_object && u_.o.x) {
 283         noj = new ObjectJson(*u_.o.x);
 284         u_.o.x->deref(j_object);
 285     } else if (u_.x.type == j_array && u_.a.x) {
 286         noj = new ObjectJson;
 287         for (int i = 0; i != u_.a.x->size; ++i)
 288             noj->find_insert(String(i), u_.a.x->a[i]);
 289         u_.a.x->deref(j_array);
 290     } else {
 291         noj = new ObjectJson;
 292         if (u_.x.type < 0)
 293             u_.str.deref();
 294     }
 295     u_.o.x = noj;
 296     u_.o.type = j_object;
 297 }
 298
 299 void Json::clear() {
 300     static_assert(offsetof(rep_type, i.type) == offsetof(rep_type, x.type), "odd Json::rep_type.i.type offset");
 301     static_assert(offsetof(rep_type, u.type) == offsetof(rep_type, x.type), "odd Json::rep_type.u.type offset");
 302     static_assert(offsetof(rep_type, d.type) == offsetof(rep_type, x.type), "odd Json::rep_type.d.type offset");
 303     static_assert(offsetof(rep_type, str.memo_offset) == offsetof(rep_type, x.type), "odd Json::rep_type.str.memo_offset offset");
 304     static_assert(offsetof(rep_type, a.type) == offsetof(rep_type, x.type), "odd Json::rep_type.a.type offset");
 305     static_assert(offsetof(rep_type, o.type) == offsetof(rep_type, x.type), "odd Json::rep_type.o.type offset");
 306
 307     if (u_.x.type == j_array) {
 308         if (u_.a.x && u_.a.x->refcount == 1) {
 309             Json* last = u_.a.x->a + u_.a.x->size;
 310             for (Json* it = u_.a.x->a; it != last; ++it)
 311                 it->~Json();
 312             u_.a.x->size = 0;
 313         } else if (u_.a.x) {
 314             u_.a.x->deref(j_array);
 315             u_.a.x = 0;
 316         }
 317     } else if (u_.x.type == j_object) {
 318         if (u_.o.x && u_.o.x->refcount == 1) {
 319             ObjectItem* last = u_.o.x->os_ + u_.o.x->n_;
 320             for (ObjectItem* it = u_.o.x->os_; it != last; ++it)
 321                 if (it->next_ != -2)
 322                     it->~ObjectItem();
 323             u_.o.x->n_ = u_.o.x->size = 0;
 324             u_.o.x->hash_.assign(u_.o.x->hash_.size(), -1);
 325         } else if (u_.o.x) {
 326             u_.o.x->deref(j_object);
 327             u_.o.x = 0;
 328         }
 329     } else {
 330         if (u_.x.type < 0)
 331             u_.str.deref();
 332         memset(&u_, 0, sizeof(u_));
 333     }
 334 }
 335
 336 void* Json::uniqueify_array_insert(bool convert, size_type pos) {
 337     size_type size = u_.a.x ? u_.a.x->size : 0;
 338     uniqueify_array(convert, size + 1);
 339     if (pos == (size_type) -1)
 340         pos = size;
 341     precondition(pos >= 0 && pos <= size);
 342     if (pos != size)
 343         memmove(&u_.a.x->a[pos + 1], &u_.a.x->a[pos], (size - pos) * sizeof(Json));
 344     ++u_.a.x->size;
 345     return (void*) &u_.a.x->a[pos];
 346 }
 347
 348 Json::array_iterator Json::erase(array_iterator first, array_iterator last) {
 349     if (first < last) {
 350         uniqueify_array(false, 0);
 351         size_type fpos = first - abegin();
 352         size_type lpos = last - abegin();
 353         size_type size = u_.a.x->size;
 354         for (size_type pos = fpos; pos != lpos; ++pos)
 355             u_.a.x->a[pos].~Json();
 356         if (lpos != size)
 357             memmove(&u_.a.x->a[fpos], &u_.a.x->a[lpos],
 358                     (size - lpos) * sizeof(Json));
 359         u_.a.x->size -= lpos - fpos;
 360     }
 361     return first;
 362 }
 363
 364 /** @brief Reserve the array Json to hold at least @a n items. */
 365 void Json::reserve(size_type n) {
 366     uniqueify_array(false, n);
 367 }
 368
 369 /** @brief Resize the array Json to size @a n. */
 370 void Json::resize(size_type n) {
 371     uniqueify_array(false, n);
 372     while (u_.a.x->size > n && u_.a.x->size > 0) {
 373         --u_.a.x->size;
 374         u_.a.x->a[u_.a.x->size].~Json();
 375     }
 376     while (u_.a.x->size < n)
 377         push_back(Json());
 378 }
 379
 380
 381 // Primitives
 382
 383 int64_t Json::hard_to_i() const {
 384     switch (u_.x.type) {
 385     case j_array:
 386     case j_object:
 387         return size();
 388     case j_bool:
 389     case j_int:
 390         return u_.i.x;
 391     case j_unsigned:
 392         return u_.u.x;
 393     case j_double:
 394         return int64_t(u_.d.x);
 395     case j_null:
 396     case j_string:
 397     default:
 398         if (!u_.x.x)
 399             return 0;
 400         invariant(u_.x.type <= 0);
 401         const char *b = reinterpret_cast<const String&>(u_.str).c_str();
 402         char *s;
 403 #if SIZEOF_LONG >= 8
 404         long x = strtol(b, &s, 0);
 405 #else
 406         long long x = strtoll(b, &s, 0);
 407 #endif
 408         if (s == b + u_.str.length)
 409             return x;
 410         else
 411             return (long) strtod(b, 0);
 412     }
 413 }
 414
 415 uint64_t Json::hard_to_u() const {
 416     switch (u_.x.type) {
 417     case j_array:
 418     case j_object:
 419         return size();
 420     case j_bool:
 421     case j_int:
 422         return u_.i.x;
 423     case j_unsigned:
 424         return u_.u.x;
 425     case j_double:
 426         return uint64_t(u_.d.x);
 427     case j_null:
 428     case j_string:
 429     default:
 430         if (!u_.x.x)
 431             return 0;
 432         const char* b = reinterpret_cast<const String&>(u_.str).c_str();
 433         char *s;
 434 #if SIZEOF_LONG >= 8
 435         unsigned long x = strtoul(b, &s, 0);
 436 #else
 437         unsigned long long x = strtoull(b, &s, 0);
 438 #endif
 439         if (s == b + u_.str.length)
 440             return x;
 441         else
 442             return (uint64_t) strtod(b, 0);
 443     }
 444 }
 445
 446 double Json::hard_to_d() const {
 447     switch (u_.x.type) {
 448     case j_array:
 449     case j_object:
 450         return size();
 451     case j_bool:
 452     case j_int:
 453         return u_.i.x;
 454     case j_unsigned:
 455         return u_.u.x;
 456     case j_double:
 457         return u_.d.x;
 458     case j_null:
 459     case j_string:
 460     default:
 461         if (!u_.x.x)
 462             return 0;
 463         else
 464             return strtod(reinterpret_cast<const String&>(u_.str).c_str(), 0);
 465     }
 466 }
 467
 468 bool Json::hard_to_b() const {
 469     switch (u_.x.type) {
 470     case j_array:
 471     case j_object:
 472         return !empty();
 473     case j_bool:
 474     case j_int:
 475     case j_unsigned:
 476         return u_.i.x != 0;
 477     case j_double:
 478         return u_.d.x;
 479     case j_null:
 480     case j_string:
 481     default:
 482         return u_.str.length != 0;
 483     }
 484 }
 485
 486 String Json::hard_to_s() const {
 487     switch (u_.x.type) {
 488     case j_array:
 489         return array_string;
 490     case j_object:
 491         return object_string;
 492     case j_bool:
 493         return String(bool(u_.i.x));
 494     case j_int:
 495         return String(u_.i.x);
 496     case j_unsigned:
 497         return String(u_.u.x);
 498     case j_double:
 499         return String(u_.d.x);
 500     case j_null:
 501     case j_string:
 502     default:
 503         if (!u_.x.x)
 504             return String::make_empty();
 505         else
 506             return String(u_.str);
 507     }
 508 }
 509
 510 const Json& Json::hard_get(Str key) const {
 511     ArrayJson *aj;
 512     unsigned i;
 513     if (is_array() && (aj = ajson())
 514         && string_to_int_key(key.begin(), key.end(), i)
 515         && i < unsigned(aj->size))
 516         return aj->a[i];
 517     else
 518         return make_null();
 519 }
 520
 521 const Json& Json::hard_get(size_type x) const {
 522     if (is_object() && u_.o.x)
 523         return get(String(x));
 524     else
 525         return make_null();
 526 }
 527
 528 Json& Json::hard_get_insert(size_type x) {
 529     if (is_object())
 530         return get_insert(String(x));
 531     else {
 532         uniqueify_array(true, x + 1);
 533         if (u_.a.x->size <= x) {
 534             memset(&u_.a.x->a[u_.a.x->size], 0, sizeof(Json) * (x + 1 - u_.a.x->size));
 535             u_.a.x->size = x + 1;
 536         }
 537         return u_.a.x->a[x];
 538     }
 539 }
 540
 541 bool operator==(const Json& a, const Json& b) {
 542     if ((a.u_.x.type > 0 || b.u_.x.type > 0)
 543         && a.u_.x.type != b.u_.x.type)
 544         return a.u_.u.x == b.u_.u.x
 545             && a.u_.i.x >= 0
 546             && a.is_int()
 547             && b.is_int();
 548     else if (a.u_.x.type == Json::j_int
 549              || a.u_.x.type == Json::j_unsigned
 550              || a.u_.x.type == Json::j_bool)
 551         return a.u_.u.x == b.u_.u.x;
 552     else if (a.u_.x.type == Json::j_double)
 553         return a.u_.d.x == b.u_.d.x;
 554     else if (a.u_.x.type > 0 || !a.u_.x.x || !b.u_.x.x)
 555         return a.u_.x.x == b.u_.x.x;
 556     else
 557         return String(a.u_.str) == String(b.u_.str);
 558 }
 559
 560
 561 // Unparsing
 562
 563 Json::unparse_manipulator Json::default_manipulator;
 564
 565 bool Json::unparse_is_complex() const {
 566     if (is_object()) {
 567         if (ObjectJson *oj = ojson()) {
 568             if (oj->size > 5)
 569                 return true;
 570             ObjectItem *ob = oj->os_, *oe = ob + oj->n_;
 571             for (; ob != oe; ++ob)
 572                 if (ob->next_ > -2 && !ob->v_.second.empty() && !ob->v_.second.is_primitive())
 573                     return true;
 574         }
 575     } else if (is_array()) {
 576         if (ArrayJson *aj = ajson()) {
 577             if (aj->size > 8)
 578                 return true;
 579             for (Json* it = aj->a; it != aj->a + aj->size; ++it)
 580                 if (!it->empty() && !it->is_primitive())
 581                     return true;
 582         }
 583     }
 584     return false;
 585 }
 586
 587 void Json::unparse_indent(StringAccum &sa, const unparse_manipulator &m, int depth)
 588 {
 589     sa << '\n';
 590     depth *= (m.tab_width() ? m.tab_width() : 8);
 591     sa.append_fill('\t', depth / 8);
 592     sa.append_fill(' ', depth % 8);
 593 }
 594
 595 namespace {
 596 const char* const upx_normal[] = {":", ","};
 597 const char* const upx_expanded[] = {": ", ","};
 598 const char* const upx_separated[] = {": ", ", "};
 599 }
 600
 601 void Json::hard_unparse(StringAccum &sa, const unparse_manipulator &m, int depth) const
 602 {
 603     if (is_object() || is_array()) {
 604         bool expanded = depth < m.indent_depth() && unparse_is_complex();
 605         const char* const* upx;
 606         if (expanded)
 607             upx = upx_expanded;
 608         else if (m.space_separator())
 609             upx = upx_separated;
 610         else
 611             upx = upx_normal;
 612
 613         if (is_object() && !u_.x.x)
 614             sa << "{}";
 615         else if (is_object()) {
 616             sa << '{';
 617             bool rest = false;
 618             ObjectJson *oj = ojson();
 619             ObjectItem *ob = oj->os_, *oe = ob + oj->n_;
 620             for (; ob != oe; ++ob)
 621                 if (ob->next_ > -2) {
 622                     if (rest)
 623                         sa << upx[1];
 624                     if (expanded)
 625                         unparse_indent(sa, m, depth + 1);
 626                     sa << '\"';
 627                     ob->v_.first.encode_json(sa);
 628                     sa << '\"' << upx[0];
 629                     ob->v_.second.hard_unparse(sa, m, depth + 1);
 630                     rest = true;
 631                 }
 632             if (expanded)
 633                 unparse_indent(sa, m, depth);
 634             sa << '}';
 635         } else if (!u_.x.x)
 636             sa << "[]";
 637         else {
 638             sa << '[';
 639             bool rest = false;
 640             ArrayJson* aj = ajson();
 641             for (Json* it = aj->a; it != aj->a + aj->size; ++it) {
 642                 if (rest)
 643                     sa << upx[1];
 644                 if (expanded)
 645                     unparse_indent(sa, m, depth + 1);
 646                 it->hard_unparse(sa, m, depth + 1);
 647                 rest = true;
 648             }
 649             if (expanded)
 650                 unparse_indent(sa, m, depth);
 651             sa << ']';
 652         }
 653     } else if (u_.x.type == j_null && !u_.x.x)
 654         sa.append("null", 4);
 655     else if (u_.x.type <= 0) {
 656         sa << '\"';
 657         reinterpret_cast<const String&>(u_.str).encode_json(sa);
 658         sa << '\"';
 659     } else if (u_.x.type == j_bool) {
 660         bool b = u_.i.x;
 661         sa.append(&"false\0true"[-b & 6], 5 - b);
 662     } else if (u_.x.type == j_int)
 663         sa << u_.i.x;
 664     else if (u_.x.type == j_unsigned)
 665         sa << u_.u.x;
 666     else if (u_.x.type == j_double)
 667         sa << u_.d.x;
 668
 669     if (depth == 0 && m.newline_terminator())
 670         sa << '\n';
 671 }
 672
 673
 674 bool
 675 Json::assign_parse(const char* first, const char* last, const String& str)
 676 {
 677     using std::swap;
 678     Json::streaming_parser jsp;
 679     first = jsp.consume(first, last, str, true);
 680     if (first != last && (*first == ' ' || *first == '\n' || *first == '\r'
 681                           || *first == '\t'))
 682         ++first;
 683     if (first == last && jsp.success()) {
 684         swap(jsp.result(), *this);
 685         return true;
 686     } else
 687         return false;
 688 }
 689
 690 static inline bool in_range(uint8_t x, unsigned low, unsigned high) {
 691     return (unsigned) x - low < high - low;
 692 }
 693
 694 static inline bool in_range(int x, unsigned low, unsigned high) {
 695     return (unsigned) x - low < high - low;
 696 }
 697
 698 inline const uint8_t* Json::streaming_parser::error_at(const uint8_t* here) {
 699     state_ = st_error;
 700     return here;
 701 }
 702
 703 inline Json* Json::streaming_parser::current() {
 704     return stack_.empty() ? &json_ : stack_.back();
 705 }
 706
 707 const uint8_t*
 708 Json::streaming_parser::consume(const uint8_t* first,
 709                                 const uint8_t* last,
 710                                 const String& str,
 711                                 bool complete) {
 712     using std::swap;
 713     Json j;
 714
 715     if (state_ >= 0 && (state_ & st_partmask)) {
 716         if ((state_ & st_stringpart) && state_ >= st_object_colon)
 717             goto string_object_key;
 718         else if (state_ & st_stringpart)
 719             goto string_value;
 720         else if (state_ & st_primitivepart)
 721             goto primitive;
 722         else
 723             goto number;
 724     }
 725
 726     while (state_ >= 0 && first != last)
 727         switch (*first) {
 728         case ' ':
 729         case '\n':
 730         case '\r':
 731         case '\t':
 732             while (first != last && *first <= 32
 733                    && (*first == ' ' || *first == '\n' || *first == '\r'
 734                        || *first == '\t'))
 735                 ++first;
 736             break;
 737
 738         case ',':
 739             if (state_ == st_array_delim)
 740                 state_ = st_array_value;
 741             else if (state_ == st_object_delim)
 742                 state_ = st_object_key;
 743             else
 744                 goto error_here;
 745             ++first;
 746             break;
 747
 748         case ':':
 749             if (state_ == st_object_colon) {
 750                 state_ = st_object_value;
 751                 ++first;
 752                 break;
 753             } else
 754                 goto error_here;
 755
 756         case '{':
 757             if (state_ <= st_object_value) {
 758                 if (stack_.size() == max_depth)
 759                     goto error_here;
 760                 ++first;
 761                 if (state_ == st_initial && json_.is_o()) {
 762                     swap(j, json_);
 763                     j.clear();
 764                 } else
 765                     j = Json::make_object();
 766                 goto value;
 767             } else
 768                 goto error_here;
 769
 770         case '}':
 771             if (state_ == st_object_initial || state_ == st_object_delim) {
 772                 ++first;
 773                 goto close_value;
 774             } else
 775                 goto error_here;
 776
 777         case '[':
 778             if (state_ <= st_object_value) {
 779                 if (stack_.size() == max_depth)
 780                     goto error_here;
 781                 ++first;
 782                 if (state_ == st_initial && json_.is_a()) {
 783                     swap(j, json_);
 784                     j.clear();
 785                 } else
 786                     j = Json::make_array();
 787                 goto value;
 788             } else
 789                 goto error_here;
 790
 791         case ']':
 792             if (state_ == st_array_initial || state_ == st_array_delim) {
 793                 ++first;
 794                 goto close_value;
 795             } else
 796                 goto error_here;
 797
 798         case '\"':
 799             if (state_ <= st_object_value) {
 800                 str_ = String();
 801                 ++first;
 802             string_value:
 803                 first = consume_string(first, last, str);
 804                 if (state_ >= 0 && !(state_ & st_stringpart)) {
 805                     j = Json(std::move(str_));
 806                     goto value;
 807                 }
 808             } else if (state_ == st_object_initial || state_ == st_object_key) {
 809                 state_ = st_object_colon;
 810                 str_ = String();
 811                 ++first;
 812             string_object_key:
 813                 first = consume_string(first, last, str);
 814                 if (state_ >= 0 && !(state_ & st_stringpart)) {
 815                     stack_.push_back(&current()->get_insert(std::move(str_)));
 816                     continue;
 817                 }
 818             } else
 819                 goto error_here;
 820             break;
 821
 822         case 'n':
 823         case 'f':
 824         case 't':
 825             if (state_ <= st_object_value) {
 826             primitive:
 827                 first = consume_primitive(first, last, j);
 828                 if (state_ >= 0 && !(state_ & st_primitivepart))
 829                     goto value;
 830             } else
 831                 goto error_here;
 832             break;
 833
 834         case '-':
 835         case '0':
 836         case '1':
 837         case '2':
 838         case '3':
 839         case '4':
 840         case '5':
 841         case '6':
 842         case '7':
 843         case '8':
 844         case '9':
 845             if (state_ <= st_object_value) {
 846             number:
 847                 first = consume_number(first, last, str, complete, j);
 848                 if (state_ >= 0 && !(state_ & st_numberpart))
 849                     goto value;
 850             } else
 851                 goto error_here;
 852             break;
 853
 854         default:
 855         error_here:
 856             return error_at(first);
 857
 858         value: {
 859             Json* jp = current();
 860             if (state_ != st_initial && jp->is_a()) {
 861                 jp->push_back(std::move(j));
 862                 jp = &jp->back();
 863             } else
 864                 swap(*jp, j);
 865
 866             if (state_ == st_object_value)
 867                 stack_.pop_back();
 868             if (jp->is_a() || jp->is_o()) {
 869                 if (state_ != st_initial)
 870                     stack_.push_back(jp);
 871                 state_ = jp->is_a() ? st_array_initial : st_object_initial;
 872             } else if (state_ == st_object_value)
 873                 state_ = st_object_delim;
 874             else if (state_ == st_array_initial || state_ == st_array_value)
 875                 state_ = st_array_delim;
 876             else {
 877                 state_ = st_final;
 878                 return first;
 879             }
 880             break;
 881         }
 882
 883         close_value:
 884             if (stack_.empty()) {
 885                 state_ = st_final;
 886                 return first;
 887             } else {
 888                 stack_.pop_back();
 889                 state_ = current()->is_a() ? st_array_delim : st_object_delim;
 890             }
 891             break;
 892         }
 893
 894     return first;
 895 }
 896
 897 const uint8_t*
 898 Json::streaming_parser::consume_string(const uint8_t* first,
 899                                        const uint8_t* last,
 900                                        const String& str) {
 901     StringAccum sa = StringAccum::make_transfer(str_);
 902
 903     if (unlikely(state_ & st_partlenmask)) {
 904         first = consume_stringpart(sa, first, last);
 905         if (state_ == st_error)
 906             return first;
 907     }
 908
 909     const uint8_t* prev = first;
 910     while (first != last) {
 911         if (likely(in_range(*first, 32, 128)) && *first != '\\' && *first != '\"')
 912             ++first;
 913         else if (*first == '\\') {
 914             sa.append(prev, first);
 915             prev = first = consume_backslash(sa, first, last);
 916             if (state_ == st_error)
 917                 return first;
 918         } else if (*first == '\"')
 919             break;
 920         else if (unlikely(!in_range(*first, 0xC2, 0xF5)))
 921             return error_at(first);
 922         else {
 923             int want = 2 + (*first >= 0xE0) + (*first >= 0xF0);
 924             int n = last - first < want ? last - first : want;
 925             if ((n > 1 && unlikely(!in_range(first[1], 0x80, 0xC0)))
 926                 || (*first >= 0xE0
 927                     && ((*first == 0xE0 && first[1] < 0xA0) /* overlong */
 928                         || (*first == 0xED && first[1] >= 0xA0) /* surrogate */
 929                         || (*first == 0xF0 && first[1] < 0x90) /* overlong */
 930                         || (*first == 0xF4 && first[1] >= 0x90) /* not a char */
 931                         )))
 932                 return error_at(first + 1);
 933             else if (n > 2 && unlikely(!in_range(first[2], 0x80, 0xC0)))
 934                 return error_at(first + 2);
 935             else if (n > 3 && unlikely(!in_range(first[3], 0x80, 0xC0)))
 936                 return error_at(first + 3);
 937             first += n;
 938             if (n != want) {
 939                 state_ |= n;
 940                 break;
 941             }
 942         }
 943     }
 944
 945     if (!sa.empty() || first == last)
 946         sa.append(prev, first);
 947     if (first != last) {
 948         if (!sa.empty())
 949             str_ = sa.take_string();
 950         else if (prev >= str.ubegin() && first <= str.uend())
 951             str_ = str.fast_substring(prev, first);
 952         else
 953             str_ = String(prev, first);
 954         state_ &= ~st_stringpart;
 955         return first + 1;
 956     } else {
 957         state_ |= st_stringpart;
 958         str_ = sa.take_string();
 959         return first;
 960     }
 961 }
 962
 963 const uint8_t*
 964 Json::streaming_parser::consume_stringpart(StringAccum& sa,
 965                                            const uint8_t* first,
 966                                            const uint8_t* last) {
 967     while ((state_ & st_partlenmask) && first != last) {
 968         int part = state_ & st_partlenmask;
 969         uint8_t tag = sa[sa.length() - part];
 970         if ((tag != '\\' && (*first & 0xC0) != 0x80)
 971             || (tag == '\\' && part == 6 && *first != '\\')
 972             || (tag == '\\' && part == 7 && *first != 'u')
 973             || (tag == '\\' && part != 1 && part != 6 && part != 7
 974                 && !isxdigit(*first))) {
 975             state_ = st_error;
 976             break;
 977         }
 978         sa.append(*first);
 979         if ((tag != '\\' && part == 1 + (tag >= 0xE0) + (tag >= 0xF0))
 980             || (tag == '\\' && (part == 1 || part == 5 || part == 11))) {
 981             uint8_t buf[12];
 982             memcpy(buf, sa.end() - part - 1, part + 1);
 983             sa.adjust_length(-part - 1);
 984             state_ -= st_stringpart | part;
 985             str_ = sa.take_string();
 986             (void) consume_string(buf, buf + part + 1, String());
 987             if (state_ == st_error)
 988                 break;
 989             sa = StringAccum::make_transfer(str_);
 990         } else
 991             ++state_;
 992         ++first;
 993     }
 994     return first;
 995 }
 996
 997 const uint8_t*
 998 Json::streaming_parser::consume_backslash(StringAccum& sa,
 999                                           const uint8_t* first,
1000                                           const uint8_t* last) {
1001     const uint8_t* prev = first;
1002     int ch = 0;
1003
1004     if (first + 1 == last)
1005         goto incomplete;
1006     else if (first[1] == '\"' || first[1] == '\\' || first[1] == '/')
1007         ch = first[1];
1008     else if (first[1] == 'b')
1009         ch = '\b';
1010     else if (first[1] == 'f')
1011         ch = '\f';
1012     else if (first[1] == 'n')
1013         ch = '\n';
1014     else if (first[1] == 'r')
1015         ch = '\r';
1016     else if (first[1] == 't')
1017         ch = '\t';
1018     else if (first[1] == 'u') {
1019         for (int i = 2; i < 6; ++i) {
1020             if (first + i == last)
1021                 goto incomplete;
1022             else if (in_range(first[i], '0', '9' + 1))
1023                 ch = 16 * ch + first[i] - '0';
1024             else if (in_range(first[i], 'A', 'F' + 1))
1025                 ch = 16 * ch + first[i] - 'A' + 10;
1026             else if (in_range(first[i], 'a', 'f' + 1))
1027                 ch = 16 * ch + first[i] - 'a' + 10;
1028             else
1029                 return error_at(&first[i]);
1030         }
1031         first += 4;
1032         // special handling required for surrogate pairs
1033         if (unlikely(in_range(ch, 0xD800, 0xE000))) {
1034             if (ch >= 0xDC00)
1035                 return error_at(&first[1]);
1036             else if (first + 2 == last)
1037                 goto incomplete;
1038             else if (first[2] != '\\')
1039                 return error_at(&first[2]);
1040             else if (first + 3 == last)
1041                 goto incomplete;
1042             else if (first[3] != 'u')
1043                 return error_at(&first[3]);
1044             int ch2 = 0;
1045             for (int i = 4; i < 8; ++i) {
1046                 if (first + i == last)
1047                     goto incomplete;
1048                 else if (in_range(first[i], '0', '9' + 1))
1049                     ch2 = 16 * ch2 + first[i] - '0';
1050                 else if (in_range(first[i], 'A', 'F' + 1))
1051                     ch2 = 16 * ch2 + first[i] - 'A' + 10;
1052                 else if (in_range(first[i], 'A', 'F' + 1))
1053                     ch2 = 16 * ch2 + first[i] - 'a' + 10;
1054                 else
1055                     return error_at(&first[i]);
1056             }
1057             if (!in_range(ch2, 0xDC00, 0xE000))
1058                 return error_at(&first[7]);
1059             ch = 0x10000 + (ch - 0xD800) * 0x400 + (ch2 - 0xDC00);
1060             first += 6;
1061         }
1062     }
1063
1064     if (!ch || !sa.append_utf8(ch))
1065         return error_at(&first[1]);
1066     return first + 2;
1067
1068  incomplete:
1069     state_ |= last - prev;
1070     sa.append(prev, last);
1071     return last;
1072 }
1073
1074 const uint8_t*
1075 Json::streaming_parser::consume_primitive(const uint8_t* first,
1076                                           const uint8_t* last,
1077                                           Json& j) {
1078     const char* t = "null\0false\0true";
1079     int n;
1080     if (unlikely(state_ & st_primitivepart)) {
1081         n = state_ & st_partlenmask;
1082         state_ &= ~st_partmask;
1083     } else {
1084         n = (*first == 'n' ? 1 : (*first == 'f' ? 6 : 12));
1085         ++first;
1086     }
1087
1088     for (; first != last && t[n]; ++n, ++first)
1089         if (t[n] != *first)
1090             return error_at(first);
1091
1092     if (t[n])
1093         state_ |= st_primitivepart | n;
1094     else if (n == 4)
1095         j = Json();
1096     else if (n == 10)
1097         j = Json(false);
1098     else
1099         j = Json(true);
1100     return first;
1101 }
1102
1103 const uint8_t*
1104 Json::streaming_parser::consume_number(const uint8_t* first,
1105                                        const uint8_t* last,
1106                                        const String& str,
1107                                        bool complete,
1108                                        Json& j) {
1109     const uint8_t* prev = first;
1110     int position = state_ & st_partlenmask;
1111
1112     switch (position) {
1113     case 0:
1114         if (*first == '-')
1115             ++first;
1116         /* fallthru */
1117     case 2:
1118         if (first != last && *first == '0') {
1119             position = 3;
1120             ++first;
1121         } else if (first != last && in_range(*first, '1', '9' + 1)) {
1122             position = 1;
1123             ++first;
1124         case 1:
1125             while (first != last && in_range(*first, '0', '9' + 1))
1126                 ++first;
1127         } else
1128             position = 2;
1129         /* fallthru */
1130     case 3:
1131         if (first != last && *first == '.') {
1132             ++first;
1133             goto decimal;
1134         }
1135     maybe_exponent:
1136         if (first != last && (*first == 'e' || *first == 'E')) {
1137             ++first;
1138             goto exponent;
1139         }
1140         break;
1141
1142     decimal:
1143     case 4:
1144         position = 4;
1145         if (first != last && in_range(*first, '0', '9' + 1)) {
1146             ++first;
1147             position = 5;
1148         }
1149         /* fallthru */
1150     case 5:
1151         while (first != last && in_range(*first, '0', '9' + 1))
1152             ++first;
1153         if (first != last && position == 5)
1154             goto maybe_exponent;
1155         break;
1156
1157     exponent:
1158     case 6:
1159         position = 6;
1160         if (first != last && (*first == '+' || *first == '-'))
1161             ++first;
1162         else if (first == last)
1163             break;
1164         /* fallthru */
1165     case 8:
1166         position = 8;
1167         if (first != last && in_range(*first, '0', '9' + 1)) {
1168             ++first;
1169             position = 9;
1170         }
1171         /* fallthru */
1172     case 9:
1173         while (first != last && in_range(*first, '0', '9' + 1))
1174             ++first;
1175         break;
1176     }
1177
1178     if (first != last || complete) {
1179         if (!(position & 1))
1180             goto error_here;
1181         last = first;
1182         if (state_ & st_partlenmask) {
1183             str_.append(prev, first);
1184             prev = str_.ubegin();
1185             first = str_.uend();
1186         }
1187         if (prev + 1 == first)
1188             j = Json(int(*prev - '0'));
1189         else if (position < 4) {
1190             bool negative = *prev == '-';
1191             prev += int(negative);
1192             uint64_t x = 0;
1193             while (prev != first) {
1194                 x = (x * 10) + *prev - '0';
1195                 ++prev;
1196             }
1197             if (negative)
1198                 j = Json(-int64_t(x));
1199             else
1200                 j = Json(x);
1201         } else {
1202             if (!(state_ & st_partlenmask))
1203                 str_ = String(prev, first);
1204             double x = strtod(str_.c_str(), 0);
1205             j = Json(x);
1206         }
1207         state_ &= ~st_partmask;
1208         str_ = String();
1209         return last;
1210     }
1211
1212     if (state_ & st_partmask)
1213         str_.append(prev, first);
1214     else if (prev >= str.ubegin() && first <= str.uend())
1215         str_ = str.substring(prev, first);
1216     else
1217         str_ = String(prev, first);
1218     state_ = (state_ & ~st_partmask) | st_numberpart | position;
1219     return first;
1220
1221  error_here:
1222     str_ = String();
1223     return error_at(first);
1224 }
1225
1226 } // namespace lcdf