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

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