1 //===--- YAMLParser.cpp - Simple YAML parser ------------------------------===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This file implements a YAML parser.
12 //===----------------------------------------------------------------------===//
14 #include "llvm/Support/YAMLParser.h"
15 #include "llvm/ADT/STLExtras.h"
16 #include "llvm/ADT/SmallString.h"
17 #include "llvm/ADT/SmallVector.h"
18 #include "llvm/ADT/StringExtras.h"
19 #include "llvm/ADT/Twine.h"
20 #include "llvm/ADT/AllocatorList.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"
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.
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;
42 /// getUnicodeEncoding - Reads up to the first 4 bytes to determine the Unicode
43 /// encoding form of \a Input.
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);
52 switch (uint8_t(Input[0])) {
54 if (Input.size() >= 4) {
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);
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);
67 if ( Input.size() >= 4
68 && uint8_t(Input[1]) == 0xFE
71 return std::make_pair(UEF_UTF32_LE, 4);
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);
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);
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);
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);
92 if (Input.size() >= 2 && Input[1] == 0)
93 return std::make_pair(UEF_UTF16_LE, 0);
95 return std::make_pair(UEF_UTF8, 0);
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() {}
110 /// Token - A single YAML token.
113 TK_Error, // Uninitialized token.
122 TK_BlockSequenceStart,
123 TK_BlockMappingStart,
125 TK_FlowSequenceStart,
138 /// A string of length 0 or more whose begin() points to the logical location
139 /// of the token in the input.
142 /// The value of a block scalar node.
145 Token() : Kind(TK_Error) {}
150 typedef llvm::BumpPtrList<Token> TokenQueueT;
153 /// @brief This struct is used to track simple keys.
155 /// Simple keys are handled by creating an entry in SimpleKeys for each Token
156 /// which could legally be the start of a simple key. When peekNext is called,
157 /// if the Token To be returned is referenced by a SimpleKey, we continue
158 /// tokenizing until that potential simple key has either been found to not be
159 /// a simple key (we moved on to the next line or went further than 1024 chars).
160 /// Or when we run into a Value, and then insert a Key token (and possibly
161 /// others) before the SimpleKey's Tok.
163 TokenQueueT::iterator Tok;
169 bool operator ==(const SimpleKey &Other) {
170 return Tok == Other.Tok;
175 /// @brief The Unicode scalar value of a UTF-8 minimal well-formed code unit
176 /// subsequence and the subsequence's length in code units (uint8_t).
177 /// A length of 0 represents an error.
178 typedef std::pair<uint32_t, unsigned> UTF8Decoded;
180 static UTF8Decoded decodeUTF8(StringRef Range) {
181 StringRef::iterator Position= Range.begin();
182 StringRef::iterator End = Range.end();
183 // 1 byte: [0x00, 0x7f]
184 // Bit pattern: 0xxxxxxx
185 if ((*Position & 0x80) == 0) {
186 return std::make_pair(*Position, 1);
188 // 2 bytes: [0x80, 0x7ff]
189 // Bit pattern: 110xxxxx 10xxxxxx
190 if (Position + 1 != End &&
191 ((*Position & 0xE0) == 0xC0) &&
192 ((*(Position + 1) & 0xC0) == 0x80)) {
193 uint32_t codepoint = ((*Position & 0x1F) << 6) |
194 (*(Position + 1) & 0x3F);
195 if (codepoint >= 0x80)
196 return std::make_pair(codepoint, 2);
198 // 3 bytes: [0x8000, 0xffff]
199 // Bit pattern: 1110xxxx 10xxxxxx 10xxxxxx
200 if (Position + 2 != End &&
201 ((*Position & 0xF0) == 0xE0) &&
202 ((*(Position + 1) & 0xC0) == 0x80) &&
203 ((*(Position + 2) & 0xC0) == 0x80)) {
204 uint32_t codepoint = ((*Position & 0x0F) << 12) |
205 ((*(Position + 1) & 0x3F) << 6) |
206 (*(Position + 2) & 0x3F);
207 // Codepoints between 0xD800 and 0xDFFF are invalid, as
208 // they are high / low surrogate halves used by UTF-16.
209 if (codepoint >= 0x800 &&
210 (codepoint < 0xD800 || codepoint > 0xDFFF))
211 return std::make_pair(codepoint, 3);
213 // 4 bytes: [0x10000, 0x10FFFF]
214 // Bit pattern: 11110xxx 10xxxxxx 10xxxxxx 10xxxxxx
215 if (Position + 3 != End &&
216 ((*Position & 0xF8) == 0xF0) &&
217 ((*(Position + 1) & 0xC0) == 0x80) &&
218 ((*(Position + 2) & 0xC0) == 0x80) &&
219 ((*(Position + 3) & 0xC0) == 0x80)) {
220 uint32_t codepoint = ((*Position & 0x07) << 18) |
221 ((*(Position + 1) & 0x3F) << 12) |
222 ((*(Position + 2) & 0x3F) << 6) |
223 (*(Position + 3) & 0x3F);
224 if (codepoint >= 0x10000 && codepoint <= 0x10FFFF)
225 return std::make_pair(codepoint, 4);
227 return std::make_pair(0, 0);
232 /// @brief Scans YAML tokens from a MemoryBuffer.
235 Scanner(StringRef Input, SourceMgr &SM, bool ShowColors = true,
236 std::error_code *EC = nullptr);
237 Scanner(MemoryBufferRef Buffer, SourceMgr &SM_, bool ShowColors = true,
238 std::error_code *EC = nullptr);
240 /// @brief Parse the next token and return it without popping it.
243 /// @brief Parse the next token and pop it from the queue.
246 void printError(SMLoc Loc, SourceMgr::DiagKind Kind, const Twine &Message,
247 ArrayRef<SMRange> Ranges = None) {
248 SM.PrintMessage(Loc, Kind, Message, Ranges, /* FixIts= */ None, ShowColors);
251 void setError(const Twine &Message, StringRef::iterator Position) {
255 // propagate the error if possible
257 *EC = make_error_code(std::errc::invalid_argument);
259 // Don't print out more errors after the first one we encounter. The rest
260 // are just the result of the first, and have no meaning.
262 printError(SMLoc::getFromPointer(Current), SourceMgr::DK_Error, Message);
266 void setError(const Twine &Message) {
267 setError(Message, Current);
270 /// @brief Returns true if an error occurred while parsing.
276 void init(MemoryBufferRef Buffer);
278 StringRef currentInput() {
279 return StringRef(Current, End - Current);
282 /// @brief Decode a UTF-8 minimal well-formed code unit subsequence starting
285 /// If the UTF-8 code units starting at Position do not form a well-formed
286 /// code unit subsequence, then the Unicode scalar value is 0, and the length
288 UTF8Decoded decodeUTF8(StringRef::iterator Position) {
289 return ::decodeUTF8(StringRef(Position, End - Position));
292 // The following functions are based on the gramar rules in the YAML spec. The
293 // style of the function names it meant to closely match how they are written
294 // in the spec. The number within the [] is the number of the grammar rule in
297 // See 4.2 [Production Naming Conventions] for the meaning of the prefixes.
300 // A production starting and ending with a special character.
302 // A production matching a single line break.
304 // A production starting and ending with a non-break character.
306 // A production starting and ending with a white space character.
308 // A production starting and ending with a non-space character.
310 // A production matching complete line(s).
312 /// @brief Skip a single nb-char[27] starting at Position.
314 /// A nb-char is 0x9 | [0x20-0x7E] | 0x85 | [0xA0-0xD7FF] | [0xE000-0xFEFE]
315 /// | [0xFF00-0xFFFD] | [0x10000-0x10FFFF]
317 /// @returns The code unit after the nb-char, or Position if it's not an
319 StringRef::iterator skip_nb_char(StringRef::iterator Position);
321 /// @brief Skip a single b-break[28] starting at Position.
323 /// A b-break is 0xD 0xA | 0xD | 0xA
325 /// @returns The code unit after the b-break, or Position if it's not a
327 StringRef::iterator skip_b_break(StringRef::iterator Position);
329 /// Skip a single s-space[31] starting at Position.
331 /// An s-space is 0x20
333 /// @returns The code unit after the s-space, or Position if it's not a
335 StringRef::iterator skip_s_space(StringRef::iterator Position);
337 /// @brief Skip a single s-white[33] starting at Position.
339 /// A s-white is 0x20 | 0x9
341 /// @returns The code unit after the s-white, or Position if it's not a
343 StringRef::iterator skip_s_white(StringRef::iterator Position);
345 /// @brief Skip a single ns-char[34] starting at Position.
347 /// A ns-char is nb-char - s-white
349 /// @returns The code unit after the ns-char, or Position if it's not a
351 StringRef::iterator skip_ns_char(StringRef::iterator Position);
353 typedef StringRef::iterator (Scanner::*SkipWhileFunc)(StringRef::iterator);
354 /// @brief Skip minimal well-formed code unit subsequences until Func
355 /// returns its input.
357 /// @returns The code unit after the last minimal well-formed code unit
358 /// subsequence that Func accepted.
359 StringRef::iterator skip_while( SkipWhileFunc Func
360 , StringRef::iterator Position);
362 /// Skip minimal well-formed code unit subsequences until Func returns its
364 void advanceWhile(SkipWhileFunc Func);
366 /// @brief Scan ns-uri-char[39]s starting at Cur.
368 /// This updates Cur and Column while scanning.
369 void scan_ns_uri_char();
371 /// @brief Consume a minimal well-formed code unit subsequence starting at
372 /// \a Cur. Return false if it is not the same Unicode scalar value as
373 /// \a Expected. This updates \a Column.
374 bool consume(uint32_t Expected);
376 /// @brief Skip \a Distance UTF-8 code units. Updates \a Cur and \a Column.
377 void skip(uint32_t Distance);
379 /// @brief Return true if the minimal well-formed code unit subsequence at
380 /// Pos is whitespace or a new line
381 bool isBlankOrBreak(StringRef::iterator Position);
383 /// Consume a single b-break[28] if it's present at the current position.
385 /// Return false if the code unit at the current position isn't a line break.
386 bool consumeLineBreakIfPresent();
388 /// @brief If IsSimpleKeyAllowed, create and push_back a new SimpleKey.
389 void saveSimpleKeyCandidate( TokenQueueT::iterator Tok
393 /// @brief Remove simple keys that can no longer be valid simple keys.
395 /// Invalid simple keys are not on the current line or are further than 1024
397 void removeStaleSimpleKeyCandidates();
399 /// @brief Remove all simple keys on FlowLevel \a Level.
400 void removeSimpleKeyCandidatesOnFlowLevel(unsigned Level);
402 /// @brief Unroll indentation in \a Indents back to \a Col. Creates BlockEnd
403 /// tokens if needed.
404 bool unrollIndent(int ToColumn);
406 /// @brief Increase indent to \a Col. Creates \a Kind token at \a InsertPoint
408 bool rollIndent( int ToColumn
409 , Token::TokenKind Kind
410 , TokenQueueT::iterator InsertPoint);
412 /// @brief Skip a single-line comment when the comment starts at the current
413 /// position of the scanner.
416 /// @brief Skip whitespace and comments until the start of the next token.
417 void scanToNextToken();
419 /// @brief Must be the first token generated.
420 bool scanStreamStart();
422 /// @brief Generate tokens needed to close out the stream.
423 bool scanStreamEnd();
425 /// @brief Scan a %BLAH directive.
426 bool scanDirective();
428 /// @brief Scan a ... or ---.
429 bool scanDocumentIndicator(bool IsStart);
431 /// @brief Scan a [ or { and generate the proper flow collection start token.
432 bool scanFlowCollectionStart(bool IsSequence);
434 /// @brief Scan a ] or } and generate the proper flow collection end token.
435 bool scanFlowCollectionEnd(bool IsSequence);
437 /// @brief Scan the , that separates entries in a flow collection.
438 bool scanFlowEntry();
440 /// @brief Scan the - that starts block sequence entries.
441 bool scanBlockEntry();
443 /// @brief Scan an explicit ? indicating a key.
446 /// @brief Scan an explicit : indicating a value.
449 /// @brief Scan a quoted scalar.
450 bool scanFlowScalar(bool IsDoubleQuoted);
452 /// @brief Scan an unquoted scalar.
453 bool scanPlainScalar();
455 /// @brief Scan an Alias or Anchor starting with * or &.
456 bool scanAliasOrAnchor(bool IsAlias);
458 /// @brief Scan a block scalar starting with | or >.
459 bool scanBlockScalar(bool IsLiteral);
461 /// Scan a chomping indicator in a block scalar header.
462 char scanBlockChompingIndicator();
464 /// Scan an indentation indicator in a block scalar header.
465 unsigned scanBlockIndentationIndicator();
467 /// Scan a block scalar header.
469 /// Return false if an error occurred.
470 bool scanBlockScalarHeader(char &ChompingIndicator, unsigned &IndentIndicator,
473 /// Look for the indentation level of a block scalar.
475 /// Return false if an error occurred.
476 bool findBlockScalarIndent(unsigned &BlockIndent, unsigned BlockExitIndent,
477 unsigned &LineBreaks, bool &IsDone);
479 /// Scan the indentation of a text line in a block scalar.
481 /// Return false if an error occurred.
482 bool scanBlockScalarIndent(unsigned BlockIndent, unsigned BlockExitIndent,
485 /// @brief Scan a tag of the form !stuff.
488 /// @brief Dispatch to the next scanning function based on \a *Cur.
489 bool fetchMoreTokens();
491 /// @brief The SourceMgr used for diagnostics and buffer management.
494 /// @brief The original input.
495 MemoryBufferRef InputBuffer;
497 /// @brief The current position of the scanner.
498 StringRef::iterator Current;
500 /// @brief The end of the input (one past the last character).
501 StringRef::iterator End;
503 /// @brief Current YAML indentation level in spaces.
506 /// @brief Current column number in Unicode code points.
509 /// @brief Current line number.
512 /// @brief How deep we are in flow style containers. 0 Means at block level.
515 /// @brief Are we at the start of the stream?
516 bool IsStartOfStream;
518 /// @brief Can the next token be the start of a simple key?
519 bool IsSimpleKeyAllowed;
521 /// @brief True if an error has occurred.
524 /// @brief Should colors be used when printing out the diagnostic messages?
527 /// @brief Queue of tokens. This is required to queue up tokens while looking
528 /// for the end of a simple key. And for cases where a single character
529 /// can produce multiple tokens (e.g. BlockEnd).
530 TokenQueueT TokenQueue;
532 /// @brief Indentation levels.
533 SmallVector<int, 4> Indents;
535 /// @brief Potential simple keys.
536 SmallVector<SimpleKey, 4> SimpleKeys;
541 } // end namespace yaml
542 } // end namespace llvm
544 /// encodeUTF8 - Encode \a UnicodeScalarValue in UTF-8 and append it to result.
545 static void encodeUTF8( uint32_t UnicodeScalarValue
546 , SmallVectorImpl<char> &Result) {
547 if (UnicodeScalarValue <= 0x7F) {
548 Result.push_back(UnicodeScalarValue & 0x7F);
549 } else if (UnicodeScalarValue <= 0x7FF) {
550 uint8_t FirstByte = 0xC0 | ((UnicodeScalarValue & 0x7C0) >> 6);
551 uint8_t SecondByte = 0x80 | (UnicodeScalarValue & 0x3F);
552 Result.push_back(FirstByte);
553 Result.push_back(SecondByte);
554 } else if (UnicodeScalarValue <= 0xFFFF) {
555 uint8_t FirstByte = 0xE0 | ((UnicodeScalarValue & 0xF000) >> 12);
556 uint8_t SecondByte = 0x80 | ((UnicodeScalarValue & 0xFC0) >> 6);
557 uint8_t ThirdByte = 0x80 | (UnicodeScalarValue & 0x3F);
558 Result.push_back(FirstByte);
559 Result.push_back(SecondByte);
560 Result.push_back(ThirdByte);
561 } else if (UnicodeScalarValue <= 0x10FFFF) {
562 uint8_t FirstByte = 0xF0 | ((UnicodeScalarValue & 0x1F0000) >> 18);
563 uint8_t SecondByte = 0x80 | ((UnicodeScalarValue & 0x3F000) >> 12);
564 uint8_t ThirdByte = 0x80 | ((UnicodeScalarValue & 0xFC0) >> 6);
565 uint8_t FourthByte = 0x80 | (UnicodeScalarValue & 0x3F);
566 Result.push_back(FirstByte);
567 Result.push_back(SecondByte);
568 Result.push_back(ThirdByte);
569 Result.push_back(FourthByte);
573 bool yaml::dumpTokens(StringRef Input, raw_ostream &OS) {
575 Scanner scanner(Input, SM);
577 Token T = scanner.getNext();
579 case Token::TK_StreamStart:
580 OS << "Stream-Start: ";
582 case Token::TK_StreamEnd:
583 OS << "Stream-End: ";
585 case Token::TK_VersionDirective:
586 OS << "Version-Directive: ";
588 case Token::TK_TagDirective:
589 OS << "Tag-Directive: ";
591 case Token::TK_DocumentStart:
592 OS << "Document-Start: ";
594 case Token::TK_DocumentEnd:
595 OS << "Document-End: ";
597 case Token::TK_BlockEntry:
598 OS << "Block-Entry: ";
600 case Token::TK_BlockEnd:
603 case Token::TK_BlockSequenceStart:
604 OS << "Block-Sequence-Start: ";
606 case Token::TK_BlockMappingStart:
607 OS << "Block-Mapping-Start: ";
609 case Token::TK_FlowEntry:
610 OS << "Flow-Entry: ";
612 case Token::TK_FlowSequenceStart:
613 OS << "Flow-Sequence-Start: ";
615 case Token::TK_FlowSequenceEnd:
616 OS << "Flow-Sequence-End: ";
618 case Token::TK_FlowMappingStart:
619 OS << "Flow-Mapping-Start: ";
621 case Token::TK_FlowMappingEnd:
622 OS << "Flow-Mapping-End: ";
627 case Token::TK_Value:
630 case Token::TK_Scalar:
633 case Token::TK_BlockScalar:
634 OS << "Block Scalar: ";
636 case Token::TK_Alias:
639 case Token::TK_Anchor:
645 case Token::TK_Error:
648 OS << T.Range << "\n";
649 if (T.Kind == Token::TK_StreamEnd)
651 else if (T.Kind == Token::TK_Error)
657 bool yaml::scanTokens(StringRef Input) {
659 llvm::yaml::Scanner scanner(Input, SM);
661 llvm::yaml::Token T = scanner.getNext();
662 if (T.Kind == Token::TK_StreamEnd)
664 else if (T.Kind == Token::TK_Error)
670 std::string yaml::escape(StringRef Input) {
671 std::string EscapedInput;
672 for (StringRef::iterator i = Input.begin(), e = Input.end(); i != e; ++i) {
674 EscapedInput += "\\\\";
676 EscapedInput += "\\\"";
678 EscapedInput += "\\0";
680 EscapedInput += "\\a";
682 EscapedInput += "\\b";
684 EscapedInput += "\\t";
686 EscapedInput += "\\n";
688 EscapedInput += "\\v";
690 EscapedInput += "\\f";
692 EscapedInput += "\\r";
694 EscapedInput += "\\e";
695 else if ((unsigned char)*i < 0x20) { // Control characters not handled above.
696 std::string HexStr = utohexstr(*i);
697 EscapedInput += "\\x" + std::string(2 - HexStr.size(), '0') + HexStr;
698 } else if (*i & 0x80) { // UTF-8 multiple code unit subsequence.
699 UTF8Decoded UnicodeScalarValue
700 = decodeUTF8(StringRef(i, Input.end() - i));
701 if (UnicodeScalarValue.second == 0) {
702 // Found invalid char.
704 encodeUTF8(0xFFFD, Val);
705 EscapedInput.insert(EscapedInput.end(), Val.begin(), Val.end());
706 // FIXME: Error reporting.
709 if (UnicodeScalarValue.first == 0x85)
710 EscapedInput += "\\N";
711 else if (UnicodeScalarValue.first == 0xA0)
712 EscapedInput += "\\_";
713 else if (UnicodeScalarValue.first == 0x2028)
714 EscapedInput += "\\L";
715 else if (UnicodeScalarValue.first == 0x2029)
716 EscapedInput += "\\P";
718 std::string HexStr = utohexstr(UnicodeScalarValue.first);
719 if (HexStr.size() <= 2)
720 EscapedInput += "\\x" + std::string(2 - HexStr.size(), '0') + HexStr;
721 else if (HexStr.size() <= 4)
722 EscapedInput += "\\u" + std::string(4 - HexStr.size(), '0') + HexStr;
723 else if (HexStr.size() <= 8)
724 EscapedInput += "\\U" + std::string(8 - HexStr.size(), '0') + HexStr;
726 i += UnicodeScalarValue.second - 1;
728 EscapedInput.push_back(*i);
733 Scanner::Scanner(StringRef Input, SourceMgr &sm, bool ShowColors,
735 : SM(sm), ShowColors(ShowColors), EC(EC) {
736 init(MemoryBufferRef(Input, "YAML"));
739 Scanner::Scanner(MemoryBufferRef Buffer, SourceMgr &SM_, bool ShowColors,
741 : SM(SM_), ShowColors(ShowColors), EC(EC) {
745 void Scanner::init(MemoryBufferRef Buffer) {
746 InputBuffer = Buffer;
747 Current = InputBuffer.getBufferStart();
748 End = InputBuffer.getBufferEnd();
753 IsStartOfStream = true;
754 IsSimpleKeyAllowed = true;
756 std::unique_ptr<MemoryBuffer> InputBufferOwner =
757 MemoryBuffer::getMemBuffer(Buffer);
758 SM.AddNewSourceBuffer(std::move(InputBufferOwner), SMLoc());
761 Token &Scanner::peekNext() {
762 // If the current token is a possible simple key, keep parsing until we
764 bool NeedMore = false;
766 if (TokenQueue.empty() || NeedMore) {
767 if (!fetchMoreTokens()) {
769 TokenQueue.push_back(Token());
770 return TokenQueue.front();
773 assert(!TokenQueue.empty() &&
774 "fetchMoreTokens lied about getting tokens!");
776 removeStaleSimpleKeyCandidates();
778 SK.Tok = TokenQueue.begin();
779 if (!is_contained(SimpleKeys, SK))
784 return TokenQueue.front();
787 Token Scanner::getNext() {
788 Token Ret = peekNext();
789 // TokenQueue can be empty if there was an error getting the next token.
790 if (!TokenQueue.empty())
791 TokenQueue.pop_front();
793 // There cannot be any referenced Token's if the TokenQueue is empty. So do a
794 // quick deallocation of them all.
795 if (TokenQueue.empty())
796 TokenQueue.resetAlloc();
801 StringRef::iterator Scanner::skip_nb_char(StringRef::iterator Position) {
804 // Check 7 bit c-printable - b-char.
805 if ( *Position == 0x09
806 || (*Position >= 0x20 && *Position <= 0x7E))
809 // Check for valid UTF-8.
810 if (uint8_t(*Position) & 0x80) {
811 UTF8Decoded u8d = decodeUTF8(Position);
813 && u8d.first != 0xFEFF
814 && ( u8d.first == 0x85
815 || ( u8d.first >= 0xA0
816 && u8d.first <= 0xD7FF)
817 || ( u8d.first >= 0xE000
818 && u8d.first <= 0xFFFD)
819 || ( u8d.first >= 0x10000
820 && u8d.first <= 0x10FFFF)))
821 return Position + u8d.second;
826 StringRef::iterator Scanner::skip_b_break(StringRef::iterator Position) {
829 if (*Position == 0x0D) {
830 if (Position + 1 != End && *(Position + 1) == 0x0A)
835 if (*Position == 0x0A)
840 StringRef::iterator Scanner::skip_s_space(StringRef::iterator Position) {
843 if (*Position == ' ')
848 StringRef::iterator Scanner::skip_s_white(StringRef::iterator Position) {
851 if (*Position == ' ' || *Position == '\t')
856 StringRef::iterator Scanner::skip_ns_char(StringRef::iterator Position) {
859 if (*Position == ' ' || *Position == '\t')
861 return skip_nb_char(Position);
864 StringRef::iterator Scanner::skip_while( SkipWhileFunc Func
865 , StringRef::iterator Position) {
867 StringRef::iterator i = (this->*Func)(Position);
875 void Scanner::advanceWhile(SkipWhileFunc Func) {
876 auto Final = skip_while(Func, Current);
877 Column += Final - Current;
881 static bool is_ns_hex_digit(const char C) {
882 return (C >= '0' && C <= '9')
883 || (C >= 'a' && C <= 'z')
884 || (C >= 'A' && C <= 'Z');
887 static bool is_ns_word_char(const char C) {
889 || (C >= 'a' && C <= 'z')
890 || (C >= 'A' && C <= 'Z');
893 void Scanner::scan_ns_uri_char() {
897 if (( *Current == '%'
899 && is_ns_hex_digit(*(Current + 1))
900 && is_ns_hex_digit(*(Current + 2)))
901 || is_ns_word_char(*Current)
902 || StringRef(Current, 1).find_first_of("#;/?:@&=+$,_.!~*'()[]")
903 != StringRef::npos) {
911 bool Scanner::consume(uint32_t Expected) {
912 if (Expected >= 0x80)
913 report_fatal_error("Not dealing with this yet");
916 if (uint8_t(*Current) >= 0x80)
917 report_fatal_error("Not dealing with this yet");
918 if (uint8_t(*Current) == Expected) {
926 void Scanner::skip(uint32_t Distance) {
929 assert(Current <= End && "Skipped past the end");
932 bool Scanner::isBlankOrBreak(StringRef::iterator Position) {
935 return *Position == ' ' || *Position == '\t' || *Position == '\r' ||
939 bool Scanner::consumeLineBreakIfPresent() {
940 auto Next = skip_b_break(Current);
949 void Scanner::saveSimpleKeyCandidate( TokenQueueT::iterator Tok
952 if (IsSimpleKeyAllowed) {
956 SK.Column = AtColumn;
957 SK.IsRequired = IsRequired;
958 SK.FlowLevel = FlowLevel;
959 SimpleKeys.push_back(SK);
963 void Scanner::removeStaleSimpleKeyCandidates() {
964 for (SmallVectorImpl<SimpleKey>::iterator i = SimpleKeys.begin();
965 i != SimpleKeys.end();) {
966 if (i->Line != Line || i->Column + 1024 < Column) {
968 setError( "Could not find expected : for simple key"
969 , i->Tok->Range.begin());
970 i = SimpleKeys.erase(i);
976 void Scanner::removeSimpleKeyCandidatesOnFlowLevel(unsigned Level) {
977 if (!SimpleKeys.empty() && (SimpleKeys.end() - 1)->FlowLevel == Level)
978 SimpleKeys.pop_back();
981 bool Scanner::unrollIndent(int ToColumn) {
983 // Indentation is ignored in flow.
987 while (Indent > ToColumn) {
988 T.Kind = Token::TK_BlockEnd;
989 T.Range = StringRef(Current, 1);
990 TokenQueue.push_back(T);
991 Indent = Indents.pop_back_val();
997 bool Scanner::rollIndent( int ToColumn
998 , Token::TokenKind Kind
999 , TokenQueueT::iterator InsertPoint) {
1002 if (Indent < ToColumn) {
1003 Indents.push_back(Indent);
1008 T.Range = StringRef(Current, 0);
1009 TokenQueue.insert(InsertPoint, T);
1014 void Scanner::skipComment() {
1015 if (*Current != '#')
1018 // This may skip more than one byte, thus Column is only incremented
1020 StringRef::iterator I = skip_nb_char(Current);
1028 void Scanner::scanToNextToken() {
1030 while (*Current == ' ' || *Current == '\t') {
1037 StringRef::iterator i = skip_b_break(Current);
1043 // New lines may start a simple key.
1045 IsSimpleKeyAllowed = true;
1049 bool Scanner::scanStreamStart() {
1050 IsStartOfStream = false;
1052 EncodingInfo EI = getUnicodeEncoding(currentInput());
1055 T.Kind = Token::TK_StreamStart;
1056 T.Range = StringRef(Current, EI.second);
1057 TokenQueue.push_back(T);
1058 Current += EI.second;
1062 bool Scanner::scanStreamEnd() {
1063 // Force an ending new line if one isn't present.
1071 IsSimpleKeyAllowed = false;
1074 T.Kind = Token::TK_StreamEnd;
1075 T.Range = StringRef(Current, 0);
1076 TokenQueue.push_back(T);
1080 bool Scanner::scanDirective() {
1081 // Reset the indentation level.
1084 IsSimpleKeyAllowed = false;
1086 StringRef::iterator Start = Current;
1088 StringRef::iterator NameStart = Current;
1089 Current = skip_while(&Scanner::skip_ns_char, Current);
1090 StringRef Name(NameStart, Current - NameStart);
1091 Current = skip_while(&Scanner::skip_s_white, Current);
1094 if (Name == "YAML") {
1095 Current = skip_while(&Scanner::skip_ns_char, Current);
1096 T.Kind = Token::TK_VersionDirective;
1097 T.Range = StringRef(Start, Current - Start);
1098 TokenQueue.push_back(T);
1100 } else if(Name == "TAG") {
1101 Current = skip_while(&Scanner::skip_ns_char, Current);
1102 Current = skip_while(&Scanner::skip_s_white, Current);
1103 Current = skip_while(&Scanner::skip_ns_char, Current);
1104 T.Kind = Token::TK_TagDirective;
1105 T.Range = StringRef(Start, Current - Start);
1106 TokenQueue.push_back(T);
1112 bool Scanner::scanDocumentIndicator(bool IsStart) {
1115 IsSimpleKeyAllowed = false;
1118 T.Kind = IsStart ? Token::TK_DocumentStart : Token::TK_DocumentEnd;
1119 T.Range = StringRef(Current, 3);
1121 TokenQueue.push_back(T);
1125 bool Scanner::scanFlowCollectionStart(bool IsSequence) {
1127 T.Kind = IsSequence ? Token::TK_FlowSequenceStart
1128 : Token::TK_FlowMappingStart;
1129 T.Range = StringRef(Current, 1);
1131 TokenQueue.push_back(T);
1133 // [ and { may begin a simple key.
1134 saveSimpleKeyCandidate(--TokenQueue.end(), Column - 1, false);
1136 // And may also be followed by a simple key.
1137 IsSimpleKeyAllowed = true;
1142 bool Scanner::scanFlowCollectionEnd(bool IsSequence) {
1143 removeSimpleKeyCandidatesOnFlowLevel(FlowLevel);
1144 IsSimpleKeyAllowed = false;
1146 T.Kind = IsSequence ? Token::TK_FlowSequenceEnd
1147 : Token::TK_FlowMappingEnd;
1148 T.Range = StringRef(Current, 1);
1150 TokenQueue.push_back(T);
1156 bool Scanner::scanFlowEntry() {
1157 removeSimpleKeyCandidatesOnFlowLevel(FlowLevel);
1158 IsSimpleKeyAllowed = true;
1160 T.Kind = Token::TK_FlowEntry;
1161 T.Range = StringRef(Current, 1);
1163 TokenQueue.push_back(T);
1167 bool Scanner::scanBlockEntry() {
1168 rollIndent(Column, Token::TK_BlockSequenceStart, TokenQueue.end());
1169 removeSimpleKeyCandidatesOnFlowLevel(FlowLevel);
1170 IsSimpleKeyAllowed = true;
1172 T.Kind = Token::TK_BlockEntry;
1173 T.Range = StringRef(Current, 1);
1175 TokenQueue.push_back(T);
1179 bool Scanner::scanKey() {
1181 rollIndent(Column, Token::TK_BlockMappingStart, TokenQueue.end());
1183 removeSimpleKeyCandidatesOnFlowLevel(FlowLevel);
1184 IsSimpleKeyAllowed = !FlowLevel;
1187 T.Kind = Token::TK_Key;
1188 T.Range = StringRef(Current, 1);
1190 TokenQueue.push_back(T);
1194 bool Scanner::scanValue() {
1195 // If the previous token could have been a simple key, insert the key token
1196 // into the token queue.
1197 if (!SimpleKeys.empty()) {
1198 SimpleKey SK = SimpleKeys.pop_back_val();
1200 T.Kind = Token::TK_Key;
1201 T.Range = SK.Tok->Range;
1202 TokenQueueT::iterator i, e;
1203 for (i = TokenQueue.begin(), e = TokenQueue.end(); i != e; ++i) {
1207 assert(i != e && "SimpleKey not in token queue!");
1208 i = TokenQueue.insert(i, T);
1210 // We may also need to add a Block-Mapping-Start token.
1211 rollIndent(SK.Column, Token::TK_BlockMappingStart, i);
1213 IsSimpleKeyAllowed = false;
1216 rollIndent(Column, Token::TK_BlockMappingStart, TokenQueue.end());
1217 IsSimpleKeyAllowed = !FlowLevel;
1221 T.Kind = Token::TK_Value;
1222 T.Range = StringRef(Current, 1);
1224 TokenQueue.push_back(T);
1228 // Forbidding inlining improves performance by roughly 20%.
1229 // FIXME: Remove once llvm optimizes this to the faster version without hints.
1230 LLVM_ATTRIBUTE_NOINLINE static bool
1231 wasEscaped(StringRef::iterator First, StringRef::iterator Position);
1233 // Returns whether a character at 'Position' was escaped with a leading '\'.
1234 // 'First' specifies the position of the first character in the string.
1235 static bool wasEscaped(StringRef::iterator First,
1236 StringRef::iterator Position) {
1237 assert(Position - 1 >= First);
1238 StringRef::iterator I = Position - 1;
1239 // We calculate the number of consecutive '\'s before the current position
1240 // by iterating backwards through our string.
1241 while (I >= First && *I == '\\') --I;
1242 // (Position - 1 - I) now contains the number of '\'s before the current
1243 // position. If it is odd, the character at 'Position' was escaped.
1244 return (Position - 1 - I) % 2 == 1;
1247 bool Scanner::scanFlowScalar(bool IsDoubleQuoted) {
1248 StringRef::iterator Start = Current;
1249 unsigned ColStart = Column;
1250 if (IsDoubleQuoted) {
1253 while (Current != End && *Current != '"')
1255 // Repeat until the previous character was not a '\' or was an escaped
1257 } while ( Current != End
1258 && *(Current - 1) == '\\'
1259 && wasEscaped(Start + 1, Current));
1263 // Skip a ' followed by another '.
1264 if (Current + 1 < End && *Current == '\'' && *(Current + 1) == '\'') {
1267 } else if (*Current == '\'')
1269 StringRef::iterator i = skip_nb_char(Current);
1271 i = skip_b_break(Current);
1286 if (Current == End) {
1287 setError("Expected quote at end of scalar", Current);
1291 skip(1); // Skip ending quote.
1293 T.Kind = Token::TK_Scalar;
1294 T.Range = StringRef(Start, Current - Start);
1295 TokenQueue.push_back(T);
1297 saveSimpleKeyCandidate(--TokenQueue.end(), ColStart, false);
1299 IsSimpleKeyAllowed = false;
1304 bool Scanner::scanPlainScalar() {
1305 StringRef::iterator Start = Current;
1306 unsigned ColStart = Column;
1307 unsigned LeadingBlanks = 0;
1308 assert(Indent >= -1 && "Indent must be >= -1 !");
1309 unsigned indent = static_cast<unsigned>(Indent + 1);
1311 if (*Current == '#')
1314 while (!isBlankOrBreak(Current)) {
1315 if ( FlowLevel && *Current == ':'
1316 && !(isBlankOrBreak(Current + 1) || *(Current + 1) == ',')) {
1317 setError("Found unexpected ':' while scanning a plain scalar", Current);
1321 // Check for the end of the plain scalar.
1322 if ( (*Current == ':' && isBlankOrBreak(Current + 1))
1324 && (StringRef(Current, 1).find_first_of(",:?[]{}")
1325 != StringRef::npos)))
1328 StringRef::iterator i = skip_nb_char(Current);
1335 // Are we at the end?
1336 if (!isBlankOrBreak(Current))
1340 StringRef::iterator Tmp = Current;
1341 while (isBlankOrBreak(Tmp)) {
1342 StringRef::iterator i = skip_s_white(Tmp);
1344 if (LeadingBlanks && (Column < indent) && *Tmp == '\t') {
1345 setError("Found invalid tab character in indentation", Tmp);
1351 i = skip_b_break(Tmp);
1360 if (!FlowLevel && Column < indent)
1365 if (Start == Current) {
1366 setError("Got empty plain scalar", Start);
1370 T.Kind = Token::TK_Scalar;
1371 T.Range = StringRef(Start, Current - Start);
1372 TokenQueue.push_back(T);
1374 // Plain scalars can be simple keys.
1375 saveSimpleKeyCandidate(--TokenQueue.end(), ColStart, false);
1377 IsSimpleKeyAllowed = false;
1382 bool Scanner::scanAliasOrAnchor(bool IsAlias) {
1383 StringRef::iterator Start = Current;
1384 unsigned ColStart = Column;
1387 if ( *Current == '[' || *Current == ']'
1388 || *Current == '{' || *Current == '}'
1392 StringRef::iterator i = skip_ns_char(Current);
1399 if (Start == Current) {
1400 setError("Got empty alias or anchor", Start);
1405 T.Kind = IsAlias ? Token::TK_Alias : Token::TK_Anchor;
1406 T.Range = StringRef(Start, Current - Start);
1407 TokenQueue.push_back(T);
1409 // Alias and anchors can be simple keys.
1410 saveSimpleKeyCandidate(--TokenQueue.end(), ColStart, false);
1412 IsSimpleKeyAllowed = false;
1417 char Scanner::scanBlockChompingIndicator() {
1418 char Indicator = ' ';
1419 if (Current != End && (*Current == '+' || *Current == '-')) {
1420 Indicator = *Current;
1426 /// Get the number of line breaks after chomping.
1428 /// Return the number of trailing line breaks to emit, depending on
1429 /// \p ChompingIndicator.
1430 static unsigned getChompedLineBreaks(char ChompingIndicator,
1431 unsigned LineBreaks, StringRef Str) {
1432 if (ChompingIndicator == '-') // Strip all line breaks.
1434 if (ChompingIndicator == '+') // Keep all line breaks.
1436 // Clip trailing lines.
1437 return Str.empty() ? 0 : 1;
1440 unsigned Scanner::scanBlockIndentationIndicator() {
1441 unsigned Indent = 0;
1442 if (Current != End && (*Current >= '1' && *Current <= '9')) {
1443 Indent = unsigned(*Current - '0');
1449 bool Scanner::scanBlockScalarHeader(char &ChompingIndicator,
1450 unsigned &IndentIndicator, bool &IsDone) {
1451 auto Start = Current;
1453 ChompingIndicator = scanBlockChompingIndicator();
1454 IndentIndicator = scanBlockIndentationIndicator();
1455 // Check for the chomping indicator once again.
1456 if (ChompingIndicator == ' ')
1457 ChompingIndicator = scanBlockChompingIndicator();
1458 Current = skip_while(&Scanner::skip_s_white, Current);
1461 if (Current == End) { // EOF, we have an empty scalar.
1463 T.Kind = Token::TK_BlockScalar;
1464 T.Range = StringRef(Start, Current - Start);
1465 TokenQueue.push_back(T);
1470 if (!consumeLineBreakIfPresent()) {
1471 setError("Expected a line break after block scalar header", Current);
1477 bool Scanner::findBlockScalarIndent(unsigned &BlockIndent,
1478 unsigned BlockExitIndent,
1479 unsigned &LineBreaks, bool &IsDone) {
1480 unsigned MaxAllSpaceLineCharacters = 0;
1481 StringRef::iterator LongestAllSpaceLine;
1484 advanceWhile(&Scanner::skip_s_space);
1485 if (skip_nb_char(Current) != Current) {
1486 // This line isn't empty, so try and find the indentation.
1487 if (Column <= BlockExitIndent) { // End of the block literal.
1491 // We found the block's indentation.
1492 BlockIndent = Column;
1493 if (MaxAllSpaceLineCharacters > BlockIndent) {
1495 "Leading all-spaces line must be smaller than the block indent",
1496 LongestAllSpaceLine);
1501 if (skip_b_break(Current) != Current &&
1502 Column > MaxAllSpaceLineCharacters) {
1503 // Record the longest all-space line in case it's longer than the
1504 // discovered block indent.
1505 MaxAllSpaceLineCharacters = Column;
1506 LongestAllSpaceLine = Current;
1510 if (Current == End) {
1515 if (!consumeLineBreakIfPresent()) {
1524 bool Scanner::scanBlockScalarIndent(unsigned BlockIndent,
1525 unsigned BlockExitIndent, bool &IsDone) {
1526 // Skip the indentation.
1527 while (Column < BlockIndent) {
1528 auto I = skip_s_space(Current);
1535 if (skip_nb_char(Current) == Current)
1538 if (Column <= BlockExitIndent) { // End of the block literal.
1543 if (Column < BlockIndent) {
1544 if (Current != End && *Current == '#') { // Trailing comment.
1548 setError("A text line is less indented than the block scalar", Current);
1551 return true; // A normal text line.
1554 bool Scanner::scanBlockScalar(bool IsLiteral) {
1556 assert(*Current == '|' || *Current == '>');
1559 char ChompingIndicator;
1560 unsigned BlockIndent;
1561 bool IsDone = false;
1562 if (!scanBlockScalarHeader(ChompingIndicator, BlockIndent, IsDone))
1567 auto Start = Current;
1568 unsigned BlockExitIndent = Indent < 0 ? 0 : (unsigned)Indent;
1569 unsigned LineBreaks = 0;
1570 if (BlockIndent == 0) {
1571 if (!findBlockScalarIndent(BlockIndent, BlockExitIndent, LineBreaks,
1576 // Scan the block's scalars body.
1577 SmallString<256> Str;
1579 if (!scanBlockScalarIndent(BlockIndent, BlockExitIndent, IsDone))
1584 // Parse the current line.
1585 auto LineStart = Current;
1586 advanceWhile(&Scanner::skip_nb_char);
1587 if (LineStart != Current) {
1588 Str.append(LineBreaks, '\n');
1589 Str.append(StringRef(LineStart, Current - LineStart));
1597 if (!consumeLineBreakIfPresent())
1602 if (Current == End && !LineBreaks)
1603 // Ensure that there is at least one line break before the end of file.
1605 Str.append(getChompedLineBreaks(ChompingIndicator, LineBreaks, Str), '\n');
1607 // New lines may start a simple key.
1609 IsSimpleKeyAllowed = true;
1612 T.Kind = Token::TK_BlockScalar;
1613 T.Range = StringRef(Start, Current - Start);
1614 T.Value = Str.str().str();
1615 TokenQueue.push_back(T);
1619 bool Scanner::scanTag() {
1620 StringRef::iterator Start = Current;
1621 unsigned ColStart = Column;
1623 if (Current == End || isBlankOrBreak(Current)); // An empty tag.
1624 else if (*Current == '<') {
1630 // FIXME: Actually parse the c-ns-shorthand-tag rule.
1631 Current = skip_while(&Scanner::skip_ns_char, Current);
1635 T.Kind = Token::TK_Tag;
1636 T.Range = StringRef(Start, Current - Start);
1637 TokenQueue.push_back(T);
1639 // Tags can be simple keys.
1640 saveSimpleKeyCandidate(--TokenQueue.end(), ColStart, false);
1642 IsSimpleKeyAllowed = false;
1647 bool Scanner::fetchMoreTokens() {
1648 if (IsStartOfStream)
1649 return scanStreamStart();
1654 return scanStreamEnd();
1656 removeStaleSimpleKeyCandidates();
1658 unrollIndent(Column);
1660 if (Column == 0 && *Current == '%')
1661 return scanDirective();
1663 if (Column == 0 && Current + 4 <= End
1665 && *(Current + 1) == '-'
1666 && *(Current + 2) == '-'
1667 && (Current + 3 == End || isBlankOrBreak(Current + 3)))
1668 return scanDocumentIndicator(true);
1670 if (Column == 0 && Current + 4 <= End
1672 && *(Current + 1) == '.'
1673 && *(Current + 2) == '.'
1674 && (Current + 3 == End || isBlankOrBreak(Current + 3)))
1675 return scanDocumentIndicator(false);
1677 if (*Current == '[')
1678 return scanFlowCollectionStart(true);
1680 if (*Current == '{')
1681 return scanFlowCollectionStart(false);
1683 if (*Current == ']')
1684 return scanFlowCollectionEnd(true);
1686 if (*Current == '}')
1687 return scanFlowCollectionEnd(false);
1689 if (*Current == ',')
1690 return scanFlowEntry();
1692 if (*Current == '-' && isBlankOrBreak(Current + 1))
1693 return scanBlockEntry();
1695 if (*Current == '?' && (FlowLevel || isBlankOrBreak(Current + 1)))
1698 if (*Current == ':' && (FlowLevel || isBlankOrBreak(Current + 1)))
1701 if (*Current == '*')
1702 return scanAliasOrAnchor(true);
1704 if (*Current == '&')
1705 return scanAliasOrAnchor(false);
1707 if (*Current == '!')
1710 if (*Current == '|' && !FlowLevel)
1711 return scanBlockScalar(true);
1713 if (*Current == '>' && !FlowLevel)
1714 return scanBlockScalar(false);
1716 if (*Current == '\'')
1717 return scanFlowScalar(false);
1719 if (*Current == '"')
1720 return scanFlowScalar(true);
1722 // Get a plain scalar.
1723 StringRef FirstChar(Current, 1);
1724 if (!(isBlankOrBreak(Current)
1725 || FirstChar.find_first_of("-?:,[]{}#&*!|>'\"%@`") != StringRef::npos)
1726 || (*Current == '-' && !isBlankOrBreak(Current + 1))
1727 || (!FlowLevel && (*Current == '?' || *Current == ':')
1728 && isBlankOrBreak(Current + 1))
1729 || (!FlowLevel && *Current == ':'
1730 && Current + 2 < End
1731 && *(Current + 1) == ':'
1732 && !isBlankOrBreak(Current + 2)))
1733 return scanPlainScalar();
1735 setError("Unrecognized character while tokenizing.");
1739 Stream::Stream(StringRef Input, SourceMgr &SM, bool ShowColors,
1740 std::error_code *EC)
1741 : scanner(new Scanner(Input, SM, ShowColors, EC)), CurrentDoc() {}
1743 Stream::Stream(MemoryBufferRef InputBuffer, SourceMgr &SM, bool ShowColors,
1744 std::error_code *EC)
1745 : scanner(new Scanner(InputBuffer, SM, ShowColors, EC)), CurrentDoc() {}
1747 Stream::~Stream() {}
1749 bool Stream::failed() { return scanner->failed(); }
1751 void Stream::printError(Node *N, const Twine &Msg) {
1752 scanner->printError( N->getSourceRange().Start
1753 , SourceMgr::DK_Error
1755 , N->getSourceRange());
1758 document_iterator Stream::begin() {
1760 report_fatal_error("Can only iterate over the stream once");
1762 // Skip Stream-Start.
1765 CurrentDoc.reset(new Document(*this));
1766 return document_iterator(CurrentDoc);
1769 document_iterator Stream::end() {
1770 return document_iterator();
1773 void Stream::skip() {
1774 for (document_iterator i = begin(), e = end(); i != e; ++i)
1778 Node::Node(unsigned int Type, std::unique_ptr<Document> &D, StringRef A,
1780 : Doc(D), TypeID(Type), Anchor(A), Tag(T) {
1781 SMLoc Start = SMLoc::getFromPointer(peekNext().Range.begin());
1782 SourceRange = SMRange(Start, Start);
1785 std::string Node::getVerbatimTag() const {
1786 StringRef Raw = getRawTag();
1787 if (!Raw.empty() && Raw != "!") {
1789 if (Raw.find_last_of('!') == 0) {
1790 Ret = Doc->getTagMap().find("!")->second;
1791 Ret += Raw.substr(1);
1793 } else if (Raw.startswith("!!")) {
1794 Ret = Doc->getTagMap().find("!!")->second;
1795 Ret += Raw.substr(2);
1798 StringRef TagHandle = Raw.substr(0, Raw.find_last_of('!') + 1);
1799 std::map<StringRef, StringRef>::const_iterator It =
1800 Doc->getTagMap().find(TagHandle);
1801 if (It != Doc->getTagMap().end())
1805 T.Kind = Token::TK_Tag;
1806 T.Range = TagHandle;
1807 setError(Twine("Unknown tag handle ") + TagHandle, T);
1809 Ret += Raw.substr(Raw.find_last_of('!') + 1);
1814 switch (getType()) {
1816 return "tag:yaml.org,2002:null";
1818 case NK_BlockScalar:
1819 // TODO: Tag resolution.
1820 return "tag:yaml.org,2002:str";
1822 return "tag:yaml.org,2002:map";
1824 return "tag:yaml.org,2002:seq";
1830 Token &Node::peekNext() {
1831 return Doc->peekNext();
1834 Token Node::getNext() {
1835 return Doc->getNext();
1838 Node *Node::parseBlockNode() {
1839 return Doc->parseBlockNode();
1842 BumpPtrAllocator &Node::getAllocator() {
1843 return Doc->NodeAllocator;
1846 void Node::setError(const Twine &Msg, Token &Tok) const {
1847 Doc->setError(Msg, Tok);
1850 bool Node::failed() const {
1851 return Doc->failed();
1856 StringRef ScalarNode::getValue(SmallVectorImpl<char> &Storage) const {
1857 // TODO: Handle newlines properly. We need to remove leading whitespace.
1858 if (Value[0] == '"') { // Double quoted.
1859 // Pull off the leading and trailing "s.
1860 StringRef UnquotedValue = Value.substr(1, Value.size() - 2);
1861 // Search for characters that would require unescaping the value.
1862 StringRef::size_type i = UnquotedValue.find_first_of("\\\r\n");
1863 if (i != StringRef::npos)
1864 return unescapeDoubleQuoted(UnquotedValue, i, Storage);
1865 return UnquotedValue;
1866 } else if (Value[0] == '\'') { // Single quoted.
1867 // Pull off the leading and trailing 's.
1868 StringRef UnquotedValue = Value.substr(1, Value.size() - 2);
1869 StringRef::size_type i = UnquotedValue.find('\'');
1870 if (i != StringRef::npos) {
1871 // We're going to need Storage.
1873 Storage.reserve(UnquotedValue.size());
1874 for (; i != StringRef::npos; i = UnquotedValue.find('\'')) {
1875 StringRef Valid(UnquotedValue.begin(), i);
1876 Storage.insert(Storage.end(), Valid.begin(), Valid.end());
1877 Storage.push_back('\'');
1878 UnquotedValue = UnquotedValue.substr(i + 2);
1880 Storage.insert(Storage.end(), UnquotedValue.begin(), UnquotedValue.end());
1881 return StringRef(Storage.begin(), Storage.size());
1883 return UnquotedValue;
1886 return Value.rtrim(' ');
1889 StringRef ScalarNode::unescapeDoubleQuoted( StringRef UnquotedValue
1890 , StringRef::size_type i
1891 , SmallVectorImpl<char> &Storage)
1893 // Use Storage to build proper value.
1895 Storage.reserve(UnquotedValue.size());
1896 for (; i != StringRef::npos; i = UnquotedValue.find_first_of("\\\r\n")) {
1897 // Insert all previous chars into Storage.
1898 StringRef Valid(UnquotedValue.begin(), i);
1899 Storage.insert(Storage.end(), Valid.begin(), Valid.end());
1900 // Chop off inserted chars.
1901 UnquotedValue = UnquotedValue.substr(i);
1903 assert(!UnquotedValue.empty() && "Can't be empty!");
1905 // Parse escape or line break.
1906 switch (UnquotedValue[0]) {
1909 Storage.push_back('\n');
1910 if ( UnquotedValue.size() > 1
1911 && (UnquotedValue[1] == '\r' || UnquotedValue[1] == '\n'))
1912 UnquotedValue = UnquotedValue.substr(1);
1913 UnquotedValue = UnquotedValue.substr(1);
1916 if (UnquotedValue.size() == 1)
1917 // TODO: Report error.
1919 UnquotedValue = UnquotedValue.substr(1);
1920 switch (UnquotedValue[0]) {
1923 T.Range = StringRef(UnquotedValue.begin(), 1);
1924 setError("Unrecognized escape code!", T);
1929 // Remove the new line.
1930 if ( UnquotedValue.size() > 1
1931 && (UnquotedValue[1] == '\r' || UnquotedValue[1] == '\n'))
1932 UnquotedValue = UnquotedValue.substr(1);
1933 // If this was just a single byte newline, it will get skipped
1937 Storage.push_back(0x00);
1940 Storage.push_back(0x07);
1943 Storage.push_back(0x08);
1947 Storage.push_back(0x09);
1950 Storage.push_back(0x0A);
1953 Storage.push_back(0x0B);
1956 Storage.push_back(0x0C);
1959 Storage.push_back(0x0D);
1962 Storage.push_back(0x1B);
1965 Storage.push_back(0x20);
1968 Storage.push_back(0x22);
1971 Storage.push_back(0x2F);
1974 Storage.push_back(0x5C);
1977 encodeUTF8(0x85, Storage);
1980 encodeUTF8(0xA0, Storage);
1983 encodeUTF8(0x2028, Storage);
1986 encodeUTF8(0x2029, Storage);
1989 if (UnquotedValue.size() < 3)
1990 // TODO: Report error.
1992 unsigned int UnicodeScalarValue;
1993 if (UnquotedValue.substr(1, 2).getAsInteger(16, UnicodeScalarValue))
1994 // TODO: Report error.
1995 UnicodeScalarValue = 0xFFFD;
1996 encodeUTF8(UnicodeScalarValue, Storage);
1997 UnquotedValue = UnquotedValue.substr(2);
2001 if (UnquotedValue.size() < 5)
2002 // TODO: Report error.
2004 unsigned int UnicodeScalarValue;
2005 if (UnquotedValue.substr(1, 4).getAsInteger(16, UnicodeScalarValue))
2006 // TODO: Report error.
2007 UnicodeScalarValue = 0xFFFD;
2008 encodeUTF8(UnicodeScalarValue, Storage);
2009 UnquotedValue = UnquotedValue.substr(4);
2013 if (UnquotedValue.size() < 9)
2014 // TODO: Report error.
2016 unsigned int UnicodeScalarValue;
2017 if (UnquotedValue.substr(1, 8).getAsInteger(16, UnicodeScalarValue))
2018 // TODO: Report error.
2019 UnicodeScalarValue = 0xFFFD;
2020 encodeUTF8(UnicodeScalarValue, Storage);
2021 UnquotedValue = UnquotedValue.substr(8);
2025 UnquotedValue = UnquotedValue.substr(1);
2028 Storage.insert(Storage.end(), UnquotedValue.begin(), UnquotedValue.end());
2029 return StringRef(Storage.begin(), Storage.size());
2032 Node *KeyValueNode::getKey() {
2035 // Handle implicit null keys.
2037 Token &t = peekNext();
2038 if ( t.Kind == Token::TK_BlockEnd
2039 || t.Kind == Token::TK_Value
2040 || t.Kind == Token::TK_Error) {
2041 return Key = new (getAllocator()) NullNode(Doc);
2043 if (t.Kind == Token::TK_Key)
2044 getNext(); // skip TK_Key.
2047 // Handle explicit null keys.
2048 Token &t = peekNext();
2049 if (t.Kind == Token::TK_BlockEnd || t.Kind == Token::TK_Value) {
2050 return Key = new (getAllocator()) NullNode(Doc);
2053 // We've got a normal key.
2054 return Key = parseBlockNode();
2057 Node *KeyValueNode::getValue() {
2062 return Value = new (getAllocator()) NullNode(Doc);
2064 // Handle implicit null values.
2066 Token &t = peekNext();
2067 if ( t.Kind == Token::TK_BlockEnd
2068 || t.Kind == Token::TK_FlowMappingEnd
2069 || t.Kind == Token::TK_Key
2070 || t.Kind == Token::TK_FlowEntry
2071 || t.Kind == Token::TK_Error) {
2072 return Value = new (getAllocator()) NullNode(Doc);
2075 if (t.Kind != Token::TK_Value) {
2076 setError("Unexpected token in Key Value.", t);
2077 return Value = new (getAllocator()) NullNode(Doc);
2079 getNext(); // skip TK_Value.
2082 // Handle explicit null values.
2083 Token &t = peekNext();
2084 if (t.Kind == Token::TK_BlockEnd || t.Kind == Token::TK_Key) {
2085 return Value = new (getAllocator()) NullNode(Doc);
2088 // We got a normal value.
2089 return Value = parseBlockNode();
2092 void MappingNode::increment() {
2095 CurrentEntry = nullptr;
2099 CurrentEntry->skip();
2100 if (Type == MT_Inline) {
2102 CurrentEntry = nullptr;
2106 Token T = peekNext();
2107 if (T.Kind == Token::TK_Key || T.Kind == Token::TK_Scalar) {
2108 // KeyValueNode eats the TK_Key. That way it can detect null keys.
2109 CurrentEntry = new (getAllocator()) KeyValueNode(Doc);
2110 } else if (Type == MT_Block) {
2112 case Token::TK_BlockEnd:
2115 CurrentEntry = nullptr;
2118 setError("Unexpected token. Expected Key or Block End", T);
2120 case Token::TK_Error:
2122 CurrentEntry = nullptr;
2126 case Token::TK_FlowEntry:
2127 // Eat the flow entry and recurse.
2130 case Token::TK_FlowMappingEnd:
2133 case Token::TK_Error:
2134 // Set this to end iterator.
2136 CurrentEntry = nullptr;
2139 setError( "Unexpected token. Expected Key, Flow Entry, or Flow "
2143 CurrentEntry = nullptr;
2148 void SequenceNode::increment() {
2151 CurrentEntry = nullptr;
2155 CurrentEntry->skip();
2156 Token T = peekNext();
2157 if (SeqType == ST_Block) {
2159 case Token::TK_BlockEntry:
2161 CurrentEntry = parseBlockNode();
2162 if (!CurrentEntry) { // An error occurred.
2164 CurrentEntry = nullptr;
2167 case Token::TK_BlockEnd:
2170 CurrentEntry = nullptr;
2173 setError( "Unexpected token. Expected Block Entry or Block End."
2176 case Token::TK_Error:
2178 CurrentEntry = nullptr;
2180 } else if (SeqType == ST_Indentless) {
2182 case Token::TK_BlockEntry:
2184 CurrentEntry = parseBlockNode();
2185 if (!CurrentEntry) { // An error occurred.
2187 CurrentEntry = nullptr;
2191 case Token::TK_Error:
2193 CurrentEntry = nullptr;
2195 } else if (SeqType == ST_Flow) {
2197 case Token::TK_FlowEntry:
2198 // Eat the flow entry and recurse.
2200 WasPreviousTokenFlowEntry = true;
2202 case Token::TK_FlowSequenceEnd:
2205 case Token::TK_Error:
2206 // Set this to end iterator.
2208 CurrentEntry = nullptr;
2210 case Token::TK_StreamEnd:
2211 case Token::TK_DocumentEnd:
2212 case Token::TK_DocumentStart:
2213 setError("Could not find closing ]!", T);
2214 // Set this to end iterator.
2216 CurrentEntry = nullptr;
2219 if (!WasPreviousTokenFlowEntry) {
2220 setError("Expected , between entries!", T);
2222 CurrentEntry = nullptr;
2225 // Otherwise it must be a flow entry.
2226 CurrentEntry = parseBlockNode();
2227 if (!CurrentEntry) {
2230 WasPreviousTokenFlowEntry = false;
2236 Document::Document(Stream &S) : stream(S), Root(nullptr) {
2237 // Tag maps starts with two default mappings.
2239 TagMap["!!"] = "tag:yaml.org,2002:";
2241 if (parseDirectives())
2242 expectToken(Token::TK_DocumentStart);
2243 Token &T = peekNext();
2244 if (T.Kind == Token::TK_DocumentStart)
2248 bool Document::skip() {
2249 if (stream.scanner->failed())
2254 Token &T = peekNext();
2255 if (T.Kind == Token::TK_StreamEnd)
2257 if (T.Kind == Token::TK_DocumentEnd) {
2264 Token &Document::peekNext() {
2265 return stream.scanner->peekNext();
2268 Token Document::getNext() {
2269 return stream.scanner->getNext();
2272 void Document::setError(const Twine &Message, Token &Location) const {
2273 stream.scanner->setError(Message, Location.Range.begin());
2276 bool Document::failed() const {
2277 return stream.scanner->failed();
2280 Node *Document::parseBlockNode() {
2281 Token T = peekNext();
2282 // Handle properties.
2287 case Token::TK_Alias:
2289 return new (NodeAllocator) AliasNode(stream.CurrentDoc, T.Range.substr(1));
2290 case Token::TK_Anchor:
2291 if (AnchorInfo.Kind == Token::TK_Anchor) {
2292 setError("Already encountered an anchor for this node!", T);
2295 AnchorInfo = getNext(); // Consume TK_Anchor.
2297 goto parse_property;
2299 if (TagInfo.Kind == Token::TK_Tag) {
2300 setError("Already encountered a tag for this node!", T);
2303 TagInfo = getNext(); // Consume TK_Tag.
2305 goto parse_property;
2311 case Token::TK_BlockEntry:
2312 // We got an unindented BlockEntry sequence. This is not terminated with
2314 // Don't eat the TK_BlockEntry, SequenceNode needs it.
2315 return new (NodeAllocator) SequenceNode( stream.CurrentDoc
2316 , AnchorInfo.Range.substr(1)
2318 , SequenceNode::ST_Indentless);
2319 case Token::TK_BlockSequenceStart:
2321 return new (NodeAllocator)
2322 SequenceNode( stream.CurrentDoc
2323 , AnchorInfo.Range.substr(1)
2325 , SequenceNode::ST_Block);
2326 case Token::TK_BlockMappingStart:
2328 return new (NodeAllocator)
2329 MappingNode( stream.CurrentDoc
2330 , AnchorInfo.Range.substr(1)
2332 , MappingNode::MT_Block);
2333 case Token::TK_FlowSequenceStart:
2335 return new (NodeAllocator)
2336 SequenceNode( stream.CurrentDoc
2337 , AnchorInfo.Range.substr(1)
2339 , SequenceNode::ST_Flow);
2340 case Token::TK_FlowMappingStart:
2342 return new (NodeAllocator)
2343 MappingNode( stream.CurrentDoc
2344 , AnchorInfo.Range.substr(1)
2346 , MappingNode::MT_Flow);
2347 case Token::TK_Scalar:
2349 return new (NodeAllocator)
2350 ScalarNode( stream.CurrentDoc
2351 , AnchorInfo.Range.substr(1)
2354 case Token::TK_BlockScalar: {
2356 StringRef NullTerminatedStr(T.Value.c_str(), T.Value.length() + 1);
2357 StringRef StrCopy = NullTerminatedStr.copy(NodeAllocator).drop_back();
2358 return new (NodeAllocator)
2359 BlockScalarNode(stream.CurrentDoc, AnchorInfo.Range.substr(1),
2360 TagInfo.Range, StrCopy, T.Range);
2363 // Don't eat the TK_Key, KeyValueNode expects it.
2364 return new (NodeAllocator)
2365 MappingNode( stream.CurrentDoc
2366 , AnchorInfo.Range.substr(1)
2368 , MappingNode::MT_Inline);
2369 case Token::TK_DocumentStart:
2370 case Token::TK_DocumentEnd:
2371 case Token::TK_StreamEnd:
2373 // TODO: Properly handle tags. "[!!str ]" should resolve to !!str "", not
2375 return new (NodeAllocator) NullNode(stream.CurrentDoc);
2376 case Token::TK_Error:
2379 llvm_unreachable("Control flow shouldn't reach here.");
2383 bool Document::parseDirectives() {
2384 bool isDirective = false;
2386 Token T = peekNext();
2387 if (T.Kind == Token::TK_TagDirective) {
2388 parseTAGDirective();
2390 } else if (T.Kind == Token::TK_VersionDirective) {
2391 parseYAMLDirective();
2399 void Document::parseYAMLDirective() {
2400 getNext(); // Eat %YAML <version>
2403 void Document::parseTAGDirective() {
2404 Token Tag = getNext(); // %TAG <handle> <prefix>
2405 StringRef T = Tag.Range;
2407 T = T.substr(T.find_first_of(" \t")).ltrim(" \t");
2408 std::size_t HandleEnd = T.find_first_of(" \t");
2409 StringRef TagHandle = T.substr(0, HandleEnd);
2410 StringRef TagPrefix = T.substr(HandleEnd).ltrim(" \t");
2411 TagMap[TagHandle] = TagPrefix;
2414 bool Document::expectToken(int TK) {
2415 Token T = getNext();
2417 setError("Unexpected token", T);