YAML: Implement block scalar parsing

[arphaman]

Summary

This patch implements the parsing of YAML block scalars. Some code existed there before, but it couldn't parse block scalars.
This patch is based on the patch 'http://reviews.llvm.org/D9448' that enables the YAMLParser tests.
I've added a new yaml node type to represent the block scalar values.
I've deleted the files 'spec-09-27.test' and 'spec-09-28.test' as they are identical to the file 'spec-09-26.test'.

[arphaman]

As suggested by Duncan, I took out the extraction of the skipComment method from this patch,
which I've committed separately in r236663. I also took out the change to the KeyValueNode skip method,
which I've committed separately in r236669.

[arphaman]

I've applied Duncan's suggestions to this patch:

• Got rid of line folding, it will go into a separate patch.
• Refactored and extracted functions that scan block scalar header, chomping indicator, indent indicator, search for block's indentation and scan the block indentation.
• Added helper functions advanceWhile, consumeLineBreakIfPresent and applyChompingIndicator.
• Decided to keep the name Start instead of renaming it to BlockStart.
• Used a SmallString instead of an output stream.
• Asserted that the first character is either an '|' or '>'.

[arphaman]

This update uses a new helper function that consumes a line break in another part of code that I forgot to update last time.

[arphaman]

I've updated the patch taking Duncan's suggestions into account.

include/llvm/Support/YAMLParser.h

   enum NodeKind {
     NK_Null,
     NK_Scalar,
+    NK_BlockScalar,
     NK_KeyValue,
     NK_Mapping,
     NK_Sequence,

                                  SmallVectorImpl<char> &Storage) const;
 };
 
+/// \brief A block scalar node is an opaque datum that can be presented as a
+///        series of zero or more Unicode scalar values.
+///
+/// Example:
+///   |
+///     Hello
+///     World
+class BlockScalarNode : public Node {
+  void anchor() override;
+
+public:
+  BlockScalarNode(std::unique_ptr<Document> &D, StringRef Anchor, StringRef Tag,
+                  std::string &Value, StringRef RawVal)
+      : Node(NK_BlockScalar, D, Anchor, Tag), Value(std::move(Value)) {
+    SMLoc Start = SMLoc::getFromPointer(RawVal.begin());
+    SMLoc End = SMLoc::getFromPointer(RawVal.end());
+    SourceRange = SMRange(Start, End);
+  }
+
+  /// \brief Gets the value of this node as a StringRef.
+  StringRef getValue() const { return Value; }
+
+  static inline bool classof(const Node *N) {
+    return N->getType() == NK_BlockScalar;
+  }
+
+private:
+  std::string Value;
+};
+
 /// \brief A key and value pair. While not technically a Node under the YAML
 ///        representation graph, it is easier to treat them this way.
 ///

lib/Support/YAMLParser.cpp

 void Node::anchor() {}
 void NullNode::anchor() {}
 void ScalarNode::anchor() {}
+void BlockScalarNode::anchor() {}
 void KeyValueNode::anchor() {}
 void MappingNode::anchor() {}
 void SequenceNode::anchor() {}

     TK_Key,
     TK_Value,
     TK_Scalar,
+    TK_BlockScalar,
     TK_Alias,
     TK_Anchor,
     TK_Tag

   /// of the token in the input.
   StringRef Range;
 
+  /// The value of a block scalar node.
+  std::string Value;
+
   Token() : Kind(TK_Error) {}
 };
 }

   ///          b-break.
   StringRef::iterator skip_b_break(StringRef::iterator Position);
 
+  /// @brief Skip a single s-space[31] starting at Position.
+  ///
+  /// An s-space is 0x20
+  ///
+  /// @returns The code unit after the s-space, or Position if it's not a
+  ///          s-space.
+  StringRef::iterator skip_s_space(StringRef::iterator Position);
+
   /// @brief Skip a single s-white[33] starting at Position.
   ///
   /// A s-white is 0x20 | 0x9

   StringRef::iterator skip_while( SkipWhileFunc Func
                                 , StringRef::iterator Position);
 
+  /// @brief Skip minimal well-formed code unit subsequences until Func
+  ///        returns its input.
+  ///
+  /// @returns The code unit after the last minimal well-formed code unit
+  ///          subsequence that Func accepted.
+  void advanceWhile(SkipWhileFunc Func);
+
   /// @brief Scan ns-uri-char[39]s starting at Cur.
   ///
   /// This updates Cur and Column while scanning.

   ///        Pos is whitespace or a new line
   bool isBlankOrBreak(StringRef::iterator Position);
 
