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