Debian Codegraph @

clang-tools-extra/include-cleaner/include/clang-include-cleaner/Types.h

raw
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
41 namespace llvm {
42 class raw_ostream;
43 } // namespace llvm
44 namespace clang {
45 class Decl;
46 class IdentifierInfo;
47 namespace include_cleaner {
48
49 /// We consider a macro to be a different symbol each time it is defined.
50 struct 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.
59 struct 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>(Storage); }
74 struct Macro macro() const { return std::get<Macro>(Storage); }
75 std::string name() const;
76
77 private:
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 };
88 llvm::raw_ostream &operator<<(llvm::raw_ostream &, const Symbol &);
89
90 /// Indicates the relation between the reference and the target.
91 enum 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 };
99 llvm::raw_ostream &operator<<(llvm::raw_ostream &, RefType);
100
101 /// Indicates that a piece of code refers to a symbol.
102 struct 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 };
110 llvm::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.
114 struct 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>(Storage); }
134 tooling::stdlib::Header standard() const {
135 return std::get<Standard>(Storage);
136 }
137 StringRef verbatim() const { return std::get<Verbatim>(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
143 private:
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 };
154 llvm::raw_ostream &operator<<(llvm::raw_ostream &, const Header &);
155
156 /// A single #include directive written in the main file.
157 struct 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 };
166 llvm::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.
170 class Includes {
171 public:
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
201 private:
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
216 namespace llvm {
217
218 template <> 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.Storage);
230 }
231 static bool isEqual(const Outer &LHS, const Outer &RHS) {
232 return Base::isEqual(LHS.Storage, RHS.Storage);
233 }
234 };
235 template <> 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 {nullptr, Base::getEmptyKey()}; }
240 static inline Outer getTombstoneKey() {
241 return {nullptr, Base::getTombstoneKey()};
242 }
243 static unsigned getHashValue(const Outer &Val) {
244 return Base::getHashValue(Val.Definition);
245 }
246 static bool isEqual(const Outer &LHS, const Outer &RHS) {
247 return Base::isEqual(LHS.Definition, RHS.Definition);
248 }
249 };
250 template <> 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.Storage);
262 }
263 static bool isEqual(const Outer &LHS, const Outer &RHS) {
264 return Base::isEqual(LHS.Storage, RHS.Storage);
265 }
266 };
267 } // namespace llvm
268
269 #endif