JSON library (just a prototype at this point).

[sammccall]

Summary

Main features:

• DOM, fully parsed/validated ahead of time
• All DOM elements arena-allocated and owned by the document
• tagged-pointer representation of Values, integers/nulls/booleans inline
• expressive syntax for JSON literals with Twine-like semantics

[sammccall]

Clean up types, add more standard APIs to Object/Array, clang-format.

[ilya-biryukov]

I've simply skimmed through the code, but overall design looks great.

It's a bit of a pity that Arrays may allocate outside the arena. What are the reasons we prefer SmallVector to std::vector if we're allocating in the arena anyway?

include/llvm/Support/JSONDetail.h

83

s/ValeWrapper/ValueWrapper

[sammccall]

In D39180#903684, @ilya-biryukov wrote:

It's a bit of a pity that Arrays may allocate outside the arena.

Yeah :-(

It's not trivial to retrofit SmallVector (we'd need to add realloc to Allocator, and SmallVector's complex inheritance hierarchy, templates, and empty base optimization might need some untangling).
I talked to Chandler about this, and he said this is the part where people write their own specialized vector.

BTW, If it wasn't for Array's heap allocations, I think we might be able to make Value's destructor empty and just abandon the objects, which would speed up/simplify a bit. The arenas just have PODs, vectors, and StringMaps...

What are the reasons we prefer SmallVector to std::vector if we're allocating in the arena anyway?

Huh, you're right: a sized std::vector initialized on an arena has the same layout as a perfectly-sized SmallVector.

With our current broken arena-allocation, SmallVector's SSO means we end up on the arena some of the time. (And avoiding the small allocations is the important part, because there won't be many big ones). But if we can adapt BumpPtrAllocator& to be an STL allocator, then std::vector would be the way to go. Time to see if someone already did that...

[klimek]

unittests/Support/JSONTest.cpp

26

Can we use variadic templates for array(1, 2, 3)?

[sammccall]

Switch to std::vector, with BumpPtrAllocator adapted to the STL allocator.
All allocations are now on the arena.

[sammccall]

unittests/Support/JSONTest.cpp

26

That would be nice... I can't make it work properly when the elements are init-lists though.

My understanding is that with variadic templates you have to accept any (heterogeneous) parameters, and then rely on SFINAE to reject the ones you don't want.

This works for "ordinary" values: I can pass a string, with a SFINAE-check that string is convertible to Literal, and then convert it in the body.

But it doesn't work if the parameter is an init-list, like array(1, {"foo", 42}), because it can't deduce a type for that parameter. Unfortunately these are the cases we care most about as they're the ambiguous ones that array() is supposed to solve.

This is what I had half-working:

template <typename R, typename...> struct all { typedef R type; };
template <typename... T>
typename all<Literal,
  typename std::enable_if<
    std::is_convertible<T, const Literal&>::value
  >::type...
>::type
array(T... V) {
  return Literal(std::initializer_list<Literal>{V...}, 1);
}

[sammccall]

Fix SmallInt testing, and allow it to build on 32-bit platforms.

[sammccall]

Add kind() API, ordering, hashing.

[sammccall]

Value semantics for literals
Bugfix in parser

[sammccall]

Add a few simple tests, fix unicode escapes (error recovery).

include/llvm/Support/JSON.h

