[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

191

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

247

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

292

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

311

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

292

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

[kbobyrev]

Address review comments.

clang-tools-extra/clangd/IncludeCleaner.cpp

247

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

247

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

249

(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.

255

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 ↗

(On Diff #383253)

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.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 "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, const IncludeStructure &Includes,
+                       FileManager &FM, HeaderSearch &HeaderInfo) {
   // 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 = FM.getFile(Includes.getRealPath(
+      static_cast<IncludeStructure::HeaderID>(*Inc->HeaderID)));
+  assert(FE);
+  if (!HeaderInfo.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) {
   ReferencedLocations Result;
   ReferencedLocationCrawler Crawler(Result);
   Crawler.TraverseAST(AST.getASTContext());
findReferencedFiles(const llvm::DenseSet<SourceLocation> &Locs,
   return std::move(Result.Files);
 }
 
 std::vector<const Inclusion *>
 getUnused(const IncludeStructure &Structure,
           const llvm::DenseSet<IncludeStructure::HeaderID> &ReferencedFiles) {
   std::vector<const Inclusion *> Unused;
   for (const Inclusion &MFI : Structure.MainFileIncludes) {
     // FIXME: Skip includes that are not self-contained.
     if (!MFI.HeaderID) {
       elog("File {0} not found.", MFI.Written);
       continue;
     }
     auto IncludeID = static_cast<IncludeStructure::HeaderID>(*MFI.HeaderID);
     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) {
translateToHeaderIDs(const llvm::DenseSet<FileID> &Files,
   }
   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);
 }
 
 std::vector<Diag> issueUnusedIncludesDiagnostics(ParsedAST &AST,
                                                  llvm::StringRef Code) {
   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))
+    if (!mayConsiderUnused(Inc, AST.getIncludeStructure(),
+                           AST.getSourceManager().getFileManager(),
+                           AST.getPreprocessor().getHeaderSearchInfo()))
       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";

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 "no_guard.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";
+  // This header is unused but doesn't have a header guard meaning it is not
+  // self-contained and can have side effects. There will be no warning for it.
+  TU.AdditionalFiles["no_guard.h"] = R"cpp(
+    int side_effects = 42;
+  )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;