1//===--- Record.cpp - Record compiler events ------------------------------===//
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 "clang-include-cleaner/Record.h"
10#include "clang-include-cleaner/Types.h"
11#include "clang/AST/ASTConsumer.h"
12#include "clang/AST/ASTContext.h"
13#include "clang/AST/DeclGroup.h"
14#include "clang/Basic/FileEntry.h"
15#include "clang/Basic/FileManager.h"
16#include "clang/Basic/LLVM.h"
17#include "clang/Basic/SourceLocation.h"
18#include "clang/Basic/SourceManager.h"
19#include "clang/Basic/Specifiers.h"
20#include "clang/Frontend/CompilerInstance.h"
21#include "clang/Lex/DirectoryLookup.h"
22#include "clang/Lex/MacroInfo.h"
23#include "clang/Lex/PPCallbacks.h"
24#include "clang/Lex/Preprocessor.h"
25#include "clang/Tooling/Inclusions/HeaderAnalysis.h"
26#include "clang/Tooling/Inclusions/StandardLibrary.h"
27#include "llvm/ADT/ArrayRef.h"
28#include "llvm/ADT/DenseMap.h"
29#include "llvm/ADT/STLExtras.h"
30#include "llvm/ADT/SmallSet.h"
31#include "llvm/ADT/SmallVector.h"
32#include "llvm/ADT/StringRef.h"
33#include "llvm/ADT/iterator_range.h"
34#include "llvm/Support/Allocator.h"
35#include "llvm/Support/Error.h"
36#include "llvm/Support/FileSystem/UniqueID.h"
37#include "llvm/Support/StringSaver.h"
38#include <algorithm>
39#include <assert.h>
40#include <memory>
41#include <optional>
42#include <set>
43#include <utility>
44#include <vector>
45
46namespace clang::include_cleaner {
47namespace {
48
49class PPRecorder : public PPCallbacks {
50public:
51 PPRecorder(RecordedPP &Recorded, const Preprocessor &PP)
52 : Recorded(Recorded), PP(PP), SM(PP.getSourceManager()) {
53 for (const auto &Dir : PP.getHeaderSearchInfo().search_dir_range())
54 if (Dir.getLookupType() == DirectoryLookup::LT_NormalDir)
55 Recorded.Includes.addSearchDirectory(Dir.getDirRef()->getName());
56 }
57
58 void FileChanged(SourceLocation Loc, FileChangeReason Reason,
59 SrcMgr::CharacteristicKind FileType,
60 FileID PrevFID) override {
61 Active = SM.isWrittenInMainFile(Loc);
62 }
63
64 void InclusionDirective(SourceLocation Hash, const Token &IncludeTok,
65 StringRef SpelledFilename, bool IsAngled,
66 CharSourceRange FilenameRange,
67 OptionalFileEntryRef File, StringRef SearchPath,
68 StringRef RelativePath, const Module *SuggestedModule,
69 bool ModuleImported,
70 SrcMgr::CharacteristicKind) override {
71 if (!Active)
72 return;
73
74 Include I;
75 I.HashLocation = Hash;
76 I.Resolved = File;
77 I.Line = SM.getSpellingLineNumber(Loc: Hash);
78 I.Spelled = SpelledFilename;
79 I.Angled = IsAngled;
80 Recorded.Includes.add(I);
81 }
82
83 void MacroExpands(const Token &MacroName, const MacroDefinition &MD,
84 SourceRange Range, const MacroArgs *Args) override {
85 if (!Active)
86 return;
87 recordMacroRef(Tok: MacroName, MI: *MD.getMacroInfo());
88 }
89
90 void MacroDefined(const Token &MacroName, const MacroDirective *MD) override {
91 if (!Active)
92 return;
93
94 const auto *MI = MD->getMacroInfo();
95 // The tokens of a macro definition could refer to a macro.
96 // Formally this reference isn't resolved until this macro is expanded,
97 // but we want to treat it as a reference anyway.
98 for (const auto &Tok : MI->tokens()) {
99 auto *II = Tok.getIdentifierInfo();
100 // Could this token be a reference to a macro? (Not param to this macro).
101 if (!II || !II->hadMacroDefinition() ||
102 llvm::is_contained(Range: MI->params(), Element: II))
103 continue;
104 if (const MacroInfo *MI = PP.getMacroInfo(II))
105 recordMacroRef(Tok, MI: *MI);
106 }
107 }
108
109 void MacroUndefined(const Token &MacroName, const MacroDefinition &MD,
110 const MacroDirective *) override {
111 if (!Active)
112 return;
113 if (const auto *MI = MD.getMacroInfo())
114 recordMacroRef(Tok: MacroName, MI: *MI);
115 }
116
117 void Ifdef(SourceLocation Loc, const Token &MacroNameTok,
118 const MacroDefinition &MD) override {
119 if (!Active)
120 return;
121 if (const auto *MI = MD.getMacroInfo())
122 recordMacroRef(Tok: MacroNameTok, MI: *MI, RT: RefType::Ambiguous);
123 }
124
125 void Ifndef(SourceLocation Loc, const Token &MacroNameTok,
126 const MacroDefinition &MD) override {
127 if (!Active)
128 return;
129 if (const auto *MI = MD.getMacroInfo())
130 recordMacroRef(Tok: MacroNameTok, MI: *MI, RT: RefType::Ambiguous);
131 }
132
133 using PPCallbacks::Elifdef;
134 using PPCallbacks::Elifndef;
135 void Elifdef(SourceLocation Loc, const Token &MacroNameTok,
136 const MacroDefinition &MD) override {
137 if (!Active)
138 return;
139 if (const auto *MI = MD.getMacroInfo())
140 recordMacroRef(Tok: MacroNameTok, MI: *MI, RT: RefType::Ambiguous);
141 }
142 void Elifndef(SourceLocation Loc, const Token &MacroNameTok,
143 const MacroDefinition &MD) override {
144 if (!Active)
145 return;
146 if (const auto *MI = MD.getMacroInfo())
147 recordMacroRef(Tok: MacroNameTok, MI: *MI, RT: RefType::Ambiguous);
148 }
149
150 void Defined(const Token &MacroNameTok, const MacroDefinition &MD,
151 SourceRange Range) override {
152 if (!Active)
153 return;
154 if (const auto *MI = MD.getMacroInfo())
155 recordMacroRef(Tok: MacroNameTok, MI: *MI, RT: RefType::Ambiguous);
156 }
157
158private:
159 void recordMacroRef(const Token &Tok, const MacroInfo &MI,
160 RefType RT = RefType::Explicit) {
161 if (MI.isBuiltinMacro())
162 return; // __FILE__ is not a reference.
163 Recorded.MacroReferences.push_back(
164 x: SymbolReference{.Target: Macro{.Name: Tok.getIdentifierInfo(), .Definition: MI.getDefinitionLoc()},
165 .RefLocation: Tok.getLocation(), .RT: RT});
166 }
167
168 bool Active = false;
169 RecordedPP &Recorded;
170 const Preprocessor &PP;
171 const SourceManager &SM;
172};
173
174} // namespace
175
176class PragmaIncludes::RecordPragma : public PPCallbacks, public CommentHandler {
177public:
178 RecordPragma(const CompilerInstance &CI, PragmaIncludes *Out)
179 : RecordPragma(CI.getPreprocessor(), Out) {}
180 RecordPragma(const Preprocessor &P, PragmaIncludes *Out)
181 : SM(P.getSourceManager()), HeaderInfo(P.getHeaderSearchInfo()), Out(Out),
182 Arena(std::make_shared<llvm::BumpPtrAllocator>()),
183 UniqueStrings(*Arena) {}
184
185 void FileChanged(SourceLocation Loc, FileChangeReason Reason,
186 SrcMgr::CharacteristicKind FileType,
187 FileID PrevFID) override {
188 InMainFile = SM.isWrittenInMainFile(Loc);
189
190 if (Reason == PPCallbacks::ExitFile) {
191 // At file exit time HeaderSearchInfo is valid and can be used to
192 // determine whether the file was a self-contained header or not.
193 if (OptionalFileEntryRef FE = SM.getFileEntryRefForID(FID: PrevFID)) {
194 if (tooling::isSelfContainedHeader(FE: *FE, SM, HeaderInfo))
195 Out->NonSelfContainedFiles.erase(V: FE->getUniqueID());
196 else
197 Out->NonSelfContainedFiles.insert(V: FE->getUniqueID());
198 }
199 }
200 }
201
202 void EndOfMainFile() override {
203 for (auto &It : Out->IWYUExportBy) {
204 llvm::sort(C&: It.getSecond());
205 It.getSecond().erase(
206 CS: std::unique(first: It.getSecond().begin(), last: It.getSecond().end()),
207 CE: It.getSecond().end());
208 }
209 Out->Arena.emplace_back(args: std::move(Arena));
210 }
211
212 void InclusionDirective(SourceLocation HashLoc, const Token &IncludeTok,
213 llvm::StringRef FileName, bool IsAngled,
214 CharSourceRange /*FilenameRange*/,
215 OptionalFileEntryRef File,
216 llvm::StringRef /*SearchPath*/,
217 llvm::StringRef /*RelativePath*/,
218 const clang::Module * /*SuggestedModule*/,
219 bool /*ModuleImported*/,
220 SrcMgr::CharacteristicKind FileKind) override {
221 FileID HashFID = SM.getFileID(SpellingLoc: HashLoc);
222 int HashLine = SM.getLineNumber(FID: HashFID, FilePos: SM.getFileOffset(SpellingLoc: HashLoc));
223 std::optional<Header> IncludedHeader;
224 if (IsAngled)
225 if (auto StandardHeader =
226 tooling::stdlib::Header::named(Name: "<" + FileName.str() + ">")) {
227 IncludedHeader = *StandardHeader;
228 }
229 if (!IncludedHeader && File)
230 IncludedHeader = *File;
231 checkForExport(IncludingFile: HashFID, HashLine, IncludedHeader: std::move(IncludedHeader), IncludedFile: File);
232 checkForKeep(HashLine, IncludedFile: File);
233 }
234
235 void checkForExport(FileID IncludingFile, int HashLine,
236 std::optional<Header> IncludedHeader,
237 OptionalFileEntryRef IncludedFile) {
238 if (ExportStack.empty())
239 return;
240 auto &Top = ExportStack.back();
241 if (Top.SeenAtFile != IncludingFile)
242 return;
243 // Make sure current include is covered by the export pragma.
244 if ((Top.Block && HashLine > Top.SeenAtLine) ||
245 Top.SeenAtLine == HashLine) {
246 if (IncludedFile)
247 Out->IWYUExportBy[IncludedFile->getUniqueID()].push_back(Elt: Top.Path);
248 if (IncludedHeader && IncludedHeader->kind() == Header::Standard)
249 Out->StdIWYUExportBy[IncludedHeader->standard()].push_back(Elt: Top.Path);
250 // main-file #include with export pragma should never be removed.
251 if (Top.SeenAtFile == SM.getMainFileID() && IncludedFile)
252 Out->ShouldKeep.insert(V: IncludedFile->getUniqueID());
253 }
254 if (!Top.Block) // Pop immediately for single-line export pragma.
255 ExportStack.pop_back();
256 }
257
258 void checkForKeep(int HashLine, OptionalFileEntryRef IncludedFile) {
259 if (!InMainFile || KeepStack.empty())
260 return;
261 KeepPragma &Top = KeepStack.back();
262 // Check if the current include is covered by a keep pragma.
263 if (IncludedFile && ((Top.Block && HashLine > Top.SeenAtLine) ||
264 Top.SeenAtLine == HashLine)) {
265 Out->ShouldKeep.insert(V: IncludedFile->getUniqueID());
266 }
267
268 if (!Top.Block)
269 KeepStack.pop_back(); // Pop immediately for single-line keep pragma.
270 }
271
272 bool HandleComment(Preprocessor &PP, SourceRange Range) override {
273 auto &SM = PP.getSourceManager();
274 auto Pragma =
275 tooling::parseIWYUPragma(Text: SM.getCharacterData(SL: Range.getBegin()));
276 if (!Pragma)
277 return false;
278
279 auto [CommentFID, CommentOffset] = SM.getDecomposedLoc(Loc: Range.getBegin());
280 int CommentLine = SM.getLineNumber(FID: CommentFID, FilePos: CommentOffset);
281
282 if (InMainFile) {
283 if (Pragma->starts_with(Prefix: "keep")) {
284 KeepStack.push_back(x: {.SeenAtLine: CommentLine, .Block: false});
285 } else if (Pragma->starts_with(Prefix: "begin_keep")) {
286 KeepStack.push_back(x: {.SeenAtLine: CommentLine, .Block: true});
287 } else if (Pragma->starts_with(Prefix: "end_keep") && !KeepStack.empty()) {
288 assert(KeepStack.back().Block);
289 KeepStack.pop_back();
290 }
291 }
292
293 auto FE = SM.getFileEntryRefForID(FID: CommentFID);
294 if (!FE) {
295 // This can only happen when the buffer was registered virtually into
296 // SourceManager and FileManager has no idea about it. In such a scenario,
297 // that file cannot be discovered by HeaderSearch, therefore no "explicit"
298 // includes for that file.
299 return false;
300 }
301 auto CommentUID = FE->getUniqueID();
302 if (Pragma->consume_front(Prefix: "private")) {
303 StringRef PublicHeader;
304 if (Pragma->consume_front(Prefix: ", include ")) {
305 // We always insert using the spelling from the pragma.
306 PublicHeader =
307 save(S: Pragma->starts_with(Prefix: "<") || Pragma->starts_with(Prefix: "\"")
308 ? (*Pragma)
309 : ("\"" + *Pragma + "\"").str());
310 }
311 Out->IWYUPublic.insert(KV: {CommentUID, PublicHeader});
312 return false;
313 }
314 if (Pragma->consume_front(Prefix: "always_keep")) {
315 Out->ShouldKeep.insert(V: CommentUID);
316 return false;
317 }
318 auto Filename = FE->getName();
319 // Record export pragma.
320 if (Pragma->starts_with(Prefix: "export")) {
321 ExportStack.push_back(x: {.SeenAtLine: CommentLine, .SeenAtFile: CommentFID, .Path: save(S: Filename), .Block: false});
322 } else if (Pragma->starts_with(Prefix: "begin_exports")) {
323 ExportStack.push_back(x: {.SeenAtLine: CommentLine, .SeenAtFile: CommentFID, .Path: save(S: Filename), .Block: true});
324 } else if (Pragma->starts_with(Prefix: "end_exports")) {
325 // FIXME: be robust on unmatching cases. We should only pop the stack if
326 // the begin_exports and end_exports is in the same file.
327 if (!ExportStack.empty()) {
328 assert(ExportStack.back().Block);
329 ExportStack.pop_back();
330 }
331 }
332 return false;
333 }
334
335private:
336 StringRef save(llvm::StringRef S) { return UniqueStrings.save(S); }
337
338 bool InMainFile = false;
339 const SourceManager &SM;
340 const HeaderSearch &HeaderInfo;
341 PragmaIncludes *Out;
342 std::shared_ptr<llvm::BumpPtrAllocator> Arena;
343 /// Intern table for strings. Contents are on the arena.
344 llvm::StringSaver UniqueStrings;
345
346 struct ExportPragma {
347 // The line number where we saw the begin_exports or export pragma.
348 int SeenAtLine = 0; // 1-based line number.
349 // The file where we saw the pragma.
350 FileID SeenAtFile;
351 // Name (per FileEntry::getName()) of the file SeenAtFile.
352 StringRef Path;
353 // true if it is a block begin/end_exports pragma; false if it is a
354 // single-line export pragma.
355 bool Block = false;
356 };
357 // A stack for tracking all open begin_exports or single-line export.
358 std::vector<ExportPragma> ExportStack;
359
360 struct KeepPragma {
361 // The line number where we saw the begin_keep or keep pragma.
362 int SeenAtLine = 0; // 1-based line number.
363 // true if it is a block begin/end_keep pragma; false if it is a
364 // single-line keep pragma.
365 bool Block = false;
366 };
367 // A stack for tracking all open begin_keep pragmas or single-line keeps.
368 std::vector<KeepPragma> KeepStack;
369};
370
371void PragmaIncludes::record(const CompilerInstance &CI) {
372 auto Record = std::make_unique<RecordPragma>(args: CI, args: this);
373 CI.getPreprocessor().addCommentHandler(Handler: Record.get());
374 CI.getPreprocessor().addPPCallbacks(C: std::move(Record));
375}
376
377void PragmaIncludes::record(Preprocessor &P) {
378 auto Record = std::make_unique<RecordPragma>(args&: P, args: this);
379 P.addCommentHandler(Handler: Record.get());
380 P.addPPCallbacks(C: std::move(Record));
381}
382
383llvm::StringRef PragmaIncludes::getPublic(const FileEntry *F) const {
384 auto It = IWYUPublic.find(Val: F->getUniqueID());
385 if (It == IWYUPublic.end())
386 return "";
387 return It->getSecond();
388}
389
390static llvm::SmallVector<FileEntryRef>
391toFileEntries(llvm::ArrayRef<StringRef> FileNames, FileManager &FM) {
392 llvm::SmallVector<FileEntryRef> Results;
393
394 for (auto FName : FileNames) {
395 // FIMXE: log the failing cases?
396 if (auto FE = FM.getOptionalFileRef(Filename: FName))
397 Results.push_back(Elt: *FE);
398 }
399 return Results;
400}
401llvm::SmallVector<FileEntryRef>
402PragmaIncludes::getExporters(const FileEntry *File, FileManager &FM) const {
403 auto It = IWYUExportBy.find(Val: File->getUniqueID());
404 if (It == IWYUExportBy.end())
405 return {};
406
407 return toFileEntries(FileNames: It->getSecond(), FM);
408}
409llvm::SmallVector<FileEntryRef>
410PragmaIncludes::getExporters(tooling::stdlib::Header StdHeader,
411 FileManager &FM) const {
412 auto It = StdIWYUExportBy.find(Val: StdHeader);
413 if (It == StdIWYUExportBy.end())
414 return {};
415 return toFileEntries(FileNames: It->getSecond(), FM);
416}
417
418bool PragmaIncludes::isSelfContained(const FileEntry *FE) const {
419 return !NonSelfContainedFiles.contains(V: FE->getUniqueID());
420}
421
422bool PragmaIncludes::isPrivate(const FileEntry *FE) const {
423 return IWYUPublic.contains(Val: FE->getUniqueID());
424}
425
426bool PragmaIncludes::shouldKeep(const FileEntry *FE) const {
427 return ShouldKeep.contains(V: FE->getUniqueID()) ||
428 NonSelfContainedFiles.contains(V: FE->getUniqueID());
429}
430
431namespace {
432template <typename T> bool isImplicitTemplateSpecialization(const Decl *D) {
433 if (const auto *TD = dyn_cast<T>(D))
434 return TD->getTemplateSpecializationKind() == TSK_ImplicitInstantiation;
435 return false;
436}
437} // namespace
438
439std::unique_ptr<ASTConsumer> RecordedAST::record() {
440 class Recorder : public ASTConsumer {
441 RecordedAST *Out;
442
443 public:
444 Recorder(RecordedAST *Out) : Out(Out) {}
445 void Initialize(ASTContext &Ctx) override { Out->Ctx = &Ctx; }
446 bool HandleTopLevelDecl(DeclGroupRef DG) override {
447 const auto &SM = Out->Ctx->getSourceManager();
448 for (Decl *D : DG) {
449 if (!SM.isWrittenInMainFile(Loc: SM.getExpansionLoc(Loc: D->getLocation())))
450 continue;
451 if (isImplicitTemplateSpecialization<FunctionDecl>(D) ||
452 isImplicitTemplateSpecialization<CXXRecordDecl>(D) ||
453 isImplicitTemplateSpecialization<VarDecl>(D))
454 continue;
455 // FIXME: Filter out certain Obj-C as well.
456 Out->Roots.push_back(x: D);
457 }
458 return ASTConsumer::HandleTopLevelDecl(D: DG);
459 }
460 };
461
462 return std::make_unique<Recorder>(args: this);
463}
464
465std::unique_ptr<PPCallbacks> RecordedPP::record(const Preprocessor &PP) {
466 return std::make_unique<PPRecorder>(args&: *this, args: PP);
467}
468
469} // namespace clang::include_cleaner
470

source code of clang-tools-extra/include-cleaner/lib/Record.cpp