[clangd] IncludeCleaner: Mark used headers

[kbobyrev]

Summary

Follow-up on D105426.

[kbobyrev]

Nit.

[kbobyrev]

Need to add some basic tests.

[kbobyrev]

Rebase on top of main.

[sammccall]

I realize many of the things I'll object to came from my own prototype, sorry about that :-\
I think/hope I gave you some forewarning about this!

clang-tools-extra/clangd/Headers.h

137 ↗

(On Diff #366835)

Hey, I recognize this code :-)

I think the key ideas here are that:

• we're using opaque identifiers for the files, nothing is interesting about a file other than its (include) edges and (directly-referenced) color
• the identity of headers is an impl detail of Headers.h rather than being something like a FileID, this allows us to hide messy details of files not having stable identity across preamble->main file

I think the second idea is important, but the first one might be a bit naive. I worry it's going to lead to certain rules being hard to implement, or being bundled into Headers.cpp instead of IncludeCleaner.

For example:

• if a file is not self-contained, how does this affect the algorithm? (There's a FIXME for this, but it's in the wrong file!)
• if a file is a standard library entrypoint?
• if a file is a standard library impl detail?

I think the facts (is a file self-contained) should be part of IncludeStructure, but that we should expose them for IncludeCleaner to deal with, rather than trying to hide them in markUsed.
This means giving IncludeStructure a wider interface, which is we need to be careful about. It makes it harder to substitute algorithms by swapping out the UsedFunc, but I think this is only a cute trick and not actually important.

---

Concretely, I think I'd suggest just extending the public API to expose the "file index" concept:

• expose the type using IncludeStructure::File = unsigned or so
• add the file id to Inclusion
• add File getFile(const FileEntry*)
• add ArrayRef<File> getIncludedFiles(File)
• in future, we can add e.g. const char* isStandardLibraryEntrypoint(File) or whatever

And implement all of markUsed in IncludeCleaner.
(Not 100% sure if we actually still need the Used ivar in Inclusion, come to think of it, maybe we just run this code in the diagnostic cycle)

clang-tools-extra/clangd/IncludeCleaner.cpp

144

nit: move this to be a line comment on the sort() call?

I think it's sufficiently nonobvious that sorting groups by file ID that it becomes nonobvious exactly what code the comment refers to!

clang-tools-extra/clangd/IncludeCleaner.h

51

so when *do* we perform this expansion?

Seems like you've wired this up end-to-end in this patch and we're just going to hit the elog case.

I think it's reasonable to put this expansion into findReferencedFiles fwiw, it's a fairly simple second pass and in practice combining them won't interfere with reasonable tests

52

comment just says spelling, not spelling/expansion, not sure if this is significant.

Expansion is actually the more obvious, but I do think we need both.

[kbobyrev]

Improve structure, address review comments.

[kbobyrev]

Hey, sorry for the gigantic turn around. I still need to cover the code with few tests and polish it a bit more but I've updated the majority of it and pushed to get some early feedback before I do that. Please let me know if you have any concerns/see some problems with the approach I went for!

[kbobyrev]

Populate Inclusion.ID, add a test (failing for now).

[kbobyrev]

Make sure FileEntry* is not nullptr

[sammccall]

clang-tools-extra/clangd/Headers.h

61 ↗

