clang-tools-extra/clangd/FindTarget.cpp

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