clang-tools  14.0.0git
Headers.cpp
Go to the documentation of this file.
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 "Compiler.h"
11 #include "Preamble.h"
12 #include "SourceCode.h"
13 #include "support/Logger.h"
14 #include "clang/Basic/SourceLocation.h"
15 #include "clang/Basic/SourceManager.h"
16 #include "clang/Frontend/CompilerInstance.h"
17 #include "clang/Frontend/CompilerInvocation.h"
18 #include "clang/Frontend/FrontendActions.h"
19 #include "clang/Lex/HeaderSearch.h"
20 #include "llvm/ADT/StringRef.h"
21 #include "llvm/Support/Path.h"
22 
23 namespace clang {
24 namespace clangd {
25 
27 public:
28  RecordHeaders(const SourceManager &SM, HeaderSearch &HeaderInfo,
29  IncludeStructure *Out)
30  : SM(SM), HeaderInfo(HeaderInfo), Out(Out) {}
31 
32  // Record existing #includes - both written and resolved paths. Only #includes
33  // in the main file are collected.
34  void InclusionDirective(SourceLocation HashLoc, const Token &IncludeTok,
35  llvm::StringRef FileName, bool IsAngled,
36  CharSourceRange /*FilenameRange*/,
37  const FileEntry *File, llvm::StringRef /*SearchPath*/,
38  llvm::StringRef /*RelativePath*/,
39  const clang::Module * /*Imported*/,
40  SrcMgr::CharacteristicKind FileKind) override {
41  auto MainFID = SM.getMainFileID();
42  // If an include is part of the preamble patch, translate #line directives.
43  if (InBuiltinFile)
44  HashLoc = translatePreamblePatchLocation(HashLoc, SM);
45 
46  // Record main-file inclusions (including those mapped from the preamble
47  // patch).
48  if (isInsideMainFile(HashLoc, SM)) {
49  Out->MainFileIncludes.emplace_back();
50  auto &Inc = Out->MainFileIncludes.back();
51  Inc.Written =
52  (IsAngled ? "<" + FileName + ">" : "\"" + FileName + "\"").str();
53  Inc.Resolved = std::string(File ? File->tryGetRealPathName() : "");
54  Inc.HashOffset = SM.getFileOffset(HashLoc);
55  Inc.HashLine =
56  SM.getLineNumber(SM.getFileID(HashLoc), Inc.HashOffset) - 1;
57  Inc.FileKind = FileKind;
58  Inc.Directive = IncludeTok.getIdentifierInfo()->getPPKeywordID();
59  if (File)
60  Inc.HeaderID = static_cast<unsigned>(Out->getOrCreateID(File));
61  }
62 
63  // Record include graph (not just for main-file includes)
64  if (File) {
65  auto *IncludingFileEntry = SM.getFileEntryForID(SM.getFileID(HashLoc));
66  if (!IncludingFileEntry) {
67  assert(SM.getBufferName(HashLoc).startswith("<") &&
68  "Expected #include location to be a file or <built-in>");
69  // Treat as if included from the main file.
70  IncludingFileEntry = SM.getFileEntryForID(MainFID);
71  }
72  auto IncludingID = Out->getOrCreateID(IncludingFileEntry),
73  IncludedID = Out->getOrCreateID(File);
74  Out->IncludeChildren[IncludingID].push_back(IncludedID);
75  }
76  }
77 
78  void FileChanged(SourceLocation Loc, FileChangeReason Reason,
79  SrcMgr::CharacteristicKind FileType,
80  FileID PrevFID) override {
81  switch (Reason) {
82  case PPCallbacks::EnterFile:
83  if (BuiltinFile.isInvalid() && SM.isWrittenInBuiltinFile(Loc)) {
84  BuiltinFile = SM.getFileID(Loc);
85  InBuiltinFile = true;
86  }
87  break;
88  case PPCallbacks::ExitFile: {
89  if (PrevFID == BuiltinFile)
90  InBuiltinFile = false;
91  // At file exit time HeaderSearchInfo is valid and can be used to
92  // determine whether the file was a self-contained header or not.
93  if (const FileEntry *FE = SM.getFileEntryForID(PrevFID))
94  if (!isSelfContainedHeader(FE, PrevFID, SM, HeaderInfo))
95  Out->NonSelfContained.insert(
96  *Out->getID(SM.getFileEntryForID(PrevFID)));
97  break;
98  }
99  case PPCallbacks::RenameFile:
100  case PPCallbacks::SystemHeaderPragma:
101  break;
102  }
103  }
104 
105 private:
106  const SourceManager &SM;
107  HeaderSearch &HeaderInfo;
108  // Set after entering the <built-in> file.
109  FileID BuiltinFile;
110  // Indicates whether <built-in> file is part of include stack.
111  bool InBuiltinFile = false;
112 
113  IncludeStructure *Out;
114 };
115 
116 bool isLiteralInclude(llvm::StringRef Include) {
117  return Include.startswith("<") || Include.startswith("\"");
118 }
119 
120 bool HeaderFile::valid() const {
121  return (Verbatim && isLiteralInclude(File)) ||
122  (!Verbatim && llvm::sys::path::is_absolute(File));
123 }
124 
125 llvm::Expected<HeaderFile> toHeaderFile(llvm::StringRef Header,
126  llvm::StringRef HintPath) {
127  if (isLiteralInclude(Header))
128  return HeaderFile{Header.str(), /*Verbatim=*/true};
129  auto U = URI::parse(Header);
130  if (!U)
131  return U.takeError();
132 
133  auto IncludePath = URI::includeSpelling(*U);
134  if (!IncludePath)
135  return IncludePath.takeError();
136  if (!IncludePath->empty())
137  return HeaderFile{std::move(*IncludePath), /*Verbatim=*/true};
138 
139  auto Resolved = URI::resolve(*U, HintPath);
140  if (!Resolved)
141  return Resolved.takeError();
142  return HeaderFile{std::move(*Resolved), /*Verbatim=*/false};
143 }
144 
145 llvm::SmallVector<llvm::StringRef, 1> getRankedIncludes(const Symbol &Sym) {
146  auto Includes = Sym.IncludeHeaders;
147  // Sort in descending order by reference count and header length.
148  llvm::sort(Includes, [](const Symbol::IncludeHeaderWithReferences &LHS,
150  if (LHS.References == RHS.References)
151  return LHS.IncludeHeader.size() < RHS.IncludeHeader.size();
152  return LHS.References > RHS.References;
153  });
154  llvm::SmallVector<llvm::StringRef, 1> Headers;
155  for (const auto &Include : Includes)
156  Headers.push_back(Include.IncludeHeader);
157  return Headers;
158 }
159 
160 std::unique_ptr<PPCallbacks>
161 IncludeStructure::collect(const CompilerInstance &CI) {
162  auto &SM = CI.getSourceManager();
163  MainFileEntry = SM.getFileEntryForID(SM.getMainFileID());
164  return std::make_unique<RecordHeaders>(
165  SM, CI.getPreprocessor().getHeaderSearchInfo(), this);
166 }
167 
168 llvm::Optional<IncludeStructure::HeaderID>
169 IncludeStructure::getID(const FileEntry *Entry) const {
170  // HeaderID of the main file is always 0;
171  if (Entry == MainFileEntry) {
172  return static_cast<IncludeStructure::HeaderID>(0u);
173  }
174  auto It = UIDToIndex.find(Entry->getUniqueID());
175  if (It == UIDToIndex.end())
176  return llvm::None;
177  return It->second;
178 }
179 
182  // Main file's FileEntry was not known at IncludeStructure creation time.
183  if (Entry == MainFileEntry) {
184  if (RealPathNames.front().empty())
185  RealPathNames.front() = MainFileEntry->tryGetRealPathName().str();
186  return MainFileID;
187  }
188  auto R = UIDToIndex.try_emplace(
189  Entry->getUniqueID(),
190  static_cast<IncludeStructure::HeaderID>(RealPathNames.size()));
191  if (R.second)
192  RealPathNames.emplace_back();
193  IncludeStructure::HeaderID Result = R.first->getSecond();
194  std::string &RealPathName = RealPathNames[static_cast<unsigned>(Result)];
195  if (RealPathName.empty())
196  RealPathName = Entry->tryGetRealPathName().str();
197  return Result;
198 }
199 
200 llvm::DenseMap<IncludeStructure::HeaderID, unsigned>
202  // Include depth 0 is the main file only.
203  llvm::DenseMap<HeaderID, unsigned> Result;
204  assert(static_cast<unsigned>(Root) < RealPathNames.size());
205  Result[Root] = 0;
206  std::vector<IncludeStructure::HeaderID> CurrentLevel;
207  CurrentLevel.push_back(Root);
208  llvm::DenseSet<IncludeStructure::HeaderID> Seen;
209  Seen.insert(Root);
210 
211  // Each round of BFS traversal finds the next depth level.
212  std::vector<IncludeStructure::HeaderID> PreviousLevel;
213  for (unsigned Level = 1; !CurrentLevel.empty(); ++Level) {
214  PreviousLevel.clear();
215  PreviousLevel.swap(CurrentLevel);
216  for (const auto &Parent : PreviousLevel) {
217  for (const auto &Child : IncludeChildren.lookup(Parent)) {
218  if (Seen.insert(Child).second) {
219  CurrentLevel.push_back(Child);
220  Result[Child] = Level;
221  }
222  }
223  }
224  }
225  return Result;
226 }
227 
229  IncludedHeaders.insert(Inc.Written);
230  if (!Inc.Resolved.empty())
231  IncludedHeaders.insert(Inc.Resolved);
232 }
233 
234 /// FIXME(ioeric): we might not want to insert an absolute include path if the
235 /// path is not shortened.
237  PathRef DeclaringHeader, const HeaderFile &InsertedHeader) const {
238  assert(InsertedHeader.valid());
239  if (!HeaderSearchInfo && !InsertedHeader.Verbatim)
240  return false;
241  if (FileName == DeclaringHeader || FileName == InsertedHeader.File)
242  return false;
243  auto Included = [&](llvm::StringRef Header) {
244  return IncludedHeaders.find(Header) != IncludedHeaders.end();
245  };
246  return !Included(DeclaringHeader) && !Included(InsertedHeader.File);
247 }
248 
249 llvm::Optional<std::string>
251  llvm::StringRef IncludingFile) const {
252  assert(InsertedHeader.valid());
253  if (InsertedHeader.Verbatim)
254  return InsertedHeader.File;
255  bool IsSystem = false;
256  std::string Suggested;
257  if (HeaderSearchInfo) {
258  Suggested = HeaderSearchInfo->suggestPathToFileForDiagnostics(
259  InsertedHeader.File, BuildDir, IncludingFile, &IsSystem);
260  } else {
261  // Calculate include relative to including file only.
262  StringRef IncludingDir = llvm::sys::path::parent_path(IncludingFile);
263  SmallString<256> RelFile(InsertedHeader.File);
264  // Replacing with "" leaves "/RelFile" if IncludingDir doesn't end in "/".
265  llvm::sys::path::replace_path_prefix(RelFile, IncludingDir, "./");
266  Suggested = llvm::sys::path::convert_to_slash(
267  llvm::sys::path::remove_leading_dotslash(RelFile));
268  }
269  // FIXME: should we allow (some limited number of) "../header.h"?
270  if (llvm::sys::path::is_absolute(Suggested))
271  return None;
272  if (IsSystem)
273  Suggested = "<" + Suggested + ">";
274  else
275  Suggested = "\"" + Suggested + "\"";
276  return Suggested;
277 }
278 
279 llvm::Optional<TextEdit>
280 IncludeInserter::insert(llvm::StringRef VerbatimHeader) const {
281  llvm::Optional<TextEdit> Edit = None;
282  if (auto Insertion = Inserter.insert(VerbatimHeader.trim("\"<>"),
283  VerbatimHeader.startswith("<")))
284  Edit = replacementToEdit(Code, *Insertion);
285  return Edit;
286 }
287 
288 llvm::raw_ostream &operator<<(llvm::raw_ostream &OS, const Inclusion &Inc) {
289  return OS << Inc.Written << " = "
290  << (!Inc.Resolved.empty() ? Inc.Resolved : "[unresolved]")
291  << " at line" << Inc.HashLine;
292 }
293 
294 bool operator==(const Inclusion &LHS, const Inclusion &RHS) {
295  return std::tie(LHS.Directive, LHS.FileKind, LHS.HashOffset, LHS.HashLine,
296  LHS.Resolved, LHS.Written) ==
297  std::tie(RHS.Directive, RHS.FileKind, RHS.HashOffset, RHS.HashLine,
298  RHS.Resolved, RHS.Written);
299 }
300 } // namespace clangd
301 } // namespace clang
Loc
SourceLocation Loc
Definition: KernelNameRestrictionCheck.cpp:45
clang::clangd::HeaderFile
Represents a header file to be #include'd.
Definition: Headers.h:40
Headers.h
clang::clangd::Edit
A set of edits generated for a single file.
Definition: SourceCode.h:184
clang::clangd::IncludeStructure::getID
llvm::Optional< HeaderID > getID(const FileEntry *Entry) const
Definition: Headers.cpp:169
clang::clangd::IncludeStructure::RecordHeaders::RecordHeaders
RecordHeaders(const SourceManager &SM, HeaderSearch &HeaderInfo, IncludeStructure *Out)
Definition: Headers.cpp:28
CI
std::unique_ptr< CompilerInvocation > CI
Definition: TUScheduler.cpp:456
Root
ASTNode Root
Definition: DumpAST.cpp:332
Preamble.h
clang::clangd::HeaderFile::valid
bool valid() const
Definition: Headers.cpp:120
clang::clangd::IncludeStructure::HeaderID
HeaderID
Definition: Headers.h:133
clang::clangd::IncludeInserter::calculateIncludePath
llvm::Optional< std::string > calculateIncludePath(const HeaderFile &InsertedHeader, llvm::StringRef IncludingFile) const
Determines the preferred way to #include a file, taking into account the search path.
Definition: Headers.cpp:250
clang::clangd::IncludeStructure::MainFileIncludes
std::vector< Inclusion > MainFileIncludes
Definition: Headers.h:160
clang::clangd::URI::parse
static llvm::Expected< URI > parse(llvm::StringRef Uri)
Parse a URI string "<scheme>:[//<authority>/]<path>".
Definition: URI.cpp:179
clang::clangd::replacementToEdit
TextEdit replacementToEdit(llvm::StringRef Code, const tooling::Replacement &R)
Definition: SourceCode.cpp:498
clang::clangd::IncludeInserter::shouldInsertInclude
bool shouldInsertInclude(PathRef DeclaringHeader, const HeaderFile &InsertedHeader) const
Checks whether to add an #include of the header into File.
Definition: Headers.cpp:236
clang::clangd::IncludeStructure
Definition: Headers.h:119
clang::clangd::isSelfContainedHeader
bool isSelfContainedHeader(const FileEntry *FE, FileID FID, const SourceManager &SM, HeaderSearch &HeaderInfo)
This scans source code, and should not be called when using a preamble.
Definition: SourceCode.cpp:1225
clang::clangd::getRankedIncludes
llvm::SmallVector< llvm::StringRef, 1 > getRankedIncludes(const Symbol &Sym)
Definition: Headers.cpp:145
clang::clangd::URI::resolve
static llvm::Expected< std::string > resolve(const URI &U, llvm::StringRef HintPath="")
Resolves the absolute path of U.
Definition: URI.cpp:247
clang::clangd::Inclusion::Directive
tok::PPKeywordKind Directive
Definition: Headers.h:60
clang::clangd::IncludeStructure::RecordHeaders
Definition: Headers.cpp:26
clang::clangd::Inclusion::HashLine
int HashLine
Definition: Headers.h:64
clang::clangd::Inclusion::Written
std::string Written
Definition: Headers.h:61
Logger.h
clang::clangd::Symbol
The class presents a C++ symbol, e.g.
Definition: Symbol.h:36
clang::clangd::URI::includeSpelling
static llvm::Expected< std::string > includeSpelling(const URI &U)
Gets the preferred spelling of this file for #include, if there is one, e.g.
Definition: URI.cpp:275
FileName
StringRef FileName
Definition: KernelNameRestrictionCheck.cpp:46
clang::clangd::toHeaderFile
llvm::Expected< HeaderFile > toHeaderFile(llvm::StringRef Header, llvm::StringRef HintPath)
Creates a HeaderFile from Header which can be either a URI or a literal include.
Definition: Headers.cpp:125
clang::clangd::operator<<
llvm::raw_ostream & operator<<(llvm::raw_ostream &OS, const CodeCompletion &C)
Definition: CodeComplete.cpp:2155
Parent
const Node * Parent
Definition: ExtractFunction.cpp:152
Entry
Definition: Modularize.cpp:428
SourceCode.h
clang::clangd::IncludeStructure::includeDepth
llvm::DenseMap< HeaderID, unsigned > includeDepth(HeaderID Root=MainFileID) const
Definition: Headers.cpp:201
IsAngled
bool IsAngled
true if this was an include with angle brackets
Definition: IncludeOrderCheck.cpp:40
Compiler.h
clang::clangd::IncludeStructure::collect
std::unique_ptr< PPCallbacks > collect(const CompilerInstance &CI)
Definition: Headers.cpp:161
clang::clangd::Inclusion
Definition: Headers.h:59
clang::clangd::isLiteralInclude
bool isLiteralInclude(llvm::StringRef Include)
Returns true if Include is literal include like "path" or <path>.
Definition: Headers.cpp:116
clang::clangd::Symbol::IncludeHeaderWithReferences
Definition: Symbol.h:87
clang::clangd::IncludeStructure::RecordHeaders::InclusionDirective
void InclusionDirective(SourceLocation HashLoc, const Token &IncludeTok, llvm::StringRef FileName, bool IsAngled, CharSourceRange, const FileEntry *File, llvm::StringRef, llvm::StringRef, const clang::Module *, SrcMgr::CharacteristicKind FileKind) override
Definition: Headers.cpp:34
clang::clangd::IncludeInserter::addExisting
void addExisting(const Inclusion &Inc)
Definition: Headers.cpp:228
clang::clangd::PathRef
llvm::StringRef PathRef
A typedef to represent a ref to file path.
Definition: Path.h:29
clang::clangd::Inclusion::Resolved
Path Resolved
Definition: Headers.h:62
clang::clangd::IncludeStructure::MainFileID
static const HeaderID MainFileID
Definition: Headers.h:165
clang::clangd::IncludeInserter::insert
llvm::Optional< TextEdit > insert(llvm::StringRef VerbatimHeader) const
Calculates an edit that inserts VerbatimHeader into code.
Definition: Headers.cpp:280
clang::clangd::Inclusion::FileKind
SrcMgr::CharacteristicKind FileKind
Definition: Headers.h:65
clang::clangd::Symbol::IncludeHeaderWithReferences::References
unsigned References
The number of translation units that reference this symbol and include this header.
Definition: Symbol.h:104
PPCallbacks
clang
===– Representation.cpp - ClangDoc Representation --------—*- C++ -*-===//
Definition: ApplyReplacements.h:27
OS
llvm::raw_string_ostream OS
Definition: TraceTests.cpp:163
clang::clangd::isInsideMainFile
bool isInsideMainFile(SourceLocation Loc, const SourceManager &SM)
Returns true iff Loc is inside the main file.
Definition: SourceCode.cpp:417
clang::clangd::IncludeStructure::getOrCreateID
HeaderID getOrCreateID(const FileEntry *Entry)
Definition: Headers.cpp:181
clang::clangd::Inclusion::HashOffset
unsigned HashOffset
Definition: Headers.h:63
clang::clangd::operator==
bool operator==(const Inclusion &LHS, const Inclusion &RHS)
Definition: Headers.cpp:294
clang::clangd::IncludeStructure::RecordHeaders::FileChanged
void FileChanged(SourceLocation Loc, FileChangeReason Reason, SrcMgr::CharacteristicKind FileType, FileID PrevFID) override
Definition: Headers.cpp:78
Out
CompiledFragmentImpl & Out
Definition: ConfigCompile.cpp:100
clang::clangd::HeaderFile::File
std::string File
Definition: Headers.h:41
clang::clangd::Symbol::IncludeHeaders
llvm::SmallVector< IncludeHeaderWithReferences, 1 > IncludeHeaders
One Symbol can potentially be included via different headers.
Definition: Symbol.h:111
clang::clangd::Symbol::IncludeHeaderWithReferences::IncludeHeader
llvm::StringRef IncludeHeader
This can be either a URI of the header to be #include'd for this symbol, or a literal header quoted w...
Definition: Symbol.h:101
clang::clangd::IncludeStructure::IncludeChildren
llvm::DenseMap< HeaderID, SmallVector< HeaderID > > IncludeChildren
Definition: Headers.h:158
clang::clangd::HeaderFile::Verbatim
bool Verbatim
If this is true, File is a literal string quoted with <> or "" that can be #included directly; otherw...
Definition: Headers.h:44
clang::clangd::translatePreamblePatchLocation
SourceLocation translatePreamblePatchLocation(SourceLocation Loc, const SourceManager &SM)
Translates locations inside preamble patch to their main-file equivalent using presumed locations.
Definition: Preamble.cpp:587