(On Diff #374226)

Most includes are part of the preamble, so there are two relevant parse actions (preamble, and mainfile-using-preamble). Each has its own SourceManager and therefore namespace of FileIDs.

There's no rule that says a header gets the same FileID when a preamble is used. As written, RecordHeaders is assigning Inclusion::ID based on the preamble, and then we end up comparing it to FileIDs from compareUnusedIncludes().

From reading the ASTReader code, I *believe* that there's a simple offset between the two: e.g. that if a preamble uses FileIDs from 1-100, then these might be mapped to FileIDs 1501-1600 when that preamble is reused. We could go down the path of exploiting this. (Though we need to investigate the details and think a little about how it works with modules).

The somewhat less-coupled alternative we use today is to use the FileEntry::Name as documented in the private section of IncludeStructure. There are a few ways to build on top of this - basically we're either going to do most calculations in FileID space, or expose a "stable file index" from IncludeStructure and do most calculations in that space...

[kbobyrev]

Perform the computation in the IncludeStructure::File space.

[kbobyrev]

Prepare for rebase: revert Headers.cpp and Headers.h

[kbobyrev]

Rebase on top of D110386.

[kbobyrev]

Rebase on top of main. Now ready for a review.

[kbobyrev]

Fix the rebase

[kbobyrev]

Tiny refactoring.

[kbobyrev]

Rebase on top of landed patches.

Ping, @sammccall

[sammccall]

Sorry, I thought i'd sent these comments...

clang-tools-extra/clangd/IncludeCleaner.cpp

158

Why are we passing around Inclusions by value?

clang-tools-extra/clangd/IncludeCleaner.h

51

This says FIXME but IIUC it's fixed.

56

this function is undocumented, unused and untested :-)

What's it for? Why does it not return a set?

[kbobyrev]

Resolve review comments.

[kbobyrev]

Refactor FileID -> IncludeStructure::HeaderID into a separate function.

[sammccall]

clang-tools-extra/clangd/IncludeCleaner.cpp

158

Sorry, should have thought this through more before leaving the comment. There are a couple of questions really:

How should we *store* the information about which inclusions are unused?

• not at all, generate ReferencedFiles and compute "is this header unused" on the fly when generating diagnostics
• store ReferencedFiles but call "is this header unused" on the fly
• store a boolean or something in each Inclusion
• store a list of the inclusions that are unused

IMO this is mostly a question of what's the lifecycle of the info, and what's the simplest representation - seems like we should prefer stuff higher on the list if we have a choice.

What should the signature of the function be?
There doesn't seem to be any work saved here by processing all the includes as a batch - why not simplify by just making this bool isUnused(...) and let the caller/test choose what data structures to use?

159

EntryPoint is unused

166

Handle unresolved case somehow? (Or assert if you're sure it can't happen - I think it can for e.g. pp_file_not_found)

166

doesn't seem like there's any need to go through filenames for this.
Can't we just store the HeaderID in the Inclusion?
(Blech, as an unsigned to avoid a circular dependency)

168

elog says that:
a) this might happen
b) logging for the user is the best thing we can do

Can this actually happen? My suspicion is no. In which case maybe it should be an assert?

173

I'm fairly (more) certain this one should be an assert

193

assert?

196

this is get, not getOrCreate, so you don't need the mutable reference

198

I'm not totally sure whether this is safe to assert or not. WDYT?

In any case, please fix the message (FE -> HeaderID, add more context)

[sammccall]

clang-tools-extra/clangd/IncludeCleaner.cpp

158

OK I was confused, nothing is getting stored, but ParsedAST::getUnused() function creates/destroys the analysis data so it needs to run as a batch.

I think probably:

• *this* function should just be a simple bool isUnused(...) and the loop lives in the caller
• ParsedAST::getUnused() should become getUnused(const ParsedAST&) and live in this file

We have some circularity between ParsedAST and IncludeCleaner, but I think we're going to have that in any case due to findReferencedLocations()

[kbobyrev]

Address review comments.

[sammccall]

clang-tools-extra/clangd/Headers.h

65 ↗

