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