clang-tools-extra/clangd/HeuristicResolver.cpp

   1 //===--- HeuristicResolver.cpp ---------------------------*- 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 "HeuristicResolver.h"
  10 #include "clang/AST/ASTContext.h"
  11 #include "clang/AST/CXXInheritance.h"
  12 #include "clang/AST/DeclTemplate.h"
  13 #include "clang/AST/ExprCXX.h"
  14 #include "clang/AST/Type.h"
  15
  16 namespace clang {
  17 namespace clangd {
  18
  19 namespace {
  20
  21 // Helper class for implementing HeuristicResolver.
  22 // Unlike HeuristicResolver which is a long-lived class,
  23 // a new instance of this class is created for every external
  24 // call into a HeuristicResolver operation. That allows this
  25 // class to store state that's local to such a top-level call,
  26 // particularly "recursion protection sets" that keep track of
  27 // nodes that have already been seen to avoid infinite recursion.
  28 class HeuristicResolverImpl {
  29 public:
  30   HeuristicResolverImpl(ASTContext &Ctx) : Ctx(Ctx) {}
  31
  32   // These functions match the public interface of HeuristicResolver
  33   // (but aren't const since they may modify the recursion protection sets).
  34   std::vector<const NamedDecl *>
  35   resolveMemberExpr(const CXXDependentScopeMemberExpr *ME);
  36   std::vector<const NamedDecl *>
  37   resolveDeclRefExpr(const DependentScopeDeclRefExpr *RE);
  38   std::vector<const NamedDecl *> resolveTypeOfCallExpr(const CallExpr *CE);
  39   std::vector<const NamedDecl *> resolveCalleeOfCallExpr(const CallExpr *CE);
  40   std::vector<const NamedDecl *>
  41   resolveUsingValueDecl(const UnresolvedUsingValueDecl *UUVD);
  42   std::vector<const NamedDecl *>
  43   resolveDependentNameType(const DependentNameType *DNT);
  44   std::vector<const NamedDecl *> resolveTemplateSpecializationType(
  45       const DependentTemplateSpecializationType *DTST);
  46   const Type *resolveNestedNameSpecifierToType(const NestedNameSpecifier *NNS);
  47   const Type *getPointeeType(const Type *T);
  48
  49 private:
  50   ASTContext &Ctx;
  51
  52   // Recursion protection sets
  53   llvm::SmallSet<const DependentNameType *, 4> SeenDependentNameTypes;
  54
  55   // Given a tag-decl type and a member name, heuristically resolve the
  56   // name to one or more declarations.
  57   // The current heuristic is simply to look up the name in the primary
  58   // template. This is a heuristic because the template could potentially
  59   // have specializations that declare different members.
  60   // Multiple declarations could be returned if the name is overloaded
  61   // (e.g. an overloaded method in the primary template).
  62   // This heuristic will give the desired answer in many cases, e.g.
  63   // for a call to vector<T>::size().
  64   std::vector<const NamedDecl *>
  65   resolveDependentMember(const Type *T, DeclarationName Name,
  66                          llvm::function_ref<bool(const NamedDecl *ND)> Filter);
  67
  68   // Try to heuristically resolve the type of a possibly-dependent expression
  69   // `E`.
  70   const Type *resolveExprToType(const Expr *E);
  71   std::vector<const NamedDecl *> resolveExprToDecls(const Expr *E);
  72
  73   // Helper function for HeuristicResolver::resolveDependentMember()
  74   // which takes a possibly-dependent type `T` and heuristically
  75   // resolves it to a CXXRecordDecl in which we can try name lookup.
  76   CXXRecordDecl *resolveTypeToRecordDecl(const Type *T);
  77
  78   // This is a reimplementation of CXXRecordDecl::lookupDependentName()
  79   // so that the implementation can call into other HeuristicResolver helpers.
  80   // FIXME: Once HeuristicResolver is upstreamed to the clang libraries
  81   // (https://github.com/clangd/clangd/discussions/1662),
  82   // CXXRecordDecl::lookupDepenedentName() can be removed, and its call sites
  83   // can be modified to benefit from the more comprehensive heuristics offered
  84   // by HeuristicResolver instead.
  85   std::vector<const NamedDecl *>
  86   lookupDependentName(CXXRecordDecl *RD, DeclarationName Name,
  87                       llvm::function_ref<bool(const NamedDecl *ND)> Filter);
  88   bool findOrdinaryMemberInDependentClasses(const CXXBaseSpecifier *Specifier,
  89                                             CXXBasePath &Path,
  90                                             DeclarationName Name);
  91 };
  92
  93 // Convenience lambdas for use as the 'Filter' parameter of
  94 // HeuristicResolver::resolveDependentMember().
  95 const auto NoFilter = [](const NamedDecl *D) { return true; };
  96 const auto NonStaticFilter = [](const NamedDecl *D) {
  97   return D->isCXXInstanceMember();
  98 };
  99 const auto StaticFilter = [](const NamedDecl *D) {
 100   return !D->isCXXInstanceMember();
 101 };
 102 const auto ValueFilter = [](const NamedDecl *D) { return isa<ValueDecl>(D); };
 103 const auto TypeFilter = [](const NamedDecl *D) { return isa<TypeDecl>(D); };
 104 const auto TemplateFilter = [](const NamedDecl *D) {
 105   return isa<TemplateDecl>(D);
 106 };
 107
 108 const Type *resolveDeclsToType(const std::vector<const NamedDecl *> &Decls,
 109                                ASTContext &Ctx) {
 110   if (Decls.size() != 1) // Names an overload set -- just bail.
 111     return nullptr;
 112   if (const auto *TD = dyn_cast<TypeDecl>(Decls[0])) {
 113     return Ctx.getTypeDeclType(TD).getTypePtr();
 114   }
 115   if (const auto *VD = dyn_cast<ValueDecl>(Decls[0])) {
 116     return VD->getType().getTypePtrOrNull();
 117   }
 118   return nullptr;
 119 }
 120
 121 // Helper function for HeuristicResolver::resolveDependentMember()
 122 // which takes a possibly-dependent type `T` and heuristically
 123 // resolves it to a CXXRecordDecl in which we can try name lookup.
 124 CXXRecordDecl *HeuristicResolverImpl::resolveTypeToRecordDecl(const Type *T) {
 125   assert(T);
 126
 127   // Unwrap type sugar such as type aliases.
 128   T = T->getCanonicalTypeInternal().getTypePtr();
 129
 130   if (const auto *DNT = T->getAs<DependentNameType>()) {
 131     T = resolveDeclsToType(resolveDependentNameType(DNT), Ctx);
 132     if (!T)
 133       return nullptr;
 134     T = T->getCanonicalTypeInternal().getTypePtr();
 135   }
 136
 137   if (const auto *RT = T->getAs<RecordType>())
 138     return dyn_cast<CXXRecordDecl>(RT->getDecl());
 139
 140   if (const auto *ICNT = T->getAs<InjectedClassNameType>())
 141     T = ICNT->getInjectedSpecializationType().getTypePtrOrNull();
 142   if (!T)
 143     return nullptr;
 144
 145   const auto *TST = T->getAs<TemplateSpecializationType>();
 146   if (!TST)
 147     return nullptr;
 148
 149   const ClassTemplateDecl *TD = dyn_cast_or_null<ClassTemplateDecl>(
 150       TST->getTemplateName().getAsTemplateDecl());
 151   if (!TD)
 152     return nullptr;
 153
 154   return TD->getTemplatedDecl();
 155 }
 156
 157 const Type *HeuristicResolverImpl::getPointeeType(const Type *T) {
 158   if (!T)
 159     return nullptr;
 160
 161   if (T->isPointerType())
 162     return T->castAs<PointerType>()->getPointeeType().getTypePtrOrNull();
 163
 164   // Try to handle smart pointer types.
 165
 166   // Look up operator-> in the primary template. If we find one, it's probably a
 167   // smart pointer type.
 168   auto ArrowOps = resolveDependentMember(
 169       T, Ctx.DeclarationNames.getCXXOperatorName(OO_Arrow), NonStaticFilter);
 170   if (ArrowOps.empty())
 171     return nullptr;
 172
 173   // Getting the return type of the found operator-> method decl isn't useful,
 174   // because we discarded template arguments to perform lookup in the primary
 175   // template scope, so the return type would just have the form U* where U is a
 176   // template parameter type.
 177   // Instead, just handle the common case where the smart pointer type has the
 178   // form of SmartPtr<X, ...>, and assume X is the pointee type.
 179   auto *TST = T->getAs<TemplateSpecializationType>();
 180   if (!TST)
 181     return nullptr;
 182   if (TST->template_arguments().size() == 0)
 183     return nullptr;
 184   const TemplateArgument &FirstArg = TST->template_arguments()[0];
 185   if (FirstArg.getKind() != TemplateArgument::Type)
 186     return nullptr;
 187   return FirstArg.getAsType().getTypePtrOrNull();
 188 }
 189
 190 std::vector<const NamedDecl *> HeuristicResolverImpl::resolveMemberExpr(
 191     const CXXDependentScopeMemberExpr *ME) {
 192   // If the expression has a qualifier, try resolving the member inside the
 193   // qualifier's type.
 194   // Note that we cannot use a NonStaticFilter in either case, for a couple
 195   // of reasons:
 196   //   1. It's valid to access a static member using instance member syntax,
 197   //      e.g. `instance.static_member`.
 198   //   2. We can sometimes get a CXXDependentScopeMemberExpr for static
 199   //      member syntax too, e.g. if `X::static_member` occurs inside
 200   //      an instance method, it's represented as a CXXDependentScopeMemberExpr
 201   //      with `this` as the base expression as `X` as the qualifier
 202   //      (which could be valid if `X` names a base class after instantiation).
 203   if (NestedNameSpecifier *NNS = ME->getQualifier()) {
 204     if (const Type *QualifierType = resolveNestedNameSpecifierToType(NNS)) {
 205       auto Decls =
 206           resolveDependentMember(QualifierType, ME->getMember(), NoFilter);
 207       if (!Decls.empty())
 208         return Decls;
 209     }
 210
 211     // Do not proceed to try resolving the member in the expression's base type
 212     // without regard to the qualifier, as that could produce incorrect results.
 213     // For example, `void foo() { this->Base::foo(); }` shouldn't resolve to
 214     // foo() itself!
 215     return {};
 216   }
 217
 218   // Try resolving the member inside the expression's base type.
 219   const Type *BaseType = ME->getBaseType().getTypePtrOrNull();
 220   if (ME->isArrow()) {
 221     BaseType = getPointeeType(BaseType);
 222   }
 223   if (!BaseType)
 224     return {};
 225   if (const auto *BT = BaseType->getAs<BuiltinType>()) {
 226     // If BaseType is the type of a dependent expression, it's just
 227     // represented as BuiltinType::Dependent which gives us no information. We
 228     // can get further by analyzing the dependent expression.
 229     Expr *Base = ME->isImplicitAccess() ? nullptr : ME->getBase();
 230     if (Base && BT->getKind() == BuiltinType::Dependent) {
 231       BaseType = resolveExprToType(Base);
 232     }
 233   }
 234   return resolveDependentMember(BaseType, ME->getMember(), NoFilter);
 235 }
 236
 237 std::vector<const NamedDecl *>
 238 HeuristicResolverImpl::resolveDeclRefExpr(const DependentScopeDeclRefExpr *RE) {
 239   return resolveDependentMember(RE->getQualifier()->getAsType(),
 240                                 RE->getDeclName(), StaticFilter);
 241 }
 242
 243 std::vector<const NamedDecl *>
 244 HeuristicResolverImpl::resolveTypeOfCallExpr(const CallExpr *CE) {
 245   const auto *CalleeType = resolveExprToType(CE->getCallee());
 246   if (!CalleeType)
 247     return {};
 248   if (const auto *FnTypePtr = CalleeType->getAs<PointerType>())
 249     CalleeType = FnTypePtr->getPointeeType().getTypePtr();
 250   if (const FunctionType *FnType = CalleeType->getAs<FunctionType>()) {
 251     if (const auto *D =
 252             resolveTypeToRecordDecl(FnType->getReturnType().getTypePtr())) {
 253       return {D};
 254     }
 255   }
 256   return {};
 257 }
 258
 259 std::vector<const NamedDecl *>
 260 HeuristicResolverImpl::resolveCalleeOfCallExpr(const CallExpr *CE) {
 261   if (const auto *ND = dyn_cast_or_null<NamedDecl>(CE->getCalleeDecl())) {
 262     return {ND};
 263   }
 264
 265   return resolveExprToDecls(CE->getCallee());
 266 }
 267
 268 std::vector<const NamedDecl *> HeuristicResolverImpl::resolveUsingValueDecl(
 269     const UnresolvedUsingValueDecl *UUVD) {
 270   return resolveDependentMember(UUVD->getQualifier()->getAsType(),
 271                                 UUVD->getNameInfo().getName(), ValueFilter);
 272 }
 273
 274 std::vector<const NamedDecl *>
 275 HeuristicResolverImpl::resolveDependentNameType(const DependentNameType *DNT) {
 276   if (auto [_, inserted] = SeenDependentNameTypes.insert(DNT); !inserted)
 277     return {};
 278   return resolveDependentMember(
 279       resolveNestedNameSpecifierToType(DNT->getQualifier()),
 280       DNT->getIdentifier(), TypeFilter);
 281 }
 282
 283 std::vector<const NamedDecl *>
 284 HeuristicResolverImpl::resolveTemplateSpecializationType(
 285     const DependentTemplateSpecializationType *DTST) {
 286   return resolveDependentMember(
 287       resolveNestedNameSpecifierToType(DTST->getQualifier()),
 288       DTST->getIdentifier(), TemplateFilter);
 289 }
 290
 291 std::vector<const NamedDecl *>
 292 HeuristicResolverImpl::resolveExprToDecls(const Expr *E) {
 293   if (const auto *ME = dyn_cast<CXXDependentScopeMemberExpr>(E)) {
 294     return resolveMemberExpr(ME);
 295   }
 296   if (const auto *RE = dyn_cast<DependentScopeDeclRefExpr>(E)) {
 297     return resolveDeclRefExpr(RE);
 298   }
 299   if (const auto *OE = dyn_cast<OverloadExpr>(E)) {
 300     return {OE->decls_begin(), OE->decls_end()};
 301   }
 302   if (const auto *CE = dyn_cast<CallExpr>(E)) {
 303     return resolveTypeOfCallExpr(CE);
 304   }
 305   if (const auto *ME = dyn_cast<MemberExpr>(E))
 306     return {ME->getMemberDecl()};
 307
 308   return {};
 309 }
 310
 311 const Type *HeuristicResolverImpl::resolveExprToType(const Expr *E) {
 312   std::vector<const NamedDecl *> Decls = resolveExprToDecls(E);
 313   if (!Decls.empty())
 314     return resolveDeclsToType(Decls, Ctx);
 315
 316   return E->getType().getTypePtr();
 317 }
 318
 319 const Type *HeuristicResolverImpl::resolveNestedNameSpecifierToType(
 320     const NestedNameSpecifier *NNS) {
 321   if (!NNS)
 322     return nullptr;
 323
 324   // The purpose of this function is to handle the dependent (Kind ==
 325   // Identifier) case, but we need to recurse on the prefix because
 326   // that may be dependent as well, so for convenience handle
 327   // the TypeSpec cases too.
 328   switch (NNS->getKind()) {
 329   case NestedNameSpecifier::TypeSpec:
 330   case NestedNameSpecifier::TypeSpecWithTemplate:
 331     return NNS->getAsType();
 332   case NestedNameSpecifier::Identifier: {
 333     return resolveDeclsToType(
 334         resolveDependentMember(
 335             resolveNestedNameSpecifierToType(NNS->getPrefix()),
 336             NNS->getAsIdentifier(), TypeFilter),
 337         Ctx);
 338   }
 339   default:
 340     break;
 341   }
 342   return nullptr;
 343 }
 344
 345 bool isOrdinaryMember(const NamedDecl *ND) {
 346   return ND->isInIdentifierNamespace(Decl::IDNS_Ordinary | Decl::IDNS_Tag |
 347                                      Decl::IDNS_Member);
 348 }
 349
 350 bool findOrdinaryMember(const CXXRecordDecl *RD, CXXBasePath &Path,
 351                         DeclarationName Name) {
 352   Path.Decls = RD->lookup(Name).begin();
 353   for (DeclContext::lookup_iterator I = Path.Decls, E = I.end(); I != E; ++I)
 354     if (isOrdinaryMember(*I))
 355       return true;
 356
 357   return false;
 358 }
 359
 360 bool HeuristicResolverImpl::findOrdinaryMemberInDependentClasses(
 361     const CXXBaseSpecifier *Specifier, CXXBasePath &Path,
 362     DeclarationName Name) {
 363   CXXRecordDecl *RD =
 364       resolveTypeToRecordDecl(Specifier->getType().getTypePtr());
 365   if (!RD)
 366     return false;
 367   return findOrdinaryMember(RD, Path, Name);
 368 }
 369
 370 std::vector<const NamedDecl *> HeuristicResolverImpl::lookupDependentName(
 371     CXXRecordDecl *RD, DeclarationName Name,
 372     llvm::function_ref<bool(const NamedDecl *ND)> Filter) {
 373   std::vector<const NamedDecl *> Results;
 374
 375   // Lookup in the class.
 376   bool AnyOrdinaryMembers = false;
 377   for (const NamedDecl *ND : RD->lookup(Name)) {
 378     if (isOrdinaryMember(ND))
 379       AnyOrdinaryMembers = true;
 380     if (Filter(ND))
 381       Results.push_back(ND);
 382   }
 383   if (AnyOrdinaryMembers)
 384     return Results;
 385
 386   // Perform lookup into our base classes.
 387   CXXBasePaths Paths;
 388   Paths.setOrigin(RD);
 389   if (!RD->lookupInBases(
 390           [&](const CXXBaseSpecifier *Specifier, CXXBasePath &Path) {
 391             return findOrdinaryMemberInDependentClasses(Specifier, Path, Name);
 392           },
 393           Paths, /*LookupInDependent=*/true))
 394     return Results;
 395   for (DeclContext::lookup_iterator I = Paths.front().Decls, E = I.end();
 396        I != E; ++I) {
 397     if (isOrdinaryMember(*I) && Filter(*I))
 398       Results.push_back(*I);
 399   }
 400   return Results;
 401 }
 402
 403 std::vector<const NamedDecl *> HeuristicResolverImpl::resolveDependentMember(
 404     const Type *T, DeclarationName Name,
 405     llvm::function_ref<bool(const NamedDecl *ND)> Filter) {
 406   if (!T)
 407     return {};
 408   if (auto *ET = T->getAs<EnumType>()) {
 409     auto Result = ET->getDecl()->lookup(Name);
 410     return {Result.begin(), Result.end()};
 411   }
 412   if (auto *RD = resolveTypeToRecordDecl(T)) {
 413     if (!RD->hasDefinition())
 414       return {};
 415     RD = RD->getDefinition();
 416     return lookupDependentName(RD, Name, Filter);
 417   }
 418   return {};
 419 }
 420 } // namespace
 421
 422 std::vector<const NamedDecl *> HeuristicResolver::resolveMemberExpr(
 423     const CXXDependentScopeMemberExpr *ME) const {
 424   return HeuristicResolverImpl(Ctx).resolveMemberExpr(ME);
 425 }
 426 std::vector<const NamedDecl *> HeuristicResolver::resolveDeclRefExpr(
 427     const DependentScopeDeclRefExpr *RE) const {
 428   return HeuristicResolverImpl(Ctx).resolveDeclRefExpr(RE);
 429 }
 430 std::vector<const NamedDecl *>
 431 HeuristicResolver::resolveTypeOfCallExpr(const CallExpr *CE) const {
 432   return HeuristicResolverImpl(Ctx).resolveTypeOfCallExpr(CE);
 433 }
 434 std::vector<const NamedDecl *>
 435 HeuristicResolver::resolveCalleeOfCallExpr(const CallExpr *CE) const {
 436   return HeuristicResolverImpl(Ctx).resolveCalleeOfCallExpr(CE);
 437 }
 438 std::vector<const NamedDecl *> HeuristicResolver::resolveUsingValueDecl(
 439     const UnresolvedUsingValueDecl *UUVD) const {
 440   return HeuristicResolverImpl(Ctx).resolveUsingValueDecl(UUVD);
 441 }
 442 std::vector<const NamedDecl *> HeuristicResolver::resolveDependentNameType(
 443     const DependentNameType *DNT) const {
 444   return HeuristicResolverImpl(Ctx).resolveDependentNameType(DNT);
 445 }
 446 std::vector<const NamedDecl *>
 447 HeuristicResolver::resolveTemplateSpecializationType(
 448     const DependentTemplateSpecializationType *DTST) const {
 449   return HeuristicResolverImpl(Ctx).resolveTemplateSpecializationType(DTST);
 450 }
 451 const Type *HeuristicResolver::resolveNestedNameSpecifierToType(
 452     const NestedNameSpecifier *NNS) const {
 453   return HeuristicResolverImpl(Ctx).resolveNestedNameSpecifierToType(NNS);
 454 }
 455 const Type *HeuristicResolver::getPointeeType(const Type *T) const {
 456   return HeuristicResolverImpl(Ctx).getPointeeType(T);
 457 }
 458
 459 } // namespace clangd
 460 } // namespace clang