[clangd] Refactor new include cleaner functionality into a separate class.

clang-tools-extra/clangd/IncludeCleaner.h

 /// to provide useful warnings in most popular scenarios but not 1:1 exact
 /// feature compatibility.
 ///
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_CLANG_TOOLS_EXTRA_CLANGD_INCLUDECLEANER_H
 #define LLVM_CLANG_TOOLS_EXTRA_CLANGD_INCLUDECLEANER_H
 
+#include "Config.h"
 #include "Headers.h"
 #include "ParsedAST.h"
 #include "index/CanonicalIncludes.h"
 #include "clang/Basic/SourceLocation.h"
 #include "clang/Tooling/Inclusions/StandardLibrary.h"
 #include "llvm/ADT/DenseSet.h"
 #include "llvm/ADT/STLFunctionalExtras.h"
 #include "llvm/ADT/StringSet.h"
 #include <optional>
 #include <vector>
 
 namespace clang {
 namespace clangd {
 
 struct ReferencedLocations {
   llvm::DenseSet<SourceLocation> User;
   llvm::DenseSet<tooling::stdlib::Symbol> Stdlib;
 };
 
+class CachedIncludeCleaner {
+
+public:
+  CachedIncludeCleaner(
+      ParsedAST &AST,
+      const std::vector<include_cleaner::SymbolReference> &MacroReferences)
+      : AST(AST), MacroReferences(MacroReferences), SM(AST.getSourceManager()) {
+  }
+
+  void run();
+  std::vector<std::pair<std::string, unsigned>> computeMissingIncludes();
+  std::vector<const Inclusion *> computeUnusedIncludesExperimental();
+
+private:
+  ParsedAST &AST;
+  const std::vector<include_cleaner::SymbolReference> &MacroReferences;
+  llvm::SmallVector<include_cleaner::SymbolReference> Refs;
+  llvm::SmallVector<llvm::SmallVector<include_cleaner::Header>> ProviderRefs;
+  SourceManager &SM;
+
+  include_cleaner::Includes
+  convertIncludes(const SourceManager &SM,
+                  std::vector<Inclusion> MainFileIncludes);
+};
+
 /// Finds locations of all symbols used in the main file.
 ///
 /// - RecursiveASTVisitor finds references to symbols and records their
 ///   associated locations. These may be macro expansions, and are not resolved
 ///   to their spelling or expansion location. These locations are later used to
 ///   determine which headers should be marked as "used" and "directly used".
 /// - If \p Tokens is not nullptr, we also examine all identifier tokens in the
 ///   file in case they reference macros macros.

 
 /// 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(ParsedAST &AST,
           const llvm::DenseSet<IncludeStructure::HeaderID> &ReferencedFiles,
           const llvm::StringSet<> &ReferencedPublicHeaders);
 
-std::vector<std::pair<std::string, unsigned>>
-computeMissingIncludes(ParsedAST &AST);
 std::vector<const Inclusion *> computeUnusedIncludes(ParsedAST &AST);
-// The same as computeUnusedIncludes, but it is an experimental and
-// include-cleaner-lib-based implementation.
-std::vector<const Inclusion *>
-computeUnusedIncludesExperimental(ParsedAST &AST);
 
-std::vector<Diag> issueMissingIncludesDiagnostics(ParsedAST &AST,
-                                                  llvm::StringRef Code);
-std::vector<Diag> issueUnusedIncludesDiagnostics(ParsedAST &AST,
-                                                 llvm::StringRef Code);
+std::vector<Diag>
+issueMissingIncludesDiagnostics(CachedIncludeCleaner &IncludeCleaner,
+                                ParsedAST &AST, llvm::StringRef Code);
+std::vector<Diag>
+issueUnusedIncludesDiagnostics(CachedIncludeCleaner &IncludeCleaner,
+                               ParsedAST &AST, llvm::StringRef Code);
 
 /// Affects whether standard library includes should be considered for
 /// removal. This is off by default for now due to implementation limitations:
 /// - macros are not tracked
 /// - symbol names without a unique associated header are not tracked
 /// - references to std-namespaced C types are not properly tracked:
 ///   instead of std::size_t -> <cstddef> we see ::size_t -> <stddef.h>
 /// FIXME: remove this hack once the implementation is good enough.
 void setIncludeCleanerAnalyzesStdlib(bool B);
 
 } // namespace clangd
 } // namespace clang
 
 #endif // LLVM_CLANG_TOOLS_EXTRA_CLANGD_INCLUDECLEANER_H

