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/SmallVector.h"
16 #include "llvm/ADT/StringExtras.h"
17 #include "llvm/ADT/Twine.h"
18 #include "llvm/ADT/ilist.h"
19 #include "llvm/ADT/ilist_node.h"
20 #include "llvm/Support/ErrorHandling.h"
21 #include "llvm/Support/MemoryBuffer.h"
22 #include "llvm/Support/SourceMgr.h"
23 #include "llvm/Support/raw_ostream.h"
28 enum UnicodeEncodingForm
{
29 UEF_UTF32_LE
, ///< UTF-32 Little Endian
30 UEF_UTF32_BE
, ///< UTF-32 Big Endian
31 UEF_UTF16_LE
, ///< UTF-16 Little Endian
32 UEF_UTF16_BE
, ///< UTF-16 Big Endian
33 UEF_UTF8
, ///< UTF-8 or ascii.
34 UEF_Unknown
///< Not a valid Unicode encoding.
37 /// EncodingInfo - Holds the encoding type and length of the byte order mark if
38 /// it exists. Length is in {0, 2, 3, 4}.
39 typedef std::pair
<UnicodeEncodingForm
, unsigned> EncodingInfo
;
41 /// getUnicodeEncoding - Reads up to the first 4 bytes to determine the Unicode
42 /// encoding form of \a Input.
44 /// @param Input A string of length 0 or more.
45 /// @returns An EncodingInfo indicating the Unicode encoding form of the input
46 /// and how long the byte order mark is if one exists.
47 static EncodingInfo
getUnicodeEncoding(StringRef Input
) {
48 if (Input
.size() == 0)
49 return std::make_pair(UEF_Unknown
, 0);
51 switch (uint8_t(Input
[0])) {
53 if (Input
.size() >= 4) {
55 && uint8_t(Input
[2]) == 0xFE
56 && uint8_t(Input
[3]) == 0xFF)
57 return std::make_pair(UEF_UTF32_BE
, 4);
58 if (Input
[1] == 0 && Input
[2] == 0 && Input
[3] != 0)
59 return std::make_pair(UEF_UTF32_BE
, 0);
62 if (Input
.size() >= 2 && Input
[1] != 0)
63 return std::make_pair(UEF_UTF16_BE
, 0);
64 return std::make_pair(UEF_Unknown
, 0);
66 if ( Input
.size() >= 4
67 && uint8_t(Input
[1]) == 0xFE
70 return std::make_pair(UEF_UTF32_LE
, 4);
72 if (Input
.size() >= 2 && uint8_t(Input
[1]) == 0xFE)
73 return std::make_pair(UEF_UTF16_LE
, 2);
74 return std::make_pair(UEF_Unknown
, 0);
76 if (Input
.size() >= 2 && uint8_t(Input
[1]) == 0xFF)
77 return std::make_pair(UEF_UTF16_BE
, 2);
78 return std::make_pair(UEF_Unknown
, 0);
80 if ( Input
.size() >= 3
81 && uint8_t(Input
[1]) == 0xBB
82 && uint8_t(Input
[2]) == 0xBF)
83 return std::make_pair(UEF_UTF8
, 3);
84 return std::make_pair(UEF_Unknown
, 0);
87 // It could still be utf-32 or utf-16.
88 if (Input
.size() >= 4 && Input
[1] == 0 && Input
[2] == 0 && Input
[3] == 0)
89 return std::make_pair(UEF_UTF32_LE
, 0);
91 if (Input
.size() >= 2 && Input
[1] == 0)
92 return std::make_pair(UEF_UTF16_LE
, 0);
94 return std::make_pair(UEF_UTF8
, 0);
99 /// Pin the vtables to this file.
100 void Node::anchor() {}
101 void NullNode::anchor() {}
102 void ScalarNode::anchor() {}
103 void KeyValueNode::anchor() {}
104 void MappingNode::anchor() {}
105 void SequenceNode::anchor() {}
106 void AliasNode::anchor() {}
108 /// Token - A single YAML token.
109 struct Token
: ilist_node
<Token
> {
111 TK_Error
, // Uninitialized token.
120 TK_BlockSequenceStart
,
121 TK_BlockMappingStart
,
123 TK_FlowSequenceStart
,
135 /// A string of length 0 or more whose begin() points to the logical location
136 /// of the token in the input.
139 Token() : Kind(TK_Error
) {}
146 struct ilist_sentinel_traits
<Token
> {
147 Token
*createSentinel() const {
150 static void destroySentinel(Token
*) {}
152 Token
*provideInitialHead() const { return createSentinel(); }
153 Token
*ensureHead(Token
*) const { return createSentinel(); }
154 static void noteHead(Token
*, Token
*) {}
157 mutable Token Sentinel
;
161 struct ilist_node_traits
<Token
> {
162 Token
*createNode(const Token
&V
) {
163 return new (Alloc
.Allocate
<Token
>()) Token(V
);
165 static void deleteNode(Token
*V
) {}
167 void addNodeToList(Token
*) {}
168 void removeNodeFromList(Token
*) {}
169 void transferNodesFromList(ilist_node_traits
& /*SrcTraits*/,
170 ilist_iterator
<Token
> /*first*/,
171 ilist_iterator
<Token
> /*last*/) {}
173 BumpPtrAllocator Alloc
;
177 typedef ilist
<Token
> TokenQueueT
;
180 /// @brief This struct is used to track simple keys.
182 /// Simple keys are handled by creating an entry in SimpleKeys for each Token
183 /// which could legally be the start of a simple key. When peekNext is called,
184 /// if the Token To be returned is referenced by a SimpleKey, we continue
185 /// tokenizing until that potential simple key has either been found to not be
186 /// a simple key (we moved on to the next line or went further than 1024 chars).
187 /// Or when we run into a Value, and then insert a Key token (and possibly
188 /// others) before the SimpleKey's Tok.
190 TokenQueueT::iterator Tok
;
196 bool operator ==(const SimpleKey
&Other
) {
197 return Tok
== Other
.Tok
;
202 /// @brief The Unicode scalar value of a UTF-8 minimal well-formed code unit
203 /// subsequence and the subsequence's length in code units (uint8_t).
204 /// A length of 0 represents an error.
205 typedef std::pair
<uint32_t, unsigned> UTF8Decoded
;
207 static UTF8Decoded
decodeUTF8(StringRef Range
) {
208 StringRef::iterator Position
= Range
.begin();
209 StringRef::iterator End
= Range
.end();
210 // 1 byte: [0x00, 0x7f]
211 // Bit pattern: 0xxxxxxx
212 if ((*Position
& 0x80) == 0) {
213 return std::make_pair(*Position
, 1);
215 // 2 bytes: [0x80, 0x7ff]
216 // Bit pattern: 110xxxxx 10xxxxxx
217 if (Position
+ 1 != End
&&
218 ((*Position
& 0xE0) == 0xC0) &&
219 ((*(Position
+ 1) & 0xC0) == 0x80)) {
220 uint32_t codepoint
= ((*Position
& 0x1F) << 6) |
221 (*(Position
+ 1) & 0x3F);
222 if (codepoint
>= 0x80)
223 return std::make_pair(codepoint
, 2);
225 // 3 bytes: [0x8000, 0xffff]
226 // Bit pattern: 1110xxxx 10xxxxxx 10xxxxxx
227 if (Position
+ 2 != End
&&
228 ((*Position
& 0xF0) == 0xE0) &&
229 ((*(Position
+ 1) & 0xC0) == 0x80) &&
230 ((*(Position
+ 2) & 0xC0) == 0x80)) {
231 uint32_t codepoint
= ((*Position
& 0x0F) << 12) |
232 ((*(Position
+ 1) & 0x3F) << 6) |
233 (*(Position
+ 2) & 0x3F);
234 // Codepoints between 0xD800 and 0xDFFF are invalid, as
235 // they are high / low surrogate halves used by UTF-16.
236 if (codepoint
>= 0x800 &&
237 (codepoint
< 0xD800 || codepoint
> 0xDFFF))
238 return std::make_pair(codepoint
, 3);
240 // 4 bytes: [0x10000, 0x10FFFF]
241 // Bit pattern: 11110xxx 10xxxxxx 10xxxxxx 10xxxxxx
242 if (Position
+ 3 != End
&&
243 ((*Position
& 0xF8) == 0xF0) &&
244 ((*(Position
+ 1) & 0xC0) == 0x80) &&
245 ((*(Position
+ 2) & 0xC0) == 0x80) &&
246 ((*(Position
+ 3) & 0xC0) == 0x80)) {
247 uint32_t codepoint
= ((*Position
& 0x07) << 18) |
248 ((*(Position
+ 1) & 0x3F) << 12) |
249 ((*(Position
+ 2) & 0x3F) << 6) |
250 (*(Position
+ 3) & 0x3F);
251 if (codepoint
>= 0x10000 && codepoint
<= 0x10FFFF)
252 return std::make_pair(codepoint
, 4);
254 return std::make_pair(0, 0);
259 /// @brief Scans YAML tokens from a MemoryBuffer.
262 Scanner(StringRef Input
, SourceMgr
&SM
);
263 Scanner(MemoryBufferRef Buffer
, SourceMgr
&SM_
);
265 /// @brief Parse the next token and return it without popping it.
268 /// @brief Parse the next token and pop it from the queue.
271 void printError(SMLoc Loc
, SourceMgr::DiagKind Kind
, const Twine
&Message
,
272 ArrayRef
<SMRange
> Ranges
= None
) {
273 SM
.PrintMessage(Loc
, Kind
, Message
, Ranges
);
276 void setError(const Twine
&Message
, StringRef::iterator Position
) {
280 // Don't print out more errors after the first one we encounter. The rest
281 // are just the result of the first, and have no meaning.
283 printError(SMLoc::getFromPointer(Current
), SourceMgr::DK_Error
, Message
);
287 void setError(const Twine
&Message
) {
288 setError(Message
, Current
);
291 /// @brief Returns true if an error occurred while parsing.
297 void init(MemoryBufferRef Buffer
);
299 StringRef
currentInput() {
300 return StringRef(Current
, End
- Current
);
303 /// @brief Decode a UTF-8 minimal well-formed code unit subsequence starting
306 /// If the UTF-8 code units starting at Position do not form a well-formed
307 /// code unit subsequence, then the Unicode scalar value is 0, and the length
309 UTF8Decoded
decodeUTF8(StringRef::iterator Position
) {
310 return ::decodeUTF8(StringRef(Position
, End
- Position
));
313 // The following functions are based on the gramar rules in the YAML spec. The
314 // style of the function names it meant to closely match how they are written
315 // in the spec. The number within the [] is the number of the grammar rule in
318 // See 4.2 [Production Naming Conventions] for the meaning of the prefixes.
321 // A production starting and ending with a special character.
323 // A production matching a single line break.
325 // A production starting and ending with a non-break character.
327 // A production starting and ending with a white space character.
329 // A production starting and ending with a non-space character.
331 // A production matching complete line(s).
333 /// @brief Skip a single nb-char[27] starting at Position.
335 /// A nb-char is 0x9 | [0x20-0x7E] | 0x85 | [0xA0-0xD7FF] | [0xE000-0xFEFE]
336 /// | [0xFF00-0xFFFD] | [0x10000-0x10FFFF]
338 /// @returns The code unit after the nb-char, or Position if it's not an
340 StringRef::iterator
skip_nb_char(StringRef::iterator Position
);
342 /// @brief Skip a single b-break[28] starting at Position.
344 /// A b-break is 0xD 0xA | 0xD | 0xA
346 /// @returns The code unit after the b-break, or Position if it's not a
348 StringRef::iterator
skip_b_break(StringRef::iterator Position
);
350 /// @brief Skip a single s-white[33] starting at Position.
352 /// A s-white is 0x20 | 0x9
354 /// @returns The code unit after the s-white, or Position if it's not a
356 StringRef::iterator
skip_s_white(StringRef::iterator Position
);
358 /// @brief Skip a single ns-char[34] starting at Position.
360 /// A ns-char is nb-char - s-white
362 /// @returns The code unit after the ns-char, or Position if it's not a
364 StringRef::iterator
skip_ns_char(StringRef::iterator Position
);
366 typedef StringRef::iterator (Scanner::*SkipWhileFunc
)(StringRef::iterator
);
367 /// @brief Skip minimal well-formed code unit subsequences until Func
368 /// returns its input.
370 /// @returns The code unit after the last minimal well-formed code unit
371 /// subsequence that Func accepted.
372 StringRef::iterator
skip_while( SkipWhileFunc Func
373 , StringRef::iterator Position
);
375 /// @brief Scan ns-uri-char[39]s starting at Cur.
377 /// This updates Cur and Column while scanning.
379 /// @returns A StringRef starting at Cur which covers the longest contiguous
380 /// sequence of ns-uri-char.
381 StringRef
scan_ns_uri_char();
383 /// @brief Consume a minimal well-formed code unit subsequence starting at
384 /// \a Cur. Return false if it is not the same Unicode scalar value as
385 /// \a Expected. This updates \a Column.
386 bool consume(uint32_t Expected
);
388 /// @brief Skip \a Distance UTF-8 code units. Updates \a Cur and \a Column.
389 void skip(uint32_t Distance
);
391 /// @brief Return true if the minimal well-formed code unit subsequence at
392 /// Pos is whitespace or a new line
393 bool isBlankOrBreak(StringRef::iterator Position
);
395 /// @brief If IsSimpleKeyAllowed, create and push_back a new SimpleKey.
396 void saveSimpleKeyCandidate( TokenQueueT::iterator Tok
400 /// @brief Remove simple keys that can no longer be valid simple keys.
402 /// Invalid simple keys are not on the current line or are further than 1024
404 void removeStaleSimpleKeyCandidates();
406 /// @brief Remove all simple keys on FlowLevel \a Level.
407 void removeSimpleKeyCandidatesOnFlowLevel(unsigned Level
);
409 /// @brief Unroll indentation in \a Indents back to \a Col. Creates BlockEnd
410 /// tokens if needed.
411 bool unrollIndent(int ToColumn
);
413 /// @brief Increase indent to \a Col. Creates \a Kind token at \a InsertPoint
415 bool rollIndent( int ToColumn
416 , Token::TokenKind Kind
417 , TokenQueueT::iterator InsertPoint
);
419 /// @brief Skip whitespace and comments until the start of the next token.
420 void scanToNextToken();
422 /// @brief Must be the first token generated.
423 bool scanStreamStart();
425 /// @brief Generate tokens needed to close out the stream.
426 bool scanStreamEnd();
428 /// @brief Scan a %BLAH directive.
429 bool scanDirective();
431 /// @brief Scan a ... or ---.
432 bool scanDocumentIndicator(bool IsStart
);
434 /// @brief Scan a [ or { and generate the proper flow collection start token.
435 bool scanFlowCollectionStart(bool IsSequence
);
437 /// @brief Scan a ] or } and generate the proper flow collection end token.
438 bool scanFlowCollectionEnd(bool IsSequence
);
440 /// @brief Scan the , that separates entries in a flow collection.
441 bool scanFlowEntry();
443 /// @brief Scan the - that starts block sequence entries.
444 bool scanBlockEntry();
446 /// @brief Scan an explicit ? indicating a key.
449 /// @brief Scan an explicit : indicating a value.
452 /// @brief Scan a quoted scalar.
453 bool scanFlowScalar(bool IsDoubleQuoted
);
455 /// @brief Scan an unquoted scalar.
456 bool scanPlainScalar();
458 /// @brief Scan an Alias or Anchor starting with * or &.
459 bool scanAliasOrAnchor(bool IsAlias
);
461 /// @brief Scan a block scalar starting with | or >.
462 bool scanBlockScalar(bool IsLiteral
);
464 /// @brief Scan a tag of the form !stuff.
467 /// @brief Dispatch to the next scanning function based on \a *Cur.
468 bool fetchMoreTokens();
470 /// @brief The SourceMgr used for diagnostics and buffer management.
473 /// @brief The original input.
474 MemoryBufferRef InputBuffer
;
476 /// @brief The current position of the scanner.
477 StringRef::iterator Current
;
479 /// @brief The end of the input (one past the last character).
480 StringRef::iterator End
;
482 /// @brief Current YAML indentation level in spaces.
485 /// @brief Current column number in Unicode code points.
488 /// @brief Current line number.
491 /// @brief How deep we are in flow style containers. 0 Means at block level.
494 /// @brief Are we at the start of the stream?
495 bool IsStartOfStream
;
497 /// @brief Can the next token be the start of a simple key?
498 bool IsSimpleKeyAllowed
;
500 /// @brief True if an error has occurred.
503 /// @brief Queue of tokens. This is required to queue up tokens while looking
504 /// for the end of a simple key. And for cases where a single character
505 /// can produce multiple tokens (e.g. BlockEnd).
506 TokenQueueT TokenQueue
;
508 /// @brief Indentation levels.
509 SmallVector
<int, 4> Indents
;
511 /// @brief Potential simple keys.
512 SmallVector
<SimpleKey
, 4> SimpleKeys
;
515 } // end namespace yaml
516 } // end namespace llvm
518 /// encodeUTF8 - Encode \a UnicodeScalarValue in UTF-8 and append it to result.
519 static void encodeUTF8( uint32_t UnicodeScalarValue
520 , SmallVectorImpl
<char> &Result
) {
521 if (UnicodeScalarValue
<= 0x7F) {
522 Result
.push_back(UnicodeScalarValue
& 0x7F);
523 } else if (UnicodeScalarValue
<= 0x7FF) {
524 uint8_t FirstByte
= 0xC0 | ((UnicodeScalarValue
& 0x7C0) >> 6);
525 uint8_t SecondByte
= 0x80 | (UnicodeScalarValue
& 0x3F);
526 Result
.push_back(FirstByte
);
527 Result
.push_back(SecondByte
);
528 } else if (UnicodeScalarValue
<= 0xFFFF) {
529 uint8_t FirstByte
= 0xE0 | ((UnicodeScalarValue
& 0xF000) >> 12);
530 uint8_t SecondByte
= 0x80 | ((UnicodeScalarValue
& 0xFC0) >> 6);
531 uint8_t ThirdByte
= 0x80 | (UnicodeScalarValue
& 0x3F);
532 Result
.push_back(FirstByte
);
533 Result
.push_back(SecondByte
);
534 Result
.push_back(ThirdByte
);
535 } else if (UnicodeScalarValue
<= 0x10FFFF) {
536 uint8_t FirstByte
= 0xF0 | ((UnicodeScalarValue
& 0x1F0000) >> 18);
537 uint8_t SecondByte
= 0x80 | ((UnicodeScalarValue
& 0x3F000) >> 12);
538 uint8_t ThirdByte
= 0x80 | ((UnicodeScalarValue
& 0xFC0) >> 6);
539 uint8_t FourthByte
= 0x80 | (UnicodeScalarValue
& 0x3F);
540 Result
.push_back(FirstByte
);
541 Result
.push_back(SecondByte
);
542 Result
.push_back(ThirdByte
);
543 Result
.push_back(FourthByte
);
547 bool yaml::dumpTokens(StringRef Input
, raw_ostream
&OS
) {
549 Scanner
scanner(Input
, SM
);
551 Token T
= scanner
.getNext();
553 case Token::TK_StreamStart
:
554 OS
<< "Stream-Start: ";
556 case Token::TK_StreamEnd
:
557 OS
<< "Stream-End: ";
559 case Token::TK_VersionDirective
:
560 OS
<< "Version-Directive: ";
562 case Token::TK_TagDirective
:
563 OS
<< "Tag-Directive: ";
565 case Token::TK_DocumentStart
:
566 OS
<< "Document-Start: ";
568 case Token::TK_DocumentEnd
:
569 OS
<< "Document-End: ";
571 case Token::TK_BlockEntry
:
572 OS
<< "Block-Entry: ";
574 case Token::TK_BlockEnd
:
577 case Token::TK_BlockSequenceStart
:
578 OS
<< "Block-Sequence-Start: ";
580 case Token::TK_BlockMappingStart
:
581 OS
<< "Block-Mapping-Start: ";
583 case Token::TK_FlowEntry
:
584 OS
<< "Flow-Entry: ";
586 case Token::TK_FlowSequenceStart
:
587 OS
<< "Flow-Sequence-Start: ";
589 case Token::TK_FlowSequenceEnd
:
590 OS
<< "Flow-Sequence-End: ";
592 case Token::TK_FlowMappingStart
:
593 OS
<< "Flow-Mapping-Start: ";
595 case Token::TK_FlowMappingEnd
:
596 OS
<< "Flow-Mapping-End: ";
601 case Token::TK_Value
:
604 case Token::TK_Scalar
:
607 case Token::TK_Alias
:
610 case Token::TK_Anchor
:
616 case Token::TK_Error
:
619 OS
<< T
.Range
<< "\n";
620 if (T
.Kind
== Token::TK_StreamEnd
)
622 else if (T
.Kind
== Token::TK_Error
)
628 bool yaml::scanTokens(StringRef Input
) {
630 llvm::yaml::Scanner
scanner(Input
, SM
);
632 llvm::yaml::Token T
= scanner
.getNext();
633 if (T
.Kind
== Token::TK_StreamEnd
)
635 else if (T
.Kind
== Token::TK_Error
)
641 std::string
yaml::escape(StringRef Input
) {
642 std::string EscapedInput
;
643 for (StringRef::iterator i
= Input
.begin(), e
= Input
.end(); i
!= e
; ++i
) {
645 EscapedInput
+= "\\\\";
647 EscapedInput
+= "\\\"";
649 EscapedInput
+= "\\0";
651 EscapedInput
+= "\\a";
653 EscapedInput
+= "\\b";
655 EscapedInput
+= "\\t";
657 EscapedInput
+= "\\n";
659 EscapedInput
+= "\\v";
661 EscapedInput
+= "\\f";
663 EscapedInput
+= "\\r";
665 EscapedInput
+= "\\e";
666 else if ((unsigned char)*i
< 0x20) { // Control characters not handled above.
667 std::string HexStr
= utohexstr(*i
);
668 EscapedInput
+= "\\x" + std::string(2 - HexStr
.size(), '0') + HexStr
;
669 } else if (*i
& 0x80) { // UTF-8 multiple code unit subsequence.
670 UTF8Decoded UnicodeScalarValue
671 = decodeUTF8(StringRef(i
, Input
.end() - i
));
672 if (UnicodeScalarValue
.second
== 0) {
673 // Found invalid char.
675 encodeUTF8(0xFFFD, Val
);
676 EscapedInput
.insert(EscapedInput
.end(), Val
.begin(), Val
.end());
677 // FIXME: Error reporting.
680 if (UnicodeScalarValue
.first
== 0x85)
681 EscapedInput
+= "\\N";
682 else if (UnicodeScalarValue
.first
== 0xA0)
683 EscapedInput
+= "\\_";
684 else if (UnicodeScalarValue
.first
== 0x2028)
685 EscapedInput
+= "\\L";
686 else if (UnicodeScalarValue
.first
== 0x2029)
687 EscapedInput
+= "\\P";
689 std::string HexStr
= utohexstr(UnicodeScalarValue
.first
);
690 if (HexStr
.size() <= 2)
691 EscapedInput
+= "\\x" + std::string(2 - HexStr
.size(), '0') + HexStr
;
692 else if (HexStr
.size() <= 4)
693 EscapedInput
+= "\\u" + std::string(4 - HexStr
.size(), '0') + HexStr
;
694 else if (HexStr
.size() <= 8)
695 EscapedInput
+= "\\U" + std::string(8 - HexStr
.size(), '0') + HexStr
;
697 i
+= UnicodeScalarValue
.second
- 1;
699 EscapedInput
.push_back(*i
);
704 Scanner::Scanner(StringRef Input
, SourceMgr
&sm
) : SM(sm
) {
705 init(MemoryBufferRef(Input
, "YAML"));
708 Scanner::Scanner(MemoryBufferRef Buffer
, SourceMgr
&SM_
) : SM(SM_
) {
712 void Scanner::init(MemoryBufferRef Buffer
) {
713 InputBuffer
= Buffer
;
714 Current
= InputBuffer
.getBufferStart();
715 End
= InputBuffer
.getBufferEnd();
720 IsStartOfStream
= true;
721 IsSimpleKeyAllowed
= true;
723 std::unique_ptr
<MemoryBuffer
> InputBufferOwner
=
724 MemoryBuffer::getMemBuffer(Buffer
);
725 SM
.AddNewSourceBuffer(std::move(InputBufferOwner
), SMLoc());
728 Token
&Scanner::peekNext() {
729 // If the current token is a possible simple key, keep parsing until we
731 bool NeedMore
= false;
733 if (TokenQueue
.empty() || NeedMore
) {
734 if (!fetchMoreTokens()) {
736 TokenQueue
.push_back(Token());
737 return TokenQueue
.front();
740 assert(!TokenQueue
.empty() &&
741 "fetchMoreTokens lied about getting tokens!");
743 removeStaleSimpleKeyCandidates();
745 SK
.Tok
= TokenQueue
.front();
746 if (std::find(SimpleKeys
.begin(), SimpleKeys
.end(), SK
)
752 return TokenQueue
.front();
755 Token
Scanner::getNext() {
756 Token Ret
= peekNext();
757 // TokenQueue can be empty if there was an error getting the next token.
758 if (!TokenQueue
.empty())
759 TokenQueue
.pop_front();
761 // There cannot be any referenced Token's if the TokenQueue is empty. So do a
762 // quick deallocation of them all.
763 if (TokenQueue
.empty()) {
764 TokenQueue
.Alloc
.Reset();
770 StringRef::iterator
Scanner::skip_nb_char(StringRef::iterator Position
) {
773 // Check 7 bit c-printable - b-char.
774 if ( *Position
== 0x09
775 || (*Position
>= 0x20 && *Position
<= 0x7E))
778 // Check for valid UTF-8.
779 if (uint8_t(*Position
) & 0x80) {
780 UTF8Decoded u8d
= decodeUTF8(Position
);
782 && u8d
.first
!= 0xFEFF
783 && ( u8d
.first
== 0x85
784 || ( u8d
.first
>= 0xA0
785 && u8d
.first
<= 0xD7FF)
786 || ( u8d
.first
>= 0xE000
787 && u8d
.first
<= 0xFFFD)
788 || ( u8d
.first
>= 0x10000
789 && u8d
.first
<= 0x10FFFF)))
790 return Position
+ u8d
.second
;
795 StringRef::iterator
Scanner::skip_b_break(StringRef::iterator Position
) {
798 if (*Position
== 0x0D) {
799 if (Position
+ 1 != End
&& *(Position
+ 1) == 0x0A)
804 if (*Position
== 0x0A)
810 StringRef::iterator
Scanner::skip_s_white(StringRef::iterator Position
) {
813 if (*Position
== ' ' || *Position
== '\t')
818 StringRef::iterator
Scanner::skip_ns_char(StringRef::iterator Position
) {
821 if (*Position
== ' ' || *Position
== '\t')
823 return skip_nb_char(Position
);
826 StringRef::iterator
Scanner::skip_while( SkipWhileFunc Func
827 , StringRef::iterator Position
) {
829 StringRef::iterator i
= (this->*Func
)(Position
);
837 static bool is_ns_hex_digit(const char C
) {
838 return (C
>= '0' && C
<= '9')
839 || (C
>= 'a' && C
<= 'z')
840 || (C
>= 'A' && C
<= 'Z');
843 static bool is_ns_word_char(const char C
) {
845 || (C
>= 'a' && C
<= 'z')
846 || (C
>= 'A' && C
<= 'Z');
849 StringRef
Scanner::scan_ns_uri_char() {
850 StringRef::iterator Start
= Current
;
854 if (( *Current
== '%'
856 && is_ns_hex_digit(*(Current
+ 1))
857 && is_ns_hex_digit(*(Current
+ 2)))
858 || is_ns_word_char(*Current
)
859 || StringRef(Current
, 1).find_first_of("#;/?:@&=+$,_.!~*'()[]")
860 != StringRef::npos
) {
866 return StringRef(Start
, Current
- Start
);
869 bool Scanner::consume(uint32_t Expected
) {
870 if (Expected
>= 0x80)
871 report_fatal_error("Not dealing with this yet");
874 if (uint8_t(*Current
) >= 0x80)
875 report_fatal_error("Not dealing with this yet");
876 if (uint8_t(*Current
) == Expected
) {
884 void Scanner::skip(uint32_t Distance
) {
887 assert(Current
<= End
&& "Skipped past the end");
890 bool Scanner::isBlankOrBreak(StringRef::iterator Position
) {
893 if ( *Position
== ' ' || *Position
== '\t'
894 || *Position
== '\r' || *Position
== '\n')
899 void Scanner::saveSimpleKeyCandidate( TokenQueueT::iterator Tok
902 if (IsSimpleKeyAllowed
) {
906 SK
.Column
= AtColumn
;
907 SK
.IsRequired
= IsRequired
;
908 SK
.FlowLevel
= FlowLevel
;
909 SimpleKeys
.push_back(SK
);
913 void Scanner::removeStaleSimpleKeyCandidates() {
914 for (SmallVectorImpl
<SimpleKey
>::iterator i
= SimpleKeys
.begin();
915 i
!= SimpleKeys
.end();) {
916 if (i
->Line
!= Line
|| i
->Column
+ 1024 < Column
) {
918 setError( "Could not find expected : for simple key"
919 , i
->Tok
->Range
.begin());
920 i
= SimpleKeys
.erase(i
);
926 void Scanner::removeSimpleKeyCandidatesOnFlowLevel(unsigned Level
) {
927 if (!SimpleKeys
.empty() && (SimpleKeys
.end() - 1)->FlowLevel
== Level
)
928 SimpleKeys
.pop_back();
931 bool Scanner::unrollIndent(int ToColumn
) {
933 // Indentation is ignored in flow.
937 while (Indent
> ToColumn
) {
938 T
.Kind
= Token::TK_BlockEnd
;
939 T
.Range
= StringRef(Current
, 1);
940 TokenQueue
.push_back(T
);
941 Indent
= Indents
.pop_back_val();
947 bool Scanner::rollIndent( int ToColumn
948 , Token::TokenKind Kind
949 , TokenQueueT::iterator InsertPoint
) {
952 if (Indent
< ToColumn
) {
953 Indents
.push_back(Indent
);
958 T
.Range
= StringRef(Current
, 0);
959 TokenQueue
.insert(InsertPoint
, T
);
964 void Scanner::scanToNextToken() {
966 while (*Current
== ' ' || *Current
== '\t') {
971 if (*Current
== '#') {
973 // This may skip more than one byte, thus Column is only incremented
975 StringRef::iterator i
= skip_nb_char(Current
);
984 StringRef::iterator i
= skip_b_break(Current
);
990 // New lines may start a simple key.
992 IsSimpleKeyAllowed
= true;
996 bool Scanner::scanStreamStart() {
997 IsStartOfStream
= false;
999 EncodingInfo EI
= getUnicodeEncoding(currentInput());
1002 T
.Kind
= Token::TK_StreamStart
;
1003 T
.Range
= StringRef(Current
, EI
.second
);
1004 TokenQueue
.push_back(T
);
1005 Current
+= EI
.second
;
1009 bool Scanner::scanStreamEnd() {
1010 // Force an ending new line if one isn't present.
1018 IsSimpleKeyAllowed
= false;
1021 T
.Kind
= Token::TK_StreamEnd
;
1022 T
.Range
= StringRef(Current
, 0);
1023 TokenQueue
.push_back(T
);
1027 bool Scanner::scanDirective() {
1028 // Reset the indentation level.
1031 IsSimpleKeyAllowed
= false;
1033 StringRef::iterator Start
= Current
;
1035 StringRef::iterator NameStart
= Current
;
1036 Current
= skip_while(&Scanner::skip_ns_char
, Current
);
1037 StringRef
Name(NameStart
, Current
- NameStart
);
1038 Current
= skip_while(&Scanner::skip_s_white
, Current
);
1041 if (Name
== "YAML") {
1042 Current
= skip_while(&Scanner::skip_ns_char
, Current
);
1043 T
.Kind
= Token::TK_VersionDirective
;
1044 T
.Range
= StringRef(Start
, Current
- Start
);
1045 TokenQueue
.push_back(T
);
1047 } else if(Name
== "TAG") {
1048 Current
= skip_while(&Scanner::skip_ns_char
, Current
);
1049 Current
= skip_while(&Scanner::skip_s_white
, Current
);
1050 Current
= skip_while(&Scanner::skip_ns_char
, Current
);
1051 T
.Kind
= Token::TK_TagDirective
;
1052 T
.Range
= StringRef(Start
, Current
- Start
);
1053 TokenQueue
.push_back(T
);
1059 bool Scanner::scanDocumentIndicator(bool IsStart
) {
1062 IsSimpleKeyAllowed
= false;
1065 T
.Kind
= IsStart
? Token::TK_DocumentStart
: Token::TK_DocumentEnd
;
1066 T
.Range
= StringRef(Current
, 3);
1068 TokenQueue
.push_back(T
);
1072 bool Scanner::scanFlowCollectionStart(bool IsSequence
) {
1074 T
.Kind
= IsSequence
? Token::TK_FlowSequenceStart
1075 : Token::TK_FlowMappingStart
;
1076 T
.Range
= StringRef(Current
, 1);
1078 TokenQueue
.push_back(T
);
1080 // [ and { may begin a simple key.
1081 saveSimpleKeyCandidate(TokenQueue
.back(), Column
- 1, false);
1083 // And may also be followed by a simple key.
1084 IsSimpleKeyAllowed
= true;
1089 bool Scanner::scanFlowCollectionEnd(bool IsSequence
) {
1090 removeSimpleKeyCandidatesOnFlowLevel(FlowLevel
);
1091 IsSimpleKeyAllowed
= false;
1093 T
.Kind
= IsSequence
? Token::TK_FlowSequenceEnd
1094 : Token::TK_FlowMappingEnd
;
1095 T
.Range
= StringRef(Current
, 1);
1097 TokenQueue
.push_back(T
);
1103 bool Scanner::scanFlowEntry() {
1104 removeSimpleKeyCandidatesOnFlowLevel(FlowLevel
);
1105 IsSimpleKeyAllowed
= true;
1107 T
.Kind
= Token::TK_FlowEntry
;
1108 T
.Range
= StringRef(Current
, 1);
1110 TokenQueue
.push_back(T
);
1114 bool Scanner::scanBlockEntry() {
1115 rollIndent(Column
, Token::TK_BlockSequenceStart
, TokenQueue
.end());
1116 removeSimpleKeyCandidatesOnFlowLevel(FlowLevel
);
1117 IsSimpleKeyAllowed
= true;
1119 T
.Kind
= Token::TK_BlockEntry
;
1120 T
.Range
= StringRef(Current
, 1);
1122 TokenQueue
.push_back(T
);
1126 bool Scanner::scanKey() {
1128 rollIndent(Column
, Token::TK_BlockMappingStart
, TokenQueue
.end());
1130 removeSimpleKeyCandidatesOnFlowLevel(FlowLevel
);
1131 IsSimpleKeyAllowed
= !FlowLevel
;
1134 T
.Kind
= Token::TK_Key
;
1135 T
.Range
= StringRef(Current
, 1);
1137 TokenQueue
.push_back(T
);
1141 bool Scanner::scanValue() {
1142 // If the previous token could have been a simple key, insert the key token
1143 // into the token queue.
1144 if (!SimpleKeys
.empty()) {
1145 SimpleKey SK
= SimpleKeys
.pop_back_val();
1147 T
.Kind
= Token::TK_Key
;
1148 T
.Range
= SK
.Tok
->Range
;
1149 TokenQueueT::iterator i
, e
;
1150 for (i
= TokenQueue
.begin(), e
= TokenQueue
.end(); i
!= e
; ++i
) {
1154 assert(i
!= e
&& "SimpleKey not in token queue!");
1155 i
= TokenQueue
.insert(i
, T
);
1157 // We may also need to add a Block-Mapping-Start token.
1158 rollIndent(SK
.Column
, Token::TK_BlockMappingStart
, i
);
1160 IsSimpleKeyAllowed
= false;
1163 rollIndent(Column
, Token::TK_BlockMappingStart
, TokenQueue
.end());
1164 IsSimpleKeyAllowed
= !FlowLevel
;
1168 T
.Kind
= Token::TK_Value
;
1169 T
.Range
= StringRef(Current
, 1);
1171 TokenQueue
.push_back(T
);
1175 // Forbidding inlining improves performance by roughly 20%.
1176 // FIXME: Remove once llvm optimizes this to the faster version without hints.
1177 LLVM_ATTRIBUTE_NOINLINE
static bool
1178 wasEscaped(StringRef::iterator First
, StringRef::iterator Position
);
1180 // Returns whether a character at 'Position' was escaped with a leading '\'.
1181 // 'First' specifies the position of the first character in the string.
1182 static bool wasEscaped(StringRef::iterator First
,
1183 StringRef::iterator Position
) {
1184 assert(Position
- 1 >= First
);
1185 StringRef::iterator I
= Position
- 1;
1186 // We calculate the number of consecutive '\'s before the current position
1187 // by iterating backwards through our string.
1188 while (I
>= First
&& *I
== '\\') --I
;
1189 // (Position - 1 - I) now contains the number of '\'s before the current
1190 // position. If it is odd, the character at 'Position' was escaped.
1191 return (Position
- 1 - I
) % 2 == 1;
1194 bool Scanner::scanFlowScalar(bool IsDoubleQuoted
) {
1195 StringRef::iterator Start
= Current
;
1196 unsigned ColStart
= Column
;
1197 if (IsDoubleQuoted
) {
1200 while (Current
!= End
&& *Current
!= '"')
1202 // Repeat until the previous character was not a '\' or was an escaped
1204 } while ( Current
!= End
1205 && *(Current
- 1) == '\\'
1206 && wasEscaped(Start
+ 1, Current
));
1210 // Skip a ' followed by another '.
1211 if (Current
+ 1 < End
&& *Current
== '\'' && *(Current
+ 1) == '\'') {
1214 } else if (*Current
== '\'')
1216 StringRef::iterator i
= skip_nb_char(Current
);
1218 i
= skip_b_break(Current
);
1233 if (Current
== End
) {
1234 setError("Expected quote at end of scalar", Current
);
1238 skip(1); // Skip ending quote.
1240 T
.Kind
= Token::TK_Scalar
;
1241 T
.Range
= StringRef(Start
, Current
- Start
);
1242 TokenQueue
.push_back(T
);
1244 saveSimpleKeyCandidate(TokenQueue
.back(), ColStart
, false);
1246 IsSimpleKeyAllowed
= false;
1251 bool Scanner::scanPlainScalar() {
1252 StringRef::iterator Start
= Current
;
1253 unsigned ColStart
= Column
;
1254 unsigned LeadingBlanks
= 0;
1255 assert(Indent
>= -1 && "Indent must be >= -1 !");
1256 unsigned indent
= static_cast<unsigned>(Indent
+ 1);
1258 if (*Current
== '#')
1261 while (!isBlankOrBreak(Current
)) {
1262 if ( FlowLevel
&& *Current
== ':'
1263 && !(isBlankOrBreak(Current
+ 1) || *(Current
+ 1) == ',')) {
1264 setError("Found unexpected ':' while scanning a plain scalar", Current
);
1268 // Check for the end of the plain scalar.
1269 if ( (*Current
== ':' && isBlankOrBreak(Current
+ 1))
1271 && (StringRef(Current
, 1).find_first_of(",:?[]{}")
1272 != StringRef::npos
)))
1275 StringRef::iterator i
= skip_nb_char(Current
);
1282 // Are we at the end?
1283 if (!isBlankOrBreak(Current
))
1287 StringRef::iterator Tmp
= Current
;
1288 while (isBlankOrBreak(Tmp
)) {
1289 StringRef::iterator i
= skip_s_white(Tmp
);
1291 if (LeadingBlanks
&& (Column
< indent
) && *Tmp
== '\t') {
1292 setError("Found invalid tab character in indentation", Tmp
);
1298 i
= skip_b_break(Tmp
);
1307 if (!FlowLevel
&& Column
< indent
)
1312 if (Start
== Current
) {
1313 setError("Got empty plain scalar", Start
);
1317 T
.Kind
= Token::TK_Scalar
;
1318 T
.Range
= StringRef(Start
, Current
- Start
);
1319 TokenQueue
.push_back(T
);
1321 // Plain scalars can be simple keys.
1322 saveSimpleKeyCandidate(TokenQueue
.back(), ColStart
, false);
1324 IsSimpleKeyAllowed
= false;
1329 bool Scanner::scanAliasOrAnchor(bool IsAlias
) {
1330 StringRef::iterator Start
= Current
;
1331 unsigned ColStart
= Column
;
1334 if ( *Current
== '[' || *Current
== ']'
1335 || *Current
== '{' || *Current
== '}'
1339 StringRef::iterator i
= skip_ns_char(Current
);
1346 if (Start
== Current
) {
1347 setError("Got empty alias or anchor", Start
);
1352 T
.Kind
= IsAlias
? Token::TK_Alias
: Token::TK_Anchor
;
1353 T
.Range
= StringRef(Start
, Current
- Start
);
1354 TokenQueue
.push_back(T
);
1356 // Alias and anchors can be simple keys.
1357 saveSimpleKeyCandidate(TokenQueue
.back(), ColStart
, false);
1359 IsSimpleKeyAllowed
= false;
1364 bool Scanner::scanBlockScalar(bool IsLiteral
) {
1365 StringRef::iterator Start
= Current
;
1366 skip(1); // Eat | or >
1368 StringRef::iterator i
= skip_nb_char(Current
);
1372 i
= skip_b_break(Current
);
1374 // We got a line break.
1380 // There was an error, which should already have been printed out.
1388 if (Start
== Current
) {
1389 setError("Got empty block scalar", Start
);
1394 T
.Kind
= Token::TK_Scalar
;
1395 T
.Range
= StringRef(Start
, Current
- Start
);
1396 TokenQueue
.push_back(T
);
1400 bool Scanner::scanTag() {
1401 StringRef::iterator Start
= Current
;
1402 unsigned ColStart
= Column
;
1404 if (Current
== End
|| isBlankOrBreak(Current
)); // An empty tag.
1405 else if (*Current
== '<') {
1411 // FIXME: Actually parse the c-ns-shorthand-tag rule.
1412 Current
= skip_while(&Scanner::skip_ns_char
, Current
);
1416 T
.Kind
= Token::TK_Tag
;
1417 T
.Range
= StringRef(Start
, Current
- Start
);
1418 TokenQueue
.push_back(T
);
1420 // Tags can be simple keys.
1421 saveSimpleKeyCandidate(TokenQueue
.back(), ColStart
, false);
1423 IsSimpleKeyAllowed
= false;
1428 bool Scanner::fetchMoreTokens() {
1429 if (IsStartOfStream
)
1430 return scanStreamStart();
1435 return scanStreamEnd();
1437 removeStaleSimpleKeyCandidates();
1439 unrollIndent(Column
);
1441 if (Column
== 0 && *Current
== '%')
1442 return scanDirective();
1444 if (Column
== 0 && Current
+ 4 <= End
1446 && *(Current
+ 1) == '-'
1447 && *(Current
+ 2) == '-'
1448 && (Current
+ 3 == End
|| isBlankOrBreak(Current
+ 3)))
1449 return scanDocumentIndicator(true);
1451 if (Column
== 0 && Current
+ 4 <= End
1453 && *(Current
+ 1) == '.'
1454 && *(Current
+ 2) == '.'
1455 && (Current
+ 3 == End
|| isBlankOrBreak(Current
+ 3)))
1456 return scanDocumentIndicator(false);
1458 if (*Current
== '[')
1459 return scanFlowCollectionStart(true);
1461 if (*Current
== '{')
1462 return scanFlowCollectionStart(false);
1464 if (*Current
== ']')
1465 return scanFlowCollectionEnd(true);
1467 if (*Current
== '}')
1468 return scanFlowCollectionEnd(false);
1470 if (*Current
== ',')
1471 return scanFlowEntry();
1473 if (*Current
== '-' && isBlankOrBreak(Current
+ 1))
1474 return scanBlockEntry();
1476 if (*Current
== '?' && (FlowLevel
|| isBlankOrBreak(Current
+ 1)))
1479 if (*Current
== ':' && (FlowLevel
|| isBlankOrBreak(Current
+ 1)))
1482 if (*Current
== '*')
1483 return scanAliasOrAnchor(true);
1485 if (*Current
== '&')
1486 return scanAliasOrAnchor(false);
1488 if (*Current
== '!')
1491 if (*Current
== '|' && !FlowLevel
)
1492 return scanBlockScalar(true);
1494 if (*Current
== '>' && !FlowLevel
)
1495 return scanBlockScalar(false);
1497 if (*Current
== '\'')
1498 return scanFlowScalar(false);
1500 if (*Current
== '"')
1501 return scanFlowScalar(true);
1503 // Get a plain scalar.
1504 StringRef
FirstChar(Current
, 1);
1505 if (!(isBlankOrBreak(Current
)
1506 || FirstChar
.find_first_of("-?:,[]{}#&*!|>'\"%@`") != StringRef::npos
)
1507 || (*Current
== '-' && !isBlankOrBreak(Current
+ 1))
1508 || (!FlowLevel
&& (*Current
== '?' || *Current
== ':')
1509 && isBlankOrBreak(Current
+ 1))
1510 || (!FlowLevel
&& *Current
== ':'
1511 && Current
+ 2 < End
1512 && *(Current
+ 1) == ':'
1513 && !isBlankOrBreak(Current
+ 2)))
1514 return scanPlainScalar();
1516 setError("Unrecognized character while tokenizing.");
1520 Stream::Stream(StringRef Input
, SourceMgr
&SM
)
1521 : scanner(new Scanner(Input
, SM
)), CurrentDoc() {}
1523 Stream::Stream(MemoryBufferRef InputBuffer
, SourceMgr
&SM
)
1524 : scanner(new Scanner(InputBuffer
, SM
)), CurrentDoc() {}
1526 Stream::~Stream() {}
1528 bool Stream::failed() { return scanner
->failed(); }
1530 void Stream::printError(Node
*N
, const Twine
&Msg
) {
1531 SmallVector
<SMRange
, 1> Ranges
;
1532 Ranges
.push_back(N
->getSourceRange());
1533 scanner
->printError( N
->getSourceRange().Start
1534 , SourceMgr::DK_Error
1539 document_iterator
Stream::begin() {
1541 report_fatal_error("Can only iterate over the stream once");
1543 // Skip Stream-Start.
1546 CurrentDoc
.reset(new Document(*this));
1547 return document_iterator(CurrentDoc
);
1550 document_iterator
Stream::end() {
1551 return document_iterator();
1554 void Stream::skip() {
1555 for (document_iterator i
= begin(), e
= end(); i
!= e
; ++i
)
1559 Node::Node(unsigned int Type
, std::unique_ptr
<Document
> &D
, StringRef A
,
1561 : Doc(D
), TypeID(Type
), Anchor(A
), Tag(T
) {
1562 SMLoc Start
= SMLoc::getFromPointer(peekNext().Range
.begin());
1563 SourceRange
= SMRange(Start
, Start
);
1566 std::string
Node::getVerbatimTag() const {
1567 StringRef Raw
= getRawTag();
1568 if (!Raw
.empty() && Raw
!= "!") {
1570 if (Raw
.find_last_of('!') == 0) {
1571 Ret
= Doc
->getTagMap().find("!")->second
;
1572 Ret
+= Raw
.substr(1);
1573 return std::move(Ret
);
1574 } else if (Raw
.startswith("!!")) {
1575 Ret
= Doc
->getTagMap().find("!!")->second
;
1576 Ret
+= Raw
.substr(2);
1577 return std::move(Ret
);
1579 StringRef TagHandle
= Raw
.substr(0, Raw
.find_last_of('!') + 1);
1580 std::map
<StringRef
, StringRef
>::const_iterator It
=
1581 Doc
->getTagMap().find(TagHandle
);
1582 if (It
!= Doc
->getTagMap().end())
1586 T
.Kind
= Token::TK_Tag
;
1587 T
.Range
= TagHandle
;
1588 setError(Twine("Unknown tag handle ") + TagHandle
, T
);
1590 Ret
+= Raw
.substr(Raw
.find_last_of('!') + 1);
1591 return std::move(Ret
);
1595 switch (getType()) {
1597 return "tag:yaml.org,2002:null";
1599 // TODO: Tag resolution.
1600 return "tag:yaml.org,2002:str";
1602 return "tag:yaml.org,2002:map";
1604 return "tag:yaml.org,2002:seq";
1610 Token
&Node::peekNext() {
1611 return Doc
->peekNext();
1614 Token
Node::getNext() {
1615 return Doc
->getNext();
1618 Node
*Node::parseBlockNode() {
1619 return Doc
->parseBlockNode();
1622 BumpPtrAllocator
&Node::getAllocator() {
1623 return Doc
->NodeAllocator
;
1626 void Node::setError(const Twine
&Msg
, Token
&Tok
) const {
1627 Doc
->setError(Msg
, Tok
);
1630 bool Node::failed() const {
1631 return Doc
->failed();
1636 StringRef
ScalarNode::getValue(SmallVectorImpl
<char> &Storage
) const {
1637 // TODO: Handle newlines properly. We need to remove leading whitespace.
1638 if (Value
[0] == '"') { // Double quoted.
1639 // Pull off the leading and trailing "s.
1640 StringRef UnquotedValue
= Value
.substr(1, Value
.size() - 2);
1641 // Search for characters that would require unescaping the value.
1642 StringRef::size_type i
= UnquotedValue
.find_first_of("\\\r\n");
1643 if (i
!= StringRef::npos
)
1644 return unescapeDoubleQuoted(UnquotedValue
, i
, Storage
);
1645 return UnquotedValue
;
1646 } else if (Value
[0] == '\'') { // Single quoted.
1647 // Pull off the leading and trailing 's.
1648 StringRef UnquotedValue
= Value
.substr(1, Value
.size() - 2);
1649 StringRef::size_type i
= UnquotedValue
.find('\'');
1650 if (i
!= StringRef::npos
) {
1651 // We're going to need Storage.
1653 Storage
.reserve(UnquotedValue
.size());
1654 for (; i
!= StringRef::npos
; i
= UnquotedValue
.find('\'')) {
1655 StringRef
Valid(UnquotedValue
.begin(), i
);
1656 Storage
.insert(Storage
.end(), Valid
.begin(), Valid
.end());
1657 Storage
.push_back('\'');
1658 UnquotedValue
= UnquotedValue
.substr(i
+ 2);
1660 Storage
.insert(Storage
.end(), UnquotedValue
.begin(), UnquotedValue
.end());
1661 return StringRef(Storage
.begin(), Storage
.size());
1663 return UnquotedValue
;
1666 return Value
.rtrim(" ");
1669 StringRef
ScalarNode::unescapeDoubleQuoted( StringRef UnquotedValue
1670 , StringRef::size_type i
1671 , SmallVectorImpl
<char> &Storage
)
1673 // Use Storage to build proper value.
1675 Storage
.reserve(UnquotedValue
.size());
1676 for (; i
!= StringRef::npos
; i
= UnquotedValue
.find_first_of("\\\r\n")) {
1677 // Insert all previous chars into Storage.
1678 StringRef
Valid(UnquotedValue
.begin(), i
);
1679 Storage
.insert(Storage
.end(), Valid
.begin(), Valid
.end());
1680 // Chop off inserted chars.
1681 UnquotedValue
= UnquotedValue
.substr(i
);
1683 assert(!UnquotedValue
.empty() && "Can't be empty!");
1685 // Parse escape or line break.
1686 switch (UnquotedValue
[0]) {
1689 Storage
.push_back('\n');
1690 if ( UnquotedValue
.size() > 1
1691 && (UnquotedValue
[1] == '\r' || UnquotedValue
[1] == '\n'))
1692 UnquotedValue
= UnquotedValue
.substr(1);
1693 UnquotedValue
= UnquotedValue
.substr(1);
1696 if (UnquotedValue
.size() == 1)
1697 // TODO: Report error.
1699 UnquotedValue
= UnquotedValue
.substr(1);
1700 switch (UnquotedValue
[0]) {
1703 T
.Range
= StringRef(UnquotedValue
.begin(), 1);
1704 setError("Unrecognized escape code!", T
);
1709 // Remove the new line.
1710 if ( UnquotedValue
.size() > 1
1711 && (UnquotedValue
[1] == '\r' || UnquotedValue
[1] == '\n'))
1712 UnquotedValue
= UnquotedValue
.substr(1);
1713 // If this was just a single byte newline, it will get skipped
1717 Storage
.push_back(0x00);
1720 Storage
.push_back(0x07);
1723 Storage
.push_back(0x08);
1727 Storage
.push_back(0x09);
1730 Storage
.push_back(0x0A);
1733 Storage
.push_back(0x0B);
1736 Storage
.push_back(0x0C);
1739 Storage
.push_back(0x0D);
1742 Storage
.push_back(0x1B);
1745 Storage
.push_back(0x20);
1748 Storage
.push_back(0x22);
1751 Storage
.push_back(0x2F);
1754 Storage
.push_back(0x5C);
1757 encodeUTF8(0x85, Storage
);
1760 encodeUTF8(0xA0, Storage
);
1763 encodeUTF8(0x2028, Storage
);
1766 encodeUTF8(0x2029, Storage
);
1769 if (UnquotedValue
.size() < 3)
1770 // TODO: Report error.
1772 unsigned int UnicodeScalarValue
;
1773 if (UnquotedValue
.substr(1, 2).getAsInteger(16, UnicodeScalarValue
))
1774 // TODO: Report error.
1775 UnicodeScalarValue
= 0xFFFD;
1776 encodeUTF8(UnicodeScalarValue
, Storage
);
1777 UnquotedValue
= UnquotedValue
.substr(2);
1781 if (UnquotedValue
.size() < 5)
1782 // TODO: Report error.
1784 unsigned int UnicodeScalarValue
;
1785 if (UnquotedValue
.substr(1, 4).getAsInteger(16, UnicodeScalarValue
))
1786 // TODO: Report error.
1787 UnicodeScalarValue
= 0xFFFD;
1788 encodeUTF8(UnicodeScalarValue
, Storage
);
1789 UnquotedValue
= UnquotedValue
.substr(4);
1793 if (UnquotedValue
.size() < 9)
1794 // TODO: Report error.
1796 unsigned int UnicodeScalarValue
;
1797 if (UnquotedValue
.substr(1, 8).getAsInteger(16, UnicodeScalarValue
))
1798 // TODO: Report error.
1799 UnicodeScalarValue
= 0xFFFD;
1800 encodeUTF8(UnicodeScalarValue
, Storage
);
1801 UnquotedValue
= UnquotedValue
.substr(8);
1805 UnquotedValue
= UnquotedValue
.substr(1);
1808 Storage
.insert(Storage
.end(), UnquotedValue
.begin(), UnquotedValue
.end());
1809 return StringRef(Storage
.begin(), Storage
.size());
1812 Node
*KeyValueNode::getKey() {
1815 // Handle implicit null keys.
1817 Token
&t
= peekNext();
1818 if ( t
.Kind
== Token::TK_BlockEnd
1819 || t
.Kind
== Token::TK_Value
1820 || t
.Kind
== Token::TK_Error
) {
1821 return Key
= new (getAllocator()) NullNode(Doc
);
1823 if (t
.Kind
== Token::TK_Key
)
1824 getNext(); // skip TK_Key.
1827 // Handle explicit null keys.
1828 Token
&t
= peekNext();
1829 if (t
.Kind
== Token::TK_BlockEnd
|| t
.Kind
== Token::TK_Value
) {
1830 return Key
= new (getAllocator()) NullNode(Doc
);
1833 // We've got a normal key.
1834 return Key
= parseBlockNode();
1837 Node
*KeyValueNode::getValue() {
1842 return Value
= new (getAllocator()) NullNode(Doc
);
1844 // Handle implicit null values.
1846 Token
&t
= peekNext();
1847 if ( t
.Kind
== Token::TK_BlockEnd
1848 || t
.Kind
== Token::TK_FlowMappingEnd
1849 || t
.Kind
== Token::TK_Key
1850 || t
.Kind
== Token::TK_FlowEntry
1851 || t
.Kind
== Token::TK_Error
) {
1852 return Value
= new (getAllocator()) NullNode(Doc
);
1855 if (t
.Kind
!= Token::TK_Value
) {
1856 setError("Unexpected token in Key Value.", t
);
1857 return Value
= new (getAllocator()) NullNode(Doc
);
1859 getNext(); // skip TK_Value.
1862 // Handle explicit null values.
1863 Token
&t
= peekNext();
1864 if (t
.Kind
== Token::TK_BlockEnd
|| t
.Kind
== Token::TK_Key
) {
1865 return Value
= new (getAllocator()) NullNode(Doc
);
1868 // We got a normal value.
1869 return Value
= parseBlockNode();
1872 void MappingNode::increment() {
1875 CurrentEntry
= nullptr;
1879 CurrentEntry
->skip();
1880 if (Type
== MT_Inline
) {
1882 CurrentEntry
= nullptr;
1886 Token T
= peekNext();
1887 if (T
.Kind
== Token::TK_Key
|| T
.Kind
== Token::TK_Scalar
) {
1888 // KeyValueNode eats the TK_Key. That way it can detect null keys.
1889 CurrentEntry
= new (getAllocator()) KeyValueNode(Doc
);
1890 } else if (Type
== MT_Block
) {
1892 case Token::TK_BlockEnd
:
1895 CurrentEntry
= nullptr;
1898 setError("Unexpected token. Expected Key or Block End", T
);
1899 case Token::TK_Error
:
1901 CurrentEntry
= nullptr;
1905 case Token::TK_FlowEntry
:
1906 // Eat the flow entry and recurse.
1909 case Token::TK_FlowMappingEnd
:
1911 case Token::TK_Error
:
1912 // Set this to end iterator.
1914 CurrentEntry
= nullptr;
1917 setError( "Unexpected token. Expected Key, Flow Entry, or Flow "
1921 CurrentEntry
= nullptr;
1926 void SequenceNode::increment() {
1929 CurrentEntry
= nullptr;
1933 CurrentEntry
->skip();
1934 Token T
= peekNext();
1935 if (SeqType
== ST_Block
) {
1937 case Token::TK_BlockEntry
:
1939 CurrentEntry
= parseBlockNode();
1940 if (!CurrentEntry
) { // An error occurred.
1942 CurrentEntry
= nullptr;
1945 case Token::TK_BlockEnd
:
1948 CurrentEntry
= nullptr;
1951 setError( "Unexpected token. Expected Block Entry or Block End."
1953 case Token::TK_Error
:
1955 CurrentEntry
= nullptr;
1957 } else if (SeqType
== ST_Indentless
) {
1959 case Token::TK_BlockEntry
:
1961 CurrentEntry
= parseBlockNode();
1962 if (!CurrentEntry
) { // An error occurred.
1964 CurrentEntry
= nullptr;
1968 case Token::TK_Error
:
1970 CurrentEntry
= nullptr;
1972 } else if (SeqType
== ST_Flow
) {
1974 case Token::TK_FlowEntry
:
1975 // Eat the flow entry and recurse.
1977 WasPreviousTokenFlowEntry
= true;
1979 case Token::TK_FlowSequenceEnd
:
1981 case Token::TK_Error
:
1982 // Set this to end iterator.
1984 CurrentEntry
= nullptr;
1986 case Token::TK_StreamEnd
:
1987 case Token::TK_DocumentEnd
:
1988 case Token::TK_DocumentStart
:
1989 setError("Could not find closing ]!", T
);
1990 // Set this to end iterator.
1992 CurrentEntry
= nullptr;
1995 if (!WasPreviousTokenFlowEntry
) {
1996 setError("Expected , between entries!", T
);
1998 CurrentEntry
= nullptr;
2001 // Otherwise it must be a flow entry.
2002 CurrentEntry
= parseBlockNode();
2003 if (!CurrentEntry
) {
2006 WasPreviousTokenFlowEntry
= false;
2012 Document::Document(Stream
&S
) : stream(S
), Root(nullptr) {
2013 // Tag maps starts with two default mappings.
2015 TagMap
["!!"] = "tag:yaml.org,2002:";
2017 if (parseDirectives())
2018 expectToken(Token::TK_DocumentStart
);
2019 Token
&T
= peekNext();
2020 if (T
.Kind
== Token::TK_DocumentStart
)
2024 bool Document::skip() {
2025 if (stream
.scanner
->failed())
2030 Token
&T
= peekNext();
2031 if (T
.Kind
== Token::TK_StreamEnd
)
2033 if (T
.Kind
== Token::TK_DocumentEnd
) {
2040 Token
&Document::peekNext() {
2041 return stream
.scanner
->peekNext();
2044 Token
Document::getNext() {
2045 return stream
.scanner
->getNext();
2048 void Document::setError(const Twine
&Message
, Token
&Location
) const {
2049 stream
.scanner
->setError(Message
, Location
.Range
.begin());
2052 bool Document::failed() const {
2053 return stream
.scanner
->failed();
2056 Node
*Document::parseBlockNode() {
2057 Token T
= peekNext();
2058 // Handle properties.
2063 case Token::TK_Alias
:
2065 return new (NodeAllocator
) AliasNode(stream
.CurrentDoc
, T
.Range
.substr(1));
2066 case Token::TK_Anchor
:
2067 if (AnchorInfo
.Kind
== Token::TK_Anchor
) {
2068 setError("Already encountered an anchor for this node!", T
);
2071 AnchorInfo
= getNext(); // Consume TK_Anchor.
2073 goto parse_property
;
2075 if (TagInfo
.Kind
== Token::TK_Tag
) {
2076 setError("Already encountered a tag for this node!", T
);
2079 TagInfo
= getNext(); // Consume TK_Tag.
2081 goto parse_property
;
2087 case Token::TK_BlockEntry
:
2088 // We got an unindented BlockEntry sequence. This is not terminated with
2090 // Don't eat the TK_BlockEntry, SequenceNode needs it.
2091 return new (NodeAllocator
) SequenceNode( stream
.CurrentDoc
2092 , AnchorInfo
.Range
.substr(1)
2094 , SequenceNode::ST_Indentless
);
2095 case Token::TK_BlockSequenceStart
:
2097 return new (NodeAllocator
)
2098 SequenceNode( stream
.CurrentDoc
2099 , AnchorInfo
.Range
.substr(1)
2101 , SequenceNode::ST_Block
);
2102 case Token::TK_BlockMappingStart
:
2104 return new (NodeAllocator
)
2105 MappingNode( stream
.CurrentDoc
2106 , AnchorInfo
.Range
.substr(1)
2108 , MappingNode::MT_Block
);
2109 case Token::TK_FlowSequenceStart
:
2111 return new (NodeAllocator
)
2112 SequenceNode( stream
.CurrentDoc
2113 , AnchorInfo
.Range
.substr(1)
2115 , SequenceNode::ST_Flow
);
2116 case Token::TK_FlowMappingStart
:
2118 return new (NodeAllocator
)
2119 MappingNode( stream
.CurrentDoc
2120 , AnchorInfo
.Range
.substr(1)
2122 , MappingNode::MT_Flow
);
2123 case Token::TK_Scalar
:
2125 return new (NodeAllocator
)
2126 ScalarNode( stream
.CurrentDoc
2127 , AnchorInfo
.Range
.substr(1)
2131 // Don't eat the TK_Key, KeyValueNode expects it.
2132 return new (NodeAllocator
)
2133 MappingNode( stream
.CurrentDoc
2134 , AnchorInfo
.Range
.substr(1)
2136 , MappingNode::MT_Inline
);
2137 case Token::TK_DocumentStart
:
2138 case Token::TK_DocumentEnd
:
2139 case Token::TK_StreamEnd
:
2141 // TODO: Properly handle tags. "[!!str ]" should resolve to !!str "", not
2143 return new (NodeAllocator
) NullNode(stream
.CurrentDoc
);
2144 case Token::TK_Error
:
2147 llvm_unreachable("Control flow shouldn't reach here.");
2151 bool Document::parseDirectives() {
2152 bool isDirective
= false;
2154 Token T
= peekNext();
2155 if (T
.Kind
== Token::TK_TagDirective
) {
2156 parseTAGDirective();
2158 } else if (T
.Kind
== Token::TK_VersionDirective
) {
2159 parseYAMLDirective();
2167 void Document::parseYAMLDirective() {
2168 getNext(); // Eat %YAML <version>
2171 void Document::parseTAGDirective() {
2172 Token Tag
= getNext(); // %TAG <handle> <prefix>
2173 StringRef T
= Tag
.Range
;
2175 T
= T
.substr(T
.find_first_of(" \t")).ltrim(" \t");
2176 std::size_t HandleEnd
= T
.find_first_of(" \t");
2177 StringRef TagHandle
= T
.substr(0, HandleEnd
);
2178 StringRef TagPrefix
= T
.substr(HandleEnd
).ltrim(" \t");
2179 TagMap
[TagHandle
] = TagPrefix
;
2182 bool Document::expectToken(int TK
) {
2183 Token T
= getNext();
2185 setError("Unexpected token", T
);