[clangd] Allow IncludeCleaner to replace unused header with transitively used

[kbobyrev]

This is POC, I need to deal with forward decls and definitions from D112707 firs. Otherwise, this introduces too much noise (LLVM really has *lots* of forward decls that make almost no sense).

[sammccall]

This is cool!
I think it will interact with other features (stdlib, exported headers), and so whatever lands second is going to have to eat the complexity of that interaction.
I think both stdlib and exported headers are more critical and more essentially complex, so should probably land first to drive the design.

clang-tools-extra/clangd/IncludeCleaner.cpp

298

It seems like this is going to include any files that are transitively reachable through multiple paths and directly reachable through none. These are going to seem like false positives.
Like <stddef.h> if the file uses size_t at all, or something.

Sure, if you want the whole file to be IWYU-clean you should remove <unused.h> and add <stddef.h>, but they're not *really* related.

311

This is going to have problems with private/exported headers.

Consider includes main -> foo -> bar -> private.
Main uses a symbol from private, bar exports private.
You need to suggest replacing the include of foo -> {bar}, not {bar, private}.

However you still want to traverse children of private in case main uses those.

376

We should offer both fixes as alternatives, maybe?

381

exactly how to spell an include and where to place it is tricky. See IncludeInserter.h in headers.

clang-tools-extra/clangd/IncludeCleaner.h

69

why are we back to passing around strings?

[kbobyrev]

Oh, sorry, I marked it as "changes intended" so that you could know it's not review-ready yet :) I was just playing around with it and previewing to see how it would feel to have a somewhat working solution.

I didn't really implement the feature (add the proper header spelling that we have in IncludeFixer as you mentioned in the comments, check if the replacement header is already included or not, etc), but there are two important problems I was facing that look rather tricky

• This actually steps into the "missing includes" land: we can be conservative when deciding whether a header is used or not. It is both system headers _and_ (currently) a lot of noise in the form of headers with forward decls. E.g. for StringRef the replacement set includes SHA1 and a bunch of very surprising headers just because we have lots of forward decls in unexpected places. I originally had the idea that we can do unused includes without missing includes but it seems that they are closer in terms of at least this usecase. I wanted to see if we would need something more but maybe the follow-up on the mentioned patch (narrow down the "used" header property set conditions) would be enough.
• Performance: providing fix-its for individual headers is not really performance-optimal: we need a graph traversal from each MainFileInclusion and it's a linear BFS, so the complexity is O(unused headers * graph size). This _might_ be unfortunate for large graphs and (surprisingly) it's just faster to collect the data for a "batch replace" of unused headers with used ones. But this brings us back into the realm of missing headers. Maybe the performance is fine, but I want to estimate it in a better way. So far I've seen somewhat small graphs when editing LLVM (<1k headers) but it might be different for different parts so I want to check the performance to make sure it's really fine.

Anyway, I'd be happy to talk once I'm back but as you mentioned this patch would probably need some QOL improvements before it can be landed (needless to say, it should be complete, too :) )!

clang-tools-extra/clangd/IncludeCleaner.h

translateToHeaderIDs(const llvm::DenseSet<FileID> &Files,
                      const IncludeStructure &Includes, const SourceManager &SM);
 
 /// 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);
 
-std::vector<const Inclusion *> computeUnusedIncludes(ParsedAST &AST);
+llvm::StringSet<> reachableUsedHeaders(
+    IncludeStructure &IncludeGraph, IncludeStructure::HeaderID Source,
+    const llvm::DenseSet<IncludeStructure::HeaderID> &UsedHeaders);
+
+struct UnusedInclude {
+  const Inclusion *Include;
+  llvm::StringSet<> ValidReplacements;
+};
+
+std::vector<UnusedInclude> computeUnusedIncludes(ParsedAST &AST);
 
 std::vector<Diag> issueUnusedIncludesDiagnostics(ParsedAST &AST,
                                                  llvm::StringRef Code);
 
 } // namespace clangd
 } // namespace clang
 
 #endif // LLVM_CLANG_TOOLS_EXTRA_CLANGD_INCLUDE_CLEANER_H

clang-tools-extra/clangd/IncludeCleaner.cpp

 //===--- IncludeCleaner.cpp - Unused/Missing Headers Analysis ---*- 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 "IncludeCleaner.h"
 #include "Config.h"
+#include "Headers.h"
 #include "ParsedAST.h"
 #include "Protocol.h"
 #include "SourceCode.h"
 #include "support/Logger.h"
 #include "support/Trace.h"
 #include "clang/AST/RecursiveASTVisitor.h"
 #include "clang/Basic/SourceLocation.h"
 #include "clang/Lex/HeaderSearch.h"
 #include "clang/Lex/Preprocessor.h"
 #include "clang/Tooling/Syntax/Tokens.h"
