Debian Codegraph @

llvm-project/clang-tools-extra/clangd/Headers.h

raw
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