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