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