[clangd] Avoid expensive checks of buffer names in IncludeCleaner

[sammccall]

Summary

This changes the handling of special buffers (<command-line> etc) that
SourceManager treats as files but FileManager does not.

We now include them in findReferencedFiles() and drop them as part of
translateToHeaderIDs(). This pairs more naturally with the data representations
we're using, and so avoids a bunch of converting between representations for
filtering.

[kbobyrev]

Thank you for taking care of this!

clang-tools-extra/clangd/IncludeCleaner.cpp

261

Implementation-wise, this seems like the right place to drop nonexistent "headers". However, this is a very surprising behavior from something like "translateToHeaderIDs" for two reasons:

• As the name states, it used to be a simple "translation" process, now it's also filtering.
• TranslatedHeaderIDs.size() == Files.size() can be rather unexpected

We never had 1:1 order etc translation assumptions but this is certainly the new behavior we want to document.

261

Thinking out loud: now I'm also thinking about the "handle non self-contained files" + "drop warnings for files without include warnings"

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

275

nit: Drop the parenthesis?

[sammccall]

clang-tools-extra/clangd/IncludeCleaner.cpp

261

This function is mapping from a domain (FileIDs excluding macros) where special buffers exist to a codomain (HeaderIDs) where they don't. Some sort of filtering/handling is implied by the signature!
So I think it's not surprising at least if you think about it that way :-) But this definitely needs to be documented, I'll do that.

Thinking out loud: now I'm also thinking about the "handle non self-contained files" + "drop warnings for files without include warnings"

There may some small efficiency from mashing those into this loop as well, but I don't think it's worth the confusion.
The reason I put this one inline instead of as a separate filtering step is that the check we'd be doing is a natural part of the conversion. It's basically a form of parse, don't validate

[sammccall]

Add more docs

[kbobyrev]

LGTM, thanks!

clang-tools-extra/clangd/IncludeCleaner.h

 ///
 /// - 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.
+/// The output only includes things SourceManager sees as files (not macro IDs).
+/// This can include <built-in>, <scratch space> etc that are not true files.
 llvm::DenseSet<FileID> findReferencedFiles(const ReferencedLocations &Locs,
                                            const SourceManager &SM);
 
 /// Maps FileIDs to the internal IncludeStructure representation (HeaderIDs).
+/// FileIDs that are not true files (<built-in> etc) are dropped.
 llvm::DenseSet<IncludeStructure::HeaderID>
 translateToHeaderIDs(const llvm::DenseSet<FileID> &Files,
                      const IncludeStructure &Includes, const SourceManager &SM);
 
 /// Retrieves headers that are referenced from the main file but not used.
 std::vector<const Inclusion *>
 getUnused(const IncludeStructure &Includes,
           const llvm::DenseSet<IncludeStructure::HeaderID> &ReferencedFiles);

