[clangd] Introduce source.organizeImports code action.

[hokein]

Summary

This would provide us a way to apply unused-includes fixts at once via
the right-click "Source Action" menu or "Organize imports" command
in VSCode.

[hokein]

rebase and polish the implementation.

[kadircet]

clang-tools-extra/clangd/ClangdLSPServer.cpp

1035

instead of doing this in here, what about introducing a new "tweak" that'll perform include-cleaner fixes?
Pros are:

• We can use it in places that don't use LSPServer.
• We can later on extend "organize imports" behaviour to do other things if needed.
• Results will be always up-to-date, as we can use the AST and compute the fixes. rather than making use of the "latest" cached version.
• Implementation would be a little bit neater (and contained), as we can just re-use the existing components in IncludeCleaner, rather than doing some ad-hoc matching & retrieval.

WDYT?

1072–1074

what does the UI look like when there are multiple code actions with "organize imports" kind?
e.g. 1&2 can actually be applied together, but 3rd one can't be combined with others, and in theory these can also be triggered on save (if the user opts in). so I am not sure if having multiple code actions, especially when they can't be merged together, really makes much sense on the editor side.

[hokein]

clang-tools-extra/clangd/ClangdLSPServer.cpp

1035

I think it is a matter of how we view it (whether it is a fix for all diagnostics or a tweak).

but +1, yeah, this looks like a good idea to me.

1072–1074

what does the UI look like when there are multiple code actions with "organize imports" kind?

Similar to the normal code action, if you trigger it via the right context menu (SourceAction), a window with 3 alternatives will pop up, so that you can select one of them (verified on VSCode).

e.g. 1&2 can actually be applied together, but 3rd one can't be combined with others, and in theory these can also be triggered on save (if the user opts in). so I am not sure if having multiple code actions, especially when they can't be merged together, really makes much sense on the editor side.

Good point. The VSocde codeActionsOnSave behavior is like what you said -- it applies each fix one by one (because we trigger preview window per fix, so 3 preview windows will be triggered in sequence).

I don't see the best way to fix it (from the codeAction requests are identical from the one sent via the context menu), one option is to send only a fixAll codeAction rather than 3.

[kadircet]

resigning in favor of https://reviews.llvm.org/D153769

clang-tools-extra/clangd/ClangdLSPServer.cpp

 //===--- ClangdLSPServer.cpp - LSP server ------------------------*- 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 "ClangdLSPServer.h"
 #include "ClangdServer.h"
 #include "CodeComplete.h"
 #include "CompileCommands.h"
 #include "Diagnostics.h"
 #include "Feature.h"
 #include "GlobalCompilationDatabase.h"
+#include "IncludeCleaner.h"
 #include "LSPBinder.h"
 #include "Protocol.h"
 #include "SemanticHighlighting.h"
 #include "SourceCode.h"
 #include "TUScheduler.h"
 #include "URI.h"
 #include "refactor/Tweak.h"
 #include "support/Cancellation.h"
 #include "support/Context.h"
 #include "support/MemoryTree.h"
 #include "support/Trace.h"
 #include "clang/Tooling/Core/Replacement.h"
 #include "llvm/ADT/ArrayRef.h"
 #include "llvm/ADT/FunctionExtras.h"
+#include "llvm/ADT/STLExtras.h"
 #include "llvm/ADT/ScopeExit.h"
 #include "llvm/ADT/StringRef.h"
 #include "llvm/ADT/Twine.h"
 #include "llvm/Support/Allocator.h"
 #include "llvm/Support/Error.h"
 #include "llvm/Support/FormatVariadic.h"
 #include "llvm/Support/JSON.h"
 #include "llvm/Support/SHA1.h"
void ClangdLSPServer::onInitialize(const InitializeParams &Params,
   // Per LSP, codeActionProvider can be either boolean or CodeActionOptions.
   // CodeActionOptions is only valid if the client supports action literal
   // via textDocument.codeAction.codeActionLiteralSupport.
   ServerCaps["codeActionProvider"] =
       Params.capabilities.CodeActionStructure
           ? llvm::json::Object{{"codeActionKinds",
                                 {CodeAction::QUICKFIX_KIND,
                                  CodeAction::REFACTOR_KIND,
-                                 CodeAction::INFO_KIND}}}
+                                 CodeAction::INFO_KIND,
+                                 CodeAction::SOURCE_ORGANIZE_IMPORT}}}
           : llvm::json::Value(true);
 
 
   std::vector<llvm::StringRef> Commands;
   for (llvm::StringRef Command : Handlers.CommandHandlers.keys())
     Commands.push_back(Command);
   llvm::sort(Commands);
   ServerCaps["executeCommandProvider"] =
