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/DiagnosticParse.h"
24 #include "clang/Basic/DiagnosticSema.h"
25 #include "clang/Basic/LangOptions.h"
26 #include "clang/Basic/SourceLocation.h"
27 #include "clang/Basic/SourceManager.h"
28 #include "clang/Basic/TokenKinds.h"
29 #include "clang/Lex/Lexer.h"
30 #include "clang/Sema/DeclSpec.h"
31 #include "clang/Sema/Lookup.h"
32 #include "clang/Sema/Scope.h"
33 #include "clang/Sema/Sema.h"
34 #include "clang/Sema/TypoCorrection.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 <algorithm>
44 #include <set>
45 #include <string>
46 #include <vector>
47 
48 namespace clang {
49 namespace clangd {
50 namespace {
51 
52 llvm::Optional<llvm::StringRef> getArgStr(const clang::Diagnostic &Info,
53                                           unsigned Index) {
54   switch (Info.getArgKind(Index)) {
55   case DiagnosticsEngine::ak_c_string:
56     return llvm::StringRef(Info.getArgCStr(Index));
57   case DiagnosticsEngine::ak_std_string:
58     return llvm::StringRef(Info.getArgStdStr(Index));
59   default:
60     return llvm::None;
61   }
62 }
63 
64 std::vector<Fix> only(llvm::Optional<Fix> F) {
65   if (F)
66     return {std::move(*F)};
67   return {};
68 }
69 
70 } // namespace
71 
72 std::vector<Fix> IncludeFixer::fix(DiagnosticsEngine::Level DiagLevel,
73                                    const clang::Diagnostic &Info) const {
74   switch (Info.getID()) {
75   /*
76    There are many "incomplete type" diagnostics!
77    They are almost all Sema diagnostics with "incomplete" in the name.
78 
79    sed -n '/CLASS_NOTE/! s/DIAG(\\([^,]*\\).*)/  case diag::\\1:/p' \
80      tools/clang/include/clang/Basic/DiagnosticSemaKinds.inc | grep incomplete
81   */
82   // clang-format off
83   //case diag::err_alignof_member_of_incomplete_type:
84   case diag::err_array_incomplete_or_sizeless_type:
85   case diag::err_array_size_incomplete_type:
86   case diag::err_asm_incomplete_type:
87   case diag::err_assoc_type_incomplete:
88   case diag::err_bad_cast_incomplete:
89   case diag::err_call_function_incomplete_return:
90   case diag::err_call_incomplete_argument:
91   case diag::err_call_incomplete_return:
92   case diag::err_capture_of_incomplete_or_sizeless_type:
93   case diag::err_catch_incomplete:
94   case diag::err_catch_incomplete_ptr:
95   case diag::err_catch_incomplete_ref:
96   case diag::err_cconv_incomplete_param_type:
97   case diag::err_coroutine_promise_type_incomplete:
98   case diag::err_covariant_return_incomplete:
99   //case diag::err_deduced_class_template_incomplete:
100   case diag::err_delete_incomplete_class_type:
101   case diag::err_dereference_incomplete_type:
102   case diag::err_exception_spec_incomplete_type:
103   case diag::err_field_incomplete_or_sizeless:
104   case diag::err_for_range_incomplete_type:
105   case diag::err_func_def_incomplete_result:
106   case diag::err_ice_incomplete_type:
107   case diag::err_illegal_message_expr_incomplete_type:
108   case diag::err_incomplete_base_class:
109   case diag::err_incomplete_enum:
110   case diag::err_incomplete_in_exception_spec:
111   case diag::err_incomplete_member_access:
112   case diag::err_incomplete_nested_name_spec:
113   case diag::err_incomplete_object_call:
114   case diag::err_incomplete_receiver_type:
115   case diag::err_incomplete_synthesized_property:
116   case diag::err_incomplete_type:
117   case diag::err_incomplete_type_objc_at_encode:
118   case diag::err_incomplete_type_used_in_type_trait_expr:
119   case diag::err_incomplete_typeid:
120   case diag::err_init_incomplete_type:
121   case diag::err_invalid_incomplete_type_use:
122   case diag::err_lambda_incomplete_result:
123   //case diag::err_matrix_incomplete_index:
124   //case diag::err_matrix_separate_incomplete_index:
125   case diag::err_memptr_incomplete:
126   case diag::err_new_incomplete_or_sizeless_type:
127   case diag::err_objc_incomplete_boxed_expression_type:
128   case diag::err_objc_index_incomplete_class_type:
129   case diag::err_offsetof_incomplete_type:
130   case diag::err_omp_firstprivate_incomplete_type:
131   case diag::err_omp_incomplete_type:
132   case diag::err_omp_lastprivate_incomplete_type:
133   case diag::err_omp_linear_incomplete_type:
134   case diag::err_omp_private_incomplete_type:
135   case diag::err_omp_reduction_incomplete_type:
136   case diag::err_omp_section_incomplete_type:
137   case diag::err_omp_threadprivate_incomplete_type:
138   case diag::err_second_parameter_to_va_arg_incomplete:
139   case diag::err_sizeof_alignof_incomplete_or_sizeless_type:
140   case diag::err_subscript_incomplete_or_sizeless_type:
141   case diag::err_switch_incomplete_class_type:
142   case diag::err_temp_copy_incomplete:
143   //case diag::err_template_arg_deduced_incomplete_pack:
144   case diag::err_template_nontype_parm_incomplete:
145   //case diag::err_tentative_def_incomplete_type:
146   case diag::err_throw_incomplete:
147   case diag::err_throw_incomplete_ptr:
148   case diag::err_typecheck_arithmetic_incomplete_or_sizeless_type:
149   case diag::err_typecheck_cast_to_incomplete:
150   case diag::err_typecheck_decl_incomplete_type:
151   //case diag::err_typecheck_incomplete_array_needs_initializer:
152   case diag::err_typecheck_incomplete_tag:
153   case diag::err_typecheck_incomplete_type_not_modifiable_lvalue:
154   case diag::err_typecheck_nonviable_condition_incomplete:
155   case diag::err_underlying_type_of_incomplete_enum:
156   case diag::ext_incomplete_in_exception_spec:
157   //case diag::ext_typecheck_compare_complete_incomplete_pointers:
158   case diag::ext_typecheck_decl_incomplete_type:
159   case diag::warn_delete_incomplete:
160   case diag::warn_incomplete_encoded_type:
161   //case diag::warn_printf_incomplete_specifier:
162   case diag::warn_return_value_udt_incomplete:
163   //case diag::warn_scanf_scanlist_incomplete:
164   //case diag::warn_tentative_incomplete_array:
165     //  clang-format on
166     // Incomplete type diagnostics should have a QualType argument for the
167     // incomplete type.
168     for (unsigned Idx = 0; Idx < Info.getNumArgs(); ++Idx) {
169       if (Info.getArgKind(Idx) == DiagnosticsEngine::ak_qualtype) {
170         auto QT = QualType::getFromOpaquePtr((void *)Info.getRawArg(Idx));
171         if (const Type *T = QT.getTypePtrOrNull()) {
172           if (T->isIncompleteType())
173             return fixIncompleteType(*T);
174           // `enum x : int;' is not formally an incomplete type.
175           // We may need a full definition anyway.
176           if (auto * ET = llvm::dyn_cast<EnumType>(T))
177             if (!ET->getDecl()->getDefinition())
178               return fixIncompleteType(*T);
179         }
180       }
181     }
182     break;
183 
184   case diag::err_unknown_typename:
185   case diag::err_unknown_typename_suggest:
186   case diag::err_unknown_type_or_class_name_suggest:
187   case diag::err_expected_class_name:
188   case diag::err_typename_nested_not_found:
189   case diag::err_no_template:
190   case diag::err_no_template_suggest:
191   case diag::err_undeclared_use:
192   case diag::err_undeclared_use_suggest:
193   case diag::err_undeclared_var_use:
194   case diag::err_undeclared_var_use_suggest:
195   case diag::err_no_member: // Could be no member in namespace.
196   case diag::err_no_member_suggest:
197   case diag::err_no_member_template:
198   case diag::err_no_member_template_suggest:
199   case diag::warn_implicit_function_decl:
200   case diag::ext_implicit_function_decl_c99:
201     dlog("Unresolved name at {0}, last typo was {1}",
202          Info.getLocation().printToString(Info.getSourceManager()),
203          LastUnresolvedName
204              ? LastUnresolvedName->Loc.printToString(Info.getSourceManager())
205              : "none");
206     if (LastUnresolvedName) {
207       // Try to fix unresolved name caused by missing declaration.
208       // E.g.
209       //   clang::SourceManager SM;
210       //          ~~~~~~~~~~~~~
211       //          UnresolvedName
212       //   or
213       //   namespace clang {  SourceManager SM; }
214       //                      ~~~~~~~~~~~~~
215       //                      UnresolvedName
216       // We only attempt to recover a diagnostic if it has the same location as
217       // the last seen unresolved name.
218       if (LastUnresolvedName->Loc == Info.getLocation())
219         return fixUnresolvedName();
220     }
221     break;
222 
223   // Cases where clang explicitly knows which header to include.
224   // (There's no fix provided for boring formatting reasons).
225   case diag::err_implied_std_initializer_list_not_found:
226     return only(insertHeader("<initializer_list>"));
227   case diag::err_need_header_before_typeid:
228     return only(insertHeader("<typeid>"));
229   case diag::err_need_header_before_placement_new:
230   case diag::err_implicit_coroutine_std_nothrow_type_not_found:
231     return only(insertHeader("<new>"));
232   case diag::err_omp_implied_type_not_found:
233   case diag::err_omp_interop_type_not_found:
234     return only(insertHeader("<omp.h>"));
235   case diag::err_implied_coroutine_type_not_found:
236     return only(insertHeader("<coroutine>"));
237   case diag::err_implied_comparison_category_type_not_found:
238     return only(insertHeader("<compare>"));
239   case diag::note_include_header_or_declare:
240     if (Info.getNumArgs() > 0)
241       if (auto Header = getArgStr(Info, 0))
242         return only(insertHeader(("<" + *Header + ">").str(),
243                                  getArgStr(Info, 1).value_or("")));
244     break;
245   }
246 
247   return {};
248 }
249 
250 llvm::Optional<Fix> IncludeFixer::insertHeader(llvm::StringRef Spelled,
251                                                llvm::StringRef Symbol) const {
252   Fix F;
253 
254   if (auto Edit = Inserter->insert(Spelled))
255     F.Edits.push_back(std::move(*Edit));
256   else
257     return llvm::None;
258 
259   if (Symbol.empty())
260     F.Message = llvm::formatv("Include {0}", Spelled);
261   else
262     F.Message = llvm::formatv("Include {0} for symbol {1}", Spelled, Symbol);
263 
264   return F;
265 }
266 
267 std::vector<Fix> IncludeFixer::fixIncompleteType(const Type &T) const {
268   // Only handle incomplete TagDecl type.
269   const TagDecl *TD = T.getAsTagDecl();
270   if (!TD)
271     return {};
272   std::string TypeName = printQualifiedName(*TD);
273   trace::Span Tracer("Fix include for incomplete type");
274   SPAN_ATTACH(Tracer, "type", TypeName);
275   vlog("Trying to fix include for incomplete type {0}", TypeName);
276 
277   auto ID = getSymbolID(TD);
278   if (!ID)
279     return {};
280   llvm::Optional<const SymbolSlab *> Symbols = lookupCached(ID);
281   if (!Symbols)
282     return {};
283   const SymbolSlab &Syms = **Symbols;
284   std::vector<Fix> Fixes;
285   if (!Syms.empty()) {
286     auto &Matched = *Syms.begin();
287     if (!Matched.IncludeHeaders.empty() && Matched.Definition &&
288         Matched.CanonicalDeclaration.FileURI == Matched.Definition.FileURI)
289       Fixes = fixesForSymbols(Syms);
290   }
291   return Fixes;
292 }
293 
294 std::vector<Fix> IncludeFixer::fixesForSymbols(const SymbolSlab &Syms) const {
295   auto Inserted = [&](const Symbol &Sym, llvm::StringRef Header)
296       -> llvm::Expected<std::pair<std::string, bool>> {
297     auto ResolvedDeclaring =
298         URI::resolve(Sym.CanonicalDeclaration.FileURI, File);
299     if (!ResolvedDeclaring)
300       return ResolvedDeclaring.takeError();
301     auto ResolvedInserted = toHeaderFile(Header, File);
302     if (!ResolvedInserted)
303       return ResolvedInserted.takeError();
304     auto Spelled = Inserter->calculateIncludePath(*ResolvedInserted, File);
305     if (!Spelled)
306       return error("Header not on include path");
307     return std::make_pair(
308         std::move(*Spelled),
309         Inserter->shouldInsertInclude(*ResolvedDeclaring, *ResolvedInserted));
310   };
311 
312   std::vector<Fix> Fixes;
313   // Deduplicate fixes by include headers. This doesn't distinguish symbols in
314   // different scopes from the same header, but this case should be rare and is
315   // thus ignored.
316   llvm::StringSet<> InsertedHeaders;
317   for (const auto &Sym : Syms) {
318     for (const auto &Inc : getRankedIncludes(Sym)) {
319       if (auto ToInclude = Inserted(Sym, Inc)) {
320         if (ToInclude->second) {
321           if (!InsertedHeaders.try_emplace(ToInclude->first).second)
322             continue;
323           if (auto Fix =
324                   insertHeader(ToInclude->first, (Sym.Scope + Sym.Name).str()))
325             Fixes.push_back(std::move(*Fix));
326         }
327       } else {
328         vlog("Failed to calculate include insertion for {0} into {1}: {2}", Inc,
329              File, ToInclude.takeError());
330       }
331     }
332   }
333   return Fixes;
334 }
335 
336 // Returns the identifiers qualified by an unresolved name. \p Loc is the
337 // start location of the unresolved name. For the example below, this returns
338 // "::X::Y" that is qualified by unresolved name "clangd":
339 //     clang::clangd::X::Y
340 //            ~
341 llvm::Optional<std::string> qualifiedByUnresolved(const SourceManager &SM,
342                                                   SourceLocation Loc,
343                                                   const LangOptions &LangOpts) {
344   std::string Result;
345   // Accept qualifier written within macro arguments, but not macro bodies.
346   SourceLocation NextLoc = SM.getTopMacroCallerLoc(Loc);
347   while (auto CCTok = Lexer::findNextToken(NextLoc, SM, LangOpts)) {
348     if (!CCTok->is(tok::coloncolon))
349       break;
350     auto IDTok = Lexer::findNextToken(CCTok->getLocation(), SM, LangOpts);
351     if (!IDTok || !IDTok->is(tok::raw_identifier))
352       break;
353     Result.append(("::" + IDTok->getRawIdentifier()).str());
354     NextLoc = IDTok->getLocation();
355   }
356   if (Result.empty())
357     return llvm::None;
358   return Result;
359 }
360 
361 // An unresolved name and its scope information that can be extracted cheaply.
362 struct CheapUnresolvedName {
363   std::string Name;
364   // This is the part of what was typed that was resolved, and it's in its
365   // resolved form not its typed form (think `namespace clang { clangd::x }` -->
366   // `clang::clangd::`).
367   llvm::Optional<std::string> ResolvedScope;
368 
369   // Unresolved part of the scope. When the unresolved name is a specifier, we
370   // use the name that comes after it as the alternative name to resolve and use
371   // the specifier as the extra scope in the accessible scopes.
372   llvm::Optional<std::string> UnresolvedScope;
373 };
374 
375 llvm::Optional<std::string> getSpelledSpecifier(const CXXScopeSpec &SS,
376     const SourceManager &SM) {
377   // Support specifiers written within a single macro argument.
378   if (!SM.isWrittenInSameFile(SS.getBeginLoc(), SS.getEndLoc()))
379     return llvm::None;
380   SourceRange Range(SM.getTopMacroCallerLoc(SS.getBeginLoc()), SM.getTopMacroCallerLoc(SS.getEndLoc()));
381   if (Range.getBegin().isMacroID() || Range.getEnd().isMacroID())
382     return llvm::None;
383 
384   return (toSourceCode(SM, Range) + "::").str();
385 }
386 
387 // Extracts unresolved name and scope information around \p Unresolved.
388 // FIXME: try to merge this with the scope-wrangling code in CodeComplete.
389 llvm::Optional<CheapUnresolvedName> extractUnresolvedNameCheaply(
390     const SourceManager &SM, const DeclarationNameInfo &Unresolved,
391     CXXScopeSpec *SS, const LangOptions &LangOpts, bool UnresolvedIsSpecifier) {
392   CheapUnresolvedName Result;
393   Result.Name = Unresolved.getAsString();
394   if (SS && SS->isNotEmpty()) { // "::" or "ns::"
395     if (auto *Nested = SS->getScopeRep()) {
396       if (Nested->getKind() == NestedNameSpecifier::Global) {
397         Result.ResolvedScope = "";
398       } else if (const auto *NS = Nested->getAsNamespace()) {
399         std::string SpecifiedNS = printNamespaceScope(*NS);
400         llvm::Optional<std::string> Spelling = getSpelledSpecifier(*SS, SM);
401 
402         // Check the specifier spelled in the source.
403         // If the resolved scope doesn't end with the spelled scope, the
404         // resolved scope may come from a sema typo correction. For example,
405         // sema assumes that "clangd::" is a typo of "clang::" and uses
406         // "clang::" as the specified scope in:
407         //     namespace clang { clangd::X; }
408         // In this case, we use the "typo" specifier as extra scope instead
409         // of using the scope assumed by sema.
410         if (!Spelling || llvm::StringRef(SpecifiedNS).endswith(*Spelling)) {
411           Result.ResolvedScope = std::move(SpecifiedNS);
412         } else {
413           Result.UnresolvedScope = std::move(*Spelling);
414         }
415       } else if (const auto *ANS = Nested->getAsNamespaceAlias()) {
416         Result.ResolvedScope = printNamespaceScope(*ANS->getNamespace());
417       } else {
418         // We don't fix symbols in scopes that are not top-level e.g. class
419         // members, as we don't collect includes for them.
420         return llvm::None;
421       }
422     }
423   }
424 
425   if (UnresolvedIsSpecifier) {
426     // If the unresolved name is a specifier e.g.
427     //      clang::clangd::X
428     //             ~~~~~~
429     // We try to resolve clang::clangd::X instead of clang::clangd.
430     // FIXME: We won't be able to fix include if the specifier is what we
431     // should resolve (e.g. it's a class scope specifier). Collecting include
432     // headers for nested types could make this work.
433 
434     // Not using the end location as it doesn't always point to the end of
435     // identifier.
436     if (auto QualifiedByUnresolved =
437             qualifiedByUnresolved(SM, Unresolved.getBeginLoc(), LangOpts)) {
438       auto Split = splitQualifiedName(*QualifiedByUnresolved);
439       if (!Result.UnresolvedScope)
440         Result.UnresolvedScope.emplace();
441       // If UnresolvedSpecifiedScope is already set, we simply append the
442       // extra scope. Suppose the unresolved name is "index" in the following
443       // example:
444       //   namespace clang {  clangd::index::X; }
445       //                      ~~~~~~  ~~~~~
446       // "clangd::" is assumed to be clang:: by Sema, and we would have used
447       // it as extra scope. With "index" being a specifier, we append "index::"
448       // to the extra scope.
449       Result.UnresolvedScope->append((Result.Name + Split.first).str());
450       Result.Name = std::string(Split.second);
451     }
452   }
453   return Result;
454 }
455 
456 /// Returns all namespace scopes that the unqualified lookup would visit.
457 std::vector<std::string>
458 collectAccessibleScopes(Sema &Sem, const DeclarationNameInfo &Typo, Scope *S,
459                         Sema::LookupNameKind LookupKind) {
460   // Collects contexts visited during a Sema name lookup.
461   struct VisitedContextCollector : public VisibleDeclConsumer {
462     VisitedContextCollector(std::vector<std::string> &Out) : Out(Out) {}
463     void EnteredContext(DeclContext *Ctx) override {
464       if (llvm::isa<NamespaceDecl>(Ctx))
465         Out.push_back(printNamespaceScope(*Ctx));
466     }
467     void FoundDecl(NamedDecl *ND, NamedDecl *Hiding, DeclContext *Ctx,
468                    bool InBaseClass) override {}
469     std::vector<std::string> &Out;
470   };
471 
472   std::vector<std::string> Scopes;
473   Scopes.push_back("");
474   VisitedContextCollector Collector(Scopes);
475   Sem.LookupVisibleDecls(S, LookupKind, Collector,
476                          /*IncludeGlobalScope=*/false,
477                          /*LoadExternal=*/false);
478   std::sort(Scopes.begin(), Scopes.end());
479   Scopes.erase(std::unique(Scopes.begin(), Scopes.end()), Scopes.end());
480   return Scopes;
481 }
482 
483 class IncludeFixer::UnresolvedNameRecorder : public ExternalSemaSource {
484 public:
485   UnresolvedNameRecorder(llvm::Optional<UnresolvedName> &LastUnresolvedName)
486       : LastUnresolvedName(LastUnresolvedName) {}
487 
488   void InitializeSema(Sema &S) override { this->SemaPtr = &S; }
489 
490   // Captures the latest typo and treat it as an unresolved name that can
491   // potentially be fixed by adding #includes.
492   TypoCorrection CorrectTypo(const DeclarationNameInfo &Typo, int LookupKind,
493                              Scope *S, CXXScopeSpec *SS,
494                              CorrectionCandidateCallback &CCC,
495                              DeclContext *MemberContext, bool EnteringContext,
496                              const ObjCObjectPointerType *OPT) override {
497     dlog("CorrectTypo: {0}", Typo.getAsString());
498     assert(SemaPtr && "Sema must have been set.");
499     if (SemaPtr->isSFINAEContext())
500       return TypoCorrection();
501     if (!isInsideMainFile(Typo.getLoc(), SemaPtr->SourceMgr))
502       return clang::TypoCorrection();
503 
504     auto Extracted = extractUnresolvedNameCheaply(
505         SemaPtr->SourceMgr, Typo, SS, SemaPtr->LangOpts,
506         static_cast<Sema::LookupNameKind>(LookupKind) ==
507             Sema::LookupNameKind::LookupNestedNameSpecifierName);
508     if (!Extracted)
509       return TypoCorrection();
510 
511     UnresolvedName Unresolved;
512     Unresolved.Name = Extracted->Name;
513     Unresolved.Loc = Typo.getBeginLoc();
514     if (!Extracted->ResolvedScope && !S) // Give up if no scope available.
515       return TypoCorrection();
516 
517     if (Extracted->ResolvedScope)
518       Unresolved.Scopes.push_back(*Extracted->ResolvedScope);
519     else // no qualifier or qualifier is unresolved.
520       Unresolved.Scopes = collectAccessibleScopes(
521           *SemaPtr, Typo, S, static_cast<Sema::LookupNameKind>(LookupKind));
522 
523     if (Extracted->UnresolvedScope) {
524       for (std::string &Scope : Unresolved.Scopes)
525         Scope += *Extracted->UnresolvedScope;
526     }
527 
528     LastUnresolvedName = std::move(Unresolved);
529 
530     // Never return a valid correction to try to recover. Our suggested fixes
531     // always require a rebuild.
532     return TypoCorrection();
533   }
534 
535 private:
536   Sema *SemaPtr = nullptr;
537 
538   llvm::Optional<UnresolvedName> &LastUnresolvedName;
539 };
540 
541 llvm::IntrusiveRefCntPtr<ExternalSemaSource>
542 IncludeFixer::unresolvedNameRecorder() {
543   return new UnresolvedNameRecorder(LastUnresolvedName);
544 }
545 
546 std::vector<Fix> IncludeFixer::fixUnresolvedName() const {
547   assert(LastUnresolvedName);
548   auto &Unresolved = *LastUnresolvedName;
549   vlog("Trying to fix unresolved name \"{0}\" in scopes: [{1}]",
550        Unresolved.Name, llvm::join(Unresolved.Scopes, ", "));
551 
552   FuzzyFindRequest Req;
553   Req.AnyScope = false;
554   Req.Query = Unresolved.Name;
555   Req.Scopes = Unresolved.Scopes;
556   Req.RestrictForCodeCompletion = true;
557   Req.Limit = 100;
558 
559   if (llvm::Optional<const SymbolSlab *> Syms = fuzzyFindCached(Req))
560     return fixesForSymbols(**Syms);
561 
562   return {};
563 }
564 
565 llvm::Optional<const SymbolSlab *>
566 IncludeFixer::fuzzyFindCached(const FuzzyFindRequest &Req) const {
567   auto ReqStr = llvm::formatv("{0}", toJSON(Req)).str();
568   auto I = FuzzyFindCache.find(ReqStr);
569   if (I != FuzzyFindCache.end())
570     return &I->second;
571 
572   if (IndexRequestCount >= IndexRequestLimit)
573     return llvm::None;
574   IndexRequestCount++;
575 
576   SymbolSlab::Builder Matches;
577   Index.fuzzyFind(Req, [&](const Symbol &Sym) {
578     if (Sym.Name != Req.Query)
579       return;
580     if (!Sym.IncludeHeaders.empty())
581       Matches.insert(Sym);
582   });
583   auto Syms = std::move(Matches).build();
584   auto E = FuzzyFindCache.try_emplace(ReqStr, std::move(Syms));
585   return &E.first->second;
586 }
587 
588 llvm::Optional<const SymbolSlab *>
589 IncludeFixer::lookupCached(const SymbolID &ID) const {
590   LookupRequest Req;
591   Req.IDs.insert(ID);
592 
593   auto I = LookupCache.find(ID);
594   if (I != LookupCache.end())
595     return &I->second;
596 
597   if (IndexRequestCount >= IndexRequestLimit)
598     return llvm::None;
599   IndexRequestCount++;
600 
601   // FIXME: consider batching the requests for all diagnostics.
602   SymbolSlab::Builder Matches;
603   Index.lookup(Req, [&](const Symbol &Sym) { Matches.insert(Sym); });
604   auto Syms = std::move(Matches).build();
605 
606   std::vector<Fix> Fixes;
607   if (!Syms.empty()) {
608     auto &Matched = *Syms.begin();
609     if (!Matched.IncludeHeaders.empty() && Matched.Definition &&
610         Matched.CanonicalDeclaration.FileURI == Matched.Definition.FileURI)
611       Fixes = fixesForSymbols(Syms);
612   }
613   auto E = LookupCache.try_emplace(ID, std::move(Syms));
614   return &E.first->second;
615 }
616 
617 } // namespace clangd
618 } // namespace clang
619