18 #include "clang/AST/ASTContext.h"
19 #include "clang/AST/ExprCXX.h"
20 #include "clang/AST/RecursiveASTVisitor.h"
21 #include "clang/Basic/SourceLocation.h"
22 #include "clang/Basic/SourceManager.h"
23 #include "clang/Lex/HeaderSearch.h"
24 #include "clang/Lex/Preprocessor.h"
25 #include "clang/Tooling/Syntax/Tokens.h"
26 #include "llvm/ADT/ArrayRef.h"
27 #include "llvm/ADT/STLFunctionalExtras.h"
28 #include "llvm/ADT/SmallString.h"
29 #include "llvm/ADT/StringSet.h"
30 #include "llvm/Support/FormatVariadic.h"
31 #include "llvm/Support/Path.h"
32 #include "llvm/Support/Regex.h"
45 class ReferencedLocationCrawler
48 ReferencedLocationCrawler(ReferencedLocations &Result,
49 const SourceManager &SM)
50 : Result(Result), SM(SM) {}
52 bool VisitDeclRefExpr(DeclRefExpr *DRE) {
54 add(DRE->getFoundDecl());
58 bool VisitMemberExpr(MemberExpr *ME) {
59 add(ME->getMemberDecl());
60 add(ME->getFoundDecl().getDecl());
64 bool VisitTagType(TagType *TT) {
69 bool VisitFunctionDecl(FunctionDecl *FD) {
71 if (FD->isThisDeclarationADefinition())
76 bool VisitCXXConstructExpr(CXXConstructExpr *CCE) {
77 add(CCE->getConstructor());
81 bool VisitTemplateSpecializationType(TemplateSpecializationType *TST) {
83 if (TST->getTemplateName().getKind() == TemplateName::UsingTemplate)
85 add(TST->getAsCXXRecordDecl());
91 bool TraverseTemplateName(TemplateName TN) {
92 VisitTemplateName(TN);
93 return Base::TraverseTemplateName(TN);
96 bool VisitTemplateName(TemplateName TN) {
97 if (
const auto *USD = TN.getAsUsingShadowDecl()) {
101 add(TN.getAsTemplateDecl());
105 bool VisitUsingType(UsingType *UT) {
106 add(UT->getFoundDecl());
110 bool VisitTypedefType(TypedefType *TT) {
119 bool VisitExpr(Expr *
E) {
120 TraverseType(
E->getType());
124 bool TraverseType(QualType T) {
125 if (isNew(T.getTypePtrOrNull()))
126 Base::TraverseType(T);
130 bool VisitUsingDecl(UsingDecl *
D) {
131 for (
const auto *Shadow :
D->shadows())
132 add(Shadow->getTargetDecl());
139 bool VisitEnumDecl(EnumDecl *
D) {
140 if (
D->isThisDeclarationADefinition() &&
D->getIntegerTypeSourceInfo())
146 bool VisitOverloadExpr(OverloadExpr *
E) {
147 for (
const auto *ResolutionDecl :
E->decls())
155 void add(
const Decl *
D) {
156 if (!
D || !isNew(
D->getCanonicalDecl()))
158 if (
auto SS = StdRecognizer(
D)) {
159 Result.Stdlib.insert(*SS);
169 if (
const auto *RD = llvm::dyn_cast<RecordDecl>(
D)) {
170 if (
const auto *Definition = RD->getDefinition()) {
171 Result.User.insert(
Definition->getLocation());
174 if (SM.isInMainFile(RD->getMostRecentDecl()->getLocation()))
177 for (
const Decl *Redecl :
D->redecls())
178 Result.User.insert(Redecl->getLocation());
181 bool isNew(
const void *P) {
return P && Visited.insert(P).second; }
183 ReferencedLocations &Result;
184 llvm::DenseSet<const void *> Visited;
185 const SourceManager &SM;
186 tooling::stdlib::Recognizer StdRecognizer;
192 struct ReferencedFilesBuilder {
193 ReferencedFilesBuilder(
const SourceManager &SM) : SM(SM) {}
196 const SourceManager &SM;
198 void add(SourceLocation
Loc) { add(SM.getFileID(
Loc),
Loc); }
200 void add(FileID FID, SourceLocation
Loc) {
203 assert(SM.isInFileID(
Loc, FID));
204 if (
Loc.isFileID()) {
209 if (!
Macros.insert(FID).second)
211 const auto &Exp = SM.getSLocEntry(FID).getExpansion();
212 add(Exp.getSpellingLoc());
213 add(Exp.getExpansionLocStart());
214 add(Exp.getExpansionLocEnd());
225 Result.end.character +=
227 return C ==
'\n' || C ==
'\r';
234 void findReferencedMacros(
const SourceManager &SM, Preprocessor &
PP,
235 const syntax::TokenBuffer *Tokens,
236 ReferencedLocations &Result) {
237 trace::Span
Tracer(
"IncludeCleaner::findReferencedMacros");
247 for (
const syntax::Token &Tok : Tokens->spelledTokens(SM.getMainFileID())) {
251 auto Loc =
Macro->Info->getDefinitionLoc();
253 Result.User.insert(
Loc);
258 static bool mayConsiderUnused(
const Inclusion &Inc, ParsedAST &AST,
260 if (Inc.BehindPragmaKeep)
266 if (Inc.Written.front() ==
'<') {
267 if (
AnalyzeStdlib && tooling::stdlib::Header::named(Inc.Written))
271 assert(Inc.HeaderID);
282 if (!AST.
getPreprocessor().getHeaderSearchInfo().isFileMultipleIncludeGuarded(
283 &FE->getFileEntry())) {
284 dlog(
"{0} doesn't have header guard and will not be considered unused",
290 llvm::SmallString<64>
Path(Inc.Resolved);
291 llvm::sys::path::native(
Path, llvm::sys::path::Style::posix);
292 if (Filter(Inc.Resolved)) {
293 dlog(
"{0} header is filtered out by the configuration", FE->getName());
304 FileID headerResponsible(FileID
ID,
const SourceManager &SM,
305 const IncludeStructure &Includes) {
308 for (
const FileEntry *FE = SM.getFileEntryForID(
ID);
ID != SM.getMainFileID();
309 FE = SM.getFileEntryForID(
ID)) {
313 auto HID = Includes.
getID(FE);
314 assert(HID &&
"We're iterating over headers already existing in "
320 ID = SM.getFileID(SM.getIncludeLoc(
ID));
328 const syntax::TokenBuffer *Tokens) {
331 const auto &SM =
Ctx.getSourceManager();
332 ReferencedLocationCrawler Crawler(Result, SM);
333 Crawler.TraverseAST(
Ctx);
335 findReferencedMacros(SM,
PP, Tokens, Result);
346 llvm::function_ref<FileID(FileID)> HeaderResponsible,
347 llvm::function_ref<Optional<StringRef>(FileID)> UmbrellaHeader) {
348 std::vector<SourceLocation> Sorted{Locs.
User.begin(), Locs.
User.end()};
350 ReferencedFilesBuilder
Builder(SM);
351 for (
auto It = Sorted.begin(); It < Sorted.end();) {
352 FileID FID = SM.getFileID(*It);
358 while (It != Sorted.end() && SM.isInFileID(*It, FID));
365 llvm::DenseSet<FileID> UserFiles;
366 llvm::StringSet<> PublicHeaders;
368 UserFiles.insert(HeaderResponsible(
ID));
369 if (
auto PublicHeader = UmbrellaHeader(
ID)) {
370 PublicHeaders.insert(*PublicHeader);
374 llvm::DenseSet<tooling::stdlib::Header> StdlibFiles;
376 for (
const auto &Header :
Symbol.headers())
377 StdlibFiles.insert(Header);
379 return {std::move(UserFiles), std::move(StdlibFiles),
380 std::move(PublicHeaders)};
386 const SourceManager &SM) {
389 [&SM, &Includes](FileID
ID) {
390 return headerResponsible(
ID, SM, Includes);
392 [&SM, &CanonIncludes](FileID
ID) -> Optional<StringRef> {
393 auto Entry = SM.getFileEntryRefForID(
ID);
397 if (PublicHeader.empty())
403 std::vector<const Inclusion *>
406 const llvm::StringSet<> &ReferencedPublicHeaders) {
409 std::vector<const Inclusion *>
Unused;
413 if (ReferencedPublicHeaders.contains(MFI.Written))
417 if (!Used && !mayConsiderUnused(MFI, AST, Cfg)) {
418 dlog(
"{0} was not used, but is not eligible to be diagnosed as unused",
424 dlog(
"{0} is {1}", MFI.Written, Used ?
"USED" :
"UNUSED");
432 const SrcMgr::FileInfo &FI = SM.getSLocEntry(FID).getFile();
433 return FI.getName().startswith(
"<");
437 llvm::DenseSet<IncludeStructure::HeaderID>
440 const SourceManager &SM) {
442 llvm::DenseSet<IncludeStructure::HeaderID> TranslatedHeaderIDs;
443 TranslatedHeaderIDs.reserve(
Files.User.size());
444 for (FileID FID :
Files.User) {
445 const FileEntry *FE = SM.getFileEntryForID(FID);
450 const auto File = Includes.
getID(FE);
452 TranslatedHeaderIDs.insert(*File);
454 for (tooling::stdlib::Header StdlibUsed :
Files.Stdlib)
456 TranslatedHeaderIDs.insert(HID);
457 return TranslatedHeaderIDs;
467 auto ReferencedHeaders =
473 llvm::StringRef
Code) {
480 std::vector<Diag> Result;
489 llvm::formatv(
"included header {0} is not used",
490 llvm::sys::path::filename(
491 Inc->Written.substr(1, Inc->Written.size() - 2),
492 llvm::sys::path::Style::posix));
493 D.Name =
"unused-includes";
494 D.Source = Diag::DiagSource::Clangd;
498 D.Range = getDiagnosticRange(
Code, Inc->HashOffset);
504 D.Fixes.emplace_back();
505 D.Fixes.back().Message =
"remove #include directive";
506 D.Fixes.back().Edits.emplace_back();
507 D.Fixes.back().Edits.back().range.start.line = Inc->HashLine;
508 D.Fixes.back().Edits.back().range.end.line = Inc->HashLine + 1;
509 D.InsideMainFile =
true;
510 Result.push_back(std::move(
D));