[Symbolize] Parse multi-line markup elements.

[mysterymath]

Summary

This allows registering certain tags as possibly beginning multi-line
elements in the symbolizer markup parser. The parser is kept agnostic to
how lines are delimited; it reports the entire contents, including line
endings, once the end of element marker is reached.

[mysterymath]

Add to comments; use "multi-line" consistently.

[mysterymath]

Merge changes to previous patch.

[mysterymath]

Merge parent.

[mysterymath]

Integrate.

[mysterymath]

Fix tests.

[mysterymath]

Integrate.

[mysterymath]

Improve comment for flush().

[peter.smith]

llvm/include/llvm/DebugInfo/Symbolize/Markup.h

70

Will be useful to expand the comment to indicate the expected usage for multiline tags. It looks like multiple calls to parseLine() are needed with the only information that can be used to determine if we are in the middle of processing a mulitple line case is that nextNode() will return None but there is still input remaining?

76

Could be worth giving an example?

/// This allows the parser to finish any deferred processing, such as an in progress Multiline tag, and
/// may cause nextNode() to return additional nodes.

llvm/lib/DebugInfo/Symbolize/Markup.cpp

49

I think this could occur due to malformed input? For example

parseLine("{{{first");
nextElement() returns None
parseLine("}}"); // Typo only two closing braces.
nextElement() returns None
parseLine("{{{second"); // Assert failure "At most one multi-line element can begin at a time"

