1 //===--- FindTarget.cpp - What does an AST node refer to? -----------------===// 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 "FindTarget.h" 10 #include "AST.h" 11 #include "support/Logger.h" 12 #include "clang/AST/ASTTypeTraits.h" 13 #include "clang/AST/Decl.h" 14 #include "clang/AST/DeclCXX.h" 15 #include "clang/AST/DeclTemplate.h" 16 #include "clang/AST/DeclVisitor.h" 17 #include "clang/AST/DeclarationName.h" 18 #include "clang/AST/Expr.h" 19 #include "clang/AST/ExprCXX.h" 20 #include "clang/AST/ExprConcepts.h" 21 #include "clang/AST/ExprObjC.h" 22 #include "clang/AST/NestedNameSpecifier.h" 23 #include "clang/AST/PrettyPrinter.h" 24 #include "clang/AST/RecursiveASTVisitor.h" 25 #include "clang/AST/StmtVisitor.h" 26 #include "clang/AST/TemplateBase.h" 27 #include "clang/AST/Type.h" 28 #include "clang/AST/TypeLoc.h" 29 #include "clang/AST/TypeLocVisitor.h" 30 #include "clang/AST/TypeVisitor.h" 31 #include "clang/Basic/LangOptions.h" 32 #include "clang/Basic/OperatorKinds.h" 33 #include "clang/Basic/SourceLocation.h" 34 #include "clang/Basic/Specifiers.h" 35 #include "llvm/ADT/STLExtras.h" 36 #include "llvm/ADT/SmallVector.h" 37 #include "llvm/Support/Casting.h" 38 #include "llvm/Support/Compiler.h" 39 #include "llvm/Support/raw_ostream.h" 40 #include <iterator> 41 #include <utility> 42 #include <vector> 43 44 namespace clang { 45 namespace clangd { 46 namespace { 47 using ast_type_traits::DynTypedNode; 48 49 LLVM_ATTRIBUTE_UNUSED std::string 50 nodeToString(const ast_type_traits::DynTypedNode &N) { 51 std::string S = std::string(N.getNodeKind().asStringRef()); 52 { 53 llvm::raw_string_ostream OS(S); 54 OS << ": "; 55 N.print(OS, PrintingPolicy(LangOptions())); 56 } 57 std::replace(S.begin(), S.end(), '\n', ' '); 58 return S; 59 } 60 61 // Helper function for getMembersReferencedViaDependentName() 62 // which takes a dependent type `T` and heuristically 63 // resolves it to a CXXRecordDecl in which we can try name lookup. 64 CXXRecordDecl *resolveTypeToRecordDecl(const Type *T) { 65 assert(T); 66 if (const auto *ICNT = T->getAs<InjectedClassNameType>()) { 67 T = ICNT->getInjectedSpecializationType().getTypePtrOrNull(); 68 } 69 const auto *TST = T->getAs<TemplateSpecializationType>(); 70 if (!TST) 71 return nullptr; 72 const ClassTemplateDecl *TD = dyn_cast_or_null<ClassTemplateDecl>( 73 TST->getTemplateName().getAsTemplateDecl()); 74 if (!TD) 75 return nullptr; 76 return TD->getTemplatedDecl(); 77 } 78 79 // Given a dependent type and a member name, heuristically resolve the 80 // name to one or more declarations. 81 // The current heuristic is simply to look up the name in the primary 82 // template. This is a heuristic because the template could potentially 83 // have specializations that declare different members. 84 // Multiple declarations could be returned if the name is overloaded 85 // (e.g. an overloaded method in the primary template). 86 // This heuristic will give the desired answer in many cases, e.g. 87 // for a call to vector<T>::size(). 88 // The name to look up is provided in the form of a factory that takes 89 // an ASTContext, because an ASTContext may be needed to obtain the 90 // name (e.g. if it's an operator name), but the caller may not have 91 // access to an ASTContext. 92 std::vector<const NamedDecl *> getMembersReferencedViaDependentName( 93 const Type *T, 94 llvm::function_ref<DeclarationName(ASTContext &)> NameFactory, 95 bool IsNonstaticMember) { 96 if (!T) 97 return {}; 98 if (auto *ET = T->getAs<EnumType>()) { 99 auto Result = 100 ET->getDecl()->lookup(NameFactory(ET->getDecl()->getASTContext())); 101 return {Result.begin(), Result.end()}; 102 } 103 if (auto *RD = resolveTypeToRecordDecl(T)) { 104 if (!RD->hasDefinition()) 105 return {}; 106 RD = RD->getDefinition(); 107 DeclarationName Name = NameFactory(RD->getASTContext()); 108 return RD->lookupDependentName(Name, [=](const NamedDecl *D) { 109 return IsNonstaticMember ? D->isCXXInstanceMember() 110 : !D->isCXXInstanceMember(); 111 }); 112 } 113 return {}; 114 } 115 116 // Given the type T of a dependent expression that appears of the LHS of a "->", 117 // heuristically find a corresponding pointee type in whose scope we could look 118 // up the name appearing on the RHS. 119 const Type *getPointeeType(const Type *T) { 120 if (!T) 121 return nullptr; 122 123 if (T->isPointerType()) { 124 return T->getAs<PointerType>()->getPointeeType().getTypePtrOrNull(); 125 } 126 127 // Try to handle smart pointer types. 128 129 // Look up operator-> in the primary template. If we find one, it's probably a 130 // smart pointer type. 131 auto ArrowOps = getMembersReferencedViaDependentName( 132 T, 133 [](ASTContext &Ctx) { 134 return Ctx.DeclarationNames.getCXXOperatorName(OO_Arrow); 135 }, 136 /*IsNonStaticMember=*/true); 137 if (ArrowOps.empty()) 138 return nullptr; 139 140 // Getting the return type of the found operator-> method decl isn't useful, 141 // because we discarded template arguments to perform lookup in the primary 142 // template scope, so the return type would just have the form U* where U is a 143 // template parameter type. 144 // Instead, just handle the common case where the smart pointer type has the 145 // form of SmartPtr<X, ...>, and assume X is the pointee type. 146 auto *TST = T->getAs<TemplateSpecializationType>(); 147 if (!TST) 148 return nullptr; 149 if (TST->getNumArgs() == 0) 150 return nullptr; 151 const TemplateArgument &FirstArg = TST->getArg(0); 152 if (FirstArg.getKind() != TemplateArgument::Type) 153 return nullptr; 154 return FirstArg.getAsType().getTypePtrOrNull(); 155 } 156 157 // Try to heuristically resolve a dependent expression `E` to one 158 // or more declarations that it likely references. 159 std::vector<const NamedDecl *> resolveDependentExprToDecls(const Expr *E) { 160 assert(E->isTypeDependent()); 161 if (const auto *ME = dyn_cast<CXXDependentScopeMemberExpr>(E)) { 162 const Type *BaseType = ME->getBaseType().getTypePtrOrNull(); 163 if (ME->isArrow()) { 164 BaseType = getPointeeType(BaseType); 165 } 166 return getMembersReferencedViaDependentName( 167 BaseType, [ME](ASTContext &) { return ME->getMember(); }, 168 /*IsNonstaticMember=*/true); 169 } 170 if (const auto *RE = dyn_cast<DependentScopeDeclRefExpr>(E)) { 171 return getMembersReferencedViaDependentName( 172 RE->getQualifier()->getAsType(), 173 [RE](ASTContext &) { return RE->getDeclName(); }, 174 /*IsNonstaticMember=*/false); 175 } 176 return {}; 177 } 178 179 const NamedDecl *getTemplatePattern(const NamedDecl *D) { 180 if (const CXXRecordDecl *CRD = dyn_cast<CXXRecordDecl>(D)) { 181 if (const auto *Result = CRD->getTemplateInstantiationPattern()) 182 return Result; 183 // getTemplateInstantiationPattern returns null if the Specialization is 184 // incomplete (e.g. the type didn't need to be complete), fall back to the 185 // primary template. 186 if (CRD->getTemplateSpecializationKind() == TSK_Undeclared) 187 if (const auto *Spec = dyn_cast<ClassTemplateSpecializationDecl>(CRD)) 188 return Spec->getSpecializedTemplate()->getTemplatedDecl(); 189 } else if (const FunctionDecl *FD = dyn_cast<FunctionDecl>(D)) { 190 return FD->getTemplateInstantiationPattern(); 191 } else if (auto *VD = dyn_cast<VarDecl>(D)) { 192 // Hmm: getTIP returns its arg if it's not an instantiation?! 193 VarDecl *T = VD->getTemplateInstantiationPattern(); 194 return (T == D) ? nullptr : T; 195 } else if (const auto *ED = dyn_cast<EnumDecl>(D)) { 196 return ED->getInstantiatedFromMemberEnum(); 197 } else if (isa<FieldDecl>(D) || isa<TypedefNameDecl>(D)) { 198 if (const auto *Parent = llvm::dyn_cast<NamedDecl>(D->getDeclContext())) 199 if (const DeclContext *ParentPat = 200 dyn_cast_or_null<DeclContext>(getTemplatePattern(Parent))) 201 for (const NamedDecl *BaseND : ParentPat->lookup(D->getDeclName())) 202 if (!BaseND->isImplicit() && BaseND->getKind() == D->getKind()) 203 return BaseND; 204 } else if (const auto *ECD = dyn_cast<EnumConstantDecl>(D)) { 205 if (const auto *ED = dyn_cast<EnumDecl>(ECD->getDeclContext())) { 206 if (const EnumDecl *Pattern = ED->getInstantiatedFromMemberEnum()) { 207 for (const NamedDecl *BaseECD : Pattern->lookup(ECD->getDeclName())) 208 return BaseECD; 209 } 210 } 211 } 212 return nullptr; 213 } 214 215 // TargetFinder locates the entities that an AST node refers to. 216 // 217 // Typically this is (possibly) one declaration and (possibly) one type, but 218 // may be more: 219 // - for ambiguous nodes like OverloadExpr 220 // - if we want to include e.g. both typedefs and the underlying type 221 // 222 // This is organized as a set of mutually recursive helpers for particular node 223 // types, but for most nodes this is a short walk rather than a deep traversal. 224 // 225 // It's tempting to do e.g. typedef resolution as a second normalization step, 226 // after finding the 'primary' decl etc. But we do this monolithically instead 227 // because: 228 // - normalization may require these traversals again (e.g. unwrapping a 229 // typedef reveals a decltype which must be traversed) 230 // - it doesn't simplify that much, e.g. the first stage must still be able 231 // to yield multiple decls to handle OverloadExpr 232 // - there are cases where it's required for correctness. e.g: 233 // template<class X> using pvec = vector<x*>; pvec<int> x; 234 // There's no Decl `pvec<int>`, we must choose `pvec<X>` or `vector<int*>` 235 // and both are lossy. We must know upfront what the caller ultimately wants. 236 // 237 // FIXME: improve common dependent scope using name lookup in primary templates. 238 // e.g. template<typename T> int foo() { return std::vector<T>().size(); } 239 // formally size() is unresolved, but the primary template is a good guess. 240 // This affects: 241 // - DependentTemplateSpecializationType, 242 // - DependentNameType 243 // - UnresolvedUsingValueDecl 244 // - UnresolvedUsingTypenameDecl 245 struct TargetFinder { 246 using RelSet = DeclRelationSet; 247 using Rel = DeclRelation; 248 249 private: 250 llvm::SmallDenseMap<const NamedDecl *, 251 std::pair<RelSet, /*InsertionOrder*/ size_t>> 252 Decls; 253 RelSet Flags; 254 255 template <typename T> void debug(T &Node, RelSet Flags) { 256 dlog("visit [{0}] {1}", Flags, 257 nodeToString(ast_type_traits::DynTypedNode::create(Node))); 258 } 259 260 void report(const NamedDecl *D, RelSet Flags) { 261 dlog("--> [{0}] {1}", Flags, 262 nodeToString(ast_type_traits::DynTypedNode::create(*D))); 263 auto It = Decls.try_emplace(D, std::make_pair(Flags, Decls.size())); 264 // If already exists, update the flags. 265 if (!It.second) 266 It.first->second.first |= Flags; 267 } 268 269 public: 270 llvm::SmallVector<std::pair<const NamedDecl *, RelSet>, 1> takeDecls() const { 271 using ValTy = std::pair<const NamedDecl *, RelSet>; 272 llvm::SmallVector<ValTy, 1> Result; 273 Result.resize(Decls.size()); 274 for (const auto &Elem : Decls) 275 Result[Elem.second.second] = {Elem.first, Elem.second.first}; 276 return Result; 277 } 278 279 void add(const Decl *Dcl, RelSet Flags) { 280 const NamedDecl *D = llvm::dyn_cast_or_null<NamedDecl>(Dcl); 281 if (!D) 282 return; 283 debug(*D, Flags); 284 if (const UsingDirectiveDecl *UDD = llvm::dyn_cast<UsingDirectiveDecl>(D)) 285 D = UDD->getNominatedNamespaceAsWritten(); 286 287 if (const TypedefNameDecl *TND = dyn_cast<TypedefNameDecl>(D)) { 288 add(TND->getUnderlyingType(), Flags | Rel::Underlying); 289 Flags |= Rel::Alias; // continue with the alias. 290 } else if (const UsingDecl *UD = dyn_cast<UsingDecl>(D)) { 291 for (const UsingShadowDecl *S : UD->shadows()) 292 add(S->getUnderlyingDecl(), Flags | Rel::Underlying); 293 Flags |= Rel::Alias; // continue with the alias. 294 } else if (const auto *NAD = dyn_cast<NamespaceAliasDecl>(D)) { 295 add(NAD->getUnderlyingDecl(), Flags | Rel::Underlying); 296 Flags |= Rel::Alias; // continue with the alias 297 } else if (const UsingShadowDecl *USD = dyn_cast<UsingShadowDecl>(D)) { 298 // Include the using decl, but don't traverse it. This may end up 299 // including *all* shadows, which we don't want. 300 report(USD->getUsingDecl(), Flags | Rel::Alias); 301 // Shadow decls are synthetic and not themselves interesting. 302 // Record the underlying decl instead, if allowed. 303 D = USD->getTargetDecl(); 304 Flags |= Rel::Underlying; // continue with the underlying decl. 305 } 306 307 if (const Decl *Pat = getTemplatePattern(D)) { 308 assert(Pat != D); 309 add(Pat, Flags | Rel::TemplatePattern); 310 // Now continue with the instantiation. 311 Flags |= Rel::TemplateInstantiation; 312 } 313 314 report(D, Flags); 315 } 316 317 void add(const Stmt *S, RelSet Flags) { 318 if (!S) 319 return; 320 debug(*S, Flags); 321 struct Visitor : public ConstStmtVisitor<Visitor> { 322 TargetFinder &Outer; 323 RelSet Flags; 324 Visitor(TargetFinder &Outer, RelSet Flags) : Outer(Outer), Flags(Flags) {} 325 326 void VisitCallExpr(const CallExpr *CE) { 327 Outer.add(CE->getCalleeDecl(), Flags); 328 } 329 void VisitConceptSpecializationExpr(const ConceptSpecializationExpr *E) { 330 Outer.add(E->getNamedConcept(), Flags); 331 } 332 void VisitDeclRefExpr(const DeclRefExpr *DRE) { 333 const Decl *D = DRE->getDecl(); 334 // UsingShadowDecl allows us to record the UsingDecl. 335 // getFoundDecl() returns the wrong thing in other cases (templates). 336 if (auto *USD = llvm::dyn_cast<UsingShadowDecl>(DRE->getFoundDecl())) 337 D = USD; 338 Outer.add(D, Flags); 339 } 340 void VisitMemberExpr(const MemberExpr *ME) { 341 const Decl *D = ME->getMemberDecl(); 342 if (auto *USD = 343 llvm::dyn_cast<UsingShadowDecl>(ME->getFoundDecl().getDecl())) 344 D = USD; 345 Outer.add(D, Flags); 346 } 347 void VisitOverloadExpr(const OverloadExpr *OE) { 348 for (auto *D : OE->decls()) 349 Outer.add(D, Flags); 350 } 351 void VisitSizeOfPackExpr(const SizeOfPackExpr *SE) { 352 Outer.add(SE->getPack(), Flags); 353 } 354 void VisitCXXConstructExpr(const CXXConstructExpr *CCE) { 355 Outer.add(CCE->getConstructor(), Flags); 356 } 357 void VisitDesignatedInitExpr(const DesignatedInitExpr *DIE) { 358 for (const DesignatedInitExpr::Designator &D : 359 llvm::reverse(DIE->designators())) 360 if (D.isFieldDesignator()) { 361 Outer.add(D.getField(), Flags); 362 // We don't know which designator was intended, we assume the outer. 363 break; 364 } 365 } 366 void VisitGotoStmt(const GotoStmt *Goto) { 367 if (auto *LabelDecl = Goto->getLabel()) 368 Outer.add(LabelDecl, Flags); 369 } 370 void VisitLabelStmt(const LabelStmt *Label) { 371 if (auto *LabelDecl = Label->getDecl()) 372 Outer.add(LabelDecl, Flags); 373 } 374 void 375 VisitCXXDependentScopeMemberExpr(const CXXDependentScopeMemberExpr *E) { 376 for (const NamedDecl *D : resolveDependentExprToDecls(E)) { 377 Outer.add(D, Flags); 378 } 379 } 380 void VisitDependentScopeDeclRefExpr(const DependentScopeDeclRefExpr *E) { 381 for (const NamedDecl *D : resolveDependentExprToDecls(E)) { 382 Outer.add(D, Flags); 383 } 384 } 385 void VisitObjCIvarRefExpr(const ObjCIvarRefExpr *OIRE) { 386 Outer.add(OIRE->getDecl(), Flags); 387 } 388 void VisitObjCMessageExpr(const ObjCMessageExpr *OME) { 389 Outer.add(OME->getMethodDecl(), Flags); 390 } 391 void VisitObjCPropertyRefExpr(const ObjCPropertyRefExpr *OPRE) { 392 if (OPRE->isExplicitProperty()) 393 Outer.add(OPRE->getExplicitProperty(), Flags); 394 else { 395 if (OPRE->isMessagingGetter()) 396 Outer.add(OPRE->getImplicitPropertyGetter(), Flags); 397 if (OPRE->isMessagingSetter()) 398 Outer.add(OPRE->getImplicitPropertySetter(), Flags); 399 } 400 } 401 void VisitObjCProtocolExpr(const ObjCProtocolExpr *OPE) { 402 Outer.add(OPE->getProtocol(), Flags); 403 } 404 void VisitOpaqueValueExpr(const OpaqueValueExpr *OVE) { 405 Outer.add(OVE->getSourceExpr(), Flags); 406 } 407 void VisitPseudoObjectExpr(const PseudoObjectExpr *POE) { 408 Outer.add(POE->getSyntacticForm(), Flags); 409 } 410 }; 411 Visitor(*this, Flags).Visit(S); 412 } 413 414 void add(QualType T, RelSet Flags) { 415 if (T.isNull()) 416 return; 417 debug(T, Flags); 418 struct Visitor : public TypeVisitor<Visitor> { 419 TargetFinder &Outer; 420 RelSet Flags; 421 Visitor(TargetFinder &Outer, RelSet Flags) : Outer(Outer), Flags(Flags) {} 422 423 void VisitTagType(const TagType *TT) { 424 Outer.add(TT->getAsTagDecl(), Flags); 425 } 426 427 void VisitElaboratedType(const ElaboratedType *ET) { 428 Outer.add(ET->desugar(), Flags); 429 } 430 431 void VisitInjectedClassNameType(const InjectedClassNameType *ICNT) { 432 Outer.add(ICNT->getDecl(), Flags); 433 } 434 435 void VisitDecltypeType(const DecltypeType *DTT) { 436 Outer.add(DTT->getUnderlyingType(), Flags | Rel::Underlying); 437 } 438 void VisitDeducedType(const DeducedType *DT) { 439 // FIXME: In practice this doesn't work: the AutoType you find inside 440 // TypeLoc never has a deduced type. https://llvm.org/PR42914 441 Outer.add(DT->getDeducedType(), Flags | Rel::Underlying); 442 } 443 void VisitDeducedTemplateSpecializationType( 444 const DeducedTemplateSpecializationType *DTST) { 445 // FIXME: This is a workaround for https://llvm.org/PR42914, 446 // which is causing DTST->getDeducedType() to be empty. We 447 // fall back to the template pattern and miss the instantiation 448 // even when it's known in principle. Once that bug is fixed, 449 // this method can be removed (the existing handling in 450 // VisitDeducedType() is sufficient). 451 if (auto *TD = DTST->getTemplateName().getAsTemplateDecl()) 452 Outer.add(TD->getTemplatedDecl(), Flags | Rel::TemplatePattern); 453 } 454 void VisitTypedefType(const TypedefType *TT) { 455 Outer.add(TT->getDecl(), Flags); 456 } 457 void 458 VisitTemplateSpecializationType(const TemplateSpecializationType *TST) { 459 // Have to handle these case-by-case. 460 461 // templated type aliases: there's no specialized/instantiated using 462 // decl to point to. So try to find a decl for the underlying type 463 // (after substitution), and failing that point to the (templated) using 464 // decl. 465 if (TST->isTypeAlias()) { 466 Outer.add(TST->getAliasedType(), Flags | Rel::Underlying); 467 // Don't *traverse* the alias, which would result in traversing the 468 // template of the underlying type. 469 Outer.report( 470 TST->getTemplateName().getAsTemplateDecl()->getTemplatedDecl(), 471 Flags | Rel::Alias | Rel::TemplatePattern); 472 } 473 // specializations of template template parameters aren't instantiated 474 // into decls, so they must refer to the parameter itself. 475 else if (const auto *Parm = 476 llvm::dyn_cast_or_null<TemplateTemplateParmDecl>( 477 TST->getTemplateName().getAsTemplateDecl())) 478 Outer.add(Parm, Flags); 479 // class template specializations have a (specialized) CXXRecordDecl. 480 else if (const CXXRecordDecl *RD = TST->getAsCXXRecordDecl()) 481 Outer.add(RD, Flags); // add(Decl) will despecialize if needed. 482 else { 483 // fallback: the (un-specialized) declaration from primary template. 484 if (auto *TD = TST->getTemplateName().getAsTemplateDecl()) 485 Outer.add(TD->getTemplatedDecl(), Flags | Rel::TemplatePattern); 486 } 487 } 488 void VisitTemplateTypeParmType(const TemplateTypeParmType *TTPT) { 489 Outer.add(TTPT->getDecl(), Flags); 490 } 491 void VisitObjCInterfaceType(const ObjCInterfaceType *OIT) { 492 Outer.add(OIT->getDecl(), Flags); 493 } 494 void VisitObjCObjectType(const ObjCObjectType *OOT) { 495 // FIXME: ObjCObjectTypeLoc has no children for the protocol list, so 496 // there is no node in id<Foo> that refers to ObjCProtocolDecl Foo. 497 if (OOT->isObjCQualifiedId() && OOT->getNumProtocols() == 1) 498 Outer.add(OOT->getProtocol(0), Flags); 499 } 500 }; 501 Visitor(*this, Flags).Visit(T.getTypePtr()); 502 } 503 504 void add(const NestedNameSpecifier *NNS, RelSet Flags) { 505 if (!NNS) 506 return; 507 debug(*NNS, Flags); 508 switch (NNS->getKind()) { 509 case NestedNameSpecifier::Identifier: 510 return; 511 case NestedNameSpecifier::Namespace: 512 add(NNS->getAsNamespace(), Flags); 513 return; 514 case NestedNameSpecifier::NamespaceAlias: 515 add(NNS->getAsNamespaceAlias(), Flags); 516 return; 517 case NestedNameSpecifier::TypeSpec: 518 case NestedNameSpecifier::TypeSpecWithTemplate: 519 add(QualType(NNS->getAsType(), 0), Flags); 520 return; 521 case NestedNameSpecifier::Global: 522 // This should be TUDecl, but we can't get a pointer to it! 523 return; 524 case NestedNameSpecifier::Super: 525 add(NNS->getAsRecordDecl(), Flags); 526 return; 527 } 528 llvm_unreachable("unhandled NestedNameSpecifier::SpecifierKind"); 529 } 530 531 void add(const CXXCtorInitializer *CCI, RelSet Flags) { 532 if (!CCI) 533 return; 534 debug(*CCI, Flags); 535 536 if (CCI->isAnyMemberInitializer()) 537 add(CCI->getAnyMember(), Flags); 538 // Constructor calls contain a TypeLoc node, so we don't handle them here. 539 } 540 }; 541 542 } // namespace 543 544 llvm::SmallVector<std::pair<const NamedDecl *, DeclRelationSet>, 1> 545 allTargetDecls(const ast_type_traits::DynTypedNode &N) { 546 dlog("allTargetDecls({0})", nodeToString(N)); 547 TargetFinder Finder; 548 DeclRelationSet Flags; 549 if (const Decl *D = N.get<Decl>()) 550 Finder.add(D, Flags); 551 else if (const Stmt *S = N.get<Stmt>()) 552 Finder.add(S, Flags); 553 else if (const NestedNameSpecifierLoc *NNSL = N.get<NestedNameSpecifierLoc>()) 554 Finder.add(NNSL->getNestedNameSpecifier(), Flags); 555 else if (const NestedNameSpecifier *NNS = N.get<NestedNameSpecifier>()) 556 Finder.add(NNS, Flags); 557 else if (const TypeLoc *TL = N.get<TypeLoc>()) 558 Finder.add(TL->getType(), Flags); 559 else if (const QualType *QT = N.get<QualType>()) 560 Finder.add(*QT, Flags); 561 else if (const CXXCtorInitializer *CCI = N.get<CXXCtorInitializer>()) 562 Finder.add(CCI, Flags); 563 564 return Finder.takeDecls(); 565 } 566 567 llvm::SmallVector<const NamedDecl *, 1> 568 targetDecl(const ast_type_traits::DynTypedNode &N, DeclRelationSet Mask) { 569 llvm::SmallVector<const NamedDecl *, 1> Result; 570 for (const auto &Entry : allTargetDecls(N)) { 571 if (!(Entry.second & ~Mask)) 572 Result.push_back(Entry.first); 573 } 574 return Result; 575 } 576 577 llvm::SmallVector<const NamedDecl *, 1> 578 explicitReferenceTargets(DynTypedNode N, DeclRelationSet Mask) { 579 assert(!(Mask & (DeclRelation::TemplatePattern | 580 DeclRelation::TemplateInstantiation)) && 581 "explicitReferenceTargets handles templates on its own"); 582 auto Decls = allTargetDecls(N); 583 584 // We prefer to return template instantiation, but fallback to template 585 // pattern if instantiation is not available. 586 Mask |= DeclRelation::TemplatePattern | DeclRelation::TemplateInstantiation; 587 588 llvm::SmallVector<const NamedDecl *, 1> TemplatePatterns; 589 llvm::SmallVector<const NamedDecl *, 1> Targets; 590 bool SeenTemplateInstantiations = false; 591 for (auto &D : Decls) { 592 if (D.second & ~Mask) 593 continue; 594 if (D.second & DeclRelation::TemplatePattern) { 595 TemplatePatterns.push_back(D.first); 596 continue; 597 } 598 if (D.second & DeclRelation::TemplateInstantiation) 599 SeenTemplateInstantiations = true; 600 Targets.push_back(D.first); 601 } 602 if (!SeenTemplateInstantiations) 603 Targets.insert(Targets.end(), TemplatePatterns.begin(), 604 TemplatePatterns.end()); 605 return Targets; 606 } 607 608 namespace { 609 llvm::SmallVector<ReferenceLoc, 2> refInDecl(const Decl *D) { 610 struct Visitor : ConstDeclVisitor<Visitor> { 611 llvm::SmallVector<ReferenceLoc, 2> Refs; 612 613 void VisitUsingDirectiveDecl(const UsingDirectiveDecl *D) { 614 // We want to keep it as non-declaration references, as the 615 // "using namespace" declaration doesn't have a name. 616 Refs.push_back(ReferenceLoc{D->getQualifierLoc(), 617 D->getIdentLocation(), 618 /*IsDecl=*/false, 619 {D->getNominatedNamespaceAsWritten()}}); 620 } 621 622 void VisitUsingDecl(const UsingDecl *D) { 623 // "using ns::identifier;" is a non-declaration reference. 624 Refs.push_back( 625 ReferenceLoc{D->getQualifierLoc(), D->getLocation(), /*IsDecl=*/false, 626 explicitReferenceTargets(DynTypedNode::create(*D), 627 DeclRelation::Underlying)}); 628 } 629 630 void VisitNamespaceAliasDecl(const NamespaceAliasDecl *D) { 631 // For namespace alias, "namespace Foo = Target;", we add two references. 632 // Add a declaration reference for Foo. 633 VisitNamedDecl(D); 634 // Add a non-declaration reference for Target. 635 Refs.push_back(ReferenceLoc{D->getQualifierLoc(), 636 D->getTargetNameLoc(), 637 /*IsDecl=*/false, 638 {D->getAliasedNamespace()}}); 639 } 640 641 void VisitNamedDecl(const NamedDecl *ND) { 642 // We choose to ignore {Class, Function, Var, TypeAlias}TemplateDecls. As 643 // as their underlying decls, covering the same range, will be visited. 644 if (llvm::isa<ClassTemplateDecl>(ND) || 645 llvm::isa<FunctionTemplateDecl>(ND) || 646 llvm::isa<VarTemplateDecl>(ND) || 647 llvm::isa<TypeAliasTemplateDecl>(ND)) 648 return; 649 // FIXME: decide on how to surface destructors when we need them. 650 if (llvm::isa<CXXDestructorDecl>(ND)) 651 return; 652 // Filter anonymous decls, name location will point outside the name token 653 // and the clients are not prepared to handle that. 654 if (ND->getDeclName().isIdentifier() && 655 !ND->getDeclName().getAsIdentifierInfo()) 656 return; 657 Refs.push_back(ReferenceLoc{getQualifierLoc(*ND), 658 ND->getLocation(), 659 /*IsDecl=*/true, 660 {ND}}); 661 } 662 }; 663 664 Visitor V; 665 V.Visit(D); 666 return V.Refs; 667 } 668 669 llvm::SmallVector<ReferenceLoc, 2> refInStmt(const Stmt *S) { 670 struct Visitor : ConstStmtVisitor<Visitor> { 671 // FIXME: handle more complicated cases: more ObjC, designated initializers. 672 llvm::SmallVector<ReferenceLoc, 2> Refs; 673 674 void VisitConceptSpecializationExpr(const ConceptSpecializationExpr *E) { 675 Refs.push_back(ReferenceLoc{E->getNestedNameSpecifierLoc(), 676 E->getConceptNameLoc(), 677 /*IsDecl=*/false, 678 {E->getNamedConcept()}}); 679 } 680 681 void VisitDeclRefExpr(const DeclRefExpr *E) { 682 Refs.push_back(ReferenceLoc{E->getQualifierLoc(), 683 E->getNameInfo().getLoc(), 684 /*IsDecl=*/false, 685 {E->getFoundDecl()}}); 686 } 687 688 void VisitDependentScopeDeclRefExpr(const DependentScopeDeclRefExpr *E) { 689 Refs.push_back(ReferenceLoc{ 690 E->getQualifierLoc(), E->getNameInfo().getLoc(), /*IsDecl=*/false, 691 explicitReferenceTargets(DynTypedNode::create(*E), {})}); 692 } 693 694 void VisitMemberExpr(const MemberExpr *E) { 695 // Skip destructor calls to avoid duplication: TypeLoc within will be 696 // visited separately. 697 if (llvm::dyn_cast<CXXDestructorDecl>(E->getFoundDecl().getDecl())) 698 return; 699 Refs.push_back(ReferenceLoc{E->getQualifierLoc(), 700 E->getMemberNameInfo().getLoc(), 701 /*IsDecl=*/false, 702 {E->getFoundDecl()}}); 703 } 704 705 void 706 VisitCXXDependentScopeMemberExpr(const CXXDependentScopeMemberExpr *E) { 707 Refs.push_back( 708 ReferenceLoc{E->getQualifierLoc(), E->getMemberNameInfo().getLoc(), 709 /*IsDecl=*/false, 710 explicitReferenceTargets(DynTypedNode::create(*E), {})}); 711 } 712 713 void VisitOverloadExpr(const OverloadExpr *E) { 714 Refs.push_back(ReferenceLoc{E->getQualifierLoc(), 715 E->getNameInfo().getLoc(), 716 /*IsDecl=*/false, 717 llvm::SmallVector<const NamedDecl *, 1>( 718 E->decls().begin(), E->decls().end())}); 719 } 720 721 void VisitSizeOfPackExpr(const SizeOfPackExpr *E) { 722 Refs.push_back(ReferenceLoc{NestedNameSpecifierLoc(), 723 E->getPackLoc(), 724 /*IsDecl=*/false, 725 {E->getPack()}}); 726 } 727 728 void VisitObjCPropertyRefExpr(const ObjCPropertyRefExpr *E) { 729 Refs.push_back(ReferenceLoc{ 730 NestedNameSpecifierLoc(), E->getLocation(), 731 /*IsDecl=*/false, 732 // Select the getter, setter, or @property depending on the call. 733 explicitReferenceTargets(DynTypedNode::create(*E), {})}); 734 } 735 736 void VisitDesignatedInitExpr(const DesignatedInitExpr *DIE) { 737 for (const DesignatedInitExpr::Designator &D : DIE->designators()) { 738 if (!D.isFieldDesignator()) 739 continue; 740 741 llvm::SmallVector<const NamedDecl *, 1> Targets; 742 if (D.getField()) 743 Targets.push_back(D.getField()); 744 Refs.push_back(ReferenceLoc{NestedNameSpecifierLoc(), D.getFieldLoc(), 745 /*IsDecl=*/false, std::move(Targets)}); 746 } 747 } 748 749 void VisitGotoStmt(const GotoStmt *GS) { 750 llvm::SmallVector<const NamedDecl *, 1> Targets; 751 if (const auto *L = GS->getLabel()) 752 Targets.push_back(L); 753 Refs.push_back(ReferenceLoc{NestedNameSpecifierLoc(), GS->getLabelLoc(), 754 /*IsDecl=*/false, std::move(Targets)}); 755 } 756 757 void VisitLabelStmt(const LabelStmt *LS) { 758 Refs.push_back(ReferenceLoc{NestedNameSpecifierLoc(), 759 LS->getIdentLoc(), 760 /*IsDecl=*/true, 761 {LS->getDecl()}}); 762 } 763 }; 764 765 Visitor V; 766 V.Visit(S); 767 return V.Refs; 768 } 769 770 llvm::SmallVector<ReferenceLoc, 2> refInTypeLoc(TypeLoc L) { 771 struct Visitor : TypeLocVisitor<Visitor> { 772 llvm::Optional<ReferenceLoc> Ref; 773 774 void VisitElaboratedTypeLoc(ElaboratedTypeLoc L) { 775 // We only know about qualifier, rest if filled by inner locations. 776 Visit(L.getNamedTypeLoc().getUnqualifiedLoc()); 777 // Fill in the qualifier. 778 if (!Ref) 779 return; 780 assert(!Ref->Qualifier.hasQualifier() && "qualifier already set"); 781 Ref->Qualifier = L.getQualifierLoc(); 782 } 783 784 void VisitTagTypeLoc(TagTypeLoc L) { 785 Ref = ReferenceLoc{NestedNameSpecifierLoc(), 786 L.getNameLoc(), 787 /*IsDecl=*/false, 788 {L.getDecl()}}; 789 } 790 791 void VisitTemplateTypeParmTypeLoc(TemplateTypeParmTypeLoc L) { 792 Ref = ReferenceLoc{NestedNameSpecifierLoc(), 793 L.getNameLoc(), 794 /*IsDecl=*/false, 795 {L.getDecl()}}; 796 } 797 798 void VisitTemplateSpecializationTypeLoc(TemplateSpecializationTypeLoc L) { 799 // We must ensure template type aliases are included in results if they 800 // were written in the source code, e.g. in 801 // template <class T> using valias = vector<T>; 802 // ^valias<int> x; 803 // 'explicitReferenceTargets' will return: 804 // 1. valias with mask 'Alias'. 805 // 2. 'vector<int>' with mask 'Underlying'. 806 // we want to return only #1 in this case. 807 Ref = ReferenceLoc{ 808 NestedNameSpecifierLoc(), L.getTemplateNameLoc(), /*IsDecl=*/false, 809 explicitReferenceTargets(DynTypedNode::create(L.getType()), 810 DeclRelation::Alias)}; 811 } 812 void VisitDeducedTemplateSpecializationTypeLoc( 813 DeducedTemplateSpecializationTypeLoc L) { 814 Ref = ReferenceLoc{ 815 NestedNameSpecifierLoc(), L.getNameLoc(), /*IsDecl=*/false, 816 explicitReferenceTargets(DynTypedNode::create(L.getType()), 817 DeclRelation::Alias)}; 818 } 819 820 void VisitInjectedClassNameTypeLoc(InjectedClassNameTypeLoc TL) { 821 Ref = ReferenceLoc{NestedNameSpecifierLoc(), 822 TL.getNameLoc(), 823 /*IsDecl=*/false, 824 {TL.getDecl()}}; 825 } 826 827 void VisitDependentTemplateSpecializationTypeLoc( 828 DependentTemplateSpecializationTypeLoc L) { 829 Ref = ReferenceLoc{ 830 L.getQualifierLoc(), L.getTemplateNameLoc(), /*IsDecl=*/false, 831 explicitReferenceTargets(DynTypedNode::create(L.getType()), {})}; 832 } 833 834 void VisitDependentNameTypeLoc(DependentNameTypeLoc L) { 835 Ref = ReferenceLoc{ 836 L.getQualifierLoc(), L.getNameLoc(), /*IsDecl=*/false, 837 explicitReferenceTargets(DynTypedNode::create(L.getType()), {})}; 838 } 839 840 void VisitTypedefTypeLoc(TypedefTypeLoc L) { 841 Ref = ReferenceLoc{NestedNameSpecifierLoc(), 842 L.getNameLoc(), 843 /*IsDecl=*/false, 844 {L.getTypedefNameDecl()}}; 845 } 846 }; 847 848 Visitor V; 849 V.Visit(L.getUnqualifiedLoc()); 850 if (!V.Ref) 851 return {}; 852 return {*V.Ref}; 853 } 854 855 class ExplicitReferenceCollector 856 : public RecursiveASTVisitor<ExplicitReferenceCollector> { 857 public: 858 ExplicitReferenceCollector(llvm::function_ref<void(ReferenceLoc)> Out) 859 : Out(Out) { 860 assert(Out); 861 } 862 863 bool VisitTypeLoc(TypeLoc TTL) { 864 if (TypeLocsToSkip.count(TTL.getBeginLoc().getRawEncoding())) 865 return true; 866 visitNode(DynTypedNode::create(TTL)); 867 return true; 868 } 869 870 bool TraverseElaboratedTypeLoc(ElaboratedTypeLoc L) { 871 // ElaboratedTypeLoc will reports information for its inner type loc. 872 // Otherwise we loose information about inner types loc's qualifier. 873 TypeLoc Inner = L.getNamedTypeLoc().getUnqualifiedLoc(); 874 TypeLocsToSkip.insert(Inner.getBeginLoc().getRawEncoding()); 875 return RecursiveASTVisitor::TraverseElaboratedTypeLoc(L); 876 } 877 878 bool VisitStmt(Stmt *S) { 879 visitNode(DynTypedNode::create(*S)); 880 return true; 881 } 882 883 bool TraverseOpaqueValueExpr(OpaqueValueExpr *OVE) { 884 visitNode(DynTypedNode::create(*OVE)); 885 // Not clear why the source expression is skipped by default... 886 // FIXME: can we just make RecursiveASTVisitor do this? 887 return RecursiveASTVisitor::TraverseStmt(OVE->getSourceExpr()); 888 } 889 890 bool TraversePseudoObjectExpr(PseudoObjectExpr *POE) { 891 visitNode(DynTypedNode::create(*POE)); 892 // Traverse only the syntactic form to find the *written* references. 893 // (The semantic form also contains lots of duplication) 894 return RecursiveASTVisitor::TraverseStmt(POE->getSyntacticForm()); 895 } 896 897 // We re-define Traverse*, since there's no corresponding Visit*. 898 // TemplateArgumentLoc is the only way to get locations for references to 899 // template template parameters. 900 bool TraverseTemplateArgumentLoc(TemplateArgumentLoc A) { 901 llvm::SmallVector<const NamedDecl *, 1> Targets; 902 switch (A.getArgument().getKind()) { 903 case TemplateArgument::Template: 904 case TemplateArgument::TemplateExpansion: 905 if (const auto *D = A.getArgument() 906 .getAsTemplateOrTemplatePattern() 907 .getAsTemplateDecl()) 908 Targets.push_back(D); 909 reportReference(ReferenceLoc{A.getTemplateQualifierLoc(), 910 A.getTemplateNameLoc(), 911 /*IsDecl=*/false, Targets}, 912 DynTypedNode::create(A.getArgument())); 913 break; 914 case TemplateArgument::Declaration: 915 break; // FIXME: can this actually happen in TemplateArgumentLoc? 916 case TemplateArgument::Integral: 917 case TemplateArgument::Null: 918 case TemplateArgument::NullPtr: 919 break; // no references. 920 case TemplateArgument::Pack: 921 case TemplateArgument::Type: 922 case TemplateArgument::Expression: 923 break; // Handled by VisitType and VisitExpression. 924 }; 925 return RecursiveASTVisitor::TraverseTemplateArgumentLoc(A); 926 } 927 928 bool VisitDecl(Decl *D) { 929 visitNode(DynTypedNode::create(*D)); 930 return true; 931 } 932 933 // We have to use Traverse* because there is no corresponding Visit*. 934 bool TraverseNestedNameSpecifierLoc(NestedNameSpecifierLoc L) { 935 if (!L.getNestedNameSpecifier()) 936 return true; 937 visitNode(DynTypedNode::create(L)); 938 // Inner type is missing information about its qualifier, skip it. 939 if (auto TL = L.getTypeLoc()) 940 TypeLocsToSkip.insert(TL.getBeginLoc().getRawEncoding()); 941 return RecursiveASTVisitor::TraverseNestedNameSpecifierLoc(L); 942 } 943 944 bool TraverseConstructorInitializer(CXXCtorInitializer *Init) { 945 visitNode(DynTypedNode::create(*Init)); 946 return RecursiveASTVisitor::TraverseConstructorInitializer(Init); 947 } 948 949 private: 950 /// Obtain information about a reference directly defined in \p N. Does not 951 /// recurse into child nodes, e.g. do not expect references for constructor 952 /// initializers 953 /// 954 /// Any of the fields in the returned structure can be empty, but not all of 955 /// them, e.g. 956 /// - for implicitly generated nodes (e.g. MemberExpr from range-based-for), 957 /// source location information may be missing, 958 /// - for dependent code, targets may be empty. 959 /// 960 /// (!) For the purposes of this function declarations are not considered to 961 /// be references. However, declarations can have references inside them, 962 /// e.g. 'namespace foo = std' references namespace 'std' and this 963 /// function will return the corresponding reference. 964 llvm::SmallVector<ReferenceLoc, 2> explicitReference(DynTypedNode N) { 965 if (auto *D = N.get<Decl>()) 966 return refInDecl(D); 967 if (auto *S = N.get<Stmt>()) 968 return refInStmt(S); 969 if (auto *NNSL = N.get<NestedNameSpecifierLoc>()) { 970 // (!) 'DeclRelation::Alias' ensures we do not loose namespace aliases. 971 return {ReferenceLoc{ 972 NNSL->getPrefix(), NNSL->getLocalBeginLoc(), false, 973 explicitReferenceTargets( 974 DynTypedNode::create(*NNSL->getNestedNameSpecifier()), 975 DeclRelation::Alias)}}; 976 } 977 if (const TypeLoc *TL = N.get<TypeLoc>()) 978 return refInTypeLoc(*TL); 979 if (const CXXCtorInitializer *CCI = N.get<CXXCtorInitializer>()) { 980 // Other type initializers (e.g. base initializer) are handled by visiting 981 // the typeLoc. 982 if (CCI->isAnyMemberInitializer()) { 983 return {ReferenceLoc{NestedNameSpecifierLoc(), 984 CCI->getMemberLocation(), 985 /*IsDecl=*/false, 986 {CCI->getAnyMember()}}}; 987 } 988 } 989 // We do not have location information for other nodes (QualType, etc) 990 return {}; 991 } 992 993 void visitNode(DynTypedNode N) { 994 for (const auto &R : explicitReference(N)) 995 reportReference(R, N); 996 } 997 998 void reportReference(const ReferenceLoc &Ref, DynTypedNode N) { 999 // Our promise is to return only references from the source code. If we lack 1000 // location information, skip these nodes. 1001 // Normally this should not happen in practice, unless there are bugs in the 1002 // traversals or users started the traversal at an implicit node. 1003 if (Ref.NameLoc.isInvalid()) { 1004 dlog("invalid location at node {0}", nodeToString(N)); 1005 return; 1006 } 1007 Out(Ref); 1008 } 1009 1010 llvm::function_ref<void(ReferenceLoc)> Out; 1011 /// TypeLocs starting at these locations must be skipped, see 1012 /// TraverseElaboratedTypeSpecifierLoc for details. 1013 llvm::DenseSet</*SourceLocation*/ unsigned> TypeLocsToSkip; 1014 }; 1015 } // namespace 1016 1017 void findExplicitReferences(const Stmt *S, 1018 llvm::function_ref<void(ReferenceLoc)> Out) { 1019 assert(S); 1020 ExplicitReferenceCollector(Out).TraverseStmt(const_cast<Stmt *>(S)); 1021 } 1022 void findExplicitReferences(const Decl *D, 1023 llvm::function_ref<void(ReferenceLoc)> Out) { 1024 assert(D); 1025 ExplicitReferenceCollector(Out).TraverseDecl(const_cast<Decl *>(D)); 1026 } 1027 void findExplicitReferences(const ASTContext &AST, 1028 llvm::function_ref<void(ReferenceLoc)> Out) { 1029 ExplicitReferenceCollector(Out).TraverseAST(const_cast<ASTContext &>(AST)); 1030 } 1031 1032 llvm::raw_ostream &operator<<(llvm::raw_ostream &OS, DeclRelation R) { 1033 switch (R) { 1034 #define REL_CASE(X) \ 1035 case DeclRelation::X: \ 1036 return OS << #X; 1037 REL_CASE(Alias); 1038 REL_CASE(Underlying); 1039 REL_CASE(TemplateInstantiation); 1040 REL_CASE(TemplatePattern); 1041 #undef REL_CASE 1042 } 1043 llvm_unreachable("Unhandled DeclRelation enum"); 1044 } 1045 llvm::raw_ostream &operator<<(llvm::raw_ostream &OS, DeclRelationSet RS) { 1046 const char *Sep = ""; 1047 for (unsigned I = 0; I < RS.S.size(); ++I) { 1048 if (RS.S.test(I)) { 1049 OS << Sep << static_cast<DeclRelation>(I); 1050 Sep = "|"; 1051 } 1052 } 1053 return OS; 1054 } 1055 1056 llvm::raw_ostream &operator<<(llvm::raw_ostream &OS, ReferenceLoc R) { 1057 // note we cannot print R.NameLoc without a source manager. 1058 OS << "targets = {"; 1059 bool First = true; 1060 for (const NamedDecl *T : R.Targets) { 1061 if (!First) 1062 OS << ", "; 1063 else 1064 First = false; 1065 OS << printQualifiedName(*T) << printTemplateSpecializationArgs(*T); 1066 } 1067 OS << "}"; 1068 if (R.Qualifier) { 1069 OS << ", qualifier = '"; 1070 R.Qualifier.getNestedNameSpecifier()->print(OS, 1071 PrintingPolicy(LangOptions())); 1072 OS << "'"; 1073 } 1074 if (R.IsDecl) 1075 OS << ", decl"; 1076 return OS; 1077 } 1078 1079 } // namespace clangd 1080 } // namespace clang 1081