llvm-project

1
//===--- AST.cpp - Utility AST functions  -----------------------*- C++ -*-===//
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 "AST.h"
10

11
#include "SourceCode.h"
12
#include "clang/AST/ASTContext.h"
13
#include "clang/AST/ASTTypeTraits.h"
14
#include "clang/AST/Decl.h"
15
#include "clang/AST/DeclBase.h"
16
#include "clang/AST/DeclCXX.h"
17
#include "clang/AST/DeclObjC.h"
18
#include "clang/AST/DeclTemplate.h"
19
#include "clang/AST/DeclarationName.h"
20
#include "clang/AST/ExprCXX.h"
21
#include "clang/AST/NestedNameSpecifier.h"
22
#include "clang/AST/PrettyPrinter.h"
23
#include "clang/AST/RecursiveASTVisitor.h"
24
#include "clang/AST/Stmt.h"
25
#include "clang/AST/TemplateBase.h"
26
#include "clang/AST/TypeLoc.h"
27
#include "clang/Basic/Builtins.h"
28
#include "clang/Basic/SourceLocation.h"
29
#include "clang/Basic/SourceManager.h"
30
#include "clang/Basic/Specifiers.h"
31
#include "clang/Index/USRGeneration.h"
32
#include "llvm/ADT/ArrayRef.h"
33
#include "llvm/ADT/STLExtras.h"
34
#include "llvm/ADT/SmallSet.h"
35
#include "llvm/ADT/StringRef.h"
36
#include "llvm/Support/Casting.h"
37
#include "llvm/Support/raw_ostream.h"
38
#include <iterator>
39
#include <optional>
40
#include <string>
41
#include <vector>
42

