llvm-project

1
//===--- FindTarget.cpp - What does an AST node refer to? -----------------===//
2
//
3
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4
// See https://llvm.org/LICENSE.txt for license information.
5
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6
//
7
//===----------------------------------------------------------------------===//
8

9
#include "FindTarget.h"
10
#include "AST.h"
11
#include "HeuristicResolver.h"
12
#include "support/Logger.h"
13
#include "clang/AST/ASTConcept.h"
14
#include "clang/AST/ASTTypeTraits.h"
15
#include "clang/AST/Decl.h"
16
#include "clang/AST/DeclBase.h"
17
#include "clang/AST/DeclCXX.h"
18
#include "clang/AST/DeclTemplate.h"
19
#include "clang/AST/DeclVisitor.h"
20
#include "clang/AST/DeclarationName.h"
21
#include "clang/AST/Expr.h"
22
#include "clang/AST/ExprCXX.h"
23
#include "clang/AST/ExprConcepts.h"
24
#include "clang/AST/ExprObjC.h"
25
#include "clang/AST/NestedNameSpecifier.h"
26
#include "clang/AST/PrettyPrinter.h"
27
#include "clang/AST/RecursiveASTVisitor.h"
28
#include "clang/AST/StmtVisitor.h"
29
#include "clang/AST/TemplateBase.h"
30
#include "clang/AST/Type.h"
31
#include "clang/AST/TypeLoc.h"
32
#include "clang/AST/TypeLocVisitor.h"
33
#include "clang/AST/TypeVisitor.h"
34
#include "clang/Basic/LangOptions.h"
35
#include "clang/Basic/SourceLocation.h"
36
#include "clang/Basic/SourceManager.h"
37
#include "clang/Basic/Specifiers.h"
38
#include "llvm/ADT/STLExtras.h"
39
#include "llvm/ADT/SmallVector.h"
40
#include "llvm/ADT/StringExtras.h"
41
#include "llvm/Support/Casting.h"
42
#include "llvm/Support/Compiler.h"
43
#include "llvm/Support/raw_ostream.h"
44
#include <iterator>
45
#include <string>
46
#include <utility>
47
#include <vector>
48

