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