43
namespace clang {
44
namespace clangd {
45

46
namespace {
47
std::optional<llvm::ArrayRef<TemplateArgumentLoc>>
48
getTemplateSpecializationArgLocs(const NamedDecl &ND) {
49
  if (auto *Func = llvm::dyn_cast<FunctionDecl>(&ND)) {
50
    if (const ASTTemplateArgumentListInfo *Args =
51
            Func->getTemplateSpecializationArgsAsWritten())
52
      return Args->arguments();
53
  } else if (auto *Cls = llvm::dyn_cast<ClassTemplateSpecializationDecl>(&ND)) {
54
    if (auto *Args = Cls->getTemplateArgsAsWritten())
55
      return Args->arguments();
56
  } else if (auto *Var = llvm::dyn_cast<VarTemplateSpecializationDecl>(&ND)) {
57
    if (auto *Args = Var->getTemplateArgsAsWritten())
58
      return Args->arguments();
59
  }
60
  // We return std::nullopt for ClassTemplateSpecializationDecls because it does
61
  // not contain TemplateArgumentLoc information.
62
  return std::nullopt;
63
}
64

65
template <class T>
66
bool isTemplateSpecializationKind(const NamedDecl *D,
67
                                  TemplateSpecializationKind Kind) {
68
  if (const auto *TD = dyn_cast<T>(D))
69
    return TD->getTemplateSpecializationKind() == Kind;
70
  return false;
71
}
72

73
bool isTemplateSpecializationKind(const NamedDecl *D,
74
                                  TemplateSpecializationKind Kind) {
75
  return isTemplateSpecializationKind<FunctionDecl>(D, Kind) ||
76
         isTemplateSpecializationKind<CXXRecordDecl>(D, Kind) ||
77
         isTemplateSpecializationKind<VarDecl>(D, Kind);
78
}
79

80
// Store all UsingDirectiveDecls in parent contexts of DestContext, that were
81
// introduced before InsertionPoint.
82
llvm::DenseSet<const NamespaceDecl *>
83
getUsingNamespaceDirectives(const DeclContext *DestContext,
84
                            SourceLocation Until) {
85
  const auto &SM = DestContext->getParentASTContext().getSourceManager();
86
  llvm::DenseSet<const NamespaceDecl *> VisibleNamespaceDecls;
87
  for (const auto *DC = DestContext; DC; DC = DC->getLookupParent()) {
88
    for (const auto *D : DC->decls()) {
89
      if (!SM.isWrittenInSameFile(D->getLocation(), Until) ||
90
          !SM.isBeforeInTranslationUnit(D->getLocation(), Until))
91
        continue;
92
      if (auto *UDD = llvm::dyn_cast<UsingDirectiveDecl>(D))
93
        VisibleNamespaceDecls.insert(
94
            UDD->getNominatedNamespace()->getCanonicalDecl());
95
    }
96
  }
97
  return VisibleNamespaceDecls;
98
}
99

100
// Goes over all parents of SourceContext until we find a common ancestor for
101
// DestContext and SourceContext. Any qualifier including and above common
102
// ancestor is redundant, therefore we stop at lowest common ancestor.
103
// In addition to that stops early whenever IsVisible returns true. This can be
104
// used to implement support for "using namespace" decls.
105
std::string
106
getQualification(ASTContext &Context, const DeclContext *DestContext,
107
                 const DeclContext *SourceContext,
108
                 llvm::function_ref<bool(NestedNameSpecifier *)> IsVisible) {
109
  std::vector<const NestedNameSpecifier *> Parents;
110
  bool ReachedNS = false;
111
  for (const DeclContext *CurContext = SourceContext; CurContext;
112
       CurContext = CurContext->getLookupParent()) {
113
    // Stop once we reach a common ancestor.
114
    if (CurContext->Encloses(DestContext))
115
      break;
116

117
    NestedNameSpecifier *NNS = nullptr;
118
    if (auto *TD = llvm::dyn_cast<TagDecl>(CurContext)) {
119
      // There can't be any more tag parents after hitting a namespace.
120
      assert(!ReachedNS);
121
      (void)ReachedNS;
122
      NNS = NestedNameSpecifier::Create(Context, nullptr, false,
123
                                        TD->getTypeForDecl());
124
    } else if (auto *NSD = llvm::dyn_cast<NamespaceDecl>(CurContext)) {
125
      ReachedNS = true;
126
      NNS = NestedNameSpecifier::Create(Context, nullptr, NSD);
127
      // Anonymous and inline namespace names are not spelled while qualifying
128
      // a name, so skip those.
129
      if (NSD->isAnonymousNamespace() || NSD->isInlineNamespace())
130
        continue;
131
    } else {
132
      // Other types of contexts cannot be spelled in code, just skip over
133
      // them.
134
      continue;
135
    }
136
    // Stop if this namespace is already visible at DestContext.
137
    if (IsVisible(NNS))
138
      break;
139

140
    Parents.push_back(NNS);
141
  }
142

143
  // Go over name-specifiers in reverse order to create necessary qualification,
144
  // since we stored inner-most parent first.
145
  std::string Result;
146
  llvm::raw_string_ostream OS(Result);
147
  for (const auto *Parent : llvm::reverse(Parents))
148
    Parent->print(OS, Context.getPrintingPolicy());
149
  return OS.str();
150
}
151

152
} // namespace
153

154
bool isImplicitTemplateInstantiation(const NamedDecl *D) {
155
  return isTemplateSpecializationKind(D, TSK_ImplicitInstantiation);
156
}
157

158
bool isExplicitTemplateSpecialization(const NamedDecl *D) {
159
  return isTemplateSpecializationKind(D, TSK_ExplicitSpecialization);
160
}
161

162
bool isImplementationDetail(const Decl *D) {
163
  return !isSpelledInSource(D->getLocation(),
164
                            D->getASTContext().getSourceManager());
165
}
166

167
SourceLocation nameLocation(const clang::Decl &D, const SourceManager &SM) {
168
  auto L = D.getLocation();
169
  // For `- (void)foo` we want `foo` not the `-`.
170
  if (const auto *MD = dyn_cast<ObjCMethodDecl>(&D))
171
    L = MD->getSelectorStartLoc();
172
  if (isSpelledInSource(L, SM))
173
    return SM.getSpellingLoc(L);
174
  return SM.getExpansionLoc(L);
175
}
176

177
std::string printQualifiedName(const NamedDecl &ND) {
178
  std::string QName;
179
  llvm::raw_string_ostream OS(QName);
180
  PrintingPolicy Policy(ND.getASTContext().getLangOpts());
181
  // Note that inline namespaces are treated as transparent scopes. This
182
  // reflects the way they're most commonly used for lookup. Ideally we'd
183
  // include them, but at query time it's hard to find all the inline
184
  // namespaces to query: the preamble doesn't have a dedicated list.
185
  Policy.SuppressUnwrittenScope = true;
186
  // (unnamed struct), not (unnamed struct at /path/to/foo.cc:42:1).
187
  // In clangd, context is usually available and paths are mostly noise.
188
  Policy.AnonymousTagLocations = false;
189
  ND.printQualifiedName(OS, Policy);
190
  OS.flush();
191
  assert(!StringRef(QName).starts_with("::"));
192
  return QName;
193
}
194

195
static bool isAnonymous(const DeclarationName &N) {
196
  return N.isIdentifier() && !N.getAsIdentifierInfo();
197
}
198

199
NestedNameSpecifierLoc getQualifierLoc(const NamedDecl &ND) {
200
  if (auto *V = llvm::dyn_cast<DeclaratorDecl>(&ND))
201
    return V->getQualifierLoc();
202
  if (auto *T = llvm::dyn_cast<TagDecl>(&ND))
203
    return T->getQualifierLoc();
204
  return NestedNameSpecifierLoc();
205
}
206

207
std::string printUsingNamespaceName(const ASTContext &Ctx,
208
                                    const UsingDirectiveDecl &D) {
209
  PrintingPolicy PP(Ctx.getLangOpts());
210
  std::string Name;
211
  llvm::raw_string_ostream Out(Name);
212

213
  if (auto *Qual = D.getQualifier())
214
    Qual->print(Out, PP);
215
  D.getNominatedNamespaceAsWritten()->printName(Out);
216
  return Out.str();
217
}
218

219
std::string printName(const ASTContext &Ctx, const NamedDecl &ND) {
220
  std::string Name;
221
  llvm::raw_string_ostream Out(Name);
222
  PrintingPolicy PP(Ctx.getLangOpts());
223
  // We don't consider a class template's args part of the constructor name.
224
  PP.SuppressTemplateArgsInCXXConstructors = true;
225

226
  // Handle 'using namespace'. They all have the same name - <using-directive>.
227
  if (auto *UD = llvm::dyn_cast<UsingDirectiveDecl>(&ND)) {
228
    Out << "using namespace ";
229
    if (auto *Qual = UD->getQualifier())
230
      Qual->print(Out, PP);
231
    UD->getNominatedNamespaceAsWritten()->printName(Out);
232
    return Out.str();
233
  }
234

235
  if (isAnonymous(ND.getDeclName())) {
236
    // Come up with a presentation for an anonymous entity.
237
    if (isa<NamespaceDecl>(ND))
238
      return "(anonymous namespace)";
239
    if (auto *Cls = llvm::dyn_cast<RecordDecl>(&ND)) {
240
      if (Cls->isLambda())
241
        return "(lambda)";
242
      return ("(anonymous " + Cls->getKindName() + ")").str();
243
    }
244
    if (isa<EnumDecl>(ND))
245
      return "(anonymous enum)";
246
    return "(anonymous)";
247
  }
248

249
  // Print nested name qualifier if it was written in the source code.
250
  if (auto *Qualifier = getQualifierLoc(ND).getNestedNameSpecifier())
251
    Qualifier->print(Out, PP);
252
  // Print the name itself.
253
  ND.getDeclName().print(Out, PP);
254
  // Print template arguments.
255
  Out << printTemplateSpecializationArgs(ND);
256

257
  return Out.str();
258
}
259

260
std::string printTemplateSpecializationArgs(const NamedDecl &ND) {
261
  std::string TemplateArgs;
262
  llvm::raw_string_ostream OS(TemplateArgs);
263
  PrintingPolicy Policy(ND.getASTContext().getLangOpts());
264
  if (std::optional<llvm::ArrayRef<TemplateArgumentLoc>> Args =
265
          getTemplateSpecializationArgLocs(ND)) {
266
    printTemplateArgumentList(OS, *Args, Policy);
267
  } else if (auto *Cls = llvm::dyn_cast<ClassTemplateSpecializationDecl>(&ND)) {
268
    // FIXME: Fix cases when getTypeAsWritten returns null inside clang AST,
269
    // e.g. friend decls. Currently we fallback to Template Arguments without
270
    // location information.
271
    printTemplateArgumentList(OS, Cls->getTemplateArgs().asArray(), Policy);
272
  }
273
  OS.flush();
274
  return TemplateArgs;
275
}
276

277
std::string printNamespaceScope(const DeclContext &DC) {
278
  for (const auto *Ctx = &DC; Ctx != nullptr; Ctx = Ctx->getParent())
279
    if (const auto *NS = dyn_cast<NamespaceDecl>(Ctx))
280
      if (!NS->isAnonymousNamespace() && !NS->isInlineNamespace())
281
        return printQualifiedName(*NS) + "::";
282
  return "";
283
}
284

285
static llvm::StringRef
286
getNameOrErrForObjCInterface(const ObjCInterfaceDecl *ID) {
287
  return ID ? ID->getName() : "<<error-type>>";
288
}
289

290
std::string printObjCMethod(const ObjCMethodDecl &Method) {
291
  std::string Name;
292
  llvm::raw_string_ostream OS(Name);
293

294
  OS << (Method.isInstanceMethod() ? '-' : '+') << '[';
295

296
  // Should always be true.
297
  if (const ObjCContainerDecl *C =
298
          dyn_cast<ObjCContainerDecl>(Method.getDeclContext()))
299
    OS << printObjCContainer(*C);
300

301
  Method.getSelector().print(OS << ' ');
302
  if (Method.isVariadic())
303
    OS << ", ...";
304

305
  OS << ']';
306
  OS.flush();
307
  return Name;
308
}
309

310
std::string printObjCContainer(const ObjCContainerDecl &C) {
311
  if (const ObjCCategoryDecl *Category = dyn_cast<ObjCCategoryDecl>(&C)) {
312
    std::string Name;
313
    llvm::raw_string_ostream OS(Name);
314
    const ObjCInterfaceDecl *Class = Category->getClassInterface();
315
    OS << getNameOrErrForObjCInterface(Class) << '(' << Category->getName()
316
       << ')';
317
    OS.flush();
318
    return Name;
319
  }
320
  if (const ObjCCategoryImplDecl *CID = dyn_cast<ObjCCategoryImplDecl>(&C)) {
321
    std::string Name;
322
    llvm::raw_string_ostream OS(Name);
323
    const ObjCInterfaceDecl *Class = CID->getClassInterface();
324
    OS << getNameOrErrForObjCInterface(Class) << '(' << CID->getName() << ')';
325
    OS.flush();
326
    return Name;
327
  }
328
  return C.getNameAsString();
329
}
330

331
SymbolID getSymbolID(const Decl *D) {
332
  llvm::SmallString<128> USR;
333
  if (index::generateUSRForDecl(D, USR))
334
    return {};
335
  return SymbolID(USR);
336
}
337

338
SymbolID getSymbolID(const llvm::StringRef MacroName, const MacroInfo *MI,
339
                     const SourceManager &SM) {
340
  if (MI == nullptr)
341
    return {};
342
  llvm::SmallString<128> USR;
343
  if (index::generateUSRForMacro(MacroName, MI->getDefinitionLoc(), SM, USR))
344
    return {};
345
  return SymbolID(USR);
346
}
347

348
const ObjCImplDecl *getCorrespondingObjCImpl(const ObjCContainerDecl *D) {
349
  if (const auto *ID = dyn_cast<ObjCInterfaceDecl>(D))
350
    return ID->getImplementation();
351
  if (const auto *CD = dyn_cast<ObjCCategoryDecl>(D)) {
352
    if (CD->IsClassExtension()) {
353
      if (const auto *ID = CD->getClassInterface())
354
        return ID->getImplementation();
355
      return nullptr;
356
    }
357
    return CD->getImplementation();
358
  }
359
  return nullptr;
360
}
361

362
Symbol::IncludeDirective
363
preferredIncludeDirective(llvm::StringRef FileName, const LangOptions &LangOpts,
364
                          ArrayRef<Inclusion> MainFileIncludes,
365
                          ArrayRef<const Decl *> TopLevelDecls) {
366
  // Always prefer #include for non-ObjC code.
367
  if (!LangOpts.ObjC)
368
    return Symbol::IncludeDirective::Include;
369
  // If this is not a header file and has ObjC set as the language, prefer
370
  // #import.
371
  if (!isHeaderFile(FileName, LangOpts))
372
    return Symbol::IncludeDirective::Import;
373

374
  // Headers lack proper compile flags most of the time, so we might treat a
375
  // header as ObjC accidentally. Perform some extra checks to make sure this
376
  // works.
377

378
  // Any file with a #import, should keep #import-ing.
379
  for (auto &Inc : MainFileIncludes)
380
    if (Inc.Directive == tok::pp_import)
381
      return Symbol::IncludeDirective::Import;
382

383
  // Any file declaring an ObjC decl should also be #import-ing.
384
  // No need to look over the references, as the file doesn't have any #imports,
385
  // it must be declaring interesting ObjC-like decls.
386
  for (const Decl *D : TopLevelDecls)
387
    if (isa<ObjCContainerDecl, ObjCIvarDecl, ObjCMethodDecl, ObjCPropertyDecl>(
388
            D))
389
      return Symbol::IncludeDirective::Import;
390

391
  return Symbol::IncludeDirective::Include;
392
}
393

394
std::string printType(const QualType QT, const DeclContext &CurContext,
395
                      const llvm::StringRef Placeholder) {
396
  std::string Result;
397
  llvm::raw_string_ostream OS(Result);
398
  PrintingPolicy PP(CurContext.getParentASTContext().getPrintingPolicy());
399
  PP.SuppressTagKeyword = true;
400
  PP.SuppressUnwrittenScope = true;
401

402
  class PrintCB : public PrintingCallbacks {
403
  public:
404
    PrintCB(const DeclContext *CurContext) : CurContext(CurContext) {}
405
    virtual ~PrintCB() {}
406
    bool isScopeVisible(const DeclContext *DC) const override {
407
      return DC->Encloses(CurContext);
408
    }
409

410
  private:
411
    const DeclContext *CurContext;
412
  };
413
  PrintCB PCB(&CurContext);
414
  PP.Callbacks = &PCB;
415

416
  QT.print(OS, PP, Placeholder);
417
  return OS.str();
418
}
419

420
bool hasReservedName(const Decl &D) {
421
  if (const auto *ND = llvm::dyn_cast<NamedDecl>(&D))
422
    if (const auto *II = ND->getIdentifier())
423
      return isReservedName(II->getName());
424
  return false;
425
}
426

427
bool hasReservedScope(const DeclContext &DC) {
428
  for (const DeclContext *D = &DC; D; D = D->getParent()) {
429
    if (D->isTransparentContext() || D->isInlineNamespace())
430
      continue;
431
    if (const auto *ND = llvm::dyn_cast<NamedDecl>(D))
432
      if (hasReservedName(*ND))
433
        return true;
434
  }
435
  return false;
436
}
437

438
QualType declaredType(const TypeDecl *D) {
439
  ASTContext &Context = D->getASTContext();
440
  if (const auto *CTSD = llvm::dyn_cast<ClassTemplateSpecializationDecl>(D))
441
    if (const auto *Args = CTSD->getTemplateArgsAsWritten())
442
      return Context.getTemplateSpecializationType(
443
          TemplateName(CTSD->getSpecializedTemplate()), Args->arguments());
444
  return Context.getTypeDeclType(D);
445
}
446

447
namespace {
448
/// Computes the deduced type at a given location by visiting the relevant
449
/// nodes. We use this to display the actual type when hovering over an "auto"
450
/// keyword or "decltype()" expression.
451
/// FIXME: This could have been a lot simpler by visiting AutoTypeLocs but it
452
/// seems that the AutoTypeLocs that can be visited along with their AutoType do
453
/// not have the deduced type set. Instead, we have to go to the appropriate
454
/// DeclaratorDecl/FunctionDecl and work our back to the AutoType that does have
455
/// a deduced type set. The AST should be improved to simplify this scenario.
456
class DeducedTypeVisitor : public RecursiveASTVisitor<DeducedTypeVisitor> {
457
  SourceLocation SearchedLocation;
458

459
public:
460
  DeducedTypeVisitor(SourceLocation SearchedLocation)
461
      : SearchedLocation(SearchedLocation) {}
462

463
  // Handle auto initializers:
464
  //- auto i = 1;
465
  //- decltype(auto) i = 1;
466
  //- auto& i = 1;
467
  //- auto* i = &a;
468
  bool VisitDeclaratorDecl(DeclaratorDecl *D) {
469
    if (!D->getTypeSourceInfo() ||
470
        !D->getTypeSourceInfo()->getTypeLoc().getContainedAutoTypeLoc() ||
471
        D->getTypeSourceInfo()
472
                ->getTypeLoc()
473
                .getContainedAutoTypeLoc()
474
                .getNameLoc() != SearchedLocation)
475
      return true;
476

477
    if (auto *AT = D->getType()->getContainedAutoType()) {
478
      DeducedType = AT->desugar();
479
    }
480
    return true;
481
  }
482

483
  // Handle auto return types:
484
  //- auto foo() {}
485
  //- auto& foo() {}
486
  //- auto foo() -> int {}
487
  //- auto foo() -> decltype(1+1) {}
488
  //- operator auto() const { return 10; }
489
  bool VisitFunctionDecl(FunctionDecl *D) {
490
    if (!D->getTypeSourceInfo())
491
      return true;
492
    // Loc of auto in return type (c++14).
493
    auto CurLoc = D->getReturnTypeSourceRange().getBegin();
494
    // Loc of "auto" in operator auto()
495
    if (CurLoc.isInvalid() && isa<CXXConversionDecl>(D))
496
      CurLoc = D->getTypeSourceInfo()->getTypeLoc().getBeginLoc();
497
    // Loc of "auto" in function with trailing return type (c++11).
498
    if (CurLoc.isInvalid())
499
      CurLoc = D->getSourceRange().getBegin();
500
    if (CurLoc != SearchedLocation)
501
      return true;
502

503
    const AutoType *AT = D->getReturnType()->getContainedAutoType();
504
    if (AT && !AT->getDeducedType().isNull()) {
505
      DeducedType = AT->getDeducedType();
506
    } else if (auto *DT = dyn_cast<DecltypeType>(D->getReturnType())) {
507
      // auto in a trailing return type just points to a DecltypeType and
508
      // getContainedAutoType does not unwrap it.
509
      if (!DT->getUnderlyingType().isNull())
510
        DeducedType = DT->getUnderlyingType();
511
    } else if (!D->getReturnType().isNull()) {
512
      DeducedType = D->getReturnType();
513
    }
514
    return true;
515
  }
516

517
  // Handle non-auto decltype, e.g.:
518
  // - auto foo() -> decltype(expr) {}
519
  // - decltype(expr);
520
  bool VisitDecltypeTypeLoc(DecltypeTypeLoc TL) {
521
    if (TL.getBeginLoc() != SearchedLocation)
522
      return true;
523

524
    // A DecltypeType's underlying type can be another DecltypeType! E.g.
525
    //  int I = 0;
526
    //  decltype(I) J = I;
527
    //  decltype(J) K = J;
528
    const DecltypeType *DT = dyn_cast<DecltypeType>(TL.getTypePtr());
529
    while (DT && !DT->getUnderlyingType().isNull()) {
530
      DeducedType = DT->getUnderlyingType();
531
      DT = dyn_cast<DecltypeType>(DeducedType.getTypePtr());
532
    }
533
    return true;
534
  }
535

536
  // Handle functions/lambdas with `auto` typed parameters.
537
  // We deduce the type if there's exactly one instantiation visible.
538
  bool VisitParmVarDecl(ParmVarDecl *PVD) {
539
    if (!PVD->getType()->isDependentType())
540
      return true;
541
    // 'auto' here does not name an AutoType, but an implicit template param.
542
    TemplateTypeParmTypeLoc Auto =
543
        getContainedAutoParamType(PVD->getTypeSourceInfo()->getTypeLoc());
544
    if (Auto.isNull() || Auto.getNameLoc() != SearchedLocation)
545
      return true;
546

547
    // We expect the TTP to be attached to this function template.
548
    // Find the template and the param index.
549
    auto *Templated = llvm::dyn_cast<FunctionDecl>(PVD->getDeclContext());
550
    if (!Templated)
551
      return true;
552
    auto *FTD = Templated->getDescribedFunctionTemplate();
553
    if (!FTD)
554
      return true;
555
    int ParamIndex = paramIndex(*FTD, *Auto.getDecl());
556
    if (ParamIndex < 0) {
557
      assert(false && "auto TTP is not from enclosing function?");
558
      return true;
559
    }
560

561
    // Now find the instantiation and the deduced template type arg.
562
    auto *Instantiation =
563
        llvm::dyn_cast_or_null<FunctionDecl>(getOnlyInstantiation(Templated));
564
    if (!Instantiation)
565
      return true;
566
    const auto *Args = Instantiation->getTemplateSpecializationArgs();
567
    if (Args->size() != FTD->getTemplateParameters()->size())
568
      return true; // no weird variadic stuff
569
    DeducedType = Args->get(ParamIndex).getAsType();
570
    return true;
571
  }
572

573
  static int paramIndex(const TemplateDecl &TD, NamedDecl &Param) {
574
    unsigned I = 0;
575
    for (auto *ND : *TD.getTemplateParameters()) {
576
      if (&Param == ND)
577
        return I;
578
      ++I;
579
    }
580
    return -1;
581
  }
582

583
  QualType DeducedType;
584
};
585
} // namespace
586

587
std::optional<QualType> getDeducedType(ASTContext &ASTCtx, SourceLocation Loc) {
588
  if (!Loc.isValid())
589
    return {};
590
  DeducedTypeVisitor V(Loc);
591
  V.TraverseAST(ASTCtx);
592
  if (V.DeducedType.isNull())
593
    return std::nullopt;
594
  return V.DeducedType;
595
}
596

597
TemplateTypeParmTypeLoc getContainedAutoParamType(TypeLoc TL) {
598
  if (auto QTL = TL.getAs<QualifiedTypeLoc>())
599
    return getContainedAutoParamType(QTL.getUnqualifiedLoc());
600
  if (llvm::isa<PointerType, ReferenceType, ParenType>(TL.getTypePtr()))
601
    return getContainedAutoParamType(TL.getNextTypeLoc());
602
  if (auto FTL = TL.getAs<FunctionTypeLoc>())
603
    return getContainedAutoParamType(FTL.getReturnLoc());
604
  if (auto TTPTL = TL.getAs<TemplateTypeParmTypeLoc>()) {
605
    if (TTPTL.getTypePtr()->getDecl()->isImplicit())
606
      return TTPTL;
607
  }
608
  return {};
609
}
610

611
template <typename TemplateDeclTy>
612
static NamedDecl *getOnlyInstantiationImpl(TemplateDeclTy *TD) {
613
  NamedDecl *Only = nullptr;
614
  for (auto *Spec : TD->specializations()) {
615
    if (Spec->getTemplateSpecializationKind() == TSK_ExplicitSpecialization)
616
      continue;
617
    if (Only != nullptr)
618
      return nullptr;
619
    Only = Spec;
620
  }
621
  return Only;
622
}
623

624
NamedDecl *getOnlyInstantiation(NamedDecl *TemplatedDecl) {
625
  if (TemplateDecl *TD = TemplatedDecl->getDescribedTemplate()) {
626
    if (auto *CTD = llvm::dyn_cast<ClassTemplateDecl>(TD))
627
      return getOnlyInstantiationImpl(CTD);
628
    if (auto *FTD = llvm::dyn_cast<FunctionTemplateDecl>(TD))
629
      return getOnlyInstantiationImpl(FTD);
630
    if (auto *VTD = llvm::dyn_cast<VarTemplateDecl>(TD))
631
      return getOnlyInstantiationImpl(VTD);
632
  }
633
  return nullptr;
634
}
635

636
std::vector<const Attr *> getAttributes(const DynTypedNode &N) {
637
  std::vector<const Attr *> Result;
638
  if (const auto *TL = N.get<TypeLoc>()) {
639
    for (AttributedTypeLoc ATL = TL->getAs<AttributedTypeLoc>(); !ATL.isNull();
640
         ATL = ATL.getModifiedLoc().getAs<AttributedTypeLoc>()) {
641
      if (const Attr *A = ATL.getAttr())
642
        Result.push_back(A);
643
      assert(!ATL.getModifiedLoc().isNull());
644
    }
645
  }
646
  if (const auto *S = N.get<AttributedStmt>()) {
647
    for (; S != nullptr; S = dyn_cast<AttributedStmt>(S->getSubStmt()))
648
      for (const Attr *A : S->getAttrs())
649
        if (A)
650
          Result.push_back(A);
651
  }
652
  if (const auto *D = N.get<Decl>()) {
653
    for (const Attr *A : D->attrs())
654
      if (A)
655
        Result.push_back(A);
656
  }
657
  return Result;
658
}
659

660
std::string getQualification(ASTContext &Context,
661
                             const DeclContext *DestContext,
662
                             SourceLocation InsertionPoint,
663
                             const NamedDecl *ND) {
664
  auto VisibleNamespaceDecls =
665
      getUsingNamespaceDirectives(DestContext, InsertionPoint);
666
  return getQualification(
667
      Context, DestContext, ND->getDeclContext(),
668
      [&](NestedNameSpecifier *NNS) {
669
        if (NNS->getKind() != NestedNameSpecifier::Namespace)
670
          return false;
671
        const auto *CanonNSD = NNS->getAsNamespace()->getCanonicalDecl();
672
        return llvm::any_of(VisibleNamespaceDecls,
673
                            [CanonNSD](const NamespaceDecl *NSD) {
674
                              return NSD->getCanonicalDecl() == CanonNSD;
675
                            });
676
      });
677
}
678

679
std::string getQualification(ASTContext &Context,
680
                             const DeclContext *DestContext,
681
                             const NamedDecl *ND,
682
                             llvm::ArrayRef<std::string> VisibleNamespaces) {
683
  for (llvm::StringRef NS : VisibleNamespaces) {
684
    assert(NS.ends_with("::"));
685
    (void)NS;
686
  }
687
  return getQualification(
688
      Context, DestContext, ND->getDeclContext(),
689
      [&](NestedNameSpecifier *NNS) {
690
        return llvm::any_of(VisibleNamespaces, [&](llvm::StringRef Namespace) {
691
          std::string NS;
692
          llvm::raw_string_ostream OS(NS);
693
          NNS->print(OS, Context.getPrintingPolicy());
694
          return OS.str() == Namespace;
695
        });
696
      });
697
}
698

699
bool hasUnstableLinkage(const Decl *D) {
700
  // Linkage of a ValueDecl depends on the type.
701
  // If that's not deduced yet, deducing it may change the linkage.
702
  auto *VD = llvm::dyn_cast_or_null<ValueDecl>(D);
703
  return VD && !VD->getType().isNull() && VD->getType()->isUndeducedType();
704
}
705

706
bool isDeeplyNested(const Decl *D, unsigned MaxDepth) {
707
  size_t ContextDepth = 0;
708
  for (auto *Ctx = D->getDeclContext(); Ctx && !Ctx->isTranslationUnit();
709
       Ctx = Ctx->getParent()) {
710
    if (++ContextDepth == MaxDepth)
711
      return true;
712
  }
713
  return false;
714
}
715

716
namespace {
717

718
// returns true for `X` in `template <typename... X> void foo()`
719
bool isTemplateTypeParameterPack(NamedDecl *D) {
720
  if (const auto *TTPD = dyn_cast<TemplateTypeParmDecl>(D)) {
721
    return TTPD->isParameterPack();
722
  }
723
  return false;
724
}
725

726
// Returns the template parameter pack type from an instantiated function
727
// template, if it exists, nullptr otherwise.
728
const TemplateTypeParmType *getFunctionPackType(const FunctionDecl *Callee) {
729
  if (const auto *TemplateDecl = Callee->getPrimaryTemplate()) {
730
    auto TemplateParams = TemplateDecl->getTemplateParameters()->asArray();
731
    // find the template parameter pack from the back
732
    const auto It = std::find_if(TemplateParams.rbegin(), TemplateParams.rend(),
733
                                 isTemplateTypeParameterPack);
734
    if (It != TemplateParams.rend()) {
735
      const auto *TTPD = dyn_cast<TemplateTypeParmDecl>(*It);
736
      return TTPD->getTypeForDecl()->castAs<TemplateTypeParmType>();
737
    }
738
  }
739
  return nullptr;
740
}
741

742
// Returns the template parameter pack type that this parameter was expanded
743
// from (if in the Args... or Args&... or Args&&... form), if this is the case,
744
// nullptr otherwise.
745
const TemplateTypeParmType *getUnderlyingPackType(const ParmVarDecl *Param) {
746
  const auto *PlainType = Param->getType().getTypePtr();
747
  if (auto *RT = dyn_cast<ReferenceType>(PlainType))
748
    PlainType = RT->getPointeeTypeAsWritten().getTypePtr();
749
  if (const auto *SubstType = dyn_cast<SubstTemplateTypeParmType>(PlainType)) {
750
    const auto *ReplacedParameter = SubstType->getReplacedParameter();
751
    if (ReplacedParameter->isParameterPack()) {
752
      return ReplacedParameter->getTypeForDecl()
753
          ->castAs<TemplateTypeParmType>();
754
    }
755
  }
756
  return nullptr;
757
}
758

759
// This visitor walks over the body of an instantiated function template.
760
// The template accepts a parameter pack and the visitor records whether
761
// the pack parameters were forwarded to another call. For example, given:
762
//
763
// template <typename T, typename... Args>
764
// auto make_unique(Args... args) {
765
//   return unique_ptr<T>(new T(args...));
766
// }
767
//
768
// When called as `make_unique<std::string>(2, 'x')` this yields a function
769
// `make_unique<std::string, int, char>` with two parameters.
770
// The visitor records that those two parameters are forwarded to the
771
// `constructor std::string(int, char);`.
772
//
773
// This information is recorded in the `ForwardingInfo` split into fully
774
// resolved parameters (passed as argument to a parameter that is not an
775
// expanded template type parameter pack) and forwarding parameters (passed to a
776
// parameter that is an expanded template type parameter pack).
777
class ForwardingCallVisitor
778
    : public RecursiveASTVisitor<ForwardingCallVisitor> {
779
public:
780
  ForwardingCallVisitor(ArrayRef<const ParmVarDecl *> Parameters)
781
      : Parameters{Parameters},
782
        PackType{getUnderlyingPackType(Parameters.front())} {}
783

784
  bool VisitCallExpr(CallExpr *E) {
785
    auto *Callee = getCalleeDeclOrUniqueOverload(E);
786
    if (Callee) {
787
      handleCall(Callee, E->arguments());
788
    }
789
    return !Info.has_value();
790
  }
791

792
  bool VisitCXXConstructExpr(CXXConstructExpr *E) {
793
    auto *Callee = E->getConstructor();
794
    if (Callee) {
795
      handleCall(Callee, E->arguments());
796
    }
797
    return !Info.has_value();
798
  }
799

800
  // The expanded parameter pack to be resolved
801
  ArrayRef<const ParmVarDecl *> Parameters;
802
  // The type of the parameter pack
803
  const TemplateTypeParmType *PackType;
804

805
  struct ForwardingInfo {
806
    // If the parameters were resolved to another FunctionDecl, these are its
807
    // first non-variadic parameters (i.e. the first entries of the parameter
808
    // pack that are passed as arguments bound to a non-pack parameter.)
809
    ArrayRef<const ParmVarDecl *> Head;
810
    // If the parameters were resolved to another FunctionDecl, these are its
811
    // variadic parameters (i.e. the entries of the parameter pack that are
812
    // passed as arguments bound to a pack parameter.)
813
    ArrayRef<const ParmVarDecl *> Pack;
814
    // If the parameters were resolved to another FunctionDecl, these are its
815
    // last non-variadic parameters (i.e. the last entries of the parameter pack
816
    // that are passed as arguments bound to a non-pack parameter.)
817
    ArrayRef<const ParmVarDecl *> Tail;
818
    // If the parameters were resolved to another forwarding FunctionDecl, this
819
    // is it.
820
    std::optional<FunctionDecl *> PackTarget;
821
  };
822

823
  // The output of this visitor
824
  std::optional<ForwardingInfo> Info;
825

826
private:
827
  // inspects the given callee with the given args to check whether it
828
  // contains Parameters, and sets Info accordingly.
829
  void handleCall(FunctionDecl *Callee, typename CallExpr::arg_range Args) {
830
    // Skip functions with less parameters, they can't be the target.
831
    if (Callee->parameters().size() < Parameters.size())
832
      return;
833
    if (llvm::any_of(Args,
834
                     [](const Expr *E) { return isa<PackExpansionExpr>(E); })) {
835
      return;
836
    }
837
    auto PackLocation = findPack(Args);
838
    if (!PackLocation)
839
      return;
840
    ArrayRef<ParmVarDecl *> MatchingParams =
841
        Callee->parameters().slice(*PackLocation, Parameters.size());
842
    // Check whether the function has a parameter pack as the last template
843
    // parameter
844
    if (const auto *TTPT = getFunctionPackType(Callee)) {
845
      // In this case: Separate the parameters into head, pack and tail
846
      auto IsExpandedPack = [&](const ParmVarDecl *P) {
847
        return getUnderlyingPackType(P) == TTPT;
848
      };
849
      ForwardingInfo FI;
850
      FI.Head = MatchingParams.take_until(IsExpandedPack);
851
      FI.Pack =
852
          MatchingParams.drop_front(FI.Head.size()).take_while(IsExpandedPack);
853
      FI.Tail = MatchingParams.drop_front(FI.Head.size() + FI.Pack.size());
854
      FI.PackTarget = Callee;
855
      Info = FI;
856
      return;
857
    }
858
    // Default case: assume all parameters were fully resolved
859
    ForwardingInfo FI;
860
    FI.Head = MatchingParams;
861
    Info = FI;
862
  }
863

864
  // Returns the beginning of the expanded pack represented by Parameters
865
  // in the given arguments, if it is there.
866
  std::optional<size_t> findPack(typename CallExpr::arg_range Args) {
867
    // find the argument directly referring to the first parameter
868
    assert(Parameters.size() <= static_cast<size_t>(llvm::size(Args)));
869
    for (auto Begin = Args.begin(), End = Args.end() - Parameters.size() + 1;
870
         Begin != End; ++Begin) {
871
      if (const auto *RefArg = unwrapForward(*Begin)) {
872
        if (Parameters.front() != RefArg->getDecl())
873
          continue;
874
        // Check that this expands all the way until the last parameter.
875
        // It's enough to look at the last parameter, because it isn't possible
876
        // to expand without expanding all of them.
877
        auto ParamEnd = Begin + Parameters.size() - 1;
878
        RefArg = unwrapForward(*ParamEnd);
879
        if (!RefArg || Parameters.back() != RefArg->getDecl())
880
          continue;
881
        return std::distance(Args.begin(), Begin);
882
      }
883
    }
884
    return std::nullopt;
885
  }
886

887
  static FunctionDecl *getCalleeDeclOrUniqueOverload(CallExpr *E) {
888
    Decl *CalleeDecl = E->getCalleeDecl();
889
    auto *Callee = dyn_cast_or_null<FunctionDecl>(CalleeDecl);
890
    if (!Callee) {
891
      if (auto *Lookup = dyn_cast<UnresolvedLookupExpr>(E->getCallee())) {
892
        Callee = resolveOverload(Lookup, E);
893
      }
894
    }
895
    // Ignore the callee if the number of arguments is wrong (deal with va_args)
896
    if (Callee && Callee->getNumParams() == E->getNumArgs())
897
      return Callee;
898
    return nullptr;
899
  }
900

901
  static FunctionDecl *resolveOverload(UnresolvedLookupExpr *Lookup,
902
                                       CallExpr *E) {
903
    FunctionDecl *MatchingDecl = nullptr;
904
    if (!Lookup->requiresADL()) {
905
      // Check whether there is a single overload with this number of
906
      // parameters
907
      for (auto *Candidate : Lookup->decls()) {
908
        if (auto *FuncCandidate = dyn_cast_or_null<FunctionDecl>(Candidate)) {
909
          if (FuncCandidate->getNumParams() == E->getNumArgs()) {
910
            if (MatchingDecl) {
911
              // there are multiple candidates - abort
912
              return nullptr;
913
            }
914
            MatchingDecl = FuncCandidate;
915
          }
916
        }
917
      }
918
    }
919
    return MatchingDecl;
920
  }
921

922
  // Tries to get to the underlying argument by unwrapping implicit nodes and
923
  // std::forward.
924
  static const DeclRefExpr *unwrapForward(const Expr *E) {
925
    E = E->IgnoreImplicitAsWritten();
926
    // There might be an implicit copy/move constructor call on top of the
927
    // forwarded arg.
928
    // FIXME: Maybe mark implicit calls in the AST to properly filter here.
929
    if (const auto *Const = dyn_cast<CXXConstructExpr>(E))
930
      if (Const->getConstructor()->isCopyOrMoveConstructor())
931
        E = Const->getArg(0)->IgnoreImplicitAsWritten();
932
    if (const auto *Call = dyn_cast<CallExpr>(E)) {
933
      const auto Callee = Call->getBuiltinCallee();
934
      if (Callee == Builtin::BIforward) {
935
        return dyn_cast<DeclRefExpr>(
936
            Call->getArg(0)->IgnoreImplicitAsWritten());
937
      }
938
    }
939
    return dyn_cast<DeclRefExpr>(E);
940
  }
941
};
942

943
} // namespace
944

945
SmallVector<const ParmVarDecl *>
946
resolveForwardingParameters(const FunctionDecl *D, unsigned MaxDepth) {
947
  auto Parameters = D->parameters();
948
  // If the function has a template parameter pack
949
  if (const auto *TTPT = getFunctionPackType(D)) {
950
    // Split the parameters into head, pack and tail
951
    auto IsExpandedPack = [TTPT](const ParmVarDecl *P) {
952
      return getUnderlyingPackType(P) == TTPT;
953
    };
954
    ArrayRef<const ParmVarDecl *> Head = Parameters.take_until(IsExpandedPack);
955
    ArrayRef<const ParmVarDecl *> Pack =
956
        Parameters.drop_front(Head.size()).take_while(IsExpandedPack);
957
    ArrayRef<const ParmVarDecl *> Tail =
958
        Parameters.drop_front(Head.size() + Pack.size());
959
    SmallVector<const ParmVarDecl *> Result(Parameters.size());
960
    // Fill in non-pack parameters
961
    auto *HeadIt = std::copy(Head.begin(), Head.end(), Result.begin());
962
    auto TailIt = std::copy(Tail.rbegin(), Tail.rend(), Result.rbegin());
963
    // Recurse on pack parameters
964
    size_t Depth = 0;
965
    const FunctionDecl *CurrentFunction = D;
966
    llvm::SmallSet<const FunctionTemplateDecl *, 4> SeenTemplates;
967
    if (const auto *Template = D->getPrimaryTemplate()) {
968
      SeenTemplates.insert(Template);
969
    }
970
    while (!Pack.empty() && CurrentFunction && Depth < MaxDepth) {
971
      // Find call expressions involving the pack
972
      ForwardingCallVisitor V{Pack};
973
      V.TraverseStmt(CurrentFunction->getBody());
974
      if (!V.Info) {
975
        break;
976
      }
977
      // If we found something: Fill in non-pack parameters
978
      auto Info = *V.Info;
979
      HeadIt = std::copy(Info.Head.begin(), Info.Head.end(), HeadIt);
980
      TailIt = std::copy(Info.Tail.rbegin(), Info.Tail.rend(), TailIt);
981
      // Prepare next recursion level
982
      Pack = Info.Pack;
983
      CurrentFunction = Info.PackTarget.value_or(nullptr);
984
      Depth++;
985
      // If we are recursing into a previously encountered function: Abort
986
      if (CurrentFunction) {
987
        if (const auto *Template = CurrentFunction->getPrimaryTemplate()) {
988
          bool NewFunction = SeenTemplates.insert(Template).second;
989
          if (!NewFunction) {
990
            return {Parameters.begin(), Parameters.end()};
991
          }
992
        }
993
      }
994
    }
995
    // Fill in the remaining unresolved pack parameters
996
    HeadIt = std::copy(Pack.begin(), Pack.end(), HeadIt);
997
    assert(TailIt.base() == HeadIt);
998
    return Result;
999
  }
1000
  return {Parameters.begin(), Parameters.end()};
1001
}
1002

1003
bool isExpandedFromParameterPack(const ParmVarDecl *D) {
1004
  return getUnderlyingPackType(D) != nullptr;
1005
}
1006

1007
} // namespace clangd
1008
} // namespace clang
1009