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