clang-tools-extra/clangd/IncludeCleaner.cpp

 #include "clang/Basic/SourceLocation.h"
 #include "clang/Basic/SourceManager.h"
 #include "clang/Lex/HeaderSearch.h"
 #include "clang/Lex/Preprocessor.h"
 #include "clang/Tooling/Syntax/Tokens.h"
 #include "llvm/ADT/ArrayRef.h"
 #include "llvm/ADT/STLFunctionalExtras.h"
 #include "llvm/ADT/SmallString.h"
+#include "llvm/ADT/SmallVector.h"
 #include "llvm/ADT/StringRef.h"
 #include "llvm/ADT/StringSet.h"
 #include "llvm/Support/FormatVariadic.h"
 #include "llvm/Support/Path.h"
 #include "llvm/Support/Regex.h"
 #include <functional>
 #include <optional>
 #include <vector>
 
 namespace clang {
 namespace clangd {
 
 static bool AnalyzeStdlib = false;
 void setIncludeCleanerAnalyzesStdlib(bool B) { AnalyzeStdlib = B; }
 
+static bool mayConsiderUnused(const Inclusion &Inc, ParsedAST &AST,
+                              const Config &Cfg) {
+  if (Inc.BehindPragmaKeep)
+    return false;
+
+  // FIXME(kirillbobyrev): We currently do not support the umbrella headers.
+  // System headers are likely to be standard library headers.
+  // Until we have good support for umbrella headers, don't warn about them.
+  if (Inc.Written.front() == '<') {
+    if (AnalyzeStdlib && tooling::stdlib::Header::named(Inc.Written))
+      return true;
+    return false;
+  }
+  assert(Inc.HeaderID);
+  auto HID = static_cast<IncludeStructure::HeaderID>(*Inc.HeaderID);
+  // FIXME: Ignore the headers with IWYU export pragmas for now, remove this
+  // check when we have more precise tracking of exported headers.
+  if (AST.getIncludeStructure().hasIWYUExport(HID))
+    return false;
+  auto FE = AST.getSourceManager().getFileManager().getFileRef(
+      AST.getIncludeStructure().getRealPath(HID));
+  assert(FE);
+  // Headers without include guards have side effects and are not
+  // self-contained, skip them.
+  if (!AST.getPreprocessor().getHeaderSearchInfo().isFileMultipleIncludeGuarded(
+          &FE->getFileEntry())) {
+    dlog("{0} doesn't have header guard and will not be considered unused",
+         FE->getName());
+    return false;
+  }
+  for (auto &Filter : Cfg.Diagnostics.Includes.IgnoreHeader) {
+    // Convert the path to Unix slashes and try to match against the filter.
+    llvm::SmallString<64> Path(Inc.Resolved);
+    llvm::sys::path::native(Path, llvm::sys::path::Style::posix);
+    if (Filter(Inc.Resolved)) {
+      dlog("{0} header is filtered out by the configuration", FE->getName());
+      return false;
+    }
+  }
+  return true;
+}
+
+std::vector<const Inclusion *> getUnused(ParsedAST &AST,
+          const llvm::DenseSet<IncludeStructure::HeaderID> &ReferencedFiles,
+          const llvm::StringSet<> &ReferencedPublicHeaders) {
+  trace::Span Tracer("IncludeCleaner::getUnused");
+  const Config &Cfg = Config::current();
+  std::vector<const Inclusion *> Unused;
+  for (const Inclusion &MFI : AST.getIncludeStructure().MainFileIncludes) {
+    if (!MFI.HeaderID)
+      continue;
+    if (ReferencedPublicHeaders.contains(MFI.Written))
+      continue;
+    auto IncludeID = static_cast<IncludeStructure::HeaderID>(*MFI.HeaderID);
+    bool Used = ReferencedFiles.contains(IncludeID);
+    if (!Used && !mayConsiderUnused(MFI, AST, Cfg)) {
+      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, Used ? "USED" : "UNUSED");
+  }
+  return Unused;
+}
+
+void CachedIncludeCleaner::run() {
+  const SourceManager &SM = AST.getSourceManager();
+  include_cleaner::walkUsed(
+      AST.getLocalTopLevelDecls(), MacroReferences, AST.getPragmaIncludes(), SM,
+      [&](const include_cleaner::SymbolReference &Ref,
+          llvm::ArrayRef<include_cleaner::Header> Providers) {
+        assert(Refs.size() == ProviderRefs.size());
+        Refs.push_back(Ref);
+
+        llvm::SmallVector<include_cleaner::Header> SymbolProviders;
+        for (const include_cleaner::Header &H : Providers) {
+          SymbolProviders.push_back(H);
+        }
+        ProviderRefs.push_back(SymbolProviders);
+      });
+}
+
+std::vector<std::pair<std::string, unsigned>>
+CachedIncludeCleaner::computeMissingIncludes() {
+  if (Refs.empty()) {
+    run();
+  }
+  std::vector<Inclusion> MainFileIncludes =
+      AST.getIncludeStructure().MainFileIncludes;
+
+  include_cleaner::Includes IncludeCleanerIncludes =
+      convertIncludes(AST.getSourceManager(), MainFileIncludes);
+  std::string FileName =
+      SM.getFileEntryRefForID(AST.getSourceManager().getMainFileID())
+          ->getName()
+          .str();
+
+  std::vector<std::pair<std::string, unsigned>> Missing;
+  const FileEntry *MainFile = SM.getFileEntryForID(SM.getMainFileID());
+  for (unsigned I = 0; I < Refs.size(); ++I) {
+    include_cleaner::SymbolReference Ref = Refs[I];
+    llvm::SmallVector<include_cleaner::Header> Providers = ProviderRefs[I];
+    bool Satisfied = false;
+    for (const include_cleaner::Header &H : Providers) {
+      if (H.kind() == include_cleaner::Header::Physical &&
+          H.physical() == MainFile) {
+        Satisfied = true;
+      }
+      if (!IncludeCleanerIncludes.match(H).empty()) {
+        Satisfied = true;
+      }
+    }
+    if (!Satisfied && !Providers.empty() &&
+        Ref.RT == include_cleaner::RefType::Explicit) {
+      std::string SpelledHeader = include_cleaner::spellHeader(
+          Providers.front(), AST.getPreprocessor().getHeaderSearchInfo(),
+          MainFile);
+      std::pair<FileID, unsigned int> FileIDAndOffset =
+          AST.getSourceManager().getDecomposedLoc(Ref.RefLocation);
+      Missing.push_back({SpelledHeader, FileIDAndOffset.second});
+    }
+  }
+  return Missing;
+}
+
+// Compute unused #includes using the include-cleaner-lib-based
+// implementation.
+std::vector<const Inclusion *>
+CachedIncludeCleaner::computeUnusedIncludesExperimental() {
+  if (Refs.empty()) {
+    run();
+  }
+  const auto &Includes = AST.getIncludeStructure();
+  // 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));
+  }
+
+  llvm::DenseSet<IncludeStructure::HeaderID> Used;
+  for (unsigned I = 0; I < Refs.size(); ++I) {
+    llvm::SmallVector<include_cleaner::Header> Providers = ProviderRefs[I];
+    for (const include_cleaner::Header &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;
+      }
+    }
+  }
+  return getUnused(AST, Used, /*ReferencedPublicHeaders*/ {});
+}
+
+include_cleaner::Includes
+CachedIncludeCleaner::convertIncludes(const SourceManager &SM,
+                                      std::vector<Inclusion> MainFileIncludes) {
+  include_cleaner::Includes Includes;
+  for (const Inclusion &Inc : MainFileIncludes) {
+    llvm::ErrorOr<const FileEntry *> ResolvedOrError =
+        SM.getFileManager().getFile(Inc.Resolved);
+    const FileEntry *Resolved = nullptr;
+    if (bool(ResolvedOrError)) {
+      Resolved = ResolvedOrError.get();
+    }
+    SourceLocation HashLocation =
+        SM.getComposedLoc(SM.getMainFileID(), Inc.HashOffset);
+    llvm::StringRef WrittenRef = llvm::StringRef(Inc.Written);
+    bool Angled = WrittenRef.starts_with("<") ? true : false;
+    Includes.add(include_cleaner::Include{WrittenRef.trim("\"<>"), Resolved,
+                                          HashLocation, (unsigned)Inc.HashLine,
+                                          Angled});
+  }
+  return Includes;
+}
+
 namespace {
 
 /// Crawler traverses the AST and feeds in the locations of (sometimes
 /// implicitly) used symbols into \p Result.
 class ReferencedLocationCrawler
     : public RecursiveASTVisitor<ReferencedLocationCrawler> {
 public:
   ReferencedLocationCrawler(ReferencedLocations &Result,
if (!Macro)
       continue;
     auto Loc = Macro->Info->getDefinitionLoc();
     if (Loc.isValid())
       Result.User.insert(Loc);
     // FIXME: support stdlib macros
   }
 }
 
-static bool mayConsiderUnused(const Inclusion &Inc, ParsedAST &AST,
-                              const Config &Cfg) {
-  if (Inc.BehindPragmaKeep)
-    return false;
-
-  // FIXME(kirillbobyrev): We currently do not support the umbrella headers.
-  // System headers are likely to be standard library headers.
-  // Until we have good support for umbrella headers, don't warn about them.
-  if (Inc.Written.front() == '<') {
-    if (AnalyzeStdlib && tooling::stdlib::Header::named(Inc.Written))
-      return true;
-    return false;
-  }
-  assert(Inc.HeaderID);
-  auto HID = static_cast<IncludeStructure::HeaderID>(*Inc.HeaderID);
-  // FIXME: Ignore the headers with IWYU export pragmas for now, remove this
-  // check when we have more precise tracking of exported headers.
-  if (AST.getIncludeStructure().hasIWYUExport(HID))
-    return false;
-  auto FE = AST.getSourceManager().getFileManager().getFileRef(
-      AST.getIncludeStructure().getRealPath(HID));
-  assert(FE);
-  // Headers without include guards have side effects and are not
-  // self-contained, skip them.
-  if (!AST.getPreprocessor().getHeaderSearchInfo().isFileMultipleIncludeGuarded(
-          &FE->getFileEntry())) {
-    dlog("{0} doesn't have header guard and will not be considered unused",
-         FE->getName());
-    return false;
-  }
-  for (auto &Filter : Cfg.Diagnostics.Includes.IgnoreHeader) {
-    // Convert the path to Unix slashes and try to match against the filter.
-    llvm::SmallString<64> Path(Inc.Resolved);
-    llvm::sys::path::native(Path, llvm::sys::path::Style::posix);
-    if (Filter(Inc.Resolved)) {
-      dlog("{0} header is filtered out by the configuration", FE->getName());
-      return false;
-    }
-  }
-  return true;
-}
-
 // In case symbols are coming from non self-contained header, we need to find
 // its first includer that is self-contained. This is the header users can
 // include, so it will be responsible for bringing the symbols from given
 // header into the scope.
 FileID headerResponsible(FileID ID, const SourceManager &SM,
                          const IncludeStructure &Includes) {
   // Unroll the chain of non self-contained headers until we find the one that
   // can be included.
return findReferencedFiles(
           return std::nullopt;
         auto PublicHeader = CanonIncludes.mapHeader(*Entry);
         if (PublicHeader.empty())
           return std::nullopt;
         return PublicHeader;
       });
 }
 
