clang-tools 18.0.0git
Headers.cpp
Go to the documentation of this file.
1//===--- Headers.cpp - 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#include "Headers.h"
10#include "Preamble.h"
11#include "SourceCode.h"
12#include "clang/Basic/SourceLocation.h"
13#include "clang/Basic/SourceManager.h"
14#include "clang/Frontend/CompilerInstance.h"
15#include "clang/Lex/DirectoryLookup.h"
16#include "clang/Lex/HeaderSearch.h"
17#include "clang/Lex/PPCallbacks.h"
18#include "clang/Lex/Preprocessor.h"
19#include "clang/Tooling/Inclusions/HeaderAnalysis.h"
20#include "llvm/ADT/SmallVector.h"
21#include "llvm/ADT/StringRef.h"
22#include "llvm/Support/Path.h"
23#include <cstring>
24#include <optional>
25#include <string>
26
27namespace clang {
28namespace clangd {
29
31public:
32 RecordHeaders(const CompilerInstance &CI, IncludeStructure *Out)
33 : SM(CI.getSourceManager()),
34 Out(Out) {}
35
36 // Record existing #includes - both written and resolved paths. Only #includes
37 // in the main file are collected.
38 void InclusionDirective(SourceLocation HashLoc, const Token &IncludeTok,
39 llvm::StringRef FileName, bool IsAngled,
40 CharSourceRange /*FilenameRange*/,
41 OptionalFileEntryRef File,
42 llvm::StringRef /*SearchPath*/,
43 llvm::StringRef /*RelativePath*/,
44 const clang::Module * /*Imported*/,
45 SrcMgr::CharacteristicKind FileKind) override {
46 auto MainFID = SM.getMainFileID();
47 // If an include is part of the preamble patch, translate #line directives.
48 if (InBuiltinFile)
49 HashLoc = translatePreamblePatchLocation(HashLoc, SM);
50
51 // Record main-file inclusions (including those mapped from the preamble
52 // patch).
53 if (isInsideMainFile(HashLoc, SM)) {
54 Out->MainFileIncludes.emplace_back();
55 auto &Inc = Out->MainFileIncludes.back();
56 Inc.Written =
57 (IsAngled ? "<" + FileName + ">" : "\"" + FileName + "\"").str();
58 Inc.Resolved = std::string(
59 File ? getCanonicalPath(*File, SM.getFileManager()).value_or("")
60 : "");
61 Inc.HashOffset = SM.getFileOffset(HashLoc);
62 Inc.HashLine =
63 SM.getLineNumber(SM.getFileID(HashLoc), Inc.HashOffset) - 1;
64 Inc.FileKind = FileKind;
65 Inc.Directive = IncludeTok.getIdentifierInfo()->getPPKeywordID();
66 if (File) {
68 Inc.HeaderID = static_cast<unsigned>(HID);
69 if (IsAngled)
70 if (auto StdlibHeader = tooling::stdlib::Header::named(Inc.Written)) {
71 auto &IDs = Out->StdlibHeaders[*StdlibHeader];
72 // Few physical files for one stdlib header name, linear scan is ok.
73 if (!llvm::is_contained(IDs, HID))
74 IDs.push_back(HID);
75 }
76 }
77 Out->MainFileIncludesBySpelling.try_emplace(Inc.Written)
78 .first->second.push_back(Out->MainFileIncludes.size() - 1);
79 }
80
81 // Record include graph (not just for main-file includes)
82 if (File) {
83 auto IncludingFileEntry = SM.getFileEntryRefForID(SM.getFileID(HashLoc));
84 if (!IncludingFileEntry) {
85 assert(SM.getBufferName(HashLoc).startswith("<") &&
86 "Expected #include location to be a file or <built-in>");
87 // Treat as if included from the main file.
88 IncludingFileEntry = SM.getFileEntryRefForID(MainFID);
89 }
90 auto IncludingID = Out->getOrCreateID(*IncludingFileEntry),
91 IncludedID = Out->getOrCreateID(*File);
92 Out->IncludeChildren[IncludingID].push_back(IncludedID);
93 }
94 }
95
96 void FileChanged(SourceLocation Loc, FileChangeReason Reason,
97 SrcMgr::CharacteristicKind FileType,
98 FileID PrevFID) override {
99 switch (Reason) {
100 case PPCallbacks::EnterFile:
101 ++Level;
102 if (BuiltinFile.isInvalid() && SM.isWrittenInBuiltinFile(Loc)) {
103 BuiltinFile = SM.getFileID(Loc);
104 InBuiltinFile = true;
105 }
106 break;
107 case PPCallbacks::ExitFile: {
108 --Level;
109 if (PrevFID == BuiltinFile)
110 InBuiltinFile = false;
111 break;
112 }
113 case PPCallbacks::RenameFile:
114 case PPCallbacks::SystemHeaderPragma:
115 break;
116 }
117 }
118
119private:
120 // Keeps track of include depth for the current file. It's 1 for main file.
121 int Level = 0;
122 bool inMainFile() const { return Level == 1; }
123
124 const SourceManager &SM;
125 // Set after entering the <built-in> file.
126 FileID BuiltinFile;
127 // Indicates whether <built-in> file is part of include stack.
128 bool InBuiltinFile = false;
129
130 IncludeStructure *Out;
131};
132
133bool isLiteralInclude(llvm::StringRef Include) {
134 return Include.startswith("<") || Include.startswith("\"");
135}
136
137bool HeaderFile::valid() const {
138 return (Verbatim && isLiteralInclude(File)) ||
139 (!Verbatim && llvm::sys::path::is_absolute(File));
140}
141
142llvm::Expected<HeaderFile> toHeaderFile(llvm::StringRef Header,
143 llvm::StringRef HintPath) {
144 if (isLiteralInclude(Header))
145 return HeaderFile{Header.str(), /*Verbatim=*/true};
146 auto U = URI::parse(Header);
147 if (!U)
148 return U.takeError();
149
150 auto IncludePath = URI::includeSpelling(*U);
151 if (!IncludePath)
152 return IncludePath.takeError();
153 if (!IncludePath->empty())
154 return HeaderFile{std::move(*IncludePath), /*Verbatim=*/true};
155
156 auto Resolved = URI::resolve(*U, HintPath);
157 if (!Resolved)
158 return Resolved.takeError();
159 return HeaderFile{std::move(*Resolved), /*Verbatim=*/false};
160}
161
162llvm::SmallVector<SymbolInclude, 1> getRankedIncludes(const Symbol &Sym) {
163 auto Includes = Sym.IncludeHeaders;
164 // Sort in descending order by reference count and header length.
165 llvm::sort(Includes, [](const Symbol::IncludeHeaderWithReferences &LHS,
167 if (LHS.References == RHS.References)
168 return LHS.IncludeHeader.size() < RHS.IncludeHeader.size();
169 return LHS.References > RHS.References;
170 });
171 llvm::SmallVector<SymbolInclude, 1> Headers;
172 for (const auto &Include : Includes)
173 Headers.push_back({Include.IncludeHeader, Include.supportedDirectives()});
174 return Headers;
175}
176
177void IncludeStructure::collect(const CompilerInstance &CI) {
178 auto &SM = CI.getSourceManager();
179 MainFileEntry = SM.getFileEntryForID(SM.getMainFileID());
180 auto Collector = std::make_unique<RecordHeaders>(CI, this);
181 CI.getPreprocessor().addPPCallbacks(std::move(Collector));
182
183 // If we're reusing a preamble, don't repopulate SearchPathsCanonical.
184 // The entries will be the same, but canonicalizing to find out is expensive!
185 if (SearchPathsCanonical.empty()) {
186 for (const auto &Dir :
187 CI.getPreprocessor().getHeaderSearchInfo().search_dir_range()) {
188 if (Dir.getLookupType() == DirectoryLookup::LT_NormalDir)
189 SearchPathsCanonical.emplace_back(
190 SM.getFileManager().getCanonicalName(*Dir.getDirRef()));
191 }
192 }
193}
194
195std::optional<IncludeStructure::HeaderID>
196IncludeStructure::getID(const FileEntry *Entry) const {
197 // HeaderID of the main file is always 0;
198 if (Entry == MainFileEntry) {
199 return static_cast<IncludeStructure::HeaderID>(0u);
200 }
201 auto It = UIDToIndex.find(Entry->getUniqueID());
202 if (It == UIDToIndex.end())
203 return std::nullopt;
204 return It->second;
205}
206
208 // Main file's FileEntry was not known at IncludeStructure creation time.
209 if (&Entry.getFileEntry() == MainFileEntry) {
210 if (RealPathNames.front().empty())
211 RealPathNames.front() = MainFileEntry->tryGetRealPathName().str();
212 return MainFileID;
213 }
214 auto R = UIDToIndex.try_emplace(
215 Entry.getUniqueID(),
216 static_cast<IncludeStructure::HeaderID>(RealPathNames.size()));
217 if (R.second)
218 RealPathNames.emplace_back();
219 IncludeStructure::HeaderID Result = R.first->getSecond();
220 std::string &RealPathName = RealPathNames[static_cast<unsigned>(Result)];
221 if (RealPathName.empty())
222 RealPathName = Entry.getFileEntry().tryGetRealPathName().str();
223 return Result;
224}
225
226llvm::DenseMap<IncludeStructure::HeaderID, unsigned>
228 // Include depth 0 is the main file only.
229 llvm::DenseMap<HeaderID, unsigned> Result;
230 assert(static_cast<unsigned>(Root) < RealPathNames.size());
231 Result[Root] = 0;
232 std::vector<IncludeStructure::HeaderID> CurrentLevel;
233 CurrentLevel.push_back(Root);
234 llvm::DenseSet<IncludeStructure::HeaderID> Seen;
235 Seen.insert(Root);
236
237 // Each round of BFS traversal finds the next depth level.
238 std::vector<IncludeStructure::HeaderID> PreviousLevel;
239 for (unsigned Level = 1; !CurrentLevel.empty(); ++Level) {
240 PreviousLevel.clear();
241 PreviousLevel.swap(CurrentLevel);
242 for (const auto &Parent : PreviousLevel) {
243 for (const auto &Child : IncludeChildren.lookup(Parent)) {
244 if (Seen.insert(Child).second) {
245 CurrentLevel.push_back(Child);
246 Result[Child] = Level;
247 }
248 }
249 }
250 }
251 return Result;
252}
253
254llvm::SmallVector<const Inclusion *>
255IncludeStructure::mainFileIncludesWithSpelling(llvm::StringRef Spelling) const {
256 llvm::SmallVector<const Inclusion *> Includes;
257 for (auto Idx : MainFileIncludesBySpelling.lookup(Spelling))
258 Includes.push_back(&MainFileIncludes[Idx]);
259 return Includes;
260}
261
263 IncludedHeaders.insert(Inc.Written);
264 if (!Inc.Resolved.empty())
265 IncludedHeaders.insert(Inc.Resolved);
266}
267
268/// FIXME(ioeric): we might not want to insert an absolute include path if the
269/// path is not shortened.
271 PathRef DeclaringHeader, const HeaderFile &InsertedHeader) const {
272 assert(InsertedHeader.valid());
273 if (!HeaderSearchInfo && !InsertedHeader.Verbatim)
274 return false;
275 if (FileName == DeclaringHeader || FileName == InsertedHeader.File)
276 return false;
277 auto Included = [&](llvm::StringRef Header) {
278 return IncludedHeaders.contains(Header);
279 };
280 return !Included(DeclaringHeader) && !Included(InsertedHeader.File);
281}
282
283std::optional<std::string>
285 llvm::StringRef IncludingFile) const {
286 assert(InsertedHeader.valid());
287 if (InsertedHeader.Verbatim)
288 return InsertedHeader.File;
289 bool IsAngled = false;
290 std::string Suggested;
291 if (HeaderSearchInfo) {
292 Suggested = HeaderSearchInfo->suggestPathToFileForDiagnostics(
293 InsertedHeader.File, BuildDir, IncludingFile, &IsAngled);
294 } else {
295 // Calculate include relative to including file only.
296 StringRef IncludingDir = llvm::sys::path::parent_path(IncludingFile);
297 SmallString<256> RelFile(InsertedHeader.File);
298 // Replacing with "" leaves "/RelFile" if IncludingDir doesn't end in "/".
299 llvm::sys::path::replace_path_prefix(RelFile, IncludingDir, "./");
300 Suggested = llvm::sys::path::convert_to_slash(
301 llvm::sys::path::remove_leading_dotslash(RelFile));
302 }
303 // FIXME: should we allow (some limited number of) "../header.h"?
304 if (llvm::sys::path::is_absolute(Suggested))
305 return std::nullopt;
306 if (IsAngled)
307 Suggested = "<" + Suggested + ">";
308 else
309 Suggested = "\"" + Suggested + "\"";
310 return Suggested;
311}
312
313std::optional<TextEdit>
314IncludeInserter::insert(llvm::StringRef VerbatimHeader,
315 tooling::IncludeDirective Directive) const {
316 std::optional<TextEdit> Edit;
317 if (auto Insertion =
318 Inserter.insert(VerbatimHeader.trim("\"<>"),
319 VerbatimHeader.startswith("<"), Directive))
320 Edit = replacementToEdit(Code, *Insertion);
321 return Edit;
322}
323
324llvm::raw_ostream &operator<<(llvm::raw_ostream &OS, const Inclusion &Inc) {
325 return OS << Inc.Written << " = "
326 << (!Inc.Resolved.empty() ? Inc.Resolved : "[unresolved]")
327 << " at line" << Inc.HashLine;
328}
329
330bool operator==(const Inclusion &LHS, const Inclusion &RHS) {
331 return std::tie(LHS.Directive, LHS.FileKind, LHS.HashOffset, LHS.HashLine,
332 LHS.Resolved, LHS.Written) ==
333 std::tie(RHS.Directive, RHS.FileKind, RHS.HashOffset, RHS.HashLine,
334 RHS.Resolved, RHS.Written);
335}
336
337} // namespace clangd
338} // namespace clang
CompiledFragmentImpl & Out
ASTNode Root
Definition: DumpAST.cpp:341
const Node * Parent
bool IsAngled
true if this was an include with angle brackets
StringRef FileName
SourceLocation Loc
const MacroDirective * Directive
std::unique_ptr< CompilerInvocation > CI
llvm::raw_string_ostream OS
Definition: TraceTests.cpp:160
void addExisting(const Inclusion &Inc)
Definition: Headers.cpp:262
std::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:284
bool shouldInsertInclude(PathRef DeclaringHeader, const HeaderFile &InsertedHeader) const
Checks whether to add an #include of the header into File.
Definition: Headers.cpp:270
std::optional< TextEdit > insert(llvm::StringRef VerbatimHeader, tooling::IncludeDirective Directive) const
Calculates an edit that inserts VerbatimHeader into code.
Definition: Headers.cpp:314
void FileChanged(SourceLocation Loc, FileChangeReason Reason, SrcMgr::CharacteristicKind FileType, FileID PrevFID) override
Definition: Headers.cpp:96
RecordHeaders(const CompilerInstance &CI, IncludeStructure *Out)
Definition: Headers.cpp:32
void InclusionDirective(SourceLocation HashLoc, const Token &IncludeTok, llvm::StringRef FileName, bool IsAngled, CharSourceRange, OptionalFileEntryRef File, llvm::StringRef, llvm::StringRef, const clang::Module *, SrcMgr::CharacteristicKind FileKind) override
Definition: Headers.cpp:38
llvm::SmallVector< const Inclusion * > mainFileIncludesWithSpelling(llvm::StringRef Spelling) const
Definition: Headers.cpp:255
static const HeaderID MainFileID
Definition: Headers.h:184
llvm::DenseMap< HeaderID, unsigned > includeDepth(HeaderID Root=MainFileID) const
Definition: Headers.cpp:227
std::vector< Inclusion > MainFileIncludes
Definition: Headers.h:174
std::vector< std::string > SearchPathsCanonical
Definition: Headers.h:179
llvm::DenseMap< tooling::stdlib::Header, llvm::SmallVector< HeaderID > > StdlibHeaders
Definition: Headers.h:172
HeaderID getOrCreateID(FileEntryRef Entry)
Definition: Headers.cpp:207
void collect(const CompilerInstance &CI)
Definition: Headers.cpp:177
std::optional< HeaderID > getID(const FileEntry *Entry) const
Definition: Headers.cpp:196
llvm::DenseMap< HeaderID, SmallVector< HeaderID > > IncludeChildren
Definition: Headers.h:169
static llvm::Expected< std::string > includeSpelling(const URI &U)
Gets the preferred spelling of this file for #include, if there is one, e.g.
Definition: URI.cpp:273
static llvm::Expected< std::string > resolve(const URI &U, llvm::StringRef HintPath="")
Resolves the absolute path of U.
Definition: URI.cpp:245
static llvm::Expected< URI > parse(llvm::StringRef Uri)
Parse a URI string "<scheme>:[//<authority>/]<path>".
Definition: URI.cpp:177
bool isLiteralInclude(llvm::StringRef Include)
Returns true if Include is literal include like "path" or <path>.
Definition: Headers.cpp:133
bool isInsideMainFile(SourceLocation Loc, const SourceManager &SM)
Returns true iff Loc is inside the main file.
Definition: SourceCode.cpp:419
bool operator==(const Inclusion &LHS, const Inclusion &RHS)
Definition: Headers.cpp:330
llvm::raw_ostream & operator<<(llvm::raw_ostream &OS, const CodeCompletion &C)
SourceLocation translatePreamblePatchLocation(SourceLocation Loc, const SourceManager &SM)
Translates locations inside preamble patch to their main-file equivalent using presumed locations.
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:142
std::optional< std::string > getCanonicalPath(const FileEntryRef F, FileManager &FileMgr)
Get the canonical path of F.
Definition: SourceCode.cpp:516
llvm::SmallVector< SymbolInclude, 1 > getRankedIncludes(const Symbol &Sym)
Definition: Headers.cpp:162
llvm::StringRef PathRef
A typedef to represent a ref to file path.
Definition: Path.h:29
TextEdit replacementToEdit(llvm::StringRef Code, const tooling::Replacement &R)
Definition: SourceCode.cpp:500
===– Representation.cpp - ClangDoc Representation --------—*- C++ -*-===//
A set of edits generated for a single file.
Definition: SourceCode.h:185
Represents a header file to be #include'd.
Definition: Headers.h:40
bool Verbatim
If this is true, File is a literal string quoted with <> or "" that can be #included directly; otherw...
Definition: Headers.h:44
std::string Written
Definition: Headers.h:70
tok::PPKeywordKind Directive
Definition: Headers.h:69
SrcMgr::CharacteristicKind FileKind
Definition: Headers.h:74
uint32_t References
The number of translation units that reference this symbol and include this header.
Definition: Symbol.h:119
llvm::StringRef IncludeHeader
This can be either a URI of the header to be #include'd for this symbol, or a literal header quoted w...
Definition: Symbol.h:116
The class presents a C++ symbol, e.g.
Definition: Symbol.h:39
llvm::SmallVector< IncludeHeaderWithReferences, 1 > IncludeHeaders
One Symbol can potentially be included via different headers.
Definition: Symbol.h:133