| 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 |
|
| 27 |
namespace clang { |
| 28 |
namespace clangd { |
| 29 |
|
| 30 |
class IncludeStructure::RecordHeaders : public PPCallbacks { |
| 31 |
public: |
| 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(HashLoc, SM); |
| 51 |
|
| 52 |
// Record main-file inclusions (including those mapped from the preamble |
| 53 |
// patch). |
| 54 |
if (isInsideMainFile(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(*File, SM.getFileManager()).value_or("") |
| 61 |
: ""); |
| 62 |
Inc.HashOffset = SM.getFileOffset(HashLoc); |
| 63 |
Inc.HashLine = |
| 64 |
SM.getLineNumber(SM.getFileID(HashLoc), Inc.HashOffset) - 1; |
| 65 |
Inc.FileKind = FileKind; |
| 66 |
Inc.Directive = IncludeTok.getIdentifierInfo()->getPPKeywordID(); |
| 67 |
if (File) { |
| 68 |
IncludeStructure::HeaderID HID = Out->getOrCreateID(*File); |
| 69 |
Inc.HeaderID = static_cast<unsigned>(HID); |
| 70 |
if (IsAngled) |
| 71 |
if (auto StdlibHeader = tooling::stdlib::Header::named(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(IDs, HID)) |
| 75 |
IDs.push_back(HID); |
| 76 |
} |
| 77 |
} |
| 78 |
Out->MainFileIncludesBySpelling.try_emplace(Inc.Written) |
| 79 |
.first->second.push_back(Out->MainFileIncludes.size() - 1); |
| 80 |
} |
| 81 |
|
| 82 |
// Record include graph (not just for main-file includes) |
| 83 |
if (File) { |
| 84 |
auto IncludingFileEntry = SM.getFileEntryRefForID(SM.getFileID(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(MainFID); |
| 90 |
} |
| 91 |
auto IncludingID = Out->getOrCreateID(*IncludingFileEntry), |
| 92 |
IncludedID = Out->getOrCreateID(*File); |
| 93 |
Out->IncludeChildren[IncludingID].push_back(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(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 |
|
| 120 |
private: |
| 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 |
|
| 134 |
bool isLiteralInclude(llvm::StringRef Include) { |
| 135 |
return Include.starts_with("<") || Include.starts_with("\""); |
| 136 |
} |
| 137 |
|
| 138 |
bool HeaderFile::valid() const { |
| 139 |
return (Verbatim && isLiteralInclude(File)) || |
| 140 |
(!Verbatim && llvm::sys::path::is_absolute(File)); |
| 141 |
} |
| 142 |
|
| 143 |
llvm::Expected<HeaderFile> toHeaderFile(llvm::StringRef Header, |
| 144 |
llvm::StringRef HintPath) { |
| 145 |
if (isLiteralInclude(Header)) |
| 146 |
return HeaderFile{Header.str(), /*Verbatim=*/true}; |
| 147 |
auto U = URI::parse(Header); |
| 148 |
if (!U) |
| 149 |
return U.takeError(); |
| 150 |
|
| 151 |
auto IncludePath = URI::includeSpelling(*U); |
| 152 |
if (!IncludePath) |
| 153 |
return IncludePath.takeError(); |
| 154 |
if (!IncludePath->empty()) |
| 155 |
return HeaderFile{std::move(*IncludePath), /*Verbatim=*/true}; |
| 156 |
|
| 157 |
auto Resolved = URI::resolve(*U, HintPath); |
| 158 |
if (!Resolved) |
| 159 |
return Resolved.takeError(); |
| 160 |
return HeaderFile{std::move(*Resolved), /*Verbatim=*/false}; |
| 161 |
} |
| 162 |
|
| 163 |
llvm::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(Includes, [](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({Include.IncludeHeader, Include.supportedDirectives()}); |
| 175 |
return Headers; |
| 176 |
} |
| 177 |
|
| 178 |
void IncludeStructure::collect(const CompilerInstance &CI) { |
| 179 |
auto &SM = CI.getSourceManager(); |
| 180 |
MainFileEntry = SM.getFileEntryForID(SM.getMainFileID()); |
| 181 |
auto Collector = std::make_unique<RecordHeaders>(CI, this); |
| 182 |
CI.getPreprocessor().addPPCallbacks(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 |
SM.getFileManager().getCanonicalName(*Dir.getDirRef())); |
| 192 |
} |
| 193 |
} |
| 194 |
} |
| 195 |
|
| 196 |
std::optional<IncludeStructure::HeaderID> |
| 197 |
IncludeStructure::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(Entry->getUniqueID()); |
| 203 |
if (It == UIDToIndex.end()) |
| 204 |
return std::nullopt; |
| 205 |
return It->second; |
| 206 |
} |
| 207 |
|
| 208 |
IncludeStructure::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 |
Entry.getUniqueID(), |
| 217 |
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 |
|
| 227 |
llvm::DenseMap<IncludeStructure::HeaderID, unsigned> |
| 228 |
IncludeStructure::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(Root); |
| 235 |
llvm::DenseSet<IncludeStructure::HeaderID> Seen; |
| 236 |
Seen.insert(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(CurrentLevel); |
| 243 |
for (const auto &Parent : PreviousLevel) { |
| 244 |
for (const auto &Child : IncludeChildren.lookup(Parent)) { |
| 245 |
if (Seen.insert(Child).second) { |
| 246 |
CurrentLevel.push_back(Child); |
| 247 |
Result[Child] = Level; |
| 248 |
} |
| 249 |
} |
| 250 |
} |
| 251 |
} |
| 252 |
return Result; |
| 253 |
} |
| 254 |
|
| 255 |
llvm::SmallVector<const Inclusion *> |
| 256 |
IncludeStructure::mainFileIncludesWithSpelling(llvm::StringRef Spelling) const { |
| 257 |
llvm::SmallVector<const Inclusion *> Includes; |
| 258 |
for (auto Idx : MainFileIncludesBySpelling.lookup(Spelling)) |
| 259 |
Includes.push_back(&MainFileIncludes[Idx]); |
| 260 |
return Includes; |
| 261 |
} |
| 262 |
|
| 263 |
void IncludeInserter::addExisting(const Inclusion &Inc) { |
| 264 |
IncludedHeaders.insert(Inc.Written); |
| 265 |
if (!Inc.Resolved.empty()) |
| 266 |
IncludedHeaders.insert(Inc.Resolved); |
| 267 |
} |
| 268 |
|
| 269 |
/// FIXME(ioeric): we might not want to insert an absolute include path if the |
| 270 |
/// path is not shortened. |
| 271 |
bool 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(Header); |
| 280 |
}; |
| 281 |
return !Included(DeclaringHeader) && !Included(InsertedHeader.File); |
| 282 |
} |
| 283 |
|
| 284 |
std::optional<std::string> |
| 285 |
IncludeInserter::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 |
InsertedHeader.File, BuildDir, IncludingFile, &IsAngled); |
| 295 |
} else { |
| 296 |
// Calculate include relative to including file only. |
| 297 |
StringRef IncludingDir = llvm::sys::path::parent_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(RelFile, IncludingDir, "./"); |
| 301 |
Suggested = llvm::sys::path::convert_to_slash( |
| 302 |
llvm::sys::path::remove_leading_dotslash(RelFile)); |
| 303 |
} |
| 304 |
// FIXME: should we allow (some limited number of) "../header.h"? |
| 305 |
if (llvm::sys::path::is_absolute(Suggested)) |
| 306 |
return std::nullopt; |
| 307 |
if (IsAngled) |
| 308 |
Suggested = "<" + Suggested + ">"; |
| 309 |
else |
| 310 |
Suggested = "\"" + Suggested + "\""; |
| 311 |
return Suggested; |
| 312 |
} |
| 313 |
|
| 314 |
std::optional<TextEdit> |
| 315 |
IncludeInserter::insert(llvm::StringRef VerbatimHeader, |
| 316 |
tooling::IncludeDirective Directive) const { |
| 317 |
std::optional<TextEdit> Edit; |
| 318 |
if (auto Insertion = |
| 319 |
Inserter.insert(VerbatimHeader.trim("\"<>"), |
| 320 |
VerbatimHeader.starts_with("<"), Directive)) |
| 321 |
Edit = replacementToEdit(Code, *Insertion); |
| 322 |
return Edit; |
| 323 |
} |
| 324 |
|
| 325 |
llvm::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 |
|
| 331 |
bool operator==(const Inclusion &LHS, const Inclusion &RHS) { |
| 332 |
return std::tie(LHS.Directive, LHS.FileKind, LHS.HashOffset, LHS.HashLine, |
| 333 |
LHS.Resolved, LHS.Written) == |
| 334 |
std::tie(RHS.Directive, RHS.FileKind, RHS.HashOffset, RHS.HashLine, |
| 335 |
RHS.Resolved, RHS.Written); |
| 336 |
} |
| 337 |
|
| 338 |
} // namespace clangd |
| 339 |
} // namespace clang |