-std::vector<const Inclusion *>
-getUnused(ParsedAST &AST,
-          const llvm::DenseSet<IncludeStructure::HeaderID> &ReferencedFiles,
-          const llvm::StringSet<> &ReferencedPublicHeaders) {
-  trace::Span Tracer("IncludeCleaner::getUnused");
-  const Config &Cfg = Config::current();
-  std::vector<const Inclusion *> Unused;
-  for (const Inclusion &MFI : AST.getIncludeStructure().MainFileIncludes) {
-    if (!MFI.HeaderID)
-      continue;
-    if (ReferencedPublicHeaders.contains(MFI.Written))
-      continue;
-    auto IncludeID = static_cast<IncludeStructure::HeaderID>(*MFI.HeaderID);
-    bool Used = ReferencedFiles.contains(IncludeID);
-    if (!Used && !mayConsiderUnused(MFI, AST, Cfg)) {
-      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, 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();
   return FI.getName().startswith("<");
 }
 #endif
 
for (FileID FID : Files.User) {
     TranslatedHeaderIDs.insert(*File);
   }
   for (tooling::stdlib::Header StdlibUsed : Files.Stdlib)
     for (auto HID : Includes.StdlibHeaders.lookup(StdlibUsed))
       TranslatedHeaderIDs.insert(HID);
   return TranslatedHeaderIDs;
 }
 
-std::vector<include_cleaner::SymbolReference>
-collectMacroReferences(ParsedAST &AST) {
-  const auto &SM = AST.getSourceManager();
-  //  FIXME: !!this is a hacky way to collect macro references.
-  std::vector<include_cleaner::SymbolReference> Macros;
-  auto &PP = AST.getPreprocessor();
-  for (const syntax::Token &Tok :
-       AST.getTokens().spelledTokens(SM.getMainFileID())) {
-    auto Macro = locateMacroAt(Tok, PP);
-    if (!Macro)
-      continue;
-    if (auto DefLoc = Macro->Info->getDefinitionLoc(); DefLoc.isValid())
-      Macros.push_back(
-          {Tok.location(),
-           include_cleaner::Macro{/*Name=*/PP.getIdentifierInfo(Tok.text(SM)),
-                                  DefLoc},
-           include_cleaner::RefType::Explicit});
-  }
-  return Macros;
-}
-
 // This is the original clangd-own implementation for computing unused
 // #includes. Eventually it will be deprecated and replaced by the
 // include-cleaner-lib-based implementation.
 std::vector<const Inclusion *> computeUnusedIncludes(ParsedAST &AST) {
   const auto &SM = AST.getSourceManager();
 
   auto Refs = findReferencedLocations(AST);
   auto ReferencedFiles =
       findReferencedFiles(Refs, AST.getIncludeStructure(),
                           AST.getCanonicalIncludes(), AST.getSourceManager());
   auto ReferencedHeaders =
       translateToHeaderIDs(ReferencedFiles, AST.getIncludeStructure(), SM);
   return getUnused(AST, ReferencedHeaders, ReferencedFiles.SpelledUmbrellas);
 }
 
-// Compute unused #includes using the include-cleaner-lib-based implementation.
-std::vector<const Inclusion *>
-computeUnusedIncludesExperimental(ParsedAST &AST) {
-  const auto &SM = AST.getSourceManager();
-  const auto &Includes = AST.getIncludeStructure();
-  // 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));
-  }
-
-  std::vector<include_cleaner::SymbolReference> Macros =
-      collectMacroReferences(AST);
-
-  llvm::DenseSet<IncludeStructure::HeaderID> Used;
-  include_cleaner::walkUsed(
-      AST.getLocalTopLevelDecls(), /*MacroRefs=*/Macros,
-      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;
-          }
-        }
-      });
-  return getUnused(AST, Used, /*ReferencedPublicHeaders*/ {});
-}
-
-include_cleaner::Includes
-convertIncludes(const SourceManager &SM,
-                std::vector<Inclusion> MainFileIncludes) {
-  include_cleaner::Includes Includes;
-  for (const Inclusion &Inc : MainFileIncludes) {
-    llvm::ErrorOr<const FileEntry *> ResolvedOrError =
-        SM.getFileManager().getFile(Inc.Resolved);
-    const FileEntry *Resolved = nullptr;
-    if (bool(ResolvedOrError)) {
-      Resolved = ResolvedOrError.get();
-    }
-    SourceLocation HashLocation =
-        SM.getComposedLoc(SM.getMainFileID(), Inc.HashOffset);
-    llvm::StringRef WrittenRef = llvm::StringRef(Inc.Written);
-    bool Angled = WrittenRef.starts_with("<") ? true : false;
-    Includes.add(include_cleaner::Include{WrittenRef.trim("\"<>"), Resolved,
-                                          HashLocation, (unsigned)Inc.HashLine,
-                                          Angled});
-  }
-  return Includes;
-}
-
-// Compute missing #includes. Uses the include-cleaner-lib-based implementation.
-std::vector<std::pair<std::string, unsigned>>
-computeMissingIncludes(ParsedAST &AST) {
-  std::vector<include_cleaner::SymbolReference> Macros =
-      collectMacroReferences(AST);
-  std::vector<Inclusion> MainFileIncludes =
-      AST.getIncludeStructure().MainFileIncludes;
-
-  include_cleaner::Includes IncludeCleanerIncludes =
-      convertIncludes(AST.getSourceManager(), MainFileIncludes);
-  std::string FileName =
-      AST.getSourceManager()
-          .getFileEntryRefForID(AST.getSourceManager().getMainFileID())
-          ->getName()
-          .str();
-  if (FileName.find("foo") != std::string::npos) {
-    vlog("Include cleaner includes: {0}", IncludeCleanerIncludes.all().size());
-  }
-
-  std::vector<std::pair<std::string, unsigned>> Missing;
-  SourceManager &SM = AST.getSourceManager();
-  const FileEntry *MainFile = SM.getFileEntryForID(SM.getMainFileID());
-  include_cleaner::walkUsed(
-      AST.getLocalTopLevelDecls(), Macros, AST.getPragmaIncludes(), SM,
-      [&](const include_cleaner::SymbolReference &Ref,
-          llvm::ArrayRef<include_cleaner::Header> Providers) {
-        bool Satisfied = false;
-        for (const include_cleaner::Header &H : Providers) {
-          if (H.kind() == include_cleaner::Header::Physical &&
-              H.physical() == MainFile) {
-            Satisfied = true;
-          }
-          if (!IncludeCleanerIncludes.match(H).empty()) {
-            Satisfied = true;
-          }
-        }
-        if (!Satisfied && !Providers.empty() &&
-            Ref.RT == include_cleaner::RefType::Explicit) {
-          std::string SpelledHeader = include_cleaner::spellHeader(
-              Providers.front(), AST.getPreprocessor().getHeaderSearchInfo(),
-              MainFile);
-          std::pair<FileID, unsigned int> FileIDAndOffset =
-              AST.getSourceManager().getDecomposedLoc(Ref.RefLocation);
-          Missing.push_back({SpelledHeader, FileIDAndOffset.second});
-        }
-      });
-  return Missing;
-}
-
-std::vector<Diag> issueMissingIncludesDiagnostics(ParsedAST &AST,
-                                                  llvm::StringRef Code) {
+std::vector<Diag>
+issueMissingIncludesDiagnostics(CachedIncludeCleaner &IncludeCleaner,
+                                ParsedAST &AST, llvm::StringRef Code) {
   const Config &Cfg = Config::current();
   if (Cfg.Diagnostics.MissingIncludes == Config::MissingIncludesPolicy::None ||
       Cfg.Diagnostics.SuppressAll ||
       Cfg.Diagnostics.Suppress.contains("missing-includes")) {
     return {};
   }
   // Interaction is only polished for C/CPP.
   if (AST.getLangOpts().ObjC)
     return {};
   trace::Span Tracer("IncludeCleaner::issueMissingIncludesDiagnostics");
   std::string FileName =
       AST.getSourceManager()
           .getFileEntryRefForID(AST.getSourceManager().getMainFileID())
           ->getName()
           .str();
 
   unsigned FixLine = 0;
   std::vector<Inclusion> MainFileIncludes =
       AST.getIncludeStructure().MainFileIncludes;
   if (!MainFileIncludes.empty())
     FixLine = MainFileIncludes[MainFileIncludes.size() - 1].HashLine + 1;
 
   std::vector<Diag> Result;
-  const auto &MissingIncludes = computeMissingIncludes(AST);
+  const auto &MissingIncludes = IncludeCleaner.computeMissingIncludes();
   for (const std::pair<std::string, unsigned> &Missing : MissingIncludes) {
     Diag D;
     D.Message = llvm::formatv("header {0} is missing", Missing.first);
     D.Name = "missing-includes";
     D.Source = Diag::DiagSource::Clangd;
     D.File = FileName;
     D.Severity = DiagnosticsEngine::Warning;
 
for (const std::pair<std::string, unsigned> &Missing : MissingIncludes) {
     D.Fixes.back().Edits.back().range.end.line = FixLine;
     D.InsideMainFile = true;
     Result.push_back(std::move(D));
   }
 
   return Result;
 }
 
-std::vector<Diag> issueUnusedIncludesDiagnostics(ParsedAST &AST,
-                                                 llvm::StringRef Code) {
+std::vector<Diag>
+issueUnusedIncludesDiagnostics(CachedIncludeCleaner &IncludeCleaner,
+                               ParsedAST &AST, llvm::StringRef Code) {
   const Config &Cfg = Config::current();
   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;
   std::string FileName =
       AST.getSourceManager()
           .getFileEntryRefForID(AST.getSourceManager().getMainFileID())
           ->getName()
           .str();
+
   const auto &UnusedIncludes =
       Cfg.Diagnostics.UnusedIncludes == Config::UnusedIncludesPolicy::Experiment
-          ? computeUnusedIncludesExperimental(AST)
+          ? IncludeCleaner.computeUnusedIncludesExperimental()
           : computeUnusedIncludes(AST);
   for (const auto *Inc : UnusedIncludes) {
     Diag D;
     D.Message =
         llvm::formatv("included header {0} is not used directly",
                       llvm::sys::path::filename(
                           Inc->Written.substr(1, Inc->Written.size() - 2),
                           llvm::sys::path::Style::posix));

clang-tools-extra/clangd/ParsedAST.h

private:
   // 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;
   std::unique_ptr<HeuristicResolver> Resolver;
 };
 
+std::vector<include_cleaner::SymbolReference>
+collectMacroReferences(ParsedAST &AST);
+
 } // namespace clangd
 } // namespace clang
 
 #endif // LLVM_CLANG_TOOLS_EXTRA_CLANGD_PARSEDAST_H

clang-tools-extra/clangd/ParsedAST.cpp

if (NeedsWerrorExclusion) {
       // downgrading diagnostics that were -Werror in the compile command.
       Diags.setDiagnosticGroupWarningAsError(Group, false);
     }
   }
 }
 
 } // namespace
 
