[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

537

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

541

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

552

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

572

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

519

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

526

Style: Space between UTF8 and *?

536

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

519

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

519

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

519

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

231

Seems like flipping the check is clearer:

if (LLVM_UNLIKELY(!isUTF8(V)) {

243

Ditto on LLVM_UNLIKELY.

404

Ditto ditto.

411

Ditto ditto ditto.

[dexonsmith]

include/llvm/Support/JSON.h

231

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

231

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/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.
+/// Doesn't check for invalid codepoints, which don't cause problems for us.
+/// 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.
+std::string fixUTF8(llvm::StringRef S);
+
 class Array;
 class ObjectKey;
 class Value;
 
 /// An Object is a JSON object, which maps strings to heterogenous JSON values.
 /// The string keys may be owned or references.
+/// They must be valid UTF-8, validated by caller! See comment above.
 class Object : public std::map<ObjectKey, Value> {
 public:
   explicit Object() {}
   // We use a custom struct for list-init, because pair forces extra copies.
   struct KV;
   explicit Object(std::initializer_list<KV> Properties);
 
   // Allow [] as if Value was default-constructible as null.

 /// Values can be serialized to JSON:
 ///   1) raw_ostream << Value                    // Basic formatting.
 ///   2) raw_ostream << formatv("{0}", Value)    // Basic formatting.
 ///   3) raw_ostream << formatv("{0:2}", Value)  // Pretty-print with indent 2.
 ///
 /// And parsed:
 ///   Expected<Value> E = json::parse("[1, 2, null]");
 ///   assert(E && E->kind() == Value::Array);
+///
 class Value {
 public:
   enum Kind {
     Null,
     Boolean,
     Number,
     String,
     Array,
     Object,
   };
 
   // It would be nice to have Value() be null. But that would make {} null too.
   Value(const Value &M) { copyFrom(M); }
   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_LIKELY(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_LIKELY(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) {}
   // Prevent implicit conversions to boolean.
   template <typename T, typename = typename std::enable_if<
                             std::is_same<T, bool>::value>::type>
   Value(T B) : Type(T_Boolean) {
     create<bool>(B);
   }
   // Numbers: arithmetic types that are not 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_LIKELY(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_LIKELY(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) {
ParseError(const char *Msg, unsigned Line, unsigned Column, unsigned Offset)
       : Msg(Msg), Line(Line), Column(Column), Offset(Offset) {}
   void log(llvm::raw_ostream &OS) const override {
     OS << llvm::formatv("[{0}:{1}, byte={2}]: {3}", Line, Column, Offset, Msg);
   }
   std::error_code convertToErrorCode() const override {
     return llvm::inconvertibleErrorCode();
   }
 };
+
 } // namespace json
 
 /// Allow printing json::Value with formatv().
 /// The default style is basic/compact formatting, like operator<<.
 /// A format string like formatv("{0:2}", Value) pretty-prints with indent 2.
 template <> struct format_provider<llvm::json::Value> {
   static void format(const llvm::json::Value &, raw_ostream &, StringRef);
 };
 } // namespace llvm
 
 #endif

lib/Support/JSON.cpp

 
 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");
     }
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;
 
+// Advances I past the character starting at S[I].
+// Returns its length, or 0 if invalid.
+LLVM_ATTRIBUTE_ALWAYS_INLINE
+static int measureChar(llvm::StringRef S, size_t &I) {
+  unsigned char C = S[I++];
+  if (LLVM_LIKELY(!(C & 0x80))) // ASCII
+    return 1;
+
+  auto EatTrailing = [&]() -> unsigned char {
+    if (LLVM_LIKELY(I < S.size() && ((unsigned char)S[I] & 0xC0) == 0x80))
+      return S[I++];
+    return 0;
+  };
+  // Multi-byte character length is encoded in the leading ones of C.
+  // We'll return if valid and break if invalid.
+  switch (countLeadingOnes(C)) {
+  case 1: // 10xxx is a continuation byte.
+    break;
+  case 2: // 110xxxxx 10xxxxxx.
+    // U+80 = C2 80 is the first two-byte character.
+    if (C < 0xC2 || !EatTrailing())
+      break;
+    return 2;
+  case 3: // 1110xxxx 10xxxxxx 10xxxxxx.
+    // U+800 = E0 A0 80 is the first three-byte character.
+    if (C == 0xE0) {
+      if (EatTrailing() < 0xA0 || !EatTrailing())
+        break;
+    } else if (!EatTrailing() || !EatTrailing()) {
+      break;
+    }
+    return 3;
+  case 4: // 11110xxx 10xxxxxx 10xxxxxx 10xxxxxx.
+    // U+10000 = F0 90 80 80 is the first three-byte character.
+    if (C == 0xF0) {
+      if (EatTrailing() < 0x90 || !EatTrailing() || !EatTrailing())
+        break;
+    } else if (!EatTrailing() || !EatTrailing() || !EatTrailing()) {
+      break;
+    }
+    return 4;
+  default: // 11111xxx is invalid.
+    break;
+  }
+  // If we fell off the end of the switch, the character is invalid.
+  while (EatTrailing()) // Advance to the next plausible character.
+    ;
+  return 0;
+}
+
+bool isUTF8(llvm::StringRef S, size_t *ErrOffset) {
+  // We could optimize for the all-ASCII case, but this already compiles down
+  // to a tight loop in that case.
+  for (size_t I = 0; I < S.size();)
+    if (!measureChar(S, I)) {
+      if (ErrOffset)
+        *ErrOffset = I - 1; // I points *after* the error, rewind into range.
+      return false;
+    }
+  return true;
+}
+
+std::string fixUTF8(llvm::StringRef S) {
+  std::string Result;
+  for (size_t I = 0; I < S.size();)
+    if (int Len = measureChar(S, I))
+      Result.append(S.data() + I - Len, Len);
+    else {
+      // UTF-8 encoded replacement character (U+FFFD).
+      Result.push_back(0xef);
+      Result.push_back(0xbf);
+      Result.push_back(0xbd);
+    }
+  return Result;
+}
+
 } // 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 << '\\';

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𐍈𐌼𐌴𐍃",
+           "invalid \xED\xA0\x80 codepoints \xF4\x90\x80\x80 not checked",
+       }) {
+    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"},
+       }) {
+    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,