[clangd] Sort includes when formatting code or inserting new includes.

[hokein]

LGTM.

clangd/ClangdServer.cpp

ClangdServer::insertInclude(PathRef File, StringRef Code,
   if (!Style) {
     llvm::consumeError(Style.takeError());
     // FIXME(ioeric): needs more consistent style support in clangd server.
     Style = format::getLLVMStyle();
   }
   // Replacement with offset UINT_MAX and length 0 will be treated as include
   // insertion.
   tooling::Replacement R(File, /*Offset=*/UINT_MAX, 0, "#include " + ToInclude);
-  return format::cleanupAroundReplacements(Code, tooling::Replacements(R),
-                                           *Style);
+  auto Replaces = format::cleanupAroundReplacements(
+      Code, tooling::Replacements(R), *Style);
+  if (!Replaces)
+    return Replaces;
+  return formatReplacements(Code, *Replaces, *Style);
 }
 
 llvm::Optional<std::string> ClangdServer::getDocument(PathRef File) {
   auto Latest = DraftMgr.getDraft(File);
   if (!Latest.Draft)
     return llvm::None;
   return std::move(*Latest.Draft);
 }
llvm::Optional<Path> ClangdServer::switchSourceHeader(PathRef Path) {
   return llvm::None;
 }
 
 llvm::Expected<tooling::Replacements>
 ClangdServer::formatCode(llvm::StringRef Code, PathRef File,
                          ArrayRef<tooling::Range> Ranges) {
   // Call clang-format.
   auto TaggedFS = FSProvider.getTaggedFileSystem(File);
-  auto StyleOrError =
+  auto Style =
       format::getStyle("file", File, "LLVM", Code, TaggedFS.Value.get());
-  if (!StyleOrError) {
-    return StyleOrError.takeError();
-  } else {
-    return format::reformat(StyleOrError.get(), Code, Ranges, File);
-  }
+  if (!Style)
+    return Style.takeError();
+
+  tooling::Replacements IncludeReplaces =
+      format::sortIncludes(*Style, Code, Ranges, File);
+  auto Changed = tooling::applyAllReplacements(Code, IncludeReplaces);
+  if (!Changed)
+    return Changed.takeError();
+
+  return IncludeReplaces.merge(format::reformat(
+      Style.get(), *Changed,
+      tooling::calculateRangesAfterReplacements(IncludeReplaces, Ranges),
+      File));
 }
 
 void ClangdServer::findDocumentHighlights(
     PathRef File, Position Pos,
     UniqueFunction<void(llvm::Expected<Tagged<std::vector<DocumentHighlight>>>)>
         Callback) {
   auto FileContents = DraftMgr.getDraft(File);
   if (!FileContents.Draft)

unittests/clangd/ClangdTests.cpp

TEST_F(ClangdVFSTest, InsertIncludes) {
   ErrorCheckingDiagConsumer DiagConsumer;
   MockCompilationDatabase CDB;
   std::string SearchDirArg = (llvm::Twine("-I") + testRoot()).str();
   CDB.ExtraClangFlags.insert(CDB.ExtraClangFlags.end(), {SearchDirArg.c_str()});
   ClangdServer Server(CDB, FS, DiagConsumer, ClangdServer::optsForTest());
 
   auto FooCpp = testPath("foo.cpp");
   const auto Code = R"cpp(
+#include "z.h"
 #include "x.h"
 
 void f() {}
 )cpp";
   FS.Files[FooCpp] = Code;
   runAddDocument(Server, FooCpp, Code);
 
-  auto Inserted = [&](llvm::StringRef Original, llvm::StringRef Preferred,
-                      llvm::StringRef Expected) {
+  auto ChangedCode = [&](llvm::StringRef Original, llvm::StringRef Preferred) {
     auto Replaces = Server.insertInclude(
         FooCpp, Code, Original, Preferred.empty() ? Original : Preferred);
     EXPECT_TRUE(static_cast<bool>(Replaces));
     auto Changed = tooling::applyAllReplacements(Code, *Replaces);
     EXPECT_TRUE(static_cast<bool>(Changed));
-    return llvm::StringRef(*Changed).contains(
-        (llvm::Twine("#include ") + Expected + "").str());
+    return *Changed;
+  };
+  auto Inserted = [&](llvm::StringRef Original, llvm::StringRef Preferred,
+                      llvm::StringRef Expected) {
+    return llvm::StringRef(ChangedCode(Original, Preferred))
+        .contains((llvm::Twine("#include ") + Expected + "").str());
   };
 
   EXPECT_TRUE(Inserted("\"y.h\"", /*Preferred=*/"","\"y.h\""));
   EXPECT_TRUE(Inserted("\"y.h\"", /*Preferred=*/"\"Y.h\"", "\"Y.h\""));
   EXPECT_TRUE(Inserted("<string>", /*Preferred=*/"", "<string>"));
   EXPECT_TRUE(Inserted("<string>", /*Preferred=*/"", "<string>"));
 
   std::string OriginalHeader = URI::createFile(testPath("y.h")).toString();
   std::string PreferredHeader = URI::createFile(testPath("Y.h")).toString();
   EXPECT_TRUE(Inserted(OriginalHeader,
                        /*Preferred=*/"", "\"y.h\""));
   EXPECT_TRUE(Inserted(OriginalHeader,
                        /*Preferred=*/"<Y.h>", "<Y.h>"));
   EXPECT_TRUE(Inserted(OriginalHeader, PreferredHeader, "\"Y.h\""));
   EXPECT_TRUE(Inserted("<y.h>", PreferredHeader, "\"Y.h\""));
+
+  // Check that includes are sorted.
+  const auto Expected = R"cpp(
+#include "x.h"
+#include "y.h"
+#include "z.h"
+
+void f() {}
+)cpp";
+  EXPECT_EQ(Expected, ChangedCode("\"y.h\"", /*Preferred=*/""));
+}
+
+TEST_F(ClangdVFSTest, FormatCode) {
+  MockFSProvider FS;
+  ErrorCheckingDiagConsumer DiagConsumer;
+  MockCompilationDatabase CDB;
+  ClangdServer Server(CDB, FS, DiagConsumer, ClangdServer::optsForTest());
+
+  auto Path = testPath("foo.cpp");
+  std::string Code = R"cpp(
+#include "y.h"
+#include "x.h"
+
+void f(  )  {}
+)cpp";
+  std::string Expected = R"cpp(
+#include "x.h"
+#include "y.h"
+
+void f() {}
+)cpp";
+  FS.Files[Path] = Code;
+  runAddDocument(Server, Path, Code);
+
+  auto Replaces = Server.formatFile(Code, Path);
+  EXPECT_TRUE(static_cast<bool>(Replaces));
+  auto Changed = tooling::applyAllReplacements(Code, *Replaces);
+  EXPECT_TRUE(static_cast<bool>(Changed));
+  EXPECT_EQ(Expected, *Changed);
 }
 
 } // namespace
 } // namespace clangd
 } // namespace clang