+std::vector<include_cleaner::SymbolReference>
+collectMacroReferences(ParsedAST &AST) {
+  const auto &SM = AST.getSourceManager();
+  //  FIXME: !!this is a hacky way to collect macro references.
+  std::vector<include_cleaner::SymbolReference> Macros;
+  auto &PP = AST.getPreprocessor();
+  for (const syntax::Token &Tok :
+       AST.getTokens().spelledTokens(SM.getMainFileID())) {
+    auto Macro = locateMacroAt(Tok, PP);
+    if (!Macro)
+      continue;
+    if (auto DefLoc = Macro->Info->getDefinitionLoc(); DefLoc.isValid())
+      Macros.push_back(
+          {Tok.location(),
+           include_cleaner::Macro{/*Name=*/PP.getIdentifierInfo(Tok.text(SM)),
+                                  DefLoc},
+           include_cleaner::RefType::Explicit});
+  }
+  return Macros;
+}
+
 std::optional<ParsedAST>
 ParsedAST::build(llvm::StringRef Filename, const ParseInputs &Inputs,
                  std::unique_ptr<clang::CompilerInvocation> CI,
                  llvm::ArrayRef<Diag> CompilerInvocationDiags,
                  std::shared_ptr<const PreambleData> Preamble) {
   trace::Span Tracer("BuildAST");
   SPAN_ATTACH(Tracer, "File", Filename);
 
if (PreserveDiags) {
     }
   }
   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));
   if (Result.Diags) {
+    std::vector<include_cleaner::SymbolReference> MacroReferences = collectMacroReferences(Result); 
+    CachedIncludeCleaner IncludeCleaner(Result, MacroReferences);
     auto UnusedHeadersDiags =
-        issueUnusedIncludesDiagnostics(Result, Inputs.Contents);
+        issueUnusedIncludesDiagnostics(IncludeCleaner, Result, Inputs.Contents);
     auto MissingHeadersDiags =
-        issueMissingIncludesDiagnostics(Result, Inputs.Contents);
+        issueMissingIncludesDiagnostics(IncludeCleaner, Result, Inputs.Contents);
     Result.Diags->insert(Result.Diags->end(),
                          make_move_iterator(UnusedHeadersDiags.begin()),
                          make_move_iterator(UnusedHeadersDiags.end()));
     Result.Diags->insert(Result.Diags->end(),
                          make_move_iterator(MissingHeadersDiags.begin()),
                          make_move_iterator(MissingHeadersDiags.end()));
   }
   return std::move(Result);

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

