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