[clangd] Only minimally escape text when rendering to markdown.

[sammccall]

Summary

Conservatively escaping everything is bad in coc.nvim which shows the markdown
to the user, and we have reports of it causing problems for other parsers.

Fixes https://github.com/clangd/clangd/issues/301

[sammccall]

couple more tests

[kadircet]

Just writing down my investigation results for context:
Looks like we'll never escape $%'(,/:;?@[^{|} anymore.

Markdown already doesn't provide backslash escaping for $%',/:;?@^| which leaves us with parentheses ([{}:

• [ looks fine as it is only used for hyperlinks and we escape the ] if need be
• '(' again seems to be only special for providing a text for hyperlinks, so that should also be OK.
• {} apparently doesn't do anything in normal markdown but some extensions make use of it for adding ids to headers, i.e # header1 {#mycrazyheader}, so again should be OK.

clang-tools-extra/clangd/FormattedString.cpp

69

what is the ? for ?

73

we early exited already in case of empty contents

130

nit: if(!StartsLine || !Before.empty()))

132

nit: After.ltrim('#')

133

markdown is weird :(

139

s/the a/the/

150

_ seems to behave different than * :(

it seems to rather depend on the spaces around the text being emphasized, i.e

foo _ bar _ foo -> no emphasis
foo _ bar_ foo -> no emphasis
foo _bar_ foo -> emphasis on bar
foo_bar_ foo -> no emphasis

so this should rather be Before.endswith(" ") && isAlpha(After) for the beginning of emphasis and the opposite for the ending.
Not sure if there's an easy way to decide on it in isolation.

162

nit: return IsBullet() || RulerLength() || !SpaceSurrounds();

164

is this really worth all the trouble ?

166

I believe it is also allowed to have whitespaces(less than 4?) before the > to be interpreted as a quote marker.

[sammccall]

Address review comments

[sammccall]

Sorry for the slow turnaround, bit off more than I could chew on a few fronts :-(

clang-tools-extra/clangd/FormattedString.cpp

69

<?foo... is a processing instruction, which is valid inline HTML (and therefore needs escaping)

132

I'm trying to avoid repeating the known values of C as there's various fallthrough/copied cases and it seems more fragile.

164

Simplified it a bit. I think it's worth not escaping < when not matched with >. Sadly the rule can't be quite that simple because multiple chunks can form a tag.

166

Yes, but a chunk never begins with whitespace (see assert at top of function)

[kadircet]

thanks, lgtm!

clang-tools-extra/clangd/FormattedString.cpp

150

regarding this one, i suppose we'll just be escaping in some unnecessary cases(like the 2nd and the 4th), but still better than the current state so nvm.

[sammccall]

Filed https://github.com/google/llvm-premerge-checks/issues/147 for the spurious unit test failure.

clang-tools-extra/clangd/FormattedString.cpp

150

Oops, I forgot to reply to this one. Good catch that * and _ are different.
The rules are indeed really complicated (particularly for _ next to punctuation) and we don't know whether we are at the start or end.

However my reading of the spec says alnum_alnum never needs to be escaped, and that's incredibly common, so I've added that special case. (Same is true for alnum___alnum, but I don't think that's common enough to bother with).

[sammccall]

Fix '_' rules.

[kadircet]

thanks, still LG

clang-tools-extra/clangd/FormattedString.h

public:
   void addCodeBlock(std::string Code, std::string Language = "cpp");
   /// Heading is a special type of paragraph that will be prepended with \p
   /// Level many '#'s in markdown.
   Paragraph &addHeading(size_t Level);
 
   BulletList &addBulletList();
 
   /// Doesn't contain any trailing newlines.
+  /// We try to make the markdown human-readable, e.g. avoid extra escaping.
+  /// At least one client (coc.nvim) displays the markdown verbatim!
   std::string asMarkdown() const;
   /// Doesn't contain any trailing newlines.
   std::string asPlainText() const;
 
 private:
   std::vector<std::unique_ptr<Block>> Children;
 };
 } // namespace markup
 } // namespace clangd
 } // namespace clang
 
 #endif

clang-tools-extra/clangd/FormattedString.cpp

 //===--- FormattedString.cpp --------------------------------*- 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
 //
 //===----------------------------------------------------------------------===//
 #include "FormattedString.h"
 #include "clang/Basic/CharInfo.h"
 #include "llvm/ADT/ArrayRef.h"
 #include "llvm/ADT/STLExtras.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/ADT/StringExtras.h"
 #include "llvm/ADT/StringRef.h"
+#include "llvm/Support/Compiler.h"
 #include "llvm/Support/ErrorHandling.h"
 #include "llvm/Support/FormatVariadic.h"
 #include "llvm/Support/raw_ostream.h"
 #include <cstddef>
 #include <iterator>
 #include <memory>
 #include <string>
 #include <vector>
 
 namespace clang {
 namespace clangd {
 namespace markup {
 
 namespace {
+
+// Is <contents a plausible start to an HTML tag?
+// Contents may not be the rest of the line, but it's the rest of the plain
+// text, so we expect to see at least the tag name.
+bool looksLikeTag(llvm::StringRef Contents) {
+  if (Contents.empty())
+    return false;
+  if (Contents.front() == '!' || Contents.front() == '?' ||
+      Contents.front() == '/')
+    return true;
+  // Check the start of the tag name.
+  if (!llvm::isAlpha(Contents.front()))
+    return false;
+  // Drop rest of the tag name, and following whitespace.
+  Contents = Contents
+                 .drop_while([](char C) {
+                   return llvm::isAlnum(C) || C == '-' || C == '_' || C == ':';
+                 })
+                 .drop_while(isWhitespace);
+  // The rest of the tag consists of attributes, which have restrictive names.
+  // If we hit '=', all bets are off (attribute values can contain anything).
+  for (; !Contents.empty(); Contents = Contents.drop_front()) {
+    if (llvm::isAlnum(Contents.front()) || isWhitespace(Contents.front()))
+      continue;
+    if (Contents.front() == '>' || Contents.startswith("/>"))
+      return true; // May close the tag.
+    if (Contents.front() == '=')
+      return true; // Don't try to parse attribute values.
+    return false;  // Random punctuation means this isn't a tag.
+  }
+  return true; // Potentially incomplete tag.
+}
+
+// Tests whether C should be backslash-escaped in markdown.
+// The string being escaped is Before + C + After. This is part of a paragraph.
+// StartsLine indicates whether `Before` is the start of the line.
+// After may not be everything until the end of the line.
+//
+// It's always safe to escape punctuation, but want minimal escaping.
+// The strategy is to escape the first character of anything that might start
+// a markdown grammar construct.
+bool needsLeadingEscape(char C, llvm::StringRef Before, llvm::StringRef After,
+                        bool StartsLine) {
+  assert(Before.take_while(isWhitespace).empty());
+  auto RulerLength = [&]() -> /*Length*/ unsigned {
+    if (!StartsLine || !Before.empty())
+      return false;
+    llvm::StringRef A = After.rtrim();
+    return llvm::all_of(A, [C](char D) { return C == D; }) ? 1 + A.size() : 0;
+  };
+  auto IsBullet = [&]() {
+    return StartsLine && Before.empty() &&
+           (After.empty() || After.startswith(" "));
+  };
+  auto SpaceSurrounds = [&]() {
+    return (After.empty() || isWhitespace(After.front())) &&
+           (Before.empty() || isWhitespace(Before.back()));
+  };
+  auto WordSurrounds = [&]() {
+    return (!After.empty() && llvm::isAlnum(After.front())) &&
+           (!Before.empty() && llvm::isAlnum(Before.back()));
+  };
+
+  switch (C) {
+  case '\\': // Escaped character.
+    return true;
+  case '`': // Code block or inline code
+    // Any number of backticks can delimit an inline code block that can end
+    // anywhere (including on another line). We must escape them all.
+    return true;
+  case '~': // Code block
+    return StartsLine && Before.empty() && After.startswith("~~");
+  case '#': { // ATX heading.
+    if (!StartsLine || !Before.empty())
+      return false;
+    llvm::StringRef Rest = After.ltrim(C);
+    return Rest.empty() || Rest.startswith(" ");
+  }
+  case ']': // Link or link reference.
+    // We escape ] rather than [ here, because it's more constrained:
+    //   ](...) is an in-line link
+    //   ]: is a link reference
+    // The following are only links if the link reference exists:
+    //   ] by itself is a shortcut link
+    //   ][...] is an out-of-line link
+    // Because we never emit link references, we don't need to handle these.
+    return After.startswith(":") || After.startswith("(");
+  case '=': // Setex heading.
+    return RulerLength() > 0;
+  case '_': // Horizontal ruler or matched delimiter.
+    if (RulerLength() >= 3)
+      return true;
+    // Not a delimiter if surrounded by space, or inside a word.
+    // (The rules at word boundaries are subtle).
+    return !(SpaceSurrounds() || WordSurrounds());
+  case '-': // Setex heading, horizontal ruler, or bullet.
+    if (RulerLength() > 0)
+      return true;
+    return IsBullet();
+  case '+': // Bullet list.
+    return IsBullet();
+  case '*': // Bullet list, horizontal ruler, or delimiter.
+    return IsBullet() || RulerLength() >= 3 || !SpaceSurrounds();
+  case '<': // HTML tag (or autolink, which we choose not to escape)
+    return looksLikeTag(After);
+  case '>': // Quote marker. Needs escaping at start of line.
+    return StartsLine && Before.empty();
+  case '&': { // HTML entity reference
+    auto End = After.find(';');
+    if (End == llvm::StringRef::npos)
+      return false;
+    llvm::StringRef Content = After.substr(0, End);
+    if (Content.consume_front("#")) {
+      if (Content.consume_front("x") || Content.consume_front("X"))
+        return llvm::all_of(Content, llvm::isHexDigit);
+      return llvm::all_of(Content, llvm::isDigit);
+    }
+    return llvm::all_of(Content, llvm::isAlpha);
+  }
+  case '.': // Numbered list indicator. Escape 12. -> 12\. at start of line.
+  case ')':
+    return StartsLine && !Before.empty() &&
+           llvm::all_of(Before, llvm::isDigit) && After.startswith(" ");
+  default:
+    return false;
+  }
+}
+
 /// Escape a markdown text block. Ensures the punctuation will not introduce
 /// any of the markdown constructs.
-std::string renderText(llvm::StringRef Input) {
-  // Escaping ASCII punctuation ensures we can't start a markdown construct.
-  constexpr llvm::StringLiteral Punctuation =
-      R"txt(!"#$%&'()*+,-./:;<=>?@[\]^_`{|}~)txt";
-
+std::string renderText(llvm::StringRef Input, bool StartsLine) {
   std::string R;
-  for (size_t From = 0; From < Input.size();) {
-    size_t Next = Input.find_first_of(Punctuation, From);
-    R += Input.substr(From, Next - From);
-    if (Next == llvm::StringRef::npos)
-      break;
-    R += "\\";
-    R += Input[Next];
-
-    From = Next + 1;
+  for (unsigned I = 0; I < Input.size(); ++I) {
+    if (needsLeadingEscape(Input[I], Input.substr(0, I), Input.substr(I + 1),
+                           StartsLine))
+      R.push_back('\\');
+    R.push_back(Input[I]);
   }
   return R;
 }
 
 /// Renders \p Input as an inline block of code in markdown. The returned value
 /// is surrounded by backticks and the inner contents are properly escaped.
 std::string renderInlineBlock(llvm::StringRef Input) {
   std::string R;

 }
 
 void Paragraph::renderMarkdown(llvm::raw_ostream &OS) const {
   llvm::StringRef Sep = "";
   for (auto &C : Chunks) {
     OS << Sep;
     switch (C.Kind) {
     case Chunk::PlainText:
-      OS << renderText(C.Contents);
+      OS << renderText(C.Contents, Sep.empty());
       break;
     case Chunk::InlineCode:
       OS << renderInlineBlock(C.Contents);
       break;
     }
     Sep = " ";
   }
   // Paragraphs are translated into markdown lines, not markdown paragraphs.

clang-tools-extra/clangd/unittests/FormattedStringTests.cpp

 #include "gmock/gmock.h"
 #include "gtest/gtest.h"
 
 namespace clang {
 namespace clangd {
 namespace markup {
 namespace {
 
-TEST(Render, Escaping) {
-  // Check some ASCII punctuation
-  Paragraph P;
-  P.appendText("*!`");
-  EXPECT_EQ(P.asMarkdown(), "\\*\\!\\`");
+std::string escape(llvm::StringRef Text) {
+  return Paragraph().appendText(Text.str()).asMarkdown();
+}
 
+MATCHER_P(escaped, C, "") {
+  return testing::ExplainMatchResult(::testing::HasSubstr(std::string{'\\', C}),
+                                     arg, result_listener);
+}
+
+MATCHER(escapedNone, "") {
+  return testing::ExplainMatchResult(::testing::Not(::testing::HasSubstr("\\")),
+                                     arg, result_listener);
+}
+
+TEST(Render, Escaping) {
   // Check all ASCII punctuation.
-  P = Paragraph();
   std::string Punctuation = R"txt(!"#$%&'()*+,-./:;<=>?@[\]^_`{|}~)txt";
-  // Same text, with each character escaped.
-  std::string EscapedPunctuation;
-  EscapedPunctuation.reserve(2 * Punctuation.size());
-  for (char C : Punctuation)
-    EscapedPunctuation += std::string("\\") + C;
-  P.appendText(Punctuation);
-  EXPECT_EQ(P.asMarkdown(), EscapedPunctuation);
+  std::string EscapedPunc = R"txt(!"#$%&'()\*+,-./:;<=>?@[\\]^\_\`{|}~)txt";
+  EXPECT_EQ(escape(Punctuation), EscapedPunc);
+
+  // Inline code
+  EXPECT_EQ(escape("`foo`"), R"(\`foo\`)");
+  EXPECT_EQ(escape("`foo"), R"(\`foo)");
+  EXPECT_EQ(escape("foo`"), R"(foo\`)");
+  EXPECT_EQ(escape("``foo``"), R"(\`\`foo\`\`)");
+  // Code blocks
+  EXPECT_EQ(escape("```"), R"(\`\`\`)"); // This could also be inline code!
+  EXPECT_EQ(escape("~~~"), R"(\~~~)");
+
+  // Rulers and headings
+  EXPECT_THAT(escape("## Heading"), escaped('#'));
+  EXPECT_THAT(escape("Foo # bar"), escapedNone());
+  EXPECT_EQ(escape("---"), R"(\---)");
+  EXPECT_EQ(escape("-"), R"(\-)");
+  EXPECT_EQ(escape("==="), R"(\===)");
+  EXPECT_EQ(escape("="), R"(\=)");
+  EXPECT_EQ(escape("***"), R"(\*\*\*)"); // \** could start emphasis!
+
+  // HTML tags.
+  EXPECT_THAT(escape("<pre"), escaped('<'));
+  EXPECT_THAT(escape("< pre"), escapedNone());
+  EXPECT_THAT(escape("if a<b then"), escaped('<'));
+  EXPECT_THAT(escape("if a<b then c."), escapedNone());
+  EXPECT_THAT(escape("if a<b then c='foo'."), escaped('<'));
+  EXPECT_THAT(escape("std::vector<T>"), escaped('<'));
+  EXPECT_THAT(escape("std::vector<std::string>"), escaped('<'));
+  EXPECT_THAT(escape("std::map<int, int>"), escapedNone());
+  // Autolinks
+  EXPECT_THAT(escape("Email <[e-mail]>"), escapedNone());
+  EXPECT_THAT(escape("Website <http://foo.bar>"), escapedNone());
+
+  // Bullet lists.
+  EXPECT_THAT(escape("- foo"), escaped('-'));
+  EXPECT_THAT(escape("* foo"), escaped('*'));
+  EXPECT_THAT(escape("+ foo"), escaped('+'));
+  EXPECT_THAT(escape("+"), escaped('+'));
+  EXPECT_THAT(escape("a + foo"), escapedNone());
+  EXPECT_THAT(escape("a+ foo"), escapedNone());
+  EXPECT_THAT(escape("1. foo"), escaped('.'));
+  EXPECT_THAT(escape("a. foo"), escapedNone());
+
+  // Emphasis.
+  EXPECT_EQ(escape("*foo*"), R"(\*foo\*)");
+  EXPECT_EQ(escape("**foo**"), R"(\*\*foo\*\*)");
+  EXPECT_THAT(escape("*foo"), escaped('*'));
+  EXPECT_THAT(escape("foo *"), escapedNone());
+  EXPECT_THAT(escape("foo * bar"), escapedNone());
+  EXPECT_THAT(escape("foo_bar"), escapedNone());
+  EXPECT_THAT(escape("foo _bar"), escaped('_'));
+  EXPECT_THAT(escape("foo_ bar"), escaped('_'));
+  EXPECT_THAT(escape("foo _ bar"), escapedNone());
+
+  // HTML entities.
+  EXPECT_THAT(escape("fish &chips;"), escaped('&'));
+  EXPECT_THAT(escape("fish & chips;"), escapedNone());
+  EXPECT_THAT(escape("fish &chips"), escapedNone());
+  EXPECT_THAT(escape("foo &#42; bar"), escaped('&'));
+  EXPECT_THAT(escape("foo &#xaf; bar"), escaped('&'));
+  EXPECT_THAT(escape("foo &?; bar"), escapedNone());
+
+  // Links.
+  EXPECT_THAT(escape("[foo](bar)"), escaped(']'));
+  EXPECT_THAT(escape("[foo]: bar"), escaped(']'));
+  // No need to escape these, as the target never exists.
+  EXPECT_THAT(escape("[foo][]"), escapedNone());
+  EXPECT_THAT(escape("[foo][bar]"), escapedNone());
+  EXPECT_THAT(escape("[foo]"), escapedNone());
 
   // In code blocks we don't need to escape ASCII punctuation.
-  P = Paragraph();
+  Paragraph P = Paragraph();
   P.appendCode("* foo !+ bar * baz");
   EXPECT_EQ(P.asMarkdown(), "`* foo !+ bar * baz`");
 
   // But we have to escape the backticks.
   P = Paragraph();
   P.appendCode("foo`bar`baz");
   EXPECT_EQ(P.asMarkdown(), "`foo``bar``baz`");
 

clang-tools-extra/clangd/unittests/HoverTests.cpp

TEST(Hover, PresentRulers) {
   HI.Kind = index::SymbolKind::Variable;
   HI.Name = "foo";
   HI.Value = "val";
   HI.Definition = "def";
 
   llvm::StringRef ExpectedMarkdown = R"md(### variable `foo`  
 
 ---
-Value \= `val`  
+Value = `val`  
 
 ---
 ```cpp
 def
 ```)md";
   EXPECT_EQ(HI.present().asMarkdown(), ExpectedMarkdown);
 
   llvm::StringRef ExpectedPlaintext = R"pt(variable foo