(On Diff #377197)

I don't think we're under any size pressure here - Optional<unsigned>?

65 ↗

(On Diff #377197)

call the member HeaderID, rather than have this as a comment only?

clang-tools-extra/clangd/IncludeCleaner.cpp

161

SM is unused

165

this can just be a check whether MFI.ID is valid or not

171

ReferencedFiles.contains(IncludeID) and inline into the if?

clang-tools-extra/clangd/ParsedAST.h

164

I think this function belongs in IncludeCleaner.h.

(There's a circularity problem between ParsedAST and IncludeCleaner, but putting the function here doesn't fix it)

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

165

Don't bother doing this stripping just for the test IMO, it obscures the assertion (more than escaping quotes would)

[kbobyrev]

Thank you for the review! Looks much better now.

clang-tools-extra/clangd/IncludeCleaner.h

 
 #ifndef LLVM_CLANG_TOOLS_EXTRA_CLANGD_INCLUDE_CLEANER_H
 #define LLVM_CLANG_TOOLS_EXTRA_CLANGD_INCLUDE_CLEANER_H
 
 #include "Headers.h"
 #include "ParsedAST.h"
 #include "clang/Basic/SourceLocation.h"
 #include "llvm/ADT/DenseSet.h"
+#include <vector>
 
 namespace clang {
 namespace clangd {
 
 using ReferencedLocations = llvm::DenseSet<SourceLocation>;
 /// Finds locations of all symbols used in the main file.
 ///
 /// Uses RecursiveASTVisitor to go through main file AST and computes all the
 /// locations used symbols are coming from. Returned locations may be macro
 /// expansions, and are not resolved to their spelling/expansion location. These
 /// locations are later used to determine which headers should be marked as
 /// "used" and "directly used".
 ///
 /// We use this to compute unused headers, so we:
 ///
 /// - cover the whole file in a single traversal for efficiency
 /// - don't attempt to describe where symbols were referenced from in
 ///   ambiguous cases (e.g. implicitly used symbols, multiple declarations)
 /// - err on the side of reporting all possible locations
 ReferencedLocations findReferencedLocations(ParsedAST &AST);
 
+/// Retrieves IDs of all files containing SourceLocations from \p Locs.
+/// FIXME: Those locations could be within macro expansions and are resolved to
+/// their spelling/expansion locations.
+llvm::DenseSet<FileID> findReferencedFiles(const ReferencedLocations &Locs,
+                                           const SourceManager &SM);
+
+inline llvm::DenseMap<IncludeStructure::HeaderID, bool> directlyReferencedFiles(
+    const IncludeStructure &Includes,
+    const llvm::DenseSet<IncludeStructure::HeaderID> &Referenced,
+    IncludeStructure::HeaderID EntryPoint) {
+  llvm::DenseMap<IncludeStructure::HeaderID, bool> Result;
+  for (IncludeStructure::HeaderID Inclusion :
+       Includes.IncludeChildren.lookup(EntryPoint))
+    Result.try_emplace(Inclusion, Referenced.contains(Inclusion));
+  return Result;
+}
+
+/// Retrieves headers that are referenced from the main file (\p EntryPoint)
+/// but not used.
+std::vector<Inclusion>
+getUnused(IncludeStructure::HeaderID EntryPoint,
+          const IncludeStructure &Includes,
+          const llvm::DenseSet<IncludeStructure::HeaderID> &ReferencedFiles,
+          const SourceManager &SM);
+
 } // namespace clangd
 } // namespace clang
 
 #endif // LLVM_CLANG_TOOLS_EXTRA_CLANGD_INCLUDE_CLEANER_H

clang-tools-extra/clangd/IncludeCleaner.cpp

private:
   }
 
   bool isNew(const void *P) { return P && Visited.insert(P).second; }
 
   ReferencedLocations &Result;
   llvm::DenseSet<const void *> Visited;
 };
 
+// Given a set of referenced FileIDs, determines all the potentially-referenced
+// files and macros by traversing expansion/spelling locations of macro IDs.
+// This is used to map the referenced SourceLocations onto real files.
+struct ReferencedFiles {
+  ReferencedFiles(const SourceManager &SM) : SM(SM) {}
+  llvm::DenseSet<FileID> Files;
+  llvm::DenseSet<FileID> Macros;
+  const SourceManager &SM;
+
+  void add(SourceLocation Loc) { add(SM.getFileID(Loc), Loc); }
+
+  void add(FileID FID, SourceLocation Loc) {
+    if (FID.isInvalid())
+      return;
+    assert(SM.isInFileID(Loc, FID));
+    if (Loc.isFileID()) {
+      Files.insert(FID);
+      return;
+    }
+    // Don't process the same macro FID twice.
+    if (!Macros.insert(FID).second)
+      return;
+    const auto &Exp = SM.getSLocEntry(FID).getExpansion();
+    add(Exp.getSpellingLoc());
+    add(Exp.getExpansionLocStart());
+    add(Exp.getExpansionLocEnd());
+  }
+};
+
 } // namespace
 
 ReferencedLocations findReferencedLocations(ParsedAST &AST) {
   ReferencedLocations Result;
   ReferencedLocationCrawler Crawler(Result);
   Crawler.TraverseAST(AST.getASTContext());
   // FIXME(kirillbobyrev): Handle macros.
   return Result;
 }
 
