1//===--- Types.h - Data structures for used-symbol analysis -------- C++-*-===//
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// Find referenced files is mostly a matter of translating:
10// AST Node => declaration => source location => file
11//
12// clang has types for these (DynTypedNode, Decl, SourceLocation, FileID), but
13// there are special cases: macros are not declarations, the concrete file where
14// a standard library symbol was defined doesn't matter, etc.
15//
16// We define some slightly more abstract sum types to handle these cases while
17// keeping the API clean. For example, Symbol may be a Decl AST node, a macro,
18// or a recognized standard library symbol.
19//
20//===----------------------------------------------------------------------===//
21
22#ifndef CLANG_INCLUDE_CLEANER_TYPES_H
23#define CLANG_INCLUDE_CLEANER_TYPES_H
24
25#include "clang/Basic/FileEntry.h"
26#include "clang/Basic/SourceLocation.h"
27#include "clang/Tooling/Inclusions/StandardLibrary.h"
28#include "llvm/ADT/ArrayRef.h"
29#include "llvm/ADT/DenseMap.h"
30#include "llvm/ADT/DenseMapInfoVariant.h"
31#include "llvm/ADT/SmallVector.h"
32#include "llvm/ADT/StringMap.h"
33#include "llvm/ADT/StringRef.h"
34#include "llvm/ADT/StringSet.h"
35#include <memory>
36#include <string>
37#include <utility>
38#include <variant>
39#include <vector>
40
41namespace llvm {
42class raw_ostream;
43} // namespace llvm
44namespace clang {
45class Decl;
46class IdentifierInfo;
47namespace include_cleaner {
48
49/// We consider a macro to be a different symbol each time it is defined.
50struct Macro {
51 const IdentifierInfo *Name;
52 /// The location of the Name where the macro is defined.
53 SourceLocation Definition;
54
55 bool operator==(const Macro &S) const { return Definition == S.Definition; }
56};
57
58/// An entity that can be referenced in the code.
59struct Symbol {
60 enum Kind {
61 /// A canonical clang declaration.
62 Declaration,
63 /// A preprocessor macro, as defined in a specific location.
64 Macro,
65 };
66
67 Symbol(const Decl &D) : Storage(&D) {}
68 Symbol(struct Macro M) : Storage(M) {}
69
70 Kind kind() const { return static_cast<Kind>(Storage.index()); }
71 bool operator==(const Symbol &RHS) const { return Storage == RHS.Storage; }
72
73 const Decl &declaration() const { return *std::get<Declaration>(v: Storage); }
74 struct Macro macro() const { return std::get<Macro>(v: Storage); }
75 std::string name() const;
76
77private:
78 // Order must match Kind enum!
79 std::variant<const Decl *, struct Macro> Storage;
80
81 // Disambiguation tag to make sure we can call the right constructor from
82 // DenseMapInfo methods.
83 struct SentinelTag {};
84 Symbol(SentinelTag, decltype(Storage) Sentinel)
85 : Storage(std::move(Sentinel)) {}
86 friend llvm::DenseMapInfo<Symbol>;
87};
88llvm::raw_ostream &operator<<(llvm::raw_ostream &, const Symbol &);
89
90/// Indicates the relation between the reference and the target.
91enum class RefType {
92 /// Target is named by the reference, e.g. function call.
93 Explicit,
94 /// Target isn't spelled, e.g. default constructor call in `Foo f;`
95 Implicit,
96 /// Target's use can't be proven, e.g. a candidate for an unresolved overload.
97 Ambiguous,
98};
99llvm::raw_ostream &operator<<(llvm::raw_ostream &, RefType);
100
101/// Indicates that a piece of code refers to a symbol.
102struct SymbolReference {
103 /// The symbol referred to.
104 Symbol Target;
105 /// The point in the code that refers to the symbol.
106 SourceLocation RefLocation;
107 /// Relation type between the reference location and the target.
108 RefType RT;
109};
110llvm::raw_ostream &operator<<(llvm::raw_ostream &, const SymbolReference &);
111
112/// Represents a file that provides some symbol. Might not be includeable, e.g.
113/// built-in or main-file itself.
114struct Header {
115 enum Kind {
116 /// A source file parsed by clang. (May also be a <built-in> buffer).
117 Physical,
118 /// A recognized standard library header, like <string>.
119 Standard,
120 /// A verbatim header spelling, a string quoted with <> or "" that can be
121 /// #included directly.
122 Verbatim,
123 };
124
125 Header(FileEntryRef FE) : Storage(FE) {}
126 Header(tooling::stdlib::Header H) : Storage(H) {}
127 Header(StringRef VerbatimSpelling) : Storage(VerbatimSpelling) {}
128
129 Kind kind() const { return static_cast<Kind>(Storage.index()); }
130 bool operator==(const Header &RHS) const { return Storage == RHS.Storage; }
131 bool operator<(const Header &RHS) const;
132
133 FileEntryRef physical() const { return std::get<Physical>(v: Storage); }
134 tooling::stdlib::Header standard() const {
135 return std::get<Standard>(v: Storage);
136 }
137 StringRef verbatim() const { return std::get<Verbatim>(v: Storage); }
138
139 /// Absolute path for the header when it's a physical file. Otherwise just
140 /// the spelling without surrounding quotes/brackets.
141 llvm::StringRef resolvedPath() const;
142
143private:
144 // Order must match Kind enum!
145 std::variant<FileEntryRef, tooling::stdlib::Header, StringRef> Storage;
146
147 // Disambiguation tag to make sure we can call the right constructor from
148 // DenseMapInfo methods.
149 struct SentinelTag {};
150 Header(SentinelTag, decltype(Storage) Sentinel)
151 : Storage(std::move(Sentinel)) {}
152 friend llvm::DenseMapInfo<Header>;
153};
154llvm::raw_ostream &operator<<(llvm::raw_ostream &, const Header &);
155
156/// A single #include directive written in the main file.
157struct Include {
158 llvm::StringRef Spelled; // e.g. vector
159 OptionalFileEntryRef Resolved; // e.g. /path/to/c++/v1/vector
160 // nullopt if the header was not found
161 SourceLocation HashLocation; // of hash in #include <vector>
162 unsigned Line = 0; // 1-based line number for #include
163 bool Angled = false; // True if spelled with <angle> quotes.
164 std::string quote() const; // e.g. <vector>
165};
166llvm::raw_ostream &operator<<(llvm::raw_ostream &, const Include &);
167
168/// A container for all includes present in a file.
169/// Supports efficiently hit-testing Headers against Includes.
170class Includes {
171public:
172 /// Registers a directory on the include path (-I etc) from HeaderSearch.
173 /// This allows reasoning about equivalence of e.g. "path/a/b.h" and "a/b.h".
174 /// This must be called before calling add() in order to take effect.
175 ///
176 /// The paths may be relative or absolute, but the paths passed to
177 /// addSearchDirectory() and add() (that is: Include.Resolved->getName())
178 /// should be consistent, as they are compared lexically.
179 /// Generally, this is satisfied if you obtain paths through HeaderSearch
180 /// and FileEntries through PPCallbacks::IncludeDirective().
181 void addSearchDirectory(llvm::StringRef);
182
183 /// Registers an include directive seen in the main file.
184 ///
185 /// This should only be called after all search directories are added.
186 void add(const Include &);
187
188 /// All #includes seen, in the order they appear.
189 llvm::ArrayRef<Include> all() const { return All; }
190
191 /// Determine #includes that match a header (that provides a used symbol).
192 ///
193 /// Matching is based on the type of Header specified:
194 /// - for a physical file like /path/to/foo.h, we check Resolved
195 /// - for a logical file like <vector>, we check Spelled
196 llvm::SmallVector<const Include *> match(Header H) const;
197
198 /// Finds the include written on the specified line.
199 const Include *atLine(unsigned OneBasedIndex) const;
200
201private:
202 llvm::StringSet<> SearchPath;
203
204 std::vector<Include> All;
205 // Lookup structures for match(), values are index into All.
206 llvm::StringMap<llvm::SmallVector<unsigned>> BySpelling;
207 // Heuristic spellings that likely resolve to the given file.
208 llvm::StringMap<llvm::SmallVector<unsigned>> BySpellingAlternate;
209 llvm::DenseMap<const FileEntry *, llvm::SmallVector<unsigned>> ByFile;
210 llvm::DenseMap<unsigned, unsigned> ByLine;
211};
212
213} // namespace include_cleaner
214} // namespace clang
215
216namespace llvm {
217
218template <> struct DenseMapInfo<clang::include_cleaner::Symbol> {
219 using Outer = clang::include_cleaner::Symbol;
220 using Base = DenseMapInfo<decltype(Outer::Storage)>;
221
222 static inline Outer getEmptyKey() {
223 return {Outer::SentinelTag{}, Base::getEmptyKey()};
224 }
225 static inline Outer getTombstoneKey() {
226 return {Outer::SentinelTag{}, Base::getTombstoneKey()};
227 }
228 static unsigned getHashValue(const Outer &Val) {
229 return Base::getHashValue(Val: Val.Storage);
230 }
231 static bool isEqual(const Outer &LHS, const Outer &RHS) {
232 return Base::isEqual(LHS: LHS.Storage, RHS: RHS.Storage);
233 }
234};
235template <> struct DenseMapInfo<clang::include_cleaner::Macro> {
236 using Outer = clang::include_cleaner::Macro;
237 using Base = DenseMapInfo<decltype(Outer::Definition)>;
238
239 static inline Outer getEmptyKey() { return {.Name: nullptr, .Definition: Base::getEmptyKey()}; }
240 static inline Outer getTombstoneKey() {
241 return {.Name: nullptr, .Definition: Base::getTombstoneKey()};
242 }
243 static unsigned getHashValue(const Outer &Val) {
244 return Base::getHashValue(Loc: Val.Definition);
245 }
246 static bool isEqual(const Outer &LHS, const Outer &RHS) {
247 return Base::isEqual(LHS: LHS.Definition, RHS: RHS.Definition);
248 }
249};
250template <> struct DenseMapInfo<clang::include_cleaner::Header> {
251 using Outer = clang::include_cleaner::Header;
252 using Base = DenseMapInfo<decltype(Outer::Storage)>;
253
254 static inline Outer getEmptyKey() {
255 return {Outer::SentinelTag{}, Base::getEmptyKey()};
256 }
257 static inline Outer getTombstoneKey() {
258 return {Outer::SentinelTag{}, Base::getTombstoneKey()};
259 }
260 static unsigned getHashValue(const Outer &Val) {
261 return Base::getHashValue(Val: Val.Storage);
262 }
263 static bool isEqual(const Outer &LHS, const Outer &RHS) {
264 return Base::isEqual(LHS: LHS.Storage, RHS: RHS.Storage);
265 }
266};
267} // namespace llvm
268
269#endif
270

source code of clang-tools-extra/include-cleaner/include/clang-include-cleaner/Types.h