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

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