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