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