[Support] Harden JSON against invalid UTF-8.

[sammccall]

Summary

Parsing invalid UTF-8 input is now a parse error.
Creating JSON values from invalid UTF-8 now triggers an assertion, and
(in no-assert builds) substitutes the unicode replacement character.
Strings retrieved from json::Value are always valid UTF-8.

[ruiu]

I wonder if you also want to replace surrogate codepoint with U+FFFD, as UTF-8 string should not contain any codepoint between U+D800 and U+DFFF.

[benhamilton]

Looks good, just missed a few edge cases for 4-byte sequences.

Also need to reject the CESU-8 encoding where UTF-16 surrogate pairs are represented as two 3-byte UTF-8 sequences.

lib/Support/JSON.cpp

535

Can we clarify the comment that this logic results in checking for the shortest possible encoding?

539

Also need to check for and reject so-called CESU-8 encoding (where UTF-16 surrogate pairs are "encoded" as separate 3-byte UTF-8 sequences):

https://www.unicode.org/reports/tr26/#definitions

550

Also need to handle two more cases which would encode a code point > U+10FFFF, which is not allowed:

1. First byte == 0xF4 and second byte > 0x8F
2. First byte > 0xF4

570

if (!LLVM_LIKELY(measureChar(S, I)) {

[benhamilton]

Also, IMHO, this logic should be in a separate UTF-8 library so we can use it outside of JSON contexts.

[sammccall]

Thanks for the comments!
Not validating codepoints was deliberate but in hindsight arbitrary, I'll
fix that. (Both surrogates and high codepoints).

Regarding a separate library: I agree in principle :-) but am concerned
about the potential scope/generality and don't have cycles to design it
right now, even extracting JSON is a bit of a yak-shave...
Here it's in support and exposed as free functions, so if it really is
useful, it *is* available and we can move it later.
That's the best argument I can come up with, open to better ideas :)

[benhamilton]

Is it super tricky to at least extract the UTF-8 validating and sanitizing functions into their own header and source files within the Support library, if not a separate library?

[sammccall]

Reject invalid codepoints (surrogates, high codepoints).
Add more comments around UTF8 validation.

[sammccall]

Use existing library code from ConvertUTF for UTF-8 validation.

[sammccall]

In D46274#1083161, @benhamilton wrote:

Is it super tricky to at least extract the UTF-8 validating and sanitizing functions into their own header and source files within the Support library, if not a separate library?

It turns out ConvertUTF already provides a nice/efficient isLegalUTF8String that I somehow missed before.
Given that, rewriting fixUTF8 to use existing facilities is a little clunky but doable, and that shouldn't be hot.

So this is now a lot simpler, sorry for any wasted time :-/
Now I think the "unicode library" point is moot?

[benhamilton]

Ah, glad we did have a solution for this. Wish I'd known, would have saved everyone time. :)

lib/Support/JSON.cpp

517

Wouldn't it make sense to move this to isLegalUTF8String()?

524

Style: Space between UTF8 and *?

534

Style: Space between UTF8 and *?

[sammccall]

Oops, sorry for losing track of this.
The JSON-in-Support patch has finally landed in r336534 so this can actually go in sometime soon :-)

lib/Support/JSON.cpp

517

Hmm.. maybe. I'm slightly leery about this, as these are common Unicode reference functions that are largely unmodified, which people may expect.
Also I think we'd still want to split it into two functions so the ASCII check can be inlined and the utf-8 wrangling outlined. It seems harmless enough here, but maybe I'm just lazy. WDYT?

[sammccall]

Rebase and format

[benhamilton]

lib/Support/JSON.cpp

517

I'm supportive of an inline-able ASCII check if we don't already have one.

[sammccall]

Properly rebase this time, and add/use isASCII in StringExtras.

[sammccall]

lib/Support/JSON.cpp

517

