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
  82   document_iterator begin();
  83   document_iterator end();
  84   void skip();
  85   bool failed();
  86   bool validate() {
  87     skip();
  88     return !failed();
  89   }
  90
  91   void printError(Node *N, const Twine &Msg);
  92
  93 private:
  94   OwningPtr<Scanner> scanner;
  95   OwningPtr<Document> CurrentDoc;
  96
  97   friend class Document;
  98
  99   /// @brief Validate a %YAML x.x directive.
 100   void handleYAMLDirective(const Token &);
 101 };
 102
 103 /// @brief Abstract base class for all Nodes.
 104 class Node {
 105 public:
 106   enum NodeKind {
 107     NK_Null,
 108     NK_Scalar,
 109     NK_KeyValue,
 110     NK_Mapping,
 111     NK_Sequence,
 112     NK_Alias
 113   };
 114
 115   Node(unsigned int Type, OwningPtr<Document>&, StringRef Anchor);
 116
 117   /// @brief Get the value of the anchor attached to this node. If it does not
 118   ///        have one, getAnchor().size() will be 0.
 119   StringRef getAnchor() const { return Anchor; }
 120
 121   SMRange getSourceRange() const { return SourceRange; }
 122   void setSourceRange(SMRange SR) { SourceRange = SR; }
 123
 124   // These functions forward to Document and Scanner.
 125   Token &peekNext();
 126   Token getNext();
 127   Node *parseBlockNode();
 128   BumpPtrAllocator &getAllocator();
 129   void setError(const Twine &Message, Token &Location) const;
 130   bool failed() const;
 131
 132   virtual void skip() {};
 133
 134   unsigned int getType() const { return TypeID; }
 135   static inline bool classof(const Node *) { return true; }
 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 private:
 152   unsigned int TypeID;
 153   StringRef Anchor;
 154 };
 155
 156 /// @brief A null value.
 157 ///
 158 /// Example:
 159 ///   !!null null
 160 class NullNode : public Node {
 161 public:
 162   NullNode(OwningPtr<Document> &D) : Node(NK_Null, D, StringRef()) {}
 163
 164   static inline bool classof(const NullNode *) { return true; }
 165   static inline bool classof(const Node *N) {
 166     return N->getType() == NK_Null;
 167   }
 168 };
 169
 170 /// @brief A scalar node is an opaque datum that can be presented as a
 171 ///        series of zero or more Unicode scalar values.
 172 ///
 173 /// Example:
 174 ///   Adena
 175 class ScalarNode : public Node {
 176 public:
 177   ScalarNode(OwningPtr<Document> &D, StringRef Anchor, StringRef Val)
 178     : Node(NK_Scalar, D, Anchor)
 179     , Value(Val) {
 180     SMLoc Start = SMLoc::getFromPointer(Val.begin());
 181     SMLoc End = SMLoc::getFromPointer(Val.end() - 1);
 182     SourceRange = SMRange(Start, End);
 183   }
 184
 185   // Return Value without any escaping or folding or other fun YAML stuff. This
 186   // is the exact bytes that are contained in the file (after conversion to
 187   // utf8).
 188   StringRef getRawValue() const { return Value; }
 189
 190   /// @brief Gets the value of this node as a StringRef.
 191   ///
 192   /// @param Storage is used to store the content of the returned StringRef iff
 193   ///        it requires any modification from how it appeared in the source.
 194   ///        This happens with escaped characters and multi-line literals.
 195   StringRef getValue(SmallVectorImpl<char> &Storage) const;
 196
 197   static inline bool classof(const ScalarNode *) { return true; }
 198   static inline bool classof(const Node *N) {
 199     return N->getType() == NK_Scalar;
 200   }
 201
 202 private:
 203   StringRef Value;
 204
 205   StringRef unescapeDoubleQuoted( StringRef UnquotedValue
 206                                 , StringRef::size_type Start
 207                                 , SmallVectorImpl<char> &Storage) const;
 208 };
 209
 210 /// @brief A key and value pair. While not technically a Node under the YAML
 211 ///        representation graph, it is easier to treat them this way.
 212 ///
 213 /// TODO: Consider making this not a child of Node.
 214 ///
 215 /// Example:
 216 ///   Section: .text
 217 class KeyValueNode : public Node {
 218 public:
 219   KeyValueNode(OwningPtr<Document> &D)
 220     : Node(NK_KeyValue, D, StringRef())
 221     , Key(0)
 222     , Value(0)
 223   {}
 224
 225   /// @brief Parse and return the key.
 226   ///
 227   /// This may be called multiple times.
 228   ///
 229   /// @returns The key, or nullptr if failed() == true.
 230   Node *getKey();
 231
 232   /// @brief Parse and return the value.
 233   ///
 234   /// This may be called multiple times.
 235   ///
 236   /// @returns The value, or nullptr if failed() == true.
 237   Node *getValue();
 238
 239   virtual void skip() {
 240     getKey()->skip();
 241     getValue()->skip();
 242   }
 243
 244   static inline bool classof(const KeyValueNode *) { return true; }
 245   static inline bool classof(const Node *N) {
 246     return N->getType() == NK_KeyValue;
 247   }
 248
 249 private:
 250   Node *Key;
 251   Node *Value;
 252 };
 253
 254 /// @brief This is an iterator abstraction over YAML collections shared by both
 255 ///        sequences and maps.
 256 ///
 257 /// BaseT must have a ValueT* member named CurrentEntry and a member function
 258 /// increment() which must set CurrentEntry to 0 to create an end iterator.
 259 template <class BaseT, class ValueT>
 260 class basic_collection_iterator
 261   : public std::iterator<std::forward_iterator_tag, ValueT> {
 262 public:
 263   basic_collection_iterator() : Base(0) {}
 264   basic_collection_iterator(BaseT *B) : Base(B) {}
 265
 266   ValueT *operator ->() const {
 267     assert(Base && Base->CurrentEntry && "Attempted to access end iterator!");
 268     return Base->CurrentEntry;
 269   }
 270
 271   ValueT &operator *() const {
 272     assert(Base && Base->CurrentEntry &&
 273            "Attempted to dereference end iterator!");
 274     return *Base->CurrentEntry;
 275   }
 276
 277   operator ValueT*() const {
 278     assert(Base && Base->CurrentEntry && "Attempted to access end iterator!");
 279     return Base->CurrentEntry;
 280   }
 281
 282   bool operator !=(const basic_collection_iterator &Other) const {
 283     if(Base != Other.Base)
 284       return true;
 285     return (Base && Other.Base) && Base->CurrentEntry
 286                                    != Other.Base->CurrentEntry;
 287   }
 288
 289   basic_collection_iterator &operator++() {
 290     assert(Base && "Attempted to advance iterator past end!");
 291     Base->increment();
 292     // Create an end iterator.
 293     if (Base->CurrentEntry == 0)
 294       Base = 0;
 295     return *this;
 296   }
 297
 298 private:
 299   BaseT *Base;
 300 };
 301
 302 // The following two templates are used for both MappingNode and Sequence Node.
 303 template <class CollectionType>
 304 typename CollectionType::iterator begin(CollectionType &C) {
 305   assert(C.IsAtBeginning && "You may only iterate over a collection once!");
 306   C.IsAtBeginning = false;
 307   typename CollectionType::iterator ret(&C);
 308   ++ret;
 309   return ret;
 310 }
 311
 312 template <class CollectionType>
 313 void skip(CollectionType &C) {
 314   // TODO: support skipping from the middle of a parsed collection ;/
 315   assert((C.IsAtBeginning || C.IsAtEnd) && "Cannot skip mid parse!");
 316   if (C.IsAtBeginning)
 317     for (typename CollectionType::iterator i = begin(C), e = C.end();
 318                                            i != e; ++i)
 319       i->skip();
 320 }
 321
 322 /// @brief Represents a YAML map created from either a block map for a flow map.
 323 ///
 324 /// This parses the YAML stream as increment() is called.
 325 ///
 326 /// Example:
 327 ///   Name: _main
 328 ///   Scope: Global
 329 class MappingNode : public Node {
 330 public:
 331   enum MappingType {
 332     MT_Block,
 333     MT_Flow,
 334     MT_Inline //< An inline mapping node is used for "[key: value]".
 335   };
 336
 337   MappingNode(OwningPtr<Document> &D, StringRef Anchor, MappingType MT)
 338     : Node(NK_Mapping, D, Anchor)
 339     , Type(MT)
 340     , IsAtBeginning(true)
 341     , IsAtEnd(false)
 342     , CurrentEntry(0)
 343   {}
 344
 345   friend class basic_collection_iterator<MappingNode, KeyValueNode>;
 346   typedef basic_collection_iterator<MappingNode, KeyValueNode> iterator;
 347   template <class T> friend typename T::iterator yaml::begin(T &);
 348   template <class T> friend void yaml::skip(T &);
 349
 350   iterator begin() {
 351     return yaml::begin(*this);
 352   }
 353
 354   iterator end() { return iterator(); }
 355
 356   virtual void skip() {
 357     yaml::skip(*this);
 358   }
 359
 360   static inline bool classof(const MappingNode *) { return true; }
 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() {
 420     yaml::skip(*this);
 421   }
 422
 423   static inline bool classof(const SequenceNode *) { return true; }
 424   static inline bool classof(const Node *N) {
 425     return N->getType() == NK_Sequence;
 426   }
 427
 428 private:
 429   SequenceType SeqType;
 430   bool IsAtBeginning;
 431   bool IsAtEnd;
 432   bool WasPreviousTokenFlowEntry;
 433   Node *CurrentEntry;
 434 };
 435
 436 /// @brief Represents an alias to a Node with an anchor.
 437 ///
 438 /// Example:
 439 ///   *AnchorName
 440 class AliasNode : public Node {
 441 public:
 442   AliasNode(OwningPtr<Document> &D, StringRef Val)
 443     : Node(NK_Alias, D, StringRef()), Name(Val) {}
 444
 445   StringRef getName() const { return Name; }
 446   Node *getTarget();
 447
 448   static inline bool classof(const ScalarNode *) { return true; }
 449   static inline bool classof(const Node *N) {
 450     return N->getType() == NK_Alias;
 451   }
 452
 453 private:
 454   StringRef Name;
 455 };
 456
 457 /// @brief A YAML Stream is a sequence of Documents. A document contains a root
 458 ///        node.
 459 class Document {
 460 public:
 461   /// @brief Root for parsing a node. Returns a single node.
 462   Node *parseBlockNode();
 463
 464   Document(Stream &ParentStream);
 465
 466   /// @brief Finish parsing the current document and return true if there are
 467   ///        more. Return false otherwise.
 468   bool skip();
 469
 470   /// @brief Parse and return the root level node.
 471   Node *getRoot() {
 472     if (Root)
 473       return Root;
 474     return Root = parseBlockNode();
 475   }
 476
 477 private:
 478   friend class Node;
 479   friend class document_iterator;
 480
 481   /// @brief Stream to read tokens from.
 482   Stream &stream;
 483
 484   /// @brief Used to allocate nodes to. All are destroyed without calling their
 485   ///        destructor when the document is destroyed.
 486   BumpPtrAllocator NodeAllocator;
 487
 488   /// @brief The root node. Used to support skipping a partially parsed
 489   ///        document.
 490   Node *Root;
 491
 492   Token &peekNext();
 493   Token getNext();
 494   void setError(const Twine &Message, Token &Location) const;
 495   bool failed() const;
 496
 497   void handleTagDirective(const Token &Tag) {
 498     // TODO: Track tags.
 499   }
 500
 501   /// @brief Parse %BLAH directives and return true if any were encountered.
 502   bool parseDirectives();
 503
 504   /// @brief Consume the next token and error if it is not \a TK.
 505   bool expectToken(int TK);
 506 };
 507
 508 /// @brief Iterator abstraction for Documents over a Stream.
 509 class document_iterator {
 510 public:
 511   document_iterator() : Doc(NullDoc) {}
 512   document_iterator(OwningPtr<Document> &D) : Doc(D) {}
 513
 514   bool operator !=(const document_iterator &Other) {
 515     return Doc != Other.Doc;
 516   }
 517
 518   document_iterator operator ++() {
 519     if (!Doc->skip()) {
 520       Doc.reset(0);
 521     } else {
 522       Stream &S = Doc->stream;
 523       Doc.reset(new Document(S));
 524     }
 525     return *this;
 526   }
 527
 528   Document &operator *() {
 529     return *Doc;
 530   }
 531
 532   OwningPtr<Document> &operator ->() {
 533     return Doc;
 534   }
 535
 536 private:
 537   static OwningPtr<Document> NullDoc;
 538   OwningPtr<Document> &Doc;
 539 };
 540
 541 }
 542 }
 543
 544 #endif