+#include "llvm/ADT/StringSet.h"
 #include "llvm/Support/FormatVariadic.h"
 #include "llvm/Support/Path.h"
+#include <queue>
 
 namespace clang {
 namespace clangd {
 namespace {
 
 /// Crawler traverses the AST and feeds in the locations of (sometimes
 /// implicitly) used symbols into \p Result.
 class ReferencedLocationCrawler
for (auto It = Sorted.begin(); It < Sorted.end();) {
     // This avoids lots of redundant Loc->File lookups for the same file.
     do
       ++It;
     while (It != Sorted.end() && SM.isInFileID(*It, FID));
   }
   return std::move(Result.Files);
 }
 
-std::vector<const Inclusion *>
-getUnused(ParsedAST &AST,
-          const llvm::DenseSet<IncludeStructure::HeaderID> &ReferencedFiles) {
-  trace::Span Tracer("IncludeCleaner::getUnused");
-  std::vector<const Inclusion *> Unused;
-  for (const Inclusion &MFI : AST.getIncludeStructure().MainFileIncludes) {
-    if (!MFI.HeaderID)
-      continue;
-    auto IncludeID = static_cast<IncludeStructure::HeaderID>(*MFI.HeaderID);
-    bool Used = ReferencedFiles.contains(IncludeID);
-    if (!Used && !mayConsiderUnused(MFI, AST)) {
-      dlog("{0} was not used, but is not eligible to be diagnosed as unused",
-           MFI.Written);
-      continue;
-    }
-    if (!Used)
-      Unused.push_back(&MFI);
-    dlog("{0} is {1}", MFI.Written, Used ? "USED" : "UNUSED");
-  }
-  return Unused;
-}
-
 #ifndef NDEBUG
 // Is FID a <built-in>, <scratch space> etc?
 static bool isSpecialBuffer(FileID FID, const SourceManager &SM) {
   const SrcMgr::FileInfo &FI = SM.getSLocEntry(FID).getFile();
   return FI.getName().startswith("<");
 }
 #endif
 
for (FileID FID : Files) {
     }
     const auto File = Includes.getID(FE);
     assert(File);
     TranslatedHeaderIDs.insert(*File);
   }
   return TranslatedHeaderIDs;
 }
 
