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