lib/Tooling/Refactoring/Rename/USRLocFinder.cpp

   1 //===--- USRLocFinder.cpp - Clang refactoring library ---------------------===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 ///
  10 /// \file
  11 /// \brief Methods for finding all instances of a USR. Our strategy is very
  12 /// simple; we just compare the USR at every relevant AST node with the one
  13 /// provided.
  14 ///
  15 //===----------------------------------------------------------------------===//
  16
  17 #include "clang/Tooling/Refactoring/Rename/USRLocFinder.h"
  18 #include "clang/AST/ASTContext.h"
  19 #include "clang/AST/RecursiveASTVisitor.h"
  20 #include "clang/Basic/LLVM.h"
  21 #include "clang/Basic/SourceLocation.h"
  22 #include "clang/Basic/SourceManager.h"
  23 #include "clang/Lex/Lexer.h"
  24 #include "clang/Tooling/Core/Lookup.h"
  25 #include "clang/Tooling/Refactoring/Rename/USRFinder.h"
  26 #include "llvm/ADT/StringRef.h"
  27 #include "llvm/Support/Casting.h"
  28 #include <cstddef>
  29 #include <set>
  30 #include <string>
  31 #include <vector>
  32
  33 using namespace llvm;
  34
  35 namespace clang {
  36 namespace tooling {
  37
  38 namespace {
  39
  40 // \brief This visitor recursively searches for all instances of a USR in a
  41 // translation unit and stores them for later usage.
  42 class USRLocFindingASTVisitor
  43     : public clang::RecursiveASTVisitor<USRLocFindingASTVisitor> {
  44 public:
  45   explicit USRLocFindingASTVisitor(const std::vector<std::string> &USRs,
  46                                    StringRef PrevName,
  47                                    const ASTContext &Context)
  48       : USRSet(USRs.begin(), USRs.end()), PrevName(PrevName), Context(Context) {
  49   }
  50
  51   // Declaration visitors:
  52
  53   bool VisitCXXConstructorDecl(clang::CXXConstructorDecl *ConstructorDecl) {
  54     for (const auto *Initializer : ConstructorDecl->inits()) {
  55       // Ignore implicit initializers.
  56       if (!Initializer->isWritten())
  57         continue;
  58       if (const clang::FieldDecl *FieldDecl = Initializer->getMember()) {
  59         if (USRSet.find(getUSRForDecl(FieldDecl)) != USRSet.end())
  60           LocationsFound.push_back(Initializer->getSourceLocation());
  61       }
  62     }
  63     return true;
  64   }
  65
  66   bool VisitNamedDecl(const NamedDecl *Decl) {
  67     if (USRSet.find(getUSRForDecl(Decl)) != USRSet.end())
  68       checkAndAddLocation(Decl->getLocation());
  69     return true;
  70   }
  71
  72   // Expression visitors:
  73
  74   bool VisitDeclRefExpr(const DeclRefExpr *Expr) {
  75     const NamedDecl *Decl = Expr->getFoundDecl();
  76
  77     if (USRSet.find(getUSRForDecl(Decl)) != USRSet.end()) {
  78       const SourceManager &Manager = Decl->getASTContext().getSourceManager();
  79       SourceLocation Location = Manager.getSpellingLoc(Expr->getLocation());
  80       checkAndAddLocation(Location);
  81     }
  82
  83     return true;
  84   }
  85
  86   bool VisitMemberExpr(const MemberExpr *Expr) {
  87     const NamedDecl *Decl = Expr->getFoundDecl().getDecl();
  88     if (USRSet.find(getUSRForDecl(Decl)) != USRSet.end()) {
  89       const SourceManager &Manager = Decl->getASTContext().getSourceManager();
  90       SourceLocation Location = Manager.getSpellingLoc(Expr->getMemberLoc());
  91       checkAndAddLocation(Location);
  92     }
  93     return true;
  94   }
  95
  96   // Other visitors:
  97
  98   bool VisitTypeLoc(const TypeLoc Loc) {
  99     if (USRSet.find(getUSRForDecl(Loc.getType()->getAsCXXRecordDecl())) !=
 100         USRSet.end())
 101       checkAndAddLocation(Loc.getBeginLoc());
 102     if (const auto *TemplateTypeParm =
 103             dyn_cast<TemplateTypeParmType>(Loc.getType())) {
 104       if (USRSet.find(getUSRForDecl(TemplateTypeParm->getDecl())) !=
 105           USRSet.end())
 106         checkAndAddLocation(Loc.getBeginLoc());
 107     }
 108     return true;
 109   }
 110
 111   // Non-visitors:
 112
 113   // \brief Returns a list of unique locations. Duplicate or overlapping
 114   // locations are erroneous and should be reported!
 115   const std::vector<clang::SourceLocation> &getLocationsFound() const {
 116     return LocationsFound;
 117   }
 118
 119   // Namespace traversal:
 120   void handleNestedNameSpecifierLoc(NestedNameSpecifierLoc NameLoc) {
 121     while (NameLoc) {
 122       const NamespaceDecl *Decl =
 123           NameLoc.getNestedNameSpecifier()->getAsNamespace();
 124       if (Decl && USRSet.find(getUSRForDecl(Decl)) != USRSet.end())
 125         checkAndAddLocation(NameLoc.getLocalBeginLoc());
 126       NameLoc = NameLoc.getPrefix();
 127     }
 128   }
 129
 130 private:
 131   void checkAndAddLocation(SourceLocation Loc) {
 132     const SourceLocation BeginLoc = Loc;
 133     const SourceLocation EndLoc = Lexer::getLocForEndOfToken(
 134         BeginLoc, 0, Context.getSourceManager(), Context.getLangOpts());
 135     StringRef TokenName =
 136         Lexer::getSourceText(CharSourceRange::getTokenRange(BeginLoc, EndLoc),
 137                              Context.getSourceManager(), Context.getLangOpts());
 138     size_t Offset = TokenName.find(PrevName);
 139
 140     // The token of the source location we find actually has the old
 141     // name.
 142     if (Offset != StringRef::npos)
 143       LocationsFound.push_back(BeginLoc.getLocWithOffset(Offset));
 144   }
 145
 146   const std::set<std::string> USRSet;
 147   const std::string PrevName;
 148   std::vector<clang::SourceLocation> LocationsFound;
 149   const ASTContext &Context;
 150 };
 151
 152 SourceLocation StartLocationForType(TypeLoc TL) {
 153   // For elaborated types (e.g. `struct a::A`) we want the portion after the
 154   // `struct` but including the namespace qualifier, `a::`.
 155   if (auto ElaboratedTypeLoc = TL.getAs<clang::ElaboratedTypeLoc>()) {
 156     NestedNameSpecifierLoc NestedNameSpecifier =
 157         ElaboratedTypeLoc.getQualifierLoc();
 158     if (NestedNameSpecifier.getNestedNameSpecifier())
 159       return NestedNameSpecifier.getBeginLoc();
 160     TL = TL.getNextTypeLoc();
 161   }
 162   return TL.getLocStart();
 163 }
 164
 165 SourceLocation EndLocationForType(TypeLoc TL) {
 166   // Dig past any namespace or keyword qualifications.
 167   while (TL.getTypeLocClass() == TypeLoc::Elaborated ||
 168          TL.getTypeLocClass() == TypeLoc::Qualified)
 169     TL = TL.getNextTypeLoc();
 170
 171   // The location for template specializations (e.g. Foo<int>) includes the
 172   // templated types in its location range.  We want to restrict this to just
 173   // before the `<` character.
 174   if (TL.getTypeLocClass() == TypeLoc::TemplateSpecialization) {
 175     return TL.castAs<TemplateSpecializationTypeLoc>()
 176         .getLAngleLoc()
 177         .getLocWithOffset(-1);
 178   }
 179   return TL.getEndLoc();
 180 }
 181
 182 NestedNameSpecifier *GetNestedNameForType(TypeLoc TL) {
 183   // Dig past any keyword qualifications.
 184   while (TL.getTypeLocClass() == TypeLoc::Qualified)
 185     TL = TL.getNextTypeLoc();
 186
 187   // For elaborated types (e.g. `struct a::A`) we want the portion after the
 188   // `struct` but including the namespace qualifier, `a::`.
 189   if (auto ElaboratedTypeLoc = TL.getAs<clang::ElaboratedTypeLoc>())
 190     return ElaboratedTypeLoc.getQualifierLoc().getNestedNameSpecifier();
 191   return nullptr;
 192 }
 193
 194 // Find all locations identified by the given USRs for rename.
 195 //
 196 // This class will traverse the AST and find every AST node whose USR is in the
 197 // given USRs' set.
 198 class RenameLocFinder : public RecursiveASTVisitor<RenameLocFinder> {
 199 public:
 200   RenameLocFinder(llvm::ArrayRef<std::string> USRs, ASTContext &Context)
 201       : USRSet(USRs.begin(), USRs.end()), Context(Context) {}
 202
 203   // A structure records all information of a symbol reference being renamed.
 204   // We try to add as few prefix qualifiers as possible.
 205   struct RenameInfo {
 206     // The begin location of a symbol being renamed.
 207     SourceLocation Begin;
 208     // The end location of a symbol being renamed.
 209     SourceLocation End;
 210     // The declaration of a symbol being renamed (can be nullptr).
 211     const NamedDecl *FromDecl;
 212     // The declaration in which the nested name is contained (can be nullptr).
 213     const Decl *Context;
 214     // The nested name being replaced (can be nullptr).
 215     const NestedNameSpecifier *Specifier;
 216   };
 217
 218   // FIXME: Currently, prefix qualifiers will be added to the renamed symbol
 219   // definition (e.g. "class Foo {};" => "class b::Bar {};" when renaming
 220   // "a::Foo" to "b::Bar").
 221   // For renaming declarations/definitions, prefix qualifiers should be filtered
 222   // out.
 223   bool VisitNamedDecl(const NamedDecl *Decl) {
 224     // UsingDecl has been handled in other place.
 225     if (llvm::isa<UsingDecl>(Decl))
 226       return true;
 227
 228     // DestructorDecl has been handled in Typeloc.
 229     if (llvm::isa<CXXDestructorDecl>(Decl))
 230       return true;
 231
 232     if (Decl->isImplicit())
 233       return true;
 234
 235     if (isInUSRSet(Decl)) {
 236       RenameInfo Info = {Decl->getLocation(), Decl->getLocation(), nullptr,
 237                          nullptr, nullptr};
 238       RenameInfos.push_back(Info);
 239     }
 240     return true;
 241   }
 242
 243   bool VisitDeclRefExpr(const DeclRefExpr *Expr) {
 244     const NamedDecl *Decl = Expr->getFoundDecl();
 245     if (isInUSRSet(Decl)) {
 246       RenameInfo Info = {Expr->getSourceRange().getBegin(),
 247                          Expr->getSourceRange().getEnd(), Decl,
 248                          getClosestAncestorDecl(*Expr), Expr->getQualifier()};
 249       RenameInfos.push_back(Info);
 250     }
 251
 252     return true;
 253   }
 254
 255   bool VisitUsingDecl(const UsingDecl *Using) {
 256     for (const auto *UsingShadow : Using->shadows()) {
 257       if (isInUSRSet(UsingShadow->getTargetDecl())) {
 258         UsingDecls.push_back(Using);
 259         break;
 260       }
 261     }
 262     return true;
 263   }
 264
 265   bool VisitNestedNameSpecifierLocations(NestedNameSpecifierLoc NestedLoc) {
 266     if (!NestedLoc.getNestedNameSpecifier()->getAsType())
 267       return true;
 268     if (IsTypeAliasWhichWillBeRenamedElsewhere(NestedLoc.getTypeLoc()))
 269       return true;
 270
 271     if (const auto *TargetDecl =
 272             getSupportedDeclFromTypeLoc(NestedLoc.getTypeLoc())) {
 273       if (isInUSRSet(TargetDecl)) {
 274         RenameInfo Info = {NestedLoc.getBeginLoc(),
 275                            EndLocationForType(NestedLoc.getTypeLoc()),
 276                            TargetDecl, getClosestAncestorDecl(NestedLoc),
 277                            NestedLoc.getNestedNameSpecifier()->getPrefix()};
 278         RenameInfos.push_back(Info);
 279       }
 280     }
 281     return true;
 282   }
 283
 284   bool VisitTypeLoc(TypeLoc Loc) {
 285     if (IsTypeAliasWhichWillBeRenamedElsewhere(Loc))
 286       return true;
 287
 288     auto Parents = Context.getParents(Loc);
 289     TypeLoc ParentTypeLoc;
 290     if (!Parents.empty()) {
 291       // Handle cases of nested name specificier locations.
 292       //
 293       // The VisitNestedNameSpecifierLoc interface is not impelmented in
 294       // RecursiveASTVisitor, we have to handle it explicitly.
 295       if (const auto *NSL = Parents[0].get<NestedNameSpecifierLoc>()) {
 296         VisitNestedNameSpecifierLocations(*NSL);
 297         return true;
 298       }
 299
 300       if (const auto *TL = Parents[0].get<TypeLoc>())
 301         ParentTypeLoc = *TL;
 302     }
 303
 304     // Handle the outermost TypeLoc which is directly linked to the interesting
 305     // declaration and don't handle nested name specifier locations.
 306     if (const auto *TargetDecl = getSupportedDeclFromTypeLoc(Loc)) {
 307       if (isInUSRSet(TargetDecl)) {
 308         // Only handle the outermost typeLoc.
 309         //
 310         // For a type like "a::Foo", there will be two typeLocs for it.
 311         // One ElaboratedType, the other is RecordType:
 312         //
 313         //   ElaboratedType 0x33b9390 'a::Foo' sugar
 314         //   `-RecordType 0x338fef0 'class a::Foo'
 315         //     `-CXXRecord 0x338fe58 'Foo'
 316         //
 317         // Skip if this is an inner typeLoc.
 318         if (!ParentTypeLoc.isNull() &&
 319             isInUSRSet(getSupportedDeclFromTypeLoc(ParentTypeLoc)))
 320           return true;
 321         RenameInfo Info = {StartLocationForType(Loc), EndLocationForType(Loc),
 322                            TargetDecl, getClosestAncestorDecl(Loc),
 323                            GetNestedNameForType(Loc)};
 324         RenameInfos.push_back(Info);
 325         return true;
 326       }
 327     }
 328
 329     // Handle specific template class specialiation cases.
 330     if (const auto *TemplateSpecType =
 331             dyn_cast<TemplateSpecializationType>(Loc.getType())) {
 332       TypeLoc TargetLoc = Loc;
 333       if (!ParentTypeLoc.isNull()) {
 334         if (llvm::isa<ElaboratedType>(ParentTypeLoc.getType()))
 335           TargetLoc = ParentTypeLoc;
 336       }
 337
 338       if (isInUSRSet(TemplateSpecType->getTemplateName().getAsTemplateDecl())) {
 339         TypeLoc TargetLoc = Loc;
 340         // FIXME: Find a better way to handle this case.
 341         // For the qualified template class specification type like
 342         // "ns::Foo<int>" in "ns::Foo<int>& f();", we want the parent typeLoc
 343         // (ElaboratedType) of the TemplateSpecializationType in order to
 344         // catch the prefix qualifiers "ns::".
 345         if (!ParentTypeLoc.isNull() &&
 346             llvm::isa<ElaboratedType>(ParentTypeLoc.getType()))
 347           TargetLoc = ParentTypeLoc;
 348         RenameInfo Info = {
 349             StartLocationForType(TargetLoc), EndLocationForType(TargetLoc),
 350             TemplateSpecType->getTemplateName().getAsTemplateDecl(),
 351             getClosestAncestorDecl(
 352                 ast_type_traits::DynTypedNode::create(TargetLoc)),
 353             GetNestedNameForType(TargetLoc)};
 354         RenameInfos.push_back(Info);
 355       }
 356     }
 357     return true;
 358   }
 359
 360   // Returns a list of RenameInfo.
 361   const std::vector<RenameInfo> &getRenameInfos() const { return RenameInfos; }
 362
 363   // Returns a list of using declarations which are needed to update.
 364   const std::vector<const UsingDecl *> &getUsingDecls() const {
 365     return UsingDecls;
 366   }
 367
 368 private:
 369   // FIXME: This method may not be suitable for renaming other types like alias
 370   // types. Need to figure out a way to handle it.
 371   bool IsTypeAliasWhichWillBeRenamedElsewhere(TypeLoc TL) const {
 372     while (!TL.isNull()) {
 373       // SubstTemplateTypeParm is the TypeLocation class for a substituted type
 374       // inside a template expansion so we ignore these.  For example:
 375       //
 376       // template<typename T> struct S {
 377       //   T t;  // <-- this T becomes a TypeLoc(int) with class
 378       //         //     SubstTemplateTypeParm when S<int> is instantiated
 379       // }
 380       if (TL.getTypeLocClass() == TypeLoc::SubstTemplateTypeParm)
 381         return true;
 382
 383       // Typedef is the TypeLocation class for a type which is a typedef to the
 384       // type we want to replace.  We ignore the use of the typedef as we will
 385       // replace the definition of it.  For example:
 386       //
 387       // typedef int T;
 388       // T a;  // <---  This T is a TypeLoc(int) with class Typedef.
 389       if (TL.getTypeLocClass() == TypeLoc::Typedef)
 390         return true;
 391       TL = TL.getNextTypeLoc();
 392     }
 393     return false;
 394   }
 395
 396   // Get the supported declaration from a given typeLoc. If the declaration type
 397   // is not supported, returns nullptr.
 398   //
 399   // FIXME: support more types, e.g. enum, type alias.
 400   const NamedDecl *getSupportedDeclFromTypeLoc(TypeLoc Loc) {
 401     if (const auto *RD = Loc.getType()->getAsCXXRecordDecl())
 402       return RD;
 403     return nullptr;
 404   }
 405
 406   // Get the closest ancester which is a declaration of a given AST node.
 407   template <typename ASTNodeType>
 408   const Decl *getClosestAncestorDecl(const ASTNodeType &Node) {
 409     auto Parents = Context.getParents(Node);
 410     // FIXME: figure out how to handle it when there are multiple parents.
 411     if (Parents.size() != 1)
 412       return nullptr;
 413     if (ast_type_traits::ASTNodeKind::getFromNodeKind<Decl>().isBaseOf(
 414             Parents[0].getNodeKind()))
 415       return Parents[0].template get<Decl>();
 416     return getClosestAncestorDecl(Parents[0]);
 417   }
 418
 419   // Get the parent typeLoc of a given typeLoc. If there is no such parent,
 420   // return nullptr.
 421   const TypeLoc *getParentTypeLoc(TypeLoc Loc) const {
 422     auto Parents = Context.getParents(Loc);
 423     // FIXME: figure out how to handle it when there are multiple parents.
 424     if (Parents.size() != 1)
 425       return nullptr;
 426     return Parents[0].get<TypeLoc>();
 427   }
 428
 429   // Check whether the USR of a given Decl is in the USRSet.
 430   bool isInUSRSet(const Decl *Decl) const {
 431     auto USR = getUSRForDecl(Decl);
 432     if (USR.empty())
 433       return false;
 434     return llvm::is_contained(USRSet, USR);
 435   }
 436
 437   const std::set<std::string> USRSet;
 438   ASTContext &Context;
 439   std::vector<RenameInfo> RenameInfos;
 440   // Record all interested using declarations which contains the using-shadow
 441   // declarations of the symbol declarations being renamed.
 442   std::vector<const UsingDecl *> UsingDecls;
 443 };
 444
 445 } // namespace
 446
 447 std::vector<SourceLocation>
 448 getLocationsOfUSRs(const std::vector<std::string> &USRs, StringRef PrevName,
 449                    Decl *Decl) {
 450   USRLocFindingASTVisitor Visitor(USRs, PrevName, Decl->getASTContext());
 451   Visitor.TraverseDecl(Decl);
 452   NestedNameSpecifierLocFinder Finder(Decl->getASTContext());
 453
 454   for (const auto &Location : Finder.getNestedNameSpecifierLocations())
 455     Visitor.handleNestedNameSpecifierLoc(Location);
 456
 457   return Visitor.getLocationsFound();
 458 }
 459
 460 std::vector<tooling::AtomicChange>
 461 createRenameAtomicChanges(llvm::ArrayRef<std::string> USRs,
 462                           llvm::StringRef NewName, Decl *TranslationUnitDecl) {
 463   RenameLocFinder Finder(USRs, TranslationUnitDecl->getASTContext());
 464   Finder.TraverseDecl(TranslationUnitDecl);
 465
 466   const SourceManager &SM =
 467       TranslationUnitDecl->getASTContext().getSourceManager();
 468
 469   std::vector<tooling::AtomicChange> AtomicChanges;
 470   auto Replace = [&](SourceLocation Start, SourceLocation End,
 471                      llvm::StringRef Text) {
 472     tooling::AtomicChange ReplaceChange = tooling::AtomicChange(SM, Start);
 473     llvm::Error Err = ReplaceChange.replace(
 474         SM, CharSourceRange::getTokenRange(Start, End), Text);
 475     if (Err) {
 476       llvm::errs() << "Faile to add replacement to AtomicChange: "
 477                    << llvm::toString(std::move(Err)) << "\n";
 478       return;
 479     }
 480     AtomicChanges.push_back(std::move(ReplaceChange));
 481   };
 482
 483   for (const auto &RenameInfo : Finder.getRenameInfos()) {
 484     std::string ReplacedName = NewName.str();
 485     if (RenameInfo.FromDecl && RenameInfo.Context) {
 486       if (!llvm::isa<clang::TranslationUnitDecl>(
 487               RenameInfo.Context->getDeclContext())) {
 488         ReplacedName = tooling::replaceNestedName(
 489             RenameInfo.Specifier, RenameInfo.Context->getDeclContext(),
 490             RenameInfo.FromDecl,
 491             NewName.startswith("::") ? NewName.str() : ("::" + NewName).str());
 492       }
 493     }
 494     // If the NewName contains leading "::", add it back.
 495     if (NewName.startswith("::") && NewName.substr(2) == ReplacedName)
 496       ReplacedName = NewName.str();
 497     Replace(RenameInfo.Begin, RenameInfo.End, ReplacedName);
 498   }
 499
 500   // Hanlde using declarations explicitly as "using a::Foo" don't trigger
 501   // typeLoc for "a::Foo".
 502   for (const auto *Using : Finder.getUsingDecls())
 503     Replace(Using->getLocStart(), Using->getLocEnd(), "using " + NewName.str());
 504
 505   return AtomicChanges;
 506 }
 507
 508 } // end namespace tooling
 509 } // end namespace clang