[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

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

50

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

51

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

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

50

This says FIXME but IIUC it's fixed.

55

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

61

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

61

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

159

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 ↗

(On Diff #377197)

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/Headers.h

 // An #include directive that we found in the main file.
 struct Inclusion {
   tok::PPKeywordKind Directive; // Directive used for inclusion, e.g. import
   std::string Written;          // Inclusion name as written e.g. <vector>.
   Path Resolved; // Resolved path of included file. Empty if not resolved.
   unsigned HashOffset = 0; // Byte offset from start of file to #.
   int HashLine = 0;        // Line number containing the directive, 0-indexed.
   SrcMgr::CharacteristicKind FileKind = SrcMgr::C_User;
+  bool Used = false; // Contains symbols used in the main file.
 };
 llvm::raw_ostream &operator<<(llvm::raw_ostream &, const Inclusion &);
 bool operator==(const Inclusion &LHS, const Inclusion &RHS);
 
 // Contains information about one file in the build grpah and its direct
 // dependencies. Doesn't own the strings it references (IncludeGraph is
 // self-contained).
 struct IncludeGraphNode {
public:
   // Usually it should be SM.getFileEntryForID(SM.getMainFileID())->getName().
   llvm::StringMap<unsigned> includeDepth(llvm::StringRef Root) const;
 
   // This updates IncludeDepth(), but not MainFileIncludes.
   void recordInclude(llvm::StringRef IncludingName,
                      llvm::StringRef IncludedName,
                      llvm::StringRef IncludedRealName);
 
+  // Classifying the main-file includes as "used" or "unused" is subtle
+  // (consider transitive includes), so we inject the algorithm.
+
+  // Maps including files (from) to included files (to).
+  using AbstractIncludeGraph = llvm::DenseMap<unsigned, SmallVector<unsigned>>;
+  // Decides usage for each file included by EntryPoint based on the set of
+  // files that contain some referenced symbol.
+  using UsedFunc = llvm::DenseMap<unsigned, bool>(
+      const AbstractIncludeGraph &, llvm::DenseSet<unsigned> Referenced,
+      unsigned EntryPoint);
+  // Produce decisions for all files included from \p EntryPoint (usually the
+  // main file).
+  void markUsed(llvm::StringRef EntryPoint,
+                llvm::ArrayRef<StringRef> ReferencedFiles,
+                llvm::function_ref<UsedFunc>);
+
 private:
   // Identifying files in a way that persists from preamble build to subsequent
   // builds is surprisingly hard. FileID is unavailable in InclusionDirective(),
   // and RealPathName and UniqueID are not preserved in the preamble.
   // We use the FileEntry::Name, which is stable, interned into a "file index".
   // The paths we want to expose are the RealPathName, so store those too.
   std::vector<std::string> RealPathNames; // In file index order.
   unsigned fileIndex(llvm::StringRef Name);

clang-tools-extra/clangd/Headers.cpp

for (const auto &Parent : PreviousLevel) {
             Result[Name] = Level;
         }
       }
     }
   }
   return Result;
 }
 
+void IncludeStructure::markUsed(llvm::StringRef EntryPoint,
+                                llvm::ArrayRef<StringRef> ReferencedFiles,
+                                llvm::function_ref<UsedFunc> Algorithm) {
+  auto Root = NameToIndex.find(EntryPoint);
+  if (Root == NameToIndex.end()) {
+    elog("IncludeCleaner: EntryPoint {0} not found in include graph",
+         EntryPoint);
+    return;
+  }
+
+  llvm::DenseSet<unsigned> Referenced;
+  Referenced.reserve(ReferencedFiles.size());
+  for (llvm::StringRef RefName : ReferencedFiles) {
+    dlog("{0} is REFERENCED", RefName);
+    auto It = NameToIndex.find(RefName);
+    if (It != NameToIndex.end())
+      Referenced.insert(It->second);
+  }
+
+  auto Decisions =
+      Algorithm(IncludeChildren, std::move(Referenced), Root->second);
+  auto RootChildren = IncludeChildren.find(Root->second);
+  assert(RootChildren != IncludeChildren.end());
+  llvm::DenseMap</*RealPath*/ StringRef, /*Index*/ unsigned> IncludeIndex;
+  for (const auto Index : RootChildren->second) {
+    if (!RealPathNames[Index].empty())
+      IncludeIndex[RealPathNames[Index]] = Index;
+  }
+  for (auto &MFI : MainFileIncludes) {
+    // FIXME: Skip includes that are not self-contained.
+    auto It = IncludeIndex.find(MFI.Resolved);
+    if (It != IncludeIndex.end()) {
+      auto DIt = Decisions.find(It->second);
+      if (DIt != Decisions.end()) {
+        MFI.Used = DIt->second;
+        dlog("{0} is {1}", MFI.Written, MFI.Used ? "USED" : "UNUSED");
+      }
+    }
+  }
+}
+
 void IncludeInserter::addExisting(const Inclusion &Inc) {
   IncludedHeaders.insert(Inc.Written);
   if (!Inc.Resolved.empty())
     IncludedHeaders.insert(Inc.Resolved);
 }
 
 /// FIXME(ioeric): we might not want to insert an absolute include path if the
 /// path is not shortened.

clang-tools-extra/clangd/IncludeCleaner.h

 /// 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. Those
+/// locations could be within macro expansions and are not resolved to their
+/// spelling locations.
+llvm::DenseSet<FileID> findReferencedFiles(const ReferencedLocations &Locs,
+                                           const SourceManager &SM);
+
+inline llvm::DenseMap<unsigned, bool>
+directlyReferencedFiles(const IncludeStructure::AbstractIncludeGraph &Graph,
+                        const llvm::DenseSet<unsigned> &Referenced,
+                        unsigned EntryPoint) {
+  llvm::DenseMap<unsigned, bool> Result;
+  for (unsigned Inclusion : Graph.lookup(EntryPoint))
+    Result.try_emplace(Inclusion, Referenced.contains(Inclusion));
+  return Result;
+}
+
 } // namespace clangd
 } // namespace clang
 
 #endif // LLVM_CLANG_TOOLS_EXTRA_CLANGD_INCLUDE_CLEANER_H

clang-tools-extra/clangd/IncludeCleaner.cpp

 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()};
+  // Group by FileID.
+  llvm::sort(Sorted);
+  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);
+}
+
 } // 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();
   }
 
+  void computeUsedIncludes();
+
 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<Decl *> LocalTopLevelDecls,
             llvm::Optional<std::vector<Diag>> Diags, IncludeStructure Includes,
             CanonicalIncludes CanonIncludes);
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 "FeatureModule.h"
 #include "Features.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);
 }
+
+void ParsedAST::computeUsedIncludes() {
+  const auto &SM = getSourceManager();
+
+  auto Refs = findReferencedLocations(*this);
+  auto ReferencedFileIDs = findReferencedFiles(Refs, SM);
+  std::vector<llvm::StringRef> ReferencedFilenames;
+  ReferencedFilenames.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;
+    }
+    ReferencedFilenames.push_back(SM.getFileEntryForID(FID)->getName());
+  }
+  Includes.markUsed(SM.getFileEntryForID(SM.getMainFileID())->getName(),
+                    ReferencedFilenames, directlyReferencedFiles);
+}
+
 } // namespace clangd
 } // namespace clang