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 // Convenience lambdas for use as the 'Filter' parameter of
  20 // HeuristicResolver::resolveDependentMember().
  21 const auto NoFilter = [](const NamedDecl *D) { return true; };
  22 const auto NonStaticFilter = [](const NamedDecl *D) {
  23   return D->isCXXInstanceMember();
  24 };
  25 const auto StaticFilter = [](const NamedDecl *D) {
  26   return !D->isCXXInstanceMember();
  27 };
  28 const auto ValueFilter = [](const NamedDecl *D) { return isa<ValueDecl>(D); };
  29 const auto TypeFilter = [](const NamedDecl *D) { return isa<TypeDecl>(D); };
  30 const auto TemplateFilter = [](const NamedDecl *D) {
  31   return isa<TemplateDecl>(D);
  32 };
  33
  34 namespace {
  35
  36 const Type *resolveDeclsToType(const std::vector<const NamedDecl *> &Decls,
  37                                ASTContext &Ctx) {
  38   if (Decls.size() != 1) // Names an overload set -- just bail.
  39     return nullptr;
  40   if (const auto *TD = dyn_cast<TypeDecl>(Decls[0])) {
  41     return Ctx.getTypeDeclType(TD).getTypePtr();
  42   }
  43   if (const auto *VD = dyn_cast<ValueDecl>(Decls[0])) {
  44     return VD->getType().getTypePtrOrNull();
  45   }
  46   return nullptr;
  47 }
  48
  49 } // namespace
  50
  51 // Helper function for HeuristicResolver::resolveDependentMember()
  52 // which takes a possibly-dependent type `T` and heuristically
  53 // resolves it to a CXXRecordDecl in which we can try name lookup.
  54 CXXRecordDecl *HeuristicResolver::resolveTypeToRecordDecl(const Type *T) const {
  55   assert(T);
  56
  57   // Unwrap type sugar such as type aliases.
  58   T = T->getCanonicalTypeInternal().getTypePtr();
  59
  60   if (const auto *DNT = T->getAs<DependentNameType>()) {
  61     T = resolveDeclsToType(resolveDependentNameType(DNT), Ctx);
  62     if (!T)
  63       return nullptr;
  64     T = T->getCanonicalTypeInternal().getTypePtr();
  65   }
  66
  67   if (const auto *RT = T->getAs<RecordType>())
  68     return dyn_cast<CXXRecordDecl>(RT->getDecl());
  69
  70   if (const auto *ICNT = T->getAs<InjectedClassNameType>())
  71     T = ICNT->getInjectedSpecializationType().getTypePtrOrNull();
  72   if (!T)
  73     return nullptr;
  74
  75   const auto *TST = T->getAs<TemplateSpecializationType>();
  76   if (!TST)
  77     return nullptr;
  78
  79   const ClassTemplateDecl *TD = dyn_cast_or_null<ClassTemplateDecl>(
  80       TST->getTemplateName().getAsTemplateDecl());
  81   if (!TD)
  82     return nullptr;
  83
  84   return TD->getTemplatedDecl();
  85 }
  86
  87 const Type *HeuristicResolver::getPointeeType(const Type *T) const {
  88   if (!T)
  89     return nullptr;
  90
  91   if (T->isPointerType())
  92     return T->castAs<PointerType>()->getPointeeType().getTypePtrOrNull();
  93
  94   // Try to handle smart pointer types.
  95
  96   // Look up operator-> in the primary template. If we find one, it's probably a
  97   // smart pointer type.
  98   auto ArrowOps = resolveDependentMember(
  99       T, Ctx.DeclarationNames.getCXXOperatorName(OO_Arrow), NonStaticFilter);
 100   if (ArrowOps.empty())
 101     return nullptr;
 102
 103   // Getting the return type of the found operator-> method decl isn't useful,
 104   // because we discarded template arguments to perform lookup in the primary
 105   // template scope, so the return type would just have the form U* where U is a
 106   // template parameter type.
 107   // Instead, just handle the common case where the smart pointer type has the
 108   // form of SmartPtr<X, ...>, and assume X is the pointee type.
 109   auto *TST = T->getAs<TemplateSpecializationType>();
 110   if (!TST)
 111     return nullptr;
 112   if (TST->template_arguments().size() == 0)
 113     return nullptr;
 114   const TemplateArgument &FirstArg = TST->template_arguments()[0];
 115   if (FirstArg.getKind() != TemplateArgument::Type)
 116     return nullptr;
 117   return FirstArg.getAsType().getTypePtrOrNull();
 118 }
 119
 120 std::vector<const NamedDecl *> HeuristicResolver::resolveMemberExpr(
 121     const CXXDependentScopeMemberExpr *ME) const {
 122   // If the expression has a qualifier, try resolving the member inside the
 123   // qualifier's type.
 124   // Note that we cannot use a NonStaticFilter in either case, for a couple
 125   // of reasons:
 126   //   1. It's valid to access a static member using instance member syntax,
 127   //      e.g. `instance.static_member`.
 128   //   2. We can sometimes get a CXXDependentScopeMemberExpr for static
 129   //      member syntax too, e.g. if `X::static_member` occurs inside
 130   //      an instance method, it's represented as a CXXDependentScopeMemberExpr
 131   //      with `this` as the base expression as `X` as the qualifier
 132   //      (which could be valid if `X` names a base class after instantiation).
 133   if (NestedNameSpecifier *NNS = ME->getQualifier()) {
 134     if (const Type *QualifierType = resolveNestedNameSpecifierToType(NNS)) {
 135       auto Decls =
 136           resolveDependentMember(QualifierType, ME->getMember(), NoFilter);
 137       if (!Decls.empty())
 138         return Decls;
 139     }
 140
 141     // Do not proceed to try resolving the member in the expression's base type
 142     // without regard to the qualifier, as that could produce incorrect results.
 143     // For example, `void foo() { this->Base::foo(); }` shouldn't resolve to
 144     // foo() itself!
 145     return {};
 146   }
 147
 148   // Try resolving the member inside the expression's base type.
 149   const Type *BaseType = ME->getBaseType().getTypePtrOrNull();
 150   if (ME->isArrow()) {
 151     BaseType = getPointeeType(BaseType);
 152   }
 153   if (!BaseType)
 154     return {};
 155   if (const auto *BT = BaseType->getAs<BuiltinType>()) {
 156     // If BaseType is the type of a dependent expression, it's just
 157     // represented as BuiltinType::Dependent which gives us no information. We
 158     // can get further by analyzing the dependent expression.
 159     Expr *Base = ME->isImplicitAccess() ? nullptr : ME->getBase();
 160     if (Base && BT->getKind() == BuiltinType::Dependent) {
 161       BaseType = resolveExprToType(Base);
 162     }
 163   }
 164   return resolveDependentMember(BaseType, ME->getMember(), NoFilter);
 165 }
 166
 167 std::vector<const NamedDecl *> HeuristicResolver::resolveDeclRefExpr(
 168     const DependentScopeDeclRefExpr *RE) const {
 169   return resolveDependentMember(RE->getQualifier()->getAsType(),
 170                                 RE->getDeclName(), StaticFilter);
 171 }
 172
 173 std::vector<const NamedDecl *>
 174 HeuristicResolver::resolveTypeOfCallExpr(const CallExpr *CE) const {
 175   const auto *CalleeType = resolveExprToType(CE->getCallee());
 176   if (!CalleeType)
 177     return {};
 178   if (const auto *FnTypePtr = CalleeType->getAs<PointerType>())
 179     CalleeType = FnTypePtr->getPointeeType().getTypePtr();
 180   if (const FunctionType *FnType = CalleeType->getAs<FunctionType>()) {
 181     if (const auto *D =
 182             resolveTypeToRecordDecl(FnType->getReturnType().getTypePtr())) {
 183       return {D};
 184     }
 185   }
 186   return {};
 187 }
 188
 189 std::vector<const NamedDecl *>
 190 HeuristicResolver::resolveCalleeOfCallExpr(const CallExpr *CE) const {
 191   if (const auto *ND = dyn_cast_or_null<NamedDecl>(CE->getCalleeDecl())) {
 192     return {ND};
 193   }
 194
 195   return resolveExprToDecls(CE->getCallee());
 196 }
 197
 198 std::vector<const NamedDecl *> HeuristicResolver::resolveUsingValueDecl(
 199     const UnresolvedUsingValueDecl *UUVD) const {
 200   return resolveDependentMember(UUVD->getQualifier()->getAsType(),
 201                                 UUVD->getNameInfo().getName(), ValueFilter);
 202 }
 203
 204 std::vector<const NamedDecl *> HeuristicResolver::resolveDependentNameType(
 205     const DependentNameType *DNT) const {
 206   return resolveDependentMember(
 207       resolveNestedNameSpecifierToType(DNT->getQualifier()),
 208       DNT->getIdentifier(), TypeFilter);
 209 }
 210
 211 std::vector<const NamedDecl *>
 212 HeuristicResolver::resolveTemplateSpecializationType(
 213     const DependentTemplateSpecializationType *DTST) const {
 214   return resolveDependentMember(
 215       resolveNestedNameSpecifierToType(DTST->getQualifier()),
 216       DTST->getIdentifier(), TemplateFilter);
 217 }
 218
 219 std::vector<const NamedDecl *>
 220 HeuristicResolver::resolveExprToDecls(const Expr *E) const {
 221   if (const auto *ME = dyn_cast<CXXDependentScopeMemberExpr>(E)) {
 222     return resolveMemberExpr(ME);
 223   }
 224   if (const auto *RE = dyn_cast<DependentScopeDeclRefExpr>(E)) {
 225     return resolveDeclRefExpr(RE);
 226   }
 227   if (const auto *OE = dyn_cast<OverloadExpr>(E)) {
 228     return {OE->decls_begin(), OE->decls_end()};
 229   }
 230   if (const auto *CE = dyn_cast<CallExpr>(E)) {
 231     return resolveTypeOfCallExpr(CE);
 232   }
 233   if (const auto *ME = dyn_cast<MemberExpr>(E))
 234     return {ME->getMemberDecl()};
 235
 236   return {};
 237 }
 238
 239 const Type *HeuristicResolver::resolveExprToType(const Expr *E) const {
 240   std::vector<const NamedDecl *> Decls = resolveExprToDecls(E);
 241   if (!Decls.empty())
 242     return resolveDeclsToType(Decls, Ctx);
 243
 244   return E->getType().getTypePtr();
 245 }
 246
 247 const Type *HeuristicResolver::resolveNestedNameSpecifierToType(
 248     const NestedNameSpecifier *NNS) const {
 249   if (!NNS)
 250     return nullptr;
 251
 252   // The purpose of this function is to handle the dependent (Kind ==
 253   // Identifier) case, but we need to recurse on the prefix because
 254   // that may be dependent as well, so for convenience handle
 255   // the TypeSpec cases too.
 256   switch (NNS->getKind()) {
 257   case NestedNameSpecifier::TypeSpec:
 258   case NestedNameSpecifier::TypeSpecWithTemplate:
 259     return NNS->getAsType();
 260   case NestedNameSpecifier::Identifier: {
 261     return resolveDeclsToType(
 262         resolveDependentMember(
 263             resolveNestedNameSpecifierToType(NNS->getPrefix()),
 264             NNS->getAsIdentifier(), TypeFilter),
 265         Ctx);
 266   }
 267   default:
 268     break;
 269   }
 270   return nullptr;
 271 }
 272
 273 namespace {
 274
 275 bool isOrdinaryMember(const NamedDecl *ND) {
 276   return ND->isInIdentifierNamespace(Decl::IDNS_Ordinary | Decl::IDNS_Tag |
 277                                      Decl::IDNS_Member);
 278 }
 279
 280 bool findOrdinaryMember(const CXXRecordDecl *RD, CXXBasePath &Path,
 281                         DeclarationName Name) {
 282   Path.Decls = RD->lookup(Name).begin();
 283   for (DeclContext::lookup_iterator I = Path.Decls, E = I.end(); I != E; ++I)
 284     if (isOrdinaryMember(*I))
 285       return true;
 286
 287   return false;
 288 }
 289
 290 } // namespace
 291
 292 bool HeuristicResolver::findOrdinaryMemberInDependentClasses(
 293     const CXXBaseSpecifier *Specifier, CXXBasePath &Path,
 294     DeclarationName Name) const {
 295   CXXRecordDecl *RD =
 296       resolveTypeToRecordDecl(Specifier->getType().getTypePtr());
 297   if (!RD)
 298     return false;
 299   return findOrdinaryMember(RD, Path, Name);
 300 }
 301
 302 std::vector<const NamedDecl *> HeuristicResolver::lookupDependentName(
 303     CXXRecordDecl *RD, DeclarationName Name,
 304     llvm::function_ref<bool(const NamedDecl *ND)> Filter) const {
 305   std::vector<const NamedDecl *> Results;
 306
 307   // Lookup in the class.
 308   bool AnyOrdinaryMembers = false;
 309   for (const NamedDecl *ND : RD->lookup(Name)) {
 310     if (isOrdinaryMember(ND))
 311       AnyOrdinaryMembers = true;
 312     if (Filter(ND))
 313       Results.push_back(ND);
 314   }
 315   if (AnyOrdinaryMembers)
 316     return Results;
 317
 318   // Perform lookup into our base classes.
 319   CXXBasePaths Paths;
 320   Paths.setOrigin(RD);
 321   if (!RD->lookupInBases(
 322           [&](const CXXBaseSpecifier *Specifier, CXXBasePath &Path) {
 323             return findOrdinaryMemberInDependentClasses(Specifier, Path, Name);
 324           },
 325           Paths, /*LookupInDependent=*/true))
 326     return Results;
 327   for (DeclContext::lookup_iterator I = Paths.front().Decls, E = I.end();
 328        I != E; ++I) {
 329     if (isOrdinaryMember(*I) && Filter(*I))
 330       Results.push_back(*I);
 331   }
 332   return Results;
 333 }
 334
 335 std::vector<const NamedDecl *> HeuristicResolver::resolveDependentMember(
 336     const Type *T, DeclarationName Name,
 337     llvm::function_ref<bool(const NamedDecl *ND)> Filter) const {
 338   if (!T)
 339     return {};
 340   if (auto *ET = T->getAs<EnumType>()) {
 341     auto Result = ET->getDecl()->lookup(Name);
 342     return {Result.begin(), Result.end()};
 343   }
 344   if (auto *RD = resolveTypeToRecordDecl(T)) {
 345     if (!RD->hasDefinition())
 346       return {};
 347     RD = RD->getDefinition();
 348     return lookupDependentName(RD, Name, Filter);
 349   }
 350   return {};
 351 }
 352
 353 } // namespace clangd
 354 } // namespace clang