LCOV - code coverage report
Current view: top level - lib/Support - YAMLParser.cpp (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 1119 1306 85.7 %
Date: 2017-09-14 15:23:50 Functions: 84 94 89.4 %
Legend: Lines: hit not hit

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

Generated by: LCOV version 1.13