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
37namespace clang::include_cleaner {
38
39namespace {
40bool shouldIgnoreMacroReference(const Preprocessor &PP, const Macro &M) {
41 auto *MI = PP.getMacroInfo(II: 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(Tok: 0).getIdentifierInfo() == M.Name;
49}
50} // namespace
51
52void 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(SpellingLoc: 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, .RefLocation: Loc, .RT: 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(Loc: SM.getSpellingLoc(Loc: MacroRef.RefLocation)) ||
73 shouldIgnoreMacroReference(PP, M: MacroRef.Target.macro()))
74 continue;
75 CB(MacroRef, headersForSymbol(S: MacroRef.Target, PP, PI));
76 }
77}
78
79AnalysisResults
80analyze(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(FID: 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 CB: [&](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(V: 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 Input: {.H: Providers.front(), .HS: PP.getHeaderSearchInfo(), .Main: MainFile});
118 for (const Include *I : Inc.match(H: Header{Spelling})) {
119 Used.insert(V: I);
120 Satisfied = true;
121 }
122 if (!Satisfied)
123 Missing.try_emplace(Key: std::move(Spelling), Args: Providers.front());
124 });
125
126 AnalysisResults Results;
127 for (const Include &I : Inc.all()) {
128 if (Used.contains(V: &I) || !I.Resolved ||
129 HeaderFilter(I.Resolved->getName()) ||
130 I.Resolved->getDir() == ResourceDir)
131 continue;
132 if (PI) {
133 if (PI->shouldKeep(FE: *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(File: *I.Resolved); !PHeader.empty()) {
138 PHeader = PHeader.trim(Chars: "<>\"");
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(Suffix: PHeader))
143 continue;
144 }
145 }
146 Results.Unused.push_back(x: &I);
147 }
148 for (auto &E : Missing)
149 Results.Missing.emplace_back(args: E.first().str(), args&: E.second);
150 llvm::sort(C&: Results.Missing);
151 return Results;
152}
153
154std::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(Err: R.add(R: tooling::Replacement(FileName, UINT_MAX, 1, I->quote())));
162 for (auto &[Spelled, _] : Results.Missing)
163 cantFail(Err: R.add(
164 R: tooling::Replacement(FileName, UINT_MAX, 0, "#include " + Spelled)));
165 // "cleanup" actually turns the UINT_MAX replacements into concrete edits.
166 auto Positioned = cantFail(ValOrErr: format::cleanupAroundReplacements(Code, Replaces: R, Style));
167 return cantFail(ValOrErr: tooling::applyAllReplacements(Code, Replaces: Positioned));
168}
169
170} // namespace clang::include_cleaner
171

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