+//===--- JSON.h - JSON representation, parser, serializer -------*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This file allows creating, mutating, and (de-)serializing JSON.
+//
+// A Document is an owned JSON tree, and is the arena owning all values.
+// Values are JSON expressions owned by a Document. This is a union of:
+//   StringRef, bool, double, nullptr_t: for primitive types
+//   Array: similar to vector<Value>
+//   Object: similar to unordered_map<string, Value>
+// Arrays and Objects are mutable, inserted values are copied into the document.
+//
+// Literal allows you to use natural C++ expressions to construct JSON values.
+//
+// An example:
+//   // Parse a JSON file and do "error checking".
+//   Expected<Document> Doc = Document::parse("[1,true,3]");
+//   assert(Doc && Doc->array());
+//
+//   Array& A = *Doc->array();
+//   for (int I = 0; I < A.size(); ++I) {
+//     if (auto N = A[I].number()) {
+//       A.set(I, {{"number", *N}});
+//     }
+//   }
+//
+//   llvm::outs() << Doc;
+//   // [{"number":1},true,{"number":3}]
+//
+//===----------------------------------------------------------------------===//
+//
+// Caveats (fix me!):
+//  - parser is recursive-descent, so can overflow on malicious input
+//  - parser can reuse strings. Not for object keys - can we fix this?
+//  - StringMap may be suboptimal for tiny objects (vector too?)
+//  - it's probably safe to skip ~Value() and abandon arena-allocated values
+//  - nested literals are copied at every level (as initializer_list is const)
+//  - no support for prettyprinting/canonicalizing output
+//  - UTF-8 in strings is not validated
+//  - UTF-16 and UTF-32 streams are not supported
+//  - encapsulation is weak - too many friend declarations
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_CLANG_TOOLS_EXTRA_CLANGD_JSON_H
+#define LLVM_CLANG_TOOLS_EXTRA_CLANGD_JSON_H
+
+#include "llvm/ADT/iterator.h"
+#include "llvm/Support/Allocator.h"
+#include "llvm/Support/Error.h"
+#include "llvm/Support/JSONDetail.h"
+#include "llvm/Support/raw_os_ostream.h"
+#include "llvm/Support/raw_ostream.h"
+
+namespace llvm {
+namespace json {
+class Object;
+class Array;
+
+// The different kinds of possible JSON values.
+enum Kind : char {
+  NullKind,
+  BooleanKind,
+  NumberKind,
+  ObjectKind,
+  ArrayKind,
+  StringKind,
+};
+
+// A Literal is a temporary JSON structure used to construct Values.
+// You can implicitly construct Literals holding:
+//   - strings: std::string, SmallString, StringRef, Twine, char*, formatv
+//              (Twines, StringRefs are not deep copies. Convert to std::string)
+//   - numbers
+//   - booleans
+//   - null: nullptr
+//   - arrays: {"foo", 42.0, false}
+//         or: json::ary{"foo", 42.0, false}
+//   - objects: json::obj{{"key1", val1}, {"key2", val2}}
+//   - json::Value, json::Document
+//              (Values are by-reference - convert to a Document for a copy.)
+// Literals can be nested: Objects and Arrays contain arbitrary literals.
+//
+// Normally you don't need to name the type, just writing directly:
+//   Document D = {"one", 2, "three"};  // Calls Document(const Literal&)
+// If you do create Literals, be aware they don't own referenced strings/Values:
+//   Literal L = {AString, {42, AValue}};
+// L is only valid as long as AString and AValue are alive.
+// Think of a Literal as the JSON version of an llvm::Twine.
+using Literal = detail::Literal;
+// array(Literal...) returns an array convertible to Literal.
+// It has a push_back() function that can be used to build an array in a loop:
+//
+// json::Literal priceList() {
+//   json::ary A;
+//   for (int X : prices())
+//     A.push_back(X);
+//   return std::move(A);
+// }
+class ary {
+public:
+  ary(std::initializer_list<Literal> Args) {
+    Vec.reserve(Args.size());
+    for (const auto &Arg : Args)
+      Vec.emplace_back(std::move(Arg));
+  }
+  void push_back(Literal L) { Vec.push_back(std::move(L)); }
+  operator Literal() && { return Literal{std::move(Vec), Literal::LT_Array}; }
+
+private:
+  // Avoid ambiguous parse of ary{{2}} by disallowing implicit copy/move.
+  explicit ary(ary&&) = delete;
+  explicit ary(const ary&) = delete;
+  std::vector<Literal> Vec;
+};
+// obj{{Twine, Literal}...} is an object convertible to Literal.
+// It has a set() function that can be used to build an object in a loop:
+//
+// json::Literal priceMap() {
+//   json::obj O;
+//   for (const std::pair<string, int> X : prices())
+//     O.set(X.first, X.second);
+//   return std::move(O);
+// }
+class obj {
+public:
+  struct KV {  // Not std::pair, we need an implicit constructor.
+    KV(Twine K, Literal &&V) : Key(std::move(K)), Value(std::move(V)) {};
+    const Twine Key;
+    const Literal Value;
+  };
+  obj(std::initializer_list<KV> Args) {
+    for (const auto &Arg : Args)
+      set(Arg.Key, std::move(Arg.Value));
+  }
+  void set(const Twine &K, Literal V) {
+    Map.try_emplace(K.isSingleStringRef() ? K.getSingleStringRef()
+                                          : StringRef(K.str()),
+                    std::move(V));
+  }
+  operator Literal() && { return Literal{std::move(Map), Literal::LT_Object}; }
+
+private:
+  // Avoid ambiguous parse of obj{{2}} by disallowing implicit copy/move.
+  explicit obj(obj&&) = delete;
+  explicit obj(const obj&) = delete;
+  StringMap<Literal> Map;
+};
+
+// Value is a generic JSON value of unknown type, owned by a Document.
+//
+// A Value may be a number, string, boolean, object, array, or null.
+// The typed accessors let you access the Value's details.
+//
+// Value is obtained by reference, and is not copyable or movable. But you can:
+//   - clone it into new document: Document D = SomeValue;
+//   - copy it into an Array or Object: SomeObject.set("foo", SomeValue);
+// References to Values are invalidated when their immediate parent is mutated.
+class Value {
+public:
+  static Value Null;
+  static Value True;
+  static Value False;
+
+  Value(Value &&) = delete;
+  Value(Value &) = delete;
+  Value &operator=(Value &&) = delete;
+  Value &operator=(const Value &) = delete;
+  ~Value();
+
+  Kind kind() const {
+    switch (U.getTag()) {
+    case detail::VT_Sentinel:
+      return U == Null ? NullKind : BooleanKind;
+    case detail::VT_SmallInt:
+    case detail::VT_Double:
+      return NumberKind;
+    case detail::VT_Array:
+      return ArrayKind;
+    case detail::VT_Object:
+      return ObjectKind;
+    case detail::VT_OwnedString:
+    case detail::VT_StaticString:
+      return StringKind;
+    }
+  }
+
+  // Typed accessors return None/nullptr of the Value is not of this type.
+  Optional<double> number() const {
+    if (detail::SmallInt I = U.get<detail::VT_SmallInt>())
+      return double(I);
+    if (double *D = U.get<detail::VT_Double>())
+      return *D;
+    return None;
+  }
+  Optional<StringRef> string() const {
+    if (detail::PString *PS = U.get<detail::VT_OwnedString>())
+      return StringRef(*PS);
+    if (const char *S = *U.get<detail::VT_StaticString>())
+      return StringRef(S);
+    return None;
+  }
+  Optional<bool> boolean() const {
+    if (U == detail::TrueRep)
+      return true;
+    if (U == detail::FalseRep)
+      return false;
+    return None;
+  }
+  Object *object() { return U.get<detail::VT_Object>(); }
+  const Object *object() const { return U.get<detail::VT_Object>(); }
+  Array *array() { return U.get<detail::VT_Array>(); }
+  const Array *array() const { return U.get<detail::VT_Array>(); }
+  bool null() const { return U == detail::NullRep; }
+
+  // Returns the JSON serialization of this Value.
+  std::string str() const {
+    std::string S;
+    raw_string_ostream OS(S);
+    OS << *this;
+    return OS.str();
+  }
+
+  // Not part of the public interface (but only internals can name it)
+  explicit operator detail::ValueRep() const { return U; }
+
+private:
+  Value(detail::ValueRep R) : U(R) {}
+
+  // Value owns the lifetime of the object pointed to by U, but not its memory.
+  detail::ValueRep U;
+  friend detail::ValueWrapper;
+  friend bool operator==(const Value &, const Value &);
+  friend raw_ostream &operator<<(raw_ostream &, const class Value &);
+};
+
+// ValueWrapper provides move semantics for Value so containers can hold it.
+// Only moves within a document are valid!
+// \private
+class detail::ValueWrapper {
+public:
+  explicit ValueWrapper(ValueRep R) : V(R) {}
+  ValueWrapper(const ValueWrapper &Copy) = delete;
+  ValueWrapper(ValueWrapper &&Move) : V(Move.V.U) { Move.V.U = NullRep; }
+  ValueWrapper &operator=(const ValueWrapper &Copy) = delete;
+  ValueWrapper &operator=(ValueWrapper &&Move) {
+    V.~Value();
+    new (&V) Value(Move.V.U);
+    Move.V.U = detail::NullRep;
+    return *this;
+  }
+
+  operator Value &() { return V; }
+  operator const Value &() const { return V; }
+
+private:
+  Value V;
+};
+
+// Document is a self-contained JSON value of unknown type.
+// It owns the entire tree of values, which are stored in a BumpPtrAllocator.
+//
+// Documents can be passed cheaply by value or reference, clone() is expensive.
+class Document {
+public:
+  // Parses a document from a UTF-8 JSON stream.
+  // The only error reported is due to malformed input.
+  static Expected<Document> parse(StringRef text);
+
+  // An empty document, with value null.
+  explicit Document() // Use Document D = json::ary{} for an empty list doc!
+      : Alloc(nullptr), Root(detail::NullRep) {}
+  Document(Document &&) = default;
+  // Create a document from a literal JSON expression (see Literal above).
+  // Note that a json::Value may be passed here, it will be deep-copied.
+  Document(const Literal &V)
+      : Alloc(new detail::Arena()), Root(V.construct(*Alloc)) {}
+  Document(Literal &&V)
+      : Alloc(new detail::Arena()), Root(V.construct(*Alloc)) {}
+  // This constructor is needed to disambiguate Document({{"foo"}}), which could
+  // be Document(Document{Literal{"foo"}}) or Document(Literal{Literal{"foo"}}).
+  Document(std::initializer_list<Literal> V) : Document(Literal(V)){};
+  Document &operator=(Document &&Move) {
+    // The defaulted operator= destroys Alloc first, then ~Value() writes to it!
+    Root.~ValueWrapper();
+    Alloc = std::move(Move.Alloc);
+    new (&Root) detail::ValueWrapper(std::move(Move.Root));
+    return *this;
+  }
+  Document &operator=(const Literal &V) { return *this = Document(V); }
+  Document &operator=(std::initializer_list<Literal> V) {
+    return *this = Literal(V);
+  }
+
+  // Explicitly obtain the Value of this document.
+  Value &root() { return Root; }
+  const Value &root() const { return Root; }
+
+  // For most purposes, a Document can be treated as its root Value.
+  Kind kind() const { return root().kind(); }
+  Optional<double> number() const { return root().number(); }
+  Optional<StringRef> string() const { return root().string(); }
+  Optional<bool> boolean() const { return root().boolean(); }
+  bool null() const { return root().null(); }
+  Object *object() { return root().object(); }
+  const Object *object() const { return root().object(); }
+  Array *array() { return root().array(); }
+  const Array *array() const { return root().array(); }
+  std::string str() const { return root().str(); }
+  operator Value &() { return Root; }
+  operator const Value &() const { return Root; }
+
+  // Clean up memory used by values orphaned by mutations.
+  // This invalidates all Value references.
+  void trim() { *this = clone(); }
+  // Does a deep-copy (the copy-constructor is deleted as it is expensive).
+  Document clone() const { return Document((const Value &)*this); }
+  // Space actually used on the arena.
+  size_t usedBytes() const { return Alloc ? Alloc->getBytesAllocated() : 0; }
+  // Space consumed by the arena.
+  size_t allocatedBytes() const { return Alloc ? Alloc->getTotalMemory() : 0; }
+
+  class Parser;
+
+private:
+  Document(detail::ValueWrapper V, std::unique_ptr<detail::Arena> Alloc)
+      : Alloc(std::move(Alloc)), Root(std::move(V)) {}
+
+  std::unique_ptr<detail::Arena> Alloc;
+  detail::ValueWrapper Root;
+};
+
+// An Array is a JSON array, conceptually similar to a std::vector<Value>.
+// Elements written to the array are cloned to the document's backing arena.
+// To assign at an index, call Ary.set(I, SomeVal), not Ary[I] = SomeVal.
+// (The array knows how to clone onto the arena, but its elements do not).
+class Array {
+public:
+  Array(detail::Arena &Alloc) : Elems(Vec::allocator_type{Alloc}) {}
+  Array(size_t Size, detail::Arena &Alloc) : Array(Alloc) {
+    Elems.reserve(Size);
+  }
+  Array(Array &&) = delete;
+  Array(Array &) = delete;
+  Array &operator=(Array &&) = delete;
+  Array &operator=(const Array &) = delete;
+
+  // Iterator API.
+  using value_type = Value;
+  class const_iterator;
+  class iterator;
+  using const_reverse_iterator = std::reverse_iterator<const_iterator>;
+  using reverse_iterator = std::reverse_iterator<iterator>;
+  iterator begin() { return iterator(Elems.begin()); }
+  const_iterator begin() const { return const_iterator(Elems.begin()); }
+  iterator end() { return iterator(Elems.end()); }
+  const_iterator end() const { return const_iterator(Elems.end()); }
+  reverse_iterator rbegin() { return reverse_iterator(end()); }
+  const_reverse_iterator rbegin() const {
+    return const_reverse_iterator(end());
+  }
+  reverse_iterator rend() { return reverse_iterator(begin()); }
+  const_reverse_iterator rend() const {
+    return const_reverse_iterator(begin());
+  }
+
+  // Basic vector methods.
+  size_t size() const { return Elems.size(); }
+  void clear() { Elems.clear(); }
+  void reserve(size_t N) { Elems.reserve(N); }
+  void push_back(const Literal &V) {
+    Elems.push_back(V.construct(Elems.get_allocator()));
+  }
+  void pop_back() { Elems.pop_back(); }
+  iterator erase(const_iterator I) {
+    return iterator(Elems.erase(I.wrapped()));
+  }
+  iterator erase(const_iterator B, const_iterator E) {
+    return iterator(Elems.erase(B.wrapped(), E.wrapped()));
+  }
+  void insert(iterator I, const Literal &V) {
+    Elems.insert(I.wrapped(), V.construct(Elems.get_allocator()));
+  }
+  Value &operator[](size_t I) { return Elems[I]; }
+  const Value &operator[](size_t I) const { return Elems[I]; }
+  void set(size_t I, const Literal &V) {
+    Elems[I] = V.construct(Elems.get_allocator());
+  }
+
+  // Typed accessors.
+  Optional<double> number(size_t I) const { return (*this)[I].number(); }
+  Optional<StringRef> string(size_t I) const { return (*this)[I].string(); }
+  Optional<bool> boolean(size_t I) const { return (*this)[I].boolean(); }
+  bool null(size_t I) const { return (*this)[I].null(); }
+  Array *array(size_t I) { return (*this)[I].array(); }
+  const Array *array(size_t I) const { return (*this)[I].array(); }
+  Object *object(size_t I) { return (*this)[I].object(); }
+  const Object *object(size_t I) const { return (*this)[I].object(); }
+
+private:
+  // SmallVector is not allocator-aware. std::vector on an Arena behaves nicely!
+  using Vec =
+      std::vector<detail::ValueWrapper, detail::STLArena<detail::ValueWrapper>>;
+  Vec Elems;
+  friend class Document::Parser;
+  friend detail::ValueRep detail::deepCopy(const detail::ValueRep &U,
+                                           detail::Arena &Alloc);
+
+public:
+  class iterator : public iterator_adaptor_base<iterator, Vec::iterator,
+                                                std::random_access_iterator_tag,
+                                                value_type> {
+    friend Array;
+
+  public:
+    iterator() = default;
+    explicit iterator(Vec::iterator I) : iterator_adaptor_base(std::move(I)) {}
+  };
+
+  class const_iterator
+      : public iterator_adaptor_base<const_iterator, Vec::const_iterator,
+                                     std::random_access_iterator_tag,
+                                     const value_type> {
+    friend Array;
+
+  public:
+    const_iterator() = default;
+    explicit const_iterator(Vec::const_iterator I)
+        : iterator_adaptor_base(std::move(I)) {}
+  };
+};
+
+// An Object is a JSON object, similar to a std::unordered_map<string, Value>.
+// Elements written to the object are cloned to the document's backing arena.
+// To assign at a key, call Obj.set(K, SomeVal), not Obj[K] = SomeVal.
+// (The object knows how to clone onto the arena, but its elements do not).
+class Object {
+public:
+  Object(detail::Arena &Alloc) : Props(Alloc) {}
+  Object(size_t Size, detail::Arena &Alloc) : Props(Size, Alloc) {}
+  Object(Object &&) = delete;
+  Object(Object &) = delete;
+  Object &operator=(Object &&) = delete;
+  Object &operator=(const Object &) = delete;
+
+  // Iterator API.
+  using key_type = StringRef;
+  using mapped_type = Value;
+  struct value_type {
+    value_type(StringRef first, Value &second) : first(first), second(second) {}
+    const StringRef first;
+    Value &second;
+  };
+  class const_iterator;
+  class iterator;
+  iterator begin() { return iterator(Props.begin()); }
+  const_iterator begin() const { return const_iterator(Props.begin()); }
+  iterator end() { return iterator(Props.end()); }
+  const_iterator end() const { return const_iterator(Props.end()); }
+
+  // Basic map methods.
+  size_t size() const { return Props.size(); }
+  void clear() { Props.clear(); }
+  Value &operator[](StringRef K) {
+    auto I = Props.find(K);
+    return (I == Props.end()) ? Value::Null : (Value &)(I->second);
+  }
+  const Value &operator[](StringRef K) const {
+    auto I = Props.find(K);
+    return (I == Props.end()) ? Value::Null : (Value &)(I->second);
+  }
+  iterator find(StringRef K) { return iterator(Props.find(K)); }
+  const_iterator find(StringRef K) const {
+    return const_iterator(Props.find(K));
+  }
+  Value *get(StringRef K) {
+    auto I = Props.find(K);
+    return (I == Props.end()) ? nullptr : &(Value &)(I->second);
+  }
+  const Value *get(StringRef K) const {
+    auto I = Props.find(K);
+    return (I == Props.end()) ? nullptr : &(const Value &)(I->second);
+  }
+  size_t count(StringRef K) { return Props.count(K); }
+  void set(StringRef K, const Literal &V) {
+    auto VW = V.construct(Props.getAllocator());
+    auto R = Props.try_emplace(K, std::move(VW));
+    if (!R.second)
+      R.first->second = std::move(VW);
+  }
+  std::pair<iterator, bool> insert(const value_type &V) {
+    return emplace(V.first, V.second);
+  }
+  std::pair<iterator, bool> emplace(StringRef K, const Literal &V) {
+    auto R = Props.try_emplace(K, V.construct(Props.getAllocator()));
+    return {iterator(R.first), R.second};
+  }
+  void erase(iterator I) { Props.erase(I.wrapped()); }
+  bool erase(StringRef K) { return Props.erase(K); }
+
+  // Typed accessors.
+  Optional<double> number(StringRef I) const {
+    if (const Value *V = get(I))
+      return V->number();
+    return None;
+  }
+  Optional<StringRef> string(StringRef I) const {
+    if (const Value *V = get(I))
+      return V->string();
+    return None;
+  }
+  Optional<bool> boolean(StringRef I) const {
+    if (const Value *V = get(I))
+      return V->boolean();
+    return None;
+  }
+  bool null(StringRef I) const {
+    if (const Value *V = get(I))
+      return V->null();
+    return false;
+  }
+  Array *array(StringRef I) {
+    if (Value *V = get(I))
+      return V->array();
+    return nullptr;
+  }
+  const Array *array(StringRef I) const {
+    if (const Value *V = get(I))
+      return V->array();
+    return nullptr;
+  }
+  Object *object(StringRef I) {
+    if (Value *V = get(I))
+      return V->object();
+    return nullptr;
+  }
+  const Object *object(StringRef I) const {
+    if (const Value *V = get(I))
+      return V->object();
+    return nullptr;
+  }
+
+private:
+  using Map = StringMap<detail::ValueWrapper, detail::Arena &>;
+  Map Props;
+  friend Document::Parser;
+  friend detail::ValueRep detail::deepCopy(const detail::ValueRep &U,
+                                           detail::Arena &Alloc);
+
+public:
+  class iterator
+      : public iterator_adaptor_base<iterator, Map::iterator,
+                                     std::forward_iterator_tag, value_type> {
+    Optional<value_type> Current;
+    friend Object;
+
+  public:
+    iterator() = default;
+    explicit iterator(Map::iterator I) : iterator_adaptor_base(std::move(I)) {}
+    value_type &operator*() {
+      Current.emplace(wrapped()->getKey(), wrapped()->second);
+      return *Current;
+    }
+  };
+
+  class const_iterator
+      : public iterator_adaptor_base<const_iterator, Map::const_iterator,
+                                     std::forward_iterator_tag,
+                                     const value_type> {
+    Optional<const value_type> Current;
+    friend Object;
+
+  public:
+    const_iterator() = default;
+    explicit const_iterator(Map::const_iterator I)
+        : iterator_adaptor_base(std::move(I)) {}
+
+    const value_type &operator*() {
+      Current.emplace(wrapped()->getKey(),
+                      const_cast<Value &>((const Value &)(wrapped()->second)));
+      return *Current;
+    }
+  };
+};
+
+bool operator==(const Array &, const Array &);
+bool operator==(const Object &, const Object &);
+bool operator==(const Value &, const Value &);
+inline bool operator!=(const Array &L, const Array &R) { return !(L == R); }
+inline bool operator!=(const Object &L, const Object &R) { return !(L == R); }
+inline bool operator!=(const Value &L, const Value &R) { return !(L == R); }
+inline hash_code hash_value(const Array &A) {
+  return hash_combine_range(A.begin(), A.end());
+}
+hash_code hash_value(const Object &O);
+hash_code hash_value(const Value &O);
+// Values are ordered Null < Boolean < Number < Object < Array < String.
+// Primitive values of the same type have their natural ordering.
+// Arrays are lexicographically ordered, Objects in some arbitrary order.
+inline bool operator<(const Object &L, const Object &R) {
+  // FIXME: define a meaningful ordering on Objects.
+  return size_t(hash_value(L)) < size_t(hash_value(R));
+}
+inline bool operator<(const Array &L, const Array &R) {
+  return std::lexicographical_compare(L.begin(), L.end(), R.begin(), R.end());
+}
+bool operator<(const Value &L, const Value &R);
+// Arrays, Objects, and Values print their JSON representations.
+raw_ostream &operator<<(raw_ostream &OS, const Array &V);
+raw_ostream &operator<<(raw_ostream &OS, const Object &V);
+raw_ostream &operator<<(raw_ostream &OS, const Value &V);
+
+// For gtest. The default operator<< adapter doesn't work, as gtest needs ADL.
+inline void PrintTo(const Array &V, std::ostream *S) {
+  raw_os_ostream OS(*S);
+  OS << V;
+}
+inline void PrintTo(const Object &V, std::ostream *S) {
+  raw_os_ostream OS(*S);
+  OS << V;
+}
+inline void PrintTo(const Value &V, std::ostream *S) {
+  raw_os_ostream OS(*S);
+  OS << V;
+}
+inline void PrintTo(const Document &V, std::ostream *S) {
+  raw_os_ostream OS(*S);
+  OS << V;
+}
+
+} // namespace json
+} // namespace llvm
+
+#endif

