[clangd] Introduce intermediate representation of formatted text

[ilya-biryukov]

Summary

That can render to markdown or plain text. Used for findHover requests.

[ilya-biryukov]

This is a follow-up for a discussion from D55250.
Still missing test, wanted to get some input on the API first.

[sammccall]

This looks pretty nice to me! Sorry for the wait.
Adding @kadircet as hover-guru-in-waiting.

clang-tools-extra/clangd/ClangdLSPServer.cpp

814 ↗

(On Diff #187936)

(I'd like to see that in this patch if possible, it shouldn't be much work)

clang-tools-extra/clangd/ClangdServer.h

186 ↗

(On Diff #187936)

Not sure about switching from Hover to FormattedString as return type here: LSP hover struct contains a range field (what are the bounds of the hovered thing?) that we may want to populate that doesn't fit in FormattedString.
I'd suggest the function in XRefs.h should return FormattedString (and later maybe pair<FormattedString, Range>), and the ClangdServer version should continue to provide the rendered Hover.

(We'll eventually want ClangdServer to return some HoverInfo struct with structured information, as we want embedding clients to be able to render it other ways, and maybe use it to provide extension methods like YCM's GetType. But no need to touch that in this patch, we'll end up producing HoverInfo -> FormattedString -> LSP Hover, I guess)

clang-tools-extra/clangd/FormattedString.cpp

42

you may want to take the language name, and default it to either cpp or nothing.
Including it in the triple-backtick block can trigger syntax highlighting, and editors are probably somewhat likely to actually implement this.

64

why do we add surrounding spaces if we don't do the same for text chunks?

clang-tools-extra/clangd/FormattedString.h

2

This will need tests as you note, which shouldn't be hard.
It's not terribly complicated, but it's the sort of thing that may accumulate special cases.

28

I guess this will get an optional parameter to control the style (bold, italic etc)?

32

Having various methods that take strings may struggle if we want a lot of composability (e.g. a bullet list whose bullet whose third word is a hyperlink/bold).

(I'm not sure whether this is going to be a real problem, just thinking out loud here)

One alternative extensibility would be to make "containers" methods taking a lambda that renders the body.
e.g.

FormattedString S;
S << "std::";
S.bold([&} S << "swap" };
S.list(FormattedString::Numbered, [&] {
  S.item([&] { S << "sometimes you get the wrong overload"; });
  S.item([&] {
    S << "watch out for ";
    S.link("https://en.cppreference.com/w/cpp/language/adl", [&] { S << "ADL"; });
  });
});
S.codeBlock([&] S << "Here is an example"; });

Not sure if this is really better, I just have it on my mind because I ended up using it for the JSON.h streaming output. We can probably bolt it on later if necessary.

40

I think we want renderForDebugging() or so which would print the chunks explicitly, a la CodeCompletionString.

This is useful for actual debugging, and for testing methods that return FormattedString (as opposed to the FormattedString->markdown translation)

clang-tools-extra/clangd/XRefs.cpp

528 ↗

(On Diff #187936)

should this be an inline code block?

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

1157 ↗

(On Diff #187936)

When this lands for real, I think we should assert on the renderForDebugging() output or similar.

[kadircet]

clang-tools-extra/clangd/ClangdServer.h

186 ↗

(On Diff #187936)

I agree with Sam on the layering. I was also working in a patch that was changing ClangdServers output from Hover to HoverInfo(a structured version of Hover).

[ilya-biryukov]

• Rebase
• Parse client capabilities, send markdown on hover if client supports it
• Use inline block for the scope
• Add a language for code blocks
• Add a FIXME for hover tests
• Fix escaping, add tests
• Update XRefs tests

[ilya-biryukov]

clang-tools-extra/clangd/FormattedString.cpp

42

Done. Defaulting to 'cpp'.
VSCode actually does syntax highlighting there and it looks nice.

64

a leftover from my first prototype.
They don't seem to be necessary, removed them.

clang-tools-extra/clangd/FormattedString.h

32

Agree that the current approach won't generalize to more complicated cases without some design work.
The lambda-heavy code is hard to read to my personal taste, but may actually be a good option in practice.
I'd also try playing around with some lambda-free alternatives to see if they lead to better syntax without compromising extensibility or making the implementation overly complex.

I also think we should bolt on this until we hit more use-cases with more extensive needs for formatting markdown.

40

That would be a useful addition. I've added a FIXME for now and testing plaintext in XRefs.
I'd suggest adding debug representation in a follow-up change, but also happy to do it now if you feel that's necessary.

That would need updates to all hover tests and that's a big enough to go into a separate change, from my perspective.

[ilya-biryukov]

clang-tools-extra/clangd/ClangdServer.h

186 ↗

(On Diff #187936)

ClangdServer does not know whether to render the FormattedString into markdown or plaintext and I believe it should stay that way.
Happy to return HoverInfo, though. I'll introduce one with FormattedString and Range

[ilya-biryukov]

• Return 'HoverInfo' instead of FormattedString
• Reformat

clang-tools-extra/clangd/ClangdServer.h

186 ↗

(On Diff #187936)

Returning HoverInfo now, with a FormattedString and a range.

[ilya-biryukov]

• Remove a FIXME that was fixed

[ilya-biryukov]

clang-tools-extra/clangd/FormattedString.h

28

Either that or a separate function to add bold/italic, etc.
I think we should keep it simple in the first revision.

This really tries to provide a vocabulary type to carry a string with formatted blocks around, not support full markdown from the start.

[ilya-biryukov]

• Remove dead test code. NFC

[ilya-biryukov]

This is ready for another round of review. As mentioned in the comments, I think some of the comments are better addressed by a separate change, because they would touch lots of lines in the test.
Let me know if I missed anything else.

[sammccall]

As discussed, it probably makes sense to split into two patches, adding this abstraction and using it.
(All together is also fine but should have the tests for the new behavior, which probably means renderForTests() too)

Generally looks good. I think we'll run into the limitations as soon as we want to add lists, but that's OK.

clang-tools-extra/clangd/FormattedString.cpp

72

backticks = "```"
while (Input.contains(backticks))
  backticks.push_back("`")

I don't think we care about DOS here?

91

comment for this merge?

108

I'm not sure we're realistically going to be able to enforce this very well, we're going to use this for types. Maybe translate into ' ' instead? (or at least in production mode)

141

(we could also use the version in CharInfo)

[ilya-biryukov]

• Use isWhitespace from CharInfo.
• Add a comment for merging text blocks together.
• Remove assertion that inline code block does not contain newlines.
• Simplify how the max number of backticks is computed.

clang-tools-extra/clangd/FormattedString.cpp

72

I'd like to keep this linear anyway.
Simplified the algorithm a bit, let me know if it still looks too complicated.

108

Actually, the CommonMark specification allows newline in the inline code blocks.
The renderers should replace newlines with spaces.
Removed the assertion.

141

Thanks! I knew there should be a helper like this somewhere in LLVM...

[ilya-biryukov]

• Remove hover-related bits, they will go into a separate revision

[sammccall]

clang-tools-extra/clangd/FormattedString.h

34

newlines are allowed now?

[ilya-biryukov]

• Update a comment

clang-tools-extra/clangd/CMakeLists.txt

add_clang_library(clangDaemon
   Context.cpp
   Diagnostics.cpp
   DraftStore.cpp
   ExpectedTypes.cpp
   FindSymbols.cpp
   FileDistance.cpp
   FS.cpp
   FSProvider.cpp
+  FormattedString.cpp
   FuzzyMatch.cpp
   GlobalCompilationDatabase.cpp
   Headers.cpp
   IncludeFixer.cpp
   JSONTransport.cpp
   Logger.cpp
   Protocol.cpp
   Quality.cpp

clang-tools-extra/clangd/FormattedString.h

+//===--- FormattedString.h ----------------------------------*- 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
+//
+//===----------------------------------------------------------------------===//
+//
+// A simple intermediate representation of formatted text that could be
+// converted to plaintext or markdown.
+//
+//===----------------------------------------------------------------------===//
+#ifndef LLVM_CLANG_TOOLS_EXTRA_CLANGD_FORMATTEDSTRING_H
+#define LLVM_CLANG_TOOLS_EXTRA_CLANGD_FORMATTEDSTRING_H
+
+#include <string>
+#include <vector>
+
+namespace clang {
+namespace clangd {
+
+/// A structured string representation that could be converted to markdown or
+/// plaintext upon requrest.
+class FormattedString {
+public:
+  /// Append plain text to the end of the string.
+  void appendText(std::string Text);
+  /// Append a block of C++ code. This translates to a ``` block in markdown.
+  /// In a plain text representation, the code block will be surrounded by
+  /// newlines.
+  void appendCodeBlock(std::string Code, std::string Language = "cpp");
+  /// Append an inline block of C++ code. This translates to the ` block in
+  /// markdown.
+  /// EXPECTS: Code does not contain newlines.
+  void appendInlineCode(std::string Code);
+
+  std::string renderAsMarkdown() const;
+  std::string renderAsPlainText() const;
+
+private:
+  enum class ChunkKind {
+    PlainText,       /// A plain text paragraph.
+    CodeBlock,       /// A block of code.
+    InlineCodeBlock, /// An inline block of code.
+  };
+  struct Chunk {
+    ChunkKind Kind = ChunkKind::PlainText;
+    std::string Contents;
+    /// Language for code block chunks. Ignored for other chunks.
+    std::string Language;
+  };
+  std::vector<Chunk> Chunks;
+};
+
+} // 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/StringRef.h"
+#include "llvm/Support/ErrorHandling.h"
+#include <cstddef>
+#include <string>
+
+namespace clang {
+namespace clangd {
+
+namespace {
+/// Escape a markdown text block. Ensures the punctuation will not introduce
+/// any of the markdown constructs.
+static std::string renderText(llvm::StringRef Input) {
+  // Escaping ASCII punctiation ensures we can't start a markdown construct.
+  constexpr llvm::StringLiteral Punctuation =
+      R"txt(!"#$%&'()*+,-./:;<=>?@[\]^_`{|}~)txt";
+
+  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;
+  }
+  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.
+static std::string renderInlineBlock(llvm::StringRef Input) {
+  std::string R;
+  // Double all backticks to make sure we don't close the inline block early.
+  for (size_t From = 0; From < Input.size();) {
+    size_t Next = Input.find("`", From);
+    R += Input.substr(From, Next - From);
+    if (Next == llvm::StringRef::npos)
+      break;
+    R += "``"; // double the found backtick.
+
+    From = Next + 1;
+  }
+  // If results starts with a backtick, add spaces on both sides. The spaces
+  // are ignored by markdown renderers.
+  if (llvm::StringRef(R).startswith("`") || llvm::StringRef(R).endswith("`"))
+    return "` " + std::move(R) + " `";
+  // Markdown render should ignore first and last space if both are there. We
+  // add an extra pair of spaces in that case to make sure we render what the
+  // user intended.
+  if (llvm::StringRef(R).startswith(" ") && llvm::StringRef(R).endswith(" "))
+    return "` " + std::move(R) + " `";
+  return "`" + std::move(R) + "`";
+}
+/// Render \p Input as markdown code block with a specified \p Language. The
+/// result is surrounded by >= 3 backticks. Although markdown also allows to use
+/// '~' for code blocks, they are never used.
+static std::string renderCodeBlock(llvm::StringRef Input,
+                                   llvm::StringRef Language) {
+  // Count the maximum number of consecutive backticks in \p Input. We need to
+  // start and end the code block with more.
+  unsigned MaxBackticks = 0;
+  unsigned Backticks = 0;
+  for (char C : Input) {
+    if (C == '`') {
+      ++Backticks;
+      continue;
+    }
+    MaxBackticks = std::max(MaxBackticks, Backticks);
+    Backticks = 0;
+  }
+  MaxBackticks = std::max(Backticks, MaxBackticks);
+  // Use the corresponding number of backticks to start and end a code block.
+  std::string BlockMarker(/*Repeat=*/std::max(3u, MaxBackticks + 1), '`');
+  return BlockMarker + Language.str() + "\n" + Input.str() + "\n" + BlockMarker;
+}
+
+} // namespace
+
+void FormattedString::appendText(std::string Text) {
+  // We merge consecutive blocks of text to simplify the overall structure.
+  if (Chunks.empty() || Chunks.back().Kind != ChunkKind::PlainText) {
+    Chunk C;
+    C.Kind = ChunkKind::PlainText;
+    Chunks.push_back(C);
+  }
+  // FIXME: ensure there is a whitespace between the chunks.
+  Chunks.back().Contents += Text;
+}
+
+void FormattedString::appendCodeBlock(std::string Code, std::string Language) {
+  Chunk C;
+  C.Kind = ChunkKind::CodeBlock;
+  C.Contents = std::move(Code);
+  C.Language = std::move(Language);
+  Chunks.push_back(std::move(C));
+}
+
+void FormattedString::appendInlineCode(std::string Code) {
+  Chunk C;
+  C.Kind = ChunkKind::InlineCodeBlock;
+  C.Contents = std::move(Code);
+  Chunks.push_back(std::move(C));
+}
+
+std::string FormattedString::renderAsMarkdown() const {
+  std::string R;
+  for (const auto &C : Chunks) {
+    switch (C.Kind) {
+    case ChunkKind::PlainText:
+      R += renderText(C.Contents);
+      continue;
+    case ChunkKind::InlineCodeBlock:
+      // Make sure we don't glue two backticks together.
+      if (llvm::StringRef(R).endswith("`"))
+        R += " ";
+      R += renderInlineBlock(C.Contents);
+      continue;
+    case ChunkKind::CodeBlock:
+      if (!R.empty() && !llvm::StringRef(R).endswith("\n"))
+        R += "\n";
+      R += renderCodeBlock(C.Contents, C.Language);
+      R += "\n";
+      continue;
+    }
+    llvm_unreachable("unhanlded ChunkKind");
+  }
+  return R;
+}
+
+std::string FormattedString::renderAsPlainText() const {
+  std::string R;
+  auto EnsureWhitespace = [&]() {
+    if (R.empty() || isWhitespace(R.back()))
+      return;
+    R += " ";
+  };
+  for (const auto &C : Chunks) {
+    switch (C.Kind) {
+    case ChunkKind::PlainText:
+      EnsureWhitespace();
+      R += C.Contents;
+      continue;
+    case ChunkKind::InlineCodeBlock:
+      EnsureWhitespace();
+      R += C.Contents;
+      continue;
+    case ChunkKind::CodeBlock:
+      if (!R.empty())
+        R += "\n\n";
+      R += C.Contents;
+      if (!llvm::StringRef(C.Contents).endswith("\n"))
+        R += "\n";
+      continue;
+    }
+    llvm_unreachable("unhanlded ChunkKind");
+  }
+  while (!R.empty() && isWhitespace(R.back()))
+    R.pop_back();
+  return R;
+}
+} // namespace clangd
+} // namespace clang

clang-tools-extra/clangd/unittests/CMakeLists.txt

add_unittest(ClangdUnitTests ClangdTests
   ContextTests.cpp
   DexTests.cpp
   DiagnosticsTests.cpp
   DraftStoreTests.cpp
   ExpectedTypeTest.cpp
   FileDistanceTests.cpp
   FileIndexTests.cpp
   FindSymbolsTests.cpp
+  FormattedStringTests.cpp
   FSTests.cpp
   FunctionTests.cpp
   FuzzyMatchTests.cpp
   GlobalCompilationDatabaseTests.cpp
   HeadersTests.cpp
   IndexActionTests.cpp
   IndexTests.cpp
   JSONTransportTests.cpp

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

+//===-- FormattedStringTests.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
+//
+//===----------------------------------------------------------------------===//
+#include "FormattedString.h"
+#include "clang/Basic/LLVM.h"
+#include "llvm/ADT/StringRef.h"
+
+#include "gmock/gmock.h"
+#include "gtest/gtest.h"
+
+namespace clang {
+namespace clangd {
+namespace {
+
+TEST(FormattedString, Basic) {
+  FormattedString S;
+  EXPECT_EQ(S.renderAsPlainText(), "");
+  EXPECT_EQ(S.renderAsMarkdown(), "");
+
+  S.appendText("foobar");
+  EXPECT_EQ(S.renderAsPlainText(), "foobar");
+  EXPECT_EQ(S.renderAsMarkdown(), "foobar");
+
+  S = FormattedString();
+  S.appendInlineCode("foobar");
+  EXPECT_EQ(S.renderAsPlainText(), "foobar");
+  EXPECT_EQ(S.renderAsMarkdown(), "`foobar`");
+
+  S = FormattedString();
+  S.appendCodeBlock("foobar");
+  EXPECT_EQ(S.renderAsPlainText(), "foobar");
+  EXPECT_EQ(S.renderAsMarkdown(), "```cpp\n"
+                                  "foobar\n"
+                                  "```\n");
+}
+
+TEST(FormattedString, CodeBlocks) {
+  FormattedString S;
+  S.appendCodeBlock("foobar");
+  S.appendCodeBlock("bazqux", "javascript");
+
+  EXPECT_EQ(S.renderAsPlainText(), "foobar\n\n\nbazqux");
+  std::string ExpectedMarkdown = R"md(```cpp
+foobar
+```
+```javascript
+bazqux
+```
+)md";
+  EXPECT_EQ(S.renderAsMarkdown(), ExpectedMarkdown);
+
+  S = FormattedString();
+  S.appendInlineCode("foobar");
+  S.appendInlineCode("bazqux");
+  EXPECT_EQ(S.renderAsPlainText(), "foobar bazqux");
+  EXPECT_EQ(S.renderAsMarkdown(), "`foobar` `bazqux`");
+
+  S = FormattedString();
+  S.appendText("foo");
+  S.appendInlineCode("bar");
+  S.appendText("baz");
+
+  EXPECT_EQ(S.renderAsPlainText(), "foo bar baz");
+  EXPECT_EQ(S.renderAsMarkdown(), "foo`bar`baz");
+}
+
+TEST(FormattedString, Escaping) {
+  // Check some ASCII punctuation
+  FormattedString S;
+  S.appendText("*!`");
+  EXPECT_EQ(S.renderAsMarkdown(), "\\*\\!\\`");
+
+  // Check all ASCII punctuation.
+  S = FormattedString();
+  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;
+  S.appendText(Punctuation);
+  EXPECT_EQ(S.renderAsMarkdown(), EscapedPunctuation);
+
+  // In code blocks we don't need to escape ASCII punctuation.
+  S = FormattedString();
+  S.appendInlineCode("* foo !+ bar * baz");
+  EXPECT_EQ(S.renderAsMarkdown(), "`* foo !+ bar * baz`");
+  S = FormattedString();
+  S.appendCodeBlock("#define FOO\n* foo !+ bar * baz");
+  EXPECT_EQ(S.renderAsMarkdown(), "```cpp\n"
+                                  "#define FOO\n* foo !+ bar * baz\n"
+                                  "```\n");
+
+  // But we have to escape the backticks.
+  S = FormattedString();
+  S.appendInlineCode("foo`bar`baz");
+  EXPECT_EQ(S.renderAsMarkdown(), "`foo``bar``baz`");
+
+  S = FormattedString();
+  S.appendCodeBlock("foo`bar`baz");
+  EXPECT_EQ(S.renderAsMarkdown(), "```cpp\n"
+                                  "foo`bar`baz\n"
+                                  "```\n");
+
+  // Inline code blocks starting or ending with backticks should add spaces.
+  S = FormattedString();
+  S.appendInlineCode("`foo");
+  EXPECT_EQ(S.renderAsMarkdown(), "` ``foo `");
+  S = FormattedString();
+  S.appendInlineCode("foo`");
+  EXPECT_EQ(S.renderAsMarkdown(), "` foo`` `");
+  S = FormattedString();
+  S.appendInlineCode("`foo`");
+  EXPECT_EQ(S.renderAsMarkdown(), "` ``foo`` `");
+
+  // Should also add extra spaces if the block stars and ends with spaces.
+  S = FormattedString();
+  S.appendInlineCode(" foo ");
+  EXPECT_EQ(S.renderAsMarkdown(), "`  foo  `");
+  S = FormattedString();
+  S.appendInlineCode("foo ");
+  EXPECT_EQ(S.renderAsMarkdown(), "`foo `");
+  S = FormattedString();
+  S.appendInlineCode(" foo");
+  EXPECT_EQ(S.renderAsMarkdown(), "` foo`");
+
+  // Code blocks might need more than 3 backticks.
+  S = FormattedString();
+  S.appendCodeBlock("foobarbaz `\nqux");
+  EXPECT_EQ(S.renderAsMarkdown(), "```cpp\n"
+                                  "foobarbaz `\nqux\n"
+                                  "```\n");
+  S = FormattedString();
+  S.appendCodeBlock("foobarbaz ``\nqux");
+  EXPECT_EQ(S.renderAsMarkdown(), "```cpp\n"
+                                  "foobarbaz ``\nqux\n"
+                                  "```\n");
+  S = FormattedString();
+  S.appendCodeBlock("foobarbaz ```\nqux");
+  EXPECT_EQ(S.renderAsMarkdown(), "````cpp\n"
+                                  "foobarbaz ```\nqux\n"
+                                  "````\n");
+  S = FormattedString();
+  S.appendCodeBlock("foobarbaz ` `` ``` ```` `\nqux");
+  EXPECT_EQ(S.renderAsMarkdown(), "`````cpp\n"
+                                  "foobarbaz ` `` ``` ```` `\nqux\n"
+                                  "`````\n");
+}
+
+} // namespace
+} // namespace clangd
+} // namespace clang