[clangd] IncludeCleaner: Decrease API dependency on clangd

[sammccall]

clang-tools-extra/clangd/IncludeCleaner.h

55

we can make Tokens & PP optional, and only track macros if they are present?

This lowers the barrier to entry a bit

65–71

doc HeaderResponsible

68

std::function -> llvm::function_ref?

[kbobyrev]

Resolve review comments.

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 "llvm/ADT/DenseSet.h"
+#include "llvm/ADT/STLFunctionalExtras.h"
 #include <vector>
 
 namespace clang {
 namespace clangd {
 
 struct ReferencedLocations {
   llvm::DenseSet<SourceLocation> User;
   llvm::DenseSet<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".
-/// - We also examine all identifier tokens in the file in case they reference
-///   macros.
-///
+/// - 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(const SourceManager &SM,
+                                            ASTContext &Ctx, Preprocessor &PP,
+                                            const syntax::TokenBuffer *Tokens);
 ReferencedLocations findReferencedLocations(ParsedAST &AST);
 
 struct ReferencedFiles {
   llvm::DenseSet<FileID> User;
   llvm::DenseSet<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);
 
-/// Affects whether standard library includes should be considered for removal.
-/// This is off by default for now due to implementation limitations:
+/// 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 "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; }
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(ParsedAST &AST, ReferencedLocations &Result) {
+void findReferencedMacros(const SourceManager &SM, Preprocessor &PP,
+                          const syntax::TokenBuffer *Tokens,
+                          ReferencedLocations &Result) {
   trace::Span Tracer("IncludeCleaner::findReferencedMacros");
-  auto &SM = AST.getSourceManager();
-  auto &PP = AST.getPreprocessor();
   // 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 :
-       AST.getTokens().spelledTokens(SM.getMainFileID())) {
+  for (const syntax::Token &Tok : Tokens->spelledTokens(SM.getMainFileID())) {
     auto Macro = locateMacroAt(Tok, PP);
     if (!Macro)
       continue;
     auto Loc = Macro->Info->getDefinitionLoc();
     if (Loc.isValid())
       Result.User.insert(Loc);
     // FIXME: support stdlib macros
   }
for (const FileEntry *FE = SM.getFileEntryForID(ID); ID != SM.getMainFileID();
     // on its includer.
     ID = SM.getFileID(SM.getIncludeLoc(ID));
   }
   return ID;
 }
 
 } // namespace
 
-ReferencedLocations findReferencedLocations(ParsedAST &AST) {
+ReferencedLocations findReferencedLocations(const SourceManager &SM,
+                                            ASTContext &Ctx, Preprocessor &PP,
+                                            const syntax::TokenBuffer *Tokens) {
   trace::Span Tracer("IncludeCleaner::findReferencedLocations");
   ReferencedLocations Result;
-  ReferencedLocationCrawler Crawler(Result, AST.getSourceManager());
-  Crawler.TraverseAST(AST.getASTContext());
-  findReferencedMacros(AST, Result);
+  ReferencedLocationCrawler Crawler(Result, SM);
+  Crawler.TraverseAST(Ctx);
+  if (Tokens)
+    findReferencedMacros(SM, PP, Tokens, Result);
   return Result;
 }
 
-ReferencedFiles findReferencedFiles(const ReferencedLocations &Locs,
-                                    const IncludeStructure &Includes,
-                                    const SourceManager &SM) {
+ReferencedLocations findReferencedLocations(ParsedAST &AST) {
+  return findReferencedLocations(AST.getSourceManager(), 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, SM, Includes));
+    UserFiles.insert(HeaderResponsible(ID));
 
   llvm::DenseSet<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;