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