[YAMLParser] Add multi-line literal folding support

[HassanElDesouky]

Summary

Last year I was working at Swift to add support for Localization of Compiler Diagnostic Messages. We are currently using YAML as the new diagnostic format. The LLVM::YAMLParser didn't have a support for multiline string literal folding and it's crucial to have that for the diagnostic message to help us keep up with the 80 columns rule. Therefore, I decided to add a multiline string literal folding support to the YAML parser.

[HassanElDesouky]

Fixed clang-tidy warning

[fodinabor]

Not too deep into the YAML world, so just my two cents re the isLineBreak function.

llvm/lib/Support/YAMLParser.cpp

1049

shouldn't this rather be a check whether the line is _empty_ -> whether it contains anything else than \n\r\t ?
Currently, this does not support empty lines with spaces, multiple tabs or windows style line feeds \r\n.

This would be easily solvable by using something like:

for(auto Position = Line.begin(); Position != Line.end(); ++Position)
  if(!isBlankOrBreak(Position))
     return false;
return true;

Renaming the function to isLineEmpty might sense then, too.

[HassanElDesouky]

Resolved @fodinabor comment.

[HassanElDesouky]

In D102590#2793808, @fodinabor wrote:

Not too deep into the YAML world, so just my two cents re the isLineBreak function.

Thank you for the review! I changed the function as suggested.

[HassanElDesouky]

@silvas sorry for pinging you. but this has been in review since May 17th. Can you take a look at it when you have free time?

[silvas]

@HassanElDesouky sorry, I'm not that familiar with this code.

@Bigcheese can you PTAL?

[HassanElDesouky]

@dexonsmith Sorry for the ping, but this has been in review for so long. Can you review when you have the time?

[HassanElDesouky]

