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 "SourceCode.h"
13 #include "index/Index.h"
14 #include "index/Symbol.h"
15 #include "support/Logger.h"
16 #include "support/Trace.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:
EnteredContext(DeclContext * Ctx)53 void EnteredContext(DeclContext *Ctx) override { Visited.push_back(Ctx); }
54
FoundDecl(NamedDecl * ND,NamedDecl * Hiding,DeclContext * Ctx,bool InBaseClass)55 void FoundDecl(NamedDecl *ND, NamedDecl *Hiding, DeclContext *Ctx,
56 bool InBaseClass) override {}
57
takeVisitedContexts()58 std::vector<DeclContext *> takeVisitedContexts() {
59 return std::move(Visited);
60 }
61
62 private:
63 std::vector<DeclContext *> Visited;
64 };
65
66 } // namespace
67
fix(DiagnosticsEngine::Level DiagLevel,const clang::Diagnostic & Info) const68 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 declaration.
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
fixIncompleteType(const Type & T) const117 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
fixesForSymbols(const SymbolSlab & Syms) const144 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 =
148 URI::resolve(Sym.CanonicalDeclaration.FileURI, File);
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 distinguish 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(Fix{std::string(llvm::formatv(
177 "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 // ~
qualifiedByUnresolved(const SourceManager & SM,SourceLocation Loc,const LangOptions & LangOpts)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.
216 struct CheapUnresolvedName {
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.
extractUnresolvedNameCheaply(const SourceManager & SM,const DeclarationNameInfo & Unresolved,CXXScopeSpec * SS,const LangOptions & LangOpts,bool UnresolvedIsSpecifier)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 = std::string(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>
collectAccessibleScopes(Sema & Sem,const DeclarationNameInfo & Typo,Scope * S,Sema::LookupNameKind LookupKind)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
322 class IncludeFixer::UnresolvedNameRecorder : public ExternalSemaSource {
323 public:
UnresolvedNameRecorder(llvm::Optional<UnresolvedName> & LastUnresolvedName)324 UnresolvedNameRecorder(llvm::Optional<UnresolvedName> &LastUnresolvedName)
325 : LastUnresolvedName(LastUnresolvedName) {}
326
InitializeSema(Sema & S)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.
CorrectTypo(const DeclarationNameInfo & Typo,int LookupKind,Scope * S,CXXScopeSpec * SS,CorrectionCandidateCallback & CCC,DeclContext * MemberContext,bool EnteringContext,const ObjCObjectPointerType * OPT)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>
unresolvedNameRecorder()380 IncludeFixer::unresolvedNameRecorder() {
381 return new UnresolvedNameRecorder(LastUnresolvedName);
382 }
383
fixUnresolvedName() const384 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 *>
fuzzyFindCached(const FuzzyFindRequest & Req) const404 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 *>
lookupCached(const SymbolID & ID) const427 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
457