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