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