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/DeclCXX.h"
14 #include "clang/AST/DeclTemplate.h"
15 #include "clang/AST/DeclVisitor.h"
16 #include "clang/AST/DeclarationName.h"
17 #include "clang/AST/ExprObjC.h"
18 #include "clang/AST/StmtVisitor.h"
19 #include "clang/AST/Type.h"
20 #include "clang/AST/TypeLocVisitor.h"
21 #include "clang/Basic/SourceLocation.h"
22 #include "llvm/Support/Casting.h"
23 #include "llvm/Support/Compiler.h"
24 #include "llvm/Support/raw_ostream.h"
25 
26 namespace clang {
27 namespace clangd {
28 namespace {
29 
30 LLVM_ATTRIBUTE_UNUSED std::string
31 nodeToString(const ast_type_traits::DynTypedNode &N) {
32   std::string S = N.getNodeKind().asStringRef();
33   {
34     llvm::raw_string_ostream OS(S);
35     OS << ": ";
36     N.print(OS, PrintingPolicy(LangOptions()));
37   }
38   std::replace(S.begin(), S.end(), '\n', ' ');
39   return S;
40 }
41 
42 // TargetFinder locates the entities that an AST node refers to.
43 //
44 // Typically this is (possibly) one declaration and (possibly) one type, but
45 // may be more:
46 //  - for ambiguous nodes like OverloadExpr
47 //  - if we want to include e.g. both typedefs and the underlying type
48 //
49 // This is organized as a set of mutually recursive helpers for particular node
50 // types, but for most nodes this is a short walk rather than a deep traversal.
51 //
52 // It's tempting to do e.g. typedef resolution as a second normalization step,
53 // after finding the 'primary' decl etc. But we do this monolithically instead
54 // because:
55 //  - normalization may require these traversals again (e.g. unwrapping a
56 //    typedef reveals a decltype which must be traversed)
57 //  - it doesn't simplify that much, e.g. the first stage must still be able
58 //    to yield multiple decls to handle OverloadExpr
59 //  - there are cases where it's required for correctness. e.g:
60 //      template<class X> using pvec = vector<x*>; pvec<int> x;
61 //    There's no Decl `pvec<int>`, we must choose `pvec<X>` or `vector<int*>`
62 //    and both are lossy. We must know upfront what the caller ultimately wants.
63 //
64 // FIXME: improve common dependent scope using name lookup in primary templates.
65 // e.g. template<typename T> int foo() { return std::vector<T>().size(); }
66 // formally size() is unresolved, but the primary template is a good guess.
67 // This affects:
68 //  - DependentTemplateSpecializationType,
69 //  - DependentScopeMemberExpr
70 //  - DependentScopeDeclRefExpr
71 //  - DependentNameType
72 struct TargetFinder {
73   using RelSet = DeclRelationSet;
74   using Rel = DeclRelation;
75   llvm::SmallDenseMap<const Decl *, RelSet> Decls;
76   RelSet Flags;
77 
78   static const Decl *getTemplatePattern(const Decl *D) {
79     if (const CXXRecordDecl *CRD = dyn_cast<CXXRecordDecl>(D)) {
80       return CRD->getTemplateInstantiationPattern();
81     } else if (const FunctionDecl *FD = dyn_cast<FunctionDecl>(D)) {
82       return FD->getTemplateInstantiationPattern();
83     } else if (auto *VD = dyn_cast<VarDecl>(D)) {
84       // Hmm: getTIP returns its arg if it's not an instantiation?!
85       VarDecl *T = VD->getTemplateInstantiationPattern();
86       return (T == D) ? nullptr : T;
87     } else if (const auto *ED = dyn_cast<EnumDecl>(D)) {
88       return ED->getInstantiatedFromMemberEnum();
89     } else if (isa<FieldDecl>(D) || isa<TypedefNameDecl>(D)) {
90       const auto *ND = cast<NamedDecl>(D);
91       if (const DeclContext *Parent = dyn_cast_or_null<DeclContext>(
92               getTemplatePattern(llvm::cast<Decl>(ND->getDeclContext()))))
93         for (const NamedDecl *BaseND : Parent->lookup(ND->getDeclName()))
94           if (!BaseND->isImplicit() && BaseND->getKind() == ND->getKind())
95             return BaseND;
96     } else if (const auto *ECD = dyn_cast<EnumConstantDecl>(D)) {
97       if (const auto *ED = dyn_cast<EnumDecl>(ECD->getDeclContext())) {
98         if (const EnumDecl *Pattern = ED->getInstantiatedFromMemberEnum()) {
99           for (const NamedDecl *BaseECD : Pattern->lookup(ECD->getDeclName()))
100             return BaseECD;
101         }
102       }
103     }
104     return nullptr;
105   }
106 
107   template <typename T> void debug(T &Node, RelSet Flags) {
108     dlog("visit [{0}] {1}", Flags,
109          nodeToString(ast_type_traits::DynTypedNode::create(Node)));
110   }
111 
112   void report(const Decl *D, RelSet Flags) {
113     dlog("--> [{0}] {1}", Flags,
114          nodeToString(ast_type_traits::DynTypedNode::create(*D)));
115     Decls[D] |= Flags;
116   }
117 
118 public:
119   void add(const Decl *D, RelSet Flags) {
120     if (!D)
121       return;
122     debug(*D, Flags);
123     if (const UsingDirectiveDecl *UDD = llvm::dyn_cast<UsingDirectiveDecl>(D))
124       D = UDD->getNominatedNamespaceAsWritten();
125 
126     if (const TypedefNameDecl *TND = dyn_cast<TypedefNameDecl>(D)) {
127       add(TND->getUnderlyingType(), Flags | Rel::Underlying);
128       Flags |= Rel::Alias; // continue with the alias.
129     } else if (const UsingDecl *UD = dyn_cast<UsingDecl>(D)) {
130       for (const UsingShadowDecl *S : UD->shadows())
131         add(S->getUnderlyingDecl(), Flags | Rel::Underlying);
132       Flags |= Rel::Alias; // continue with the alias.
133     } else if (const auto *NAD = dyn_cast<NamespaceAliasDecl>(D)) {
134       add(NAD->getUnderlyingDecl(), Flags | Rel::Underlying);
135       Flags |= Rel::Alias; // continue with the alias
136     } else if (const UsingShadowDecl *USD = dyn_cast<UsingShadowDecl>(D)) {
137       // Include the using decl, but don't traverse it. This may end up
138       // including *all* shadows, which we don't want.
139       report(USD->getUsingDecl(), Flags | Rel::Alias);
140       // Shadow decls are synthetic and not themselves interesting.
141       // Record the underlying decl instead, if allowed.
142       D = USD->getTargetDecl();
143       Flags |= Rel::Underlying; // continue with the underlying decl.
144     }
145 
146     if (const Decl *Pat = getTemplatePattern(D)) {
147       assert(Pat != D);
148       add(Pat, Flags | Rel::TemplatePattern);
149       // Now continue with the instantiation.
150       Flags |= Rel::TemplateInstantiation;
151     }
152 
153     report(D, Flags);
154   }
155 
156   void add(const Stmt *S, RelSet Flags) {
157     if (!S)
158       return;
159     debug(*S, Flags);
160     struct Visitor : public ConstStmtVisitor<Visitor> {
161       TargetFinder &Outer;
162       RelSet Flags;
163       Visitor(TargetFinder &Outer, RelSet Flags) : Outer(Outer), Flags(Flags) {}
164 
165       void VisitDeclRefExpr(const DeclRefExpr *DRE) {
166         const Decl *D = DRE->getDecl();
167         // UsingShadowDecl allows us to record the UsingDecl.
168         // getFoundDecl() returns the wrong thing in other cases (templates).
169         if (auto *USD = llvm::dyn_cast<UsingShadowDecl>(DRE->getFoundDecl()))
170           D = USD;
171         Outer.add(D, Flags);
172       }
173       void VisitMemberExpr(const MemberExpr *ME) {
174         const Decl *D = ME->getMemberDecl();
175         if (auto *USD =
176                 llvm::dyn_cast<UsingShadowDecl>(ME->getFoundDecl().getDecl()))
177           D = USD;
178         Outer.add(D, Flags);
179       }
180       void VisitCXXConstructExpr(const CXXConstructExpr *CCE) {
181         Outer.add(CCE->getConstructor(), Flags);
182       }
183       void VisitDesignatedInitExpr(const DesignatedInitExpr *DIE) {
184         for (const DesignatedInitExpr::Designator &D :
185              llvm::reverse(DIE->designators()))
186           if (D.isFieldDesignator()) {
187             Outer.add(D.getField(), Flags);
188             // We don't know which designator was intended, we assume the outer.
189             break;
190           }
191       }
192       void VisitObjCIvarRefExpr(const ObjCIvarRefExpr *OIRE) {
193         Outer.add(OIRE->getDecl(), Flags);
194       }
195       void VisitObjCMessageExpr(const ObjCMessageExpr *OME) {
196         Outer.add(OME->getMethodDecl(), Flags);
197       }
198       void VisitObjCPropertyRefExpr(const ObjCPropertyRefExpr *OPRE) {
199         if (OPRE->isExplicitProperty())
200           Outer.add(OPRE->getExplicitProperty(), Flags);
201         else {
202           if (OPRE->isMessagingGetter())
203             Outer.add(OPRE->getImplicitPropertyGetter(), Flags);
204           if (OPRE->isMessagingSetter())
205             Outer.add(OPRE->getImplicitPropertySetter(), Flags);
206         }
207       }
208       void VisitObjCProtocolExpr(const ObjCProtocolExpr *OPE) {
209         Outer.add(OPE->getProtocol(), Flags);
210       }
211     };
212     Visitor(*this, Flags).Visit(S);
213   }
214 
215   void add(QualType T, RelSet Flags) {
216     if (T.isNull())
217       return;
218     debug(T, Flags);
219     struct Visitor : public TypeVisitor<Visitor> {
220       TargetFinder &Outer;
221       RelSet Flags;
222       Visitor(TargetFinder &Outer, RelSet Flags) : Outer(Outer), Flags(Flags) {}
223 
224       void VisitTagType(const TagType *TT) {
225         Outer.add(TT->getAsTagDecl(), Flags);
226       }
227       void VisitDecltypeType(const DecltypeType *DTT) {
228         Outer.add(DTT->getUnderlyingType(), Flags | Rel::Underlying);
229       }
230       void VisitDeducedType(const DeducedType *DT) {
231         // FIXME: In practice this doesn't work: the AutoType you find inside
232         // TypeLoc never has a deduced type. https://llvm.org/PR42914
233         Outer.add(DT->getDeducedType(), Flags | Rel::Underlying);
234       }
235       void VisitTypedefType(const TypedefType *TT) {
236         Outer.add(TT->getDecl(), Flags);
237       }
238       void
239       VisitTemplateSpecializationType(const TemplateSpecializationType *TST) {
240         // Have to handle these case-by-case.
241 
242         // templated type aliases: there's no specialized/instantiated using
243         // decl to point to. So try to find a decl for the underlying type
244         // (after substitution), and failing that point to the (templated) using
245         // decl.
246         if (TST->isTypeAlias()) {
247           Outer.add(TST->getAliasedType(), Flags | Rel::Underlying);
248           // Don't *traverse* the alias, which would result in traversing the
249           // template of the underlying type.
250           Outer.report(
251               TST->getTemplateName().getAsTemplateDecl()->getTemplatedDecl(),
252               Flags | Rel::Alias | Rel::TemplatePattern);
253         }
254         // specializations of template template parameters aren't instantiated
255         // into decls, so they must refer to the parameter itself.
256         else if (const auto *Parm =
257                      llvm::dyn_cast_or_null<TemplateTemplateParmDecl>(
258                          TST->getTemplateName().getAsTemplateDecl()))
259           Outer.add(Parm, Flags);
260         // class template specializations have a (specialized) CXXRecordDecl.
261         else if (const CXXRecordDecl *RD = TST->getAsCXXRecordDecl())
262           Outer.add(RD, Flags); // add(Decl) will despecialize if needed.
263         else {
264           // fallback: the (un-specialized) declaration from primary template.
265           if (auto *TD = TST->getTemplateName().getAsTemplateDecl())
266             Outer.add(TD->getTemplatedDecl(), Flags | Rel::TemplatePattern);
267         }
268       }
269       void VisitTemplateTypeParmType(const TemplateTypeParmType *TTPT) {
270         Outer.add(TTPT->getDecl(), Flags);
271       }
272       void VisitObjCInterfaceType(const ObjCInterfaceType *OIT) {
273         Outer.add(OIT->getDecl(), Flags);
274       }
275       void VisitObjCObjectType(const ObjCObjectType *OOT) {
276         // FIXME: ObjCObjectTypeLoc has no children for the protocol list, so
277         // there is no node in id<Foo> that refers to ObjCProtocolDecl Foo.
278         if (OOT->isObjCQualifiedId() && OOT->getNumProtocols() == 1)
279           Outer.add(OOT->getProtocol(0), Flags);
280       }
281     };
282     Visitor(*this, Flags).Visit(T.getTypePtr());
283   }
284 
285   void add(const NestedNameSpecifier *NNS, RelSet Flags) {
286     if (!NNS)
287       return;
288     debug(*NNS, Flags);
289     switch (NNS->getKind()) {
290     case NestedNameSpecifier::Identifier:
291       return;
292     case NestedNameSpecifier::Namespace:
293       add(NNS->getAsNamespace(), Flags);
294       return;
295     case NestedNameSpecifier::NamespaceAlias:
296       add(NNS->getAsNamespaceAlias(), Flags);
297       return;
298     case NestedNameSpecifier::TypeSpec:
299     case NestedNameSpecifier::TypeSpecWithTemplate:
300       add(QualType(NNS->getAsType(), 0), Flags);
301       return;
302     case NestedNameSpecifier::Global:
303       // This should be TUDecl, but we can't get a pointer to it!
304       return;
305     case NestedNameSpecifier::Super:
306       add(NNS->getAsRecordDecl(), Flags);
307       return;
308     }
309     llvm_unreachable("unhandled NestedNameSpecifier::SpecifierKind");
310   }
311 
312   void add(const CXXCtorInitializer *CCI, RelSet Flags) {
313     if (!CCI)
314       return;
315     debug(*CCI, Flags);
316 
317     if (CCI->isAnyMemberInitializer())
318       add(CCI->getAnyMember(), Flags);
319     // Constructor calls contain a TypeLoc node, so we don't handle them here.
320   }
321 };
322 
323 } // namespace
324 
325 llvm::SmallVector<std::pair<const Decl *, DeclRelationSet>, 1>
326 allTargetDecls(const ast_type_traits::DynTypedNode &N) {
327   dlog("allTargetDecls({0})", nodeToString(N));
328   TargetFinder Finder;
329   DeclRelationSet Flags;
330   if (const Decl *D = N.get<Decl>())
331     Finder.add(D, Flags);
332   else if (const Stmt *S = N.get<Stmt>())
333     Finder.add(S, Flags);
334   else if (const NestedNameSpecifierLoc *NNSL = N.get<NestedNameSpecifierLoc>())
335     Finder.add(NNSL->getNestedNameSpecifier(), Flags);
336   else if (const NestedNameSpecifier *NNS = N.get<NestedNameSpecifier>())
337     Finder.add(NNS, Flags);
338   else if (const TypeLoc *TL = N.get<TypeLoc>())
339     Finder.add(TL->getType(), Flags);
340   else if (const QualType *QT = N.get<QualType>())
341     Finder.add(*QT, Flags);
342   else if (const CXXCtorInitializer *CCI = N.get<CXXCtorInitializer>())
343     Finder.add(CCI, Flags);
344 
345   return {Finder.Decls.begin(), Finder.Decls.end()};
346 }
347 
348 llvm::SmallVector<const Decl *, 1>
349 targetDecl(const ast_type_traits::DynTypedNode &N, DeclRelationSet Mask) {
350   llvm::SmallVector<const Decl *, 1> Result;
351   for (const auto &Entry : allTargetDecls(N))
352     if (!(Entry.second & ~Mask))
353       Result.push_back(Entry.first);
354   return Result;
355 }
356 
357 llvm::raw_ostream &operator<<(llvm::raw_ostream &OS, DeclRelation R) {
358   switch (R) {
359 #define REL_CASE(X)                                                            \
360   case DeclRelation::X:                                                        \
361     return OS << #X;
362     REL_CASE(Alias);
363     REL_CASE(Underlying);
364     REL_CASE(TemplateInstantiation);
365     REL_CASE(TemplatePattern);
366 #undef REL_CASE
367   }
368   llvm_unreachable("Unhandled DeclRelation enum");
369 }
370 llvm::raw_ostream &operator<<(llvm::raw_ostream &OS, DeclRelationSet RS) {
371   const char *Sep = "";
372   for (unsigned I = 0; I < RS.S.size(); ++I) {
373     if (RS.S.test(I)) {
374       OS << Sep << static_cast<DeclRelation>(I);
375       Sep = "|";
376     }
377   }
378   return OS;
379 }
380 
381 } // namespace clangd
382 } // namespace clang
383