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 /// For phiscal files, either absolute path or path relative to the execution 140 /// root. Otherwise just 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 270