49
namespace clang {
50
namespace clangd {
51
namespace {
52

53
LLVM_ATTRIBUTE_UNUSED std::string nodeToString(const DynTypedNode &N) {
54
  std::string S = std::string(N.getNodeKind().asStringRef());
55
  {
56
    llvm::raw_string_ostream OS(S);
57
    OS << ": ";
58
    N.print(OS, PrintingPolicy(LangOptions()));
59
  }
60
  std::replace(S.begin(), S.end(), '\n', ' ');
61
  return S;
62
}
63

64
const NamedDecl *getTemplatePattern(const NamedDecl *D) {
65
  if (const CXXRecordDecl *CRD = dyn_cast<CXXRecordDecl>(D)) {
66
    if (const auto *Result = CRD->getTemplateInstantiationPattern())
67
      return Result;
68
    // getTemplateInstantiationPattern returns null if the Specialization is
69
    // incomplete (e.g. the type didn't need to be complete), fall back to the
70
    // primary template.
71
    if (CRD->getTemplateSpecializationKind() == TSK_Undeclared)
72
      if (const auto *Spec = dyn_cast<ClassTemplateSpecializationDecl>(CRD))
73
        return Spec->getSpecializedTemplate()->getTemplatedDecl();
74
  } else if (const FunctionDecl *FD = dyn_cast<FunctionDecl>(D)) {
75
    return FD->getTemplateInstantiationPattern();
76
  } else if (auto *VD = dyn_cast<VarDecl>(D)) {
77
    // Hmm: getTIP returns its arg if it's not an instantiation?!
78
    VarDecl *T = VD->getTemplateInstantiationPattern();
79
    return (T == D) ? nullptr : T;
80
  } else if (const auto *ED = dyn_cast<EnumDecl>(D)) {
81
    return ED->getInstantiatedFromMemberEnum();
82
  } else if (isa<FieldDecl>(D) || isa<TypedefNameDecl>(D)) {
83
    if (const auto *Parent = llvm::dyn_cast<NamedDecl>(D->getDeclContext()))
84
      if (const DeclContext *ParentPat =
85
              dyn_cast_or_null<DeclContext>(getTemplatePattern(Parent)))
86
        for (const NamedDecl *BaseND : ParentPat->lookup(D->getDeclName()))
87
          if (!BaseND->isImplicit() && BaseND->getKind() == D->getKind())
88
            return BaseND;
89
  } else if (const auto *ECD = dyn_cast<EnumConstantDecl>(D)) {
90
    if (const auto *ED = dyn_cast<EnumDecl>(ECD->getDeclContext())) {
91
      if (const EnumDecl *Pattern = ED->getInstantiatedFromMemberEnum()) {
92
        for (const NamedDecl *BaseECD : Pattern->lookup(ECD->getDeclName()))
93
          return BaseECD;
94
      }
95
    }
96
  }
97
  return nullptr;
98
}
99

100
// Returns true if the `TypedefNameDecl` should not be reported.
101
bool shouldSkipTypedef(const TypedefNameDecl *TD) {
102
  // These should be treated as keywords rather than decls - the typedef is an
103
  // odd implementation detail.
104
  if (TD == TD->getASTContext().getObjCInstanceTypeDecl() ||
105
      TD == TD->getASTContext().getObjCIdDecl())
106
    return true;
107
  return false;
108
}
109

110
// TargetFinder locates the entities that an AST node refers to.
111
//
112
// Typically this is (possibly) one declaration and (possibly) one type, but
113
// may be more:
114
//  - for ambiguous nodes like OverloadExpr
115
//  - if we want to include e.g. both typedefs and the underlying type
116
//
117
// This is organized as a set of mutually recursive helpers for particular node
118
// types, but for most nodes this is a short walk rather than a deep traversal.
119
//
120
// It's tempting to do e.g. typedef resolution as a second normalization step,
121
// after finding the 'primary' decl etc. But we do this monolithically instead
122
// because:
123
//  - normalization may require these traversals again (e.g. unwrapping a
124
//    typedef reveals a decltype which must be traversed)
125
//  - it doesn't simplify that much, e.g. the first stage must still be able
126
//    to yield multiple decls to handle OverloadExpr
127
//  - there are cases where it's required for correctness. e.g:
128
//      template<class X> using pvec = vector<x*>; pvec<int> x;
129
//    There's no Decl `pvec<int>`, we must choose `pvec<X>` or `vector<int*>`
130
//    and both are lossy. We must know upfront what the caller ultimately wants.
131
struct TargetFinder {
132
  using RelSet = DeclRelationSet;
133
  using Rel = DeclRelation;
134

135
private:
136
  const HeuristicResolver *Resolver;
137
  llvm::SmallDenseMap<const NamedDecl *,
138
                      std::pair<RelSet, /*InsertionOrder*/ size_t>>
139
      Decls;
140
  llvm::SmallDenseMap<const Decl *, RelSet> Seen;
141
  RelSet Flags;
142

143
  template <typename T> void debug(T &Node, RelSet Flags) {
144
    dlog("visit [{0}] {1}", Flags, nodeToString(DynTypedNode::create(Node)));
145
  }
146

147
  void report(const NamedDecl *D, RelSet Flags) {
148
    dlog("--> [{0}] {1}", Flags, nodeToString(DynTypedNode::create(*D)));
149
    auto It = Decls.try_emplace(D, std::make_pair(Flags, Decls.size()));
150
    // If already exists, update the flags.
151
    if (!It.second)
152
      It.first->second.first |= Flags;
153
  }
154

155
public:
156
  TargetFinder(const HeuristicResolver *Resolver) : Resolver(Resolver) {}
157

158
  llvm::SmallVector<std::pair<const NamedDecl *, RelSet>, 1> takeDecls() const {
159
    using ValTy = std::pair<const NamedDecl *, RelSet>;
160
    llvm::SmallVector<ValTy, 1> Result;
161
    Result.resize(Decls.size());
162
    for (const auto &Elem : Decls)
163
      Result[Elem.second.second] = {Elem.first, Elem.second.first};
164
    return Result;
165
  }
166

167
  void add(const Decl *Dcl, RelSet Flags) {
168
    const NamedDecl *D = llvm::dyn_cast_or_null<NamedDecl>(Dcl);
169
    if (!D)
170
      return;
171
    debug(*D, Flags);
172

173
    // Avoid recursion (which can arise in the presence of heuristic
174
    // resolution of dependent names) by exiting early if we have
175
    // already seen this decl with all flags in Flags.
176
    auto Res = Seen.try_emplace(D);
177
    if (!Res.second && Res.first->second.contains(Flags))
178
      return;
179
    Res.first->second |= Flags;
180

181
    if (const UsingDirectiveDecl *UDD = llvm::dyn_cast<UsingDirectiveDecl>(D))
182
      D = UDD->getNominatedNamespaceAsWritten();
183

184
    if (const TypedefNameDecl *TND = dyn_cast<TypedefNameDecl>(D)) {
185
      add(TND->getUnderlyingType(), Flags | Rel::Underlying);
186
      Flags |= Rel::Alias; // continue with the alias.
187
    } else if (const UsingDecl *UD = dyn_cast<UsingDecl>(D)) {
188
      // no Underlying as this is a non-renaming alias.
189
      for (const UsingShadowDecl *S : UD->shadows())
190
        add(S->getUnderlyingDecl(), Flags);
191
      Flags |= Rel::Alias; // continue with the alias.
192
    } else if (const UsingEnumDecl *UED = dyn_cast<UsingEnumDecl>(D)) {
193
      // UsingEnumDecl is not an alias at all, just a reference.
194
      D = UED->getEnumDecl();
195
    } else if (const auto *NAD = dyn_cast<NamespaceAliasDecl>(D)) {
196
      add(NAD->getUnderlyingDecl(), Flags | Rel::Underlying);
197
      Flags |= Rel::Alias; // continue with the alias
198
    } else if (const UnresolvedUsingValueDecl *UUVD =
199
                   dyn_cast<UnresolvedUsingValueDecl>(D)) {
200
      if (Resolver) {
201
        for (const NamedDecl *Target : Resolver->resolveUsingValueDecl(UUVD)) {
202
          add(Target, Flags); // no Underlying as this is a non-renaming alias
203
        }
204
      }
205
      Flags |= Rel::Alias; // continue with the alias
206
    } else if (isa<UnresolvedUsingTypenameDecl>(D)) {
207
      // FIXME: improve common dependent scope using name lookup in primary
208
      // templates.
209
      Flags |= Rel::Alias;
210
    } else if (const UsingShadowDecl *USD = dyn_cast<UsingShadowDecl>(D)) {
211
      // Include the introducing UsingDecl, but don't traverse it. This may end
212
      // up including *all* shadows, which we don't want.
213
      // Don't apply this logic to UsingEnumDecl, which can't easily be
214
      // conflated with the aliases it introduces.
215
      if (llvm::isa<UsingDecl>(USD->getIntroducer()))
216
        report(USD->getIntroducer(), Flags | Rel::Alias);
217
      // Shadow decls are synthetic and not themselves interesting.
218
      // Record the underlying decl instead, if allowed.
219
      D = USD->getTargetDecl();
220
    } else if (const auto *DG = dyn_cast<CXXDeductionGuideDecl>(D)) {
221
      D = DG->getDeducedTemplate();
222
    } else if (const ObjCImplementationDecl *IID =
223
                   dyn_cast<ObjCImplementationDecl>(D)) {
224
      // Treat ObjC{Interface,Implementation}Decl as if they were a decl/def
225
      // pair as long as the interface isn't implicit.
226
      if (const auto *CID = IID->getClassInterface())
227
        if (const auto *DD = CID->getDefinition())
228
          if (!DD->isImplicitInterfaceDecl())
229
            D = DD;
230
    } else if (const ObjCCategoryImplDecl *CID =
231
                   dyn_cast<ObjCCategoryImplDecl>(D)) {
232
      // Treat ObjC{Category,CategoryImpl}Decl as if they were a decl/def pair.
233
      D = CID->getCategoryDecl();
234
    }
235
    if (!D)
236
      return;
237

238
    if (const Decl *Pat = getTemplatePattern(D)) {
239
      assert(Pat != D);
240
      add(Pat, Flags | Rel::TemplatePattern);
241
      // Now continue with the instantiation.
242
      Flags |= Rel::TemplateInstantiation;
243
    }
244

245
    report(D, Flags);
246
  }
247

248
  void add(const Stmt *S, RelSet Flags) {
249
    if (!S)
250
      return;
251
    debug(*S, Flags);
252
    struct Visitor : public ConstStmtVisitor<Visitor> {
253
      TargetFinder &Outer;
254
      RelSet Flags;
255
      Visitor(TargetFinder &Outer, RelSet Flags) : Outer(Outer), Flags(Flags) {}
256

257
      void VisitCallExpr(const CallExpr *CE) {
258
        Outer.add(CE->getCalleeDecl(), Flags);
259
      }
260
      void VisitConceptSpecializationExpr(const ConceptSpecializationExpr *E) {
261
        Outer.add(E->getConceptReference(), Flags);
262
      }
263
      void VisitDeclRefExpr(const DeclRefExpr *DRE) {
264
        const Decl *D = DRE->getDecl();
265
        // UsingShadowDecl allows us to record the UsingDecl.
266
        // getFoundDecl() returns the wrong thing in other cases (templates).
267
        if (auto *USD = llvm::dyn_cast<UsingShadowDecl>(DRE->getFoundDecl()))
268
          D = USD;
269
        Outer.add(D, Flags);
270
      }
271
      void VisitMemberExpr(const MemberExpr *ME) {
272
        const Decl *D = ME->getMemberDecl();
273
        if (auto *USD =
274
                llvm::dyn_cast<UsingShadowDecl>(ME->getFoundDecl().getDecl()))
275
          D = USD;
276
        Outer.add(D, Flags);
277
      }
278
      void VisitOverloadExpr(const OverloadExpr *OE) {
279
        for (auto *D : OE->decls())
280
          Outer.add(D, Flags);
281
      }
282
      void VisitSizeOfPackExpr(const SizeOfPackExpr *SE) {
283
        Outer.add(SE->getPack(), Flags);
284
      }
285
      void VisitCXXConstructExpr(const CXXConstructExpr *CCE) {
286
        Outer.add(CCE->getConstructor(), Flags);
287
      }
288
      void VisitDesignatedInitExpr(const DesignatedInitExpr *DIE) {
289
        for (const DesignatedInitExpr::Designator &D :
290
             llvm::reverse(DIE->designators()))
291
          if (D.isFieldDesignator()) {
292
            Outer.add(D.getFieldDecl(), Flags);
293
            // We don't know which designator was intended, we assume the outer.
294
            break;
295
          }
296
      }
297
      void VisitGotoStmt(const GotoStmt *Goto) {
298
        if (auto *LabelDecl = Goto->getLabel())
299
          Outer.add(LabelDecl, Flags);
300
      }
301
      void VisitLabelStmt(const LabelStmt *Label) {
302
        if (auto *LabelDecl = Label->getDecl())
303
          Outer.add(LabelDecl, Flags);
304
      }
305
      void
306
      VisitCXXDependentScopeMemberExpr(const CXXDependentScopeMemberExpr *E) {
307
        if (Outer.Resolver) {
308
          for (const NamedDecl *D : Outer.Resolver->resolveMemberExpr(E)) {
309
            Outer.add(D, Flags);
310
          }
311
        }
312
      }
313
      void VisitDependentScopeDeclRefExpr(const DependentScopeDeclRefExpr *E) {
314
        if (Outer.Resolver) {
315
          for (const NamedDecl *D : Outer.Resolver->resolveDeclRefExpr(E)) {
316
            Outer.add(D, Flags);
317
          }
318
        }
319
      }
320
      void VisitObjCIvarRefExpr(const ObjCIvarRefExpr *OIRE) {
321
        Outer.add(OIRE->getDecl(), Flags);
322
      }
323
      void VisitObjCMessageExpr(const ObjCMessageExpr *OME) {
324
        Outer.add(OME->getMethodDecl(), Flags);
325
      }
326
      void VisitObjCPropertyRefExpr(const ObjCPropertyRefExpr *OPRE) {
327
        if (OPRE->isExplicitProperty())
328
          Outer.add(OPRE->getExplicitProperty(), Flags);
329
        else {
330
          if (OPRE->isMessagingGetter())
331
            Outer.add(OPRE->getImplicitPropertyGetter(), Flags);
332
          if (OPRE->isMessagingSetter())
333
            Outer.add(OPRE->getImplicitPropertySetter(), Flags);
334
        }
335
      }
336
      void VisitObjCProtocolExpr(const ObjCProtocolExpr *OPE) {
337
        Outer.add(OPE->getProtocol(), Flags);
338
      }
339
      void VisitOpaqueValueExpr(const OpaqueValueExpr *OVE) {
340
        Outer.add(OVE->getSourceExpr(), Flags);
341
      }
342
      void VisitPseudoObjectExpr(const PseudoObjectExpr *POE) {
343
        Outer.add(POE->getSyntacticForm(), Flags);
344
      }
345
      void VisitCXXNewExpr(const CXXNewExpr *CNE) {
346
        Outer.add(CNE->getOperatorNew(), Flags);
347
      }
348
      void VisitCXXDeleteExpr(const CXXDeleteExpr *CDE) {
349
        Outer.add(CDE->getOperatorDelete(), Flags);
350
      }
351
      void
352
      VisitCXXRewrittenBinaryOperator(const CXXRewrittenBinaryOperator *RBO) {
353
        Outer.add(RBO->getDecomposedForm().InnerBinOp, Flags);
354
      }
355
    };
356
    Visitor(*this, Flags).Visit(S);
357
  }
358

359
  void add(QualType T, RelSet Flags) {
360
    if (T.isNull())
361
      return;
362
    debug(T, Flags);
363
    struct Visitor : public TypeVisitor<Visitor> {
364
      TargetFinder &Outer;
365
      RelSet Flags;
366
      Visitor(TargetFinder &Outer, RelSet Flags) : Outer(Outer), Flags(Flags) {}
367

368
      void VisitTagType(const TagType *TT) {
369
        Outer.add(TT->getAsTagDecl(), Flags);
370
      }
371

372
      void VisitElaboratedType(const ElaboratedType *ET) {
373
        Outer.add(ET->desugar(), Flags);
374
      }
375

376
      void VisitUsingType(const UsingType *ET) {
377
        Outer.add(ET->getFoundDecl(), Flags);
378
      }
379

380
      void VisitInjectedClassNameType(const InjectedClassNameType *ICNT) {
381
        Outer.add(ICNT->getDecl(), Flags);
382
      }
383

384
      void VisitDecltypeType(const DecltypeType *DTT) {
385
        Outer.add(DTT->getUnderlyingType(), Flags | Rel::Underlying);
386
      }
387
      void VisitDeducedType(const DeducedType *DT) {
388
        // FIXME: In practice this doesn't work: the AutoType you find inside
389
        // TypeLoc never has a deduced type. https://llvm.org/PR42914
390
        Outer.add(DT->getDeducedType(), Flags);
391
      }
392
      void VisitUnresolvedUsingType(const UnresolvedUsingType *UUT) {
393
        Outer.add(UUT->getDecl(), Flags);
394
      }
395
      void VisitDeducedTemplateSpecializationType(
396
          const DeducedTemplateSpecializationType *DTST) {
397
        if (const auto *USD = DTST->getTemplateName().getAsUsingShadowDecl())
398
          Outer.add(USD, Flags);
399

400
        // FIXME: This is a workaround for https://llvm.org/PR42914,
401
        // which is causing DTST->getDeducedType() to be empty. We
402
        // fall back to the template pattern and miss the instantiation
403
        // even when it's known in principle. Once that bug is fixed,
404
        // the following code can be removed (the existing handling in
405
        // VisitDeducedType() is sufficient).
406
        if (auto *TD = DTST->getTemplateName().getAsTemplateDecl())
407
          Outer.add(TD->getTemplatedDecl(), Flags | Rel::TemplatePattern);
408
      }
409
      void VisitDependentNameType(const DependentNameType *DNT) {
410
        if (Outer.Resolver) {
411
          for (const NamedDecl *ND :
412
               Outer.Resolver->resolveDependentNameType(DNT)) {
413
            Outer.add(ND, Flags);
414
          }
415
        }
416
      }
417
      void VisitDependentTemplateSpecializationType(
418
          const DependentTemplateSpecializationType *DTST) {
419
        if (Outer.Resolver) {
420
          for (const NamedDecl *ND :
421
               Outer.Resolver->resolveTemplateSpecializationType(DTST)) {
422
            Outer.add(ND, Flags);
423
          }
424
        }
425
      }
426
      void VisitTypedefType(const TypedefType *TT) {
427
        if (shouldSkipTypedef(TT->getDecl()))
428
          return;
429
        Outer.add(TT->getDecl(), Flags);
430
      }
431
      void
432
      VisitTemplateSpecializationType(const TemplateSpecializationType *TST) {
433
        // Have to handle these case-by-case.
434

435
        if (const auto *UTN = TST->getTemplateName().getAsUsingShadowDecl())
436
          Outer.add(UTN, Flags);
437

438
        // templated type aliases: there's no specialized/instantiated using
439
        // decl to point to. So try to find a decl for the underlying type
440
        // (after substitution), and failing that point to the (templated) using
441
        // decl.
442
        if (TST->isTypeAlias()) {
443
          Outer.add(TST->getAliasedType(), Flags | Rel::Underlying);
444
          // Don't *traverse* the alias, which would result in traversing the
445
          // template of the underlying type.
446

447
          TemplateDecl *TD = TST->getTemplateName().getAsTemplateDecl();
448
          // Builtin templates e.g. __make_integer_seq, __type_pack_element
449
          // are such that they don't have alias *decls*. Even then, we still
450
          // traverse their desugared *types* so that instantiated decls are
451
          // collected.
452
          if (llvm::isa<BuiltinTemplateDecl>(TD))
453
            return;
454
          Outer.report(TD->getTemplatedDecl(),
455
                       Flags | Rel::Alias | Rel::TemplatePattern);
456
        }
457
        // specializations of template template parameters aren't instantiated
458
        // into decls, so they must refer to the parameter itself.
459
        else if (const auto *Parm =
460
                     llvm::dyn_cast_or_null<TemplateTemplateParmDecl>(
461
                         TST->getTemplateName().getAsTemplateDecl()))
462
          Outer.add(Parm, Flags);
463
        // class template specializations have a (specialized) CXXRecordDecl.
464
        else if (const CXXRecordDecl *RD = TST->getAsCXXRecordDecl())
465
          Outer.add(RD, Flags); // add(Decl) will despecialize if needed.
466
        else {
467
          // fallback: the (un-specialized) declaration from primary template.
468
          if (auto *TD = TST->getTemplateName().getAsTemplateDecl())
469
            Outer.add(TD->getTemplatedDecl(), Flags | Rel::TemplatePattern);
470
        }
471
      }
472
      void
473
      VisitSubstTemplateTypeParmType(const SubstTemplateTypeParmType *STTPT) {
474
        Outer.add(STTPT->getReplacementType(), Flags);
475
      }
476
      void VisitTemplateTypeParmType(const TemplateTypeParmType *TTPT) {
477
        Outer.add(TTPT->getDecl(), Flags);
478
      }
479
      void VisitObjCInterfaceType(const ObjCInterfaceType *OIT) {
480
        Outer.add(OIT->getDecl(), Flags);
481
      }
482
    };
483
    Visitor(*this, Flags).Visit(T.getTypePtr());
484
  }
485

486
  void add(const NestedNameSpecifier *NNS, RelSet Flags) {
487
    if (!NNS)
488
      return;
489
    debug(*NNS, Flags);
490
    switch (NNS->getKind()) {
491
    case NestedNameSpecifier::Namespace:
492
      add(NNS->getAsNamespace(), Flags);
493
      return;
494
    case NestedNameSpecifier::NamespaceAlias:
495
      add(NNS->getAsNamespaceAlias(), Flags);
496
      return;
497
    case NestedNameSpecifier::Identifier:
498
      if (Resolver) {
499
        add(QualType(Resolver->resolveNestedNameSpecifierToType(NNS), 0),
500
            Flags);
501
      }
502
      return;
503
    case NestedNameSpecifier::TypeSpec:
504
    case NestedNameSpecifier::TypeSpecWithTemplate:
505
      add(QualType(NNS->getAsType(), 0), Flags);
506
      return;
507
    case NestedNameSpecifier::Global:
508
      // This should be TUDecl, but we can't get a pointer to it!
509
      return;
510
    case NestedNameSpecifier::Super:
511
      add(NNS->getAsRecordDecl(), Flags);
512
      return;
513
    }
514
    llvm_unreachable("unhandled NestedNameSpecifier::SpecifierKind");
515
  }
516

517
  void add(const CXXCtorInitializer *CCI, RelSet Flags) {
518
    if (!CCI)
519
      return;
520
    debug(*CCI, Flags);
521

522
    if (CCI->isAnyMemberInitializer())
523
      add(CCI->getAnyMember(), Flags);
524
    // Constructor calls contain a TypeLoc node, so we don't handle them here.
525
  }
526

527
  void add(const TemplateArgument &Arg, RelSet Flags) {
528
    // Only used for template template arguments.
529
    // For type and non-type template arguments, SelectionTree
530
    // will hit a more specific node (e.g. a TypeLoc or a
531
    // DeclRefExpr).
532
    if (Arg.getKind() == TemplateArgument::Template ||
533
        Arg.getKind() == TemplateArgument::TemplateExpansion) {
534
      if (TemplateDecl *TD =
535
              Arg.getAsTemplateOrTemplatePattern().getAsTemplateDecl()) {
536
        report(TD, Flags);
537
      }
538
      if (const auto *USD =
539
              Arg.getAsTemplateOrTemplatePattern().getAsUsingShadowDecl())
540
        add(USD, Flags);
541
    }
542
  }
543

544
  void add(const ConceptReference *CR, RelSet Flags) {
545
    add(CR->getNamedConcept(), Flags);
546
  }
547
};
548

549
} // namespace
550

551
llvm::SmallVector<std::pair<const NamedDecl *, DeclRelationSet>, 1>
552
allTargetDecls(const DynTypedNode &N, const HeuristicResolver *Resolver) {
553
  dlog("allTargetDecls({0})", nodeToString(N));
554
  TargetFinder Finder(Resolver);
555
  DeclRelationSet Flags;
556
  if (const Decl *D = N.get<Decl>())
557
    Finder.add(D, Flags);
558
  else if (const Stmt *S = N.get<Stmt>())
559
    Finder.add(S, Flags);
560
  else if (const NestedNameSpecifierLoc *NNSL = N.get<NestedNameSpecifierLoc>())
561
    Finder.add(NNSL->getNestedNameSpecifier(), Flags);
562
  else if (const NestedNameSpecifier *NNS = N.get<NestedNameSpecifier>())
563
    Finder.add(NNS, Flags);
564
  else if (const TypeLoc *TL = N.get<TypeLoc>())
565
    Finder.add(TL->getType(), Flags);
566
  else if (const QualType *QT = N.get<QualType>())
567
    Finder.add(*QT, Flags);
568
  else if (const CXXCtorInitializer *CCI = N.get<CXXCtorInitializer>())
569
    Finder.add(CCI, Flags);
570
  else if (const TemplateArgumentLoc *TAL = N.get<TemplateArgumentLoc>())
571
    Finder.add(TAL->getArgument(), Flags);
572
  else if (const CXXBaseSpecifier *CBS = N.get<CXXBaseSpecifier>())
573
    Finder.add(CBS->getTypeSourceInfo()->getType(), Flags);
574
  else if (const ObjCProtocolLoc *PL = N.get<ObjCProtocolLoc>())
575
    Finder.add(PL->getProtocol(), Flags);
576
  else if (const ConceptReference *CR = N.get<ConceptReference>())
577
    Finder.add(CR, Flags);
578
  return Finder.takeDecls();
579
}
580

581
llvm::SmallVector<const NamedDecl *, 1>
582
targetDecl(const DynTypedNode &N, DeclRelationSet Mask,
583
           const HeuristicResolver *Resolver) {
584
  llvm::SmallVector<const NamedDecl *, 1> Result;
585
  for (const auto &Entry : allTargetDecls(N, Resolver)) {
586
    if (!(Entry.second & ~Mask))
587
      Result.push_back(Entry.first);
588
  }
589
  return Result;
590
}
591

592
llvm::SmallVector<const NamedDecl *, 1>
593
explicitReferenceTargets(DynTypedNode N, DeclRelationSet Mask,
594
                         const HeuristicResolver *Resolver) {
595
  assert(!(Mask & (DeclRelation::TemplatePattern |
596
                   DeclRelation::TemplateInstantiation)) &&
597
         "explicitReferenceTargets handles templates on its own");
598
  auto Decls = allTargetDecls(N, Resolver);
599

600
  // We prefer to return template instantiation, but fallback to template
601
  // pattern if instantiation is not available.
602
  Mask |= DeclRelation::TemplatePattern | DeclRelation::TemplateInstantiation;
603

604
  llvm::SmallVector<const NamedDecl *, 1> TemplatePatterns;
605
  llvm::SmallVector<const NamedDecl *, 1> Targets;
606
  bool SeenTemplateInstantiations = false;
607
  for (auto &D : Decls) {
608
    if (D.second & ~Mask)
609
      continue;
610
    if (D.second & DeclRelation::TemplatePattern) {
611
      TemplatePatterns.push_back(D.first);
612
      continue;
613
    }
614
    if (D.second & DeclRelation::TemplateInstantiation)
615
      SeenTemplateInstantiations = true;
616
    Targets.push_back(D.first);
617
  }
618
  if (!SeenTemplateInstantiations)
619
    Targets.insert(Targets.end(), TemplatePatterns.begin(),
620
                   TemplatePatterns.end());
621
  return Targets;
622
}
623

624
namespace {
625
llvm::SmallVector<ReferenceLoc> refInDecl(const Decl *D,
626
                                          const HeuristicResolver *Resolver) {
627
  struct Visitor : ConstDeclVisitor<Visitor> {
628
    Visitor(const HeuristicResolver *Resolver) : Resolver(Resolver) {}
629

630
    const HeuristicResolver *Resolver;
631
    llvm::SmallVector<ReferenceLoc> Refs;
632

633
    void VisitUsingDirectiveDecl(const UsingDirectiveDecl *D) {
634
      // We want to keep it as non-declaration references, as the
635
      // "using namespace" declaration doesn't have a name.
636
      Refs.push_back(ReferenceLoc{D->getQualifierLoc(),
637
                                  D->getIdentLocation(),
638
                                  /*IsDecl=*/false,
639
                                  {D->getNominatedNamespaceAsWritten()}});
640
    }
641

642
    void VisitUsingDecl(const UsingDecl *D) {
643
      // "using ns::identifier;" is a non-declaration reference.
644
      Refs.push_back(ReferenceLoc{
645
          D->getQualifierLoc(), D->getLocation(), /*IsDecl=*/false,
646
          explicitReferenceTargets(DynTypedNode::create(*D),
647
                                   DeclRelation::Underlying, Resolver)});
648
    }
649

650
    void VisitUsingEnumDecl(const UsingEnumDecl *D) {
651
      // "using enum ns::E" is a non-declaration reference.
652
      // The reference is covered by the embedded typeloc.
653
      // Don't use the default VisitNamedDecl, which would report a declaration.
654
    }
655

656
    void VisitNamespaceAliasDecl(const NamespaceAliasDecl *D) {
657
      // For namespace alias, "namespace Foo = Target;", we add two references.
658
      // Add a declaration reference for Foo.
659
      VisitNamedDecl(D);
660
      // Add a non-declaration reference for Target.
661
      Refs.push_back(ReferenceLoc{D->getQualifierLoc(),
662
                                  D->getTargetNameLoc(),
663
                                  /*IsDecl=*/false,
664
                                  {D->getAliasedNamespace()}});
665
    }
666

667
    void VisitNamedDecl(const NamedDecl *ND) {
668
      // We choose to ignore {Class, Function, Var, TypeAlias}TemplateDecls. As
669
      // as their underlying decls, covering the same range, will be visited.
670
      if (llvm::isa<ClassTemplateDecl>(ND) ||
671
          llvm::isa<FunctionTemplateDecl>(ND) ||
672
          llvm::isa<VarTemplateDecl>(ND) ||
673
          llvm::isa<TypeAliasTemplateDecl>(ND))
674
        return;
675
      // FIXME: decide on how to surface destructors when we need them.
676
      if (llvm::isa<CXXDestructorDecl>(ND))
677
        return;
678
      // Filter anonymous decls, name location will point outside the name token
679
      // and the clients are not prepared to handle that.
680
      if (ND->getDeclName().isIdentifier() &&
681
          !ND->getDeclName().getAsIdentifierInfo())
682
        return;
683
      Refs.push_back(ReferenceLoc{getQualifierLoc(*ND),
684
                                  ND->getLocation(),
685
                                  /*IsDecl=*/true,
686
                                  {ND}});
687
    }
688

689
    void VisitCXXDeductionGuideDecl(const CXXDeductionGuideDecl *DG) {
690
      // The class template name in a deduction guide targets the class
691
      // template.
692
      Refs.push_back(ReferenceLoc{DG->getQualifierLoc(),
693
                                  DG->getNameInfo().getLoc(),
694
                                  /*IsDecl=*/false,
695
                                  {DG->getDeducedTemplate()}});
696
    }
697

698
    void VisitObjCMethodDecl(const ObjCMethodDecl *OMD) {
699
      // The name may have several tokens, we can only report the first.
700
      Refs.push_back(ReferenceLoc{NestedNameSpecifierLoc(),
701
                                  OMD->getSelectorStartLoc(),
702
                                  /*IsDecl=*/true,
703
                                  {OMD}});
704
    }
705

706
    void VisitObjCCategoryDecl(const ObjCCategoryDecl *OCD) {
707
      // getLocation is the extended class's location, not the category's.
708
      Refs.push_back(ReferenceLoc{NestedNameSpecifierLoc(),
709
                                  OCD->getLocation(),
710
                                  /*IsDecl=*/false,
711
                                  {OCD->getClassInterface()}});
712
      Refs.push_back(ReferenceLoc{NestedNameSpecifierLoc(),
713
                                  OCD->getCategoryNameLoc(),
714
                                  /*IsDecl=*/true,
715
                                  {OCD}});
716
    }
717

718
    void VisitObjCCategoryImplDecl(const ObjCCategoryImplDecl *OCID) {
719
      Refs.push_back(ReferenceLoc{NestedNameSpecifierLoc(),
720
                                  OCID->getLocation(),
721
                                  /*IsDecl=*/false,
722
                                  {OCID->getClassInterface()}});
723
      Refs.push_back(ReferenceLoc{NestedNameSpecifierLoc(),
724
                                  OCID->getCategoryNameLoc(),
725
                                  /*IsDecl=*/false,
726
                                  {OCID->getCategoryDecl()}});
727
      Refs.push_back(ReferenceLoc{NestedNameSpecifierLoc(),
728
                                  OCID->getCategoryNameLoc(),
729
                                  /*IsDecl=*/true,
730
                                  {OCID}});
731
    }
732

733
    void VisitObjCImplementationDecl(const ObjCImplementationDecl *OIMD) {
734
      Refs.push_back(ReferenceLoc{NestedNameSpecifierLoc(),
735
                                  OIMD->getLocation(),
736
                                  /*IsDecl=*/false,
737
                                  {OIMD->getClassInterface()}});
738
      Refs.push_back(ReferenceLoc{NestedNameSpecifierLoc(),
739
                                  OIMD->getLocation(),
740
                                  /*IsDecl=*/true,
741
                                  {OIMD}});
742
    }
743
  };
744

745
  Visitor V{Resolver};
746
  V.Visit(D);
747
  return V.Refs;
748
}
749

750
llvm::SmallVector<ReferenceLoc> refInStmt(const Stmt *S,
751
                                          const HeuristicResolver *Resolver) {
752
  struct Visitor : ConstStmtVisitor<Visitor> {
753
    Visitor(const HeuristicResolver *Resolver) : Resolver(Resolver) {}
754

755
    const HeuristicResolver *Resolver;
756
    // FIXME: handle more complicated cases: more ObjC, designated initializers.
757
    llvm::SmallVector<ReferenceLoc> Refs;
758

759
    void VisitDeclRefExpr(const DeclRefExpr *E) {
760
      Refs.push_back(ReferenceLoc{E->getQualifierLoc(),
761
                                  E->getNameInfo().getLoc(),
762
                                  /*IsDecl=*/false,
763
                                  {E->getFoundDecl()}});
764
    }
765

766
    void VisitDependentScopeDeclRefExpr(const DependentScopeDeclRefExpr *E) {
767
      Refs.push_back(ReferenceLoc{
768
          E->getQualifierLoc(), E->getNameInfo().getLoc(), /*IsDecl=*/false,
769
          explicitReferenceTargets(DynTypedNode::create(*E), {}, Resolver)});
770
    }
771

772
    void VisitMemberExpr(const MemberExpr *E) {
773
      // Skip destructor calls to avoid duplication: TypeLoc within will be
774
      // visited separately.
775
      if (llvm::isa<CXXDestructorDecl>(E->getFoundDecl().getDecl()))
776
        return;
777
      Refs.push_back(ReferenceLoc{E->getQualifierLoc(),
778
                                  E->getMemberNameInfo().getLoc(),
779
                                  /*IsDecl=*/false,
780
                                  {E->getFoundDecl()}});
781
    }
782

783
    void
784
    VisitCXXDependentScopeMemberExpr(const CXXDependentScopeMemberExpr *E) {
785
      Refs.push_back(ReferenceLoc{
786
          E->getQualifierLoc(), E->getMemberNameInfo().getLoc(),
787
          /*IsDecl=*/false,
788
          explicitReferenceTargets(DynTypedNode::create(*E), {}, Resolver)});
789
    }
790

791
    void VisitOverloadExpr(const OverloadExpr *E) {
792
      Refs.push_back(ReferenceLoc{E->getQualifierLoc(),
793
                                  E->getNameInfo().getLoc(),
794
                                  /*IsDecl=*/false,
795
                                  llvm::SmallVector<const NamedDecl *, 1>(
796
                                      E->decls().begin(), E->decls().end())});
797
    }
798

799
    void VisitSizeOfPackExpr(const SizeOfPackExpr *E) {
800
      Refs.push_back(ReferenceLoc{NestedNameSpecifierLoc(),
801
                                  E->getPackLoc(),
802
                                  /*IsDecl=*/false,
803
                                  {E->getPack()}});
804
    }
805

806
    void VisitObjCPropertyRefExpr(const ObjCPropertyRefExpr *E) {
807
      Refs.push_back(ReferenceLoc{
808
          NestedNameSpecifierLoc(), E->getLocation(),
809
          /*IsDecl=*/false,
810
          // Select the getter, setter, or @property depending on the call.
811
          explicitReferenceTargets(DynTypedNode::create(*E), {}, Resolver)});
812
    }
813

814
    void VisitObjCIvarRefExpr(const ObjCIvarRefExpr *OIRE) {
815
      Refs.push_back(ReferenceLoc{NestedNameSpecifierLoc(),
816
                                  OIRE->getLocation(),
817
                                  /*IsDecl=*/false,
818
                                  {OIRE->getDecl()}});
819
    }
820

821
    void VisitObjCMessageExpr(const ObjCMessageExpr *E) {
822
      // The name may have several tokens, we can only report the first.
823
      Refs.push_back(ReferenceLoc{NestedNameSpecifierLoc(),
824
                                  E->getSelectorStartLoc(),
825
                                  /*IsDecl=*/false,
826
                                  {E->getMethodDecl()}});
827
    }
828

829
    void VisitDesignatedInitExpr(const DesignatedInitExpr *DIE) {
830
      for (const DesignatedInitExpr::Designator &D : DIE->designators()) {
831
        if (!D.isFieldDesignator())
832
          continue;
833

834
        Refs.push_back(ReferenceLoc{NestedNameSpecifierLoc(),
835
                                    D.getFieldLoc(),
836
                                    /*IsDecl=*/false,
837
                                    {D.getFieldDecl()}});
838
      }
839
    }
840

841
    void VisitGotoStmt(const GotoStmt *GS) {
842
      Refs.push_back(ReferenceLoc{NestedNameSpecifierLoc(),
843
                                  GS->getLabelLoc(),
844
                                  /*IsDecl=*/false,
845
                                  {GS->getLabel()}});
846
    }
847

848
    void VisitLabelStmt(const LabelStmt *LS) {
849
      Refs.push_back(ReferenceLoc{NestedNameSpecifierLoc(),
850
                                  LS->getIdentLoc(),
851
                                  /*IsDecl=*/true,
852
                                  {LS->getDecl()}});
853
    }
854
  };
855

856
  Visitor V{Resolver};
857
  V.Visit(S);
858
  return V.Refs;
859
}
860

861
llvm::SmallVector<ReferenceLoc>
862
refInTypeLoc(TypeLoc L, const HeuristicResolver *Resolver) {
863
  struct Visitor : TypeLocVisitor<Visitor> {
864
    Visitor(const HeuristicResolver *Resolver) : Resolver(Resolver) {}
865

866
    const HeuristicResolver *Resolver;
867
    llvm::SmallVector<ReferenceLoc> Refs;
868

869
    void VisitElaboratedTypeLoc(ElaboratedTypeLoc L) {
870
      // We only know about qualifier, rest if filled by inner locations.
871
      size_t InitialSize = Refs.size();
872
      Visit(L.getNamedTypeLoc().getUnqualifiedLoc());
873
      size_t NewSize = Refs.size();
874
      // Add qualifier for the newly-added refs.
875
      for (unsigned I = InitialSize; I < NewSize; ++I) {
876
        ReferenceLoc *Ref = &Refs[I];
877
        // Fill in the qualifier.
878
        assert(!Ref->Qualifier.hasQualifier() && "qualifier already set");
879
        Ref->Qualifier = L.getQualifierLoc();
880
      }
881
    }
882

883
    void VisitUsingTypeLoc(UsingTypeLoc L) {
884
      Refs.push_back(ReferenceLoc{NestedNameSpecifierLoc(),
885
                                  L.getLocalSourceRange().getBegin(),
886
                                  /*IsDecl=*/false,
887
                                  {L.getFoundDecl()}});
888
    }
889

890
    void VisitTagTypeLoc(TagTypeLoc L) {
891
      Refs.push_back(ReferenceLoc{NestedNameSpecifierLoc(),
892
                                  L.getNameLoc(),
893
                                  /*IsDecl=*/false,
894
                                  {L.getDecl()}});
895
    }
896

897
    void VisitTemplateTypeParmTypeLoc(TemplateTypeParmTypeLoc L) {
898
      Refs.push_back(ReferenceLoc{NestedNameSpecifierLoc(),
899
                                  L.getNameLoc(),
900
                                  /*IsDecl=*/false,
901
                                  {L.getDecl()}});
902
    }
903

904
    void VisitTemplateSpecializationTypeLoc(TemplateSpecializationTypeLoc L) {
905
      // We must ensure template type aliases are included in results if they
906
      // were written in the source code, e.g. in
907
      //    template <class T> using valias = vector<T>;
908
      //    ^valias<int> x;
909
      // 'explicitReferenceTargets' will return:
910
      //    1. valias with mask 'Alias'.
911
      //    2. 'vector<int>' with mask 'Underlying'.
912
      //  we want to return only #1 in this case.
913
      Refs.push_back(ReferenceLoc{
914
          NestedNameSpecifierLoc(), L.getTemplateNameLoc(), /*IsDecl=*/false,
915
          explicitReferenceTargets(DynTypedNode::create(L.getType()),
916
                                   DeclRelation::Alias, Resolver)});
917
    }
918
    void VisitDeducedTemplateSpecializationTypeLoc(
919
        DeducedTemplateSpecializationTypeLoc L) {
920
      Refs.push_back(ReferenceLoc{
921
          NestedNameSpecifierLoc(), L.getNameLoc(), /*IsDecl=*/false,
922
          explicitReferenceTargets(DynTypedNode::create(L.getType()),
923
                                   DeclRelation::Alias, Resolver)});
924
    }
925

926
    void VisitInjectedClassNameTypeLoc(InjectedClassNameTypeLoc TL) {
927
      Refs.push_back(ReferenceLoc{NestedNameSpecifierLoc(),
928
                                  TL.getNameLoc(),
929
                                  /*IsDecl=*/false,
930
                                  {TL.getDecl()}});
931
    }
932

933
    void VisitDependentTemplateSpecializationTypeLoc(
934
        DependentTemplateSpecializationTypeLoc L) {
935
      Refs.push_back(
936
          ReferenceLoc{L.getQualifierLoc(), L.getTemplateNameLoc(),
937
                       /*IsDecl=*/false,
938
                       explicitReferenceTargets(
939
                           DynTypedNode::create(L.getType()), {}, Resolver)});
940
    }
941

942
    void VisitDependentNameTypeLoc(DependentNameTypeLoc L) {
943
      Refs.push_back(
944
          ReferenceLoc{L.getQualifierLoc(), L.getNameLoc(),
945
                       /*IsDecl=*/false,
946
                       explicitReferenceTargets(
947
                           DynTypedNode::create(L.getType()), {}, Resolver)});
948
    }
949

950
    void VisitTypedefTypeLoc(TypedefTypeLoc L) {
951
      if (shouldSkipTypedef(L.getTypedefNameDecl()))
952
        return;
953
      Refs.push_back(ReferenceLoc{NestedNameSpecifierLoc(),
954
                                  L.getNameLoc(),
955
                                  /*IsDecl=*/false,
956
                                  {L.getTypedefNameDecl()}});
957
    }
958

959
    void VisitObjCInterfaceTypeLoc(ObjCInterfaceTypeLoc L) {
960
      Refs.push_back(ReferenceLoc{NestedNameSpecifierLoc(),
961
                                  L.getNameLoc(),
962
                                  /*IsDecl=*/false,
963
                                  {L.getIFaceDecl()}});
964
    }
965
  };
966

967
  Visitor V{Resolver};
968
  V.Visit(L.getUnqualifiedLoc());
969
  return V.Refs;
970
}
971

972
class ExplicitReferenceCollector
973
    : public RecursiveASTVisitor<ExplicitReferenceCollector> {
974
public:
975
  ExplicitReferenceCollector(llvm::function_ref<void(ReferenceLoc)> Out,
976
                             const HeuristicResolver *Resolver)
977
      : Out(Out), Resolver(Resolver) {
978
    assert(Out);
979
  }
980

981
  bool VisitTypeLoc(TypeLoc TTL) {
982
    if (TypeLocsToSkip.count(TTL.getBeginLoc()))
983
      return true;
984
    visitNode(DynTypedNode::create(TTL));
985
    return true;
986
  }
987

988
  bool TraverseElaboratedTypeLoc(ElaboratedTypeLoc L) {
989
    // ElaboratedTypeLoc will reports information for its inner type loc.
990
    // Otherwise we loose information about inner types loc's qualifier.
991
    TypeLoc Inner = L.getNamedTypeLoc().getUnqualifiedLoc();
992
    if (L.getBeginLoc() == Inner.getBeginLoc())
993
      return RecursiveASTVisitor::TraverseTypeLoc(Inner);
994
    else
995
      TypeLocsToSkip.insert(Inner.getBeginLoc());
996
    return RecursiveASTVisitor::TraverseElaboratedTypeLoc(L);
997
  }
998

999
  bool VisitStmt(Stmt *S) {
1000
    visitNode(DynTypedNode::create(*S));
1001
    return true;
1002
  }
1003

1004
  bool TraverseOpaqueValueExpr(OpaqueValueExpr *OVE) {
1005
    visitNode(DynTypedNode::create(*OVE));
1006
    // Not clear why the source expression is skipped by default...
1007
    // FIXME: can we just make RecursiveASTVisitor do this?
1008
    return RecursiveASTVisitor::TraverseStmt(OVE->getSourceExpr());
1009
  }
1010

1011
  bool TraversePseudoObjectExpr(PseudoObjectExpr *POE) {
1012
    visitNode(DynTypedNode::create(*POE));
1013
    // Traverse only the syntactic form to find the *written* references.
1014
    // (The semantic form also contains lots of duplication)
1015
    return RecursiveASTVisitor::TraverseStmt(POE->getSyntacticForm());
1016
  }
1017

1018
  // We re-define Traverse*, since there's no corresponding Visit*.
1019
  // TemplateArgumentLoc is the only way to get locations for references to
1020
  // template template parameters.
1021
  bool TraverseTemplateArgumentLoc(TemplateArgumentLoc A) {
1022
    switch (A.getArgument().getKind()) {
1023
    case TemplateArgument::Template:
1024
    case TemplateArgument::TemplateExpansion:
1025
      reportReference(ReferenceLoc{A.getTemplateQualifierLoc(),
1026
                                   A.getTemplateNameLoc(),
1027
                                   /*IsDecl=*/false,
1028
                                   {A.getArgument()
1029
                                        .getAsTemplateOrTemplatePattern()
1030
                                        .getAsTemplateDecl()}},
1031
                      DynTypedNode::create(A.getArgument()));
1032
      break;
1033
    case TemplateArgument::Declaration:
1034
      break; // FIXME: can this actually happen in TemplateArgumentLoc?
1035
    case TemplateArgument::Integral:
1036
    case TemplateArgument::Null:
1037
    case TemplateArgument::NullPtr:
1038
      break; // no references.
1039
    case TemplateArgument::Pack:
1040
    case TemplateArgument::Type:
1041
    case TemplateArgument::Expression:
1042
    case TemplateArgument::StructuralValue:
1043
      break; // Handled by VisitType and VisitExpression.
1044
    };
1045
    return RecursiveASTVisitor::TraverseTemplateArgumentLoc(A);
1046
  }
1047

1048
  bool VisitDecl(Decl *D) {
1049
    visitNode(DynTypedNode::create(*D));
1050
    return true;
1051
  }
1052

1053
  // We have to use Traverse* because there is no corresponding Visit*.
1054
  bool TraverseNestedNameSpecifierLoc(NestedNameSpecifierLoc L) {
1055
    if (!L.getNestedNameSpecifier())
1056
      return true;
1057
    visitNode(DynTypedNode::create(L));
1058
    // Inner type is missing information about its qualifier, skip it.
1059
    if (auto TL = L.getTypeLoc())
1060
      TypeLocsToSkip.insert(TL.getBeginLoc());
1061
    return RecursiveASTVisitor::TraverseNestedNameSpecifierLoc(L);
1062
  }
1063

1064
  bool TraverseObjCProtocolLoc(ObjCProtocolLoc ProtocolLoc) {
1065
    visitNode(DynTypedNode::create(ProtocolLoc));
1066
    return true;
1067
  }
1068

1069
  bool TraverseConstructorInitializer(CXXCtorInitializer *Init) {
1070
    visitNode(DynTypedNode::create(*Init));
1071
    return RecursiveASTVisitor::TraverseConstructorInitializer(Init);
1072
  }
1073

1074
  bool VisitConceptReference(const ConceptReference *CR) {
1075
    visitNode(DynTypedNode::create(*CR));
1076
    return true;
1077
  }
1078

1079
private:
1080
  /// Obtain information about a reference directly defined in \p N. Does not
1081
  /// recurse into child nodes, e.g. do not expect references for constructor
1082
  /// initializers
1083
  ///
1084
  /// Any of the fields in the returned structure can be empty, but not all of
1085
  /// them, e.g.
1086
  ///   - for implicitly generated nodes (e.g. MemberExpr from range-based-for),
1087
  ///     source location information may be missing,
1088
  ///   - for dependent code, targets may be empty.
1089
  ///
1090
  /// (!) For the purposes of this function declarations are not considered to
1091
  ///     be references. However, declarations can have references inside them,
1092
  ///     e.g. 'namespace foo = std' references namespace 'std' and this
1093
  ///     function will return the corresponding reference.
1094
  llvm::SmallVector<ReferenceLoc> explicitReference(DynTypedNode N) {
1095
    if (auto *D = N.get<Decl>())
1096
      return refInDecl(D, Resolver);
1097
    if (auto *S = N.get<Stmt>())
1098
      return refInStmt(S, Resolver);
1099
    if (auto *NNSL = N.get<NestedNameSpecifierLoc>()) {
1100
      // (!) 'DeclRelation::Alias' ensures we do not loose namespace aliases.
1101
      return {ReferenceLoc{
1102
          NNSL->getPrefix(), NNSL->getLocalBeginLoc(), false,
1103
          explicitReferenceTargets(
1104
              DynTypedNode::create(*NNSL->getNestedNameSpecifier()),
1105
              DeclRelation::Alias, Resolver)}};
1106
    }
1107
    if (const TypeLoc *TL = N.get<TypeLoc>())
1108
      return refInTypeLoc(*TL, Resolver);
1109
    if (const CXXCtorInitializer *CCI = N.get<CXXCtorInitializer>()) {
1110
      // Other type initializers (e.g. base initializer) are handled by visiting
1111
      // the typeLoc.
1112
      if (CCI->isAnyMemberInitializer()) {
1113
        return {ReferenceLoc{NestedNameSpecifierLoc(),
1114
                             CCI->getMemberLocation(),
1115
                             /*IsDecl=*/false,
1116
                             {CCI->getAnyMember()}}};
1117
      }
1118
    }
1119
    if (const ObjCProtocolLoc *PL = N.get<ObjCProtocolLoc>())
1120
      return {ReferenceLoc{NestedNameSpecifierLoc(),
1121
                           PL->getLocation(),
1122
                           /*IsDecl=*/false,
1123
                           {PL->getProtocol()}}};
1124
    if (const ConceptReference *CR = N.get<ConceptReference>())
1125
      return {ReferenceLoc{CR->getNestedNameSpecifierLoc(),
1126
                           CR->getConceptNameLoc(),
1127
                           /*IsDecl=*/false,
1128
                           {CR->getNamedConcept()}}};
1129

1130
    // We do not have location information for other nodes (QualType, etc)
1131
    return {};
1132
  }
1133

1134
  void visitNode(DynTypedNode N) {
1135
    for (auto &R : explicitReference(N))
1136
      reportReference(std::move(R), N);
1137
  }
1138

1139
  void reportReference(ReferenceLoc &&Ref, DynTypedNode N) {
1140
    // Strip null targets that can arise from invalid code.
1141
    // (This avoids having to check for null everywhere we insert)
1142
    llvm::erase(Ref.Targets, nullptr);
1143
    // Our promise is to return only references from the source code. If we lack
1144
    // location information, skip these nodes.
1145
    // Normally this should not happen in practice, unless there are bugs in the
1146
    // traversals or users started the traversal at an implicit node.
1147
    if (Ref.NameLoc.isInvalid()) {
1148
      dlog("invalid location at node {0}", nodeToString(N));
1149
      return;
1150
    }
1151
    Out(Ref);
1152
  }
1153

1154
  llvm::function_ref<void(ReferenceLoc)> Out;
1155
  const HeuristicResolver *Resolver;
1156
  /// TypeLocs starting at these locations must be skipped, see
1157
  /// TraverseElaboratedTypeSpecifierLoc for details.
1158
  llvm::DenseSet<SourceLocation> TypeLocsToSkip;
1159
};
1160
} // namespace
1161

1162
void findExplicitReferences(const Stmt *S,
1163
                            llvm::function_ref<void(ReferenceLoc)> Out,
1164
                            const HeuristicResolver *Resolver) {
1165
  assert(S);
1166
  ExplicitReferenceCollector(Out, Resolver).TraverseStmt(const_cast<Stmt *>(S));
1167
}
1168
void findExplicitReferences(const Decl *D,
1169
                            llvm::function_ref<void(ReferenceLoc)> Out,
1170
                            const HeuristicResolver *Resolver) {
1171
  assert(D);
1172
  ExplicitReferenceCollector(Out, Resolver).TraverseDecl(const_cast<Decl *>(D));
1173
}
1174
void findExplicitReferences(const ASTContext &AST,
1175
                            llvm::function_ref<void(ReferenceLoc)> Out,
1176
                            const HeuristicResolver *Resolver) {
1177
  ExplicitReferenceCollector(Out, Resolver)
1178
      .TraverseAST(const_cast<ASTContext &>(AST));
1179
}
1180

1181
llvm::raw_ostream &operator<<(llvm::raw_ostream &OS, DeclRelation R) {
1182
  switch (R) {
1183
#define REL_CASE(X)                                                            \
1184
  case DeclRelation::X:                                                        \
1185
    return OS << #X;
1186
    REL_CASE(Alias);
1187
    REL_CASE(Underlying);
1188
    REL_CASE(TemplateInstantiation);
1189
    REL_CASE(TemplatePattern);
1190
#undef REL_CASE
1191
  }
1192
  llvm_unreachable("Unhandled DeclRelation enum");
1193
}
1194
llvm::raw_ostream &operator<<(llvm::raw_ostream &OS, DeclRelationSet RS) {
1195
  const char *Sep = "";
1196
  for (unsigned I = 0; I < RS.S.size(); ++I) {
1197
    if (RS.S.test(I)) {
1198
      OS << Sep << static_cast<DeclRelation>(I);
1199
      Sep = "|";
1200
    }
1201
  }
1202
  return OS;
1203
}
1204

1205
llvm::raw_ostream &operator<<(llvm::raw_ostream &OS, ReferenceLoc R) {
1206
  // note we cannot print R.NameLoc without a source manager.
1207
  OS << "targets = {";
1208
  llvm::SmallVector<std::string> Targets;
1209
  for (const NamedDecl *T : R.Targets) {
1210
    llvm::raw_string_ostream Target(Targets.emplace_back());
1211
    Target << printQualifiedName(*T) << printTemplateSpecializationArgs(*T);
1212
  }
1213
  llvm::sort(Targets);
1214
  OS << llvm::join(Targets, ", ");
1215
  OS << "}";
1216
  if (R.Qualifier) {
1217
    OS << ", qualifier = '";
1218
    R.Qualifier.getNestedNameSpecifier()->print(OS,
1219
                                                PrintingPolicy(LangOptions()));
1220
    OS << "'";
1221
  }
1222
  if (R.IsDecl)
1223
    OS << ", decl";
1224
  return OS;
1225
}
1226

1227
} // namespace clangd
1228
} // namespace clang
1229