Added one to StringExtras.h (Unicode.h and ConvertUTF.h have weird style and no dependencies, it's hard to work out how to make it fit).

[benhamilton]

Thanks!

include/llvm/Support/JSON.h

302

Seems like flipping the check is clearer:

if (LLVM_UNLIKELY(!isUTF8(V)) {

314

Ditto on LLVM_UNLIKELY.

491

Ditto ditto.

498

Ditto ditto ditto.

[dexonsmith]

include/llvm/Support/JSON.h

302

Moreover, __builtin_expect doesn't work if it's not the top-level condition, and LLVM_LIKELY and LLVM_UNLIKELY are both using it.

[sammccall]

include/llvm/Support/JSON.h

302

Interesting! Naive test suggests this isn't always true for clang, though probably is for GCC:
https://godbolt.org/g/vek4jo

Done in any case.

[sammccall]

Make LLVM_[UN]LIKELY top-level

[sammccall]

Landed as r336657, not sure why it didn't get linked to this review.

include/llvm/ADT/StringExtras.h

 inline bool isAlpha(char C) {
   return ('a' <= C && C <= 'z') || ('A' <= C && C <= 'Z');
 }
 
 /// Checks whether character \p C is either a decimal digit or an uppercase or
 /// lowercase letter as classified by "C" locale.
 inline bool isAlnum(char C) { return isAlpha(C) || isDigit(C); }
 
+/// Checks whether character \p C is valid ASCII (high bit is zero).
+inline bool isASCII(char C) { return static_cast<unsigned char>(C) <= 127; }
+
+/// Checks whether all characters in S are ASCII.
+inline bool isASCII(llvm::StringRef S) {
+  for (char C : S)
+    if (LLVM_UNLIKELY(!isASCII(C)))
+      return false;
+  return true;
+}
+
 /// Returns the corresponding lowercase character if \p x is uppercase.
 inline char toLower(char x) {
   if (x >= 'A' && x <= 'Z')
     return x - 'A' + 'a';
   return x;
 }
 
 /// Returns the corresponding uppercase character if \p x is lowercase.

include/llvm/Support/JSON.h

 #include "llvm/ADT/StringRef.h"
 #include "llvm/Support/Error.h"
 #include "llvm/Support/FormatVariadic.h"
 #include "llvm/Support/raw_ostream.h"
 #include <map>
 
 namespace llvm {
 namespace json {
+
+// === String encodings ===
+//
+// JSON strings are character sequences (not byte sequences like std::string).
+// We need to know the encoding, and for simplicity only support UTF-8.
+//
+//   - When parsing, invalid UTF-8 is a syntax error like any other
+//
+//   - When creating Values from strings, callers must ensure they are UTF-8.
+//        with asserts on, invalid UTF-8 will crash the program
+//        with asserts off, we'll substitute the replacement character (U+FFFD)
+//     Callers can use json::isUTF8() and json::fixUTF8() for validation.
+//
+//   - When retrieving strings from Values (e.g. asString()), the result will
+//     always be valid UTF-8.
+
+/// Returns true if \p S is valid UTF-8, which is required for use as JSON.
+/// If it returns false, \p Offset is set to a byte offset near the first error.
+bool isUTF8(llvm::StringRef S, size_t *ErrOffset = nullptr);
+/// Replaces invalid UTF-8 sequences in \p S with the replacement character
+/// (U+FFFD). The returned string is valid UTF-8.
+/// This is much slower than isUTF8, so test that first.
+std::string fixUTF8(llvm::StringRef S);
+
 class Array;
 class ObjectKey;
 class Value;
 template <typename T> Value toJSON(const llvm::Optional<T> &Opt);
 
 /// An Object is a JSON object, which maps strings to heterogenous JSON values.
 /// It simulates DenseMap<ObjectKey, Value>. ObjectKey is a maybe-owned string.
 class Object {
public:
   Value(Value &&M) { moveFrom(std::move(M)); }
   Value(std::initializer_list<Value> Elements);
   Value(json::Array &&Elements) : Type(T_Array) {
     create<json::Array>(std::move(Elements));
   }
   Value(json::Object &&Properties) : Type(T_Object) {
     create<json::Object>(std::move(Properties));
   }
-  // Strings: types with value semantics.
-  Value(std::string &&V) : Type(T_String) { create<std::string>(std::move(V)); }
-  Value(const std::string &V) : Type(T_String) { create<std::string>(V); }
-  Value(const llvm::SmallVectorImpl<char> &V) : Type(T_String) {
-    create<std::string>(V.begin(), V.end());
+  // Strings: types with value semantics. Must be valid UTF-8.
+  Value(std::string V) : Type(T_String) {
+    if (LLVM_UNLIKELY(!isUTF8(V))) {
+      assert(false && "Invalid UTF-8 in value used as JSON");
+      V = fixUTF8(std::move(V));
+    }
+    create<std::string>(std::move(V));
   }
+  Value(const llvm::SmallVectorImpl<char> &V)
+      : Value(std::string(V.begin(), V.end())){};
   Value(const llvm::formatv_object_base &V) : Value(V.str()){};
-  // Strings: types with reference semantics.
-  Value(llvm::StringRef V) : Type(T_StringRef) { create<llvm::StringRef>(V); }
-  Value(const char *V) : Type(T_StringRef) { create<llvm::StringRef>(V); }
+  // Strings: types with reference semantics. Must be valid UTF-8.
+  Value(StringRef V) : Type(T_StringRef) {
+    create<llvm::StringRef>(V);
+    if (LLVM_UNLIKELY(!isUTF8(V))) {
+      assert(false && "Invalid UTF-8 in value used as JSON");
+      *this = Value(fixUTF8(V));
+    }
+  }
+  Value(const char *V) : Value(StringRef(V)) {}
   Value(std::nullptr_t) : Type(T_Null) {}
   // Boolean (disallow implicit conversions).
   // (The last template parameter is a dummy to keep templates distinct.)
   template <
       typename T,
       typename = typename std::enable_if<std::is_same<T, bool>::value>::type,
       bool = false>
   Value(T B) : Type(T_Boolean) {

 
 bool operator==(const Value &, const Value &);
 inline bool operator!=(const Value &L, const Value &R) { return !(L == R); }
 llvm::raw_ostream &operator<<(llvm::raw_ostream &, const Value &);
 
 /// ObjectKey is a used to capture keys in Object. Like Value but:
 ///   - only strings are allowed
 ///   - it's optimized for the string literal case (Owned == nullptr)
+/// Like Value, strings must be UTF-8. See isUTF8 documentation for details.
 class ObjectKey {
 public:
-  ObjectKey(const char *S) : Data(S) {}
-  ObjectKey(llvm::StringRef S) : Data(S) {}
-  ObjectKey(std::string &&V)
-      : Owned(new std::string(std::move(V))), Data(*Owned) {}
-  ObjectKey(const std::string &V) : Owned(new std::string(V)), Data(*Owned) {}
+  ObjectKey(const char *S) : ObjectKey(StringRef(S)) {}
+  ObjectKey(std::string S) : Owned(new std::string(std::move(S))) {
+    if (LLVM_UNLIKELY(!isUTF8(*Owned))) {
+      assert(false && "Invalid UTF-8 in value used as JSON");
+      *Owned = fixUTF8(std::move(*Owned));
+    }
+    Data = *Owned;
+  }
+  ObjectKey(llvm::StringRef S) : Data(S) {
+    if (LLVM_UNLIKELY(!isUTF8(Data))) {
+      assert(false && "Invalid UTF-8 in value used as JSON");
+      *this = ObjectKey(fixUTF8(S));
+    }
+  }
   ObjectKey(const llvm::SmallVectorImpl<char> &V)
       : ObjectKey(std::string(V.begin(), V.end())) {}
   ObjectKey(const llvm::formatv_object_base &V) : ObjectKey(V.str()) {}
 
   ObjectKey(const ObjectKey &C) { *this = C; }
   ObjectKey(ObjectKey &&C) : ObjectKey(static_cast<const ObjectKey &&>(C)) {}
   ObjectKey &operator=(const ObjectKey &C) {
     if (C.Owned) {

lib/Support/JSON.cpp

 //=== JSON.cpp - JSON value, parsing and serialization - C++ -----------*-===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===---------------------------------------------------------------------===//
 
 #include "llvm/Support/JSON.h"
+#include "llvm/Support/ConvertUTF.h"
 #include "llvm/Support/Format.h"
 #include <cctype>
 
 namespace llvm {
 namespace json {
 
 Value &Object::operator[](const ObjectKey &K) {
   return try_emplace(K, nullptr).first->getSecond();

 
 namespace {
 // Simple recursive-descent JSON parser.
 class Parser {
 public:
   Parser(StringRef JSON)
       : Start(JSON.begin()), P(JSON.begin()), End(JSON.end()) {}
 
+  bool checkUTF8() {
+    size_t ErrOffset;
+    if (isUTF8(StringRef(Start, End - Start), &ErrOffset))
+      return true;
+    P = Start + ErrOffset; // For line/column calculation.
+    return parseError("Invalid UTF-8 sequence");
+  }
+
   bool parseValue(Value &Out);
 
   bool assertEnd() {
     eatWhitespace();
     if (P == End)
       return true;
     return parseError("Text after end of document");
   }
while (true) {
     // Case 2: it's an (unpaired) trailing surrogate.
     if (LLVM_UNLIKELY(First >= 0xDC00)) {
       Invalid();
       return true;
     }
 
     // Case 3: it's a leading surrogate. We expect a trailing one next.
     // Case 3a: there's no trailing \u escape. Don't advance in the stream.
-    if (!LLVM_LIKELY(P + 2 <= End && *P == '\\' && *(P + 1) == 'u')) {
+    if (LLVM_UNLIKELY(P + 2 > End || *P != '\\' || *(P + 1) != 'u')) {
       Invalid(); // Leading surrogate was unpaired.
       return true;
     }
     P += 2;
     uint16_t Second;
     if (!Parse4Hex(Second))
       return false;
     // Case 3b: there was another \u escape, but it wasn't a trailing surrogate.
Err.emplace(
       llvm::make_unique<ParseError>(Msg, Line, P - StartOfLine, P - Start));
   return false;
 }
 } // namespace
 
 Expected<Value> parse(StringRef JSON) {
   Parser P(JSON);
   Value E = nullptr;
+  if (P.checkUTF8())
     if (P.parseValue(E))
       if (P.assertEnd())
         return std::move(E);
   return P.takeError();
 }
 char ParseError::ID = 0;
 
 static std::vector<const Object::value_type *> sortedElements(const Object &O) {
   std::vector<const Object::value_type *> Elements;
   for (const auto &E : O)
     Elements.push_back(&E);
   llvm::sort(Elements.begin(), Elements.end(),
              [](const Object::value_type *L, const Object::value_type *R) {
                return L->first < R->first;
              });
   return Elements;
 }
 
+bool isUTF8(llvm::StringRef S, size_t *ErrOffset) {
+  // Fast-path for ASCII, which is valid UTF-8.
+  if (LLVM_LIKELY(isASCII(S)))
+    return true;
+
+  const UTF8 *Data = reinterpret_cast<const UTF8 *>(S.data()), *Rest = Data;
+  if (LLVM_LIKELY(isLegalUTF8String(&Rest, Data + S.size())))
+    return true;
+
+  if (ErrOffset)
+    *ErrOffset = Rest - Data;
+  return false;
+}
+
+std::string fixUTF8(llvm::StringRef S) {
+  // This isn't particularly efficient, but is only for error-recovery.
+  std::vector<UTF32> Codepoints(S.size()); // 1 codepoint per byte suffices.
+  const UTF8 *In8 = reinterpret_cast<const UTF8 *>(S.data());
+  UTF32 *Out32 = Codepoints.data();
+  ConvertUTF8toUTF32(&In8, In8 + S.size(), &Out32, Out32 + Codepoints.size(),
+                     lenientConversion);
+  Codepoints.resize(Out32 - Codepoints.data());
+  std::string Res(4 * Codepoints.size(), 0); // 4 bytes per codepoint suffice
+  const UTF32 *In32 = Codepoints.data();
+  UTF8 *Out8 = reinterpret_cast<UTF8 *>(&Res[0]);
+  ConvertUTF32toUTF8(&In32, In32 + Codepoints.size(), &Out8, Out8 + Res.size(),
+                     strictConversion);
+  Res.resize(reinterpret_cast<char *>(Out8) - Res.data());
+  return Res;
+}
+
 } // namespace json
 } // namespace llvm
 
 static void quote(llvm::raw_ostream &OS, llvm::StringRef S) {
   OS << '\"';
   for (unsigned char C : S) {
     if (C == 0x22 || C == 0x5C)
       OS << '\\';
     if (C >= 0x20) {
       OS << C;
       continue;
     }
     OS << '\\';
     switch (C) {
     // A few characters are common enough to make short escapes worthwhile.
     case '\t':
       OS << 't';
       break;
     case '\n':
       OS << 'n';
       break;

unittests/Support/JSONTest.cpp

 
 TEST(JSONTest, Types) {
   EXPECT_EQ("true", s(true));
   EXPECT_EQ("null", s(nullptr));
   EXPECT_EQ("2.5", s(2.5));
   EXPECT_EQ(R"("foo")", s("foo"));
   EXPECT_EQ("[1,2,3]", s({1, 2, 3}));
   EXPECT_EQ(R"({"x":10,"y":20})", s(Object{{"x", 10}, {"y", 20}}));
+
+#ifdef NDEBUG
+  EXPECT_EQ(R"("��")", s("\xC0\x80"));
+  EXPECT_EQ(R"({"��":0})", s(Object{{"\xC0\x80", 0}}));
+#else
+  EXPECT_DEATH(s("\xC0\x80"), "Invalid UTF-8");
+  EXPECT_DEATH(s(Object{{"\xC0\x80", 0}}), "Invalid UTF-8");
+#endif
 }
 
 TEST(JSONTest, Constructors) {
   // Lots of edge cases around empty and singleton init lists.
   EXPECT_EQ("[[[3]]]", s({{{3}}}));
   EXPECT_EQ("[[[]]]", s({{{}}}));
   EXPECT_EQ("[[{}]]", s({{Object{}}}));
   EXPECT_EQ(R"({"A":{"B":{}}})", s(Object{{"A", Object{{"B", Object{}}}}}));
TEST(JSONTest, ParseErrors) {
   ExpectErr("Unterminated string", R"("abc\"def)");
   ExpectErr("Control character in string", "\"abc\ndef\"");
   ExpectErr("Invalid escape sequence", R"("\030")");
   ExpectErr("Invalid \\u escape sequence", R"("\usuck")");
   ExpectErr("[3:3, byte=19]", R"({
   "valid": 1,
   invalid: 2
 })");
+  ExpectErr("Invalid UTF-8 sequence", "\"\xC0\x80\""); // WTF-8 null
+}
+
+// Direct tests of isUTF8 and fixUTF8. Internal uses are also tested elsewhere.
+TEST(JSONTest, UTF8) {
+  for (const char *Valid : {
+           "this is ASCII text",
+           "thïs tëxt häs BMP chäräctërs",
+           "𐌶𐌰L𐌾𐍈 C𐍈𐌼𐌴𐍃",
+       }) {
+    EXPECT_TRUE(isUTF8(Valid)) << Valid;
+    EXPECT_EQ(fixUTF8(Valid), Valid);
+  }
+  for (auto Invalid : std::vector<std::pair<const char *, const char *>>{
+           {"lone trailing \x81\x82 bytes", "lone trailing �� bytes"},
+           {"missing trailing \xD0 bytes", "missing trailing � bytes"},
+           {"truncated character \xD0", "truncated character �"},
+           {"not \xC1\x80 the \xE0\x9f\xBF shortest \xF0\x83\x83\x83 encoding",
+            "not �� the ��� shortest ���� encoding"},
+           {"too \xF9\x80\x80\x80\x80 long", "too ����� long"},
+           {"surrogate \xED\xA0\x80 invalid \xF4\x90\x80\x80",
+            "surrogate ��� invalid ����"}}) {
+    EXPECT_FALSE(isUTF8(Invalid.first)) << Invalid.first;
+    EXPECT_EQ(fixUTF8(Invalid.first), Invalid.second);
+  }
 }
 
 TEST(JSONTest, Inspection) {
   llvm::Expected<Value> Doc = parse(R"(
     {
       "null": null,
       "boolean": false,
       "number": 2.78,