[prototype] include-cleaner library

[sammccall]

Summary

See RFC
https://discourse.llvm.org/t/rfc-lifting-include-cleaner-missing-unused-include-detection-out-of-clangd/61228

This includes

• a prototype library for IWYU analysis (include-cleaner/{lib,include})
• a standalone tool (include-cleaner/tool)
• replacing clangd's unused-include warning with the library
• adding a new clangd hover interaction
• a clang-tidy unused-include check

This squashes together quite a few patches worth of scope, has no tests, and
designs are half baked. Still it demonstrates that such a library could be
reused across tools & across unused vs missing warnings.

Some significant things that are missing:

• IWYU pragma support and other non-self-contained-header patterns
• ability to sensibly rank suggested includes. (Probably requires a design change to preserve the Node->Symbol->Location->Header DAG)
• better standard library support (macros)
• general accuracy
• missing-include integration for clang-tidy and clangd (mechanical really)

[sammccall]

oops, remove "include is used" diagnostic from clang-tidy!

[sammccall]

doc and clean up

[sammccall]

Add "hints", used for ranking candidates for suggestions.

Not totally happy with this design:

• its intrusive to a bunch of the types
• computing/sorting these eagerly seems wasteful when they're rarely needed

However it is nice to be able to share the code easily.

[serge-sans-paille]

Hey Sam, any update on this one? How can I help?

[kadircet]

