diff --git a/clang-tools-extra/clangd/Headers.h b/clang-tools-extra/clangd/Headers.h --- a/clang-tools-extra/clangd/Headers.h +++ b/clang-tools-extra/clangd/Headers.h @@ -58,6 +58,7 @@ unsigned HashOffset = 0; // Byte offset from start of file to #. int HashLine = 0; // Line number containing the directive, 0-indexed. SrcMgr::CharacteristicKind FileKind = SrcMgr::C_User; + bool Used = false; // Contains symbols used in the main file. }; llvm::raw_ostream &operator<<(llvm::raw_ostream &, const Inclusion &); bool operator==(const Inclusion &LHS, const Inclusion &RHS); @@ -129,6 +130,22 @@ llvm::StringRef IncludedName, llvm::StringRef IncludedRealName); + // Classifying the main-file includes as "used" or "unused" is subtle + // (consider transitive includes), so we inject the algorithm. + + // Maps including files (from) to included files (to). + using AbstractIncludeGraph = llvm::DenseMap>; + // Decides usage for each file included by EntryPoint based on the set of + // files that contain some referenced symbol. + using UsedFunc = llvm::DenseMap( + const AbstractIncludeGraph &, llvm::DenseSet Referenced, + unsigned EntryPoint); + // Produce decisions for all files included from \p EntryPoint (usually the + // main file). + void markUsed(llvm::StringRef EntryPoint, + llvm::ArrayRef ReferencedFiles, + llvm::function_ref); + private: // Identifying files in a way that persists from preamble build to subsequent // builds is surprisingly hard. FileID is unavailable in InclusionDirective(), diff --git a/clang-tools-extra/clangd/Headers.cpp b/clang-tools-extra/clangd/Headers.cpp --- a/clang-tools-extra/clangd/Headers.cpp +++ b/clang-tools-extra/clangd/Headers.cpp @@ -204,6 +204,47 @@ return Result; } +void IncludeStructure::markUsed(llvm::StringRef EntryPoint, + llvm::ArrayRef ReferencedFiles, + llvm::function_ref Algorithm) { + auto Root = NameToIndex.find(EntryPoint); + if (Root == NameToIndex.end()) { + elog("IncludeCleaner: EntryPoint {0} not found in include graph", + EntryPoint); + return; + } + + llvm::DenseSet Referenced; + Referenced.reserve(ReferencedFiles.size()); + for (llvm::StringRef RefName : ReferencedFiles) { + dlog("{0} is REFERENCED", RefName); + auto It = NameToIndex.find(RefName); + if (It != NameToIndex.end()) + Referenced.insert(It->second); + } + + auto Decisions = + Algorithm(IncludeChildren, std::move(Referenced), Root->second); + auto RootChildren = IncludeChildren.find(Root->second); + assert(RootChildren != IncludeChildren.end()); + llvm::DenseMap IncludeIndex; + for (const auto Index : RootChildren->second) { + if (!RealPathNames[Index].empty()) + IncludeIndex[RealPathNames[Index]] = Index; + } + for (auto &MFI : MainFileIncludes) { + // FIXME: Skip includes that are not self-contained. + auto It = IncludeIndex.find(MFI.Resolved); + if (It != IncludeIndex.end()) { + auto DIt = Decisions.find(It->second); + if (DIt != Decisions.end()) { + MFI.Used = DIt->second; + dlog("{0} is {1}", MFI.Written, MFI.Used ? "USED" : "UNUSED"); + } + } + } +} + void IncludeInserter::addExisting(const Inclusion &Inc) { IncludedHeaders.insert(Inc.Written); if (!Inc.Resolved.empty()) diff --git a/clang-tools-extra/clangd/IncludeCleaner.h b/clang-tools-extra/clangd/IncludeCleaner.h --- a/clang-tools-extra/clangd/IncludeCleaner.h +++ b/clang-tools-extra/clangd/IncludeCleaner.h @@ -46,6 +46,22 @@ /// - err on the side of reporting all possible locations ReferencedLocations findReferencedLocations(ParsedAST &AST); +/// Retrieves IDs of all files containing SourceLocations from \p Locs. Those +/// locations could be within macro expansions and are not resolved to their +/// spelling locations. +llvm::DenseSet findReferencedFiles(const ReferencedLocations &Locs, + const SourceManager &SM); + +inline llvm::DenseMap +directlyReferencedFiles(const IncludeStructure::AbstractIncludeGraph &Graph, + const llvm::DenseSet &Referenced, + unsigned EntryPoint) { + llvm::DenseMap Result; + for (unsigned Inclusion : Graph.lookup(EntryPoint)) + Result.try_emplace(Inclusion, Referenced.contains(Inclusion)); + return Result; +} + } // namespace clangd } // namespace clang diff --git a/clang-tools-extra/clangd/IncludeCleaner.cpp b/clang-tools-extra/clangd/IncludeCleaner.cpp --- a/clang-tools-extra/clangd/IncludeCleaner.cpp +++ b/clang-tools-extra/clangd/IncludeCleaner.cpp @@ -98,6 +98,35 @@ llvm::DenseSet Visited; }; +// 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 ReferencedFiles { + ReferencedFiles(const SourceManager &SM) : SM(SM) {} + llvm::DenseSet Files; + llvm::DenseSet 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()); + } +}; + } // namespace ReferencedLocations findReferencedLocations(ParsedAST &AST) { @@ -108,5 +137,24 @@ return Result; } +llvm::DenseSet +findReferencedFiles(const llvm::DenseSet &Locs, + const SourceManager &SM) { + std::vector Sorted{Locs.begin(), Locs.end()}; + // Group by FileID. + llvm::sort(Sorted); + ReferencedFiles Result(SM); + for (auto It = Sorted.begin(); It < Sorted.end();) { + FileID FID = SM.getFileID(*It); + Result.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)); + } + return std::move(Result.Files); +} + } // namespace clangd } // namespace clang diff --git a/clang-tools-extra/clangd/ParsedAST.h b/clang-tools-extra/clangd/ParsedAST.h --- a/clang-tools-extra/clangd/ParsedAST.h +++ b/clang-tools-extra/clangd/ParsedAST.h @@ -116,6 +116,8 @@ return Resolver.get(); } + void computeUsedIncludes(); + private: ParsedAST(llvm::StringRef Version, std::shared_ptr Preamble, diff --git a/clang-tools-extra/clangd/ParsedAST.cpp b/clang-tools-extra/clangd/ParsedAST.cpp --- a/clang-tools-extra/clangd/ParsedAST.cpp +++ b/clang-tools-extra/clangd/ParsedAST.cpp @@ -18,6 +18,7 @@ #include "FeatureModule.h" #include "Headers.h" #include "HeuristicResolver.h" +#include "IncludeCleaner.h" #include "IncludeFixer.h" #include "Preamble.h" #include "SourceCode.h" @@ -601,5 +602,25 @@ return llvm::None; return llvm::StringRef(Preamble->Version); } + +void ParsedAST::computeUsedIncludes() { + const auto &SM = getSourceManager(); + + auto Refs = findReferencedLocations(*this); + auto ReferencedFileIDs = findReferencedFiles(Refs, SM); + std::vector ReferencedFilenames; + ReferencedFilenames.reserve(ReferencedFileIDs.size()); + for (FileID FID : ReferencedFileIDs) { + const FileEntry *FE = SM.getFileEntryForID(FID); + if (!FE) { + elog("Missing FE for {0}", SM.getComposedLoc(FID, 0).printToString(SM)); + continue; + } + ReferencedFilenames.push_back(SM.getFileEntryForID(FID)->getName()); + } + Includes.markUsed(SM.getFileEntryForID(SM.getMainFileID())->getName(), + ReferencedFilenames, directlyReferencedFiles); +} + } // namespace clangd } // namespace clang