365 lines · cpp
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-exception6//7//===----------------------------------------------------------------------===//8 9#include "Headers.h"10#include "Preamble.h"11#include "SourceCode.h"12#include "support/Logger.h"13#include "clang/Basic/SourceLocation.h"14#include "clang/Basic/SourceManager.h"15#include "clang/Frontend/CompilerInstance.h"16#include "clang/Lex/DirectoryLookup.h"17#include "clang/Lex/HeaderSearch.h"18#include "clang/Lex/PPCallbacks.h"19#include "clang/Lex/Preprocessor.h"20#include "clang/Tooling/Inclusions/HeaderAnalysis.h"21#include "llvm/ADT/SmallVector.h"22#include "llvm/ADT/StringRef.h"23#include "llvm/Support/Path.h"24#include <cstring>25#include <optional>26#include <string>27 28namespace clang {29namespace clangd {30 31class IncludeStructure::RecordHeaders : public PPCallbacks {32public:33 RecordHeaders(const CompilerInstance &CI, IncludeStructure *Out)34 : SM(CI.getSourceManager()), Out(Out) {}35 36 // Record existing #includes - both written and resolved paths. Only #includes37 // 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 preamble53 // 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[Inc.Written].push_back(79 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 120private: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 134bool isLiteralInclude(llvm::StringRef Include) {135 return Include.starts_with("<") || Include.starts_with("\"");136}137 138bool HeaderFile::valid() const {139 return (Verbatim && isLiteralInclude(File)) ||140 (!Verbatim && llvm::sys::path::is_absolute(File));141}142 143llvm::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 163llvm::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 178void 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 196std::optional<IncludeStructure::HeaderID>197IncludeStructure::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 208IncludeStructure::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 227llvm::DenseMap<IncludeStructure::HeaderID, unsigned>228IncludeStructure::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 255llvm::SmallVector<const Inclusion *>256IncludeStructure::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 263void 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 the270/// path is not shortened.271bool 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 284std::optional<std::string>285IncludeInserter::calculateIncludePath(const HeaderFile &InsertedHeader,286 llvm::StringRef IncludingFile) const {287 assert(InsertedHeader.valid());288 if (InsertedHeader.Verbatim)289 return InsertedHeader.File;290 bool IsAngledByDefault = false;291 std::string Suggested;292 if (HeaderSearchInfo) {293 Suggested = HeaderSearchInfo->suggestPathToFileForDiagnostics(294 InsertedHeader.File, BuildDir, IncludingFile, &IsAngledByDefault);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 auto HeaderPath = llvm::sys::path::convert_to_slash(InsertedHeader.File);308 bool IsAngled = false;309 for (auto &Filter : AngledHeaders) {310 if (Filter(HeaderPath)) {311 IsAngled = true;312 break;313 }314 }315 bool IsQuoted = false;316 for (auto &Filter : QuotedHeaders) {317 if (Filter(HeaderPath)) {318 IsQuoted = true;319 break;320 }321 }322 // No filters apply, or both filters apply (a bug), use system default.323 if (IsAngled == IsQuoted) {324 // Probably a bug in the config regex.325 if (IsAngled && IsQuoted) {326 elog("Header '{0}' matches both quoted and angled regexes, default will "327 "be used.",328 HeaderPath);329 }330 IsAngled = IsAngledByDefault;331 }332 if (IsAngled)333 Suggested = "<" + Suggested + ">";334 else // if (IsQuoted)335 Suggested = "\"" + Suggested + "\"";336 return Suggested;337}338 339std::optional<TextEdit>340IncludeInserter::insert(llvm::StringRef VerbatimHeader,341 tooling::IncludeDirective Directive) const {342 std::optional<TextEdit> Edit;343 if (auto Insertion =344 Inserter.insert(VerbatimHeader.trim("\"<>"),345 VerbatimHeader.starts_with("<"), Directive))346 Edit = replacementToEdit(Code, *Insertion);347 return Edit;348}349 350llvm::raw_ostream &operator<<(llvm::raw_ostream &OS, const Inclusion &Inc) {351 return OS << Inc.Written << " = "352 << (!Inc.Resolved.empty() ? Inc.Resolved : "[unresolved]")353 << " at line" << Inc.HashLine;354}355 356bool operator==(const Inclusion &LHS, const Inclusion &RHS) {357 return std::tie(LHS.Directive, LHS.FileKind, LHS.HashOffset, LHS.HashLine,358 LHS.Resolved, LHS.Written) ==359 std::tie(RHS.Directive, RHS.FileKind, RHS.HashOffset, RHS.HashLine,360 RHS.Resolved, RHS.Written);361}362 363} // namespace clangd364} // namespace clang365