contrib/llvm/lib/Support/JSON.cpp

   1 //=== JSON.cpp - JSON value, parsing and serialization - C++ -----------*-===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===---------------------------------------------------------------------===//
   9
  10 #include "llvm/Support/JSON.h"
  11 #include "llvm/Support/ConvertUTF.h"
  12 #include "llvm/Support/Format.h"
  13 #include <cctype>
  14
  15 namespace llvm {
  16 namespace json {
  17
  18 Value &Object::operator[](const ObjectKey &K) {
  19   return try_emplace(K, nullptr).first->getSecond();
  20 }
  21 Value &Object::operator[](ObjectKey &&K) {
  22   return try_emplace(std::move(K), nullptr).first->getSecond();
  23 }
  24 Value *Object::get(StringRef K) {
  25   auto I = find(K);
  26   if (I == end())
  27     return nullptr;
  28   return &I->second;
  29 }
  30 const Value *Object::get(StringRef K) const {
  31   auto I = find(K);
  32   if (I == end())
  33     return nullptr;
  34   return &I->second;
  35 }
  36 llvm::Optional<std::nullptr_t> Object::getNull(StringRef K) const {
  37   if (auto *V = get(K))
  38     return V->getAsNull();
  39   return llvm::None;
  40 }
  41 llvm::Optional<bool> Object::getBoolean(StringRef K) const {
  42   if (auto *V = get(K))
  43     return V->getAsBoolean();
  44   return llvm::None;
  45 }
  46 llvm::Optional<double> Object::getNumber(StringRef K) const {
  47   if (auto *V = get(K))
  48     return V->getAsNumber();
  49   return llvm::None;
  50 }
  51 llvm::Optional<int64_t> Object::getInteger(StringRef K) const {
  52   if (auto *V = get(K))
  53     return V->getAsInteger();
  54   return llvm::None;
  55 }
  56 llvm::Optional<llvm::StringRef> Object::getString(StringRef K) const {
  57   if (auto *V = get(K))
  58     return V->getAsString();
  59   return llvm::None;
  60 }
  61 const json::Object *Object::getObject(StringRef K) const {
  62   if (auto *V = get(K))
  63     return V->getAsObject();
  64   return nullptr;
  65 }
  66 json::Object *Object::getObject(StringRef K) {
  67   if (auto *V = get(K))
  68     return V->getAsObject();
  69   return nullptr;
  70 }
  71 const json::Array *Object::getArray(StringRef K) const {
  72   if (auto *V = get(K))
  73     return V->getAsArray();
  74   return nullptr;
  75 }
  76 json::Array *Object::getArray(StringRef K) {
  77   if (auto *V = get(K))
  78     return V->getAsArray();
  79   return nullptr;
  80 }
  81 bool operator==(const Object &LHS, const Object &RHS) {
  82   if (LHS.size() != RHS.size())
  83     return false;
  84   for (const auto &L : LHS) {
  85     auto R = RHS.find(L.first);
  86     if (R == RHS.end() || L.second != R->second)
  87       return false;
  88   }
  89   return true;
  90 }
  91
  92 Array::Array(std::initializer_list<Value> Elements) {
  93   V.reserve(Elements.size());
  94   for (const Value &V : Elements) {
  95     emplace_back(nullptr);
  96     back().moveFrom(std::move(V));
  97   }
  98 }
  99
 100 Value::Value(std::initializer_list<Value> Elements)
 101     : Value(json::Array(Elements)) {}
 102
 103 void Value::copyFrom(const Value &M) {
 104   Type = M.Type;
 105   switch (Type) {
 106   case T_Null:
 107   case T_Boolean:
 108   case T_Double:
 109   case T_Integer:
 110     memcpy(Union.buffer, M.Union.buffer, sizeof(Union.buffer));
 111     break;
 112   case T_StringRef:
 113     create<StringRef>(M.as<StringRef>());
 114     break;
 115   case T_String:
 116     create<std::string>(M.as<std::string>());
 117     break;
 118   case T_Object:
 119     create<json::Object>(M.as<json::Object>());
 120     break;
 121   case T_Array:
 122     create<json::Array>(M.as<json::Array>());
 123     break;
 124   }
 125 }
 126
 127 void Value::moveFrom(const Value &&M) {
 128   Type = M.Type;
 129   switch (Type) {
 130   case T_Null:
 131   case T_Boolean:
 132   case T_Double:
 133   case T_Integer:
 134     memcpy(Union.buffer, M.Union.buffer, sizeof(Union.buffer));
 135     break;
 136   case T_StringRef:
 137     create<StringRef>(M.as<StringRef>());
 138     break;
 139   case T_String:
 140     create<std::string>(std::move(M.as<std::string>()));
 141     M.Type = T_Null;
 142     break;
 143   case T_Object:
 144     create<json::Object>(std::move(M.as<json::Object>()));
 145     M.Type = T_Null;
 146     break;
 147   case T_Array:
 148     create<json::Array>(std::move(M.as<json::Array>()));
 149     M.Type = T_Null;
 150     break;
 151   }
 152 }
 153
 154 void Value::destroy() {
 155   switch (Type) {
 156   case T_Null:
 157   case T_Boolean:
 158   case T_Double:
 159   case T_Integer:
 160     break;
 161   case T_StringRef:
 162     as<StringRef>().~StringRef();
 163     break;
 164   case T_String:
 165     as<std::string>().~basic_string();
 166     break;
 167   case T_Object:
 168     as<json::Object>().~Object();
 169     break;
 170   case T_Array:
 171     as<json::Array>().~Array();
 172     break;
 173   }
 174 }
 175
 176 bool operator==(const Value &L, const Value &R) {
 177   if (L.kind() != R.kind())
 178     return false;
 179   switch (L.kind()) {
 180   case Value::Null:
 181     return *L.getAsNull() == *R.getAsNull();
 182   case Value::Boolean:
 183     return *L.getAsBoolean() == *R.getAsBoolean();
 184   case Value::Number:
 185     // Workaround for https://gcc.gnu.org/bugzilla/show_bug.cgi?id=323
 186     // The same integer must convert to the same double, per the standard.
 187     // However we see 64-vs-80-bit precision comparisons with gcc-7 -O3 -m32.
 188     // So we avoid floating point promotion for exact comparisons.
 189     if (L.Type == Value::T_Integer || R.Type == Value::T_Integer)
 190       return L.getAsInteger() == R.getAsInteger();
 191     return *L.getAsNumber() == *R.getAsNumber();
 192   case Value::String:
 193     return *L.getAsString() == *R.getAsString();
 194   case Value::Array:
 195     return *L.getAsArray() == *R.getAsArray();
 196   case Value::Object:
 197     return *L.getAsObject() == *R.getAsObject();
 198   }
 199   llvm_unreachable("Unknown value kind");
 200 }
 201
 202 namespace {
 203 // Simple recursive-descent JSON parser.
 204 class Parser {
 205 public:
 206   Parser(StringRef JSON)
 207       : Start(JSON.begin()), P(JSON.begin()), End(JSON.end()) {}
 208
 209   bool checkUTF8() {
 210     size_t ErrOffset;
 211     if (isUTF8(StringRef(Start, End - Start), &ErrOffset))
 212       return true;
 213     P = Start + ErrOffset; // For line/column calculation.
 214     return parseError("Invalid UTF-8 sequence");
 215   }
 216
 217   bool parseValue(Value &Out);
 218
 219   bool assertEnd() {
 220     eatWhitespace();
 221     if (P == End)
 222       return true;
 223     return parseError("Text after end of document");
 224   }
 225
 226   Error takeError() {
 227     assert(Err);
 228     return std::move(*Err);
 229   }
 230
 231 private:
 232   void eatWhitespace() {
 233     while (P != End && (*P == ' ' || *P == '\r' || *P == '\n' || *P == '\t'))
 234       ++P;
 235   }
 236
 237   // On invalid syntax, parseX() functions return false and set Err.
 238   bool parseNumber(char First, Value &Out);
 239   bool parseString(std::string &Out);
 240   bool parseUnicode(std::string &Out);
 241   bool parseError(const char *Msg); // always returns false
 242
 243   char next() { return P == End ? 0 : *P++; }
 244   char peek() { return P == End ? 0 : *P; }
 245   static bool isNumber(char C) {
 246     return C == '0' || C == '1' || C == '2' || C == '3' || C == '4' ||
 247            C == '5' || C == '6' || C == '7' || C == '8' || C == '9' ||
 248            C == 'e' || C == 'E' || C == '+' || C == '-' || C == '.';
 249   }
 250
 251   Optional<Error> Err;
 252   const char *Start, *P, *End;
 253 };
 254
 255 bool Parser::parseValue(Value &Out) {
 256   eatWhitespace();
 257   if (P == End)
 258     return parseError("Unexpected EOF");
 259   switch (char C = next()) {
 260   // Bare null/true/false are easy - first char identifies them.
 261   case 'n':
 262     Out = nullptr;
 263     return (next() == 'u' && next() == 'l' && next() == 'l') ||
 264            parseError("Invalid JSON value (null?)");
 265   case 't':
 266     Out = true;
 267     return (next() == 'r' && next() == 'u' && next() == 'e') ||
 268            parseError("Invalid JSON value (true?)");
 269   case 'f':
 270     Out = false;
 271     return (next() == 'a' && next() == 'l' && next() == 's' && next() == 'e') ||
 272            parseError("Invalid JSON value (false?)");
 273   case '"': {
 274     std::string S;
 275     if (parseString(S)) {
 276       Out = std::move(S);
 277       return true;
 278     }
 279     return false;
 280   }
 281   case '[': {
 282     Out = Array{};
 283     Array &A = *Out.getAsArray();
 284     eatWhitespace();
 285     if (peek() == ']') {
 286       ++P;
 287       return true;
 288     }
 289     for (;;) {
 290       A.emplace_back(nullptr);
 291       if (!parseValue(A.back()))
 292         return false;
 293       eatWhitespace();
 294       switch (next()) {
 295       case ',':
 296         eatWhitespace();
 297         continue;
 298       case ']':
 299         return true;
 300       default:
 301         return parseError("Expected , or ] after array element");
 302       }
 303     }
 304   }
 305   case '{': {
 306     Out = Object{};
 307     Object &O = *Out.getAsObject();
 308     eatWhitespace();
 309     if (peek() == '}') {
 310       ++P;
 311       return true;
 312     }
 313     for (;;) {
 314       if (next() != '"')
 315         return parseError("Expected object key");
 316       std::string K;
 317       if (!parseString(K))
 318         return false;
 319       eatWhitespace();
 320       if (next() != ':')
 321         return parseError("Expected : after object key");
 322       eatWhitespace();
 323       if (!parseValue(O[std::move(K)]))
 324         return false;
 325       eatWhitespace();
 326       switch (next()) {
 327       case ',':
 328         eatWhitespace();
 329         continue;
 330       case '}':
 331         return true;
 332       default:
 333         return parseError("Expected , or } after object property");
 334       }
 335     }
 336   }
 337   default:
 338     if (isNumber(C))
 339       return parseNumber(C, Out);
 340     return parseError("Invalid JSON value");
 341   }
 342 }
 343
 344 bool Parser::parseNumber(char First, Value &Out) {
 345   // Read the number into a string. (Must be null-terminated for strto*).
 346   SmallString<24> S;
 347   S.push_back(First);
 348   while (isNumber(peek()))
 349     S.push_back(next());
 350   char *End;
 351   // Try first to parse as integer, and if so preserve full 64 bits.
 352   // strtoll returns long long >= 64 bits, so check it's in range too.
 353   auto I = std::strtoll(S.c_str(), &End, 10);
 354   if (End == S.end() && I >= std::numeric_limits<int64_t>::min() &&
 355       I <= std::numeric_limits<int64_t>::max()) {
 356     Out = int64_t(I);
 357     return true;
 358   }
 359   // If it's not an integer
 360   Out = std::strtod(S.c_str(), &End);
 361   return End == S.end() || parseError("Invalid JSON value (number?)");
 362 }
 363
 364 bool Parser::parseString(std::string &Out) {
 365   // leading quote was already consumed.
 366   for (char C = next(); C != '"'; C = next()) {
 367     if (LLVM_UNLIKELY(P == End))
 368       return parseError("Unterminated string");
 369     if (LLVM_UNLIKELY((C & 0x1f) == C))
 370       return parseError("Control character in string");
 371     if (LLVM_LIKELY(C != '\\')) {
 372       Out.push_back(C);
 373       continue;
 374     }
 375     // Handle escape sequence.
 376     switch (C = next()) {
 377     case '"':
 378     case '\\':
 379     case '/':
 380       Out.push_back(C);
 381       break;
 382     case 'b':
 383       Out.push_back('\b');
 384       break;
 385     case 'f':
 386       Out.push_back('\f');
 387       break;
 388     case 'n':
 389       Out.push_back('\n');
 390       break;
 391     case 'r':
 392       Out.push_back('\r');
 393       break;
 394     case 't':
 395       Out.push_back('\t');
 396       break;
 397     case 'u':
 398       if (!parseUnicode(Out))
 399         return false;
 400       break;
 401     default:
 402       return parseError("Invalid escape sequence");
 403     }
 404   }
 405   return true;
 406 }
 407
 408 static void encodeUtf8(uint32_t Rune, std::string &Out) {
 409   if (Rune < 0x80) {
 410     Out.push_back(Rune & 0x7F);
 411   } else if (Rune < 0x800) {
 412     uint8_t FirstByte = 0xC0 | ((Rune & 0x7C0) >> 6);
 413     uint8_t SecondByte = 0x80 | (Rune & 0x3F);
 414     Out.push_back(FirstByte);
 415     Out.push_back(SecondByte);
 416   } else if (Rune < 0x10000) {
 417     uint8_t FirstByte = 0xE0 | ((Rune & 0xF000) >> 12);
 418     uint8_t SecondByte = 0x80 | ((Rune & 0xFC0) >> 6);
 419     uint8_t ThirdByte = 0x80 | (Rune & 0x3F);
 420     Out.push_back(FirstByte);
 421     Out.push_back(SecondByte);
 422     Out.push_back(ThirdByte);
 423   } else if (Rune < 0x110000) {
 424     uint8_t FirstByte = 0xF0 | ((Rune & 0x1F0000) >> 18);
 425     uint8_t SecondByte = 0x80 | ((Rune & 0x3F000) >> 12);
 426     uint8_t ThirdByte = 0x80 | ((Rune & 0xFC0) >> 6);
 427     uint8_t FourthByte = 0x80 | (Rune & 0x3F);
 428     Out.push_back(FirstByte);
 429     Out.push_back(SecondByte);
 430     Out.push_back(ThirdByte);
 431     Out.push_back(FourthByte);
 432   } else {
 433     llvm_unreachable("Invalid codepoint");
 434   }
 435 }
 436
 437 // Parse a UTF-16 \uNNNN escape sequence. "\u" has already been consumed.
 438 // May parse several sequential escapes to ensure proper surrogate handling.
 439 // We do not use ConvertUTF.h, it can't accept and replace unpaired surrogates.
 440 // These are invalid Unicode but valid JSON (RFC 8259, section 8.2).
 441 bool Parser::parseUnicode(std::string &Out) {
 442   // Invalid UTF is not a JSON error (RFC 8529§8.2). It gets replaced by U+FFFD.
 443   auto Invalid = [&] { Out.append(/* UTF-8 */ {'\xef', '\xbf', '\xbd'}); };
 444   // Decodes 4 hex digits from the stream into Out, returns false on error.
 445   auto Parse4Hex = [this](uint16_t &Out) -> bool {
 446     Out = 0;
 447     char Bytes[] = {next(), next(), next(), next()};
 448     for (unsigned char C : Bytes) {
 449       if (!std::isxdigit(C))
 450         return parseError("Invalid \\u escape sequence");
 451       Out <<= 4;
 452       Out |= (C > '9') ? (C & ~0x20) - 'A' + 10 : (C - '0');
 453     }
 454     return true;
 455   };
 456   uint16_t First; // UTF-16 code unit from the first \u escape.
 457   if (!Parse4Hex(First))
 458     return false;
 459
 460   // We loop to allow proper surrogate-pair error handling.
 461   while (true) {
 462     // Case 1: the UTF-16 code unit is already a codepoint in the BMP.
 463     if (LLVM_LIKELY(First < 0xD800 || First >= 0xE000)) {
 464       encodeUtf8(First, Out);
 465       return true;
 466     }
 467
 468     // Case 2: it's an (unpaired) trailing surrogate.
 469     if (LLVM_UNLIKELY(First >= 0xDC00)) {
 470       Invalid();
 471       return true;
 472     }
 473
 474     // Case 3: it's a leading surrogate. We expect a trailing one next.
 475     // Case 3a: there's no trailing \u escape. Don't advance in the stream.
 476     if (LLVM_UNLIKELY(P + 2 > End || *P != '\\' || *(P + 1) != 'u')) {
 477       Invalid(); // Leading surrogate was unpaired.
 478       return true;
 479     }
 480     P += 2;
 481     uint16_t Second;
 482     if (!Parse4Hex(Second))
 483       return false;
 484     // Case 3b: there was another \u escape, but it wasn't a trailing surrogate.
 485     if (LLVM_UNLIKELY(Second < 0xDC00 || Second >= 0xE000)) {
 486       Invalid();      // Leading surrogate was unpaired.
 487       First = Second; // Second escape still needs to be processed.
 488       continue;
 489     }
 490     // Case 3c: a valid surrogate pair encoding an astral codepoint.
 491     encodeUtf8(0x10000 | ((First - 0xD800) << 10) | (Second - 0xDC00), Out);
 492     return true;
 493   }
 494 }
 495
 496 bool Parser::parseError(const char *Msg) {
 497   int Line = 1;
 498   const char *StartOfLine = Start;
 499   for (const char *X = Start; X < P; ++X) {
 500     if (*X == 0x0A) {
 501       ++Line;
 502       StartOfLine = X + 1;
 503     }
 504   }
 505   Err.emplace(
 506       llvm::make_unique<ParseError>(Msg, Line, P - StartOfLine, P - Start));
 507   return false;
 508 }
 509 } // namespace
 510
 511 Expected<Value> parse(StringRef JSON) {
 512   Parser P(JSON);
 513   Value E = nullptr;
 514   if (P.checkUTF8())
 515     if (P.parseValue(E))
 516       if (P.assertEnd())
 517         return std::move(E);
 518   return P.takeError();
 519 }
 520 char ParseError::ID = 0;
 521
 522 static std::vector<const Object::value_type *> sortedElements(const Object &O) {
 523   std::vector<const Object::value_type *> Elements;
 524   for (const auto &E : O)
 525     Elements.push_back(&E);
 526   llvm::sort(Elements,
 527              [](const Object::value_type *L, const Object::value_type *R) {
 528                return L->first < R->first;
 529              });
 530   return Elements;
 531 }
 532
 533 bool isUTF8(llvm::StringRef S, size_t *ErrOffset) {
 534   // Fast-path for ASCII, which is valid UTF-8.
 535   if (LLVM_LIKELY(isASCII(S)))
 536     return true;
 537
 538   const UTF8 *Data = reinterpret_cast<const UTF8 *>(S.data()), *Rest = Data;
 539   if (LLVM_LIKELY(isLegalUTF8String(&Rest, Data + S.size())))
 540     return true;
 541
 542   if (ErrOffset)
 543     *ErrOffset = Rest - Data;
 544   return false;
 545 }
 546
 547 std::string fixUTF8(llvm::StringRef S) {
 548   // This isn't particularly efficient, but is only for error-recovery.
 549   std::vector<UTF32> Codepoints(S.size()); // 1 codepoint per byte suffices.
 550   const UTF8 *In8 = reinterpret_cast<const UTF8 *>(S.data());
 551   UTF32 *Out32 = Codepoints.data();
 552   ConvertUTF8toUTF32(&In8, In8 + S.size(), &Out32, Out32 + Codepoints.size(),
 553                      lenientConversion);
 554   Codepoints.resize(Out32 - Codepoints.data());
 555   std::string Res(4 * Codepoints.size(), 0); // 4 bytes per codepoint suffice
 556   const UTF32 *In32 = Codepoints.data();
 557   UTF8 *Out8 = reinterpret_cast<UTF8 *>(&Res[0]);
 558   ConvertUTF32toUTF8(&In32, In32 + Codepoints.size(), &Out8, Out8 + Res.size(),
 559                      strictConversion);
 560   Res.resize(reinterpret_cast<char *>(Out8) - Res.data());
 561   return Res;
 562 }
 563
 564 } // namespace json
 565 } // namespace llvm
 566
 567 static void quote(llvm::raw_ostream &OS, llvm::StringRef S) {
 568   OS << '\"';
 569   for (unsigned char C : S) {
 570     if (C == 0x22 || C == 0x5C)
 571       OS << '\\';
 572     if (C >= 0x20) {
 573       OS << C;
 574       continue;
 575     }
 576     OS << '\\';
 577     switch (C) {
 578     // A few characters are common enough to make short escapes worthwhile.
 579     case '\t':
 580       OS << 't';
 581       break;
 582     case '\n':
 583       OS << 'n';
 584       break;
 585     case '\r':
 586       OS << 'r';
 587       break;
 588     default:
 589       OS << 'u';
 590       llvm::write_hex(OS, C, llvm::HexPrintStyle::Lower, 4);
 591       break;
 592     }
 593   }
 594   OS << '\"';
 595 }
 596
 597 enum IndenterAction {
 598   Indent,
 599   Outdent,
 600   Newline,
 601   Space,
 602 };
 603
 604 // Prints JSON. The indenter can be used to control formatting.
 605 template <typename Indenter>
 606 void llvm::json::Value::print(raw_ostream &OS, const Indenter &I) const {
 607   switch (Type) {
 608   case T_Null:
 609     OS << "null";
 610     break;
 611   case T_Boolean:
 612     OS << (as<bool>() ? "true" : "false");
 613     break;
 614   case T_Double:
 615     OS << format("%.*g", std::numeric_limits<double>::max_digits10,
 616                  as<double>());
 617     break;
 618   case T_Integer:
 619     OS << as<int64_t>();
 620     break;
 621   case T_StringRef:
 622     quote(OS, as<StringRef>());
 623     break;
 624   case T_String:
 625     quote(OS, as<std::string>());
 626     break;
 627   case T_Object: {
 628     bool Comma = false;
 629     OS << '{';
 630     I(Indent);
 631     for (const auto *P : sortedElements(as<json::Object>())) {
 632       if (Comma)
 633         OS << ',';
 634       Comma = true;
 635       I(Newline);
 636       quote(OS, P->first);
 637       OS << ':';
 638       I(Space);
 639       P->second.print(OS, I);
 640     }
 641     I(Outdent);
 642     if (Comma)
 643       I(Newline);
 644     OS << '}';
 645     break;
 646   }
 647   case T_Array: {
 648     bool Comma = false;
 649     OS << '[';
 650     I(Indent);
 651     for (const auto &E : as<json::Array>()) {
 652       if (Comma)
 653         OS << ',';
 654       Comma = true;
 655       I(Newline);
 656       E.print(OS, I);
 657     }
 658     I(Outdent);
 659     if (Comma)
 660       I(Newline);
 661     OS << ']';
 662     break;
 663   }
 664   }
 665 }
 666
 667 void llvm::format_provider<llvm::json::Value>::format(
 668     const llvm::json::Value &E, raw_ostream &OS, StringRef Options) {
 669   if (Options.empty()) {
 670     OS << E;
 671     return;
 672   }
 673   unsigned IndentAmount = 0;
 674   if (Options.getAsInteger(/*Radix=*/10, IndentAmount))
 675     llvm_unreachable("json::Value format options should be an integer");
 676   unsigned IndentLevel = 0;
 677   E.print(OS, [&](IndenterAction A) {
 678     switch (A) {
 679     case Newline:
 680       OS << '\n';
 681       OS.indent(IndentLevel);
 682       break;
 683     case Space:
 684       OS << ' ';
 685       break;
 686     case Indent:
 687       IndentLevel += IndentAmount;
 688       break;
 689     case Outdent:
 690       IndentLevel -= IndentAmount;
 691       break;
 692     };
 693   });
 694 }
 695
 696 llvm::raw_ostream &llvm::json::operator<<(raw_ostream &OS, const Value &E) {
 697   E.print(OS, [](IndenterAction A) { /*ignore*/ });
 698   return OS;
 699 }