[clangd] IncludeCleaner: Skip non self-contained headers

[kbobyrev]

Summary

Headers without include guards might have side effects or can be the files we
don't want to consider (e.g. tablegen ".inc" files). Skip them when translating
headers to the HeaderIDs that we will consider as unused.

[kbobyrev]

Update the docs.

[kbobyrev]

Aww, I think this is the wrong place to do that.

[kbobyrev]

Put the check into the right place.

[kbobyrev]

Remove redundant changes.

[kbobyrev]

Revert docs change that is no longer true.

[sammccall]

clang-tools-extra/clangd/IncludeCleaner.cpp

192–213

this is a local helper only, just pass in ParsedAST instead of all the extra params?

249–250

this is fixed now (though I think it would be better addressed ~here)

298–299

while here, pull out findReferencedFiles into its own var, and leave a FIXME to adjust the set of referenced files to account for non-self-contained headers whose symbols can be attributed to their include parents

324–325

Oops, I missed this in previous review.

Why are we first computing which includes are unused (including ineligible) and then filtering some out, rather than doing this check in the loop in computeUnused?

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

1483

This can be now or later, but we can't/shouldn't jam every feature into one test case.
At some point we need to find a way to split this up into different cases, or at least not have many features that can only be tested at the diagnostic level.
(If we call mayConsiderUnused inside computeUnused as suggested above, this no longer has to be a diagnostic test)

[sammccall]

clang-tools-extra/clangd/IncludeCleaner.cpp

298–299

Sorry, this was meant to be an optional suggestion rather than an angry command :-)

[kbobyrev]

Address review comments.

clang-tools-extra/clangd/IncludeCleaner.cpp

249–250

That's what I had initially (you can see the previous version of the patch, after which I sent "oh, wrong place" and changed it). I think my idea was that this looks confusing from the API standpoint. Choosing to filter out non-guarded headers looks like a diagnostics decision and it looked awkward to me to do that here: what getUnused does is simply merge two data structures. I think it's somewhat similar to the patch where you mentioned "parse, don't validate" and it is a great argument: the <built-in> and <scratch-space> are indeed not "headers" in a sensible meaning of the term but non self-contained ones are.

I don't have a very strong opinion on this, so I put the filtering back here but I'm curious if you agree with my thoughs.

[kbobyrev]

Remove stale FIXME.

[sammccall]

clang-tools-extra/clangd/IncludeCleaner.cpp

249–250

Sorry, I was unclear: I meant we should put the call to mayConsiderUnused here, not that we should split it up and put half of it here. So the "written with <" check would also be at this point.

Choosing to filter out non-guarded headers looks like a diagnostics decision

I don't think so: we don't know that a header is unused if we suspect it of being an umbrella header or used for side effects. The reason we're choosing not to diagnose it doesn't have anything to do with diagnostics per se.
You could say "unused" has some more narrow definition, but that doesn't seem very useful to me.

what getUnused does is simply merge two data structures

Sure, because the nontrivial parts haven't been implemented yet :-) But its role is to make filtering decisions of Inclusions from the AST to support a high-level concept of "unused", so I think the filtering fits well here.
If we support a non-strict policy, I'd expect getUnused to implement that (maybe with helpers) and that's going to involve some more analysis too.

On the other hand, I think the role of the loop in issueUnusedIncludesDiagnostics *is* simply converting: between an unused include list to diagnostics.

I think it's somewhat similar to the patch where you mentioned "parse, don't validate" and it is a great argument: the <built-in> and <scratch-space> are indeed not "headers" in a sensible meaning of the term but non self-contained ones are.

I'm not sure the analogy holds: my argument was to do the filtering at the place where you're doing the conversion/parsing that might fail. But here we could perfectly well convert the unused FileIDs to unused Header IDs to unused Inclusions to diagnostics, it would just be logically wrong to do so. We have free choice of where to put that logic, and diagnostic conversion seems like the wrong place to me.

[kbobyrev]

Address review comments.

[kbobyrev]

Add a header guard in tests.

[sammccall]

clang-tools-extra/clangd/IncludeCleaner.cpp

250–251

(sorry, I missed this before)

We should not be elogging this case, we're already emitting a diagnostic and it doesn't indicate anything wrong with clangd itself.

256

This seems pretty vague text (particularly: what does valid mean, and is it valid but used or invalid but unused). Maybe "{0} was not used, but is not eligible to be diagnosed as unused"?

