include/llvm/Support/YAMLParser.h

   1 //===--- YAMLParser.h - Simple YAML parser --------------------------------===//
   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 is a YAML 1.2 parser.
  11 //
  12 //  See http://www.yaml.org/spec/1.2/spec.html for the full standard.
  13 //
  14 //  This currently does not implement the following:
  15 //    * Multi-line literal folding.
  16 //    * Tag resolution.
  17 //    * UTF-16.
  18 //    * BOMs anywhere other than the first Unicode scalar value in the file.
  19 //
  20 //  The most important class here is Stream. This represents a YAML stream with
  21 //  0, 1, or many documents.
  22 //
  23 //  SourceMgr sm;
  24 //  StringRef input = getInput();
  25 //  yaml::Stream stream(input, sm);
  26 //
  27 //  for (yaml::document_iterator di = stream.begin(), de = stream.end();
  28 //       di != de; ++di) {
  29 //    yaml::Node *n = di->getRoot();
  30 //    if (n) {
  31 //      // Do something with n...
  32 //    } else
  33 //      break;
  34 //  }
  35 //
  36 //===----------------------------------------------------------------------===//
  37
  38 #ifndef LLVM_SUPPORT_YAML_PARSER_H
  39 #define LLVM_SUPPORT_YAML_PARSER_H
  40
  41 #include "llvm/ADT/OwningPtr.h"
  42 #include "llvm/ADT/SmallString.h"
  43 #include "llvm/ADT/StringRef.h"
  44 #include "llvm/Support/Allocator.h"
  45 #include "llvm/Support/SMLoc.h"
  46
  47 #include <limits>
  48 #include <utility>
  49
  50 namespace llvm {
  51 class MemoryBuffer;
  52 class SourceMgr;
  53 class raw_ostream;
  54 class Twine;
  55
  56 namespace yaml {
  57
  58 class document_iterator;
  59 class Document;
  60 class Node;
  61 class Scanner;
  62 struct Token;
  63
  64 /// @brief Dump all the tokens in this stream to OS.
  65 /// @returns true if there was an error, false otherwise.
  66 bool dumpTokens(StringRef Input, raw_ostream &);
  67
  68 /// @brief Scans all tokens in input without outputting anything. This is used
  69 ///        for benchmarking the tokenizer.
  70 /// @returns true if there was an error, false otherwise.
  71 bool scanTokens(StringRef Input);
  72
  73 /// @brief Escape \a Input for a double quoted scalar.
  74 std::string escape(StringRef Input);
  75
  76 /// @brief This class represents a YAML stream potentially containing multiple
  77 ///        documents.
  78 class Stream {
  79 public:
  80   Stream(StringRef Input, SourceMgr &);
  81   ~Stream();
  82
  83   document_iterator begin();
  84   document_iterator end();
  85   void skip();
  86   bool failed();
  87   bool validate() {
  88     skip();
  89     return !failed();
  90   }
  91
  92   void printError(Node *N, const Twine &Msg);
  93
  94 private:
  95   OwningPtr<Scanner> scanner;
  96   OwningPtr<Document> CurrentDoc;
  97
  98   friend class Document;
  99
 100   /// @brief Validate a %YAML x.x directive.
 101   void handleYAMLDirective(const Token &);
 102 };
 103
 104 /// @brief Abstract base class for all Nodes.
 105 class Node {
 106 public:
 107   enum NodeKind {
 108     NK_Null,
 109     NK_Scalar,
 110     NK_KeyValue,
 111     NK_Mapping,
 112     NK_Sequence,
 113     NK_Alias
 114   };
 115
 116   Node(unsigned int Type, OwningPtr<Document>&, StringRef Anchor);
 117
 118   /// @brief Get the value of the anchor attached to this node. If it does not
 119   ///        have one, getAnchor().size() will be 0.
 120   StringRef getAnchor() const { return Anchor; }
 121
 122   SMRange getSourceRange() const { return SourceRange; }
 123   void setSourceRange(SMRange SR) { SourceRange = SR; }
 124
 125   // These functions forward to Document and Scanner.
 126   Token &peekNext();
 127   Token getNext();
 128   Node *parseBlockNode();
 129   BumpPtrAllocator &getAllocator();
 130   void setError(const Twine &Message, Token &Location) const;
 131   bool failed() const;
 132
 133   virtual void skip() {}
 134
 135   unsigned int getType() const { return TypeID; }
 136
 137   void *operator new ( size_t Size
 138                      , BumpPtrAllocator &Alloc
 139                      , size_t Alignment = 16) throw() {
 140     return Alloc.Allocate(Size, Alignment);
 141   }
 142
 143   void operator delete(void *Ptr, BumpPtrAllocator &Alloc, size_t) throw() {
 144     Alloc.Deallocate(Ptr);
 145   }
 146
 147 protected:
 148   OwningPtr<Document> &Doc;
 149   SMRange SourceRange;
 150
 151   void operator delete(void *) throw() {}
 152
 153   virtual ~Node() {}
 154
 155 private:
 156   unsigned int TypeID;
 157   StringRef Anchor;
 158 };
 159
 160 /// @brief A null value.
 161 ///
 162 /// Example:
 163 ///   !!null null
 164 class NullNode : public Node {
 165 public:
 166   NullNode(OwningPtr<Document> &D) : Node(NK_Null, D, StringRef()) {}
 167
 168   static inline bool classof(const Node *N) {
 169     return N->getType() == NK_Null;
 170   }
 171 };
 172
 173 /// @brief A scalar node is an opaque datum that can be presented as a
 174 ///        series of zero or more Unicode scalar values.
 175 ///
 176 /// Example:
 177 ///   Adena
 178 class ScalarNode : public Node {
 179 public:
 180   ScalarNode(OwningPtr<Document> &D, StringRef Anchor, StringRef Val)
 181     : Node(NK_Scalar, D, Anchor)
 182     , Value(Val) {
 183     SMLoc Start = SMLoc::getFromPointer(Val.begin());
 184     SMLoc End = SMLoc::getFromPointer(Val.end() - 1);
 185     SourceRange = SMRange(Start, End);
 186   }
 187
 188   // Return Value without any escaping or folding or other fun YAML stuff. This
 189   // is the exact bytes that are contained in the file (after conversion to
 190   // utf8).
 191   StringRef getRawValue() const { return Value; }
 192
 193   /// @brief Gets the value of this node as a StringRef.
 194   ///
 195   /// @param Storage is used to store the content of the returned StringRef iff
 196   ///        it requires any modification from how it appeared in the source.
 197   ///        This happens with escaped characters and multi-line literals.
 198   StringRef getValue(SmallVectorImpl<char> &Storage) const;
 199
 200   static inline bool classof(const Node *N) {
 201     return N->getType() == NK_Scalar;
 202   }
 203
 204 private:
 205   StringRef Value;
 206
 207   StringRef unescapeDoubleQuoted( StringRef UnquotedValue
 208                                 , StringRef::size_type Start
 209                                 , SmallVectorImpl<char> &Storage) const;
 210 };
 211
 212 /// @brief A key and value pair. While not technically a Node under the YAML
 213 ///        representation graph, it is easier to treat them this way.
 214 ///
 215 /// TODO: Consider making this not a child of Node.
 216 ///
 217 /// Example:
 218 ///   Section: .text
 219 class KeyValueNode : public Node {
 220 public:
 221   KeyValueNode(OwningPtr<Document> &D)
 222     : Node(NK_KeyValue, D, StringRef())
 223     , Key(0)
 224     , Value(0)
 225   {}
 226
 227   /// @brief Parse and return the key.
 228   ///
 229   /// This may be called multiple times.
 230   ///
 231   /// @returns The key, or nullptr if failed() == true.
 232   Node *getKey();
 233
 234   /// @brief Parse and return the value.
 235   ///
 236   /// This may be called multiple times.
 237   ///
 238   /// @returns The value, or nullptr if failed() == true.
 239   Node *getValue();
 240
 241   virtual void skip() LLVM_OVERRIDE {
 242     getKey()->skip();
 243     getValue()->skip();
 244   }
 245
 246   static inline bool classof(const Node *N) {
 247     return N->getType() == NK_KeyValue;
 248   }
 249
 250 private:
 251   Node *Key;
 252   Node *Value;
 253 };
 254
 255 /// @brief This is an iterator abstraction over YAML collections shared by both
 256 ///        sequences and maps.
 257 ///
 258 /// BaseT must have a ValueT* member named CurrentEntry and a member function
 259 /// increment() which must set CurrentEntry to 0 to create an end iterator.
 260 template <class BaseT, class ValueT>
 261 class basic_collection_iterator
 262   : public std::iterator<std::forward_iterator_tag, ValueT> {
 263 public:
 264   basic_collection_iterator() : Base(0) {}
 265   basic_collection_iterator(BaseT *B) : Base(B) {}
 266
 267   ValueT *operator ->() const {
 268     assert(Base && Base->CurrentEntry && "Attempted to access end iterator!");
 269     return Base->CurrentEntry;
 270   }
 271
 272   ValueT &operator *() const {
 273     assert(Base && Base->CurrentEntry &&
 274            "Attempted to dereference end iterator!");
 275     return *Base->CurrentEntry;
 276   }
 277
 278   operator ValueT*() const {
 279     assert(Base && Base->CurrentEntry && "Attempted to access end iterator!");
 280     return Base->CurrentEntry;
 281   }
 282
 283   bool operator !=(const basic_collection_iterator &Other) const {
 284     if(Base != Other.Base)
 285       return true;
 286     return (Base && Other.Base) && Base->CurrentEntry
 287                                    != Other.Base->CurrentEntry;
 288   }
 289
 290   basic_collection_iterator &operator++() {
 291     assert(Base && "Attempted to advance iterator past end!");
 292     Base->increment();
 293     // Create an end iterator.
 294     if (Base->CurrentEntry == 0)
 295       Base = 0;
 296     return *this;
 297   }
 298
 299 private:
 300   BaseT *Base;
 301 };
 302
 303 // The following two templates are used for both MappingNode and Sequence Node.
 304 template <class CollectionType>
 305 typename CollectionType::iterator begin(CollectionType &C) {
 306   assert(C.IsAtBeginning && "You may only iterate over a collection once!");
 307   C.IsAtBeginning = false;
 308   typename CollectionType::iterator ret(&C);
 309   ++ret;
 310   return ret;
 311 }
 312
 313 template <class CollectionType>
 314 void skip(CollectionType &C) {
 315   // TODO: support skipping from the middle of a parsed collection ;/
 316   assert((C.IsAtBeginning || C.IsAtEnd) && "Cannot skip mid parse!");
 317   if (C.IsAtBeginning)
 318     for (typename CollectionType::iterator i = begin(C), e = C.end();
 319                                            i != e; ++i)
 320       i->skip();
 321 }
 322
 323 /// @brief Represents a YAML map created from either a block map for a flow map.
 324 ///
 325 /// This parses the YAML stream as increment() is called.
 326 ///
 327 /// Example:
 328 ///   Name: _main
 329 ///   Scope: Global
 330 class MappingNode : public Node {
 331 public:
 332   enum MappingType {
 333     MT_Block,
 334     MT_Flow,
 335     MT_Inline ///< An inline mapping node is used for "[key: value]".
 336   };
 337
 338   MappingNode(OwningPtr<Document> &D, StringRef Anchor, MappingType MT)
 339     : Node(NK_Mapping, D, Anchor)
 340     , Type(MT)
 341     , IsAtBeginning(true)
 342     , IsAtEnd(false)
 343     , CurrentEntry(0)
 344   {}
 345
 346   friend class basic_collection_iterator<MappingNode, KeyValueNode>;
 347   typedef basic_collection_iterator<MappingNode, KeyValueNode> iterator;
 348   template <class T> friend typename T::iterator yaml::begin(T &);
 349   template <class T> friend void yaml::skip(T &);
 350
 351   iterator begin() {
 352     return yaml::begin(*this);
 353   }
 354
 355   iterator end() { return iterator(); }
 356
 357   virtual void skip() LLVM_OVERRIDE {
 358     yaml::skip(*this);
 359   }
 360
 361   static inline bool classof(const Node *N) {
 362     return N->getType() == NK_Mapping;
 363   }
 364
 365 private:
 366   MappingType Type;
 367   bool IsAtBeginning;
 368   bool IsAtEnd;
 369   KeyValueNode *CurrentEntry;
 370
 371   void increment();
 372 };
 373
 374 /// @brief Represents a YAML sequence created from either a block sequence for a
 375 ///        flow sequence.
 376 ///
 377 /// This parses the YAML stream as increment() is called.
 378 ///
 379 /// Example:
 380 ///   - Hello
 381 ///   - World
 382 class SequenceNode : public Node {
 383 public:
 384   enum SequenceType {
 385     ST_Block,
 386     ST_Flow,
 387     // Use for:
 388     //
 389     // key:
 390     // - val1
 391     // - val2
 392     //
 393     // As a BlockMappingEntry and BlockEnd are not created in this case.
 394     ST_Indentless
 395   };
 396
 397   SequenceNode(OwningPtr<Document> &D, StringRef Anchor, SequenceType ST)
 398     : Node(NK_Sequence, D, Anchor)
 399     , SeqType(ST)
 400     , IsAtBeginning(true)
 401     , IsAtEnd(false)
 402     , WasPreviousTokenFlowEntry(true) // Start with an imaginary ','.
 403     , CurrentEntry(0)
 404   {}
 405
 406   friend class basic_collection_iterator<SequenceNode, Node>;
 407   typedef basic_collection_iterator<SequenceNode, Node> iterator;
 408   template <class T> friend typename T::iterator yaml::begin(T &);
 409   template <class T> friend void yaml::skip(T &);
 410
 411   void increment();
 412
 413   iterator begin() {
 414     return yaml::begin(*this);
 415   }
 416
 417   iterator end() { return iterator(); }
 418
 419   virtual void skip() LLVM_OVERRIDE {
 420     yaml::skip(*this);
 421   }
 422
 423   static inline bool classof(const Node *N) {
 424     return N->getType() == NK_Sequence;
 425   }
 426
 427 private:
 428   SequenceType SeqType;
 429   bool IsAtBeginning;
 430   bool IsAtEnd;
 431   bool WasPreviousTokenFlowEntry;
 432   Node *CurrentEntry;
 433 };
 434
 435 /// @brief Represents an alias to a Node with an anchor.
 436 ///
 437 /// Example:
 438 ///   *AnchorName
 439 class AliasNode : public Node {
 440 public:
 441   AliasNode(OwningPtr<Document> &D, StringRef Val)
 442     : Node(NK_Alias, D, StringRef()), Name(Val) {}
 443
 444   StringRef getName() const { return Name; }
 445   Node *getTarget();
 446
 447   static inline bool classof(const Node *N) {
 448     return N->getType() == NK_Alias;
 449   }
 450
 451 private:
 452   StringRef Name;
 453 };
 454
 455 /// @brief A YAML Stream is a sequence of Documents. A document contains a root
 456 ///        node.
 457 class Document {
 458 public:
 459   /// @brief Root for parsing a node. Returns a single node.
 460   Node *parseBlockNode();
 461
 462   Document(Stream &ParentStream);
 463
 464   /// @brief Finish parsing the current document and return true if there are
 465   ///        more. Return false otherwise.
 466   bool skip();
 467
 468   /// @brief Parse and return the root level node.
 469   Node *getRoot() {
 470     if (Root)
 471       return Root;
 472     return Root = parseBlockNode();
 473   }
 474
 475 private:
 476   friend class Node;
 477   friend class document_iterator;
 478
 479   /// @brief Stream to read tokens from.
 480   Stream &stream;
 481
 482   /// @brief Used to allocate nodes to. All are destroyed without calling their
 483   ///        destructor when the document is destroyed.
 484   BumpPtrAllocator NodeAllocator;
 485
 486   /// @brief The root node. Used to support skipping a partially parsed
 487   ///        document.
 488   Node *Root;
 489
 490   Token &peekNext();
 491   Token getNext();
 492   void setError(const Twine &Message, Token &Location) const;
 493   bool failed() const;
 494
 495   void handleTagDirective(const Token &Tag) {
 496     // TODO: Track tags.
 497   }
 498
 499   /// @brief Parse %BLAH directives and return true if any were encountered.
 500   bool parseDirectives();
 501
 502   /// @brief Consume the next token and error if it is not \a TK.
 503   bool expectToken(int TK);
 504 };
 505
 506 /// @brief Iterator abstraction for Documents over a Stream.
 507 class document_iterator {
 508 public:
 509   document_iterator() : Doc(0) {}
 510   document_iterator(OwningPtr<Document> &D) : Doc(&D) {}
 511
 512   bool operator ==(const document_iterator &Other) {
 513     if (isAtEnd() || Other.isAtEnd())
 514       return isAtEnd() && Other.isAtEnd();
 515
 516     return *Doc == *Other.Doc;
 517   }
 518   bool operator !=(const document_iterator &Other) {
 519     return !(*this == Other);
 520   }
 521
 522   document_iterator operator ++() {
 523     assert(Doc != 0 && "incrementing iterator past the end.");
 524     if (!(*Doc)->skip()) {
 525       Doc->reset(0);
 526     } else {
 527       Stream &S = (*Doc)->stream;
 528       Doc->reset(new Document(S));
 529     }
 530     return *this;
 531   }
 532
 533   Document &operator *() {
 534     return *Doc->get();
 535   }
 536
 537   OwningPtr<Document> &operator ->() {
 538     return *Doc;
 539   }
 540
 541 private:
 542   bool isAtEnd() const {
 543     return Doc == 0 || *Doc == 0;
 544   }
 545
 546   OwningPtr<Document> *Doc;
 547 };
 548
 549 }
 550 }
 551
 552 #endif