+llvm::DenseSet<FileID>
+findReferencedFiles(const llvm::DenseSet<SourceLocation> &Locs,
+                    const SourceManager &SM) {
+  std::vector<SourceLocation> Sorted{Locs.begin(), Locs.end()};
+  llvm::sort(Sorted); // Group by FileID.
+  ReferencedFiles Result(SM);
+  for (auto It = Sorted.begin(); It < Sorted.end();) {
+    FileID FID = SM.getFileID(*It);
+    Result.add(FID, *It);
+    // Cheaply skip over all the other locations from the same FileID.
+    // 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<Inclusion>
+getUnused(IncludeStructure::HeaderID EntryPoint,
+          const IncludeStructure &Structure,
+          const llvm::DenseSet<IncludeStructure::HeaderID> &ReferencedFiles,
+          const SourceManager &SM) {
+  std::vector<Inclusion> Unused;
+  for (auto &MFI : Structure.MainFileIncludes) {
+    // FIXME: Skip includes that are not self-contained.
+    auto Entry = SM.getFileManager().getFile(MFI.Resolved);
+    if (!Entry) {
+      elog("Missing FileEntry for {0}", MFI.Resolved);
+      continue;
+    }
+    auto It = Structure.getID(*Entry);
+    if (!It) {
+      elog("Missing IncludeStructure::File for {0}", MFI.Resolved);
+      continue;
+    }
+    bool Used = ReferencedFiles.find(*It) != ReferencedFiles.end();
+    if (!Used) {
+      Unused.push_back(MFI);
+    }
+    dlog("{0} is {1}", MFI.Written, Used ? "USED" : "UNUSED");
+  }
+  return Unused;
+}
+
 } // namespace clangd
 } // namespace clang

clang-tools-extra/clangd/ParsedAST.h

public:
   /// Returns the version of the ParseInputs used to build Preamble part of this
   /// AST. Might be None if no Preamble is used.
   llvm::Optional<llvm::StringRef> preambleVersion() const;
 
   const HeuristicResolver *getHeuristicResolver() const {
     return Resolver.get();
   }
 
+  std::vector<Inclusion> computeUnusedIncludes();
+
 private:
   ParsedAST(llvm::StringRef Version,
             std::shared_ptr<const PreambleData> Preamble,
             std::unique_ptr<CompilerInstance> Clang,
             std::unique_ptr<FrontendAction> Action, syntax::TokenBuffer Tokens,
             MainFileMacros Macros, std::vector<PragmaMark> Marks,
             std::vector<Decl *> LocalTopLevelDecls,
             llvm::Optional<std::vector<Diag>> Diags, IncludeStructure Includes,
private:
   // Top-level decls inside the current file. Not that this does not include
   // top-level decls from the preamble.
   std::vector<Decl *> LocalTopLevelDecls;
   IncludeStructure Includes;
   CanonicalIncludes CanonIncludes;
   std::unique_ptr<HeuristicResolver> Resolver;
 };
 
 } // namespace clangd
 } // namespace clang
 
 #endif // LLVM_CLANG_TOOLS_EXTRA_CLANGD_PARSEDAST_H

clang-tools-extra/clangd/ParsedAST.cpp

 #include "AST.h"
 #include "Compiler.h"
 #include "Config.h"
 #include "Diagnostics.h"
 #include "Feature.h"
 #include "FeatureModule.h"
 #include "Headers.h"
 #include "HeuristicResolver.h"
+#include "IncludeCleaner.h"
 #include "IncludeFixer.h"
 #include "Preamble.h"
 #include "SourceCode.h"
 #include "TidyProvider.h"
 #include "index/CanonicalIncludes.h"
 #include "index/Index.h"
 #include "support/Logger.h"
 #include "support/Trace.h"
