clang-tools-extra/clangd/Headers.h

   1 //===--- Headers.h - 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 #ifndef LLVM_CLANG_TOOLS_EXTRA_CLANGD_HEADERS_H
  10 #define LLVM_CLANG_TOOLS_EXTRA_CLANGD_HEADERS_H
  11
  12 #include "Protocol.h"
  13 #include "SourceCode.h"
  14 #include "index/Symbol.h"
  15 #include "support/Path.h"
  16 #include "clang/Basic/FileEntry.h"
  17 #include "clang/Basic/TokenKinds.h"
  18 #include "clang/Format/Format.h"
  19 #include "clang/Frontend/CompilerInstance.h"
  20 #include "clang/Lex/HeaderSearch.h"
  21 #include "clang/Lex/Preprocessor.h"
  22 #include "clang/Tooling/Inclusions/HeaderIncludes.h"
  23 #include "clang/Tooling/Inclusions/StandardLibrary.h"
  24 #include "llvm/ADT/ArrayRef.h"
  25 #include "llvm/ADT/DenseSet.h"
  26 #include "llvm/ADT/StringRef.h"
  27 #include "llvm/ADT/StringSet.h"
  28 #include "llvm/Support/Error.h"
  29 #include "llvm/Support/FileSystem/UniqueID.h"
  30 #include <optional>
  31 #include <string>
  32
  33 namespace clang {
  34 namespace clangd {
  35
  36 /// Returns true if \p Include is literal include like "path" or <path>.
  37 bool isLiteralInclude(llvm::StringRef Include);
  38
  39 /// Represents a header file to be #include'd.
  40 struct HeaderFile {
  41   std::string File;
  42   /// If this is true, `File` is a literal string quoted with <> or "" that
  43   /// can be #included directly; otherwise, `File` is an absolute file path.
  44   bool Verbatim;
  45
  46   bool valid() const;
  47 };
  48
  49 /// A header and directives as stored in a Symbol.
  50 struct SymbolInclude {
  51   /// The header to include. This is either a URI or a verbatim include which is
  52   /// quoted with <> or "".
  53   llvm::StringRef Header;
  54   /// The include directive(s) that can be used, e.g. #import and/or #include.
  55   Symbol::IncludeDirective Directive;
  56 };
  57
  58 /// Creates a `HeaderFile` from \p Header which can be either a URI or a literal
  59 /// include.
  60 llvm::Expected<HeaderFile> toHeaderFile(llvm::StringRef Header,
  61                                         llvm::StringRef HintPath);
  62
  63 // Returns include headers for \p Sym sorted by popularity. If two headers are
  64 // equally popular, prefer the shorter one.
  65 llvm::SmallVector<SymbolInclude, 1> getRankedIncludes(const Symbol &Sym);
  66
  67 // An #include directive that we found in the main file.
  68 struct Inclusion {
  69   tok::PPKeywordKind Directive; // Directive used for inclusion, e.g. import
  70   std::string Written;          // Inclusion name as written e.g. <vector>.
  71   Path Resolved; // Resolved path of included file. Empty if not resolved.
  72   unsigned HashOffset = 0; // Byte offset from start of file to #.
  73   int HashLine = 0;        // Line number containing the directive, 0-indexed.
  74   SrcMgr::CharacteristicKind FileKind = SrcMgr::C_User;
  75   std::optional<unsigned> HeaderID;
  76 };
  77 llvm::raw_ostream &operator<<(llvm::raw_ostream &, const Inclusion &);
  78 bool operator==(const Inclusion &LHS, const Inclusion &RHS);
  79
  80 // Contains information about one file in the build graph and its direct
  81 // dependencies. Doesn't own the strings it references (IncludeGraph is
  82 // self-contained).
  83 struct IncludeGraphNode {
  84   enum class SourceFlag : uint8_t {
  85     None = 0,
  86     // Whether current file is a main file rather than a header.
  87     IsTU = 1 << 0,
  88     // Whether current file had any uncompilable errors during indexing.
  89     HadErrors = 1 << 1,
  90   };
  91
  92   SourceFlag Flags = SourceFlag::None;
  93   llvm::StringRef URI;
  94   FileDigest Digest{{0}};
  95   std::vector<llvm::StringRef> DirectIncludes;
  96 };
  97 // FileURI and FileInclusions are references to keys of the map containing
  98 // them.
  99 // Important: The graph generated by those callbacks might contain cycles, self
 100 // edges and multi edges.
 101 using IncludeGraph = llvm::StringMap<IncludeGraphNode>;
 102
 103 inline IncludeGraphNode::SourceFlag operator|(IncludeGraphNode::SourceFlag A,
 104                                               IncludeGraphNode::SourceFlag B) {
 105   return static_cast<IncludeGraphNode::SourceFlag>(static_cast<uint8_t>(A) |
 106                                                    static_cast<uint8_t>(B));
 107 }
 108
 109 inline bool operator&(IncludeGraphNode::SourceFlag A,
 110                       IncludeGraphNode::SourceFlag B) {
 111   return static_cast<uint8_t>(A) & static_cast<uint8_t>(B);
 112 }
 113
 114 inline IncludeGraphNode::SourceFlag &
 115 operator|=(IncludeGraphNode::SourceFlag &A, IncludeGraphNode::SourceFlag B) {
 116   return A = A | B;
 117 }
 118
 119 // Information captured about the inclusion graph in a translation unit.
 120 // This includes detailed information about the direct #includes, and summary
 121 // information about all transitive includes.
 122 //
 123 // It should be built incrementally with collectIncludeStructureCallback().
 124 // When we build the preamble, we capture and store its include structure along
 125 // with the preamble data. When we use the preamble, we can copy its
 126 // IncludeStructure and use another collectIncludeStructureCallback() to fill
 127 // in any non-preamble inclusions.
 128 class IncludeStructure {
 129 public:
 130   IncludeStructure() {
 131     // Reserve HeaderID = 0 for the main file.
 132     RealPathNames.emplace_back();
 133   }
 134
 135   // Inserts a PPCallback and CommentHandler that visits all includes in the
 136   // main file and populates the structure. It will also scan for IWYU pragmas
 137   // in comments.
 138   void collect(const CompilerInstance &CI);
 139
 140   // HeaderID identifies file in the include graph. It corresponds to a
 141   // FileEntry rather than a FileID, but stays stable across preamble & main
 142   // file builds.
 143   enum class HeaderID : unsigned {};
 144
 145   std::optional<HeaderID> getID(const FileEntry *Entry) const;
 146   HeaderID getOrCreateID(FileEntryRef Entry);
 147
 148   StringRef getRealPath(HeaderID ID) const {
 149     assert(static_cast<unsigned>(ID) <= RealPathNames.size());
 150     return RealPathNames[static_cast<unsigned>(ID)];
 151   }
 152
 153   // Return all transitively reachable files.
 154   llvm::ArrayRef<std::string> allHeaders() const { return RealPathNames; }
 155
 156   // Returns includes inside the main file with the given spelling.
 157   // Spelling should include brackets or quotes, e.g. <foo>.
 158   llvm::SmallVector<const Inclusion *>
 159   mainFileIncludesWithSpelling(llvm::StringRef Spelling) const;
 160
 161   // Return all transitively reachable files, and their minimum include depth.
 162   // All transitive includes (absolute paths), with their minimum include depth.
 163   // Root --> 0, #included file --> 1, etc.
 164   // Root is the ID of the header being visited first.
 165   llvm::DenseMap<HeaderID, unsigned>
 166   includeDepth(HeaderID Root = MainFileID) const;
 167
 168   // Maps HeaderID to the ids of the files included from it.
 169   llvm::DenseMap<HeaderID, SmallVector<HeaderID>> IncludeChildren;
 170
 171   llvm::DenseMap<tooling::stdlib::Header, llvm::SmallVector<HeaderID>>
 172       StdlibHeaders;
 173
 174   std::vector<Inclusion> MainFileIncludes;
 175
 176   // We reserve HeaderID(0) for the main file and will manually check for that
 177   // in getID and getOrCreateID because the UniqueID is not stable when the
 178   // content of the main file changes.
 179   static const HeaderID MainFileID = HeaderID(0u);
 180
 181   class RecordHeaders;
 182
 183 private:
 184   // MainFileEntry will be used to check if the queried file is the main file
 185   // or not.
 186   const FileEntry *MainFileEntry = nullptr;
 187
 188   std::vector<std::string> RealPathNames; // In HeaderID order.
 189   // FileEntry::UniqueID is mapped to the internal representation (HeaderID).
 190   // Identifying files in a way that persists from preamble build to subsequent
 191   // builds is surprisingly hard. FileID is unavailable in InclusionDirective(),
 192   // and RealPathName and UniqueID are not preserved in
 193   // the preamble.
 194   llvm::DenseMap<llvm::sys::fs::UniqueID, HeaderID> UIDToIndex;
 195
 196   // Maps written includes to indices in MainFileInclude for easier lookup by
 197   // spelling.
 198   llvm::StringMap<llvm::SmallVector<unsigned>> MainFileIncludesBySpelling;
 199 };
 200
 201 // Calculates insertion edit for including a new header in a file.
 202 class IncludeInserter {
 203 public:
 204   // If \p HeaderSearchInfo is nullptr (e.g. when compile command is
 205   // infeasible), this will only try to insert verbatim headers, and
 206   // include path of non-verbatim header will not be shortened.
 207   IncludeInserter(StringRef FileName, StringRef Code,
 208                   const format::FormatStyle &Style, StringRef BuildDir,
 209                   HeaderSearch *HeaderSearchInfo)
 210       : FileName(FileName), Code(Code), BuildDir(BuildDir),
 211         HeaderSearchInfo(HeaderSearchInfo),
 212         Inserter(FileName, Code, Style.IncludeStyle) {}
 213
 214   void addExisting(const Inclusion &Inc);
 215
 216   /// Checks whether to add an #include of the header into \p File.
 217   /// An #include will not be added if:
 218   ///   - Either \p DeclaringHeader or \p InsertedHeader is already (directly)
 219   ///   in \p Inclusions (including those included via different paths).
 220   ///   - \p DeclaringHeader or \p InsertedHeader is the same as \p File.
 221   ///
 222   /// \param DeclaringHeader is path of the original header corresponding to \p
 223   /// InsertedHeader e.g. the header that declares a symbol.
 224   /// \param InsertedHeader The preferred header to be inserted. This could be
 225   /// the same as DeclaringHeader but must be provided.
 226   bool shouldInsertInclude(PathRef DeclaringHeader,
 227                            const HeaderFile &InsertedHeader) const;
 228
 229   /// Determines the preferred way to #include a file, taking into account the
 230   /// search path. Usually this will prefer a shorter representation like
 231   /// 'Foo/Bar.h' over a longer one like 'Baz/include/Foo/Bar.h'.
 232   ///
 233   /// \param InsertedHeader The preferred header to be inserted.
 234   ///
 235   /// \param IncludingFile is the absolute path of the file that InsertedHeader
 236   /// will be inserted.
 237   ///
 238   /// \return A quoted "path" or <path> to be included, or std::nullopt if it
 239   /// couldn't be shortened.
 240   std::optional<std::string>
 241   calculateIncludePath(const HeaderFile &InsertedHeader,
 242                        llvm::StringRef IncludingFile) const;
 243
 244   /// Calculates an edit that inserts \p VerbatimHeader into code. If the header
 245   /// is already included, this returns std::nullopt.
 246   std::optional<TextEdit> insert(llvm::StringRef VerbatimHeader,
 247                                  tooling::IncludeDirective Directive) const;
 248
 249 private:
 250   StringRef FileName;
 251   StringRef Code;
 252   StringRef BuildDir;
 253   HeaderSearch *HeaderSearchInfo = nullptr;
 254   llvm::StringSet<> IncludedHeaders; // Both written and resolved.
 255   tooling::HeaderIncludes Inserter;  // Computers insertion replacement.
 256 };
 257
 258 } // namespace clangd
 259 } // namespace clang
 260
 261 namespace llvm {
 262
 263 // Support HeaderIDs as DenseMap keys.
 264 template <> struct DenseMapInfo<clang::clangd::IncludeStructure::HeaderID> {
 265   static inline clang::clangd::IncludeStructure::HeaderID getEmptyKey() {
 266     return static_cast<clang::clangd::IncludeStructure::HeaderID>(-1);
 267   }
 268
 269   static inline clang::clangd::IncludeStructure::HeaderID getTombstoneKey() {
 270     return static_cast<clang::clangd::IncludeStructure::HeaderID>(-2);
 271   }
 272
 273   static unsigned
 274   getHashValue(const clang::clangd::IncludeStructure::HeaderID &Tag) {
 275     return hash_value(static_cast<unsigned>(Tag));
 276   }
 277
 278   static bool isEqual(const clang::clangd::IncludeStructure::HeaderID &LHS,
 279                       const clang::clangd::IncludeStructure::HeaderID &RHS) {
 280     return LHS == RHS;
 281   }
 282 };
 283
 284 } // namespace llvm
 285
 286 #endif // LLVM_CLANG_TOOLS_EXTRA_CLANGD_HEADERS_H