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:
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_nested_name_spec:
72   case diag::err_incomplete_base_class:
73   case diag::err_incomplete_member_access:
74   case diag::err_incomplete_type:
75   case diag::err_typecheck_decl_incomplete_type:
76   case diag::err_typecheck_incomplete_tag:
77   case diag::err_invalid_incomplete_type_use:
78   case diag::err_sizeof_alignof_incomplete_or_sizeless_type:
79   case diag::err_for_range_incomplete_type:
80   case diag::err_func_def_incomplete_result:
81   case diag::err_field_incomplete_or_sizeless:
82     // Incomplete type diagnostics should have a QualType argument for the
83     // incomplete type.
84     for (unsigned Idx = 0; Idx < Info.getNumArgs(); ++Idx) {
85       if (Info.getArgKind(Idx) == DiagnosticsEngine::ak_qualtype) {
86         auto QT = QualType::getFromOpaquePtr((void *)Info.getRawArg(Idx));
87         if (const Type *T = QT.getTypePtrOrNull())
88           if (T->isIncompleteType())
89             return fixIncompleteType(*T);
90       }
91     }
92     break;
93   case diag::err_unknown_typename:
94   case diag::err_unknown_typename_suggest:
95   case diag::err_typename_nested_not_found:
96   case diag::err_no_template:
97   case diag::err_no_template_suggest:
98   case diag::err_undeclared_use:
99   case diag::err_undeclared_use_suggest:
100   case diag::err_undeclared_var_use:
101   case diag::err_undeclared_var_use_suggest:
102   case diag::err_no_member: // Could be no member in namespace.
103   case diag::err_no_member_suggest:
104   case diag::err_no_member_template:
105   case diag::err_no_member_template_suggest:
106     if (LastUnresolvedName) {
107       // Try to fix unresolved name caused by missing declaration.
108       // E.g.
109       //   clang::SourceManager SM;
110       //          ~~~~~~~~~~~~~
111       //          UnresolvedName
112       //   or
113       //   namespace clang {  SourceManager SM; }
114       //                      ~~~~~~~~~~~~~
115       //                      UnresolvedName
116       // We only attempt to recover a diagnostic if it has the same location as
117       // the last seen unresolved name.
118       if (DiagLevel >= DiagnosticsEngine::Error &&
119           LastUnresolvedName->Loc == Info.getLocation())
120         return fixUnresolvedName();
121     }
122   }
123   return {};
124 }
125 
126 std::vector<Fix> IncludeFixer::fixIncompleteType(const Type &T) const {
127   // Only handle incomplete TagDecl type.
128   const TagDecl *TD = T.getAsTagDecl();
129   if (!TD)
130     return {};
131   std::string TypeName = printQualifiedName(*TD);
132   trace::Span Tracer("Fix include for incomplete type");
133   SPAN_ATTACH(Tracer, "type", TypeName);
134   vlog("Trying to fix include for incomplete type {0}", TypeName);
135 
136   auto ID = getSymbolID(TD);
137   if (!ID)
138     return {};
139   llvm::Optional<const SymbolSlab *> Symbols = lookupCached(ID);
140   if (!Symbols)
141     return {};
142   const SymbolSlab &Syms = **Symbols;
143   std::vector<Fix> Fixes;
144   if (!Syms.empty()) {
145     auto &Matched = *Syms.begin();
146     if (!Matched.IncludeHeaders.empty() && Matched.Definition &&
147         Matched.CanonicalDeclaration.FileURI == Matched.Definition.FileURI)
148       Fixes = fixesForSymbols(Syms);
149   }
150   return Fixes;
151 }
152 
153 std::vector<Fix> IncludeFixer::fixesForSymbols(const SymbolSlab &Syms) const {
154   auto Inserted = [&](const Symbol &Sym, llvm::StringRef Header)
155       -> llvm::Expected<std::pair<std::string, bool>> {
156     auto ResolvedDeclaring =
157         URI::resolve(Sym.CanonicalDeclaration.FileURI, File);
158     if (!ResolvedDeclaring)
159       return ResolvedDeclaring.takeError();
160     auto ResolvedInserted = toHeaderFile(Header, File);
161     if (!ResolvedInserted)
162       return ResolvedInserted.takeError();
163     auto Spelled = Inserter->calculateIncludePath(*ResolvedInserted, File);
164     if (!Spelled)
165       return error("Header not on include path");
166     return std::make_pair(
167         std::move(*Spelled),
168         Inserter->shouldInsertInclude(*ResolvedDeclaring, *ResolvedInserted));
169   };
170 
171   std::vector<Fix> Fixes;
172   // Deduplicate fixes by include headers. This doesn't distinguish symbols in
173   // different scopes from the same header, but this case should be rare and is
174   // thus ignored.
175   llvm::StringSet<> InsertedHeaders;
176   for (const auto &Sym : Syms) {
177     for (const auto &Inc : getRankedIncludes(Sym)) {
178       if (auto ToInclude = Inserted(Sym, Inc)) {
179         if (ToInclude->second) {
180           auto I = InsertedHeaders.try_emplace(ToInclude->first);
181           if (!I.second)
182             continue;
183           if (auto Edit = Inserter->insert(ToInclude->first))
184             Fixes.push_back(Fix{std::string(llvm::formatv(
185                                     "Add include {0} for symbol {1}{2}",
186                                     ToInclude->first, Sym.Scope, Sym.Name)),
187                                 {std::move(*Edit)}});
188         }
189       } else {
190         vlog("Failed to calculate include insertion for {0} into {1}: {2}", Inc,
191              File, ToInclude.takeError());
192       }
193     }
194   }
195   return Fixes;
196 }
197 
198 // Returns the identifiers qualified by an unresolved name. \p Loc is the
199 // start location of the unresolved name. For the example below, this returns
200 // "::X::Y" that is qualified by unresolved name "clangd":
201 //     clang::clangd::X::Y
202 //            ~
203 llvm::Optional<std::string> qualifiedByUnresolved(const SourceManager &SM,
204                                                   SourceLocation Loc,
205                                                   const LangOptions &LangOpts) {
206   std::string Result;
207 
208   SourceLocation NextLoc = Loc;
209   while (auto CCTok = Lexer::findNextToken(NextLoc, SM, LangOpts)) {
210     if (!CCTok->is(tok::coloncolon))
211       break;
212     auto IDTok = Lexer::findNextToken(CCTok->getLocation(), SM, LangOpts);
213     if (!IDTok || !IDTok->is(tok::raw_identifier))
214       break;
215     Result.append(("::" + IDTok->getRawIdentifier()).str());
216     NextLoc = IDTok->getLocation();
217   }
218   if (Result.empty())
219     return llvm::None;
220   return Result;
221 }
222 
223 // An unresolved name and its scope information that can be extracted cheaply.
224 struct CheapUnresolvedName {
225   std::string Name;
226   // This is the part of what was typed that was resolved, and it's in its
227   // resolved form not its typed form (think `namespace clang { clangd::x }` -->
228   // `clang::clangd::`).
229   llvm::Optional<std::string> ResolvedScope;
230 
231   // Unresolved part of the scope. When the unresolved name is a specifier, we
232   // use the name that comes after it as the alternative name to resolve and use
233   // the specifier as the extra scope in the accessible scopes.
234   llvm::Optional<std::string> UnresolvedScope;
235 };
236 
237 // Extracts unresolved name and scope information around \p Unresolved.
238 // FIXME: try to merge this with the scope-wrangling code in CodeComplete.
239 llvm::Optional<CheapUnresolvedName> extractUnresolvedNameCheaply(
240     const SourceManager &SM, const DeclarationNameInfo &Unresolved,
241     CXXScopeSpec *SS, const LangOptions &LangOpts, bool UnresolvedIsSpecifier) {
242   bool Invalid = false;
243   llvm::StringRef Code = SM.getBufferData(
244       SM.getDecomposedLoc(Unresolved.getBeginLoc()).first, &Invalid);
245   if (Invalid)
246     return llvm::None;
247   CheapUnresolvedName Result;
248   Result.Name = Unresolved.getAsString();
249   if (SS && SS->isNotEmpty()) { // "::" or "ns::"
250     if (auto *Nested = SS->getScopeRep()) {
251       if (Nested->getKind() == NestedNameSpecifier::Global)
252         Result.ResolvedScope = "";
253       else if (const auto *NS = Nested->getAsNamespace()) {
254         auto SpecifiedNS = printNamespaceScope(*NS);
255 
256         // Check the specifier spelled in the source.
257         // If the resolved scope doesn't end with the spelled scope. The
258         // resolved scope can come from a sema typo correction. For example,
259         // sema assumes that "clangd::" is a typo of "clang::" and uses
260         // "clang::" as the specified scope in:
261         //     namespace clang { clangd::X; }
262         // In this case, we use the "typo" specifier as extra scope instead
263         // of using the scope assumed by sema.
264         auto B = SM.getFileOffset(SS->getBeginLoc());
265         auto E = SM.getFileOffset(SS->getEndLoc());
266         std::string Spelling = (Code.substr(B, E - B) + "::").str();
267         if (llvm::StringRef(SpecifiedNS).endswith(Spelling))
268           Result.ResolvedScope = SpecifiedNS;
269         else
270           Result.UnresolvedScope = Spelling;
271       } else if (const auto *ANS = Nested->getAsNamespaceAlias()) {
272         Result.ResolvedScope = printNamespaceScope(*ANS->getNamespace());
273       } else {
274         // We don't fix symbols in scopes that are not top-level e.g. class
275         // members, as we don't collect includes for them.
276         return llvm::None;
277       }
278     }
279   }
280 
281   if (UnresolvedIsSpecifier) {
282     // If the unresolved name is a specifier e.g.
283     //      clang::clangd::X
284     //             ~~~~~~
285     // We try to resolve clang::clangd::X instead of clang::clangd.
286     // FIXME: We won't be able to fix include if the specifier is what we
287     // should resolve (e.g. it's a class scope specifier). Collecting include
288     // headers for nested types could make this work.
289 
290     // Not using the end location as it doesn't always point to the end of
291     // identifier.
292     if (auto QualifiedByUnresolved =
293             qualifiedByUnresolved(SM, Unresolved.getBeginLoc(), LangOpts)) {
294       auto Split = splitQualifiedName(*QualifiedByUnresolved);
295       if (!Result.UnresolvedScope)
296         Result.UnresolvedScope.emplace();
297       // If UnresolvedSpecifiedScope is already set, we simply append the
298       // extra scope. Suppose the unresolved name is "index" in the following
299       // example:
300       //   namespace clang {  clangd::index::X; }
301       //                      ~~~~~~  ~~~~~
302       // "clangd::" is assumed to be clang:: by Sema, and we would have used
303       // it as extra scope. With "index" being a specifier, we append "index::"
304       // to the extra scope.
305       Result.UnresolvedScope->append((Result.Name + Split.first).str());
306       Result.Name = std::string(Split.second);
307     }
308   }
309   return Result;
310 }
311 
312 /// Returns all namespace scopes that the unqualified lookup would visit.
313 std::vector<std::string>
314 collectAccessibleScopes(Sema &Sem, const DeclarationNameInfo &Typo, Scope *S,
315                         Sema::LookupNameKind LookupKind) {
316   std::vector<std::string> Scopes;
317   VisitedContextCollector Collector;
318   Sem.LookupVisibleDecls(S, LookupKind, Collector,
319                          /*IncludeGlobalScope=*/false,
320                          /*LoadExternal=*/false);
321 
322   Scopes.push_back("");
323   for (const auto *Ctx : Collector.takeVisitedContexts()) {
324     if (isa<NamespaceDecl>(Ctx))
325       Scopes.push_back(printNamespaceScope(*Ctx));
326   }
327   return Scopes;
328 }
329 
330 class IncludeFixer::UnresolvedNameRecorder : public ExternalSemaSource {
331 public:
332   UnresolvedNameRecorder(llvm::Optional<UnresolvedName> &LastUnresolvedName)
333       : LastUnresolvedName(LastUnresolvedName) {}
334 
335   void InitializeSema(Sema &S) override { this->SemaPtr = &S; }
336 
337   // Captures the latest typo and treat it as an unresolved name that can
338   // potentially be fixed by adding #includes.
339   TypoCorrection CorrectTypo(const DeclarationNameInfo &Typo, int LookupKind,
340                              Scope *S, CXXScopeSpec *SS,
341                              CorrectionCandidateCallback &CCC,
342                              DeclContext *MemberContext, bool EnteringContext,
343                              const ObjCObjectPointerType *OPT) override {
344     assert(SemaPtr && "Sema must have been set.");
345     if (SemaPtr->isSFINAEContext())
346       return TypoCorrection();
347     if (!isInsideMainFile(Typo.getLoc(), SemaPtr->SourceMgr))
348       return clang::TypoCorrection();
349 
350     auto Extracted = extractUnresolvedNameCheaply(
351         SemaPtr->SourceMgr, Typo, SS, SemaPtr->LangOpts,
352         static_cast<Sema::LookupNameKind>(LookupKind) ==
353             Sema::LookupNameKind::LookupNestedNameSpecifierName);
354     if (!Extracted)
355       return TypoCorrection();
356 
357     UnresolvedName Unresolved;
358     Unresolved.Name = Extracted->Name;
359     Unresolved.Loc = Typo.getBeginLoc();
360     if (!Extracted->ResolvedScope && !S) // Give up if no scope available.
361       return TypoCorrection();
362 
363     if (Extracted->ResolvedScope)
364       Unresolved.Scopes.push_back(*Extracted->ResolvedScope);
365     else // no qualifier or qualifier is unresolved.
366       Unresolved.Scopes = collectAccessibleScopes(
367           *SemaPtr, Typo, S, static_cast<Sema::LookupNameKind>(LookupKind));
368 
369     if (Extracted->UnresolvedScope) {
370       for (std::string &Scope : Unresolved.Scopes)
371         Scope += *Extracted->UnresolvedScope;
372     }
373 
374     LastUnresolvedName = std::move(Unresolved);
375 
376     // Never return a valid correction to try to recover. Our suggested fixes
377     // always require a rebuild.
378     return TypoCorrection();
379   }
380 
381 private:
382   Sema *SemaPtr = nullptr;
383 
384   llvm::Optional<UnresolvedName> &LastUnresolvedName;
385 };
386 
387 llvm::IntrusiveRefCntPtr<ExternalSemaSource>
388 IncludeFixer::unresolvedNameRecorder() {
389   return new UnresolvedNameRecorder(LastUnresolvedName);
390 }
391 
392 std::vector<Fix> IncludeFixer::fixUnresolvedName() const {
393   assert(LastUnresolvedName.hasValue());
394   auto &Unresolved = *LastUnresolvedName;
395   vlog("Trying to fix unresolved name \"{0}\" in scopes: [{1}]",
396        Unresolved.Name, llvm::join(Unresolved.Scopes, ", "));
397 
398   FuzzyFindRequest Req;
399   Req.AnyScope = false;
400   Req.Query = Unresolved.Name;
401   Req.Scopes = Unresolved.Scopes;
402   Req.RestrictForCodeCompletion = true;
403   Req.Limit = 100;
404 
405   if (llvm::Optional<const SymbolSlab *> Syms = fuzzyFindCached(Req))
406     return fixesForSymbols(**Syms);
407 
408   return {};
409 }
410 
411 llvm::Optional<const SymbolSlab *>
412 IncludeFixer::fuzzyFindCached(const FuzzyFindRequest &Req) const {
413   auto ReqStr = llvm::formatv("{0}", toJSON(Req)).str();
414   auto I = FuzzyFindCache.find(ReqStr);
415   if (I != FuzzyFindCache.end())
416     return &I->second;
417 
418   if (IndexRequestCount >= IndexRequestLimit)
419     return llvm::None;
420   IndexRequestCount++;
421 
422   SymbolSlab::Builder Matches;
423   Index.fuzzyFind(Req, [&](const Symbol &Sym) {
424     if (Sym.Name != Req.Query)
425       return;
426     if (!Sym.IncludeHeaders.empty())
427       Matches.insert(Sym);
428   });
429   auto Syms = std::move(Matches).build();
430   auto E = FuzzyFindCache.try_emplace(ReqStr, std::move(Syms));
431   return &E.first->second;
432 }
433 
434 llvm::Optional<const SymbolSlab *>
435 IncludeFixer::lookupCached(const SymbolID &ID) const {
436   LookupRequest Req;
437   Req.IDs.insert(ID);
438 
439   auto I = LookupCache.find(ID);
440   if (I != LookupCache.end())
441     return &I->second;
442 
443   if (IndexRequestCount >= IndexRequestLimit)
444     return llvm::None;
445   IndexRequestCount++;
446 
447   // FIXME: consider batching the requests for all diagnostics.
448   SymbolSlab::Builder Matches;
449   Index.lookup(Req, [&](const Symbol &Sym) { Matches.insert(Sym); });
450   auto Syms = std::move(Matches).build();
451 
452   std::vector<Fix> Fixes;
453   if (!Syms.empty()) {
454     auto &Matched = *Syms.begin();
455     if (!Matched.IncludeHeaders.empty() && Matched.Definition &&
456         Matched.CanonicalDeclaration.FileURI == Matched.Definition.FileURI)
457       Fixes = fixesForSymbols(Syms);
458   }
459   auto E = LookupCache.try_emplace(ID, std::move(Syms));
460   return &E.first->second;
461 }
462 
463 } // namespace clangd
464 } // namespace clang
465