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