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 | |
26 | namespace clang { |
27 | namespace clangd { |
28 | |
29 | class IncludeStructure:: : public PPCallbacks { |
30 | public: |
31 | (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 (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 = 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 (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 | |
118 | private: |
119 | // Keeps track of include depth for the current file. It's 1 for main file. |
120 | int = 0; |
121 | bool inMainFile() const { return Level == 1; } |
122 | |
123 | const SourceManager &; |
124 | // Set after entering the <built-in> file. |
125 | FileID ; |
126 | // Indicates whether <built-in> file is part of include stack. |
127 | bool = false; |
128 | |
129 | IncludeStructure *; |
130 | }; |
131 | |
132 | bool isLiteralInclude(llvm::StringRef Include) { |
133 | return Include.startswith("<" ) || Include.startswith("\"" ); |
134 | } |
135 | |
136 | bool HeaderFile::() const { |
137 | return (Verbatim && isLiteralInclude(File)) || |
138 | (!Verbatim && llvm::sys::path::is_absolute(File)); |
139 | } |
140 | |
141 | llvm::Expected<HeaderFile> (llvm::StringRef , |
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 | |
161 | llvm::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> ; |
171 | for (const auto &Include : Includes) |
172 | Headers.push_back({Include.IncludeHeader, Include.supportedDirectives()}); |
173 | return Headers; |
174 | } |
175 | |
176 | void 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 | |
183 | std::optional<IncludeStructure::HeaderID> |
184 | IncludeStructure::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 | |
195 | IncludeStructure::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 | |
214 | llvm::DenseMap<IncludeStructure::HeaderID, unsigned> |
215 | IncludeStructure::(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 | |
242 | llvm::SmallVector<const Inclusion *> |
243 | IncludeStructure::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 | |
250 | void 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. |
258 | bool IncludeInserter::( |
259 | PathRef , const HeaderFile &) 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 ) { |
266 | return IncludedHeaders.contains(Header); |
267 | }; |
268 | return !Included(DeclaringHeader) && !Included(InsertedHeader.File); |
269 | } |
270 | |
271 | std::optional<std::string> |
272 | IncludeInserter::(const HeaderFile &, |
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 | |
301 | std::optional<TextEdit> |
302 | IncludeInserter::insert(llvm::StringRef , |
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 | |
312 | llvm::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 | |
318 | bool 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 | |