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 
nodeToString(const DynTypedNode & N)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 
getTemplatePattern(const NamedDecl * D)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.
shouldSkipTypedef(const TypedefNameDecl * TD)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 
debugclang::clangd::__anona77b79730111::TargetFinder142   template <typename T> void debug(T &Node, RelSet Flags) {
143     dlog("visit [{0}] {1}", Flags, nodeToString(DynTypedNode::create(Node)));
144   }
145 
reportclang::clangd::__anona77b79730111::TargetFinder146   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:
TargetFinderclang::clangd::__anona77b79730111::TargetFinder155   TargetFinder(const HeuristicResolver *Resolver) : Resolver(Resolver) {}
156 
takeDeclsclang::clangd::__anona77b79730111::TargetFinder157   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 
addclang::clangd::__anona77b79730111::TargetFinder166   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       add(UED->getEnumDecl(), Flags);
193       Flags |= Rel::Alias; // continue with the alias.
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 decl, but don't traverse it. This may end up
211       // including *all* shadows, which we don't want.
212       report(USD->getIntroducer(), Flags | Rel::Alias);
213       // Shadow decls are synthetic and not themselves interesting.
214       // Record the underlying decl instead, if allowed.
215       D = USD->getTargetDecl();
216     } else if (const auto *DG = dyn_cast<CXXDeductionGuideDecl>(D)) {
217       D = DG->getDeducedTemplate();
218     } else if (const ObjCImplementationDecl *IID =
219                    dyn_cast<ObjCImplementationDecl>(D)) {
220       // Treat ObjC{Interface,Implementation}Decl as if they were a decl/def
221       // pair as long as the interface isn't implicit.
222       if (const auto *CID = IID->getClassInterface())
223         if (const auto *DD = CID->getDefinition())
224           if (!DD->isImplicitInterfaceDecl())
225             D = DD;
226     } else if (const ObjCCategoryImplDecl *CID =
227                    dyn_cast<ObjCCategoryImplDecl>(D)) {
228       // Treat ObjC{Category,CategoryImpl}Decl as if they were a decl/def pair.
229       D = CID->getCategoryDecl();
230     }
231     if (!D)
232       return;
233 
234     if (const Decl *Pat = getTemplatePattern(D)) {
235       assert(Pat != D);
236       add(Pat, Flags | Rel::TemplatePattern);
237       // Now continue with the instantiation.
238       Flags |= Rel::TemplateInstantiation;
239     }
240 
241     report(D, Flags);
242   }
243 
addclang::clangd::__anona77b79730111::TargetFinder244   void add(const Stmt *S, RelSet Flags) {
245     if (!S)
246       return;
247     debug(*S, Flags);
248     struct Visitor : public ConstStmtVisitor<Visitor> {
249       TargetFinder &Outer;
250       RelSet Flags;
251       Visitor(TargetFinder &Outer, RelSet Flags) : Outer(Outer), Flags(Flags) {}
252 
253       void VisitCallExpr(const CallExpr *CE) {
254         Outer.add(CE->getCalleeDecl(), Flags);
255       }
256       void VisitConceptSpecializationExpr(const ConceptSpecializationExpr *E) {
257         Outer.add(E->getNamedConcept(), Flags);
258       }
259       void VisitDeclRefExpr(const DeclRefExpr *DRE) {
260         const Decl *D = DRE->getDecl();
261         // UsingShadowDecl allows us to record the UsingDecl.
262         // getFoundDecl() returns the wrong thing in other cases (templates).
263         if (auto *USD = llvm::dyn_cast<UsingShadowDecl>(DRE->getFoundDecl()))
264           D = USD;
265         Outer.add(D, Flags);
266       }
267       void VisitMemberExpr(const MemberExpr *ME) {
268         const Decl *D = ME->getMemberDecl();
269         if (auto *USD =
270                 llvm::dyn_cast<UsingShadowDecl>(ME->getFoundDecl().getDecl()))
271           D = USD;
272         Outer.add(D, Flags);
273       }
274       void VisitOverloadExpr(const OverloadExpr *OE) {
275         for (auto *D : OE->decls())
276           Outer.add(D, Flags);
277       }
278       void VisitSizeOfPackExpr(const SizeOfPackExpr *SE) {
279         Outer.add(SE->getPack(), Flags);
280       }
281       void VisitCXXConstructExpr(const CXXConstructExpr *CCE) {
282         Outer.add(CCE->getConstructor(), Flags);
283       }
284       void VisitDesignatedInitExpr(const DesignatedInitExpr *DIE) {
285         for (const DesignatedInitExpr::Designator &D :
286              llvm::reverse(DIE->designators()))
287           if (D.isFieldDesignator()) {
288             Outer.add(D.getField(), Flags);
289             // We don't know which designator was intended, we assume the outer.
290             break;
291           }
292       }
293       void VisitGotoStmt(const GotoStmt *Goto) {
294         if (auto *LabelDecl = Goto->getLabel())
295           Outer.add(LabelDecl, Flags);
296       }
297       void VisitLabelStmt(const LabelStmt *Label) {
298         if (auto *LabelDecl = Label->getDecl())
299           Outer.add(LabelDecl, Flags);
300       }
301       void
302       VisitCXXDependentScopeMemberExpr(const CXXDependentScopeMemberExpr *E) {
303         if (Outer.Resolver) {
304           for (const NamedDecl *D : Outer.Resolver->resolveMemberExpr(E)) {
305             Outer.add(D, Flags);
306           }
307         }
308       }
309       void VisitDependentScopeDeclRefExpr(const DependentScopeDeclRefExpr *E) {
310         if (Outer.Resolver) {
311           for (const NamedDecl *D : Outer.Resolver->resolveDeclRefExpr(E)) {
312             Outer.add(D, Flags);
313           }
314         }
315       }
316       void VisitObjCIvarRefExpr(const ObjCIvarRefExpr *OIRE) {
317         Outer.add(OIRE->getDecl(), Flags);
318       }
319       void VisitObjCMessageExpr(const ObjCMessageExpr *OME) {
320         Outer.add(OME->getMethodDecl(), Flags);
321       }
322       void VisitObjCPropertyRefExpr(const ObjCPropertyRefExpr *OPRE) {
323         if (OPRE->isExplicitProperty())
324           Outer.add(OPRE->getExplicitProperty(), Flags);
325         else {
326           if (OPRE->isMessagingGetter())
327             Outer.add(OPRE->getImplicitPropertyGetter(), Flags);
328           if (OPRE->isMessagingSetter())
329             Outer.add(OPRE->getImplicitPropertySetter(), Flags);
330         }
331       }
332       void VisitObjCProtocolExpr(const ObjCProtocolExpr *OPE) {
333         Outer.add(OPE->getProtocol(), Flags);
334       }
335       void VisitOpaqueValueExpr(const OpaqueValueExpr *OVE) {
336         Outer.add(OVE->getSourceExpr(), Flags);
337       }
338       void VisitPseudoObjectExpr(const PseudoObjectExpr *POE) {
339         Outer.add(POE->getSyntacticForm(), Flags);
340       }
341       void VisitCXXNewExpr(const CXXNewExpr *CNE) {
342         Outer.add(CNE->getOperatorNew(), Flags);
343       }
344       void VisitCXXDeleteExpr(const CXXDeleteExpr *CDE) {
345         Outer.add(CDE->getOperatorDelete(), Flags);
346       }
347     };
348     Visitor(*this, Flags).Visit(S);
349   }
350 
addclang::clangd::__anona77b79730111::TargetFinder351   void add(QualType T, RelSet Flags) {
352     if (T.isNull())
353       return;
354     debug(T, Flags);
355     struct Visitor : public TypeVisitor<Visitor> {
356       TargetFinder &Outer;
357       RelSet Flags;
358       Visitor(TargetFinder &Outer, RelSet Flags) : Outer(Outer), Flags(Flags) {}
359 
360       void VisitTagType(const TagType *TT) {
361         Outer.add(TT->getAsTagDecl(), Flags);
362       }
363 
364       void VisitElaboratedType(const ElaboratedType *ET) {
365         Outer.add(ET->desugar(), Flags);
366       }
367 
368       void VisitUsingType(const UsingType *ET) {
369         Outer.add(ET->getFoundDecl(), Flags);
370       }
371 
372       void VisitInjectedClassNameType(const InjectedClassNameType *ICNT) {
373         Outer.add(ICNT->getDecl(), Flags);
374       }
375 
376       void VisitDecltypeType(const DecltypeType *DTT) {
377         Outer.add(DTT->getUnderlyingType(), Flags | Rel::Underlying);
378       }
379       void VisitDeducedType(const DeducedType *DT) {
380         // FIXME: In practice this doesn't work: the AutoType you find inside
381         // TypeLoc never has a deduced type. https://llvm.org/PR42914
382         Outer.add(DT->getDeducedType(), Flags);
383       }
384       void VisitUnresolvedUsingType(const UnresolvedUsingType *UUT) {
385         Outer.add(UUT->getDecl(), Flags);
386       }
387       void VisitDeducedTemplateSpecializationType(
388           const DeducedTemplateSpecializationType *DTST) {
389         if (const auto *USD = DTST->getTemplateName().getAsUsingShadowDecl())
390           Outer.add(USD, Flags);
391 
392         // FIXME: This is a workaround for https://llvm.org/PR42914,
393         // which is causing DTST->getDeducedType() to be empty. We
394         // fall back to the template pattern and miss the instantiation
395         // even when it's known in principle. Once that bug is fixed,
396         // the following code can be removed (the existing handling in
397         // VisitDeducedType() is sufficient).
398         if (auto *TD = DTST->getTemplateName().getAsTemplateDecl())
399           Outer.add(TD->getTemplatedDecl(), Flags | Rel::TemplatePattern);
400       }
401       void VisitDependentNameType(const DependentNameType *DNT) {
402         if (Outer.Resolver) {
403           for (const NamedDecl *ND :
404                Outer.Resolver->resolveDependentNameType(DNT)) {
405             Outer.add(ND, Flags);
406           }
407         }
408       }
409       void VisitDependentTemplateSpecializationType(
410           const DependentTemplateSpecializationType *DTST) {
411         if (Outer.Resolver) {
412           for (const NamedDecl *ND :
413                Outer.Resolver->resolveTemplateSpecializationType(DTST)) {
414             Outer.add(ND, Flags);
415           }
416         }
417       }
418       void VisitTypedefType(const TypedefType *TT) {
419         if (shouldSkipTypedef(TT->getDecl()))
420           return;
421         Outer.add(TT->getDecl(), Flags);
422       }
423       void
424       VisitTemplateSpecializationType(const TemplateSpecializationType *TST) {
425         // Have to handle these case-by-case.
426 
427         if (const auto *UTN = TST->getTemplateName().getAsUsingShadowDecl())
428           Outer.add(UTN, Flags);
429 
430         // templated type aliases: there's no specialized/instantiated using
431         // decl to point to. So try to find a decl for the underlying type
432         // (after substitution), and failing that point to the (templated) using
433         // decl.
434         if (TST->isTypeAlias()) {
435           Outer.add(TST->getAliasedType(), Flags | Rel::Underlying);
436           // Don't *traverse* the alias, which would result in traversing the
437           // template of the underlying type.
438           Outer.report(
439               TST->getTemplateName().getAsTemplateDecl()->getTemplatedDecl(),
440               Flags | Rel::Alias | Rel::TemplatePattern);
441         }
442         // specializations of template template parameters aren't instantiated
443         // into decls, so they must refer to the parameter itself.
444         else if (const auto *Parm =
445                      llvm::dyn_cast_or_null<TemplateTemplateParmDecl>(
446                          TST->getTemplateName().getAsTemplateDecl()))
447           Outer.add(Parm, Flags);
448         // class template specializations have a (specialized) CXXRecordDecl.
449         else if (const CXXRecordDecl *RD = TST->getAsCXXRecordDecl())
450           Outer.add(RD, Flags); // add(Decl) will despecialize if needed.
451         else {
452           // fallback: the (un-specialized) declaration from primary template.
453           if (auto *TD = TST->getTemplateName().getAsTemplateDecl())
454             Outer.add(TD->getTemplatedDecl(), Flags | Rel::TemplatePattern);
455         }
456       }
457       void VisitTemplateTypeParmType(const TemplateTypeParmType *TTPT) {
458         Outer.add(TTPT->getDecl(), Flags);
459       }
460       void VisitObjCInterfaceType(const ObjCInterfaceType *OIT) {
461         Outer.add(OIT->getDecl(), Flags);
462       }
463     };
464     Visitor(*this, Flags).Visit(T.getTypePtr());
465   }
466 
addclang::clangd::__anona77b79730111::TargetFinder467   void add(const NestedNameSpecifier *NNS, RelSet Flags) {
468     if (!NNS)
469       return;
470     debug(*NNS, Flags);
471     switch (NNS->getKind()) {
472     case NestedNameSpecifier::Namespace:
473       add(NNS->getAsNamespace(), Flags);
474       return;
475     case NestedNameSpecifier::NamespaceAlias:
476       add(NNS->getAsNamespaceAlias(), Flags);
477       return;
478     case NestedNameSpecifier::Identifier:
479       if (Resolver) {
480         add(QualType(Resolver->resolveNestedNameSpecifierToType(NNS), 0),
481             Flags);
482       }
483       return;
484     case NestedNameSpecifier::TypeSpec:
485     case NestedNameSpecifier::TypeSpecWithTemplate:
486       add(QualType(NNS->getAsType(), 0), Flags);
487       return;
488     case NestedNameSpecifier::Global:
489       // This should be TUDecl, but we can't get a pointer to it!
490       return;
491     case NestedNameSpecifier::Super:
492       add(NNS->getAsRecordDecl(), Flags);
493       return;
494     }
495     llvm_unreachable("unhandled NestedNameSpecifier::SpecifierKind");
496   }
497 
addclang::clangd::__anona77b79730111::TargetFinder498   void add(const CXXCtorInitializer *CCI, RelSet Flags) {
499     if (!CCI)
500       return;
501     debug(*CCI, Flags);
502 
503     if (CCI->isAnyMemberInitializer())
504       add(CCI->getAnyMember(), Flags);
505     // Constructor calls contain a TypeLoc node, so we don't handle them here.
506   }
507 
addclang::clangd::__anona77b79730111::TargetFinder508   void add(const TemplateArgument &Arg, RelSet Flags) {
509     // Only used for template template arguments.
510     // For type and non-type template arguments, SelectionTree
511     // will hit a more specific node (e.g. a TypeLoc or a
512     // DeclRefExpr).
513     if (Arg.getKind() == TemplateArgument::Template ||
514         Arg.getKind() == TemplateArgument::TemplateExpansion) {
515       if (TemplateDecl *TD =
516               Arg.getAsTemplateOrTemplatePattern().getAsTemplateDecl()) {
517         report(TD, Flags);
518       }
519       if (const auto *USD =
520               Arg.getAsTemplateOrTemplatePattern().getAsUsingShadowDecl())
521         add(USD, Flags);
522     }
523   }
524 };
525 
526 } // namespace
527 
528 llvm::SmallVector<std::pair<const NamedDecl *, DeclRelationSet>, 1>
allTargetDecls(const DynTypedNode & N,const HeuristicResolver * Resolver)529 allTargetDecls(const DynTypedNode &N, const HeuristicResolver *Resolver) {
530   dlog("allTargetDecls({0})", nodeToString(N));
531   TargetFinder Finder(Resolver);
532   DeclRelationSet Flags;
533   if (const Decl *D = N.get<Decl>())
534     Finder.add(D, Flags);
535   else if (const Stmt *S = N.get<Stmt>())
536     Finder.add(S, Flags);
537   else if (const NestedNameSpecifierLoc *NNSL = N.get<NestedNameSpecifierLoc>())
538     Finder.add(NNSL->getNestedNameSpecifier(), Flags);
539   else if (const NestedNameSpecifier *NNS = N.get<NestedNameSpecifier>())
540     Finder.add(NNS, Flags);
541   else if (const TypeLoc *TL = N.get<TypeLoc>())
542     Finder.add(TL->getType(), Flags);
543   else if (const QualType *QT = N.get<QualType>())
544     Finder.add(*QT, Flags);
545   else if (const CXXCtorInitializer *CCI = N.get<CXXCtorInitializer>())
546     Finder.add(CCI, Flags);
547   else if (const TemplateArgumentLoc *TAL = N.get<TemplateArgumentLoc>())
548     Finder.add(TAL->getArgument(), Flags);
549   else if (const CXXBaseSpecifier *CBS = N.get<CXXBaseSpecifier>())
550     Finder.add(CBS->getTypeSourceInfo()->getType(), Flags);
551   else if (const ObjCProtocolLoc *PL = N.get<ObjCProtocolLoc>())
552     Finder.add(PL->getProtocol(), Flags);
553   return Finder.takeDecls();
554 }
555 
556 llvm::SmallVector<const NamedDecl *, 1>
targetDecl(const DynTypedNode & N,DeclRelationSet Mask,const HeuristicResolver * Resolver)557 targetDecl(const DynTypedNode &N, DeclRelationSet Mask,
558            const HeuristicResolver *Resolver) {
559   llvm::SmallVector<const NamedDecl *, 1> Result;
560   for (const auto &Entry : allTargetDecls(N, Resolver)) {
561     if (!(Entry.second & ~Mask))
562       Result.push_back(Entry.first);
563   }
564   return Result;
565 }
566 
567 llvm::SmallVector<const NamedDecl *, 1>
explicitReferenceTargets(DynTypedNode N,DeclRelationSet Mask,const HeuristicResolver * Resolver)568 explicitReferenceTargets(DynTypedNode N, DeclRelationSet Mask,
569                          const HeuristicResolver *Resolver) {
570   assert(!(Mask & (DeclRelation::TemplatePattern |
571                    DeclRelation::TemplateInstantiation)) &&
572          "explicitReferenceTargets handles templates on its own");
573   auto Decls = allTargetDecls(N, Resolver);
574 
575   // We prefer to return template instantiation, but fallback to template
576   // pattern if instantiation is not available.
577   Mask |= DeclRelation::TemplatePattern | DeclRelation::TemplateInstantiation;
578 
579   llvm::SmallVector<const NamedDecl *, 1> TemplatePatterns;
580   llvm::SmallVector<const NamedDecl *, 1> Targets;
581   bool SeenTemplateInstantiations = false;
582   for (auto &D : Decls) {
583     if (D.second & ~Mask)
584       continue;
585     if (D.second & DeclRelation::TemplatePattern) {
586       TemplatePatterns.push_back(D.first);
587       continue;
588     }
589     if (D.second & DeclRelation::TemplateInstantiation)
590       SeenTemplateInstantiations = true;
591     Targets.push_back(D.first);
592   }
593   if (!SeenTemplateInstantiations)
594     Targets.insert(Targets.end(), TemplatePatterns.begin(),
595                    TemplatePatterns.end());
596   return Targets;
597 }
598 
599 namespace {
refInDecl(const Decl * D,const HeuristicResolver * Resolver)600 llvm::SmallVector<ReferenceLoc> refInDecl(const Decl *D,
601                                           const HeuristicResolver *Resolver) {
602   struct Visitor : ConstDeclVisitor<Visitor> {
603     Visitor(const HeuristicResolver *Resolver) : Resolver(Resolver) {}
604 
605     const HeuristicResolver *Resolver;
606     llvm::SmallVector<ReferenceLoc> Refs;
607 
608     void VisitUsingDirectiveDecl(const UsingDirectiveDecl *D) {
609       // We want to keep it as non-declaration references, as the
610       // "using namespace" declaration doesn't have a name.
611       Refs.push_back(ReferenceLoc{D->getQualifierLoc(),
612                                   D->getIdentLocation(),
613                                   /*IsDecl=*/false,
614                                   {D->getNominatedNamespaceAsWritten()}});
615     }
616 
617     void VisitUsingDecl(const UsingDecl *D) {
618       // "using ns::identifier;" is a non-declaration reference.
619       Refs.push_back(ReferenceLoc{
620           D->getQualifierLoc(), D->getLocation(), /*IsDecl=*/false,
621           explicitReferenceTargets(DynTypedNode::create(*D),
622                                    DeclRelation::Underlying, Resolver)});
623     }
624 
625     void VisitNamespaceAliasDecl(const NamespaceAliasDecl *D) {
626       // For namespace alias, "namespace Foo = Target;", we add two references.
627       // Add a declaration reference for Foo.
628       VisitNamedDecl(D);
629       // Add a non-declaration reference for Target.
630       Refs.push_back(ReferenceLoc{D->getQualifierLoc(),
631                                   D->getTargetNameLoc(),
632                                   /*IsDecl=*/false,
633                                   {D->getAliasedNamespace()}});
634     }
635 
636     void VisitNamedDecl(const NamedDecl *ND) {
637       // We choose to ignore {Class, Function, Var, TypeAlias}TemplateDecls. As
638       // as their underlying decls, covering the same range, will be visited.
639       if (llvm::isa<ClassTemplateDecl>(ND) ||
640           llvm::isa<FunctionTemplateDecl>(ND) ||
641           llvm::isa<VarTemplateDecl>(ND) ||
642           llvm::isa<TypeAliasTemplateDecl>(ND))
643         return;
644       // FIXME: decide on how to surface destructors when we need them.
645       if (llvm::isa<CXXDestructorDecl>(ND))
646         return;
647       // Filter anonymous decls, name location will point outside the name token
648       // and the clients are not prepared to handle that.
649       if (ND->getDeclName().isIdentifier() &&
650           !ND->getDeclName().getAsIdentifierInfo())
651         return;
652       Refs.push_back(ReferenceLoc{getQualifierLoc(*ND),
653                                   ND->getLocation(),
654                                   /*IsDecl=*/true,
655                                   {ND}});
656     }
657 
658     void VisitCXXDeductionGuideDecl(const CXXDeductionGuideDecl *DG) {
659       // The class template name in a deduction guide targets the class
660       // template.
661       Refs.push_back(ReferenceLoc{DG->getQualifierLoc(),
662                                   DG->getNameInfo().getLoc(),
663                                   /*IsDecl=*/false,
664                                   {DG->getDeducedTemplate()}});
665     }
666 
667     void VisitObjCMethodDecl(const ObjCMethodDecl *OMD) {
668       // The name may have several tokens, we can only report the first.
669       Refs.push_back(ReferenceLoc{NestedNameSpecifierLoc(),
670                                   OMD->getSelectorStartLoc(),
671                                   /*IsDecl=*/true,
672                                   {OMD}});
673     }
674 
675     void VisitObjCCategoryDecl(const ObjCCategoryDecl *OCD) {
676       // getLocation is the extended class's location, not the category's.
677       Refs.push_back(ReferenceLoc{NestedNameSpecifierLoc(),
678                                   OCD->getLocation(),
679                                   /*IsDecl=*/false,
680                                   {OCD->getClassInterface()}});
681       Refs.push_back(ReferenceLoc{NestedNameSpecifierLoc(),
682                                   OCD->getCategoryNameLoc(),
683                                   /*IsDecl=*/true,
684                                   {OCD}});
685     }
686 
687     void VisitObjCCategoryImplDecl(const ObjCCategoryImplDecl *OCID) {
688       Refs.push_back(ReferenceLoc{NestedNameSpecifierLoc(),
689                                   OCID->getLocation(),
690                                   /*IsDecl=*/false,
691                                   {OCID->getClassInterface()}});
692       Refs.push_back(ReferenceLoc{NestedNameSpecifierLoc(),
693                                   OCID->getCategoryNameLoc(),
694                                   /*IsDecl=*/true,
695                                   {OCID->getCategoryDecl()}});
696     }
697   };
698 
699   Visitor V{Resolver};
700   V.Visit(D);
701   return V.Refs;
702 }
703 
refInStmt(const Stmt * S,const HeuristicResolver * Resolver)704 llvm::SmallVector<ReferenceLoc> refInStmt(const Stmt *S,
705                                           const HeuristicResolver *Resolver) {
706   struct Visitor : ConstStmtVisitor<Visitor> {
707     Visitor(const HeuristicResolver *Resolver) : Resolver(Resolver) {}
708 
709     const HeuristicResolver *Resolver;
710     // FIXME: handle more complicated cases: more ObjC, designated initializers.
711     llvm::SmallVector<ReferenceLoc> Refs;
712 
713     void VisitConceptSpecializationExpr(const ConceptSpecializationExpr *E) {
714       Refs.push_back(ReferenceLoc{E->getNestedNameSpecifierLoc(),
715                                   E->getConceptNameLoc(),
716                                   /*IsDecl=*/false,
717                                   {E->getNamedConcept()}});
718     }
719 
720     void VisitDeclRefExpr(const DeclRefExpr *E) {
721       Refs.push_back(ReferenceLoc{E->getQualifierLoc(),
722                                   E->getNameInfo().getLoc(),
723                                   /*IsDecl=*/false,
724                                   {E->getFoundDecl()}});
725     }
726 
727     void VisitDependentScopeDeclRefExpr(const DependentScopeDeclRefExpr *E) {
728       Refs.push_back(ReferenceLoc{
729           E->getQualifierLoc(), E->getNameInfo().getLoc(), /*IsDecl=*/false,
730           explicitReferenceTargets(DynTypedNode::create(*E), {}, Resolver)});
731     }
732 
733     void VisitMemberExpr(const MemberExpr *E) {
734       // Skip destructor calls to avoid duplication: TypeLoc within will be
735       // visited separately.
736       if (llvm::isa<CXXDestructorDecl>(E->getFoundDecl().getDecl()))
737         return;
738       Refs.push_back(ReferenceLoc{E->getQualifierLoc(),
739                                   E->getMemberNameInfo().getLoc(),
740                                   /*IsDecl=*/false,
741                                   {E->getFoundDecl()}});
742     }
743 
744     void
745     VisitCXXDependentScopeMemberExpr(const CXXDependentScopeMemberExpr *E) {
746       Refs.push_back(ReferenceLoc{
747           E->getQualifierLoc(), E->getMemberNameInfo().getLoc(),
748           /*IsDecl=*/false,
749           explicitReferenceTargets(DynTypedNode::create(*E), {}, Resolver)});
750     }
751 
752     void VisitOverloadExpr(const OverloadExpr *E) {
753       Refs.push_back(ReferenceLoc{E->getQualifierLoc(),
754                                   E->getNameInfo().getLoc(),
755                                   /*IsDecl=*/false,
756                                   llvm::SmallVector<const NamedDecl *, 1>(
757                                       E->decls().begin(), E->decls().end())});
758     }
759 
760     void VisitSizeOfPackExpr(const SizeOfPackExpr *E) {
761       Refs.push_back(ReferenceLoc{NestedNameSpecifierLoc(),
762                                   E->getPackLoc(),
763                                   /*IsDecl=*/false,
764                                   {E->getPack()}});
765     }
766 
767     void VisitObjCPropertyRefExpr(const ObjCPropertyRefExpr *E) {
768       Refs.push_back(ReferenceLoc{
769           NestedNameSpecifierLoc(), E->getLocation(),
770           /*IsDecl=*/false,
771           // Select the getter, setter, or @property depending on the call.
772           explicitReferenceTargets(DynTypedNode::create(*E), {}, Resolver)});
773     }
774 
775     void VisitObjCIvarRefExpr(const ObjCIvarRefExpr *OIRE) {
776       Refs.push_back(ReferenceLoc{NestedNameSpecifierLoc(),
777                                   OIRE->getLocation(),
778                                   /*IsDecl=*/false,
779                                   {OIRE->getDecl()}});
780     }
781 
782     void VisitObjCMessageExpr(const ObjCMessageExpr *E) {
783       // The name may have several tokens, we can only report the first.
784       Refs.push_back(ReferenceLoc{NestedNameSpecifierLoc(),
785                                   E->getSelectorStartLoc(),
786                                   /*IsDecl=*/false,
787                                   {E->getMethodDecl()}});
788     }
789 
790     void VisitDesignatedInitExpr(const DesignatedInitExpr *DIE) {
791       for (const DesignatedInitExpr::Designator &D : DIE->designators()) {
792         if (!D.isFieldDesignator())
793           continue;
794 
795         Refs.push_back(ReferenceLoc{NestedNameSpecifierLoc(),
796                                     D.getFieldLoc(),
797                                     /*IsDecl=*/false,
798                                     {D.getField()}});
799       }
800     }
801 
802     void VisitGotoStmt(const GotoStmt *GS) {
803       Refs.push_back(ReferenceLoc{NestedNameSpecifierLoc(),
804                                   GS->getLabelLoc(),
805                                   /*IsDecl=*/false,
806                                   {GS->getLabel()}});
807     }
808 
809     void VisitLabelStmt(const LabelStmt *LS) {
810       Refs.push_back(ReferenceLoc{NestedNameSpecifierLoc(),
811                                   LS->getIdentLoc(),
812                                   /*IsDecl=*/true,
813                                   {LS->getDecl()}});
814     }
815   };
816 
817   Visitor V{Resolver};
818   V.Visit(S);
819   return V.Refs;
820 }
821 
822 llvm::SmallVector<ReferenceLoc>
refInTypeLoc(TypeLoc L,const HeuristicResolver * Resolver)823 refInTypeLoc(TypeLoc L, const HeuristicResolver *Resolver) {
824   struct Visitor : TypeLocVisitor<Visitor> {
825     Visitor(const HeuristicResolver *Resolver) : Resolver(Resolver) {}
826 
827     const HeuristicResolver *Resolver;
828     llvm::SmallVector<ReferenceLoc> Refs;
829 
830     void VisitElaboratedTypeLoc(ElaboratedTypeLoc L) {
831       // We only know about qualifier, rest if filled by inner locations.
832       size_t InitialSize = Refs.size();
833       Visit(L.getNamedTypeLoc().getUnqualifiedLoc());
834       size_t NewSize = Refs.size();
835       // Add qualifier for the newly-added refs.
836       for (unsigned I = InitialSize; I < NewSize; ++I) {
837         ReferenceLoc *Ref = &Refs[I];
838         // Fill in the qualifier.
839         assert(!Ref->Qualifier.hasQualifier() && "qualifier already set");
840         Ref->Qualifier = L.getQualifierLoc();
841       }
842     }
843 
844     void VisitUsingTypeLoc(UsingTypeLoc L) {
845       Refs.push_back(ReferenceLoc{NestedNameSpecifierLoc(),
846                                   L.getLocalSourceRange().getBegin(),
847                                   /*IsDecl=*/false,
848                                   {L.getFoundDecl()}});
849     }
850 
851     void VisitTagTypeLoc(TagTypeLoc L) {
852       Refs.push_back(ReferenceLoc{NestedNameSpecifierLoc(),
853                                   L.getNameLoc(),
854                                   /*IsDecl=*/false,
855                                   {L.getDecl()}});
856     }
857 
858     void VisitTemplateTypeParmTypeLoc(TemplateTypeParmTypeLoc L) {
859       Refs.push_back(ReferenceLoc{NestedNameSpecifierLoc(),
860                                   L.getNameLoc(),
861                                   /*IsDecl=*/false,
862                                   {L.getDecl()}});
863     }
864 
865     void VisitTemplateSpecializationTypeLoc(TemplateSpecializationTypeLoc L) {
866       // We must ensure template type aliases are included in results if they
867       // were written in the source code, e.g. in
868       //    template <class T> using valias = vector<T>;
869       //    ^valias<int> x;
870       // 'explicitReferenceTargets' will return:
871       //    1. valias with mask 'Alias'.
872       //    2. 'vector<int>' with mask 'Underlying'.
873       //  we want to return only #1 in this case.
874       Refs.push_back(ReferenceLoc{
875           NestedNameSpecifierLoc(), L.getTemplateNameLoc(), /*IsDecl=*/false,
876           explicitReferenceTargets(DynTypedNode::create(L.getType()),
877                                    DeclRelation::Alias, Resolver)});
878     }
879     void VisitDeducedTemplateSpecializationTypeLoc(
880         DeducedTemplateSpecializationTypeLoc L) {
881       Refs.push_back(ReferenceLoc{
882           NestedNameSpecifierLoc(), L.getNameLoc(), /*IsDecl=*/false,
883           explicitReferenceTargets(DynTypedNode::create(L.getType()),
884                                    DeclRelation::Alias, Resolver)});
885     }
886 
887     void VisitInjectedClassNameTypeLoc(InjectedClassNameTypeLoc TL) {
888       Refs.push_back(ReferenceLoc{NestedNameSpecifierLoc(),
889                                   TL.getNameLoc(),
890                                   /*IsDecl=*/false,
891                                   {TL.getDecl()}});
892     }
893 
894     void VisitDependentTemplateSpecializationTypeLoc(
895         DependentTemplateSpecializationTypeLoc L) {
896       Refs.push_back(
897           ReferenceLoc{L.getQualifierLoc(), L.getTemplateNameLoc(),
898                        /*IsDecl=*/false,
899                        explicitReferenceTargets(
900                            DynTypedNode::create(L.getType()), {}, Resolver)});
901     }
902 
903     void VisitDependentNameTypeLoc(DependentNameTypeLoc L) {
904       Refs.push_back(
905           ReferenceLoc{L.getQualifierLoc(), L.getNameLoc(),
906                        /*IsDecl=*/false,
907                        explicitReferenceTargets(
908                            DynTypedNode::create(L.getType()), {}, Resolver)});
909     }
910 
911     void VisitTypedefTypeLoc(TypedefTypeLoc L) {
912       if (shouldSkipTypedef(L.getTypedefNameDecl()))
913         return;
914       Refs.push_back(ReferenceLoc{NestedNameSpecifierLoc(),
915                                   L.getNameLoc(),
916                                   /*IsDecl=*/false,
917                                   {L.getTypedefNameDecl()}});
918     }
919 
920     void VisitObjCInterfaceTypeLoc(ObjCInterfaceTypeLoc L) {
921       Refs.push_back(ReferenceLoc{NestedNameSpecifierLoc(),
922                                   L.getNameLoc(),
923                                   /*IsDecl=*/false,
924                                   {L.getIFaceDecl()}});
925     }
926   };
927 
928   Visitor V{Resolver};
929   V.Visit(L.getUnqualifiedLoc());
930   return V.Refs;
931 }
932 
933 class ExplicitReferenceCollector
934     : public RecursiveASTVisitor<ExplicitReferenceCollector> {
935 public:
ExplicitReferenceCollector(llvm::function_ref<void (ReferenceLoc)> Out,const HeuristicResolver * Resolver)936   ExplicitReferenceCollector(llvm::function_ref<void(ReferenceLoc)> Out,
937                              const HeuristicResolver *Resolver)
938       : Out(Out), Resolver(Resolver) {
939     assert(Out);
940   }
941 
VisitTypeLoc(TypeLoc TTL)942   bool VisitTypeLoc(TypeLoc TTL) {
943     if (TypeLocsToSkip.count(TTL.getBeginLoc()))
944       return true;
945     visitNode(DynTypedNode::create(TTL));
946     return true;
947   }
948 
TraverseElaboratedTypeLoc(ElaboratedTypeLoc L)949   bool TraverseElaboratedTypeLoc(ElaboratedTypeLoc L) {
950     // ElaboratedTypeLoc will reports information for its inner type loc.
951     // Otherwise we loose information about inner types loc's qualifier.
952     TypeLoc Inner = L.getNamedTypeLoc().getUnqualifiedLoc();
953     TypeLocsToSkip.insert(Inner.getBeginLoc());
954     return RecursiveASTVisitor::TraverseElaboratedTypeLoc(L);
955   }
956 
VisitStmt(Stmt * S)957   bool VisitStmt(Stmt *S) {
958     visitNode(DynTypedNode::create(*S));
959     return true;
960   }
961 
TraverseOpaqueValueExpr(OpaqueValueExpr * OVE)962   bool TraverseOpaqueValueExpr(OpaqueValueExpr *OVE) {
963     visitNode(DynTypedNode::create(*OVE));
964     // Not clear why the source expression is skipped by default...
965     // FIXME: can we just make RecursiveASTVisitor do this?
966     return RecursiveASTVisitor::TraverseStmt(OVE->getSourceExpr());
967   }
968 
TraversePseudoObjectExpr(PseudoObjectExpr * POE)969   bool TraversePseudoObjectExpr(PseudoObjectExpr *POE) {
970     visitNode(DynTypedNode::create(*POE));
971     // Traverse only the syntactic form to find the *written* references.
972     // (The semantic form also contains lots of duplication)
973     return RecursiveASTVisitor::TraverseStmt(POE->getSyntacticForm());
974   }
975 
976   // We re-define Traverse*, since there's no corresponding Visit*.
977   // TemplateArgumentLoc is the only way to get locations for references to
978   // template template parameters.
TraverseTemplateArgumentLoc(TemplateArgumentLoc A)979   bool TraverseTemplateArgumentLoc(TemplateArgumentLoc A) {
980     switch (A.getArgument().getKind()) {
981     case TemplateArgument::Template:
982     case TemplateArgument::TemplateExpansion:
983       reportReference(ReferenceLoc{A.getTemplateQualifierLoc(),
984                                    A.getTemplateNameLoc(),
985                                    /*IsDecl=*/false,
986                                    {A.getArgument()
987                                         .getAsTemplateOrTemplatePattern()
988                                         .getAsTemplateDecl()}},
989                       DynTypedNode::create(A.getArgument()));
990       break;
991     case TemplateArgument::Declaration:
992       break; // FIXME: can this actually happen in TemplateArgumentLoc?
993     case TemplateArgument::Integral:
994     case TemplateArgument::Null:
995     case TemplateArgument::NullPtr:
996       break; // no references.
997     case TemplateArgument::Pack:
998     case TemplateArgument::Type:
999     case TemplateArgument::Expression:
1000       break; // Handled by VisitType and VisitExpression.
1001     };
1002     return RecursiveASTVisitor::TraverseTemplateArgumentLoc(A);
1003   }
1004 
VisitDecl(Decl * D)1005   bool VisitDecl(Decl *D) {
1006     visitNode(DynTypedNode::create(*D));
1007     return true;
1008   }
1009 
1010   // We have to use Traverse* because there is no corresponding Visit*.
TraverseNestedNameSpecifierLoc(NestedNameSpecifierLoc L)1011   bool TraverseNestedNameSpecifierLoc(NestedNameSpecifierLoc L) {
1012     if (!L.getNestedNameSpecifier())
1013       return true;
1014     visitNode(DynTypedNode::create(L));
1015     // Inner type is missing information about its qualifier, skip it.
1016     if (auto TL = L.getTypeLoc())
1017       TypeLocsToSkip.insert(TL.getBeginLoc());
1018     return RecursiveASTVisitor::TraverseNestedNameSpecifierLoc(L);
1019   }
1020 
TraverseObjCProtocolLoc(ObjCProtocolLoc ProtocolLoc)1021   bool TraverseObjCProtocolLoc(ObjCProtocolLoc ProtocolLoc) {
1022     visitNode(DynTypedNode::create(ProtocolLoc));
1023     return true;
1024   }
1025 
TraverseConstructorInitializer(CXXCtorInitializer * Init)1026   bool TraverseConstructorInitializer(CXXCtorInitializer *Init) {
1027     visitNode(DynTypedNode::create(*Init));
1028     return RecursiveASTVisitor::TraverseConstructorInitializer(Init);
1029   }
1030 
1031 private:
1032   /// Obtain information about a reference directly defined in \p N. Does not
1033   /// recurse into child nodes, e.g. do not expect references for constructor
1034   /// initializers
1035   ///
1036   /// Any of the fields in the returned structure can be empty, but not all of
1037   /// them, e.g.
1038   ///   - for implicitly generated nodes (e.g. MemberExpr from range-based-for),
1039   ///     source location information may be missing,
1040   ///   - for dependent code, targets may be empty.
1041   ///
1042   /// (!) For the purposes of this function declarations are not considered to
1043   ///     be references. However, declarations can have references inside them,
1044   ///     e.g. 'namespace foo = std' references namespace 'std' and this
1045   ///     function will return the corresponding reference.
explicitReference(DynTypedNode N)1046   llvm::SmallVector<ReferenceLoc> explicitReference(DynTypedNode N) {
1047     if (auto *D = N.get<Decl>())
1048       return refInDecl(D, Resolver);
1049     if (auto *S = N.get<Stmt>())
1050       return refInStmt(S, Resolver);
1051     if (auto *NNSL = N.get<NestedNameSpecifierLoc>()) {
1052       // (!) 'DeclRelation::Alias' ensures we do not loose namespace aliases.
1053       return {ReferenceLoc{
1054           NNSL->getPrefix(), NNSL->getLocalBeginLoc(), false,
1055           explicitReferenceTargets(
1056               DynTypedNode::create(*NNSL->getNestedNameSpecifier()),
1057               DeclRelation::Alias, Resolver)}};
1058     }
1059     if (const TypeLoc *TL = N.get<TypeLoc>())
1060       return refInTypeLoc(*TL, Resolver);
1061     if (const CXXCtorInitializer *CCI = N.get<CXXCtorInitializer>()) {
1062       // Other type initializers (e.g. base initializer) are handled by visiting
1063       // the typeLoc.
1064       if (CCI->isAnyMemberInitializer()) {
1065         return {ReferenceLoc{NestedNameSpecifierLoc(),
1066                              CCI->getMemberLocation(),
1067                              /*IsDecl=*/false,
1068                              {CCI->getAnyMember()}}};
1069       }
1070     }
1071     if (const ObjCProtocolLoc *PL = N.get<ObjCProtocolLoc>())
1072       return {ReferenceLoc{NestedNameSpecifierLoc(),
1073                            PL->getLocation(),
1074                            /*IsDecl=*/false,
1075                            {PL->getProtocol()}}};
1076 
1077     // We do not have location information for other nodes (QualType, etc)
1078     return {};
1079   }
1080 
visitNode(DynTypedNode N)1081   void visitNode(DynTypedNode N) {
1082     for (auto &R : explicitReference(N))
1083       reportReference(std::move(R), N);
1084   }
1085 
reportReference(ReferenceLoc && Ref,DynTypedNode N)1086   void reportReference(ReferenceLoc &&Ref, DynTypedNode N) {
1087     // Strip null targets that can arise from invalid code.
1088     // (This avoids having to check for null everywhere we insert)
1089     llvm::erase_value(Ref.Targets, nullptr);
1090     // Our promise is to return only references from the source code. If we lack
1091     // location information, skip these nodes.
1092     // Normally this should not happen in practice, unless there are bugs in the
1093     // traversals or users started the traversal at an implicit node.
1094     if (Ref.NameLoc.isInvalid()) {
1095       dlog("invalid location at node {0}", nodeToString(N));
1096       return;
1097     }
1098     Out(Ref);
1099   }
1100 
1101   llvm::function_ref<void(ReferenceLoc)> Out;
1102   const HeuristicResolver *Resolver;
1103   /// TypeLocs starting at these locations must be skipped, see
1104   /// TraverseElaboratedTypeSpecifierLoc for details.
1105   llvm::DenseSet<SourceLocation> TypeLocsToSkip;
1106 };
1107 } // namespace
1108 
findExplicitReferences(const Stmt * S,llvm::function_ref<void (ReferenceLoc)> Out,const HeuristicResolver * Resolver)1109 void findExplicitReferences(const Stmt *S,
1110                             llvm::function_ref<void(ReferenceLoc)> Out,
1111                             const HeuristicResolver *Resolver) {
1112   assert(S);
1113   ExplicitReferenceCollector(Out, Resolver).TraverseStmt(const_cast<Stmt *>(S));
1114 }
findExplicitReferences(const Decl * D,llvm::function_ref<void (ReferenceLoc)> Out,const HeuristicResolver * Resolver)1115 void findExplicitReferences(const Decl *D,
1116                             llvm::function_ref<void(ReferenceLoc)> Out,
1117                             const HeuristicResolver *Resolver) {
1118   assert(D);
1119   ExplicitReferenceCollector(Out, Resolver).TraverseDecl(const_cast<Decl *>(D));
1120 }
findExplicitReferences(const ASTContext & AST,llvm::function_ref<void (ReferenceLoc)> Out,const HeuristicResolver * Resolver)1121 void findExplicitReferences(const ASTContext &AST,
1122                             llvm::function_ref<void(ReferenceLoc)> Out,
1123                             const HeuristicResolver *Resolver) {
1124   ExplicitReferenceCollector(Out, Resolver)
1125       .TraverseAST(const_cast<ASTContext &>(AST));
1126 }
1127 
operator <<(llvm::raw_ostream & OS,DeclRelation R)1128 llvm::raw_ostream &operator<<(llvm::raw_ostream &OS, DeclRelation R) {
1129   switch (R) {
1130 #define REL_CASE(X)                                                            \
1131   case DeclRelation::X:                                                        \
1132     return OS << #X;
1133     REL_CASE(Alias);
1134     REL_CASE(Underlying);
1135     REL_CASE(TemplateInstantiation);
1136     REL_CASE(TemplatePattern);
1137 #undef REL_CASE
1138   }
1139   llvm_unreachable("Unhandled DeclRelation enum");
1140 }
operator <<(llvm::raw_ostream & OS,DeclRelationSet RS)1141 llvm::raw_ostream &operator<<(llvm::raw_ostream &OS, DeclRelationSet RS) {
1142   const char *Sep = "";
1143   for (unsigned I = 0; I < RS.S.size(); ++I) {
1144     if (RS.S.test(I)) {
1145       OS << Sep << static_cast<DeclRelation>(I);
1146       Sep = "|";
1147     }
1148   }
1149   return OS;
1150 }
1151 
operator <<(llvm::raw_ostream & OS,ReferenceLoc R)1152 llvm::raw_ostream &operator<<(llvm::raw_ostream &OS, ReferenceLoc R) {
1153   // note we cannot print R.NameLoc without a source manager.
1154   OS << "targets = {";
1155   llvm::SmallVector<std::string> Targets;
1156   for (const NamedDecl *T : R.Targets) {
1157     llvm::raw_string_ostream Target(Targets.emplace_back());
1158     Target << printQualifiedName(*T) << printTemplateSpecializationArgs(*T);
1159   }
1160   llvm::sort(Targets);
1161   OS << llvm::join(Targets, ", ");
1162   OS << "}";
1163   if (R.Qualifier) {
1164     OS << ", qualifier = '";
1165     R.Qualifier.getNestedNameSpecifier()->print(OS,
1166                                                 PrintingPolicy(LangOptions()));
1167     OS << "'";
1168   }
1169   if (R.IsDecl)
1170     OS << ", decl";
1171   return OS;
1172 }
1173 
1174 } // namespace clangd
1175 } // namespace clang
1176