[clang-tidy] misc-include-cleaner: avoid duplicated fixes

[danix800]

Summary

Do deduplication when inserting missing headers when diags are not self contained.

Fixes https://github.com/llvm/llvm-project/issues/65285

[sammccall]

Thanks! @kadircet should make the call on these features (they look good to me), I have some implementation notes.

This is making two independent changes, one is a policy change that should be applied to the include-cleaner library, and one is a bugfix to the clang-tidy check. I think they should be separate patches.

clang-tools-extra/clang-tidy/misc/IncludeCleanerCheck.cpp

170

If we want this policy, it should be provided at the include-cleaner library level so it applies to all clients, not just the clang-tidy check.

I think the clearest way is to encapsulate this in include_cleaner::Includes, so that match() never matches a Header requirement against a duplicative Include. This will naturally lead to the directives being marked as unused.

(In practice, the result will work in clangd, and will respect configuration of headers where analysis should be ignored, keep directives, etc)

203

This means that if you're looking at individual diagnostics rather than applying all fixes to a file, only the first diagnostic will have any fix available at all.

I believe the preferred solution is to do this conditionally based on areDiagsSelfContained(). clang_tidy::utils::IncludeInserter encapsulates this, but isn't used here.

I don't know whether we would want to use it here, or how carefully it's already been considered. (It definitely contains a lot of logic that is dubious to apply when the include to insert has already been precisely calculated, but also some things that would be helpful). Will defer to Kadir on that.

[danix800]

clang-tools-extra/clang-tidy/misc/IncludeCleanerCheck.cpp

170

I'll leave the policy part to another revision (maybe by others).

203

Thanks for mentioning the clang_tidy::utils::IncludeInserter. I took a further look and found that IncludeInserter is
more suitable for this checker.

[danix800]

1. Use clang::tidy::utils::IncludeInserter to avoid repeated insertion;
2. Leave out the deduplication policy part.

[danix800]

Ping @kadircet~, could you please take a look at this revision?

[kadircet]

Thanks a lot for the patch @danix800 !

I initially was rather focused on behavior of this check in workflows that require seeing "self-contained-diags", but also I rather see the bulk-apply use cases as always requiring clang-format afterwards. Hence didn't really try to polish that use case a lot, but I believe changes in this patch improve those use cases reasonably. But users do still need to run clang-format afterwards, e.g. if we first generate a finding that inserts "b.h" and then "a.h", they'll be in wrong order. So this is only fixing some cases. If you'd like to work on a more complete approach, we can prepare all the edits in a single tooling::Replacements and run clang::format::cleanupAroundReplacements on top of it to generate proper edits, and emit FixIts with those merged replacements. Note that this still won't be enough in all cases, as there can be other checks that emit fixes that are touching includes :/

