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