clang-tools-extra/clangd/Headers.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-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