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 = 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