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/TokenKinds.h" 17 #include "clang/Format/Format.h" 18 #include "clang/Lex/HeaderSearch.h" 19 #include "clang/Lex/PPCallbacks.h" 20 #include "clang/Tooling/Inclusions/HeaderIncludes.h" 21 #include "llvm/ADT/ArrayRef.h" 22 #include "llvm/ADT/StringRef.h" 23 #include "llvm/ADT/StringSet.h" 24 #include "llvm/Support/Error.h" 25 #include "llvm/Support/VirtualFileSystem.h" 26 #include <string> 27 28 namespace clang { 29 namespace clangd { 30 31 /// Returns true if \p Include is literal include like "path" or <path>. 32 bool isLiteralInclude(llvm::StringRef Include); 33 34 /// Represents a header file to be #include'd. 35 struct HeaderFile { 36 std::string File; 37 /// If this is true, `File` is a literal string quoted with <> or "" that 38 /// can be #included directly; otherwise, `File` is an absolute file path. 39 bool Verbatim; 40 41 bool valid() const; 42 }; 43 44 /// Creates a `HeaderFile` from \p Header which can be either a URI or a literal 45 /// include. 46 llvm::Expected<HeaderFile> toHeaderFile(llvm::StringRef Header, 47 llvm::StringRef HintPath); 48 49 // Returns include headers for \p Sym sorted by popularity. If two headers are 50 // equally popular, prefer the shorter one. 51 llvm::SmallVector<llvm::StringRef, 1> getRankedIncludes(const Symbol &Sym); 52 53 // An #include directive that we found in the main file. 54 struct Inclusion { 55 tok::PPKeywordKind Directive; // Directive used for inclusion, e.g. import 56 std::string Written; // Inclusion name as written e.g. <vector>. 57 Path Resolved; // Resolved path of included file. Empty if not resolved. 58 unsigned HashOffset = 0; // Byte offset from start of file to #. 59 int HashLine = 0; // Line number containing the directive, 0-indexed. 60 SrcMgr::CharacteristicKind FileKind = SrcMgr::C_User; 61 }; 62 llvm::raw_ostream &operator<<(llvm::raw_ostream &, const Inclusion &); 63 bool operator==(const Inclusion &LHS, const Inclusion &RHS); 64 65 // Contains information about one file in the build grpah and its direct 66 // dependencies. Doesn't own the strings it references (IncludeGraph is 67 // self-contained). 68 struct IncludeGraphNode { 69 enum class SourceFlag : uint8_t { 70 None = 0, 71 // Whether current file is a main file rather than a header. 72 IsTU = 1 << 0, 73 // Whether current file had any uncompilable errors during indexing. 74 HadErrors = 1 << 1, 75 }; 76 77 SourceFlag Flags = SourceFlag::None; 78 llvm::StringRef URI; 79 FileDigest Digest{{0}}; 80 std::vector<llvm::StringRef> DirectIncludes; 81 }; 82 // FileURI and FileInclusions are references to keys of the map containing 83 // them. 84 // Important: The graph generated by those callbacks might contain cycles, self 85 // edges and multi edges. 86 using IncludeGraph = llvm::StringMap<IncludeGraphNode>; 87 88 inline IncludeGraphNode::SourceFlag operator|(IncludeGraphNode::SourceFlag A, 89 IncludeGraphNode::SourceFlag B) { 90 return static_cast<IncludeGraphNode::SourceFlag>(static_cast<uint8_t>(A) | 91 static_cast<uint8_t>(B)); 92 } 93 94 inline bool operator&(IncludeGraphNode::SourceFlag A, 95 IncludeGraphNode::SourceFlag B) { 96 return static_cast<uint8_t>(A) & static_cast<uint8_t>(B); 97 } 98 99 inline IncludeGraphNode::SourceFlag & 100 operator|=(IncludeGraphNode::SourceFlag &A, IncludeGraphNode::SourceFlag B) { 101 return A = A | B; 102 } 103 104 // Information captured about the inclusion graph in a translation unit. 105 // This includes detailed information about the direct #includes, and summary 106 // information about all transitive includes. 107 // 108 // It should be built incrementally with collectIncludeStructureCallback(). 109 // When we build the preamble, we capture and store its include structure along 110 // with the preamble data. When we use the preamble, we can copy its 111 // IncludeStructure and use another collectIncludeStructureCallback() to fill 112 // in any non-preamble inclusions. 113 class IncludeStructure { 114 public: 115 std::vector<Inclusion> MainFileIncludes; 116 117 // Return all transitively reachable files, and their minimum include depth. 118 // All transitive includes (absolute paths), with their minimum include depth. 119 // Root --> 0, #included file --> 1, etc. 120 // Root is clang's name for a file, which may not be absolute. 121 // Usually it should be SM.getFileEntryForID(SM.getMainFileID())->getName(). 122 llvm::StringMap<unsigned> includeDepth(llvm::StringRef Root) const; 123 124 // This updates IncludeDepth(), but not MainFileIncludes. 125 void recordInclude(llvm::StringRef IncludingName, 126 llvm::StringRef IncludedName, 127 llvm::StringRef IncludedRealName); 128 129 private: 130 // Identifying files in a way that persists from preamble build to subsequent 131 // builds is surprisingly hard. FileID is unavailable in InclusionDirective(), 132 // and RealPathName and UniqueID are not preserved in the preamble. 133 // We use the FileEntry::Name, which is stable, interned into a "file index". 134 // The paths we want to expose are the RealPathName, so store those too. 135 std::vector<std::string> RealPathNames; // In file index order. 136 unsigned fileIndex(llvm::StringRef Name); 137 llvm::StringMap<unsigned> NameToIndex; // Values are file indexes. 138 // Maps a file's index to that of the files it includes. 139 llvm::DenseMap<unsigned, SmallVector<unsigned, 8>> IncludeChildren; 140 }; 141 142 /// Returns a PPCallback that visits all inclusions in the main file. 143 std::unique_ptr<PPCallbacks> 144 collectIncludeStructureCallback(const SourceManager &SM, IncludeStructure *Out); 145 146 // Calculates insertion edit for including a new header in a file. 147 class IncludeInserter { 148 public: 149 // If \p HeaderSearchInfo is nullptr (e.g. when compile command is 150 // infeasible), this will only try to insert verbatim headers, and 151 // include path of non-verbatim header will not be shortened. IncludeInserter(StringRef FileName,StringRef Code,const format::FormatStyle & Style,StringRef BuildDir,HeaderSearch * HeaderSearchInfo)152 IncludeInserter(StringRef FileName, StringRef Code, 153 const format::FormatStyle &Style, StringRef BuildDir, 154 HeaderSearch *HeaderSearchInfo) 155 : FileName(FileName), Code(Code), BuildDir(BuildDir), 156 HeaderSearchInfo(HeaderSearchInfo), 157 Inserter(FileName, Code, Style.IncludeStyle) {} 158 159 void addExisting(const Inclusion &Inc); 160 161 /// Checks whether to add an #include of the header into \p File. 162 /// An #include will not be added if: 163 /// - Either \p DeclaringHeader or \p InsertedHeader is already (directly) 164 /// in \p Inclusions (including those included via different paths). 165 /// - \p DeclaringHeader or \p InsertedHeader is the same as \p File. 166 /// 167 /// \param DeclaringHeader is path of the original header corresponding to \p 168 /// InsertedHeader e.g. the header that declares a symbol. 169 /// \param InsertedHeader The preferred header to be inserted. This could be 170 /// the same as DeclaringHeader but must be provided. 171 bool shouldInsertInclude(PathRef DeclaringHeader, 172 const HeaderFile &InsertedHeader) const; 173 174 /// Determines the preferred way to #include a file, taking into account the 175 /// search path. Usually this will prefer a shorter representation like 176 /// 'Foo/Bar.h' over a longer one like 'Baz/include/Foo/Bar.h'. 177 /// 178 /// \param InsertedHeader The preferred header to be inserted. 179 /// 180 /// \param IncludingFile is the absolute path of the file that InsertedHeader 181 /// will be inserted. 182 /// 183 /// \return A quoted "path" or <path> to be included, or None if it couldn't 184 /// be shortened. 185 llvm::Optional<std::string> 186 calculateIncludePath(const HeaderFile &InsertedHeader, 187 llvm::StringRef IncludingFile) const; 188 189 /// Calculates an edit that inserts \p VerbatimHeader into code. If the header 190 /// is already included, this returns None. 191 llvm::Optional<TextEdit> insert(llvm::StringRef VerbatimHeader) const; 192 193 private: 194 StringRef FileName; 195 StringRef Code; 196 StringRef BuildDir; 197 HeaderSearch *HeaderSearchInfo = nullptr; 198 llvm::StringSet<> IncludedHeaders; // Both written and resolved. 199 tooling::HeaderIncludes Inserter; // Computers insertion replacement. 200 }; 201 202 } // namespace clangd 203 } // namespace clang 204 205 #endif // LLVM_CLANG_TOOLS_EXTRA_CLANGD_HEADERS_H 206