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