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 "support/Logger.h"
11 #include "clang/AST/RecursiveASTVisitor.h"
12 #include "clang/Basic/SourceLocation.h"
13 
14 namespace clang {
15 namespace clangd {
16 namespace {
17 
18 /// Crawler traverses the AST and feeds in the locations of (sometimes
19 /// implicitly) used symbols into \p Result.
20 class ReferencedLocationCrawler
21     : public RecursiveASTVisitor<ReferencedLocationCrawler> {
22 public:
23   ReferencedLocationCrawler(ReferencedLocations &Result) : Result(Result) {}
24 
25   bool VisitDeclRefExpr(DeclRefExpr *DRE) {
26     add(DRE->getDecl());
27     add(DRE->getFoundDecl());
28     return true;
29   }
30 
31   bool VisitMemberExpr(MemberExpr *ME) {
32     add(ME->getMemberDecl());
33     add(ME->getFoundDecl().getDecl());
34     return true;
35   }
36 
37   bool VisitTagType(TagType *TT) {
38     add(TT->getDecl());
39     return true;
40   }
41 
42   bool VisitCXXConstructExpr(CXXConstructExpr *CCE) {
43     add(CCE->getConstructor());
44     return true;
45   }
46 
47   bool VisitTemplateSpecializationType(TemplateSpecializationType *TST) {
48     if (isNew(TST)) {
49       add(TST->getTemplateName().getAsTemplateDecl()); // Primary template.
50       add(TST->getAsCXXRecordDecl());                  // Specialization
51     }
52     return true;
53   }
54 
55   bool VisitTypedefType(TypedefType *TT) {
56     add(TT->getDecl());
57     return true;
58   }
59 
60   // Consider types of any subexpression used, even if the type is not named.
61   // This is helpful in getFoo().bar(), where Foo must be complete.
62   // FIXME(kirillbobyrev): Should we tweak this? It may not be desirable to
63   // consider types "used" when they are not directly spelled in code.
64   bool VisitExpr(Expr *E) {
65     TraverseType(E->getType());
66     return true;
67   }
68 
69   bool TraverseType(QualType T) {
70     if (isNew(T.getTypePtrOrNull())) { // don't care about quals
71       Base::TraverseType(T);
72     }
73     return true;
74   }
75 
76   bool VisitUsingDecl(UsingDecl *D) {
77     for (const auto *Shadow : D->shadows()) {
78       add(Shadow->getTargetDecl());
79     }
80     return true;
81   }
82 
83 private:
84   using Base = RecursiveASTVisitor<ReferencedLocationCrawler>;
85 
86   void add(const Decl *D) {
87     if (!D || !isNew(D->getCanonicalDecl())) {
88       return;
89     }
90     for (const Decl *Redecl : D->redecls()) {
91       Result.insert(Redecl->getLocation());
92     }
93   }
94 
95   bool isNew(const void *P) { return P && Visited.insert(P).second; }
96 
97   ReferencedLocations &Result;
98   llvm::DenseSet<const void *> Visited;
99 };
100 
101 // Given a set of referenced FileIDs, determines all the potentially-referenced
102 // files and macros by traversing expansion/spelling locations of macro IDs.
103 // This is used to map the referenced SourceLocations onto real files.
104 struct ReferencedFiles {
105   ReferencedFiles(const SourceManager &SM) : SM(SM) {}
106   llvm::DenseSet<FileID> Files;
107   llvm::DenseSet<FileID> Macros;
108   const SourceManager &SM;
109 
110   void add(SourceLocation Loc) { add(SM.getFileID(Loc), Loc); }
111 
112   void add(FileID FID, SourceLocation Loc) {
113     if (FID.isInvalid())
114       return;
115     assert(SM.isInFileID(Loc, FID));
116     if (Loc.isFileID()) {
117       Files.insert(FID);
118       return;
119     }
120     // Don't process the same macro FID twice.
121     if (!Macros.insert(FID).second)
122       return;
123     const auto &Exp = SM.getSLocEntry(FID).getExpansion();
124     // For token pasting operator in macros, spelling and expansion locations
125     // can be within a temporary buffer that Clang creates (scratch space or
126     // ScratchBuffer). That is not a real file we can include.
127     if (!SM.isWrittenInScratchSpace(Exp.getSpellingLoc()))
128       add(Exp.getSpellingLoc());
129     if (!SM.isWrittenInScratchSpace(Exp.getExpansionLocStart()))
130       add(Exp.getExpansionLocStart());
131     if (!SM.isWrittenInScratchSpace(Exp.getExpansionLocEnd()))
132       add(Exp.getExpansionLocEnd());
133   }
134 };
135 
136 } // namespace
137 
138 ReferencedLocations findReferencedLocations(ParsedAST &AST) {
139   ReferencedLocations Result;
140   ReferencedLocationCrawler Crawler(Result);
141   Crawler.TraverseAST(AST.getASTContext());
142   // FIXME(kirillbobyrev): Handle macros.
143   return Result;
144 }
145 
146 llvm::DenseSet<FileID>
147 findReferencedFiles(const llvm::DenseSet<SourceLocation> &Locs,
148                     const SourceManager &SM) {
149   std::vector<SourceLocation> Sorted{Locs.begin(), Locs.end()};
150   llvm::sort(Sorted); // Group by FileID.
151   ReferencedFiles Result(SM);
152   for (auto It = Sorted.begin(); It < Sorted.end();) {
153     FileID FID = SM.getFileID(*It);
154     Result.add(FID, *It);
155     // Cheaply skip over all the other locations from the same FileID.
156     // This avoids lots of redundant Loc->File lookups for the same file.
157     do
158       ++It;
159     while (It != Sorted.end() && SM.isInFileID(*It, FID));
160   }
161   return std::move(Result.Files);
162 }
163 
164 std::vector<const Inclusion *>
165 getUnused(const IncludeStructure &Structure,
166           const llvm::DenseSet<IncludeStructure::HeaderID> &ReferencedFiles) {
167   std::vector<const Inclusion *> Unused;
168   for (const Inclusion &MFI : Structure.MainFileIncludes) {
169     // FIXME: Skip includes that are not self-contained.
170     if (!MFI.HeaderID) {
171       elog("File {0} not found.", MFI.Written);
172       continue;
173     }
174     auto IncludeID = static_cast<IncludeStructure::HeaderID>(*MFI.HeaderID);
175     if (!ReferencedFiles.contains(IncludeID)) {
176       Unused.push_back(&MFI);
177     }
178     dlog("{0} is {1}", MFI.Written,
179          ReferencedFiles.contains(IncludeID) ? "USED" : "UNUSED");
180   }
181   return Unused;
182 }
183 
184 llvm::DenseSet<IncludeStructure::HeaderID>
185 translateToHeaderIDs(const llvm::DenseSet<FileID> &Files,
186                      const IncludeStructure &Includes,
187                      const SourceManager &SM) {
188   llvm::DenseSet<IncludeStructure::HeaderID> TranslatedHeaderIDs;
189   TranslatedHeaderIDs.reserve(Files.size());
190   for (FileID FID : Files) {
191     const FileEntry *FE = SM.getFileEntryForID(FID);
192     assert(FE);
193     const auto File = Includes.getID(FE);
194     assert(File);
195     TranslatedHeaderIDs.insert(*File);
196   }
197   return TranslatedHeaderIDs;
198 }
199 
200 std::vector<const Inclusion *> computeUnusedIncludes(ParsedAST &AST) {
201   const auto &SM = AST.getSourceManager();
202 
203   auto Refs = findReferencedLocations(AST);
204   auto ReferencedFiles = translateToHeaderIDs(findReferencedFiles(Refs, SM),
205                                               AST.getIncludeStructure(), SM);
206   return getUnused(AST.getIncludeStructure(), ReferencedFiles);
207 }
208 
209 } // namespace clangd
210 } // namespace clang
211