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
30class IncludeStructure::RecordHeaders : public PPCallbacks {
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 * /*SuggestedModule*/,
45 bool /*ModuleImported*/,
46 SrcMgr::CharacteristicKind FileKind) override {
47 auto MainFID = SM.getMainFileID();
48 // If an include is part of the preamble patch, translate #line directives.
49 if (InBuiltinFile)
50 HashLoc = translatePreamblePatchLocation(Loc: HashLoc, SM);
51
52 // Record main-file inclusions (including those mapped from the preamble
53 // patch).
54 if (isInsideMainFile(Loc: HashLoc, SM)) {
55 Out->MainFileIncludes.emplace_back();
56 auto &Inc = Out->MainFileIncludes.back();
57 Inc.Written =
58 (IsAngled ? "<" + FileName + ">" : "\"" + FileName + "\"").str();
59 Inc.Resolved = std::string(
60 File ? getCanonicalPath(F: *File, FileMgr&: SM.getFileManager()).value_or(u: "")
61 : "");
62 Inc.HashOffset = SM.getFileOffset(SpellingLoc: HashLoc);
63 Inc.HashLine =
64 SM.getLineNumber(FID: SM.getFileID(SpellingLoc: HashLoc), FilePos: Inc.HashOffset) - 1;
65 Inc.FileKind = FileKind;
66 Inc.Directive = IncludeTok.getIdentifierInfo()->getPPKeywordID();
67 if (File) {
68 IncludeStructure::HeaderID HID = Out->getOrCreateID(Entry: *File);
69 Inc.HeaderID = static_cast<unsigned>(HID);
70 if (IsAngled)
71 if (auto StdlibHeader = tooling::stdlib::Header::named(Name: Inc.Written)) {
72 auto &IDs = Out->StdlibHeaders[*StdlibHeader];
73 // Few physical files for one stdlib header name, linear scan is ok.
74 if (!llvm::is_contained(Range&: IDs, Element: HID))
75 IDs.push_back(Elt: HID);
76 }
77 }
78 Out->MainFileIncludesBySpelling.try_emplace(Key: Inc.Written)
79 .first->second.push_back(Elt: Out->MainFileIncludes.size() - 1);
80 }
81
82 // Record include graph (not just for main-file includes)
83 if (File) {
84 auto IncludingFileEntry = SM.getFileEntryRefForID(FID: SM.getFileID(SpellingLoc: HashLoc));
85 if (!IncludingFileEntry) {
86 assert(SM.getBufferName(HashLoc).starts_with("<") &&
87 "Expected #include location to be a file or <built-in>");
88 // Treat as if included from the main file.
89 IncludingFileEntry = SM.getFileEntryRefForID(FID: MainFID);
90 }
91 auto IncludingID = Out->getOrCreateID(Entry: *IncludingFileEntry),
92 IncludedID = Out->getOrCreateID(Entry: *File);
93 Out->IncludeChildren[IncludingID].push_back(Elt: IncludedID);
94 }
95 }
96
97 void FileChanged(SourceLocation Loc, FileChangeReason Reason,
98 SrcMgr::CharacteristicKind FileType,
99 FileID PrevFID) override {
100 switch (Reason) {
101 case PPCallbacks::EnterFile:
102 ++Level;
103 if (BuiltinFile.isInvalid() && SM.isWrittenInBuiltinFile(Loc)) {
104 BuiltinFile = SM.getFileID(SpellingLoc: Loc);
105 InBuiltinFile = true;
106 }
107 break;
108 case PPCallbacks::ExitFile: {
109 --Level;
110 if (PrevFID == BuiltinFile)
111 InBuiltinFile = false;
112 break;
113 }
114 case PPCallbacks::RenameFile:
115 case PPCallbacks::SystemHeaderPragma:
116 break;
117 }
118 }
119
120private:
121 // Keeps track of include depth for the current file. It's 1 for main file.
122 int Level = 0;
123 bool inMainFile() const { return Level == 1; }
124
125 const SourceManager &SM;
126 // Set after entering the <built-in> file.
127 FileID BuiltinFile;
128 // Indicates whether <built-in> file is part of include stack.
129 bool InBuiltinFile = false;
130
131 IncludeStructure *Out;
132};
133
134bool isLiteralInclude(llvm::StringRef Include) {
135 return Include.starts_with(Prefix: "<") || Include.starts_with(Prefix: "\"");
136}
137
138bool HeaderFile::valid() const {
139 return (Verbatim && isLiteralInclude(Include: File)) ||
140 (!Verbatim && llvm::sys::path::is_absolute(path: File));
141}
142
143llvm::Expected<HeaderFile> toHeaderFile(llvm::StringRef Header,
144 llvm::StringRef HintPath) {
145 if (isLiteralInclude(Include: Header))
146 return HeaderFile{.File: Header.str(), /*Verbatim=*/true};
147 auto U = URI::parse(Uri: Header);
148 if (!U)
149 return U.takeError();
150
151 auto IncludePath = URI::includeSpelling(U: *U);
152 if (!IncludePath)
153 return IncludePath.takeError();
154 if (!IncludePath->empty())
155 return HeaderFile{.File: std::move(*IncludePath), /*Verbatim=*/true};
156
157 auto Resolved = URI::resolve(U: *U, HintPath);
158 if (!Resolved)
159 return Resolved.takeError();
160 return HeaderFile{.File: std::move(*Resolved), /*Verbatim=*/false};
161}
162
163llvm::SmallVector<SymbolInclude, 1> getRankedIncludes(const Symbol &Sym) {
164 auto Includes = Sym.IncludeHeaders;
165 // Sort in descending order by reference count and header length.
166 llvm::sort(C&: Includes, Comp: [](const Symbol::IncludeHeaderWithReferences &LHS,
167 const Symbol::IncludeHeaderWithReferences &RHS) {
168 if (LHS.References == RHS.References)
169 return LHS.IncludeHeader.size() < RHS.IncludeHeader.size();
170 return LHS.References > RHS.References;
171 });
172 llvm::SmallVector<SymbolInclude, 1> Headers;
173 for (const auto &Include : Includes)
174 Headers.push_back(Elt: {.Header: Include.IncludeHeader, .Directive: Include.supportedDirectives()});
175 return Headers;
176}
177
178void IncludeStructure::collect(const CompilerInstance &CI) {
179 auto &SM = CI.getSourceManager();
180 MainFileEntry = SM.getFileEntryForID(FID: SM.getMainFileID());
181 auto Collector = std::make_unique<RecordHeaders>(args: CI, args: this);
182 CI.getPreprocessor().addPPCallbacks(C: std::move(Collector));
183
184 // If we're reusing a preamble, don't repopulate SearchPathsCanonical.
185 // The entries will be the same, but canonicalizing to find out is expensive!
186 if (SearchPathsCanonical.empty()) {
187 for (const auto &Dir :
188 CI.getPreprocessor().getHeaderSearchInfo().search_dir_range()) {
189 if (Dir.getLookupType() == DirectoryLookup::LT_NormalDir)
190 SearchPathsCanonical.emplace_back(
191 args: SM.getFileManager().getCanonicalName(Dir: *Dir.getDirRef()));
192 }
193 }
194}
195
196std::optional<IncludeStructure::HeaderID>
197IncludeStructure::getID(const FileEntry *Entry) const {
198 // HeaderID of the main file is always 0;
199 if (Entry == MainFileEntry) {
200 return static_cast<IncludeStructure::HeaderID>(0u);
201 }
202 auto It = UIDToIndex.find(Val: Entry->getUniqueID());
203 if (It == UIDToIndex.end())
204 return std::nullopt;
205 return It->second;
206}
207
208IncludeStructure::HeaderID IncludeStructure::getOrCreateID(FileEntryRef Entry) {
209 // Main file's FileEntry was not known at IncludeStructure creation time.
210 if (&Entry.getFileEntry() == MainFileEntry) {
211 if (RealPathNames.front().empty())
212 RealPathNames.front() = MainFileEntry->tryGetRealPathName().str();
213 return MainFileID;
214 }
215 auto R = UIDToIndex.try_emplace(
216 Key: Entry.getUniqueID(),
217 Args: static_cast<IncludeStructure::HeaderID>(RealPathNames.size()));
218 if (R.second)
219 RealPathNames.emplace_back();
220 IncludeStructure::HeaderID Result = R.first->getSecond();
221 std::string &RealPathName = RealPathNames[static_cast<unsigned>(Result)];
222 if (RealPathName.empty())
223 RealPathName = Entry.getFileEntry().tryGetRealPathName().str();
224 return Result;
225}
226
227llvm::DenseMap<IncludeStructure::HeaderID, unsigned>
228IncludeStructure::includeDepth(HeaderID Root) const {
229 // Include depth 0 is the main file only.
230 llvm::DenseMap<HeaderID, unsigned> Result;
231 assert(static_cast<unsigned>(Root) < RealPathNames.size());
232 Result[Root] = 0;
233 std::vector<IncludeStructure::HeaderID> CurrentLevel;
234 CurrentLevel.push_back(x: Root);
235 llvm::DenseSet<IncludeStructure::HeaderID> Seen;
236 Seen.insert(V: Root);
237
238 // Each round of BFS traversal finds the next depth level.
239 std::vector<IncludeStructure::HeaderID> PreviousLevel;
240 for (unsigned Level = 1; !CurrentLevel.empty(); ++Level) {
241 PreviousLevel.clear();
242 PreviousLevel.swap(x&: CurrentLevel);
243 for (const auto &Parent : PreviousLevel) {
244 for (const auto &Child : IncludeChildren.lookup(Val: Parent)) {
245 if (Seen.insert(V: Child).second) {
246 CurrentLevel.push_back(x: Child);
247 Result[Child] = Level;
248 }
249 }
250 }
251 }
252 return Result;
253}
254
255llvm::SmallVector<const Inclusion *>
256IncludeStructure::mainFileIncludesWithSpelling(llvm::StringRef Spelling) const {
257 llvm::SmallVector<const Inclusion *> Includes;
258 for (auto Idx : MainFileIncludesBySpelling.lookup(Key: Spelling))
259 Includes.push_back(Elt: &MainFileIncludes[Idx]);
260 return Includes;
261}
262
263void IncludeInserter::addExisting(const Inclusion &Inc) {
264 IncludedHeaders.insert(key: Inc.Written);
265 if (!Inc.Resolved.empty())
266 IncludedHeaders.insert(key: Inc.Resolved);
267}
268
269/// FIXME(ioeric): we might not want to insert an absolute include path if the
270/// path is not shortened.
271bool IncludeInserter::shouldInsertInclude(
272 PathRef DeclaringHeader, const HeaderFile &InsertedHeader) const {
273 assert(InsertedHeader.valid());
274 if (!HeaderSearchInfo && !InsertedHeader.Verbatim)
275 return false;
276 if (FileName == DeclaringHeader || FileName == InsertedHeader.File)
277 return false;
278 auto Included = [&](llvm::StringRef Header) {
279 return IncludedHeaders.contains(key: Header);
280 };
281 return !Included(DeclaringHeader) && !Included(InsertedHeader.File);
282}
283
284std::optional<std::string>
285IncludeInserter::calculateIncludePath(const HeaderFile &InsertedHeader,
286 llvm::StringRef IncludingFile) const {
287 assert(InsertedHeader.valid());
288 if (InsertedHeader.Verbatim)
289 return InsertedHeader.File;
290 bool IsAngled = false;
291 std::string Suggested;
292 if (HeaderSearchInfo) {
293 Suggested = HeaderSearchInfo->suggestPathToFileForDiagnostics(
294 File: InsertedHeader.File, WorkingDir: BuildDir, MainFile: IncludingFile, IsAngled: &IsAngled);
295 } else {
296 // Calculate include relative to including file only.
297 StringRef IncludingDir = llvm::sys::path::parent_path(path: IncludingFile);
298 SmallString<256> RelFile(InsertedHeader.File);
299 // Replacing with "" leaves "/RelFile" if IncludingDir doesn't end in "/".
300 llvm::sys::path::replace_path_prefix(Path&: RelFile, OldPrefix: IncludingDir, NewPrefix: "./");
301 Suggested = llvm::sys::path::convert_to_slash(
302 path: llvm::sys::path::remove_leading_dotslash(path: RelFile));
303 }
304 // FIXME: should we allow (some limited number of) "../header.h"?
305 if (llvm::sys::path::is_absolute(path: Suggested))
306 return std::nullopt;
307 if (IsAngled)
308 Suggested = "<" + Suggested + ">";
309 else
310 Suggested = "\"" + Suggested + "\"";
311 return Suggested;
312}
313
314std::optional<TextEdit>
315IncludeInserter::insert(llvm::StringRef VerbatimHeader,
316 tooling::IncludeDirective Directive) const {
317 std::optional<TextEdit> Edit;
318 if (auto Insertion =
319 Inserter.insert(Header: VerbatimHeader.trim(Chars: "\"<>"),
320 IsAngled: VerbatimHeader.starts_with(Prefix: "<"), Directive))
321 Edit = replacementToEdit(Code, R: *Insertion);
322 return Edit;
323}
324
325llvm::raw_ostream &operator<<(llvm::raw_ostream &OS, const Inclusion &Inc) {
326 return OS << Inc.Written << " = "
327 << (!Inc.Resolved.empty() ? Inc.Resolved : "[unresolved]")
328 << " at line" << Inc.HashLine;
329}
330
331bool operator==(const Inclusion &LHS, const Inclusion &RHS) {
332 return std::tie(args: LHS.Directive, args: LHS.FileKind, args: LHS.HashOffset, args: LHS.HashLine,
333 args: LHS.Resolved, args: LHS.Written) ==
334 std::tie(args: RHS.Directive, args: RHS.FileKind, args: RHS.HashOffset, args: RHS.HashLine,
335 args: RHS.Resolved, args: RHS.Written);
336}
337
338} // namespace clangd
339} // namespace clang
340

source code of clang-tools-extra/clangd/Headers.cpp