void ClangdLSPServer::onCodeAction(const CodeActionParams &Params,
   if (KindAllowed(CodeAction::QUICKFIX_KIND)) {
     for (const Diagnostic &D : Params.context.diagnostics) {
       for (auto &CA : getFixes(File.file(), D)) {
         FixIts.push_back(CA);
         FixIts.back().diagnostics = {D};
       }
     }
   }
+  if (KindAllowed(CodeAction::SOURCE_ORGANIZE_IMPORT)) {
+    std::lock_guard<std::mutex> Lock(FixItsMutex);
+    if (auto FileFixItsIter = FixItsMap.find(File.file());
+        FileFixItsIter != FixItsMap.end()) {
+      auto UnusedDiag =
+          llvm::find_if(FileFixItsIter->second, [](const auto &DiagFixes) {
+            return DiagFixes.first.code == "unused-includes";
+          });
+      auto MissingDiag =
+          llvm::find_if(FileFixItsIter->second, [](const auto &DiagFixes) {
+            return DiagFixes.first.code == "missing-include";
+          });
+      clang::clangd::CodeAction *RemoveAllUnused = nullptr;
+      clang::clangd::CodeAction *AddAllMissing = nullptr;
+      clang::clangd::CodeAction *FixAll = nullptr;
+      if (UnusedDiag != FileFixItsIter->second.end()) {
+        for (auto &Fix : UnusedDiag->second) {
+          if (Fix.title == RemoveAllUnusedMessage)
+            RemoveAllUnused = &Fix;
+          else if (Fix.title == FixAllIncludesMessage)
+            FixAll = &Fix;
+        }
+      }
+      if (MissingDiag != FileFixItsIter->second.end()) {
+        for (auto &Fix : MissingDiag->second) {
+          if (Fix.title == AddAllMissingIncludesMessage)
+            AddAllMissing = &Fix;
+          else if (Fix.title == FixAllIncludesMessage)
+            FixAll = &Fix;
+        }
+      }
+      auto AddFix = [&](const clang::clangd::CodeAction *Fix) {
+        if (!Fix)
+          return;
+        FixIts.push_back(*Fix);
+        FixIts.back().kind = CodeAction::SOURCE_ORGANIZE_IMPORT;
+      };
+      AddFix(RemoveAllUnused);
+      AddFix(AddAllMissing);
+      AddFix(FixAll);
+    }
+  }
 
   // Now enumerate the semantic code actions.
   auto ConsumeActions =
       [Diags = Params.context.diagnostics, Reply = std::move(Reply), File,
        Selection = Params.range, FixIts = std::move(FixIts), this](
           llvm::Expected<std::vector<ClangdServer::TweakRef>> Tweaks) mutable {
         if (!Tweaks)
           return Reply(Tweaks.takeError());

clang-tools-extra/clangd/IncludeCleaner.h

 #ifndef LLVM_CLANG_TOOLS_EXTRA_CLANGD_INCLUDECLEANER_H
 #define LLVM_CLANG_TOOLS_EXTRA_CLANGD_INCLUDECLEANER_H
 
 #include "Headers.h"
 #include "ParsedAST.h"
 #include "clang-include-cleaner/Types.h"
 #include "clang/Tooling/Syntax/Tokens.h"
 #include "llvm/ADT/DenseSet.h"
+#include "llvm/ADT/StringRef.h"
 #include "llvm/ADT/StringSet.h"
 #include <tuple>
 #include <vector>
 
 namespace clang {
 namespace clangd {
 
 // Data needed for missing include diagnostics.
 struct MissingIncludeDiagInfo {
   include_cleaner::Symbol Symbol;
   syntax::FileRange SymRefRange;
   std::vector<include_cleaner::Header> Providers;
 
   bool operator==(const MissingIncludeDiagInfo &Other) const {
     return std::tie(SymRefRange, Providers, Symbol) ==
            std::tie(Other.SymRefRange, Other.Providers, Other.Symbol);
   }
 };
 
 struct IncludeCleanerFindings {
   std::vector<const Inclusion *> UnusedIncludes;
   std::vector<MissingIncludeDiagInfo> MissingIncludes;
 };
+inline constexpr llvm::StringLiteral RemoveAllUnusedMessage =
+    "remove all unused includes";
+inline constexpr llvm::StringLiteral AddAllMissingIncludesMessage =
+    "add all missing includes";
+inline constexpr llvm::StringLiteral FixAllIncludesMessage = "fix all includes";
 
 /// Retrieves headers that are referenced from the main file but not used.
 /// In unclear cases, headers are not marked as unused.
 std::vector<const Inclusion *>
 getUnused(ParsedAST &AST,
           const llvm::DenseSet<IncludeStructure::HeaderID> &ReferencedFiles,
           const llvm::StringSet<> &ReferencedPublicHeaders);
 

clang-tools-extra/clangd/IncludeCleaner.cpp

std::vector<const Inclusion *> UnusedIncludes =
       getUnused(AST, Used, /*ReferencedPublicHeaders*/ {});
   return {std::move(UnusedIncludes), std::move(MissingIncludes)};
 }
 
 Fix removeAllUnusedIncludes(llvm::ArrayRef<Diag> UnusedIncludes) {
   assert(!UnusedIncludes.empty());
 
   Fix RemoveAll;
-  RemoveAll.Message = "remove all unused includes";
+  RemoveAll.Message = RemoveAllUnusedMessage;
   for (const auto &Diag : UnusedIncludes) {
     assert(Diag.Fixes.size() == 1 && "Expected exactly one fix.");
     RemoveAll.Edits.insert(RemoveAll.Edits.end(),
          Diag.Fixes.front().Edits.begin(),
          Diag.Fixes.front().Edits.end());
   }
 
   // TODO(hokein): emit a suitable text for the label.
   ChangeAnnotation Annotation = {/*label=*/"",
                                  /*needsConfirmation=*/true,
                                  /*description=*/""};
   static const ChangeAnnotationIdentifier RemoveAllUnusedID =
       "RemoveAllUnusedIncludes";
   for (unsigned I = 0; I < RemoveAll.Edits.size(); ++I) {
     ChangeAnnotationIdentifier ID = RemoveAllUnusedID + std::to_string(I);
     RemoveAll.Edits[I].annotationId = ID;
     RemoveAll.Annotations.push_back({ID, Annotation});
   }
   return RemoveAll;
 }
 Fix addAllMissingIncludes(llvm::ArrayRef<Diag> MissingIncludeDiags) {
   assert(!MissingIncludeDiags.empty());
 
   Fix AddAllMissing;
-  AddAllMissing.Message = "add all missing includes";
+  AddAllMissing.Message = AddAllMissingIncludesMessage;
   // A map to deduplicate the edits with the same new text.
   // newText (#include "my_missing_header.h") -> TextEdit.
   llvm::StringMap<TextEdit> Edits;
   for (const auto &Diag : MissingIncludeDiags) {
     assert(Diag.Fixes.size() == 1 && "Expected exactly one fix.");
     for (const auto& Edit : Diag.Fixes.front().Edits) {
       Edits.try_emplace(Edit.newText, Edit);
     }
for (auto &It : Edits) {
     AddAllMissing.Edits.back().annotationId = ID;
 
     AddAllMissing.Annotations.push_back({ID, Annotation});
   }
   return AddAllMissing;
 }
 Fix fixAll(const Fix& RemoveAllUnused, const Fix& AddAllMissing) {
   Fix FixAll;
-  FixAll.Message = "fix all includes";
+  FixAll.Message = FixAllIncludesMessage;
 
   for (const auto &F : RemoveAllUnused.Edits)
     FixAll.Edits.push_back(F);
   for (const auto &F : AddAllMissing.Edits)
     FixAll.Edits.push_back(F);
 
   for (const auto& A : RemoveAllUnused.Annotations)
     FixAll.Annotations.push_back(A);

clang-tools-extra/clangd/Protocol.h

struct CodeAction {
   std::string title;
 
   /// The kind of the code action.
   /// Used to filter code actions.
   std::optional<std::string> kind;
   const static llvm::StringLiteral QUICKFIX_KIND;
   const static llvm::StringLiteral REFACTOR_KIND;
   const static llvm::StringLiteral INFO_KIND;
+  const static llvm::StringLiteral SOURCE_ORGANIZE_IMPORT;
 
   /// The diagnostics that this code action resolves.
   std::optional<std::vector<Diagnostic>> diagnostics;
 
   /// Marks this as a preferred action. Preferred actions are used by the
   /// `auto fix` command and can be targeted by keybindings.
   /// A quick fix should be marked preferred if it properly addresses the
   /// underlying error. A refactoring should be marked preferred if it is the

clang-tools-extra/clangd/Protocol.cpp

llvm::json::Value toJSON(const Command &C) {
   if (!C.argument.getAsNull())
     Cmd["arguments"] = llvm::json::Array{C.argument};
   return std::move(Cmd);
 }
 
 const llvm::StringLiteral CodeAction::QUICKFIX_KIND = "quickfix";
 const llvm::StringLiteral CodeAction::REFACTOR_KIND = "refactor";
 const llvm::StringLiteral CodeAction::INFO_KIND = "info";
+const llvm::StringLiteral CodeAction::SOURCE_ORGANIZE_IMPORT = "source.organizeImports";
 
 llvm::json::Value toJSON(const CodeAction &CA) {
   auto CodeAction = llvm::json::Object{{"title", CA.title}};
   if (CA.kind)
     CodeAction["kind"] = *CA.kind;
   if (CA.diagnostics)
     CodeAction["diagnostics"] = llvm::json::Array(*CA.diagnostics);
   if (CA.isPreferred)

clang-tools-extra/clangd/test/include-cleaner-batch-fix.test

 # CHECK-NEXT:           1
 # CHECK-NEXT:         ]
 # CHECK-NEXT:       }
 # CHECK-NEXT:     ],
 # CHECK-NEXT:     "uri": "file://{{.*}}/simple.cpp",
 # CHECK-NEXT:     "version": 0
 # CHECK-NEXT:   }
 ---
-{"jsonrpc":"2.0","id":2,"method":"textDocument/codeAction","params":{"textDocument":{"uri":"test:///simple.cpp"},"range":{"start":{"line":2,"character":1},"end":{"line":2,"character":4}},"context":{"diagnostics":[{"range":{"start": {"line": 2, "character": 1}, "end": {"line": 2, "character": 4}},"severity":2,"message":"No header providing \"Foo\" is directly included (fixes available)", "code": "missing-includes", "source": "clangd"}]}}}
+{"jsonrpc":"2.0","id":2,"method":"textDocument/codeAction","params":{"textDocument":{"uri":"test:///simple.cpp"},"range":{"start":{"line":2,"character":1},"end":{"line":2,"character":4}},"context":{"only":["quickfix"], "diagnostics":[{"range":{"start": {"line": 2, "character": 1}, "end": {"line": 2, "character": 4}},"severity":2,"message":"No header providing \"Foo\" is directly included (fixes available)", "code": "missing-includes", "source": "clangd"}]}}}
 #      CHECK:  "id": 2,
 # CHECK-NEXT:  "jsonrpc": "2.0",
 # CHECK-NEXT:  "result": [
 # CHECK-NEXT:    {
 # CHECK-NEXT:      "arguments": [
 # CHECK-NEXT:        {
 # CHECK-NEXT:          "documentChanges": [
 # CHECK-NEXT:            {

 # CHECK-NEXT:          ]
 # CHECK-NEXT:        }
 # CHECK-NEXT:      ],
 # CHECK-NEXT:      "command": "clangd.applyFix",
 # CHECK-NEXT:      "title": "Apply fix: fix all includes"
 # CHECK-NEXT:    }
 # CHECK-NEXT:  ]
 ---
-{"jsonrpc":"2.0","id":3,"method":"textDocument/codeAction","params":{"textDocument":{"uri":"test:///simple.cpp"},"range":{"start":{"line":0,"character":0},"end":{"line":0,"character":17}},"context":{"diagnostics":[{"range":{"start": {"line": 0, "character": 0}, "end": {"line": 0, "character": 17}},"severity":2,"message":"Included header all1.h is not used directly (fixes available)", "code": "unused-includes", "source": "clangd"}]}}}
+{"jsonrpc":"2.0","id":3,"method":"textDocument/codeAction","params":{"textDocument":{"uri":"test:///simple.cpp"},"range":{"start":{"line":0,"character":0},"end":{"line":0,"character":17}},"context":{"only":["quickfix"], "diagnostics":[{"range":{"start": {"line": 0, "character": 0}, "end": {"line": 0, "character": 17}},"severity":2,"message":"Included header all1.h is not used directly (fixes available)", "code": "unused-includes", "source": "clangd"}]}}}
 #      CHECK:  "id": 3,
 # CHECK-NEXT:  "jsonrpc": "2.0",
 # CHECK-NEXT:  "result": [
 # CHECK-NEXT:    {
 # CHECK-NEXT:      "arguments": [
 # CHECK-NEXT:        {
 # CHECK-NEXT:          "documentChanges": [
 # CHECK-NEXT:            {