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