Would imply that an assertions build would crash on malformed input, but would append {{{second to the in progress multiline otherwise. I think this would be useful to report as a parse error. An assert seems like it is more appropriate for a coding error (misuse of the API).

[mysterymath]

Add comments; remove assert.

llvm/lib/DebugInfo/Symbolize/Markup.cpp

49

This assertion shouldn't ever be tripped; there's an early if(!InProgressMultiline.empty()) continue/return. I've removed it, as it didn't add much clarity.

For the example you gave, the current behavior would be to consider this a multi-line element with tag first (presuming the first line was {{{first:; multi-line elements have to begin with the field delimiter) and with the contents being everything else given. No elements would be emitted since the end tag still hasn't been seen, if flush() were called, the text would be scanned for control codes and emitted.

[mysterymath]

Refactor markup parser to parse lazily on each node request.

With the semantic changes to parseLine() in the previous change, this only
requires a slight modifification to the parsing algorithm. This has the
advantage that only the portion of the line that is actually used is parsed,
which is advantageous for context lines, where any suffix of the context
element is summarily discarded.

[mysterymath]

Add missed NextIdx=0 call.

[peter.smith]

LGTM thanks for the updates. I think the refactoring to a lazy interface has made it easier to see the intended usage.

[mysterymath]

Clean up usage of NextIdx.

[mysterymath]

Missed comment.

llvm/include/llvm/DebugInfo/Symbolize/Markup.h

 #ifndef LLVM_DEBUGINFO_SYMBOLIZE_MARKUP_H
 #define LLVM_DEBUGINFO_SYMBOLIZE_MARKUP_H
 
 #include <iostream>
 
 #include "llvm/ADT/Optional.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/ADT/StringRef.h"
+#include "llvm/ADT/StringSet.h"
 #include "llvm/Support/Regex.h"
 
 namespace llvm {
 namespace symbolize {
 
 /// A node of symbolizer markup.
 ///
 /// If only the Text field is set, this represents a region of text outside a
bool operator==(const MarkupNode &Other) const {
     return Text == Other.Text && Tag == Other.Tag && Fields == Other.Fields;
   }
   bool operator!=(const MarkupNode &Other) const { return !(*this == Other); }
 };
 
 /// Parses a log containing symbolizer markup into a sequence of nodes.
 class MarkupParser {
 public:
-  MarkupParser();
+  MarkupParser(StringSet<> MultilineTags = {});
 
   /// Parses an individual \p Line of input.
   ///
   /// Nodes from the previous parseLine() call that haven't yet been extracted
   /// by nextNode() are discarded. The nodes returned by nextNode() may
   /// reference the input string, so it must be retained by the caller until the
   /// last use.
+  ///
+  /// Note that some elements may span multiple lines. If a line ends with the
+  /// start of one of these elements, then no nodes will be produced until the
+  /// either the end or something that cannot be part of an element is
+  /// encountered. This may only occur after multiple calls to parseLine(),
+  /// corresponding to the lines of the multi-line element.
   void parseLine(StringRef Line);
 
-  /// Returns the next node from the most recent parseLine() call.
+  /// Inform the parser of that the input stream has ended.
+  ///
+  /// This allows the parser to finish any deferred processing (e.g., an
+  /// in-progress multi-line element) and may cause nextNode() to return
+  /// additional nodes.
+  void flush();
+
+  /// Returns the next node in the input sequence.
   ///
   /// Calling nextNode() may invalidate the contents of the node returned by the
   /// previous call.
   ///
   /// \returns the next markup node or None if none remain.
-  Optional<MarkupNode> nextNode() {
-    if (!NextIdx)
-      NextIdx = 0;
-    if (*NextIdx == Buffer.size()) {
-      NextIdx.reset();
-      Buffer.clear();
-      return None;
-    }
-    return std::move(Buffer[(*NextIdx)++]);
-  }
+  Optional<MarkupNode> nextNode();
 
 private:
   Optional<MarkupNode> parseElement(StringRef Line);
   void parseTextOutsideMarkup(StringRef Text);
+  Optional<StringRef> parseMultiLineBegin(StringRef Line);
+  Optional<StringRef> parseMultiLineEnd(StringRef Line);
+
+  // Tags of elements that can span multiple lines.
+  const StringSet<> MultilineTags;
+
+  // Contents of a multi-line element that has finished being parsed. Retained
+  // to keep returned StringRefs for the contents valid.
+  std::string FinishedMultiline;
+
+  // Contents of a multi-line element that is still in the process of receiving
+  // lines.
+  std::string InProgressMultiline;
+
+  // The line currently being parsed.
+  StringRef Line;
 
   // Buffer for nodes parsed from the current line.
   SmallVector<MarkupNode> Buffer;
 
-  // Next buffer index to return or None if nextNode has not yet been called.
-  Optional<size_t> NextIdx;
+  // Next buffer index to return.
+  size_t NextIdx;
 
   // Regular expression matching supported ANSI SGR escape sequences.
   const Regex SGRSyntax;
 };
 
 } // end namespace symbolize
 } // end namespace llvm
 
 #endif // LLVM_DEBUGINFO_SYMBOLIZE_MARKUP_H

llvm/lib/DebugInfo/Symbolize/Markup.cpp

 //===- lib/DebugInfo/Symbolize/Markup.cpp ------------------------------===//
 //
 // 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
 //
 //===----------------------------------------------------------------------===//
 ///
 /// \file
 /// This file defines the log symbolizer markup data model and parser.
 ///
 //===----------------------------------------------------------------------===//
 
 #include "llvm/DebugInfo/Symbolize/Markup.h"
 
+#include "llvm/ADT/STLExtras.h"
 #include "llvm/ADT/StringExtras.h"
 
 namespace llvm {
 namespace symbolize {
 
 // Matches the following:
 //   "\033[0m"
 //   "\033[1m"
 //   "\033[30m" -- "\033[37m"
 static const char SGRSyntaxStr[] = "\033\\[([0-1]|3[0-7])m";
 
-MarkupParser::MarkupParser() : SGRSyntax(SGRSyntaxStr) {}
+MarkupParser::MarkupParser(StringSet<> MultilineTags)
+    : MultilineTags(std::move(MultilineTags)), SGRSyntax(SGRSyntaxStr) {}
 
 static StringRef takeTo(StringRef Str, StringRef::iterator Pos) {
   return Str.take_front(Pos - Str.begin());
 }
 static void advanceTo(StringRef &Str, StringRef::iterator Pos) {
   Str = Str.drop_front(Pos - Str.begin());
 }
 
 void MarkupParser::parseLine(StringRef Line) {
   Buffer.clear();
-  while (!Line.empty()) {
-    // Find the first valid markup element, if any.
-    if (Optional<MarkupNode> Element = parseElement(Line)) {
-      parseTextOutsideMarkup(takeTo(Line, Element->Text.begin()));
-      Buffer.push_back(std::move(*Element));
-      advanceTo(Line, Element->Text.end());
-    } else {
-      // The line doesn't contain any more markup elements, so emit it as text.
-      parseTextOutsideMarkup(Line);
-      return;
-    }
-  }
+  NextIdx = 0;
+  FinishedMultiline.clear();
+  this->Line = Line;
+}
+
+Optional<MarkupNode> MarkupParser::nextNode() {
+  // Pull something out of the buffer if possible.
+  if (!Buffer.empty()) {
+    if (NextIdx < Buffer.size())
+      return std::move(Buffer[NextIdx++]);
+    NextIdx = 0;
+    Buffer.clear();
+  }
+
+  // The buffer is empty, so parse the next bit of the line.
+
+  if (Line.empty())
+    return None;
+
+  if (!InProgressMultiline.empty()) {
+    if (Optional<StringRef> MultilineEnd = parseMultiLineEnd(Line)) {
+      llvm::append_range(InProgressMultiline, *MultilineEnd);
+      assert(FinishedMultiline.empty() &&
+             "At most one multi-line element can be finished at a time.");
+      FinishedMultiline.swap(InProgressMultiline);
+      // Parse the multi-line element as if it were contiguous.
+      advanceTo(Line, MultilineEnd->end());
+      return *parseElement(FinishedMultiline);
+    }
+
+    // The whole line is part of the multi-line element.
+    llvm::append_range(InProgressMultiline, Line);
+    Line = Line.drop_front(Line.size());
+    return None;
+  }
+
+    return nextNode();
+  }
+
+  // Since there were no valid elements remaining, see if the line opens a
+  // multi-line element.
+  if (Optional<StringRef> MultilineBegin = parseMultiLineBegin(Line)) {
+    // Emit any text before the element.
+    parseTextOutsideMarkup(takeTo(Line, MultilineBegin->begin()));
+
+    // Begin recording the multi-line element.
+    llvm::append_range(InProgressMultiline, *MultilineBegin);
+    Line = Line.drop_front(Line.size());
+    return nextNode();
+  }
+
+  Line = Line.drop_front(Line.size());
+  return nextNode();
+
+void MarkupParser::flush() {
+  if (InProgressMultiline.empty())
+    return;
+  FinishedMultiline.swap(InProgressMultiline);
+  parseTextOutsideMarkup(FinishedMultiline);
 }
 
 // Finds and returns the next valid markup element in the given line. Returns
 // None if the line contains no valid elements.
 Optional<MarkupNode> MarkupParser::parseElement(StringRef Line) {
   while (true) {
     // Find next element using begin and end markers.
     size_t BeginPos = Line.find("{{{");
while (SGRSyntax.match(Text, &Matches)) {
 
     Buffer.push_back(textNode(*Matches.begin()));
     advanceTo(Text, Matches.begin()->end());
   }
   if (!Text.empty())
     Buffer.push_back(textNode(Text));
 }
 
+// Given that a line doesn't contain any valid markup, see if it ends with the
+// start of a multi-line element. If so, returns the beginning.
+Optional<StringRef> MarkupParser::parseMultiLineBegin(StringRef Line) {
+  // A multi-line begin marker must be the last one on the line.
+  size_t BeginPos = Line.rfind("{{{");
+  if (BeginPos == StringRef::npos)
+    return None;
+  size_t BeginTagPos = BeginPos + 3;
+
+  // If there are any end markers afterwards, the begin marker cannot belong to
+  // a multi-line element.
+  size_t EndPos = Line.find("}}}", BeginTagPos);
+  if (EndPos != StringRef::npos)
+    return None;
+
+  // Check whether the tag is registered multi-line.
+  size_t EndTagPos = Line.find(':', BeginTagPos);
+  if (EndTagPos == StringRef::npos)
+    return None;
+  StringRef Tag = Line.slice(BeginTagPos, EndTagPos);
+  if (!MultilineTags.contains(Tag))
+    return None;
+  return Line.substr(BeginPos);
+}
+
+// See if the line begins with the ending of an in-progress multi-line element.
+// If so, return the ending.
+Optional<StringRef> MarkupParser::parseMultiLineEnd(StringRef Line) {
+  size_t EndPos = Line.find("}}}");
+  if (EndPos == StringRef::npos)
+    return None;
+  return Line.take_front(EndPos + 3);
+}
+
 } // end namespace symbolize
 } // end namespace llvm

llvm/unittests/DebugInfo/Symbolizer/MarkupTest.cpp

TEST(SymbolizerMarkup, LinesWithoutMarkup) {
   EXPECT_THAT(Parser.nextNode(), testing::Optional(isNode("text")));
   EXPECT_THAT(Parser.nextNode(), None);
 
   Parser.parseLine("discarded");
   Parser.parseLine("kept");
   EXPECT_THAT(Parser.nextNode(), testing::Optional(isNode("kept")));
   EXPECT_THAT(Parser.nextNode(), None);
 
+  Parser.parseLine("text\n");
+  EXPECT_THAT(Parser.nextNode(), testing::Optional(isNode("text\n")));
+  EXPECT_THAT(Parser.nextNode(), None);
+
+  Parser.parseLine("text\r\n");
+  EXPECT_THAT(Parser.nextNode(), testing::Optional(isNode("text\r\n")));
+  EXPECT_THAT(Parser.nextNode(), None);
+
   Parser.parseLine("{{{");
   EXPECT_THAT(Parser.nextNode(), testing::Optional(isNode("{{{")));
   EXPECT_THAT(Parser.nextNode(), None);
 
   Parser.parseLine("{{{}}");
   EXPECT_THAT(Parser.nextNode(), testing::Optional(isNode("{{{}}")));
   EXPECT_THAT(Parser.nextNode(), None);
 
TEST(SymbolizerMarkup, LinesWithMarkup) {
 
   Parser.parseLine("{{{tag:\033[0m}}}");
   EXPECT_THAT(Parser.nextNode(),
               testing::Optional(
                   isNode("{{{tag:\033[0m}}}", "tag", ElementsAre("\033[0m"))));
   EXPECT_THAT(Parser.nextNode(), None);
 }
 
+TEST(SymbolizerMarkup, MultilineElements) {
+  MarkupParser Parser(/*MultilineTags=*/{"first", "second"});
+
+  Parser.parseLine("{{{tag:");
+  EXPECT_THAT(Parser.nextNode(), testing::Optional(isNode("{{{tag:")));
+  EXPECT_THAT(Parser.nextNode(), None);
+
+  Parser.parseLine("{{{first:");
+  EXPECT_THAT(Parser.nextNode(), None);
+  Parser.parseLine("}}}{{{second:");
+  EXPECT_THAT(
+      Parser.nextNode(),
+      testing::Optional(isNode("{{{first:}}}", "first", ElementsAre(""))));
+  EXPECT_THAT(Parser.nextNode(), None);
+  Parser.parseLine("}}}");
+  EXPECT_THAT(
+      Parser.nextNode(),
+      testing::Optional(isNode("{{{second:}}}", "second", ElementsAre(""))));
+  EXPECT_THAT(Parser.nextNode(), None);
+
+  Parser.parseLine("{{{before{{{first:");
+  EXPECT_THAT(Parser.nextNode(), testing::Optional(isNode("{{{before")));
+  EXPECT_THAT(Parser.nextNode(), None);
+  Parser.parseLine("line");
+  EXPECT_THAT(Parser.nextNode(), None);
+  Parser.parseLine("}}}after");
+  EXPECT_THAT(Parser.nextNode(),
+              testing::Optional(
+                  isNode("{{{first:line}}}", "first", ElementsAre("line"))));
+  EXPECT_THAT(Parser.nextNode(), testing::Optional(isNode("after")));
+  EXPECT_THAT(Parser.nextNode(), None);
+
+  Parser.parseLine("{{{first:");
+  EXPECT_THAT(Parser.nextNode(), None);
+  Parser.flush();
+  EXPECT_THAT(Parser.nextNode(), testing::Optional(isNode("{{{first:")));
+  EXPECT_THAT(Parser.nextNode(), None);
+
+  Parser.parseLine("{{{first:\n");
+  EXPECT_THAT(Parser.nextNode(), None);
+  Parser.parseLine("}}}\n");
+  EXPECT_THAT(
+      Parser.nextNode(),
+      testing::Optional(isNode("{{{first:\n}}}", "first", ElementsAre("\n"))));
+  EXPECT_THAT(Parser.nextNode(), testing::Optional(isNode("\n")));
+  EXPECT_THAT(Parser.nextNode(), None);
+
+  Parser.parseLine("{{{first:\r\n");
+  EXPECT_THAT(Parser.nextNode(), None);
+  Parser.parseLine("}}}\r\n");
+  EXPECT_THAT(Parser.nextNode(),
+              testing::Optional(
+                  isNode("{{{first:\r\n}}}", "first", ElementsAre("\r\n"))));
+  EXPECT_THAT(Parser.nextNode(), testing::Optional(isNode("\r\n")));
+  EXPECT_THAT(Parser.nextNode(), None);
+
+  Parser.parseLine("{{{first:");
+  EXPECT_THAT(Parser.nextNode(), None);
+  Parser.parseLine("\033[0m}}}");
+  EXPECT_THAT(Parser.nextNode(),
+              testing::Optional(isNode("{{{first:\033[0m}}}", "first",
+                                       ElementsAre("\033[0m"))));
+  EXPECT_THAT(Parser.nextNode(), None);
+}
+
 } // namespace