1 //===--- JSONParser.cpp - Simple JSON parser ------------------------------===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This file implements a JSON parser.
12 //===----------------------------------------------------------------------===//
14 #include "llvm/Support/JSONParser.h"
16 #include "llvm/ADT/Twine.h"
17 #include "llvm/Support/Casting.h"
18 #include "llvm/Support/MemoryBuffer.h"
22 JSONParser::JSONParser(StringRef Input, SourceMgr *SM)
23 : SM(SM), Failed(false) {
24 InputBuffer = MemoryBuffer::getMemBuffer(Input, "JSON");
25 SM->AddNewSourceBuffer(InputBuffer, SMLoc());
26 End = InputBuffer->getBuffer().end();
27 Position = InputBuffer->getBuffer().begin();
30 JSONValue *JSONParser::parseRoot() {
31 if (Position != InputBuffer->getBuffer().begin())
32 report_fatal_error("Cannot reuse JSONParser.");
35 if (errorIfAtEndOfFile("'[' or '{' at start of JSON text"))
39 return new (ValueAllocator.Allocate<JSONArray>(1)) JSONArray(this);
41 return new (ValueAllocator.Allocate<JSONObject>(1)) JSONObject(this);
43 setExpectedError("'[' or '{' at start of JSON text", *Position);
48 bool JSONParser::validate() {
49 JSONValue *Root = parseRoot();
56 bool JSONParser::skip(const JSONAtom &Atom) {
57 switch(Atom.getKind()) {
58 case JSONAtom::JK_Array:
59 case JSONAtom::JK_Object:
60 return skipContainer(*cast<JSONContainer>(&Atom));
61 case JSONAtom::JK_String:
63 case JSONAtom::JK_KeyValuePair:
64 return skip(*cast<JSONKeyValuePair>(&Atom)->Value);
66 llvm_unreachable("Impossible enum value.");
69 // Sets the current error to:
70 // "expected <Expected>, but found <Found>".
71 void JSONParser::setExpectedError(StringRef Expected, StringRef Found) {
72 SM->PrintMessage(SMLoc::getFromPointer(Position), SourceMgr::DK_Error,
73 "expected " + Expected + ", but found " + Found + ".", ArrayRef<SMRange>());
77 // Sets the current error to:
78 // "expected <Expected>, but found <Found>".
79 void JSONParser::setExpectedError(StringRef Expected, char Found) {
80 setExpectedError(Expected, ("'" + StringRef(&Found, 1) + "'").str());
83 // If there is no character available, returns true and sets the current error
84 // to: "expected <Expected>, but found EOF.".
85 bool JSONParser::errorIfAtEndOfFile(StringRef Expected) {
86 if (Position == End) {
87 setExpectedError(Expected, "EOF");
93 // Sets the current error if the current character is not C to:
94 // "expected 'C', but got <current character>".
95 bool JSONParser::errorIfNotAt(char C, StringRef Message) {
97 std::string Expected =
98 ("'" + StringRef(&C, 1) + "' " + Message).str();
100 setExpectedError(Expected, "EOF");
102 setExpectedError(Expected, *Position);
108 // Forbidding inlining improves performance by roughly 20%.
109 // FIXME: Remove once llvm optimizes this to the faster version without hints.
110 LLVM_ATTRIBUTE_NOINLINE static bool
111 wasEscaped(StringRef::iterator First, StringRef::iterator Position);
113 // Returns whether a character at 'Position' was escaped with a leading '\'.
114 // 'First' specifies the position of the first character in the string.
115 static bool wasEscaped(StringRef::iterator First,
116 StringRef::iterator Position) {
117 assert(Position - 1 >= First);
118 StringRef::iterator I = Position - 1;
119 // We calulate the number of consecutive '\'s before the current position
120 // by iterating backwards through our string.
121 while (I >= First && *I == '\\') --I;
122 // (Position - 1 - I) now contains the number of '\'s before the current
123 // position. If it is odd, the character at 'Positon' was escaped.
124 return (Position - 1 - I) % 2 == 1;
127 // Parses a JSONString, assuming that the current position is on a quote.
128 JSONString *JSONParser::parseString() {
129 assert(Position != End);
130 assert(!isWhitespace());
131 if (errorIfNotAt('"', "at start of string"))
133 StringRef::iterator First = Position + 1;
135 // Benchmarking shows that this loop is the hot path of the application with
136 // about 2/3rd of the runtime cycles. Since escaped quotes are not the common
137 // case, and multiple escaped backslashes before escaped quotes are very rare,
138 // we pessimize this case to achieve a smaller inner loop in the common case.
139 // We're doing that by having a quick inner loop that just scans for the next
140 // quote. Once we find the quote we check the last character to see whether
141 // the quote might have been escaped. If the last character is not a '\', we
142 // know the quote was not escaped and have thus found the end of the string.
143 // If the immediately preceding character was a '\', we have to scan backwards
144 // to see whether the previous character was actually an escaped backslash, or
145 // an escape character for the quote. If we find that the current quote was
146 // escaped, we continue parsing for the next quote and repeat.
147 // This optimization brings around 30% performance improvements.
149 // Step over the current quote.
151 // Find the next quote.
152 while (Position != End && *Position != '"')
154 if (errorIfAtEndOfFile("'\"' at end of string"))
156 // Repeat until the previous character was not a '\' or was an escaped
158 } while (*(Position - 1) == '\\' && wasEscaped(First, Position));
160 return new (ValueAllocator.Allocate<JSONString>())
161 JSONString(StringRef(First, Position - First));
165 // Advances the position to the next non-whitespace position.
166 void JSONParser::nextNonWhitespace() {
169 } while (isWhitespace());
172 // Checks if there is a whitespace character at the current position.
173 bool JSONParser::isWhitespace() {
174 return *Position == ' ' || *Position == '\t' ||
175 *Position == '\n' || *Position == '\r';
178 bool JSONParser::failed() const {
182 // Parses a JSONValue, assuming that the current position is at the first
183 // character of the value.
184 JSONValue *JSONParser::parseValue() {
185 assert(Position != End);
186 assert(!isWhitespace());
189 return new (ValueAllocator.Allocate<JSONArray>(1)) JSONArray(this);
191 return new (ValueAllocator.Allocate<JSONObject>(1)) JSONObject(this);
193 return parseString();
195 setExpectedError("'[', '{' or '\"' at start of value", *Position);
200 // Parses a JSONKeyValuePair, assuming that the current position is at the first
201 // character of the key, value pair.
202 JSONKeyValuePair *JSONParser::parseKeyValuePair() {
203 assert(Position != End);
204 assert(!isWhitespace());
206 JSONString *Key = parseString();
211 if (errorIfNotAt(':', "between key and value"))
215 const JSONValue *Value = parseValue();
219 return new (ValueAllocator.Allocate<JSONKeyValuePair>(1))
220 JSONKeyValuePair(Key, Value);
223 /// \brief Parses the first element of a JSON array or object, or closes the
226 /// The method assumes that the current position is before the first character
227 /// of the element, with possible white space in between. When successful, it
228 /// returns the new position after parsing the element. Otherwise, if there is
229 /// no next value, it returns a default constructed StringRef::iterator.
230 StringRef::iterator JSONParser::parseFirstElement(JSONAtom::Kind ContainerKind,
231 char StartChar, char EndChar,
232 const JSONAtom *&Element) {
233 assert(*Position == StartChar);
236 if (errorIfAtEndOfFile("value or end of container at start of container"))
237 return StringRef::iterator();
239 if (*Position == EndChar)
240 return StringRef::iterator();
242 Element = parseElement(ContainerKind);
244 return StringRef::iterator();
249 /// \brief Parses the next element of a JSON array or object, or closes the
252 /// The method assumes that the current position is before the ',' which
253 /// separates the next element from the current element. When successful, it
254 /// returns the new position after parsing the element. Otherwise, if there is
255 /// no next value, it returns a default constructed StringRef::iterator.
256 StringRef::iterator JSONParser::parseNextElement(JSONAtom::Kind ContainerKind,
258 const JSONAtom *&Element) {
261 if (errorIfAtEndOfFile("',' or end of container for next element"))
264 if (*Position == ',') {
266 if (errorIfAtEndOfFile("element in container"))
267 return StringRef::iterator();
269 Element = parseElement(ContainerKind);
271 return StringRef::iterator();
274 } else if (*Position == EndChar) {
275 return StringRef::iterator();
277 setExpectedError("',' or end of container for next element", *Position);
278 return StringRef::iterator();
282 const JSONAtom *JSONParser::parseElement(JSONAtom::Kind ContainerKind) {
283 switch (ContainerKind) {
284 case JSONAtom::JK_Array:
286 case JSONAtom::JK_Object:
287 return parseKeyValuePair();
289 llvm_unreachable("Impossible code path");
293 bool JSONParser::skipContainer(const JSONContainer &Container) {
294 for (JSONContainer::AtomIterator I = Container.atom_current(),
295 E = Container.atom_end();