clang-tools-extra/clangd/IncludeCleaner.cpp

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) {
-    // Check if Loc is not written in a physical file.
-    if (FID.isInvalid() || SM.isWrittenInBuiltinFile(Loc) ||
-        SM.isWrittenInCommandLineFile(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();
-    // For token pasting operator in macros, spelling and expansion locations
-    // can be within a temporary buffer that Clang creates (scratch space or
-    // ScratchBuffer). That is not a real file we can include.
-    if (!SM.isWrittenInScratchSpace(Exp.getSpellingLoc()))
-      add(Exp.getSpellingLoc());
-    if (!SM.isWrittenInScratchSpace(Exp.getExpansionLocStart()))
-      add(Exp.getExpansionLocStart());
-    if (!SM.isWrittenInScratchSpace(Exp.getExpansionLocEnd()))
-      add(Exp.getExpansionLocEnd());
   }
 };
 
 // Returns the range starting at '#' and ending at EOL. Escaped newlines are not
 // handled.
 clangd::Range getDiagnosticRange(llvm::StringRef Code, unsigned HashOffset) {
   clangd::Range Result;
   Result.end = Result.start = offsetToPosition(Code, HashOffset);
for (const Inclusion &MFI : Structure.MainFileIncludes) {
     if (!ReferencedFiles.contains(IncludeID))
       Unused.push_back(&MFI);
     dlog("{0} is {1}", MFI.Written,
          ReferencedFiles.contains(IncludeID) ? "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
+
 llvm::DenseSet<IncludeStructure::HeaderID>
 translateToHeaderIDs(const llvm::DenseSet<FileID> &Files,
                      const IncludeStructure &Includes,
                      const SourceManager &SM) {
   llvm::DenseSet<IncludeStructure::HeaderID> TranslatedHeaderIDs;
   TranslatedHeaderIDs.reserve(Files.size());
   for (FileID FID : Files) {
     const FileEntry *FE = SM.getFileEntryForID(FID);
-    assert(FE);
+    if (!FE) {
+      assert(isSpecialBuffer(FID, SM));
+      continue;
+    }
     const auto File = Includes.getID(FE);
     assert(File);
     TranslatedHeaderIDs.insert(*File);
   }
   return TranslatedHeaderIDs;
 }
 
 std::vector<const Inclusion *> computeUnusedIncludes(ParsedAST &AST) {

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::ElementsAre;
 using ::testing::UnorderedElementsAre;
 
 TEST(IncludeCleaner, ReferencedLocations) {
   struct TestCase {
     std::string HeaderCode;
     std::string MainCode;
   };
   TestCase Cases[] = {
for (const auto &Include : computeUnusedIncludes(AST))
     UnusedIncludes.push_back(Include->Written);
   EXPECT_THAT(UnusedIncludes,
               UnorderedElementsAre("\"unused.h\"", "\"dir/unused.h\"",
                                    "<system_header.h>"));
 }
 
 TEST(IncludeCleaner, VirtualBuffers) {
   TestTU TU;
-  TU.Filename = "foo.cpp";
   TU.Code = R"cpp(
-    #include "macro_spelling_in_scratch_buffer.h"
+    #include "macros.h"
 
     using flags::FLAGS_FOO;
 
     // CLI will come from a define, __llvm__ is a built-in. In both cases, they
     // come from non-existent files.
     int y = CLI + __llvm__;
 
     int concat(a, b) = 42;
     )cpp";
   // The pasting operator in combination with DEFINE_FLAG will create
   // ScratchBuffer with `flags::FLAGS_FOO` that will have FileID but not
   // FileEntry.
-  TU.AdditionalFiles["macro_spelling_in_scratch_buffer.h"] = R"cpp(
+  TU.AdditionalFiles["macros.h"] = R"cpp(
     #define DEFINE_FLAG(X) \
     namespace flags { \
     int FLAGS_##X; \
     } \
 
     DEFINE_FLAG(FOO)
 
     #define ab x
     #define concat(x, y) x##y
     )cpp";
   TU.ExtraArgs = {"-DCLI=42"};
   ParsedAST AST = TU.build();
   auto &SM = AST.getSourceManager();
   auto &Includes = AST.getIncludeStructure();
+
   auto ReferencedFiles = findReferencedFiles(findReferencedLocations(AST), SM);
-  auto Entry = SM.getFileManager().getFile(
-      testPath("macro_spelling_in_scratch_buffer.h"));
-  ASSERT_TRUE(Entry);
-  auto FID = SM.translateFile(*Entry);
-  // No "<scratch space>" FID.
-  EXPECT_THAT(ReferencedFiles, UnorderedElementsAre(FID));
-  // Should not crash due to <scratch space> "files" missing from include
-  // structure.
-  EXPECT_THAT(
-      getUnused(Includes, translateToHeaderIDs(ReferencedFiles, Includes, SM)),
-      ::testing::IsEmpty());
+  llvm::StringSet<> ReferencedFileNames;
+  for (FileID FID : ReferencedFiles)
+    ReferencedFileNames.insert(
+        SM.getPresumedLoc(SM.getLocForStartOfFile(FID)).getFilename());
+  // Note we deduped the names as _number_ of <built-in>s is uninteresting.
+  EXPECT_THAT(ReferencedFileNames.keys(),
+              UnorderedElementsAre("<built-in>", "<scratch space>",
+                                   testPath("macros.h")));
+
+  // Should not crash due to FileIDs that are not headers.
+  auto ReferencedHeaders = translateToHeaderIDs(ReferencedFiles, Includes, SM);
+  std::vector<llvm::StringRef> ReferencedHeaderNames;
+  for (IncludeStructure::HeaderID HID : ReferencedHeaders)
+    ReferencedHeaderNames.push_back(Includes.getRealPath(HID));
+  // Non-header files are gone at this point.
+  EXPECT_THAT(ReferencedHeaderNames, ElementsAre(testPath("macros.h")));
+
+  // Sanity check.
+  EXPECT_THAT(getUnused(Includes, ReferencedHeaders), ::testing::IsEmpty());
 }
 
 } // namespace
 } // namespace clangd
 } // namespace clang