include/llvm/Support/JSONDetail.h

+//===--- JSONDetail.h - implementation details for JSON.h -------*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/ADT/PointerEmbeddedInt.h"
+#include "llvm/ADT/PointerSumType.h"
+#include "llvm/ADT/Twine.h"
+#include "llvm/Support/Allocator.h"
+#include "llvm/Support/FormatVariadic.h"
+#include "llvm/Support/PointerLikeTypeTraits.h"
+#include "llvm/Support/TrailingObjects.h"
+
+namespace llvm {
+namespace json {
+class Object;
+class Array;
+class Value;
+class Document;
+class obj;
+class ary;
+namespace detail {
+
+// Memory inside a JSON document is managed by an Arena (BumpPtrAllocator).
+// Array uses std::vector, so we adapt LLVM's allocator concept to the STL's.
+constexpr size_t FirstSlabSize = 1024;
+using Arena = BumpPtrAllocatorImpl<MallocAllocator, FirstSlabSize>;
+template <typename T> struct STLArena {
+  using value_type = T;
+  T *allocate(size_t N) {
+    return static_cast<T *>(A.Allocate(N * sizeof(T), alignof(T)));
+  }
+  void deallocate(T *P, size_t N) { A.Deallocate(P, N * sizeof(T)); }
+  operator Arena &() { return A; }
+  Arena &A;
+};
+
+// The Object and Array types are used in a the Value::Rep PointerSumType.
+// This requires them to be complete, but they have Values as indirect members!
+// We get around this circularity by explicitly specifying that they are at
+// least as aligned as an int64. (Both are large objects of at least 24 bytes).
+} // namespace detail
+} // namespace json
+template <> struct PointerLikeTypeTraits<json::Object *> {
+  static inline void *getAsVoidPointer(json::Object *P) { return P; }
+  static inline json::Object *getFromVoidPointer(void *P) {
+    return static_cast<json::Object *>(P);
+  }
+  enum {
+    NumLowBitsAvailable = PointerLikeTypeTraits<int64_t *>::NumLowBitsAvailable
+  };
+};
+template <> struct PointerLikeTypeTraits<json::Array *> {
+  static inline void *getAsVoidPointer(json::Array *P) { return P; }
+  static inline json::Array *getFromVoidPointer(void *P) {
+    return static_cast<json::Array *>(P);
+  }
+  enum {
+    NumLowBitsAvailable = PointerLikeTypeTraits<int64_t *>::NumLowBitsAvailable
+  };
+};
+namespace json {
+namespace detail {
+
+// PString is the internal representation of a String value.
+// These are immutable, so we just allocate the right number of bytes.
+struct PString final : public TrailingObjects<PString, char> {
+  size_t Size;
+  const char *data() const { return getTrailingObjects<char>(); }
+
+  operator StringRef() const { return StringRef(data(), Size); }
+  bool operator==(const PString &PS) const {
+    return Size == PS.Size && !memcmp(data(), PS.data(), Size);
+  }
+  static PString *create(StringRef S, Arena &Alloc) {
+    PString *PS = static_cast<PString *>(
+        Alloc.Allocate(totalSizeToAlloc<char>(S.size()), alignof(PString)));
+    PS->Size = S.size();
+    memcpy(const_cast<char *>(PS->data()), S.data(), S.size());
+    return PS;
+  }
+};
+
+// ValueRep is the lightweight representation of an arbitrary JSON value.
+// It is a tagged pointer: [ pointer to representation | type ].
+// The representation is stored in a BumpPtrAllocator in a type-specific way.
+// true/false/null/integers have no extra data outside the ValueType.
+//
+// ValueRep has no ownership semantics, like a raw pointer.
+// Value wraps ValueRep and owns the external data's lifetime (but not storage).
+// ValueWrapper wraps Value and adds movability for use in internal containers.
+enum ValueType {
+  VT_Sentinel = 0,
+  VT_SmallInt,
+  VT_Double,
+  VT_Array,
+  VT_Object,
+  VT_OwnedString,
+  VT_StaticString,
+};
+enum SentinelValue : char {
+  SV_Null = 0,
+  SV_True = 1,
+  SV_False = 2,
+};
+// We pack integers into the pointer, up to 53 bits. (More than that would
+// result in inconsistent rounding as they're not representible as doubles).
+// Of course on 32-bit platforms, we have fewer spare bits.
+constexpr size_t SmallIntSize = 53 <= CHAR_BIT * sizeof(uintptr_t) - 3
+                                    ? 53
+                                    : CHAR_BIT * sizeof(uintptr_t) - 3;
+using SmallInt = PointerEmbeddedInt<int64_t, SmallIntSize>;
+template <typename T> bool isSmallInt(T V) {
+  int64_t I = static_cast<int64_t>(V);
+  return V == I && isInt<SmallIntSize>(I);
+}
+using ValueRep = PointerSumType<
+    ValueType,
+    PointerSumTypeMember<VT_Sentinel, PointerEmbeddedInt<SentinelValue>>,
+    PointerSumTypeMember<VT_SmallInt, SmallInt>,
+    PointerSumTypeMember<VT_Double, double *>,
+    PointerSumTypeMember<VT_Array, Array *>,
+    PointerSumTypeMember<VT_Object, Object *>,
+    PointerSumTypeMember<VT_OwnedString, PString *>,
+    PointerSumTypeMember<VT_StaticString, const char **>>;
+const ValueRep TrueRep = ValueRep::create<VT_Sentinel>(SV_True);
+const ValueRep FalseRep = ValueRep::create<VT_Sentinel>(SV_False);
+const ValueRep NullRep = ValueRep::create<VT_Sentinel>(SV_Null);
+
+class ValueWrapper;
+ValueRep deepCopy(const ValueRep &U, Arena &Alloc);
+
+class Literal {
+public:
+  // This moves from a *const* rvalue reference! (all members are mutable)
+  // This allows moving rather than copying out of initializer_list<Literal>.
+  // We lose the compiler's sanity-checking and the ability to usefully overload
+  // on const vs non-const Literals, luckily we need neither.
+  Literal(const Literal &&);
+  ~Literal();
+
+  // Strings: std::string, SmallString, char* (by value).
+  // StringRef, Twine, (by reference).
+  // char literals (by reference, and never copied into the document).
+  Literal(std::string &&V) : Type(LT_String) {
+    new (&R.String) std::string(std::move(V));
+  }
+  Literal(const std::string &V) : Type(LT_String) {
+    new (&R.String) std::string(V);
+  }
+  // We don't actually move SmallString/formatv, but copy to get value semantics.
+  Literal(const SmallVectorImpl<char> &V) : Type(LT_String) {
+    new (&R.String) std::string(V.data(), V.size());
+  }
+  Literal(const formatv_object_base &V) : Type(LT_String) {
+    new (&R.String) std::string(V.str());
+  }
+  Literal(const Twine &V) : Type(LT_Twine) { new (&R.Twine) Twine(V); }
+  Literal(const StringRef &V) : Type(LT_Twine) { new (&R.Twine) Twine(V); }
+  // String literals are tracked separately to avoid copying them later.
+  template <int N> Literal(const char (&V)[N]) : Type(LT_StaticString) {
+    assert(strlen(V) == N - 1 &&
+           "Detected string literal but not null-terminated!");
+    R.StaticString = V;
+  }
+  // Don't treat const char* as a string literal unless it matched above.
+  // Use a template to reduce overload match strength of string literals.
+  template <typename T,
+            typename = typename std::enable_if<
+                std::is_same<T, const char *>::value>::type,
+            char Dummy = 0>
+  Literal(T V) : Type(LT_Twine) {
+    new (&R.String) std::string(V);
+  }
+  // Mutable char arrays are also not string literals.
+  template <int N> Literal(char (&V)[N]) : Literal((const char *)V) {}
+
+  // Booleans: bool.
+  // The default conversion rules will convert things to bool way too easily.
+  template <
+      typename T,
+      typename = typename std::enable_if<std::is_same<T, bool>::value>::type,
+      bool Dummy = 0>
+  Literal(T V) : Type(LT_Immediate) {
+    R.Immediate = V ? TrueRep : FalseRep;
+  }
+
+  // Numbers: built-in numeric types.
+  // is_arithmetic<T> is almost the right criterion, but exclude bool.
+  template <
+      typename T,
+      typename = typename std::enable_if<std::is_arithmetic<T>::value>::type,
+      typename = typename std::enable_if<std::integral_constant<
+          bool, !std::is_same<T, bool>::value>::value>::type,
+      int Dummy = 0>
+  Literal(T V) {
+    if (isSmallInt(V)) {
+      Type = LT_Immediate;
+      R.Immediate = ValueRep::create<VT_SmallInt>(V);
+    } else {
+      Type = LT_Double;
+      R.Double = V;
+    }
+  }
+
+  // Null: nullptr.
+  Literal(std::nullptr_t) : Type(LT_Immediate) { R.Immediate = NullRep; }
+
+  // Arrays: initializer_list<Literal>.
+  using LiteralList = std::initializer_list<Literal>;
+  Literal(LiteralList V);
+
+  // References to JSON values: Value&.
+  // The value must outlive this Literal.
+  Literal(const Value &V) : Type(LT_Value) { R.Value = &V; }
+  // Complete JSON document: Document.
+  Literal(Document V);
+
+  // Materializes this JSON value, allocating into the arena.
+  ValueWrapper construct(Arena &) const;
+
+private:
+  void reset() const;
+
+  mutable enum LiteralType : char {
+    LT_Twine,
+    LT_String,
+    LT_StaticString,
+    LT_Array,
+    LT_Object,
+    LT_Double,
+    LT_Immediate,
+    LT_Value,
+    LT_Document,
+  } Type;
+  union Rep {
+    Rep() {}
+    ~Rep() {}
+    Twine Twine;
+    std::string String;
+    const char *StaticString;
+    std::vector<Literal> Array;
+    StringMap<Literal> Object;
+    double Double;
+    ValueRep Immediate;
+    const Value *Value;
+    std::unique_ptr<Document> Document;
+  };
+  mutable Rep R;
+
+  Literal(StringMap<Literal> &&Object, LiteralType Dummy) : Type(LT_Object) {
+    new (&R.Object) StringMap<Literal>(std::move(Object));
+  }
+  friend obj;
+  Literal(std::vector<Literal> &&Array, LiteralType Dummy) : Type(LT_Array) {
+    new (&R.Array) std::vector<Literal>(std::move(Array));
+  }
+  friend ary;
+};
+
+} // namespace detail
+} // namespace json
+} // namespace llvm