+  /// @brief Consume a single b-break[28] if it's present at the current
+  /// position. Return false if the code unit at the current position ins't a
+  /// line break.
+  bool consumeLineBreakIfPresent();
+
   /// @brief If IsSimpleKeyAllowed, create and push_back a new SimpleKey.
   void saveSimpleKeyCandidate( TokenQueueT::iterator Tok
                              , unsigned AtColumn

   /// @brief Scan a block scalar starting with | or >.
   bool scanBlockScalar(bool IsLiteral);
 
+  /// @brief Scan a chomping indicator in a block scalar header.
+  char scanBlockChompingIndicator();
+
+  /// @brief Scan an indentation indicator in a block scalar header.
+  unsigned scanBlockIndentationIndicator();
+
+  /// @brief Scan a block scalar header.
+  /// Return true if we've reached the end of the block scalar.
+  bool scanBlockScalarHeader(char &ChompingIndicator, unsigned &IndentIndicator,
+                             bool &WasScanningSuccessful);
+
+  /// @brief Look for the indentation level of a block scalar.
+  /// Return true if we've reached the end of the block scalar.
+  bool findBlockScalarIndent(unsigned &BlockIndent, unsigned BlockExitIndent,
+                             unsigned &LineBreaks);
+
+  /// @brief Scan the indentation of a text line in a block scalar.
+  /// Return true if we've reached the end of the block scalar.
+  bool scanBlockScalarIndent(unsigned BlockIndent, unsigned BlockExitIndent);
+
   /// @brief Scan a tag of the form !stuff.
   bool scanTag();
 

     case Token::TK_Scalar:
       OS << "Scalar: ";
       break;
+    case Token::TK_BlockScalar:
+      OS << "Block Scalar: ";
+      break;
     case Token::TK_Alias:
       OS << "Alias: ";
       break;

   return Position;
 }
 
+StringRef::iterator Scanner::skip_s_space(StringRef::iterator Position) {
+  if (Position == End)
+    return Position;
+  if (*Position == ' ')
+    return Position + 1;
+  return Position;
+}
 
 StringRef::iterator Scanner::skip_s_white(StringRef::iterator Position) {
   if (Position == End)

   return Position;
 }
 
+void Scanner::advanceWhile(SkipWhileFunc Func) {
+  auto Final = skip_while(Func, Current);
+  Column += Final - Current;
+  Current = Final;
+}
+
 static bool is_ns_hex_digit(const char C) {
   return    (C >= '0' && C <= '9')
          || (C >= 'a' && C <= 'z')

   return false;
 }
 
+bool Scanner::consumeLineBreakIfPresent() {
+  auto Next = skip_b_break(Current);
+  if (Next == Current)
+    return false;
+  Column = 0;
+  ++Line;
+  Current = Next;
+  return true;
+}
+
 void Scanner::saveSimpleKeyCandidate( TokenQueueT::iterator Tok
                                     , unsigned AtColumn
                                     , bool IsRequired) {

   return true;
 }
 
