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