@silvas Do you know anyone who can review this? I really wanna this to get merged :(

[scott.linder]

I'm not sure I'm the best person for the job, but I tried to give my thoughts.

The only correctness issue I'm not certain about is the discussion around what constitutes an "empty" line. My understanding is that lines containing only whitespace can be non-empty, and that only the indent is stripped before checking if there is content in the line. @fodinabor do you have any links that describe your definition of empty? The docs I'm looking at are https://yaml.org/spec/1.2/spec.html#l-empty(n,c)

Other than that I believe your code as-is faithfully implements the YAML spec, but the approach you took doesn't match how I model it in my head, which makes it harder to review. I suggested a different approach that I'm more confident is correct (or at the very least, if it is incorrect it might help me identify the part of the spec I don't understand!)

Let me know what you think!

llvm/lib/Support/YAMLParser.cpp

1535

This appears to be dead, was it used previously?

1684

I'd rather hoist the call to isFoldedBlock up instead of juggling Start like this.

I think even better would be to replace isFoldedBlock with something like:

/// Scan a block scalar style indicator and header.
///
/// Note: This is distinct from scanBlockScalarHeader to mirror the fact that
/// YAML does not consider the style indicator to be a part of the header.
///
/// Return false if an error occurred.
bool scanBlockScalarIndicators(char &StyleIndicator, char &ChompingIndicator, unsigned &IndentIndicator, bool &IsDone);

Then the code here is:

bool Scanner::scanBlockScalar(bool IsLiteral) {
  char StyleIndicator;
  char ChompingIndicator;
  unsigned BlockIndent;
  bool IsDone;
  if (!scanBlockScalarIndicators(StyleIndicator, ChompingIndicator, BlockIndent, IsDone))
    return false;
  ...
  // Here you could do `bool IsFolded = StyleIndicator == '>';`

It would be even better to have this return actual enums instead of chars or bools:

enum BlockStyle { Literal; Folded; };
enum BlockChomping { ... };
bool scanBlockScalarIndicators(BlockStyle &Style, BlockChomping &Chomping, unsigned &Indent, bool &IsDone);

// Now code can check `if (Style == BlockStyle::Folded)`, which I think reads the best out of the options, with the bonus of type safety to catch typos.

I don't know if this case is enough reason to change the style of surrounding code to use enums though, so I'd be fine with the new scan method just accepting a bool& or char& for the style indicator and calling it a day. Do others have any thoughts?

1717–1742

I think this can be simplified if you just think of the folding as a special case at the point this loop encounters a line where LineStart != Current (i.e. a line with content). At that point, for literal blocks we just insert LineBreaks count of newlines as we did previously, whereas for folded blocks we do one of three things:

• If LineBreaks == 0 we don't append anything.
• If LineBreaks == 1 we append a single space (this is the "folding").
• Otherwise, we append LineBreaks - 1 newlines (this is the clause of YAML which allows you to get newlines into the final scalar string by using multiple adjacent newlines; the general case is that the first two newlines together get you into this "no folding" mode, then you can chain as many newlines as you want before encountering content again and going back to "folding" mode).

This avoids maintaining more state in checking the last character in Str, and it shows the common aspects of the two styles more clearly.

I'm not a YAML expert, though, so if I'm just wrong please correct me! This is just based on my understanding after skimming the relevant parts of the YAML spec.

[scott.linder]

So, I tried to work out the behavior of the spec parser, and I think my understanding of empty is faulty. Compare http://ben-kiki.org/ypaste/data/26953/index.html (all content is non-space characters) with http://ben-kiki.org/ypaste/data/26954/index.html (the middle line content is a single space).

The single space is still considered content (what I would expect), but somehow prevents the folding from occuring (not what I would expect). I think this lines up with @fodinabor definition of isLineEmpty? In that case, I think my suggestion would be:

if (LineStart != Current) {
  if (LineBreaks && IsFolded) {
    // The folded style "folds" any single line break between content into a single space, except when that
    // content is "empty" (only contains whitespace) in which case the line break is left as-is.
    if (LineBreaks == 1) {
      Str.append(LineBreaks, isLineEmpty(StringRef(LineStart, Current-LineStart)) ? '\n' : ' ');
    }
    // If we saw a single line break, we are completely replacing it and so want `LineBreaks == 0`.
    // Otherwise this decrement accounts for the fact that the first line break is "trimmed", only
    // being used to signal a sequence of line breaks which should not be folded.
    LineBreaks--;
  }
  Str.append(LineBreaks, '\n');
  Str.append(StringRef(LineStart, Current - LineStart));
  LineBreaks = 0;
}

[HassanElDesouky]

@scott.linder Thank you so much for the review!

1. I made the changes you pointed out regarding defining a new scanBlockScalarIndicators method.
2. I think the idea of enum BlockStyle and enum BlockChomping is really good. I will definitely implement it but maybe in another PR/diff. -- if that's okay :)
3. I'm afraid that your suggested code in regarding simplifying the logic behind folding is not correct. It doesn't work with folded scalars that has strip/clip. However, I tried my best to simplify the logic. If you have any other ideas let me know!

[scott.linder]

In D102590#2971046, @HassanElDesouky wrote:

@scott.linder Thank you so much for the review!

1. I made the changes you pointed out regarding defining a new scanBlockScalarIndicators method.
2. I think the idea of enum BlockStyle and enum BlockChomping is really good. I will definitely implement it but maybe in another PR/diff. -- if that's okay :)

Yes, that sounds great :)

3. I'm afraid that your suggested code in regarding simplifying the logic behind folding is not correct. It doesn't work with folded scalars that has strip/clip. However, I tried my best to simplify the logic. If you have any other ideas let me know!

I couldn't figure out exactly what was going wrong with my changes, and when I actually build my changes locally it seems to implement the strip/clip/keep as I'd expect. The existing tests don't cover all the combinations, and the contents changing between them makes it harder to compare, so I also updated the test. See the attached patch (which includes your changes, with my proposed edits), which you should be able to apply with git am

0001-Proposed-revisions-to-https-reviews.llvm.org-D102590.patch7 KBDownload

.
Can you let me know what I'm missing?

[njames93]

Apologies for this getting sidelined for so long.
Can the build failures be addressed please, it may just be a case of rebasing to trunk as I think the file causing the failures no longer exists on trunk.

[HassanElDesouky]

In D102590#3334023, @njames93 wrote:

Apologies for this getting sidelined for so long.
Can the build failures be addressed please, it may just be a case of rebasing to trunk as I think the file causing the failures no longer exists on trunk.

Yeah sure, I'll do it this weekend.

[HassanElDesouky]

I finally finished working on this. The tests have passed on Windows and the failure on Debian isn't related to my changes. Can we get this merged, please? 🚢
@scott.linder @njames93

[scott.linder]

LGTM, thank you!

[HassanElDesouky]

In D102590#3349470, @scott.linder wrote:

LGTM, thank you!

Thank you so much for your help last year! This is my very first commit in LLVM. I’m super happy right now 😄

[HassanElDesouky]

@scott.linder I don’t have a commit permission so I’d love it if you can commit it on my behalf. Thanks!

[scott.linder]

In D102590#3349510, @HassanElDesouky wrote:

@scott.linder I don’t have a commit permission so I’d love it if you can commit it on my behalf. Thanks!

Sure thing, I'll run a final check-all and commit it soon! Welcome to LLVM :)

llvm/include/llvm/Support/YAMLParser.h

 //===- YAMLParser.h - Simple YAML parser ------------------------*- C++ -*-===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 //
 //  This is a YAML 1.2 parser.
 //
 //  See http://www.yaml.org/spec/1.2/spec.html for the full standard.
 //
 //  This currently does not implement the following:
-//    * Multi-line literal folding.
 //    * Tag resolution.
 //    * UTF-16.
 //    * BOMs anywhere other than the first Unicode scalar value in the file.
 //
 //  The most important class here is Stream. This represents a YAML stream with
 //  0, 1, or many documents.
 //
 //  SourceMgr sm;

llvm/lib/Support/YAMLParser.cpp

private:
 
   /// Skip \a Distance UTF-8 code units. Updates \a Cur and \a Column.
   void skip(uint32_t Distance);
 
   /// Return true if the minimal well-formed code unit subsequence at
   ///        Pos is whitespace or a new line
   bool isBlankOrBreak(StringRef::iterator Position);
 
+  /// Return true if the line is a line break, false otherwise.
+  bool isLineBreak(StringRef Line);
+
   /// Consume a single b-break[28] if it's present at the current position.
   ///
   /// Return false if the code unit at the current position isn't a line break.
   bool consumeLineBreakIfPresent();
 
   /// If IsSimpleKeyAllowed, create and push_back a new SimpleKey.
   void saveSimpleKeyCandidate( TokenQueueT::iterator Tok
                              , unsigned AtColumn
private:
   bool scanPlainScalar();
 
   /// Scan an Alias or Anchor starting with * or &.
   bool scanAliasOrAnchor(bool IsAlias);
 
   /// Scan a block scalar starting with | or >.
   bool scanBlockScalar(bool IsLiteral);
 
+  /// Check if the scalar block is folded. If scalar is folded `NewlineOrSpace`
+  /// will be assigned to a space ` `.
+  ///
+  /// Return true if the `Position` start with `>`.
+  bool isFoldedBlock(StringRef::iterator Position, char &NewlineOrSpace,
+                     char ChompingIndicator);
+
   /// Scan a chomping indicator in a block scalar header.
   char scanBlockChompingIndicator();
 
   /// Scan an indentation indicator in a block scalar header.
   unsigned scanBlockIndentationIndicator();
 
   /// Scan a block scalar header.
   ///

 
 bool Scanner::isBlankOrBreak(StringRef::iterator Position) {
   if (Position == End)
     return false;
   return *Position == ' ' || *Position == '\t' || *Position == '\r' ||
          *Position == '\n';
 }
 
+bool Scanner::isLineBreak(StringRef Line) {
+  return Line == "\n" || Line == "\r" || Line == "\t\n";
+}
+
 bool Scanner::consumeLineBreakIfPresent() {
   auto Next = skip_b_break(Current);
   if (Next == Current)
     return false;
   Column = 0;
   ++Line;
   Current = Next;
   return true;
bool Scanner::scanAliasOrAnchor(bool IsAlias) {
   // Alias and anchors can be simple keys.
   saveSimpleKeyCandidate(--TokenQueue.end(), ColStart, false);
 
   IsSimpleKeyAllowed = false;
 
   return true;
 }
 
+bool Scanner::isFoldedBlock(StringRef::iterator Position, char &NewlineOrSpace,
+                            char ChompingIndicator) {
+  bool IsFolded = false;
+  if (*Position == '>') {
+    IsFolded = true;
+    NewlineOrSpace = ' ';
+  }
+  return IsFolded;
+}
+
 char Scanner::scanBlockChompingIndicator() {
   char Indicator = ' ';
   if (Current != End && (*Current == '+' || *Current == '-')) {
     Indicator = *Current;
     skip(1);
   }
   return Indicator;
 }
if (Column < BlockIndent) {
     return false;
   }
   return true; // A normal text line.
 }
 
 bool Scanner::scanBlockScalar(bool IsLiteral) {
   // Eat '|' or '>'
   assert(*Current == '|' || *Current == '>');
+  const auto *Start = Current;
   skip(1);
 
+  char NewlineOrSpace = '\n';
   char ChompingIndicator;
   unsigned BlockIndent;
   bool IsDone = false;
   if (!scanBlockScalarHeader(ChompingIndicator, BlockIndent, IsDone))
     return false;
   if (IsDone)
     return true;
+  bool IsFolded = isFoldedBlock(Start, NewlineOrSpace, ChompingIndicator);
 
-  auto Start = Current;
+  Start = Current;
   unsigned BlockExitIndent = Indent < 0 ? 0 : (unsigned)Indent;
   unsigned LineBreaks = 0;
   if (BlockIndent == 0) {
     if (!findBlockScalarIndent(BlockIndent, BlockExitIndent, LineBreaks,
                                IsDone))
       return false;
   }
 
   // Scan the block's scalars body.
   SmallString<256> Str;
   while (!IsDone) {
     if (!scanBlockScalarIndent(BlockIndent, BlockExitIndent, IsDone))
       return false;
     if (IsDone)
       break;
 
     // Parse the current line.
     auto LineStart = Current;
     advanceWhile(&Scanner::skip_nb_char);
     if (LineStart != Current) {
+      if (Str.empty() && IsFolded) {
         Str.append(LineBreaks, '\n');
+      } else {
+        if (Str.str().back() != '\n')
+          Str.append(LineBreaks, NewlineOrSpace);
+      }
       Str.append(StringRef(LineStart, Current - LineStart));
       LineBreaks = 0;
     }
 
+    if (IsFolded && !Str.empty()) {
+      // Handling empty lines in a folded string literal.
+      auto Line = StringRef(LineStart, Current - LineStart + 1);
+      if (isLineBreak(Line))
+        Str.append("\n");
+    }
+
     // 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;
   Str.append(getChompedLineBreaks(ChompingIndicator, LineBreaks, Str), '\n');
 
   // New lines may start a simple key.
   if (!FlowLevel)

llvm/test/YAMLParser/spec-09-24.test

 # RUN: yaml-bench -canonical %s | FileCheck %s
 # CHECK: ? !!str "strip"
-# CHECK: : !!str ""
+# CHECK: : !!str "Hello\n\nworld on multiple    \n\nlines\nspaces stripped"
 # CHECK: ? !!str "clip"
-# CHECK: : !!str ""
+# CHECK: : !!str "\nHello world on multiple\nlines only one space at the \n\nend\n"
 # CHECK: ? !!str "keep"
-# CHECK: : !!str "\n"
+# CHECK: : !!str "\nHello\nworld\non\nmultiple\n\n\nlines\nwith space at the end of each\nline\n\n"
+# CHECK: ? !!str "example"
+# CHECK: : !!str "Several lines of text,\nwith some \"quotes\" of various 'types',\nand also a blank line:\n\nplus another line at the end."
 
 strip: >-
+    Hello
 
+
+    world
+    on
+    multiple    
+    
+    
+    lines
+    
+    spaces stripped
 clip: >
 
+    Hello
+    world
+    on
+    multiple
+    
+    lines
+    only one space at the 
+    
+    
+    end
 keep: |+
+
+    Hello
+    world
+    on
+    multiple
+
+
+    lines
+    with space at the end of each
+    line
+
+example: |-
+    Several lines of text,
+    with some "quotes" of various 'types',
+    and also a blank line:
+
+    plus another line at the end.