[clangd] prototype: Implement unused include warnings with include-cleaner library.

[hokein]

Summary

A prototype of using include-cleaner library in clangd:

• (re)implement clangd's "unused include" warnings with the library
• the new implementation is hidden under a flag Config::UnusedIncludesPolicy::Experiment

[hokein]

rebase and update

[kadircet]

regarding testing, i think updating all tests that we have in IncludeCleanerTests that call computeUnusedIncludes to also call the new function that'll use include-cleaner library should be enough.

clang-tools-extra/clangd/CMakeLists.txt

5

can you move this near the include_directories for clang-tidy below (near line 63)

clang-tools-extra/clangd/Config.h

91

can you also add a comment saying that "Experiment tries to provide the same behaviour as Strict but using include-cleaner"

clang-tools-extra/clangd/IncludeCleaner.cpp

470

agreed, let's change StdlibHeaders in IncludeStructure to actually be a BySpelling mapping, it should be no-op for existing implementation as we're only checking for stdlib headers already (and there's no other usage)

478

this might behave slightly different than what we have in RecordedPP, and rest of the applications of include-cleaner will be using that. can we expose the pieces in RecordedPP that collects MacroRefs as a separate handler and attach that collector (combined with the skipped range collection inside CollectMainFileMacros and also still converting to MainFileMacros in the end (as we can't store sourcelocations/identifierinfos from preamble)?

afterwards we can use the names stored in there to get back to IdentifierInfos and Ranges stored to get back to SourceLocations. WDYT?

486

you can get the IdentifierInfo using Name inside Macro and PP.

511

let's use getUnused directly here, with an empty set of PublicHeaders.

528

can you keep computeUnusedIncludes the same and introduce a new function that'll call include_cleaner? afterwards we can just do a switch on policy here and call the relevant function.

clang-tools-extra/clangd/ParsedAST.cpp

594

why do we need to collect pragmas in main file? i think we already have necessary information available via IncludeStructure (it stores keeps and exports, and we don't care about anything else in the main file AFAICT). so let's just use the PragmaIncludes we're getting from the Preamble directly? without even making a copy and returning a reference from the Preamble instead in ParsedAST::getPragmaIncludes

[hokein]

address comments.

clang-tools-extra/clangd/IncludeCleaner.cpp

470

sure, I will address it in a followup patch.

478

Yeah, this is a better solution, but I'm not sure whether we should do this before the release cut, it has a side effect of changing the find-macro-reference behavior in clangd. It requires some design/implement work.

I agree that the current solution is hacky, and eventually will be replaced, but it follows the existing findReferencedMacros, so it is not that bad. I tend to land this version before the release cut. What do you think?

486

oh, right. Done.

clang-tools-extra/clangd/ParsedAST.cpp

594

i think we already have necessary information available via IncludeStructure (it stores keeps and exports, and we don't care about anything else in the main file AFAICT)

The IncludeStructure doesn't have a full support for IWYU export pragma, it only tracks the headers that have the export pragma.

My understand of the end goal is to use the PragmaInclude to handle every IWYU-related things, and we can remove all these IWYU bits in the IncludeStructure, clangd IWYU pragma handling code.

[hokein]

update the tests.

[kadircet]

clang-tools-extra/clangd/IncludeCleaner.cpp

478

Yeah, this is a better solution, but I'm not sure whether we should do this before the release cut, it has a side effect of changing the find-macro-reference behavior in clangd.

OK, i think you're right about possibly changing semantic highlighting&refs for clangd. Let's push this as a follow-up after the branch cut then.

It requires some design/implement work.

No action needed here just wanted to layout some ideas;
We just need to change the implementation details of CollectMainFileMacros to wrap the RecordedPP and add skipped ranges support to it. We might need to do a little plumbing to convert between types (as RecordedPP stores SourceLocations/MacroInfos that can't be used across preamble and AST) but that should be trivial to marshal (we can do the conversion inside EndOfMainFile). I haven't fully tried this though, so if you tried and faced certain incompatibilities PLMK.

I agree that the current solution is hacky, and eventually will be replaced, but it follows the existing findReferencedMacros, so it is not that bad. I tend to land this version before the release cut. What do you think?

I am worried that landing this version and letting people use it for 6 months might result in us getting bug reports that we can't address until we converge (or even worse get bug reports due to behavior change after we converge). But changes here are somewhat more justified as we put this as an experimental feature, compared to regressions in existing clangd behavior as you pointed out.

clang-tools-extra/clangd/IncludeCleaner.h

100 ↗

(On Diff #490287)

s/computeUnusedIncludesNew/computeUnusedIncludesExperimental/

can you also add a comment saying that this uses include-cleaner library to perform usage analysis?

clang-tools-extra/clangd/ParsedAST.cpp

594

The IncludeStructure doesn't have a full support for IWYU export pragma, it only tracks the headers that have the export pragma.

And I think that's all we need for IWYU pragmas inside the main file (as main file is a leaf and exporting headers from it doesn't change anything apart from making sure we keep them around)

My understand of the end goal is to use the PragmaInclude to handle every IWYU-related things, and we can remove all these IWYU bits in the IncludeStructure, clangd IWYU pragma handling code.

Yes, I agree with some version of that, but until then this is introducing some extra changes (+ copying around more information in every AST build). So can we leave this piece out of the initial patch and just use the PragmaInclude we have from Preamble without copying it around?

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

345 ↗

(On Diff #490287)

can you inline the call to computeUnusedIncludes into the EXPECT statement here?

382 ↗

(On Diff #490287)

can you also update the test here to have same structure as below?

[hokein]

address comments:

• rename to computeUnusedIncludesExperimental
• use PragmaInclude from preamble, limit the scope of the patch

clang-tools-extra/clangd/ParsedAST.cpp

594

Yes, I agree with some version of that, but until then this is introducing some extra changes (+ copying around more information in every AST build). So can we leave this piece out of the initial patch and just use the PragmaInclude we have from Preamble without copying it around?

Sure, that sounds a good plan, and have a better narrowed scope of the patch.

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

345 ↗

(On Diff #490287)

sure, since this is not directly related to this patch, addressed in ccb67491f0dd55c5bd8ed5f71cb802422bfaa969.

[kadircet]

thanks!

clang-tools-extra/clangd/ParsedAST.h

110

can you add a comment saying might be null if AST is built without a preamble?

[ckandeler]

With this, I now get:
FAILED: bin/clangd-fuzzer
: && /usr/lib/icecream/libexec/icecc/bin/c++ -fPIC -fno-semantic-interposition -fvisibility-inlines-hidden -Werror=date-time -Wall -Wextra -Wno-unused-parameter -Wwrite-strings -Wcast-qual -Wno-missing-field-initializers -pedantic -Wno-long-long -Wimplicit-fallthrough -Wno-maybe-uninitialized -Wno-class-memaccess -Wno-redundant-move -Wno-pessimizing-move -Wno-noexcept-type -Wdelete-non-virtual-dtor -Wsuggest-override -Wno-comment -Wno-misleading-indentation -Wctad-maybe-unsupported -fdiagnostics-color -ffunction-sections -fdata-sections -fno-common -Woverloaded-virtual -fno-strict-aliasing -O2 -g -DNDEBUG -fuse-ld=lld -Wl,--color-diagnostics -Wl,--gc-sections tools/clang/tools/extra/clangd/fuzzer/CMakeFiles/clangd-fuzzer.dir/FuzzerClangdMain.cpp.o tools/clang/tools/extra/clangd/fuzzer/CMakeFiles/clangd-fuzzer.dir/clangd-fuzzer.cpp.o -o bin/clangd-fuzzer -Wl,-rpath,"\$ORIGIN/../lib" lib/libclangDaemon.a lib/libclangdSupport.a lib/libclangPseudo.a lib/libclangPseudoGrammar.a lib/libclangTidyAndroidModule.a lib/libclangTidyAbseilModule.a lib/libclangTidyAlteraModule.a lib/libclangTidyBoostModule.a lib/libclangTidyCERTModule.a lib/libclangTidyConcurrencyModule.a lib/libclangTidyDarwinModule.a lib/libclangTidyFuchsiaModule.a lib/libclangTidyHICPPModule.a lib/libclangTidyBugproneModule.a lib/libclangTidyCppCoreGuidelinesModule.a lib/libclangTidyGoogleModule.a lib/libclangTidyLinuxKernelModule.a lib/libclangTidyLLVMModule.a lib/libclangTidyLLVMLibcModule.a lib/libclangTidyMiscModule.a lib/libclangAnalysis.a lib/libclangASTMatchers.a lib/libclangAST.a lib/libclangLex.a lib/libclangBasic.a lib/libclangTidyModernizeModule.a lib/libclangTidyObjCModule.a lib/libclangTidyOpenMPModule.a lib/libclangTidyPerformanceModule.a lib/libclangTidyPortabilityModule.a lib/libclangTidyReadabilityModule.a lib/libclangTidyZirconModule.a lib/libclangTidyMPIModule.a lib/libclangTidyUtils.a lib/libclangTidy.a lib/libclang-cpp.so.16git lib/libLLVM-16git.so && :
ld.lld: error: undefined symbol: clang::include_cleaner::walkUsed(llvm::ArrayRef<clang::Decl*>, llvm::ArrayRef<clang::include_cleaner::SymbolReference>, clang::include_cleaner::PragmaIncludes const*, clang::SourceManager const&, llvm::function_ref<void (clang::include_cleaner::SymbolReference const&, llvm::ArrayRef<clang::include_cleaner::Header>)>)

referenced by IncludeCleaner.cpp:504 (/sda/home/christian/dev/llvm/clang-tools-extra/clangd/IncludeCleaner.cpp:504)

IncludeCleaner.cpp.o:(clang::clangd::computeUnusedIncludesExperimental(clang::clangd::ParsedAST&) (.localalias)) in archive lib/libclangDaemon.a

[hokein]

In D140875#4065763, @ckandeler wrote:

With this, I now get:
FAILED: bin/clangd-fuzzer
: && /usr/lib/icecream/libexec/icecc/bin/c++ -fPIC -fno-semantic-interposition -fvisibility-inlines-hidden -Werror=date-time -Wall -Wextra -Wno-unused-parameter -Wwrite-strings -Wcast-qual -Wno-missing-field-initializers -pedantic -Wno-long-long -Wimplicit-fallthrough -Wno-maybe-uninitialized -Wno-class-memaccess -Wno-redundant-move -Wno-pessimizing-move -Wno-noexcept-type -Wdelete-non-virtual-dtor -Wsuggest-override -Wno-comment -Wno-misleading-indentation -Wctad-maybe-unsupported -fdiagnostics-color -ffunction-sections -fdata-sections -fno-common -Woverloaded-virtual -fno-strict-aliasing -O2 -g -DNDEBUG -fuse-ld=lld -Wl,--color-diagnostics -Wl,--gc-sections tools/clang/tools/extra/clangd/fuzzer/CMakeFiles/clangd-fuzzer.dir/FuzzerClangdMain.cpp.o tools/clang/tools/extra/clangd/fuzzer/CMakeFiles/clangd-fuzzer.dir/clangd-fuzzer.cpp.o -o bin/clangd-fuzzer -Wl,-rpath,"\$ORIGIN/../lib" lib/libclangDaemon.a lib/libclangdSupport.a lib/libclangPseudo.a lib/libclangPseudoGrammar.a lib/libclangTidyAndroidModule.a lib/libclangTidyAbseilModule.a lib/libclangTidyAlteraModule.a lib/libclangTidyBoostModule.a lib/libclangTidyCERTModule.a lib/libclangTidyConcurrencyModule.a lib/libclangTidyDarwinModule.a lib/libclangTidyFuchsiaModule.a lib/libclangTidyHICPPModule.a lib/libclangTidyBugproneModule.a lib/libclangTidyCppCoreGuidelinesModule.a lib/libclangTidyGoogleModule.a lib/libclangTidyLinuxKernelModule.a lib/libclangTidyLLVMModule.a lib/libclangTidyLLVMLibcModule.a lib/libclangTidyMiscModule.a lib/libclangAnalysis.a lib/libclangASTMatchers.a lib/libclangAST.a lib/libclangLex.a lib/libclangBasic.a lib/libclangTidyModernizeModule.a lib/libclangTidyObjCModule.a lib/libclangTidyOpenMPModule.a lib/libclangTidyPerformanceModule.a lib/libclangTidyPortabilityModule.a lib/libclangTidyReadabilityModule.a lib/libclangTidyZirconModule.a lib/libclangTidyMPIModule.a lib/libclangTidyUtils.a lib/libclangTidy.a lib/libclang-cpp.so.16git lib/libLLVM-16git.so && :
ld.lld: error: undefined symbol: clang::include_cleaner::walkUsed(llvm::ArrayRef<clang::Decl*>, llvm::ArrayRef<clang::include_cleaner::SymbolReference>, clang::include_cleaner::PragmaIncludes const*, clang::SourceManager const&, llvm::function_ref<void (clang::include_cleaner::SymbolReference const&, llvm::ArrayRef<clang::include_cleaner::Header>)>)

referenced by IncludeCleaner.cpp:504 (/sda/home/christian/dev/llvm/clang-tools-extra/clangd/IncludeCleaner.cpp:504)

IncludeCleaner.cpp.o:(clang::clangd::computeUnusedIncludesExperimental(clang::clangd::ParsedAST&) (.localalias)) in archive lib/libclangDaemon.a

sorry, should be fixed in https://github.com/llvm/llvm-project/commit/e84d69f52d9a9fab9162128d8fe8ebec99ea60da.

[raj.khem]

In D140875#4065824, @hokein wrote:

In D140875#4065763, @ckandeler wrote:

With this, I now get:
FAILED: bin/clangd-fuzzer
: && /usr/lib/icecream/libexec/icecc/bin/c++ -fPIC -fno-semantic-interposition -fvisibility-inlines-hidden -Werror=date-time -Wall -Wextra -Wno-unused-parameter -Wwrite-strings -Wcast-qual -Wno-missing-field-initializers -pedantic -Wno-long-long -Wimplicit-fallthrough -Wno-maybe-uninitialized -Wno-class-memaccess -Wno-redundant-move -Wno-pessimizing-move -Wno-noexcept-type -Wdelete-non-virtual-dtor -Wsuggest-override -Wno-comment -Wno-misleading-indentation -Wctad-maybe-unsupported -fdiagnostics-color -ffunction-sections -fdata-sections -fno-common -Woverloaded-virtual -fno-strict-aliasing -O2 -g -DNDEBUG -fuse-ld=lld -Wl,--color-diagnostics -Wl,--gc-sections tools/clang/tools/extra/clangd/fuzzer/CMakeFiles/clangd-fuzzer.dir/FuzzerClangdMain.cpp.o tools/clang/tools/extra/clangd/fuzzer/CMakeFiles/clangd-fuzzer.dir/clangd-fuzzer.cpp.o -o bin/clangd-fuzzer -Wl,-rpath,"\$ORIGIN/../lib" lib/libclangDaemon.a lib/libclangdSupport.a lib/libclangPseudo.a lib/libclangPseudoGrammar.a lib/libclangTidyAndroidModule.a lib/libclangTidyAbseilModule.a lib/libclangTidyAlteraModule.a lib/libclangTidyBoostModule.a lib/libclangTidyCERTModule.a lib/libclangTidyConcurrencyModule.a lib/libclangTidyDarwinModule.a lib/libclangTidyFuchsiaModule.a lib/libclangTidyHICPPModule.a lib/libclangTidyBugproneModule.a lib/libclangTidyCppCoreGuidelinesModule.a lib/libclangTidyGoogleModule.a lib/libclangTidyLinuxKernelModule.a lib/libclangTidyLLVMModule.a lib/libclangTidyLLVMLibcModule.a lib/libclangTidyMiscModule.a lib/libclangAnalysis.a lib/libclangASTMatchers.a lib/libclangAST.a lib/libclangLex.a lib/libclangBasic.a lib/libclangTidyModernizeModule.a lib/libclangTidyObjCModule.a lib/libclangTidyOpenMPModule.a lib/libclangTidyPerformanceModule.a lib/libclangTidyPortabilityModule.a lib/libclangTidyReadabilityModule.a lib/libclangTidyZirconModule.a lib/libclangTidyMPIModule.a lib/libclangTidyUtils.a lib/libclangTidy.a lib/libclang-cpp.so.16git lib/libLLVM-16git.so && :
ld.lld: error: undefined symbol: clang::include_cleaner::walkUsed(llvm::ArrayRef<clang::Decl*>, llvm::ArrayRef<clang::include_cleaner::SymbolReference>, clang::include_cleaner::PragmaIncludes const*, clang::SourceManager const&, llvm::function_ref<void (clang::include_cleaner::SymbolReference const&, llvm::ArrayRef<clang::include_cleaner::Header>)>)

referenced by IncludeCleaner.cpp:504 (/sda/home/christian/dev/llvm/clang-tools-extra/clangd/IncludeCleaner.cpp:504)

IncludeCleaner.cpp.o:(clang::clangd::computeUnusedIncludesExperimental(clang::clangd::ParsedAST&) (.localalias)) in archive lib/libclangDaemon.a

sorry, should be fixed in https://github.com/llvm/llvm-project/commit/e84d69f52d9a9fab9162128d8fe8ebec99ea60da.

this seems to be not enough, I am also seeing clangd build failiures

/mnt/b/yoe/master/build/tmp/hosttools/ld: lib/libclangDaemon.a(Preamble.cpp.o): in function `clang::clangd::(anonymous namespace)::CppFilePreambleCallbacks::BeforeExecute(clang::CompilerInstance&)':
Preamble.cpp:(.text._ZN5clang6clangd12_GLOBAL__N_124CppFilePreambleCallbacks13BeforeExecuteERNS_16CompilerInstanceE+0x8b): undefined reference to `clang::include_cleaner::PragmaIncludes::record(clang::CompilerInsta
nce const&)'
/mnt/b/yoe/master/build/tmp/hosttools/ld: lib/libclangDaemon.a(IncludeCleaner.cpp.o): in function `clang::clangd::computeUnusedIncludesExperimental(clang::clangd::ParsedAST&) [clone .localalias]':
IncludeCleaner.cpp:(.text._ZN5clang6clangd33computeUnusedIncludesExperimentalERNS0_9ParsedASTE+0x3a1): undefined reference to `clang::include_cleaner::walkUsed(llvm::ArrayRef<clang::Decl*>, llvm::ArrayRef<clang::in
clude_cleaner::SymbolReference>, clang::include_cleaner::PragmaIncludes const*, clang::SourceManager const&, llvm::function_ref<void (clang::include_cleaner::SymbolReference const&, llvm::ArrayRef<clang::include_cl
eaner::Header>)>)'
collect2: error: ld returned 1 exit status
[193/193] Linking CXX executable bin/clangd
FAILED: bin/clangd

[glandium]

I'm still seeing the build error on clangd-fuzzer on a commit that clearly has e84d69f52d9a9fab9162128d8fe8ebec99ea60da in its history.

[glandium]

with -DLLVM_LINK_LLVM_DYLIB=ON, in case it matters.

[kadircet]

sorry for the hassle 2133e8b9f942f91ec54e28c580fccf6d6b26c62e should fix

[hokein]

oops, sorry for the trouble it caused, and thanks for @kadircet fixing it.

clang-tools-extra/clangd/CMakeLists.txt

 # This is a no-op for building files in this dir, but is inherited by subdirs.
 include_directories(${CMAKE_CURRENT_SOURCE_DIR})
 include_directories(${CMAKE_CURRENT_BINARY_DIR})
 
+include_directories(${CMAKE_CURRENT_SOURCE_DIR}/../include-cleaner/include)
+
 add_subdirectory(support)
 
 # Configure the Features.inc file.
 if (NOT DEFINED CLANGD_BUILD_XPC)
   if(${CMAKE_SYSTEM_NAME} MATCHES "Darwin")
     set(CLANGD_BUILD_XPC_DEFAULT ON)
   else ()
     set(CLANGD_BUILD_XPC_DEFAULT OFF)

 clang_target_link_libraries(clangDaemon
   PRIVATE
   clangAST
   clangASTMatchers
   clangBasic
   clangDriver
   clangFormat
   clangFrontend
+  clangIncludeCleaner
   clangIndex
   clangLex
   clangSema
   clangSerialization
   clangTooling
   clangToolingCore
   clangToolingInclusions
   clangToolingInclusionsStdlib

clang-tools-extra/clangd/Config.h

struct Config {
   /// Controls index behavior.
   struct {
     /// Whether this TU should be background-indexed.
     BackgroundPolicy Background = BackgroundPolicy::Build;
     ExternalIndexSpec External;
     bool StandardLibrary = true;
   } Index;
 
-  enum UnusedIncludesPolicy { Strict, None };
+  enum UnusedIncludesPolicy { Strict, None, Experiment };
   /// Controls warnings and errors when parsing code.
   struct {
     bool SuppressAll = false;
     llvm::StringSet<> Suppress;
 
     /// Configures what clang-tidy checks to run and options to use with them.
     struct {
       // A comma-seperated list of globs specify which clang-tidy checks to run.

clang-tools-extra/clangd/ConfigCompile.cpp

if (!Normalized.empty())
           [Normalized(std::move(Normalized))](const Params &, Config &C) {
             if (C.Diagnostics.SuppressAll)
               return;
             for (llvm::StringRef N : Normalized)
               C.Diagnostics.Suppress.insert(N);
           });
 
     if (F.UnusedIncludes)
-      if (auto Val = compileEnum<Config::UnusedIncludesPolicy>(
-                         "UnusedIncludes", **F.UnusedIncludes)
-                         .map("Strict", Config::UnusedIncludesPolicy::Strict)
-                         .map("None", Config::UnusedIncludesPolicy::None)
-                         .value())
+      if (auto Val =
+              compileEnum<Config::UnusedIncludesPolicy>("UnusedIncludes",
+                                                        **F.UnusedIncludes)
+                  .map("Experiment", Config::UnusedIncludesPolicy::Experiment)
         Out.Apply.push_back([Val](const Params &, Config &C) {
           C.Diagnostics.UnusedIncludes = *Val;
         });
     compile(std::move(F.Includes));
 
     compile(std::move(F.ClangTidy));
   }
 

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 "Headers.h"
 #include "ParsedAST.h"
 #include "Protocol.h"
 #include "SourceCode.h"
+#include "clang-include-cleaner/Analysis.h"
+#include "clang-include-cleaner/Types.h"
 #include "index/CanonicalIncludes.h"
 #include "support/Logger.h"
 #include "support/Trace.h"
 #include "clang/AST/ASTContext.h"
 #include "clang/AST/ExprCXX.h"
 #include "clang/AST/RecursiveASTVisitor.h"
 #include "clang/Basic/SourceLocation.h"
 #include "clang/Basic/SourceManager.h"
translateToHeaderIDs(const ReferencedFiles &Files,
   for (tooling::stdlib::Header StdlibUsed : Files.Stdlib)
     for (auto HID : Includes.StdlibHeaders.lookup(StdlibUsed))
       TranslatedHeaderIDs.insert(HID);
   return TranslatedHeaderIDs;
 }
 
 std::vector<const Inclusion *> computeUnusedIncludes(ParsedAST &AST) {
   const auto &SM = AST.getSourceManager();
+  const auto &Includes = AST.getIncludeStructure();
+  const Config &Cfg = Config::current();
+  if (Cfg.Diagnostics.UnusedIncludes ==
+      Config::UnusedIncludesPolicy::Experiment) {
+    llvm::DenseSet<IncludeStructure::HeaderID> Used;
+
+    // FIXME: this map should probably be in IncludeStructure.
+    llvm::StringMap<llvm::SmallVector<IncludeStructure::HeaderID>> BySpelling;
+    for (const auto &Inc : Includes.MainFileIncludes) {
+      if (Inc.HeaderID)
+        BySpelling.try_emplace(Inc.Written)
+            .first->second.push_back(
+                static_cast<IncludeStructure::HeaderID>(*Inc.HeaderID));
+    }
+    // FIXME: pass the macro references.
+    include_cleaner::walkUsed(
+        AST.getLocalTopLevelDecls(), /*MacroRefs=*/{}, &AST.getPragmaIncludes(),
+        SM,
+        [&](const include_cleaner::SymbolReference &Ref,
+            llvm::ArrayRef<include_cleaner::Header> Providers) {
+          for (const auto &H : Providers) {
+            switch (H.kind()) {
+            case include_cleaner::Header::Physical:
+              if (auto HeaderID = Includes.getID(H.physical()))
+                Used.insert(*HeaderID);
+              break;
+            case include_cleaner::Header::Standard:
+              for (auto HeaderID : Includes.StdlibHeaders.lookup(H.standard()))
+                Used.insert(HeaderID);
+              break;
+            case include_cleaner::Header::Verbatim:
+              for (auto HeaderID : BySpelling.lookup(H.verbatim()))
+                Used.insert(HeaderID);
+              break;
+            }
+          }
+        });
+    std::vector<const Inclusion *> Unused;
+    for (const auto &I : Includes.MainFileIncludes) {
+      // non-existing headers may not have header ID!
+      if (!I.HeaderID)
+        continue;
+      auto HID = static_cast<IncludeStructure::HeaderID>(*I.HeaderID);
+      // FIXME: use mayConsiderUnused to respect the AnalyzeStdlib and
+      // IgnoreHeader options, but it also does extra IWYU-related filterings
+      // which we don't need.
+      if (!Used.contains(HID) &&
+          !AST.getPragmaIncludes().shouldKeep(I.HashLine + 1) &&
+          mayConsiderUnused(I, AST, Cfg))
+        Unused.push_back(&I);
+    }
+    return Unused;
+  }
 
   auto Refs = findReferencedLocations(AST);
   auto ReferencedFiles =
-      findReferencedFiles(Refs, AST.getIncludeStructure(),
-                          AST.getCanonicalIncludes(), AST.getSourceManager());
-  auto ReferencedHeaders =
-      translateToHeaderIDs(ReferencedFiles, AST.getIncludeStructure(), SM);
+      findReferencedFiles(Refs, Includes, AST.getCanonicalIncludes(), SM);
+  auto ReferencedHeaders = translateToHeaderIDs(ReferencedFiles, Includes, SM);
   return getUnused(AST, ReferencedHeaders, ReferencedFiles.SpelledUmbrellas);
 }
 
 std::vector<Diag> issueUnusedIncludesDiagnostics(ParsedAST &AST,
                                                  llvm::StringRef Code) {
   const Config &Cfg = Config::current();
-  if (Cfg.Diagnostics.UnusedIncludes != Config::UnusedIncludesPolicy::Strict ||
+  if (Cfg.Diagnostics.UnusedIncludes == Config::UnusedIncludesPolicy::None ||
       Cfg.Diagnostics.SuppressAll ||
       Cfg.Diagnostics.Suppress.contains("unused-includes"))
     return {};
   // Interaction is only polished for C/CPP.
   if (AST.getLangOpts().ObjC)
     return {};
   trace::Span Tracer("IncludeCleaner::issueUnusedIncludesDiagnostics");
   std::vector<Diag> Result;

clang-tools-extra/clangd/ParsedAST.h

 #ifndef LLVM_CLANG_TOOLS_EXTRA_CLANGD_PARSEDAST_H
 #define LLVM_CLANG_TOOLS_EXTRA_CLANGD_PARSEDAST_H
 
 #include "CollectMacros.h"
 #include "Compiler.h"
 #include "Diagnostics.h"
 #include "Headers.h"
 #include "Preamble.h"
+#include "clang-include-cleaner/Record.h"
 #include "index/CanonicalIncludes.h"
 #include "support/Path.h"
 #include "clang/Frontend/FrontendAction.h"
 #include "clang/Lex/Preprocessor.h"
 #include "clang/Tooling/Syntax/Tokens.h"
 #include "llvm/ADT/ArrayRef.h"
 #include "llvm/ADT/Optional.h"
 #include "llvm/ADT/StringRef.h"
public:
   /// file, including those in the preamble region.
   const MainFileMacros &getMacros() const;
   /// Gets all pragma marks in the main file.
   const std::vector<PragmaMark> &getMarks() const;
   /// Tokens recorded while parsing the main file.
   /// (!) does not have tokens from the preamble.
   const syntax::TokenBuffer &getTokens() const { return Tokens; }
 
+  const include_cleaner::PragmaIncludes &getPragmaIncludes() const {
+    return Pragmas;
+  }
+
   /// Returns the version of the ParseInputs this AST was built from.
   llvm::StringRef version() const { return Version; }
 
   /// Returns the path passed by the caller when building this AST.
   PathRef tuPath() const { return TUPath; }
 
   /// Returns the version of the ParseInputs used to build Preamble part of this
   /// AST. Might be std::nullopt if no Preamble is used.
   llvm::Optional<llvm::StringRef> preambleVersion() const;
 
   const HeuristicResolver *getHeuristicResolver() const {
     return Resolver.get();
   }
 
 private:
   ParsedAST(PathRef TUPath, 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<PragmaMark> Marks,
             std::vector<Decl *> LocalTopLevelDecls,
             llvm::Optional<std::vector<Diag>> Diags, IncludeStructure Includes,
-            CanonicalIncludes CanonIncludes);
+            CanonicalIncludes CanonIncludes,
+            include_cleaner::PragmaIncludes Pragmas);
 
   Path TUPath;
   std::string Version;
   // In-memory preambles must outlive the AST, it is important that this member
   // goes before Clang and Action.
   std::shared_ptr<const PreambleData> Preamble;
   // We store an "incomplete" FrontendAction (i.e. no EndSourceFile was called
   // on it) and CompilerInstance used to run it. That way we don't have to do
private:
   // Data, stored after parsing. std::nullopt if AST was built with a stale
   // preamble.
   llvm::Optional<std::vector<Diag>> Diags;
   // 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;
+  include_cleaner::PragmaIncludes Pragmas;
   std::unique_ptr<HeuristicResolver> Resolver;
 };
 
 } // namespace clangd
 } // namespace clang
 
 #endif // LLVM_CLANG_TOOLS_EXTRA_CLANGD_PARSEDAST_H

clang-tools-extra/clangd/ParsedAST.cpp

 #include "FeatureModule.h"
 #include "Headers.h"
 #include "HeuristicResolver.h"
 #include "IncludeCleaner.h"
 #include "IncludeFixer.h"
 #include "Preamble.h"
 #include "SourceCode.h"
 #include "TidyProvider.h"
+#include "clang-include-cleaner/Record.h"
 #include "index/CanonicalIncludes.h"
 #include "index/Index.h"
 #include "support/Logger.h"
 #include "support/Trace.h"
 #include "clang/AST/ASTContext.h"
 #include "clang/AST/Decl.h"
 #include "clang/Basic/Diagnostic.h"
 #include "clang/Basic/DiagnosticSema.h"
if (Inputs.Index && !BuildDir.getError()) {
                                               const clang::Diagnostic &Info) {
         return FixIncludes->fix(DiagLevl, Info);
       });
       Clang->setExternalSemaSource(FixIncludes->unresolvedNameRecorder());
     }
   }
 
   IncludeStructure Includes;
+  include_cleaner::PragmaIncludes Pragmas;
   // If we are using a preamble, copy existing includes.
   if (Preamble) {
     Includes = Preamble->Includes;
+    Pragmas = Preamble->Pragmas;
     Includes.MainFileIncludes = Patch->preambleIncludes();
     // Replay the preamble includes so that clang-tidy checks can see them.
     ReplayPreamble::attach(Patch->preambleIncludes(), *Clang,
                            Patch->modifiedBounds());
   }
   // Important: collectIncludeStructure is registered *after* ReplayPreamble!
   // Otherwise we would collect the replayed includes again...
   // (We can't *just* use the replayed includes, they don't have Resolved path).
   Includes.collect(*Clang);
+  if (Config::current().Diagnostics.UnusedIncludes ==
+      Config::UnusedIncludesPolicy::Experiment)
+    Pragmas.record(*Clang);
   // Copy over the macros in the preamble region of the main file, and combine
   // with non-preamble macros below.
   MainFileMacros Macros;
   if (Preamble)
     Macros = Preamble->Macros;
   Clang->getPreprocessor().addPPCallbacks(
       std::make_unique<CollectMainFileMacros>(Clang->getSourceManager(),
                                               Macros));
// Finally, add diagnostics coming from the AST.
       std::vector<Diag> D = ASTDiags.take(&*CTContext);
       Diags->insert(Diags->end(), D.begin(), D.end());
     }
   }
   ParsedAST Result(Filename, Inputs.Version, std::move(Preamble),
                    std::move(Clang), std::move(Action), std::move(Tokens),
                    std::move(Macros), std::move(Marks), std::move(ParsedDecls),
                    std::move(Diags), std::move(Includes),
-                   std::move(CanonIncludes));
+                   std::move(CanonIncludes), std::move(Pragmas));
   if (Result.Diags) {
     auto UnusedHeadersDiags =
         issueUnusedIncludesDiagnostics(Result, Inputs.Contents);
     Result.Diags->insert(Result.Diags->end(),
                          make_move_iterator(UnusedHeadersDiags.begin()),
                          make_move_iterator(UnusedHeadersDiags.end()));
   }
   return std::move(Result);

 ParsedAST::ParsedAST(PathRef TUPath, 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<PragmaMark> Marks,
                      std::vector<Decl *> LocalTopLevelDecls,
                      llvm::Optional<std::vector<Diag>> Diags,
-                     IncludeStructure Includes, CanonicalIncludes CanonIncludes)
+                     IncludeStructure Includes, CanonicalIncludes CanonIncludes,
+                     include_cleaner::PragmaIncludes Pragmas)
     : TUPath(TUPath), Version(Version), Preamble(std::move(Preamble)),
       Clang(std::move(Clang)), Action(std::move(Action)),
       Tokens(std::move(Tokens)), Macros(std::move(Macros)),
       Marks(std::move(Marks)), Diags(std::move(Diags)),
       LocalTopLevelDecls(std::move(LocalTopLevelDecls)),
-      Includes(std::move(Includes)), CanonIncludes(std::move(CanonIncludes)) {
+      Includes(std::move(Includes)), CanonIncludes(std::move(CanonIncludes)),
+      Pragmas(std::move(Pragmas)) {
   Resolver = std::make_unique<HeuristicResolver>(getASTContext());
   assert(this->Clang);
   assert(this->Action);
 }
 
 llvm::Optional<llvm::StringRef> ParsedAST::preambleVersion() const {
   if (!Preamble)
     return std::nullopt;
   return llvm::StringRef(Preamble->Version);
 }
 
 } // namespace clangd
 } // namespace clang

clang-tools-extra/clangd/Preamble.h

 #ifndef LLVM_CLANG_TOOLS_EXTRA_CLANGD_PREAMBLE_H
 #define LLVM_CLANG_TOOLS_EXTRA_CLANGD_PREAMBLE_H
 
 #include "CollectMacros.h"
 #include "Compiler.h"
 #include "Diagnostics.h"
 #include "FS.h"
 #include "Headers.h"
+#include "clang-include-cleaner/Record.h"
 #include "index/CanonicalIncludes.h"
 #include "support/Path.h"
 #include "clang/Frontend/CompilerInvocation.h"
 #include "clang/Frontend/PrecompiledPreamble.h"
 #include "clang/Lex/Lexer.h"
 #include "clang/Tooling/CompilationDatabase.h"
 #include "llvm/ADT/StringRef.h"
 
struct PreambleData {
   // Version of the ParseInputs this preamble was built from.
   std::string Version;
   tooling::CompileCommand CompileCommand;
   PrecompiledPreamble Preamble;
   std::vector<Diag> Diags;
   // Processes like code completions and go-to-definitions will need #include
   // information, and their compile action skips preamble range.
   IncludeStructure Includes;
+
+  include_cleaner::PragmaIncludes Pragmas;
   // Macros defined in the preamble section of the main file.
   // Users care about headers vs main-file, not preamble vs non-preamble.
   // These should be treated as main-file entities e.g. for code completion.
   MainFileMacros Macros;
   // Pragma marks defined in the preamble section of the main file.
   std::vector<PragmaMark> Marks;
   // Cache of FS operations performed when building the preamble.
   // When reusing a preamble, this cache can be consumed to save IO.

clang-tools-extra/clangd/Preamble.cpp

 //===--- Preamble.cpp - Reusing expensive parts of the AST ----------------===//
 //
 // 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 "Preamble.h"
 #include "Compiler.h"
 #include "Config.h"
 #include "Headers.h"
 #include "SourceCode.h"
+#include "clang-include-cleaner/Record.h"
 #include "support/Logger.h"
 #include "support/ThreadsafeFS.h"
 #include "support/Trace.h"
 #include "clang/AST/DeclTemplate.h"
 #include "clang/Basic/Diagnostic.h"
 #include "clang/Basic/DiagnosticLex.h"
 #include "clang/Basic/LangOptions.h"
 #include "clang/Basic/SourceLocation.h"
CppFilePreambleCallbacks(
         BeforeExecuteCallback(std::move(BeforeExecuteCallback)) {}
 
   IncludeStructure takeIncludes() { return std::move(Includes); }
 
   MainFileMacros takeMacros() { return std::move(Macros); }
 
   std::vector<PragmaMark> takeMarks() { return std::move(Marks); }
 
+  include_cleaner::PragmaIncludes takePragmaIncludes() {
+    return std::move(Pragmas);
+  }
   CanonicalIncludes takeCanonicalIncludes() { return std::move(CanonIncludes); }
 
   bool isMainFileIncludeGuarded() const { return IsMainFileIncludeGuarded; }
 
   void AfterExecute(CompilerInstance &CI) override {
     if (ParsedCallback) {
       trace::Span Tracer("Running PreambleCallback");
       ParsedCallback(CI.getASTContext(), CI.getPreprocessor(), CanonIncludes);
void AfterExecute(CompilerInstance &CI) override {
     }
   }
 
   void BeforeExecute(CompilerInstance &CI) override {
     CanonIncludes.addSystemHeadersMapping(CI.getLangOpts());
     LangOpts = &CI.getLangOpts();
     SourceMgr = &CI.getSourceManager();
     Includes.collect(CI);
+    if (Config::current().Diagnostics.UnusedIncludes ==
+        Config::UnusedIncludesPolicy::Experiment)
+      Pragmas.record(CI);
     if (BeforeExecuteCallback)
       BeforeExecuteCallback(CI);
   }
 
   std::unique_ptr<PPCallbacks> createPPCallbacks() override {
     assert(SourceMgr && LangOpts &&
            "SourceMgr and LangOpts must be set at this point");
 
bool shouldSkipFunctionBody(Decl *D) override {
     return true;
   }
 
 private:
   PathRef File;
   PreambleParsedCallback ParsedCallback;
   IncludeStructure Includes;
   CanonicalIncludes CanonIncludes;
+  include_cleaner::PragmaIncludes Pragmas;
   MainFileMacros Macros;
   std::vector<PragmaMark> Marks;
   bool IsMainFileIncludeGuarded = false;
   std::unique_ptr<CommentHandler> IWYUHandler = nullptr;
   const clang::LangOptions *LangOpts = nullptr;
   const SourceManager *SourceMgr = nullptr;
   PreambleBuildStats *Stats;
   bool ParseForwardingFunctions;
log("Built preamble of size {0} for file {1} version {2} in {3} seconds",
          BuiltPreamble->getSize(), FileName, Inputs.Version,
          PreambleTimer.getTime());
     std::vector<Diag> Diags = PreambleDiagnostics.take();
     auto Result = std::make_shared<PreambleData>(std::move(*BuiltPreamble));
     Result->Version = Inputs.Version;
     Result->CompileCommand = Inputs.CompileCommand;
     Result->Diags = std::move(Diags);
     Result->Includes = CapturedInfo.takeIncludes();
+    Result->Pragmas = CapturedInfo.takePragmaIncludes();
     Result->Macros = CapturedInfo.takeMacros();
     Result->Marks = CapturedInfo.takeMarks();
     Result->CanonIncludes = CapturedInfo.takeCanonicalIncludes();
     Result->StatCache = std::move(StatCache);
     Result->MainIsIncludeGuarded = CapturedInfo.isMainFileIncludeGuarded();
     return Result;
   }
 

clang-tools-extra/include-cleaner/include/clang-include-cleaner/Record.h

 /// other use-instead-like mechanisms (#pragma include_instead) on included
 /// files.
 ///
 /// This is a low-level piece being used in the "Location => Header" analysis
 /// step to determine the final public header rather than the header directly
 /// defines the symbol.
 class PragmaIncludes {
 public:
+  PragmaIncludes() = default;
+  PragmaIncludes(PragmaIncludes &&) = default;
+  PragmaIncludes &operator=(PragmaIncludes &&) = default;
+
+  PragmaIncludes(const PragmaIncludes &);
+  PragmaIncludes &operator=(const PragmaIncludes &);
+
   /// Installs an analysing PPCallback and CommentHandler and populates results
   /// to the structure.
   void record(const CompilerInstance &CI);
 
   /// Returns true if the given #include of the main-file should never be
   /// removed.
   bool shouldKeep(unsigned HashLineNumber) const {
     return ShouldKeep.find(HashLineNumber) != ShouldKeep.end();

clang-tools-extra/include-cleaner/lib/Record.cpp

 
 } // namespace
 
 class PragmaIncludes::RecordPragma : public PPCallbacks, public CommentHandler {
 public:
   RecordPragma(const CompilerInstance &CI, PragmaIncludes *Out)
       : SM(CI.getSourceManager()),
         HeaderInfo(CI.getPreprocessor().getHeaderSearchInfo()), Out(Out),
-        UniqueStrings(Arena) {}
+        UniqueStrings(Out->Arena) {}
 
   void FileChanged(SourceLocation Loc, FileChangeReason Reason,
                    SrcMgr::CharacteristicKind FileType,
                    FileID PrevFID) override {
     InMainFile = SM.isWrittenInMainFile(Loc);
 
     if (Reason == PPCallbacks::ExitFile) {
       // At file exit time HeaderSearchInfo is valid and can be used to
public:
 
   void EndOfMainFile() override {
     for (auto &It : Out->IWYUExportBy) {
       llvm::sort(It.getSecond());
       It.getSecond().erase(
           std::unique(It.getSecond().begin(), It.getSecond().end()),
           It.getSecond().end());
     }
-    Out->Arena = std::move(Arena);
   }
 
   void InclusionDirective(SourceLocation HashLoc, const Token &IncludeTok,
                           llvm::StringRef FileName, bool IsAngled,
                           CharSourceRange /*FilenameRange*/,
                           OptionalFileEntryRef File,
                           llvm::StringRef /*SearchPath*/,
                           llvm::StringRef /*RelativePath*/,

 
 private:
   StringRef save(llvm::StringRef S) { return UniqueStrings.save(S); }
 
   bool InMainFile = false;
   const SourceManager &SM;
   HeaderSearch &HeaderInfo;
   PragmaIncludes *Out;
-  llvm::BumpPtrAllocator Arena;
   /// Intern table for strings. Contents are on the arena.
   llvm::StringSaver UniqueStrings;
 
   struct ExportPragma {
     // The line number where we saw the begin_exports or export pragma.
     int SeenAtLine = 0; // 1-based line number.
     // The file where we saw the pragma.
     FileID SeenAtFile;
struct KeepPragma {
     // true if it is a block begin/end_keep pragma; false if it is a
     // single-line keep pragma.
     bool Block = false;
   };
   // A stack for tracking all open begin_keep pragmas or single-line keeps.
   std::vector<KeepPragma> KeepStack;
 };
 
+PragmaIncludes::PragmaIncludes(const PragmaIncludes & In) {
+  *this = In;
+}
+
+PragmaIncludes &PragmaIncludes::operator=(const PragmaIncludes &In) {
+  ShouldKeep = In.ShouldKeep;
+  NonSelfContainedFiles = In.NonSelfContainedFiles;
+  Arena.Reset();
+  llvm::UniqueStringSaver Strings(Arena);
+  IWYUPublic.clear();
+  for (const auto& It : In.IWYUPublic)
+    IWYUPublic.try_emplace(It.first, Strings.save(It.second));
+  IWYUExportBy.clear();
+  for (const auto& UIDAndExporters : In.IWYUExportBy) {
+    const auto& [UID, Exporters] = UIDAndExporters;
+    for (StringRef ExporterHeader : Exporters)
+       IWYUExportBy.try_emplace(UID).first->second.push_back(ExporterHeader);
+  }
+  return *this;
+ }
+
 void PragmaIncludes::record(const CompilerInstance &CI) {
   auto Record = std::make_unique<RecordPragma>(CI, this);
   CI.getPreprocessor().addCommentHandler(Record.get());
   CI.getPreprocessor().addPPCallbacks(std::move(Record));
 }
 
 llvm::StringRef PragmaIncludes::getPublic(const FileEntry *F) const {
   auto It = IWYUPublic.find(F->getUniqueID());