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 "Compiler.h"
11 #include "Preamble.h"
12 #include "SourceCode.h"
13 #include "support/Logger.h"
14 #include "clang/Basic/SourceLocation.h"
15 #include "clang/Basic/SourceManager.h"
16 #include "clang/Frontend/CompilerInstance.h"
17 #include "clang/Frontend/CompilerInvocation.h"
18 #include "clang/Frontend/FrontendActions.h"
19 #include "clang/Lex/HeaderSearch.h"
20 #include "llvm/ADT/StringRef.h"
21 #include "llvm/Support/Path.h"
22
23 namespace clang {
24 namespace clangd {
25 namespace {
26
27 class RecordHeaders : public PPCallbacks {
28 public:
RecordHeaders(const SourceManager & SM,IncludeStructure * Out)29 RecordHeaders(const SourceManager &SM, IncludeStructure *Out)
30 : SM(SM), Out(Out) {}
31
32 // Record existing #includes - both written and resolved paths. Only #includes
33 // in the main file are collected.
InclusionDirective(SourceLocation HashLoc,const Token & IncludeTok,llvm::StringRef FileName,bool IsAngled,CharSourceRange,const FileEntry * File,llvm::StringRef,llvm::StringRef,const Module *,SrcMgr::CharacteristicKind FileKind)34 void InclusionDirective(SourceLocation HashLoc, const Token &IncludeTok,
35 llvm::StringRef FileName, bool IsAngled,
36 CharSourceRange /*FilenameRange*/,
37 const FileEntry *File, llvm::StringRef /*SearchPath*/,
38 llvm::StringRef /*RelativePath*/,
39 const Module * /*Imported*/,
40 SrcMgr::CharacteristicKind FileKind) override {
41 auto MainFID = SM.getMainFileID();
42 // If an include is part of the preamble patch, translate #line directives.
43 if (InBuiltinFile)
44 HashLoc = translatePreamblePatchLocation(HashLoc, SM);
45
46 // Record main-file inclusions (including those mapped from the preamble
47 // patch).
48 if (isInsideMainFile(HashLoc, SM)) {
49 Out->MainFileIncludes.emplace_back();
50 auto &Inc = Out->MainFileIncludes.back();
51 Inc.Written =
52 (IsAngled ? "<" + FileName + ">" : "\"" + FileName + "\"").str();
53 Inc.Resolved = std::string(File ? File->tryGetRealPathName() : "");
54 Inc.HashOffset = SM.getFileOffset(HashLoc);
55 Inc.HashLine =
56 SM.getLineNumber(SM.getFileID(HashLoc), Inc.HashOffset) - 1;
57 Inc.FileKind = FileKind;
58 Inc.Directive = IncludeTok.getIdentifierInfo()->getPPKeywordID();
59 }
60
61 // Record include graph (not just for main-file includes)
62 if (File) {
63 auto *IncludingFileEntry = SM.getFileEntryForID(SM.getFileID(HashLoc));
64 if (!IncludingFileEntry) {
65 assert(SM.getBufferName(HashLoc).startswith("<") &&
66 "Expected #include location to be a file or <built-in>");
67 // Treat as if included from the main file.
68 IncludingFileEntry = SM.getFileEntryForID(MainFID);
69 }
70 Out->recordInclude(IncludingFileEntry->getName(), File->getName(),
71 File->tryGetRealPathName());
72 }
73 }
74
FileChanged(SourceLocation Loc,FileChangeReason Reason,SrcMgr::CharacteristicKind FileType,FileID PrevFID)75 void FileChanged(SourceLocation Loc, FileChangeReason Reason,
76 SrcMgr::CharacteristicKind FileType,
77 FileID PrevFID) override {
78 switch (Reason) {
79 case PPCallbacks::EnterFile:
80 if (BuiltinFile.isInvalid() && SM.isWrittenInBuiltinFile(Loc)) {
81 BuiltinFile = SM.getFileID(Loc);
82 InBuiltinFile = true;
83 }
84 break;
85 case PPCallbacks::ExitFile:
86 if (PrevFID == BuiltinFile)
87 InBuiltinFile = false;
88 break;
89 case PPCallbacks::RenameFile:
90 case PPCallbacks::SystemHeaderPragma:
91 break;
92 }
93 }
94
95 private:
96 const SourceManager &SM;
97 // Set after entering the <built-in> file.
98 FileID BuiltinFile;
99 // Indicates whether <built-in> file is part of include stack.
100 bool InBuiltinFile = false;
101
102 IncludeStructure *Out;
103 };
104
105 } // namespace
106
isLiteralInclude(llvm::StringRef Include)107 bool isLiteralInclude(llvm::StringRef Include) {
108 return Include.startswith("<") || Include.startswith("\"");
109 }
110
valid() const111 bool HeaderFile::valid() const {
112 return (Verbatim && isLiteralInclude(File)) ||
113 (!Verbatim && llvm::sys::path::is_absolute(File));
114 }
115
toHeaderFile(llvm::StringRef Header,llvm::StringRef HintPath)116 llvm::Expected<HeaderFile> toHeaderFile(llvm::StringRef Header,
117 llvm::StringRef HintPath) {
118 if (isLiteralInclude(Header))
119 return HeaderFile{Header.str(), /*Verbatim=*/true};
120 auto U = URI::parse(Header);
121 if (!U)
122 return U.takeError();
123
124 auto IncludePath = URI::includeSpelling(*U);
125 if (!IncludePath)
126 return IncludePath.takeError();
127 if (!IncludePath->empty())
128 return HeaderFile{std::move(*IncludePath), /*Verbatim=*/true};
129
130 auto Resolved = URI::resolve(*U, HintPath);
131 if (!Resolved)
132 return Resolved.takeError();
133 return HeaderFile{std::move(*Resolved), /*Verbatim=*/false};
134 }
135
getRankedIncludes(const Symbol & Sym)136 llvm::SmallVector<llvm::StringRef, 1> getRankedIncludes(const Symbol &Sym) {
137 auto Includes = Sym.IncludeHeaders;
138 // Sort in descending order by reference count and header length.
139 llvm::sort(Includes, [](const Symbol::IncludeHeaderWithReferences &LHS,
140 const Symbol::IncludeHeaderWithReferences &RHS) {
141 if (LHS.References == RHS.References)
142 return LHS.IncludeHeader.size() < RHS.IncludeHeader.size();
143 return LHS.References > RHS.References;
144 });
145 llvm::SmallVector<llvm::StringRef, 1> Headers;
146 for (const auto &Include : Includes)
147 Headers.push_back(Include.IncludeHeader);
148 return Headers;
149 }
150
151 std::unique_ptr<PPCallbacks>
collectIncludeStructureCallback(const SourceManager & SM,IncludeStructure * Out)152 collectIncludeStructureCallback(const SourceManager &SM,
153 IncludeStructure *Out) {
154 return std::make_unique<RecordHeaders>(SM, Out);
155 }
156
recordInclude(llvm::StringRef IncludingName,llvm::StringRef IncludedName,llvm::StringRef IncludedRealName)157 void IncludeStructure::recordInclude(llvm::StringRef IncludingName,
158 llvm::StringRef IncludedName,
159 llvm::StringRef IncludedRealName) {
160 auto Child = fileIndex(IncludedName);
161 if (!IncludedRealName.empty() && RealPathNames[Child].empty())
162 RealPathNames[Child] = std::string(IncludedRealName);
163 auto Parent = fileIndex(IncludingName);
164 IncludeChildren[Parent].push_back(Child);
165 }
166
fileIndex(llvm::StringRef Name)167 unsigned IncludeStructure::fileIndex(llvm::StringRef Name) {
168 auto R = NameToIndex.try_emplace(Name, RealPathNames.size());
169 if (R.second)
170 RealPathNames.emplace_back();
171 return R.first->getValue();
172 }
173
174 llvm::StringMap<unsigned>
includeDepth(llvm::StringRef Root) const175 IncludeStructure::includeDepth(llvm::StringRef Root) const {
176 // Include depth 0 is the main file only.
177 llvm::StringMap<unsigned> Result;
178 Result[Root] = 0;
179 std::vector<unsigned> CurrentLevel;
180 llvm::DenseSet<unsigned> Seen;
181 auto It = NameToIndex.find(Root);
182 if (It != NameToIndex.end()) {
183 CurrentLevel.push_back(It->second);
184 Seen.insert(It->second);
185 }
186
187 // Each round of BFS traversal finds the next depth level.
188 std::vector<unsigned> PreviousLevel;
189 for (unsigned Level = 1; !CurrentLevel.empty(); ++Level) {
190 PreviousLevel.clear();
191 PreviousLevel.swap(CurrentLevel);
192 for (const auto &Parent : PreviousLevel) {
193 for (const auto &Child : IncludeChildren.lookup(Parent)) {
194 if (Seen.insert(Child).second) {
195 CurrentLevel.push_back(Child);
196 const auto &Name = RealPathNames[Child];
197 // Can't include files if we don't have their real path.
198 if (!Name.empty())
199 Result[Name] = Level;
200 }
201 }
202 }
203 }
204 return Result;
205 }
206
addExisting(const Inclusion & Inc)207 void IncludeInserter::addExisting(const Inclusion &Inc) {
208 IncludedHeaders.insert(Inc.Written);
209 if (!Inc.Resolved.empty())
210 IncludedHeaders.insert(Inc.Resolved);
211 }
212
213 /// FIXME(ioeric): we might not want to insert an absolute include path if the
214 /// path is not shortened.
shouldInsertInclude(PathRef DeclaringHeader,const HeaderFile & InsertedHeader) const215 bool IncludeInserter::shouldInsertInclude(
216 PathRef DeclaringHeader, const HeaderFile &InsertedHeader) const {
217 assert(InsertedHeader.valid());
218 if (!HeaderSearchInfo && !InsertedHeader.Verbatim)
219 return false;
220 if (FileName == DeclaringHeader || FileName == InsertedHeader.File)
221 return false;
222 auto Included = [&](llvm::StringRef Header) {
223 return IncludedHeaders.find(Header) != IncludedHeaders.end();
224 };
225 return !Included(DeclaringHeader) && !Included(InsertedHeader.File);
226 }
227
228 llvm::Optional<std::string>
calculateIncludePath(const HeaderFile & InsertedHeader,llvm::StringRef IncludingFile) const229 IncludeInserter::calculateIncludePath(const HeaderFile &InsertedHeader,
230 llvm::StringRef IncludingFile) const {
231 assert(InsertedHeader.valid());
232 if (InsertedHeader.Verbatim)
233 return InsertedHeader.File;
234 bool IsSystem = false;
235 std::string Suggested;
236 if (HeaderSearchInfo) {
237 Suggested = HeaderSearchInfo->suggestPathToFileForDiagnostics(
238 InsertedHeader.File, BuildDir, IncludingFile, &IsSystem);
239 } else {
240 // Calculate include relative to including file only.
241 StringRef IncludingDir = llvm::sys::path::parent_path(IncludingFile);
242 SmallString<256> RelFile(InsertedHeader.File);
243 // Replacing with "" leaves "/RelFile" if IncludingDir doesn't end in "/".
244 llvm::sys::path::replace_path_prefix(RelFile, IncludingDir, "./");
245 Suggested = llvm::sys::path::convert_to_slash(
246 llvm::sys::path::remove_leading_dotslash(RelFile));
247 }
248 // FIXME: should we allow (some limited number of) "../header.h"?
249 if (llvm::sys::path::is_absolute(Suggested))
250 return None;
251 if (IsSystem)
252 Suggested = "<" + Suggested + ">";
253 else
254 Suggested = "\"" + Suggested + "\"";
255 return Suggested;
256 }
257
258 llvm::Optional<TextEdit>
insert(llvm::StringRef VerbatimHeader) const259 IncludeInserter::insert(llvm::StringRef VerbatimHeader) const {
260 llvm::Optional<TextEdit> Edit = None;
261 if (auto Insertion = Inserter.insert(VerbatimHeader.trim("\"<>"),
262 VerbatimHeader.startswith("<")))
263 Edit = replacementToEdit(Code, *Insertion);
264 return Edit;
265 }
266
operator <<(llvm::raw_ostream & OS,const Inclusion & Inc)267 llvm::raw_ostream &operator<<(llvm::raw_ostream &OS, const Inclusion &Inc) {
268 return OS << Inc.Written << " = "
269 << (!Inc.Resolved.empty() ? Inc.Resolved : "[unresolved]")
270 << " at line" << Inc.HashLine;
271 }
272
operator ==(const Inclusion & LHS,const Inclusion & RHS)273 bool operator==(const Inclusion &LHS, const Inclusion &RHS) {
274 return std::tie(LHS.Directive, LHS.FileKind, LHS.HashOffset, LHS.HashLine,
275 LHS.Resolved, LHS.Written) ==
276 std::tie(RHS.Directive, RHS.FileKind, RHS.HashOffset, RHS.HashLine,
277 RHS.Resolved, RHS.Written);
278 }
279 } // namespace clangd
280 } // namespace clang
281