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