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