| 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 |