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