[clangd] Revamp textDocument/onTypeFormatting.

[sammccall]

Summary

The existing implementation (which triggers on }) is fairly simple and
has flaws:

• doesn't trigger frequently/regularly enough (particularly in editors that type the } for you)
• often reformats too much code around the edit
• has jarring cases that I don't have clear ideas for fixing

This implementation is designed to trigger on newline, which feels to me more
intuitive than } or ;.
It does have allow for reformatting after other characters - it has a
basic behavior and a model for adding specialized behavior for
particular characters. But at least initially I'd stick to advertising
\n in the capabilities.

This also handles comment splitting: when you insert a line break inside
a line comment, it will make the new line into an aligned line comment.

Working on tests, but want people to patch it in and try it - it's hard to
see if "feel" is right purely by looking at a test.

[sammccall]

Unit tests.

[sammccall]

Lots more test cases and better handling of braced blocks.

This turns out to be an interesting case:

if (foo) {
^}

Really the right thing to do here is insert another newline.
Unfortuantely that means inserting text before and after the cursor, which
confuses tooling::Replacements so... lots of churn in this patch :-(

[sammccall]

@kadircet if you're interested in the behavior here, you can patch this in and try out with vscode.

[ilya-biryukov]

Found an issue today.

Input (break a line at ^):

// here is my comment ^// another comment

Expected:

// here is my comment
^// another comment

Actual (an extra comment marker is added):

// here is my comment
// // another comment

[sammccall]

Fix comment wrapping behavior:

• when splitting a comment before , don't add another
• if the editor inserts // before the cursor to continue a line comment, indent it and adjust to three slashes if needed.

This doesn't mean enter at the *end* of a comment will continue the comment,
but if editors do that (vim does) then it will be respected.

[ilya-biryukov]

Another example:

int test() {

  ^
}

Expected: a newline was added.
Actual: newline does not allow to be added.

[ilya-biryukov]

Input:

int test() {
}^

Expected:

int test() {
}
^

Actual:

int test() {}
^

[sammccall]

Avoid removing lines when formatting after \n.

[sammccall]

In D60605#1478579, @ilya-biryukov wrote:

Another example:

int test() {

  ^
}

Expected: a newline was added.
Actual: newline does not allow to be added.

Fixed.

In D60605#1478581, @ilya-biryukov wrote:

Input:

int test() {
}^

Actual:

int test() {}
^

I really do think this is the right thing in particular if you typed the brace.
It's visually confusing that hitting \n results in the cursor staying on the same line and the } moving.
And this interacts badly with the previous bug.
But can you see if this is something you could live with, and if not, explain why you don't want the {} formatted?

[ilya-biryukov]

In D60605#1478922, @sammccall wrote:

In D60605#1478581, @ilya-biryukov wrote:

Input:

int test() {
}^

Actual:

int test() {}
^

I really do think this is the right thing in particular if you typed the brace.
It's visually confusing that hitting \n results in the cursor staying on the same line and the } moving.
And this interacts badly with the previous bug.
But can you see if this is something you could live with, and if not, explain why you don't want the {} formatted?

In general, I have high tolerance for quirks in IDE features. But this one really makes me itchy. I'd say clangd should never remove lines while I'm trying to add them. Are there examples where this behavior is useful?

[ilya-biryukov]

Input:

// this is my comment. ^
// and it continues on the next line.

Expected:

// this is my comment.
// ^
// and it continues on the next line.

Actual:

// this is my comment.
^
// and it continues on the next line.

[ilya-biryukov]

Input:

if (something)
  foo; // a comment^

Expected:

if (something)
  foo; // a comment
^

Actual (indented to align with a comment):

if (something)
  foo; // a comment
       ^

[sammccall]

Fix more comment contination cases.

[ilya-biryukov]

Found today:

if (something)
  return; // some long comment
          // that takes two lines.^

Expected: comment on last line is not re-indented.
Actual (comment re-indented):

if (something)
  return; // some long comment
// that takes two lines.

[sammccall]

In D60605#1483729, @ilya-biryukov wrote:

Found today:

I'm not able to reproduce this, can you give a complete example?

[ilya-biryukov]

In D60605#1485375, @sammccall wrote:

I'm not able to reproduce this, can you give a complete example?

After adding a newline here:

int test(bool x) {
  if (x)
    return 10; // All spelled tokens are accounted for.
               // that takes two lines^
}

I get:

int test(bool x) {
  if (x)
    return 10; // All spelled tokens are accounted for.
  // that takes two lines
  ^
}

Maybe that's due to some extra logic applied in VSCode on top of what we do.
Let me know if this does not reproduce.

[sammccall]

Fix latest case (trailing comment outdented in vscode).

[sammccall]

In D60605#1488039, @ilya-biryukov wrote:

Maybe that's due to some extra logic applied in VSCode on top of what we do.
Let me know if this does not reproduce.

Aha, the missing piece was that vscode reindented the cursor to align with the comment (but didn't continue the comment).
This caused us to replace the cursor with an *indented* identifier, and clang-format thought the last line of the comment was attached to it.

It almost seems silly to keep patching the code rather than add a "break here" option to clang-format that doesn't have side-effects. However the fix here is pretty simple, so why not.

Do you think this is converging to something we should land? The last few have been pretty small tweaks and I'm happy to keep fixing those as incremental patches.
Conversely, if the basic design isn't right, then further polish probably isn't worthwhile.

[ilya-biryukov]

Sorry for the delay, I'll make sure to take a close look at the change tomorrow.

As mentioned in offline discussions, doing this through clang-format seems like the right approach. At the same the markers we put into the files to drive formatting seem fragile, giving results we don't want.
The biggest issue that I can see is that it's super-hard to predict what clang-format is going to do in each case and even harder to certify that this should work in general case.

Intuitively, moving the logic to clang-format seems like the right thing to do in the long run (e.g. introducing a special cursor marker into clang-format, similar a code completion marker used by clang or something similar).
OTOH, it's hard for me to asses the amount of work needed to do this inside clang-format itself (not a clang-format expert), and the patch is definitely an improvement to what we had before (I've been using it for awhile now). The problems do get fixed, so I'm totally happy with it landing as is if we commit to fixing those nasty cases until we run out of them.

PS. In the meantime, I've found another case where newline gets eaten:

class SyntaxTreeTest {
public:
  ^ 
};

Expected: newline is added.
Actual: does not let to add a newline (the added newline is removed).

[yvvan]

@ilya-biryukov
What do you think about D53072? It can be polished and combined with this change removing some code from here (which I assume is a good thing).
The idea there is that clang-format knows that it's not allowed to remove new lines and it always marks them with MustBreakBefore.
I'm not sure if anybody needs an executable but I think it's not a big deal to have an extra reformat() function.

It is also safe because it was the only way I found which does not break the code style like, for instance, adding comment block to the end of the previous line.

[ilya-biryukov]

In D60605#1495268, @yvvan wrote:

@ilya-biryukov
What do you think about D53072? It can be polished and combined with this change removing some code from here (which I assume is a good thing).
The idea there is that clang-format knows that it's not allowed to remove new lines and it always marks them with MustBreakBefore.
I'm not sure if anybody needs an executable but I think it's not a big deal to have an extra reformat() function.

It is also safe because it was the only way I found which does not break the code style like, for instance, adding comment block to the end of the previous line.

I also think (both Sam and you seem to agree with this) that we'll definitely need changes to clang-format to support this use-case.
Also sympathetic to the view that this change should probably live in clang-format, but having it in clangd first and moving to clang-format later also LG.
@sammccall, what's your plan there? Experimenting in clangd and moving to clang-format later? Any reason to not start in clang-format in the first place?

Will add a few comments regarding the need for a separate tool in D53072 directly.

[ilya-biryukov]

LGTM with a few NITs and a few questions about the possibility of moving this to clang-format at some point in the future.
From what I can to simplify the calling, we need to:

1. teach clang-format about a cursor (by making it a special token or somehow else), this would allow to avoid some book-keeping;
2. teach clang-format to format in presence of unmatched parentheses. Again, would simplify things. Although not sure it's easy to do in clang-format either;
3. teach clang-format to respect indentation before the cursor (added by the editor in our case).

After that we don't seem to need the complicated multi-pass replacements.

• Am I missing something that we also need from clang-format here?
• How would you estimate the amount of work needed to move this functionality to clang-format?
• In general, do you think it's worth moving it there or not?

clangd/Format.cpp

84

NIT: put a comment about filename being required but ignored here to explain why we need this variable.

clangd/Format.h

26

NIT: maybe be more concrete? near \p Cursor means right before \p Cursor? Or can it have other characters (e.g. whitespace in your example)?

[sammccall]

OK, this has been stuck for a while and (as discussed a bit offline) I haven't been able to make the alternative approaches work.

In D60605#1495268, @yvvan wrote:

@ilya-biryukov
What do you think about D53072? It can be polished and combined with this change removing some code from here (which I assume is a good thing).
The idea there is that clang-format knows that it's not allowed to remove new lines and it always marks them with MustBreakBefore.
I'm not sure if anybody needs an executable but I think it's not a big deal to have an extra reformat() function.

It is also safe because it was the only way I found which does not break the code style like, for instance, adding comment block to the end of the previous line.

I'm not sure D53072 helps in its current form. Preserving newlines with content on the line isn't always the (IMO) right formatting: see e.g. FormatBrace test.
(I have other concerns about the details of that patch, but they don't really relate to this one).

In D60605#1518031, @ilya-biryukov wrote:

LGTM with a few NITs and a few questions about the possibility of moving this to clang-format at some point in the future.
From what I can to simplify the calling, we need to:

1. teach clang-format about a cursor (by making it a special token or somehow else), this would allow to avoid some book-keeping;

There's at least one wrinkle with making it a special token: it may be within a token. E.g. after splitting a line comment, the cursor is at offset 3 within // the new line. Not sure how deep this problem goes.

2. teach clang-format to format in presence of unmatched parentheses. Again, would simplify things. Although not sure it's easy to do in clang-format either;

Note this needs to be a style or other option, as the fact that clang-format bails out on broken code in general is well-established desired behavior.
I attempted this (by having the parser return "true" rather than "false" on reaching the end of a paren/brace list, and got lost in the details. I'm not sure whether it's likely to work, or whether clang-format would just do the same source transformation as we do here. (Obviously sharing it would be nice).

3. teach clang-format to respect indentation before the cursor (added by the editor in our case).

I'm not sure what you mean by this: I don't think we want that indentation to be respected, but rather reformatted away.

After that we don't seem to need the complicated multi-pass replacements.

We currently have pre-formatting changes (e.g. comment splitting). I'm not sure if you expect these to belong to clang-format, but I wouldn't. (They're more like a "respond to newline" helper for editors than they are like formatting a range). So you'd go from {pre-formatting changes, insert placeholder, clang-format, remove placeholder} to {pre-formatting changes, clang-format}.
So the logic to implement multi-pass replacements is still needed I think, though you'd have fewer actual passes.

• Am I missing something that we also need from clang-format here?

The comment splitting and {} splitting, I think.

• How would you estimate the amount of work needed to move this functionality to clang-format?
• In general, do you think it's worth moving it there or not?

I don't know, I put maybe 8 hours into this approach and didn't make any progress.
If someone finds a clean way to do it, I'd be in favour. But a hacky/brute-force way would do more harm than good in my opinion.

In the meantime, I've found another case where newline gets eaten:

Yes :-(
I've added a test to document this bad behavior. It's very hard to fix with clang-format as a black-box, because it hard-codes erasure of blank lines adjacent to a formatted region.
Probably the simplest approach is to add a clang-format option to always preserve blank lines. Although the motivation isn't an actual style guide, it makes sense to think of this as a style rule, it's very simple, and it's related to existing options.

clangd/Format.h

26

s/near/before/.
Yes, it can have other characters, these are already mentioned in the comment.

clangd/CMakeLists.txt

add_clang_library(clangDaemon
   CodeCompletionStrings.cpp
   Compiler.cpp
   Context.cpp
   Diagnostics.cpp
   DraftStore.cpp
   ExpectedTypes.cpp
   FindSymbols.cpp
   FileDistance.cpp
+  Format.cpp
   FS.cpp
   FSProvider.cpp
   FuzzyMatch.cpp
   GlobalCompilationDatabase.cpp
   Headers.cpp
   IncludeFixer.cpp
   JSONTransport.cpp
   Logger.cpp

clangd/ClangdLSPServer.cpp

void ClangdLSPServer::onInitialize(const InitializeParams &Params,
   llvm::json::Object Result{
       {{"capabilities",
         llvm::json::Object{
             {"textDocumentSync", (int)TextDocumentSyncKind::Incremental},
             {"documentFormattingProvider", true},
             {"documentRangeFormattingProvider", true},
             {"documentOnTypeFormattingProvider",
              llvm::json::Object{
-                 {"firstTriggerCharacter", "}"},
+                 {"firstTriggerCharacter", "\n"},
                  {"moreTriggerCharacter", {}},
              }},
             {"codeActionProvider", true},
             {"completionProvider",
              llvm::json::Object{
                  {"resolveProvider", false},
                  // We do extra checks for '>' and ':' in completion to only
                  // trigger on '->' and '::'.
void ClangdLSPServer::onDocumentOnTypeFormatting(
     Callback<std::vector<TextEdit>> Reply) {
   auto File = Params.textDocument.uri.file();
   auto Code = DraftMgr.getDraft(File);
   if (!Code)
     return Reply(llvm::make_error<LSPError>(
         "onDocumentOnTypeFormatting called for non-added file",
         ErrorCode::InvalidParams));
 
-  auto ReplacementsOrError = Server->formatOnType(*Code, File, Params.position);
-  if (ReplacementsOrError)
-    Reply(replacementsToEdits(*Code, ReplacementsOrError.get()));
-  else
-    Reply(ReplacementsOrError.takeError());
+  Reply(Server->formatOnType(*Code, File, Params.position, Params.ch));
 }
 
 void ClangdLSPServer::onDocumentRangeFormatting(
     const DocumentRangeFormattingParams &Params,
     Callback<std::vector<TextEdit>> Reply) {
   auto File = Params.textDocument.uri.file();
   auto Code = DraftMgr.getDraft(File);
   if (!Code)

clangd/ClangdServer.h

public:
   /// Run formatting for \p Rng inside \p File with content \p Code.
   llvm::Expected<tooling::Replacements> formatRange(StringRef Code,
                                                     PathRef File, Range Rng);
 
   /// Run formatting for the whole \p File with content \p Code.
   llvm::Expected<tooling::Replacements> formatFile(StringRef Code,
                                                    PathRef File);
 
-  /// Run formatting after a character was typed at \p Pos in \p File with
+  /// Run formatting after \p TriggerText was typed at \p Pos in \p File with
   /// content \p Code.
-  llvm::Expected<tooling::Replacements>
-  formatOnType(StringRef Code, PathRef File, Position Pos);
+  llvm::Expected<std::vector<TextEdit>> formatOnType(StringRef Code,
+                                                     PathRef File, Position Pos,
+                                                     StringRef TriggerText);
 
   /// Rename all occurrences of the symbol at the \p Pos in \p File to
   /// \p NewName.
   void rename(PathRef File, Position Pos, llvm::StringRef NewName,
               Callback<std::vector<TextEdit>> CB);
 
   struct TweakRef {
     std::string ID;    /// ID to pass for applyTweak.

clangd/ClangdServer.cpp

 //===--- ClangdServer.cpp - Main clangd server code --------------*- 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 "ClangdServer.h"
 #include "ClangdUnit.h"
 #include "CodeComplete.h"
 #include "FindSymbols.h"
+#include "Format.h"
 #include "Headers.h"
 #include "Protocol.h"
 #include "SourceCode.h"
 #include "TUScheduler.h"
 #include "Trace.h"
 #include "index/CanonicalIncludes.h"
 #include "index/FileIndex.h"
 #include "index/Merge.h"

 }
 
 llvm::Expected<tooling::Replacements>
 ClangdServer::formatFile(llvm::StringRef Code, PathRef File) {
   // Format everything.
   return formatCode(Code, File, {tooling::Range(0, Code.size())});
 }
 
-llvm::Expected<tooling::Replacements>
-ClangdServer::formatOnType(llvm::StringRef Code, PathRef File, Position Pos) {
-  // Look for the previous opening brace from the character position and
-  // format starting from there.
+llvm::Expected<std::vector<TextEdit>>
+ClangdServer::formatOnType(llvm::StringRef Code, PathRef File, Position Pos,
+                           StringRef TriggerText) {
   llvm::Expected<size_t> CursorPos = positionToOffset(Code, Pos);
   if (!CursorPos)
     return CursorPos.takeError();
-  size_t PreviousLBracePos =
-      llvm::StringRef(Code).find_last_of('{', *CursorPos);
-  if (PreviousLBracePos == llvm::StringRef::npos)
-    PreviousLBracePos = *CursorPos;
-  size_t Len = *CursorPos - PreviousLBracePos;
+  auto FS = FSProvider.getFileSystem();
+  auto Style = format::getStyle(format::DefaultFormatStyle, File,
+                                format::DefaultFallbackStyle, Code, FS.get());
+  if (!Style)
+    return Style.takeError();
 
-  return formatCode(Code, File, {tooling::Range(PreviousLBracePos, Len)});
+  std::vector<TextEdit> Result;
+  for (const tooling::Replacement &R :
+       formatIncremental(Code, *CursorPos, TriggerText, *Style))
+    Result.push_back(replacementToEdit(Code, R));
+  return Result;
 }
 
 void ClangdServer::rename(PathRef File, Position Pos, llvm::StringRef NewName,
                           Callback<std::vector<TextEdit>> CB) {
   auto Action = [Pos](Path File, std::string NewName,
                       Callback<std::vector<TextEdit>> CB,
                       llvm::Expected<InputsAndAST> InpAST) {
     if (!InpAST)

clangd/Format.h

+//===--- Format.h - automatic code formatting ---------------*- 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
+//
+//===----------------------------------------------------------------------===//
+//
+// Clangd uses clang-format for formatting operations.
+// This file adapts it to support new scenarios like format-on-type.
+//
+//===----------------------------------------------------------------------===//
+#ifndef LLVM_CLANG_TOOLS_EXTRA_CLANGD_FORMAT_H
+#define LLVM_CLANG_TOOLS_EXTRA_CLANGD_FORMAT_H
+
+#include "Protocol.h"
+#include "clang/Format/Format.h"
+#include "clang/Tooling/Core/Replacement.h"
+#include "llvm/ADT/StringRef.h"
+
+namespace clang {
+namespace clangd {
+
+/// Applies limited formatting around new \p InsertedText.
+/// The \p Code already contains the updated text near \p Cursor, and may have
+/// had additional / characters (such as indentation) inserted by the editor.
+///
+/// Example breaking a line (^ is the cursor):
+/// === before newline is typed ===
+/// if(1){^}
+/// === after newline is typed and editor indents ===
+/// if(1){
+///   ^}
+/// === after formatIncremental(InsertedText="\n") ===
+/// if (1) {
+///   ^
+/// }
+///
+/// We return sorted vector<tooling::Replacement>, not tooling::Replacements!
+/// We may insert text both before and after the cursor. tooling::Replacements
+/// would merge these, and thus lose information about cursor position.
+std::vector<tooling::Replacement>
+formatIncremental(llvm::StringRef Code, unsigned Cursor,
+                  llvm::StringRef InsertedText, format::FormatStyle Style);
+
+/// Determine the new cursor position after applying \p Replacements.
+/// Analogue of tooling::Replacements::getShiftedCodePosition().
+unsigned
+transformCursorPosition(unsigned Offset,
+                        const std::vector<tooling::Replacement> &Replacements);
+
+} // namespace clangd
+} // namespace clang
+
+#endif
+

clangd/Format.cpp

+//===--- Format.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 "Format.h"
+#include "Logger.h"
+#include "clang/Basic/SourceManager.h"
+#include "clang/Format/Format.h"
+#include "clang/Lex/Lexer.h"
+#include "clang/Tooling/Core/Replacement.h"
+#include "llvm/Support/Unicode.h"
+
+namespace clang {
+namespace clangd {
+namespace {
+
+/// Append closing brackets )]} to \p Code to make it well-formed.
+/// Clang-format conservatively refuses to format files with unmatched brackets
+/// as it isn't sure where the errors are and so can't correct.
+/// When editing, it's reasonable to assume code before the cursor is complete.
+void closeBrackets(std::string &Code, const format::FormatStyle &Style) {
+  SourceManagerForFile FileSM("dummy.cpp", Code);
+  auto &SM = FileSM.get();
+  FileID FID = SM.getMainFileID();
+  Lexer Lex(FID, SM.getBuffer(FID), SM, format::getFormattingLangOpts(Style));
+  Token Tok;
+  std::vector<char> Brackets;
+  while (!Lex.LexFromRawLexer(Tok)) {
+    switch(Tok.getKind()) {
+      case tok::l_paren:
+        Brackets.push_back(')');
+        break;
+      case tok::l_brace:
+        Brackets.push_back('}');
+        break;
+      case tok::l_square:
+        Brackets.push_back(']');
+        break;
+      case tok::r_paren:
+        if (!Brackets.empty() && Brackets.back() == ')')
+          Brackets.pop_back();
+        break;
+      case tok::r_brace:
+        if (!Brackets.empty() && Brackets.back() == '}')
+          Brackets.pop_back();
+        break;
+      case tok::r_square:
+        if (!Brackets.empty() && Brackets.back() == ']')
+          Brackets.pop_back();
+        break;
+      default:
+        continue;
+    }
+  }
+  // Attempt to end any open comments first.
+  Code.append("\n// */\n");
+  Code.append(Brackets.rbegin(), Brackets.rend());
+}
+
+static StringRef commentMarker(llvm::StringRef Line) {
+  for (StringRef Marker : {"///", "//"}){
+    auto I = Line.rfind(Marker);
+    if (I != StringRef::npos)
+      return Line.substr(I, Marker.size());
+  }
+  return "";
+}
+
+llvm::StringRef firstLine(llvm::StringRef Code) {
+  return Code.take_until([](char C) { return C == '\n'; });
+}
+
+llvm::StringRef lastLine(llvm::StringRef Code) {
+  llvm::StringRef Rest = Code;
+  while (!Rest.empty() && Rest.back() != '\n')
+    Rest = Rest.drop_back();
+  return Code.substr(Rest.size());
+}
+
+llvm::StringRef Filename = "<stdin>";
+
+// tooling::Replacement from overlapping StringRefs: From must be part of Code.
+tooling::Replacement replacement(llvm::StringRef Code, llvm::StringRef From,
+                                 llvm::StringRef To) {
+  assert(From.begin() >= Code.begin() && From.end() <= Code.end());
+  // The filename is required but ignored.
+  return tooling::Replacement(Filename, From.data() - Code.data(),
+                              From.size(), To);
+};
+
+// High-level representation of incremental formatting changes.
+// The changes are made in two steps.
+// 1) a (possibly-empty) set of changes synthesized by clangd (e.g. adding
+//    comment markers when splitting a line comment with a newline).
+// 2) a selective clang-format run:
+//    - the "source code" passed to clang format is the code up to the cursor,
+//      a placeholder for the cursor, and some closing brackets
+//    - the formatting is restricted to the cursor and (possibly) other ranges
+//      (e.g. the old line when inserting a newline).
+//    - changes before the cursor are applied, those after are discarded.
+struct IncrementalChanges {
+  // Changes that should be applied before running clang-format.
+  tooling::Replacements Changes;
+  // Ranges of the original source code that should be clang-formatted.
+  // The CursorProxyText will also be formatted.
+  std::vector<tooling::Range> FormatRanges;
+  // The source code that should stand in for the cursor when clang-formatting.
+  // e.g. after inserting a newline, a line-comment at the cursor is used to
+  // ensure that the newline is preserved.
+  std::string CursorPlaceholder;
+};
+
+// After a newline:
+//  - we continue any line-comment that was split
+//  - we format the old line in addition to the cursor
+//  - we represent the cursor with a line comment to preserve the newline
+IncrementalChanges getIncrementalChangesAfterNewline(llvm::StringRef Code,
+                                                     unsigned Cursor) {
+  IncrementalChanges Result;
+  // Before newline, code looked like:
+  //    leading^trailing
+  // After newline, code looks like:
+  //    leading
+  //    indentation^trailing
+  // Where indentation was added by the editor.
+  StringRef Trailing = firstLine(Code.substr(Cursor));
+  StringRef Indentation = lastLine(Code.take_front(Cursor));
+  if (Indentation.data() == Code.data()) {
+    vlog("Typed a newline, but we're still on the first line!");
+    return Result;
+  }
+  StringRef Leading =
+      lastLine(Code.take_front(Indentation.data() - Code.data() - 1));
+  StringRef NextLine = firstLine(Code.substr(Cursor + Trailing.size() + 1));
+
+  // Strip leading whitespace on trailing line.
+  StringRef TrailingTrim = Trailing.ltrim();
+  if (unsigned TrailWS = Trailing.size() - TrailingTrim.size())
+    cantFail(Result.Changes.add(
+        replacement(Code, StringRef(Trailing.begin(), TrailWS), "")));
+
+  // If we split a comment, replace indentation with a comment marker.
+  // If the editor made the new line a comment, also respect that.
+  StringRef CommentMarker = commentMarker(Leading);
+  bool NewLineIsComment = !commentMarker(Indentation).empty();
+  if (!CommentMarker.empty() &&
+      (NewLineIsComment || !commentMarker(NextLine).empty() ||
+       (!TrailingTrim.empty() && !TrailingTrim.startswith("//")))) {
+    using llvm::sys::unicode::columnWidthUTF8;
+    // We indent the new comment to match the previous one.
+    StringRef PreComment =
+        Leading.take_front(CommentMarker.data() - Leading.data());
+    std::string IndentAndComment =
+        (std::string(columnWidthUTF8(PreComment), ' ') + CommentMarker + " ")
+            .str();
+    cantFail(
+        Result.Changes.add(replacement(Code, Indentation, IndentAndComment)));
+  }
+
+  // If we put a the newline inside a {} pair, put } on its own line...
+  if (CommentMarker.empty() && Leading.endswith("{") &&
+      Trailing.startswith("}")) {
+    cantFail(
+        Result.Changes.add(replacement(Code, Trailing.take_front(1), "\n}")));
+    // ...and format it.
+    Result.FormatRanges.push_back(
+        tooling::Range(Trailing.data() - Code.data() + 1, 1));
+  }
+
+  // Format the whole leading line.
+  Result.FormatRanges.push_back(
+      tooling::Range(Leading.data() - Code.data(), Leading.size()));
+
+  // We use a comment to represent the cursor, to preserve the newline.
+  // A trailing identifier improves parsing of e.g. for without braces.
+  // Exception: if the previous line has a trailing comment, we can't use one
+  // as the cursor (they will be aligned). But in this case we don't need to.
+  Result.CursorPlaceholder = !CommentMarker.empty() ? "ident" : "//==\nident";
+
+  return Result;
+}
+
+IncrementalChanges getIncrementalChanges(llvm::StringRef Code, unsigned Cursor,
+                                         llvm::StringRef InsertedText) {
+  IncrementalChanges Result;
+  if (InsertedText == "\n")
+    return getIncrementalChangesAfterNewline(Code, Cursor);
+
+  Result.CursorPlaceholder = " /**/";
+  return Result;
+}
+
+// Returns equivalent replacements that preserve the correspondence between
+// OldCursor and NewCursor. If OldCursor lies in a replaced region, that
+// replacement will be split.
+std::vector<tooling::Replacement>
+split(const tooling::Replacements &Replacements, unsigned OldCursor,
+      unsigned NewCursor) {
+  std::vector<tooling::Replacement> Result;
+  int LengthChange = 0;
+  for (const tooling::Replacement &R : Replacements) {
+    if (R.getOffset() + R.getLength() <= OldCursor) { // before cursor
+      Result.push_back(R);
+      LengthChange += R.getReplacementText().size() - R.getLength();
+    } else if (R.getOffset() < OldCursor) { // overlaps cursor
+      int ReplacementSplit = NewCursor - LengthChange - R.getOffset();
+      assert(ReplacementSplit >= 0 &&
+             ReplacementSplit <= int(R.getReplacementText().size()) &&
+             "NewCursor incompatible with OldCursor!");
+      Result.push_back(tooling::Replacement(
+          R.getFilePath(), R.getOffset(), OldCursor - R.getOffset(),
+          R.getReplacementText().take_front(ReplacementSplit)));
+      Result.push_back(tooling::Replacement(
+          R.getFilePath(), OldCursor,
+          R.getLength() - (OldCursor - R.getOffset()),
+          R.getReplacementText().drop_front(ReplacementSplit)));
+    } else if (R.getOffset() >= OldCursor) { // after cursor
+      Result.push_back(R);
+    }
+  }
+  return Result;
+}
+
+} // namespace
+
+// We're simulating the following sequence of changes:
+//   - apply the pre-formatting edits (see getIncrementalChanges)
+//   - insert a placeholder for the cursor
+//   - format some of the resulting code
+//   - remove the cursor placeholder again
+// The replacements we return are produced by composing these.
+//
+// The text we actually pass to clang-format is slightly different from this,
+// e.g. we have to close brackets. We ensure these differences are *after*
+// all the regions we want to format, and discard changes in them.
+std::vector<tooling::Replacement>
+formatIncremental(llvm::StringRef OriginalCode, unsigned OriginalCursor,
+                  llvm::StringRef InsertedText, format::FormatStyle Style) {
+  IncrementalChanges Incremental =
+      getIncrementalChanges(OriginalCode, OriginalCursor, InsertedText);
+  // Never *remove* lines in response to pressing enter! This annoys users.
+  if (InsertedText == "\n") {
+    Style.MaxEmptyLinesToKeep = 1000;
+    Style.KeepEmptyLinesAtTheStartOfBlocks = true;
+  }
+
+  // Compute the code we want to format:
+  // 1) Start with code after the pre-formatting edits.
+  std::string CodeToFormat = cantFail(
+      tooling::applyAllReplacements(OriginalCode, Incremental.Changes));
+  unsigned Cursor = Incremental.Changes.getShiftedCodePosition(OriginalCursor);
+  // 2) Truncate code after the last interesting range.
+  unsigned FormatLimit = Cursor;
+  for (tooling::Range &R : Incremental.FormatRanges)
+    FormatLimit = std::max(FormatLimit, R.getOffset() + R.getLength());
+  CodeToFormat.resize(FormatLimit);
+  // 3) Insert a placeholder for the cursor.
+  CodeToFormat.insert(Cursor, Incremental.CursorPlaceholder);
+  // 4) Append brackets after FormatLimit so the code is well-formed.
+  closeBrackets(CodeToFormat, Style);
+
+  // Determine the ranges to format:
+  std::vector<tooling::Range> RangesToFormat = Incremental.FormatRanges;
+  // Ranges after the cursor need to be adjusted for the placeholder.
+  for (auto &R : RangesToFormat) {
+    if (R.getOffset() > Cursor)
+      R = tooling::Range(R.getOffset() + Incremental.CursorPlaceholder.size(),
+                         R.getLength());
+  }
+  // We also format the cursor.
+  RangesToFormat.push_back(
+      tooling::Range(Cursor, Incremental.CursorPlaceholder.size()));
+  // Also update FormatLimit for the placeholder, we'll use this later.
+  FormatLimit += Incremental.CursorPlaceholder.size();
+
+  // Run clang-format, and truncate changes at FormatLimit.
+  tooling::Replacements FormattingChanges;
+  format::FormattingAttemptStatus Status;
+  for (const tooling::Replacement &R : format::reformat(
+           Style, CodeToFormat, RangesToFormat, Filename, &Status)) {
+    if (R.getOffset() + R.getLength() <= FormatLimit) // Before limit.
+      cantFail(FormattingChanges.add(R));
+    else if(R.getOffset() < FormatLimit) { // Overlaps limit.
+      if (R.getReplacementText().empty()) // Deletions are easy to handle.
+        cantFail(FormattingChanges.add(tooling::Replacement(Filename,
+            R.getOffset(), FormatLimit - R.getOffset(), "")));
+      else
+        // Hopefully won't happen in practice?
+        elog("Incremental clang-format edit overlapping cursor @ {0}!\n{1}",
+             Cursor, CodeToFormat);
+    }
+  }
+  if (!Status.FormatComplete)
+    vlog("Incremental format incomplete at line {0}", Status.Line);
+
+  // Now we are ready to compose the changes relative to OriginalCode.
+  //   edits -> insert placeholder -> format -> remove placeholder.
+  // We must express insert/remove as Replacements.
+  tooling::Replacements InsertCursorPlaceholder(
+      tooling::Replacement(Filename, Cursor, 0, Incremental.CursorPlaceholder));
+  unsigned FormattedCursorStart =
+               FormattingChanges.getShiftedCodePosition(Cursor),
+           FormattedCursorEnd = FormattingChanges.getShiftedCodePosition(
+               Cursor + Incremental.CursorPlaceholder.size());
+  tooling::Replacements RemoveCursorPlaceholder(
+      tooling::Replacement(Filename, FormattedCursorStart,
+                           FormattedCursorEnd - FormattedCursorStart, ""));
+
+  // We can't simply merge() and return: tooling::Replacements will combine
+  // adjacent edits left and right of the cursor. This gives the right source
+  // code, but loses information about where the cursor is!
+  // Fortunately, none of the individual passes lose information, so:
+  //  - we use merge() to compute the final Replacements
+  //  - we chain getShiftedCodePosition() to compute final cursor position
+  //  - we split the final Replacements at the cursor position, so that
+  //    each Replacement lies either before or after the cursor.
+  tooling::Replacements Final;
+  unsigned FinalCursor = OriginalCursor;
+#ifndef NDEBUG
+  std::string FinalCode = OriginalCode;
+  dlog("Initial code: {0}", FinalCode);
+#endif
+  for (auto Pass :
+       std::vector<std::pair<const char *, const tooling::Replacements *>>{
+           {"Pre-formatting changes", &Incremental.Changes},
+           {"Insert placeholder", &InsertCursorPlaceholder},
+           {"clang-format", &FormattingChanges},
+           {"Remove placeholder", &RemoveCursorPlaceholder}}) {
+    Final = Final.merge(*Pass.second);
+    FinalCursor = Pass.second->getShiftedCodePosition(FinalCursor);
+#ifndef NDEBUG
+    FinalCode =
+        cantFail(tooling::applyAllReplacements(FinalCode, *Pass.second));
+    dlog("After {0}:\n{1}^{2}", Pass.first,
+         StringRef(FinalCode).take_front(FinalCursor),
+         StringRef(FinalCode).drop_front(FinalCursor));
+#endif
+  }
+  return split(Final, OriginalCursor, FinalCursor);
+}
+
+unsigned
+transformCursorPosition(unsigned Offset,
+                        const std::vector<tooling::Replacement> &Replacements) {
+  unsigned OriginalOffset = Offset;
+  for (const auto &R : Replacements) {
+    if (R.getOffset() + R.getLength() <= OriginalOffset) {
+      // Replacement is before cursor.
+      Offset += R.getReplacementText().size();
+      Offset -= R.getLength();
+    } else if (R.getOffset() < OriginalOffset) {
+      // Replacement overlaps cursor.
+      // Preserve position within replacement text, as far as possible.
+      unsigned PositionWithinReplacement = Offset - R.getOffset();
+      if (PositionWithinReplacement > R.getReplacementText().size()) {
+        Offset += R.getReplacementText().size();
+        Offset -= PositionWithinReplacement;
+      }
+    } else {
+      // Replacement after cursor.
+      break; // Replacements are sorted, the rest are also after the cursor.
+    }
+  }
+  return Offset;
+}
+
+}
+} // namespace clang

test/clangd/formatting.test

 ---
 {"jsonrpc":"2.0","method":"textDocument/didChange","params":{"textDocument":{"uri":"test:///foo.c","version":9},"contentChanges":[{"text":"int foo(int x) {\n  x = x + 1;\n  return x;\n}"}]}}
 ---
 {"jsonrpc":"2.0","id":4,"method":"textDocument/formatting","params":{"textDocument":{"uri":"test:///foo.c"},"options":{"tabSize":4,"insertSpaces":true}}}
 #      CHECK:  "id": 4,
 # CHECK-NEXT:  "jsonrpc": "2.0",
 # CHECK-NEXT:  "result": []
 ---
-{"jsonrpc":"2.0","method":"textDocument/didChange","params":{"textDocument":{"uri":"test:///foo.c","version":5},"contentChanges":[{"text":"int foo ( int x ) {\n  x = x + 1;\n  return x;\n}"}]}}
+{"jsonrpc":"2.0","method":"textDocument/didChange","params":{"textDocument":{"uri":"test:///foo.c","version":5},"contentChanges":[{"text":"int x=\n"}]}}
 ---
-{"jsonrpc":"2.0","id":5,"method":"textDocument/onTypeFormatting","params":{"textDocument":{"uri":"test:///foo.c"},"position":{"line":3,"character":1},"ch":"}","options":{"tabSize":4,"insertSpaces":true}}}
+{"jsonrpc":"2.0","id":5,"method":"textDocument/onTypeFormatting","params":{"textDocument":{"uri":"test:///foo.c"},"position":{"line":1,"character":0},"ch":"\n","options":{"tabSize":4,"insertSpaces":true}}}
 #      CHECK:  "id": 5,
 # CHECK-NEXT:  "jsonrpc": "2.0",
 # CHECK-NEXT:  "result": [
 # CHECK-NEXT:    {
-# CHECK-NEXT:      "newText": "",
+# CHECK-NEXT:      "newText": " ",
 # CHECK-NEXT:      "range": {
 # CHECK-NEXT:        "end": {
-# CHECK-NEXT:          "character": 8,
-# CHECK-NEXT:          "line": 0
-# CHECK-NEXT:        },
-# CHECK-NEXT:        "start": {
-# CHECK-NEXT:          "character": 7,
-# CHECK-NEXT:          "line": 0
-# CHECK-NEXT:        }
-# CHECK-NEXT:      }
-# CHECK-NEXT:    },
-# CHECK-NEXT:    {
-# CHECK-NEXT:      "newText": "",
-# CHECK-NEXT:      "range": {
-# CHECK-NEXT:        "end": {
-# CHECK-NEXT:          "character": 10,
+# CHECK-NEXT:          "character": 5,
 # CHECK-NEXT:          "line": 0
 # CHECK-NEXT:        },
 # CHECK-NEXT:        "start": {
-# CHECK-NEXT:          "character": 9,
+# CHECK-NEXT:          "character": 5,
 # CHECK-NEXT:          "line": 0
 # CHECK-NEXT:        }
 # CHECK-NEXT:      }
 # CHECK-NEXT:    },
 # CHECK-NEXT:    {
-# CHECK-NEXT:      "newText": "",
+# CHECK-NEXT:      "newText": "\n    ",
 # CHECK-NEXT:      "range": {
 # CHECK-NEXT:        "end": {
-# CHECK-NEXT:          "character": 16,
-# CHECK-NEXT:          "line": 0
+# CHECK-NEXT:          "character": 0,
+# CHECK-NEXT:          "line": 1
 # CHECK-NEXT:        },
 # CHECK-NEXT:        "start": {
-# CHECK-NEXT:          "character": 15,
+# CHECK-NEXT:          "character": 6,
 # CHECK-NEXT:          "line": 0
 # CHECK-NEXT:        }
 # CHECK-NEXT:      }
 # CHECK-NEXT:    }
 # CHECK-NEXT:  ]
 ---
 {"jsonrpc":"2.0","id":6,"method":"shutdown"}
 ---
 {"jsonrpc":"2.0","method":"exit"}

test/clangd/initialize-params.test

 # CHECK-NEXT:          ":"
 # CHECK-NEXT:        ]
 # CHECK-NEXT:      },
 # CHECK-NEXT:      "declarationProvider": true,
 # CHECK-NEXT:      "definitionProvider": true,
 # CHECK-NEXT:      "documentFormattingProvider": true,
 # CHECK-NEXT:      "documentHighlightProvider": true,
 # CHECK-NEXT:      "documentOnTypeFormattingProvider": {
-# CHECK-NEXT:        "firstTriggerCharacter": "}",
+# CHECK-NEXT:        "firstTriggerCharacter": "\n",
 # CHECK-NEXT:        "moreTriggerCharacter": []
 # CHECK-NEXT:      },
 # CHECK-NEXT:      "documentRangeFormattingProvider": true,
 # CHECK-NEXT:      "documentSymbolProvider": true,
 # CHECK-NEXT:      "executeCommandProvider": {
 # CHECK-NEXT:        "commands": [
 # CHECK-NEXT:          "clangd.applyFix",
 # CHECK-NEXT:          "clangd.applyTweak"

unittests/clangd/CMakeLists.txt

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

unittests/clangd/FormatTests.cpp

+//===-- FormatTests.cpp - Automatic code formatting tests -----------------===//
+//
+// 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 "Format.h"
+#include "Annotations.h"
+#include "SourceCode.h"
+#include "TestFS.h"
+#include "clang/Format/Format.h"
+#include "clang/Tooling/Core/Replacement.h"
+#include "llvm/Support/Error.h"
+#include "gmock/gmock.h"
+#include "gtest/gtest.h"
+
+namespace clang {
+namespace clangd {
+namespace {
+
+std::string afterTyped(llvm::StringRef CodeWithCursor,
+                           llvm::StringRef Typed) {
+  Annotations Code(CodeWithCursor);
+  unsigned Cursor = llvm::cantFail(positionToOffset(Code.code(), Code.point()));
+  auto Changes =
+      formatIncremental(Code.code(), Cursor, Typed,
+                        format::getGoogleStyle(format::FormatStyle::LK_Cpp));
+  tooling::Replacements Merged;
+  for (const auto& R : Changes)
+    if (llvm::Error E = Merged.add(R))
+      ADD_FAILURE() << llvm::toString(std::move(E));
+  auto NewCode = tooling::applyAllReplacements(Code.code(), Merged);
+  EXPECT_TRUE(bool(NewCode))
+      << "Bad replacements: " << llvm::toString(NewCode.takeError());
+  NewCode->insert(transformCursorPosition(Cursor, Changes), "^");
+  return *NewCode;
+}
+
+// We can't pass raw strings directly to EXPECT_EQ because of gcc bugs.
+void expectAfterNewline(const char *Before, const char *After) {
+  EXPECT_EQ(After, afterTyped(Before, "\n")) << Before;
+}
+void expectAfter(const char *Typed, const char *Before, const char *After) {
+  EXPECT_EQ(After, afterTyped(Before, Typed)) << Before;
+}
+
+TEST(FormatIncremental, SplitComment) {
+  expectAfterNewline(R"cpp(
+// this comment was
+^split
+)cpp",
+   R"cpp(
+// this comment was
+// ^split
+)cpp");
+
+  expectAfterNewline(R"cpp(
+// trailing whitespace is not a split
+^   
+)cpp",
+   R"cpp(
+// trailing whitespace is not a split
+^
+)cpp");
+
+  expectAfterNewline(R"cpp(
+// splitting a
+^
+// multiline comment
+)cpp",
+                     R"cpp(
+// splitting a
+// ^
+// multiline comment
+)cpp");
+
+  expectAfterNewline(R"cpp(
+// extra   
+    ^     whitespace
+)cpp",
+   R"cpp(
+// extra
+// ^whitespace
+)cpp");
+
+  expectAfterNewline(R"cpp(
+/// triple
+^slash
+)cpp",
+   R"cpp(
+/// triple
+/// ^slash
+)cpp");
+
+  expectAfterNewline(R"cpp(
+/// editor continuation
+//^
+)cpp",
+   R"cpp(
+/// editor continuation
+/// ^
+)cpp");
+
+  expectAfterNewline(R"cpp(
+// break before
+^ // slashes
+)cpp",
+   R"cpp(
+// break before
+^// slashes
+)cpp");
+
+
+  expectAfterNewline(R"cpp(
+int x;  // aligned
+^comment
+)cpp",
+   R"cpp(
+int x;  // aligned
+        // ^comment
+)cpp");
+}
+
+TEST(FormatIncremental, Indentation) {
+  expectAfterNewline(R"cpp(
+void foo() {
+  if (bar)
+^
+)cpp",
+   R"cpp(
+void foo() {
+  if (bar)
+    ^
+)cpp");
+
+  expectAfterNewline(R"cpp(
+void foo() {
+  bar(baz(
+^
+)cpp",
+   R"cpp(
+void foo() {
+  bar(baz(
+      ^
+)cpp");
+
+  expectAfterNewline(R"cpp(
+void foo() {
+^}
+)cpp",
+   R"cpp(
+void foo() {
+  ^
+}
+)cpp");
+
+  expectAfterNewline(R"cpp(
+class X {
+protected:
+^
+)cpp",
+   R"cpp(
+class X {
+ protected:
+  ^
+)cpp");
+
+// Mismatched brackets (1)
+  expectAfterNewline(R"cpp(
+void foo() {
+  foo{bar(
+^}
+}
+)cpp",
+   R"cpp(
+void foo() {
+  foo {
+    bar(
+        ^}
+}
+)cpp");
+// Mismatched brackets (2)
+  expectAfterNewline(R"cpp(
+void foo() {
+  foo{bar(
+^text}
+}
+)cpp",
+   R"cpp(
+void foo() {
+  foo {
+    bar(
+        ^text}
+}
+)cpp");
+// Matched brackets
+  expectAfterNewline(R"cpp(
+void foo() {
+  foo{bar(
+^)
+}
+)cpp",
+   R"cpp(
+void foo() {
+  foo {
+    bar(
+        ^)
+}
+)cpp");
+}
+
+TEST(FormatIncremental, FormatPreviousLine) {
+  expectAfterNewline(R"cpp(
+void foo() {
+   untouched( );
+int x=2;
+^
+)cpp",
+                     R"cpp(
+void foo() {
+   untouched( );
+   int x = 2;
+   ^
+)cpp");
+
+  expectAfterNewline(R"cpp(
+int x=untouched( );
+auto L = []{return;return;};
+^
+)cpp",
+   R"cpp(
+int x=untouched( );
+auto L = [] {
+  return;
+  return;
+};
+^
+)cpp");
+}
+
+TEST(FormatIncremental, Annoyances) {
+  // Don't remove newlines the user typed!
+  expectAfterNewline(R"cpp(
+int x(){
+
+
+^
+}
+)cpp",
+   R"cpp(
+int x(){
+
+
+  ^
+}
+)cpp");
+}
+
+TEST(FormatIncremental, FormatBrace) {
+  expectAfter("}", R"cpp(
+vector<int> x= {
+  1,
+  2,
+  3}^
+)cpp",
+              R"cpp(
+vector<int> x = {1, 2, 3}^
+)cpp");
+}
+
+} // namespace
+} // namespace clangd
+} // namespace clang