-bool Scanner::scanBlockScalar(bool IsLiteral) {
-  StringRef::iterator Start = Current;
-  skip(1); // Eat | or >
-  while(true) {
-    StringRef::iterator i = skip_nb_char(Current);
-    if (i == Current) {
-      if (Column == 0)
-        break;
-      i = skip_b_break(Current);
-      if (i != Current) {
-        // We got a line break.
-        Column = 0;
-        ++Line;
-        Current = i;
-        continue;
+char Scanner::scanBlockChompingIndicator() {
+  char Indicator = ' ';
+  if (Current != End && (*Current == '+' || *Current == '-')) {
+    Indicator = *Current;
+    skip(1);
+  }
+  return Indicator;
+}
+
+/// \brief Return the number of trailing line breaks that have to be emitted
+/// as determined by the chomping indicator.
+static unsigned applyChompingIndicator(char ChompingIndicator,
+                                       unsigned LineBreaks, StringRef Str) {
+  // Don't output any trailing new lines if the stripping chomping behaviour is
+  // specified.
+  if (ChompingIndicator == '-')
+    return 0;
+  // Keep trailing lines when the keep chomping behaviour is specified.
+  else if (ChompingIndicator == '+')
+    return LineBreaks;
+  // Clip trailing lines (default chomping behaviour). The final line break
+  // is preserved as long as the string isn't empty, but the other trailing
+  // lines aren't kept.
+  return Str.empty() ? 0 : 1;
+}
+
+unsigned Scanner::scanBlockIndentationIndicator() {
+  unsigned Indent = 0;
+  if (Current != End && (*Current >= '1' && *Current <= '9')) {
+    Indent = unsigned(*Current - '0');
+    skip(1);
+  }
+  return Indent;
+}
+
+bool Scanner::scanBlockScalarHeader(char &ChompingIndicator,
+                                    unsigned &IndentIndicator,
+                                    bool &WasScanningSuccessful) {
+  // Chomping indicator ([164] c-chomping-indicator)
+  ChompingIndicator = scanBlockChompingIndicator();
+  // Indentation indicator ([163] c-indentation-indicator)
+  IndentIndicator = scanBlockIndentationIndicator();
+  // Check for the chomping indicator once again.
+  if (ChompingIndicator == ' ')
+    ChompingIndicator = scanBlockChompingIndicator();
+  Current = skip_while(&Scanner::skip_s_white, Current);
+  skipComment();
+
+  if (Current == End) {
+    // End of file after block header, we have an empty scalar.
+    WasScanningSuccessful = true;
+    return true;
+  }
+  auto I = skip_b_break(Current);
+  if (I == Current) {
+    setError("Expected a line break after block scalar header", Current);
+    WasScanningSuccessful = false;
+    return true;
+  }
+  Current = I;
+  Column = 0;
+  ++Line;
+  return false;
+}
+
+bool Scanner::findBlockScalarIndent(unsigned &BlockIndent,
+                                    unsigned BlockExitIndent,
+                                    unsigned &LineBreaks) {
+  unsigned MaxAllSpaceLineCharacters = 0;
+  StringRef::iterator LongestAllSpaceLine;
+
+  while (true) {
+    advanceWhile(&Scanner::skip_s_space);
+    // If there is a non breaking character next, then this is a non empty
+    // line, thus we can use the discovered indentation as the block's
+    // indentation.
+    if (skip_nb_char(Current) != Current) {
+      if (Column <= BlockExitIndent) {
+        // This is the end of the block literal
+        return true;
       } else {
-        // There was an error, which should already have been printed out.
-        return false;
+        BlockIndent = Column;
+        // So here we enforce the rule that the leading all space lines can't
+        // have more characters than the block's indentation level
+        if (MaxAllSpaceLineCharacters > BlockIndent) {
+          setError("A leading all-space line must not have too many spaces",
+                   LongestAllSpaceLine);
+        }
+        // We found the block's indentation.
+        break;
+      }
+    } else if (skip_b_break(Current) != Current) {
+      // This is an all space line, so we have to record the amount of
+      // space characters it has so that later when we find the first
+      // text line that defines the indentation level we can make sure
+      // that all previous all space lines don't have more space
+      // characters than the indentation level.
+      if (Column > MaxAllSpaceLineCharacters) {
+        MaxAllSpaceLineCharacters = Column;
+        LongestAllSpaceLine = Current;
       }
     }
-    Current = i;
+
+    // Check for EOF.
+    if (Current == End)
+      return true;
+
+    if (!consumeLineBreakIfPresent())
+      return true;
+    ++LineBreaks;
+  }
+  return false;
+}
+
+bool Scanner::scanBlockScalarIndent(unsigned BlockIndent,
+                                    unsigned BlockExitIndent) {
+  // Skip the indentation.
+  while (Column < BlockIndent) {
+    auto I = skip_s_space(Current);
+    if (I == Current)
+      break;
+    Current = I;
     ++Column;
   }
 
-  if (Start == Current) {
-    setError("Got empty block scalar", Start);
-    return false;
+  // If this line isn't empty then we have to check the indentation to
+  // see if the block scalar ends.
+  if (skip_nb_char(Current) != Current) {
+    if (Column <= BlockExitIndent) {
+      // This is the end of the block literal
+      return true;
+    } else if (Column < BlockIndent) {
+      if (Current != End && *Current == '#') {
+        // This is a trailing comment
+        return true;
+      } else {
+        setError("A text line is less indented than the block scalar", Current);
+      }
+    }
+  }
+  return false;
+}
+
+bool Scanner::scanBlockScalar(bool IsLiteral) {
+  auto Start = Current;
+  // Eat '|' or '>'
+  assert(*Current == '|' || *Current == '>');
+  skip(1);
+
+  // Block Header ([162] c-b-block-header)
+  char ChompingIndicator;
+  unsigned BlockIndent;
+  bool WasScanningSuccessful;
+  bool Done = scanBlockScalarHeader(ChompingIndicator, BlockIndent,
+                                    WasScanningSuccessful);
+  if (Done) {
+    if (WasScanningSuccessful) {
+      Token T;
+      T.Kind = Token::TK_BlockScalar;
+      T.Range = StringRef(Start, Current - Start);
+      TokenQueue.push_back(T);
+    }
+    return WasScanningSuccessful;
+  }
+  Start = Current;
+
+  // Look for a first non-blank line to determine the indenation of the block
+  // scalar.
+  unsigned BlockExitIndent = Indent < 0 ? 0 : (unsigned)Indent;
+  unsigned LineBreaks = 0;
+  if (BlockIndent == 0)
+    Done = findBlockScalarIndent(BlockIndent, BlockExitIndent, LineBreaks);
+
+  // Scan the block's scalars body.
+  SmallString<256> Str;
+  while (!Done) {
+    // Handle the block's indentation
+    if (scanBlockScalarIndent(BlockIndent, BlockExitIndent))
+      break;
+
+    // Parse the current line.
+    auto LineStart = Current;
+    advanceWhile(&Scanner::skip_nb_char);
+    if (LineStart != Current) {
+      for (unsigned I = 0; I < LineBreaks; ++I)
+        Str.push_back('\n');
+      LineBreaks = 0;
+      Str.append(StringRef(LineStart, Current - LineStart));
+    }
+
+    // Check for EOF.
+    if (Current == End)
+      break;
+
+    if (!consumeLineBreakIfPresent())
+      break;
+    ++LineBreaks;
   }
 
+  if (Current == End && !LineBreaks)
+    // Ensure that there is at least one line break before the end of file.
+    LineBreaks = 1;
+  LineBreaks = applyChompingIndicator(ChompingIndicator, LineBreaks, Str);
+  for (unsigned I = 0; I < LineBreaks; ++I)
+    Str.push_back('\n');
+
+  // New lines may start a simple key.
+  if (!FlowLevel)
+    IsSimpleKeyAllowed = true;
+
   Token T;
-  T.Kind = Token::TK_Scalar;
+  T.Kind = Token::TK_BlockScalar;
   T.Range = StringRef(Start, Current - Start);
+  T.Value = std::move(Str.str().str());
   TokenQueue.push_back(T);
   return true;
 }

   case NK_Null:
     return "tag:yaml.org,2002:null";
   case NK_Scalar:
+  case NK_BlockScalar:
     // TODO: Tag resolution.
     return "tag:yaml.org,2002:str";
   case NK_Mapping:

                 , AnchorInfo.Range.substr(1)
                 , TagInfo.Range
                 , T.Range);
+  case Token::TK_BlockScalar:
+    getNext();
+    return new (NodeAllocator)
+        BlockScalarNode(stream.CurrentDoc, AnchorInfo.Range.substr(1),
+                        TagInfo.Range, T.Value, T.Range);
   case Token::TK_Key:
     // Don't eat the TK_Key, KeyValueNode expects it.
     return new (NodeAllocator)

test/YAMLParser/spec-09-14.test

-# RUN: yaml-bench -canonical %s 2>&1 | FileCheck %s
+# RUN: not yaml-bench -canonical %s 2>&1 | FileCheck %s
 #
-# FIXME: This test should actually fail. Yaml bench should report an error that
-# says that the '---' and '...' document start/end markers must not be specified
-# as the first content line of a non-indented plain scalar.
-# CHECK: !!str
+# CHECK: error: Expected a line break after block scalar header
 
 ---
 --- ||| : foo

test/YAMLParser/spec-09-18.test

-# RUN: yaml-bench -canonical %s
+# RUN: yaml-bench -canonical %s | FileCheck %s
+# CHECK: !!str "literal\n"
+# CHECK: !!str " folded\n"
+# CHECK: !!str "keep\n\n"
+# CHECK: !!str " strip"
 
 - | # Just the style
  literal

test/YAMLParser/spec-09-19.test

-# RUN: yaml-bench -canonical %s
+# RUN: yaml-bench -canonical %s | FileCheck %s
+# CHECK: !!str "literal\n"
+# CHECK: !!str "folded\n"
 
 - |
  literal

test/YAMLParser/spec-09-20.test

-# RUN: yaml-bench -canonical %s
+# RUN: yaml-bench -canonical %s | FileCheck %s
+# CHECK: !!str "detected\n"
+# CHECK: !!str "\n\n# detected\n"
+# CHECK: !!str " explicit\n"
+# CHECK: !!str "\t\ndetected\n"
 
 - |
  detected

test/YAMLParser/spec-09-21.test

 - |1
  text
 
-# CHECK: error
+# CHECK: 8:2: error: A text line is less indented than the block scalar

test/YAMLParser/spec-09-22.test

-# RUN: yaml-bench -canonical %s
+# RUN: yaml-bench -canonical %s | FileCheck %s
+# CHECK: !!str "text"
+# CHECK: !!str "text\n"
+# CHECK: !!str "text\n\n"
 
 strip: |-
-  text
clip: |
-  text…keep: |+
-  text

+  text
+clip: |
+  text
+keep: |+
+  text
+

test/YAMLParser/spec-09-24.test

-# RUN: yaml-bench -canonical %s
+# RUN: yaml-bench -canonical %s | FileCheck %s
+# CHECK: ? !!str "strip"
+# CHECK: : !!str ""
+# CHECK: ? !!str "clip"
+# CHECK: : !!str ""
+# CHECK: ? !!str "keep"
+# CHECK: : !!str "\n"
 
 strip: >-
 
 clip: >
 
 keep: |+
-

test/YAMLParser/spec-09-25.test

-# RUN: yaml-bench -canonical %s
+# RUN: yaml-bench -canonical %s | FileCheck %s
+# CHECK: !!str "literal\n\ttext\n"
 
 | # Simple block scalar
  literal

test/YAMLParser/spec-09-26.test

-# RUN: yaml-bench -canonical %s
+# RUN: yaml-bench -canonical %s | FileCheck %s
+# CHECK: !!str "\n\nliteral\n\ntext\n"
 
 |
  

test/YAMLParser/spec-09-27.test

-# RUN: yaml-bench -canonical %s
-
-|
- 
-  
-  literal
- 
-  text
-
- # Comment

test/YAMLParser/spec-09-28.test

-# RUN: yaml-bench -canonical %s
-
-|
- 
-  
-  literal
- 
-  text
-
- # Comment

unittests/Support/YAMLParserTest.cpp

   ExpectParseSuccess("Array of arrays", "[[]]");
 }
 
+TEST(YAMLParser, ParsesBlockLiteralScalars) {
+  ExpectParseSuccess("Block literal scalar", "test: |\n  Hello\n  World\n");
+  ExpectParseSuccess("Block literal scalar EOF", "test: |\n  Hello\n  World");
+  ExpectParseSuccess("Empty block literal scalar header EOF", "test: | ");
+  ExpectParseSuccess("Empty block literal scalar", "test: |\ntest2: 20");
+  ExpectParseSuccess("Empty block literal scalar 2", "- | \n  \n\n \n- 42");
+  ExpectParseSuccess("Block literal scalar in sequence",
+                     "- |\n  Testing\n  Out\n\n- 22");
+  ExpectParseSuccess("Block literal scalar in document",
+                     "--- |\n  Document\n...");
+  ExpectParseSuccess("Empty non indented lines still count",
+                     "- |\n  First line\n \n\n  Another line\n\n- 2");
+  ExpectParseSuccess("Comment in block literal scalar header",
+                     "test: | # Comment \n  No Comment\ntest 2: | # Void");
+  ExpectParseSuccess("Chomping indicators in block literal scalar header",
+                     "test: |- \n  Hello\n\ntest 2: |+ \n\n  World\n\n\n");
+  ExpectParseSuccess("Indent indicators in block literal scalar header",
+                     "test: |1 \n  \n Hello \n  World\n");
+  ExpectParseSuccess("Chomping and indent indicators in block literals",
+                     "test: |-1\n Hello\ntest 2: |9+\n         World");
+  ExpectParseSuccess("Trailing comments in block literals",
+                     "test: |\n  Content\n # Trailing\n  #Comment\ntest 2: 3");
+  ExpectParseError("Invalid block scalar header", "test: | failure");
+  ExpectParseError("Invalid line indentation", "test: |\n  First line\n Error");
+  ExpectParseError("Long leading space line", "test: |\n   \n  Test\n");
+}
+
 TEST(YAMLParser, HandlesEndOfFileGracefully) {
   ExpectParseError("In string starting with EOF", "[\"");
   ExpectParseError("In string hitting EOF", "[\"   ");

utils/yaml-bench/YAMLBench.cpp

     SmallString<32> Storage;
     StringRef Val = sn->getValue(Storage);
     outs() << prettyTag(n) << " \"" << yaml::escape(Val) << "\"";
+  } else if (yaml::BlockScalarNode *BN = dyn_cast<yaml::BlockScalarNode>(n)) {
+    outs() << prettyTag(n) << " \"" << yaml::escape(BN->getValue()) << "\"";
   } else if (yaml::SequenceNode *sn = dyn_cast<yaml::SequenceNode>(n)) {
     outs() << prettyTag(n) << " [\n";
     ++Indent;