include/llvm/Support/JSONParser.h

   1 //===--- JsonParser.h - Simple JSON parser ----------------------*- C++ -*-===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 //  This file implements a JSON parser.
  11 //
  12 //  See http://www.json.org/ for an overview.
  13 //  See http://www.ietf.org/rfc/rfc4627.txt for the full standard.
  14 //
  15 //  FIXME: Currently this supports a subset of JSON. Specifically, support
  16 //  for numbers, booleans and null for values is missing.
  17 //
  18 //===----------------------------------------------------------------------===//
  19
  20 #ifndef LLVM_CLANG_TOOLING_JSON_PARSER_H
  21 #define LLVM_CLANG_TOOLING_JSON_PARSER_H
  22
  23 #include "llvm/ADT/StringRef.h"
  24 #include "llvm/Support/Allocator.h"
  25 #include "llvm/Support/ErrorHandling.h"
  26
  27 #include <string>
  28
  29 namespace llvm {
  30
  31 class JSONString;
  32 class JSONValue;
  33 class JSONKeyValuePair;
  34
  35 /// \brief Base class for a parsable JSON atom.
  36 ///
  37 /// This class has no semantics other than being a unit of JSON data which can
  38 /// be parsed out of a JSON document.
  39 class JSONAtom {
  40 public:
  41   /// \brief Possible types of JSON objects.
  42   enum Kind { JK_KeyValuePair, JK_Array, JK_Object, JK_String };
  43
  44   /// \brief Returns the type of this value.
  45   Kind getKind() const { return MyKind; }
  46
  47   static bool classof(const JSONAtom *Atom) { return true; }
  48
  49 protected:
  50   JSONAtom(Kind MyKind) : MyKind(MyKind) {}
  51
  52 private:
  53   /// \brief Parses to the end of the object and returns whether parsing
  54   /// was successful.
  55   bool skip() const;
  56
  57   Kind MyKind;
  58
  59   friend class JSONParser;
  60   friend class JSONKeyValuePair;
  61   template <typename, char, char, JSONAtom::Kind> friend class JSONContainer;
  62 };
  63
  64 /// \brief A parser for JSON text.
  65 ///
  66 /// Use an object of JSONParser to iterate over the values of a JSON text.
  67 /// All objects are parsed during the iteration, so you can only iterate once
  68 /// over the JSON text, but the cost of partial iteration is minimized.
  69 /// Create a new JSONParser if you want to iterate multiple times.
  70 class JSONParser {
  71 public:
  72   /// \brief Create a JSONParser for the given input.
  73   ///
  74   /// Parsing is started via parseRoot(). Access to the object returned from
  75   /// parseRoot() will parse the input lazily.
  76   JSONParser(StringRef Input);
  77
  78   /// \brief Returns the outermost JSON value (either an array or an object).
  79   ///
  80   /// Can return NULL if the input does not start with an array or an object.
  81   /// The object is not parsed yet - the caller must either iterate over the
  82   /// returned object or call 'skip' to trigger parsing.
  83   ///
  84   /// A JSONValue can be either a JSONString, JSONObject or JSONArray.
  85   JSONValue *parseRoot();
  86
  87   /// \brief Parses the JSON text and returns whether it is valid JSON.
  88   ///
  89   /// In case validate() return false, failed() will return true and
  90   /// getErrorMessage() will return the parsing error.
  91   bool validate();
  92
  93   /// \brief Returns true if an error occurs during parsing.
  94   ///
  95   /// If there was an error while parsing an object that was created by
  96   /// iterating over the result of 'parseRoot', 'failed' will return true.
  97   bool failed() const;
  98
  99   /// \brief Returns an error message when 'failed' returns true.
 100   std::string getErrorMessage() const;
 101
 102 private:
 103   /// \brief These methods manage the implementation details of parsing new JSON
 104   /// atoms.
 105   /// @{
 106   JSONString *parseString();
 107   JSONValue *parseValue();
 108   JSONKeyValuePair *parseKeyValuePair();
 109   /// @}
 110
 111   /// \brief Templated helpers to parse the elements out of both forms of JSON
 112   /// containers.
 113   /// @{
 114   template <typename AtomT> AtomT *parseElement();
 115   template <typename AtomT, char StartChar, char EndChar>
 116   StringRef::iterator parseFirstElement(const AtomT *&Element);
 117   template <typename AtomT, char EndChar>
 118   StringRef::iterator parseNextElement(const AtomT *&Element);
 119   /// @}
 120
 121   /// \brief Whitespace parsing.
 122   /// @{
 123   void nextNonWhitespace();
 124   bool isWhitespace();
 125   /// @}
 126
 127   /// \brief These methods are used for error handling.
 128   /// {
 129   void setExpectedError(StringRef Expected, StringRef Found);
 130   void setExpectedError(StringRef Expected, char Found);
 131   bool errorIfAtEndOfFile(StringRef Message);
 132   bool errorIfNotAt(char C, StringRef Message);
 133   /// }
 134
 135   /// All nodes are allocated by the parser and will be deallocated when the
 136   /// parser is destroyed.
 137   BumpPtrAllocator ValueAllocator;
 138
 139   /// \brief The original input to the parser.
 140   const StringRef Input;
 141
 142   /// \brief The current position in the parse stream.
 143   StringRef::iterator Position;
 144
 145   /// \brief If non-empty, an error has occurred.
 146   std::string ErrorMessage;
 147
 148   template <typename AtomT, char StartChar, char EndChar,
 149             JSONAtom::Kind ContainerKind>
 150   friend class JSONContainer;
 151 };
 152
 153
 154 /// \brief Base class for JSON value objects.
 155 ///
 156 /// This object represents an abstract JSON value. It is the root node behind
 157 /// the group of JSON entities that can represent top-level values in a JSON
 158 /// document. It has no API, and is just a placeholder in the type hierarchy of
 159 /// nodes.
 160 class JSONValue : public JSONAtom {
 161 protected:
 162   JSONValue(Kind MyKind) : JSONAtom(MyKind) {}
 163
 164 public:
 165   /// \brief dyn_cast helpers
 166   ///@{
 167   static bool classof(const JSONAtom *Atom) {
 168     switch (Atom->getKind()) {
 169       case JK_Array:
 170       case JK_Object:
 171       case JK_String:
 172         return true;
 173       case JK_KeyValuePair:
 174         return false;
 175     };
 176     llvm_unreachable("Invalid JSONAtom kind");
 177   }
 178   static bool classof(const JSONValue *Value) { return true; }
 179   ///@}
 180 };
 181
 182 /// \brief Gives access to the text of a JSON string.
 183 ///
 184 /// FIXME: Implement a method to return the unescaped text.
 185 class JSONString : public JSONValue {
 186 public:
 187   /// \brief Returns the underlying parsed text of the string.
 188   ///
 189   /// This is the unescaped content of the JSON text.
 190   /// See http://www.ietf.org/rfc/rfc4627.txt for details.
 191   StringRef getRawText() const { return RawText; };
 192
 193 private:
 194   JSONString(StringRef RawText) : JSONValue(JK_String), RawText(RawText) {}
 195
 196   /// \brief Skips to the next position in the parse stream.
 197   bool skip() const { return true; };
 198
 199   StringRef RawText;
 200
 201   friend class JSONAtom;
 202   friend class JSONParser;
 203
 204 public:
 205   /// \brief dyn_cast helpers
 206   ///@{
 207   static bool classof(const JSONAtom *Atom) {
 208     return Atom->getKind() == JK_String;
 209   }
 210   static bool classof(const JSONString *String) { return true; }
 211   ///@}
 212 };
 213
 214 /// \brief A (key, value) tuple of type (JSONString *, JSONValue *).
 215 ///
 216 /// Note that JSONKeyValuePair is not a JSONValue, it is a bare JSONAtom.
 217 /// JSONKeyValuePairs can be elements of a JSONObject, but not of a JSONArray.
 218 /// They are not viable as top-level values either.
 219 class JSONKeyValuePair : public JSONAtom {
 220 public:
 221   const JSONString * const Key;
 222   const JSONValue * const Value;
 223
 224 private:
 225   JSONKeyValuePair(const JSONString *Key, const JSONValue *Value)
 226       : JSONAtom(JK_KeyValuePair), Key(Key), Value(Value) {}
 227
 228   /// \brief Skips to the next position in the parse stream.
 229   bool skip() const { return Value->skip(); };
 230
 231   friend class JSONAtom;
 232   friend class JSONParser;
 233   template <typename, char, char, JSONAtom::Kind> friend class JSONContainer;
 234
 235 public:
 236   /// \brief dyn_cast helpers
 237   ///@{
 238   static bool classof(const JSONAtom *Atom) {
 239     return Atom->getKind() == JK_KeyValuePair;
 240   }
 241   static bool classof(const JSONKeyValuePair *KeyValuePair) { return true; }
 242   ///@}
 243 };
 244
 245 /// \brief Implementation of JSON containers (arrays and objects).
 246 ///
 247 /// JSONContainers drive the lazy parsing of JSON arrays and objects via
 248 /// forward iterators. Call 'skip' to validate parsing of all elements of the
 249 /// container and to position the parse stream behind the container.
 250 template <typename AtomT, char StartChar, char EndChar,
 251           JSONAtom::Kind ContainerKind>
 252 class JSONContainer : public JSONValue {
 253 public:
 254   /// \brief An iterator that parses the underlying container during iteration.
 255   ///
 256   /// Iterators on the same collection use shared state, so when multiple copies
 257   /// of an iterator exist, only one is allowed to be used for iteration;
 258   /// iterating multiple copies of an iterator of the same collection will lead
 259   /// to undefined behavior.
 260   class const_iterator : public std::iterator<std::forward_iterator_tag,
 261                                               const AtomT*> {
 262   public:
 263     const_iterator(const const_iterator &I) : Container(I.Container) {}
 264
 265     bool operator==(const const_iterator &I) const {
 266       if (isEnd() || I.isEnd())
 267         return isEnd() == I.isEnd();
 268       return Container->Position == I.Container->Position;
 269     }
 270     bool operator!=(const const_iterator &I) const { return !(*this == I); }
 271
 272     const_iterator &operator++() {
 273       Container->parseNextElement();
 274       return *this;
 275     }
 276
 277     const AtomT *operator*() { return Container->Current; }
 278
 279   private:
 280     /// \brief Create an iterator for which 'isEnd' returns true.
 281     const_iterator() : Container(0) {}
 282
 283     /// \brief Create an iterator for the given container.
 284     const_iterator(const JSONContainer *Container) : Container(Container) {}
 285
 286     bool isEnd() const {
 287       return Container == 0 || Container->Position == StringRef::iterator();
 288     }
 289
 290     const JSONContainer * const Container;
 291
 292     friend class JSONContainer;
 293   };
 294
 295   /// \brief Returns a lazy parsing iterator over the container.
 296   ///
 297   /// As the iterator drives the parse stream, begin() must only be called
 298   /// once per container.
 299   const_iterator begin() const {
 300     if (Started)
 301       report_fatal_error("Cannot parse container twice.");
 302     Started = true;
 303     // Set up the position and current element when we begin iterating over the
 304     // container.
 305     Position = Parser->parseFirstElement<AtomT, StartChar, EndChar>(Current);
 306     return const_iterator(this);
 307   }
 308
 309   const_iterator end() const {
 310     return const_iterator();
 311   }
 312
 313 private:
 314   JSONContainer(JSONParser *Parser)
 315     : JSONValue(ContainerKind), Parser(Parser),
 316       Position(), Current(0), Started(false) {}
 317
 318   const_iterator current() const {
 319     if (!Started)
 320       return begin();
 321
 322     return const_iterator(this);
 323   }
 324
 325   /// \brief Skips to the next position in the parse stream.
 326   bool skip() const {
 327     for (const_iterator I = current(), E = end(); I != E; ++I) {
 328       assert(*I != 0);
 329       if (!(*I)->skip())
 330         return false;
 331     }
 332     return !Parser->failed();
 333   }
 334
 335   /// \brief Parse the next element in the container into the Current element.
 336   ///
 337   /// This routine is called as an iterator into this container walks through
 338   /// its elements. It mutates the container's internal current node to point to
 339   /// the next atom of the container.
 340   void parseNextElement() const {
 341     Current->skip();
 342     Position = Parser->parseNextElement<AtomT, EndChar>(Current);
 343   }
 344
 345   // For parsing, JSONContainers call back into the JSONParser.
 346   JSONParser * const Parser;
 347
 348   // 'Position', 'Current' and 'Started' store the state of the parse stream
 349   // for iterators on the container, they don't change the container's elements
 350   // and are thus marked as mutable.
 351   mutable StringRef::iterator Position;
 352   mutable const AtomT *Current;
 353   mutable bool Started;
 354
 355   friend class JSONAtom;
 356   friend class JSONParser;
 357   friend class const_iterator;
 358
 359 public:
 360   /// \brief dyn_cast helpers
 361   ///@{
 362   static bool classof(const JSONAtom *Atom) {
 363     return Atom->getKind() == ContainerKind;
 364   }
 365   static bool classof(const JSONContainer *Container) { return true; }
 366   ///@}
 367 };
 368
 369 /// \brief A simple JSON array.
 370 typedef JSONContainer<JSONValue, '[', ']', JSONAtom::JK_Array> JSONArray;
 371
 372 /// \brief A JSON object: an iterable list of JSON key-value pairs.
 373 typedef JSONContainer<JSONKeyValuePair, '{', '}', JSONAtom::JK_Object>
 374     JSONObject;
 375
 376 /// \brief Template adaptor to dispatch element parsing for values.
 377 template <> JSONValue *JSONParser::parseElement();
 378
 379 /// \brief Template adaptor to dispatch element parsing for key value pairs.
 380 template <> JSONKeyValuePair *JSONParser::parseElement();
 381
 382 /// \brief Parses the first element of a JSON array or object, or closes the
 383 /// array.
 384 ///
 385 /// The method assumes that the current position is before the first character
 386 /// of the element, with possible white space in between. When successful, it
 387 /// returns the new position after parsing the element. Otherwise, if there is
 388 /// no next value, it returns a default constructed StringRef::iterator.
 389 template <typename AtomT, char StartChar, char EndChar>
 390 StringRef::iterator JSONParser::parseFirstElement(const AtomT *&Element) {
 391   assert(*Position == StartChar);
 392   Element = 0;
 393   nextNonWhitespace();
 394   if (errorIfAtEndOfFile("value or end of container at start of container"))
 395     return StringRef::iterator();
 396
 397   if (*Position == EndChar)
 398     return StringRef::iterator();
 399
 400   Element = parseElement<AtomT>();
 401   if (Element == 0)
 402     return StringRef::iterator();
 403
 404   return Position;
 405 }
 406
 407 /// \brief Parses the next element of a JSON array or object, or closes the
 408 /// array.
 409 ///
 410 /// The method assumes that the current position is before the ',' which
 411 /// separates the next element from the current element. When successful, it
 412 /// returns the new position after parsing the element. Otherwise, if there is
 413 /// no next value, it returns a default constructed StringRef::iterator.
 414 template <typename AtomT, char EndChar>
 415 StringRef::iterator JSONParser::parseNextElement(const AtomT *&Element) {
 416   Element = 0;
 417   nextNonWhitespace();
 418   if (errorIfAtEndOfFile("',' or end of container for next element"))
 419     return 0;
 420
 421   switch (*Position) {
 422     case ',':
 423       nextNonWhitespace();
 424       if (errorIfAtEndOfFile("element in container"))
 425         return StringRef::iterator();
 426
 427       Element = parseElement<AtomT>();
 428       if (Element == 0)
 429         return StringRef::iterator();
 430
 431       return Position;
 432
 433     case EndChar:
 434       return StringRef::iterator();
 435
 436     default:
 437       setExpectedError("',' or end of container for next element", *Position);
 438       return StringRef::iterator();
 439   }
 440 }
 441
 442 } // end namespace llvm
 443
 444 #endif // LLVM_CLANG_TOOLING_JSON_PARSER_H