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
26using namespace llvm;
27using namespace yaml;
28
29enum 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}.
40typedef 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.
48static 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
98namespace llvm {
99namespace yaml {
100/// Pin the vtables to this file.
101void Node::anchor() {}
102void NullNode::anchor() {}
103void ScalarNode::anchor() {}
104void BlockScalarNode::anchor() {}
105void KeyValueNode::anchor() {}
106void MappingNode::anchor() {}
107void SequenceNode::anchor() {}
108void AliasNode::anchor() {}
109
110/// Token - A single YAML token.
111struct Token : ilist_node<Token> {
112  enum TokenKind {
113    TK_Error, // Uninitialized token.
114    TK_StreamStart,
115    TK_StreamEnd,
116    TK_VersionDirective,
117    TK_TagDirective,
118    TK_DocumentStart,
119    TK_DocumentEnd,
120    TK_BlockEntry,
121    TK_BlockEnd,
122    TK_BlockSequenceStart,
123    TK_BlockMappingStart,
124    TK_FlowEntry,
125    TK_FlowSequenceStart,
126    TK_FlowSequenceEnd,
127    TK_FlowMappingStart,
128    TK_FlowMappingEnd,
129    TK_Key,
130    TK_Value,
131    TK_Scalar,
132    TK_BlockScalar,
133    TK_Alias,
134    TK_Anchor,
135    TK_Tag
136  } Kind;
137
138  /// A string of length 0 or more whose begin() points to the logical location
139  /// of the token in the input.
140  StringRef Range;
141
142  /// The value of a block scalar node.
143  std::string Value;
144
145  Token() : Kind(TK_Error) {}
146};
147}
148}
149
150namespace llvm {
151template<>
152struct ilist_sentinel_traits<Token> {
153  Token *createSentinel() const {
154    return &Sentinel;
155  }
156  static void destroySentinel(Token*) {}
157
158  Token *provideInitialHead() const { return createSentinel(); }
159  Token *ensureHead(Token*) const { return createSentinel(); }
160  static void noteHead(Token*, Token*) {}
161
162private:
163  mutable Token Sentinel;
164};
165
166template<>
167struct ilist_node_traits<Token> {
168  Token *createNode(const Token &V) {
169    return new (Alloc.Allocate<Token>()) Token(V);
170  }
171  static void deleteNode(Token *V) { V->~Token(); }
172
173  void addNodeToList(Token *) {}
174  void removeNodeFromList(Token *) {}
175  void transferNodesFromList(ilist_node_traits &    /*SrcTraits*/,
176                             ilist_iterator<Token> /*first*/,
177                             ilist_iterator<Token> /*last*/) {}
178
179  BumpPtrAllocator Alloc;
180};
181}
182
183typedef ilist<Token> TokenQueueT;
184
185namespace {
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.
195struct SimpleKey {
196  TokenQueueT::iterator Tok;
197  unsigned Column;
198  unsigned Line;
199  unsigned FlowLevel;
200  bool IsRequired;
201
202  bool operator ==(const SimpleKey &Other) {
203    return Tok == Other.Tok;
204  }
205};
206}
207
208/// @brief The Unicode scalar value of a UTF-8 minimal well-formed code unit
209///        subsequence and the subsequence's length in code units (uint8_t).
210///        A length of 0 represents an error.
211typedef std::pair<uint32_t, unsigned> UTF8Decoded;
212
213static 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
263namespace llvm {
264namespace yaml {
265/// @brief Scans YAML tokens from a MemoryBuffer.
266class Scanner {
267public:
268  Scanner(StringRef Input, SourceMgr &SM, bool ShowColors = true);
269  Scanner(MemoryBufferRef Buffer, SourceMgr &SM_, bool ShowColors = true);
270
271  /// @brief Parse the next token and return it without popping it.
272  Token &peekNext();
273
274  /// @brief Parse the next token and pop it from the queue.
275  Token getNext();
276
277  void printError(SMLoc Loc, SourceMgr::DiagKind Kind, const Twine &Message,
278                  ArrayRef<SMRange> Ranges = None) {
279    SM.PrintMessage(Loc, Kind, Message, Ranges, /* FixIts= */ None, ShowColors);
280  }
281
282  void setError(const Twine &Message, StringRef::iterator Position) {
283    if (Current >= End)
284      Current = End - 1;
285
286    // Don't print out more errors after the first one we encounter. The rest
287    // are just the result of the first, and have no meaning.
288    if (!Failed)
289      printError(SMLoc::getFromPointer(Current), SourceMgr::DK_Error, Message);
290    Failed = true;
291  }
292
293  void setError(const Twine &Message) {
294    setError(Message, Current);
295  }
296
297  /// @brief Returns true if an error occurred while parsing.
298  bool failed() {
299    return Failed;
300  }
301
302private:
303  void init(MemoryBufferRef Buffer);
304
305  StringRef currentInput() {
306    return StringRef(Current, End - Current);
307  }
308
309  /// @brief Decode a UTF-8 minimal well-formed code unit subsequence starting
310  ///        at \a Position.
311  ///
312  /// If the UTF-8 code units starting at Position do not form a well-formed
313  /// code unit subsequence, then the Unicode scalar value is 0, and the length
314  /// is 0.
315  UTF8Decoded decodeUTF8(StringRef::iterator Position) {
316    return ::decodeUTF8(StringRef(Position, End - Position));
317  }
318
319  // The following functions are based on the gramar rules in the YAML spec. The
320  // style of the function names it meant to closely match how they are written
321  // in the spec. The number within the [] is the number of the grammar rule in
322  // the spec.
323  //
324  // See 4.2 [Production Naming Conventions] for the meaning of the prefixes.
325  //
326  // c-
327  //   A production starting and ending with a special character.
328  // b-
329  //   A production matching a single line break.
330  // nb-
331  //   A production starting and ending with a non-break character.
332  // s-
333  //   A production starting and ending with a white space character.
334  // ns-
335  //   A production starting and ending with a non-space character.
336  // l-
337  //   A production matching complete line(s).
338
339  /// @brief Skip a single nb-char[27] starting at Position.
340  ///
341  /// A nb-char is 0x9 | [0x20-0x7E] | 0x85 | [0xA0-0xD7FF] | [0xE000-0xFEFE]
342  ///                  | [0xFF00-0xFFFD] | [0x10000-0x10FFFF]
343  ///
344  /// @returns The code unit after the nb-char, or Position if it's not an
345  ///          nb-char.
346  StringRef::iterator skip_nb_char(StringRef::iterator Position);
347
348  /// @brief Skip a single b-break[28] starting at Position.
349  ///
350  /// A b-break is 0xD 0xA | 0xD | 0xA
351  ///
352  /// @returns The code unit after the b-break, or Position if it's not a
353  ///          b-break.
354  StringRef::iterator skip_b_break(StringRef::iterator Position);
355
356  /// Skip a single s-space[31] starting at Position.
357  ///
358  /// An s-space is 0x20
359  ///
360  /// @returns The code unit after the s-space, or Position if it's not a
361  ///          s-space.
362  StringRef::iterator skip_s_space(StringRef::iterator Position);
363
364  /// @brief Skip a single s-white[33] starting at Position.
365  ///
366  /// A s-white is 0x20 | 0x9
367  ///
368  /// @returns The code unit after the s-white, or Position if it's not a
369  ///          s-white.
370  StringRef::iterator skip_s_white(StringRef::iterator Position);
371
372  /// @brief Skip a single ns-char[34] starting at Position.
373  ///
374  /// A ns-char is nb-char - s-white
375  ///
376  /// @returns The code unit after the ns-char, or Position if it's not a
377  ///          ns-char.
378  StringRef::iterator skip_ns_char(StringRef::iterator Position);
379
380  typedef StringRef::iterator (Scanner::*SkipWhileFunc)(StringRef::iterator);
381  /// @brief Skip minimal well-formed code unit subsequences until Func
382  ///        returns its input.
383  ///
384  /// @returns The code unit after the last minimal well-formed code unit
385  ///          subsequence that Func accepted.
386  StringRef::iterator skip_while( SkipWhileFunc Func
387                                , StringRef::iterator Position);
388
389  /// Skip minimal well-formed code unit subsequences until Func returns its
390  /// input.
391  void advanceWhile(SkipWhileFunc Func);
392
393  /// @brief Scan ns-uri-char[39]s starting at Cur.
394  ///
395  /// This updates Cur and Column while scanning.
396  ///
397  /// @returns A StringRef starting at Cur which covers the longest contiguous
398  ///          sequence of ns-uri-char.
399  StringRef scan_ns_uri_char();
400
401  /// @brief Consume a minimal well-formed code unit subsequence starting at
402  ///        \a Cur. Return false if it is not the same Unicode scalar value as
403  ///        \a Expected. This updates \a Column.
404  bool consume(uint32_t Expected);
405
406  /// @brief Skip \a Distance UTF-8 code units. Updates \a Cur and \a Column.
407  void skip(uint32_t Distance);
408
409  /// @brief Return true if the minimal well-formed code unit subsequence at
410  ///        Pos is whitespace or a new line
411  bool isBlankOrBreak(StringRef::iterator Position);
412
413  /// Consume a single b-break[28] if it's present at the current position.
414  ///
415  /// Return false if the code unit at the current position isn't a line break.
416  bool consumeLineBreakIfPresent();
417
418  /// @brief If IsSimpleKeyAllowed, create and push_back a new SimpleKey.
419  void saveSimpleKeyCandidate( TokenQueueT::iterator Tok
420                             , unsigned AtColumn
421                             , bool IsRequired);
422
423  /// @brief Remove simple keys that can no longer be valid simple keys.
424  ///
425  /// Invalid simple keys are not on the current line or are further than 1024
426  /// columns back.
427  void removeStaleSimpleKeyCandidates();
428
429  /// @brief Remove all simple keys on FlowLevel \a Level.
430  void removeSimpleKeyCandidatesOnFlowLevel(unsigned Level);
431
432  /// @brief Unroll indentation in \a Indents back to \a Col. Creates BlockEnd
433  ///        tokens if needed.
434  bool unrollIndent(int ToColumn);
435
436  /// @brief Increase indent to \a Col. Creates \a Kind token at \a InsertPoint
437  ///        if needed.
438  bool rollIndent( int ToColumn
439                 , Token::TokenKind Kind
440                 , TokenQueueT::iterator InsertPoint);
441
442  /// @brief Skip a single-line comment when the comment starts at the current
443  /// position of the scanner.
444  void skipComment();
445
446  /// @brief Skip whitespace and comments until the start of the next token.
447  void scanToNextToken();
448
449  /// @brief Must be the first token generated.
450  bool scanStreamStart();
451
452  /// @brief Generate tokens needed to close out the stream.
453  bool scanStreamEnd();
454
455  /// @brief Scan a %BLAH directive.
456  bool scanDirective();
457
458  /// @brief Scan a ... or ---.
459  bool scanDocumentIndicator(bool IsStart);
460
461  /// @brief Scan a [ or { and generate the proper flow collection start token.
462  bool scanFlowCollectionStart(bool IsSequence);
463
464  /// @brief Scan a ] or } and generate the proper flow collection end token.
465  bool scanFlowCollectionEnd(bool IsSequence);
466
467  /// @brief Scan the , that separates entries in a flow collection.
468  bool scanFlowEntry();
469
470  /// @brief Scan the - that starts block sequence entries.
471  bool scanBlockEntry();
472
473  /// @brief Scan an explicit ? indicating a key.
474  bool scanKey();
475
476  /// @brief Scan an explicit : indicating a value.
477  bool scanValue();
478
479  /// @brief Scan a quoted scalar.
480  bool scanFlowScalar(bool IsDoubleQuoted);
481
482  /// @brief Scan an unquoted scalar.
483  bool scanPlainScalar();
484
485  /// @brief Scan an Alias or Anchor starting with * or &.
486  bool scanAliasOrAnchor(bool IsAlias);
487
488  /// @brief Scan a block scalar starting with | or >.
489  bool scanBlockScalar(bool IsLiteral);
490
491  /// Scan a chomping indicator in a block scalar header.
492  char scanBlockChompingIndicator();
493
494  /// Scan an indentation indicator in a block scalar header.
495  unsigned scanBlockIndentationIndicator();
496
497  /// Scan a block scalar header.
498  ///
499  /// Return false if an error occurred.
500  bool scanBlockScalarHeader(char &ChompingIndicator, unsigned &IndentIndicator,
501                             bool &IsDone);
502
503  /// Look for the indentation level of a block scalar.
504  ///
505  /// Return false if an error occurred.
506  bool findBlockScalarIndent(unsigned &BlockIndent, unsigned BlockExitIndent,
507                             unsigned &LineBreaks, bool &IsDone);
508
509  /// Scan the indentation of a text line in a block scalar.
510  ///
511  /// Return false if an error occurred.
512  bool scanBlockScalarIndent(unsigned BlockIndent, unsigned BlockExitIndent,
513                             bool &IsDone);
514
515  /// @brief Scan a tag of the form !stuff.
516  bool scanTag();
517
518  /// @brief Dispatch to the next scanning function based on \a *Cur.
519  bool fetchMoreTokens();
520
521  /// @brief The SourceMgr used for diagnostics and buffer management.
522  SourceMgr &SM;
523
524  /// @brief The original input.
525  MemoryBufferRef InputBuffer;
526
527  /// @brief The current position of the scanner.
528  StringRef::iterator Current;
529
530  /// @brief The end of the input (one past the last character).
531  StringRef::iterator End;
532
533  /// @brief Current YAML indentation level in spaces.
534  int Indent;
535
536  /// @brief Current column number in Unicode code points.
537  unsigned Column;
538
539  /// @brief Current line number.
540  unsigned Line;
541
542  /// @brief How deep we are in flow style containers. 0 Means at block level.
543  unsigned FlowLevel;
544
545  /// @brief Are we at the start of the stream?
546  bool IsStartOfStream;
547
548  /// @brief Can the next token be the start of a simple key?
549  bool IsSimpleKeyAllowed;
550
551  /// @brief True if an error has occurred.
552  bool Failed;
553
554  /// @brief Should colors be used when printing out the diagnostic messages?
555  bool ShowColors;
556
557  /// @brief Queue of tokens. This is required to queue up tokens while looking
558  ///        for the end of a simple key. And for cases where a single character
559  ///        can produce multiple tokens (e.g. BlockEnd).
560  TokenQueueT TokenQueue;
561
562  /// @brief Indentation levels.
563  SmallVector<int, 4> Indents;
564
565  /// @brief Potential simple keys.
566  SmallVector<SimpleKey, 4> SimpleKeys;
567};
568
569} // end namespace yaml
570} // end namespace llvm
571
572/// encodeUTF8 - Encode \a UnicodeScalarValue in UTF-8 and append it to result.
573static 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
601bool 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
685bool 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
698std::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
761Scanner::Scanner(StringRef Input, SourceMgr &sm, bool ShowColors)
762    : SM(sm), ShowColors(ShowColors) {
763  init(MemoryBufferRef(Input, "YAML"));
764}
765
766Scanner::Scanner(MemoryBufferRef Buffer, SourceMgr &SM_, bool ShowColors)
767    : SM(SM_), ShowColors(ShowColors) {
768  init(Buffer);
769}
770
771void 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
787Token &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
814Token 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
829StringRef::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
854StringRef::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
868StringRef::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
876StringRef::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
884StringRef::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
892StringRef::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
903void Scanner::advanceWhile(SkipWhileFunc Func) {
904  auto Final = skip_while(Func, Current);
905  Column += Final - Current;
906  Current = Final;
907}
908
909static 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
915static bool is_ns_word_char(const char C) {
916  return    C == '-'
917         || (C >= 'a' && C <= 'z')
918         || (C >= 'A' && C <= 'Z');
919}
920
921StringRef 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
941bool 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
956void Scanner::skip(uint32_t Distance) {
957  Current += Distance;
958  Column += Distance;
959  assert(Current <= End && "Skipped past the end");
960}
961
962bool Scanner::isBlankOrBreak(StringRef::iterator Position) {
963  if (Position == End)
964    return false;
965  return *Position == ' ' || *Position == '\t' || *Position == '\r' ||
966         *Position == '\n';
967}
968
969bool 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
979void 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
993void 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
1006void Scanner::removeSimpleKeyCandidatesOnFlowLevel(unsigned Level) {
1007  if (!SimpleKeys.empty() && (SimpleKeys.end() - 1)->FlowLevel == Level)
1008    SimpleKeys.pop_back();
1009}
1010
1011bool 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
1027bool 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
1044void 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
1058void 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
1079bool 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
1092bool 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
1110bool 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
1142bool 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
1155bool 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
1172bool 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
1186bool 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
1197bool 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
1209bool 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
1224bool 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.
1260LLVM_ATTRIBUTE_NOINLINE static bool
1261wasEscaped(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.
1265static 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
1277bool 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
1334bool 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
1412bool 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
1447char 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.
1460static 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
1470unsigned 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
1479bool 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
1507bool 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
1554bool 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
1584bool 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
1649bool 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
1677bool 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
1769Stream::Stream(StringRef Input, SourceMgr &SM, bool ShowColors)
1770    : scanner(new Scanner(Input, SM, ShowColors)), CurrentDoc() {}
1771
1772Stream::Stream(MemoryBufferRef InputBuffer, SourceMgr &SM, bool ShowColors)
1773    : scanner(new Scanner(InputBuffer, SM, ShowColors)), CurrentDoc() {}
1774
1775Stream::~Stream() {}
1776
1777bool Stream::failed() { return scanner->failed(); }
1778
1779void Stream::printError(Node *N, const Twine &Msg) {
1780  scanner->printError( N->getSourceRange().Start
1781                     , SourceMgr::DK_Error
1782                     , Msg
1783                     , N->getSourceRange());
1784}
1785
1786document_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
1797document_iterator Stream::end() {
1798  return document_iterator();
1799}
1800
1801void Stream::skip() {
1802  for (document_iterator i = begin(), e = end(); i != e; ++i)
1803    i->skip();
1804}
1805
1806Node::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
1813std::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
1858Token &Node::peekNext() {
1859  return Doc->peekNext();
1860}
1861
1862Token Node::getNext() {
1863  return Doc->getNext();
1864}
1865
1866Node *Node::parseBlockNode() {
1867  return Doc->parseBlockNode();
1868}
1869
1870BumpPtrAllocator &Node::getAllocator() {
1871  return Doc->NodeAllocator;
1872}
1873
1874void Node::setError(const Twine &Msg, Token &Tok) const {
1875  Doc->setError(Msg, Tok);
1876}
1877
1878bool Node::failed() const {
1879  return Doc->failed();
1880}
1881
1882
1883
1884StringRef 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
1917StringRef 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
2060Node *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
2085Node *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
2120void 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
2174void 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
2260Document::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
2272bool 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
2288Token &Document::peekNext() {
2289  return stream.scanner->peekNext();
2290}
2291
2292Token Document::getNext() {
2293  return stream.scanner->getNext();
2294}
2295
2296void Document::setError(const Twine &Message, Token &Location) const {
2297  stream.scanner->setError(Message, Location.Range.begin());
2298}
2299
2300bool Document::failed() const {
2301  return stream.scanner->failed();
2302}
2303
2304Node *Document::parseBlockNode() {
2305  Token T = peekNext();
2306  // Handle properties.
2307  Token AnchorInfo;
2308  Token TagInfo;
2309parse_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
2407bool 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
2423void Document::parseYAMLDirective() {
2424  getNext(); // Eat %YAML <version>
2425}
2426
2427void 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
2438bool 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