kbobyrev created this revision.
kbobyrev added a reviewer: sammccall.
Herald added subscribers: usaxena95, kadircet, arphaman, mgrang.
kbobyrev requested review of this revision.
Herald added subscribers: cfe-commits, MaskRay, ilya-biryukov.
Herald added a project: clang-tools-extra.
Follow-p on D105426 <https://reviews.llvm.org/D105426>.
Repository:
rG LLVM Github Monorepo
https://reviews.llvm.org/D108194
Files:
clang-tools-extra/clangd/Headers.cpp
clang-tools-extra/clangd/Headers.h
clang-tools-extra/clangd/IncludeCleaner.cpp
clang-tools-extra/clangd/IncludeCleaner.h
clang-tools-extra/clangd/ParsedAST.cpp
clang-tools-extra/clangd/ParsedAST.h
Index: clang-tools-extra/clangd/ParsedAST.h
===================================================================
--- clang-tools-extra/clangd/ParsedAST.h
+++ clang-tools-extra/clangd/ParsedAST.h
@@ -116,6 +116,8 @@
return Resolver.get();
}
+ void computeUsedIncludes();
+
private:
ParsedAST(llvm::StringRef Version,
std::shared_ptr<const PreambleData> Preamble,
Index: clang-tools-extra/clangd/ParsedAST.cpp
===================================================================
--- clang-tools-extra/clangd/ParsedAST.cpp
+++ clang-tools-extra/clangd/ParsedAST.cpp
@@ -18,6 +18,7 @@
#include "Features.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, getSourceManager());
+ std::vector<llvm::StringRef> 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
Index: clang-tools-extra/clangd/IncludeCleaner.h
===================================================================
--- clang-tools-extra/clangd/IncludeCleaner.h
+++ 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<FileID> findReferencedFiles(const ReferencedLocations &Locs,
+ const SourceManager &SM);
+
+inline llvm::DenseMap<unsigned, bool>
+directlyReferencedFiles(const IncludeStructure::AbstractIncludeGraph &Graph,
+ const llvm::DenseSet<unsigned> &Referenced,
+ unsigned EntryPoint) {
+ llvm::DenseMap<unsigned, bool> Result;
+ for (unsigned Inclusion : Graph.lookup(EntryPoint))
+ Result.try_emplace(Inclusion, Referenced.contains(Inclusion));
+ return Result;
+}
+
} // namespace clangd
} // namespace clang
Index: clang-tools-extra/clangd/IncludeCleaner.cpp
===================================================================
--- clang-tools-extra/clangd/IncludeCleaner.cpp
+++ clang-tools-extra/clangd/IncludeCleaner.cpp
@@ -137,5 +137,24 @@
return Result;
}
+llvm::DenseSet<FileID>
+findReferencedFiles(const llvm::DenseSet<SourceLocation> &Locs,
+ const SourceManager &SM) {
+ std::vector<SourceLocation> 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
Index: clang-tools-extra/clangd/Headers.h
===================================================================
--- clang-tools-extra/clangd/Headers.h
+++ 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<unsigned, SmallVector<unsigned>>;
+ // Decides usage for each file included by EntryPoint based on the set of
+ // files that contain some referenced symbol.
+ using UsedFunc = llvm::DenseMap<unsigned, bool>(
+ const AbstractIncludeGraph &, llvm::DenseSet<unsigned> Referenced,
+ unsigned EntryPoint);
+ // Produce decisions for all files included from \p EntryPoint (usually the
+ // main file).
+ void markUsed(llvm::StringRef EntryPoint,
+ llvm::ArrayRef<StringRef> ReferencedFiles,
+ llvm::function_ref<UsedFunc>);
+
private:
// Identifying files in a way that persists from preamble build to subsequent
// builds is surprisingly hard. FileID is unavailable in InclusionDirective(),
Index: clang-tools-extra/clangd/Headers.cpp
===================================================================
--- clang-tools-extra/clangd/Headers.cpp
+++ clang-tools-extra/clangd/Headers.cpp
@@ -204,6 +204,47 @@
return Result;
}
+void IncludeStructure::markUsed(llvm::StringRef EntryPoint,
+ llvm::ArrayRef<StringRef> ReferencedFiles,
+ llvm::function_ref<UsedFunc> Algorithm) {
+ auto Root = NameToIndex.find(EntryPoint);
+ if (Root == NameToIndex.end()) {
+ elog("IncludeCleaner: EntryPoint {0} not found in include graph",
+ EntryPoint);
+ return;
+ }
+
+ llvm::DenseSet<unsigned> 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</*RealPath*/ StringRef, /*Index*/ unsigned> 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())
_______________________________________________
cfe-commits mailing list
[email protected]
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
