1 //===- YAMLParser.cpp - Simple YAML parser --------------------------------===//
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
7 //===----------------------------------------------------------------------===//
9 // This file implements a YAML parser.
11 //===----------------------------------------------------------------------===//
13 #include "llvm/Support/YAMLParser.h"
14 #include "llvm/ADT/AllocatorList.h"
15 #include "llvm/ADT/ArrayRef.h"
16 #include "llvm/ADT/None.h"
17 #include "llvm/ADT/STLExtras.h"
18 #include "llvm/ADT/SmallString.h"
19 #include "llvm/ADT/SmallVector.h"
20 #include "llvm/ADT/StringExtras.h"
21 #include "llvm/ADT/StringRef.h"
22 #include "llvm/ADT/Twine.h"
23 #include "llvm/Support/Compiler.h"
24 #include "llvm/Support/ErrorHandling.h"
25 #include "llvm/Support/MemoryBuffer.h"
26 #include "llvm/Support/SMLoc.h"
27 #include "llvm/Support/SourceMgr.h"
28 #include "llvm/Support/Unicode.h"
29 #include "llvm/Support/raw_ostream.h"
37 #include <system_error>
43 enum UnicodeEncodingForm {
44 UEF_UTF32_LE, ///< UTF-32 Little Endian
45 UEF_UTF32_BE, ///< UTF-32 Big Endian
46 UEF_UTF16_LE, ///< UTF-16 Little Endian
47 UEF_UTF16_BE, ///< UTF-16 Big Endian
48 UEF_UTF8, ///< UTF-8 or ascii.
49 UEF_Unknown ///< Not a valid Unicode encoding.
52 /// EncodingInfo - Holds the encoding type and length of the byte order mark if
53 /// it exists. Length is in {0, 2, 3, 4}.
54 using EncodingInfo = std::pair<UnicodeEncodingForm, unsigned>;
56 /// getUnicodeEncoding - Reads up to the first 4 bytes to determine the Unicode
57 /// encoding form of \a Input.
59 /// @param Input A string of length 0 or more.
60 /// @returns An EncodingInfo indicating the Unicode encoding form of the input
61 /// and how long the byte order mark is if one exists.
62 static EncodingInfo getUnicodeEncoding(StringRef Input) {
64 return std::make_pair(UEF_Unknown, 0);
66 switch (uint8_t(Input[0])) {
68 if (Input.size() >= 4) {
70 && uint8_t(Input[2]) == 0xFE
71 && uint8_t(Input[3]) == 0xFF)
72 return std::make_pair(UEF_UTF32_BE, 4);
73 if (Input[1] == 0 && Input[2] == 0 && Input[3] != 0)
74 return std::make_pair(UEF_UTF32_BE, 0);
77 if (Input.size() >= 2 && Input[1] != 0)
78 return std::make_pair(UEF_UTF16_BE, 0);
79 return std::make_pair(UEF_Unknown, 0);
81 if ( Input.size() >= 4
82 && uint8_t(Input[1]) == 0xFE
85 return std::make_pair(UEF_UTF32_LE, 4);
87 if (Input.size() >= 2 && uint8_t(Input[1]) == 0xFE)
88 return std::make_pair(UEF_UTF16_LE, 2);
89 return std::make_pair(UEF_Unknown, 0);
91 if (Input.size() >= 2 && uint8_t(Input[1]) == 0xFF)
92 return std::make_pair(UEF_UTF16_BE, 2);
93 return std::make_pair(UEF_Unknown, 0);
95 if ( Input.size() >= 3
96 && uint8_t(Input[1]) == 0xBB
97 && uint8_t(Input[2]) == 0xBF)
98 return std::make_pair(UEF_UTF8, 3);
99 return std::make_pair(UEF_Unknown, 0);
102 // It could still be utf-32 or utf-16.
103 if (Input.size() >= 4 && Input[1] == 0 && Input[2] == 0 && Input[3] == 0)
104 return std::make_pair(UEF_UTF32_LE, 0);
106 if (Input.size() >= 2 && Input[1] == 0)
107 return std::make_pair(UEF_UTF16_LE, 0);
109 return std::make_pair(UEF_UTF8, 0);
112 /// Pin the vtables to this file.
113 void Node::anchor() {}
114 void NullNode::anchor() {}
115 void ScalarNode::anchor() {}
116 void BlockScalarNode::anchor() {}
117 void KeyValueNode::anchor() {}
118 void MappingNode::anchor() {}
119 void SequenceNode::anchor() {}
120 void AliasNode::anchor() {}
125 /// Token - A single YAML token.
128 TK_Error, // Uninitialized token.
137 TK_BlockSequenceStart,
138 TK_BlockMappingStart,
140 TK_FlowSequenceStart,
153 /// A string of length 0 or more whose begin() points to the logical location
154 /// of the token in the input.
157 /// The value of a block scalar node.
163 } // end namespace yaml
164 } // end namespace llvm
166 using TokenQueueT = BumpPtrList<Token>;
170 /// This struct is used to track simple keys.
172 /// Simple keys are handled by creating an entry in SimpleKeys for each Token
173 /// which could legally be the start of a simple key. When peekNext is called,
174 /// if the Token To be returned is referenced by a SimpleKey, we continue
175 /// tokenizing until that potential simple key has either been found to not be
176 /// a simple key (we moved on to the next line or went further than 1024 chars).
177 /// Or when we run into a Value, and then insert a Key token (and possibly
178 /// others) before the SimpleKey's Tok.
180 TokenQueueT::iterator Tok;
186 bool operator ==(const SimpleKey &Other) {
187 return Tok == Other.Tok;
191 } // end anonymous namespace
193 /// The Unicode scalar value of a UTF-8 minimal well-formed code unit
194 /// subsequence and the subsequence's length in code units (uint8_t).
195 /// A length of 0 represents an error.
196 using UTF8Decoded = std::pair<uint32_t, unsigned>;
198 static UTF8Decoded decodeUTF8(StringRef Range) {
199 StringRef::iterator Position= Range.begin();
200 StringRef::iterator End = Range.end();
201 // 1 byte: [0x00, 0x7f]
202 // Bit pattern: 0xxxxxxx
203 if ((*Position & 0x80) == 0) {
204 return std::make_pair(*Position, 1);
206 // 2 bytes: [0x80, 0x7ff]
207 // Bit pattern: 110xxxxx 10xxxxxx
208 if (Position + 1 != End &&
209 ((*Position & 0xE0) == 0xC0) &&
210 ((*(Position + 1) & 0xC0) == 0x80)) {
211 uint32_t codepoint = ((*Position & 0x1F) << 6) |
212 (*(Position + 1) & 0x3F);
213 if (codepoint >= 0x80)
214 return std::make_pair(codepoint, 2);
216 // 3 bytes: [0x8000, 0xffff]
217 // Bit pattern: 1110xxxx 10xxxxxx 10xxxxxx
218 if (Position + 2 != End &&
219 ((*Position & 0xF0) == 0xE0) &&
220 ((*(Position + 1) & 0xC0) == 0x80) &&
221 ((*(Position + 2) & 0xC0) == 0x80)) {
222 uint32_t codepoint = ((*Position & 0x0F) << 12) |
223 ((*(Position + 1) & 0x3F) << 6) |
224 (*(Position + 2) & 0x3F);
225 // Codepoints between 0xD800 and 0xDFFF are invalid, as
226 // they are high / low surrogate halves used by UTF-16.
227 if (codepoint >= 0x800 &&
228 (codepoint < 0xD800 || codepoint > 0xDFFF))
229 return std::make_pair(codepoint, 3);
231 // 4 bytes: [0x10000, 0x10FFFF]
232 // Bit pattern: 11110xxx 10xxxxxx 10xxxxxx 10xxxxxx
233 if (Position + 3 != End &&
234 ((*Position & 0xF8) == 0xF0) &&
235 ((*(Position + 1) & 0xC0) == 0x80) &&
236 ((*(Position + 2) & 0xC0) == 0x80) &&
237 ((*(Position + 3) & 0xC0) == 0x80)) {
238 uint32_t codepoint = ((*Position & 0x07) << 18) |
239 ((*(Position + 1) & 0x3F) << 12) |
240 ((*(Position + 2) & 0x3F) << 6) |
241 (*(Position + 3) & 0x3F);
242 if (codepoint >= 0x10000 && codepoint <= 0x10FFFF)
243 return std::make_pair(codepoint, 4);
245 return std::make_pair(0, 0);
251 /// Scans YAML tokens from a MemoryBuffer.
254 Scanner(StringRef Input, SourceMgr &SM, bool ShowColors = true,
255 std::error_code *EC = nullptr);
256 Scanner(MemoryBufferRef Buffer, SourceMgr &SM_, bool ShowColors = true,
257 std::error_code *EC = nullptr);
259 /// Parse the next token and return it without popping it.
262 /// Parse the next token and pop it from the queue.
265 void printError(SMLoc Loc, SourceMgr::DiagKind Kind, const Twine &Message,
266 ArrayRef<SMRange> Ranges = None) {
267 SM.PrintMessage(Loc, Kind, Message, Ranges, /* FixIts= */ None, ShowColors);
270 void setError(const Twine &Message, StringRef::iterator Position) {
274 // propagate the error if possible
276 *EC = make_error_code(std::errc::invalid_argument);
278 // Don't print out more errors after the first one we encounter. The rest
279 // are just the result of the first, and have no meaning.
281 printError(SMLoc::getFromPointer(Current), SourceMgr::DK_Error, Message);
285 void setError(const Twine &Message) {
286 setError(Message, Current);
289 /// Returns true if an error occurred while parsing.
295 void init(MemoryBufferRef Buffer);
297 StringRef currentInput() {
298 return StringRef(Current, End - Current);
301 /// Decode a UTF-8 minimal well-formed code unit subsequence starting
304 /// If the UTF-8 code units starting at Position do not form a well-formed
305 /// code unit subsequence, then the Unicode scalar value is 0, and the length
307 UTF8Decoded decodeUTF8(StringRef::iterator Position) {
308 return ::decodeUTF8(StringRef(Position, End - Position));
311 // The following functions are based on the gramar rules in the YAML spec. The
312 // style of the function names it meant to closely match how they are written
313 // in the spec. The number within the [] is the number of the grammar rule in
316 // See 4.2 [Production Naming Conventions] for the meaning of the prefixes.
319 // A production starting and ending with a special character.
321 // A production matching a single line break.
323 // A production starting and ending with a non-break character.
325 // A production starting and ending with a white space character.
327 // A production starting and ending with a non-space character.
329 // A production matching complete line(s).
331 /// Skip a single nb-char[27] starting at Position.
333 /// A nb-char is 0x9 | [0x20-0x7E] | 0x85 | [0xA0-0xD7FF] | [0xE000-0xFEFE]
334 /// | [0xFF00-0xFFFD] | [0x10000-0x10FFFF]
336 /// @returns The code unit after the nb-char, or Position if it's not an
338 StringRef::iterator skip_nb_char(StringRef::iterator Position);
340 /// Skip a single b-break[28] starting at Position.
342 /// A b-break is 0xD 0xA | 0xD | 0xA
344 /// @returns The code unit after the b-break, or Position if it's not a
346 StringRef::iterator skip_b_break(StringRef::iterator Position);
348 /// Skip a single s-space[31] starting at Position.
350 /// An s-space is 0x20
352 /// @returns The code unit after the s-space, or Position if it's not a
354 StringRef::iterator skip_s_space(StringRef::iterator Position);
356 /// Skip a single s-white[33] starting at Position.
358 /// A s-white is 0x20 | 0x9
360 /// @returns The code unit after the s-white, or Position if it's not a
362 StringRef::iterator skip_s_white(StringRef::iterator Position);
364 /// Skip a single ns-char[34] starting at Position.
366 /// A ns-char is nb-char - s-white
368 /// @returns The code unit after the ns-char, or Position if it's not a
370 StringRef::iterator skip_ns_char(StringRef::iterator Position);
372 using SkipWhileFunc = StringRef::iterator (Scanner::*)(StringRef::iterator);
374 /// Skip minimal well-formed code unit subsequences until Func
375 /// returns its input.
377 /// @returns The code unit after the last minimal well-formed code unit
378 /// subsequence that Func accepted.
379 StringRef::iterator skip_while( SkipWhileFunc Func
380 , StringRef::iterator Position);
382 /// Skip minimal well-formed code unit subsequences until Func returns its
384 void advanceWhile(SkipWhileFunc Func);
386 /// Scan ns-uri-char[39]s starting at Cur.
388 /// This updates Cur and Column while scanning.
389 void scan_ns_uri_char();
391 /// Consume a minimal well-formed code unit subsequence starting at
392 /// \a Cur. Return false if it is not the same Unicode scalar value as
393 /// \a Expected. This updates \a Column.
394 bool consume(uint32_t Expected);
396 /// Skip \a Distance UTF-8 code units. Updates \a Cur and \a Column.
397 void skip(uint32_t Distance);
399 /// Return true if the minimal well-formed code unit subsequence at
400 /// Pos is whitespace or a new line
401 bool isBlankOrBreak(StringRef::iterator Position);
403 /// Consume a single b-break[28] if it's present at the current position.
405 /// Return false if the code unit at the current position isn't a line break.
406 bool consumeLineBreakIfPresent();
408 /// If IsSimpleKeyAllowed, create and push_back a new SimpleKey.
409 void saveSimpleKeyCandidate( TokenQueueT::iterator Tok
413 /// Remove simple keys that can no longer be valid simple keys.
415 /// Invalid simple keys are not on the current line or are further than 1024
417 void removeStaleSimpleKeyCandidates();
419 /// Remove all simple keys on FlowLevel \a Level.
420 void removeSimpleKeyCandidatesOnFlowLevel(unsigned Level);
422 /// Unroll indentation in \a Indents back to \a Col. Creates BlockEnd
423 /// tokens if needed.
424 bool unrollIndent(int ToColumn);
426 /// Increase indent to \a Col. Creates \a Kind token at \a InsertPoint
428 bool rollIndent( int ToColumn
429 , Token::TokenKind Kind
430 , TokenQueueT::iterator InsertPoint);
432 /// Skip a single-line comment when the comment starts at the current
433 /// position of the scanner.
436 /// Skip whitespace and comments until the start of the next token.
437 void scanToNextToken();
439 /// Must be the first token generated.
440 bool scanStreamStart();
442 /// Generate tokens needed to close out the stream.
443 bool scanStreamEnd();
445 /// Scan a %BLAH directive.
446 bool scanDirective();
448 /// Scan a ... or ---.
449 bool scanDocumentIndicator(bool IsStart);
451 /// Scan a [ or { and generate the proper flow collection start token.
452 bool scanFlowCollectionStart(bool IsSequence);
454 /// Scan a ] or } and generate the proper flow collection end token.
455 bool scanFlowCollectionEnd(bool IsSequence);
457 /// Scan the , that separates entries in a flow collection.
458 bool scanFlowEntry();
460 /// Scan the - that starts block sequence entries.
461 bool scanBlockEntry();
463 /// Scan an explicit ? indicating a key.
466 /// Scan an explicit : indicating a value.
469 /// Scan a quoted scalar.
470 bool scanFlowScalar(bool IsDoubleQuoted);
472 /// Scan an unquoted scalar.
473 bool scanPlainScalar();
475 /// Scan an Alias or Anchor starting with * or &.
476 bool scanAliasOrAnchor(bool IsAlias);
478 /// Scan a block scalar starting with | or >.
479 bool scanBlockScalar(bool IsLiteral);
481 /// Scan a chomping indicator in a block scalar header.
482 char scanBlockChompingIndicator();
484 /// Scan an indentation indicator in a block scalar header.
485 unsigned scanBlockIndentationIndicator();
487 /// Scan a block scalar header.
489 /// Return false if an error occurred.
490 bool scanBlockScalarHeader(char &ChompingIndicator, unsigned &IndentIndicator,
493 /// Look for the indentation level of a block scalar.
495 /// Return false if an error occurred.
496 bool findBlockScalarIndent(unsigned &BlockIndent, unsigned BlockExitIndent,
497 unsigned &LineBreaks, bool &IsDone);
499 /// Scan the indentation of a text line in a block scalar.
501 /// Return false if an error occurred.
502 bool scanBlockScalarIndent(unsigned BlockIndent, unsigned BlockExitIndent,
505 /// Scan a tag of the form !stuff.
508 /// Dispatch to the next scanning function based on \a *Cur.
509 bool fetchMoreTokens();
511 /// The SourceMgr used for diagnostics and buffer management.
514 /// The original input.
515 MemoryBufferRef InputBuffer;
517 /// The current position of the scanner.
518 StringRef::iterator Current;
520 /// The end of the input (one past the last character).
521 StringRef::iterator End;
523 /// Current YAML indentation level in spaces.
526 /// Current column number in Unicode code points.
529 /// Current line number.
532 /// How deep we are in flow style containers. 0 Means at block level.
535 /// Are we at the start of the stream?
536 bool IsStartOfStream;
538 /// Can the next token be the start of a simple key?
539 bool IsSimpleKeyAllowed;
541 /// True if an error has occurred.
544 /// Should colors be used when printing out the diagnostic messages?
547 /// Queue of tokens. This is required to queue up tokens while looking
548 /// for the end of a simple key. And for cases where a single character
549 /// can produce multiple tokens (e.g. BlockEnd).
550 TokenQueueT TokenQueue;
552 /// Indentation levels.
553 SmallVector<int, 4> Indents;
555 /// Potential simple keys.
556 SmallVector<SimpleKey, 4> SimpleKeys;
561 } // end namespace yaml
562 } // end namespace llvm
564 /// encodeUTF8 - Encode \a UnicodeScalarValue in UTF-8 and append it to result.
565 static void encodeUTF8( uint32_t UnicodeScalarValue
566 , SmallVectorImpl<char> &Result) {
567 if (UnicodeScalarValue <= 0x7F) {
568 Result.push_back(UnicodeScalarValue & 0x7F);
569 } else if (UnicodeScalarValue <= 0x7FF) {
570 uint8_t FirstByte = 0xC0 | ((UnicodeScalarValue & 0x7C0) >> 6);
571 uint8_t SecondByte = 0x80 | (UnicodeScalarValue & 0x3F);
572 Result.push_back(FirstByte);
573 Result.push_back(SecondByte);
574 } else if (UnicodeScalarValue <= 0xFFFF) {
575 uint8_t FirstByte = 0xE0 | ((UnicodeScalarValue & 0xF000) >> 12);
576 uint8_t SecondByte = 0x80 | ((UnicodeScalarValue & 0xFC0) >> 6);
577 uint8_t ThirdByte = 0x80 | (UnicodeScalarValue & 0x3F);
578 Result.push_back(FirstByte);
579 Result.push_back(SecondByte);
580 Result.push_back(ThirdByte);
581 } else if (UnicodeScalarValue <= 0x10FFFF) {
582 uint8_t FirstByte = 0xF0 | ((UnicodeScalarValue & 0x1F0000) >> 18);
583 uint8_t SecondByte = 0x80 | ((UnicodeScalarValue & 0x3F000) >> 12);
584 uint8_t ThirdByte = 0x80 | ((UnicodeScalarValue & 0xFC0) >> 6);
585 uint8_t FourthByte = 0x80 | (UnicodeScalarValue & 0x3F);
586 Result.push_back(FirstByte);
587 Result.push_back(SecondByte);
588 Result.push_back(ThirdByte);
589 Result.push_back(FourthByte);
593 bool yaml::dumpTokens(StringRef Input, raw_ostream &OS) {
595 Scanner scanner(Input, SM);
597 Token T = scanner.getNext();
599 case Token::TK_StreamStart:
600 OS << "Stream-Start: ";
602 case Token::TK_StreamEnd:
603 OS << "Stream-End: ";
605 case Token::TK_VersionDirective:
606 OS << "Version-Directive: ";
608 case Token::TK_TagDirective:
609 OS << "Tag-Directive: ";
611 case Token::TK_DocumentStart:
612 OS << "Document-Start: ";
614 case Token::TK_DocumentEnd:
615 OS << "Document-End: ";
617 case Token::TK_BlockEntry:
618 OS << "Block-Entry: ";
620 case Token::TK_BlockEnd:
623 case Token::TK_BlockSequenceStart:
624 OS << "Block-Sequence-Start: ";
626 case Token::TK_BlockMappingStart:
627 OS << "Block-Mapping-Start: ";
629 case Token::TK_FlowEntry:
630 OS << "Flow-Entry: ";
632 case Token::TK_FlowSequenceStart:
633 OS << "Flow-Sequence-Start: ";
635 case Token::TK_FlowSequenceEnd:
636 OS << "Flow-Sequence-End: ";
638 case Token::TK_FlowMappingStart:
639 OS << "Flow-Mapping-Start: ";
641 case Token::TK_FlowMappingEnd:
642 OS << "Flow-Mapping-End: ";
647 case Token::TK_Value:
650 case Token::TK_Scalar:
653 case Token::TK_BlockScalar:
654 OS << "Block Scalar: ";
656 case Token::TK_Alias:
659 case Token::TK_Anchor:
665 case Token::TK_Error:
668 OS << T.Range << "\n";
669 if (T.Kind == Token::TK_StreamEnd)
671 else if (T.Kind == Token::TK_Error)
677 bool yaml::scanTokens(StringRef Input) {
679 Scanner scanner(Input, SM);
681 Token T = scanner.getNext();
682 if (T.Kind == Token::TK_StreamEnd)
684 else if (T.Kind == Token::TK_Error)
690 std::string yaml::escape(StringRef Input, bool EscapePrintable) {
691 std::string EscapedInput;
692 for (StringRef::iterator i = Input.begin(), e = Input.end(); i != e; ++i) {
694 EscapedInput += "\\\\";
696 EscapedInput += "\\\"";
698 EscapedInput += "\\0";
700 EscapedInput += "\\a";
702 EscapedInput += "\\b";
704 EscapedInput += "\\t";
706 EscapedInput += "\\n";
708 EscapedInput += "\\v";
710 EscapedInput += "\\f";
712 EscapedInput += "\\r";
714 EscapedInput += "\\e";
715 else if ((unsigned char)*i < 0x20) { // Control characters not handled above.
716 std::string HexStr = utohexstr(*i);
717 EscapedInput += "\\x" + std::string(2 - HexStr.size(), '0') + HexStr;
718 } else if (*i & 0x80) { // UTF-8 multiple code unit subsequence.
719 UTF8Decoded UnicodeScalarValue
720 = decodeUTF8(StringRef(i, Input.end() - i));
721 if (UnicodeScalarValue.second == 0) {
722 // Found invalid char.
724 encodeUTF8(0xFFFD, Val);
725 EscapedInput.insert(EscapedInput.end(), Val.begin(), Val.end());
726 // FIXME: Error reporting.
729 if (UnicodeScalarValue.first == 0x85)
730 EscapedInput += "\\N";
731 else if (UnicodeScalarValue.first == 0xA0)
732 EscapedInput += "\\_";
733 else if (UnicodeScalarValue.first == 0x2028)
734 EscapedInput += "\\L";
735 else if (UnicodeScalarValue.first == 0x2029)
736 EscapedInput += "\\P";
737 else if (!EscapePrintable &&
738 sys::unicode::isPrintable(UnicodeScalarValue.first))
739 EscapedInput += StringRef(i, UnicodeScalarValue.second);
741 std::string HexStr = utohexstr(UnicodeScalarValue.first);
742 if (HexStr.size() <= 2)
743 EscapedInput += "\\x" + std::string(2 - HexStr.size(), '0') + HexStr;
744 else if (HexStr.size() <= 4)
745 EscapedInput += "\\u" + std::string(4 - HexStr.size(), '0') + HexStr;
746 else if (HexStr.size() <= 8)
747 EscapedInput += "\\U" + std::string(8 - HexStr.size(), '0') + HexStr;
749 i += UnicodeScalarValue.second - 1;
751 EscapedInput.push_back(*i);
756 Scanner::Scanner(StringRef Input, SourceMgr &sm, bool ShowColors,
758 : SM(sm), ShowColors(ShowColors), EC(EC) {
759 init(MemoryBufferRef(Input, "YAML"));
762 Scanner::Scanner(MemoryBufferRef Buffer, SourceMgr &SM_, bool ShowColors,
764 : SM(SM_), ShowColors(ShowColors), EC(EC) {
768 void Scanner::init(MemoryBufferRef Buffer) {
769 InputBuffer = Buffer;
770 Current = InputBuffer.getBufferStart();
771 End = InputBuffer.getBufferEnd();
776 IsStartOfStream = true;
777 IsSimpleKeyAllowed = true;
779 std::unique_ptr<MemoryBuffer> InputBufferOwner =
780 MemoryBuffer::getMemBuffer(Buffer);
781 SM.AddNewSourceBuffer(std::move(InputBufferOwner), SMLoc());
784 Token &Scanner::peekNext() {
785 // If the current token is a possible simple key, keep parsing until we
787 bool NeedMore = false;
789 if (TokenQueue.empty() || NeedMore) {
790 if (!fetchMoreTokens()) {
792 TokenQueue.push_back(Token());
793 return TokenQueue.front();
796 assert(!TokenQueue.empty() &&
797 "fetchMoreTokens lied about getting tokens!");
799 removeStaleSimpleKeyCandidates();
801 SK.Tok = TokenQueue.begin();
802 if (!is_contained(SimpleKeys, SK))
807 return TokenQueue.front();
810 Token Scanner::getNext() {
811 Token Ret = peekNext();
812 // TokenQueue can be empty if there was an error getting the next token.
813 if (!TokenQueue.empty())
814 TokenQueue.pop_front();
816 // There cannot be any referenced Token's if the TokenQueue is empty. So do a
817 // quick deallocation of them all.
818 if (TokenQueue.empty())
819 TokenQueue.resetAlloc();
824 StringRef::iterator Scanner::skip_nb_char(StringRef::iterator Position) {
827 // Check 7 bit c-printable - b-char.
828 if ( *Position == 0x09
829 || (*Position >= 0x20 && *Position <= 0x7E))
832 // Check for valid UTF-8.
833 if (uint8_t(*Position) & 0x80) {
834 UTF8Decoded u8d = decodeUTF8(Position);
836 && u8d.first != 0xFEFF
837 && ( u8d.first == 0x85
838 || ( u8d.first >= 0xA0
839 && u8d.first <= 0xD7FF)
840 || ( u8d.first >= 0xE000
841 && u8d.first <= 0xFFFD)
842 || ( u8d.first >= 0x10000
843 && u8d.first <= 0x10FFFF)))
844 return Position + u8d.second;
849 StringRef::iterator Scanner::skip_b_break(StringRef::iterator Position) {
852 if (*Position == 0x0D) {
853 if (Position + 1 != End && *(Position + 1) == 0x0A)
858 if (*Position == 0x0A)
863 StringRef::iterator Scanner::skip_s_space(StringRef::iterator Position) {
866 if (*Position == ' ')
871 StringRef::iterator Scanner::skip_s_white(StringRef::iterator Position) {
874 if (*Position == ' ' || *Position == '\t')
879 StringRef::iterator Scanner::skip_ns_char(StringRef::iterator Position) {
882 if (*Position == ' ' || *Position == '\t')
884 return skip_nb_char(Position);
887 StringRef::iterator Scanner::skip_while( SkipWhileFunc Func
888 , StringRef::iterator Position) {
890 StringRef::iterator i = (this->*Func)(Position);
898 void Scanner::advanceWhile(SkipWhileFunc Func) {
899 auto Final = skip_while(Func, Current);
900 Column += Final - Current;
904 static bool is_ns_hex_digit(const char C) {
905 return (C >= '0' && C <= '9')
906 || (C >= 'a' && C <= 'z')
907 || (C >= 'A' && C <= 'Z');
910 static bool is_ns_word_char(const char C) {
912 || (C >= 'a' && C <= 'z')
913 || (C >= 'A' && C <= 'Z');
916 void Scanner::scan_ns_uri_char() {
920 if (( *Current == '%'
922 && is_ns_hex_digit(*(Current + 1))
923 && is_ns_hex_digit(*(Current + 2)))
924 || is_ns_word_char(*Current)
925 || StringRef(Current, 1).find_first_of("#;/?:@&=+$,_.!~*'()[]")
926 != StringRef::npos) {
934 bool Scanner::consume(uint32_t Expected) {
935 if (Expected >= 0x80)
936 report_fatal_error("Not dealing with this yet");
939 if (uint8_t(*Current) >= 0x80)
940 report_fatal_error("Not dealing with this yet");
941 if (uint8_t(*Current) == Expected) {
949 void Scanner::skip(uint32_t Distance) {
952 assert(Current <= End && "Skipped past the end");
955 bool Scanner::isBlankOrBreak(StringRef::iterator Position) {
958 return *Position == ' ' || *Position == '\t' || *Position == '\r' ||
962 bool Scanner::consumeLineBreakIfPresent() {
963 auto Next = skip_b_break(Current);
972 void Scanner::saveSimpleKeyCandidate( TokenQueueT::iterator Tok
975 if (IsSimpleKeyAllowed) {
979 SK.Column = AtColumn;
980 SK.IsRequired = IsRequired;
981 SK.FlowLevel = FlowLevel;
982 SimpleKeys.push_back(SK);
986 void Scanner::removeStaleSimpleKeyCandidates() {
987 for (SmallVectorImpl<SimpleKey>::iterator i = SimpleKeys.begin();
988 i != SimpleKeys.end();) {
989 if (i->Line != Line || i->Column + 1024 < Column) {
991 setError( "Could not find expected : for simple key"
992 , i->Tok->Range.begin());
993 i = SimpleKeys.erase(i);
999 void Scanner::removeSimpleKeyCandidatesOnFlowLevel(unsigned Level) {
1000 if (!SimpleKeys.empty() && (SimpleKeys.end() - 1)->FlowLevel == Level)
1001 SimpleKeys.pop_back();
1004 bool Scanner::unrollIndent(int ToColumn) {
1006 // Indentation is ignored in flow.
1010 while (Indent > ToColumn) {
1011 T.Kind = Token::TK_BlockEnd;
1012 T.Range = StringRef(Current, 1);
1013 TokenQueue.push_back(T);
1014 Indent = Indents.pop_back_val();
1020 bool Scanner::rollIndent( int ToColumn
1021 , Token::TokenKind Kind
1022 , TokenQueueT::iterator InsertPoint) {
1025 if (Indent < ToColumn) {
1026 Indents.push_back(Indent);
1031 T.Range = StringRef(Current, 0);
1032 TokenQueue.insert(InsertPoint, T);
1037 void Scanner::skipComment() {
1038 if (*Current != '#')
1041 // This may skip more than one byte, thus Column is only incremented
1043 StringRef::iterator I = skip_nb_char(Current);
1051 void Scanner::scanToNextToken() {
1053 while (*Current == ' ' || *Current == '\t') {
1060 StringRef::iterator i = skip_b_break(Current);
1066 // New lines may start a simple key.
1068 IsSimpleKeyAllowed = true;
1072 bool Scanner::scanStreamStart() {
1073 IsStartOfStream = false;
1075 EncodingInfo EI = getUnicodeEncoding(currentInput());
1078 T.Kind = Token::TK_StreamStart;
1079 T.Range = StringRef(Current, EI.second);
1080 TokenQueue.push_back(T);
1081 Current += EI.second;
1085 bool Scanner::scanStreamEnd() {
1086 // Force an ending new line if one isn't present.
1094 IsSimpleKeyAllowed = false;
1097 T.Kind = Token::TK_StreamEnd;
1098 T.Range = StringRef(Current, 0);
1099 TokenQueue.push_back(T);
1103 bool Scanner::scanDirective() {
1104 // Reset the indentation level.
1107 IsSimpleKeyAllowed = false;
1109 StringRef::iterator Start = Current;
1111 StringRef::iterator NameStart = Current;
1112 Current = skip_while(&Scanner::skip_ns_char, Current);
1113 StringRef Name(NameStart, Current - NameStart);
1114 Current = skip_while(&Scanner::skip_s_white, Current);
1117 if (Name == "YAML") {
1118 Current = skip_while(&Scanner::skip_ns_char, Current);
1119 T.Kind = Token::TK_VersionDirective;
1120 T.Range = StringRef(Start, Current - Start);
1121 TokenQueue.push_back(T);
1123 } else if(Name == "TAG") {
1124 Current = skip_while(&Scanner::skip_ns_char, Current);
1125 Current = skip_while(&Scanner::skip_s_white, Current);
1126 Current = skip_while(&Scanner::skip_ns_char, Current);
1127 T.Kind = Token::TK_TagDirective;
1128 T.Range = StringRef(Start, Current - Start);
1129 TokenQueue.push_back(T);
1135 bool Scanner::scanDocumentIndicator(bool IsStart) {
1138 IsSimpleKeyAllowed = false;
1141 T.Kind = IsStart ? Token::TK_DocumentStart : Token::TK_DocumentEnd;
1142 T.Range = StringRef(Current, 3);
1144 TokenQueue.push_back(T);
1148 bool Scanner::scanFlowCollectionStart(bool IsSequence) {
1150 T.Kind = IsSequence ? Token::TK_FlowSequenceStart
1151 : Token::TK_FlowMappingStart;
1152 T.Range = StringRef(Current, 1);
1154 TokenQueue.push_back(T);
1156 // [ and { may begin a simple key.
1157 saveSimpleKeyCandidate(--TokenQueue.end(), Column - 1, false);
1159 // And may also be followed by a simple key.
1160 IsSimpleKeyAllowed = true;
1165 bool Scanner::scanFlowCollectionEnd(bool IsSequence) {
1166 removeSimpleKeyCandidatesOnFlowLevel(FlowLevel);
1167 IsSimpleKeyAllowed = false;
1169 T.Kind = IsSequence ? Token::TK_FlowSequenceEnd
1170 : Token::TK_FlowMappingEnd;
1171 T.Range = StringRef(Current, 1);
1173 TokenQueue.push_back(T);
1179 bool Scanner::scanFlowEntry() {
1180 removeSimpleKeyCandidatesOnFlowLevel(FlowLevel);
1181 IsSimpleKeyAllowed = true;
1183 T.Kind = Token::TK_FlowEntry;
1184 T.Range = StringRef(Current, 1);
1186 TokenQueue.push_back(T);
1190 bool Scanner::scanBlockEntry() {
1191 rollIndent(Column, Token::TK_BlockSequenceStart, TokenQueue.end());
1192 removeSimpleKeyCandidatesOnFlowLevel(FlowLevel);
1193 IsSimpleKeyAllowed = true;
1195 T.Kind = Token::TK_BlockEntry;
1196 T.Range = StringRef(Current, 1);
1198 TokenQueue.push_back(T);
1202 bool Scanner::scanKey() {
1204 rollIndent(Column, Token::TK_BlockMappingStart, TokenQueue.end());
1206 removeSimpleKeyCandidatesOnFlowLevel(FlowLevel);
1207 IsSimpleKeyAllowed = !FlowLevel;
1210 T.Kind = Token::TK_Key;
1211 T.Range = StringRef(Current, 1);
1213 TokenQueue.push_back(T);
1217 bool Scanner::scanValue() {
1218 // If the previous token could have been a simple key, insert the key token
1219 // into the token queue.
1220 if (!SimpleKeys.empty()) {
1221 SimpleKey SK = SimpleKeys.pop_back_val();
1223 T.Kind = Token::TK_Key;
1224 T.Range = SK.Tok->Range;
1225 TokenQueueT::iterator i, e;
1226 for (i = TokenQueue.begin(), e = TokenQueue.end(); i != e; ++i) {
1230 assert(i != e && "SimpleKey not in token queue!");
1231 i = TokenQueue.insert(i, T);
1233 // We may also need to add a Block-Mapping-Start token.
1234 rollIndent(SK.Column, Token::TK_BlockMappingStart, i);
1236 IsSimpleKeyAllowed = false;
1239 rollIndent(Column, Token::TK_BlockMappingStart, TokenQueue.end());
1240 IsSimpleKeyAllowed = !FlowLevel;
1244 T.Kind = Token::TK_Value;
1245 T.Range = StringRef(Current, 1);
1247 TokenQueue.push_back(T);
1251 // Forbidding inlining improves performance by roughly 20%.
1252 // FIXME: Remove once llvm optimizes this to the faster version without hints.
1253 LLVM_ATTRIBUTE_NOINLINE static bool
1254 wasEscaped(StringRef::iterator First, StringRef::iterator Position);
1256 // Returns whether a character at 'Position' was escaped with a leading '\'.
1257 // 'First' specifies the position of the first character in the string.
1258 static bool wasEscaped(StringRef::iterator First,
1259 StringRef::iterator Position) {
1260 assert(Position - 1 >= First);
1261 StringRef::iterator I = Position - 1;
1262 // We calculate the number of consecutive '\'s before the current position
1263 // by iterating backwards through our string.
1264 while (I >= First && *I == '\\') --I;
1265 // (Position - 1 - I) now contains the number of '\'s before the current
1266 // position. If it is odd, the character at 'Position' was escaped.
1267 return (Position - 1 - I) % 2 == 1;
1270 bool Scanner::scanFlowScalar(bool IsDoubleQuoted) {
1271 StringRef::iterator Start = Current;
1272 unsigned ColStart = Column;
1273 if (IsDoubleQuoted) {
1276 while (Current != End && *Current != '"')
1278 // Repeat until the previous character was not a '\' or was an escaped
1280 } while ( Current != End
1281 && *(Current - 1) == '\\'
1282 && wasEscaped(Start + 1, Current));
1286 // Skip a ' followed by another '.
1287 if (Current + 1 < End && *Current == '\'' && *(Current + 1) == '\'') {
1290 } else if (*Current == '\'')
1292 StringRef::iterator i = skip_nb_char(Current);
1294 i = skip_b_break(Current);
1309 if (Current == End) {
1310 setError("Expected quote at end of scalar", Current);
1314 skip(1); // Skip ending quote.
1316 T.Kind = Token::TK_Scalar;
1317 T.Range = StringRef(Start, Current - Start);
1318 TokenQueue.push_back(T);
1320 saveSimpleKeyCandidate(--TokenQueue.end(), ColStart, false);
1322 IsSimpleKeyAllowed = false;
1327 bool Scanner::scanPlainScalar() {
1328 StringRef::iterator Start = Current;
1329 unsigned ColStart = Column;
1330 unsigned LeadingBlanks = 0;
1331 assert(Indent >= -1 && "Indent must be >= -1 !");
1332 unsigned indent = static_cast<unsigned>(Indent + 1);
1334 if (*Current == '#')
1337 while (!isBlankOrBreak(Current)) {
1338 if ( FlowLevel && *Current == ':'
1339 && !(isBlankOrBreak(Current + 1) || *(Current + 1) == ',')) {
1340 setError("Found unexpected ':' while scanning a plain scalar", Current);
1344 // Check for the end of the plain scalar.
1345 if ( (*Current == ':' && isBlankOrBreak(Current + 1))
1347 && (StringRef(Current, 1).find_first_of(",:?[]{}")
1348 != StringRef::npos)))
1351 StringRef::iterator i = skip_nb_char(Current);
1358 // Are we at the end?
1359 if (!isBlankOrBreak(Current))
1363 StringRef::iterator Tmp = Current;
1364 while (isBlankOrBreak(Tmp)) {
1365 StringRef::iterator i = skip_s_white(Tmp);
1367 if (LeadingBlanks && (Column < indent) && *Tmp == '\t') {
1368 setError("Found invalid tab character in indentation", Tmp);
1374 i = skip_b_break(Tmp);
1383 if (!FlowLevel && Column < indent)
1388 if (Start == Current) {
1389 setError("Got empty plain scalar", Start);
1393 T.Kind = Token::TK_Scalar;
1394 T.Range = StringRef(Start, Current - Start);
1395 TokenQueue.push_back(T);
1397 // Plain scalars can be simple keys.
1398 saveSimpleKeyCandidate(--TokenQueue.end(), ColStart, false);
1400 IsSimpleKeyAllowed = false;
1405 bool Scanner::scanAliasOrAnchor(bool IsAlias) {
1406 StringRef::iterator Start = Current;
1407 unsigned ColStart = Column;
1410 if ( *Current == '[' || *Current == ']'
1411 || *Current == '{' || *Current == '}'
1415 StringRef::iterator i = skip_ns_char(Current);
1422 if (Start == Current) {
1423 setError("Got empty alias or anchor", Start);
1428 T.Kind = IsAlias ? Token::TK_Alias : Token::TK_Anchor;
1429 T.Range = StringRef(Start, Current - Start);
1430 TokenQueue.push_back(T);
1432 // Alias and anchors can be simple keys.
1433 saveSimpleKeyCandidate(--TokenQueue.end(), ColStart, false);
1435 IsSimpleKeyAllowed = false;
1440 char Scanner::scanBlockChompingIndicator() {
1441 char Indicator = ' ';
1442 if (Current != End && (*Current == '+' || *Current == '-')) {
1443 Indicator = *Current;
1449 /// Get the number of line breaks after chomping.
1451 /// Return the number of trailing line breaks to emit, depending on
1452 /// \p ChompingIndicator.
1453 static unsigned getChompedLineBreaks(char ChompingIndicator,
1454 unsigned LineBreaks, StringRef Str) {
1455 if (ChompingIndicator == '-') // Strip all line breaks.
1457 if (ChompingIndicator == '+') // Keep all line breaks.
1459 // Clip trailing lines.
1460 return Str.empty() ? 0 : 1;
1463 unsigned Scanner::scanBlockIndentationIndicator() {
1464 unsigned Indent = 0;
1465 if (Current != End && (*Current >= '1' && *Current <= '9')) {
1466 Indent = unsigned(*Current - '0');
1472 bool Scanner::scanBlockScalarHeader(char &ChompingIndicator,
1473 unsigned &IndentIndicator, bool &IsDone) {
1474 auto Start = Current;
1476 ChompingIndicator = scanBlockChompingIndicator();
1477 IndentIndicator = scanBlockIndentationIndicator();
1478 // Check for the chomping indicator once again.
1479 if (ChompingIndicator == ' ')
1480 ChompingIndicator = scanBlockChompingIndicator();
1481 Current = skip_while(&Scanner::skip_s_white, Current);
1484 if (Current == End) { // EOF, we have an empty scalar.
1486 T.Kind = Token::TK_BlockScalar;
1487 T.Range = StringRef(Start, Current - Start);
1488 TokenQueue.push_back(T);
1493 if (!consumeLineBreakIfPresent()) {
1494 setError("Expected a line break after block scalar header", Current);
1500 bool Scanner::findBlockScalarIndent(unsigned &BlockIndent,
1501 unsigned BlockExitIndent,
1502 unsigned &LineBreaks, bool &IsDone) {
1503 unsigned MaxAllSpaceLineCharacters = 0;
1504 StringRef::iterator LongestAllSpaceLine;
1507 advanceWhile(&Scanner::skip_s_space);
1508 if (skip_nb_char(Current) != Current) {
1509 // This line isn't empty, so try and find the indentation.
1510 if (Column <= BlockExitIndent) { // End of the block literal.
1514 // We found the block's indentation.
1515 BlockIndent = Column;
1516 if (MaxAllSpaceLineCharacters > BlockIndent) {
1518 "Leading all-spaces line must be smaller than the block indent",
1519 LongestAllSpaceLine);
1524 if (skip_b_break(Current) != Current &&
1525 Column > MaxAllSpaceLineCharacters) {
1526 // Record the longest all-space line in case it's longer than the
1527 // discovered block indent.
1528 MaxAllSpaceLineCharacters = Column;
1529 LongestAllSpaceLine = Current;
1533 if (Current == End) {
1538 if (!consumeLineBreakIfPresent()) {
1547 bool Scanner::scanBlockScalarIndent(unsigned BlockIndent,
1548 unsigned BlockExitIndent, bool &IsDone) {
1549 // Skip the indentation.
1550 while (Column < BlockIndent) {
1551 auto I = skip_s_space(Current);
1558 if (skip_nb_char(Current) == Current)
1561 if (Column <= BlockExitIndent) { // End of the block literal.
1566 if (Column < BlockIndent) {
1567 if (Current != End && *Current == '#') { // Trailing comment.
1571 setError("A text line is less indented than the block scalar", Current);
1574 return true; // A normal text line.
1577 bool Scanner::scanBlockScalar(bool IsLiteral) {
1579 assert(*Current == '|' || *Current == '>');
1582 char ChompingIndicator;
1583 unsigned BlockIndent;
1584 bool IsDone = false;
1585 if (!scanBlockScalarHeader(ChompingIndicator, BlockIndent, IsDone))
1590 auto Start = Current;
1591 unsigned BlockExitIndent = Indent < 0 ? 0 : (unsigned)Indent;
1592 unsigned LineBreaks = 0;
1593 if (BlockIndent == 0) {
1594 if (!findBlockScalarIndent(BlockIndent, BlockExitIndent, LineBreaks,
1599 // Scan the block's scalars body.
1600 SmallString<256> Str;
1602 if (!scanBlockScalarIndent(BlockIndent, BlockExitIndent, IsDone))
1607 // Parse the current line.
1608 auto LineStart = Current;
1609 advanceWhile(&Scanner::skip_nb_char);
1610 if (LineStart != Current) {
1611 Str.append(LineBreaks, '\n');
1612 Str.append(StringRef(LineStart, Current - LineStart));
1620 if (!consumeLineBreakIfPresent())
1625 if (Current == End && !LineBreaks)
1626 // Ensure that there is at least one line break before the end of file.
1628 Str.append(getChompedLineBreaks(ChompingIndicator, LineBreaks, Str), '\n');
1630 // New lines may start a simple key.
1632 IsSimpleKeyAllowed = true;
1635 T.Kind = Token::TK_BlockScalar;
1636 T.Range = StringRef(Start, Current - Start);
1637 T.Value = Str.str().str();
1638 TokenQueue.push_back(T);
1642 bool Scanner::scanTag() {
1643 StringRef::iterator Start = Current;
1644 unsigned ColStart = Column;
1646 if (Current == End || isBlankOrBreak(Current)); // An empty tag.
1647 else if (*Current == '<') {
1653 // FIXME: Actually parse the c-ns-shorthand-tag rule.
1654 Current = skip_while(&Scanner::skip_ns_char, Current);
1658 T.Kind = Token::TK_Tag;
1659 T.Range = StringRef(Start, Current - Start);
1660 TokenQueue.push_back(T);
1662 // Tags can be simple keys.
1663 saveSimpleKeyCandidate(--TokenQueue.end(), ColStart, false);
1665 IsSimpleKeyAllowed = false;
1670 bool Scanner::fetchMoreTokens() {
1671 if (IsStartOfStream)
1672 return scanStreamStart();
1677 return scanStreamEnd();
1679 removeStaleSimpleKeyCandidates();
1681 unrollIndent(Column);
1683 if (Column == 0 && *Current == '%')
1684 return scanDirective();
1686 if (Column == 0 && Current + 4 <= End
1688 && *(Current + 1) == '-'
1689 && *(Current + 2) == '-'
1690 && (Current + 3 == End || isBlankOrBreak(Current + 3)))
1691 return scanDocumentIndicator(true);
1693 if (Column == 0 && Current + 4 <= End
1695 && *(Current + 1) == '.'
1696 && *(Current + 2) == '.'
1697 && (Current + 3 == End || isBlankOrBreak(Current + 3)))
1698 return scanDocumentIndicator(false);
1700 if (*Current == '[')
1701 return scanFlowCollectionStart(true);
1703 if (*Current == '{')
1704 return scanFlowCollectionStart(false);
1706 if (*Current == ']')
1707 return scanFlowCollectionEnd(true);
1709 if (*Current == '}')
1710 return scanFlowCollectionEnd(false);
1712 if (*Current == ',')
1713 return scanFlowEntry();
1715 if (*Current == '-' && isBlankOrBreak(Current + 1))
1716 return scanBlockEntry();
1718 if (*Current == '?' && (FlowLevel || isBlankOrBreak(Current + 1)))
1721 if (*Current == ':' && (FlowLevel || isBlankOrBreak(Current + 1)))
1724 if (*Current == '*')
1725 return scanAliasOrAnchor(true);
1727 if (*Current == '&')
1728 return scanAliasOrAnchor(false);
1730 if (*Current == '!')
1733 if (*Current == '|' && !FlowLevel)
1734 return scanBlockScalar(true);
1736 if (*Current == '>' && !FlowLevel)
1737 return scanBlockScalar(false);
1739 if (*Current == '\'')
1740 return scanFlowScalar(false);
1742 if (*Current == '"')
1743 return scanFlowScalar(true);
1745 // Get a plain scalar.
1746 StringRef FirstChar(Current, 1);
1747 if (!(isBlankOrBreak(Current)
1748 || FirstChar.find_first_of("-?:,[]{}#&*!|>'\"%@`") != StringRef::npos)
1749 || (*Current == '-' && !isBlankOrBreak(Current + 1))
1750 || (!FlowLevel && (*Current == '?' || *Current == ':')
1751 && isBlankOrBreak(Current + 1))
1752 || (!FlowLevel && *Current == ':'
1753 && Current + 2 < End
1754 && *(Current + 1) == ':'
1755 && !isBlankOrBreak(Current + 2)))
1756 return scanPlainScalar();
1758 setError("Unrecognized character while tokenizing.");
1762 Stream::Stream(StringRef Input, SourceMgr &SM, bool ShowColors,
1763 std::error_code *EC)
1764 : scanner(new Scanner(Input, SM, ShowColors, EC)), CurrentDoc() {}
1766 Stream::Stream(MemoryBufferRef InputBuffer, SourceMgr &SM, bool ShowColors,
1767 std::error_code *EC)
1768 : scanner(new Scanner(InputBuffer, SM, ShowColors, EC)), CurrentDoc() {}
1770 Stream::~Stream() = default;
1772 bool Stream::failed() { return scanner->failed(); }
1774 void Stream::printError(Node *N, const Twine &Msg) {
1775 scanner->printError( N->getSourceRange().Start
1776 , SourceMgr::DK_Error
1778 , N->getSourceRange());
1781 document_iterator Stream::begin() {
1783 report_fatal_error("Can only iterate over the stream once");
1785 // Skip Stream-Start.
1788 CurrentDoc.reset(new Document(*this));
1789 return document_iterator(CurrentDoc);
1792 document_iterator Stream::end() {
1793 return document_iterator();
1796 void Stream::skip() {
1797 for (document_iterator i = begin(), e = end(); i != e; ++i)
1801 Node::Node(unsigned int Type, std::unique_ptr<Document> &D, StringRef A,
1803 : Doc(D), TypeID(Type), Anchor(A), Tag(T) {
1804 SMLoc Start = SMLoc::getFromPointer(peekNext().Range.begin());
1805 SourceRange = SMRange(Start, Start);
1808 std::string Node::getVerbatimTag() const {
1809 StringRef Raw = getRawTag();
1810 if (!Raw.empty() && Raw != "!") {
1812 if (Raw.find_last_of('!') == 0) {
1813 Ret = Doc->getTagMap().find("!")->second;
1814 Ret += Raw.substr(1);
1816 } else if (Raw.startswith("!!")) {
1817 Ret = Doc->getTagMap().find("!!")->second;
1818 Ret += Raw.substr(2);
1821 StringRef TagHandle = Raw.substr(0, Raw.find_last_of('!') + 1);
1822 std::map<StringRef, StringRef>::const_iterator It =
1823 Doc->getTagMap().find(TagHandle);
1824 if (It != Doc->getTagMap().end())
1828 T.Kind = Token::TK_Tag;
1829 T.Range = TagHandle;
1830 setError(Twine("Unknown tag handle ") + TagHandle, T);
1832 Ret += Raw.substr(Raw.find_last_of('!') + 1);
1837 switch (getType()) {
1839 return "tag:yaml.org,2002:null";
1841 case NK_BlockScalar:
1842 // TODO: Tag resolution.
1843 return "tag:yaml.org,2002:str";
1845 return "tag:yaml.org,2002:map";
1847 return "tag:yaml.org,2002:seq";
1853 Token &Node::peekNext() {
1854 return Doc->peekNext();
1857 Token Node::getNext() {
1858 return Doc->getNext();
1861 Node *Node::parseBlockNode() {
1862 return Doc->parseBlockNode();
1865 BumpPtrAllocator &Node::getAllocator() {
1866 return Doc->NodeAllocator;
1869 void Node::setError(const Twine &Msg, Token &Tok) const {
1870 Doc->setError(Msg, Tok);
1873 bool Node::failed() const {
1874 return Doc->failed();
1877 StringRef ScalarNode::getValue(SmallVectorImpl<char> &Storage) const {
1878 // TODO: Handle newlines properly. We need to remove leading whitespace.
1879 if (Value[0] == '"') { // Double quoted.
1880 // Pull off the leading and trailing "s.
1881 StringRef UnquotedValue = Value.substr(1, Value.size() - 2);
1882 // Search for characters that would require unescaping the value.
1883 StringRef::size_type i = UnquotedValue.find_first_of("\\\r\n");
1884 if (i != StringRef::npos)
1885 return unescapeDoubleQuoted(UnquotedValue, i, Storage);
1886 return UnquotedValue;
1887 } else if (Value[0] == '\'') { // Single quoted.
1888 // Pull off the leading and trailing 's.
1889 StringRef UnquotedValue = Value.substr(1, Value.size() - 2);
1890 StringRef::size_type i = UnquotedValue.find('\'');
1891 if (i != StringRef::npos) {
1892 // We're going to need Storage.
1894 Storage.reserve(UnquotedValue.size());
1895 for (; i != StringRef::npos; i = UnquotedValue.find('\'')) {
1896 StringRef Valid(UnquotedValue.begin(), i);
1897 Storage.insert(Storage.end(), Valid.begin(), Valid.end());
1898 Storage.push_back('\'');
1899 UnquotedValue = UnquotedValue.substr(i + 2);
1901 Storage.insert(Storage.end(), UnquotedValue.begin(), UnquotedValue.end());
1902 return StringRef(Storage.begin(), Storage.size());
1904 return UnquotedValue;
1907 return Value.rtrim(' ');
1910 StringRef ScalarNode::unescapeDoubleQuoted( StringRef UnquotedValue
1911 , StringRef::size_type i
1912 , SmallVectorImpl<char> &Storage)
1914 // Use Storage to build proper value.
1916 Storage.reserve(UnquotedValue.size());
1917 for (; i != StringRef::npos; i = UnquotedValue.find_first_of("\\\r\n")) {
1918 // Insert all previous chars into Storage.
1919 StringRef Valid(UnquotedValue.begin(), i);
1920 Storage.insert(Storage.end(), Valid.begin(), Valid.end());
1921 // Chop off inserted chars.
1922 UnquotedValue = UnquotedValue.substr(i);
1924 assert(!UnquotedValue.empty() && "Can't be empty!");
1926 // Parse escape or line break.
1927 switch (UnquotedValue[0]) {
1930 Storage.push_back('\n');
1931 if ( UnquotedValue.size() > 1
1932 && (UnquotedValue[1] == '\r' || UnquotedValue[1] == '\n'))
1933 UnquotedValue = UnquotedValue.substr(1);
1934 UnquotedValue = UnquotedValue.substr(1);
1937 if (UnquotedValue.size() == 1)
1938 // TODO: Report error.
1940 UnquotedValue = UnquotedValue.substr(1);
1941 switch (UnquotedValue[0]) {
1944 T.Range = StringRef(UnquotedValue.begin(), 1);
1945 setError("Unrecognized escape code!", T);
1950 // Remove the new line.
1951 if ( UnquotedValue.size() > 1
1952 && (UnquotedValue[1] == '\r' || UnquotedValue[1] == '\n'))
1953 UnquotedValue = UnquotedValue.substr(1);
1954 // If this was just a single byte newline, it will get skipped
1958 Storage.push_back(0x00);
1961 Storage.push_back(0x07);
1964 Storage.push_back(0x08);
1968 Storage.push_back(0x09);
1971 Storage.push_back(0x0A);
1974 Storage.push_back(0x0B);
1977 Storage.push_back(0x0C);
1980 Storage.push_back(0x0D);
1983 Storage.push_back(0x1B);
1986 Storage.push_back(0x20);
1989 Storage.push_back(0x22);
1992 Storage.push_back(0x2F);
1995 Storage.push_back(0x5C);
1998 encodeUTF8(0x85, Storage);
2001 encodeUTF8(0xA0, Storage);
2004 encodeUTF8(0x2028, Storage);
2007 encodeUTF8(0x2029, Storage);
2010 if (UnquotedValue.size() < 3)
2011 // TODO: Report error.
2013 unsigned int UnicodeScalarValue;
2014 if (UnquotedValue.substr(1, 2).getAsInteger(16, UnicodeScalarValue))
2015 // TODO: Report error.
2016 UnicodeScalarValue = 0xFFFD;
2017 encodeUTF8(UnicodeScalarValue, Storage);
2018 UnquotedValue = UnquotedValue.substr(2);
2022 if (UnquotedValue.size() < 5)
2023 // TODO: Report error.
2025 unsigned int UnicodeScalarValue;
2026 if (UnquotedValue.substr(1, 4).getAsInteger(16, UnicodeScalarValue))
2027 // TODO: Report error.
2028 UnicodeScalarValue = 0xFFFD;
2029 encodeUTF8(UnicodeScalarValue, Storage);
2030 UnquotedValue = UnquotedValue.substr(4);
2034 if (UnquotedValue.size() < 9)
2035 // TODO: Report error.
2037 unsigned int UnicodeScalarValue;
2038 if (UnquotedValue.substr(1, 8).getAsInteger(16, UnicodeScalarValue))
2039 // TODO: Report error.
2040 UnicodeScalarValue = 0xFFFD;
2041 encodeUTF8(UnicodeScalarValue, Storage);
2042 UnquotedValue = UnquotedValue.substr(8);
2046 UnquotedValue = UnquotedValue.substr(1);
2049 Storage.insert(Storage.end(), UnquotedValue.begin(), UnquotedValue.end());
2050 return StringRef(Storage.begin(), Storage.size());
2053 Node *KeyValueNode::getKey() {
2056 // Handle implicit null keys.
2058 Token &t = peekNext();
2059 if ( t.Kind == Token::TK_BlockEnd
2060 || t.Kind == Token::TK_Value
2061 || t.Kind == Token::TK_Error) {
2062 return Key = new (getAllocator()) NullNode(Doc);
2064 if (t.Kind == Token::TK_Key)
2065 getNext(); // skip TK_Key.
2068 // Handle explicit null keys.
2069 Token &t = peekNext();
2070 if (t.Kind == Token::TK_BlockEnd || t.Kind == Token::TK_Value) {
2071 return Key = new (getAllocator()) NullNode(Doc);
2074 // We've got a normal key.
2075 return Key = parseBlockNode();
2078 Node *KeyValueNode::getValue() {
2083 return Value = new (getAllocator()) NullNode(Doc);
2085 // Handle implicit null values.
2087 Token &t = peekNext();
2088 if ( t.Kind == Token::TK_BlockEnd
2089 || t.Kind == Token::TK_FlowMappingEnd
2090 || t.Kind == Token::TK_Key
2091 || t.Kind == Token::TK_FlowEntry
2092 || t.Kind == Token::TK_Error) {
2093 return Value = new (getAllocator()) NullNode(Doc);
2096 if (t.Kind != Token::TK_Value) {
2097 setError("Unexpected token in Key Value.", t);
2098 return Value = new (getAllocator()) NullNode(Doc);
2100 getNext(); // skip TK_Value.
2103 // Handle explicit null values.
2104 Token &t = peekNext();
2105 if (t.Kind == Token::TK_BlockEnd || t.Kind == Token::TK_Key) {
2106 return Value = new (getAllocator()) NullNode(Doc);
2109 // We got a normal value.
2110 return Value = parseBlockNode();
2113 void MappingNode::increment() {
2116 CurrentEntry = nullptr;
2120 CurrentEntry->skip();
2121 if (Type == MT_Inline) {
2123 CurrentEntry = nullptr;
2127 Token T = peekNext();
2128 if (T.Kind == Token::TK_Key || T.Kind == Token::TK_Scalar) {
2129 // KeyValueNode eats the TK_Key. That way it can detect null keys.
2130 CurrentEntry = new (getAllocator()) KeyValueNode(Doc);
2131 } else if (Type == MT_Block) {
2133 case Token::TK_BlockEnd:
2136 CurrentEntry = nullptr;
2139 setError("Unexpected token. Expected Key or Block End", T);
2141 case Token::TK_Error:
2143 CurrentEntry = nullptr;
2147 case Token::TK_FlowEntry:
2148 // Eat the flow entry and recurse.
2151 case Token::TK_FlowMappingEnd:
2154 case Token::TK_Error:
2155 // Set this to end iterator.
2157 CurrentEntry = nullptr;
2160 setError( "Unexpected token. Expected Key, Flow Entry, or Flow "
2164 CurrentEntry = nullptr;
2169 void SequenceNode::increment() {
2172 CurrentEntry = nullptr;
2176 CurrentEntry->skip();
2177 Token T = peekNext();
2178 if (SeqType == ST_Block) {
2180 case Token::TK_BlockEntry:
2182 CurrentEntry = parseBlockNode();
2183 if (!CurrentEntry) { // An error occurred.
2185 CurrentEntry = nullptr;
2188 case Token::TK_BlockEnd:
2191 CurrentEntry = nullptr;
2194 setError( "Unexpected token. Expected Block Entry or Block End."
2197 case Token::TK_Error:
2199 CurrentEntry = nullptr;
2201 } else if (SeqType == ST_Indentless) {
2203 case Token::TK_BlockEntry:
2205 CurrentEntry = parseBlockNode();
2206 if (!CurrentEntry) { // An error occurred.
2208 CurrentEntry = nullptr;
2212 case Token::TK_Error:
2214 CurrentEntry = nullptr;
2216 } else if (SeqType == ST_Flow) {
2218 case Token::TK_FlowEntry:
2219 // Eat the flow entry and recurse.
2221 WasPreviousTokenFlowEntry = true;
2223 case Token::TK_FlowSequenceEnd:
2226 case Token::TK_Error:
2227 // Set this to end iterator.
2229 CurrentEntry = nullptr;
2231 case Token::TK_StreamEnd:
2232 case Token::TK_DocumentEnd:
2233 case Token::TK_DocumentStart:
2234 setError("Could not find closing ]!", T);
2235 // Set this to end iterator.
2237 CurrentEntry = nullptr;
2240 if (!WasPreviousTokenFlowEntry) {
2241 setError("Expected , between entries!", T);
2243 CurrentEntry = nullptr;
2246 // Otherwise it must be a flow entry.
2247 CurrentEntry = parseBlockNode();
2248 if (!CurrentEntry) {
2251 WasPreviousTokenFlowEntry = false;
2257 Document::Document(Stream &S) : stream(S), Root(nullptr) {
2258 // Tag maps starts with two default mappings.
2260 TagMap["!!"] = "tag:yaml.org,2002:";
2262 if (parseDirectives())
2263 expectToken(Token::TK_DocumentStart);
2264 Token &T = peekNext();
2265 if (T.Kind == Token::TK_DocumentStart)
2269 bool Document::skip() {
2270 if (stream.scanner->failed())
2275 Token &T = peekNext();
2276 if (T.Kind == Token::TK_StreamEnd)
2278 if (T.Kind == Token::TK_DocumentEnd) {
2285 Token &Document::peekNext() {
2286 return stream.scanner->peekNext();
2289 Token Document::getNext() {
2290 return stream.scanner->getNext();
2293 void Document::setError(const Twine &Message, Token &Location) const {
2294 stream.scanner->setError(Message, Location.Range.begin());
2297 bool Document::failed() const {
2298 return stream.scanner->failed();
2301 Node *Document::parseBlockNode() {
2302 Token T = peekNext();
2303 // Handle properties.
2308 case Token::TK_Alias:
2310 return new (NodeAllocator) AliasNode(stream.CurrentDoc, T.Range.substr(1));
2311 case Token::TK_Anchor:
2312 if (AnchorInfo.Kind == Token::TK_Anchor) {
2313 setError("Already encountered an anchor for this node!", T);
2316 AnchorInfo = getNext(); // Consume TK_Anchor.
2318 goto parse_property;
2320 if (TagInfo.Kind == Token::TK_Tag) {
2321 setError("Already encountered a tag for this node!", T);
2324 TagInfo = getNext(); // Consume TK_Tag.
2326 goto parse_property;
2332 case Token::TK_BlockEntry:
2333 // We got an unindented BlockEntry sequence. This is not terminated with
2335 // Don't eat the TK_BlockEntry, SequenceNode needs it.
2336 return new (NodeAllocator) SequenceNode( stream.CurrentDoc
2337 , AnchorInfo.Range.substr(1)
2339 , SequenceNode::ST_Indentless);
2340 case Token::TK_BlockSequenceStart:
2342 return new (NodeAllocator)
2343 SequenceNode( stream.CurrentDoc
2344 , AnchorInfo.Range.substr(1)
2346 , SequenceNode::ST_Block);
2347 case Token::TK_BlockMappingStart:
2349 return new (NodeAllocator)
2350 MappingNode( stream.CurrentDoc
2351 , AnchorInfo.Range.substr(1)
2353 , MappingNode::MT_Block);
2354 case Token::TK_FlowSequenceStart:
2356 return new (NodeAllocator)
2357 SequenceNode( stream.CurrentDoc
2358 , AnchorInfo.Range.substr(1)
2360 , SequenceNode::ST_Flow);
2361 case Token::TK_FlowMappingStart:
2363 return new (NodeAllocator)
2364 MappingNode( stream.CurrentDoc
2365 , AnchorInfo.Range.substr(1)
2367 , MappingNode::MT_Flow);
2368 case Token::TK_Scalar:
2370 return new (NodeAllocator)
2371 ScalarNode( stream.CurrentDoc
2372 , AnchorInfo.Range.substr(1)
2375 case Token::TK_BlockScalar: {
2377 StringRef NullTerminatedStr(T.Value.c_str(), T.Value.length() + 1);
2378 StringRef StrCopy = NullTerminatedStr.copy(NodeAllocator).drop_back();
2379 return new (NodeAllocator)
2380 BlockScalarNode(stream.CurrentDoc, AnchorInfo.Range.substr(1),
2381 TagInfo.Range, StrCopy, T.Range);
2384 // Don't eat the TK_Key, KeyValueNode expects it.
2385 return new (NodeAllocator)
2386 MappingNode( stream.CurrentDoc
2387 , AnchorInfo.Range.substr(1)
2389 , MappingNode::MT_Inline);
2390 case Token::TK_DocumentStart:
2391 case Token::TK_DocumentEnd:
2392 case Token::TK_StreamEnd:
2394 // TODO: Properly handle tags. "[!!str ]" should resolve to !!str "", not
2396 return new (NodeAllocator) NullNode(stream.CurrentDoc);
2397 case Token::TK_Error:
2400 llvm_unreachable("Control flow shouldn't reach here.");
2404 bool Document::parseDirectives() {
2405 bool isDirective = false;
2407 Token T = peekNext();
2408 if (T.Kind == Token::TK_TagDirective) {
2409 parseTAGDirective();
2411 } else if (T.Kind == Token::TK_VersionDirective) {
2412 parseYAMLDirective();
2420 void Document::parseYAMLDirective() {
2421 getNext(); // Eat %YAML <version>
2424 void Document::parseTAGDirective() {
2425 Token Tag = getNext(); // %TAG <handle> <prefix>
2426 StringRef T = Tag.Range;
2428 T = T.substr(T.find_first_of(" \t")).ltrim(" \t");
2429 std::size_t HandleEnd = T.find_first_of(" \t");
2430 StringRef TagHandle = T.substr(0, HandleEnd);
2431 StringRef TagPrefix = T.substr(HandleEnd).ltrim(" \t");
2432 TagMap[TagHandle] = TagPrefix;
2435 bool Document::expectToken(int TK) {
2436 Token T = getNext();
2438 setError("Unexpected token", T);