ParsedAST::ParsedAST(llvm::StringRef Version,
   assert(this->Action);
 }
 
 llvm::Optional<llvm::StringRef> ParsedAST::preambleVersion() const {
   if (!Preamble)
     return llvm::None;
   return llvm::StringRef(Preamble->Version);
 }
+
+std::vector<Inclusion> ParsedAST::computeUnusedIncludes() {
+  const auto &SM = getSourceManager();
+
+  auto Refs = findReferencedLocations(*this);
+  auto ReferencedFileIDs = findReferencedFiles(Refs, SM);
+  llvm::DenseSet<IncludeStructure::HeaderID> ReferencedFiles;
+  ReferencedFiles.reserve(ReferencedFileIDs.size());
+  for (FileID FID : ReferencedFileIDs) {
+    const FileEntry *FE = SM.getFileEntryForID(FID);
+    if (!FE) {
+      elog("Missing FE for {0}", SM.getComposedLoc(FID, 0).printToString(SM));
+      continue;
+    }
+    const auto File = Includes.getID(FE);
+    if (!File) {
+      elog("Missing FE for {0}", SM.getComposedLoc(FID, 0).printToString(SM));
+      continue;
+    }
+    ReferencedFiles.insert(*File);
+  }
+  auto MainFileIndex = Includes.getID(SM.getFileEntryForID(SM.getMainFileID()));
+  assert(MainFileIndex && "MainFile should always have HeaderID (0)");
+  return getUnused(*MainFileIndex, Includes, ReferencedFiles, SM);
+}
+
 } // namespace clangd
 } // namespace clang

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

 #include "TestTU.h"
 #include "gmock/gmock.h"
 #include "gtest/gtest.h"
 
 namespace clang {
 namespace clangd {
 namespace {
 
+using ::testing::UnorderedElementsAre;
+
 TEST(IncludeCleaner, ReferencedLocations) {
   struct TestCase {
     std::string HeaderCode;
     std::string MainCode;
   };
   TestCase Cases[] = {
       // DeclRefExpr
       {
for (const TestCase &T : Cases) {
     }
     llvm::sort(Points);
 
     EXPECT_EQ(Points, Header.points()) << T.HeaderCode << "\n---\n"
                                        << T.MainCode;
   }
 }
 
+TEST(IncludeCleaner, GetUnusedHeaders) {
+  llvm::StringLiteral MainFile = R"cpp(
+    #include "a.h"
+    #include "b.h"
+    #include "dir/c.h"
+    #include "dir/unused.h"
+    #include "unused.h"
+    void foo() {
+      a();
+      b();
+      c();
+    })cpp";
+  // Build expected ast with symbols coming from headers.
+  TestTU TU;
+  TU.Filename = "foo.cpp";
+  TU.AdditionalFiles["foo.h"] = "void foo();";
+  TU.AdditionalFiles["a.h"] = "void a();";
+  TU.AdditionalFiles["b.h"] = "void b();";
+  TU.AdditionalFiles["dir/c.h"] = "void c();";
+  TU.AdditionalFiles["unused.h"] = "void unused();";
+  TU.AdditionalFiles["dir/unused.h"] = "void dirUnused();";
+  TU.AdditionalFiles["not_included.h"] = "void notIncluded();";
+  TU.ExtraArgs = {"-I" + testPath("dir")};
+  TU.Code = MainFile.str();
+  ParsedAST AST = TU.build();
+  auto UnusedIncludes = AST.computeUnusedIncludes();
+  std::vector<std::string> UnusedHeaders;
+  UnusedHeaders.reserve(UnusedIncludes.size());
+  for (const auto &Include : UnusedIncludes) {
+    // Strip enclosing "".
+    UnusedHeaders.push_back(
+        Include.Written.substr(1, Include.Written.size() - 2));
+  }
+  EXPECT_THAT(UnusedHeaders, UnorderedElementsAre("unused.h", "dir/unused.h"));
+}
+
 } // namespace
 } // namespace clangd
 } // namespace clang