TU.AdditionalFiles["bits"] = R"cpp(
     }
   )cpp";
   TU.AdditionalFiles["list"] = "#include <bits>";
   TU.AdditionalFiles["queue"] = "#include <bits>";
   TU.ExtraArgs = {"-isystem", testRoot()};
   auto AST = TU.build();
   EXPECT_THAT(computeUnusedIncludes(AST),
               ElementsAre(Pointee(writtenInclusion("<queue>"))));
-  EXPECT_THAT(computeUnusedIncludesExperimental(AST),
+  std::vector<include_cleaner::SymbolReference> MacroReferences = collectMacroReferences(AST); 
+  CachedIncludeCleaner IncludeCleaner(AST, MacroReferences);
+  EXPECT_THAT(IncludeCleaner.computeUnusedIncludesExperimental(),
               ElementsAre(Pointee(writtenInclusion("<queue>"))));
 }
 
 TEST(IncludeCleaner, GetUnusedHeaders) {
   llvm::StringLiteral MainFile = R"cpp(
     #include "a.h"
     #include "b.h"
     #include "dir/c.h"
TEST(IncludeCleaner, GetUnusedHeaders) {
   TU.ExtraArgs.push_back("-I" + testPath("dir"));
   TU.ExtraArgs.push_back("-isystem" + testPath("system"));
   TU.Code = MainFile.str();
   ParsedAST AST = TU.build();
   EXPECT_THAT(
       computeUnusedIncludes(AST),
       UnorderedElementsAre(Pointee(writtenInclusion("\"unused.h\"")),
                            Pointee(writtenInclusion("\"dir/unused.h\""))));
+  std::vector<include_cleaner::SymbolReference> MacroReferences = collectMacroReferences(AST); 
+  CachedIncludeCleaner IncludeCleaner(AST, MacroReferences);
   EXPECT_THAT(
-      computeUnusedIncludesExperimental(AST),
+      IncludeCleaner.computeUnusedIncludesExperimental(),
       UnorderedElementsAre(Pointee(writtenInclusion("\"unused.h\"")),
                            Pointee(writtenInclusion("\"dir/unused.h\""))));
 }
 
 TEST(IncludeCleaner, GetMissingHeaders) {
   llvm::StringLiteral MainFile = R"cpp(
     #include "a.h"
     #include "dir/c.h"
TEST(IncludeCleaner, GetMissingHeaders) {
 
   TU.AdditionalFiles["system/e.h"] = guard("#include <f.h>");
   TU.AdditionalFiles["system/f.h"] = guard("void f();");
   TU.ExtraArgs.push_back("-isystem" + testPath("system"));
 
   TU.Code = MainFile.str();
   ParsedAST AST = TU.build();
 
+  std::vector<include_cleaner::SymbolReference> MacroReferences = collectMacroReferences(AST); 
+  CachedIncludeCleaner IncludeCleaner(AST, MacroReferences);
   std::vector<std::pair<std::string, unsigned>> MissingIncludes =
-      computeMissingIncludes(AST);
+      IncludeCleaner.computeMissingIncludes();
 
   std::pair<std::string, unsigned> b{"\"b.h\"", 86};
   std::pair<std::string, unsigned> d{"\"dir/d.h\"", 97};
   std::pair<std::string, unsigned> h{"<f.h>", 108};
   EXPECT_THAT(MissingIncludes, UnorderedElementsAre(b, d, h));
 }
 
 TEST(IncludeCleaner, VirtualBuffers) {
TEST(IncludeCleaner, IWYUPragmas) {
   EXPECT_EQ(ReferencedFiles.SpelledUmbrellas.begin()->getKey(), "\"public.h\"");
   EXPECT_EQ(ReferencedFiles.User.size(), 2u);
   EXPECT_TRUE(
       ReferencedFiles.User.contains(AST.getSourceManager().getMainFileID()));
   EXPECT_TRUE(
       ReferencedFiles.User.contains(AST.getSourceManager().getMainFileID()));
   EXPECT_THAT(AST.getDiagnostics(), llvm::ValueIs(IsEmpty()));
   EXPECT_THAT(computeUnusedIncludes(AST), IsEmpty());
-  EXPECT_THAT(computeUnusedIncludesExperimental(AST), IsEmpty());
+
+  std::vector<include_cleaner::SymbolReference> MacroReferences = collectMacroReferences(AST); 
+  CachedIncludeCleaner IncludeCleaner(AST, MacroReferences);
+  EXPECT_THAT(IncludeCleaner.computeUnusedIncludesExperimental(), IsEmpty());
 }
 
 TEST(IncludeCleaner, RecursiveInclusion) {
   TestTU TU;
   TU.Code = R"cpp(
     #include "foo.h"
 
     void baz() {
TEST(IncludeCleaner, RecursiveInclusion) {
   )cpp";
   TU.AdditionalFiles["bar.h"] = guard(R"cpp(
     #include "foo.h"
   )cpp");
   ParsedAST AST = TU.build();
 
   EXPECT_THAT(AST.getDiagnostics(), llvm::ValueIs(IsEmpty()));
   EXPECT_THAT(computeUnusedIncludes(AST), IsEmpty());
-  EXPECT_THAT(computeUnusedIncludesExperimental(AST), IsEmpty());
+
+  std::vector<include_cleaner::SymbolReference> MacroReferences = clang::clangd::collectMacroReferences(AST); 
+  CachedIncludeCleaner IncludeCleaner(AST, MacroReferences);
+  EXPECT_THAT(IncludeCleaner.computeUnusedIncludesExperimental(), IsEmpty());
 }
 
 TEST(IncludeCleaner, IWYUPragmaExport) {
   TestTU TU;
   TU.Code = R"cpp(
     #include "foo.h"
     )cpp";
   TU.AdditionalFiles["foo.h"] = R"cpp(
     #ifndef FOO_H
     #define FOO_H
 
     #include "bar.h" // IWYU pragma: export
 
     #endif
   )cpp";
   TU.AdditionalFiles["bar.h"] = guard(R"cpp(
     void bar() {}
   )cpp");
   ParsedAST AST = TU.build();
 
   EXPECT_THAT(AST.getDiagnostics(), llvm::ValueIs(IsEmpty()));
   // FIXME: This is not correct: foo.h is unused but is not diagnosed as such
   // because we ignore headers with IWYU export pragmas for now.
   EXPECT_THAT(computeUnusedIncludes(AST), IsEmpty());
-  EXPECT_THAT(computeUnusedIncludesExperimental(AST), IsEmpty());
+  std::vector<include_cleaner::SymbolReference> MacroReferences = collectMacroReferences(AST); 
+  CachedIncludeCleaner IncludeCleaner(AST, MacroReferences);
+  EXPECT_THAT(IncludeCleaner.computeUnusedIncludesExperimental(), IsEmpty());
 }
 
 TEST(IncludeCleaner, NoDiagsForObjC) {
   TestTU TU;
   TU.Code = R"cpp(
     #include "foo.h"
 
     void bar() {}