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