| 1 |
//===--- Headers.h - Include headers -----------------------------*- 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 |
#ifndef LLVM_CLANG_TOOLS_EXTRA_CLANGD_HEADERS_H |
| 10 |
#define LLVM_CLANG_TOOLS_EXTRA_CLANGD_HEADERS_H |
| 11 |
|
| 12 |
#include "Protocol.h" |
| 13 |
#include "SourceCode.h" |
| 14 |
#include "index/Symbol.h" |
| 15 |
#include "support/Path.h" |
| 16 |
#include "clang/Basic/FileEntry.h" |
| 17 |
#include "clang/Basic/TokenKinds.h" |
| 18 |
#include "clang/Format/Format.h" |
| 19 |
#include "clang/Frontend/CompilerInstance.h" |
| 20 |
#include "clang/Lex/HeaderSearch.h" |
| 21 |
#include "clang/Lex/Preprocessor.h" |
| 22 |
#include "clang/Tooling/Inclusions/HeaderIncludes.h" |
| 23 |
#include "clang/Tooling/Inclusions/StandardLibrary.h" |
| 24 |
#include "llvm/ADT/ArrayRef.h" |
| 25 |
#include "llvm/ADT/DenseSet.h" |
| 26 |
#include "llvm/ADT/StringRef.h" |
| 27 |
#include "llvm/ADT/StringSet.h" |
| 28 |
#include "llvm/Support/Error.h" |
| 29 |
#include "llvm/Support/FileSystem/UniqueID.h" |
| 30 |
#include <optional> |
| 31 |
#include <string> |
| 32 |
|
| 33 |
namespace clang { |
| 34 |
namespace clangd { |
| 35 |
|
| 36 |
/// Returns true if \p Include is literal include like "path" or <path>. |
| 37 |
bool isLiteralInclude(llvm::StringRef Include); |
| 38 |
|
| 39 |
/// Represents a header file to be #include'd. |
| 40 |
struct HeaderFile { |
| 41 |
std::string File; |
| 42 |
/// If this is true, `File` is a literal string quoted with <> or "" that |
| 43 |
/// can be #included directly; otherwise, `File` is an absolute file path. |
| 44 |
bool Verbatim; |
| 45 |
|
| 46 |
bool valid() const; |
| 47 |
}; |
| 48 |
|
| 49 |
/// A header and directives as stored in a Symbol. |
| 50 |
struct SymbolInclude { |
| 51 |
/// The header to include. This is either a URI or a verbatim include which is |
| 52 |
/// quoted with <> or "". |
| 53 |
llvm::StringRef Header; |
| 54 |
/// The include directive(s) that can be used, e.g. #import and/or #include. |
| 55 |
Symbol::IncludeDirective Directive; |
| 56 |
}; |
| 57 |
|
| 58 |
/// Creates a `HeaderFile` from \p Header which can be either a URI or a literal |
| 59 |
/// include. |
| 60 |
llvm::Expected<HeaderFile> toHeaderFile(llvm::StringRef Header, |
| 61 |
llvm::StringRef HintPath); |
| 62 |
|
| 63 |
// Returns include headers for \p Sym sorted by popularity. If two headers are |
| 64 |
// equally popular, prefer the shorter one. |
| 65 |
llvm::SmallVector<SymbolInclude, 1> getRankedIncludes(const Symbol &Sym); |
| 66 |
|
| 67 |
// An #include directive that we found in the main file. |
| 68 |
struct Inclusion { |
| 69 |
tok::PPKeywordKind Directive; // Directive used for inclusion, e.g. import |
| 70 |
std::string Written; // Inclusion name as written e.g. <vector>. |
| 71 |
Path Resolved; // Resolved path of included file. Empty if not resolved. |
| 72 |
unsigned HashOffset = 0; // Byte offset from start of file to #. |
| 73 |
int HashLine = 0; // Line number containing the directive, 0-indexed. |
| 74 |
SrcMgr::CharacteristicKind FileKind = SrcMgr::C_User; |
| 75 |
std::optional<unsigned> HeaderID; |
| 76 |
bool BehindPragmaKeep = false; // Has IWYU pragma: keep right after. |
| 77 |
}; |
| 78 |
llvm::raw_ostream &operator<<(llvm::raw_ostream &, const Inclusion &); |
| 79 |
bool operator==(const Inclusion &LHS, const Inclusion &RHS); |
| 80 |
|
| 81 |
// Contains information about one file in the build graph and its direct |
| 82 |
// dependencies. Doesn't own the strings it references (IncludeGraph is |
| 83 |
// self-contained). |
| 84 |
struct IncludeGraphNode { |
| 85 |
enum class SourceFlag : uint8_t { |
| 86 |
None = 0, |
| 87 |
// Whether current file is a main file rather than a header. |
| 88 |
IsTU = 1 << 0, |
| 89 |
// Whether current file had any uncompilable errors during indexing. |
| 90 |
HadErrors = 1 << 1, |
| 91 |
}; |
| 92 |
|
| 93 |
SourceFlag Flags = SourceFlag::None; |
| 94 |
llvm::StringRef URI; |
| 95 |
FileDigest Digest{{0}}; |
| 96 |
std::vector<llvm::StringRef> DirectIncludes; |
| 97 |
}; |
| 98 |
// FileURI and FileInclusions are references to keys of the map containing |
| 99 |
// them. |
| 100 |
// Important: The graph generated by those callbacks might contain cycles, self |
| 101 |
// edges and multi edges. |
| 102 |
using IncludeGraph = llvm::StringMap<IncludeGraphNode>; |
| 103 |
|
| 104 |
inline IncludeGraphNode::SourceFlag operator|(IncludeGraphNode::SourceFlag A, |
| 105 |
IncludeGraphNode::SourceFlag B) { |
| 106 |
return static_cast<IncludeGraphNode::SourceFlag>(static_cast<uint8_t>(A) | |
| 107 |
static_cast<uint8_t>(B)); |
| 108 |
} |
| 109 |
|
| 110 |
inline bool operator&(IncludeGraphNode::SourceFlag A, |
| 111 |
IncludeGraphNode::SourceFlag B) { |
| 112 |
return static_cast<uint8_t>(A) & static_cast<uint8_t>(B); |
| 113 |
} |
| 114 |
|
| 115 |
inline IncludeGraphNode::SourceFlag & |
| 116 |
operator|=(IncludeGraphNode::SourceFlag &A, IncludeGraphNode::SourceFlag B) { |
| 117 |
return A = A | B; |
| 118 |
} |
| 119 |
|
| 120 |
// Information captured about the inclusion graph in a translation unit. |
| 121 |
// This includes detailed information about the direct #includes, and summary |
| 122 |
// information about all transitive includes. |
| 123 |
// |
| 124 |
// It should be built incrementally with collectIncludeStructureCallback(). |
| 125 |
// When we build the preamble, we capture and store its include structure along |
| 126 |
// with the preamble data. When we use the preamble, we can copy its |
| 127 |
// IncludeStructure and use another collectIncludeStructureCallback() to fill |
| 128 |
// in any non-preamble inclusions. |
| 129 |
class IncludeStructure { |
| 130 |
public: |
| 131 |
IncludeStructure() { |
| 132 |
// Reserve HeaderID = 0 for the main file. |
| 133 |
RealPathNames.emplace_back(); |
| 134 |
} |
| 135 |
|
| 136 |
// Inserts a PPCallback and CommentHandler that visits all includes in the |
| 137 |
// main file and populates the structure. It will also scan for IWYU pragmas |
| 138 |
// in comments. |
| 139 |
void collect(const CompilerInstance &CI); |
| 140 |
|
| 141 |
// HeaderID identifies file in the include graph. It corresponds to a |
| 142 |
// FileEntry rather than a FileID, but stays stable across preamble & main |
| 143 |
// file builds. |
| 144 |
enum class HeaderID : unsigned {}; |
| 145 |
|
| 146 |
std::optional<HeaderID> getID(const FileEntry *Entry) const; |
| 147 |
HeaderID getOrCreateID(FileEntryRef Entry); |
| 148 |
|
| 149 |
StringRef getRealPath(HeaderID ID) const { |
| 150 |
assert(static_cast<unsigned>(ID) <= RealPathNames.size()); |
| 151 |
return RealPathNames[static_cast<unsigned>(ID)]; |
| 152 |
} |
| 153 |
|
| 154 |
bool isSelfContained(HeaderID ID) const { |
| 155 |
return !NonSelfContained.contains(ID); |
| 156 |
} |
| 157 |
|
| 158 |
bool hasIWYUExport(HeaderID ID) const { |
| 159 |
return HasIWYUExport.contains(ID); |
| 160 |
} |
| 161 |
|
| 162 |
// Return all transitively reachable files. |
| 163 |
llvm::ArrayRef<std::string> allHeaders() const { return RealPathNames; } |
| 164 |
|
| 165 |
// Return all transitively reachable files, and their minimum include depth. |
| 166 |
// All transitive includes (absolute paths), with their minimum include depth. |
| 167 |
// Root --> 0, #included file --> 1, etc. |
| 168 |
// Root is the ID of the header being visited first. |
| 169 |
llvm::DenseMap<HeaderID, unsigned> |
| 170 |
includeDepth(HeaderID Root = MainFileID) const; |
| 171 |
|
| 172 |
// Maps HeaderID to the ids of the files included from it. |
| 173 |
llvm::DenseMap<HeaderID, SmallVector<HeaderID>> IncludeChildren; |
| 174 |
|
| 175 |
llvm::DenseMap<tooling::stdlib::Header, llvm::SmallVector<HeaderID>> |
| 176 |
StdlibHeaders; |
| 177 |
|
| 178 |
std::vector<Inclusion> MainFileIncludes; |
| 179 |
|
| 180 |
// We reserve HeaderID(0) for the main file and will manually check for that |
| 181 |
// in getID and getOrCreateID because the UniqueID is not stable when the |
| 182 |
// content of the main file changes. |
| 183 |
static const HeaderID MainFileID = HeaderID(0u); |
| 184 |
|
| 185 |
class RecordHeaders; |
| 186 |
|
| 187 |
private: |
| 188 |
// MainFileEntry will be used to check if the queried file is the main file |
| 189 |
// or not. |
| 190 |
const FileEntry *MainFileEntry = nullptr; |
| 191 |
|
| 192 |
std::vector<std::string> RealPathNames; // In HeaderID order. |
| 193 |
// FileEntry::UniqueID is mapped to the internal representation (HeaderID). |
| 194 |
// Identifying files in a way that persists from preamble build to subsequent |
| 195 |
// builds is surprisingly hard. FileID is unavailable in InclusionDirective(), |
| 196 |
// and RealPathName and UniqueID are not preserved in |
| 197 |
// the preamble. |
| 198 |
llvm::DenseMap<llvm::sys::fs::UniqueID, HeaderID> UIDToIndex; |
| 199 |
// Contains HeaderIDs of all non self-contained entries in the |
| 200 |
// IncludeStructure. |
| 201 |
llvm::DenseSet<HeaderID> NonSelfContained; |
| 202 |
// Contains a set of headers that have either "IWYU pragma: export" or "IWYU |
| 203 |
// pragma: begin_exports". |
| 204 |
llvm::DenseSet<HeaderID> HasIWYUExport; |
| 205 |
}; |
| 206 |
|
| 207 |
// Calculates insertion edit for including a new header in a file. |
| 208 |
class IncludeInserter { |
| 209 |
public: |
| 210 |
// If \p HeaderSearchInfo is nullptr (e.g. when compile command is |
| 211 |
// infeasible), this will only try to insert verbatim headers, and |
| 212 |
// include path of non-verbatim header will not be shortened. |
| 213 |
IncludeInserter(StringRef FileName, StringRef Code, |
| 214 |
const format::FormatStyle &Style, StringRef BuildDir, |
| 215 |
HeaderSearch *HeaderSearchInfo) |
| 216 |
: FileName(FileName), Code(Code), BuildDir(BuildDir), |
| 217 |
HeaderSearchInfo(HeaderSearchInfo), |
| 218 |
Inserter(FileName, Code, Style.IncludeStyle) {} |
| 219 |
|
| 220 |
void addExisting(const Inclusion &Inc); |
| 221 |
|
| 222 |
/// Checks whether to add an #include of the header into \p File. |
| 223 |
/// An #include will not be added if: |
| 224 |
/// - Either \p DeclaringHeader or \p InsertedHeader is already (directly) |
| 225 |
/// in \p Inclusions (including those included via different paths). |
| 226 |
/// - \p DeclaringHeader or \p InsertedHeader is the same as \p File. |
| 227 |
/// |
| 228 |
/// \param DeclaringHeader is path of the original header corresponding to \p |
| 229 |
/// InsertedHeader e.g. the header that declares a symbol. |
| 230 |
/// \param InsertedHeader The preferred header to be inserted. This could be |
| 231 |
/// the same as DeclaringHeader but must be provided. |
| 232 |
bool shouldInsertInclude(PathRef DeclaringHeader, |
| 233 |
const HeaderFile &InsertedHeader) const; |
| 234 |
|
| 235 |
/// Determines the preferred way to #include a file, taking into account the |
| 236 |
/// search path. Usually this will prefer a shorter representation like |
| 237 |
/// 'Foo/Bar.h' over a longer one like 'Baz/include/Foo/Bar.h'. |
| 238 |
/// |
| 239 |
/// \param InsertedHeader The preferred header to be inserted. |
| 240 |
/// |
| 241 |
/// \param IncludingFile is the absolute path of the file that InsertedHeader |
| 242 |
/// will be inserted. |
| 243 |
/// |
| 244 |
/// \return A quoted "path" or <path> to be included, or std::nullopt if it |
| 245 |
/// couldn't be shortened. |
| 246 |
std::optional<std::string> |
| 247 |
calculateIncludePath(const HeaderFile &InsertedHeader, |
| 248 |
llvm::StringRef IncludingFile) const; |
| 249 |
|
| 250 |
/// Calculates an edit that inserts \p VerbatimHeader into code. If the header |
| 251 |
/// is already included, this returns std::nullopt. |
| 252 |
std::optional<TextEdit> insert(llvm::StringRef VerbatimHeader, |
| 253 |
tooling::IncludeDirective Directive) const; |
| 254 |
|
| 255 |
private: |
| 256 |
StringRef FileName; |
| 257 |
StringRef Code; |
| 258 |
StringRef BuildDir; |
| 259 |
HeaderSearch *HeaderSearchInfo = nullptr; |
| 260 |
llvm::StringSet<> IncludedHeaders; // Both written and resolved. |
| 261 |
tooling::HeaderIncludes Inserter; // Computers insertion replacement. |
| 262 |
}; |
| 263 |
|
| 264 |
} // namespace clangd |
| 265 |
} // namespace clang |
| 266 |
|
| 267 |
namespace llvm { |
| 268 |
|
| 269 |
// Support HeaderIDs as DenseMap keys. |
| 270 |
template <> struct DenseMapInfo<clang::clangd::IncludeStructure::HeaderID> { |
| 271 |
static inline clang::clangd::IncludeStructure::HeaderID getEmptyKey() { |
| 272 |
return static_cast<clang::clangd::IncludeStructure::HeaderID>(-1); |
| 273 |
} |
| 274 |
|
| 275 |
static inline clang::clangd::IncludeStructure::HeaderID getTombstoneKey() { |
| 276 |
return static_cast<clang::clangd::IncludeStructure::HeaderID>(-2); |
| 277 |
} |
| 278 |
|
| 279 |
static unsigned |
| 280 |
getHashValue(const clang::clangd::IncludeStructure::HeaderID &Tag) { |
| 281 |
return hash_value(static_cast<unsigned>(Tag)); |
| 282 |
} |
| 283 |
|
| 284 |
static bool isEqual(const clang::clangd::IncludeStructure::HeaderID &LHS, |
| 285 |
const clang::clangd::IncludeStructure::HeaderID &RHS) { |
| 286 |
return LHS == RHS; |
| 287 |
} |
| 288 |
}; |
| 289 |
|
| 290 |
} // namespace llvm |
| 291 |
|
| 292 |
#endif // LLVM_CLANG_TOOLS_EXTRA_CLANGD_HEADERS_H |