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 "Protocol.h"
12 #include "SourceCode.h"
13 #include "support/Logger.h"
14 #include "clang/AST/RecursiveASTVisitor.h"
15 #include "clang/Basic/SourceLocation.h"
16 #include "llvm/Support/FormatVariadic.h"
17 #include "llvm/Support/Path.h"
18 
19 namespace clang {
20 namespace clangd {
21 namespace {
22 
23 /// Crawler traverses the AST and feeds in the locations of (sometimes
24 /// implicitly) used symbols into \p Result.
25 class ReferencedLocationCrawler
26     : public RecursiveASTVisitor<ReferencedLocationCrawler> {
27 public:
28   ReferencedLocationCrawler(ReferencedLocations &Result) : Result(Result) {}
29 
30   bool VisitDeclRefExpr(DeclRefExpr *DRE) {
31     add(DRE->getDecl());
32     add(DRE->getFoundDecl());
33     return true;
34   }
35 
36   bool VisitMemberExpr(MemberExpr *ME) {
37     add(ME->getMemberDecl());
38     add(ME->getFoundDecl().getDecl());
39     return true;
40   }
41 
42   bool VisitTagType(TagType *TT) {
43     add(TT->getDecl());
44     return true;
45   }
46 
47   bool VisitFunctionDecl(FunctionDecl *FD) {
48     // Function definition will require redeclarations to be included.
49     if (FD == FD->getDefinition())
50       add(FD);
51     return true;
52   }
53 
54   bool VisitCXXConstructExpr(CXXConstructExpr *CCE) {
55     add(CCE->getConstructor());
56     return true;
57   }
58 
59   bool VisitTemplateSpecializationType(TemplateSpecializationType *TST) {
60     if (isNew(TST)) {
61       add(TST->getTemplateName().getAsTemplateDecl()); // Primary template.
62       add(TST->getAsCXXRecordDecl());                  // Specialization
63     }
64     return true;
65   }
66 
67   bool VisitTypedefType(TypedefType *TT) {
68     add(TT->getDecl());
69     return true;
70   }
71 
72   // Consider types of any subexpression used, even if the type is not named.
73   // This is helpful in getFoo().bar(), where Foo must be complete.
74   // FIXME(kirillbobyrev): Should we tweak this? It may not be desirable to
75   // consider types "used" when they are not directly spelled in code.
76   bool VisitExpr(Expr *E) {
77     TraverseType(E->getType());
78     return true;
79   }
80 
81   bool TraverseType(QualType T) {
82     if (isNew(T.getTypePtrOrNull())) { // don't care about quals
83       Base::TraverseType(T);
84     }
85     return true;
86   }
87 
88   bool VisitUsingDecl(UsingDecl *D) {
89     for (const auto *Shadow : D->shadows()) {
90       add(Shadow->getTargetDecl());
91     }
92     return true;
93   }
94 
95   // Enums may be usefully forward-declared as *complete* types by specifying
96   // an underlying type. In this case, the definition should see the declaration
97   // so they can be checked for compatibility.
98   bool VisitEnumDecl(EnumDecl *D) {
99     if (D->isThisDeclarationADefinition() && D->getIntegerTypeSourceInfo())
100       add(D);
101     return true;
102   }
103 
104 private:
105   using Base = RecursiveASTVisitor<ReferencedLocationCrawler>;
106 
107   void add(const Decl *D) {
108     if (!D || !isNew(D->getCanonicalDecl())) {
109       return;
110     }
111     for (const Decl *Redecl : D->redecls()) {
112       Result.insert(Redecl->getLocation());
113     }
114   }
115 
116   bool isNew(const void *P) { return P && Visited.insert(P).second; }
117 
118   ReferencedLocations &Result;
119   llvm::DenseSet<const void *> Visited;
120 };
121 
122 // Given a set of referenced FileIDs, determines all the potentially-referenced
123 // files and macros by traversing expansion/spelling locations of macro IDs.
124 // This is used to map the referenced SourceLocations onto real files.
125 struct ReferencedFiles {
126   ReferencedFiles(const SourceManager &SM) : SM(SM) {}
127   llvm::DenseSet<FileID> Files;
128   llvm::DenseSet<FileID> Macros;
129   const SourceManager &SM;
130 
131   void add(SourceLocation Loc) { add(SM.getFileID(Loc), Loc); }
132 
133   void add(FileID FID, SourceLocation Loc) {
134     if (FID.isInvalid())
135       return;
136     assert(SM.isInFileID(Loc, FID));
137     if (Loc.isFileID()) {
138       Files.insert(FID);
139       return;
140     }
141     // Don't process the same macro FID twice.
142     if (!Macros.insert(FID).second)
143       return;
144     const auto &Exp = SM.getSLocEntry(FID).getExpansion();
145     // For token pasting operator in macros, spelling and expansion locations
146     // can be within a temporary buffer that Clang creates (scratch space or
147     // ScratchBuffer). That is not a real file we can include.
148     if (!SM.isWrittenInScratchSpace(Exp.getSpellingLoc()))
149       add(Exp.getSpellingLoc());
150     if (!SM.isWrittenInScratchSpace(Exp.getExpansionLocStart()))
151       add(Exp.getExpansionLocStart());
152     if (!SM.isWrittenInScratchSpace(Exp.getExpansionLocEnd()))
153       add(Exp.getExpansionLocEnd());
154   }
155 };
156 
157 // Returns the range starting at '#' and ending at EOL. Escaped newlines are not
158 // handled.
159 clangd::Range getDiagnosticRange(llvm::StringRef Code, unsigned HashOffset) {
160   clangd::Range Result;
161   Result.end = Result.start = offsetToPosition(Code, HashOffset);
162 
163   // Span the warning until the EOL or EOF.
164   Result.end.character +=
165       lspLength(Code.drop_front(HashOffset).take_until([](char C) {
166         return C == '\n' || C == '\r';
167       }));
168   return Result;
169 }
170 
171 } // namespace
172 
173 ReferencedLocations findReferencedLocations(ParsedAST &AST) {
174   ReferencedLocations Result;
175   ReferencedLocationCrawler Crawler(Result);
176   Crawler.TraverseAST(AST.getASTContext());
177   // FIXME(kirillbobyrev): Handle macros.
178   return Result;
179 }
180 
181 llvm::DenseSet<FileID>
182 findReferencedFiles(const llvm::DenseSet<SourceLocation> &Locs,
183                     const SourceManager &SM) {
184   std::vector<SourceLocation> Sorted{Locs.begin(), Locs.end()};
185   llvm::sort(Sorted); // Group by FileID.
186   ReferencedFiles Result(SM);
187   for (auto It = Sorted.begin(); It < Sorted.end();) {
188     FileID FID = SM.getFileID(*It);
189     Result.add(FID, *It);
190     // Cheaply skip over all the other locations from the same FileID.
191     // This avoids lots of redundant Loc->File lookups for the same file.
192     do
193       ++It;
194     while (It != Sorted.end() && SM.isInFileID(*It, FID));
195   }
196   return std::move(Result.Files);
197 }
198 
199 std::vector<const Inclusion *>
200 getUnused(const IncludeStructure &Structure,
201           const llvm::DenseSet<IncludeStructure::HeaderID> &ReferencedFiles) {
202   std::vector<const Inclusion *> Unused;
203   for (const Inclusion &MFI : Structure.MainFileIncludes) {
204     // FIXME: Skip includes that are not self-contained.
205     if (!MFI.HeaderID) {
206       elog("File {0} not found.", MFI.Written);
207       continue;
208     }
209     auto IncludeID = static_cast<IncludeStructure::HeaderID>(*MFI.HeaderID);
210     if (!ReferencedFiles.contains(IncludeID)) {
211       Unused.push_back(&MFI);
212     }
213     dlog("{0} is {1}", MFI.Written,
214          ReferencedFiles.contains(IncludeID) ? "USED" : "UNUSED");
215   }
216   return Unused;
217 }
218 
219 llvm::DenseSet<IncludeStructure::HeaderID>
220 translateToHeaderIDs(const llvm::DenseSet<FileID> &Files,
221                      const IncludeStructure &Includes,
222                      const SourceManager &SM) {
223   llvm::DenseSet<IncludeStructure::HeaderID> TranslatedHeaderIDs;
224   TranslatedHeaderIDs.reserve(Files.size());
225   for (FileID FID : Files) {
226     const FileEntry *FE = SM.getFileEntryForID(FID);
227     assert(FE);
228     const auto File = Includes.getID(FE);
229     assert(File);
230     TranslatedHeaderIDs.insert(*File);
231   }
232   return TranslatedHeaderIDs;
233 }
234 
235 std::vector<const Inclusion *> computeUnusedIncludes(ParsedAST &AST) {
236   const auto &SM = AST.getSourceManager();
237 
238   auto Refs = findReferencedLocations(AST);
239   auto ReferencedFiles = translateToHeaderIDs(findReferencedFiles(Refs, SM),
240                                               AST.getIncludeStructure(), SM);
241   return getUnused(AST.getIncludeStructure(), ReferencedFiles);
242 }
243 
244 std::vector<Diag> issueUnusedIncludesDiagnostics(ParsedAST &AST,
245                                                  llvm::StringRef Code) {
246   const Config &Cfg = Config::current();
247   if (Cfg.Diagnostics.UnusedIncludes != Config::UnusedIncludesPolicy::Strict ||
248       Cfg.Diagnostics.SuppressAll ||
249       Cfg.Diagnostics.Suppress.contains("unused-includes"))
250     return {};
251   std::vector<Diag> Result;
252   std::string FileName =
253       AST.getSourceManager()
254           .getFileEntryForID(AST.getSourceManager().getMainFileID())
255           ->getName()
256           .str();
257   for (const auto *Inc : computeUnusedIncludes(AST)) {
258     Diag D;
259     D.Message =
260         llvm::formatv("included header {0} is not used",
261                       llvm::sys::path::filename(
262                           Inc->Written.substr(1, Inc->Written.size() - 2),
263                           llvm::sys::path::Style::posix));
264     D.Name = "unused-includes";
265     D.Source = Diag::DiagSource::Clangd;
266     D.File = FileName;
267     D.Severity = DiagnosticsEngine::Warning;
268     D.Tags.push_back(Unnecessary);
269     D.Range = getDiagnosticRange(Code, Inc->HashOffset);
270     // FIXME(kirillbobyrev): Removing inclusion might break the code if the
271     // used headers are only reachable transitively through this one. Suggest
272     // including them directly instead.
273     // FIXME(kirillbobyrev): Add fix suggestion for adding IWYU pragmas
274     // (keep/export) remove the warning once we support IWYU pragmas.
275     D.Fixes.emplace_back();
276     D.Fixes.back().Message = "remove #include directive";
277     D.Fixes.back().Edits.emplace_back();
278     D.Fixes.back().Edits.back().range.start.line = Inc->HashLine;
279     D.Fixes.back().Edits.back().range.end.line = Inc->HashLine + 1;
280     D.InsideMainFile = true;
281     Result.push_back(std::move(D));
282   }
283   return Result;
284 }
285 
286 } // namespace clangd
287 } // namespace clang
288