Regarding usage of IncludeInserter; we were deliberately not using IncludeInserter here, as it has slightly different semantics to HeaderIncludes, which is used by all the other applications of include-cleaner when producing edits. That way it's easier for us to reason about the behavior in various places (and also to fix them). But moreover, HeaderIncludes uses clang-format config to figure out include-styles and works with a bigger set of projects without requiring extra configurations (hence this patch will actually be a regression for those). Therefore can you keep using HeaderIncludes, while skipping generation of duplicate fixits when we're in non-self-contained-diags mode (assuming you don't want to generalize the approach as I explained above).

[danix800]

In D159263#4638167, @kadircet wrote:

Thanks a lot for the patch @danix800 !

I initially was rather focused on behavior of this check in workflows that require seeing "self-contained-diags", but also I rather see the bulk-apply use cases as always requiring clang-format afterwards. Hence didn't really try to polish that use case a lot, but I believe changes in this patch improve those use cases reasonably. But users do still need to run clang-format afterwards, e.g. if we first generate a finding that inserts "b.h" and then "a.h", they'll be in wrong order. So this is only fixing some cases. If you'd like to work on a more complete approach, we can prepare all the edits in a single tooling::Replacements and run clang::format::cleanupAroundReplacements on top of it to generate proper edits, and emit FixIts with those merged replacements. Note that this still won't be enough in all cases, as there can be other checks that emit fixes that are touching includes :/

Regarding usage of IncludeInserter; we were deliberately not using IncludeInserter here, as it has slightly different semantics to HeaderIncludes, which is used by all the other applications of include-cleaner when producing edits. That way it's easier for us to reason about the behavior in various places (and also to fix them). But moreover, HeaderIncludes uses clang-format config to figure out include-styles and works with a bigger set of projects without requiring extra configurations (hence this patch will actually be a regression for those). Therefore can you keep using HeaderIncludes, while skipping generation of duplicate fixits when we're in non-self-contained-diags mode (assuming you don't want to generalize the approach as I explained above).

Thanks for the background!

If we have further plans from upstream on these checker/clang-format related logic, I can wait and abandon this revision.

Or if such issue does need fixing then coud you take a look at the previous diff 1
which uses an internal set to prevent this issue?

[kadircet]

In D159263#4638199, @danix800 wrote:

If we have further plans from upstream on these checker/clang-format related logic, I can wait and abandon this revision.

Not at the moment, so please don't!

Or if such issue does need fixing then coud you take a look at the previous diff 1
which uses an internal set to prevent this issue?

Yes, I think that approach makes sense. But we should make it conditional on areDiagsSelfContained (basically de-duplicate only when diags are not self contained).

[danix800]

1. Revert to internal set (not using IncludeCleaner);
2. Only do deduplication when not areDiagsSelfContained().

[danix800]

Duplicated to https://github.com/llvm/llvm-project/pull/65431, abandon this one.

clang-tools-extra/clang-tidy/misc/IncludeCleanerCheck.h

 //===--- IncludeCleanerCheck.h - clang-tidy ---------------------*- 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
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_CLANG_TOOLS_EXTRA_CLANG_TIDY_MISC_INCLUDECLEANER_H
 #define LLVM_CLANG_TOOLS_EXTRA_CLANG_TIDY_MISC_INCLUDECLEANER_H
 
 #include "../ClangTidyCheck.h"
 #include "../ClangTidyDiagnosticConsumer.h"
 #include "../ClangTidyOptions.h"
+#include "../utils/IncludeInserter.h"
 #include "clang-include-cleaner/Record.h"
 #include "clang-include-cleaner/Types.h"
 #include "clang/ASTMatchers/ASTMatchFinder.h"
 #include "clang/Basic/LLVM.h"
+#include "clang/Basic/LangOptions.h"
 #include "clang/Basic/SourceLocation.h"
-#include "clang/Lex/HeaderSearch.h"
-#include "clang/Lex/Preprocessor.h"
 #include "llvm/Support/Regex.h"
 #include <vector>
 
 namespace clang::tidy::misc {
 
 /// Checks for unused and missing includes. Generates findings only for
 /// the main file of a translation unit.
 /// Findings correspond to https://clangd.llvm.org/design/include-cleaner.

 
 private:
   include_cleaner::RecordedPP RecordedPreprocessor;
   include_cleaner::PragmaIncludes RecordedPI;
   const Preprocessor *PP = nullptr;
   std::vector<StringRef> IgnoreHeaders;
   // Whether emit only one finding per usage of a symbol.
   const bool DeduplicateFindings;
+  utils::IncludeInserter IncludeInserter;
   llvm::SmallVector<llvm::Regex> IgnoreHeadersRegex;
   bool shouldIgnore(const include_cleaner::Header &H);
 };
 
 } // namespace clang::tidy::misc
 
 #endif // LLVM_CLANG_TOOLS_EXTRA_CLANG_TIDY_MISC_INCLUDECLEANER_H

clang-tools-extra/clang-tidy/misc/IncludeCleanerCheck.cpp

 //===--- IncludeCleanerCheck.cpp - clang-tidy -----------------------------===//
 //
 // 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 "IncludeCleanerCheck.h"
 #include "../ClangTidyCheck.h"
 #include "../ClangTidyDiagnosticConsumer.h"
 #include "../ClangTidyOptions.h"
+#include "../utils/IncludeSorter.h"
 #include "../utils/OptionsUtils.h"
 #include "clang-include-cleaner/Analysis.h"
 #include "clang-include-cleaner/IncludeSpeller.h"
 #include "clang-include-cleaner/Record.h"
 #include "clang-include-cleaner/Types.h"
 #include "clang/AST/ASTContext.h"
 #include "clang/AST/Decl.h"
 #include "clang/AST/DeclBase.h"
 #include "clang/ASTMatchers/ASTMatchFinder.h"
 #include "clang/ASTMatchers/ASTMatchers.h"
 #include "clang/Basic/Diagnostic.h"
 #include "clang/Basic/FileEntry.h"
 #include "clang/Basic/LLVM.h"
 #include "clang/Basic/LangOptions.h"
 #include "clang/Basic/SourceLocation.h"
-#include "clang/Format/Format.h"
 #include "clang/Lex/Preprocessor.h"
 #include "clang/Tooling/Core/Replacement.h"
-#include "clang/Tooling/Inclusions/HeaderIncludes.h"
 #include "llvm/ADT/DenseSet.h"
 #include "llvm/ADT/STLExtras.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/ADT/StringRef.h"
 #include "llvm/Support/ErrorHandling.h"
 #include "llvm/Support/Path.h"
 #include "llvm/Support/Regex.h"
-#include <optional>
 #include <string>
 #include <vector>
 
 using namespace clang::ast_matchers;
 
 namespace clang::tidy::misc {
 
 namespace {
 struct MissingIncludeInfo {
   include_cleaner::SymbolReference SymRef;
   include_cleaner::Header Missing;
 };
 } // namespace
 
 IncludeCleanerCheck::IncludeCleanerCheck(StringRef Name,
                                          ClangTidyContext *Context)
     : ClangTidyCheck(Name, Context),
       IgnoreHeaders(utils::options::parseStringList(
           Options.getLocalOrGlobal("IgnoreHeaders", ""))),
       DeduplicateFindings(
-          Options.getLocalOrGlobal("DeduplicateFindings", true)) {
+          Options.getLocalOrGlobal("DeduplicateFindings", true)),
+      IncludeInserter(Options.getLocalOrGlobal("IncludeStyle",
+                                               utils::IncludeSorter::IS_LLVM),
+                      areDiagsSelfContained()) {
   for (const auto &Header : IgnoreHeaders) {
     if (!llvm::Regex{Header}.isValid())
       configurationDiag("Invalid ignore headers regex '%0'") << Header;
     std::string HeaderSuffix{Header.str()};
     if (!Header.ends_with("$"))
       HeaderSuffix += "$";
     IgnoreHeadersRegex.emplace_back(HeaderSuffix);
   }
 }
 
 void IncludeCleanerCheck::storeOptions(ClangTidyOptions::OptionMap &Opts) {
   Options.store(Opts, "IgnoreHeaders",
                 utils::options::serializeStringList(IgnoreHeaders));
+  Options.store(Opts, "IncludeStyle", IncludeInserter.getStyle());
   Options.store(Opts, "DeduplicateFindings", DeduplicateFindings);
 }
 
 bool IncludeCleanerCheck::isLanguageVersionSupported(
     const LangOptions &LangOpts) const {
   return !LangOpts.ObjC;
 }
 
 void IncludeCleanerCheck::registerMatchers(MatchFinder *Finder) {
   Finder->addMatcher(translationUnitDecl().bind("top"), this);
 }
 
 void IncludeCleanerCheck::registerPPCallbacks(const SourceManager &SM,
                                               Preprocessor *PP,
                                               Preprocessor *ModuleExpanderPP) {
+  IncludeInserter.registerPreprocessor(PP);
   PP->addPPCallbacks(RecordedPreprocessor.record(*PP));
   this->PP = PP;
   RecordedPI.record(*PP);
 }
 
 bool IncludeCleanerCheck::shouldIgnore(const include_cleaner::Header &H) {
   return llvm::any_of(IgnoreHeadersRegex, [&H](const llvm::Regex &R) {
     switch (H.kind()) {
void IncludeCleanerCheck::check(const MatchFinder::MatchResult &Result) {
   for (const include_cleaner::Include &I :
        RecordedPreprocessor.Includes.all()) {
     if (Used.contains(&I) || !I.Resolved)
       continue;
     if (RecordedPI.shouldKeep(*I.Resolved))
       continue;
     // Check if main file is the public interface for a private header. If so
     // we shouldn't diagnose it as unused.
     if (auto PHeader = RecordedPI.getPublic(*I.Resolved); !PHeader.empty()) {
       PHeader = PHeader.trim("<>\"");
       // Since most private -> public mappings happen in a verbatim way, we
       // check textually here. This might go wrong in presence of symlinks or
       // header mappings. But that's not different than rest of the places.
       if (getCurrentMainFile().endswith(PHeader))
         continue;
     }
 
     if (llvm::none_of(
             IgnoreHeadersRegex,
             [Resolved = (*I.Resolved).getFileEntry().tryGetRealPathName()](
                 const llvm::Regex &R) { return R.match(Resolved); }))
       Unused.push_back(&I);
   }
 
-  llvm::StringRef Code = SM->getBufferData(SM->getMainFileID());
-  auto FileStyle =
-      format::getStyle(format::DefaultFormatStyle, getCurrentMainFile(),
-                       format::DefaultFallbackStyle, Code,
-                       &SM->getFileManager().getVirtualFileSystem());
-  if (!FileStyle)
-    FileStyle = format::getLLVMStyle();
-
   for (const auto *Inc : Unused) {
     diag(Inc->HashLocation, "included header %0 is not used directly")
         << llvm::sys::path::filename(Inc->Spelled,
                                      llvm::sys::path::Style::posix)
         << FixItHint::CreateRemoval(CharSourceRange::getCharRange(
                SM->translateLineCol(SM->getMainFileID(), Inc->Line, 1),
                SM->translateLineCol(SM->getMainFileID(), Inc->Line + 1, 1)));
   }
 
-  tooling::HeaderIncludes HeaderIncludes(getCurrentMainFile(), Code,
-                                         FileStyle->IncludeStyle);
   for (const auto &Inc : Missing) {
     std::string Spelling = include_cleaner::spellHeader(
         {Inc.Missing, PP->getHeaderSearchInfo(), MainFile});
-    bool Angled = llvm::StringRef{Spelling}.starts_with("<");
-    // We might suggest insertion of an existing include in edge cases, e.g.,
-    // include is present in a PP-disabled region, or spelling of the header
-    // turns out to be the same as one of the unresolved includes in the
-    // main file.
-    if (auto Replacement =
-            HeaderIncludes.insert(llvm::StringRef{Spelling}.trim("\"<>"),
-                                  Angled, tooling::IncludeDirective::Include))
-      diag(SM->getSpellingLoc(Inc.SymRef.RefLocation),
-           "no header providing \"%0\" is directly included")
-          << Inc.SymRef.Target.name()
-          << FixItHint::CreateInsertion(
-                 SM->getComposedLoc(SM->getMainFileID(),
-                                    Replacement->getOffset()),
-                 Replacement->getReplacementText());
+        << IncludeInserter.createMainFileIncludeInsertion(
+               llvm::StringRef{Spelling}.trim("\""));
   }
 }
 
 } // namespace clang::tidy::misc

clang-tools-extra/test/clang-tidy/checkers/misc/Inputs/baz.h

 #pragma once
+#define BAZ 10
 int baz();

clang-tools-extra/test/clang-tidy/checkers/misc/include-cleaner.cpp

 // RUN: %check_clang_tidy %s misc-include-cleaner %t -- -- -I%S/Inputs -isystem%S/Inputs/system
 #include "bar.h"
 // CHECK-FIXES: {{^}}#include "baz.h"{{$}}
 #include "foo.h"
 // CHECK-MESSAGES: :[[@LINE-1]]:1: warning: included header foo.h is not used directly [misc-include-cleaner]
 // CHECK-FIXES: {{^}}
 // CHECK-FIXES: {{^}}#include <string>{{$}}
 #include <vector.h>
 // CHECK-MESSAGES: :[[@LINE-1]]:1: warning: included header vector.h is not used directly [misc-include-cleaner]
 // CHECK-FIXES: {{^}}
 int BarResult = bar();
 int BazResult = baz();
 // CHECK-MESSAGES: :[[@LINE-1]]:17: warning: no header providing "baz" is directly included [misc-include-cleaner]
+int BazResultAgain = BAZ; // Header should not be inserted more than once
+// CHECK-MESSAGES: :[[@LINE-1]]:22: warning: no header providing "BAZ" is directly included [misc-include-cleaner]
 std::string HelloString;
 // CHECK-MESSAGES: :[[@LINE-1]]:6: warning: no header providing "std::string" is directly included [misc-include-cleaner]
 int FooBarResult = foobar();
 // CHECK-MESSAGES: :[[@LINE-1]]:20: warning: no header providing "foobar" is directly included [misc-include-cleaner]