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 * /*Imported*/,
  45                           SrcMgr::CharacteristicKind FileKind) override {
  46     auto MainFID = SM.getMainFileID();
  47     // If an include is part of the preamble patch, translate #line directives.
  48     if (InBuiltinFile)
  49       HashLoc = translatePreamblePatchLocation(HashLoc, SM);
  50
  51     // Record main-file inclusions (including those mapped from the preamble
  52     // patch).
  53     if (isInsideMainFile(HashLoc, SM)) {
  54       Out->MainFileIncludes.emplace_back();
  55       auto &Inc = Out->MainFileIncludes.back();
  56       Inc.Written =
  57           (IsAngled ? "<" + FileName + ">" : "\"" + FileName + "\"").str();
  58       Inc.Resolved = std::string(
  59           File ? getCanonicalPath(*File, SM.getFileManager()).value_or("")
  60                : "");
  61       Inc.HashOffset = SM.getFileOffset(HashLoc);
  62       Inc.HashLine =
  63           SM.getLineNumber(SM.getFileID(HashLoc), Inc.HashOffset) - 1;
  64       Inc.FileKind = FileKind;
  65       Inc.Directive = IncludeTok.getIdentifierInfo()->getPPKeywordID();
  66       if (File) {
  67         IncludeStructure::HeaderID HID = Out->getOrCreateID(*File);
  68         Inc.HeaderID = static_cast<unsigned>(HID);
  69         if (IsAngled)
  70           if (auto StdlibHeader = tooling::stdlib::Header::named(Inc.Written)) {
  71             auto &IDs = Out->StdlibHeaders[*StdlibHeader];
  72             // Few physical files for one stdlib header name, linear scan is ok.
  73             if (!llvm::is_contained(IDs, HID))
  74               IDs.push_back(HID);
  75           }
  76       }
  77       Out->MainFileIncludesBySpelling.try_emplace(Inc.Written)
  78           .first->second.push_back(Out->MainFileIncludes.size() - 1);
  79     }
  80
  81     // Record include graph (not just for main-file includes)
  82     if (File) {
  83       auto IncludingFileEntry = SM.getFileEntryRefForID(SM.getFileID(HashLoc));
  84       if (!IncludingFileEntry) {
  85         assert(SM.getBufferName(HashLoc).startswith("<") &&
  86                "Expected #include location to be a file or <built-in>");
  87         // Treat as if included from the main file.
  88         IncludingFileEntry = SM.getFileEntryRefForID(MainFID);
  89       }
  90       auto IncludingID = Out->getOrCreateID(*IncludingFileEntry),
  91            IncludedID = Out->getOrCreateID(*File);
  92       Out->IncludeChildren[IncludingID].push_back(IncludedID);
  93     }
  94   }
  95
  96   void FileChanged(SourceLocation Loc, FileChangeReason Reason,
  97                    SrcMgr::CharacteristicKind FileType,
  98                    FileID PrevFID) override {
  99     switch (Reason) {
 100     case PPCallbacks::EnterFile:
 101       ++Level;
 102       if (BuiltinFile.isInvalid() && SM.isWrittenInBuiltinFile(Loc)) {
 103         BuiltinFile = SM.getFileID(Loc);
 104         InBuiltinFile = true;
 105       }
 106       break;
 107     case PPCallbacks::ExitFile: {
 108       --Level;
 109       if (PrevFID == BuiltinFile)
 110         InBuiltinFile = false;
 111       break;
 112     }
 113     case PPCallbacks::RenameFile:
 114     case PPCallbacks::SystemHeaderPragma:
 115       break;
 116     }
 117   }
 118
 119 private:
 120   // Keeps track of include depth for the current file. It's 1 for main file.
 121   int Level = 0;
 122   bool inMainFile() const { return Level == 1; }
 123
 124   const SourceManager &SM;
 125   // Set after entering the <built-in> file.
 126   FileID BuiltinFile;
 127   // Indicates whether <built-in> file is part of include stack.
 128   bool InBuiltinFile = false;
 129
 130   IncludeStructure *Out;
 131 };
 132
 133 bool isLiteralInclude(llvm::StringRef Include) {
 134   return Include.startswith("<") || Include.startswith("\"");
 135 }
 136
 137 bool HeaderFile::valid() const {
 138   return (Verbatim && isLiteralInclude(File)) ||
 139          (!Verbatim && llvm::sys::path::is_absolute(File));
 140 }
 141
 142 llvm::Expected<HeaderFile> toHeaderFile(llvm::StringRef Header,
 143                                         llvm::StringRef HintPath) {
 144   if (isLiteralInclude(Header))
 145     return HeaderFile{Header.str(), /*Verbatim=*/true};
 146   auto U = URI::parse(Header);
 147   if (!U)
 148     return U.takeError();
 149
 150   auto IncludePath = URI::includeSpelling(*U);
 151   if (!IncludePath)
 152     return IncludePath.takeError();
 153   if (!IncludePath->empty())
 154     return HeaderFile{std::move(*IncludePath), /*Verbatim=*/true};
 155
 156   auto Resolved = URI::resolve(*U, HintPath);
 157   if (!Resolved)
 158     return Resolved.takeError();
 159   return HeaderFile{std::move(*Resolved), /*Verbatim=*/false};
 160 }
 161
 162 llvm::SmallVector<SymbolInclude, 1> getRankedIncludes(const Symbol &Sym) {
 163   auto Includes = Sym.IncludeHeaders;
 164   // Sort in descending order by reference count and header length.
 165   llvm::sort(Includes, [](const Symbol::IncludeHeaderWithReferences &LHS,
 166                           const Symbol::IncludeHeaderWithReferences &RHS) {
 167     if (LHS.References == RHS.References)
 168       return LHS.IncludeHeader.size() < RHS.IncludeHeader.size();
 169     return LHS.References > RHS.References;
 170   });
 171   llvm::SmallVector<SymbolInclude, 1> Headers;
 172   for (const auto &Include : Includes)
 173     Headers.push_back({Include.IncludeHeader, Include.supportedDirectives()});
 174   return Headers;
 175 }
 176
 177 void IncludeStructure::collect(const CompilerInstance &CI) {
 178   auto &SM = CI.getSourceManager();
 179   MainFileEntry = SM.getFileEntryForID(SM.getMainFileID());
 180   auto Collector = std::make_unique<RecordHeaders>(CI, this);
 181   CI.getPreprocessor().addPPCallbacks(std::move(Collector));
 182
 183   // If we're reusing a preamble, don't repopulate SearchPathsCanonical.
 184   // The entries will be the same, but canonicalizing to find out is expensive!
 185   if (SearchPathsCanonical.empty()) {
 186     for (const auto &Dir :
 187          CI.getPreprocessor().getHeaderSearchInfo().search_dir_range()) {
 188       if (Dir.getLookupType() == DirectoryLookup::LT_NormalDir)
 189         SearchPathsCanonical.emplace_back(
 190             SM.getFileManager().getCanonicalName(*Dir.getDirRef()));
 191     }
 192   }
 193 }
 194
 195 std::optional<IncludeStructure::HeaderID>
 196 IncludeStructure::getID(const FileEntry *Entry) const {
 197   // HeaderID of the main file is always 0;
 198   if (Entry == MainFileEntry) {
 199     return static_cast<IncludeStructure::HeaderID>(0u);
 200   }
 201   auto It = UIDToIndex.find(Entry->getUniqueID());
 202   if (It == UIDToIndex.end())
 203     return std::nullopt;
 204   return It->second;
 205 }
 206
 207 IncludeStructure::HeaderID IncludeStructure::getOrCreateID(FileEntryRef Entry) {
 208   // Main file's FileEntry was not known at IncludeStructure creation time.
 209   if (&Entry.getFileEntry() == MainFileEntry) {
 210     if (RealPathNames.front().empty())
 211       RealPathNames.front() = MainFileEntry->tryGetRealPathName().str();
 212     return MainFileID;
 213   }
 214   auto R = UIDToIndex.try_emplace(
 215       Entry.getUniqueID(),
 216       static_cast<IncludeStructure::HeaderID>(RealPathNames.size()));
 217   if (R.second)
 218     RealPathNames.emplace_back();
 219   IncludeStructure::HeaderID Result = R.first->getSecond();
 220   std::string &RealPathName = RealPathNames[static_cast<unsigned>(Result)];
 221   if (RealPathName.empty())
 222     RealPathName = Entry.getFileEntry().tryGetRealPathName().str();
 223   return Result;
 224 }
 225
 226 llvm::DenseMap<IncludeStructure::HeaderID, unsigned>
 227 IncludeStructure::includeDepth(HeaderID Root) const {
 228   // Include depth 0 is the main file only.
 229   llvm::DenseMap<HeaderID, unsigned> Result;
 230   assert(static_cast<unsigned>(Root) < RealPathNames.size());
 231   Result[Root] = 0;
 232   std::vector<IncludeStructure::HeaderID> CurrentLevel;
 233   CurrentLevel.push_back(Root);
 234   llvm::DenseSet<IncludeStructure::HeaderID> Seen;
 235   Seen.insert(Root);
 236
 237   // Each round of BFS traversal finds the next depth level.
 238   std::vector<IncludeStructure::HeaderID> PreviousLevel;
 239   for (unsigned Level = 1; !CurrentLevel.empty(); ++Level) {
 240     PreviousLevel.clear();
 241     PreviousLevel.swap(CurrentLevel);
 242     for (const auto &Parent : PreviousLevel) {
 243       for (const auto &Child : IncludeChildren.lookup(Parent)) {
 244         if (Seen.insert(Child).second) {
 245           CurrentLevel.push_back(Child);
 246           Result[Child] = Level;
 247         }
 248       }
 249     }
 250   }
 251   return Result;
 252 }
 253
 254 llvm::SmallVector<const Inclusion *>
 255 IncludeStructure::mainFileIncludesWithSpelling(llvm::StringRef Spelling) const {
 256   llvm::SmallVector<const Inclusion *> Includes;
 257   for (auto Idx : MainFileIncludesBySpelling.lookup(Spelling))
 258     Includes.push_back(&MainFileIncludes[Idx]);
 259   return Includes;
 260 }
 261
 262 void IncludeInserter::addExisting(const Inclusion &Inc) {
 263   IncludedHeaders.insert(Inc.Written);
 264   if (!Inc.Resolved.empty())
 265     IncludedHeaders.insert(Inc.Resolved);
 266 }
 267
 268 /// FIXME(ioeric): we might not want to insert an absolute include path if the
 269 /// path is not shortened.
 270 bool IncludeInserter::shouldInsertInclude(
 271     PathRef DeclaringHeader, const HeaderFile &InsertedHeader) const {
 272   assert(InsertedHeader.valid());
 273   if (!HeaderSearchInfo && !InsertedHeader.Verbatim)
 274     return false;
 275   if (FileName == DeclaringHeader || FileName == InsertedHeader.File)
 276     return false;
 277   auto Included = [&](llvm::StringRef Header) {
 278     return IncludedHeaders.contains(Header);
 279   };
 280   return !Included(DeclaringHeader) && !Included(InsertedHeader.File);
 281 }
 282
 283 std::optional<std::string>
 284 IncludeInserter::calculateIncludePath(const HeaderFile &InsertedHeader,
 285                                       llvm::StringRef IncludingFile) const {
 286   assert(InsertedHeader.valid());
 287   if (InsertedHeader.Verbatim)
 288     return InsertedHeader.File;
 289   bool IsAngled = false;
 290   std::string Suggested;
 291   if (HeaderSearchInfo) {
 292     Suggested = HeaderSearchInfo->suggestPathToFileForDiagnostics(
 293         InsertedHeader.File, BuildDir, IncludingFile, &IsAngled);
 294   } else {
 295     // Calculate include relative to including file only.
 296     StringRef IncludingDir = llvm::sys::path::parent_path(IncludingFile);
 297     SmallString<256> RelFile(InsertedHeader.File);
 298     // Replacing with "" leaves "/RelFile" if IncludingDir doesn't end in "/".
 299     llvm::sys::path::replace_path_prefix(RelFile, IncludingDir, "./");
 300     Suggested = llvm::sys::path::convert_to_slash(
 301         llvm::sys::path::remove_leading_dotslash(RelFile));
 302   }
 303   // FIXME: should we allow (some limited number of) "../header.h"?
 304   if (llvm::sys::path::is_absolute(Suggested))
 305     return std::nullopt;
 306   if (IsAngled)
 307     Suggested = "<" + Suggested + ">";
 308   else
 309     Suggested = "\"" + Suggested + "\"";
 310   return Suggested;
 311 }
 312
 313 std::optional<TextEdit>
 314 IncludeInserter::insert(llvm::StringRef VerbatimHeader,
 315                         tooling::IncludeDirective Directive) const {
 316   std::optional<TextEdit> Edit;
 317   if (auto Insertion =
 318           Inserter.insert(VerbatimHeader.trim("\"<>"),
 319                           VerbatimHeader.startswith("<"), Directive))
 320     Edit = replacementToEdit(Code, *Insertion);
 321   return Edit;
 322 }
 323
 324 llvm::raw_ostream &operator<<(llvm::raw_ostream &OS, const Inclusion &Inc) {
 325   return OS << Inc.Written << " = "
 326             << (!Inc.Resolved.empty() ? Inc.Resolved : "[unresolved]")
 327             << " at line" << Inc.HashLine;
 328 }
 329
 330 bool operator==(const Inclusion &LHS, const Inclusion &RHS) {
 331   return std::tie(LHS.Directive, LHS.FileKind, LHS.HashOffset, LHS.HashLine,
 332                   LHS.Resolved, LHS.Written) ==
 333          std::tie(RHS.Directive, RHS.FileKind, RHS.HashOffset, RHS.HashLine,
 334                   RHS.Resolved, RHS.Written);
 335 }
 336
 337 } // namespace clangd
 338 } // namespace clang