1 //===--- Analysis.cpp -----------------------------------------------------===// 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/Analysis.h" 10 #include "AnalysisInternal.h" 11 #include "clang-include-cleaner/IncludeSpeller.h" 12 #include "clang-include-cleaner/Record.h" 13 #include "clang-include-cleaner/Types.h" 14 #include "clang/AST/Decl.h" 15 #include "clang/AST/DeclBase.h" 16 #include "clang/Basic/DirectoryEntry.h" 17 #include "clang/Basic/FileEntry.h" 18 #include "clang/Basic/SourceManager.h" 19 #include "clang/Format/Format.h" 20 #include "clang/Lex/HeaderSearch.h" 21 #include "clang/Lex/Preprocessor.h" 22 #include "clang/Tooling/Core/Replacement.h" 23 #include "clang/Tooling/Inclusions/StandardLibrary.h" 24 #include "llvm/ADT/ArrayRef.h" 25 #include "llvm/ADT/DenseSet.h" 26 #include "llvm/ADT/STLExtras.h" 27 #include "llvm/ADT/STLFunctionalExtras.h" 28 #include "llvm/ADT/SmallVector.h" 29 #include "llvm/ADT/StringMap.h" 30 #include "llvm/ADT/StringRef.h" 31 #include "llvm/Support/Error.h" 32 #include "llvm/Support/ErrorHandling.h" 33 #include <cassert> 34 #include <climits> 35 #include <string> 36 37 namespace clang::include_cleaner { 38 39 namespace { 40 bool shouldIgnoreMacroReference(const Preprocessor &PP, const Macro &M) { 41 auto *MI = PP.getMacroInfo(M.Name); 42 // Macros that expand to themselves are confusing from user's point of view. 43 // They usually aspect the usage to be attributed to the underlying decl and 44 // not the macro definition. So ignore such macros (e.g. std{in,out,err} are 45 // implementation defined macros, that just resolve to themselves in 46 // practice). 47 return MI && MI->getNumTokens() == 1 && MI->isObjectLike() && 48 MI->getReplacementToken(0).getIdentifierInfo() == M.Name; 49 } 50 } // namespace 51 52 void walkUsed(llvm::ArrayRef<Decl *> ASTRoots, 53 llvm::ArrayRef<SymbolReference> MacroRefs, 54 const PragmaIncludes *PI, const Preprocessor &PP, 55 UsedSymbolCB CB) { 56 const auto &SM = PP.getSourceManager(); 57 // This is duplicated in writeHTMLReport, changes should be mirrored there. 58 tooling::stdlib::Recognizer Recognizer; 59 for (auto *Root : ASTRoots) { 60 walkAST(*Root, [&](SourceLocation Loc, NamedDecl &ND, RefType RT) { 61 auto FID = SM.getFileID(SM.getSpellingLoc(Loc)); 62 if (FID != SM.getMainFileID() && FID != SM.getPreambleFileID()) 63 return; 64 // FIXME: Most of the work done here is repetitive. It might be useful to 65 // have a cache/batching. 66 SymbolReference SymRef{ND, Loc, RT}; 67 return CB(SymRef, headersForSymbol(ND, PP, PI)); 68 }); 69 } 70 for (const SymbolReference &MacroRef : MacroRefs) { 71 assert(MacroRef.Target.kind() == Symbol::Macro); 72 if (!SM.isWrittenInMainFile(SM.getSpellingLoc(MacroRef.RefLocation)) || 73 shouldIgnoreMacroReference(PP, MacroRef.Target.macro())) 74 continue; 75 CB(MacroRef, headersForSymbol(MacroRef.Target, PP, PI)); 76 } 77 } 78 79 AnalysisResults 80 analyze(llvm::ArrayRef<Decl *> ASTRoots, 81 llvm::ArrayRef<SymbolReference> MacroRefs, const Includes &Inc, 82 const PragmaIncludes *PI, const Preprocessor &PP, 83 llvm::function_ref<bool(llvm::StringRef)> HeaderFilter) { 84 auto &SM = PP.getSourceManager(); 85 const auto MainFile = *SM.getFileEntryRefForID(SM.getMainFileID()); 86 llvm::DenseSet<const Include *> Used; 87 llvm::StringMap<Header> Missing; 88 constexpr auto DefaultHeaderFilter = [](llvm::StringRef) { return false; }; 89 if (!HeaderFilter) 90 HeaderFilter = DefaultHeaderFilter; 91 OptionalDirectoryEntryRef ResourceDir = 92 PP.getHeaderSearchInfo().getModuleMap().getBuiltinDir(); 93 walkUsed(ASTRoots, MacroRefs, PI, PP, 94 [&](const SymbolReference &Ref, llvm::ArrayRef<Header> Providers) { 95 bool Satisfied = false; 96 for (const Header &H : Providers) { 97 if (H.kind() == Header::Physical && 98 (H.physical() == MainFile || 99 H.physical().getDir() == ResourceDir)) { 100 Satisfied = true; 101 } 102 for (const Include *I : Inc.match(H)) { 103 Used.insert(I); 104 Satisfied = true; 105 } 106 } 107 // Bail out if we can't (or need not) insert an include. 108 if (Satisfied || Providers.empty() || Ref.RT != RefType::Explicit) 109 return; 110 if (HeaderFilter(Providers.front().resolvedPath())) 111 return; 112 // Check if we have any headers with the same spelling, in edge 113 // cases like `#include_next "foo.h"`, the user can't ever 114 // include the physical foo.h, but can have a spelling that 115 // refers to it. 116 auto Spelling = spellHeader( 117 {Providers.front(), PP.getHeaderSearchInfo(), MainFile}); 118 for (const Include *I : Inc.match(Header{Spelling})) { 119 Used.insert(I); 120 Satisfied = true; 121 } 122 if (!Satisfied) 123 Missing.try_emplace(std::move(Spelling), Providers.front()); 124 }); 125 126 AnalysisResults Results; 127 for (const Include &I : Inc.all()) { 128 if (Used.contains(&I) || !I.Resolved || 129 HeaderFilter(I.Resolved->getName()) || 130 I.Resolved->getDir() == ResourceDir) 131 continue; 132 if (PI) { 133 if (PI->shouldKeep(*I.Resolved)) 134 continue; 135 // Check if main file is the public interface for a private header. If so 136 // we shouldn't diagnose it as unused. 137 if (auto PHeader = PI->getPublic(*I.Resolved); !PHeader.empty()) { 138 PHeader = PHeader.trim("<>\""); 139 // Since most private -> public mappings happen in a verbatim way, we 140 // check textually here. This might go wrong in presence of symlinks or 141 // header mappings. But that's not different than rest of the places. 142 if (MainFile.getName().ends_with(PHeader)) 143 continue; 144 } 145 } 146 Results.Unused.push_back(&I); 147 } 148 for (auto &E : Missing) 149 Results.Missing.emplace_back(E.first().str(), E.second); 150 llvm::sort(Results.Missing); 151 return Results; 152 } 153 154 std::string fixIncludes(const AnalysisResults &Results, 155 llvm::StringRef FileName, llvm::StringRef Code, 156 const format::FormatStyle &Style) { 157 assert(Style.isCpp() && "Only C++ style supports include insertions!"); 158 tooling::Replacements R; 159 // Encode insertions/deletions in the magic way clang-format understands. 160 for (const Include *I : Results.Unused) 161 cantFail(R.add(tooling::Replacement(FileName, UINT_MAX, 1, I->quote()))); 162 for (auto &[Spelled, _] : Results.Missing) 163 cantFail(R.add( 164 tooling::Replacement(FileName, UINT_MAX, 0, "#include " + Spelled))); 165 // "cleanup" actually turns the UINT_MAX replacements into concrete edits. 166 auto Positioned = cantFail(format::cleanupAroundReplacements(Code, R, Style)); 167 return cantFail(tooling::applyAllReplacements(Code, Positioned)); 168 } 169 170 } // namespace clang::include_cleaner 171