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