clang-tools-extra/clangd/IncludeFixer.cpp

   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/STLExtras.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 <optional>
  44 #include <set>
  45 #include <string>
  46 #include <vector>
  47
  48 namespace clang {
  49 namespace clangd {
  50 namespace {
  51
  52 std::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 std::nullopt;
  61   }
  62 }
  63
  64 std::vector<Fix> only(std::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("<typeinfo>"));
 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 std::optional<Fix> IncludeFixer::insertHeader(llvm::StringRef Spelled,
 251                                                llvm::StringRef Symbol,
 252                                                tooling::IncludeDirective Directive) const {
 253   Fix F;
 254
 255   if (auto Edit = Inserter->insert(Spelled, Directive))
 256     F.Edits.push_back(std::move(*Edit));
 257   else
 258     return std::nullopt;
 259
 260   llvm::StringRef DirectiveSpelling =
 261       Directive == tooling::IncludeDirective::Include ? "Include" : "Import";
 262   if (Symbol.empty())
 263     F.Message = llvm::formatv("{0} {1}", DirectiveSpelling, Spelled);
 264   else
 265     F.Message = llvm::formatv("{0} {1} for symbol {2}",
 266         DirectiveSpelling, Spelled, Symbol);
 267
 268   return F;
 269 }
 270
 271 std::vector<Fix> IncludeFixer::fixIncompleteType(const Type &T) const {
 272   // Only handle incomplete TagDecl type.
 273   const TagDecl *TD = T.getAsTagDecl();
 274   if (!TD)
 275     return {};
 276   std::string TypeName = printQualifiedName(*TD);
 277   trace::Span Tracer("Fix include for incomplete type");
 278   SPAN_ATTACH(Tracer, "type", TypeName);
 279   vlog("Trying to fix include for incomplete type {0}", TypeName);
 280
 281   auto ID = getSymbolID(TD);
 282   if (!ID)
 283     return {};
 284   std::optional<const SymbolSlab *> Symbols = lookupCached(ID);
 285   if (!Symbols)
 286     return {};
 287   const SymbolSlab &Syms = **Symbols;
 288   std::vector<Fix> Fixes;
 289   if (!Syms.empty()) {
 290     auto &Matched = *Syms.begin();
 291     if (!Matched.IncludeHeaders.empty() && Matched.Definition &&
 292         Matched.CanonicalDeclaration.FileURI == Matched.Definition.FileURI)
 293       Fixes = fixesForSymbols(Syms);
 294   }
 295   return Fixes;
 296 }
 297
 298 std::vector<Fix> IncludeFixer::fixesForSymbols(const SymbolSlab &Syms) const {
 299   auto Inserted = [&](const Symbol &Sym, llvm::StringRef Header)
 300       -> llvm::Expected<std::pair<std::string, bool>> {
 301     auto ResolvedDeclaring =
 302         URI::resolve(Sym.CanonicalDeclaration.FileURI, File);
 303     if (!ResolvedDeclaring)
 304       return ResolvedDeclaring.takeError();
 305     auto ResolvedInserted = toHeaderFile(Header, File);
 306     if (!ResolvedInserted)
 307       return ResolvedInserted.takeError();
 308     auto Spelled = Inserter->calculateIncludePath(*ResolvedInserted, File);
 309     if (!Spelled)
 310       return error("Header not on include path");
 311     return std::make_pair(
 312         std::move(*Spelled),
 313         Inserter->shouldInsertInclude(*ResolvedDeclaring, *ResolvedInserted));
 314   };
 315
 316   std::vector<Fix> Fixes;
 317   // Deduplicate fixes by include headers. This doesn't distinguish symbols in
 318   // different scopes from the same header, but this case should be rare and is
 319   // thus ignored.
 320   llvm::StringSet<> InsertedHeaders;
 321   for (const auto &Sym : Syms) {
 322     for (const auto &Inc : getRankedIncludes(Sym)) {
 323       if ((Inc.Directive & Directive) == 0)
 324         continue;
 325       if (auto ToInclude = Inserted(Sym, Inc.Header)) {
 326         if (ToInclude->second) {
 327           if (!InsertedHeaders.try_emplace(ToInclude->first).second)
 328             continue;
 329           if (auto Fix =
 330                   insertHeader(ToInclude->first, (Sym.Scope + Sym.Name).str(),
 331                                Directive == Symbol::Import
 332                                   ? tooling::IncludeDirective::Import
 333                                   : tooling::IncludeDirective::Include))
 334             Fixes.push_back(std::move(*Fix));
 335         }
 336       } else {
 337         vlog("Failed to calculate include insertion for {0} into {1}: {2}",
 338              Inc.Header, File, ToInclude.takeError());
 339       }
 340     }
 341   }
 342   return Fixes;
 343 }
 344
 345 // Returns the identifiers qualified by an unresolved name. \p Loc is the
 346 // start location of the unresolved name. For the example below, this returns
 347 // "::X::Y" that is qualified by unresolved name "clangd":
 348 //     clang::clangd::X::Y
 349 //            ~
 350 std::optional<std::string> qualifiedByUnresolved(const SourceManager &SM,
 351                                                   SourceLocation Loc,
 352                                                   const LangOptions &LangOpts) {
 353   std::string Result;
 354   // Accept qualifier written within macro arguments, but not macro bodies.
 355   SourceLocation NextLoc = SM.getTopMacroCallerLoc(Loc);
 356   while (auto CCTok = Lexer::findNextToken(NextLoc, SM, LangOpts)) {
 357     if (!CCTok->is(tok::coloncolon))
 358       break;
 359     auto IDTok = Lexer::findNextToken(CCTok->getLocation(), SM, LangOpts);
 360     if (!IDTok || !IDTok->is(tok::raw_identifier))
 361       break;
 362     Result.append(("::" + IDTok->getRawIdentifier()).str());
 363     NextLoc = IDTok->getLocation();
 364   }
 365   if (Result.empty())
 366     return std::nullopt;
 367   return Result;
 368 }
 369
 370 // An unresolved name and its scope information that can be extracted cheaply.
 371 struct CheapUnresolvedName {
 372   std::string Name;
 373   // This is the part of what was typed that was resolved, and it's in its
 374   // resolved form not its typed form (think `namespace clang { clangd::x }` -->
 375   // `clang::clangd::`).
 376   std::optional<std::string> ResolvedScope;
 377
 378   // Unresolved part of the scope. When the unresolved name is a specifier, we
 379   // use the name that comes after it as the alternative name to resolve and use
 380   // the specifier as the extra scope in the accessible scopes.
 381   std::optional<std::string> UnresolvedScope;
 382 };
 383
 384 std::optional<std::string> getSpelledSpecifier(const CXXScopeSpec &SS,
 385     const SourceManager &SM) {
 386   // Support specifiers written within a single macro argument.
 387   if (!SM.isWrittenInSameFile(SS.getBeginLoc(), SS.getEndLoc()))
 388     return std::nullopt;
 389   SourceRange Range(SM.getTopMacroCallerLoc(SS.getBeginLoc()), SM.getTopMacroCallerLoc(SS.getEndLoc()));
 390   if (Range.getBegin().isMacroID() || Range.getEnd().isMacroID())
 391     return std::nullopt;
 392
 393   return (toSourceCode(SM, Range) + "::").str();
 394 }
 395
 396 // Extracts unresolved name and scope information around \p Unresolved.
 397 // FIXME: try to merge this with the scope-wrangling code in CodeComplete.
 398 std::optional<CheapUnresolvedName> extractUnresolvedNameCheaply(
 399     const SourceManager &SM, const DeclarationNameInfo &Unresolved,
 400     CXXScopeSpec *SS, const LangOptions &LangOpts, bool UnresolvedIsSpecifier) {
 401   CheapUnresolvedName Result;
 402   Result.Name = Unresolved.getAsString();
 403   if (SS && SS->isNotEmpty()) { // "::" or "ns::"
 404     if (auto *Nested = SS->getScopeRep()) {
 405       if (Nested->getKind() == NestedNameSpecifier::Global) {
 406         Result.ResolvedScope = "";
 407       } else if (const auto *NS = Nested->getAsNamespace()) {
 408         std::string SpecifiedNS = printNamespaceScope(*NS);
 409         std::optional<std::string> Spelling = getSpelledSpecifier(*SS, SM);
 410
 411         // Check the specifier spelled in the source.
 412         // If the resolved scope doesn't end with the spelled scope, the
 413         // resolved scope may come from a sema typo correction. For example,
 414         // sema assumes that "clangd::" is a typo of "clang::" and uses
 415         // "clang::" as the specified scope in:
 416         //     namespace clang { clangd::X; }
 417         // In this case, we use the "typo" specifier as extra scope instead
 418         // of using the scope assumed by sema.
 419         if (!Spelling || llvm::StringRef(SpecifiedNS).ends_with(*Spelling)) {
 420           Result.ResolvedScope = std::move(SpecifiedNS);
 421         } else {
 422           Result.UnresolvedScope = std::move(*Spelling);
 423         }
 424       } else if (const auto *ANS = Nested->getAsNamespaceAlias()) {
 425         Result.ResolvedScope = printNamespaceScope(*ANS->getNamespace());
 426       } else {
 427         // We don't fix symbols in scopes that are not top-level e.g. class
 428         // members, as we don't collect includes for them.
 429         return std::nullopt;
 430       }
 431     }
 432   }
 433
 434   if (UnresolvedIsSpecifier) {
 435     // If the unresolved name is a specifier e.g.
 436     //      clang::clangd::X
 437     //             ~~~~~~
 438     // We try to resolve clang::clangd::X instead of clang::clangd.
 439     // FIXME: We won't be able to fix include if the specifier is what we
 440     // should resolve (e.g. it's a class scope specifier). Collecting include
 441     // headers for nested types could make this work.
 442
 443     // Not using the end location as it doesn't always point to the end of
 444     // identifier.
 445     if (auto QualifiedByUnresolved =
 446             qualifiedByUnresolved(SM, Unresolved.getBeginLoc(), LangOpts)) {
 447       auto Split = splitQualifiedName(*QualifiedByUnresolved);
 448       if (!Result.UnresolvedScope)
 449         Result.UnresolvedScope.emplace();
 450       // If UnresolvedSpecifiedScope is already set, we simply append the
 451       // extra scope. Suppose the unresolved name is "index" in the following
 452       // example:
 453       //   namespace clang {  clangd::index::X; }
 454       //                      ~~~~~~  ~~~~~
 455       // "clangd::" is assumed to be clang:: by Sema, and we would have used
 456       // it as extra scope. With "index" being a specifier, we append "index::"
 457       // to the extra scope.
 458       Result.UnresolvedScope->append((Result.Name + Split.first).str());
 459       Result.Name = std::string(Split.second);
 460     }
 461   }
 462   return Result;
 463 }
 464
 465 /// Returns all namespace scopes that the unqualified lookup would visit.
 466 std::vector<std::string>
 467 collectAccessibleScopes(Sema &Sem, const DeclarationNameInfo &Typo, Scope *S,
 468                         Sema::LookupNameKind LookupKind) {
 469   // Collects contexts visited during a Sema name lookup.
 470   struct VisitedContextCollector : public VisibleDeclConsumer {
 471     VisitedContextCollector(std::vector<std::string> &Out) : Out(Out) {}
 472     void EnteredContext(DeclContext *Ctx) override {
 473       if (llvm::isa<NamespaceDecl>(Ctx))
 474         Out.push_back(printNamespaceScope(*Ctx));
 475     }
 476     void FoundDecl(NamedDecl *ND, NamedDecl *Hiding, DeclContext *Ctx,
 477                    bool InBaseClass) override {}
 478     std::vector<std::string> &Out;
 479   };
 480
 481   std::vector<std::string> Scopes;
 482   Scopes.push_back("");
 483   VisitedContextCollector Collector(Scopes);
 484   Sem.LookupVisibleDecls(S, LookupKind, Collector,
 485                          /*IncludeGlobalScope=*/false,
 486                          /*LoadExternal=*/false);
 487   llvm::sort(Scopes);
 488   Scopes.erase(std::unique(Scopes.begin(), Scopes.end()), Scopes.end());
 489   return Scopes;
 490 }
 491
 492 class IncludeFixer::UnresolvedNameRecorder : public ExternalSemaSource {
 493 public:
 494   UnresolvedNameRecorder(std::optional<UnresolvedName> &LastUnresolvedName)
 495       : LastUnresolvedName(LastUnresolvedName) {}
 496
 497   void InitializeSema(Sema &S) override { this->SemaPtr = &S; }
 498
 499   // Captures the latest typo and treat it as an unresolved name that can
 500   // potentially be fixed by adding #includes.
 501   TypoCorrection CorrectTypo(const DeclarationNameInfo &Typo, int LookupKind,
 502                              Scope *S, CXXScopeSpec *SS,
 503                              CorrectionCandidateCallback &CCC,
 504                              DeclContext *MemberContext, bool EnteringContext,
 505                              const ObjCObjectPointerType *OPT) override {
 506     dlog("CorrectTypo: {0}", Typo.getAsString());
 507     assert(SemaPtr && "Sema must have been set.");
 508     if (SemaPtr->isSFINAEContext())
 509       return TypoCorrection();
 510     if (!isInsideMainFile(Typo.getLoc(), SemaPtr->SourceMgr))
 511       return clang::TypoCorrection();
 512
 513     auto Extracted = extractUnresolvedNameCheaply(
 514         SemaPtr->SourceMgr, Typo, SS, SemaPtr->LangOpts,
 515         static_cast<Sema::LookupNameKind>(LookupKind) ==
 516             Sema::LookupNameKind::LookupNestedNameSpecifierName);
 517     if (!Extracted)
 518       return TypoCorrection();
 519
 520     UnresolvedName Unresolved;
 521     Unresolved.Name = Extracted->Name;
 522     Unresolved.Loc = Typo.getBeginLoc();
 523     if (!Extracted->ResolvedScope && !S) // Give up if no scope available.
 524       return TypoCorrection();
 525
 526     if (Extracted->ResolvedScope)
 527       Unresolved.Scopes.push_back(*Extracted->ResolvedScope);
 528     else // no qualifier or qualifier is unresolved.
 529       Unresolved.Scopes = collectAccessibleScopes(
 530           *SemaPtr, Typo, S, static_cast<Sema::LookupNameKind>(LookupKind));
 531
 532     if (Extracted->UnresolvedScope) {
 533       for (std::string &Scope : Unresolved.Scopes)
 534         Scope += *Extracted->UnresolvedScope;
 535     }
 536
 537     LastUnresolvedName = std::move(Unresolved);
 538
 539     // Never return a valid correction to try to recover. Our suggested fixes
 540     // always require a rebuild.
 541     return TypoCorrection();
 542   }
 543
 544 private:
 545   Sema *SemaPtr = nullptr;
 546
 547   std::optional<UnresolvedName> &LastUnresolvedName;
 548 };
 549
 550 llvm::IntrusiveRefCntPtr<ExternalSemaSource>
 551 IncludeFixer::unresolvedNameRecorder() {
 552   return new UnresolvedNameRecorder(LastUnresolvedName);
 553 }
 554
 555 std::vector<Fix> IncludeFixer::fixUnresolvedName() const {
 556   assert(LastUnresolvedName);
 557   auto &Unresolved = *LastUnresolvedName;
 558   vlog("Trying to fix unresolved name \"{0}\" in scopes: [{1}]",
 559        Unresolved.Name, llvm::join(Unresolved.Scopes, ", "));
 560
 561   FuzzyFindRequest Req;
 562   Req.AnyScope = false;
 563   Req.Query = Unresolved.Name;
 564   Req.Scopes = Unresolved.Scopes;
 565   Req.RestrictForCodeCompletion = true;
 566   Req.Limit = 100;
 567
 568   if (std::optional<const SymbolSlab *> Syms = fuzzyFindCached(Req))
 569     return fixesForSymbols(**Syms);
 570
 571   return {};
 572 }
 573
 574 std::optional<const SymbolSlab *>
 575 IncludeFixer::fuzzyFindCached(const FuzzyFindRequest &Req) const {
 576   auto ReqStr = llvm::formatv("{0}", toJSON(Req)).str();
 577   auto I = FuzzyFindCache.find(ReqStr);
 578   if (I != FuzzyFindCache.end())
 579     return &I->second;
 580
 581   if (IndexRequestCount >= IndexRequestLimit)
 582     return std::nullopt;
 583   IndexRequestCount++;
 584
 585   SymbolSlab::Builder Matches;
 586   Index.fuzzyFind(Req, [&](const Symbol &Sym) {
 587     if (Sym.Name != Req.Query)
 588       return;
 589     if (!Sym.IncludeHeaders.empty())
 590       Matches.insert(Sym);
 591   });
 592   auto Syms = std::move(Matches).build();
 593   auto E = FuzzyFindCache.try_emplace(ReqStr, std::move(Syms));
 594   return &E.first->second;
 595 }
 596
 597 std::optional<const SymbolSlab *>
 598 IncludeFixer::lookupCached(const SymbolID &ID) const {
 599   LookupRequest Req;
 600   Req.IDs.insert(ID);
 601
 602   auto I = LookupCache.find(ID);
 603   if (I != LookupCache.end())
 604     return &I->second;
 605
 606   if (IndexRequestCount >= IndexRequestLimit)
 607     return std::nullopt;
 608   IndexRequestCount++;
 609
 610   // FIXME: consider batching the requests for all diagnostics.
 611   SymbolSlab::Builder Matches;
 612   Index.lookup(Req, [&](const Symbol &Sym) { Matches.insert(Sym); });
 613   auto Syms = std::move(Matches).build();
 614
 615   std::vector<Fix> Fixes;
 616   if (!Syms.empty()) {
 617     auto &Matched = *Syms.begin();
 618     if (!Matched.IncludeHeaders.empty() && Matched.Definition &&
 619         Matched.CanonicalDeclaration.FileURI == Matched.Definition.FileURI)
 620       Fixes = fixesForSymbols(Syms);
 621   }
 622   auto E = LookupCache.try_emplace(ID, std::move(Syms));
 623   return &E.first->second;
 624 }
 625
 626 } // namespace clangd
 627 } // namespace clang