-std::vector<const Inclusion *> computeUnusedIncludes(ParsedAST &AST) {
+std::vector<const Inclusion *>
+getUnused(ParsedAST &AST,
+          const llvm::DenseSet<IncludeStructure::HeaderID> &ReferencedFiles) {
+  trace::Span Tracer("IncludeCleaner::getUnused");
+  std::vector<const Inclusion *> Unused;
+  for (const Inclusion &MFI : AST.getIncludeStructure().MainFileIncludes) {
+    if (!MFI.HeaderID)
+      continue;
+    auto IncludeID = static_cast<IncludeStructure::HeaderID>(*MFI.HeaderID);
+    bool Used = ReferencedFiles.contains(IncludeID);
+    if (!Used && !mayConsiderUnused(MFI, AST)) {
+      dlog("{0} was not used, but is not eligible to be diagnosed as unused",
+           MFI.Written);
+      continue;
+    }
+    if (!Used)
+      Unused.push_back(&MFI);
+    dlog("{0} is {1}", MFI.Written, Used ? "USED" : "UNUSED");
+  }
+  return Unused;
+}
+
+llvm::StringSet<> reachableUsedHeaders(
+    const IncludeStructure &IncludeGraph, IncludeStructure::HeaderID Source,
+    const llvm::DenseSet<IncludeStructure::HeaderID> &UsedHeaders) {
+  llvm::StringSet<> Result;
+  llvm::DenseSet<IncludeStructure::HeaderID> Visited;
+  std::queue<IncludeStructure::HeaderID> ToVisit;
+  ToVisit.push(Source);
+  while (!ToVisit.empty()) {
+    auto NextID = ToVisit.front();
+    ToVisit.pop();
+    Visited.insert(NextID);
+    if (UsedHeaders.contains(NextID))
+      Result.insert(IncludeGraph.getRealPath(NextID));
+    for (const auto &Header : IncludeGraph.IncludeChildren.lookup(NextID))
+      if (!Visited.contains(Header))
+        ToVisit.push(Header);
+  }
+  return Result;
+}
+
+std::vector<UnusedInclude> computeUnusedIncludes(ParsedAST &AST) {
   const auto &SM = AST.getSourceManager();
 
   auto Refs = findReferencedLocations(AST);
   // FIXME(kirillbobyrev): Attribute the symbols from non self-contained
   // headers to their parents while the information about respective
   // SourceLocations and FileIDs is not lost. It is not possible to do that
   // later when non-guarded headers included multiple times will get same
   // HeaderID.
   auto ReferencedFileIDs = findReferencedFiles(Refs, SM);
   auto ReferencedHeaders =
       translateToHeaderIDs(ReferencedFileIDs, AST.getIncludeStructure(), SM);
-  return getUnused(AST, ReferencedHeaders);
+  std::vector<UnusedInclude> UnusedIncludes;
+  for (const auto *Header : getUnused(AST, ReferencedHeaders)) {
+    UnusedIncludes.push_back(UnusedInclude{
+        Header, reachableUsedHeaders(
+                    AST.getIncludeStructure(),
+                    static_cast<IncludeStructure::HeaderID>(*Header->HeaderID),
+                    ReferencedHeaders)});
+  }
+  return UnusedIncludes;
 }
 
 std::vector<Diag> issueUnusedIncludesDiagnostics(ParsedAST &AST,
                                                  llvm::StringRef Code) {
   trace::Span Tracer("IncludeCleaner::issueUnusedIncludesDiagnostics");
   const Config &Cfg = Config::current();
   if (Cfg.Diagnostics.UnusedIncludes != Config::UnusedIncludesPolicy::Strict ||
       Cfg.Diagnostics.SuppressAll ||
       Cfg.Diagnostics.Suppress.contains("unused-includes"))
     return {};
   std::vector<Diag> Result;
   std::string FileName =
       AST.getSourceManager()
           .getFileEntryForID(AST.getSourceManager().getMainFileID())
           ->getName()
           .str();
-  for (const auto *Inc : computeUnusedIncludes(AST)) {
+  for (const auto &I : computeUnusedIncludes(AST)) {
     Diag D;
-    D.Message =
-        llvm::formatv("included header {0} is not used",
-                      llvm::sys::path::filename(
-                          Inc->Written.substr(1, Inc->Written.size() - 2),
-                          llvm::sys::path::Style::posix));
+    D.Message = llvm::formatv(
+        "included header {0} is not used",
+            I.Include->Written.substr(1, I.Include->Written.size() - 2),
     D.Name = "unused-includes";
     D.Source = Diag::DiagSource::Clangd;
     D.File = FileName;
     D.Severity = DiagnosticsEngine::Warning;
     D.Tags.push_back(Unnecessary);
-    D.Range = getDiagnosticRange(Code, Inc->HashOffset);
+    D.Range = getDiagnosticRange(Code, I.Include->HashOffset);
     // FIXME(kirillbobyrev): Removing inclusion might break the code if the
     // used headers are only reachable transitively through this one. Suggest
     // including them directly instead.
     // FIXME(kirillbobyrev): Add fix suggestion for adding IWYU pragmas
     // (keep/export) remove the warning once we support IWYU pragmas.
     D.Fixes.emplace_back();
     D.Fixes.back().Message = "remove #include directive";
     D.Fixes.back().Edits.emplace_back();
-    D.Fixes.back().Edits.back().range.start.line = Inc->HashLine;
-    D.Fixes.back().Edits.back().range.end.line = Inc->HashLine + 1;
+    D.Fixes.back().Edits.back().range.start.line = I.Include->HashLine;
+    D.Fixes.back().Edits.back().range.end.line = I.Include->HashLine + 1;
+    std::string DirectIncludes;
+    for (const auto &Replacement : I.ValidReplacements) {
+      DirectIncludes +=
+          llvm::formatv("#include \"{0}\"\n", Replacement.getKey());
+    }
+    D.Fixes.back().Edits.back().newText = DirectIncludes;
     D.InsideMainFile = true;
     Result.push_back(std::move(D));
   }
   return Result;
 }
 
 } // namespace clangd
 } // namespace clang

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

TEST(IncludeCleaner, GetUnusedHeaders) {
   TU.AdditionalFiles["dir/unused.h"] = guard("void dirUnused();");
   TU.AdditionalFiles["system/system_header.h"] = guard("");
   TU.AdditionalFiles["unguarded.h"] = "";
   TU.ExtraArgs.push_back("-I" + testPath("dir"));
   TU.ExtraArgs.push_back("-isystem" + testPath("system"));
   TU.Code = MainFile.str();
   ParsedAST AST = TU.build();
   std::vector<std::string> UnusedIncludes;
-  for (const auto &Include : computeUnusedIncludes(AST))
-    UnusedIncludes.push_back(Include->Written);
+  for (const auto &I : computeUnusedIncludes(AST))
+    UnusedIncludes.push_back(I.Include->Written);
   EXPECT_THAT(UnusedIncludes,
               UnorderedElementsAre("\"unused.h\"", "\"dir/unused.h\""));
 }
 
 TEST(IncludeCleaner, VirtualBuffers) {
   TestTU TU;
   TU.Code = R"cpp(
     #include "macros.h"