clang-tools  10.0.0svn
clangd/IncludeFixer.cpp
Go to the documentation of this file.
1 //===--- IncludeFixer.cpp ----------------------------------------*- 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 "IncludeFixer.h"
10 #include "AST.h"
11 #include "Diagnostics.h"
12 #include "Logger.h"
13 #include "SourceCode.h"
14 #include "Trace.h"
15 #include "index/Index.h"
16 #include "index/Symbol.h"
17 #include "clang/AST/Decl.h"
18 #include "clang/AST/DeclBase.h"
19 #include "clang/AST/DeclarationName.h"
20 #include "clang/AST/NestedNameSpecifier.h"
21 #include "clang/AST/Type.h"
22 #include "clang/Basic/Diagnostic.h"
23 #include "clang/Basic/DiagnosticSema.h"
24 #include "clang/Basic/LangOptions.h"
25 #include "clang/Basic/SourceLocation.h"
26 #include "clang/Basic/SourceManager.h"
27 #include "clang/Basic/TokenKinds.h"
28 #include "clang/Lex/Lexer.h"
29 #include "clang/Sema/DeclSpec.h"
30 #include "clang/Sema/Lookup.h"
31 #include "clang/Sema/Scope.h"
32 #include "clang/Sema/Sema.h"
33 #include "clang/Sema/TypoCorrection.h"
34 #include "llvm/ADT/ArrayRef.h"
35 #include "llvm/ADT/DenseMap.h"
36 #include "llvm/ADT/None.h"
37 #include "llvm/ADT/Optional.h"
38 #include "llvm/ADT/StringExtras.h"
39 #include "llvm/ADT/StringRef.h"
40 #include "llvm/ADT/StringSet.h"
41 #include "llvm/Support/Error.h"
42 #include "llvm/Support/FormatVariadic.h"
43 #include <vector>
44 
45 namespace clang {
46 namespace clangd {
47 
48 namespace {
49 
50 // Collects contexts visited during a Sema name lookup.
51 class VisitedContextCollector : public VisibleDeclConsumer {
52 public:
53  void EnteredContext(DeclContext *Ctx) override { Visited.push_back(Ctx); }
54 
55  void FoundDecl(NamedDecl *ND, NamedDecl *Hiding, DeclContext *Ctx,
56  bool InBaseClass) override {}
57 
58  std::vector<DeclContext *> takeVisitedContexts() {
59  return std::move(Visited);
60  }
61 
62 private:
63  std::vector<DeclContext *> Visited;
64 };
65 
66 } // namespace
67 
68 std::vector<Fix> IncludeFixer::fix(DiagnosticsEngine::Level DiagLevel,
69  const clang::Diagnostic &Info) const {
70  switch (Info.getID()) {
71  case diag::err_incomplete_type:
72  case diag::err_incomplete_member_access:
73  case diag::err_incomplete_base_class:
74  case diag::err_incomplete_nested_name_spec:
75  // Incomplete type diagnostics should have a QualType argument for the
76  // incomplete type.
77  for (unsigned Idx = 0; Idx < Info.getNumArgs(); ++Idx) {
78  if (Info.getArgKind(Idx) == DiagnosticsEngine::ak_qualtype) {
79  auto QT = QualType::getFromOpaquePtr((void *)Info.getRawArg(Idx));
80  if (const Type *T = QT.getTypePtrOrNull())
81  if (T->isIncompleteType())
82  return fixIncompleteType(*T);
83  }
84  }
85  break;
86  case diag::err_unknown_typename:
87  case diag::err_unknown_typename_suggest:
88  case diag::err_typename_nested_not_found:
89  case diag::err_no_template:
90  case diag::err_no_template_suggest:
91  case diag::err_undeclared_use:
92  case diag::err_undeclared_use_suggest:
93  case diag::err_undeclared_var_use:
94  case diag::err_undeclared_var_use_suggest:
95  case diag::err_no_member: // Could be no member in namespace.
96  case diag::err_no_member_suggest:
97  if (LastUnresolvedName) {
98  // Try to fix unresolved name caused by missing declaraion.
99  // E.g.
100  // clang::SourceManager SM;
101  // ~~~~~~~~~~~~~
102  // UnresolvedName
103  // or
104  // namespace clang { SourceManager SM; }
105  // ~~~~~~~~~~~~~
106  // UnresolvedName
107  // We only attempt to recover a diagnostic if it has the same location as
108  // the last seen unresolved name.
109  if (DiagLevel >= DiagnosticsEngine::Error &&
110  LastUnresolvedName->Loc == Info.getLocation())
111  return fixUnresolvedName();
112  }
113  }
114  return {};
115 }
116 
117 std::vector<Fix> IncludeFixer::fixIncompleteType(const Type &T) const {
118  // Only handle incomplete TagDecl type.
119  const TagDecl *TD = T.getAsTagDecl();
120  if (!TD)
121  return {};
122  std::string TypeName = printQualifiedName(*TD);
123  trace::Span Tracer("Fix include for incomplete type");
124  SPAN_ATTACH(Tracer, "type", TypeName);
125  vlog("Trying to fix include for incomplete type {0}", TypeName);
126 
127  auto ID = getSymbolID(TD);
128  if (!ID)
129  return {};
130  llvm::Optional<const SymbolSlab *> Symbols = lookupCached(*ID);
131  if (!Symbols)
132  return {};
133  const SymbolSlab &Syms = **Symbols;
134  std::vector<Fix> Fixes;
135  if (!Syms.empty()) {
136  auto &Matched = *Syms.begin();
137  if (!Matched.IncludeHeaders.empty() && Matched.Definition &&
138  Matched.CanonicalDeclaration.FileURI == Matched.Definition.FileURI)
139  Fixes = fixesForSymbols(Syms);
140  }
141  return Fixes;
142 }
143 
144 std::vector<Fix> IncludeFixer::fixesForSymbols(const SymbolSlab &Syms) const {
145  auto Inserted = [&](const Symbol &Sym, llvm::StringRef Header)
146  -> llvm::Expected<std::pair<std::string, bool>> {
147  auto ResolvedDeclaring =
149  if (!ResolvedDeclaring)
150  return ResolvedDeclaring.takeError();
151  auto ResolvedInserted = toHeaderFile(Header, File);
152  if (!ResolvedInserted)
153  return ResolvedInserted.takeError();
154  auto Spelled = Inserter->calculateIncludePath(*ResolvedInserted, File);
155  if (!Spelled)
156  return llvm::createStringError(llvm::inconvertibleErrorCode(),
157  "Header not on include path");
158  return std::make_pair(
159  std::move(*Spelled),
160  Inserter->shouldInsertInclude(*ResolvedDeclaring, *ResolvedInserted));
161  };
162 
163  std::vector<Fix> Fixes;
164  // Deduplicate fixes by include headers. This doesn't distiguish symbols in
165  // different scopes from the same header, but this case should be rare and is
166  // thus ignored.
167  llvm::StringSet<> InsertedHeaders;
168  for (const auto &Sym : Syms) {
169  for (const auto &Inc : getRankedIncludes(Sym)) {
170  if (auto ToInclude = Inserted(Sym, Inc)) {
171  if (ToInclude->second) {
172  auto I = InsertedHeaders.try_emplace(ToInclude->first);
173  if (!I.second)
174  continue;
175  if (auto Edit = Inserter->insert(ToInclude->first))
176  Fixes.push_back(
177  Fix{llvm::formatv("Add include {0} for symbol {1}{2}",
178  ToInclude->first, Sym.Scope, Sym.Name),
179  {std::move(*Edit)}});
180  }
181  } else {
182  vlog("Failed to calculate include insertion for {0} into {1}: {2}", Inc,
183  File, ToInclude.takeError());
184  }
185  }
186  }
187  return Fixes;
188 }
189 
190 // Returns the identifiers qualified by an unresolved name. \p Loc is the
191 // start location of the unresolved name. For the example below, this returns
192 // "::X::Y" that is qualified by unresolved name "clangd":
193 // clang::clangd::X::Y
194 // ~
195 llvm::Optional<std::string> qualifiedByUnresolved(const SourceManager &SM,
196  SourceLocation Loc,
197  const LangOptions &LangOpts) {
198  std::string Result;
199 
200  SourceLocation NextLoc = Loc;
201  while (auto CCTok = Lexer::findNextToken(NextLoc, SM, LangOpts)) {
202  if (!CCTok->is(tok::coloncolon))
203  break;
204  auto IDTok = Lexer::findNextToken(CCTok->getLocation(), SM, LangOpts);
205  if (!IDTok || !IDTok->is(tok::raw_identifier))
206  break;
207  Result.append(("::" + IDTok->getRawIdentifier()).str());
208  NextLoc = IDTok->getLocation();
209  }
210  if (Result.empty())
211  return llvm::None;
212  return Result;
213 }
214 
215 // An unresolved name and its scope information that can be extracted cheaply.
217  std::string Name;
218  // This is the part of what was typed that was resolved, and it's in its
219  // resolved form not its typed form (think `namespace clang { clangd::x }` -->
220  // `clang::clangd::`).
221  llvm::Optional<std::string> ResolvedScope;
222 
223  // Unresolved part of the scope. When the unresolved name is a specifier, we
224  // use the name that comes after it as the alternative name to resolve and use
225  // the specifier as the extra scope in the accessible scopes.
226  llvm::Optional<std::string> UnresolvedScope;
227 };
228 
229 // Extracts unresolved name and scope information around \p Unresolved.
230 // FIXME: try to merge this with the scope-wrangling code in CodeComplete.
231 llvm::Optional<CheapUnresolvedName> extractUnresolvedNameCheaply(
232  const SourceManager &SM, const DeclarationNameInfo &Unresolved,
233  CXXScopeSpec *SS, const LangOptions &LangOpts, bool UnresolvedIsSpecifier) {
234  bool Invalid = false;
235  llvm::StringRef Code = SM.getBufferData(
236  SM.getDecomposedLoc(Unresolved.getBeginLoc()).first, &Invalid);
237  if (Invalid)
238  return llvm::None;
239  CheapUnresolvedName Result;
240  Result.Name = Unresolved.getAsString();
241  if (SS && SS->isNotEmpty()) { // "::" or "ns::"
242  if (auto *Nested = SS->getScopeRep()) {
243  if (Nested->getKind() == NestedNameSpecifier::Global)
244  Result.ResolvedScope = "";
245  else if (const auto *NS = Nested->getAsNamespace()) {
246  auto SpecifiedNS = printNamespaceScope(*NS);
247 
248  // Check the specifier spelled in the source.
249  // If the resolved scope doesn't end with the spelled scope. The
250  // resolved scope can come from a sema typo correction. For example,
251  // sema assumes that "clangd::" is a typo of "clang::" and uses
252  // "clang::" as the specified scope in:
253  // namespace clang { clangd::X; }
254  // In this case, we use the "typo" specifier as extra scope instead
255  // of using the scope assumed by sema.
256  auto B = SM.getFileOffset(SS->getBeginLoc());
257  auto E = SM.getFileOffset(SS->getEndLoc());
258  std::string Spelling = (Code.substr(B, E - B) + "::").str();
259  if (llvm::StringRef(SpecifiedNS).endswith(Spelling))
260  Result.ResolvedScope = SpecifiedNS;
261  else
262  Result.UnresolvedScope = Spelling;
263  } else if (const auto *ANS = Nested->getAsNamespaceAlias()) {
264  Result.ResolvedScope = printNamespaceScope(*ANS->getNamespace());
265  } else {
266  // We don't fix symbols in scopes that are not top-level e.g. class
267  // members, as we don't collect includes for them.
268  return llvm::None;
269  }
270  }
271  }
272 
273  if (UnresolvedIsSpecifier) {
274  // If the unresolved name is a specifier e.g.
275  // clang::clangd::X
276  // ~~~~~~
277  // We try to resolve clang::clangd::X instead of clang::clangd.
278  // FIXME: We won't be able to fix include if the specifier is what we
279  // should resolve (e.g. it's a class scope specifier). Collecting include
280  // headers for nested types could make this work.
281 
282  // Not using the end location as it doesn't always point to the end of
283  // identifier.
284  if (auto QualifiedByUnresolved =
285  qualifiedByUnresolved(SM, Unresolved.getBeginLoc(), LangOpts)) {
286  auto Split = splitQualifiedName(*QualifiedByUnresolved);
287  if (!Result.UnresolvedScope)
288  Result.UnresolvedScope.emplace();
289  // If UnresolvedSpecifiedScope is already set, we simply append the
290  // extra scope. Suppose the unresolved name is "index" in the following
291  // example:
292  // namespace clang { clangd::index::X; }
293  // ~~~~~~ ~~~~~
294  // "clangd::" is assumed to be clang:: by Sema, and we would have used
295  // it as extra scope. With "index" being a specifier, we append "index::"
296  // to the extra scope.
297  Result.UnresolvedScope->append((Result.Name + Split.first).str());
298  Result.Name = Split.second;
299  }
300  }
301  return Result;
302 }
303 
304 /// Returns all namespace scopes that the unqualified lookup would visit.
305 std::vector<std::string>
306 collectAccessibleScopes(Sema &Sem, const DeclarationNameInfo &Typo, Scope *S,
307  Sema::LookupNameKind LookupKind) {
308  std::vector<std::string> Scopes;
309  VisitedContextCollector Collector;
310  Sem.LookupVisibleDecls(S, LookupKind, Collector,
311  /*IncludeGlobalScope=*/false,
312  /*LoadExternal=*/false);
313 
314  Scopes.push_back("");
315  for (const auto *Ctx : Collector.takeVisitedContexts()) {
316  if (isa<NamespaceDecl>(Ctx))
317  Scopes.push_back(printNamespaceScope(*Ctx));
318  }
319  return Scopes;
320 }
321 
323 public:
324  UnresolvedNameRecorder(llvm::Optional<UnresolvedName> &LastUnresolvedName)
325  : LastUnresolvedName(LastUnresolvedName) {}
326 
327  void InitializeSema(Sema &S) override { this->SemaPtr = &S; }
328 
329  // Captures the latest typo and treat it as an unresolved name that can
330  // potentially be fixed by adding #includes.
331  TypoCorrection CorrectTypo(const DeclarationNameInfo &Typo, int LookupKind,
332  Scope *S, CXXScopeSpec *SS,
333  CorrectionCandidateCallback &CCC,
334  DeclContext *MemberContext, bool EnteringContext,
335  const ObjCObjectPointerType *OPT) override {
336  assert(SemaPtr && "Sema must have been set.");
337  if (SemaPtr->isSFINAEContext())
338  return TypoCorrection();
339  if (!isInsideMainFile(Typo.getLoc(), SemaPtr->SourceMgr))
340  return clang::TypoCorrection();
341 
342  auto Extracted = extractUnresolvedNameCheaply(
343  SemaPtr->SourceMgr, Typo, SS, SemaPtr->LangOpts,
344  static_cast<Sema::LookupNameKind>(LookupKind) ==
345  Sema::LookupNameKind::LookupNestedNameSpecifierName);
346  if (!Extracted)
347  return TypoCorrection();
348 
349  UnresolvedName Unresolved;
350  Unresolved.Name = Extracted->Name;
351  Unresolved.Loc = Typo.getBeginLoc();
352  if (!Extracted->ResolvedScope && !S) // Give up if no scope available.
353  return TypoCorrection();
354 
355  if (Extracted->ResolvedScope)
356  Unresolved.Scopes.push_back(*Extracted->ResolvedScope);
357  else // no qualifier or qualifier is unresolved.
358  Unresolved.Scopes = collectAccessibleScopes(
359  *SemaPtr, Typo, S, static_cast<Sema::LookupNameKind>(LookupKind));
360 
361  if (Extracted->UnresolvedScope) {
362  for (std::string &Scope : Unresolved.Scopes)
363  Scope += *Extracted->UnresolvedScope;
364  }
365 
366  LastUnresolvedName = std::move(Unresolved);
367 
368  // Never return a valid correction to try to recover. Our suggested fixes
369  // always require a rebuild.
370  return TypoCorrection();
371  }
372 
373 private:
374  Sema *SemaPtr = nullptr;
375 
376  llvm::Optional<UnresolvedName> &LastUnresolvedName;
377 };
378 
379 llvm::IntrusiveRefCntPtr<ExternalSemaSource>
381  return new UnresolvedNameRecorder(LastUnresolvedName);
382 }
383 
384 std::vector<Fix> IncludeFixer::fixUnresolvedName() const {
385  assert(LastUnresolvedName.hasValue());
386  auto &Unresolved = *LastUnresolvedName;
387  vlog("Trying to fix unresolved name \"{0}\" in scopes: [{1}]",
388  Unresolved.Name, llvm::join(Unresolved.Scopes, ", "));
389 
390  FuzzyFindRequest Req;
391  Req.AnyScope = false;
392  Req.Query = Unresolved.Name;
393  Req.Scopes = Unresolved.Scopes;
394  Req.RestrictForCodeCompletion = true;
395  Req.Limit = 100;
396 
397  if (llvm::Optional<const SymbolSlab *> Syms = fuzzyFindCached(Req))
398  return fixesForSymbols(**Syms);
399 
400  return {};
401 }
402 
403 llvm::Optional<const SymbolSlab *>
404 IncludeFixer::fuzzyFindCached(const FuzzyFindRequest &Req) const {
405  auto ReqStr = llvm::formatv("{0}", toJSON(Req)).str();
406  auto I = FuzzyFindCache.find(ReqStr);
407  if (I != FuzzyFindCache.end())
408  return &I->second;
409 
410  if (IndexRequestCount >= IndexRequestLimit)
411  return llvm::None;
412  IndexRequestCount++;
413 
414  SymbolSlab::Builder Matches;
415  Index.fuzzyFind(Req, [&](const Symbol &Sym) {
416  if (Sym.Name != Req.Query)
417  return;
418  if (!Sym.IncludeHeaders.empty())
419  Matches.insert(Sym);
420  });
421  auto Syms = std::move(Matches).build();
422  auto E = FuzzyFindCache.try_emplace(ReqStr, std::move(Syms));
423  return &E.first->second;
424 }
425 
426 llvm::Optional<const SymbolSlab *>
427 IncludeFixer::lookupCached(const SymbolID &ID) const {
428  LookupRequest Req;
429  Req.IDs.insert(ID);
430 
431  auto I = LookupCache.find(ID);
432  if (I != LookupCache.end())
433  return &I->second;
434 
435  if (IndexRequestCount >= IndexRequestLimit)
436  return llvm::None;
437  IndexRequestCount++;
438 
439  // FIXME: consider batching the requests for all diagnostics.
440  SymbolSlab::Builder Matches;
441  Index.lookup(Req, [&](const Symbol &Sym) { Matches.insert(Sym); });
442  auto Syms = std::move(Matches).build();
443 
444  std::vector<Fix> Fixes;
445  if (!Syms.empty()) {
446  auto &Matched = *Syms.begin();
447  if (!Matched.IncludeHeaders.empty() && Matched.Definition &&
448  Matched.CanonicalDeclaration.FileURI == Matched.Definition.FileURI)
449  Fixes = fixesForSymbols(Syms);
450  }
451  auto E = LookupCache.try_emplace(ID, std::move(Syms));
452  return &E.first->second;
453 }
454 
455 } // namespace clangd
456 } // namespace clang
SourceLocation Loc
&#39;#&#39; location in the include directive
llvm::Optional< std::string > qualifiedByUnresolved(const SourceManager &SM, SourceLocation Loc, const LangOptions &LangOpts)
std::string Code
An immutable symbol container that stores a set of symbols.
Definition: Symbol.h:177
llvm::json::Value toJSON(const FuzzyFindRequest &Request)
Definition: Index.cpp:48
bool AnyScope
If set to true, allow symbols from any scope.
Definition: Index.h:39
std::string printQualifiedName(const NamedDecl &ND)
Returns the qualified name of ND.
Definition: AST.cpp:87
llvm::Optional< SymbolID > getSymbolID(const Decl *D)
Gets the symbol ID for a declaration, if possible.
Definition: AST.cpp:199
bool RestrictForCodeCompletion
If set to true, only symbols for completion support will be considered.
Definition: Index.h:44
std::string printNamespaceScope(const DeclContext &DC)
Returns the first enclosing namespace scope starting from DC.
Definition: AST.cpp:191
llvm::DenseSet< SymbolID > IDs
Definition: Index.h:64
std::pair< StringRef, StringRef > splitQualifiedName(StringRef QName)
Definition: SourceCode.cpp:602
bool isInsideMainFile(SourceLocation Loc, const SourceManager &SM)
Returns true iff Loc is inside the main file.
Definition: SourceCode.cpp:537
void insert(const Symbol &S)
Adds a symbol, overwriting any existing one with the same ID.
Definition: Symbol.cpp:50
Documents should not be synced at all.
llvm::Optional< std::string > UnresolvedScope
void vlog(const char *Fmt, Ts &&... Vals)
Definition: Logger.h:67
llvm::Optional< CheapUnresolvedName > extractUnresolvedNameCheaply(const SourceManager &SM, const DeclarationNameInfo &Unresolved, CXXScopeSpec *SS, const LangOptions &LangOpts, bool UnresolvedIsSpecifier)
SymbolSlab::Builder is a mutable container that can &#39;freeze&#39; to SymbolSlab.
Definition: Symbol.h:199
std::vector< std::string > Scopes
If this is non-empty, symbols must be in at least one of the scopes (e.g.
Definition: Index.h:36
Context Ctx
llvm::Optional< std::string > ResolvedScope
bool empty() const
Definition: Symbol.h:190
llvm::SmallVector< IncludeHeaderWithReferences, 1 > IncludeHeaders
One Symbol can potentially be incuded via different headers.
Definition: Symbol.h:111
std::string Query
A query string for the fuzzy find.
Definition: Index.h:29
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:77
SymbolLocation CanonicalDeclaration
The location of the preferred declaration of the symbol.
Definition: Symbol.h:56
std::shared_ptr< SymbolCollector > Collector
Represents a single fix-it that editor can apply to fix the error.
Definition: Diagnostics.h:71
SymbolSlab Symbols
An information message.
TypoCorrection CorrectTypo(const DeclarationNameInfo &Typo, int LookupKind, Scope *S, CXXScopeSpec *SS, CorrectionCandidateCallback &CCC, DeclContext *MemberContext, bool EnteringContext, const ObjCObjectPointerType *OPT) override
The class presents a C++ symbol, e.g.
Definition: Symbol.h:36
===– Representation.cpp - ClangDoc Representation --------—*- C++ -*-===//
llvm::IntrusiveRefCntPtr< ExternalSemaSource > unresolvedNameRecorder()
Returns an ExternalSemaSource that records failed name lookups in Sema.
llvm::StringRef Name
The unqualified name of the symbol, e.g. "bar" (for ns::bar).
Definition: Symbol.h:42
const_iterator begin() const
Definition: Symbol.h:185
llvm::SmallVector< llvm::StringRef, 1 > getRankedIncludes(const Symbol &Sym)
Definition: Headers.cpp:97
std::vector< Fix > fix(DiagnosticsEngine::Level DiagLevel, const clang::Diagnostic &Info) const
Returns include insertions that can potentially recover the diagnostic.
std::vector< const char * > Expected
llvm::Optional< uint32_t > Limit
The number of top candidates to return.
Definition: Index.h:42
static llvm::Expected< std::string > resolve(const URI &U, llvm::StringRef HintPath="")
Resolves the absolute path of U.
Definition: URI.cpp:233
static std::string join(ArrayRef< SpecialMemberFunctionsCheck::SpecialMemberFunctionKind > SMFS, llvm::StringRef AndOr)
std::vector< std::string > collectAccessibleScopes(Sema &Sem, const DeclarationNameInfo &Typo, Scope *S, Sema::LookupNameKind LookupKind)
Returns all namespace scopes that the unqualified lookup would visit.
Records an event whose duration is the lifetime of the Span object.
Definition: Trace.h:81
#define SPAN_ATTACH(S, Name, Expr)
Attach a key-value pair to a Span event.
Definition: Trace.h:97
A set of edits generated for a single file.
Definition: SourceCode.h:210
NodeType Type
UnresolvedNameRecorder(llvm::Optional< UnresolvedName > &LastUnresolvedName)
const SymbolIndex * Index
Definition: Dexp.cpp:84