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 "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/ExprObjC.h" 21 #include "clang/AST/NestedNameSpecifier.h" 22 #include "clang/AST/PrettyPrinter.h" 23 #include "clang/AST/RecursiveASTVisitor.h" 24 #include "clang/AST/StmtVisitor.h" 25 #include "clang/AST/TemplateBase.h" 26 #include "clang/AST/Type.h" 27 #include "clang/AST/TypeLoc.h" 28 #include "clang/AST/TypeLocVisitor.h" 29 #include "clang/Basic/LangOptions.h" 30 #include "clang/Basic/SourceLocation.h" 31 #include "llvm/ADT/STLExtras.h" 32 #include "llvm/ADT/SmallVector.h" 33 #include "llvm/Support/Casting.h" 34 #include "llvm/Support/Compiler.h" 35 #include "llvm/Support/raw_ostream.h" 36 #include <utility> 37 38 namespace clang { 39 namespace clangd { 40 namespace { 41 using ast_type_traits::DynTypedNode; 42 43 LLVM_ATTRIBUTE_UNUSED std::string 44 nodeToString(const ast_type_traits::DynTypedNode &N) { 45 std::string S = N.getNodeKind().asStringRef(); 46 { 47 llvm::raw_string_ostream OS(S); 48 OS << ": "; 49 N.print(OS, PrintingPolicy(LangOptions())); 50 } 51 std::replace(S.begin(), S.end(), '\n', ' '); 52 return S; 53 } 54 55 // TargetFinder locates the entities that an AST node refers to. 56 // 57 // Typically this is (possibly) one declaration and (possibly) one type, but 58 // may be more: 59 // - for ambiguous nodes like OverloadExpr 60 // - if we want to include e.g. both typedefs and the underlying type 61 // 62 // This is organized as a set of mutually recursive helpers for particular node 63 // types, but for most nodes this is a short walk rather than a deep traversal. 64 // 65 // It's tempting to do e.g. typedef resolution as a second normalization step, 66 // after finding the 'primary' decl etc. But we do this monolithically instead 67 // because: 68 // - normalization may require these traversals again (e.g. unwrapping a 69 // typedef reveals a decltype which must be traversed) 70 // - it doesn't simplify that much, e.g. the first stage must still be able 71 // to yield multiple decls to handle OverloadExpr 72 // - there are cases where it's required for correctness. e.g: 73 // template<class X> using pvec = vector<x*>; pvec<int> x; 74 // There's no Decl `pvec<int>`, we must choose `pvec<X>` or `vector<int*>` 75 // and both are lossy. We must know upfront what the caller ultimately wants. 76 // 77 // FIXME: improve common dependent scope using name lookup in primary templates. 78 // e.g. template<typename T> int foo() { return std::vector<T>().size(); } 79 // formally size() is unresolved, but the primary template is a good guess. 80 // This affects: 81 // - DependentTemplateSpecializationType, 82 // - DependentScopeMemberExpr 83 // - DependentScopeDeclRefExpr 84 // - DependentNameType 85 struct TargetFinder { 86 using RelSet = DeclRelationSet; 87 using Rel = DeclRelation; 88 llvm::SmallDenseMap<const Decl *, RelSet> Decls; 89 RelSet Flags; 90 91 static const Decl *getTemplatePattern(const Decl *D) { 92 if (const CXXRecordDecl *CRD = dyn_cast<CXXRecordDecl>(D)) { 93 return CRD->getTemplateInstantiationPattern(); 94 } else if (const FunctionDecl *FD = dyn_cast<FunctionDecl>(D)) { 95 return FD->getTemplateInstantiationPattern(); 96 } else if (auto *VD = dyn_cast<VarDecl>(D)) { 97 // Hmm: getTIP returns its arg if it's not an instantiation?! 98 VarDecl *T = VD->getTemplateInstantiationPattern(); 99 return (T == D) ? nullptr : T; 100 } else if (const auto *ED = dyn_cast<EnumDecl>(D)) { 101 return ED->getInstantiatedFromMemberEnum(); 102 } else if (isa<FieldDecl>(D) || isa<TypedefNameDecl>(D)) { 103 const auto *ND = cast<NamedDecl>(D); 104 if (const DeclContext *Parent = dyn_cast_or_null<DeclContext>( 105 getTemplatePattern(llvm::cast<Decl>(ND->getDeclContext())))) 106 for (const NamedDecl *BaseND : Parent->lookup(ND->getDeclName())) 107 if (!BaseND->isImplicit() && BaseND->getKind() == ND->getKind()) 108 return BaseND; 109 } else if (const auto *ECD = dyn_cast<EnumConstantDecl>(D)) { 110 if (const auto *ED = dyn_cast<EnumDecl>(ECD->getDeclContext())) { 111 if (const EnumDecl *Pattern = ED->getInstantiatedFromMemberEnum()) { 112 for (const NamedDecl *BaseECD : Pattern->lookup(ECD->getDeclName())) 113 return BaseECD; 114 } 115 } 116 } 117 return nullptr; 118 } 119 120 template <typename T> void debug(T &Node, RelSet Flags) { 121 dlog("visit [{0}] {1}", Flags, 122 nodeToString(ast_type_traits::DynTypedNode::create(Node))); 123 } 124 125 void report(const Decl *D, RelSet Flags) { 126 dlog("--> [{0}] {1}", Flags, 127 nodeToString(ast_type_traits::DynTypedNode::create(*D))); 128 Decls[D] |= Flags; 129 } 130 131 public: 132 void add(const Decl *D, RelSet Flags) { 133 if (!D) 134 return; 135 debug(*D, Flags); 136 if (const UsingDirectiveDecl *UDD = llvm::dyn_cast<UsingDirectiveDecl>(D)) 137 D = UDD->getNominatedNamespaceAsWritten(); 138 139 if (const TypedefNameDecl *TND = dyn_cast<TypedefNameDecl>(D)) { 140 add(TND->getUnderlyingType(), Flags | Rel::Underlying); 141 Flags |= Rel::Alias; // continue with the alias. 142 } else if (const UsingDecl *UD = dyn_cast<UsingDecl>(D)) { 143 for (const UsingShadowDecl *S : UD->shadows()) 144 add(S->getUnderlyingDecl(), Flags | Rel::Underlying); 145 Flags |= Rel::Alias; // continue with the alias. 146 } else if (const auto *NAD = dyn_cast<NamespaceAliasDecl>(D)) { 147 add(NAD->getUnderlyingDecl(), Flags | Rel::Underlying); 148 Flags |= Rel::Alias; // continue with the alias 149 } else if (const UsingShadowDecl *USD = dyn_cast<UsingShadowDecl>(D)) { 150 // Include the using decl, but don't traverse it. This may end up 151 // including *all* shadows, which we don't want. 152 report(USD->getUsingDecl(), Flags | Rel::Alias); 153 // Shadow decls are synthetic and not themselves interesting. 154 // Record the underlying decl instead, if allowed. 155 D = USD->getTargetDecl(); 156 Flags |= Rel::Underlying; // continue with the underlying decl. 157 } 158 159 if (const Decl *Pat = getTemplatePattern(D)) { 160 assert(Pat != D); 161 add(Pat, Flags | Rel::TemplatePattern); 162 // Now continue with the instantiation. 163 Flags |= Rel::TemplateInstantiation; 164 } 165 166 report(D, Flags); 167 } 168 169 void add(const Stmt *S, RelSet Flags) { 170 if (!S) 171 return; 172 debug(*S, Flags); 173 struct Visitor : public ConstStmtVisitor<Visitor> { 174 TargetFinder &Outer; 175 RelSet Flags; 176 Visitor(TargetFinder &Outer, RelSet Flags) : Outer(Outer), Flags(Flags) {} 177 178 void VisitCallExpr(const CallExpr *CE) { 179 Outer.add(CE->getCalleeDecl(), Flags); 180 } 181 void VisitDeclRefExpr(const DeclRefExpr *DRE) { 182 const Decl *D = DRE->getDecl(); 183 // UsingShadowDecl allows us to record the UsingDecl. 184 // getFoundDecl() returns the wrong thing in other cases (templates). 185 if (auto *USD = llvm::dyn_cast<UsingShadowDecl>(DRE->getFoundDecl())) 186 D = USD; 187 Outer.add(D, Flags); 188 } 189 void VisitMemberExpr(const MemberExpr *ME) { 190 const Decl *D = ME->getMemberDecl(); 191 if (auto *USD = 192 llvm::dyn_cast<UsingShadowDecl>(ME->getFoundDecl().getDecl())) 193 D = USD; 194 Outer.add(D, Flags); 195 } 196 void VisitOverloadExpr(const OverloadExpr *OE) { 197 for (auto *D : OE->decls()) 198 Outer.add(D, Flags); 199 } 200 void VisitSizeOfPackExpr(const SizeOfPackExpr *SE) { 201 Outer.add(SE->getPack(), Flags); 202 } 203 void VisitCXXConstructExpr(const CXXConstructExpr *CCE) { 204 Outer.add(CCE->getConstructor(), Flags); 205 } 206 void VisitDesignatedInitExpr(const DesignatedInitExpr *DIE) { 207 for (const DesignatedInitExpr::Designator &D : 208 llvm::reverse(DIE->designators())) 209 if (D.isFieldDesignator()) { 210 Outer.add(D.getField(), Flags); 211 // We don't know which designator was intended, we assume the outer. 212 break; 213 } 214 } 215 void VisitObjCIvarRefExpr(const ObjCIvarRefExpr *OIRE) { 216 Outer.add(OIRE->getDecl(), Flags); 217 } 218 void VisitObjCMessageExpr(const ObjCMessageExpr *OME) { 219 Outer.add(OME->getMethodDecl(), Flags); 220 } 221 void VisitObjCPropertyRefExpr(const ObjCPropertyRefExpr *OPRE) { 222 if (OPRE->isExplicitProperty()) 223 Outer.add(OPRE->getExplicitProperty(), Flags); 224 else { 225 if (OPRE->isMessagingGetter()) 226 Outer.add(OPRE->getImplicitPropertyGetter(), Flags); 227 if (OPRE->isMessagingSetter()) 228 Outer.add(OPRE->getImplicitPropertySetter(), Flags); 229 } 230 } 231 void VisitObjCProtocolExpr(const ObjCProtocolExpr *OPE) { 232 Outer.add(OPE->getProtocol(), Flags); 233 } 234 }; 235 Visitor(*this, Flags).Visit(S); 236 } 237 238 void add(QualType T, RelSet Flags) { 239 if (T.isNull()) 240 return; 241 debug(T, Flags); 242 struct Visitor : public TypeVisitor<Visitor> { 243 TargetFinder &Outer; 244 RelSet Flags; 245 Visitor(TargetFinder &Outer, RelSet Flags) : Outer(Outer), Flags(Flags) {} 246 247 void VisitTagType(const TagType *TT) { 248 Outer.add(TT->getAsTagDecl(), Flags); 249 } 250 void VisitDecltypeType(const DecltypeType *DTT) { 251 Outer.add(DTT->getUnderlyingType(), Flags | Rel::Underlying); 252 } 253 void VisitDeducedType(const DeducedType *DT) { 254 // FIXME: In practice this doesn't work: the AutoType you find inside 255 // TypeLoc never has a deduced type. https://llvm.org/PR42914 256 Outer.add(DT->getDeducedType(), Flags | Rel::Underlying); 257 } 258 void VisitTypedefType(const TypedefType *TT) { 259 Outer.add(TT->getDecl(), Flags); 260 } 261 void 262 VisitTemplateSpecializationType(const TemplateSpecializationType *TST) { 263 // Have to handle these case-by-case. 264 265 // templated type aliases: there's no specialized/instantiated using 266 // decl to point to. So try to find a decl for the underlying type 267 // (after substitution), and failing that point to the (templated) using 268 // decl. 269 if (TST->isTypeAlias()) { 270 Outer.add(TST->getAliasedType(), Flags | Rel::Underlying); 271 // Don't *traverse* the alias, which would result in traversing the 272 // template of the underlying type. 273 Outer.report( 274 TST->getTemplateName().getAsTemplateDecl()->getTemplatedDecl(), 275 Flags | Rel::Alias | Rel::TemplatePattern); 276 } 277 // specializations of template template parameters aren't instantiated 278 // into decls, so they must refer to the parameter itself. 279 else if (const auto *Parm = 280 llvm::dyn_cast_or_null<TemplateTemplateParmDecl>( 281 TST->getTemplateName().getAsTemplateDecl())) 282 Outer.add(Parm, Flags); 283 // class template specializations have a (specialized) CXXRecordDecl. 284 else if (const CXXRecordDecl *RD = TST->getAsCXXRecordDecl()) 285 Outer.add(RD, Flags); // add(Decl) will despecialize if needed. 286 else { 287 // fallback: the (un-specialized) declaration from primary template. 288 if (auto *TD = TST->getTemplateName().getAsTemplateDecl()) 289 Outer.add(TD->getTemplatedDecl(), Flags | Rel::TemplatePattern); 290 } 291 } 292 void VisitTemplateTypeParmType(const TemplateTypeParmType *TTPT) { 293 Outer.add(TTPT->getDecl(), Flags); 294 } 295 void VisitObjCInterfaceType(const ObjCInterfaceType *OIT) { 296 Outer.add(OIT->getDecl(), Flags); 297 } 298 void VisitObjCObjectType(const ObjCObjectType *OOT) { 299 // FIXME: ObjCObjectTypeLoc has no children for the protocol list, so 300 // there is no node in id<Foo> that refers to ObjCProtocolDecl Foo. 301 if (OOT->isObjCQualifiedId() && OOT->getNumProtocols() == 1) 302 Outer.add(OOT->getProtocol(0), Flags); 303 } 304 }; 305 Visitor(*this, Flags).Visit(T.getTypePtr()); 306 } 307 308 void add(const NestedNameSpecifier *NNS, RelSet Flags) { 309 if (!NNS) 310 return; 311 debug(*NNS, Flags); 312 switch (NNS->getKind()) { 313 case NestedNameSpecifier::Identifier: 314 return; 315 case NestedNameSpecifier::Namespace: 316 add(NNS->getAsNamespace(), Flags); 317 return; 318 case NestedNameSpecifier::NamespaceAlias: 319 add(NNS->getAsNamespaceAlias(), Flags); 320 return; 321 case NestedNameSpecifier::TypeSpec: 322 case NestedNameSpecifier::TypeSpecWithTemplate: 323 add(QualType(NNS->getAsType(), 0), Flags); 324 return; 325 case NestedNameSpecifier::Global: 326 // This should be TUDecl, but we can't get a pointer to it! 327 return; 328 case NestedNameSpecifier::Super: 329 add(NNS->getAsRecordDecl(), Flags); 330 return; 331 } 332 llvm_unreachable("unhandled NestedNameSpecifier::SpecifierKind"); 333 } 334 335 void add(const CXXCtorInitializer *CCI, RelSet Flags) { 336 if (!CCI) 337 return; 338 debug(*CCI, Flags); 339 340 if (CCI->isAnyMemberInitializer()) 341 add(CCI->getAnyMember(), Flags); 342 // Constructor calls contain a TypeLoc node, so we don't handle them here. 343 } 344 }; 345 346 } // namespace 347 348 llvm::SmallVector<std::pair<const Decl *, DeclRelationSet>, 1> 349 allTargetDecls(const ast_type_traits::DynTypedNode &N) { 350 dlog("allTargetDecls({0})", nodeToString(N)); 351 TargetFinder Finder; 352 DeclRelationSet Flags; 353 if (const Decl *D = N.get<Decl>()) 354 Finder.add(D, Flags); 355 else if (const Stmt *S = N.get<Stmt>()) 356 Finder.add(S, Flags); 357 else if (const NestedNameSpecifierLoc *NNSL = N.get<NestedNameSpecifierLoc>()) 358 Finder.add(NNSL->getNestedNameSpecifier(), Flags); 359 else if (const NestedNameSpecifier *NNS = N.get<NestedNameSpecifier>()) 360 Finder.add(NNS, Flags); 361 else if (const TypeLoc *TL = N.get<TypeLoc>()) 362 Finder.add(TL->getType(), Flags); 363 else if (const QualType *QT = N.get<QualType>()) 364 Finder.add(*QT, Flags); 365 else if (const CXXCtorInitializer *CCI = N.get<CXXCtorInitializer>()) 366 Finder.add(CCI, Flags); 367 368 return {Finder.Decls.begin(), Finder.Decls.end()}; 369 } 370 371 llvm::SmallVector<const Decl *, 1> 372 targetDecl(const ast_type_traits::DynTypedNode &N, DeclRelationSet Mask) { 373 llvm::SmallVector<const Decl *, 1> Result; 374 for (const auto &Entry : allTargetDecls(N)) { 375 if (!(Entry.second & ~Mask)) 376 Result.push_back(Entry.first); 377 } 378 return Result; 379 } 380 381 namespace { 382 /// Find declarations explicitly referenced in the source code defined by \p N. 383 /// For templates, will prefer to return a template instantiation whenever 384 /// possible. However, can also return a template pattern if the specialization 385 /// cannot be picked, e.g. in dependent code or when there is no corresponding 386 /// Decl for a template instantitation, e.g. for templated using decls: 387 /// template <class T> using Ptr = T*; 388 /// Ptr<int> x; 389 /// ^~~ there is no Decl for 'Ptr<int>', so we return the template pattern. 390 llvm::SmallVector<const NamedDecl *, 1> 391 explicitReferenceTargets(DynTypedNode N, DeclRelationSet Mask = {}) { 392 assert(!(Mask & (DeclRelation::TemplatePattern | 393 DeclRelation::TemplateInstantiation)) && 394 "explicitRefenceTargets handles templates on its own"); 395 auto Decls = allTargetDecls(N); 396 397 // We prefer to return template instantiation, but fallback to template 398 // pattern if instantiation is not available. 399 Mask |= DeclRelation::TemplatePattern | DeclRelation::TemplateInstantiation; 400 401 llvm::SmallVector<const NamedDecl *, 1> TemplatePatterns; 402 llvm::SmallVector<const NamedDecl *, 1> Targets; 403 bool SeenTemplateInstantiations = false; 404 for (auto &D : Decls) { 405 if (D.second & ~Mask) 406 continue; 407 if (D.second & DeclRelation::TemplatePattern) { 408 TemplatePatterns.push_back(llvm::cast<NamedDecl>(D.first)); 409 continue; 410 } 411 if (D.second & DeclRelation::TemplateInstantiation) 412 SeenTemplateInstantiations = true; 413 Targets.push_back(llvm::cast<NamedDecl>(D.first)); 414 } 415 if (!SeenTemplateInstantiations) 416 Targets.insert(Targets.end(), TemplatePatterns.begin(), 417 TemplatePatterns.end()); 418 return Targets; 419 } 420 421 llvm::SmallVector<ReferenceLoc, 2> refInDecl(const Decl *D) { 422 struct Visitor : ConstDeclVisitor<Visitor> { 423 llvm::SmallVector<ReferenceLoc, 2> Refs; 424 425 void VisitUsingDirectiveDecl(const UsingDirectiveDecl *D) { 426 // We want to keep it as non-declaration references, as the 427 // "using namespace" declaration doesn't have a name. 428 Refs.push_back(ReferenceLoc{D->getQualifierLoc(), 429 D->getIdentLocation(), 430 /*IsDecl=*/false, 431 {D->getNominatedNamespaceAsWritten()}}); 432 } 433 434 void VisitUsingDecl(const UsingDecl *D) { 435 // "using ns::identifer;" is a non-declaration reference. 436 Refs.push_back( 437 ReferenceLoc{D->getQualifierLoc(), D->getLocation(), /*IsDecl=*/false, 438 explicitReferenceTargets(DynTypedNode::create(*D), 439 DeclRelation::Underlying)}); 440 } 441 442 void VisitNamespaceAliasDecl(const NamespaceAliasDecl *D) { 443 // For namespace alias, "namespace Foo = Target;", we add two references. 444 // Add a declaration reference for Foo. 445 VisitNamedDecl(D); 446 // Add a non-declaration reference for Target. 447 Refs.push_back(ReferenceLoc{D->getQualifierLoc(), 448 D->getTargetNameLoc(), 449 /*IsDecl=*/false, 450 {D->getAliasedNamespace()}}); 451 } 452 453 void VisitNamedDecl(const NamedDecl *ND) { 454 // FIXME: decide on how to surface destructors when we need them. 455 if (llvm::isa<CXXDestructorDecl>(ND)) 456 return; 457 // Filter anonymous decls, name location will point outside the name token 458 // and the clients are not prepared to handle that. 459 if (ND->getDeclName().isIdentifier() && 460 !ND->getDeclName().getAsIdentifierInfo()) 461 return; 462 Refs.push_back(ReferenceLoc{getQualifierLoc(*ND), 463 ND->getLocation(), 464 /*IsDecl=*/true, 465 {ND}}); 466 } 467 }; 468 469 Visitor V; 470 V.Visit(D); 471 return V.Refs; 472 } 473 474 llvm::SmallVector<ReferenceLoc, 2> refInExpr(const Expr *E) { 475 struct Visitor : ConstStmtVisitor<Visitor> { 476 // FIXME: handle more complicated cases, e.g. ObjC, designated initializers. 477 llvm::SmallVector<ReferenceLoc, 2> Refs; 478 479 void VisitDeclRefExpr(const DeclRefExpr *E) { 480 Refs.push_back(ReferenceLoc{E->getQualifierLoc(), 481 E->getNameInfo().getLoc(), 482 /*IsDecl=*/false, 483 {E->getFoundDecl()}}); 484 } 485 486 void VisitMemberExpr(const MemberExpr *E) { 487 Refs.push_back(ReferenceLoc{E->getQualifierLoc(), 488 E->getMemberNameInfo().getLoc(), 489 /*IsDecl=*/false, 490 {E->getFoundDecl()}}); 491 } 492 493 void VisitOverloadExpr(const OverloadExpr *E) { 494 Refs.push_back(ReferenceLoc{E->getQualifierLoc(), 495 E->getNameInfo().getLoc(), 496 /*IsDecl=*/false, 497 llvm::SmallVector<const NamedDecl *, 1>( 498 E->decls().begin(), E->decls().end())}); 499 } 500 501 void VisitSizeOfPackExpr(const SizeOfPackExpr *E) { 502 Refs.push_back(ReferenceLoc{NestedNameSpecifierLoc(), 503 E->getPackLoc(), 504 /*IsDecl=*/false, 505 {E->getPack()}}); 506 } 507 }; 508 509 Visitor V; 510 V.Visit(E); 511 return V.Refs; 512 } 513 514 llvm::SmallVector<ReferenceLoc, 2> refInTypeLoc(TypeLoc L) { 515 struct Visitor : TypeLocVisitor<Visitor> { 516 llvm::Optional<ReferenceLoc> Ref; 517 518 void VisitElaboratedTypeLoc(ElaboratedTypeLoc L) { 519 // We only know about qualifier, rest if filled by inner locations. 520 Visit(L.getNamedTypeLoc().getUnqualifiedLoc()); 521 // Fill in the qualifier. 522 if (!Ref) 523 return; 524 assert(!Ref->Qualifier.hasQualifier() && "qualifier already set"); 525 Ref->Qualifier = L.getQualifierLoc(); 526 } 527 528 void VisitTagTypeLoc(TagTypeLoc L) { 529 Ref = ReferenceLoc{NestedNameSpecifierLoc(), 530 L.getNameLoc(), 531 /*IsDecl=*/false, 532 {L.getDecl()}}; 533 } 534 535 void VisitTemplateTypeParmTypeLoc(TemplateTypeParmTypeLoc L) { 536 Ref = ReferenceLoc{NestedNameSpecifierLoc(), 537 L.getNameLoc(), 538 /*IsDecl=*/false, 539 {L.getDecl()}}; 540 } 541 542 void VisitTemplateSpecializationTypeLoc(TemplateSpecializationTypeLoc L) { 543 // We must ensure template type aliases are included in results if they 544 // were written in the source code, e.g. in 545 // template <class T> using valias = vector<T>; 546 // ^valias<int> x; 547 // 'explicitReferenceTargets' will return: 548 // 1. valias with mask 'Alias'. 549 // 2. 'vector<int>' with mask 'Underlying'. 550 // we want to return only #1 in this case. 551 Ref = ReferenceLoc{ 552 NestedNameSpecifierLoc(), L.getTemplateNameLoc(), /*IsDecl=*/false, 553 explicitReferenceTargets(DynTypedNode::create(L.getType()), 554 DeclRelation::Alias)}; 555 } 556 void VisitDeducedTemplateSpecializationTypeLoc( 557 DeducedTemplateSpecializationTypeLoc L) { 558 Ref = ReferenceLoc{ 559 NestedNameSpecifierLoc(), L.getNameLoc(), /*IsDecl=*/false, 560 explicitReferenceTargets(DynTypedNode::create(L.getType()), 561 DeclRelation::Alias)}; 562 } 563 564 void VisitDependentTemplateSpecializationTypeLoc( 565 DependentTemplateSpecializationTypeLoc L) { 566 Ref = ReferenceLoc{ 567 L.getQualifierLoc(), L.getTemplateNameLoc(), /*IsDecl=*/false, 568 explicitReferenceTargets(DynTypedNode::create(L.getType()))}; 569 } 570 571 void VisitDependentNameTypeLoc(DependentNameTypeLoc L) { 572 Ref = ReferenceLoc{ 573 L.getQualifierLoc(), L.getNameLoc(), /*IsDecl=*/false, 574 explicitReferenceTargets(DynTypedNode::create(L.getType()))}; 575 } 576 577 void VisitTypedefTypeLoc(TypedefTypeLoc L) { 578 Ref = ReferenceLoc{NestedNameSpecifierLoc(), 579 L.getNameLoc(), 580 /*IsDecl=*/false, 581 {L.getTypedefNameDecl()}}; 582 } 583 }; 584 585 Visitor V; 586 V.Visit(L.getUnqualifiedLoc()); 587 if (!V.Ref) 588 return {}; 589 return {*V.Ref}; 590 } 591 592 class ExplicitReferenceColletor 593 : public RecursiveASTVisitor<ExplicitReferenceColletor> { 594 public: 595 ExplicitReferenceColletor(llvm::function_ref<void(ReferenceLoc)> Out) 596 : Out(Out) { 597 assert(Out); 598 } 599 600 bool VisitTypeLoc(TypeLoc TTL) { 601 if (TypeLocsToSkip.count(TTL.getBeginLoc().getRawEncoding())) 602 return true; 603 visitNode(DynTypedNode::create(TTL)); 604 return true; 605 } 606 607 bool TraverseElaboratedTypeLoc(ElaboratedTypeLoc L) { 608 // ElaboratedTypeLoc will reports information for its inner type loc. 609 // Otherwise we loose information about inner types loc's qualifier. 610 TypeLoc Inner = L.getNamedTypeLoc().getUnqualifiedLoc(); 611 TypeLocsToSkip.insert(Inner.getBeginLoc().getRawEncoding()); 612 return RecursiveASTVisitor::TraverseElaboratedTypeLoc(L); 613 } 614 615 bool VisitExpr(Expr *E) { 616 visitNode(DynTypedNode::create(*E)); 617 return true; 618 } 619 620 // We re-define Traverse*, since there's no corresponding Visit*. 621 // TemplateArgumentLoc is the only way to get locations for references to 622 // template template parameters. 623 bool TraverseTemplateArgumentLoc(TemplateArgumentLoc A) { 624 switch (A.getArgument().getKind()) { 625 case TemplateArgument::Template: 626 case TemplateArgument::TemplateExpansion: 627 reportReference(ReferenceLoc{A.getTemplateQualifierLoc(), 628 A.getTemplateNameLoc(), 629 /*IsDecl=*/false, 630 {A.getArgument() 631 .getAsTemplateOrTemplatePattern() 632 .getAsTemplateDecl()}}, 633 DynTypedNode::create(A.getArgument())); 634 break; 635 case TemplateArgument::Declaration: 636 break; // FIXME: can this actually happen in TemplateArgumentLoc? 637 case TemplateArgument::Integral: 638 case TemplateArgument::Null: 639 case TemplateArgument::NullPtr: 640 break; // no references. 641 case TemplateArgument::Pack: 642 case TemplateArgument::Type: 643 case TemplateArgument::Expression: 644 break; // Handled by VisitType and VisitExpression. 645 }; 646 return RecursiveASTVisitor::TraverseTemplateArgumentLoc(A); 647 } 648 649 bool VisitDecl(Decl *D) { 650 visitNode(DynTypedNode::create(*D)); 651 return true; 652 } 653 654 // We have to use Traverse* because there is no corresponding Visit*. 655 bool TraverseNestedNameSpecifierLoc(NestedNameSpecifierLoc L) { 656 if (!L.getNestedNameSpecifier()) 657 return true; 658 visitNode(DynTypedNode::create(L)); 659 // Inner type is missing information about its qualifier, skip it. 660 if (auto TL = L.getTypeLoc()) 661 TypeLocsToSkip.insert(TL.getBeginLoc().getRawEncoding()); 662 return RecursiveASTVisitor::TraverseNestedNameSpecifierLoc(L); 663 } 664 665 bool TraverseConstructorInitializer(CXXCtorInitializer *Init) { 666 visitNode(DynTypedNode::create(*Init)); 667 return RecursiveASTVisitor::TraverseConstructorInitializer(Init); 668 } 669 670 private: 671 /// Obtain information about a reference directly defined in \p N. Does not 672 /// recurse into child nodes, e.g. do not expect references for constructor 673 /// initializers 674 /// 675 /// Any of the fields in the returned structure can be empty, but not all of 676 /// them, e.g. 677 /// - for implicitly generated nodes (e.g. MemberExpr from range-based-for), 678 /// source location information may be missing, 679 /// - for dependent code, targets may be empty. 680 /// 681 /// (!) For the purposes of this function declarations are not considered to 682 /// be references. However, declarations can have references inside them, 683 /// e.g. 'namespace foo = std' references namespace 'std' and this 684 /// function will return the corresponding reference. 685 llvm::SmallVector<ReferenceLoc, 2> explicitReference(DynTypedNode N) { 686 if (auto *D = N.get<Decl>()) 687 return refInDecl(D); 688 if (auto *E = N.get<Expr>()) 689 return refInExpr(E); 690 if (auto *NNSL = N.get<NestedNameSpecifierLoc>()) { 691 // (!) 'DeclRelation::Alias' ensures we do not loose namespace aliases. 692 return {ReferenceLoc{ 693 NNSL->getPrefix(), NNSL->getLocalBeginLoc(), false, 694 explicitReferenceTargets( 695 DynTypedNode::create(*NNSL->getNestedNameSpecifier()), 696 DeclRelation::Alias)}}; 697 } 698 if (const TypeLoc *TL = N.get<TypeLoc>()) 699 return refInTypeLoc(*TL); 700 if (const CXXCtorInitializer *CCI = N.get<CXXCtorInitializer>()) { 701 // Other type initializers (e.g. base initializer) are handled by visiting 702 // the typeLoc. 703 if (CCI->isAnyMemberInitializer()) { 704 return {ReferenceLoc{NestedNameSpecifierLoc(), 705 CCI->getMemberLocation(), 706 /*IsDecl=*/false, 707 {CCI->getAnyMember()}}}; 708 } 709 } 710 // We do not have location information for other nodes (QualType, etc) 711 return {}; 712 } 713 714 void visitNode(DynTypedNode N) { 715 for (const auto &R : explicitReference(N)) 716 reportReference(R, N); 717 } 718 719 void reportReference(const ReferenceLoc &Ref, DynTypedNode N) { 720 // Our promise is to return only references from the source code. If we lack 721 // location information, skip these nodes. 722 // Normally this should not happen in practice, unless there are bugs in the 723 // traversals or users started the traversal at an implicit node. 724 if (Ref.NameLoc.isInvalid()) { 725 dlog("invalid location at node {0}", nodeToString(N)); 726 return; 727 } 728 Out(Ref); 729 } 730 731 llvm::function_ref<void(ReferenceLoc)> Out; 732 /// TypeLocs starting at these locations must be skipped, see 733 /// TraverseElaboratedTypeSpecifierLoc for details. 734 llvm::DenseSet</*SourceLocation*/ unsigned> TypeLocsToSkip; 735 }; 736 } // namespace 737 738 void findExplicitReferences(const Stmt *S, 739 llvm::function_ref<void(ReferenceLoc)> Out) { 740 assert(S); 741 ExplicitReferenceColletor(Out).TraverseStmt(const_cast<Stmt *>(S)); 742 } 743 void findExplicitReferences(const Decl *D, 744 llvm::function_ref<void(ReferenceLoc)> Out) { 745 assert(D); 746 ExplicitReferenceColletor(Out).TraverseDecl(const_cast<Decl *>(D)); 747 } 748 void findExplicitReferences(const ASTContext &AST, 749 llvm::function_ref<void(ReferenceLoc)> Out) { 750 ExplicitReferenceColletor(Out).TraverseAST(const_cast<ASTContext &>(AST)); 751 } 752 753 llvm::raw_ostream &operator<<(llvm::raw_ostream &OS, DeclRelation R) { 754 switch (R) { 755 #define REL_CASE(X) \ 756 case DeclRelation::X: \ 757 return OS << #X; 758 REL_CASE(Alias); 759 REL_CASE(Underlying); 760 REL_CASE(TemplateInstantiation); 761 REL_CASE(TemplatePattern); 762 #undef REL_CASE 763 } 764 llvm_unreachable("Unhandled DeclRelation enum"); 765 } 766 llvm::raw_ostream &operator<<(llvm::raw_ostream &OS, DeclRelationSet RS) { 767 const char *Sep = ""; 768 for (unsigned I = 0; I < RS.S.size(); ++I) { 769 if (RS.S.test(I)) { 770 OS << Sep << static_cast<DeclRelation>(I); 771 Sep = "|"; 772 } 773 } 774 return OS; 775 } 776 777 llvm::raw_ostream &operator<<(llvm::raw_ostream &OS, ReferenceLoc R) { 778 // note we cannot print R.NameLoc without a source manager. 779 OS << "targets = {"; 780 bool First = true; 781 for (const NamedDecl *T : R.Targets) { 782 if (!First) 783 OS << ", "; 784 else 785 First = false; 786 OS << printQualifiedName(*T) << printTemplateSpecializationArgs(*T); 787 } 788 OS << "}"; 789 if (R.Qualifier) { 790 OS << ", qualifier = '"; 791 R.Qualifier.getNestedNameSpecifier()->print(OS, 792 PrintingPolicy(LangOptions())); 793 OS << "'"; 794 } 795 if (R.IsDecl) 796 OS << ", decl"; 797 return OS; 798 } 799 800 } // namespace clangd 801 } // namespace clang 802