1 //===--- YAMLParser.cpp - 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 file implements a YAML parser. 11 // 12 //===----------------------------------------------------------------------===// 13 14 #include "llvm/Support/YAMLParser.h" 15 #include "llvm/ADT/SmallString.h" 16 #include "llvm/ADT/SmallVector.h" 17 #include "llvm/ADT/StringExtras.h" 18 #include "llvm/ADT/Twine.h" 19 #include "llvm/ADT/ilist.h" 20 #include "llvm/ADT/ilist_node.h" 21 #include "llvm/Support/ErrorHandling.h" 22 #include "llvm/Support/MemoryBuffer.h" 23 #include "llvm/Support/SourceMgr.h" 24 #include "llvm/Support/raw_ostream.h" 25 26 using namespace llvm; 27 using namespace yaml; 28 29 enum UnicodeEncodingForm { 30 UEF_UTF32_LE, ///< UTF-32 Little Endian 31 UEF_UTF32_BE, ///< UTF-32 Big Endian 32 UEF_UTF16_LE, ///< UTF-16 Little Endian 33 UEF_UTF16_BE, ///< UTF-16 Big Endian 34 UEF_UTF8, ///< UTF-8 or ascii. 35 UEF_Unknown ///< Not a valid Unicode encoding. 36 }; 37 38 /// EncodingInfo - Holds the encoding type and length of the byte order mark if 39 /// it exists. Length is in {0, 2, 3, 4}. 40 typedef std::pair<UnicodeEncodingForm, unsigned> EncodingInfo; 41 42 /// getUnicodeEncoding - Reads up to the first 4 bytes to determine the Unicode 43 /// encoding form of \a Input. 44 /// 45 /// @param Input A string of length 0 or more. 46 /// @returns An EncodingInfo indicating the Unicode encoding form of the input 47 /// and how long the byte order mark is if one exists. 48 static EncodingInfo getUnicodeEncoding(StringRef Input) { 49 if (Input.size() == 0) 50 return std::make_pair(UEF_Unknown, 0); 51 52 switch (uint8_t(Input[0])) { 53 case 0x00: 54 if (Input.size() >= 4) { 55 if ( Input[1] == 0 56 && uint8_t(Input[2]) == 0xFE 57 && uint8_t(Input[3]) == 0xFF) 58 return std::make_pair(UEF_UTF32_BE, 4); 59 if (Input[1] == 0 && Input[2] == 0 && Input[3] != 0) 60 return std::make_pair(UEF_UTF32_BE, 0); 61 } 62 63 if (Input.size() >= 2 && Input[1] != 0) 64 return std::make_pair(UEF_UTF16_BE, 0); 65 return std::make_pair(UEF_Unknown, 0); 66 case 0xFF: 67 if ( Input.size() >= 4 68 && uint8_t(Input[1]) == 0xFE 69 && Input[2] == 0 70 && Input[3] == 0) 71 return std::make_pair(UEF_UTF32_LE, 4); 72 73 if (Input.size() >= 2 && uint8_t(Input[1]) == 0xFE) 74 return std::make_pair(UEF_UTF16_LE, 2); 75 return std::make_pair(UEF_Unknown, 0); 76 case 0xFE: 77 if (Input.size() >= 2 && uint8_t(Input[1]) == 0xFF) 78 return std::make_pair(UEF_UTF16_BE, 2); 79 return std::make_pair(UEF_Unknown, 0); 80 case 0xEF: 81 if ( Input.size() >= 3 82 && uint8_t(Input[1]) == 0xBB 83 && uint8_t(Input[2]) == 0xBF) 84 return std::make_pair(UEF_UTF8, 3); 85 return std::make_pair(UEF_Unknown, 0); 86 } 87 88 // It could still be utf-32 or utf-16. 89 if (Input.size() >= 4 && Input[1] == 0 && Input[2] == 0 && Input[3] == 0) 90 return std::make_pair(UEF_UTF32_LE, 0); 91 92 if (Input.size() >= 2 && Input[1] == 0) 93 return std::make_pair(UEF_UTF16_LE, 0); 94 95 return std::make_pair(UEF_UTF8, 0); 96 } 97 98 namespace llvm { 99 namespace yaml { 100 /// Pin the vtables to this file. 101 void Node::anchor() {} 102 void NullNode::anchor() {} 103 void ScalarNode::anchor() {} 104 void BlockScalarNode::anchor() {} 105 void KeyValueNode::anchor() {} 106 void MappingNode::anchor() {} 107 void SequenceNode::anchor() {} 108 void AliasNode::anchor() {} 109 110 /// Token - A single YAML token. 111 struct Token : ilist_node<Token> { 112 enum TokenKind { 113 TK_Error, // Uninitialized token. 114 TK_StreamStart, 115 TK_StreamEnd, 116 TK_VersionDirective, 117 TK_TagDirective, 118 TK_DocumentStart, 119 TK_DocumentEnd, 120 TK_BlockEntry, 121 TK_BlockEnd, 122 TK_BlockSequenceStart, 123 TK_BlockMappingStart, 124 TK_FlowEntry, 125 TK_FlowSequenceStart, 126 TK_FlowSequenceEnd, 127 TK_FlowMappingStart, 128 TK_FlowMappingEnd, 129 TK_Key, 130 TK_Value, 131 TK_Scalar, 132 TK_BlockScalar, 133 TK_Alias, 134 TK_Anchor, 135 TK_Tag 136 } Kind; 137 138 /// A string of length 0 or more whose begin() points to the logical location 139 /// of the token in the input. 140 StringRef Range; 141 142 /// The value of a block scalar node. 143 std::string Value; 144 145 Token() : Kind(TK_Error) {} 146 }; 147 } 148 } 149 150 namespace llvm { 151 template<> 152 struct ilist_sentinel_traits<Token> { 153 Token *createSentinel() const { 154 return &Sentinel; 155 } 156 static void destroySentinel(Token*) {} 157 158 Token *provideInitialHead() const { return createSentinel(); } 159 Token *ensureHead(Token*) const { return createSentinel(); } 160 static void noteHead(Token*, Token*) {} 161 162 private: 163 mutable Token Sentinel; 164 }; 165 166 template<> 167 struct ilist_node_traits<Token> { 168 Token *createNode(const Token &V) { 169 return new (Alloc.Allocate<Token>()) Token(V); 170 } 171 static void deleteNode(Token *V) { V->~Token(); } 172 173 void addNodeToList(Token *) {} 174 void removeNodeFromList(Token *) {} 175 void transferNodesFromList(ilist_node_traits & /*SrcTraits*/, 176 ilist_iterator<Token> /*first*/, 177 ilist_iterator<Token> /*last*/) {} 178 179 BumpPtrAllocator Alloc; 180 }; 181 } 182 183 typedef ilist<Token> TokenQueueT; 184 185 namespace { 186 /// @brief This struct is used to track simple keys. 187 /// 188 /// Simple keys are handled by creating an entry in SimpleKeys for each Token 189 /// which could legally be the start of a simple key. When peekNext is called, 190 /// if the Token To be returned is referenced by a SimpleKey, we continue 191 /// tokenizing until that potential simple key has either been found to not be 192 /// a simple key (we moved on to the next line or went further than 1024 chars). 193 /// Or when we run into a Value, and then insert a Key token (and possibly 194 /// others) before the SimpleKey's Tok. 195 struct SimpleKey { 196 TokenQueueT::iterator Tok; 197 unsigned Column; 198 unsigned Line; 199 unsigned FlowLevel; 200 bool IsRequired; 201 202 bool operator ==(const SimpleKey &Other) { 203 return Tok == Other.Tok; 204 } 205 }; 206 } 207 208 /// @brief The Unicode scalar value of a UTF-8 minimal well-formed code unit 209 /// subsequence and the subsequence's length in code units (uint8_t). 210 /// A length of 0 represents an error. 211 typedef std::pair<uint32_t, unsigned> UTF8Decoded; 212 213 static UTF8Decoded decodeUTF8(StringRef Range) { 214 StringRef::iterator Position= Range.begin(); 215 StringRef::iterator End = Range.end(); 216 // 1 byte: [0x00, 0x7f] 217 // Bit pattern: 0xxxxxxx 218 if ((*Position & 0x80) == 0) { 219 return std::make_pair(*Position, 1); 220 } 221 // 2 bytes: [0x80, 0x7ff] 222 // Bit pattern: 110xxxxx 10xxxxxx 223 if (Position + 1 != End && 224 ((*Position & 0xE0) == 0xC0) && 225 ((*(Position + 1) & 0xC0) == 0x80)) { 226 uint32_t codepoint = ((*Position & 0x1F) << 6) | 227 (*(Position + 1) & 0x3F); 228 if (codepoint >= 0x80) 229 return std::make_pair(codepoint, 2); 230 } 231 // 3 bytes: [0x8000, 0xffff] 232 // Bit pattern: 1110xxxx 10xxxxxx 10xxxxxx 233 if (Position + 2 != End && 234 ((*Position & 0xF0) == 0xE0) && 235 ((*(Position + 1) & 0xC0) == 0x80) && 236 ((*(Position + 2) & 0xC0) == 0x80)) { 237 uint32_t codepoint = ((*Position & 0x0F) << 12) | 238 ((*(Position + 1) & 0x3F) << 6) | 239 (*(Position + 2) & 0x3F); 240 // Codepoints between 0xD800 and 0xDFFF are invalid, as 241 // they are high / low surrogate halves used by UTF-16. 242 if (codepoint >= 0x800 && 243 (codepoint < 0xD800 || codepoint > 0xDFFF)) 244 return std::make_pair(codepoint, 3); 245 } 246 // 4 bytes: [0x10000, 0x10FFFF] 247 // Bit pattern: 11110xxx 10xxxxxx 10xxxxxx 10xxxxxx 248 if (Position + 3 != End && 249 ((*Position & 0xF8) == 0xF0) && 250 ((*(Position + 1) & 0xC0) == 0x80) && 251 ((*(Position + 2) & 0xC0) == 0x80) && 252 ((*(Position + 3) & 0xC0) == 0x80)) { 253 uint32_t codepoint = ((*Position & 0x07) << 18) | 254 ((*(Position + 1) & 0x3F) << 12) | 255 ((*(Position + 2) & 0x3F) << 6) | 256 (*(Position + 3) & 0x3F); 257 if (codepoint >= 0x10000 && codepoint <= 0x10FFFF) 258 return std::make_pair(codepoint, 4); 259 } 260 return std::make_pair(0, 0); 261 } 262 263 namespace llvm { 264 namespace yaml { 265 /// @brief Scans YAML tokens from a MemoryBuffer. 266 class Scanner { 267 public: 268 Scanner(StringRef Input, SourceMgr &SM, bool ShowColors = true); 269 Scanner(MemoryBufferRef Buffer, SourceMgr &SM_, bool ShowColors = true); 270 271 /// @brief Parse the next token and return it without popping it. 272 Token &peekNext(); 273 274 /// @brief Parse the next token and pop it from the queue. 275 Token getNext(); 276 277 void printError(SMLoc Loc, SourceMgr::DiagKind Kind, const Twine &Message, 278 ArrayRef<SMRange> Ranges = None) { 279 SM.PrintMessage(Loc, Kind, Message, Ranges, /* FixIts= */ None, ShowColors); 280 } 281 282 void setError(const Twine &Message, StringRef::iterator Position) { 283 if (Current >= End) 284 Current = End - 1; 285 286 // Don't print out more errors after the first one we encounter. The rest 287 // are just the result of the first, and have no meaning. 288 if (!Failed) 289 printError(SMLoc::getFromPointer(Current), SourceMgr::DK_Error, Message); 290 Failed = true; 291 } 292 293 void setError(const Twine &Message) { 294 setError(Message, Current); 295 } 296 297 /// @brief Returns true if an error occurred while parsing. 298 bool failed() { 299 return Failed; 300 } 301 302 private: 303 void init(MemoryBufferRef Buffer); 304 305 StringRef currentInput() { 306 return StringRef(Current, End - Current); 307 } 308 309 /// @brief Decode a UTF-8 minimal well-formed code unit subsequence starting 310 /// at \a Position. 311 /// 312 /// If the UTF-8 code units starting at Position do not form a well-formed 313 /// code unit subsequence, then the Unicode scalar value is 0, and the length 314 /// is 0. 315 UTF8Decoded decodeUTF8(StringRef::iterator Position) { 316 return ::decodeUTF8(StringRef(Position, End - Position)); 317 } 318 319 // The following functions are based on the gramar rules in the YAML spec. The 320 // style of the function names it meant to closely match how they are written 321 // in the spec. The number within the [] is the number of the grammar rule in 322 // the spec. 323 // 324 // See 4.2 [Production Naming Conventions] for the meaning of the prefixes. 325 // 326 // c- 327 // A production starting and ending with a special character. 328 // b- 329 // A production matching a single line break. 330 // nb- 331 // A production starting and ending with a non-break character. 332 // s- 333 // A production starting and ending with a white space character. 334 // ns- 335 // A production starting and ending with a non-space character. 336 // l- 337 // A production matching complete line(s). 338 339 /// @brief Skip a single nb-char[27] starting at Position. 340 /// 341 /// A nb-char is 0x9 | [0x20-0x7E] | 0x85 | [0xA0-0xD7FF] | [0xE000-0xFEFE] 342 /// | [0xFF00-0xFFFD] | [0x10000-0x10FFFF] 343 /// 344 /// @returns The code unit after the nb-char, or Position if it's not an 345 /// nb-char. 346 StringRef::iterator skip_nb_char(StringRef::iterator Position); 347 348 /// @brief Skip a single b-break[28] starting at Position. 349 /// 350 /// A b-break is 0xD 0xA | 0xD | 0xA 351 /// 352 /// @returns The code unit after the b-break, or Position if it's not a 353 /// b-break. 354 StringRef::iterator skip_b_break(StringRef::iterator Position); 355 356 /// Skip a single s-space[31] starting at Position. 357 /// 358 /// An s-space is 0x20 359 /// 360 /// @returns The code unit after the s-space, or Position if it's not a 361 /// s-space. 362 StringRef::iterator skip_s_space(StringRef::iterator Position); 363 364 /// @brief Skip a single s-white[33] starting at Position. 365 /// 366 /// A s-white is 0x20 | 0x9 367 /// 368 /// @returns The code unit after the s-white, or Position if it's not a 369 /// s-white. 370 StringRef::iterator skip_s_white(StringRef::iterator Position); 371 372 /// @brief Skip a single ns-char[34] starting at Position. 373 /// 374 /// A ns-char is nb-char - s-white 375 /// 376 /// @returns The code unit after the ns-char, or Position if it's not a 377 /// ns-char. 378 StringRef::iterator skip_ns_char(StringRef::iterator Position); 379 380 typedef StringRef::iterator (Scanner::*SkipWhileFunc)(StringRef::iterator); 381 /// @brief Skip minimal well-formed code unit subsequences until Func 382 /// returns its input. 383 /// 384 /// @returns The code unit after the last minimal well-formed code unit 385 /// subsequence that Func accepted. 386 StringRef::iterator skip_while( SkipWhileFunc Func 387 , StringRef::iterator Position); 388 389 /// Skip minimal well-formed code unit subsequences until Func returns its 390 /// input. 391 void advanceWhile(SkipWhileFunc Func); 392 393 /// @brief Scan ns-uri-char[39]s starting at Cur. 394 /// 395 /// This updates Cur and Column while scanning. 396 /// 397 /// @returns A StringRef starting at Cur which covers the longest contiguous 398 /// sequence of ns-uri-char. 399 StringRef scan_ns_uri_char(); 400 401 /// @brief Consume a minimal well-formed code unit subsequence starting at 402 /// \a Cur. Return false if it is not the same Unicode scalar value as 403 /// \a Expected. This updates \a Column. 404 bool consume(uint32_t Expected); 405 406 /// @brief Skip \a Distance UTF-8 code units. Updates \a Cur and \a Column. 407 void skip(uint32_t Distance); 408 409 /// @brief Return true if the minimal well-formed code unit subsequence at 410 /// Pos is whitespace or a new line 411 bool isBlankOrBreak(StringRef::iterator Position); 412 413 /// Consume a single b-break[28] if it's present at the current position. 414 /// 415 /// Return false if the code unit at the current position isn't a line break. 416 bool consumeLineBreakIfPresent(); 417 418 /// @brief If IsSimpleKeyAllowed, create and push_back a new SimpleKey. 419 void saveSimpleKeyCandidate( TokenQueueT::iterator Tok 420 , unsigned AtColumn 421 , bool IsRequired); 422 423 /// @brief Remove simple keys that can no longer be valid simple keys. 424 /// 425 /// Invalid simple keys are not on the current line or are further than 1024 426 /// columns back. 427 void removeStaleSimpleKeyCandidates(); 428 429 /// @brief Remove all simple keys on FlowLevel \a Level. 430 void removeSimpleKeyCandidatesOnFlowLevel(unsigned Level); 431 432 /// @brief Unroll indentation in \a Indents back to \a Col. Creates BlockEnd 433 /// tokens if needed. 434 bool unrollIndent(int ToColumn); 435 436 /// @brief Increase indent to \a Col. Creates \a Kind token at \a InsertPoint 437 /// if needed. 438 bool rollIndent( int ToColumn 439 , Token::TokenKind Kind 440 , TokenQueueT::iterator InsertPoint); 441 442 /// @brief Skip a single-line comment when the comment starts at the current 443 /// position of the scanner. 444 void skipComment(); 445 446 /// @brief Skip whitespace and comments until the start of the next token. 447 void scanToNextToken(); 448 449 /// @brief Must be the first token generated. 450 bool scanStreamStart(); 451 452 /// @brief Generate tokens needed to close out the stream. 453 bool scanStreamEnd(); 454 455 /// @brief Scan a %BLAH directive. 456 bool scanDirective(); 457 458 /// @brief Scan a ... or ---. 459 bool scanDocumentIndicator(bool IsStart); 460 461 /// @brief Scan a [ or { and generate the proper flow collection start token. 462 bool scanFlowCollectionStart(bool IsSequence); 463 464 /// @brief Scan a ] or } and generate the proper flow collection end token. 465 bool scanFlowCollectionEnd(bool IsSequence); 466 467 /// @brief Scan the , that separates entries in a flow collection. 468 bool scanFlowEntry(); 469 470 /// @brief Scan the - that starts block sequence entries. 471 bool scanBlockEntry(); 472 473 /// @brief Scan an explicit ? indicating a key. 474 bool scanKey(); 475 476 /// @brief Scan an explicit : indicating a value. 477 bool scanValue(); 478 479 /// @brief Scan a quoted scalar. 480 bool scanFlowScalar(bool IsDoubleQuoted); 481 482 /// @brief Scan an unquoted scalar. 483 bool scanPlainScalar(); 484 485 /// @brief Scan an Alias or Anchor starting with * or &. 486 bool scanAliasOrAnchor(bool IsAlias); 487 488 /// @brief Scan a block scalar starting with | or >. 489 bool scanBlockScalar(bool IsLiteral); 490 491 /// Scan a chomping indicator in a block scalar header. 492 char scanBlockChompingIndicator(); 493 494 /// Scan an indentation indicator in a block scalar header. 495 unsigned scanBlockIndentationIndicator(); 496 497 /// Scan a block scalar header. 498 /// 499 /// Return false if an error occurred. 500 bool scanBlockScalarHeader(char &ChompingIndicator, unsigned &IndentIndicator, 501 bool &IsDone); 502 503 /// Look for the indentation level of a block scalar. 504 /// 505 /// Return false if an error occurred. 506 bool findBlockScalarIndent(unsigned &BlockIndent, unsigned BlockExitIndent, 507 unsigned &LineBreaks, bool &IsDone); 508 509 /// Scan the indentation of a text line in a block scalar. 510 /// 511 /// Return false if an error occurred. 512 bool scanBlockScalarIndent(unsigned BlockIndent, unsigned BlockExitIndent, 513 bool &IsDone); 514 515 /// @brief Scan a tag of the form !stuff. 516 bool scanTag(); 517 518 /// @brief Dispatch to the next scanning function based on \a *Cur. 519 bool fetchMoreTokens(); 520 521 /// @brief The SourceMgr used for diagnostics and buffer management. 522 SourceMgr &SM; 523 524 /// @brief The original input. 525 MemoryBufferRef InputBuffer; 526 527 /// @brief The current position of the scanner. 528 StringRef::iterator Current; 529 530 /// @brief The end of the input (one past the last character). 531 StringRef::iterator End; 532 533 /// @brief Current YAML indentation level in spaces. 534 int Indent; 535 536 /// @brief Current column number in Unicode code points. 537 unsigned Column; 538 539 /// @brief Current line number. 540 unsigned Line; 541 542 /// @brief How deep we are in flow style containers. 0 Means at block level. 543 unsigned FlowLevel; 544 545 /// @brief Are we at the start of the stream? 546 bool IsStartOfStream; 547 548 /// @brief Can the next token be the start of a simple key? 549 bool IsSimpleKeyAllowed; 550 551 /// @brief True if an error has occurred. 552 bool Failed; 553 554 /// @brief Should colors be used when printing out the diagnostic messages? 555 bool ShowColors; 556 557 /// @brief Queue of tokens. This is required to queue up tokens while looking 558 /// for the end of a simple key. And for cases where a single character 559 /// can produce multiple tokens (e.g. BlockEnd). 560 TokenQueueT TokenQueue; 561 562 /// @brief Indentation levels. 563 SmallVector<int, 4> Indents; 564 565 /// @brief Potential simple keys. 566 SmallVector<SimpleKey, 4> SimpleKeys; 567 }; 568 569 } // end namespace yaml 570 } // end namespace llvm 571 572 /// encodeUTF8 - Encode \a UnicodeScalarValue in UTF-8 and append it to result. 573 static void encodeUTF8( uint32_t UnicodeScalarValue 574 , SmallVectorImpl<char> &Result) { 575 if (UnicodeScalarValue <= 0x7F) { 576 Result.push_back(UnicodeScalarValue & 0x7F); 577 } else if (UnicodeScalarValue <= 0x7FF) { 578 uint8_t FirstByte = 0xC0 | ((UnicodeScalarValue & 0x7C0) >> 6); 579 uint8_t SecondByte = 0x80 | (UnicodeScalarValue & 0x3F); 580 Result.push_back(FirstByte); 581 Result.push_back(SecondByte); 582 } else if (UnicodeScalarValue <= 0xFFFF) { 583 uint8_t FirstByte = 0xE0 | ((UnicodeScalarValue & 0xF000) >> 12); 584 uint8_t SecondByte = 0x80 | ((UnicodeScalarValue & 0xFC0) >> 6); 585 uint8_t ThirdByte = 0x80 | (UnicodeScalarValue & 0x3F); 586 Result.push_back(FirstByte); 587 Result.push_back(SecondByte); 588 Result.push_back(ThirdByte); 589 } else if (UnicodeScalarValue <= 0x10FFFF) { 590 uint8_t FirstByte = 0xF0 | ((UnicodeScalarValue & 0x1F0000) >> 18); 591 uint8_t SecondByte = 0x80 | ((UnicodeScalarValue & 0x3F000) >> 12); 592 uint8_t ThirdByte = 0x80 | ((UnicodeScalarValue & 0xFC0) >> 6); 593 uint8_t FourthByte = 0x80 | (UnicodeScalarValue & 0x3F); 594 Result.push_back(FirstByte); 595 Result.push_back(SecondByte); 596 Result.push_back(ThirdByte); 597 Result.push_back(FourthByte); 598 } 599 } 600 601 bool yaml::dumpTokens(StringRef Input, raw_ostream &OS) { 602 SourceMgr SM; 603 Scanner scanner(Input, SM); 604 while (true) { 605 Token T = scanner.getNext(); 606 switch (T.Kind) { 607 case Token::TK_StreamStart: 608 OS << "Stream-Start: "; 609 break; 610 case Token::TK_StreamEnd: 611 OS << "Stream-End: "; 612 break; 613 case Token::TK_VersionDirective: 614 OS << "Version-Directive: "; 615 break; 616 case Token::TK_TagDirective: 617 OS << "Tag-Directive: "; 618 break; 619 case Token::TK_DocumentStart: 620 OS << "Document-Start: "; 621 break; 622 case Token::TK_DocumentEnd: 623 OS << "Document-End: "; 624 break; 625 case Token::TK_BlockEntry: 626 OS << "Block-Entry: "; 627 break; 628 case Token::TK_BlockEnd: 629 OS << "Block-End: "; 630 break; 631 case Token::TK_BlockSequenceStart: 632 OS << "Block-Sequence-Start: "; 633 break; 634 case Token::TK_BlockMappingStart: 635 OS << "Block-Mapping-Start: "; 636 break; 637 case Token::TK_FlowEntry: 638 OS << "Flow-Entry: "; 639 break; 640 case Token::TK_FlowSequenceStart: 641 OS << "Flow-Sequence-Start: "; 642 break; 643 case Token::TK_FlowSequenceEnd: 644 OS << "Flow-Sequence-End: "; 645 break; 646 case Token::TK_FlowMappingStart: 647 OS << "Flow-Mapping-Start: "; 648 break; 649 case Token::TK_FlowMappingEnd: 650 OS << "Flow-Mapping-End: "; 651 break; 652 case Token::TK_Key: 653 OS << "Key: "; 654 break; 655 case Token::TK_Value: 656 OS << "Value: "; 657 break; 658 case Token::TK_Scalar: 659 OS << "Scalar: "; 660 break; 661 case Token::TK_BlockScalar: 662 OS << "Block Scalar: "; 663 break; 664 case Token::TK_Alias: 665 OS << "Alias: "; 666 break; 667 case Token::TK_Anchor: 668 OS << "Anchor: "; 669 break; 670 case Token::TK_Tag: 671 OS << "Tag: "; 672 break; 673 case Token::TK_Error: 674 break; 675 } 676 OS << T.Range << "\n"; 677 if (T.Kind == Token::TK_StreamEnd) 678 break; 679 else if (T.Kind == Token::TK_Error) 680 return false; 681 } 682 return true; 683 } 684 685 bool yaml::scanTokens(StringRef Input) { 686 llvm::SourceMgr SM; 687 llvm::yaml::Scanner scanner(Input, SM); 688 for (;;) { 689 llvm::yaml::Token T = scanner.getNext(); 690 if (T.Kind == Token::TK_StreamEnd) 691 break; 692 else if (T.Kind == Token::TK_Error) 693 return false; 694 } 695 return true; 696 } 697 698 std::string yaml::escape(StringRef Input) { 699 std::string EscapedInput; 700 for (StringRef::iterator i = Input.begin(), e = Input.end(); i != e; ++i) { 701 if (*i == '\\') 702 EscapedInput += "\\\\"; 703 else if (*i == '"') 704 EscapedInput += "\\\""; 705 else if (*i == 0) 706 EscapedInput += "\\0"; 707 else if (*i == 0x07) 708 EscapedInput += "\\a"; 709 else if (*i == 0x08) 710 EscapedInput += "\\b"; 711 else if (*i == 0x09) 712 EscapedInput += "\\t"; 713 else if (*i == 0x0A) 714 EscapedInput += "\\n"; 715 else if (*i == 0x0B) 716 EscapedInput += "\\v"; 717 else if (*i == 0x0C) 718 EscapedInput += "\\f"; 719 else if (*i == 0x0D) 720 EscapedInput += "\\r"; 721 else if (*i == 0x1B) 722 EscapedInput += "\\e"; 723 else if ((unsigned char)*i < 0x20) { // Control characters not handled above. 724 std::string HexStr = utohexstr(*i); 725 EscapedInput += "\\x" + std::string(2 - HexStr.size(), '0') + HexStr; 726 } else if (*i & 0x80) { // UTF-8 multiple code unit subsequence. 727 UTF8Decoded UnicodeScalarValue 728 = decodeUTF8(StringRef(i, Input.end() - i)); 729 if (UnicodeScalarValue.second == 0) { 730 // Found invalid char. 731 SmallString<4> Val; 732 encodeUTF8(0xFFFD, Val); 733 EscapedInput.insert(EscapedInput.end(), Val.begin(), Val.end()); 734 // FIXME: Error reporting. 735 return EscapedInput; 736 } 737 if (UnicodeScalarValue.first == 0x85) 738 EscapedInput += "\\N"; 739 else if (UnicodeScalarValue.first == 0xA0) 740 EscapedInput += "\\_"; 741 else if (UnicodeScalarValue.first == 0x2028) 742 EscapedInput += "\\L"; 743 else if (UnicodeScalarValue.first == 0x2029) 744 EscapedInput += "\\P"; 745 else { 746 std::string HexStr = utohexstr(UnicodeScalarValue.first); 747 if (HexStr.size() <= 2) 748 EscapedInput += "\\x" + std::string(2 - HexStr.size(), '0') + HexStr; 749 else if (HexStr.size() <= 4) 750 EscapedInput += "\\u" + std::string(4 - HexStr.size(), '0') + HexStr; 751 else if (HexStr.size() <= 8) 752 EscapedInput += "\\U" + std::string(8 - HexStr.size(), '0') + HexStr; 753 } 754 i += UnicodeScalarValue.second - 1; 755 } else 756 EscapedInput.push_back(*i); 757 } 758 return EscapedInput; 759 } 760 761 Scanner::Scanner(StringRef Input, SourceMgr &sm, bool ShowColors) 762 : SM(sm), ShowColors(ShowColors) { 763 init(MemoryBufferRef(Input, "YAML")); 764 } 765 766 Scanner::Scanner(MemoryBufferRef Buffer, SourceMgr &SM_, bool ShowColors) 767 : SM(SM_), ShowColors(ShowColors) { 768 init(Buffer); 769 } 770 771 void Scanner::init(MemoryBufferRef Buffer) { 772 InputBuffer = Buffer; 773 Current = InputBuffer.getBufferStart(); 774 End = InputBuffer.getBufferEnd(); 775 Indent = -1; 776 Column = 0; 777 Line = 0; 778 FlowLevel = 0; 779 IsStartOfStream = true; 780 IsSimpleKeyAllowed = true; 781 Failed = false; 782 std::unique_ptr<MemoryBuffer> InputBufferOwner = 783 MemoryBuffer::getMemBuffer(Buffer); 784 SM.AddNewSourceBuffer(std::move(InputBufferOwner), SMLoc()); 785 } 786 787 Token &Scanner::peekNext() { 788 // If the current token is a possible simple key, keep parsing until we 789 // can confirm. 790 bool NeedMore = false; 791 while (true) { 792 if (TokenQueue.empty() || NeedMore) { 793 if (!fetchMoreTokens()) { 794 TokenQueue.clear(); 795 TokenQueue.push_back(Token()); 796 return TokenQueue.front(); 797 } 798 } 799 assert(!TokenQueue.empty() && 800 "fetchMoreTokens lied about getting tokens!"); 801 802 removeStaleSimpleKeyCandidates(); 803 SimpleKey SK; 804 SK.Tok = TokenQueue.begin(); 805 if (std::find(SimpleKeys.begin(), SimpleKeys.end(), SK) 806 == SimpleKeys.end()) 807 break; 808 else 809 NeedMore = true; 810 } 811 return TokenQueue.front(); 812 } 813 814 Token Scanner::getNext() { 815 Token Ret = peekNext(); 816 // TokenQueue can be empty if there was an error getting the next token. 817 if (!TokenQueue.empty()) 818 TokenQueue.pop_front(); 819 820 // There cannot be any referenced Token's if the TokenQueue is empty. So do a 821 // quick deallocation of them all. 822 if (TokenQueue.empty()) { 823 TokenQueue.Alloc.Reset(); 824 } 825 826 return Ret; 827 } 828 829 StringRef::iterator Scanner::skip_nb_char(StringRef::iterator Position) { 830 if (Position == End) 831 return Position; 832 // Check 7 bit c-printable - b-char. 833 if ( *Position == 0x09 834 || (*Position >= 0x20 && *Position <= 0x7E)) 835 return Position + 1; 836 837 // Check for valid UTF-8. 838 if (uint8_t(*Position) & 0x80) { 839 UTF8Decoded u8d = decodeUTF8(Position); 840 if ( u8d.second != 0 841 && u8d.first != 0xFEFF 842 && ( u8d.first == 0x85 843 || ( u8d.first >= 0xA0 844 && u8d.first <= 0xD7FF) 845 || ( u8d.first >= 0xE000 846 && u8d.first <= 0xFFFD) 847 || ( u8d.first >= 0x10000 848 && u8d.first <= 0x10FFFF))) 849 return Position + u8d.second; 850 } 851 return Position; 852 } 853 854 StringRef::iterator Scanner::skip_b_break(StringRef::iterator Position) { 855 if (Position == End) 856 return Position; 857 if (*Position == 0x0D) { 858 if (Position + 1 != End && *(Position + 1) == 0x0A) 859 return Position + 2; 860 return Position + 1; 861 } 862 863 if (*Position == 0x0A) 864 return Position + 1; 865 return Position; 866 } 867 868 StringRef::iterator Scanner::skip_s_space(StringRef::iterator Position) { 869 if (Position == End) 870 return Position; 871 if (*Position == ' ') 872 return Position + 1; 873 return Position; 874 } 875 876 StringRef::iterator Scanner::skip_s_white(StringRef::iterator Position) { 877 if (Position == End) 878 return Position; 879 if (*Position == ' ' || *Position == '\t') 880 return Position + 1; 881 return Position; 882 } 883 884 StringRef::iterator Scanner::skip_ns_char(StringRef::iterator Position) { 885 if (Position == End) 886 return Position; 887 if (*Position == ' ' || *Position == '\t') 888 return Position; 889 return skip_nb_char(Position); 890 } 891 892 StringRef::iterator Scanner::skip_while( SkipWhileFunc Func 893 , StringRef::iterator Position) { 894 while (true) { 895 StringRef::iterator i = (this->*Func)(Position); 896 if (i == Position) 897 break; 898 Position = i; 899 } 900 return Position; 901 } 902 903 void Scanner::advanceWhile(SkipWhileFunc Func) { 904 auto Final = skip_while(Func, Current); 905 Column += Final - Current; 906 Current = Final; 907 } 908 909 static bool is_ns_hex_digit(const char C) { 910 return (C >= '0' && C <= '9') 911 || (C >= 'a' && C <= 'z') 912 || (C >= 'A' && C <= 'Z'); 913 } 914 915 static bool is_ns_word_char(const char C) { 916 return C == '-' 917 || (C >= 'a' && C <= 'z') 918 || (C >= 'A' && C <= 'Z'); 919 } 920 921 StringRef Scanner::scan_ns_uri_char() { 922 StringRef::iterator Start = Current; 923 while (true) { 924 if (Current == End) 925 break; 926 if (( *Current == '%' 927 && Current + 2 < End 928 && is_ns_hex_digit(*(Current + 1)) 929 && is_ns_hex_digit(*(Current + 2))) 930 || is_ns_word_char(*Current) 931 || StringRef(Current, 1).find_first_of("#;/?:@&=+$,_.!~*'()[]") 932 != StringRef::npos) { 933 ++Current; 934 ++Column; 935 } else 936 break; 937 } 938 return StringRef(Start, Current - Start); 939 } 940 941 bool Scanner::consume(uint32_t Expected) { 942 if (Expected >= 0x80) 943 report_fatal_error("Not dealing with this yet"); 944 if (Current == End) 945 return false; 946 if (uint8_t(*Current) >= 0x80) 947 report_fatal_error("Not dealing with this yet"); 948 if (uint8_t(*Current) == Expected) { 949 ++Current; 950 ++Column; 951 return true; 952 } 953 return false; 954 } 955 956 void Scanner::skip(uint32_t Distance) { 957 Current += Distance; 958 Column += Distance; 959 assert(Current <= End && "Skipped past the end"); 960 } 961 962 bool Scanner::isBlankOrBreak(StringRef::iterator Position) { 963 if (Position == End) 964 return false; 965 return *Position == ' ' || *Position == '\t' || *Position == '\r' || 966 *Position == '\n'; 967 } 968 969 bool Scanner::consumeLineBreakIfPresent() { 970 auto Next = skip_b_break(Current); 971 if (Next == Current) 972 return false; 973 Column = 0; 974 ++Line; 975 Current = Next; 976 return true; 977 } 978 979 void Scanner::saveSimpleKeyCandidate( TokenQueueT::iterator Tok 980 , unsigned AtColumn 981 , bool IsRequired) { 982 if (IsSimpleKeyAllowed) { 983 SimpleKey SK; 984 SK.Tok = Tok; 985 SK.Line = Line; 986 SK.Column = AtColumn; 987 SK.IsRequired = IsRequired; 988 SK.FlowLevel = FlowLevel; 989 SimpleKeys.push_back(SK); 990 } 991 } 992 993 void Scanner::removeStaleSimpleKeyCandidates() { 994 for (SmallVectorImpl<SimpleKey>::iterator i = SimpleKeys.begin(); 995 i != SimpleKeys.end();) { 996 if (i->Line != Line || i->Column + 1024 < Column) { 997 if (i->IsRequired) 998 setError( "Could not find expected : for simple key" 999 , i->Tok->Range.begin()); 1000 i = SimpleKeys.erase(i); 1001 } else 1002 ++i; 1003 } 1004 } 1005 1006 void Scanner::removeSimpleKeyCandidatesOnFlowLevel(unsigned Level) { 1007 if (!SimpleKeys.empty() && (SimpleKeys.end() - 1)->FlowLevel == Level) 1008 SimpleKeys.pop_back(); 1009 } 1010 1011 bool Scanner::unrollIndent(int ToColumn) { 1012 Token T; 1013 // Indentation is ignored in flow. 1014 if (FlowLevel != 0) 1015 return true; 1016 1017 while (Indent > ToColumn) { 1018 T.Kind = Token::TK_BlockEnd; 1019 T.Range = StringRef(Current, 1); 1020 TokenQueue.push_back(T); 1021 Indent = Indents.pop_back_val(); 1022 } 1023 1024 return true; 1025 } 1026 1027 bool Scanner::rollIndent( int ToColumn 1028 , Token::TokenKind Kind 1029 , TokenQueueT::iterator InsertPoint) { 1030 if (FlowLevel) 1031 return true; 1032 if (Indent < ToColumn) { 1033 Indents.push_back(Indent); 1034 Indent = ToColumn; 1035 1036 Token T; 1037 T.Kind = Kind; 1038 T.Range = StringRef(Current, 0); 1039 TokenQueue.insert(InsertPoint, T); 1040 } 1041 return true; 1042 } 1043 1044 void Scanner::skipComment() { 1045 if (*Current != '#') 1046 return; 1047 while (true) { 1048 // This may skip more than one byte, thus Column is only incremented 1049 // for code points. 1050 StringRef::iterator I = skip_nb_char(Current); 1051 if (I == Current) 1052 break; 1053 Current = I; 1054 ++Column; 1055 } 1056 } 1057 1058 void Scanner::scanToNextToken() { 1059 while (true) { 1060 while (*Current == ' ' || *Current == '\t') { 1061 skip(1); 1062 } 1063 1064 skipComment(); 1065 1066 // Skip EOL. 1067 StringRef::iterator i = skip_b_break(Current); 1068 if (i == Current) 1069 break; 1070 Current = i; 1071 ++Line; 1072 Column = 0; 1073 // New lines may start a simple key. 1074 if (!FlowLevel) 1075 IsSimpleKeyAllowed = true; 1076 } 1077 } 1078 1079 bool Scanner::scanStreamStart() { 1080 IsStartOfStream = false; 1081 1082 EncodingInfo EI = getUnicodeEncoding(currentInput()); 1083 1084 Token T; 1085 T.Kind = Token::TK_StreamStart; 1086 T.Range = StringRef(Current, EI.second); 1087 TokenQueue.push_back(T); 1088 Current += EI.second; 1089 return true; 1090 } 1091 1092 bool Scanner::scanStreamEnd() { 1093 // Force an ending new line if one isn't present. 1094 if (Column != 0) { 1095 Column = 0; 1096 ++Line; 1097 } 1098 1099 unrollIndent(-1); 1100 SimpleKeys.clear(); 1101 IsSimpleKeyAllowed = false; 1102 1103 Token T; 1104 T.Kind = Token::TK_StreamEnd; 1105 T.Range = StringRef(Current, 0); 1106 TokenQueue.push_back(T); 1107 return true; 1108 } 1109 1110 bool Scanner::scanDirective() { 1111 // Reset the indentation level. 1112 unrollIndent(-1); 1113 SimpleKeys.clear(); 1114 IsSimpleKeyAllowed = false; 1115 1116 StringRef::iterator Start = Current; 1117 consume('%'); 1118 StringRef::iterator NameStart = Current; 1119 Current = skip_while(&Scanner::skip_ns_char, Current); 1120 StringRef Name(NameStart, Current - NameStart); 1121 Current = skip_while(&Scanner::skip_s_white, Current); 1122 1123 Token T; 1124 if (Name == "YAML") { 1125 Current = skip_while(&Scanner::skip_ns_char, Current); 1126 T.Kind = Token::TK_VersionDirective; 1127 T.Range = StringRef(Start, Current - Start); 1128 TokenQueue.push_back(T); 1129 return true; 1130 } else if(Name == "TAG") { 1131 Current = skip_while(&Scanner::skip_ns_char, Current); 1132 Current = skip_while(&Scanner::skip_s_white, Current); 1133 Current = skip_while(&Scanner::skip_ns_char, Current); 1134 T.Kind = Token::TK_TagDirective; 1135 T.Range = StringRef(Start, Current - Start); 1136 TokenQueue.push_back(T); 1137 return true; 1138 } 1139 return false; 1140 } 1141 1142 bool Scanner::scanDocumentIndicator(bool IsStart) { 1143 unrollIndent(-1); 1144 SimpleKeys.clear(); 1145 IsSimpleKeyAllowed = false; 1146 1147 Token T; 1148 T.Kind = IsStart ? Token::TK_DocumentStart : Token::TK_DocumentEnd; 1149 T.Range = StringRef(Current, 3); 1150 skip(3); 1151 TokenQueue.push_back(T); 1152 return true; 1153 } 1154 1155 bool Scanner::scanFlowCollectionStart(bool IsSequence) { 1156 Token T; 1157 T.Kind = IsSequence ? Token::TK_FlowSequenceStart 1158 : Token::TK_FlowMappingStart; 1159 T.Range = StringRef(Current, 1); 1160 skip(1); 1161 TokenQueue.push_back(T); 1162 1163 // [ and { may begin a simple key. 1164 saveSimpleKeyCandidate(--TokenQueue.end(), Column - 1, false); 1165 1166 // And may also be followed by a simple key. 1167 IsSimpleKeyAllowed = true; 1168 ++FlowLevel; 1169 return true; 1170 } 1171 1172 bool Scanner::scanFlowCollectionEnd(bool IsSequence) { 1173 removeSimpleKeyCandidatesOnFlowLevel(FlowLevel); 1174 IsSimpleKeyAllowed = false; 1175 Token T; 1176 T.Kind = IsSequence ? Token::TK_FlowSequenceEnd 1177 : Token::TK_FlowMappingEnd; 1178 T.Range = StringRef(Current, 1); 1179 skip(1); 1180 TokenQueue.push_back(T); 1181 if (FlowLevel) 1182 --FlowLevel; 1183 return true; 1184 } 1185 1186 bool Scanner::scanFlowEntry() { 1187 removeSimpleKeyCandidatesOnFlowLevel(FlowLevel); 1188 IsSimpleKeyAllowed = true; 1189 Token T; 1190 T.Kind = Token::TK_FlowEntry; 1191 T.Range = StringRef(Current, 1); 1192 skip(1); 1193 TokenQueue.push_back(T); 1194 return true; 1195 } 1196 1197 bool Scanner::scanBlockEntry() { 1198 rollIndent(Column, Token::TK_BlockSequenceStart, TokenQueue.end()); 1199 removeSimpleKeyCandidatesOnFlowLevel(FlowLevel); 1200 IsSimpleKeyAllowed = true; 1201 Token T; 1202 T.Kind = Token::TK_BlockEntry; 1203 T.Range = StringRef(Current, 1); 1204 skip(1); 1205 TokenQueue.push_back(T); 1206 return true; 1207 } 1208 1209 bool Scanner::scanKey() { 1210 if (!FlowLevel) 1211 rollIndent(Column, Token::TK_BlockMappingStart, TokenQueue.end()); 1212 1213 removeSimpleKeyCandidatesOnFlowLevel(FlowLevel); 1214 IsSimpleKeyAllowed = !FlowLevel; 1215 1216 Token T; 1217 T.Kind = Token::TK_Key; 1218 T.Range = StringRef(Current, 1); 1219 skip(1); 1220 TokenQueue.push_back(T); 1221 return true; 1222 } 1223 1224 bool Scanner::scanValue() { 1225 // If the previous token could have been a simple key, insert the key token 1226 // into the token queue. 1227 if (!SimpleKeys.empty()) { 1228 SimpleKey SK = SimpleKeys.pop_back_val(); 1229 Token T; 1230 T.Kind = Token::TK_Key; 1231 T.Range = SK.Tok->Range; 1232 TokenQueueT::iterator i, e; 1233 for (i = TokenQueue.begin(), e = TokenQueue.end(); i != e; ++i) { 1234 if (i == SK.Tok) 1235 break; 1236 } 1237 assert(i != e && "SimpleKey not in token queue!"); 1238 i = TokenQueue.insert(i, T); 1239 1240 // We may also need to add a Block-Mapping-Start token. 1241 rollIndent(SK.Column, Token::TK_BlockMappingStart, i); 1242 1243 IsSimpleKeyAllowed = false; 1244 } else { 1245 if (!FlowLevel) 1246 rollIndent(Column, Token::TK_BlockMappingStart, TokenQueue.end()); 1247 IsSimpleKeyAllowed = !FlowLevel; 1248 } 1249 1250 Token T; 1251 T.Kind = Token::TK_Value; 1252 T.Range = StringRef(Current, 1); 1253 skip(1); 1254 TokenQueue.push_back(T); 1255 return true; 1256 } 1257 1258 // Forbidding inlining improves performance by roughly 20%. 1259 // FIXME: Remove once llvm optimizes this to the faster version without hints. 1260 LLVM_ATTRIBUTE_NOINLINE static bool 1261 wasEscaped(StringRef::iterator First, StringRef::iterator Position); 1262 1263 // Returns whether a character at 'Position' was escaped with a leading '\'. 1264 // 'First' specifies the position of the first character in the string. 1265 static bool wasEscaped(StringRef::iterator First, 1266 StringRef::iterator Position) { 1267 assert(Position - 1 >= First); 1268 StringRef::iterator I = Position - 1; 1269 // We calculate the number of consecutive '\'s before the current position 1270 // by iterating backwards through our string. 1271 while (I >= First && *I == '\\') --I; 1272 // (Position - 1 - I) now contains the number of '\'s before the current 1273 // position. If it is odd, the character at 'Position' was escaped. 1274 return (Position - 1 - I) % 2 == 1; 1275 } 1276 1277 bool Scanner::scanFlowScalar(bool IsDoubleQuoted) { 1278 StringRef::iterator Start = Current; 1279 unsigned ColStart = Column; 1280 if (IsDoubleQuoted) { 1281 do { 1282 ++Current; 1283 while (Current != End && *Current != '"') 1284 ++Current; 1285 // Repeat until the previous character was not a '\' or was an escaped 1286 // backslash. 1287 } while ( Current != End 1288 && *(Current - 1) == '\\' 1289 && wasEscaped(Start + 1, Current)); 1290 } else { 1291 skip(1); 1292 while (true) { 1293 // Skip a ' followed by another '. 1294 if (Current + 1 < End && *Current == '\'' && *(Current + 1) == '\'') { 1295 skip(2); 1296 continue; 1297 } else if (*Current == '\'') 1298 break; 1299 StringRef::iterator i = skip_nb_char(Current); 1300 if (i == Current) { 1301 i = skip_b_break(Current); 1302 if (i == Current) 1303 break; 1304 Current = i; 1305 Column = 0; 1306 ++Line; 1307 } else { 1308 if (i == End) 1309 break; 1310 Current = i; 1311 ++Column; 1312 } 1313 } 1314 } 1315 1316 if (Current == End) { 1317 setError("Expected quote at end of scalar", Current); 1318 return false; 1319 } 1320 1321 skip(1); // Skip ending quote. 1322 Token T; 1323 T.Kind = Token::TK_Scalar; 1324 T.Range = StringRef(Start, Current - Start); 1325 TokenQueue.push_back(T); 1326 1327 saveSimpleKeyCandidate(--TokenQueue.end(), ColStart, false); 1328 1329 IsSimpleKeyAllowed = false; 1330 1331 return true; 1332 } 1333 1334 bool Scanner::scanPlainScalar() { 1335 StringRef::iterator Start = Current; 1336 unsigned ColStart = Column; 1337 unsigned LeadingBlanks = 0; 1338 assert(Indent >= -1 && "Indent must be >= -1 !"); 1339 unsigned indent = static_cast<unsigned>(Indent + 1); 1340 while (true) { 1341 if (*Current == '#') 1342 break; 1343 1344 while (!isBlankOrBreak(Current)) { 1345 if ( FlowLevel && *Current == ':' 1346 && !(isBlankOrBreak(Current + 1) || *(Current + 1) == ',')) { 1347 setError("Found unexpected ':' while scanning a plain scalar", Current); 1348 return false; 1349 } 1350 1351 // Check for the end of the plain scalar. 1352 if ( (*Current == ':' && isBlankOrBreak(Current + 1)) 1353 || ( FlowLevel 1354 && (StringRef(Current, 1).find_first_of(",:?[]{}") 1355 != StringRef::npos))) 1356 break; 1357 1358 StringRef::iterator i = skip_nb_char(Current); 1359 if (i == Current) 1360 break; 1361 Current = i; 1362 ++Column; 1363 } 1364 1365 // Are we at the end? 1366 if (!isBlankOrBreak(Current)) 1367 break; 1368 1369 // Eat blanks. 1370 StringRef::iterator Tmp = Current; 1371 while (isBlankOrBreak(Tmp)) { 1372 StringRef::iterator i = skip_s_white(Tmp); 1373 if (i != Tmp) { 1374 if (LeadingBlanks && (Column < indent) && *Tmp == '\t') { 1375 setError("Found invalid tab character in indentation", Tmp); 1376 return false; 1377 } 1378 Tmp = i; 1379 ++Column; 1380 } else { 1381 i = skip_b_break(Tmp); 1382 if (!LeadingBlanks) 1383 LeadingBlanks = 1; 1384 Tmp = i; 1385 Column = 0; 1386 ++Line; 1387 } 1388 } 1389 1390 if (!FlowLevel && Column < indent) 1391 break; 1392 1393 Current = Tmp; 1394 } 1395 if (Start == Current) { 1396 setError("Got empty plain scalar", Start); 1397 return false; 1398 } 1399 Token T; 1400 T.Kind = Token::TK_Scalar; 1401 T.Range = StringRef(Start, Current - Start); 1402 TokenQueue.push_back(T); 1403 1404 // Plain scalars can be simple keys. 1405 saveSimpleKeyCandidate(--TokenQueue.end(), ColStart, false); 1406 1407 IsSimpleKeyAllowed = false; 1408 1409 return true; 1410 } 1411 1412 bool Scanner::scanAliasOrAnchor(bool IsAlias) { 1413 StringRef::iterator Start = Current; 1414 unsigned ColStart = Column; 1415 skip(1); 1416 while(true) { 1417 if ( *Current == '[' || *Current == ']' 1418 || *Current == '{' || *Current == '}' 1419 || *Current == ',' 1420 || *Current == ':') 1421 break; 1422 StringRef::iterator i = skip_ns_char(Current); 1423 if (i == Current) 1424 break; 1425 Current = i; 1426 ++Column; 1427 } 1428 1429 if (Start == Current) { 1430 setError("Got empty alias or anchor", Start); 1431 return false; 1432 } 1433 1434 Token T; 1435 T.Kind = IsAlias ? Token::TK_Alias : Token::TK_Anchor; 1436 T.Range = StringRef(Start, Current - Start); 1437 TokenQueue.push_back(T); 1438 1439 // Alias and anchors can be simple keys. 1440 saveSimpleKeyCandidate(--TokenQueue.end(), ColStart, false); 1441 1442 IsSimpleKeyAllowed = false; 1443 1444 return true; 1445 } 1446 1447 char Scanner::scanBlockChompingIndicator() { 1448 char Indicator = ' '; 1449 if (Current != End && (*Current == '+' || *Current == '-')) { 1450 Indicator = *Current; 1451 skip(1); 1452 } 1453 return Indicator; 1454 } 1455 1456 /// Get the number of line breaks after chomping. 1457 /// 1458 /// Return the number of trailing line breaks to emit, depending on 1459 /// \p ChompingIndicator. 1460 static unsigned getChompedLineBreaks(char ChompingIndicator, 1461 unsigned LineBreaks, StringRef Str) { 1462 if (ChompingIndicator == '-') // Strip all line breaks. 1463 return 0; 1464 if (ChompingIndicator == '+') // Keep all line breaks. 1465 return LineBreaks; 1466 // Clip trailing lines. 1467 return Str.empty() ? 0 : 1; 1468 } 1469 1470 unsigned Scanner::scanBlockIndentationIndicator() { 1471 unsigned Indent = 0; 1472 if (Current != End && (*Current >= '1' && *Current <= '9')) { 1473 Indent = unsigned(*Current - '0'); 1474 skip(1); 1475 } 1476 return Indent; 1477 } 1478 1479 bool Scanner::scanBlockScalarHeader(char &ChompingIndicator, 1480 unsigned &IndentIndicator, bool &IsDone) { 1481 auto Start = Current; 1482 1483 ChompingIndicator = scanBlockChompingIndicator(); 1484 IndentIndicator = scanBlockIndentationIndicator(); 1485 // Check for the chomping indicator once again. 1486 if (ChompingIndicator == ' ') 1487 ChompingIndicator = scanBlockChompingIndicator(); 1488 Current = skip_while(&Scanner::skip_s_white, Current); 1489 skipComment(); 1490 1491 if (Current == End) { // EOF, we have an empty scalar. 1492 Token T; 1493 T.Kind = Token::TK_BlockScalar; 1494 T.Range = StringRef(Start, Current - Start); 1495 TokenQueue.push_back(T); 1496 IsDone = true; 1497 return true; 1498 } 1499 1500 if (!consumeLineBreakIfPresent()) { 1501 setError("Expected a line break after block scalar header", Current); 1502 return false; 1503 } 1504 return true; 1505 } 1506 1507 bool Scanner::findBlockScalarIndent(unsigned &BlockIndent, 1508 unsigned BlockExitIndent, 1509 unsigned &LineBreaks, bool &IsDone) { 1510 unsigned MaxAllSpaceLineCharacters = 0; 1511 StringRef::iterator LongestAllSpaceLine; 1512 1513 while (true) { 1514 advanceWhile(&Scanner::skip_s_space); 1515 if (skip_nb_char(Current) != Current) { 1516 // This line isn't empty, so try and find the indentation. 1517 if (Column <= BlockExitIndent) { // End of the block literal. 1518 IsDone = true; 1519 return true; 1520 } 1521 // We found the block's indentation. 1522 BlockIndent = Column; 1523 if (MaxAllSpaceLineCharacters > BlockIndent) { 1524 setError( 1525 "Leading all-spaces line must be smaller than the block indent", 1526 LongestAllSpaceLine); 1527 return false; 1528 } 1529 return true; 1530 } 1531 if (skip_b_break(Current) != Current && 1532 Column > MaxAllSpaceLineCharacters) { 1533 // Record the longest all-space line in case it's longer than the 1534 // discovered block indent. 1535 MaxAllSpaceLineCharacters = Column; 1536 LongestAllSpaceLine = Current; 1537 } 1538 1539 // Check for EOF. 1540 if (Current == End) { 1541 IsDone = true; 1542 return true; 1543 } 1544 1545 if (!consumeLineBreakIfPresent()) { 1546 IsDone = true; 1547 return true; 1548 } 1549 ++LineBreaks; 1550 } 1551 return true; 1552 } 1553 1554 bool Scanner::scanBlockScalarIndent(unsigned BlockIndent, 1555 unsigned BlockExitIndent, bool &IsDone) { 1556 // Skip the indentation. 1557 while (Column < BlockIndent) { 1558 auto I = skip_s_space(Current); 1559 if (I == Current) 1560 break; 1561 Current = I; 1562 ++Column; 1563 } 1564 1565 if (skip_nb_char(Current) == Current) 1566 return true; 1567 1568 if (Column <= BlockExitIndent) { // End of the block literal. 1569 IsDone = true; 1570 return true; 1571 } 1572 1573 if (Column < BlockIndent) { 1574 if (Current != End && *Current == '#') { // Trailing comment. 1575 IsDone = true; 1576 return true; 1577 } 1578 setError("A text line is less indented than the block scalar", Current); 1579 return false; 1580 } 1581 return true; // A normal text line. 1582 } 1583 1584 bool Scanner::scanBlockScalar(bool IsLiteral) { 1585 // Eat '|' or '>' 1586 assert(*Current == '|' || *Current == '>'); 1587 skip(1); 1588 1589 char ChompingIndicator; 1590 unsigned BlockIndent; 1591 bool IsDone = false; 1592 if (!scanBlockScalarHeader(ChompingIndicator, BlockIndent, IsDone)) 1593 return false; 1594 if (IsDone) 1595 return true; 1596 1597 auto Start = Current; 1598 unsigned BlockExitIndent = Indent < 0 ? 0 : (unsigned)Indent; 1599 unsigned LineBreaks = 0; 1600 if (BlockIndent == 0) { 1601 if (!findBlockScalarIndent(BlockIndent, BlockExitIndent, LineBreaks, 1602 IsDone)) 1603 return false; 1604 } 1605 1606 // Scan the block's scalars body. 1607 SmallString<256> Str; 1608 while (!IsDone) { 1609 if (!scanBlockScalarIndent(BlockIndent, BlockExitIndent, IsDone)) 1610 return false; 1611 if (IsDone) 1612 break; 1613 1614 // Parse the current line. 1615 auto LineStart = Current; 1616 advanceWhile(&Scanner::skip_nb_char); 1617 if (LineStart != Current) { 1618 Str.append(LineBreaks, '\n'); 1619 Str.append(StringRef(LineStart, Current - LineStart)); 1620 LineBreaks = 0; 1621 } 1622 1623 // Check for EOF. 1624 if (Current == End) 1625 break; 1626 1627 if (!consumeLineBreakIfPresent()) 1628 break; 1629 ++LineBreaks; 1630 } 1631 1632 if (Current == End && !LineBreaks) 1633 // Ensure that there is at least one line break before the end of file. 1634 LineBreaks = 1; 1635 Str.append(getChompedLineBreaks(ChompingIndicator, LineBreaks, Str), '\n'); 1636 1637 // New lines may start a simple key. 1638 if (!FlowLevel) 1639 IsSimpleKeyAllowed = true; 1640 1641 Token T; 1642 T.Kind = Token::TK_BlockScalar; 1643 T.Range = StringRef(Start, Current - Start); 1644 T.Value = Str.str().str(); 1645 TokenQueue.push_back(T); 1646 return true; 1647 } 1648 1649 bool Scanner::scanTag() { 1650 StringRef::iterator Start = Current; 1651 unsigned ColStart = Column; 1652 skip(1); // Eat !. 1653 if (Current == End || isBlankOrBreak(Current)); // An empty tag. 1654 else if (*Current == '<') { 1655 skip(1); 1656 scan_ns_uri_char(); 1657 if (!consume('>')) 1658 return false; 1659 } else { 1660 // FIXME: Actually parse the c-ns-shorthand-tag rule. 1661 Current = skip_while(&Scanner::skip_ns_char, Current); 1662 } 1663 1664 Token T; 1665 T.Kind = Token::TK_Tag; 1666 T.Range = StringRef(Start, Current - Start); 1667 TokenQueue.push_back(T); 1668 1669 // Tags can be simple keys. 1670 saveSimpleKeyCandidate(--TokenQueue.end(), ColStart, false); 1671 1672 IsSimpleKeyAllowed = false; 1673 1674 return true; 1675 } 1676 1677 bool Scanner::fetchMoreTokens() { 1678 if (IsStartOfStream) 1679 return scanStreamStart(); 1680 1681 scanToNextToken(); 1682 1683 if (Current == End) 1684 return scanStreamEnd(); 1685 1686 removeStaleSimpleKeyCandidates(); 1687 1688 unrollIndent(Column); 1689 1690 if (Column == 0 && *Current == '%') 1691 return scanDirective(); 1692 1693 if (Column == 0 && Current + 4 <= End 1694 && *Current == '-' 1695 && *(Current + 1) == '-' 1696 && *(Current + 2) == '-' 1697 && (Current + 3 == End || isBlankOrBreak(Current + 3))) 1698 return scanDocumentIndicator(true); 1699 1700 if (Column == 0 && Current + 4 <= End 1701 && *Current == '.' 1702 && *(Current + 1) == '.' 1703 && *(Current + 2) == '.' 1704 && (Current + 3 == End || isBlankOrBreak(Current + 3))) 1705 return scanDocumentIndicator(false); 1706 1707 if (*Current == '[') 1708 return scanFlowCollectionStart(true); 1709 1710 if (*Current == '{') 1711 return scanFlowCollectionStart(false); 1712 1713 if (*Current == ']') 1714 return scanFlowCollectionEnd(true); 1715 1716 if (*Current == '}') 1717 return scanFlowCollectionEnd(false); 1718 1719 if (*Current == ',') 1720 return scanFlowEntry(); 1721 1722 if (*Current == '-' && isBlankOrBreak(Current + 1)) 1723 return scanBlockEntry(); 1724 1725 if (*Current == '?' && (FlowLevel || isBlankOrBreak(Current + 1))) 1726 return scanKey(); 1727 1728 if (*Current == ':' && (FlowLevel || isBlankOrBreak(Current + 1))) 1729 return scanValue(); 1730 1731 if (*Current == '*') 1732 return scanAliasOrAnchor(true); 1733 1734 if (*Current == '&') 1735 return scanAliasOrAnchor(false); 1736 1737 if (*Current == '!') 1738 return scanTag(); 1739 1740 if (*Current == '|' && !FlowLevel) 1741 return scanBlockScalar(true); 1742 1743 if (*Current == '>' && !FlowLevel) 1744 return scanBlockScalar(false); 1745 1746 if (*Current == '\'') 1747 return scanFlowScalar(false); 1748 1749 if (*Current == '"') 1750 return scanFlowScalar(true); 1751 1752 // Get a plain scalar. 1753 StringRef FirstChar(Current, 1); 1754 if (!(isBlankOrBreak(Current) 1755 || FirstChar.find_first_of("-?:,[]{}#&*!|>'\"%@`") != StringRef::npos) 1756 || (*Current == '-' && !isBlankOrBreak(Current + 1)) 1757 || (!FlowLevel && (*Current == '?' || *Current == ':') 1758 && isBlankOrBreak(Current + 1)) 1759 || (!FlowLevel && *Current == ':' 1760 && Current + 2 < End 1761 && *(Current + 1) == ':' 1762 && !isBlankOrBreak(Current + 2))) 1763 return scanPlainScalar(); 1764 1765 setError("Unrecognized character while tokenizing."); 1766 return false; 1767 } 1768 1769 Stream::Stream(StringRef Input, SourceMgr &SM, bool ShowColors) 1770 : scanner(new Scanner(Input, SM, ShowColors)), CurrentDoc() {} 1771 1772 Stream::Stream(MemoryBufferRef InputBuffer, SourceMgr &SM, bool ShowColors) 1773 : scanner(new Scanner(InputBuffer, SM, ShowColors)), CurrentDoc() {} 1774 1775 Stream::~Stream() {} 1776 1777 bool Stream::failed() { return scanner->failed(); } 1778 1779 void Stream::printError(Node *N, const Twine &Msg) { 1780 scanner->printError( N->getSourceRange().Start 1781 , SourceMgr::DK_Error 1782 , Msg 1783 , N->getSourceRange()); 1784 } 1785 1786 document_iterator Stream::begin() { 1787 if (CurrentDoc) 1788 report_fatal_error("Can only iterate over the stream once"); 1789 1790 // Skip Stream-Start. 1791 scanner->getNext(); 1792 1793 CurrentDoc.reset(new Document(*this)); 1794 return document_iterator(CurrentDoc); 1795 } 1796 1797 document_iterator Stream::end() { 1798 return document_iterator(); 1799 } 1800 1801 void Stream::skip() { 1802 for (document_iterator i = begin(), e = end(); i != e; ++i) 1803 i->skip(); 1804 } 1805 1806 Node::Node(unsigned int Type, std::unique_ptr<Document> &D, StringRef A, 1807 StringRef T) 1808 : Doc(D), TypeID(Type), Anchor(A), Tag(T) { 1809 SMLoc Start = SMLoc::getFromPointer(peekNext().Range.begin()); 1810 SourceRange = SMRange(Start, Start); 1811 } 1812 1813 std::string Node::getVerbatimTag() const { 1814 StringRef Raw = getRawTag(); 1815 if (!Raw.empty() && Raw != "!") { 1816 std::string Ret; 1817 if (Raw.find_last_of('!') == 0) { 1818 Ret = Doc->getTagMap().find("!")->second; 1819 Ret += Raw.substr(1); 1820 return Ret; 1821 } else if (Raw.startswith("!!")) { 1822 Ret = Doc->getTagMap().find("!!")->second; 1823 Ret += Raw.substr(2); 1824 return Ret; 1825 } else { 1826 StringRef TagHandle = Raw.substr(0, Raw.find_last_of('!') + 1); 1827 std::map<StringRef, StringRef>::const_iterator It = 1828 Doc->getTagMap().find(TagHandle); 1829 if (It != Doc->getTagMap().end()) 1830 Ret = It->second; 1831 else { 1832 Token T; 1833 T.Kind = Token::TK_Tag; 1834 T.Range = TagHandle; 1835 setError(Twine("Unknown tag handle ") + TagHandle, T); 1836 } 1837 Ret += Raw.substr(Raw.find_last_of('!') + 1); 1838 return Ret; 1839 } 1840 } 1841 1842 switch (getType()) { 1843 case NK_Null: 1844 return "tag:yaml.org,2002:null"; 1845 case NK_Scalar: 1846 case NK_BlockScalar: 1847 // TODO: Tag resolution. 1848 return "tag:yaml.org,2002:str"; 1849 case NK_Mapping: 1850 return "tag:yaml.org,2002:map"; 1851 case NK_Sequence: 1852 return "tag:yaml.org,2002:seq"; 1853 } 1854 1855 return ""; 1856 } 1857 1858 Token &Node::peekNext() { 1859 return Doc->peekNext(); 1860 } 1861 1862 Token Node::getNext() { 1863 return Doc->getNext(); 1864 } 1865 1866 Node *Node::parseBlockNode() { 1867 return Doc->parseBlockNode(); 1868 } 1869 1870 BumpPtrAllocator &Node::getAllocator() { 1871 return Doc->NodeAllocator; 1872 } 1873 1874 void Node::setError(const Twine &Msg, Token &Tok) const { 1875 Doc->setError(Msg, Tok); 1876 } 1877 1878 bool Node::failed() const { 1879 return Doc->failed(); 1880 } 1881 1882 1883 1884 StringRef ScalarNode::getValue(SmallVectorImpl<char> &Storage) const { 1885 // TODO: Handle newlines properly. We need to remove leading whitespace. 1886 if (Value[0] == '"') { // Double quoted. 1887 // Pull off the leading and trailing "s. 1888 StringRef UnquotedValue = Value.substr(1, Value.size() - 2); 1889 // Search for characters that would require unescaping the value. 1890 StringRef::size_type i = UnquotedValue.find_first_of("\\\r\n"); 1891 if (i != StringRef::npos) 1892 return unescapeDoubleQuoted(UnquotedValue, i, Storage); 1893 return UnquotedValue; 1894 } else if (Value[0] == '\'') { // Single quoted. 1895 // Pull off the leading and trailing 's. 1896 StringRef UnquotedValue = Value.substr(1, Value.size() - 2); 1897 StringRef::size_type i = UnquotedValue.find('\''); 1898 if (i != StringRef::npos) { 1899 // We're going to need Storage. 1900 Storage.clear(); 1901 Storage.reserve(UnquotedValue.size()); 1902 for (; i != StringRef::npos; i = UnquotedValue.find('\'')) { 1903 StringRef Valid(UnquotedValue.begin(), i); 1904 Storage.insert(Storage.end(), Valid.begin(), Valid.end()); 1905 Storage.push_back('\''); 1906 UnquotedValue = UnquotedValue.substr(i + 2); 1907 } 1908 Storage.insert(Storage.end(), UnquotedValue.begin(), UnquotedValue.end()); 1909 return StringRef(Storage.begin(), Storage.size()); 1910 } 1911 return UnquotedValue; 1912 } 1913 // Plain or block. 1914 return Value.rtrim(' '); 1915 } 1916 1917 StringRef ScalarNode::unescapeDoubleQuoted( StringRef UnquotedValue 1918 , StringRef::size_type i 1919 , SmallVectorImpl<char> &Storage) 1920 const { 1921 // Use Storage to build proper value. 1922 Storage.clear(); 1923 Storage.reserve(UnquotedValue.size()); 1924 for (; i != StringRef::npos; i = UnquotedValue.find_first_of("\\\r\n")) { 1925 // Insert all previous chars into Storage. 1926 StringRef Valid(UnquotedValue.begin(), i); 1927 Storage.insert(Storage.end(), Valid.begin(), Valid.end()); 1928 // Chop off inserted chars. 1929 UnquotedValue = UnquotedValue.substr(i); 1930 1931 assert(!UnquotedValue.empty() && "Can't be empty!"); 1932 1933 // Parse escape or line break. 1934 switch (UnquotedValue[0]) { 1935 case '\r': 1936 case '\n': 1937 Storage.push_back('\n'); 1938 if ( UnquotedValue.size() > 1 1939 && (UnquotedValue[1] == '\r' || UnquotedValue[1] == '\n')) 1940 UnquotedValue = UnquotedValue.substr(1); 1941 UnquotedValue = UnquotedValue.substr(1); 1942 break; 1943 default: 1944 if (UnquotedValue.size() == 1) 1945 // TODO: Report error. 1946 break; 1947 UnquotedValue = UnquotedValue.substr(1); 1948 switch (UnquotedValue[0]) { 1949 default: { 1950 Token T; 1951 T.Range = StringRef(UnquotedValue.begin(), 1); 1952 setError("Unrecognized escape code!", T); 1953 return ""; 1954 } 1955 case '\r': 1956 case '\n': 1957 // Remove the new line. 1958 if ( UnquotedValue.size() > 1 1959 && (UnquotedValue[1] == '\r' || UnquotedValue[1] == '\n')) 1960 UnquotedValue = UnquotedValue.substr(1); 1961 // If this was just a single byte newline, it will get skipped 1962 // below. 1963 break; 1964 case '0': 1965 Storage.push_back(0x00); 1966 break; 1967 case 'a': 1968 Storage.push_back(0x07); 1969 break; 1970 case 'b': 1971 Storage.push_back(0x08); 1972 break; 1973 case 't': 1974 case 0x09: 1975 Storage.push_back(0x09); 1976 break; 1977 case 'n': 1978 Storage.push_back(0x0A); 1979 break; 1980 case 'v': 1981 Storage.push_back(0x0B); 1982 break; 1983 case 'f': 1984 Storage.push_back(0x0C); 1985 break; 1986 case 'r': 1987 Storage.push_back(0x0D); 1988 break; 1989 case 'e': 1990 Storage.push_back(0x1B); 1991 break; 1992 case ' ': 1993 Storage.push_back(0x20); 1994 break; 1995 case '"': 1996 Storage.push_back(0x22); 1997 break; 1998 case '/': 1999 Storage.push_back(0x2F); 2000 break; 2001 case '\\': 2002 Storage.push_back(0x5C); 2003 break; 2004 case 'N': 2005 encodeUTF8(0x85, Storage); 2006 break; 2007 case '_': 2008 encodeUTF8(0xA0, Storage); 2009 break; 2010 case 'L': 2011 encodeUTF8(0x2028, Storage); 2012 break; 2013 case 'P': 2014 encodeUTF8(0x2029, Storage); 2015 break; 2016 case 'x': { 2017 if (UnquotedValue.size() < 3) 2018 // TODO: Report error. 2019 break; 2020 unsigned int UnicodeScalarValue; 2021 if (UnquotedValue.substr(1, 2).getAsInteger(16, UnicodeScalarValue)) 2022 // TODO: Report error. 2023 UnicodeScalarValue = 0xFFFD; 2024 encodeUTF8(UnicodeScalarValue, Storage); 2025 UnquotedValue = UnquotedValue.substr(2); 2026 break; 2027 } 2028 case 'u': { 2029 if (UnquotedValue.size() < 5) 2030 // TODO: Report error. 2031 break; 2032 unsigned int UnicodeScalarValue; 2033 if (UnquotedValue.substr(1, 4).getAsInteger(16, UnicodeScalarValue)) 2034 // TODO: Report error. 2035 UnicodeScalarValue = 0xFFFD; 2036 encodeUTF8(UnicodeScalarValue, Storage); 2037 UnquotedValue = UnquotedValue.substr(4); 2038 break; 2039 } 2040 case 'U': { 2041 if (UnquotedValue.size() < 9) 2042 // TODO: Report error. 2043 break; 2044 unsigned int UnicodeScalarValue; 2045 if (UnquotedValue.substr(1, 8).getAsInteger(16, UnicodeScalarValue)) 2046 // TODO: Report error. 2047 UnicodeScalarValue = 0xFFFD; 2048 encodeUTF8(UnicodeScalarValue, Storage); 2049 UnquotedValue = UnquotedValue.substr(8); 2050 break; 2051 } 2052 } 2053 UnquotedValue = UnquotedValue.substr(1); 2054 } 2055 } 2056 Storage.insert(Storage.end(), UnquotedValue.begin(), UnquotedValue.end()); 2057 return StringRef(Storage.begin(), Storage.size()); 2058 } 2059 2060 Node *KeyValueNode::getKey() { 2061 if (Key) 2062 return Key; 2063 // Handle implicit null keys. 2064 { 2065 Token &t = peekNext(); 2066 if ( t.Kind == Token::TK_BlockEnd 2067 || t.Kind == Token::TK_Value 2068 || t.Kind == Token::TK_Error) { 2069 return Key = new (getAllocator()) NullNode(Doc); 2070 } 2071 if (t.Kind == Token::TK_Key) 2072 getNext(); // skip TK_Key. 2073 } 2074 2075 // Handle explicit null keys. 2076 Token &t = peekNext(); 2077 if (t.Kind == Token::TK_BlockEnd || t.Kind == Token::TK_Value) { 2078 return Key = new (getAllocator()) NullNode(Doc); 2079 } 2080 2081 // We've got a normal key. 2082 return Key = parseBlockNode(); 2083 } 2084 2085 Node *KeyValueNode::getValue() { 2086 if (Value) 2087 return Value; 2088 getKey()->skip(); 2089 if (failed()) 2090 return Value = new (getAllocator()) NullNode(Doc); 2091 2092 // Handle implicit null values. 2093 { 2094 Token &t = peekNext(); 2095 if ( t.Kind == Token::TK_BlockEnd 2096 || t.Kind == Token::TK_FlowMappingEnd 2097 || t.Kind == Token::TK_Key 2098 || t.Kind == Token::TK_FlowEntry 2099 || t.Kind == Token::TK_Error) { 2100 return Value = new (getAllocator()) NullNode(Doc); 2101 } 2102 2103 if (t.Kind != Token::TK_Value) { 2104 setError("Unexpected token in Key Value.", t); 2105 return Value = new (getAllocator()) NullNode(Doc); 2106 } 2107 getNext(); // skip TK_Value. 2108 } 2109 2110 // Handle explicit null values. 2111 Token &t = peekNext(); 2112 if (t.Kind == Token::TK_BlockEnd || t.Kind == Token::TK_Key) { 2113 return Value = new (getAllocator()) NullNode(Doc); 2114 } 2115 2116 // We got a normal value. 2117 return Value = parseBlockNode(); 2118 } 2119 2120 void MappingNode::increment() { 2121 if (failed()) { 2122 IsAtEnd = true; 2123 CurrentEntry = nullptr; 2124 return; 2125 } 2126 if (CurrentEntry) { 2127 CurrentEntry->skip(); 2128 if (Type == MT_Inline) { 2129 IsAtEnd = true; 2130 CurrentEntry = nullptr; 2131 return; 2132 } 2133 } 2134 Token T = peekNext(); 2135 if (T.Kind == Token::TK_Key || T.Kind == Token::TK_Scalar) { 2136 // KeyValueNode eats the TK_Key. That way it can detect null keys. 2137 CurrentEntry = new (getAllocator()) KeyValueNode(Doc); 2138 } else if (Type == MT_Block) { 2139 switch (T.Kind) { 2140 case Token::TK_BlockEnd: 2141 getNext(); 2142 IsAtEnd = true; 2143 CurrentEntry = nullptr; 2144 break; 2145 default: 2146 setError("Unexpected token. Expected Key or Block End", T); 2147 case Token::TK_Error: 2148 IsAtEnd = true; 2149 CurrentEntry = nullptr; 2150 } 2151 } else { 2152 switch (T.Kind) { 2153 case Token::TK_FlowEntry: 2154 // Eat the flow entry and recurse. 2155 getNext(); 2156 return increment(); 2157 case Token::TK_FlowMappingEnd: 2158 getNext(); 2159 case Token::TK_Error: 2160 // Set this to end iterator. 2161 IsAtEnd = true; 2162 CurrentEntry = nullptr; 2163 break; 2164 default: 2165 setError( "Unexpected token. Expected Key, Flow Entry, or Flow " 2166 "Mapping End." 2167 , T); 2168 IsAtEnd = true; 2169 CurrentEntry = nullptr; 2170 } 2171 } 2172 } 2173 2174 void SequenceNode::increment() { 2175 if (failed()) { 2176 IsAtEnd = true; 2177 CurrentEntry = nullptr; 2178 return; 2179 } 2180 if (CurrentEntry) 2181 CurrentEntry->skip(); 2182 Token T = peekNext(); 2183 if (SeqType == ST_Block) { 2184 switch (T.Kind) { 2185 case Token::TK_BlockEntry: 2186 getNext(); 2187 CurrentEntry = parseBlockNode(); 2188 if (!CurrentEntry) { // An error occurred. 2189 IsAtEnd = true; 2190 CurrentEntry = nullptr; 2191 } 2192 break; 2193 case Token::TK_BlockEnd: 2194 getNext(); 2195 IsAtEnd = true; 2196 CurrentEntry = nullptr; 2197 break; 2198 default: 2199 setError( "Unexpected token. Expected Block Entry or Block End." 2200 , T); 2201 case Token::TK_Error: 2202 IsAtEnd = true; 2203 CurrentEntry = nullptr; 2204 } 2205 } else if (SeqType == ST_Indentless) { 2206 switch (T.Kind) { 2207 case Token::TK_BlockEntry: 2208 getNext(); 2209 CurrentEntry = parseBlockNode(); 2210 if (!CurrentEntry) { // An error occurred. 2211 IsAtEnd = true; 2212 CurrentEntry = nullptr; 2213 } 2214 break; 2215 default: 2216 case Token::TK_Error: 2217 IsAtEnd = true; 2218 CurrentEntry = nullptr; 2219 } 2220 } else if (SeqType == ST_Flow) { 2221 switch (T.Kind) { 2222 case Token::TK_FlowEntry: 2223 // Eat the flow entry and recurse. 2224 getNext(); 2225 WasPreviousTokenFlowEntry = true; 2226 return increment(); 2227 case Token::TK_FlowSequenceEnd: 2228 getNext(); 2229 case Token::TK_Error: 2230 // Set this to end iterator. 2231 IsAtEnd = true; 2232 CurrentEntry = nullptr; 2233 break; 2234 case Token::TK_StreamEnd: 2235 case Token::TK_DocumentEnd: 2236 case Token::TK_DocumentStart: 2237 setError("Could not find closing ]!", T); 2238 // Set this to end iterator. 2239 IsAtEnd = true; 2240 CurrentEntry = nullptr; 2241 break; 2242 default: 2243 if (!WasPreviousTokenFlowEntry) { 2244 setError("Expected , between entries!", T); 2245 IsAtEnd = true; 2246 CurrentEntry = nullptr; 2247 break; 2248 } 2249 // Otherwise it must be a flow entry. 2250 CurrentEntry = parseBlockNode(); 2251 if (!CurrentEntry) { 2252 IsAtEnd = true; 2253 } 2254 WasPreviousTokenFlowEntry = false; 2255 break; 2256 } 2257 } 2258 } 2259 2260 Document::Document(Stream &S) : stream(S), Root(nullptr) { 2261 // Tag maps starts with two default mappings. 2262 TagMap["!"] = "!"; 2263 TagMap["!!"] = "tag:yaml.org,2002:"; 2264 2265 if (parseDirectives()) 2266 expectToken(Token::TK_DocumentStart); 2267 Token &T = peekNext(); 2268 if (T.Kind == Token::TK_DocumentStart) 2269 getNext(); 2270 } 2271 2272 bool Document::skip() { 2273 if (stream.scanner->failed()) 2274 return false; 2275 if (!Root) 2276 getRoot(); 2277 Root->skip(); 2278 Token &T = peekNext(); 2279 if (T.Kind == Token::TK_StreamEnd) 2280 return false; 2281 if (T.Kind == Token::TK_DocumentEnd) { 2282 getNext(); 2283 return skip(); 2284 } 2285 return true; 2286 } 2287 2288 Token &Document::peekNext() { 2289 return stream.scanner->peekNext(); 2290 } 2291 2292 Token Document::getNext() { 2293 return stream.scanner->getNext(); 2294 } 2295 2296 void Document::setError(const Twine &Message, Token &Location) const { 2297 stream.scanner->setError(Message, Location.Range.begin()); 2298 } 2299 2300 bool Document::failed() const { 2301 return stream.scanner->failed(); 2302 } 2303 2304 Node *Document::parseBlockNode() { 2305 Token T = peekNext(); 2306 // Handle properties. 2307 Token AnchorInfo; 2308 Token TagInfo; 2309 parse_property: 2310 switch (T.Kind) { 2311 case Token::TK_Alias: 2312 getNext(); 2313 return new (NodeAllocator) AliasNode(stream.CurrentDoc, T.Range.substr(1)); 2314 case Token::TK_Anchor: 2315 if (AnchorInfo.Kind == Token::TK_Anchor) { 2316 setError("Already encountered an anchor for this node!", T); 2317 return nullptr; 2318 } 2319 AnchorInfo = getNext(); // Consume TK_Anchor. 2320 T = peekNext(); 2321 goto parse_property; 2322 case Token::TK_Tag: 2323 if (TagInfo.Kind == Token::TK_Tag) { 2324 setError("Already encountered a tag for this node!", T); 2325 return nullptr; 2326 } 2327 TagInfo = getNext(); // Consume TK_Tag. 2328 T = peekNext(); 2329 goto parse_property; 2330 default: 2331 break; 2332 } 2333 2334 switch (T.Kind) { 2335 case Token::TK_BlockEntry: 2336 // We got an unindented BlockEntry sequence. This is not terminated with 2337 // a BlockEnd. 2338 // Don't eat the TK_BlockEntry, SequenceNode needs it. 2339 return new (NodeAllocator) SequenceNode( stream.CurrentDoc 2340 , AnchorInfo.Range.substr(1) 2341 , TagInfo.Range 2342 , SequenceNode::ST_Indentless); 2343 case Token::TK_BlockSequenceStart: 2344 getNext(); 2345 return new (NodeAllocator) 2346 SequenceNode( stream.CurrentDoc 2347 , AnchorInfo.Range.substr(1) 2348 , TagInfo.Range 2349 , SequenceNode::ST_Block); 2350 case Token::TK_BlockMappingStart: 2351 getNext(); 2352 return new (NodeAllocator) 2353 MappingNode( stream.CurrentDoc 2354 , AnchorInfo.Range.substr(1) 2355 , TagInfo.Range 2356 , MappingNode::MT_Block); 2357 case Token::TK_FlowSequenceStart: 2358 getNext(); 2359 return new (NodeAllocator) 2360 SequenceNode( stream.CurrentDoc 2361 , AnchorInfo.Range.substr(1) 2362 , TagInfo.Range 2363 , SequenceNode::ST_Flow); 2364 case Token::TK_FlowMappingStart: 2365 getNext(); 2366 return new (NodeAllocator) 2367 MappingNode( stream.CurrentDoc 2368 , AnchorInfo.Range.substr(1) 2369 , TagInfo.Range 2370 , MappingNode::MT_Flow); 2371 case Token::TK_Scalar: 2372 getNext(); 2373 return new (NodeAllocator) 2374 ScalarNode( stream.CurrentDoc 2375 , AnchorInfo.Range.substr(1) 2376 , TagInfo.Range 2377 , T.Range); 2378 case Token::TK_BlockScalar: { 2379 getNext(); 2380 StringRef NullTerminatedStr(T.Value.c_str(), T.Value.length() + 1); 2381 StringRef StrCopy = NullTerminatedStr.copy(NodeAllocator).drop_back(); 2382 return new (NodeAllocator) 2383 BlockScalarNode(stream.CurrentDoc, AnchorInfo.Range.substr(1), 2384 TagInfo.Range, StrCopy, T.Range); 2385 } 2386 case Token::TK_Key: 2387 // Don't eat the TK_Key, KeyValueNode expects it. 2388 return new (NodeAllocator) 2389 MappingNode( stream.CurrentDoc 2390 , AnchorInfo.Range.substr(1) 2391 , TagInfo.Range 2392 , MappingNode::MT_Inline); 2393 case Token::TK_DocumentStart: 2394 case Token::TK_DocumentEnd: 2395 case Token::TK_StreamEnd: 2396 default: 2397 // TODO: Properly handle tags. "[!!str ]" should resolve to !!str "", not 2398 // !!null null. 2399 return new (NodeAllocator) NullNode(stream.CurrentDoc); 2400 case Token::TK_Error: 2401 return nullptr; 2402 } 2403 llvm_unreachable("Control flow shouldn't reach here."); 2404 return nullptr; 2405 } 2406 2407 bool Document::parseDirectives() { 2408 bool isDirective = false; 2409 while (true) { 2410 Token T = peekNext(); 2411 if (T.Kind == Token::TK_TagDirective) { 2412 parseTAGDirective(); 2413 isDirective = true; 2414 } else if (T.Kind == Token::TK_VersionDirective) { 2415 parseYAMLDirective(); 2416 isDirective = true; 2417 } else 2418 break; 2419 } 2420 return isDirective; 2421 } 2422 2423 void Document::parseYAMLDirective() { 2424 getNext(); // Eat %YAML <version> 2425 } 2426 2427 void Document::parseTAGDirective() { 2428 Token Tag = getNext(); // %TAG <handle> <prefix> 2429 StringRef T = Tag.Range; 2430 // Strip %TAG 2431 T = T.substr(T.find_first_of(" \t")).ltrim(" \t"); 2432 std::size_t HandleEnd = T.find_first_of(" \t"); 2433 StringRef TagHandle = T.substr(0, HandleEnd); 2434 StringRef TagPrefix = T.substr(HandleEnd).ltrim(" \t"); 2435 TagMap[TagHandle] = TagPrefix; 2436 } 2437 2438 bool Document::expectToken(int TK) { 2439 Token T = getNext(); 2440 if (T.Kind != TK) { 2441 setError("Unexpected token", T); 2442 return false; 2443 } 2444 return true; 2445 } 2446