| 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/SourceLocation.h" |
| 26 |
#include "clang/Tooling/Inclusions/StandardLibrary.h" |
| 27 |
#include "llvm/ADT/ArrayRef.h" |
| 28 |
#include "llvm/ADT/DenseMap.h" |
| 29 |
#include "llvm/ADT/SmallVector.h" |
| 30 |
#include "llvm/ADT/StringMap.h" |
| 31 |
#include <memory> |
| 32 |
#include <utility> |
| 33 |
#include <vector> |
| 34 |
|
| 35 |
namespace llvm { |
| 36 |
class raw_ostream; |
| 37 |
} // namespace llvm |
| 38 |
namespace clang { |
| 39 |
class Decl; |
| 40 |
class FileEntry; |
| 41 |
class IdentifierInfo; |
| 42 |
namespace include_cleaner { |
| 43 |
|
| 44 |
/// We consider a macro to be a different symbol each time it is defined. |
| 45 |
struct Macro { |
| 46 |
IdentifierInfo *Name; |
| 47 |
/// The location of the Name where the macro is defined. |
| 48 |
SourceLocation Definition; |
| 49 |
|
| 50 |
bool operator==(const Macro &S) const { return Definition == S.Definition; } |
| 51 |
}; |
| 52 |
|
| 53 |
/// An entity that can be referenced in the code. |
| 54 |
struct Symbol { |
| 55 |
enum Kind { |
| 56 |
/// A canonical clang declaration. |
| 57 |
Declaration, |
| 58 |
/// A preprocessor macro, as defined in a specific location. |
| 59 |
Macro, |
| 60 |
}; |
| 61 |
|
| 62 |
Symbol(const Decl &D) : Storage(&D) {} |
| 63 |
Symbol(struct Macro M) : Storage(M) {} |
| 64 |
|
| 65 |
Kind kind() const { return static_cast<Kind>(Storage.index()); } |
| 66 |
bool operator==(const Symbol &RHS) const { return Storage == RHS.Storage; } |
| 67 |
|
| 68 |
const Decl &declaration() const { return *std::get<Declaration>(Storage); } |
| 69 |
struct Macro macro() const { return std::get<Macro>(Storage); } |
| 70 |
|
| 71 |
private: |
| 72 |
// Order must match Kind enum! |
| 73 |
std::variant<const Decl *, struct Macro> Storage; |
| 74 |
|
| 75 |
// Disambiguation tag to make sure we can call the right constructor from |
| 76 |
// DenseMapInfo methods. |
| 77 |
struct SentinelTag {}; |
| 78 |
Symbol(SentinelTag, decltype(Storage) Sentinel) |
| 79 |
: Storage(std::move(Sentinel)) {} |
| 80 |
friend llvm::DenseMapInfo<Symbol>; |
| 81 |
}; |
| 82 |
llvm::raw_ostream &operator<<(llvm::raw_ostream &, const Symbol &); |
| 83 |
|
| 84 |
/// Indicates the relation between the reference and the target. |
| 85 |
enum class RefType { |
| 86 |
/// Target is named by the reference, e.g. function call. |
| 87 |
Explicit, |
| 88 |
/// Target isn't spelled, e.g. default constructor call in `Foo f;` |
| 89 |
Implicit, |
| 90 |
/// Target's use can't be proven, e.g. a candidate for an unresolved overload. |
| 91 |
Ambiguous, |
| 92 |
}; |
| 93 |
llvm::raw_ostream &operator<<(llvm::raw_ostream &, RefType); |
| 94 |
|
| 95 |
/// Indicates that a piece of code refers to a symbol. |
| 96 |
struct SymbolReference { |
| 97 |
/// The point in the code that refers to the symbol. |
| 98 |
SourceLocation RefLocation; |
| 99 |
/// The symbol referred to. |
| 100 |
Symbol Target; |
| 101 |
/// Relation type between the reference location and the target. |
| 102 |
RefType RT; |
| 103 |
}; |
| 104 |
llvm::raw_ostream &operator<<(llvm::raw_ostream &, const SymbolReference &); |
| 105 |
|
| 106 |
/// Represents a file that provides some symbol. Might not be includeable, e.g. |
| 107 |
/// built-in or main-file itself. |
| 108 |
struct Header { |
| 109 |
enum Kind { |
| 110 |
/// A source file parsed by clang. (May also be a <built-in> buffer). |
| 111 |
Physical, |
| 112 |
/// A recognized standard library header, like <string>. |
| 113 |
Standard, |
| 114 |
/// A verbatim header spelling, a string quoted with <> or "" that can be |
| 115 |
/// #included directly. |
| 116 |
Verbatim, |
| 117 |
}; |
| 118 |
|
| 119 |
Header(const FileEntry *FE) : Storage(FE) {} |
| 120 |
Header(tooling::stdlib::Header H) : Storage(H) {} |
| 121 |
Header(StringRef VerbatimSpelling) : Storage(VerbatimSpelling) {} |
| 122 |
|
| 123 |
Kind kind() const { return static_cast<Kind>(Storage.index()); } |
| 124 |
bool operator==(const Header &RHS) const { return Storage == RHS.Storage; } |
| 125 |
bool operator<(const Header &RHS) const; |
| 126 |
|
| 127 |
const FileEntry *physical() const { return std::get<Physical>(Storage); } |
| 128 |
tooling::stdlib::Header standard() const { |
| 129 |
return std::get<Standard>(Storage); |
| 130 |
} |
| 131 |
StringRef verbatim() const { return std::get<Verbatim>(Storage); } |
| 132 |
|
| 133 |
private: |
| 134 |
// Order must match Kind enum! |
| 135 |
std::variant<const FileEntry *, tooling::stdlib::Header, StringRef> Storage; |
| 136 |
|
| 137 |
// Disambiguation tag to make sure we can call the right constructor from |
| 138 |
// DenseMapInfo methods. |
| 139 |
struct SentinelTag {}; |
| 140 |
Header(SentinelTag, decltype(Storage) Sentinel) |
| 141 |
: Storage(std::move(Sentinel)) {} |
| 142 |
friend llvm::DenseMapInfo<Header>; |
| 143 |
}; |
| 144 |
llvm::raw_ostream &operator<<(llvm::raw_ostream &, const Header &); |
| 145 |
|
| 146 |
/// A single #include directive written in the main file. |
| 147 |
struct Include { |
| 148 |
llvm::StringRef Spelled; // e.g. vector |
| 149 |
const FileEntry *Resolved = nullptr; // e.g. /path/to/c++/v1/vector |
| 150 |
// nullptr if the header was not found |
| 151 |
SourceLocation HashLocation; // of hash in #include <vector> |
| 152 |
unsigned Line = 0; // 1-based line number for #include |
| 153 |
bool Angled = false; // True if spelled with <angle> quotes. |
| 154 |
std::string quote() const; // e.g. <vector> |
| 155 |
}; |
| 156 |
llvm::raw_ostream &operator<<(llvm::raw_ostream &, const Include &); |
| 157 |
|
| 158 |
/// A container for all includes present in a file. |
| 159 |
/// Supports efficiently hit-testing Headers against Includes. |
| 160 |
class Includes { |
| 161 |
public: |
| 162 |
void add(const Include &); |
| 163 |
|
| 164 |
/// All #includes seen, in the order they appear. |
| 165 |
llvm::ArrayRef<Include> all() const { return All; } |
| 166 |
|
| 167 |
/// Determine #includes that match a header (that provides a used symbol). |
| 168 |
/// |
| 169 |
/// Matching is based on the type of Header specified: |
| 170 |
/// - for a physical file like /path/to/foo.h, we check Resolved |
| 171 |
/// - for a logical file like <vector>, we check Spelled |
| 172 |
llvm::SmallVector<const Include *> match(Header H) const; |
| 173 |
|
| 174 |
/// Finds the include written on the specified line. |
| 175 |
const Include *atLine(unsigned OneBasedIndex) const; |
| 176 |
|
| 177 |
private: |
| 178 |
std::vector<Include> All; |
| 179 |
// Lookup structures for match(), values are index into All. |
| 180 |
llvm::StringMap<llvm::SmallVector<unsigned>> BySpelling; |
| 181 |
llvm::DenseMap<const FileEntry *, llvm::SmallVector<unsigned>> ByFile; |
| 182 |
llvm::DenseMap<unsigned, unsigned> ByLine; |
| 183 |
}; |
| 184 |
|
| 185 |
} // namespace include_cleaner |
| 186 |
} // namespace clang |
| 187 |
|
| 188 |
namespace llvm { |
| 189 |
|
| 190 |
template <> struct DenseMapInfo<clang::include_cleaner::Symbol> { |
| 191 |
using Outer = clang::include_cleaner::Symbol; |
| 192 |
using Base = DenseMapInfo<decltype(Outer::Storage)>; |
| 193 |
|
| 194 |
static inline Outer getEmptyKey() { |
| 195 |
return {Outer::SentinelTag{}, Base::getEmptyKey()}; |
| 196 |
} |
| 197 |
static inline Outer getTombstoneKey() { |
| 198 |
return {Outer::SentinelTag{}, Base::getTombstoneKey()}; |
| 199 |
} |
| 200 |
static unsigned getHashValue(const Outer &Val) { |
| 201 |
return Base::getHashValue(Val.Storage); |
| 202 |
} |
| 203 |
static bool isEqual(const Outer &LHS, const Outer &RHS) { |
| 204 |
return Base::isEqual(LHS.Storage, RHS.Storage); |
| 205 |
} |
| 206 |
}; |
| 207 |
template <> struct DenseMapInfo<clang::include_cleaner::Macro> { |
| 208 |
using Outer = clang::include_cleaner::Macro; |
| 209 |
using Base = DenseMapInfo<decltype(Outer::Definition)>; |
| 210 |
|
| 211 |
static inline Outer getEmptyKey() { return {nullptr, Base::getEmptyKey()}; } |
| 212 |
static inline Outer getTombstoneKey() { |
| 213 |
return {nullptr, Base::getTombstoneKey()}; |
| 214 |
} |
| 215 |
static unsigned getHashValue(const Outer &Val) { |
| 216 |
return Base::getHashValue(Val.Definition); |
| 217 |
} |
| 218 |
static bool isEqual(const Outer &LHS, const Outer &RHS) { |
| 219 |
return Base::isEqual(LHS.Definition, RHS.Definition); |
| 220 |
} |
| 221 |
}; |
| 222 |
template <> struct DenseMapInfo<clang::include_cleaner::Header> { |
| 223 |
using Outer = clang::include_cleaner::Header; |
| 224 |
using Base = DenseMapInfo<decltype(Outer::Storage)>; |
| 225 |
|
| 226 |
static inline Outer getEmptyKey() { |
| 227 |
return {Outer::SentinelTag{}, Base::getEmptyKey()}; |
| 228 |
} |
| 229 |
static inline Outer getTombstoneKey() { |
| 230 |
return {Outer::SentinelTag{}, Base::getTombstoneKey()}; |
| 231 |
} |
| 232 |
static unsigned getHashValue(const Outer &Val) { |
| 233 |
return Base::getHashValue(Val.Storage); |
| 234 |
} |
| 235 |
static bool isEqual(const Outer &LHS, const Outer &RHS) { |
| 236 |
return Base::isEqual(LHS.Storage, RHS.Storage); |
| 237 |
} |
| 238 |
}; |
| 239 |
} // namespace llvm |
| 240 |
|
| 241 |
#endif |