clang-tools-extra/clangd/IncludeCleaner.h

64

I'm slightly worried about these sorts of comments becoming stale, they're really just describing what we think "not used" means.

I'd replace it with something more general like "In unclear cases, headers are not marked as unused", but up to you

[kbobyrev]

Resolve the review comments.

clang-tools-extra/clangd/IncludeCleaner.h

 
 /// 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.
+/// In unclear cases, headers are not marked as unused.
 std::vector<const Inclusion *>
-getUnused(const IncludeStructure &Includes,
+getUnused(ParsedAST &AST,
           const llvm::DenseSet<IncludeStructure::HeaderID> &ReferencedFiles);
 
 std::vector<const Inclusion *> 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 "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/Support/FormatVariadic.h"
 #include "llvm/Support/Path.h"
 
 namespace clang {
 namespace clangd {
 namespace {
 
for (const syntax::Token &Tok :
     if (!Macro)
       continue;
     auto Loc = Macro->Info->getDefinitionLoc();
     if (Loc.isValid())
       Result.insert(Loc);
   }
 }
 
+bool mayConsiderUnused(const Inclusion &Inc, ParsedAST &AST) {
   // FIXME(kirillbobyrev): We currently do not support the umbrella headers.
-// Standard Library headers are typically umbrella headers, and system headers
-// are likely to be the Standard Library headers. Until we have a good support
-// for umbrella headers and Standard Library headers, don't warn about them.
-bool mayConsiderUnused(const Inclusion *Inc) {
-  return Inc->Written.front() != '<';
+  // Standard Library headers are typically umbrella headers, and system
+  // headers are likely to be the Standard Library headers. Until we have a
+  // good support for umbrella headers and Standard Library headers, don't warn
+  // about them.
+  if (Inc.Written.front() == '<')
+    return false;
+  // Headers without include guards have side effects and are not
+  // self-contained, skip them.
+  assert(Inc.HeaderID);
+  auto FE = AST.getSourceManager().getFileManager().getFile(
+      AST.getIncludeStructure().getRealPath(
+          static_cast<IncludeStructure::HeaderID>(*Inc.HeaderID)));
+  assert(FE);
+  if (!AST.getPreprocessor().getHeaderSearchInfo().isFileMultipleIncludeGuarded(
+          *FE)) {
+    dlog("{0} doesn't have header guard and will not be considered unused",
+         (*FE)->getName());
+    return false;
+  }
+  return true;
 }
 
 } // namespace
 
 ReferencedLocations findReferencedLocations(ParsedAST &AST) {
   trace::Span Tracer("IncludeCleaner::findReferencedLocations");
   ReferencedLocations Result;
   ReferencedLocationCrawler Crawler(Result);
for (auto It = Sorted.begin(); It < Sorted.end();) {
     do
       ++It;
     while (It != Sorted.end() && SM.isInFileID(*It, FID));
   }
   return std::move(Result.Files);
 }
 
 std::vector<const Inclusion *>
-getUnused(const IncludeStructure &Includes,
+getUnused(ParsedAST &AST,
           const llvm::DenseSet<IncludeStructure::HeaderID> &ReferencedFiles) {
   trace::Span Tracer("IncludeCleaner::getUnused");
   std::vector<const Inclusion *> Unused;
-  for (const Inclusion &MFI : Includes.MainFileIncludes) {
-    // FIXME: Skip includes that are not self-contained.
-    if (!MFI.HeaderID) {
-      elog("File {0} not found.", MFI.Written);
+  for (const Inclusion &MFI : AST.getIncludeStructure().MainFileIncludes) {
+    if (!MFI.HeaderID)
       continue;
-    }
     auto IncludeID = static_cast<IncludeStructure::HeaderID>(*MFI.HeaderID);
-    if (!ReferencedFiles.contains(IncludeID))
+    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,
-         ReferencedFiles.contains(IncludeID) ? "USED" : "UNUSED");
+    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();
for (FileID FID : Files) {
     TranslatedHeaderIDs.insert(*File);
   }
   return TranslatedHeaderIDs;
 }
 
 std::vector<const Inclusion *> computeUnusedIncludes(ParsedAST &AST) {
   const auto &SM = AST.getSourceManager();
 
   auto Refs = findReferencedLocations(AST);
-  auto ReferencedFiles = translateToHeaderIDs(findReferencedFiles(Refs, SM),
-                                              AST.getIncludeStructure(), SM);
-  return getUnused(AST.getIncludeStructure(), ReferencedFiles);
+  // 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<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)) {
-    if (!mayConsiderUnused(Inc))
-      continue;
     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.Name = "unused-includes";
     D.Source = Diag::DiagSource::Clangd;
     D.File = FileName;

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

TEST(Diagnostics, Tags) {
   EXPECT_THAT(*TU.build().getDiagnostics(),
               UnorderedElementsAre(
                   AllOf(Diag(Test.range("unused"), "unused variable 'x'"),
                         WithTag(DiagnosticTag::Unnecessary)),
                   AllOf(Diag(Test.range("deprecated"), "'bar' is deprecated"),
                         WithTag(DiagnosticTag::Deprecated))));
 }
 
 TEST(DiagnosticsTest, IncludeCleaner) {
   Annotations Test(R"cpp(
 $fix[[  $diag[[#include "unused.h"]]
-]]#include "used.h"
+]]
+  #include "used.h"
 
   #include <system_header.h>
 
   void foo() {
     used();
   }
   )cpp");
   TestTU TU;
   TU.Code = Test.code().str();
   TU.AdditionalFiles["unused.h"] = R"cpp(
+    #pragma once
     void unused() {}
   )cpp";
   TU.AdditionalFiles["used.h"] = R"cpp(
+    #pragma once
     void used() {}
   )cpp";
   TU.AdditionalFiles["system/system_header.h"] = "";
   TU.ExtraArgs = {"-isystem" + testPath("system")};
   // Off by default.
   EXPECT_THAT(*TU.build().getDiagnostics(), IsEmpty());
   Config Cfg;
   Cfg.Diagnostics.UnusedIncludes = Config::UnusedIncludesPolicy::Strict;

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

 
 namespace clang {
 namespace clangd {
 namespace {
 
 using ::testing::ElementsAre;
 using ::testing::UnorderedElementsAre;
 
+std::string guard(llvm::StringRef Code) {
+  return "#pragma once\n" + Code.str();
+}
+
 TEST(IncludeCleaner, ReferencedLocations) {
   struct TestCase {
     std::string HeaderCode;
     std::string MainCode;
   };
   TestCase Cases[] = {
       // DeclRefExpr
       {

 }
 
 TEST(IncludeCleaner, GetUnusedHeaders) {
   llvm::StringLiteral MainFile = R"cpp(
     #include "a.h"
     #include "b.h"
     #include "dir/c.h"
     #include "dir/unused.h"
+    #include "unguarded.h"
     #include "unused.h"
     #include <system_header.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["system/system_header.h"] = "";
+  TU.AdditionalFiles["foo.h"] = guard("void foo();");
+  TU.AdditionalFiles["a.h"] = guard("void a();");
+  TU.AdditionalFiles["b.h"] = guard("void b();");
+  TU.AdditionalFiles["dir/c.h"] = guard("void c();");
+  TU.AdditionalFiles["unused.h"] = guard("void unused();");
+  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);
   EXPECT_THAT(UnusedIncludes,
-              UnorderedElementsAre("\"unused.h\"", "\"dir/unused.h\"",
-                                   "<system_header.h>"));
+              UnorderedElementsAre("\"unused.h\"", "\"dir/unused.h\""));
 }
 
 TEST(IncludeCleaner, VirtualBuffers) {
   TestTU TU;
   TU.Code = R"cpp(
     #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["macros.h"] = R"cpp(
+    #ifndef MACROS_H
+    #define MACROS_H
+
     #define DEFINE_FLAG(X) \
     namespace flags { \
     int FLAGS_##X; \
     } \
 
     DEFINE_FLAG(FOO)
 
     #define ab x
     #define concat(x, y) x##y
+
+    #endif // MACROS_H
     )cpp";
   TU.ExtraArgs = {"-DCLI=42"};
   ParsedAST AST = TU.build();
   auto &SM = AST.getSourceManager();
   auto &Includes = AST.getIncludeStructure();
 
   auto ReferencedFiles = findReferencedFiles(findReferencedLocations(AST), SM);
   llvm::StringSet<> ReferencedFileNames;
TEST(IncludeCleaner, VirtualBuffers) {
   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());
+  EXPECT_THAT(getUnused(AST, ReferencedHeaders), ::testing::IsEmpty());
 }
 
 } // namespace
 } // namespace clangd
 } // namespace clang