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