clang-tools-extra/clangd/AST.cpp

   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 =
  54                  llvm::dyn_cast<ClassTemplatePartialSpecializationDecl>(&ND)) {
  55     if (auto *Args = Cls->getTemplateArgsAsWritten())
  56       return Args->arguments();
  57   } else if (auto *Var =
  58                  llvm::dyn_cast<VarTemplatePartialSpecializationDecl>(&ND)) {
  59     if (auto *Args = Var->getTemplateArgsAsWritten())
  60       return Args->arguments();
  61   } else if (auto *Var = llvm::dyn_cast<VarTemplateSpecializationDecl>(&ND)) {
  62     if (auto *Args = Var->getTemplateArgsInfo())
  63       return Args->arguments();
  64   }
  65   // We return std::nullopt for ClassTemplateSpecializationDecls because it does
  66   // not contain TemplateArgumentLoc information.
  67   return std::nullopt;
  68 }
  69
  70 template <class T>
  71 bool isTemplateSpecializationKind(const NamedDecl *D,
  72                                   TemplateSpecializationKind Kind) {
  73   if (const auto *TD = dyn_cast<T>(D))
  74     return TD->getTemplateSpecializationKind() == Kind;
  75   return false;
  76 }
  77
  78 bool isTemplateSpecializationKind(const NamedDecl *D,
  79                                   TemplateSpecializationKind Kind) {
  80   return isTemplateSpecializationKind<FunctionDecl>(D, Kind) ||
  81          isTemplateSpecializationKind<CXXRecordDecl>(D, Kind) ||
  82          isTemplateSpecializationKind<VarDecl>(D, Kind);
  83 }
  84
  85 // Store all UsingDirectiveDecls in parent contexts of DestContext, that were
  86 // introduced before InsertionPoint.
  87 llvm::DenseSet<const NamespaceDecl *>
  88 getUsingNamespaceDirectives(const DeclContext *DestContext,
  89                             SourceLocation Until) {
  90   const auto &SM = DestContext->getParentASTContext().getSourceManager();
  91   llvm::DenseSet<const NamespaceDecl *> VisibleNamespaceDecls;
  92   for (const auto *DC = DestContext; DC; DC = DC->getLookupParent()) {
  93     for (const auto *D : DC->decls()) {
  94       if (!SM.isWrittenInSameFile(D->getLocation(), Until) ||
  95           !SM.isBeforeInTranslationUnit(D->getLocation(), Until))
  96         continue;
  97       if (auto *UDD = llvm::dyn_cast<UsingDirectiveDecl>(D))
  98         VisibleNamespaceDecls.insert(
  99             UDD->getNominatedNamespace()->getCanonicalDecl());
 100     }
 101   }
 102   return VisibleNamespaceDecls;
 103 }
 104
 105 // Goes over all parents of SourceContext until we find a common ancestor for
 106 // DestContext and SourceContext. Any qualifier including and above common
 107 // ancestor is redundant, therefore we stop at lowest common ancestor.
 108 // In addition to that stops early whenever IsVisible returns true. This can be
 109 // used to implement support for "using namespace" decls.
 110 std::string
 111 getQualification(ASTContext &Context, const DeclContext *DestContext,
 112                  const DeclContext *SourceContext,
 113                  llvm::function_ref<bool(NestedNameSpecifier *)> IsVisible) {
 114   std::vector<const NestedNameSpecifier *> Parents;
 115   bool ReachedNS = false;
 116   for (const DeclContext *CurContext = SourceContext; CurContext;
 117        CurContext = CurContext->getLookupParent()) {
 118     // Stop once we reach a common ancestor.
 119     if (CurContext->Encloses(DestContext))
 120       break;
 121
 122     NestedNameSpecifier *NNS = nullptr;
 123     if (auto *TD = llvm::dyn_cast<TagDecl>(CurContext)) {
 124       // There can't be any more tag parents after hitting a namespace.
 125       assert(!ReachedNS);
 126       (void)ReachedNS;
 127       NNS = NestedNameSpecifier::Create(Context, nullptr, false,
 128                                         TD->getTypeForDecl());
 129     } else if (auto *NSD = llvm::dyn_cast<NamespaceDecl>(CurContext)) {
 130       ReachedNS = true;
 131       NNS = NestedNameSpecifier::Create(Context, nullptr, NSD);
 132       // Anonymous and inline namespace names are not spelled while qualifying
 133       // a name, so skip those.
 134       if (NSD->isAnonymousNamespace() || NSD->isInlineNamespace())
 135         continue;
 136     } else {
 137       // Other types of contexts cannot be spelled in code, just skip over
 138       // them.
 139       continue;
 140     }
 141     // Stop if this namespace is already visible at DestContext.
 142     if (IsVisible(NNS))
 143       break;
 144
 145     Parents.push_back(NNS);
 146   }
 147
 148   // Go over name-specifiers in reverse order to create necessary qualification,
 149   // since we stored inner-most parent first.
 150   std::string Result;
 151   llvm::raw_string_ostream OS(Result);
 152   for (const auto *Parent : llvm::reverse(Parents))
 153     Parent->print(OS, Context.getPrintingPolicy());
 154   return OS.str();
 155 }
 156
 157 } // namespace
 158
 159 bool isImplicitTemplateInstantiation(const NamedDecl *D) {
 160   return isTemplateSpecializationKind(D, TSK_ImplicitInstantiation);
 161 }
 162
 163 bool isExplicitTemplateSpecialization(const NamedDecl *D) {
 164   return isTemplateSpecializationKind(D, TSK_ExplicitSpecialization);
 165 }
 166
 167 bool isImplementationDetail(const Decl *D) {
 168   return !isSpelledInSource(D->getLocation(),
 169                             D->getASTContext().getSourceManager());
 170 }
 171
 172 SourceLocation nameLocation(const clang::Decl &D, const SourceManager &SM) {
 173   auto L = D.getLocation();
 174   // For `- (void)foo` we want `foo` not the `-`.
 175   if (const auto *MD = dyn_cast<ObjCMethodDecl>(&D))
 176     L = MD->getSelectorStartLoc();
 177   if (isSpelledInSource(L, SM))
 178     return SM.getSpellingLoc(L);
 179   return SM.getExpansionLoc(L);
 180 }
 181
 182 std::string printQualifiedName(const NamedDecl &ND) {
 183   std::string QName;
 184   llvm::raw_string_ostream OS(QName);
 185   PrintingPolicy Policy(ND.getASTContext().getLangOpts());
 186   // Note that inline namespaces are treated as transparent scopes. This
 187   // reflects the way they're most commonly used for lookup. Ideally we'd
 188   // include them, but at query time it's hard to find all the inline
 189   // namespaces to query: the preamble doesn't have a dedicated list.
 190   Policy.SuppressUnwrittenScope = true;
 191   // (unnamed struct), not (unnamed struct at /path/to/foo.cc:42:1).
 192   // In clangd, context is usually available and paths are mostly noise.
 193   Policy.AnonymousTagLocations = false;
 194   ND.printQualifiedName(OS, Policy);
 195   OS.flush();
 196   assert(!StringRef(QName).startswith("::"));
 197   return QName;
 198 }
 199
 200 static bool isAnonymous(const DeclarationName &N) {
 201   return N.isIdentifier() && !N.getAsIdentifierInfo();
 202 }
 203
 204 NestedNameSpecifierLoc getQualifierLoc(const NamedDecl &ND) {
 205   if (auto *V = llvm::dyn_cast<DeclaratorDecl>(&ND))
 206     return V->getQualifierLoc();
 207   if (auto *T = llvm::dyn_cast<TagDecl>(&ND))
 208     return T->getQualifierLoc();
 209   return NestedNameSpecifierLoc();
 210 }
 211
 212 std::string printUsingNamespaceName(const ASTContext &Ctx,
 213                                     const UsingDirectiveDecl &D) {
 214   PrintingPolicy PP(Ctx.getLangOpts());
 215   std::string Name;
 216   llvm::raw_string_ostream Out(Name);
 217
 218   if (auto *Qual = D.getQualifier())
 219     Qual->print(Out, PP);
 220   D.getNominatedNamespaceAsWritten()->printName(Out);
 221   return Out.str();
 222 }
 223
 224 std::string printName(const ASTContext &Ctx, const NamedDecl &ND) {
 225   std::string Name;
 226   llvm::raw_string_ostream Out(Name);
 227   PrintingPolicy PP(Ctx.getLangOpts());
 228   // We don't consider a class template's args part of the constructor name.
 229   PP.SuppressTemplateArgsInCXXConstructors = true;
 230
 231   // Handle 'using namespace'. They all have the same name - <using-directive>.
 232   if (auto *UD = llvm::dyn_cast<UsingDirectiveDecl>(&ND)) {
 233     Out << "using namespace ";
 234     if (auto *Qual = UD->getQualifier())
 235       Qual->print(Out, PP);
 236     UD->getNominatedNamespaceAsWritten()->printName(Out);
 237     return Out.str();
 238   }
 239
 240   if (isAnonymous(ND.getDeclName())) {
 241     // Come up with a presentation for an anonymous entity.
 242     if (isa<NamespaceDecl>(ND))
 243       return "(anonymous namespace)";
 244     if (auto *Cls = llvm::dyn_cast<RecordDecl>(&ND)) {
 245       if (Cls->isLambda())
 246         return "(lambda)";
 247       return ("(anonymous " + Cls->getKindName() + ")").str();
 248     }
 249     if (isa<EnumDecl>(ND))
 250       return "(anonymous enum)";
 251     return "(anonymous)";
 252   }
 253
 254   // Print nested name qualifier if it was written in the source code.
 255   if (auto *Qualifier = getQualifierLoc(ND).getNestedNameSpecifier())
 256     Qualifier->print(Out, PP);
 257   // Print the name itself.
 258   ND.getDeclName().print(Out, PP);
 259   // Print template arguments.
 260   Out << printTemplateSpecializationArgs(ND);
 261
 262   return Out.str();
 263 }
 264
 265 std::string printTemplateSpecializationArgs(const NamedDecl &ND) {
 266   std::string TemplateArgs;
 267   llvm::raw_string_ostream OS(TemplateArgs);
 268   PrintingPolicy Policy(ND.getASTContext().getLangOpts());
 269   if (std::optional<llvm::ArrayRef<TemplateArgumentLoc>> Args =
 270           getTemplateSpecializationArgLocs(ND)) {
 271     printTemplateArgumentList(OS, *Args, Policy);
 272   } else if (auto *Cls = llvm::dyn_cast<ClassTemplateSpecializationDecl>(&ND)) {
 273     if (const TypeSourceInfo *TSI = Cls->getTypeAsWritten()) {
 274       // ClassTemplateSpecializationDecls do not contain
 275       // TemplateArgumentTypeLocs, they only have TemplateArgumentTypes. So we
 276       // create a new argument location list from TypeSourceInfo.
 277       auto STL = TSI->getTypeLoc().getAs<TemplateSpecializationTypeLoc>();
 278       llvm::SmallVector<TemplateArgumentLoc> ArgLocs;
 279       ArgLocs.reserve(STL.getNumArgs());
 280       for (unsigned I = 0; I < STL.getNumArgs(); ++I)
 281         ArgLocs.push_back(STL.getArgLoc(I));
 282       printTemplateArgumentList(OS, ArgLocs, Policy);
 283     } else {
 284       // FIXME: Fix cases when getTypeAsWritten returns null inside clang AST,
 285       // e.g. friend decls. Currently we fallback to Template Arguments without
 286       // location information.
 287       printTemplateArgumentList(OS, Cls->getTemplateArgs().asArray(), Policy);
 288     }
 289   }
 290   OS.flush();
 291   return TemplateArgs;
 292 }
 293
 294 std::string printNamespaceScope(const DeclContext &DC) {
 295   for (const auto *Ctx = &DC; Ctx != nullptr; Ctx = Ctx->getParent())
 296     if (const auto *NS = dyn_cast<NamespaceDecl>(Ctx))
 297       if (!NS->isAnonymousNamespace() && !NS->isInlineNamespace())
 298         return printQualifiedName(*NS) + "::";
 299   return "";
 300 }
 301
 302 static llvm::StringRef
 303 getNameOrErrForObjCInterface(const ObjCInterfaceDecl *ID) {
 304   return ID ? ID->getName() : "<<error-type>>";
 305 }
 306
 307 std::string printObjCMethod(const ObjCMethodDecl &Method) {
 308   std::string Name;
 309   llvm::raw_string_ostream OS(Name);
 310
 311   OS << (Method.isInstanceMethod() ? '-' : '+') << '[';
 312
 313   // Should always be true.
 314   if (const ObjCContainerDecl *C =
 315           dyn_cast<ObjCContainerDecl>(Method.getDeclContext()))
 316     OS << printObjCContainer(*C);
 317
 318   Method.getSelector().print(OS << ' ');
 319   if (Method.isVariadic())
 320     OS << ", ...";
 321
 322   OS << ']';
 323   OS.flush();
 324   return Name;
 325 }
 326
 327 std::string printObjCContainer(const ObjCContainerDecl &C) {
 328   if (const ObjCCategoryDecl *Category = dyn_cast<ObjCCategoryDecl>(&C)) {
 329     std::string Name;
 330     llvm::raw_string_ostream OS(Name);
 331     const ObjCInterfaceDecl *Class = Category->getClassInterface();
 332     OS << getNameOrErrForObjCInterface(Class) << '(' << Category->getName()
 333        << ')';
 334     OS.flush();
 335     return Name;
 336   }
 337   if (const ObjCCategoryImplDecl *CID = dyn_cast<ObjCCategoryImplDecl>(&C)) {
 338     std::string Name;
 339     llvm::raw_string_ostream OS(Name);
 340     const ObjCInterfaceDecl *Class = CID->getClassInterface();
 341     OS << getNameOrErrForObjCInterface(Class) << '(' << CID->getName() << ')';
 342     OS.flush();
 343     return Name;
 344   }
 345   return C.getNameAsString();
 346 }
 347
 348 SymbolID getSymbolID(const Decl *D) {
 349   llvm::SmallString<128> USR;
 350   if (index::generateUSRForDecl(D, USR))
 351     return {};
 352   return SymbolID(USR);
 353 }
 354
 355 SymbolID getSymbolID(const llvm::StringRef MacroName, const MacroInfo *MI,
 356                      const SourceManager &SM) {
 357   if (MI == nullptr)
 358     return {};
 359   llvm::SmallString<128> USR;
 360   if (index::generateUSRForMacro(MacroName, MI->getDefinitionLoc(), SM, USR))
 361     return {};
 362   return SymbolID(USR);
 363 }
 364
 365 const ObjCImplDecl *getCorrespondingObjCImpl(const ObjCContainerDecl *D) {
 366   if (const auto *ID = dyn_cast<ObjCInterfaceDecl>(D))
 367     return ID->getImplementation();
 368   if (const auto *CD = dyn_cast<ObjCCategoryDecl>(D)) {
 369     if (CD->IsClassExtension()) {
 370       if (const auto *ID = CD->getClassInterface())
 371         return ID->getImplementation();
 372       return nullptr;
 373     }
 374     return CD->getImplementation();
 375   }
 376   return nullptr;
 377 }
 378
 379 Symbol::IncludeDirective
 380 preferredIncludeDirective(llvm::StringRef FileName, const LangOptions &LangOpts,
 381                           ArrayRef<Inclusion> MainFileIncludes,
 382                           ArrayRef<const Decl *> TopLevelDecls) {
 383   // Always prefer #include for non-ObjC code.
 384   if (!LangOpts.ObjC)
 385     return Symbol::IncludeDirective::Include;
 386   // If this is not a header file and has ObjC set as the language, prefer
 387   // #import.
 388   if (!isHeaderFile(FileName, LangOpts))
 389     return Symbol::IncludeDirective::Import;
 390
 391   // Headers lack proper compile flags most of the time, so we might treat a
 392   // header as ObjC accidentally. Perform some extra checks to make sure this
 393   // works.
 394
 395   // Any file with a #import, should keep #import-ing.
 396   for (auto &Inc : MainFileIncludes)
 397     if (Inc.Directive == tok::pp_import)
 398       return Symbol::IncludeDirective::Import;
 399
 400   // Any file declaring an ObjC decl should also be #import-ing.
 401   // No need to look over the references, as the file doesn't have any #imports,
 402   // it must be declaring interesting ObjC-like decls.
 403   for (const Decl *D : TopLevelDecls)
 404     if (isa<ObjCContainerDecl, ObjCIvarDecl, ObjCMethodDecl, ObjCPropertyDecl>(
 405             D))
 406       return Symbol::IncludeDirective::Import;
 407
 408   return Symbol::IncludeDirective::Include;
 409 }
 410
 411 std::string printType(const QualType QT, const DeclContext &CurContext,
 412                       const llvm::StringRef Placeholder) {
 413   std::string Result;
 414   llvm::raw_string_ostream OS(Result);
 415   PrintingPolicy PP(CurContext.getParentASTContext().getPrintingPolicy());
 416   PP.SuppressTagKeyword = true;
 417   PP.SuppressUnwrittenScope = true;
 418
 419   class PrintCB : public PrintingCallbacks {
 420   public:
 421     PrintCB(const DeclContext *CurContext) : CurContext(CurContext) {}
 422     virtual ~PrintCB() {}
 423     bool isScopeVisible(const DeclContext *DC) const override {
 424       return DC->Encloses(CurContext);
 425     }
 426
 427   private:
 428     const DeclContext *CurContext;
 429   };
 430   PrintCB PCB(&CurContext);
 431   PP.Callbacks = &PCB;
 432
 433   QT.print(OS, PP, Placeholder);
 434   return OS.str();
 435 }
 436
 437 bool hasReservedName(const Decl &D) {
 438   if (const auto *ND = llvm::dyn_cast<NamedDecl>(&D))
 439     if (const auto *II = ND->getIdentifier())
 440       return isReservedName(II->getName());
 441   return false;
 442 }
 443
 444 bool hasReservedScope(const DeclContext &DC) {
 445   for (const DeclContext *D = &DC; D; D = D->getParent()) {
 446     if (D->isTransparentContext() || D->isInlineNamespace())
 447       continue;
 448     if (const auto *ND = llvm::dyn_cast<NamedDecl>(D))
 449       if (hasReservedName(*ND))
 450         return true;
 451   }
 452   return false;
 453 }
 454
 455 QualType declaredType(const TypeDecl *D) {
 456   if (const auto *CTSD = llvm::dyn_cast<ClassTemplateSpecializationDecl>(D))
 457     if (const auto *TSI = CTSD->getTypeAsWritten())
 458       return TSI->getType();
 459   return D->getASTContext().getTypeDeclType(D);
 460 }
 461
 462 namespace {
 463 /// Computes the deduced type at a given location by visiting the relevant
 464 /// nodes. We use this to display the actual type when hovering over an "auto"
 465 /// keyword or "decltype()" expression.
 466 /// FIXME: This could have been a lot simpler by visiting AutoTypeLocs but it
 467 /// seems that the AutoTypeLocs that can be visited along with their AutoType do
 468 /// not have the deduced type set. Instead, we have to go to the appropriate
 469 /// DeclaratorDecl/FunctionDecl and work our back to the AutoType that does have
 470 /// a deduced type set. The AST should be improved to simplify this scenario.
 471 class DeducedTypeVisitor : public RecursiveASTVisitor<DeducedTypeVisitor> {
 472   SourceLocation SearchedLocation;
 473
 474 public:
 475   DeducedTypeVisitor(SourceLocation SearchedLocation)
 476       : SearchedLocation(SearchedLocation) {}
 477
 478   // Handle auto initializers:
 479   //- auto i = 1;
 480   //- decltype(auto) i = 1;
 481   //- auto& i = 1;
 482   //- auto* i = &a;
 483   bool VisitDeclaratorDecl(DeclaratorDecl *D) {
 484     if (!D->getTypeSourceInfo() ||
 485         !D->getTypeSourceInfo()->getTypeLoc().getContainedAutoTypeLoc() ||
 486         D->getTypeSourceInfo()
 487                 ->getTypeLoc()
 488                 .getContainedAutoTypeLoc()
 489                 .getNameLoc() != SearchedLocation)
 490       return true;
 491
 492     if (auto *AT = D->getType()->getContainedAutoType()) {
 493       DeducedType = AT->desugar();
 494     }
 495     return true;
 496   }
 497
 498   // Handle auto return types:
 499   //- auto foo() {}
 500   //- auto& foo() {}
 501   //- auto foo() -> int {}
 502   //- auto foo() -> decltype(1+1) {}
 503   //- operator auto() const { return 10; }
 504   bool VisitFunctionDecl(FunctionDecl *D) {
 505     if (!D->getTypeSourceInfo())
 506       return true;
 507     // Loc of auto in return type (c++14).
 508     auto CurLoc = D->getReturnTypeSourceRange().getBegin();
 509     // Loc of "auto" in operator auto()
 510     if (CurLoc.isInvalid() && isa<CXXConversionDecl>(D))
 511       CurLoc = D->getTypeSourceInfo()->getTypeLoc().getBeginLoc();
 512     // Loc of "auto" in function with trailing return type (c++11).
 513     if (CurLoc.isInvalid())
 514       CurLoc = D->getSourceRange().getBegin();
 515     if (CurLoc != SearchedLocation)
 516       return true;
 517
 518     const AutoType *AT = D->getReturnType()->getContainedAutoType();
 519     if (AT && !AT->getDeducedType().isNull()) {
 520       DeducedType = AT->getDeducedType();
 521     } else if (auto *DT = dyn_cast<DecltypeType>(D->getReturnType())) {
 522       // auto in a trailing return type just points to a DecltypeType and
 523       // getContainedAutoType does not unwrap it.
 524       if (!DT->getUnderlyingType().isNull())
 525         DeducedType = DT->getUnderlyingType();
 526     } else if (!D->getReturnType().isNull()) {
 527       DeducedType = D->getReturnType();
 528     }
 529     return true;
 530   }
 531
 532   // Handle non-auto decltype, e.g.:
 533   // - auto foo() -> decltype(expr) {}
 534   // - decltype(expr);
 535   bool VisitDecltypeTypeLoc(DecltypeTypeLoc TL) {
 536     if (TL.getBeginLoc() != SearchedLocation)
 537       return true;
 538
 539     // A DecltypeType's underlying type can be another DecltypeType! E.g.
 540     //  int I = 0;
 541     //  decltype(I) J = I;
 542     //  decltype(J) K = J;
 543     const DecltypeType *DT = dyn_cast<DecltypeType>(TL.getTypePtr());
 544     while (DT && !DT->getUnderlyingType().isNull()) {
 545       DeducedType = DT->getUnderlyingType();
 546       DT = dyn_cast<DecltypeType>(DeducedType.getTypePtr());
 547     }
 548     return true;
 549   }
 550
 551   // Handle functions/lambdas with `auto` typed parameters.
 552   // We deduce the type if there's exactly one instantiation visible.
 553   bool VisitParmVarDecl(ParmVarDecl *PVD) {
 554     if (!PVD->getType()->isDependentType())
 555       return true;
 556     // 'auto' here does not name an AutoType, but an implicit template param.
 557     TemplateTypeParmTypeLoc Auto =
 558         getContainedAutoParamType(PVD->getTypeSourceInfo()->getTypeLoc());
 559     if (Auto.isNull() || Auto.getNameLoc() != SearchedLocation)
 560       return true;
 561
 562     // We expect the TTP to be attached to this function template.
 563     // Find the template and the param index.
 564     auto *Templated = llvm::dyn_cast<FunctionDecl>(PVD->getDeclContext());
 565     if (!Templated)
 566       return true;
 567     auto *FTD = Templated->getDescribedFunctionTemplate();
 568     if (!FTD)
 569       return true;
 570     int ParamIndex = paramIndex(*FTD, *Auto.getDecl());
 571     if (ParamIndex < 0) {
 572       assert(false && "auto TTP is not from enclosing function?");
 573       return true;
 574     }
 575
 576     // Now find the instantiation and the deduced template type arg.
 577     auto *Instantiation =
 578         llvm::dyn_cast_or_null<FunctionDecl>(getOnlyInstantiation(Templated));
 579     if (!Instantiation)
 580       return true;
 581     const auto *Args = Instantiation->getTemplateSpecializationArgs();
 582     if (Args->size() != FTD->getTemplateParameters()->size())
 583       return true; // no weird variadic stuff
 584     DeducedType = Args->get(ParamIndex).getAsType();
 585     return true;
 586   }
 587
 588   static int paramIndex(const TemplateDecl &TD, NamedDecl &Param) {
 589     unsigned I = 0;
 590     for (auto *ND : *TD.getTemplateParameters()) {
 591       if (&Param == ND)
 592         return I;
 593       ++I;
 594     }
 595     return -1;
 596   }
 597
 598   QualType DeducedType;
 599 };
 600 } // namespace
 601
 602 std::optional<QualType> getDeducedType(ASTContext &ASTCtx, SourceLocation Loc) {
 603   if (!Loc.isValid())
 604     return {};
 605   DeducedTypeVisitor V(Loc);
 606   V.TraverseAST(ASTCtx);
 607   if (V.DeducedType.isNull())
 608     return std::nullopt;
 609   return V.DeducedType;
 610 }
 611
 612 TemplateTypeParmTypeLoc getContainedAutoParamType(TypeLoc TL) {
 613   if (auto QTL = TL.getAs<QualifiedTypeLoc>())
 614     return getContainedAutoParamType(QTL.getUnqualifiedLoc());
 615   if (llvm::isa<PointerType, ReferenceType, ParenType>(TL.getTypePtr()))
 616     return getContainedAutoParamType(TL.getNextTypeLoc());
 617   if (auto FTL = TL.getAs<FunctionTypeLoc>())
 618     return getContainedAutoParamType(FTL.getReturnLoc());
 619   if (auto TTPTL = TL.getAs<TemplateTypeParmTypeLoc>()) {
 620     if (TTPTL.getTypePtr()->getDecl()->isImplicit())
 621       return TTPTL;
 622   }
 623   return {};
 624 }
 625
 626 template <typename TemplateDeclTy>
 627 static NamedDecl *getOnlyInstantiationImpl(TemplateDeclTy *TD) {
 628   NamedDecl *Only = nullptr;
 629   for (auto *Spec : TD->specializations()) {
 630     if (Spec->getTemplateSpecializationKind() == TSK_ExplicitSpecialization)
 631       continue;
 632     if (Only != nullptr)
 633       return nullptr;
 634     Only = Spec;
 635   }
 636   return Only;
 637 }
 638
 639 NamedDecl *getOnlyInstantiation(NamedDecl *TemplatedDecl) {
 640   if (TemplateDecl *TD = TemplatedDecl->getDescribedTemplate()) {
 641     if (auto *CTD = llvm::dyn_cast<ClassTemplateDecl>(TD))
 642       return getOnlyInstantiationImpl(CTD);
 643     if (auto *FTD = llvm::dyn_cast<FunctionTemplateDecl>(TD))
 644       return getOnlyInstantiationImpl(FTD);
 645     if (auto *VTD = llvm::dyn_cast<VarTemplateDecl>(TD))
 646       return getOnlyInstantiationImpl(VTD);
 647   }
 648   return nullptr;
 649 }
 650
 651 std::vector<const Attr *> getAttributes(const DynTypedNode &N) {
 652   std::vector<const Attr *> Result;
 653   if (const auto *TL = N.get<TypeLoc>()) {
 654     for (AttributedTypeLoc ATL = TL->getAs<AttributedTypeLoc>(); !ATL.isNull();
 655          ATL = ATL.getModifiedLoc().getAs<AttributedTypeLoc>()) {
 656       if (const Attr *A = ATL.getAttr())
 657         Result.push_back(A);
 658       assert(!ATL.getModifiedLoc().isNull());
 659     }
 660   }
 661   if (const auto *S = N.get<AttributedStmt>()) {
 662     for (; S != nullptr; S = dyn_cast<AttributedStmt>(S->getSubStmt()))
 663       for (const Attr *A : S->getAttrs())
 664         if (A)
 665           Result.push_back(A);
 666   }
 667   if (const auto *D = N.get<Decl>()) {
 668     for (const Attr *A : D->attrs())
 669       if (A)
 670         Result.push_back(A);
 671   }
 672   return Result;
 673 }
 674
 675 std::string getQualification(ASTContext &Context,
 676                              const DeclContext *DestContext,
 677                              SourceLocation InsertionPoint,
 678                              const NamedDecl *ND) {
 679   auto VisibleNamespaceDecls =
 680       getUsingNamespaceDirectives(DestContext, InsertionPoint);
 681   return getQualification(
 682       Context, DestContext, ND->getDeclContext(),
 683       [&](NestedNameSpecifier *NNS) {
 684         if (NNS->getKind() != NestedNameSpecifier::Namespace)
 685           return false;
 686         const auto *CanonNSD = NNS->getAsNamespace()->getCanonicalDecl();
 687         return llvm::any_of(VisibleNamespaceDecls,
 688                             [CanonNSD](const NamespaceDecl *NSD) {
 689                               return NSD->getCanonicalDecl() == CanonNSD;
 690                             });
 691       });
 692 }
 693
 694 std::string getQualification(ASTContext &Context,
 695                              const DeclContext *DestContext,
 696                              const NamedDecl *ND,
 697                              llvm::ArrayRef<std::string> VisibleNamespaces) {
 698   for (llvm::StringRef NS : VisibleNamespaces) {
 699     assert(NS.endswith("::"));
 700     (void)NS;
 701   }
 702   return getQualification(
 703       Context, DestContext, ND->getDeclContext(),
 704       [&](NestedNameSpecifier *NNS) {
 705         return llvm::any_of(VisibleNamespaces, [&](llvm::StringRef Namespace) {
 706           std::string NS;
 707           llvm::raw_string_ostream OS(NS);
 708           NNS->print(OS, Context.getPrintingPolicy());
 709           return OS.str() == Namespace;
 710         });
 711       });
 712 }
 713
 714 bool hasUnstableLinkage(const Decl *D) {
 715   // Linkage of a ValueDecl depends on the type.
 716   // If that's not deduced yet, deducing it may change the linkage.
 717   auto *VD = llvm::dyn_cast_or_null<ValueDecl>(D);
 718   return VD && !VD->getType().isNull() && VD->getType()->isUndeducedType();
 719 }
 720
 721 bool isDeeplyNested(const Decl *D, unsigned MaxDepth) {
 722   size_t ContextDepth = 0;
 723   for (auto *Ctx = D->getDeclContext(); Ctx && !Ctx->isTranslationUnit();
 724        Ctx = Ctx->getParent()) {
 725     if (++ContextDepth == MaxDepth)
 726       return true;
 727   }
 728   return false;
 729 }
 730
 731 namespace {
 732
 733 // returns true for `X` in `template <typename... X> void foo()`
 734 bool isTemplateTypeParameterPack(NamedDecl *D) {
 735   if (const auto *TTPD = dyn_cast<TemplateTypeParmDecl>(D)) {
 736     return TTPD->isParameterPack();
 737   }
 738   return false;
 739 }
 740
 741 // Returns the template parameter pack type from an instantiated function
 742 // template, if it exists, nullptr otherwise.
 743 const TemplateTypeParmType *getFunctionPackType(const FunctionDecl *Callee) {
 744   if (const auto *TemplateDecl = Callee->getPrimaryTemplate()) {
 745     auto TemplateParams = TemplateDecl->getTemplateParameters()->asArray();
 746     // find the template parameter pack from the back
 747     const auto It = std::find_if(TemplateParams.rbegin(), TemplateParams.rend(),
 748                                  isTemplateTypeParameterPack);
 749     if (It != TemplateParams.rend()) {
 750       const auto *TTPD = dyn_cast<TemplateTypeParmDecl>(*It);
 751       return TTPD->getTypeForDecl()->castAs<TemplateTypeParmType>();
 752     }
 753   }
 754   return nullptr;
 755 }
 756
 757 // Returns the template parameter pack type that this parameter was expanded
 758 // from (if in the Args... or Args&... or Args&&... form), if this is the case,
 759 // nullptr otherwise.
 760 const TemplateTypeParmType *getUnderylingPackType(const ParmVarDecl *Param) {
 761   const auto *PlainType = Param->getType().getTypePtr();
 762   if (auto *RT = dyn_cast<ReferenceType>(PlainType))
 763     PlainType = RT->getPointeeTypeAsWritten().getTypePtr();
 764   if (const auto *SubstType = dyn_cast<SubstTemplateTypeParmType>(PlainType)) {
 765     const auto *ReplacedParameter = SubstType->getReplacedParameter();
 766     if (ReplacedParameter->isParameterPack()) {
 767       return ReplacedParameter->getTypeForDecl()
 768           ->castAs<TemplateTypeParmType>();
 769     }
 770   }
 771   return nullptr;
 772 }
 773
 774 // This visitor walks over the body of an instantiated function template.
 775 // The template accepts a parameter pack and the visitor records whether
 776 // the pack parameters were forwarded to another call. For example, given:
 777 //
 778 // template <typename T, typename... Args>
 779 // auto make_unique(Args... args) {
 780 //   return unique_ptr<T>(new T(args...));
 781 // }
 782 //
 783 // When called as `make_unique<std::string>(2, 'x')` this yields a function
 784 // `make_unique<std::string, int, char>` with two parameters.
 785 // The visitor records that those two parameters are forwarded to the
 786 // `constructor std::string(int, char);`.
 787 //
 788 // This information is recorded in the `ForwardingInfo` split into fully
 789 // resolved parameters (passed as argument to a parameter that is not an
 790 // expanded template type parameter pack) and forwarding parameters (passed to a
 791 // parameter that is an expanded template type parameter pack).
 792 class ForwardingCallVisitor
 793     : public RecursiveASTVisitor<ForwardingCallVisitor> {
 794 public:
 795   ForwardingCallVisitor(ArrayRef<const ParmVarDecl *> Parameters)
 796       : Parameters{Parameters}, PackType{getUnderylingPackType(
 797                                     Parameters.front())} {}
 798
 799   bool VisitCallExpr(CallExpr *E) {
 800     auto *Callee = getCalleeDeclOrUniqueOverload(E);
 801     if (Callee) {
 802       handleCall(Callee, E->arguments());
 803     }
 804     return !Info.has_value();
 805   }
 806
 807   bool VisitCXXConstructExpr(CXXConstructExpr *E) {
 808     auto *Callee = E->getConstructor();
 809     if (Callee) {
 810       handleCall(Callee, E->arguments());
 811     }
 812     return !Info.has_value();
 813   }
 814
 815   // The expanded parameter pack to be resolved
 816   ArrayRef<const ParmVarDecl *> Parameters;
 817   // The type of the parameter pack
 818   const TemplateTypeParmType *PackType;
 819
 820   struct ForwardingInfo {
 821     // If the parameters were resolved to another FunctionDecl, these are its
 822     // first non-variadic parameters (i.e. the first entries of the parameter
 823     // pack that are passed as arguments bound to a non-pack parameter.)
 824     ArrayRef<const ParmVarDecl *> Head;
 825     // If the parameters were resolved to another FunctionDecl, these are its
 826     // variadic parameters (i.e. the entries of the parameter pack that are
 827     // passed as arguments bound to a pack parameter.)
 828     ArrayRef<const ParmVarDecl *> Pack;
 829     // If the parameters were resolved to another FunctionDecl, these are its
 830     // last non-variadic parameters (i.e. the last entries of the parameter pack
 831     // that are passed as arguments bound to a non-pack parameter.)
 832     ArrayRef<const ParmVarDecl *> Tail;
 833     // If the parameters were resolved to another forwarding FunctionDecl, this
 834     // is it.
 835     std::optional<FunctionDecl *> PackTarget;
 836   };
 837
 838   // The output of this visitor
 839   std::optional<ForwardingInfo> Info;
 840
 841 private:
 842   // inspects the given callee with the given args to check whether it
 843   // contains Parameters, and sets Info accordingly.
 844   void handleCall(FunctionDecl *Callee, typename CallExpr::arg_range Args) {
 845     // Skip functions with less parameters, they can't be the target.
 846     if (Callee->parameters().size() < Parameters.size())
 847       return;
 848     if (llvm::any_of(Args,
 849                      [](const Expr *E) { return isa<PackExpansionExpr>(E); })) {
 850       return;
 851     }
 852     auto PackLocation = findPack(Args);
 853     if (!PackLocation)
 854       return;
 855     ArrayRef<ParmVarDecl *> MatchingParams =
 856         Callee->parameters().slice(*PackLocation, Parameters.size());
 857     // Check whether the function has a parameter pack as the last template
 858     // parameter
 859     if (const auto *TTPT = getFunctionPackType(Callee)) {
 860       // In this case: Separate the parameters into head, pack and tail
 861       auto IsExpandedPack = [&](const ParmVarDecl *P) {
 862         return getUnderylingPackType(P) == TTPT;
 863       };
 864       ForwardingInfo FI;
 865       FI.Head = MatchingParams.take_until(IsExpandedPack);
 866       FI.Pack =
 867           MatchingParams.drop_front(FI.Head.size()).take_while(IsExpandedPack);
 868       FI.Tail = MatchingParams.drop_front(FI.Head.size() + FI.Pack.size());
 869       FI.PackTarget = Callee;
 870       Info = FI;
 871       return;
 872     }
 873     // Default case: assume all parameters were fully resolved
 874     ForwardingInfo FI;
 875     FI.Head = MatchingParams;
 876     Info = FI;
 877   }
 878
 879   // Returns the beginning of the expanded pack represented by Parameters
 880   // in the given arguments, if it is there.
 881   std::optional<size_t> findPack(typename CallExpr::arg_range Args) {
 882     // find the argument directly referring to the first parameter
 883     assert(Parameters.size() <= static_cast<size_t>(llvm::size(Args)));
 884     for (auto Begin = Args.begin(), End = Args.end() - Parameters.size() + 1;
 885          Begin != End; ++Begin) {
 886       if (const auto *RefArg = unwrapForward(*Begin)) {
 887         if (Parameters.front() != RefArg->getDecl())
 888           continue;
 889         // Check that this expands all the way until the last parameter.
 890         // It's enough to look at the last parameter, because it isn't possible
 891         // to expand without expanding all of them.
 892         auto ParamEnd = Begin + Parameters.size() - 1;
 893         RefArg = unwrapForward(*ParamEnd);
 894         if (!RefArg || Parameters.back() != RefArg->getDecl())
 895           continue;
 896         return std::distance(Args.begin(), Begin);
 897       }
 898     }
 899     return std::nullopt;
 900   }
 901
 902   static FunctionDecl *getCalleeDeclOrUniqueOverload(CallExpr *E) {
 903     Decl *CalleeDecl = E->getCalleeDecl();
 904     auto *Callee = dyn_cast_or_null<FunctionDecl>(CalleeDecl);
 905     if (!Callee) {
 906       if (auto *Lookup = dyn_cast<UnresolvedLookupExpr>(E->getCallee())) {
 907         Callee = resolveOverload(Lookup, E);
 908       }
 909     }
 910     // Ignore the callee if the number of arguments is wrong (deal with va_args)
 911     if (Callee && Callee->getNumParams() == E->getNumArgs())
 912       return Callee;
 913     return nullptr;
 914   }
 915
 916   static FunctionDecl *resolveOverload(UnresolvedLookupExpr *Lookup,
 917                                        CallExpr *E) {
 918     FunctionDecl *MatchingDecl = nullptr;
 919     if (!Lookup->requiresADL()) {
 920       // Check whether there is a single overload with this number of
 921       // parameters
 922       for (auto *Candidate : Lookup->decls()) {
 923         if (auto *FuncCandidate = dyn_cast_or_null<FunctionDecl>(Candidate)) {
 924           if (FuncCandidate->getNumParams() == E->getNumArgs()) {
 925             if (MatchingDecl) {
 926               // there are multiple candidates - abort
 927               return nullptr;
 928             }
 929             MatchingDecl = FuncCandidate;
 930           }
 931         }
 932       }
 933     }
 934     return MatchingDecl;
 935   }
 936
 937   // Tries to get to the underlying argument by unwrapping implicit nodes and
 938   // std::forward.
 939   static const DeclRefExpr *unwrapForward(const Expr *E) {
 940     E = E->IgnoreImplicitAsWritten();
 941     // There might be an implicit copy/move constructor call on top of the
 942     // forwarded arg.
 943     // FIXME: Maybe mark implicit calls in the AST to properly filter here.
 944     if (const auto *Const = dyn_cast<CXXConstructExpr>(E))
 945       if (Const->getConstructor()->isCopyOrMoveConstructor())
 946         E = Const->getArg(0)->IgnoreImplicitAsWritten();
 947     if (const auto *Call = dyn_cast<CallExpr>(E)) {
 948       const auto Callee = Call->getBuiltinCallee();
 949       if (Callee == Builtin::BIforward) {
 950         return dyn_cast<DeclRefExpr>(
 951             Call->getArg(0)->IgnoreImplicitAsWritten());
 952       }
 953     }
 954     return dyn_cast<DeclRefExpr>(E);
 955   }
 956 };
 957
 958 } // namespace
 959
 960 SmallVector<const ParmVarDecl *>
 961 resolveForwardingParameters(const FunctionDecl *D, unsigned MaxDepth) {
 962   auto Parameters = D->parameters();
 963   // If the function has a template parameter pack
 964   if (const auto *TTPT = getFunctionPackType(D)) {
 965     // Split the parameters into head, pack and tail
 966     auto IsExpandedPack = [TTPT](const ParmVarDecl *P) {
 967       return getUnderylingPackType(P) == TTPT;
 968     };
 969     ArrayRef<const ParmVarDecl *> Head = Parameters.take_until(IsExpandedPack);
 970     ArrayRef<const ParmVarDecl *> Pack =
 971         Parameters.drop_front(Head.size()).take_while(IsExpandedPack);
 972     ArrayRef<const ParmVarDecl *> Tail =
 973         Parameters.drop_front(Head.size() + Pack.size());
 974     SmallVector<const ParmVarDecl *> Result(Parameters.size());
 975     // Fill in non-pack parameters
 976     auto HeadIt = std::copy(Head.begin(), Head.end(), Result.begin());
 977     auto TailIt = std::copy(Tail.rbegin(), Tail.rend(), Result.rbegin());
 978     // Recurse on pack parameters
 979     size_t Depth = 0;
 980     const FunctionDecl *CurrentFunction = D;
 981     llvm::SmallSet<const FunctionTemplateDecl *, 4> SeenTemplates;
 982     if (const auto *Template = D->getPrimaryTemplate()) {
 983       SeenTemplates.insert(Template);
 984     }
 985     while (!Pack.empty() && CurrentFunction && Depth < MaxDepth) {
 986       // Find call expressions involving the pack
 987       ForwardingCallVisitor V{Pack};
 988       V.TraverseStmt(CurrentFunction->getBody());
 989       if (!V.Info) {
 990         break;
 991       }
 992       // If we found something: Fill in non-pack parameters
 993       auto Info = *V.Info;
 994       HeadIt = std::copy(Info.Head.begin(), Info.Head.end(), HeadIt);
 995       TailIt = std::copy(Info.Tail.rbegin(), Info.Tail.rend(), TailIt);
 996       // Prepare next recursion level
 997       Pack = Info.Pack;
 998       CurrentFunction = Info.PackTarget.value_or(nullptr);
 999       Depth++;
1000       // If we are recursing into a previously encountered function: Abort
1001       if (CurrentFunction) {
1002         if (const auto *Template = CurrentFunction->getPrimaryTemplate()) {
1003           bool NewFunction = SeenTemplates.insert(Template).second;
1004           if (!NewFunction) {
1005             return {Parameters.begin(), Parameters.end()};
1006           }
1007         }
1008       }
1009     }
1010     // Fill in the remaining unresolved pack parameters
1011     HeadIt = std::copy(Pack.begin(), Pack.end(), HeadIt);
1012     assert(TailIt.base() == HeadIt);
1013     return Result;
1014   }
1015   return {Parameters.begin(), Parameters.end()};
1016 }
1017
1018 bool isExpandedFromParameterPack(const ParmVarDecl *D) {
1019   return getUnderylingPackType(D) != nullptr;
1020 }
1021
1022 } // namespace clangd
1023 } // namespace clang