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   virtual ~Node();
 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   static inline bool classof(const Node *) { return true; }
 137
 138   void *operator new ( size_t Size
 139                      , BumpPtrAllocator &Alloc
 140                      , size_t Alignment = 16) throw() {
 141     return Alloc.Allocate(Size, Alignment);
 142   }
 143
 144   void operator delete(void *Ptr, BumpPtrAllocator &Alloc, size_t) throw() {
 145     Alloc.Deallocate(Ptr);
 146   }
 147
 148 protected:
 149   OwningPtr<Document> &Doc;
 150   SMRange SourceRange;
 151
 152 private:
 153   unsigned int TypeID;
 154   StringRef Anchor;
 155 };
 156
 157 /// @brief A null value.
 158 ///
 159 /// Example:
 160 ///   !!null null
 161 class NullNode : public Node {
 162 public:
 163   NullNode(OwningPtr<Document> &D) : Node(NK_Null, D, StringRef()) {}
 164
 165   static inline bool classof(const NullNode *) { return true; }
 166   static inline bool classof(const Node *N) {
 167     return N->getType() == NK_Null;
 168   }
 169 };
 170
 171 /// @brief A scalar node is an opaque datum that can be presented as a
 172 ///        series of zero or more Unicode scalar values.
 173 ///
 174 /// Example:
 175 ///   Adena
 176 class ScalarNode : public Node {
 177 public:
 178   ScalarNode(OwningPtr<Document> &D, StringRef Anchor, StringRef Val)
 179     : Node(NK_Scalar, D, Anchor)
 180     , Value(Val) {
 181     SMLoc Start = SMLoc::getFromPointer(Val.begin());
 182     SMLoc End = SMLoc::getFromPointer(Val.end() - 1);
 183     SourceRange = SMRange(Start, End);
 184   }
 185
 186   // Return Value without any escaping or folding or other fun YAML stuff. This
 187   // is the exact bytes that are contained in the file (after conversion to
 188   // utf8).
 189   StringRef getRawValue() const { return Value; }
 190
 191   /// @brief Gets the value of this node as a StringRef.
 192   ///
 193   /// @param Storage is used to store the content of the returned StringRef iff
 194   ///        it requires any modification from how it appeared in the source.
 195   ///        This happens with escaped characters and multi-line literals.
 196   StringRef getValue(SmallVectorImpl<char> &Storage) const;
 197
 198   static inline bool classof(const ScalarNode *) { return true; }
 199   static inline bool classof(const Node *N) {
 200     return N->getType() == NK_Scalar;
 201   }
 202
 203 private:
 204   StringRef Value;
 205
 206   StringRef unescapeDoubleQuoted( StringRef UnquotedValue
 207                                 , StringRef::size_type Start
 208                                 , SmallVectorImpl<char> &Storage) const;
 209 };
 210
 211 static bool getAs(const ScalarNode *SN, bool &Result) {
 212   SmallString<4> Storage;
 213   StringRef Value = SN->getValue(Storage);
 214   if (Value == "true")
 215     Result = true;
 216   else if (Value == "false")
 217     Result = false;
 218   else
 219     return false;
 220   return true;
 221 }
 222
 223 template<class T>
 224 typename enable_if_c<std::numeric_limits<T>::is_integer, bool>::type
 225 getAs(const ScalarNode *SN, T &Result) {
 226   SmallString<4> Storage;
 227   return !SN->getValue(Storage).getAsInteger(0, Result);
 228 }
 229
 230 /// @brief A key and value pair. While not technically a Node under the YAML
 231 ///        representation graph, it is easier to treat them this way.
 232 ///
 233 /// TODO: Consider making this not a child of Node.
 234 ///
 235 /// Example:
 236 ///   Section: .text
 237 class KeyValueNode : public Node {
 238 public:
 239   KeyValueNode(OwningPtr<Document> &D)
 240     : Node(NK_KeyValue, D, StringRef())
 241     , Key(0)
 242     , Value(0)
 243   {}
 244
 245   /// @brief Parse and return the key.
 246   ///
 247   /// This may be called multiple times.
 248   ///
 249   /// @returns The key, or nullptr if failed() == true.
 250   Node *getKey();
 251
 252   /// @brief Parse and return the value.
 253   ///
 254   /// This may be called multiple times.
 255   ///
 256   /// @returns The value, or nullptr if failed() == true.
 257   Node *getValue();
 258
 259   virtual void skip() {
 260     getKey()->skip();
 261     getValue()->skip();
 262   }
 263
 264   static inline bool classof(const KeyValueNode *) { return true; }
 265   static inline bool classof(const Node *N) {
 266     return N->getType() == NK_KeyValue;
 267   }
 268
 269 private:
 270   Node *Key;
 271   Node *Value;
 272 };
 273
 274 /// @brief This is an iterator abstraction over YAML collections shared by both
 275 ///        sequences and maps.
 276 ///
 277 /// BaseT must have a ValueT* member named CurrentEntry and a member function
 278 /// increment() which must set CurrentEntry to 0 to create an end iterator.
 279 template <class BaseT, class ValueT>
 280 class basic_collection_iterator
 281   : public std::iterator<std::forward_iterator_tag, ValueT> {
 282 public:
 283   basic_collection_iterator() : Base(0) {}
 284   basic_collection_iterator(BaseT *B) : Base(B) {}
 285
 286   ValueT *operator ->() const {
 287     assert(Base && Base->CurrentEntry && "Attempted to access end iterator!");
 288     return Base->CurrentEntry;
 289   }
 290
 291   ValueT &operator *() const {
 292     assert(Base && Base->CurrentEntry &&
 293            "Attempted to dereference end iterator!");
 294     return *Base->CurrentEntry;
 295   }
 296
 297   operator ValueT*() const {
 298     assert(Base && Base->CurrentEntry && "Attempted to access end iterator!");
 299     return Base->CurrentEntry;
 300   }
 301
 302   bool operator !=(const basic_collection_iterator &Other) const {
 303     if(Base != Other.Base)
 304       return true;
 305     return (Base && Other.Base) && Base->CurrentEntry
 306                                    != Other.Base->CurrentEntry;
 307   }
 308
 309   basic_collection_iterator &operator++() {
 310     assert(Base && "Attempted to advance iterator past end!");
 311     Base->increment();
 312     // Create an end iterator.
 313     if (Base->CurrentEntry == 0)
 314       Base = 0;
 315     return *this;
 316   }
 317
 318 private:
 319   BaseT *Base;
 320 };
 321
 322 // The following two templates are used for both MappingNode and Sequence Node.
 323 template <class CollectionType>
 324 typename CollectionType::iterator begin(CollectionType &C) {
 325   assert(C.IsAtBeginning && "You may only iterate over a collection once!");
 326   C.IsAtBeginning = false;
 327   typename CollectionType::iterator ret(&C);
 328   ++ret;
 329   return ret;
 330 }
 331
 332 template <class CollectionType>
 333 void skip(CollectionType &C) {
 334   // TODO: support skipping from the middle of a parsed collection ;/
 335   assert((C.IsAtBeginning || C.IsAtEnd) && "Cannot skip mid parse!");
 336   if (C.IsAtBeginning)
 337     for (typename CollectionType::iterator i = begin(C), e = C.end();
 338                                            i != e; ++i)
 339       i->skip();
 340 }
 341
 342 /// @brief Represents a YAML map created from either a block map for a flow map.
 343 ///
 344 /// This parses the YAML stream as increment() is called.
 345 ///
 346 /// Example:
 347 ///   Name: _main
 348 ///   Scope: Global
 349 class MappingNode : public Node {
 350 public:
 351   enum MappingType {
 352     MT_Block,
 353     MT_Flow,
 354     MT_Inline //< An inline mapping node is used for "[key: value]".
 355   };
 356
 357   MappingNode(OwningPtr<Document> &D, StringRef Anchor, MappingType MT)
 358     : Node(NK_Mapping, D, Anchor)
 359     , Type(MT)
 360     , IsAtBeginning(true)
 361     , IsAtEnd(false)
 362     , CurrentEntry(0)
 363   {}
 364
 365   friend class basic_collection_iterator<MappingNode, KeyValueNode>;
 366   typedef basic_collection_iterator<MappingNode, KeyValueNode> iterator;
 367   template <class T> friend typename T::iterator yaml::begin(T &);
 368   template <class T> friend void yaml::skip(T &);
 369
 370   iterator begin() {
 371     return yaml::begin(*this);
 372   }
 373
 374   iterator end() { return iterator(); }
 375
 376   virtual void skip() {
 377     yaml::skip(*this);
 378   }
 379
 380   static inline bool classof(const MappingNode *) { return true; }
 381   static inline bool classof(const Node *N) {
 382     return N->getType() == NK_Mapping;
 383   }
 384
 385 private:
 386   MappingType Type;
 387   bool IsAtBeginning;
 388   bool IsAtEnd;
 389   KeyValueNode *CurrentEntry;
 390
 391   void increment();
 392 };
 393
 394 /// @brief Represents a YAML sequence created from either a block sequence for a
 395 ///        flow sequence.
 396 ///
 397 /// This parses the YAML stream as increment() is called.
 398 ///
 399 /// Example:
 400 ///   - Hello
 401 ///   - World
 402 class SequenceNode : public Node {
 403 public:
 404   enum SequenceType {
 405     ST_Block,
 406     ST_Flow,
 407     // Use for:
 408     //
 409     // key:
 410     // - val1
 411     // - val2
 412     //
 413     // As a BlockMappingEntry and BlockEnd are not created in this case.
 414     ST_Indentless
 415   };
 416
 417   SequenceNode(OwningPtr<Document> &D, StringRef Anchor, SequenceType ST)
 418     : Node(NK_Sequence, D, Anchor)
 419     , SeqType(ST)
 420     , IsAtBeginning(true)
 421     , IsAtEnd(false)
 422     , WasPreviousTokenFlowEntry(true) // Start with an imaginary ','.
 423     , CurrentEntry(0)
 424   {}
 425
 426   friend class basic_collection_iterator<SequenceNode, Node>;
 427   typedef basic_collection_iterator<SequenceNode, Node> iterator;
 428   template <class T> friend typename T::iterator yaml::begin(T &);
 429   template <class T> friend void yaml::skip(T &);
 430
 431   void increment();
 432
 433   iterator begin() {
 434     return yaml::begin(*this);
 435   }
 436
 437   iterator end() { return iterator(); }
 438
 439   virtual void skip() {
 440     yaml::skip(*this);
 441   }
 442
 443   static inline bool classof(const SequenceNode *) { return true; }
 444   static inline bool classof(const Node *N) {
 445     return N->getType() == NK_Sequence;
 446   }
 447
 448 private:
 449   SequenceType SeqType;
 450   bool IsAtBeginning;
 451   bool IsAtEnd;
 452   bool WasPreviousTokenFlowEntry;
 453   Node *CurrentEntry;
 454 };
 455
 456 /// @brief Represents an alias to a Node with an anchor.
 457 ///
 458 /// Example:
 459 ///   *AnchorName
 460 class AliasNode : public Node {
 461 public:
 462   AliasNode(OwningPtr<Document> &D, StringRef Val)
 463     : Node(NK_Alias, D, StringRef()), Name(Val) {}
 464
 465   StringRef getName() const { return Name; }
 466   Node *getTarget();
 467
 468   static inline bool classof(const ScalarNode *) { return true; }
 469   static inline bool classof(const Node *N) {
 470     return N->getType() == NK_Alias;
 471   }
 472
 473 private:
 474   StringRef Name;
 475 };
 476
 477 /// @brief A YAML Stream is a sequence of Documents. A document contains a root
 478 ///        node.
 479 class Document {
 480 public:
 481   /// @brief Root for parsing a node. Returns a single node.
 482   Node *parseBlockNode();
 483
 484   Document(Stream &ParentStream);
 485
 486   /// @brief Finish parsing the current document and return true if there are
 487   ///        more. Return false otherwise.
 488   bool skip();
 489
 490   /// @brief Parse and return the root level node.
 491   Node *getRoot() {
 492     if (Root)
 493       return Root;
 494     return Root = parseBlockNode();
 495   }
 496
 497 private:
 498   friend class Node;
 499   friend class document_iterator;
 500
 501   /// @brief Stream to read tokens from.
 502   Stream &stream;
 503
 504   /// @brief Used to allocate nodes to. All are destroyed without calling their
 505   ///        destructor when the document is destroyed.
 506   BumpPtrAllocator NodeAllocator;
 507
 508   /// @brief The root node. Used to support skipping a partially parsed
 509   ///        document.
 510   Node *Root;
 511
 512   Token &peekNext();
 513   Token getNext();
 514   void setError(const Twine &Message, Token &Location) const;
 515   bool failed() const;
 516
 517   void handleTagDirective(const Token &Tag) {
 518     // TODO: Track tags.
 519   }
 520
 521   /// @brief Parse %BLAH directives and return true if any were encountered.
 522   bool parseDirectives();
 523
 524   /// @brief Consume the next token and error if it is not \a TK.
 525   bool expectToken(int TK);
 526 };
 527
 528 /// @brief Iterator abstraction for Documents over a Stream.
 529 class document_iterator {
 530 public:
 531   document_iterator() : Doc(NullDoc) {}
 532   document_iterator(OwningPtr<Document> &D) : Doc(D) {}
 533
 534   bool operator !=(const document_iterator &Other) {
 535     return Doc != Other.Doc;
 536   }
 537
 538   document_iterator operator ++() {
 539     if (!Doc->skip()) {
 540       Doc.reset(0);
 541     } else {
 542       Stream &S = Doc->stream;
 543       Doc.reset(new Document(S));
 544     }
 545     return *this;
 546   }
 547
 548   Document &operator *() {
 549     return *Doc;
 550   }
 551
 552   OwningPtr<Document> &operator ->() {
 553     return Doc;
 554   }
 555
 556 private:
 557   static OwningPtr<Document> NullDoc;
 558   OwningPtr<Document> &Doc;
 559 };
 560
 561 }
 562 }
 563
 564 #endif