Debian Codegraph @

llvm-project/clang-tools-extra/clangd/IncludeCleaner.cpp

raw
1 //===--- IncludeCleaner.cpp - Unused/Missing Headers Analysis ---*- C++ -*-===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8
9 #include "IncludeCleaner.h"
10 #include "Config.h"
11 #include "Headers.h"
12 #include "ParsedAST.h"
13 #include "Protocol.h"
14 #include "SourceCode.h"
15 #include "clang-include-cleaner/Analysis.h"
16 #include "clang-include-cleaner/Types.h"
17 #include "index/CanonicalIncludes.h"
18 #include "support/Logger.h"
19 #include "support/Trace.h"
20 #include "clang/AST/ASTContext.h"
21 #include "clang/AST/ExprCXX.h"
22 #include "clang/AST/RecursiveASTVisitor.h"
23 #include "clang/Basic/SourceLocation.h"
24 #include "clang/Basic/SourceManager.h"
25 #include "clang/Lex/HeaderSearch.h"
26 #include "clang/Lex/Preprocessor.h"
27 #include "clang/Tooling/Syntax/Tokens.h"
28 #include "llvm/ADT/ArrayRef.h"
29 #include "llvm/ADT/STLFunctionalExtras.h"
30 #include "llvm/ADT/SmallString.h"
31 #include "llvm/ADT/StringSet.h"
32 #include "llvm/Support/FormatVariadic.h"
33 #include "llvm/Support/Path.h"
34 #include "llvm/Support/Regex.h"
35 #include <functional>
36 #include <optional>
37
38 namespace clang {
39 namespace clangd {
40
41 static bool AnalyzeStdlib = false;
42 void setIncludeCleanerAnalyzesStdlib(bool B) { AnalyzeStdlib = B; }
43
44 namespace {
45
46 /// Crawler traverses the AST and feeds in the locations of (sometimes
47 /// implicitly) used symbols into \p Result.
48 class ReferencedLocationCrawler
49 : public RecursiveASTVisitor<ReferencedLocationCrawler> {
50 public:
51 ReferencedLocationCrawler(ReferencedLocations &Result,
52 const SourceManager &SM)
53 : Result(Result), SM(SM) {}
54
55 bool VisitDeclRefExpr(DeclRefExpr *DRE) {
56 add(DRE->getDecl());
57 add(DRE->getFoundDecl());
58 return true;
59 }
60
61 bool VisitMemberExpr(MemberExpr *ME) {
62 add(ME->getMemberDecl());
63 add(ME->getFoundDecl().getDecl());
64 return true;
65 }
66
67 bool VisitTagType(TagType *TT) {
68 add(TT->getDecl());
69 return true;
70 }
71
72 bool VisitFunctionDecl(FunctionDecl *FD) {
73 // Function definition will require redeclarations to be included.
74 if (FD->isThisDeclarationADefinition())
75 add(FD);
76 return true;
77 }
78
79 bool VisitCXXConstructExpr(CXXConstructExpr *CCE) {
80 add(CCE->getConstructor());
81 return true;
82 }
83
84 bool VisitTemplateSpecializationType(TemplateSpecializationType *TST) {
85 // Using templateName case is handled by the override TraverseTemplateName.
86 if (TST->getTemplateName().getKind() == TemplateName::UsingTemplate)
87 return true;
88 add(TST->getAsCXXRecordDecl()); // Specialization
89 return true;
90 }
91
92 // There is no VisitTemplateName in RAV, thus we override the Traverse version
93 // to handle the Using TemplateName case.
94 bool TraverseTemplateName(TemplateName TN) {
95 VisitTemplateName(TN);
96 return Base::TraverseTemplateName(TN);
97 }
98 // A pseudo VisitTemplateName, dispatched by the above TraverseTemplateName!
99 bool VisitTemplateName(TemplateName TN) {
100 if (const auto *USD = TN.getAsUsingShadowDecl()) {
101 add(USD);
102 return true;
103 }
104 add(TN.getAsTemplateDecl()); // Primary template.
105 return true;
106 }
107
108 bool VisitUsingType(UsingType *UT) {
109 add(UT->getFoundDecl());
110 return true;
111 }
112
113 bool VisitTypedefType(TypedefType *TT) {
114 add(TT->getDecl());
115 return true;
116 }
117
118 // Consider types of any subexpression used, even if the type is not named.
119 // This is helpful in getFoo().bar(), where Foo must be complete.
120 // FIXME(kirillbobyrev): Should we tweak this? It may not be desirable to
121 // consider types "used" when they are not directly spelled in code.
122 bool VisitExpr(Expr *E) {
123 TraverseType(E->getType());
124 return true;
125 }
126
127 bool TraverseType(QualType T) {
128 if (isNew(T.getTypePtrOrNull())) // don't care about quals
129 Base::TraverseType(T);
130 return true;
131 }
132
133 bool VisitUsingDecl(UsingDecl *D) {
134 for (const auto *Shadow : D->shadows())
135 add(Shadow->getTargetDecl());
136 return true;
137 }
138
139 // Enums may be usefully forward-declared as *complete* types by specifying
140 // an underlying type. In this case, the definition should see the declaration
141 // so they can be checked for compatibility.
142 bool VisitEnumDecl(EnumDecl *D) {
143 if (D->isThisDeclarationADefinition() && D->getIntegerTypeSourceInfo())
144 add(D);
145 return true;
146 }
147
148 // When the overload is not resolved yet, mark all candidates as used.
149 bool VisitOverloadExpr(OverloadExpr *E) {
150 for (const auto *ResolutionDecl : E->decls())
151 add(ResolutionDecl);
152 return true;
153 }
154
155 private:
156 using Base = RecursiveASTVisitor<ReferencedLocationCrawler>;
157
158 void add(const Decl *D) {
159 if (!D || !isNew(D->getCanonicalDecl()))
160 return;
161 if (auto SS = StdRecognizer(D)) {
162 Result.Stdlib.insert(*SS);
163 return;
164 }
165 // Special case RecordDecls, as it is common for them to be forward
166 // declared multiple times. The most common cases are:
167 // - Definition available in TU, only mark that one as usage. The rest is
168 // likely to be unnecessary. This might result in false positives when an
169 // internal definition is visible.
170 // - There's a forward declaration in the main file, no need for other
171 // redecls.
172 if (const auto *RD = llvm::dyn_cast<RecordDecl>(D)) {
173 if (const auto *Definition = RD->getDefinition()) {
174 Result.User.insert(Definition->getLocation());
175 return;
176 }
177 if (SM.isInMainFile(RD->getMostRecentDecl()->getLocation()))
178 return;
179 }
180 for (const Decl *Redecl : D->redecls())
181 Result.User.insert(Redecl->getLocation());
182 }
183
184 bool isNew(const void *P) { return P && Visited.insert(P).second; }
185
186 ReferencedLocations &Result;
187 llvm::DenseSet<const void *> Visited;
188 const SourceManager &SM;
189 tooling::stdlib::Recognizer StdRecognizer;
190 };
191
192 // Given a set of referenced FileIDs, determines all the potentially-referenced
193 // files and macros by traversing expansion/spelling locations of macro IDs.
194 // This is used to map the referenced SourceLocations onto real files.
195 struct ReferencedFilesBuilder {
196 ReferencedFilesBuilder(const SourceManager &SM) : SM(SM) {}
197 llvm::DenseSet<FileID> Files;
198 llvm::DenseSet<FileID> Macros;
199 const SourceManager &SM;
200
201 void add(SourceLocation Loc) { add(SM.getFileID(Loc), Loc); }
202
203 void add(FileID FID, SourceLocation Loc) {
204 if (FID.isInvalid())
205 return;
206 assert(SM.isInFileID(Loc, FID));
207 if (Loc.isFileID()) {
208 Files.insert(FID);
209 return;
210 }
211 // Don't process the same macro FID twice.
212 if (!Macros.insert(FID).second)
213 return;
214 const auto &Exp = SM.getSLocEntry(FID).getExpansion();
215 add(Exp.getSpellingLoc());
216 add(Exp.getExpansionLocStart());
217 add(Exp.getExpansionLocEnd());
218 }
219 };
220
221 // Returns the range starting at '#' and ending at EOL. Escaped newlines are not
222 // handled.
223 clangd::Range getDiagnosticRange(llvm::StringRef Code, unsigned HashOffset) {
224 clangd::Range Result;
225 Result.end = Result.start = offsetToPosition(Code, HashOffset);
226
227 // Span the warning until the EOL or EOF.
228 Result.end.character +=
229 lspLength(Code.drop_front(HashOffset).take_until([](char C) {
230 return C == '\n' || C == '\r';
231 }));
232 return Result;
233 }
234
235 // Finds locations of macros referenced from within the main file. That includes
236 // references that were not yet expanded, e.g `BAR` in `#define FOO BAR`.
237 void findReferencedMacros(const SourceManager &SM, Preprocessor &PP,
238 const syntax::TokenBuffer *Tokens,
239 ReferencedLocations &Result) {
240 trace::Span Tracer("IncludeCleaner::findReferencedMacros");
241 // FIXME(kirillbobyrev): The macros from the main file are collected in
242 // ParsedAST's MainFileMacros. However, we can't use it here because it
243 // doesn't handle macro references that were not expanded, e.g. in macro
244 // definitions or preprocessor-disabled sections.
245 //
246 // Extending MainFileMacros to collect missing references and switching to
247 // this mechanism (as opposed to iterating through all tokens) will improve
248 // the performance of findReferencedMacros and also improve other features
249 // relying on MainFileMacros.
250 for (const syntax::Token &Tok : Tokens->spelledTokens(SM.getMainFileID())) {
251 auto Macro = locateMacroAt(Tok, PP);
252 if (!Macro)
253 continue;
254 auto Loc = Macro->Info->getDefinitionLoc();
255 if (Loc.isValid())
256 Result.User.insert(Loc);
257 // FIXME: support stdlib macros
258 }
259 }
260
261 static bool mayConsiderUnused(const Inclusion &Inc, ParsedAST &AST,
262 const Config &Cfg) {
263 if (Inc.BehindPragmaKeep)
264 return false;
265
266 // FIXME(kirillbobyrev): We currently do not support the umbrella headers.
267 // System headers are likely to be standard library headers.
268 // Until we have good support for umbrella headers, don't warn about them.
269 if (Inc.Written.front() == '<') {
270 if (AnalyzeStdlib && tooling::stdlib::Header::named(Inc.Written))
271 return true;
272 return false;
273 }
274 assert(Inc.HeaderID);
275 auto HID = static_cast<IncludeStructure::HeaderID>(*Inc.HeaderID);
276 // FIXME: Ignore the headers with IWYU export pragmas for now, remove this
277 // check when we have more precise tracking of exported headers.
278 if (AST.getIncludeStructure().hasIWYUExport(HID))
279 return false;
280 auto FE = AST.getSourceManager().getFileManager().getFileRef(
281 AST.getIncludeStructure().getRealPath(HID));
282 assert(FE);
283 // Headers without include guards have side effects and are not
284 // self-contained, skip them.
285 if (!AST.getPreprocessor().getHeaderSearchInfo().isFileMultipleIncludeGuarded(
286 &FE->getFileEntry())) {
287 dlog("{0} doesn't have header guard and will not be considered unused",
288 FE->getName());
289 return false;
290 }
291 for (auto &Filter : Cfg.Diagnostics.Includes.IgnoreHeader) {
292 // Convert the path to Unix slashes and try to match against the filter.
293 llvm::SmallString<64> Path(Inc.Resolved);
294 llvm::sys::path::native(Path, llvm::sys::path::Style::posix);
295 if (Filter(Inc.Resolved)) {
296 dlog("{0} header is filtered out by the configuration", FE->getName());
297 return false;
298 }
299 }
300 return true;
301 }
302
303 // In case symbols are coming from non self-contained header, we need to find
304 // its first includer that is self-contained. This is the header users can
305 // include, so it will be responsible for bringing the symbols from given
306 // header into the scope.
307 FileID headerResponsible(FileID ID, const SourceManager &SM,
308 const IncludeStructure &Includes) {
309 // Unroll the chain of non self-contained headers until we find the one that
310 // can be included.
311 for (const FileEntry *FE = SM.getFileEntryForID(ID); ID != SM.getMainFileID();
312 FE = SM.getFileEntryForID(ID)) {
313 // If FE is nullptr, we consider it to be the responsible header.
314 if (!FE)
315 break;
316 auto HID = Includes.getID(FE);
317 assert(HID && "We're iterating over headers already existing in "
318 "IncludeStructure");
319 if (Includes.isSelfContained(*HID))
320 break;
321 // The header is not self-contained: put the responsibility for its symbols
322 // on its includer.
323 ID = SM.getFileID(SM.getIncludeLoc(ID));
324 }
325 return ID;
326 }
327
328 } // namespace
329
330 ReferencedLocations findReferencedLocations(ASTContext &Ctx, Preprocessor &PP,
331 const syntax::TokenBuffer *Tokens) {
332 trace::Span Tracer("IncludeCleaner::findReferencedLocations");
333 ReferencedLocations Result;
334 const auto &SM = Ctx.getSourceManager();
335 ReferencedLocationCrawler Crawler(Result, SM);
336 Crawler.TraverseAST(Ctx);
337 if (Tokens)
338 findReferencedMacros(SM, PP, Tokens, Result);
339 return Result;
340 }
341
342 ReferencedLocations findReferencedLocations(ParsedAST &AST) {
343 return findReferencedLocations(AST.getASTContext(), AST.getPreprocessor(),
344 &AST.getTokens());
345 }
346
347 ReferencedFiles findReferencedFiles(
348 const ReferencedLocations &Locs, const SourceManager &SM,
349 llvm::function_ref<FileID(FileID)> HeaderResponsible,
350 llvm::function_ref<std::optional<StringRef>(FileID)> UmbrellaHeader) {
351 std::vector<SourceLocation> Sorted{Locs.User.begin(), Locs.User.end()};
352 llvm::sort(Sorted); // Group by FileID.
353 ReferencedFilesBuilder Builder(SM);
354 for (auto It = Sorted.begin(); It < Sorted.end();) {
355 FileID FID = SM.getFileID(*It);
356 Builder.add(FID, *It);
357 // Cheaply skip over all the other locations from the same FileID.
358 // This avoids lots of redundant Loc->File lookups for the same file.
359 do
360 ++It;
361 while (It != Sorted.end() && SM.isInFileID(*It, FID));
362 }
363
364 // If a header is not self-contained, we consider its symbols a logical part
365 // of the including file. Therefore, mark the parents of all used
366 // non-self-contained FileIDs as used. Perform this on FileIDs rather than
367 // HeaderIDs, as each inclusion of a non-self-contained file is distinct.
368 llvm::DenseSet<FileID> UserFiles;
369 llvm::StringSet<> PublicHeaders;
370 for (FileID ID : Builder.Files) {
371 UserFiles.insert(HeaderResponsible(ID));
372 if (auto PublicHeader = UmbrellaHeader(ID)) {
373 PublicHeaders.insert(*PublicHeader);
374 }
375 }
376
377 llvm::DenseSet<tooling::stdlib::Header> StdlibFiles;
378 for (const auto &Symbol : Locs.Stdlib)
379 for (const auto &Header : Symbol.headers())
380 StdlibFiles.insert(Header);
381
382 return {std::move(UserFiles), std::move(StdlibFiles),
383 std::move(PublicHeaders)};
384 }
385
386 ReferencedFiles findReferencedFiles(const ReferencedLocations &Locs,
387 const IncludeStructure &Includes,
388 const CanonicalIncludes &CanonIncludes,
389 const SourceManager &SM) {
390 return findReferencedFiles(
391 Locs, SM,
392 [&SM, &Includes](FileID ID) {
393 return headerResponsible(ID, SM, Includes);
394 },
395 [&SM, &CanonIncludes](FileID ID) -> std::optional<StringRef> {
396 auto Entry = SM.getFileEntryRefForID(ID);
397 if (!Entry)
398 return std::nullopt;
399 auto PublicHeader = CanonIncludes.mapHeader(*Entry);
400 if (PublicHeader.empty())
401 return std::nullopt;
402 return PublicHeader;
403 });
404 }
405
406 std::vector<const Inclusion *>
407 getUnused(ParsedAST &AST,
408 const llvm::DenseSet<IncludeStructure::HeaderID> &ReferencedFiles,
409 const llvm::StringSet<> &ReferencedPublicHeaders) {
410 trace::Span Tracer("IncludeCleaner::getUnused");
411 const Config &Cfg = Config::current();
412 std::vector<const Inclusion *> Unused;
413 for (const Inclusion &MFI : AST.getIncludeStructure().MainFileIncludes) {
414 if (!MFI.HeaderID)
415 continue;
416 if (ReferencedPublicHeaders.contains(MFI.Written))
417 continue;
418 auto IncludeID = static_cast<IncludeStructure::HeaderID>(*MFI.HeaderID);
419 bool Used = ReferencedFiles.contains(IncludeID);
420 if (!Used && !mayConsiderUnused(MFI, AST, Cfg)) {
421 dlog("{0} was not used, but is not eligible to be diagnosed as unused",
422 MFI.Written);
423 continue;
424 }
425 if (!Used)
426 Unused.push_back(&MFI);
427 dlog("{0} is {1}", MFI.Written, Used ? "USED" : "UNUSED");
428 }
429 return Unused;
430 }
431
432 #ifndef NDEBUG
433 // Is FID a <built-in>, <scratch space> etc?
434 static bool isSpecialBuffer(FileID FID, const SourceManager &SM) {
435 const SrcMgr::FileInfo &FI = SM.getSLocEntry(FID).getFile();
436 return FI.getName().startswith("<");
437 }
438 #endif
439
440 llvm::DenseSet<IncludeStructure::HeaderID>
441 translateToHeaderIDs(const ReferencedFiles &Files,
442 const IncludeStructure &Includes,
443 const SourceManager &SM) {
444 trace::Span Tracer("IncludeCleaner::translateToHeaderIDs");
445 llvm::DenseSet<IncludeStructure::HeaderID> TranslatedHeaderIDs;
446 TranslatedHeaderIDs.reserve(Files.User.size());
447 for (FileID FID : Files.User) {
448 const FileEntry *FE = SM.getFileEntryForID(FID);
449 if (!FE) {
450 assert(isSpecialBuffer(FID, SM));
451 continue;
452 }
453 const auto File = Includes.getID(FE);
454 assert(File);
455 TranslatedHeaderIDs.insert(*File);
456 }
457 for (tooling::stdlib::Header StdlibUsed : Files.Stdlib)
458 for (auto HID : Includes.StdlibHeaders.lookup(StdlibUsed))
459 TranslatedHeaderIDs.insert(HID);
460 return TranslatedHeaderIDs;
461 }
462
463 // This is the original clangd-own implementation for computing unused
464 // #includes. Eventually it will be deprecated and replaced by the
465 // include-cleaner-lib-based implementation.
466 std::vector<const Inclusion *> computeUnusedIncludes(ParsedAST &AST) {
467 const auto &SM = AST.getSourceManager();
468
469 auto Refs = findReferencedLocations(AST);
470 auto ReferencedFiles =
471 findReferencedFiles(Refs, AST.getIncludeStructure(),
472 AST.getCanonicalIncludes(), AST.getSourceManager());
473 auto ReferencedHeaders =
474 translateToHeaderIDs(ReferencedFiles, AST.getIncludeStructure(), SM);
475 return getUnused(AST, ReferencedHeaders, ReferencedFiles.SpelledUmbrellas);
476 }
477 std::vector<const Inclusion *> computeUnusedIncludesExperimental(ParsedAST &AST) {
478 const auto &SM = AST.getSourceManager();
479 const auto &Includes = AST.getIncludeStructure();
480 // FIXME: this map should probably be in IncludeStructure.
481 llvm::StringMap<llvm::SmallVector<IncludeStructure::HeaderID>> BySpelling;
482 for (const auto &Inc : Includes.MainFileIncludes) {
483 if (Inc.HeaderID)
484 BySpelling.try_emplace(Inc.Written)
485 .first->second.push_back(
486 static_cast<IncludeStructure::HeaderID>(*Inc.HeaderID));
487 }
488 // FIXME: !!this is a hacky way to collect macro references.
489 std::vector<include_cleaner::SymbolReference> Macros;
490 auto& PP = AST.getPreprocessor();
491 for (const syntax::Token &Tok :
492 AST.getTokens().spelledTokens(SM.getMainFileID())) {
493 auto Macro = locateMacroAt(Tok, PP);
494 if (!Macro)
495 continue;
496 if (auto DefLoc = Macro->Info->getDefinitionLoc(); DefLoc.isValid())
497 Macros.push_back(
498 {Tok.location(),
499 include_cleaner::Macro{/*Name=*/PP.getIdentifierInfo(Tok.text(SM)),
500 DefLoc},
501 include_cleaner::RefType::Explicit});
502 }
503 llvm::DenseSet<IncludeStructure::HeaderID> Used;
504 include_cleaner::walkUsed(
505 AST.getLocalTopLevelDecls(), /*MacroRefs=*/Macros,
506 AST.getPragmaIncludes(), SM,
507 [&](const include_cleaner::SymbolReference &Ref,
508 llvm::ArrayRef<include_cleaner::Header> Providers) {
509 for (const auto &H : Providers) {
510 switch (H.kind()) {
511 case include_cleaner::Header::Physical:
512 if (auto HeaderID = Includes.getID(H.physical()))
513 Used.insert(*HeaderID);
514 break;
515 case include_cleaner::Header::Standard:
516 for (auto HeaderID : Includes.StdlibHeaders.lookup(H.standard()))
517 Used.insert(HeaderID);
518 break;
519 case include_cleaner::Header::Verbatim:
520 for (auto HeaderID : BySpelling.lookup(H.verbatim()))
521 Used.insert(HeaderID);
522 break;
523 }
524 }
525 });
526 return getUnused(AST, Used, /*ReferencedPublicHeaders*/{});
527 }
528
529 std::vector<Diag> issueUnusedIncludesDiagnostics(ParsedAST &AST,
530 llvm::StringRef Code) {
531 const Config &Cfg = Config::current();
532 if (Cfg.Diagnostics.UnusedIncludes == Config::UnusedIncludesPolicy::None ||
533 Cfg.Diagnostics.SuppressAll ||
534 Cfg.Diagnostics.Suppress.contains("unused-includes"))
535 return {};
536 // Interaction is only polished for C/CPP.
537 if (AST.getLangOpts().ObjC)
538 return {};
539 trace::Span Tracer("IncludeCleaner::issueUnusedIncludesDiagnostics");
540 std::vector<Diag> Result;
541 std::string FileName =
542 AST.getSourceManager()
543 .getFileEntryRefForID(AST.getSourceManager().getMainFileID())
544 ->getName()
545 .str();
546 const auto &UnusedIncludes =
547 Cfg.Diagnostics.UnusedIncludes == Config::UnusedIncludesPolicy::Experiment
548 ? computeUnusedIncludesExperimental(AST)
549 : computeUnusedIncludes(AST);
550 for (const auto *Inc : UnusedIncludes) {
551 Diag D;
552 D.Message =
553 llvm::formatv("included header {0} is not used directly",
554 llvm::sys::path::filename(
555 Inc->Written.substr(1, Inc->Written.size() - 2),
556 llvm::sys::path::Style::posix));
557 D.Name = "unused-includes";
558 D.Source = Diag::DiagSource::Clangd;
559 D.File = FileName;
560 D.Severity = DiagnosticsEngine::Warning;
561 D.Tags.push_back(Unnecessary);
562 D.Range = getDiagnosticRange(Code, Inc->HashOffset);
563 // FIXME(kirillbobyrev): Removing inclusion might break the code if the
564 // used headers are only reachable transitively through this one. Suggest
565 // including them directly instead.
566 // FIXME(kirillbobyrev): Add fix suggestion for adding IWYU pragmas
567 // (keep/export) remove the warning once we support IWYU pragmas.
568 D.Fixes.emplace_back();
569 D.Fixes.back().Message = "remove #include directive";
570 D.Fixes.back().Edits.emplace_back();
571 D.Fixes.back().Edits.back().range.start.line = Inc->HashLine;
572 D.Fixes.back().Edits.back().range.end.line = Inc->HashLine + 1;
573 D.InsideMainFile = true;
574 Result.push_back(std::move(D));
575 }
576 return Result;
577 }
578
579 } // namespace clangd
580 } // namespace clang