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