hi Serge, sorry for the silence here. we'll be moving this towards a production ready version over the next months (also releasing some comments i've forgotten to send, we've already discussed these offline so no need for action).
we'll probably be leaving some todos/fixmes as we go, if you want to help it'd be great to keep an eye on changes going into the clang-tools-extra/include-cleaner directory (i'll also try to add you as a subscriber to them) and mention things you'd be interested in picking up.

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

61

i guess one annyoing thing we're missing here is communication of IWYU export / keep like pragmas. It feels like handling of such will now be distributed across all users, which feels unfortunate.
maybe we can address that by either completely deleting such headers from RecordedPP->Includes.all or having some helper like shouldKeep in RecordedPP->Includes (similar to match).

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

51

i think we might want to have some pointers to AnalysisContext owning these DefinedMacros, it's pretty surprising for the user otherwise.

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

38

feels like we might need some language-based hints here. like stdio.h is C-like.

for the multiple header cases, i suppose it's fine to put them in an order that we think is "common", while still providing the others. so that unused includes usecase won't annoy folks and missing includes can provide sane defaults.

i am not sure if we care much about "guaranteed umbrella headers" case. but in such a scenario, i guess we'd want a policy, that way missing includes can be suppressed but unused includes can still fire (basically a flip that returns only the specific header vs both specific and umbrella header).

[PiotrZSL]

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

62

Missing tests & documentation for this check.

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

39

why not just:

Finder->addMatcher(decl(isExpansionInMainFile()).bind("top"))

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

36

There are going to be manny reallocations of this std::vector, we got manny declarations, consider using std::deque.

clang-tools-extra/CMakeLists.txt

 include(CMakeDependentOption)
 include(GNUInstallDirs)
 
 option(CLANG_TIDY_ENABLE_STATIC_ANALYZER
   "Include static analyzer checks in clang-tidy" ON)
 
 add_subdirectory(clang-apply-replacements)
 add_subdirectory(clang-reorder-fields)
 add_subdirectory(modularize)
 add_subdirectory(clang-tidy)
 
 add_subdirectory(clang-change-namespace)
 add_subdirectory(clang-doc)
 add_subdirectory(clang-include-fixer)
 add_subdirectory(clang-move)
 add_subdirectory(clang-query)
+add_subdirectory(include-cleaner)
 add_subdirectory(pp-trace)
 add_subdirectory(pseudo)
 add_subdirectory(tool-template)
 
 # Add the common testsuite after all the tools.
 if(CLANG_INCLUDE_TESTS)
 add_subdirectory(test)
 add_subdirectory(unittests)

clang-tools-extra/clang-tidy/misc/CMakeLists.txt

+include_directories(${CMAKE_CURRENT_SOURCE_DIR}/../../include-cleaner/include)
+
 set(LLVM_LINK_COMPONENTS
   FrontendOpenMP
   Support
   )
 
 add_clang_library(clangTidyMiscModule
   DefinitionsInHeadersCheck.cpp
   MiscTidyModule.cpp
   MisleadingBidirectional.cpp
   MisleadingIdentifier.cpp
   MisplacedConstCheck.cpp
   NewDeleteOverloadsCheck.cpp
   NoRecursionCheck.cpp
   NonCopyableObjects.cpp
   NonPrivateMemberVariablesInClassesCheck.cpp
   RedundantExpressionCheck.cpp
   StaticAssertCheck.cpp
   ThrowByValueCatchByReferenceCheck.cpp
   UnconventionalAssignOperatorCheck.cpp
   UniqueptrResetReleaseCheck.cpp
   UnusedAliasDeclsCheck.cpp
+  UnusedIncludesCheck.cpp
   UnusedParametersCheck.cpp
   UnusedUsingDeclsCheck.cpp
 
   LINK_LIBS
   clangTidy
   clangTidyUtils
 
   DEPENDS
   omp_gen
   )
 
 clang_target_link_libraries(clangTidyMiscModule
   PRIVATE
   clangAnalysis
   clangAST
   clangASTMatchers
   clangBasic
+  clangIncludeCleaner
   clangLex
   clangSerialization
   clangTooling
   )

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

 #include "NonCopyableObjects.h"
 #include "NonPrivateMemberVariablesInClassesCheck.h"
 #include "RedundantExpressionCheck.h"
 #include "StaticAssertCheck.h"
 #include "ThrowByValueCatchByReferenceCheck.h"
 #include "UnconventionalAssignOperatorCheck.h"
 #include "UniqueptrResetReleaseCheck.h"
 #include "UnusedAliasDeclsCheck.h"
+#include "UnusedIncludesCheck.h"
 #include "UnusedParametersCheck.h"
 #include "UnusedUsingDeclsCheck.h"
 
 namespace clang {
 namespace tidy {
 namespace misc {
 
 class MiscModule : public ClangTidyModule {
void addCheckFactories(ClangTidyCheckFactories &CheckFactories) override {
     CheckFactories.registerCheck<ThrowByValueCatchByReferenceCheck>(
         "misc-throw-by-value-catch-by-reference");
     CheckFactories.registerCheck<UnconventionalAssignOperatorCheck>(
         "misc-unconventional-assign-operator");
     CheckFactories.registerCheck<UniqueptrResetReleaseCheck>(
         "misc-uniqueptr-reset-release");
     CheckFactories.registerCheck<UnusedAliasDeclsCheck>(
         "misc-unused-alias-decls");
+    CheckFactories.registerCheck<UnusedIncludesCheck>("misc-unused-includes");
     CheckFactories.registerCheck<UnusedParametersCheck>(
         "misc-unused-parameters");
     CheckFactories.registerCheck<UnusedUsingDeclsCheck>(
         "misc-unused-using-decls");
   }
 };
 
 } // namespace misc

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

+//===--- UnusedIncludesCheck.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_UNUSED_INCLUDES_H
+#define LLVM_CLANG_TOOLS_EXTRA_CLANG_TIDY_MISC_UNUSED_INCLUDES_H
+
+#include "../ClangTidyCheck.h"
+
+namespace clang {
+namespace include_cleaner {
+class AnalysisContext;
+struct RecordedPP;
+} // namespace include_cleaner
+namespace tidy {
+namespace misc {
+
+class UnusedIncludesCheck : public ClangTidyCheck {
+public:
+  UnusedIncludesCheck(StringRef Name, ClangTidyContext *Context);
+  ~UnusedIncludesCheck();
+  void registerPPCallbacks(const SourceManager &SM, Preprocessor *,
+                           Preprocessor *) override;
+  void registerMatchers(ast_matchers::MatchFinder *Finder) override;
+  void check(const ast_matchers::MatchFinder::MatchResult &Result) override;
+  void onEndOfTranslationUnit() override;
+
+private:
+  std::unique_ptr<include_cleaner::AnalysisContext> Ctx;
+  std::unique_ptr<include_cleaner::RecordedPP> RecordedPP;
+  std::vector<Decl *> Top;
+};
+
+} // namespace misc
+} // namespace tidy
+} // namespace clang
+
+#endif // LLVM_CLANG_TOOLS_EXTRA_CLANG_TIDY_MISC_UNUSED_INCLUDES_H

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

+//===--- UnusedIncludesCheck.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 "UnusedIncludesCheck.h"
+#include "clang-include-cleaner/Analysis.h"
+#include "clang-include-cleaner/Hooks.h"
+#include "clang/Basic/Diagnostic.h"
+#include "clang/Basic/LLVM.h"
+#include "clang/Basic/SourceLocation.h"
+#include "clang/Lex/Preprocessor.h"
+
+using namespace clang::ast_matchers;
+
+namespace clang {
+namespace tidy {
+namespace misc {
+
+UnusedIncludesCheck::UnusedIncludesCheck(StringRef Name,
+                                         ClangTidyContext *Context)
+    : ClangTidyCheck(Name, Context) {}
+
+void UnusedIncludesCheck::registerPPCallbacks(const SourceManager &SM,
+                                              Preprocessor *PP,
+                                              Preprocessor *) {
+  Ctx = std::make_unique<include_cleaner::AnalysisContext>(
+      include_cleaner::Policy{}, *PP);
+  RecordedPP = std::make_unique<include_cleaner::RecordedPP>();
+  PP->addPPCallbacks(RecordedPP->record(*Ctx));
+}
+
+void UnusedIncludesCheck::registerMatchers(MatchFinder *Finder) {
+  Finder->addMatcher(
+      translationUnitDecl(forEach(decl(isExpansionInMainFile()).bind("top"))),
+      this);
+}
+
+void UnusedIncludesCheck::check(const MatchFinder::MatchResult &Result) {
+  Top.push_back(const_cast<Decl *>(Result.Nodes.getNodeAs<Decl>("top")));
+}
+
+void UnusedIncludesCheck::onEndOfTranslationUnit() {
+  llvm::DenseSet<const include_cleaner::RecordedPP::Include *> Used;
+  llvm::DenseSet<include_cleaner::Header> Seen;
+  include_cleaner::walkUsed(
+      *Ctx, Top, RecordedPP->MacroReferences,
+      [&](SourceLocation Loc, include_cleaner::Symbol Sym,
+          llvm::ArrayRef<include_cleaner::Header> Headers) {
+        for (const auto &Header : Headers) {
+          if (!Seen.insert(Header).second)
+            continue;
+          for (const auto *I : RecordedPP->Includes.match(Header))
+            Used.insert(I);
+        }
+      });
+  for (const auto &I : RecordedPP->Includes.all()) {
+    if (!Used.contains(&I)) {
+      const auto &SM = Ctx->sourceManager();
+      FileID FID = SM.getFileID(I.Location);
+      diag(I.Location, "include is unused")
+          << FixItHint::CreateRemoval(CharSourceRange::getCharRange(
+                 SM.translateLineCol(FID, I.Line, 1),
+                 SM.translateLineCol(FID, I.Line + 1, 1)));
+    } else {
+      diag(I.Location, "include is used!");
+    }
+  }
+}
+
+UnusedIncludesCheck::~UnusedIncludesCheck() = default;
+
+} // namespace misc
+} // namespace tidy
+} // namespace clang

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
   clangToolingSyntax

clang-tools-extra/clangd/Hover.cpp

 //===--- Hover.cpp - Information about code at the cursor location --------===//
 //
 // 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 "Hover.h"
 
 #include "AST.h"
 #include "CodeCompletionStrings.h"
 #include "Config.h"
 #include "FindTarget.h"
+#include "IncludeCleaner.h"
 #include "ParsedAST.h"
 #include "Selection.h"
 #include "SourceCode.h"
+#include "clang-include-cleaner/Analysis.h"
 #include "index/SymbolCollector.h"
 #include "support/Markup.h"
 #include "clang/AST/ASTContext.h"
 #include "clang/AST/ASTDiagnostic.h"
 #include "clang/AST/ASTTypeTraits.h"
 #include "clang/AST/Attr.h"
 #include "clang/AST/Decl.h"
 #include "clang/AST/DeclBase.h"
if (const auto MainFilePath =
     for (const auto &Inc : AST.getIncludeStructure().MainFileIncludes) {
       if (Inc.Resolved.empty() || Inc.HashLine != Pos.line)
         continue;
       HoverInfo HI;
       HI.Name = std::string(llvm::sys::path::filename(Inc.Resolved));
       // FIXME: We don't have a fitting value for Kind.
       HI.Definition =
           URIForFile::canonicalize(Inc.Resolved, *MainFilePath).file().str();
+
+      // FIXME: share code, macros too...
+      include_cleaner::AnalysisContext Ctx(include_cleaner::Policy{},
+                                           AST.getPreprocessor());
+      std::vector<std::string> Provides;
+      include_cleaner::walkUsed(
+          Ctx, AST.getLocalTopLevelDecls(), /*Macros=*/{},
+          [&](SourceLocation Loc, include_cleaner::Symbol S,
+              llvm::ArrayRef<include_cleaner::Header> Headers) {
+            for (const auto &H : Headers)
+              if (match(H, Inc, AST.getIncludeStructure()))
+                Provides.push_back(S.name());
+          });
+      llvm::sort(Provides);
+      Provides.erase(std::unique(Provides.begin(), Provides.end()),
+                     Provides.end());
+      HI.Documentation = "provides " + llvm::join(Provides, ", ");
       HI.DefinitionLanguage = "";
       return HI;
     }
   }
 
   // To be used as a backup for highlighting the selected token, we use back as
   // it aligns better with biases elsewhere (editors tend to send the position
   // for the left of the hovered token).

clang-tools-extra/clangd/IncludeCleaner.h

 ///
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_CLANG_TOOLS_EXTRA_CLANGD_INCLUDECLEANER_H
 #define LLVM_CLANG_TOOLS_EXTRA_CLANGD_INCLUDECLEANER_H
 
 #include "Headers.h"
 #include "ParsedAST.h"
-#include "clang/Basic/SourceLocation.h"
-#include "clang/Tooling/Inclusions/StandardLibrary.h"
+#include "clang-include-cleaner/Types.h"
 #include "llvm/ADT/DenseSet.h"
-#include "llvm/ADT/STLFunctionalExtras.h"
 #include <vector>
 
 namespace clang {
 namespace clangd {
 
-struct ReferencedLocations {
-  llvm::DenseSet<SourceLocation> User;
-  llvm::DenseSet<tooling::stdlib::Symbol> Stdlib;
-};
-
-/// 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.
-/// We use this to compute unused headers, so we:
-///
-/// - cover the whole file in a single traversal for efficiency
-/// - don't attempt to describe where symbols were referenced from in
-///   ambiguous cases (e.g. implicitly used symbols, multiple declarations)
-/// - err on the side of reporting all possible locations
-ReferencedLocations findReferencedLocations(ASTContext &Ctx, Preprocessor &PP,
-                                            const syntax::TokenBuffer *Tokens);
-ReferencedLocations findReferencedLocations(ParsedAST &AST);
-
-struct ReferencedFiles {
-  llvm::DenseSet<FileID> User;
-  llvm::DenseSet<tooling::stdlib::Header> Stdlib;
-};
-
-/// Retrieves IDs of all files containing SourceLocations from \p Locs.
-/// The output only includes things SourceManager sees as files (not macro IDs).
-/// This can include <built-in>, <scratch space> etc that are not true files.
-/// \p HeaderResponsible returns the public header that should be included given
-/// symbols from a file with the given FileID (example: public headers should be
-/// preferred to non self-contained and private headers).
-ReferencedFiles
-findReferencedFiles(const ReferencedLocations &Locs, const SourceManager &SM,
-                    llvm::function_ref<FileID(FileID)> HeaderResponsible);
-ReferencedFiles findReferencedFiles(const ReferencedLocations &Locs,
-                                    const IncludeStructure &Includes,
-                                    const SourceManager &SM);
-
-/// Maps FileIDs to the internal IncludeStructure representation (HeaderIDs).
-/// FileIDs that are not true files (<built-in> etc) are dropped.
-llvm::DenseSet<IncludeStructure::HeaderID>
-translateToHeaderIDs(const ReferencedFiles &Files,
-                     const IncludeStructure &Includes, const SourceManager &SM);
-
 /// Retrieves headers that are referenced from the main file but not used.
 /// In unclear cases, headers are not marked as unused.
 std::vector<const Inclusion *>
 getUnused(ParsedAST &AST,
           const llvm::DenseSet<IncludeStructure::HeaderID> &ReferencedFiles);
 
 std::vector<const Inclusion *> computeUnusedIncludes(ParsedAST &AST);
 
 std::vector<Diag> issueUnusedIncludesDiagnostics(ParsedAST &AST,
                                                  llvm::StringRef Code);
 
+// Does an include-cleaner header spec match a clangd recorded inclusion?
+bool match(const include_cleaner::Header &H, const Inclusion &I,
+           const IncludeStructure &S);
+
 /// 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

 //===--- 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 "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"
 #include "clang/Lex/HeaderSearch.h"
 #include "clang/Lex/Preprocessor.h"
 #include "clang/Tooling/Syntax/Tokens.h"
 #include "llvm/ADT/STLFunctionalExtras.h"
 #include "llvm/Support/FormatVariadic.h"
 #include "llvm/Support/Path.h"
 
 namespace clang {
 namespace clangd {
 
 static bool AnalyzeStdlib = false;
 void setIncludeCleanerAnalyzesStdlib(bool B) { AnalyzeStdlib = B; }
 
 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,
-                            const SourceManager &SM)
-      : Result(Result), SM(SM) {}
-
-  bool VisitDeclRefExpr(DeclRefExpr *DRE) {
-    add(DRE->getDecl());
-    add(DRE->getFoundDecl());
-    return true;
-  }
-
-  bool VisitMemberExpr(MemberExpr *ME) {
-    add(ME->getMemberDecl());
-    add(ME->getFoundDecl().getDecl());
-    return true;
-  }
-
-  bool VisitTagType(TagType *TT) {
-    add(TT->getDecl());
-    return true;
-  }
-
-  bool VisitFunctionDecl(FunctionDecl *FD) {
-    // Function definition will require redeclarations to be included.
-    if (FD->isThisDeclarationADefinition())
-      add(FD);
-    return true;
-  }
-
-  bool VisitCXXConstructExpr(CXXConstructExpr *CCE) {
-    add(CCE->getConstructor());
-    return true;
-  }
-
-  bool VisitTemplateSpecializationType(TemplateSpecializationType *TST) {
-    add(TST->getTemplateName().getAsTemplateDecl()); // Primary template.
-    add(TST->getAsCXXRecordDecl());                  // Specialization
-    return true;
-  }
-
-  bool VisitUsingType(UsingType *UT) {
-    add(UT->getFoundDecl());
-    return true;
-  }
-
-  bool VisitTypedefType(TypedefType *TT) {
-    add(TT->getDecl());
-    return true;
-  }
-
-  // Consider types of any subexpression used, even if the type is not named.
-  // This is helpful in getFoo().bar(), where Foo must be complete.
-  // FIXME(kirillbobyrev): Should we tweak this? It may not be desirable to
-  // consider types "used" when they are not directly spelled in code.
-  bool VisitExpr(Expr *E) {
-    TraverseType(E->getType());
-    return true;
-  }
-
-  bool TraverseType(QualType T) {
-    if (isNew(T.getTypePtrOrNull())) // don't care about quals
-      Base::TraverseType(T);
-    return true;
-  }
-
-  bool VisitUsingDecl(UsingDecl *D) {
-    for (const auto *Shadow : D->shadows())
-      add(Shadow->getTargetDecl());
-    return true;
-  }
-
-  // Enums may be usefully forward-declared as *complete* types by specifying
-  // an underlying type. In this case, the definition should see the declaration
-  // so they can be checked for compatibility.
-  bool VisitEnumDecl(EnumDecl *D) {
-    if (D->isThisDeclarationADefinition() && D->getIntegerTypeSourceInfo())
-      add(D);
-    return true;
-  }
-
-  // When the overload is not resolved yet, mark all candidates as used.
-  bool VisitOverloadExpr(OverloadExpr *E) {
-    for (const auto *ResolutionDecl : E->decls())
-      add(ResolutionDecl);
-    return true;
-  }
-
-private:
-  using Base = RecursiveASTVisitor<ReferencedLocationCrawler>;
-
-  void add(const Decl *D) {
-    if (!D || !isNew(D->getCanonicalDecl()))
-      return;
-    if (auto SS = StdRecognizer(D)) {
-      Result.Stdlib.insert(*SS);
-      return;
-    }
-    // Special case RecordDecls, as it is common for them to be forward
-    // declared multiple times. The most common cases are:
-    // - Definition available in TU, only mark that one as usage. The rest is
-    //   likely to be unnecessary. This might result in false positives when an
-    //   internal definition is visible.
-    // - There's a forward declaration in the main file, no need for other
-    //   redecls.
-    if (const auto *RD = llvm::dyn_cast<RecordDecl>(D)) {
-      if (const auto *Definition = RD->getDefinition()) {
-        Result.User.insert(Definition->getLocation());
-        return;
-      }
-      if (SM.isInMainFile(RD->getMostRecentDecl()->getLocation()))
-        return;
-    }
-    for (const Decl *Redecl : D->redecls())
-      Result.User.insert(Redecl->getLocation());
-  }
-
-  bool isNew(const void *P) { return P && Visited.insert(P).second; }
-
-  ReferencedLocations &Result;
-  llvm::DenseSet<const void *> Visited;
-  const SourceManager &SM;
-  tooling::stdlib::Recognizer StdRecognizer;
-};
-
-// Given a set of referenced FileIDs, determines all the potentially-referenced
-// files and macros by traversing expansion/spelling locations of macro IDs.
-// This is used to map the referenced SourceLocations onto real files.
-struct ReferencedFilesBuilder {
-  ReferencedFilesBuilder(const SourceManager &SM) : SM(SM) {}
-  llvm::DenseSet<FileID> Files;
-  llvm::DenseSet<FileID> Macros;
-  const SourceManager &SM;
-
-  void add(SourceLocation Loc) { add(SM.getFileID(Loc), Loc); }
-
-  void add(FileID FID, SourceLocation Loc) {
-    if (FID.isInvalid())
-      return;
-    assert(SM.isInFileID(Loc, FID));
-    if (Loc.isFileID()) {
-      Files.insert(FID);
-      return;
-    }
-    // Don't process the same macro FID twice.
-    if (!Macros.insert(FID).second)
-      return;
-    const auto &Exp = SM.getSLocEntry(FID).getExpansion();
-    add(Exp.getSpellingLoc());
-    add(Exp.getExpansionLocStart());
-    add(Exp.getExpansionLocEnd());
-  }
-};
-
 // Returns the range starting at '#' and ending at EOL. Escaped newlines are not
 // handled.
 clangd::Range getDiagnosticRange(llvm::StringRef Code, unsigned HashOffset) {
   clangd::Range Result;
   Result.end = Result.start = offsetToPosition(Code, HashOffset);
 
   // Span the warning until the EOL or EOF.
   Result.end.character +=
       lspLength(Code.drop_front(HashOffset).take_until([](char C) {
         return C == '\n' || C == '\r';
       }));
   return Result;
 }
 
 // Finds locations of macros referenced from within the main file. That includes
 // references that were not yet expanded, e.g `BAR` in `#define FOO BAR`.
-void findReferencedMacros(const SourceManager &SM, Preprocessor &PP,
-                          const syntax::TokenBuffer *Tokens,
-                          ReferencedLocations &Result) {
+std::vector<include_cleaner::SymbolReference>
+findReferencedMacros(ParsedAST &AST, include_cleaner::AnalysisContext &Ctx) {
   trace::Span Tracer("IncludeCleaner::findReferencedMacros");
+  std::vector<include_cleaner::SymbolReference> Result;
   // FIXME(kirillbobyrev): The macros from the main file are collected in
   // ParsedAST's MainFileMacros. However, we can't use it here because it
   // doesn't handle macro references that were not expanded, e.g. in macro
   // definitions or preprocessor-disabled sections.
   //
   // Extending MainFileMacros to collect missing references and switching to
   // this mechanism (as opposed to iterating through all tokens) will improve
   // the performance of findReferencedMacros and also improve other features
   // relying on MainFileMacros.
-  for (const syntax::Token &Tok : Tokens->spelledTokens(SM.getMainFileID())) {
-    auto Macro = locateMacroAt(Tok, PP);
+  for (const syntax::Token &Tok :
+       AST.getTokens().spelledTokens(AST.getSourceManager().getMainFileID())) {
+    auto Macro = locateMacroAt(Tok, AST.getPreprocessor());
     if (!Macro)
       continue;
     auto Loc = Macro->Info->getDefinitionLoc();
     if (Loc.isValid())
-      Result.User.insert(Loc);
-    // FIXME: support stdlib macros
+      Result.push_back(include_cleaner::SymbolReference{
+          Tok.location(),
+          Ctx.macro(AST.getPreprocessor().getIdentifierInfo(Macro->Name),
+                    Loc)});
   }
+  return Result;
 }
 
 static bool mayConsiderUnused(const Inclusion &Inc, ParsedAST &AST) {
   if (Inc.BehindPragmaKeep)
     return false;
 
   // FIXME(kirillbobyrev): We currently do not support the umbrella headers.
   // System headers are likely to be standard library headers.
if (!AST.getPreprocessor().getHeaderSearchInfo().isFileMultipleIncludeGuarded(
           *FE)) {
     dlog("{0} doesn't have header guard and will not be considered unused",
          (*FE)->getName());
     return false;
   }
   return true;
 }
 
-// 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.
-  for (const FileEntry *FE = SM.getFileEntryForID(ID); ID != SM.getMainFileID();
-       FE = SM.getFileEntryForID(ID)) {
-    // If FE is nullptr, we consider it to be the responsible header.
-    if (!FE)
-      break;
-    auto HID = Includes.getID(FE);
-    assert(HID && "We're iterating over headers already existing in "
-                  "IncludeStructure");
-    if (Includes.isSelfContained(*HID))
-      break;
-    // The header is not self-contained: put the responsibility for its symbols
-    // on its includer.
-    ID = SM.getFileID(SM.getIncludeLoc(ID));
-  }
-  return ID;
-}
-
 } // namespace
 
-ReferencedLocations findReferencedLocations(ASTContext &Ctx, Preprocessor &PP,
-                                            const syntax::TokenBuffer *Tokens) {
-  trace::Span Tracer("IncludeCleaner::findReferencedLocations");
-  ReferencedLocations Result;
-  const auto &SM = Ctx.getSourceManager();
-  ReferencedLocationCrawler Crawler(Result, SM);
-  Crawler.TraverseAST(Ctx);
-  if (Tokens)
-    findReferencedMacros(SM, PP, Tokens, Result);
-  return Result;
-}
-
-ReferencedLocations findReferencedLocations(ParsedAST &AST) {
-  return findReferencedLocations(AST.getASTContext(), AST.getPreprocessor(),
-                                 &AST.getTokens());
-}
-
-ReferencedFiles
-findReferencedFiles(const ReferencedLocations &Locs, const SourceManager &SM,
-                    llvm::function_ref<FileID(FileID)> HeaderResponsible) {
-  std::vector<SourceLocation> Sorted{Locs.User.begin(), Locs.User.end()};
-  llvm::sort(Sorted); // Group by FileID.
-  ReferencedFilesBuilder Builder(SM);
-  for (auto It = Sorted.begin(); It < Sorted.end();) {
-    FileID FID = SM.getFileID(*It);
-    Builder.add(FID, *It);
-    // Cheaply skip over all the other locations from the same FileID.
-    // This avoids lots of redundant Loc->File lookups for the same file.
-    do
-      ++It;
-    while (It != Sorted.end() && SM.isInFileID(*It, FID));
-  }
-
-  // If a header is not self-contained, we consider its symbols a logical part
-  // of the including file. Therefore, mark the parents of all used
-  // non-self-contained FileIDs as used. Perform this on FileIDs rather than
-  // HeaderIDs, as each inclusion of a non-self-contained file is distinct.
-  llvm::DenseSet<FileID> UserFiles;
-  for (FileID ID : Builder.Files)
-    UserFiles.insert(HeaderResponsible(ID));
-
-  llvm::DenseSet<tooling::stdlib::Header> StdlibFiles;
-  for (const auto &Symbol : Locs.Stdlib)
-    for (const auto &Header : Symbol.headers())
-      StdlibFiles.insert(Header);
-
-  return {std::move(UserFiles), std::move(StdlibFiles)};
-}
-
-ReferencedFiles findReferencedFiles(const ReferencedLocations &Locs,
-                                    const IncludeStructure &Includes,
-                                    const SourceManager &SM) {
-  return findReferencedFiles(Locs, SM, [&SM, &Includes](FileID ID) {
-    return headerResponsible(ID, SM, Includes);
-  });
-}
-
 std::vector<const Inclusion *>
 getUnused(ParsedAST &AST,
           const llvm::DenseSet<IncludeStructure::HeaderID> &ReferencedFiles) {
   trace::Span Tracer("IncludeCleaner::getUnused");
   std::vector<const Inclusion *> Unused;
   for (const Inclusion &MFI : AST.getIncludeStructure().MainFileIncludes) {
     if (!MFI.HeaderID)
       continue;
     auto IncludeID = static_cast<IncludeStructure::HeaderID>(*MFI.HeaderID);
     bool Used = ReferencedFiles.contains(IncludeID);
     if (!Used && !mayConsiderUnused(MFI, AST)) {
       dlog("{0} was not used, but is not eligible to be diagnosed as unused",
            MFI.Written);
       continue;
     }
     if (!Used)
       Unused.push_back(&MFI);
     dlog("{0} is {1}", MFI.Written, 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
-
-llvm::DenseSet<IncludeStructure::HeaderID>
-translateToHeaderIDs(const ReferencedFiles &Files,
-                     const IncludeStructure &Includes,
-                     const SourceManager &SM) {
-  trace::Span Tracer("IncludeCleaner::translateToHeaderIDs");
-  llvm::DenseSet<IncludeStructure::HeaderID> TranslatedHeaderIDs;
-  TranslatedHeaderIDs.reserve(Files.User.size());
-  for (FileID FID : Files.User) {
-    const FileEntry *FE = SM.getFileEntryForID(FID);
-    if (!FE) {
-      assert(isSpecialBuffer(FID, SM));
-      continue;
-    }
-    const auto File = Includes.getID(FE);
-    assert(File);
-    TranslatedHeaderIDs.insert(*File);
-  }
-  for (tooling::stdlib::Header StdlibUsed : Files.Stdlib)
-    for (auto HID : Includes.StdlibHeaders.lookup(StdlibUsed))
-      TranslatedHeaderIDs.insert(HID);
-  return TranslatedHeaderIDs;
+bool match(const include_cleaner::Header &H, const Inclusion &I,
+           const IncludeStructure &S) {
+  switch (H.kind()) {
+  case include_cleaner::Header::Physical:
+    if (auto HID = S.getID(H.getPhysical()))
+      if (static_cast<unsigned>(*HID) == I.HeaderID)
+        return true;
+    break;
+  case include_cleaner::Header::StandardLibrary:
+    return I.Written == H.getStandardLibrary().name();
+  case include_cleaner::Header::Verbatim:
+    return llvm::StringRef(I.Written).trim("\"<>") == H.getVerbatimSpelling();
+  case include_cleaner::Header::Builtin:
+  case include_cleaner::Header::MainFile:
+    break;
+  return false;
 }
 
 std::vector<const Inclusion *> computeUnusedIncludes(ParsedAST &AST) {
-  const auto &SM = AST.getSourceManager();
-
-  auto Refs = findReferencedLocations(AST);
-  auto ReferencedFileIDs = findReferencedFiles(Refs, AST.getIncludeStructure(),
-                                               AST.getSourceManager());
-  auto ReferencedHeaders =
-      translateToHeaderIDs(ReferencedFileIDs, AST.getIncludeStructure(), SM);
-  return getUnused(AST, ReferencedHeaders);
+  include_cleaner::AnalysisContext Ctx(include_cleaner::Policy{},
+                                       AST.getPreprocessor());
+  llvm::DenseSet<const Inclusion *> Used;
+  include_cleaner::walkUsed(
+      Ctx, AST.getLocalTopLevelDecls(),
+      /*MacroRefs=*/findReferencedMacros(AST, Ctx),
+      [&](SourceLocation Loc, include_cleaner::Symbol Sym,
+          llvm::ArrayRef<include_cleaner::Header> Headers) {
+        for (const auto &I : AST.getIncludeStructure().MainFileIncludes)
+          for (const auto &H : Headers)
+            if (match(H, I, AST.getIncludeStructure()))
+              Used.insert(&I);
+      });
+  std::vector<const Inclusion *> Unused;
+  for (const auto &I : AST.getIncludeStructure().MainFileIncludes) {
+    if (!Used.contains(&I) && mayConsiderUnused(I, AST))
+      Unused.push_back(&I);
+  }
+  return Unused;
 }
 
 std::vector<Diag> issueUnusedIncludesDiagnostics(ParsedAST &AST,
                                                  llvm::StringRef Code) {
   const Config &Cfg = Config::current();
   if (Cfg.Diagnostics.UnusedIncludes != Config::UnusedIncludesPolicy::Strict ||
       Cfg.Diagnostics.SuppressAll ||
       Cfg.Diagnostics.Suppress.contains("unused-includes"))

clang-tools-extra/include-cleaner/CMakeLists.txt

+include_directories(include)
+include_directories(${CMAKE_CURRENT_BINARY_DIR}/include)
+add_subdirectory(lib)
+add_subdirectory(tool)
+

clang-tools-extra/include-cleaner/README.md

+# include-cleaner
+
+This is intended as a library, to be embedded in clang-tidy, clangd and other
+tools. Nevertheless a standalone clang-include-cleaner based on libTooling is
+provided.

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

+//===--- Analysis.h - Analyze used files --------------------------- 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 CLANG_INCLUDE_CLEANER_ANALYSIS_H
+#define CLANG_INCLUDE_CLEANER_ANALYSIS_H
+
+#include "clang-include-cleaner/Policy.h"
+#include "clang-include-cleaner/Types.h"
+
+namespace clang {
+namespace include_cleaner {
+class Cache;
+
+class AnalysisContext {
+public:
+  AnalysisContext(const Policy &, const Preprocessor &);
+  AnalysisContext(AnalysisContext &&) = delete;
+  AnalysisContext &operator=(AnalysisContext &&) = delete;
+  ~AnalysisContext();
+
+  const SourceManager &sourceManager() const { return *SM; }
+  const Preprocessor &preprocessor() const { return *PP; }
+  const Policy &policy() const { return P; }
+
+  Cache &cache() { return *C; }
+  // FIXME: does this need to be public?
+  Symbol macro(const IdentifierInfo *, SourceLocation);
+
+private:
+  Policy P;
+  const SourceManager *SM;
+  const Preprocessor *PP;
+  std::unique_ptr<Cache> C;
+};
+
+// A UsedSymbolVisitor is a callback invoked for each symbol reference seen.
+// References occur at a particular location, refer to a single symbol, and
+// that symbol may be provided by any of several headers.
+using UsedSymbolVisitor =
+    llvm::function_ref<void(SourceLocation UsedAt, Symbol UsedSymbol,
+                            llvm::ArrayRef<Header> ProvidedBy)>;
+
+// Find and report all references to symbols in a region of code.
+// The AST traversal is rooted at ASTRoots - typically top-level declarations
+// of a single source file. MacroRefs are additional recorded references to
+// macros, which do not appear in the AST.
+void walkUsed(AnalysisContext &, llvm::ArrayRef<Decl *> ASTRoots,
+              llvm::ArrayRef<SymbolReference> MacroRefs,
+              UsedSymbolVisitor Callback);
+
+} // namespace include_cleaner
+} // namespace clang
+
+#endif

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

+//===--- Hooks.h - Record compiler events -------------------------- 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 CLANG_INCLUDE_CLEANER_HOOKS_H
+#define CLANG_INCLUDE_CLEANER_HOOKS_H
+
+#include "Analysis.h"
+#include "Types.h"
+#include "clang/Basic/SourceLocation.h"
+#include "llvm/ADT/DenseMap.h"
+#include "llvm/ADT/SmallVector.h"
+#include "llvm/ADT/StringMap.h"
+#include "llvm/ADT/StringRef.h"
+#include <vector>
+
+namespace clang {
+class FileEntry;
+class PPCallbacks;
+namespace include_cleaner {
+class PPRecorder;
+
+struct RecordedPP {
+  struct Include {
+    llvm::StringRef Spelled;
+    const FileEntry *Resolved;
+    SourceLocation Location;
+    unsigned Line;
+  };
+  class RecordedIncludes {
+  public:
+    llvm::ArrayRef<Include> all() const { return All; }
+    llvm::SmallVector<const Include *> match(Header H) const;
+
+  private:
+    std::vector<Include> All;
+    llvm::StringMap<llvm::SmallVector<unsigned>> BySpelling;
+    llvm::DenseMap<const FileEntry *, llvm::SmallVector<unsigned>> ByFile;
+    friend PPRecorder;
+  } Includes;
+
+  std::vector<SymbolReference> MacroReferences;
+
+  std::unique_ptr<PPCallbacks> record(AnalysisContext &Ctx);
+};
+
+struct RecordedAST {
+  std::vector<Decl *> TopLevelDecls;
+
+  std::unique_ptr<ASTConsumer> record(AnalysisContext &Ctx);
+};
+
+} // namespace include_cleaner
+} // namespace clang
+
+#endif

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

+//===--- Policy.h - Tuning what is considered used ----------------- 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 CLANG_INCLUDE_CLEANER_POLICY_H
+#define CLANG_INCLUDE_CLEANER_POLICY_H
+
+namespace clang {
+namespace include_cleaner {
+
+// Provides some fine-tuning of include-cleaner's choices about what is used.
+//
+// Changing the policy serves two purposes:
+// - marking more things used reduces the false-positives for "unused include",
+//   while marking fewer things improves "missing include" in the same way.
+// - different coding styles may make different decisions about which includes
+//   are required.
+struct Policy {
+  // Does construction count as use of the type, when the type is not named?
+  // e.g. printVector({x, y, z});  - is std::vector used?
+  bool Construction = false;
+  // Is member access tracked as a reference?
+  bool Members = false;
+  // Are operator calls tracked as references?
+  bool Operators = false;
+};
+
+} // namespace include_cleaner
+} // namespace clang
+
+#endif

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

+//===--- Types.h - Data structures for used-symbol 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
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef CLANG_INCLUDE_CLEANER_TYPES_H
+#define CLANG_INCLUDE_CLEANER_TYPES_H
+
+#include "clang/AST/DeclBase.h"
+#include "clang/Tooling/Inclusions/StandardLibrary.h"
+#include "llvm/ADT/PointerSumType.h"
+
+namespace clang {
+class IdentifierInfo;
+class MacroDirective;
+
+namespace include_cleaner {
+
+// Identifies a macro, along with the definition that was seen for it.
+struct DefinedMacro {
+  const IdentifierInfo *Name;
+  const SourceLocation Definition;
+};
+
+// A Symbol is an entity that can be referenced.
+// It is either a declaration (NamedDecl) or a macro (DefinedMacro).
+class Symbol {
+public:
+  enum Kind {
+    Macro,
+    Declaration,
+  };
+  Symbol(NamedDecl *ND) : Target(ND) {}
+  Symbol(const DefinedMacro *M) : Target(M) {}
+
+  std::string name() const;
+  std::string nodeName() const;
+  Kind kind() const { return Target.is<NamedDecl *>() ? Declaration : Macro; }
+
+  NamedDecl *getDeclaration() const { return Target.get<NamedDecl *>(); }
+  const DefinedMacro *getMacro() const {
+    return Target.get<const DefinedMacro *>();
+  }
+
+private:
+  llvm::PointerUnion<const DefinedMacro *, NamedDecl *> Target;
+};
+
+// A usage of a Symbol seen in our source code.
+struct SymbolReference {
+  SourceLocation Location;
+  Symbol Target;
+};
+
+// A Location is a place where a symbol can be provided.
+// It is either a physical part of the TU (SourceLocation) or a logical location
+// in the standard library (stdlib::Symbol).
+class Location {
+public:
+  enum Kind : uint8_t {
+    Physical,
+    StandardLibrary,
+  };
+
+  Location(SourceLocation S) : K(Physical), SrcLoc(S) {}
+  Location(tooling::stdlib::Symbol S) : K(StandardLibrary), StdlibSym(S) {}
+
+  std::string name(const SourceManager &SM) const;
+  Kind kind() const { return K; }
+
+  SourceLocation getPhysical() const {
+    assert(kind() == Physical);
+    return SrcLoc;
+  };
+  tooling::stdlib::Symbol getStandardLibrary() const {
+    assert(kind() == StandardLibrary);
+    return StdlibSym;
+  };
+
+private:
+  Kind K;
+  union {
+    SourceLocation SrcLoc;
+    tooling::stdlib::Symbol StdlibSym;
+  };
+};
+
+// A Header is an includable file that can provide access to Locations.
+// It is either a physical file (FileEntry), a logical location in the standard
+// library (stdlib::Header), or a verbatim header spelling (StringRef).
+class Header {
+public:
+  enum Kind : uint8_t {
+    Physical,
+    StandardLibrary,
+    Verbatim,
+    Builtin,
+    MainFile,
+  };
+
+  Header(const FileEntry *FE) : K(Physical), PhysicalFile(FE) {}
+  Header(tooling::stdlib::Header H) : K(StandardLibrary), StdlibHeader(H) {}
+  Header(const char *V) : K(Verbatim), VerbatimSpelling(V) {}
+  static Header builtin() { return Header{Builtin}; };
+  static Header mainFile() { return Header{MainFile}; };
+
+  std::string name() const;
+  Kind kind() const { return K; }
+
+  const FileEntry *getPhysical() const {
+    assert(kind() == Physical);
+    return PhysicalFile;
+  };
+  tooling::stdlib::Header getStandardLibrary() const {
+    assert(kind() == StandardLibrary);
+    return StdlibHeader;
+  };
+  llvm::StringRef getVerbatimSpelling() const {
+    assert(kind() == Verbatim);
+    return VerbatimSpelling;
+  };
+
+private:
+  Header(Kind K) : K(K) {}
+
+  Kind K;
+  union {
+    const FileEntry *PhysicalFile;
+    tooling::stdlib::Header StdlibHeader;
+    const char *VerbatimSpelling;
+  };
+
+  friend bool operator==(const Header &L, const Header &R) {
+    if (L.kind() != R.kind())
+      return false;
+    switch (L.kind()) {
+    case Physical:
+      return L.getPhysical() == R.getPhysical();
+    case StandardLibrary:
+      return L.getStandardLibrary() == R.getStandardLibrary();
+    case Verbatim:
+      return L.getVerbatimSpelling() == R.getVerbatimSpelling();
+    case Builtin:
+    case MainFile:
+      return true; // no payload
+    }
+    llvm_unreachable("unhandled Header kind");
+  }
+
+  friend llvm::hash_code hash_value(const Header &H) {
+    switch (H.K) {
+    case Header::Physical:
+      return llvm::hash_combine(H.K, H.getPhysical());
+    case Header::StandardLibrary:
+      // FIXME: make StdlibHeader hashable instead.
+      return llvm::hash_combine(H.K, H.getStandardLibrary().name());
+    case Header::Verbatim:
+      return llvm::hash_combine(H.K, llvm::StringRef(H.VerbatimSpelling));
+    case Header::Builtin:
+    case Header::MainFile:
+      return llvm::hash_value(H.K);
+    }
+  }
+};
+
+template <typename T> struct DefaultDenseMapInfo {
+  static T isEqual(const T &L, const T &R) { return L == R; }
+  static unsigned getHashValue(const T &V) { return hash_value(V); }
+};
+
+} // namespace include_cleaner
+} // namespace clang
+
+namespace llvm {
+template <> struct DenseMapInfo<clang::include_cleaner::Header> {
+  using Header = clang::include_cleaner::Header;
+  static Header getTombstoneKey() { return Header("__tombstone__"); }
+  static Header getEmptyKey() { return Header("__empty__"); }
+  static bool isEqual(const Header &L, const Header &R) { return L == R; }
+  static unsigned getHashValue(const Header &V) { return hash_value(V); }
+};
+} // namespace llvm
+
+#endif

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

+#include "clang-include-cleaner/Analysis.h"
+#include "AnalysisInternal.h"
+#include "clang/Lex/Preprocessor.h"
+
+namespace clang {
+namespace include_cleaner {
+
+AnalysisContext::AnalysisContext(const Policy &P, const Preprocessor &PP)
+    : P(P), SM(&PP.getSourceManager()), PP(&PP), C(std::make_unique<Cache>()) {}
+AnalysisContext::~AnalysisContext() = default;
+
+void walkUsed(AnalysisContext &Ctx, llvm::ArrayRef<Decl *> ASTRoots,
+              llvm::ArrayRef<SymbolReference> MacroRefs,
+              UsedSymbolVisitor Callback) {
+  for (Decl *Root : ASTRoots) {
+    walkAST(Ctx, *Root, [&](SourceLocation RefLoc, NamedDecl &ND) {
+      auto Locations = locateDecl(Ctx, ND);
+      llvm::SmallVector<Header> Headers;
+      for (const auto &Loc : Locations)
+        Headers.append(includableHeader(Ctx, Loc));
+      Callback(RefLoc, &ND, Headers);
+    });
+  }
+  for (const SymbolReference &MacroRef : MacroRefs) {
+    assert(MacroRef.Target.kind() == Symbol::Macro);
+    auto Loc = locateMacro(Ctx, *MacroRef.Target.getMacro());
+    auto Headers = includableHeader(Ctx, Loc);
+    Callback(MacroRef.Location, MacroRef.Target, Headers);
+  }
+}
+
+Symbol AnalysisContext::macro(const IdentifierInfo *II, SourceLocation Loc) {
+  return cache().macro(II, Loc);
+}
+
+} // namespace include_cleaner
+} // namespace clang

clang-tools-extra/include-cleaner/lib/AnalysisInternal.h

+//===--- AnalysisInternal.h - Analysis building blocks ------------- 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
+//
+//===----------------------------------------------------------------------===//
+//
+// This file provides smaller, testable pieces of the used-header analysis.
+// We find the headers by chaining together several mappings.
+//
+// AST => AST node => Symbol => Location => Header
+//                   /
+// Macro expansion =>
+//
+// The individual steps are declared here.
+// (AST => AST Node => Symbol is one API to avoid materializing DynTypedNodes).
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef CLANG_INCLUDE_CLEANER_ANALYSISINTERNAL_H
+#define CLANG_INCLUDE_CLEANER_ANALYSISINTERNAL_H
+
+#include "clang-include-cleaner/Analysis.h"
+#include "clang-include-cleaner/Types.h"
+#include "clang/Tooling/Inclusions/StandardLibrary.h"
+
+namespace clang {
+namespace include_cleaner {
+
+class Cache {
+public:
+  Symbol macro(const IdentifierInfo *Name, const SourceLocation Def) {
+    auto &DMS = DefinedMacros[Name->getName()];
+    // Linear search. We probably only saw ~1 definition of each macro name.
+    for (const DefinedMacro &DM : DMS)
+      if (DM.Definition == Def)
+        return &DM;
+    DMS.push_back(DefinedMacro{Name, Def});
+    return &DMS.back();
+  }
+
+  tooling::stdlib::Recognizer StdlibRecognizer;
+
+private:
+  llvm::StringMap<llvm::SmallVector<DefinedMacro>> DefinedMacros;
+};
+
+// Traverses a subtree of the AST, reporting declarations referenced.
+void walkAST(AnalysisContext &, Decl &Root,
+             llvm::function_ref<void(SourceLocation, NamedDecl &)>);
+
+// Finds the locations where a declaration is provided.
+llvm::SmallVector<Location> locateDecl(AnalysisContext &, const NamedDecl &);
+
+// Finds the locations where a macro is provided.
+Location locateMacro(AnalysisContext &, const DefinedMacro &);
+
+// Finds the headers that provide a location.
+llvm::SmallVector<Header> includableHeader(AnalysisContext &, const Location &);
+
+} // namespace include_cleaner
+} // namespace clang
+
+#endif

clang-tools-extra/include-cleaner/lib/CMakeLists.txt

+set(LLVM_LINK_COMPONENTS Support)
+
+add_clang_library(clangIncludeCleaner
+  Analysis.cpp
+  Headers.cpp
+  Hooks.cpp
+  Locations.cpp
+  Types.cpp
+  WalkAST.cpp
+
+  LINK_LIBS
+  clangBasic
+  clangLex
+  clangAST
+  )
+

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

+#include "AnalysisInternal.h"
+#include "clang/Basic/SourceManager.h"
+#include "clang/Lex/Preprocessor.h"
+
+namespace clang {
+namespace include_cleaner {
+
+llvm::SmallVector<Header> includableHeader(AnalysisContext &Ctx,
+                                           const Location &Loc) {
+  switch (Loc.kind()) {
+  case Location::Physical: {
+    FileID FID = Ctx.sourceManager().getFileID(
+        Ctx.sourceManager().getExpansionLoc(Loc.getPhysical()));
+    if (FID == Ctx.sourceManager().getMainFileID())
+      return {Header::mainFile()};
+    if (FID == Ctx.preprocessor().getPredefinesFileID())
+      return {Header::builtin()};
+    if (auto *FE = Ctx.sourceManager().getFileEntryForID(FID))
+      return {FE};
+    return {};
+  }
+  case Location::StandardLibrary:
+    return {Loc.getStandardLibrary().header()};
+  }
+}
+
+} // namespace include_cleaner
+} // namespace clang

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

+//===--- Hooks.cpp - Record events from the compiler --------------- 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 "clang-include-cleaner/Hooks.h"
+#include "AnalysisInternal.h"
+#include "clang-include-cleaner/Analysis.h"
+#include "clang/AST/ASTConsumer.h"
+#include "clang/AST/DeclCXX.h"
+#include "clang/AST/DeclGroup.h"
+#include "clang/AST/DeclObjC.h"
+#include "clang/Lex/MacroInfo.h"
+#include "clang/Lex/PPCallbacks.h"
+#include "clang/Lex/Preprocessor.h"
+#include "clang/Lex/Token.h"
+
+namespace clang {
+namespace include_cleaner {
+
+class PPRecorder : public PPCallbacks {
+public:
+  PPRecorder(AnalysisContext &Ctx, RecordedPP &Recorded)
+      : Ctx(Ctx), Recorded(Recorded) {}
+
+  virtual void FileChanged(SourceLocation Loc, FileChangeReason Reason,
+                           SrcMgr::CharacteristicKind FileType,
+                           FileID PrevFID) override {
+    Active = Ctx.sourceManager().isWrittenInMainFile(Loc);
+  }
+
+  void InclusionDirective(SourceLocation Hash, const Token &IncludeTok,
+                          StringRef SpelledFilename, bool IsAngled,
+                          CharSourceRange FilenameRange, const FileEntry *File,
+                          StringRef SearchPath, StringRef RelativePath,
+                          const Module *, SrcMgr::CharacteristicKind) override {
+    if (!Active)
+      return;
+
+    unsigned Index = Recorded.Includes.All.size();
+    Recorded.Includes.All.emplace_back();
+    RecordedPP::Include &I = Recorded.Includes.All.back();
+    I.Location = Hash;
+    I.Resolved = File;
+    I.Line = Ctx.sourceManager().getSpellingLineNumber(Hash);
+    auto BySpellingIt =
+        Recorded.Includes.BySpelling.try_emplace(SpelledFilename).first;
+    I.Spelled = BySpellingIt->first();
+
+    BySpellingIt->second.push_back(Index);
+    Recorded.Includes.ByFile[File].push_back(Index);
+  }
+
+  void MacroExpands(const Token &MacroName, const MacroDefinition &MD,
+                    SourceRange Range, const MacroArgs *Args) override {
+    if (!Active)
+      return;
+    recordMacroRef(MacroName, *MD.getMacroInfo());
+  }
+
+  void MacroDefined(const Token &MacroName, const MacroDirective *MD) override {
+    if (!Active)
+      return;
+
+    const auto *MI = MD->getMacroInfo();
+    // The tokens of a macro definition could refer to a macro.
+    // Formally this reference isn't resolved until this macro is expanded,
+    // but we want to treat it as a reference anyway.
+    for (const auto &Tok : MI->tokens()) {
+      auto *II = Tok.getIdentifierInfo();
+      // Could this token be a reference to a macro? (Not param to this macro).
+      if (!II || !II->hadMacroDefinition() ||
+          llvm::is_contained(MI->params(), II))
+        continue;
+      if (const MacroInfo *MI = Ctx.preprocessor().getMacroInfo(II))
+        recordMacroRef(Tok, *MI);
+    }
+  }
+
+private:
+  void recordMacroRef(const Token &Tok, const MacroInfo &MI) {
+    if (MI.isBuiltinMacro())
+      return; // __FILE__ is not a reference.
+    Recorded.MacroReferences.push_back(SymbolReference{
+        Tok.getLocation(),
+        Ctx.cache().macro(Tok.getIdentifierInfo(), MI.getDefinitionLoc())});
+  }
+
+  bool Active = false;
+  AnalysisContext &Ctx;
+  RecordedPP &Recorded;
+};
+
+llvm::SmallVector<const RecordedPP::Include *>
+RecordedPP::RecordedIncludes::match(Header H) const {
+  llvm::SmallVector<const Include *> Result;
+  switch (H.kind()) {
+  case Header::Physical:
+    for (unsigned I : ByFile.lookup(H.getPhysical()))
+      Result.push_back(&All[I]);
+    break;
+  case Header::StandardLibrary:
+    for (unsigned I :
+         BySpelling.lookup(H.getStandardLibrary().name().trim("<>")))
+      Result.push_back(&All[I]);
+    break;
+  case Header::Verbatim:
+    for (unsigned I : BySpelling.lookup(H.getVerbatimSpelling()))
+      Result.push_back(&All[I]);
+    break;
+  case Header::Builtin:
+  case Header::MainFile:
+    break;
+  }
+  llvm::sort(Result);
+  Result.erase(std::unique(Result.begin(), Result.end()), Result.end());
+  return Result;
+}
+
+class ASTRecorder : public ASTConsumer {
+public:
+  ASTRecorder(AnalysisContext &Ctx, RecordedAST &Recorded)
+      : Ctx(Ctx), Recorded(Recorded) {}
+
+  bool HandleTopLevelDecl(DeclGroupRef DG) override {
+    for (Decl *D : DG) {
+      if (!Ctx.sourceManager().isWrittenInMainFile(
+              Ctx.sourceManager().getExpansionLoc(D->getLocation())))
+        continue;
+      if (const auto *T = llvm::dyn_cast<FunctionDecl>(D))
+        if (T->getTemplateSpecializationKind() == TSK_ImplicitInstantiation)
+          continue;
+      if (const auto *T = llvm::dyn_cast<CXXRecordDecl>(D))
+        if (T->getTemplateSpecializationKind() == TSK_ImplicitInstantiation)
+          continue;
+      if (const auto *T = llvm::dyn_cast<VarDecl>(D))
+        if (T->getTemplateSpecializationKind() == TSK_ImplicitInstantiation)
+          continue;
+      // ObjCMethodDecl are not actually top-level!
+      if (isa<ObjCMethodDecl>(D))
+        continue;
+
+      Recorded.TopLevelDecls.push_back(D);
+    }
+    return true;
+  }
+
+private:
+  AnalysisContext &Ctx;
+  RecordedAST &Recorded;
+};
+
+std::unique_ptr<PPCallbacks> RecordedPP::record(AnalysisContext &Ctx) {
+  return std::make_unique<PPRecorder>(Ctx, *this);
+}
+
+std::unique_ptr<ASTConsumer> RecordedAST::record(AnalysisContext &Ctx) {
+  return std::make_unique<ASTRecorder>(Ctx, *this);
+}
+
+} // namespace include_cleaner
+} // namespace clang

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

+#include "AnalysisInternal.h"
+#include "clang-include-cleaner/Analysis.h"
+#include "clang-include-cleaner/Types.h"
+#include "clang/AST/Decl.h"
+#include "clang/AST/DeclBase.h"
+#include "clang/Basic/SourceLocation.h"
+#include "llvm/ADT/SmallVector.h"
+
+namespace clang {
+namespace include_cleaner {
+
+llvm::SmallVector<Location> locateDecl(AnalysisContext &Ctx,
+                                       const NamedDecl &ND) {
+  if (auto StdlibSym = Ctx.cache().StdlibRecognizer(&ND))
+    return {*StdlibSym};
+
+  llvm::SmallVector<Location> Result;
+  for (const Decl *RD : ND.redecls()) {
+    // `friend X` is not an interesting location for X unless it's acting as a
+    // forward-declaration.
+    if (RD->getFriendObjectKind() == Decl::FOK_Declared)
+      continue;
+    SourceLocation Loc = RD->getLocation();
+    if (Loc.isValid())
+      Result.push_back(Loc);
+  }
+  return Result;
+}
+
+Location locateMacro(AnalysisContext &Ctx, const DefinedMacro &M) {
+  return {M.Definition};
+}
+
+} // namespace include_cleaner
+} // namespace clang

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

+#include "clang-include-cleaner/Types.h"
+#include "clang/AST/Decl.h"
+#include "clang/Basic/FileEntry.h"
+#include "clang/Basic/IdentifierTable.h"
+#include "clang/Tooling/Inclusions/StandardLibrary.h"
+
+namespace clang {
+namespace include_cleaner {
+
+std::string Symbol::name() const {
+  switch (kind()) {
+  case Macro:
+    return getMacro()->Name->getName().str();
+  case Declaration:
+    return getDeclaration()->getNameAsString();
+  }
+  llvm_unreachable("Unhandled Symbol kind");
+}
+
+std::string Symbol::nodeName() const {
+  if (kind() == Macro)
+    return "macro";
+  return getDeclaration()->getDeclKindName();
+}
+
+std::string Location::name(const SourceManager &SM) const {
+  switch (K) {
+  case Physical:
+    return SrcLoc.printToString(SM);
+  case StandardLibrary:
+    return StdlibSym.name().str();
+  }
+  llvm_unreachable("Unhandled Location kind");
+}
+
+std::string Header::name() const {
+  switch (K) {
+  case Physical:
+    return PhysicalFile->getName().str();
+  case StandardLibrary:
+    return StdlibHeader.name().str();
+  case Verbatim:
+    return VerbatimSpelling;
+  case Builtin:
+    return "<built-in>";
+  case MainFile:
+    return "<main-file>";
+  }
+  llvm_unreachable("Unhandled Header kind");
+}
+
+} // namespace include_cleaner
+} // namespace clang

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

+#include "AnalysisInternal.h"
+#include "clang-include-cleaner/Analysis.h"
+#include "clang/AST/RecursiveASTVisitor.h"
+#include "clang/Basic/SourceManager.h"
+#include "llvm/Support/SaveAndRestore.h"
+
+namespace clang {
+namespace include_cleaner {
+namespace {
+
+using DeclCallback = llvm::function_ref<void(SourceLocation, NamedDecl &)>;
+
+class ASTWalker : public RecursiveASTVisitor<ASTWalker> {
+public:
+  ASTWalker(AnalysisContext &Ctx, DeclCallback Callback)
+      : Ctx(Ctx), Callback(Callback) {}
+
+  bool VisitDeclRefExpr(DeclRefExpr *E) {
+    if (!Ctx.policy().Operators)
+      if (auto *FD = E->getDecl()->getAsFunction())
+        if (FD->isOverloadedOperator())
+          return true;
+    report(E->getLocation(), E->getFoundDecl());
+    return true;
+  }
+
+  bool VisitMemberExpr(MemberExpr *ME) {
+    if (Ctx.policy().Members)
+      report(ME->getMemberLoc(), ME->getFoundDecl().getDecl());
+    return true;
+  }
+
+  bool VisitTagType(TagType *TT) {
+    report(LocationOfType, TT->getDecl());
+    return true;
+  }
+
+  bool VisitFunctionDecl(FunctionDecl *FD) {
+    // Count function definitions as a reference to their declarations.
+    if (FD->isThisDeclarationADefinition() && FD->getCanonicalDecl() != FD)
+      report(FD->getLocation(), FD->getCanonicalDecl());
+    return true;
+  }
+
+  bool VisitCXXConstructExpr(CXXConstructExpr *E) {
+    if (!Ctx.policy().Construction)
+      return true;
+    SaveAndRestore<SourceLocation> Loc(LocationOfType, E->getLocation());
+    LocationOfType = E->getLocation();
+    return TraverseType(E->getType());
+  }
+
+  bool VisitTemplateSpecializationType(TemplateSpecializationType *TST) {
+    report(LocationOfType,
+           TST->getTemplateName().getAsTemplateDecl()); // Primary template.
+    report(LocationOfType, TST->getAsCXXRecordDecl());  // Specialization
+    return true;
+  }
+
+  bool VisitUsingType(UsingType *UT) {
+    report(LocationOfType, UT->getFoundDecl());
+    return true;
+  }
+
+  bool VisitTypedefType(TypedefType *TT) {
+    report(LocationOfType, TT->getDecl());
+    return true;
+  }
+
+  bool VisitUsingDecl(UsingDecl *UD) {
+    for (const auto *USD : UD->shadows())
+      report(UD->getLocation(), USD->getTargetDecl());
+    return true;
+  }
+
+  bool VisitOverloadExpr(OverloadExpr *E) {
+    if (llvm::isa<UnresolvedMemberExpr>(E) && !Ctx.policy().Members)
+      return true;
+    for (auto *Candidate : E->decls())
+      report(E->getExprLoc(), Candidate);
+    return true;
+  }
+
+  bool TraverseTypeLoc(TypeLoc TL) {
+    SaveAndRestore<SourceLocation> Loc(LocationOfType, TL.getBeginLoc());
+    return Base::TraverseTypeLoc(TL);
+  }
+
+private:
+  void report(SourceLocation Loc, NamedDecl *ND) {
+    while (Loc.isMacroID()) {
+      auto DecLoc = Ctx.sourceManager().getDecomposedLoc(Loc);
+      const SrcMgr::ExpansionInfo &Expansion =
+          Ctx.sourceManager().getSLocEntry(DecLoc.first).getExpansion();
+      if (!Expansion.isMacroArgExpansion())
+        return; // Names in macro bodies are not considered references.
+      Loc = Expansion.getSpellingLoc().getLocWithOffset(DecLoc.second);
+    }
+    if (ND)
+      Callback(Loc, *ND);
+  }
+
+  using Base = RecursiveASTVisitor;
+
+  AnalysisContext &Ctx;
+  DeclCallback Callback;
+
+  SourceLocation LocationOfType;
+};
+
+} // namespace
+
+void walkAST(AnalysisContext &Ctx, Decl &Root, DeclCallback Callback) {
+  ASTWalker(Ctx, Callback).TraverseDecl(&Root);
+}
+
+} // namespace include_cleaner
+} // namespace clang

clang-tools-extra/include-cleaner/tool/CMakeLists.txt

+set(LLVM_LINK_COMPONENTS support)
+
+add_clang_tool(clang-include-cleaner
+  ClangIncludeCleaner.cpp
+  )
+
+clang_target_link_libraries(clang-include-cleaner
+  PRIVATE
+  clangBasic
+  clangFrontend
+  clangTooling
+  )
+
+target_link_libraries(clang-include-cleaner
+  PRIVATE
+  clangIncludeCleaner
+  )
+
+

clang-tools-extra/include-cleaner/tool/ClangIncludeCleaner.cpp

+#include "clang-include-cleaner/Analysis.h"
+#include "clang-include-cleaner/Hooks.h"
+#include "clang/Basic/Diagnostic.h"
+#include "clang/Frontend/CompilerInstance.h"
+#include "clang/Frontend/FrontendAction.h"
+#include "clang/Tooling/CommonOptionsParser.h"
+#include "clang/Tooling/Tooling.h"
+#include "llvm/Support/CommandLine.h"
+#include "llvm/Support/InitLLVM.h"
+
+llvm::cl::OptionCategory OptionsCat{"clang-include-cleaner"};
+llvm::cl::opt<bool> ShowSatisfied{
+    "satisfied",
+    llvm::cl::cat(OptionsCat),
+    llvm::cl::desc(
+        "Show references whose header is included, and used includes"),
+    llvm::cl::init(false),
+};
+llvm::cl::opt<bool> Recover{
+    "recover",
+    llvm::cl::cat(OptionsCat),
+    llvm::cl::desc("Suppress further errors for the same header"),
+    llvm::cl::init(true),
+};
+
+namespace clang {
+namespace include_cleaner {
+namespace {
+
+class Action : public clang::ASTFrontendAction {
+public:
+  bool BeginSourceFileAction(CompilerInstance &CI) override {
+    Diags = &CI.getDiagnostics();
+    initDiagnostics();
+    Ctx.emplace(Policy{}, CI.getPreprocessor());
+    CI.getPreprocessor().addPPCallbacks(PP.record(*Ctx));
+    return true;
+  }
+
+  void EndSourceFile() override {
+    llvm::DenseSet<Header> Recovered;
+    llvm::DenseMap<const RecordedPP::Include *, Symbol> Used;
+    walkUsed(*Ctx, AST.TopLevelDecls, PP.MacroReferences,
+             [&](SourceLocation Loc, Symbol Sym, ArrayRef<Header> Headers) {
+               diagnoseReference(Loc, Sym, Headers, Recovered, Used);
+             });
+    diagnoseIncludes(PP.Includes.all(), Used);
+    Ctx.reset();
+
+    ASTFrontendAction::EndSourceFile();
+  }
+
+  virtual std::unique_ptr<ASTConsumer>
+  CreateASTConsumer(CompilerInstance &CI, StringRef InFile) override {
+    return AST.record(*Ctx);
+  }
+
+private:
+  void initDiagnostics() {
+    auto SatisfiedLevel =
+        ShowSatisfied ? DiagnosticsEngine::Remark : DiagnosticsEngine::Ignored;
+    DiagIDs.Satisfied =
+        Diags->getCustomDiagID(SatisfiedLevel, "%0 '%1' provided by %2");
+    DiagIDs.Unsatisfied = Diags->getCustomDiagID(
+        DiagnosticsEngine::Error, "no header included for %0 '%1'");
+    DiagIDs.NoHeader = Diags->getCustomDiagID(
+        DiagnosticsEngine::Warning, "unclear which header provides %0 '%1'");
+    DiagIDs.NoteHeader =
+        Diags->getCustomDiagID(DiagnosticsEngine::Note, "provided by %0");
+    DiagIDs.Used =
+        Diags->getCustomDiagID(SatisfiedLevel, "include provides %0 '%1'");
+    DiagIDs.Unused =
+        Diags->getCustomDiagID(DiagnosticsEngine::Error, "include is unused");
+  }
+
+  void
+  diagnoseReference(SourceLocation Loc, Symbol Sym, ArrayRef<Header> Headers,
+                    llvm::DenseSet<Header> &Recovered,
+                    llvm::DenseMap<const RecordedPP::Include *, Symbol> &Used) {
+    bool Diagnosed = false;
+    for (const auto &H : Headers) {
+      if (H.kind() == Header::Builtin || H.kind() == Header::MainFile) {
+        if (!Diagnosed) {
+          Diags->Report(Loc, DiagIDs.Satisfied)
+              << Sym.nodeName() << Sym.name() << H.name();
+          Diagnosed = true;
+        }
+      }
+      for (const auto *I : PP.Includes.match(H)) {
+        Used.try_emplace(I, Sym);
+        if (!Diagnosed) {
+          Diags->Report(Loc, DiagIDs.Satisfied)
+              << Sym.nodeName() << Sym.name() << I->Spelled;
+          Diagnosed = true;
+        }
+      }
+    }
+    if (Diagnosed)
+      return;
+    for (const auto &H : Headers) {
+      if (Recovered.contains(H)) {
+        Diags->Report(Loc, DiagIDs.Satisfied)
+            << Sym.nodeName() << Sym.name() << H.name();
+        return;
+      }
+    }
+    Diags->Report(Loc, Headers.empty() ? DiagIDs.NoHeader : DiagIDs.Unsatisfied)
+        << Sym.nodeName() << Sym.name();
+    for (const auto &H : Headers) {
+      Recovered.insert(H);
+      Diags->Report(DiagIDs.NoteHeader) << H.name();
+    }
+  }
+
+  void diagnoseIncludes(
+      ArrayRef<RecordedPP::Include> Includes,
+      const llvm::DenseMap<const RecordedPP::Include *, Symbol> &Used) {
+    for (const auto &I : Includes) {
+      auto It = Used.find(&I);
+      if (It == Used.end())
+        Diags->Report(I.Location, DiagIDs.Unused);
+      else
+        Diags->Report(I.Location, DiagIDs.Used)
+            << It->second.nodeName() << It->second.name();
+    }
+  }
+
+  llvm::Optional<AnalysisContext> Ctx;
+  RecordedPP PP;
+  RecordedAST AST;
+  DiagnosticsEngine *Diags;
+  struct DiagIDs {
+    unsigned Satisfied;
+    unsigned Unsatisfied;
+    unsigned NoHeader;
+    unsigned NoteHeader;
+
+    unsigned Used;
+    unsigned Unused;
+  } DiagIDs;
+};
+
+} // namespace
+} // namespace include_cleaner
+} // namespace clang
+
+int main(int Argc, const char **Argv) {
+  llvm::InitLLVM X(Argc, Argv);
+  auto OptionsParser =
+      clang::tooling::CommonOptionsParser::create(Argc, Argv, OptionsCat);
+  if (!OptionsParser) {
+    llvm::errs() << toString(OptionsParser.takeError());
+    return 1;
+  }
+
+  // Create the tool and run the compilation.
+  return clang::tooling::ClangTool(OptionsParser->getCompilations(),
+                                   OptionsParser->getSourcePathList())
+      .run(clang::tooling::newFrontendActionFactory<
+               clang::include_cleaner::Action>()
+               .get());
+}