Debian Codegraph @

llvm-project/clang-tools-extra/clangd/Headers.cpp

raw
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/StringRef.h"
20 #include "llvm/Support/Path.h"
21 #include <cstring>
22 #include <optional>
23
24 namespace clang {
25 namespace clangd {
26
27 class IncludeStructure::RecordHeaders : public PPCallbacks,
28 public CommentHandler {
29 public:
30 RecordHeaders(const CompilerInstance &CI, IncludeStructure *Out)
31 : SM(CI.getSourceManager()),
32 HeaderInfo(CI.getPreprocessor().getHeaderSearchInfo()), Out(Out) {}
33
34 // Record existing #includes - both written and resolved paths. Only #includes
35 // in the main file are collected.
36 void InclusionDirective(SourceLocation HashLoc, const Token &IncludeTok,
37 llvm::StringRef FileName, bool IsAngled,
38 CharSourceRange /*FilenameRange*/,
39 OptionalFileEntryRef File,
40 llvm::StringRef /*SearchPath*/,
41 llvm::StringRef /*RelativePath*/,
42 const clang::Module * /*Imported*/,
43 SrcMgr::CharacteristicKind FileKind) override {
44 auto MainFID = SM.getMainFileID();
45 // If an include is part of the preamble patch, translate #line directives.
46 if (InBuiltinFile)
47 HashLoc = translatePreamblePatchLocation(HashLoc, SM);
48
49 // Record main-file inclusions (including those mapped from the preamble
50 // patch).
51 if (isInsideMainFile(HashLoc, SM)) {
52 Out->MainFileIncludes.emplace_back();
53 auto &Inc = Out->MainFileIncludes.back();
54 Inc.Written =
55 (IsAngled ? "<" + FileName + ">" : "\"" + FileName + "\"").str();
56 Inc.Resolved =
57 std::string(File ? File->getFileEntry().tryGetRealPathName() : "");
58 Inc.HashOffset = SM.getFileOffset(HashLoc);
59 Inc.HashLine =
60 SM.getLineNumber(SM.getFileID(HashLoc), Inc.HashOffset) - 1;
61 Inc.FileKind = FileKind;
62 Inc.Directive = IncludeTok.getIdentifierInfo()->getPPKeywordID();
63 if (LastPragmaKeepInMainFileLine == Inc.HashLine)
64 Inc.BehindPragmaKeep = true;
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 }
77
78 // Record include graph (not just for main-file includes)
79 if (File) {
80 auto IncludingFileEntry = SM.getFileEntryRefForID(SM.getFileID(HashLoc));
81 if (!IncludingFileEntry) {
82 assert(SM.getBufferName(HashLoc).startswith("<") &&
83 "Expected #include location to be a file or <built-in>");
84 // Treat as if included from the main file.
85 IncludingFileEntry = SM.getFileEntryRefForID(MainFID);
86 }
87 auto IncludingID = Out->getOrCreateID(*IncludingFileEntry),
88 IncludedID = Out->getOrCreateID(*File);
89 Out->IncludeChildren[IncludingID].push_back(IncludedID);
90 }
91 }
92
93 void FileChanged(SourceLocation Loc, FileChangeReason Reason,
94 SrcMgr::CharacteristicKind FileType,
95 FileID PrevFID) override {
96 switch (Reason) {
97 case PPCallbacks::EnterFile:
98 ++Level;
99 if (BuiltinFile.isInvalid() && SM.isWrittenInBuiltinFile(Loc)) {
100 BuiltinFile = SM.getFileID(Loc);
101 InBuiltinFile = true;
102 }
103 break;
104 case PPCallbacks::ExitFile: {
105 --Level;
106 if (PrevFID == BuiltinFile)
107 InBuiltinFile = false;
108 // At file exit time HeaderSearchInfo is valid and can be used to
109 // determine whether the file was a self-contained header or not.
110 if (const FileEntry *FE = SM.getFileEntryForID(PrevFID)) {
111 // isSelfContainedHeader only returns true once the full header-guard
112 // structure has been seen, i.e. when exiting the *outer* copy of the
113 // file. So last result wins.
114 if (tooling::isSelfContainedHeader(FE, SM, HeaderInfo))
115 Out->NonSelfContained.erase(*Out->getID(FE));
116 else
117 Out->NonSelfContained.insert(*Out->getID(FE));
118 }
119 break;
120 }
121 case PPCallbacks::RenameFile:
122 case PPCallbacks::SystemHeaderPragma:
123 break;
124 }
125 }
126
127 bool HandleComment(Preprocessor &PP, SourceRange Range) override {
128 auto Pragma =
129 tooling::parseIWYUPragma(SM.getCharacterData(Range.getBegin()));
130 if (!Pragma)
131 return false;
132
133 if (inMainFile()) {
134 // Given:
135 //
136 // #include "foo.h"
137 // #include "bar.h" // IWYU pragma: keep
138 //
139 // The order in which the callbacks will be triggered:
140 //
141 // 1. InclusionDirective("foo.h")
142 // 2. handleCommentInMainFile("// IWYU pragma: keep")
143 // 3. InclusionDirective("bar.h")
144 //
145 // This code stores the last location of "IWYU pragma: keep" (or export)
146 // comment in the main file, so that when InclusionDirective is called, it
147 // will know that the next inclusion is behind the IWYU pragma.
148 // FIXME: Support "IWYU pragma: begin_exports" and "IWYU pragma:
149 // end_exports".
150 if (!Pragma->startswith("export") && !Pragma->startswith("keep"))
151 return false;
152 unsigned Offset = SM.getFileOffset(Range.getBegin());
153 LastPragmaKeepInMainFileLine =
154 SM.getLineNumber(SM.getMainFileID(), Offset) - 1;
155 } else {
156 // Memorize headers that have export pragmas in them. Include Cleaner
157 // does not support them properly yet, so they will be not marked as
158 // unused.
159 // FIXME: Once IncludeCleaner supports export pragmas, remove this.
160 if (!Pragma->startswith("export") && !Pragma->startswith("begin_exports"))
161 return false;
162 Out->HasIWYUExport.insert(
163 *Out->getID(SM.getFileEntryForID(SM.getFileID(Range.getBegin()))));
164 }
165 return false;
166 }
167
168 private:
169 // Keeps track of include depth for the current file. It's 1 for main file.
170 int Level = 0;
171 bool inMainFile() const { return Level == 1; }
172
173 const SourceManager &SM;
174 HeaderSearch &HeaderInfo;
175 // Set after entering the <built-in> file.
176 FileID BuiltinFile;
177 // Indicates whether <built-in> file is part of include stack.
178 bool InBuiltinFile = false;
179
180 IncludeStructure *Out;
181
182 // The last line "IWYU pragma: keep" was seen in the main file, 0-indexed.
183 int LastPragmaKeepInMainFileLine = -1;
184 };
185
186 bool isLiteralInclude(llvm::StringRef Include) {
187 return Include.startswith("<") || Include.startswith("\"");
188 }
189
190 bool HeaderFile::valid() const {
191 return (Verbatim && isLiteralInclude(File)) ||
192 (!Verbatim && llvm::sys::path::is_absolute(File));
193 }
194
195 llvm::Expected<HeaderFile> toHeaderFile(llvm::StringRef Header,
196 llvm::StringRef HintPath) {
197 if (isLiteralInclude(Header))
198 return HeaderFile{Header.str(), /*Verbatim=*/true};
199 auto U = URI::parse(Header);
200 if (!U)
201 return U.takeError();
202
203 auto IncludePath = URI::includeSpelling(*U);
204 if (!IncludePath)
205 return IncludePath.takeError();
206 if (!IncludePath->empty())
207 return HeaderFile{std::move(*IncludePath), /*Verbatim=*/true};
208
209 auto Resolved = URI::resolve(*U, HintPath);
210 if (!Resolved)
211 return Resolved.takeError();
212 return HeaderFile{std::move(*Resolved), /*Verbatim=*/false};
213 }
214
215 llvm::SmallVector<SymbolInclude, 1> getRankedIncludes(const Symbol &Sym) {
216 auto Includes = Sym.IncludeHeaders;
217 // Sort in descending order by reference count and header length.
218 llvm::sort(Includes, [](const Symbol::IncludeHeaderWithReferences &LHS,
219 const Symbol::IncludeHeaderWithReferences &RHS) {
220 if (LHS.References == RHS.References)
221 return LHS.IncludeHeader.size() < RHS.IncludeHeader.size();
222 return LHS.References > RHS.References;
223 });
224 llvm::SmallVector<SymbolInclude, 1> Headers;
225 for (const auto &Include : Includes)
226 Headers.push_back({Include.IncludeHeader, Include.supportedDirectives()});
227 return Headers;
228 }
229
230 void IncludeStructure::collect(const CompilerInstance &CI) {
231 auto &SM = CI.getSourceManager();
232 MainFileEntry = SM.getFileEntryForID(SM.getMainFileID());
233 auto Collector = std::make_unique<RecordHeaders>(CI, this);
234 CI.getPreprocessor().addCommentHandler(Collector.get());
235 CI.getPreprocessor().addPPCallbacks(std::move(Collector));
236 }
237
238 std::optional<IncludeStructure::HeaderID>
239 IncludeStructure::getID(const FileEntry *Entry) const {
240 // HeaderID of the main file is always 0;
241 if (Entry == MainFileEntry) {
242 return static_cast<IncludeStructure::HeaderID>(0u);
243 }
244 auto It = UIDToIndex.find(Entry->getUniqueID());
245 if (It == UIDToIndex.end())
246 return std::nullopt;
247 return It->second;
248 }
249
250 IncludeStructure::HeaderID IncludeStructure::getOrCreateID(FileEntryRef Entry) {
251 // Main file's FileEntry was not known at IncludeStructure creation time.
252 if (&Entry.getFileEntry() == MainFileEntry) {
253 if (RealPathNames.front().empty())
254 RealPathNames.front() = MainFileEntry->tryGetRealPathName().str();
255 return MainFileID;
256 }
257 auto R = UIDToIndex.try_emplace(
258 Entry.getUniqueID(),
259 static_cast<IncludeStructure::HeaderID>(RealPathNames.size()));
260 if (R.second)
261 RealPathNames.emplace_back();
262 IncludeStructure::HeaderID Result = R.first->getSecond();
263 std::string &RealPathName = RealPathNames[static_cast<unsigned>(Result)];
264 if (RealPathName.empty())
265 RealPathName = Entry.getFileEntry().tryGetRealPathName().str();
266 return Result;
267 }
268
269 llvm::DenseMap<IncludeStructure::HeaderID, unsigned>
270 IncludeStructure::includeDepth(HeaderID Root) const {
271 // Include depth 0 is the main file only.
272 llvm::DenseMap<HeaderID, unsigned> Result;
273 assert(static_cast<unsigned>(Root) < RealPathNames.size());
274 Result[Root] = 0;
275 std::vector<IncludeStructure::HeaderID> CurrentLevel;
276 CurrentLevel.push_back(Root);
277 llvm::DenseSet<IncludeStructure::HeaderID> Seen;
278 Seen.insert(Root);
279
280 // Each round of BFS traversal finds the next depth level.
281 std::vector<IncludeStructure::HeaderID> PreviousLevel;
282 for (unsigned Level = 1; !CurrentLevel.empty(); ++Level) {
283 PreviousLevel.clear();
284 PreviousLevel.swap(CurrentLevel);
285 for (const auto &Parent : PreviousLevel) {
286 for (const auto &Child : IncludeChildren.lookup(Parent)) {
287 if (Seen.insert(Child).second) {
288 CurrentLevel.push_back(Child);
289 Result[Child] = Level;
290 }
291 }
292 }
293 }
294 return Result;
295 }
296
297 void IncludeInserter::addExisting(const Inclusion &Inc) {
298 IncludedHeaders.insert(Inc.Written);
299 if (!Inc.Resolved.empty())
300 IncludedHeaders.insert(Inc.Resolved);
301 }
302
303 /// FIXME(ioeric): we might not want to insert an absolute include path if the
304 /// path is not shortened.
305 bool IncludeInserter::shouldInsertInclude(
306 PathRef DeclaringHeader, const HeaderFile &InsertedHeader) const {
307 assert(InsertedHeader.valid());
308 if (!HeaderSearchInfo && !InsertedHeader.Verbatim)
309 return false;
310 if (FileName == DeclaringHeader || FileName == InsertedHeader.File)
311 return false;
312 auto Included = [&](llvm::StringRef Header) {
313 return IncludedHeaders.find(Header) != IncludedHeaders.end();
314 };
315 return !Included(DeclaringHeader) && !Included(InsertedHeader.File);
316 }
317
318 std::optional<std::string>
319 IncludeInserter::calculateIncludePath(const HeaderFile &InsertedHeader,
320 llvm::StringRef IncludingFile) const {
321 assert(InsertedHeader.valid());
322 if (InsertedHeader.Verbatim)
323 return InsertedHeader.File;
324 bool IsSystem = false;
325 std::string Suggested;
326 if (HeaderSearchInfo) {
327 Suggested = HeaderSearchInfo->suggestPathToFileForDiagnostics(
328 InsertedHeader.File, BuildDir, IncludingFile, &IsSystem);
329 } else {
330 // Calculate include relative to including file only.
331 StringRef IncludingDir = llvm::sys::path::parent_path(IncludingFile);
332 SmallString<256> RelFile(InsertedHeader.File);
333 // Replacing with "" leaves "/RelFile" if IncludingDir doesn't end in "/".
334 llvm::sys::path::replace_path_prefix(RelFile, IncludingDir, "./");
335 Suggested = llvm::sys::path::convert_to_slash(
336 llvm::sys::path::remove_leading_dotslash(RelFile));
337 }
338 // FIXME: should we allow (some limited number of) "../header.h"?
339 if (llvm::sys::path::is_absolute(Suggested))
340 return std::nullopt;
341 if (IsSystem)
342 Suggested = "<" + Suggested + ">";
343 else
344 Suggested = "\"" + Suggested + "\"";
345 return Suggested;
346 }
347
348 std::optional<TextEdit>
349 IncludeInserter::insert(llvm::StringRef VerbatimHeader,
350 tooling::IncludeDirective Directive) const {
351 std::optional<TextEdit> Edit;
352 if (auto Insertion =
353 Inserter.insert(VerbatimHeader.trim("\"<>"),
354 VerbatimHeader.startswith("<"), Directive))
355 Edit = replacementToEdit(Code, *Insertion);
356 return Edit;
357 }
358
359 llvm::raw_ostream &operator<<(llvm::raw_ostream &OS, const Inclusion &Inc) {
360 return OS << Inc.Written << " = "
361 << (!Inc.Resolved.empty() ? Inc.Resolved : "[unresolved]")
362 << " at line" << Inc.HashLine;
363 }
364
365 bool operator==(const Inclusion &LHS, const Inclusion &RHS) {
366 return std::tie(LHS.Directive, LHS.FileKind, LHS.HashOffset, LHS.HashLine,
367 LHS.Resolved, LHS.Written) ==
368 std::tie(RHS.Directive, RHS.FileKind, RHS.HashOffset, RHS.HashLine,
369 RHS.Resolved, RHS.Written);
370 }
371
372 } // namespace clangd
373 } // namespace clang