lib/Support/CMakeLists.txt

add_llvm_library(LLVMSupport
   FormattedStream.cpp
   FormatVariadic.cpp
   GlobPattern.cpp
   GraphWriter.cpp
   Hashing.cpp
   IntEqClasses.cpp
   IntervalMap.cpp
   JamCRC.cpp
+  JSON.cpp
   KnownBits.cpp
   LEB128.cpp
   LineIterator.cpp
   Locale.cpp
   LockFileManager.cpp
   LowLevelType.cpp
   ManagedStatic.cpp
   MathExtras.cpp

lib/Support/JSON.cpp

+//===--- JSON.cpp - JSON representation, parser, serializer -----*- 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/Format.h"
+#include "llvm/Support/FormatVariadic.h"
+#include "llvm/Support/NativeFormatting.h"
+
+namespace llvm {
+namespace json {
+using namespace llvm::json::detail;
+
+ValueRep detail::deepCopy(const ValueRep &U, Arena &Alloc) {
+  switch (U.getTag()) {
+  case VT_Sentinel:
+  case VT_SmallInt:
+    return U;
+  case VT_OwnedString:
+    return ValueRep::create<VT_OwnedString>(
+        PString::create(*U.cast<VT_OwnedString>(), Alloc));
+  case VT_StaticString:
+    return ValueRep::create<VT_StaticString>(
+        new (Alloc) const char *(*U.cast<VT_StaticString>()));
+  case VT_Double:
+    return ValueRep::create<VT_Double>(
+        new (Alloc) double{*U.cast<VT_Double>()});
+  case VT_Array: {
+    Array *Old = U.cast<VT_Array>();
+    Array *A = new (Alloc) Array(Old->size(), Alloc);
+    for (const Value &E : *Old)
+      A->Elems.emplace_back(deepCopy(ValueRep(E), Alloc));
+    return ValueRep::create<VT_Array>(A);
+  }
+  case VT_Object: {
+    Object *Old = U.cast<VT_Object>();
+    Object *O = new (Alloc) Object(Old->size(), Alloc);
+    for (const auto &E : *Old)
+      // TODO: remove friends with more naive code if it optimizes OK.
+      O->Props.try_emplace(E.first, deepCopy(ValueRep(E.second), Alloc));
+    return ValueRep::create<VT_Object>(O);
+  }
+  }
+}
+
+ValueWrapper Literal::construct(Arena &Alloc) const {
+  switch (Type) {
+  case LT_Twine: {
+    return ValueWrapper(ValueRep::create<VT_OwnedString>(PString::create(
+        R.Twine.isSingleStringRef() ? R.Twine.getSingleStringRef()
+                                    : StringRef(R.Twine.str()),
+        Alloc)));
+  }
+  case LT_String:
+    return ValueWrapper(
+        ValueRep::create<VT_OwnedString>(PString::create(R.String, Alloc)));
+  case LT_StaticString:
+    return ValueWrapper(ValueRep::create<VT_StaticString>(
+        new (Alloc) const char *(R.StaticString)));
+  case LT_Array: {
+    Array *A = new (Alloc) Array(R.Array.size(), Alloc);
+    for (const Literal &E : R.Array)
+      A->push_back(E);
+    return ValueWrapper(ValueRep::create<VT_Array>(A));
+  }
+  case LT_Object: {
+    Object *O = new (Alloc) Object(R.Object.size(), Alloc);
+    for (const auto &E : R.Object)
+      O->set(E.first(), E.second);
+    return ValueWrapper(ValueRep::create<VT_Object>(O));
+  }
+  case LT_Double:
+    return ValueWrapper(
+        ValueRep::create<VT_Double>(new (Alloc) double{R.Double}));
+  case LT_Immediate:
+    return ValueWrapper(R.Immediate);
+  case LT_Value: // Deep copy.
+    return ValueWrapper(deepCopy(ValueRep(*R.Value), Alloc));
+  case LT_Document: // Deep copy.
+    return ValueWrapper(deepCopy(ValueRep(R.Document->root()), Alloc));
+  }
+}
+
+Value Value::True(TrueRep);
+Value Value::False(FalseRep);
+Value Value::Null(NullRep);
+
+Value::~Value() {
+  static_assert(alignof(Array) >= alignof(int64_t), "");
+  static_assert(alignof(Object) >= alignof(int64_t), "");
+
+  switch (U.getTag()) {
+  case VT_Array:
+    U.cast<VT_Array>()->~Array();
+    break;
+  case VT_Object:
+    U.cast<VT_Object>()->~Object();
+    break;
+  case VT_StaticString:
+  case VT_OwnedString:
+  case VT_Double:
+  case VT_SmallInt:
+  case VT_Sentinel:
+    // POD, nothing to do.
+    break;
+  }
+}
+
+bool operator==(const Value &L, const Value &R) {
+  if (L.U == R.U)
+    return true;
+  Kind K = L.kind();
+  if (K != R.kind())
+    return false;
+  switch (K) {
+  case StringKind:
+    return *L.string() == *R.string();
+  case ArrayKind:
+    return *L.U.cast<VT_Array>() == *R.U.cast<VT_Array>();
+  case ObjectKind:
+    return *L.U.cast<VT_Object>() == *R.U.cast<VT_Object>();
+  case NumberKind:
+    return *L.number() == *R.number();
+  case BooleanKind:
+    return false; // rep equality checked above.
+  case NullKind:
+    llvm_unreachable("NullKinds with distinct ValueRep");
+  }
+}
+
+bool operator<(const Value &L, const Value &R) {
+  Kind LK = L.kind(), RK = R.kind();
+  if (LK != RK)
+    return LK < RK;
+  switch (LK) {
+  case StringKind:
+    return *L.string() < *R.string();
+  case ArrayKind:
+    return *L.array() < *R.array();
+  case ObjectKind:
+    return *L.object() < *R.object();
+  case NumberKind:
+    return *L.number() < *R.number();
+  case BooleanKind:
+    return *L.boolean() < *R.boolean();
+  case NullKind:
+    return false;
+  }
+}
+
+hash_code hash_value(const Value &V) {
+  switch (Kind K = V.kind()) {
+  case StringKind:
+    return hash_combine(K, *V.string());
+  case ArrayKind:
+    return hash_combine(K, *V.array());
+  case ObjectKind:
+    return hash_combine(K, *V.object());
+  case NumberKind: {
+    double D = *V.number(); // doubles are not directly hashable.
+    return hash_combine(K, *reinterpret_cast<uint64_t *>(&D));
+  }
+  case BooleanKind:
+    return hash_combine(K, *V.boolean());
+  case NullKind:
+    return hash_combine(K);
+  }
+}
+
+bool operator==(const Array &L, const Array &R) {
+  if (L.size() != R.size())
+    return false;
+  for (size_t I = 0; I < L.size(); ++I)
+    if (L[I] != R[I])
+      return false;
+  return true;
+}
+
+bool operator==(const Object &L, const Object &R) {
+  if (L.size() != R.size())
+    return false;
+  for (const auto &E : L) {
+    const Value *Other = R.get(E.first);
+    if (!Other || E.second != *Other)
+      return false;
+  }
+  return true;
+}
+
+hash_code hash_value(const Object &O) {
+  size_t Hash = 0;
+  for (const auto &E : O)
+    Hash += hash_combine(E.first, E.second);
+  return Hash; // Independent of iteration order.
+}
+
+Literal::Literal(LiteralList V) : Type(LT_Array) {
+  new (&R.Array) std::vector<Literal>(std::make_move_iterator(V.begin()),
+                                      std::make_move_iterator(V.end()));
+}
+
+Literal::Literal(Document V) : Type(LT_Document) {
+  new (&R.Document) std::unique_ptr<Document>(new Document(std::move(V)));
+}
+
+Literal::Literal(const Literal &&Move) {
+  switch (Move.Type) {
+  case LT_Twine:
+    new (&R.Twine) Twine(std::move(Move.R.Twine));
+    Move.R.Twine.~Twine();
+    break;
+  case LT_String:
+    new (&R.String) std::string(std::move(Move.R.String));
+    Move.R.String.~basic_string();
+    break;
+  case LT_Object:
+    new (&R.Object) StringMap<Literal>(std::move(Move.R.Object));
+    Move.R.Object.~StringMap();
+    break;
+  case LT_Array:
+    new (&R.Array) std::vector<Literal>(std::move(Move.R.Array));
+    Move.R.Array.~vector();
+    break;
+  case LT_Document:
+    new (&R.Document) std::unique_ptr<Document>(std::move(Move.R.Document));
+    Move.R.Document.~unique_ptr();
+    break;
+  case LT_Immediate:
+  case LT_StaticString:
+  case LT_Double:
+  case LT_Value:
+    memcpy(&R, &Move.R, sizeof(ValueRep)); // POD
+  }
+  Type = Move.Type;
+  Move.Type = LT_Immediate;
+  Move.R.Immediate = NullRep;
+}
+
+Literal::~Literal() {
+  switch (Type) {
+  case LT_Twine:
+    R.Twine.~Twine();
+    break;
+  case LT_String:
+    R.String.~basic_string();
+    break;
+  case LT_Object:
+    R.Object.~StringMap();
+    break;
+  case LT_Array:
+    R.Array.~vector();
+    break;
+  case LT_Document:
+    R.Document.~unique_ptr();
+    break;
+  case LT_Immediate:
+  case LT_StaticString:
+  case LT_Double:
+  case LT_Value:
+    break; // POD, nothing to do.
+  }
+}
+
+static void quote(StringRef S, raw_ostream &OS) {
+  OS << "\"";
+  for (unsigned char C : S) {
+    if (C == 0x22 || C == 0x5C)
+      OS << '\\';
+    if (C >= 0x20) {
+      OS << C;
+      continue;
+    }
+    OS << '\\';
+    switch (C) {
+    // Some control characters have shorter escape sequences than \uXXXX.
+    case '\b':
+      OS << 'b';
+      break;
+    case '\t':
+      OS << 't';
+      break;
+    case '\n':
+      OS << 'n';
+      break;
+    case '\f':
+      OS << 'f';
+      break;
+    case '\r':
+      OS << 'r';
+      break;
+    default:
+      OS << 'u';
+      llvm::write_hex(OS, C, HexPrintStyle::Lower, 4);
+      break;
+    }
+  }
+  OS << "\"";
+}
+
+raw_ostream &operator<<(raw_ostream &OS, const Array &V) {
+  const char *Sep = "";
+  OS << "[";
+  for (const auto &E : V) {
+    OS << Sep << E;
+    Sep = ",";
+  }
+  OS << "]";
+  return OS;
+}
+
+raw_ostream &operator<<(raw_ostream &OS, const Object &V) {
+  const char *Sep = "";
+  OS << "{";
+  for (const auto &P : V) {
+    OS << Sep;
+    quote(P.first, OS);
+    OS << ":" << P.second;
+    Sep = ",";
+  }
+  OS << "}";
+  return OS;
+}
+
+raw_ostream &operator<<(raw_ostream &OS, const Value &V) {
+  switch (V.U.getTag()) {
+  case VT_Array:
+    OS << *V.U.cast<VT_Array>();
+    break;
+  case VT_Object:
+    OS << *V.U.cast<VT_Object>();
+    break;
+  case VT_OwnedString:
+    quote(*V.U.cast<VT_OwnedString>(), OS);
+    break;
+  case VT_StaticString:
+    quote(*V.U.cast<VT_StaticString>(), OS);
+    break;
+  case VT_Double:
+    OS << format("%g", *V.U.cast<VT_Double>());
+    break;
+  case VT_SmallInt:
+    OS << V.U.cast<VT_SmallInt>();
+    break;
+  case VT_Sentinel:
+    switch (V.U.cast<VT_Sentinel>()) {
+    case SV_Null:
+      OS << "null";
+      break;
+    case SV_True:
+      OS << "true";
+      break;
+    case SV_False:
+      OS << "false";
+      break;
+    }
+    break;
+  }
+  return OS;
+}
+
+class Document::Parser {
+public:
+  Parser(StringRef Text)
+      : Start(Text.data()), P(Text.data()), End(Text.data() + Text.size()),
+        Alloc(new Arena()) {}
+
+  Expected<Document> parseDocument() {
+    auto Root = parseObject();
+    if (!Root)
+      return std::move(*Err);
+    eatWhitespace();
+    if (P != End) {
+      error("Text after end of document");
+      return std::move(*Err);
+    }
+    if (Err)
+      llvm_unreachable("Error should have been reported");
+    return Document(ValueWrapper(*Root), std::move(Alloc));
+  }
+
+private:
+  Optional<Error> Err;
+  const char *Start, *P, *End;
+  std::unique_ptr<Arena> Alloc;
+
+  Optional<ValueRep> parseObject() {
+    eatWhitespace();
+    if (P == End)
+      return error("Unexpected EOF");
+    switch (char C = next()) {
+    case 't': {
+      if (!(consume('r') && consume('u') && consume('e')))
+        return error("Invalid bareword");
+      return TrueRep;
+    }
+    case 'f': {
+      if (!(consume('a') && consume('l') && consume('s') && consume('e')))
+        return error("Invalid bareword");
+      return FalseRep;
+    }
+    case 'n': {
+      if (!(consume('u') && consume('l') && consume('l')))
+        return error("Invalid bareword");
+      return NullRep;
+    }
+    case '"': {
+      auto S = parseString();
+      if (!S)
+        return None;
+      return ValueRep::create<VT_OwnedString>(PString::create(*S, *Alloc));
+    }
+    case '[': {
+      Array *A = new (*Alloc) Array(*Alloc);
+      eatWhitespace();
+      if (peek() == ']') {
+        ++P;
+        return ValueRep::create<VT_Array>(A);
+      }
+      for (;;) {
+        auto Elem = parseObject();
+        if (!Elem)
+          return None;
+        A->Elems.emplace_back(*Elem);
+        eatWhitespace();
+        switch (next()) {
+        case ',':
+          eatWhitespace();
+          continue;
+        case ']':
+          return ValueRep::create<VT_Array>(A);
+        default:
+          return error("Expected , or ] after array element");
+        }
+      }
+    }
+    case '{': {
+      Object *O = new (*Alloc) Object(*Alloc);
+      eatWhitespace();
+      if (peek() == '}') {
+        ++P;
+        return ValueRep::create<VT_Object>(O);
+      }
+      for (;;) {
+        if (next() != '"')
+          return error("Expected object key");
+        auto K = parseString();
+        if (!K)
+          return None;
+        eatWhitespace();
+        if (next() != ':')
+          return error("Expected : after object key");
+        eatWhitespace();
+        auto V = parseObject();
+        if (!V)
+          return None;
+        O->Props.try_emplace(*K, *V);
+        eatWhitespace();
+        switch (next()) {
+        case ',':
+          eatWhitespace();
+          continue;
+        case '}':
+          return ValueRep::create<VT_Object>(O);
+        default:
+          return error("Expected , or } after object value");
+        }
+      }
+    }
+    default:
+      if (isNumber(C)) {
+        auto V = parseNumber(C);
+        if (!V)
+          return None;
+        if (isSmallInt(*V))
+          return ValueRep::create<VT_SmallInt>(*V);
+        return ValueRep::create<VT_Double>(new (*Alloc) double{*V});
+      }
+      return error("Expected JSON value");
+    }
+  }
+
+  Optional<SmallString<16>> parseString() {
+    SmallString<16> Result;
+    for (char C = next(); C != '"'; C = next()) {
+      switch (C) {
+      default:
+        Result.push_back(C);
+        break;
+      case 0:
+        return error("Unterminated string");
+      case '\\':
+        switch (C = next()) {
+        case '"':
+        case '\\':
+        case '/':
+          Result.push_back(C);
+          break;
+        case 'b':
+          Result.push_back('\b');
+          break;
+        case 'f':
+          Result.push_back('\f');
+          break;
+        case 'n':
+          Result.push_back('\n');
+          break;
+        case 'r':
+          Result.push_back('\r');
+          break;
+        case 't':
+          Result.push_back('\t');
+          break;
+        case 'u':
+          if (!parseUnicode(Result))
+            return None;
+          break;
+        default:
+          return error("Invalid escape sequence");
+        }
+      }
+    }
+    return Result;
+  }
+
+  // Parse a \uNNNN escape sequence, the \u have already been consumed.
+  // May parse multiple escapes in some cases (surrogate pairs).
+  bool parseUnicode(SmallVectorImpl<char> &Out) {
+    auto Invalid = [&] { Out.append({'\xef', '\xbf', '\xbd'}); };
+    auto Parse2 = [this](uint16_t &V) {
+      V = 0;
+      char Bytes[] = {next(), next(), next(), next()};
+      for (unsigned char C : Bytes) {
+        if (!std::isxdigit(C)) {
+          error("invalid \\u escape sequence");
+          return false;
+        }
+        V <<= 4;
+        V |= (C > '9') ? (C & ~0x20) - 'A' + 10 : (C - '0');
+      }
+      return true;
+    };
+    uint16_t First;
+    if (!Parse2(First))
+      return false;
+
+    // We loop to allow proper surrogate-pair error handling.
+    while (true) {
+      if (First < 0xD800 || First >= 0xE000) // BMP.
+        return encodeUtf8(First, Out);
+
+      if (First >= 0xDC00) {
+        Invalid(); // Lone trailing surrogate.
+        return true;
+      }
+
+      // We have a leading surrogate, and need a trailing one.
+      // Don't advance P: a lone surrogate is valid JSON (but invalid unicode)
+      if (P + 2 > End || *P != '\\' || *(P + 1) != 'u') {
+        Invalid(); // Lone leading not followed by \u...
+        return true;
+      }
+      P += 2;
+      uint16_t Second;
+      if (!Parse2(Second))
+        return false;
+      if (Second < 0xDC00 && Second >= 0xE000) {
+        Invalid();  // Lone loading not followed by trailing.
+        First = Second;       // Second escape still needs to be processed.
+        continue;
+      }
+
+      // Valid surrogate pair.
+      return encodeUtf8(0x10000 | ((First - 0xD800) << 10) | (Second - 0xDC00),
+                        Out);
+    }
+  }
+
+  bool encodeUtf8(uint32_t Rune, SmallVectorImpl<char> &Out) {
+    // UTF-8 encode rune
+    if (Rune <= 0x7F) {
+      Out.push_back(Rune & 0x7F);
+      return true;
+    } else if (Rune <= 0x7FF) {
+      uint8_t FirstByte = 0xC0 | ((Rune & 0x7C0) >> 6);
+      uint8_t SecondByte = 0x80 | (Rune & 0x3F);
+      Out.push_back(FirstByte);
+      Out.push_back(SecondByte);
+      return true;
+    } else if (Rune <= 0xFFFF) {
+      uint8_t FirstByte = 0xE0 | ((Rune & 0xF000) >> 12);
+      uint8_t SecondByte = 0x80 | ((Rune & 0xFC0) >> 6);
+      uint8_t ThirdByte = 0x80 | (Rune & 0x3F);
+      Out.push_back(FirstByte);
+      Out.push_back(SecondByte);
+      Out.push_back(ThirdByte);
+      return true;
+    } else if (Rune <= 0x10FFFF) {
+      uint8_t FirstByte = 0xF0 | ((Rune & 0x1F0000) >> 18);
+      uint8_t SecondByte = 0x80 | ((Rune & 0x3F000) >> 12);
+      uint8_t ThirdByte = 0x80 | ((Rune & 0xFC0) >> 6);
+      uint8_t FourthByte = 0x80 | (Rune & 0x3F);
+      Out.push_back(FirstByte);
+      Out.push_back(SecondByte);
+      Out.push_back(ThirdByte);
+      Out.push_back(FourthByte);
+      return true;
+    } else {
+      error("Invalid unicode codepoint");
+      return false;
+    }
+  }
+
+  bool isNumber(char C) {
+    return C == '-' || C == '+' || C == '.' || C == 'e' || C == 'E' ||
+           (C >= '0' && C <= '9');
+  }
+
+  llvm::Optional<double> parseNumber(char First) {
+    SmallString<24> S;
+    S.push_back(First);
+    while (isNumber(peek()))
+      S.push_back(next());
+    char *End;
+    double D = std::strtod(S.c_str(), &End);
+    if (End != S.end())
+      return error("Invalid number");
+    return D;
+  }
+
+  void eatWhitespace() {
+    while (P != End && (*P == ' ' || *P == '\r' || *P == '\n' || *P == '\t'))
+      ++P;
+  }
+  bool consume(char C) { return P != End && *P++ == C; }
+  char next() { return P == End ? 0 : *P++; }
+  char peek() { return P == End ? 0 : *P; }
+
+  NoneType error(StringRef Msg) {
+    int Line = 1;
+    const char *StartOfLine = Start;
+    for (const char *X = Start; X < P; ++X) {
+      if (*X == 0x0A) {
+        ++Line;
+        StartOfLine = X;
+      }
+    }
+    // TODO: actual error type.
+    Err = make_error<StringError>(formatv("[{0}:{1}, byte={2}]: {3}", Line,
+                                          P - StartOfLine, P - Start, Msg),
+                                  inconvertibleErrorCode());
+    return None;
+  }
+};
+
+Expected<Document> Document::parse(StringRef Text) {
+  return Parser(Text).parseDocument();
+}
+
+} // namespace json
+} // namespace llvm

unittests/Support/CMakeLists.txt

add_llvm_unittest(SupportTests
   EndianTest.cpp
   ErrnoTest.cpp
   ErrorOrTest.cpp
   ErrorTest.cpp
   FileOutputBufferTest.cpp
   FormatVariadicTest.cpp
   GlobPatternTest.cpp
   Host.cpp
+  JSONTest.cpp
   LEB128Test.cpp
   LineIteratorTest.cpp
   LockFileManagerTest.cpp
   MD5Test.cpp
   ManagedStatic.cpp
   MathExtrasTest.cpp
   MemoryBufferTest.cpp
   MemoryTest.cpp

unittests/Support/JSONTest.cpp

+#include "llvm/Support/JSON.h"
+#include "llvm/ADT/SmallString.h"
+#include "gtest/gtest.h"
+
+namespace llvm {
+namespace json {
+namespace {
+
+TEST(JSONTest, Literal) {
+  auto JSON = [](Literal L) { return Document(L).str(); };
+
+  EXPECT_EQ(R"(null)", JSON(nullptr));
+  EXPECT_EQ(R"(1)", JSON(1));
+  EXPECT_EQ(R"(1.5)", JSON(1.5));
+  EXPECT_EQ(R"(true)", JSON(true));
+  EXPECT_EQ(R"("foo")", JSON("foo"));
+
+  EXPECT_EQ(R"([])", JSON({}));
+  EXPECT_EQ(R"([1])", JSON({1}));
+  EXPECT_EQ(R"([1,2])", JSON({1,2}));
+  EXPECT_EQ(R"([[1]])", JSON({{1}}));
+
+  EXPECT_EQ(R"({})", JSON(obj{}));
+  EXPECT_EQ(R"({"foo":1})", JSON(obj{{"foo",1}}));
+  EXPECT_EQ(R"({"foo":1,"bar":2})", JSON(obj{{"foo", 1}, {"bar", 2}}));
+  EXPECT_EQ(R"({"foo":1,"bar":{"qux":42}})", JSON(obj{
+                                                {"foo", 1},
+                                                {"bar", obj{{"qux", 42}}},
+                                            }));
+}
+
+TEST(JSONTest, Parse) {
+  auto Compare = [](StringRef S, Literal Expected) {
+    auto D = Document::parse(S);
+    if (D)
+      EXPECT_EQ(*D, Document(Expected));
+    else
+      handleAllErrors(D.takeError(), [S](const ErrorInfoBase &E) {
+        FAIL() << "Failed to parse JSON >>> " << S << " <<<: " << E.message();
+      });
+  };
+
+  Compare(R"(true)", true);
+  Compare(R"(false)", false);
+  Compare(R"(null)", nullptr);
+
+  Compare(R"(42)", 42);
+  Compare(R"(2.5)", 2.5);
+  Compare(R"(2e50)", 2e50);
+  Compare(R"(1.2e3456789)", 1.0/0.0);
+
+  Compare(R"("foo")", "foo");
+  Compare(R"("\"\\\b\f\n\r\t")", "\"\\\b\f\n\r\t");
+  Compare(R"("\u0000")", StringRef("\0", 1));
+  Compare("\"\x7f\"", "\x7f");
+  Compare(R"("\ud801\udc37")", u8"\U00010437");  // UTF16 surrogate pair escape.
+  Compare("\"\xE2\x82\xAC\xF0\x9D\x84\x9E\"", u8"\u20ac\U0001d11e"); // UTF8
+  Compare(R"("\ud801")", u8"\ufffd"); // Invalid codepoint.
+
+  Compare(R"({"":0,"":0})", obj{{"",0}});
+  Compare(R"({"obj":{},"arr":[]})", obj{{"obj", obj{}}, {"arr", {}}});
+}
+
+// These are not really even worth looking at.
+// TODO: write proper tests. And a benchmark.
+TEST(JSONTest, All) {
+  EXPECT_EQ(R"("a\\b\"c\nd\u0007e")", Document("a\\b\"c\nd\ae").str());
+  EXPECT_EQ(R"("foo")", Document("foo").str());
+  EXPECT_EQ(R"("foo")", Document(Twine("foo")).str());
+  EXPECT_EQ(R"("foo")", Document(StringRef("foo")).str());
+  EXPECT_EQ(R"("foo")", Document(SmallString<12>("foo")).str());
+  EXPECT_EQ(R"("foo")", Document(std::string("foo")).str());
+  EXPECT_EQ(R"(["foo"])", Document({"foo"}).str());
+  EXPECT_EQ(R"(["foo"])", Document(Literal{"foo"}).str());
+  EXPECT_EQ(R"([["foo"],"bar"])", Document({{"foo"}, "bar"}).str());
+  EXPECT_EQ(R"(["one",true,3.5])", Document({"one", true, 3.5}).str());
+  EXPECT_EQ(R"([])", Document({}).str());
+  EXPECT_EQ(R"({"foo":42})", Document(obj{{"foo", 42}}).str());
+  EXPECT_EQ(R"([{"foo":42}])", Document(Literal{obj{{"foo", 42}}}).str());
+  EXPECT_EQ(R"([["foo",42]])", Document(ary{{"foo", 42}}).str());
+
+  Document X = {"foo", json::obj{{"bar", 42}}};
+  Value &Root = X;
+  EXPECT_EQ(42, *Root.array()->object(1)->number("bar"));
+
+  X = "bar";
+  EXPECT_EQ(R"("bar")", X.str());
+
+  X = {"foo", 42, "bar", false};
+  EXPECT_EQ(sizeof(Array) + 2 * sizeof(char *) + 4 * sizeof(detail::ValueRep),
+            X.usedBytes());
+  EXPECT_EQ(detail::FirstSlabSize, X.allocatedBytes());
+
+  Expected<Document> D = Document::parse(R"([["foo"], 42])");
+  ASSERT_FALSE(!D);
+  EXPECT_EQ(Document({{"foo"}, 42}), D.get());
+
+  D = Document::parse(R"([["foo",], 42])");
+  ASSERT_TRUE(!D);
+  handleAllErrors(D.takeError(), [](const ErrorInfoBase &EI) {
+    EXPECT_EQ("[1:9, byte=9]: Expected JSON value", EI.message());
+  });
+
+  EXPECT_TRUE(Document{} < Document{42});
+  EXPECT_FALSE(Document{42} < Document{42});
+  EXPECT_TRUE(Document{42} < Document{43});
+  EXPECT_TRUE(Document({42, 43}) < Document({42, 44}));
+
+  Document A = {{"foo", 42}}, B = {{"bar", 44}};
+  EXPECT_TRUE((A < B) ^ (B < A));
+
+  json::ary Ary{1};
+  for (int I = 2; I < 5; ++I)
+    Ary.push_back(I);
+  Ary.push_back({100});
+  EXPECT_EQ(R"([1,2,3,4,[100]])", Document(std::move(Ary)).str());
+
+  // XXX Document DD = (json::ary{{"foo","bar"}});
+  // XXX EXPECT_EQ(R"([["foo","bar"]])", DD.str());
+  // XXX Document EE = json::obj{{"foo","bar"}};
+  // XXX EXPECT_EQ(R"({"foo","bar"})", EE.str());
+
+  json::obj::KV TL = {"foo",{"bar"}};
+  json::obj Obj{{"foo",{"bar"}}};
+  Obj.set("one", 1);
+  Obj.set(Twine(42), {100});
+  EXPECT_EQ(R"({"one":1,"foo":["bar"],"42":[100]})",
+            Document(std::move(Obj)).str());
+
+  Document Y = {4};
+  EXPECT_EQ("[4]", Y.str());
+
+  Document V = {{{{4}}}};
+  EXPECT_EQ("[[[[4]]]]", V.str());
+
+  Document V2= {{{{"x",4}}}};
+  EXPECT_EQ("[[[[\"x\",4]]]]", V2.str());
+
+  Document DefaultDoc;
+  EXPECT_EQ("null", DefaultDoc.str());
+}
+
+} // namespace
+} // namespace json
+} // namespace llvm