contrib/llvm/include/llvm/Support/YAMLParser.h

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